Subject: Re: index prefetching

From: Peter Geoghegan <[email-masked]>
Date: Tue, 17 Feb 2026 15:16:06 -0500

On Tue, Feb 17, 2026 at 2:27 PM Andres Freund <[email-masked]> wrote:
> On 2026-02-17 12:16:23 -0500, Peter Geoghegan wrote:
> > On Mon, Feb 16, 2026 at 11:48 AM Andres Freund <[email-masked]> wrote:
> > I agree that the current heuristics (which were invented recently) are
> > too conservative. I overfit the heuristics to my current set of
> > adversarial queries, as a stopgap measure.
>
> Are you doing any testing on higher latency storage?  I found it to be quite
> valuable to use dm_delay to have a disk with reproducible (i.e. not cloud)
> higher latency (i.e. not just a local SSD).

I sometimes use dm_delay (with the minimum 1ms delay) when testing,
but don't do so regularly. Just because it's inconvenient to do so
(perhaps not a great reason).

> Low latency NVMe can reduce the
> penalty of not enough readahead so much that it's hard to spot problems...

I'll keep that in mind.

> > ISTM that we need the yields to better cooperate with whatever's
> > happening on the read stream side.
>
> Plausible.  It could be that we could get away with controlling the rampup to
> be slower in potentially problematic cases, without needing the yielding, but
> not sure.
>
> If that doesn't work, it might just be sufficient to increase the number of
> batches that trigger yields as the scan goes on (perhaps by taking the number
> of already "consumed" batches into account).

It could make sense to take the number of consumed batches into
account. In general, I think the best approach will be one that
combines multiple complementary strategies.

