Eager aggregation, take 3

Started by Richard Guoabout 2 years ago126 messages
Jump to latest
#1Richard Guo
guofenglinux@gmail.com

Hi All,

Eager aggregation is a query optimization technique that partially
pushes a group-by past a join, and finalizes it once all the relations
are joined. Eager aggregation reduces the number of input rows to the
join and thus may result in a better overall plan. This technique is
thoroughly described in the 'Eager Aggregation and Lazy Aggregation'
paper [1]https://www.vldb.org/conf/1995/P345.PDF.

Back in 2017, a patch set has been proposed by Antonin Houska to
implement eager aggregation in thread [2]/messages/by-id/9666.1491295317@localhost. However, it was at last
withdrawn after entering the pattern of "please rebase thx" followed by
rebasing and getting no feedback until "please rebase again thx". A
second attempt in 2022 unfortunately fell into the same pattern about
one year ago and was eventually closed again [3]/messages/by-id/OS3PR01MB66609589B896FBDE190209F495EE9@OS3PR01MB6660.jpnprd01.prod.outlook.com.

That patch set has included most of the necessary concepts to implement
eager aggregation. However, as far as I can see, it has several weak
points that we need to address. It introduces invasive changes to some
core planner functions, such as make_join_rel(). And with such changes
join_is_legal() would be performed three times for the same proposed
join, which is not great. Another weak point is that the complexity of
join searching dramatically increases with the growing number of
relations to be joined. This occurs because when we generate partially
aggregated paths, each path of the input relation is considered as an
input path for the grouped paths. As a result, the number of grouped
paths we generate increases exponentially, leading to a significant
explosion in computational complexity. Other weak points include the
lack of support for outer joins and partitionwise joins. And during my
review of the code, I came across several bugs (planning error or crash)
that need to be addressed.

I'd like to give it another take to implement eager aggregation, while
borrowing lots of concepts and many chunks of codes from the previous
patch set. Please see attached. I have chosen to use the term 'Eager
Aggregation' from the paper [1]https://www.vldb.org/conf/1995/P345.PDF instead of 'Aggregation push-down', to
differentiate the aggregation push-down technique in FDW.

The patch has been split into small pieces to make the review easier.

0001 introduces the RelInfoList structure, which encapsulates both a
list and a hash table, so that we can leverage the hash table for faster
lookups not only for join relations but also for upper relations. With
eager aggregation, it is possible that we generate so many upper rels of
type UPPERREL_PARTIAL_GROUP_AGG that a hash table can help a lot with
lookups.

0002 introduces the RelAggInfo structure to store information needed to
create grouped paths for base and join rels. It also revises the
RelInfoList related structures and functions so that they can be used
with RelAggInfos.

0003 checks if eager aggregation is applicable, and if so, collects
suitable aggregate expressions and grouping expressions in the query,
and records them in root->agg_clause_list and root->group_expr_list
respectively.

0004 implements the functions that check if eager aggregation is
applicable for a given relation, and if so, create RelAggInfo structure
for the relation, using the infos about aggregate expressions and
grouping expressions we collected earlier. In this patch, when we check
if a target expression can act as grouping expression, we need to check
if this expression can be known equal to other expressions due to ECs
that can act as grouping expressions. This patch leverages function
exprs_known_equal() to achieve that, after enhancing this function to
consider opfamily if provided.

0005 implements the functions that generate paths for grouped relations
by adding sorted and hashed partial aggregation paths on top of paths of
the plain base or join relations. For sorted partial aggregation paths,
we only consider any suitably-sorted input paths as well as sorting the
cheapest-total path. For hashed partial aggregation paths, we only
consider the cheapest-total path as input. By not considering other
paths we can reduce the number of grouping paths as much as possible
while still achieving reasonable results.

0006 builds grouped relations for each base relation if possible, and
generates aggregation paths for the grouped base relations.

0007 builds grouped relations for each just-processed join relation if
possible, and generates aggregation paths for the grouped join
relations. The changes made to make_join_rel() are relatively minor,
with the addition of a new function make_grouped_join_rel(), which finds
or creates a grouped relation for the just-processed joinrel, and
generates grouped paths by joining a grouped input relation with a
non-grouped input relation.

The other way to generate grouped paths is by adding sorted and hashed
partial aggregation paths on top of paths of the joinrel. This occurs
in standard_join_search(), after we've run set_cheapest() for the
joinrel. The reason for performing this step after set_cheapest() is
that we need to know the joinrel's cheapest paths (see 0005).

