Subject: Re: Eager aggregation, take 3

From: Richard Guo <[email-masked]>
Date: Wed, 3 Jul 2024 16:29:27 +0800

On Thu, Jun 13, 2024 at 4:07 PM Richard Guo <[email-masked]> wrote:
> I spent some time testing this patchset and found a few more issues.
> ...

> Hence here is the v8 patchset, with fixes for all the above issues.

I found an 'ORDER/GROUP BY expression not found in targetlist' error
with this patchset, with the query below:

create table t (a boolean);

set enable_eager_aggregate to on;

explain (costs off)
select min(1) from t t1 left join t t2 on t1.a group by (not (not
t1.a)), t1.a order by t1.a;
ERROR:  ORDER/GROUP BY expression not found in targetlist

This happens because the two grouping items are actually the same and
standard_qp_callback would remove one of them.  The fully-processed
groupClause is kept in root->processed_groupClause.  However, when
collecting grouping expressions in create_grouping_expr_infos, we are
checking parse->groupClause, which is incorrect.

The fix is straightforward: check root->processed_groupClause instead.

Here is a new rebase with this fix.

Thanks
Richard

---

From: Paul George <[email-masked]>
Date: Sat, 6 Jul 2024 19:45:32 -0700

Richard:

Thanks for reviving this patch and for all of your work on it! Eager
aggregation pushdown will be beneficial for my work and I'm hoping to see
it land.

I was playing around with v9 of the patches and was specifically curious
about this previous statement...

>This patch also makes eager aggregation work with outer joins.  With
>outer join, the aggregate cannot be pushed down if any column referenced
>by grouping expressions or aggregate functions is nullable by an outer
>join above the relation to which we want to apply the partiall
>aggregation.  Thanks to Tom's outer-join-aware-Var infrastructure, we
>can easily identify such situations and subsequently refrain from
>pushing down the aggregates.

 ...and this related comment in eager_aggregate.out:

>-- Ensure aggregation cannot be pushed down to the nullable side

While I'm new to this work and its subtleties, I'm wondering if this is too
broad a condition.

I modified the first test query in eager_aggregate.sql to make it a LEFT
JOIN and eager aggregation indeed did not happen, which is expected based
on the comments upthread.

query:
SET enable_eager_aggregate=ON;
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.a, sum(t2.c) FROM eager_agg_t1 t1 LEFT JOIN eager_agg_t2 t2 ON
t1.b = t2.b GROUP BY t1.a ORDER BY t1.a;

plan:
                         QUERY PLAN
------------------------------------------------------------
 GroupAggregate
   Output: t1.a, sum(t2.c)
   Group Key: t1.a
   ->  Sort
         Output: t1.a, t2.c
         Sort Key: t1.a
         ->  Hash Right Join
               Output: t1.a, t2.c
               Hash Cond: (t2.b = t1.b)
               ->  Seq Scan on public.eager_agg_t2 t2
                     Output: t2.a, t2.b, t2.c
               ->  Hash
                     Output: t1.a, t1.b
                     ->  Seq Scan on public.eager_agg_t1 t1
                           Output: t1.a, t1.b
(15 rows)

(NOTE: I changed the aggregate from avg(...) to sum(...) for simplicity)

But, it seems that eager aggregation for the query above can be
"replicated" as:

query:

EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.a, sum(t2.c)
FROM eager_agg_t1 t1
LEFT JOIN (
    SELECT b, sum(c) c
    FROM eager_agg_t2 t2p
    GROUP BY b
) t2 ON t1.b = t2.b
GROUP BY t1.a
ORDER BY t1.a;

The output of both the original query and this one match (and the plans
with eager aggregation and the subquery are nearly identical if you restore
the LEFT JOIN to a JOIN). I admittedly may be missing a subtlety, but does
this mean that there are conditions under which eager aggregation can be
pushed down to the nullable side?

-Paul-

---

From: Richard Guo <[email-masked]>
Date: Wed, 10 Jul 2024 16:27:02 +0800

On Sun, Jul 7, 2024 at 10:45 AM Paul George <[email-masked]> wrote:
> Thanks for reviving this patch and for all of your work on it! Eager aggregation pushdown will be beneficial for my work and I'm hoping to see it land.

Thanks for looking at this patch!

> The output of both the original query and this one match (and the plans with eager aggregation and the subquery are nearly identical if you restore the LEFT JOIN to a JOIN). I admittedly may be missing a subtlety, but does this mean that there are conditions under which eager aggregation can be pushed down to the nullable side?

I think it's a very risky thing to push a partial aggregation down to
the nullable side of an outer join, because the NULL-extended rows
produced by the outer join would not be available when we perform the
partial aggregation, while with a non-eager-aggregation plan these
rows are available for the top-level aggregation.  This may put the
rows into groups in a different way than expected, or get wrong values
from the aggregate functions.  I've managed to compose an example:

create table t (a int, b int);
insert into t select 1, 1;

select t2.a, count(*) from t t1 left join t t2 on t2.b > 1 group by
t2.a having t2.a is null;
 a | count
---+-------
   |     1
(1 row)

This is the expected result, because after the outer join we have got
a NULL-extended row.

But if we somehow push down the partial aggregation to the nullable
side of this outer join, we would get a wrong result.

explain (costs off)
select t2.a, count(*) from t t1 left join t t2 on t2.b > 1 group by
t2.a having t2.a is null;
                QUERY PLAN
-------------------------------------------
 Finalize HashAggregate
   Group Key: t2.a
   ->  Nested Loop Left Join
         Filter: (t2.a IS NULL)
         ->  Seq Scan on t t1
         ->  Materialize
               ->  Partial HashAggregate
                     Group Key: t2.a
                     ->  Seq Scan on t t2
                           Filter: (b > 1)
