SQL Server deadlock - strange situation

Question

Hi there!

I've found a deadlock situation on SQL Server inserting values in a parent + child tables which, in theory, shouldn't lead to a deadlock, but in fact it occurs. The original scenario occurs in a big software application, but I was able to reproduce it with a very simple example script.

To reproduce this:

• Paste the SQL code below in a MS SQL Management Studio query, using some test database
• Run the "setup" section, which creates 3 tables for the test (parent table, child table, and a special dummy table to be used in an INSERT INTO SELECT statement)
• Using two query windows, run the "Session 1" in one session and "Session 2" in the other, step-by-step, as indicated in the comments (step 1, then step 2, and so on...)
• This should lead to a deadlock (more information after the code section below)

-----------------------------------------------------------------------------------------------
-- TEST SETUP
-----------------------------------------------------------------------------------------------

-- Cleanup (you can use this to delete all test tables)
DROP TABLE IF EXISTS MyChildTable;
DROP TABLE IF EXISTS MyParentTable;
DROP TABLE IF EXISTS MyDummyTable;

CREATE TABLE MyParentTable (
    Tid BIGINT NOT NULL PRIMARY KEY,
);
GO

CREATE TABLE MyChildTable (
    Tid BIGINT IDENTITY(1,1) NOT NULL PRIMARY KEY,
	Number INT,
	MyParentTableTid BIGINT,
	CONSTRAINT MyChildTable_MyParentTable_FK FOREIGN KEY ( MyParentTableTid ) REFERENCES MyParentTable ( Tid )
);
GO

-- Example table, used for the "insert into ... select"
CREATE TABLE MyDummyTable (
    Tid BIGINT IDENTITY(1,1) NOT NULL PRIMARY KEY,
	Number INT
);
GO

-- Populate the dummy table
DECLARE @Counter INT 
SET @Counter = 1
WHILE ( @Counter <= 100000 )
BEGIN
    INSERT INTO MyDummyTable ( Number ) VALUES ( @Counter );
    SET @Counter = @Counter + 1;
END

-- Create index on FK
CREATE INDEX MyChildTable_MyParentTable_IX ON MyChildTable ( MyParentTableTid );

-----------------------------------------------------------------------------------------------
-- END OF TEST SETUP
-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------
-- Session 1
-----------------------------------------------------------------------------------------------

-- Step 1:
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
BEGIN TRAN
    INSERT INTO MyParentTable VALUES ( 1 ); -- Insert first parent
-- Step 1 ends here

-- Step 3:
    BEGIN
        INSERT INTO MyChildTable ( Number, MyParentTableTid )
		    SELECT
		        TOP 4000 Tid,
		        1 -- parent ID
			FROM MyDummyTable
			ORDER BY Tid
    END
-- Step 3 ends here

ROLLBACK


-----------------------------------------------------------------------------------------------
-- Session 2 (copy the code below to a new query window / session)
-----------------------------------------------------------------------------------------------

-- Step 2:
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
BEGIN TRAN
    INSERT INTO MyParentTable VALUES ( 2 ); -- Insert second parent
-- Step 2 ends here

-- Step 4:
    BEGIN
        INSERT INTO MyChildTable ( Number, MyParentTableTid )
		    SELECT
		        TOP 4000 Tid,
		        2 -- parent ID
			FROM MyDummyTable
			ORDER BY Tid
    END
-- Step 4 ends here

ROLLBACK

If all went well, you got a deadlock from the code steps, as described.

Please notice that the rows are independent (different parents) and there is an index on the Foreign Key.

From my investigation, the locking behavior is not always the same, depending on the tables, if they have values, and so on, but the deadlock is almost always occurring.

If you change the TOP 4000 to smaller values (not deterministic, the value seems to depend on several things), but for example TOP 10 or TOP 5 should not lead to deadlocks. Using that method I could insert +30.000 rows in the same transaction for each of the two sessions, even alternating INSERT's between sessions, without ever getting a deadlock.

What seems to be occurring:

• First insert (parent) creates a X key lock on the inserted row, plus IX on its page and IX on the table (as expected!)
• Second insert, when the SELECT returns lots of rows (as is the case with the TOP 4000), SQL Server tries to issue a lock on the parent
  • This is usually a shared (S) page lock, but I've seen also an exclusive (X) key lock
  • This additional locking doesn't occur with a smaller SELECT
  • Note: the original scenario does not have a "TOP" keyword in the SELECT, but the query returns different set sizes and I suspect that the deadlock occurs when the estimated rows exceed some value threshold
• This second lock request is blocked, due to the other session's IX on the parent's page
• When we repeat the same INSERT INTO SELECT block on the other session, this behavior is replicated, also leading to the session being blocked, which causes the deadlock

What I find difficult to explain is the need to issue these extra locks. The parent is protected by the IX lock in that session/transaction, so there should be no need to protect the FK in this case with an additional lock, I think...?

Also, why only do it when the SELECT returns a few more rows (but not if we do it in small steps at a time, even on the same transaction)?

I would very much appreciate if someone could help me understand what's happening here. It almost feels like a bug, but maybe someone can explain the rationale for this behavior...?

Many thanks everyone! Best regards, Dave

Answer 1

you are probably running into common locks from page splits which ripple up the index (which is b-tree), especially when the depth is low, both sets of inserts will need to split a common set of parent rows. once the table is larger, and the keys not adjacent, this is less common, but always possible.

if you really need to prevent deadlocks and performance is not an issue, then take an exclusive lock on the MyParentTable table. this will serialize the bulk inserts.

Answer 2

I've been able to reproduce this on SQL 2022 CU7.

I can explain part of it, but not all.

The strange thing appears already after step 3. The first process gets blocked by the second window, waiting on a S lock in MyParentTable, which is blocked by an X lock by the second window. In sys.dm_tran_locks, I can find the lock resource, and when I run

SELECT * FROM MyParentTable WITH (NOLOCK) WHERE %%LOCKRES%% = '(f03d7d8b0dcc)' 

The returned value is 2, the row inserted by the second window. Why first window wants to read that row I don't know.

The next part is easier to understand. When the second process wants to insert rows into the child table, it wants page locks, but is being blocked by IX locks held by the first window, add we have a deadlock. This also explains why the number of rows matter. With fewer rows, there will be no page locks.

I need to investigate this more, but when I changed TOP 4000 to TOP 4, the first window did not block in step three.

I tried changing the key value for the second process, let's say 12. That alone did not change things. But when I inserted a row with Tid = 8, in the parent, step 3 did not block. So adjacent keys seems to be part of the equation.