Sorry for this being so long but I want to describe this as thoroughly as possible.

I am having two problems with foreign keys.  One is a performance problem and the other is a deadlock problem but they  are related to the same root cause.  I am running PostgreSQL 7.3 (the released version).

I have isolated it down to a simple test:

Given the following database:

create table names (
    id integer not null,
    name text not null,
    primary key (id)
);

create table orders (
    id integer not null,
    nameid integer,
    description text,
    primary key (id)
);
alter table orders add constraint oname foreign key(nameid) references names(id);

insert into names values (1,'bob');
insert into names values (2,'fred');
insert into names values (3,'sam');

insert into orders values (1,1,'bob1');
insert into orders values (2,1,'bob2');
insert into orders values (3,1,'bob3');
insert into orders values (4,2,'fred1');
insert into orders values (5,3,'sam1');

To reproduce the bug, start psql on the database in two different shells.

In shell A:

begin;
update orders set description='bob1-1' where id=1;


In shell B:

begin;
update orders set description='bob2-1' where id=2;


The update in shell B will blocuntilll you do a "commit;" or "rollback;" in shell A.  This blocking should not occur.

The problem is that the update in shell A causes a

SELECT 1 FROM ONLY "public"."names" x WHERE "id" = $1 FOR UPDATE OF x

statement to be generated internally as part of the foreign key checking.  For shell A this works fine but when shell B executes this line it blocks until the transaction in shell A does a commit or rollback.

The purpose of this SELECT seems to be two-fold:
 1. To make sure that row in the target table exists.
2. To make sure that the row does not get deleted or that column in that row does not get changed until the commit  happens because other transactions cannot see the changes until the commit happens.

As a test I went into "backend/utils/adt/ri_triggers.c" and removed the "FOR UPDATE OF X" from the foreign key checks  and the concurrency issues disappeared.  This still make check 1 happen but removed the safety net of check 2.

The "FOR UPDATE OF X" seems to grab a lock that cannot be shared so the second foreign key select must wait until the  first one releases.  Is there a weaker lock that can applied to the foreign key check in ri_triggers.c?  Is a new type  of lock "FOR FKEY OF X" required?

This really drags down our system when we get alot of traffic.  It also also causes deadlocks.

DEADLOCK
--------

The example is a very simple case but in my application where I have more tables and multiple foreign keys I run into  deadlocks.

In the simplest case I have multiple "information" tables that are the targets of foreign keys.  I have 2 "data"  tables that have foreign keys into the information tables.  If I am inserting/updating rows in tables "data1" and  "data2".

Here is an example I made up to (hopefully) make this clear:

create table names (
    id integer not null,
    name text not null,
    primary key (id)
);

create table billaddr (
    id integer not null,
    address text not null,
    primary key (id)
);

create table shipaddr (
    id integer not null,
    address text not null,
    primary key (id)
);

create table phone_orders (
    id integer not null,
    nameid integer,
    billid integer,
    shipid integer,
    description text,
    primary key (id)
);
alter table phone_orders add constraint poname  foreign key(nameid) references names(id);
alter table phone_orders add constraint pobaddr foreign key(billid) references billaddr(id);
alter table phone_orders add constraint posaddr foreign key(shipid) references shipaddr(id);

create table web_orders (
    id integer not null,
    nameid integer,
    billid integer,
    shipid integer,
    description text,
    primary key (id)
);
alter table web_orders add constraint woname  foreign key(nameid) references names(id);
alter table web_orders add constraint wobaddr foreign key(billid) references billaddr(id);
alter table web_orders add constraint wosaddr foreign key(shipid) references shipaddr(id);

insert into names values (1,'bob');
insert into names values (2,'fred');
insert into names values (3,'sam');

insert into billaddr values (1,'123 main st');
insert into billaddr values (2,'456 minor ave');

insert into shipaddr values (1,'789 major ct');
insert into shipaddr values (2,'912 losers lane');

insert into phone_orders values (1,1,1,1,'phone order 1');
insert into phone_orders values (2,2,2,2,'phone order 2');

