planner: ORDER BY on an equivalent join key misses LIMIT early stop and causes a ~120x slowdown

[ZhaoyungZhang]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduce step (Required)

tidb_order_by_equivalent_join_key_limit_early_stop_repro.sql

tidb_order_by_equivalent_join_key_limit_early_stop_repro_result.txt

Run the attached reproduction file:

tidb_order_by_equivalent_join_key_limit_early_stop_repro.sql

For example:

mysql -h 127.0.0.1 -P 4000 -u root \
  < tidb_order_by_equivalent_join_key_limit_early_stop_repro.sql

The script creates the following data shape:

t0 rows:                  48,000
t1 rows:                  72,000
distinct join keys:        4,000
rows after the join:     859,680

The relevant indexes are:

KEY idx_t0_probe (c0, c4, c1)
KEY idx_t1_order (c0, c3, c2, c1)

The tables are joined using the following equality condition:

t1.c0 = t0.c0

Therefore, for every row produced by the inner join, the following two orderings are equivalent:

ORDER BY t0.c0 ASC, t1.c3 ASC

ORDER BY t1.c0 ASC, t1.c3 ASC

The original query is:

SELECT t1.c2 AS ref0
FROM t1
INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 ASC
LIMIT 3;

The equivalent rewrite is:

SELECT t1.c2 AS ref0
FROM t1
INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 ASC
LIMIT 3;

Run both queries three times using EXPLAIN ANALYZE and compare their median execution times.

The reproduction file also compares the two queries while forcing the same join order, join algorithm, and indexes.

Original ordering:

SELECT /*+ LEADING(t1, t0)
           INL_JOIN(t0)
           USE_INDEX(t1, idx_t1_order)
           USE_INDEX(t0, idx_t0_probe) */
       t1.c2 AS ref0
FROM t1
INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 ASC
LIMIT 3;

Equivalent rewritten ordering:

SELECT /*+ LEADING(t1, t0)
           INL_JOIN(t0)
           USE_INDEX(t1, idx_t1_order)
           USE_INDEX(t0, idx_t0_probe) */
       t1.c2 AS ref0
FROM t1
INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 ASC
LIMIT 3;

The following validation confirms that the join keys are equal for every joined row:

equality_violations = 0

The script also compares deterministic Top 300 results.

Ascending-order result validation:

original_rows       = 300
rewritten_rows      = 300
original_checksum   = 644303268053
rewritten_checksum  = 644303268053

Mixed-direction result validation:

original_rows       = 300
rewritten_rows      = 300
original_checksum   = 646514305003
rewritten_checksum  = 646514305003

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

Because the inner join condition establishes:

t0.c0 = t1.c0

TiDB should treat t0.c0 and t1.c0 as equivalent when deriving the required ordering property.

Consequently:

ORDER BY t0.c0 ASC, t1.c3 ASC

should be recognized as equivalent to:

ORDER BY t1.c0 ASC, t1.c3 ASC

for this inner join.

The optimizer should be able to use the ordered scan provided by:

idx_t1_order (c0, c3, c2, c1)

as the outer side of an index join and stop execution after the parent LIMIT 3 receives enough rows.

The optimizer does not have to choose exactly the same physical operator for both queries. However, replacing an ordering expression with an equal join column should not determine whether TiDB must produce all 859,680 join rows.

In the forced-plan comparison, both queries use the same join order, join algorithm, and indexes. Both forms should therefore preserve the same ordering property and support the same LIMIT early-stop behavior.

3. What did you see instead (Required)

TiDB does not propagate the required ordering property through the join equality when the first ordering expression is written as t0.c0.

Default-plan comparison

For the original query:

ORDER BY t0.c0 ASC, t1.c3 ASC
LIMIT 3

TiDB chooses:

TopN
└─ MergeJoin

The MergeJoin produces all 859,680 joined rows before TopN returns three rows.

Three executions:

236.3 ms
 71.6 ms
 69.6 ms

Median execution time:

71.6 ms

For the equivalent rewrite:

ORDER BY t1.c0 ASC, t1.c3 ASC
LIMIT 3

TiDB chooses:

Limit
└─ IndexHashJoin
   ├─ ordered scan of idx_t1_order
   └─ index range scan of idx_t0_probe

Three executions:

1.1800 ms
1.0600 ms
0.9879 ms

Median execution time:

1.06 ms

The median runtime difference is approximately:

71.6 / 1.06 = 67.5x

The rewritten query reads only a small prefix of the ordered outer input and probes 12 rows from t0. The original query produces all 859,680 join rows.

Same join order, join algorithm, and indexes

The stronger comparison forces both queries to use:

LEADING(t1, t0)
INL_JOIN(t0)
USE_INDEX(t1, idx_t1_order)
USE_INDEX(t0, idx_t0_probe)

For the original ordering:

ORDER BY t0.c0 ASC, t1.c3 ASC
LIMIT 3

the plan is:

TopN
└─ IndexJoin

The IndexJoin produces all 859,680 joined rows.

Three executions:

136.1 ms
121.4 ms
121.7 ms

Median execution time:

121.7 ms

For the equivalent rewritten ordering:

ORDER BY t1.c0 ASC, t1.c3 ASC
LIMIT 3

the plan is:

Limit
└─ IndexJoin

The IndexJoin stops after producing three rows.

Three executions:

1.45 ms
0.97 ms
1.01 ms

Median execution time:

1.01 ms

The median runtime difference is approximately:

121.7 / 1.01 = 120.5x

This comparison uses the same join order, the same join algorithm, and the same indexes. The material difference is whether the first ORDER BY expression is written as t0.c0 or as the equal join key t1.c0.

Supplementary mixed-direction comparison

The reproduction file also compares:

ORDER BY t0.c0 ASC, t1.c3 DESC

with:

ORDER BY t1.c0 ASC, t1.c3 DESC

Both queries use TopN above a MergeJoin, and both produce all 859,680 joined rows.

Median execution times:

original mixed-direction ordering:   71.7 ms
rewritten mixed-direction ordering:  83.0 ms

This supplementary comparison is affected by the mixed ordering directions and is not the primary performance oracle.

The ascending ordered-index comparison directly demonstrates that TiDB misses equality-based ordering-property propagation and therefore fails to use LIMIT early termination.

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

Additional relevant session variables:

tidb_cost_model_version      = 2
tidb_opt_advanced_join_hint  = ON
tidb_isolation_read_engines  = tikv

[kennedy8312]

/sig planner
/severity moderate

[kennedy8312]

tidb-triage-bot AI rationale

• severity/moderate: This is a planner performance issue where missed ordering-property propagation prevents LIMIT early stop and causes a large slowdown without correctness or availability impact.
• sig/planner: The issue concerns optimizer ordering-property propagation across equivalent join keys and plan selection for LIMIT pushdown.