MIME-Version: 1.0
References: <64a2re223ajj4popowsyu4xekbuvvyfwkrihn5yzyrkwsmsuvp@2lls3tpww5dl>
 <a67mvhyi2q45eg4eimhpwdg6l3s3dmpahti2svffvmvzwmss27@r4nohusvndbq>
 <c19a18fc-ef2e-4d91-b7ba-576d1891315d@vondra.me> <il7jtfowpatrlg33qb5plj7v7pferes4ogerq5fdczszi4kokh@sbwvb2ukfgos>
 <52512325-b1f2-4fff-819e-f68122b2e427@vondra.me> <ws47e3wly6skt36b23zy5qfvcxzueo6od3uicunuodsqnxl7os@7v2qi7qkxzbz>
 <CAH2-Wzk-89uCvdJ1Q6NsM6LvDvUEt6Qy66T6A60J=D_voWxZDg@mail.gmail.com>
 <64mfcfv7iihc4pmqlxarii4esnmqry52ckz5m7lmwylnfnuxuz@oxh4ioxkjtep>
 <CAH2-Wz=GQaLKy3qaq1iYuKZOKt_2YVx13_wxcTf+xcLMEO4qyg@mail.gmail.com>
 <720560ca-97b9-40a1-ad40-9f9b8a6648e9@vondra.me> <cdpcdaaiceonmplfbl6oujf57gzzgdijknwyo2wg4d3lj2zxx3@zp7sbpvi5h5k>
 <2f7fdaa6-2855-4a49-884c-16b91db9a97b@vondra.me>
In-Reply-To: <2f7fdaa6-2855-4a49-884c-16b91db9a97b@vondra.me>
From: Alexandre Felipe <o.alexandre.felipe@gmail.com>
Date: Sun, 22 Feb 2026 16:23:11 +0000
Message-ID: <CAE8JnxPqNGReQWc+-fyprdOXwqODymgoxcxvNrC0W+AJRXpRfQ@mail.gmail.com>
Subject: Re: index prefetching
To: Tomas Vondra <tomas@vondra.me>
Cc: Andres Freund <andres@anarazel.de>, 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>
Content-Type: multipart/alternative; boundary="000000000000c1b3b1064b6c1243"
Archived-At: <https://www.postgresql.org/message-id/CAE8JnxPqNGReQWc%2B-fyprdOXwqODymgoxcxvNrC0W%2BAJRXpRfQ%40mail.gmail.com>
Precedence: bulk

--000000000000c1b3b1064b6c1243
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 =3D up
read-block =3D 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 =3D down
  if heap-down is empty
    direction =3D up
  if direction =3D up
    read-block =3D pop from heap-up
  else
    read-block =3D 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


On Wed, Feb 18, 2026 at 3:39=E2=80=AFPM Tomas Vondra <tomas@vondra.me> wrot=
e:

>
>
> On 2/18/26 05:21, Andres Freund wrote:
> > Hi,
> >
> > On 2026-02-17 22:36:53 +0100, Tomas Vondra wrote:
> >> On 2/17/26 21:16, Peter Geoghegan wrote:
> >>> On Tue, Feb 17, 2026 at 2:27=E2=80=AFPM Andres Freund <andres@anaraze=
l.de>
> wrote:
> >>>> On 2026-02-17 12:16:23 -0500, Peter Geoghegan wrote:
> >>>>> On Mon, Feb 16, 2026 at 11:48=E2=80=AFAM Andres Freund <andres@anar=
azel.de>
> 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.
> >>>
> >>
> >> So, what counts as "higher latency" in this context? What delays shoul=
d
> >> we consider practical/relevant for testing?
> >
> > 0.5-4ms is the range I've seen in various clouds across their reasonabl=
e
> > 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 muc=
h
> > 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.
> >
>
> 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).
>
> >
> >>> 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 on=
e
> >>> query at the cost of regressing another.
> >>>
> >>
> >> What counts as "unconsumed IO"? The IOs the stream already started, bu=
t
> >> 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.
> >
>
> I'll try to add it to the EXPLAIN.
>
>
> regards
>
> --
> Tomas Vondra
>
>

