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

On Fri, Jan 24, 2025 at 10:38 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> I can reproduce this. However, it should be noted that the regression
> completely goes away if I make one small change to your test case: all
> I need to do is make sure that the CREATE INDEX happens *before*
> inserting any rows into the table. Once I do that, suffix truncation
> tends to be quite a bit more effective. This makes all the difference
> with your test case, since it encourages the existing heuristics
> within _bt_advance_array_keys to do the right thing and stick on the
> leaf level. That allows the "skipskip" mechanism to kick in as
> expected, which doesn't seem to be happening when the index is built
> by CREATE INDEX.

I think that I could have done better at explaining myself here. I'll
have another go at that:

Your test case showed an excessive number of primitive index scans:
EXPLAIN ANALYZE showed "Index Searches: 21859", even though the ideal
number of index searches is 1, given all these specifics. It would be
understandable if a person saw that and concluded that the added
overhead/regression comes from descending the index many more times
than is truly necessary -- blaming the added overhead that comes from
all those extra _bt_search calls is a good guess. But that's not it.
Not really.

You (Heikki) didn't actually make any claims about _bt_search being
too hot during profiling of this test case. You didn't actually see
_bt_search show up prominently when you ran "perf". What you actually
saw (and actually complained about) was stuff that is called from
_bt_readpage, to deal with array maintenance. Even still, I want to
avoid making this any more confusing than it needs to be. The nature
of the problem needs to be carefully teased apart.

There is an important sense in which the issue of excessive primitive
index scans *is* related to the regression from wasting cycles on
array maintenance, though only indirectly: the heuristics that decide
if the skipskip mechanism should be enabled during a _bt_readpage call
are indirectly influenced by certain other heuristics, in
_bt_advance_array_keys.
These other heuristics are the heuristics that determine
whether or not we'll start another primitive index scan (all of which
are in _bt_advance_array_key, and were added in Postgres 17, and
haven't been touched by this patch series).

More concretely: if we choose to start another primitive index scan,
and make a bad choice (because we land on the very next sibling leaf
page when we could gotten to by simply stepping right without calling
_bt_first/_bt_search again), then we also won't have an opportunity to
apply the skipskip mechanism when on that same sibling leaf page.
That's because in practice every leaf page read within _bt_readpage
will be the first leaf page of the ongoing primitive index scan with
this test case. Being the first leaf page of a primscan supposedly
makes a leaf page a bad target for the skipskip optimization, and so
we never actually apply the skipskip optimization in practice here.

Again, the real problem is simply that we're not applying the skipskip
optimization at all -- even though it was specifically written with
cases like Heikki's adversarial case in mind, and even though it
actually works as designed once it is forced to activate with Heikki's
test case. It may also be a bit of a problem that there's 21859 calls to
_bt_search instead of just 1, but that's a surprisingly small
contributor to the added overhead. (I'll probably fix the problem by
avoiding useless primitive index scans in the first place, rather than
by changing the heuristics that activate skipskip, which condition the
use of skipskip on firstPage=false. But, again, that doesn't mean that
the problem is excessive primscan overhead from all of the extra
_bt_first/_bt_search calls. The problem is indirect, and so my solution
can be indirect, too.)

--
Peter Geoghegan