ROLLBACK with Before-Images

Why this stage exists

In the last stage a transaction could already be thrown away, by 01303 or by ending the session. You probably did it by forgetting the pages in memory and letting the next read fetch them from the file again, which works because nothing uncommitted ever reaches the file. That is a way out, not an answer. The user has no way to say "I changed my mind", and a statement that fails half way through still leaves its first half behind.

ROLLBACK is the user saying it. The answer this stage teaches is the one every engine uses in some form: before you change something, keep what it was. Here the something is a page, and the copy is its before-image. ROLLBACK puts the copies back.

It is worth doing properly now because the same copies solve a second problem. A statement that fails after it changed some pages, such as an UPDATE that reaches a damaged leaf after rewriting three healthy ones, has to change nothing. Inside a transaction you cannot throw the whole transaction away for that. You need to undo exactly one statement, and before-images taken at the right moment are exactly that.

What changes: a copy before the first change

The first time a transaction is about to change a page, it takes a copy. Later changes to the same page take nothing: the copy that matters is the page as it was at BEGIN.

ROLLBACK walks the transaction's pages. A page with a before-image gets it back. A page the transaction allocated past the end of the file has no image: it simply leaves, and the page count goes back to what it was. Nothing is written to the file: thanks to no-steal it never saw the changes. Do not get the old bytes back by reading the file again, though. It works today, and stops working when commits stop writing the file (the checkpoint stage): then the page at BEGIN may hold a commit the file does not have yet. The before-image always has it.

Since everything in droid is a page, this one mechanism undoes everything:

What is not a page is a copy of something a page holds, kept in memory for speed: the page count, a table's root or the catalog's root, the head and length of the free list, anything a statement cached about the schema. After ROLLBACK every such copy must agree with the restored pages again, either because it was put back with them or because it is read from them afresh. The transaction's own bookkeeping (its set of pages, its images, its state) is the other thing outside the pages, and ROLLBACK clears it.

PostgreSQL never needs before-images for rollback: an aborted transaction's row versions simply stay invisible. InnoDB keeps an undo log of row changes instead of whole pages. SQLite's rollback journal is the closest to this stage: before a page is first changed in a transaction, its original goes to the journal.

What changes: a statement inside a transaction

A statement is a small transaction of its own. Before it runs, note what the transaction had changed so far. If it fails part way, put back what it changed, then print its error: the transaction carries on with the statements before it, as if the failed one had never run.

Output contract for this stage

The full definition is on the output contract page, sections 32 and 34.

After ROLLBACK, pager status shows the same total_pages as at BEGIN, and db header, db freelist, catalog list and btree structure print what they printed then.

What you should see when done

$droid --db shop.db
Welcome to droid!
>create table items (id int, label varchar(40));
Create table statement executed successfully
>insert into items (id, label) values (1, 'lamp');
Insert statement executed successfully (1 rows)
>begin;
Begin statement executed successfully
>update items set label = 'broken lamp' where id = 1;
Update statement executed successfully (1 rows)
[EXEC] rows_examined=1
>create table orders (id int, item int);
Create table statement executed successfully
>catalog list
[CATALOG] Tables: 2
[CATALOG]   items root=2 (id INT, label VARCHAR(40))
[CATALOG]   orders root=3 (id INT, item INT)
>rollback;
Rollback statement executed successfully
>catalog list
[CATALOG] Tables: 1
[CATALOG]   items root=2 (id INT, label VARCHAR(40))
>select * from items;
id | label
1 | lamp
(1 rows)
[EXEC] rows_examined=1
>rollback;
[ERROR:01302] No transaction is open
>.exit
exiting.. good bye!

The UPDATE and the new table went back together: the catalog is a tree of pages, and its leaf had a before-image like any other.

Common bugs in this stage

• Taking the image after the change. The copy must be taken before the first byte of the page changes, on every path that writes a page: one missed path is a page ROLLBACK cannot put back.
• Taking a new image on every change. The second change must not replace the image, or ROLLBACK restores the page as it was after the first statement.
• Forgetting the header. Allocating from the free list, freeing a page and creating a table change page 0. Without its image the free list or the catalog's root points at pages that no longer hold what it says.
• Restoring the pages and not their copies. A page count, a root or a free-list head kept in memory still says what the transaction made it say. The pages are right, and the next statement follows the stale copy.
• Leaving new pages behind. A page allocated past the end of the file has no image. If it stays, total_pages is too large and the next allocation skips a page.
• Undoing a failed statement with the transaction's images. That throws away the statements before it too. A statement needs to know what it changed for the first time and what the transaction had already changed, and put each back to its own point.
• Re-reading the page from the file instead of keeping an image. It works until commits stop at the log; then it brings back a page from before the last checkpoint and loses commits.
• Writing the images to the file. The file never saw the changes: writing them is wasted work, and with a small pool it can push out a page the transaction still holds.

Language notes

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

• C: an image is a 4096-byte memcpy into a buffer you own. A small array of (page number, buffer) per transaction is enough at this scale; free the buffers on commit and on rollback, or every transaction leaks 4 KB a page.
• C++: a hash map from page number to a fixed 4096-byte array holds the images. The standard map has an insert that does nothing when the key is already there, which is the rule above in one call.
• Rust: a hash map from page number to a copy of the page. Its entry API can insert only when the page has no image yet. Take the copy while you hold the frame mutably, before you write, and the borrow checker keeps the order honest.
• Zig: a hash map from page number to a 4096-byte array. Its get-or-put tells you whether the page already had an image; fill the value only when it did not. Clear the map at commit and rollback, keeping its capacity.