MySQL Bugs: #34478: Falcon: search failure with varbinary = 0x00

Bug #34478	Falcon: search failure with varbinary = 0x00
Submitted:	12 Feb 2008 2:27	Modified:	15 May 2009 14:15
Reporter:	Peter Gulutzan	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Falcon storage engine	Severity:	S3 (Non-critical)
Version:	6.0.5-alpha-debug	OS:	Linux (SUSE 10 \| 32-bit)
Assigned to:	Lars-Erik BjÃ¸rk	CPU Architecture:	Any
Tags:	F_ENCODING

Description:
I'm using mysql-6.0-falcon.

I create an indexed Falcon table with a VARBINARY column.
I insert several strings, containing 0x00 and NULL.
I search for "column = 0x00".
I find only one row. But there are two matching rows.

I do not see the same effect if I define the
column as VARCHAR instead of VARBINARY, and
it is "using '=' and the explicit key value",
so I think it's different from other '0x00' bugs:
Bug#30282 Falcon: duplicate-key error for value that ends with 0x00
Bug#23692 Falcon: searches fail if data is 0x00

How to repeat:
mysql> create table t (s1 varbinary(1000)) engine=falcon;
Query OK, 0 rows affected (0.10 sec)

mysql> create index i on t (s1);
Query OK, 0 rows affected (0.14 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> insert into t values (0x0000),(0x00),(0x000000);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> insert into t values (null),(0x000000);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into t values (0x0000000000000000),(0x00),(0x0000);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> select hex(s1) from t;
+------------------+
| hex(s1)          |
+------------------+
| 0000             |
| 00               |
| 000000           |
| NULL             |
| 000000           |
| 0000000000000000 |
| 00               |
| 0000             |
+------------------+
8 rows in set (0.00 sec)

mysql> select hex(s1) from t where s1 = 0x00;
+---------+
| hex(s1) |
+---------+
| 00      |
+---------+
1 row in set (0.00 sec)

Thank you for the bug report.

Another character-set related bug.

This one is just strange, at least to me. I tried to narrow it down, and here is what happens:
 
insert into t values (0x00), (0x0000), (0x0000), (0x00);

If I do a select for hex(0x00), only one row is returned. It seems that if there are more than 1 intermediate all-zero value between the two 0x00s, we will only be able to find one of the following 0x00s through the index. If we remove one of the intermediate 0x0000 or have an intermediate non-zero value, it will work as expected. Also, every 0x00 value inserted before this strange sequence, will be found as expected through the index, whereas every 0x00 value inserted after this sequence will not be found, unless it is in a different insert statement.

Enabling some debug in IndexRootPage::scanIndex suggests that the ordering in the index is wrong.

insert into t values (0x00),(0x0080),(0x0080),(0x00);

The ordering is as follows:

lower: : *00 "*." [0]
upper: : *00 "*." [0]
Btree Page 6, level 0, length 77, prior 0, next 0, parent 0
Supernodes:
   60(super). offset 0, length 1, 0: : *00 "*." [0]
   64. offset 1, length 0, 3: : 00 "." [0]
   67. offset 1, length 1, 1: : 00*80 ".*." [0]
   71. offset 2, length 0, 2: : 00,80 ".." [0]
   74. offset 0, length 0, -2: :  "" [0]

The failing case

insert into t values (0x00),(0x0000),(0x0000),(0x00);

The order is as follows:

lower: : *00 "*." [0]
upper: : *00 "*." [0]
Btree Page 4, level 0, length 77, prior 0, next 0, parent 0
Supernodes:
   60(super). offset 0, length 1, 0: : *00 "*." [0]
   64. offset 1, length 1, 1: : 00*00 ".*." [0]
   68. offset 2, length 0, 2: : 00,00 ".." [0]
   71. offset 1, length 0, 3: : 00 "." [0]
   74. offset 0, length 0, -2: :  "" [0]

An even more illustrative non-working case:

 insert into t values (0x00), (0x0000), (0x0000), (0x0080), (0x0040), (0x00), (0x00), (0x0060);

lower: : *00 "*." [0]
upper: : *00 "*." [0]
Btree Page 4, level 0, length 92, prior 0, next 0, parent 0
Supernodes:
   60(super). offset 0, length 1, 0: : *00 "*." [0]
   64. offset 1, length 1, 1: : 00*00 ".*." [0]
   68. offset 2, length 0, 2: : 00,00 ".." [0]
   71. offset 1, length 0, 5: : 00 "." [0]
   74. offset 1, length 0, 6: : 00 "." [0]
   77. offset 1, length 1, 4: : 00*40 ".*." [0]
   81. offset 1, length 1, 7: : 00*60 ".*." [0]
   85. offset 1, length 1, 3: : 00*80 ".*." [0]
   89. offset 0, length 0, -2: :  "" [0]

I believe the equality search stops when the first 0x0000 is hit

I have debugged this a little further, and I will base the explanation on the following insert statement:

insert into t values (0x00),(0x0000),(0x0000),(0x00);

I have looked at DeferredIndex::addNode in DeferredIndex.cpp (way down the call stack from StorageInterface::write_row)

This method 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 recordNubmer 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 index.

When searching for values = 0x00, we will stop when we reach 0x0000, and therefore not get the correct number of rows.

This bug needs to be re-triaged based on Kostjas request.

kostja wrote;
Bug#34478 "Falcon: search failure with varbinary = 0x00"
is affecting the foreign key implementation.

Bug#41844 Foreign keys: failure with varbinary update cascade
yields a similar error when varbinary is used for foreign key
columns. 

Could you please re-prioritize this bug, increase its priority and
assign someone to get it fixed?

I believe a manifestation in foreign key context is a valid new
use case that should influence priority.

We need it to be able to complete Milestone 8, which is due to be
done in February.

This bug is similar to Bug#33190 in that the core problem is that DeferredIndex is not sorting key values exactly like Index Key values are sorted with regard to 0x00 characters.

A patch has been pushed for this bug.

The commit is available at http://lists.mysql.com/commits/65950

Bug #41844 "Foreign keys: failure with varbinary update cascade" was marked as duplicate of this bug.

Pushed into 6.0.11

A note has been added to the 6.0.11 changelog: 

Searching for 0x00 in Falcon tables using the VARBINARY column type would fail to return the correct rows. In addition, a crash could be encountered when modifying a column to the VARBINARY type.