The idea: is this interleaving as good as a serial run?

A database runs many transactions at the same time, so their reads and writes get mixed. Running them one by one (a serial run) is always correct, but slow. So the question is: given one mixed order, is its effect the same as some serial run? Conflict serializability gives a simple test. Find the pairs of operations whose order matters, draw them as arrows between the transactions, and look for a cycle.

Three steps from left to right. A schedule of read and write operations of T1 and T2. Then the conflicting pairs, each giving an edge from the earlier transaction to the later one. Then the precedence graph: with no cycle the schedule equals a serial run, with a cycle it does not.
The test in three steps: the schedule, its conflicts, and the graph they make.

The canvas shows the schedule as a grid (one row per transaction, time goes right), the data items A, B and C, the precedence graph, and a table that compares the schedule's final values with every serial run.

Schedules and the three programs

A schedule is one fixed order of all the operations. r1(A) means T1 reads item A, and w2(A) means T2 writes A. Inside the schedule each transaction keeps its own order; only the mixing between transactions changes. The items start at A = 100, B = 200 and C = 300.

To get real numbers, each transaction runs one small program on every item it touches:

transactionprogramneeds a read first?
T1X = X + 10yes
T2X = X × 2yes
T3X = 50no (a blind write)

A read copies the item into the transaction's own copy. A write computes the new value from that copy, not from what the item holds at that moment. The order of these programs matters: (100 + 10) × 2 = 220, but 100 × 2 + 10 = 210.

Which operations conflict

Two operations conflict when all three of these hold:

  • they are on the same item,
  • they belong to different transactions,
  • at least one is a write.
earlierlaterconflict?why
r1(A)r2(A)notwo reads see the same value in either order
r1(A)w2(A)yesswapped, T1 would read T2's value
w1(A)r2(A)yesswapped, T2 would read the old value
w1(A)w2(A)yesswapped, the other value would be left in A
w1(A)w2(B)nodifferent items

Two neighbours that do not conflict can be swapped without changing any value read or written. If such swaps can turn a schedule into a serial one, the schedule is conflict-serializable.

The precedence graph

Trying all swaps is slow. The precedence graph (also called the serialization graph) gives the answer directly. It has one node per transaction. For every conflicting pair it gets an edge Ti → Tj, where Ti's operation came first. The edge says: in any equivalent serial schedule, Ti must run before Tj. Many pairs can give the same edge; the page then only adds the item to the edge's label.

On the page, each Add Op runs the operation, lights the earlier operations it conflicts with, and draws the edge. Demo: serial schedule, T1 then T2 gives a single edge T1 → T2. Demo: interleaved but serializable mixes the two transactions on A and on B, but every conflict still points from T1 to T2.

The lost update schedule r1(A), r2(A), w1(A), w2(A) with A starting at 100. T1 writes 110, then T2 writes 200 from its old copy. The conflict r2(A) before w1(A) gives the edge T2 to T1, and r1(A) and w1(A) before w2(A) give T1 to T2: a cycle. Serial runs give 220 or 210, the schedule gives 200.
The lost update: both read A = 100, both write, and the two edges point opposite ways.

Cycle or no cycle

If the graph has a cycle, the schedule is not conflict-serializable. A cycle T1 → T2 → T1 says T1 must run before T2 and T2 before T1. No serial order can do both.

If the graph has no cycle, the schedule is conflict-serializable, and any topological order of the graph is an equivalent serial schedule. Test Graph finds it the usual way: take a transaction with no incoming edge, remove it, and repeat (see topological sort by indegree). If the sort gets stuck, the transactions that are left form a cycle.

Left: a graph with edges T2 to T1 and T1 to T3 has no cycle, so the serial order is T2, T1, T3. Right: a graph with edges T1 to T2, T2 to T3 and T3 to T1 is a cycle through all three, so there is no serial order.
No cycle: read the serial order off the arrows. A cycle: there is no order to read.

The serial order need not follow the transaction numbers or who started first. In Demo: three transactions, order T2 → T1 → T3 the edges are T2 → T1 (on A) and T1 → T3 (on B). A cycle also need not be between two transactions: in Demo: three transactions, a cycle through all three no pair has edges both ways, yet T1 → T2 → T3 → T1 closes a loop.

What goes wrong: real values

Compare Serial runs the same transactions one by one in every possible order and lists the final values.

demographthe schedule ends withserial runs give
interleaved but serializableT1 → T2, no cycleA = 220, B = 420T1, T2: 220, 420 (same ✓) · T2, T1: 210, 410
lost updateT1 ⇄ T2, cycleA = 200220 or 210, never 200 ✗
two items, opposite ordersT1 → T2 on A, T2 → T1 on BA = 220, B = 410220, 420 or 210, 410 ✗
order T2 → T1 → T3no cycleA = 210, B = 50only T2, T1, T3 of the 6 runs is the same ✓
a cycle through all threeT1 → T2 → T3 → T1A = 60, B = 420, C = 50none of the 6 runs ✗

