Understanding a specific type of deadlock

Question

I'm trying to understand how a specific type of deadlock comes about.

I have a very simple deadlock graph with two resources and two processes. One is running a SELECT the other an UPDATE statement. I understand that there are situations where this can result in a deadlock, but I do not understand how it happens in this specific scenario.

Victim's query:

SELECT id_particle, id_event, dt_created, dt_rcvd, tlx_no, from_routename, re, deleted 
FROM msg_list 
WHERE to_routename =  @P0  
AND ((dt_answ IS NULL AND b_complete = 0 AND id_event=6) OR (id_event = 10 AND deleted = 0) 
OR (from_id_post = 9705 AND deleted = 0)) 
ORDER BY dt_created ASC

Winner's query:

UPDATE msg_list 
SET
  ID_EVENT=7, 
  STATUS='Answered', 
  DT_ANSW={ts '2017-02-12 05:34:14'
WHERE ID_PARTICLE = 46211816

The complete deadlock graph:

<deadlock-list>
 <deadlock victim="process30aa42d468">
  <process-list>
   <process id="process30aa42d468" taskpriority="0" logused="0" waitresource="PAGE: 6:1:155679 " waittime="921" ownerId="427175775" transactionname="SELECT" lasttranstarted="2017-02-12T05:34:48.293" XDES="0x3126fbba40" lockMode="S" schedulerid="4" kpid="10648" status="suspended" spid="184" sbid="0" ecid="0" priority="0" trancount="0" lastbatchstarted="2017-02-12T05:34:48.293" lastbatchcompleted="2017-02-12T05:34:48.280" lastattention="1900-01-01T00:00:00.280" clientapp="jTDS" hostname="LNS" hostpid="123" loginname="MsgStore" isolationlevel="read committed (2)" xactid="427175775" currentdb="6" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
    <executionStack>
     <frame procname="tempdb.dbo.#jtds000003_____________________________________________________________________________________________________________0042FD9D" line="1" stmtstart="92" stmtend="668" sqlhandle="0x030002005819e1b4efce580018a7000001000000000000000000000000000000000000000000000000000000">
SELECT id_particle, id_event, dt_created, dt_rcvd, tlx_no, from_routename, re, deleted FROM msg_list WHERE to_routename =  @P0  AND ((dt_answ IS NULL AND b_complete = 0 AND id_event=6) OR (id_event = 10 AND deleted = 0) OR (from_id_post = 9705 AND deleted = 0)) ORDER BY dt_created AS     </frame>
    </executionStack>
    <inputbuf>
Proc [Database Id = 2 Object Id = -1260316328]    </inputbuf>
   </process>
   <process id="process319282aca8" taskpriority="0" logused="21256" waitresource="PAGE: 6:1:396658 " waittime="869" ownerId="427175573" transactionname="implicit_transaction" lasttranstarted="2017-02-12T05:34:48.210" XDES="0x30c2dbc408" lockMode="IX" schedulerid="4" kpid="11980" status="suspended" spid="99" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2017-02-12T05:34:48.430" lastbatchcompleted="2017-02-12T05:34:48.427" lastattention="2017-02-12T03:34:28.130" clientapp="NotesMover" hostname="LNS" hostpid="8828" loginname="Notesmover" isolationlevel="read committed (2)" xactid="427175573" currentdb="6" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128058">
    <executionStack>
     <frame procname="adhoc" line="1" stmtstart="364" stmtend="812" sqlhandle="0x020000006d523b316d15563a50b97ce8d56da3cf6d8fc4450000000000000000000000000000000000000000">
unknown     </frame>
     <frame procname="adhoc" line="1" stmtend="554" sqlhandle="0x02000000d8b78713c51b1588947edf24f2d7b69031f4f1d60000000000000000000000000000000000000000">
unknown     </frame>
     <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown     </frame>
    </executionStack>
    <inputbuf>
UPDATE msg_list SET ID_EVENT=7, STATUS='Answered', DT_ANSW={ts '2017-02-12 05:34:14'WHERE ID_PARTICLE = 46211816    
    </inputbuf> 
   </process>
  </process-list>
  <resource-list>
   <pagelock fileid="1" pageid="155679" dbid="6" subresource="FULL" objectname="MsgStore.dbo.msg_list" id="lock31683f2400" mode="IX" associatedObjectId="72057594523811840">
    <owner-list>
     <owner id="process319282aca8" mode="IX"/>
    </owner-list>
    <waiter-list>
     <waiter id="process30aa42d468" mode="S" requestType="wait"/>
    </waiter-list>
   </pagelock>
   <pagelock fileid="1" pageid="396658" dbid="6" subresource="FULL" objectname="MsgStore.dbo.msg_list" id="lock2f80c2e300" mode="S" associatedObjectId="72057594523811840">
    <owner-list>
     <owner id="process30aa42d468" mode="S"/>
    </owner-list>
    <waiter-list>
     <waiter id="process319282aca8" mode="IX" requestType="wait"/>
    </waiter-list>
   </pagelock>
  </resource-list>
 </deadlock>
</deadlock-list>

And the graphical representation of same:

And here are the query plans that are generated when running those two queries:

The Victim:

The Winner:

The ncci_rcvd_list index used by the victim is a non-clustered covering index with a single key column and several included columns. One of those included columns is updated by the winner. The key column is not updated.

The mgs_list table has about 500,000 records. The result set returned by the SELECT query is usually only a few rows like a dozen or so (though occasionally it can be larger up to perhaps a couple thousand).

Can someone explain how this situation results in a deadlock?

This is captured from a production system where this occurs quite frequently. I have solved this by changing the transaction isolation level to read committed snapshot and it's no longer an issue but I'd like to understand what happened there and then also see if there is a different solution to the problem.

Answer 1

Page 155679 is owned by process319282aca8 (the UPDATE) in IX mode and wanted by process30aa42d468 (the SELECT) in S mode. Page 396658 is owned by SELECT in S mode and wanted by UPDATE in IX mode.

The problem is missing indexes, for both queries. The UPDATE uses an index but is not covering so it needs to look up RIDs into the clustered index. The SELECT is a scan (as given away by page level S locks...). This is guaranteed deadlock under concurrency.

This is yet another example of misusing tables as queues. Read Using tables as Queues. Separate your state from your events. Enqueue and dequeue only events.

PS. The 'victim' will always be the transaction that has less work to rollback, and in a read vs. write this will always be the read. Also, I doubt the SELECT execution plan you posted is the one that actually deadlocked.