List:Falcon Storage Engine« Previous MessageNext Message »
From:Lars-Erik Bjørk Date:May 14 2009 10:17am
Subject:Some more on IndexWalkers
View as plain text  
Hi Ann, and the crew!

After pushing http://lists.mysql.com/commits/73707 for bug #43630
'A SELECT using ORDER BY and LIMIT sometimes returns no rows'
I have been looking at the remaining cases where we are returned too
few, or no, rows when doing a LIMIT query. It seems that when we find  
a node
with a recordNumber >= 0 as the first node on a page, we forget to  
expand
the key. I believed that this was deliberate, as the key should  
already be
expanded, being identical to the last entry on the previous page.  
Looking at this
in the debugger however, this does not seem to be the case.

When we start searching the first page that actually contains valid  
entries,
IndexWalker::keyLength and IndexWalker::key has the following values:

(gdb) p keyLength
$4 = 2
(gdb) x/bt key
0x7fab4cfaf810: 10111111
(gdb) x/bt key+1
0x7fab4cfaf811: 11110000

whereas the index node we are looking at has the following:

(gdb) p node
$2 = {node = 0x7fab4cfa7750, nextNode = 0x7fab4cfa7755, offset = 0,  
length = 1, key = 0x7fab4cfa7754 "\300\001", number = 329}
(gdb) p node.length
$3 = 1
(gdb) x/bt node.key
0x7fab4cfa7754: 11000000

The keys and keylengths do not match. The recordKey created from the
record when comparing in IndexWalker::getValidatedRecord, however, looks
the same as the node:

(gdb) p recordKey.keyLength
$5 = 1
(gdb) x/bt recordKey.key
0x7fab3fcb88e8: 11000000

Since all the fields have the same value, expanding the key for the  
following
nodes is a no-op, because the offset will be 1 and the length 0.  
Therefore we
miss a lot of rows until we reach a node with offset 0 and length 1.  
This is
maybe a supernode, since it seems to be fully expanded?

If I add the following line of code:

int32 WalkIndex::getNextNode(void)
{
    for (;; first = true)
        {
        if (first)
            {
            first = false;
            recordNumber = node.getNumber();

            if (recordNumber >= 0)
                {
                  node.expandKey(&indexKey);  // <==== This line
                  return recordNumber;
                  }

we only experience some cases where we miss 1 row, opposed to
often missing a lot. We still have the other problem with too many  
rows though :)

Is it correct that we miss to expand the key here, or is it something  
else that is fishy?
(I know there is fishy stuff here, but hopefully not regarding this  
particular issue :) )

For the curious, a little information about the nodes searched is  
presented below:

Page = page number
dup = number of entries reported as duplicates
nrec = number of entries that have no matching record
ncan = number of entries that had no visible records
nmis = number of entries who's key does not match with the key  
generated from the record
nret = number of entries returned as valid entries

This is presented in search order

Page:137,        dup:0,  nrec:0,         ncan:0,         nmis: 
35,        nret:0
Page:138,        dup:0,  nrec:0,         ncan:0,         nmis: 
1000,      nret:0
Page:181,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:175,        dup:0,  nrec:0,         ncan:0,         nmis: 
206,       nret:465               (valid)
Page:136,        dup:0,  nrec:0,         ncan:0,         nmis: 
515,       nret:0
Page:219,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:147,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:174,        dup:0,  nrec:0,         ncan:0,         nmis: 
2,         nret:329               (valid)
Page:199,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:173,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:214,        dup:1,  nrec:0,         ncan:0,         nmis: 
451,       nret:0
Page:149,        dup:1,  nrec:0,         ncan:0,         nmis: 
459,       nret:0
Page:139,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:156,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:185,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:159,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:229,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:164,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:165,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:186,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:191,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:228,        dup:0,  nrec:0,         ncan:0,         nmis: 
91,        nret:0
Page:230,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:234,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:235,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:158,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:160,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:155,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:151,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:162,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:236,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:237,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:161,        dup:0,  nrec:0,         ncan:0,         nmis: 
23,        nret:0
Page:143,        dup:1,  nrec:0,         ncan:0,         nmis: 
506,       nret:0
Page:140,        dup:0,  nrec:0,         ncan:0,         nmis: 
1,         nret:0
Page:142,        dup:0,  nrec:0,         ncan:0,         nmis: 
24,        nret:0
Page:141,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)
Page:218,        dup:0,  nrec:0,         ncan:0,         nmis: 
0,         nret:0         (empty)


Number of empty pages: 11
Number of pages with vaild entries: 2
Number of pages processed: 38

This query returned 794 rows, while 1000 rows were expected

/Lars-Erik
Thread
Some more on IndexWalkersLars-Erik Bjørk14 May
  • Re: Some more on IndexWalkersKevin Lewis14 May
    • Re: Some more on IndexWalkersLars-Erik Bjørk14 May
      • RE: Some more on IndexWalkersVladislav Vaintroub14 May
  • Re: Some more on IndexWalkersAnn W. Harrison15 May
    • Re: Some more on IndexWalkersLars-Erik Bjørk18 May
    • Re: Some more on IndexWalkersLars-Erik Bjørk18 May
      • Re: Some more on IndexWalkersKevin Lewis18 May
        • Re: Some more on IndexWalkersLars-Erik Bjørk18 May
      • Re: Some more on IndexWalkersJim Starkey18 May
Re: Some more on IndexWalkersLars-Erik Bjørk14 May