The first query in the deadlock will very likely have a full table or index scan because of the non-SARGable criteria you wrote for the wait-time. Because you used a CTE in an attempt to quickly isolate rows, you also have the problem of executing a SELECT, an UPDATE, and a JOIN instead of just doing a quick update and getting out. That would probably explain the deadlock, as well, because you're not doing just an UPDATE.

I recommend you rewrite the first query as the following. You can do the TOP thing if you insist, but I don't believe it will be necessary once you have the index I recommend in a bit in place.

UPDATE dbo.TableA

SET TableAStatusTypeID = 9

WHERE WaitingRoomCreationTime <= DATEADD(mi,-@wrExpirationMinutes,@curUtcDate)

AND TableAStatusTypeID IN (1,2,3,4)

;

Once that's done, it would really help the performance if you put an index on the WaitingRoomCreationTime. It may be a hindrence to add TableAstatusTypeID to that index because then you'd be updating an index column but you'd have to try both ways to see which the optimizer thinks is best. With either index, I would add the TableAID as the final column of the index (not as an INCLUDE, either) so that you can make the index UNIQUE which will prevent SQL Server from adding a rather lengthy uniquifier to the index and make the row lookup that will occur a bit faster. SQL Server LOVES unique indexes.

You have a similar problem with your second query (the DELETE). In essence, you're first doing a SELECT followed by a joined delete all in one query. I'd rewrite it as follows.

DELETE FROM dbo.TableA

WHERE TableAStatusTypeID IN (11,12)

;

If you really need to do it in segments according to TOP (@TOP_HANDLED_ROWS), then use a Temp Table to isolate the rows instead of a CTE to get the SELECT part of it all out of the transaction. Like this...

SELECT TOP (@TOP_HANDLED_ROWS)

TableAID

INTO #MyHead

FROM dbo.TableA

WHERE TableAStatusTypeID IN (11,12)

ORDER BY TableAID

;

DELETE FROM dbo.TableA

WHERE TableAID IN (SELECT TableAID FROM #MyHead)

;

Notice in the above that we're doing deletes in the same order as what I expect the Clustered Index will be. That moves most of the deletes away from what is usually the most active section of the table (the most recent IDs) and keeps from having a shotgun effect which scatters the deletes across a larger part of the table.

For those about to jump on me about the use of "IN", you'll find that "IN" is frequently faster than an actual INNER JOIN. I'd offer proof of that in the form of code but I don't want to hijack this thread with such proof.

Of course, all of this is just a suggestion because I don't actually have your data to experiement with. I can only tell you that I've solved many a deadlock using the methods I've described. Your mileage may vary and you'll need to experimennt. My methods are not a panacea 😉