Key-range RangeI-N lock compatibility in SQL Server

Question

The documentation states that the RangeI-N lock (Insert range, null resource lock; used to test ranges before inserting a new key into an index) is compatible with itself (see the compatibility matrix), so even though one transaction has obtained a RangeI-N lock on particular key another transaction can also obtain such a lock.

Further below, it says that

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.

Quoting another source - Microsoft SQL Server 2008 Internals: Transactions and Concurrency:

For example, the RangeIn-Null lock is acquired when SQL Server attempts to insert into the range between keys in a session using Serializable isolation. This type of lock is not often seen because it is typically very transient. It is held only until the correct location for insertion is found, and then the lock is converted into an X lock.

My understanding is that this type of lock is during the process of identifying the range where the newly inserted key should be placed (I'm assuming that's what 'test the range' means). After this happens the lock is released, the new key gets inserted and an X lock is placed on it.

However I do not see why two RangeI-N locks are said to be compatible with each other. If transactions A and B both place a RangeI-N lock on the same key because they both want to insert a new key into the range and transaction A performs the insert first, then the location for key insertion determined by B might be already incorrect because the ranges have changed (A inserted a new value there). Could anyone explain that?

Answer 1

My understanding is that this type of lock is during the process of identifying the range where the newly inserted key should be placed (I'm assuming that's what 'test the range' means). After this happens the lock is released, the new key gets inserted and an X lock is placed on it.

RangeI-N lock is requested to test that insertion into key range will not interfere with another transaction that may potentially do some serializable operation incompatible with insertion (like reading for example).

During insertion of record into index database engine locates page, where key being inserted should be placed. Page and key locks are not used at this stage yet, only latches. Once page is located, engine starts acquiring locks necessary for performing insertion of record to the page. These are IX lock for the page located, then RangeI-N lock for the key next to key being inserted. Upon acquiring RangeI-N is not held, and next X lock for the key being inserted is requested. After necessary locks acquired, insertion of the record proceeds.

Say we have table and data

CREATE TABLE T
(
    K int NOT NULL,
    CONSTRAINT UQ_T UNIQUE CLUSTERED (K)
);

INSERT INTO T (K)
VALUES (1), (2), (9), (10);

Let's take result of the following query

SELECT K, %%lockres%% AS lockres
FROM T;

which is

K    lockres
---- ---------------
1    (8194443284a0)
2    (61a06abd401c)
9    (30b7763ed433)
10   (d08358b1108f)

(we will refer to it in the things that follow).

Then, say we have a query

SELECT COUNT(*)
FROM T
WHERE K BETWEEN 1 AND 9;

Running it under SERIALIZABLE isolation level results to the following locking footprint

To protect key range, database engine locks every key in this range with RangeS-S lock. Additionally, key next to the range is locked (this is necessary for non-unique index, but engine is doing it for unique index too). In this case, locks are placed on resources corresponding (according to result of the query taken earlier) to keys 1, 2, 9 and 10.

Non-concurrent insertion to the table

INSERT INTO T (K)
VALUES (3);

results to following locking footprint

Key 3 does not exists in the table, and so database engine requests RangeI-N lock on the resource (30b7763ed433) corresponding to key 9, which is next to 3 at the moment. Acquiring RangeI-N means that there is no incompatible serializable activity being performed, so engine proceeds and acquires X lock on the resource (98ec012aa510) corresponding to key 3. Then actual insertion happens and locks are released. Notice that there is no release of RangeI-N lock.

Running above SELECT and INSERT concurrently causes INSERT to wait until transaction performed serializable SELECT is active

because of RangeI-N incompatibility with RangeS-S. As soon as transaction performed SELECT ends INSERT will proceed.

This is what "test the range" means.

---

However I do not see why two RangeI-N locks are said to be compatible with each other.

RangeI-N locks compatibility is good, because of it allows concurrent insertions into key range.

Imagine we are doing

INSERT INTO T (K)
VALUES (4);

and

INSERT INTO T (K)
VALUES (6);

concurrently.

It may happen that at some moment both statements acquire RangeI-N on the resource (30b7763ed433) corresponding to key 9. But this is fine, because of then concurrency is controlled by X on the keys and by page latch further.