Thread: The Future of Aggregation

Hi,

On 06/09/15 12:58, David Rowley wrote:
>
> These are things along the lines of:
>
> 1. Parallel Aggregation (computes each aggregate state in parallel
> worker processes and then merges these states in serial mode)
> 2. Aggregate push-down / Aggregate before join (requires passing
> partially computed aggregate states between executor nodes)
> 3. Auto-updating Materialized views (ones which contain aggregate functions)
> 4. Foreign table aggregation
> 5. Dependant Aggregates (I talked about earlier here ->
> http://www.postgresql.org/message-id/CAKJS1f8ebkc=EhEq+ArM8vwYZ5vSapJ1Seub5=FvRRuDCtFfsQ@mail.gmail.com)
>
> Items 1-4 above I believe require support of "Aggregate State
> Combine Support" -> https://commitfest.postgresql.org/5/131/ which I
> believe will need to be modified to implement complex database types
> to backup our internal aggregate state types so that these types be
> properly passed between executor nodes, between worker processes and
> perhaps foreign data wrappers (maybe just postgres_fdw I've not
> looked into this yet)

I think yet another use case that might benefit from this would be 
'memory-bounded hash aggregate'. Jeff Davis was working on a different 
approach that worked quite well for fixed-length states, but for 
handling custom states in 'internal' data type, the (de)serialization 
seems like a must for this use case.


regards

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

David Rowley <david.rowley@2ndquadrant.com> wrote:

> It appears to me that there's quite a few new features and
> optimisations on the not too distant horizon which will require
> adding yet more fields into pg_aggregate.
>
> These are things along the lines of:

> 3. Auto-updating Materialized views (ones which contain aggregate
> functions)

Yes, that's certainly on the road map.  The recent work to add
support for inverse transition functions already goes a huge way
toward allowing optimization of incremental maintenance of
aggregates in materialized views.

> Items 1-4 above I believe require support of "Aggregate State
> Combine Support" -> https://commitfest.postgresql.org/5/131/

Yeah, that seems likely to extend optimized cases even further.


> 5. Dependant Aggregates

> Item 5 makes items 1-4 a bit more complex as with this item
> there's opportunity for very good performance improvements by
> allowing aggregates like AVG(x) also perform all the required
> work to allow SUM(x) and COUNT(x) to be calculated for "free" in
> a query containing all 3 aggregates.

Not only CPU is saved, but the optimizations for materialized views
would require the aggregate function's transition state to be saved
in each row, and the duplicate state information among these
functions would be a waste of space.

> I've discussed item 5 off-list with Simon and he mentioned that
> we might invent a transition state and transition functions which
> can have parts switched on and off much like how calcSumX2
> controls if do_numeric_accum() should calculate sum(x*x) or not.
> The problem with this is that if we ever want to store aggregate
> states in an auto-updating materialized view, then this generic
> aggregate state will have to contain at least 3 fields (to store
> count(x), sum(x) and sum(x*x)), and those 3 fields would have to
> be stored even if the aggregate was just a simple count(*).

Yeah, I think we want to preserve the ability of count() to have a
simple state, and implement dependent aggregates as discussed in
the other thread -- where (as I understood it) having sum(x),
count(x), and avg(x) in a query would avoid the row-by-row work for
sum(x) and count(x), and just invoke a final function to extract
those values from the transition state of the avg(x) aggregate.  I
see incremental maintenance of materialized views taking advantage
of the same sort of behavior, only maintaining the state for avg(x)
during incremental maintenance and *at the end* pulling the values
for sum(x) and count(x) out of that.

> The idea I discussed in the link in item 5 above gets around this
> problem, but it's a perhaps more surprise filled implementation
> as it will mean "select avg(x),sum(x),count(x) from t" is
> actually faster than "select sum(x),count(x) from t" as the agg
> state for avg() will satisfy sum and count too.

I'm skeptical that it will be noticeably faster.  It's easy to see
why this optimization will make a query *with all three* faster,
but I would not expect the process of accumulating the sum and
count to be about the same speed whether performed by one
transition function or two.  Of course I could be persuaded by a
benchmark showing otherwise.

> The purpose of this email is to open the doors for discussion
> about this so that nobody goes off and develops feature X into a
> corner and disallows feature Y and so that we end up with the
> most optimal solution that does not trip us up in the future.

That laudable.  So far I don't see anything that will do anything
but make the materialized view maintenance easier, at least if
dependent aggregates are implemented as described in the other
thread.

> I'm interested to hear if Kevin or Amit have had any time to give
> this any thought before. It would be good to ensure we all have
> the same vision here.

It sounds great to me.  I had thought about the need to deal with
these issues at some point to allow optimizations to the
incremental maintenance of materialized views (there needs to be a
fall-back of recalculating from scratch where such optimizations
are not possible, but people will not be happy with the performance
of that for simple cases where it is intuitively clear that we
could do better).  You have developed the ideas farther than I
have, and (at least on a first review) I like what I'm seeing.
There may be some devils in the details down the road, but I would
say that what you're doing looks like it will dovetail nicely with
what's on my road map.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Kevin Grittner wrote:
> David Rowley <david.rowley@2ndquadrant.com> wrote:

> > 5. Dependant Aggregates
> 
> > Item 5 makes items 1-4 a bit more complex as with this item
> > there's opportunity for very good performance improvements by
> > allowing aggregates like AVG(x) also perform all the required
> > work to allow SUM(x) and COUNT(x) to be calculated for "free" in
> > a query containing all 3 aggregates.
> 
> Not only CPU is saved, but the optimizations for materialized views
> would require the aggregate function's transition state to be saved
> in each row, and the duplicate state information among these
> functions would be a waste of space.

Uh, this also requires serialization and deserialization of non-
finalized transition state, no?

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

Alvaro Herrera <alvherre@2ndquadrant.com> wrote:
> Kevin Grittner wrote:
>> David Rowley <david.rowley@2ndquadrant.com> wrote:

>>> 5. Dependant Aggregates
>>>
>>> Item 5 makes items 1-4 a bit more complex as with this item
>>> there's opportunity for very good performance improvements by
>>> allowing aggregates like AVG(x) also perform all the required
>>> work to allow SUM(x) and COUNT(x) to be calculated for "free" in
>>> a query containing all 3 aggregates.
>>
>> Not only CPU is saved, but the optimizations for materialized
>> views would require the aggregate function's transition state to
>> be saved in each row, and the duplicate state information among
>> these functions would be a waste of space.
>
> Uh, this also requires serialization and deserialization of non-
> finalized transition state, no?

For that sort of optimization to incremental maintenance of
materialized views (when we get there), yes.  That will be one of
many issues to sort out.  Any reason you're focusing on that now?
Do you think we need to settle on a format for that to proceed with
the work David is discussing?

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 06/09/15 16:10, Tomas Vondra wrote:
> Hi,
>
> On 06/09/15 12:58, David Rowley wrote:
>>
...
>> Items 1-4 above I believe require support of "Aggregate State
>> Combine Support" -> https://commitfest.postgresql.org/5/131/ which I
>> believe will need to be modified to implement complex database types
>> to backup our internal aggregate state types so that these types be
>> properly passed between executor nodes, between worker processes and
>> perhaps foreign data wrappers (maybe just postgres_fdw I've not
>> looked into this yet)
>
> I think yet another use case that might benefit from this would be
> 'memory-bounded hash aggregate'. Jeff Davis was working on a different
> approach that worked quite well for fixed-length states, but for
> handling custom states in 'internal' data type, the (de)serialization
> seems like a must for this use case.

... and yet another use case for 'aggregate state combine' that I just 
remembered about is grouping sets. What GROUPING SET (ROLLUP, ...) do 
currently is repeatedly sorting the input, once for each grouping. What 
could happen in some cases is building the most detailed aggregation 
first, then repeatedly combine these partial states.

regards

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

Kevin Grittner wrote:
> Alvaro Herrera <alvherre@2ndquadrant.com> wrote:

> > Uh, this also requires serialization and deserialization of non-
> > finalized transition state, no?
> 
> For that sort of optimization to incremental maintenance of
> materialized views (when we get there), yes.  That will be one of
> many issues to sort out.  Any reason you're focusing on that now?
> Do you think we need to settle on a format for that to proceed with
> the work David is discussing?

No, it's just that it wasn't on David's list.

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

On 2015-06-09 17:19:33 +0200, Tomas Vondra wrote:
> ... and yet another use case for 'aggregate state combine' that I just
> remembered about is grouping sets. What GROUPING SET (ROLLUP, ...) do
> currently is repeatedly sorting the input, once for each grouping.

Actually, that's not really what happens. All aggregates that share a
sort order are computed in parallel. Only when sets do not share an
order additional sorts are required.

> What
> could happen in some cases is building the most detailed aggregation first,
> then repeatedly combine these partial states.

I'm not sure that'll routinely be beneficial, because it'd require
keeping track of all the individual "most detailed" results, no?

Greetings,

Andres Freund

On 06/09/15 17:27, Andres Freund wrote:
> On 2015-06-09 17:19:33 +0200, Tomas Vondra wrote:
>> ... and yet another use case for 'aggregate state combine' that I
>> just remembered about is grouping sets. What GROUPING SET (ROLLUP,
>> ...) do currently is repeatedly sorting the input, once for each
>> grouping.
>
> Actually, that's not really what happens. All aggregates that share
> a sort order are computed in parallel. Only when sets do not share
> an order additional sorts are required.

Oh, right, that's what I meant, but failed to explain clearly.

>> What could happen in some cases is building the most detailed
>> aggregationfirst, then repeatedly combine these partial states.
>
> I'm not sure that'll routinely be beneficial, because it'd require
> keeping track of all the individual "most detailed" results, no?

Yes, it requires tracking all the "detailed" aggregate states. I'm not 
claiming this is beneficial in every case - sometimes the current sort 
approach will be better, sometimes the combine approach  will be faster. 
In a sense it's similar to GroupAggregate vs. HashAggregate.

I expect this 'combine' approach will be much faster is cases with many 
source rows, but number of groups so small the detailed states fit into 
work_mem. In that case you can do hashagg and then walk through the hash 
table to build the actual results. This entirely eliminates the 
expensive sorts, which is killing us in many DWH workloads (because 
real-world queries usually produce only few rows, even on very large 
data sets).

But ISTM this might help even in cases when the detailed states don't 
fit into memory, still assuming the number of groups is much smaller 
than the number of source rows. Just do "partial aggregation" by 
aggregating the source rows (using hashagg) until you fill work_mem. 
Then either dump all the aggregate states to disk or only some of them 
(least frequently used?) and continue. Then you can sort the states, and 
assuming it's much smaller amount of data, it'll be much faster than 
sorting all the rows. And you can do the grouping sets using multiple 
sorts, just like today.

Of course, this only works if the partial aggregation actually reduces 
the amount of data spilled to disk - if the aggregate states grow fast, 
or if you get the tuples in certain order, it may get ugly.

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

David Rowley wrote:
> On 10 June 2015 at 03:25, Alvaro Herrera <alvherre@2ndquadrant.com> wrote:
> 
> > Kevin Grittner wrote:
> > > Alvaro Herrera <alvherre@2ndquadrant.com> wrote:
> >
> > > > Uh, this also requires serialization and deserialization of non-
> > > > finalized transition state, no?
> > >
> > > For that sort of optimization to incremental maintenance of
> > > materialized views (when we get there), yes.  That will be one of
> > > many issues to sort out.  Any reason you're focusing on that now?
> > > Do you think we need to settle on a format for that to proceed with
> > > the work David is discussing?
> >
> > No, it's just that it wasn't on David's list.
> >
> That's this part, right?
> 
> I wrote:
> "which I believe will need to be modified to implement complex database
> types to backup our internal aggregate state types so that these types be
> properly passed between executor nodes, between worker processes and
> perhaps foreign data wrappers (maybe just postgres_fdw I've not looked into
> this yet)"

Hmm, sort of, I guess.  If I understand Kevin correctly, he says these
would be stored on disk alongside matview tuples.  Anyway, it's probably
not the hardest issue to solve ...

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

On 6/9/15 9:52 AM, Kevin Grittner wrote:
> Yeah, I think we want to preserve the ability of count() to have a
> simple state, and implement dependent aggregates as discussed in
> the other thread -- where (as I understood it) having sum(x),
> count(x), and avg(x) in a query would avoid the row-by-row work for
> sum(x) and count(x), and just invoke a final function to extract
> those values from the transition state of the avg(x) aggregate.  I
> see incremental maintenance of materialized views taking advantage
> of the same sort of behavior, only maintaining the state for avg(x)
> during incremental maintenance and*at the end*  pulling the values
> for sum(x) and count(x) out of that.

Last I checked, Oracle forbade things like avg() in matviews. Since it's 
trivial to calculate avg() by hand, I don't see that as a big deal. It'd 
be nice to not require that, but it'd be MUCH nicer to have any kind of 
incremental matview update.

Just trying to keep things in perspective. :)
-- 
Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX
Data in Trouble? Get it in Treble! http://BlueTreble.com

