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.

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)