Re: Index range search optimization

Hi!

On Fri, 29 Sept 2023 at 10:35, Alexander Korotkov <aekorotkov(at)gmail(dot)com> wrote:
>
> Hi, Peter.
>
> On Fri, Sep 29, 2023 at 4:57 AM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> > On Fri, Sep 22, 2023 at 7:24 AM Alexander Korotkov <aekorotkov(at)gmail(dot)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.
I've looked through the patch v8. I think it's good enough to be
pushed if Peter has no objections.

Regards,
Pavel.