Subject: Add proper planner support for ORDER BY / DISTINCT aggregates

From: David Rowley <[email-masked]>
Date: Sun, 13 Jun 2021 03:07:18 +1200

A few years ago I wrote a patch to implement the missing aggregate
combine functions for array_agg and string_agg [1].  In the end, the
patch was rejected due to some concern [2] that if we allow these
aggregates to run in parallel then it might mess up the order in which
values are being aggregated by some unsuspecting user who didn't
include an ORDER BY clause in the aggregate.   It was mentioned at the
time that due to nodeAgg.c performing so terribly with ORDER BY
aggregates that we couldn't possibly ask users who were upset by this
change to include an ORDER BY in their aggregate functions.

I'd still quite like to finish off the remaining aggregate functions
that still don't have a combine function, so to get that going again
I've written some code that gets the query planner onboard with
picking a plan that allows nodeAgg.c to skip doing any internal sorts
when the input results are already sorted according to what's required
by the aggregate function.

Of course, the query could have many aggregates all with differing
ORDER BY clauses. Since we reuse the same input for each, it might not
be possible to feed each aggregate with suitably sorted input.   When
the input is not sorted, nodeAgg.c still must perform the sort as it
does today.  So unfortunately we can't remove the nodeAgg.c code for
that.

The best I could come up with is just picking a sort order that suits
the first ORDER BY aggregate, then spin through the remaining ones to
see if there's any with a more strict order requirement that we can
use to suit that one and the first one. The planner does something
similar for window functions already, although it's not quite as
comprehensive to look beyond the first window for windows with a more
strict sort requirement.

This allows us to give presorted input to both aggregates in the following case:

SELECT agg(a ORDER BY a),agg2(a ORDER BY a,b) ...

but just the first agg in this one:

SELECT agg(a ORDER BY a),agg2(a ORDER BY c) ...

In order to make DISTINCT work, I had to add a new expression
evaluation operator to allow filtering if the current value is the
same as the last value.  The current unpatched code implements
distinct when reading back the sorted tuplestore data.  Since I don't
have a tuplestore with the pre-sorted version, I needed to cache the
last Datum, or last tuple somewhere.  I ended up putting that in the
AggStatePerTransData struct. I'm not quite sure if I like that, but I
don't really see where else it could go.

When testing the performance of all this I found that when a suitable
index exists to provide pre-sorted input for the aggregation that the
performance does improve. Unfortunately, it looks like things get more
complex when no index exists.  In this case, since we're setting
pathkeys to tell the planner we need a plan that provides pre-sorted
input to the aggregates, the planner will add a sort below the
aggregate node.  I initially didn't see any problem with that as it
just moves the sort to a Sort node rather than having it done
implicitly inside nodeAgg.c.  The problem is, it just does not perform
as well.  I guess this is because when the sort is done inside
nodeAgg.c that the transition function is called in a tight loop while
reading records back from the tuplestore.  In the patched version,
there's an additional node transition in between nodeAgg and nodeSort
and that causes slower performance.  For now, I'm not quite sure what
to do about that.  We set the plan pathkeys well before we could
possibly decide if asking for pre-sorted input for the aggregates
would be a good idea or not.

Please find attached my WIP patch.  It's WIP due to what I mentioned
in the above paragraph and also because I've not bothered to add JIT
support for the new expression evaluation steps.

I'll add this to the July commitfest.

David

[1] https://www.postgresql.org/message-id/CAKJS1f9sx_6GTcvd6TMuZnNtCh0VhBzhX6FZqw17TgVFH-ga_A%40mail.gmail.com
[2] https://www.postgresql.org/message-id/flat/6538.1522096067%40sss.pgh.pa.us#c228ed67026faa15209c76dada035da4

---

From: Ronan Dunklau <[email-masked]>
Date: Fri, 02 Jul 2021 09:53:52 +0200

> SELECT agg(a ORDER BY a),agg2(a ORDER BY c) ...

I don't know if it's acceptable, but in the case where you add both an 
aggregate with an ORDER BY clause, and another aggregate without the clause, 
the output for the unordered one will change and use the same ordering, maybe 
suprising the unsuspecting user. Would that be acceptable ?

> would be a good idea or not.

I was curious about the performance implication of that additional transition, 
and could not reproduce a signifcant difference. I may be doing something 
wrong: how did you highlight it ?

Regards,

--
Ronan Dunklau

---

From: David Rowley <[email-masked]>
Date: Fri, 2 Jul 2021 20:39:44 +1200

> suprising the unsuspecting user. Would that be acceptable ?

That's a good question. There was an argument in [1] that mentions
that there might be a group of people who rely on aggregation being
done in a certain order where they're not specifying an ORDER BY
clause in the aggregate.  If that group of people exists, then it's
possible they might be upset in the scenario that you describe.

I also think that it's going to be pretty hard to make significant
gains in this area if we are too scared to make changes to undefined
behaviour.  You wouldn't have to look too hard in the pgsql-general
mailing list to find someone complaining that their query output is in
the wrong order on some query that does not have an ORDER BY. We
pretty much always tell those people that the order is undefined
without an ORDER BY. I'm not too sure why Tom in [1] classes the ORDER
BY aggregate people any differently. We'll be stuck forever here and
in many other areas if we're too scared to change the order of
aggregation. You could argue that something like parallelism has
changed that for people already. I think the multi-batch Hash
Aggregate code could also change this.

> wrong: how did you highlight it ?

It was pretty basic. I just created a table with two columns and no
index and did something like SELECT a,SUM(b ORDER BY b) from ab GROUP
BY 1;  the new code will include a Sort due to lack of any index and
the old code would have done a sort inside nodeAgg.c. I imagine that
the overhead comes from the fact that in the patched version nodeAgg.c
must ask its subnode (nodeSort.c) for the next tuple each time,
whereas unpatched nodeAgg.c already has all the tuples in a tuplestore
and can fetch them very quickly in a tight loop.

David

[1] https://www.postgresql.org/message-id/6538.1522096067%40sss.pgh.pa.us

---

From: Gavin Flower <[email-masked]>
Date: Sat, 3 Jul 2021 08:37:40 +1200

> possible they might be upset in the scenario that you describe.

[...]

I've always worked on the assumption that if I do not specify an ORDER 
BY clause then the rdbms is expected to present rows in the order most 
efficient for it to do so. If pg orders rows when not requested then 
this could add extra elapsed time to the query, which might be 
significant for large queries.

I don't know of any rdbms that guarantees the order of returned rows 
when an ORDER BY clause is not used.

So I think that pg has no obligation to protect the sensibilities of 
naive users in this case, especially at the expense of users that want 
queries to complete as quickly as possible.  IMHO

Cheers,
Gavin

---

From: Tom Lane <[email-masked]>
Date: Fri, 02 Jul 2021 16:51:51 -0400

> queries to complete as quickly as possible.  IMHO

I agree.  We've broken such expectations in the past and I don't
have much hesitation about breaking them again.

			regards, tom lane

---

From: Ronan Dunklau <[email-masked]>
Date: Mon, 05 Jul 2021 08:38:28 +0200

Le vendredi 2 juillet 2021, 10:39:44 CEST David Rowley a écrit :
> > aggregate with an ORDER BY clause, and another aggregate without the
> > clause, the output for the unordered one will change and use the same
> > ordering, maybe suprising the unsuspecting user. Would that be acceptable
> > ?
> 

I would agree with that.

> 
> > I was curious about the performance implication of that additional
> > transition, and could not reproduce a signifcant difference. I may be
> > doing something wrong: how did you highlight it ?
> 

Ok, I reproduced that case, just not using a group by: by adding the group by 
a sort node is added in both cases (master and your patch), except that with 
your patch we sort on both keys and that doesn't really incur a performance 
penalty. 

I think the overhead occurs because in the ExecAgg case, we use the 
tuplesort_*_datum API as an optimization when we have a single column as an 
input, which the ExecSort code doesn't. Maybe it would be worth it to try to 
use that API in sort nodes too, when it can be done. 

-- 
Ronan Dunklau

---

From: Ronan Dunklau <[email-masked]>
Date: Mon, 05 Jul 2021 14:07:05 +0200

> Ok, I reproduced that case, just not using a group by: by adding the group
> by a sort node is added in both cases (master and your patch), except that
> with your patch we sort on both keys and that doesn't really incur a
> performance penalty.
> 

Please find attached a POC patch to do just that.

The switch to the single-datum tuplesort is done when there is only one 
attribute, it is byval (to avoid having to deal with copy of the references 
everywhere) and we are not in bound mode (to also avoid having to move things 
around).

A naive run on make check pass on this, but I may have overlooked things.

Should I add this separately to the commitfest ?

For the record, the times I got on my laptop, on master VS david's patch VS 
both. Values are an average of 100 runs, as reported by pgbench --no-vacuum -f 
<file.sql> -t 100. There is a good amount of noise, but the simple "select one 
ordered column case" seems worth the optimization.

Only shared_buffers and work_mem have been set to 2GB each.

Setup 1: single table, 1 000 000 tuples, no index
CREATE TABLE tbench (
  a int,
  b int
);

INSERT INTO tbench (a, b) SELECT a, b FROM generate_series(1, 100) a, 
generate_series(1, 10000) b;

Test 1: Single-column ordered select (order by b since the table is already 
sorted by a)
select b from tbench order by b;

master: 303.661ms
with mine: 148.571ms

Test 2: Ordered sum (using b so that the input is not presorted)
select sum(b order by b) from tbench;

master: 112.379ms
with david's patch: 144.469ms
with david's patch + mine: 97ms

Test 3: Ordered sum + group by
select b, sum(a order by a) from tbench GROUP BY b;

master: 316.117ms
with david's patch: 297.079
with david's patch + mine: 294.601

Setup 2: same as before, but adding an index on (b, a)
CREATE INDEX ON tbench (b, a);

Test 2: Ordered sum:
select sum(a order by a) from tbench;

master: 111.847 ms
with david's patch: 48.088
with david's patch + mine: 47.678 ms

Test 3: Ordered sum + group by:
select a, sum(b order by b) from tbench GROUP BY a;

master: 76.873 ms
with david's patch: 61.105
with david's patch + mine:   62.672 ms

-- 
Ronan Dunklau

---

From: James Coleman <[email-masked]>
Date: Mon, 5 Jul 2021 15:12:51 -0400

> comprehensive to look beyond the first window for windows with a more

