Subject: Re: POC: GROUP BY optimization

From: Alexander Korotkov <[email-masked]>
Date: Sat, 13 Jan 2024 17:00:03 +0200

On Sat, Jan 13, 2024 at 11:09 AM Andrei Lepikhov
<[email-masked]> wrote:
> On 11/1/2024 18:30, Alexander Korotkov wrote:
> > On Tue, Jan 9, 2024 at 1:14 PM Pavel Borisov <[email-masked]> wrote:
> >>> Hmm, I don't see this old code in these patches. Resend 0002-* because
> >>> of trailing spaces.
> >>
> >>
> >> AFAIK, cfbot does not seek old versions of patchset parts in previous messages. So for it to run correctly, a new version of the whole patchset should be sent even if most patches are unchanged.
> >
> > Please, find the revised patchset with some refactoring and comments
> > improvement from me.  I'll continue looking into this.
> The patch looks better, thanks to your refactoring.
> I propose additional comments and tests to make the code more
> understandable (see attachment).
> I intended to look into this part of the code more, but the tests show a
> difference between PostgreSQL v.15 and v.16, which causes changes in the
> code of this feature.

Makes sense.  I've incorporated your changes into the patchset.

------
Regards,
Alexander Korotkov

---

From: Andrei Lepikhov <[email-masked]>
Date: Sun, 14 Jan 2024 19:14:13 +0700

> Makes sense.  I've incorporated your changes into the patchset.
One more improvement. To underpin code change:

-               return cur_ec;  /* Match! */
+           {
+               /*
+                * Match!
+                *
+                * Copy the sortref if it wasn't set yet. That may happen if
+                * the ec was constructed from WHERE clause, i.e. it doesn't
+                * have a target reference at all.
+                */
+               if (cur_ec->ec_sortref == 0 && sortref > 0)
+                   cur_ec->ec_sortref = sortref;
+               return cur_ec;
+           }

I propose the test (see attachment). It shows why we introduce this 
change: GROUP-BY should juggle not only pathkeys generated by explicit 
sort operators but also planner-made, likewise in this example, by 
MergeJoin.

-- 
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 0d46e096e5..ca38e78f21 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -2879,6 +2879,37 @@ FROM t1 WHERE c2 < 100 GROUP BY c1 ORDER BY 2;
 (10 rows)
 
 DROP TABLE t1 CASCADE;
+-- Check, that GROUP-BY reordering optimization can operate with pathkeys, built
+-- by planner itself. For example, by MergeJoin.
+SET enable_hashjoin = off;
+SET enable_nestloop = off;
+explain (COSTS OFF)
+SELECT c1.relname,c1.relpages
+FROM pg_class c1 JOIN pg_class c2 ON (c1.relname=c2.relname AND c1.relpages=c2.relpages)
+GROUP BY c1.reltuples,c1.relpages,c1.relname
+ORDER BY c1.relpages, c1.relname, c1.relpages*c1.relpages;
+                                         QUERY PLAN                                          
+---------------------------------------------------------------------------------------------
+ Incremental Sort
+   Sort Key: c1.relpages, c1.relname, ((c1.relpages * c1.relpages))
+   Presorted Key: c1.relpages, c1.relname
+   ->  Group
+         Group Key: c1.relpages, c1.relname, c1.reltuples
+         ->  Incremental Sort
+               Sort Key: c1.relpages, c1.relname, c1.reltuples
+               Presorted Key: c1.relpages, c1.relname
+               ->  Merge Join
+                     Merge Cond: ((c1.relpages = c2.relpages) AND (c1.relname = c2.relname))
+                     ->  Sort
+                           Sort Key: c1.relpages, c1.relname
+                           ->  Seq Scan on pg_class c1
+                     ->  Sort
+                           Sort Key: c2.relpages, c2.relname
+                           ->  Seq Scan on pg_class c2
+(16 rows)
+
+RESET enable_hashjoin;
+RESET enable_nestloop;
 RESET enable_hashagg;
 RESET max_parallel_workers;
 RESET max_parallel_workers_per_gather;
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index f99167ac9e..cf87b5d5dd 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -1233,6 +1233,18 @@ SELECT array_agg(c1 ORDER BY c2),c2
 FROM t1 WHERE c2 < 100 GROUP BY c1 ORDER BY 2;
 DROP TABLE t1 CASCADE;
 
+-- Check, that GROUP-BY reordering optimization can operate with pathkeys, built
+-- by planner itself. For example, by MergeJoin.
+SET enable_hashjoin = off;
+SET enable_nestloop = off;
+explain (COSTS OFF)
+SELECT c1.relname,c1.relpages
+FROM pg_class c1 JOIN pg_class c2 ON (c1.relname=c2.relname AND c1.relpages=c2.relpages)
+GROUP BY c1.reltuples,c1.relpages,c1.relname
+ORDER BY c1.relpages, c1.relname, c1.relpages*c1.relpages;
+RESET enable_hashjoin;
+RESET enable_nestloop;
+
 RESET enable_hashagg;
 RESET max_parallel_workers;
 RESET max_parallel_workers_per_gather;

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 15 Jan 2024 02:19:41 +0200

> sort operators but also planner-made, likewise in this example, by

Thank you for providing the test case relevant for this code change.
The revised patch incorporating this change is attached.  Now the
patchset looks good to me.  I'm going to push it if there are no
objections.

------
Regards,
Alexander Korotkov

---

From: Richard Guo <[email-masked]>
Date: Mon, 15 Jan 2024 14:42:16 +0800

> patchset looks good to me.  I'm going to push it if there are no

Seems I'm late for the party.  Can we hold for several more days?  I'd
like to have a review on this patch.

Thanks
Richard

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 15 Jan 2024 09:56:32 +0200

On Mon, Jan 15, 2024 at 8:42 AM Richard Guo <[email-masked]> wrote:
> On Mon, Jan 15, 2024 at 8:20 AM Alexander Korotkov <[email-masked]> wrote:
>>

Sure, NP.  I'll hold it till your review.

------
Regards,
Alexander Korotkov

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 15 Jan 2024 16:46:03 +0700

On 15/1/2024 13:42, Richard Guo wrote:
> 
> On Mon, Jan 15, 2024 at 8:20 AM Alexander Korotkov <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
Get on board! It looks like this feature needs as much review as 
possible (likewise SJE).

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Richard Guo <[email-masked]>
Date: Tue, 16 Jan 2024 10:48:15 +0800

> Sure, NP.  I'll hold it till your review.

Thanks.  Appreciate that.

I have briefly reviewed this patch and here are some comments.

* When trying to match the ordering of GROUP BY to that of ORDER BY in
get_useful_group_keys_orderings, this patch checks against the length of
path->pathkeys.  This does not make sense.  I guess this is a typo and
the real intention is to check against root->sort_pathkeys.

--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -504,7 +504,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path
*path)
                                           root->num_groupby_pathkeys);

        if (n > 0 &&
-           (enable_incremental_sort || n == list_length(path->pathkeys)))
+           (enable_incremental_sort || n ==
list_length(root->sort_pathkeys)))

However, I think this is also incorrect.  When incremental sort is
disabled, it is reasonable to consider reordering the GROUP BY keys only
if the number of matching pathkeys is equal to the length of
root->group_pathkeys i.e. if 'n == list_length(root->group_pathkeys)'.

* When the original ordering of GROUP BY keys matches the path's
pathkeys or ORDER BY keys, get_useful_group_keys_orderings would
generate duplicate PathKeyInfos.  Consequently, this duplication would
lead to the creation and addition of identical paths multiple times.
This is not great.  Consider the query below:

create table t (a int, b int);
create index on t (a, b);
set enable_hashagg to off;

explain select count(*) from t group by a, b;
                                    QUERY PLAN
----------------------------------------------------------------------------------
 GroupAggregate  (cost=0.15..97.27 rows=226 width=16)
   Group Key: a, b
   ->  Index Only Scan using t_a_b_idx on t  (cost=0.15..78.06 rows=2260
width=8)
(3 rows)

The same path with group keys {a, b} is created and added twice.

* Part of the work performed in this patch overlaps with that of
preprocess_groupclause.  They are both trying to adjust the ordering of
the GROUP BY keys to match ORDER BY.  I wonder if it would be better to
perform this work only once.

* When reordering the GROUP BY keys, I think the following checks need
some improvements.

+       /*
+        * Since 1349d27 pathkey coming from underlying node can be in the
+        * root->group_pathkeys but not in the processed_groupClause. So, we
+        * should be careful here.
+        */
+       sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref,
+                                           *group_clauses);
+       if (!sgc)
+           /* The grouping clause does not cover this pathkey */
+           break;

I think we need to check or assert 'pathkey->pk_eclass->ec_sortref' is
valid before calling get_sortgroupref_clause_noerr with it.  Also, how
can we guarantee that the returned GROUP BY item is sortable?  Should we
check that with OidIsValid(sgc->sortop)?

Thanks
Richard

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 16 Jan 2024 17:05:33 +0200

Hi!

Thank you for your review.  The revised patchset is attached.

On Tue, Jan 16, 2024 at 4:48 AM Richard Guo <[email-masked]> wrote:
> On Mon, Jan 15, 2024 at 3:56 PM Alexander Korotkov <[email-masked]> wrote:
>>
> @@ -504,7 +504,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
> +           (enable_incremental_sort || n == list_length(root->sort_pathkeys)))
>

Hmm... Why should this be list_length(root->group_pathkeys) while
we're targeting root->sort_pathkeys.  I yet changed that to
list_length(root->sort_pathkeys).

>    ->  Index Only Scan using t_a_b_idx on t  (cost=0.15..78.06 rows=2260 width=8)
> (3 rows)
>

I tried to address that.

> perform this work only once.

Andrei, could you take a look.

> check that with OidIsValid(sgc->sortop)?

Added.

------
Regards,
Alexander Korotkov

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 18 Jan 2024 16:48:54 +0700

>> the real intention is to check against root->sort_pathkeys.
Thanks! It is really my blunder - fresh look works.
> list_length(root->sort_pathkeys).
I think, in the first case, when we are trying to arrange group-by keys 
according to underlying pathkeys with incremental sort = off, it makes 
sense to do if we fetch all group-by keys regardless of a more or equal 
number of path keys the incoming path contains. The code and test case 
are in step1.txt.
> Andrei, could you take a look.
As I see, the PathKeyInfo list often contains duplicated pathkeys, 
coming from either sort_pathkeys or path->pathkeys orderings. So, I can 
propose to check duplicates each time (see step2.txt in attachment).
>> check that with OidIsValid(sgc->sortop)?
Reviewed it, looks good.

-- 
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 919d54dd79..1095b73dac 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -489,8 +489,9 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 		n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
 										   root->num_groupby_pathkeys);
 
