What an isolation level promises

Two transactions that run at the same time should not see each other half-done. Running them strictly one after another would guarantee that, but would be slow, so SQL lets you choose how much interference you accept. The SQL-92 standard defines the four isolation levels by the anomalies each one must rule out:

leveldirty readnon-repeatable readphantom
READ UNCOMMITTEDpossiblepossiblepossible
READ COMMITTEDnopossiblepossible
REPEATABLE READnonopossible
SERIALIZABLEnonono

The standard was written with locking databases in mind, and phrasing it by anomaly turned out to be leaky: Berenson et al. (1995) showed that a database can avoid all three and still not be serializable. The page runs five short scripts (the three anomalies plus lost update and write skew) under each level and fills in the results matrix with what actually happened. Demo: fill the whole matrix runs all twenty.

The table is accounts(id, balance) with accounts 1 and 2 at 100, written by the committed transaction 90. T1 gets xid 101 and T2 xid 102 at BEGIN. The clock runs one statement per transaction per tick, T1 first; the timeline under the columns shows each transaction's state at every tick.

MVCC: versions, not overwrites

In a multi-version database an UPDATE never overwrites a row. It marks the current version as ended (xmax = its xid) and writes a new version (xmin = its xid). pg_xact (the commit log) records for every xid whether it is in progress, committed or aborted. A reader decides which version it sees by comparing xmin and xmax with its snapshot {xmin, xmax, in progress}: every xid below xmin had finished when the snapshot was taken, every xid from xmax up had not started, and the list names the ones that were running.

  • A version I wrote myself is visible, unless I have replaced it since.
  • Otherwise it is not visible if its xmin aborted, was in progress, or is ≥ the snapshot's xmax: it was not committed as of my snapshot.
  • If its xmin is fine, it is visible unless its xmax is a transaction that had committed as of my snapshot (then it was already replaced).

Worked example (non-repeatable read at REPEATABLE READ): T1's first SELECT at t 2 takes the snapshot xmin 101 · xmax 102 · in progress []. T2 begins later (xid 102), writes 50 and commits. At t 6 T1 looks at account 1 again: version (50, 102/–) has xmin 102 ≥ xmax 102, "started after my snapshot" → ✗; version (100, 90/102) has xmin 90 committed and xmax 102 also after the snapshot → ✓. T1 reads 100 again, although 50 is committed. At READ COMMITTED the second SELECT takes a new snapshot with 102 committed, so it reads 50.

Two heap versions of account 1: balance 100 with xmin 90, xmax 102, and balance 50 with xmin 102. T1's snapshot (xmin 101, xmax 102, none in progress) sees the 100 version and not the 50 version, because xid 102 started after the snapshot.
A reader does not take locks: it compares each version's xmin and xmax with its snapshot and picks the one that was committed as of that snapshot.

So readers never wait for writers and writers never wait for readers: a reader just picks an older version. And most of the isolation level is when the snapshot is taken: READ COMMITTED takes a new one for every statement, REPEATABLE READ and SERIALIZABLE take one at the first statement of the transaction and keep it. Demo: versions, not overwrites shows two versions of account 1 and a reader that skips the uncommitted one.

Two timelines of T1 and T2: T1 SELECTs at t2, T2 updates to 50 and commits at t4, T1 SELECTs again at t6. Under READ COMMITTED T1 takes a new snapshot at t6 and reads 50; under REPEATABLE READ it keeps the t2 snapshot and reads 100 again.
The isolation level is mostly when the snapshot is taken: per statement (READ COMMITTED) or once per transaction (REPEATABLE READ).

PostgreSQL and InnoDB

The page draws PostgreSQL's layout: every version is a tuple in the table's heap, with xmin/xmax in its header, and VACUUM removes the dead ones later (see How PostgreSQL Runs a Query). InnoDB updates the row in place in the clustered index and keeps the older versions in the undo log; a reader with an older read view (InnoDB's snapshot) follows DB_ROLL_PTR back through the undo records to rebuild the version it may see, and purge throws undo away once no read view needs it (see How MySQL Runs a Query). The visibility question is the same in both.

READ UNCOMMITTED differs. PostgreSQL accepts the name but behaves as READ COMMITTED, so it has no dirty reads at all. InnoDB really reads the newest version, committed or not. The page uses InnoDB's behaviour for this one level, so that the dirty read can be shown.

The anomalies, one script each

  • Dirty read: T1 reads a value that T2 wrote and has not committed. In the script T2 sets account 1 to 50 and rolls back: under READ UNCOMMITTED T1 has read a value that never existed. Every other level reads through a snapshot, where 102 is in progress, so it skips the version.
  • Non-repeatable read: T1 reads the same row twice and gets two committed values, because T2 committed in between. Seen at READ COMMITTED (new snapshot per statement), prevented from REPEATABLE READ up.
  • Phantom: T1 runs the same predicate query twice (SELECT COUNT(*), SUM(balance) WHERE balance >= 100) and a new row shows up the second time, because T2 inserted it. The standard still allows this at REPEATABLE READ; a snapshot does not show it, so PostgreSQL's REPEATABLE READ is stronger than the standard requires (marked * in the matrix).

Writers still lock: the lost update

T1 and T2 both read account 1 (100) and add to it: T1 writes 110, T2 writes 120, each computing the value in the application from its own read. Correct would be 130. Two writers of the same row never run together at any level: T2's UPDATE finds the row locked by T1 (in PostgreSQL: T1's xid in xmax) and waits. What happens when T1 commits depends on the level:

  • READ COMMITTED: T2 follows the version chain to the newest version (110), re-checks its WHERE and applies its SET there. PostgreSQL calls this EvalPlanQual. T2 writes 120 and T1's +10 is lost, though no one ever saw uncommitted data.
  • REPEATABLE READ / SERIALIZABLE: T2 may not update a version its snapshot cannot see, so it fails with ERROR 40001: could not serialize access due to concurrent update: the first updater wins. Account 1 is 110 and T2 is aborted. With retry on 40001, the app runs T2 again as xid 103: it reads 110 and writes 130.

