DELETE leaves an orphaned index entry when the entry's key no longer matches the row
- Dominant language
- C
- Stars
- 268
- Forks
- 18
- Avg merge
- 2h 26m
- Merged PRs (30d)
- 454
Description
Found while restoring `PRAGMA integrity_check`'s index-entry-count comparison (#2911, PR #2921).
When an index entry's key stops matching what the table row would produce, a later `DELETE` of that row leaves the entry behind. The orphan is unreachable through the index but physically present in the tree, so the table and the index disagree on entry count.
Reachable today only through `SQLITE_TESTCTRL_IMPOSTER`, which is how `expridx1.test` constructs it: a second schema is pointed at an existing index's root, rows are rewritten through that schema, and the rows are then deleted through the real table.
`expridx1` section 2, counts traced out of `sqlite3BtreeIntegrityCheck`:
```
after the imposter UPDATE: t1 = 1000, t1c = 1000 consistent
after deleting 500 rows: t1 = 500, t1c = 518 18 orphans
```
Stock SQLite ends consistent, which is why `expridx1-2.4` asserts `ok`. DoltLite keeps 18 entries whose rows are gone.
The delete computes the index key from the table row's current values. The imposter had rewritten those entries under different keys, so the seek finds nothing and the stale entry survives. Stock reaches a consistent end state from the same sequence.
This has always been true; it was invisible because the arm of `integrity_check` that compares per-tree entry counts was dead — `sqlite3BtreeIntegrityCheck` wrote zero into every `aCnt` slot, so `pragma.c`'s comparison was `0 == 0`. #2911 fixes that, which is what surfaced this.
`expridx1 expridx1-2.4` is gated in `test/known_testfixture_divergences.txt` as `class=engine-gap issue=` so PR #2921 can land; the gate should be removed when this is fixed.
Note `imposter1.test` passes clean, so the imposter facility itself works on this engine — the gap is specifically the orphaned entry left by a delete whose index key no longer matches.
## Why it matters beyond the test
The same shape — an index holding entries no table row accounts for — is what #2864, #2489, #2632 and #2644 all produced through engine bugs rather than through a test facility. `integrity_check` can now see that class, which is the point of #2911. Making the delete path tolerate a missing index entry without leaving the stale one behind would close the remaining gap.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with section 2 of test/expridx1.test and trace the DELETE path involved in the imposter UPDATE sequence, using sqlite3BtreeIntegrityCheck counts to observe the orphaned entries. The fix is complete when deleting rows no longer leaves stale index entries, expridx1-2.4 passes without the known-testfixture-divergences.txt gate, and integrity counts agree.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, sqlite
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100