SQL Server – Avoiding Deadlocks Without Restricting Parallelism

deadlockparallelismsql serversql server 2014

I have an update statement that is generating intra query parallelism deadlock. Based on this link I believe my two options to resolve this issue is to force SQL Server to avoid parallelism via an OPTION (MAXDOP 1) query hint or to add an index to reduce the cost so SQL Server decides on its own not to use a parallel plan.

Just to see the impact I set the max degrees of parallelism to 1 and it doubled the execution time from 0.5 seconds to 1 second. Since this query is run frequently I don't feel comfortable degrading the already poor performance. So far I've been unable to meaningfully improve the performance of the update statement to remove the parallelism. The query is below, and here is a link to the execution plan.

DECLARE @calllist_id int = 1;
DECLARE @customer_id int = NULL;

WITH ToUpdate AS 
(
    SELECT 
        CLQ.CallList_Queue_ID
        , newLastOpportunityCreateDate = MAX(O.CreateDate)
        , newLastOpportunity_ID = MAX(CLQO.Opportunity_ID)
    FROM tbl_CallList_Queue CLQ
        INNER JOIN tbl_CallList_Queue_Opportunity CLQO ON CLQ.CallList_Queue_ID = CLQO.CallList_Queue_ID
        INNER JOIN tbl_Opportunity O ON CLQO.Opportunity_ID = O.Opportunity_ID   
    WHERE 
        CLQ.CallList_ID = @calllist_id
        AND
        (
             @customer_id IS NULL
             OR 
             CLQ.Customer_ID = @customer_id
        )
    GROUP BY
        CLQ.CallList_Queue_ID
        , CLQ.LastOpportunityCreateDate
        , CLQ.LastOpportunity_ID
    HAVING
    (
        CLQ.LastOpportunityCreateDate IS NULL
        OR
        CLQ.LastOpportunityCreateDate < MAX(O.CreateDate)
        OR
        CLQ.LastOpportunity_ID IS NULL
        OR
        CLQ.LastOpportunity_ID < MAX(CLQO.Opportunity_ID)
    )
)
UPDATE CLQ
SET 
    LastOpportunityCreateDate = TU.newLastOpportunityCreateDate
    , LastOpportunity_ID = TU.newLastOpportunity_ID
FROM tbl_CallList_Queue CLQ 
    INNER JOIN ToUpdate TU on CLQ.CallList_Queue_ID = TU.CallList_Queue_ID;

As you'll see in the plan roughly 50% of the estimated cost is in updating the included columns in a non-clustered index. Is that the best place to consider optimizing since I haven't had much luck with optimizing elsewhere? Also there is a trigger that logs changes to the table that I didn't include in the plan I uploaded. I don't think the trigger is causing significant performance problems but it is present.

Here is the deadlock report pulled from the System Health Extended Event. As you can tell I prettied up the SQL a bit verses what I displayed above. The changes were just to improve alias names and remove the ubiquitous WITH(NOLOCK) query hints that are unfortunately part of the historical legacy of this code base.

