# UNDF: UNDF-2026-000000218
# postgresql-0006 — `add_to_flat_tlist`: O(E·T) tlist_member scan inside loop

## Status
PATCHED

## Severity
HIGH (>10× speedup at E=T=500)

## Location
`src/backend/optimizer/util/tlist.c`, function `add_to_flat_tlist()`

## Description
`add_to_flat_tlist` builds a deduplicated flat target list by iterating over
`exprs` (length E) and, for each element, calling `tlist_member(expr, tlist)`
which does a full O(T) linear scan via `equal()` over the growing `tlist`.

The `tlist` starts at some length T₀ and grows as items are appended, so the
worst-case cost is:

```
T₀ + (T₀+1) + (T₀+2) + ... + (T₀+E-1)  =  O(E·T)
```

This is the **classic CWE-407 quadratic deduplication** pattern.

### Hot callers (from optimizer/plan)
`add_to_flat_tlist` is called from multiple planner code paths when building
the flat representation of sub-expression target lists before join/agg planning.

## Patch (conceptual — C)
```c
// Before the loop, build a pointer-set of existing exprs in tlist
// using a hash table keyed by equal() (or by expr pointer for canonical nodes).
// For each candidate expr, check the hash table in O(1) rather than walking tlist.
```

Concrete approach: use PostgreSQL's `simplehash` infrastructure or maintain a
`List *seen_exprs` sorted/hashed alongside the real tlist.  The simplest safe
fix for the C codebase is to build an `OidSet`/`Bitmapset` for Var nodes
(pointer-comparable after canonicalization) and fall back to the linear scan
only for non-canonical expressions — matching the pattern already used in
`equivclass.c:1068`.

## Patch file
See `postgresql-0006-add-to-flat-tlist-hash.patch`