In the lost update, T1 and T2 both read A = 100. T1 writes 110. Then T2 writes 100 × 2 = 200 from its old copy, and T1's + 10 is gone. In the "opposite orders" demo each item alone looks fine: A was updated in the order T1, T2 and B in the order T2, T1. Only together they match no serial run.

Two serial runs may give different values (220 or 210). Both are correct: a database promises the result of some serial order, not of one chosen order.

What MariaDB does instead

MariaDB does not build a precedence graph. Testing a schedule after it ran would be too late. InnoDB instead stops bad schedules while they happen, with row locks held until commit (strict two-phase locking). A lock makes the second transaction wait, so every conflict on a row points the same way and a cycle in the precedence graph cannot form. If the waits themselves form a cycle, InnoDB's deadlock detector rolls one transaction back with ERROR 1213 (40001), and the application runs it again.

How much is locked depends on the isolation level, set with SET TRANSACTION ISOLATION LEVEL …:

levelplain SELECTthe lost update above
REPEATABLE READ (the default)reads a snapshot, takes no lockcan happen when the application reads, computes and then writes
SERIALIZABLEtakes a shared lock, like SELECT … LOCK IN SHARE MODE (when autocommit is off)both hold a shared lock and both want to write: a deadlock, one is rolled back

At the default level you prevent the lost update yourself. Read with SELECT … FOR UPDATE, so the second reader waits for the first writer. Or let the server do the read and the write in one statement: UPDATE account SET balance = balance + 10 WHERE id = 1. See InnoDB isolation: snapshot reads vs current reads and MVCC and isolation levels.

Other ways to get the same guarantee without locks: timestamp ordering fixes the serial order in advance, and PostgreSQL's serializable snapshot isolation watches for a dangerous pattern of edges while transactions run.

See also recoverable, cascadeless and strict schedules, where transactions abort and a rollback can reach the transactions that read their data.

See also Validation-Based Optimistic Concurrency Control, where the validation order fixes the serial order.

What the page leaves out

Aborts and commits: every transaction here commits, so recoverable, cascadeless and strict schedules are not shown. View serializability: with blind writes a schedule can have a cycle and still equal a serial run; the conflict test is safe but stricter than needed (try r1(A), w3(A), w1(A), w3(A)). Comparing final values is also a weaker check than the graph: values can match by luck. Predicates and phantoms, where the conflict is on rows that do not exist yet (InnoDB uses gap locks for those). MariaDB has no command that shows a precedence graph or tests a schedule.

On the mind map

Open the Databases & Storage mind mapDatabases& StorageSchema and storage: how rows land on diskSchema and storageIndexes: find rows without a full scanIndexesRunning a query: parse, plan, executeRunning a queryCost-based optimizer: estimate rows, pick cheapest planCost-based optimizerQuery rewrites: same answer, simpler queryQuery rewritesTransactions: ACID: isolation and recoveryTransactionsApps and connections: the client side of the databaseApps and connectionsMongoDB: documents, replica sets, shardsMongoDBMVCC and isolationMVCC and isolationreaders see a snapshot of row versionsTwo-phase lockingTwo-phase lockinggrow locks, then release; detect cyclesConflict serializabilityCycle in precedence graph = not serializableRecoverable schedulesRecoverable schedulesCommit only after those you read fromWait-Die and Wound-WaitWait-Die and Wound-WaitAge decides who waits and who rolls backMultiple Granularity LockingMultiple Granularity LockingIntention locks on every ancestorOptimistic vs pessimisticOptimistic vs pessimisticversion check vs SELECT FOR UPDATEValidation-based OCCValidation-based OCCCheck read/write sets at commit, else abortWAL and ARIESWAL and ARIESlog first; redo all, then undo losersTimestamp orderingTimestamp orderingolder timestamp wins; late writes abortOpen the Databases & Storage mind mapDatabases & StorageACID: isolation and recoveryTransactionsMVCC and isolationMVCC and isolationreaders see a snapshot of row versionsTwo-phase lockingTwo-phase lockinggrow locks, then release; detect cyclesConflict serializabilityCycle in precedence graph = not serializableRecoverable schedulesRecoverable schedulesCommit only after those you read fromWait-Die and Wound-WaitWait-Die and Wound-WaitAge decides who waits and who rolls backMultiple Granularity LockingMultiple Granularity LockingIntention locks on every ancestorOptimistic vs pessimisticOptimistic vs pessimisticversion check vs SELECT FOR UPDATEValidation-based OCCValidation-based OCCCheck read/write sets at commit, else abortWAL and ARIESWAL and ARIESlog first; redo all, then undo losersTimestamp orderingTimestamp orderingolder timestamp wins; late writes abort
This page on the Databases & Storage mind map · 55 pages in 8 branches · open it to see the whole map and test yourself in recall mode.