Thread: Push down Aggregates below joins

Push down Aggregates below joins

From
Heikki Linnakangas
Date:
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.

For example:

create temp table a (id int4 primary key);
create temp table b (id int4);

insert into a select g from generate_series(1, 1000) g;
insert into b select g/10 from generate_series(1, 10000) g;
analyze a,b;

explain select b.id from a, b where a.id = b.id group by b.id;

Currently, you get a plan like this:

                               QUERY PLAN
-----------------------------------------------------------------------
  HashAggregate  (cost=323.64..333.65 rows=1001 width=4)
    Group Key: b.id
    ->  Hash Join  (cost=27.50..298.66 rows=9990 width=4)
          Hash Cond: (b.id = a.id)
          ->  Seq Scan on b  (cost=0.00..145.00 rows=10000 width=4)
          ->  Hash  (cost=15.00..15.00 rows=1000 width=4)
                ->  Seq Scan on a  (cost=0.00..15.00 rows=1000 width=4)
(7 rows)

With the patch, you get a plan like this:

                                QUERY PLAN
-------------------------------------------------------------------------
  Hash Join  (cost=192.52..221.27 rows=9990 width=4)
    Hash Cond: (a.id = b.id)
    ->  Seq Scan on a  (cost=0.00..15.00 rows=1000 width=4)
    ->  Hash  (cost=180.01..180.01 rows=1001 width=4)
          ->  HashAggregate  (cost=170.00..180.01 rows=1001 width=4)
                Group Key: b.id
                ->  Seq Scan on b  (cost=0.00..145.00 rows=10000 width=4)
(7 rows)


This is faster, because you need to join fewer rows. (That's not 
reflected in the cost estimates above; cost estimation is not done 
properly in this prototype yet.)

Implementation
--------------

Move the responsibility of planning aggregates from the "upper stages", 
in grouping_planner(), into scan/join planning, in query_planner().

In query_planner(), after building the RelOptInfo for a scan or join 
rel, also build a grouped RelOptInfo to shadow each RelOptInfo (if 
aggregation can be done at that rel). The grouped RelOptInfo is stored 
in a new 'grouped_rel' field in the parent RelOptInfo.

A grouped rel holds Paths where the grouping/aggregation is already
performed at that node, or below it. For a base rel, it represents 
performing the aggregation on top of the scan, i.e. the Paths are like 
Agg(Scan). For a grouped join rel, the paths look like an Agg(Join(A, 
B)), or Join(Agg(A), B).

The first three of the attached patches just move existing code around. 
The fourth patch contains the actual feature.

This is still a rough prototype, but any thoughts on the general approach?

- Heikki

Attachment

Re: Push down Aggregates below joins

From
Tomas Vondra
Date:
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


Re: Push down Aggregates below joins

From
Tomas Vondra
Date:
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

From
Antonin Houska
Date:
Tomas Vondra <tomas.vondra@2ndquadrant.com> 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

From
Heikki Linnakangas
Date:
On 21/06/18 09:11, Antonin Houska wrote:
> Tomas Vondra <tomas.vondra@2ndquadrant.com> 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

From
Antonin Houska
Date:
Heikki Linnakangas <hlinnaka@iki.fi> 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 the substitution for simple Vars of the same datatype. That seems safe
> to me.

Yes, I reached the same conclusion. I'll add this restriction to the next
version of the patch.

> Overall, your patch is in a more polished state than my prototype.

Probably I spent much more time on it.

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

As mentioned above, I think we can only live without the Var substitution (in
other words without 2-stage aggregation) if we can check the uniqueness of
grouping keys of any path. So the question is how much effort this check
requires.

> And I'd suggest adopting my approach of attaching the grouped RelOptInfos to
> the parent RelOptInfo, that seems simpler.

o.k., I'll try this in the next version.

> And if we punt on the partial aggregation, and only allow pushing down the
> whole Aggregate, how much smaller would your patch get?

I can't tell now, need to spend some time looking at the code.

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

Likewise, I'll be off from July 5th to 22nd. I'll post what I have before I
leave and will see what you could make out of it :-)