David Rowley <david.rowley@2ndquadrant.com> wrote:
> On 10 June 2015 at 02:52, Kevin Grittner <kgrittn@ymail.com> wrote:
>> David Rowley <david.rowley@2ndquadrant.com> wrote:
>>> The idea I discussed in the link in item 5 above gets around this
>>> problem, but it's a perhaps more surprise filled implementation
>>> as it will mean "select avg(x),sum(x),count(x) from t" is
>>> actually faster than "select sum(x),count(x) from t" as the agg
>>> state for avg() will satisfy sum and count too.
>>
>> I'm skeptical that it will be noticeably faster.  It's easy to see
>> why this optimization will make a query *with all three* faster,
>> but I would not expect the process of accumulating the sum and
>> count to be about the same speed whether performed by one
>> transition function or two.  Of course I could be persuaded by a
>> benchmark showing otherwise.

Of course, after reading Tom's post and digging into what
aggregates share a transition function, I was already prepared to
eat my words above.  Since the sum() aggregate is using the
xxx_avg_accum transition function, it is clearly doing the work of
accumulating the count already, so it's clear that the above can
be a win.

> Assuming that if we reuse the avg(x) state for count(x) and
> sum(x) then it will perform almost exactly like a query
> containing just avg(x), the only additional overhead is the call
> to the final functions per group, so in the following case that's
> likely immeasurable:
>
> /* setup */ create table millionrowtable as select
> generate_series(1,1000000)::numeric as x;
> /* test 1 */ SELECT sum(x) / count(x)  from millionrowtable;
> /* test 2 */ SELECT avg(x) from millionrowtable;
>
> Test 1:
> 274.979 ms
> 272.104 ms
> 269.915 ms
>
> Test 2:
> 229.619 ms
> 220.703 ms
> 234.743 ms
>

