planner: correlated Apply alternative can beat MPP hash join due to underestimated lookup fanout
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Bug Report
Please answer these questions before submitting your issue. Thanks!
### 1. Minimal reproduce step (Required)
This report is based on an anonymized production diagnostic case. Table names, tenant IDs, object type IDs, and literal values are sanitized.
The affected query shape is a `TopN + EXISTS` query over a large object table and a large relationship table:
```sql
SELECT o.sequential_id, o.label
FROM obj_large AS o
WHERE o.tenant_id = 'tenant_x'
AND o.obj_type_id IN (x'type_a', x'type_b', x'type_c', x'type_d', x'type_e')
AND o.text_attr_24 = 'value_a'
AND EXISTS (
SELECT 1
FROM rel_large AS r
JOIN obj_large AS o1
ON r.referenced_object_id = o1.id
AND o1.obj_type_id IN (x'type_a', x'type_b', x'type_c', x'type_d', x'type_e')
WHERE r.tenant_id = 'tenant_x'
AND o.id = r.object_id
AND o1.tenant_id = 'tenant_x'
AND EXISTS (
SELECT 1
FROM rel_large AS r1
JOIN obj_large AS o2
ON r1.object_id = o2.id
AND o2.obj_type_id IN (x'type_a', x'type_b', x'type_c', x'type_d', x'type_e')
WHERE r1.tenant_id = 'tenant_x'
AND o1.id = r1.referenced_object_id
AND o2.tenant_id = 'tenant_x'
AND (o2.text_attr_8 = 'value_b' OR o2.text_attr_8 = 'value_c')
)
)
ORDER BY o.label
LIMIT 1000;
```
Tables are large enough that the relationship table has tens of millions of rows. The object table has predicates on tenant ID, object type, and text attributes. The relationship table has indexes that allow correlated index lookup by `(tenant_id, object_id, referenced_object_id, ...)` or `(tenant_id, referenced_object_id, ...)`.
**In the alternative logical plan framework, an MPP hash-join plan is available, but the correlated Apply alternative wins by cost.**
Observed problematic plan shape:
```text
TopN
└─Apply_33 CARTESIAN semi join, cache:OFF
├─TableReader_40(Build) -- outer object side
│ └─Selection / TableRangeScan -- tenant + object type + text_attr_24
└─Apply_46(Probe) CARTESIAN semi join, cache:OFF
├─IndexJoin_51 -- rel_large + obj_large
│ ├─IndexReader / IndexRangeScan -- correlated lookup on rel_large
│ └─TableReader -- lookup object rows
└─IndexJoin_142
├─IndexLookUp_183 -- correlated lookup on rel_large
└─TableReader_187 -- lookup object rows
```
Representative `EXPLAIN ANALYZE` facts from the anonymized case:
```text
TopN_27 time: 30m22s, actRows: 1000
Apply_33 estRows: 1451, actRows: 24033, cache:OFF
TableReader_40(Build) estRows: 1451, actRows: 29948
Apply_46(Probe) time: 30m22s, loops: 53981, cache:OFF
IndexJoin_142 time: 29m04s
IndexLookUp_183 estRows: 1477, actRows: 4,504,102
TableRowIDScan_181 cop_task num: 3,239,283
TableReader_187 estRows: 0.15, actRows: 389,859
TableReader_187 cop_task num: 2,070,722
```
The same logical query with the MPP hash-join alternative completes in about 200-300 ms:
```text
Projection
└─TopN
└─TableReader
└─ExchangeSender
└─TopN
└─HashJoin semi join
├─object filtered side
└─HashJoin / TableRangeScan on relationship table
EXPLAIN ANALYZE wall time: ~231 ms
```
A simpler one-level `EXISTS` query shows the same pattern with smaller blast radius:
```text
TopN_19 time: 60s
Apply_25 estRows: 11963, actRows: 3859, cache:OFF
IndexJoin_41 time: 60s
IndexLookUp_82 estRows: 16457, actRows: 108285
TableReader_86 estRows: 60, actRows: 4737
TableRowIDScan / TableReader cop_task num: tens of thousands
Equivalent MPP hash-join plan: ~209 ms
```
### 2. What did you expect to see? (Required)
The optimizer should not choose a correlated `Apply + IndexJoin + IndexLookUp` alternative when:
- the outer/build side is not tiny,
- the inner side is a relationship-table lookup path with uncertain/high fanout,
- the Apply cache is disabled or ineffective,
- the lookup path requires large numbers of table lookups / cop tasks,
- and an MPP semi-hash-join alternative is available and much cheaper in reality.
Expected behavior:
- Prefer the decorrelated semi-join / MPP hash-join alternative for this query class, or
- make the Apply alternative cost reflect the real execution risk: outer rows × correlated lookup fanout × table lookup amplification × cop/RPC startup cost.
Potential correction points:
1. Add a conservative admission rule or penalty for Join-to-Apply alternatives generated from semi joins when estimated outer rows are above a threshold and the inner side is an IndexJoin/IndexLookUp path.
2. In `PhysicalApply` costing, explicitly account for lookup-heavy inner plans and their per-outer-row RPC/coprocessor startup cost.
3. Do not let `ORDER BY ... LIMIT` / expected row count assumptions make the Apply probe count too optimistic unless the optimizer can prove high semi-join hit rate or early termination.
4. Consider making the `SEMI_JOIN_REWRITE` logical transformation available in the alternative plan framework, so the optimizer can compare native Apply/SemiJoin with a rewritten inner-join + dedup/hash-join plan shape.
### 3. What did you see instead (Required)
The Apply alternative wins the cost comparison even though runtime is much worse than the MPP alternative.
The issue appears to be a multiplicative underestimation:
```text
estimated total probe work
<< actual outer rows
× actual relationship lookup fanout
× table lookup amplification
× cop/RPC task count
```
In the representative two-level `EXISTS` case:
- outer/build side: estimated ~1.4K rows, actual ~30K rows,
- inner relationship lookup: estimated ~1.4K rows, actual ~4.5M rows,
- final object lookup: estimated ~0.15 rows, actual ~390K rows,
- runtime creates millions of small TiKV cop tasks / RPCs,
- total wall time is about 30 minutes,
- the MPP hash-join alternative completes in ~231 ms.
This is not primarily a raw scan-volume problem. The MPP plan may scan many rows, but it does so with batch scan + hash join. The bad Apply plan creates a very large number of small correlated lookup and table-lookup tasks.
### 4. What is your TiDB version? (Required)
Observed on a TiDB v8.5.6 based custom build:
```text
TiDB: pingcap/tidb:v8.5.6-20260528-889c355
TiKV: pingcap/tikv:v8.5.6-20260519-b7d1a0f
TiFlash: pingcap/tiflash:v8.5.6-20260522-23dd10b
```
Suggested labels: `sig/planner`, `planner/performance`, `component/statistics`, `affects-8.5`, `severity/major`.
Contributor guide
Assessment
This issue has not been assessed yet.