(10 rows)

select t2.a, count(*) from t t1 left join t t2 on t2.b > 1 group by
t2.a having t2.a is null;
 a | count
---+-------
   |     0
(1 row)

I believe there are cases where pushing a partial aggregation down to
the nullable side of an outer join can be safe, but I doubt that there
is an easy way to identify these cases and do the push-down for them.
So for now I think we'd better refrain from doing that.

Thanks
Richard

---

From: Paul George <[email-masked]>
Date: Thu, 11 Jul 2024 14:50:35 -0700

Hey Richard,

Looking more closely at this example

>select t2.a, count(*) from t t1 left join t t2 on t2.b > 1 group by t2.a
having t2.a is null;

I wonder if the inability to exploit eager aggregation is more based on the
fact that COUNT(*) cannot be decomposed into an aggregation of PARTIAL
COUNT(*)s (apologies if my terminology is off/made up...I'm new to the
codebase). In other words, is it the case that a given aggregate function
already has built-in protection against the error case you correctly
pointed out?

To highlight this, in the simple example below we don't see aggregate
pushdown even with an INNER JOIN when the agg function is COUNT(*) but we
do when it's COUNT(t2.*):

-- same setup
drop table if exists t;
create table t(a int, b int, c int);
insert into t select i % 100, i % 10, i from generate_series(1, 1000) i;
analyze t;

-- query 1: COUNT(*) --> no pushdown

set enable_eager_aggregate=on;
explain (verbose, costs off) select t1.a, count(*) from t t1 join t t2 on
t1.a=t2.a group by t1.a;

                QUERY PLAN
-------------------------------------------
 HashAggregate
   Output: t1.a, count(*)
   Group Key: t1.a
   ->  Hash Join
         Output: t1.a
         Hash Cond: (t1.a = t2.a)
         ->  Seq Scan on public.t t1
               Output: t1.a, t1.b, t1.c
         ->  Hash
               Output: t2.a
               ->  Seq Scan on public.t t2
                     Output: t2.a
(12 rows)

-- query 2: COUNT(t2.*) --> agg pushdown

set enable_eager_aggregate=on;
explain (verbose, costs off) select t1.a, count(t2.*) from t t1 join t t2
on t1.a=t2.a group by t1.a;

                      QUERY PLAN
-------------------------------------------------------
 Finalize HashAggregate
   Output: t1.a, count(t2.*)
   Group Key: t1.a
   ->  Hash Join
         Output: t1.a, (PARTIAL count(t2.*))
         Hash Cond: (t1.a = t2.a)
         ->  Seq Scan on public.t t1
               Output: t1.a, t1.b, t1.c
         ->  Hash
               Output: t2.a, (PARTIAL count(t2.*))
               ->  Partial HashAggregate
                     Output: t2.a, PARTIAL count(t2.*)
                     Group Key: t2.a
                     ->  Seq Scan on public.t t2
                           Output: t2.*, t2.a
(15 rows)

...while it might be true that COUNT(*) ... INNER JOIN should allow eager
agg pushdown (I haven't thought deeply about it, TBH), I did find this
result pretty interesting.

-Paul

---

From: Richard Guo <[email-masked]>
Date: Fri, 16 Aug 2024 16:14:41 +0800

I had a self-review of this patchset and made some refactoring,
especially to the function that creates the RelAggInfo structure for a
given relation.  While there were no major changes, the code should
now be simpler.

Attached is the updated version of the patchset.  Previously, the
patchset was not well-split, which made it time-consuming to
distribute the changes across the patches during the refactoring.  So
I squashed them into two patches to save effort.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Wed, 21 Aug 2024 15:10:51 +0800

> given relation.  While there were no major changes, the code should

I found a bug in v10 patchset: when we generate the GROUP BY clauses
for the partial aggregation that is pushed down to a non-aggregated
relation, we may produce a clause with a tleSortGroupRef that
duplicates one already present in the query's groupClause, which would
cause problems.

Attached is the updated version of the patchset that fixes this bug
and includes further code refactoring.

Thanks
Richard

---

From: Robert Haas <[email-masked]>
Date: Fri, 23 Aug 2024 11:59:17 -0400

> and includes further code refactoring.

Here are some initial, high-level thoughts about this patch set.

1. As far as I can see, there's no real performance testing on this
thread. I expect that it's possible to show an arbitrarily large gain
for the patch by finding a case where partial aggregation is way
better than anything we currently know, but that's not very
interesting. What I think would be useful to do is find a corpus of
existing queries on an existing data set and try them with and without
the patch and see which query plans change and whether they're
actually better. For example, maybe TPC-H or the subset of TPC-DS that
we can actually run would be a useful starting point. One could then
also measure how much the planning time increases with the patch to
get a sense of what the overhead of enabling this feature would be.
Even if it's disabled by default, people aren't going to want to
enable it if it causes planning times to become much longer on many
queries for which there is no benefit.

2. I think there might be techniques we could use to limit planning
effort at an earlier stage when the approach doesn't appear promising.
For example, if the proposed grouping column is already unique, the
exercise is pointless (I think). Ideally we'd like to detect that
without even creating the grouped_rel. But the proposed grouping
column might also be *mostly* unique. For example, consider a table
with a million rows and a column 500,000 distinct values. I suspect it
will be difficult for partial aggregation to work out to a win in a
case like this, because I think that the cost of performing the
partial aggregation will not reduce the cost either of the final
aggregation or of the intervening join steps by enough to compensate.
It would be best to find a way to avoid generating a lot of rels and
paths in cases where there's really not much hope of a win.

One could, perhaps, imagine going further with this by postponing
eager aggregation planning until after regular paths have been built,
so that we have good cardinality estimates. Suppose the query joins a
single fact table to a series of dimension tables. The final plan thus
uses the fact table as the driving table and joins to the dimension
tables one by one. Do we really need to consider partial aggregation
at every level? Perhaps just where there's been a significant row
count reduction since the last time we tried it, but at the next level
the row count will increase again?

Maybe there are other heuristics we could use in addition or instead.

3. In general, we are quite bad at estimating what will happen to the
row count after an aggregation, and we have no real idea what the
distribution of values will be. That might be a problem for this
patch, because it seems like the decisions we will make about where to
perform the partial aggregation might end up being quite random. At
the top of the join tree, I'll need to compare directly aggregating
the best join path with various paths that involve a finalize
aggregation step at the top and a partial aggregation step further
down. But my cost estimates and row counts for the partial aggregate
steps seem like they will often be quite poor, which means that the
plans that use those partial aggregate steps might also be quite poor.
Even if they're not, I fear that comparing the cost of those
PartialAggregate-Join(s)-FinalizeAggregate paths to the direct
Aggregate path will look too much like comparing random numbers. We
need to know whether the combination of the FinalizeAggregate step and
the PartialAggregate step will be more or less expensive than a plain
old Aggregate, but how can we tell that if we don't have accurate
cardinality estimates?

Thanks for working on this.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

---

From: Tender Wang <[email-masked]>
Date: Wed, 28 Aug 2024 11:57:12 +0800

> and includes further code refactoring.

Rectenly, I do some benchmark tests, mainly on tpch and tpcds.
tpch tests have no plan diff, so I do not continue to test on tpch.
tpcds(10GB) tests have 22 plan diff as below:
4.sql, 5.sql, 8.sql,11.sql,19.sql,23.sql,31.sql,
33.sql,39.sql,45.sql,46.sql,47.sql,53.sql,
56.sql,57.sql,60.sql,63.sql,68.sql,74.sql,77.sql,80.sql,89.sql

I haven't look all of them. I just pick few simple plan test(e.g. 19.sql,
45.sql).
For example, 19.sql, eager agg pushdown doesn't get large gain, but a little
performance regress.

