From: =?utf-8?Q?Micha=C5=82_K=C5=82eczek?= <michal@kleczek.org>
Message-Id: <E313FDE4-8138-44CC-99CE-60F38251D878@kleczek.org>
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_949C9C92-0BD5-4F30-B1A1-79B3FAE58331"
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3864.300.41.1.7\))
Subject: Re: New access method for b-tree.
Date: Wed, 4 Feb 2026 08:13:11 +0100
In-Reply-To: <CANwKhkNd85u+4joaKR3YHoDOQSMg5SmJmsYJGo-tMyW=XVXTew@mail.gmail.com>
Cc: Tomas Vondra <tomas@vondra.me>,
 Alexandre Felipe <alexandre.felipe@tpro.io>,
 "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
To: Ants Aasma <ants.aasma@cybertec.at>
References: <AS1PR02MB784695AFEC37179FFAF7EAE19A9DA@AS1PR02MB7846.eurprd02.prod.outlook.com>
 <a652515e-278a-4838-815b-ecd2ad4495f6@vondra.me>
 <CANwKhkNd85u+4joaKR3YHoDOQSMg5SmJmsYJGo-tMyW=XVXTew@mail.gmail.com>
Archived-At: <https://www.postgresql.org/message-id/E313FDE4-8138-44CC-99CE-60F38251D878%40kleczek.org>
Precedence: bulk


--Apple-Mail=_949C9C92-0BD5-4F30-B1A1-79B3FAE58331
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8


> On 3 Feb 2026, at 22:42, Ants Aasma <ants.aasma@cybertec.at> wrote:
>=20
> On Mon, 2 Feb 2026 at 01:54, Tomas Vondra <tomas@vondra.me> wrote:
>> I'm also wondering how common is the targeted query pattern? How =
common
>> it is to have an IN condition on the leading column in an index, and
>> ORDER BY on the second one?
>=20
> I have seen this pattern multiple times. My nickname for it is the
> timeline view. Think of the social media timeline, showing posts from
> all followed accounts in timestamp order, returned in reasonably sized
> batches. The naive SQL query will have to scan all posts from all
> followed accounts and pass them through a top-N sort. When the total
> number of posts is much larger than the batch size this is much slower
> than what is proposed here (assuming I understand it correctly) -
> effectively equivalent to running N index scans through Merge Append.
>=20
> My workarounds I have proposed users have been either to rewrite the
> query as a UNION ALL of a set of single value prefix queries wrapped
> in an order by limit. This gives the exact needed merge append plan
> shape. But repeating the query N times can get unwieldy when the
> number of values grows, so the fallback is:
>=20
> SELECT * FROM unnest(:friends) id, LATERAL (
>    SELECT * FROM posts
>    WHERE user_id =3D id
>    ORDER BY tstamp DESC LIMIT 100)
> ORDER BY tstamp DESC LIMIT 100;
>=20
> The downside of this formulation is that we still have to fetch a
> batch worth of items from scans where we otherwise would have only had
> to look at one index tuple.

GIST can be used to handle this kind of queries as it supports multiple =
sort orders.
The only problem is that GIST does not support ORDER BY column.
One possible workaround is [1] but as described there it does not play =
well with partitioning.
I=E2=80=99ve started drafting support for ORDER BY column in GIST - see =
[2].
I think it would be easier to implement and maintain than a new IAM (but =
I don=E2=80=99t have enough knowledge and experience to implement it =
myself)

[1] =
https://www.postgresql.org/message-id/3FA1E0A9-8393-41F6-88BD-62EEEA1EC21F=
%40kleczek.org
[2] =
https://www.postgresql.org/message-id/B2AC13F9-6655-4E27-BFD3-068844E5DC91=
%40kleczek.org

=E2=80=94
Kind regards,
Michal=

--Apple-Mail=_949C9C92-0BD5-4F30-B1A1-79B3FAE58331
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=utf-8

<html aria-label=3D"message body"><head><meta http-equiv=3D"content-type" =
content=3D"text/html; charset=3Dutf-8"></head><body =
style=3D"overflow-wrap: break-word; -webkit-nbsp-mode: space; =
line-break: after-white-space;"><br =
id=3D"lineBreakAtBeginningOfMessage"><div><br><blockquote =
type=3D"cite"><div>On 3 Feb 2026, at 22:42, Ants Aasma =
&lt;ants.aasma@cybertec.at&gt; wrote:</div><br =
class=3D"Apple-interchange-newline"><div><div>On Mon, 2 Feb 2026 at =
01:54, Tomas Vondra &lt;tomas@vondra.me&gt; wrote:<br><blockquote =
type=3D"cite">I'm also wondering how common is the targeted query =
pattern? How common<br>it is to have an IN condition on the leading =
column in an index, and<br>ORDER BY on the second =
one?<br></blockquote><br>I have seen this pattern multiple times. My =
nickname for it is the<br>timeline view. Think of the social media =
timeline, showing posts from<br>all followed accounts in timestamp =
order, returned in reasonably sized<br>batches. The naive SQL query will =
have to scan all posts from all<br>followed accounts and pass them =
through a top-N sort. When the total<br>number of posts is much larger =
than the batch size this is much slower<br>than what is proposed here =
(assuming I understand it correctly) -<br>effectively equivalent to =
running N index scans through Merge =
Append.</div></div></blockquote><blockquote type=3D"cite"><div><div><br>My=
 workarounds I have proposed users have been either to rewrite =
the<br>query as a UNION ALL of a set of single value prefix queries =
wrapped<br>in an order by limit. This gives the exact needed merge =
append plan<br>shape. But repeating the query N times can get unwieldy =
when the<br>number of values grows, so the fallback is:<br><br>SELECT * =
FROM unnest(:friends) id, LATERAL (<br> &nbsp;&nbsp;&nbsp;SELECT * FROM =
posts<br> &nbsp;&nbsp;&nbsp;WHERE user_id =3D id<br> =
&nbsp;&nbsp;&nbsp;ORDER BY tstamp DESC LIMIT 100)<br>ORDER BY tstamp =
DESC LIMIT 100;<br><br>The downside of this formulation is that we still =
have to fetch a<br>batch worth of items from scans where we otherwise =
would have only had<br>to look at one index =
tuple.<br></div></div></blockquote><div><br></div><div>GIST can be used =
to handle this kind of queries as it supports multiple sort =
orders.</div><div>The only problem is that GIST does not support ORDER =
BY column.</div><div>One possible workaround is [1] but as described =
there it does not play well with partitioning.</div><div>I=E2=80=99ve =
started drafting support for ORDER BY column in GIST - see =
[2].</div><div>I think it would be easier to implement and maintain than =
a new IAM (but I don=E2=80=99t have enough knowledge and experience to =
implement it myself)</div><div><br></div><div>[1]&nbsp;<a =
href=3D"https://www.postgresql.org/message-id/3FA1E0A9-8393-41F6-88BD-62EE=
EA1EC21F%40kleczek.org">https://www.postgresql.org/message-id/3FA1E0A9-839=
3-41F6-88BD-62EEEA1EC21F%40kleczek.org</a></div><div>[2]&nbsp;<a =
href=3D"https://www.postgresql.org/message-id/B2AC13F9-6655-4E27-BFD3-0688=
44E5DC91%40kleczek.org">https://www.postgresql.org/message-id/B2AC13F9-665=
5-4E27-BFD3-068844E5DC91%40kleczek.org</a></div><br></div>=E2=80=94<div>Ki=
nd regards,<br><div>Michal</div></div></body></html>=

--Apple-Mail=_949C9C92-0BD5-4F30-B1A1-79B3FAE58331--