Undo Records and Reconstructing Older Row Versions

Two architectures solve the same problem with opposite placements of history. One writes a new copy of the row and leaves the old copy in the heap, so every version is a full row at a known location. The other overwrites the row in place and writes the previous value into an undo segment, so the heap holds exactly one version per row and earlier states must be computed.

The first is described in heap tuple headers and visibility. The second is the subject here, using InnoDB and Oracle as the two concrete instances because they expose the structure in their documentation: a rollback segment holding undo records, each record containing the before-image of the columns a transaction changed, chained by a pointer in the clustered index record.

What an undo record contains

An undo record is not a copy of the whole row. It is the minimal information needed to reverse one change: for an update, the old values of the changed columns plus enough identifying information to locate the row; for an insert, the information needed to remove it; for a delete, the information needed to reinsert it.

InnoDB’s undo records fall into two families. Insert undo records contain only the row identifier and are needed for rollback, not for reads, because no snapshot can legitimately need a row that never committed. Update undo records contain the before-image of the changed columns and are needed for both rollback and consistent reads. The distinction matters for space: a workload that inserts and commits produces undo that can be discarded as soon as the transaction’s slot is no longer needed, while a workload that updates leaves history that must be retained for as long as any snapshot might look.

Each clustered index record carries a pointer to the most recent undo record for that row, encoded as a location inside the undo tablespace rather than as a heap address. That pointer is the head of a version chain. The undo record in turn contains a pointer to the next older undo record, and the chain continues backward through successive modifications.

Reconstructing a version on demand

To produce the version visible to a snapshot, a reader takes the current row from the clustered index and walks the chain backward, applying inverse changes until it reaches a version whose transaction is visible to the snapshot.

def visible_version(row, undo_chain, snapshot):
    """row: current committed image. undo_chain: newest-first undo records,
    each a dict of {column: old_value} plus the modifying txn id."""
    image = dict(row)
    for rec in undo_chain:
        if snapshot.sees(rec.txn):
            return image            # this version was created by a visible txn
        image.update(rec.before)    # undo the change, keep walking
    return None                     # row did not exist in this snapshot

The loop applies the before-image in reverse chronological order, so after undoing the changes made by every transaction invisible to the snapshot, image holds the row as it stood at the snapshot boundary. The cost is proportional to the number of undo records traversed, which is the number of times the row was modified since the snapshot was taken.

This is the fundamental difference from the heap-version design. There, the walk is over ctid links to full tuples on pages, and each step may be a page fetch. Here, the walk is over undo records that are typically in a small number of undo segments, and each step is a memory copy of a few columns. Reconstruction is cheaper per step and more expensive per version, since a version is computed rather than read.

The chain grows with update count

Both designs degrade with repeated updates, but differently. In the heap-version design, each update adds a row to the heap, and the index gains an entry, so space grows with updates. In the undo design, each update adds an undo record, and the heap row stays one row, so index churn is avoided and space grows only in the undo area.

A row updated a thousand times between collections has a thousand undo records. A reader whose snapshot predates all of them must apply all thousand before-images to see the original. This is the read amplification that makes long-running analytical queries on hot rows expensive in an undo-based engine: the query’s snapshot is old, so every row it touches must be reconstructed by walking back through every modification since the snapshot.

Engines mitigate with two techniques. The first is a limit on how far back a chain is maintained, after which the engine may return an error rather than reconstruct: Oracle’s documented behaviour for a query that needs undo that has been overwritten is the ORA-01555 snapshot-too-old error. The second is to avoid the walk entirely by keeping a version store, which is what some engines do for statement-level reads so that a row’s recent history can be served from memory rather than from undo segments.

Rollback, recovery, and reads share one structure

The reason undo lives in a separate area rather than in the heap is that three consumers need it. Rollback of an aborted transaction needs the before-images to restore the previous state. Consistent reads need them to reconstruct versions. Recovery after a crash needs them, in combination with the redo log, to undo transactions that were in flight when the crash occurred.

