MVCC — multi-version concurrency control: Worked examples

This page is the drill hall for MVCC — multi-version concurrency control. The parent gave you the visibility rule; here we run it against every kind of input it can receive, so no scenario ever surprises you.

Before we compute anything, let us re-anchor the symbols we will use in plain words, because every example below depends on them.

Definition What "

$\infty$ " means for xmax Each stored row-version carries two tags. In pictures they are just numbers on a timeline.

==xmin== — the txid (a plain counting number, like a ticket number) of the transaction that wrote this version into existence.
==xmax== — the ticket number of the transaction that deleted or overwrote this version.

When no transaction has deleted it yet, there is no ticket number to store, so the database writes a special placeholder meaning "no deleter — still alive." We draw that placeholder as == $\infty$ == ("infinity"). It is not a real txid and never equals any real ticket; it simply means "the death test has nothing to check — this version has not been killed." Concretely a real database stores a sentinel like 0; we use $\infty$ because on the timeline it sits beyond every possible future ticket, so no reader's cut can ever reach it.

Figure — MVCC — multi-version concurrency control

Figure s01 — the snapshot as a cut on the txid timeline. A left-to-right black arrow is the txid timeline (small ticket numbers on the left, larger/newer ones on the right). Two black dots at ticket 40 and ticket 90 are past transactions labelled "committed". A bold red vertical line at 100 is the snapshot cut, labelled $x_{ma x}^{s na p} = 100$ . One more black dot sits at ticket 101, just to the right of the red line, annotated "in my FUTURE (invisible)"; the region left of the line is annotated "in my PAST (possibly visible)". The whole picture says: every visibility question reduces to "which side of the red line is this ticket?"

Why three sub-tests and not one? Because a ticket number alone (xmin < x^{snap}_{max}) tells you only when it started, not whether it succeeded (the committed lookup) and not whether it was already running when you looked (the active set). Each sub-test answers a different question, so we need all three.

The scenario matrix

Every question MVCC can throw at you falls into one of the case-classes below. Read this as a checklist of coverage: each row is one kind of input, and each is worked out in full further down. Together the examples hit every row.

Cell A — Creator started after my snapshot ( $x min \geq x_{ma x}^{s na p}$ ). → Example 1
Cell B — Creator committed before my snapshot. → Example 1, Example 2
Cell C — Creator still in my active set (concurrent, uncommitted). → Example 2
Cell D — Creator aborted (never committed). → Example 3
Cell E — Finite xmax whose deleter is visible → row looks dead. → Example 4
Cell F — Finite xmax whose deleter is invisible → row looks alive. → Example 4
Cell D′ — Deleter aborted (xmax set, then rolled back) → row looks alive. → Example 5
Cell G — Degenerate: row never touched, $x ma x = \infty$ , empty active set. → Example 6
Cell H — Write–write conflict, same row (limiting case). → Example 7
Cell I — Real-world word problem (bank balance across a snapshot). → Example 8
Cell J — Exam twist: write skew — two txns, disjoint rows, broken constraint. → Example 9
Cell K — Limiting behaviour: long-open reader freezes the GC horizon. → Example 10

Example 1 — Creator in my future (Cells A, B)

Forecast: Guess now — do I read the fresh value (101) or the stale one (90)?

Test $V_{n e w}$ 's birth. Is $101 < x_{ma x}^{s na p} = 100$ ? No. Why this step? A ticket number $\geq 100$ was handed out after I froze my snapshot — it is in my future (this is exactly the black dot at 101 sitting right of the red cut line in figure s01). Future work is invisible. $V_{n e w}$ fails immediately → invisible.
Test $V_{o l d}$ 's birth. $x min = 90$ : committed ✓ (status lookup returns committed), not in active set ✓, $90 < 100$ ✓ → birth visible. Why this step? All three checks pass, so this version legitimately existed for me.
Test $V_{o l d}$ 's death. $x ma x = 101$ . Is the deleter 101 visible? By step 1, $101 \geq 100$ → deleter invisible. So the death has not happened for me → row still alive. Why this step? A version is only "dead to me" if I can see the transaction that killed it. I cannot see 101, so $V_{o l d}$ stays alive.

Answer: I read $V_{o l d}$ .

Verify: Only one version can be visible at a time (a consistent read returns exactly one value). We got $V_{n e w}$ invisible, $V_{o l d}$ visible → exactly one → consistent. ✓

Example 2 — Concurrent, uncommitted creator (Cell C)

Forecast: 95 is smaller than 100 — so is it visible? Guess.

Check "committed?" The status lookup for 95 returns in progress, not committed. Birth test already fails on the committed clause. Why this step? Reading data from a transaction that has not committed = reading dirty data, which MVCC forbids.
Check "in active set?" Yes, $95 \in {95}$ . Why this step? Even if 95 commits a millisecond later, it was in-progress when I looked. For a repeatable picture I must pretend it never happened.

Answer: Invisible. The version fails birth on two independent clauses — a clean demonstration of why we need both "committed" and "not in active set."

Verify: $x min \in$ active set $\Rightarrow$ birth invisible, regardless of the $x min < x_{ma x}^{s na p}$ number check. Predicate visible = False. ✓

