Bug #43452 Wrong number of rows returned when using LIMIT
Submitted: 6 Mar 2009 13:08 Modified: 15 May 2009 17:05
Reporter: Lars-Erik Bjørk Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Falcon storage engine Severity:S3 (Non-critical)
Version:6.0.10 OS:Any
Assigned to: Lars-Erik Bjørk CPU Architecture:Any
Tags: F_LIMIT

[6 Mar 2009 13:08] Lars-Erik Bjørk 
Description:
We have a table with a single indexed integer column, created like this:

CREATE TABLE t1 (int_key INTEGER, KEY (int_key))  ENGINE=falcon;

We insert two rows and update both rows to have the same value:

INSERT INTO t1 VALUES (8), (1);
UPDATE t1 SET int_key = 3;

The we search for all values below eight without using LIMIT. This way, the comparison is done by the server:

SELECT * FROM t1 WHERE int_key < 8;

This will always return two rows.

The we use LIMIT to push down the comparison to Falcon

SELECT * FROM t1 WHERE int_key < 8 ORDER BY int_key LIMIT 4;

Depending on the timing, this will return only one row

How to repeat:
See above
[6 Mar 2009 13:15] Lars-Erik Bjørk 
This is what is happening:

In a transient period, we have both the old and the new values available when walking the index. The order they are traversed is the following:    (notation  (recNumber, indexValue)  )

(1,1) (0,3) (1,3) (0,8)

We check the first value in IndexWalker::getValidatedRecord and see that the index value (1) does not match the record value (3), therefore we skip it. At the next iteration we check the next entry. We check that this is not the same record as the on the last iteration by comparing the record number to a variable called lastRecordNumber. This value is initialized to 0, and has not yet been updated because we skipped the previous entry. Therefore we mistakingly think we have processed this record already and skip it. We therefore loose the first record in the table.

The solution to this is not to initialize lastRecordNumber to 0, which is a legal record number, but to initialize it to a negative, illegal record number.
[6 Mar 2009 13:51] Bugs System 
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/68502

3054 lars-erik.bjork@sun.com	2009-03-06
      This is a patch for bug#43452 Wrong number of rows returned when using LIMIT
      
      In a transient period, we have both the old and the new values available when walking the
      index. The order they are traversed is the following:    (notation  (recNumber,
      indexValue)  )
      
      (1,1) (0,3) (1,3) (0,8)
      
      We check the first value in IndexWalker::getValidatedRecord and see that the index value
      (1) does not match the record value (3), therefore we skip it. At the next iteration we
      check the next entry. We check that this is not the same record as the on the last
      iteration by comparing the record number to a variable called lastRecordNumber. This value
      is initialized to 0, and has not yet been updated because we skipped the previous entry.
      Therefore we mistakingly think we have processed this record already and skip it. We
      therefore loose the first record in the table.
      
      The solution to this is not to initialize lastRecordNumber to 0, which is a legal record
      number, but to initialize it to a negative, illegal record number.
      
      Added file 'mysql-test/suite/falcon/t/falcon_bug_43452.test'
      ------------------------------------------------------------
      A test testing the patch
      
      Added file 'mysql-test/suite/falcon/r/falcon_bug_43452.result'
      -------------------------------------------------------------
      Expected result of the test
      
      Modified file 'storage/falcon/IndexWalker.cpp'
      ----------------------------------------------
      Initialize lastRecordNumber to a negative value
[6 Mar 2009 13:53] Bugs System 
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/68503

