Postgresql -> deadlock from simple update. I can't get the cause

Question

Here is table ( simplified ):

                                       Table "public.link"
    Column     |            Type             |                     Modifiers                     
---------------+-----------------------------+---------------------------------------------------
 id            | integer                     | not null default nextval('link_id_seq'::regclass)
 page_id       | integer                     | 
 placed_at     | timestamp without time zone | default now()
Indexes:
    "link_pkey" PRIMARY KEY, btree (id)
    "link_page_id_index" btree (page_id)
Foreign-key constraints:
    "link_page_id_foreign_key" FOREIGN KEY (page_id) REFERENCES page(id) ON UPDATE RESTRICT ON DELETE RESTRICT

And here is query ( simplified ):

UPDATE link SET page_id = ?, placed_at = now() 
WHERE id IN ( SELECT id FROM link ... ) AND page_id IS NOT NULL

Deadlock message:

ERROR: deadlock detected
  Detail: Process 5822 waits for ShareLock on transaction 19705; blocked by process 5821.
Process 5821 waits for ShareLock on transaction 19706; blocked by process 5822.
  Hint: See server log for query details.

How can that query, executed in parallel by several processes, lead to deadlock ?
Thanks!

Answer 1

Session A tries to update ids 10, 2, 30, 4 and session B tries with 40, 30, 20, 10

They both try to lock their respective rows ready for update and A gets 10 and is waiting for 30 while B gets 30 and is waiting for 10. Deadlock.

Your fundamental issue is that you are trying to update (some of) the same ids in concurrent transactions.

Without knowing your database structure and precisely what you're trying to do, it's difficult to suggest the best solution. Typically, you would either make sure different backends don't update the same rows, or reduce timeouts and just retry after a random pause.