russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
57 lines
2.5 KiB
Markdown
57 lines
2.5 KiB
Markdown
---
|
||
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`
|