russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
1.9 KiB
| id | repo | severity | status | created |
|---|---|---|---|---|
| sqlite-0001 | sqlite/sqlite | MEDIUM | PATCHED | 2026-03-23 |
Defect
File: src/trigger.c:792 (checkColumnOverlap)
Pattern: sqlite3IdListIndex(pIdList, pEList->a[e].zEName) inside for(e=0; e<pEList->nExpr; e++)
Complexity: O(|SET_cols| × |trigger_cols|) per DML trigger check
Language: C
Description
checkColumnOverlap determines whether any column in an UPDATE's SET clause (pEList)
matches any column listed in a trigger's WHEN-columns list (pIdList). It does this
by looping over each column in the SET clause and calling sqlite3IdListIndex() — a
linear scan through the IdList — for each one.
sqlite3IdListIndex is a sequential name-comparison loop (O(|pIdList|)). The outer
for loop is O(|pEList->nExpr|). Combined: O(|SET_cols| × |trigger_cols|).
This function is called by triggersReallyExist() which runs 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, each DML statement triggers O(S × W) comparisons.
At S=W=50 (wide table with a full-column UPDATE trigger), this is 2,500 string comparisons
per DML statement.
Fix
Replace: Linear scan via sqlite3IdListIndex for each SET column
With: Build a case-insensitive hash set over pIdList->a[i].zName before the loop;
check O(1) per SET column via hash lookup.
Data structure: SQLite's sqlite3HashInsert/sqlite3HashFind (already used in the
codebase) keyed on column name string.
Work required
- Patch in
defects/sqlite/patch/ - Unit test — asserts exact comparison counts before/after (in
defects/sqlite/unit/) - Integration test — UPDATE on table with W=10,20,50 trigger-watched columns (in
defects/sqlite/integration/) - Benchmark — timing before/after on 10,000 UPDATE statements (in
defects/sqlite/bench/) - White paper section —
whitepaper/vectors/database/sqlite.rst