Subject: btree: downlink right separator/HIKEY optimization

From: Matthias van de Meent <[email-masked]>
Date: Tue, 31 Oct 2023 23:08:04 +0100

(now really to -hackers)
Hi,

Over at [0] I'd implemented an optimization that allows us to skip
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.

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).

By adding this, the number of _bt_compare calls per _bt_search is
often reduced by one per btree level.

Kind regards,

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

PS. Best served with dynamic prefix truncation [1] and btree specialization [0].

[0] https://www.postgresql.org/message-id/CAEze2WiqOONRQTUT1p_ZV19nyMA69UU2s0e2dp+jSBM=[email-masked]
[1] https://www.postgresql.org/message-id/flat/CAEze2Wh-h20DmPSMXp4qHR0-ykh9=[email-masked]

---

From: Heikki Linnakangas <[email-masked]>
Date: Tue, 5 Dec 2023 09:43:20 +0200

> separator key bytewise, excluding the data stored in the

Good observation.

> 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)

---

From: vignesh C <[email-masked]>
Date: Sat, 6 Jan 2024 21:09:56 +0530

> often reduced by one per btree level.

CFBot shows the following compilation error at [1]:
[16:56:22.153] FAILED:
src/backend/postgres_lib.a.p/access_nbtree_nbtsearch.c.obj
[16:56:22.153] "cl" "-Isrc\backend\postgres_lib.a.p" "-Isrc\include"
"-I..\src\include" "-Ic:\openssl\1.1\include"
"-I..\src\include\port\win32" "-I..\src\include\port\win32_msvc"
"/MDd" "/FIpostgres_pch.h" "/Yupostgres_pch.h"
"/Fpsrc\backend\postgres_lib.a.p\postgres_pch.pch" "/nologo"
"/showIncludes" "/utf-8" "/W2" "/Od" "/Zi" "/DWIN32" "/DWINDOWS"
"/D__WINDOWS__" "/D__WIN32__" "/D_CRT_SECURE_NO_DEPRECATE"
"/D_CRT_NONSTDC_NO_DEPRECATE" "/wd4018" "/wd4244" "/wd4273" "/wd4101"
"/wd4102" "/wd4090" "/wd4267" "-DBUILDING_DLL" "/FS"
"/FdC:\cirrus\build\src\backend\postgres_lib.pdb"
/Fosrc/backend/postgres_lib.a.p/access_nbtree_nbtsearch.c.obj "/c"
../src/backend/access/nbtree/nbtsearch.c
[16:56:22.153] ../src/backend/access/nbtree/nbtsearch.c(112): error
C2143: syntax error: missing ';' before 'type'
[16:56:22.280] ../src/backend/access/nbtree/nbtsearch.c(112): warning
C4091: ' ': ignored on left of 'int' when no variable is declared

[1] - https://cirrus-ci.com/task/4634619035779072

Regards,
Vignesh

---

From: Matthias van de Meent <[email-masked]>
Date: Thu, 22 Feb 2024 16:42:40 +0100

On Sat, 6 Jan 2024 at 16:40, vignesh C <[email-masked]> wrote:
> [...]

I forgot to address this in the previous patch, so here's v3 which
fixes the issue warning.

Kind regards,

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