Secondary Indexes Under Versions

Why this stage exists

Read views rebuild old rows from undo, but they reach rows through the table's key. A secondary index is a second tree, keyed by value. Move a person from city a to city b, and the index on city loses (a, 1) and gains (b, 1). A reader whose view predates the move asks for city a: the entry is gone, so the index says nobody lives there, while the same reader's full scan finds person 1 in a. Two plans, two answers.

Entries have no version

One fix is to put versions in the index: each entry carrying the transactions that created and deleted it. Then every index write must also maintain those versions, every index grows with old values, and every update writes all of them. InnoDB does not do this, and neither does this engine.

Instead, an entry stays just a value and a key, and the index keeps old entries around, marked, the way the table keeps deleted rows:

After the move, the index holds (a, 1) marked and (b, 1). Both point at row 1.

Every hit is checked

Because entries carry no version, an entry is only a candidate. For each entry in range, marked or not, the reader rebuilds the version of the row it may see, and keeps the row only if that version's value is the entry's value:

So the old view finds person 1 in a and nobody in b, and a new view the opposite, and each row is handed up at most once, since its visible version has one value.

An index-only scan answers from the index without reading the table. That is only safe when the entry cannot be newer than the reader: it is not marked and the row has no kept undo record, so every view sees the same thing. Otherwise the scan reads the row like any index scan.

A unique index checks values the same way: a value is taken by an entry that is not marked, or by a marked one whose marking transaction is another transaction that has not committed. A transaction's own deletion frees the value for its own INSERT. Delete a row and insert its unique value again, with an old view still open, and the insert is accepted: the old entry is marked by a committed delete.

Output contract for this stage

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

What you should see when done

$droid --db m.db
Welcome to droid!
>create table people (id int primary key, city varchar(20));
Create table statement executed successfully
>insert into people (id, city) values (1, 'a');
Insert statement executed successfully (1 rows)
>create index by_city on people (city);
Create index statement executed successfully
>@1 begin;
@1| Begin statement executed successfully
>@1 select * from people where city = 'a';
@1| id | city
@1| 1 | a
@1| (1 rows)
@1| [EXEC] rows_examined=1 index_lookups=0
>@2 update people set city = 'b' where id = 1;
@2| Update statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
>@1 select * from people where city = 'b';
@1| id | city
@1| (0 rows)
@1| [EXEC] rows_examined=0 index_lookups=0
>index check by_city
[INDEX] Check by_city: OK entries=2
>.exit
exiting.. good bye!

Common bugs in this stage

• Removing the old entry on UPDATE. An old view can no longer find the row by its old value.
• Trusting a hit. Rebuild the row and compare its value with the entry's.
• Handing a row up twice when both its old and new entries are in range. The value check keeps one.
• Counting a marked entry as taken in a unique index after its delete committed.
• Index-only answers from a marked entry. Read the table.

Language notes

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

• C: reuse the slot-length bit helper from read views for index leaves; the entry's value bytes are compared with memcmp against the rebuilt row's column.
• C++: a bool marked() accessor on the index cell type keeps the bit twiddling in one place.
• Rust: give the index cursor an iterator adapter that yields candidates and a second that filters them by the rebuilt version.
• Zig: the same filter as an inline function over the cursor's next(), returning null for rejected entries.