Re: Index range search optimization

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.

------
Regards,
Alexander Korotkov