Обсуждение: 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

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

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
workand 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
nearlyidentical if you restore the LEFT JOIN to a JOIN). I admittedly may be missing a subtlety, but does this mean
thatthere 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

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

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

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

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

On Wed, Aug 28, 2024 at 9:01 PM Robert Haas <robertmhaas@gmail.com> wrote:
> On Tue, Aug 27, 2024 at 11:57 PM Tender Wang <tndrwang@gmail.com> wrote:
> > 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.

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

On Wed, Aug 28, 2024 at 10:26 PM Richard Guo <guofenglinux@gmail.com> wrote:
> 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.

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

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

On Wed, Aug 28, 2024 at 11:38 PM Tender Wang <tndrwang@gmail.com> wrote:
> 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.

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.

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