Your transaction takes a lock on every row a range query returns, yet re-running that same range query still returns extra rows. Explain why row-level locking cannot prevent phantoms, and what locking mechanisms do.

## Why row locks structurally cannot do it A lock manager associates a lock with an identifiable object — a row id, a page, an index key. When a transaction reads `WHERE amount BETWEEN 100 AND 200` and locks the four rows it found, it has protected four points on the number line. The interval between and around those points is unprotected, and that is exactly where a concurrent INSERT lands. The anomaly is about the *predicate's extension* (the set of all rows that could match), not about the rows currently in it. ## Predicate locking: the correct-but-impractical answer The original theory says: lock the predicate. A writer wanting to insert a row must check its row against every predicate lock held; if the row would satisfy one, it waits. This is provably sufficient. It is also impractical: - Deciding whether an arbitrary new row satisfies an arbitrary held predicate, for every insert, is expensive. - Deciding whether two arbitrary predicates can overlap (needed to conflict-check two readers/writers cheaply) is, in general, undecidable. So no mainstream engine does true general predicate locking on the write path. ## Index-range locking: the practical approximation The key insight is that a predicate an index can serve corresponds to a **contiguous range of index key space**. Lock the range and you have conservatively locked the predicate — you may lock slightly more than the predicate strictly needs (false conflicts), but never less (no missed phantoms). The building blocks: - **Record lock**: the index entry itself. - **Gap lock**: the open interval *between* two adjacent index keys, containing no rows. It exists purely to stop inserts. - **Next-key lock**: a record lock plus the gap preceding that record — the usual unit engines take when scanning an index under a phantom-preventing isolation level. - **Insert-intention lock**: what an INSERT requests in a gap; it conflicts with gap locks, so the insert waits, but two insert intentions at different points in the same gap do not conflict with each other. A range scan therefore takes a chain of next-key locks covering the whole scanned interval, including the boundary gaps at each end, so nothing can be inserted into the range until the scanning transaction commits. ## The index dependency — the part interviewers push on The locked range is determined by the **access path the optimizer chose**, not by the text of the predicate. Consequences: - **No usable index** → the engine scans the table and must lock every row and gap it examined, which for a large scan is effectively a table-wide lock. A `WHERE email = ?` check with no index on `email` can block all inserts into the table. - **A less selective index** → a wider locked range than logically necessary, so unrelated transactions block on rows that do not even match the predicate. A common symptom is "we get lock waits on rows the query never returned". - **Locks on non-matching rows** → because gap locks straddle keys, a transaction can block an insert of a value that would not have satisfied the predicate at all. This is a false conflict, and it is the deliberate price of a conservative approximation. - **Deadlock risk rises**, because two transactions scanning overlapping ranges in different orders each hold part of the other's range. ## Other mechanisms in the family - **Key-range locks** in lock-based engines are the same idea with a richer mode matrix (range-shared, range-insert, range-exclusive). - **Snapshot reads** avoid read phantoms without locking at all — the reader has a stable view — but they protect only the reader's own view, not an invariant the reader intends to act on. - **Serializable Snapshot Isolation (SSI)** takes a different tack: no blocking locks, but tracked read dependencies (typically via SIREAD markers on index ranges) and an abort when a dangerous cycle forms. Phantoms are caught by tracking the *ranges scanned*, not the rows returned. - **A unique or exclusion constraint** enforces the rule inside the index itself, converting a race into a constraint violation, and is often the cheapest correct answer for "there must not already exist a row like this". ## How to reason about it in practice When a transaction's correctness depends on "nothing else matches this predicate", ask three questions: which index will serve the predicate, how wide a key range does that make the engine lock, and how long will the transaction hold it? Narrow the range with a better index, shorten the hold time by doing the scan late in the transaction, and prefer a declarative constraint whenever the invariant can be expressed as one.