Re: btree: downlink right separator/HIKEY optimization

On 01/11/2023 00:08, Matthias van de Meent wrote:
> calling _bt_compare in _bt_moveright in many common cases. This patch,
> when stacked on top of the prefix truncation patch, improves INSERT
> performance by an additional 2-9%pt, with an extreme case of 45% in
> the worscase index tests at [0].
> 
> The optimization is that we now recognze that our page split algorithm
> all but guarantees that the HIKEY matches this page's downlink's right
> separator key bytewise, excluding the data stored in the
> IndexTupleData struct.

Good observation.

> By caching the right separator index tuple in _bt_search, we can
> compare the downlink's right separator and the HIKEY, and when they
> are equal (memcmp() == 0) we don't have to call _bt_compare - the
> HIKEY is known to be larger than the scan key, because our key is
> smaller than the right separator, and thus transitively also smaller
> than the HIKEY because it contains the same data. As _bt_compare can
> call expensive user-provided functions, this can be a large
> performance boon, especially when there are only a small number of
> column getting compared on each page (e.g. index tuples of many 100s
> of bytes, or dynamic prefix truncation is enabled).

What would be the worst case scenario for this? One situation where the 
memcmp() would not match is when there is a concurrent page split. I 
think it's OK to pessimize that case. Are there any other situations? 
When the memcmp() matches, I think this is almost certainly not slower 
than calling the datatype's comparison function.

>         if (offnum < PageGetMaxOffsetNumber(page))
>         {
>             ItemId    rightsepitem = PageGetItemId(page, offnum + 1);
>             IndexTuple pagerightsep = (IndexTuple) PageGetItem(page, rightsepitem);
>             memcpy(rsepbuf.data, pagerightsep, ItemIdGetLength(rightsepitem));
>             rightsep = &rsepbuf.tuple;
>         }
>         else if (!P_RIGHTMOST(opaque))
>         {
>             /*
>              * The rightmost data tuple on inner page has P_HIKEY as its right
>              * separator.
>              */
>             ItemId    rightsepitem = PageGetItemId(page, P_HIKEY);
>             IndexTuple pagerightsep = (IndexTuple) PageGetItem(page, rightsepitem);
>             memcpy(rsepbuf.data, pagerightsep, ItemIdGetLength(rightsepitem));
>             rightsep = &rsepbuf.tuple;
>         }

This could use a one-line comment above this, something like "Remember 
the right separator of the downlink we follow, to speed up the next 
_bt_moveright call".

Should there be an "else rightsep = NULL;" here? Is it possible that we 
follow the non-rightmost downlink on a higher level and rightmost 
downlink on next level? Concurrent page deletion?

Please update the comment above _bt_moveright to describe the new 
argument. Perhaps the text from README should go there, this feels like 
a detail specific to _bt_search and _bt_moveright.

-- 
Heikki Linnakangas
Neon (https://neon.tech)