Lock granularity and intention locks

How do nested locks answer table-level questions cheaply, and why does isolation depend on the query plan?

The constraint

A lock protects a set of data, and sets are nested: a table contains pages, a page contains rows. You want a full-table scan to take one lock and a single-row update to take one lock. And you need a table-level request to be answerable without inspecting a million rows.

Intention locks

The only way to answer "is anything below this node locked?" in O(1) time is to pass the information upward at acquisition time. So:

Before taking a shared lock S on a row, take an IS (intention-shared) lock on the table.
Before taking an exclusive lock X on a row, take an IX (intention-exclusive) lock on the table.

A table-level request now reads one lock entry and has its answer.

The compatibility matrix reduces to one asymmetry worth memorizing:

IX is compatible with IX, because two transactions can intend to write different rows.
IX is not compatible with S, because a reader of the whole table cannot coexist with a transaction that intends to write inside it.
SIX (shared + intention exclusive) exists for the "scan the table and update a few rows" pattern.

Everything else follows from these.

Held \ Requested	IS	IX	S	X
IS	yes	yes	yes	no
IX	yes	yes	no	no
S	yes	no	yes	no
X	no	no	no	no

(SIX, not shown, is compatible only with IS.)

A lock entry of about 100 bytes times a one-million-row update is 100 MB of lock-manager memory. So systems escalate: past a threshold, they swap the many fine locks for one coarse lock (SQL Server's default threshold is 5,000 locks). You trade metadata cost for false conflicts against transactions that never touched your rows.

The lock table is a cache, lock granularity is its block size. Too fine costs metadata; too coarse costs false sharing; there is no setting that avoids both.

Predicate locks, and why nobody implements them

The correct fix for phantoms is to lock the predicate itself (the condition "salary > 100000"). But deciding whether two arbitrary predicates could ever be satisfied by the same row is undecidable in general and expensive even in restricted cases. So everyone implements a conservative approximation over the index structure: next-key locks and gap locks. These lock ranges of keys inside a B-tree (including the gaps between existing keys, which is where a new row could appear) instead of logical predicates.

The consequence is one of the least-appreciated facts in the field: which locks a statement takes depends on which index the optimizer chose. If no index covers the predicate, the only safe superset of "all rows that could match" is the whole table.

This is exactly Tomas's second symptom.

Granularity is block size for the lock manager, and predicate locking is intractable, so every real system locks index ranges and inherits the optimizer's choices.