MySQL Bugs: #19762: InnoDB should not lock a delete-marked record

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

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.

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.

This is more properly classified as a feature request.

Bug #45975 is a possible duplicate.

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().

Bug #55717 is a duplicate of this.

Fixing this bug would also fix Bug #52020.

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.

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?

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

Does this status means this will soon be closed?

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."

Is it practical to add counters for rows locked and delete-marked rows locked to help make it easier to diagnose this event?

Was this ever fixed? It doesn't seem to appear on MySQL v5.1.53+.

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.