Recently I spent some time on a recurring Deadlock problem on a customer’s site in a high concurrency environment. It was only after finding the solution on my own that I discovered that this particular problem is already well documented if you search for the right keyword. ¯\_(ツ)_/¯

Anyway, in this blog, I will give feedback with some useful information about this specific Deadlock case.

The Deadlock

Deadlock Graph

Here is a Deadlock graph similar to the real one the customer had in Production :

Deadlock Graph

Looking at the XML properties we can notice the isolation level of both transactions is Serializable and that it’s the same object (stored procedure) causing the deadlock.

Stored Procedure

Here is what the stored procedure looks like.

CREATE PROCEDURE dbo.[bigTransactionHistory]
	@TransactionID		bigint
	, @ProductID		int
	, @TransactionDate	datetime
	, @Quantity			int
	, @ActualCost		money
AS
BEGIN
	SET NOCOUNT ON;

	SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

	BEGIN TRAN
		IF EXISTS(SELECT 1 FROM [bigTransactionHistory] WHERE TransactionID = @TransactionID)
		BEGIN
			UPDATE dbo.[bigTransactionHistory]
			SET ProductID = @ProductID
				, TransactionDate =	@TransactionDate
				, Quantity =		@Quantity
				, ActualCost =		@ActualCost
			WHERE TransactionID = @TransactionID
		END
		ELSE
		BEGIN
			INSERT INTO [bigTransactionHistory](
				[TransactionID]
				, [ProductID]
				, [TransactionDate]
				, [Quantity]
				, [ActualCost])
			VALUES (
				@TransactionID
				, @ProductID
				, @TransactionDate
				, @Quantity
				, @ActualCost
			)
		END
	COMMIT
END

The stored procedure is doing an UPDATE or an INSERT based on the existence of the row inside the table.
The existence check is performed with the “IF EXISTS(SELECT…)”.

Serializable isolation level

The documentation mentions the following behavior for this level of isolation:

No other transactions can modify data that has been read by the current transaction until the current transaction completes.

Other transactions cannot insert new rows with key values that would fall in the range of keys read by any statements in the current transaction until the current transaction completes.

It’s the “IF EXISTS” which reads the row and holds a RangeS-S lock for the duration of the transaction.
If the Stored Procedure is run at the same time for the same key in two concurrent sessions the deadlock can occur.

StoredProcedureAndLocks

RangeS-S and RangeX-X are incompatible locks.

Range Locks compatibility matrix

Solution

To solve this deadlock I changed the Stored Procedure removing the IF EXISTS(SELECT..).

	SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

	BEGIN TRAN
			UPDATE dbo.[bigTransactionHistory]
			SET ProductID = @ProductID
				, TransactionDate =	@TransactionDate
				, Quantity =		@Quantity
				, ActualCost =		@ActualCost
			WHERE TransactionID = @TransactionID
		IF @@ROWCOUNT = 0
		BEGIN
			INSERT INTO [bigTransactionHistory](
				[TransactionID]
				, [ProductID]
				, [TransactionDate]
				, [Quantity]
				, [ActualCost])
			VALUES (
				@TransactionID
				, @ProductID
				, @TransactionDate
				, @Quantity
				, @ActualCost
			)
		END
	COMMIT

The UPDATE is performed at all times. If no row is updated (checked with @@ROWCOUNT) a new row is INSERTED, removing the need for a first RangeS-S lock and any Deadlock possibility.

UPSERT

This type of scenario is a classic and is called UPSERT.
You can find a great article about this from Michael J. Swart; SQL Server UPSERT Patterns and Antipatterns

UPSERT scenario, from Michael J. Swart

Interesting fact, some SQL Database Management Systems like CockroachDB implement an UPSERT statement.

This UPSERT article adds a UPDLOCK hint to the UPDATE statement.
The idea is to protect against a potential conversion deadlock. I have not encountered this type of deadlock but the addition of UPLOCK is a good thing to prevent any deadlock (and the associated retry logic). It will force other transactions to wait for the requested U lock.
The hint should be added to the UPDATE statement like this:

UPDATE dbo.[bigTransactionHistory] WITH (UPDLOCK)
SET ProductID = @ProductID
	, TransactionDate =	@TransactionDate
	, Quantity =		@Quantity
	, ActualCost =		@ActualCost
WHERE TransactionID = @TransactionID

Conclusion

The UPSERT pattern is very common but is not trivial to write correctly in SQL. I hope this can help you understand and solve this kind of Deadlocks.