Description:
A semantically equivalent rewrite of a range predicate across an INNER JOIN
equality causes MySQL to choose a very different execution plan.
The original query contains:
t3.c1 = t0.c0
AND t3.c1 < 1832658698
The rewritten query only changes the range predicate to:
t3.c1 = t0.c0
AND t0.c0 < 1832658698
Therefore, the two queries are equivalent.
However, MySQL estimates the rewritten query as much more expensive while it
actually runs substantially faster.
On MySQL 9.7.1, using the attached reproduction:
Original query:
estimated cost: 27742.787
EXPLAIN ANALYZE times: 2139 ms, 3150 ms, 2826 ms
median: 2826 ms
Equivalent rewrite:
estimated cost: 80343.932
EXPLAIN ANALYZE times: 982 ms, 996 ms, 992 ms
median: 992 ms
Thus:
Cost(rewrite) / Cost(original) = 2.90x
while:
Runtime(original) / Runtime(rewrite) = 2.85x
That is, the optimizer ranks the substantially faster plan as substantially
more expensive.
The two queries return identical results. The reproduction checks:
row_count = 1575991
sum_c1 = 3137439
sumsq_c1 = 9342431
for both queries.
PLAN DIFFERENCE
---------------
The original query chooses approximately:
t3
-> index lookup t1
-> index lookup t0
-> Sort(t1.c1 DESC)
The join produces about 1.58 million rows at runtime, and the final Sort
therefore sorts about 1.58 million rows.
The equivalent rewrite instead chooses:
Sort(t1.c1 DESC)
-> t1
-> index lookup t3
-> index lookup t0
Here the Sort is performed on t1 before join fanout. t1 contains only 502 rows,
and the nested-loop joins preserve the outer ordering.
EXPLAIN ANALYZE confirms that the Sort in this plan processes only 502 rows.
SAME-QUERY CONTROL
------------------
The faster physical strategy is also available to the original query without
rewriting the predicate.
Adding only:
/*+ JOIN_ORDER(t1, t3, t0) */
to the original query gives:
estimated cost: 30706.599
EXPLAIN ANALYZE times: 1005 ms, 1002 ms, 991 ms
median: 1002 ms
Therefore, for exactly the same SQL semantics and predicate:
default plan cost: 27742.787
forced fast plan cost: 30706.599
but:
default median runtime: 2826 ms
forced median runtime: 1002 ms
The optimizer therefore already has access to a roughly 2.82x faster join
order, but considers it more expensive.
ORDER BY CONTROL
----------------
Removing ORDER BY almost completely removes the runtime difference.
Without ORDER BY:
Original:
987 ms, 986 ms, 982 ms
median: 986 ms
Equivalent rewrite:
984 ms, 1104 ms, 985 ms
median: 985 ms
This indicates that the performance regression is mainly caused by ORDER BY
placement rather than by the underlying joins themselves.
OPTIMIZER TRACE
---------------
I also enabled optimizer_trace with optimizer_prune_level=0 to determine
whether the faster t1-first join order was missing from plan enumeration.
It was not missing.
For the original query, optimizer_trace explicitly considers:
t1 -> t3 -> t0
with:
rows_for_plan = 223602
cost_for_plan = 30706.6
sort_cost = 223602
new_cost_for_plan = 254309
The chosen t3 -> t1 -> t0 order is costed as:
rows_for_plan = 223602
cost_for_plan = 27742.8
sort_cost = 223602
new_cost_for_plan = 251345
Therefore the optimizer chooses t3 -> t1 -> t0 because:
251345 < 254309
However, when t1 -> t3 -> t0 is actually selected, either through the
equivalent rewrite or JOIN_ORDER, the finalized physical plan does not sort
223602 joined rows.
The later optimizer trace instead reports:
adding_sort_to_table: "t1"
and EXPLAIN shows that only the 502-row t1 input is sorted before the nested-loop
joins.
This suggests a mismatch between join-order costing and the physical ORDER BY
implementation used after that join order is selected.
During join-order comparison, the t1-first candidate appears to be charged a
sort cost based on the estimated final join cardinality. Later plan
construction recognizes that this join order can satisfy ORDER BY by sorting
the small outer table before join fanout.
As a result, the optimizer rejects a join order that is about 2.8x faster in
practice.
How to repeat:
1. Run the attached file:
mysql_orderby_rewrite_cost_inversion_repro.sql
on MySQL 9.7.1.
2. The script creates the database mysql_orderby_cost_repro, loads the test
data, creates the required indexes, and runs ANALYZE TABLE.
3. Compare EXPLAIN FORMAT=JSON and the three EXPLAIN ANALYZE executions for the
original query:
SELECT t1.c1 AS ref0
FROM t3
INNER JOIN t0 ON t3.c1 = t0.c0
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 < 1832658698
ORDER BY t1.c1 DESC;
with the semantically equivalent rewrite:
SELECT t1.c1 AS ref0
FROM t3
INNER JOIN t0 ON t3.c1 = t0.c0
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t0.c0 < 1832658698
ORDER BY t1.c1 DESC;
4. Take the median of the three root-node actual times.
On my system:
Original:
cost = 27742.787
median runtime = 2826 ms
Rewrite:
cost = 80343.932
median runtime = 992 ms
5. The script also checks result equivalence. Both queries produce:
row_count = 1575991
sum_c1 = 3137439
sumsq_c1 = 9342431
6. Compare the original query with the same query plus:
/*+ JOIN_ORDER(t1, t3, t0) */
On my system:
default median = 2826 ms
JOIN_ORDER median = 1002 ms
although the hinted plan has the higher estimated cost
(30706.599 vs. 27742.787).
7. Run the included queries without ORDER BY.
The median runtimes become approximately identical:
original = 986 ms
rewrite = 985 ms
8. The final sections of the script enable optimizer_trace.
In the trace for the original query, inspect considered_execution_plans.
The t1 -> t3 -> t0 candidate is present and has approximately:
cost_for_plan = 30706.6
sort_cost = 223602
new_cost_for_plan = 254309
The selected t3 -> t1 -> t0 candidate has:
cost_for_plan = 27742.8
sort_cost = 223602
new_cost_for_plan = 251345
9. In the optimizer trace for the forced t1 -> t3 -> t0 order, inspect the
final ORDER BY planning stage.
It reports:
adding_sort_to_table: "t1"
The corresponding EXPLAIN plan sorts only the 502-row t1 input before the
joins.
Suggested fix:
Please consider making ORDER BY cost part of join-order comparison reflect the
ordering strategy that can actually be used by each candidate join order.
In this example, the t1 -> t3 -> t0 nested-loop plan can sort the 502-row outer
table t1 before join fanout and preserve that ordering through the joins.
However, during join-order enumeration the candidate appears to receive a sort
cost based on the estimated final join cardinality (223602 rows), the same sort
cost assigned to the plan that really requires a final-result sort.
If possible, the optimizer should account for the pre-fanout sort/order-
preserving property when ranking join orders, rather than discovering this
cheaper ORDER BY implementation only after the join order has already been
selected.
It may also be worth checking why the equality-equivalent forms
t3.c1 < constant
and
t0.c0 < constant
receive different selectivity treatment during optimization, since that
difference is what makes the rewrite expose the faster join order in this
reproduction.
Description: A semantically equivalent rewrite of a range predicate across an INNER JOIN equality causes MySQL to choose a very different execution plan. The original query contains: t3.c1 = t0.c0 AND t3.c1 < 1832658698 The rewritten query only changes the range predicate to: t3.c1 = t0.c0 AND t0.c0 < 1832658698 Therefore, the two queries are equivalent. However, MySQL estimates the rewritten query as much more expensive while it actually runs substantially faster. On MySQL 9.7.1, using the attached reproduction: Original query: estimated cost: 27742.787 EXPLAIN ANALYZE times: 2139 ms, 3150 ms, 2826 ms median: 2826 ms Equivalent rewrite: estimated cost: 80343.932 EXPLAIN ANALYZE times: 982 ms, 996 ms, 992 ms median: 992 ms Thus: Cost(rewrite) / Cost(original) = 2.90x while: Runtime(original) / Runtime(rewrite) = 2.85x That is, the optimizer ranks the substantially faster plan as substantially more expensive. The two queries return identical results. The reproduction checks: row_count = 1575991 sum_c1 = 3137439 sumsq_c1 = 9342431 for both queries. PLAN DIFFERENCE --------------- The original query chooses approximately: t3 -> index lookup t1 -> index lookup t0 -> Sort(t1.c1 DESC) The join produces about 1.58 million rows at runtime, and the final Sort therefore sorts about 1.58 million rows. The equivalent rewrite instead chooses: Sort(t1.c1 DESC) -> t1 -> index lookup t3 -> index lookup t0 Here the Sort is performed on t1 before join fanout. t1 contains only 502 rows, and the nested-loop joins preserve the outer ordering. EXPLAIN ANALYZE confirms that the Sort in this plan processes only 502 rows. SAME-QUERY CONTROL ------------------ The faster physical strategy is also available to the original query without rewriting the predicate. Adding only: /*+ JOIN_ORDER(t1, t3, t0) */ to the original query gives: estimated cost: 30706.599 EXPLAIN ANALYZE times: 1005 ms, 1002 ms, 991 ms median: 1002 ms Therefore, for exactly the same SQL semantics and predicate: default plan cost: 27742.787 forced fast plan cost: 30706.599 but: default median runtime: 2826 ms forced median runtime: 1002 ms The optimizer therefore already has access to a roughly 2.82x faster join order, but considers it more expensive. ORDER BY CONTROL ---------------- Removing ORDER BY almost completely removes the runtime difference. Without ORDER BY: Original: 987 ms, 986 ms, 982 ms median: 986 ms Equivalent rewrite: 984 ms, 1104 ms, 985 ms median: 985 ms This indicates that the performance regression is mainly caused by ORDER BY placement rather than by the underlying joins themselves. OPTIMIZER TRACE --------------- I also enabled optimizer_trace with optimizer_prune_level=0 to determine whether the faster t1-first join order was missing from plan enumeration. It was not missing. For the original query, optimizer_trace explicitly considers: t1 -> t3 -> t0 with: rows_for_plan = 223602 cost_for_plan = 30706.6 sort_cost = 223602 new_cost_for_plan = 254309 The chosen t3 -> t1 -> t0 order is costed as: rows_for_plan = 223602 cost_for_plan = 27742.8 sort_cost = 223602 new_cost_for_plan = 251345 Therefore the optimizer chooses t3 -> t1 -> t0 because: 251345 < 254309 However, when t1 -> t3 -> t0 is actually selected, either through the equivalent rewrite or JOIN_ORDER, the finalized physical plan does not sort 223602 joined rows. The later optimizer trace instead reports: adding_sort_to_table: "t1" and EXPLAIN shows that only the 502-row t1 input is sorted before the nested-loop joins. This suggests a mismatch between join-order costing and the physical ORDER BY implementation used after that join order is selected. During join-order comparison, the t1-first candidate appears to be charged a sort cost based on the estimated final join cardinality. Later plan construction recognizes that this join order can satisfy ORDER BY by sorting the small outer table before join fanout. As a result, the optimizer rejects a join order that is about 2.8x faster in practice. How to repeat: 1. Run the attached file: mysql_orderby_rewrite_cost_inversion_repro.sql on MySQL 9.7.1. 2. The script creates the database mysql_orderby_cost_repro, loads the test data, creates the required indexes, and runs ANALYZE TABLE. 3. Compare EXPLAIN FORMAT=JSON and the three EXPLAIN ANALYZE executions for the original query: SELECT t1.c1 AS ref0 FROM t3 INNER JOIN t0 ON t3.c1 = t0.c0 INNER JOIN t1 ON t3.c0 = t1.c0 WHERE t3.c1 < 1832658698 ORDER BY t1.c1 DESC; with the semantically equivalent rewrite: SELECT t1.c1 AS ref0 FROM t3 INNER JOIN t0 ON t3.c1 = t0.c0 INNER JOIN t1 ON t3.c0 = t1.c0 WHERE t0.c0 < 1832658698 ORDER BY t1.c1 DESC; 4. Take the median of the three root-node actual times. On my system: Original: cost = 27742.787 median runtime = 2826 ms Rewrite: cost = 80343.932 median runtime = 992 ms 5. The script also checks result equivalence. Both queries produce: row_count = 1575991 sum_c1 = 3137439 sumsq_c1 = 9342431 6. Compare the original query with the same query plus: /*+ JOIN_ORDER(t1, t3, t0) */ On my system: default median = 2826 ms JOIN_ORDER median = 1002 ms although the hinted plan has the higher estimated cost (30706.599 vs. 27742.787). 7. Run the included queries without ORDER BY. The median runtimes become approximately identical: original = 986 ms rewrite = 985 ms 8. The final sections of the script enable optimizer_trace. In the trace for the original query, inspect considered_execution_plans. The t1 -> t3 -> t0 candidate is present and has approximately: cost_for_plan = 30706.6 sort_cost = 223602 new_cost_for_plan = 254309 The selected t3 -> t1 -> t0 candidate has: cost_for_plan = 27742.8 sort_cost = 223602 new_cost_for_plan = 251345 9. In the optimizer trace for the forced t1 -> t3 -> t0 order, inspect the final ORDER BY planning stage. It reports: adding_sort_to_table: "t1" The corresponding EXPLAIN plan sorts only the 502-row t1 input before the joins. Suggested fix: Please consider making ORDER BY cost part of join-order comparison reflect the ordering strategy that can actually be used by each candidate join order. In this example, the t1 -> t3 -> t0 nested-loop plan can sort the 502-row outer table t1 before join fanout and preserve that ordering through the joins. However, during join-order enumeration the candidate appears to receive a sort cost based on the estimated final join cardinality (223602 rows), the same sort cost assigned to the plan that really requires a final-result sort. If possible, the optimizer should account for the pre-fanout sort/order- preserving property when ranking join orders, rather than discovering this cheaper ORDER BY implementation only after the join order has already been selected. It may also be worth checking why the equality-equivalent forms t3.c1 < constant and t0.c0 < constant receive different selectivity treatment during optimization, since that difference is what makes the rewrite expose the faster join order in this reproduction.