--000000000000c1b3b1064b6c1243
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi all,<div><br><div>I did some experiments on a few quest=
ions that flew over this thread. In the hope to be useful.<br><br>DISTANCE =
CONTROL<br><br>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=C2=A0+ io_c=
ombine_limi, but in the end the 2*d gives the best results=C2=A0across=C2=
=A0different patterns, e.g. (h{200}m{200}) that seems to be a more reasonab=
le pattern, as previous scans would have loaded in blocks. But these are fu=
ndamentally 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 i=
s the transient when we go in and out of a cached region.<div><br></div><di=
v>LIMITING PREFETCH<br><div><br>To avoid prefetch waste with a limit node w=
ouldn&#39;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) - re=
turned,=C2=A0but a selectivity factor would be important if most rows are r=
emoved,=C2=A0a good start would be (limit - filtered) * selectivity, a simp=
le model for the selectivity would be (unfiltered=C2=A0+ 1) / (filtered=C2=
=A0+ 1),=C2=A0 the 1 here accounts for the uncertainty about the next row b=
eing 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.</div><d=
iv><br></div><div>I/O REORDERING</div><div><font face=3D"monospace"><br></f=
ont></div><div><font face=3D"monospace">I did an experiment reordering the =
heap accesses, following a zig-zag pattern, using constant memory like this=
</font></div><div><font face=3D"monospace"><br></font></div><div><font face=
=3D"monospace">fill heap-up with W blocks</font></div><div><font face=3D"mo=
nospace">direction =3D up</font></div><div><font face=3D"monospace">read-bl=
ock =3D pop from heap-up</font></div><div><font face=3D"monospace">for each=
 new-block</font></div><div><font face=3D"monospace">=C2=A0 if new-block &g=
t; read block</font></div><div><font face=3D"monospace">=C2=A0 =C2=A0 push =
new-block into heap-up</font></div><div><font face=3D"monospace">=C2=A0 els=
e</font></div><div><font face=3D"monospace">=C2=A0 =C2=A0 push new-block in=
to heap-down</font></div><div><font face=3D"monospace">=C2=A0 if heap-up is=
 empty</font></div><div><font face=3D"monospace">=C2=A0 =C2=A0 direction =
=3D down</font></div><div><font face=3D"monospace">=C2=A0 if heap-down is e=
mpty</font></div><div><font face=3D"monospace">=C2=A0 =C2=A0 direction =3D =
up</font></div><div><font face=3D"monospace">=C2=A0 if direction =3D up</fo=
nt></div><div><font face=3D"monospace">=C2=A0 =C2=A0 read-block =3D pop fro=
m heap-up</font></div><div><font face=3D"monospace">=C2=A0 else</font></div=
><div><font face=3D"monospace">=C2=A0 =C2=A0 read-block =3D pop from heap-d=
own</font></div><div><font face=3D"monospace"><br>The heap-up and heap-down=
 will contain at most W elements, so they can be stored in complementary re=