I think this is a reasonable choice. I could imagine a more complex
method, say, counting the number of aggregates benefiting from a given
sort, and choosing the one that benefits the most (and this could be
further complicated by ranking based on "cost" -- not costing in the
normal sense since we don't have that at this point), but I think it'd
take a lot of convincing that that was valuable.

> don't really see where else it could go.

That sounds like what nodeIncrementalSort.c's isCurrentGroup() does,
except it's just implemented inline. Not anything you need to change
in this patch, but noting it in case it triggered a thought valuable
for you for me later on.

> would be a good idea or not.

This opens up another path for significant plan benefits too: if
there's now an explicit sort node, then it's possible for that node to
be an incremental sort node, which isn't something nodeAgg is capable
of utilizing currently.

> support for the new expression evaluation steps.

I looked this over (though didn't get a chance to play with it).

I'm wondering about the changes to the test output in tuplesort.out.
It looks like where a merge join used to be proceeding with an
explicit sort with DESC it's now sorting with (implicit) ASC, and then
an explicit sort node using DESC is above the merge join node.  Two
thoughts:

1. It seems like losing the "proper" sort order in the JOIN node isn't
preferable. Given both are full sorts, it may not actually be a
significant performance difference on its own (it can't short
circuit), but it means precluding using incremental sort in the new
sort node.
2. In an ideal world we'd push the more complex sort down into the
merge join rather than doing a sort on "col1" and then a sort on
"col1, col2". That's likely beyond this patch, but I haven't
investigated at all.

Thanks for your work on this; both this patch and the original one
you're trying to enable seem like great additions.

James

---

From: James Coleman <[email-masked]>
Date: Mon, 5 Jul 2021 15:33:59 -0400

> Should I add this separately to the commitfest ?

It seems like a pretty obvious win on its own, and, I'd expect, will
need less discussion than David's patch, so my vote is to make it a
separate thread. The patch tester wants the full series attached each
time, and even without that it's difficult to discuss multiple patches
on a single thread.

If you make a separate thread and CF entry, please CC me and add me as
a reviewer on the CF entry.

One thing from a quick read through of the patch: your changes near
the end of ExecSort, in ExecInitSort, and in execnodes.h need
indentation fixes.

Thanks,
James

---

From: Ronan Dunklau <[email-masked]>
Date: Tue, 06 Jul 2021 08:19:38 +0200

> a reviewer on the CF entry.

Ok, I started a new thread and added it to the next CF: https://
commitfest.postgresql.org/34/3237/

-- 
Ronan Dunklau

---

From: David Rowley <[email-masked]>
Date: Tue, 6 Jul 2021 19:26:49 +1200

> use that API in sort nodes too, when it can be done.

That's a really great find!  Looks like I was wrong to assume that the
extra overhead was from transitioning between nodes.

I ran the performance results locally here with:

create table t1(a int not null);
create table t2(a int not null, b int not null);
create table t3(a int not null, b int not null, c int not null);

insert into t1 select x from generate_Series(1,1000000)x;
insert into t2 select x,x from generate_Series(1,1000000)x;
insert into t3 select x,x,1 from generate_Series(1,1000000)x;
vacuum freeze analyze t1,t2,t3;

select1: select sum(a order by a) from t1;
select2: select sum(a order by b) from t2;
select3: select c,sum(a order by b) from t3 group by c;

master = https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=8aafb02616753f5c6c90bbc567636b73c0cbb9d4
patch1 = https://www.postgresql.org/message-id/attachment/123546/wip_planner_support_for_orderby_distinct_aggs_v0.patch
patch2 = https://www.postgresql.org/message-id/attachment/124238/0001-Allow-Sort-nodes-to-use-the-fast-single-datum-tuples.patch

The attached graph shows the results.

It's very good to see that with both patches applied there's no
regression. I'm a bit surprised there's much performance gain here
given that I didn't add any indexes to provide any presorted input.

David

---

From: David Rowley <[email-masked]>
Date: Tue, 13 Jul 2021 00:04:22 +1200

> support for the new expression evaluation steps.

I've split this patch into two parts.

0001 Adds planner support for ORDER BY aggregates.

0002 is a WIP patch for DISTINCT support.  This still lacks JIT
support and I'm still not certain of the best where to store the
previous value or tuple to determine if the current one is distinct
from it.

The 0001 patch is fairly simple and does not require much in the way
of changes in the planner aside from standard_qp_callback().
Surprisingly the executor does not need a great deal of work here
either.  It's just mostly about skipping the normal agg(.. ORDER BY)
code when the Aggref is presorted.

David

---

From: Ranier Vilela <[email-masked]>
Date: Mon, 12 Jul 2021 20:04:26 -0300

> I've split this patch into two parts.
Hi, I'll take a look.

> 0001 Adds planner support for ORDER BY aggregates.
/* Normal transition function without ORDER BY / DISTINCT. */
Is it possible to avoid entering to initialize args if 'argno >=
pertrans->numTransInputs'?
Like this:

if (!pertrans->aggsortrequired && argno < pertrans->numTransInputs)

And if argos is '>' that pertrans->numTransInputs?
The test shouldn't be, inside the loop?

+ /*
+ * Don't initialize args for any ORDER BY clause that might
+ * exist in a presorted aggregate.
+ */
+ if (argno >= pertrans->numTransInputs)
+ break;

I think that or can reduce the scope of variable 'sortlist' or simply
remove it?

a)
+ /* Determine pathkeys for aggregate functions with an ORDER BY */
+ if (parse->groupingSets == NIL && root->numOrderedAggs > 0 &&
+ (qp_extra->groupClause == NIL || root->group_pathkeys))
+ {
+ ListCell   *lc;
+ List   *pathkeys = NIL;
+
+ foreach(lc, root->agginfos)
+ {
+ AggInfo    *agginfo = (AggInfo *) lfirst(lc);
+ Aggref   *aggref = agginfo->representative_aggref;
+ List   *sortlist;
+

or better

b)
+ /* Determine pathkeys for aggregate functions with an ORDER BY */
+ if (parse->groupingSets == NIL && root->numOrderedAggs > 0 &&
+ (qp_extra->groupClause == NIL || root->group_pathkeys))
+ {
+ ListCell   *lc;
+ List   *pathkeys = NIL;
+
+ foreach(lc, root->agginfos)
+ {
+ AggInfo    *agginfo = (AggInfo *) lfirst(lc);
+ Aggref   *aggref = agginfo->representative_aggref;
+
+ if (AGGKIND_IS_ORDERED_SET(aggref->aggkind))
+ continue;
+
+ /* DISTINCT aggregates not yet supported by the planner */
+ if (aggref->aggdistinct != NIL)
+ continue;
+
+ if (aggref->aggorder == NIL)
+ continue;
+
+ /*
+ * Find the pathkeys with the most sorted derivative of the first
+ * Aggref. For example, if we determine the pathkeys for the first
+ * Aggref to be {a}, and we find another with {a,b}, then we use
+ * {a,b} since it's useful for more Aggrefs than just {a}.  We
+ * currently ignore anything that might have a longer list of
+ * pathkeys than the first Aggref if it is not contained in the
+ * pathkeys for the first agg.  We can't practically plan for all
+ * orders of each Aggref, so this seems like the best compromise.
+ */
+ if (pathkeys == NIL)
+ {
+ pathkeys = make_pathkeys_for_sortclauses(root,  aggref->aggorder ,
+ aggref->args);
+ aggref->aggpresorted = true;
+ }
+ else
+ {
+ List   *pathkeys2 = make_pathkeys_for_sortclauses(root,
+  aggref->aggorder,
+  aggref->args);

> previous value or tuple to determine if the current one is distinct
In the patch 0002, I think that can reduce the scope of variable 'aggstate'?

+ EEO_CASE(EEOP_AGG_PRESORTED_DISTINCT_SINGLE)
+ {
+ AggStatePerTrans pertrans = op->d.agg_presorted_distinctcheck.pertrans;
+ Datum value = pertrans->transfn_fcinfo->args[1].value;
+ bool isnull = pertrans->transfn_fcinfo->args[1].isnull;
+
+ if (!pertrans->haslast ||
+ pertrans->lastisnull != isnull ||
+ !DatumGetBool(FunctionCall2Coll(&pertrans->equalfnOne,
+ pertrans->aggCollation,
+ pertrans->lastdatum, value)))
+ {
+ if (pertrans->haslast && !pertrans->inputtypeByVal)
+ pfree(DatumGetPointer(pertrans->lastdatum));
+
+ pertrans->haslast = true;
+ if (!isnull)
+ {
+ AggState   *aggstate = castNode(AggState, state->parent);
+
+ /*
+ * XXX is it worth having a dedicted ByVal version of this
+ * operation so that we can skip switching memory contexts
+ * and do a simple assign rather than datumCopy below?
+ */
+ MemoryContext oldContext;
+
+ oldContext =
MemoryContextSwitchTo(aggstate->curaggcontext->ecxt_per_tuple_memory);

What do you think?

regards,
Ranier Vilela

---

From: David Rowley <[email-masked]>
Date: Tue, 13 Jul 2021 16:44:12 +1200

Thanks for having a look at this.

On Tue, 13 Jul 2021 at 11:04, Ranier Vilela <[email-masked]> wrote:
> Is it possible to avoid entering to initialize args if 'argno >= pertrans->numTransInputs'?
> Like this:
>

The idea is to stop the loop before processing any Aggref arguments
that might belong to the ORDER BY clause. We must still process other
arguments up to the ORDER BY args though, so we can't skip this loop.

Note that we're doing argno++ inside the loop.  If we had a
for_each_to() macro, similar to for_each_from(), but allowed us to
specify an end element then we could use that instead, but we don't
and we still must initialize the transition arguments.

> I think that or can reduce the scope of variable 'sortlist' or simply remove it?

I've adjusted the scope of this.  I didn't want to remove it because
it's kinda useful to have it that way otherwise the 0002 patch would
need to add it.

> + EEO_CASE(EEOP_AGG_PRESORTED_DISTINCT_SINGLE)

Yeah, that could be done.

I've attached the updated patches.

David

---

From: Ranier Vilela <[email-masked]>
Date: Tue, 13 Jul 2021 08:45:20 -0300

Em ter., 13 de jul. de 2021 às 01:44, David Rowley <[email-masked]>
escreveu:

> that might belong to the ORDER BY clause.

Yes, I get the idea.

We must still process other
> arguments up to the ORDER BY args though,

I may have misunderstood, but the other arguments are under
pertrans->numTransInputs?

> so we can't skip this loop.
>
The question not answered is if *argno* can '>=' that
pertrans->numTransInputs,
before entering the loop?
If *can*, the loop might be useless in that case.

>
> Note that we're doing argno++ inside the loop.

Another question is, if *argno* can '>' that pertrans->numTransInputs,
before the loop, the test will fail?
if (argno == pertrans->numTransInputs)

> it's kinda useful to have it that way otherwise the 0002 patch would
Nice.

> I've attached the updated patches.
Thanks.

regards,
Ranier Vilela

---

From: David Rowley <[email-masked]>
Date: Wed, 14 Jul 2021 13:15:27 +1200

On Tue, 13 Jul 2021 at 23:45, Ranier Vilela <[email-masked]> wrote:
> The question not answered is if *argno* can '>=' that pertrans->numTransInputs,

argno is *always* 0 before the loop starts.

David

---

From: Ranier Vilela <[email-masked]>
Date: Tue, 13 Jul 2021 22:45:22 -0300

> argno is *always* 0 before the loop starts.
Good. Thanks.

regards,
Ranier Vilela

---

From: Ronan Dunklau <[email-masked]>
Date: Thu, 15 Jul 2021 15:02:00 +0200

> I've attached the updated patches.

The approach of building a pathkey for the first order by we find, then 
appending to it as needed seems sensible but I'm a bit worried about users 
starting to rely on this as an optimization. Even if we don't document it, 
people may start to change the order of their target lists to "force" a 
specific sort on the lower nodes. How confident are we that we won't change this 
or that we will be willing to break it ?

Generating all possible pathkeys and costing the resulting plans would be too 
expensive, but maybe a more "stable" (and limited) approach would be fine, like 
generating the pathkeys only if every ordered aggref shares the same prefix. I 
don't think there would be any ambiguity here.

-- 
Ronan Dunklau

---

From: David Rowley <[email-masked]>
Date: Fri, 16 Jul 2021 18:04:03 +1200

> or that we will be willing to break it ?

That's a good question.  I mainly did it that way because Windowing
functions work similarly based on the position of items in the
targetlist.  The situation there is slightly more complex as it
depends on the SortGroupClause->tleSortGroupRef.

> don't think there would be any ambiguity here.

I think that's a bad idea as it would leave a lot on the table. I
don't see any reason to make it that restrictive. Remember that before
this that every Aggref with a sort clause must perform their own sort.
So it's not like we'll ever increase the number of sorts here as a
result.

What we maybe could consider instead would be to pick the first Aggref
then look for the most sorted derivative of that then tally up the
number of Aggrefs that can be sorted using those pathkeys, then repeat
that process for the remaining Aggrefs that didn't have the same
prefix then use the pathkeys for the set with the most Aggrefs.  We
could still tiebreak on the targetlist position so at least it's not
random which ones we pick. Now that we have a list of Aggrefs that are
deduplicated in the planner thanks to 0a2bc5d61e it should be fairly
easy to do that.

David

---

From: David Rowley <[email-masked]>
Date: Fri, 16 Jul 2021 22:00:44 +1200

> deduplicated in the planner thanks to 0a2bc5d61e it should be fairly

I've attached a patch which does as I mention above.

I'm still not sold on if this is better than just going with the order
of the first aggregate.  The problem might be that a plan could change
as new aggregates are added to the end of the target list. It feels
like there might be a bit less control over it than the previous
version. Remember that suiting more aggregates is not always better as
there might be an index that could provide presorted input for another
set of aggregates which would overall reduce the number of sorts.
However, maybe it's not too big an issue as for any aggregates that
are not presorted we're left doing 1 sort per Aggref, so reducing the
number of those might be more important than selecting the order that
has an index to support it.

I've left off the 0002 patch this time as I think the lack of JIT
support for DISTINCT was causing the CF bot to fail.  I'd quite like
to confirm that theory.

David

---

From: David Rowley <[email-masked]>
Date: Sat, 17 Jul 2021 14:36:09 +1200

> I've attached a patch which does as I mention above.

Looks like I did a sloppy job of that.  I messed up the condition in
standard_qp_callback() that sets the ORDER BY aggregate pathkeys so
that it accidentally set them when there was an unsortable GROUP BY
clause, as highlighted by the postgres_fdw tests failing.  I've now
added a comment to explain why the condition is the way it is so that
I don't forget again.

Here's a cleaned-up version that passes make check-world.

David

---

From: Ronan Dunklau <[email-masked]>
Date: Mon, 19 Jul 2021 08:32:34 +0200

> Here's a cleaned-up version that passes make check-world.

I've noticed that when the ORDER BY is a grouping key (which to be honest 
doesn't seem to make much sense to me), the sort key is duplicated, as 
demonstrated by one of the modified tests (partition_aggregate.sql). 

This leads to additional sort nodes being added when there is no necessity to 
do so. In the case of sort and index pathes, the duplicate keys are not 
considered,  I think the same should apply here.

It means the logic for appending the order by pathkeys to the existing group 
by pathkeys would ideally need to remove the redundant group by keys from the 
order by keys, considering this example:

regression=# explain select sum(unique1 order by ten, two), sum(unique1 order 
by four), sum(unique1 order by two, four) from tenk2 group by ten;
                               QUERY PLAN                               
------------------------------------------------------------------------
 GroupAggregate  (cost=1109.39..1234.49 rows=10 width=28)
   Group Key: ten
   ->  Sort  (cost=1109.39..1134.39 rows=10000 width=16)
         Sort Key: ten, ten, two
         ->  Seq Scan on tenk2  (cost=0.00..445.00 rows=10000 width=16)

We would ideally like to sort on ten, two, four to satisfy the first and last 
aggref at once. Stripping the common prefix (ten) would eliminate this problem. 

Also, existing regression tests cover the first problem (order by a grouping 
key) but I feel like they should be extended with a case similar as the above 
to check which pathkeys are used in the "multiple ordered aggregates + group 
by" cases. 

-- 
Ronan Dunklau

---

From: David Rowley <[email-masked]>
Date: Tue, 20 Jul 2021 23:06:40 +1200

> by four), sum(unique1 order by two, four) from tenk2 group by ten;

hmm, yeah. That's not great.  This comes from the way I'm doing
list_concat on the pathkeys from the GROUP BY with the ones from the
ordered aggregates. If it were possible to use
make_pathkeys_for_sortclauses() to make these in one go, that would
fix the problem since pathkey_is_redundant() would skip the 2nd "ten".
Unfortunately, it's not possible to pass the combined list of
SortGroupClauses to make_pathkeys_for_sortclauses since they're not
from the same targetlist.  Aggrefs have their own targetlist and the
SortGroupClauses for the Aggref reference that tlist.

I think to do this we'd need something like pathkeys_append() in
pathkeys.c which had a loop and appended the pathkey only if
pathkey_is_redundant returns false.

> to check which pathkeys are used in the "multiple ordered aggregates + group

It does seem like a bit of a weird case to go to a lot of effort to
make work, but it would be nice if it did work without having to
contort the code too much.

David

---

From: David Rowley <[email-masked]>
Date: Wed, 21 Jul 2021 14:52:43 +1200

> by four), sum(unique1 order by two, four) from tenk2 group by ten;

Thanks for finding this.  I've made a few changes to make this case
work as you describe. Please see attached v6 patches.

Because I had to add additional code to take the GROUP BY pathkeys
into account when choosing the best ORDER BY agg pathkeys, the
function that does that became a little bigger.  To try to reduce the
complexity of it, I got rid of all the processing from the initial
loop and instead it now uses the logic from the 2nd loop to find the
best pathkeys.  The reason I'd not done that in the first place was
because I'd thought I could get away without building an additional
Bitmapset for simple cases, but that's probably fairly cheap compared
to building Pathkeys.   With the additional complexity for the GROUP
BY pathkeys, the extra code seemed not worth it.

The 0001 patch is the ORDER BY aggregate code.  0002 is to fix up some
broken regression tests in postgres_fdw that 0001 caused.  It appears
that 0001 uncovered a bug in the postgres_fdw code.  I've reported
that in [1]. If that turns out to be a bug then it'll need to be fixed
before this can progress.

David

[1] https://www.postgresql.org/message-id/CAApHDvr4OeC2DBVY--zVP83-K=[email-masked]

---

From: Ronan Dunklau <[email-masked]>
Date: Wed, 21 Jul 2021 16:01:03 +0200

> before this can progress.

I tested the 0001 patch against both HEAD and my proposed bugfix for 
postgres_fdw.

There is a problem that the ordered aggregate is not pushed down anymore. The 
underlying Sort node is correctly pushed down though. 

This comes from the fact that postgres_fdw grouping path never contains any 
pathkey. Since the cost is fuzzily the same between the pushed-down aggregate 
and the locally performed one, the tie is broken against the pathkeys.

Ideally we would add the group pathkeys to the grouping path, but this would 
add an additional ORDER BY expression matching the GROUP BY. Moreover, some 
triaging of the pathkeys would be necessary since we now mix the sort-in-
aggref pathkeys with the group_pathkeys.

-- 
Ronan Dunklau

---

From: David Rowley <[email-masked]>
Date: Thu, 22 Jul 2021 19:38:50 +1200

> and the locally performed one, the tie is broken against the pathkeys.

I think this might be more down to a lack of any penalty cost for
fetching foreign tuples. Looking at create_foreignscan_path(), I don't
see anything that adds anything to account for fetching the tuples
from the foreign server. If there was something like that then there'd
be more of a preference to perform the remote aggregation so that
fewer rows must arrive from the remote server.

I tested by adding: total_cost += cpu_tuple_cost * rows * 100; in
create_foreignscan_path() and I got the plan with the remote
aggregation. That's a fairly large penalty of 1.0 per row. Much bigger
than parallel_tuple_cost's default value.

I'm a bit undecided on how much this patch needs to get involved in
adjusting foreign scan costs.  The problem is that we've given the
executor a new path to consider and nobody has done any proper
costings for the foreign scan so that it properly prefers paths that
have to pull fewer foreign tuples.  This is a pretty similar problem
to what parallel_tuple_cost aims to fix. Also similar to how we had to
add APPEND_CPU_COST_MULTIPLIER to have partition-wise aggregates
prefer grouping at the partition level rather than at the partitioned
table level.

> aggref pathkeys with the group_pathkeys.

I think you're talking about passing pathkeys into
create_foreign_upper_path in add_foreign_grouping_paths. If so, I
don't really see how it would be safe to add pathkeys to the foreign
grouping path. What if the foreign server did a Hash Aggregate?  The
rows might come back in any random order.

I kinda think that to fix this properly would need a new foreign
server option such as foreign_tuple_cost. I'd feel better about
something like that with some of the people with a vested interest in
the FDW code were watching more closely. So far we've not managed to
entice any of them with the bug report yet, but it's maybe early days
yet.

David

---

From: Ronan Dunklau <[email-masked]>
Date: Thu, 22 Jul 2021 10:42:49 +0200

Le jeudi 22 juillet 2021, 09:38:50 CEST David Rowley a écrit :
> > There is a problem that the ordered aggregate is not pushed down anymore.
> > The underlying Sort node is correctly pushed down though.
> > 
> > pathkey. Since the cost is fuzzily the same between the pushed-down
> > aggregate and the locally performed one, the tie is broken against the
> > pathkeys.
> > Ideally we would add the group pathkeys to the grouping path, but this
> > would add an additional ORDER BY expression matching the GROUP BY.
> > Moreover, some triaging of the pathkeys would be necessary since we now
> > mix the sort-in- aggref pathkeys with the group_pathkeys.
> 

Yes, I was suggesting to add a new path with the pathkeys factored in, which 
if chosen over the non-ordered path would result in an additional ORDER BY 
clause to prevent a HashAggregate. But that doesn't seem a good idea after 
all.

> entice any of them with the bug report yet, but it's maybe early days

We already have that in the form of fdw_tuple_cost as a server option if I'm 
not mistaken ? It works as expected when the number of tuples is notably 
reduced by the foreign group by.

The problem arise when the cardinality of the groups is equal to the input's 
cardinality. I think even in that case we should try to use a remote aggregate 
since it's a computation that will not happen on the local server. I also 
think we're more likely to have up to date statistics remotely than the ones 
collected locally on the foreign tables, and the estimated number of groups 
would be more accurate on the remote side than the local one.

-- 
Ronan Dunklau

---

From: Ronan Dunklau <[email-masked]>
Date: Thu, 04 Nov 2021 08:59:00 +0100

Le jeudi 22 juillet 2021, 10:42:49 CET Ronan Dunklau a écrit :
> cardinality. I think even in that case we should try to use a remote
> aggregate since it's a computation that will not happen on the local
> server. I also think we're more likely to have up to date statistics
> remotely than the ones collected locally on the foreign tables, and the
> estimated number of groups would be more accurate on the remote side than
> the local one.

I took some time to toy with this again.

At first I thought that charging a discount in foreign grouping paths for 
Aggref targets (since they are computed remotely) would be a good idea, 
similar to what is done for the grouping keys.

But in the end, it's probably not something we would like to do. Yes, the 
group planning will be more accurate on the remote side generally (better 
statistics than locally for estimating the number of groups) but executing the 
grouping locally when the number of groups is close to the input's cardinality 
(ex: group by unique_key)  gives us a form of parallelism which can actually 
perform better. 

For the other cases where there is fewer output than input tuples, that is, 
when an actual grouping takes place, adjusting fdw_tuple_cost might be enough 
to tune the behavior to what is desirable.

-- 
Ronan Dunklau

---

From: Greg Stark <[email-masked]>
Date: Wed, 30 Mar 2022 13:35:57 -0400

This patch is now failing in the sqljson regression test. It looks
like it's just the ordering of the elements in json_arrayagg() calls
which may actually be a faulty test that needs more ORDER BY clauses
rather than any issues with the code. Nonetheless it's something that
needs to be addressed before this patch could be applied.

Given it's gotten some feedback from Ronan and this regression test
failure I'll move it to Waiting on Author but we're near the end of
the CF and it'll probably be moved forward soon.

-- 
greg

---

From: David Rowley <[email-masked]>
Date: Wed, 20 Jul 2022 17:26:39 +1200

> similar to what is done for the grouping keys.

I've been working on this patch again. There was a bit of work to do
to rebase it atop db0d67db2.  The problem there was that since this
patch appends pathkeys to suit ORDER BY / DISTINCT aggregates to the
query's group_pathkeys, db0d67db2 goes and tries to rearrange those,
but fails to find the SortGroupClause corresponding to the PathKey in
group_pathkeys. I wish the code I came up with to make that work was a
bit nicer, but what's there at least seems to work. There are a few
more making copies of Lists than I'd like.

I've also went and added LLVM support to make JIT work with the new
DISTINCT expression evaluation step types.

Also, James mentioned in [1] about the Merge Join plan change that
this patch was causing in an existing test.  I looked into that and
found the cause.  The plan change is not really the fault of this
patch, so I've proposed a fix for to make that work more efficiently
in [2]. The basics there are that select_outer_pathkeys_for_merge()
pre-dates Incremental Sorts and didn't consider prefixes of the
query_pathkeys after matching all the join quals. The patch on that
thread relaxes that rule and makes this patch produce an Incremental
Sort plan for the query in question.

Another annoying part of this patch is that I've added an
"aggpresorted" field to Aggref, which the planner sets.  That's a
parse node type and it would be nicer not to have the planner mess
around with those. We maybe could wrap up the Aggrefs in some planner
struct and pass those to the executor instead.  That would require a
bit more churn than what I've got in the attached.

I've attached the v7 patch.

David

[1] https://www.postgresql.org/message-id/CAAaqYe-yxXkXVPJkRw1nDA=CJBw28jvhACRyDcU10dAOcdSj=[email-masked]
[2] https://www.postgresql.org/message-id/[email-masked]
From f586a426d1bb3b32aa3be8dec94b17944353600e Mon Sep 17 00:00:00 2001
From: David Rowley <[email-masked]>
Date: Mon, 3 May 2021 16:31:29 +1200
Subject: [PATCH v7] Add planner support for ORDER BY aggregates

ORDER BY aggreagtes have, since implemented in Postgres, been executed by
always performing a sort in nodeAgg.c to sort the tuples in the current
group into the correct order before calling the transition function on the
sorted results.  This was not great as often there might be an index that
could have provided pre-sorted input and allowed the transition functions
to be called as the rows come in, rather than having to store them in a
tuplestore in order to sort them later.

Here we get the planner on-board with picking a plan that provides
pre-sorted inputs to ORDER BY aggregates.

Since there can be many ORDER BY aggregates in any given query level, it's
very possible that we can't find an order that suits all aggregates.  The
sort order the the planner chooses is simply the one that suits the most
aggregate functions.  We take the most strictly sorted variation of each
order and see how many aggregate functions can use that, then we try again
with the order of the remaining aggregates to see if another order would
suit more aggregate functions.  For example:

would request the sort order to be {a, b} because {a} is a subset of the
sort order of {a,b}, but;

would just pick a plan ordered by {a}.

SELECT agg(a ORDER BY a),agg2(a ORDER BY b),agg3(a ORDER BY b) ...

would choose to order by {b} since two aggregates suit that vs just one
that requires order by {a}.

Discussion: https://postgr.es/m/CAApHDvpHzfo92%3DR4W0%2BxVua3BUYCKMckWAmo-2t_KiXN-wYH%3Dw%40mail.gmail.com
---
 .../postgres_fdw/expected/postgres_fdw.out    |  46 +--
 src/backend/executor/execExpr.c               |  52 +++-
 src/backend/executor/execExprInterp.c         | 102 ++++++
 src/backend/executor/nodeAgg.c                |  34 +-
 src/backend/jit/llvm/llvmjit_expr.c           |  48 +++
 src/backend/jit/llvm/llvmjit_types.c          |   2 +
 src/backend/optimizer/path/pathkeys.c         |  44 ++-
 src/backend/optimizer/plan/planagg.c          |   2 +-
 src/backend/optimizer/plan/planner.c          | 294 ++++++++++++++++--
 src/backend/optimizer/prep/prepagg.c          |   7 +-
 src/include/executor/execExpr.h               |  17 +
 src/include/executor/nodeAgg.h                |   9 +
 src/include/nodes/pathnodes.h                 |  16 +-
 src/include/nodes/primnodes.h                 |   7 +
 src/include/optimizer/paths.h                 |   4 +-
 src/test/regress/expected/aggregates.out      |  80 ++++-
 .../regress/expected/partition_aggregate.out  | 118 +++----
 src/test/regress/expected/sqljson.out         |  12 +-
 src/test/regress/expected/tuplesort.out       |  40 +--
 src/test/regress/sql/aggregates.sql           |  43 +++
 20 files changed, 833 insertions(+), 144 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index ade797159d..a42e16e8d2 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -3295,15 +3295,18 @@ create operator class my_op_class for type int using btree family my_op_family a
 -- extension yet.
 explain (verbose, costs off)
 select array_agg(c1 order by c1 using operator(public.<^)) from ft2 where c2 = 6 and c1 < 100 group by c2;
-                                         QUERY PLAN                                         
---------------------------------------------------------------------------------------------
+                                            QUERY PLAN                                            
+--------------------------------------------------------------------------------------------------
  GroupAggregate
    Output: array_agg(c1 ORDER BY c1 USING <^ NULLS LAST), c2
    Group Key: ft2.c2
-   ->  Foreign Scan on public.ft2
-         Output: c1, c2
-         Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND ((c2 = 6))
-(6 rows)
+   ->  Sort
+         Output: c2, c1
+         Sort Key: ft2.c1 USING <^
+         ->  Foreign Scan on public.ft2
+               Output: c2, c1
+               Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND ((c2 = 6))
+(9 rows)
 
 -- This should not be pushed either.
 explain (verbose, costs off)
@@ -3331,13 +3334,15 @@ alter server loopback options (set extensions 'postgres_fdw');
 -- Now this will be pushed as sort operator is part of the extension.
 explain (verbose, costs off)
 select array_agg(c1 order by c1 using operator(public.<^)) from ft2 where c2 = 6 and c1 < 100 group by c2;
-                                                                           QUERY PLAN                                                                           
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
- Foreign Scan
-   Output: (array_agg(c1 ORDER BY c1 USING <^ NULLS LAST)), c2
-   Relations: Aggregate on (public.ft2)
-   Remote SQL: SELECT array_agg("C 1" ORDER BY "C 1" USING OPERATOR(public.<^) NULLS LAST), c2 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND ((c2 = 6)) GROUP BY 2
-(4 rows)
+                                                                   QUERY PLAN                                                                   
+------------------------------------------------------------------------------------------------------------------------------------------------
+ GroupAggregate
+   Output: array_agg(c1 ORDER BY c1 USING <^ NULLS LAST), c2
+   Group Key: ft2.c2
+   ->  Foreign Scan on public.ft2
+         Output: c1, c2
+         Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND ((c2 = 6)) ORDER BY "C 1" USING OPERATOR(public.<^) NULLS LAST
+(6 rows)
 
 select array_agg(c1 order by c1 using operator(public.<^)) from ft2 where c2 = 6 and c1 < 100 group by c2;
            array_agg            
@@ -3366,15 +3371,18 @@ alter server loopback options (set extensions 'postgres_fdw');
 -- This will not be pushed as sort operator is now removed from the extension.
 explain (verbose, costs off)
 select array_agg(c1 order by c1 using operator(public.<^)) from ft2 where c2 = 6 and c1 < 100 group by c2;
-                                         QUERY PLAN                                         
---------------------------------------------------------------------------------------------
+                                            QUERY PLAN                                            
+--------------------------------------------------------------------------------------------------
  GroupAggregate
    Output: array_agg(c1 ORDER BY c1 USING <^ NULLS LAST), c2
    Group Key: ft2.c2
-   ->  Foreign Scan on public.ft2
-         Output: c1, c2
-         Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND ((c2 = 6))
-(6 rows)
+   ->  Sort
+         Output: c2, c1
+         Sort Key: ft2.c1 USING <^
+         ->  Foreign Scan on public.ft2
+               Output: c2, c1
+               Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND ((c2 = 6))
+(9 rows)
 
 -- Cleanup
 drop operator class my_op_class using btree;
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index c8d7145fe3..d0a57c7aae 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3666,13 +3666,17 @@ ExecBuildAggTrans(AggState *aggstate, AggStatePerPhase phase,
 				scratch.resnull = &state->resnull;
 			}
 			argno++;
+
+			Assert(pertrans->numInputs == argno);
 		}
-		else if (pertrans->numSortCols == 0)
+		else if (!pertrans->aggsortrequired)
 		{
 			ListCell   *arg;
 
 			/*
-			 * Normal transition function without ORDER BY / DISTINCT.
+			 * Normal transition function without ORDER BY / DISTINCT or with
+			 * ORDER BY / DISTINCT but the planner has given us pre-sorted
+			 * input.
 			 */
 			strictargs = trans_fcinfo->args + 1;
 
@@ -3680,6 +3684,13 @@ ExecBuildAggTrans(AggState *aggstate, AggStatePerPhase phase,
 			{
 				TargetEntry *source_tle = (TargetEntry *) lfirst(arg);
 
+				/*
+				 * Don't initialize args for any ORDER BY clause that might
+				 * exist in a presorted aggregate.
+				 */
+				if (argno == pertrans->numTransInputs)
+					break;
+
 				/*
 				 * Start from 1, since the 0th arg will be the transition
 				 * value
@@ -3689,11 +3700,13 @@ ExecBuildAggTrans(AggState *aggstate, AggStatePerPhase phase,
 								&trans_fcinfo->args[argno + 1].isnull);
 				argno++;
 			}
+			Assert(pertrans->numTransInputs == argno);
 		}
 		else if (pertrans->numInputs == 1)
 		{
 			/*
-			 * DISTINCT and/or ORDER BY case, with a single column sorted on.
+			 * Non-presorted DISTINCT and/or ORDER BY case, with a single
+			 * column sorted on.
 			 */
 			TargetEntry *source_tle =
 			(TargetEntry *) linitial(pertrans->aggref->args);
@@ -3705,11 +3718,14 @@ ExecBuildAggTrans(AggState *aggstate, AggStatePerPhase phase,
 							&state->resnull);
 			strictnulls = &state->resnull;
 			argno++;
+
+			Assert(pertrans->numInputs == argno);
 		}
 		else
 		{
 			/*
-			 * DISTINCT and/or ORDER BY case, with multiple columns sorted on.
+			 * Non-presorted DISTINCT and/or ORDER BY case, with multiple
+			 * columns sorted on.
 			 */
 			Datum	   *values = pertrans->sortslot->tts_values;
 			bool	   *nulls = pertrans->sortslot->tts_isnull;
@@ -3725,8 +3741,8 @@ ExecBuildAggTrans(AggState *aggstate, AggStatePerPhase phase,
 								&values[argno], &nulls[argno]);
 				argno++;
 			}
+			Assert(pertrans->numInputs == argno);
 		}
-		Assert(pertrans->numInputs == argno);
 
 		/*
 		 * For a strict transfn, nothing happens when there's a NULL input; we
@@ -3748,6 +3764,21 @@ ExecBuildAggTrans(AggState *aggstate, AggStatePerPhase phase,
 										 state->steps_len - 1);
 		}
 
+		/* Handle DISTINCT aggregates which have pre-sorted input */
+		if (pertrans->numDistinctCols > 0 && !pertrans->aggsortrequired)
+		{
+			if (pertrans->numDistinctCols > 1)
+				scratch.opcode = EEOP_AGG_PRESORTED_DISTINCT_MULTI;
+			else
+				scratch.opcode = EEOP_AGG_PRESORTED_DISTINCT_SINGLE;
+
+			scratch.d.agg_presorted_distinctcheck.pertrans = pertrans;
+			scratch.d.agg_presorted_distinctcheck.jumpdistinct = -1;	/* adjust later */
+			ExprEvalPushStep(state, &scratch);
+			adjust_bailout = lappend_int(adjust_bailout,
+										 state->steps_len - 1);
+		}
+
 		/*
 		 * Call transition function (once for each concurrently evaluated
 		 * grouping set). Do so for both sort and hash based computations, as
@@ -3808,6 +3839,12 @@ ExecBuildAggTrans(AggState *aggstate, AggStatePerPhase phase,
 				Assert(as->d.agg_deserialize.jumpnull == -1);
 				as->d.agg_deserialize.jumpnull = state->steps_len;
 			}
+			else if (as->opcode == EEOP_AGG_PRESORTED_DISTINCT_SINGLE ||
+					 as->opcode == EEOP_AGG_PRESORTED_DISTINCT_MULTI)
+			{
+				Assert(as->d.agg_presorted_distinctcheck.jumpdistinct == -1);
+				as->d.agg_presorted_distinctcheck.jumpdistinct = state->steps_len;
+			}
 			else
 				Assert(false);
 		}
@@ -3857,7 +3894,8 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
 	/*
 	 * Determine appropriate transition implementation.
 	 *
-	 * For non-ordered aggregates:
+	 * For non-ordered aggregates and ORDER BY / DISTINCT aggregates with
+	 * presorted input:
 	 *
 	 * If the initial value for the transition state doesn't exist in the
 	 * pg_aggregate table then we will let the first non-NULL value returned
@@ -3887,7 +3925,7 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
 	 * process_ordered_aggregate_{single, multi} and
 	 * advance_transition_function.
 	 */
-	if (pertrans->numSortCols == 0)
+	if (!pertrans->aggsortrequired)
 	{
 		if (pertrans->transtypeByVal)
 		{
diff --git a/src/backend/executor/execExprInterp.c b/src/backend/executor/execExprInterp.c
index 723770fda0..e8d77929a9 100644
--- a/src/backend/executor/execExprInterp.c
+++ b/src/backend/executor/execExprInterp.c
@@ -502,6 +502,8 @@ ExecInterpExpr(ExprState *state, ExprContext *econtext, bool *isnull)
 		&&CASE_EEOP_AGG_PLAIN_TRANS_INIT_STRICT_BYREF,
 		&&CASE_EEOP_AGG_PLAIN_TRANS_STRICT_BYREF,
 		&&CASE_EEOP_AGG_PLAIN_TRANS_BYREF,
+		&&CASE_EEOP_AGG_PRESORTED_DISTINCT_SINGLE,
+		&&CASE_EEOP_AGG_PRESORTED_DISTINCT_MULTI,
 		&&CASE_EEOP_AGG_ORDERED_TRANS_DATUM,
 		&&CASE_EEOP_AGG_ORDERED_TRANS_TUPLE,
 		&&CASE_EEOP_LAST
@@ -1786,6 +1788,28 @@ ExecInterpExpr(ExprState *state, ExprContext *econtext, bool *isnull)
 			EEO_NEXT();
 		}
 
+		EEO_CASE(EEOP_AGG_PRESORTED_DISTINCT_SINGLE)
+		{
+			AggStatePerTrans pertrans = op->d.agg_presorted_distinctcheck.pertrans;
+			AggState   *aggstate = castNode(AggState, state->parent);
+
+			if (ExecEvalPreOrderedDistinctSingle(aggstate, pertrans))
+				EEO_NEXT();
+			else
+				EEO_JUMP(op->d.agg_presorted_distinctcheck.jumpdistinct);
+		}
+
+		EEO_CASE(EEOP_AGG_PRESORTED_DISTINCT_MULTI)
+		{
+			AggState   *aggstate = castNode(AggState, state->parent);
+			AggStatePerTrans pertrans = op->d.agg_presorted_distinctcheck.pertrans;
+
+			if (ExecEvalPreOrderedDistinctMulti(aggstate, pertrans))
+				EEO_NEXT();
+			else
+				EEO_JUMP(op->d.agg_presorted_distinctcheck.jumpdistinct);
+		}
+
 		/* process single-column ordered aggregate datum */
 		EEO_CASE(EEOP_AGG_ORDERED_TRANS_DATUM)
 		{
@@ -4402,6 +4426,84 @@ ExecAggTransReparent(AggState *aggstate, AggStatePerTrans pertrans,
 	return newValue;
 }
 
+/*
+ * ExecEvalPreOrderedDistinctSingle
+ *		Returns true when the aggregate transition value Datum is distinct
+ *		from the previous input Datum and returns false when the input Datum
+ *		matches the previous input Datum.
+ */
+bool
+ExecEvalPreOrderedDistinctSingle(AggState *aggstate, AggStatePerTrans pertrans)
+{
+	Datum		value = pertrans->transfn_fcinfo->args[1].value;
+	bool		isnull = pertrans->transfn_fcinfo->args[1].isnull;
+
+	if (!pertrans->haslast ||
+		pertrans->lastisnull != isnull ||
+		!DatumGetBool(FunctionCall2Coll(&pertrans->equalfnOne,
+					  pertrans->aggCollation,
+					  pertrans->lastdatum, value)))
+	{
+		if (pertrans->haslast && !pertrans->inputtypeByVal)
+			pfree(DatumGetPointer(pertrans->lastdatum));
+
+		pertrans->haslast = true;
+		if (!isnull)
+		{
+			MemoryContext oldContext;
+
+			oldContext = MemoryContextSwitchTo(aggstate->curaggcontext->ecxt_per_tuple_memory);
+
+			pertrans->lastdatum = datumCopy(value, pertrans->inputtypeByVal,
+											pertrans->inputtypeLen);
+
+			MemoryContextSwitchTo(oldContext);
+		}
+		else
+			pertrans->lastdatum = (Datum) 0;
+		pertrans->lastisnull = isnull;
+		return true;
+	}
+
+	return false;
+}
+
+/*
+ * ExecEvalPreOrderedDistinctMulti
+ *		Returns true when the aggregate input is distinct from the previous
+ *		input and returns false when the input matches the previous input.
+ */
+bool
+ExecEvalPreOrderedDistinctMulti(AggState *aggstate, AggStatePerTrans pertrans)
+{
+	ExprContext *tmpcontext = aggstate->tmpcontext;
+
+	for (int i = 0; i < pertrans->numTransInputs; i++)
+	{
+		pertrans->sortslot->tts_values[i] = pertrans->transfn_fcinfo->args[i + 1].value;
+		pertrans->sortslot->tts_isnull[i] = pertrans->transfn_fcinfo->args[i + 1].isnull;
+	}
+
+	ExecClearTuple(pertrans->sortslot);
+	pertrans->sortslot->tts_nvalid = pertrans->numInputs;
+	ExecStoreVirtualTuple(pertrans->sortslot);
+
+	tmpcontext->ecxt_outertuple = pertrans->sortslot;
+	tmpcontext->ecxt_innertuple = pertrans->uniqslot;
+
+	if (!pertrans->haslast ||
+		!ExecQual(pertrans->equalfnMulti, tmpcontext))
+	{
+		if (pertrans->haslast)
+			ExecClearTuple(pertrans->uniqslot);
+
+		pertrans->haslast = true;
+		ExecCopySlot(pertrans->uniqslot, pertrans->sortslot);
+		return true;
+	}
+	return false;
+}
+
 /*
  * Invoke ordered transition function, with a datum argument.
  */
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 2fc606cf29..96d200e446 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -583,7 +583,7 @@ initialize_aggregate(AggState *aggstate, AggStatePerTrans pertrans,
 	/*
 	 * Start a fresh sort operation for each DISTINCT/ORDER BY aggregate.
 	 */
-	if (pertrans->numSortCols > 0)
+	if (pertrans->aggsortrequired)
 	{
 		/*
 		 * In case of rescan, maybe there could be an uncompleted sort
@@ -1309,7 +1309,7 @@ finalize_aggregates(AggState *aggstate,
 
 		pergroupstate = &pergroup[transno];
 
-		if (pertrans->numSortCols > 0)
+		if (pertrans->aggsortrequired)
 		{
 			Assert(aggstate->aggstrategy != AGG_HASHED &&
 				   aggstate->aggstrategy != AGG_MIXED);
@@ -1323,6 +1323,21 @@ finalize_aggregates(AggState *aggstate,
 												pertrans,
 												pergroupstate);
 		}
+		else if (pertrans->numDistinctCols > 0 && pertrans->haslast)
+		{
+			pertrans->haslast = false;
+
+			if (pertrans->numDistinctCols == 1)
+			{
+				if (!pertrans->inputtypeByVal && !pertrans->lastisnull)
+					pfree(DatumGetPointer(pertrans->lastdatum));
+
+				pertrans->lastisnull = false;
+				pertrans->lastdatum = (Datum) 0;
+			}
+			else
+				ExecClearTuple(pertrans->uniqslot);
+		}
 	}
 
 	/*
@@ -4127,6 +4142,12 @@ build_pertrans_for_aggref(AggStatePerTrans pertrans,
 	 * stick them into arrays.  We ignore ORDER BY for an ordered-set agg,
 	 * however; the agg's transfn and finalfn are responsible for that.
 	 *
+	 * When the planner has set the aggpresorted flag, the input to the
+	 * aggregate is already correctly sorted.  For ORDER BY aggregates we can
+	 * simply treat these as normal aggregates.  For presorted DISTINCT
+	 * aggregates an extra step must be added to remove duplicate consecutive
+	 * inputs.
+	 *
 	 * Note that by construction, if there is a DISTINCT clause then the ORDER
 	 * BY clause is a prefix of it (see transformDistinctClause).
 	 */
@@ -4134,18 +4155,27 @@ build_pertrans_for_aggref(AggStatePerTrans pertrans,
 	{
 		sortlist = NIL;
 		numSortCols = numDistinctCols = 0;
+		pertrans->aggsortrequired = false;
+	}
+	else if (aggref->aggpresorted && aggref->aggdistinct == NIL)
+	{
+		sortlist = NIL;
+		numSortCols = numDistinctCols = 0;
+		pertrans->aggsortrequired = false;
 	}
 	else if (aggref->aggdistinct)
 	{
 		sortlist = aggref->aggdistinct;
 		numSortCols = numDistinctCols = list_length(sortlist);
 		Assert(numSortCols >= list_length(aggref->aggorder));
+		pertrans->aggsortrequired = !aggref->aggpresorted;
 	}
 	else
 	{
 		sortlist = aggref->aggorder;
 		numSortCols = list_length(sortlist);
 		numDistinctCols = 0;
+		pertrans->aggsortrequired = (numSortCols > 0);
 	}
 
 	pertrans->numSortCols = numSortCols;
diff --git a/src/backend/jit/llvm/llvmjit_expr.c b/src/backend/jit/llvm/llvmjit_expr.c
index b6b6512ef1..c6eb2e9207 100644
--- a/src/backend/jit/llvm/llvmjit_expr.c
+++ b/src/backend/jit/llvm/llvmjit_expr.c
@@ -2335,6 +2335,54 @@ llvm_compile_expr(ExprState *state)
 					break;
 				}
 
+			case EEOP_AGG_PRESORTED_DISTINCT_SINGLE:
+			{
+				AggState   *aggstate = castNode(AggState, state->parent);
+				AggStatePerTrans pertrans = op->d.agg_presorted_distinctcheck.pertrans;
+				int			jumpdistinct = op->d.agg_presorted_distinctcheck.jumpdistinct;
+
+				LLVMValueRef	v_fn = llvm_pg_func(mod, "ExecEvalPreOrderedDistinctSingle");
+				LLVMValueRef	v_args[2];
+				LLVMValueRef	v_ret;
+
+				v_args[0] = l_ptr_const(aggstate, l_ptr(StructAggState));
+				v_args[1] = l_ptr_const(pertrans, l_ptr(StructAggStatePerTransData));
+
+				v_ret = LLVMBuildCall(b, v_fn, v_args, 2, "");
+				v_ret = LLVMBuildZExt(b, v_ret, TypeStorageBool, "");
+
+				LLVMBuildCondBr(b,
+								LLVMBuildICmp(b, LLVMIntEQ, v_ret,
+												l_sbool_const(1), ""),
+								opblocks[opno + 1],
+								opblocks[jumpdistinct]);
+				break;
+			}
+
+			case EEOP_AGG_PRESORTED_DISTINCT_MULTI:
+			{
+				AggState   *aggstate = castNode(AggState, state->parent);
+				AggStatePerTrans pertrans = op->d.agg_presorted_distinctcheck.pertrans;
+				int			jumpdistinct = op->d.agg_presorted_distinctcheck.jumpdistinct;
+
+				LLVMValueRef	v_fn = llvm_pg_func(mod, "ExecEvalPreOrderedDistinctMulti");
+				LLVMValueRef	v_args[2];
+				LLVMValueRef	v_ret;
+
+				v_args[0] = l_ptr_const(aggstate, l_ptr(StructAggState));
+				v_args[1] = l_ptr_const(pertrans, l_ptr(StructAggStatePerTransData));
+
+				v_ret = LLVMBuildCall(b, v_fn, v_args, 2, "");
+				v_ret = LLVMBuildZExt(b, v_ret, TypeStorageBool, "");
+
+				LLVMBuildCondBr(b,
+								LLVMBuildICmp(b, LLVMIntEQ, v_ret,
+												l_sbool_const(1), ""),
+								opblocks[opno + 1],
+								opblocks[jumpdistinct]);
+				break;
+			}
+
 			case EEOP_AGG_ORDERED_TRANS_DATUM:
 				build_EvalXFunc(b, mod, "ExecEvalAggOrderedTransDatum",
 								v_state, op, v_econtext);
diff --git a/src/backend/jit/llvm/llvmjit_types.c b/src/backend/jit/llvm/llvmjit_types.c
index b2bda86889..373471ad27 100644
--- a/src/backend/jit/llvm/llvmjit_types.c
+++ b/src/backend/jit/llvm/llvmjit_types.c
@@ -103,6 +103,8 @@ void	   *referenced_functions[] =
 {
 	ExecAggInitGroup,
 	ExecAggTransReparent,
+	ExecEvalPreOrderedDistinctSingle,
+	ExecEvalPreOrderedDistinctMulti,
 	ExecEvalAggOrderedTransDatum,
 	ExecEvalAggOrderedTransTuple,
 	ExecEvalArrayCoerce,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index b5d6c977ee..11de286e60 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -103,6 +103,27 @@ make_canonical_pathkey(PlannerInfo *root,
 	return pk;
 }
 
+/*
+ * append_pathkeys
+ *		Append all non-redundant PathKeys in 'source' onto 'target'
+ */
+List *
+append_pathkeys(List *target, List *source)
+{
+	ListCell   *lc;
+
+	Assert(target != NIL);
+
+	foreach(lc, source)
+	{
+		PathKey    *pk = lfirst_node(PathKey, lc);
+
+		if (!pathkey_is_redundant(pk, target))
+			target = lappend(target, pk);
+	}
+	return target;
+}
+
 /*
  * pathkey_is_redundant
  *	   Is a pathkey redundant with one already in the given list?
@@ -746,7 +767,8 @@ get_cheapest_group_keys_order(PlannerInfo *root, double nrows,
 List *
 get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 								List *path_pathkeys,
-								List *group_pathkeys, List *group_clauses)
+								List *group_pathkeys, List *group_clauses,
+								List *aggregate_pathkeys)
 {
 	Query	   *parse = root->parse;
 	List	   *infos = NIL;
@@ -758,7 +780,10 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 
 	/* always return at least the original pathkeys/clauses */
 	info = makeNode(PathKeyInfo);
-	info->pathkeys = pathkeys;
+	if (aggregate_pathkeys != NIL)
+		info->pathkeys = list_concat_copy(pathkeys, aggregate_pathkeys);
+	else
+		info->pathkeys = pathkeys;
 	info->clauses = clauses;
 
 	infos = lappend(infos, info);
@@ -783,7 +808,10 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 									  n_preordered))
 	{
 		info = makeNode(PathKeyInfo);
-		info->pathkeys = pathkeys;
+		if (aggregate_pathkeys != NIL)
+			info->pathkeys = list_concat_copy(pathkeys, aggregate_pathkeys);
+		else
+			info->pathkeys = pathkeys;
 		info->clauses = clauses;
 
 		infos = lappend(infos, info);
@@ -822,7 +850,10 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 		 * still want to keep the keys reordered to path_pathkeys.
 		 */
 		info = makeNode(PathKeyInfo);
-		info->pathkeys = pathkeys;
+		if (aggregate_pathkeys != NIL)
+			info->pathkeys = list_concat_copy(pathkeys, aggregate_pathkeys);
+		else
+			info->pathkeys = pathkeys;
 		info->clauses = clauses;
 
 		infos = lappend(infos, info);
@@ -850,7 +881,10 @@ get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 
 		/* keep the group keys reordered to match ordering of input path */
 		info = makeNode(PathKeyInfo);
-		info->pathkeys = pathkeys;
+		if (aggregate_pathkeys != NIL)
+			info->pathkeys = list_concat_copy(pathkeys, aggregate_pathkeys);
+		else
+			info->pathkeys = pathkeys;
 		info->clauses = clauses;
 
 		infos = lappend(infos, info);
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
index e0e357960f..ab3f7abba1 100644
--- a/src/backend/optimizer/plan/planagg.c
+++ b/src/backend/optimizer/plan/planagg.c
@@ -245,7 +245,7 @@ can_minmax_aggs(PlannerInfo *root, List **context)
 	foreach(lc, root->agginfos)
 	{
 		AggInfo    *agginfo = lfirst_node(AggInfo, lc);
-		Aggref	   *aggref = agginfo->representative_aggref;
+		Aggref	   *aggref = linitial_node(Aggref, agginfo->aggrefs);
 		Oid			aggsortop;
 		TargetEntry *curTarget;
 		MinMaxAggInfo *mminfo;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 06ad856eac..46cb4d4a22 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -24,6 +24,7 @@
 #include "access/sysattr.h"
 #include "access/table.h"
 #include "access/xact.h"
+#include "catalog/pg_aggregate.h"
 #include "catalog/pg_constraint.h"
 #include "catalog/pg_inherits.h"
 #include "catalog/pg_proc.h"
@@ -3125,6 +3126,205 @@ reorder_grouping_sets(List *groupingsets, List *sortclause)
 	return result;
 }
 
+/*
+ * make_pathkeys_for_groupagg
+ *		Determine the pathkeys for the GROUP BY clause and/or any ordered
+ *		aggregates.  We expect at least one of these here.
+ *
+ * Building the pathkeys for the GROUP BY is simple.  Most of the complexity
+ * involved here comes from calculating the best pathkeys for ordered
+ * aggregates.  We define "best" as the pathkeys that suit the most number of
+ * aggregate functions.  We find these by looking at the first ORDER BY /
+ * DISTINCT aggregate and taking the pathkeys for that before searching for
+ * other aggregates that require the same or a more strict variation of the
+ * same pathkeys.  We then repeat that process for any remaining aggregates
+ * with different pathkeys and if we find another set of pathkeys that suits a
+ * larger number of aggregates then we return those pathkeys instead.
+ *
+ * *number_groupby_pathkeys gets set to the number of elemenents in the
+ * returned list that belong to the GROUP BY clause.  Any elements above this
+ * number must belong to ORDER BY / DISTINCT aggregates.
+ *
+ * When the best pathkeys are found we also mark each Aggref that can use
+ * those pathkeys as aggpresorted = true.
+ */
+static List *
+make_pathkeys_for_groupagg(PlannerInfo *root, List *groupClause, List *tlist,
+						   int *number_groupby_pathkeys)
+{
+	List	   *grouppathkeys = NIL;
+	List	   *bestpathkeys;
+	Bitmapset  *bestaggs;
+	Bitmapset  *unprocessed_aggs;
+	ListCell   *lc;
+	int			i;
+
+	Assert(groupClause != NIL || root->numOrderedAggs > 0);
+
+	if (groupClause != NIL)
+	{
+		/* no pathkeys possible if there's an unsortable GROUP BY */
+		if (!grouping_is_sortable(groupClause))
+		{
+			*number_groupby_pathkeys = 0;
+			return NIL;
+		}
+
+		grouppathkeys = make_pathkeys_for_sortclauses(root, groupClause,
+													  tlist);
+		*number_groupby_pathkeys = list_length(grouppathkeys);
+	}
+	else
+		*number_groupby_pathkeys = 0;
+
+	/*
+	 * We can't add pathkeys for ordered aggregates if there are any grouping
+	 * sets.  All handling specific to ordered aggregates must be done by the
+	 * executor in that case.
+	 */
+	if (root->numOrderedAggs == 0 || root->parse->groupingSets != NIL)
+		return grouppathkeys;
+
+	/*
+	 * Make a first pass over all AggInfos to collect a Bitmapset containing
+	 * the indexes of all AggInfos to be processed below.
+	 */
+	unprocessed_aggs = NULL;
+	foreach(lc, root->agginfos)
+	{
+		AggInfo    *agginfo = (AggInfo *) lfirst(lc);
+		Aggref	   *aggref = linitial_node(Aggref, agginfo->aggrefs);
+
+		if (AGGKIND_IS_ORDERED_SET(aggref->aggkind))
+			continue;
+
+		/* skip aggs with no DISTINCT or ORDER BY */
+		if (aggref->aggdistinct == NIL && aggref->aggorder == NIL)
+			continue;
+
+
+		unprocessed_aggs = bms_add_member(unprocessed_aggs,
+										  foreach_current_index(lc));
+	}
+
+	/*
+	 * Now process all the unprocessed_aggs to find the best set of pathkeys
+	 * for the given set of aggregates.
+	 *
+	 * On the first outer loop here 'bestaggs' will be empty.   We'll populate
+	 * this during the first loop using the pathkeys for the very first
+	 * AggInfo then taking any stronger pathkeys from any other AggInfos with
+	 * a more strict set of compatible pathkeys.  Once the outer loop is
+	 * complete, we mark off all the aggregates with compatible pathkeys then
+	 * remove those from the unprocessed_aggs and repeat the process to try to
+	 * find another set of pathkeys that are suitable for a larger number of
+	 * aggregates.  The outer loop will stop when there are not enough
+	 * unprocessed aggregates for it to be possible to find a set of pathkeys
+	 * to suit a larger number of aggregates.
+	 */
+	bestpathkeys = NIL;
+	bestaggs = NULL;
+	while (bms_num_members(unprocessed_aggs) > bms_num_members(bestaggs))
+	{
+		Bitmapset  *aggindexes = NULL;
+		List	   *currpathkeys = NIL;
+
+		i = -1;
+		while ((i = bms_next_member(unprocessed_aggs, i)) >= 0)
+		{
+			AggInfo    *agginfo = list_nth(root->agginfos, i);
+			Aggref	   *aggref = linitial_node(Aggref, agginfo->aggrefs);
+			List	   *sortlist;
+
+			if (aggref->aggdistinct != NIL)
+				sortlist = aggref->aggdistinct;
+			else
+				sortlist = aggref->aggorder;
+
+			/*
+			 * When not set yet, take the pathkeys from the first unprocessed
+			 * aggregate.
+			 */
+			if (currpathkeys == NIL)
+			{
+				currpathkeys = make_pathkeys_for_sortclauses(root, sortlist,
+															 aggref->args);
+
+				/* include the GROUP BY pathkeys, if they exist */
+				if (grouppathkeys != NIL)
+					currpathkeys = append_pathkeys(list_copy(grouppathkeys),
+												   currpathkeys);
+
+				/* record that we found pathkeys for this aggregate */
+				aggindexes = bms_add_member(aggindexes, i);
+			}
+			else
+			{
+				List	   *pathkeys;
+
+				/* now look for a stronger set of matching pathkeys */
+				pathkeys = make_pathkeys_for_sortclauses(root, sortlist,
+														 aggref->args);
+
+				/* include the GROUP BY pathkeys, if they exist */
+				if (grouppathkeys != NIL)
+					pathkeys = append_pathkeys(list_copy(grouppathkeys),
+											   pathkeys);
+
+				if (pathkeys_contained_in(currpathkeys, pathkeys))
+				{
+					/* pathkeys are stronger, use these ones instead */
+					currpathkeys = pathkeys;
+
+					/* record that we found pathkeys for this aggregate */
+					aggindexes = bms_add_member(aggindexes, i);
+				}
+			}
+		}
+
+		/* remove the aggregates that we've just processed */
+		unprocessed_aggs = bms_del_members(unprocessed_aggs, aggindexes);
+
+		/*
+		 * If this pass included more aggregates than the previous best then
+		 * use these ones as the best set.
+		 */
+		if (bms_num_members(aggindexes) > bms_num_members(bestaggs))
+		{
+			bestaggs = aggindexes;
+			bestpathkeys = currpathkeys;
+		}
+	}
+
+	/*
+	 * Now that we've found the best set of aggregates we can set the
+	 * presorted flag to indicate to the executor that it needn't bother
+	 * performing a sort for these Aggrefs.
+	 */
+	i = -1;
+	while ((i = bms_next_member(bestaggs, i)) >= 0)
+	{
+		AggInfo    *agginfo = list_nth(root->agginfos, i);
+
+		foreach(lc, agginfo->aggrefs)
+		{
+			Aggref	   *aggref = lfirst_node(Aggref, lc);
+
+			aggref->aggpresorted = true;
+		}
+	}
+
+	/*
+	 * bestpathkeys includes the GROUP BY pathkeys, so if we found any ordered
+	 * aggregates, then return bestpathkeys, otherwise return the
+	 * grouppathkeys.
+	 */
+	if (bestpathkeys != NIL)
+		return bestpathkeys;
+
+	return grouppathkeys;
+}
+
 /*
  * Compute query_pathkeys and other pathkeys during plan generation
  */
@@ -3137,18 +3337,19 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 	List	   *activeWindows = qp_extra->activeWindows;
 
 	/*
-	 * Calculate pathkeys that represent grouping/ordering requirements.  The
-	 * sortClause is certainly sort-able, but GROUP BY and DISTINCT might not
-	 * be, in which case we just leave their pathkeys empty.
+	 * Calculate pathkeys that represent grouping/ordering and/or ordered
+	 * aggregate requirements.
 	 */
-	if (qp_extra->groupClause &&
-		grouping_is_sortable(qp_extra->groupClause))
-		root->group_pathkeys =
-			make_pathkeys_for_sortclauses(root,
-										  qp_extra->groupClause,
-										  tlist);
+	if (qp_extra->groupClause != NIL || root->numOrderedAggs > 0)
+		root->group_pathkeys = make_pathkeys_for_groupagg(root,
+														  qp_extra->groupClause,
+														  tlist,
+														  &root->num_groupby_pathkeys);
 	else
+	{
 		root->group_pathkeys = NIL;
+		root->num_groupby_pathkeys = 0;
+	}
 
 	/* We consider only the first (bottom) window in pathkeys logic */
 	if (activeWindows != NIL)
@@ -6222,6 +6423,26 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 
 	if (can_sort)
 	{
+		List	   *group_pathkeys;
+		List	   *orderAggPathkeys;
+		int			numAggPathkeys;
+
+		numAggPathkeys = list_length(root->group_pathkeys) -
+						 root->num_groupby_pathkeys;
+
+		if (numAggPathkeys > 0)
+		{
+			group_pathkeys = list_copy_head(root->group_pathkeys,
+											root->num_groupby_pathkeys);
+			orderAggPathkeys = list_copy_tail(root->group_pathkeys,
+											  root->num_groupby_pathkeys);
+		}
+		else
+		{
+			group_pathkeys = root->group_pathkeys;
+			orderAggPathkeys = NIL;
+		}
+
 		/*
 		 * Use any available suitably-sorted path as input, and also consider
 		 * sorting the cheapest-total path.
@@ -6234,7 +6455,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 
 			List	   *pathkey_orderings = NIL;
 
-			List	   *group_pathkeys = root->group_pathkeys;
 			List	   *group_clauses = parse->groupClause;
 
 			/* generate alternative group orderings that might be useful */
@@ -6242,7 +6462,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 																path->rows,
 																path->pathkeys,
 																group_pathkeys,
-																group_clauses);
+																group_clauses,
+																orderAggPathkeys);
 
 			Assert(list_length(pathkey_orderings) > 0);
 
@@ -6414,7 +6635,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 																	path->rows,
 																	path->pathkeys,
 																	group_pathkeys,
-																	group_clauses);
+																	group_clauses,
+																	orderAggPathkeys);
 
 				Assert(list_length(pathkey_orderings) > 0);
 
@@ -6717,6 +6939,24 @@ create_partial_grouping_paths(PlannerInfo *root,
 
 	if (can_sort && cheapest_total_path != NULL)
 	{
+		List	   *group_pathkeys;
+		List	   *orderAggPathkeys;
+		int			numAggPathkeys;
+
+		numAggPathkeys = list_length(root->group_pathkeys) -
+						 root->num_groupby_pathkeys;
+
+		if (numAggPathkeys > 0)
+		{
+			group_pathkeys = list_copy_head(root->group_pathkeys, root->num_groupby_pathkeys);
+			orderAggPathkeys = list_copy_tail(root->group_pathkeys, root->num_groupby_pathkeys);
+		}
+		else
+		{
+			group_pathkeys = root->group_pathkeys;
+			orderAggPathkeys = NIL;
+		}
+
 		/* This should have been checked previously */
 		Assert(parse->hasAggs || parse->groupClause);
 
@@ -6729,10 +6969,7 @@ create_partial_grouping_paths(PlannerInfo *root,
 			ListCell   *lc2;
 			Path	   *path = (Path *) lfirst(lc);
 			Path	   *path_save = path;
-
 			List	   *pathkey_orderings = NIL;
-
-			List	   *group_pathkeys = root->group_pathkeys;
 			List	   *group_clauses = parse->groupClause;
 
 			/* generate alternative group orderings that might be useful */
@@ -6740,7 +6977,8 @@ create_partial_grouping_paths(PlannerInfo *root,
 																path->rows,
 																path->pathkeys,
 																group_pathkeys,
-																group_clauses);
+																group_clauses,
+																orderAggPathkeys);
 
 			Assert(list_length(pathkey_orderings) > 0);
 
@@ -6856,16 +7094,31 @@ create_partial_grouping_paths(PlannerInfo *root,
 
 	if (can_sort && cheapest_partial_path != NULL)
 	{
+		List	   *group_pathkeys;
+		List	   *orderAggPathkeys;
+		int			numAggPathkeys;
+
+		numAggPathkeys = list_length(root->group_pathkeys) -
+						 root->num_groupby_pathkeys;
+
+		if (numAggPathkeys > 0)
+		{
+			group_pathkeys = list_copy_head(root->group_pathkeys, root->num_groupby_pathkeys);
+			orderAggPathkeys = list_copy_tail(root->group_pathkeys, root->num_groupby_pathkeys);
+		}
+		else
+		{
+			group_pathkeys = root->group_pathkeys;
+			orderAggPathkeys = NIL;
+		}
+
 		/* Similar to above logic, but for partial paths. */
 		foreach(lc, input_rel->partial_pathlist)
 		{
 			ListCell   *lc2;
 			Path	   *path = (Path *) lfirst(lc);
 			Path	   *path_original = path;
-
 			List	   *pathkey_orderings = NIL;
-
-			List	   *group_pathkeys = root->group_pathkeys;
 			List	   *group_clauses = parse->groupClause;
 
 			/* generate alternative group orderings that might be useful */
@@ -6873,7 +7126,8 @@ create_partial_grouping_paths(PlannerInfo *root,
 																path->rows,
 																path->pathkeys,
 																group_pathkeys,
-																group_clauses);
+																group_clauses,
+																orderAggPathkeys);
 
 			Assert(list_length(pathkey_orderings) > 0);
 
diff --git a/src/backend/optimizer/prep/prepagg.c b/src/backend/optimizer/prep/prepagg.c
index 5b12937ead..da89b55402 100644
--- a/src/backend/optimizer/prep/prepagg.c
+++ b/src/backend/optimizer/prep/prepagg.c
@@ -225,6 +225,7 @@ preprocess_aggref(Aggref *aggref, PlannerInfo *root)
 	{
 		AggInfo    *agginfo = list_nth_node(AggInfo, root->agginfos, aggno);
 
+		agginfo->aggrefs = lappend(agginfo->aggrefs, aggref);
 		transno = agginfo->transno;
 	}
 	else
@@ -232,7 +233,7 @@ preprocess_aggref(Aggref *aggref, PlannerInfo *root)
 		AggInfo    *agginfo = makeNode(AggInfo);
 
 		agginfo->finalfn_oid = aggfinalfn;
-		agginfo->representative_aggref = aggref;
+		agginfo->aggrefs = list_make1(aggref);
 		agginfo->shareable = shareable;
 
 		aggno = list_length(root->agginfos);
@@ -386,7 +387,7 @@ find_compatible_agg(PlannerInfo *root, Aggref *newagg,
 
 		aggno++;
 
-		existingRef = agginfo->representative_aggref;
+		existingRef = linitial_node(Aggref, agginfo->aggrefs);
 
 		/* all of the following must be the same or it's no match */
 		if (newagg->inputcollid != existingRef->inputcollid ||
@@ -648,7 +649,7 @@ get_agg_clause_costs(PlannerInfo *root, AggSplit aggsplit, AggClauseCosts *costs
 	foreach(lc, root->agginfos)
 	{
 		AggInfo    *agginfo = lfirst_node(AggInfo, lc);
-		Aggref	   *aggref = agginfo->representative_aggref;
+		Aggref	   *aggref = linitial_node(Aggref, agginfo->aggrefs);
 
 		/*
 		 * Add the appropriate component function execution costs to
diff --git a/src/include/executor/execExpr.h b/src/include/executor/execExpr.h
index 1e3f1bbee8..0739b389f3 100644
--- a/src/include/executor/execExpr.h
+++ b/src/include/executor/execExpr.h
@@ -258,6 +258,8 @@ typedef enum ExprEvalOp
 	EEOP_AGG_PLAIN_TRANS_INIT_STRICT_BYREF,
 	EEOP_AGG_PLAIN_TRANS_STRICT_BYREF,
 	EEOP_AGG_PLAIN_TRANS_BYREF,
+	EEOP_AGG_PRESORTED_DISTINCT_SINGLE,
+	EEOP_AGG_PRESORTED_DISTINCT_MULTI,
 	EEOP_AGG_ORDERED_TRANS_DATUM,
 	EEOP_AGG_ORDERED_TRANS_TUPLE,
 
@@ -659,6 +661,17 @@ typedef struct ExprEvalStep
 			int			jumpnull;
 		}			agg_plain_pergroup_nullcheck;
 
+		/* for EEOP_AGG_PRESORTED_DISTINCT_{SINGLE,MULTI} */
+		struct
+		{
+			AggStatePerTrans pertrans;
+			ExprContext *aggcontext;
+			int			setno;
+			int			transno;
+			int			setoff;
+			int			jumpdistinct;
+		}			agg_presorted_distinctcheck;
+
 		/* for EEOP_AGG_PLAIN_TRANS_[INIT_][STRICT_]{BYVAL,BYREF} */
 		/* for EEOP_AGG_ORDERED_TRANS_{DATUM,TUPLE} */
 		struct
@@ -868,6 +881,10 @@ extern void ExecAggInitGroup(AggState *aggstate, AggStatePerTrans pertrans, AggS
 extern Datum ExecAggTransReparent(AggState *aggstate, AggStatePerTrans pertrans,
 								  Datum newValue, bool newValueIsNull,
 								  Datum oldValue, bool oldValueIsNull);
+extern bool ExecEvalPreOrderedDistinctSingle(AggState *aggstate,
+											 AggStatePerTrans pertrans);
+extern bool ExecEvalPreOrderedDistinctMulti(AggState *aggstate,
+											AggStatePerTrans pertrans);
 extern void ExecEvalAggOrderedTransDatum(ExprState *state, ExprEvalStep *op,
 										 ExprContext *econtext);
 extern void ExecEvalAggOrderedTransTuple(ExprState *state, ExprEvalStep *op,
diff --git a/src/include/executor/nodeAgg.h b/src/include/executor/nodeAgg.h
index 4d1bd92999..d46ff98c6d 100644
--- a/src/include/executor/nodeAgg.h
+++ b/src/include/executor/nodeAgg.h
@@ -48,6 +48,12 @@ typedef struct AggStatePerTransData
 	 */
 	bool		aggshared;
 
+	/*
+	 * True for ORDER BY and DISTINCT aggregates that are not
+	 * Aggref->aggpresorted.
+	 */
+	bool		aggsortrequired;
+
 	/*
 	 * Number of aggregated input columns.  This includes ORDER BY expressions
 	 * in both the plain-agg and ordered-set cases.  Ordered-set direct args
@@ -136,6 +142,9 @@ typedef struct AggStatePerTransData
 	TupleTableSlot *sortslot;	/* current input tuple */
 	TupleTableSlot *uniqslot;	/* used for multi-column DISTINCT */
 	TupleDesc	sortdesc;		/* descriptor of input tuples */
+	Datum		lastdatum;		/* used for single-column DISTINCT */
+	bool		lastisnull;		/* used for single-column DISTINCT */
+	bool		haslast;		/* got a last value for DISTINCT check */
 
 	/*
 	 * These values are working state that is initialized at the start of an
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index e650af5ff2..53ef881792 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -359,6 +359,14 @@ struct PlannerInfo
 
 	/* groupClause pathkeys, if any */
 	List	   *group_pathkeys;
+
+	/*
+	 * The number of elements in the group_pathkeys list which belong to the
+	 * GROUP BY clause.  Additional ones belong to ORDER BY / DISTINCT
+	 * aggregates.
+	 */
+	int			num_groupby_pathkeys;
+
 	/* pathkeys of bottom window, if any */
 	List	   *window_pathkeys;
 	/* distinctClause pathkeys, if any */
@@ -3126,12 +3134,12 @@ typedef struct AggInfo
 	NodeTag		type;
 
 	/*
-	 * Link to an Aggref expr this state value is for.
+	 * List of Aggref exprs that this state value is for.
 	 *
-	 * There can be multiple identical Aggref's sharing the same per-agg. This
-	 * points to the first one of them.
+	 * There will always be at least one, but there can be multiple identical
+	 * Aggref's sharing the same per-agg.
 	 */
-	Aggref	   *representative_aggref;
+	List	   *aggrefs;
 
 	/* Transition state number for this aggregate */
 	int			transno;
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 1fc2fbffa3..854ae4ba5d 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -357,6 +357,10 @@ typedef struct Param
  * replaced with a single argument representing the partial-aggregate
  * transition values.
  *
+ * aggpresorted is set by the query planner for ORDER BY and DISTINCT
+ * aggregates where the plan chosen provides presorted input for this
+ * aggregate during execution
+ *
  * aggsplit indicates the expected partial-aggregation mode for the Aggref's
  * parent plan node.  It's always set to AGGSPLIT_SIMPLE in the parser, but
  * the planner might change it to something else.  We use this mainly as
@@ -422,6 +426,9 @@ typedef struct Aggref
 	/* aggregate kind (see pg_aggregate.h) */
 	char		aggkind;
 
+	/* aggregate input already sorted */
+	bool		aggpresorted pg_node_attr(equal_ignore);
+
 	/* > 0 if agg belongs to outer query */
 	Index		agglevelsup;
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 54ab709c67..d11cdac7f8 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -208,7 +208,8 @@ extern int	group_keys_reorder_by_pathkeys(List *pathkeys,
 										   List **group_clauses);
 extern List *get_useful_group_keys_orderings(PlannerInfo *root, double nrows,
 											 List *path_pathkeys,
-											 List *group_pathkeys, List *group_clauses);
+											 List *group_pathkeys, List *group_clauses,
+											 List *aggregate_pathkeys);
 extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
 											Relids required_outer,
 											CostSelector cost_criterion,
@@ -255,6 +256,7 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root,
 									   RelOptInfo *rel,
 									   List *pathkeys);
 extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern List *append_pathkeys(List *target, List *source);
 extern PathKey *make_canonical_pathkey(PlannerInfo *root,
 									   EquivalenceClass *eclass, Oid opfamily,
 									   int strategy, bool nulls_first);
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 601047fa3d..e141919600 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1392,6 +1392,84 @@ ERROR:  column "t1.f1" must appear in the GROUP BY clause or be used in an aggre
 LINE 1: select t1.f1 from t1 left join t2 using (f1) group by f1;
                ^
 drop table t1, t2;
+--
+-- Test planner's selection of pathkeys for ORDER BY aggregates
+--
+-- Ensure we order by four.  This suits the most aggregate functions.
+explain (costs off)
+select sum(two order by two),max(four order by four), min(four order by four)
+from tenk1;
+          QUERY PLAN           
+-------------------------------
+ Aggregate
+   ->  Sort
+         Sort Key: four
+         ->  Seq Scan on tenk1
+(4 rows)
+
+-- Ensure we order by two.  It's a tie between ordering by two and four but
+-- we tiebreak on the aggregate's position.
+explain (costs off)
+select
+  sum(two order by two), max(four order by four),
+  min(four order by four), max(two order by two)
+from tenk1;
+          QUERY PLAN           
+-------------------------------
+ Aggregate
+   ->  Sort
+         Sort Key: two
+         ->  Seq Scan on tenk1
+(4 rows)
+
+-- Similar to above, but tiebreak on ordering by four
+explain (costs off)
+select
+  max(four order by four), sum(two order by two),
+  min(four order by four), max(two order by two)
+from tenk1;
+          QUERY PLAN           
+-------------------------------
+ Aggregate
+   ->  Sort
+         Sort Key: four
+         ->  Seq Scan on tenk1
+(4 rows)
+
+-- Ensure this one orders by ten since there are 3 aggregates that require ten
+-- vs two that suit two and four.
+explain (costs off)
+select
+  max(four order by four), sum(two order by two),
+  min(four order by four), max(two order by two),
+  sum(ten order by ten), min(ten order by ten), max(ten order by ten)
+from tenk1;
+          QUERY PLAN           
+-------------------------------
+ Aggregate
+   ->  Sort
+         Sort Key: ten
+         ->  Seq Scan on tenk1
+(4 rows)
+
+-- Try a case involving a GROUP BY clause where the GROUP BY column is also
+-- part of an aggregate's ORDER BY clause.  We want a sort order that works
+-- for the GROUP BY and first and last aggregate.
+explain (costs off)
+select
+  sum(unique1 order by ten, two), sum(unique1 order by four),
+  sum(unique1 order by two, four)
+from tenk1
+group by ten;
+            QUERY PLAN            
+----------------------------------
+ GroupAggregate
+   Group Key: ten
+   ->  Sort
+         Sort Key: ten, two, four
+         ->  Seq Scan on tenk1
+(5 rows)
+
 --
 -- Test combinations of DISTINCT and/or ORDER BY
 --
@@ -2263,8 +2341,8 @@ NOTICE:  avg_transfn called with 3
 -- shouldn't share states due to the distinctness not matching.
 select my_avg(distinct one),my_sum(one) from (values(1),(3)) t(one);
 NOTICE:  avg_transfn called with 1
-NOTICE:  avg_transfn called with 3
 NOTICE:  avg_transfn called with 1
+NOTICE:  avg_transfn called with 3
 NOTICE:  avg_transfn called with 3
  my_avg | my_sum 
 --------+--------
diff --git a/src/test/regress/expected/partition_aggregate.out b/src/test/regress/expected/partition_aggregate.out
index a08a3825ff..4b41ccf1aa 100644
--- a/src/test/regress/expected/partition_aggregate.out
+++ b/src/test/regress/expected/partition_aggregate.out
@@ -367,17 +367,17 @@ SELECT c, sum(b order by a) FROM pagg_tab GROUP BY c ORDER BY 1, 2;
          ->  GroupAggregate
                Group Key: pagg_tab.c
                ->  Sort
-                     Sort Key: pagg_tab.c
+                     Sort Key: pagg_tab.c, pagg_tab.a
                      ->  Seq Scan on pagg_tab_p1 pagg_tab
          ->  GroupAggregate
                Group Key: pagg_tab_1.c
                ->  Sort
-                     Sort Key: pagg_tab_1.c
+                     Sort Key: pagg_tab_1.c, pagg_tab_1.a
                      ->  Seq Scan on pagg_tab_p2 pagg_tab_1
          ->  GroupAggregate
                Group Key: pagg_tab_2.c
                ->  Sort
-                     Sort Key: pagg_tab_2.c
+                     Sort Key: pagg_tab_2.c, pagg_tab_2.a
                      ->  Seq Scan on pagg_tab_p3 pagg_tab_2
 (18 rows)
 
@@ -948,34 +948,36 @@ SET max_parallel_workers_per_gather TO 2;
 -- is not partial agg safe.
 EXPLAIN (COSTS OFF)
 SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) < 3 ORDER BY 1, 2, 3;
-                                      QUERY PLAN                                      
---------------------------------------------------------------------------------------
- Sort
-   Sort Key: pagg_tab_ml.a, (sum(pagg_tab_ml.b)), (array_agg(DISTINCT pagg_tab_ml.c))
-   ->  Append
-         ->  GroupAggregate
-               Group Key: pagg_tab_ml.a
-               Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
-               ->  Sort
-                     Sort Key: pagg_tab_ml.a
-                     ->  Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
-         ->  GroupAggregate
-               Group Key: pagg_tab_ml_2.a
-               Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
-               ->  Sort
-                     Sort Key: pagg_tab_ml_2.a
-                     ->  Append
-                           ->  Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
-                           ->  Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
-         ->  GroupAggregate
-               Group Key: pagg_tab_ml_5.a
-               Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
-               ->  Sort
-                     Sort Key: pagg_tab_ml_5.a
-                     ->  Append
-                           ->  Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
-                           ->  Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
-(25 rows)
+                                         QUERY PLAN                                         
+--------------------------------------------------------------------------------------------
+ Gather Merge
+   Workers Planned: 2
+   ->  Sort
+         Sort Key: pagg_tab_ml.a, (sum(pagg_tab_ml.b)), (array_agg(DISTINCT pagg_tab_ml.c))
+         ->  Parallel Append
+               ->  GroupAggregate
+                     Group Key: pagg_tab_ml.a
+                     Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
+                     ->  Sort
+                           Sort Key: pagg_tab_ml.a, pagg_tab_ml.c
+                           ->  Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
+               ->  GroupAggregate
+                     Group Key: pagg_tab_ml_5.a
+                     Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
+                     ->  Sort
+                           Sort Key: pagg_tab_ml_5.a, pagg_tab_ml_5.c
+                           ->  Append
+                                 ->  Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
+                                 ->  Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
+               ->  GroupAggregate
+                     Group Key: pagg_tab_ml_2.a
+                     Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
+                     ->  Sort
+                           Sort Key: pagg_tab_ml_2.a, pagg_tab_ml_2.c
+                           ->  Append
+                                 ->  Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
+                                 ->  Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
+(27 rows)
 
 SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) < 3 ORDER BY 1, 2, 3;
  a  | sum  |  array_agg  | count 
@@ -994,32 +996,34 @@ SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HA
 -- Without ORDER BY clause, to test Gather at top-most path
 EXPLAIN (COSTS OFF)
 SELECT a, sum(b), array_agg(distinct c), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) < 3;
-                             QUERY PLAN                              
----------------------------------------------------------------------
- Append
-   ->  GroupAggregate
-         Group Key: pagg_tab_ml.a
-         Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
-         ->  Sort
-               Sort Key: pagg_tab_ml.a
-               ->  Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
-   ->  GroupAggregate
-         Group Key: pagg_tab_ml_2.a
-         Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
-         ->  Sort
-               Sort Key: pagg_tab_ml_2.a
-               ->  Append
-                     ->  Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
-                     ->  Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
-   ->  GroupAggregate
-         Group Key: pagg_tab_ml_5.a
-         Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
-         ->  Sort
-               Sort Key: pagg_tab_ml_5.a
-               ->  Append
-                     ->  Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
-                     ->  Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
-(23 rows)
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Gather
+   Workers Planned: 2
+   ->  Parallel Append
+         ->  GroupAggregate
+               Group Key: pagg_tab_ml.a
+               Filter: (avg(pagg_tab_ml.b) < '3'::numeric)
+               ->  Sort
+                     Sort Key: pagg_tab_ml.a, pagg_tab_ml.c
+                     ->  Seq Scan on pagg_tab_ml_p1 pagg_tab_ml
+         ->  GroupAggregate
+               Group Key: pagg_tab_ml_5.a
+               Filter: (avg(pagg_tab_ml_5.b) < '3'::numeric)
+               ->  Sort
+                     Sort Key: pagg_tab_ml_5.a, pagg_tab_ml_5.c
+                     ->  Append
+                           ->  Seq Scan on pagg_tab_ml_p3_s1 pagg_tab_ml_5
+                           ->  Seq Scan on pagg_tab_ml_p3_s2 pagg_tab_ml_6
+         ->  GroupAggregate
+               Group Key: pagg_tab_ml_2.a
+               Filter: (avg(pagg_tab_ml_2.b) < '3'::numeric)
+               ->  Sort
+                     Sort Key: pagg_tab_ml_2.a, pagg_tab_ml_2.c
+                     ->  Append
+                           ->  Seq Scan on pagg_tab_ml_p2_s1 pagg_tab_ml_2
+                           ->  Seq Scan on pagg_tab_ml_p2_s2 pagg_tab_ml_3
+(25 rows)
 
 -- Full aggregation at level 1 as GROUP BY clause matches with PARTITION KEY
 -- for level 1 only. For subpartitions, GROUP BY clause does not match with
diff --git a/src/test/regress/expected/sqljson.out b/src/test/regress/expected/sqljson.out
index bdd0969a50..748dfdb04d 100644
--- a/src/test/regress/expected/sqljson.out
+++ b/src/test/regress/expected/sqljson.out
@@ -866,14 +866,14 @@ FROM
 	(VALUES (NULL), (3), (1), (NULL), (NULL), (5), (2), (4), (NULL)) foo(bar);
   json_arrayagg  |  json_arrayagg  |  json_arrayagg  |  json_arrayagg  |              json_arrayagg              |              json_arrayagg              |  json_arrayagg  |                                                      json_arrayagg                                                       | json_arrayagg |            json_arrayagg             
 -----------------+-----------------+-----------------+-----------------+-----------------------------------------+-----------------------------------------+-----------------+--------------------------------------------------------------------------------------------------------------------------+---------------+--------------------------------------
- [3, 1, 5, 2, 4] | [3, 1, 5, 2, 4] | [3, 1, 5, 2, 4] | [3, 1, 5, 2, 4] | [null, 3, 1, null, null, 5, 2, 4, null] | [null, 3, 1, null, null, 5, 2, 4, null] | [{"bar":null}, +| [{"bar": null}, {"bar": 3}, {"bar": 1}, {"bar": null}, {"bar": null}, {"bar": 5}, {"bar": 2}, {"bar": 4}, {"bar": null}] | [{"bar":3},  +| [{"bar": 3}, {"bar": 4}, {"bar": 5}]
-                 |                 |                 |                 |                                         |                                         |  {"bar":3},    +|                                                                                                                          |  {"bar":4},  +| 
-                 |                 |                 |                 |                                         |                                         |  {"bar":1},    +|                                                                                                                          |  {"bar":5}]   | 
+ [1, 2, 3, 4, 5] | [1, 2, 3, 4, 5] | [1, 2, 3, 4, 5] | [1, 2, 3, 4, 5] | [1, 2, 3, 4, 5, null, null, null, null] | [1, 2, 3, 4, 5, null, null, null, null] | [{"bar":1},    +| [{"bar": 1}, {"bar": 2}, {"bar": 3}, {"bar": 4}, {"bar": 5}, {"bar": null}, {"bar": null}, {"bar": null}, {"bar": null}] | [{"bar":3},  +| [{"bar": 3}, {"bar": 4}, {"bar": 5}]
+                 |                 |                 |                 |                                         |                                         |  {"bar":2},    +|                                                                                                                          |  {"bar":4},  +| 
+                 |                 |                 |                 |                                         |                                         |  {"bar":3},    +|                                                                                                                          |  {"bar":5}]   | 
+                 |                 |                 |                 |                                         |                                         |  {"bar":4},    +|                                                                                                                          |               | 
+                 |                 |                 |                 |                                         |                                         |  {"bar":5},    +|                                                                                                                          |               | 
+                 |                 |                 |                 |                                         |                                         |  {"bar":null}, +|                                                                                                                          |               | 
                  |                 |                 |                 |                                         |                                         |  {"bar":null}, +|                                                                                                                          |               | 
                  |                 |                 |                 |                                         |                                         |  {"bar":null}, +|                                                                                                                          |               | 
-                 |                 |                 |                 |                                         |                                         |  {"bar":5},    +|                                                                                                                          |               | 
-                 |                 |                 |                 |                                         |                                         |  {"bar":2},    +|                                                                                                                          |               | 
-                 |                 |                 |                 |                                         |                                         |  {"bar":4},    +|                                                                                                                          |               | 
                  |                 |                 |                 |                                         |                                         |  {"bar":null}]  |                                                                                                                          |               | 
 (1 row)
 
diff --git a/src/test/regress/expected/tuplesort.out b/src/test/regress/expected/tuplesort.out
index 418f296a3f..ef79574ecf 100644
--- a/src/test/regress/expected/tuplesort.out
+++ b/src/test/regress/expected/tuplesort.out
@@ -622,15 +622,17 @@ EXPLAIN (COSTS OFF) :qry;
          ->  GroupAggregate
                Group Key: a.col12
                Filter: (count(*) > 1)
-               ->  Merge Join
-                     Merge Cond: (a.col12 = b.col12)
-                     ->  Sort
-                           Sort Key: a.col12 DESC
-                           ->  Seq Scan on test_mark_restore a
-                     ->  Sort
-                           Sort Key: b.col12 DESC
-                           ->  Seq Scan on test_mark_restore b
-(14 rows)
+               ->  Sort
+                     Sort Key: a.col12 DESC, a.col1
+                     ->  Merge Join
+                           Merge Cond: (a.col12 = b.col12)
+                           ->  Sort
+                                 Sort Key: a.col12
+                                 ->  Seq Scan on test_mark_restore a
+                           ->  Sort
+                                 Sort Key: b.col12
+                                 ->  Seq Scan on test_mark_restore b
+(16 rows)
 
 :qry;
  col12 | count | count | count | count | count 
@@ -658,15 +660,17 @@ EXPLAIN (COSTS OFF) :qry;
          ->  GroupAggregate
                Group Key: a.col12
                Filter: (count(*) > 1)
-               ->  Merge Join
-                     Merge Cond: (a.col12 = b.col12)
-                     ->  Sort
-                           Sort Key: a.col12 DESC
-                           ->  Seq Scan on test_mark_restore a
-                     ->  Sort
-                           Sort Key: b.col12 DESC
-                           ->  Seq Scan on test_mark_restore b
-(14 rows)
+               ->  Sort
+                     Sort Key: a.col12 DESC, a.col1
+                     ->  Merge Join
+                           Merge Cond: (a.col12 = b.col12)
+                           ->  Sort
+                                 Sort Key: a.col12
+                                 ->  Seq Scan on test_mark_restore a
+                           ->  Sort
+                                 Sort Key: b.col12
+                                 ->  Seq Scan on test_mark_restore b
+(16 rows)
 
 :qry;
  col12 | count | count | count | count | count 
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index c6e0d7ba2b..d719cd1836 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -503,6 +503,49 @@ select t1.f1 from t1 left join t2 using (f1) group by f1;
 
 drop table t1, t2;
 
+--
+-- Test planner's selection of pathkeys for ORDER BY aggregates
+--
+
+-- Ensure we order by four.  This suits the most aggregate functions.
+explain (costs off)
+select sum(two order by two),max(four order by four), min(four order by four)
+from tenk1;
+
+-- Ensure we order by two.  It's a tie between ordering by two and four but
+-- we tiebreak on the aggregate's position.
+explain (costs off)
+select
+  sum(two order by two), max(four order by four),
+  min(four order by four), max(two order by two)
+from tenk1;
+
+-- Similar to above, but tiebreak on ordering by four
+explain (costs off)
+select
+  max(four order by four), sum(two order by two),
+  min(four order by four), max(two order by two)
+from tenk1;
+
+-- Ensure this one orders by ten since there are 3 aggregates that require ten
+-- vs two that suit two and four.
+explain (costs off)
+select
+  max(four order by four), sum(two order by two),
+  min(four order by four), max(two order by two),
+  sum(ten order by ten), min(ten order by ten), max(ten order by ten)
+from tenk1;
+
+-- Try a case involving a GROUP BY clause where the GROUP BY column is also
+-- part of an aggregate's ORDER BY clause.  We want a sort order that works
+-- for the GROUP BY and first and last aggregate.
+explain (costs off)
+select
+  sum(unique1 order by ten, two), sum(unique1 order by four),
+  sum(unique1 order by two, four)
+from tenk1
+group by ten;
+
 --
 -- Test combinations of DISTINCT and/or ORDER BY
 --
-- 
2.35.1.windows.2

---

From: David Rowley <[email-masked]>
Date: Fri, 22 Jul 2022 16:00:15 +1200

> to tune the behavior to what is desirable.

I've now looked into this issue. With the patched code, the remote
aggregate path loses out in add_path() due to the fact that the local
aggregate path compares fuzzily the same as the remote aggregate path.
Since the local aggregate path is now fetching the rows from the
foreign server with a SQL query containing an ORDER BY clause (per my
change to query_pathkeys being picked up in
get_useful_pathkeys_for_relation()), add_path now prefers that path
due to it having pathkeys and the remote aggregate query not having
any (PATHKEYS_BETTER2).

It seems what's going on is that quite simply the default
fdw_tuple_cost is unrealistically low. Let's look.

#define DEFAULT_FDW_TUPLE_COST 0.01

Which is even lower than DEFAULT_PARALLEL_TUPLE_COST (0.1) and the
same as cpu_tuple_cost!

After some debugging, I see add_path() switches to the, seemingly
better, remote aggregate plan again if I multiple fdw_tuple_cost by
28. Anything below that sticks to the (inferior) local aggregate plan.

There's also another problem going on that would make that situation
better. The query planner expects the following query to produce 6
rows:

SELECT array_agg("C 1" ORDER BY "C 1" USING OPERATOR(public.<^) NULLS
LAST), c2 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND ((c2 = 6)) GROUP
BY c2;

You might expect the planner to think there'd just be 1 row due to the
"c2 = 6" and "GROUP BY c2", but it thinks there will be more than
that. If estimate_num_groups() knew about EquivalenceClasses and
checked ec_has_const, then it might be able to do better, but it
doesn't, so:

GroupAggregate  (cost=11.67..11.82 rows=6 width=36)

If I force that estimate to be 1 row instead of 6, then I only need a
fdw_tuple_cost to be 12 times the default to get it to switch to the
remote aggregate plan.

I think we should likely just patch master and change
DEFAULT_FDW_TUPLE_COST to at the very least 0.2, which is 20x higher
than today's setting. I'd be open to a much higher setting such as 0.5
(50x).

David

---

From: Richard Guo <[email-masked]>
Date: Fri, 22 Jul 2022 17:33:24 +0800

> more making copies of Lists than I'd like.

We may need to do more checks when adding members to 'aggindexes' to
record we've found pathkeys for an aggregate, because 'currpathkeys' may
include pathkeys for some latter aggregates. I can see this problem with
the query below:

    select max(b order by b), max(a order by a) from t group by a;

When processing the first aggregate, we compose the 'currpathkeys' as
{a, b} and mark this aggregate in 'aggindexes'. When it comes to the
second aggregate, we compose its pathkeys as {a} and decide that it is
not stronger than 'currpathkeys'. So the second aggregate is not
recorded in 'aggindexes'. As a result, we fail to mark aggpresorted for
the second aggregate.

Thanks
Richard

---

From: David Rowley <[email-masked]>
Date: Tue, 26 Jul 2022 11:38:44 +1200

On Fri, 22 Jul 2022 at 21:33, Richard Guo <[email-masked]> wrote:
> I can see this problem with
> the query below:
>

Yeah, you're right. I have a missing check to see if currpathkeys are
better than the pathkeys for the current aggregate. In your example
case we'd have still processed the 2nd aggregate the old way instead
of realising we could take the new pre-sorted path for faster
processing.

I've adjusted that in the attached to make it properly include the
case where currpathkeys are better.

Thanks for the review.

David
From 1ebfac68080b10181086b4c9c9dcb3e3e1582cdb Mon Sep 17 00:00:00 2001
From: David Rowley <[email-masked]>
Date: Mon, 3 May 2021 16:31:29 +1200
Subject: [PATCH v8] Add planner support for ORDER BY aggregates

 src/backend/executor/execExpr.c               |  52 ++-
 src/backend/optimizer/plan/planner.c          | 306 ++++++++++++++++--
 20 files changed, 845 insertions(+), 144 deletions(-)

 
 
 -- Cleanup
 
 			/*

+				/*
 
 		/*

 
+/*

 
 	/*

 
+/*
+ * append_pathkeys

 

 
index 06ad856eac..2f7e5e2fd2 100644
@@ -3125,6 +3126,217 @@ reorder_grouping_sets(List *groupingsets, List *sortclause)
 	return result;
 }
 
+/*
+		/* only add aggregates with a DISTINCT or ORDER BY */
+		if (aggref->aggdistinct != NIL || aggref->aggorder != NIL)
+				/* are 'pathkeys' compatible or better than 'currpathkeys'? */
+				switch (compare_pathkeys(currpathkeys, pathkeys))
+					case PATHKEYS_BETTER2:
+						/* 'pathkeys' are stronger, use these ones instead */
+						/* FALLTHROUGH */
+					case PATHKEYS_BETTER1:
+						/* 'pathkeys' are less strict */
+						/* FALLTHROUGH */
+					case PATHKEYS_EQUAL:
+						/* mark this aggregate is covered by 'currpathkeys' */
+					case PATHKEYS_DIFFERENT:
+	 * performing a sort for these Aggrefs.  We're able to do this now
+	 * as there's no chance of a Hash Aggregate plan as create_grouping_paths
+	 * will not mark the group by as GROUPING_CAN_USE_HASH due to the
+	 * presence of ordered aggregates.
@@ -3137,18 +3349,19 @@ standard_qp_callback(PlannerInfo *root, void *extra)
 
 	/*
 
 	/* We consider only the first (bottom) window in pathkeys logic */
 	if (activeWindows != NIL)
@@ -6222,6 +6435,26 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 
 	if (can_sort)
 	{
+		List	   *group_pathkeys;
@@ -6234,7 +6467,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,

 
 			/* generate alternative group orderings that might be useful */
@@ -6242,7 +6474,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 																path->rows,
 																path->pathkeys,
 																group_pathkeys,
-																group_clauses);
+																group_clauses,
+																orderAggPathkeys);

@@ -6414,7 +6647,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 																	path->rows,
 																	path->pathkeys,
 																	group_pathkeys,
-																	group_clauses);
+																	group_clauses,
+																	orderAggPathkeys);

@@ -6717,6 +6951,24 @@ create_partial_grouping_paths(PlannerInfo *root,

@@ -6729,10 +6981,7 @@ create_partial_grouping_paths(PlannerInfo *root,
 			ListCell   *lc2;
 
 			/* generate alternative group orderings that might be useful */
@@ -6740,7 +6989,8 @@ create_partial_grouping_paths(PlannerInfo *root,
 																path->rows,
 																path->pathkeys,
 																group_pathkeys,
-																group_clauses);
+																group_clauses,
+																orderAggPathkeys);

@@ -6856,16 +7106,31 @@ create_partial_grouping_paths(PlannerInfo *root,

 			/* generate alternative group orderings that might be useful */
@@ -6873,7 +7138,8 @@ create_partial_grouping_paths(PlannerInfo *root,
 																path->rows,
 																path->pathkeys,
 																group_pathkeys,
-																group_clauses);
+																group_clauses,
+																orderAggPathkeys);

 

 
 		aggno++;

 
 		/*

 
+	/*
 
 	/*
 	 * These values are working state that is initialized at the start of an
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index e2081db4ed..3b065139e6 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -365,6 +365,14 @@ struct PlannerInfo
 
@@ -3134,12 +3142,12 @@ typedef struct AggInfo
 	NodeTag		type;
 
 	/*

 

 

 :qry;
 
 :qry;
 
 drop table t1, t2;
 
+--
2.34.1

---

From: Zhihong Yu <[email-masked]>
Date: Mon, 25 Jul 2022 17:07:31 -0700

> case where currpathkeys are better.
Hi,

sort order the the planner chooses is simply : there is duplicate `the`

+                       /* mark this aggregate is covered by 'currpathkeys'
*/

is covered by -> as covered by

Cheers

---

From: Richard Guo <[email-masked]>
Date: Tue, 26 Jul 2022 15:39:25 +0800

> case where currpathkeys are better.

Thanks. Verified problem is solved in v8 patch.

Also I'm wondering if it's possible to take into consideration the
ordering indicated by existing indexes when determining the pathkeys. So
that for the query below we can avoid the Incremental Sort node if we
consider that there is an index on t(a, c):

# explain (costs off) select max(b order by b), max(c order by c) from t
group by a;
                 QUERY PLAN
---------------------------------------------
 GroupAggregate
   Group Key: a
   ->  Incremental Sort
         Sort Key: a, b
         Presorted Key: a
         ->  Index Scan using t_a_c_idx on t
(6 rows)

Thanks
Richard

---

From: David Rowley <[email-masked]>
Date: Wed, 27 Jul 2022 10:37:26 +1200

> sort order the the planner chooses is simply : there is duplicate `the`

I think the first "the" should be "that"

> is covered by -> as covered by

I think it was shortened from "mark that this aggregate", but I
dropped "that" to get the comment to fit on a single line. Swapping
"is" for "as" makes it better. Thanks.

David

---

From: David Rowley <[email-masked]>
Date: Wed, 27 Jul 2022 10:45:44 +1200

On Tue, 26 Jul 2022 at 19:39, Richard Guo <[email-masked]> wrote:
> # explain (costs off) select max(b order by b), max(c order by c) from t group by a;
>                  QUERY PLAN

That would be nice but I'm not going to add anything to this patch
which does anything like that. I think the patch, as it is, is a good
meaningful step forward to improve the performance of ordered
aggregates.

There are other things in the planner that could gain from what you
talk about. For example, choosing the evaluation order of WindowFuncs.
Perhaps it would be better to try to tackle those two problems
together rather than try to sneak something half-baked along with this
patch.

David

---

From: Richard Guo <[email-masked]>
Date: Wed, 27 Jul 2022 11:16:36 +0800

> meaningful step forward to improve the performance of ordered

Concur with that.

> together rather than try to sneak something half-baked along with this

That makes sense. The patch looks in a good shape to me in this part.

Thanks
Richard

---

From: David Rowley <[email-masked]>
Date: Fri, 29 Jul 2022 06:49:53 +1200

> That makes sense. The patch looks in a good shape to me in this part.

Thanks for giving it another look.

I'm also quite happy with the patch now. The 2 plan changes are
explained. I have a patch on another thread [1] for the change in the
Merge Join plan.  I'd like to consider that separately from this
patch.

The postgres_fdw changes are explained in [2]. This can be fixed by
setting fdw_tuple_cost to something more realistic in the foreign
server settings on the test.

I'd like to take a serious look at pushing this patch on the first few
days of August, so if anyone is following along here that might have
objections, can you do so before then?

David

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

---

From: Tom Lane <[email-masked]>
Date: Sun, 31 Jul 2022 11:49:51 -0400

> objections, can you do so before then?

Are you going to push the other patch (adjusting
select_outer_pathkeys_for_merge) first, so that we can see the residual
plan changes that this patch creates?  I'm not entirely comfortable
with the regression test changes as posted.  Likewise, it might be
better to fix DEFAULT_FDW_TUPLE_COST beforehand, to detangle what
the effects of that are.

Also, I think it's bad style to rely on aggpresorted defaulting to false.
You should explicitly initialize it anywhere that an Aggref node is
constructed.  It looks like there are just two places to fix
(parse_expr.c and parse_func.c).

Nothing else jumped out at me in a quick scan.

			regards, tom lane

---

From: David Rowley <[email-masked]>
Date: Tue, 2 Aug 2022 23:21:04 +1200

On Mon, 1 Aug 2022 at 03:49, Tom Lane <[email-masked]> wrote:
> with the regression test changes as posted.

Yes, I pushed that earlier.

> Likewise, it might be

I chatted to Andres and Thomas about this last week and their view
made me think it might not be quite as clear-cut as "just bump it up a
bunch because it's ridiculously low" that I had in mind.  They
mentioned about file_fdw and another one that appears to work on
mmapped segments, which I don't recall if any names were mentioned.
Certainly that's not a reason not to change it, but it's not quite as
clear-cut as I thought.  I'll open a thread with some reasonable
evidence to get a topic going and see where we end up.  In the
meantime I've just coded it to do a temporary adjustment to the
fdw_tuple_cost foreign server setting just before the test in
question.

> (parse_expr.c and parse_func.c).

Ooops. I'm normally good at remembering that. Not this time!

> Nothing else jumped out at me in a quick scan.

Thanks for the quick scan.  I did another few myself and adjusted a
small number of things. Mostly comments and using things like
lfirst_node and list_nth_node instead of lfirst and list_nth with a
cast.

I've now pushed the patch.

Thank you to everyone who looked at this.

David

---

From: Tom Lane <[email-masked]>
Date: Tue, 02 Aug 2022 09:19:39 -0400

> mmapped segments, which I don't recall if any names were mentioned.

Um ... DEFAULT_FDW_TUPLE_COST is postgres_fdw-specific, so I do not
see what connection some other FDW would have to it.

			regards, tom lane

---

From: David Rowley <[email-masked]>
Date: Wed, 3 Aug 2022 02:59:05 +1200

> see what connection some other FDW would have to it.

I should have devoted more brain cells to that one.

Anyway, I started a thread at [1].

David

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

---

From: Zhihong Yu <[email-masked]>
Date: Tue, 2 Aug 2022 11:02:51 -0700

> Hi, David:

I was looking at the final patch and noticed that setno field
in agg_presorted_distinctcheck struct is never used.

Looks like it was copied from neighboring struct.

Can you take a look at the patch ?

Thanks

---

From: Zhihong Yu <[email-masked]>
Date: Tue, 2 Aug 2022 12:38:22 -0700

On Tue, Aug 2, 2022 at 11:02 AM Zhihong Yu <[email-masked]> wrote:

> Looks like setoff field is not used either.

Cheers

---

From: David Rowley <[email-masked]>
Date: Wed, 3 Aug 2022 09:48:49 +1200

On Wed, 3 Aug 2022 at 07:31, Zhihong Yu <[email-masked]> wrote:
>> I was looking at the final patch and noticed that setno field in agg_presorted_distinctcheck struct is never used.

> Looks like setoff field is not used either.

Thanks for the report. It seems transno was unused too.

I just pushed a commit to remove all 3.

David

---

From: Justin Pryzby <[email-masked]>
Date: Tue, 16 Aug 2022 20:57:55 -0500

> I've now pushed the patch.

I've not studied the patch at all.

But in a few places, it removes the locally-computed group_pathkeys:

However it doesn't do that here:

                /*
                 * Instead of operating directly on the input relation, we can
                 * consider finalizing a partially aggregated path.
                 */
                if (partially_grouped_rel != NULL)
                {
                        foreach(lc, partially_grouped_rel->pathlist)
                        {
                                ListCell   *lc2;
                                Path       *path = (Path *) lfirst(lc);
                                Path       *path_original = path;

                                List       *group_pathkeys = root->group_pathkeys;

I noticed because that creates a new shadow variable, which seems accidental.

make src/backend/optimizer/plan/planner.o COPT=-Wshadow=compatible-local

src/backend/optimizer/plan/planner.c:6642:14: warning: declaration of ‘group_pathkeys’ shadows a previous local [-Wshadow=compatible-local]
 6642 |     List    *group_pathkeys = root->group_pathkeys;
      |              ^~~~~~~~~~~~~~
src/backend/optimizer/plan/planner.c:6438:12: note: shadowed declaration is here
 6438 |   List    *group_pathkeys;

-- 
Justin

---

From: David Rowley <[email-masked]>
Date: Thu, 18 Aug 2022 11:38:25 +1200

> I noticed because that creates a new shadow variable, which seems accidental.

Thanks for the report.

I've just pushed a fix for this that basically just removes the line
you quoted.  Really I should have been using the version of
group_pathkeys that stripped off the pathkeys from the ORDER BY /
DISTINCT aggregates that is calculated earlier in that function.   In
practice, there was no actual bug here as the wrong variable was only
being used in the code path that was handling partial paths.  We never
create any partial paths when there are aggregates with ORDER BY /
DISTINCT  clauses, so in that code path, the two versions of the
group_pathkeys variable would have always been set to the same thing.

It makes sense just to get rid of the shadowed variable since the
value of it will be the same anyway.

David

---

From: Pavel Luzanov <[email-masked]>
Date: Sat, 5 Nov 2022 11:51:23 +0300

Hello,

While playing with the patch I found a situation where the performance 
may be degraded compared to previous versions.

The test case below.
If you create a proper index for the query (a,c), version 16 wins. On my 
notebook, the query runs ~50% faster.
But if there is no index (a,c), but only (a,b), in previous versions the 
planner uses it, but with this patch a full table scan is selected.

create table t (a text, b text, c text);
insert into t (a,b,c) select x,y,x from generate_series(1,100) as x, 
generate_series(1,10000) y;
create index on t (a,b);
vacuum analyze t;

explain (analyze, buffers)
select a, array_agg(c order by c) from t group by a;

v 14.5
                                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=0.42..46587.76 rows=100 width=34) (actual 
time=3.077..351.526 rows=100 loops=1)
    Group Key: a
    Buffers: shared hit=193387 read=2745
    ->  Index Scan using t_a_b_idx on t  (cost=0.42..41586.51 
rows=1000000 width=4) (actual time=0.014..155.095 rows=1000000 loops=1)
          Buffers: shared hit=193387 read=2745
  Planning:
    Buffers: shared hit=9
  Planning Time: 0.059 ms
  Execution Time: 351.581 ms
(9 rows)

v 16
                                                        QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=128728.34..136229.59 rows=100 width=34) (actual 
time=262.930..572.915 rows=100 loops=1)
    Group Key: a
    Buffers: shared hit=5396, temp read=1950 written=1964
    ->  Sort  (cost=128728.34..131228.34 rows=1000000 width=4) (actual 
time=259.423..434.105 rows=1000000 loops=1)
          Sort Key: a, c
          Sort Method: external merge  Disk: 15600kB
          Buffers: shared hit=5396, temp read=1950 written=1964
          ->  Seq Scan on t  (cost=0.00..15396.00 rows=1000000 width=4) 
(actual time=0.005..84.104 rows=1000000 loops=1)
                Buffers: shared hit=5396
  Planning:
    Buffers: shared hit=9
  Planning Time: 0.055 ms
  Execution Time: 575.146 ms
(13 rows)

-- 
Pavel Luzanov
Postgres Professional: https://postgrespro.com
The Russian Postgres Company

---

From: Ronan Dunklau <[email-masked]>
Date: Mon, 07 Nov 2022 15:53:42 +0100

Hello,

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

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

ro=# create index on t (b, a);
CREATE INDEX
ro=# explain  select b, array_agg(c order by c) from t group by b;
                                       QUERY PLAN                                        
-----------------------------------------------------------------------------------------
 GroupAggregate  (cost=10.64..120926.80 rows=9970 width=36)
   Group Key: b
   ->  Incremental Sort  (cost=10.64..115802.17 rows=1000000 width=6)
         Sort Key: b, c
         Presorted Key: b
         ->  Index Scan using t_b_a_idx on t  (cost=0.42..47604.12 
rows=1000000 width=6)
(6 rows)

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

                                       QUERY PLAN                                        
-----------------------------------------------------------------------------------------
 GroupAggregate  (cost=154944.94..162446.19 rows=100 width=34)
   Group Key: a
   ->  Sort  (cost=154944.94..157444.94 rows=1000000 width=4)
         Sort Key: a, c
         ->  Index Scan using t_a_b_idx on t  (cost=0.42..41612.60 
rows=1000000 width=4)
(5 rows)

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

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

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

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

Best regards,

--
Ronan Dunklau

---

From: Pavel Luzanov <[email-masked]>
Date: Mon, 7 Nov 2022 19:58:50 +0300

Hi,

> you will get a full sort over an index scan:

You are right. By disabling seq scan, we can get this plan. But compare 
it with the plan in v15:

postgres@db(15.0)=# explain
select a, array_agg(c order by c) from t group by a;
                                     QUERY PLAN
-----------------------------------------------------------------------------------
  GroupAggregate  (cost=0.42..46667.56 rows=100 width=34)
    Group Key: a
    ->  Index Scan using t_a_b_idx on t  (cost=0.42..41666.31 
rows=1000000 width=4)
(3 rows)

The total plan cost in v16 is ~4 times higher, while the index scan cost 
remains the same.

> using the same presorted path.

The only reason I can see is the number of buffers to read. In the plan 
with incremental sort we read the whole index, ~190000 buffers.
And the plan with seq scan only required ~5000 (I think due to buffer 
ring optimization).

Perhaps this behavior is preferable. Especially when many concurrent 
queries are running. The less buffer cache is busy, the better. But in 
single-user mode this query is slower.

---

From: Ronan Dunklau <[email-masked]>
Date: Mon, 07 Nov 2022 18:30:16 +0100

Le lundi 7 novembre 2022, 17:58:50 CET Pavel Luzanov a écrit :
> > I can't see why an incrementalsort could be more expensive than a full
> > sort, using the same presorted path.
> 

What I meant here is that disabling seqscans, the planner still chooses a full 
sort over a partial sort. The underlying index is the same, it is just a 
matter of choosing a Sort node over an IncrementalSort node. This, I think, is 
wrong: I can't see how it could be worse to use an incrementalsort in that 
case. 

It makes sense to prefer a SeqScan over an IndexScan if you are going to sort 
the whole table anyway. But in that case we shouldn't. What happened before is 
that some sort of incremental sort was always chosen, because it was hidden as 
an implementation detail of the agg node. But now it has to compete on a cost 
basis with the full sort, and that costing is wrong in that case. 

Maybe the original costing code for incremental sort was a bit too 
pessimistic. 

--
Ronan Dunklau

---

From: Pavel Luzanov <[email-masked]>
Date: Mon, 7 Nov 2022 23:37:55 +0300

> wrong: I can't see how it could be worse to use an incrementalsort in that

I finally get your point. And I agree with you.

> Maybe the original costing code for incremental sort was a bit too

In this query, incremental sorting lost just a little bit in cost: 
164468.95 vs 162504.23.

QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=155002.98..162504.23 rows=100 width=34) (actual 
time=296.591..568.270 rows=100 loops=1)
    Group Key: a
    ->  Sort  (cost=155002.98..157502.98 rows=1000000 width=4) (actual 
time=293.810..454.170 rows=1000000 loops=1)
          Sort Key: a, c
          Sort Method: external merge  Disk: 15560kB
          ->  Index Scan using t_a_b_idx on t (cost=0.42..41670.64 
rows=1000000 width=4) (actual time=0.021..156.441 rows=1000000 loops=1)
  Settings: enable_seqscan = 'off'
  Planning Time: 0.074 ms
  Execution Time: 569.957 ms
(9 rows)

set enable_sort=off;
SET
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=1457.58..164468.95 rows=100 width=34) (actual 
time=6.623..408.833 rows=100 loops=1)
    Group Key: a
    ->  Incremental Sort  (cost=1457.58..159467.70 rows=1000000 width=4) 
(actual time=2.652..298.530 rows=1000000 loops=1)
          Sort Key: a, c
          Presorted Key: a
          Full-sort Groups: 100  Sort Method: quicksort  Average Memory: 
27kB  Peak Memory: 27kB
          Pre-sorted Groups: 100  Sort Method: quicksort  Average 
Memory: 697kB  Peak Memory: 697kB
          ->  Index Scan using t_a_b_idx on t (cost=0.42..41670.64 
rows=1000000 width=4) (actual time=0.011..155.260 rows=1000000 loops=1)
  Settings: enable_seqscan = 'off', enable_sort = 'off'
  Planning Time: 0.044 ms
  Execution Time: 408.867 ms

---

From: David Rowley <[email-masked]>
Date: Tue, 8 Nov 2022 14:31:12 +1300

> to make sure they are never more expensive than the full sort ?

The only thing that I could think of that would cause incremental sort
to be more expensive than sort is the tuplesort_reset() calls that are
performed between sorts. However, I see cost_incremental_sort()
accounts for those already with:

run_cost += 2.0 * cpu_tuple_cost * input_groups;

Also, I see at the top of incremental_sort.sql there's a comment claiming:

-- When we have to sort the entire table, incremental sort will
-- be slower than plain sort, so it should not be used.

I'm just unable to verify that's true by doing the following:

$ echo "select * from (select * from tenk1 order by four) t order by
four, ten;" > bench.sql

$ pgbench -n -f bench.sql -T 60 -M prepared regression | grep -E "^tps"
tps = 102.136151 (without initial connection time)

$ # disable sort so that the test performs Sort -> Incremental Sort rather
$ # than Sort -> Sort
$ psql -c "alter system set enable_sort=0;" regression
$ psql -c "select pg_reload_conf();" regression

$ pgbench -n -f bench.sql -T 60 -M prepared regression | grep -E "^tps"
tps = 112.378761 (without initial connection time)

When I disable sort, the plan changes to use Incremental Sort and
execution becomes faster, not slower like the comment claims it will.
Perhaps this was true during the development of Incremental sort and
then something was changed to speed things up.  I do recall reviewing
that patch many years ago and hinting about the invention of
tuplesort_reset(). I don't recall, but I assume the patch must have
been creating a new tuplesort each group before that.

Also, I was looking at add_paths_to_grouping_rel() and I saw that if
presorted_keys > 0 that we'll create both a Sort and Incremental Sort
path.  If we assume Incremental Sort is always better when it can be
done, then it seems useless to create the Sort path when Incremental
Sort is possible.  When working on making Incremental Sorts work for
window functions I did things that way. Maybe we should just make
add_paths_to_grouping_rel() work the same way.

Regarding the 1.5 factor in cost_incremental_sort(), I assume this is
for skewed groups. Imagine there's 1 huge group and 99 tiny ones.
However, even if that were the case, I imagine the performance would
still be around the same performance as the non-incremental variant of
sort.

I've been playing around with the attached patch which does:

1. Adjusts add_paths_to_grouping_rel so that we don't add a Sort path
when we can add an Incremental Sort path instead. This removes quite a
few redundant lines of code.
2. Removes the * 1.5 fuzz-factor in cost_incremental_sort()
3. Does various other code tidy stuff in cost_incremental_sort().
4. Removes the test from incremental_sort.sql that was ensuring the
inferior Sort -> Sort plan was being used instead of the superior Sort
-> Incremental Sort plan.

I'm not really that 100% confident in the removal of the * 1.5 thing.
I wonder if there's some reason we're not considering that might cause
a performance regression if we're to remove it.

David
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 4c6b1d1f55..9f4c011dac 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1959,8 +1959,8 @@ cost_incremental_sort(Path *path,
 					  double input_tuples, int width, Cost comparison_cost, int sort_mem,
 					  double limit_tuples)
 {
-	Cost		startup_cost = 0,
-				run_cost = 0,
+	Cost		startup_cost,
+				run_cost,
 				input_run_cost = input_total_cost - input_startup_cost;
 	double		group_tuples,
 				input_groups;
@@ -1969,10 +1969,9 @@ cost_incremental_sort(Path *path,
 				group_input_run_cost;
 	List	   *presortedExprs = NIL;
 	ListCell   *l;
-	int			i = 0;
 	bool		unknown_varno = false;
 
-	Assert(presorted_keys != 0);
+	Assert(presorted_keys > 0 && presorted_keys < list_length(pathkeys));
 
 	/*
 	 * We want to be sure the cost of a sort is never estimated as zero, even
@@ -2025,8 +2024,7 @@ cost_incremental_sort(Path *path,
 		/* expression not containing any Vars with "varno 0" */
 		presortedExprs = lappend(presortedExprs, member->em_expr);
 
-		i++;
-		if (i >= presorted_keys)
+		if (foreach_current_index(l) + 1 >= presorted_keys)
 			break;
 	}
 
@@ -2040,21 +2038,18 @@ cost_incremental_sort(Path *path,
 
 	/*
 	 * Estimate average cost of sorting of one group where presorted keys are
-	 * equal.  Incremental sort is sensitive to distribution of tuples to the
-	 * groups, where we're relying on quite rough assumptions.  Thus, we're
-	 * pessimistic about incremental sort performance and increase its average
-	 * group size by half.
+	 * equal.
 	 */
 	cost_tuplesort(&group_startup_cost, &group_run_cost,
-				   1.5 * group_tuples, width, comparison_cost, sort_mem,
+				   group_tuples, width, comparison_cost, sort_mem,
 				   limit_tuples);
 
 	/*
 	 * Startup cost of incremental sort is the startup cost of its first group
 	 * plus the cost of its input.
 	 */
-	startup_cost += group_startup_cost
-		+ input_startup_cost + group_input_run_cost;
+	startup_cost = group_startup_cost + input_startup_cost +
+				   group_input_run_cost;
 
 	/*
 	 * After we started producing tuples from the first group, the cost of
@@ -2062,17 +2057,20 @@ cost_incremental_sort(Path *path,
 	 * group, plus the total cost to process the remaining groups, plus the
 	 * remaining cost of input.
 	 */
-	run_cost += group_run_cost
-		+ (group_run_cost + group_startup_cost) * (input_groups - 1)
-		+ group_input_run_cost * (input_groups - 1);
+	run_cost = group_run_cost + (group_run_cost + group_startup_cost) *
+			   (input_groups - 1) + group_input_run_cost * (input_groups - 1);
 
 	/*
 	 * Incremental sort adds some overhead by itself. Firstly, it has to
 	 * detect the sort groups. This is roughly equal to one extra copy and
-	 * comparison per tuple. Secondly, it has to reset the tuplesort context
-	 * for every group.
+	 * comparison per tuple.
 	 */
 	run_cost += (cpu_tuple_cost + comparison_cost) * input_tuples;
+
+	/*
+	 * Additionally, we charge double cpu_tuple_cost for each input group to
+	 * account for the tuplesort_reset that's performed after each group.
+	 */
 	run_cost += 2.0 * cpu_tuple_cost * input_groups;
 
 	path->rows = input_tuples;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 493a3af0fa..355abeaefb 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6496,7 +6496,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 		foreach(lc, input_rel->pathlist)
 		{
 			Path	   *path = (Path *) lfirst(lc);
-			Path	   *path_original = path;
 			bool		is_sorted;
 			int			presorted_keys;
 
@@ -6504,90 +6503,28 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 													path->pathkeys,
 													&presorted_keys);
 
-			if (path == cheapest_path || is_sorted)
+			if (!is_sorted)
 			{
-				/* Sort the cheapest-total path if it isn't already sorted */
-				if (!is_sorted)
+				/*
+				 * We've no need to consider both a sort and incremental sort.
+				 * We'll just do a sort if there are no pre-sorted keys and
+				 * an incremental sort when there are pre-sorted keys.
+				 */
+				if (presorted_keys == 0 || !enable_incremental_sort)
 					path = (Path *) create_sort_path(root,
 													 grouped_rel,
 													 path,
 													 root->group_pathkeys,
 													 -1.0);
-
-				/* Now decide what to stick atop it */
-				if (parse->groupingSets)
-				{
-					consider_groupingsets_paths(root, grouped_rel,
-												path, true, can_hash,
-												gd, agg_costs, dNumGroups);
-				}
-				else if (parse->hasAggs)
-				{
-					/*
-					 * We have aggregation, possibly with plain GROUP BY. Make
-					 * an AggPath.
-					 */
-					add_path(grouped_rel, (Path *)
-							 create_agg_path(root,
-											 grouped_rel,
-											 path,
-											 grouped_rel->reltarget,
-											 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
-											 AGGSPLIT_SIMPLE,
-											 parse->groupClause,
-											 havingQual,
-											 agg_costs,
-											 dNumGroups));
-				}
-				else if (parse->groupClause)
-				{
-					/*
-					 * We have GROUP BY without aggregation or grouping sets.
-					 * Make a GroupPath.
-					 */
-					add_path(grouped_rel, (Path *)
-							 create_group_path(root,
-											   grouped_rel,
-											   path,
-											   parse->groupClause,
-											   havingQual,
-											   dNumGroups));
-				}
 				else
-				{
-					/* Other cases should have been handled above */
-					Assert(false);
-				}
+					path = (Path *) create_incremental_sort_path(root,
+																 grouped_rel,
+																 path,
+																 root->group_pathkeys,
+																 presorted_keys,
+																 -1.0);
 			}
 
-			/*
-			 * Now we may consider incremental sort on this path, but only
-			 * when the path is not already sorted and when incremental sort
-			 * is enabled.
-			 */
-			if (is_sorted || !enable_incremental_sort)
-				continue;
-
-			/* Restore the input path (we might have added Sort on top). */
-			path = path_original;
-
-			/* no shared prefix, no point in building incremental sort */
-			if (presorted_keys == 0)
-				continue;
-
-			/*
-			 * We should have already excluded pathkeys of length 1 because
-			 * then presorted_keys > 0 would imply is_sorted was true.
-			 */
-			Assert(list_length(root->group_pathkeys) != 1);
-
-			path = (Path *) create_incremental_sort_path(root,
-														 grouped_rel,
-														 path,
-														 root->group_pathkeys,
-														 presorted_keys,
-														 -1.0);
-
 			/* Now decide what to stick atop it */
 			if (parse->groupingSets)
 			{
@@ -6602,16 +6539,16 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 				 * AggPath.
 				 */
 				add_path(grouped_rel, (Path *)
-						 create_agg_path(root,
-										 grouped_rel,
-										 path,
-										 grouped_rel->reltarget,
-										 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
-										 AGGSPLIT_SIMPLE,
-										 parse->groupClause,
-										 havingQual,
-										 agg_costs,
-										 dNumGroups));
+							create_agg_path(root,
+											grouped_rel,
+											path,
+											grouped_rel->reltarget,
+											parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+											AGGSPLIT_SIMPLE,
+											parse->groupClause,
+											havingQual,
+											agg_costs,
+											dNumGroups));
 			}
 			else if (parse->groupClause)
 			{
@@ -6620,12 +6557,12 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 				 * a GroupPath.
 				 */
 				add_path(grouped_rel, (Path *)
-						 create_group_path(root,
-										   grouped_rel,
-										   path,
-										   parse->groupClause,
-										   havingQual,
-										   dNumGroups));
+							create_group_path(root,
+											grouped_rel,
+											path,
+											parse->groupClause,
+											havingQual,
+											dNumGroups));
 			}
 			else
 			{
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..1a1e8b2365 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1,16 +1,3 @@
--- When we have to sort the entire table, incremental sort will
--- be slower than plain sort, so it should not be used.
-explain (costs off)
-select * from (select * from tenk1 order by four) t order by four, ten;
-            QUERY PLAN             
------------------------------------
- Sort
-   Sort Key: tenk1.four, tenk1.ten
-   ->  Sort
-         Sort Key: tenk1.four
-         ->  Seq Scan on tenk1
-(5 rows)
-
 -- When there is a LIMIT clause, incremental sort is beneficial because
 -- it only has to sort some of the groups, and not the entire table.
 explain (costs off)
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 284a354dbb..071f8a5268 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -1,8 +1,3 @@
--- When we have to sort the entire table, incremental sort will
--- be slower than plain sort, so it should not be used.
-explain (costs off)
-select * from (select * from tenk1 order by four) t order by four, ten;
-
 -- When there is a LIMIT clause, incremental sort is beneficial because
 -- it only has to sort some of the groups, and not the entire table.
 explain (costs off)

---

From: Pavel Luzanov <[email-masked]>
Date: Tue, 8 Nov 2022 09:39:12 +0300

> -> Incremental Sort plan.

I can confirm that with this patch, the plan with incremental sorting 
beats the others.

Here are the test results with my previous example.

Script:

create index on t (a);
vacuum analyze t;
reset all;

explain (settings, analyze)
select a, array_agg(c order by c) from t group by a;

\echo set enable_incremental_sort=off;
set enable_incremental_sort=off;

explain (settings, analyze)
select a, array_agg(c order by c) from t group by a;

\echo set enable_seqscan=off;
set enable_seqscan=off;

explain (settings, analyze)
select a, array_agg(c order by c) from t group by a;

Script output:

CREATE TABLE
INSERT 0 1000000
CREATE INDEX
VACUUM
RESET
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=957.60..113221.24 rows=100 width=34) (actual 
time=6.088..381.777 rows=100 loops=1)
    Group Key: a
    ->  Incremental Sort  (cost=957.60..108219.99 rows=1000000 width=4) 
(actual time=2.387..272.332 rows=1000000 loops=1)
          Sort Key: a, c
          Presorted Key: a
          Full-sort Groups: 100  Sort Method: quicksort  Average Memory: 
27kB  Peak Memory: 27kB
          Pre-sorted Groups: 100  Sort Method: quicksort  Average 
Memory: 697kB  Peak Memory: 697kB
          ->  Index Scan using t_a_idx on t (cost=0.42..29279.42 
rows=1000000 width=4) (actual time=0.024..128.083 rows=1000000 loops=1)
  Planning Time: 0.070 ms
  Execution Time: 381.815 ms
(10 rows)

set enable_incremental_sort=off;
SET
                                                        QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=128728.34..136229.59 rows=100 width=34) (actual 
time=234.044..495.537 rows=100 loops=1)
    Group Key: a
    ->  Sort  (cost=128728.34..131228.34 rows=1000000 width=4) (actual 
time=231.172..383.393 rows=1000000 loops=1)
          Sort Key: a, c
          Sort Method: external merge  Disk: 15600kB
          ->  Seq Scan on t  (cost=0.00..15396.00 rows=1000000 width=4) 
(actual time=0.005..78.189 rows=1000000 loops=1)
  Settings: enable_incremental_sort = 'off'
  Planning Time: 0.041 ms
  Execution Time: 497.230 ms
(9 rows)

set enable_seqscan=off;
SET
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=142611.77..150113.02 rows=100 width=34) (actual 
time=262.250..527.260 rows=100 loops=1)
    Group Key: a
    ->  Sort  (cost=142611.77..145111.77 rows=1000000 width=4) (actual 
time=259.551..417.154 rows=1000000 loops=1)
          Sort Key: a, c
          Sort Method: external merge  Disk: 15560kB
          ->  Index Scan using t_a_idx on t (cost=0.42..29279.42 
rows=1000000 width=4) (actual time=0.012..121.995 rows=1000000 loops=1)
  Settings: enable_incremental_sort = 'off', enable_seqscan = 'off'
  Planning Time: 0.041 ms
  Execution Time: 528.950 ms
(9 rows)

---

From: Richard Guo <[email-masked]>
Date: Tue, 8 Nov 2022 14:51:00 +0800

> few redundant lines of code.

For unsorted paths, the original logic here is to explicitly add a Sort
path only for the cheapest-total path.  This patch changes that and may
add a Sort path for other paths besides the cheapest-total path.  I
think this may introduce in some unnecessary path candidates.

I think it's good that this patch removes redundant codes.  ISTM we can
do the same when we try to finalize the partially aggregated paths from
partially_grouped_rel.

Thanks
Richard

---

From: Ronan Dunklau <[email-masked]>
Date: Tue, 08 Nov 2022 09:43:57 +0100

> few redundant lines of code.

This seems sensible

> a performance regression if we're to remove it.

I'm not sure about it either. It seems to me that we were afraid of 
regressions, and having this overcharged just made us miss a new optimization 
without changing existing plans. With ordered aggregates, the balance is a bit 
trickier and we are at risk of either regressing on aggregate plans, or more 
common ordered ones.

--
Ronan Dunklau

---

From: David Rowley <[email-masked]>
Date: Wed, 9 Nov 2022 14:58:53 +1300

> think this may introduce in some unnecessary path candidates.

Yeah, you're right. The patch shouldn't change that.  I've adjusted
the attached patch so that part works more like it did before.

v2 attached.

Thanks

David
index 4c6b1d1f55..fe8573d92c 100644

 	/*
 	 * We want to be sure the cost of a sort is never estimated as zero, even
@@ -2025,12 +2024,11 @@ cost_incremental_sort(Path *path,
 		/* expression not containing any Vars with "varno 0" */
 		presortedExprs = lappend(presortedExprs, member->em_expr);
 
-		i++;
 
-	/* Estimate number of groups with equal presorted keys. */
+	/* Estimate the number of groups with equal presorted keys. */
 	if (!unknown_varno)
 		input_groups = estimate_num_groups(root, presortedExprs, input_tuples,
 										   NULL, NULL);
@@ -2039,22 +2037,19 @@ cost_incremental_sort(Path *path,
 	group_input_run_cost = input_run_cost / input_groups;
 
 	/*
-	 * Estimate average cost of sorting of one group where presorted keys are
-	 * equal.  Incremental sort is sensitive to distribution of tuples to the
-	 * groups, where we're relying on quite rough assumptions.  Thus, we're
-	 * pessimistic about incremental sort performance and increase its average
-	 * group size by half.
+	 * Estimate the average cost of sorting of one group where presorted keys
+	 * are equal.
 	 */
 	cost_tuplesort(&group_startup_cost, &group_run_cost,
-				   1.5 * group_tuples, width, comparison_cost, sort_mem,
+				   group_tuples, width, comparison_cost, sort_mem,
 				   limit_tuples);
 
 	/*
 
 	/*
 
 	/*
 
 	path->rows = input_tuples;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 493a3af0fa..67c87e2444 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6491,12 +6491,12 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 	{
 		/*
 		 * Use any available suitably-sorted path as input, and also consider
-		 * sorting the cheapest-total path.
+		 * sorting the cheapest-total path and incremental sort on any paths
+		 * with pre-sorted keys.
 		 */
 		foreach(lc, input_rel->pathlist)
 		{
 			Path	   *path = (Path *) lfirst(lc);
-			Path	   *path_original = path;
 			bool		is_sorted;
 			int			presorted_keys;
 
@@ -6504,90 +6504,40 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 													path->pathkeys,
 													&presorted_keys);
 
-			if (path == cheapest_path || is_sorted)
+			if (!is_sorted)
 			{
-				/* Sort the cheapest-total path if it isn't already sorted */
-				if (!is_sorted)
+				/*
+				 * Try at least sorting the cheapest path and also try
+				 * incrementally sorting any path which is partially sorted
+				 * already (no need to worry about pre-sorted keys when
+				 * incremental sort is disabled).
+				 */
+				if (path != cheapest_path &&
+					(presorted_keys == 0 || !enable_incremental_sort))
+					continue;
+
+				/*
+				 * We've no need to consider both a sort and incremental sort.
+				 * We'll just do a sort if there are no pre-sorted keys and
+				 * an incremental sort when there are pre-sorted keys.
+				 */
+				if (presorted_keys == 0 || !enable_incremental_sort)
+				{
 					path = (Path *) create_sort_path(root,
 													 grouped_rel,
 													 path,
 													 root->group_pathkeys,
 													 -1.0);
-
-				/* Now decide what to stick atop it */
-				if (parse->groupingSets)
-				{
-					consider_groupingsets_paths(root, grouped_rel,
-												path, true, can_hash,
-												gd, agg_costs, dNumGroups);
-				}
-				else if (parse->hasAggs)
-				{
-					/*
-					 * We have aggregation, possibly with plain GROUP BY. Make
-					 * an AggPath.
-					 */
-					add_path(grouped_rel, (Path *)
-							 create_agg_path(root,
-											 grouped_rel,
-											 path,
-											 grouped_rel->reltarget,
-											 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
-											 AGGSPLIT_SIMPLE,
-											 parse->groupClause,
-											 havingQual,
-											 agg_costs,
-											 dNumGroups));
-				}
-				else if (parse->groupClause)
-				{
-					/*
-					 * We have GROUP BY without aggregation or grouping sets.
-					 * Make a GroupPath.
-					 */
-					add_path(grouped_rel, (Path *)
-							 create_group_path(root,
-											   grouped_rel,
-											   path,
-											   parse->groupClause,
-											   havingQual,
-											   dNumGroups));
 				}
 				else
-				{
-					/* Other cases should have been handled above */
-					Assert(false);
-				}
+					path = (Path *) create_incremental_sort_path(root,
+																 grouped_rel,
+																 path,
+																 root->group_pathkeys,
+																 presorted_keys,
+																 -1.0);
 			}
 
-			/*
@@ -6602,16 +6552,16 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
@@ -6620,12 +6570,12 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,

---

From: David Rowley <[email-masked]>
Date: Tue, 13 Dec 2022 20:53:40 +1300

> v2 attached.

I've been looking at this again and this time around understand why
the * 1.5 pessimism factor was included in the incremental sort code.

If we create a table with a very large skew in the number of rows per
what will be our pre-sorted groups.

create table ab (a int not null, b int not null);
insert into ab select 0,x from generate_Series(1,999000)x union all
select x%1000+1,0 from generate_Series(999001,1000000)x;

Here the 0 group has close to 1 million rows, but the remaining groups
1-1000 have just 1 row each. The planner only knows there are about
1001 distinct values in "a" and assumes an even distribution of rows
between those values.

With:
explain (analyze, timing off) select * from ab order by a,b;

In master, the plan is:

                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Sort  (cost=122490.27..124990.27 rows=1000000 width=8) (actual
rows=1000000 loops=1)
   Sort Key: a, b
   Sort Method: quicksort  Memory: 55827kB
   ->  Index Scan using ab_a_idx on ab  (cost=0.42..22832.42
rows=1000000 width=8) (actual rows=1000000 loops=1)
 Planning Time: 0.069 ms
 Execution Time: 155.469 ms

With the v2 patch it's:
                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Incremental Sort  (cost=2767.38..109344.55 rows=1000000 width=8)
(actual rows=1000000 loops=1)
   Sort Key: a, b
   Presorted Key: a
   Full-sort Groups: 33  Sort Method: quicksort  Average Memory: 27kB
Peak Memory: 27kB
   Pre-sorted Groups: 1  Sort Method: quicksort  Average Memory:
55795kB  Peak Memory: 55795kB
   ->  Index Scan using ab_a_idx on ab  (cost=0.42..22832.42
rows=1000000 width=8) (actual rows=1000000 loops=1)
 Planning Time: 0.072 ms
 Execution Time: 163.614 ms

So there is a performance regression.

Sometimes teaching the planner new tricks means that it might use
those tricks at a bad time.  Normally we put in an off switch for
these situations to allow users an escape hatch. We have
enable_incremental_sort for this.  It seems like incremental sort has
tried to avoid this problem by always considering the same "Sort"
paths that we did prior to incremental sort, and also considers
incremental sort for pre-sorted paths with the 1.5 pessimism factor.
The v2 patch taking away the safety net.

I think what we need to do is:  Do our best to give incremental sort
the most realistic costs we can and accept that it might choose a
worse plan in some cases. Users can turn it off if they really have no
other means to convince the planner it's wrong.

Additionally, I think what we also need to add a GUC such as
enable_presorted_aggregate.  People can use that when their Index Scan
-> Incremental Sort -> Aggregate plan is worse than their previous Seq
Scan -> Sort -> Aggregate plan that they were getting in < 16.
Turning off enable_incremental_sort alone won't give them the same
aggregate plan that they had in pg15 as we always set the
query_pathkeys to request a sort order that will suit the order by /
distinct aggregates.

I'll draft up a patch for the enable_presorted_aggregate.

David

---

From: David Rowley <[email-masked]>
Date: Fri, 16 Dec 2022 00:10:44 +1300

> I'll draft up a patch for the enable_presorted_aggregate.

I've attached a patch series for this.

v3-0001 can be ignored here. I've posted about that in [1]. Any
discussion about that patch should take place over there.  The patch
is required to get the 0002 patch to pass isolation check

v3-0002 removes the 1.5 x cost pessimism from incremental sort and
also rewrites how we make incremental sort paths.  I've now gone
through the remaining places where we create an incremental sort path
to give all those the same treatment that I'd added to
add_paths_to_grouping_rel(). There was a 1 or 2 plan changes in the
regression tests.  One was the isolation test change, which I claim to
be a broken test and should be fixed another way.  The other was
performing a Sort on the cheapest input path which had presorted keys.
That plan now uses an Incremental Sort to make use of the presorted
keys. I'm happy to see just how much redundant code this removes.
About 200 lines.

v3-0003 adds the enable_presorted_aggregate GUC.

David

[1] https://www.postgresql.org/message-id/CAApHDvrbDhObhLV+=[email-masked]
From ed0e0bd525ea16ea724e9794b5f4feddf29da497 Mon Sep 17 00:00:00 2001
From: David Rowley <[email-masked]>
Date: Thu, 15 Dec 2022 17:49:40 +1300
Subject: [PATCH v3 1/3] Re-adjust drop-index-concurrently-1 isolation test

It seems that drop-index-concurrently has started to forget what it was
originally meant to be testing.  d2d8a229b, which added incremental sorts
changed the expected plan to be an Index Scan plan instead of a Seq Scan
plan.  This occurred as the primary key index of the table in question
provided presorted input and, because that index happened to be the
cheapest input path due to enable_seqscan being disabled, the incremental
sort changes just added a Sort on top of that.  It seems based on the name
of the PREPAREd statement that the intention here is that query produce a
seqscan plan.

The reason this test has become broken seems to be due to how the test was
originally coded. It tried to force a seqscan plan by performing some
casting to make it so the test_dc couldn't be used to perform the required
filtering.  This likely wasn't the best design.  It seems much better just
to toggle enable_seqscan to allow the planner to produce a more
predictable plan.  Trying to coax the planner into using a plan which has
costed in a disable_cost seems like it's always going to be flakey.  So
let's get rid of that and put the expected plans closer to what they were
originally when the test was added.

Additionally, rename a few things in the test and add some additional
wording to the comments to try and make it more clear in the future what
we expect this test to be doing.
---
 .../expected/drop-index-concurrently-1.out    | 31 ++++++++++---------
 .../expected/drop-index-concurrently-1_2.out  | 31 ++++++++++---------
 .../specs/drop-index-concurrently-1.spec      | 22 +++++++------
 3 files changed, 44 insertions(+), 40 deletions(-)

diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out b/src/test/isolation/expected/drop-index-concurrently-1.out
index 97e1a6e779..1cb2250891 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -1,17 +1,17 @@
 Parsed test spec with 3 sessions
 
-starting permutation: noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
-step noseq: SET enable_seqscan = false;
+starting permutation: chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
 step chkiso: SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation';
 is_read_committed
 -----------------
 t                
 (1 row)
 
-step prepi: PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
-step preps: PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data;
+step prepi: PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
+step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
 step begin: BEGIN;
-step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idx;
+step disableseq: SET enable_seqscan = false;
+step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
 QUERY PLAN                                    
 ----------------------------------------------
 Sort                                          
@@ -20,16 +20,17 @@ Sort
         Index Cond: (data = 34)               
 (4 rows)
 
-step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;
-QUERY PLAN                                    
-----------------------------------------------
-Sort                                          
-  Sort Key: id, data                          
-  ->  Index Scan using test_dc_pkey on test_dc
-        Filter: ((data)::text = '34'::text)   
+step enableseq: SET enable_seqscan = true;
+step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
+QUERY PLAN                 
+---------------------------
+Sort                       
+  Sort Key: id             
+  ->  Seq Scan on test_dc  
+        Filter: (data = 34)
 (4 rows)
 
-step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
+step select2: SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
 id|data
 --+----
 34|  34
@@ -38,14 +39,14 @@ id|data
 step drop: DROP INDEX CONCURRENTLY test_dc_data; <waiting ...>
 step insert2: INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100);
 step end2: COMMIT;
-step selecti: EXECUTE getrow_idx;
+step selecti: EXECUTE getrow_idxscan;
  id|data
 ---+----
  34|  34
 134|  34
 (2 rows)
 
-step selects: EXECUTE getrow_seq;
+step selects: EXECUTE getrow_seqscan;
  id|data
 ---+----
  34|  34
diff --git a/src/test/isolation/expected/drop-index-concurrently-1_2.out b/src/test/isolation/expected/drop-index-concurrently-1_2.out
index 04612d3cac..266b0e4ada 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1_2.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1_2.out
@@ -1,17 +1,17 @@
 Parsed test spec with 3 sessions
 
-starting permutation: noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
-step noseq: SET enable_seqscan = false;
+starting permutation: chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
 step chkiso: SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation';
 is_read_committed
 -----------------
 f                
 (1 row)
 
-step prepi: PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
-step preps: PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data;
+step prepi: PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
+step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
 step begin: BEGIN;
-step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idx;
+step disableseq: SET enable_seqscan = false;
+step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
 QUERY PLAN                                    
 ----------------------------------------------
 Sort                                          
@@ -20,16 +20,17 @@ Sort
         Index Cond: (data = 34)               
 (4 rows)
 
-step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;
-QUERY PLAN                                    
-----------------------------------------------
-Sort                                          
-  Sort Key: id, data                          
-  ->  Index Scan using test_dc_pkey on test_dc
-        Filter: ((data)::text = '34'::text)   
+step enableseq: SET enable_seqscan = true;
+step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
+QUERY PLAN                 
+---------------------------
+Sort                       
+  Sort Key: id             
+  ->  Seq Scan on test_dc  
+        Filter: (data = 34)
 (4 rows)
 
-step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
+step select2: SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
 id|data
 --+----
 34|  34
@@ -38,13 +39,13 @@ id|data
 step drop: DROP INDEX CONCURRENTLY test_dc_data; <waiting ...>
 step insert2: INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100);
 step end2: COMMIT;
-step selecti: EXECUTE getrow_idx;
+step selecti: EXECUTE getrow_idxscan;
 id|data
 --+----
 34|  34
 (1 row)
 
-step selects: EXECUTE getrow_seq;
+step selects: EXECUTE getrow_seqscan;
 id|data
 --+----
 34|  34
diff --git a/src/test/isolation/specs/drop-index-concurrently-1.spec b/src/test/isolation/specs/drop-index-concurrently-1.spec
index 812b5de226..a57a02469d 100644
--- a/src/test/isolation/specs/drop-index-concurrently-1.spec
+++ b/src/test/isolation/specs/drop-index-concurrently-1.spec
@@ -3,7 +3,8 @@
 # This test shows that the concurrent write behaviour works correctly
 # with the expected output being 2 rows at the READ COMMITTED and READ
 # UNCOMMITTED transaction isolation levels, and 1 row at the other
-# transaction isolation levels.
+# transaction isolation levels.  We ensure this is the case by checking
+# the returned rows in an index scan plan and a seq scan plan.
 #
 setup
 {
@@ -18,24 +19,25 @@ teardown
 }
 
 session s1
-step noseq { SET enable_seqscan = false; }
 step chkiso { SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation'; }
-step prepi { PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data; }
-step preps { PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data; }
+step prepi { PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
+step preps { PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
 step begin { BEGIN; }
-step explaini { EXPLAIN (COSTS OFF) EXECUTE getrow_idx; }
-step explains { EXPLAIN (COSTS OFF) EXECUTE getrow_seq; }
-step selecti { EXECUTE getrow_idx; }
-step selects { EXECUTE getrow_seq; }
+step disableseq { SET enable_seqscan = false; }
+step explaini { EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan; }
+step enableseq { SET enable_seqscan = true; }
+step explains { EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan; }
+step selecti { EXECUTE getrow_idxscan; }
+step selects { EXECUTE getrow_seqscan; }
 step end { COMMIT; }
 
 session s2
 setup { BEGIN; }
-step select2 { SELECT * FROM test_dc WHERE data=34 ORDER BY id,data; }
+step select2 { SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
 step insert2 { INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100); }
 step end2 { COMMIT; }
 
 session s3
 step drop { DROP INDEX CONCURRENTLY test_dc_data; }
 
-permutation noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
+permutation chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
-- 
2.35.1.windows.2

From 3112cc7e40778d3d377660d864db1f218a3b2cf6 Mon Sep 17 00:00:00 2001
From: David Rowley <[email-masked]>
Date: Tue, 8 Nov 2022 14:36:38 +1300
Subject: [PATCH v3 2/3] Remove pessimistic cost penalization from Incremental
 Sort

When incremental sorts were added in v13 a 1.5x pessimism factor was added
to the cost modal.  Seemingly this was done because the cost modal only
has an estimate of the total number of input rows and the number of
presorted groups.  It assumes that the input rows will be evenly
distributed throughout the presorted groups.  The 1.5x pessimism factor
was added to slightly reduce the likelihood of incremental sorts being
used in the hope to avoid performance regressions where an incremental
sort plan was picked and turned out slower due to a large skew in the
number of rows in the presorted groups.

An additional quirk with the path generation code meant that we could
consider both a sort and an incremental sort on paths with presorted keys.
This meant that with the pessimism factor, it was possible that we opted
to perform a sort rather than an incremental sort when the given path had
presorted keys.

Here we remove the 1.5x pessimism factor to allow incremental sorts to
have a fairer chance at being chosen against a full sort.

Additionally, this changes how incremental sort paths are generated.

Previously we would generally create a sort path on the cheapest input
path (if that wasn't sorted already) and incremental sort paths on any
path which had presorted keys.  This meant that if the cheapest input path
wasn't completely sorted but happened to have presorted keys, we would
create a full sort path *and* an incremental sort path on that input path.
Here we change this logic so that if there are presorted keys, we only
create an incremental sort path, and create sort paths only when a full
sort is required or enable_incremental_sort is disabled.

Both the removal of the cost pessimism factor and the changes made to the
path generation make it more likely that incremental sorts will now be
chosen.  That, of course, as with teaching the planner any new tricks,
means an increased likelihood that the planner will perform an incremental
sort when it's not the best method.  Our standard escape hatch for these
cases is an enable_* GUC.  enable_incremental_sort already exists for
this.

This came out of a report by Pavel Luzanov where he mentioned that v16
was choosing to perform a Seq Scan -> Sort -> Group Aggregate for his
query with an ORDER BY aggregate function.  The v15 plan for his query
performed an Index Scan -> Group Aggregate, of course, the aggregate
performed the final sort internally in nodeAgg.c for the aggregate's ORDER
BY.  The ideal plan would have been to use the index, which provided
partially sorted input then use an incremental sort to provide the
aggregate with the sorted input.  This was not being chosen due to the
pessimism in the incremental sort cost modal, so here we remove that and
rationalize the path generation so that sort and incremental sort plans
don't have to needlessly complete.

Reported-by: Pavel Luzanov
Reviewed-by: Richard Guo
Discussion: https://postgr.es/m/9f61ddbf-2989-1536-b31e-6459370a6baa%40postgrespro.ru
---
 .../postgres_fdw/expected/postgres_fdw.out    |   2 +
 contrib/postgres_fdw/sql/postgres_fdw.sql     |   2 +
 src/backend/optimizer/path/allpaths.c         |  94 ++--
 src/backend/optimizer/path/costsize.c         |  38 +-
 src/backend/optimizer/plan/planner.c          | 480 ++++++------------
 .../regress/expected/incremental_sort.out     |  13 -
 src/test/regress/expected/partition_join.out  |   5 +-
 src/test/regress/sql/incremental_sort.sql     |   5 -
 8 files changed, 220 insertions(+), 419 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 2ab3f1efaa..5f6e1f9833 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -2796,6 +2796,7 @@ select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
 (5 rows)
 
 -- Aggregates in subquery are pushed down.
+set enable_incremental_sort = off;
 explain (verbose, costs off)
 select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
                                                                  QUERY PLAN                                                                  
@@ -2814,6 +2815,7 @@ select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, s
   1000 | 4500
 (1 row)
 
+reset enable_incremental_sort;
 -- Aggregate is still pushed down by taking unshippable expression out
 explain (verbose, costs off)
 select c2 * (random() <= 1)::int as sum1, sum(c1) * c2 as sum2 from ft1 group by c2 order by 1, 2;
diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql
index 51560429e0..bfcac4ea14 100644
--- a/contrib/postgres_fdw/sql/postgres_fdw.sql
+++ b/contrib/postgres_fdw/sql/postgres_fdw.sql
@@ -750,9 +750,11 @@ select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
 select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
 
 -- Aggregates in subquery are pushed down.
+set enable_incremental_sort = off;
 explain (verbose, costs off)
 select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
 select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
+reset enable_incremental_sort;
 
 -- Aggregate is still pushed down by taking unshippable expression out
 explain (verbose, costs off)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 0c564be7f6..0cfa3a1d6c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -3207,70 +3207,52 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
 				continue;
 
 			/*
-			 * Consider regular sort for the cheapest partial path (for each
-			 * useful pathkeys). We know the path is not sorted, because we'd
-			 * not get here otherwise.
+			 * Try at least sorting the cheapest path and also try
+			 * incrementally sorting any path which is partially sorted
+			 * already (no need to deal with paths which have presorted keys
+			 * when incremental sort is disabled unless it's the cheapest
+			 * input path).
+			 */
+			if (subpath != cheapest_partial_path &&
+				(presorted_keys == 0 || !enable_incremental_sort))
+				continue;
+
+			/*
+			 * Consider regular sort for any path that's not presorted or if
+			 * incremental sort is disabled.  We've no need to consider both
+			 * sort and incremental sort on the same path.  We assume that
+			 * incremental sort is always faster when there are presorted
+			 * keys.
 			 *
 			 * This is not redundant with the gather paths created in
 			 * generate_gather_paths, because that doesn't generate ordered
 			 * output. Here we add an explicit sort to match the useful
 			 * ordering.
 			 */
-			if (cheapest_partial_path == subpath)
+			if (presorted_keys == 0 || !enable_incremental_sort)
 			{
-				Path	   *tmp;
-
-				tmp = (Path *) create_sort_path(root,
-												rel,
-												subpath,
-												useful_pathkeys,
-												-1.0);
-
-				rows = tmp->rows * tmp->parallel_workers;
-
-				path = create_gather_merge_path(root, rel,
-												tmp,
-												rel->reltarget,
-												tmp->pathkeys,
-												NULL,
-												rowsp);
-
-				add_path(rel, &path->path);
-
-				/* Fall through */
-			}
-
-			/*
-			 * Consider incremental sort, but only when the subpath is already
-			 * partially sorted on a pathkey prefix.
-			 */
-			if (enable_incremental_sort && presorted_keys > 0)
-			{
-				Path	   *tmp;
-
-				/*
-				 * We should have already excluded pathkeys of length 1
-				 * because then presorted_keys > 0 would imply is_sorted was
-				 * true.
-				 */
-				Assert(list_length(useful_pathkeys) != 1);
-
-				tmp = (Path *) create_incremental_sort_path(root,
-															rel,
-															subpath,
-															useful_pathkeys,
-															presorted_keys,
-															-1);
-
-				path = create_gather_merge_path(root, rel,
-												tmp,
-												rel->reltarget,
-												tmp->pathkeys,
-												NULL,
-												rowsp);
-
-				add_path(rel, &path->path);
+				subpath = (Path *) create_sort_path(root,
+													rel,
+													subpath,
+													useful_pathkeys,
+													-1.0);
+				rows = subpath->rows * subpath->parallel_workers;
 			}
+			else
+				subpath = (Path *) create_incremental_sort_path(root,
+																rel,
+																subpath,
+																useful_pathkeys,
+																presorted_keys,
+																-1);
+			path = create_gather_merge_path(root, rel,
+											subpath,
+											rel->reltarget,
+											subpath->pathkeys,
+											NULL,
+											rowsp);
+
+			add_path(rel, &path->path);
 		}
 	}
 }
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 897309d7ec..0f0bcfb7e5 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1959,8 +1959,8 @@ cost_incremental_sort(Path *path,
 					  double input_tuples, int width, Cost comparison_cost, int sort_mem,
 					  double limit_tuples)
 {
-	Cost		startup_cost = 0,
-				run_cost = 0,
+	Cost		startup_cost,
+				run_cost,
 				input_run_cost = input_total_cost - input_startup_cost;
 	double		group_tuples,
 				input_groups;
@@ -1969,10 +1969,9 @@ cost_incremental_sort(Path *path,
 				group_input_run_cost;
 	List	   *presortedExprs = NIL;
 	ListCell   *l;
-	int			i = 0;
 	bool		unknown_varno = false;

 	/*
 
-		i++;

 	/*
 
 	/*
 
 	/*
 
 	/*
 
 	path->rows = input_tuples;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5dd4f92720..dfda251d95 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4965,7 +4965,7 @@ create_ordered_paths(PlannerInfo *root,
 	foreach(lc, input_rel->pathlist)
 	{
 		Path	   *input_path = (Path *) lfirst(lc);
-		Path	   *sorted_path = input_path;
+		Path	   *sorted_path;
 		bool		is_sorted;
 		int			presorted_keys;
 
@@ -4973,69 +4973,46 @@ create_ordered_paths(PlannerInfo *root,
 												input_path->pathkeys, &presorted_keys);
 
 		if (is_sorted)
-		{
-			/* Use the input path as is, but add a projection step if needed */
-			if (sorted_path->pathtarget != target)
-				sorted_path = apply_projection_to_path(root, ordered_rel,
-													   sorted_path, target);
-
-			add_path(ordered_rel, sorted_path);
-		}
+			sorted_path = input_path;
 		else
 		{
 			/*
-			 * Try adding an explicit sort, but only to the cheapest total
-			 * path since a full sort should generally add the same cost to
-			 * all paths.
+			 * Try at least sorting the cheapest path and also try
+			 * incrementally sorting any path which is partially sorted
+			 * already (no need to deal with paths which have presorted keys
+			 * when incremental sort is disabled unless it's the cheapest
+			 * input path).
 			 */
-			if (input_path == cheapest_input_path)
-			{
-				/*
-				 * Sort the cheapest input path. An explicit sort here can
-				 * take advantage of LIMIT.
-				 */
+			if (input_path != cheapest_input_path &&
+				(presorted_keys == 0 || !enable_incremental_sort))
+				continue;
+
+			/*
+			 * We've no need to consider both a sort and incremental sort.
+			 * We'll just do a sort if there are no presorted keys and an
+			 * incremental sort when there are presorted keys.
+			 */
+			if (presorted_keys == 0 || !enable_incremental_sort)
 				sorted_path = (Path *) create_sort_path(root,
 														ordered_rel,
 														input_path,
 														root->sort_pathkeys,
 														limit_tuples);
-				/* Add projection step if needed */
-				if (sorted_path->pathtarget != target)
-					sorted_path = apply_projection_to_path(root, ordered_rel,
-														   sorted_path, target);
-
-				add_path(ordered_rel, sorted_path);
-			}
-
-			/*
-			 * If incremental sort is enabled, then try it as well. Unlike
-			 * with regular sorts, we can't just look at the cheapest path,
-			 * because the cost of incremental sort depends on how well
-			 * presorted the path is. Additionally incremental sort may enable
-			 * a cheaper startup path to win out despite higher total cost.
-			 */
-			if (!enable_incremental_sort)
-				continue;
-
-			/* Likewise, if the path can't be used for incremental sort. */
-			if (!presorted_keys)
-				continue;
-
-			/* Also consider incremental sort. */
-			sorted_path = (Path *) create_incremental_sort_path(root,
-																ordered_rel,
-																input_path,
-																root->sort_pathkeys,
-																presorted_keys,
-																limit_tuples);
+			else
+				sorted_path = (Path *) create_incremental_sort_path(root,
+																	ordered_rel,
+																	input_path,
+																	root->sort_pathkeys,
+																	presorted_keys,
+																	limit_tuples);
+		}
 
-			/* Add projection step if needed */
-			if (sorted_path->pathtarget != target)
-				sorted_path = apply_projection_to_path(root, ordered_rel,
-													   sorted_path, target);
+		/* Add projection step if needed */
+		if (sorted_path->pathtarget != target)
+			sorted_path = apply_projection_to_path(root, ordered_rel,
+												   sorted_path, target);
 
-			add_path(ordered_rel, sorted_path);
-		}
+		add_path(ordered_rel, sorted_path);
 	}
 
 	/*
@@ -6501,12 +6478,12 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 	{
 		/*
+		 * with presorted keys.
 
@@ -6514,90 +6491,39 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 													path->pathkeys,
 													&presorted_keys);
 
+				 * already (no need to deal with paths which have presorted
+				 * keys when incremental sort is disabled unless it's the
+				 * cheapest input path).
+				 * We'll just do a sort if there are no presorted keys and an
+				 * incremental sort when there are presorted keys.
 
-			/*
@@ -6653,7 +6579,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 
@@ -6661,19 +6586,38 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 														path->pathkeys,
 														&presorted_keys);
 
-				/*
-				 * Insert a Sort node, if required.  But there's no point in
-				 * sorting anything but the cheapest path.
-				 */
 				if (!is_sorted)
 				{
-					if (path != partially_grouped_rel->cheapest_total_path)
+					/*
+					 * Try at least sorting the cheapest path and also try
+					 * incrementally sorting any path which is partially
+					 * sorted already (no need to deal with paths which have
+					 * presorted keys when incremental sort is disabled unless
+					 * it's the cheapest input path).
+					 */
+					if (path != partially_grouped_rel->cheapest_total_path &&
+						(presorted_keys == 0 || !enable_incremental_sort))
 						continue;
-					path = (Path *) create_sort_path(root,
-													 grouped_rel,
-													 path,
-													 root->group_pathkeys,
-													 -1.0);
+
+					/*
+					 * We've no need to consider both a sort and incremental
+					 * sort.  We'll just do a sort if there are no pre-sorted
+					 * keys and an incremental sort when there are presorted
+					 * keys.
+					 */
+					if (presorted_keys == 0 || !enable_incremental_sort)
+						path = (Path *) create_sort_path(root,
+														 grouped_rel,
+														 path,
+														 root->group_pathkeys,
+														 -1.0);
+					else
+						path = (Path *) create_incremental_sort_path(root,
+																	 grouped_rel,
+																	 path,
+																	 root->group_pathkeys,
+																	 presorted_keys,
+																	 -1.0);
 				}
 
 				if (parse->hasAggs)
@@ -6697,55 +6641,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
 											   havingQual,
 											   dNumGroups));
 
-				/*
-				 * Now we may consider incremental sort on this path, but only
-				 * when the path is not already sorted and when incremental
-				 * sort is enabled.
-				 */
-				if (is_sorted || !enable_incremental_sort)
-					continue;
-
-				/* Restore the input path (we might have added Sort on top). */
-				path = path_original;
-
-				/* no shared prefix, not point in building incremental sort */
-				if (presorted_keys == 0)
-					continue;
-
-				/*
-				 * We should have already excluded pathkeys of length 1
-				 * because then presorted_keys > 0 would imply is_sorted was
-				 * true.
-				 */
-				Assert(list_length(root->group_pathkeys) != 1);
-
-				path = (Path *) create_incremental_sort_path(root,
-															 grouped_rel,
-															 path,
-															 root->group_pathkeys,
-															 presorted_keys,
-															 -1.0);
-
-				if (parse->hasAggs)
-					add_path(grouped_rel, (Path *)
-							 create_agg_path(root,
-											 grouped_rel,
-											 path,
-											 grouped_rel->reltarget,
-											 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
-											 AGGSPLIT_FINAL_DESERIAL,
-											 parse->groupClause,
-											 havingQual,
-											 agg_final_costs,
-											 dNumGroups));
-				else
-					add_path(grouped_rel, (Path *)
-							 create_group_path(root,
-											   grouped_rel,
-											   path,
-											   parse->groupClause,
-											   havingQual,
-											   dNumGroups));
 			}
 		}
 	}
