#At file:///home/lb200670/mysql/42208_B/ based on revid:lars-erik.bjork@stripped
3033 lars-erik.bjork@stripped 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.
added:
mysql-test/suite/falcon/r/falcon_bug_42208.result
mysql-test/suite/falcon/t/falcon_bug_42208.test
modified:
storage/falcon/Index.cpp
storage/falcon/StorageDatabase.cpp
per-file messages:
mysql-test/suite/falcon/r/falcon_bug_42208.result
Expected output from the test
mysql-test/suite/falcon/t/falcon_bug_42208.test
Test file testing the patch
storage/falcon/Index.cpp
Index keys for the NULL value will now have length 0.
Prepend 0x00 to empty keys, and keys starting with 0x00
This is done to distinguish Null from empty keys, and to
preserve the original sorting sequence.
Remove a small optimization from Vlad, that will no longer work.
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.
=== added file 'mysql-test/suite/falcon/r/falcon_bug_42208.result'
--- a/mysql-test/suite/falcon/r/falcon_bug_42208.result 1970-01-01 00:00:00 +0000
+++ b/mysql-test/suite/falcon/r/falcon_bug_42208.result 2009-02-23 11:49:41 +0000
@@ -0,0 +1,514 @@
+*** Bug #42208 ***
+SET @@storage_engine = 'Falcon';
+DROP TABLE IF EXISTS t1;
+CREATE TABLE t1(c1 tinyint unsigned null, c2 tinyint, c3 bigint, index idx(c2,c3));
+INSERT INTO t1 (c1,c2,c3) values (0,NULL,26),(0,NULL,106),(0,-128,11);
+INSERT INTO t1 (c1,c2,c3) values (0,0,26),(0,1,2),(0,126,26);
+SELECT * FROM t1 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
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 1;
+c1 c2 c3
+0 NULL 26
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 2;
+c1 c2 c3
+0 NULL 26
+0 NULL 106
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 3;
+c1 c2 c3
+0 NULL 26
+0 NULL 106
+0 -128 11
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 4;
+c1 c2 c3
+0 NULL 26
+0 NULL 106
+0 -128 11
+0 0 26
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 5;
+c1 c2 c3
+0 NULL 26
+0 NULL 106
+0 -128 11
+0 0 26
+0 1 2
+SELECT * FROM t1 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
+DROP TABLE t1;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("This"), (""), ("is"), (NULL), ("a"), (NULL), (""), (""), ("test"), (""), ("of"), (NULL), ("and"), ("");
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+test
+This
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+s1
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+s1
+NULL
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+s1
+NULL
+NULL
+NULL
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+s1
+NULL
+NULL
+NULL
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+s1
+NULL
+NULL
+NULL
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 7;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 8;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 9;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+SELECT * FROM t1 ORDER BY s1 LIMIT 10;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+SELECT * FROM t1 ORDER BY s1 LIMIT 11;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+SELECT * FROM t1 ORDER BY s1 LIMIT 12;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+SELECT * FROM t1 ORDER BY s1 LIMIT 13;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+test
+SELECT * FROM t1 ORDER BY s1 LIMIT 14;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+test
+This
+DROP TABLE t1;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""),(NULL),(""),(""),(NULL), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+NULL
+NULL
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+s1
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+s1
+NULL
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+s1
+NULL
+NULL
+NULL
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+s1
+NULL
+NULL
+NULL
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+s1
+NULL
+NULL
+NULL
+
+
+
+DROP TABLE t1;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("");
+SELECT * FROM t1 ORDER BY s1;
+s1
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+
+DROP TABLE t1;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (NULL);
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+DROP TABLE t1;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+s1
+NULL
+
+DROP TABLE t1;
+SET @@autocommit = 0;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("This"), (""), ("is"), (NULL), ("a"), (NULL), (""), (""), ("test"), (""), ("of"), (NULL), ("and"), ("");
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+test
+This
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+s1
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+s1
+NULL
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+s1
+NULL
+NULL
+NULL
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+s1
+NULL
+NULL
+NULL
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+s1
+NULL
+NULL
+NULL
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 7;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 8;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 9;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+SELECT * FROM t1 ORDER BY s1 LIMIT 10;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+SELECT * FROM t1 ORDER BY s1 LIMIT 11;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+SELECT * FROM t1 ORDER BY s1 LIMIT 12;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+SELECT * FROM t1 ORDER BY s1 LIMIT 13;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+test
+SELECT * FROM t1 ORDER BY s1 LIMIT 14;
+s1
+NULL
+NULL
+NULL
+
+
+
+
+
+a
+and
+is
+of
+test
+This
+DROP TABLE t1;
+COMMIT;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""),(NULL),(""),(""),(NULL), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+NULL
+NULL
+
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+s1
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+s1
+NULL
+NULL
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+s1
+NULL
+NULL
+NULL
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+s1
+NULL
+NULL
+NULL
+
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+s1
+NULL
+NULL
+NULL
+
+
+
+DROP TABLE t1;
+COMMIT;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("");
+SELECT * FROM t1 ORDER BY s1;
+s1
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+
+DROP TABLE t1;
+COMMIT;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (NULL);
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+DROP TABLE t1;
+COMMIT;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+s1
+NULL
+
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+s1
+NULL
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+s1
+NULL
+
+COMMIT;
+SET @@autocommit = 1;
+SELECT count(*) FROM t1;
+count(*)
+2
+DROP TABLE t1;
=== added file 'mysql-test/suite/falcon/t/falcon_bug_42208.test'
--- a/mysql-test/suite/falcon/t/falcon_bug_42208.test 1970-01-01 00:00:00 +0000
+++ b/mysql-test/suite/falcon/t/falcon_bug_42208.test 2009-02-23 11:49:41 +0000
@@ -0,0 +1,162 @@
+--source include/have_falcon.inc
+
+#
+# Bug #42208: Falcon's ORDER BY ..LIMIT gives wrong/inconsistent results on NULL values
+#
+--echo *** Bug #42208 ***
+
+# ----------------------------------------------------- #
+# --- Initialisation --- #
+# ----------------------------------------------------- #
+let $engine = 'Falcon';
+eval SET @@storage_engine = $engine;
+
+--disable_warnings
+DROP TABLE IF EXISTS t1;
+--enable_warnings
+
+# ----------------------------------------------------- #
+# --- Test --- #
+# ----------------------------------------------------- #
+
+# Testing the case from the bug report
+
+CREATE TABLE t1(c1 tinyint unsigned null, c2 tinyint, c3 bigint, index idx(c2,c3));
+INSERT INTO t1 (c1,c2,c3) values (0,NULL,26),(0,NULL,106),(0,-128,11);
+INSERT INTO t1 (c1,c2,c3) values (0,0,26),(0,1,2),(0,126,26);
+SELECT * FROM t1 ORDER BY c2,c3;
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 1;
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 2;
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 3;
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 4;
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 5;
+SELECT * FROM t1 ORDER BY c2,c3 LIMIT 6;
+DROP TABLE t1;
+
+# Testing some other interesting cases as too, that will
+# be affected by the patch
+
+# Testing single field indexes to see that empty string and NULL sort correctly
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("This"), (""), ("is"), (NULL), ("a"), (NULL), (""), (""), ("test"), (""), ("of"), (NULL), ("and"), ("");
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+SELECT * FROM t1 ORDER BY s1 LIMIT 7;
+SELECT * FROM t1 ORDER BY s1 LIMIT 8;
+SELECT * FROM t1 ORDER BY s1 LIMIT 9;
+SELECT * FROM t1 ORDER BY s1 LIMIT 10;
+SELECT * FROM t1 ORDER BY s1 LIMIT 11;
+SELECT * FROM t1 ORDER BY s1 LIMIT 12;
+SELECT * FROM t1 ORDER BY s1 LIMIT 13;
+SELECT * FROM t1 ORDER BY s1 LIMIT 14;
+DROP TABLE t1;
+
+# Testing special cases with only NULLs and empty strings
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""),(NULL),(""),(""),(NULL), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+DROP TABLE t1;
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("");
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+DROP TABLE t1;
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (NULL);
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+DROP TABLE t1;
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+DROP TABLE t1;
+
+# Then we are testing the for single field index with
+# autocommit of, to test the access through the deferred
+# indexes
+
+SET @@autocommit = 0;
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("This"), (""), ("is"), (NULL), ("a"), (NULL), (""), (""), ("test"), (""), ("of"), (NULL), ("and"), ("");
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+SELECT * FROM t1 ORDER BY s1 LIMIT 7;
+SELECT * FROM t1 ORDER BY s1 LIMIT 8;
+SELECT * FROM t1 ORDER BY s1 LIMIT 9;
+SELECT * FROM t1 ORDER BY s1 LIMIT 10;
+SELECT * FROM t1 ORDER BY s1 LIMIT 11;
+SELECT * FROM t1 ORDER BY s1 LIMIT 12;
+SELECT * FROM t1 ORDER BY s1 LIMIT 13;
+SELECT * FROM t1 ORDER BY s1 LIMIT 14;
+DROP TABLE t1;
+COMMIT;
+
+# Testing special cases with only NULLs and empty strings
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""),(NULL),(""),(""),(NULL), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+SELECT * FROM t1 ORDER BY s1 LIMIT 3;
+SELECT * FROM t1 ORDER BY s1 LIMIT 4;
+SELECT * FROM t1 ORDER BY s1 LIMIT 5;
+SELECT * FROM t1 ORDER BY s1 LIMIT 6;
+DROP TABLE t1;
+COMMIT;
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values ("");
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+DROP TABLE t1;
+COMMIT;
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (NULL);
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+DROP TABLE t1;
+COMMIT;
+
+CREATE TABLE t1 (s1 varchar(10), key(s1));
+INSERT INTO t1 values (""), (NULL);
+SELECT * FROM t1 ORDER BY s1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 1;
+SELECT * FROM t1 ORDER BY s1 LIMIT 2;
+COMMIT;
+
+SET @@autocommit = 1;
+
+# ----------------------------------------------------- #
+# --- Check --- #
+# ----------------------------------------------------- #
+SELECT count(*) FROM t1;
+
+# ----------------------------------------------------- #
+# --- Final cleanup --- #
+# ----------------------------------------------------- #
+DROP TABLE t1;
=== modified file 'storage/falcon/Index.cpp'
--- a/storage/falcon/Index.cpp 2009-02-20 12:14:41 +0000
+++ b/storage/falcon/Index.cpp 2009-02-23 11:49:41 +0000
@@ -296,7 +296,7 @@ void Index::makeKey(Field *field, Value
indexKey->keyLength = 0;
- if (!value)
+ if (!value || value->getType() == Null)
return;
switch (field->type)
@@ -356,6 +356,23 @@ void Index::makeKey(Field *field, Value
default:
indexKey->appendNumber(value->getDouble());
}
+
+ // Prepend 0x00 to empty keys, and keys starting with 0x00
+ // This is done to distinguish Null from empty keys, and to
+ // preserve the original sorting sequence
+ if (indexKey->keyLength == 0)
+ {
+ indexKey->key[0] = 0;
+ ++indexKey->keyLength;
+ }
+ else if (indexKey->key[0] == 0)
+ {
+ size_t moveLen = MIN(indexKey->keyLength, MAX_PHYSICAL_KEY_LENGTH - 1);
+ memmove (indexKey->key + 1, indexKey->key, moveLen);
+ indexKey->key[0] = 0;
+ indexKey->keyLength = moveLen + 1;
+ }
+
}
void Index::makeKey(int count, Value **values, IndexKey *indexKey, bool highKey)
@@ -421,17 +438,6 @@ void Index::makeKey(int count, Value **v
}
}
- if (n && n < numberFields)
- {
- // We're constructing partial search key, with only some
- // first fields given. Append segment byte for the next
- // segment. This will make key larger and will hopefully
- // reduce the number of false positives in search (saves
- // work in postprocessing).
- if (p < (uint)database->getMaxKeyLength())
- key[p++] = SEGMENT_BYTE(n, numberFields);
- }
-
indexKey->keyLength = p;
}
=== modified file 'storage/falcon/StorageDatabase.cpp'
--- a/storage/falcon/StorageDatabase.cpp 2009-02-20 12:14:41 +0000
+++ b/storage/falcon/StorageDatabase.cpp 2009-02-23 11:49:41 +0000
@@ -819,10 +819,7 @@ int StorageDatabase::makeKey(StorageInde
int len = getSegmentValue(segment, p, values[segmentNumber], index->fields[segmentNumber]);
if (nullFlag)
- {
values[segmentNumber]->setNull();
- break;
- }
p += len;
}
