Bug #19762 InnoDB should not lock a delete-marked record
Submitted: 12 May 2006 10:18 Modified: 29 Jun 2011 14:45
Reporter: Marko Mäkelä Email Updates:
Status: Won't fix Impact on me:
None 
Category:MySQL Server: InnoDB storage engine Severity:S4 (Feature request)
Version:all OS:Any (all)
Assigned to: Geir Høydalsvik CPU Architecture:Any

[12 May 2006 10:18] Marko Mäkelä
Description:
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

Suggested fix:
Transactions should ignore committed delete-marked records when they come across them. Possibly also the deadlock detection algorithm (lock_deadlock_recursive) could be improved to ignore locks that are already partially held by the transaction, i.e., an exclusive rec+gap lock cannot be granted to other transactions if the current transaction is holding a lock on rec.
[12 May 2006 11:31] Heikki Tuuri
Yes, a lock on a delete-marked record, where the delete-marking transaction is already committed, is semantically a 'gap' lock, and we could use the gap locking rules for it.
[5 Jun 2006 17:04] Heikki Tuuri
This is more properly classified as a feature request.
[16 Nov 2009 11:11] Marko Mäkelä
Bug #45975 is a possible duplicate.
[29 Apr 2010 12:53] Marko Mäkelä
A possible fix: If the delete-marked committed record is in a secondary index or if there are no secondary indexes, attempt to purge it immediately (possible if no active transaction can see the record). If the purge succeeds, no lock will have to be acquired on the delete-marked record.

Another possible fix: Acquire gap locks on the delete-marked records. Gap locks will not conflict with each other. But make sure that they would conflict with row_ins_clust_index_entry_by_modify() and row_ins_sec_index_entry_by_modify().
[5 Aug 2010 12:59] Marko Mäkelä
Bug #55717 is a duplicate of this.
[11 Aug 2010 7:07] Marko Mäkelä
Fixing this bug would also fix Bug #52020.
[1 Sep 2010 9:07] Marko Mäkelä
Yet another fix: When a transaction is about to lock a committed delete-marked record, signal the purge subsystem to remove the record as soon as possible, converting the record lock to a gap lock on the following record. This would shrink the window of opportunity, but not completely solve the problem.

Another possible fix that we discussed today is to introduce a new type of gap locks that would cover the preceding record (in this case, the committed delete-marked record). Then, instead of locking the delete-marked record, we would acquire the special gap lock on the successor record and a normal gap lock on the delete-marked record. That would complicate the locking rules even further and could blow up the memory usage, by allocating another record bitmap per B-tree index page. That could also introduce locking conflicts in other types of workloads, such as when the same record is being inserted and deleted over and over again.
[6 Sep 2010 18:46] Mikhail Izioumtchenko
another solution that was discussed was to change the semantics 
of the gap lock to cover the delete marked records before and after the gap,
in other words pretend that the delete marked records do not exist as far 
as the gap locks are concerned. The coding and performance implications
are not clear. I wonder if with this approach we could make the purge
pretend the gap locks do not exist?
[29 Jun 2011 13:33] Jon Stephens
Thank you for taking the time to write to us, but this is not a bug. Please double-check the documentation available at http://dev.mysql.com/doc/ and the instructions on
how to report a bug at http://bugs.mysql.com/how-to-report.php
[29 Jun 2011 14:09] Mark Callaghan
Does this status means this will soon be closed?
[29 Jun 2011 14:45] Valeriy Kravchuk
As far as I can see, the decision was made internally not to implement this any time soon:

"Thanks for your request. After initial review, we have determined it will not be implemented in an upcoming release.

An analysis by the InnoDB team indicates that this feature is too hard to implement and brings too little practical benefit."
[4 Jul 2011 23:24] James Day
Is it practical to add counters for rows locked and delete-marked rows locked to help make it easier to diagnose this event?
[21 Jun 2012 21:16] John Smith
Was this ever fixed? It doesn't seem to appear on MySQL v5.1.53+.
[11 Sep 2012 5:31] Marko Mäkelä
No, this bug was not fixed yet and probably will not be fixed in MySQL 5.6 or earlier.

There has been some internal discussion on storing the transaction identifier in each secondary index record. Currently, we only have a per-page PAGE_MAX_TRX_ID in secondary index leaf pages. This and possibly a new undo log format could simplify purge so much that we could have 'on-demand purge' of such delete-marked records.