Visual walkthrough — MVCC — multi-version concurrency control

We assume you know only this: a database stores rows, and many people (transactions) touch it at once. Everything else — versions, txids, snapshots, the rule — we grow on-screen.

---

Step 1 — What is a "transaction id", really?

WHAT. Every time someone opens a new job on the database (start reading, start writing), the database hands them a numbered ticket. That number is the transaction id (we write it txid). Tickets are handed out in order: 1, then 2, then 3… never repeating, never going backwards.

WHY. Ordering is the whole game. If I can compare two ticket numbers, I can ask "did this happen before or after that?" — and "before/after" is exactly what decides who is allowed to see whose work.

PICTURE. Below, a number line of tickets. The little clock hand points at the next ticket to be given out. Everything to the left already exists; everything to the right hasn't happened yet.

---

Step 2 — One row becomes a chain of versions

WHAT. In a locking database, a row has exactly one value. In MVCC, an update never overwrites — it writes a new copy and leaves the old copy sitting there. So a single logical row (balance) becomes a stack of versions stitched together — a version chain.

WHY. This is the trick that lets readers avoid waiting. If the old copy is still lying around, a reader who is "living in the past" can read it while a writer builds the new copy. Nobody blocks anybody.

PICTURE. Two boxes for the same logical row. Each box carries two stamps:

$\underset{\text{txid that }\text{created}\text{ this version}}{\underbrace{xmin}}\underset{\text{txid that }\text{killed}\text{ this version, or }\infty \text{ if still alive}}{\underbrace{xmax}}$

• $xmin$ = birth certificate — who wrote this version.
• $xmax$ = death certificate — who superseded/deleted it. If nobody has, it is $\infty$ ("still live").

Notice the handshake: when txid 101 updates the row, the old box's $xmax$ becomes 101 (it died at 101's hand) and the new box's $xmin$ becomes 101 (it was born from 101). Same number, two roles.

---

Step 3 — Freezing a moment: the snapshot

WHAT. When a transaction starts reading, it takes a snapshot: a frozen note of "who had already committed right now". Three pieces:

$\text{snapshot }S=(\underset{\text{oldest txid still running}}{\underbrace{x_{min}^{snap}}},\underset{\text{next txid to be handed out}}{\underbrace{x_{max}^{snap}}},\underset{\text{txids in-progress right now}}{\underbrace{\text{active set}}})$

• $x_{max}^{snap}$ = the clock hand from Step 1. Anything $\ge$ this is in my future — it hadn't even started when I froze time.
• active set = the txids that had started but not yet committed at the freeze instant. They are "in flight".
• $x_{min}^{snap}$ = the smallest still-running txid; useful later for garbage collection, but the rule mainly needs the other two.

WHY. A reader doesn't want the latest value — it wants a consistent one. "Consistent" = "the world exactly as it looked at one single instant." The snapshot is that instant, bottled.

PICTURE. The number line again, now split into three coloured regions by one transaction's snapshot: the committed past (visible), the in-flight holes (active set — invisible even though their numbers are in the past), and the future (everything $\ge x_{max}^{snap}$, invisible).

---

Step 4 — When can I see a birth? (the $xmin$ test)

WHAT. Take one version. Ask only about its creator $xmin$. It counts as born-for-me when all three hold:

$\underset{\text{(a) creator finished}}{\underbrace{\text{committed}(xmin)}}\wedge \underset{\text{(b) not a hole in my past}}{\underbrace{\neg \text{inActive}(xmin,S)}}\wedge \underset{\text{(c) not in my future}}{\underbrace{xmin<x_{max}^{snap}}}$

WHY each clause — derived, not memorised:

• (a) committed — if the creator never committed, its data is uncommitted garbage. Reading it = reading dirty data. Forbidden.
• (b) not in active set — even if it commits later, at my freeze instant it was in-flight. To keep one consistent instant I must pretend it never happened.
• (c) $xmin<x_{max}^{snap}$ — a txid at or beyond the clock hand started after me. It is my future; I can't see the future.

PICTURE. A single version's $xmin$ dropped onto the three-region number line. Green light only if it lands in the committed-past region and isn't a hole.

---

Step 5 — When is a death still hidden? (the $xmax$ mirror)

WHAT. Now the deleter $xmax$. A version is still-alive-for-me when its death has not yet happened from my point of view:

$\underset{\text{nobody killed it}}{\underbrace{xmax=\infty }}\vee \underset{\text{killer isn’t visible to me}}{\underbrace{\neg V_{create}(xmax)}}$

