Deadlock involving foreign key constraint

Question

I would like to understand better a mechanism of locking in postgres.

Let's say that tree can have apples (via foreign key on apple table). It seems that when selecting a tree for update lock is obtained on an apple. However, the operation is not blocked even if someone else already holds a lock on this apple.

Why is it so?

p.s. Please don't suggest to remove "select for update".

Scenario

Transaction 1      Transaction 2
BEGIN              .
update apple;      .
.                  BEGIN
.                  select tree for update;
.                  update apple;
.                  --halts because of the other transaction locking an apple
update apple;      .
-- deadlock        .
                   COMMIT
                   --transaction succeeds

Code

If you want to try it in your postgres - here is a code you can copy/paste.

I have a following db schema

CREATE TABLE trees (
    id       integer primary key
);

create table apples (
    id       integer primary key,
    tree_id  integer references trees(id)
);

and very simple data

insert into trees values(1);
insert into apples values(1,1);

There are two simple transactions. One is updating apples, the second is locking a tree and updating an apple.

BEGIN;
    UPDATE apples SET id = id WHERE id = 1;
    -- run second transaction in paralell
    UPDATE apples SET id = id WHERE id = 1;
COMMIT;

BEGIN;
    SELECT id FROM trees WHERE id = 1 FOR UPDATE;
    UPDATE apples SET id = id WHERE id = 1;
COMMIT;

When I run them - deadlock occurs on the second update of first transaction.

ERROR:  deadlock detected
DETAIL:  Process 81122 waits for ShareLock on transaction 227154; blocked by process 81100.
Process 81100 waits for ShareLock on transaction 227153; blocked by process 81122.
CONTEXT:  SQL statement "SELECT 1 FROM ONLY "public"."trees" x WHERE "id" OPERATOR(pg_catalog.=) $1 FOR SHARE OF x"

Answer 1

Just a wild guess: you're running into an issue related to an implementation detail...

Specifically, your select tree for update statement acquires an exclusive lock on the trees. And the update apples statements obtain an exclusive lock on the relevant apples.

When you run the update on apples, Postgres' foreign-key related per row triggers fire, to ensure that the tree_id exists. I don't recall their precise names off the top of my head, but they're in the catalog and there are bits and pieces in the documentation that reference them explicitly or implicitly, e.g.:

create constraint trigger ... on ... from ...

http://www.postgresql.org/docs/current/static/sql-createtrigger.html

At any rate, these triggers will run something that amounts to the following:

select exists (select 1 from trees where id = 1);

And therein lies your problem: the exclusive access due to the select for update makes it wait for transaction 2 to release the lock on trees in order to finalize its update statement on apples, but transaction 2 is waiting for transaction 1 to complete in order to obtain a lock on apples so as to begin its update statement on apples.

As a result, Postgres bails with a deadlock.