Thread: Deadlocks caused by a foreign key constraint

Hello.

I have a number of deadlock because of the foreign key constraint:

Assume we have 2 tables: A and B. Table A has a field fk referenced to B.id as a foreign key constraint.


-- transaction #1
BEGIN;
...
INSERT INTO A(x, y, fk) VALUES (1, 2, 666);
...
END;


-- transaction #2
BEGIN;
UPDATE B SET z = z + 1 WHERE id = 666;
...
UPDATE B SET z = z + 1 WHERE id = 666;
...
UPDATE B SET z = z + 1 WHERE id = 666;
END;


You see, table A is only inserted, and table B is only updated their field z on its single row.
If we execute a lot of these transactions concurrently using multiple parellel threads, sometimes we have a deadlock:

DETAIL:  Process 6867 waits for ShareLock on transaction 1259392; blocked by process 30444.
    Process 30444 waits for ShareLock on transaction 1259387; blocked by process 6867.
CONTEXT:  SQL statement "SELECT 1 FROM ONLY "public"."B" x WHERE "id" = $1 FOR SHARE OF x"

If I delete the foreign key constraint, all begins to work fine.
Seems Postgres thinks that "UPDATE B SET z = z + 1 WHERE id = 666" query may modify B.id field and touch A.fk, so it holds the shareable lock on it.

The question is: is it possible to KEEP this foreign key constraint, but avoid deadlocks?

On Fri, Aug 10, 2007 at 09:38:36PM +0400, Dmitry Koterov wrote:
> Hello.
>
> I have a number of deadlock because of the foreign key constraint:
>
> Assume we have 2 tables: A and B. Table A has a field fk referenced to
> B.idas a foreign key constraint.
>
>
> -- transaction #1
> BEGIN;
> ...
> INSERT INTO A(x, y, fk) VALUES (1, 2, 666);
> ...
> END;
>
>
> -- transaction #2
> BEGIN;
> UPDATE B SET z = z + 1 WHERE id = 666;
> ...
> UPDATE B SET z = z + 1 WHERE id = 666;
> ...
> UPDATE B SET z = z + 1 WHERE id = 666;
> END;
>
>
> You see, table A is only inserted, and table B is only updated their field z
> on its single row.
> If we execute a lot of these transactions concurrently using multiple
> parellel threads, sometimes we have a deadlock:
>
> DETAIL:  Process 6867 waits for ShareLock on transaction 1259392; blocked by
> process 30444.
>     Process 30444 waits for ShareLock on transaction 1259387; blocked by
> process 6867.
> CONTEXT:  SQL statement "SELECT 1 FROM ONLY "public"."B" x WHERE "id" = $1
> FOR SHARE OF x"
>
> If I delete the foreign key constraint, all begins to work fine.
> Seems Postgres thinks that "UPDATE B SET z = z + 1 WHERE id = 666" query may
> modify B.id field and touch A.fk, so it holds the shareable lock on it.

What version are you running? I'm pretty sure that recent versions check
to see if the key actually changed.

> The question is: is it possible to KEEP this foreign key constraint, but
> avoid deadlocks?

I'm pretty sure that the deadlock is actually being caused by your
application code, likely because you're doing multiple updates within
one transaction, but not being careful about the id order you do them
in.
--
Decibel!, aka Jim Nasby                        decibel@decibel.org
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

No.

I have tested all cases, the code I quoted is complete and minimal. All operations are non-blocking (count incrementation is non-blocking, insertion with a foreign key is non-blocking too), but it still generates a deadlock time to time. Deletion of the foreign key constraint completely solves the problem.

I am using the latest version of Postgres.

You said "I'm pretty sure that recent versions check to see if the key actually changed", but how could it be if Postgres uses a row-level locking, not field-level locking? Seems it cannot check what fields are changed, it locks the whole row.

On Aug 15, 2007, at 1:27 PM, Dmitry Koterov wrote:
> I have tested all cases, the code I quoted is complete and minimal.
> All operations are non-blocking (count incrementation is non-
> blocking, insertion with a foreign key is non-blocking too), but it
> still generates a deadlock time to time. Deletion of the foreign
> key constraint completely solves the problem.

Code? Got a reproducible test case?

> You said "I'm pretty sure that recent versions check to see if the
> key actually changed", but how could it be if Postgres uses a row-
> level locking, not field-level locking? Seems it cannot check what
> fields are changed, it locks the whole row.

You already have the child row that's being updated; both versions of
it. So you don't have to lock anything to see if the FK field has
changed or not.

But... taking a quick look at RI_FKey_check in backend/utils/adt/
ri_triggers.c, I don't see it checking to see if the FK has changed,
which seems odd. I would think that if the FK fields haven't changed
that there's no need to perform the check.
--
Decibel!, aka Jim Nasby                        decibel@decibel.org
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

Decibel! <decibel@decibel.org> writes:
> But... taking a quick look at RI_FKey_check in backend/utils/adt/
> ri_triggers.c, I don't see it checking to see if the FK has changed,
> which seems odd. I would think that if the FK fields haven't changed
> that there's no need to perform the check.

You looked in the wrong place; see AfterTriggerSaveEvent in
commands/trigger.c

            regards, tom lane

On Thu, Aug 16, 2007 at 01:21:43AM -0400, Tom Lane wrote:
> Decibel! <decibel@decibel.org> writes:
> > But... taking a quick look at RI_FKey_check in backend/utils/adt/
> > ri_triggers.c, I don't see it checking to see if the FK has changed,
> > which seems odd. I would think that if the FK fields haven't changed
> > that there's no need to perform the check.
>
> You looked in the wrong place; see AfterTriggerSaveEvent in
> commands/trigger.c

Ahh, I figured it must be in here somewhere...

I guess it's safe to say that RI triggers get a decent amount of special
treatment in the backend compared to normal triggers.
--
Decibel!, aka Jim Nasby                        decibel@decibel.org
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)