Key-Range Locking
Key-range locks protect a range of rows implicitly included in a record set being read by a Transact-SQL statement while using the serializable transaction isolation level. The serializable isolation level requires that any query executed during a transaction must obtain the same set of rows every time it is executed during the transaction. A key range lock protects this requirement by preventing other transactions from inserting new rows whose keys would fall in the range of keys read by the serializable transaction.
Key-range locking prevents phantom reads. By protecting the ranges of keys between rows, it also prevents phantom insertions into a set of records accessed by a transaction.
A key-range lock is placed on an index, specifying a beginning and ending key value. This lock blocks any attempt to insert, update, or delete any row with a key value that falls in the range because those operations would first have to acquire a lock on the index. For example, a serializable transaction could issue a SELECT statement that reads all rows whose key values are between 'AAA' and 'CZZ'. A key-range lock on the key values in the range from 'AAA' to 'CZZ' prevents other transactions from inserting rows with key values anywhere in that range, such as 'ADG', 'BBD', or 'CAL'.
Key-Range Lock Modes
Key-range locks include both a range and a row component specified in range-row format:
Range represents the lock mode protecting the range between two consecutive index entries.
Row represents the lock mode protecting the index entry.
Mode represents the combined lock mode used. Key-range lock modes consist of two parts. The first represents the type of lock used to lock the index range (RangeT) and the second represents the lock type used to lock a specific key (K). The two parts are connected with a hyphen (-), such as RangeT-K.
Range
Row
Mode
Description
RangeS
S
RangeS-S
Shared range, shared resource lock; serializable range scan.
RangeS
U
RangeS-U
Shared range, update resource lock; serializable update scan.
RangeI
Null
RangeI-N
Insert range, null resource lock; used to test ranges before inserting a new key into an index.
RangeX
X
RangeX-X
Exclusive range, exclusive resource lock; used when updating a key in a range.
Note
The internal Null lock mode is compatible with all other lock modes.
Key-range lock modes have a compatibility matrix that shows which locks are compatible with other locks obtained on overlapping keys and ranges. For the full matrix of lock compatibility, see Lock Compatibility.
|
Existing granted mode |
|
|
|
|
|
|
|---|---|---|---|---|---|---|---|
Requested mode |
S |
U |
X |
RangeS-S |
RangeS-U |
RangeI-N |
RangeX-X |
Shared (S) |
Yes |
Yes |
No |
Yes |
Yes |
Yes |
No |
Update (U) |
Yes |
No |
No |
Yes |
No |
Yes |
No |
Exclusive (X) |
No |
No |
No |
No |
No |
Yes |
No |
RangeS-S |
Yes |
Yes |
No |
Yes |
Yes |
No |
No |
RangeS-U |
Yes |
No |
No |
Yes |
No |
No |
No |
RangeI-N |
Yes |
Yes |
Yes |
No |
No |
Yes |
No |
RangeX-X |
No |
No |
No |
No |
No |
No |
No |
Conversion Locks
Conversion locks are created when a key-range lock overlaps another lock.
Lock 1 |
Lock 2 |
Conversion lock |
|---|---|---|
S |
RangeI-N |
RangeI-S |
U |
RangeI-N |
RangeI-U |
X |
RangeI-N |
RangeI-X |
RangeI-N |
RangeS-S |
RangeX-S |
RangeI-N |
RangeS-U |
RangeX-U |
Conversion locks can be observed for a short period of time under different complex circumstances, sometimes while running concurrent processes.
Serializable Range Scan, Singleton Fetch, Delete, and Insert
Key-range locking ensures that the following operations are serializable:
Range scan query
Singleton fetch of nonexistent row
Delete operation
Insert operation
Before key-range locking can occur, the following conditions must be satisfied:
The transaction-isolation level must be set to SERIALIZABLE.
The query processor must use an index to implement the range filter predicate. For example, the WHERE clause in a SELECT statement could establish a range condition with this predicate: ColumnX BETWEEN N**'AAA'** AND N**'CZZ'**. A key-range lock can only be acquired if ColumnX is covered by an index key.
Examples
The following table and index are used as a basis for the key-range locking examples that follow.
.gif "Database table with index b-tree illustration")
Range Scan Query
To ensure a range scan query is serializable, the same query should return the same results each time it is executed within the same transaction. New rows must not be inserted within the range scan query by other transactions; otherwise, these become phantom inserts. For example, the following query uses the table and index in the previous illustration:
SELECT name
FROM mytable
WHERE name BETWEEN 'A' AND 'C';
Key-range locks are placed on the index entries corresponding to the range of data rows where the name is between the values Adam and Dale, preventing new rows qualifying in the previous query from being added or deleted. Although the first name in this range is Adam, the RangeS-S mode key-range lock on this index entry ensures that no new names beginning with the letter A can be added before Adam, such as Abigail. Similarly, the RangeS-S key-range lock on the index entry for Dale ensures that no new names beginning with the letter C can be added after Carlos, such as Clive.
Note
The number of RangeS-S locks held is n+1, where n is the number of rows that satisfy the query.
Singleton Fetch of Nonexistent Data
If a query within a transaction attempts to select a row that does not exist, issuing the query at a later point within the same transaction has to return the same result. No other transaction can be allowed to insert that nonexistent row. For example, given this query:
SELECT name
FROM mytable
WHERE name = 'Bill';
A key-range lock is placed on the index entry corresponding to the name range from Ben to Bing because the name Bill would be inserted between these two adjacent index entries. The RangeS-S mode key-range lock is placed on the index entry Bing. This prevents any other transaction from inserting values, such as Bill, between the index entries Ben and Bing.
Delete Operation
When deleting a value within a transaction, the range the value falls into does not have to be locked for the duration of the transaction performing the delete operation. Locking the deleted key value until the end of the transaction is sufficient to maintain serializability. For example, given this DELETE statement:
DELETE mytable
WHERE name = 'Bob';
An exclusive (X) lock is placed on the index entry corresponding to the name Bob. Other transactions can insert or delete values before or after the deleted value Bob. However, any transaction that attempts to read, insert, or delete the value Bob will be blocked until the deleting transaction either commits or rolls back.
Range delete can be executed using three basic lock modes: row, page, or table lock. The row, page, or table locking strategy is decided by query optimizer or can be specified by the user through optimizer hints such as ROWLOCK, PAGLOCK, or TABLOCK. When PAGLOCK or TABLOCK is used, the Database Engine immediately deallocates an index page if all rows are deleted from this page. In contrast, when ROWLOCK is used, all deleted rows are marked only as deleted; they are removed from the index page later using a background task.
Insert Operation
When inserting a value within a transaction, the range the value falls into does not have to be locked for the duration of the transaction performing the insert operation. Locking the inserted key value until the end of the transaction is sufficient to maintain serializability. For example, given this INSERT statement:
INSERT mytable VALUES ('Dan');
The RangeI-N mode key-range lock is placed on the index entry corresponding to the name David to test the range. If the lock is granted, Dan is inserted and an exclusive (X) lock is placed on the value Dan. The RangeI-N mode key-range lock is necessary only to test the range and is not held for the duration of the transaction performing the insert operation. Other transactions can insert or delete values before or after the inserted value Dan. However, any transaction attempting to read, insert, or delete the value Dan will be locked until the inserting transaction either commits or rolls back.