How to avoid deadlocking in a stored procedure with SERIALIZABLE isolation level, INSERTs, UPDATEs, and DELETEs

Question

I'm having trouble with deadlocks in a stored procedure.

This stored procedure is part of a custom full-text-like search system. It's called after a record is updated, and inserts/updates a list of "words" and where those words are located in the record.

First, here are the tables the stored proc uses. I've simplified the column definition down to a list for simplicity and skipped the foreign keys, but I've included all index definitions.

CREATE TABLE FTS.Word (
    -- ID, 
    -- StringValue, DateValue, TimeValue, NumericValue, Unit,
    -- Metaphone, FK_BaseWord, BaseWordConfidence, IsStopWord

    CONSTRAINT PK_FTS_Word PRIMARY KEY (ID),
    INDEX IX_FTS_Word_FullValue (StringValue, DateValue, TimeValue, NumericValue, Unit),
    INDEX IX_FTS_Word_DateValue (DateValue),
    INDEX IX_FTS_Word_TimeValue (TimeValue),
    INDEX IX_FTS_Word_NumbValue (NumericValue, Unit),
    INDEX IX_FTS_Word_Metaphone (Metaphone),
    INDEX IX_FTS_Word_BaseWord  (FK_BaseWord)
)

CREATE TABLE FTS.WordUsage_RecordRegularColumn (
    -- ID,
    -- FK_InRecord, FK_InColumn, SubTableRecordID,
    -- FK_Word, FK_WordType, WordTypeConfidence,
    -- StartIndex, EndIndex, FullFieldMatch

    CONSTRAINT PK_FTS_WordUsageRC PRIMARY KEY (ID),
    INDEX IX_FTS_WordUsageRC_Location (FK_InRecord, FK_InColumn, SubTableRecordID),
    INDEX IX_FTS_WordUsageRC_Word     (FK_Word, FK_WordType)
)

CREATE TABLE FTS.WordUsage_RecordLookupColumn (
    -- ID,
    -- FK_InRecord, FK_InColumn, SubTableRecordID,
    -- FK_LookupItem

    CONSTRAINT PK_FTS_WordUsageLC PRIMARY KEY (ID),
    INDEX IX_FTS_WordUsageLC_Location (FK_InRecord, FK_InColumn, SubTableRecordID)
)

There are actually two stored procedures involved here. I extracted this bit out to its own stored proc to get rid of code duplication, because the same actions need to be performed in two circumstances. (The other is not really relevant to this question, so is not included.)

So this, InsertWords, only handles inserting new "words" into the Word table (and updating one column for certain existing ones). I believe I have gotten this to not deadlock when this is the only thing called from the RecordDataChanged proc (shown later).

CREATE PROCEDURE FTS.InsertWords
    @words AS FTS.InsertWord READONLY       -- table valued parameter
