planner: NDV used in join cardinality estimation is over-estimated in some cases
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
```
create table t1 (a int);
insert into t1 values (1), (2);
...
insert into t1 values (1), (2); -- 100
create table t2 (a int);
insert into t2 select * from t1;
insert into t2 values(3);
...
insert into t2 values(200);
analyze table t1;
analyze table t2;
mysql> explain analyze select * from t1, t2 where t1.a=t2.a and t2.a in (1, 2);
+------------------------------+---------+---------+-----------+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------------------+-----------+---------+
| id | estRows | actRows | task | access object | execution info | operator info | memory | disk |
+------------------------------+---------+---------+-----------+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------------------+-----------+---------+
| HashJoin_9 | 415.22 | 20000 | root | | time:1.64ms, loops:21, build_hash_table:{total:92.1µs, fetch:76.5µs, build:15.6µs}, probe:{concurrency:5, total:2.35ms, max:1.61ms, probe:1.26ms, fetch:1.09ms} | inner join, equal:[eq(test.t1.a, test.t2.a)] | 8.23 KB | 0 Bytes |
| ├─TableReader_12(Build) | 200.00 | 200 | root | | time:27.4µs, loops:2, cop_task: {num: 1, max: 169.5µs, proc_keys: 0, rpc_num: 1, rpc_time: 162.1µs, copr_cache_hit_ratio: 0.00} | data:Selection_11 | 590 Bytes | N/A |
| │ └─Selection_11 | 200.00 | 200 | cop[tikv] | | tikv_task:{time:54.8µs, loops:200} | in(test.t1.a, 1, 2), not(isnull(test.t1.a)) | N/A | N/A |
| │ └─TableFullScan_10 | 200.00 | 200 | cop[tikv] | table:t1 | tikv_task:{time:17µs, loops:200} | keep order:false | N/A | N/A |
| └─TableReader_15(Probe) | 200.52 | 200 | root | | time:127.1µs, loops:2, cop_task: {num: 1, max: 288µs, proc_keys: 0, rpc_num: 1, rpc_time: 243.3µs, copr_cache_hit_ratio: 0.00} | data:Selection_14 | 590 Bytes | N/A |
| └─Selection_14 | 200.52 | 200 | cop[tikv] | | tikv_task:{time:96.8µs, loops:382} | in(test.t2.a, 1, 2), not(isnull(test.t2.a)) | N/A | N/A |
| └─TableFullScan_13 | 383.00 | 382 | cop[tikv] | table:t2 | tikv_task:{time:24µs, loops:382} | keep order:false | N/A | N/A |
+------------------------------+---------+---------+-----------+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------------------+-----------+---------+
```
TiDB uses the classical formula `|t1|*|t2|/max(NDV(t1), NDV(t2))` to estimate join cardinality. And in this case, the optimizer estimate `NDV(t2)` as `ColNDV(t2.a) * Selectivity(t2.a in (1, 2)) = 200*0.5 = 100`, but the actual `NDV(t2)` after the condition `t2.a in (1, 2)` is 2.
Contributor guide
Research direction
Start in the planner by reproducing the supplied TiDB SQL and EXPLAIN ANALYZE example, focusing on the join cardinality estimate and filtered NDV calculation. Trace how the IN predicate affects the NDV used for the join, then verify that the estimate reflects the filtered distinct values and add or run coverage for this reproduction.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100