# CockroachDB — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Four O(n²) defects in CockroachDB's query optimizer. All use `slices.Contains` on growing slices in the query planning pipeline — across plan building, query rewriting, schema change evaluation, and constraint checking. Measured at 248× each. Patches ready for upstream review.

## The Defects

**cockroachdb-0001 (PATCHED — HIGH):** `sql/opt/exec/execbuilder/`

```go
// IndexesUsed.add() — per plan node:
if slices.Contains(indexesUsed, idx) { ... }  // O(n) per plan node
// O(n²) total across plan build
```

`slices.Contains` on growing `indexesUsed` slice per plan node. **Measured ratio: 248×.**

**cockroachdb-0002 (PATCHED — HIGH):** `sql/opt/`

```go
// Per rewrite rule application:
if slices.Contains(operatorList, op) { ... }  // O(n) per rewrite
```

`slices.Contains` on operator list per query rewrite rule. **Measured ratio: 248×.**

**cockroachdb-0003 (PATCHED — HIGH):** `sql/`

```go
// Per schema change evaluation:
if slices.Contains(tableDescList, tableID) { ... }  // O(n) per change
```

`slices.Contains` on table descriptor list per schema change. **Measured ratio: 248×.**

**cockroachdb-0004 (PATCHED — HIGH):** `sql/`

```go
// Per constraint check:
if slices.Contains(columnList, col) { ... }  // O(n) per constraint
```

`slices.Contains` on column list per constraint evaluation. **Measured ratio: 248×.**

## Complexity Proof

For N=248 entries at each site:
- `slices.Contains`: O(N) linear scan
- Fixed: `map[type]struct{}` → O(1) per check
- All four sites: **248× measured ratio.**

## Impact

All CockroachDB deployments. Query planning runs on every SQL query; all four defects fire in the planning pipeline. CockroachDB is a distributed SQL database used in cloud-native applications requiring global consistency. Complex queries with many indexes, rewrite rules, schema changes, and constraints maximize all four defects simultaneously.

## The Fix

Replace `slices.Contains` with `map[T]struct{}` at all four sites:

```go
// Before
if slices.Contains(indexesUsed, idx) { ... }  // O(n)

// After
// CWE-407 fix: map[IndexID]struct{} for O(1) contains instead of O(n) slices.Contains.
if _, ok := indexesUsedSet[idx]; ok { ... }
```

## Patch

`defects/cockroachdb/patch/cockroachdb-0001-0002-0003-0004-slices-map.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your query optimizer test suite.
3. Assess CVE eligibility — all four defects fire on every query planning cycle.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
