MySQL Bugs: #23692: Falcon: searches fail if data is 0x00

Bug #23692	Falcon: searches fail if data is 0x00
Submitted:	26 Oct 2006 20:49	Modified:	15 May 2009 15:55
Reporter:	Peter Gulutzan	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Falcon storage engine	Severity:	S3 (Non-critical)
Version:	5.1.13-falcon-alpha-pb-debug	OS:	Linux (SUSE 10.0 / 64-bit)
Assigned to:	Lars-Erik BjÃ¸rk	CPU Architecture:	Any
Tags:	F_ENCODING, INDEX

Description:
I create a Falcon table with a character column with an index.
I insert 0x00.
I search for < ''.
I see 0 rows.

How to repeat:
ChangeSet@1.2346, 2006-10-26 10:08:37-04:00

mysql> create table t62 (s1 char(1),key(s1)) engine=falcon;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t62 values (0x00);
Query OK, 1 row affected (0.00 sec)

mysql> select * from t62 where s1<'';
Empty set (0.00 sec)

Verified on Linux 32-bit, change set 1.2348, 2006-10-27.

Added test case falcon_bug_23692.test to 5.1-falcon tree.

Regards, Hakan

Another test case:

mysql> create table tv (s1 varbinary(5)) engine=falcon;
Query OK, 0 rows affected (0.01 sec)

