Horton

Re: index prefetching

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: Tomas Vondra <tomas@vondra.me>
Cc: Alexandre Felipe <o.alexandre.felipe@gmail.com>, Peter Geoghegan <pg@bowt.ie>, 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-03-02T15:01:02Z
Lists: pgsql-hackers 
Hi,

On 2026-03-02 14:18:31 +0100, Tomas Vondra wrote:
> On 3/2/26 10:00, Alexandre Felipe wrote:
> >
> >
> > On Sun, Mar 1, 2026 at 11:33 PM Tomas Vondra <tomas@vondra.me
> > <mailto:tomas@vondra.me>> wrote:
> >
> >     On 3/1/26 23:32, Alexandre Felipe wrote:
> >     >
> >     > On Sun, Mar 1, 2026 at 3:03 PM Tomas Vondra <tomas@vondra.me
> >     <mailto:tomas@vondra.me>
> >     > <mailto:tomas@vondra.me <mailto:tomas@vondra.me>>> wrote:
> >     >
> >     >     Hi,
> >     >
> >     >     I've decided to run a couple tests, trying to reproduce some
> >     of the
> >     >     behaviors described in your (Felipe's) messages.
> >     >
> >     >
> >     > Thank you,
> >     > I will look into this data later. I am impressed with the number of IO
> >     > workers
> >     > you used, my test was typically with 3.
> >     >
> >
> >     3 is extremely low for an I/O bound system. It's our tradition to pick
> >     defaults that work even on tiny systems, but need tuning on actual
> >     non-toy systems :-(
> >
> >
> > That is was a surprise for me, because I am used to javascript
> > that does everything in one single process (with a coroutine
> > async model) and does with very little overhead.
> >
>
> Well, we don't have coroutines (or other threads). If you want something
> similarly lightweight, you need to use io_uring. Which means you need to
> be on Linux, unfortunately.

Even if we had coroutines, there's no portable way of integrating them with
file IO.  For that you need either something like io_uring, IOCP or posix_aio
(although the latter performs so terribly on most platforms, including macos,
it's not worth using).

> > This could explain Andres Freund observation [1]
> >
> >> It seems caused to a significant degree by waiting at low queue
> > depths. If I
> >> comment out the stream->distance-- in read_stream_start_pending_read() the
> >> regression is reduced greatly.
> >
>
> Yes, because the distance heuristics is based solely on buffer hits and
> misses (and not on some direct feedback if we're prefetching far enough).
>
> For any algorithm that increases/decreases the distance (e.g. the
> current distance*2 and distance--) there is a data patterns that
> collapses to 1 too early. It just takes the right fraction of hits and
> misses. (If we ignore "trivial" heuristics that never decreases the
> distance etc.)

I think this is making the problem sound harder than it has to be to be a
significant im provement:

Right now an IO pattern like [(miss, hit)+] will oscillate between distance =
0 and 1, and thus will do all IO synchronuously. I.e. every second required
buffer will require a synchronous read - you'll have a terrible IO
performance.

This is also true for any pattern that will have more hits, but not more
misses in a row - those are extremely common pattern.

If you instead make the distance increase logic something like:
  distance = Max(4, distance * 2);
and have the decrease logic be something like

  /*
   * Only decrease distance if there are no IOs in the queue. As long as we
   * are asynchronously executing IO we are benefiting from the higher
   * distance.
   */
  if (stream->ios_in_progress == 0 && stream->distance > 1)
      stream->distance--;

You need a more adverse pattern to not get any readahead. Even if you look at
the most trivial adverse pattern ([(miss, hits{3})+]), you've reduced the
number of synchronous waits by 2x compared to the current worst case pattern.

And if you ever have two hits separated by less than three hits in a row,
distance will much more often not be decreased by the hits (because there's
still IO in progress when encountering a hit) and distance will increase
further (because we need to wait for IO).


Another thing that we probably ought to do is to perform lookahead when the
fast path encountered a miss (rather than doing so *after* waiting for the
IO), so that we at least amortize the cost of having to wait across multiple
IOs.


> IMHO the simplest solution with the current heuristics would be to not
> allow the distance to "drop" below a "small" value that is high enough
> to hide the AIO overhead.

Unfortunately that has too big a performance penalty for fully cached
workloads :(. Doing buffer mapping lookups ahead of the current point is not
free.


We could probably do something much more aggressive than what I described
above without meaningful negative impacts, substantially reducing the maximum
negative impact of decreasing the distance. E.g. a separate cooloff counter
that needs to be decremented before the distance can be decreased after a
miss.  If we e.g. were to only allow to decrease distance after 32 buffer
hits, at a time where no IO is in progress, the worst case #waits is a lot
lower than today.

Greetings,

Andres Freund

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.