droidPart 8 · Sessions and Concurrency

Sessions and Concurrency · Stage 2

Row-Level Undo

Replace page copies with one undo record per row change: the key for an INSERT, the old row for an UPDATE or a DELETE. ROLLBACK applies them newest first, by key, wherever the row is now; splits and merges are never undone, and pages a DROP frees wait for the commit.

Not run yet · 7 tests

Why this stage exists

Since Transactions and Recovery, ROLLBACK has put back copies of the pages a transaction changed, taken at BEGIN. With one transaction at a time that is exactly right, and it is the simplest way to teach what undo is.

With two sessions it breaks on the first shared page. Session 1 inserts row 1 into a leaf; session 2 inserts row 2 into the same leaf; session 1 rolls back:

@1 begin: copy of the leaf taken (empty)

header

cells = 0

free space

@1 inserts 1, @2 inserts 2

header

cells = 2

cell 0

key = 1

new

cell 1

key = 2

new

free space

@1 rollback with page copies: the empty copy comes back

header

cells = 0

free space

@1 rollback with undo records: delete key 1

header

cells = 1

cell 0

key = 2

free space

Each cell is 25 bytes. A cell that moves one position moves by 25 bytes.

The page copy predates session 2's row, so putting it back erases a change that was not session 1's to take back.

The page copy was taken before session 2's row existed, so putting it back erases session 2's insert. The fix is to stop thinking in pages: session 1 changed one row, and taking back that one row is all its rollback should do.

One record per row change

Every time a transaction changes a row, it first writes down how to take that change back:

Change	Undo record	Taking it back
INSERT	the table and the key	delete the row with that key
UPDATE	the table, the key, the row as it was	put that row back
DELETE	the table, the row as it was	insert it again

ROLLBACK walks the transaction's records from the newest to the oldest. Newest first matters: a row updated three times is put back three times, each time to the value before the change, ending at the original. Applied oldest first, the last thing written would be the newest record's old value: the value before the last update, not the original.

Each record is applied the way the opposite statement would run: through the tree, by key, wherever the row lives now. Indexes follow, as they follow any INSERT, UPDATE or DELETE, so a rolled-back DELETE is found through its secondary index again. An UPDATE that grew a row into overflow pages is put back by an UPDATE to the old, short row, which frees the chain.

The tree's shape is not undone

A transaction that inserted 40 wide rows split leaves and allocated pages. Its rollback deletes those 40 keys: some leaves merge and their pages go to the free list, others may stay. The rows are exactly what they were, and the tree keeps every invariant, but it may have more pages than before, and pager status and db freelist may show it.

That is not a flaw. Between the insert and the rollback, another session may have added rows to those very leaves. Putting the old tree back would lose them; taking back rows by key cannot. InnoDB does the same: it never undoes a page split.

DDL is rows too

The catalog is a table, so CREATE TABLE inserts a catalog row and DROP TABLE deletes one, and both leave undo records like any row change. Two things are not rows, the pages of a tree that is created or dropped:

Undoing a CREATE TABLE or CREATE INDEX also frees the new tree's pages.
DROP TABLE, TRUNCATE and DROP INDEX do not free the old tree's pages until the transaction commits. Until then nothing can reuse them, so undoing the catalog change finds the tree exactly where it was. Inside a transaction, TRUNCATE gives the table a new, empty root for the same reason.

Records live as long as their transaction

In this stage the records are kept in memory, per transaction, and dropped when it commits or rolls back. Everything that used to put pages back now applies records instead: ROLLBACK, a failed statement, 01303 and the end of the program. A rollback changes pages too, so it logs them the way a commit does: nothing it changed is left waiting for someone else's commit. Nothing else needs them yet. undo status shows how many are held:

droid session

>@1 begin;
@1| Begin statement executed successfully
>@1 insert into a (id, v) values (1, 'one');
@1| Insert statement executed successfully (1 rows)
>@1 update a set v = 'uno' where id = 1;
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1
>undo status
[UNDO] records=2 pages=0 oldest_view=0 purgeable=0

pages counts the undo pages in the file, which the next stage writes for crashes; until then it is 0. oldest_view and purgeable belong to read views and purge, later in this part.

The algorithm in words

Recording a change

One record per row, written as the row changes.

1.Before an INSERT puts a row in a table, append a record: the table and the new row's key.
2.Before an UPDATE changes a row, append a record: the table, the key and the whole row as it is now.
3.Before a DELETE takes a row, append a record: the table and the whole row.
4.Records belong to the transaction of the line's session, in the order they were made. Index entries need none: they follow the row.
5.CREATE TABLE and CREATE INDEX insert a catalog row; DROP TABLE and DROP INDEX delete one; ALTER TABLE and ANALYZE update one. Each leaves its record like any row change.

Rolling back

Walk the records from the newest to the oldest, and run the opposite of each.

1.An INSERT record: delete the row with that key from its table, as a DELETE would, indexes and merges included.
2.An UPDATE record: put the old row back under its key, as an UPDATE would.
3.A DELETE record: insert the old row again, as an INSERT would.
4.A catalog record for a CREATE: also free the new tree's pages. For a DROP or a TRUNCATE: the old tree is still there, because its pages are freed only at commit.
5.Drop the records, and log the pages undo changed as a commit logs its pages, so none is left waiting.
6.A statement that fails does the same with its own records, back to where it started.

Output contract for this stage

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

Input	Output
`undo status`	`[UNDO] records=<n> pages=0 oldest_view=0 purgeable=0`, `n` the records every session holds
`rollback;`	`Rollback statement executed successfully`; the transaction's rows, indexes and catalog as at BEGIN
`drop table t;` in a transaction	`db freelist` unchanged until the COMMIT

What you should see when done

shell

$droid --db u.db
Welcome to droid!
>create table a (id int primary key, v varchar(20));
Create table statement executed successfully
>@1 begin;
@1| Begin statement executed successfully
>@1 insert into a (id, v) values (1, 'one');
@1| Insert statement executed successfully (1 rows)
>@2 begin;
@2| Begin statement executed successfully
>@2 insert into a (id, v) values (2, 'two');
@2| Insert statement executed successfully (1 rows)
>@1 rollback;
@1| Rollback statement executed successfully
>@2 commit;
@2| Commit statement executed successfully
>select * from a;
id | v
2 | two
(1 rows)
[EXEC] rows_examined=1
>.exit
exiting.. good bye!

Common bugs in this stage

Applying records oldest first. A row changed twice ends at the wrong value.
Undoing by position. A record that remembers a page and a slot finds another row there after a split. Find the row by key.
Forgetting the indexes. Putting a row back must write its index entries, as an INSERT would.
Freeing a dropped table's pages at once. Another statement may reuse them before the ROLLBACK that needs them.
Keeping page copies for DDL. The catalog leaf is shared too; a copy of it erases another session's CREATE TABLE.

Language notes

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

C: a growable array of records per session, each a kind, a table id, a key and an owned copy of the row bytes; free the copies when the transaction ends.
C++: std::vector<UndoRecord> per session, the old row as std::vector<uint8_t>, walked with reverse iterators.
Rust: an enum Undo { Insert { table, key }, Update { table, key, old }, Delete { table, old } } in a Vec, applied with .iter().rev().
Zig: a tagged union in an ArrayList, the row bytes allocated with the session's allocator and freed at the end of the transaction.

Loading starter code…

No run yet

7 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.