Re: Eager aggregation, take 3

On Fri, Sep 5, 2025 at 10:10 PM Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> 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.

Thanks for pointing this out. I should have clarified that the proof
is intended for the inner join case. My plan was to first establish
the correctness for inner joins, and then extend the proof to cover
outer joins, but I failed to make that clear.

In the case where there are any outer joins, the situation becomes
more complex due to join order constraints and the semantics of
null-extension in outer joins. If the relations that contain at least
one aggregation column cannot be treated as a single relation because
of the join order constraints, partial aggregation paths will not be
generated, and thus the transformation is not applicable.

Otherwise, to preserve correctness, we need to add an additional
condition: R1 must not be on the nullable side of any outer join.
This ensures that partial aggregation over R1 does not suppress any
null-extended rows that would be introduced by outer joins.

I'll update the proof in README to cover the outer join case.

> > 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.

Thanks for liking this idea. Another way this heuristic makes life
easier is that it ensures all grouped paths for the same grouped
relation produce the same set of rows. This means we don't need all
the hacks for comparing costs between grouped paths, nor do we have to
resolve disputes about how many RelOptInfos to create for a single
grouped relation. I'd prefer to keep this property for now and
explore more complex heuristics in the future.

- Richard