MySQL Bugs: #85286: Possible unreasonable gap lock

Bug #85286	Possible unreasonable gap lock
Submitted:	3 Mar 2017 7:00	Modified:	2 Apr 2017 13:03
Reporter:	dean winchester	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S3 (Non-critical)
Version:	5.7	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
I see some unexpected gap lock(to me at least) when one transaction is selecting something for update bug without a match. See how to reproduce below. 

How to repeat:
create table:
`create table testdl (id int auto_increment, c int, primary key (id), key idx_c (c));`
add a record:
`insert into testdl (c) values (1000);`

With isolation level repeatable read:
Tx1: `select * from testdl where c = 500 for update; --no match, coz there's only one record with c = 1000`
Tx2: `insert into testdl (c) values (?); -- this hangs for any value < 1000`

So looks like when Tx1 fails to find a match, practically the whole range up to 1000 is locked. I don't see the point of this, after all, I'm selecting `c = 500`, not `c < 500` or something

Hi!

There are very good reasons for taking this gap lock. Gap locks are there to assure ACID compatibility and multi-versioning control. Second standard dictates that that lock is taken even when WHERE clause in DML does not match any row.

In your case, gap is formed between lowest pseudo-record, named "infimum" and the physical record that you inserted. 

You can read all about gap locks, pseudo-record and related issues in our 5.7 manual, in the chapters 14.2 and in the Glossary.

Hi,
  I'm not sure what 'Second standard' means, is it second normal form? If so, I still can't see what it relates to this gap lock thing.
  Anyway, the problem is I can't see what possible harm can it be in this case, say we prohibit insertion of value 500 only (by other concurrent transactions), but allows everything else?. Or maybe is it just a implementation thing? The node 500 does not really exist, so we have to lock the next thing, in this simple case, 1000?

Hi,

By second standard I implied MVCC, which means multi-versioning control. It has very much to do with gap locks as explained in that chapter that I already quoted. It also has to do with pseudo-records, which I, also, wrote about.

To repeat, all this is explained in our manual, in those chapters that I mentioned in my previous post.

I think manual explains gap locks well enough here:

https://dev.mysql.com/doc/refman/5.7/en/innodb-locking.html#innodb-gap-locks

Valerii,

Thanks.

Guys, please stop pointing me the doc, I know where it is.

Let me put it another way:

Here's the table:
`create table t (id int(11) primary key, c int(11), key idx_c (c));`
`insert into t values (1, 1), (2, 5), (3, 10), (4, 20);`

So the table looks like:
+----+------+
| id | c    |
+----+------+
|  1 |    1 |
|  2 |    5 |
|  3 |   10 |
|  4 |   20 |
+----+------+

Now:
Tx1: `begin; select * from t where c = 5 for update;`
This locks the range (1, 10).

I think that confuses a lot of people, why can't I insert an 8 while some other guy select 5 for update? Is it necessary to prevent some shit happen(which I can not figure out)? Or is it an implementation thing?

The answer is simple. Due to the gap lock. I do recommend reading the entire 14.2. chapter from our 5.7 manual.

Let me study your case with the following enabled to get locks information in details:

mysql> show global variables like 'innodb_status_output%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| innodb_status_output       | ON    |
| innodb_status_output_locks | ON    |
+----------------------------+-------+
2 rows in set (0.02 sec)

In one session:

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from t where c = 5 for update;
+----+------+
| id | c    |
+----+------+
|  2 |    5 |
+----+------+
1 row in set (0.00 sec)

In another session:

mysql> show engine innodb status\G
...
------------
TRANSACTIONS
------------
Trx id counter 2328
Purge done for trx's n:o < 2324 undo n:o < 0 state: running but idle
History list length 6
LIST OF TRANSACTIONS FOR EACH SESSION:
---TRANSACTION 422168432626424, not started
0 lock struct(s), heap size 1136, 0 row lock(s)
---TRANSACTION 2327, ACTIVE 26 sec
4 lock struct(s), heap size 1136, 3 row lock(s)
MySQL thread id 3, OS thread handle 140693130499840, query id 36 localhost root
TABLE LOCK table `test`.`t` trx id 2327 lock mode IX
RECORD LOCKS space id 27 page no 4 n bits 80 index idx_c of table `test`.`t` trx id 2327 lock_mode X
Record lock, heap no 3 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 4; hex 80000005; asc     ;;
 1: len 4; hex 80000002; asc     ;;