-		if (n > 0 && compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL &&
-			(enable_incremental_sort || n == list_length(path->pathkeys)))
+		if (n > 0 &&
+			(enable_incremental_sort || n == root->num_groupby_pathkeys) &&
+			compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL)
 		{
 			info = makeNode(PathKeyInfo);
 			info->pathkeys = pathkeys;
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index ca38e78f21..67dd20f375 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -2856,6 +2856,23 @@ explain (COSTS OFF) SELECT x,w FROM btg GROUP BY w,x,y,z ORDER BY x*x,z;
                ->  Index Scan using abc on btg
 (8 rows)
 
+SET enable_incremental_sort = off;
+-- The case when the number of incoming subtree path keys is more than
+-- the number of grouping keys.
+CREATE INDEX idx_y_x_z ON btg(y,x,w);
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT y,x,array_agg(distinct w) FROM btg WHERE y < 0 GROUP BY x,y;
+                     QUERY PLAN                      
+-----------------------------------------------------
+ GroupAggregate
+   Output: y, x, array_agg(DISTINCT w)
+   Group Key: btg.y, btg.x
+   ->  Index Only Scan using idx_y_x_z on public.btg
+         Output: y, x, w
+         Index Cond: (btg.y < 0)
+(6 rows)
+
+RESET enable_incremental_sort;
 DROP TABLE btg;
 -- The case, when scanning sort order correspond to aggregate sort order but
 -- can not be found in the group-by list
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index 9880a188d3..524bdfa67d 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -1182,7 +1182,6 @@ SELECT balk(hundred) FROM tenk1;
 ROLLBACK;
 
 -- GROUP BY optimization by reorder columns
-
 CREATE TABLE btg AS SELECT
   i % 100 AS x,
   i % 100 AS y,
@@ -1223,8 +1222,11 @@ explain (COSTS OFF) SELECT x,y FROM btg GROUP BY w,x,z,y ORDER BY y,x,z,w;
 explain (COSTS OFF) SELECT x,w FROM btg GROUP BY w,x,y,z ORDER BY x*x,z;
 
 SET enable_incremental_sort = off;
-EXPLAIN (VERBOSE, COSTS ON)
-SELECT x,y, array_agg(z) FROM btg WHERE x < 2 GROUP BY y,x;
+-- The case when the number of incoming subtree path keys is more than
+-- the number of grouping keys.
+CREATE INDEX idx_y_x_z ON btg(y,x,w);
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT y,x,array_agg(distinct w) FROM btg WHERE y < 0 GROUP BY x,y;
 RESET enable_incremental_sort;
 
 DROP TABLE btg;

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 18 Jan 2024 21:18:34 +0700

Just forgotten second attachment.

-- 
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 1095b73dac..b612420547 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -432,6 +432,21 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 	return n;
 }
 
