List:Commits« Previous MessageNext Message »
From:lars-erik.bjork Date:February 10 2009 8:01pm
Subject:bzr commit into mysql-6.0-falcon-team branch (lars-erik.bjork:3013)
View as plain text  
#At file:///home/lb200670/devel/mysql/blurp/ based on revid:hky@stripped

 3013 lars-erik.bjork@stripped	2009-02-10
      #34478 and #33190:
      ------------------
      
      I will base the explanation on the following
      insert statement:
      
      insert into t values (0x00),(0x0000),(0x0000),(0x00);
      
      DeferredIndex::addNode in DeferredIndex.cpp (way down the call stack
      from StorageInterface::write_row) adds one index node at a time for
      each inserted value. It compares the index keys and determines in
      which order the nodes should be arranged, in an array of nodes
      (leaf->nodes). After inserting the three first values, 0x00, 0x0000
      and 0x0000, the array looks like this
      
      [0x00|0x0000|0x0000|...] 
      
      which is correct. 
      
      When inserting the forth value, DeferredIndex::compare(DINode* node1, DINode* node2)
      returns that the node for 0x00 is greater than the node for 0x0000, and puts it
      (incorrectly at the end of the array) The comparison works like this:
      
      1. Check if one of the nodes are 0x0 pointers
         if (!node1)
         	  return -1;
      
      	  if (!node2)
      	  	 return 1;
      
      2. Find the shortest key length, and compare the values of the key up to this length. This
      will be equal for the first byte of 0x00 and 0x0000
      
      	 const UCHAR *p1 = node1->key;
      	 const UCHAR *p2 = node2->key;
      	 uint len = MIN(node1->keyLength, node2->keyLength);
      	 const UCHAR *end = p1 + len;
      	 
      	 while (p1 < end)
      	 	   if (*p1++ != *p2++)
      		   	  		 return p1[-1] - p2[-1];
      
      3. Check which key is the shortest, pad it to the other keys length, and compare. Because
      the pad byte is 0x00, the keys will still be equal.
      		
      		if (len < node1->keyLength)
      		   {
      				int n = checkTail(len, node1);
      					
      						if (n)
      								return n;
      									   }
      									   else if (len < node2->keyLength)
      									   		{
      												int n = checkTail(len, node2);
      													
      														if (n)
      																return -n;
      																	   }
      
      4. Finally compare the recordNumber. The recordNumber for the 0x00 node is higher, and
      therefore it is considered to sort after 0x0000.
      		  	 
      			 return node1->recordNumber - node2->recordNumber;
      }
      
      Padding with 0x00 and comparing seems to return the wrong result in
      this scenario.  The array will look like this
      [0x00|0x0000|0x0000|0x00], which is merged into the actual index.
      
      The fix for this is not to pad to the length of the longer key, but
      instead compare the length of the keys. This will also make sure
      that the ordering of the index keys are the same for both
      DeferredIndex::addNode and IndexRootPage::indexMerge. Therefore we can
      also enable the ASSERT that was commented out to hide #33190. Before
      commented out, this ASSERT used to hit because of different orderings.
      
      
      === added file 'mysql-test/suite/falcon/t/falcon_bug_34478.test'
      Test case for #34478, test case for #33190 already exists
      
      === added file 'mysql-test/suite/falcon/r/falcon_bug_34478.result'
      Result file for the test case
      
      === modified file 'storage/falcon/DeferredIndex.cpp'
      Changed the comparison methods, and removed the no longer used checkTail methods
      
      === modified file 'storage/falcon/DeferredIndex.h'
      Removed the no longer used checkTail methods
      
      === modified file 'storage/falcon/IndexRootPage.cpp'
      Uncommented the ASSERT and removed the debug message
added:
  mysql-test/suite/falcon/r/falcon_bug_34478.result
  mysql-test/suite/falcon/t/falcon_bug_34478.test
modified:
  storage/falcon/DeferredIndex.cpp
  storage/falcon/DeferredIndex.h
  storage/falcon/IndexRootPage.cpp

=== added file 'mysql-test/suite/falcon/r/falcon_bug_34478.result'
--- a/mysql-test/suite/falcon/r/falcon_bug_34478.result	1970-01-01 00:00:00 +0000
+++ b/mysql-test/suite/falcon/r/falcon_bug_34478.result	2009-02-10 20:01:34 +0000
@@ -0,0 +1,14 @@
+*** Bug #34478 ***
+SET @@storage_engine = 'Falcon';
+DROP TABLE IF EXISTS t1;
+CREATE TABLE t1 (s1 varbinary(1000));
+CREATE INDEX i1 on t1(s1);
+INSERT INTO t1 VALUES (0x00), (0x0000), (0x0000), (0x00);
+SELECT hex(s1) FROM t1 WHERE s1 = 0x00;
+hex(s1)
+00
+00
+SELECT count(*) FROM t1;
+count(*)
+4
+DROP TABLE t1;