I will continue to do benchmark on this feature.

[1] https://github.com/tenderwg/eager_agg

-- 
Tender Wang

---

From: Robert Haas <[email-masked]>
Date: Wed, 28 Aug 2024 09:00:57 -0400

> tpch tests have no plan diff, so I do not continue to test on tpch.

Interesting to know.

> 4.sql, 5.sql, 8.sql,11.sql,19.sql,23.sql,31.sql, 33.sql,39.sql,45.sql,46.sql,47.sql,53.sql,

OK.

> I haven't look all of them. I just pick few simple plan test(e.g. 19.sql, 45.sql).

Yeah, this is one of the things I was worried about in my previous
reply to Richard. It would be worth Richard, or someone, probing into
exactly why that's happening. My fear is that we just don't have good
enough estimates to make good decisions, but there might well be
another explanation.

> [1] https://github.com/tenderwg/eager_agg

Thanks!

---

From: Richard Guo <[email-masked]>
Date: Thu, 29 Aug 2024 10:26:01 +0800

> Here are some initial, high-level thoughts about this patch set.

Thank you for your review and feedback!  It helps a lot in moving this
work forward.

> queries for which there is no benefit.

Right.  I haven’t had time to run any benchmarks yet, but that is
something I need to do.

> Maybe there are other heuristics we could use in addition or instead.

Yeah, one of my concerns with this work is that it can use
significantly more CPU time and memory during planning once enabled.
It would be great if we have some efficient heuristics to limit the
effort.  I'll work on that next and see what happens.

> old Aggregate, but how can we tell that if we don't have accurate

Yeah, I'm concerned about this too.  In addition to the inaccuracies
in aggregation estimates, our estimates for joins are sometimes not
very accurate either.  All this are likely to result in regressions
with eager aggregation in some cases.  Currently I don't have a good
answer to this problem.  Maybe we can run some benchmarks first and
investigate the regressions discovered on a case-by-case basis to better
understand the specific issues.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Thu, 29 Aug 2024 10:29:26 +0800

> I will continue to do benchmark on this feature.

Thank you for running the benchmarks.  That really helps a lot.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Thu, 29 Aug 2024 10:45:58 +0800

> enough estimates to make good decisions, but there might well be

It's great that we have a query to probe into.  Your guess is likely
correct: it may be caused by poor estimates.

Tender, would you please help provide the outputs of

EXPLAIN (COSTS ON, ANALYZE)

on 19.sql with and without eager aggregation?

> > I will continue to do benchmark on this feature.

Thanks again for running the benchmarks.

Thanks
Richard

---

From: Tender Wang <[email-masked]>
Date: Thu, 29 Aug 2024 11:22:24 +0800

> on 19.sql with and without eager aggregation?

Yeah, in [1], 19_off.out and 19_on.out are the output of explain(costs off,
analyze).
I will do EXPLAIN(COSTS ON, ANALYZE) tests and upload them later today.

-- 
Tender Wang

---

From: Tender Wang <[email-masked]>
Date: Thu, 29 Aug 2024 11:38:11 +0800

Richard Guo <[email-masked]> 于2024年8月29日周四 10:46写道：

> I upload EXPLAIN(COSTS ON, ANALYZE) test to [1].
I ran the same query three times, and I chose the third time result.
You can check 19_off_explain.out and 19_on_explain.out.

-- 
Tender Wang

---