<event name="xml_deadlock_report" package="sqlserver" timestamp="2018-12-03T20:25:08.807Z">
  <data name="xml_report">
    <type name="xml" package="package0" />
    <value>
      <deadlock>
        <victim-list>
          <victimProcess id="process3b5d29468" />
        </victim-list>
        <process-list>
          <process id="process3b5d29468" taskpriority="0" logused="0" waitresource="PAGE: 10:1:18686 " waittime="4963" ownerId="3780998682" transactionname="UPDATE" lasttranstarted="2018-12-03T13:25:03.703" XDES="0x3cb856fb0" lockMode="U" schedulerid="2" kpid="8340" status="suspended" spid="352" sbid="0" ecid="18" priority="0" trancount="0" lastbatchstarted="2018-12-03T13:25:03.710" lastbatchcompleted="2018-12-03T13:25:03.707" lastattention="1900-01-01T00:00:00.707" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" isolationlevel="read committed (2)" xactid="3780998682" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
          <process id="process3c1ea6ca8" taskpriority="0" logused="0" waitresource="PAGE: 10:1:127895 " waittime="3736" ownerId="3780998682" transactionname="UPDATE" lasttranstarted="2018-12-03T13:25:03.703" XDES="0x1b6c813050" lockMode="U" schedulerid="5" kpid="9608" status="suspended" spid="352" sbid="0" ecid="21" priority="0" trancount="0" lastbatchstarted="2018-12-03T13:25:03.710" lastbatchcompleted="2018-12-03T13:25:03.707" lastattention="1900-01-01T00:00:00.707" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" isolationlevel="read committed (2)" xactid="3780998682" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
          <process id="process23d219468" taskpriority="0" logused="0" waitresource="PAGE: 10:1:90295 " waittime="4970" ownerId="3780999522" transactionname="UPDATE" lasttranstarted="2018-12-03T13:25:03.733" XDES="0x2a4ece8040" lockMode="U" schedulerid="10" kpid="4084" status="suspended" spid="356" sbid="0" ecid="17" priority="0" trancount="0" lastbatchstarted="2018-12-03T13:25:03.740" lastbatchcompleted="2018-12-03T13:25:03.740" lastattention="1900-01-01T00:00:00.740" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" isolationlevel="read committed (2)" xactid="3780999522" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
          <process id="process2a1982d848" taskpriority="0" logused="0" waitresource="PAGE: 10:1:18686 " waittime="4970" ownerId="3780999522" transactionname="UPDATE" lasttranstarted="2018-12-03T13:25:03.733" XDES="0x1bd782e040" lockMode="U" schedulerid="5" kpid="8040" status="suspended" spid="356" sbid="0" ecid="18" priority="0" trancount="0" lastbatchstarted="2018-12-03T13:25:03.740" lastbatchcompleted="2018-12-03T13:25:03.740" lastattention="1900-01-01T00:00:00.740" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" isolationlevel="read committed (2)" xactid="3780999522" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
          <process id="process11628a0ca8" taskpriority="0" logused="0" waitresource="PAGE: 10:1:127895 " waittime="4966" ownerId="3780999522" transactionname="UPDATE" lasttranstarted="2018-12-03T13:25:03.733" XDES="0x28b357ac90" lockMode="U" schedulerid="7" kpid="6404" status="suspended" spid="356" sbid="0" ecid="24" priority="0" trancount="0" lastbatchstarted="2018-12-03T13:25:03.740" lastbatchcompleted="2018-12-03T13:25:03.740" lastattention="1900-01-01T00:00:00.740" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" isolationlevel="read committed (2)" xactid="3780999522" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
          <process id="process3bd04b088" taskpriority="0" logused="0" waitresource="PAGE: 10:1:90295 " waittime="3736" ownerId="3780998682" transactionname="UPDATE" lasttranstarted="2018-12-03T13:25:03.703" XDES="0x2391ef5ca0" lockMode="U" schedulerid="8" kpid="8168" status="suspended" spid="352" sbid="0" ecid="23" priority="0" trancount="0" lastbatchstarted="2018-12-03T13:25:03.710" lastbatchcompleted="2018-12-03T13:25:03.707" lastattention="1900-01-01T00:00:00.707" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" isolationlevel="read committed (2)" xactid="3780998682" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
          <process id="process1f85527c28" taskpriority="0" logused="10000" waittime="5003" schedulerid="8" kpid="7980" status="suspended" spid="352" sbid="0" ecid="25" priority="0" trancount="0" lastbatchstarted="2018-12-03T13:25:03.710" lastbatchcompleted="2018-12-03T13:25:03.707" lastattention="1900-01-01T00:00:00.707" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" isolationlevel="read committed (2)" xactid="3780998682" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
          <process id="process3b3b22ca8" taskpriority="0" logused="10000" waittime="5057" schedulerid="7" kpid="5344" status="suspended" spid="352" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2018-12-03T13:25:03.710" lastbatchcompleted="2018-12-03T13:25:03.707" lastattention="1900-01-01T00:00:00.707" clientapp=".Net SqlClient Data Provider" hostname="HWVPAPAC001" hostpid="5008" loginname="NGIC\AGTC-APP-HCI-Prod" isolationlevel="read committed (2)" xactid="3780998682" currentdb="10" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
              <frame procname="Foo.dbo.CallListDistributor_CallList_Rebuild_V2_Step6_Clear" line="16" stmtstart="888" stmtend="4200" sqlhandle="0x03000a0026ffbb1ed19a9e00eca2000001000000000000000000000000000000000000000000000000000000">
