cockroachdb / cockroachdb/cockroach

sql/opt: NOT MATERIALIZED multiply-referenced CTE has no inlining cap, causing planning-time OOM

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

A CTE marked `NOT MATERIALIZED` is inlined at every reference site, including
when it is referenced more than once. `CanInlineWith` allows inlining a
multiply-referenced binding whenever `Mtr == CTEMaterializeNever`, and `InlineWith`
rewrites each `WithScan` reference with the full binding subtree via a walk that
is not memoized — the binding is reconstructed at each reference site. A chain of
CTEs where each references the previous one twice therefore expands to `O(2^N)`
inlined relational subtrees at nesting depth `N`. Each rebuilt subtree mints fresh
column IDs, so memo interning cannot collapse the structurally-identical copies,
and the memo retains `O(2^N)` distinct nodes.

With the default (empty) materialization a multiply-referenced CTE is not inlined,
so ordinary nested CTEs stay cheap; `NOT MATERIALIZED` removes that guard. This is
a normalization-phase allocation on the plain Go heap, not covered by
`--max-sql-memory`, and the build/normalization path has no depth cap and no
cancellation check (so `statement_timeout` does not cover it). Growth is
exponential in `N` while the SQL text is `O(N)`. `EXPLAIN` alone triggers it; no
rows are read.

**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 = 20
print("CREATE TABLE base (x INT PRIMARY KEY);")
lines = ["WITH", " c0 AS NOT MATERIALIZED (SELECT x FROM base),"]
for k in range(1, N + 1):
term = f" c{k} AS NOT MATERIALIZED (SELECT a.x FROM c{k-1} AS a JOIN c{k-1} AS b ON a.x = b.x)"
lines.append(term + ("," if k < N else ""))
print("EXPLAIN " + "\n".join(lines) + f"\nSELECT * FROM c{N};")
PY
```

Each `cK` keeps a single output column, so the blowup is purely inlining fan-out
(`2^N` rebuilt subtrees), not column-count growth.

**Observed**

- `N = 16`: completes, ~1.5GB peak RSS.
- `N = 18`: heap grows past 2GB, OOM-killed during planning within a few seconds.
- `N = 20`: same, OOM-killed during planning.
- Control — same shape with `NOT MATERIALIZED` removed (default materialization),
`N = 20`: completes at idle baseline RSS (~0.7GB) in ~2s, since the
multiply-referenced CTEs are not inlined. This isolates the blowup to the
`NOT MATERIALIZED` inlining path.

RSS roughly doubles per two levels of nesting, consistent with `2^N` growth.

**Environment**

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

**Code reference**

`CanInlineWith` and `InlineWith` in `pkg/sql/opt/norm/with_funcs.go` (a
multiply-referenced CTE is inlined when `Mtr == CTEMaterializeNever`; the
`InlineWith` replace walk is not memoized, so the binding is rebuilt at each
reference site).

Jira issue: CRDB-67034

Contributor guide

Open the contributing guide

Research direction

Start with CanInlineWith and InlineWith in pkg/sql/opt/norm/with_funcs.go, then run the provided EXPLAIN reproduction with nested NOT MATERIALIZED CTEs and compare it with the default-materialization control. Done means multiply-referenced CTE planning no longer grows without bound or causes an OOM while preserving the existing behavior for ordinary CTEs.

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
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.