Reading Without Waiting

Why this stage exists

With locks, a report that sums every account takes S on the whole table, and waits behind every transfer that holds X on a row. Worse, every transfer waits behind the report. Readers and writers queue for each other, though a reader changes nothing.

InnoDB's answer, and this stage's: a plain read takes no locks. It reads the database as it was at a fixed moment, rebuilding any row that changed since from the undo records that already exist for rollback. Writers still lock each other; readers never wait and are never waited for.

Versions

The row in the tree is the newest version. Each undo record of that row holds the version before one change, and says which transaction made the change. So the newest version and the row's records, newest first, are its whole history:

• in the tree: name = d, made by transaction 9;
• undo record: name = c, made by transaction 8;
• undo record: name = b, made by transaction 7;
• undo record: name = ann, made by transaction 3.

A reader walks this chain from the newest version until it reaches one it is allowed to see. These records live in memory, beside the undo records of the transaction that made them, found by table and key. InnoDB keeps the same pointer inside every row as two hidden columns; keeping it outside the row means the row format does not change, and after a restart no view can be open, so nothing is lost.

The read view

What a reader may see is fixed by its read view, taken by its first plain read, not by BEGIN: a transaction that begins and waits a minute before reading sees what was committed during that minute. The view holds two things: the id the next transaction would get, and the ids of the transactions open at that moment.

A change made by transaction t is visible to the view if t is the reader itself, or if t had committed when the view was taken: its id is below the view's next id, and it was not in the open list.

The open list is what simpler rules forget. Transaction 4 began before the view and is still running when it is taken; it commits a moment later. Its id is small, but its change was not committed at the view's moment, so the reader must never see it, before or after that commit.

A transaction keeps its view until it ends, so it reads the same thing every time: this is REPEATABLE READ, the default. The next stage adds other levels.

Deletes become marks

If a DELETE took the row out of its leaf, an old reader scanning the leaf would never meet it, and could not walk back to the version it should see. So a DELETE now only marks the row: bit 15 of the length in its slot. The row keeps its bytes and its slot, and its leaf keeps the space. A reader that sees the delete skips it; one that does not reads the version before it.

Marks and kept records must go some time. When a transaction ends and no view is open anywhere, nobody can need any old version: every committed record is dropped, and every row a committed transaction marked is taken out of its leaf as a DELETE took it out before, merges included. With one session that happens at every COMMIT, so a lone session sees exactly what it saw before this stage. With a view open they stay; the purge stage deals with what a long view holds back.

A marked row still holds its key. An INSERT of that key, once the deleting transaction has committed, replaces the marked row; while the delete is uncommitted, the INSERT waits for its row lock as before.

>@1 begin;
@1| Begin statement executed successfully
>@1 select count(*) from users;
@1| COUNT(*)
@1| 2
@1| (1 rows)
@1| [EXEC] rows_examined=2
>@2 delete from users where id = 6;
@2| Delete statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
>btree dump 2
[BTREE] Page 2: type=LEAF num_cells=2 free_space=4028
[BTREE]   Cell 0: key=5 (16 bytes)
[BTREE]   Cell 1: key=6 (16 bytes) marked
>undo status
[UNDO] records=1 pages=0 oldest_view=4 purgeable=0

Output contract for this stage

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

What you should see when done

$droid --db v.db
Welcome to droid!
>create table users (id int primary key, name varchar(20));
Create table statement executed successfully
>insert into users (id, name) values (5, 'ann');
Insert statement executed successfully (1 rows)
>@1 begin;
@1| Begin statement executed successfully
>@1 select name from users where id = 5;
@1| name
@1| ann
@1| (1 rows)
@1| [EXEC] rows_examined=1
>@2 begin;
@2| Begin statement executed successfully
>@2 update users set name = 'bea' where id = 5;
@2| Update statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
>@1 select name from users where id = 5;
@1| name
@1| ann
@1| (1 rows)
@1| [EXEC] rows_examined=1
>@2 commit;
@2| Commit statement executed successfully
>@1 select name from users where id = 5;
@1| name
@1| ann
@1| (1 rows)
@1| [EXEC] rows_examined=1
>@3 select name from users where id = 5;
@3| name
@3| bea
@3| (1 rows)
@3| [EXEC] rows_examined=1
>.exit
exiting.. good bye!

Common bugs in this stage

• Taking the view at BEGIN. The first read takes it.
• Comparing ids only. A transaction open when the view was taken is invisible whatever its id.
• Dropping undo records at COMMIT. A view may still need them.
• Removing the row on DELETE. An old reader can no longer find it; mark it.
• Counting rows the view does not see in rows_examined. Only rows handed up count.
• Locking plain reads. UPDATE and DELETE still lock, and act on the newest rows; SELECT does not.

Language notes

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

• C: a hash table from (table id, key) to the newest undo record of that row, each record pointing at the next older one of the same row.
• C++: std::unordered_map<RowId, UndoRecord*>, with records in a std::deque so pointers stay valid as it grows.
• Rust: keep records in a Vec and link them by index (Option<usize>), which avoids self-referencing structures.
• Zig: an AutoHashMap(RowId, u32) of record indexes into an ArrayList(UndoRecord).