WHY. A deletion only "takes effect" for me if the deleting transaction is itself visible to me — by the exact same three tests from Step 4. If the killer is in my future, or a hole, or uncommitted, then for me the row was never killed. It still looks alive.

PICTURE. The mirror image of Step 4. Same green/red machine, but green here means "death is hidden → row still alive". Note the logic flips: creator visible = good; deleter visible = bad (it means the row is gone for me).

---

Step 6 — Assembling the full rule

WHAT. Glue Steps 4 and 5:

$\boxed{\text{Visible}(v,S)\equiv \underset{\text{birth I can see}}{\underbrace{V_{create}(xmin)}}\wedge \underset{\text{death I can NOT see yet}}{\underbrace{(xmax=\infty \vee \neg V_{create}(xmax))}}}$

WHY. These two conditions are independent and both necessary. Miss the first → you'd read something not yet born (dirty/future). Miss the second → you'd keep reading something already deleted for you (stale).

PICTURE. A 2×2 truth grid: birth-visible? (yes/no) crossed with death-hidden? (yes/no). Only one cell is green — top-left.

Try each cell:

---

Step 7 — Replaying Worked Example 1 through the machine

WHAT. Row balance = 100. Clock at 50. Reader T100 takes its snapshot ($x_{max}^{snap}=100$, active set $=\{\}$). Then writer T101 updates to 200 and commits. What does T100 read?

WHY replay it? To prove the abstract boxes give the "obvious" human answer: T100 started first, so it should see 100.

Two versions now exist:

version	value	$xmin$	$xmax$
old	100	(earlier)	101
new	200	101	$\infty$

Run each through Step 6:

• New version ($xmin=101$): test (c) $101<x_{max}^{snap}=100$? False — 101 is in T100's future. $V_{create}$ fails → invisible.
• Old version ($xmax=101$): is the deleter 101 visible? Same test: $101<100$? False → killer invisible → death hidden → old version alive → T100 reads 100. ✅

PICTURE. Both versions plotted on T100's number line; 101 sits to the right of the clock hand, so it's greyed out in both roles.

No waiting happened anywhere. Reader didn't block writer; writer didn't block reader — the promise, delivered by arithmetic on ticket numbers.

---

Step 8 — The edge cases (never leave a scenario unshown)

WHAT & WHY. The rule must survive weird inputs. Four corners:

1. $xmax=\infty$ (never deleted). Death clause is trivially true → visibility rides entirely on the birth test. The most common case — a live, untouched row.
2. Self-visibility (I read my own uncommitted write). Your own txid is not "committed" globally yet, but the engine special-cases it: a transaction always sees its own changes. So $xmin=$ my txid $\Rightarrow$ born-for-me even though not committed.
3. Aborted creator. $\text{committed}(xmin)$ is false (it rolled back) → born-for-me fails → invisible forever, to everyone. The version is dead-on-arrival garbage awaiting VACUUM.
4. Deleter in my active set (a hole). A concurrent txn deleted the row but hasn't committed at my freeze instant. Its $xmax$ is in my active set → killer invisible → row still alive for me. I read the pre-delete value.

PICTURE. Four mini-panels, one per corner, each showing where the deciding txid lands and the resulting verdict.

---

The one-picture summary

Everything above collapses into a single decision machine: drop a version's $xmin$ and $xmax$ onto the reader's three-region number line; read off two green/red lights; VISIBLE = born-light green AND death-light red.

This is exactly Snapshot Isolation's reading rule; layering write-conflict detection on top gives the road toward Serializability, while Two-Phase Locking (2PL) is the pessimistic alternative it replaces (see Optimistic vs Pessimistic Concurrency Control).

Recall Feynman: the walkthrough in plain words

Every job gets a numbered ticket, in order. When you change a row, you don't erase the old one — you make a fresh copy and note "born by ticket #N" on it, and stamp "killed by ticket #N" on the old one. When you start reading, you snap a photo of "who has finished so far" and "what the next ticket number is." Now to decide if a copy is real for you: you must be able to see its birth (its creator finished, wasn't mid-flight when you snapped, and isn't a future ticket) and you must NOT yet be able to see its death (its killer is either nobody, or a ticket you also can't see). Both lights right → you read it. Because the old copy is still there, you never wait for the writer, and the writer never waits for you. The only fight left is two writers grabbing the same copy — that one still needs a lock.

Recall Predict before you close the tab

A reader holds a snapshot with $x_{max}^{snap}=100$. A row version has $xmin=100$, committed. Visible? Answer ::: No — test (c) needs $xmin<x_{max}^{snap}$, but $100<100$ is false. Ticket 100 started at or after the snapshot instant → future → invisible.