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

On Fri, May 2, 2025 at 3:04 PM Peter Geoghegan <pg@bowt.ie> wrote:
> I would like to commit the first patch later today, ahead of shipping
> beta1. But the second patch won't make it into beta1.

Committed the first patch last Friday.

Attached is v2, whose 0002- bugfix patch is essentially unchanged
compared to v1 -- there are now comments explaining why RowCompare
keys cannot safely use the pstate.forcenonrequired behavior (in the
presence of a higher-order array). There is also a new 0001- patch
(not to be confused with the prior 0001- patch that I committed last
week).

I plan to commit everything in the next couple of days, barring any objections.

> The second patch is more complicated, and seems like something that
> I'll need to spend more time thinking about before proceeding with
> commit. It has subtle behavioral implications, in that it causes the
> pstate.forcenonrequired mechanism to influence when and how
> _bt_advance_array_keys schedules primitive index scans in a tiny
> minority of forward scan cases. I know of only 3 queries where this
> happens, 2 of which are from my repro -- it's actually really hard to
> find an example of this, even if you go out of your way to.

The new 0001- patch addresses these concerns of mine about
pstate.forcenonrequired affecting primscan scheduling.

It turned out that this unprincipled behavioral inconsistency was only
possible because of an inconsistency in how the recheck within
_bt_scanbehind_checkkeys works in the presence of relevant truncated
high key attributes -- an inconsistency compared to similar code
within _bt_advance_array_keys. Now (with the new 0001- patch applied),
we won't allow a scan with an "almost matching" set of array keys to
continue with reading the next page in the case where the keys merely
satisfy the next page's high key's untruncated attribute prefix values
-- we won't accept it when there's uncertainty due to other arrays
pertaining to attributes that are truncated within the next page's
high key/finaltup.

There is no reason to believe that this matters on correctness ground,
or even on performance grounds, but it does seem like the principled
approach. We shouldn't cross more than one leaf page boundary before
resolving our uncertainty about whether or not stepping to the next
leaf page (i.e. not starting another primscan) is the right thing to
do.

Note again that this is a very narrow issue: it could only happen when
we advanced the array keys on a page to values that just so happen to
be exact matches for the *next* page's high key, when there were
additional keys corresponding to truncated suffix attributes in that
same next page high key. The chances of things lining up like that are
very slim indeed. But, I find the behavioral inconsistency distracting
and unprincipled, and it's easy enough to just eliminate it
altogether. I haven't formally promised that calling _bt_set_startikey
must never affect the total number of primscans (relative to an
equivalent query/scan where we just don't call it), but that feels
like a good goal.

--
Peter Geoghegan