Deadlock puzzle : Victim doesn't own any resource, used to kill to resolve deadlock

I've strange deadlock graph where the victim chosen by MSSQL server 2008 isn't part of the deadlock loop. This deadlock is between select and insert. The deadlock resource is a single table where all selects want waitresource = "KEY: 6:72057594098810880 (ffffffffffff)"

Question1 : Does ffffffffffff here mean they want a full range lock on whole table? Or whole key range? Or something else?

We are following a rule where table will never have a row with primary key id = 0. There are few places where we do this kind of check

select foo from bar where @someId = 0 OR SomeId = @someId.

I also came to know about that SQL doesn't short-circuit the expression. So if I pass @someId = 0 that doesn't guarantee the other part won't be evaluated. So it's possible that SQL can execute at runtime SomeId = @someId.

Question2 : Since it wasn't able to find 0 in SomeId, SQL will acquire a range lock on whole table (or row) so no one else inserts 0 id. Right?

With that assumption in mind I changed the where clause to this

(CASE
       WHEN @someId = 0 THEN 1
       WHEN SomeId = @someId THEN 1
       ELSE 0
END = 1)

hoping that this will force evaluation order. But I'm wrong. I'm getting the deadlock again. I've attached the deadlock graph below. I've renamed tables and sprocs involved (Company policy)

Question3 : Do you know what I'm missing here?

  <deadlock-list>
 <deadlock victim="process722c508">
  <process-list>
   <process id="process722c508" taskpriority="0" logused="0" waitresource="KEY: 6:72057594098810880 (ffffffffffff)" waittime="6217" ownerId="24219001" transactionname="SELECT" lasttranstarted="2011-05-17T03:29:16.033" XDES="0x80073a40" lockMode="RangeS-S" schedulerid="13" kpid="20436" status="suspended" spid="91" sbid="0" ecid="0" priority="0" trancount="0" lastbatchstarted="2011-05-17T03:29:16.033" lastbatchcompleted="2011-05-17T03:29:16.033" clientapp=".Net SqlClient Data Provider" hostname="SOMEHOST" hostpid="28820" loginname="someloginname" isolationlevel="serializable (4)" xactid="24219001" currentdb="6" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
    <executionStack>
     <frame procname="fnGetTableResultAByBId" line="44" stmtstart="2246" stmtend="3566" sqlhandle="0x03000600800d7f0bda124000d99e00000000000000000000">
INSERT INTO @ReturnTable
    SELECT Foo, Bar
    FROM TheOneTable 
    WHERE ZId = @zId 
    AND (CASE
            WHEN @yId = 0 THEN 1
            WHEN YId = @yId THEN 1
            ELSE 0
        END = 1)
    AND (CASE
            WHEN @xId = 0 THEN 1
            WHEN XId = @xId THEN 1
            ELSE 0
        END = 1)     </frame>
     <frame procname="GetViewCByDId" line="9" stmtstart="272" stmtend="2984" sqlhandle="0x03000600c21629025d8f3f00d99e00000100000000000000">
    </frame>
    </executionStack>
    <inputbuf>
Proc [Database Id = 6 Object Id = 36247234]    </inputbuf>
   </process>
   <process id="process7185048" taskpriority="0" logused="0" waitresource="KEY: 6:72057594098810880 (ffffffffffff)" waittime="6217" ownerId="24218992" transactionname="SELECT" lasttranstarted="2011-05-17T03:29:16.030" XDES="0x179980430" lockMode="RangeS-S" schedulerid="13" kpid="30616" status="suspended" spid="79" sbid="0" ecid="0" priority="0" trancount="0" lastbatchstarted="2011-05-17T03:29:16.030" lastbatchcompleted="2011-05-17T03:29:16.030" clientapp=".Net SqlClient Data Provider" hostname="SOMEHOST" hostpid="28820" loginname="someloginname" isolationlevel="serializable (4)" xactid="24218992" currentdb="6" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
    <executionStack>
     <frame procname="fnGetTableResultAByBId" line="44" stmtstart="2246" stmtend="3566" sqlhandle="0x03000600800d7f0bda124000d99e00000000000000000000">
INSERT INTO @ReturnTable
    SELECT Foo, Bar
    FROM TheOneTable 
    WHERE ZId = @zId 
    AND (CASE
            WHEN @yId = 0 THEN 1
            WHEN YId = @yId THEN 1
            ELSE 0
        END = 1)
    AND (CASE
            WHEN @xId = 0 THEN 1
            WHEN XId = @xId THEN 1
            ELSE 0
        END = 1)     </frame>
     <frame procname="GetViewCByDId" line="9" stmtstart="272" stmtend="2984" sqlhandle="0x03000600c21629025d8f3f00d99e00000100000000000000">
</frame>开发者_如何学编程
    </executionStack>
    <inputbuf>
