Gap Locks and Next-Key Locking in an Index-Ordered Store

A multi-version engine can avoid blocking reads entirely, which leaves the problem of phantoms without a natural solution. A snapshot handles phantoms for reads by pinning a consistent view. A locking engine cannot: if it wants a transaction to re-read a predicate and see the same set of rows, it must prevent insertions into the range the predicate covers, and that means locking something that does not yet exist.

The mechanism that does this is the gap lock, and it is defined over the index rather than over the table. Understanding it requires understanding that a row lock in an index-organized engine is always a lock on an index record, and that index records are ordered, so between any two of them there is a gap that can be locked as an object in its own right.

Three lock modes over index records

A record lock locks a single index record. An exclusive record lock on the record for primary key 5 blocks another transaction from updating or deleting that record. It does not block an insert of primary key 6, because 6 is a different record.

A gap lock locks the interval between two adjacent index records, exclusive of the records themselves. A gap lock on the interval between 5 and 10 blocks any insertion whose key would place a record strictly inside that interval. Keys equal to an existing record are governed by the record lock on that record and by the uniqueness check, not by the gap. Multiple transactions can hold gap locks on the same gap simultaneously, and gap locks do not conflict with each other; their only purpose is to block insertion.

A next-key lock is the combination: a record lock on the record plus a gap lock on the interval preceding it. Locking the next-key interval ending at 10 covers everything in the open-closed range that ends at 10, which means it blocks inserts into the gap before 10 and blocks modification of 10 itself.

The combination exists because a range scan naturally locks what it traverses. A scan of WHERE id BETWEEN 5 AND 10 reads records 5 through 10 and, in a locking engine, takes next-key locks on each: the interval before 5, the interval before 6, and so on up to the interval ending at 10. The union of those intervals is the whole range from just after the previous record to 10 inclusive, which is precisely the set of positions where a new row could appear and change the result of the scan.

Why the gap must be locked at all

The phantom problem is that a predicate’s result set can change between two evaluations without any individual row changing. Locking the rows that satisfied the predicate at the first evaluation does nothing about rows that will satisfy it at the second.

A gap lock closes that hole by making insertion into the range impossible for the duration. If no new row can appear in the range, the second evaluation returns the same set. This is a predicate lock restricted to the index that the scan used, which is why it is exact for equality and range predicates on indexed columns and approximate or absent for predicates the index cannot serve.

The last point is the important limitation. A gap lock protects the index it is taken on. A query with a predicate on a column that no index covers cannot be answered by a range scan, so the engine scans the whole table or a secondary index and locks everything it examines, which is a much coarser lock than the predicate. The gap between “the lock the engine takes” and “the predicate the query expresses” is the source of both the mechanism’s safety and its contention.

Taking the locks from a scan

The lock set for a statement is determined by the access path. Consider a secondary index on a status column with values in order, and a statement that reads all rows with status between ‘a’ and ‘c’ using that index.

The engine positions on the first index record with status at or after ‘a’ and takes a next-key lock on it. It then walks forward, taking a next-key lock on each record until it passes ‘c’. The final lock is on the first record beyond the range, which is the one that defines the upper boundary; locking it as a next-key lock covers the gap between the last in-range record and that boundary record. If the range extends to the end of the index, the lock is on the supremum pseudo-record, a synthetic record representing the position after the last real entry.

-- Session A: locking read over a range on an indexed column.
BEGIN;
SELECT * FROM orders WHERE status BETWEEN 'a' and 'c' FOR UPDATE;
-- Locks: next-key on each index record in range, plus the gap before
-- the first one and the gap up to the first record beyond 'c'.

-- Session B: an insert whose status falls inside that range blocks,
-- even though no existing row conflicts with it.
INSERT INTO orders (id, status) VALUES (999, 'b');   -- waits

The insert blocks not because of any row it touches but because the position it would occupy is inside a locked gap. The blocking is on the insert intention, which the engine treats as a request for a lock on the gap it is about to place a record into.

Insert intention locks are the fourth mode, and they behave differently from gap locks in one crucial respect: they do conflict with gap locks held by other transactions, but two transactions inserting into the same gap at different positions do not conflict with each other unless their positions coincide. This is why concurrent inserts into the same gap are usually allowed while an insert into a gap locked by a range scan is not.

Deadlocks that come from the gaps