+static bool
+duplicated_pathkey_combination(List *infos, List *pathkeys)
+{
+	ListCell *lc;
+
+	foreach (lc, infos)
+	{
+		PathKeyInfo *info = lfirst_node(PathKeyInfo, lc);
+
+		if (compare_pathkeys(pathkeys, info->pathkeys) == PATHKEYS_EQUAL)
+			return true;
+	}
+	return false;
+}
+
 /*
  * get_useful_group_keys_orderings
  *		Determine which orderings of GROUP BY keys are potentially interesting.
@@ -491,7 +506,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 
 		if (n > 0 &&
 			(enable_incremental_sort || n == root->num_groupby_pathkeys) &&
-			compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL)
+			!duplicated_pathkey_combination(infos, pathkeys))
 		{
 			info = makeNode(PathKeyInfo);
 			info->pathkeys = pathkeys;
@@ -514,8 +529,9 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 										   &clauses,
 										   root->num_groupby_pathkeys);
 
-		if (n > 0 && compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL &&
-			(enable_incremental_sort || n == list_length(root->sort_pathkeys)))
+		if (n > 0 &&
+			(enable_incremental_sort || n == list_length(root->sort_pathkeys)) &&
+			!duplicated_pathkey_combination(infos, pathkeys))
 		{
 			info = makeNode(PathKeyInfo);
 			info->pathkeys = pathkeys;

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 19 Jan 2024 16:21:48 +0200

Hi!

I've applied your changes with minor editing, thank you.

> propose to check duplicates each time (see step2.txt in attachment).

Actually I asked to recheck if we can cut some part of
preprocess_groupclause() given that we're reordering the pathkeys
later.  It seems that we can remove everything except the work with a
grouping set.  I've done this in the revised patchset.

I'm going to push this if there are no objections.

------
Regards,
Alexander Korotkov

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 24 Jan 2024 11:37:35 -0600

A recent buildfarm failure [0] seems to indicate a name collision with the
"abc" index in the aggregates.sql test and the "abc" table in
namespace.sql.

[0] https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=piculet&dt=2024-01-24%2014%3A05%3A14

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 24 Jan 2024 21:44:56 +0200

> [0] https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=piculet&dt=2024-01-24%2014%3A05%3A14

Thank you for catching this.  Fixed.

------
Regards,
Alexander Korotkov

---

From: vignesh C <[email-masked]>
Date: Fri, 26 Jan 2024 20:07:42 +0530

> Thank you for catching this.  Fixed.

Since the patch has been committed, I have marked this entry as committed.

Regards,
Vignesh

---

From: Tom Lane <[email-masked]>
Date: Thu, 01 Feb 2024 21:02:35 -0500

> I'm going to push this if there are no objections.

One of the test cases added by this commit has not been very
stable in the buildfarm.  Latest example is here:

https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=prion&dt=2024-02-01%2021%3A28%3A04

and I've seen similar failures intermittently on other machines.

I'd suggest building this test atop a table that is more stable
than pg_class.  You're just waving a red flag in front of a bull
if you expect stable statistics from that during a regression run.
Nor do I see any particular reason for pg_class to be especially
suited to the test.

			regards, tom lane

---

From: Richard Guo <[email-masked]>
Date: Fri, 2 Feb 2024 11:32:17 +0800

> Nor do I see any particular reason for pg_class to be especially

Yeah, it's not a good practice to use pg_class in this place.  While
looking through the test cases added by this commit, I noticed some
other minor issues that are not great.  Such as

* The table 'btg' is inserted with 10000 tuples, which seems a bit
expensive for a test.  I don't think we need such a big table to test
what we want.

* I don't see why we need to manipulate GUC max_parallel_workers and
max_parallel_workers_per_gather.

* I think we'd better write the tests with the keywords being all upper
or all lower.  A mixed use of upper and lower is not great. Such as in

    explain (COSTS OFF) SELECT x,y FROM btg GROUP BY x,y,z,w;

* Some comments for the test queries are not easy to read.

* For this statement

    CREATE INDEX idx_y_x_z ON btg(y,x,w);

I think the index name would cause confusion.  It creates an index on
columns y, x and w, but the name indicates an index on y, x and z.

I'd like to write a draft patch for the fixes.

Thanks
Richard

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 2 Feb 2024 10:42:45 +0700

> Nor do I see any particular reason for pg_class to be especially
Yeah, It is my fault. Please, see in the attachment the patch fixing that.
-- 
regards,
Andrei Lepikhov
Postgres Professional
From 11a049d95ee48e38ad569aab7663d8de91f946ad Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Fri, 2 Feb 2024 10:39:55 +0700
Subject: [PATCH] Replace the GROUP-BY optimization test with the same based on
 something less volatile when the pg_class relation.

---
 src/test/regress/expected/aggregates.out | 32 +++++++++++-------------
 src/test/regress/sql/aggregates.sql      |  9 +++----
 2 files changed, 18 insertions(+), 23 deletions(-)

diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 7a73c19314..c2e1b8c9ed 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -2873,7 +2873,6 @@ SELECT y,x,array_agg(distinct w) FROM btg WHERE y < 0 GROUP BY x,y;
 (6 rows)
 
 RESET enable_incremental_sort;
-DROP TABLE btg;
 -- The case, when scanning sort order correspond to aggregate sort order but
 -- can not be found in the group-by list
 CREATE TABLE agg_sort_order (c1 int PRIMARY KEY, c2 int);
@@ -2901,32 +2900,31 @@ DROP TABLE agg_sort_order CASCADE;
 SET enable_hashjoin = off;
 SET enable_nestloop = off;
 explain (COSTS OFF)
-SELECT c1.relname,c1.relpages
-FROM pg_class c1 JOIN pg_class c2 ON (c1.relname=c2.relname AND c1.relpages=c2.relpages)
-GROUP BY c1.reltuples,c1.relpages,c1.relname
-ORDER BY c1.relpages, c1.relname, c1.relpages*c1.relpages;
-                                         QUERY PLAN                                          
----------------------------------------------------------------------------------------------
+SELECT b1.x,b1.w FROM btg b1 JOIN btg b2 ON (b1.z=b2.z AND b1.w=b2.w)
+GROUP BY b1.x,b1.z,b1.w ORDER BY b1.z, b1.w, b1.x*b1.x;
+                            QUERY PLAN                             
+-------------------------------------------------------------------
  Incremental Sort
-   Sort Key: c1.relpages, c1.relname, ((c1.relpages * c1.relpages))
-   Presorted Key: c1.relpages, c1.relname
+   Sort Key: b1.z, b1.w, ((b1.x * b1.x))
+   Presorted Key: b1.z, b1.w
    ->  Group
-         Group Key: c1.relpages, c1.relname, c1.reltuples
+         Group Key: b1.z, b1.w, b1.x
          ->  Incremental Sort
-               Sort Key: c1.relpages, c1.relname, c1.reltuples
-               Presorted Key: c1.relpages, c1.relname
+               Sort Key: b1.z, b1.w, b1.x
+               Presorted Key: b1.z, b1.w
                ->  Merge Join
-                     Merge Cond: ((c1.relpages = c2.relpages) AND (c1.relname = c2.relname))
+                     Merge Cond: ((b1.z = b2.z) AND (b1.w = b2.w))
                      ->  Sort
-                           Sort Key: c1.relpages, c1.relname
-                           ->  Seq Scan on pg_class c1
+                           Sort Key: b1.z, b1.w
+                           ->  Seq Scan on btg b1
                      ->  Sort
-                           Sort Key: c2.relpages, c2.relname
-                           ->  Seq Scan on pg_class c2
+                           Sort Key: b2.z, b2.w
+                           ->  Seq Scan on btg b2
 (16 rows)
 
 RESET enable_hashjoin;
 RESET enable_nestloop;
+DROP TABLE btg;
 RESET enable_hashagg;
 RESET max_parallel_workers;
 RESET max_parallel_workers_per_gather;
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index 916dbf908f..3548fbb8db 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -1229,8 +1229,6 @@ EXPLAIN (VERBOSE, COSTS OFF)
 SELECT y,x,array_agg(distinct w) FROM btg WHERE y < 0 GROUP BY x,y;
 RESET enable_incremental_sort;
 
-DROP TABLE btg;
-
 -- The case, when scanning sort order correspond to aggregate sort order but
 -- can not be found in the group-by list
 CREATE TABLE agg_sort_order (c1 int PRIMARY KEY, c2 int);
@@ -1245,13 +1243,12 @@ DROP TABLE agg_sort_order CASCADE;
 SET enable_hashjoin = off;
 SET enable_nestloop = off;
 explain (COSTS OFF)
-SELECT c1.relname,c1.relpages
-FROM pg_class c1 JOIN pg_class c2 ON (c1.relname=c2.relname AND c1.relpages=c2.relpages)
-GROUP BY c1.reltuples,c1.relpages,c1.relname
-ORDER BY c1.relpages, c1.relname, c1.relpages*c1.relpages;
+SELECT b1.x,b1.w FROM btg b1 JOIN btg b2 ON (b1.z=b2.z AND b1.w=b2.w)
+GROUP BY b1.x,b1.z,b1.w ORDER BY b1.z, b1.w, b1.x*b1.x;
 RESET enable_hashjoin;
 RESET enable_nestloop;
 
+DROP TABLE btg;
 RESET enable_hashagg;
2.43.0

---

From: Richard Guo <[email-masked]>
Date: Fri, 2 Feb 2024 12:06:42 +0800

> I'd like to write a draft patch for the fixes.

Here is the draft patch that fixes the issues I complained about in
upthread.

Thanks
Richard

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 2 Feb 2024 11:40:12 +0700

On 2/2/2024 11:06, Richard Guo wrote:
> 
> On Fri, Feb 2, 2024 at 11:32 AM Richard Guo <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
>     On Fri, Feb 2, 2024 at 10:02 AM Tom Lane <[email-masked]
>     <mailto:[email-masked]>> wrote:
> 
>         https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=prion&dt=2024-02-01%2021%3A28%3A04 <https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=prion&dt=2024-02-01%2021%3A28%3A04>
> 
I passed through the patch. Looks like it doesn't break anything. Why do 
you prefer to use count(*) in EXPLAIN instead of plain targetlist, like 
"SELECT x,y,..."?
Also, according to the test mentioned by Tom:
1. I see, PG uses IndexScan on (x,y). So, column x will be already 
sorted before the MergeJoin. Why not use Incremental Sort on (x,z,w) 
instead of full sort?
2. For memo, IMO, this test shows us the future near perspective of this 
feature: It is cheaper to use grouping order (w,z) instead of (z,w).

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Richard Guo <[email-masked]>
Date: Wed, 21 Feb 2024 16:08:12 +0800

On Fri, Feb 2, 2024 at 12:40 PM Andrei Lepikhov <[email-masked]>
wrote:

> <

> you prefer to use count(*) in EXPLAIN instead of plain targetlist, like

Nothing special.  Just making the test cases consistent as much as
possible.

> sorted before the MergeJoin. Why not use Incremental Sort on (x,z,w)

I think that's because the planner chooses to use (z, w, x) to perform
the mergejoin.  I did not delve into the details, but I guess the cost
estimation decides this is cheaper.

Hi Alexander,

What do you think about the revisions for the test cases?

Thanks
Richard

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 21 Feb 2024 12:19:53 +0200

Hi, Richard!

> What do you think about the revisions for the test cases?

I've rebased your patch upthread.  Did some minor beautifications.

> expensive for a test.  I don't think we need such a big table to test

Your patch reduces the number of rows to 1000 tuples.  I found it
possible to further reduce it to 100 tuples.  That also allowed me to
save the plan in the test case introduced by e1b7fde418.

Please check if you're OK with the patch attached.

------
Regards,
Alexander Korotkov

---

From: Maxim Orlov <[email-masked]>
Date: Wed, 21 Feb 2024 18:08:54 +0300

Hi!

Another issue on test introduced in 0452b461bc405. I think it may be
unstable in some circumstances.
For example, if we'll try to use different BLCKSZ. See, I've made a little
change in the number of tuples to be inserted:

$ git diff
diff --git a/src/test/regress/sql/aggregates.sql
b/src/test/regress/sql/aggregates.sql
index d6ed5d0eff..414078d4ec 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -1187,7 +1187,7 @@ CREATE TABLE btg AS SELECT
   i % 100 AS y,
   'abc' || i % 10 AS z,
   i AS w
-FROM generate_series(1,10000) AS i;
+FROM generate_series(1,11900) AS i;
 CREATE INDEX btg_x_y_idx ON btg(x,y);
 ANALYZE btg;

And the bulk extension is kicked, so we got zeroed pages in the relation.
The plane is also changed,
switched to seq scan from index scan:
@@ -2734,7 +2734,7 @@
   i % 100 AS y,
   'abc' || i % 10 AS z,
   i AS w
-FROM generate_series(1,10000) AS i;
+FROM generate_series(1,11900) AS i;
 CREATE INDEX btg_x_y_idx ON btg(x,y);
 ANALYZE btg;
 -- GROUP BY optimization by reorder columns by frequency
@@ -2760,62 +2760,57 @@

 -- Engage incremental sort
 explain (COSTS OFF) SELECT x,y FROM btg GROUP BY x,y,z,w;
-                   QUERY PLAN
--------------------------------------------------
+          QUERY PLAN
+------------------------------
  Group
    Group Key: x, y, z, w
-   ->  Incremental Sort
+   ->  Sort
          Sort Key: x, y, z, w
-         Presorted Key: x, y
-         ->  Index Scan using btg_x_y_idx on btg
-(6 rows)
+         ->  Seq Scan on btg
+(5 rows)
... and so on.

So, my proposal is simple. I think we need not just "ANALYZE btg", but
"VACUUM ANALYZE btg", to get rid of zeroed pages in this particular
case. PFA corresponding patch.

-- 
Best regards,
Maxim Orlov.

---

From: Richard Guo <[email-masked]>
Date: Thu, 22 Feb 2024 10:09:20 +0800

> Please check if you're OK with the patch attached.

I looked through the v2 patch and have two comments.

* The test case under "Check we don't pick aggregate path key instead of
grouping path key" does not have EXPLAIN to show the plan.  So how can
we ensure we do not mistakenly select the aggregate pathkeys instead of
the grouping pathkeys?

* I don't think the test case introduced by e1b7fde418 is still needed,
because we already have one under "Utilize the ordering of merge join to
avoid a full Sort operation".  This kind of test case is just to ensure
that we are able to utilize the ordering of the subplans underneath.  So
it should be parallel to the test cases for utilize the ordering of
index scan and subquery scan.

See the attached v3 patch.  I also made cosmetic tweaks to the comments,
and simplified a test case query.

Thanks
Richard

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 22 Feb 2024 11:18:42 +0700

On 22/2/2024 09:09, Richard Guo wrote:
> 
> On Wed, Feb 21, 2024 at 6:20 PM Alexander Korotkov <[email-masked] 
I confirm it works correctly. I am not sure about the stability of the 
zeros number in the output on different platforms here:
        avg
--------------------
  4.0000000000000000
  5.0000000000000000
It was why I'd used the format() function before. So, may we elaborate 
on the test and restrict the output?
> index scan and subquery scan.
I confirm, this version also checks ec_sortref initialization in the 
case when ec are contructed from WHERE clause. Generally, I like more 
one test for one issue instead of one test for all at once. But it works 
and I don't have any reason to dispute it.

Also, I'm unsure about removing the disabling of the 
max_parallel_workers_per_gather parameter. Have you discovered the 
domination of the current plan over the partial one? Do the cost 
fluctuations across platforms not trigger a parallel plan?

What's more, I suggest to address here the complaint from [1]. As I see, 
cost difference between Sort and IncrementalSort strategies in that case 
is around 0.5. To make the test more stable I propose to change it a bit 
and add a limit:
SELECT count(*) FROM btg GROUP BY z, y, w, x LIMIT 10;
It makes efficacy of IncrementalSort more obvious difference around 10 
cost points.

[1] 
https://www.postgresql.org/message-id/CACG=ezaYM1tr6Lmp8PRH1aeZq=[email-masked]

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Richard Guo <[email-masked]>
Date: Thu, 22 Feb 2024 14:35:41 +0800

> zeros number in the output on different platforms here:

The avg() function on integer argument is commonly used in
aggregates.sql.  I don't think this is an issue.  See the first test
query in aggregates.sql.

SELECT avg(four) AS avg_1 FROM onek;
       avg_1
--------------------
 1.5000000000000000
(1 row)

> fluctuations across platforms not trigger a parallel plan?

The table used for testing contains only 100 tuples, which is the size
of only one page.  I don't believe it would trigger any parallel plans,
unless we manually change min_parallel_table_scan_size.

> It makes efficacy of IncrementalSort more obvious difference around 10

I don't think that's necessary.  With Incremental Sort the final cost
is:

    GroupAggregate  (cost=1.66..19.00 rows=100 width=25)

while with full Sort it is:

    GroupAggregate  (cost=16.96..19.46 rows=100 width=25)

With the STD_FUZZ_FACTOR (1.01), there is no doubt that the first path
is cheaper on total cost.  Not to say that even if somehow we decide the
two paths are fuzzily the same on total cost, the first path still
dominates because its startup cost is much cheaper.

Thanks
Richard

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 22 Feb 2024 14:04:55 +0700

> aggregates.sql.  I don't think this is an issue.  See the first test
Make sense
> unless we manually change min_parallel_table_scan_size.
I don't intend to argue it, but just for the information, I frequently 
reduce it to zero, allowing PostgreSQL to make a decision based on 
costs. It sometimes works much better, because one small table in multi 
join can disallow an effective parallel plan.
> dominates because its startup cost is much cheaper.
As before, I won't protest here - it needs some computations about how 
much cost can be added by bulk extension of the relation blocks. If 
Maxim will answer that it's enough to resolve his issue, why not?

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Tom Lane <[email-masked]>
Date: Thu, 11 Apr 2024 19:44:42 -0400

I'm late to the party, and I apologize for not having paid attention
to this thread for months ... but I am wondering why 0452b461b got
committed.  It seems to add a substantial amount of complexity and
planner cycles in return for not much.  The reason why I'm dubious
about it can be found in this comment that the patch deleted:

- * In principle it might be interesting to consider other orderings of the
- * GROUP BY elements, which could match the sort ordering of other
- * possible plans (eg an indexscan) and thereby reduce cost.  We don't
- * bother with that, though.  Hashed grouping will frequently win anyway.

Indeed, if you remove the

SET enable_hashagg = off;
SET enable_seqscan = off;

lines added to aggregates.sql, you find that every single one of the
test cases added there changes plan, except for the one case that is
there to prove that the planner *doesn't* pick this type of plan.
That shows that the planner doesn't believe any of the plans developed
here are cheaper than other alternatives it would normally consider
(usually HashAgg).  So it sure seems like we're spending a lot of
effort on uninteresting plans.  Maybe this is an artifact of testing
against toy tables and a useful win could be shown on bigger tables,
but I don't see any indication in the thread that anyone actually
demonstrated that.

I might hold still for this patch anyway if the patch were simpler
and more obviously correct, but there are scary bits in it:

* The very first hunk causes get_eclass_for_sort_expr to have
side-effects on existing EquivalenceClass data structures.
What is the argument that that's not going to cause problems?
At the very least it introduces asymmetry, in that the first
caller wins the chance to change the EC's ec_sortref and later
callers won't be able to.

* I'm pretty unconvinced by group_keys_reorder_by_pathkeys (which
I notice has already had one band-aid added to it since commit).
In particular, it seems to believe that the pathkeys and clauses
lists match one-for-one, but I seriously doubt that that invariant
remains guaranteed after the cleanup steps

    /* append the remaining group pathkeys (will be treated as not sorted) */
    *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
                                             *group_pathkeys);
    *group_clauses = list_concat_unique_ptr(new_group_clauses,
                                            *group_clauses);

