MySQL Bugs: #98639: Redundant row-level locking for secondary index

Bug #98639	Redundant row-level locking for secondary index
Submitted:	17 Feb 2020 15:48	Modified:	19 Feb 2020 17:24
Reporter:	Sergei Muraviev	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S5 (Performance)
Version:	8.0.19	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	innodb, locking

Description:
I found some redundant row-level locking when scanning a range of non-unique index.
The problem does not occur when scanning a unique index.

How to repeat:
CREATE TABLE foo (
  a INT NOT NULL,
  b INT NOT NULL,
  c CHAR(1),
  PRIMARY KEY (a),
  KEY (b)
) ENGINE=InnoDB;

INSERT INTO foo VALUES (1,1,'A'), (3,3,'B'), (5,5,'C'), (7,7,'D'), (9,9,'E');

Session 1:
START TRANSACTION;
SELECT * FROM foo WHERE b < 2 FOR UPDATE;

Session 2:
DELETE FROM foo WHERE b = 3;  -- Blocks

You can also compare this behavior with locking a unique index, as shown below.

Session 1:
START TRANSACTION;
SELECT * FROM foo WHERE a < 2 FOR UPDATE;

Session 2:
DELETE FROM foo WHERE a = 3;  -- Success

Suggested fix:
See the non-unique index record to the right of the scanned range (b = 3). This index record does not belong to the scanned range in the locking read of session 1.
If the repeatable read isolation level is used, then it's enough to set a gap lock on this index record, not a next-key lock.
If a weaker isolation level is used, then this index record does not need to be blocked at all.

Hello Mr. Vuraviev,

Thank you for your bug report.

In order to be more precise with your report, can you send us the output from the innodb status for both cases separately.

Thanks in advance.

InnoDB status (non-unique index)

Attachment: status (non-unique index).txt (text/plain), 5.16 KiB.

InnoDB status (unique index)

Attachment: status (unique index).txt (text/plain), 5.13 KiB.

Thank you for your feedback.

Thanks to your feedback it was easy to understand what happened.

Simply, you have too few rows in that table. In the case when the search is done by the primary key,  the optimiser calculated that it is faster to search through index then to scan the table.

In case of a non-unique key, optimiser chose table scanning, which is why that row is locked.

Insert many thousand rows and you will notice that locking will be very similar.

Not a bug.

Firstly, if the non-unique index were not used, and the entire table were scanned, then the next index records (b = 5, 6, etc) would also be blocked, but this does not happen.

Secondly, the size of the table is not too small. I've just tested this example on a table containing 10,000 rows. The result is the same, with exactly the same locks.

The big table for testing

Attachment: foo.sql (application/octet-stream, text), 173.83 KiB.

Here is some additional information in case someone starts fixing this issue.

1. The issue concerns any secondary index, and not just non-unique. For clustered index, it was fixed in version 8.0.18.

2. Blocking read direction matters (ascending or descending). Incorrect locking (unconditional next-key lock) occurs only at the end of the scan, but not at the beginning.

3. Some additional information can be found in the answers to the forum topic: https://forums.mysql.com/read.php?22,684356,684356

Hi Mr. Muraviev,

First to answer your question, the scanning stops when the first row in the sequence does not meets the condition.

Regarding the larger table, thank you for it, but you forgot to send us output from the InnoDB status which proves that non-unique index is not used in the query execution, which leads to an extra row being locked.

Mr. Muraviev,

I have to excuse myself. No need to send us anything.

Let me explain what happens with non-unique index. First of all, whenever InnoDB has to read a row or key entry, it has to lock it.

The real reason on why is extra row being locked is very simple.

Imagine you have  a table with many rows with with  non-unique indices on two integer columns. Next, imagine that values of the first column are the following ones:

1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4...........

And that the values of the second column are like this:

1,2,3,4,5 .......

And of course, you are not using equality condition, but conditions of smaller or greater values.

Simply, with non-unique index, InnoDB can not know what value is the next one. InnoDB has to read index entries until it hits the value that does not meet the criteria. But, in order to read it, in needs to lock it first, in order to prevent DMLs on those rows.

That is a full explanation.

Not a bug.

> Simply, with non-unique index, InnoDB can not know what value is the next one. InnoDB has to read index entries until it hits the value that does not meet the criteria. But, in order to read it, in needs to lock it first, in order to prevent DMLs on those rows.
As I already specified above, this bug arises not only for a non-unique index, but for any secondary index.
In addition, if InnoDB needs some auxiliary locks during the scan of the index range, then there should be no problem to remove these locks at the end of the scan and not leave them until the end of the current transaction.

Well, let it not be called a bug. Excessive locking is most likely a performance issue. I've changed the severity of this report.

Information for programmers.
The problem is that the last index record on which the scan ends is blocked incorrectly with the unconditional X-lock (the record itself plus a gap before it). However, this index record no longer meets the condition (it's out of the scan range), and it either does not need to be blocked, or it needs to be blocked using gap-only locking. The gap lock should only be set in the following two cases: 1) if this index record is to the right of the scanned range, and the index is ascending, 2) if this index record is to the left of the scanned range, and the index is descending. Otherwise this index record shouldn't be blocked. That's all. I've just described how to fix the bug.

Gap locks can not be used for this purpose. 

Where and why are gap locks used is described in our Reference Manual.

Gap locks can not be used for this purpose. 

Where and why are gap locks used is described in our Reference Manual.