From: Robert Haas <[email-masked]>
Date: Thu, 29 Aug 2024 08:40:09 -0400

> understand the specific issues.

While it's true that we can make mistakes during join estimation, I
believe aggregate estimation tends to be far worse.

---

From: Robert Haas <[email-masked]>
Date: Thu, 29 Aug 2024 09:02:10 -0400

> You can check 19_off_explain.out and 19_on_explain.out.

So, in 19_off_explain.out, we got this:

         ->  Finalize GroupAggregate  (cost=666986.48..667015.35
rows=187 width=142) (actual time=272.649..334.318 rows=900 loops=1)
               ->  Gather Merge  (cost=666986.48..667010.21 rows=187
width=142) (actual time=272.644..333.847 rows=901 loops=1)
                     ->  Partial GroupAggregate
(cost=665986.46..665988.60 rows=78 width=142) (actual
time=266.379..267.476 rows=300 loops=3)
                           ->  Sort  (cost=665986.46..665986.65
rows=78 width=116) (actual time=266.367..266.583 rows=5081 loops=3)

And in 19_on_explan.out, we got this:

         ->  Finalize GroupAggregate  (cost=666987.03..666989.77
rows=19 width=142) (actual time=285.018..357.374 rows=900 loops=1)
               ->  Gather Merge  (cost=666987.03..666989.25 rows=19
width=142) (actual time=285.000..352.793 rows=15242 loops=1)
                     ->  Sort  (cost=665987.01..665987.03 rows=8
width=142) (actual time=273.391..273.580 rows=5081 loops=3)
                           ->  Nested Loop  (cost=665918.00..665986.89
rows=8 width=142) (actual time=252.667..269.719 rows=5081 loops=3)
                                 ->  Nested Loop
(cost=665917.85..665985.43 rows=8 width=157) (actual
time=252.656..264.755 rows=5413 loops=3)
                                       ->  Partial GroupAggregate
(cost=665917.43..665920.10 rows=82 width=150) (actual
time=252.643..255.627 rows=5413 loops=3)
                                             ->  Sort
(cost=665917.43..665917.64 rows=82 width=124) (actual
time=252.636..252.927 rows=5413 loops=3)

So, the patch was expected to cause the number of rows passing through
the Gather Merge to decrease from 197 to 19, but actually caused the
number of rows passing through the Gather Merge to increase from 901
to 15242. When the PartialAggregate was positioned at the top of the
join tree, it reduced the number of rows from 5081 to 300; but when it
was pushed down below two joins, it didn't reduce the row count at
all, and the subsequent two joins reduced it by less than 10%.

Now, you could complain about the fact that the Parallel Hash Join
isn't well-estimated here, but my question is: why does the planner
think that the PartialAggregate should go specifically here? In both
plans, the PartialAggregate isn't expected to change the row count.
And if that is true, then it's going to be cheapest to do it at the
point where the joins have reduced the row count to the minimum value.
Here, that would be at the top of the plan tree, where we have only
5081 estimated rows, but instead, the patch chooses to do it as soon
as we have all of the grouping columns, when we. still have 5413 rows.
I don't understand why that path wins on cost, unless it's just that
the paths compare fuzzily the same, in which case it kind of goes to
my earlier point about not really having the statistics to know which
way is actually going to be better.

---

From: Tender Wang <[email-masked]>
Date: Wed, 4 Sep 2024 11:48:30 +0800

> and includes further code refactoring.

The v11-0002 git am failed on HEAD(6c2b5edecc).

tender@iZ2ze6la2dizi7df9q3xheZ:/workspace/postgres$ git am
v11-0002-Implement-Eager-Aggregation.patch
Applying: Implement Eager Aggregation
error: patch failed: src/test/regress/parallel_schedule:119
error: src/test/regress/parallel_schedule: patch does not apply
Patch failed at 0001 Implement Eager Aggregation
hint: Use 'git am --show-current-patch=diff' to see the failed patch
When you have resolved this problem, run "git am --continue".
If you prefer to skip this patch, run "git am --skip" instead.
To restore the original branch and stop patching, run "git am --abort".

-- 
Thanks,
Tender Wang

---

From: Tender Wang <[email-masked]>
Date: Thu, 5 Sep 2024 09:40:18 +0800

> and includes further code refactoring.

 I review the v11 patch set, and here are a few of my thoughts:

1.  in setup_eager_aggregation(), before calling create_agg_clause_infos(),
it does
some checks if eager aggregation is available. Can we move those checks
into a function,
for example, can_eager_agg(), like can_partial_agg() does?

2.  I found that outside of joinrel.c we all use IS_DUMMY_REL,  but in
joinrel.c, Tom always uses
is_dummy_rel(). Other commiters use IS_DUMMY_REL.

3.  The attached patch does not consider FDW when creating a path for
grouped_rel or grouped_join.
Do we need to think about FDW?

I haven't finished reviewing the patch set. I will continue to learn this
feature.

-- 
Thanks,
Tender Wang

---

From: Tender Wang <[email-masked]>
Date: Wed, 11 Sep 2024 10:52:05 +0800

> and includes further code refactoring.
I continue to review the v11 version patches. Here are some my thoughts.

1. In make_one_rel(), we have the below codes:
/*
* Build grouped base relations for each base rel if possible.
*/
setup_base_grouped_rels(root);

As far as I know, each base rel only has one grouped base relation, if
possible.
The comments may be changed to "Build a grouped base relation for each base
rel if possible."

2.  According to the comments of generate_grouped_paths(), we may generate
paths for a grouped
relation on top of paths of join relation. So the ”rel_plain" argument in
generate_grouped_paths() may be
confused. "plain" usually means "base rel" . How about Re-naming rel_plain
to input_rel?

