Bug #26452 Unable to retrieve some rows with index
Submitted: 16 Feb 2007 17:02 Modified: 9 Mar 2007 11:01
Reporter: Alexey Stroganov Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Falcon storage engine Severity:S2 (Serious)
Version:5.2.3 OS:Linux (Linux)
Assigned to: Kevin Lewis CPU Architecture:Any

[16 Feb 2007 17:02] Alexey Stroganov
Description:
Testing of Falcon engine with 'mysql-bench' suite I've observed a case when server  sometime returns empty result set for following query:

select * from bench1 where id3=<value>

Table definition:

create table bench1 (id int NOT NULL,id2 int NOT NULL,
                     id3 int NOT NULL, dummy1 char(30),
                     primary key (id,id2), 
                     index ix_id3 (id3)) ENGINE=Falcon

Such issue was observed only in cases when rows were inserted in reverse or random order.

Below is output of attached perl script for table filled with 100000 rows:

Creating table
Inserting data in reverse order: 100000 rows
Retrieving inserted data:
rows for id3=43008 not found but they exist 0E0
rows for id3=45056 not found but they exist 0E0
rows for id3=47104 not found but they exist 0E0
rows for id3=49152 not found but they exist 0E0
rows for id3=51200 not found but they exist 0E0
rows for id3=65536 not found but they exist 0E0
rows for id3=69632 not found but they exist 0E0
rows for id3=73728 not found but they exist 0E0
rows for id3=77824 not found but they exist 0E0
rows for id3=81920 not found but they exist 0E0
rows for id3=86016 not found but they exist 0E0
rows for id3=90112 not found but they exist 0E0
rows for id3=94208 not found but they exist 0E0
rows for id3=98304 not found but they exist 0E0
Total ok=99986 nok=14

Interesting that distance between these 'holes' is either 2048 or 4096.

How to repeat:
Run attached test-case
[16 Feb 2007 17:04] Alexey Stroganov
test case for reported issue

Attachment: bug26452.pl (application/x-perl, text), 1.09 KiB.

[28 Feb 2007 7:38] Kevin Lewis
The following changeset was just pushed which fixes the problem illustrated by the perl script as it was designed.
ChangeSet@1.2461, 2007-02-27 22:09:35-06:00, klewis@klewis-mysql. +8 -0
  Use IndexPage::findIndexNode() instead of IndexPage::findIndex()
  to locate a the correct node within a page.  Also, modify this code so that if
  the record number is not provided, as in scanIndex, it can be called with
  recordNumber = -1.  On upper levels, when the record number is provided, always compare
  the main part of the key first, and then the record number for a tie-breaker,
  instead of treating them as one continuous string.

The problem was that index entries were periodicaly being inserted on the wrong page, so the SELEST statement failed to find it later.  It went on the wrong page because the appended record number on the parent page looked like part of the key.  Only numbers that had a shorter key, as represented in the index page, showed this problem.  The function that is used to find the correct node within a key page was improved so that it always compares the key value first, and then the record number (if it is a parent page and the record number is part of the search).

Even though this test case is fixed, there is a situation which is not fixed.  If the testcase is modified to not use a primary key, and 1000 duplicates are inserted for each of 500 unique records, then sometimes the SELECT will fail. 

I will attach the modified test script that currently fails.
[28 Feb 2007 14:48] Kevin Lewis
Duplicates across multiple pages.

Attachment: bug26452_A.pl (application/x-perl, text), 1.66 KiB.

[28 Feb 2007 15:34] Kevin Lewis
Added a second perl script which inserts 500 unique records but 1000 duplicates of each of these 500.  It causes level 1 pages to contain multiple nodes with the same key value. 

After the indexes are created, A SELECT for a specific value (id2=242 for example) will fail to find all 1000 records. The problem is the assumption that if you have previously matched n bytes of a key, and the current offset is greater than that, then you don't need to look at the current record.
Where this breaks down is when you match less than the full key because of an appended record number.

Consider the following section of the index;
   526. offset 1, length 6, 5957: : c0*6e,20,40,3f,16,34 ".*n ...4" [241]
   536. offset 6, length 1, 5970: : c0,6e,20,40,3f,16*44 ".n ...*D" [241]
   541. offset 2, length 4, 5980: : c0,6e*40,3f,54,b4 ".n*..T." [242]
   549. offset 5, length 1, 5991: : c0,6e,40,3f,54*c4 ".n..T*." [242]
   554. offset 3, length 4, 5935: : c0,6e,40*40,3e,d7,b4 ".n.*...." [242]
   562. offset 6, length 1, 5947: : c0,6e,40,40,3e,d7*c4 ".n....*." [242]
   567. offset 2, length 5, 5912: : c0,6e*60,40,3e,99,34 ".n*....4" [243]
   576. offset 6, length 1, 5924: : c0,6e,60,40,3e,99*44 ".n....*D" [243]

Suppose you are looking for the first occurance of c0,6e,40, and you have just compared with the node at offset 541.  541 is too short, with only two bytes length for key value and 4 bytes of record number. But the first two bytes match.  The next node, 549, has an offset of 5.
Since 5 > 2, the first 5 bytes match the previous revord, so the first two bytes match, so the algorithm skips this record without doing a comparison.  The next node, 554, is where we should stop, because the key value exactly matches
The searchKey (c0,6e,40)  But since the offset of 3 is greater than what we have successfully matched before, this record is also ignored.  WRONG. It has an offset of 3 because the 0x40 as the third byte of the key value happens to be the same as the first byte of the appended record number.

So now that we are not comparing the appended record number as part of the full key, then we cannot use the offset in the same way that we did before.

I am working on a solution.
[9 Mar 2007 9:41] Hakan Küçükyılmaz
Runs fine now:

hakan@lu0008:~/work/mysql/mysql-5.1-falcon> perl /home/hakan/work/mysql/bug26452.pl
Creating table
Inserting data in reverse order: 100000 rows
Retrieving inserted data:
Total ok=100000 nok=0

hakan@lu0008:~/work/mysql/mysql-5.1-falcon> perl /home/hakan/work/mysql/bug26452_A.pl
Creating table
Inserting in reverse order: 500 unique rows, 1000 of each
Retrieving inserted data from id1:
Retrieving inserted data from id2:
Total ok=500 nok=0

Best regards, Hakan
[9 Mar 2007 11:01] MC Brown
An entry has been placed in the 5.2.4 changelog.
[9 Mar 2007 15:38] Kevin Lewis
More complex test

Attachment: bug26452_B.pl (application/x-perl, text), 3.01 KiB.

[9 Mar 2007 15:41] Kevin Lewis
I added a more complexe test script, bug26452_B.pl which I used to find the final problems with this bug. It adds records from low to high alternating with records from high to low.  This adds more compbinations of index node comparisons.
[10 Jul 2007 19:10] MC Brown
This bug report entry has been moved to the 6.0.0 Falcon changelog.