@@ -6950,97 +6845,64 @@ create_partial_grouping_paths(PlannerInfo *root,
 		{
 			Path	   *path = (Path *) lfirst(lc);
 			bool		is_sorted;
+			int			presorted_keys;
 
-			is_sorted = pathkeys_contained_in(root->group_pathkeys,
-											  path->pathkeys);
-			if (path == cheapest_total_path || is_sorted)
+			is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
+													path->pathkeys,
+													&presorted_keys);
+			if (!is_sorted)
 			{
-				/* Sort the cheapest partial path, if it isn't already */
-				if (!is_sorted)
+				/*
+				 * Try at least sorting the cheapest path and also try
+				 * incrementally sorting any path which is partially sorted
+				 * already (no need to deal with paths which have presorted
+				 * keys when incremental sort is disabled unless it's the
+				 * cheapest input path).
+				 */
+				if (path != cheapest_total_path &&
+					(presorted_keys == 0 || !enable_incremental_sort))
+					continue;
+
+				/*
+				 * We've no need to consider both a sort and incremental sort.
+				 * We'll just do a sort if there are no presorted keys and an
+				 * incremental sort when there are presorted keys.
+				 */
+				if (presorted_keys == 0 || !enable_incremental_sort)
 					path = (Path *) create_sort_path(root,
 													 partially_grouped_rel,
 													 path,
 													 root->group_pathkeys,
 													 -1.0);
-
-				if (parse->hasAggs)
-					add_path(partially_grouped_rel, (Path *)
-							 create_agg_path(root,
-											 partially_grouped_rel,
-											 path,
-											 partially_grouped_rel->reltarget,
-											 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
-											 AGGSPLIT_INITIAL_SERIAL,
-											 parse->groupClause,
-											 NIL,
-											 agg_partial_costs,
-											 dNumPartialGroups));
 				else
-					add_path(partially_grouped_rel, (Path *)
-							 create_group_path(root,
-											   partially_grouped_rel,
-											   path,
-											   parse->groupClause,
-											   NIL,
-											   dNumPartialGroups));
+					path = (Path *) create_incremental_sort_path(root,
+																 partially_grouped_rel,
+																 path,
+																 root->group_pathkeys,
+																 presorted_keys,
+																 -1.0);
 			}
-		}
-
-		/*
-		 * Consider incremental sort on all partial paths, if enabled.
-		 *
-		 * We can also skip the entire loop when we only have a single-item
-		 * group_pathkeys because then we can't possibly have a presorted
-		 * prefix of the list without having the list be fully sorted.
-		 */
-		if (enable_incremental_sort && list_length(root->group_pathkeys) > 1)
-		{
-			foreach(lc, input_rel->pathlist)
-			{
-				Path	   *path = (Path *) lfirst(lc);
-				bool		is_sorted;
-				int			presorted_keys;
-
-				is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
-														path->pathkeys,
-														&presorted_keys);
-
-				/* Ignore already sorted paths */
-				if (is_sorted)
-					continue;
-
-				if (presorted_keys == 0)
-					continue;
 
-				/* Since we have presorted keys, consider incremental sort. */
-				path = (Path *) create_incremental_sort_path(root,
-															 partially_grouped_rel,
-															 path,
-															 root->group_pathkeys,
-															 presorted_keys,
-															 -1.0);
-
-				if (parse->hasAggs)
-					add_path(partially_grouped_rel, (Path *)
-							 create_agg_path(root,
-											 partially_grouped_rel,
-											 path,
-											 partially_grouped_rel->reltarget,
-											 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
-											 AGGSPLIT_INITIAL_SERIAL,
-											 parse->groupClause,
-											 NIL,
-											 agg_partial_costs,
-											 dNumPartialGroups));
-				else
-					add_path(partially_grouped_rel, (Path *)
-							 create_group_path(root,
-											   partially_grouped_rel,
-											   path,
-											   parse->groupClause,
-											   NIL,
-											   dNumPartialGroups));
-			}
+			if (parse->hasAggs)
+				add_path(partially_grouped_rel, (Path *)
+						 create_agg_path(root,
+										 partially_grouped_rel,
+										 path,
+										 partially_grouped_rel->reltarget,
+										 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+										 AGGSPLIT_INITIAL_SERIAL,
+										 parse->groupClause,
+										 NIL,
+										 agg_partial_costs,
+										 dNumPartialGroups));
+			else
+				add_path(partially_grouped_rel, (Path *)
+						 create_group_path(root,
+										   partially_grouped_rel,
+										   path,
+										   parse->groupClause,
+										   NIL,
+										   dNumPartialGroups));
 		}
 	}
 
