SQLite — CWE-407 Analysis
==========================

.. contents:: :local:

Overview
--------

SQLite is the most widely deployed database engine in the world, embedded in browsers,
mobile operating systems, and countless applications. Its query optimizer performs join
reordering, subquery flattening, and recursive CTE processing.

SQLite is implemented in C using array-backed list types (``ExprList``, ``SrcList``,
``IdList``) with O(n) membership functions: ``sqlite3ColumnIndex()`` (linear name scan
over table columns) and ``sqlite3IdListIndex()`` (linear name scan over an ``IdList``).

**Status: 2 confirmed defects — MEDIUM severity, all unpatched**

The main optimizer logic (``where.c``, the ``WhereLoop`` builder, join ordering) is clean:
it uses bitmask-backed ``Bitmask`` types for table and column tracking. The defects are
concentrated in DML support and join resolution paths.

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

.. list-table::
   :header-rows: 1
   :widths: 15 35 25 10 15

   * - ID
     - File:Line
     - Pattern
     - Complexity
     - Severity
   * - sqlite-0001
     - ``src/trigger.c:792``
     - ``sqlite3IdListIndex`` in ``checkColumnOverlap`` foreach SET cols
     - O(|SET| × |trigger_cols|)
     - MEDIUM
   * - sqlite-0002
     - ``src/select.c:575-617``
     - ``sqlite3ColumnIndex`` × 2 in NATURAL JOIN / USING loop
     - O(|USING| × |tables| × |cols|)
     - MEDIUM

Defect Detail — sqlite-0001
----------------------------

``checkColumnOverlap()`` in ``trigger.c`` determines whether an UPDATE's SET clause
touches any column in a trigger's column-list condition::

   for(e=0; e<pEList->nExpr; e++){
     if( sqlite3IdListIndex(pIdList, pEList->a[e].zEName)>=0 ) return 1;
   }

``sqlite3IdListIndex`` is a sequential string-comparison loop (O(|pIdList|)). The outer
``for`` loop is O(|pEList->nExpr|). Combined: O(|SET_cols| × |trigger_cols|).

This is called by ``triggersReallyExist()`` on **every INSERT, UPDATE, and DELETE**
to determine which triggers fire. For a table with W trigger-watched columns and an
UPDATE with S SET columns: O(S × W) string comparisons per DML statement.

**Fix:** Build a case-insensitive hash set over ``pIdList`` names before the loop;
O(1) per SET column. SQLite's ``Hash`` type (already used in the codebase) suffices.

Defect Detail — sqlite-0002
----------------------------

In ``addWhereTerm()`` / ``sqliteProcessJoin()`` for NATURAL JOIN and JOIN ... USING,
each USING column triggers::

   iRightCol = sqlite3ColumnIndex(pRightTab, zName);        /* O(right_cols) */
   tableAndColumnIndex(pSrc, 0, i, zName, &iLeft, &iLeftCol, ...);  /* O(tables × cols) */

Both calls are inside ``for(j=0; j<pList->nId; j++)`` over USING clause columns.
Combined: O(|USING_cols| × |tables| × |max_cols_per_table|).

For a NATURAL JOIN on two 50-column tables: O(50 × 2 × 50) = 5,000 string comparisons.
All comparisons use ``sqlite3StrICmp`` (case-insensitive string compare).

**Fix:** Pre-build a name → column-index hash map for each participating table before
the USING loop; O(1) lookup per column name.

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

The scanner returned 7 candidates from ``WalkExprList`` cross-matching — all false
positives:

- ``alter.c:938`` — sequential ``WalkExprList`` then separate loop (not nested)
- ``alter.c:1475`` — trigger step walker, no membership test, pure traversal
- ``select.c:7496`` — outer join table-function arg walker, no membership test
- ``select.c:7520`` — ``sqlite3CopySortOrder``: two equal-length lists, positional copy
- ``walker.c:110,173`` — ``sqlite3WalkExprList`` implementation itself (inner loop body)
- ``window.c:901`` — ``exprListAppendList``: copy with duplication, no membership test

Additional low-severity sites NOT promoted to defects:

- ``insert.c:1086`` — ``sqlite3ColumnIndex`` in INSERT column mapping: O(|cols|²) for
  INSERT with explicit column list, but bounded (schema width) and not hot.
- ``update.c:476`` — same pattern for UPDATE column mapping.
- ``build.c:1555`` — ``sqlite3ColumnIndex`` duplicate check in CREATE TABLE: O(N²)
  over N columns, but DDL cold path.

Optimizer Core — CLEAN
-----------------------

SQLite's ``where.c`` (the core join optimizer) is clean:

- Table membership: ``Bitmask`` — one bit per table index, O(1) bitwise AND
- Column tracking: ``Bitmask`` — same mechanism
- ``WhereLoop`` selection: cost-based, no list membership
- ``WITH RECURSIVE`` cycle detection: ``sqlite3_exec`` row-level deduplication via
  ephemeral table hash, not a list scan

The main optimizer avoids the defect pattern by design.

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

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

Strategy: Lead with ``sqlite3ExprListFind``, ``sqlite3IdListIndex``, and
``for(i<->nExpr/nSrc/nId)`` patterns; confirm loop context within ±20 lines.
Follow-up targeted search for ``sqlite3ColumnIndex`` and ``sqlite3IdListIndex``
call sites with outer loop context.

References
----------

* Tickets: sqlite-0001, sqlite-0002
* Scanner: ``tools/scans/sqlite.sh``
* SQLite List API: ``src/sqliteInt.h`` — ``ExprList``, ``SrcList``, ``IdList``
* SQLite Hash API: ``src/hash.h``, ``src/hash.c``