=== added file 'mysql-test/suite/falcon/t/falcon_bug_34478.test'
--- a/mysql-test/suite/falcon/t/falcon_bug_34478.test	1970-01-01 00:00:00 +0000
+++ b/mysql-test/suite/falcon/t/falcon_bug_34478.test	2009-02-10 20:01:34 +0000
@@ -0,0 +1,37 @@
+--source include/have_falcon.inc
+
+#
+# Bug #34478: Falcon: search failure with varbinary = 0x00
+#
+--echo *** Bug #34478 ***
+
+# ----------------------------------------------------- #
+# --- Initialisation                                --- #
+# ----------------------------------------------------- #
+let $engine = 'Falcon';
+eval SET @@storage_engine = $engine;
+
+--disable_warnings
+DROP TABLE IF EXISTS t1;
+--enable_warnings
+
+# ----------------------------------------------------- #
+# --- Test                                          --- #
+# ----------------------------------------------------- #
+
+CREATE TABLE t1 (s1 varbinary(1000));
+CREATE INDEX i1 on t1(s1);
+INSERT INTO t1 VALUES (0x00), (0x0000), (0x0000), (0x00);
+
+# This would only return 1 row, should return 2
+SELECT hex(s1) FROM t1 WHERE s1 = 0x00;
+
+# ----------------------------------------------------- #
+# --- Check                                         --- #
+# ----------------------------------------------------- #
+SELECT count(*) FROM t1;
+
+# ----------------------------------------------------- #
+# --- Final cleanup                                 --- #
+# ----------------------------------------------------- #
+DROP TABLE t1;

=== modified file 'storage/falcon/DeferredIndex.cpp'
--- a/storage/falcon/DeferredIndex.cpp	2009-01-26 17:29:41 +0000
+++ b/storage/falcon/DeferredIndex.cpp	2009-02-10 20:01:34 +0000
@@ -453,41 +453,20 @@ int DeferredIndex::compare(DINode* node1
 	if (!node2)
 		return 1;
 
-	const UCHAR *p1 = node1->key;
-	const UCHAR *p2 = node2->key;
-	uint len = MIN(node1->keyLength, node2->keyLength);
-	const UCHAR *end = p1 + len;
-	
-	while (p1 < end)
-		if (*p1++ != *p2++)
-			return p1[-1] - p2[-1];
-	
-	/***		
-	for (uint l = len; l; --l)
-		{
-		int n = *p1++ - *p2++;
-		
-		if (n)
-			return n;
-		}
-	***/
-	
-	if (len < node1->keyLength)
-		{
-		int n = checkTail(len, node1);
-		
-		if (n)
-			return n;
-		}
-	else if (len < node2->keyLength)
-		{
-		int n = checkTail(len, node2);
-		
-		if (n)
-			return -n;
-		}
-		
-	return node1->recordNumber - node2->recordNumber;
+	uint len1 = node1->keyLength;
+	uint len2 = node2->keyLength;
+	uint minLen = MIN(len1, len2);
+	int ret = 0;
+
+	if (ret = memcmp(node1->key, node2->key, minLen))
+		return ret;
+
+	if (ret = len1 > len2 ? 1 : len1 < len2 ? -1 : 0)
+		return ret;
+	
+	int32 rno1 = node1->recordNumber;
+	int32 rno2 = node2->recordNumber;
+	return rno1 > rno2 ? 1 : rno1 < rno2 ? -1 : 0;
 }
 
 int DeferredIndex::compare(IndexKey *node1, DINode *node2, bool partial)
@@ -503,44 +482,18 @@ int DeferredIndex::compare(IndexKey *nod
 		return 1;
 		}
 
-	const UCHAR *p1 = node1->key;
-	const UCHAR *p2 = node2->key;
-	uint len = MIN(node1->keyLength, node2->keyLength);
-	const UCHAR *end = p1 + len;
-	
-	while (p1 < end)
-		if (*p1++ != *p2++)
-			return p1[-1] - p2[-1];
+	uint len1 = node1->keyLength;
+	uint len2 = node2->keyLength;
+	uint minLen = MIN(len1, len2);
+	int ret = 0;
+
+	if (ret = memcmp(node1->key, node2->key, minLen))
+		return ret;
 
