Received: from malur.postgresql.org ([2a02:16a8:dc51::56])
	by arkaria.postgresql.org with esmtps
 (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256)
	(Exim 4.89)
	(envelope-from <pgsql-hackers-owner+archive@lists.postgresql.org>)
	id 1fxyG5-0004sb-M3
	for pgsql-hackers@arkaria.postgresql.org; Thu, 06 Sep 2018 17:39:57 +0000
Received: from localhost ([127.0.0.1] helo=malur.postgresql.org)
	by malur.postgresql.org with esmtp (Exim 4.89)
	(envelope-from <pgsql-hackers-owner+archive@lists.postgresql.org>)
	id 1fxyG3-0003YJ-Bj
	for pgsql-hackers@arkaria.postgresql.org; Thu, 06 Sep 2018 17:39:55 +0000
Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29])
	by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256)
	(Exim 4.89)
	(envelope-from <tgl@sss.pgh.pa.us>)
	id 1fxyG3-0003Y2-4G
	for pgsql-hackers@lists.postgresql.org; Thu, 06 Sep 2018 17:39:55 +0000
Received: from sss.pgh.pa.us ([66.207.139.130])
	by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256)
	(Exim 4.89)
	(envelope-from <tgl@sss.pgh.pa.us>)
	id 1fxyG0-00017a-3H
	for pgsql-hackers@lists.postgresql.org; Thu, 06 Sep 2018 17:39:54 +0000
Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1])
	by sss.pgh.pa.us (8.14.4/8.14.4) with ESMTP id w86Hdlmw016618;
	Thu, 6 Sep 2018 13:39:47 -0400
From: Tom Lane <tgl@sss.pgh.pa.us>
To: James Coleman <jtc331@gmail.com>
cc: pgsql-hackers@lists.postgresql.org,
        Alexander Korotkov <a.korotkov@postgrespro.ru>
Subject: Re: [PATCH] Incremental sort (was: PoC: Partial sort)
In-reply-to: 
 <153625271389.4078.18405235923135713189.pgcf@coridan.postgresql.org>
References: 
 <CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ@mail.gmail.com>
 <CAPpHfdsjv1+eRvoHqn1NwCEcBAVcOr0c67BFuzg50zZdHTANRg@mail.gmail.com>
 <153625271389.4078.18405235923135713189.pgcf@coridan.postgresql.org>
Comments: In-reply-to James Coleman <jtc331@gmail.com>
	message dated "Thu, 06 Sep 2018 16:51:53 -0000"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <16616.1536255587.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable
Date: Thu, 06 Sep 2018 13:39:47 -0400
Message-ID: <16617.1536255587@sss.pgh.pa.us>
List-Id: <pgsql-hackers.lists.postgresql.org>
List-Help: <https://lists.postgresql.org/manage/>
List-Subscribe: <https://lists.postgresql.org/manage/>
List-Post: <mailto:pgsql-hackers@lists.postgresql.org>
List-Owner: <mailto:pgsql-hackers-owner@lists.postgresql.org>
List-Archive: <https://www.postgresql.org/list/pgsql-hackers>
Precedence: bulk

James Coleman <jtc331@gmail.com> writes:
> A fairly common planning problem for us is what we call "most recent fir=
st" queries; i.e., "the 50 most recent <table> rows for a <foreign key>".

> Here's a basic setup:

> -- created_at has very high cardinality
> create table foo(pk serial primary key, owner_fk integer, created_at tim=
estamp);
> create index idx_foo_on_owner_and_created_at on foo(owner_fk, created_at=
);

> -- technically this data guarantees unique created_at values,
> -- but there's no reason it couldn't be modified to have a few
> -- random non-unique values to prove the point
> insert into foo(owner_fk, created_at)
>   select i % 100, now() - (i::text || ' minutes')::interval
>   from generate_series(1, 1000000) t(i);

> And here's the naive query to get the results we want:

> select *
> from foo
> where owner_fk =3D 23
> -- pk is only here to disambiguate/guarantee a stable sort
> -- in the rare case that there are collisions in the other
> -- sort field(s)
> order by created_at desc, pk desc
> limit 50;

If you're concerned about the performance of this case, why don't you make
an index that actually matches the query?

regression=3D# create index on foo (owner_fk, created_at, pk);     =

CREATE INDEX
regression=3D# explain analyze select * from foo where owner_fk =3D 23 ord=
er by created_at desc, pk desc limit 50;
                                                                          =
 QUERY PLAN                                                               =
             =

--------------------------------------------------------------------------=
--------------------------------------------------------------------------=
-------------
 Limit  (cost=3D0.42..110.92 rows=3D50 width=3D16) (actual time=3D0.151..0=
.280 rows=3D50 loops=3D1)
   ->  Index Only Scan Backward using foo_owner_fk_created_at_pk_idx on fo=
o  (cost=3D0.42..20110.94 rows=3D9100 width=3D16) (actual time=3D0.146..0.=
255 rows=3D50 loops=3D1)
         Index Cond: (owner_fk =3D 23)
         Heap Fetches: 50
 Planning Time: 0.290 ms
 Execution Time: 0.361 ms
(6 rows)

There may be use-cases for Alexander's patch, but I don't find this
one to be terribly convincing.

			regards, tom lane