MySQL Bugs: #42208: Falcon's ORDER BY ..LIMIT gives wrong/inconsistent results on NULL values

Bug #42208	Falcon's ORDER BY ..LIMIT gives wrong/inconsistent results on NULL values
Submitted:	20 Jan 2009 8:10	Modified:	15 May 2009 15:49
Reporter:	Nidhi Shrotriya	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Falcon storage engine	Severity:	S3 (Non-critical)
Version:	6.0.8-alpha	OS:	Linux
Assigned to:	Lars-Erik BjÃ¸rk	CPU Architecture:	Any
Tags:	F_LIMIT

Description:
ORDER BY <columns> LIMIT <small no> produces different results in 'Falcon'than with other Storage engines as MyISAM, Innodb, Maria if the column in sort order includes NULL values.

These results are also not consistent with Falcon's -
-ORDER BY <columns> 
-ORDER BY <columns> LIMIT <maxrows>

The above 2 seem to produce correct and same results as other SEs.

All other SEs produces same results and consistent with the above 2 for NULL values too.

How to repeat:
mysql> create table myisam1(c1 tinyint unsigned null, c2 tinyint, c3 bigint, index idx(c2,c3));
Query OK, 0 rows affected (0.14 sec)

Create table falcon1 with same definition with engine=falcon.
Insert some rows to both tables as below.

mysql> select * from myisam1 order by c2,c3;
+------+------+------+
| c1   | c2   | c3   |
+------+------+------+
|    0 | NULL |   26 |
|    0 | NULL |  106 |
|    0 | -128 |   11 |
|    0 |    0 |   26 |
|    0 |    1 |    2 |
|    0 |  126 |   26 |
+------+------+------+
6 rows in set (0.00 sec)

mysql> select * from falcon1 order by c2,c3;
+----+------+------+
| c1 | c2   | c3   |
+----+------+------+
|  0 | NULL |   26 |
|  0 | NULL |  106 |
|  0 | -128 |   11 |
|  0 |    0 |   26 |
|  0 |    1 |    2 |
|  0 |  126 |   26 |
+----+------+------+
6 rows in set (0.00 sec)

mysql> select * from myisam1 order by c2,c3 LIMIT 4;
+------+------+------+
| c1   | c2   | c3   |
+------+------+------+
|    0 | NULL |   26 |
|    0 | NULL |  106 |
|    0 | -128 |   11 |
|    0 |    0 |   26 |
+------+------+------+
4 rows in set (0.00 sec)

mysql> select * from falcon1 order by c2,c3 LIMIT 4;
+----+------+------+
| c1 | c2   | c3   |
+----+------+------+
|  0 | -128 |   11 |
|  0 | NULL |   26 |
|  0 |    0 |   26 |
|  0 | NULL |  106 |
+----+------+------+
4 rows in set (0.00 sec)

mysql> select * from myisam1 order by c2,c3 LIMIT 6;
+------+------+------+
| c1   | c2   | c3   |
+------+------+------+
|    0 | NULL |   26 |
|    0 | NULL |  106 |
|    0 | -128 |   11 |
|    0 |    0 |   26 |
|    0 |    1 |    2 |
|    0 |  126 |   26 |
+------+------+------+
6 rows in set (0.00 sec)

mysql> select * from falcon1  order by c2,c3 LIMIT 6;
+----+------+------+
| c1 | c2   | c3   |
+----+------+------+
|  0 | NULL |   26 |
|  0 | NULL |  106 |
|  0 | -128 |   11 |
|  0 |    0 |   26 |
|  0 |    1 |    2 |
|  0 |  126 |   26 |
+----+------+------+
6 rows in set (0.00 sec)

Thank you for the bug report. Verified as described.

