Foreign key order evaluation

[Shawn Chisholm]

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...

Thanks,

Shawn

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faqs/FAQ.html

[Michael Fuhr]

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...9/msg00405.php
http://archives.postgresql.org/pgsql...9/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]

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

mi**@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...9/msg00405.php
http://archives.postgresql.org/pgsql...9/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..."
%%%% <ya***@ieee.org> % Getting To The Point', *Balance of Power*, ELO
http://home.earthlink.net/~yatescr

[Randy Yates]

Randy Yates <ya***@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

mi**@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...9/msg00405.php
http://archives.postgresql.org/pgsql...9/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..."
%%%% <ya***@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 %
%%%% <ya***@ieee.org> % 'Living' Thing', *A New World Record*, ELO
http://home.earthlink.net/~yatescr

[Michael Fuhr]

On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote:

Randy Yates <ya***@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...9/msg00405.php

You can create a deadlock situation that raises an error, as shown
in this message:

http://archives.postgresql.org/pgsql...9/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/

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Gaetano Mendola]

Michael Fuhr wrote:

On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote:

Randy Yates <ya***@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

[Randy Yates]

Michael,

Thank you for your responses. Further questions below.

Michael Fuhr <mi**@fuhr.org> writes:

On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote:

Randy Yates <ya***@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...9/msg00405.php

You can create a deadlock situation that raises an error, as shown
in this message:

http://archives.postgresql.org/pgsql...9/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 since the conflict is still POSSIBLE.

In short, I don't see a problem with postgresql. The responsibility
is on the developer to handle such cases.

Or am I still confused?
--
% Randy Yates % "Though you ride on the wheels of tomorrow,
%% Fuquay-Varina, NC % you still wander the fields of your
%%% 919-577-9882 % sorrow."
%%%% <ya***@ieee.org> % '21st Century Man', *Time*, ELO
http://home.earthlink.net/~yatescr

[Randy Yates]

Michael,

Thank you for your responses. Further questions below.

Michael Fuhr <mi**@fuhr.org> writes:

On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote:

Randy Yates <ya***@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...9/msg00405.php

You can create a deadlock situation that raises an error, as shown
in this message:

http://archives.postgresql.org/pgsql...9/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)',
%%%% <ya***@ieee.org> % *A New World Record*, ELO
http://home.earthlink.net/~yatescr
---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Stephan Szabo]

On Tue, 28 Sep 2004, Randy Yates wrote:

Michael Fuhr <mi**@fuhr.org> writes:

On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote:

Randy Yates <ya***@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.

---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if your
joining column's datatypes do not match

[Randy Yates]

ss****@megazone.bigpanda.com (Stephan Szabo) writes:

On Tue, 28 Sep 2004, Randy Yates wrote:

Michael Fuhr <mi**@fuhr.org> writes:

> On Tue, Sep 28, 2004 at 01:30:08PM +0000, Randy Yates wrote:
>> Randy Yates <ya***@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..."
%%%% <ya***@ieee.org> % 'Waterfall', *Face The Music*, ELO
http://home.earthlink.net/~yatescr

[Michael Fuhr]

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/

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster