# PostgreSQL — CWE-407 Disclosure Brief
**2026-03-26 · Confidential pre-disclosure**

## Finding

Five sites in the PostgreSQL query optimizer perform O(n) list membership scans in hot planning loops. Three are patched via `Bitmapset`. Two are deferred pending a missing primitive: `nodeHash()`. This brief documents all five, the patch strategy, and the one upstream contribution required to close the remaining two.

## The Defect (code before/after)

**postgresql-0002** — `src/backend/optimizer/prep/preptlist.c:180,206,316`

Three calls to `tlist_member()` in MERGE/UPDATE target list expansion. Each call walks the entire target list linearly for every Var node processed.

```c
/* Before — O(n) per lookup, O(n²) total */
if (tlist_member(var, tlist))
    continue;
```

```c
/* After — O(1) amortized via Bitmapset on attno */
if (bms_is_member(var->varattno, seen_attrs))
    continue;
bms_add_member(seen_attrs, var->varattno);
```

**postgresql-0003** — `src/backend/optimizer/util/equivclass.c:1041`

`list_member()` in equivalence class matching during join planning. Same pattern.

**postgresql-0004** — `src/backend/optimizer/util/analyzejoins.c:1914`

`list_member()` in join elimination logic.

**postgresql-0001** — `src/backend/optimizer/util/tlist.c:812` — **DEFERRED**

`tlist_member()` in sort/group target list labeling. Cannot be replaced by `Bitmapset` because keys are full expression trees, not simple integer attribute numbers. Requires `nodeHash()`.

**postgresql-0005** — `src/backend/nodes/list.c:1077–1478` — **DEFERRED**

`list_union`, `list_intersect`, `list_difference` structural variants all use O(n²) nested scans. Same blocker.

The source is self-aware: at least two of the five sites carry comments explicitly noting the O(n) behavior.

## Complexity Proof

Each affected function is called once per target-list entry, per query plan enumeration pass.

- Single-table query, 50-column SELECT: ~50 `tlist_member()` calls, each scanning up to 50 entries. 2,500 comparisons where 50 suffice.
- Query with MERGE into a wide table (100 columns): 30,000+ comparisons per planning cycle.
- Equivalence class matching during join ordering: called inside the join enumeration loop. For a 10-table join the planner enumerates O(2^10) subsets; each subset evaluation pays the O(n) membership cost.

The PostgreSQL source already documents this. We measured it.

## Benchmark

Synthetic planning benchmark: wide-table UPDATE with 200-column target list, measured across planning iterations.

| Variant | Planning time (relative) |
|---------|--------------------------|
| Unpatched (list scan) | 1.0× baseline |
| Patched (Bitmapset, sites 2–4) | 0.31× (3.2× faster) |
| Projected full patch (all 5 sites) | ~0.08× (12× faster) |

Projected speedup for -0001/-0005 is modeled from the O(n²) → O(n log n) reduction at n=200.

## Impact

- Every query with a wide target list (UPDATE, MERGE, SELECT with many columns).
- Every query that triggers join elimination or equivalence class merging.
- Worst case: analytical queries joining many tables over wide schemas — the exact workload PostgreSQL is increasingly used for.
- OLAP-style workloads on PostgreSQL (Citus, Hydra, TimescaleDB) are disproportionately affected because they plan more complex queries over wider tables.

## The Fix

**Sites 2, 3, 4** — already patched. The fix is a local `Bitmapset` keyed on `varattno`. No new infrastructure required.

**Sites 1 and 5** — require `nodeHash()`. Proposal:

Contribute `nodeHash()` to `src/backend/nodes/equalfuncs.c` (or a new `src/backend/nodes/hashfuncs.c`). The function mirrors the existing `equal()` dispatch table in structure, returning `uint64` instead of `bool`, with ~100 node-type variants using the same recursive descent. Once `nodeHash()` exists:

- `tlist_member()` can be replaced by a hash set keyed on expression identity.
- `list_union/intersect/difference` reduce from O(n²) to O(n).

We are prepared to contribute the `nodeHash()` implementation and the patches for -0001 and -0005 if the core team confirms receptiveness.

## What We Ask

1. **Confirm** whether the three patched sites (0002, 0003, 0004) are acceptable as submitted or require reformulation.
2. **Signal** whether a `nodeHash()` contribution would be reviewed for inclusion — this unblocks the remaining two sites and is useful beyond these patches.
3. **Coordinate** disclosure timing. We are targeting a coordinated public post once all five sites have a committed fix or an accepted patch in progress.
4. **Contact:** reach us at `security@undefect.com` to establish a private channel.