> (About 19% slower)

Of course, with Tom's approach you would see the benefit; the two
statements should run at about the same speed.

I am a little curious what sort of machine you're running on,
because my i7 is much slower.  I ran a few other tests with your
table for perspective.

To get the raw time to just pass the tuples:

SELECT from millionrowtable where xmin = '0';
Time: 125.340 ms
Time: 124.443 ms
Time: 115.629 ms

Just the count(*) of those rows didn't boost the time much:

SELECT count(*) from millionrowtable;
Time: 132.128 ms
Time: 128.036 ms
Time: 125.400 ms

The NULL check added by specifying count(x) boosted it more:

SELECT count(x) from millionrowtable;
Time: 165.858 ms
Time: 163.872 ms
Time: 165.448 ms

A NULL check plus numeric addition gets expensive:

SELECT sum(x) from millionrowtable;
Time: 366.879 ms
Time: 364.503 ms
Time: 365.418 ms

Since sum() and avg() use the same transition function, I was
suprised to see a difference here:

SELECT avg(x) from millionrowtable;
Time: 374.339 ms
Time: 372.294 ms
Time: 366.933 ms

Here's the statement you are talking about optimizing:

SELECT sum(x), count(x)  from millionrowtable;
Time: 441.331 ms
Time: 442.501 ms
Time: 436.930 ms

