List:Falcon Storage Engine« Previous MessageNext Message »
From:Lars-Erik Bjørk Date:May 18 2009 8:45am
Subject:Re: Some more on IndexWalkers
View as plain text  
Hi Ann, see my comment below.

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

I think I have misused the term expand a little here. The first entry of
  a page is expanded in the sense that it is not compressed in any way,
but unless it is also the first entry of the very first page we look  
at, I don't
think it is "expanded" by calling node.expandKey(&indexKey).

I had a day off on Friday, but I will look closer into your and Vlad's  
theories
today:)

Thanks!

>
> Cheers,
>
> Ann

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