---
id: sqlite-0002
repo: sqlite/sqlite
severity: MEDIUM
status: NOT-A-DEFECT
created: 2026-03-23
---

## Defect

**File:** `src/select.c:575-617` (NATURAL JOIN / USING clause processing)
**Pattern:** `sqlite3ColumnIndex(pRightTab, zName)` + `tableAndColumnIndex(pSrc, ...)` inside `for(j=0; j<pList->nId; j++)`
**Complexity:** O(|USING_cols| × |tables| × |table_cols|) during join resolution

## VERDICT: NOT A DEFECT (2026-03-23)

`sqlite3ColumnIndex` already has a hash-based fast path via `pTab->aHx`:
- Uses `sqlite3StrIHash(zCol)` to index into `pTab->aHx`
- O(1) for most columns (lucky match on first probe)
- Full linear scan only on hash collision
Complexity is O(|USING_cols| × |tables|) × O(1) — not O(n²) with large table_cols.
The `IdList`-based `sqlite3IdListIndex` (used in sqlite-0001) lacks this optimization.
**Language:** C

## Description

During NATURAL JOIN and JOIN ... USING processing, SQLite builds equijoin conditions
for each column in the USING clause. For each USING column `zName`, it calls:

1. `sqlite3ColumnIndex(pRightTab, zName)` — O(|right_table_cols|) linear scan
2. `tableAndColumnIndex(pSrc, ...)` — which itself loops over source tables calling
   `sqlite3ColumnIndex` for each → O(|left_tables| × |table_cols|)

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

For a wide-table NATURAL JOIN (e.g., two tables with 50 shared columns on a 10-table
star schema), this is O(50 × 10 × 50) = 25,000 column comparisons — all string-based.
Runs every time the query is planned.

`sqlite3ColumnIndex` uses sequential string comparison with `sqlite3StrICmp`. The IdList
USING column list has the same structure and the same O(n) lookup.

## Fix

**Replace:** `sqlite3ColumnIndex` calls inside USING loop
**With:** Pre-build a name → column_index hash map for each participating table before
iterating USING columns. O(1) lookup per USING column per table.
**Scope:** Localized to the `addWhereTerm()` / `sqliteProcessJoin()` functions in `select.c`.

## Work required

- [ ] Patch in `defects/sqlite/patch/`
- [ ] Unit test — asserts exact comparison counts for NATURAL JOIN with N=5,10,20,50 shared columns (in `defects/sqlite/unit/`)
- [ ] Integration test — NATURAL JOIN on tables with N shared columns (in `defects/sqlite/integration/`)
- [ ] Benchmark — EXPLAIN QUERY PLAN timing, planning phase (in `defects/sqlite/bench/`)
- [ ] White paper section — `whitepaper/vectors/database/sqlite.rst`