#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.bjork | 10 Feb |
