Postgres deadlock in INSERT VALUES concurrent with ON DELETE CASCADE I create tables like this:

CREATE TABLE tgroups (
    group_id text PRIMARY KEY,
    vacancy_id text
);
CREATE INDEX tgroups_vacancy_id_idx ON tgroups (vacancy_id);

CREATE TABLE tscores (
    application_id text NOT NULL,
    group_id text NOT NULL,
    CONSTRAINT tscores_pkey PRIMARY KEY (application_id, group_id),
    CONSTRAINT tscores_group_id_fkey FOREIGN KEY (group_id) REFERENCES tgroups(group_id) ON DELETE CASCADE
);
CREATE INDEX tscores_group_id_idx ON tscores(group_id);


I then have two processes executing SQL transactions in very rapid succession. Both have the standard READ COMMITTED isolation level. The first process is running this, except the values in the INSERT...VALUES are in a random order (I've done it in Python):

BEGIN;
    DELETE FROM tgroups WHERE vacancy_id = 'vacancy1';

    INSERT INTO tgroups (group_id, vacancy_id) VALUES
    ('group1', 'vacancy1'),
    ('group2', 'vacancy1'),
    ...
    ('group10', 'vacancy1');
COMMIT;


The second process runs the following SQL. Again, the values in INSERT...VALUES are in a random order. The variable :application_id is chosen from the set ["application1"..."application10"], which I've done with Python (I guess you could achieve the same in pgsql):

BEGIN;
    DELETE FROM tscores WHERE application_id = :application_id;

    INSERT INTO tscores (application_id, group_id) VALUES
    (:application_id, 'group1'),
    (:application_id, 'group2'),
    ...
    (:application_id, 'group10');
COMMIT;


This sometimes deadlocks:

sqlalchemy.exc.OperationalError: (psycopg2.extensions.TransactionRollbackError) deadlock detected
DETAIL:  Process 527 waits for ShareLock on transaction 391860; blocked by process 526.
Process 526 waits for ShareLock on transaction 391861; blocked by process 527.
HINT:  See server log for query details.
CONTEXT:  while deleting tuple (2,218) in relation "tgroups"
 [SQL: "DELETE FROM tgroups WHERE vacancy_id = 'vacancy1';"]


I can only reproduce the deadlock if both of the following are true:


The deletes in tscores from the first transaction are carried out behind the scenes by ON DELETE CASCADE. If I remove the constraint and manually delete the rows in question at the beginning of the transaction there is no deadlock
The values inside the insert statement are in a random order


I was under the impression that both DELETE and INSERT...VALUES were atomic, and that ON DELETE CASCADE happened at the same time as the DELETE it is related to. Therefore I'd have thought that if one transaction was already in process, the blocked transaction would block on DELETE until the other transaction finished, and then continue, and indeed this is what seems to happen if I manually run the two transactions line-by-line in separate psql sessions.

Somehow I clearly misunderstand the way that locks, inserts, foreign keys and cascades interact.

NB I am aware sometimes the INSERT into tscores will sometimes fail because the group that is referenced has just been deleted, but this isn't my problem (though I guess it could be related).
I would not worry about the behavior, just retry the transaction if terminated by the deadlock.

The first transaction tries to delete A and B, and acquires sequentially a lock on them, and the second deletes B and A, with the same approach. Upon locking A and B, none of the two transactions can progress, hence one of them is terminated by a deadlock.