Horton

Re: index prefetching

Peter Geoghegan <pg@bowt.ie>

View thread View on postgr.es
From: Peter Geoghegan <pg@bowt.ie>
To: Tomas Vondra <tomas@vondra.me>
Cc: Andres Freund <andres@anarazel.de>, Thomas Munro <thomas.munro@gmail.com>, Nazir Bilal Yavuz <byavuz81@gmail.com>, Robert Haas <robertmhaas@gmail.com>, Melanie Plageman <melanieplageman@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>, Georgios <gkokolatos@protonmail.com>, Konstantin Knizhnik <knizhnik@garret.ru>, Dilip Kumar <dilipbalaut@gmail.com>
Date: 2026-02-09T22:44:11Z
Lists: pgsql-hackers

Attachments

On Fri, Jan 30, 2026 at 7:18 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached is v9.

Attached is v10. There are 2 major areas of improvement in this latest revision:

1. We have enhanced the read stream callback (heapam_getnext_stream,
which is added by
v10-0005-Add-prefetching-to-index-scans-using-batch-inter.patch),
making it yield at key intervals. When we yield, we temporarily
suspend prefetching -- but only for long enough to give the scan the
opportunity to return one more matching tuple (don't confuse yielding
with pausing; we do both, but the goals are rather different in each
case).

Yielding like this keeps the scan responsive during prefetching: the
scan should never go too long without returning at least one tuple
(except when that just isn't possible at all). Testing has shown that
keeping the scan responsive in this sense is particularly important
during scans that appear in "ORDER BY ... LIMIT N" queries, as well as
during scans that feed into certain merge joins. IOW, it is
particularly important that we "keep the scan responsive" whenever it
has the potential to allow the scan to shut down before it has
performed work that turns out to be unnecessary (though it also seems
to have some benefits even when that isn't the case).

There is a complex trade-off here: we want to yield when we expect
some benefit from doing so. But we don't want to yield when doing so
risks compromising the read stream's ability to maintain an adequate
prefetch distance. There are comments in heapam_getnext_stream that
describe the theory in more detail. There are heuristics that were
derived using adversarial benchmarking/stress-testing. I'm sure that
they need more work, but this does seem like roughly the right idea.
Note that we now test whether the scan's read stream is using its
fast-path mode (read stream uses this when the scan reads heap pages
that are all cached).

2. A new patch (v10-0007-Limit-get_actual_variable_range-to-scan-one-inde.patch)
compensates for the fact that the main prefetching commit removes
get_actual_variable_range's VISITED_PAGES_LIMIT mechanism. Since
VISITED_PAGES_LIMIT cannot easily be ported over to the new table AM
interface selfuncs.c now uses.

I described the problem that we need to address when I posted v9:

> selfuncs.c problem
> ------------------
>
> Also worth noting that we recently found a problem with selfuncs.c:
> the VISITED_PAGES_LIMIT stuff in selfuncs.c is broken right now. v9
> tears that code out, pending adding back a real fix (earlier versions
> of the patch had VISITED_PAGES_LIMIT, but it didn't work).
>
> The underlying problem is that the existing VISITED_PAGES_LIMIT design
> is incompatible with our new table_index_getnext_slot interface. The
> new interface doesn't stop scanning until it is able to at least
> return 1 tuple. But VISITED_PAGES_LIMIT was invented precisely because
> get_actual_variable_endpoint's index scans took far too long, even
> though they're only ever required to locate 1 tuple. So that just
> won't work.
>
> We'll need to invent some kind of API that directly acknowledges the
> needs of the selfuncs.c caller, and others like it. Doing it in an
> ad-hoc way just doesn't seem possible anymore. That will have to wait
> for the next revision, though (or the one after that).

The new patch deals with the problem in a completely different way,
and at a completely different layer: it adds a new
IndexScanDescData.xs_read_extremal_only field, set only by
get_actual_variable_range. When nbtree sees that the field has been
set, it gives up after scanning only one leaf page (the page that
contains extremal values that are of interest to
get_actual_variable_range). Note that we completely stop caring about
heap page fetches with this new approach.

There are good reasons to believe that the new
IndexScanDescData.xs_read_extremal_only approach will solve existing
problems with VISITED_PAGES_LIMIT. Recent benchmarking from Mark
Callaghan [1] (which I've independently recreated with my own minimal
test suite) shows that VISITED_PAGES_LIMIT becomes completely
ineffective, once we reach a tipping point where many index tuples at
one end of the index all have their LP_DEAD bit set.

I'm going to start a new thread to discuss the issues in this area
later today. I'm aiming to fix an existing, independent issue in this
new patch, so it makes sense to discuss it on a completely separate
thread.

[1] https://smalldatum.blogspot.com/2026/01/cpu-bound-insert-benchmark-vs-postgres.html
--
Peter Geoghegan

Commits

  1. read stream: Split decision about look ahead for AIO and combining

  2. read_stream: Only increase read-ahead distance when waiting for IO

  3. aio: io_uring: Trigger async processing for large IOs

  4. heapam: Keep buffer pins across index scan resets.

  5. heapam: Track heap block in IndexFetchHeapData.

  6. Move heapam_handler.c index scan code to new file.

  7. Rename heapam_index_fetch_tuple argument for clarity.

  8. Optimize fast-path FK checks with batched index probes

  9. read_stream: Prevent distance from decaying too quickly

  10. read_stream: Issue IO synchronously while in fast path

  11. bufmgr: Return whether WaitReadBuffers() needed to wait

  12. aio: io_uring: Allow IO methods to check if IO completed in the background

  13. bufmgr: Make UnlockReleaseBuffer() more efficient

  14. Add fake LSN support to hash index AM.

  15. Make IndexScanInstrumentation a pointer in executor scan nodes.

  16. Use fake LSNs to improve nbtree dropPin behavior.

  17. Move fake LSN infrastructure out of GiST.

  18. Use simplehash for backend-private buffer pin refcounts.

  19. nbtree: Avoid allocating _bt_search stack.

  20. bufmgr: Fix use of wrong variable in GetPrivateRefCountEntrySlow()

  21. Conditional locking in pgaio_worker_submit_internal

  22. Reduce ExecSeqScan* code size using pg_assume()

  23. Fix rare bug in read_stream.c's split IO handling.

  24. Remove HeapBitmapScan's skip_fetch optimization

  25. Optimize nbtree backwards scans.

  26. Fix multiranges to behave more like dependent types.

  27. Add EXPLAIN (MEMORY) to report planner memory consumption

  28. Optimize nbtree backward scan boundary cases.

  29. Increment xactCompletionCount during subtransaction abort.

  30. Add nbtree Valgrind buffer lock checks.

  31. Add nbtree high key "continuescan" optimization.

  32. Reduce pinning and buffer content locking for btree scans.

  33. Teach btree to handle ScalarArrayOpExpr quals natively.