One missing index, one stalled system, and the road to deadlock

01One harmless DELETE

The ticket said only checkout is slow. Then it said checkout is down. When I looked at the database, an Oracle instance, the cause was a single line a back-office script had run a minute earlier: DELETE FROM orders WHERE id = 42. One row, one primary key, the most innocent statement a database knows. Yet dozens of unrelated sessions were queued behind it, none of them touching order 42, and the queue was growing.

The story is a composite: it is the pattern I first met in the notes of a DBA I once worked with (an Oracle shop), and met again while reading chapter 7 of Kleppmann's Designing Data-Intensive Applications (first edition). The two sources describe the same mechanism from opposite ends. His notes begin with the symptom and end with the cause; the book begins with the theory of locks. When I put them side by side, the sentence that fell out was this: a transaction lock and the lock caused by a missing index are the same mechanism. This post is about that sentence, and about what happens when such locks start to tangle into a ring.

what the DELETE meant to touch

1 row

FK columns Postgres indexes for you

0

phases in two-phase locking

2

SQLSTATE of a Postgres deadlock

40P01

02The warehouse with and without a catalogue

To see why a lock can be far wider than the row you meant, leave the database for a minute and picture a warehouse. A customer has asked you to seal all of their crates. If the warehouse keeps a catalogue, you look up the customer, read off the aisle and shelf, walk straight there and put a padlock on those three crates. The rest of the warehouse keeps working. If there is no catalogue, you have to walk every aisle and read every label to find the customer's crates, and to be sure no crate moves while you are looking, you chain the main gate until you are done. Every porter with a cart waits outside, including the ones who have nothing to do with your customer.

A database index is that catalogue. It does two jobs, and people usually remember only the first: it makes the search fast, and it narrows the set of rows the engine has to visit, and therefore the set it locks. A database must be sure that what it just read is still true when it writes, so it locks what it looked at. The more it looks at, the more it locks.

This is not folklore. In the chapter on transactions, Kleppmann describes index-range locks: because exact predicate locks are expensive, databases approximate them by attaching a lock to a range of an index, and, as I read the passage, if there is no suitable index to hang that range on, the database can fall back to a shared lock on the entire table. InnoDB's documentation says the same thing in its own words: at the default REPEATABLE READ level, a statement that has no usable index and must scan the table ends up locking every row it scanned. The index is the unit of lock granularity.

03The case: orders and order_items

Enough warehouses. Here is the schema behind my story. A parent table of orders and a child table of their line items, linked by a foreign key. The foreign key is declared; the index on it is not. That is the whole bug.

CREATE TABLE orders (
  id          bigint PRIMARY KEY,
  customer_id bigint      NOT NULL,
  status      text        NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now()
);

CREATE TABLE order_items (
  id       bigint PRIMARY KEY,
  order_id bigint NOT NULL REFERENCES orders(id),   -- foreign key declared...
  sku      text   NOT NULL,
  qty      int    NOT NULL
);
-- ...but nothing indexes order_items(order_id). The FK constraint
-- checks integrity; it does not promise a fast way to find children.

-- the fix, one line (CONCURRENTLY avoids blocking writes on Postgres):
CREATE INDEX CONCURRENTLY order_items_order_id_idx ON order_items (order_id);

Now run DELETE FROM orders WHERE id = 42. Before it may remove the parent, the database must prove that no child still points at it. That proof is a query: is there any row in order_items with order_id = 42? With an index on order_id the answer comes from one probe. Without it, the engine has to walk the whole child table to say no, and what it does while walking depends on the engine.

What each engine actually does

This is where precision matters, because the three engines most of us use behave quite differently. The principle (less indexed means more scanned means more locked or longer held) is universal. The symptoms are engine-specific.

In Oracle the picture is the vivid one: with no index on the foreign key, a delete or primary-key update on the parent takes a share lock on the entire child table, and every writer on order_items (every checkout adding a line) waits. That is the "TM contention" in the DBA's notes. In modern Oracle versions the lock is released as soon as the statement ends, which is why it hides in tests: it is short. But under load "short" is a queue, and a queue of checkouts is an outage.

In PostgreSQL there is no escalation to a table lock, so the failure looks different and arrives later: the parent delete runs the child scan inside your transaction, so on a big child table a transaction that should last a millisecond can last seconds, and everything it holds (the parent row, other rows it already updated) is held with it. Which brings us to the real danger: the longer locks are held, the more likely they are to meet in a ring.

04Finding the foreign keys nobody indexed