This patch also makes the grouped relation for the topmost join rel act
as the upper rel representing the result of partial aggregation, so that
we can add the final aggregation on top of that. Additionally, this
patch extends the functionality of eager aggregation to work with
partitionwise join and geqo.

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.

Starting from this patch, you should be able to see plans with eager
aggregation.

0008 adds test cases for eager aggregation.

0009 adds a section in README that describes this feature (copied from
previous patch set, with minor tweaks).

Thoughts and comments are welcome.

[1]: https://www.vldb.org/conf/1995/P345.PDF
[2]: /messages/by-id/9666.1491295317@localhost
[3]: /messages/by-id/OS3PR01MB66609589B896FBDE190209F495EE9@OS3PR01MB6660.jpnprd01.prod.outlook.com
/messages/by-id/OS3PR01MB66609589B896FBDE190209F495EE9@OS3PR01MB6660.jpnprd01.prod.outlook.com

Thanks
Richard

Attachments:

v1-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v1-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v1-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v1-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v1-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v1-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+662-11
v1-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v1-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v1-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v1-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v1-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v1-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v1-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v1-0007-Build-grouped-relations-out-of-join-relations.patchDownload+320-27
v1-0009-Add-README.patchapplication/octet-stream; name=v1-0009-Add-README.patchDownload+88-1
v1-0008-Add-test-cases.patchapplication/octet-stream; name=v1-0008-Add-test-cases.patchDownload+1476-2
#2Andy Fan
zhihui.fan1213@gmail.com
In reply to: Richard Guo (#1)
Re: Eager aggregation, take 3

Richard Guo <guofenglinux@gmail.com> writes:

Hi All,

Eager aggregation is a query optimization technique that partially
pushes a group-by past a join, and finalizes it once all the relations
are joined. Eager aggregation reduces the number of input rows to the
join and thus may result in a better overall plan. This technique is
thoroughly described in the 'Eager Aggregation and Lazy Aggregation'
paper [1].

This is a really helpful and not easy task, even I am not sure when I
can spend time to study this, I want to say "Thanks for working on
this!" first and hope we can really progress on this topic. Good luck!

--
Best Regards
Andy Fan

#3Richard Guo
guofenglinux@gmail.com
In reply to: Andy Fan (#2)
Re: Eager aggregation, take 3

On Mon, Mar 4, 2024 at 7:49 PM Andy Fan <zhihuifan1213@163.com> wrote:

This is a really helpful and not easy task, even I am not sure when I
can spend time to study this, I want to say "Thanks for working on
this!" first and hope we can really progress on this topic. Good luck!

Thanks. I hope this take can go even further and ultimately find its
way to be committed.

This needs a rebase after dbbca2cf29. I also revised the commit message
for 0007 and fixed a typo in 0009.

Thanks
Richard

Attachments:

v2-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v2-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v2-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v2-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+662-11
v2-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v2-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v2-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v2-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v2-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v2-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v2-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v2-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v2-0009-Add-README.patchapplication/octet-stream; name=v2-0009-Add-README.patchDownload+88-1
v2-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v2-0007-Build-grouped-relations-out-of-join-relations.patchDownload+320-27
v2-0008-Add-test-cases.patchapplication/octet-stream; name=v2-0008-Add-test-cases.patchDownload+1476-2
#4Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#3)
Re: Eager aggregation, take 3

On Tue, Mar 5, 2024 at 2:47 PM Richard Guo <guofenglinux@gmail.com> wrote:

This needs a rebase after dbbca2cf29. I also revised the commit message
for 0007 and fixed a typo in 0009.

Here is another rebase, mainly to make the test cases more stable by
adding ORDER BY clauses to the test queries. Also fixed more typos in
passing.

Thanks
Richard

Attachments:

v3-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v3-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v3-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v3-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v3-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v3-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v3-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v3-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+662-11
v3-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v3-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v3-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v3-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v3-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v3-0007-Build-grouped-relations-out-of-join-relations.patchDownload+320-27
v3-0008-Add-test-cases.patchapplication/octet-stream; name=v3-0008-Add-test-cases.patchDownload+1486-2
v3-0009-Add-README.patchapplication/octet-stream; name=v3-0009-Add-README.patchDownload+88-1
#5Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#4)
Re: Eager aggregation, take 3

On Tue, Mar 5, 2024 at 7:19 PM Richard Guo <guofenglinux@gmail.com> wrote:

Here is another rebase, mainly to make the test cases more stable by
adding ORDER BY clauses to the test queries. Also fixed more typos in
passing.

This needs another rebase after 97d85be365. I also addressed several
issues that I identified during self-review, which include:

* In some cases GroupPathExtraData.agg_final_costs, which is the cost of
final aggregation, fails to be calculated. This can lead to bogus cost
estimation and end up with unexpected plan.

* If the cheapest partially grouped path is generated through eager
aggregation, the number of groups estimated for the final phase will be
different from the number of groups estimated for non-split aggregation.
That is to say, we should not use 'dNumGroups' for the final aggregation
in add_paths_to_grouping_rel().

* It is possible that we may generate dummy grouped join relations, and
that would trigger the Assert in make_grouped_join_rel().

* More typo fixes.

Thanks
Richard

Attachments:

v4-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v4-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v4-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v4-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v4-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v4-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v4-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v4-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+661-11
v4-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v4-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v4-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v4-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v4-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v4-0007-Build-grouped-relations-out-of-join-relations.patchDownload+360-44
v4-0008-Add-test-cases.patchapplication/octet-stream; name=v4-0008-Add-test-cases.patchDownload+1486-2
v4-0009-Add-README.patchapplication/octet-stream; name=v4-0009-Add-README.patchDownload+88-1
#6Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#5)
Re: Eager aggregation, take 3

There is a conflict in the parallel_schedule file. So here is another
rebase. Nothing else has changed.

Thanks
Richard

Attachments:

v5-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v5-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v5-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v5-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v5-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v5-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v5-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v5-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+661-11
v5-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v5-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v5-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v5-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v5-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v5-0007-Build-grouped-relations-out-of-join-relations.patchDownload+360-44
v5-0008-Add-test-cases.patchapplication/octet-stream; name=v5-0008-Add-test-cases.patchDownload+1486-2
v5-0009-Add-README.patchapplication/octet-stream; name=v5-0009-Add-README.patchDownload+88-1
#7Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#6)
Re: Eager aggregation, take 3

Here is an update of the patchset with the following changes:

* Fix a 'Aggref found where not expected' error caused by the PVC call
in is_var_in_aggref_only. This would happen if we have Aggrefs
contained in other expressions.

* Use joinrel's relids rather than the union of the relids of its outer
and inner to search for its grouped rel. This is more correct as we
need to include OJs into consideration.

* Remove RelAggInfo.agg_exprs as it is not used anymore.

Thanks
Richard

Attachments:

v6-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v6-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v6-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v6-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v6-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v6-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v6-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v6-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+674-11
v6-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v6-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v6-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v6-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v6-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v6-0007-Build-grouped-relations-out-of-join-relations.patchDownload+355-52
v6-0008-Add-test-cases.patchapplication/octet-stream; name=v6-0008-Add-test-cases.patchDownload+1486-2
v6-0009-Add-README.patchapplication/octet-stream; name=v6-0009-Add-README.patchDownload+88-1
#8Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#7)
Re: Eager aggregation, take 3

Another rebase is needed after d1d286d83c. Also I realized that the
partially_grouped_rel generated by eager aggregation might be dummy,
such as in query:

select count(t2.c) from t t1 join t t2 on t1.b = t2.b where false group by
t1.a;

If somehow we choose this dummy path with a Finalize Agg Path on top of
it as the final cheapest path (a very rare case), we would encounter the
"Aggref found in non-Agg plan node" error. The v7 patch fixes this
issue.

Thanks
Richard

Attachments:

v7-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v7-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v7-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v7-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v7-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v7-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v7-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v7-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+674-11
v7-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v7-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v7-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v7-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v7-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v7-0007-Build-grouped-relations-out-of-join-relations.patchDownload+363-52
v7-0008-Add-test-cases.patchapplication/octet-stream; name=v7-0008-Add-test-cases.patchDownload+1486-2
v7-0009-Add-README.patchapplication/octet-stream; name=v7-0009-Add-README.patchDownload+88-1
#9Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#8)
Re: Eager aggregation, take 3

On Mon, May 20, 2024 at 4:12 PM Richard Guo <guofenglinux@gmail.com> wrote:

Another rebase is needed after d1d286d83c. Also I realized that the
partially_grouped_rel generated by eager aggregation might be dummy,
such as in query:

select count(t2.c) from t t1 join t t2 on t1.b = t2.b where false group by t1.a;

If somehow we choose this dummy path with a Finalize Agg Path on top of
it as the final cheapest path (a very rare case), we would encounter the
"Aggref found in non-Agg plan node" error. The v7 patch fixes this
issue.

I spent some time testing this patchset and found a few more issues.

One issue is that partially-grouped partial paths may have already been
generated in the process of building up the grouped join relations by
eager aggregation, in which case the partially_grouped_rel would contain
valid partial paths by the time we reach create_partial_grouping_paths.
If we subsequently find that parallelism is not possible for
partially_grouped_rel, we need to drop these partial paths; otherwise we
risk encountering Assert(subpath->parallel_safe) when creating gather /
gather merge path. This issue can be reproduced with the query below on
v7 patch.

create function parallel_restricted_func(a int) returns int as
$$ begin return a; end; $$ parallel restricted language plpgsql;
create table t (a int, b int, c int) with (parallel_workers = 2);
set enable_eager_aggregate to on;

explain (costs off)
select parallel_restricted_func(1) * count(t2.c)
from t t1, t t2 where t1.b = t2.b group by t2.c;

Another issue I found is that when we check to see whether a given Var
appears only within Aggrefs, we need to account for havingQual in
addition to targetlist; otherwise there's a risk of omitting this Var
from the targetlist of the partial Agg node, leading to 'ERROR: variable
not found in subplan target list'. This error can be reproduced with
the query below on v7.

create table t (a int primary key, b int, c int);
set enable_eager_aggregate to on;

explain (costs off)
select count(*) from t t1, t t2 group by t1.a having min(t1.b) < t1.b;
ERROR: variable not found in subplan target list

A third issue I found is that with v7 we might push the Partial Agg to
the nullable side of an outer join, which is not correct. This happens
because when determining whether a Partial Agg can be pushed down to a
relation, the v7 patchset indeed checks if the aggregate expressions can
be evaluated at this relation level. However, it overlooks checking the
grouping expressions. The grouping expressions can originate from two
sources: the original GROUP BY clauses, or constructed from join
conditions. In either case, we must verify that the grouping
expressions cannot be nulled by outer joins that are above the current
relation, otherwise the Partial Agg cannot be pushed down to this rel.

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

Thanks
Richard

Attachments:

v8-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v8-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v8-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v8-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v8-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v8-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v8-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v8-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+704-22
v8-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v8-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v8-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v8-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v8-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v8-0007-Build-grouped-relations-out-of-join-relations.patchDownload+385-52
v8-0008-Add-test-cases.patchapplication/octet-stream; name=v8-0008-Add-test-cases.patchDownload+1486-2
v8-0009-Add-README.patchapplication/octet-stream; name=v8-0009-Add-README.patchDownload+88-1
#10Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#9)
Re: Eager aggregation, take 3

On Thu, Jun 13, 2024 at 4:07 PM Richard Guo <guofenglinux@gmail.com> 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

Attachments:

v9-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v9-0001-Introduce-RelInfoList-structure.patchDownload+133-98
v9-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchapplication/octet-stream; name=v9-0002-Introduce-RelAggInfo-structure-to-store-info-for-grouped-paths.patchDownload+118-22
v9-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchapplication/octet-stream; name=v9-0003-Set-up-for-eager-aggregation-by-collecting-needed-infos.patchDownload+315-2
v9-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchapplication/octet-stream; name=v9-0004-Implement-functions-that-create-RelAggInfos-if-applicable.patchDownload+704-22
v9-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchapplication/octet-stream; name=v9-0005-Implement-functions-that-generate-paths-for-grouped-relations.patchDownload+315-9
v9-0006-Build-grouped-relations-out-of-base-relations.patchapplication/octet-stream; name=v9-0006-Build-grouped-relations-out-of-base-relations.patchDownload+196-1
v9-0007-Build-grouped-relations-out-of-join-relations.patchapplication/octet-stream; name=v9-0007-Build-grouped-relations-out-of-join-relations.patchDownload+385-52
v9-0008-Add-test-cases.patchapplication/octet-stream; name=v9-0008-Add-test-cases.patchDownload+1486-2
v9-0009-Add-README.patchapplication/octet-stream; name=v9-0009-Add-README.patchDownload+88-1
v9-0010-Run-pgindent.patchapplication/octet-stream; name=v9-0010-Run-pgindent.patchDownload+119-112
#11Paul George
p.a.george19@gmail.com
In reply to: Richard Guo (#10)
Re: Eager aggregation, take 3

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-

On Sat, Jul 6, 2024 at 4:56 PM Richard Guo <guofenglinux@gmail.com> wrote:

Show quoted text

On Thu, Jun 13, 2024 at 4:07 PM Richard Guo <guofenglinux@gmail.com>
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

#12Richard Guo
guofenglinux@gmail.com
In reply to: Paul George (#11)
Re: Eager aggregation, take 3

On Sun, Jul 7, 2024 at 10:45 AM Paul George <p.a.george19@gmail.com> 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

#13Paul George
p.a.george19@gmail.com
In reply to: Richard Guo (#12)
Re: Eager aggregation, take 3

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

On Wed, Jul 10, 2024 at 1:27 AM Richard Guo <guofenglinux@gmail.com> wrote:

Show quoted text

On Sun, Jul 7, 2024 at 10:45 AM Paul George <p.a.george19@gmail.com>
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

#14Richard Guo
guofenglinux@gmail.com
In reply to: Paul George (#13)
Re: Eager aggregation, take 3

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

Attachments:

v10-0002-Implement-Eager-Aggregation.patchapplication/octet-stream; name=v10-0002-Implement-Eager-Aggregation.patchDownload+3488-98
v10-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v10-0001-Introduce-RelInfoList-structure.patchDownload+136-99
#15Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#14)
Re: Eager aggregation, take 3

On Fri, Aug 16, 2024 at 4:14 PM Richard Guo <guofenglinux@gmail.com> wrote:

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.

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

Attachments:

v11-0001-Introduce-RelInfoList-structure.patchapplication/octet-stream; name=v11-0001-Introduce-RelInfoList-structure.patchDownload+136-99
v11-0002-Implement-Eager-Aggregation.patchapplication/octet-stream; name=v11-0002-Implement-Eager-Aggregation.patchDownload+3467-100
#16Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#15)
Re: Eager aggregation, take 3

On Wed, Aug 21, 2024 at 3:11 AM Richard Guo <guofenglinux@gmail.com> wrote:

Attached is the updated version of the patchset that fixes this bug
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

#17Tender Wang
tndrwang@gmail.com
In reply to: Richard Guo (#15)
Re: Eager aggregation, take 3

Richard Guo <guofenglinux@gmail.com> 于2024年8月21日周三 15:11写道:

On Fri, Aug 16, 2024 at 4:14 PM Richard Guo <guofenglinux@gmail.com>
wrote:

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.

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.

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

#18Robert Haas
robertmhaas@gmail.com
In reply to: Tender Wang (#17)
Re: Eager aggregation, take 3

On Tue, Aug 27, 2024 at 11:57 PM Tender Wang <tndrwang@gmail.com> wrote:

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.

Interesting to know.

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

OK.

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.

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.

I will continue to do benchmark on this feature.

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

Thanks!

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

#19Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#16)
Re: Eager aggregation, take 3

On Fri, Aug 23, 2024 at 11:59 PM Robert Haas <robertmhaas@gmail.com> wrote:

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.

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.

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

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.

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.

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?

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

#20Richard Guo
guofenglinux@gmail.com
In reply to: Tender Wang (#17)
Re: Eager aggregation, take 3

On Wed, Aug 28, 2024 at 11:57 AM Tender Wang <tndrwang@gmail.com> wrote:

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.

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

Thanks
Richard

#21Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#18)
#22Tender Wang
tndrwang@gmail.com
In reply to: Richard Guo (#21)
#23Tender Wang
tndrwang@gmail.com
In reply to: Richard Guo (#21)
#24Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#19)
#25Robert Haas
robertmhaas@gmail.com
In reply to: Tender Wang (#23)
#26Tender Wang
tndrwang@gmail.com
In reply to: Richard Guo (#15)
#27Tender Wang
tndrwang@gmail.com
In reply to: Richard Guo (#15)
#28Tender Wang
tndrwang@gmail.com
In reply to: Richard Guo (#15)
#29Tender Wang
tndrwang@gmail.com
In reply to: Tender Wang (#26)
#30Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#18)
#31Richard Guo
guofenglinux@gmail.com
In reply to: Tender Wang (#27)
#32Richard Guo
guofenglinux@gmail.com
In reply to: Tender Wang (#28)
#33Richard Guo
guofenglinux@gmail.com
In reply to: Tender Wang (#29)
#34Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#30)
#35Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#34)
#36Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#35)
#37jian he
jian.universality@gmail.com
In reply to: Richard Guo (#35)
#38jian he
jian.universality@gmail.com
In reply to: jian he (#37)
#39Richard Guo
guofenglinux@gmail.com
In reply to: jian he (#37)
#40Richard Guo
guofenglinux@gmail.com
In reply to: jian he (#38)
#41Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#32)
#42Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#30)
#43Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#36)
#44Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#40)
#45Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#39)
#46jian he
jian.universality@gmail.com
In reply to: Robert Haas (#45)
#47Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#41)
#48Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#42)
#49Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#44)
#50Richard Guo
guofenglinux@gmail.com
In reply to: jian he (#46)
#51Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#49)
#52jian he
jian.universality@gmail.com
In reply to: Richard Guo (#19)
#53Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#51)
#54Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#53)
#55Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#54)
#56Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#55)
#57Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#56)
#58Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#55)
#59Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#58)
#60Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#48)
#61Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#60)
#62jian he
jian.universality@gmail.com
In reply to: Richard Guo (#61)
#63Richard Guo
guofenglinux@gmail.com
In reply to: jian he (#62)
#64Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#61)
#65Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#64)
#66Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#65)
#67Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#66)
#68Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#67)
#69Tom Lane
tgl@sss.pgh.pa.us
In reply to: Richard Guo (#68)
#70Richard Guo
guofenglinux@gmail.com
In reply to: Tom Lane (#69)
#71Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#68)
#72Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#71)
#73Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#72)
#74Tom Lane
tgl@sss.pgh.pa.us
In reply to: Robert Haas (#73)
#75Robert Haas
robertmhaas@gmail.com
In reply to: Tom Lane (#74)
#76Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#73)
#77Richard Guo
guofenglinux@gmail.com
In reply to: Tom Lane (#74)
#78Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#76)
#79Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#78)
#80Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#79)
#81Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#80)
#82Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#81)
#83Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#82)
#84Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#83)
#85Matheus Alcantara
matheusssilv97@gmail.com
In reply to: Richard Guo (#84)
#86Richard Guo
guofenglinux@gmail.com
In reply to: Matheus Alcantara (#85)
#87Matheus Alcantara
matheusssilv97@gmail.com
In reply to: Richard Guo (#86)
#88Richard Guo
guofenglinux@gmail.com
In reply to: Matheus Alcantara (#87)
#89Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#86)
#90Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#89)
#91Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#81)
#92Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#84)
#93Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#90)
#94Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#84)
#95Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#91)
#96Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#92)
#97Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#93)
#98Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#94)
#99Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#96)
#100Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#97)
#101Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#99)
#102Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#101)
#103Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#102)
#104Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#103)
#105Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#104)
#106Matheus Alcantara
matheusssilv97@gmail.com
In reply to: Richard Guo (#105)
#107Richard Guo
guofenglinux@gmail.com
In reply to: Matheus Alcantara (#106)
#108Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#107)
#109Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#108)
#110Matheus Alcantara
matheusssilv97@gmail.com
In reply to: Richard Guo (#109)
#111Richard Guo
guofenglinux@gmail.com
In reply to: Matheus Alcantara (#110)
#112Matheus Alcantara
matheusssilv97@gmail.com
In reply to: Richard Guo (#111)
#113Richard Guo
guofenglinux@gmail.com
In reply to: Matheus Alcantara (#112)
#114Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#105)
#115David Rowley
dgrowleyml@gmail.com
In reply to: Richard Guo (#114)
#116Richard Guo
guofenglinux@gmail.com
In reply to: David Rowley (#115)
#117David Rowley
dgrowleyml@gmail.com
In reply to: Richard Guo (#116)
#118Robert Haas
robertmhaas@gmail.com
In reply to: Richard Guo (#116)
#119Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#114)
#120Richard Guo
guofenglinux@gmail.com
In reply to: David Rowley (#117)
#121Richard Guo
guofenglinux@gmail.com
In reply to: Robert Haas (#118)
#122Tom Lane
tgl@sss.pgh.pa.us
In reply to: Richard Guo (#121)
#123Richard Guo
guofenglinux@gmail.com
In reply to: Tom Lane (#122)
#124Antonin Houska
ah@cybertec.at
In reply to: Richard Guo (#119)
#125Richard Guo
guofenglinux@gmail.com
In reply to: Antonin Houska (#124)
#126Richard Guo
guofenglinux@gmail.com
In reply to: Richard Guo (#120)