Is this surprising deadlock reasonable or a MariaDB bug? 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)
A guess...

DELETE without WHERE needs to lock the entire table.  Perhaps that is done via "start through current end", where the 'end' is at 10.  Hence messing with '9' would be problematic.

On the other hand, '11' is off the end, so less ambiguity.

Are you arguing that neither should deadlock?  Or that both should deadlock?

Here's another aspect...  To do everything "correct" in every case would possibly be very complex.  So some shortcuts have been taken.  And your test case pulls out a case where the shortcut led to an inconsistency.

Or is it "right" to have the inconsistency?  One thread is deleting "old" stuff; the other thread is adding "new" stuff.  Think of a queue -- this is exactly what you need.