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

On Wed, Mar 19, 2025 at 5:08 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> The tricky logic added by 0003-* is my single biggest outstanding
> concern about the patch series. Particularly its potential to confuse
> the existing invariants for required arrays. And particularly in light
> of the changes that I made to 0003-* in the past few days.

A big part of the concern here is with the existing pstate.prechecked
optimization (the one added to Postgres 17 by Alexander Korotkov's
commit e0b1ee17). It now seems quite redundant -- the new
_bt_skip_ikeyprefix mechanism added by my 0003-* patch does the same
thing, but does it better (especially since I taught
_bt_skip_ikeyprefix to deal with simple inequalities in v29). I now
think that it makes most sense to totally replace pstate.prechecked
with _bt_skip_ikeyprefix -- we should use _bt_skip_ikeyprefix during
every scan (not just during skip scans, not just during scans with
SAOP array keys), and be done with it.

To recap, right now the so->scanBehind flag serves two roles:

1. It lets us know that it is unsafe to apply the pstate.prechecked
optimization when _bt_readpage gets to the next page.

2. It lets us know that a recheck of the finaltup tuple is required on
the next page (right now that is limited to forwards scans that
encounter a truncated high key, but I intend to expand it in the
0001-* patch to other cases where we want to move onto the next page
without being 100% sure that it's the right thing to do).

Role #1 is related to the fact that pstate.prechecked works in a way
that doesn't really know anything about SAOP array keys. My Postgres
17 commit 5bf748b8 added role #1, to work around the problem of the
precheck being confused in cases where the scan's array keys are
advanced before we reach the final tuple on the page (the precheck
tuple). That way, scans with array keys were still able to safely use
the pstate.prechecked optimization, at least in simpler cases.

The new, similar _bt_skip_ikeyprefix mechanism has no need to check
scanBehind like this. That's because it is directly aware of both SAOP
arrays and skip arrays (it doesn't actually examine the sk_argument
from a scan key associated with an array, it just looks at the array
itself). That's a big advantage -- especially in light of the
scheduling improvements from 0001-*, which will make many more
_bt_readpage calls see the so->scanBehind flag as set (making us not
use pstate.prechecked). The new scheduling stuff from 0001-* affects
scans with skip arrays and SAOP arrays in just the same way, and yet
right now there's an unhelpful disconnect between what each case will
do once it reaches the next page. This is probably the single biggest
point that makes pstate.prechecked seem like it clashes with
_bt_skip_ikeyprefix: it undermines the principle that array type (SAOP
array vs skip array) should not matter anywhere outside of the lowest
level nbtutils.c code, which is a principle that now seems important.

Another key advantage of the _bt_skip_ikeyprefix mechanism is that it
can plausibly work in many cases that pstate.prechecked currently
can't handle at all. The design of pstate.prechecked makes it an "all
or nothing" thing -- it either works for every scan key required in
the scan direction, or it works for none at all. Not so for
_bt_skip_ikeyprefix; it can set pstate.ikey to skip a prefix of = scan
keys (a prefix of keys known to satisfy all tuples on pstate.page),
without the prefix necessarily including every = scan key. That
flexibility could matter a lot.

Furthermore, it can do this (set pstate.ikey to a value greater than
0) *without* needing to set pstate.forcenonrequired to make it safe
(pstate.forcenonrequired must be set during scans with array keys to
set pstate.ikey to a non-zero value, but otherwise doesn't need to be
set). In other words, it's possible for most scans to use
_bt_skip_ikeyprefix without having to commit themselves to scan all of
the tuples on the page (unlike pstate.prechecked).

I'm pretty sure that this is the right direction already, for the
reasons given, but also because I already have a draft version that
passes all tests. It significantly improves performance in many of my
most important microbenchmarks: unsympathetic cases that previously
had 5%-10% regression in query execution time end up with only 2% - 5%
regressions. I think that that's because the draft patch completely
removes the "prechecked" code path from _bt_check_compare, which is a
very hot function -- especially during these adversarial
microbenchmarks.

Under this new scheme, so->scanBehind is strictly a flag that
indicates that a recheck is scheduled, to be performed once the scan
calls _bt_readpage for the next page. It no longer serves role #1,
only role #2. That seems significantly simpler.

Note that I'm *not* proposing to remove/replace the similar
pstate.firstmatch optimization (also added by Alexander Korotkov's
commit e0b1ee17). That's still independently useful (it'll complement
_bt_skip_ikeyprefix in just the same way as it complemented
pstate.prechecked).

--
Peter Geoghegan