Thread: Foreign key order evaluation
Hi, I am trying to deal with a deadlock situation caused by foreign key references on insert and I was wondering if anyoneknows what order the foreign keys are locked (or evaluated) in for a particular table? Deferring the locks is unfortunatelynot a good option for me... Thanks, Shawn
On Mon, Sep 27, 2004 at 03:19:47PM -0400, Shawn Chisholm wrote: > > Hi, I am trying to deal with a deadlock situation caused by foreign > key references on insert and I was wondering if anyone knows what > order the foreign keys are locked (or evaluated) in for a particular > table? Deferring the locks is unfortunately not a good option for me... What do you mean by "what order the foreign keys are locked"? Can you give us an example of what you're doing and what problem you're trying to solve? As I mentioned in reply to your earlier message, foreign key locking and the potential for deadlock were recently brought up in pgsql-general: http://archives.postgresql.org/pgsql-general/2004-09/msg00405.php http://archives.postgresql.org/pgsql-general/2004-09/msg00442.php My followup to that thread (the second link above) mentions somebody else's suggestion for a shared lock on the foreign key, but as far as I can tell, no such solution has been implemented as of 8.0.0beta3. -- Michael Fuhr http://www.fuhr.org/~mfuhr/
Mike, I'm confused. Where is the lock? Is it on the 1 record in the model table? If so, why is that record locked? Is it possible in Postgresql to update the primary key of a record? --RY mike@fuhr.org (Michael Fuhr) writes: > On Mon, Sep 27, 2004 at 03:19:47PM -0400, Shawn Chisholm wrote: >> >> Hi, I am trying to deal with a deadlock situation caused by foreign >> key references on insert and I was wondering if anyone knows what >> order the foreign keys are locked (or evaluated) in for a particular >> table? Deferring the locks is unfortunately not a good option for me... > > What do you mean by "what order the foreign keys are locked"? Can > you give us an example of what you're doing and what problem you're > trying to solve? As I mentioned in reply to your earlier message, > foreign key locking and the potential for deadlock were recently > brought up in pgsql-general: > > http://archives.postgresql.org/pgsql-general/2004-09/msg00405.php > http://archives.postgresql.org/pgsql-general/2004-09/msg00442.php > > My followup to that thread (the second link above) mentions somebody > else's suggestion for a shared lock on the foreign key, but as far > as I can tell, no such solution has been implemented as of 8.0.0beta3. > > -- > Michael Fuhr > http://www.fuhr.org/~mfuhr/ > > ---------------------------(end of broadcast)--------------------------- > TIP 6: Have you searched our list archives? > > http://archives.postgresql.org > -- % Randy Yates % "And all that I can do %% Fuquay-Varina, NC % is say I'm sorry, %%% 919-577-9882 % that's the way it goes..." %%%% <yates@ieee.org> % Getting To The Point', *Balance of Power*, ELO http://home.earthlink.net/~yatescr
Randy Yates <yates@ieee.org> writes: > Mike, > > I'm confused. Where is the lock? Is it on the 1 record in the model table? > If so, why is that record locked? Is it possible in Postgresql to update > the primary key of a record? Let me also ask why this is a problem. It may be a lock situation but it isn't a DEADlock situation. I.e., the second transaction will just have to wait until the first completes, and the first should complete in milliseconds on a reasonable computer. Right? Or am I completely missing the boat? --Randy > > --RY > > mike@fuhr.org (Michael Fuhr) writes: > >> On Mon, Sep 27, 2004 at 03:19:47PM -0400, Shawn Chisholm wrote: >>> >>> Hi, I am trying to deal with a deadlock situation caused by foreign >>> key references on insert and I was wondering if anyone knows what >>> order the foreign keys are locked (or evaluated) in for a particular >>> table? Deferring the locks is unfortunately not a good option for me... >> >> What do you mean by "what order the foreign keys are locked"? Can >> you give us an example of what you're doing and what problem you're >> trying to solve? As I mentioned in reply to your earlier message, >> foreign key locking and the potential for deadlock were recently >> brought up in pgsql-general: >> >> http://archives.postgresql.org/pgsql-general/2004-09/msg00405.php >> http://archives.postgresql.org/pgsql-general/2004-09/msg00442.php >> >> My followup to that thread (the second link above) mentions somebody >> else's suggestion for a shared lock on the foreign key, but as far >> as I can tell, no such solution has been implemented as of 8.0.0beta3. >> >> -- >> Michael Fuhr >> http://www.fuhr.org/~mfuhr/ >> >> ---------------------------(end of broadcast)--------------------------- >> TIP 6: Have you searched our list archives? >> >> http://archives.postgresql.org >> > > -- > % Randy Yates % "And all that I can do > %% Fuquay-Varina, NC % is say I'm sorry, > %%% 919-577-9882 % that's the way it goes..." > %%%% <yates@ieee.org> % Getting To The Point', *Balance of Power*, ELO > http://home.earthlink.net/~yatescr -- % Randy Yates % "Rollin' and riding and slippin' and %% Fuquay-Varina, NC % sliding, it's magic." %%% 919-577-9882 % %%%% <yates@ieee.org> % 'Living' Thing', *A New World Record*, ELO http://home.earthlink.net/~yatescr
On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote: > Randy Yates <yates@ieee.org> writes: > > > > I'm confused. Where is the lock? Is it on the 1 record in the model table? Yes. > > If so, why is that record locked? Is it possible in Postgresql to update > > the primary key of a record? When you insert a row that has a foreign key reference, PostgreSQL does a SELECT FOR UPDATE on the referenced row in the foreign table; the lock prevents other transactions from changing the referenced row before this transaction completes. Unfortunately it also prevents other transactions from acquiring a lock on the same row, so those transactions will block until the transaction holding the lock completes. > Let me also ask why this is a problem. It may be a lock situation but > it isn't a DEADlock situation. I.e., the second transaction will just > have to wait until the first completes, and the first should complete > in milliseconds on a reasonable computer. Right? We don't know how long it will take for the first transaction to complete -- it might be part of a lengthy process, so performance might suffer. Also, there *is* the potential for deadlock. Take the table definitions in this message: http://archives.postgresql.org/pgsql-general/2004-09/msg00405.php You can create a deadlock situation that raises an error, as shown in this message: http://archives.postgresql.org/pgsql-general/2004-09/msg00442.php Here's what's happening: * Transaction 1 acquires a lock on foreign key 1. * Transaction 2 acquires a lock on foreign key 2. * Transaction 1 attempts to acquire a lock on foreign key 2, but that lock is already held by transaction 2 so transaction 1 blocks. * Transaction 2 attempts to acquire a lock on foreign key 1, but that lock is already held by transaction 1, so transaction 2 blocks. Transaction 1 is now waiting for a lock held by transaction 2, and transaction 2 is waiting for a lock held by transaction 1. Deadlock. PostgreSQL recognizes this and raises an exception in one of the transactions. The blocking and potential for deadlock can be avoided by deferring the foreign key constraints, but then foreign key violations won't be detected until the transaction attempts to commit. For some applications this might be a problem, especially if one wants to take advantage of 8.0.0's savepoints (e.g., an application might want to know if a foreign key constraint has been violated so it can roll back only the offending statement). -- Michael Fuhr http://www.fuhr.org/~mfuhr/
Michael Fuhr wrote: > On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote: > >>Randy Yates <yates@ieee.org> writes: >> >>>I'm confused. Where is the lock? Is it on the 1 record in the model table? > > > Yes. > > >>>If so, why is that record locked? Is it possible in Postgresql to update >>>the primary key of a record? > > > When you insert a row that has a foreign key reference, PostgreSQL > does a SELECT FOR UPDATE on the referenced row in the foreign table; > the lock prevents other transactions from changing the referenced > row before this transaction completes. Unfortunately it also > prevents other transactions from acquiring a lock on the same row, > so those transactions will block until the transaction holding the > lock completes. There are some proposal to have another kind of lock in order to avoid the above. I hope soon. Regards Gaetano Mendola
Here is an example, pardon syntax sloppiness:
create table locations
(
id serial,
address varchar,
...
)
-- In the real application there are 5 tables like this
create table a1
(
from int,
to int,
...
FOREIGN KEY (from) references locations(id),
FOREIGN KEY (to) references locations(id)
)
This causes deadlock with two simple inserts
insert into a1(from,to) values (1,2)
insert into a1(from,to) values (2,1)
I called this a scalability problem because clients timeout and retry properly so it has negligible impact with 20
clients,noticeable with 50, and unacceptable with 70.
The solution I am looking at is to duplicate the locations table since I can put appropriate protections to make sure
theystay in sync (it is already a modify restricted table and is rarely updated):
create table locations_1 ( ... )
create table locations_2 ( ... )
then have all "from" foreign keys in tables a1 through a5 reference locations_1 and all "to" foreign keys reference
locations_2. This will work provided that all inserts into tables a1 through a5 do their foreign key locks in
deterministicallythe same order...
I would agree that the real solution is to make the foreign key locks shared so these kinds of hacks arent necessary,
unfortunatelyI have to make do with the present state of things.
Thanks,
Shawn
-----Original Message-----
From: Michael Fuhr [mailto:mike@fuhr.org]
Sent: Monday, September 27, 2004 11:35 PM
To: Shawn Chisholm
Cc: pgsql-general@postgresql.org
Subject: Re: [GENERAL] Foreign key order evaluation
On Mon, Sep 27, 2004 at 03:19:47PM -0400, Shawn Chisholm wrote:
>
> Hi, I am trying to deal with a deadlock situation caused by foreign
> key references on insert and I was wondering if anyone knows what
> order the foreign keys are locked (or evaluated) in for a particular
> table? Deferring the locks is unfortunately not a good option for me...
What do you mean by "what order the foreign keys are locked"? Can
you give us an example of what you're doing and what problem you're
trying to solve? As I mentioned in reply to your earlier message,
foreign key locking and the potential for deadlock were recently
brought up in pgsql-general:
http://archives.postgresql.org/pgsql-general/2004-09/msg00405.php
http://archives.postgresql.org/pgsql-general/2004-09/msg00442.php
My followup to that thread (the second link above) mentions somebody
else's suggestion for a shared lock on the foreign key, but as far
as I can tell, no such solution has been implemented as of 8.0.0beta3.
--
Michael Fuhr
http://www.fuhr.org/~mfuhr/
Michael, Thank you for your responses. Further questions below. Michael Fuhr <mike@fuhr.org> writes: > On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote: >> Randy Yates <yates@ieee.org> writes: >> > >> > I'm confused. Where is the lock? Is it on the 1 record in the model table? > > Yes. > >> > If so, why is that record locked? Is it possible in Postgresql to update >> > the primary key of a record? > > When you insert a row that has a foreign key reference, PostgreSQL > does a SELECT FOR UPDATE on the referenced row in the foreign table; > the lock prevents other transactions from changing the referenced > row before this transaction completes. Unfortunately it also > prevents other transactions from acquiring a lock on the same row, > so those transactions will block until the transaction holding the > lock completes. Well, yeah - sure it does. Given that the locking mechanism's granularity is record-level, it MUST if it is to guarantee referential integrity. I don't see this as a problem with the database unless you want to argue that the locking mechanism should have finer granularity. Given the granularity, the problem must be solved in the application or business rule logic, not the database. >> Let me also ask why this is a problem. It may be a lock situation but >> it isn't a DEADlock situation. I.e., the second transaction will just >> have to wait until the first completes, and the first should complete >> in milliseconds on a reasonable computer. Right? > > We don't know how long it will take for the first transaction to > complete -- it might be part of a lengthy process, so performance > might suffer. Also, there *is* the potential for deadlock. Take > the table definitions in this message: > > http://archives.postgresql.org/pgsql-general/2004-09/msg00405.php > > You can create a deadlock situation that raises an error, as shown > in this message: > > http://archives.postgresql.org/pgsql-general/2004-09/msg00442.php > > Here's what's happening: > > * Transaction 1 acquires a lock on foreign key 1. > * Transaction 2 acquires a lock on foreign key 2. > * Transaction 1 attempts to acquire a lock on foreign key 2, but that > lock is already held by transaction 2 so transaction 1 blocks. > * Transaction 2 attempts to acquire a lock on foreign key 1, but that > lock is already held by transaction 1, so transaction 2 blocks. > > Transaction 1 is now waiting for a lock held by transaction 2, and > transaction 2 is waiting for a lock held by transaction 1. Deadlock. > PostgreSQL recognizes this and raises an exception in one of the > transactions. > > The blocking and potential for deadlock can be avoided by deferring > the foreign key constraints, but then foreign key violations won't > be detected until the transaction attempts to commit. This just defers the problem. Yeah, it may help in some situations, but in either case the application level or business rule logic must decide what to do. In short, I don't see a problem with postgresql. The responsibility is on the developer to handle such cases. -- % Randy Yates % "Watching all the days go by... %% Fuquay-Varina, NC % Who are you and who am I?" %%% 919-577-9882 % 'Mission (A World Record)', %%%% <yates@ieee.org> % *A New World Record*, ELO http://home.earthlink.net/~yatescr
On Tue, 28 Sep 2004, Randy Yates wrote: > Michael Fuhr <mike@fuhr.org> writes: > > > On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote: > >> Randy Yates <yates@ieee.org> writes: > >> > > >> > I'm confused. Where is the lock? Is it on the 1 record in the model table? > > > > Yes. > > > >> > If so, why is that record locked? Is it possible in Postgresql to update > >> > the primary key of a record? > > > > When you insert a row that has a foreign key reference, PostgreSQL > > does a SELECT FOR UPDATE on the referenced row in the foreign table; > > the lock prevents other transactions from changing the referenced > > row before this transaction completes. Unfortunately it also > > prevents other transactions from acquiring a lock on the same row, > > so those transactions will block until the transaction holding the > > lock completes. > > Well, yeah - sure it does. Given that the locking mechanism's > granularity is record-level, it MUST if it is to guarantee referential > integrity. But it doesn't need to prevent other transactions that want to just see if the row is there from continuing (as opposed to ones that want to actually modify that row). We just simply don't have that lock currently.
sszabo@megazone.bigpanda.com (Stephan Szabo) writes: > On Tue, 28 Sep 2004, Randy Yates wrote: > >> Michael Fuhr <mike@fuhr.org> writes: >> >> > On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote: >> >> Randy Yates <yates@ieee.org> writes: >> >> > >> >> > I'm confused. Where is the lock? Is it on the 1 record in the model table? >> > >> > Yes. >> > >> >> > If so, why is that record locked? Is it possible in Postgresql to update >> >> > the primary key of a record? >> > >> > When you insert a row that has a foreign key reference, PostgreSQL >> > does a SELECT FOR UPDATE on the referenced row in the foreign table; >> > the lock prevents other transactions from changing the referenced >> > row before this transaction completes. Unfortunately it also >> > prevents other transactions from acquiring a lock on the same row, >> > so those transactions will block until the transaction holding the >> > lock completes. >> >> Well, yeah - sure it does. Given that the locking mechanism's >> granularity is record-level, it MUST if it is to guarantee referential >> integrity. > > But it doesn't need to prevent other transactions that want to just see if > the row is there from continuing (as opposed to ones that want to actually > modify that row). We just simply don't have that lock currently. I see the light. You mean it would be nice to be able to have a "LOCK-FOR-UPDATE-ONLY" lock as well as a "LOCK-FOR-UPDATE-OR-READ" lock, but all you have now is "LOCK-FOR-UPDATE-OR-READ" and that gets applied even when you don't care if someone else reads the record? -- % Randy Yates % "So now it's getting late, %% Fuquay-Varina, NC % and those who hesitate %%% 919-577-9882 % got no one..." %%%% <yates@ieee.org> % 'Waterfall', *Face The Music*, ELO http://home.earthlink.net/~yatescr
On Tue, Sep 28, 2004 at 10:27:21PM +0000, Randy Yates wrote: > I see the light. You mean it would be nice to be able to have a "LOCK-FOR-UPDATE-ONLY" > lock as well as a "LOCK-FOR-UPDATE-OR-READ" lock, but all you have now is > "LOCK-FOR-UPDATE-OR-READ" and that gets applied even when you don't care if > someone else reads the record? Right. The current implementation acquires an exclusive lock (FOR UPDATE -- what you're referring to as LOCK-FOR-UPDATE-OR-READ); it would be nice to have a lock that could be shared so multiple transactions could acquire it at the same time without blocking. Then all transactions could read the foreign key record, but no transaction could modify it until the other transactions completed and released their locks. -- Michael Fuhr http://www.fuhr.org/~mfuhr/
On Tue, Sep 28, 2004 at 01:35:32PM -0400, Shawn Chisholm wrote: > create table locations > ( > id serial, > address varchar, > ... > ) > > -- In the real application there are 5 tables like this > create table a1 > ( > from int, > to int, > ... > FOREIGN KEY (from) references locations(id), > FOREIGN KEY (to) references locations(id) > ) > > This causes deadlock with two simple inserts > > insert into a1(from,to) values (1,2) > insert into a1(from,to) values (2,1) If these two inserts occur in different transactions then the second transaction will block. This is different than a deadlock, which is when two transactions are each waiting for a lock that the other holds, in which case PostgreSQL will raise an error. That situation is possible but isn't shown here; see some of the other messages in this thread for an example. > I called this a scalability problem because clients timeout and > retry properly so it has negligible impact with 20 clients, noticeable > with 50, and unacceptable with 70. Agreed. > The solution I am looking at is to duplicate the locations table > since I can put appropriate protections to make sure they stay in > sync (it is already a modify restricted table and is rarely updated): > > create table locations_1 ( ... ) > create table locations_2 ( ... ) > > then have all "from" foreign keys in tables a1 through a5 reference > locations_1 and all "to" foreign keys reference locations_2. This > will work provided that all inserts into tables a1 through a5 do > their foreign key locks in deterministically the same order... You'll still get blocking if more than one transaction refers to the same foreign key. Perhaps less than with your current implementation, but it could still happen. I'm not sure the kludgy workaround would be worth whatever small gain you realized (if any). > I would agree that the real solution is to make the foreign key > locks shared so these kinds of hacks arent necessary, unfortunately > I have to make do with the present state of things. Your hack might not be as effective as you'd like -- have you done any tests with it? Until a shared lock is implemented, you might be stuck with the way things are. -- Michael Fuhr http://www.fuhr.org/~mfuhr/