MVCC Internals: Version Chains and Snapshots

Account 7 was created with balance 100 by transaction 10. Transaction 15 later debited it to 80. Under in-place update the page would now say 80 and nothing else. Under MVCC the page holds *both* tuples: the original, stamped xmin=10, xmax=15, and the new one, xmin=15, xmax=0. The old version's xmax says "superseded by 15"; its t_ctid says where the successor is. Nothing has been erased. The versions form a chain, oldest to newest, exactly a Linked List whose links are (page, slot) addresses.

A transaction that started before 15 committed, and one that started after, both scan this page and both find two tuples. What differs is the answer each gets from the visibility rule, and the rule's only inputs are the two ids on each tuple and the reader's snapshot.

A snapshot is not a copy of data; it is a compact description of which transactions count as finished. Three parts. xmin: the lowest transaction id still in progress when the snapshot was taken — every id below it has committed or aborted, and only the status table is needed to tell which. xmax: the next id to be assigned — every id at or above it started after the snapshot and is invisible regardless of whether it has since committed. xip: the list of ids in between that were in progress at snapshot time; they may commit later, but not for this snapshot. The whole structure is a few dozen bytes, built by one pass over the running list from A Transaction, Inside the Engine.

Because it is built from the running list rather than from the data, taking a snapshot costs microseconds and does not touch a single page. That is why READ COMMITTED can afford a new one per statement.

Every tuple a scan touches goes through the same test, and it has two halves. First the creator: is xmin something this snapshot considers committed? Yes if xmin is my own transaction and the tuple was written by an earlier command of mine (cmin below the current command id); yes if xmin < snap.xmin and the status table says committed; yes if snap.xmin ≤ xmin < snap.xmax, xmin is not in snap.xip, and the status table says committed. Any other case — aborted, in progress, in xip, or at or above snap.xmax — and the tuple is invisible: it was created by something outside my world.

Then the deleter, with the same test on xmax. xmax = 0: nobody has deleted or superseded it; visible. xmax aborted: the deletion never happened; visible. xmax in progress, in xip, or ≥ snap.xmax: the deletion is outside my world; visible. xmax committed and inside my world: the tuple was gone before I started; invisible. One more case: xmax is my own transaction — then it is invisible if the deletion was by an earlier command, otherwise visible. In the example above, a snapshot with xip = [15] sees slot 3 (creator 10 committed, deleter 15 in progress → alive) and not slot 8 (creator 15 in progress); a snapshot taken after 15 committed sees slot 8 and not slot 3.

PostgreSQL keeps every version in the table itself. An UPDATE inserts a new tuple — on the same page if there is room, otherwise elsewhere — and stamps the old one. The chain is walked by t_ctid only in special cases (a READ COMMITTED update chasing a concurrently modified row); ordinary scans simply test every tuple on every page and keep the visible ones. The approach is simple and makes rollback free, at the cost that the table grows with every update until VACUUM reclaims dead versions, and that every index must point at every version. UPDATE, DELETE and Dead Tuples is about that cost; Slotted Pages shows the page structure the versions sit in.

InnoDB (and Oracle before it) keeps only the newest version in the table. An UPDATE overwrites the row in the clustered index in place, after writing the old column values to an undo log record in a rollback segment; the row's DB_ROLL_PTR points at that record, and the record points at the previous one, so the chain runs backwards through undo space. A reader whose read view cannot see the row's DB_TRX_ID follows the roll pointer and reconstructs the older version, repeating until it reaches one whose transaction id its view accepts. The table stays compact and secondary indexes point at the primary key rather than at a version. The costs are the reconstruction work for old snapshots, the undo space a long reader forces the engine to keep (the "history list"), and the possibility — in Oracle, ORA-01555 — that the undo needed for a very old snapshot has already been recycled.

Transaction ids are 32-bit, and PostgreSQL assigns one to every writing transaction. Four billion ids sounds like plenty; at ten thousand write transactions per second it is five days. Rather than stop, the counter wraps, and comparisons are done modulo 2^32: id *a* is older than id *b* if *a* lies within the two billion ids behind *b*. That works as long as no tuple on disk carries an xmin more than about two billion ids in the past — beyond that horizon the old id would compare as *newer* than the current counter, and the tuple would become invisible to everyone: silent data loss.

Freezing prevents it. VACUUM marks tuples whose xmin is older than vacuum_freeze_min_age as frozen — historically by overwriting xmin with a reserved id, since 9.4 by setting HEAP_XMIN_FROZEN in the infomask — which the visibility rule treats as "committed before every possible snapshot" without any comparison. Each table records the oldest unfrozen id it might contain (relfrozenxid); when that age reaches autovacuum_freeze_max_age (200 million) autovacuum runs an aggressive vacuum on the table whether it is bloated or not. If something prevents freezing for long enough — a table autovacuum cannot finish, a stuck prepared transaction, an abandoned replication slot — the server warns at forty million ids from the limit and, a few million from it, refuses to assign new ids at all: the database goes read-only until a manual VACUUM catches up. The 64-bit ids that would remove the problem are still a long-standing work item, so age(relfrozenxid) is a number every PostgreSQL operator monitors.