AS
BEGIN
    SET NOCOUNT ON

    /* **************************************************************************************** */
    -- insert the base word if it doesn't exist yet
    -- and/or anything that doesn't have a base word itself
    /* **************************************************************************************** */

    INSERT INTO FTS.Word
        (StringValue, DateValue, TimeValue, NumericValue, Unit, Metaphone, IsStopWord)
    SELECT DISTINCT
        inp.StringValue, inp.DateValue, inp.TimeValue, inp.NumericValue, inp.Unit, inp.Metaphone,
        CASE WHEN inp.StringValue IS NOT NULL AND EXISTS (SELECT 1 FROM FTS.StopWords WHERE Word = inp.StringValue)
            THEN 1
            ELSE 0
        END
    FROM @words inp
    LEFT JOIN FTS.Word exist WITH (UPDLOCK, INDEX(IX_FTS_Word_FullValue)) 
        ON (
            (exist.StringValue  IS NOT NULL AND exist.StringValue  = inp.StringValue ) OR
            (exist.DateValue    IS NOT NULL AND exist.DateValue    = inp.DateValue   ) OR
            (exist.TimeValue    IS NOT NULL AND exist.TimeValue    = inp.TimeValue   ) OR
            (exist.NumericValue IS NOT NULL AND exist.NumericValue = inp.NumericValue)
        ) AND (inp.Unit IS NULL OR exist.Unit = inp.Unit)
    WHERE exist.ID IS NULL          -- where not exists
        AND inp.BaseWord IS NULL

    /* **************************************************************************************** */
    -- insert the main word if it doesn't exist yet
    /* **************************************************************************************** */

    INSERT INTO FTS.Word
        (StringValue, DateValue, TimeValue, NumericValue, Unit, Metaphone, FK_BaseWord, BaseWordConfidence, IsStopWord)
    SELECT DISTINCT
        inp.StringValue, inp.DateValue, inp.TimeValue, inp.NumericValue, inp.Unit, inp.Metaphone,
        base.ID, inp.BaseWordConfidence,
        CASE WHEN inp.StringValue IS NOT NULL AND EXISTS (SELECT 1 FROM FTS.StopWords WHERE Word = inp.StringValue)
            THEN 1
            ELSE 0
        END
    FROM @words inp
    JOIN FTS.Word base ON inp.BaseWord = base.StringValue   -- only things w/ a string value have base words
    LEFT JOIN FTS.Word exist WITH (UPDLOCK, INDEX(IX_FTS_Word_FullValue)) 
        ON (
            (exist.StringValue  IS NOT NULL AND exist.StringValue  = inp.StringValue ) OR
            (exist.DateValue    IS NOT NULL AND exist.DateValue    = inp.DateValue   ) OR
            (exist.TimeValue    IS NOT NULL AND exist.TimeValue    = inp.TimeValue   ) OR
            (exist.NumericValue IS NOT NULL AND exist.NumericValue = inp.NumericValue)
        ) AND (inp.Unit IS NULL OR exist.Unit = inp.Unit)
    WHERE exist.ID IS NULL          -- where not exists
        AND inp.BaseWord IS NOT NULL

    /* **************************************************************************************** */
    -- update all
    /* **************************************************************************************** */

    UPDATE upd
    SET upd.BaseWordConfidence = inp.BaseWordConfidence
    FROM FTS.Word upd WITH (UPDLOCK, INDEX(IX_FTS_Word_FullValue))
    INNER JOIN @words AS inp ON  (
        (upd.StringValue  IS NOT NULL AND upd.StringValue  = inp.StringValue ) OR
        (upd.DateValue    IS NOT NULL AND upd.DateValue    = inp.DateValue   ) OR
        (upd.TimeValue    IS NOT NULL AND upd.TimeValue    = inp.TimeValue   ) OR
        (upd.NumericValue IS NOT NULL AND upd.NumericValue = inp.NumericValue)
    ) AND (inp.Unit IS NULL OR upd.Unit = inp.Unit)
    WHERE upd.BaseWordConfidence IS NOT NULL
        AND upd.BaseWordConfidence < inp.BaseWordConfidence
END

This one is where the problems seem to occur. This stored proc calls InsertWords, then inserts data into the two "word usage" tables. Rather than trying to handle updating existing items and only deleting ones that were removed, etc, I just delete all word uses in a given record field, and then insert whatever word uses it currently should have.

CREATE PROCEDURE FTS.RecordDataChanged
    @recordId AS bigint,
    @words    AS FTS.RecordDataWord READONLY    -- table valued parameter
