What is a Version Chain?
A version chain is a linked list of row versions that enables Multi-Version Concurrency Control (MVCC). When a row is updated, the database does not overwrite the old value in place. Instead, it creates a new version and links the old version into a chain, allowing concurrent readers to see a consistent snapshot of the data without blocking writers.
How version chains work
Each row version contains:
- The actual data (column values)
- A transaction ID (xid) — the ID of the transaction that created this version
- A pointer to the previous version (the undo pointer)
When a transaction updates a row:
- The current (latest) version's before-image is copied to the undo log (a separate storage area).
- The row is updated in place with the new values and the current transaction's ID.
- A pointer from the new version links back to the old version in the undo log.
When a transaction reads a row:
- Start at the latest version.
- Check if this version is visible to the reader's snapshot (i.e., the creating transaction committed before the reader's snapshot timestamp).
- If not visible, follow the undo pointer to the previous version and repeat.
- Return the first version that is visible.
Undo log
The undo log stores before-images of modified rows. It serves two purposes:
- MVCC reads: readers traverse the version chain to find their visible version.
- Rollback: if a transaction aborts, the database follows the version chain and restores the previous version. The undo log contains exactly the data needed to "undo" each change.
Visibility rules
A version created by transaction T is visible to reader R if:
- T committed before R's snapshot was taken, OR
- T is the same transaction as R (a transaction can see its own uncommitted changes)
A version is not visible if:
- T is still active (uncommitted) when R reads
- T committed after R's snapshot (R should not see future changes)
Version chain length and performance
Long version chains hurt read performance. If a row has been updated 100 times, a reader with an old snapshot must traverse up to 100 versions to find the one it can see. This is why:
- Long-running transactions are problematic — they prevent old versions from being garbage collected.
- Vacuum/purge processes periodically clean up versions that are no longer visible to any active transaction.
- PostgreSQL stores old versions in the main heap (no separate undo log), making vacuum even more critical.
- MySQL/InnoDB stores old versions in a dedicated undo tablespace and has a background purge thread.
Approaches to version storage
| Approach | Where old versions live | Used by |
|---|---|---|
| Append-only (O2N) | Main table, oldest-to-newest chain | PostgreSQL |
| Append-only (N2O) | Main table, newest-to-oldest chain | (less common) |
| Delta storage | Undo log (only changed columns) | MySQL/InnoDB, Oracle |
| Full undo | Undo log (complete row copies) | SQL Server |
Delta storage is the most space-efficient: if only one column out of 20 changes, only that column's before-image is stored in the undo log. PostgreSQL's approach creates a full copy of the row for every update, which can cause significant table bloat (known as "bloat" or "dead tuples").
Rollback via version chain
When a transaction aborts:
- Follow the version chain for each modified row.
- Restore the previous version (the before-image from the undo log).
- Remove the aborted version.
This is efficient because the undo log already contains exactly the data needed.
Real-Life: MVCC in PostgreSQL and MySQL
PostgreSQL's version chain (append-only):
-- Transaction A (xid=100) inserts a row
INSERT INTO accounts (id, balance) VALUES (1, 1000);
-- Row version: {id:1, balance:1000, xmin:100, xmax:null}
-- Transaction B (xid=101) updates the balance
UPDATE accounts SET balance = 900 WHERE id = 1;
-- Old version: {id:1, balance:1000, xmin:100, xmax:101}
-- New version: {id:1, balance:900, xmin:101, xmax:null}
Both versions exist in the heap. A concurrent reader with snapshot before xid=101 still sees balance=1000. PostgreSQL's VACUUM later removes the old version when no transaction needs it.
MySQL/InnoDB's version chain (undo log):
In InnoDB, the latest version lives in the clustered index (the main table). Old versions are pushed to the undo log:
- Row in table:
{id:1, balance:900, trx_id:101, roll_ptr: → undo_log_entry} - Undo log entry:
{id:1, balance:1000, trx_id:100, roll_ptr: → older_entry_or_null}
A reader with an old snapshot follows roll_ptr to find its visible version.
The cost of long chains: If a table row is updated once per second and a reporting query takes 5 minutes, the query might need to traverse up to 300 versions of that row. This is why DBAs warn against long-running transactions in OLTP databases — they cause version chain buildup, increase undo log size, and slow down reads.
Practical tip: Monitor pg_stat_user_tables.n_dead_tup in PostgreSQL or trx_undo_history_len in MySQL to detect version chain buildup.