Re: Multicolumn index scan efficiency

On Mon, Nov 10, 2025 at 12:12 AM Vitalii Tymchyshyn <vit@tym.im> wrote:
> Thank you so much for both clarifying and fixing it!

FWIW the problem is limited to row compares/row constructor
comparisons that are used to decide when to end the scan. Note in
particular that row compares that decide where in the index (what leaf
page) the scan should *begin* from were never affected -- only those
that determine where the scan should end. In other words, for a
forwards scan, > and >= row compares aren't affected (but < and <= row
compares are). For backwards scans/with ORDER BY a DESC, b DESC, it's
exactly the other way around (it's > and >= row compares that'll end
the scan/that had this problem).

My guess is that this issue wasn't noticed sooner because in practice
a lot of users of row compares only use them to determine where each
scan begins from, in the context of apply row compares to implement
keyset pagination [1]. I think that it's typical to use an ORDER BY
... LIMIT, or a FETCH FIRST ... ROWS WITH TIES to limit the size of
the result set on each individual query. It was a nasty and surprising
issue, but it didn't actually come up all that often.

After all, if you use a < or a <= condition to end each scan, the
total number of rows that'll be returned each time is unpredictable --
and potentially very large. That isn't generally desirable with keyset
pagination; what users usually do is have Postgres return a more or
less uniform number of rows for each individual query that fetches the
next portion of the "total result set". That's kinda the natural way
to do it.

[1] https://wiki.postgresql.org/images/3/35/Pagination_Done_the_PostgreSQL_Way.pdf
--
Peter Geoghegan