AS
BEGIN
    SET NOCOUNT ON

    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
    BEGIN TRANSACTION

        /* **************************************************************************************** */
        -- call FTS.InsertWords
        /* **************************************************************************************** */

        DECLARE @insWords FTS.InsertWord

        INSERT INTO @insWords
        SELECT StringValue, DateValue, TimeValue, NumericValue, Unit, Metaphone, BaseWord, BaseWordConfidence
        FROM @words
        WHERE LookupTableId IS NULL

        EXEC FTS.InsertWords @insWords


        /* **************************************************************************************** */
        -- Now do the word usage table
        -- just delete all and insert all
        /* **************************************************************************************** */

        DELETE del
        FROM FTS.WordUsage_RecordRegularColumn del --WITH (UPDLOCK)     -- locks?
        JOIN @words inp ON
            @recordId            = del.FK_InRecord      AND
            inp.IndexedColumn    = del.FK_InColumn      AND
            inp.InSubtableRecord = del.SubTableRecordID
        WHERE inp.LookupTableId IS NULL

        DELETE del
        FROM FTS.WordUsage_RecordLookupColumn del --WITH (UPDLOCK)     -- locks?
        JOIN @words inp ON
            @recordId            = del.FK_InRecord      AND
            inp.IndexedColumn    = del.FK_InColumn      AND
            inp.InSubtableRecord = del.SubTableRecordID
        WHERE inp.LookupTableId IS NOT NULL


        /* **************************************************************************************** */
        -- insert to "RecordRegularColumn" word usage table
        /* **************************************************************************************** */

        INSERT INTO FTS.WordUsage_RecordRegularColumn --WITH (TABLOCK)
            (FK_InRecord, FK_InColumn, SubTableRecordID,
             FK_Word, FK_WordType, WordTypeConfidence,
             StartIndex, EndIndex, FullFieldMatch)
        SELECT
            @recordId, inp.IndexedColumn, inp.InSubtableRecord,
            word.ID, inp.WordType, inp.WordTypeConfidence,
            inp.StartIndex, inp.EndIndex, inp.IsFullMatch
        FROM @words inp
        JOIN FTS.Word word ON (
                (word.StringValue  IS NOT NULL AND word.StringValue  = inp.StringValue ) OR
                (word.DateValue    IS NOT NULL AND word.DateValue    = inp.DateValue   ) OR
                (word.TimeValue    IS NOT NULL AND word.TimeValue    = inp.TimeValue   ) OR
                (word.NumericValue IS NOT NULL AND word.NumericValue = inp.NumericValue)
            ) AND (inp.Unit IS NULL OR word.Unit = inp.Unit)
        WHERE inp.LookupTableId IS NULL AND
            (inp.IsFullMatch = 1 OR (inp.StartIndex IS NOT NULL AND inp.EndIndex IS NOT NULL))  -- one/other required, which base words don't (always) have


        /* **************************************************************************************** */
        -- insert to "RecordLookupColumn" word usage table
        /* **************************************************************************************** */

        INSERT INTO FTS.WordUsage_RecordLookupColumn --WITH (TABLOCK)
            (FK_InRecord, FK_InColumn, SubTableRecordID, FK_LookupItem)
        SELECT
            @recordId, inp.IndexedColumn, inp.InSubtableRecord,
            ltwu.ID
        FROM @words inp
        JOIN FTS.IndexedColumns             col  ON inp.IndexedColumn = col.ID
        JOIN FTS.LookupTableItem            lti  ON inp.LookupTableId = lti.ItemID AND lti.FK_LookupTable = col.FK_LookupTable
        JOIN FTS.WordUsage_LookupTableItems ltwu ON lti.ID = ltwu.FK_LookupTableItem
        WHERE inp.LookupTableId IS NOT NULL

    COMMIT TRANSACTION
END

I previously had a working version that didn't appear to deadlock (but I'm not sure how thoroughly I tested concurrency). But I had to change my table structure, and since then, I've been struggling to understand what I need to do to avoid deadlocking. Using a SERIALIZABLE transaction isolation level and UPDLOCKs seemed to be working then, so I carried that over to the new version.

Here's approximately what I had before I changed the table structure:

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN TRANSACTION

    -- this statement twice, just like the current version,
    -- once where inp.BaseWord IS NULL and once where inp.BaseWord IS NOT NULL
    INSERT INTO FTS.Word
    SELECT ...
    FROM @words
    LEFT JOIN FTS.Word WITH (UPDLOCK, HOLDLOCK)

    UPDATE -- BaseWordConfidence
    FROM FTS.Word upd WITH (UPDLOCK, HOLDLOCK)
    INNER JOIN @words
    
    DELETE del
    FROM FTS.WordUsage del WITH (UPDLOCK, HOLDLOCK)
    JOIN @words
    
    INSERT INTO FTS.WordUsage
    SELECT ... 
    FROM @words
    JOIN FTS.Word  -- no lock hint

COMMIT TRANSACTION

Final thoughts:

