List:Falcon Storage Engine« Previous MessageNext Message »
From:Jim Starkey Date:May 18 2009 3:59pm
Subject:Re: Some more on IndexWalkers
View as plain text  
Lars, I believe you are correct.  It is necessary to set up indexKey to 
reflect the first index on the page so subsequent calls to expandKey 
will have the desired result.

It is also correct that assuming the historical BUCKET_END key value is 
the same as the current first value on the next page is a bug waiting to 
happen.

Lars-Erik Bjørk wrote:
> Hi Ann!
>
> Reading your e-mail again, I believe that adding the
> following piece of code will be the right thing to do:
>
>     for (;; first = true)
>         {
>         if (first)
>             {
>             first = false;
>             recordNumber = node.getNumber();
>
>             if (recordNumber >= 0)
>                 {
>                 node.expandKey(&indexKey); // This line
>                 return recordNumber;
>                 }
>
> Given your explanation, I don't think it works if the BUCKET_END key 
> over time
> diverges from the first entry in the next block unless we add this 
> line (unless the search
> only touches a single page).
>
> /Lars-Erik
>
> Btw, thank you for your nice explanation :)
>
> On May 15, 2009, at 12:52 AM, Ann W. Harrison wrote:
>
>> Lars-Erik Bjørk wrote:
>>> 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.
>>
>> OK.  As an index is created and grows, the last entry on page n will
>> be the same as the first entry on page n + 1 and the first entry on
>> each page will be completely expanded.
>>
>> The reason for expanding the first node completely is that we
>> look at the first entry on an index page without having looked
>> at the previous page as we're coming down from the top.
>>
>> The reason for duplicating entries is to avoid the cost of
>> looking at the next page if the first entry on the next page
>> is not in the range we want.  The last entry on a page is
>> NOT a valid index node and should not be used to look up
>> a candidate record.  If the key value of the last entry is
>> in range, the look up should resume with the first entry on
>> the next page.
>>
>> That's the case when we're adding entries to an index.  When we
>> remove entries, the rules change somewhat - and my guess is that
>> they change too much.  A specific difference, as Vlad pointed out,
>> happens when you remove the first entry on a page.  It's OK not
>> to move the new first value to the previous page.  If you remove
>> the first entry on a page, the next entry is either the same or
>> higher.  In either case, the last entry on the previous page still
>> marks the end of range acceptably.  There's some loss of optimization -
>> you may read page n + 1 thinking that the first value is in range
>> based on the last value on page n, and find that the first actual
>> value on that page is not in range - and old in-range value having
>> been removed.
>>
>> However, if we don't expand the new first entry, all hell breaks
>> loose.  So,
>>
>> 1) The value of the last entry on a page is usually the
>> same as the first entry on the next page.
>>
>> 2) The value of the last entry on a page is is never greater
>> than the value of the first entry on the next page.
>>
>> 3) The first entry on each page is completely expanded.
>>
>> If #3 isn't true, it should be.
>>
>>
>> Cheers,
>>
>> Ann
>>
>> -- 
>> Falcon Storage Engine Mailing List
>> For list archives: http://lists.mysql.com/falcon
>> To unsubscribe:    
>> http://lists.mysql.com/falcon?unsub=1
>>
>
>


-- 
Jim Starkey
President, NimbusDB, Inc.
978 526-1376

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