java-topology/tools/tickets/defects/postgresql-0002.md

id	repo	severity	status	created
postgresql-0002	postgres/postgres	HIGH	DEFERRED	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."