List:Commits« Previous MessageNext Message »
From:lars-erik.bjork Date:February 16 2009 7:40pm
Subject:bzr commit into mysql-6.0-falcon-team branch (lars-erik.bjork:3025) Bug#42208
View as plain text  
#At file:///home/lb200670/devel/mysql/blurp/ based on revid:vvaintroub@stripped

 3025 lars-erik.bjork@stripped	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
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/IndexWalker.cpp
  storage/falcon/IndexWalker.h
  storage/falcon/StorageDatabase.cpp
  storage/falcon/WalkDeferred.cpp
  storage/falcon/WalkIndex.cpp

=== 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-16 19:40:32 +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-16 19:40:32 +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-01-26 17:34:37 +0000
+++ b/storage/falcon/Index.cpp	2009-02-16 19:40:32 +0000
@@ -296,7 +296,12 @@ void Index::makeKey(Field *field, Value 
 
 	indexKey->keyLength = 0;
 
-	if (!value)
+	// Returning with a keyLength of 0 for Null values, will make
+	// keys for Null values, and keys for empty string values ("")
+	// sort together. To make up for this, we have to take some
+	// special steps when traversing the index with the IndexWalker
+
+	if (!value || value->getType() == Null)
 		return;
 
 	switch (field->type)
@@ -407,17 +412,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/IndexWalker.cpp'
--- a/storage/falcon/IndexWalker.cpp	2008-11-20 17:05:50 +0000
+++ b/storage/falcon/IndexWalker.cpp	2009-02-16 19:40:32 +0000
@@ -18,6 +18,8 @@
 #include "Record.h"
 #include "Table.h"
 #include "SQLError.h"
+#include "Value.h"
+#include "Field.h"
 
 #define RESET_PARENT(newChild)		\
 	if (parent->lower == this)		\
@@ -41,12 +43,19 @@ IndexWalker::IndexWalker(Index *idx, Tra
 	lower = NULL;
 	lastRecordNumber = 0;
 	firstRecord = true;
+	cache = NULL;
+	numberCached = 0;
+	currentCached = 0;
+	done = false;
+	walkState = INSERTING_INTO_CACHE;
 }
 
 IndexWalker::~IndexWalker(void)
 {
 	if (next)
 		delete next;
+	if (cache)
+		delete [] cache;
 }
 
 Record* IndexWalker::getNext(bool lockForUpdate)
@@ -124,7 +133,7 @@ Record* IndexWalker::getNext(bool lockFo
 	return NULL;
 }
 
-Record* IndexWalker::getValidatedRecord(int32 recordId, bool lockForUpdate)
+Record* IndexWalker::getValidatedRecord(int32 recordId, bool lockForUpdate, IndexKey &recordKey, bool cached)
 {
 	// If this is the same recordId as the last record we returned,
 	// then either we've got a duplicate copy because a deferred
@@ -133,7 +142,7 @@ Record* IndexWalker::getValidatedRecord(
 
 	if (firstRecord)
 		firstRecord = false;
-	else if (recordId == lastRecordNumber)
+	else if (recordId == lastRecordNumber && !cached)
 		return NULL;
 
 	// Fetch record.  If it doesn't exist, that's ok.
@@ -151,6 +160,7 @@ Record* IndexWalker::getValidatedRecord(
 	
 	if (!record)
 		{
+
 		if (!lockForUpdate)
 			candidate->release();
 		
@@ -164,24 +174,27 @@ Record* IndexWalker::getValidatedRecord(
 		record->addRef();
 		candidate->release();
 		}
+
+	if (cached)
+		{
+		lastRecordNumber = recordId;
+		return record;
+		}
+
+	// Compute record key and compare against index key. If there' different, punt
 	
-	// Compute record key and compare against index key.  If there' different, punt
-	
-	IndexKey recordKey;
 	index->makeKey(record, &recordKey);
 	
-	if (recordKey.keyLength != keyLength ||
-		memcmp(recordKey.key, key, keyLength) != 0)
+	if ((recordKey.keyLength != keyLength ||
+		 memcmp(recordKey.key, key, keyLength) != 0))
 		{
 		record->release();
 		
 		return NULL;
 		}
 
-	// remember this record
-
 	lastRecordNumber = recordId;
-
+	
 	return record;
 }
 
@@ -558,3 +571,29 @@ void IndexWalker::corrupt(const char *te
 {
 	ASSERT(false);
 }
+
+IndexWalker::ValueInfo IndexWalker::examineKey(IndexKey *recordKey, Record *record)
+{
+
+	if (recordKey->keyLength == 0 && index->numberFields == 1) 
+		{
+		
+		// This is either from the value of an empty string, or from
+		// a Null. If it is from an empty string it should 
+		// be cached until a non empty key is encountered
+		
+		Value value; 
+		record->getValue(index->fields[0]->id, &value);
+		
+		if (value.getType() == Null)
+			{
+			return NULL_VALUE;
+			}
+		else
+			{
+			return EMPTY_VALUE;
+			}
+		}
+
+	return REGULAR_VALUE;
+}

=== modified file 'storage/falcon/IndexWalker.h'
--- a/storage/falcon/IndexWalker.h	2008-07-28 14:31:20 +0000
+++ b/storage/falcon/IndexWalker.h	2009-02-16 19:40:32 +0000
@@ -18,11 +18,15 @@
 
 #include "IndexKey.h"
 
+#define CACHE_SIZE_DELTA 32
+
 class Index;
 class Transaction;
 class Record;
 class Table;
 
+
+
 class IndexWalker
 {
 public:
@@ -31,7 +35,7 @@ public:
 	
 	virtual Record*		getNext(bool lockForUpdate);
 
-	Record*				getValidatedRecord(int32 recordId, bool lockForUpdate);
+	Record*				getValidatedRecord(int32 recordId, bool lockForUpdate, IndexKey& recordKey, bool cached);
 	int					compare(IndexWalker* node1, IndexWalker* node2);
 	void				addWalker(IndexWalker* walker);
 	bool				insert(IndexWalker* node);
@@ -45,7 +49,7 @@ public:
 	// debugging routines 
 	int					validate(void);
 	void				corrupt(const char *text);
-	
+
 	Index			*index;
 	Transaction		*transaction;
 	Record			*currentRecord;
@@ -62,6 +66,29 @@ public:
 	int				searchFlags;
 	bool			first;
 	bool			firstRecord;
+
+protected:
+	enum WalkState {
+		INSERTING_INTO_CACHE = 1,
+		READING_FROM_CACHE,
+		NOT_USING_CACHE
+	};
+
+	enum ValueInfo {
+		NULL_VALUE = 1,
+		EMPTY_VALUE,
+		REGULAR_VALUE
+	};
+
+	// This is an array that will be allocated when needed
+	int32*          cache;
+
+	int             numberCached;
+	int             currentCached;
+	bool            done;
+	WalkState       walkState;
+
+	ValueInfo       examineKey(IndexKey *indexKey, Record *record);
 };
 
 #endif

=== modified file 'storage/falcon/StorageDatabase.cpp'
--- a/storage/falcon/StorageDatabase.cpp	2009-01-20 08:09:02 +0000
+++ b/storage/falcon/StorageDatabase.cpp	2009-02-16 19:40:32 +0000
@@ -821,7 +821,6 @@ int StorageDatabase::makeKey(StorageInde
 			if (nullFlag)
 				{
 				values[segmentNumber]->setNull();
-				break;
 				}
 
 			p += len;

=== modified file 'storage/falcon/WalkDeferred.cpp'
--- a/storage/falcon/WalkDeferred.cpp	2008-10-16 02:53:35 +0000
+++ b/storage/falcon/WalkDeferred.cpp	2009-02-16 19:40:32 +0000
@@ -13,9 +13,15 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
+#include <memory.h>
 #include "Engine.h"
 #include "WalkDeferred.h"
 
+#ifdef _DEBUG
+#undef THIS_FILE
+static const char THIS_FILE[]=__FILE__;
+#endif
+
 WalkDeferred::WalkDeferred(DeferredIndex *deferredIdx, Transaction *transaction, int flags, IndexKey *lower, IndexKey *upper) 
 	: IndexWalker(deferredIdx->index, transaction, flags)
 {
@@ -33,19 +39,174 @@ Record* WalkDeferred::getNext(bool lockF
 {
 	for (;;)
 		{
-		node = walker.next();
-		
-		if (!node)
+
+		// Because keys for the empty string value ("") and Nulls
+		// look the same (they both have keyLength 0), we have
+		// to take this into consideration when walking the 
+		// index. These keys may come mixed, and we should 
+		// cache the record numbers for all zero length keys 
+		// that are not for Null values until we reach a 
+		// non-zero length key. This way we ensure that
+		// the ordering returned from this function is correct.
+
+		bool cacheRecord;
+		int32 recordNumber;
+		currentRecord = NULL;
+
+		// Will be Passed by reference to getValidatedRecord() 
+		IndexKey recordKey;
+
+		switch (walkState)
 			{
-			currentRecord = NULL;
-			return NULL;
-			}
-
-		key = node->key;
-		keyLength = node->keyLength;
-		recordNumber = node->recordNumber;
+
+			// In this state we are inserting record numbers 
+			// into the cache until we reach a key with a 
+			// non-zero key length, or until we reach the end.
+			
+			case INSERTING_INTO_CACHE:
+			    {
+			
+				node = walker.next();
 		
-		if ( (currentRecord = getValidatedRecord(recordNumber, lockForUpdate)) )
-			return currentRecord;
-		}
+				if (!node)
+					{
+					walkState = READING_FROM_CACHE;
+					done = true;
+					break;					
+					}
+
+				key = node->key;
+				keyLength = node->keyLength;
+				recordNumber = node->recordNumber;
+			
+				// Passing a reference, to recordKey
+				currentRecord = getValidatedRecord(recordNumber, lockForUpdate, 
+												   recordKey, false);				
+
+				// Checking what kind of value this key is for
+   				ValueInfo info = examineKey(&recordKey, currentRecord);
+				
+				switch (info)
+					{
+					case REGULAR_VALUE:
+
+						// This is the first normal key value. If there
+						// are record numbers in the cache, we will need to
+						// cache this one as well to preserve the ordering
+						
+						cacheRecord = (numberCached > 0);
+						walkState = READING_FROM_CACHE;
+						break;
+						
+					case NULL_VALUE:
+						cacheRecord = false;
+						break;
+
+					case EMPTY_VALUE:
+						cacheRecord = true;
+						break;
+
+					default:
+						ASSERT(false);
+					}
+
+				if (cacheRecord)
+					{
+
+					if (!cache)
+						{
+						cache = new int32[CACHE_SIZE_DELTA];
+						}
+					else if (!numberCached < sizeof(cache))
+						{
+
+						// The cache is full, extend it
+						
+						int newCacheSize = sizeof(cache) + CACHE_SIZE_DELTA;
+						int32* newCache = new int32[newCacheSize];
+
+						// Copying all the cached values
+						memcpy(newCache, cache, numberCached * sizeof(int32));
+
+						delete [] cache;
+						cache = newCache;
+						}
+
+					cache[numberCached++] = recordNumber;
+					}
+				else
+					{
+
+					if (currentRecord)
+						return currentRecord;
+
+					}
+				}
+				break;
+				
+			// In this state, we are reading record numbers from
+			// the cache until it is empty. The records are fetched
+			// again through getValidateRecord(), passing 'true' to
+			// tell that these record numbers are cached
+			   				
+			case READING_FROM_CACHE:
+				
+				// There are still recordNumbers in the cache,
+				// return Records for these in the order they 
+				// were added
+				
+				if (numberCached > 0)
+					{
+					recordNumber = cache[currentCached++];
+					numberCached--;
+					currentRecord = getValidatedRecord(recordNumber, lockForUpdate, 
+													   recordKey, true);					
+					}
+
+				// We have used all the record numbers in
+				// the cache
+
+				if (numberCached == 0)
+					walkState = NOT_USING_CACHE;
+
+				if (currentRecord)
+					return currentRecord;
+
+				break;
+
+			// In this state, we have read all keys with a zero 
+			// key length (if any), and we are going back to normal processing
+
+			case NOT_USING_CACHE:
+			    {
+
+				// We already reached the end, trying to call 
+				// next() again, will fail
+
+				if (done)
+					return NULL;
+				
+				node = walker.next();
+		
+				if (!node)
+					return NULL;
+
+				key = node->key;
+				keyLength = node->keyLength;
+				recordNumber = node->recordNumber;
+				currentRecord = getValidatedRecord(recordNumber, lockForUpdate, 
+												   recordKey, false);
+				
+				if (currentRecord)
+					return currentRecord;
+				
+				}
+				break;
+
+			default:
+				ASSERT(false);
+
+		    } // end of switch
+
+		} // end of loop
 }

=== modified file 'storage/falcon/WalkIndex.cpp'
--- a/storage/falcon/WalkIndex.cpp	2008-07-15 18:57:27 +0000
+++ b/storage/falcon/WalkIndex.cpp	2009-02-16 19:40:32 +0000
@@ -62,20 +62,176 @@ Record* WalkIndex::getNext(bool lockForU
 {
 	for (;;)
 		{
-		int32 recordNumber = getNextNode();
-		
-		if (recordNumber < 0)
+
+		// Because keys for the empty string value ("") and Nulls
+		// look the same (they both have keyLength 0), we have
+		// to take this into consideration when walking the 
+		// index. These keys may come mixed, and we should 
+		// cache the record numbers for all zero length keys 
+		// that are not for Null values until we reach a 
+		// non-zero length key. This way we ensure that
+		// the ordering returned from this function is correct.
+
+		bool cacheRecord;
+		int32 recordNumber;
+		currentRecord = NULL;
+
+		// Will be Passed by reference to getValidatedRecord() 
+		IndexKey recordKey;
+
+		switch (walkState)
 			{
-			currentRecord = NULL;
+
+			// In this state we are inserting record numbers 
+			// into the cache until we reach a key with a 
+			// non-zero key length, or until we reach the end.
+
+			case INSERTING_INTO_CACHE:
+			    {
 			
-			return NULL;
-			}
-		
-		keyLength = indexKey.keyLength;
-		
-		if ( (currentRecord = getValidatedRecord(recordNumber, lockForUpdate)) )
-			return currentRecord;
-		}
+				recordNumber = getNextNode();
+			
+				if (recordNumber < 0)
+					{
+					walkState = READING_FROM_CACHE;
+					done = true;
+					break;
+					}		
+				
+				keyLength = indexKey.keyLength;
+				
+				// Passing a reference to recordKey
+				currentRecord = getValidatedRecord(recordNumber, lockForUpdate, 
+												   recordKey, false);
+				
+				// Checking what kind of value this is key for				
+				ValueInfo info = examineKey(&recordKey, currentRecord);
+				
+				switch (info)
+					{
+					case REGULAR_VALUE:
+
+						// This is the first normal key value. If there
+						// are record numbers in the cache, we will need to
+						// cache this one as well to preserve the ordering.
+						// Switching the state.
+						
+						cacheRecord = (numberCached > 0);
+						walkState = READING_FROM_CACHE;
+						break;
+						
+					case NULL_VALUE:
+						cacheRecord = false;
+						break;
+
+					case EMPTY_VALUE:
+						cacheRecord = true;
+						break;
+
+					default:
+						ASSERT(false);
+					}
+
+				if (cacheRecord)
+					{
+
+					if (!cache)
+						{
+						cache = new int32[CACHE_SIZE_DELTA];
+						}
+					else if (!numberCached < sizeof(cache))
+						{
+						
+						// The cache is full, extend it
+
+						int newCacheSize = sizeof(cache) + CACHE_SIZE_DELTA;
+						int32* newCache = new int32[newCacheSize];
+
+						// Copying all the cached values
+						memcpy(newCache, cache, numberCached * sizeof(int32));
+
+						delete [] cache;
+						cache = newCache;
+						}
+
+					cache[numberCached++] = recordNumber;
+
+					}
+				else
+					{
+
+					if (currentRecord)
+						return currentRecord;
+
+					}
+				}
+				break;
+
+			// In this state, we are reading record numbers from
+			// the cache until it is empty. The records are fetched
+			// again through getValidateRecord(), passing 'true' to
+			// tell that these record numbers are cached
+				
+			case READING_FROM_CACHE:
+				
+				// There are still recordNumbers in the cache,
+				// return Records for these in the order they 
+				// were added
+				
+				if (numberCached > 0)
+					{
+					recordNumber = cache[currentCached++];
+					numberCached--;
+					currentRecord = getValidatedRecord(recordNumber, lockForUpdate, 
+													   recordKey, true);
+					}
+
+				// We have used all the record numbers in
+				// the cache
+
+				if (numberCached == 0)
+					walkState = NOT_USING_CACHE;
+
+				if (currentRecord)
+					return currentRecord;
+
+				break;
+
+			// In this state, we have read all keys with a zero 
+			// key length, and we are going back to normal processing
+
+			case NOT_USING_CACHE:
+			    {
+
+				// We already reached the end trying to call 
+				// getNextNode(), again, will fail
+
+				if (done)
+					{
+					return NULL;
+					}
+				
+				recordNumber = getNextNode();
+
+				if (recordNumber < 0)
+					return NULL;
+				
+				keyLength = indexKey.keyLength;
+				currentRecord = getValidatedRecord(recordNumber, lockForUpdate, 
+												   recordKey, false);
+				
+				if (currentRecord)
+					return currentRecord;
+				
+				}
+				break;
+
+			default:
+				ASSERT(false);
+
+		    } // end of switch
+
+		} // end of for
 }
 
 int32 WalkIndex::getNextNode(void)

Thread
bzr commit into mysql-6.0-falcon-team branch (lars-erik.bjork:3025) Bug#42208lars-erik.bjork16 Feb