---
id: postgresql-0002
repo: postgres/postgres
severity: HIGH
status: DEFERRED
created: 2026-03-23
---

## Defect

**File:** `src/backend/optimizer/prep/preptlist.c:180,206,316`
**Pattern:** `tlist_member(var, tlist)` inside `foreach(l, vars)` / `foreach(l2, vars)`
**Complexity:** O(|vars|² × |tlist|) per target list merge in MERGE/UPDATE planning
**Language:** C

## Description

`preptlist.c` builds and deduplicates the target list for MERGE, UPDATE, and similar
DML statements. Lines 180 and 206 call `tlist_member()` inside separate `foreach`
loops over the variable list `vars`; line 316 does the same in a third loop. Each
call is O(|tlist|); the outer loop iterates O(|vars|) times; and for MERGE statements
with many WHEN clauses, `vars` grows with the number of MERGE actions.

For a MERGE with W WHEN clauses each touching C columns, the target list contains O(W×C)
entries and the deduplication is O(W²×C²) — fully quadratic in both dimensions.

MERGE was added in PostgreSQL 15 (2022) and is an actively used feature for upsert-heavy
workloads. This defect hits every MERGE planning pass.

## Fix

**Replace:** `tlist_member(var, tlist)` — O(n) linear scan repeated in loop
**With:** Build a hash set of already-added vars before each loop; check O(1) per var.
**Data structure:** `Bitmapset *` keyed on `var->varattno` suffices for Var nodes;
general expressions need pointer-identity hash.

## Work required

- [ ] Patch in `defects/postgresql/patch/`
- [ ] Unit test — asserts exact operation counts before/after (in `defects/postgresql/unit/`)
- [ ] Integration test — MERGE with W=5,10,20,50 WHEN clauses × C=10 columns (in `defects/postgresql/integration/`)
- [ ] Benchmark — EXPLAIN ANALYZE timing, planning time only (in `defects/postgresql/bench/`)
- [ ] White paper section — `whitepaper/vectors/database/postgresql.rst`

## DEFERRED (2026-03-23)

PostgreSQL uses structural deep equality (`equal()`) for expression comparison.
No generic expression hash function exists in PostgreSQL core. A correct fix
requires either: (a) a structural hash based on Node type+fields, or (b) sort+merge
using a total order on Expr* — neither is available without significant framework
additions. PostgreSQL developers explicitly note the O(n²) cost in comments and
say "really you should be using some other data structure."