Re: Eager aggregation, take 3

Sorry for the slow response.

On Fri, Jun 13, 2025 at 3:42 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> The transformation of eager aggregation is:
>
> GROUP BY G, AGG(A) on (R1 JOIN R2 ON J)
> =
> GROUP BY G, AGG(agg_A) on ((GROUP BY G1, AGG(A) AS agg_A on R1)
> JOIN R2 ON J)
>
> This equivalence holds under the following conditions:
>
> 1) AGG is decomposable, meaning that it can be computed in two stages:
> a partial aggregation followed by a final aggregation;
> 2) The set G1 used in the pre-aggregation of R1 includes:
> * all columns from R1 that are part of the grouping keys G, and
> * all columns from R1 that appear in the join condition J.
> 3) The grouping operator for any column in G1 must be compatible with
> the operator used for that column in the join condition J.

This proof seems to ignore join-order constraints. I'm not sure to
what degree that influences the ultimate outcome here, but given A
LEFT JOIN (B INNER JOIN C), we cannot simply decide that A and C
comprise R1 and B comprises R2, because it is not actually possible to
do the A-C join first and treat the result as a relation to be joined
to B. That said, I do very much like the explicit enumeration of
criteria that must be met for the optimization to be valid. That makes
it a lot easier to evaluate whether the theory of the patch is
correct.

> To address these concerns, I'm thinking that maybe we can adopt a
> strategy where partial aggregation is only pushed to the lowest
> possible level in the join tree that is deemed useful. In other
> words, if we can build a grouped path like "AGG(B) JOIN A" -- and
> AGG(B) yields a significant reduction in row count -- we skip
> exploring alternatives like "AGG(A JOIN B)".

I really like this idea. I believe we need some heuristic here and
this seems like a reasonable one. I think there could be a better one,
potentially. For instance, it would be reasonable (in my opinion) to
do some kind of evaluation of AGG(A JOIN B) vs. AGG(B) JOIN A that
does not involve performing full path generation for both cases; e.g.
one could try to decide considering only row counts, for instance.
However, I'm not saying that would work better than your proposal
here, or that it should be a requirement for this to be committed;
it's just an idea. IMHO, the requirement to have something committable
is that there is SOME heuristic limiting the search space and at the
same time the patch can still be demonstrated to give SOME benefit. I
think what you propose here meets those criteria. I also like the fact
that it's simple and easy to understand. If it does go wrong, it will
not be too difficult for someone to understand why it has gone wrong,
which is very desirable.

> I think this heuristic serves as a good starting point, and we can
> look into extending it with more advanced strategies as the feature
> evolves.

So IOW, +1 to what you say here.

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