Why does this combination of foreign + primary key produce a Postgres deadlock?

Question

Start with these two tables and this an initial record for c:

create table c
(
    id   serial primary key,
    name varchar not null
);

create table e
(
    id   varchar                  not null,
    c_id bigint references c (id) not null,
    name varchar                  not null,
    primary key (id, c_id)
);

insert into c (name) values ('deadlock test');

Thread 1:

begin;
select * from c where id = 1 for update;
insert into e (id, c_id, name) VALUES ('bar', 1, 'second') on conflict do nothing ;
commit;

Thread 2:

begin;
insert into e (id, c_id, name) VALUES ('bar', 1, 'first') on conflict do nothing ;
commit;

Execution order is:

Thread 1: begin
Thread 2: begin
Thread 1: lock c
Thread 2: insert e
Thread 1: insert e <-- deadlock

Why does this happen?

Adding a lock to c on Thread 2 of course avoids the deadlock, but it's not clear to me why. Also interesting is that if the row in e exists before Thread 1 or 2 run, then no deadlock happens.

I suspect there are at least two things going on:

The primary key creates a unique constraint that causes some sort of locking on e that I don't understand, even with the ON CONFLICT DO NOTHING.
The foreign key on c_id results in some sort of trigger causing a lock on c when a new record is inserted (or when c_id is updated, I presume).

Thanks!

Laurenz Albe Laurenz Albe · Accepted Answer · 2020-04-11T17:52:18

To maintain integrity, every insert on e will lock the referenced row in c with a KEY SHARE lock. This keeps any concurrent transaction from deleting the row in c or modifying the primary key.

Such a KEY SHARE lock conflicts with the UPDATE lock session 1 took explicitly (see the documentation), so the INSERT of session 2 blocks - but it already inserted (and locked) an index tuple in the primary key index of e.

Now session 1 wants to insert a row with the same primary key that session 2 inserted, so it will block on the lock just taken by session 2, and the deadlock is perfect.

You probably wonder why ON CONFLICT DO NOTHING doesn't change the behavior. But PostgreSQL doesn't get there, because to know if there is a conflict, session 1 will have to wait until it knows if session 2 commits or rolls back. So the deadlock happens before we know if there will be a conflict or not.

Why does this combination of foreign + primary key produce a Postgres deadlock?

1 Answers