pingcap / pingcap/tidb

planner: remove duplicated predicates in CNF or DNF

Open
#61,568 2 comments 0 reactions 0 assignees View on GitHub
report/customer sig/planner type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement
See the case below:
```
create table t1 (a int, b int, c int);
create table t2 (a int, b int, c int);

explain select * from t1 where
1=1 and (
(t1.a in (select a from t2 where b>10)) or
(t1.a in (select a from t2 where b>10)) or
(t1.a in (select a from t2 where b>10)))

+--------------------------------------+----------+-----------+---------------+-----------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+--------------------------------------+----------+-----------+---------------+-----------------------------------------------------------------------------------------------+
| Projection_16 | 8000.00 | root | | test.t1.a, test.t1.b, test.t1.c |
| └─Selection_17 | 8000.00 | root | | or(Column#9, or(Column#14, Column#19)) |
| └─HashJoin_24 | 10000.00 | root | | CARTESIAN left outer semi join, left side:HashJoin_31, other cond:eq(test.t1.a, test.t2.a) |
| ├─TableReader_49(Build) | 3333.33 | root | | data:Selection_48 |
| │ └─Selection_48 | 3333.33 | cop[tikv] | | gt(test.t2.b, 10) |
| │ └─TableFullScan_47 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
| └─HashJoin_31(Probe) | 10000.00 | root | | CARTESIAN left outer semi join, left side:HashJoin_38, other cond:eq(test.t1.a, test.t2.a) |
| ├─TableReader_46(Build) | 3333.33 | root | | data:Selection_45 |
| │ └─Selection_45 | 3333.33 | cop[tikv] | | gt(test.t2.b, 10) |
| │ └─TableFullScan_44 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
| └─HashJoin_38(Probe) | 10000.00 | root | | CARTESIAN left outer semi join, left side:TableReader_40, other cond:eq(test.t1.a, test.t2.a) |
| ├─TableReader_43(Build) | 3333.33 | root | | data:Selection_42 |
| │ └─Selection_42 | 3333.33 | cop[tikv] | | gt(test.t2.b, 10) |
| │ └─TableFullScan_41 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
| └─TableReader_40(Probe) | 10000.00 | root | | data:TableFullScan_39 |
| └─TableFullScan_39 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+--------------------------------------+----------+-----------+---------------+-----------------------------------------------------------------------------------------------+
```

The DNF in this query is generated by code, so there might be some duplicated predicates: `(t1.a in (select a from t2 where b>10))`. Since there are 3 duplicated predicates, we have to execute the same `HashJoin` three times.
The optimizer should remove these duplicated predicates automatically, and the final optimal plan should be:

```
+----------------------------------+----------+-----------+---------------+----------------------------------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------------+----------+-----------+---------------+----------------------------------------------------------+
| HashJoin_26 | 3330.00 | root | | inner join, equal:[eq(test.t2.a, test.t1.a)] |
| ├─HashAgg_32(Build) | 2664.00 | root | | group by:test.t2.a, funcs:firstrow(test.t2.a)->test.t2.a |
| │ └─TableReader_33 | 2664.00 | root | | data:HashAgg_27 |
| │ └─HashAgg_27 | 2664.00 | cop[tikv] | | group by:test.t2.a, |
| │ └─Selection_31 | 3330.00 | cop[tikv] | | gt(test.t2.b, 10), not(isnull(test.t2.a)) |
| │ └─TableFullScan_30 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
| └─TableReader_45(Probe) | 9990.00 | root | | data:Selection_44 |
| └─Selection_44 | 9990.00 | cop[tikv] | | not(isnull(test.t1.a)) |
| └─TableFullScan_43 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+----------------------------------+----------+-----------+---------------+----------------------------------------------------------+
```

And CNF has the same problem:
```
mysql> explain select * from t1 where
-> 1=1 and (
-> (t1.a in (select a from t2 where b>10)) and
-> (t1.a in (select a from t2 where b>10)) and
-> (t1.a in (select a from t2 where b>10)));
+--------------------------------------+----------+-----------+---------------+----------------------------------------------------------+
| id | estRows | task | access object | operator info |
+--------------------------------------+----------+-----------+---------------+----------------------------------------------------------+
| HashJoin_38 | 2664.00 | root | | inner join, equal:[eq(test.t1.a, test.t2.a)] |
| ├─HashAgg_114(Build) | 2664.00 | root | | group by:test.t2.a, funcs:firstrow(test.t2.a)->test.t2.a |
| │ └─TableReader_115 | 2664.00 | root | | data:HashAgg_109 |
| │ └─HashAgg_109 | 2664.00 | cop[tikv] | | group by:test.t2.a, |
| │ └─Selection_113 | 3330.00 | cop[tikv] | | gt(test.t2.b, 10), not(isnull(test.t2.a)) |
| │ └─TableFullScan_112 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
| └─HashJoin_52(Probe) | 2664.00 | root | | inner join, equal:[eq(test.t1.a, test.t2.a)] |
| ├─HashAgg_98(Build) | 2664.00 | root | | group by:test.t2.a, funcs:firstrow(test.t2.a)->test.t2.a |
| │ └─TableReader_99 | 2664.00 | root | | data:HashAgg_93 |
| │ └─HashAgg_93 | 2664.00 | cop[tikv] | | group by:test.t2.a, |
| │ └─Selection_97 | 3330.00 | cop[tikv] | | gt(test.t2.b, 10), not(isnull(test.t2.a)) |
| │ └─TableFullScan_96 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
| └─HashJoin_67(Probe) | 3330.00 | root | | inner join, equal:[eq(test.t2.a, test.t1.a)] |
| ├─HashAgg_73(Build) | 2664.00 | root | | group by:test.t2.a, funcs:firstrow(test.t2.a)->test.t2.a |
| │ └─TableReader_74 | 2664.00 | root | | data:HashAgg_68 |
| │ └─HashAgg_68 | 2664.00 | cop[tikv] | | group by:test.t2.a, |
| │ └─Selection_72 | 3330.00 | cop[tikv] | | gt(test.t2.b, 10), not(isnull(test.t2.a)) |
| │ └─TableFullScan_71 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
| └─TableReader_86(Probe) | 9990.00 | root | | data:Selection_85 |
| └─Selection_85 | 9990.00 | cop[tikv] | | not(isnull(test.t1.a)) |
| └─TableFullScan_84 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+--------------------------------------+----------+-----------+---------------+----------------------------------------------------------+
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.