Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1tnJWx-0049rU-RM for pgsql-performance@arkaria.postgresql.org; Wed, 26 Feb 2025 15:41:04 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1tnJWw-008EWi-Sr for pgsql-performance@arkaria.postgresql.org; Wed, 26 Feb 2025 15:41:02 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1tnJWw-008EWZ-7Q for pgsql-performance@lists.postgresql.org; Wed, 26 Feb 2025 15:41:02 +0000 Received: from fhigh-a6-smtp.messagingengine.com ([103.168.172.157]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1tnJWs-000DvS-2e for pgsql-performance@lists.postgresql.org; Wed, 26 Feb 2025 15:41:01 +0000 Received: from phl-compute-12.internal (phl-compute-12.phl.internal [10.202.2.52]) by mailfhigh.phl.internal (Postfix) with ESMTP id 420E0114016A; Wed, 26 Feb 2025 10:40:57 -0500 (EST) Received: from phl-imap-15 ([10.202.2.104]) by phl-compute-12.internal (MEProxy); Wed, 26 Feb 2025 10:40:57 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=salomvary.com; h=cc:cc:content-type:content-type:date:date:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to; s=fm2; t=1740584457; x= 1740670857; bh=q1XuROFhgh0RnS2/4r0RFxe+drJJAYtiJNpo4TueBsg=; b=U Bn2USykQ4CxW6WKceD+3c55/l805yVttKCgvZroBpdVLrfwlz+rEVkjTxpQCW9y7 9VGYsODu8hdgmjoGesPDq0xV/WoewYC1+q70DAk+MQIWLvoJQAAkUNCLiYmGsLBN Y+tbTIuI+ArhuUHsDLR+RVb0+q+om57yVm5YRrR73r+2OBCGB/SDphDRbYogs1BV 2DW5Vy/llHduiz14kVatqcfjiGJjHnb9Ny6JGIvLvR+bH99bp/AArJh1Bi3mC/kB ClFI31qGvrSH76JzdBsArvglOOal+R1z6WCDbz7hvsJGDCFskSb8AkqQu8l7S8Fm +1F/UL3aGJaFzPThPUMng== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t= 1740584457; x=1740670857; bh=q1XuROFhgh0RnS2/4r0RFxe+drJJAYtiJNp o4TueBsg=; b=cQH03epL7PPuu0536zM89QYGZR4behF6YMJxt6fvjm5qBSpmG5o P8Vmv4DBHo+SyErYgDfw/i572q6vhw0c3pi7DEk/yncGG1sdt88Ca+pd7j4SpQLa Row3XaUFXJWIadt1ZgLs9EngO++0O4GPp0rTYlVFCET6vOMgaTh6lNT0zo+Ug/ho oHElOq2/+kMmQiZyFlNnTskTb8sBBkFj3BqeVqU2fAZ6ELPNRwFoK/+xxYb3HHRg ZKuvsXS6x4+3UwhwNSIqixkdG8HYfHQCEd3nmce9tUmezJ8mevNgPWu04pgdjclW SVkfY+ZVlTvwtqHR8N0OPOWvoQlTbLQ7rzQ== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdekgeeliecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefoggffhffvvefkjghfufgtsegrtderreertdej necuhfhrohhmpehlrghrghgvrdhgohhoshgvvdekvdelsehsrghlohhmvhgrrhihrdgtoh hmnecuggftrfgrthhtvghrnhepieelleehgfelgfdthfefudejvedvvefhfffhkeeuueel jefhhfffkeduvdeiiedtnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrg hilhhfrhhomheplhgrrhhgvgdrghhoohhsvgdvkedvleesshgrlhhomhhvrghrhidrtgho mhdpnhgspghrtghpthhtohepvddpmhhouggvpehsmhhtphhouhhtpdhrtghpthhtohepph hgsegsohifthdrihgvpdhrtghpthhtohepphhgshhqlhdqphgvrhhfohhrmhgrnhgtvges lhhishhtshdrphhoshhtghhrvghsqhhlrdhorhhg X-ME-Proxy: Feedback-ID: i35d941ae:Fastmail Received: by mailuser.phl.internal (Postfix, from userid 501) id E9803780065; Wed, 26 Feb 2025 10:40:56 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface MIME-Version: 1.0 Date: Wed, 26 Feb 2025 16:40:35 +0100 From: large.goose2829@salomvary.com To: "Peter Geoghegan" Cc: pgsql-performance@lists.postgresql.org Message-Id: <32308394-e197-4a9f-9dbe-336e8af6da58@app.fastmail.com> In-Reply-To: References: Subject: Re: Efficient pagination using multi-column cursors Content-Type: multipart/alternative; boundary=c8742d3b2a79414ca4685beebcbd7fc8 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --c8742d3b2a79414ca4685beebcbd7fc8 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Thanks for the insights! On Wed, Feb 26, 2025, at 16:05, Peter Geoghegan wrote: > On Wed, Feb 26, 2025 at 9:29=E2=80=AFAM 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 i= n the "perfect" plan. >=20 > 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). >=20 >=20 > 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.=20 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. >=20 > 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 >=3D 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 t= he same performance as "WHERE (col_1, col_2, col_3) > (10, 20, 29)" usin= g "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 filte= ring using the "OR AND" variant (at least when no mixed ordering is invo= lved): SELECT content FROM data WHERE col_1 > 10 OR ( col_1 =3D 10 AND ( col_2 > 20 OR ( col_2 =3D 20 AND col_3 > 29 ) ) ) ORDER BY col_1, col_2, col_3 LIMIT 100; -> Limit: 100 row(s) (cost=3D100710 rows=3D100) (actual time=3D0.0322..= 1.15 rows=3D100 loops=3D1) -> Index range scan on data using data_index over (col_1 =3D 10 AND col_2 =3D 20 AND 29 < col_3) OR (col_1 =3D= 10 AND 20 < col_2) OR (10 < col_1), with index condition: ((`data`.col_1 > 10) or ((`data`.col_1 =3D= 10) and ((`data`.col_2 > 20) or ((`data`.col_2 =3D 20) and (`data`.col_= 3 > 29))))) (cost=3D100710 rows=3D511937) (actual time=3D0.0316..1.14 rows=3D= 100 loops=3D1) Still slightly slower actual total time on the same machine as PostgreSQ= L though (based on a single EXPLAIN ANALYZE sample only). >=20 > 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 =E2=80=94 Pick Any Two" ;) Cheers, M=C3=A1rton --c8742d3b2a79414ca4685beebcbd7fc8 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable
Thanks for the = insights!

