cockroachdb / cockroachdb/cockroach
opt: SplitLimitedScanIntoUnionScans does not apply for highly selective constraints
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
The exploration rule `SplitLimitedScanIntoUnionScans` which can push hard limits into scans to avoid sort or top-k expressions currently has this check: https://github.com/cockroachdb/cockroach/blob/d6ccd106865e86c765112353562cc07f3afe2ead/pkg/sql/opt/xform/general_funcs.go#L504-L515
The purpose of this check is to prevent the rule from firing when it is unlikely to produce a more efficient plan. However, this check is far too strict. It prevents the rule from firing when the original scan is highly selective, e.g., a row count less than one. There are a couple reasons it is too strict:
1. `rowCount * log₂(rowCount)` is negative when `rowCount` is less than one.
2. It is comparing two different _units_, rows and cost.
Here's an example based on a real-world query where the check prevents the scan from being split into unions of limited scans.
```
exec-ddl
CREATE TABLE t (
crdb_region STRING,
id INT,
a INT,
b INT,
c INT,
PRIMARY KEY (crdb_region, id),
CHECK (crdb_region IN ('ca', 'us', 'eu')),
INDEX (crdb_region, a, b, c)
)
----
exec-ddl
ALTER TABLE t INJECT STATISTICS '[
{
"columns": ["crdb_region"],
"created_at": "2018-01-01 1:00:00.00000+00:00",
"row_count": 1000000,
"distinct_count": 3,
"histo_col_type": "string",
"histo_buckets": [
{"num_eq": 330000, "num_range": 0, "distinct_range": 0, "upper_bound": "ca"},
{"num_eq": 330000, "num_range": 0, "distinct_range": 0, "upper_bound": "eu"},
{"num_eq": 340000, "num_range": 0, "distinct_range": 0, "upper_bound": "us"}
]
},
{
"columns": ["id"],
"created_at": "2018-01-01 1:00:00.00000+00:00",
"row_count": 1000000,
"distinct_count": 1000000,
"histo_col_type": "int",
"histo_buckets": [
{"num_eq": 0, "num_range": 0, "distinct_range": 0, "upper_bound": "0"},
{"num_eq": 1, "num_range": 9, "distinct_range": 9, "upper_bound": "10"},
{"num_eq": 1, "num_range": 999989, "distinct_range": 999989, "upper_bound": "1000000"}
]
},
{
"columns": ["a"],
"created_at": "2018-01-01 1:00:00.00000+00:00",
"row_count": 1000000,
"distinct_count": 1000,
"histo_col_type": "int",
"histo_buckets": [
{"num_eq": 0, "num_range": 0, "distinct_range": 0, "upper_bound": "0"},
{"num_eq": 1000, "num_range": 9, "distinct_range": 9, "upper_bound": "10"},
{"num_eq": 1, "num_range": 998990, "distinct_range": 998990, "upper_bound": "1000"}
]
},
{
"columns": ["b"],
"created_at": "2018-01-01 1:00:00.00000+00:00",
"row_count": 1000000,
"distinct_count": 1000,
"histo_col_type": "int",
"histo_buckets": [
{"num_eq": 0, "num_range": 0, "distinct_range": 0, "upper_bound": "0"},
{"num_eq": 1000, "num_range": 9, "distinct_range": 9, "upper_bound": "10"},
{"num_eq": 1, "num_range": 998990, "distinct_range": 998990, "upper_bound": "1000"}
]
},
{
"columns": ["c"],
"created_at": "2018-01-01 1:00:00.00000+00:00",
"row_count": 1000000,
"distinct_count": 1000,
"histo_col_type": "int",
"histo_buckets": [
{"num_eq": 0, "num_range": 0, "distinct_range": 0, "upper_bound": "0"},
{"num_eq": 1000, "num_range": 9, "distinct_range": 9, "upper_bound": "10"},
{"num_eq": 1, "num_range": 998990, "distinct_range": 998990, "upper_bound": "1000"}
]
}
]'
----
opt format=show-stats
SELECT * FROM t
WHERE a = 10 AND b = 10 AND c = 10 AND id > 10
ORDER BY id LIMIT 1
----
top-k
├── columns: crdb_region:1!null id:2!null a:3!null b:4!null c:5!null
├── internal-ordering: +2 opt(3-5)
├── k: 1
├── stats: [rows=0.8101819]
└── scan t@t_crdb_region_a_b_c_idx
├── columns: crdb_region:1!null id:2!null a:3!null b:4!null c:5!null
├── constraint: /1/3/4/5/2
│ ├── [/'ca'/10/10/10/11 - /'ca'/10/10/10]
│ ├── [/'eu'/10/10/10/11 - /'eu'/10/10/10]
│ └── [/'us'/10/10/10/11 - /'us'/10/10/10]
└── stats: [rows=0.8101819, distinct(2)=0.810182, null(2)=0, distinct(3)=0.810182, null(3)=0, distinct(4)=0.810182, null(4)=0, distinct(5)=0.810182, null(5)=0, distinct(3-5)=0.810182, null(3-5)=0, distinct(2-5)=0.810182, null(2-5)=0]
histogram(2)= 0 0 0.81018 8.1019e-07
<--- 10 --------- 1000000 -
histogram(3)= 0 0.81018
<---- 10 --
histogram(4)= 0 0.81018
<---- 10 --
histogram(5)= 0 0.81018
<---- 10 --
```
Notice that the plan could scan up to 1000 rows (assuming the stats are accurate), but if we perform 3 separate scans we only need to scan at most 3 rows.
I believe the check in `SplitLimitedScanIntoUnionScans` should be removed. I believe it's an anti-pattern to make cost-based decisions inside an exploration rule.
Jira issue: CRDB-22868
Contributor guide
Assessment
This issue has not been assessed yet.