So the hole is easy to dig. The fix is one line; the hard part is knowing where to apply it, because nothing fails until the table is big and the traffic is real. On PostgreSQL the catalogue can tell you: list every foreign-key constraint and keep the ones for which no index starts with exactly those columns.

-- foreign keys whose columns are not the leading columns of any index
SELECT c.conrelid::regclass  AS child_table,
       c.conname             AS fk_name,
       pg_get_constraintdef(c.oid) AS definition
FROM   pg_constraint c
WHERE  c.contype = 'f'
  AND  NOT EXISTS (
         SELECT 1
         FROM   pg_index i
         WHERE  i.indrelid = c.conrelid
           AND  (string_to_array(i.indkey::text, ' ')::int2[])[1:cardinality(c.conkey)]
                  @> c.conkey
           AND  (string_to_array(i.indkey::text, ' ')::int2[])[1:cardinality(c.conkey)]
                  <@ c.conkey
       )
ORDER  BY 1, 2;

Run it on a database you inherited and be ready to be uncomfortable. A result row is a suspect, not a verdict: a tiny lookup table that is never deleted from does not need the index, and every index you add taxes every write. The ones to fix first are children of tables that see parent deletes or key updates, and children that are large and written to often, exactly like order_items.

05Two-phase locking is not locking twice

Locks pile up; the other half of the story is the rule for when they are let go. I need to confess a misunderstanding here. For a long time I read "two-phase locking" as lock, then lock again, some kind of double-checked padlock. It is nothing like that. The two phases are two stretches of one transaction's life: first a growing phase, in which the transaction only acquires locks as it touches rows, and then a shrinking phase, in which it only releases them and never acquires another.

Why bother with the rule? Because it is what buys serializability from locks: if a transaction never releases a lock before it has taken its last one, no other transaction can sneak into the middle of its reads and writes. The price, as Kleppmann stresses, is concurrency: under 2PL readers block writers and writers block readers, and response times at the high percentiles can become erratic (the tail-latency post is about why that tail hurts). PostgreSQL softens this with MVCC, where plain reads take no row locks, but writers still hold their row locks to the end. Real engines make it stricter still and hold every lock until commit, which is exactly why a slow transaction is an expensive one: it is holding its whole growing phase hostage the entire time.

06Where deadlocks come from

That rule has a side effect that surprised me. I assumed locking exists to prevent trouble, so a correct locking protocol should not be able to jam itself. But two-phase locking does not prevent deadlock, it makes deadlock possible. Hold-and-wait is the very definition of the growing phase: you keep what you have while you ask for more. If transaction 1 holds A and wants B while transaction 2 holds B and wants A, each waits for the other forever.

You can reproduce it in two psql sessions in a minute. Run the statements in the order of the numbers.

-- setup (any session)
INSERT INTO orders (id, customer_id, status) VALUES (1, 7, 'paid'), (2, 8, 'paid');

-- 1) session 1
BEGIN;
UPDATE orders SET status = 'packed' WHERE id = 1;     -- holds row 1

-- 2) session 2
BEGIN;
UPDATE orders SET status = 'packed' WHERE id = 2;     -- holds row 2

-- 3) session 1
UPDATE orders SET status = 'shipped' WHERE id = 2;    -- blocks: row 2 is session 2's

