MIME-Version: 1.0
References: <a60186fe-b552-42e3-824e-27dbdd312f15@app.fastmail.com>
 <CAH2-Wzk0XHmt_1yEeDzRB3jWfceK0ZxcnPKFsqt-XEBiZ3d7fA@mail.gmail.com>
 <32308394-e197-4a9f-9dbe-336e8af6da58@app.fastmail.com>
In-Reply-To: <32308394-e197-4a9f-9dbe-336e8af6da58@app.fastmail.com>
From: Peter Geoghegan <pg@bowt.ie>
Date: Wed, 26 Feb 2025 11:14:21 -0500
Message-ID: 
 <CAH2-WzmUHCkDbqAvK4OXe84T-o+VQrtuMQer57KKPCivyPCFFw@mail.gmail.com>
Subject: Re: Efficient pagination using multi-column cursors
To: large.goose2829@salomvary.com
Cc: pgsql-performance@lists.postgresql.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CAH2-WzmUHCkDbqAvK4OXe84T-o%2BVQrtuMQer57KKPCivyPCFFw%40mail.gmail.com>
Precedence: bulk

On Wed, Feb 26, 2025 at 10:40=E2=80=AFAM <large.goose2829@salomvary.com> wr=
ote:
> My understanding is that given this "mixed order" index:
> CREATE INDEX data_index_desc ON data (col_1, col_2 DESC, col_3);
>
> The index tuples are physically organized exactly in this way:
> ORDER BY col_1, col_2 DESC, col_3
>
> So that I should be able to write a query that reads a continuous range f=
rom this index without filtering.

Yes, you can. For example, if you use the predicate "col_1 >=3D 10", it
can work in this way, even with a mixed-asc-and-desc order multicolumn
index -- without any filtering. Same thing if you don't have any
predicate at all -- there's no lower-order columns to filter on
because there's no columns to filter on at all.

The actual predicate that you're interested in isn't like that. It
cannot use an index that both returns rows in the mixed-ASC-and-DESC
order that you want (and so terminate early with a LIMIT and whatnot),
while at the same time accessing all the tuples as exactly one
contiguous group. You have to pick which is more important. It sounds
very much like having the most useful sort order is important.

> Does this mean that it is not possible to come up with a plan that has th=
e same performance as "WHERE (col_1, col_2, col_3) > (10, 20, 29)" using "h=
andwritten" filters, or only for "mixed order"? Or not a theoretical limita=
tion but a limitation of the current implementation of the query planner?

Perhaps the query planner should be taught to rewrite the query in
such a way as to make it unnecessary for you to do so -- I think that
that's what MySQL is doing for you. That is beside the point.

Again, think about how things are physically laid out in an index
which mixes ASC and DESC order. It is inevitable that the scan has to
traverse over non-matching tuples in order to read all of the matching
tuples (or to read a given number of matching tuples). This has
nothing to do with the query planner.

> Aka. "Good, Fast, Cheap =E2=80=94 Pick Any Two" ;)

It's not like that. Often it just isn't necessary to pick any 2 -- you
can have all 3, because the requirements of the query allow it. (Plus
it would never make sense to pick the first and second stars over the
third.)

--=20
Peter Geoghegan