cockroachdb / cockroachdb/cockroach

sql/opt: index-constraint OR-union path is not bounded by optimizer_span_limit

Open
#173,724 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**

The index-constraint OR-union path is not bounded by `optimizer_span_limit`.
`makeSpansForOr` collects contiguous ORs and unions them via
`binaryMergeSpansForOr` (divide-and-conquer `Constraint.UnionWith`), with no
`spanLimit` check and no cancellation check anywhere in the recursion. A large
single-column OR-of-equalities on an indexed column therefore builds and retains
an `O(N)`-span constraint in `ScanPrivate.Constraint` (peak transient
`O(N log N)` from the merges). There is no OR→IN normalization, so such a
predicate never reaches the span-limit guard on the IN path.

These are plain Go heap allocations during planning, not covered by
`--max-sql-memory`. `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
N = 1000000
ors = " OR ".join(f"c = {2*i}" for i in range(1, N+1))
print("CREATE TABLE t (k INT PRIMARY KEY, c INT, INDEX (c));")
print(f"EXPLAIN SELECT * FROM t WHERE {ors};")
PY
```

Retained growth is `O(N)` in the number of OR disjuncts (linear in query text).

**Observed**

- `N = 100000`: completes, ~1.2GB peak RSS.
- `N = 300000`: completes, ~1.9GB peak RSS.
- `N = 1000000` (~14 MB of SQL): heap grows past 2GB, OOM-killed during
`EXPLAIN` within a few seconds.

**Environment**

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

**Code reference**

`makeSpansForOr` / `binaryMergeSpansForOr` in
`pkg/sql/opt/idxconstraint/index_constraints.go`; `Constraint.UnionWith` in
`pkg/sql/opt/constraint/constraint.go`.

Jira issue: CRDB-67031

Contributor guide

Open the contributing guide

Research direction

Read makeSpansForOr and binaryMergeSpansForOr in pkg/sql/opt/idxconstraint/index_constraints.go, then follow Constraint.UnionWith in pkg/sql/opt/constraint/constraint.go. Run the provided cockroach demo EXPLAIN reproduction and inspect how span limits and cancellation are handled in the OR-union recursion. Done means large OR predicates no longer retain unbounded planning spans or continue recursive work after cancellation.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.