planner: DISTINCT equality join expands duplicate matches instead of using an available Merge Semi Join

[ZhaoyungZhang]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduce step (Required)

tidb_distinct_equality_semijoin_repro.sql

tidb_distinct_equality_semijoin_repro_result.txt

Run the attached reproduction script:

mysql -h 127.0.0.1 -P 4000 -u root --comments --table \
  < tidb_distinct_equality_semijoin_repro.sql \
  > tidb_distinct_equality_semijoin_repro_result.txt 2>&1

The script creates and analyzes three tables:

t0:  90 rows,  8 distinct c0 values
t1: 203 rows, 32 distinct c0 values
t3: 117 rows,  8 distinct c0 values

The query being tested is:

SELECT DISTINCT
       t0.c1 AS ref0,
       t3.c1 AS t3_c1,
       t0.c0 AS t0_c0
FROM t3
JOIN t0 ON t3.c0 = t0.c0
JOIN t1 ON t1.c0 = t0.c0
ORDER BY t0.c0
LIMIT 8;

t1 does not contribute any projected column, DISTINCT key, or ordering expression. It only determines whether the current t0.c0 value has at least one matching row.

The logically equivalent existence form is:

SELECT DISTINCT
       t0.c1 AS ref0,
       t3.c1 AS t3_c1,
       t0.c0 AS t0_c0
FROM t3
JOIN t0 ON t3.c0 = t0.c0
WHERE EXISTS (
    SELECT 1
    FROM t1
    WHERE t1.c0 = t0.c0
)
ORDER BY t0.c0
LIMIT 8;

The script verifies exact result equivalence:

inner_rows         = 7
exists_rows        = 7
inner_minus_exists = 0
exists_minus_inner = 0

For the base data, the relevant cardinalities are:

ordinary inner-join rows                 = 20,223
t0/t3 rows having at least one t1 match  = 1,137
final DISTINCT rows                      = 7

The script also creates t1_amplified by copying every t1 row 32 times:

base t1 rows       = 203
amplification      = 32
t1_amplified rows  = 6,496
distinct c0 values = 32

This amplification changes only the number of duplicate matches. It does not change whether a given t0.c0 value has a match, and it does not change the final DISTINCT result.

For the amplified data:

ordinary inner-join rows = 647,136
final DISTINCT rows      = 7

The complete SQL script and execution result are attached.

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

Because t1 contributes no observable output value, additional t1 rows matching the same t0.c0 value cannot produce a new final DISTINCT row.

For each row produced by t3 JOIN t0, the required semantics with respect to t1 are only:

check whether at least one t1 row has t1.c0 = t0.c0
stop after the first match

I expected the optimizer to consider a duplicate-aware transformation equivalent to:

DISTINCT over columns from t0 and t3
+
inner equality join to duplicate-only t1
→
semijoin / FirstMatch against t1

The explicit EXISTS form demonstrates that TiDB already has a suitable physical plan for this equality predicate:

TopN
└─HashAgg
  └─MergeJoin semi join

Therefore, the original inner-join query should be able to use the same or another equivalent duplicate-eliminating strategy, such as:

Merge Semi Join

or:

deduplicate t1.c0
→
join the distinct t1 keys with t0/t3

or an index-based FirstMatch plan that stops after the first matching t1 row.

The optimizer does not need to produce one specific physical plan. Any equivalent strategy that avoids sending every duplicate t1 match to the upper HashAgg would be sufficient.

3. What did you see instead (Required)

Base data

The original inner-join query uses ordinary MergeJoins:

TopN                                      actRows = 7
└─HashAgg                                 actRows = 7
  └─Projection                            actRows = 20,223
    └─MergeJoin inner join                actRows = 20,223

All 20,223 matching join rows are materialized before HashAgg reduces them to 7 distinct rows.

Three runs of the original query:

2.79 ms
3.39 ms
2.99 ms

Median runtime:

2.99 ms

The equivalent EXISTS query is recognized as a semi join:

TopN                                      actRows = 7
└─HashAgg                                 actRows = 7
  └─MergeJoin semi join                   actRows = 1,137

Three runs of the equivalent EXISTS query:

1.70 ms
1.60 ms
1.50 ms

Median runtime:

1.60 ms

The original query is approximately:

