Stop locking plain reads. A transaction's first read takes a read view; every row it reads is the newest version that view may see, rebuilt from undo records when the row changed since. DELETE marks rows instead of removing them, and purge takes marks and old records away once no view is open.
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.
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:
name = d, made by transaction 9;name = c, made by transaction 8;name = b, made by transaction 7;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.
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.
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
At the first plain read, not at BEGIN.
Walk back until the change is one the view may see.
Marks, then removal when nobody can look.
These are the exact lines the tests check. The full definition is on the output contract page, section 87.
| Input | Output |
|---|---|
| a SELECT beside a writer's open transaction | its result, from the view, and no [LOCK] line |
btree dump of a leaf with a marked row | [BTREE] Cell <i>: key=<k> (<n> bytes) marked; free_space unchanged |
undo status while a view is open | oldest_view=<id of the transaction holding the oldest view>, purgeable=<the undo records of committed transactions whose change every open view sees> |
$droid --db v.dbWelcome 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>.exitexiting.. good bye!
rows_examined. Only rows handed up count.The page above is the same for every language. These are the only language-specific hints.
std::unordered_map<RowId, UndoRecord*>, with records in a std::deque so pointers stay valid as it grows.Vec and link them by index (Option<usize>), which avoids self-referencing structures.AutoHashMap(RowId, u32) of record indexes into an ArrayList(UndoRecord).