For that to be reliable, the SortGroupClauses added to
new_group_clauses in the main loop have to be exactly those
that are associated with the same pathkeys in the old lists.
I doubt that that's necessarily true in the presence of redundant
grouping clauses.  (Maybe we can't get here with any redundant
grouping clauses, but still, we don't really guarantee uniqueness of
SortGroupClauses, much less that they are never copied which is what
you need if you want to believe that pointer equality is sufficient
for de-duping here.  PathKeys are explicitly made to be safe to compare
pointer-wise, but I know of no such guarantee for SortGroupClauses.)

* It seems like root->processed_groupClause no longer has much to do
with the grouping behavior, which is scary given how much code still
believes that it does.  I suspect there are bugs lurking there, and
am not comforted by the fact that the patch changed exactly nothing
in the pathnodes.h documentation of that field.  This comment looks
pretty silly now too:

            /* Preprocess regular GROUP BY clause, if any */
            root->processed_groupClause = list_copy(parse->groupClause);

What "preprocessing" is going on there?  This comment was adequate
before, when the code line invoked preprocess_groupclause which had
a bunch of commentary; but now it has to stand on its own and it's
not doing a great job of that.

* Speaking of pathnodes.h, PathKeyInfo is a pretty uninformative node
type name, and the comments provided for it are not going to educate
anybody.  What is the "association" between the pathkeys and clauses?
I guess the clauses are supposed to be SortGroupClauses, but not all
pathkeys match up to SortGroupClauses, so what then?  This is very
underspecified, and fuzzy thinking about data structures tends to lead
to bugs.

So I'm quite afraid that there are still bugs lurking here.
What's more, given that the plans this patch makes apparently
seldom win when you don't put a thumb on the scales, it might
take a very long time to isolate those bugs.  If the patch
produces a faulty plan (e.g. not sorted properly) we'd never
notice if that plan isn't chosen, and even if it is chosen
it probably wouldn't produce anything as obviously wrong as
a crash.

If this patch were producing better results I'd be more excited
about putting more work into it.  But on the basis of what I'm
seeing right now, I think maybe we ought to give up on it.

			regards, tom lane

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 12 Apr 2024 12:05:14 +0700

> seeing right now, I think maybe we ought to give up on it.
First, thanks for the deep review - sometimes, only a commit gives us a 
chance to get such observation :))).
On a broader note, introducing automatic group-by-order choosing is a 
step towards training the optimiser to handle poorly tuned incoming 
queries. While it's true that this may initially impact performance, 
it's crucial to weigh the potential benefits. So, beforehand, we should 
agree: Is it worth it?
If yes, I would say I see how often hashing doesn't work in grouping. 
Sometimes because of estimation errors, sometimes because grouping 
already has sorted input, sometimes in analytical queries when planner 
doesn't have enough memory for hashing. In analytical cases, the only 
way to speed up queries sometimes is to be smart with features like 
IncrementalSort and this one.
About low efficiency. Remember the previous version of the GROUP-BY 
optimisation - we disagreed on operator costs and the cost model in 
general. In the current version, we went the opposite - adding small 
features step-by-step. The current commit contains an integral part of 
the feature and is designed for safely testing the approach and adding 
more profitable parts like choosing group-by-order according to distinct 
values or unique indexes on grouping columns.
I have passed through the code being steered by the issues explained in 
detail. I see seven issues. Two of them definitely should be scrutinised 
right now, and I'm ready to do that.

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 16 Apr 2024 12:59:35 +0700

> callers won't be able to.
Let me resolve issues bit by bit.
Addressing your first note, 'asymmetry,' I discovered this part of the 
code. Before the 8d83a5d, it could cause some artefacts, but since then, 
a kind of asymmetry has been introduced into the GROUP-BY clause list.
As you can see in the attached patch, GROUP-BY reordering works even 
when the asymmetry of the 8d83a5d chooses different keys.

At the same time, I agree that implicitly setting anything in an 
exporting function, which should just look up for EC, is a questionable 
coding style. To avoid possible usage issues (in extensions, for 
example), I propose setting it up afterwards, explicitly forcing this 
action by input parameter - see my attempt in the attachment.

-- 
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index a619ff9177..bc08dfadaf 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -652,18 +652,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 
 			if (opcintype == cur_em->em_datatype &&
 				equal(expr, cur_em->em_expr))
-			{
-				/*
-				 * Match!
-				 *
-				 * Copy the sortref if it wasn't set yet.  That may happen if
-				 * the ec was constructed from a WHERE clause, i.e. it doesn't
-				 * have a target reference at all.
-				 */
-				if (cur_ec->ec_sortref == 0 && sortref > 0)
-					cur_ec->ec_sortref = sortref;
-				return cur_ec;
-			}
+				return cur_ec; /* Match! */
 		}
 	}
 
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 1d61881a6b..5d9597adcd 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -1355,7 +1355,8 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
 													&sortclauses,
 													tlist,
 													false,
-													&sortable);
+													&sortable,
+													false);
 	/* It's caller error if not all clauses were sortable */
 	Assert(sortable);
 	return result;
@@ -1379,13 +1380,16 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
  * to remove any clauses that can be proven redundant via the eclass logic.
  * Even though we'll have to hash in that case, we might as well not hash
  * redundant columns.)
+ * *set_ec_sortref is true if caller wants to set up ec_sortref field in
+ * the pathkey Equivalence Class, if it have not initialized beforehand.
  */
 List *
 make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
 									   List **sortclauses,
 									   List *tlist,
 									   bool remove_redundant,
-									   bool *sortable)
+									   bool *sortable,
+									   bool set_ec_sortref)
 {
 	List	   *pathkeys = NIL;
 	ListCell   *l;
@@ -1409,6 +1413,13 @@ make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
 										   sortcl->nulls_first,
 										   sortcl->tleSortGroupRef,
 										   true);
+		if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
+			/*
+			 * Copy the sortref if it wasn't set yet.  That may happen if
+			 * the ec was constructed from a WHERE clause, i.e. it doesn't
+			 * have a target reference at all.
+			 */
+			pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
 
 		/* Canonical form eliminates redundant ordering keys */
 		if (!pathkey_is_redundant(pathkey, pathkeys))
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5320da51a0..dee98c9a90 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3391,7 +3391,7 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 		/*
 		 * With a plain GROUP BY list, we can remove any grouping items that
 		 * are proven redundant by EquivalenceClass processing.  For example,
-		 * we can remove y given "WHERE x = y GROUP BY x, y".  These aren't
+		 * we can remove y given "WHERE x get_eclass_for_sort_expr= y GROUP BY x, y".  These aren't
 		 * especially common cases, but they're nearly free to detect.  Note
 		 * that we remove redundant items from processed_groupClause but not
 		 * the original parse->groupClause.
@@ -3403,7 +3403,8 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 												   &root->processed_groupClause,
 												   tlist,
 												   true,
-												   &sortable);
+												   &sortable,
+												   true);
 		if (!sortable)
 		{
 			/* Can't sort; no point in considering aggregate ordering either */
@@ -3453,7 +3454,8 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 												   &root->processed_distinctClause,
 												   tlist,
 												   true,
-												   &sortable);
+												   &sortable,
+												   false);
 		if (!sortable)
 			root->distinct_pathkeys = NIL;
 	}
@@ -3479,7 +3481,8 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 												   &groupClauses,
 												   tlist,
 												   false,
-												   &sortable);
+												   &sortable,
+												   false);
 		if (!sortable)
 			root->setop_pathkeys = NIL;
 	}
@@ -6027,7 +6030,8 @@ make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
 																 &wc->partitionClause,
 																 tlist,
 																 true,
-																 &sortable);
+																 &sortable,
+																 false);
 
 		Assert(sortable);
 	}
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 39ba461548..fff4b69dfd 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -242,7 +242,8 @@ extern List *make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
 													List **sortclauses,
 													List *tlist,
 													bool remove_redundant,
