In a database that keeps multiple versions of each row, what stamps are recorded on a row version when it is created or superseded, and how does the engine use those stamps to decide whether a particular transaction may read that version?
answer
- creator stamp + expirer stamp per version
- UPDATE = expire old + create new
- stamp says who, not whether it committed
- commit log / hint bits resolve status
- aborted rows stay on disk, just invisible
basics
~20 sEvery row version records the id of the transaction that created it and, once superseded or deleted, the id of the transaction that expired it. A reader sees a version only if its creator had committed as of the reader's snapshot and its expirer had not.
solid answer
~60 sA multi-version engine never overwrites a live row in place for concurrent readers. Each **row version** carries two stamps: a *creator* transaction id (written by the INSERT or by the UPDATE that produced this version) and an *expirer* transaction id (written by the DELETE or UPDATE that superseded it; empty while the version is current). An UPDATE is logically a delete plus an insert: it stamps the old version as expired by the updating transaction and writes a new version created by it. Visibility is then a two-part test against the reader's snapshot: the version is visible if its creator **committed before the snapshot was taken**, and its expirer is absent, aborted, or **not yet committed as of the snapshot**. Crucially the stamp says *who*, not *whether it committed* — the engine consults a separate commit-status structure (a commit log / transaction status map) and usually caches the answer on the row so later readers skip the lookup. An aborted transaction's versions simply stay on disk and fail the test forever.
code
text · 8 linesversion A: creator=100 expirer=140 value='draft'
version B: creator=140 expirer=175 value='review'
version C: creator=175 expirer=- value='final'
reader whose snapshot sees {100 committed, 140 committed, 175 in flight}
-> A: creation visible, expiry (140) visible => deleted, skip
-> B: creation visible, expiry (175) not visible => VISIBLE
-> C: creation (175) not visible => skipgo deeper
Be able to state that each version records who created it and who expired it, that UPDATE creates a new version, and that a reader picks the version matching its snapshot.
Add that the stamp is identity only — commit status comes from a separate transaction-status structure with hint-bit caching — and that transaction ids order by start, not by commit.
Connect the mechanics to operational symptoms: rolled-back loads still consume space, first-read-after-write slowness from hint bits, delete not freeing space, and cheap rollback versus expensive undo-based rollback designs.
Discuss the design axis: txid-plus-in-flight-list versus commit-timestamp stamping, what each costs at commit and at read time, and how the choice constrains distributed or multi-node read consistency.
## The problem being solved If a database overwrote a row in place, a transaction that started before the change and one that started after would have to fight over the same bytes — one of them must be blocked or given wrong data. Multi-version concurrency control (MVCC) sidesteps this: an update creates a **new version** of the row and keeps the old one around, so different transactions can each read the version that matches *their* point in time. To make that work, every version must be labelled with when it came into existence and when it ceased to exist. ## The two stamps Each row version carries, in its header: - a **creator id** — the transaction id (txid) of the transaction that produced this version. PostgreSQL calls it `xmin`; InnoDB stores a `DB_TRX_ID`; Oracle-family designs record an equivalent change number. - an **expirer id** — the txid of the transaction that deleted this version or replaced it with a newer one. PostgreSQL calls it `xmax`; it is null/zero while the version is the current one. A transaction id is just a monotonically increasing number handed out when a transaction first needs to write (some engines assign lazily, so read-only transactions never burn an id). Ordering of ids therefore reflects *start* order, not *commit* order — a fact that matters enormously for snapshot rules. ## What INSERT, DELETE and UPDATE actually do - **INSERT**: write one version with creator = my txid, expirer = empty. - **DELETE**: do not remove the bytes; set expirer = my txid on the current version. - **UPDATE**: the logical equivalent of delete + insert. Stamp the old version's expirer = my txid, and write a new version whose creator = my txid. In an append-style engine that new version is a new physical tuple; in an undo-style engine the current row is modified in place and the prior image is written to an undo record, but the logical stamping is the same idea. So a row that has been updated three times leaves a *chain* of versions whose creator/expirer stamps interlock: version N's expirer equals version N+1's creator. ## The visibility test Given a reader holding a snapshot, a version is visible when **both** hold: 1. **Creation is visible**: the creator transaction committed, and it committed "before" the snapshot — i.e. the snapshot considers that txid finished. (The reader's own txid also counts as visible to itself.) 2. **Expiry is not visible**: either there is no expirer, or the expirer transaction aborted, or the expirer is still in flight / started after the snapshot — so from the snapshot's viewpoint the row has not been deleted yet. If creation is not visible, the row does not exist yet for this reader. If creation is visible but expiry is also visible, the row has been deleted for this reader. Exactly one version of a given logical row passes both tests for a given snapshot, which is what makes reads consistent. ## Stamps record identity, not outcome A common misunderstanding: the stamp does not say "committed". When transaction 500 inserts a row and then rolls back, the version stays on disk with creator = 500. Rollback in a multi-version engine is therefore cheap — it flips one entry in the transaction status map from *in progress* to *aborted*, and every reader that consults that map now judges the version invisible. The engine keeps a commit log (PostgreSQL's `pg_xact`/clog, InnoDB's rollback-segment state, Oracle's transaction table) and typically caches the resolved answer as **hint bits** on the version so the second reader does not repeat the lookup. ## Timestamps instead of raw ids Some engines stamp with a commit timestamp or a global sequence number (Oracle's SCN, InnoDB's read-view limits, distributed systems' hybrid logical clocks) rather than comparing against a list of ids. The principle is unchanged: a version is visible when its creation stamp precedes the reader's read point and its expiry stamp does not. Commit-timestamp designs have the nice property that the stamp is assigned at commit, so ordering by stamp is ordering by commit — at the cost of having to fix up the stamp after the fact or indirect through a transaction table. ## Why this matters in practice Understanding the stamps explains behaviours engineers meet daily: why a rolled-back bulk load still consumed disk space, why a delete does not immediately free space, why the first read after a big write is slower than the second (hint-bit setting), and why an update of an unindexed column can still be an expensive operation. It is also the foundation for the snapshot rules that decide *which* committed transactions count as "before" the reader.
- If a transaction inserts a million rows and then rolls back, what happens to those row versions?They stay physically on disk exactly as written, with their creator stamp pointing at the aborted transaction. Rollback only marks that transaction as aborted in the commit-status structure, so every subsequent visibility test rejects those versions. The space is reclaimed later by the engine's background cleanup, not by the rollback itself.
- Why does the engine need a separate commit log rather than storing 'committed: true' directly on the row version?A transaction can touch millions of versions, and commit must be a single atomic act. Writing a flag on every version at commit time would make commit O(rows touched) and non-atomic. Instead commit flips one status entry, and readers resolve status by lookup — with the resolved answer cached back onto the version as a hint so the cost is paid once, lazily.
- Does a read-only transaction get a transaction id?In most engines, no — ids are assigned lazily on first write, because ids are a finite, contended resource and stamps only matter for writers. A read-only transaction still gets a snapshot, which is what it needs to evaluate visibility; it simply has no id to appear in anyone else's stamps.
Think of a shared document where nobody erases: each edit is filed as a new page marked "written by clerk #47" and the previous page gets stamped "superseded by clerk #47". A separate ledger says which clerks actually signed off. To read the document as of a moment, you take the one page whose writer had signed off by then and whose superseder had not.
saying these in an interview costs you the question
- Saying the old row is overwritten and the previous value is kept 'in the log' for rollback only — conflating write-ahead logging with row versioning.
- Claiming the creator stamp means the transaction committed, so no commit-status lookup is needed.
- Believing a DELETE immediately removes the row bytes.
- Saying an UPDATE modifies the row in place and only bumps a version counter, with no new version and no expirer stamp.