planner: the optimizer can't produce an optimal plan for queries with sub-queries in select list
- 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
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