planner: large outer-join cardinality estimation error when there are multiple join keys
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
Use the script to generate SQLs to prepare data:
```
print('create table t1 (a int, b int, c int, d int);')
print('create table t2 (a int, b int, c int, d int);')
print('create table t3 (a int, b int, c int, d int);')
print('create table t4 (a int, b int, c int, d int);')
print('create table t5 (a int, b int, c int, d int);')
print('')
for a in range(10):
for b in range(10):
for c in range(10):
for d in range(10):
print('insert into t1 values (%d,%d,%d,%d);' % (a, b, c, d))
# insert into t values (0, 0, 0, 0);
# insert into t values (0, 0, 0, 1);
# insert into t values (0, 0, 0, 2);
...
# insert into t values (9, 9, 9, 8);
# insert into t values (9, 9, 9, 9);
print('')
print('insert into t2 select * from t1;')
print('insert into t3 select * from t1;')
print('insert into t4 select * from t1;')
print('insert into t5 select * from t1;')
print('')
print('analyze table t1;')
print('analyze table t2;')
print('analyze table t3;')
print('analyze table t4;')
print('analyze table t5;')
```
Then run the query:
```
+--------------------------------------+----------------------+---------+-----------+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------+----------+---------+
| id | estRows | actRows | task | access object | execution info | operator info | memory | disk |
+--------------------------------------+----------------------+---------+-----------+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------+----------+---------+
| Projection_18 | 20000000000000000.00 | 10000 | root | | time:14.1ms, loops:11, RU:48.291601, Concurrency:5 | 1->Column#26 | 39.3 KB | N/A |
| └─HashJoin_19 | 20000000000000000.00 | 10000 | root | | time:14ms, loops:11, build_hash_table:{total:8.69ms, fetch:5.79ms, build:2.9ms}, probe:{concurrency:5, total:67.9ms, max:13.8ms, probe:4.66ms, fetch:63.2ms} | left outer join, equal:[eq(test.t1.a, test.t5.a) eq(test.t1.b, test.t5.b) eq(test.t1.c, test.t5.c) eq(test.t1.d, test.t5.d)] | 1.04 MB | 0 Bytes |
| ├─TableReader_40(Build) | 10000.00 | 10000 | root | | time:6.93ms, loops:11, cop_task: {num: 7, max: 2.84ms, min: 361.4µs, avg: 1.16ms, p95: 2.84ms, tot_proc: 4ms, rpc_num: 7, rpc_time: 7.99ms, copr_cache_hit_ratio: 0.00, build_task_duration: 2.33µs, max_distsql_concurrency: 1} | data:Selection_39 | 201.4 KB | N/A |
| │ └─Selection_39 | 10000.00 | 10000 | cop[tikv] | | tikv_task:{proc max:2.78ms, min:323.3µs, avg: 1.1ms, p80:1.44ms, p95:2.78ms, iters:0, tasks:7} | not(isnull(test.t5.a)), not(isnull(test.t5.b)), not(isnull(test.t5.c)), not(isnull(test.t5.d)) | N/A | N/A |
| │ └─TableFullScan_38 | 10000.00 | 10000 | cop[tikv] | table:t5 | tikv_task:{proc max:2.78ms, min:323.3µs, avg: 1.1ms, p80:1.44ms, p95:2.78ms, iters:0, tasks:7} | keep order:false | N/A | N/A |
| └─HashJoin_21(Probe) | 20000000000000.00 | 10000 | root | | time:13.6ms, loops:11, build_hash_table:{total:9.1ms, fetch:6.21ms, build:2.89ms}, probe:{concurrency:5, total:65.7ms, max:13.5ms, probe:6.51ms, fetch:59.2ms} | left outer join, equal:[eq(test.t1.a, test.t4.a) eq(test.t1.b, test.t4.b) eq(test.t1.c, test.t4.c) eq(test.t1.d, test.t4.d)] | 1.04 MB | 0 Bytes |
| ├─TableReader_37(Build) | 10000.00 | 10000 | root | | time:7.69ms, loops:11, cop_task: {num: 7, max: 3.34ms, min: 330.2µs, avg: 1.27ms, p95: 3.34ms, tot_proc: 5ms, rpc_num: 7, rpc_time: 8.84ms, copr_cache_hit_ratio: 0.00, build_task_duration: 959ns, max_distsql_concurrency: 1} | data:Selection_36 | 201.4 KB | N/A |
| │ └─Selection_36 | 10000.00 | 10000 | cop[tikv] | | tikv_task:{proc max:3.24ms, min:296.8µs, avg: 1.22ms, p80:1.78ms, p95:3.24ms, iters:0, tasks:7} | not(isnull(test.t4.a)), not(isnull(test.t4.b)), not(isnull(test.t4.c)), not(isnull(test.t4.d)) | N/A | N/A |
| │ └─TableFullScan_35 | 10000.00 | 10000 | cop[tikv] | table:t4 | tikv_task:{proc max:3.24ms, min:296.8µs, avg: 1.22ms, p80:1.78ms, p95:3.24ms, iters:0, tasks:7} | keep order:false | N/A | N/A |
| └─HashJoin_23(Probe) | 20000000000.00 | 10000 | root | | time:13ms, loops:11, build_hash_table:{total:8.89ms, fetch:6.04ms, build:2.85ms}, probe:{concurrency:5, total:62.8ms, max:12.9ms, probe:5.88ms, fetch:56.9ms} | left outer join, equal:[eq(test.t1.a, test.t3.a) eq(test.t1.b, test.t3.b) eq(test.t1.c, test.t3.c) eq(test.t1.d, test.t3.d)] | 1.04 MB | 0 Bytes |
| ├─TableReader_34(Build) | 10000.00 | 10000 | root | | time:7.33ms, loops:11, cop_task: {num: 7, max: 2.77ms, min: 371.5µs, avg: 1.24ms, p95: 2.77ms, tot_proc: 5ms, rpc_num: 7, rpc_time: 8.62ms, copr_cache_hit_ratio: 0.00, build_task_duration: 1.13µs, max_distsql_concurrency: 1} | data:Selection_33 | 201.4 KB | N/A |
| │ └─Selection_33 | 10000.00 | 10000 | cop[tikv] | | tikv_task:{proc max:2.71ms, min:338.1µs, avg: 1.2ms, p80:2.03ms, p95:2.71ms, iters:0, tasks:7} | not(isnull(test.t3.a)), not(isnull(test.t3.b)), not(isnull(test.t3.c)), not(isnull(test.t3.d)) | N/A | N/A |
| │ └─TableFullScan_32 | 10000.00 | 10000 | cop[tikv] | table:t3 | tikv_task:{proc max:2.71ms, min:338.1µs, avg: 1.2ms, p80:2.03ms, p95:2.71ms, iters:0, tasks:7} | keep order:false | N/A | N/A |
| └─HashJoin_25(Probe) | 20000000.00 | 10000 | root | | time:12.4ms, loops:11, build_hash_table:{total:8.71ms, fetch:6.14ms, build:2.57ms}, probe:{concurrency:5, total:59.3ms, max:12.3ms, probe:7ms, fetch:52.3ms} | left outer join, equal:[eq(test.t1.a, test.t2.a) eq(test.t1.b, test.t2.b) eq(test.t1.c, test.t2.c) eq(test.t1.d, test.t2.d)] | 1.04 MB | 0 Bytes |
| ├─TableReader_31(Build) | 10000.00 | 10000 | root | | time:7.16ms, loops:11, cop_task: {num: 7, max: 3.05ms, min: 340.2µs, avg: 1.22ms, p95: 3.05ms, tot_proc: 4ms, rpc_num: 7, rpc_time: 8.51ms, copr_cache_hit_ratio: 0.00, build_task_duration: 4.29µs, max_distsql_concurrency: 1} | data:Selection_30 | 201.4 KB | N/A |
| │ └─Selection_30 | 10000.00 | 10000 | cop[tikv] | | tikv_task:{proc max:2.96ms, min:311.5µs, avg: 1.17ms, p80:1.52ms, p95:2.96ms, iters:0, tasks:7} | not(isnull(test.t2.a)), not(isnull(test.t2.b)), not(isnull(test.t2.c)), not(isnull(test.t2.d)) | N/A | N/A |
| │ └─TableFullScan_29 | 10000.00 | 10000 | cop[tikv] | table:t2 | tikv_task:{proc max:2.96ms, min:311.5µs, avg: 1.17ms, p80:1.52ms, p95:2.96ms, iters:0, tasks:7} | keep order:false | N/A | N/A |
| └─TableReader_28(Probe) | 20000.00 | 10000 | root | | time:4.11ms, loops:11, cop_task: {num: 7, max: 1.55ms, min: 229.1µs, avg: 713.7µs, p95: 1.55ms, tot_proc: 1ms, rpc_num: 7, rpc_time: 4.92ms, copr_cache_hit_ratio: 0.00, build_task_duration: 8.58µs, max_distsql_concurrency: 1} | data:TableFullScan_27 | 201.4 KB | N/A |
| └─TableFullScan_27 | 20000.00 | 10000 | cop[tikv] | table:t1 | tikv_task:{proc max:1.49ms, min:197.4µs, avg: 662.1µs, p80:959.7µs, p95:1.49ms, iters:0, tasks:7} | keep order:false | N/A | N/A |
+--------------------------------------+----------------------+---------+-----------+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------+----------+---------+
```
The cardinality estimation error is huge (20000000000000000 v.s. 10000).
The reason is interesting, our outer-join estimation formula is `LeftRows * RightRows / Max(LeftNDV, RightNDV)`, which is a classical formula for join estimation.
For example, the formula for `select * from t1, t2 where t1.a=t2.a and t1.b=t2.b and t1.c=t2.c` is `Rows(t1) * Rows(t2) / Max(NDV(t1.a, b, c), NDV(t2.a, b, c))`.
But TiDB has no stats for multi-col NDV in this case, so to get `NDV(t1.a, b, c)`, we use `Max(NDV(t1.a), NDV(b), NDV(c))`, which can lead to a huge under-estimation on NDV, which eventually causes this issue.

It's hard to estimate the NDV of multiple columns correctly.
Contributor guide
Assessment
This issue has not been assessed yet.