Re: Optimizing "boundary cases" during backward scan B-Tree index descents

On Sun, 15 Oct 2023 at 22:56, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>
> On Mon, Sep 18, 2023 at 4:58 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> > Attached is v3, which is a straightforward rebase of v2. v3 is needed
> > to get the patch to apply cleanly against HEAD - so no real changes
> > here.
>
> Attached is v4. Just to keep CFTester happy.

> @@ -402,10 +405,27 @@ _bt_binsrch(Relation rel,
> + if (unlikely(key->backward))
> + return OffsetNumberPrev(low);
> +
> return low;

I wonder if this is (or can be) optimized to the mostly equivalent
"return low - (OffsetNumber) key->backward", as that would remove an
"unlikely" branch that isn't very unlikely during page deletion, even
if page deletion by itself is quite rare.
I'm not sure it's worth the additional cognitive overhead, or if there
are any significant performance implications for the hot path.

> @@ -318,9 +318,12 @@ _bt_moveright(Relation rel,
> [...]
> * On a leaf page, _bt_binsrch() returns the OffsetNumber of the first
> [...]
> + * key >= given scankey, or > scankey if nextkey is true for forward scans.
> + * _bt_binsrch() also "steps back" by one item/tuple on the leaf level in the
> + * case of backward scans. (NOTE: this means it is possible to return a value
> + * that's 1 greater than the number of keys on the leaf page. It also means
> + * that we can return an item 1 less than the first non-pivot tuple on any
> + * leaf page.)

I think this can use a bit more wordsmithing: the use of "also" with
"steps back" implies we also step back in other cases, which aren't
mentioned. Could you update the wording to be more clear about this?

> @@ -767,7 +787,7 @@ _bt_compare(Relation rel,
> [...]
> - * Most searches have a scankey that is considered greater than a
> + * Forward scans have a scankey that is considered greater than a

Although it's not strictly an issue for this patch, the comment here
doesn't describe backward scans in as much detail as forward scans
here. The concepts are mostly "do the same but in reverse", but the
difference is noticable.

Apart from these comments, no further noteworthy comments. Looks good.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)