-													bool *sortable);
+													bool *sortable,
+													bool set_ec_sortref);
 extern void initialize_mergeclause_eclasses(PlannerInfo *root,
 											RestrictInfo *restrictinfo);
 extern void update_mergeclause_eclasses(PlannerInfo *root,
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 50695d83a2..1b06f9ca97 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -2886,6 +2886,53 @@ GROUP BY c1.w, c1.z;
  5.0000000000000000
 (2 rows)
 
+-- Pathkeys, built in subtree, can be used to optimize GROUP-BY clause ordering.
+-- Also, here we check that it doesn't depend on the initial clause order in the
+-- GROUP-BY list.
+EXPLAIN (COSTS OFF)
+SELECT c1.y,c1.x FROM group_agg_pk c1
+  JOIN group_agg_pk c2
+  ON c1.x = c2.x
+GROUP BY c1.y,c1.x,c2.x;
+                     QUERY PLAN                      
+-----------------------------------------------------
+ Group
+   Group Key: c1.x, c1.y
+   ->  Incremental Sort
+         Sort Key: c1.x, c1.y
+         Presorted Key: c1.x
+         ->  Merge Join
+               Merge Cond: (c1.x = c2.x)
+               ->  Sort
+                     Sort Key: c1.x
+                     ->  Seq Scan on group_agg_pk c1
+               ->  Sort
+                     Sort Key: c2.x
+                     ->  Seq Scan on group_agg_pk c2
+(13 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT c1.y,c1.x FROM group_agg_pk c1
+  JOIN group_agg_pk c2
+  ON c1.x = c2.x
+GROUP BY c1.y,c2.x,c1.x;
+                     QUERY PLAN                      
+-----------------------------------------------------
+ Group
+   Group Key: c2.x, c1.y
+   ->  Incremental Sort
+         Sort Key: c2.x, c1.y
+         Presorted Key: c2.x
+         ->  Merge Join
+               Merge Cond: (c1.x = c2.x)
+               ->  Sort
+                     Sort Key: c1.x
+                     ->  Seq Scan on group_agg_pk c1
+               ->  Sort
+                     Sort Key: c2.x
+                     ->  Seq Scan on group_agg_pk c2
+(13 rows)
+
 RESET enable_nestloop;
 RESET enable_hashjoin;
 DROP TABLE group_agg_pk;
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index 2905848ead..0be9c48483 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -1253,6 +1253,20 @@ SELECT avg(c1.f ORDER BY c1.x, c1.y)
 FROM group_agg_pk c1 JOIN group_agg_pk c2 ON c1.x = c2.x
 GROUP BY c1.w, c1.z;
 
+-- Pathkeys, built in subtree, can be used to optimize GROUP-BY clause ordering.
+-- Also, here we check that it doesn't depend on the initial clause order in the
+-- GROUP-BY list.
+EXPLAIN (COSTS OFF)
+SELECT c1.y,c1.x FROM group_agg_pk c1
+  JOIN group_agg_pk c2
+  ON c1.x = c2.x
+GROUP BY c1.y,c1.x,c2.x;
+EXPLAIN (COSTS OFF)
+SELECT c1.y,c1.x FROM group_agg_pk c1
+  JOIN group_agg_pk c2
+  ON c1.x = c2.x
+GROUP BY c1.y,c2.x,c1.x;
+
 RESET enable_nestloop;
 RESET enable_hashjoin;
 DROP TABLE group_agg_pk;

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 17 Apr 2024 10:11:59 +0700

> pointer-wise, but I know of no such guarantee for SortGroupClauses.)
I spent a lot of time inventing situations with SortGroupClause 
duplicates. Unfortunately, it looks impossible so far. But because we 
really don't guarantee uniqueness, I changed the code to survive in this 
case. Also, I added assertion checking to be sure we don't have logical 
mistakes here - see attachment.
About the band-aid mentioned above - as I see, 4169850 introduces the 
same trick in planner.c. So, it looks like result of design of the 
current code.

-- 
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 5d9597adcd..aa80f6486c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -380,15 +380,18 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 
 	/*
 	 * We're going to search within just the first num_groupby_pathkeys of
-	 * *group_pathkeys.  The thing is that root->group_pathkeys is passed as
+	 * *group_pathkeys. The thing is that root->group_pathkeys is passed as
 	 * *group_pathkeys containing grouping pathkeys altogether with aggregate
-	 * pathkeys.  If we process aggregate pathkeys we could get an invalid
+	 * pathkeys. If we process aggregate pathkeys we could get an invalid
 	 * result of get_sortgroupref_clause_noerr(), because their
-	 * pathkey->pk_eclass->ec_sortref doesn't referece query targetlist.  So,
+	 * pathkey->pk_eclass->ec_sortref doesn't reference query targetlist. So,
 	 * we allocate a separate list of pathkeys for lookups.
 	 */
 	grouping_pathkeys = list_copy_head(*group_pathkeys, num_groupby_pathkeys);
 
+	/* Make a new copy before reordering clauses */
+	*group_clauses = list_copy(*group_clauses);
+
 	/*
 	 * Walk the pathkeys (determining ordering of the input path) and see if
 	 * there's a matching GROUP BY key. If we find one, we append it to the
@@ -400,8 +403,8 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 	 */
 	foreach(lc, pathkeys)
 	{
-		PathKey    *pathkey = (PathKey *) lfirst(lc);
-		SortGroupClause *sgc;
+		PathKey			   *pathkey = (PathKey *) lfirst(lc);
+		SortGroupClause	   *sgc;
 
 		/*
 		 * Pathkeys are built in a way that allows simply comparing pointers.
@@ -431,17 +434,25 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 		Assert(OidIsValid(sgc->sortop));
 
 		new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
+
+		/*
+		 * Keeping in mind that the SortGroupClause list doesn't guarantee
+		 * unique pointers we must explicitly transfer elements one-by-one.
+		 */
 		new_group_clauses = lappend(new_group_clauses, sgc);
+		*group_clauses = list_delete_ptr(*group_clauses, sgc);
 	}
 
 	/* remember the number of pathkeys with a matching GROUP BY key */
 	n = list_length(new_group_pathkeys);
 
-	/* append the remaining group pathkeys (will be treated as not sorted) */
+	/*
+	 * Append the remaining group pathkeys (will be treated as not sorted) and
+	 * grouping clauses.
+	 */
 	*group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
 											 *group_pathkeys);
-	*group_clauses = list_concat_unique_ptr(new_group_clauses,
-											*group_clauses);
+	*group_clauses = list_concat(new_group_clauses, *group_clauses);
 
 	list_free(grouping_pathkeys);
 	return n;
@@ -484,9 +495,9 @@ pathkeys_are_duplicate(List *infos, List *pathkeys)
 List *
 get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 {
-	Query	   *parse = root->parse;
-	List	   *infos = NIL;
-	PathKeyInfo *info;
+	Query		   *parse = root->parse;
+	List		   *infos = NIL;
+	PathKeyInfo	   *info;
 
 	List	   *pathkeys = root->group_pathkeys;
 	List	   *clauses = root->processed_groupClause;
@@ -561,6 +572,23 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 		}
 	}
 
+#ifdef USE_ASSERT_CHECKING
+	{
+		PathKeyInfo	   *pinfo = linitial_node(PathKeyInfo, infos);
+		ListCell	   *lc;
+
+		/* Test consistency of info structures */
+		for_each_from(lc, infos, 1)
+		{
+			info = lfirst_node(PathKeyInfo, lc);
+
+			Assert(list_length(info->clauses) == list_length(pinfo->clauses));
+			Assert(list_length(info->pathkeys) == list_length(pinfo->pathkeys));
+			Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
+			Assert(list_difference_ptr(info->pathkeys, pinfo->pathkeys) == NIL);
+		}
+	}
+#endif
 	return infos;
 }

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 18 Apr 2024 12:01:13 +0700

> believes that it does.  I suspect there are bugs lurking there, and
1. Analysing the code, processed_groupClause is used in:
- adjust_foreign_grouping_path_cost - to decide, do we need to add cost 
of sort to the foreign grouping.
- just for replacing relids during SJE process.
- create_groupingsets_plan(), preprocess_grouping_sets, 
remove_useless_groupby_columns - we don't apply this feature in the case 
of grouping sets.
- get_number_of_groups - estimation shouldn't depend on the order of 
clauses.
- create_grouping_paths - to analyse hashability of grouping clause
- make_group_input_target, make_partial_grouping_target - doesn't depend 
on the order of clauses
planner.c: add_paths_to_grouping_rel, create_partial_grouping_paths - in 
the case of hash grouping.

So, the only case we can impact current behavior lies in the 
postgres_fdw. But here we don't really know which plan will be chosen 
during planning on foreign node and stay the same behavior is legal for me.
> not doing a great job of that.
Thanks for picking this place. I fixed it.
More interesting here is that we move decisions on the order of group-by 
clauses to the stage, where we already have underlying subtree and 
incoming path keys. In principle, we could return the preprocessing 
routine and arrange GROUP-BY with the ORDER-BY clause as it was before. 
But looking into the code, I found only one reason to do this: 
adjust_group_pathkeys_for_groupagg. Curious about how much profit we get 
here, I think we can discover it later with no hurry. A good outcome 
here will be a test case that can show the importance of arranging 
GROUP-BY and ORDER-BY at an early stage.

