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

On Wed, Feb 5, 2025 at 6:43 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> The way that the "skipskip" optimization works is unchanged in v23.
> And even the way that we decide whether to apply that optimization
> didn't really change, either. What's new in v23 is that
> v23-0003-*patch adds rules around primitive scan scheduling.
> Obviously, I specifically targeted Heikki's regression when I came up
> with this, but the new _bt_advance_array_keys rules are nevertheless
> orthogonal: even scans that just use conventional SAOP arrays will
> also use these new _bt_advance_array_keys heuristics (though it'll
> tend to matter much less there).

Attached is v24, which breaks out these recent changes to primscan
scheduling into their own commit/patch (namely
v24-0002-Improve-nbtree-SAOP-primitive-scan-scheduling.patch). The
primscan scheduling improvement stuff hasn't really changed since
v23, though (though I did polish it some more). I hope to be able to
commit this new primscan scheduling patch sooner rather than later
(though I don't think that it's quite committable yet). It is
technically an independent improvement to the scheduling of primitive
index scans during SAOP nbtree index scans, so it makes sense to get
it out of the way.

The changes in v24 aren't just structural. The real changes in v24 are
to the optimization previously known as the "skipskip" optimization,
which now appears alone in
v24-0004-Lower-the-overhead-of-nbtree-runtime-skip-checks.patch (since
I broke out the other changes into their own patch). I guess it's
called the "_bt_skip_ikeyprefix" optimization now, since that's the
name of the function that now activates the optimization (the function
that is sometimes called from _bt_readpage during so->skipScan scans).
It seemed better to place the emphasis on starting calls to
_bt_check_compare with a later pstate.ikey (i.e. one greater than 0),
since that's where most of the benefit comes from.

We now treat all of the scan's arrays as nonrequired when the
_bt_skip_ikeyprefix optimization is activated -- even skip arrays can
have nonrequired calls to _bt_advance_array_keys from
_bt_check_compare (that won't just happen for the scan's SAOP arrays
in v24). This approach seems clearer to me. More importantly, it
performs much better than the previous approach in certain complicated
cases involving multiple range skip arrays against several different
index columns. (I can elaborate on what those queries look like and
why they're better with this new approach, if anybody wants me to.)

--
Peter Geoghegan