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

On Mon, 23 Jan 2023 at 14:54, Matthias van de Meent
<boekewurm+postgres(at)gmail(dot)com> wrote:
> On Fri, 20 Jan 2023 at 20:37, Matthias van de Meent
> <boekewurm+postgres(at)gmail(dot)com> wrote:
> > On Thu, 12 Jan 2023 at 16:11, David Christensen <david(at)pgguru(dot)net> wrote:
> > > Last I saw on the thread you were going to see if the specialization was required or not.
> >
> > Thank you for your interest, and sorry for the delayed response. I've
> > been working on rebasing and polishing the patches, and hit some
> > issues benchmarking the set. Attached in Perf_results.xlsx are the
> > results of my benchmarks, and a new rebased patchset.

Attached v10 which fixes one compile warning, and fixes
headerscheck/cpluspluscheck by adding nbtree_spec.h and
nbtree_specfuncs.h to ignored headers files. It also fixes some cases
of later modifications of earlier patches' code where the change
should be incorporated in the earlier patch instead.

I think this is ready for review, I don't .

The top-level design of the patchset:

0001 modifies btree descent code to use dynamic prefix compression,
i.e. skip comparing columns in binary search when the same column on
tuples on both the left and the right of this tuple have been compared
as 'equal'.

It also includes an optimized path when the downlink's tuple's right
neighbor's data is bytewise equal to the highkey of the page we
descended onto - in those cases we don't need to run _bt_compare on
the index tuple as we know that the result will be the same as that of
the downlink tuple, i.e. it compare as "less than".

NOTE that this patch when applied as stand-alone adds overhead for all
indexes, with the benefits of the patch limited to non-unique indexes
or indexes where the uniqueness is guaranteed only at later
attributes. Later patches in the patchset return performance to a
similar level as before 0001 for the impacted indexes.

0002 creates a scaffold for specializing nbtree functions, and moves
the functions I selected for specialization into separate files. Those
separate files (postfixed with _spec) are included in the original
files through inclusion of the nbtree specialization header file with
a macro variable. The code itself has not materially changed yet at
this point.

0003 updates the functions selected in 0002 to utilize the
specializable attribute iterator macros instead of manual attribute
iteration.

Then, 0004 adds specialization for single-attribute indexes,
0005 adds a helper function for populating attcacheoff (which is
separately useful too, but essential in this patchset), and
0006 adds specialization for multi-column indexes of which the offsets
of the last key column cannot be known.

Kind regards,

Matthias van de Meent.