How can I avoid a deadlock between these two SQL statements?

Question

I have two stored procedures running in separate threads, running on SQL Server 2005. One procedure inserts new rows into a set of tables and the other procedure deletes old data from the same set of tables. These procedures are running into a deadlock on the tables DLevel and Model. Here is the schema:

_{(source: barramsoft.com)}

Table DFile: Primary Key = DFileID
Table DLevel: Primary Key = DLevelID, Foreign Key: DFileID
Table Model: Primary Key = ModelID, Foreign Key: DFileID
Table ELement: Primary key = ElementID, Foreign Key1: DFileID, Foreign Key2: DLevelID

I have isolated the exact two SQL statements (one from each stored procedure) that are causing the deadlock. I have seen the deadlock reported by either of the procedures. I use top (1000) in both cases and both statements are executed in a loop until they complete with no rows left to delete/insert.

SQL Statement 1:

while (...)
begin
    delete top (1000) from DLevel where DFileID = @fileID1
    ...
end

SQL Statement 2:

while (...)
begin
    insert into Element (ElementID, DFileID, LevelNum, ...)
       select top (1000) el.ElementID, el.DFileID, el.LevelNum, ...
       from   ElementLoader el with (nolock)
              left outer join Element e with (nolock)
                   on e.ElementID = el.ElementID
       where  el.DFileID = @fileID2
       and    e.ElementID is null
       order  by el.ElementID
    ...
end

Note: The values for @fileID1 and @fileID2 are always guaranteed to be different. DLevel table has on average approx. 60 rows for a single DFileID and thus would complete deletion of all rows in a single pass.

How can I avoid a deadlock between these two SQL statements?

Edit 1: Rewritten to better clarify issue; added image; simplified SQL and removed join to DLevel table, which did not contribute to deadlock.

Edit 2: Added XML of deadlock graph.
Deadlock now occurs on Model table. Similar delete statement and schema for Model as for DLevel table.

<deadlock victim="process2bae38">
    <process-list>
        <process id="process2bae38" taskpriority="0" logused="4760" waitresource="PAGE: 11:1:1946" waittime="46" ownerId="4127445" transactionname="DELETE" lasttranstarted="2010-06-24T16:19:00.107" XDES="0xffffffff90552ae0" lockMode="S" schedulerid="1" kpid="14252" status="suspended" spid="58" sbid="0" ecid="0" priority="0" transcount="2" lastbatchstarted="2010-06-24T16:19:00.107" lastbatchcompleted="2010-06-24T16:19:00.107" clientapp=".Net SqlClient Data Provider" hostname="LT0103" hostpid="1668" loginname="NT AUTHORITY\SYSTEM" isolationlevel="read committed (2)" xactid="4127445" currentdb="11" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
                <frame procname="CadExplorer5.dbo.pCleanUpOldFiles" line="364" stmtstart="23718" stmtend="23834" sqlhandle="0x03000b00fb1c2229b1a7f7009f9d00000100000000000000">
delete top (@batchSize) from Model where DFileID = @fileID     </frame>
            </executionStack>
            <inputbuf>
Proc [Database Id = 11 Object Id = 690101499]    </inputbuf>
        </process>
        <process id="process2c95b8" taskpriority="0" logused="283388" waitresource="KEY: 11:72057594039304192 (8100bdf15e8b)" waittime="78" ownerId="4127412" transactionname="INSERT" lasttranstarted="2010-06-24T16:19:00.103" XDES="0xffffffff81d5ef18" lockMode="S" schedulerid="2" kpid="8460" status="suspended" spid="63" sbid="0" ecid="0" priority="0" transcount="2" lastbatchstarted="2010-06-24T16:18:59.413" lastbatchcompleted="2010-06-24T16:18:59.413" clientapp=".Net SqlClient Data Provider" hostname="LT0103" hostpid="1668" loginname="NT AUTHORITY\SYSTEM" isolationlevel="read committed (2)" xactid="4127412" currentdb="11" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">
            <executionStack>
                <frame procname="CadExplorer5.dbo.pLoadElements" line="288" stmtstart="28796" stmtend="33194" sqlhandle="0x03000b00a689fe2b2c5107019f9d00000100000000000000">
insert into Element (
                        ElementID, DFileID, ModelID, ElementTypeID, CADElementID,
                        ParentID,
                        LevelNum,
                        Depth, NumChildren,
                        Color, Weight, Style, Xlo, Ylo, Zlo, Xhi, Yhi, Zhi,
                        Diagonal, XCenter,
                        BitFlags, ElementModTime
                        )
                  select top (@batchSize)
                        el.ElementID, el.DFileID, el.ModelID, el.ElementTypeID, el.CADElementID,
                        parent.ElementID as ParentID,
                        (case when el.LoaderType = 1 and et.IsGraphical = 1 then el.LevelAttrib else null end) as LevelNum,
                        --l.LevelNum,
                        el.Depth, el.NumChildren,
                        el.Color, el.Weight, el.Style, el.Xlo, el.Ylo, el.Zlo, el.Xhi, el.Yhi, el.Zhi,
                        el.Diagonal, el.XCenter,     </frame>
            </executionStack>
            <inputbuf>
Proc [Database Id = 11 Object Id = 738101670]    </inputbuf>
        </process>
    </process-list>
    <resource-list>
        <pagelock fileid="1" pageid="1946" dbid="11" objectname="CadExplorer5.dbo.Element" id="lockffffffff86ffd080" mode="IX" associatedObjectId="72057594039107584">
            <owner-list>
                <owner id="process2c95b8" mode="IX"/>
            </owner-list>
            <waiter-list>
                <waiter id="process2bae38" mode="S" requestType="wait"/>
            </waiter-list>
        </pagelock>
        <keylock hobtid="72057594039304192" dbid="11" objectname="CadExplorer5.dbo.Model" indexname="PK_Model" id="lockffffffff8d66db80" mode="X" associatedObjectId="72057594039304192">
            <owner-list>
                <owner id="process2bae38" mode="X"/>
            </owner-list>
            <waiter-list>
                <waiter id="process2c95b8" mode="S" requestType="wait"/>
            </waiter-list>
        </keylock>
    </resource-list>
</deadlock>

Answer 1

One possible scenario: one connection insert a row in Element, and that row refers to a row in DLevel, and that row in DLevel is being deleted by another connection. Your nolock hint does not apply to foreign keys.

Answer 2

You might try removing the Foreign Key to DLevel.DFileID from the Element table. Since you have a Primary Key on DLevel.DlevelID and you reference that as a Foreign key in Element, the DFileID foreign key is not really needed.