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

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

Defect

File: src/backend/optimizer/path/equivclass.c:1041 Pattern: list_member(exprvars, lfirst(lc2)) inside foreach(lc2, emvars) Complexity: O(|emvars| × |exprvars|) per equivalence class membership test during planning Language: C

Description

The equivalence class machinery (equivclass.c) matches expression variables against the set of variables referenced in equivalence member expressions during query planning. At line 1041, list_member() — a linear scan — is called inside foreach(lc2, emvars) to check whether a given variable appears in exprvars.

Equivalence classes are built and queried for every join predicate, index condition, and ORDER BY clause. On a query with K equivalence classes each containing M members and referencing E expression variables, this inner check is O(M × E) per class, and the outer planning loop iterates over all relevant equivalence classes. Large analytical queries with many join predicates trigger this on every path enumeration.

PostgreSQL developers acknowledged the pattern elsewhere (see execExpr.c:626 dev comment: "risks O(N^2) behavior") and patched it there with bitmapset. This site was not caught in that fix.

Fix

Replace: list_member(exprvars, lfirst(lc2)) — O(n) per test With: Pre-build a Bitmapset over exprvars (keyed by var index) before the foreach(lc2, emvars) loop; all membership checks become O(1).

Work required

• Patch in defects/postgresql/patch/
• Unit test — asserts exact operation counts before/after (in defects/postgresql/unit/)
• Integration test — query with N=5,10,20,50 join predicates all in same equivalence class (in defects/postgresql/integration/)
• Benchmark — EXPLAIN ANALYZE planning time on star-schema query (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."