-- 
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5ea3705796..861656a192 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1424,7 +1424,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction,
 		}
 		else if (parse->groupClause)
 		{
-			/* Preprocess regular GROUP BY clause, if any */
+			/*
+			 * Make a copy of origin groupClause because we are going to
+			 * remove redundant clauses.
+			 */
 			root->processed_groupClause = list_copy(parse->groupClause);
 			/* Remove any redundant GROUP BY columns */
 			remove_useless_groupby_columns(root);

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 18 Apr 2024 15:54:45 +0700

> underspecified, and fuzzy thinking about data structures tends to lead
I'm not the best in English documentation and naming style. So, feel 
free to check my version.
> it probably wouldn't produce anything as obviously wrong as
I added checkings on the proper order of pathkeys and clauses.
  If you really care about that, we should spend additional time and 
rewrite the code to generate an order of clauses somewhere in the plan 
creation phase. For example, during the create_group_plan call, we could 
use the processed_groupClause list, cycle through subpath->pathkeys, set 
the order, and detect whether the pathkeys list corresponds to the 
group-by or is enough to build a grouping plan.
Anyway, make this part of code more resistant to blunders is another story.

-- 
regards,
Andrei Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index aa80f6486c..9c079270ec 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -461,7 +461,7 @@ group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
 /*
  * pathkeys_are_duplicate
  *		Check if give pathkeys are already contained the list of
- *		PathKeyInfo's.
+ *		GroupByOrdering's.
  */
 static bool
 pathkeys_are_duplicate(List *infos, List *pathkeys)
@@ -470,7 +470,7 @@ pathkeys_are_duplicate(List *infos, List *pathkeys)
 
 	foreach(lc, infos)
 	{
-		PathKeyInfo *info = lfirst_node(PathKeyInfo, lc);
+		GroupByOrdering *info = lfirst_node(GroupByOrdering, lc);
 
 		if (compare_pathkeys(pathkeys, info->pathkeys) == PATHKEYS_EQUAL)
 			return true;
@@ -482,7 +482,7 @@ pathkeys_are_duplicate(List *infos, List *pathkeys)
  * get_useful_group_keys_orderings
  *		Determine which orderings of GROUP BY keys are potentially interesting.
  *
- * Returns a list of PathKeyInfo items, each representing an interesting
+ * Returns a list of GroupByOrdering items, each representing an interesting
  * ordering of GROUP BY keys.  Each item stores pathkeys and clauses in the
  * matching order.
  *
@@ -495,15 +495,15 @@ pathkeys_are_duplicate(List *infos, List *pathkeys)
 List *
 get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 {
-	Query		   *parse = root->parse;
-	List		   *infos = NIL;
-	PathKeyInfo	   *info;
+	Query			   *parse = root->parse;
+	List			   *infos = NIL;
+	GroupByOrdering	   *info;

 	/* always return at least the original pathkeys/clauses */
-	info = makeNode(PathKeyInfo);
+	info = makeNode(GroupByOrdering);
 	info->pathkeys = pathkeys;
 	info->clauses = clauses;
 	infos = lappend(infos, info);
@@ -539,7 +539,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 			(enable_incremental_sort || n == root->num_groupby_pathkeys) &&
 			!pathkeys_are_duplicate(infos, pathkeys))
 		{
-			info = makeNode(PathKeyInfo);
+			info = makeNode(GroupByOrdering);
 			info->pathkeys = pathkeys;
 			info->clauses = clauses;
 
@@ -564,7 +564,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 			(enable_incremental_sort || n == list_length(root->sort_pathkeys)) &&
 			!pathkeys_are_duplicate(infos, pathkeys))
 		{
-			info = makeNode(PathKeyInfo);
+			info = makeNode(GroupByOrdering);
 			info->pathkeys = pathkeys;
 			info->clauses = clauses;
 
@@ -574,18 +574,29 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
 
 #ifdef USE_ASSERT_CHECKING
 	{
-		PathKeyInfo	   *pinfo = linitial_node(PathKeyInfo, infos);
+		GroupByOrdering	   *pinfo = linitial_node(GroupByOrdering, infos);
 		ListCell	   *lc;
 
 		/* Test consistency of info structures */
 		for_each_from(lc, infos, 1)
 		{
-			info = lfirst_node(PathKeyInfo, lc);
+			ListCell *lc1, *lc2;
+
+			info = lfirst_node(GroupByOrdering, lc);
 
 			Assert(list_length(info->clauses) == list_length(pinfo->clauses));
 			Assert(list_length(info->pathkeys) == list_length(pinfo->pathkeys));
 			Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
 			Assert(list_difference_ptr(info->pathkeys, pinfo->pathkeys) == NIL);
+
+			forboth(lc1, info->clauses, lc2, info->pathkeys)
+			{
+				SortGroupClause *sgc = lfirst_node(SortGroupClause, lc1);
+				PathKey *pk = lfirst_node(PathKey, lc2);
+
+				if (pk->pk_eclass->ec_sortref != sgc->tleSortGroupRef)
+					elog(ERROR, "Order of group-by clauses doesn't correspond incoming sort order");
+			}
 		}
 	}
 #endif
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 861656a192..4751a700ab 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6882,7 +6882,7 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 
 			foreach(lc2, pathkey_orderings)
 			{
-				PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
+				GroupByOrdering *info = (GroupByOrdering *) lfirst(lc2);
 
 				/* restore the path (we replace it in the loop) */
 				path = path_save;
@@ -6963,7 +6963,7 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 				/* process all potentially interesting grouping reorderings */
 				foreach(lc2, pathkey_orderings)
 				{
-					PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
+					GroupByOrdering *info = (GroupByOrdering *) lfirst(lc2);
 
 					/* restore the path (we replace it in the loop) */
 					path = path_save;
@@ -7214,7 +7214,7 @@ create_partial_grouping_paths(PlannerInfo *root,
 			/* process all potentially interesting grouping reorderings */
 			foreach(lc2, pathkey_orderings)
 			{
-				PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
+				GroupByOrdering *info = (GroupByOrdering *) lfirst(lc2);
 
 				/* restore the path (we replace it in the loop) */
 				path = path_save;
@@ -7270,7 +7270,7 @@ create_partial_grouping_paths(PlannerInfo *root,
 			/* process all potentially interesting grouping reorderings */
 			foreach(lc2, pathkey_orderings)
 			{
-				PathKeyInfo *info = (PathKeyInfo *) lfirst(lc2);
+				GroupByOrdering *info = (GroupByOrdering *) lfirst(lc2);

 				/* restore the path (we replace it in the loop) */
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 6c71098f2d..b3862500b6 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -427,6 +427,10 @@ struct PlannerInfo
 	 * containing all the query's rows.  Hence, if you want to check whether
 	 * GROUP BY was specified, test for nonempty parse->groupClause, not for
 	 * nonempty processed_groupClause.
+	 * Optimiser chooses specific order of group-by clauses during the upper
+	 * paths generation process, attempting to use different strategies to
+	 * minimize number of sorts or engage incremental sort.
+	 * See get_useful_group_keys_orderings for details.
 	 *
 	 * Currently, when grouping sets are specified we do not attempt to
 	 * optimize the groupClause, so that processed_groupClause will be
@@ -1468,14 +1472,20 @@ typedef struct PathKey
 } PathKey;
 
 /*
- * Combines the information about pathkeys and the associated clauses.
+ * Contains an order of group-by clauses and corresponding list of pathkeys.
+ *
+ * Order of SortGroupClause elements must correspond the order in the head of
+ * PathKey list:
+ * tleSortGroupRef of N-th element in the clauses must be the same as the value
+ * of ec_sortref in N-th pathkey equivalence class.
  */
-typedef struct PathKeyInfo
+typedef struct GroupByOrdering
 {
 	NodeTag		type;
+
 	List	   *pathkeys;
 	List	   *clauses;
-} PathKeyInfo;
+} GroupByOrdering;
 
 /*
  * VolatileFunctionStatus -- allows nodes to cache their
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index d551ada325..33eff1e63a 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -4113,7 +4113,7 @@ manifest_writer
 rfile
 ws_options
 ws_file_info
-PathKeyInfo
+GroupByOrdering
 TidStore
 TidStoreIter
 TidStoreIterResult

---

From: Alexander Korotkov <[email-masked]>
Date: Thu, 18 Apr 2024 13:57:41 +0300

Hi, Andrei!

> Anyway, make this part of code more resistant to blunders is another story.

Thank you for the fixes you've proposed.  I didn't look much into
details yet, but I think the main concern Tom expressed in [1] is
whether the feature is reasonable at all.  I think at this stage the
most important thing is to come up with convincing examples showing
how huge performance benefits it could cause.  I will return to this
later today and will try to provide some convincing examples.

Links
1. https://www.postgresql.org/message-id/266850.1712879082%40sss.pgh.pa.us

------
Regards,
Alexander Korotkov

---

From: jian he <[email-masked]>
Date: Fri, 19 Apr 2024 18:44:44 +0800

> later today and will try to provide some convincing examples.

hi.
I found a case where it improved performance.

+-- GROUP BY optimization by reorder columns
+CREATE TABLE btg AS SELECT
+ i % 100 AS x,
+ i % 100 AS y,
+ 'abc' || i % 10 AS z,
+ i AS w
+FROM generate_series(1,10000) AS i;
+CREATE INDEX abc ON btg(x,y);
+ANALYZE btg;
+
I change
+FROM generate_series(1,10000) AS i;
to
+ FROM generate_series(1, 1e6) AS i;

Then I found out about these 2 queries performance improved a lot.
A: explain(analyze) SELECT count(*) FROM btg GROUP BY w, x, y, z ORDER
BY y, x \watch i=0.1 c=10
B: explain(analyze) SELECT count(*) FROM btg GROUP BY w, x, z, y ORDER
BY y, x, z, w \watch i=0.1 c=10

set (enable_seqscan,enable_hashagg) from on to off:
queryA execution time from 1533.013 ms to 533.430 ms
queryB execution time from 1996.817 ms to 497.020 ms

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 22 Apr 2024 10:51:02 +0700

> seeing right now, I think maybe we ought to give up on it.
Let me show current cases where users have a profit with this tiny 
improvement (see queries and execution results in query.sql):
1. 'Not optimised query text' — when we didn't consider group-by 
ordering during database development.
2. 'Accidental pathkeys' - we didn't see any explicit orderings, but 
accidentally, the planner used merge join that caused some orderings and 
we can utilise it.
3. 'Uncertain scan path' — We have options regarding which index to use, 
and because of that, we can't predict the optimal group-by ordering 
before the start of query planning.
4. 'HashAgg V/S GroupAgg' — sometimes, the GroupAgg strategy outperforms 
HashAgg just because we don't need any ordering procedure at all.

And the last thing here — this code introduces the basics needed to add 
more sophisticated strategies, like ordering according to uniqueness or 
preferring to set constant-width columns first in grouping.

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: jian he <[email-masked]>
Date: Mon, 22 Apr 2024 16:56:19 +0800

> > later today and will try to provide some convincing examples.

hi.
previously preprocess_groupclause will not process cases
where no ORDER BY clause is specified.
commit 0452b461b will reorder the GROUP BY element even though no
ORDER BY clause is specified
, if there are associated indexes on it.
(hope I understand it correctly).

for example (when enable_hashagg is false)
explain(verbose) select count(*) FROM btg GROUP BY y,x;
in pg16 will not reorder, it will be as is: `GROUP BY y,x`

after commit 0452b461b, it will reorder to `GROUP BY x,y`.
because there is an index `btree (x, y)` (only one) associated with it.
if you drop the index `btree (x, y)` , it will be `GROUP BY y,x` as pg16.

This reordering GROUP BY element when no ORDER BY clause is not specified
is performant useful when the work_mem is small.
I've attached some tests comparing master with REL_16_STABLE to
demonstrate that.
all the tests attached are under the condition:
work_mem='64kB', buildtype=release, max_parallel_workers_per_gather=0.

one example:
CREATE TABLE btg5 AS
SELECT i::numeric % 10 AS x, i % 10 AS y, 'abc' || i % 10 AS z, i % 100000 AS w
FROM generate_series(1, 1e6) AS i;
CREATE INDEX btg5_x_y_idx ON btg5(x, y);

explain(analyze) SELECT count(*) FROM btg5 GROUP BY z, y, w, x;
in pg17,  the execution time is: 746.574 ms
in pg16,  the execution time is: 1693.483 ms

if I reorder it manually as:
`explain(analyze) SELECT count(*) FROM btg5 GROUP BY x, y, w, z;`
then in pg16, the execution time is 630.394 ms

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 23 Apr 2024 01:19:59 +0300

Hi!

> later today and will try to provide some convincing examples.

I took a fresh look at 0452b461b, and have the following thoughts:
1) Previously, preprocess_groupclause() tries to reorder GROUP BY
clauses to match the required ORDER BY order.  It only reorders if
GROUP BY pathkeys are the prefix of ORDER BY pathkeys or vice versa.
So, both of them need to be satisfied by one ordering.  0452b461b also
tries to match GROUP BY clauses to ORDER BY clauses, but takes into
account an incremental sort.  Actually, instead of removing
preprocess_groupclause(), we could just teach it to take incremental
sort into account.
2) The get_useful_group_keys_orderings() function takes into account 3
orderings of pathkeys and clauses: original order as written in GROUP
BY, matching ORDER BY clauses as much as possible, and matching the
input path as much as possible.  Given that even before 0452b461b,
preprocess_groupclause() could change the original order of GROUP BY
clauses, so we don't need to distinguish the first two.  We could just
consider output of new preprocess_groupclause() taking into account an
incremental sort and the ordering matching the input path as much as
possible.  This seems like significant simplification.

Let me also describe my thoughts about the justification of the
feature itself.  As Tom pointed upthread, Sort + Grouping is generally
unlikely faster than Hash Aggregate.  The main point of this feature
is being able to match the order of GROUP BY clauses to the order of
the input path.  That input path could be Index Scan or Subquery.
Let's concentrate on Index Scan.  Index Scan can give us the required
order, so we can do grouping without Sort or with significantly
cheaper Incremental Sort.  That could be much faster than Hash
Aggregate.  But if we scan the full table (or its significant
fraction), Index Scan is typically much more expensive than Sequential
Scan because of random page access.  However, there are cases when
Index Scan could be cheaper.
1) If the heap row is wide and the index contains all the required
columns, Index Only Scan can be cheaper than Sequential Scan because
of lesser volume.
2) If the query predicate is selective enough and matches the index,
Index Scan might be significantly cheaper.  One may say that if the
query predicate is selective enough then there are not that many
matching rows, so aggregating them either way isn't a big deal anyway.
However, given that data volumes are growing tremendously, it's not
hard to imagine that the index selected a small fraction of table
rows, but they are still enough to be costly for aggregating.
Therefore, I think there are significant cases where matching GROUP BY
clauses to the order of the input path could give a substantial
improvement over Hash Aggregate.

While there are some particular use-cases by Jian He, I hope that
above could give some rationale.

------
Regards,
Alexander Korotkov

---

From: jian he <[email-masked]>
Date: Wed, 24 Apr 2024 14:25:22 +0800

hi.
I found an interesting case.

CREATE TABLE t1 AS
  SELECT (i % 10)::numeric AS x,(i % 10)::int8 AS y,'abc' || i % 10 AS
z, i::int4 AS w
  FROM generate_series(1, 100) AS i;
CREATE INDEX t1_x_y_idx ON t1 (x, y);
ANALYZE t1;
SET enable_hashagg = off;
SET enable_seqscan = off;

EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,z,y,w;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,w,y,z;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,z,w,y;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,w,z,y;
the above part will use:
  ->  Incremental Sort
         Sort Key: x, $, $, $
         Presorted Key: x
         ->  Index Scan using t1_x_y_idx on t1

EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY z,y,w,x;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY w,y,z,x;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY y,z,x,w;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY y,w,x,z;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY y,x,z,w;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY y,x,w,z;

these will use:
  ->  Incremental Sort
         Sort Key: x, y, $, $
         Presorted Key: x, y
         ->  Index Scan using t1_x_y_idx on t1

I guess this is fine, but not optimal?

---

From: jian he <[email-masked]>
Date: Wed, 24 Apr 2024 19:17:34 +0800

hi
one more question (maybe a dumb one....)

drop table if exists t1;
CREATE TABLE t1 AS

EXPLAIN (COSTS OFF, verbose) SELECT count(*) FROM t1 GROUP BY z,x,y,w
order by w;

                      QUERY PLAN
------------------------------------------------------
 GroupAggregate
   Output: count(*), w, z, x, y
   Group Key: t1.w, t1.x, t1.y, t1.z
   ->  Sort
         Output: w, z, x, y
         Sort Key: t1.w, t1.x, t1.y, t1.z
         ->  Index Scan using t1_x_y_idx on public.t1
               Output: w, z, x, y
(8 rows)

if you do
` Sort Key: t1.w, t1.x, t1.y, t1.z`

then the output is supposed to be:

Output: w, x, y, z

?

---

From: jian he <[email-masked]>
Date: Mon, 29 Apr 2024 10:50:00 +0800

>          ->  Index Scan using t1_x_y_idx on t1

We can make these cases also `Presorted Key: x, y`.

in
`if (path->pathkeys && !pathkeys_contained_in(path->pathkeys,
root->group_pathkeys))` branch
we can simple do
-                       infos = lappend(infos, info);
+                       infos = lcons(info, infos);

similar to what we did at plancat.c (search lcons).

get_useful_group_keys_orderings returns a  list of PathKeyInfo,
then the caller function just iterates each element.
so for the caller, order of the returned list element from
get_useful_group_keys_orderings
does not matter.

for path Incremental Sort:
function make_ordered_path will return the same cost for different
numbers of  presorted keys.

for example:
EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,z,y,w;
make_ordered_path cost is same for:
`info->pathkeys: x,y,z,w`
`info->pathkeys:x,z,y,w`

if we arrange `info->pathkeys: x,y,z,w` before `info->pathkeys:x,z,y,w`
in get_useful_group_keys_orderings.
then with the same cost, we will choose the first one
(`info->pathkeys: x,y,z,w`),
if we use IncrementalSort, then we use `Presorted Key: x, y`.

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 16 May 2024 14:47:01 +0700

> I guess this is fine, but not optimal?
It looks like a bug right now - in current implementation we don't 
differentiate different orders. So:
1. Applying all the patches from the thread which I proposed as an 
answer to T.Lane last rebuke - does behavior still the same?.
2. Could you try to find the reason?

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: jian he <[email-masked]>
Date: Mon, 20 May 2024 16:54:56 +0800

> answer to T.Lane last rebuke - does behavior still the same?.

I've applied these 4 patches in  this thread.
final_improvements.patch
minor_comment.patch
get_useful_group_keys_orderings.patch
group_by_asymmetry.diff

The behavior is still the same as the master.
meaning that below quoted queries are still using "Presorted Key: x".

> 2. Could you try to find the reason?
the following are my understanding, it may be wrong...

function get_useful_group_keys_orderings, may generate alternative
pathkeys and group clauses.
for different PathKeyInfo
sub functions within add_paths_to_grouping_rel:
make_ordered_path, create_agg_path will yield the same cost.
function add_path (within add_paths_to_grouping_rel) will add these
paths (different PathKeyInfos) in a *sequential* order.

then later in the function set_cheapest.
`foreach(p, parent_rel->pathlist)`  will iterate these different paths
in a sequential order.
so in set_cheapest if 2 path costs are the same, then the first path
residing in parent_rel->pathlist wins.

fo a concrete example:
CREATE TABLE t1 AS
SELECT (i % 10)::numeric AS x,(i % 10)::int8 AS y,'abc' || i % 10 AS
z, i::float4 AS w FROM generate_series(1, 100) AS i;
CREATE INDEX t1_x_y_idx ON t1 (x, y);
ANALYZE t1;
SET enable_hashagg = off;
SET enable_seqscan = off;
EXPLAIN (COSTS OFF, verbose) SELECT count(*) FROM t1 GROUP BY x,z,y,w;

add_paths_to_grouping_rel will do the following in a sequential order.
A. generate and add original PathKeyInfo(groupby x,z,y,w)
B. generate and add alternative PathKeyInfo(groupby x,y,z,w). (because
of the index path)
C. can_hash is true, generate a HashAgg Path (because of
enable_hashagg is set to off, so this path the cost is very high)

As mentioned previously,
both A and B can use Incremental Sort, set_cheapest will choose the A
instead of B,
because A step generated path **first** satisfies increment sort.

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 21 May 2024 16:01:19 +0700

> because A step generated path **first** satisfies increment sort.
Yeah, I agree with your analysis.
Looking into the cost_incremental_sort, I see that we have ten 
group_tuples. This value doesn't depend on how many presorted keys (1 or 
2) we use. This is caused by default estimation.
Given the current circumstances, it seems unlikely that we can make any 
significant changes without introducing a new sort cost model that 
accounts for the number of sorted columns.

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: jian he <[email-masked]>
Date: Fri, 24 May 2024 08:00:00 +0800

> the following are my understanding, it may be wrong...

I think
my previous thread only explained that two paths have the same cost,
the planner chooses the one that was first added into the pathlist.

but didn't explain why Incremental Sort path, presorted by one key and
presorted by two keys
yield the same cost.
--------------------------------------------
if (rel->tuples > 0)
{
/*
* Clamp to size of rel, or size of rel / 10 if multiple Vars. The
* fudge factor is because the Vars are probably correlated but we
* don't know by how much.  We should never clamp to less than the
* largest ndistinct value for any of the Vars, though, since
* there will surely be at least that many groups.
*/
double clamp = rel->tuples;

if (relvarcount > 1)
{
clamp *= 0.1;
if (clamp < relmaxndistinct)
{
clamp = relmaxndistinct;
/* for sanity in case some ndistinct is too large: */
if (clamp > rel->tuples)
clamp = rel->tuples;
}
}
if (reldistinct > clamp)
reldistinct = clamp;
...
}

i think,
the above code[0] snippet within function estimate_num_groups
makes Incremental Sort Path not pickup the optimal presorted keys.

see original problem thread: [1]
----------------------------------------------------------------------------------------
CREATE TABLE t1 AS
SELECT (i % 10)::numeric AS x,(i % 10)::int8 AS y,'abc' || i % 10 AS
z, i::int4 AS w
FROM generate_series(1, 100) AS i;
CREATE INDEX t1_x_y_idx ON t1 (x, y);
ANALYZE t1;
SET enable_hashagg = off;
SET enable_seqscan = off;

EXPLAIN (COSTS OFF) SELECT count(*) FROM t1 GROUP BY x,z,y,w;
will generate 2 Incremental Sort path, one: "Presorted Key: x",
another one: "Presorted Key: x,y".
The first Incremental Sort path is added first.
The function estimate_num_groups returned value (input_groups) is the
main key to
calculate the cost of Incremental Sort path!

But here, the estimate_num_groups function returned the same
value: 10 for
"Presorted Key: x" and "Presorted Key: x,y".
then later cost_incremental_sort returns the same cost for "Presorted
Key: x" and "Presorted Key: x,y".

(line refers to src/backend/utils/adt/selfuncs line number).
why "Presorted Key: x,y" return 10 in estimate_num_groups:
line 3667 assign clamp to 100.0, because rel->tuples is 100.
line 3671 clamp *= 0.1; make clamp because 10.
line 3680, 3681  `if (reldistinct > clamp) branch` make reldistinct
from 100 to 10.
line 3733 make  `numdistinct *= reldistinct;` makes numdistinct because 10.

If I change the total number of rows in a relation, or change the
distinct number of y values
then the planner will use "Incremental Sort Presorted Key: x,y".
for example:

    CREATE TABLE t10 AS
    SELECT (i % 10)::numeric AS x,(i % 11)::int8 AS y,'abc' || i % 10
AS z, i::float4 AS w FROM generate_series(1, 1E2) AS i;
    CREATE INDEX t10_x_y_idx ON t10 (x, y);
    ANALYZE t10;

The above setup will make the following query using "Incremental Sort
Presorted Key: x,y".
EXPLAIN (COSTS OFF) SELECT count(*) FROM t10 GROUP BY x,z,y,w;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t10 GROUP BY x,w,y,z;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t10 GROUP BY x,z,w,y;
EXPLAIN (COSTS OFF) SELECT count(*) FROM t10 GROUP BY x,w,z,y;

summary:
* the regression test setup at [2] can make some cases not pickup the
best optimal
Incremental Sort path.

we use this test in src/test/regress/sql/aggregates.sql
-- Engage incremental sort
EXPLAIN (COSTS OFF)
SELECT count(*) FROM btg GROUP BY z, y, w, x;

but if we use:
EXPLAIN (COSTS OFF)
SELECT count(*) FROM btg GROUP BY x, z, w, y;
then the plan is not the best.

* The regression test setup makes estimate_num_groups code logic
return the same value.
therefore make Incremental Sort presort by one key, two keys yield the
same cost.
the cost_incremental_sort will return the same cost.

* https://git.postgresql.org/cgit/postgresql.git/tree/src/test/regress/sql/aggregates.sql#n1194
maybe we can change:

  i % 10 AS x,
  i % 10 AS y,

to

CREATE TABLE btg AS SELECT
  i % 10 AS x,
  i % 10 AS y,
  'abc' || i % 10 AS z,
  i AS w
FROM generate_series(1, 1000) AS i;

[0] https://git.postgresql.org/cgit/postgresql.git/tree/src/backend/utils/adt/selfuncs.c#n3669
[1] https://www.postgresql.org/message-id/CACJufxGt99nZ%2Bnir%2BaB6pFQ%3DK8oNiHAQ3OELqSbGMqNxok8nxA%40mail.gmail.com
[2] https://git.postgresql.org/cgit/postgresql.git/tree/src/test/regress/sql/aggregates.sql#n1194

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 27 May 2024 15:41:25 +0300

Hi!

> above could give some rationale.

I've assembled patches in this thread into one patchset.
0001 The patch fixing asymmetry in setting EquivalenceClass.ec_sortref
by Andrei [1].  I've revised comments and wrote the commit message.
0002 The patch for handling duplicates of SortGroupClause.  I didn't
get the sense of Andrei implementation.  It seems to care about
duplicate pointers in group clauses list.  But the question is the
equal SortGroupClause's comprising different pointers.  I think we
should group duplicate SortGroupClause's together as
preprocess_groupclause() used to do.  Reimplemented patch to do so.
0003 Rename PathKeyInfo to GroupByOrdering by Andres [3].  I only
revised comments and wrote the commit message.
0004 Turn back preprocess_groupclause() for the reason I described upthread [4].

Any thoughts?

Links.
1. https://www.postgresql.org/message-id/17037754-f187-4138-8285-0e2bfebd0dea%40postgrespro.ru
2. https://www.postgresql.org/message-id/a663f0f6-cbf6-49aa-af2e-234dc6768a07%40postgrespro.ru
3. https://www.postgresql.org/message-id/db0fc3a4-966c-4cec-a136-94024d39212d%40postgrespro.ru
4. https://www.postgresql.org/message-id/CAPpHfdvyWLMGwvxaf%3D7KAp-z-4mxbSH8ti2f6mNOQv5metZFzg%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 29 May 2024 15:08:26 +0700

> 0004 Turn back preprocess_groupclause() for the reason I described upthread [4].
About 0001:
Having overviewed it, I don't see any issues (but I'm the author), 
except grammatical ones - but I'm not a native to judge it.
Also, the sentence 'turning GROUP BY clauses  into pathkeys' is unclear 
to me. It may be better to write something like:  'building pathkeys by 
the list of grouping clauses'.

0002:
The part under USE_ASSERT_CHECKING looks good to me. But the code in 
group_keys_reorder_by_pathkeys looks suspicious: of course, we do some 
doubtful work without any possible way to reproduce, but if we envision 
some duplicated elements in the group_clauses, we should avoid usage of 
the list_concat_unique_ptr. What's more, why do you not exit from 
foreach_ptr immediately after SortGroupClause has been found? I think 
the new_group_clauses should be consistent with the new_group_pathkeys.

0003:
Looks good

0004:
I was also thinking about reintroducing the preprocess_groupclause 
because with the re-arrangement of GROUP-BY clauses according to 
incoming pathkeys, it doesn't make sense to have a user-defined order—at 
least while cost_sort doesn't differ costs for alternative column orderings.
So, I'm okay with the code. But why don't you use the same approach with 
foreach_ptr as before?

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 29 May 2024 15:53:39 +0300

Hi, Andrei!

Thank you for your feedback.

> the list of grouping clauses'.

OK, thank you.  I'll run once again for the grammar issues.

> the list_concat_unique_ptr.

As I understand Tom, there is a risk that clauses list may contain
multiple instances of equivalent SortGroupClause, not duplicate
pointers.

> What's more, why do you not exit from

I wanted this to be consistent with preprocess_groupclause(), where
duplicate SortGroupClause'es are grouped together.  Otherwise, we
could just delete redundant SortGroupClause'es.

> So, I'm okay with the code. But why don't you use the same approach with

I restored the function as it was before 0452b461bc with minimal edits
to support the incremental sort.  I think it would be more valuable to
keep the difference with pg16 code small rather than refactor to
simplify existing code.

------
Regards,
Alexander Korotkov

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 30 May 2024 11:22:46 +0700

> multiple instances of equivalent SortGroupClause, not duplicate
Maybe. I just implemented the worst-case scenario with the intention of 
maximum safety. So, it's up to you.
> could just delete redundant SortGroupClause'es.
Hm, preprocess_groupclause is called before the standard_qp_callback 
forms the 'canonical form' of group_pathkeys and such behaviour needed. 
But the code that chooses the reordering strategy uses already processed 
grouping clauses, where we don't have duplicates in the first 
num_groupby_pathkeys elements, do we?
> keep the difference with pg16 code small rather than refactor to
Got it

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 31 May 2024 03:12:28 +0300

Hi!

> > OK, thank you.  I'll run once again for the grammar issues.

I've revised some grammar including the sentence you've proposed.

> num_groupby_pathkeys elements, do we?

Yep, it seems that we work with group clauses which were processed by
standard_qp_callback().  In turn standard_qp_callback() called
make_pathkeys_for_sortclauses_extended() with remove_redundant ==
true.  So, there shouldn't be duplicates.  And it's unclear what
should we be protected from.

I leaved 0002 with just asserts.  And extracted questionable changes into 0005.

------
Regards,
Alexander Korotkov
Supabase

---

From: jian he <[email-masked]>
Date: Sun, 2 Jun 2024 15:55:44 +0800

> I've revised some grammar including the sentence you've proposed.

-static List *groupclause_apply_groupingset(PlannerInfo *root, List *force);
+static List *preprocess_groupclause(PlannerInfo *root, List *force);

changing preprocess_groupclause the second argument
from "force" to "gset" would be more intuitive, I think.

`elog(ERROR, "Order of group-by clauses doesn't correspond incoming
sort order");`

I think this error message makes people wonder what "incoming sort order" is.
BTW, "correspond", generally people use  "correspond to".

I did some minor cosmetic changes, mainly changing foreach to foreach_node.
Please check the attachment.
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6a1fb8e..801d9f6d 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -2852,15 +2852,13 @@ preprocess_groupclause(PlannerInfo *root, List *force)
 {
 	Query	   *parse = root->parse;
 	List	   *new_groupclause = NIL;
-	ListCell   *sl;
-	ListCell   *gl;
+	ListCell	*gl;
 
 	/* For grouping sets, we need to force the ordering */
-	if (force)
+	if (force != NIL)
 	{
-		foreach(sl, force)
+		foreach_int(ref, force)
 		{
-			Index		ref = lfirst_int(sl);
 			SortGroupClause *cl = get_sortgroupref_clause(ref, parse->groupClause);
 
 			new_groupclause = lappend(new_groupclause, cl);
@@ -2879,10 +2877,8 @@ preprocess_groupclause(PlannerInfo *root, List *force)
 	 *
 	 * This code assumes that the sortClause contains no duplicate items.
 	 */
-	foreach(sl, parse->sortClause)
+	foreach_node(SortGroupClause, sc, parse->sortClause)
 	{
-		SortGroupClause *sc = lfirst_node(SortGroupClause, sl);
-
 		foreach(gl, parse->groupClause)
 		{
 			SortGroupClause *gc = lfirst_node(SortGroupClause, gl);
@@ -2908,10 +2904,8 @@ preprocess_groupclause(PlannerInfo *root, List *force)
 	 * implemented using incremental sort.  Also, give up if there are any
 	 * non-sortable GROUP BY items, since then there's no hope anyway.
 	 */
-	foreach(gl, parse->groupClause)
+	foreach_node(SortGroupClause,gc, parse->groupClause)
 	{
-		SortGroupClause *gc = lfirst_node(SortGroupClause, gl);
-
 		if (list_member_ptr(new_groupclause, gc))
 			continue;			/* it matched an ORDER BY item */
 		if (!OidIsValid(gc->sortop))	/* give up, GROUP BY can't be sorted */
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index af8de421..2ba297c1 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -426,7 +426,7 @@ struct PlannerInfo
 	 * items to be proven redundant, implying that there is only one group
 	 * containing all the query's rows.  Hence, if you want to check whether
 	 * GROUP BY was specified, test for nonempty parse->groupClause, not for
-	 * nonempty processed_groupClause.  Optimiser chooses specific order of
+	 * nonempty processed_groupClause.  Optimizer chooses specific order of
 	 * group-by clauses during the upper paths generation process, attempting
 	 * to use different strategies to minimize number of sorts or engage
 	 * incremental sort.  See preprocess_groupclause() and

---

From: Alexander Korotkov <[email-masked]>
Date: Sun, 2 Jun 2024 16:18:11 +0300

Hi!

> from "force" to "gset" would be more intuitive, I think.

Probably, but my intention is to restore preprocess_groupclause() as
it was before 0452b461bc with minimal edits to support incremental
sort.  I'd rather avoid refactoring if this area for now.

> BTW, "correspond", generally people use  "correspond to".

Thank you.  On the second thought, I think it would be better to turn
this into an assertion like the checks before.

> Please check the attachment.

I would avoid refactoring of preprocess_groupclause() for the reason
described above.  But I picked the grammar fix for PlannerInfo's
comment.

------
Regards,
Alexander Korotkov
Supabase

---

From: Pavel Borisov <[email-masked]>
Date: Mon, 3 Jun 2024 19:54:53 +0400

Hi, Alexander!

> described above.  But I picked the grammar fix for PlannerInfo's

Thank you for working on this patchset.

0001: Patch looks right

Comments:

Covert -> Convert
sets the uninitialized value of ec_sortref of the pathkey's
EquivalenceClass -> sets the value of the pathkey's EquivalenceClass unless
it's already initialized
wasn't set yet -> hasn't been set yet

0002: additional assert checking only. Looks right.

0003: pure renaming, looks good.

0004: Restores pre 0452b461bc state to preprocess_groupclause with removed
partial_match fallback. Looks right. I haven't checked the comments
provided they are restored from pre 0452b461bc state.

0005: Looks right.

Regards,
Pavel Borisov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 4 Jun 2024 01:47:43 +0300

On Mon, Jun 3, 2024 at 6:55 PM Pavel Borisov <[email-masked]> wrote:
> On Sun, 2 Jun 2024 at 17:18, Alexander Korotkov <[email-masked]> wrote:
>>
>> Hi!
>>
> sets the uninitialized value of ec_sortref of the pathkey's EquivalenceClass -> sets the value of the pathkey's EquivalenceClass unless it's already initialized
> 0004: Restores pre 0452b461bc state to preprocess_groupclause with removed partial_match fallback. Looks right. I haven't checked the comments provided they are restored from pre 0452b461bc state.
>
> 0005: Looks right.

Thank you.  Revised according to your comments.  I think 0001-0004
comprising a good refactoring addressing concerns from Tom [1].
0001 Removes from get_eclass_for_sort_expr() unnatural responsibility
of setting EquivalenceClass.ec_sortref.  Instead this field is set in
make_pathkeys_for_sortclauses_extended() while processing of group
clauses.
0002 Provides additional asserts.  That should helping to defend
against lurking bugs.
0003 Fixes unsuitable name of data structure.
0004 Restores pre 0452b461bc state to preprocess_groupclause() and
lowers the number of paths to consider.
It would be good to explicitly hear Tom about this.  But I'm quite
sure these patches makes situation better not worse.  I'm going to
push them if no objections.

I'm putting 0005 aside.  It's unclear why and how there could be
duplicate SortGroupClauses at that stage.  Also, it's unclear why
existing code handles them bad.  So, this should wait a comment from
Tom.

Links.

------
Regards,
Alexander Korotkov
Supabase