A relational engine can resolve stuck lock waits either by periodically searching a wait-for graph for cycles or by aborting any transaction that has waited longer than a configured lock-wait timeout. Compare the two approaches, and explain what a deadlock detector considers when choosing which transaction to abort.

## Two ways out of a stuck wait When a transaction blocks on a lock, the engine has to decide how long that is acceptable and how to tell a temporary wait from a permanent one. There are two mechanisms in practice. ### Wait-for-graph detection The lock manager already knows, for every blocked transaction, which transaction holds the lock it wants. That is exactly the data needed for a **wait-for graph**: nodes are active transactions, and an edge T1 → T2 means T1 is blocked on a lock T2 holds. A cycle in this graph is a deadlock, definitionally — no waiter in the ring can be satisfied without another releasing first, and none will release before finishing. Engines rarely run the search on every single wait, because most waits resolve in microseconds and a graph traversal per wait would be pure overhead at high concurrency. The common design is to start the check only after a transaction has waited past a small threshold, or to sweep the graph on a short timer. Either way the algorithm is a cycle search over a graph whose size is bounded by the number of *blocked* transactions, not all transactions. The strengths are precision and latency. Only a member of an actual cycle is aborted, so transactions that are merely waiting behind a slow but healthy holder are left alone. And resolution happens within the detection interval — typically well under a second — rather than after a timeout tuned for the worst legitimate wait. The weaknesses are cost and reach. Maintaining and traversing the graph consumes CPU and requires synchronisation on lock-manager structures, which matters when thousands of sessions are blocked. More importantly, the graph only covers waits the engine knows about. A transaction blocked on something outside the lock manager — an application-level mutex, a remote call, a lock held in another database node — is invisible, and no local detector will ever see that cycle. ### Lock-wait timeouts The alternative is to give up on diagnosis: any transaction that waits longer than a configured interval is aborted. This is trivial to implement, costs nothing while nothing is blocked, and works uniformly for every kind of wait, including the ones the graph cannot see. The price is bluntness. A timeout cannot distinguish "you are in a cycle and will wait forever" from "the holder is doing a slow but perfectly normal update", so it aborts innocent waiters whenever a lock is held longer than the threshold. And when there *is* a real deadlock, the participants sit idle for the entire timeout before anything happens — with a 50-second timeout, a deadlock costs 50 seconds of latency and a held connection. Tuning is a genuine dilemma: low values abort healthy work under load spikes, high values make deadlocks catastrophic for latency. ### How real systems combine them Most production engines run a detector for local deadlocks *and* keep a lock-wait timeout as a backstop. The detector handles the common case precisely and quickly; the timeout catches waits the detector structurally cannot resolve — cross-node waits in a distributed setup, waits on resources outside the lock manager, and any pathological case where the detector is disabled or falls behind. In distributed systems that lack a global wait-for graph, timeouts are often the *only* available mechanism, which is why distributed deadlocks are typically resolved by timeout and retry. ## Choosing the victim Once a cycle is found, one member must be aborted. The goal is to break the cycle at the lowest total cost, so engines weigh some combination of: - **Work already done** — rows modified, undo or log records generated. Aborting the transaction with the least to undo is both cheaper to roll back and cheaper to redo. - **Locks held** — a transaction holding many locks may be closer to completion and unblocking more waiters. - **Age** — very old transactions are sometimes protected to avoid starvation, where the same transaction is repeatedly chosen and never finishes. - **Explicit priority** — some engines let an operator or session mark work as more or less expendable. Two consequences follow for application design. First, victim choice is **not** under application control and not predictable, so every transaction that takes locks needs the same deadlock-retry handling — you cannot assume the batch job always loses and the interactive request always wins. Second, a transaction that does very little work is a *likely* victim, so a small, frequently-run statement colliding with a large batch may be aborted repeatedly, which is a starvation pattern worth watching for in metrics. ## What to look at operationally When deadlocks appear, the engine's deadlock report is the primary artifact: it names the transactions in the cycle, the locks each held and wanted, and the statements involved. That is what identifies the conflicting access orders. Timeout-driven aborts, by contrast, tell you almost nothing about *why* — which is another reason to prefer a detector and keep the timeout as a safety net rather than the mechanism.