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

On Mon, Oct 28, 2024 at 12:38 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> Attached is v12, which is yet another revision required only so that
> the patch's latest version applies cleanly on top of master.

Attached is v13, which is the first revision posted that has new
functional changes in quite some time (this isn't just for fixing
bitrot).

The notable change for v13 is the addition of preprocessing that
adjusts skip array attributes > and < operators. These are used for
initial position purposes by _bt_first -- the purpose of this new
preprocessing/transformation is to minimize the number of descents of
the index in certain corner cases involving > and < operators, by
converting them into similar >= and <= operators during preprocessing
where possible. This transformation relies on the opclass skip support
routine, and is strictly optional.

Imagine a qual like "WHERE a > 5" AND b = 3". This will use a range
style skip array on "a", and a regular required scan key on "b". The
new transformation makes the final scan keys output by preprocessing
match what you'd get if the qual had been written "WHERE a >= 6 AND b
= 3". This leads to a modest reduction in the number of descents
required in some cases. It's possible that a naive "a > 5" initial
descent within _bt_first would have wastefully landed on an earlier
leaf page. Whereas now, with v13, our more discriminating "a >= 6 AND
b = 3" initial _bt_first descent will manage to land directly on the
true first page (the inclusion of "b = 3" in the first _bt_first call
makes this possible).

Obviously, the new transformation won't help most individual calls to
_bt_first when a skip array (with a low_compare inequality) is used,
since most individual calls will already have a real skip array
element value (not just the sentinel value -inf or +inf) to work off
of. This is not an essential optimization (it only optimizes the first
_bt_first call for the whole skip scan), but it seems worth having.
Very early versions of the patch had this same optimization, though
that was implemented in a way that wasn't compatible with cross-type
operators. The approach taken in v13 has no such problems, and does
things in a way that's very well targeted -- there's no impact on any
of the other preprocessing steps.

--
Peter Geoghegan