From: Lars-Erik Bjørk
Date: May 18 2009 8:45am
Subject: Re: Some more on IndexWalkers
List-Archive: http://lists.mysql.com/falcon/740
Message-Id: <8E4B82E6-642F-4C94-9B77-5817FB54F564@Sun.COM>
MIME-Version: 1.0
Content-Type: text/plain; delsp=yes; format=flowed; charset=ISO-8859-1
Content-Transfer-Encoding: QUOTED-PRINTABLE

Hi Ann, see my comment below.

On May 15, 2009, at 12:52 AM, Ann W. Harrison wrote:

> Lars-Erik Bj=F8rk wrote:
>> I have been looking at the remaining cases where we are returned t=
oo
>> few, or no, rows when doing a LIMIT query. It seems that when we f=
ind
>> a node with a recordNumber >=3D 0 as the first node on a page, we =
=20
>> forget to expand the key. I believed that this was deliberate, as =
=20
>> the key should already be
>> expanded, being identical to the last entry on the previous page. =
=20
>> Looking at this in the debugger however, this does not seem to be =
=20
>> the case.
>
> OK.  As an index is created and grows, the last entry on page n wil=
l
> 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 =20
> 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 wa=
y,
but unless it is also the first entry of the very first page we look =
=20
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 =20
theories
today:)

Thanks!

>
> Cheers,
>
> Ann