Passing down a LIMIT N hint has proven to be a good idea -- and it
doesn't really require applying any information related to the read
stream. That's enough to prevent problems in the really extreme cases
(e.g., nested loop antijoins with a LIMIT 1 on the inner side). The
problematic merge join I showed you is a not-so-extreme case, which
makes it trickier. ISTM that taking into consideration the number of
"consumed" batches will not help that particular merge join query,
precisely because it's not-so-extreme: the inner index scan consumes
plenty of batches, but is nevertheless significantly regressed (at
least when we don't yield at all).

> To evaluate the amount of wasted work, it could be useful to make the read
> stream stats page spit out the amount of "unconsumed" IOs at the end of the
> scan.

That would make sense. You can already tell when that's happened by
comparing the details shown by EXPLAIN ANALYZE against the same query
execution on master, but that approach is inconvenient. Automating my
microbenchmarks has proven to be important with this project. There's
quite a few competing considerations, and it's too easy to improve one
query at the cost of regressing another.

> > The main motivation for yielding is to deal with things like merge
> > joins fed by at least one plain index scan, and plain scans for an
> > "ORDER BY .... LIMIT N" query.
>
> Would be good to document why the yielding exists more extensively in the
> comment above it...

I agree that the comments aren't fully worked out. Mostly because my
understanding of what's going on here isn't fully worked out.

> > I attach an example of where disabling the yield mechanism hurts
> > instead of helping, to give you a sense of the problems in this area.
>
> What data/schema is that? Looks kinda but not really TPC-H like.

Attached SQL script generates the same test data. There is a dimension
table, which might make it similar to TPC-H, though that wasn't really
intentional.

> I assume that there are no mark & restores in the query, given that presumably
> the inner side is unique?

Right; this particular query doesn't use mark and restore.

I do have another test query that does use mark and restore (a
self-join + range conditions), but so far that doesn't seem to be too
much of a problem. We have to reset the read stream when we restore a
mark, which creates noticeable overhead. But (it seems) usually not
enough added overhead for it to really matter.

FWIW when the inner side of a merge join is an index-only scan, and we
have to mark + restore a lot, the patch is quite a lot faster than
master -- even when everything is cached. We don't have to repeatedly
do the same VM lookups on the inner side (we can just use our local VM
cache instead).

-- 
Peter Geoghegan

---

From: Tomas Vondra <[email-masked]>
Date: Tue, 17 Feb 2026 22:36:53 +0100

>> penalty of not enough readahead so much that it's hard to spot problems...

So, what counts as "higher latency" in this context? What delays should
we consider practical/relevant for testing?

> combines multiple complementary strategies.

Yes, this is roughly what I meant by "ramp up". Start by limiting the
batch distance to 2, then gradually increase that during the scan.

> query at the cost of regressing another.

What counts as "unconsumed IO"? The IOs the stream already started, but
then did not consume? That shouldn't be hard, I think.

regards

-- 
Tomas Vondra

---

From: Andres Freund <[email-masked]>
Date: Tue, 17 Feb 2026 19:30:57 -0500

Hi,

On 2026-02-17 15:16:06 -0500, Peter Geoghegan wrote:
> stream.

Yea, that seems like something that should obviously be done.

> That's enough to prevent problems in the really extreme cases

Interestingly, I can't reproduce a regression compared to index prefetching
being disabled.

If I evict just prefetch_customers between runs, I see prefetch + no-yield
being the fastest by a good amount.

If I evict prefetch_customers as well as prefetch_customers_pkey, yielding
wins, but only just about. Which I guess makes sense, the index reads are
synchronous random reads, and we do more of those if we prefetch too
aggressively.

I ran the queries both with pgbench (in a script that evicts the buffers, but
then just looks at the per-statement time for the SELECT, 30 iterations) and
separately interactively with EXPLAIN ANALYZE to get IO stats.

This is with debug_io_direct=data, were you measuring this without DIO? If so,
was the data in the page cache or did you evict it from there?

We really should add a function to pg_prewarm (or pg_buffercache, or ...) that
evicts pages in a targeted way from the kernel page cache... Flushing the
entire kernel pagecache leads to undesirable noise, because it also evicts
filesystem metadata (on somefilesystems at least) etc.

evicting prefetch_customers:

index_prefetch = 0:

    pgbench: 23.970

        ->  Index Scan using prefetch_customers_pkey on prefetch_customers c (actual time=0.066..21.465 rows=1858.00 loops=1)
              Filter: (region_id = 4)
              Rows Removed by Filter: 35285
              Index Searches: 1
              Buffers: shared hit=103 read=237
              I/O Timings: shared read=16.696

(the variability here is huge, for some reason, anything between 11.5 and
27ms, despite cpuidling etc being disabled, above is average)

index_prefetch = 1, yield:

    pgbench: 20.829

        ->  Index Scan using prefetch_customers_pkey on prefetch_customers c (actual time=0.070..13.147 rows=1858.00 loops=1)
              Filter: (region_id = 4)
              Rows Removed by Filter: 35285
              Index Searches: 1
              Prefetch: distance=7.895 count=266 stalls=1 skipped=31356 resets=0 pauses=33 ungets=0 forwarded=0
                        histogram [2,4) => 2, [4,8) => 4, [8,16) => 260
              Buffers: shared hit=103 read=237
              I/O Timings: shared read=8.302

index_prefetch = 1, no yield:

    pgbench: 17.384

        ->  Index Scan using prefetch_customers_pkey on prefetch_customers c (actual time=0.070..7.354 rows=1858.00 loops=1)
              Filter: (region_id = 4)
              Rows Removed by Filter: 35285
              Index Searches: 1
              Prefetch: distance=295.456 count=419 stalls=1 skipped=59537 resets=0 pauses=38 ungets=0 forwarded=0
                        histogram [2,4) => 2, [4,8) => 4, [8,16) => 8, [16,32) => 16, [32,64) => 32, [64,128) => 48, [128,256) => 80, [256,512) => 42, [512,10>
              Buffers: shared hit=166 read=385
              I/O Timings: shared read=1.571

evicting prefetch_customers, prefetch_customers_pkey :

index_prefetch = 0:

    pgbench: 31.248

        ->  Index Scan using prefetch_customers_pkey on prefetch_customers c (actual time=0.067..21.231 rows=1858.00 loops=1)
              Filter: (region_id = 4)
              Rows Removed by Filter: 35285
              Index Searches: 1
              Buffers: shared hit=2 read=338
              I/O Timings: shared read=16.396

index_prefetch = 1, yield:

    pgbench: 25.823

        ->  Index Scan using prefetch_customers_pkey on prefetch_customers c (actual time=0.070..16.397 rows=1858.00 loops=1)
              Filter: (region_id = 4)
              Rows Removed by Filter: 35285
              Index Searches: 1
              Prefetch: distance=7.895 count=266 stalls=1 skipped=31356 resets=0 pauses=33 ungets=0 forwarded=0
                        histogram [2,4) => 2, [4,8) => 4, [8,16) => 260
              Buffers: shared hit=2 read=338
              I/O Timings: shared read=11.524

index_prefetch = 1, no yield:

    pgbench: 25.923

        ->  Index Scan using prefetch_customers_pkey on prefetch_customers c (actual rows=1858.00 loops=1)
              Filter: (region_id = 4)
              Rows Removed by Filter: 35285
              Index Searches: 1
              Prefetch: distance=295.456 count=419 stalls=1 skipped=59537 resets=0 pauses=38 ungets=0 forwarded=0
                        histogram [2,4) => 2, [4,8) => 4, [8,16) => 8, [16,32) => 16, [32,64) => 32, [64,128) => 48, [128,256) => 80, [256,512) => 42, [512,1024) => 187
              Buffers: shared hit=2 read=549
              I/O Timings: shared read=13.195

But it's not hard to see that doing another 211 blocks worth of IO could hurt
noticeably. Particularly if it's non-prefetchable IO, as, I think, is the case
for 63 of those 211 blocks...

> enough added overhead for it to really matter.

I guess you'd have to have oddly many duplicate rows for the prefetch on the
inner side, filtering some of those out on the inner side, so you actually
ramp up to a significant distance, wasting some of that effort once due to
finding a matching row in the anti-join.  Probably not a huge issue.

> do the same VM lookups on the inner side (we can just use our local VM

Hah.

FWIW, I got a crash in a mark-restore query. I think I see the problem:

	/*
	 * Release all currently loaded batches, being sure to avoid freeing
	 * markBatch (unless called with complete, where we're supposed to)
	 */
	for (uint8 i = batchringbuf->headBatch; i != batchringbuf->nextBatch; i++)
	{
		IndexScanBatch batch = index_scan_batch(scan, i);

		if (complete || batch != markBatch)
		{
			markBatchFreed = (batch == markBatch);
			tableam_util_free_batch(scan, batch);
		}
	}

	if (complete && markBatch != NULL && !markBatchFreed)
	{
		/*
		 * We didn't free markBatch because it was no longer loaded in ring
		 * buffer.  Do so now instead.
		 */
		tableam_util_free_batch(scan, markBatch);
	}

If, in the loop, there's a batch after the markBatch in the ring, it'll reset
markBatchFreed to false. Which then leads to the batch being freed a second
time.

Greetings,

Andres Freund

---

From: Peter Geoghegan <[email-masked]>
Date: Tue, 17 Feb 2026 20:11:24 -0500

> synchronous random reads, and we do more of those if we prefetch too

That can't have been a factor when I ran the query (which is pretty
obvious from the EXPLAIN ANALYZE output).

> was the data in the page cache or did you evict it from there?

I rarely use debug_io_direct=data for any of my testing. The standard
for me is to use buffered IO + io_uring, while prewarming all indexes
and evicting all heap relations. And by evicting the OS filesystem
cache before each run.

FWIW, the version of the patch you're using is slightly different to
the one I have here. Since I worked on unrelated issues with things
like the cost of rescans with nestloop joins. Another difference is
that the memory allocation for the VM cache is now combined with the
main batch alloc, which seems to be more cache efficient. And saves us
memory for plain index scans.

> filesystem metadata (on somefilesystems at least) etc.

Yeah, having to flush the kernel page cache has been really inconvenient.

> markBatchFreed to false. Which then leads to the batch being freed a second

Oops.

-- 
Peter Geoghegan

---

From: Andres Freund <[email-masked]>
Date: Tue, 17 Feb 2026 23:21:28 -0500

Hi,

> we consider practical/relevant for testing?

0.5-4ms is the range I've seen in various clouds across their reasonable
storage products (i.e. not spinning disks or other ver bulk oriented things).

Unfortunately dm_delay doesn't support < 1ms delays, but it's still much
better than nothing.

I've been wondering about teaching AIO to delay IOs (by adding a sleep to
workers and linking a IORING_OP_TIMEOUT submission with the actually intended
IO) to allow testing smaller delays.

> then did not consume? That shouldn't be hard, I think.

Yes, the number of IOs that were started but not consumed. Or, even better,
the number of IOs that completed but were not consumed - but that'd be harder
to get right now.

I agree that started-but-not-consumed should be pretty easy.

Greetings,

Andres Freund

---

From: Peter Geoghegan <[email-masked]>
Date: Wed, 18 Feb 2026 00:02:34 -0500

> memory for plain index scans.

Here's a rebased branch with all of those mostly-unrelated optimization:

https://github.com/petergeoghegan/postgres/tree/index-prefetch-master-vmcache-rescan-optimizations

I suggest that you work off of this, on the off chance that these new
optimizations end up mattering. Which is quite possible with anything
that involves an index-only scan.

-- 
Peter Geoghegan

---

From: Tomas Vondra <[email-masked]>
Date: Wed, 18 Feb 2026 16:39:30 +0100

> IO) to allow testing smaller delays.

