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: | |
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
[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.