Description:
I found a missed ORDER BY ... LIMIT optimization in MySQL 9.7.1.
The testcase has a simple two-table INNER JOIN:
t1.c0 = t0.c0
The original query orders by:
ORDER BY t0.c0 ASC, t1.c3 DESC
Because of the join equality t1.c0 = t0.c0, the leading ORDER BY key t0.c0 is equivalent to t1.c0 on joined rows. Therefore, for the joined result, the following ORDER BY is semantically equivalent:
ORDER BY t1.c0 ASC, t1.c3 DESC
However, MySQL chooses a much slower plan for the original query and a much faster plan for the equivalent rewrite.
Original query:
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;
Equivalent rewrite:
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 DESC
LIMIT 3;
The generated data shape is:
t0 rows: 48000
t1 rows: 72000
NDV(t0.c0): 4000
NDV(t1.c0): 4000
t0 rows per key: 12
t1 rows per key: 18
join rows before filter: 864000
join rows after filter: 859680
For the original query, EXPLAIN ANALYZE shows:
Limit: 3 row(s) (actual time=1777..1777 rows=3 loops=1)
Sort: t0.c0, t1.c3 DESC
Stream results (actual time=0.0225..1595 rows=859680 loops=1)
Nested loop inner join (actual time=0.0204..1415 rows=859680 loops=1)
Table scan on t0 (actual rows=48000)
Index lookup on t1 using idx_t1_c0 (actual rows=18 loops=47760)
So the original query scans t0, does 47760 index lookups into t1, produces the full joined result, sorts it, and only then applies LIMIT 3. Runtime is about 1777 ms.
For the equivalent ORDER BY rewrite, EXPLAIN ANALYZE shows:
Limit: 3 row(s) (actual time=191..191 rows=3 loops=1)
Nested loop inner join (actual time=191..191 rows=3 loops=1)
Sort: t1.c0, t1.c3 DESC (actual rows=19 loops=1)
Covering index scan on t1 using idx_t1_c3_c0_c2
Index lookup on t0 using idx_t0_c0_c1 (actual loops=19)
The rewritten query sorts t1 first and only probes t0 19 times before satisfying LIMIT 3. Runtime is about 191 ms.
The first result rows of the original ORDER BY and rewritten ORDER BY are the same in the testcase, as expected from the equality t0.c0 = t1.c0.
With LIMIT 300, the same pattern remains:
Original ORDER BY:
actual time about 1800 ms
processes/sorts 859680 joined rows
Equivalent ORDER BY rewrite:
actual time about 86 ms
probes t0 only 43 times
Changing optimizer_switch prefer_ordering_index between on and off does not change the original slow plan.
This looks like the optimizer does not use equality-propagated ORDER BY keys for ORDER BY ... LIMIT planning. It does not recognize that ORDER BY t0.c0, t1.c3 can be treated as ORDER BY t1.c0, t1.c3 because t0.c0 = t1.c0, and therefore misses a much faster sort-before-join / early-stop plan.
How to repeat:
Run the attached SQL testcase:
mysql < mysql_order_limit_equivalent_order_key_missed.sql > result.txt
The testcase creates a fresh database:
mysql_order_limit_equivalent_order_key_missed
It creates two tables, inserts deterministic data, creates indexes, runs ANALYZE TABLE, and then compares:
1. Original query:
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;
2. Equivalent ORDER BY rewrite:
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 DESC
LIMIT 3;
Expected observation:
The original query processes the full join result and sorts it, taking around 1.7s on my machine.
The equivalent ORDER BY rewrite sorts t1 first, probes t0 only a few times, and finishes much faster. In my run it took about 191 ms for LIMIT 3 and about 86 ms for LIMIT 300.
The SQL file also checks prefer_ordering_index=on/off and a LIMIT 300 variant.
Suggested fix:
When optimizing ORDER BY ... LIMIT over INNER JOIN equalities, consider ORDER BY key equivalence classes before choosing the join order and sort strategy.
In this testcase, t0.c0 and t1.c0 are equal because of the join condition t1.c0 = t0.c0. The optimizer should be able to recognize that:
ORDER BY t0.c0 ASC, t1.c3 DESC
is equivalent on joined rows to:
ORDER BY t1.c0 ASC, t1.c3 DESC
This would allow the optimizer to consider the faster plan that sorts/reads the t1 side first and then probes t0, stopping early after LIMIT is satisfied.
The cost model should account for the early-stop effect of LIMIT when such an equality-propagated ORDER BY key makes a sorted outer-table plan possible.
Description: I found a missed ORDER BY ... LIMIT optimization in MySQL 9.7.1. The testcase has a simple two-table INNER JOIN: t1.c0 = t0.c0 The original query orders by: ORDER BY t0.c0 ASC, t1.c3 DESC Because of the join equality t1.c0 = t0.c0, the leading ORDER BY key t0.c0 is equivalent to t1.c0 on joined rows. Therefore, for the joined result, the following ORDER BY is semantically equivalent: ORDER BY t1.c0 ASC, t1.c3 DESC However, MySQL chooses a much slower plan for the original query and a much faster plan for the equivalent rewrite. Original query: SELECT t1.c2 AS ref0 FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 WHERE t0.c4 IS NOT NULL ORDER BY t0.c0 ASC, t1.c3 DESC LIMIT 3; Equivalent rewrite: SELECT t1.c2 AS ref0 FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 WHERE t0.c4 IS NOT NULL ORDER BY t1.c0 ASC, t1.c3 DESC LIMIT 3; The generated data shape is: t0 rows: 48000 t1 rows: 72000 NDV(t0.c0): 4000 NDV(t1.c0): 4000 t0 rows per key: 12 t1 rows per key: 18 join rows before filter: 864000 join rows after filter: 859680 For the original query, EXPLAIN ANALYZE shows: Limit: 3 row(s) (actual time=1777..1777 rows=3 loops=1) Sort: t0.c0, t1.c3 DESC Stream results (actual time=0.0225..1595 rows=859680 loops=1) Nested loop inner join (actual time=0.0204..1415 rows=859680 loops=1) Table scan on t0 (actual rows=48000) Index lookup on t1 using idx_t1_c0 (actual rows=18 loops=47760) So the original query scans t0, does 47760 index lookups into t1, produces the full joined result, sorts it, and only then applies LIMIT 3. Runtime is about 1777 ms. For the equivalent ORDER BY rewrite, EXPLAIN ANALYZE shows: Limit: 3 row(s) (actual time=191..191 rows=3 loops=1) Nested loop inner join (actual time=191..191 rows=3 loops=1) Sort: t1.c0, t1.c3 DESC (actual rows=19 loops=1) Covering index scan on t1 using idx_t1_c3_c0_c2 Index lookup on t0 using idx_t0_c0_c1 (actual loops=19) The rewritten query sorts t1 first and only probes t0 19 times before satisfying LIMIT 3. Runtime is about 191 ms. The first result rows of the original ORDER BY and rewritten ORDER BY are the same in the testcase, as expected from the equality t0.c0 = t1.c0. With LIMIT 300, the same pattern remains: Original ORDER BY: actual time about 1800 ms processes/sorts 859680 joined rows Equivalent ORDER BY rewrite: actual time about 86 ms probes t0 only 43 times Changing optimizer_switch prefer_ordering_index between on and off does not change the original slow plan. This looks like the optimizer does not use equality-propagated ORDER BY keys for ORDER BY ... LIMIT planning. It does not recognize that ORDER BY t0.c0, t1.c3 can be treated as ORDER BY t1.c0, t1.c3 because t0.c0 = t1.c0, and therefore misses a much faster sort-before-join / early-stop plan. How to repeat: Run the attached SQL testcase: mysql < mysql_order_limit_equivalent_order_key_missed.sql > result.txt The testcase creates a fresh database: mysql_order_limit_equivalent_order_key_missed It creates two tables, inserts deterministic data, creates indexes, runs ANALYZE TABLE, and then compares: 1. Original query: SELECT t1.c2 AS ref0 FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 WHERE t0.c4 IS NOT NULL ORDER BY t0.c0 ASC, t1.c3 DESC LIMIT 3; 2. Equivalent ORDER BY rewrite: SELECT t1.c2 AS ref0 FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 WHERE t0.c4 IS NOT NULL ORDER BY t1.c0 ASC, t1.c3 DESC LIMIT 3; Expected observation: The original query processes the full join result and sorts it, taking around 1.7s on my machine. The equivalent ORDER BY rewrite sorts t1 first, probes t0 only a few times, and finishes much faster. In my run it took about 191 ms for LIMIT 3 and about 86 ms for LIMIT 300. The SQL file also checks prefer_ordering_index=on/off and a LIMIT 300 variant. Suggested fix: When optimizing ORDER BY ... LIMIT over INNER JOIN equalities, consider ORDER BY key equivalence classes before choosing the join order and sort strategy. In this testcase, t0.c0 and t1.c0 are equal because of the join condition t1.c0 = t0.c0. The optimizer should be able to recognize that: ORDER BY t0.c0 ASC, t1.c3 DESC is equivalent on joined rows to: ORDER BY t1.c0 ASC, t1.c3 DESC This would allow the optimizer to consider the faster plan that sorts/reads the t1 side first and then probes t0, stopping early after LIMIT is satisfied. The cost model should account for the early-stop effect of LIMIT when such an equality-propagated ORDER BY key makes a sorted outer-table plan possible.