planner: greedy join reorder may seed outer-join groups from the smallest table instead of the cheapest first join
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Bug Report
Please answer these questions before submitting your issue. Thanks!
### 1. Minimal reproduce step (Required)
```
drop table if exists t1, t2, t3;
create table t1(id int primary key, col1 int not null, key idx_col1(col1));
create table t2(id int primary key, col2 int not null);
create table t3(id int primary key, col1 int not null, key idx_col1(col1));
insert into t1 values
(1, 1), (2, 2), (3, 3), (4, 4),
(5, 5), (6, 6), (7, 7), (8, 8),
(9, 9), (10, 10), (11, 11), (12, 12),
(13, 13), (14, 14), (15, 15), (16, 16);
insert into t2 values (1, 1);
insert into t3 values (1, 1), (2, 2);
analyze table t1, t2, t3;
set @@tidb_enable_outer_join_reorder = 1;
explain select * from
(select t1.id, t1.col1 from t1 left join t2 on t1.col1 = t2.col2) tt
join t3 on t3.col1 = tt.col1;
```
The simplified background is:
```
select * from
(select t1.* from t1 left join t2 on t1.col1 = t2.col2) tt
join t3 on t3.col1 = tt.col1;
```
Assume t2 < t3 << t1, and t1.col1 has an index. And performing an inner join between t1 and t3 first can significantly reduce the number of rows
### 2. What did you expect to see? (Required)
```
+-------------------------------+---------+-----------+--------------------------------+---------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+---------+-----------+--------------------------------+---------------------------------------------------------------------------------+
| HashJoin_20 | 4.00 | root | | left outer join, left side:MergeJoin_22, equal:[eq(test.t1.col1, test.t2.col2)] |
| ├─TableReader_54(Build) | 2.00 | root | | data:TableFullScan_53 |
| │ └─TableFullScan_53 | 2.00 | cop[tikv] | table:t2 | keep order:false |
| └─MergeJoin_22(Probe) | 4.00 | root | | inner join, left key:test.t1.col1, right key:test.t3.col1 |
| ├─IndexReader_40(Build) | 4.00 | root | | index:IndexFullScan_39 |
| │ └─IndexFullScan_39 | 4.00 | cop[tikv] | table:t3, index:idx_col1(col1) | keep order:true |
| └─IndexReader_38(Probe) | 32.00 | root | | index:IndexFullScan_37 |
| └─IndexFullScan_37 | 32.00 | cop[tikv] | table:t1, index:idx_col1(col1) | keep order:true |
+-------------------------------+---------+-----------+--------------------------------+---------------------------------------------------------------------------------+
```
The greedy join reorder should choose the cheapest valid first join, which is to join t3 with t1 first and then left-join t2.
That keeps the intermediate result smaller and exposes a better physical plan.
### 3. What did you see instead (Required)
```
+-------------------------------+---------+-----------+---------------+-----------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+---------+-----------+---------------+-----------------------------------------------------------------------------------+
| HashJoin_27 | 4.00 | root | | inner join, equal:[eq(test.t1.col1, test.t3.col1)] |
| ├─TableReader_54(Build) | 4.00 | root | | data:TableFullScan_53 |
| │ └─TableFullScan_53 | 4.00 | cop[tikv] | table:t3 | keep order:false |
| └─HashJoin_43(Probe) | 32.00 | root | | left outer join, left side:TableReader_46, equal:[eq(test.t1.col1, test.t2.col2)] |
| ├─TableReader_50(Build) | 2.00 | root | | data:TableFullScan_49 |
| │ └─TableFullScan_49 | 2.00 | cop[tikv] | table:t2 | keep order:false |
| └─TableReader_46(Probe) | 32.00 | root | | data:TableFullScan_45 |
| └─TableFullScan_45 | 32.00 | cop[tikv] | table:t1 | keep order:false |
+-------------------------------+---------+-----------+---------------+-----------------------------------------------------------------------------------+
8 rows in set (0.00 sec)
```
The greedy algorithm seeds the join group from the smallest base table.
In this case it may start from t2, which effectively leads to starting from t1 left join t2, even though that outer join cannot reduce below t1's row count.
As a result, the first greedy choice is driven by base-table size instead of the cumulative cost of the first valid join.
### 4. What is your TiDB version? (Required)
lastest master
Contributor guide
Assessment
This issue has not been assessed yet.