public inbox for [email protected]  

help / color / mirror / Atom feed

From: Peter Geoghegan <[email protected]>
To: [email protected]
Cc: [email protected]
Subject: Re: Efficient pagination using multi-column cursors
Date: Wed, 26 Feb 2025 10:05:52 -0500
Message-ID: <CAH2-Wzk0XHmt_1yEeDzRB3jWfceK0ZxcnPKFsqt-XEBiZ3d7fA@mail.gmail.com> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>

On Wed, Feb 26, 2025 at 9:29 AM <[email protected]> wrote:
> Without being familiar the internals of the query planner, I *think* there *should* be a way to come up with WHERE conditions that results in the "perfect" plan.

There is a fundamental trade-off involved here. The simple, fast
"WHERE (col_1, col_2, col_3) > (10, 20, 29)" query returns whatever
tuples are stored immediately after "(10, 20, 29)" in the index.
Naturally, they're returned in index order, which is usually the most
useful order (simple ASC order or simple DESC order for all columns).

The B-Tree code can physically traverse your mixed-ASC-and-DESC order
index in almost the same way. But it is much less useful, since the
matching index tuples won't be physically located together as exactly
one contiguous group of tuples. And so (with your "handwritten" row
comparison) you get a filter qual that filters out non-matching tuples
using lower-order index columns. The index scan actually just returns
"Index Cond: (col_1 >= 10)" (which still returns a contiguous group of
index tuples), while a filter condition excludes those tuples returned
by the index scan node that don't satisfy the later/lower-order column
condition.

The book "Relational Database Index Design and the Optimizers"
proposes a vocabulary for the trade-offs in this area -- the 3 star
model. When creating the best possible index for certain queries it is
sometimes inherently necessary to choose between what it calls the
first star (which means avoiding a sort) and the second star (which
means having the thinnest possible "row slice"). Sometimes those
things are in tension, which makes sense when you imagine how the
index must be physically traversed.

-- 
Peter Geoghegan

view thread (6+ messages)  latest in thread

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected]
  Subject: Re: Efficient pagination using multi-column cursors
  In-Reply-To: <CAH2-Wzk0XHmt_1yEeDzRB3jWfceK0ZxcnPKFsqt-XEBiZ3d7fA@mail.gmail.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox