InnoDB Locking Deep Dive: Record Locks, Gap Locks, and Next-Key Locks

Consider a simple table containing three rows with primary keys 10, 20, and 30:

CREATE TABLE items (
    id INT PRIMARY KEY,
    name VARCHAR(50)
);

INSERT INTO items VALUES (10, 'Book'), (20, 'Pen'), (30, 'Desk');

Transaction A executes a range update inside a transaction under default REPEATABLE READ isolation:

-- Transaction A
BEGIN;
SELECT * FROM items WHERE id BETWEEN 15 AND 25 FOR UPDATE;

While Transaction A is active, Transaction B attempts to insert a brand new row with id = 15:

-- Transaction B
BEGIN;
INSERT INTO items VALUES (15, 'Notebook'); -- BLOCKS!

Transaction B freezes. It is blocked, waiting for a lock.

Why was Transaction B blocked when trying to insert id = 15—a row key that did not exist in the database when Transaction A started?

The answer lies in how InnoDB uses Gap Locks and Next-Key Locks on B+ Tree index structures to prevent Phantom Reads.

1. The Three InnoDB Locking Algorithms

When InnoDB locks rows during locking reads (FOR UPDATE or LOCK IN SHARE MODE) or modifications (UPDATE, DELETE), it places locks on index entries, not on raw data rows.

InnoDB uses three distinct locking algorithms:

Index Keys: ... ----( Gap Lock )----> [ Record 20 ] ----( Gap Lock )----> [ Record 30 ]
                                      |___________|
                                     Next-Key Lock
                                      (10, 20]

A. Record Lock

A Record Lock locks a specific, existing index record.

Example: Locking the index entry where id = 20.
Prevents other transactions from modifying or deleting that exact record.

B. Gap Lock

A Gap Lock locks the open interval between index records, or the gap before the first record or after the last record.

Example: Locking the open interval $(10, 20)$ .
Purpose: Prevents other transactions from inserting new rows into the gap.
Note: Gap locks have a single purpose: to prevent concurrent inserts. Multiple transactions can hold conflicting gap locks on the exact same gap simultaneously without blocking each other!

C. Next-Key Lock

A Next-Key Lock is a combination of a Record Lock on an index record plus a Gap Lock on the gap preceding that record.

Mathematically, a Next-Key lock on key $K_i$ locks the left-half-open interval: $(K_{i-1}, K_i]$ .
This is the default locking algorithm used by InnoDB under REPEATABLE READ isolation.

2. Preventing Phantom Reads Under REPEATABLE READ

Standard SQL specifications state that REPEATABLE READ isolation permits Phantom Reads, requiring full SERIALIZABLE isolation to guarantee range query consistency.

However, MySQL InnoDB prevents Phantom Reads under REPEATABLE READ by combining MVCC for non-locking snapshot reads with Next-Key Locks for locking reads.

Concrete Scenario Breakdown

Suppose items has primary keys 10, 20, and 30.

The index structure forms four distinct lockable gaps:

  Gap 1: (-infinity, 10]
  Gap 2: (10, 20]
  Gap 3: (20, 30]
  Gap 4: (30, +infinity)   <-- Protected by the "Supremum" Pseudo-Record

When Transaction A executes:

SELECT * FROM items WHERE id BETWEEN 15 AND 25 FOR UPDATE;

InnoDB searches the B+ Tree index for keys matching the predicate range $[15, 25]$ .
It encounters existing record 20 and places a Next-Key Lock on record 20, locking the interval $(10, 20]$ .
It encounters existing record 30 (the first record past the range) and places a Next-Key Lock on record 30, locking the interval $(20, 30]$ .
When Transaction B attempts INSERT INTO items VALUES (15, 'Notebook'), the engine checks if 15 falls within any active Gap or Next-Key locks.
Because 15 falls inside the locked interval $(10, 20]$ , Transaction B is blocked until Transaction A commits!

3. The Supremum Pseudo-Record

How does InnoDB protect the open-ended gap past the highest value in an index (id > 30)?

Every InnoDB index page contains two hidden internal pseudo-records:

infimum: A pseudo-record lower than any user key on the page.
supremum: A pseudo-record higher than any possible user key on the page.

To lock the gap $(30, +\infty)$ , InnoDB places a Next-Key Lock on the supremum pseudo-record, locking the interval $(30, \text{supremum}]$ .

4. Lock Downgrading: Unique Index Equality Optimization

While Next-Key locking is the default, InnoDB optimizes lock granularity when executing exact equality queries against unique indexes.

If a query searches a UNIQUE index or PRIMARY KEY using an exact equality predicate (WHERE id = 20):

InnoDB checks if record 20 exists.
Because id is unique, no concurrent transaction can insert a duplicate row with id = 20.
Therefore, InnoDB downgrades the Next-Key lock $(10, 20]$ to a simple Record Lock on 20, releasing the gap lock on $(10, 20)$ .

-- Query on Primary Key (Exact Equality):
SELECT * FROM items WHERE id = 20 FOR UPDATE;
-- Locks ONLY Record 20. Another thread CAN insert id = 15 concurrently!

Key Exception: If searching a non-unique secondary index (e.g., WHERE status = 'PENDING' FOR UPDATE), InnoDB cannot downgrade to a record lock. It must retain Next-Key locks on matching records and gap locks around them to prevent concurrent threads from inserting new rows with status = 'PENDING'.

InnoDB Lock Comparison Summary Matrix

Query Type	Index Type	Isolation Level	Lock Algorithm Applied
`SELECT ...` (Non-locking)	Any	`REPEATABLE READ`	No Locks (MVCC Snapshot Read)
`SELECT ... FOR UPDATE`	Unique Key Equality (`WHERE id = 20`)	Any	Record Lock on `20`
`SELECT ... FOR UPDATE`	Non-Unique Key (`WHERE age = 25`)	`REPEATABLE READ`	Next-Key Locks on matching keys + preceding gaps
`SELECT ... FOR UPDATE`	Range Query (`WHERE id BETWEEN 10 AND 20`)	`REPEATABLE READ`	Next-Key Locks covering full predicate range
`INSERT INTO ...`	Any	Any	Insert Intention Lock (Waits on active Gap/Next-Key locks)

Summary & Next Steps

InnoDB’s index locking protocol protects transactional consistency across range queries:

Record Locks protect existing individual index entries.
Gap Locks lock spaces between index entries to prevent concurrent inserts.
Next-Key Locks combine record locks and gap locks ( $(K_{i-1}, K_i]$ ), serving as the primary mechanism for preventing Phantom Reads in REPEATABLE READ.
Unique key equality queries downgrade Next-Key locks to simple Record Locks, maximizing concurrency.

In the next article, we examine InnoDB Undo Logs and Read Views: Constructing Point-In-Time Snapshots.

References & Further Reading

Gray, J. (1978). Notes on Data Base Operating Systems: Two-Phase Commit Protocol. Operating Systems, LNCS 60, Springer.
Garcia-Molina, H., & Salem, K. (1987). Sagas. Proceedings of ACM SIGMOD Conference, 249–259.
Bernstein, P. A., Hadzilacos, V., & Goodman, N. (1987). Concurrency Control and Recovery in Database Systems (Chapter 7). Addison-Wesley.