pingcap / pingcap/tidb

planner: NDV used in join cardinality estimation is over-estimated in some cases

Open
#36,475 1 comment 0 reactions 0 assignees View on GitHub
epic/cardinality-estimation sig/planner type/enhancement
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.

image

Contributor guide

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.