dolthub / dolthub/doltlite

DELETE leaves an orphaned index entry when the entry's key no longer matches the row

Closed
#2,922 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 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.