Thread

1. Deadlocks caused by referential integrity checks

   Greg Stark <gsstark@mit.edu> — 2004-08-24T22:29:26Z

   There's another poster complaining about referential integrity checks causing
   deadlocks. Unfortunately I've deleted the message so this response (and the
   archives aren't responding) isn't going to show up on the right thread.
   
   The reason the deadlock is happening is because of a known deficiency in
   Postgres that postgres has to take an exclusive lock on the records to ensure
   they aren't deleted before your insert/update commits. Unfortunately this
   isn't likely to be fixed soon, certainly not in 8.0.
   
   However I'm a bit surprised it causes deadlocks. It seems like you should be
   able to avoid deadlocks by making sure all the referential integrity checks
   are performed in a consistent order.
   
   At least some versions of postgres ensure that constraint triggers will be
   executed in alphabetical order. This means if all your foreign key constraints
   are named in a consistent order the row locks should be taken in a consistent
   order. If that's true then deadlocks shouldn't happen.
   
   So you would have to take a schema dump, grep out all the foriegn key
   constraints, sort them and uniquefy them, decide on an order, and then go
   through every table renaming them to enforce that order.
   
   That could be a lot of work so hopefully someone more knowledgeable will be
   able to confirm that this should work (and which versions it would work in)
   before you go about trying it. I'm sure other people would like to hear if
   it's successful since it's a pretty frequently asked question.
   
   -- 
   greg
   
   
   

2. Re: Deadlocks caused by referential integrity checks

   Tom Lane <tgl@sss.pgh.pa.us> — 2004-08-24T22:47:58Z

   Greg Stark <gsstark@mit.edu> writes:
   > At least some versions of postgres ensure that constraint triggers will be
   > executed in alphabetical order.
   
   Only within a single event, though, so I don't think fooling with the
   trigger names will do anything to resolve the sorts of problems people
   are dealing with.
   
   The most promising quick-fix I've heard suggested is to mark all the FK
   constraints as deferred until end of transaction.  That would reduce the
   time window in which the locks are held to a short interval and thus
   make deadlocks less likely (not impossible, certainly, but less likely).
   
   			regards, tom lane
   
   

3. Re: Deadlocks caused by referential integrity checks

   Stephan Szabo <sszabo@megazone.bigpanda.com> — 2004-08-24T22:51:13Z

   On Tue, 24 Aug 2004, Greg Stark wrote:
   
   >
   > There's another poster complaining about referential integrity checks causing
   > deadlocks. Unfortunately I've deleted the message so this response (and the
   > archives aren't responding) isn't going to show up on the right thread.
   >
   > The reason the deadlock is happening is because of a known deficiency in
   > Postgres that postgres has to take an exclusive lock on the records to ensure
   > they aren't deleted before your insert/update commits. Unfortunately this
   > isn't likely to be fixed soon, certainly not in 8.0.
   >
   > However I'm a bit surprised it causes deadlocks. It seems like you should be
   > able to avoid deadlocks by making sure all the referential integrity checks
   > are performed in a consistent order.
   
   The general issue is when the actions causing the checks aren't in a
   consistent order, or worse in cases where there can't be a consistent
   order.
   
   If transaction 1 inserts a child row that references row A, then
   transaction 2 does a child row that references row B and they both then go
   to do child rows that reference the other, in the current implementation,
   there's no way to change the order to make that work (although deferring
   the constraint often lowers the probability sufficiently).
   
   

4. Re: Deadlocks caused by referential integrity checks

   Carlos Moreno <moreno@mochima.com> — 2004-08-25T04:14:56Z

   Greg Stark wrote:
   
   > [...] 
   > However I'm a bit surprised it causes deadlocks. It seems like you should be
   > able to avoid deadlocks by making sure all the referential integrity checks
   > are performed in a consistent order.
   > 
   > At least some versions of postgres ensure that constraint triggers will be
   > executed in alphabetical order. This means if all your foreign key constraints
   > are named in a consistent order the row locks should be taken in a consistent
   > order. If that's true then deadlocks shouldn't happen.
   > 
   > So you would have to take a schema dump, grep out all the foriegn key
   > constraints, sort them and uniquefy them, decide on an order, and then go
   > through every table renaming them to enforce that order.
   > 
   > That could be a lot of work so hopefully someone more knowledgeable will be
   > able to confirm that this should work (and which versions it would work in)
   > before you go about trying it. I'm sure other people would like to hear if
   > it's successful since it's a pretty frequently asked question.
   
   I'm not sure this can work.  In the example I put, the
   locks occur as SQL statements are being executed; those
   are asynchrnous and with timing beyond the server's
   control (we have a client/server system with multiple
   concurrent client requests).  That would mean (I think),
   that the names of the constraints play no role in the
   order in which the locks are set.  It would work the
   way you describe it if there are multiple referential
   integrity checks in the same statement.  But I'm not
   sure if that can cause a deadlock at all -- I mean,
   aren't *single* SQL's atomic in postgres? (i.e., aren't
   they fully serialized such that no two statements can
   be concurrent?)
   
   
   What is suggested in the documentation is to follow the
   standard practice in multithreaded programing to avoid
   deadlocks when multiple resources have to be locked:
   ensure that the SQL's are executed maintaining a given
   order in the foreign-key values (e.g., always ascending).
   This way, it is impossible that one transaction locks
   something that another transaction has not locked yet
   if that other transaction has already locked something
   (they both go in ascending order, and that's what
   guarantees that it is impossible for the deadlock
   condition to happen).
   
   Now, the thing is that this is always feasable if there
   is only one foreign key.  If there are two foreign-keys
   that are not correlated, and in some other situations,
   it may not be possible to sort the statements guaranteeing
   a particular order for all foreign-keys.
   
   Fortunately (for me), in my case a preliminary analysis
   tells me that this is not the case -- the transactions
   that are causing deadlocks have a single foreign-key
   constraint, so it looks like this solution can work.
   
   Thanks,
   
   Carlos
   --
   
   

