Purge

Why this stage exists

Since read views, every change leaves an old version behind, and a DELETE leaves a marked row. They go when a transaction ends and no view at all is open. On a busy database that moment may never come: as long as any reader is running, nothing is dropped, even versions that no running reader could ever ask for.

Look at what a version is for. The undo record of a change made by transaction t holds the row as it was before t. Only a view that does not see t's change can need it. Once every open view sees t, the record is dead weight.

The oldest view is the horizon

So the question is not "is any view open?" but "is any view old enough to need this?". The answer depends only on the oldest open view: whatever it sees, every newer view sees too.

undo status shows both halves: who holds the horizon, and how much is waiting behind it.

>undo status
[UNDO] records=15 pages=0 oldest_view=16 purgeable=10
>purge
[PURGE] records=10 rows=0
>undo status
[UNDO] records=5 pages=0 oldest_view=16 purgeable=0

purge drops what is purgeable, takes the rows and index entries those records had marked out of their trees, and frees undo pages left empty. By itself, purge still runs only when a transaction ends with no view open, as before; the command is how a database with readers always open keeps up.

The long-running transaction

The lesson of this stage is a villain: the transaction that stays open. A report that runs for an hour keeps its view for an hour, and every version every other transaction makes in that hour waits behind it. Undo grows, marked rows keep their space, and every reader that walks a version chain walks further. Ending that one transaction lets all of it go.

Purge, PostgreSQL's VACUUM and ours

PostgreSQL solves the same problem the other way round. It keeps every version as a row in the table, so dead rows sit among live ones, and something must sweep the table: its VACUUM finds rows no snapshot can see and frees their space. InnoDB keeps old versions in undo and trims a log, which is what purge does here. Same problem, same villain: in both, one open transaction holds back every cleanup after it.

This engine's own VACUUM, from Memory and Space, is a third thing: it moves pages to make the file shorter, and has nothing to do with versions.

Output contract for this stage

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

What you should see when done

$droid --db p.db
Welcome to droid!
>create table t (id int primary key, v varchar(20));
Create table statement executed successfully
>insert into t (id, v) values (1, 'v1');
Insert statement executed successfully (1 rows)
>insert into t (id, v) values (2, 'v2');
Insert statement executed successfully (1 rows)
>@1 begin;
@1| Begin statement executed successfully
>@1 select count(*) from t;
@1| COUNT(*)
@1| 2
@1| (1 rows)
@1| [EXEC] rows_examined=2
>@2 delete from t where id = 2;
@2| Delete statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
>@3 begin;
@3| Begin statement executed successfully
>@3 select count(*) from t;
@3| COUNT(*)
@3| 1
@3| (1 rows)
@3| [EXEC] rows_examined=1
>@1 commit;
@1| Commit statement executed successfully
>undo status
[UNDO] records=1 pages=0 oldest_view=6 purgeable=1
>purge
[PURGE] records=1 rows=1
>.exit
exiting.. good bye!

Common bugs in this stage

• Purging what the oldest view needs. A record is purgeable only when every open view sees its change.
• Taking out a marked row whose delete is still needed. The row goes with its record, not before.
• Leaving index entries behind. Purge takes out every entry a dropped record's change marked: a deleted row's entries and an updated row's old ones.
• Leaving empty undo pages allocated. They go back to the free list.

Language notes

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

• C: keep committed records in commit order; the purgeable ones are a prefix of that list, so purge walks from the front and stops at the first one some view needs.
• C++: a std::deque of committed transactions with their records; pop_front while the oldest view sees the front one.
• Rust: a VecDeque of committed transactions; while let Some(t) = q.front() with the view check.
• Zig: an ArrayList used as a queue with a head index, compacted after each purge.