3054 lars-erik.bjork@sun.com	2009-03-06
      This is a patch for bug#43452 Wrong number of rows returned when using LIMIT
      
      In a transient period, we have both the old and the new values available when walking the
      index. The order they are traversed is the following:    (notation  (recNumber,
      indexValue)  )
      
      (1,1) (0,3) (1,3) (0,8)
      
      We check the first value in IndexWalker::getValidatedRecord and see that the index value
      (1) does not match the record value (3), therefore we skip it. At the next iteration we
      check the next entry. We check that this is not the same record as the on the last
      iteration by comparing the record number to a variable called lastRecordNumber. This value
      is initialized to 0, and has not yet been updated because we skipped the previous entry.
      Therefore we mistakingly think we have processed this record already and skip it. We
      therefore loose the first record in the table.
      
      The solution to this is not to initialize lastRecordNumber to 0, which is a legal record
      number, but to initialize it to a negative, illegal record number.
      
      Added file 'mysql-test/suite/falcon/t/falcon_bug_43452.test'
      ------------------------------------------------------------
      A test testing the patch
      
      Added file 'mysql-test/suite/falcon/r/falcon_bug_43452.result'
      -------------------------------------------------------------
      Expected result of the test
      
      Modified file 'storage/falcon/IndexWalker.cpp'
      ----------------------------------------------
      Initialize lastRecordNumber to a negative value
[6 Mar 2009 14:03] Bugs System 
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/68505

3054 lars-erik.bjork@sun.com	2009-03-06
      This is a patch for bug#43452 Wrong number of rows returned when using LIMIT
      
      In a transient period, we have both the old and the new values available when walking the
      index. The order they are traversed is the following:    (notation  (recNumber,
      indexValue)  )
      
      (1,1) (0,3) (1,3) (0,8)
      
      We check the first value in IndexWalker::getValidatedRecord and see that the index value
      (1) does not match the record value (3), therefore we skip it. At the next iteration we
      check the next entry. We check that this is not the same record as the on the last
      iteration by comparing the record number to a variable called lastRecordNumber. This value
      is initialized to 0, and has not yet been updated because we skipped the previous entry.
      Therefore we mistakingly think we have processed this record already and skip it. We
      therefore loose the first record in the table.
      
      The solution to this is not to initialize lastRecordNumber to 0, which is a legal record
      number, but to initialize it to a negative, illegal record number.
      
      Added file 'mysql-test/suite/falcon/t/falcon_bug_43452.test'
      ------------------------------------------------------------
      A test testing the patch
      
      Added file 'mysql-test/suite/falcon/r/falcon_bug_43452.result'
      -------------------------------------------------------------
      Expected result of the test
      
      Modified file 'storage/falcon/IndexWalker.cpp'
      ----------------------------------------------
      Initialize lastRecordNumber to a negative value
[7 Mar 2009 7:52] Bugs System 
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/68576

3055 lars-erik.bjork@sun.com	2009-03-07
      This is a patch for bug#43452 Wrong number of rows returned when using LIMIT
      
      In a transient period, we have both the old and the new values available when walking the
      index. The order they are traversed is the following:    (notation  (recNumber,
      indexValue)  )
      
      (1,1) (0,3) (1,3) (0,8)
      
      We check the first value in IndexWalker::getValidatedRecord and see that the index value
      (1) does not match the record value (3), therefore we skip it. At the next iteration we
      check the next entry. We check that this is not the same record as the on the last
      iteration by comparing the record number to a variable called lastRecordNumber. This value
      is initialized to 0, and has not yet been updated because we skipped the previous entry.
      Therefore we mistakingly think we have processed this record already and skip it. We
      therefore loose the first record in the table.
      
      The solution to this is not to initialize lastRecordNumber to 0, which is a legal record
      number, but to initialize it to a negative, illegal record number.
      
      Added file 'mysql-test/suite/falcon/t/falcon_bug_43452.test'
      ------------------------------------------------------------
      A test testing the patch
      
      Added file 'mysql-test/suite/falcon/r/falcon_bug_43452.result'
      -------------------------------------------------------------
      Expected result of the test
      
      Modified file 'storage/falcon/IndexWalker.cpp'
      ----------------------------------------------
      Initialize lastRecordNumber to a negative value
[2 Apr 2009 17:39] Bugs System 
Pushed into 6.0.11-alpha (revid:hky@sun.com-20090402144811-yc5kp8g0rjnhz7vy) (version source revid:lars-erik.bjork@sun.com-20090307075129-kfuj2ueaxm24qrhm) (merge vers: 6.0.11-alpha) (pib:6)
[15 May 2009 17:05] MC Brown 
A note has been added to the 6.0.11 changelog: 

When performing SELECT statements on a Falcon table using an indexed INTEGER column could return incorrect row matches.