insert into web_orders values (1,1,1,1,'web order 1');
insert into web_orders values (2,2,2,2,'web order 2');


Once again start psql on the database in two different shells.

In shell A:

begin;
update phone_orders set description='phone order 1-1' where id=1;


In shell B:

begin;
update web_orders set description='web order 1-1' where id=1;

If the PostgreSQL server acquires the foreign key locks in a different order on the web-orders and phone_orders tables  then you will get a deadlock.  When I ran this exact case I did not see this but I have seen it when running my  application.  I reorganized by schema to try to get the locks to be acquired in the same order all the time but I  could not get it to work.  Even if I could get this to work it would not solve the performance issue.


I saw a discussion on this from March:

http://archives.postgresql.org/pgsql-hackers/2002-03/msg01156.php

These does not seem to be a resolution to this yet.

Are there any plans to fix this soon?  This is a serious problem for us.

Thanks

Brian Walker








Tue, 10 Dec 2002 10:47:16 -0600
"Brian Walker" <brianw@mcsdallas.com>
Problem with foreign keys (performance and deadlocks)
On Tue, 10 Dec 2002, Brian Walker wrote:

> As a test I went into "backend/utils/adt/ri_triggers.c" and removed
> the "FOR UPDATE OF X" from the foreign key checks and the concurrency
> issues disappeared.  This still make check 1 happen but removed the
> safety net of check 2.

Right, at which point you lose the guarantees of the constraint.

> The "FOR UPDATE OF X" seems to grab a lock that cannot be shared so
> the second foreign key select must wait until the first one releases.
> Is there a weaker lock that can applied to the foreign key check in
> ri_triggers.c?  Is a new type of lock "FOR FKEY OF X" required?

Not in the same way and sort of (it's more involved than a new kind of
lock).

> I saw a discussion on this from March:
>
> http://archives.postgresql.org/pgsql-hackers/2002-03/msg01156.php
>
> These does not seem to be a resolution to this yet.
>
> Are there any plans to fix this soon?  This is a serious problem for us.

There are plans to fix it.  Right now, soon is relative to how much time I
can spend on it.  I think a version of my very early testing patch ended
up on -general (with one bug that was mentioned afterwards that has an
easy fix) that I was asking for information on.  As I say in that message,
it's not a prime time patch since at the last it lets through bad data
(less so than removing the for update from the original patch) and it
really needs better management of its local data and it's really ugly.  I
haven't had any time recently, but I'm hoping to get a new testing patch
out by early January.


Tue, 10 Dec 2002 10:22:36 -0800 (PST)
Stephan Szabo <sszabo@megazone23.bigpanda.com>
Re: Problem with foreign keys (performance and deadlocks)

I posted this message to psql-bugs in December but I have not heard if this has been fixed or not.  This is holding up our development and testing of our product using Linux and PostgreSQL.

Thanks



********** ORIGINAL MESSAGE ***************

Sorry for this being so long but I want to describe this as thoroughly as possible.

I am having two problems with foreign keys.  One is a performance problem and the other is a deadlock problem but they are related to the same root cause.  I am running PostgreSQL 7.3 (the released version).

I have isolated it down to a simple test:

Given the following database:

create table names (
    id integer not null,
    name text not null,
    primary key (id)
);

create table orders (
    id integer not null,
    nameid integer,
    description text,
    primary key (id)
);
alter table orders add constraint oname foreign key(nameid) references names(id);

insert into names values (1,'bob');
insert into names values (2,'fred');
insert into names values (3,'sam');

insert into orders values (1,1,'bob1');
insert into orders values (2,1,'bob2');
insert into orders values (3,1,'bob3');
insert into orders values (4,2,'fred1');
insert into orders values (5,3,'sam1');

To reproduce the bug, start psql on the database in two different shells.

In shell A:

begin;
update orders set description='bob1-1' where id=1;


In shell B:

begin;
update orders set description='bob2-1' where id=2;


The update in shell B will blocuntilll you do a "commit;" or "rollback;" in shell A.  This blocking should not occur.

