Postgres: record-merge function deadlocks with concurrent writers on linked rows (FK KEY SHARE taken late)

A PL/pgSQL function that merges two rows (locks them FOR UPDATE, deletes their link rows, re-inserts links to a new row, deletes the old rows) deadlocks (40P01) with a concurrent merge of a linked row or a concurrent 'unlink' (delete of one link row). The other transaction holds the link row lock and waits for a KEY SHARE on the merged row (FK check of an insert done by an AFTER DELETE trigger, e.g. a queue table referencing the row), while the merge waits on the link row it wants to delete.

At the very start of the merge, take every lock in one pass ordered by id: FOR UPDATE on the rows being merged and FOR KEY SHARE on every linked row (the FK of re-inserted links and of trigger-written queue rows would take that lock later anyway). Mixed lock modes in one global order need a PL/pgSQL loop (one PERFORM ... FOR UPDATE / FOR KEY SHARE per id), never 'lock all KEY SHARE then upgrade' (upgrades deadlock). Then lock the link rows of the merged rows (SELECT ... ORDER BY pk FOR UPDATE) before writing anything, so an 'unlink' waits for the merge instead of holding the link row. Finally, in the application, retry the whole transaction on 40P01/40001 (2-3 attempts) and turn the last failure into a user message. KEY SHARE does not block ordinary UPDATEs of the linked rows (they take FOR NO KEY UPDATE), so editing a linked row during a merge is not slowed down.

FK checks and trigger-side inserts take KEY SHARE on the referenced row only when they run, i.e. after the link rows have already been locked by a delete; two transactions then wait on each other in opposite orders.