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:
> 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)

> 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).

Attached is v23, which fixes this issue by making sure that the
"skipskip" optimization is actually applied -- something that was
always *supposed* to happen in cases such as this one. With v22, your
adversarial case was a little over 20% slower. With this v23 I have
the regression down to under 3%, since we'll now apply the skipskip
optimization as expected. This level of slowdown seems acceptable to
me, for a case such as this (after all, this is an index scan that the
optimizer is unlikely to ever actually choose).

The way that the "skipskip" optimization works is unchanged in v23.
And even the way that we decide whether to apply that optimization
didn't really change, either. What's new in v23 is that
v23-0003-*patch adds rules around primitive scan scheduling.
Obviously, I specifically targeted Heikki's regression when I came up
with this, but the new _bt_advance_array_keys rules are nevertheless
orthogonal: even scans that just use conventional SAOP arrays will
also use these new _bt_advance_array_keys heuristics (though it'll
tend to matter much less there).

As I attempted to explain recently (admittedly it's quite confusing),
making better choices around scheduling primitive index scans is
important for its own sake, for fairly obvious reasons, but it's even
more important for far more subtle reasons: better scheduling gives
the skipskip heuristics a clearer picture of what's really going on.
That's why more or less the same set of skipskip heuristics now work
much better in practice (in cases such as Heikki's adversarial case).
It's rather indirect.

Again, the problem that Heikki highlighted was more or less an
unforeseen, far removed consequence of not having a very clear picture
about how to schedule primitive index scans within
_bt_advance_array_keys. I proved this when I showed that Heikki's
problem went away, even with v22, once retail inserts were used
instead of CREATE INDEX. I demonstrated that that'll allow the
nbtsplitloc.c suffix truncation stuff to work, which is one way to
give the _bt_advance_array_keys primitive scan scheduling a clearer
picture of what it should be doing. With v23 I came up with another
way of doing that -- a way that actually works with indexes built with
CREATE INDEX (as well as with backwards scans, which had essentially
the same problem even when suffix truncation was working well).

The structure of the existing code changes somewhat to accommodate the
new requirements: v23 moves the scanBehind recheck process from
_bt_checkkeys into its _bt_readpage caller. This was arguably already
a missed opportunity for my commit 79fa7b3b from late last year. If we
expect _bt_readpage to explicitly check a flag to perform a
so->scanBehind recheck in one case, then we might as well have it do
so in all cases. It makes what's really going with on with the scan
quite a bit clearer.

--
Peter Geoghegan