ASE Quiz Question Randomizer
 
Randomly selected quiz question (want a different question? Click here):


June 2005
This is a problem that took me quite some time to figure out a customer site a while ago.

The customer had a trading system with two central tables in a Parent-Child relationship (let's call the tables 'Parent' and 'Child'; they're both row-locked). When a row was inserted into the Child, the values of some of the inserted columns had to be added to the Parent; this was done through an insert trigger on the Child.
Since multiple inserts of Child rows for the same Parent could happen at the same time, deadlocks occurred a bit too frequently. Changing the application was not an option, so a classic trick to force serialization was applied: the insert trigger first locks the Parent row with a dummy update and then performs the actual trigger work. The idea is that a second Child insert for that Parent row will hit the Exclusive-Row lock on the Parent row and be forced to wait until the first transaction completed.
Basically, the trigger code looked like this:
create trigger Child_insert_trigger on Child for insert 
as
begin
-- first, force serialization in case of multiple
-- Child inserts for the same parent
update Parent
set SomeColumn = P.SomeColumn
from Parent P, inserted i
where P.ParentKey = i.ParentKey

-- now do the real trigger work...
...
...
end
Admittedly, this won't win prizes for subtlety, but this method tends to work fine as far as forcing serialization is concerned. Sometimes this kind of (indeed somewhat heavy-handed) approach may be your only option to alleviate terrible deadlock situations.

Now, the problem: amazingly, even with this trigger-serialization code, deadlocks still kept occurring! These deadlocks always involved two sessions executing the Child_insert_trigger trying to lock the same Parent row to force serialization.
This did not seem logical: when looking at the locks taken out by the trigger (by building a waitfor in the last part of the trigger for example), we could clearly see the Parent row being locked exclusively before anything else happened.

So.... the question is: how is it possible that deadlocks still kept occuring despite these serialization statements?

Here are two additional pieces of information.
First, assume no other activity takes place on these Parent and Child tables other than the inserts into Child.
Second, this is an example of the deadlock details:
Deadlock Id 128: Process (Familyid 0, Spid 59, Suid 3) was executing 
a UPDATE command in the trigger 'Child_insert_trigger'.
SQL Text: insert into Child (...)
Deadlock Id 128: Process (Familyid 0, Spid 48, Suid 3) was executing 
a UPDATE command in the trigger 'Child_insert_trigger'.
SQL Text: insert into Child (...)
Deadlock Id 128: Process (Familyid 0, Spid 48) was waiting for a 
'exclusive row' lock on row 8 page 1334285 of the 'Parent' table 
in database 4 but process (Familyid 0, Spid 59) already held a 
'shared row' lock on it.
Deadlock Id 128: Process (Familyid 0, Spid 59) was waiting for a 
'update row' lock on row 8 page 1334285 of the 'Parent' table in
database 4 but process (Familyid 0, Spid 48) already held a 
'update row' lock on it.

Deadlock Id 128: Process (Familyid 0, Spid 59) was chosen as the 
victim. End of deadlock information.


Answer:
The key to solving this problem lies in the types of locks mentioned in the deadlock info details. Since we're inserting a row and updating another row, and both tables are row-locked, exclusive-row and/or update-row locks on those tables would only be logical. However, the deadlock details also show a shared-row lock on Parent. The insert into Child and the update of Parent do not require shared-row locks. So where is this lock coming from?
The answer: there appears to be foreign-key constraint between Child and Parent (i.e. alter table Child add constraint fkey foreign key (ParentKey) references Parent(ParentKey)).
When a row is inserted into Child, an implicit lookup is performed on Parent, which leads to a shared-row lock on the corresponding row in Parent. This shared-row lock is maintained until the end of the insert statement; since the trigger is executed as part of the insert, this means the lock is active during the trigger execution. This can lead to a deadlock when two sessions insert a row for the same Parent row concurrently.

Without the foreign-key constraint, the locks would be as follows, showing that serialization for the trigger will indeed occur:
Session 1Session 2
insert Child: exclusive-row on Child for inserted row 
trigger update: update-row on Parent for updated row 
 insert Child: exclusive-row on Child for inserted row
 trigger update: needs an update-row lock on Parent but is blocked the update-row (or exclusive-row) lock held by session 1
trigger update: the update-row lock on Parent is upgraded to exclusive-row 
...performs other trigger actions.......blocked by session 1...
commit: releases all locks...blocked by session 1...
 exclusive-row lock on Parent for updated row is now granted
 session 2 proceeds


However, with the foreign-key constraint, the additional shared-row lock can spoil this scenario, potentially leading to a deadlock as shown in the question follows:
Session 1Session 2
insert Child: shared-row on Parent for row lookup due to RI contraint, plus exclusive-row on Child for inserted row 
trigger update: update-row on Parent for updated row 
 insert Child: shared-row on Parent for row lookup due to RI contraint, plus exclusive-row on Child for inserted row
trigger update: the update-row lock on Parent is upgraded to exclusive-row, but this is blocked because session 2 now holds a shared-row lock on this row 
 trigger update: needs an update-row lock on Parent but is blocked the update-row lock held by session 1
...session is blocked by session 2......session 2 is blocked by session 1...
A deadlock has occurred -- ASE will abort one of the transactions


Whether a deadlock will indeed occur according to this scenario depends partly on chance, since the timing of each of the above steps by the two sessions matters a lot: if the actions by both sessions overlap just a little bit differently, a deadlock may occur differently, or not at all. In contrast, without the shared-row lock due to the constraint, a deadlock will never occur, no matter how the actions of both sessions are timed.

It may seem a bit odd that an RI constraint can have such an effect on concurrency. The reason is simply that without the constraints, only update locks and exclusive locks are involved, which are mutually exclusive. The shared lock from the constraint however, will read through an update lock -- but an update lock will be blocked by a shared lock. As demonstrated, this can change the concurrency aspects quite a bit.

Note that it is actually quite reasonble to expect a foreign-key constraint to exist in this example: there is obviously a relation between Parent and Child, so it is logical to expect this relation to be guarded by a constraint. With hindsight, the attempt to force serialization by locking the Parent row was not the right approach for this particular problem. If serialization is really essential in this case, it might have been better to drop the foreign-key constraint and guard the relation be means of triggers.

To see the details of the lock acquisition yourself, you can run the statements with traceflag 1217:
create table Child 
(ChildKey int, ParentKey int unique, 
SomeColumn int) 
lock datarows

create table Parent 
(ParentKey int unique, 
SomeColumn int) 
lock datarows

insert Parent values (200, 1)
insert Parent values (201, 2)
go

create trigger Child_insert_trigger on Child for insert 
as
begin
-- first, force serialization in case of multiple
-- Child inserts for the same parent
update Parent
set SomeColumn = P.SomeColumn
from Parent P, inserted i
where P.ParentKey = i.ParentKey

select "this is the trigger"
end
go

dbcc traceon(1217,3604)
go

insert Child values (1000, 200, 2)
go

[you may need to reconnect to ASE at this point since this is 
one of those traceflags that can sometimes get a client 
confused and the connection aborted]

alter table Child add constraint fkey 
foreign key (ParentKey) references Parent(ParentKey)
go

dbcc traceon(1271,3604)
go

insert Child values (1000, 201, 2)
go


How would you rate this ASE quiz question?
Great    OK    Average    Boring     


More ASE quiz questions: 2013 - 2012 - 2011 - 2010 - 2009 - 2008 - 2007 - 2006 - 2005 - 2004 - 2003 - 2002 - 2001
For a randomly selected quiz question, click here.


 
 This document is located at www.sypron.nl/quizrand.html