CS PAPERS DEEP-READ · PAPER 62
Berenson, Bernstein, Gray, Melton, O'Neil, O'Neil · SIGMOD 1995
Every database has a dial called the isolation level. It decides how much several simultaneous pieces of work are allowed to disturb each other. Turn it tight and you are safe but slow; turn it loose and you are fast but your books may come out wrong. The 1992 international SQL standard put four notches on that dial and described, in a few sentences of plain English, what each notch protects you from. In 1995 six heavyweights of the database world — including the editor of the SQL standard himself, and Jim Gray, one of the founders of transaction processing — wrote this paper and took those sentences apart. Their finding: the plain English can be read two different ways, and the list of hazards it names leaves out several accidents that happen every day.
The standard's description of a "dirty read" runs roughly like this: A changes a row but has not finalized it, B reads that row anyway, and then A changes its mind and cancels — so B has read a number that never really existed. Sounds reasonable.
But the paper points out: taken literally, it is only an accident if A cancels at the end. What if A never changes its mind and finishes normally? B can still read a half-finished ledger — money has left one account and not yet arrived in the other, and B, looking at that moment, sees the total mysteriously short. By the literal reading, that does not count as a violation. One sentence, two readings: the strict one forbids all of these situations, the loose one forbids only a corner of them. This is not hair-splitting — what sits between the two readings is whether your money gets counted wrong.
The paper then lists hazards the standard never mentions but that are common in practice. First: two people change the same spot at once, and the later write quietly erases the earlier one. Even the loosest notch has to prevent that one, or else "cancel" itself stops working — you no longer know which old value to restore. Second: two people each read a balance, each add money, each write it back, and one of the two updates simply evaporates.
The nastiest is the third: two people each look at the same books, each make a decision that is perfectly legal on its own, and together they break the rule. A couple holds two cards on two accounts, and the bank's rule is that the two accounts together must not go into the red. Both check at the same time, both see "a hundred left between us", so one takes eighty from this account and the other takes eighty from that one. Neither withdrawal crosses the line by itself; together they are sixty in the red. Nobody read dirty data, and the books are still wrong.
The paper also tidied up and formally named a technique that databases were already using: snapshot isolation. The intuition: the moment you walk in, someone photographs the entire library for you; from then on, no matter how other people shuffle the books, you only ever look at your own photograph. So reading never has to queue behind anyone, and you never catch anyone mid-shuffle. Your own changes are kept under your name where nobody else can see them, and only come out when you go to the counter to check out. There the clerk runs one test: if someone touched the same book after you walked in and checked out before you did, they win and your whole basket is voided — go do it again.
It is fast and clean, and it blocks nearly every accident above — except the couple at the cash machine: those two touched different books, so the clerk's test finds no collision and waves both through, even though the photographs they each acted on had gone stale.
This paper turned "isolation level" from a paragraph that is easy to misread into a checklist you can go through line by line: for each notch, exactly which accidents are prevented and which are let through. The industry got a shared vocabulary out of it — dirty read, non-repeatable read, phantom, lost update, write skew, snapshot isolation all trace back here.
The standard defined isolation levels in a few sentences of plain English that were both ambiguous (one sentence, two readings, with real money between them) and incomplete (real accidents missing). This paper wrote out, hazard by hazard, what each notch actually prevents, filled in the gaps, and named the "read your own snapshot, first committer wins" technique snapshot isolation — while noting that useful as it is, it cannot stop the case where two decisions are each legal and jointly wrong.
Want the precise notation, the four missing anomalies, and why isolation levels do not line up in a single row? → Switch to the deep read
The 1992 SQL-92 standard defined four isolation levels in terms of three phenomena — dirty read, non-repeatable read, phantom. This paper shows that definition is both ambiguous and incomplete: the English prose admits a loose and a strict reading, and only the strict one survives scrutiny; and the list omits real anomalies such as dirty write, lost update, read skew and write skew. The authors rewrite every anomaly as a precise sequence of operations, complete the list, formally define cursor stability and snapshot isolation, and deliver a structural result: isolation levels are not a straight line — snapshot isolation and REPEATABLE READ are incomparable.
r1[x] for "transaction 1 reads item x", w1[x] for "writes x", c1 for "commits", a1 for "aborts", and r1[P] for "reads the set of rows matching predicate P".The authors are Hal Berenson, Phil Bernstein, Jim Gray (a founder of transaction-processing theory and a Turing Award winner), Jim Melton (editor of the SQL standard), Elizabeth O'Neil and Patrick O'Neil; the work was done at Microsoft Research and published at SIGMOD 1995. The standard's own editor took part in criticizing the standard, which gives the paper unusual weight. It follows Gray et al.'s 1976 lock-based "degrees of consistency" tradition and the SQL-92 text; it leads to Adya's generalized definitions in 1999 and to the whole line of work after 2005 on making snapshot isolation genuinely serializable.
Start with why isolation levels exist at all. The correct thing is obviously to run transactions one at a time (serializable), but throughput then becomes unusable. So engineering strikes a bargain: give up a little correctness, buy back concurrency. And if it is a bargain, the crucial thing is to state precisely what you gave up.
SQL-92's answer was to avoid mentioning locks (so as not to nail down an implementation) and define four levels via three phenomena: dirty read P1 (reading someone's uncommitted data), non-repeatable read P2 (reading a row twice and getting different values), phantom P3 (running the same predicate query twice and finding rows appear or disappear). READ UNCOMMITTED allows all three; READ COMMITTED bars dirty reads; REPEATABLE READ also bars non-repeatable reads; SERIALIZABLE bars all three.
The paper finds three places where that neat table caves in.
One: "implementation independent" is not true. The three phenomena were reverse-engineered from a locking implementation — they line up exactly with Gray's 1976 degrees 1/2/3 (how long you hold read locks, how long you hold write locks). Move to a multiversion implementation and levels and phenomena stop matching: a multiversion system cannot see uncommitted data at all, yet commits other sins.
Two: the English prose is ambiguous. Detailed in the next section.
Three: the list is incomplete — and what it omits happens to be exactly what engineers trip over.
Which surfaces the real problem: an engineer who picks READ COMMITTED by reading the standard does not actually know what they just allowed. Meanwhile DBAs, vendors and the standards committee talk past each other, because they are all reading the same two-way sentence.
The most valuable move in the paper looks almost humble: rewrite each anomaly from an English description into a family of forbidden event sequences. With the notation from the glossary, "dirty read" stops being a sentence whose wording can be argued about and becomes a pattern — any execution shaped like this is forbidden, full stop.
That shifts the argument from "how do you read this sentence" to "does this execution match this pattern". Once something can be checked case by case, people can no longer talk past each other. Everything below follows from this one move.
Take dirty read first. The standard's English says: T1 modifies a row, T2 reads it before T1 commits, and if T1 then rolls back, T2 has read a value that was never committed. Read literally, what is forbidden is this pattern (the paper calls it A1): w1[x] … r2[x] … (a1 and c2 in either order) — note the a1: it only counts if T1 aborts at the end.
The paper argues the pattern that should be forbidden is the broader one (P1): w1[x] … r2[x] … (c1 or a1) — the moment T2 reads an x that T1 has not committed, it counts, whatever happens afterwards.
Why must it be the broad reading? One counterexample is enough. Let x and y be two accounts holding 50 each, under the business constraint x + y = 100. T1 transfers 40 from x to y:
Non-repeatable read and phantom go the same way: read literally, each demands that the same transaction read again and find a difference — so a transaction that reads once and then acts on it can be wrecked without the standard calling it a violation. The strict reading instead forbids the underlying event: someone modifying what T1 has read while T1 is still running.
The strict reading buys something decisive: only under it does "exclude P1, P2, P3" become equivalent to lock-based serializability. Under the literal reading, a level that excludes A1, A2 and A3 is not serializable — the paper coins the name ANOMALY SERIALIZABLE for that misnamed level. The standard's SERIALIZABLE sits suspended between the two readings.
Once the notation is laid out, the gaps are obvious.
Dirty write, P0: w1[x] … w2[x] … (c1 or a1). Two uncommitted transactions write the same item in turn. The standard never mentions it, yet the paper shows every level must forbid it, including the loosest one. The reason is hard: otherwise rollback is meaningless — when T1 aborts, what should x be restored to? Its old value has already been overwritten by T2. And constraints across items shatter: under the constraint x = y, if T1 wants both set to 1 and T2 wants both set to 2, an interleaving can leave x=1, y=2, with both transactions having "run in full" and the constraint broken. So even the loosest notch is not a free-for-all — it must hold its write locks until commit.
Lost update, P4: r1[x] … w2[x] … w1[x] … c1. Read a balance, add to it, write it back. Two people do that at once and T2's contribution evaporates, because T1 computed its new value from a stale read and then pasted it over. READ COMMITTED does not stop it (the read lock is dropped immediately); REPEATABLE READ does; this is probably the most common concurrency bug in application code. The cheap variant that protects only the row the cursor is sitting on is P4C, matching the cursor stability notch industry already had and the standard has no slot for.
Read skew, A5A: r1[x] … w2[x] w2[y] c2 … r1[y]. A transaction reads two related items one after another, and in between somebody changes both of them in one go, so it ends up holding an old x and a new y that do not fit together. Every individual value it read was committed; the combination is a state that never existed.
Write skew, A5B: r1[x] r2[y] w1[y] w2[x] (c1 and c2). The subtlest one: each transaction reads what the other is about to modify, each write is legal on its own, and together they break the constraint.
Having closed the gaps, the paper does its second big thing: it pins down the technique multiversion databases were already using but had never formally named — snapshot isolation (SI).
Three steps. (1) A transaction takes a start-timestamp when it begins; from then on it reads only versions committed before that timestamp, plus whatever it wrote itself — the database freezes into a photograph for it. (2) Its writes go into new versions visible only to itself. (3) At commit it takes a commit-timestamp, and the database checks: did any other committed transaction write an item I also wrote within the interval [start, commit]? If so, I am rolled back — first-committer-wins.
The properties are elegant: reads never block writes and writes never block reads; uncommitted versions are invisible to others, so dirty reads and dirty writes cannot occur; the snapshot is frozen, so non-repeatable reads and phantom re-reads cannot occur; first-committer-wins stops lost updates; a single consistent photograph stops read skew.
But it does not stop write skew. The reason is baked into the mechanism: the conflict check only asks whether two transactions wrote the same item, and in write skew they wrote different items. Their conflict lives on the read side, where both snapshots had gone stale, and the check cannot see it. So snapshot isolation is not serializable.
This is the paper's heaviest punch. Try to slot snapshot isolation into the standard's ladder and it simply will not fit. REPEATABLE READ stops write skew (it holds read locks to commit, so the second transaction cannot modify what the first has read) but not phantoms (it does not lock predicates, so new rows can be inserted). Snapshot isolation is the mirror image: the frozen snapshot immunizes it against phantom re-reads, while write skew goes straight through.
Neither contains the other. So the widespread mental image of isolation levels as a line from loose to strict is wrong — it is a partially ordered net. And that is the intrinsic price of defining levels by "which anomalies are excluded": you can compare two sets of excluded anomalies, but sets do not give you a total order.
This is a paper of definitions and arguments: no benchmarks, no performance numbers, and saying so plainly beats inventing figures. Its "results" are three things: a list of anomalies pinned down as event sequences, a level-by-level table, and the strength relations between levels (including the incomparability above). The table reads as an engineering checklist:
The paper then holds that table up against the commercial systems of the day: most default to READ COMMITTED; several offer cursor stability; and Oracle's multiversion "read consistency" belongs to the snapshot-isolation family — what it delivers is not true serializability. (Oracle's SERIALIZABLE mode being snapshot isolation for years afterwards is the footnote to that verdict.)
It gave the whole industry a shared vocabulary. The anomaly list in any database manual today — dirty read, non-repeatable read, phantom, lost update, read skew, write skew — traces back here. Engineers stopped asking "what is this level called" and started asking "which anomalies does this level exclude". The level name is marketing; the anomaly list is the contract.
Snapshot isolation got its name here and went mainstream. PostgreSQL's REPEATABLE READ, MySQL InnoDB's consistent reads, and the SNAPSHOT level added in SQL Server 2005 all belong to this family. The vast majority of applications today run on snapshot isolation or READ COMMITTED, not on serializability.
It launched a research line directly. If snapshot isolation is only one anomaly short, can that gap be closed? Fekete et al. (2005) characterized the "dangerous structures" that make an SI execution non-serializable, and Cahill et al. (2008) built serializable snapshot isolation (SSI) on top of that — track read-write dependencies and abort one side when a dangerous cycle forms. PostgreSQL 9.1 (2011) shipped it, becoming the first mainstream database to offer genuine serializability on a multiversion engine. The starting gun for all of it was this paper's "SI does not exclude A5B".
1. In one sentence: SQL-92 defined four isolation levels via three "phenomena"; this paper proved that definition both ambiguous and incomplete, and closed the gaps.
2. The pain and the method: the standard aimed at implementation independence but was reverse-engineered from locking, so an engineer picking a level from it does not know what they allowed; the paper rewrites every anomaly as a precise event sequence (w1[x] … r2[x] … c1), moving the argument from wording to checkable patterns.
3. The ambiguity: read literally (A1), a dirty read requires T1 to abort; a counterexample — a half-finished transfer observed while T1 goes on to commit — forces the strict reading (P1). Only under the strict reading does excluding the three phenomena amount to serializability.
4. The gaps: dirty write P0 (every level must forbid it, or rollback itself breaks), lost update P4 and its cursor variant P4C, read skew A5A, write skew A5B — none of them in the standard.
5. Snapshot isolation: read from a snapshot frozen at your start-timestamp, keep writes in your own versions, and at commit apply first-committer-wins; readers and writers never block each other. But it does not exclude write skew — the conflict check only asks "did we write the same item", while the conflict lives on the read side; hence SI is not serializable.
6. Structural result: SI and REPEATABLE READ are incomparable (one stops phantoms but not write skew, the other the reverse) — isolation levels form a partially ordered net, not a line.
7. Impact and limitations: it left the industry its anomaly vocabulary, named snapshot isolation and made it where most databases actually run, and led straight to Fekete (2005) → SSI (2008) → PostgreSQL 9.1; but its definitions remain lock-flavored (generalized by Adya in 1999 via serialization graphs), enumerating anomalies can never be complete, and the SQL standard itself was never amended.