dolthub / dolthub/doltlite

A NOCASE index costs a full index scan at plan time on every prepare while edits are pending

Closed
#2,917 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
268
Forks
18
Avg merge
2h 26m
Merged PRs (30d)
454

Description

Found in a full-repo review at `0ba280f06f`.

While any edit is pending on a table, every `prepare` of a statement that considers a NOCASE index pays a full scan of that index. The cost is linear in table size and is pure planning overhead — both engines pick the same plan.

## Measured

Inside `BEGIN`, one `UPDATE` to the indexed column, then 100 index-equality `SELECT`s, whole-process wall time (the ~30 ms floor is process startup, visible in the two control columns):

| rows | DoltLite, NOCASE index | DoltLite, BINARY index | stock, NOCASE index |
|---|---|---|---|
| 50,000 | 130.0 ms | 32.6 ms | 31.2 ms |
| 200,000 | 428.6 ms | 44.6 ms | 28.8 ms |

Net of startup that is roughly **1.0 ms per statement at 50k rows and 4.0 ms at 200k** — 4x the rows, 4x the cost — while the BINARY index and stock stay flat. Only NOCASE indexes are affected; there is an early-out for every other collation.

## Cause

`src/where.c:4146-4163` runs inside the per-candidate-index loop of `whereLoopAddBtree`, so it fires on every index on every planning pass:

```c
if( !pProbe->bNocaseNul
&& iDb>=0 && iDbnDb && db->aDb[iDb].pBt
&& !sqlite3BtreeUsesOrig(db->aDb[iDb].pBt) ){
rc = sqlite3BtreeProllyIndexHasNocaseNul(
db->aDb[iDb].pBt, pProbe->tnum, pProbe->nKeyCol,
pProbe->azColl, &hasNocaseNul);
```

`sqlite3BtreeProllyIndexHasNocaseNul` (`src/prolly_btree.c:62`) answers by scanning the index, and its memo is disabled whenever the index has any uncommitted edit (`src/prolly_btree.c:89-90`):

```c
pMap = (ProllyMutMap*)pTE->pPending;
cacheable = !pMap || prollyMutMapIsEmpty(pMap);
if( cacheable && pTE->nocaseNulState
&& prollyHashCompare(&pTE->nocaseNulRoot, &pTE->root)==0 ){
```

So a transaction that writes once and then reads many times — an extremely ordinary shape — rescans the whole index per prepared statement.

## Fix

Determine `bNocaseNul` incrementally at write time: a sticky per-table flag set when a NOCASE key containing a NUL byte is inserted, cleared only on a rebuild. That removes the scan from the planning path entirely. Failing that, keep the memo valid across pending edits by consulting only the pending map (which the function already walks separately) rather than invalidating the whole answer.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start in src/where.c:4146-4163 and src/prolly_btree.c:62, tracing how pending edits and the NOCASE state are maintained through write paths. Determine how to avoid repeated full index scans without missing NOCASE keys containing NUL bytes, then verify that repeated prepares after an uncommitted edit no longer scale with index size while query plans remain correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, sqlite
Domain
databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.