-	/***	
-	for (uint l = len; l; --l)
-		{
-		int n = *p1++ - *p2++;
-		
-		if (n)
-			return n;
-		}
-	***/
-	
 	if (partial)
 		return 0;
 
-	if (len < node1->keyLength)
-		{
-		int n = checkTail(len, node1);
-		
-		if (n)
-			return n;
-		}
-	else if (len < node2->keyLength)
-		{
-		int n = checkTail(len, node2);
-		
-		if (n)
-			return -n;
-		}
-		
-	return 0;
+	return len1 > len2 ? 1 : len1 < len2 ? -1 : 0;
 }
 
 
@@ -552,66 +505,20 @@ int DeferredIndex::compare(IndexKey* nod
 	if (!node2)
 		return 1;
 
-	const UCHAR *p1 = node1->key;
-	const UCHAR *p2 = node2->key;
-	uint len = MIN(node1->keyLength, node2->keyLength);
-	
-	for (uint l = len; l; --l)
-		{
-		int n = *p1++ - *p2++;
-		
-		if (n)
-			return n;
-		}
-	
-	if (len < node1->keyLength)
-		{
-		int n = checkTail(len, node1);
-		
-		if (n)
-			return n;
-		}
-	else if (len < node2->keyLength)
-		{
-		int n = checkTail(len, node2);
-		
-		if (n)
-			return -n;
-		}
-		
-	return recordNumber - node2->recordNumber;
-}
+	uint len1 = node1->keyLength;
+	uint len2 = node2->keyLength;
+	uint minLen = MIN(len1, len2);
+	int ret = 0;
 
-int DeferredIndex::checkTail(uint position, DINode* node)
-{
-	UCHAR padByte = index->getPadByte();
-	
-	for (uint pos = position; pos < node->keyLength; ++pos)
-		if (index->numberFields == 1 || pos % RUN != 0)
-			{
-			int n = node->key[pos] - padByte;
-			
-			if (n)
-				return n;
-			}
-	
-	return 0;
-}
+	if (ret = memcmp(node1->key, node2->key, minLen))
+		return ret;
+
+	if (ret = len1 > len2 ? 1 : len1 < len2 ? -1 : 0)
+		return ret;
+
+	int32 rno2 = node2->recordNumber;
+	return recordNumber > rno2 ? 1 : recordNumber < rno2 ? -1 : 0;
 
-int DeferredIndex::checkTail(uint position, IndexKey *indexKey)
-{
-	UCHAR padByte = index->getPadByte();
-	
-	for (uint pos = position; pos < indexKey->keyLength; ++pos)
-		if (index->numberFields == 1 || pos % RUN != 0)
-			{
-			int n = indexKey->key[pos] - padByte;
-			
-			if (n)
-				return n;
-			}
-	
-	return 0;		
 }
 
 void DeferredIndex::validate(void)

=== modified file 'storage/falcon/DeferredIndex.h'
--- a/storage/falcon/DeferredIndex.h	2009-01-26 17:29:41 +0000
+++ b/storage/falcon/DeferredIndex.h	2009-02-10 20:01:34 +0000
@@ -88,8 +88,6 @@ public:
 	void			scanIndex (IndexKey *lowKey, IndexKey *highKey, int searchFlags, Bitmap *bitmap);
 	bool			chill(Dbb *dbb);
 
-	int				checkTail(uint position, DINode* node);
-	int				checkTail(uint position, IndexKey *indexKey);
 	void			validate(void);
 	static char*	format (uint indent, DINode *node, uint bufferLength, char *buffer);
 	void			print();

=== modified file 'storage/falcon/IndexRootPage.cpp'
--- a/storage/falcon/IndexRootPage.cpp	2008-11-20 17:05:50 +0000
+++ b/storage/falcon/IndexRootPage.cpp	2009-02-10 20:01:34 +0000
@@ -1026,8 +1026,7 @@ void IndexRootPage::indexMerge(Dbb *dbb,
 			// If the key is out of order, somebody screwed up.  Punt out of here
 			
 			if (key.compare(&priorKey) > 0)
-				//ASSERT(false);
-				Log::log("IndexRootPage::addIndexEntry: Unexpected out of order index");
+				ASSERT(false);
 
 			// Find the next insertion point, compute the next key, etc.
 			

Thread
bzr commit into mysql-6.0-falcon-team branch (lars-erik.bjork:3013) lars-erik.bjork10 Feb