Sharing one structure across three consumers is the design’s main economy. The alternative — maintaining history separately for reads and separately for rollback — would duplicate writes. The cost is that the retention requirement is the maximum over the three consumers: undo must be kept until the oldest snapshot that needs it is done, even if the transaction that wrote it committed long ago and rollback will never be needed.

This is why the undo tablespace’s size is a function of the longest-running query, not of the transaction rate. A short transaction that updates a row can pin undo for hours if a reporting query took its snapshot before the update and has not finished.

Interaction with locks

In an undo-based engine, a writer that modifies a row takes an exclusive lock on it and holds that lock until commit. Readers do not take shared locks; they reconstruct the version they need from undo and therefore never block a writer. This is the same non-blocking read property as the heap-version design, achieved by a different route.

The lock is still required for write-write exclusion, and it is also what makes a reader’s reconstruction correct. If another transaction modified the row after the reader’s snapshot, the undo chain contains that modification’s before-image, which is exactly what the reader needs to step past it. If the other transaction is still in flight, its undo record exists and is marked as belonging to an uncommitted transaction, so the reader steps past it without needing to know whether it will commit.

There is one asymmetry worth noting. A reader that encounters a row whose most recent modification is uncommitted must decide whether to wait. Under read committed, the reader may wait for the writer to commit or abort, then reconstruct. Under a snapshot level, the reader can step past the uncommitted modification immediately, because the modification is invisible by definition and the before-image is already available. The first behaviour can produce blocking that the second avoids, and it is a per-statement decision in engines that support both. Which snapshot a reader is comparing against, and when it was fixed, is the subject of snapshot acquisition and commit ordering.

-- In an undo-based engine, the read does not wait for the writer:
-- the SELECT reconstructs the pre-update image from undo.
-- Session A
UPDATE accounts SET balance = balance - 100 WHERE id = 1;   -- uncommitted
-- Session B, at a snapshot taken before A started
SELECT balance FROM accounts WHERE id = 1;                  -- returns old value

In a locking engine the same read would block until session A resolves. The difference is not the isolation level’s name but which mechanism implements it.

Block cleanout and the cost of deferral

Writing the undo record is not the only work an update performs. The row’s header must record the transaction that made the change and the pointer to the undo, and the index entries must be updated. For a large update touching many rows, doing all of that eagerly is expensive, so some engines defer part of it.

Oracle’s deferred block cleanout is the documented case: when a transaction modifies a large number of blocks, it may leave the transaction’s identifier and a commit flag in each block header without immediately rewriting every row header to mark the transaction committed. A later reader that encounters such a block performs the cleanup itself, which is why the first access to a recently modified table can be slower than subsequent accesses. The mechanism shifts work from the committing transaction to the next reader, which is a throughput decision: commit latency matters more than the latency of an arbitrary later read.

The consequence for visibility is that a row header may reference a transaction that has committed but is not yet marked as such in that block. The reader must consult the transaction status, find it committed, and then update the header. Correctness is preserved because the status lookup is authoritative; the header is a cache of it.

Which placement wins

The choice between heap versions and undo is not a matter of one being newer. Each optimizes a different path.

Heap versions make reads of old data cheap in CPU and expensive in space and index churn: an update writes a full row and a new index entry, and a reader walks pointers to full tuples. Undo makes updates cheap in space and index churn and makes old reads expensive in reconstruction: an update writes only the changed columns’ before-images, and a reader computes the version.

The observable consequences are predictable from that. Tables with wide rows and few updates favour heap versions, because the space cost of a full copy is high but the update rate is low. Tables with narrow rows and heavy update rates favour undo, because a before-image of two columns is far smaller than a full row and index maintenance is avoided. Long-running analytical queries are cheaper against heap versions, since the walk reaches a materialized tuple rather than reconstructing one. Write-heavy transactional workloads are cheaper with undo, since commit does not wait for index insertion of a new version.

The visibility rules are identical in both. What differs is where the bytes live, and therefore which operation pays for the versioning.