MySQL gap lock reasoning

Question

I'm having a deadlock and I'm trying to figure out the reasoning behind it.

The question can be reduced to this:

table:

create table testdl (id int auto_increment, c int, primary key (id), key idx_c (c));

Isolation level is repeatable read

(Tx1): begin; delete from testdl where c = 1000; -- nothing is deleted coz the table is empty

(Tx2): begin; insert into testdl (c) values (?);

Whatever the value in Tx2 is, it hangs. So it basically means that Tx1 holds the gap of the whole range (-∞, +∞), when delete from testdl where c = 1000 fails to find a match, right?.

So my question is: is this by design? What's the point of this if it is?

Update:

Say we already have a record in testdl:

+----+------+
| id | c    |
+----+------+
|  1 | 1000 |
+----+------+

Case 1:

(Tx1): select * from testdl where c = 500 for update; -- c = 500 not exists

(TX2): insert into testdl (c) values (?);

In this case, any value >= 1000 can be inserted, so Tx1 locks the gap (-∞, 1000)

Again, is locking (-∞, 1000) necessary? What's the reasoning behind this?

Missi

you might want to check this out dev.mysql.com/doc/refman/5.7/en/innodb-locking.html – Neusatz

Yeah it says what is what but I still can't find a reason why the whole range is locked in this case while delete from testdl where c = 1000 doesn't find a match – Missi

See this question #23194261 – Neusatz

What would you propose as an alternative? There is not a (-∞, +∞) "range" in an empty table. As far as I know, here's a single zero-width gap between the infimum and supremum pseudo-records... and that single gap is locked. – Chard

@Michael-sqlbot What's confusing me is while a select * from testdl where c = 500 for update fails to match a record, I can't insert a record with c = 100. After all, I'm selected c = 500 for update, not c < 500. What would be wrong if inserting a record with c = 100 is allowed? Is there some reason for it? Or maybe is it just an implementation thing, nothing bad would actually happen? – Missi

Locking locks actual things, and there's no 500 "thing" available to be locked. There's only the gap between infimum and 1000. If you want to insert 500 and I want to insert 100, we are both vying for what is currently the same gap, so one of us needs to wait for the other. – Chard

@Michael-sqlbot sorry I don't see your point here. I mean if I'm select * from testdl where c > 500 for update, it makes sense to me that all concurrent writes with c > 500 should be forbidden until I'm done. But if I'm select * from testdl where c = 500 for update, what possible harm can it be if another transactions inserts a record with c = 100? – Missi

If another transaction inserts c = 100, it has to be inserted in exactly the same place where c = 500 would go -- both potential new rows need to go in exactly same place: the gap immediately preceding c = 1000. There is exactly one gap there, and the fact that you've locked the nonexistent 500 doesn't create two holes, one < 500 and one >= 500. It's still just one gap. The two transactions need the same thing, so one needs to wait. – Chard

Answer 1

This is similar to what I was curious myself recently so let me try to explain...

Whatever the value in Tx2 is, it hangs. So it basically means that Tx1 holds the gap of the whole range (-∞, +∞), when delete from testdl where c = 1000 fails to find a match, right?.

So my question is: is this by design? What's the point of this if it is?

This is by design, the main point of gap locks is to prevent any records inserts into these gaps to avoid phantom rows.

So, imagine you have your empty table and inside of a transaction you do delete from testdl where c = 1000;. Now, no matter how many such rows existed before you expect that after this query you have no such rows in your table, right? So, if after that you do select * from testdl where c = 1000 for update; in the same transaction you expect it to be an empty result.

But in order to make sure there are no new rows with c = 1000 inserted into the table we need to lock the gaps where such records can be inserted. And in an empty table there is only one gap: the gap between the infimum and supremum pseudo-records (as Michael pointed out).

In this case, any value >= 1000 can be inserted, so Tx1 locks the gap (-∞, 1000)

Again, is locking (-∞, 1000) necessary? What's the reasoning behind this?

I believe the above explanation should also explain the questions you ask about your second case when there is already one record in the table. But I'll try to explain it anyway.

In your first transaction you do select * from testdl where c = 500 for update; and now we need to make sure there are no new records with c = 500 appear if we decide to make such query again inside of this transaction. So we need to lock all the necessary gaps for it. Which gaps do we have? (-∞, 1000) and (1000, +∞), obviously new records where c = 500 won't be inserted into the second gap but they will be inserted into the first gap, so we have to lock it.

Hope this answers it.

Impair

It's been two years :) I'm aware of the phantom read thing. Let me put it this way, theoretically speaking all we need is to forbid the inserting of c=1000 right (in the first example) ? And if we forget about the 'you can't lock something not exist, locking is just some serialized access to some memory address' thing, this is more like an implementation thing(or choice, or that's the best we can do right now) right? – Missi

