Slow running query with table with ORDER BY and LIMIT

I have the following query:

SELECT 
m.id_ AS match_id,
mv.id_ AS match_version_id,
t.id_ AS tournament_id
FROM
test.match_version AS mv
JOIN
test.match_ AS m ON m.id_ = mv.match_id
JOIN
test.tournament AS t ON t.orig_id = m.tournament_orig_id
AND t.tour_id = m.tour_id
ORDER BY mv.id_ DESC
LIMIT 100;

It is taking around 4 seconds to run where the match tables have circa 1m rows and the tournament table has circa 30k rows. If I remove the ORDER_BY then it runs in 0.002 seconds.

Here are the CREATE TABLE statements for each table:

CREATE TABLE `match_` (
`id_` int NOT NULL AUTO_INCREMENT,
`tour_id` tinyint NOT NULL,
`tournament_orig_id` int NOT NULL,
PRIMARY KEY (`id_`),
KEY `ix__match__tour_id` (`tour_id`),
KEY `ix__match__tour_id__tournament_orig_id` (`tour_id`,`tournament_orig_id`),
KEY `ix__match__tournament_orig_id` (`tournament_orig_id`),
CONSTRAINT `fk__match__tournament` FOREIGN KEY (`tour_id`, `tournament_orig_id`) REFERENCES `tournament` (`tour_id`, `orig_id`)
) ENGINE=InnoDB AUTO_INCREMENT=1666470 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
CREATE TABLE `match_version` (
`id_` int NOT NULL AUTO_INCREMENT,
`match_id` int NOT NULL,
`generation_start` int NOT NULL DEFAULT '0',
`generation_end` int NOT NULL DEFAULT '0',
PRIMARY KEY (`id_`),
KEY `ix__match_version__match_id` (`match_id`),
KEY `ix__match_version__match_id__generation_end` (`match_id`,`generation_end`),
KEY `ix__match_version__generation_end` (`generation_end`),
CONSTRAINT `fk__match_version__match_id` FOREIGN KEY (`match_id`) REFERENCES `match_` (`id_`)
) ENGINE=InnoDB AUTO_INCREMENT=1669206 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
CREATE TABLE `tournament` (
`id_` int NOT NULL AUTO_INCREMENT,
`tour_id` tinyint NOT NULL,
`orig_id` int NOT NULL,
PRIMARY KEY (`id_`),
UNIQUE KEY `uq__tournament_oc__tour_id__orig_id` (`tour_id`,`orig_id`),
KEY `ix__tournament_oc__tour_id` (`tour_id`),
KEY `ix__tournament_oc__orig_id` (`orig_id`)
) ENGINE=InnoDB AUTO_INCREMENT=30962 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

Here is the EXPLAIN result:

+----+-------------+-------+------------+-------+-------------------------------------------------------------------------------------------------+----------------------------------------+---------+-------------------------------+-------+----------+----------------------------------------------+
| id | select_type | table | partitions | type  |                                          possible_keys                                          |                  key                   | key_len |              ref              | rows  | filtered |                    Extra                     |
+----+-------------+-------+------------+-------+-------------------------------------------------------------------------------------------------+----------------------------------------+---------+-------------------------------+-------+----------+----------------------------------------------+
|  1 | SIMPLE      | t     | NULL       | index | uq__tournament_oc__tour_id__orig_id,ix__tournament_oc__tour_id,ix__tournament_oc__orig_id       | uq__tournament_oc__tour_id__orig_id    |       5 | NULL                          | 30900 |      100 | Using index; Using temporary; Using filesort |
|  1 | SIMPLE      | m     | NULL       | ref   | PRIMARY,ix__match__tour_id,ix__match__tour_id__tournament_orig_id,ix__match__tournament_orig_id | ix__match__tour_id__tournament_orig_id |       5 | test.t.tour_id,test.t.orig_id |    48 |      100 | Using index                                  |
|  1 | SIMPLE      | mv    | NULL       | ref   | ix__match_version__match_id,ix__match_version__match_id__generation_end                         | ix__match_version__match_id            |       4 | test.m.id_                    |     1 |      100 | Using index                                  |
+----+-------------+-------+------------+-------+-------------------------------------------------------------------------------------------------+----------------------------------------+---------+-------------------------------+-------+----------+----------------------------------------------+

How come I'm getting considerably poorer performance when the ORDER_BY is present? How would I solve this?

Note: Worth mentioning that I know it's not ideal that there is no tournament_version.tournament_id foreign key that links to tournament.id_ but that's sadly what I'm working with atm!

Your query appears to be running into issues with the mysql order by limit slow rate look up. Unfortunately, this is a missing optimization in mysql.

See additional details here to understand why this query is slow. At the bottom of the page, it shows some strategies for how to speed up queries like this: https://explainextended.com/2009/10/23/mysql-order-by-limit-performance-late-row-lookups/

If that doesn't work you can try to restructure your query to not include both ORDER BY and LIMIT. As you probably noticed from toying with your query, if you can remove either of those keywords, it will be fast again.

I think your indexes are good, but there are some extras you should get rid of.

Since id_ is the PRIAMRY KEY, it is unnecessary and inefficient to start any other index with id_.

There are no WHERE filtering, so the Optimizer will probably decide to start with an index for the ORDER BY, which exists. This also means that it will stop after 100 rows. The EXPLAIN is not likely to show this stoppage.

A FOREIGN KEY is two things:

• An index (which could be constructed via INDEX -- equally well)
• A dynamic check in the other table that there is a link.

With ENGINE=InnoDB, the PRIMARY KEY is silently tacked on the end of each secondary index. So it is redundant (optional) to add id_ at the end of the above indexes.

Tip. And this may actually help with performance:

When you have INDEX(a,b) (or UNIQUE(a,b)), do not also have INDEX(a). It is redundant, wastes space, and may trick the Optimizer into using the shorter index instead of the composite one. (I see one such case in each table definition.)

If the EXPLAIN fails to list mv as the first table, there are multiple ways to force it to be used first.

Thanks to @tay_inc for the link. This code executes in 0.04 seconds:

SELECT 
m.id_ AS match_id,
mv.id_ AS match_version_id,
t.id_ AS tournament_id
FROM
test.match_version AS mv
JOIN
test.match_ AS m ON m.id_ = mv.match_id
JOIN
test.tournament AS t ON t.orig_id = m.tournament_orig_id
AND t.tour_id = m.tour_id
JOIN
(
SELECT 
mv.id_ AS match_version_id
FROM
test.match_version AS mv
ORDER BY mv.id_ DESC
LIMIT 100
) AS o ON o.match_version_id = mv.id_
ORDER BY mv.id_ DESC;

The only issue I can see is that this takes the last 100 records in mv regardless of whether they can be joined to m and t. Not an issue for me in this case but worth bearing in mind...