The idea: the newest version in the page, older ones in undo
InnoDB keeps one version of each row in the clustered index: the newest. When a transaction changes a row, it first copies the old version into an undo record, then changes the record in place. Each record points to its undo record, and each undo record points to the one before it. That is a version chain, kept in the undo tablespaces. A reader with an old snapshot walks back the chain until it finds a version it may see. The purge thread frees old versions once no snapshot needs them.
Hidden columns: DB_TRX_ID and DB_ROLL_PTR
Every clustered index record has two hidden system columns (plus DB_ROW_ID when the table has no primary key):
DB_TRX_ID(6 bytes): the id of the transaction that wrote this version. Read-write transactions get an id fromtrx_sysat their first write; read-only transactions get none.DB_ROLL_PTR(7 bytes): the address of the undo record that rebuilds the previous version (rollback segment, page, offset), with one bit that says "this is insert undo".
An UPDATE writes an update undo record with the old values of the changed columns and the old DB_TRX_ID and DB_ROLL_PTR, then changes the record (Demo: UPDATE builds a version chain). Undo pages are ordinary pages: they live in the buffer pool and are protected by the redo log.
Read views
A consistent read (a plain SELECT) uses a read view. In REPEATABLE READ it is created at the first consistent read and kept until the transaction ends; in READ COMMITTED each statement gets a new one. A read view holds four values, and decides for each DB_TRX_ID:
| field | set to, at creation | test |
|---|---|---|
m_up_limit_id | smallest active trx id | id < it → visible ✓ |
m_low_limit_id | next trx id to be assigned | id ≥ it → not visible ✗ |
m_ids | trx ids active at that moment | id in it → not visible ✗ |
m_creator_trx_id | the reader's own id (0 if read-only) | own changes → visible ✓ |
If the version in the page is not visible, InnoDB follows DB_ROLL_PTR, builds the previous version from the undo record and tests again (row_vers_build_for_consistent_read). The reader takes no locks (Demo: an old read view reads the old version). See MVCC and isolation levels for the anomalies each level allows.
DELETE only delete-marks
A DELETE does not remove the record. It sets the record's delete mark and writes an undo record, like an update. Older read views still see the row through the chain. The record is removed from the page later, by purge, once every read view sees the delete (Demo: commit, then purge). Secondary index entries are delete-marked and purged the same way.
Commit, the history list and purge
At COMMIT, the transaction's update undo log is added to the history list of its rollback segment, in commit order. The undo records are no longer needed for rollback, but an older read view may still need them for reading. The purge thread (innodb_purge_threads, default 4) takes a copy of the oldest open read view, the purge view, and walks the history list from the oldest end. A transaction's undo log can go when the purge view sees it. Purge then frees the undo records and removes delete-marked records. It stops at the first transaction some read view cannot see yet.
The number of undo logs waiting in the history list is the history list length, shown in SHOW ENGINE INNODB STATUS:
------------ TRANSACTIONS ------------ Trx id counter 103 Purge done for trx's n:o < 100 undo n:o < 0 state: running History list length 3
Long transactions grow the history list
A transaction that stays open keeps its read view, so purge cannot pass it. Every write committed after the view was opened adds to the history list, and nothing leaves it. Undo tablespaces grow, delete-marked rows pile up in the indexes, and the old reader itself gets slower: each of its reads walks a longer chain (Demo: long transaction blocks purge: three committed updates, history list length 3, and one SELECT reads 3 undo records to return bal 100). Once the reader commits, purge frees all of it. Watch History list length and information_schema.innodb_trx (trx_started) to find the culprit; innodb_max_purge_lag can slow writers down when the list gets long.
Insert undo and ROLLBACK
An INSERT writes insert undo: only the key, enough to remove the row on rollback. There is no older version, and a read view that cannot see the inserting transaction must not see the row at all; the insert bit in DB_ROLL_PTR tells it so. So insert undo is freed at COMMIT and never enters the history list (Demo: insert undo is discarded at commit).
ROLLBACK applies the transaction's undo records from newest to oldest: insert undo removes the row, delete-mark undo clears the mark, update undo copies the old values back (Demo: ROLLBACK applies the undo log). A big rollback costs about as much as the work it undoes. After a crash, recovery rolls back unfinished transactions from undo the same way (see InnoDB crash recovery).
Compared with PostgreSQL
Both engines give readers a snapshot without locks. They keep old versions in different places:
| InnoDB | PostgreSQL | |
|---|---|---|
| where old versions live | undo log; the page holds the newest | heap; every version is a tuple in the table |
| row header | DB_TRX_ID, DB_ROLL_PTR | xmin, xmax, ctid |
| old snapshot reads | rebuild from undo, walking the chain | skip invisible tuples in the heap |
| clean-up | purge thread, history list | VACUUM / autovacuum, dead tuples |
| ROLLBACK | applies undo | marks the xid aborted in pg_xact; nothing undone |
| long transaction hurts | history list length, long chains | table and index bloat, VACUUM cannot remove dead tuples |
See also How PostgreSQL Runs a Query, pg_xact and hint bits, How MySQL Runs a Query, InnoDB consistent and locking reads and the InnoDB page.
What the page leaves out
Real purge compares the transaction serialisation number (trx_no, given at commit) against the purge view's m_low_limit_no, not the trx id, and works in batches (innodb_purge_batch_size) over 128 rollback segments in two or more undo tablespaces, which it can truncate (innodb_undo_log_truncate). Undo records store only the changed columns, and an update of a key column is a delete-mark plus insert. Secondary indexes have no hidden columns: a reader checks the page's PAGE_MAX_TRX_ID and may go to the clustered index. Locking reads (FOR UPDATE) read the newest version and lock it. Temporary tables use non-redo-logged undo.