RECORD LOCKS space id 27 page no 3 n bits 80 index PRIMARY of table `test`.`t` trx id 2327 lock_mode X locks rec but not gap
Record lock, heap no 3 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 4; hex 80000002; asc     ;;
 1: len 6; hex 000000000909; asc       ;;
 2: len 7; hex a90000011d011c; asc        ;;
 3: len 4; hex 80000005; asc     ;;

RECORD LOCKS space id 27 page no 4 n bits 80 index idx_c of table `test`.`t` trx id 2327 lock_mode X locks gap before rec
Record lock, heap no 4 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 4; hex 8000000a; asc     ;;
 1: len 4; hex 80000003; asc     ;;

So, we had a next-key lock on the secondary index record with value 5 (expected), primary key lock on record with value 2 (surely, we locked (2,5), not any gap, and then a gap lock on the secondary index record with value 3 (that is, row (3,10)). The later is probably because the index on c is not unique, and we have to read the next record to check if it's 5. It was 10, so record lock is released, but gap before it stays locked.

Now, in another session, we can try to insert the following:

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t values(5,3);
...

It hangs:

---TRANSACTION 2328, ACTIVE 40 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 1136, 1 row lock(s), undo log entries 1
MySQL thread id 4, OS thread handle 140693130233600, query id 42 localhost root update
insert into t values(5,3)
------- TRX HAS BEEN WAITING 40 SEC FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 27 page no 4 n bits 80 index idx_c of table `test`.`t` trx id 2328 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 3 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 4; hex 80000005; asc     ;;
 1: len 4; hex 80000002; asc     ;;

because it needs "insert intention" (a kind of gap) lock before the record (2,5), as 3 is before 5, but the gap is locked.

Now, if we rollback and try value 8 for column c:

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t values(6,8);
...

it also hangs, and we see:

---TRANSACTION 2329, ACTIVE 26 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 1136, 1 row lock(s), undo log entries 1
MySQL thread id 4, OS thread handle 140693130233600, query id 47 localhost root update
insert into t values(6,8)
------- TRX HAS BEEN WAITING 26 SEC FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 27 page no 4 n bits 80 index idx_c of table `test`.`t` trx id 2329 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 4 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 4; hex 8000000a; asc     ;;
 1: len 4; hex 80000003; asc     ;;

Yes, we want insert intention (gap) lock for value 8 that fits before 10, but it's locked.

All these are (more or less) documented, for range 1 < c < 5 and for range 5 < c < 10. Counterintuitive, but this is how it is implemented, to make sure no one inserts row that your SELECT ... FOR UPDATE may see if executed again (to prevent phantom rows).

This could be implemented differently, maybe, but we have InnoDB more or less like this for many years.

Now, if you change your key to UNIQUE:

mysql> alter table t drop key idx_c;
Query OK, 0 rows affected (0.15 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> alter table t add unique key idx_c(c);
Query OK, 0 rows affected (0.26 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> select * from t;
+----+------+
| id | c    |
+----+------+
|  1 |    1 |
|  2 |    5 |
|  3 |   10 |
|  4 |   20 |
+----+------+
4 rows in set (0.00 sec)

We'll get different locking:

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from t where c = 5 for update;
+----+------+
| id | c    |
+----+------+
|  2 |    5 |
+----+------+
1 row in set (0.00 sec)

Now, in other session:

---TRANSACTION 2346, ACTIVE 13 sec
3 lock struct(s), heap size 1136, 2 row lock(s)
MySQL thread id 3, OS thread handle 140693130499840, query id 58 localhost root
Trx read view will not see trx with id >= 2346, sees < 2346
TABLE LOCK table `test`.`t` trx id 2346 lock mode IX
RECORD LOCKS space id 27 page no 4 n bits 72 index idx_c of table `test`.`t` trx id 2346 lock_mode X locks rec but not gap
Record lock, heap no 3 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 4; hex 80000005; asc     ;;
 1: len 4; hex 80000002; asc     ;;

RECORD LOCKS space id 27 page no 3 n bits 80 index PRIMARY of table `test`.`t` trx id 2346 lock_mode X locks rec but not gap
Record lock, heap no 3 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 4; hex 80000002; asc     ;;
 1: len 6; hex 000000000909; asc       ;;
 2: len 7; hex a90000011d011c; asc        ;;
 3: len 4; hex 80000005; asc     ;;

we see no gap locks! And we can do this in another session:

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t values(5,3);
Query OK, 1 row affected (0.00 sec)

mysql> insert into t values(6,8);
Query OK, 1 row affected (0.00 sec)

mysql> select * from t;
+----+------+
| id | c    |
+----+------+
|  1 |    1 |
|  5 |    3 |
|  2 |    5 |
|  6 |    8 |
|  3 |   10 |
|  4 |   20 |
+----+------+
6 rows in set (0.00 sec)

All these because we are sure there may be at most one record with some specific value in the c column.

To summarize, just check how it works. InnoDB locks are mostly documented. Ehen they are not - I complain, see my bug reports.

On the other hand, Dean, you maybe even right to some extent, as blocking value > 5 and < 10 is somewhat unexpected. See my https://bugs.mysql.com/bug.php?id=85749 reported to highlight this specifically.

It seems gap lock (for the gap before the next secondary index record, even different) is the only way to prevent phantom rows. At READ COMMITTED isolation level one can easily insert another row with c = 5 and then, in the same transaction, same SELECT returns different number of rows:

mysql> set tx_isolation='read-committed';
Query OK, 0 rows affected (0.02 sec)

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> explain select * from t where c = 5 for update;
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref   | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
|  1 | SIMPLE      | t     | NULL       | ref  | idx_c         | idx_c | 5       | const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> select * from t where c = 5 for update;
+----+------+
| id | c    |
+----+------+
|  2 |    5 |
+----+------+
1 row in set (0.00 sec)

mysql> select * from t where c = 5 for update;
+----+------+
| id | c    |
+----+------+
|  2 |    5 |
|  6 |    5 |
+----+------+
2 rows in set (0.00 sec)

In between selects I just did:

mysql> insert into t values (6,5);
Query OK, 1 row affected (0.10 sec)

from the other session. For UNIQUE index this is not a problem, as we fail fro the same c value.

At default REPEATABLE READ (that is aimed at preventing phantom rows) that INSERT would wait:

---TRANSACTION 8732, ACTIVE 2 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 1136, 1 row lock(s), undo log entries 1
MySQL thread id 10, OS thread handle 0x7ff19c04c700, query id 41 localhost root update
insert into t values(6,5)
------- TRX HAS BEEN WAITING 2 SEC FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 11 page no 4 n bits 72 index idx_c of table `test`.`t` trx id 8732 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 4 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 4; hex 8000000a; asc     ;;
 1: len 4; hex 80000003; asc     ;;

------------------
TABLE LOCK table `test`.`t` trx id 8732 lock mode IX
RECORD LOCKS space id 11 page no 4 n bits 72 index idx_c of table `test`.`t` trx id 8732 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 4 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 4; hex 8000000a; asc     ;;
 1: len 4; hex 80000003; asc     ;;

and note WHAT gap lock it is waiting for, check value above, hex 8000000a is for 10, hex 80000003 is for 3, so this is the gap before (3,10) record, this one. Having this gap lock is the only way to prevent phantom row from appearing for the initial transaction, as row (6,5) is inserted after (2,5) into the non-unique secondary index, as index records there are sorted by primary key values ASC in it.

As we do not have any row besides (3,10) and we can not lock "just gaps" without  referring to real record, we had to lock that gap, and this locks entire interval 5 <= c < 10 from further insertions.

We may say this is implementation specific (other databases may prevent phantom rows differently, even if they use row level locks), but the reason for current locking in your case, given the goals and the implementation, are clear and consistent. 

Manual may skip some detail or not provide proper explanation for some lock (as the code is complicated and takes different corner cases into account). It gets improved with time, though.

Nice.

The reason I filed this bug is that I could not figure out the reasoning behind this. All the manual, or some blog posts I read, only says the gap lock is there, to prevent shit happen, no one seems to mention the necessity of the gap (why is it this range safe, can it be smaller etc).

So let's be clear, when one tx has a `select * from t where c = 5 for update`, technically, putting aside how difficult or maybe even possible to implement for a moment, IS A 'gap lock' [5,5] GOOD ENOUGH for preventing shit to happen?

Secondly, if this is by design, I think the manual should be more specific about this. Instead of giving examples like `SELECT c1 FROM t WHERE c1 BETWEEN 10 and 20 FOR UPDATE`, which is easier to understand. I think what we are talking about here is more counter intuitive, and should be mentioned specifically.