planner: NOT (x <> y) is not normalized to an equi-join key, causing a Cartesian join and about 247x slowdown

[ZhaoyungZhang]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduce step (Required)

Run the attached reproduction script:

tidb_not_ne_join_predicate_repro.sql

tidb_not_ne_join_predicate_repro_result.txt

The script creates and analyzes three tables with 6,000 rows each.

The data is constructed so that:

• t3.c0 = t1.c1 produces 6,000 rows.
• t3.c1 = t2.c1 produces 10 rows.
• The final three-table join produces 10 rows.

It then compares the following two logically equivalent queries.

Equality reference:

SELECT t1.c1 AS ref0, t2.c1 AS ref1
FROM t3
INNER JOIN t1 ON t3.c0 = t1.c1
INNER JOIN t2 ON t3.c1 = t2.c1
WHERE t2.c1 <= 1596112929;

NOT (<>) form:

SELECT t1.c1 AS ref0, t2.c1 AS ref1
FROM t3
INNER JOIN t1 ON t3.c0 = t1.c1
INNER JOIN t2 ON NOT (t3.c1 <> t2.c1)
WHERE t2.c1 <= 1596112929;

The two join predicates are equivalent under SQL three-valued logic:

NOT (x <> y)

and:

x = y

Both queries return the same result:

+--------------------+-------------+----------+
| variant            | result_rows | checksum |
+--------------------+-------------+----------+
| EQUALITY_REFERENCE |          10 | 40000110 |
| NOT_NE_TEST        |          10 | 40000110 |
+--------------------+-------------+----------+

All three tables are analyzed before the queries are executed:

+------------+--------------+-----------+
| Table_name | Modify_count | Row_count |
+------------+--------------+-----------+
| t1         |            0 |      6000 |
| t2         |            0 |      6000 |
| t3         |            0 |      6000 |
+------------+--------------+-----------+

2. What did you expect to see? (Required)

TiDB should recognize:

NOT (t3.c1 <> t2.c1)

as an equality-equivalent join predicate and extract it as an equi-join key, in the same way as:

t3.c1 = t2.c1

The resulting plan does not have to be identical, but it should avoid a Cartesian join and should have performance comparable to the equality form.

For example, the condition should be represented as an equality condition similar to:

equal:[eq(tidb_not_ne_join_repro.t2.c1,
          tidb_not_ne_join_repro.t3.c1)]

3. What did you see instead (Required)

For the equality reference, TiDB correctly extracts both equality predicates as equi-join keys:

HashJoin
inner join,
equal:[eq(tidb_not_ne_join_repro.t3.c0,
          tidb_not_ne_join_repro.t1.c1)]

HashJoin
inner join,
equal:[eq(tidb_not_ne_join_repro.t2.c1,
          tidb_not_ne_join_repro.t3.c1)]

The equality reference returned 10 rows with the following execution times:

run 1: 13.1 ms
run 2:  7.5 ms
run 3:  7.3 ms
median: 7.5 ms

However, TiDB does not extract the NOT (<>) predicate as an equi-join key.

Instead, it produces a Cartesian Hash Join and evaluates the predicate as a residual condition:

HashJoin
CARTESIAN inner join,
other cond:not(ne(tidb_not_ne_join_repro.t3.c1,
                  tidb_not_ne_join_repro.t2.c1))

The unchanged equality join between t3 and t1 remains a normal non-Cartesian join:

MergeJoin
inner join,
left key:tidb_not_ne_join_repro.t3.c0,
right key:tidb_not_ne_join_repro.t1.c1

This isolates the Cartesian join to the failure to normalize:

NOT (t3.c1 <> t2.c1)

The Cartesian Hash Join is estimated to return 11,964,000 rows, although the actual result contains only 10 rows:

estRows: 11964000.00
actRows: 10

The NOT (<>) query returned the same result but required:

run 1: 2.06 s
run 2: 1.85 s
run 3: 1.83 s
median: 1.85 s

The median runtime is therefore approximately:

1.85 s / 7.5 ms = 246.7x

slower than the logically equivalent equality form.

This appears to be a missing predicate-normalization rule rather than a join-algorithm selection problem. Because NOT (x <> y) is not converted into an equality expression before join-condition extraction, TiDB treats it as a general residual condition and cannot construct an equi-join key.

Suggested fix direction

Normalize equality-equivalent expressions of the form:

NOT (x <> y)

into:

x = y

before extracting join equality conditions.

The normalized expression should be added to the join's equality-condition list so that Hash Join, Merge Join, or Index Join can use it as a join key instead of executing a Cartesian join with a residual filter.

A regression test should cover both non-NULL and NULL inputs to verify that the rewrite preserves SQL three-valued semantics.

4. What is your TiDB version? (Required)

Release Version: v8.5.7
Edition: Community
Git Commit Hash: 202b7f47286a1109b5c957401d34c9358d130ae0
Git Branch: HEAD
UTC Build Time: 2026-07-15 02:06:00
GoVersion: go1.25.10
Race Enabled: false
Check Table Before Drop: false
Store: tikv

Relevant optimizer settings:

tidb_opt_enable_hash_join = ON
tidb_hash_join_version = legacy
tidb_cost_model_version = 2

[kennedy8312]

/sig planner
/severity moderate

[kennedy8312]

tidb-triage-bot AI rationale

• severity/moderate: The issue is a planner normalization gap causing a much slower Cartesian join without reported correctness or availability impact.
• sig/planner: The bug concerns optimizer predicate normalization and equi-join key extraction for NOT inequality expressions.