I could call InsertWords in one transaction, and handle the DELETE and INSERT in another, but the delete and insert must be in one transaction together. However - I tested this with the call to InsertWords commented out, and the DELETE and INSERT statements on their own still caused a deadlock. So I know there has to be more to it than that.

Answer 1

Ok, there is a lot to unpack in these procedures, so I'll do my best to lay it out in a comprehendible way.

The way your queries are written, they're likely to contain many non-SARGABLE predications that will produce table scans, and hold long locks. Making them susceptible to blocking and deadlocking each other. You want to make these transaction as short as possible, so they get out of the way of any other incoming transactions. Preferably, there would be a key to link the two tables together, instead of multiple OR conditions. However, if you must use multiple OR conditions, consider this...

1. Your procedures are accepting a table type parameters. These are similar to table variables, in that they often produce poor estimates and perform poorly. Consider dumping the contents to a #Temp table at the start of the procedure and then joining that to the other tables.

2. For predicates like this (exist.StringValue IS NOT NULL AND exist.StringValue = inp.StringValue ), instead use exist.StringValue = inp.StringValue. If either value is NULL, it will not return True. No need to explicitly check if the column IS NOT NULL before comparing it to another column.

3. Eliminate your use of the OR operator. You can use several smaller queries and union them together instead, or several smaller updates back to back for each condition. Using the OR operator as you are, SQL Server is not going to use your indexes, and that will make your transaction stay open longer. I talk about the use of OR in UPDATES here on my blog. Better yet, is there reason to believe that all columns should not contain data from the source?

4. Decide if you're more likely to have INSERTS or UPDATES, and follow this article from Aaron Bertrand on the best way to handle UPSERTS, choosing the pattern that most matches your need.

In Summary, for each OR condition that would be an INSERT and/or UPDATE, considering turning it into one simple UPSERT statement. Focus on small and short transactions, and then move on to the next OR condition, and so on. This should allow them to move fast, and avoid blocking and deadlocking.

Edit

Below is an example. I would consider writing one of these statements for each matching pattern you're looking for, and seeing how it performs. In this way, you're breaking each OR condition into its own transaction that should run fast, with minimal blocking. But again, if you had a Key column you could map to between the incoming and existing tables, this would be even easier.

UPSERT

BEGIN TRAN

INSERT INTO FTS.Word (
    StringValue, DateValue, TimeValue, NumericValue, Unit,
    Metaphone, FK_BaseWord, BaseWordConfidence, IsStopWord
)
SELECT inp.StringValue, inp.DateValue, inp.TimeValue, inp.NumericValue, inp.Unit, inp.Metaphone,
    NULL,NULL,
    CASE WHEN EXISTS (
        SELECT 1
        FROM FTS.StopWords
        WHERE Word = inp.StringValue
    )
    THEN 1
    ELSE 0
    END
FROM @words AS inp
WHERE inp.BaseWord IS NULL
    AND NOT EXISTS
    (
        SELECT 1 FROM dbo.Word WITH (UPDLOCK, SERIALIZABLE)
        WHERE Word.Unit = inp.Unit
            AND Word.StringValue = inp.StringValue
    )

UNION

SELECT inp.StringValue, inp.DateValue, inp.TimeValue, inp.NumericValue, inp.Unit, inp.Metaphone,
    base.ID, inp.BaseWordConfidence,
    CASE WHEN EXISTS (
        SELECT 1
        FROM FTS.StopWords
        WHERE Word = inp.StringValue
    )
FROM @words inp
JOIN FTS.Word base
    ON inp.BaseWord = base.StringValue   -- only things w/ a string value have base words
WHERE inp.BaseWord IS NULL
    AND NOT EXISTS
    (
        SELECT 1 FROM dbo.Word WITH (UPDLOCK, SERIALIZABLE)
        WHERE Word.Unit = inp.Unit
            AND Word.StringValue = inp.StringValue
    )

UPDATE upd
SET upd.BaseWordConfidence = inp.BaseWordConfidence
FROM FTS.Word upd
INNER JOIN @words AS inp
    ON upd.StringValue = inp.StringValue
        AND upd.Unit = inp.Unit
WHERE upd.BaseWordConfidence < inp.BaseWordConfidence

COMMIT TRAN