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

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

Defect

File: src/backend/optimizer/util/analyzejoins.c:1914 Pattern: list_member(toKeep->reltarget->exprs, node) inside foreach(lc, toRemove->reltarget->exprs) Complexity: O(|toRemove.exprs|² × |toKeep.exprs|) per join elimination pass Language: C

Description

analyzejoins.c implements join elimination — removing redundant joins from the query plan when the optimizer can prove the join does not affect the result set. During join relation merging, line 1914 calls list_member() inside foreach(lc, toRemove->reltarget->exprs) to check whether each expression from the removed relation already exists in the kept relation's target list.

Join elimination runs on every query that has self-joins, redundant outer joins, or joins to views. For a query that eliminates a join between relations with E expressions each, this is O(E²). Since reltarget->exprs contains all expressions needed from that relation (not just the join key), complex queries with many projected columns trigger quadratic behavior.

Fix

Replace: list_member(toKeep->reltarget->exprs, node) — O(n) per check With: Pre-build a pointer-identity hash set over toKeep->reltarget->exprs before the foreach loop; check O(1) per expression. Data structure: Simple array-backed hash set over Node * pointers; palloc'd for the duration of the join elimination pass.

Work required

• Patch in defects/postgresql/patch/
• Unit test — asserts exact operation counts before/after (in defects/postgresql/unit/)
• Integration test — query with self-join on table with C=5,10,20,50 projected columns (in defects/postgresql/integration/)
• Benchmark — EXPLAIN ANALYZE planning time, join elimination enabled vs disabled (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."