Re: Push down Aggregates below joins
On Fri, Aug 03, 2018 at 04:50:11PM +0200, Antonin Houska wrote: > Antonin Houska wrote: > > > I didn't have enough time to separate "your functionality" and can do it > > when > > I'm back from vacation. > > So I've separated the code that does not use the 2-stage replication (and > therefore the feature is not involved in parallel queries). This patch has been waiting for input from its author for a couple of months now, so I am switching it to "Returned with Feedback". If a new version can be provided, please feel free to send a new one. -- Michael signature.asc Description: PGP signature
Re: Push down Aggregates below joins
Heikki Linnakangas wrote: > Ah, cool! I missed that thread earlier. Yes, seems like we've been hacking on > the same feature. Let's compare! > > I've been using this paper as a guide: > > "Including Group-By in Query Optimization", by Surajit Chaudhuri and Kyuseok > Shim: > https://pdfs.semanticscholar.org/3079/5447cec18753254edbbd7839f0afa58b2a39.pdf > Using the terms from that paper, my patch does only "Invariant Grouping > transormation", while yours can do "Simple Coalescing Grouping", which is more > general. In layman terms, my patch can push the Aggregate below a join, while > your patch can also split an Aggregate so that you do a partial aggregate > below the join, and a final stage above it. Thanks for the link. I've just checked the two approaches briefly so far. > My thinking was to start with the simpler Invariant Grouping transformation > first, and do the more advanced splitting into partial aggregates later, as > a separate patch. I think for this you need to make sure that no join duplicates already processed groups. I tried to implement PoC of "unique keys" in v5 of my patch [1], see 09_avoid_agg_finalization.diff. The point is that the final aggregation can be replaced by calling pg_aggregate(aggfinalfn) function if the final join generates only unique values of the GROUP BY expression. Eventually I considered this an additional optimization of my approach and postponed work on this to later, but I think something like this would be necessary for your approach. As soon as you find out that a grouped relation is joined to another relation in a way that duplicates the grouping expression, you cannot proceed in creating grouped path. > There's some difference in the way we're dealing with the grouped > RelOptInfos. You're storing them completely separately, in PlannerInfo's new > 'simple_grouped_rel_array' array and 'join_grouped_rel_list/hash'. I'm > attaching each grouped RelOptInfo to its parent. In the first version of my patch I added several fields to RelOptInfo (reltarget for the grouped paths, separate pathlist, etc.) but some people didn't like it. In the later versions I introduced a separate RelOptInfo for grouped relations, but stored it in a separate list. Your approach might make the patch a bit less invasive, i.e. we don't have to add those RelOptInfo lists / arrays to standard_join_search() and subroutines. > I got away with much less code churn in allpaths.c, indxpath.c, > joinpath.c. You're adding new 'do_aggregate' flags to many functions. I'm not > sure if you needed that because you do partial aggregation and I don't, but it > would be nice to avoid it. IIRC, the do_aggregate argument determines how the grouped join should be created. If it's false, the planner joins a grouped relation (if it exists) to non-grouped one. If it's true, it joins two non-grouped relations and applies (partial) aggregation to the result. > You're introducing a new GroupedVar expression to represent Aggrefs between > the partial and final aggregates, while I'm just using Aggref directly, above > the aggregate node. I'm not thrilled about introducing an new Var-like > expression. We already have PlaceHolderVars, and I'm always confused on how > those work. But maybe that's necessary to supprot partial aggregation? The similarity of GroupedVar and PlaceHolderVar is that they are evaluated at some place in the join tree and the result is only passed to the joins above and eventually to the query target, w/o being evaluated again. In contrast, generic expressions are evaluated in the query target (only the input Vars get propagated from lower nodes), but that's not what we want for 2-stage aggregation. In my patch GroupedVar represents either the result of partial aggregation (the value of the transient state) or a grouping expression which is more complex than a plain column reference (Var expression). > In the other thread, Robert Haas wrote: > > Concretely, in your test query "SELECT p.i, avg(c1.v) FROM > > agg_pushdown_parent AS p JOIN agg_pushdown_child1 AS c1 ON c1.parent = > > p.i GROUP BY p.i" you assume that it's OK to do a Partial > > HashAggregate over c1.parent rather than p.i. This will be false if, > > say, c1.parent is of type citext and p.i is of type text; this will > > get grouped together that shouldn't. It will also be false if the > > grouping expression is something like GROUP BY length(p.i::text), > > because one value could be '0'::numeric and the other '0.00'::numeric. > > I can't think of a reason why it would be false if the grouping > > expressions are both simple Vars of the same underlying data type, but > > I'm a little nervous that I might be wrong even about that case. > > Maybe you've handled all of this somehow, but it's not obvious to me > > that it has been considered. > > Ah, I made the same mistake. I did consider the "GROUP BY length(o.i::text)", > but not the cross-datatype case. I think we should punt on that for now, and > only do
Re: Push down Aggregates below joins
On 21/06/18 09:11, Antonin Houska wrote: Tomas Vondra wrote: On 06/20/2018 10:12 PM, Heikki Linnakangas wrote: Currently, the planner always first decides the scan/join order, and adds Group/Agg nodes on top of the joins. Sometimes it would be legal, and beneficial, to perform the aggregation below a join. I've been hacking on a patch to allow that. There was a patch [1] from Antonin Houska aiming to achieve something similar. IIRC it aimed to push the aggregate down in more cases, leveraging the partial aggregation stuff. Yes, I interrupted the work when it become clear that it doesn't find its way into v11. I'm about to get back to it next week, and at least rebase it so it can be applied to the current master branch. Ah, cool! I missed that thread earlier. Yes, seems like we've been hacking on the same feature. Let's compare! I've been using this paper as a guide: "Including Group-By in Query Optimization", by Surajit Chaudhuri and Kyuseok Shim: https://pdfs.semanticscholar.org/3079/5447cec18753254edbbd7839f0afa58b2a39.pdf Using the terms from that paper, my patch does only "Invariant Grouping transormation", while yours can do "Simple Coalescing Grouping", which is more general. In layman terms, my patch can push the Aggregate below a join, while your patch can also split an Aggregate so that you do a partial aggregate below the join, and a final stage above it. My thinking was to start with the simpler Invariant Grouping transformation first, and do the more advanced splitting into partial aggregates later, as a separate patch. Doing partial aggregation actually made your patch simpler in some ways, though. I had to make some changes to grouping_planner(), because in my patch, it is no longer responsible for aggregation. In your patch, it's still responsible for doing the final aggregation. There's some difference in the way we're dealing with the grouped RelOptInfos. You're storing them completely separately, in PlannerInfo's new 'simple_grouped_rel_array' array and 'join_grouped_rel_list/hash'. I'm attaching each grouped RelOptInfo to its parent. I got away with much less code churn in allpaths.c, indxpath.c, joinpath.c. You're adding new 'do_aggregate' flags to many functions. I'm not sure if you needed that because you do partial aggregation and I don't, but it would be nice to avoid it. You're introducing a new GroupedVar expression to represent Aggrefs between the partial and final aggregates, while I'm just using Aggref directly, above the aggregate node. I'm not thrilled about introducing an new Var-like expression. We already have PlaceHolderVars, and I'm always confused on how those work. But maybe that's necessary to supprot partial aggregation? In the other thread, Robert Haas wrote: Concretely, in your test query "SELECT p.i, avg(c1.v) FROM agg_pushdown_parent AS p JOIN agg_pushdown_child1 AS c1 ON c1.parent = p.i GROUP BY p.i" you assume that it's OK to do a Partial HashAggregate over c1.parent rather than p.i. This will be false if, say, c1.parent is of type citext and p.i is of type text; this will get grouped together that shouldn't. It will also be false if the grouping expression is something like GROUP BY length(p.i::text), because one value could be '0'::numeric and the other '0.00'::numeric. I can't think of a reason why it would be false if the grouping expressions are both simple Vars of the same underlying data type, but I'm a little nervous that I might be wrong even about that case. Maybe you've handled all of this somehow, but it's not obvious to me that it has been considered. Ah, I made the same mistake. I did consider the "GROUP BY length(o.i::text)", but not the cross-datatype case. I think we should punt on that for now, and only do the substitution for simple Vars of the same datatype. That seems safe to me. Overall, your patch is in a more polished state than my prototype. For easier review, though, I think we should try to get something smaller committed first, and build on that. Let's punt on the Var substitution. And I'd suggest adopting my approach of attaching the grouped RelOptInfos to the parent RelOptInfo, that seems simpler. And if we punt on the partial aggregation, and only allow pushing down the whole Aggregate, how much smaller would your patch get? (I'll be on vacation for the next two weeks, but I'll be following this thread. After that, I plan to focus on this feature, as time from reviewing patches in the commitfest permits.) - Heikki
Re: Push down Aggregates below joins
Tomas Vondra wrote: > On 06/20/2018 10:12 PM, Heikki Linnakangas wrote: > > Currently, the planner always first decides the scan/join order, and > > adds Group/Agg nodes on top of the joins. Sometimes it would be legal, > > and beneficial, to perform the aggregation below a join. I've been > > hacking on a patch to allow that. > > > > There was a patch [1] from Antonin Houska aiming to achieve something > similar. IIRC it aimed to push the aggregate down in more cases, > leveraging the partial aggregation stuff. Yes, I interrupted the work when it become clear that it doesn't find its way into v11. I'm about to get back to it next week, and at least rebase it so it can be applied to the current master branch. -- Antonin Houska Cybertec Schönig & Schönig GmbH Gröhrmühlgasse 26, A-2700 Wiener Neustadt Web: https://www.cybertec-postgresql.com
Re: Push down Aggregates below joins
On 06/20/2018 10:12 PM, Heikki Linnakangas wrote: > Currently, the planner always first decides the scan/join order, and > adds Group/Agg nodes on top of the joins. Sometimes it would be legal, > and beneficial, to perform the aggregation below a join. I've been > hacking on a patch to allow that. > There was a patch [1] from Antonin Houska aiming to achieve something similar. IIRC it aimed to push the aggregate down in more cases, leveraging the partial aggregation stuff. I suppose your patch only aims to do the pushdown when the two-phase aggregation is not needed? [1] https://www.postgresql.org/message-id/flat/9666.1491295317@localhost regards -- Tomas Vondra http://www.2ndQuadrant.com PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Re: Push down Aggregates below joins
On 06/20/2018 10:12 PM, Heikki Linnakangas wrote: > Currently, the planner always first decides the scan/join order, and > adds Group/Agg nodes on top of the joins. Sometimes it would be legal, > and beneficial, to perform the aggregation below a join. I've been > hacking on a patch to allow that. > There was a patch [1] from Antonin Houska aiming to achieve something similar. IIRC it aimed to push the aggregate down in more cases, leveraging the partial aggregation stuff. I suppose your patch only aims to do the pushdown when the two-phase aggregation is not needed? regards -- Tomas Vondra http://www.2ndQuadrant.com PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
