The idea: InnoDB locks index records and the gaps between them
A row lock in InnoDB is not a lock on a row. It is a lock on an index record: an entry in a B+ tree. A locking read (SELECT … FOR UPDATE, UPDATE, DELETE) locks every index entry it scans, and for each match also the record in the clustered index (PRIMARY), where the row itself lives. Between two neighbouring entries of an index there is a gap, and InnoDB can lock that too. A gap belongs to the record after it: the gap between 20 and 30 is "the gap before 30". After the last entry comes the supremum, a pseudo-record that stands for "+∞", so the last gap can be locked too.
The canvas shows table t (id INT PRIMARY KEY AUTO_INCREMENT, age INT, KEY idx_age (age)) with rows (1,10), (2,20) and (3,30). Both indexes are drawn as number lines: idx_age holds entries (age, id) in order, PRIMARY holds the ids. Locks of T1 are drawn above each line, locks of T2 below. Pick a session and a statement and press Execute; the first statement of a session starts its transaction.
Reading performance_schema.data_locks
MySQL 8.0 lists every lock InnoDB keeps in performance_schema.data_locks. The table on the canvas has the same columns. LOCK_TYPE is TABLE or RECORD; LOCK_DATA is the index entry (20, 2 in idx_age is age 20 with primary key 2), or supremum pseudo-record. LOCK_MODE says which kind of lock it is:
| LOCK_MODE | Name | Covers | Blocks |
|---|---|---|---|
X,REC_NOT_GAP | record lock | the record only | other locks on the record |
X,GAP | gap lock | the gap before the record, not the record | only INSERTs into that gap |
X | next-key lock | the record and the gap before it | both of the above |
X,GAP,INSERT_INTENTION | insert intention | a point in the gap where a new row goes | nothing; it waits for gap locks |
Every transaction that locks rows also takes TABLE IX, an intention lock. IX locks never conflict with each other; they only exist so that LOCK TABLES … WRITE can see that someone is working on rows. The page shows exclusive (X) locks only; SELECT … FOR SHARE takes the same kinds in S mode.
Gap locks only stop inserts
The rules for when a request waits (lock_rec_has_to_wait in lock0lock.cc) are short:
- A request for a record (
XorX,REC_NOT_GAP) waits for another transaction's lock on that record. - A gap-only request (
X,GAP, or any lock on the supremum) never waits. Two transactions can hold gap locks on the same gap at the same time. - An insert intention waits for another transaction's gap lock or next-key lock on the next record. Two inserts into the same gap don't wait for each other.
A gap lock is "purely inhibitive": it doesn't protect any data, it only keeps new rows out. That is why two of them can share a gap, and why the last rule is the only one that matters for them.
Next-key locks prevent phantoms
Under REPEATABLE READ, the default, SELECT * FROM t WHERE age = 20 FOR UPDATE on the non-unique index takes three record locks: a next-key lock X on (20, 2), which also covers the gap between 10 and 20; X,REC_NOT_GAP on PRIMARY 2; and a gap lock X,GAP on (30, 3), the next entry, which covers the gap between 20 and 30. Together they cover every place where another row with age 20 could be inserted. If T2 now inserts age 25, its insert has to go into the gap before (30, 3); it creates X,GAP,INSERT_INTENTION in state WAITING and sleeps until T1 ends. If T1 ran the same SELECT again, it would see exactly the same rows: no phantom (Demo: next-key lock blocks an INSERT).
An insert that doesn't have to wait stores no lock at all. Its new row carries an implicit lock: the row's hidden DB_TRX_ID names a transaction that is still active. Only when another transaction wants that row is the implicit lock turned into an explicit X,REC_NOT_GAP of the inserter. After the insert, the new record also inherits the gap locks of the record after it, as X,GAP, so both halves of the split gap stay locked.
A unique match locks the record only
When the search is an equality on a unique index and finds a row, no other row can have that key, so there is nothing to protect in the gaps. SELECT * FROM t WHERE id = 2 FOR UPDATE takes just X,REC_NOT_GAP on PRIMARY 2. T2 can insert age 25 at once. But T2's age = 20 FOR UPDATE still waits: it gets its next-key lock on idx_age (20, 2), then needs PRIMARY 2 (Demo: unique primary key = record lock only). If the unique search finds no row, InnoDB locks the gap where it would be, as for a non-unique index.
Range scans lock up to the supremum
A range scan locks every entry it reads with a next-key lock, and it reads one entry past the end to know that the range is over. For age > 15 there is no end, so the scan reaches the supremum and locks it: the gap after 30 up to +∞ is locked. T2 can't insert age 35, or any age above 15 (Demo: range scan locks up to supremum). In real tables this is how one UPDATE … WHERE created_at > ? can block every insert at the end of an index. The rows below 15 are free: (1, 10) is never read, and the gap before 10 is not locked.
READ COMMITTED: no gap locks
Under READ COMMITTED InnoDB turns gap locking off for searches and index scans. A locking read takes only X,REC_NOT_GAP on the rows it returns (and it releases locks on rows that turn out not to match the WHERE). Inserts into the gaps go ahead, so a second identical read in the same transaction can return a new row: a phantom (Demo: READ COMMITTED takes no gap locks). Gap locks are still used for foreign-key and duplicate-key checks. Fewer gap locks means fewer waits and deadlocks, which is why many applications run READ COMMITTED with row-based binary logging.
The insert-if-missing deadlock
A very common pattern is "lock the row, insert it if it isn't there":
START TRANSACTION; SELECT * FROM t WHERE age = 25 FOR UPDATE; -- Empty set INSERT INTO t (age) VALUES (25); COMMIT;
With two sessions it deadlocks. Both SELECTs find no row and each takes X,GAP on (30, 3). That is allowed: gap locks don't conflict. Then T1's INSERT needs an insert intention in that gap and waits for T2's gap lock; T2's INSERT waits for T1's. Each waits for the other. InnoDB checks for a cycle on every wait (innodb_deadlock_detect = ON), finds it at once and rolls back one transaction, which gets ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction. It picks the lighter transaction (fewer rows changed and locks); here both are equal, and the page rolls back the one whose request closed the cycle. The other insert then goes ahead (Demo: SELECT FOR UPDATE then INSERT deadlock).
Fixes: put a unique index on the column and insert first (INSERT … ON DUPLICATE KEY UPDATE, or catch the duplicate-key error) instead of SELECT-then-INSERT; a unique index alone doesn't help, because a missing-key search takes the same gap lock. Or use READ COMMITTED, where the empty SELECT takes no lock. Either way, retry the transaction on error 1213, which an application must do anyway.
DELETE of a missing row still locks a gap
DELETE FROM t WHERE age = 25 is a locking read followed by a delete. When no row matches, it deletes nothing, reports 0 rows affected, and still holds X,GAP on (30, 3) until the transaction ends. Another session's insert of age 25 (or 21, or 29) waits (Demo: DELETE of a missing row takes a gap lock). "Delete it in case it exists, then insert" therefore has the same deadlock as the pattern above. A delete that does match only delete-marks the records (✗ on the canvas); they stay in both indexes, still locked, until the transaction commits and purge removes them.
See also Two-Phase Locking and Deadlock Detection for S and X row locks, waits and the wait-for graph, InnoDB isolation levels for consistent versus locking reads, MVCC and Isolation Levels for phantoms in general, MySQL metadata locks for the table-level locks DDL takes, the PostgreSQL lock manager, which has no gap locks and uses predicate locks under SERIALIZABLE instead, and How MySQL Runs a Query for the bigger picture.
What the page leaves out
Shared (S) locks from FOR SHARE, foreign-key checks and INSERT … SELECT; the duplicate-key check of a unique index (which takes S next-key locks and causes its own deadlocks); the AUTO-INC table lock; lock waits timing out after innodb_lock_wait_timeout (50 s); semi-consistent reads of UPDATE under READ COMMITTED; how the optimizer chooses between the index and a full scan (a full scan locks every row and every gap); lock bitmaps per page and the lock hash table; purge removing delete-marked records; and SERIALIZABLE, which turns every plain SELECT into FOR SHARE. Here a transaction starts with its first statement, and a deadlock victim's whole transaction is rolled back, as in InnoDB.