@@ -7050,7 +6912,6 @@ create_partial_grouping_paths(PlannerInfo *root,
 		foreach(lc, input_rel->partial_pathlist)
 		{
 			Path	   *path = (Path *) lfirst(lc);
-			Path	   *path_original = path;
 			bool		is_sorted;
 			int			presorted_keys;
 
@@ -7058,66 +6919,39 @@ create_partial_grouping_paths(PlannerInfo *root,
 													path->pathkeys,
 													&presorted_keys);
 
-			if (path == cheapest_partial_path || is_sorted)
+			if (!is_sorted)
 			{
-				/* Sort the cheapest partial path, if it isn't already */
-				if (!is_sorted)
+				/*
+				 * Try at least sorting the cheapest path and also try
+				 * incrementally sorting any path which is partially sorted
+				 * already (no need to deal with paths which have presorted
+				 * keys when incremental sort is disabled unless it's the
+				 * cheapest input path).
+				 */
+				if (path != cheapest_partial_path &&
+					(presorted_keys == 0 || !enable_incremental_sort))
+					continue;
+
+				/*
+				 * We've no need to consider both a sort and incremental sort.
+				 * We'll just do a sort if there are no presorted keys and an
+				 * incremental sort when there are presorted keys.
+				 */
+				if (presorted_keys == 0 || !enable_incremental_sort)
 					path = (Path *) create_sort_path(root,
 													 partially_grouped_rel,
 													 path,
 													 root->group_pathkeys,
 													 -1.0);
-
-				if (parse->hasAggs)
-					add_partial_path(partially_grouped_rel, (Path *)
-									 create_agg_path(root,
-													 partially_grouped_rel,
-													 path,
-													 partially_grouped_rel->reltarget,
-													 parse->groupClause ? AGG_SORTED : AGG_PLAIN,
-													 AGGSPLIT_INITIAL_SERIAL,
-													 parse->groupClause,
-													 NIL,
-													 agg_partial_costs,
-													 dNumPartialPartialGroups));
 				else
-					add_partial_path(partially_grouped_rel, (Path *)
-									 create_group_path(root,
-													   partially_grouped_rel,
-													   path,
-													   parse->groupClause,
-													   NIL,
-													   dNumPartialPartialGroups));
+					path = (Path *) create_incremental_sort_path(root,
+																 partially_grouped_rel,
+																 path,
+																 root->group_pathkeys,
+																 presorted_keys,
+																 -1.0);
 			}
 
-			/*
-			 * Now we may consider incremental sort on this path, but only
-			 * when the path is not already sorted and when incremental sort
-			 * is enabled.
-			 */
-			if (is_sorted || !enable_incremental_sort)
-				continue;
-
-			/* Restore the input path (we might have added Sort on top). */
-			path = path_original;
-
-			/* no shared prefix, not point in building incremental sort */
-			if (presorted_keys == 0)
-				continue;
-
-			/*
-			 * We should have already excluded pathkeys of length 1 because
-			 * then presorted_keys > 0 would imply is_sorted was true.
-			 */
-			Assert(list_length(root->group_pathkeys) != 1);
-
-			path = (Path *) create_incremental_sort_path(root,
-														 partially_grouped_rel,
-														 path,
-														 root->group_pathkeys,
-														 presorted_keys,
-														 -1.0);
-
 			if (parse->hasAggs)
 				add_partial_path(partially_grouped_rel, (Path *)
 								 create_agg_path(root,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..1a1e8b2365 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1,16 +1,3 @@
--- When we have to sort the entire table, incremental sort will
--- be slower than plain sort, so it should not be used.
-explain (costs off)
-select * from (select * from tenk1 order by four) t order by four, ten;
-            QUERY PLAN             
------------------------------------
- Sort
-   Sort Key: tenk1.four, tenk1.ten
-   ->  Sort
-         Sort Key: tenk1.four
-         ->  Seq Scan on tenk1
-(5 rows)
-
 -- When there is a LIMIT clause, incremental sort is beneficial because
 -- it only has to sort some of the groups, and not the entire table.
 explain (costs off)
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index b20facc19f..c59caf1cb3 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -1173,8 +1173,9 @@ EXPLAIN (COSTS OFF)
 SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
                         QUERY PLAN                         
 -----------------------------------------------------------
- Sort
+ Incremental Sort
    Sort Key: prt1.a, prt2.b
+   Presorted Key: prt1.a
    ->  Merge Left Join
          Merge Cond: (prt1.a = prt2.b)
          ->  Sort
@@ -1191,7 +1192,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
                            Filter: (b > 250)
                      ->  Seq Scan on prt2_p3 prt2_2
                            Filter: (b > 250)
-(18 rows)
+(19 rows)
 
 SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
   a  |  b  

From 0eb650dd777925d28ff3c47ffbae244f06386d55 Mon Sep 17 00:00:00 2001
From: David Rowley <[email-masked]>
Date: Wed, 14 Dec 2022 10:25:19 +1300
Subject: [PATCH v3 3/3] Add enable_presorted_aggregate GUC

1349d279 added query planner support to allow more efficient execution of
aggregate functions which have an ORDER BY or a DISTINCT clause.  Prior to
that commit, the planner would only request that the lower planner produce
a plan with the order required for the GROUP BY clause and it would be
left up to nodeAgg.c to perform the final sort of records within each
group so that the aggregate transition functions were called in the
correct order.  Now that the planner requests the lower planner produce a
plan with the GROUP BY and the ORDER BY / DISTINCT aggregates in mind,
there is the possibility that the planner chooses a plan which could be
less efficient than what would have been produced before 1349d279.

While developing 1349d279, I had in mind that Incremental Sort would help
us in cases where an index exists only on the GROUP BY column(s).
Incremental Sort would just replace the implicit tuplesorts which are
being performed in nodeAgg.c.  However, because the planner has the
flexibility to instead choose a plan which just performs a full sort on
both the GROUP BY and ORDER BY / DISTINCT aggregate columns, there is
potential for the planner to make a bad choice.  The costing for
Incremental Sort is not perfect as it assumes an even distribution of rows
to sort within each sort group.

Here we add an escape hatch in the form of the enable_presorted_aggregate
GUC.  This will allow users to get the pre-PG16 behavior in cases where
they have no other means to convince the query planner to produce a plan
which only sorts on the GROUP BY column(s).

Discussion: https://postgr.es/m/[email-masked]
---
 doc/src/sgml/config.sgml                      | 23 +++++++++++++++++++
 src/backend/optimizer/path/costsize.c         |  1 +
 src/backend/optimizer/plan/planner.c          |  3 ++-
 src/backend/utils/misc/guc_tables.c           | 15 ++++++++++++
 src/backend/utils/misc/postgresql.conf.sample |  1 +
 src/include/optimizer/cost.h                  |  1 +
 src/test/regress/expected/aggregates.out      | 11 +++++++++
 src/test/regress/expected/sysviews.out        |  3 ++-
 src/test/regress/sql/aggregates.sql           |  6 +++++
 9 files changed, 62 insertions(+), 2 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 8e4145979d..9eedab652d 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5311,6 +5311,29 @@ ANY <replaceable class="parameter">num_sync</replaceable> ( <replaceable class="
       </listitem>
      </varlistentry>
 
+     <varlistentry id="guc-enable-presorted-aggregate" xreflabel="enable_presorted_aggregate">
+      <term><varname>enable_presorted_aggregate</varname> (<type>boolean</type>)
+      <indexterm>
+       <primary><varname>enable_presorted_aggregate</varname> configuration parameter</primary>
+      </indexterm>
+      </term>
+      <listitem>
+       <para>
+        Controls if the query planner will produce a plan which will provide
+        rows which are presorted in the order required for the query's
+        <literal>ORDER BY</literal> / <literal>DISTINCT</literal> aggregate
+        functions.  When disabled, the query planner will produce a plan which
+        will always require the executor to perform a sort before performing
+        aggregation of each aggregate function containing an
+        <literal>ORDER BY</literal> or <literal>DISTINCT</literal> clause.
+        When enabled, the planner will try to produce a more efficient plan
+        which provides input to the aggregate functions which is presorted in
+        the order they require for aggregation.  The default value is
+        <literal>on</literal>.
+       </para>
+      </listitem>
+     </varlistentry>
+
      <varlistentry id="guc-enable-seqscan" xreflabel="enable_seqscan">
       <term><varname>enable_seqscan</varname> (<type>boolean</type>)
       <indexterm>
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 0f0bcfb7e5..89d3c4352c 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -151,6 +151,7 @@ bool		enable_partitionwise_aggregate = false;
 bool		enable_parallel_append = true;
 bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
+bool		enable_presorted_aggregate = true;
 bool		enable_async_append = true;
 
 typedef struct
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index dfda251d95..e21e72eb87 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3191,7 +3191,8 @@ make_pathkeys_for_groupagg(PlannerInfo *root, List *groupClause, List *tlist,
 	 * sets.  All handling specific to ordered aggregates must be done by the
 	 * executor in that case.
 	 */
-	if (root->numOrderedAggs == 0 || root->parse->groupingSets != NIL)
+	if (root->numOrderedAggs == 0 || root->parse->groupingSets != NIL ||
+		!enable_presorted_aggregate)
 		return grouppathkeys;
 
 	/*
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 1bf14eec66..436afe1d21 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -971,6 +971,21 @@ struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_presorted_aggregate", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables the planner's ability to produce plans which "
+						 "provide presorted input for ORDER BY / DISTINCT aggregate "
+						 "functions."),
+			gettext_noop("Allows the query planner to build plans which provide "
+						 "presorted input for aggregate functions with an ORDER BY / "
+						 "DISTINCT clause.  When disabled, implicit sorts are always "
+						 "performed during execution."),
+			GUC_EXPLAIN
+		},
+		&enable_presorted_aggregate,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		{"enable_async_append", PGC_USERSET, QUERY_TUNING_METHOD,
 			gettext_noop("Enables the planner's use of async append plans."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 043864597f..5afdeb04de 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -384,6 +384,7 @@
 #enable_partition_pruning = on
 #enable_partitionwise_join = off
 #enable_partitionwise_aggregate = off
+#enable_presorted_aggregate = on
 #enable_seqscan = on
 #enable_sort = on
 #enable_tidscan = on
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 204e94b6d1..b6cc2c9cd6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -68,6 +68,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
 extern PGDLLIMPORT bool enable_parallel_append;
 extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_presorted_aggregate;
 extern PGDLLIMPORT bool enable_async_append;
 extern PGDLLIMPORT int constraint_exclusion;
 
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index fc2bd40be2..309c2dc865 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1471,6 +1471,17 @@ group by ten;
          ->  Seq Scan on tenk1
 (5 rows)
 
+-- Ensure no ordering is requested when enable_presorted_aggregate is off
+set enable_presorted_aggregate to off;
+explain (costs off)
+select sum(two order by two) from tenk1;
+       QUERY PLAN        
+-------------------------
+ Aggregate
+   ->  Seq Scan on tenk1
+(2 rows)
+
+reset enable_presorted_aggregate;
 --
 -- Test combinations of DISTINCT and/or ORDER BY
 --
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 579b861d84..001c6e7eb9 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -128,10 +128,11 @@ select name, setting from pg_settings where name like 'enable%';
  enable_partition_pruning       | on
  enable_partitionwise_aggregate | off
  enable_partitionwise_join      | off
+ enable_presorted_aggregate     | on
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(20 rows)
+(21 rows)
 
 -- Test that the pg_timezone_names and pg_timezone_abbrevs views are
 -- more-or-less working.  We can't test their contents in any great detail
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index a4c00ff7a9..15f6be8e15 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -546,6 +546,12 @@ select
 from tenk1
 group by ten;
 
+-- Ensure no ordering is requested when enable_presorted_aggregate is off
+set enable_presorted_aggregate to off;
+explain (costs off)
+select sum(two order by two) from tenk1;
+reset enable_presorted_aggregate;
+
 --
 -- Test combinations of DISTINCT and/or ORDER BY
 --
-- 
2.35.1.windows.2

---

From: David Rowley <[email-masked]>
Date: Fri, 16 Dec 2022 15:26:20 +1300

> keys. I'm happy to see just how much redundant code this removes.

I've now pushed this patch. Thanks for the report and everyone for all
the useful discussion. Also Richard for the review.

> v3-0003 adds the enable_presorted_aggregate GUC.

This I've moved off to [1]. We tend to have lengthy discussions about
GUCs, what to name them and if we actually need them. I didn't want to
bury that discussion in this old and already long thread.

David

[1] https://postgr.es/m/CAApHDvqzuHerD8zN1Qu=d66e3bp1=[email-masked]