pingcap / pingcap/tidb

planner: over-estimation of out-of-range EQ predicates when all values are collected in TopN

Open
#64,716 0 comments 0 reactions 1 assignee Claimed by @qw4990 View on GitHub
epic/cardinality-estimation severity/major sig/planner type/bug
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:

Image

Below is the real user case:

Please get in touch with me to get the Plan Replayer.

This issue was accidentally introduced by https://github.com/pingcap/tidb/pull/56848.

Image

Before https://github.com/pingcap/tidb/pull/56848, we just returned 0 or 1 in this case.
In https://github.com/pingcap/tidb/pull/56848, the formula becomes like:
1. if NDV is 0, then `modify_cnt / sqrt(realtimerows)`;
2. if NDV is not 0, then `modify_cnt / NDV`;

The problem is in the second part, `modify_cnt / NDV` means we still assume the current estimating value is one of those that have appeared before, which contradicts with the out-of-range semantic here.

The data distribution is like:

```
create table t (a int, key(a));
insert t values (1, 2, 3);
...
insert t values (1, 2, 3); -- 10000 rows
analyze table t;

insert more data into t to let modify_cnt = 10000

then estimate "where t.a=5";

`t.a=5` is an out-of-range estimation for the prior collected stats which is based on `1, 2, 3`.
So the prior NDV=3 based on `1, 2, 3` as well is not appropriate for the current out-of-range estimation.
```

It seems like we should always use `modify_cnt / sqrt(realtimerows)` in this case. And below is the result of using the first formula, which seems much better:

Image

Image

### 2. What did you expect to see? (Required)
A relatively low estimation result

### 3. What did you see instead (Required)
A large estimation result.

### 4. What is your TiDB version? (Required)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.