When a transaction is able to delete-mark a record and commit the change, no active transaction may possibly have seen (and locked) the record. The record can be removed by the purge thread at any time, and it is logically equivalent to a gap (non-existing record).
However, currently InnoDB transactions will lock committed delete-marked records.
How to repeat:
Run at least 3 identical DELETE statements in parallel, and possibly some INSERT with a key value slightly smaller than that of the deleted record. InnoDB should report a bogus deadlock between 2 DELETE statements:
trx (1) has obtained an X-lock on the delete-marked committed record
trx (2) is waiting for an X-lock on the record and the preceding gap
trx (1) is waiting for an X-lock on the record and the preceding gap
Transactions should ignore committed delete-marked records when they come across them.
The solution we will try to implement is that when using isolation level is READ COMMITTED then DELETE will ignore any delete marked rows.
This is same as https://bugs.mysql.com/bug.php?id=19762