Row-Level Undo

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:

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:

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:

>@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.

Output contract for this stage

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

What you should see when done

$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.