InnoDB Deadlock - Next Key Locking

So you use InnoDB, have indexes on your table, think of row level locking and concurrent queries, feel good and go to sleep. All this while forgetting that even UPDATE and SELECT .... FOR UPDATE statements will (or may) also use the same index for scanning or updating. Then what? You may ask.

Well, InnoDB row level locking works in a somewhat different manner when using indexes. In this case, InnoDB locks index records in shared or exclusive mode when searching or scanning an index. Therefore, as mentioned in MySQL Documentation, the row level locks are actually index record locks.

To complicate matters (or resolve issues) further, the lock is a gap lock. A gap lock refers to a lock that only locks a gap before some index record.

As per the example in MySQL Documentation, lets say we have a query like this.

   1: SELECT * FROM child WHERE id > 100 FOR UPDATE;

And there is an index on id column. The query will lock all the index records where id is greater than 100, like 103, 107, etc. Meanwhile, the query also locks out inserts made in the gaps, say for 101,102, 104, 105, 106, 108 and above. If this is not done, there may be inserts while the transaction is under way.

Now let us consider a little tricky problem. Suppose we have a table table_name with index on colx. We will have two queries running in parallel. For sure, both the queries are working on only one row each and as per the application, they are always different queries.

The queries we have are:

   1: mysql> SELECT * FROM table_name WHERE

   2:     -> colx IS NULL

   3:     -> LIMIT 1

   4:     -> FOR UPDATE;

and

   1: mysql> UPDATE table_name SET

   2:     -> colx = NULL, coly = NULL

   3:     -> WHERE colz = 'something';

The first query starts locking the index records. But locking is not done in a single shot, it is done record by record. Meanwhile, the second query also gets lock on the record that signifies the current value of colx and proceeds towards the NULL value record. Now by the time second query gets to the NULL value record, that gets locked by the first query and first query somehow waits for the lock already grabbed by second one. Huh!

You need to be very (un)lucky to achieve this.

Workarounds

1. Figure out all such indexes and queries where a deadlock can happen. In most cases, theoretical investigation may lead to unnecessary paranoia, so its better to have a regression test on your system and monitor for deadlocks. If you can, part away from those indexes.
2. If you think you cannot live without your indexes, and the queries involved in deadlocks are mutually exclusive, you can go ahead with enabling innodb_locks_unsafe_for_binlog without citing this blog as a reference. It's all your choice.
3. The tests I have conducted have been done on MySQL 4.1.x. There is a claim that from MySQL 5.0.2, UPDATE and DELETE only locks rows that are going to be affected. So this should reduce the probability of deadlocks. I haven't tested it though.

Hope this blog was helpful to you. Keep posting your comments.