Can two concurrent but identical DELETE statements cause a deadlock?

Question

Assume some_table has two rows, with primary key 1 and 2. The following sequence of statements can cause a deadlock:

session 1: begin;
session 2: begin;
session 1: DELETE FROM my_table WHERE my_key = 1;
session 2: DELETE FROM my_table WHERE my_key = 2;
session 1: DELETE FROM my_table WHERE my_key = 2;
session 2: DELETE FROM my_table WHERE my_key = 1;

The deadlock would not have occurred if both sessions deleted in the same order.

Now, coming to my question, what happens if the DELETE statement touches multiple rows? For example:

session 1: begin;
session 2: begin;
session 1: DELETE FROM my_table;
session 2: DELETE FROM my_table;

Is it possible that two concurrent but identical DELETE statements will delete rows in a different order? Is it possible to enforce the deletion order to avoid a deadlock?

I could not find this information in the documentation, so I would say that deletion order is not guaranteed (although it might be indirectly as an implementation detail). I wanted to double check here.

Mcclean

This will cause a deadlock because you aren't committing either transaction. – Staphylococcus

@Staphylococcus AFAIK a possible deadlock would occur during the DELETE statement (that is, as early as possible). It should not be delayed until the COMMIT statement, which is indeed absent here. My question is not about a trivial deadlock due to the absence of a COMMIT statement. – Mcclean

A 'transaction' does cause 'serialization' of access. It guarantees that all of the processing will complete successfully or it will fail. It will also block waiting for a resource in use inside your transactions that access the same resources. The first thing you do is get and lock the resources you need to complete the current step of the transaction. In your case, lock all the rows you want (select for update) or lock the table, accesses the rows, and release it. Seriously, the easiest way is to access resources in the same order in each transaction to prevent 'deadlocks'. – Homosporous

@RyanVincent That's actually my question. A SELECT FOR UPDATE prior to the DELETE would be unnecessary if the rows are always deleted in the same order or there if there was a way to enforce deletion order. If not, a SELECT ... ORDER BY ... FOR UPDATE (SKIP LOCKED) could be useful indeed. – Mcclean

Regarding FOR UPDATE, I am not sure if that works as we would expect. See #51972702 – Mcclean

Answer 1

Yes, this could lead to a deadlock, because the order of rows in a table is not fixed.

Any UPDATE may change the order of rows returned by a sequential table scan, and if synchronize_seqscans is at its default value on, the order may change even if the table doesn't if several sequential scans are executed concurrently (like in your case).

You should first run a SELECT ... FOR UPDATE with an ORDER BY clause to reduce the risk of a deadlock, but even then you cannot be absolutely certain, unless you sort by a column that will not get updated concurrently (like the primary key).

Dekko

Thank you, this is what I expected. Regarding adding an ORDER BY, did you mean something like this: DELETE FROM my_table WHERE my_key IN (SELECT my_key FROM my_table ORDER MY my_key)? Does the DELETE honor the order of the subquery? – Mcclean

I didn't think hard enough; I edited the answer. A prior SELECT ... FOR UPDATE should do the trick. – Dekko

Great! This was also my thought, that's why I created #51972702. – Mcclean

Summary: DELETE FROM my_table WHERE my_key IN (SELECT my_key FROM my_table ORDER BY my_key FOR UPDATE (SKIP LOCKED/NOWAIT) should give a deterministic deletion order. One can add SKIP LOCKED or NOWAIT if needed. – Mcclean

That should work, except that NOWAIT will cause an error. – Dekko