Sql-server – Set the Deadlock Priority to Lowest possible value, but the script is still NOT always the victim in deadlock situations

Deleted my previous answer when I realised the trace shows parallelism.

With a big warning to test this very very thoroughly, you might alleviate the deadlocks by restricting MAXDOP and adding a UPDLOCK hint on Table1. I would also (as per @Aaron's suggestion) try EXISTS.

DELETE 
    d
FROM 
    Table1 d WITH (UPDLOCK)
INNER JOIN
    #deleteEntities de
ON  de.id = oeh.EntityId 
WHERE EXISTS
    (
    SELECT
        NULL
    FROM
        dbo.Table2 orc 
    INNER JOIN
        dbo.Table3 orr 
    ON  orr.id = orc.Table3Id
    INNER JOIN 
        dbo.Table4 oeh            
    ON  oeh.id = orr.Table4Id
    WHERE
        oeh.id = de.Table2Id
    ) OPTION (MAXDOP 1, RECOMPILE)

This would be the sledgehammer approach. It's likely you could eliminate the parallelism with appropriate indexing but can't advise on that unless we see an execution plan and or statistics.

@deleteEntities in the deadlock trace is a little "suspicious". You're passing in a single identifer but have this temporary table in there?. Optimiser is likely to be producing an execution plan that estimates 1 for this, so if it contains a variable number of rows I'd switch to temporary table and force recompile (as above).

Original post describes a classic deadlock scenario with a twist, namely, a single DELETE ... WITH statement, which acquires 2 different kinds of locks.

Recommendation - change table from All Page Lock (APL) to Data Row Lock (DRL) scheme

• clustered index will be replaced by placement index separate from data page
• index access / updates will use latches rather than logical locks
• row-level deadlock conflict is less probably (than page-level's)

Both SPIDs are executing the same sproc with the 1st DELETE ... WHERE statement demanding 2 different kinds of locks:

• initially an UPDATE lock on a page when scanning for a row to delete (UPDATE lock is compatible with shared locks only but not with another UPDATE lock or exclusive lock);
• once a target row is found on a page, then the UPDATE lock must be upgraded to an exclusive lockbefore deleting that row.

The DEADLOCK events posted in your original question confirm the scenario :

• SPID 134 has held an exclusive lock on a page while waiting to acquire an UPDATE lock on another page i.e. it has deleted at least one row already and is continuing with searching for another (row to delete);
• SPID 166 blocks the first SPID's acquiring an UPDATE lock on a page while waiting to apply an exclusive lock on another page, which has an exclusive lock held by SPID 134 already (after deleting 1 row or more).