Description:
A range predicate on one side of an INNER JOIN equality is not utilized in the same way as the equivalent predicate written explicitly on the other side, causing the optimizer to miss a substantially cheaper and faster join order.
The testcase contains the following join equality:
lookup_dim.join_key = fact_rows.lookup_key
The original query has the range predicate only on lookup_dim.join_key:
lookup_dim.join_key <= 1865571077
Because this is an INNER JOIN, the following predicate is equivalent for all joined rows:
fact_rows.lookup_key <= 1865571077
I compared the original query with two counterfactual queries:
1. The range predicate is moved to the equality-equivalent column
fact_rows.lookup_key.
2. The equivalent predicate is added in addition to the original predicate.
This second predicate is logically redundant because it is implied by the
join equality and the original range predicate.
All three queries return exactly the same result: 203 rows with the same
checksum.
However, MySQL chooses very different join orders.
Original query:
fanout_rows -> fact_rows -> lookup_dim
Estimated cost: 32306
Median runtime over three EXPLAIN ANALYZE executions: 464.806 ms
Equivalent-predicate counterfactual:
fact_rows -> lookup_dim -> fanout_rows
Estimated cost: 13672
Median runtime: 3.890 ms
This plan is about 119.5x faster, and MySQL's own cost model also estimates
it to be about 2.36x cheaper.
More importantly, simply adding the logically redundant equivalent predicate:
lookup_dim.join_key <= 1865571077
AND fact_rows.lookup_key <= 1865571077
also changes the plan to:
fact_rows -> lookup_dim -> fanout_rows
with the same estimated cost of 13672 and a median runtime of 3.731 ms,
about 124.6x faster than the original query.
This suggests that the problem is not only a runtime/cost-model mismatch.
The optimizer itself considers the counterfactual plan substantially cheaper,
but that plan is not selected when the range predicate is present only on the
other side of the join equality.
There is also evidence that MySQL does derive the equivalent predicate.
In the EXPLAIN output for the original query, the filter is shown as:
fact_rows.lookup_key <= 1865571077
even though the SQL query only contains the predicate on
lookup_dim.join_key.
However, this derived predicate does not appear to have the same effect
during join-order optimization as an explicitly written predicate.
For the original query, MySQL first joins fanout_rows with fact_rows,
producing 189197 intermediate rows, and then performs 189197 index lookups
into lookup_dim before returning only 203 final rows.
For the equivalent-predicate plan, MySQL scans 1874 fact_rows, joins them
with lookup_dim first, obtains only 2 intermediate rows, and performs only
2 lookups into fanout_rows.
Therefore, the issue appears to be that a range predicate derived through
a join equality is not made available or costed equivalently during
join-order enumeration, even though the equivalent condition is recognized
later by the optimizer.
How to repeat:
1. Run the attached SQL testcase on MySQL 9.7.1.
The testcase creates three tables, loads the reproducing data, creates the
required indexes, and runs ANALYZE TABLE.
2. Compare the following three queries.
Original query:
SELECT f.group_key, l.payload
FROM fact_rows AS f
INNER JOIN fanout_rows AS d
ON f.group_key = d.group_key
INNER JOIN lookup_dim AS l
ON f.lookup_key = l.join_key
WHERE l.join_key <= 1865571077;
Equivalent-predicate counterfactual:
SELECT f.group_key, l.payload
FROM fact_rows AS f
INNER JOIN fanout_rows AS d
ON f.group_key = d.group_key
INNER JOIN lookup_dim AS l
ON f.lookup_key = l.join_key
WHERE f.lookup_key <= 1865571077;
Redundant-predicate counterfactual:
SELECT f.group_key, l.payload
FROM fact_rows AS f
INNER JOIN fanout_rows AS d
ON f.group_key = d.group_key
INNER JOIN lookup_dim AS l
ON f.lookup_key = l.join_key
WHERE l.join_key <= 1865571077
AND f.lookup_key <= 1865571077;
3. Verify that all three queries return the same result.
In my run:
row count = 203
and all three queries produced the same checksum.
4. Run EXPLAIN for all three queries.
Observed plans:
Original:
fanout_rows -> fact_rows -> lookup_dim
cost = 32306
Equivalent/redundant predicate:
fact_rows -> lookup_dim -> fanout_rows
cost = 13672
5. Run EXPLAIN ANALYZE three times for each query and compare the median
execution time.
Observed on MySQL 9.7.1:
Original:
464.806 ms
462.017 ms
471.860 ms
median = 464.806 ms
Equivalent predicate:
3.890 ms
3.332 ms
5.741 ms
median = 3.890 ms
Redundant predicate:
3.546 ms
3.731 ms
5.916 ms
median = 3.731 ms
The equivalent-predicate plan is about 119.5x faster.
The redundant-predicate plan is about 124.6x faster.
Attached files:
mysql_join_equality_range_predicate_repro.sql: complete self-contained reproduction script, including database/table creation, test data, indexes, ANALYZE TABLE, correctness checks, EXPLAIN, and three EXPLAIN ANALYZE runs for each query.
mysql_join_equality_range_predicate_repro.txt: complete output produced by running the reproduction script on MySQL 9.7.1.
Suggested fix:
Please consider making range predicates derived through INNER JOIN equality
classes available consistently during join-order enumeration and access-path
costing.
For example, given:
A.x = B.x
AND A.x <= constant
the optimizer should be able to use the implied predicate:
B.x <= constant
during the same optimization phase as if B.x <= constant had been written
explicitly in the SQL text.
In this testcase, MySQL appears to derive the equivalent predicate eventually,
because it is visible in the final EXPLAIN output, but the derived predicate
does not have the same effect on join-order selection as the explicitly written
predicate.
It may therefore be useful to ensure that equality-derived range predicates
are propagated before, or made directly available to, join-order enumeration
and cardinality/access-path costing.
The propagated predicates should also preferably be deduplicated, since the
redundant-predicate query currently shows the same range condition twice in
the final plan.
Description: A range predicate on one side of an INNER JOIN equality is not utilized in the same way as the equivalent predicate written explicitly on the other side, causing the optimizer to miss a substantially cheaper and faster join order. The testcase contains the following join equality: lookup_dim.join_key = fact_rows.lookup_key The original query has the range predicate only on lookup_dim.join_key: lookup_dim.join_key <= 1865571077 Because this is an INNER JOIN, the following predicate is equivalent for all joined rows: fact_rows.lookup_key <= 1865571077 I compared the original query with two counterfactual queries: 1. The range predicate is moved to the equality-equivalent column fact_rows.lookup_key. 2. The equivalent predicate is added in addition to the original predicate. This second predicate is logically redundant because it is implied by the join equality and the original range predicate. All three queries return exactly the same result: 203 rows with the same checksum. However, MySQL chooses very different join orders. Original query: fanout_rows -> fact_rows -> lookup_dim Estimated cost: 32306 Median runtime over three EXPLAIN ANALYZE executions: 464.806 ms Equivalent-predicate counterfactual: fact_rows -> lookup_dim -> fanout_rows Estimated cost: 13672 Median runtime: 3.890 ms This plan is about 119.5x faster, and MySQL's own cost model also estimates it to be about 2.36x cheaper. More importantly, simply adding the logically redundant equivalent predicate: lookup_dim.join_key <= 1865571077 AND fact_rows.lookup_key <= 1865571077 also changes the plan to: fact_rows -> lookup_dim -> fanout_rows with the same estimated cost of 13672 and a median runtime of 3.731 ms, about 124.6x faster than the original query. This suggests that the problem is not only a runtime/cost-model mismatch. The optimizer itself considers the counterfactual plan substantially cheaper, but that plan is not selected when the range predicate is present only on the other side of the join equality. There is also evidence that MySQL does derive the equivalent predicate. In the EXPLAIN output for the original query, the filter is shown as: fact_rows.lookup_key <= 1865571077 even though the SQL query only contains the predicate on lookup_dim.join_key. However, this derived predicate does not appear to have the same effect during join-order optimization as an explicitly written predicate. For the original query, MySQL first joins fanout_rows with fact_rows, producing 189197 intermediate rows, and then performs 189197 index lookups into lookup_dim before returning only 203 final rows. For the equivalent-predicate plan, MySQL scans 1874 fact_rows, joins them with lookup_dim first, obtains only 2 intermediate rows, and performs only 2 lookups into fanout_rows. Therefore, the issue appears to be that a range predicate derived through a join equality is not made available or costed equivalently during join-order enumeration, even though the equivalent condition is recognized later by the optimizer. How to repeat: 1. Run the attached SQL testcase on MySQL 9.7.1. The testcase creates three tables, loads the reproducing data, creates the required indexes, and runs ANALYZE TABLE. 2. Compare the following three queries. Original query: SELECT f.group_key, l.payload FROM fact_rows AS f INNER JOIN fanout_rows AS d ON f.group_key = d.group_key INNER JOIN lookup_dim AS l ON f.lookup_key = l.join_key WHERE l.join_key <= 1865571077; Equivalent-predicate counterfactual: SELECT f.group_key, l.payload FROM fact_rows AS f INNER JOIN fanout_rows AS d ON f.group_key = d.group_key INNER JOIN lookup_dim AS l ON f.lookup_key = l.join_key WHERE f.lookup_key <= 1865571077; Redundant-predicate counterfactual: SELECT f.group_key, l.payload FROM fact_rows AS f INNER JOIN fanout_rows AS d ON f.group_key = d.group_key INNER JOIN lookup_dim AS l ON f.lookup_key = l.join_key WHERE l.join_key <= 1865571077 AND f.lookup_key <= 1865571077; 3. Verify that all three queries return the same result. In my run: row count = 203 and all three queries produced the same checksum. 4. Run EXPLAIN for all three queries. Observed plans: Original: fanout_rows -> fact_rows -> lookup_dim cost = 32306 Equivalent/redundant predicate: fact_rows -> lookup_dim -> fanout_rows cost = 13672 5. Run EXPLAIN ANALYZE three times for each query and compare the median execution time. Observed on MySQL 9.7.1: Original: 464.806 ms 462.017 ms 471.860 ms median = 464.806 ms Equivalent predicate: 3.890 ms 3.332 ms 5.741 ms median = 3.890 ms Redundant predicate: 3.546 ms 3.731 ms 5.916 ms median = 3.731 ms The equivalent-predicate plan is about 119.5x faster. The redundant-predicate plan is about 124.6x faster. Attached files: mysql_join_equality_range_predicate_repro.sql: complete self-contained reproduction script, including database/table creation, test data, indexes, ANALYZE TABLE, correctness checks, EXPLAIN, and three EXPLAIN ANALYZE runs for each query. mysql_join_equality_range_predicate_repro.txt: complete output produced by running the reproduction script on MySQL 9.7.1. Suggested fix: Please consider making range predicates derived through INNER JOIN equality classes available consistently during join-order enumeration and access-path costing. For example, given: A.x = B.x AND A.x <= constant the optimizer should be able to use the implied predicate: B.x <= constant during the same optimization phase as if B.x <= constant had been written explicitly in the SQL text. In this testcase, MySQL appears to derive the equivalent predicate eventually, because it is visible in the final EXPLAIN output, but the derived predicate does not have the same effect on join-order selection as the explicitly written predicate. It may therefore be useful to ensure that equality-derived range predicates are propagated before, or made directly available to, join-order enumeration and cardinality/access-path costing. The propagated predicates should also preferably be deduplicated, since the redundant-predicate query currently shows the same range condition twice in the final plan.