cockroachdb / cockroachdb/cockroach

sql/opt: JoinOrderBuilder is 3^N time / 2^N memory and uninterruptible when reorder_joins_limit is raised

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

`JoinOrderBuilder`'s DP enumeration is `Θ(3^N)` time and `Θ(2^N)` memory, and it
runs uninterruptibly. `dpSube` iterates over all `2^N-1` vertex subsets and, for
each, every sub-subset (Σ 2^|S| = 3^N partition pairs), minting a join memo
expression per pair; the `plans` and `applicableEdges` maps grow to `2^N`
entries. These are plain Go allocations not covered by `--max-sql-memory`. There
are no cancellation checks between the limit check and the end of the
enumeration, so `statement_timeout` cannot interrupt it.

`N` is bounded by `reorder_joins_limit + 1`. The cluster setting is clamped to
[0, 63], but session-level `SET reorder_joins_limit = N` rejects only negatives,
so an arbitrarily high value can be set. At the default (8) this is safe; raised,
`EXPLAIN` of a connected N-way join OOMs during planning.

**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 = 18
for i in range(N):
print(f"CREATE TABLE t{i} (a INT, b INT);")
print(f"SET reorder_joins_limit = {N};")
tables = ", ".join(f"t{i}" for i in range(N))
conds = " AND ".join(f"t{i}.a=t{i+1}.a" for i in range(N-1))
print(f"EXPLAIN SELECT * FROM {tables} WHERE {conds};")
PY
```

Tables are empty. Growth is time `Θ(3^N)`, live maps `Θ(2^N)`.

**Observed**

- `reorder_joins_limit = 18`, 18-way connected join: heap grows past 2GB,
OOM-killed during `EXPLAIN` (~33s, running uninterruptibly).
- Control — same 18-way join at the default `reorder_joins_limit = 8`:
completes at baseline RSS in a few seconds.

**Environment**

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

**Code reference**

`dpSube` and the `plans` / `applicableEdges` maps in
`pkg/sql/opt/xform/join_order_builder.go`; session validation for
`reorder_joins_limit` in `pkg/sql/vars.go`.

Jira issue: CRDB-67030

Contributor guide

Open the contributing guide

Research direction

Start with dpSube and the plans/applicableEdges maps in pkg/sql/opt/xform/join_order_builder.go, then inspect session validation for reorder_joins_limit in pkg/sql/vars.go. Reproduce the 18-way EXPLAIN from the issue under the stated memory limits and compare it with the default limit. Done means raised limits no longer allow unbounded planning memory or an uninterruptible enumeration, while statement_timeout can interrupt the work.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.