On Wed, Feb 26, 2025, at 16:05, P= eter Geoghegan wrote:
On Wed, Feb 26, 2025 at 9:29=E2=80=AFAM <large.goose2829@salomvary.com> wr= ote:
> Without being familiar the internals of the quer= y planner, I *think* there *should* be a way to come up with WHERE condi= tions that results in the "perfect" plan.

T= here is a fundamental trade-off involved here. The simple, fast
"WHERE (col_1, col_2, col_3) > (10, 20, 29)" query returns what= ever
tuples are stored immediately after "(10, 20, 29)" in= the index.
Naturally, they're returned in index order, wh= ich 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 us= eful, since the
matching index tuples won't be physically = located together as exactly
one contiguous group of tuples= . 

I am not sure I unders= tand 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 tuple= s are physically organized exactly in this way:
ORDER BY c= ol_1, col_2 DESC, col_3

So that I should be= able to write a query that reads a continuous range from this index wit= hout filtering.


And so (with your "handwritten" row
comparison) you get a filter qual that filters out non-matc= hing tuples
using lower-order index columns. The index sca= n actually just returns
"Index Cond: (col_1 >=3D 10)" (= which still returns a contiguous group of
index tuples), w= hile a filter condition excludes those tuples returned
by = the index scan node that don't satisfy the later/lower-order column
<= /div>
condition.

Does this= mean that it is not possible to come up with a plan that has the same p= erformance as "WHERE (col_1, col_2, col_3) > (10, 20, 29)" using "han= dwritten" filters, or only for "mixed order"? Or not a theoretical limit= ation but a limitation of the current implementation of the query planne= r?

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

SELE= CT content
FROM data
WHERE
  col_1 > 10
  OR (
 =    col_1 =3D 10
    AND (
=
      col_2 > 20
      OR (<= br style=3D"max-width:100%;height:auto;">
   &n= bsp;    col_2 =3D 20
        AND col_3 >= ; 29
  &nb= sp;   )
&n= bsp;   )
&= nbsp; )
ORDER BY col= _1, col_2, col_3
LIM= IT 100;

-> Limit: 100 row(s)  (cost=3D100710 rows=3D100) (actual time= =3D0.0322..1.15 rows=3D100 loops=3D1)
    -= > Index range scan on data using data_index
       &nb= sp; over (col_1 =3D 10 AND col_2 =3D 20 AND 29 < col_3) OR (col_1 =3D= 10 AND 20 < col_2) OR (10 < col_1),
         = with index condition: ((`data`.col_1 > 10) or ((`data`.col_1 =3D 10) = and ((`data`.col_2 > 20) or ((`data`.col_2 =3D 20) and (`data`.col_3 = > 29)))))
 &= nbsp;       (cost=3D100710 rows=3D511937) = (actual time=3D0.0316..1.14 rows=3D100 loops=3D1)


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


The book "Relational Database Index Design an= d 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 inheren= tly necessary to choose between what it calls the
first st= ar (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 t= he
index must be physically traversed.

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

Cheers,
M=C3=A1rton
--c8742d3b2a79414ca4685beebcbd7fc8--