It's cool that you intend to work on this feature too!

[1] https://www.postgresql.org/message-id/18007.1513957437%40localhost

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

From
Peter Eisentraut
Date:
On 20.06.18 22:12, 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.

Because this patch moves a lot of code around, there are nontrivial
conflicts now.  I was able to apply it on top of
fb6accd27b99f5f91a7e9e5bd32b98a53fc6d6b8 based on the date.

With that, I'm getting test failures in partition_aggregate, like this

  Sort
    Sort Key: t2.y, (sum(t1.y)), (count(*))
-   ->  Append
-         ->  HashAggregate
-               Group Key: t2.y
...
+   ->  Result
+         ->  Append
+               ->  HashAggregate
+                     Group Key: t1.x
...

And there is apparently no expected/aggregate_pushdown.out file in the
patch set.

-- 
Peter Eisentraut              http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


Re: Push down Aggregates below joins

From
Antonin Houska
Date:
This is what I managed to hack so far. Now the patch can also handle the
AGGSPLIT_SIMPLE aggregates.

Antonin Houska <ah@cybertec.at> wrote:

> Heikki Linnakangas <hlinnaka@iki.fi> 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.

The current patch version does not check the uniqueness of grouping keys, so
it actually doe not produce the plans you wanted to see. For expeimental
purposes, you can comment out the (agg_kind == REL_AGG_KIND_SIMPLE) branch
near the bottom of make_join_rel_common_grouped() and see that the
agg_pushdown regression test will generate plans with AGGSPLIT_SIMPLE pushed
down. For example

 Finalize HashAggregate
   Group Key: p.i
   ->  Hash Join
         Hash Cond: (p.i = c1.parent)
         ->  Seq Scan on agg_pushdown_parent p
         ->  Hash
               ->  Partial HashAggregate
                     Group Key: c1.parent
                     ->  Seq Scan on agg_pushdown_child1 c1

will become

 Hash Join
   Hash Cond: (p.i = c1.parent)
   ->  Seq Scan on agg_pushdown_parent p
   ->  Hash
         ->  HashAggregate
               Group Key: c1.parent
               ->  Seq Scan on agg_pushdown_child1 c1

The plan will look correct but it can generate duplicate grouping keys.

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

Done. I think this concept might eventually lead to simplification of
create_grouping_paths(), especially the in the special cases related to
partitioning. I just think so because it's more generic, but haven't tried
yet.

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

I'm still not convinced that GroupedVar should be removed. First, RelOptInfo
can currently have either Var or PlaceHolderVar in its reltarget, so I prefer
to add no more than one kind of expression (GroupedVar can represent either
Aggref or a generic (non-Var) grouping expression). Second, GroupedVar
indicates during cost estimation that the value has been evaluated at lower
node of the join tree and thus the higher nodes should not account for the
evaluation again, see set_pathtarget_cost_width().

> > 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.
>
> Yes, I reached the same conclusion. I'll add this restriction to the next
> version of the patch.

Done.

Rleated problem is "binary equality" of grouping keys. We need to avoid
aggregation push-down if it can discard information that JOIN/ON or WHERE
clause needs. The patch does not solve the problem yet. This is where the
discussion ended up: [1]

> > Overall, your patch is in a more polished state than my prototype.
>
> Probably I spent much more time on it.
>
> > 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 if we punt on the partial aggregation, and only allow pushing down the
> > whole Aggregate, how much smaller would your patch get?
>
> I can't tell now, need to spend some time looking at the code.

I didn't have enough time to separate "your functionality" and can do it when
I'm back from vacation. If you're courious and want to try yourself, this is
what you need to do to eliminate "my functionality":

* Remove the REL_AGG_KIND_PARTIAL constant (or the whole RelAggKind
  enumeration)

* Remove the needs_final_agg field of the RelOptGrouped structure (or the
  whole structure and make RelOptInfo grouped point directly to the RelOptInfo
  that no_final_agg currently points to).

* Remove code paths "if (GroupedVar.agg_partial != NULL) ..."