drop table if exists myisam1;
drop table if exists falcon1;
create table myisam1(c1 tinyint unsigned null, c2 tinyint, c3 bigint, index
idx(c2,c3)) engine MyISAM;
create table falcon1(c1 tinyint unsigned null, c2 tinyint, c3 bigint, index
idx(c2,c3)) engine Falcon;
insert into myisam1 (c1,c2,c3) values (0,NULL,26),(0,NULL,106),(0,-128,11);
insert into myisam1 (c1,c2,c3) values (0,0,26),(0,1,2),(0,126,26);
insert into falcon1 (c1,c2,c3) values (0,NULL,26),(0,NULL,106),(0,-128,11);
insert into falcon1 (c1,c2,c3) values (0,0,26),(0,1,2),(0,126,26);
select * from myisam1 order by c2,c3;
select * from falcon1 order by c2,c3;
select * from myisam1 order by c2,c3 LIMIT 4;
select * from falcon1 order by c2,c3 LIMIT 4;
select * from myisam1 order by c2,c3 LIMIT 6;
select * from falcon1  order by c2,c3 LIMIT 6;

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

3025 lars-erik.bjork@sun.com	2009-02-16
      This is a patch for bug#42208 (Falcon's ORDER BY ..LIMIT gives
      wrong/inconsistent results on NULL values)
      
      The reason for this bug is that NULL values in Falcon sort together
      with numeric zero. This is wrong as the default behavior should be
      for NULLs to sort before every other value. In order to achieve this,
      keys for NULL values now have a keyLength of zero. This will make them
      sort together with the keys for the empty string. One possible way to
      differentiate these two would be to prepend 0x00 to every key starting
      in 0x00. This would cause extra work during key creation, a critical
      path in the system. Because the empty string value occurs relatively
      infrequently I have worked around this (as suggested by Jim), by
      caching the record numbers for records with these values that has a
      single field index on the field. This is done when traversing the
      index using the IndexWalker. This logic is implemented in 
      WalkIndex::getNext() and WalkDeferred::getNext()
      
      modified file 'storage/falcon/Index.cpp'
      ---------------------------------------------------------------
      When creating a key for the NULL value, the keyLength will now be
      zero. Also removed some code by Vlad, to make this and the change in
      StorageDatabase.cpp work.
      
      modified file 'storage/falcon/IndexWalker.cpp'
      ---------------------------------------------------------------
      Added a new method called examineKey() that takes a Record and an
      IndexKey and checks if this key is for a NULL value, the empty
      string ("") or a regular value. Return an enum that is also defined
      within the scope of the IndexWalker class (and sub classes). Added 
      some protected member variables used to keep track of the state of 
      the caching when traversing the index. Updated getValidatedRecord()
      to cope with the fact that it is receiving cached record numbers 
      (record numbers that it has already processed).
      
      modified file 'storage/falcon/IndexWalker.h'
      ---------------------------------------------------------------
      New member variables and method signature
      
      modified file 'storage/falcon/StorageDatabase.cpp'
      ---------------------------------------------------------------
      We no longer stop building a multi segment index key when reaching
      a NULL value. This is done in order to also sort correctly on fields
      after the NULL value.
      
      modified file 'storage/falcon/WalkDeferred.cpp' and
      modified file 'storage/falcon/WalkIndex.cpp'
      ---------------------------------------------------------------
      Changed the getNext method to cache record numbers for keys for
      the empty string value. Quite some code is added to do this 
      nicely, but most it will only be triggered if we encounter keys
      for empty strings (which should happen quite rarely).
      The cache is only allocated if such a key is encountered and it
      is created with a small initial value (can contain 32 record numbers)
      and is increased by the same value if the cache is filled. The value
      of 32 is an educated (read random) guess.
      
      A lot of this code was duplicated in WalkIndex::getNext() and
      WalkDeferred::getNext()
      
      added file 'mysql-test/suite/falcon/t/falcon_bug_42208.test'
      ---------------------------------------------------------------
      Test file testing the patch
      
      added file 'mysql-test/suite/falcon/r/falcon_bug_42208.result'
      ---------------------------------------------------------------
      Expected result for the test

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

