PostgreSQL — CWE-407 Analysis
==============================

.. contents:: :local:

Overview
--------

PostgreSQL's query planner is a cost-based optimizer that performs join ordering,
equivalence class reasoning, target list construction, and join elimination. The
planner is implemented in C and uses PostgreSQL's own ``List`` type (a singly-linked
list of ``void *`` cells) with O(n) membership functions: ``list_member()``,
``list_member_ptr()``, ``list_member_int()``, ``list_member_oid()``, and
``list_member_xid()``.

**Status: 5 confirmed defects — all unpatched**

The scanner used pg-specific patterns (``list_member*`` membership tests, ``foreach``
loop macro) rather than generic C patterns. 58 candidates were identified; 5 confirmed
as true CWE-407 defects in hot planner paths. PostgreSQL developers independently
acknowledged the O(n²) risk in ``execExpr.c:626`` (patched locally with bitmapset)
— confirming the pattern is real and known to the project.

Confirmed Defects
-----------------

.. list-table::
   :header-rows: 1
   :widths: 15 35 20 15 15

   * - ID
     - File:Line
     - Pattern
     - Complexity
     - Severity
   * - postgresql-0001
     - ``optimizer/util/tlist.c:812``
     - ``tlist_member`` in sort/group labeling foreach
     - O(sort_keys × width)
     - HIGH
   * - postgresql-0002
     - ``optimizer/prep/preptlist.c:180,206,316``
     - ``tlist_member`` in MERGE/UPDATE target dedup (3 loops)
     - O(W² × C²) for MERGE
     - HIGH
   * - postgresql-0003
     - ``optimizer/path/equivclass.c:1041``
     - ``list_member`` in equivalence class var matching
     - O(M × E) per class
     - HIGH
   * - postgresql-0004
     - ``optimizer/util/analyzejoins.c:1914``
     - ``list_member`` in join elimination expr merge
     - O(E²) per eliminated join
     - HIGH
   * - postgresql-0005
     - ``nodes/list.c:1077-1478``
     - ``list_union``, ``list_intersect``, ``list_difference``
     - O(|a| × |b|) per call
     - MEDIUM

Developer Acknowledgment
------------------------

A PostgreSQL developer commented in ``execExpr.c:626``::

   /* Using list_member_int() tests, but that risks O(N^2) behavior with many columns */

That site was subsequently patched with ``bitmapset``. The five sites above were not
caught in the same pass — confirming they are unaddressed.

Threat Model
------------

All five defects are triggered at **planning time** — before execution begins. For
OLTP queries the planner is amortized over many executions via plan caching. For
ad-hoc analytical queries, uncached plans are regenerated on every execution.

Worst-case scenarios:

- **MERGE with many WHEN clauses** (postgresql-0002): PostgreSQL 15+ feature, upsert-heavy
  workloads. W=50 WHEN clauses × C=20 columns → O(W²×C²) ≈ 10⁶ membership tests per plan.
- **Star schema with many equivalence members** (postgresql-0003): analytical databases
  with wide dimension tables. K equivalence classes × M=20 members × E=20 exprvars → O(K×400).
- **Views with many columns + self-join** (postgresql-0004): joins against wide views
  trigger join elimination on every query. E=50 projected columns → 2,500 list_member calls.

Fix Pattern
-----------

All five defects follow the same fix pattern:

1. Before the ``foreach`` loop, build an O(1) membership structure:

   - For Var nodes: ``Bitmapset *`` keyed on ``varattno`` (already used by PG)
   - For expression pointer identity: pointer-identity hash set (palloc'd)
   - For int/oid/xid variants: ``Bitmapset *`` or integer hash set

2. Replace ``list_member*(list, item)`` in the loop body with O(1) set lookup.

3. Free the temporary structure after the loop (palloc memory is freed with context).

PostgreSQL already has ``bitmapset.h`` and ``HTAB`` (hash table) as first-class
utilities — no new dependencies required.

False Positives Triaged
-----------------------

53 of 58 scanner candidates were false positives:

- **``execExpr.c:626``** — already patched by PG developers with bitmapset (O(1) check)
- **``nodeHashjoin.c``**, **``nodeNestloop.c``** — list traversal is the join execution
  itself, not a membership test inside traversal
- **``ruleutils.c``**, **``deparse.c``** — display/deparse code, cold path
- **``pg_dump``** — dump utility, not query planner, not performance-critical
- Remaining 48 candidates — bounded input (typically < 10 elements) or genuinely cold paths

Scan Details
------------

Scanner: ``tools/scans/postgresql.sh``

Strategy: Lead with ``list_member*`` call sites, confirm ``foreach`` loop context
within ±20 lines. Inverted from generic C scanner because PG uses its own list API
(``foreach``/``lfirst``) rather than ``std::find`` or ``.count()``.

Directories scanned:

- ``src/backend/optimizer`` — query planner
- ``src/backend/nodes`` — node utilities including ``list.c``
- ``src/backend/rewrite`` — rule rewriter
- ``src/backend/executor`` — execution engine
- ``src/backend/parser`` — SQL parser
- ``src/backend/planner`` — (alias for optimizer in older PG layouts)

References
----------

* Tickets: postgresql-0001 through postgresql-0005
* Scanner: ``tools/scans/postgresql.sh``
* Developer acknowledgment: ``execExpr.c:626`` comment (bitmapset fix)
* PostgreSQL List API: ``src/include/nodes/pg_list.h``