Proc [Database Id = 6 Object Id = 36247234]    </inputbuf>
   </process>
   <process id="process7223048" taskpriority="0" logused="0" waitresource="KEY: 6:72057594098810880 (ffffffffffff)" waittime="5330" ownerId="24235090" transactionname="SELECT" lasttranstarted="2011-05-17T03:29:16.927" XDES="0x840d3b30" lockMode="RangeS-S" schedulerid="15" kpid="23452" status="suspended" spid="88" sbid="0" ecid="0" priority="0" trancount="0" lastbatchstarted="2011-05-17T03:29:16.927" lastbatchcompleted="2011-05-17T03:29:16.927" clientapp=".Net SqlClient Data Provider" hostname="SOMEHOST" hostpid="28820" loginname="someloginname" isolationlevel="serializable (4)" xactid="24235090" currentdb="6" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
    <executionStack>
     <frame procname="GetOneRowEByFId" line="11" stmtstart="260" stmtend="2456" sqlhandle="0x03000600db082c08ba823f00d99e00000100000000000000">
         SELECT TOP 1
         Col1, Col2, Col3

         FROM The2ndTable
         INNER JOIN [dbo].[TheOneTable] ON [dbo].[TheOneTable].[LinkBetweenOneAndTwoId]=[The2ndTable].[LinkBetweenOneAndTwoId]
         WHERE [dbo].[TheOneTable].ZId= @ActivityId and
         [TheOneTable].[n
     </frame>
    </executionStack>
    <inputbuf>
Proc [Database Id = 6 Object Id = 137103579]    </inputbuf>
   </process>
   <process id="process6334088" taskpriority="0" logused="0" waitresource="KEY: 6:72057594098810880 (ffffffffffff)" waittime="5668" ownerId="24229434" transactionname="SELECT" lasttranstarted="2011-05-17T03:29:16.587" XDES="0x17ea9ac90" lockMode="RangeS-S" schedulerid="12" kpid="5104" status="suspended" spid="86" sbid="0" ecid="0" priority="0" trancount="0" lastbatchstarted="2011-05-17T03:29:16.587" lastbatchcompleted="2011-05-17T03:29:16.587" clientapp=".Net SqlClient Data Provider" hostname="SOMEHOST" hostpid="28820" loginname="someloginname" isolationlevel="serializable (4)" xactid="24229434" currentdb="6" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
    <executionStack>
     <frame procname="GetOneRowEByFId" line="11" stmtstart="260" stmtend="2456" sqlhandle="0x03000600db082c08ba823f00d99e00000100000000000000">
SELECT TOP 1 
    Col1, Col2, Col3

    FROM The2ndTable
    INNER JOIN [dbo].[TheOneTable] ON [dbo].[TheOneTable].[LinkBetweenOneAndTwoId]=[The2ndTable].[LinkBetweenOneAndTwoId]
    WHERE [dbo].[TheOneTable].ZId= @ActivityId and
        [TheOneTable].[n</frame>
    </executionStack>
    <inputbuf>
Proc [Database Id = 6 Object Id = 137103579]    </inputbuf>
   </process>
   <process id="process8808e08" taskpriority="0" logused="0" waitresource="KEY: 6:72057594098810880 (ffffffffffff)" waittime="6652" ownerId="24217112" transactionname="SELECT" lasttranstarted="2011-05-17T03:29:15.610" XDES="0x833b5ca0" lockMode="RangeS-S" schedulerid="1" kpid="19752" status="suspended" spid="89" sbid="0" ecid="0" priority="0" trancount="0" lastbatchstarted="2011-05-17T03:29:15.610" lastbatchcompleted="2011-05-17T03:29:15.610" clientapp=".Net SqlClient Data Provider" hostname="SOMEHOST" hostpid="28820" loginname="someloginname" isolationlevel="serializable (4)" xactid="24217112" currentdb="6" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
    <executionStack>
     <frame procname="GetOneRowEByFId" line="11" stmtstart="260" stmtend="2456" sqlhandle="0x03000600db082c08ba823f00d99e00000100000000000000">
         SELECT TOP 1
         Col1, Col2, Col3

         FROM The2ndTable
         INNER JOIN [dbo].[TheOneTable] ON [dbo].[TheOneTable].[LinkBetweenOneAndTwoId]=[The2ndTable].[LinkBetweenOneAndTwoId]
         WHERE [dbo].[TheOneTable].ZId= @ActivityId and
         [TheOneTable].[n
     </frame>
    </executionStack>
    <inputbuf>
Proc [Database Id = 6 Object Id = 137103579]    </inputbuf>
   </process>
   <process id="process5c08988" taskpriority="0" logused="1644" waitresource="KEY: 6:72057594098810880 (91a0638558d2)" waittime="4889" ownerId="24214248" transactionname="user_transaction" lasttranstarted="2011-05-17T03:29:15.327" XDES="0x186609470" lockMode="RangeI-N" schedulerid="9" kpid="9000" status="suspended" spid="102" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2011-05-17T03:29:15.330" lastbatchcompleted="2011-05-17T03:29:15.330" clientapp=".Net SqlClient Data Provider" hostname="SOMEHOST" hostpid="28820" loginname="someloginname" isolationlevel="serializable (4)" xactid="24214248" currentdb="6" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
    <executionStack>
     <frame procname="InsertIntoTheOneTable" line="25" stmtstart="1334" stmtend="2608" sqlhandle="0x03000600bbbacb5d25883f00d99e00000100000000000000">
INSERT INTO [dbo].[TheOneTable] (Some,Col,Here)
    VALUES (@some,@col,@here)     </frame>
    </executionStack>
    <inputbuf>
Proc [Database Id = 6 Object Id = 1573632699]    </inputbuf>
   </process>
  </process-list>
  <resource-list>
   <keylock hobtid="72057594098810880" dbid="6" objectname="TheOneTable" indexname="PK_TheOneTable" id="lock6b17a00" mode="RangeI-N" associatedObjectId="72057594098810880">
    <owner-list />
    <waiter-list>
     <waiter id="process722c508" mode="RangeS-S" requestType="wait" />
    </waiter-list>
   </keylock>
   <keylock hobtid="72057594098810880" dbid="6" objectname="TheOneTable" indexname="PK_TheOneTable" id="lock6b17a00" mode="RangeI-N" associatedObjectId="72057594098810880">
    <owner-list />
    <waiter-list>
     <waiter id="process7185048" mode="RangeS-S" requestType="wait" />
    </waiter-list>
   </keylock>
   <keylock hobtid="72057594098810880" dbid="6" objectname="TheOneTable" indexname="PK_TheOneTable" id="lock6b17a00" mode="RangeI-N" associatedObjectId="72057594098810880">
    <owner-list />
    <waiter-list>
     <waiter id="process7223048" mode="RangeS-S" requestType="wait" />
    </waiter-list>
   </keylock>
   <keylock hobtid="72057594098810880" dbid="6" objectname="TheOneTable" indexname="PK_TheOneTable" id="lock6b17a00" mode="RangeI-N" associatedObjectId="72057594098810880">
    <owner-list />
    <waiter-list>
     <waiter id="process6334088" mode="RangeS-S" requestType="wait" />
    </waiter-list>
   </keylock>
   <keylock hobtid="72057594098810880" dbid="6" objectname="TheOneTable" indexname="PK_TheOneTable" id="lock6b17a00" mode="RangeI-N" associatedObjectId="72057594098810880">
    <owner-list>
     <owner id="process5c08988" mode="RangeI-N" />
    </owner-list>
    <waiter-list>
     <waiter id="process8808e08" mode="RangeS-S" requestType="wait" />
    </waiter-list>
   </keylock>
   <keylock hobtid="72057594098810880" dbid="6" objectname="TheOneTable" indexname="PK_TheOneTable" id="lock6372e80" mode="RangeS-S" associatedObjectId="72057594098810880">
    <owner-list>
     <owner id="process7223048" mode="RangeS-S" />
     <owner id="process6334088" mode="RangeS-S" />
    </owner-list>
    <waiter-list>
     <waiter id="process5c08988" mode="RangeI-N" requestType="wait" />
    </waiter-list>
   </keylock>
  </resource-list>
 </deadlock>
</deadlock-list>

In the context of locking, tables and their related indexes are separate entities. At times, dead locking happens between a table and its index, rather than between two separate tables.

The problem is most likely when a lock is aquired on an index and then another lock is aquired on the related table (i.e. bar) to do the data lookup. During the insert, this will happen in the opposite order. First, the table (i.e. bar) is locked and updated, then indexes are locked.

select foo 
from bar 
where @someId = 0 OR SomeId = @someId

Do you have/can you add a covering index (to help with the select) that contains both the SomeId and foo ? This way you'll avoid the lookup altogether and stop the problem from occuring.

Can you post the query plans rather than deadlock frames?

Would you mind trying some alternate criteria? I've been playing with this method lately (only I use NULLs not 0 to mean all values):

SET @yId = NullIf(@yId, 0);
SET @xId = NullIf(@xId, 0);

...
WHERE
   @yId BETWEEN Coalesce(@yId, 0) AND Coalesce(@yId, 2147483647)
   AND @xId BETWEEN Coalesce(@xId, 0) AND Coalesce(@xId, 2147483647)

Or you could use your zeroes intact:

WHERE
   @yId BETWEEN @yId AND Coalesce(NullIf(@yId, 0), 2147483647)
   AND @xId BETWEEN @xId AND Coalesce(NullIf(@xId, 0), 2147483647)

Thinking about this a little more... just to review, deadlocks only occur because of conflicting resource acquisition order. A resource is not just a table but rows, extents, pages, etc. If two queries are being submitted at once that initially acquire a smaller granularity lock, then escalate their locks to a something that overlaps the smaller lock the other process has, then you get a deadlock.

So, is there any way you can either acquire the larger lock earlier, avoid acquiring the larger conflicting lock, or change the resource acquisition order?

You could experiment with using WITH (TABLOCKX) which sounds horrible, but if your @yId or @xId is 0 thus making you select all rows, you're going to need the whole table anyway.

Have you also considered trying OPTION (MAXDOP 1) just to see if it helps? Theoretically, having multiple streams for the same data request could increase the likelihood of conflicting locks being acquired simultaneously.

Does the table have a clustered index? If not, add it, and if so, is it being used or can you force it to be used? This potentially could make the queries access the table in a different way, preventing the deadlock.

Post your comments and I'll see if any more ideas come up based on your responses.