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

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

Defect

File: src/backend/optimizer/util/tlist.c:812 Pattern: tlist_member(expr, tlist) inside foreach(lc, target->exprs) Complexity: O(|target_exprs| × |tlist|) per sort/group reference labeling pass Language: C

Description

tlist_member() is a linear scan through the target list. In tlist.c:812 it is called inside a foreach loop over target->exprs during sort and group reference labeling — a pass that annotates each expression in a subquery's target list with whether it appears in the output target list. For a query with a wide SELECT list and multiple sort/group columns, this is O(sort_keys × select_width), which degrades quadratically as queries widen.

This is a planning-time defect: triggered on every query that has ORDER BY, GROUP BY, or DISTINCT on a subquery with a wide target list.

Fix

Replace: tlist_member(expr, tlist) — O(n) linear scan With: Pre-build an expression → position hash map over tlist before entering the foreach loop; all membership checks become O(1). Data structure: HTAB * (PostgreSQL's built-in hash table) or a temporary palloc'd hash keyed on expression pointer identity (list_member_ptr semantics).

Work required

• Patch in defects/postgresql/patch/
• Unit test — asserts exact operation counts before/after (in defects/postgresql/unit/)
• Integration test (in defects/postgresql/integration/)
• Benchmark — before/after on query with SELECT width=10,50,100,200 columns + ORDER BY (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."