Mime-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8
Date: Thu, 14 Aug 2025 12:56:21 -0400
Message-Id: <DC2B4TY023QP.2ZL331BPZCBSX@bowt.ie>
Cc: "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>
Subject: Re: index prefetching
From: "Peter Geoghegan" <pg@bowt.ie>
To: "Tomas Vondra" <tomas@vondra.me>, "Andres Freund" <andres@anarazel.de>
References: <f516d66b-5bed-45af-8127-d09b684dad9e@vondra.me>
 <CAH2-WzmdiO4fHA1O06SYUjgMQZG7haysY7Tu5DS5z-CHsv5MLQ@mail.gmail.com>
 <d7bad36a-ac8d-4727-a52b-822621142d64@vondra.me>
 <CAH2-Wz=Y-PsC6_tZOPhHWvPx0geGnrh9VKjUZ-168ezUM_XM2Q@mail.gmail.com>
 <CA+hUKGKMaZLmNQHaa_DZMw9MJJKGegjrqnTY3KOZB-_nvFa3wQ@mail.gmail.com>
 <DC0RJDW1PEAX.NDGIXR6WPM94@bowt.ie>
 <51b5f71b-5f19-4453-91ff-2b9f2a840c58@vondra.me>
 <b739c179-25ca-4371-b528-cf80ea111d94@vondra.me>
 <CAH2-Wzko86NwiENCJGtakJ=fOhWpr-Yz-F+1oxgv2Ku1mvXwvA@mail.gmail.com>
 <6cb6109d-71d6-490c-8056-d8885081b008@vondra.me>
 <c7a77pcyc5eynme376wvyojryijtlieyxsu3bvxp4eiy6au6uf@caniulyi4jr5>
 <CAH2-Wz=L7h-koDKa3_NEg39Faw7MrOkSVOsodvQ4toSQahvWjQ@mail.gmail.com>
 <a9c0a5f9-cf5e-4ac9-abf6-683483161169@vondra.me>
 <DC1PBQW5HBEJ.3W4SMGI4LW3VI@bowt.ie>
 <7c308720-5cd4-4508-8cc0-6e55a6352731@vondra.me>
In-Reply-To: <7c308720-5cd4-4508-8cc0-6e55a6352731@vondra.me>
Archived-At: 
 <https://www.postgresql.org/message-id/DC2B4TY023QP.2ZL331BPZCBSX%40bowt.ie>
Precedence: bulk

On Wed Aug 13, 2025 at 8:59 PM EDT, Tomas Vondra wrote:
> On 8/14/25 01:50, Peter Geoghegan wrote:
>> I first made the order of the table random, except among groups of index=
 tuples
>> that have exactly the same value. Those will still point to the same 1 o=
r 2 heap
>> blocks in virtually all cases, so we have "heap clustering without any h=
eap
>> correlation" in the newly rewritten table.  To set things up this way, I=
 first
>> made another index, and then clustered the table using that new index:

> Interesting. It's really surprising random I/O beats the sequential.

It should be noted that the effect seems to be limited to io_method=3Dio_ur=
ing.
I find that with io_method=3Dworker, the execution time of the original
"sequential heap access" backwards scan is very similar to the execution ti=
me
of the variant with the index that exhibits "heap clustering without any he=
ap
correlation" (the variant where individual heap blocks appear in random ord=
er).

Benchmark that includes both io_uring and worker
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

I performed the usual procedure of prewarming the index and evicting the he=
ap
relation, and then actually running the relevant query through EXPLAIN
ANALYZE. Direct I/O was used throughout.

io_method=3Dworker
----------------

Original backwards scan: 1498.024 ms (shared read=3D48.080)
"No heap correlation" backwards scan: 1483.348 ms (shared read=3D22.036)

Original forwards scan: 656.884 ms (shared read=3D19.904)
"No heap correlation" forwards scan: 578.076 ms (shared read=3D10.159)

io_method=3Dio_uring
------------------

Original backwards scan: 1052.807 ms (shared read=3D187.876)
"No heap correlation" backwards scan: 649.473 ms (shared read=3D365.802)

Original forwards scan: 593.126 ms (shared read=3D55.837)
"No heap correlation" forwards scan: 429.888 ms (shared read=3D188.619)

Summary
-------

As of this morning, io_method=3Dio_uring also shows that the forwards scan =
is
faster with random heap accesses than without (not just the backwards scan)=
.
I double-checked, to make sure that the effect was real; it seems to be.
I'm aware that some of these numbers (those for the original/sequential
forward scan case) don't match what I reported on Tuesday. I believe that
this is due to changes I made to my SSD's readahead using blockdev, though
it's possible that there's some other explanation. (In case it matters, I'm
running Debian unstable with liburing2 "2.9-1".)

The important point remains: at least with io_uring, the backwards scan que=
ry
is much faster with random I/O than it is with descending sequential I/O. I=
t
might make sense if they were at least at parity, but clearly they're not.

--=20
Peter Geoghegan