3. In create_partial_grouping_paths(), The partially_grouped_rel could have
been already created due to eager
aggregation. If partially_grouped_rel exists,  its reltarget has been
created. So do we need below logic?

/*
* Build target list for partial aggregate paths.  These paths cannot just
* emit the same tlist as regular aggregate paths, because (1) we must
* include Vars and Aggrefs needed in HAVING, which might not appear in
* the result tlist, and (2) the Aggrefs must be set in partial mode.
*/
partially_grouped_rel->reltarget =
       make_partial_grouping_target(root, grouped_rel->reltarget,
                                                        extra->havingQual);

--
Thanks,
Tender Wang

---

From: Tender Wang <[email-masked]>
Date: Fri, 13 Sep 2024 15:48:20 +0800

> To restore the original branch and stop patching, run "git am --abort".
Since MERGE/SPLIT partition has been reverted, the tests  *partition_merge*
and  *partition_split*  should be removed
from parallel_schedule. After doing the above, the 0002 patch can be
applied.

-- 
Thanks,
Tender Wang

---

From: Richard Guo <[email-masked]>
Date: Wed, 25 Sep 2024 11:20:14 +0800

> enough estimates to make good decisions, but there might well be

Sorry it takes some time to switch back to this thread.

I revisited the part about cost estimates for grouped paths in this
patch, and I found a big issue: the row estimate for a join path could
be significantly inaccurate if there is a grouped join path beneath
it.

The reason is that it is very tricky to set the size estimates for a
grouped join relation.  For a non-grouped join relation, we know that
all its paths have the same rowcount estimate (well, in theory).  But
this is not true for a grouped join relation.  Suppose we have a
grouped join relation for t1/t2 join.  There might be two paths for
it:

Aggregate
    -> Join
        -> Scan on t1
        -> Scan on t2

Or

Join
 -> Scan on t1
 -> Aggregate
     -> Scan on t2

These two paths can have very different rowcount estimates, and we
have no way of knowing which one to set for this grouped join
relation, because we do not know which path would be picked in the
final plan.  This issue can be illustrated with the query below.

create table t (a int, b int, c int);
insert into t select i%10, i%10, i%10 from generate_series(1,1000)i;
analyze t;

explain (costs on)
select sum(t2.c) from t t1 join t t2 on t1.a = t2.a join t t3 on t2.b
= t3.b group by t3.a;
                                      QUERY PLAN
---------------------------------------------------------------------------------------
 Finalize HashAggregate  (cost=6840.60..6840.70 rows=10 width=12)
   Group Key: t3.a
   ->  Nested Loop  (cost=1672.00..1840.60 rows=1000000 width=12)
         Join Filter: (t2.b = t3.b)
         ->  Partial HashAggregate  (cost=1672.00..1672.10 rows=10 width=12)
               Group Key: t2.b
               ->  Hash Join  (cost=28.50..1172.00 rows=100000 width=8)
                     Hash Cond: (t1.a = t2.a)
                     ->  Seq Scan on t t1  (cost=0.00..16.00 rows=1000 width=4)
                     ->  Hash  (cost=16.00..16.00 rows=1000 width=12)
                           ->  Seq Scan on t t2  (cost=0.00..16.00
rows=1000 width=12)
         ->  Materialize  (cost=0.00..21.00 rows=1000 width=8)
               ->  Seq Scan on t t3  (cost=0.00..16.00 rows=1000 width=8)
(13 rows)

Look at the Nested Loop node:

   ->  Nested Loop  (cost=1672.00..1840.60 rows=1000000 width=12)

How can a 10-row outer path joining a 1000-row inner path generate
1000000 rows?  This is because we are using the plan of the first path
described above, and the rowcount estimate of the second path.  What a
kluge!

To address this issue, one solution I’m considering is to recalculate
the row count estimate for a grouped join path using its outer and
inner paths.  While this may seem expensive, it might not be that bad
since we will cache the results of the selectivity calculation.  In
fact, this is already the approach we take for parameterized join
paths (see get_parameterized_joinrel_size).

Any thoughts on this?

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Wed, 25 Sep 2024 14:55:00 +0800

On Thu, Sep 5, 2024 at 9:40 AM Tender Wang <[email-masked]> wrote:
> 1.  in setup_eager_aggregation(), before calling create_agg_clause_infos(), it does
> some checks if eager aggregation is available. Can we move those checks into a function,

We can do this, but I'm not sure this would be better.

> 2.  I found that outside of joinrel.c we all use IS_DUMMY_REL,  but in joinrel.c, Tom always uses

They are essentially the same: IS_DUMMY_REL() is a macro that wraps
is_dummy_rel().  I think they are interchangeable, and I don’t have a
preference for which one is better.

> 3.  The attached patch does not consider FDW when creating a path for grouped_rel or grouped_join.

We may add support for foreign relations in the future, but for now, I
think we'd better not expand the scope too much until we ensure that
everything is working correctly.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Wed, 25 Sep 2024 15:02:51 +0800

On Wed, Sep 11, 2024 at 10:52 AM Tender Wang <[email-masked]> wrote:
> As far as I know, each base rel only has one grouped base relation, if possible.
> The comments may be changed to "Build a grouped base relation for each base rel if possible."

Yeah, each base rel has only one grouped rel.  However, there is a
comment nearby stating 'consider_parallel flags for each base rel',
which confuses me about whether it should be singular or plural in
this context.  Perhaps someone more proficient in English could
clarify this.

> 2.  According to the comments of generate_grouped_paths(), we may generate paths for a grouped
> relation on top of paths of join relation. So the ”rel_plain" argument in generate_grouped_paths() may be
> confused. "plain" usually means "base rel" . How about Re-naming rel_plain to input_rel?

