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 :

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.

RangeS-S and RangeX-X are incompatible locks.

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

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.