WITH toupdate as 
       (
              SELECT 
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              , newLastOpportunityCreateDate = Max(c.CreateDate)
              , newLastOpportunity_ID = Max(b.Opportunity_ID)
              FROM tbl_CallList_Queue a WITH(NOLOCK)
              INNER JOIN tbl_CallList_Queue_Opportunity b WITH(NOLOCK)
              ON a.CallList_Queue_ID = b.CallList_Queue_ID
              INNER JOIN tbl_Opportunity c WITH(NOLOCK)
              ON b.Opportunity_ID = c.Opportunity_ID   
              WHERE 
              a.CallList_ID = @tmpcalllist_id
              AND
              (
                     @tmpcustomer_id IS NULL
                     OR 
                     a.Customer_ID = @tmpcustomer_id
              )
              GROUP BY
              a.CallList_Queue_ID
              , a.LastOpportunityCreateDate
              , a.LastOpportunity_ID
              HAVING    </frame>
              <frame procname="adhoc" line="1" stmtstart="84" sqlhandle="0x01000a00197a883660fd14321400000000000000000000000000000000000000000000000000000000000000">
EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1    </frame>
              <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">
unknown    </frame>
            </executionStack>
            <inputbuf>
(@p0 int,@p1 int,@RETURN_VALUE int output)EXEC @RETURN_VALUE = [dbo].[CallListDistributor_CallList_Rebuild_V2_Step6_Clear] @calllist_id = @p0, @customer_id = @p1   </inputbuf>
          </process>
        </process-list>
        <resource-list>
          <pagelock fileid="1" pageid="18686" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock34211ea00" mode="U" associatedObjectId="72057605387976704">
            <owner-list>
              <owner id="process2a1982d848" mode="U" requestType="wait" />
            </owner-list>
            <waiter-list>
              <waiter id="process3b5d29468" mode="U" requestType="wait" />
            </waiter-list>
          </pagelock>
          <pagelock fileid="1" pageid="127895" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock111730a200" mode="U" associatedObjectId="72057605387976704">
            <owner-list>
              <owner id="process11628a0ca8" mode="U" requestType="wait" />
            </owner-list>
            <waiter-list>
              <waiter id="process3c1ea6ca8" mode="U" requestType="wait" />
            </waiter-list>
          </pagelock>
          <pagelock fileid="1" pageid="90295" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock281980c00" mode="U" associatedObjectId="72057605387976704">
            <owner-list>
              <owner id="process3b3b22ca8" mode="U" />
            </owner-list>
            <waiter-list>
              <waiter id="process23d219468" mode="U" requestType="wait" />
            </waiter-list>
          </pagelock>
          <pagelock fileid="1" pageid="18686" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock34211ea00" mode="U" associatedObjectId="72057605387976704">
            <owner-list>
              <owner id="process3b3b22ca8" mode="U" />
            </owner-list>
            <waiter-list>
              <waiter id="process2a1982d848" mode="U" requestType="wait" />
            </waiter-list>
          </pagelock>
          <pagelock fileid="1" pageid="127895" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock111730a200" mode="U" associatedObjectId="72057605387976704">
            <owner-list>
              <owner id="process3b3b22ca8" mode="U" />
            </owner-list>
            <waiter-list>
              <waiter id="process11628a0ca8" mode="U" requestType="wait" />
            </waiter-list>
          </pagelock>
          <pagelock fileid="1" pageid="90295" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock281980c00" mode="U" associatedObjectId="72057605387976704">
            <owner-list>
              <owner id="process23d219468" mode="U" requestType="wait" />
            </owner-list>
            <waiter-list>
              <waiter id="process3bd04b088" mode="U" requestType="wait" />
            </waiter-list>
          </pagelock>
          <exchangeEvent id="Port2832c76700" WaitType="e_waitPortClose" nodeId="45">
            <owner-list>
              <owner id="process3bd04b088" />
              <owner id="process3b5d29468" />
              <owner id="process3c1ea6ca8" />
            </owner-list>
            <waiter-list>
              <waiter id="process1f85527c28" />
            </waiter-list>
          </exchangeEvent>
          <exchangeEvent id="Port2832c76100" WaitType="e_waitPortOpen" nodeId="11">
            <owner-list>
              <owner id="process1f85527c28" />
            </owner-list>
            <waiter-list>
              <waiter id="process3b3b22ca8" />
            </waiter-list>
          </exchangeEvent>
        </resource-list>
      </deadlock>
    </value>
  </data>
</event>

Best Answer

This is an ordinary deadlock. Here's the resource list, transformed to show the spid for each process:

 <resource-list>

      <pagelock fileid="1" pageid="18686" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock34211ea00" mode="U" associatedObjectId="72057605387976704">
        <owner-list>
          <owner id="356-2" mode="U" requestType="wait" />
        </owner-list>
        <waiter-list>
          <waiter id="352-1" mode="U" requestType="wait" />
        </waiter-list>
      </pagelock>
      <pagelock fileid="1" pageid="127895" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock111730a200" mode="U" associatedObjectId="72057605387976704">
        <owner-list>
          <owner id="356-3" mode="U" requestType="wait" />
        </owner-list>
        <waiter-list>
          <waiter id="352-2" mode="U" requestType="wait" />
        </waiter-list>
      </pagelock>
      <pagelock fileid="1" pageid="90295" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock281980c00" mode="U" associatedObjectId="72057605387976704">
        <owner-list>
          <owner id="352-5" mode="U" />
        </owner-list>
        <waiter-list>
          <waiter id="356-1" mode="U" requestType="wait" />
        </waiter-list>
      </pagelock>
      <pagelock fileid="1" pageid="18686" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock34211ea00" mode="U" associatedObjectId="72057605387976704">
        <owner-list>
          <owner id="352-5" mode="U" />
        </owner-list>
        <waiter-list>
          <waiter id="356-2" mode="U" requestType="wait" />
        </waiter-list>
      </pagelock>
      <pagelock fileid="1" pageid="127895" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock111730a200" mode="U" associatedObjectId="72057605387976704">
        <owner-list>
          <owner id="352-5" mode="U" />
        </owner-list>
        <waiter-list>
          <waiter id="356-3" mode="U" requestType="wait" />
        </waiter-list>
      </pagelock>
      <pagelock fileid="1" pageid="90295" dbid="10" subresource="FULL" objectname="Foo.dbo.tbl_CallList_Queue" id="lock281980c00" mode="U" associatedObjectId="72057605387976704">
        <owner-list>
          <owner id="356-1" mode="U" requestType="wait" />
        </owner-list>
        <waiter-list>
          <waiter id="352-3" mode="U" requestType="wait" />
        </waiter-list>
      </pagelock>

You can see above that spid 356 has page U locks that 352 is waiting for, and spid 352 has page U locks that spid 356 is waiting for. The 'exchangeEvent' locks below don't show any such cycle of ownership among the processes for spid 352:

  <exchangeEvent id="Port2832c76700" WaitType="e_waitPortClose" nodeId="45">
    <owner-list>
      <owner id="352-3" />
      <owner id="352-1" />
      <owner id="352-2" />
    </owner-list>
    <waiter-list>
      <waiter id="352-4" />
    </waiter-list>
  </exchangeEvent>
  <exchangeEvent id="Port2832c76100" WaitType="e_waitPortOpen" nodeId="11">
    <owner-list>
      <owner id="352-4" />
    </owner-list>
    <waiter-list>
      <waiter id="352-5" />
    </waiter-list>
  </exchangeEvent>
</resource-list>

I don't have firm numbers at hand but this stored proc runs at least 500 times a day, but probably more for our bigger customers.

At this scale I would just wrap this in a transaction with a call to sp_getapplock at the top of the transaction and force it to run one-at-a-time.