---
id: sqlite-0001
repo: sqlite/sqlite
severity: MEDIUM
status: PATCHED
created: 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`