MySQL Bugs: #48911: SELECT ... FOR UPDATE doesn't do exclusive lock when table is empty

Bug #48911	SELECT ... FOR UPDATE doesn't do exclusive lock when table is empty
Submitted:	19 Nov 2009 15:46	Modified:	31 Mar 2010 12:19
Reporter:	Vitaliy Garnashevich	Email Updates:
Status:	Duplicate	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S2 (Serious)
Version:	5.1.41, 5.1.42-bzr	OS:	Any
Assigned to:	Assigned Account	CPU Architecture:	Any
Tags:	deadlock, lock, select for update

Description:
In our system there are many concurrent worker threads. Each one essentially does the following: 
1) find some specific record (SELECT)
2) if found, modify it (UPDATE)
3) if not found, create new one (INSERT)

In this case there is great possibility of a deadlock (when two threads get shared lock with SELECT, and then none of them can do UPDATE). We're trying to solve this by using SELECT FOR UPDATE, in order to get exclusive lock instead of shared lock.

This works when both threads select same record. The problem is that when the table is empty, MySQL doesn't do exclusive lock. In such case threads can deadlock on INSERT.

How to repeat:
SESSION 1: create table tt (id int primary key) engine=InnoDB;
SESSION 1: set autocommit=0;
SESSION 1: begin;
SESSION 1: select * from tt where id=1 for update;

SESSION 2: set autocommit=0;
SESSION 2: begin;
SESSION 2: select * from tt where id=1 for update;

SESSION 1: insert into tt values(1);
SESSION 2: insert into tt values(1);

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

Suggested fix:
Do exclusive table lock on SELECT FOR UPDATE when the table is empty.

Or even better, always do exclusive table lock on SELECT FOR UPDATE.

Thank you for the problem report. After enabling lock monitor one can see that after execution of SELECT ... FOR UPDATE on empty table we have the following locks set:

---TRANSACTION 0 13827, ACTIVE 9 sec, OS thread id 2957455360
2 lock struct(s), heap size 320, 1 row lock(s)
MySQL thread id 6, query id 215 localhost root
TABLE LOCK table `test`.`tt` trx id 0 13827 lock mode IX
RECORD LOCKS space id 0 page no 52 n bits 72 index `PRIMARY` of table `test`.`tt
` trx id 0 13827 lock_mode X
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0 0: len 8; hex 73757072656d756d; asc supremum;;

---TRANSACTION 0 13826, ACTIVE 43 sec, OS thread id 2955325440
2 lock struct(s), heap size 320, 1 row lock(s)
MySQL thread id 3, query id 188 localhost root
TABLE LOCK table `test`.`tt` trx id 0 13826 lock mode IX
RECORD LOCKS space id 0 page no 52 n bits 72 index `PRIMARY` of table `test`.`tt
` trx id 0 13826 lock_mode X
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
0: len 8; hex 73757072656d756d; asc supremum;;

So, X locks are set, on supremum record. But(!) second transaction was able to set X lock on supremum record even after that same supremum record was already X locked by the first transaction. Hence the following deadlock.

I consider this a (serious) bug. At least, nothing like this is documented at http://dev.mysql.com/doc/refman/5.1/en/innodb-locks-set.html. This behavior not only leads to deadlock in the scenario described, but is against common understanding of X (exclusive!) lock. There can NOT be two exclusive lock on one record, or these locks should have some other name, not "exclusive". So, if it is intended and can not be easily changed, it should be clearly and explicitly documented. Supremum record looks very different from any real index record in this respect.

P.S.

Deadlock happens because at INSERT step both transactions try to set "insert intention waiting" X lock on supremum record:

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 52 n bits 72 index `PRIMARY` of table `test`.`tt` trx id 0 13827 lock_mode X insert intention waiting
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
0: len 8; hex 73757072656d756d; asc supremum;;

and this is NOT possible because of X lock from the other transaction.

Just realized that the problem is of wider range than just empty tables. It will occur on any SELECT/INSERT:

SESSION 1: create table tt (id int primary key) engine=InnoDB;
SESSION 1: insert into tt values(1),(2);
SESSION 1: set autocommit=0;
SESSION 1: begin;
SESSION 1: select * from tt where id=3 for update;

SESSION 2: set autocommit=0;
SESSION 2: begin;
SESSION 2: select * from tt where id=3 for update;

SESSION 1: insert into tt values(3);
SESSION 2: insert into tt values(3);

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

Problem is related to supremum index records, so it will happen every time you are inserting value that is larger than any existing value in the table.

This is a duplicate of Bug#25847 - Add predicate locking to avoid deadlocks due to locking non-existent rows.