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

On Fri, Jan 24, 2025 at 10:07 PM Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:
> On my laptop, this is the worst case I could come up with:
>
> create table skiptest as select g / 10 as a, g%10 as b from
> generate_series(1, 10000000) g;
> vacuum freeze skiptest;
> create index on skiptest (a, b);
>
> set enable_seqscan=off; set max_parallel_workers_per_gather=0;
>
> \timing on
>
> After repeating a few times, to warm the cache:
>
> postgres=# select count(*) from skiptest where b=1;
> count
> ---------
> 1000000
> (1 row)

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.

Of course, this doesn't make your adversarial case invalid. But it
does suggest a solution: Maybe nbtsort.c could be taught to be more
careful about "picking a split point", matching the behavior of
nbtsplitloc.c. Alternatively, I could invent some new heuristics with
this issue in mind.

I already had an open item in my personal TODO. That open item
concerns backwards scans, which don't use the high key within
_bt_advance_array_keys. As such they cannot really expect to benefit
in the same way by my suggested changes to nbtsort.c.

Your adversarial case is probably exactly the same issue as the
backwards scan issue I plan on looking into, even though you used a
forward scan + CREATE INDEX. So I probably need a solution that'll
work just as well, regardless of how effective suffix truncation is
(since backwards scans will never have a "low key" to consider what's
likely to be on the next page in any case).

> Aside from the performance of those routines, it doesn't feel very
> intuitive. _bt_checkkeys() not only checks the current keys, but it can
> also read ahead tuples on the same page and update the array keys.

True. But none of that is new. That's all from Postgres 17.

> One little thing I noticed by stepping with debugger is that it calls
> index_getattr() twice for the same tuple and attribute. First in
> _bt_check_compare(), and if that sets *continuescan=false, again in
> _bt_tuple_before_array_skeys(). The first index_getattr() call is
> certainly pretty expensive because that's where you get the cache miss
> on the tuple when scanning. Not sure if the second call matters much,
> but it feels like a bad smell.

Possibly, but the right thing to do here is to just not maintain the
skip arrays at all. What's at issue with your test case is that the
scan doesn't quite manage to notice that that's what it should do. You
might still be right about this, but it is nevertheless true that this
*shouldn't* be relevant (it is relevant right now, but it's not hard
to see that it doesn't have to be relevant).

> The comment on _bt_tuple_before_array_skeys() says:
>
> > * readpagetup callers must only call here when _bt_check_compare already set
> > * continuescan=false. We help these callers deal with _bt_check_compare's
> > * inability to distinguishing between the < and > cases (it uses equality
> > * operator scan keys, whereas we use 3-way ORDER procs)
> That begs the question, why does _bt_check_compare() not call the 3-way
> ORDER proc in the first place? That would avoid the overhead of another
> call here.

Again, this is a design decision made by the Postgres 17 SAOP patch.

I think that there is something to be said for matching the behavior
of regular scans, including using operators (not 3-way ORDER procs)
when scanning on the leaf level.

> Aside from these micro-optimizations, I wonder about the "look-ahead"
> logic in _bt_checkkeys_look_ahead. It feels pretty simplistic. Could you
> use Exponential Search
> (https://en.wikipedia.org/wiki/Exponential_search) instead of a plain
> binary search on the page?

Maybe. But, again, I don't think that that's really the issue with
your test case. The issue is that it doesn't quite manage to use the
skipskip optimization, even though that's clearly possible, and
actually fixes the issue. Once it does that then
_bt_checkkeys_look_ahead won't ever be used, so it can't matter (at
least not as far as the query you came up with is concerned).

Let me get back to you on this.

Thanks for the review!

--
Peter Geoghegan