Ways to avoid the lost update at READ COMMITTED: let the database compute it (SET balance = balance + 20; choose write style: balance + d and it ends at 130 with no retry), lock the row when reading it (SELECT … FOR UPDATE), or use an optimistic version column (UPDATE … WHERE id = 1 AND version = 7, retry if it matched 0 rows). Demo: lost update shows three of them.

InnoDB's REPEATABLE READ is different. A plain SELECT reads the snapshot, but UPDATE, DELETE and locking reads work on the latest committed row, not on the snapshot, and never raise a serialization error. So InnoDB at REPEATABLE READ does lose T1's update in this script, like READ COMMITTED. Locking reads there take next-key locks (the record plus the gap before it) so that no one can insert into a range the transaction has scanned.

Write skew: snapshot isolation is not serializable

Accounts 1 and 2 are a joint account with overdraft protection: the rule is balance(1) + balance(2) ≥ 0. T1 and T2 each check the total (200 ≥ 150) and withdraw 150, T1 from account 1 and T2 from account 2. They write different rows, so no lock ever conflicts, and each sees a consistent snapshot in which its withdrawal is allowed. At REPEATABLE READ both commit and the total is −100: a state no serial order could produce. The textbook story is the same: two doctors on call, each checks that the other is on call and goes home.

REPEATABLE READ in PostgreSQL is snapshot isolation. It prevents all three anomalies of the standard's table and the lost update, and still allows write skew.

T1 and T2 both see SUM 200 ≥ 150, then T1 sets account 1 to −50 and T2 sets account 2 to −50, different rows, and both commit. Under REPEATABLE READ the total is −100 and the rule is broken; under SERIALIZABLE the two rw-dependencies make T2's COMMIT fail with 40001 and the total stays 50.
Two transactions that each check the rule on their own snapshot and write different rows can break it together; only SERIALIZABLE catches this.

SERIALIZABLE: serializable snapshot isolation (SSI)

PostgreSQL's SERIALIZABLE (since 9.1) keeps snapshot isolation and watches for the dangerous pattern:

  • Every read leaves a SIREAD mark: on the tuple for a point read, on the page or the whole relation for a scan. These are not locks; nothing waits on them.
  • When a transaction writes something a concurrent serializable transaction has read (or reads past a concurrent transaction's new version), that is an rw-antidependency reader → writer: the reader must come first in any serial order. The page draws them as purple arrows between the columns.
  • A dangerous structure is two consecutive rw-antidependencies T_in → T_pivot → T_out between concurrent transactions. With two transactions, arrows both ways: T1 must come before T2 and T2 before T1. PostgreSQL aborts one of them with ERROR 40001: could not serialize access due to read/write dependencies among transactions. The page always aborts the one that commits second, at its COMMIT.

In the write-skew script at SERIALIZABLE, both SUMs mark the relation; T1's write of account 1 creates T2 → T1, T2's write of account 2 creates T1 → T2, and T2's COMMIT fails: the balances are −50 and 100, total 50. With retry on, T2 runs again, sees the total 50 < 150 and withdraws nothing.

SSI can have false positives: it tracks at tuple, page and relation granularity and promotes many tuple marks to a page or relation mark, and it does not check that the cycle really closes, so it may abort a transaction that was in fact safe. Read-only transactions can declare SET TRANSACTION READ ONLY DEFERRABLE: they wait for a snapshot that can never be part of a dangerous structure and then run without any SSI overhead or risk of abort.

Retrying is part of the contract

At REPEATABLE READ and SERIALIZABLE a 40001 is a normal answer, not a bug. The application must be ready to run the whole transaction again from BEGIN, re-reading everything, because the values it read before are exactly what was out of date. Keep transactions short, and make any side effect outside the database (an e-mail, a message) happen after the commit, or idempotent, so that a retry cannot do it twice.

What the page leaves out

  • xids are handed out at BEGIN; PostgreSQL assigns one at the first write and gives readers only a virtual xid.
  • SSI raises its error at the second COMMIT; PostgreSQL may raise it earlier, at the write or read that completes the dangerous structure. SIREAD marks are per row or per relation, never per page, and there are no false positives from granularity promotion.
  • The rw-antidependency and waiting lines are solid colored arrows (the drawing library has no dashed lines). A read draws an arrow only to the version it returns; the ✓ / ✗ marks show every version it examined.
  • Lock waits have no timeout and no deadlock detection; free mode refuses a statement that would close a wait cycle.
  • An error aborts the transaction at once (PostgreSQL leaves it in an "aborted, waiting for ROLLBACK" state). The duplicate-key check for INSERT (3, 100) always reports 23505.
  • VACUUM, hint bits, HOT updates, xid wraparound, subtransactions and savepoints, SELECT … FOR UPDATE / FOR SHARE, predicate locks at page granularity, and SERIALIZABLE by strict two-phase locking as in InnoDB and SQL Server.

See also Saga vs two-phase commit (what happens to isolation across services) and Readers–writers (the same questions with plain locks). The app-level fixes for a lost update, SELECT … FOR UPDATE vs a version column, run side by side in Optimistic vs Pessimistic Locking.