tidb
tidb copied to clipboard
Published
20 hours ago •
pingcap
pingcap
planner: the optimizer can't produce an optimal plan for queries with sub-queries in select list since it always decorrelate sub-queries
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;
We need the rule JoinToApply to do the optimization.
Agree, that needs cost based cascades optimizer.
the inner join and left join are built from syntax directly, not decorated from apply, so just modify the title
for internal part: we can use INL_JOIN hint to use "APPLY" MODE
tidb> set @@tidb_enable_inl_join_inner_multi_pattern=1;
Query OK, 0 rows affected (0.00 sec)
tidb> explain select * from small_t left join ( select /*+ inl_join(big_t2) */ 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_14 | 10000.00 | root | | left outer join, equal:[eq(test.small_t.id, test.big_t.id)] |
| ├─IndexJoin_25(Build) | 7992.00 | root | | inner join, inner:Selection_24, outer key:test.big_t.id, inner key:test.big_t.id, equal cond:eq(test.big_t.id, test.big_t.id), eq(test.big_t.v, Column#9) |
| │ ├─TableReader_53(Build) | 9980.01 | root | | data:Selection_52 |
| │ │ └─Selection_52 | 9980.01 | cop[tikv] | | not(isnull(test.big_t.id)), not(isnull(test.big_t.v)) |
| │ │ └─TableFullScan_51 | 10000.00 | cop[tikv] | table:big_t | keep order:false, stats:pseudo |
| │ └─Selection_24(Probe) | 63808191.94 | root | | not(isnull(Column#9)) |
| │ └─HashAgg_22 | 79760239.92 | root | | group by:test.big_t.id, funcs:min(Column#11)->Column#9, funcs:firstrow(test.big_t.id)->test.big_t.id |
| │ └─IndexLookUp_23 | 79760239.92 | root | | |
| │ ├─Selection_20(Build) | 7992.00 | cop[tikv] | | not(isnull(test.big_t.id)) |
| │ │ └─IndexRangeScan_18 | 8000.00 | cop[tikv] | table:big_t, index:id(id) | range: decided by [eq(test.big_t.id, test.big_t.id)], keep order:false, stats:pseudo |
| │ └─HashAgg_21(Probe) | 79760239.92 | cop[tikv] | | group by:test.big_t.id, funcs:min(test.big_t.v)->Column#11 |
| │ └─TableRowIDScan_19 | 7992.00 | cop[tikv] | table:big_t | keep order:false, stats:pseudo |
| └─TableReader_17(Probe) | 10000.00 | root | | data:TableFullScan_16 |
| └─TableFullScan_16 | 10000.00 | cop[tikv] | table:small_t | keep order:false, stats:pseudo |
+---------------------------------------+-------------+-----------+---------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------+
14 rows in set, 1 warning (0.00 sec)
tidb> explain select * from small_t left join ( select /*+ inl_join(big_t) */ 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_14 | 10000.00 | root | | left outer join, equal:[eq(test.small_t.id, test.big_t.id)] |
| ├─IndexJoin_23(Build) | 7992.00 | root | | inner join, inner:IndexLookUp_22, outer key:test.big_t.id, inner key:test.big_t.id, equal cond:eq(Column#9, test.big_t.v), eq(test.big_t.id, test.big_t.id) |
| │ ├─Selection_33(Build) | 6393.60 | root | | not(isnull(Column#9)) |
| │ │ └─HashAgg_41 | 7992.00 | root | | group by:test.big_t.id, funcs:min(Column#13)->Column#9, funcs:firstrow(test.big_t.id)->test.big_t.id |
| │ │ └─TableReader_42 | 7992.00 | root | | data:HashAgg_34 |
| │ │ └─HashAgg_34 | 7992.00 | cop[tikv] | | group by:test.big_t.id, funcs:min(test.big_t.v)->Column#13 |
| │ │ └─Selection_40 | 9990.00 | cop[tikv] | | not(isnull(test.big_t.id)) |
| │ │ └─TableFullScan_39 | 10000.00 | cop[tikv] | table:big_t | keep order:false, stats:pseudo |
| │ └─IndexLookUp_22(Probe) | 7992.00 | root | | |
| │ ├─Selection_20(Build) | 8000.00 | cop[tikv] | | not(isnull(test.big_t.id)) |
| │ │ └─IndexRangeScan_18 | 8008.01 | cop[tikv] | table:big_t, index:id(id) | range: decided by [eq(test.big_t.id, test.big_t.id)], keep order:false, stats:pseudo |
| │ └─Selection_21(Probe) | 7992.00 | cop[tikv] | | not(isnull(test.big_t.v)) |
| │ └─TableRowIDScan_19 | 8000.00 | cop[tikv] | table:big_t | keep order:false, stats:pseudo |
| └─TableReader_17(Probe) | 10000.00 | root | | data:TableFullScan_16 |
| └─TableFullScan_16 | 10000.00 | cop[tikv] | table:small_t | keep order:false, stats:pseudo |
+----------------------------------------+----------+-----------+---------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------+
15 rows in set, 1 warning (0.00 sec)
but for outer part: t_small and derived table from (t_big and t_big2), there is no way to hint for index join