planner: Histogram out-of-range over-estimation when modify_cnt is high and most values are collected in TopN
- 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)
Here is a simplified case:
Below is a more real case:
Use the SQL below to reproduce this issue:
```
set global tidb_enable_auto_analyze=0;
create table t (v int, key(v));
set @@cte_max_recursion_depth=100000;
insert into t select * from (
with recursive t1 as (
select 1 as v
union all
select v + 1 from t1 where v < 20000
)
select if(v<(20000-10), 0, v-(20000-10)) as v from t1
) t2;
-- restart TiDB to trigger modify cnt update
analyze table t with 1 topn, 3 buckets;
select v, count(1) from t group by v order by v;
-- the data distribution
+------+----------+
| v | count(1) |
+------+----------+
| 0 | 19990 | -- collected in topN
| 1 | 1 | -- others are in Histogram
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
| 10 | 1 |
+------+----------+
set @@cte_max_recursion_depth=100000;
insert into t select * from ( -- insert more data with the same data distribution
with recursive t1 as (
select 1 as v
union all
select v + 1 from t1 where v < 10000
)
select if(v<9990, 0, v-9990) as v from t1
) t2;
-- restart TiDB to trigger modify cnt update
explain analyze select 1 from t where t.v > 0;
+--------------------------+----------+---------+-----------+---------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------+-----------+------+
| id | estRows | actRows | task | access object | execution info | operator info | memory | disk |
+--------------------------+----------+---------+-----------+---------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------+-----------+------+
| Projection_4 | 10015.00 | 20 | root | | time:740.9µs, loops:2, RU:0.48, Concurrency:5 | 1->Column#3 | 3.71 KB | N/A |
| └─IndexReader_6 | 10015.00 | 20 | root | | time:712.6µs, loops:2, cop_task: {num: 1, max: 689.3µs, proc_keys: 0, copr_cache_hit_ratio: 0.00, build_task_duration: 13.8µs, max_distsql_concurrency: 1}, rpc_info:{Cop:{num_rpc:1, total_time:677.4µs}} | index:IndexRangeScan_5 | 349 Bytes | N/A |
| └─IndexRangeScan_5 | 10015.00 | 20 | cop[tikv] | table:t, index:v(v) | tikv_task:{time:670.5µs, loops:0} | range:(0,+inf], keep order:false | N/A | N/A |
+--------------------------+----------+---------+-----------+---------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------+-----------+------+
```
Accidentally caused by https://github.com/pingcap/tidb/pull/57431. When doing out-of-range estimation on Histogram, we first calculate a percentage based on the Histogram, and if there are too many newly added rows, the final result is like `added-rows * per-based-on-hist` (see the pic below):
The problem is that most rows represented by `added-rows` might be collected in TopN, which means we shouldn't multiply it directly by a percentage from Histogram.
The correct formula should be `added-rows * (hist-rows / tot-rows) * per-based-on-hist`.
### 2. What did you expect to see? (Required)
### 3. What did you see instead (Required)
### 4. What is your TiDB version? (Required)
Master
Contributor guide
Assessment
This issue has not been assessed yet.