pingcap / pingcap/tidb

planner: the optimizer can't produce an optimal plan for queries with sub-queries in select list

Open
#51,225 5 comments 0 reactions 0 assignees View on GitHub
planner/cascades sig/planner type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement
For queries like `select t_small join {subquery} t_big on t_small.c=t_big.c` or `select * from t_small, {subquery} t_big where t_small.c=t_big.c`, TiDB always tries to decorrelate sub-queries (this operator is not cost-based), which might miss some optimization opportunities and lead to sub-optimal plans, and our current `no_decorrelate` hint cannot work for these 2 cases.

A concrete example:
```
create table small_t (id int);
create table big_t (id int, v int, index(id));

explain select * from small_t
left join (
select big_t.id from big_t, (select id, min(v) v from big_t group by id) big_t2
where big_t.id = big_t2.id and big_t.v = big_t2.v
) big_t on small_t.id = big_t.id;
+----------------------------------------+----------+-----------+---------------+---------------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------------------+----------+-----------+---------------+---------------------------------------------------------------------------------------------------------+
| HashJoin_15 | 10000.00 | root | | left outer join, equal:[eq(wdhis.small_t.id, wdhis.big_t.id)] |
| ├─HashJoin_34(Build) | 7992.00 | root | | inner join, equal:[eq(wdhis.big_t.id, wdhis.big_t.id) eq(wdhis.big_t.v, Column#9)] |
| │ ├─Selection_36(Build) | 6393.60 | root | | not(isnull(Column#9)) |
| │ │ └─HashAgg_44 | 7992.00 | root | | group by:wdhis.big_t.id, funcs:min(Column#13)->Column#9, funcs:firstrow(wdhis.big_t.id)->wdhis.big_t.id |
| │ │ └─TableReader_45 | 7992.00 | root | | data:HashAgg_37 |
| │ │ └─HashAgg_37 | 7992.00 | cop[tikv] | | group by:wdhis.big_t.id, funcs:min(wdhis.big_t.v)->Column#13 |
| │ │ └─Selection_43 | 9990.00 | cop[tikv] | | not(isnull(wdhis.big_t.id)) |
| │ │ └─TableFullScan_42 | 10000.00 | cop[tikv] | table:big_t | keep order:false, stats:pseudo |
| │ └─TableReader_62(Probe) | 9980.01 | root | | data:Selection_61 |
| │ └─Selection_61 | 9980.01 | cop[tikv] | | not(isnull(wdhis.big_t.id)), not(isnull(wdhis.big_t.v)) |
| │ └─TableFullScan_60 | 10000.00 | cop[tikv] | table:big_t | keep order:false, stats:pseudo |
| └─TableReader_18(Probe) | 10000.00 | root | | data:TableFullScan_17 |
| └─TableFullScan_17 | 10000.00 | cop[tikv] | table:small_t | keep order:false, stats:pseudo |
+----------------------------------------+----------+-----------+---------------+---------------------------------------------------------------------------------------------------------+
```
Obviously, a better plan should be like this (Oracle has the same plan below):
```
Apply(NestedLoop)
TableFullScan[build] (small_t)
Join[probe] (any join)
IndexRangeScan(big_t, id)
IndexRangeScan(big_t, id)
```
Then we can use the predicate `small_t.id = big_t.id` to avoid FullScan on the `big_t`, and since `small_t` is small, the below plan should be faster than the original plan with 2 FullScan on `big_t`.

The query below has the same problem:
```
explain select * from small_t, (select /*+ no_decorrelate() */ big_t.id from big_t, (select id, min(v) v from big_t group by id) big_t2
where big_t.id = big_t2.id and big_t.v = big_t2.v) big_t where small_t.id = big_t.id;
```

Contributor guide

Open the contributing guide

Research direction

Reproduce the two EXPLAIN examples and start by tracing TiDB's subquery decorrelation and no_decorrelate hint handling for subqueries in the FROM clause. Compare the resulting plans with the requested Apply(NestedLoop) shape and index range scans. Done means both query forms can preserve the outer predicate and produce the better plan without breaking existing decorrelation behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.