The idea: lock big or small, on one tree

A transaction that reads one row wants a small lock, so others can use the other rows. A transaction that reads the whole table wants one big lock, not thousands of row locks. Multiple granularity locking lets both happen. The data is a tree of granules: the database, its tables, each table's pages, each page's rows. A lock on a node locks everything below it. The page uses a database db, one table t, pages P1 and P2, and rows r1 to r4 (with id 1 to 4).

A tree: database db at the top, table t below it, pages P1 and P2 below t, rows r1 and r2 under P1, r3 and r4 under P2. T1 updates r2: it holds IX on db, IX on t, IX on P1 and X on r2, taken in that order from the top. T2 scans the table and asks for S on t, which conflicts with T1's IX.
To update r2, T1 marks the path from the root with IX, then takes X on the row; a table lock request only has to look at t.

The canvas shows the tree with the locks on each node, the compatibility matrix with the last check marked, and a panel for each of the two transactions, T1 and T2. The model menu switches between the textbook scheme and what MariaDB's InnoDB really does.

Intention locks, top-down

Suppose T1 holds X on row r2 and T2 asks for S on the whole table. To find the conflict, the lock manager would have to look at every row lock in the table. Intention locks fix this. Before T1 locks a node, it puts an intention lock on every ancestor, starting at the root:

  • IS (intention shared): "I will take S somewhere below this node".
  • IX (intention exclusive): "I will take X somewhere below this node".
  • SIX (shared + intention exclusive): S on the whole subtree, plus the intention to take X on some nodes below.

So a row update walks IX(db), IX(t), IX(P1), X(r2), and a row read walks IS, IS, IS, S. A node can be locked in S or IS only if its parent is held in IS or IX (or stronger); in X, IX or SIX only if its parent is held in IX or SIX (or X). Locks are released the other way, bottom-up: a node's children are unlocked before the node itself. On the page all locks are released at COMMIT (strict two-phase locking, see Two-Phase Locking), and the release goes rows, pages, table, database.

A held lock can also cover what is below it. If T1 holds S on t, it may read any row without more locks. If it holds X on t, it may also write any row.

The compatibility matrix

Each new request is checked against the other transaction's lock on the same node, and only that node:

held \ requestedISIXSSIXX
IS✓✓✓✓✗
IX✓✓✗✗✗
S✓✗✓✗✗
SIX✓✗✗✗✗
X✗✗✗✗✗

Intention locks never clash with each other: IX and IX are compatible, because two writers of different rows don't conflict at the table. The real conflict, if there is one, is found lower down, at the row. Demo: two row updates, no conflict: T1 updates r1 and T2 updates r3. Both hold IX on db and t, each holds IX on its own page and X on its own row: 8 locks, no wait.

If a transaction already holds a lock on the node, the new mode is the smallest one that covers both: IS + IX = IX, IS + S = S, and IX + S = SIX.

A table scan vs a row update

In Demo: table scan vs a row update, T1 runs SELECT * FROM t LOCK IN SHARE MODE. It takes IS on db and S on t: 2 locks cover all 4 rows. T2 then updates r2. It gets IX on db (IS vs IX ✓) but waits at t, because T1's S and T2's IX are ✗. One check at the table was enough; nobody had to look at the rows. When T1 commits, T2 goes on and takes IX(t), IX(P1), X(r2).

Demo: SIX is the classic "scan the table, change a few rows" job. T1 scans (S on t) and then updates r2. It needs IX on t, and S + IX becomes SIX. T2 can still read r4 (SIX vs IS ✓), but its update of r3 waits (SIX vs IX ✗). Demo: LOCK TABLES waits for an intention lock is the other direction: T1 holds IX on t because it updated r1, so T2's request for X on the whole table waits at t.

Lock escalation

Every lock costs memory in the lock table. Some systems escalate: when a transaction holds many row locks under one table, they are swapped for one table lock (S, or X if any of them is X). SQL Server and Db2 do this; SQL Server tries it at about 5,000 locks on one table. The page escalates at 3 row locks, so you can see it. Escalation is skipped when another transaction holds a conflicting lock on the table.

Before: T1 holds IX on db, IX on t, IX on P1 and P2, and X on r1, r2 and r3, 7 locks. After escalation: T1 holds IX on db and X on t, 2 locks, and T2's read of r4 waits at t although T1 never touched r4.
Escalation turns 7 locks into 2, but it locks rows the transaction never touched.

Demo: lock escalation at 3 row locks: T1 updates r1, r2 and r3 and holds 7 locks: IX on db, t, P1 and P2, and X on the three rows. After the third, the lock manager swaps them for X(t): T1 holds IX(db) and X(t), 2 locks. T2 then reads r4, a row T1 never touched, and waits at t (X vs IS ✗). That is the price: less memory, less concurrency.

What MariaDB's InnoDB really does

InnoDB uses only two levels of this tree. On the table it takes IS or IX intention locks; on rows (really index records) it takes S or X. SELECT … LOCK IN SHARE MODE takes IS on the table and S on the rows it reads; UPDATE, DELETE and SELECT … FOR UPDATE take IX on the table and X on the rows. SHOW ENGINE INNODB STATUS prints the table lock as TABLE LOCK table `test`.`t` trx id … lock mode IX. InnoDB has:

  • no page or database level in its lock system. A row lock is a bit in a per-page lock object, but it locks one record, not the page (see InnoDB's lock_sys).
  • no SIX mode. Its table modes are IS, IX, S, X and AUTO-INC.
  • no lock escalation. Row locks are stored compactly, so InnoDB never needs to swap them for a table lock. Demo: InnoDB, same updates, no escalation runs the escalation demo again: T1 keeps IX(t) and 3 row X locks (4 locks), and T2 reads r4 at once with IS(t) and S(r4).

A locking scan therefore takes a lock on every row it reads. Demo: InnoDB, a locking scan locks every row: T1 holds IS(t) and S on r1 to r4, 5 locks instead of the textbook's 2. T2's update of r2 gets IX on t (IS vs IX ✓) and waits at the row (S vs X ✗), not at the table. InnoDB intention locks block only whole-table requests such as LOCK TABLES t WRITE. In MariaDB that statement first waits on the server's metadata lock, before InnoDB's table lock is checked; see MySQL Metadata Locks. For the gaps between records that InnoDB also locks, see InnoDB record, gap and next-key locks. PostgreSQL has eight table lock modes instead; see The PostgreSQL Lock Manager.

When two transactions each wait for the other, the page rolls back the younger one with ERROR 1213. How deadlocks are found or prevented is shown on Two-Phase Locking and Wait-Die and Wound-Wait.

What the page leaves out

The textbook model has one table, two pages and four rows, and two transactions; a real tree has many tables and a file or index level. The page has no wait queue order, lock wait timeout (innodb_lock_wait_timeout, 50 s by default) or lock upgrades waiting ahead of others. In InnoDB mode it leaves out gap and next-key locks (a REPEATABLE READ scan also locks the gaps and the supremum record), AUTO-INC table locks, metadata locks, and LOCK TABLES … READ, which takes an InnoDB S table lock only when autocommit=0 and innodb_table_locks=1. MariaDB has no page-level or SIX locks and no escalation, so those appear only in the textbook model.

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 serializabilityConflict 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 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 serializabilityConflict 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 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.