I always figured an UPDATE that matches zero rows was about as harmless as SQL gets. Nothing matched, nothing changed, so there’s nothing to lock. MySQL disagrees. It’ll lock the empty space where those rows would be, and make anybody who tries to put something there wait. Those are gap locks, and I managed to write SQL for years without thinking about them once.

I’m not an InnoDB expert (I want to be very clear about that). I ran into this, read more of the MySQL manual than I ever planned to, and came out with a slightly better mental model. Some of it confused me for a lot longer than I’d like to admit… so if it’s confusing you too, hopefully this saves you some time.

The service in question did a lot of upserts with optimistic locking (I’ve written about my complicated feelings toward that code before). Picture 50 concurrent jobs, each upserting thousands of rows into a big state table and bumping a single stats row, all in one transaction, over and over. Some of those transactions were also slow. The worst offender was a synchronous call to a third party, right in the middle of the transaction. (Oops.)

Eventually, this started showing up in the logs.

ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction

I kept looking for two workers changing the same row. Other than the stats row, there weren’t any. Every query touched a different key, and I reread them more times than I want to count. So what was everybody waiting on?

What actually gets locked

Take a jobs table with id as its primary key. There are rows with ids 3 and 8, and nothing in between. (I don’t know why there are jobs 3 and 8 and nothing between them either. It’s a curated example. Just roll with it.)

InnoDB locks entries in an index, not rows in a table, which is how empty space can be locked at all. A record lock protects an existing index record. A gap lock stops other transactions from inserting between two records.

An optimistic update only changes a row if it’s still in the state you expect. Say T1 wants to move job 5 from queued to running.

BEGIN;
UPDATE jobs SET state = 'running'
  WHERE id = 5 AND state = 'queued';
-- 0 rows affected. T1 stays open.

If job 5 exists, InnoDB locks that one record and moves on. But if it doesn’t exist (it hasn’t been created yet, or it already got cleaned up), the update matches nothing. InnoDB’s default isolation level is REPEATABLE READ (an isolation level is the setting for how much transactions running at the same time can see of each other). At that level, matching nothing locks the whole gap between 3 and 8.

Now T2 comes along with an upsert for a completely different job.

INSERT INTO jobs (id, state)
  VALUES (6, 'queued')
  ON DUPLICATE KEY UPDATE
    state = 'queued';

There’s no row 6, so that upsert is really an insert, and inserts into a locked gap wait. It doesn’t matter that T1 was only ever looking for 5. An upsert for 4, 5, or 7 would wait too. T2 waits until T1 commits, which in our case meant waiting until a third party got around to responding.

Why lock rows that don’t exist? T1 just learned there’s no queued job 5, and it might be about to act on that. The gap lock keeps that true until T1 finishes, so nobody can slip a surprise row in behind its back (the docs call these phantoms).

A plain SELECT doesn’t do this, by the way. It reads a snapshot and takes no locks. UPDATE, DELETE, and SELECT ... FOR UPDATE do. And if your WHERE clause uses a non-unique index, InnoDB locks the gaps around everything it scans, even when it finds rows. If it uses no index at all, you’ve locked… a lot.

READ COMMITTED gives up that promise. The same update takes no gap lock, and T2’s upsert goes right through. You can step through both versions here.

T1 updates job 5, which doesn't exist. Then T2 upserts job 6.

What we changed

The sync call came out first. Obviously, lol. Our poor databases. No database setting was going to fix a transaction that held its locks while it waited on somebody else’s API.

Then we ran those transactions at READ COMMITTED. Those writes were independent, so nothing needed a range of the table to hold still. The gap waits went away, and once nobody was stuck in a gap, nobody was stuck holding the stats row either. (It’s still one row everybody wants. The line is just a lot shorter now.)

That one line does change things, though. At READ COMMITTED, every read sees the latest committed data, so reading the same thing twice can give you two different answers. So you have to be very intentional with how and where you use it! Duplicate-key and foreign-key checks still take gap locks, so upserts can still occasionally wait on each other. The isolation-level docs have the full list.

One gotcha if you try this. Set it for the transaction (SET TRANSACTION with no SESSION), not the session, or it’ll quietly follow that connection back into the pool and surprise whoever gets it next.

When waiting turns into a deadlock

All of that was about waiting. But if your code ever does “update it, and insert it if it wasn’t there,” the same gap locks can deadlock too, and this was the part that took me longest to get.

Two gap locks on the same gap don’t block each other. They only block inserts. So say two workers want to create rows that don’t exist yet. T1 wants 5 and T2 wants 6.

  1. T1 updates 5. Nothing matches, so it locks the gap between 3 and 8.
  2. T2 updates 6. Same gap. Gap locks don’t conflict, so T2 gets one too.
  3. T1 inserts 5, into a gap T2 has locked. T1 waits.
  4. T2 inserts 6, into a gap T1 has locked. T2 waits.

Neither can move until the other one finishes, and neither can finish. InnoDB notices and kills one of them.

ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

The usual deadlock advice is to take locks in the same order everywhere. That doesn’t help here, because both transactions did take the same gap lock in the same order. They’re each fine until they try to insert. READ COMMITTED helps, since the updates stop taking gap locks. So does inserting first and updating on a duplicate, which is what INSERT ... ON DUPLICATE KEY UPDATE is for. And the MySQL deadlock guide says to be ready to retry the whole transaction anyway, because sometimes InnoDB will kill one no matter what you do.

A timeout means you waited too long for somebody. A deadlock means you were waiting on each other, so waiting longer was never going to help.

Next time every query touches a different key and things are still stuck, I’m checking the gaps… and whatever else the transaction is doing while it holds them.