Could be useful testing facility, if it's done in a way that does not
limit the IO concurrency (i.e. the delay should probably be when
consuming the IO, depending on the timestamp of the IO start).

> I agree that started-but-not-consumed should be pretty easy.

I'll try to add it to the EXPLAIN.

regards

-- 
Tomas Vondra

---

From: Alexandre Felipe <[email-masked]>
Date: Sun, 22 Feb 2026 16:23:11 +0000

Hi all,

I did some experiments on a few questions that flew over this thread. In
the hope to be useful.

DISTANCE CONTROL

I tested different strategies to increase distance. 2*d, 2*d+1, d+2, d+4,
and so on. In my head, what would make sense is d + io_combine_limi, but in
the end the 2*d gives the best results across different patterns, e.g.
(h{200}m{200}) that seems to be a more reasonable pattern, as previous
scans would have loaded in blocks. But these are fundamentally the same, as
I posted about this a markov model, and the limit will be something like
max_distance * sigmoid(h * (p - p0)), what changes is the transient when we
go in and out of a cached region.

LIMITING PREFETCH

To avoid prefetch waste with a limit node wouldn't it make sense to send
from the executor an estimate of how many rows will be required. A strict
lower bound would be limit (+ offset) - returned, but a selectivity factor
would be important if most rows are removed, a good start would be (limit -
filtered) * selectivity, a simple model for the selectivity would be
(unfiltered + 1) / (filtered + 1),  the 1 here accounts for the uncertainty
about the next row being filtered or not, and avoids a division by zero for
the first row, and naturally will cap the distance to the limit when the
query starts.

