russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
52 lines
2.3 KiB
Markdown
52 lines
2.3 KiB
Markdown
---
|
||
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."
|