The problem is that the update in shell A causes a

SELECT 1 FROM ONLY "public"."names" x WHERE "id" = $1 FOR UPDATE OF x

statement to be generated internally as part of the foreign key checking.  For shell A this works fine but when shell B executes this line it blocks until the transaction in shell A does a commit or rollback.

The purpose of this SELECT seems to be two-fold:
 1. To make sure that row in the target table exists.
2. To make sure that the row does not get deleted or that column in that row does not get changed until the commit  happens because other transactions cannot see the changes until the commit happens.

As a test I went into "backend/utils/adt/ri_triggers.c" and removed the "FOR UPDATE OF X" from the foreign key checks  and the concurrency issues disappeared.  This still make check 1 happen but removed the safety net of check 2.

The "FOR UPDATE OF X" seems to grab a lock that cannot be shared so the second foreign key select must wait until the  first one releases.  Is there a weaker lock that can applied to the foreign key check in ri_triggers.c?  Is a new type  of lock "FOR FKEY OF X" required?

This really drags down our system when we get alot of traffic.  It also also causes deadlocks.

DEADLOCK
--------

The example is a very simple case but in my application where I have more tables and multiple foreign keys I run into  deadlocks.

In the simplest case I have multiple "information" tables that are the targets of foreign keys.  I have 2 "data"  tables that have foreign keys into the information tables.  If I am inserting/updating rows in tables "data1" and  "data2".

Here is an example I made up to (hopefully) make this clear:

create table names (
    id integer not null,
    name text not null,
    primary key (id)
);

create table billaddr (
    id integer not null,
    address text not null,
    primary key (id)
);

create table shipaddr (
    id integer not null,
    address text not null,
    primary key (id)
);

create table phone_orders (
    id integer not null,
    nameid integer,
    billid integer,
    shipid integer,
    description text,
    primary key (id)
);
alter table phone_orders add constraint poname  foreign key(nameid) references names(id);
alter table phone_orders add constraint pobaddr foreign key(billid) references billaddr(id);
alter table phone_orders add constraint posaddr foreign key(shipid) references shipaddr(id);

create table web_orders (
    id integer not null,
    nameid integer,
    billid integer,
    shipid integer,
    description text,
    primary key (id)
);
alter table web_orders add constraint woname  foreign key(nameid) references names(id);
alter table web_orders add constraint wobaddr foreign key(billid) references billaddr(id);
alter table web_orders add constraint wosaddr foreign key(shipid) references shipaddr(id);

insert into names values (1,'bob');
insert into names values (2,'fred');
insert into names values (3,'sam');

insert into billaddr values (1,'123 main st');
insert into billaddr values (2,'456 minor ave');

insert into shipaddr values (1,'789 major ct');
insert into shipaddr values (2,'912 losers lane');

insert into phone_orders values (1,1,1,1,'phone order 1');
insert into phone_orders values (2,2,2,2,'phone order 2');

insert into web_orders values (1,1,1,1,'web order 1');
insert into web_orders values (2,2,2,2,'web order 2');


Once again start psql on the database in two different shells.

In shell A:

begin;
update phone_orders set description='phone order 1-1' where id=1;


In shell B:

begin;
update web_orders set description='web order 1-1' where id=1;

If the PostgreSQL server acquires the foreign key locks in a different order on the web-orders and phone_orders tables  then you will get a deadlock.  When I ran this exact case I did not see this but I have seen it when running my  application.  I reorganized by schema to try to get the locks to be acquired in the same order all the time but I  could not get it to work.  Even if I could get this to work it would not solve the performance issue.


I saw a discussion on this from March:

http://archives.postgresql.org/pgsql-hackers/2002-03/msg01156.php

These does not seem to be a resolution to this yet.

Are there any plans to fix this soon?  This is a serious problem for us.

Thanks

Brian Walker




Tue, 04 Mar 2003 13:21:15 -0600
"Brian Walker" <brianw@mcsdallas.com>
Problem with foreign keys (performance and deadlocks)