Re: Efficient pagination using multi-column cursors

public inbox for [email protected]  
help / color / mirror / Atom feed

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

Thanks for the insights!

On Wed, Feb 26, 2025, at 16:05, Peter Geoghegan wrote:
> 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. 

I am not sure I understand this.

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 from this index without filtering.

> 
> 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.

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

I don't know whether it's polite to bring up competitors on this mailing list, but MySQL 8 (which quite ironically has poor performance for the "row values" syntax, doing a full index scan) seems to avoid index filtering using the "OR AND" variant (at least when no mixed ordering is involved):

SELECT content
FROM data
WHERE
  col_1 > 10
  OR (
    col_1 = 10
    AND (
      col_2 > 20
      OR (
        col_2 = 20
        AND col_3 > 29
      )
    )
  )
ORDER BY col_1, col_2, col_3
LIMIT 100;

-> Limit: 100 row(s)  (cost=100710 rows=100) (actual time=0.0322..1.15 rows=100 loops=1)
    -> Index range scan on data using data_index
         over (col_1 = 10 AND col_2 = 20 AND 29 < col_3) OR (col_1 = 10 AND 20 < col_2) OR (10 < col_1),
         with index condition: ((`data`.col_1 > 10) or ((`data`.col_1 = 10) and ((`data`.col_2 > 20) or ((`data`.col_2 = 20) and (`data`.col_3 > 29)))))
         (cost=100710 rows=511937) (actual time=0.0316..1.14 rows=100 loops=1)


Still slightly slower actual total time on the same machine as PostgreSQL though (based on a single EXPLAIN ANALYZE sample only).

> 
> 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.

Aka. "Good, Fast, Cheap — Pick Any Two" ;)

Cheers,
Márton

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: <[email protected]>

* 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