5. Re: Deadlocks caused by referential integrity checks

   Bruce Momjian <pgman@candle.pha.pa.us> — 2004-08-26T03:36:43Z

   Tom Lane wrote:
   > Greg Stark <gsstark@mit.edu> writes:
   > > At least some versions of postgres ensure that constraint triggers will be
   > > executed in alphabetical order.
   > 
   > Only within a single event, though, so I don't think fooling with the
   > trigger names will do anything to resolve the sorts of problems people
   > are dealing with.
   > 
   > The most promising quick-fix I've heard suggested is to mark all the FK
   > constraints as deferred until end of transaction.  That would reduce the
   > time window in which the locks are held to a short interval and thus
   > make deadlocks less likely (not impossible, certainly, but less likely).
   
   We would probably have to allow the deferred trigger queue to spill to
   disk if we do that, of course.
   
   -- 
     Bruce Momjian                        |  http://candle.pha.pa.us
     pgman@candle.pha.pa.us               |  (610) 359-1001
     +  If your life is a hard drive,     |  13 Roberts Road
     +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073
   
   

6. Re: Deadlocks caused by referential integrity checks

   Vivek Khera <khera@kcilink.com> — 2004-08-27T19:58:18Z

   >>>>> "SS" == Stephan Szabo <sszabo@megazone.bigpanda.com> writes:
   
   SS> If transaction 1 inserts a child row that references row A, then
   SS> transaction 2 does a child row that references row B and they both then go
   SS> to do child rows that reference the other, in the current implementation,
   SS> there's no way to change the order to make that work (although deferring
   SS> the constraint often lowers the probability sufficiently).
   
   consider three tables: users, messages, actions.
   
   primary key of users is users_id.
   
   messages referes to users_id as FK.
   actions refers to users_id as FK.
   
   Now, we track sent messages by doing a select on users inserting the ID
   numbers into messages, along with a message ID.  This select can have
   thousands of rows.
   
   the actions track things that those users do.  those actions are
   inserted in unpredictable order.
   
   If an action happens by a user who is currently the target of a new
   message, both inserts will try to lock that row for the FK check.
   Since the order of actions is unpredictable, you're hosed.  Deadlock
   occurs and you spit and curse. :-(
   
   If PG had a way for me to tell it the action logger transaction was
   "less important" and should be the one killed, I'd live with that,
   since the other transaction is usually more expensive.
   
   
   
   -- 
   =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
   Vivek Khera, Ph.D.                Khera Communications, Inc.
   Internet: khera@kciLink.com       Rockville, MD  +1-301-869-4449 x806
   AIM: vivekkhera Y!: vivek_khera   http://www.khera.org/~vivek/
   
   

7. Re: Deadlocks caused by referential integrity checks

   Joshua D. Drake <jd@commandprompt.com> — 2004-08-27T21:16:46Z

   > 
   > If PG had a way for me to tell it the action logger transaction was
   > "less important" and should be the one killed, I'd live with that,
   > since the other transaction is usually more expensive.
   > 
   
   Hello set the check deferrable.
   
   
   > 
   > 
   
   
   -- 
   Command Prompt, Inc., home of Mammoth PostgreSQL - S/ODBC and S/JDBC
   Postgresql support, programming shared hosting and dedicated hosting.
   +1-503-667-4564 - jd@commandprompt.com - http://www.commandprompt.com
   Mammoth PostgreSQL Replicator. Integrated Replication for PostgreSQL
   

8. Re: Deadlocks caused by referential integrity checks

   Vivek Khera <khera@kcilink.com> — 2004-08-30T13:58:05Z

   On Aug 27, 2004, at 5:16 PM, Joshua D. Drake wrote:
   
   >
   >> If PG had a way for me to tell it the action logger transaction was
   >> "less important" and should be the one killed, I'd live with that,
   >> since the other transaction is usually more expensive.
   >
   > Hello set the check deferrable.
   
   Thanks... On which transaction would I set that?  The short one or the 
   long one?  Or both?
   
   And how do you specify that a FK check is deferrable?  Do I need to 
   drop and recreate the FK with the deferrable attribute?