3033 lars-erik.bjork@sun.com	2009-02-23
      This is a patch for bug#42208 (Falcon's ORDER BY ..LIMIT gives
      wrong/inconsistent results on NULL values)
            
      The reason for this bug is that NULL values in Falcon sort together
      with numeric zero. This is wrong as the default behavior should be
      for NULLs to sort before every other value. In order to achieve this,
      keys for NULL values now have a keyLength of zero. This will make them
      sort together with the keys for the empty string.
      
      To preserve the sorting order, 0x00 is prepended to all empty keys
      and keys starting with 0x00. This will make NULL sort below everything.

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

3097 Vladislav Vaintroub	2009-04-06
      Bug#42208 Falcon's ORDER BY ..LIMIT gives wrong/inconsistent results on NULL values 
      Bug#42405 Missing/Wrong rows on Falcon's ORDER BY ..LIMIT with range access on pk/index 
      
      This patch introduces new Falcon index version.
      
      It changes handling of multisegment keys, so binary keys that 
      differ in number of trailing zeros bytes are now considered different.
      
      Also, NULL in index is now different from 0, empty string 
      (0x00) and zero length string and sorts according to SQL
      standard rules, less than any other value.
      (incorporated changes from Lars-Erik for Bug#42208)
      
      INDEX_CURRENT_VERSION is now 2. Minor ODS version is increased to 5.
     @ mysql-test/suite/falcon/r/falcon_bug_42208.result
        test for bug 42208
     @ mysql-test/suite/falcon/r/falcon_index_v2.result
        test for correct sorting order of multisegment keys,
        NULLs and zero length keys
     @ mysql-test/suite/falcon/t/falcon_bug_42208.test
        test for bug 42208
     @ mysql-test/suite/falcon/t/falcon_index_v2.test
        test for correct sorting order of multisegment keys,
        NULLs and zero length keys
     @ storage/falcon/Database.h
        Increase ODS version (new index format)
     @ storage/falcon/Index.cpp
        Increase ODS version (new index format)
     @ storage/falcon/Index.h
        Increase index version
     @ storage/falcon/StorageDatabase.cpp
        Use all keys provided by optimizer, do not break at NULLs
        (but not for index version 1, where NULL is broken)

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

3097 Vladislav Vaintroub	2009-04-06
      Bug#42208 Falcon's ORDER BY ..LIMIT gives wrong/inconsistent results on NULL values 
      
      
      This patch introduces new Falcon index version.
      
      It changes handling of multisegment keys, so binary keys that 
      differ in number of trailing zeros bytes are now considered different.
      
      Also, NULL in index is now different from 0, empty string 
      (0x00) and zero length string and sorts according to SQL
      standard rules, less than any other value.
      (incorporated changes from Lars-Erik for Bug#42208)
      
      INDEX_CURRENT_VERSION is now 2. Minor ODS version is increased to 5.
     @ mysql-test/suite/falcon/r/falcon_bug_42208.result
        test for bug 42208
     @ mysql-test/suite/falcon/r/falcon_index_v2.result
        test for correct sorting order of multisegment keys,
        NULLs and zero length keys
     @ mysql-test/suite/falcon/t/falcon_bug_42208.test
        test for bug 42208
     @ mysql-test/suite/falcon/t/falcon_index_v2.test
        test for correct sorting order of multisegment keys,
        NULLs and zero length keys
     @ storage/falcon/Database.h
        Increase ODS version (new index format)
     @ storage/falcon/Index.cpp
        Increase ODS version (new index format)
     @ storage/falcon/Index.h
        Increase index version
     @ storage/falcon/StorageDatabase.cpp
        Use all keys provided by optimizer, do not break at NULLs
        (but not for index version 1, where NULL is broken)

Pushed into 6.0.11-alpha (revid:hky@sun.com-20090415164923-9arx29ye5pzxd4zf) (version source revid:vvaintroub@mysql.com-20090406114449-g655t39h8511iakq) (merge vers: 6.0.11-alpha) (pib:6)

An entry has been added to the 6.0.11 changelog: 

Using ORDER BY and or LIMIT on Falcon tables could give inconsistent results for rows that contain NULL columns in the corresponding ORDER BY clause