When and why can this kind of deadlock occur?

``
------------------------
LATEST DETECTED DEADLOCK
------------------------
130409 0:40:58
*** (1) TRANSACTION:
TRANSACTION 3D61D41F, ACTIVE 3 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 43 lock struct(s), heap size 6960, 358 row lock(s), undo log entries 43
MySQL thread id 17241690, OS thread handle 0x7ffd3469a700, query id 860259163 localhost root update
INSERT INTO notification (other_grouped_notifications_count, user_id, notifiable_type, action_item, action_id, created_at, status, updated_at) VALUES (0, 4442, 'MATCH', 'MATCH', 224716, 1365448255, 1, 1365448255)
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 272207 n bits 1272 index user_id of table notification trx id 3D61D41F lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 69 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
0: len 4; hex 8000115b; asc [;;
1: len 4; hex 0005e0bb; asc ;;

*** (2) TRANSACTION:
TRANSACTION 3D61C472, ACTIVE 15 sec starting index read
mysql tables in use 1, locked 1
3 lock struct(s), heap size 1248, 2 row lock(s)
MySQL thread id 17266704, OS thread handle 0x7ffd34b01700, query id 860250374 localhost root Updating
UPDATE notification SET status=0 WHERE user_id = 4443 and status=1
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 272207 n bits 1272 index user_id of table notification trx id 3D61C472 lock_mode X
Record lock, heap no 69 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
0: len 4; hex 8000115b; asc [;;
1: len 4; hex 0005e0bb; asc ;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 261029 n bits 248 index PRIMARY of table notification` trx id 3D61C472 lock_mode X locks rec but not gap waiting
Record lock, heap no 161 PHYSICAL RECORD: n_fields 16; compact format; info bits 0
0: len 4; hex 0005e0bb; asc ;;
1: len 6; hex 00000c75178f; asc u ;;
2: len 7; hex 480007c00c1d10; asc H ;;

Let's look at the queries that are deadlocking:

Under TRANSACTION 3D61D41F, you have this query:

INSERT INTO `notification` (`other_grouped_notifications_count`, `user_id`,
`notifiable_type`, `action_item`, `action_id`, `created_at`, `status`, `updated_at`)
VALUES (0, 4442, 'MATCH', 'MATCH', 224716, 1365448255, 1, 1365448255)

Under TRANSACTION 3D61C472, you have this query:

UPDATE `notification` SET `status`=0 WHERE user_id = 4443 and status=1

How in thw world could these queries deadlock?

To answer this, you must understand how the InnoDB Storage Engine handles indexes. For starters, click here to see the pictorial representation of InnoDB's Infrastructure.

Here is something to also start with: the gen_clust_index, better known as the Clustered Index. It is the home of the PRIMARY KEY. As the MySQL Documentation says:


All indexes other than the clustered index are known as secondary
indexes. In InnoDB, each record in a secondary index contains the
primary key columns for the row, as well as the columns specified for
the secondary index. InnoDB uses this primary key value to search for
the row in the clustered index.


If the primary key is long, the secondary indexes use more space, so
it is advantageous to have a short primary key.

Since entries in a Secondary Index contain the key back to the Clustered Index, there would be some processing done to align secondary keys with corresponding PRIMARY KEY entries. This is performed in the Insert Buffer contained within ibdata1 (the system tablespace).

Now, look back at the queries.

FIRST QUERY : The INSERT query from TRANSACTION 3D61D41F has to lock a newly generated entry in the gen_clust_index. It also has to create an entry in the Secondary Index for user_id 4442 and must carry the newly created gen_clust_index key and process them together in the Insert Buffer.

SECOND QUERY : The UPDATE query in TRANSACTION 3D61C472 has to get a lock on an already existing row whose user_id is 4443. Consequently, a lock on the corresponding gen_clust_index entry is required.

LOCKS IN COMMON

TRANSACTION 3D61D41F

RECORD LOCKS space id 0 page no 272207 n bits 1272 index `user_id`
0: len 4; hex 8000115b; asc    [;;
1: len 4; hex 0005e0bb; asc     ;;
Record lock, heap no 69 PHYSICAL RECORD: n_fields 2; compact format; info bits 0

TRANSACTION 3D61C472

RECORD LOCKS space id 0 page no 272207 n bits 1272 index `user_id`
0: len 4; hex 8000115b; asc    [;;
1: len 4; hex 0005e0bb; asc     ;;
Record lock, heap no 69 PHYSICAL RECORD: n_fields 2; compact format; info bits 0

Both Transactions Need the Same Part of the gen_clust_index

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 261029 n bits 248 index `PRIMARY` of table `notification` trx id 3D61C472 lock_mode X locks rec but not gap waiting
Record lock, heap no 161 PHYSICAL RECORD: n_fields 16; compact format; info bits 0

According to this, the UPDATE query has attempted to lock first. Unfortunately, that's fair because UPDATE works with an already existing row. The INSERT is attempting to create a new row. It had to auto generate a PRIMARY KEY entry in the same location needed by the UPDATE.

This solves the mystery as to why the deadlock occurs in this particular instance.

StackExchange Database Administrators Q#39550, answer score: 5