Re: Index range search optimization

Hi, Peter.

On Fri, Sep 29, 2023 at 4:57 AM Peter Geoghegan <pg@bowt.ie> wrote:
> On Fri, Sep 22, 2023 at 7:24 AM Alexander Korotkov <aekorotkov@gmail.com> wrote:
> > The thing is that NULLs could appear in the middle of matching values.
> >
> > # WITH t (a, b) AS (VALUES ('a', 'b'), ('a', NULL), ('b', 'a'))
> > SELECT a, b, (a, b) > ('a', 'a') FROM t ORDER BY (a, b);
> >  a |  b   | ?column?
> > ---+------+----------
> >  a | b    | t
> >  a | NULL | NULL
> >  b | a    | t
> > (3 rows)
> >
> > So we can't just skip the row comparison operator, because we can meet
> > NULL at any place.
>
> But why would SK_ROW_HEADER be any different? Is it related to this
> existing case inside _bt_check_rowcompare()?:
>
>         if (subkey->sk_flags & SK_ISNULL)
>         {
>             /*
>              * Unlike the simple-scankey case, this isn't a disallowed case.
>              * But it can never match.  If all the earlier row comparison
>              * columns are required for the scan direction, we can stop the
>              * scan, because there can't be another tuple that will succeed.
>              */
>             if (subkey != (ScanKey) DatumGetPointer(skey->sk_argument))
>                 subkey--;
>             if ((subkey->sk_flags & SK_BT_REQFWD) &&
>                 ScanDirectionIsForward(dir))
>                 *continuescan = false;
>             else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
>                      ScanDirectionIsBackward(dir))
>                 *continuescan = false;
>             return false;
>         }

Yes, exactly. Our row comparison operators don't match if there is any
null inside the row.  But you can find these rows within the matching
range.

> I noticed that you're not initializing so->firstPage correctly for the
> _bt_endpoint() path, which is used when the initial position of the
> scan is either the leftmost or rightmost page. That is, it's possible
> to reach _bt_readpage() without having reached the point in
> _bt_first() where you initialize so->firstPage to "true".

Good catch, thank you!

> It would probably make sense if the flag was initialized to "false" in
> the same way as most other scan state is already, somewhere in
> nbtree.c. Probably in btrescan().

Makes sense, initialisation is added.

------
Regards,
Alexander Korotkov