mysql> create index iv on tv (s1);
Query OK, 0 rows affected (0.02 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> insert into tv values (0x02),(0x0202);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> select hex(s1) from tv where s1 >= 0x02 or s1 = 0x0202;
+---------+
| hex(s1) |
+---------+
| 02      |
+---------+
1 row in set (0.01 sec)

Verified latest comment from Peter Gulutzan on Linux 32-bit and added additional test to test case falcon_bug_23962.test and pushed it to 5.1-falcon tree.

Regards, Hakan

Two weeks ago, I fixed BUG 24861 (Incorrect handling af varbinary fields) by making a special case for a BINARY collation.  The situation was the old falcon_bug_137 test within falcon_bugs.

# Mantis bug #137: Varbinary use fails if index exists
create table t4 (s1 varbinary(3) primary key);
insert into t4 values (0x41),(0x4100),(0x410000);

This test would fail because the Falcon code was trimming the string of trailing spaces and nullbytes.  I questioned whether a varbinary should have a CHARSET anyway, but made a special case for when it does.

Now, since the most recent merge with the mysql-5.1 tree, the CHARSET is no longer associated with varbinary.  Varbinary fields are given the type string when the field is defined thru the storage engine handler.  Without the CHARSET, I am not sure how to tell the difference between a varchar and a varbinary.

Varbinary fields are being declared as type string, and bytes between 0x00 and 0x20 have special meaning.  This is why this test fails.   

mysql> create table t4 (s1 varbinary(3) primary key);
mysql> insert into t4 values (0x41),(0x4100),(0x4120),(0x4121),(0x4141);
mysql> select hex(s1) from t4 where s1 > 0x41;
+---------+
| hex(s1) |
+---------+
| 4121    |
| 4141    |
+---------+
2 rows in set (0.00 sec)

In order to fix this, I need to figure out how to tell the difference between a varbinary field with no CHARSET and a varchar with no CHARSET.

This problem has no good solutions.  Either we get inaccurate results when looking for values that have ending characters less than the space character, or we get a general drop in performance.

The problem stems from the fact that Falcon uses prefix compression.  In order to do this efficiently, all trailing blanks must be trimmed off.  In SQL, trailing blanks are only assumed or implied, but when Falcon is sent strings from the server engine, they are real.  The server explicitly pads all search strings with spaces up to the maximum byte length that those strings could psssibly be.

So the Falcon engine is in the business of stripping trailing blanks off the end of search strings in order to find them in the index.  

Consider the following strings;
CREATE TABLE t3 (a char(5), key (a));
INSERT INTO t3 VALUES (0x4200), (0x4209), (0x42), (0x4242);

According to SQL, they should be sorted in the order entered.  But Falcon stores (0x4200) and (0x42) together as the same value, befor (0x4209).  So;
SELECT hex(a) FROM t3 WHERE a < 0x42;  
   returns nothing, but should return 0x4200 & 0x4209

Falcon takes the string with the implied trailing value of 0x20 and sorts it as if it had a trailing value of 0x00, so trailing values between 0x00 and 0x20 are not found for a less than search.  

If Falcon started treating the high value of a search range, like values < 'b', as if it was looking for values < 'b ', then  it would return from the index all the records where the value  = 'b'.  This is because the code that finds and returns hits in an index has no knowledge of the type of data in the comparison.  All key entries are sortable bytewise, left to right, so searching can be done quickly.  This solution, appending a space to a search string, will find too many hits, and waste too much time checking those hits against the record.  This would be especially bad in an index that had thousands of key values = 'b'.  In other words, large numbers of duplicates would have a VERY unoptimized search.  We cannot do thisjust to find  values with trailing character > 0 and < space.  It is not worth it.

Another solution is to store at least one training space character after each string that ended with a hex value of space or higher.  So the values above would be stored as 0x42, 0x4209, 0x4220 & 0x424220.  This would cause them to be sorted correctly, but it would add one or two bytes to almost every non-duplicate key page node, depending if the character set is collated as unicode.  This is also a performance problem, increasing the size of the index.

So I am in a quandary as to how this particular bug can be fixed without causing a general performance hit, which is not allowed!!!

As may be implied from the previous entry, this bug may not be fixable without a performance hit.  After discussions with Jim Starkey, we do not think this bug is worth fixing if it causes a performance hit.  So I would like to mark this 'Won't Fix'.

We should document that a search for a string that ends with a character who's sort weight is greater than zero and less than the implied SQL pad character (space), will work using '=' and the explicit key value.  But other searches will be problematic.

The code that I checked in last week does not work as I expected for this test.  My intention was to be able to find the 0x4109 with a like 'a%' search.  As I look at the fix for that, I think I might be able to use the implied pad character on the highKey of a range search in order to always return the correct records.

Putting this back to 'In Progress' to see if I can make a solution that works without slowing Falcon down.

Pushed an enhanced testcase, which still does not work.

I looked into adding a single pad character to the highKey so that it is positioned after all the values with trailing characters between 0x00 and the pad character. But this would for the inclusion of the highKey hits even if the search is field < 'value'.  I thought this would cause a performance problem, but them I found that the end points of ALL range searches are already being included even for 'less than' and 'greater than' searches where the end points are not needed.  

Jim indicated that this is necessary for indexes that contain numeric fields that may contain 'round off' differences from the exact stored value.  Falcon indexes arre designed to be less exact in resolving hits.  So the final resolve is always done against the records.  

Since the endpoints are always included in every range search, it causes no harm to add one pad character to the highKey during an index scan.  So I will pursue this solution.

We will fix this after the beta release since it affect some very commonly called code;  scanIndex().  And the result is the ability to retrieve records using a < search when the key matches the search key but with low bytes appended, such as a tab.  In other words, the benefit is rarely needed, but the changed code is used all the time.  So the risk is much higher than the benefit.

On 2007-05-17 Kevin Lewis marked this "to be fixed later"
saying "We will fix this after the beta release ...".
Since it is now after the beta release, I set it back to
"Verified".

Another character-set related bug.

Test case for this bug. Moved from falcon_team suite. Will fail until bug is fixed.

Attachment: falcon_bug_23692.test (application/octet-stream, text), 1.39 KiB.

Test result file associated with the attached falcon_bug_23692.test.

Attachment: falcon_bug_23692.result (application/octet-stream, text), 1.51 KiB.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/67022

3030 lars-erik.bjork@sun.com	2009-02-20
      This is a patch for bug#23692 (Falcon: searches fail if data is 0x00)
      
      The solution is to append a pad key to the upper 
      bound search key, if its last character is equal
      to or greater than the pad character. This is done
      In order to make it position after all values with 
      trailing characters lower than the pad character.
      
      For fields with a collation registered
      [if (field->collation)], there is no efficient way
      of checking if the last character is equal or greater
      than the pad character, without iterating through the
      entire key from the beginning.
      
      I have discussed this with Alexander Barkov who suggests
      to always pad the upper bound search key in these cases,
      and to pad it to the length of the key, instead of 
      appending just a single character. This way I can use the
      existing cs->coll->strnxfrm function.
      
      In the other cases, I have checked on the last byte and
      appended 0x20 if the byte was >= 0x20.
      
      I have also added one more parameter to the makeKey methods
      to say that this is a highKey.

Looks like a good soluition and the code looks good.

Pushed into 6.0.11-alpha (revid:alik@sun.com-20090302140208-lfdejjbcyezlhhjt) (version source revid:vvaintroub@mysql.com-20090223172157-jllfd81jwvak4n5j) (merge vers: 6.0.11-alpha) (pib:6)

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.