gions of the same array.</font></div><div><font face=3D"monospace">With a s=
mall adjustmentment=C2=A0(moving one element to the heap behind when the ne=
w-block is ahead) we ensure that the delay added to a block doesn&#39;t exc=
eed 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.<br><br>Creating a ~400MB table<br><br></font>CREA=
TE TABLE zigzag_test (<br>=C2=A0 =C2=A0 id serial, random_key int, data tex=
t,<br>=C2=A0 =C2=A0 pad1 char(2000), pad2 char(2000), pad3 char(2000)<br>);=
<br>SELECT setseed(0.42);<br>INSERT INTO zigzag_test (random_key, data, pad=
1, pad2, pad3)<br>SELECT (random() * 100000)::int, &#39;data_&#39; || g, &#=
39;x&#39;, &#39;x&#39;, &#39;x&#39;<br>FROM generate_series(1, 5000) g;<fon=
t face=3D"monospace"></font></div><div><font face=3D"monospace"><br></font>=
</div><div><font face=3D"monospace">Then accessing 5% of it using index sca=
n (or the zigzag that breaks the index order)</font></div><div><font face=
=3D"monospace"><br></font></div><div>SELECT sum(id), sum(abs(blk - prev_blk=
)) as seek_dist FROM (<br>=C2=A0 =C2=A0 SELECT id, (ctid::text::point)[0] a=
s blk, lag((ctid::text::point)[0]) over () as prev_blk <br>=C2=A0 =C2=A0 FR=
OM zigzag_test WHERE random_key &lt; 50000<font face=3D"monospace"></font><=
/div><div><br></div><div>Measuring time=C2=A0+/- std-dev, using the I(ndex)=
 order access and the Z(igzag) order (not so exactly as the algorithm descr=
ibed above)</div><div><font face=3D"monospace"><br></font></div><div><font =
face=3D"monospace">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 I order (ms) =C2=A0 =C2=A0Z order (ms) =C2=A0Diff % =C2=A0Seek (I/Z)=
<br>Disk Prefetch =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 <br>HDD =C2=A0on =C2=
=A0 =C2=A0 =C2=A0 =C2=A0250.4 +/- 227.8 =C2=A0168.7 +/- 83.0 =C2=A0-32.6% =
=C2=A078281/1242<br>=C2=A0 =C2=A0 =C2=A0off =C2=A0 =C2=A0 =C2=A0 185.8 +/- =
269.9 =C2=A0141.9 +/- 77.4 =C2=A0-23.6% =C2=A078281/1242<br>SSD =C2=A0on =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 148.2 +/- 69.7 =C2=A0117.6 +/- 39.6 =C2=A0-20.7=
% =C2=A078281/1242<br>=C2=A0 =C2=A0 =C2=A0off =C2=A0 =C2=A0 =C2=A0 =C2=A0 6=
6.8 +/- 34.1 =C2=A0121.5 +/- 39.7 =C2=A0+81.8% =C2=A078281/1242</font></div=
><div><br></div><div>The tricky datapoint (and the one with the highest sta=
tistical significance) here is SSD without prefetch in index order.</div><d=
iv><br></div><div>On small rows, and not-so-sparse indices this might help =
with pinning-unpinning overhead (??), but for that case we already have bit=
map scans.</div><div><br></div><div>Regards,</div><div>Alexandre</div><div>=
<br><br></div></div></div></div></div><br><div class=3D"gmail_quote"><div d=
ir=3D"ltr" class=3D"gmail_attr">On Wed, Feb 18, 2026 at 3:39=E2=80=AFPM Tom=
as Vondra &lt;<a href=3D"mailto:tomas@vondra.me" target=3D"_blank">tomas@vo=
ndra.me</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"=
margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-lef=
t:1ex"><br>
<br>
On 2/18/26 05:21, Andres Freund wrote:<br>
&gt; Hi,<br>
&gt; <br>
&gt; On 2026-02-17 22:36:53 +0100, Tomas Vondra wrote:<br>
&gt;&gt; On 2/17/26 21:16, Peter Geoghegan wrote:<br>
&gt;&gt;&gt; On Tue, Feb 17, 2026 at 2:27=E2=80=AFPM Andres Freund &lt;<a h=
ref=3D"mailto:andres@anarazel.de" target=3D"_blank">andres@anarazel.de</a>&=
gt; wrote:<br>
&gt;&gt;&gt;&gt; On 2026-02-17 12:16:23 -0500, Peter Geoghegan wrote:<br>
&gt;&gt;&gt;&gt;&gt; On Mon, Feb 16, 2026 at 11:48=E2=80=AFAM Andres Freund=
 &lt;<a href=3D"mailto:andres@anarazel.de" target=3D"_blank">andres@anaraze=
l.de</a>&gt; wrote:<br>
&gt;&gt;&gt;&gt;&gt; I agree that the current heuristics (which were invent=
ed recently) are<br>
&gt;&gt;&gt;&gt;&gt; too conservative. I overfit the heuristics to my curre=
nt set of<br>
&gt;&gt;&gt;&gt;&gt; adversarial queries, as a stopgap measure.<br>
&gt;&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; Are you doing any testing on higher latency storage?=C2=A0=
 I found it to be quite<br>
&gt;&gt;&gt;&gt; valuable to use dm_delay to have a disk with reproducible =
(i.e. not cloud)<br>
&gt;&gt;&gt;&gt; higher latency (i.e. not just a local SSD).<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; I sometimes use dm_delay (with the minimum 1ms delay) when tes=
ting,<br>
&gt;&gt;&gt; but don&#39;t do so regularly. Just because it&#39;s inconveni=
ent to do so<br>
&gt;&gt;&gt; (perhaps not a great reason).<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt;&gt; Low latency NVMe can reduce the<br>
&gt;&gt;&gt;&gt; penalty of not enough readahead so much that it&#39;s hard=
 to spot problems...<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; I&#39;ll keep that in mind.<br>
&gt;&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; So, what counts as &quot;higher latency&quot; in this context? Wha=
t delays should<br>
&gt;&gt; we consider practical/relevant for testing?<br>
&gt; <br>
&gt; 0.5-4ms is the range I&#39;ve seen in various clouds across their reas=
onable<br>
&gt; storage products (i.e. not spinning disks or other ver bulk oriented t=
hings).<br>
&gt; <br>
&gt; Unfortunately dm_delay doesn&#39;t support &lt; 1ms delays, but it&#39=
;s still much<br>
&gt; better than nothing.<br>
&gt; <br>
&gt; I&#39;ve been wondering about teaching AIO to delay IOs (by adding a s=
leep to<br>
&gt; workers and linking a IORING_OP_TIMEOUT submission with the actually i=
ntended<br>
&gt; IO) to allow testing smaller delays.<br>
&gt; <br>
<br>
Could be useful testing facility, if it&#39;s done in a way that does not<b=
r>
limit the IO concurrency (i.e. the delay should probably be when<br>
consuming the IO, depending on the timestamp of the IO start).<br>
<br>
&gt; <br>
&gt;&gt;&gt; That would make sense. You can already tell when that&#39;s ha=
ppened by<br>
&gt;&gt;&gt; comparing the details shown by EXPLAIN ANALYZE against the sam=
e query<br>
&gt;&gt;&gt; execution on master, but that approach is inconvenient. Automa=
ting my<br>
&gt;&gt;&gt; microbenchmarks has proven to be important with this project. =
There&#39;s<br>
&gt;&gt;&gt; quite a few competing considerations, and it&#39;s too easy to=
 improve one<br>
&gt;&gt;&gt; query at the cost of regressing another.<br>
&gt;&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; What counts as &quot;unconsumed IO&quot;? The IOs the stream alrea=
dy started, but<br>
&gt;&gt; then did not consume? That shouldn&#39;t be hard, I think.<br>
&gt; <br>
&gt; Yes, the number of IOs that were started but not consumed. Or, even be=
tter,<br>
&gt; the number of IOs that completed but were not consumed - but that&#39;=
d be harder<br>
&gt; to get right now.<br>
&gt; <br>
&gt; I agree that started-but-not-consumed should be pretty easy.<br>
&gt; <br>
<br>
I&#39;ll try to add it to the EXPLAIN.<br>
<br>
<br>
regards<br>
<br>
-- <br>
Tomas Vondra<br>
<br>
</blockquote></div>

--000000000000c1b3b1064b6c1243--