Re: Improving btree performance through specializing by key shape, take 2

On Thu, 1 Feb 2024 at 15:49, Matthias van de Meent
<boekewurm+postgres(at)gmail(dot)com> wrote:
> I've attached a rebased version, on top of HEAD @ 7b745d85. The
> changes for prefix compression [0] and the rightsep+hikey optimization
> [1] have been split off to separate patches/threads. I've also split
> previous patch number 0003 into multiple parts, to clearly delineate
> code movement vs modifications.

Rebased to v16 to fix bitrot from 8af25652.

Again, short explanation
========

Current nbtree code is optimized for short index keys, i.e. with few
attributes, and index keys with cacheable offsets
(pg_attribute.attcacheoff). This is optimized for many cases, but for
some index shapes (e.g. ON (textfield, intfield)) the current code
doesn't work nice and adds significant overhead during descent: We
repeatedly re-calculate attribute offsets for key attributes with
uncacheable offsets.

To fix this O(n^2) problem in _bt_compare(), the first idea was to use
attribute offset iteration (as introduced 0003). Measurements showed
that the changes do great work for uncacheable attribute offsets, but
reduce the performance of indexes with cached offsets significantly.
This meant that using this approach for all indexes was uneconomical:
we couldn't reuse the same code across all index key shapes.

To get around this performance issue, this patchset introduces
specialization. Various key functions inside the btree AM which have
hot paths that depend on key shape are "specialized" to one of 3
"index key shapes" identified in the patchset: "cached", "uncached",
and "single attribute".

Specialization is implemented with a helper header that #includes the
to-be-specialized code once for each index key shape. The
to-be-specialized code can then utilize several macros for iterating
over index key attributes in the most efficient way available for that
index key shape.

For specific implementation details, see the comments in the header of
include/access/nbtree_spec.h.

Patches
========

0001 moves code around without modification in preparation for specialization
0002 updates non-specialized code to hook into specialization
infrastructure, without yet changing functionality.
0003 updates to-be-specialized code to use specialized index attribute
iterators, and introduces the first specialization type "cached". This
is no different from our current iteration type; it just has a new
name and now fits in the scaffolding of specialization.
0004 introduces a helper function to be used in 0006, which calculates
and stores attcacheoff for cacheable attributes, while also (new for
attcacheoff) storing negative cache values (i.e. uncacheable) for
those attributes that can't have attcacheoff, e.g. those behind a size
of < 0.
0005 introduces the "single attribute" specialization, which realizes
that the first attribute has a known offset in the index tuple data
section, so it doesn't have to access or keep track of as much
information, which saves cycles in the common case of single-attribute
indexes.
0006 introduces the final, "uncached", specialization. It
progressively calculates offsets of attributes as needed, rather than
the start from scratch approach in indexgetattr().

Tradeoffs
========

This patch introduces a new CPP templating mechanism which is more
complex than most other templates currently in use. This is certainly
additional complexity, but the file structure used allow for a mostly
similar C programming experience, with the only caveat that the file
is not built into an object file directly, but included into another
file (and thus shouldn't #include its own headers).

By templating functions, this patch also increases the size of the
PostgreSQL binary. Bloaty measured a 48kiB increase in size of the
.text section of the binary (47MiB) built with debugging options at
[^0], while a non-debug build of the same kind [^1] (9.89MiB) has an
increase in size of 34.8kiB. Given the performance improvements
achievable using this patch, I believe this patch is worth the
increase in size.

Performance
========

I haven't retested the results separately yet, but I assume the
performance results of [2] hold mostly true in comparing 0002 vs 0007.
I will do a performance (re-)evaluation of only this patch if so
requested (or once I have time), but please do review the code, too.

Kind regards,

Matthias van de Meent

[^0] ./configure --enable-depend --enable-tap-tests --enable-cassert
--with-lz4 --enable-debug --with-zstd COPT='-O3 -g3'
--prefix=~/projects/postgresql/pg_install
[^1] ./configure --enable-depend --enable-tap-tests --with-lz4
--with-zstd COPT='-O3' --prefix=~/projects/postgresql/pg_install

[2] https://www.postgresql.org/message-id/CAEze2WiqOONRQTUT1p_ZV19nyMA69UU2s0e2dp%2BjSBM%3Dj8snuw%40mail.gmail.com