Merge statement deadlocking itself

There would not be a problem if the table variable only ever held one value. With multiple rows, there is a new possibility for deadlock. Suppose two concurrent processes (A & B) run with table variables containing (1, 2) and (2, 1) for the same company.

Process A reads the destination, finds no row, and inserts the value '1'. It holds an exclusive row lock on value '1'. Process B reads the destination, finds no row, and inserts the value '2'. It holds an exclusive row lock on value '2'.

Now process A needs to process row 2, and process B needs to process row 1. Neither process can make progress because it requires a lock that is incompatible with the exclusive lock held by the other process.

To avoid deadlocks with multiple rows, the rows need to be processed (and tables accessed) in the same order every time. The table variable in the execution plan shown in the question is a heap, so the rows have no intrinsic order (they are quite likely to be read in insertion order, though this is not guaranteed):

The lack of consistent row processing order leads directly to the deadlock opportunity. A second consideration is that the lack of a key uniqueness guarantee means that a Table Spool is necessary to provide correct Halloween Protection. The spool is an eager spool, meaning all rows are written to a tempdb worktable before being read back and replayed for the Insert operator.

Redefining the TYPE of the table variable to include a clustered PRIMARY KEY:

DROP TYPE dbo.CoUserData;

CREATE TYPE dbo.CoUserData
AS TABLE
(
    MyKey   integer NOT NULL PRIMARY KEY CLUSTERED,
    MyValue integer NOT NULL
);

The execution plan now shows a scan of the clustered index and the uniqueness guarantee means the optimizer is able to safely remove the Table Spool:

In tests with 5000 iterations of the MERGE statement on 128 threads, no deadlocks occurred with the clustered table variable. I should stress that this is only on the basis of observation; the clustered table variable could also (technically) produce its rows in a variety of orders, but the chances of a consistent order are very greatly enhanced. The observed behaviour would need to be retested for every new cumulative update, service pack, or new version of SQL Server, of course.

In case the table variable definition cannot be changed, there is another alternative:

MERGE dbo.CompanyUser AS R
USING 
    (SELECT DISTINCT MyKey, MyValue FROM @DataTable) AS NewData ON
    R.CompanyId = @CompanyID
    AND R.UserID = @UserID
    AND R.MyKey = NewData.MyKey
WHEN NOT MATCHED THEN 
    INSERT 
        (CompanyID, UserID, MyKey, MyValue) 
    VALUES
        (@CompanyID, @UserID, NewData.MyKey, NewData.MyValue)
OPTION (ORDER GROUP);

This also achieves the elimination of the spool (and row-order consistency) at the cost of introducing an explicit sort:

This plan also produced no deadlocks using the same test. Reproduction script below:

CREATE TYPE dbo.CoUserData
AS TABLE
(
    MyKey   integer NOT NULL /* PRIMARY KEY */,
    MyValue integer NOT NULL
);
GO
CREATE TABLE dbo.Company
(
    CompanyID   integer NOT NULL

    CONSTRAINT PK_Company
        PRIMARY KEY (CompanyID)
);
GO
CREATE TABLE dbo.CompanyUser
(
    CompanyID   integer NOT NULL,
    UserID      integer NOT NULL,
    MyKey       integer NOT NULL,
    MyValue     integer NOT NULL

    CONSTRAINT PK_CompanyUser
        PRIMARY KEY CLUSTERED
            (CompanyID, UserID, MyKey),

    FOREIGN KEY (CompanyID)
        REFERENCES dbo.Company (CompanyID),
);
GO
CREATE NONCLUSTERED INDEX nc1
ON dbo.CompanyUser (CompanyID, UserID);
GO
INSERT dbo.Company (CompanyID) VALUES (1);
GO
DECLARE 
    @DataTable AS dbo.CoUserData,
    @CompanyID integer = 1,
    @UserID integer = 1;

INSERT @DataTable
SELECT TOP (10)
    V.MyKey,
    V.MyValue
FROM
(
    VALUES
        (1, 1),
        (2, 2),
        (3, 3),
        (4, 4),
        (5, 5),
        (6, 6),
        (7, 7),
        (8, 8),
        (9, 9)
) AS V (MyKey, MyValue)
ORDER BY NEWID();

BEGIN TRANSACTION;

    -- Test MERGE statement here

ROLLBACK TRANSACTION;

OK, after looking everything over a couple of times, I think that your basic assumption was correct. What's probably going on here is that:

1. The MATCH part of the MERGE checks the index for matches, read-locking those rows/pages as it goes.

2. When it has a row without a match, it will try to insert the new Index Row first so it will request a row/page write-lock ...

But if another user has also gotten to step 1 on the same row/page, then the first user will be blocked from the Update, and ...

If the second user also needs to insert on the same page, then they're in a deadlock.

AFAIK, there's only one (simple) way to be 100% sure that you cannot get a deadlock with this procedure and that would be to add a TABLOCKX hint to the MERGE, but that would probably have a really bad impact on performance.

It is possible that adding a TABLOCK hint instead would be enough to solve the problem without having to big an effect on your performance.

Finally, you could also try adding PAGLOCK, XLOCK or both PAGLOCK and XLOCK. Again that might work and performance might not be too awful. You'll have to try it to see.

I think SQL_Kiwi provided a very good analysis. If you need to solve the problem in the database, you should follow his suggestion. Of course you need to retest that it still works for you every time you upgrade, apply a service pack, or add/change an index or an indexed view.

There are three other alternatives:

1. You can serialize your inserts so that they do not collide: you can invoke sp_getapplock at the beginning of your transaction and acquire an exclusive lock before executing your MERGE. Of course you still need to stress test it.

2. You can have one thread handle all your inserts, so that your app server handles concurrency.

3. You can automatically retry after deadlocks - this may be the slowest approach if the concurrency is high.

Either way, only you can determine the impact of your solution on the performance.

Typically we do not have deadlocks in our system at all, although we do have a lot of potential for having them. In 2011 we made a mistake in one deployment and had half a dozen of deadlocks occur in a few hours, all following the same scenario. I fixed that soon and that was all the deadlocks for the year.

We are mostly using approach 1 in our system. It works really well for us.