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

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" hostna开发者_StackOverflowme="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>

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.

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.

I suspect there must be some kind of key violation with delete and insert going at same time..?