I don't think 'plain relation' necessarily means 'base relation'.  In
this context I think it can mean 'non-grouped relation'.  But maybe
I'm wrong.

> 3. In create_partial_grouping_paths(), The partially_grouped_rel could have been already created due to eager
> aggregation. If partially_grouped_rel exists,  its reltarget has been created. So do we need below logic?
>
> /*

Yeah, maybe we can avoid building the target list here for
partially_grouped_rel that is generated by eager aggregation.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Wed, 25 Sep 2024 15:12:57 +0800

On Fri, Sep 13, 2024 at 3:48 PM Tender Wang <[email-masked]> wrote:
> Since MERGE/SPLIT partition has been reverted, the tests  *partition_merge* and  *partition_split*  should be removed
> from parallel_schedule. After doing the above, the 0002 patch can be applied.

Yeah, that's what I need to do.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Fri, 27 Sep 2024 11:53:43 +0800

> paths (see get_parameterized_joinrel_size).

Here is an updated version of this patch that fixes the rowcount
estimate issue along this routine. (see set_joinpath_size.)

Now the Nested Loop node looks like:

   ->  Nested Loop  (cost=1672.00..1840.60 rows=1000 width=12)
                    (actual time=119.685..122.841 rows=1000 loops=1)

Its rowcount estimate looks much more sane now.

But wait, why are we using nestloop here?  My experience suggests that
hashjoin typically outperforms nestloop with input paths of this size
on this type of dataset.

The thing is, the first path (join-then-aggregate one) of the t1/t2
grouped join relation has a much fewer rowcount but more expensive
costs:

   :path.rows 10
   :path.disabled_nodes 0
   :path.startup_cost 1672
   :path.total_cost 1672.1

And the second path (aggregate-then-join one) has cheaper costs but
more rows.

   :jpath.path.rows 10000
   :jpath.path.disabled_nodes 0
   :jpath.path.startup_cost 25.75
   :jpath.path.total_cost 156.75

Both paths have survived the add_path() tournament for this relation,
and the second one is selected as the cheapest path by set_cheapest,
which mainly uses costs and then pathkeys as the selection criterion.
The rowcount estimate is not taken into account, which is reasonable
because unparameterized paths for the same relation usually have the
same rowcount estimate.  And when creating hashjoins, we only consider
the cheapest input paths.  This is why we are unable to generate a
hashjoin with the first path.

However, the situation changes with grouped relations, as different
paths of a grouped relation can have very different row counts.  To
cope with this, I modified set_cheapest() to also find the fewest-row
unparameterized path if the relation is a grouped relation, and
include it in the cheapest_parameterized_paths list.  It could be
argued that this will increase the overall planning time a lot because
it adds one more path to cheapest_parameterized_paths.  But in many
cases the fewest-row-path is the same path as cheapest_total_path, in
which case we do not need to add it again.

And now the plan becomes:

explain (costs on)
select sum(t2.c) from t t1 join t t2 on t1.a = t2.a join t t3 on t2.b
= t3.b group by t3.a;
                                         QUERY PLAN
---------------------------------------------------------------------------------------------
 Finalize HashAggregate  (cost=1706.97..1707.07 rows=10 width=12)
   Group Key: t3.a
   ->  Hash Join  (cost=1672.22..1701.97 rows=1000 width=12)
         Hash Cond: (t3.b = t2.b)
         ->  Seq Scan on t t3  (cost=0.00..16.00 rows=1000 width=8)
         ->  Hash  (cost=1672.10..1672.10 rows=10 width=12)
               ->  Partial HashAggregate  (cost=1672.00..1672.10
rows=10 width=12)
                     Group Key: t2.b
                     ->  Hash Join  (cost=28.50..1172.00 rows=100000 width=8)
                           Hash Cond: (t1.a = t2.a)
                           ->  Seq Scan on t t1  (cost=0.00..16.00
rows=1000 width=4)
                           ->  Hash  (cost=16.00..16.00 rows=1000 width=12)
                                 ->  Seq Scan on t t2
(cost=0.00..16.00 rows=1000 width=12)
(13 rows)

I believe this is the most optimal plan we can find for this query on
this dataset.

I also made some changes to how grouped relations are stored in this
version of the patch.

Thanks
Richard

---

From: Robert Haas <[email-masked]>
Date: Tue, 29 Oct 2024 08:59:21 -0400

> this context.  Perhaps someone more proficient in English could

It's not confusing the way you have it, but I think an English teacher
wouldn't like it, because part of the sentence is singular ("each base
rel") and the other part is plural ("grouped base relations").
Tender's proposed rewrite fixes that. Another way to fix it is to
write "Build group relations for base rels where possible".

> this context I think it can mean 'non-grouped relation'.  But maybe

We use the term "plain relation" in several different ways. In the
header comments for addFkRecurseReferenced, it means a non-partitioned
relation. In the struct comments for RangeTblEntry, it means any sort
of named thing in pg_class that you can scan, so either a partitioned
or unpartitioned table but not a join or a table function or
something. AFAICT, the most common meaning of "plain relation" is a
pg_class entry where relkind==RELKIND_RELATION.

---

From: Robert Haas <[email-masked]>
Date: Tue, 29 Oct 2024 16:05:50 -0400

> grouped join relation for t1/t2 join.  There might be two paths for

What exactly do you mean by "well, in theory" here? My understanding
of how things work today is that every relation is supposed to produce
a specific set of rows and every unparameterized path must produce
that set of rows. The order of the rows may vary but the set of rows
may not. With your proposed design here, that's no longer true.
Instead, what's promised is that the row sets will become equivalent
after a later FinalizeAggregate step. In a sense, this is like
parameterization or partial paths. Suppose I have:

SELECT * FROM foo, bar WHERE foo.x = bar.x;

While every unparameterized path for bar has the same row count,
there's also the possibility of performing an index scan on bar.x
parameterized by foo.x, and that path will have a far lower row count
than the unparameterized paths. Instead of producing all the same rows
as every other path, the parameterized path promises only that if run
repeatedly, with all relevant values of foo.x, you'll eventually get
all the same rows you would have gotten from the unparameterized path.
Because of this difference, parameterized paths need special handling
in many different parts of the code.

And the same thing is true of partial paths. They also do not promise
to generate all the same rows -- instead, they promise that when run
simultaneously across multiple workers, the total set of rows returned
across all invocations will be equal to what a normal path would have
produced. Here again, there's a need for special handling because
these paths behave differently than standard paths.

I think what you're doing here is roughly equivalent to either of
these two cases. It's more like the parameterized path case. Instead
of having a path for a relation which is parameterized by some input
parameter, you have a path for a relation, say bar, which is partially
aggregated by some grouping column. But there's no guarantee of how
much partial aggregation has been done. In your example, PartialAgg(t1
JOIN t2) is "more aggregated" than t1 JOIN PartialAgg(t2), so the row
counts are different. This makes me quite nervous. You can't compare a
parameterized path to an unparameterized path, but you can compare it
to another parameterized path if the parameterizations are the same.
You can't compare a partial path to a non-partial path, but you can
compare partial paths to each other. But with this work,
unparameterized, non-partial paths in the same RelOptInfo don't seem
like they are truly comparable. Maybe that's OK, but I'm not sure that
it isn't going to break other things.

You might for example imagine a design where PartialAgg(t1 JOIN t2)
and t1 JOIN PartialAgg(t2) get separate RelOptInfos. After all, there
are probably multiple ways to generate paths for each of those things,
and paths in each category can be compared to each other apples to
apples. What's less clear is whether it's fair to compare across the
two categories, and how many assumptions will be broken by doing so.
I'm not sure that it's right to have separate RelOptInfos; we
definitely don't want to create more RelOptInfos than necessary. At
the same time, if we mix together all of those paths into a single
RelOptInfo, we need to be confident that we're neither going to break
anything nor introduce too many special cases into hot code paths. For
instance, set_joinpath_size() represents an unwelcome complexity
increase that could impact performance generally, even apart from the
cases this patch intends to handle.

It's tempting to wonder if there's some way that we can avoid
generating paths for both PartialAgg(t1 JOIN t2) and t1 JOIN
PartialAgg(t2). Either the former has lower cardinality, or the latter
does. It seems likely that the lower-cardinality set is the winning
strategy. Even if the path has higher cost to generate, we save work
at every subsequent join level and at the final aggregation step. Are
there counterexamples where it's better to  use a path from the
higher-cardinality set?

By the way, the work of figuring out what target list should be
produced by partial grouping is done by init_grouping_targets(), but
the comments seem to take it for granted that I know what result we're
trying to produce, and I don't. I think some more high-level
explanation of the goals of this code would be useful. It seems to me
that if I'm looking at a path for an ungrouped relation and it
produces a certain target list, then every column of that target list
is needed somewhere. If those columns are group keys, cool: we pass
those through. If they're inputs to the aggregates, cool: we feed them
to the aggregates. But if they are neither, then what? In the patch,
you either group on those columns or add them to the
possibly_dependent list depending on the result of
is_var_needed_by_join(). I can believe that there are some cases where
we can group on such columns and others where we can't, but find it
difficult to believe that this test reliably distinguishes between
those two cases. If it does, I don't understand why it does. Don't I
need to know something about how those columns are used in the upper
joins? Like, if those columns are connected by a chain of
binary-equality operators back to the user's choice of grouping
columns, that sounds good, but this test doesn't distinguish between
that case and an upper join on the < operator.
create_grouping_expr_infos() does reason based on whether there's an
equal-image operator available, but AIUI that's only reasoning about
the group columns the user mentioned, not the sort of implicit
grouping columns that init_grouping_targets() is creating.

I spent a lot of time thinking today about what makes it safe to push
down grouping or not. I'm not sure that I have a solid answer to that
question even yet. But it seems to me that there are at least two
cases that clearly won't fly. One is the case where the partial
aggregation would merge rows that need to be included in the final
aggregation with rows that should be filtered out. If the
partially-grouped relation simply has a filter qual, that's fine,
because it will be evaluated before the aggregation. But there might
be a qual that has to be evaluated later, either because (a) it
involves another rel, like this_rel.x + that_rel.y > 10 or (b) it
appears in the ON clause of an outer join and thus needs to be
deferred to the level of the OJ, e.g. A LEFT JOIN B ON a.x = b.x AND
b.y = 42. I wonder if you can comment on how these cases are handled.
Perhaps this coding around functional dependencies has something to do
with it, but it isn't clear to me.

Thanks,

---

From: Richard Guo <[email-masked]>
Date: Fri, 1 Nov 2024 10:50:24 +0900

> write "Build group relations for base rels where possible".

Thank you for the suggestion.  The new wording looks much better
grammatically.  It seems to me that we should address the nearby
comment too, which goes like "consider_parallel flags for each base
rel", as each rel has only one consider_parallel flag.

> pg_class entry where relkind==RELKIND_RELATION.

Agreed.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Fri, 1 Nov 2024 14:54:28 +0900

On Wed, Oct 30, 2024 at 5:06 AM Robert Haas <[email-masked]> wrote:
> parameterization or partial paths.

Yeah, you're correct that currently each relation is expected to
produce the same specific set of rows.  When I say "well, in theory" I
mean that for a join relation, all its unparameterized paths should
theoretically have the same row count estimate.  However, in practice,
because there are more than one way to make a joinrel for more than
two base relations, and the selectivity estimation routines don’t
handle all cases equally well, we might get different row count
estimates depending on the pair provided.

And yes, with the grouped relations proposed in this patch, the
situation changes.  For a grouped join relation, different paths can
produce very different row sets, depending on where the partial
aggregation is placed in the path tree.  This is also why we need to
recalculate the row count estimate for a grouped join path using its
outer and inner paths provided, rather than using path->parent->rows
directly.  This is very like the parameterized path case.

> it isn't going to break other things.

Perhaps we could introduce a GroupPathInfo into the Path structure to
store common information for a grouped path, such as the location of
the partial aggregation (which could be the relids of the relation on
top of which we place the partial aggregation) and the estimated
rowcount for this grouped path, similar to how ParamPathInfo functions
for parameterized paths.  Then we should be able to compare the
grouped paths of the same location apples to apples.  I haven’t
thought this through in detail yet, though.

> there counterexamples where it's better to  use a path from the

This is very appealing if we can retain only the lower-cardinality
path, as it would greatly simplify the overall design.  I haven't
looked for counterexamples yet, but I plan to do so later.

> grouping columns that init_grouping_targets() is creating.

Yeah, this patch does not get it correct here.  Basically the logic is
that for the partial aggregation pushed down to a non-aggregated
relation, we need to consider all columns of that relation involved in
upper join clauses and include them in the grouping keys.  Currently,
the patch only checks whether a column is involved in upper join
clauses but does not verify how the column is used.  We need to ensure
that the operator used in the join clause is at least compatible with
the grouping operator; otherwise, the grouping operator might
interpret the values as the same while the join operator sees them as
different.

Thanks
Richard

---

From: jian he <[email-masked]>
Date: Wed, 6 Nov 2024 13:04:38 +0800

> effort.  I'll work on that next and see what happens.

in v13, latest version. we can

    /* ... and initialize these targets */
    if (!init_grouping_targets(root, rel, target, agg_input,
                               &group_clauses, &group_exprs))
        return NULL;
    if (rel->reloptkind == RELOPT_BASEREL && group_exprs != NIL)
    {
        foreach_node(Var, var, group_exprs)
        {
            if(var->varno == rel->relid &&
                has_unique_index(rel, var->varattno))
                return NULL;
        }
    }

