Extremely slow sql query when using multiple inner join and order clauses

I have a MySQL database with three relevant tables, t1 with 6598 rows, t2 with 1713 rows and t3 with 10023 rows.

Details:

TABLE t1 (
    `id` SERIAL,
    `t2_id` BIGINT UNSIGNED NOT NULL,
    `t3_id` BIGINT UNSIGNED,
    PRIMARY KEY (`id`),
    FOREIGN KEY (t2_id) REFERENCES t2(id),
    FOREIGN KEY (t3_id) REFERENCES t3(id)   
);

TABLE t2(
    `id` SERIAL,
    `name` VARCHAR(128) NOT NULL,
    PRIMARY KEY (`id`)
);

TABLE t3 (
    `id` SERIAL,
    `name` VARCHAR(128),
    PRIMARY KEY (`id`)
);

I want perform the following query but it does not finish (takes forever basically):

SELECT *
FROM t1
INNER JOIN t3
ON t1.t3_id = t3.id
INNER JOIN t2
ON t1.t2_id = t2.id
WHERE (t3.name NOT NULL)
ORDER BY t3.name ASC , t1.id ASC
LIMIT 25

When i remove the order clause it works very fast (0.17 sec).

How could i change the query to make it work?

Solution

I can suggest the following indices:

CREATE INDEX idx_t1 ON t1 (t2_id, t3_id, id);
CREATE INDEX idx_t3 ON t3 (id, name);

These indices at the very least should substantially speed up the joins. If used, MySQL would most likely be taking the following joining strategy:

SELECT *
FROM t2
INNER JOIN t1
    ON t2.id = t1.t2_id
INNER JOIN t3
    ON t1.t3_id = t3.id
WHERE
    t3.name IS NOT NULL
ORDER BY
    t3.name,
    t1.id
LIMIT 25;

The idea here is that we do a full table scan on t2, which is by far the smallest table. There are no restrictions on the records in t2 anyway, so we might as well scan this first. Then, for each of the joins to t1 and t3 we try to use the indices setup. Note that because your tables have relatively few columns, the two indices defined can easily cover all columns, thereby increasing the likelihood that MySQL will choose to use the indices.