Bug #25847 Add predicate locking to avoid deadlocks due to locking non-existent rows
Submitted: 25 Jan 2007 14:06 Modified: 25 Jan 2007 14:49
Reporter: Mark Leith Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: InnoDB storage engine Severity:S4 (Feature request)
Version:5.0.32 OS:Any (Any)
Assigned to: Assigned Account CPU Architecture:Any
Tags: deadlock, innodb, lock, select for update
Triage: Triaged: D5 (Feature request)

[25 Jan 2007 14:06] Mark Leith
Description:
Using "SELECT ... FOR UPDATE" against a row that does not exist, then trying to INSERT, all within a single transaction, causes deadlocks (likely because the SELECT ... FOR UPDATE is holding the supremum record?). 

The semantics of the transaction should not result within deadlocks however. 

Also uploading C testcase which reproduces this within 1 second of running. 

How to repeat:
Run the following transaction within 2 threads concurrently:

/* setup */

DROP TABLE IF EXISTS csc13829;
CREATE TABLE csc13829 (i INT AUTO_INCREMENT PRIMARY KEY, j INT, k INT) ENGINE = InnoDB;

/* Within each thread */

START TRANSACTION;
SELECT i FROM csc13829 WHERE i = 1000000000 FOR UPDATE;
INSERT INTO csc13829 (j, k) VALUES (10,10);
COMMIT;

Suggested fix:
Do not hold the supremum record (if this is the issue) if the rows are found to be non-existant.
[25 Jan 2007 14:07] Mark Leith
Deadlock test case

Attachment: csc13829.c (text/plain), 5.04 KiB.

[25 Jan 2007 14:37] Heikki Tuuri
Mark,

on the default isolation level REPEATABLE READ, it makes sense to lock also the 'supremum' record of the index page. We must make sure that no one can insert a row with i = 1000000000. The only way to ensure that in InnoDB is to lock the 'supremum' record. InnoDB does not have 'predicate locking', which would allow us to lock just the non-existent record i = 1000000000.

row0sel.c in 5.0:

        if (page_rec_is_supremum(rec)) {

                if (set_also_gap_locks
                    && !srv_locks_unsafe_for_binlog
                    && prebuilt->select_lock_type != LOCK_NONE) {

                        /* Try to place a lock on the index record */

                        /* If innodb_locks_unsafe_for_binlog option is used,
                        we do not lock gaps. Supremum record is really
                        a gap and therefore we do not set locks there. */

                        offsets = rec_get_offsets(rec, index, offsets,
                                        ULINT_UNDEFINED, &heap);
                        err = sel_set_rec_lock(rec, index, offsets,
                                        prebuilt->select_lock_type,
                                        LOCK_ORDINARY, thr);

                        if (err != DB_SUCCESS) {

                                goto lock_wait_or_error;
                        }
                }
                /* A page supremum record cannot be in the result set: skip
                it now that we have placed a possible lock on it */

                goto next_rec;
        }

Workarounds: use innodb_locks_unsafe_for_binlog in 5.0 (read the caveats), or use the isolation level READ COMMITTED in 5.1 when you do the SELECT ...FOR UPDATE.

Regards,

Heikki
[25 Jan 2007 14:49] Mark Leith
Hi Heikki,

Thanks for the explanation!

I've now altered the synopsis, and added this as a feature request ;)

Cheers,

Mark
[31 Mar 2010 12:20] Mark Leith
Bug#48911 was marked as a duplicate of this one.
[22 Apr 2010 23:38] Andras Gyomrey
Don't know about multiple column primary key handling, but this also fails to lock one session until the other ends:

SESSION1: SET AUTOCOMMIT=0;
SESSION1: DROP TABLE IF EXISTS tdl;
SESSION1: CREATE TABLE tdl (i INT, j INT, PRIMARY KEY (i, j)) ENGINE = InnoDB;
SESSION1: SELECT * FROM tdl WHERE i=1 AND j=1 FOR UPDATE;
SESSION2: SET AUTOCOMMIT=0;
SESSION2: SELECT * FROM tdl WHERE i=1 AND j=1 FOR UPDATE;

The second session doesn't wait till the first has commited changes.
[29 May 2010 14:55] Andras Gyomrey
I followed Heikki's workarounds:

Workarounds: use innodb_locks_unsafe_for_binlog in 5.0 (read the caveats), or use the
isolation level READ COMMITTED in 5.1 when you do the SELECT ...FOR UPDATE.

But none of them were successful with my previous example :(. Is there any other option?
[5 May 2011 17:23] Sveta Smirnova
Bug #61026 was marked as duplicate of this one.
[19 Oct 2011 18:49] Doris Hung
The same issue is reproducible on mysql 5.1.56.  Is there a fix for this in later versions?
[19 Oct 2011 18:49] Doris Hung
The same issue is reproducible on mysql 5.1.56.  Is there a fix for this in later versions?
[14 Nov 2011 17:19] Jason Woods
Uploaded by Jason to show inconsistency

Attachment: MySQLBug25847_Scenarios.txt (text/plain), 6.35 KiB.

[14 Nov 2011 17:20] Jason Woods
Hi all,

This is quote frustrating and absolutely inconsistent.
I've attached a text file showing three scenarios for testing that show different results depending on where the target record WOULD appear in the index should it have existed.

So no matter what way one looks at it, there is an inconsistency in the way this is handled as the three scenarios should all have the same result - this is what one would expect anyways. If I'm wrong, please do educate me lol as I really do want to understand this!

There are two ways to look at this.

***** First:
Nonexistent rows are treated in the same way as existent rows when it comes to FOR UPDATE.
The lock on suprenum (or the other etc) is the correct way, and MySQL should also be locking the gap index in the case the target ID is NOT at the beginning or end of the index. This lock is exclusive so another transaction should have to wait for this lock to be released before they can access the table.
This would being all 3 scenarios in line to act the same.
Now, the point the lock is released and the second transaction gains it... FOR UPDATE is supposed to work on the latest version of the row only. If we return 0 rows (would we? I don't know) this is surely wrong as this is not the latest version - the latest version is the one inserted by the last query, so potentially we then need to try an X lock on that row (if it was inserted) and afterwards release the X on the suprenum or otherwise. Complicated? Don't know but seems it would be beneficial and prevent all the deadlock annoyance with FOR UPDATE then INSERTs and not break anything.

***** Second:
Nonexistent rows are treated different to actual rows, and FOR UPDATE should be documented that it does absolutely nothing if there is no rows found (I don't think it is currently.)
This means the suprenum and that other lock should never happen. And this means duplicate key error will always happen when you FOR UPDATE and then INSERT concurrently as this is documented to be an absolutely wrong way to go about it.
But if this is the chosen case - then we have no simple way to INSERT a row if it does not exist and run this concurrently with other threads. We'd have to use a kind of semaphore table to make the INSERT serialised (which we are actually doing at the moment!) or start the transaction with an INSERT IGNORE and then SELECT FOR UPDATE it - but this makes every transaction contain INSERT then SELECT when really this is not ideal, we should be able to SELECT and if it doesn't exist INSERT and do this safely.

Just my two cents and hopefully somebody can offer a path to realise one of these and update documentation.

Thanks

Jason.