MIME-Version: 1.0
References: 
 <CAH2-Wzn7vqmt=qE_hDrOx4NETkUoCbdn74G1gswMXi1APUuYrA@mail.gmail.com>
 <CAH2-WznFwgU3AddTqnvJABX5xo-9upG6NiX+2s0eaFhFj6tRAg@mail.gmail.com>
 <CA+Tgmobav+-oR9-jJUGbHj3j7bhwPpz7qVkfr_9zUSF-kens9A@mail.gmail.com>
 <CAH2-WzkqnVGLEQ31W1vm8T_uzy-ma-6A8QL-C56=0QUqs12b=Q@mail.gmail.com>
 <CAH2-WznmrgwFShyKuKjF2v7M_Eid6VzKd+SRPjh4-y68T6uCDw@mail.gmail.com>
 <esftck6ayqkkdtzijd736oazhve577sp7hthnwouyg2stlwlqj@rmhohbhl7tuz>
 <57d0e292-73d5-4ab9-9855-110ee9cbd90a@vondra.me>
 <efac3238-6f34-41ea-a393-26cc0441b506@vondra.me>
 <32c15a30-6e25-4f6d-9191-76a19482c556@vondra.me>
 <CAH2-WzmVvU2KmKyq8sUeYXrc_roA5LfOgDE1-vdtorpk_M3DfA@mail.gmail.com>
 <ec4d8c7b-bbc7-4805-919f-8fdeb11b3d34@vondra.me>
 <64c8b824-6203-46a3-b045-5e95b796feee@vondra.me>
 <CAH2-Wzm-u6b4gDbLNP=1pkfqJbEyPyey9M-8wG0C+QOTit963Q@mail.gmail.com>
 <03dcc1a9-c5d0-4965-889c-684dc0a7580c@vondra.me>
 <aa46af80-5219-47e6-a7d0-7628106965a6@vondra.me>
 <CA+hUKG+P0RnG_c4vL6=d8ACwpmux5ZF91FO4UpX8PDu1WqEg9w@mail.gmail.com>
 <23f490f4-8325-408c-91a0-a6757ab2441c@vondra.me>
 <CA+hUKG+WWr4-8TYemyU=ucQsNe6bUBN_Sq3mCnBoBtxaJ9w3ug@mail.gmail.com>
 <CA+hUKGLvL408O2ss6YZQsdupryvBqjhuej_hyOYU9fobhdHkTQ@mail.gmail.com>
In-Reply-To: 
 <CA+hUKGLvL408O2ss6YZQsdupryvBqjhuej_hyOYU9fobhdHkTQ@mail.gmail.com>
From: Nazir Bilal Yavuz <byavuz81@gmail.com>
Date: Mon, 21 Jul 2025 09:53:45 +0300
Message-ID: 
 <CAN55FZ0y57uEK+Ts8s3NV9Gyg=YiAV-y610XJpfS+jdCh_7f5g@mail.gmail.com>
Subject: Re: index prefetching
To: Thomas Munro <thomas.munro@gmail.com>
Cc: Tomas Vondra <tomas@vondra.me>, Peter Geoghegan <pg@bowt.ie>,
 Andres Freund <andres@anarazel.de>,
	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: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CAN55FZ0y57uEK%2BTs8s3NV9Gyg%3DYiAV-y610XJpfS%2BjdCh_7f5g%40mail.gmail.com>
Precedence: bulk

Hi,

On Mon, 21 Jul 2025 at 03:59, Thomas Munro <thomas.munro@gmail.com> wrote:
>
> On Sun, Jul 20, 2025 at 1:07=E2=80=AFAM Thomas Munro <thomas.munro@gmail.=
com> wrote:
> > On Sat, Jul 19, 2025 at 11:23=E2=80=AFPM Tomas Vondra <tomas@vondra.me>=
 wrote:
> > > The thing that however concerns me is that what I observed was not th=
e
> > > distance getting reset to 1, and then ramping up. Which should happen
> > > pretty quickly, thanks to the doubling. In my experiments it *never*
> > > ramped up again, it stayed at 1. I still don't quite understand why.
> >
> > Huh.  Will look into that on Monday.
>
> I suspect that it might be working as designed, but suffering from a
> bit of a weakness in the distance control algorithm, which I described
> in another thread[1].  In short, the simple minded algorithm that
> doubles on miss and subtracts one on hit can get stuck alternating
> between 1 and 2 if you hit certain patterns.  Bilal pinged me off-list
> to say that he'd repro'd something like your test case and that's what
> seemed to be happening, anyway?  I will dig out my experimental
> patches that tried different adjustments to escape from that state....

I used Tomas Vondra's test [1]. I tracked how many times
StartReadBuffersImpl() functions return true (IO is needed) and false
(IO is not needed, cache hit). It returns true ~%6 times on both
simple and complex patches (~116000 times true, ~1900000 times false
on both patches).

A complex patch ramps up to ~250 distance at the start of the stream
and %6 is enough to stay at distance. Actually, it is enough to ramp
up more but it seems the max distance is about ~270 so it stays there.
On the other hand, a simple patch doesn't ramp up at the start of the
stream and %6 is not enough to ramp up. It is always like distance is
1 and IO needed, so multiplying the distance by 2 -> distance =3D 2 but
then the next block is cached, so decreasing the distance by 1 and
distance is 1 again.

[1] https://www.postgresql.org/message-id/aa46af80-5219-47e6-a7d0-762810696=
5a6%40vondra.me

--=20
Regards,
Nazir Bilal Yavuz
Microsoft