MySQL Bugs: #29240: Falcon: duplicate-key error when there's no duplicate key

Bug #29240	Falcon: duplicate-key error when there's no duplicate key
Submitted:	20 Jun 2007 15:08	Modified:	7 Aug 2007 7:03
Reporter:	Peter Gulutzan	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Falcon storage engine	Severity:	S3 (Non-critical)
Version:	6.0.1-alpha-debug	OS:	Linux (SUSE 10 64-bit)
Assigned to:	Christopher Powers	CPU Architecture:	Any

Description:
I create a Falcon table with a unique column.
On one connection, I insert.
On a second connection, I try to insert the same value, and wait.
On the first connection, I try to insert again and fail.
On the first connection, I delete what I inserted.
On the first connection, I commit.
Now, on the second connection, I see an error message:
"ERROR 1582 (23000): Duplicate entry ..."
But at this point the table is empty so there is no duplicate.

How to repeat:
Use two mysql client connections. Call them T1 and T2.

On T1, say:
create table t1 (s1 int unique) engine=falcon;
set @@autocommit=0;
insert into t1 values (1);

On T2, say:
set @@autocommit=0;
insert into t1 values (1);

On T1, say:
insert into t1 values (1); /* fails */
delete from t1;
commit;

Look for this error message on T2:
ERROR 1582 (23000): Duplicate entry '1' for key 's1'

Thank you for the bug report. Verified on FC 6 32-bit.

T2>insert into t1 values (1);
ERROR 1582 (23000): Duplicate entry '1' for key 's1'
T2>

This problem appears to be related to BUG#22847 "Falcon: Unnecessary blockage for nulls."

Here is an overview of the transaction interactions:

1. Transaction A inserts record with unique index.
2. Transaction B inserts record with same index.
3. Transaction B block on Transaction A.

   checkUniqueIndex() determines that the record is being accessed by
   Transaction A and that the record is a duplicate.

3. Transaction A attempts insert of same record. Duplicate key error.
4. Transaction A deletes record.

At this point, Transaction A has 2 record versions:
   record version 1, the original inserted record, which is superceded by
   record version 2, the deleted record.

5. Transaction A commits.
8. Transaction B unblocks, still in checkUniqueIndexes().
9. Transaction B refetches the record.

Here the relative state of Transaction A is assessed to be CommittedButYounger.

Transaction A is now committed, however, Transaction A was active at the time
Transaction B began and is therefore determined to be not visible.

9. Although checkUniqueIndexes() found the committed, deleted record version, but continues looking for older committed records.
10.The prior (non-deleted) record version is examined and determined to be a
   duplicate, causing an error.

The problem is that checkUniqueIndexes() did not recognize the deleted record version is the first committed record and continued searching anyway.

This bit of logic in checkUniqueIndexes might be suspect:

    // May need to skip some record versions.
    if (transaction->isolationLevel == TRANSACTION_REPEATABLE_READ)
        {
        if (foundFirstCommitted && (state == CommittedButYounger))
            // Look for an older committed record, ignoring those inbetween.
            continue;

Should foundFirstCommitted should have been set to true, or should the test be
"if (foundFirstCommitted || CommittedButYounger)?".

This works, Scenario #1:

Transaction A inserts a record.
Transaction B inserts a duplicate record. Blocked until A commits.
Transaction A deletes the record.
Transaction A commits.
Transaction B unblocks, record is inserted.

This fails, Scenario #2:

Transaction A inserts a record.
Transaction B inserts a duplicate record. Blocked until A commits.
Transaction A inserts a duplicate record. Duplicate key error.
Transaction A deletes the record.
Transaction A commits.
Transaction B unblocks. Duplicate key error.

The difference is that after unblocking, Transaction B sees only the 'delete' record version Scenario #1, but sees two record versions in Scenario #2. The duplicate key error is triggered by an older record version with a duplicate key.

Details:

With autocommit off, an internal savepoint is created for each operation. New record versions within a transaction are assigned to the current savepoint and the savepoint id is advanced by one.

After the operation, older record verions are scavenged according to savepoint id, and removed from the transaction if possible.

The failed insert on Transaction A advances the savepoint id. Because of the error, there is no corresponding scavenge and the new record version is abandonded.

At the time of commit in Scenario #2, the record version chain looks like this:

Record Version: v2 v1
Transaction: A A
Operation: DELETE INSERT
Savepoint: 2 0
Key Value: 1 1

Note that record version v1 was not scavenged because its savepoint id was too low.

When Transaction A commits, Transaction B unblocks and resumes its check for duplicates. Although checkUniqueIndexes() sees the deleted and commited record version, it continues looking for duplicates anyway and throws an error when it encounters the older record version (v1).

In this case, changes applied in Transaction A should not visible to Transaction B, however, the check for duplicates against 'invisible' record versions is intentional. From WL#3523 "Repeatable Read Isolation in Falcon":

"The third type of update conflict is when a Consistent Read transaction attempts to create a key value that is the same as an older, but still visible record version. Even though a newer key value has been committed by a concurrent transaction, the Consistent Read transaction does not see it. Instead, it sees the old value. If this transaction tried to make another record with this value, it would 'appear' as if there are duplicates in a unique index. So this also, is not allowed in the Falcon storage engine."

So, the two questions that remain are:

1. Should the older record version (v1 above) have been scavenged, and does it really matter if it wasn't?

2. Should checkUniqueIndexes() have abandoned the duplicate key search when it encountered a deleted and committed record version?

The testcase passes with isolation level READ COMMITTED, as expected.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/29907

ChangeSet@1.2575, 2007-06-28 16:36:15-05:00, chris@terrazzo.site +2 -0
  Bug#29240, "Falcon: duplicate-key error"
  
  Adjusted logic in Table::checkUniqueIndexes() to ignore older record
  versions once a deleted but committed record version is detected.

Added test case falcon_bug_29240.test which passes now.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/31611

ChangeSet@1.2662, 2007-07-26 14:30:05+02:00, hakank@au0012.local +2 -0
  Added test for Bug#29240.

A note has been added to the 6.0.1 changelog: 

Falcon could occasionally report a problem with a duplicate key error during INSERT when inserting the same data into a unique column on two or more connections simultaneously.