Re: index prefetching

On Thu, May 1, 2025 at 7:02 PM Tomas Vondra <tomas@vondra.me> wrote:
> There's two "fix" patches trying to make this work - it does not crash,
> and almost all the "incorrect" query results are actually stats about
> buffer hits etc. And that is expected to change with prefetching, not a
> bug. But then there are a bunch of explains where the number of index
> scans changed, e.g. like
>
> -         Index Searches: 5
> +         Index Searches: 4
>
> And that is almost certainly a bug.
>
> I haven't figured this out yet, and I feel a bit lost again :-(

For the benefit of other people reading this thread: I sent Tomas a
revised version of this "complex" patch this week, fixing all these
bugs. It only took me a few hours, and I regret not doing that work
sooner.

I also cleaned up nbtree aspects of the "complex" patch considerably.
The nbtree footprint was massively reduced:

17 files changed, 422 insertions(+), 685 deletions(-)

So there's a net negative nbtree code footprint. We're effectively
just moving things out of nbtree that are already completely
index-AM-generic. I think that the amount of code that can be removed
from nbtree (and other AMs that currently use amgettuple) will be even
higher if we go this way.

> The one real limitation of the simpler approach is that prefetching is
> limited to a single leaf page - we can't prefetch from the next one,
> until the scan advances to it. But based on experiments comparing this
> simpler and the "complex" approach, I don't think that really matters
> that much. I haven't seen any difference for regular queries.

Did you model/benchmark it?

> The one case where I think it might matter is queries with array keys,
> where each array key matches a single tuple on a different leaf page.
> The complex patch might prefetch tuples for later array values, while
> the simpler patch won't be able to do that. If an array key matches
> multiple tuples, the simple patch can prefetch those just fine, of
> course. I don't know which case is more likely.

We discussed this in Montreal, but I'd like to respond to this point
again on list:

I don't think that array keys are in any way relevant to the design of
this patch. Nothing I've said about this project has anything to do
with array keys, except when I was concerned about specific bugs in
the patch. (Bugs that I've now fixed in a way that is wholly confined
to nbtree.)

The overarching goal of my work on nbtree array scans was to make them
work just like other scans to the maximum extent possible. Array scans
"where each array key matches a single tuple on a different leaf page"
are virtually identical to any other scan that'll return only one or
two tuples from each neighboring page. You could see a similar pattern
with literally any kind of key.

Again, what I'm concerned about is coming up with a design that gives
scans maximum freedom to reorder work (not necessarily in the first
committed version), so that we can keep the read stream busy by giving
it sufficiently many heap pages to read: a truly adaptive design, that
weighs all relevant costs. Sometimes that'll necessitate eagerly
reading leaf pages. There is nothing fundamentally complicated about
that idea. Nothing in index AMs cares about how or when heap accesses
take place.

Again, it just *makes sense* to centralize the code that controls the
progress of ordered/amgettuple scans. Every affected index AM is
already doing virtually the same thing as each other. They're all
following the rules around index locking/pinning for amgettuple [1].
Individual index AMs are *already* required to read leaf pages a
certain way, in a certain order *relative to the heap accesses*. All
for the benefit of scan correctness (to avoid breaking things in a way
that relates to heapam implementation details).

Why wouldn't we want to relieve all AMs of that responsibility?
Leaving it up to index AMs has resulted in subtle bugs [2][3], and
AFAICT has no redeeming quality. If affected index AMs were *forced*
to do *exactly* the same thing as each other (not just *oblidged* to
do *almost* the same thing), it would make life easier for everybody.

[1] https://www.postgresql.org/docs/current/index-locking.html
[2] https://commitfest.postgresql.org/patch/5721/
[3] https://commitfest.postgresql.org/patch/5542/
--
Peter Geoghegan