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

On Tue, Mar 18, 2025 at 3:15 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> I've actually come around to your point of view on this (or what I
> thought was your PoV from our call). That is, I now *think* that it
> would be better if the code added by 0003-* called
> _bt_skip_ikeyprefix, without regard for whether or not we'll have a
> finaltup _bt_checkkeys call to "recover" (i.e. whether we're on the
> leftmost or rightmost page shouldn't matter).
>
> My change in perspective on this question is related to another change
> of perspective, on the question of whether we actually need to call
> _bt_start_array_keys as part of "recovering/restoring the array
> invariant", just ahead of the finaltup _bt_checkkeys call. As you
> know, 0003-* calls _bt_start_array_keys in this way, but that now
> seems like overkill. It can have undesirable side-effects when the
> array keys spuriously appear to advance, when in fact they were
> restarted via the _bt_start_array_keys call, only to have their
> original values restored via the finaltup call that immediately
> follows.

> Tying it back to your concern, once I do that (once I stop calling
> _bt_start_array_keys in 0003-* to "hard reset" the arrays), I can also
> stop caring about finaltup being set on the rightmost page, at the
> point where we decide if _bt_skip_ikeyprefix should be called.

Attached is v29, which teaches _bt_skip_ikeyprefix to do things along
these lines (_bt_skip_ikeyprefix is added by 0003-*, same as last
time) . That's the first notable change for v29.

> > The code halts optimizing "prefix prechecks" when we notice a
> > non-equality key. It seems to me that we can do the precheck on shared
> > prefixes with non-equality keys just the same as with equality keys;
> > and it'd improve performance in those cases, too.
>
> Yeah, I was thinking of doing this already (though not for RowCompare
> inequalities, which would be hard to evaluate from here). It makes
> sense because it's exactly the same case as the range skip array case,
> really -- why not just do it the same way?

Second notable change for v29:

v29 also teaches 0003-* to handle plain inequalities (not just range
skip arrays) within _bt_skip_ikeyprefix, as I outlined to Matthias
here.

FWIW this doesn't really help much in practice, because scans that
benefit only do so to a limited degree, under fairly narrow
circumstances (I can explain what I mean by that if you're interested,
but it's not all that interesting). Even still, as I said the other
day, I think that it's worth doing this on consistency grounds. The
underlying rules that make this safe are literally identical to the
rules for range skip arrays (where determining if a key can be skipped
in _bt_skip_ikeyprefix tends to be much more important), so not doing
it with simple lower-order inequalities could confuse the reader.

Third notable change for v29:

Quite a few small improvements have been made to our new cost model,
in selfuncs.c/btcostestimate (see 0002-*, the main commit/patch that
introduces skip scan). The code is much better commented, and is more
idiomatic.

Most notably, I'm now using clauselist_selectivity() to adjust
ndistinct, as part of estimating the scan's num_sa_scans (I'm no
longer doing that in an ad-hoc way). The control flow is a lot easier
to understand. There are now a couple of new cases where we
conservatively fall back on using the old costing (i.e. we cost the
scan as if it was a Postgres 17 full index scan) for lack of a better
idea about what to do. We do this when we detect a default/generic
ndistinct estimate (we chicken out there), and we do it when we see a
range of values/a set of RestringInfos against a single column whose
selectivity is already relatively high (specifically, under
DEFAULT_RANGE_INEQ_SEL, meaning a selectivity that's under half a
percentage point).

Here are my plans around committing the patches:

* 0001-* can be committed within a matter of days. Probably before the
week is out.

It is commitable now, and is independently useful work.

* The remaining patches in the patch series (0002-* through to 0004-*)
are very close to being committable, but are still not quite ready.

I'm going to hold off on committing the big patches until late next
week, at the earliest. My current best estimate is that the bulk of
this work (0002-* through to 0004-*) will be committed together, on or
about April 2 (I suppose that I could commit 0004-* a few days later,
just to give things time to settle, but it wouldn't make sense to
commit 0002-* without also committing 0003-* immediately afterwards).

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. In short, I
need to think long and hard about the stuff I described under "Here's
how I think that this will be safe:" in my email to Matthias from
yesterday. The precondition and postcondition assertions in
_bt_advance_array_keys (added to Postgres 17) remain effective, which
gives me a certain amount of confidence in the changes made by 0003-*.

Thanks
--
Peter Geoghegan