# 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`

```c
// 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):

```c
// 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.