pingcap / pingcap/tidb

planner: index join inner side supports an embedded inner join, but that join cannot itself be an index join (second table still full-scanned)

Open
#70,558 0 comments 0 reactions 0 assignees View on GitHub
contribution type/enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.