Re: Adding skip scan (including MDAM style range skip scan) to nbtree

On Fri, 18 Oct 2024 at 18:17, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Wed, Oct 16, 2024 at 1:14 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > Attached is v10, which is another revision that's intended only to fix
> > bit rot against the master branch. There are no notable changes to
> > report.
>
> Attached is v11, which is yet another revision whose sole purpose is
> to fix bit rot/make the patch apply cleanly against the master
> branch's tip.

This is a review on v11, not the latest v13. I suspect most comments
still apply, but I haven't verified this.

Re: design

I'm a bit concerned about the additional operations that are being
added to the scan. Before this patch, the amount of work in the
"horizontal" portion of the scan was limited to user-supplied
scankeys, so O(1) even when the index condition is only (f < 7). But,
with this patch, we're adding work for (a=, b=, c=, etc.) for every
tuple in the scan.
As these new "skip array" keys are primarily useful for inter-page
coordination (by determining if we want to start a primitive scan to
skip to a different page and which value range that primitive scan
would search for, or continue on to the next sibling), can't we only
apply the "skip array" portion of the code at the final tuple we
access on this page?

> +++ b/doc/src/sgml/indices.sgml
[...]
> +   leading prefix column, but this is usually much less efficient than a scan
> +   of an index without the extra prefix column.  See <xref

I think this last part is a bit more clear about what should go
without the prefix column when formulated as follows:

[...], but this is usually much less efficient than scanning an index
without the extra prefix column.

> -   would be almost useless for queries involving only <literal>y</literal>, so it
> -   should not be the only index.  A combination of the multicolumn index
> -   and a separate index on <literal>y</literal> would serve reasonably well.  For
> +   would be less useful for queries involving only <literal>y</literal>.  Just
> +   how useful might depend on how effective the B-Tree index skip scan
> +   optimization is; if <literal>x</literal> has no more than several hundred

While this section already defines some things about index scans which
seem btree-specific, I don't think we should add more references to
btree scan internals in a section about bitmaps and bitmap index
scans. While presumably btree is the most commonly used index type,
I'm not sure if we should just assume that's the only one that does
efficient non-prefix searches. GIN, for example, is quite efficient
for searches on non-primary columns, and BRIN's performance also
generally doesn't care about which column of the index is searched.

> +++ b/src/backend/access/nbtree/nbtree.c
[...]
> -    slock_t        btps_mutex;        /* protects above variables, btps_arrElems */
> +    LWLock        btps_lock;        /* protects above variables, btps_arrElems */

Why is this changed to LWLock, when it's only ever acquired exclusively?

> +btestimateparallelscan(Relation rel, int nkeys, int norderbys)

I notice you're using DatumSerialize. Are there reasons why we
wouldn't want to use heap_fill_tuple, which generally produces much
more compact output?

Also, I think you can limit the space usage to BLCKSZ in total,
because a full index tuple can't be larger than 1/3rd of a block; and
for skip scans we'll only have known equality bounds for a prefix of
attributes available in the index tuples, and a single (?)
index-produced dynamic attribute we want to skip ahead of. So, IIUC,
at most we'll have 2 index tuples' worth of data, or 2/3 BLCKSZ.
Right?

> +++ b/src/backend/access/nbtree/nbtsearch.c
[...]
> +     * Skip scan works by having _bt_preprocess_keys cons up = boundary keys

I needed to look up what this 'cons up' thing is, as it wasn't
something that I'd seen before. It also seems used exclusively in
btree code, and only after the array keys patch, so I think it'd be
better in general to use 'construct' here.

> +++ b/src/backend/access/nbtree/nbtcompare.c

The changes here are essentially 6x the same code, but for different
types. What do you think about the attached
0001-Deduplicate[...].patch.txt, which has the same effect but with
only 1 copy of the code checked in?

> +++b/src/backend/access/nbtree/nbtutils.c
[...]
> +_bt_decide_skipatts(IndexScanDesc scan, BTSkipPreproc *skipatts)

Why does this stop processing keys after hitting a row compare?
Doesn't skip scan still apply to any subsequent normal keys? E.g.
"c=1" creates a scan "a=skip, b=skip, c=1", so "(a, b)>(1, 2), c=1"
should IMO still allow a skip scan for a=skip, b=1 to be constructed -
it shouldn't be that we get a much less specific (and potentially,
performant) scan just by adding a rowcompare scankey on early
attributes.

> _bt_preprocess_array_keys
> -                output_ikey = 0;
> +                numArrayKeyData,
> +                numSkipArrayKeys;

I don't think numArrayKeyData/arrayKeyData are good names here, as it
confused me many times reviewing this function's changes. On a scankey
of a=1,b=2 we won't have any array keys, yet this variable is set to
2. Something like numOutputKeys is probably more accurate.

> +        /* Create a skip array and scan key where indicated by skipatts */
> +        while (numSkipArrayKeys &&
> +               attno_skip <= scan->keyData[input_ikey].sk_attno)
> +        {
> +            Oid            opcintype = rel->rd_opcintype[attno_skip - 1];
> +            Oid            collation = rel->rd_indcollation[attno_skip - 1];
> +            Oid            eq_op = skipatts[attno_skip - 1].eq_op;
> +            RegProcedure cmp_proc;
> +
> +            if (!OidIsValid(eq_op))
> +            {
> +                /* won't skip using this attribute */
> +                attno_skip++;

Isn't this branch impossible, given that numSkipArrayKeys is output
from _bt_decide_skipatts, whose output won't contain skipped
attributes which have eq_op=InvalidOid? I'd replace this with
Assert(OidIsValid(eq_op)).

> _bt_rewind_nonrequired_arrays

What types of scan keys can still generate non-required array keys? It
seems to me those are now mostly impossible, as this patch generates
required skip arrays for all attributes that don't yet have an
equality key and which are ahead of any (in)equality keys, except the
case with row compare keys which I already commented on above.

> utils/skipsupport.[ch]
I'm not sure why this is included in utils - isn't this exclusively
used in access/nbtree/*?

> +++ b/src/include/access/nbtree.h
BTArrayKeyInfo explodes in size, from 24B to 88B. I think some of that
is necessary, but should it really be that large?


Kind regards,

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