What is a deadlock, and how do databases detect and resolve them?

A minimal deadlock example

-- Transaction A                      -- Transaction B
BEGIN;                                BEGIN;
UPDATE accounts SET balance = balance - 10
  WHERE id = 1;                       UPDATE accounts SET balance = balance - 10
  -- A now holds a lock on row 1        WHERE id = 2;
                                       -- B now holds a lock on row 2
UPDATE accounts SET balance = balance + 10
  WHERE id = 2;                       UPDATE accounts SET balance = balance + 10
  -- A waits for B's lock on row 2      WHERE id = 1;
                                       -- B waits for A's lock on row 1
                                       -- DEADLOCK: neither can proceed

A is waiting for a lock B holds; B is waiting for a lock A holds. Neither will ever release, without intervention.

Detection

Most engines maintain a wait-for graph — a graph where an edge from transaction X to transaction Y means "X is waiting on a lock held by Y." Periodically (or on each new lock wait), the engine checks this graph for a cycle — a cycle means a deadlock exists. This is generally cheaper and faster than the alternative (a pure timeout, used by some simpler systems), since it detects the problem the moment a cycle forms rather than waiting for an arbitrary timeout to expire.

Resolution

Once a cycle is found, the database picks a victim transaction — typically the one that would be cheapest to roll back (least work done, fewest locks held, or simply the one that most recently joined the cycle, depending on engine) — and forcibly aborts it with a deadlock error, releasing its locks so the other transaction(s) can proceed.

ERROR: deadlock detected
DETAIL: Process 1234 waits for ShareLock on transaction 5678; blocked by process 5678.
        Process 5678 waits for ShareLock on transaction 1234; blocked by process 1234.
HINT: See server log for query details.

The application's responsibility

A deadlock is not a bug in the database — it's an expected, occasional outcome of concurrent access patterns, and the losing transaction's work is fully rolled back (atomicity holds). Applications must catch this specific error and retry the whole transaction from the beginning (not just the last statement), typically with a short randomized backoff to avoid immediately re-colliding with the same transaction.

How to reduce deadlock frequency

• Access rows/tables in a consistent order across all transactions — in the example above, if both transactions always updated account 1 before account 2, no cycle could ever form.
• Keep transactions short — the longer a transaction holds locks, the more opportunity for another transaction to also be waiting on something it holds.
• Use the lowest isolation level that satisfies your correctness needs (higher isolation levels generally take more/broader locks, or in MVCC engines, cause more serialization failures which are a related-but-distinct phenomenon from classic lock deadlocks).
• Consider explicit, application-level lock ordering (e.g., always lock the row with the lower ID first) for code paths known to touch multiple rows that could also be touched in the opposite order elsewhere.