Problem with foreign keys (performance and deadlocks)

Sorry for this being so long but I want to describe this as thoroughly as p=
ossible.

I am having two problems with foreign keys.  One is a performance problem a=
nd the other is a deadlock problem but they  are related to the same root c=
ause.  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 name=
s(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=3D'bob1-1' where id=3D1;


In shell B:

begin;
update orders set description=3D'bob2-1' where id=3D2;


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" =3D $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 u=
ntil 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 ro=
w 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 "FO=
R UPDATE OF X" from the foreign key checks  and the concurrency issues disa=
ppeared.  This still make check 1 happen but removed the safety net of chec=
k 2.

The "FOR UPDATE OF X" seems to grab a lock that cannot be shared so the sec=
ond 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?  I=
s a new type  of lock "FOR FKEY OF X" required?

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

DEADLOCK
--------

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

In the simplest case I have multiple "information" tables that are the targ=
ets of foreign keys.  I have 2 "data"  tables that have foreign keys into t=
he information tables.  If I am inserting/updating rows in tables "data1" a=
nd  "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) referen=
ces names(id);
alter table phone_orders add constraint pobaddr foreign key(billid) referen=
ces billaddr(id);
alter table phone_orders add constraint posaddr foreign key(shipid) referen=
ces 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) reference=
s names(id);
alter table web_orders add constraint wobaddr foreign key(billid) reference=
s billaddr(id);
alter table web_orders add constraint wosaddr foreign key(shipid) reference=
s 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=3D'phone order 1-1' where id=3D1;


In shell B:

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

If the PostgreSQL server acquires the foreign key locks in a different orde=
r 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 runn=
ing 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