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

id	repo	severity	status	created
postgresql-0005	postgres/postgres	MEDIUM	DEFERRED	2026-03-23

Defect

File: src/backend/nodes/list.c:1077-1478 Pattern: list_union, list_intersect, list_difference — all O(n²) by construction Complexity: O(|a| × |b|) per call — foreach over list A with list_member check against list B Language: C

Description

PostgreSQL's list.c implements set operations over its List type via three functions:

• list_union(a, b) — appends elements of b not in a
• list_intersect(a, b) — elements of a that are in b
• list_difference(a, b) — elements of a that are not in b

Each is implemented as a foreach over one list with a list_member/list_member_ptr call for each element against the other list. This is O(|a| × |b|) — standard O(n²) set operation pattern.

These functions are called throughout the optimizer (path/, plan/, prep/) for clause deduplication, required column computation, and equivalence set operations. Individual call sites may not be hot, but the functions are utility-level and called frequently across the planner on complex queries.

MEDIUM severity because: (1) inputs are often small in practice (10s of elements), (2) not on the critical path of every query — only complex multi-table analytical queries, (3) fix requires touching every call site or at minimum the utility implementations.

The PG developers acknowledged this class of defect in execExpr.c:626 (dev comment: "risks O(N^2) behavior with many columns") and fixed it locally with bitmapset. The utility functions themselves were not updated.

Fix

For list_union/list_intersect/list_difference (by-pointer variants): Pre-build a hash set over the membership-check list before the iteration loop.

For oid/int/xid variants: Use Bitmapset (already available in PG) when the domain is bounded, or a hash set keyed on integer value for unbounded domains.

Callers: All call sites can remain unchanged if the utility functions are fixed.

Work required

• Patch in defects/postgresql/patch/
• Unit test — asserts exact operation counts for list_union/intersect/difference at n=100,500,1000 (in defects/postgresql/unit/)
• Integration test — query exercising clause deduplication with N columns (in defects/postgresql/integration/)
• Benchmark — list_union timing before/after at n=10,50,100,500 (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."