MySQL Deadlock using an index with a new value

Question

Table:

create table properties
(
  id              int auto_increment primary key,
  other_id        int          null
);

create index index_properties_on_other_id
  on properties (other_id);

TX 1:

start transaction;
SET @last_id = 1;
delete from `properties` WHERE `properties`.`other_id` = @last_id;
INSERT INTO `properties` (`other_id`) VALUES (@last_id);
commit

TX 2:

start transaction;
SET @last_id = 2;
delete from `properties` WHERE `properties`.`other_id` = @last_id;
INSERT INTO `properties` (`other_id`) VALUES (@last_id);
commit

Assume table is empty prior to running transactions.

My application has 2 use cases. Sometimes last_id would already be used by another row, hence it would be indexed prior; but sometimes it would be generated in same transaction by a previous insert query, and in that case I get a deadlock.

I need to run both transactions until after delete statement. And when I run insert on tx1, it waits to get a lock, then I run insert on tx2, tx2 gets a deadlock and rollsback.

mysql            | LATEST DETECTED DEADLOCK
mysql            | ------------------------
mysql            | 2019-06-03 21:01:05 0x7f0ba4052700
mysql            | *** (1) TRANSACTION:
mysql            | TRANSACTION 320051, ACTIVE 12 sec inserting
mysql            | mysql tables in use 1, locked 1
mysql            | LOCK WAIT 3 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
mysql            | MySQL thread id 286, OS thread handle 139687839577856, query id 17804 172.18.0.1 root update
mysql            | INSERT INTO `properties` (`other_id`) VALUES (@last_id)
mysql            | *** (1) WAITING FOR THIS LOCK TO BE GRANTED:
mysql            | RECORD LOCKS space id 1524 page no 4 n bits 72 index index_properties_on_other_id of table `properties` trx id 320051 lock_mode X insert intention waiting
mysql            | Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
mysql            |  0: len 8; hex 73757072656d756d; asc supremum;;
mysql            | 
mysql            | *** (2) TRANSACTION:
mysql            | TRANSACTION 320052, ACTIVE 8 sec inserting
mysql            | mysql tables in use 1, locked 1
mysql            | 3 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
mysql            | MySQL thread id 287, OS thread handle 139687973168896, query id 17814 172.18.0.1 root update
mysql            | INSERT INTO `properties` (`other_id`) VALUES (@last_id)
mysql            | *** (2) HOLDS THE LOCK(S):
mysql            | RECORD LOCKS space id 1524 page no 4 n bits 72 index index_properties_on_other_id of table `properties` trx id 320052 lock_mode X
mysql            | Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
mysql            |  0: len 8; hex 73757072656d756d; asc supremum;;
mysql            | 
mysql            | *** (2) WAITING FOR THIS LOCK TO BE GRANTED:
mysql            | RECORD LOCKS space id 1524 page no 4 n bits 72 index index_properties_on_other_id of table `properties` trx id 320052 lock_mode X insert intention waiting
mysql            | Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
mysql            |  0: len 8; hex 73757072656d756d; asc supremum;;
mysql            | 
mysql            | *** WE ROLL BACK TRANSACTION (2)

Status of locks after delete statements:

mysql            | ---TRANSACTION 320066, ACTIVE 90 sec
mysql            | 2 lock struct(s), heap size 1136, 1 row lock(s)
mysql            | MySQL thread id 287, OS thread handle 139687973168896, query id 18076 172.18.0.1 root
mysql            | TABLE LOCK table `properties` trx id 320066 lock mode IX
mysql            | RECORD LOCKS space id 1524 page no 4 n bits 72 index index_properties_on_other_id of table `properties` trx id 320066 lock_mode X
mysql            | Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
mysql            |  0: len 8; hex 73757072656d756d; asc supremum;;
mysql            | 
mysql            | ---TRANSACTION 320065, ACTIVE 95 sec
mysql            | 2 lock struct(s), heap size 1136, 1 row lock(s)
mysql            | MySQL thread id 286, OS thread handle 139687839577856, query id 18039 172.18.0.1 root
mysql            | TABLE LOCK table `properties` trx id 320065 lock mode IX
mysql            | RECORD LOCKS space id 1524 page no 4 n bits 72 index index_properties_on_other_id of table ``properties` trx id 320065 lock_mode X
mysql            | Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
mysql            |  0: len 8; hex 73757072656d756d; asc supremum;;

So two transactions are deleting/inserting different other_ids, I wasn't expecting them to get into a deadlock. I want to learn why exactly this is happening.

Answer 1

MySQL does not lock something that is not there, e.g. locks rows that you didn't delete. It also does not store that you tried to delete rows with the specific value "1". What it does instead is that it marks the space where the "1" should have been if it would have been there, and locks it with a gap lock, which has the following characteristics:

Gap locks in InnoDB are “purely inhibitive”, which means that their only purpose is to prevent other transactions from inserting to the gap. Gap locks can co-exist. A gap lock taken by one transaction does not prevent another transaction from taking a gap lock on the same gap. There is no difference between shared and exclusive gap locks. They do not conflict with each other, and they perform the same function.

In an empty table, the place that the 1 would have been is "anywhere in the table" (or anywhere from the start to the "supremum" mentioned in the deadlock) - which is consequently gaplocked by the delete. The same is true for the 2. And those locks do not conflict each other by definition.

But the insert does. The first insert will have to wait for the gaplock that the second transaction issued for its delete. If the second transaction now tries to also insert into the gap, this would require the gaplock from the first transaction to be lifted, but this cannot happen because the first transaction already waits for the second gaplock to be lifted. So you get a deadlock.

Once you fill your table, this will happen less often, as the gaplocks do not need to span the whole table anymore. If you e.g. already have other_id 1 and 3 in your table, delete/inserting value 2 and 4 will not deadlock each other.

In general, empty tables are a rarity, and you cannot and should not infer anything from such a special case to the normal behaviour. You basically have to accept edge cases:

Gap locks are part of the tradeoff between performance and concurrency

So in the general use case, you just need to be prepared that occasionally a deadlock may happen (and then repeat the transaction). If your expected use case is that you have a basically empty table, or are mostly adding at the end of the values, or oftentimes add 2 values into the same gap, you may need a different solution (and should ask a question on how to proceed in this specific use case). You may e.g. be able to use a unique index (that does not require gap locks), recode/hash your value to sit randomly in the index, or you let all transactions lock something that you know exists, so they wait for each other.