since in init_grouping_targets we already Asserted that group_exprs is
a list of Var.

--------------------------------------------------------------------------------
also in create_rel_agg_info, estimate_num_groups

    result->group_exprs = group_exprs;
    result->grouped_rows = estimate_num_groups(root, result->group_exprs,
                                               rel->rows, NULL, NULL);
        /*
         * The grouped paths for the given relation are considered useful iff
         * the row reduction ratio is greater than EAGER_AGGREGATE_RATIO.
         */
        agg_info->agg_useful =
            (agg_info->grouped_rows <= rel->rows * (1 - EAGER_AGGREGATE_RATIO));

If the associated Var in group_exprs is too many, then result->grouped_rows
will be less accurate, therefore agg_info->agg_useful will be less accurate.
should we limit the number of Var associated with Var group_exprs.

for example:
SET enable_eager_aggregate TO on;
drop table if exists eager_agg_t1,eager_agg_t2, eager_agg_t3;
CREATE TABLE eager_agg_t1 (a int, b int, c double precision);
CREATE TABLE eager_agg_t2 (a int, b int, c double precision);
INSERT INTO eager_agg_t1 SELECT i % 100, i, i FROM generate_series(1, 5)i;
INSERT INTO eager_agg_t2 SELECT i % 10, i, i FROM generate_series(1, 5)i;
INSERT INTO eager_agg_t2 SELECT i % 10, i, i FROM generate_series(-4, -2)i;
explain(costs off, verbose, settings)
SELECT t1.a, avg(t2.c) FROM eager_agg_t1 t1 JOIN eager_agg_t2 t2 ON
abs(t1.b) = abs(t2.b % 10 + t2.a) group by 1;

