cockroachdb / cockroachdb/cockroach

ORed predicate selectivity overestimate makes full scan of LIMIT query look cheap

Open
#106,872 0 comments 0 reactions 0 assignees View on GitHub
C-bug T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

**Describe the problem**
The following query with a small LIMIT value is using a full scan instead of doing a constrained scan from the index when it shouldn't:
```sql
EXPLAIN(opt,verbose) SELECT
data
FROM
t1
WHERE
(
status = 'status1'
AND ts1 <= '2020-01-01 11:45:00.123456'
)
OR (
status = 'status4'
AND ts2 <= '2020-01-01 11:45:00.123456'
)
LIMIT
15;
info
------------------------
project
├── columns: data:2
├── cardinality: [0 - 15]
├── stats: [rows=15]
├── cost: 129.52
├── prune: (2)
└── limit
├── columns: data:2 ts1:3 ts2:4 status:5
├── cardinality: [0 - 15]
├── stats: [rows=15]
├── cost: 129.36
├── select
│ ├── columns: data:2 ts1:3 ts2:4 status:5
│ ├── stats: [rows=20666.67, distinct(5)=2, null(5)=0]
│ ├── cost: 129.2
│ ├── limit hint: 15.00
│ ├── prune: (2)
│ ├── scan t1
│ │ ├── columns: data:2 ts1:3 ts2:4 status:5
│ │ ├── stats: [rows=124000, distinct(5)=4, null(5)=0]
│ │ │ histogram(5)= 0 2800 1 1.01e+05 1 19500
│ │ │ <--- 'status1' --- 'status2' --- 'status3'
│ │ ├── cost: 128.27
│ │ ├── limit hint: 90.00
│ │ └── prune: (2-5)
│ └── filters
│ └── ((status:5 = 'status1') AND (ts1:3 <= '2020-01-01 11:45:00.123456')) OR ((status:5 = 'status4') AND (ts2:4 <= '2020-01-01 11:45:00.123456')) [outer=(3-5), constraints=(/5: [/'status1' - /'status1'] [/'status4' - /'status4'])]
└── 15
```
When LIMIT is used, the optimizer computes a "limit hint" to pass to the execution engine to read a reduced set of rows in each batch, with the assumption that the selection filter ((status = 'status1') AND (ts1 <= '2020-01-01 11:45:00.123456')) OR ((status = 'status4') AND (ts2 <= '2020-01-01 11:45:00.123456')) needs roughly "limit hint" number of rows input to it to produce the number of rows specified in the LIMIT. This limit hint is then also used to adjust the full table scan costs downwards, with the assumption the scan can stop once that number of rows is scanned.

When the selectivity of the filter (fractional ratio of rows which satisfy the filter) is estimated too high, the limit hint is reduced because we think the filter will filter out less rows than it actually does, and that smaller limit hint causes the cost of the full scan to go down.

#89358 fixes this issue by using a more accurate formula for ORed term selectivity estimation when the optimizer can't form the OR'ed predicates into a "constraint". But in this case a constraint is built, so that fix doesn't kick in.
This issue is opened to extend that fix to ORed predicates that can form a constraint.

Note that in this case, the Select is estimated to have 20666.67 rows, even though there are only 2800 rows with status = 'status1' and no rows with status = 'status4'

Setup for the above issue:
```sql
CREATE TABLE t1 (
id UUID NOT NULL,
data STRING NULL,
ts1 TIMESTAMP NOT NULL,
ts2 TIMESTAMP NOT NULL,
status STRING,
CONSTRAINT pk PRIMARY KEY (id ASC),
INDEX ts1_idx (status ASC, ts1 ASC),
INDEX ts2_idx (status ASC, ts2 ASC)
);

ALTER TABLE t1 INJECT STATISTICS '[
{
"avg_size": 17,
"columns": [
"status"
],
"created_at": "2020-01-01 17:15:42.123456",
"distinct_count": 4,
"histo_buckets": [
{
"distinct_range": 0,
"num_eq": 2800,
"num_range": 0,
"upper_bound": "status1"
},
{
"distinct_range": 0.5,
"num_eq": 101000,
"num_range": 1,
"upper_bound": "status2"
},
{
"distinct_range": 0.5,
"num_eq": 19500,
"num_range": 1,
"upper_bound": "status3"
}
],
"histo_col_type": "STRING",
"histo_version": 2,
"name": "__auto__",
"null_count": 0,
"row_count": 124000
},
{
"avg_size": 11,
"columns": [
"ts2"
],
"created_at": "2020-01-01 17:15:42.123456",
"distinct_count": 122862,
"histo_buckets": [
{
"distinct_range": 0,
"num_eq": 12,
"num_range": 0,
"upper_bound": "2019-03-30 12:00:18.121"
},
{
"distinct_range": 122860,
"num_eq": 12,
"num_range": 124029,
"upper_bound": "2020-01-01 3:45:00.123456"
}
],
"histo_col_type": "TIMESTAMP",
"histo_version": 2,
"name": "__auto__",
"null_count": 0,
"row_count": 124000
},
{
"avg_size": 11,
"columns": [
"ts1"
],
"created_at": "2020-01-01 17:15:42.123456",
"distinct_count": 122400,
"histo_buckets": [
{
"distinct_range": 0,
"num_eq": 12,
"num_range": 0,
"upper_bound": "2019-03-30 12:00:18.121"
},
{
"distinct_range": 122468,
"num_eq": 12,
"num_range": 124020,
"upper_bound": "2020-01-01 12:45:00.123456"
}
],
"histo_col_type": "TIMESTAMP",
"histo_version": 2,
"name": "__auto__",
"null_count": 0,
"row_count": 124000
}
]';
```
**Environment:**
- CockroachDB version: All versions, 23.1+ and below

**Additional context**
What was the impact?
Query needs to be rewritten to run efficiently

The initial reporting of this issue was through https://github.com/cockroachlabs/support/issues/2447

Jira issue: CRDB-29746

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.