Here’s an example of the classic scenario that is usually used to introduce the concept of a deadlock in a database:
1. Begin Transaction
2. Update Part table
2. Update Supplier table
3. Update Supplier table
3. Update Part table
4. Commit Transaction
If Process A and Process B each reached step #3 in their respective transactions at approximately the same time, it’s easy to see how they could end up blocking each other. The most obvious solution to this deadlock is to change the order of the UPDATE statements in one of the transactions, so that lock resources are acquired in a consistent order.
Instead of this overly simplistic deadlock, let’s take a closer look at the deadlock scenario demonstrated in Deadlock Troubleshooting, Part 2. In that case, these two stored procedures ended up deadlocked:
CREATE PROC p1 @p1 int AS
SELECT c2, c3 FROM t1 WHERE c2 BETWEEN @p1 AND @p1+1
CREATE PROC p2 @p1 int AS
UPDATE t1 SET c2 = c2+1 WHERE c1 = @p1
UPDATE t1 SET c2 = c2-1 WHERE c1 = @p1
There’s no UPDATE, DELETE, or INSERT in the first proc; it consists of a single SELECT. And even the two UPDATE statements in the second proc aren’t wrapped in an outer BEGIN TRAN/COMMIT TRAN. Both UPDATEs ran within their own autocommit transaction, which means that only one of them could have been involved in the deadlock. Clearly this doesn’t fit the stereotypical “modify A then modify B / modify B then modify A” deadlock model described above. This isn’t an edge case, by the way. We actually see this type of deadlock – where one or both of the participants are in the middle a single-query, autocommit transaction – more often than easy-to-understand deadlock scenarios involving two multi-statement transactions that just modify two tables in a different order.
So, what would you do if DTA hadn’t automagically recommended a new index that prevented this deadlock? To craft your own solution by hand, you need a deeper understanding of the deadlock than we have at the moment.
What caused this deadlock?
We’ll need to refer back to the deadlock summary that was distilled from the -T1222 output (see Deadlock Troubleshooting, Part 1 for a refresher on decoding -T1222):
Spid X is running this query (line 2 of proc [p1], inputbuffer “… EXEC p1 4 …”): SELECT c2, c3 FROM t1 WHERE c2 BETWEEN @p1 AND @p1+1 Spid Y is running this query (line 2 of proc [p2], inputbuffer “EXEC p2 4”): UPDATE t1 SET c2 = c2+1 WHERE c1 = @p1 The SELECT is waiting for a Shared KEY lock on index t1.cidx. The UPDATE holds a conflicting X lock. The UPDATE is waiting for an eXclusive KEY lock on index t1.idx1. The SELECT holds a conflicting S lock.
First, let’s look at the query plan for the SELECT query. To view the plan, execute “SET STATISTICS PROFILE ON”, then run “EXEC p1 4”.
SELECT c2, c3 FROM t1 WHERE c2 BETWEEN @p1 AND @p1+1
|--Nested Loops(Inner Join, OUTER REFERENCES:([Uniq1002], [t1].[c1]))
|--Index Seek(OBJECT:([t1].[idx1]), SEEK:([t1].[c2] >= [@p1] AND [t1].[c2] <= [@p1]+(1)) ORDERED FORWARD)
|--Clustered Index Seek(OBJECT:([t1].[cidx]), SEEK:([t1].[c1]=[t1].[c1] AND [Uniq1002]=[Uniq1002]) LOOKUP ORDERED FORWARD)
A Nested Loop join executes its first child operator once, and executes the second child operator for each row returned by the first child (see this post for details). In this case, the first child is a nonclustered Index Seek to find the rows “WHERE c2 BETWEEN @p1 AND @p1+1”. For each qualifying row in the nonclustered index, a second seek is done on the clustered index to look up the whole data row. This clustered index seek is necessary because the nonclustered index does not cover the query. If you’re running SQL 2000, you’ll see a different-looking plan:
SELECT c2, c3 FROM t1 WHERE c2 BETWEEN @p1 AND @p1+1
|--Bookmark Lookup(BOOKMARK:([Bmk1000]), OBJECT:([t1]))
|--Index Seek(OBJECT:([t1].[idx1]), SEEK:([t1].[c2] >= [@p1] AND [t1].[c2] <= [@p1]+1) ORDERED FORWARD)
For practical purposes, these two plans are identical. The purpose of the Bookmark Lookup operator in the SQL 2000 plan is to visit the clustered index to retrieve the full set of columns for a row identified by a nonclustered index. In SQL 2005 this same operation is expressed as a loop join between the nonclustered index and the clustered index. For this deadlock, it’s simply important to note that both plans calls for a seek from the nonclustered index, then a seek from the clustered index.
Now let’s look at the UPDATE:
UPDATE t1 SET c2 = c2+1 WHERE c1 = @p1
|--Clustered Index Update(OBJECT:([t1].[cidx]), OBJECT:([t1].[idx1]), SET:([t1].[c2] = [Expr1004]))
|--Compute Scalar(DEFINE:([Expr1004]=[t1].[c2]+(1), [Expr1013]=CASE WHEN CASE WHEN ...
|--Top(ROWCOUNT est 0)
|--Clustered Index Seek(OBJECT:([t1].[cidx]), SEEK:([t1].[c1]=[@p1]) ORDERED FORWARD)
The UPDATE has a fairly simple query plan. The two most significant operators are the first and the last one. The Clustered Index Seek locates the rows that quality for the “WHERE c1 = @p1” predicate. Once a qualifying row has been found, the Clustered Index Update operator acquires an eXclusive key lock on the clustered index and modifies the row.
We now have a full understanding of how the UPDATE blocks the SELECT: the UPDATE acquires an X lock on a clustered index key, and that lock blocks the SELECT’s bookmark lookup on the clustered index. But the other half of the deadlock – the reason that the SELECT blocks the UPDATE – isn’t quite so obvious. The -T1222 told us “The UPDATE is waiting for an eXclusive KEY lock on index t1.idx1. The SELECT holds a conflicting S lock.” It’s not very apparent from the plan, but the UPDATE needs an X lock on the nonclustered index [idx1] because the column it is updating ([c2]) is one of the non-clustered index’s key columns. Any change to an index key column means that a row in the index must be relocated, and that relocation requires an X lock.
This is a key point to remember when trying to understand many deadlocks: the access path to find the qualifying rows is important, but index updates implied by the columns being modified can be just as important. To make things more confusing, sometimes you’ll see explicit “Index Update” or “Index Delete” operators in the plan for each nonclustered index that needs to be updated, while other times these don’t show up in the plan. (For more info on this check out Wide vs. Narrow Plans.)
To summarize: the SELECT used the nonclustered index to find a qualifying row. While holding a Shared lock on the nonclustered index, it needs to jump over to the clustered index and retrieve some columns that aren’t part of the nonclustered index. While it’s doing this, the UPDATE is busy doing a seek on the clustered index. It finds a row, locks it and modifies it. But because one of the columns being modified is a key column in the nonclustered index, it then has to move to the nonclustered index and update that index, too. This requires a second X key lock on the nonclustered index. So, the SELECT ends up blocked waiting for the UPDATE to release his X lock on the clustered index, while the UPDATE winds up blocked and waiting for the SELECT to release his S lock on the nonclustered index.
Hopefully it’s clear that even though each participant in this deadlock is just a single query, this is still a problem caused by out-of-order resource access patterns. The SELECT statement locks a key in the nonclustered index, then locks a key in the clustered index. The problem is that the UPDATE needs to lock the same two resources, but because of its query plan, it tries to lock them in the opposite order. In a sense, it’s really the same problem as the simple deadlock scenario described at the beginning of this post.
The locks acquired by a query aren’t acquired all at once. A query plan is like a little program. It wouldn’t be terribly inaccurate, for example, to think of a nested loop join as a FOR loop. Each iteration of the loop acquires a key lock on the outer table, then holds that lock while looking up (and locking) matching rows in the inner table. Deadlocks like this one are a little harder to figure out because the order of resource access within a single query depends on the query plan, and can’t be determined just by looking at the T-SQL.
How did DTA’s new index avoid the deadlock?
Here’s an index that will prevent this deadlock:
CREATE INDEX idx2 ON t1 (c2, c3)
This index “covers” the query “SELECT c2, c3 FROM t1 WHERE c2 BETWEEN @p1 AND @p1+1”, which is just another way of saying that the index includes all of the columns referenced by the query. SQL will use this index instead of the [idx1] index because the plan based on the covering index is cheaper. The fact that the index covers the query means that the bookmark lookup against the clustered index is no longer necessary. And since the SELECT no longer needs to access the clustered index, it won’t get blocked by the UPDATE’s lock on the clustered index.
What other solutions are available?
All deadlocks boil down to out-of-order resource access patterns. In the simple deadlock scenario described at the beginning of this post, the solution is obvious: just reverse the two UPDATE statements in one of the transactions, and you won’t end up deadlocked. But in the more complex scenario that we just explored, it’s not so clear how to change the order in which locks are acquired. Each deadlock participant is running a single-query, autocommit transaction, so you can’t just swap the order of two queries to acquire resources in a different order. SQL is a language designed to express high-level set operations; the specifics of how the database should go about retrieving and updating the specified set of data is generally left up to the SQL engine, with good reason. However, you do have some options for either influencing which lock resources a query needs, or modifying the order in which it acquires the locks. Below are six different possible solutions to this deadlock. Some of these are not ideal for this particular deadlock, but they are still worth exploring since the approach to deadlock avoidance that they illustrate may be the best possible solution for some other deadlock you encounter.
If you can think of any other solutions, please share them in a comment.
Your deadlock is not a "normal" lock deadlock; it's a parallel thread deadlock. Note that the resources are "exchangeEvent" resources, and all participants in the deadlock are threads from the same spid (51). This is a query that is deadlocking with itself.
It's a query in a longish proc (line number 546), but to get the specific proc name and stmt text you'll need to capture a profiler trace. Once you've identified the query, the easiest workaround is to prevent parallel execution either by tuning the query (parallelism like this generally suggests a large table scan, hash, or sort) or by adding an "OPTION (MAXDOP 1)" query hint to the query.
Sorry, I didn't have time to read all the comments(maybe this situation is mentioned in them) but one of the most "baffling" deadlocks is when you have a select being the cause of the deadlock: you have an update and a select on different rows in the table but the select generates a table scan . After aquring several shared locks SQL Server 2000 decides that an table lock escalation is necessary and voila, you have the deadlock. I wonder if this happens in 2005 also.
That sort of deadlock can definitely happen in SQL 2005 (or 2008). It's common for people to assume that a query won't touch any rows except those that it will end up modifying or selecting, but it is often the case that the indexes on the table don't allow for such an efficient query plan. Index tuning may be necessary to prevent scans or limit the number of locks that a query needs to acquire in some other way.
(As an aside, lock escalation never blocks; if SQL can't escalate to a table lock to because someone else holds an incompatible lock, it will continue acquiring locks at the row or page level. But you can still run into a SELECT vs. UPDATE deadlock. In fact, that's the scenario in the deadlock dissected in this post.)
The T1204 message was pretty specific, something like escalating to table lock(sorry, my memory doesn't help me when it comes to generated messages:-). The update was doing the rest by holding a lock. Indexes didn't help because the table scan was generated by something like str1 = UPPER(str2), so the optimizer wouldn't use any indexes. So what do you mean by lock escalation never blocks? Please elaborate.
I mean that a lock escalation attempt will never block. As SQL scans a table, it has thresholds that, when crossed, trigger an attempt to escalate. Escalation means acquiring a TABle lock, then releasing all PAGe/ROW/KEY locks. If someone holds a lock on the table that would block the TAB lock, the escalation attempt is aborted, and the scan continues to acquire locks at the original granularity (row, key, or page). Periodically (every N locks), it will retry the escalation, but the subsequent attempts will also not block.
This is the way the lock manager has handled escalation since SQL 7.
A SELECT can deadlock with an UPDATE without requiring a TAB lock (see the scenario in this blog post, for example). Or the engine can decide at the beginning of the query that a TAB lock would be the best locking strategy, in which case a table lock would be involved even though no escalation occurred (lock escalation is, by definition, a decision to promote a existing set of KEY/ROW/PAG locks to a TAB lock). But you should never see a a blocking incident where a lock escalation attempt is stuck waiting for someone else to release an incompatible TAB lock. If you ever see someone blocked waiting on a TAB lock, it is always because that lock type was decided on before the query began executing.
Now that I got your attention(sorry for the delay between posts): the version based isolation level should get rid of the deadlocks mentioned above. WHat would be the dangers of completely switching to this isolation level?
Yes, snapshot isolation/read versioning is one of the alternate solutions identified above. The main danger is that it allows you to read a stale image of data that is currently being modified by someone else. See the discussion in the Definition section of http://en.wikipedia.org/wiki/Snapshot_isolation for some more info. Whether this risk matters is dependent on the application.
I read somewhere that the snapshot will put pressure on tempdb inducing performance problems. Personally I doubt that, but did you guys have more data about the impact on performance?
Yes, that can happen. If used on databases with high transaction rates, snapshot isolation can also increase the size of tempdb (to store the pre-modification row versions). In many cases, neither of these will be an issue, but both problems can and do happen.
I don't think it's possible to quantify the impact in a simplistic way (e.g. read committed snapshot isolation will slow down your transactions by X% and will cause tempdb to grow by Y%). The affect, if any, depends on far too many variables: current size and % free space in tempdb, speed of the disks that tempdb is on, whether the disks servicing tempdb also have to deal with log writes or other I/O-intensive operations, the user database's transaction rate, amount of log records generated for a typical write transaction, length of time that transactions stay open, proportion of read-only vs. write transactions, likelihood that the rows being modified will need to be read concurrently by someone else, etc etc...
The only way to find out for sure that I know of is to test. Or, if you don't have a realistic QA environment, flip the switch during a non-peak period and say a prayer. In most environments it will work without any fuss. In some you may have to make some config changes (for example, increase tempdb size, or move tempdb to a dedicated disk). In some more extreme cases you may find that you can't safely use snapshot isolation levels, and will need to look at one other other possible deadlock solutions.
I have the following deadlock which was caused through the same spid:
2008-06-18 11:31:35.260 spid16s deadlock-list
2008-06-18 11:31:35.260 spid16s deadlock victim=process3831c18
2008-06-18 11:31:35.260 spid16s process-list
2008-06-18 11:31:35.260 spid16s process id=process3826c58 taskpriority=0 logused=4244 waitresource=PAGE: 7:1:825 waittime=2359 ownerId=2757801102 transactionname=implicit_transaction lasttranstarted=2008-06-18T11:31:30.933 XDES=0x4394e0370 lockMode=U schedulerid=4 kpid=2576 status=suspended spid=86 sbid=0 ecid=0 priority=0 transcount=3 lastbatchstarted=2008-06-18T11:31:32.887 lastbatchcompleted=2008-06-18T11:31:32.887 clientapp=SOCRATE CONTABILITATE hostname=TS1 hostpid=9472 loginname=BotaN isolationlevel=read committed (2) xactid=2757801102 currentdb=7 lockTimeout=4294967295 clientoption1=673185824 clientoption2=128058
2008-06-18 11:31:35.260 spid16s executionStack
2008-06-18 11:31:35.260 spid16s frame procname=rcs.dbo.CNT18_RulajeDocCont line=399 stmtstart=28380 stmtend=29620 sqlhandle=0x030007002a4c5604732423010b9800000100000000000000
2008-06-18 11:31:35.260 spid16s UPDATE rulajevaluta
2008-06-18 11:31:35.260 spid16s SET rulajdebit = COALESCE (r.rulajdebit, 0) + COALESCE (i.rd, 0),
2008-06-18 11:31:35.260 spid16s rulajcredit = COALESCE (r.rulajcredit, 0) + COALESCE (i.rc, 0)
2008-06-18 11:31:35.260 spid16s FROM rulajevaluta r
2008-06-18 11:31:35.260 spid16s JOIN @rulajevaluta i ON i.cont = r.cont
2008-06-18 11:31:35.260 spid16s AND i.conta = r.conta
2008-06-18 11:31:35.260 spid16s AND i.conts = r.conts
2008-06-18 11:31:35.260 spid16s AND i.contb = r.contb
2008-06-18 11:31:35.260 spid16s AND i.contu = r.contu
2008-06-18 11:31:35.260 spid16s AND i.contv = r.contv
2008-06-18 11:31:35.260 spid16s AND r.codsoc = i.codsoc
2008-06-18 11:31:35.260 spid16s AND r.luna = i.luna
2008-06-18 11:31:35.260 spid16s AND r.an = i.an
2008-06-18 11:31:35.260 spid16s AND r.valuta = i.valuta
2008-06-18 11:31:35.260 spid16s AND ISNULL(r.iddimensiune1,0) = ISNULL(i.iddimensiune1,0)
2008-06-18 11:31:35.260 spid16s AND ISNULL(r.iddimensiune2,0) = ISNULL(i.iddimensiune2,0)
2008-06-18 11:31:35.260 spid16s frame procname=rcs.dbo.CNT_ArtContIntroducere line=122 stmtstart=5060 stmtend=5172 sqlhandle=0x03000700f2c0fe04d8855c01829600000100000000000000
2008-06-18 11:31:35.260 spid16s exec @lret = CNT18_RulajeDocCont @nrcontare,@id, 0
2008-06-18 11:31:35.260 spid16s inputbuf
2008-06-18 11:31:35.260 spid16s Proc [Database Id = 7 Object Id = 83804402]
2008-06-18 11:31:35.260 spid16s process id=process3831c18 taskpriority=0 logused=2228 waitresource=PAGE: 7:1:1317504 waittime=2890 ownerId=2757801521 transactionname=user_transaction lasttranstarted=2008-06-18T11:31:31.480 XDES=0x420160370 lockMode=U schedulerid=5 kpid=4736 status=suspended spid=238 sbid=0 ecid=0 priority=0 transcount=2 lastbatchstarted=2008-06-18T11:31:31.387 lastbatchcompleted=2008-06-18T11:31:31.387 clientapp=SOCRATE TREZORERIE hostname=TS3 hostpid=20144 loginname=BalteanuI isolationlevel=read committed (2) xactid=2757801521 currentdb=7 lockTimeout=4294967295 clientoption1=673185824 clientoption2=128056
2008-06-18 11:31:35.260 spid16s frame procname=rcs.dbo.TRS_Transfer_Plati line=453 stmtstart=24698 stmtend=24808 sqlhandle=0x03000700cb55092a74943901c29900000100000000000000
2008-06-18 11:31:35.260 spid16s exec @lret = CNT18_RulajeDocCont @nrcontare,NULL,0,1
2008-06-18 11:31:35.260 spid16s Proc [Database Id = 7 Object Id = 705254859]
2008-06-18 11:31:35.260 spid16s resource-list
2008-06-18 11:31:35.260 spid16s pagelock fileid=1 pageid=1317504 dbid=7 objectname=rcs.dbo.rulajevaluta id=lock42c25bd00 mode=UIX associatedObjectId=58630224609280
2008-06-18 11:31:35.260 spid16s owner-list
2008-06-18 11:31:35.260 spid16s owner id=process3826c58 mode=UIX
2008-06-18 11:31:35.260 spid16s waiter-list
2008-06-18 11:31:35.260 spid16s waiter id=process3831c18 mode=U requestType=wait
2008-06-18 11:31:35.260 spid16s pagelock fileid=1 pageid=825 dbid=7 objectname=rcs.dbo.rulajevaluta id=lock42c349900 mode=U associatedObjectId=58630224609280
2008-06-18 11:31:35.260 spid16s owner id=process3831c18 mode=U
2008-06-18 11:31:35.260 spid16s waiter id=process3826c58 mode=U requestType=wait
What's about it? How to solve it?
thanks in advance,
It's actually not the same spid. One of the process elements is "spid=86", while the other is "spid=238". The "spid16s" on the left of each line is just the identifier of the background system thread that handled the deadlock; you can ignore it.
I recommend that you go through the steps listed in http://blogs.msdn.com/bartd/archive/2006/09/09/Deadlock-Troubleshooting_2C00_-Part-1.aspx. Break down the -T1222 output so that you have a better understanding of what caused the deadlock, then follow the remaining steps in that post to see if there is a simplistic solution. For example, see whether the UPDATE is doing an unnecessary table scan that could be prevented with a better index. Check the BEGIN/COMMIT TRANs in stored procs CNT_ArtContIntroducere, TRS_Transfer_Plati, and CNT18_RulajeDocCont to make sure that you aren't holding a transaction open any longer than is absolutely necessary.
It seems that the same procedure was called from within several stored procedures. It's about CNT18_RulajeDocCont . Should I set a transaction isolation level inside this procedure? In order to be called in a serialization fashion?
Have a nice day,
I've received a couple of questions in email and in comments about deadlocks involving mysterious-sounding
I hate doing this, but I think this is a deadlock trace that hasn't been on here before (its not intra-query parallelism!). I have two simple update queries that are contending on the same index but on different keys, which doesn't sound exotic, but I cannot think of a scenario that would result in this deadlock graph:
process id=process3a12c58 waitresource=KEY: 8:72057594690666496 (0100dc8c8473) waittime=2953 lockMode=X kpid=4072 isolationlevel=read uncommitted (1)
frame procname=adhoc line=1 stmtstart=144
UPDATE CONTROL_LEVEL SET control_amt = @P0, credit_amt = @P1, credit_cnt = @P2, debit_amt =@P3, debit_cnt=@P4, difference_amt=@P5 WHERE (ID = @P6)
(@P0 bigint,@P1 bigint,@P2 int,@P3 bigint,@P4 int,@P5 bigint,@P6 bigint)UPDATE CONTROL_LEVEL SET control_amt = @P0, credit_amt = @P1, credit_cnt = @P2, debit_amt =@P3, debit_cnt=@P4, difference_amt=@P5 WHERE (ID = @P6)
process id=process42b2ef8 waitresource=KEY: 8:72057594690666496 (0100a18ba131) waittime=2968 lockMode=X kpid=2796 isolationlevel=read uncommitted (1)
frame procname=adhoc line=1 stmtstart=24 sqlhandle=0x02000000a00dbb2c60ffa236c31f45683a32d26f213ff8ba
UPDATE CONTROL_LEVEL SET IQA_PENDING_CNT = IQA_PENDING_CNT - 12 WHERE ID = @P0
frame procname=unknown line=1 sqlhandle=0x000000000000000000000000000000000000000000000000
(@P0 bigint)UPDATE CONTROL_LEVEL SET IQA_PENDING_CNT = IQA_PENDING_CNT - 12 WHERE ID = @P0
keylock hobtid=72057594690666496 dbid=8 objectname=TW.dbo.CONTROL_LEVEL indexname=PK__CONTROL_LEVEL__6A9FD071 id=lockeebe0200 mode=X associatedObjectId=72057594690666496
owner id=process3a12c58 mode=X
waiter id=process42b2ef8 mode=X requestType=wait
keylock hobtid=72057594690666496 dbid=8 objectname=TW.dbo.CONTROL_LEVEL indexname=PK__CONTROL_LEVEL__6A9FD071 id=lock3151ee400 mode=X associatedObjectId=72057594690666496
owner id=process42b2ef8 mode=X
waiter id=process3a12c58 mode=X requestType=wait
So as you see, the only own each other, which is a key X lock on a key in the PK clustered index. Why this is wierd to me is that both statements update a single record in the table, using the primary key value as the index-- so they shouldn't be trying to lock each other.
UNLESS... they are traversing the index "in the opposite order" (or via hash join) and lock each other, but I would've though that would result in an IX during traversal until the actual key was found, then an X. In which case, they shouldn't be trying to get X locks on each other. The other thing I was thinking about was what happens in the event of a page split (or does that not affect locking?), but these are all numeric values that don't expand...
Bart- regardless if you are able to take time to reply I am really thankful for your insightful and informative blog posts!
Steve, any chance that these processes are part of a multi-statement transaction that does more than one modification to the CONTROL_LEVEL table within the same transaction?