java-topology/whitepaper/outreach/postgres.md

PostgreSQL — CWE-407 Disclosure Brief (postgres-0001)

2026-04-13 · Patch available — awaiting upstream merge

Finding

O(V²) visited-set membership test in typeInheritsFrom() where list_member_oid() performs a linear scan over the visited list for every type in the inheritance hierarchy during type resolution.

The Defect

postgres-0001 (PATCHED — MEDIUM): src/backend/catalog/pg_inherits.c:443

// Inside inheritance hierarchy traversal:
if (list_member_oid(visited, this_relid))
    continue;
visited = lappend_oid(visited, this_relid);

list_member_oid() is O(V) where V = visited OIDs. For deep or wide inheritance hierarchies, the total traversal cost is O(V²) instead of O(V).

Complexity Proof

At V=100 types in the hierarchy:

• Defective: 100 × 50 (avg) = 5,000 OID comparisons
• Fixed: 100 hash insertions + 100 hash lookups = 200 operations
• ~25× op reduction. Scales worse with deeper hierarchies.

Impact

PostgreSQL type inheritance resolution fires during query planning for tables using inheritance. Complex schemas with deep or wide inheritance trees (common in partitioned table setups) trigger typeInheritsFrom() during type checking. The quadratic cost compounds during query compilation for queries touching many partitioned tables.

The Fix

Replace the List visited tracker with a HTAB (PostgreSQL's built-in hash table):

// Before — O(V) list scan:
if (list_member_oid(visited, this_relid))
    continue;
visited = lappend_oid(visited, this_relid);

// After — O(1) hash lookup:
hash_search(visited_set, &this_relid, HASH_ENTER, &found);
if (found)
    continue;

Uses PostgreSQL's native hash_create / hash_search / hash_destroy API, consistent with existing catalog code patterns.

Patch

Fix available: defects/postgres/patch/postgres-0001-type-inherits-from-htab.patch

Single-file patch in pg_inherits.c.

What We Ask

A patch is ready for review.

1. Confirm receipt via the PostgreSQL security mailing list or Commitfest.
2. Assess severity — fires during type resolution in inheritance hierarchies.
3. Coordinate a disclosure date — we target 90 days from first contact.
4. We will credit the PostgreSQL team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.