I/O REORDERING

I did an experiment reordering the heap accesses, following a zig-zag
pattern, using constant memory like this

fill heap-up with W blocks
direction = up
read-block = pop from heap-up
for each new-block
  if new-block > read block
    push new-block into heap-up
  else
    push new-block into heap-down
  if heap-up is empty
    direction = down
  if heap-down is empty
    direction = up
  if direction = up
    read-block = pop from heap-up
  else
    read-block = pop from heap-down

The heap-up and heap-down will contain at most W elements, so they can be
stored in complementary regions of the same array.
With a small adjustmentment (moving one element to the heap behind when the
new-block is ahead) we ensure that the delay added to a block doesn't
exceed the buffer length, and we can restore the index order with another
heap, so this would give an algorithm with O(W) memory O(W * log(W))
complexity, asymptotically constant on the table size. And will reduce the
total seek distance by roughly 2/W.

Creating a ~400MB table

CREATE TABLE zigzag_test (
    id serial, random_key int, data text,
    pad1 char(2000), pad2 char(2000), pad3 char(2000)
);
SELECT setseed(0.42);
INSERT INTO zigzag_test (random_key, data, pad1, pad2, pad3)
SELECT (random() * 100000)::int, 'data_' || g, 'x', 'x', 'x'
FROM generate_series(1, 5000) g;