The lock modes above produce deadlocks that do not exist in a pure row-locking engine, and their shape is worth recognizing.

The first is the range-versus-insert cycle. Transaction A takes a next-key lock covering a gap; transaction B inserts into a different part of the same gap and then, in a later statement, requests a lock on a record A holds. A waits for B’s insert to resolve; B waits for A’s record. Neither can proceed.

The second arises from two range scans in opposite directions. A scans ascending and locks the records in order; B scans descending over an overlapping range and locks them in reverse. The two lock sequences cross and each holds a record the other needs.

The third, and the most surprising, comes from the fact that a gap lock does not block another gap lock. Two transactions can each hold a gap lock on the same interval, then each attempt an insert into it. The inserts conflict with the other’s gap lock, and both wait. The engine must detect this as a deadlock rather than as a simple wait, because neither will ever be granted.

-- Deadlock shape: each session holds a gap the other needs.
-- The exact gap each statement locks depends on which index records exist.
-- A
BEGIN;
SELECT * FROM orders WHERE status = 'a' FOR UPDATE;   -- next-key locks
-- B
BEGIN;
SELECT * FROM orders WHERE status = 'c' FOR UPDATE;   -- different records
-- A then inserts at 'c'; B then inserts at 'a'; each waits on a gap
-- the other holds, and neither can proceed.

The practical consequence is that applications running at a locking isolation level must be prepared for deadlock errors on workloads that insert into ranges concurrently scanned, and must retry the whole transaction rather than the failing statement, because the lock set is a property of the transaction, not of the statement.

Insert intention and duplicate keys

A special case is the insert of a key that already exists. The inserting transaction must take a lock on the existing record to check uniqueness, and that lock is a shared next-key lock. Two transactions inserting the same key therefore both take a shared lock on the same record and then both attempt to upgrade to exclusive in order to write; the upgrade deadlocks, and one of them is chosen as the victim.

This is why concurrent inserts of the same unique key produce deadlocks rather than a clean duplicate-key error. The error arrives only after the lock conflict resolves, and the resolution is a rollback of one transaction. An application that treats duplicate-key errors as a normal outcome must also treat the associated deadlock as one.

The cost, and the reason snapshot engines avoid it

The cost of next-key locking is contention that is proportional to the size of the scanned range rather than to the number of rows the statement modifies. A statement that updates one row by a range predicate locks every index record the scan touched to find that row, which can be thousands of records for a scan that examines many candidates before finding its target.

That cost is why the mechanism is confined to locking reads and to engines that implement isolation through locks. A snapshot-based engine answers the same query against a fixed read view, so the result cannot change mid-transaction and no gap needs locking. The trade is that the snapshot engine must retain old versions for the duration, which is the storage cost described in vacuum horizons and dead version collection, and that its serializable level must detect conflicts after the fact, as described in the dangerous-structure analysis.

A hybrid is possible and is what several engines actually implement: plain reads use a snapshot and take no locks, while locking reads and writes take next-key locks. The isolation level then depends on the statement type, not just on the transaction’s declared level, which is a distinction that surprises applications. A transaction at a snapshot level that issues a locking read has opted into the locking engine’s behaviour for that statement, including its deadlock exposure and its blocking.

Choosing between the mechanisms

The decision between gap locking and snapshot isolation is a decision about where to put the cost. Gap locking puts it in concurrency: readers and writers block each other, and deadlocks must be detected and retried. Snapshots put it in storage and in validation: old versions accumulate, and serializable levels need post-hoc conflict detection.

The workloads that favour gap locking are those with short transactions and predicates that touch few index records, where the blocked interval is small and the abort rate is low. The workloads that favour snapshots are those with long reads and wide predicates, where locking the range would block every writer in it for the duration of the read.

There is a middle path that avoids most of the contention without abandoning the guarantee: index the predicate so that the lock can be taken on a narrow range. A query filtered on an unindexed column forces a full scan and a lock on everything; the same query with an index on the filter column locks only the matching range. The lock set is a function of the access path, which is why index design and isolation behaviour are not independent concerns.

That is the same conclusion the precedence graph reaches from the other direction. The granularity at which the engine reasons about conflicts determines both the anomaly set and the contention, and the granularity is chosen by the index, not by the isolation level’s name. A level that promises serializability delivers it at whatever granularity the access paths allow, and a predicate that cannot be localized to an index range will be protected by locking far more than the predicate describes.