planner: index join inner side supports an embedded inner join, but that join cannot itself be an index join (second table still full-scanned)
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
### Summary
https://github.com/pingcap/tidb/pull/66156 -> let an index join's inner side *contain* an inner join. But that embedded join is still restricted to a hash join, so only **one** level of parameterization happens: the first table inside the nest gets an index range, the second is full-scanned.
Related: #65781 (unify index join inner executor build) — the `dataReaderBuilder` duplication described there is the same machinery that would need to support re-parameterization.
### Minimal reproduction
No data and no statistics required — three empty tables (master @ 65c2a6c):
CREATE TABLE am(user_id varchar(36), account_id varchar(36), KEY(user_id, account_id));
CREATE TABLE c (account_id varchar(36), source_id varchar(64), updated datetime, KEY(account_id));
CREATE TABLE p (source_id varchar(64), name varchar(64), UNIQUE KEY(source_id));
EXPLAIN FORMAT='brief'
SELECT am.account_id, c.updated, p.name
FROM c INNER JOIN p ON p.source_id = c.source_id
RIGHT JOIN am ON c.account_id = am.account_id
WHERE am.user_id = 'x' ORDER BY c.updated DESC LIMIT 100;
ACTUAL — master 65c2a6c
```sql
CREATE TABLE am(user_id varchar(36), account_id varchar(36), KEY(user_id, account_id));
CREATE TABLE c (account_id varchar(36), source_id varchar(64), updated datetime, KEY(account_id));
CREATE TABLE p (source_id varchar(64), name varchar(64), UNIQUE KEY(source_id));
EXPLAIN FORMAT='brief'
SELECT am.account_id, c.updated, p.name
FROM c INNER JOIN p ON p.source_id = c.source_id
RIGHT JOIN am ON c.account_id = am.account_id
WHERE am.user_id = 'x' ORDER BY c.updated DESC LIMIT 100;
```
**Actual (master):**
```
Projection 15.62 root
└─TopN 15.62 root
└─IndexHashJoin 15.62 root
├─IndexReader(Build) 10.00 root table:am, index:user_id
└─HashJoin(Probe) 124750.12 root <-- hash join, and...
├─IndexLookUp(Build) 15.62 root table:c, index:account_id
└─TableReader(Probe) 99900.00 root
└─TableFullScan 100000.00 cop table:p <-- ...p full-scanned
```
`p.source_id` has a UNIQUE index and is the join key, but it is never used.
**Expected** (what MySQL 8.0 / Aurora produces for the same query — a 3-table
`nested_loop`, every table `access_type: ref`):
```
└─IndexHashJoin 15.62 root
├─IndexReader(Build) 10.00 root table:am, index:user_id
└─IndexJoin(Probe) 15.62 root
├─IndexLookUp(Build) 15.62 root table:c, index:account_id
└─IndexLookUp(Probe) 15.62 root table:p, index:source_id
```
Expetcted on TIDB:
```
id estRows task access object
Projection 15.62 root
└─TopN 15.62 root
└─IndexHashJoin 15.62 root
├─IndexReader(Build) 10.00 root
│ └─IndexRangeScan 10.00 cop[tikv] table:am, index:user_id(user_id, account_id)
└─IndexJoin(Probe) 15.62 root
├─IndexLookUp(Build) 15.62 root
│ ├─Selection(Build) 15.64 cop[tikv]
│ │ └─IndexRangeScan 15.66 cop[tikv] table:c, index:account_id(account_id)
│ └─Selection(Probe) 15.62 cop[tikv]
│ └─TableRowIDScan 15.64 cop[tikv] table:c
└─IndexLookUp(Probe) 15.62 root
├─Selection(Build) 15.62 cop[tikv]
│ └─IndexRangeScan 15.62 cop[tikv] table:p, index:source_id(source_id)
└─TableRowIDScan(Probe) 15.62 cop[tikv] table:p
```
### Proposed change
Allow a `LogicalJoin` carrying an `IndexJoinProp` to enumerate index joins where the prop-consuming child becomes the outer side and the sibling receives a newly constructed `IndexJoinRuntimeProp` built from that join's own `EqualConditions`. `property.IndexJoinRuntimeProp` already carries every needed field.
Contributor guide
Research direction
Start with the LogicalJoin, IndexJoinProp, and IndexJoinRuntimeProp machinery described in the issue, then run the three-table EXPLAIN reproduction. Trace how the prop-consuming child and sibling are enumerated and re-parameterized. Done means the plan uses a nested IndexJoin for p with its source_id index instead of a hash join and full scan.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100