That only holds true if your column in the where clause is indexed, otherwise the clause is disregarded - innodb locks indexes not records. If you index c it will do a record lock and allow inserts/deletes/updates in the gap, otherwise it will do a next-key lock which is a record lock and a gap lock combined. – Modiste

@DeanWinchester Did you find the actual reason for this ? – Unmistakable

not really. but I tend to think it's an implementation thing. say when the table is empty, there's only -∞ and +∞. so that's all mysql has to lock. but it's just what I tell myself to justify what I saw, not necessarily the truth. – Missi

Answer 2

After executing

create table testdl (id int auto_increment, c int, primary key (id), key idx_c (c));

-- transaction 1
begin;
delete from testdl where c = 1000;

-- transaction 2
begin;
insert into testdl (c) values (?); -- ? can be any int

The output of select * from performance_schema.data_locks is:

+--------+----------------------------------------+-----------------------+-----------+----------+---------------+-------------+----------------+-------------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+
| ENGINE | ENGINE_LOCK_ID                         | ENGINE_TRANSACTION_ID | THREAD_ID | EVENT_ID | OBJECT_SCHEMA | OBJECT_NAME | PARTITION_NAME | SUBPARTITION_NAME | INDEX_NAME | OBJECT_INSTANCE_BEGIN | LOCK_TYPE | LOCK_MODE          | LOCK_STATUS | LOCK_DATA              |
+--------+----------------------------------------+-----------------------+-----------+----------+---------------+-------------+----------------+-------------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+
| INNODB | 140043377180024:1073:140043381454544   |                  2322 |        48 |      218 | test          | testdl      | NULL           | NULL              | NULL       |       140043381454544 | TABLE     | IX                 | GRANTED     | NULL                   |
| INNODB | 140043377180024:12:5:1:140043381451552 |                  2322 |        48 |      218 | test          | testdl      | NULL           | NULL              | idx_c      |       140043381451552 | RECORD    | X,INSERT_INTENTION | WAITING     | supremum pseudo-record |
| INNODB | 140043377180872:1073:140043381460688   |                  2321 |        49 |      154 | test          | testdl      | NULL           | NULL              | NULL       |       140043381460688 | TABLE     | IX                 | GRANTED     | NULL                   |
| INNODB | 140043377180872:12:5:1:140043381457776 |                  2321 |        49 |      154 | test          | testdl      | NULL           | NULL              | idx_c      |       140043381457776 | RECORD    | X                  | GRANTED     | supremum pseudo-record |
+--------+----------------------------------------+-----------------------+-----------+----------+---------------+-------------+----------------+-------------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+

transaction 2 is waiting to get insert intention lock (negative infinity, positive infinity) because transaction 1 is holding next-key lock (negative infinity, positive infinity), so it can't proceed.

But after executing

create table testdl (id int auto_increment, c int, primary key (id), key idx_c (c));
insert into testdl values(1, 1000);

-- transaction 1
begin;
select * from testdl where c = 500 for update;

The output of select * from performance_schema.data_locks is:

+--------+----------------------------------------+-----------------------+-----------+----------+---------------+-------------+----------------+-------------------+------------+-----------------------+-----------+-----------+-------------+-----------+
| ENGINE | ENGINE_LOCK_ID                         | ENGINE_TRANSACTION_ID | THREAD_ID | EVENT_ID | OBJECT_SCHEMA | OBJECT_NAME | PARTITION_NAME | SUBPARTITION_NAME | INDEX_NAME | OBJECT_INSTANCE_BEGIN | LOCK_TYPE | LOCK_MODE | LOCK_STATUS | LOCK_DATA |
+--------+----------------------------------------+-----------------------+-----------+----------+---------------+-------------+----------------+-------------------+------------+-----------------------+-----------+-----------+-------------+-----------+
| INNODB | 140043377180872:1074:140043381460688   |                  2341 |        49 |      167 | test          | testdl      | NULL           | NULL              | NULL       |       140043381460688 | TABLE     | IX        | GRANTED     | NULL      |
| INNODB | 140043377180872:13:5:2:140043381457776 |                  2341 |        49 |      167 | test          | testdl      | NULL           | NULL              | idx_c      |       140043381457776 | RECORD    | X,GAP     | GRANTED     | 1000, 1   |
+--------+----------------------------------------+-----------------------+-----------+----------+---------------+-------------+----------------+-------------------+------------+-----------------------+-----------+-----------+-------------+-----------+

transaction 1 is holding gap lock (negative infinity, (1000, 1)), so other transactions can't insert data into that gap.

Forby