cockroachdb / cockroachdb/cockroach
sql/opt: JoinOrderBuilder is 3^N time / 2^N memory and uninterruptible when reorder_joins_limit is raised
- 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
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