How can I avoid this three-way deadlock in Postgres?

This might be how the deadlock is happening. Each table has a foreign key on user_id to the user table. When you insert into a table that has a foreign key constraint, postgres needs to lock the row of the referenced table to ensure that it's not deleted while you insert the row that refers to it (and violate the FK contraints on commit). This should be a shared lock now.

It looks like all the insert/updates for tables that refer to user also update the user seq on the user table after the insert on the primary table. These updates require an exclusive lock and get blocked by any shared locks that are not part of the current transaction. If two happen concurrently, they deadlock.

For example, two transaction inserting into media_size and source concurrently might deadlock w/ something like this:

T1                                   T2-----------------------------------------------------------------------1. Insert media size1a. Excl Lock media size row1b. Shared Lock on user row (FK)                                     2. Insert Source                                     2a. Excl Lock source row                                     2b. Shared lock on user row (FK)3. Update user seq3a. Excl Lock on user row (BLOCKS on 2b)                                     4. Update user seq                                     4a. Excl Lock on user row (Blocks on 1b)5. Deadlock

I think switching the update user seq step to be first makes sense as it would force T1 and T2 to block before trying to acquire a shared lock (which it wouldn't need since it has an exclused lock already).

Assuming the default transaction isolation level Read Committed.

The UPDATE statement always locks updated rows. Concurrent transactions trying to update the same row cannot proceed until the first transaction is rolled back or committed.

The RETURNING clause is orthogonal to the problem.

The deadlock would have happened without Process 5671 just as well. That's just another transaction queuing for the same row, that came in between. Process 5670 and Process 5652 are deadlocking, really, most probably due to other commands in the same transaction. A less likely candidate would be triggers on the table.

Try to break transactions into smaller pieces that update tables and rows of same tables in the same, straight order. Then they cannot interlock.

Foreign keys

Since you mention foreign keys in a later comment: those can play their part in a deadlock, too. Postgres 9.3 introduced new locking levels to address that:

FOR KEY SHARE and FOR NO KEY UPDATE

Details in this blog post by Michael Paquier.

Which should render FK constaints less of a problem. Still not ruled out, though.

Latest point release

There have been a number of small fixes to locking mechanisms since version 9.3.0. Upgrade to the latest point release, it might help.

View current locks

In reply to your comment:You can find (most) currently held locks in the system catalog view pg_locks. Be sure to read the manual and possibly more before drawing conclusions.