java-topology/tools/tickets/defects/sqlite-0002.md

id	repo	severity	status	created
sqlite-0002	sqlite/sqlite	MEDIUM	NOT-A-DEFECT	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