Re: Optimizing "boundary cases" during backward scan B-Tree index descents

On Mon, Jun 19, 2023 at 4:28 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> We still fall short when it comes to handling boundary cases optimally
> during backwards scans. This is at least true for a subset of
> backwards scans that request "goback=true" processing inside
> _bt_first. Attached patch improves matters here. Again, the simplest
> way of explaining what this does is through a practical worked
> example.

On further reflection, we should go even further in the direction of
teaching _bt_search (and related routines) about the initial leaf
level positioning requirements of backwards scans. In fact, we should
give _bt_search and friends exclusive responsibility for dealing with
initial positioning on behalf of _bt_first. Attached revision shows
how this can work.

This new direction is partly based on the observation that "goback" is
really just a synonym of "backwards scan initial positioning
behavior": all backwards scans already use "goback", while all forward
scans use "!goback". So why shouldn't we just change any "goback"
symbol names to "backward", and be done with it? Then we can move the
"step back one item on leaf level" logic from _bt_first over to
_bt_binsrch. Now _bt_search/_bt_binsrch/_bt_compare own everything to
do with initial positioning.

The main benefit of this approach is that it allows _bt_first to
describe how its various initial positioning strategies work using
high level language, while pretty much leaving the implementation
details up to _bt_search. I've always thought that it was confusing
that the "<= strategy" uses "nextkey=true" -- how can it be "next key"
while also returning keys that directly match those from the insertion
scankey? It only makes sense once you see that the "<= strategy" uses
both "nextkey=true" and "backwards/goback = true" -- something that
the structure in the patch makes clear and explicit.

This revision also adds test coverage for the aforementioned "<=
strategy" (not to be confused with the strategy that we're
optimizing), since it was missing before now. It also adds test
coverage for the "< strategy" (which *is* the strategy affected by the
new optimization). The "< strategy" already has decent enough coverage
-- it just doesn't have coverage that exercises the new optimization.
(Note that I use the term "new optimization" advisedly here -- the new
behavior is closer to "how it's really supposed to work".)

I'm happy with the way that v2 came out, since the new structure makes
a lot more sense to me. The refactoring is probably the most important
aspect of this patch. The new structure seems like it might become
important in a world with skip scan or other new MDAM techniques added
to B-Tree. The important principle here is "think in terms of logical
key space, not in terms of physical pages".

Adding this to the next CF.

--
Peter Geoghegan