Problem with foreign keys (performance and deadlocks)

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