Then accessing 5% of it using index scan (or the zigzag that breaks the
index order)

SELECT sum(id), sum(abs(blk - prev_blk)) as seek_dist FROM (
    SELECT id, (ctid::text::point)[0] as blk, lag((ctid::text::point)[0])
over () as prev_blk
    FROM zigzag_test WHERE random_key < 50000

Measuring time +/- std-dev, using the I(ndex) order access and the Z(igzag)
order (not so exactly as the algorithm described above)

                  I order (ms)    Z order (ms)  Diff %  Seek (I/Z)
Disk Prefetch
HDD  on        250.4 +/- 227.8  168.7 +/- 83.0  -32.6%  78281/1242
     off       185.8 +/- 269.9  141.9 +/- 77.4  -23.6%  78281/1242
SSD  on         148.2 +/- 69.7  117.6 +/- 39.6  -20.7%  78281/1242
     off         66.8 +/- 34.1  121.5 +/- 39.7  +81.8%  78281/1242

The tricky datapoint (and the one with the highest statistical
significance) here is SSD without prefetch in index order.

On small rows, and not-so-sparse indices this might help with
pinning-unpinning overhead (??), but for that case we already have bitmap
scans.

Regards,
Alexandre

---

From: Peter Geoghegan <[email-masked]>
Date: Sun, 22 Feb 2026 14:28:00 -0500

On Sun, Feb 22, 2026 at 11:23 AM Alexandre Felipe
<[email-masked]> wrote:
> DISTANCE CONTROL
>
> I tested different strategies to increase distance. 2*d, 2*d+1, d+2, d+4, and so on. In my head, what would make sense is d + io_combine_limi, but in the end the 2*d gives the best results across different patterns, e.g. (h{200}m{200}) that seems to be a more reasonable pattern, as previous scans would have loaded in blocks. But these are fundamentally the same, as I posted about this a markov model, and the limit will be something like max_distance * sigmoid(h * (p - p0)), what changes is the transient when we go in and out of a cached region.

I don't understand. Why, in general, would a Markov model be useful
for determining prefetch distance?

> LIMITING PREFETCH
>
> To avoid prefetch waste with a limit node wouldn't it make sense to send from the executor an estimate of how many rows will be required.

There's a patch that does that. Have you looked at the patch series at all?

> I/O REORDERING
>
> I did an experiment reordering the heap accesses, following a zig-zag pattern

There's no question that reordering heap accesses is an interesting
direction to eventually take this infrastructure in. I've experimented
with that myself. But this is the worst possible time to be increasing
the scope of the patch for an uncertain benefit.

We're in crunch mode right now, ahead of feature freeze, which is less
than 6 weeks away. Tomas has been working on this project for about 3
years, and I've been working on it for about 1. Long digressions about
the asymptotic complexity of priority queues add less than zero value.

-- 
Peter Geoghegan

---

From: Alexandre Felipe <[email-masked]>
Date: Mon, 23 Feb 2026 13:27:09 +0000

> than 6 weeks away.

BTW, it seems that someone forgot to #include "utils/rel.h" in
src/backend/access/transam/xloginsert.c

> Tomas has been working on this project for about 3
> years, and I've been working on it for about 1.

That is why I gave up on contributing a feature that I wanted back in 2022
(that could make some of our queries dozens of times faster queries).
Before going for it I tried something easier staying away from critical
things like IO, contention, replication and submitting a planner
improvement (5479), and while I waited I decided to look for high impact
features. That is how I ended up in this thread. So even if I am
inconvenient you can look at my presence here as a compliment!

> Long digressions about

Sorry for that, for some readers that could not be obvious. Let me know if
you think there is something where I can add greater than or equal zero
value.

On Sun, Feb 22, 2026 at 7:28 PM Peter Geoghegan <[email-masked]> wrote:

> > I tested different strategies to increase distance. 2*d, 2*d+1, d+2,
> d+4, and so on. In my head, what would make sense is d + io_combine_limi,
> but in the end the 2*d gives the best results across different patterns,
> e.g. (h{200}m{200}) that seems to be a more reasonable pattern, as previous
> from the executor an estimate of how many rows will be required.
>
> pattern