-- 4) session 2 (wait more than 1 s after step 3, i.e. past deadlock_timeout)
UPDATE orders SET status = 'shipped' WHERE id = 1;    -- closes the ring
-- ... about one second of silence, then in session 2:
-- ERROR:  deadlock detected
-- DETAIL:  Process 8412 waits for ShareLock on transaction 9030; blocked by process 8398.
--          Process 8398 waits for ShareLock on transaction 9031; blocked by process 8412.
-- HINT:  See server log for query details.
-- SQLSTATE 40P01. Session 2 is rolled back; session 1's UPDATE from step 3 now completes.
-- (Whichever session's deadlock_timeout expires while the ring exists is the one that aborts.)

The PIDs and transaction ids will differ on your machine; the shape will not. Notice that nobody did anything wrong: each session updated two rows, each update was legal. The only fault is that they touched the same two rows in opposite order. In real code that happens whenever a batch job deletes WHERE id IN (...) in whatever order the planner picks, while an API call touches the same orders in another.

Detecting it: the wait-for graph

The database cannot prevent the ring, but it can see it. It keeps a wait-for graph: a node per transaction, an arrow from T1 to T2 when T1 is waiting for a lock T2 holds. A deadlock is simply a cycle in that graph. Engines run the check either continuously or after a wait has lasted a while (PostgreSQL waits deadlock_timeout, one second by default, before it bothers to look). When it finds a cycle it picks a victim, rolls that transaction back so its locks vanish, and lets the others proceed. Kleppmann describes exactly this: the database detects deadlocks automatically, aborts one transaction, and the application is expected to try it again.

There are two defences, and you want both. The first is design: touch rows in one global order. If every code path locks orders in ascending id (SELECT ... WHERE id IN (...) ORDER BY id FOR UPDATE before the writes, the same row lock as in the concert-ticket post), a ring cannot form. The second is humility: assume it will happen anyway, because someone, someday, will write a path that forgets.

07The retry the ORM will not write for you

When the database picks you as the victim it does not silently redo your work. It returns an error: SQLSTATE 40P01 in PostgreSQL, 40001 for serialization failures, error 1213 in MySQL, and in Prisma a P2034 ("write conflict or a deadlock"). An ORM will happily surface that as an exception and your user as a 500. The retry has to be written by you, around the whole transaction, not around a single statement.

const RETRYABLE_SQLSTATE = new Set(["40P01", "40001"]); // deadlock_detected, serialization_failure

function isRetryable(e: unknown): boolean {
  const err = e as { code?: string; errno?: number; meta?: { code?: string }; cause?: { code?: string } };
  return (
    err?.code === "P2034" ||                       // Prisma: write conflict or deadlock
    RETRYABLE_SQLSTATE.has(err?.code ?? "") ||     // node-postgres
    RETRYABLE_SQLSTATE.has(err?.meta?.code ?? "") ||
    RETRYABLE_SQLSTATE.has(err?.cause?.code ?? "") ||
    err?.errno === 1213                            // MySQL ER_LOCK_DEADLOCK
  );
}

export async function withRetry<T>(
  fn: () => Promise<T>,                            // must run the WHOLE transaction
  { attempts = 5, baseMs = 50, capMs = 2000 } = {},
): Promise<T> {
  for (let attempt = 0; ; attempt++) {
    try {
      return await fn();
    } catch (e) {
      if (!isRetryable(e) || attempt + 1 >= attempts) throw e;
      // exponential backoff with full jitter, so the two victims do not collide again
      const ceiling = Math.min(capMs, baseMs * 2 ** attempt);
      await new Promise((r) => setTimeout(r, Math.random() * ceiling));
    }
  }
}

// usage
await withRetry(() =>
  prisma.$transaction(async (tx) => {
    await tx.order.update({ where: { id: 1 }, data: { status: "shipped" } });
    await tx.order.update({ where: { id: 2 }, data: { status: "shipped" } });
  }),
);

• Retry the whole unit. The victim was rolled back completely; re-running just the failed statement would leave the earlier ones undone.
• Jitter matters. Two victims that sleep the same 100 ms wake together and may collide again. Randomness breaks the tie.
• Side effects stay out. No email, no payment call inside the callback, or a retry sends it twice. Pair it with an idempotency key, as in the booking post.
• Cap the attempts. A retry loop with no limit turns a deadlock into a livelock under load.

08A checklist, and one mechanism

• Run the foreign-key query above on every database you own. Every suspect gets a decision, an index or a written reason.
• Put an index on the child column before the parent table gets deletes or key updates, not after the first outage.
• Keep transactions short and free of network calls; a lock is held as long as its transaction lives.
• Touch rows in one global order (ascending primary key is the usual choice).
• Wrap every multi-statement transaction in a bounded retry with backoff and jitter, and log each retry so deadlocks become visible instead of invisible.

A lock is only ever as narrow as the index that found the row. Narrow the search and you narrow the lock.

My mantra for this chapter

So the answer to the question I could not answer at first, what is the relationship between a transaction lock and the lock caused by a missing foreign-key index?, is that there is no relationship to find. They are one mechanism seen from two angles: the transaction decides when locks are held, the index decides how many, and a deadlock is what you get when both are generous. Back at the warehouse, the cure was never a stronger chain. It was a catalogue, so the keeper no longer needs to padlock the main gate to find three crates.

09Coming next

Here the lock was wide because of a missing index. In the next post the lock is perfectly narrow, one row, and it is still the problem, because a hundred thousand writers all want that same row. The DBA's notes hold three more cases (the bitmap index, the APPEND hint, the hot block) that I will write up only after I have done the reading, rather than guess.

Written by Vũ Duy Anh, backend engineer in Hà Nội. Questions or corrections are welcome by email.