cockroachdb / cockroachdb/cockroach

opt: slow planning time with filters that generate many constraint spans

Open
#100,950 8 comments 0 reactions 0 assignees View on GitHub
C-bug O-support P-3 T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

Consider the table and query below:

```sql
CREATE TABLE (
k STRING PRIMARY KEY,
a STRING,
INDEX a_idx (a)
);

SELECT * FROM t WHERE k IN (... 1000 items ...) AND a IN (... 1000 items ...);
```

The filters in this query cause the optimizer to explore a constrained scan with 1 million spans - one for each combination of the 1000 values of `k` and the 1000 values of `a`. Theses 1 million spans stress algorithms within the optimizer that have time complexity of `O(number of spans)`, which significantly slows down planning time.

CPU and memory profiles highlight significant inefficiencies when filter histograms. As one example, when calculating the selectivity of each span to be unioned together, we copy the column's histogram for each constraint:

https://github.com/cockroachdb/cockroach/blob/57abe808178987f4acf2c87d549e2eed1909eca5/pkg/sql/opt/memo/statistics_builder.go#L855

Some potential improvements here could be:
1. Do not use histograms when calculating span union stats.
2. Avoid high-cost allocations of histogram buckets when filters histograms by using a scatch histogram bucket slice that is ephemeral and can be reused for each span in the constraint.
3. It seems that histograms of string datums cause a significant slow down vs histograms of integers. Investigate this.

Jira issue: CRDB-26709

Contributor guide

Open the contributing guide

Research direction

Start in pkg/sql/opt/memo/statistics_builder.go around line 855 and reproduce the SQL query with 1,000-value filters on both columns. Use CPU and memory profiles to examine histogram copying and string-datum histogram behavior; done means identifying and validating a change that reduces planning time and allocation pressure for these many-span constraints.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Refactor
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.