From: Ronan Dunklau <ronan.dunklau@aiven.io>
To: David Rowley <dgrowleyml@gmail.com>, Justin Pryzby <pryzby@telsasoft.com>,
 Pavel Luzanov <p.luzanov@postgrespro.ru>
Cc: Tom Lane <tgl@sss.pgh.pa.us>, Richard Guo <guofenglinux@gmail.com>,
 pgsql-hackers@lists.postgresql.org, Ranier Vilela <ranier.vf@gmail.com>
Subject: Re: Add proper planner support for ORDER BY / DISTINCT aggregates
Date: Mon, 07 Nov 2022 15:53:42 +0100
Message-ID: <2202180.iZASKD2KPV@aivenlaptop>
In-Reply-To: <9f61ddbf-2989-1536-b31e-6459370a6baa@postgrespro.ru>
References: <3163474.aeNJFYEL58@aivenronan>
 <CAApHDvowz-gfbuq=8iwHebRcy4VpFuJv52B3jCcXVi+CPFrd1A@mail.gmail.com>
 <9f61ddbf-2989-1536-b31e-6459370a6baa@postgrespro.ru>
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="iso-8859-1"
Archived-At: 
 <https://www.postgresql.org/message-id/2202180.iZASKD2KPV%40aivenlaptop>
Precedence: bulk

Le samedi 5 novembre 2022, 09:51:23 CET Pavel Luzanov a =E9crit :
> While playing with the patch I found a situation where the performance
> may be degraded compared to previous versions.
>=20
> The test case below.
> If you create a proper index for the query (a,c), version 16 wins. On my
> notebook, the query runs ~50% faster.
> But if there is no index (a,c), but only (a,b), in previous versions the
> planner uses it, but with this patch a full table scan is selected.

Hello,

In your exact use case, the combo incremental-sort + Index scan is evaluate=
d=20
to cost more than doing a full sort + seqscan.=20

If you try for example to create an index on (b, a) and group by b, you wil=
l=20
get the expected behaviour:

ro=3D# create index on t (b, a);
CREATE INDEX
ro=3D# explain  select b, array_agg(c order by c) from t group by b;
                                       QUERY PLAN                          =
             =20
=2D------------------------------------------------------------------------=
=2D---------------
 GroupAggregate  (cost=3D10.64..120926.80 rows=3D9970 width=3D36)
   Group Key: b
   ->  Incremental Sort  (cost=3D10.64..115802.17 rows=3D1000000 width=3D6)
         Sort Key: b, c
         Presorted Key: b
         ->  Index Scan using t_b_a_idx on t  (cost=3D0.42..47604.12=20
rows=3D1000000 width=3D6)
(6 rows)

I think we can trace that back to incremental sort being pessimistic about=
=20
it's performance. If you try the same query, but with set enable_seqscan =
=3D off,=20
you will get a full sort over an index scan:

                                       QUERY PLAN                          =
             =20
=2D------------------------------------------------------------------------=
=2D---------------
 GroupAggregate  (cost=3D154944.94..162446.19 rows=3D100 width=3D34)
   Group Key: a
   ->  Sort  (cost=3D154944.94..157444.94 rows=3D1000000 width=3D4)
         Sort Key: a, c
         ->  Index Scan using t_a_b_idx on t  (cost=3D0.42..41612.60=20
rows=3D1000000 width=3D4)
(5 rows)


This probably comes from the overly pessimistic behaviour that the number o=
f=20
tuples per group will be 1.5 times as much as we should estimate:

	/*
	 * Estimate average cost of sorting of one group where presorted=20
keys are
	 * equal.  Incremental sort is sensitive to distribution of tuples=20
to the
	 * groups, where we're relying on quite rough assumptions.  Thus,=20
we're
	 * pessimistic about incremental sort performance and increase its=20
average
	 * group size by half.
	 */

I can't see why an incrementalsort could be more expensive than a full sort=
,=20
using the same presorted path. It looks to me that in that case we should=20
always prefer an incrementalsort. Maybe we should bound incremental sorts c=
ost=20
to make sure they are never more expensive than the full sort ?

Also, prior to this commit I don't think it made a real difference, because=
=20
worst case scenario we would have missed an incremental sort, which we didn=
't=20
have beforehand. But with this patch, we may actually replace a "hidden"=20
incremental sort which was done in the agg codepath by a full sort.=20

Best regards,

=2D-
Ronan Dunklau