To confirm that projecting the extra column compared to avg() was
not significant:

SELECT sum(x) / count(x)  from millionrowtable;
Time: 442.404 ms
Time: 436.241 ms
Time: 442.381 ms

So this can reasonably be compared to the avg(x) time above.

On my machine this optimization could be expected to shave off
about 16% of current run time.

One question that arose in my mind running this was whether might
be able to combine sum(x) with count(*) if x was NOT NULL, even
though the arguments don't match.  It might not be worth the
gymnastics of recognizing the special case, and I certainly
wouldn't recommend looking at that optimization in a first pass;
but it might be worth jotting down on a list somewhere....

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Jun 9, 2015 at 11:00 AM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:
> Uh, this also requires serialization and deserialization of non-
> finalized transition state, no?

A bunch of this stuff does, but I recently had a Brilliant Insight: we
don't need to add a new method for serializing and deserializing
transition functions.  We can already do that: to serialize an
aggregate transition state, you run it through the typoutput (or
typsend) function and to deserialize it, you run it through the
typinput (or typreceive) function.  The only problem is that we have
some aggregate functions that use an internal type.  Those could,
however, be changed: we could invent new types for each aggregate that
uses a distinctive internal representation, rather than lumping it all
under internal, and then give those types real input and output
functions.  That way, we don't really need to invent anything new
here.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Jun 9, 2015 at 11:00 AM, Alvaro Herrera
> <alvherre@2ndquadrant.com> wrote:
>> Uh, this also requires serialization and deserialization of non-
>> finalized transition state, no?

> A bunch of this stuff does, but I recently had a Brilliant Insight: we
> don't need to add a new method for serializing and deserializing
> transition functions.  We can already do that: to serialize an
> aggregate transition state, you run it through the typoutput (or
> typsend) function and to deserialize it, you run it through the
> typinput (or typreceive) function.  The only problem is that we have
> some aggregate functions that use an internal type.  Those could,
> however, be changed: we could invent new types for each aggregate that
> uses a distinctive internal representation, rather than lumping it all
> under internal, and then give those types real input and output
> functions.  That way, we don't really need to invent anything new
> here.

Yeah.  Now, there are reasons why some of those aggregates are using
"internal" and not, say, "bytea": they want the core aggregate logic to be
just passing a pointer around and not trying to copy the aggregate's
actual state value.  However, I have been wondering whether the "expanded
objects" stuff I did recently could provide a more principled way to do
that kind of thing.
        regards, tom lane

David Rowley <david.rowley@2ndquadrant.com> wrote:


>> I am a little curious what sort of machine you're running on,
>> because my i7 is much slower.  I ran a few other tests with your
>> table for perspective.
>
> Assert enabled build?

Mystery solved.  Too often I forget to reconfigure with
optimization and without cassert for quick tests like that.
Hopefully the results are not skewed *too* badly by that in this
case.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company