Example 3 — Aborted creator (Cell D)

Forecast: 88 is old and not active — tempting to say visible. Guess.

Check "committed?" The status lookup for 88 returns aborted, so it never committed. Why this step? An aborted transaction's writes are logically erased — they must be invisible to everyone, forever, even transactions that started long after.

Answer: Invisible. Aborts are the reason "committed" is a hard requirement and not just "old enough."

Verify: committed(88) is False $\Rightarrow$ birth-visible is False $\Rightarrow$ visible is False. ✓

Example 4 — The mirror image: is the death visible? (Cells E, F)

Forecast: Same version, two readers — can they disagree? Guess before reading.

Both see the birth. $x min = 50$ : committed ✓, not active ✓, $50 < 120$ and $50 < 200$ ✓. Birth visible for both. Why this step? We must run all three birth sub-tests before touching the death test — a version whose birth is invisible is invisible outright, and there would be nothing to ask about its death. Here all three pass for both readers, so the birth is settled and the interesting difference must come from the death test.
Reader P checks the death. Is deleter $150$ visible to P? $150 < x_{ma x}^{s na p} = 120$ ? No → deleter invisible → death not visible → $V$ alive for P. (Cell F) Why this step? P froze time at ticket 120; the delete at 150 is in P's future.
Reader Q checks the death. Is deleter $150$ visible to Q? committed ✓, not active ✓, $150 < 200$ ✓ → deleter visible → death visible → $V$ dead for Q. (Cell E)

Answer: The same version is alive for P and dead for Q simultaneously. This is MVCC's whole point: two readers legitimately see two different truths.

Figure s02 — one version, two readers, two truths. A horizontal red bar spans ticket 50 to ticket 150: this is version $V$ 's lifespan, born at its left end (xmin=50) and killed at its right end (xmax=150). A black dashed vertical line at 120 is Reader P's cut, landing inside the red bar → the death at 150 is still in P's future → P sees the bar as ongoing (alive). A black dotted vertical line at 200 is Reader Q's cut, landing past the red bar's right end → Q sees the whole bar finished (dead). One red object, two black cut lines: one version, two truths.

Verify: alive_for_P = True, alive_for_Q = False. ✓

Example 5 — The deleter aborts (Cell D′)

Forecast: The xmax field literally says 140 and $140 < 200$ — so is the row dead? Guess.

Birth of $V$ : $x min = 30$ committed ✓, not active ✓, $30 < 200$ ✓ → birth visible. Why this step? Before asking whether a version died, we confirm it was ever born to us. It was.
Death test on deleter 140 — run the same three sub-tests. Status lookup for 140 returns aborted → the "committed" sub-test fails. Why this step? The xmax number being present is not enough. A delete only takes effect if the deleting transaction actually committed. An aborted deleter rolled back its delete, so the row was never really removed. This is the exact mirror of Example 3 (aborted creator) — here the abort spares a death instead of cancelling a birth.
Deleter invisible → death not visible → $V$ alive.

Answer: $V$ is alive. A stamped xmax from an aborted transaction is a "phantom death" that everyone must ignore.

Verify: committed(140) = False $\Rightarrow$ death-visible = False $\Rightarrow$ $V$ alive = True. ✓

Example 6 — Degenerate: an untouched row (Cell G)

Forecast: No competing versions at all — trivially visible? Guess.

Birth: committed ✓, not active ✓, $10 < 1000$ ✓. Why this step? Even in the "obvious" case we still run all three birth sub-tests, because each guards a different failure mode: committed rules out dirty data, not-in-active rules out a concurrent-but-later commit, and $x min < x_{ma x}^{s na p}$ rules out a future ticket. Skipping any one is how bugs like reading uncommitted rows creep in — so we check all three even when the answer feels certain.
Death: $x ma x = \infty$ → the "or $x ma x = \infty$ " branch fires immediately → death not visible. Why this step? The $\infty$ placeholder means "no deleter to look up," so the death test has nothing to check. It is the base case of the whole rule.

Answer: Visible. This is the simplest, most common case — worth naming so you recognise it instantly.

Verify: $x ma x = \infty \Rightarrow$ death-invisible branch is True $\Rightarrow$ visible = (birth-visible) = True. ✓

Example 7 — Write–write conflict on one row (Cell H)

Forecast: MVCC says "writers never block readers" — so does T201 sail through? Guess.

T201 reads the row for its own snapshot. Its active set contains 200, so T200's new version $(x min = 200)$ is invisible to T201 by the birth test (200 in active set) → T201 reads the old value 5, just like any reader. Why this step? This confirms the read half still obeys the visibility rule — T201's snapshot ( $x_{ma x}^{s na p} = 201$ , active set ${200}$ ) makes T200's uncommitted write invisible, exactly as in Example 2.
T201 now tries to write a new version of that same row. There can be only one current version claiming to supersede a given row. Why this step? Two versions both saying "I replace version X" is a contradiction — the version chain would fork.
T201 blocks on a row-level write lock held by T200 until T200 commits or aborts. Why this step? Someone must lose; the writes are serialized so the chain stays linear.
If T200 commits: under Snapshot Isolation T201 gets could not serialize access due to concurrent update. Why this step? T201's snapshot was frozen before T200 committed, so the value T201 based its update on (5) is now stale. Overwriting it would silently discard T200's committed change (a lost update). Snapshot Isolation refuses this and reports it as a serialization error.