* Revert my changes of create_ordinary_grouping_paths()

* Revert the related part of my changes of set_upper_references() (see
  comments)

And then try to adjust the code so it can compile.

Of course the patch needs quite some polishing, but first we need to
achieve consensus on the concepts.

>
> > (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.)
>
> Likewise, I'll be off from July 5th to 22nd. I'll post what I have before I
> leave and will see what you could make out of it :-)
>
> It's cool that you intend to work on this feature too!
>
> [1] https://www.postgresql.org/message-id/18007.1513957437%40localhost

A few more notes:

* I didn't have time to check if all the regression tests succeed. Besides the
tests that the patch adds I only ran the partition_join test with
enable_agg_pushdown enabled, to see that the patch does push aggregation down
to partitions.

* Older version of my patch contains the postgres_fdw part. I can adjust it
when I'm back.

[1] https://www.postgresql.org/message-id/11966.1530875502%40localhost

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26, A-2700 Wiener Neustadt
Web: https://www.cybertec-postgresql.com


Attachment

Re: Push down Aggregates below joins

From
Antonin Houska
Date:
Antonin Houska <ah@cybertec.at> 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).

Note on coding: so far most of the functions to which I added the "grouped"
argument can get the same information from rel->agg_info (it's set iff the
relation is grouped). So we can remove it for this "simple aggregation", but
the next (more generic) part of the patch will have to add some argument
anyway, to indicate whether AGGSPLIT_SIMPLE, AGGSPLIT_INITIAL_SERIAL (or no
aggregation) should be performed.

Besides splitting the code I worked on the determination whether join
duplicates grouping keys or not. Currently it still fails to combine
"uniquekeys" of joined relation in some (important) cases when the information
needed is actually available. I think ECs should be used here, like it is for
pathkeys.

So currently you should comment out this code

    if (!match_uniquekeys_to_group_pathkeys(root, result, target))
        *keys_ok = false;

in pathnode.c:make_uniquekeys_for_join() if you want the patch to at leat
produce interesting EXPLAIN output.

One example:

CREATE TABLE a(i int primary key);
CREATE TABLE b(j int primary key, k int);

SET enable_agg_pushdown TO true;

EXPLAIN
SELECT          j, sum(k)
FROM            a, b
WHERE           i = j
GROUP BY        j

                              QUERY PLAN
-----------------------------------------------------------------------
 Hash Join  (cost=94.75..162.43 rows=2260 width=12)
   Hash Cond: (a.i = b.j)
   ->  Seq Scan on a  (cost=0.00..35.50 rows=2550 width=4)
   ->  Hash  (cost=66.50..66.50 rows=2260 width=12)
         ->  HashAggregate  (cost=43.90..66.50 rows=2260 width=12)
               Group Key: b.j
               ->  Seq Scan on b  (cost=0.00..32.60 rows=2260 width=8)

However there are cases like this

EXPLAIN
SELECT          i, sum(k)
FROM            a, b
WHERE           i = j
GROUP BY        i

which currently does not work. The reason is that the column b.j which is not
in the GROUP BY clause needs to be in the grouped output of the "b" (grouped)
table output, otherwise the join condition cannot be evaluated.

While separating the code that only uses 1-stage aggregation I removed the
code that adds such extra grouping keys to per-relation AggPath because in
general this is only safe if the final aggregation is performed, and the final
aggregation uses no added columns. However I forgot that grouping keys can be
added in cases like shown above, i.e. the grouping expression b.j is derived
from GROUP BY using equivalence class.

I'll fix this (and various other problems) asap. I believe it's worth to at
least show the current code. I'm curious if it's something we can build on or
if another rework will be needed.

(I'll be off next week.)

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26, A-2700 Wiener Neustadt
Web: https://www.cybertec-postgresql.com


Attachment

Re: Push down Aggregates below joins

From
Michael Paquier
Date:
On Fri, Aug 03, 2018 at 04:50:11PM +0200, Antonin Houska wrote:
> Antonin Houska <ah@cybertec.at> 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

Attachment