I recently had to diagnose a deadlock in an application that seemed impossible to me. Even after I found out how to reproduce it, I don't really undestand why it happens. I'm considering filing a MariaDB bug, but since I'm not a database expert, I thought I'd ask first if someone can tell me there is a reasonable explanation.

Edit: Filed as a bug now at https://jira.mariadb.org/browse/MDEV-17512

I used a recent version of mariadb (will have to look up the exact version number, but I think that's more interesting for a bug report than for a general "why does this happen") with its default transaction isolation level of REPEATABLE_READ. Here is how I can reproduce the problem:

First, let's set up the test:

create database deadlock;
use deadlock;
create table foo(id int primary key) engine=InnoDB;
insert into foo values (10);

Now we can start. Let's open two connections A and B to the database.

-- Connection A
begin;
delete from foo;

-- Connection B
begin;
delete from foo;

At this point, the delete issued by B is waiting. This is as expected because A is holding the relevant locks.

-- Connection A
insert into foo values (9);

And at this point, mariadb kills the waiting query of B due to a deadlock. This is very surprising to me, because it would mean that B has already managed to acquire some locks.

As an additional point of information, if you use the id 11 instead of 9 in the last statement, there is no deadlock.

So can someone explain what is happening here? Is this normal behaviour, or should I file a bug?

Edit: Here is the output of SHOW ENGINE INNODB STATUS:

------------------------
LATEST DETECTED DEADLOCK
------------------------
2018-10-15 21:33:09 0x7f9f9da02700
*** (1) TRANSACTION:
TRANSACTION 481736, ACTIVE 9 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 1136, 1 row lock(s)
MySQL thread id 3049, OS thread handle 140323520444160, query id 12527706 localhost root updating
delete from foo
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 32882 page no 3 n bits 72 index PRIMARY of table `deadlock`.`foo` trx id 481736 lock_mode X waiting
Record lock, heap no 2 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 4; hex 8000000a; asc     ;;
 1: len 6; hex 0000000759c3; asc     Y ;;
 2: len 7; hex 2d000002182fc2; asc -    / ;;

*** (2) TRANSACTION:
TRANSACTION 481731, ACTIVE 16 sec inserting
mysql tables in use 1, locked 1
3 lock struct(s), heap size 1136, 3 row lock(s), undo log entries 1
MySQL thread id 3050, OS thread handle 140323521046272, query id 12527773 localhost root update
insert into foo values(9)
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 32882 page no 3 n bits 72 index PRIMARY of table `deadlock`.`foo` trx id 481731 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;;

Record lock, heap no 2 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 4; hex 8000000a; asc     ;;
 1: len 6; hex 0000000759c3; asc     Y ;;
 2: len 7; hex 2d000002182fc2; asc -    / ;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 32882 page no 3 n bits 72 index PRIMARY of table `deadlock`.`foo` trx id 481731 lock_mode X locks gap before rec i
Record lock, heap no 2 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 4; hex 8000000a; asc     ;;
 1: len 6; hex 0000000759c3; asc     Y ;;
 2: len 7; hex 2d000002182fc2; asc -    / ;;

*** WE ROLL BACK TRANSACTION (1)