Description:
This is a performance issue in equality-equivalent join predicate handling.
The attached testcase creates three InnoDB tables with 6000 rows each. The final query returns 10 rows.
The following four predicate forms are logically equivalent in this testcase and return the same 10 rows with the same checksum:
1. Equality form:
t3.c0 = t1.c1
AND t3.c1 = t2.c1
2. BETWEEN-equivalent form:
t3.c0 BETWEEN t1.c1 AND t1.c1
AND t3.c1 BETWEEN t2.c1 AND t2.c1
3. >= and <= equivalent form:
t3.c0 >= t1.c1 AND t3.c0 <= t1.c1
AND t3.c1 >= t2.c1 AND t3.c1 <= t2.c1
4. NOT <> equivalent control form:
NOT (t3.c0 <> t1.c1)
AND NOT (t3.c1 <> t2.c1)
With optimizer_switch='hypergraph_optimizer=on', the equality form uses normal hash equi-joins:
Inner hash join (t3.c1 = t2.c1)
-> Inner hash join (t3.c0 = t1.c1)
It returns 10 rows in about 11 ms on my machine.
However, the logically equivalent BETWEEN form is not extracted as an equi-join condition. The hypergraph optimizer produces no-condition hash joins with extra conditions:
Inner hash join (no condition), extra conditions: (t3.c0 between t1.c1 and t1.c1)
-> Inner hash join (no condition), extra conditions: (t3.c1 between t2.c1 and t2.c1)
It returns the same 10 rows, but takes about 1084 ms on my machine, about 100x slower than the equality form.
The equivalent >= and <= form has the same issue and takes about 2109 ms.
As a control, the NOT <> equivalent form is simplified back to normal hash equi-joins and runs in about 11.2 ms. This suggests that the optimizer can recognize some equality-equivalent predicates, but does not extract equi-join keys from BETWEEN x AND x or from the equivalent x >= y AND x <= y range form.
The legacy optimizer shows the same predicate-normalization issue as well: equality takes about 19 ms, BETWEEN takes about 3493 ms, >=/<= takes about 21325 ms, and the NOT <> control takes about 22.6 ms.
The expected behavior is that x BETWEEN y AND y should be recognized as equality-equivalent to x = y for join planning, when SQL NULL semantics and type/collation rules are preserved. This would allow the optimizer to extract equi-join keys and use normal hash join conditions instead of evaluating Cartesian-like no-condition hash joins with extra conditions.
How to repeat:
1. Save the attached SQL file as:
mysql_hg_between_nonempty_bug_full_matrix.sql
2. Run it as follows:
mysql -h 127.0.0.1 -P 3306 -u root --comments --table \
< mysql_hg_between_nonempty_bug_full_matrix.sql \
> mysql_hg_between_nonempty_bug_full_matrix_result.txt 2>&1
3. The script creates a database named:
mysql_hg_between_nonempty
It creates three InnoDB tables, inserts 6000 rows into each table, creates indexes, runs ANALYZE TABLE, and then compares equality-equivalent join predicate forms under both the legacy optimizer and the hypergraph optimizer.
4. Observe the result-equivalence section. All forms return the same 10 rows and checksum:
EQUALITY_FORM: result_rows = 10, checksum = 40000110
BETWEEN_EQUIV: result_rows = 10, checksum = 40000110
GE_LE_EQUIV: result_rows = 10, checksum = 40000110
NOT_NE_EQUIV: result_rows = 10, checksum = 40000110
5. Observe the hypergraph equality form. It uses normal hash equi-joins:
-> Inner hash join (t3.c1 = t2.c1)
-> Inner hash join (t3.c0 = t1.c1)
On my machine it returns 10 rows in about 11 ms.
6. Observe the hypergraph BETWEEN-equivalent form. It uses no-condition hash joins with extra conditions:
-> Inner hash join (no condition), extra conditions: (t3.c0 between t1.c1 and t1.c1)
-> Inner hash join (no condition), extra conditions: (t3.c1 between t2.c1 and t2.c1)
On my machine it returns the same 10 rows, but takes about 1084 ms.
7. Observe the hypergraph >= and <= equivalent form. It also uses no-condition hash joins with extra conditions and takes about 2109 ms.
8. Observe the hypergraph NOT <> equivalent control form. It is simplified back to normal hash equi-joins and runs in about 11.2 ms.
9. The legacy optimizer also shows the same predicate-normalization issue: equality and NOT <> are around 19-23 ms, while BETWEEN is about 3493 ms and >=/<= is about 21325 ms.
Suggested fix:
Consider normalizing equality-equivalent range predicates into equi-join conditions before or during join planning.
In particular, predicates of the form:
x BETWEEN y AND y
are equality-equivalent to:
x = y
for this testcase. Similarly:
x >= y AND x <= y
is equality-equivalent to x = y, assuming SQL NULL semantics and type/collation rules are preserved.
When such predicates compare columns from different tables, the optimizer should be able to extract them as equi-join keys, so that the hypergraph optimizer can build normal hash equi-joins instead of no-condition hash joins with extra conditions.
The testcase shows that NOT(x <> y) is already simplified back to a normal equality hash join. Extending similar equality extraction to BETWEEN x AND x and >=/<= forms would avoid the observed 100x slowdown.
Description: This is a performance issue in equality-equivalent join predicate handling. The attached testcase creates three InnoDB tables with 6000 rows each. The final query returns 10 rows. The following four predicate forms are logically equivalent in this testcase and return the same 10 rows with the same checksum: 1. Equality form: t3.c0 = t1.c1 AND t3.c1 = t2.c1 2. BETWEEN-equivalent form: t3.c0 BETWEEN t1.c1 AND t1.c1 AND t3.c1 BETWEEN t2.c1 AND t2.c1 3. >= and <= equivalent form: t3.c0 >= t1.c1 AND t3.c0 <= t1.c1 AND t3.c1 >= t2.c1 AND t3.c1 <= t2.c1 4. NOT <> equivalent control form: NOT (t3.c0 <> t1.c1) AND NOT (t3.c1 <> t2.c1) With optimizer_switch='hypergraph_optimizer=on', the equality form uses normal hash equi-joins: Inner hash join (t3.c1 = t2.c1) -> Inner hash join (t3.c0 = t1.c1) It returns 10 rows in about 11 ms on my machine. However, the logically equivalent BETWEEN form is not extracted as an equi-join condition. The hypergraph optimizer produces no-condition hash joins with extra conditions: Inner hash join (no condition), extra conditions: (t3.c0 between t1.c1 and t1.c1) -> Inner hash join (no condition), extra conditions: (t3.c1 between t2.c1 and t2.c1) It returns the same 10 rows, but takes about 1084 ms on my machine, about 100x slower than the equality form. The equivalent >= and <= form has the same issue and takes about 2109 ms. As a control, the NOT <> equivalent form is simplified back to normal hash equi-joins and runs in about 11.2 ms. This suggests that the optimizer can recognize some equality-equivalent predicates, but does not extract equi-join keys from BETWEEN x AND x or from the equivalent x >= y AND x <= y range form. The legacy optimizer shows the same predicate-normalization issue as well: equality takes about 19 ms, BETWEEN takes about 3493 ms, >=/<= takes about 21325 ms, and the NOT <> control takes about 22.6 ms. The expected behavior is that x BETWEEN y AND y should be recognized as equality-equivalent to x = y for join planning, when SQL NULL semantics and type/collation rules are preserved. This would allow the optimizer to extract equi-join keys and use normal hash join conditions instead of evaluating Cartesian-like no-condition hash joins with extra conditions. How to repeat: 1. Save the attached SQL file as: mysql_hg_between_nonempty_bug_full_matrix.sql 2. Run it as follows: mysql -h 127.0.0.1 -P 3306 -u root --comments --table \ < mysql_hg_between_nonempty_bug_full_matrix.sql \ > mysql_hg_between_nonempty_bug_full_matrix_result.txt 2>&1 3. The script creates a database named: mysql_hg_between_nonempty It creates three InnoDB tables, inserts 6000 rows into each table, creates indexes, runs ANALYZE TABLE, and then compares equality-equivalent join predicate forms under both the legacy optimizer and the hypergraph optimizer. 4. Observe the result-equivalence section. All forms return the same 10 rows and checksum: EQUALITY_FORM: result_rows = 10, checksum = 40000110 BETWEEN_EQUIV: result_rows = 10, checksum = 40000110 GE_LE_EQUIV: result_rows = 10, checksum = 40000110 NOT_NE_EQUIV: result_rows = 10, checksum = 40000110 5. Observe the hypergraph equality form. It uses normal hash equi-joins: -> Inner hash join (t3.c1 = t2.c1) -> Inner hash join (t3.c0 = t1.c1) On my machine it returns 10 rows in about 11 ms. 6. Observe the hypergraph BETWEEN-equivalent form. It uses no-condition hash joins with extra conditions: -> Inner hash join (no condition), extra conditions: (t3.c0 between t1.c1 and t1.c1) -> Inner hash join (no condition), extra conditions: (t3.c1 between t2.c1 and t2.c1) On my machine it returns the same 10 rows, but takes about 1084 ms. 7. Observe the hypergraph >= and <= equivalent form. It also uses no-condition hash joins with extra conditions and takes about 2109 ms. 8. Observe the hypergraph NOT <> equivalent control form. It is simplified back to normal hash equi-joins and runs in about 11.2 ms. 9. The legacy optimizer also shows the same predicate-normalization issue: equality and NOT <> are around 19-23 ms, while BETWEEN is about 3493 ms and >=/<= is about 21325 ms. Suggested fix: Consider normalizing equality-equivalent range predicates into equi-join conditions before or during join planning. In particular, predicates of the form: x BETWEEN y AND y are equality-equivalent to: x = y for this testcase. Similarly: x >= y AND x <= y is equality-equivalent to x = y, assuming SQL NULL semantics and type/collation rules are preserved. When such predicates compare columns from different tables, the optimizer should be able to extract them as equi-join keys, so that the hypergraph optimizer can build normal hash equi-joins instead of no-condition hash joins with extra conditions. The testcase shows that NOT(x <> y) is already simplified back to a normal equality hash join. Extending similar equality extraction to BETWEEN x AND x and >=/<= forms would avoid the observed 100x slowdown.