planner: Explain Explore should consider NO_DECORRELATE() hint #65986
Description
Enhancement
Whether or not decorrelate a query is not cost-based now in TiDB, which caused many suboptimal queries in the past.
The current behavior is that the optimizer always decorrelates sub-queries unless there is a NO_DECORRELATE() hint.
If the outer table is small, always-decorrelate leads to sub-optimal plans. For example, if o is small, the second undecorrelated plan would be better, since it can avoid the full scan on b.
mysql> EXPLAIN select o.* from o
-> where exists (select 1 from r inner join o1 on o1.a=r.a where r.b=o.b)
-> order by o.b limit 1;
+--------------------------------------------+---------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+--------------------------------------------+---------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
| Limit_23 | 1.00 | root | | offset:0, count:1 |
| └─MergeJoin_101 | 1.00 | root | | semi join, left side:Projection_111, left key:test.o.b, right key:test.r.b |
| ├─IndexHashJoin_118(Build) | 1.56 | root | | inner join, inner:IndexReader_52, outer key:test.r.a, inner key:test.o1.a, equal cond:eq(test.r.a, test.o1.a) |
| │ ├─Projection_123(Build) | 1.25 | root | | test.r.a, test.r.b |
| │ │ └─IndexLookUp_122 | 1.25 | root | | |
| │ │ ├─IndexFullScan_119(Build) | 101.14 | cop[tikv] | table:r, index:b(b) | keep order:true, stats:pseudo |
| │ │ └─Selection_121(Probe) | 1.25 | cop[tikv] | | not(isnull(test.r.a)) |
| │ │ └─TableRowIDScan_120 | 101.14 | cop[tikv] | table:r | keep order:false, stats:pseudo |
| │ └─IndexReader_52(Probe) | 1.56 | root | | index:Selection_51 |
| │ └─Selection_51 | 1.56 | cop[tikv] | | not(isnull(test.o1.a)) |
| │ └─IndexRangeScan_50 | 1.56 | cop[tikv] | table:o1, index:a(a) | range: decided by [eq(test.o1.a, test.r.a)], keep order:false, stats:pseudo |
| └─Projection_111(Probe) | 1.25 | root | | test.o.a, test.o.b, test.o.c, test.o.d |
| └─IndexLookUp_110 | 1.25 | root | | |
| ├─IndexFullScan_108(Build) | 1.25 | cop[tikv] | table:o, index:b(b) | keep order:true, stats:pseudo |
| └─TableRowIDScan_109(Probe) | 1.25 | cop[tikv] | table:o | keep order:false, stats:pseudo |
+--------------------------------------------+---------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
mysql> EXPLAIN select o.* from o
-> where exists (select /*+ NO_DECORRELATE() */ 1 from r inner join o1 on o1.a=r.a where r.b=o.b)
-> order by o.b limit 1;
+------------------------------------------+----------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------------------+----------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
| TopN_22 | 1.00 | root | | test.o.b, offset:0, count:1 |
| └─Apply_28 | 10000.00 | root | | CARTESIAN semi join, left side:TableReader_30 |
| ├─TableReader_30(Build) | 10000.00 | root | | data:TableFullScan_29 |
| │ └─TableFullScan_29 | 10000.00 | cop[tikv] | table:o | keep order:false, stats:pseudo |
| └─Limit_33(Probe) | 10000.00 | root | | offset:0, count:1 |
| └─IndexHashJoin_42 | 10000.00 | root | | inner join, inner:IndexReader_71, outer key:test.r.a, inner key:test.o1.a, equal cond:eq(test.r.a, test.o1.a) |
| ├─IndexLookUp_68(Build) | 8000.00 | root | | |
| │ ├─IndexRangeScan_65(Build) | 8927.93 | cop[tikv] | table:r, index:b(b) | range: decided by [eq(test.r.b, test.o.b)], keep order:false, stats:pseudo |
| │ └─Selection_67(Probe) | 8000.00 | cop[tikv] | | not(isnull(test.r.a)) |
| │ └─TableRowIDScan_66 | 8927.93 | cop[tikv] | table:r | keep order:false, stats:pseudo |
| └─IndexReader_71(Probe) | 10000.00 | root | | index:Selection_70 |
| └─Selection_70 | 10000.00 | cop[tikv] | | not(isnull(test.o1.a)) |
| └─IndexRangeScan_69 | 10010.01 | cop[tikv] | table:o1, index:a(a) | range: decided by [eq(test.o1.a, test.r.a)], keep order:false, stats:pseudo |
+------------------------------------------+----------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
Explain Explore should consider whether to decorrelate sub-queries to find potential optimal plans.
A quick solution could be enumerate NO_DECORRELATE() hint with query block number:
mysql> EXPLAIN select /*+ NO_DECORRELATE(@sel_2) */ o.* from o
-> where exists (select 1 from r inner join o1 on o1.a=r.a where r.b=o.b)
-> order by o.b limit 1;
+------------------------------------------+----------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------------------+----------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+
| TopN_22 | 1.00 | root | | test.o.b, offset:0, count:1 |
| └─Apply_28 | 10000.00 | root | | CARTESIAN semi join, left side:TableReader_30 |
| ├─TableReader_30(Build) | 10000.00 | root | | data:TableFullScan_29 |
| │ └─TableFullScan_29 | 10000.00 | cop[tikv] | table:o | keep order:false, stats:pseudo |
| └─Limit_33(Probe) | 10000.00 | root | | offset:0, count:1 |
| └─IndexHashJoin_42 | 10000.00 | root | | inner join, inner:IndexReader_71, outer key:test.r.a, inner key:test.o1.a, equal cond:eq(test.r.a, test.o1.a) |
| ├─IndexLookUp_68(Build) | 8000.00 | root | | |
| │ ├─IndexRangeScan_65(Build) | 8927.93 | cop[tikv] | table:r, index:b(b) | range: decided by [eq(test.r.b, test.o.b)], keep order:false, stats:pseudo |
| │ └─Selection_67(Probe) | 8000.00 | cop[tikv] | | not(isnull(test.r.a)) |
| │ └─TableRowIDScan_66 | 8927.93 | cop[tikv] | table:r | keep order:false, stats:pseudo |
| └─IndexReader_71(Probe) | 10000.00 | root | | index:Selection_70 |
| └─Selection_70 | 10000.00 | cop[tikv] | | not(isnull(test.o1.a)) |
| └─IndexRangeScan_69 | 10010.01 | cop[tikv] | table:o1, index:a(a) | range: decided by [eq(test.o1.a, test.r.a)], keep order:false, stats:pseudo |
+------------------------------------------+----------+-----------+----------------------+---------------------------------------------------------------------------------------------------------------+