Answer: T201 waits, then aborts/retries. This is the limiting case where MVCC's no-blocking promise stops.

Verify: the final stock after one successful decrement of 5 is 4 (only one writer wins). ✓

Example 8 — Word problem: bank balance across a snapshot (Cell I)

Forecast: After a committed write of 200, surely T100 sees 200? Guess.

$V_{n e w}$ birth: $101 < x_{ma x}^{s na p} = 100$ ? No → invisible (T101 is in T100's future). Why this step? T101's ticket (101) was handed out after T100 froze its snapshot at 100, so the whole "balance = 200" version lives in T100's future and cannot be read — regardless of the fact that it later committed.
$V_{o l d}$ birth: $40 < 100$ ✓, committed ✓, not active ✓ → visible. Why this step? This is the value that existed at the instant T100 took its snapshot; all three birth sub-tests confirm T100 is entitled to see it, giving T100 a consistent view of the past.
$V_{o l d}$ death: deleter $101$ invisible (step 1) → row alive. Why this step? The delete of $V_{o l d}$ was performed by T101, and T101 is invisible to T100, so from T100's viewpoint the old balance was never superseded — it is still the live value.

Answer: T100 reads 100, and it never blocked — the write of 200 happened concurrently but is invisible to T100's frozen snapshot.

Verify: visible value = 100 (the old version), not 200. ✓

Example 9 — Exam twist: write skew (Cell J)

Forecast: They edited different rows — so no write-write conflict. Does the DB catch this? Guess.

Both read the same frozen snapshot → each sees the other as still on-call. Why this step? Snapshot Isolation reads a frozen past; neither sees the other's write.
They write disjoint rows (Alice-row, Bob-row) → no write-write conflict → both commit. Why this step? The write-write lock from Example 7 only fires when two transactions target the same row-version. Here T1 supersedes only Alice's version and T2 supersedes only Bob's version, so neither ever asks for a lock the other holds → the DB sees nothing to serialize and lets both through.
Result: zero doctors on-call — a cross-row constraint broken with no conflict flagged. Why this step? Each transaction's decision was correct against its own snapshot (one other doctor was on-call in that frozen past). But the constraint spans both rows, and no single row-level conflict check ever compares the two writes together — so the combined effect (both off) slips past every guard the DB had.

Answer: SI allows this anomaly (write skew); true Serializability forbids it. Fix: SSI (Serializable Snapshot Isolation, an upgraded SI that tracks read–write dependencies between transactions and aborts one when a dangerous cycle forms) or explicit SELECT ... FOR UPDATE. See ACID Properties for the "I" (Isolation) this stresses.

Verify: final on-call count $= 2 - 2 = 0 < 1$ → constraint violated. ✓

Example 10 — Limiting behaviour: the frozen GC horizon (Cell K)

Forecast: Millions of overwritten versions are dead — can we clean them all? Guess.

Define the horizon. A version is reclaimable only if no live snapshot could see it. The oldest live snapshot is R's, and its $x_{min}^{s na p}$ is pinned at 500. Why this step? R might still need any version alive as of txid 500 — so the $x_{min}^{s na p}$ of the oldest open transaction becomes the global cutoff below which cleanup is safe. (This is the one place the $x_{min}^{s na p}$ symbol from the opening definitions does real work.)
Consequence: every version whose death is newer than R's view is unreclaimable, because R's snapshot might treat it as alive. Why this step? GC cannot cross a live reader's horizon — R freezes it at 500.

Answer: Almost nothing can be reclaimed → table bloat + slow scans. This is why long-open transactions are an MVCC anti-pattern. (Related: Transaction IDs and Wraparound, Write-Ahead Logging (WAL).)

Verify: reclaimable-horizon $= min (live snapshot xmins) = 500$ , not 9{,}000{,}000. ✓

Recall

Recall Quick self-test

A version $(x min = 101, x ma x = \infty)$ vs snapshot with $x_{ma x}^{s na p} = 100$ — visible? ::: No — creator is in the reader's future ( $101 \geq 100$ ). Same version alive for reader P but dead for reader Q — possible? ::: Yes (Ex 4): if the deleter's txid falls between their two $x_{ma x}^{s na p}$ values. A version has xmax=140 but txid 140 aborted — alive or dead? ::: Alive (Ex 5) — an aborted deleter's death is a phantom everyone ignores. What does $\infty$ mean in the xmax field? ::: "No deleter yet" — a placeholder beyond every real ticket, so the death test has nothing to check. Two txns edit different rows and break a constraint — what anomaly? ::: Write skew, allowed by Snapshot Isolation. What pins the VACUUM horizon? ::: The oldest still-open transaction's snapshot ( $x_{min}^{s na p}$ ). What does SSI stand for? ::: Serializable Snapshot Isolation.