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 1tnIR8-003zL0-Vf for pgsql-performance@arkaria.postgresql.org; Wed, 26 Feb 2025 14:30:59 +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 1tnIQ9-0070ci-Ul for pgsql-performance@arkaria.postgresql.org; Wed, 26 Feb 2025 14:29:57 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1tnIQ9-0070cS-1l for pgsql-performance@lists.postgresql.org; Wed, 26 Feb 2025 14:29:57 +0000 Received: from fhigh-a5-smtp.messagingengine.com ([103.168.172.156]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1tnIQ5-000CZ9-1t for pgsql-performance@lists.postgresql.org; Wed, 26 Feb 2025 14:29:56 +0000 Received: from phl-compute-12.internal (phl-compute-12.phl.internal [10.202.2.52]) by mailfhigh.phl.internal (Postfix) with ESMTP id 7C5241140094 for ; Wed, 26 Feb 2025 09:29:53 -0500 (EST) Received: from phl-imap-15 ([10.202.2.104]) by phl-compute-12.internal (MEProxy); Wed, 26 Feb 2025 09:29:53 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=salomvary.com; h=cc:content-type:content-type:date:date:from:from:in-reply-to :message-id:mime-version:reply-to:subject:subject:to:to; s=fm2; t=1740580193; x=1740666593; bh=qfMdhNjF+wPVLGfQFTT34dOyHQFWQI3X FhPrGMVlRzk=; b=fMh7k801KUHrQ1dZlRUPSeTPkGWbMMtrz4yxXCDvNA4kvDfX 8tXREMOzNSyGEIwMAyXm9eqhwq0PTgZF9wncvOjzRoOml3an1V/8QHdvSlRmfKyJ tQmmClnmEI0bMhF2sIC+aSQZw4xuo8B7HkVYuxOxBpxU7eWJcRtFcGsTo04gi/1R f3MJ7LgWfVQ93zwD9Om2Yb/gtt1BpcrSAsB6etQooW6426UP/u6OoNx0BYygNfV/ fNy4XFHlFjQFRszRZ+V8igAOeDx+nud3YqBZmLG4AGT1p4Ke/vzKrPS9Pd+/Lo4g pZhjC5rp0P5bu8AB6syFX8MxHHDJbsQcitaGuw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:message-id :mime-version:reply-to:subject:subject:to:to:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t=1740580193; x= 1740666593; bh=qfMdhNjF+wPVLGfQFTT34dOyHQFWQI3XFhPrGMVlRzk=; b=C CqlQ5yyA/IFyUMGAAp2eSteUENTKG/0l0MihXdUA7liWxIhFpc+3IBSOVIeOcihx +lPaiehfk23y6tSAzZgup4fEzp1qVKIXgO6J5rwPjdhS/McE4NHx3W9/FclXNqj7 vxWYXNrOB+JaFooTWNP1eFfR7nfW+cTPi5h41sTaIsmATMavK/CKOASwge3CwWA1 7/BqimuHK+4BfwAzSG5oNnjZ3NE6NpLNOzGki82gID7s9eQ96AQuOY8axdbKHmV2 gOFdxCGlqbV1HbkLRPeUNOnc/QslBmbo/yym1j/Iksbx61dwW8CGf2E4sNmmYEZ1 4aUF98FKW4AZ9ll+6Cbdg== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdekgeekvdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecunecujfgurhepofggff fhvffkufgtsegrtderreertdejnecuhfhrohhmpehlrghrghgvrdhgohhoshgvvdekvdel sehsrghlohhmvhgrrhihrdgtohhmnecuggftrfgrthhtvghrnhepgefhgfefteduvdeuge ffuedthefffeevffeigfffveettedvlefhvddugefhjedtnecuffhomhgrihhnpehushgv qdhthhgvqdhinhguvgigqdhluhhkvgdrtghomhdpuggsqdhfihguughlvgdrtghomhenuc evlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehlrghrghgv rdhgohhoshgvvdekvdelsehsrghlohhmvhgrrhihrdgtohhmpdhnsggprhgtphhtthhope dupdhmohguvgepshhmthhpohhuthdprhgtphhtthhopehpghhsqhhlqdhpvghrfhhorhhm rghntggvsehlihhsthhsrdhpohhsthhgrhgvshhqlhdrohhrgh X-ME-Proxy: Feedback-ID: i35d941ae:Fastmail Received: by mailuser.phl.internal (Postfix, from userid 501) id 3A2C5780065; Wed, 26 Feb 2025 09:29:53 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface MIME-Version: 1.0 Date: Wed, 26 Feb 2025 15:27:53 +0100 From: large.goose2829@salomvary.com To: pgsql-performance@lists.postgresql.org Message-Id: Subject: Efficient pagination using multi-column cursors Content-Type: multipart/alternative; boundary=906f8a56d6344474a07badca1b973d0d List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --906f8a56d6344474a07badca1b973d0d Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Hi folks, I am working on optimizing a query that attempts to efficiently paginate= through a large table using multi-column "cursors" aka. the "seek metho= d" (as described in detail here: https://use-the-index-luke.com/sql/part= ial-results/fetch-next-page). The table (drastically simplified) looks like this: CREATE TABLE data ( col_1 int NOT NULL, col_2 int NOT NULL, col_3 int NOT NULL, content varchar(10) NOT NULL ); And has an appropriate index: CREATE INDEX data_index ON data (col_1, col_2, col_3); The recommended query to paginate through this table is using the "row v= alues" syntax: SELECT content FROM data WHERE (col_1, col_2, col_3) > (10, 20, 29) ORDER BY col_1, col_2, col_3 LIMIT 100; Which results in a perfectly optimized query plan (slightly edited for r= eadability, using test data of 1 million rows, on PostgreSQL 17.2): Limit (cost=3D0.42..5.33 rows=3D100 width=3D20) (actual time=3D0.084..0.197 rows=3D100 loops=3D1) -> Index Scan using data_index on data =20 (cost=3D0.42..43617.30 rows=3D889600 width=3D20) (actual time=3D0.081..0.176 rows=3D100 loops=3D1) Index Cond: (ROW(col_1, col_2, col_3) > ROW(10, 20, 29)) Planning Time: 0.344 ms Execution Time: 0.264 ms However, in reality, my query uses a mix of ascending and descending ord= ering (with an index matching the order columns), in which case the WHER= E (col_1, col_2, col_3) > (10, 20, 29) syntax is not an option (unless I= somehow derive "reversed" data from the column, which I would like to a= void). Therefore I am using an equivalent query using multiple WHERE conditions= , something like this (for simplicity, no mixed ordering is involved in = the examples): SELECT content FROM data WHERE col_1 >=3D 10 AND ( col_1 > 10 OR ( col_2 >=3D 20 AND ( col_2 > 20 OR col_3 > 29 ) ) ) ORDER BY col_1, col_2, col_3 LIMIT 100; Which returns the same rows, but the query plan is slightly less efficie= nt: Limit (cost=3D0.42..6.48 rows=3D100 width=3D20)=20 (actual time=3D0.848..0.893 rows=3D100 loops=3D1) -> Index Scan using data_index on data =20 (cost=3D0.42..52984.52 rows=3D874874 width=3D20) (actual time=3D0.847..0.884 rows=3D100 loops=3D1) Index Cond: (col_1 >=3D 10) Filter: ((col_1 > 10) OR ((col_2 >=3D 20) AND ((col_2 > 20) OR (= col_3 > 29)))) Rows Removed by Filter: 2030 Planning Time: 0.133 ms Execution Time: 0.916 ms Instead of exclusively relying on an index access predicate, this plan i= nvolves an index filter predicate. Without being familiar the internals of the query planner, I *think* the= re *should* be a way to come up with WHERE conditions that results in th= e "perfect" plan. There are several ways to phrase the conditions, of wh= ich I've tried a few, only to get the same or worse performance. Does an= yone have a suggestion for a better query? I am also aware that I might be chasing an optimization with low returns= (yet to see how it performs in Real Life data) but I'm already too deep= down in a rabbit hole without being able to turn back without knowing T= he Truth. I've dumped my experiments into a DB Fiddle: https://www.db-fiddle.com/f= /kd8zaibZGKGH1HSStyxNkx/0 Cheers, M=C3=A1rton --906f8a56d6344474a07badca1b973d0d Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable
Hi folks,

I am working on optimizing a query that attempts= to efficiently paginate through a large table using multi-column "curso= rs" aka. the "seek method" (as described in detail here: htt= ps://use-the-index-luke.com/sql/partial-results/fetch-next-page).

The table (drastically simplified) looks like= this:

CREATE TABLE data
(
    col= _1   int         NOT N= ULL,
  &nb= sp; col_2   int        = ; NOT NULL,
 &n= bsp;  col_3   int      &nbs= p;  NOT NULL,
&= nbsp;   content varchar(10) NOT NULL
);
<= /div>

And has an appropriate index:
CREATE INDEX data_index ON data (col_1, col_2, col_3);

The recommended query to paginate through this t= able is using the "row values" syntax:

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

Which results in a perfectly optimized query plan (sli= ghtly edited for readability, using test data of 1 million rows, on Post= greSQL 17.2):

Limit  (cost=3D0.42..5.3= 3 rows=3D100 width=3D20)
     &nb= sp; (actual time=3D0.084..0.197 rows=3D100 loops=3D1)
  ->  Index Scan using da= ta_index on data  
        (cost=3D0.42..43617.= 30 rows=3D889600 width=3D20)
        (actual time=3D0.081= ..0.176 rows=3D100 loops=3D1)
<= /div>
        Index Cond: (ROW(co= l_1, col_2, col_3) > ROW(10, 20, 29))
Planning Time: 0.344 ms
Execution Time: 0.264 ms

However, in reality, my query uses a mix of ascending and descend= ing ordering (with an index matching the order columns), in which case t= he WHERE (col_1, col_2, col_3) > (10, 20, 29) syntax is not an o= ption (unless I somehow derive "reversed" data from the column, which I = would like to avoid).

Therefore I am using = an equivalent query using multiple WHERE conditions, something like this= (for simplicity, no mixed ordering is involved in the examples):

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

W= hich returns the same rows, but the query plan is slightly less efficien= t:

Limit  (cost=3D0.42..6.48 rows=3D10= 0 width=3D20) 
       (= actual time=3D0.848..0.893 rows=3D100 loops=3D1)
  ->  Index Scan using data_in= dex on data  
<= div>        (cost=3D0.42..52984.52 ro= ws=3D874874 width=3D20)
<= div>        (actual time=3D0.847..0.8= 84 rows=3D100 loops=3D1)
=
        Index Cond: (col_1 >=3D= 10)
  &nb= sp;     Filter: ((col_1 > 10) OR ((col_2 >=3D = 20) AND ((col_2 > 20) OR (col_3 > 29))))
        Ro= ws Removed by Filter: 2030
Planning Time: 0.133 ms
=
Execution Time: 0.916 ms

Instead= of exclusively relying on an index access predicate, this plan involves= an index filter predicate.

Without being f= amiliar the internals of the query planner, I *think* there *should* be = a way to come up with WHERE conditions that results in the "perfect" pla= n. There are several ways to phrase the conditions, of which I've tried = a few, only to get the same or worse performance. Does anyone have a sug= gestion for a better query?

I am also aware tha= t I might be chasing an optimization with low returns (yet to see how it= performs in Real Life data) but I'm already too deep down in a rabbit h= ole without being able to turn back without knowing The Truth.
=

I've dumped my experiments into a DB Fiddle: https://w= ww.db-fiddle.com/f/kd8zaibZGKGH1HSStyxNkx/0

=
Cheers,
M=C3=A1rton


--906f8a56d6344474a07badca1b973d0d--