explain(costs off, verbose, settings)
SELECT t1.a, avg(t2.c) FROM eager_agg_t1 t1 JOIN eager_agg_t2 t2 ON
abs(t1.b) = abs(t2.b % 10 + t2.a) group by 1;
                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Finalize HashAggregate
   Output: t1.a, avg(t2.c)
   Group Key: t1.a
   ->  Merge Join
         Output: t1.a, (PARTIAL avg(t2.c))
         Merge Cond: ((abs(((t2.b % 10) + t2.a))) = (abs(t1.b)))
         ->  Sort
               Output: t2.b, t2.a, (PARTIAL avg(t2.c)), (abs(((t2.b %
10) + t2.a)))
               Sort Key: (abs(((t2.b % 10) + t2.a)))
               ->  Partial HashAggregate
                     Output: t2.b, t2.a, PARTIAL avg(t2.c), abs(((t2.b
% 10) + t2.a))
                     Group Key: t2.b, t2.a
                     ->  Seq Scan on public.eager_agg_t2 t2
                           Output: t2.a, t2.b, t2.c
         ->  Sort
               Output: t1.a, t1.b, (abs(t1.b))
               Sort Key: (abs(t1.b))
               ->  Seq Scan on public.eager_agg_t1 t1
                     Output: t1.a, t1.b, abs(t1.b)
 Settings: enable_eager_aggregate = 'on'
 Query Identifier: -734044107933323262