Keeping Indexes True: DML, Rollback, Recovery

Why this stage exists

The previous stage built an index once, from the rows a table had at that moment. The next INSERT makes it wrong.

A wrong index is the worst kind of bug a database can have. It does not crash. It answers where name = 'bob' with no rows while bob sits in the table, or with a row that is no longer bob, and nothing tells you. A full scan would have been right. So the rule of this stage is absolute: after every statement, every index holds exactly one entry per row of its table, with that row's value and key. index check tests exactly that, and the tests run it after commits, rollbacks, failures and crashes.

What each statement does to an index

The last-but-one line is worth the care. An UPDATE that does not change an indexed column must not touch that index: not rewrite the entry in place, not even read its pages for writing. tx status counts the pages a transaction changed, and the tests use it to check.

Transactions and crashes come for free

There is no new recovery code in this stage. An index's nodes are pages, and the transaction machinery from Transactions and Recovery works on pages:

• ROLLBACK restores every page the transaction changed, index pages among them.
• A statement that fails halfway, for instance an INSERT whose index entry went in before the table said the key already exists, takes its pages back by the same rule.
• A crash loses the uncommitted pages and the log brings back the committed ones, index pages among them.

What the stage asks of you is to make sure every index write happens inside the statement, through the same pool and the same transaction as the table's write. An index written outside it, or after the commit, is the one recovery cannot fix.

Find every row, then change them

UPDATE and DELETE now find their rows through an index when their WHERE allows it. That opens an old trap. Take an index on name and:

update t set name = 'b' where name = 'a';

The scan walks the entries with value 'a'. Each UPDATE removes one and inserts an entry with value 'b'. If the scan and the writes are interleaved, the scan's position in the leaf can shift under it, or, with a range, the scan can meet the very entries the statement just wrote and update the same row again. IBM's System R team found this in 1976 with a query that gave everyone under a salary a raise and kept going until no one was under it; it is still called the Halloween problem.

The cure is to separate the two phases. Run the scan to the end and collect the keys of the rows it keeps. Then change each row by its key. The rows changed are those that matched when the statement began, each once. The contract makes this the rule for every UPDATE and DELETE, whatever its plan.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 55.

There is no new syntax and no new code.

What you should see when done

$droid --db shop.db
Welcome to droid!
>create table t (id int, name varchar(20), n int);
Create table statement executed successfully
>create index idx on t (name);
Create index statement executed successfully
>insert into t (id, name, n) values (1, 'ada', 3);
Insert statement executed successfully (1 rows)
>insert into t (id, name, n) values (2, 'bob', 5);
Insert statement executed successfully (1 rows)
>update t set name = 'zed' where id = 2;
Update statement executed successfully (1 rows)
[EXEC] rows_examined=1
>select id from t where name = 'bob';
id
(0 rows)
[EXEC] rows_examined=0 index_lookups=0
>begin;
Begin statement executed successfully
>delete from t where name = 'zed';
Delete statement executed successfully (1 rows)
[EXEC] rows_examined=1 index_lookups=1
>rollback;
Rollback statement executed successfully
>select id from t where name = 'zed';
id
2
(1 rows)
[EXEC] rows_examined=1 index_lookups=1
>index check idx
[INDEX] Check idx: OK entries=2
>.exit
exiting.. good bye!

Common bugs in this stage

• Removing the old entry by value alone. With duplicates, that removes someone else's entry. Remove the exact entry: value and key.
• Reading the old value after writing the new row. UPDATE needs the old value to find the old entry. Read the row before you change it.
• Writing the index for every UPDATE. It works, and tx status shows the extra pages. Touch only the indexes whose column the statement assigns and whose value really changes.
• Adding the entry before the checks. An INSERT that then fails on a duplicate key leaves a ghost entry unless the statement's pages are taken back. Check first, or make sure the failure path restores every page.
• Scanning and writing at the same time. Collect the keys, then change the rows.
• An index updated outside the transaction. ROLLBACK and recovery restore what went through the pool and the log, nothing else.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: collecting keys needs a growable array of 32-bit keys; a realloc-doubling buffer is enough.
• C++: collect into a std::vector<uint32_t> before the write loop.
• Rust: collecting the keys first also satisfies the borrow checker, which would refuse a mutable write to the tree while an iterator borrows it.
• Zig: an std.ArrayList(u32) with the statement's allocator, freed when the statement ends.