List:Falcon Storage Engine« Previous MessageNext Message »
From:Kevin Lewis Date:May 14 2009 1:25pm
Subject:Re: Some more on IndexWalkers
View as plain text  
Lars-Erik,

So the first node on the page is out of order?  The unexpanded nodes after that would
match if they were expanded?  How can that be?

Lars-Erik Bjørk wrote:
> 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