MySQL Bugs: #43630: A SELECT using ORDER BY and LIMIT sometimes returns no rows

Bug #43630	A SELECT using ORDER BY and LIMIT sometimes returns no rows
Submitted:	13 Mar 2009 11:31	Modified:	22 Oct 2009 10:35
Reporter:	Lars-Erik BjÃ¸rk	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Falcon storage engine	Severity:	S2 (Serious)
Version:	falcon-team	OS:	Any
Assigned to:	Lars-Erik BjÃ¸rk	CPU Architecture:	Any
Tags:	F_LIMIT

Description:
This bug is filed as a part of the investigation of "umbrella" bug#42915 

When running a modified version of falcon_nolimit_int.yy, the test will almost always fail with falcon returning 0 rows when using LIMIT, even though rows are returned when LIMIT is not used. 

The modified version of falcon_limit_int.yy looks like this:

query:
        select | dml | dml | dml | dml | dml ;

dml:
        update ;

select:
        SELECT * FROM _table where;

where:
        |
        WHERE _field sign value ;

sign:
        < ;

insert:
        INSERT INTO _table ( _field , _field ) VALUES ( value , value ) ;

update:
        UPDATE _table AS X SET _field = value where ;

value:
        _digit | _tinyint_unsigned ;

# Use only indexed fields:

_field:
        `int_key` ;

_table
        `E` ;

The test can be run with the following command from the gentest directory, given you have branched the mysql-test-extra-6.0 tree:

perl runall.pl \
--basedir=<path_to_your_basedir> \
--mysqld=--loose-innodb-lock-wait-timeout=1 \
--mysqld=--table-lock-wait-timeout=1 \
--mysqld=--loose-falcon-lock-wait-timeout=1 \
--mysqld=--loose-falcon-debug-mask=2 \
--mysqld=--skip-safemalloc \
--grammar=conf/falcon_nolimit_int.yy \
--threads=1 --validator=Limit \ --reporters=Deadlock,ErrorLog,Backtrace,WinPackage \
--duration=1200 \
--vardir=/tmp/vardir \
--mysqld=--log-output=file \
--queries=100000 \
--engine=falcon

How to repeat:
See above

There seems to be at least two cases that leads to no rows (or too few rows) being returned:

The first case is that the walker logic does not handle if an index page is empty. In loads with lots of updates, we may get empty pages. When walking the index we will stop at the first empty index page, even though this is not the end of the level. In this test, this has often been the first page, resulting in no rows returned. In other cases, when it is not the first page, it has lead to some rows returned, but not all.

It also seems that we sometimes compare the wrong keys. We have a local copy of an index entry's key that we compare to the actual record to see if the key matches the record. It seems that in some circumstances we forget to update the local copy of the key and therefore compare the wrong keys. In this case, all the rows for the indexed field has been set to the same value. If we fail to update the local copy for the first of the index entries for these, we will also fail to do it for the rest of the keys due to the prefix compression. I have not yet figured out under what circumstances we fail to do this.

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/73707

2701 lars-erik.bjork@sun.com	2009-05-09
      This is one of at least two patches for bug#43630 
      'A SELECT using ORDER BY and LIMIT sometimes returns no rows'
      
      The index walker logic does not handle if an index page is empty. In
      loads with lots of updates, we may get empty pages. When walking the
      index we will stop at the first empty index page, even though this is
      not the end of the level. In this test, this has often been the first
      page, resulting in no rows returned.
      
      This patch makes the search proceed to the next page when an empty
      index page that is not the end of the level is encountered.
      
      === modified file 'storage/falcon/WalkIndex.cpp'
      WalkIndex::getNextNode has been changed to reposition the index to the
      next page when an index page with BUCKET_END as it first node is
      encountered.
      modified:
        storage/falcon/WalkIndex.cpp

Putting back to 'In progress' as the previous patch was only one of at least two patches for this bug

When we look at the first index entry of a page, the following piece of code is executed:

for (;; first = true)
	{
	if (first)
		{
		first = false;
		recordNumber = node.getNumber();
		
		if (recordNumber >= 0)
			{
			return recordNumber;
			}

We return the recordNumber without setting up indexKey to reflect the first index entry on the page. This will only work in two scenarioes:

1: If the key value of the END_BUCKET node on the previous page is the same as the key value of the first index node on the current page

2: If this is the first page we look at during the search

With a lot of UPDATE/DELETE statements, the prerequisites for scenario 1 to be correct, may easily be broken, and we will get wrong results.

The fix is to call node.expandKey(&indexKey) if this is the first node on the page. This is however not necessary if it is the first page we look at during the search, as this has already been done in IndexRootPage::positionIndex

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/74886

2712 lars-erik.bjork@sun.com	2009-05-25
      This is the second of two patches for bug#43630
      A SELECT using ORDER BY and LIMIT sometimes returns no rows
      
      When we look at the first index entry of a page, the following piece of code is executed:
      
      for (;; first = true)
      	{
      	if (first)
      		{
      		first = false;
      		recordNumber = node.getNumber();
      		
      		if (recordNumber >= 0)
      			{
      			return recordNumber;
      			}
      
      We return the recordNumber without setting up indexKey to reflect the first index entry on
      the page. This will only work in two scenarioes:
      
      1: If the key value of the END_BUCKET node on the previous page is the same as the key
      value of the first index node on the current page
      
      2: If this is the first page we look at during the search
      
      With a lot of UPDATE/DELETE statements, the prerequisites for scenario 1 to be correct,
      may easily be broken, and we will get wrong results.
      
      The fix is to call node.expandKey(&indexKey) if this is the first node on the page. This
      is however not necessary if it is the first page we look at during the search, as this has
      already been done in IndexRootPage::positionIndex
      modified:
        storage/falcon/WalkIndex.cpp
        storage/falcon/WalkIndex.h

The second patch looks OK to expand the first node in a page when walking the index from one page to the next.

A Falcon bug, closing since no documentation entry is necessary (a bug in a feature tree).