cockroachdb / cockroachdb/cockroach

sql/opt: per-group filtered histograms and IN-list spans retained across candidate scans can OOM planning

Open
#173,722 0 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer branch-master C-bug O-agent T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

**Describe the problem**

Two planning-time allocations compound across candidate constrained scans and
drive the process to OOM:

1. The filters/scalar constraint builder (`memo.constraintsBuilder`, used for
cardinality estimation and filter simplification) builds one span per `IN`
element with no `optimizer_span_limit` consultation.
2. Each scan/select group stores a filtered histogram
(`colStat.Histogram = inputHist.Filter(c)`) into its shared relational props.
`Histogram.filter` can *increase* the bucket count (≈ 2 buckets per range
span + 1 per point span), so a constraint with S point spans over a B-bucket
histogram yields ≈ 2S + B buckets, retained per group.

With a table that has many secondary indexes leading with the constrained
column, each index is a candidate constrained scan retaining its own span set +
filtered histogram, and all coexist in the memo until planning ends. These are
plain Go heap allocations not covered by `--max-sql-memory`. Keeping the IN-list
just under `optimizer_span_limit` (131072) maximizes per-group span/bucket
counts on the index path. `EXPLAIN` alone triggers it.

**To Reproduce**

On a node limited to ~2GB (e.g. `cockroach demo` under a 2GB cgroup, or with
`GOMEMLIMIT=1100000000 --max-sql-memory=512MiB --cache=512MiB`):

```bash
python3 - <<'PY' | cockroach demo --no-example-database --insecure --max-sql-memory=512MiB --cache=512MiB
NIN, NIDX, NB = 130000, 100, 200 # IN-list (< span limit), #indexes, #buckets
cols = ["x INT","y INT","z INT"] + [f"c{i} INT" for i in range(NIDX)]
print(f"CREATE TABLE t (k INT PRIMARY KEY, {', '.join(cols)});")
for i in range(NIDX):
print(f"CREATE INDEX idx{i} ON t (x, c{i});")
def hist(c):
step = max(1, NIN//NB)
b = ",".join('{"num_eq":100,"num_range":100,"distinct_range":50,"upper_bound":"%d"}' % (k*step) for k in range(NB))
return ('{"columns":["%s"],"created_at":"2024-01-01 00:00:00","row_count":1000000,'
'"distinct_count":%d,"null_count":0,"histo_col_type":"INT8","histo_buckets":[%s]}' % (c, NIN, b))
print("ALTER TABLE t INJECT STATISTICS '[%s]';" % ",".join(hist(c) for c in ["x","y","z"]))
vals = ",".join(map(str, range(NIN)))
print(f"EXPLAIN SELECT * FROM t WHERE x IN ({vals}) AND y > 0 AND z > 0;")
PY
```

Retained growth is `O(groups × constrained-cols × (spans + buckets))`.

**Observed**

- Setup only (100 indexes + injected stats, no `EXPLAIN`): completes,
~1.2GB peak RSS.
- Adding the `EXPLAIN`: heap grows past 2GB, OOM-killed during planning.
- Pushing the IN-list *over* `optimizer_span_limit` (e.g. 200000) makes the
index path bail to unconstrained and uses *less* memory — confirming the
blowup is the per-group constrained-scan span/histogram retention.

**Environment**

- CockroachDB `v26.4.0-alpha` (master), CCL, `cockroach demo` single node.
- Client: `cockroach sql`.

**Code reference**

`buildSingleColumnConstraint` in `pkg/sql/opt/memo/constraint_builder.go`
(spans allocated per IN element, no span-limit); `updateHistogram` in
`pkg/sql/opt/memo/statistics_builder.go` and `Histogram.filter` in
`pkg/sql/opt/props/histogram.go` (per-group filtered histograms).

Jira issue: CRDB-67029

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the EXPLAIN workload in the issue under the stated memory limits. Read buildSingleColumnConstraint in pkg/sql/opt/memo/constraint_builder.go, updateHistogram in pkg/sql/opt/memo/statistics_builder.go, and Histogram.filter in pkg/sql/opt/props/histogram.go. Done means planning no longer retains enough spans and filtered histogram buckets across candidate scans to cause the reported OOM.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.