2.99 ms / 1.60 ms = 1.87x slower

Even on the small base data, the ordinary inner join sends approximately:

20,223 / 1,137 = 17.8x

more rows to the duplicate-elimination stage than the semi join.

Duplicate amplification

After copying each t1 row 32 times, the original inner-join query produces:

MergeJoin actRows = 647,136
HashAgg actRows   = 7

Three runs:

74.9 ms
73.5 ms
73.9 ms

Median runtime:

73.9 ms

The equivalent amplified EXISTS query still uses a Merge Semi Join and emits only:

MergeJoin semi join actRows = 1,137
HashAgg actRows             = 7

Three runs:

5.73 ms
6.06 ms
5.41 ms

Median runtime:

5.73 ms

The original amplified query is approximately:

73.9 ms / 5.73 ms = 12.9x slower

The ordinary join output grows exactly with the duplicate amplification factor:

20,223 × 32 = 647,136

However, neither the existence condition nor the final DISTINCT result changes.

This shows that the runtime is scaling with duplicate match multiplicity that is not observable in the final result.

The issue is not limited to ORDER BY or LIMIT

The script also executes the same two logical forms without ORDER BY and LIMIT.

Plain DISTINCT with the ordinary inner join:

HashAgg actRows   = 7
MergeJoin actRows = 20,223
runtime           = 3.35 ms

Plain DISTINCT with the equivalent semi join:

HashAgg actRows             = 7
MergeJoin semi join actRows = 1,137
runtime                     = 1.61 ms

Therefore, this is not only a TopN costing or ordered early-termination issue.

The missing optimization is more generally:

DISTINCT
+
predicate-connected equality-join input that contributes no output columns
+
multiple matches that only create removable duplicates
→
semijoin / FirstMatch

Relation to #69918

This issue is related at a high level to #69918, because both involve duplicate-only join matches below DISTINCT.

However, this reproducer isolates a different and narrower planner path.

In #69918:

• the join condition is a correlated non-equality predicate;
• the explicit EXISTS rewrite still uses a Cartesian Hash Semi Join;
• and an additional problem is that TiDB does not generate an efficient parameterized dynamic index range for the correlated predicate.

In this issue:

• every join condition is a simple equality predicate;
• indexes exist on the equality keys;
• the explicit EXISTS rewrite already produces an efficient MergeJoin semi join;
• there is no dynamic range, residual inequality, or repeated correlated index-range problem;
• and the efficient physical semi-join plan is already available.

This reproducer therefore specifically isolates the failure to derive or consider the available equality semijoin from an ordinary multi-table inner join under DISTINCT.

Impact

The unnecessary intermediate work grows with:

number of t0/t3 rows
×
number of duplicate t1 matches per join key

Increasing only the duplicate multiplicity of t1 from the base data to 32 copies increases the ordinary query runtime from approximately 3 ms to approximately 74 ms, while the final result remains unchanged.

For larger inputs or more heavily duplicated join keys, this can cause:

• unnecessary CPU consumption;
• increased aggregation work;
• larger intermediate result processing;
• higher query latency;
• resource contention;
• and query timeouts.

The current workaround is to manually rewrite the duplicate-only inner join as an EXISTS predicate.

Suggested fix direction

Consider adding a logical transformation for DISTINCT and equivalent duplicate-insensitive aggregation plans.

When:

• an inner-join input contributes no projected column;
• it contributes no DISTINCT, grouping, ordering, or other observable value;
• its only role is to determine whether a matching row exists;
• and multiple matches can only produce duplicates removed by the upper operator;

the optimizer could replace the ordinary inner join with a semijoin or FirstMatch-equivalent operation.

For equality predicates, TiDB could reuse the same Merge Semi Join candidate that is already generated for the explicit EXISTS form, or deduplicate the inner equality keys before joining.

The transformation must preserve no-match semantics: a t0/t3 row must not appear if no matching t1 row exists.

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

[kennedy8312]

/sig planner
/severity moderate

[kennedy8312]

tidb-triage-bot AI rationale

• severity/moderate: The issue is a planner optimization miss that causes duplicate-driven runtime growth without correctness or availability impact.
• sig/planner: The bug concerns optimizer planning for DISTINCT inner joins versus an available equality semi-join plan.