Re: [PATCH] Negative Transition Aggregate Functions (WIP)

I've been working on speeding up aggregate functions when used in the
context of a window's with non fixed frame heads.

Currently if the top of the window is not in a fixed position then when the
window frame moves down the aggregates must be recalculated by looping over
each record in the new scope of the window frame.

Take the following as an example:

SELECT SUM(n::int) OVER (ORDER BY n ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING)
FROM generate_series(1,20000) g(n);

Here the frame head moves along with the current row and always finishes
with the last row in the partition or the last row in the frame if no
partitioning exists.
Currently PostgreSQL must recalculate the aggregate each time, this means
looping from the current row to the end of the frame for each row
produced... So the first row needs 20000 iterations, the 2nd row 19999, 3rd
row 19998 etc.

The above query on the unpatched head, on my laptop takes 36676 ms. With
the attached patch it takes 73 ms. So a speed increase of about 500 times
for 20,000 rows. Of course this performance gap will increase with more
rows and decrease with less rows, but it's even seeing a performance
improvement with as little as 50 rows.

The attached patch is not quite finished yet, I've not yet fully covered
SUM and AVG for all types. I just need to look into numeric a bit more
before I figure that one out.
Here is a list of things still todo:

1. Fully implement negative transition functions for SUM and AVG.
2. CREATE AGGREGATE support for user defined aggregates.
3. Documentation.
4. Look to see which other aggregates apart from COUNT, SUM and AVG that
can make use of this.

Please note that if the aggregate function does not have a negative
transition function setup, e.g MAX and MIN, then the old behaviour will
take place.

One thing that is currently on my mind is what to do when passing volatile
functions to the aggregate. Since the number of times we execute a volatile
function will much depend on the window frame options, I think we should
include some sort of warning in the documentation that "The number of times
that the expression is evaluated within the aggregate function when used in
the context of a WINDOW is undefined". The other option would be to disable
this optimisation if the aggregate expression contained a volatile
function, but doing this, to me seems a bit weird as is anyone actually
going to be depending on a volatile function being executed so many times?

If anyone can see any road blocking issues to why this optimisation cannot
be done please let me know.

Otherwise I'll continue to work on this so that it is ready for CF4.

Regards

David Rowley

David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> The attached patch is not quite finished yet, I've not yet fully covered
> SUM and AVG for all types.

I think you *can't* cover them for the float types; roundoff error
would mean you don't get the same answers as before.

regards, tom lane

On 14 Dec 2013 15:40, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> > The attached patch is not quite finished yet, I've not yet fully covered
> > SUM and AVG for all types.
>
> I think you *can't* cover them for the float types; roundoff error
> would mean you don't get the same answers as before.

I was going to say the same thing. But then I started to wonder.... What's
so special about the answers we used to give? They are also subject to
round off and the results are already quite questionable in those cases.

On Sun, Dec 15, 2013 at 12:48 PM, Greg Stark <stark(at)mit(dot)edu> wrote:

>
> On 14 Dec 2013 15:40, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> >
> > David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> > > The attached patch is not quite finished yet, I've not yet fully
> covered
> > > SUM and AVG for all types.
> >
> > I think you *can't* cover them for the float types; roundoff error
> > would mean you don't get the same answers as before.
>
> I was going to say the same thing. But then I started to wonder.... What's
> so special about the answers we used to give? They are also subject to
> round off and the results are already quite questionable in those cases.
>
I guess they probably shouldn't be, subject to rounding / influenced by
errors from tuples that are out of scope of the aggregate context.
Though saying that it would be a shame to have this optimisation for all
but float and double. I can imagine the questions in [GENERAL].. Why is
SUM(<int>) OVER ().. fast but SUM(<float>) OVER () slow? I wonder what
other RDBMS' do here...

Regards

David Rowley

Greg Stark <stark(at)mit(dot)edu> writes:
> On 14 Dec 2013 15:40, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> I think you *can't* cover them for the float types; roundoff error
>> would mean you don't get the same answers as before.

> I was going to say the same thing. But then I started to wonder.... What's
> so special about the answers we used to give? They are also subject to
> round off and the results are already quite questionable in those cases.

Well, we can't easily do better than the old answers, and the new ones
might be arbitrarily worse. Example: sum or average across single-row
windows ought to be exact in any case, but it might be arbitrarily wrong
with the negative-transition technique.

More generally, this is supposed to be a performance enhancement only;
it's not supposed to change the results.

This consideration also makes me question whether we should apply the
method for NUMERIC. Although in principle numeric addition/subtraction
is exact, such a sequence could leave us with a different dscale than
is returned by the existing code. I'm not sure if changing the number of
trailing zeroes is a big enough behavior change to draw complaints.

regards, tom lane

On 12/14/2013 05:00 PM, Tom Lane wrote:
> This consideration also makes me question whether we should apply the
> method for NUMERIC. Although in principle numeric addition/subtraction
> is exact, such a sequence could leave us with a different dscale than
> is returned by the existing code. I'm not sure if changing the number of
> trailing zeroes is a big enough behavior change to draw complaints.

If we're going to disqualify NUMERIC too, we might as well bounce the
feature. Without a fast FLOAT or NUMERIC, you've lost most of the
target audience.

I think even the FLOAT case deserves some consideration. What's the
worst-case drift? In general, folks who do aggregate operations on
FLOATs aren't expecting an exact answer, or one which is consistent
beyond a certain number of significant digits.

And Dave is right: how many bug reports would we get about "NUMERIC is
fast, but FLOAT is slow"?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Sun, Dec 15, 2013 at 2:27 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:

> If we're going to disqualify NUMERIC too, we might as well bounce the
> feature. Without a fast FLOAT or NUMERIC, you've lost most of the
> target audience.
>
>
I don't agree with this. I'm going with the opinion that the more types and
aggregates we can support (properly) the better. I'd rather delay
implementations of the ones which could change results than see them as a
roadblock for the ones we can implement today without this danger.

I think the feature is worth it alone if we could improve COUNT(*).
It's a bit silly to have to loop through all the tuples in a tuplestore to
see how many there are after removing one, when we already knew the count
before removing it. Something like, 10 - 1 .... ummm I dunno, let's count
again.. 1, 2, 3, 4, 5, 6, 7, 8, 9.... It's 9!! Where with this patch it's
just 10 - 1 *result*. Feels a bit like asking a kid, if you have 10 beans
and you take 1 away, how many will there be. You and I know 9, but the kid
might have to count them again. PostgreSQL counts them again.

Regards

David Rowley

--
> Josh Berkus
> PostgreSQL Experts Inc.
> http://pgexperts.com
>

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> I think even the FLOAT case deserves some consideration. What's the
> worst-case drift?

Complete loss of all significant digits.

The case I was considering earlier of single-row windows could be made
safe (I think) if we apply the negative transition function first, before
incorporating the new row(s). Then for example if you've got float8 1e20
followed by 1, you compute (1e20 - 1e20) + 1 and get the right answer.
It's not so good with two-row windows though:

Table correct sum of negative-transition
this + next value result
1e20 1e20 1e20 + 1 = 1e20
1 1 1e20 - 1e20 + 0 = 0
0

> In general, folks who do aggregate operations on
> FLOATs aren't expecting an exact answer, or one which is consistent
> beyond a certain number of significant digits.

Au contraire. People who know what they're doing expect the results
to be what an IEEE float arithmetic unit would produce for the given
calculation. They know how the roundoff error ought to behave, and they
will not thank us for doing a calculation that's not the one specified.
I will grant you that there are plenty of clueless people out there
who *don't* know this, but they shouldn't be using float arithmetic
anyway.

> And Dave is right: how many bug reports would we get about "NUMERIC is
> fast, but FLOAT is slow"?

I've said this before, but: we can make it arbitrarily fast if we don't
have to get the right answer. I'd rather get "it's slow" complaints
than "this is the wrong answer" complaints.

regards, tom lane

David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> On Sun, Dec 15, 2013 at 2:27 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:
>> If we're going to disqualify NUMERIC too, we might as well bounce the
>> feature. Without a fast FLOAT or NUMERIC, you've lost most of the
>> target audience.

> I think the feature is worth it alone if we could improve COUNT(*).

Agreed, count(*) and operations on integers are alone enough to be worth
the trouble.

regards, tom lane

I wrote:
> It's not so good with two-row windows though:

Actually, carrying that example a bit further makes the point even more
forcefully:

Table correct sum of negative-transition
this + next value result
1e20 1e20 1e20 + 1 = 1e20
1 1 1e20 - 1e20 + 0 = 0
0 0 0 - 1 + 0 = -1
0 1 -1 - 0 + 1 = 0
1

Those last few answers are completely corrupt.

regards, tom lane

On Sun, Dec 15, 2013 at 3:08 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> I wrote:
> > It's not so good with two-row windows though:
>
> Actually, carrying that example a bit further makes the point even more
> forcefully:
>
> Table correct sum of negative-transition
> this + next value result
> 1e20 1e20 1e20 + 1 = 1e20
> 1 1 1e20 - 1e20 + 0 = 0
> 0 0 0 - 1 + 0 = -1
> 0 1 -1 - 0 + 1 = 0
> 1
>
> Those last few answers are completely corrupt.
>
>
I guess the answer for the people that complain about slowness could be
that they create their own aggregate function which implements float4pl as
the trans function and float4mi as the negative trans function. They can
call it SUMFASTBUTWRONG() if they like. Perhaps it would be worth a note in
the documents for this patch?

I've removed the negative trans function setups for float4 and float8 with
SUM and AVG stuff in my working copy now.

As for numeric, I did start working on this just after I posted the
original patch and before I saw your comment about it. I did end up making
do_numeric_desperse() which was to be the reverse of do_numeric_accum(),
but I got stuck on the equivalent of when do_numeric_accum()
does mul_var(&X, &X, &X2, X.dscale * 2);

If it is decided that we don't want to implement a negative trans function
for numeric, then I guess I could leave in my trans function to allow users
to create their own fast version, maybe?

Regards

David Rowley

> regards, tom lane
>

David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> I guess the answer for the people that complain about slowness could be
> that they create their own aggregate function which implements float4pl as
> the trans function and float4mi as the negative trans function. They can
> call it SUMFASTBUTWRONG() if they like. Perhaps it would be worth a note in
> the documents for this patch?

I think it would be an absolutely perfect documentation example to show
how to set up such an aggregate (and then point out the risks, of course).

> As for numeric, I did start working on this just after I posted the
> original patch and before I saw your comment about it. I did end up making
> do_numeric_desperse() which was to be the reverse of do_numeric_accum(),
> but I got stuck on the equivalent of when do_numeric_accum()
> does mul_var(&X, &X, &X2, X.dscale * 2);

Ummm ... why doesn't it work to just use numeric_add and numeric_sub,
exactly parallel to the float case?

regards, tom lane

On Sun, Dec 15, 2013 at 3:08 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> I wrote:
> > It's not so good with two-row windows though:
>
> Actually, carrying that example a bit further makes the point even more
> forcefully:
>
> Table correct sum of negative-transition
> this + next value result
> 1e20 1e20 1e20 + 1 = 1e20
> 1 1 1e20 - 1e20 + 0 = 0
> 0 0 0 - 1 + 0 = -1
> 0 1 -1 - 0 + 1 = 0
> 1
>
> Those last few answers are completely corrupt.
>
>
For sake of the archives I just wanted to reproduce this...
I used the following query with the patch which was attached upthread to
confirm this:

SELECT sum(n::float8) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND 1
FOLLOWING)
FROM (VALUES(1,1e20),(2,1)) n(i,n);

sum
--------
1e+020
0
(2 rows)

SUM(1) should equal 1 not 0.

But unpatched I get:

sum
--------
1e+020
1
(2 rows)

This discovery seems like good information to keep around, so I've added a
regression test in my local copy of the patch to try to make sure nobody
tries to add a negative trans for float or double in the future.

Regards

David Rowley

> regards, tom lane
>

On Sun, Dec 15, 2013 at 9:29 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> > I guess the answer for the people that complain about slowness could be
> > that they create their own aggregate function which implements float4pl
> as
> > the trans function and float4mi as the negative trans function. They can
> > call it SUMFASTBUTWRONG() if they like. Perhaps it would be worth a note
> in
> > the documents for this patch?
>
> I think it would be an absolutely perfect documentation example to show
> how to set up such an aggregate (and then point out the risks, of course).
>
>
I've attached an updated patch which includes some documentation.
I've also added support for negfunc in CREATE AGGREGATE. Hopefully that's
an ok name for the option, but if anyone has any better ideas please let
them be known.

For the checks before the aggregate is created, I put these together quite
quickly and I think I'm still missing a check to ensure that the strict
property for the trans and negtrans functions are set to the same thing,
though I do have a runtime check for this, it's likely bad to wait until
then to tell the user about it.

> As for numeric, I did start working on this just after I posted the
> > original patch and before I saw your comment about it. I did end up
> making
> > do_numeric_desperse() which was to be the reverse of do_numeric_accum(),
> > but I got stuck on the equivalent of when do_numeric_accum()
> > does mul_var(&X, &X, &X2, X.dscale * 2);
>
> Ummm ... why doesn't it work to just use numeric_add and numeric_sub,
> exactly parallel to the float case?
>
>
I've not quite got back to this yet and I actually pulled out my initial
try at this thinking that we didn't want it because it was affecting the
scale. The transition function for SUM numeric does not seem to use
numeric_add, it uses numeric_avg_accum as the transition function which
lets do_numeric_accum do the hard work and that just does add_var. I
changes these add_var's to sub_var's and altered the initial value to flip
the sign so that NULL,10 would be -10 instead of 10. I think that's all it
needs, and I guess I leave the dscale as is in this situation then?

Regards

David Rowley

> regards, tom lane
>

David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> I've attached an updated patch which includes some documentation.
> I've also added support for negfunc in CREATE AGGREGATE. Hopefully that's
> an ok name for the option, but if anyone has any better ideas please let
> them be known.

I'd be a bit inclined to build the terminology around "reverse" instead of
"negative" --- the latter seems a bit too arithmetic-centric. But that's
just MHO.

regards, tom lane

On Dec 15, 2013 6:44 PM, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> > I've attached an updated patch which includes some documentation.
> > I've also added support for negfunc in CREATE AGGREGATE. Hopefully
that's
> > an ok name for the option, but if anyone has any better ideas please let
> > them be known.
>
> I'd be a bit inclined to build the terminology around "reverse" instead of
> "negative" --- the latter seems a bit too arithmetic-centric. But that's
> just MHO.

To contribute to the bike shedding, inverse is often used in similar
contexts.

--
Ants Aasma

On Mon, Dec 16, 2013 at 6:00 AM, Ants Aasma <ants(dot)aasma(at)eesti(dot)ee> wrote:

> On Dec 15, 2013 6:44 PM, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> > > I've attached an updated patch which includes some documentation.
> > > I've also added support for negfunc in CREATE AGGREGATE. Hopefully
> that's
> > > an ok name for the option, but if anyone has any better ideas please
> let
> > > them be known.
> >
> > I'd be a bit inclined to build the terminology around "reverse" instead
> of
> > "negative" --- the latter seems a bit too arithmetic-centric. But that's
> > just MHO.
>
> To contribute to the bike shedding, inverse is often used in similar
> contexts.
>
I guess it's not really bike shedding, most of the work I hope is done, so
I might as well try to get the docs polished up and we'd need a consensus
on what we're going to call them before I can get that done.

I like both of these better than negative transition function and I agree
negative implies arithmetic rather than opposite.
Out of these 2 I do think inverse fits better than reverse, so I guess that
would make it "inverse aggregate transition function".
Would that make the CREATE AGGREGATE option be INVFUNC ?

Any other ideas or +1's for any of the existing ones?

Regards

David Rowley

> --
> Ants Aasma
>

On Mon, Dec 16, 2013 at 08:39:33PM +1300, David Rowley wrote:
> On Mon, Dec 16, 2013 at 6:00 AM, Ants Aasma <ants(dot)aasma(at)eesti(dot)ee> wrote:
>
> > On Dec 15, 2013 6:44 PM, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > > David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> > > > I've attached an updated patch which includes some documentation.
> > > > I've also added support for negfunc in CREATE AGGREGATE. Hopefully
> > that's
> > > > an ok name for the option, but if anyone has any better ideas please
> > let
> > > > them be known.
> > >
> > > I'd be a bit inclined to build the terminology around "reverse" instead
> > of
> > > "negative" --- the latter seems a bit too arithmetic-centric. But that's
> > > just MHO.
> >
> > To contribute to the bike shedding, inverse is often used in similar
> > contexts.
> >
> I guess it's not really bike shedding, most of the work I hope is done, so
> I might as well try to get the docs polished up and we'd need a consensus
> on what we're going to call them before I can get that done.
>
> I like both of these better than negative transition function and I agree
> negative implies arithmetic rather than opposite.
> Out of these 2 I do think inverse fits better than reverse, so I guess that
> would make it "inverse aggregate transition function".
> Would that make the CREATE AGGREGATE option be INVFUNC ?
>
> Any other ideas or +1's for any of the existing ones?

+1 for inverse.

Cheers,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

On 12/16/2013 08:39 AM, David Rowley wrote:
> On Mon, Dec 16, 2013 at 6:00 AM, Ants Aasma <ants(dot)aasma(at)eesti(dot)ee
> <mailto:ants(dot)aasma(at)eesti(dot)ee>> wrote:
>
> On Dec 15, 2013 6:44 PM, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us
> <mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us>> wrote:
> > David Rowley <dgrowleyml(at)gmail(dot)com
> <mailto:dgrowleyml(at)gmail(dot)com>> writes:
> > > I've attached an updated patch which includes some documentation.
> > > I've also added support for negfunc in CREATE AGGREGATE.
> Hopefully that's
> > > an ok name for the option, but if anyone has any better ideas
> please let
> > > them be known.
> >
> > I'd be a bit inclined to build the terminology around "reverse"
> instead of
> > "negative" --- the latter seems a bit too arithmetic-centric.
> But that's
> > just MHO.
>
> To contribute to the bike shedding, inverse is often used in
> similar contexts.
>
> I guess it's not really bike shedding, most of the work I hope is
> done, so I might as well try to get the docs polished up and we'd need
> a consensus on what we're going to call them before I can get that done.
>
> I like both of these better than negative transition function and I
> agree negative implies arithmetic rather than opposite.
> Out of these 2 I do think inverse fits better than reverse, so I guess
> that would make it "inverse aggregate transition function".
> Would that make the CREATE AGGREGATE option be INVFUNC ?
>
> Any other ideas or +1's for any of the existing ones?
+1, inverse good :)
>
> Regards
>
> David Rowley
>
> --
> Ants Aasma
>
>

--
Hannu Krosing
PostgreSQL Consultant
Performance, Scalability and High Availability
2ndQuadrant Nordic OÜ

On 12/15/2013 03:57 AM, Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> I think even the FLOAT case deserves some consideration. What's the
>> worst-case drift?
>
> Complete loss of all significant digits.
>
> The case I was considering earlier of single-row windows could be made
> safe (I think) if we apply the negative transition function first, before
> incorporating the new row(s). Then for example if you've got float8 1e20
> followed by 1, you compute (1e20 - 1e20) + 1 and get the right answer.
> It's not so good with two-row windows though:
>
> Table correct sum of negative-transition
> this + next value result
> 1e20 1e20 1e20 + 1 = 1e20
> 1 1 1e20 - 1e20 + 0 = 0
> 0
>
>> In general, folks who do aggregate operations on
>> FLOATs aren't expecting an exact answer, or one which is consistent
>> beyond a certain number of significant digits.
>
> Au contraire. People who know what they're doing expect the results
> to be what an IEEE float arithmetic unit would produce for the given
> calculation. They know how the roundoff error ought to behave, and they
> will not thank us for doing a calculation that's not the one specified.
> I will grant you that there are plenty of clueless people out there
> who *don't* know this, but they shouldn't be using float arithmetic
> anyway.
>
>> And Dave is right: how many bug reports would we get about "NUMERIC is
>> fast, but FLOAT is slow"?
>
> I've said this before, but: we can make it arbitrarily fast if we don't
> have to get the right answer. I'd rather get "it's slow" complaints
> than "this is the wrong answer" complaints.

There's another technique we could use which doesn't need a negative
transition function, assuming the order you feed the values to the
aggreate function doesn't matter: keep subtotals. For example, if the
window first contains values 1, 2, 3, 4, you calculate 3 + 4 = 7, and
then 1 + 2 + 7 = 10. Next, 1 leaves the window, and 5 enters it. Now you
calculate 2 + 7 + 5 = 14. By keeping the subtotal (3 + 4 = 7) around,
you saved one addition compared to calculating 2 + 3 + 4 + 5 from scratch.

The negative transition function is a lot simpler and faster for
count(*) and integer operations, so we probably should implement that
anyway. But the subtotals technique could be very useful for other data
types.

- Heikki

On Mon, Dec 16, 2013 at 9:39 PM, Heikki Linnakangas <hlinnakangas(at)vmware(dot)com
> wrote:

>
> There's another technique we could use which doesn't need a negative
> transition function, assuming the order you feed the values to the aggreate
> function doesn't matter: keep subtotals. For example, if the window first
> contains values 1, 2, 3, 4, you calculate 3 + 4 = 7, and then 1 + 2 + 7 =
> 10. Next, 1 leaves the window, and 5 enters it. Now you calculate 2 + 7 +
> 5 = 14. By keeping the subtotal (3 + 4 = 7) around, you saved one addition
> compared to calculating 2 + 3 + 4 + 5 from scratch.
>
> The negative transition function is a lot simpler and faster for count(*)
> and integer operations, so we probably should implement that anyway. But
> the subtotals technique could be very useful for other data types.
>
> - Heikki
>

That's quite interesting. I guess we would need another flag in
pg_aggregate to mark if the order of the tuples matters, string_agg would
be an example of one that would have to skip this.

At least for ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING if the
aggregate order did not matter than it would likely be quite efficient just
to aggregate from the bottom up and materialise the results at each tuple
and store it in the tuple store, then just use that materialised value when
that tuple is processed. This method won't work when the frame base is not
fixed.

I had been thinking ahead on how to improve MIN and MAX cases too. I came
up with something called "tuple store indexes" that could be build as
binary search trees with a composite index on the tuple position and the
aggregate's sort operator... Something similar to how the following query
could use an index on (id,value) to calculate max()
select max(value) from test where id between 1 and 100;
It's certainly not something for this patch, but it was an idea I came up
with which I think would be possible without adding any more columns to
pg_aggregate.

Regards

David Rowley

On Sun, Dec 15, 2013 at 12:17 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

>
> One thing that is currently on my mind is what to do when passing volatile
> functions to the aggregate. Since the number of times we execute a volatile
> function will much depend on the window frame options, I think we should
> include some sort of warning in the documentation that "The number of times
> that the expression is evaluated within the aggregate function when used in
> the context of a WINDOW is undefined". The other option would be to disable
> this optimisation if the aggregate expression contained a volatile
> function, but doing this, to me seems a bit weird as is anyone actually
> going to be depending on a volatile function being executed so many times?
>
>
>
I just wanted to bring this back into people's minds.
During writing this patch I found and removed a comment which was a todo
item to implement these negative transition functions. This comment said
about maybe disallowing the use of these if the expression of the function
contained a volatile function. I wondered why this was important and I
still don't really see why we would disallow this only to enforce that we
call that function an undefined number of times anyway.

nextval was the only volatile function that I could think of that would
allow me to give an example which was easy to understand what is going on
here.

CREATE SEQUENCE test_seq;
SELECT currval('test_seq'),
COUNT(*) OVER (ORDER BY x.x ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING),
SUM(nextval('test_seq')) OVER (ORDER BY x.x ROWS BETWEEN CURRENT ROW
AND UNBOUNDED FOLLOWING)
FROM generate_series(1,2) x (x);
DROP SEQUENCE test_seq;

The results are:
currval | count | sum
---------+-------+-----
2 | 2 | 3
3 | 1 | 3

I've not looked to see if the spec has anything about this but, the first
row will have sum as 1+2 then the 2nd row will just have 1 row to aggregate
and the value will be 3 due to nextval returning 3, I could see an argument
that the results for this should actually be:

currval | count | sum
---------+-------+-----
2 | 2 | 3
3 | 1 | 2

If it was then the solution would have to be to materalise the expression
by evaluating it once for each tuple which sounds like a big change. I
thought maybe if we're going to be playing around with the number of times
these expressions are evaluated then we should stick a node in the docs to
tell our users not to depend on this.

Something like the attached maybe.

David Rowley <dgrowleyml(at)gmail(dot)com> writes:
>> One thing that is currently on my mind is what to do when passing volatile
>> functions to the aggregate. Since the number of times we execute a volatile
>> function will much depend on the window frame options, I think we should
>> include some sort of warning in the documentation that "The number of times
>> that the expression is evaluated within the aggregate function when used in
>> the context of a WINDOW is undefined". The other option would be to disable
>> this optimisation if the aggregate expression contained a volatile
>> function, but doing this, to me seems a bit weird as is anyone actually
>> going to be depending on a volatile function being executed so many times?

Once again: this patch has no business changing any user-visible behavior.
That would include not changing the number of evaluations of volatile
functions. The planner is full of places where optimizations are disabled
for volatile subexpressions, and I don't see why this should be different.

regards, tom lane

On Sat, Dec 14, 2013 at 8:00 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Greg Stark <stark(at)mit(dot)edu> writes:
>> On 14 Dec 2013 15:40, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> I think you *can't* cover them for the float types; roundoff error
>>> would mean you don't get the same answers as before.
>
>> I was going to say the same thing. But then I started to wonder.... What's
>> so special about the answers we used to give? They are also subject to
>> round off and the results are already quite questionable in those cases.
>
> Well, we can't easily do better than the old answers, and the new ones
> might be arbitrarily worse. Example: sum or average across single-row
> windows ought to be exact in any case, but it might be arbitrarily wrong
> with the negative-transition technique.
>
> More generally, this is supposed to be a performance enhancement only;
> it's not supposed to change the results.
>
> This consideration also makes me question whether we should apply the
> method for NUMERIC. Although in principle numeric addition/subtraction
> is exact, such a sequence could leave us with a different dscale than
> is returned by the existing code. I'm not sure if changing the number of
> trailing zeroes is a big enough behavior change to draw complaints.

I tend to think it is. I'm not sure if it's worth it, but you could
finesse this problem with a more complex transition state - keep track
of how many values with any given scale are part of the current
window.

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

On Tue, Dec 17, 2013 at 1:18 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Once again: this patch has no business changing any user-visible behavior.
> That would include not changing the number of evaluations of volatile
> functions. The planner is full of places where optimizations are disabled
> for volatile subexpressions, and I don't see why this should be different.
>
>
My point was meant to be more along the lines of that I thought it was
already broken and it perhaps should be fixed or at the very least we could
warn the users about it.
I would imagine that most of those other places in the planner are to
prevent extra evaluations of volatile functions? In this particular case
we're already evaluating these multiple extra times when a tuple moves of
the top of the frame. I would have thought that we should only evaluate the
volatile function once per tuple. This is not what the current
implementation does.

I don't have an issue skipping this optimisation when the aggregate's
expression contain any volatile functions. I just wanted to raise my
concerns about the current behaviour, which I find a bit bizarre.

Regards

David Rowley

> regards, tom lane
>

On Tue, Dec 17, 2013 at 11:06 AM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> On Tue, Dec 17, 2013 at 1:18 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>> Once again: this patch has no business changing any user-visible behavior.
>> That would include not changing the number of evaluations of volatile
>> functions. The planner is full of places where optimizations are disabled
>> for volatile subexpressions, and I don't see why this should be different.
>>
>>
> My point was meant to be more along the lines of that I thought it was
> already broken and it perhaps should be fixed or at the very least we could
> warn the users about it.
> I would imagine that most of those other places in the planner are to
> prevent extra evaluations of volatile functions? In this particular case
> we're already evaluating these multiple extra times when a tuple moves of
> the top of the frame. I would have thought that we should only evaluate the
> volatile function once per tuple. This is not what the current
> implementation does.
>
> I don't have an issue skipping this optimisation when the aggregate's
> expression contain any volatile functions. I just wanted to raise my
> concerns about the current behaviour, which I find a bit bizarre.
>
>
>
To improve on the example I used to try and get my point across:

These were all run on an unpatched copy of HEAD. Ignore the actual results
from sum() and look at what currval() is set to after each query.

create sequence seq;
select sum(nextval('seq')) over (order by n rows between current row and
unbounded following)
from generate_series(1,10) n(n);
select currval('seq');

drop sequence seq;
create sequence seq;
select sum(nextval('seq')) over (order by n)
from generate_series(1,10) n(n);
select currval('seq');

nextval() is executed 55 times with the first query and 10 times with the
2nd query. Of course this is because the current implementation requires
that when a tuple moves out of scope that the whole frame be re-aggregated.
I had thought that all of the places that disabled optimisations due to
there being volatile somewhere were to stop the number of executions being
undefined, this case seems undefined already, or at least I can't find
anywhere in the docs that says the expression will be executed this number
of times.

Once again, I'm not fighting to have inverse transitions uses when volatile
functions are involved, I'll happily disable that. I just wanted to raise
this to find out if it's intended or not and it seemed like a good thread
to do it on.

Regards

David Rowley

On Mon, Dec 16, 2013 at 9:36 PM, Hannu Krosing <hannu(at)2ndquadrant(dot)com>wrote:

> On 12/16/2013 08:39 AM, David Rowley wrote:
>
>
> Any other ideas or +1's for any of the existing ones?
>
> +1, inverse good :)
>
>
In the attached patch I've renamed negative to inverse. I've also disabled
the inverse functions when an expression in an aggregate contains a
volatile function.

Regards

David Rowley

On Tue, Dec 17, 2013 at 10:51 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> On Mon, Dec 16, 2013 at 9:36 PM, Hannu Krosing <hannu(at)2ndquadrant(dot)com>wrote:
>
>> On 12/16/2013 08:39 AM, David Rowley wrote:
>>
>>
>> Any other ideas or +1's for any of the existing ones?
>>
>> +1, inverse good :)
>>
>>
> In the attached patch I've renamed negative to inverse. I've also disabled
> the inverse functions when an expression in an aggregate contains a
> volatile function.
>
>
I've attached an updated patch in which I've done some more work to the
documents and also added some more sanity checking around CREATE AGGREGATE.
The previous patch allowed CREATE AGGREGATE to accept a transition function
which was strict and an inverse transition function which was not, or vise
versa.

I've also added a bunch of regression tests around create aggregate which
were missing in the previous patch.

Regards

David Rowley

On Sat, December 21, 2013 10:53, David Rowley wrote:

> [inverse_transition_functions_v1.1.patch.gz ]

Hi,

I know, $subject says "WIP", but I assumed it's supposed to compile, so I tried to get this to run on linux (Centos 5.0).
gcc 4.8.2,
with

./configure --prefix=/home/aardvark/pg_stuff/pg_installations/pgsql.inverse --with-pgport=6554 --enable-depend
--enable-cassert --enable-debug --with-openssl --with-perl --with-libxml --with-libxslt --with-ossp-uuid

but although applying the patch and configure were OK, the compile went awry:

[...]
make[4]: Entering directory `/home/aardvark/pg_stuff/pg_sandbox/pgsql.inverse/src/backend'
make[4]: Nothing to be done for `submake-errcodes'.
make[4]: Leaving directory `/home/aardvark/pg_stuff/pg_sandbox/pgsql.inverse/src/backend'
make[3]: Leaving directory `/home/aardvark/pg_stuff/pg_sandbox/pgsql.inverse/src/common'
make -C catalog schemapg.h
make[3]: Entering directory `/home/aardvark/pg_stuff/pg_sandbox/pgsql.inverse/src/backend/catalog'
cd ../../../src/include/catalog && '/home/aardvark/perl-5.19/bin/perl' ./duplicate_oids
1220
1221
1800
1801
1970
1971
make[3]: Leaving directory `/home/aardvark/pg_stuff/pg_sandbox/pgsql.inverse/src/backend/catalog'
make[2]: Leaving directory `/home/aardvark/pg_stuff/pg_sandbox/pgsql.inverse/src/backend'
make[1]: Leaving directory `/home/aardvark/pg_stuff/pg_sandbox/pgsql.inverse/src'
-- [2013.12.21 11:35:29 inverse] make contrib
dblink.c:55:28: fatal error: utils/fmgroids.h: No such file or directory
#include "utils/fmgroids.h"
^
compilation terminated.
make[1]: *** [dblink.o] Error 1
make: *** [all-dblink-recurse] Error 2
-- make returned 2 - abort

( although that output mentions perl 5,19, I also tried with regular perl 5.18, cassert on/off, etc.; every combination
yielded this same compile error )

Thanks,

Erik Rijkers

On Sat, Dec 21, 2013 at 11:47 PM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:

> On Sat, December 21, 2013 10:53, David Rowley wrote:
>
> > [inverse_transition_functions_v1.1.patch.gz ]
>
> Hi,
>
> I know, $subject says "WIP", but I assumed it's supposed to compile, so I
> tried to get this to run on linux (Centos 5.0).
> gcc 4.8.2,
> with
>

<snip>

> cd ../../../src/include/catalog && '/home/aardvark/perl-5.19/bin/perl'
> ./duplicate_oids
> 1220
> 1221
> 1800
> 1801
> 1970
> 1971
>

Thanks for the report. It seems the windows build does not check for
duplicate OIDs and the linux one does.
I'll just need to change the Oids of the new functions I've added, only it
seems the unused_oids perl script does not like windows.

I'll try to get you a working patch shortly.

Regards

David Rowley

On Sun, Dec 22, 2013 at 12:12 AM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> On Sat, Dec 21, 2013 at 11:47 PM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:
>
>> On Sat, December 21, 2013 10:53, David Rowley wrote:
>>
>> > [inverse_transition_functions_v1.1.patch.gz ]
>>
>> Hi,
>>
>> I know, $subject says "WIP", but I assumed it's supposed to compile, so I
>> tried to get this to run on linux (Centos 5.0).
>> gcc 4.8.2,
>> with
>>
>
> <snip>
>
>
>> cd ../../../src/include/catalog && '/home/aardvark/perl-5.19/bin/perl'
>> ./duplicate_oids
>> 1220
>> 1221
>> 1800
>> 1801
>> 1970
>> 1971
>>
>
> Thanks for the report. It seems the windows build does not check for
> duplicate OIDs and the linux one does.
> I'll just need to change the Oids of the new functions I've added, only it
> seems the unused_oids perl script does not like windows.
>
> I'll try to get you a working patch shortly.
>
>
Please find attached an updated patch which should remove the duplicate OID
problem you saw.

Regards

David Rowley

> Regards
>
> David Rowley
>
>

On Sat, December 21, 2013 12:38, David Rowley wrote:
> [ inverse_transition_functions_v1.2.patch.gz ]
> Please find attached an updated patch which should remove the duplicate OID
> problem you saw.

That fixes it, thanks

There is 1 of 141 failed tests:

window ... FAILED

but that's easily ignored for now.

I'll do some testing later,

Thanks

Erik Rijkers

On Sun, Dec 22, 2013 at 12:49 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:

> On Sat, December 21, 2013 12:38, David Rowley wrote:
> > [ inverse_transition_functions_v1.2.patch.gz ]
> > Please find attached an updated patch which should remove the duplicate
> OID
> > problem you saw.
>
> That fixes it, thanks
>
> There is 1 of 141 failed tests:
>
> window ... FAILED
>
>
That's strange, it passes here.

Would you be able to send me the regression diff file?

Regards

David Rowley

> but that's easily ignored for now.
>
> I'll do some testing later,
>
> Thanks
>
> Erik Rijkers
>
>
>
>
>
>
>

On Sat, December 21, 2013 12:52, David Rowley wrote:
> On Sun, Dec 22, 2013 at 12:49 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:
>
>> On Sat, December 21, 2013 12:38, David Rowley wrote:
>> > [ inverse_transition_functions_v1.2.patch.gz ]
>> > Please find attached an updated patch which should remove the duplicate
>> OID
>> > problem you saw.
>>
>> That fixes it, thanks
>>
>> There is 1 of 141 failed tests:
>>
>> window ... FAILED
>>
>>
> That's strange, it passes here.
>
> Would you be able to send me the regression diff file?
>

attached...

On Sun, Dec 22, 2013 at 1:01 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:

> On Sat, December 21, 2013 12:52, David Rowley wrote:
> > On Sun, Dec 22, 2013 at 12:49 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:
> >
> >> On Sat, December 21, 2013 12:38, David Rowley wrote:
> >> > [ inverse_transition_functions_v1.2.patch.gz ]
> >> > Please find attached an updated patch which should remove the
> duplicate
> >> OID
> >> > problem you saw.
> >>
> >> That fixes it, thanks
> >>
> >> There is 1 of 141 failed tests:
> >>
> >> window ... FAILED
> >>
> >>
> > That's strange, it passes here.
> >
> > Would you be able to send me the regression diff file?
> >
>
> attached...
>

Thanks

This was just down to some missing trailing white space on the expected
results. I've fixed these up and attached another patch.

Regards

David Rowley

On Sun, Dec 22, 2013 at 2:42 AM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> On Sun, Dec 22, 2013 at 1:01 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:
>
>> On Sat, December 21, 2013 12:52, David Rowley wrote:
>> > On Sun, Dec 22, 2013 at 12:49 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:
>> >
>> >> On Sat, December 21, 2013 12:38, David Rowley wrote:
>> >> > [ inverse_transition_functions_v1.2.patch.gz ]
>> >> > Please find attached an updated patch which should remove the
>> duplicate
>> >> OID
>> >> > problem you saw.
>> >>
>> >> That fixes it, thanks
>> >>
>> >> There is 1 of 141 failed tests:
>> >>
>> >> window ... FAILED
>> >>
>> >>
>> > That's strange, it passes here.
>> >
>> > Would you be able to send me the regression diff file?
>> >
>>
>> attached...
>>
>
> Thanks
>
> This was just down to some missing trailing white space on the expected
> results. I've fixed these up and attached another patch.
>
>
I've attached an updated patch which is re-merged to current head.

I've also done a bit more work to the patch:
Added inverse transition functions for all the stddev() type aggregates for
all int types.
Added inverse transition function for SUM with bigint
Added pg_dump support.

I've yet to do SUM or AVG for numeric types due to some concern with having
more digits after the decimal point after inverse transitions take place.

Regards

David Rowley

Regards
>
> David Rowley
>
>

On Wed, December 25, 2013 14:49, David Rowley wrote:

> [ inverse_transition_functions_v1.5.patch.gz ]

I ran into the following problem which is, I think, NOT a problem with your patch but with my setup. Still, if anyone can
enlighten me on its cause I'd be thankful (it shows up every now and then for me).

I have a 200 GB dev database running under 9.4devel that I thought I could now, for test purposes, compile a patched
postgres binary for (i.e.: a HEAD + inverse_transition_functions_v1.5.patch.gz binary), so as to avoid an initdb and use
the existing 200 GB data.

I know the patch is valid, because a separately built, newly initdb-ed instance runs the below statement without fail.

But running from existing 200 gb dev database I get:

$ echo "\\set VERBOSITY verbose \\\\ SELECT SUM(n::integer) OVER (ORDER BY n ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING) FROM generate_series(1, 100) g(n)" | psql
ERROR: XX000: cache lookup failed for type 0
LOCATION: get_typlenbyval, lsyscache.c:1895
Time: 2.752 ms

Is there a way I can use the existing database and avoid both initdb and this error?

Thanks,

Erik Rijkers

See also:
[1]
http://www.postgresql.org/message-id/flat/E5F4C5A18CAB7A4DA23080DE9CE8158603E67AA1(at)eaubrmw001(dot)eapac(dot)ericsson(dot)se#E5F4C5A18CAB7A4DA23080DE9CE8158603E67AA1@eaubrmw001.eapac.ericsson.se

"Erik Rijkers" <er(at)xs4all(dot)nl> writes:
> I have a 200 GB dev database running under 9.4devel that I thought I could now, for test purposes, compile a patched
> postgres binary for (i.e.: a HEAD + inverse_transition_functions_v1.5.patch.gz binary), so as to avoid an initdb and use
> the existing 200 GB data.

That's not going to work for any patch that touches the initial contents
of the system catalogs.

> Is there a way I can use the existing database and avoid both initdb and this error?

Use pg_upgrade to move the data into a newly initdb'd directory. Note
you will need both unpatched and patched executables for this.

regards, tom lane

On Sun, Dec 15, 2013 at 2:27 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:

> On 12/14/2013 05:00 PM, Tom Lane wrote:
> > This consideration also makes me question whether we should apply the
> > method for NUMERIC. Although in principle numeric addition/subtraction
> > is exact, such a sequence could leave us with a different dscale than
> > is returned by the existing code. I'm not sure if changing the number of
> > trailing zeroes is a big enough behavior change to draw complaints.
>
> If we're going to disqualify NUMERIC too, we might as well bounce the
> feature. Without a fast FLOAT or NUMERIC, you've lost most of the
> target audience.
>
> I think even the FLOAT case deserves some consideration. What's the
> worst-case drift? In general, folks who do aggregate operations on
> FLOATs aren't expecting an exact answer, or one which is consistent
> beyond a certain number of significant digits.
>
> And Dave is right: how many bug reports would we get about "NUMERIC is
> fast, but FLOAT is slow"?
>
>
From what I can tell adding an inverse transition function to support AVG
for numeric does not affect the number of trailing zeros in the results, so
I've attached a patch which now has inverse transition functions to support
numeric types in AVG and all of the STDDEV* aggregates.

The function numeric_avg_accum_inv is the inverse transition function for
AVG. In the attached patch I've set this to be the inverse transition
function for SUM too. I know it was mentioned that having extra trailing
zeros here is a change of results and could be unwanted, but I've left it
in for now and I've included a failing regression test to demonstrate
exactly what has changed in the hope that it may seed a discussion on what
the best solution is.

Here's a quick example of what I'm talking about:

With this query I'll include a call to MAX to force the executor to not use
inverse transitions.
SELECT SUM(n::numeric) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND
UNBOUNDED FOLLOWING),
MAX(n::numeric) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND UNBOUNDED
FOLLOWING)
FROM (VALUES(1,1.00000000000001),(2,2),(3,3)) v(i,n);
sum | max
------------------+-----
6.00000000000001 | 3
5 | 3
3 | 3
(3 rows)

Notice lack of trailing zeros for the sum results in rows 2 and 3.

Here an inverse transition will be performed... Notice the extra trailing
zeros on rows 2 and 3.
SELECT SUM(n::numeric) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND
UNBOUNDED FOLLOWING)
FROM (VALUES(1,1.00000000000001),(2,2),(3,3)) v(i,n);
sum
------------------
6.00000000000001
5.00000000000000
3.00000000000000
(3 rows)

My ideas so far on what to do about this:

1. Don't allow inverse transition for SUM with numeric, but
since numeric_avg_accum_inv is already written for AVG numeric support we
could include a note in the docs to tell users how to create a SUM
aggregate for numeric that supports inverse transitions.
2. Don't worry about the trailing zeros... After all SELECT AVG(n) FROM
(VALUES(2::numeric)) v(n); adds a whole bunch of trailing zeros. Only the
above 2 queries shows that this behaviour can be a bit weird.
3. Invent some way to remove trailing zeros, perhaps in numeric_out. Is
there a reason they are there? Note that this would affect numeric globally.

What I don't currently know is: Are there any rules about trailing zeros on
numeric? I see that AVG with a single numeric produces many trailing zeros
after the decimal point. Are these meant to be there or is it just a side
effect of dividing on numerics?

Please note that I'm not trying to push for any of the above points. I just
want to get the information I currently have out there as perhaps someone
can think of something better or show a good reason for or against any of
the 3 points.

Regards

David Rowley

--
> Josh Berkus
> PostgreSQL Experts Inc.
> http://pgexperts.com
>

On Fri, Dec 27, 2013 at 1:36 AM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> From what I can tell adding an inverse transition function to support AVG
> for numeric does not affect the number of trailing zeros in the results, so
> I've attached a patch which now has inverse transition functions to support
> numeric types in AVG and all of the STDDEV* aggregates.
>

here's a slightly updated patch in which I've fixed up an comment that had
become out-dated because of the patch. I also changed the wording in quite
a few of my comments and made some changes to the docs. The only other
change was an extra error check just in case window_gettupleslot was to
fail to get a tuple that should always be in the tuple store.

I'm now classing the patch is not WIP anymore. I think it's ready for the
commitfest.

Regards

David Rowley

On Thu, January 2, 2014 13:05, David Rowley wrote:
> here's a slightly updated patch
> [inverse_transition_functions_v1.8.patch.gz ]

patch applies, and compiles (although with new warnings).
But make check complains loudly: see attached.

warnings:

In file included from gram.y:13871:0:
scan.c: In function â:
scan.c:10167:23: warning: unused variable â [-Wunused-variable]
struct yyguts_t * yyg = (struct yyguts_t*)yyscanner; /* This var may be unused depending upon options. */
^
In file included from ../../../../src/include/utils/probes.h:6:0,
from ../../../../src/include/pg_trace.h:15,
from tuplesort.c:109:
tuplesort.c: In function â:
tuplesort.c:935:44: warning: comparison between pointer and integer [enabled by default]
TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
^
tuplesort.c:935:2: note: in expansion of macro â
TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);

I didn't yet use the patch you sent after this patch.

Thanks,

Erik Rijkers

2013/12/15 David Rowley <dgrowleyml(at)gmail(dot)com>:

> I've been working on speeding up aggregate functions when used in the
> context of a window's with non fixed frame heads.

> 1. Fully implement negative transition functions for SUM and AVG.

I would like to mention that this functionality is also extremely
useful to have for the incremental maintenance of materialized views
that use aggregation (which IMHO is one of the most useful kinds).

(Simply imagine a view of the form “SELECT a, agg_function(b) FROM
table GROUP BY a”, a lot of rows in the table, a lot of rows in each
group, and changes that both remove and add new rows.)

For this to work, two things are needed:

(1) A way to apply a value normally (already supported) and inversely
(i.e., this patch) to the current “internal state” of an aggregation.

(2) A way to store the “internal state” of an aggregation in the
materialized view’s “extent” (i.e., the physical rows that represent
the view’s contents, which may or may not be slightly different from
what you get when you do SELECT * FROM matview). As (AFAIK) that state
is stored as a normal value, the maintenance code could just take the
value, store it in the extent, and next time retrieve it again and
perform normal or inverse transitions. When selecting from the
matview, the state could be retrieved, and the final function applied
to it to yield the value to be returned.

To understand (2), assume that one wants to store an AVG() in a
materialized view; To be able to update the value incrementally, one
needs to actually store the SUM() and COUNT(), and perform the
division when selecting from the materialized view. Or it could
(initially) be decided to define AVG() as “not supporting fast
incremental maintenance,” and require the user (if he/she wants fast
incremental maintenance) to put SUM() and COUNT() in the materialized
view manually, and perform the division manually when wanting to
retrieve the average.

Nicolas

--
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?

On Thu, January 2, 2014 13:36, Erik Rijkers wrote:
> On Thu, January 2, 2014 13:05, David Rowley wrote:
>> here's a slightly updated patch
>> [inverse_transition_functions_v1.8.patch.gz ]
>
> patch applies, and compiles (although with new warnings).
> But make check complains loudly: see attached.
>
> warnings:

The TRACE_POSTGRESQL_SORT_DONE warnings were not from your patch; sorry about that. They occur on HEAD too (with a debug
compile).

tuplesort.c:935:44: warning: comparison between pointer and integer [enabled by default]
TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
^
tuplesort.c:935:2: note: in expansion of macro â
TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);

The 'make check' failure remains a problem

The output I sent earlier today was for this configure:

./configure --prefix=/var/data1/pg_stuff/pg_installations/pgsql.inverse --with-pgport=6594 \
--bindir=/var/data1/pg_stuff/pg_installations/pgsql.inverse/bin \
--libdir=/var/data1/pg_stuff/pg_installations/pgsql.inverse/lib \
--quiet --enable-depend --enable-cassert --enable-debug --with-perl \
--with-openssl --with-libxml --enable-dtrace

(and that's still repeatable)

Perhaps this helps:

with another configure:

./configure --prefix=/var/data1/pg_stuff/pg_installations/pgsql.inverse --with-pgport=6594
--bindir=/var/data1/pg_stuff/pg_installations/pgsql.inverse/bin.fast
--libdir=/var/data1/pg_stuff/pg_installations/pgsql.inverse/lib.fast --quiet --enable-depend --with-perl --with-openssl
--with-libxml

I get only this single 'make check' error:

*** /var/data1/pg_stuff/pg_sandbox/pgsql.inverse/src/test/regress/expected/window.out 2014-01-02 16:19:48.000000000 +0100
--- /var/data1/pg_stuff/pg_sandbox/pgsql.inverse/src/test/regress/results/window.out 2014-01-02 16:21:43.000000000 +0100
***************
*** 1188,1195 ****
sum
------
6.01
! 5
! 3
(3 rows)

SELECT i,COUNT(v) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
--- 1188,1195 ----
sum
------
6.01
! 5.00
! 3.00
(3 rows)

SELECT i,COUNT(v) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)

======================================================================

Centos 5.7
gcc 4.8.2

Thanks; and Happy New Year

Erik Rijkers

"Erik Rijkers" <er(at)xs4all(dot)nl> writes:
> The TRACE_POSTGRESQL_SORT_DONE warnings were not from your patch; sorry about that. They occur on HEAD too (with a debug
> compile).

> tuplesort.c:935:44: warning: comparison between pointer and integer [enabled by default]
> TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);
> ^
> tuplesort.c:935:2: note: in expansion of macro
> TRACE_POSTGRESQL_SORT_DONE(state->tapeset != NULL, spaceUsed);

FWIW, I don't see any such warnings on either of the machines I have that
will accept --enable-dtrace. state->tapeset is a pointer, so these
warnings look a tad bogus.

regards, tom lane

On Fri, Jan 3, 2014 at 5:33 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:

> *** /var/data1/pg_stuff/pg_sandbox/pgsql.inverse/src/
> test/regress/expected/window.out 2014-01-02 16:19:48.000000000 +0100
> ---
> /var/data1/pg_stuff/pg_sandbox/pgsql.inverse/src/test/regress/results/window.out
> 2014-01-02 16:21:43.000000000 +0100
> ***************
> *** 1188,1195 ****
> sum
> ------
> 6.01
> ! 5
> ! 3
> (3 rows)
>
> SELECT i,COUNT(v) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND
> UNBOUNDED FOLLOWING)
> --- 1188,1195 ----
> sum
> ------
> 6.01
> ! 5.00
> ! 3.00
> (3 rows)
>
>
I've left those failures in for now in the hope to generate some discussion
on if we can inverse transition for sum(numeric). Please see my email
before the previous one for details. To fix it pg_aggregate.h just needs to
be changed to remove the inverse transition for sum(numeric).

On Thu, January 2, 2014 17:33, Erik Rijkers wrote:
> On Thu, January 2, 2014 13:36, Erik Rijkers wrote:
>> On Thu, January 2, 2014 13:05, David Rowley wrote:
>>> here's a slightly updated patch
>>> [inverse_transition_functions_v1.8.patch.gz ]
>>
>> patch applies, and compiles (although with new warnings).
>> But make check complains loudly

To figure out where this 'make check' failed, I lifted a few statements from the offending sql:
src/test/regress/sql/window.sql (see snafu.sh below).

That reliably crashes the server. It is caused by a SUM, but only when configured like this (i.e. *not* configured for
speed) :

$ pg_config --configure
'--prefix=/home/aardvark/pg_stuff/pg_installations/pgsql.inverse'
'--bindir=/home/aardvark/pg_stuff/pg_installations/pgsql.inverse/bin'
'--libdir=/home/aardvark/pg_stuff/pg_installations/pgsql.inverse/lib' '--with-pgport=6554' '--enable-depend'
'--enable-cassert' '--enable-debug' '--with-openssl' '--with-perl' '--with-libxml' '--with-libxslt' '--with-ossp-uuid'
'--with-zlib'

$ cat snafu.sh
#!/bin/sh

echo "
--
-- WINDOW FUNCTIONS
--

drop TABLE if exists empsalary ;

-- CREATE TEMPORARY TABLE empsalary (
CREATE TABLE empsalary (
depname varchar,
empno bigint,
salary int,
enroll_date date
);

INSERT INTO empsalary VALUES
('develop', 10, 5200, '2007-08-01'),
('sales', 1, 5000, '2006-10-01'),
('personnel', 5, 3500, '2007-12-10'),
('sales', 4, 4800, '2007-08-08'),
('personnel', 2, 3900, '2006-12-23'),
('develop', 7, 4200, '2008-01-01'),
('develop', 9, 4500, '2008-01-01'),
('sales', 3, 4800, '2007-08-01'),
('develop', 8, 6000, '2006-10-01'),
('develop', 11, 5200, '2007-08-15');

-- SELECT depname, empno, salary, sum(salary) OVER (PARTITION BY depname) FROM empsalary ORDER BY depname, salary;

" | psql

echo "select * from empsalary;" | psql

echo "
SELECT depname, empno, salary, sum(salary) OVER (PARTITION BY depname) FROM empsalary ORDER BY depname, salary;
" | psql

$ ./snafu.sh
Timing is on.
DROP TABLE
Time: 1.093 ms
CREATE TABLE
Time: 80.161 ms
INSERT 0 10
Time: 11.964 ms
Timing is on.
depname | empno | salary | enroll_date
-----------+-------+--------+-------------
develop | 10 | 5200 | 2007-08-01
sales | 1 | 5000 | 2006-10-01
personnel | 5 | 3500 | 2007-12-10
sales | 4 | 4800 | 2007-08-08
personnel | 2 | 3900 | 2006-12-23
develop | 7 | 4200 | 2008-01-01
develop | 9 | 4500 | 2008-01-01
sales | 3 | 4800 | 2007-08-01
develop | 8 | 6000 | 2006-10-01
develop | 11 | 5200 | 2007-08-15
(10 rows)

Time: 1.854 ms
Timing is on.
connection to server was lost

So, to repeat, this runs fine on a server compiled for speed.

I haven't looked any further (whether perhaps more statements are faulty)

On Fri, January 3, 2014 00:09, Erik Rijkers wrote:

> connection to server was lost
>
> So, to repeat, this runs fine on a server compiled for speed.
>

I forgot to append the log messages:

2014-01-03 00:19:17.073 CET 14054 LOG: database system is ready to accept connections
TRAP: FailedAssertion("!(!((bool) ((invtransfn_oid) != ((Oid) 0))))", File: "parse_agg.c", Line: 1255)
2014-01-03 00:19:29.605 CET 14054 LOG: server process (PID 14143) was terminated by signal 6: Aborted
2014-01-03 00:19:29.605 CET 14054 DETAIL: Failed process was running: SELECT depname, empno, salary, sum(salary) OVER
(PARTITION BY depname) FROM empsalary ORDER BY depname, salary;
2014-01-03 00:19:29.605 CET 14054 LOG: terminating any other active server processes
2014-01-03 00:19:29.607 CET 14054 LOG: all server processes terminated; reinitializing
etc. etc.

On Fri, Jan 3, 2014 at 12:23 PM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:

> On Fri, January 3, 2014 00:09, Erik Rijkers wrote:
>
>
> > connection to server was lost
> >
> > So, to repeat, this runs fine on a server compiled for speed.
> >
>
> I forgot to append the log messages:
>
> 2014-01-03 00:19:17.073 CET 14054 LOG: database system is ready to accept
> connections
> TRAP: FailedAssertion("!(!((bool) ((invtransfn_oid) != ((Oid) 0))))",
> File: "parse_agg.c", Line: 1255)
> 2014-01-03 00:19:29.605 CET 14054 LOG: server process (PID 14143) was
> terminated by signal 6: Aborted
> 2014-01-03 00:19:29.605 CET 14054 DETAIL: Failed process was running:
> SELECT depname, empno, salary, sum(salary) OVER
> (PARTITION BY depname) FROM empsalary ORDER BY depname, salary;
> 2014-01-03 00:19:29.605 CET 14054 LOG: terminating any other active
> server processes
> 2014-01-03 00:19:29.607 CET 14054 LOG: all server processes terminated;
> reinitializing
> etc. etc.
>
>
>
hmm, yeah, compiling and testing a build with assets enabled... That's a
good idea!
I probably should have tried that :)
I've attached another patch which should fix this problem.

The single failing SUM(numeric) regression test is still in there and it is
a known failure to do the extra trailing zeros that it can now produce that
would not be present in an unpatched version. It's there purely in the hope
to generate some discussion about it to find out if we can use inverse
transitions for sum(numeric) or not.

Regards

David Rowley

On 15 December 2013 01:57, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> I think even the FLOAT case deserves some consideration. What's the
>> worst-case drift?
>
> Complete loss of all significant digits.
>
> The case I was considering earlier of single-row windows could be made
> safe (I think) if we apply the negative transition function first, before
> incorporating the new row(s). Then for example if you've got float8 1e20
> followed by 1, you compute (1e20 - 1e20) + 1 and get the right answer.
> It's not so good with two-row windows though:
>
> Table correct sum of negative-transition
> this + next value result
> 1e20 1e20 1e20 + 1 = 1e20
> 1 1 1e20 - 1e20 + 0 = 0
> 0
>
>> In general, folks who do aggregate operations on
>> FLOATs aren't expecting an exact answer, or one which is consistent
>> beyond a certain number of significant digits.
>
> Au contraire. People who know what they're doing expect the results
> to be what an IEEE float arithmetic unit would produce for the given
> calculation. They know how the roundoff error ought to behave, and they
> will not thank us for doing a calculation that's not the one specified.
> I will grant you that there are plenty of clueless people out there
> who *don't* know this, but they shouldn't be using float arithmetic
> anyway.
>
>> And Dave is right: how many bug reports would we get about "NUMERIC is
>> fast, but FLOAT is slow"?
>
> I've said this before, but: we can make it arbitrarily fast if we don't
> have to get the right answer. I'd rather get "it's slow" complaints
> than "this is the wrong answer" complaints.
>

Hi,

Reading over this, I realised that there is a problem with NaN
handling --- once the state becomes NaN, it can never recover. So the
results using the inverse transition function don't match HEAD in
cases like this:

create table t(a int, b numeric);
insert into t values(1,1),(2,2),(3,'NaN'),(4,3),(5,4);
select a, b,
sum(b) over(order by a rows between 1 preceding and current row)
from t;

which in HEAD produces:

a | b | sum
---+-----+-----
1 | 1 | 1
2 | 2 | 3
3 | NaN | NaN
4 | 3 | NaN
5 | 4 | 7
(5 rows)

but with this patch produces:

a | b | sum
---+-----+-----
1 | 1 | 1
2 | 2 | 3
3 | NaN | NaN
4 | 3 | NaN
5 | 4 | NaN
(5 rows)

Regards,
Dean

Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com> writes:
> Reading over this, I realised that there is a problem with NaN
> handling --- once the state becomes NaN, it can never recover. So the
> results using the inverse transition function don't match HEAD in
> cases like this:

Ouch! That takes out numeric, float4, and float8 in one fell swoop.

Given the relative infrequency of NaNs in most data, it seems like
it might still be possible to get a speedup if we could use inverse
transitions until we hit a NaN, then do it the hard way until the
NaN is outside the window, then go back to inverse transitions.
I'm not sure though if this is at all practical from an implementation
standpoint. We certainly don't want the core code knowing about
anything as datatype-specific as a NaN, but maybe the inverse transition
function could have an API that allows reporting "I can't do it here,
fall back to the hard way".

regards, tom lane

On Jan9, 2014, at 17:15 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com> writes:
>> Reading over this, I realised that there is a problem with NaN
>> handling --- once the state becomes NaN, it can never recover. So the
>> results using the inverse transition function don't match HEAD in
>> cases like this:
>
> Ouch! That takes out numeric, float4, and float8 in one fell swoop.

For numeric, it seems that this could be overcome by having the state
be a pair (s numeric, n numeric). s would track the sum of non-NaNs
summands and n would track the number of NaN summands. The final
function would return NaN if n > 0 and s otherwise. The pair could
be represented as a value of type numeric[] to avoid having to invent
a new type for this.

For float 4 and float8, wasn't the consensus that the potential
lossy-ness of addition makes this impossible anyway, even without the
NaN issue? But...

> Given the relative infrequency of NaNs in most data, it seems like
> it might still be possible to get a speedup if we could use inverse
> transitions until we hit a NaN, then do it the hard way until the
> NaN is outside the window, then go back to inverse transitions.
> I'm not sure though if this is at all practical from an implementation
> standpoint. We certainly don't want the core code knowing about
> anything as datatype-specific as a NaN, but maybe the inverse transition
> function could have an API that allows reporting "I can't do it here,
> fall back to the hard way".

that sounds like it might be possible to make things work for float4
and float8 afterall, if we can determine whether a particular addition
was lossy or not.

best regards,
Florian Pflug

Florian Pflug <fgp(at)phlo(dot)org> writes:
> For float 4 and float8, wasn't the consensus that the potential
> lossy-ness of addition makes this impossible anyway, even without the
> NaN issue? But...

Well, that was my opinion, I'm not sure if it was consensus ;-).
But NaN is an orthogonal problem I think. I'm not sure whether it
has analogues in other data types.

regards, tom lane

On Jan9, 2014, at 18:09 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Florian Pflug <fgp(at)phlo(dot)org> writes:
>> For float 4 and float8, wasn't the consensus that the potential
>> lossy-ness of addition makes this impossible anyway, even without the
>> NaN issue? But...
>
> Well, that was my opinion, I'm not sure if it was consensus ;-).

I'd say your example showing how it could produce completely bogus
results was pretty convincing...

> But NaN is an orthogonal problem I think. I'm not sure whether it
> has analogues in other data types.

Transfer functions which are partially invertible are not that
uncommon, I'd say. Browsing through 9.3's list of aggregate functions,
the following come to mind

max()
Values smaller than the maximum can be removed, removing the current
maximum requires a rescan. By remembering the N largest values,
the number of required rescans can be reduced, but never fully
eliminated. Same works for min().

bool_or()
FALSE can be removed, removing TRUE requires a rescan. Could be made
fully invertible by counting the number of TRUE and FALSE values,
similar to my suggestion for how to handle NaN for sum(numeric).
Same works for bool_and().

bit_or()
Like boo_or(), 0 can be removed, everything else requires a rescan.
Same works for bit_and()

Plus, any aggregate with a strict transfer function would be in
exactly the same situation regarding NULL as sum(numeric) is regarding
NaN. AFAIK we don't have any such aggregate in core, though.

best regards,
Florian Pflug

On Fri, Jan 10, 2014 at 4:09 AM, Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com>wrote:

> Hi,
>
> Reading over this, I realised that there is a problem with NaN
> handling --- once the state becomes NaN, it can never recover. So the
> results using the inverse transition function don't match HEAD in
> cases like this:
>
> create table t(a int, b numeric);
> insert into t values(1,1),(2,2),(3,'NaN'),(4,3),(5,4);
> select a, b,
> sum(b) over(order by a rows between 1 preceding and current row)
> from t;
>
> which in HEAD produces:
>
> a | b | sum
> ---+-----+-----
> 1 | 1 | 1
> 2 | 2 | 3
> 3 | NaN | NaN
> 4 | 3 | NaN
> 5 | 4 | 7
> (5 rows)
>
> but with this patch produces:
>
> a | b | sum
> ---+-----+-----
> 1 | 1 | 1
> 2 | 2 | 3
> 3 | NaN | NaN
> 4 | 3 | NaN
> 5 | 4 | NaN
> (5 rows)
>
>
Nice catch! Thanks for having a look at the patch.

Ok, so I thought about this and I don't think it's too big a problem at to
fix it all. I think it can be handled very similar to how I'm taking care
of NULL values in window frame. For these, I simply keep a count of them in
an int64 and when the last one leaves the aggregate context things can
continue as normal.

Lucky for us that all numeric aggregation (and now inverse aggregation)
goes through 2 functions. do_numeric_accum() and the new inverse version of
it do_numeric_discard(), both these functions operate on a NumericAggState
which in the attached I've changed the isNaN bool field to a NaNCount int64
field. I'm just doing NaNCount++ when we get a NaN value in
do_numeric_accum and NaNCount-- in do_numeric_discard(), in the final
functions I'm just checking if NaNCount > 0.

Though this implementation does fix the reported problem unfortunately it
may have an undesired performance impact for numeric aggregate functions
when not uses in the context of a window.. Let me explain what I mean:

Previously there was some code in do_numeric_accum() which did:

if (state->isNaN || NUMERIC_IS_NAN(newval))
{
state->isNaN = true;
return;
}

Which meant that it didn't bother adding new perfectly valid numerics to
the aggregate totals when there was an NaN encountered previously. I had to
change this to continue on regardless as we still need to keep the totals
just in case all the NaN values are removed and the totals are required
once again. This means that the non-window version of SUM(numeric) and
AVG(numeric) and and the stddev aggregates for numeric pay a price and have
to keep on totaling after encountering NaN values. :(

If there was a way to know if the function was being called in a window
context or a normal aggregate context then we probably almost completely
restore that possible performance regression just by skipping the totaling
when not in windows context. I really don't know how common NaN values are
in the real world to know if this matters too much. I'd hazard a guess that
more people would benefit from inverse transitions on numeric types more,
but I have nothing to back that up.

I've attached version 2 of the patch which fixes the NaN problem and adds a
regression test to cover it.

Thanks again for testing this and finding the problem.

Regards

David Rowley

> Regards,
> Dean
>

On Fri, Jan 10, 2014 at 5:15 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com> writes:
> > Reading over this, I realised that there is a problem with NaN
> > handling --- once the state becomes NaN, it can never recover. So the
> > results using the inverse transition function don't match HEAD in
> > cases like this:
>
> Ouch! That takes out numeric, float4, and float8 in one fell swoop.
>
> Given the relative infrequency of NaNs in most data, it seems like
> it might still be possible to get a speedup if we could use inverse
> transitions until we hit a NaN, then do it the hard way until the
> NaN is outside the window, then go back to inverse transitions.
> I'm not sure though if this is at all practical from an implementation
> standpoint. We certainly don't want the core code knowing about
> anything as datatype-specific as a NaN, but maybe the inverse transition
> function could have an API that allows reporting "I can't do it here,
> fall back to the hard way".
>
>
I had thought about that API, not for numeric as I think I've managed to
find another solution, it was for MAX and MIN.

I posted an idea about it here:
http://www.postgresql.org/message-id/CAApHDvqu+yGW0vbPBb+yxHrPG5VcY_kiFYi8xmxFo8KYOczP3A@mail.gmail.com
but it didn't generate much interest at the time and I didn't have any
ideas on how the inverse aggregate functions would communicate this
inability to remove the value to the caller. Perhaps it would be an idea
still, but I had put it to the back of my mind in favour of tuplestore
indexes that could be created on the fly based on the row position within
the frame and the aggregate's sort operator on the aggregate value.
This would mean that MAX and MIN values could be found quickly all the time
rather than just when the value being removed happened not to affect the
current maximum or minimum. It's not something I have planned for this
patch though and I'd have lots of questions around memory allocation before
I'd want to start any work on it.

Regards

David Rowley

> regards, tom lane
>

>
>
> bool_or()
> FALSE can be removed, removing TRUE requires a rescan. Could be made
> fully invertible by counting the number of TRUE and FALSE values,
> similar to my suggestion for how to handle NaN for sum(numeric).
> Same works for bool_and().
>
> bit_or()
> Like boo_or(), 0 can be removed, everything else requires a rescan.
> Same works for bit_and()
>
>
Interesting, I'd not thought of any way to optimise these ones, but I had
originally thought about allowing the inverse transition functions to
report if they could perform the inverse transition based on the value they
received and if they reported failure, then perform the rescan.
I just don't quite know yet the base way for the inverse transition
function to communicate this to the caller yet. If you have any ideas on
the best way to do this then I'd really like to hear them.

Regards

David Rowley

On 10 January 2014 08:12, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> On Fri, Jan 10, 2014 at 4:09 AM, Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com>
> wrote:
>>
>> Hi,
>>
>> Reading over this, I realised that there is a problem with NaN
>> handling --- once the state becomes NaN, it can never recover. So the
>> results using the inverse transition function don't match HEAD in
>> cases like this:
>>
>> create table t(a int, b numeric);
>> insert into t values(1,1),(2,2),(3,'NaN'),(4,3),(5,4);
>> select a, b,
>> sum(b) over(order by a rows between 1 preceding and current row)
>> from t;
>>
>> which in HEAD produces:
>>
>> a | b | sum
>> ---+-----+-----
>> 1 | 1 | 1
>> 2 | 2 | 3
>> 3 | NaN | NaN
>> 4 | 3 | NaN
>> 5 | 4 | 7
>> (5 rows)
>>
>> but with this patch produces:
>>
>> a | b | sum
>> ---+-----+-----
>> 1 | 1 | 1
>> 2 | 2 | 3
>> 3 | NaN | NaN
>> 4 | 3 | NaN
>> 5 | 4 | NaN
>> (5 rows)
>>
>
> Nice catch! Thanks for having a look at the patch.
>
> Ok, so I thought about this and I don't think it's too big a problem at to
> fix it all. I think it can be handled very similar to how I'm taking care of
> NULL values in window frame. For these, I simply keep a count of them in an
> int64 and when the last one leaves the aggregate context things can continue
> as normal.
>
> Lucky for us that all numeric aggregation (and now inverse aggregation) goes
> through 2 functions. do_numeric_accum() and the new inverse version of it
> do_numeric_discard(), both these functions operate on a NumericAggState
> which in the attached I've changed the isNaN bool field to a NaNCount int64
> field. I'm just doing NaNCount++ when we get a NaN value in do_numeric_accum
> and NaNCount-- in do_numeric_discard(), in the final functions I'm just
> checking if NaNCount > 0.
>

Cool, that sounds like a neat fix.

> Though this implementation does fix the reported problem unfortunately it
> may have an undesired performance impact for numeric aggregate functions
> when not uses in the context of a window.. Let me explain what I mean:
>
> Previously there was some code in do_numeric_accum() which did:
>
> if (state->isNaN || NUMERIC_IS_NAN(newval))
> {
> state->isNaN = true;
> return;
> }
>
> Which meant that it didn't bother adding new perfectly valid numerics to the
> aggregate totals when there was an NaN encountered previously. I had to
> change this to continue on regardless as we still need to keep the totals
> just in case all the NaN values are removed and the totals are required once
> again. This means that the non-window version of SUM(numeric) and
> AVG(numeric) and and the stddev aggregates for numeric pay a price and have
> to keep on totaling after encountering NaN values. :(
>

I suspect that NaNs almost never occur in practice, so the fact that
it might now take longer to tell you that the sum is NaN doesn't worry
me. More important is that it always gives the right answer.

Note, if anyone ever did this for floats, +/- Infinity would also need
to be handled, so you'd have to maintain 3 counts and deal with logic
like Infinity - Infinity = NaN.

Regards,
Dean

On Jan10, 2014, at 09:34 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> I just don't quite know yet the base way for the inverse transition function to communicate this to the caller yet. If you have any ideas on the best way to do this then I'd really like to hear them.

Could they maybe just return NULL as the new state? It would mean that
aggregates that do want to provide an inverse transition function couldn't
use NULL as a valid aggregate state, but do we need to support that?

Looking at the code it seems that for quite a few existing aggregates,
the state remains NULL until the first non-NULL input is processed. But
that doesn't hurt much - those aggregates can remain as they are until
someone wants to add an inverse transfer function. Once that happens,
there's a choice between living with needless rescans on trailing NULL
inputs or changing the state type.

This solution isn't particularly pretty, but I don't currently see a good
alternative that allows implementing inverse transfer functions is something
other than C and avoid needless overhead for those which are written in C.

best regards,
Florian Pflug

Florian Pflug <fgp(at)phlo(dot)org> writes:
> On Jan10, 2014, at 09:34 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>> I just don't quite know yet the base way for the inverse transition function to communicate this to the caller yet. If you have any ideas on the best way to do this then I'd really like to hear them.

> Could they maybe just return NULL as the new state? It would mean that
> aggregates that do want to provide an inverse transition function couldn't
> use NULL as a valid aggregate state, but do we need to support that?

Yeah, I was going to suggest the same. Seems like it wouldn't be that
difficult to come up with some alternative representation for "everything
seen so far was NULL", if you needed to.

> Looking at the code it seems that for quite a few existing aggregates,
> the state remains NULL until the first non-NULL input is processed. But
> that doesn't hurt much - those aggregates can remain as they are until
> someone wants to add an inverse transfer function. Once that happens,
> there's a choice between living with needless rescans on trailing NULL
> inputs or changing the state type.

Also, it might be reasonable for both the regular and the inverse
transition functions to be strict. If a null entering the window
does not matter, then a null exiting the window doesn't either, no?

regards, tom lane

On Jan10, 2014, at 15:49 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Florian Pflug <fgp(at)phlo(dot)org> writes:
>> Looking at the code it seems that for quite a few existing aggregates,
>> the state remains NULL until the first non-NULL input is processed. But
>> that doesn't hurt much - those aggregates can remain as they are until
>> someone wants to add an inverse transfer function. Once that happens,
>> there's a choice between living with needless rescans on trailing NULL
>> inputs or changing the state type.
>
> Also, it might be reasonable for both the regular and the inverse
> transition functions to be strict. If a null entering the window
> does not matter, then a null exiting the window doesn't either, no?

That's not true, I think, unless we're special-casing strict transition
functions somewhere. AFAICS, an aggregate with a strict transition function
will produce the state NULL whenever any of the inputs was NULL, i.e. we won't
ever transition out of the NULL state once we got there. The inverse
transition function, however, would *have* to be able to transition away
from the NULL state, which requires it to be non-strict. Otherwise, how would
the state aver become non-NULL after the last NULL input leaves the window?

best regards,
Florian Pflug

Florian Pflug <fgp(at)phlo(dot)org> writes:
> On Jan10, 2014, at 15:49 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Also, it might be reasonable for both the regular and the inverse
>> transition functions to be strict. If a null entering the window
>> does not matter, then a null exiting the window doesn't either, no?

> That's not true, I think, unless we're special-casing strict transition
> functions somewhere. AFAICS, an aggregate with a strict transition function
> will produce the state NULL whenever any of the inputs was NULL, i.e. we won't
> ever transition out of the NULL state once we got there.

Nope, not the case; read xaggr.sgml and/or the CREATE AGGREGATE reference
page. An aggregate with a strict transition function essentially just
ignores null input rows. I suspect the inverse transition function could
just be made strict with a similar special-case rule (viz, keep the old
transition value when deleting a null input from the window); but maybe
I'm missing something and it has to work harder than that anyway.

regards, tom lane

Florian Pflug <fgp(at)phlo(dot)org> wrote:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Florian Pflug <fgp(at)phlo(dot)org> writes:
>>> For float 4 and float8, wasn't the consensus that the potential
>>> lossy-ness of addition makes this impossible anyway, even
>>> without the NaN issue? But...
>>
>> Well, that was my opinion, I'm not sure if it was consensus ;-).
>
> I'd say your example showing how it could produce completely
> bogus results was pretty convincing...

Aggregates on approximate (floating-point) numbers are not nearly
as consistent as many people probably assume.  Picture for a minute
a table where a column contains positive floating point numbers
happen to be located in the heap in increasing order, perhaps as
the result of a CLUSTER on an index on the column.  SELECT
sum(colname) FROM tablename; would tend to give the most accurate
answer possible when a sequence scan was run -- unless there
happened to be a seqscan already half-way through the heap.  Then
the result would be different.  So the exact same query against the
exact same data, with no intervening modifications or maintenance
activity could give one answer most of the time, and give various
other answers depending on concurrent SELECT queries.

Given that this is already the case with aggregates on floating
point approximate numbers, why should we rule out an optimization
which only makes rounding errors more likely to be visible?  The
real issue here is that if you are using an approximate data type
and expecting exact answers, you will have problems.

That's not to say that approximations are useless.  If you
represent the circumference of the earth with a double precision
number you're dealing with an expected rounding error of about a
foot.  That's close enough for many purposes.  The mistake is
assuming that it will be exact or that rounding errors cannot
accumulate.  In situations where SQL does not promise particular
ordering of operations, it should not be assumed; so any
expectations of a specific or repeatable result from a sum or
average of approximate numbers is misplaced.

>> But NaN is an orthogonal problem I think.

Agreed.

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

Kevin Grittner <kgrittn(at)ymail(dot)com> writes:
> Aggregates on approximate (floating-point) numbers are not nearly
> as consistent as many people probably assume. Picture for a minute
> a table where a column contains positive floating point numbers
> happen to be located in the heap in increasing order, perhaps as
> the result of a CLUSTER on an index on the column. SELECT
> sum(colname) FROM tablename; would tend to give the most accurate
> answer possible when a sequence scan was run -- unless there
> happened to be a seqscan already half-way through the heap. Then
> the result would be different.

I don't think that argument holds any water. In the first place, somebody
could turn off synchronize_seqscans if they needed to have the calculation
done the same way every time (and I recall questions from users who ended
up doing exactly that, shortly after we introduced synchronize_seqscans).
In the second place, for most use-cases it'd be pretty foolish to rely on
physical heap order, so somebody who was really trying to sum float8s
accurately would likely do

select sum(x order by x) from ...

This is a well-defined, numerically stable calculation, and I don't want
to see us put in non-defeatable optimizations that break it.

> The real issue here is that if you are using an approximate data type
> and expecting exact answers, you will have problems.

That's a canard. People who know what they're doing (admittedly a
minority) do not expect exact answers, but they do expect to be able to
specify how to do the calculation in a way that minimizes roundoff errors.
The inverse-transition-function approach breaks that, and it does so at a
level where the user can't work around it, short of building his own
aggregates.

regards, tom lane

I wrote:
> Kevin Grittner <kgrittn(at)ymail(dot)com> writes:
>> The real issue here is that if you are using an approximate data type
>> and expecting exact answers, you will have problems.

> That's a canard. People who know what they're doing (admittedly a
> minority) do not expect exact answers, but they do expect to be able to
> specify how to do the calculation in a way that minimizes roundoff errors.
> The inverse-transition-function approach breaks that, and it does so at a
> level where the user can't work around it, short of building his own
> aggregates.

Although, having said that ... maybe "build your own aggregate" would
be a reasonable suggestion for people who need this? I grant that
it's going to be a minority requirement, maybe even a small minority
requirement. People who have the chops to get this sort of thing right
can probably manage a custom aggregate definition.

The constraint this would pose on the float4 and float8 implementations
is that it be possible to use their transition and final functions in
a custom aggregate declaration while leaving off the inverse function;
or, if that combination doesn't work for some reason, we have to continue
to provide the previous transition/final functions for use in user
aggregates.

Suitable documentation would be needed too, of course.

regards, tom lane

On Jan10, 2014, at 18:14 , Kevin Grittner <kgrittn(at)ymail(dot)com> wrote:
> Given that this is already the case with aggregates on floating
> point approximate numbers, why should we rule out an optimization
> which only makes rounding errors more likely to be visible? The
> real issue here is that if you are using an approximate data type
> and expecting exact answers, you will have problems.

Because without the optimization, only the values which you
*actually* process for a given result determine whether you lose
precision or not. With the optimization, OTOH, values which have
*nothing* to do with the result in question can nevertheless
make it completely bogus.

SUM() is a good example. As long as all your values are positive,
the amount of precision you lose is bound by the number of input
values. If I sum over 10 values, the worst that can happen is that
the first values is large enough to prevent the other 9 values from
influencing the result. That limits the relative error to something
like 9*epsilon, where epsilon is the relative precision of the
floating point type, i.e. 1e-15 or so for double. In other words,
as long as your frames are less than 10e13 rows long, the relative
error will stay below 1%.

But with the optimization, that is no longer true. If you sum
from, say, CURRENT ROW to UNBOUNDED FOLLOWING, the relative error
of the result in one row now depends on the magnitude of values
*preceding* that row, even though that value isn't in the frame.
And since we now internally subtract, not only add, the relative
error is no longer bound by the number of rows in the frame.

Here's the corresponding SELECT (which is basically the same
as Tom's example upthread):
select
n,
x::float,
sum(x::float) over (
order by n rows between current row and unbounded following
)
from (values
(1, 1e20),
(2, 1),
(3, 2)
) as t(n, x)
order by n;

Currently that returns
n | x | sum
---+-------+-------
1 | 1e+20 | 1e+20
2 | 1 | 3
3 | 2 | 2

but with an inverse transfer function, it may very well return
n | x | sum
---+-------+-------
1 | 1e+20 | 1e+20
2 | 1 | 0
3 | 2 | -1

> That's not to say that approximations are useless. If you
> represent the circumference of the earth with a double precision
> number you're dealing with an expected rounding error of about a
> foot. That's close enough for many purposes. The mistake is
> assuming that it will be exact or that rounding errors cannot
> accumulate. In situations where SQL does not promise particular
> ordering of operations, it should not be assumed; so any
> expectations of a specific or repeatable result from a sum or
> average of approximate numbers is misplaced.

But this isn't about ordering, it's replacing one computation
with a completely different one that just happens to be equivalent
*algebraically*.

To me, the proposed optimization for float is akin to C compiler
which decided to evaluate
a + b + c + … z
as
-a + (2a - b) + (2b - c) + … + (2y - z) + 2z
Algebraically, these are the same, but it'd still be insane to
do that.

best regards,
Florian Pflug

On Jan10, 2014, at 19:08 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> I wrote:
>> Kevin Grittner <kgrittn(at)ymail(dot)com> writes:
>>> The real issue here is that if you are using an approximate data type
>>> and expecting exact answers, you will have problems.
>
>> That's a canard. People who know what they're doing (admittedly a
>> minority) do not expect exact answers, but they do expect to be able to
>> specify how to do the calculation in a way that minimizes roundoff errors.
>> The inverse-transition-function approach breaks that, and it does so at a
>> level where the user can't work around it, short of building his own
>> aggregates.
>
> Although, having said that ... maybe "build your own aggregate" would
> be a reasonable suggestion for people who need this? I grant that
> it's going to be a minority requirement, maybe even a small minority
> requirement. People who have the chops to get this sort of thing right
> can probably manage a custom aggregate definition.

So we'd put a footgun into the hands of people who don't know what they're
doing, to be fired for performance's sake, and leave it to the people
who know what they are doing to put the safety on?

best regards,
Florian Pflug

Florian Pflug <fgp(at)phlo(dot)org> writes:
> On Jan10, 2014, at 19:08 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Although, having said that ... maybe "build your own aggregate" would
>> be a reasonable suggestion for people who need this? I grant that
>> it's going to be a minority requirement, maybe even a small minority
>> requirement. People who have the chops to get this sort of thing right
>> can probably manage a custom aggregate definition.

> So we'd put a footgun into the hands of people who don't know what they're
> doing, to be fired for performance's sake, and leave it to the people
> who know what they are doing to put the safety on?

If I may put words in Kevin's mouth, I think his point is that having
float8 sum() at all is a foot-gun, and that's hard to deny. You need
to know how to use it safely.

A compromise compromise might be to provide these alternative "safer"
aggregates built-in. Or, depending on what color you like your bikeshed,
leave the standard aggregates alone and define "fast_sum" etc for the less
safe versions. In any case it'd be incumbent on us to document the
tradeoffs.

regards, tom lane

FYI, I'm using the verb "rewind" to talk about using the negative transition aggregation function to get a prior value.  I don't know if this is the right verb.

Conceptually, when aggregating over floating point numbers, there is some infinitely precise theoretical value, and the computation is approximating it.  Call the infinitely precise value 'r'.  Call the computed value 'c', which is the result of the aggregation function.  (For float4_agg and float8_agg, typeof(c) == float8).

The problem you have with rewinding an aggregate is that you don't know if you are getting the same value of c that you would have gotten from a
rescan.  But if you have a type that tracks a margin [min,max] where typeof(min) == typeof(max) is higher precision than typeof(c), then you can track:

min <= r <= max

By setting the rounding mode down, then up, when computing the next value of min and max, respectively.  (Extra flag bits or booleans could track whether you've encountered +inf, -inf, Nan, and any other oddball cases, with corresponding special logic that has been discussed already upthread.)  In many but not all cases:

min != max

but

(typeof(c))min == (typeof(c))max

Because the margin of error is small enough not to render different values when cast to the lower precision typeof(c).

You could rewind the aggregation whenever this second case holds, and only force a rescan when it does not.  This would render the same results for queries whether they were performed with rewinds or with rescans.  The results might differ from older versions of postgres, but only in that they might be more accurate, with less accumulated rounding errors, owing to the higher precision state transition variable.

For many modern platforms, typeof(min)
could be __float128 using libquadmath, or something similar to that.  If not available at compile time, it could be float64 instead.  Even then, you'd still know that rewinding was possible when min == max and not otherwise, which is useful for cases of aggregation over exact values.

I admit I've done a bit of handwaving on the computation of the margin and the handling of floating-point rounding issues, but I believe the implementation details are tractible.

mark

On Friday, January 10, 2014 10:10 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

On Jan10, 2014, at 18:14 , Kevin Grittner <kgrittn(at)ymail(dot)com> wrote:
> Given that this is already the case with aggregates on floating
> point approximate numbers, why should we rule out an optimization
> which only makes rounding errors more likely to be visible?  The
> real issue here is that if you are using an approximate data type
> and expecting exact answers, you will have problems.

Because without the optimization, only the values which you
*actually* process for a given result determine whether you lose
precision or not. With the optimization, OTOH, values which have
*nothing* to do with the result in question can nevertheless
make it completely bogus.

SUM() is a good example. As long as all your values are positive,
the amount of precision you lose is bound by the number of input
values. If I sum over 10 values, the worst that can happen is that
the first values is large enough to prevent the other 9 values from
influencing the result. That limits the relative error to something
like 9*epsilon, where epsilon is the relative precision of the
floating point type, i.e. 1e-15 or so for double. In other words,
as long as your frames are less than 10e13 rows long, the relative
error will stay below 1%.

But with the optimization, that is no longer true. If you sum
from, say, CURRENT ROW to UNBOUNDED FOLLOWING, the relative error
of the result in one row now depends on the magnitude of values
*preceding* that row, even though that value isn't in the frame.
And since we now internally subtract, not only add, the relative
error is no longer bound by the number of rows in the frame.

Here's the corresponding SELECT (which is basically the same
as Tom's example upthread):
select
  n,
  x::float,
  sum(x::float) over (
    order by n rows between current row and unbounded following
  )
  from (values
    (1, 1e20),
    (2, 1),
    (3, 2)
  ) as t(n, x)
  order by n;

Currently that returns
  n |  x  |  sum 
  ---+-------+-------
  1 | 1e+20 | 1e+20
  2 |    1 |    3
  3 |    2 |    2

but with an inverse transfer function, it may very well return
  n |  x  |  sum 
  ---+-------+-------
  1 | 1e+20 | 1e+20
  2 |    1 |    0
  3 |    2 |    -1

> That's not to say that approximations are
useless.  If you
> represent the circumference of the earth with a double precision
> number you're dealing with an expected rounding error of about a
> foot.  That's close enough for many purposes.  The mistake is
> assuming that it will be exact or that rounding errors cannot
> accumulate.  In situations where SQL does not promise particular
> ordering of operations, it should not be assumed; so any
> expectations of a specific or repeatable result from a sum or
> average of approximate numbers is misplaced.

But this isn't about ordering, it's replacing one computation
with a completely different one that just happens to be equivalent
*algebraically*.

To me, the proposed optimization
for float is akin to C compiler
which decided to evaluate
  a + b + c + … z
as
  -a + (2a - b) + (2b - c) + … + (2y - z) + 2z
Algebraically, these are the same, but it'd still be insane to
do that.

best regards,

Florian Pflug

On Sat, Jan 11, 2014 at 7:08 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Although, having said that ... maybe "build your own aggregate" would
> be a reasonable suggestion for people who need this? I grant that
> it's going to be a minority requirement, maybe even a small minority
> requirement. People who have the chops to get this sort of thing right
> can probably manage a custom aggregate definition.
>
>
I more or less wrote off the idea of inverse transition functions after
your example upthread. I had thought that perhaps if we could get inverse
transitions in there for SUM(numeric) then people who need more speed could
just cast their value to numeric then back to float or double precision
after aggregation takes place. I had to delay writing any documentation
around that as I'm still not sure if we can have sum(numeric) use an
inverse transition function due to the fact that it can introduce extra
zeros after the decimal point.

As the patch stands at the moment, I currently have a regression test which
currently fails due to these extra zeros after the decimal point:

-- This test currently fails due extra trailing 0 digits.
SELECT SUM(n::numeric) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND
UNBOUNDED FOLLOWING)
FROM (VALUES(1,1.01),(2,2),(3,3)) v(i,n);

Patched produces:
6.01
5.00
3.00
Unpatched produces:
6.01
5
3

With inverse transitions this query still produces correct results, it just
does not produces the numeric in the same format as it does without
performing inverse transitions. Personally I'd rather focus on trying to
get SUM(numeric) in there for 9.4 and maybe focus on floating point stuff
at a later date as casting to numeric can be the work around for users who
complain about the speed. Or if they really want they can create their own
aggregate, using an existing built in function as the inverse transition,
like float8_mi.

There's certain things that currently seem a big magical to me when it
comes to numeric, for example I've no idea why the following query produces
20 0's after the decimal point for 1 and only 16 for 2.

select n::numeric / 1 from generate_series(1,2) g(n);

To me it does not look very consistent at all and I'm really wondering if
there is some special reason why we bother including the useless zeros at
the end at all. I've written a patch which gets rid of them in numeric_out,
but I had not planned on posting it here in case it gets laughed off stage
due to some special reason we have for keeping those zeros that I don't
know about.

Can anyone explain to me why we have these unneeded zeros in numeric when
the precision is not supplied?

Regards

David Rowley

> The constraint this would pose on the float4 and float8 implementations
> is that it be possible to use their transition and final functions in
> a custom aggregate declaration while leaving off the inverse function;
> or, if that combination doesn't work for some reason, we have to continue
> to provide the previous transition/final functions for use in user
> aggregates.
>
> Suitable documentation would be needed too, of course.
>
> regards, tom lane
>

On 1/10/14, 1:07 PM, Tom Lane wrote:
> Florian Pflug<fgp(at)phlo(dot)org> writes:
>> >On Jan10, 2014, at 19:08 , Tom Lane<tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> >>Although, having said that ... maybe "build your own aggregate" would
>>> >>be a reasonable suggestion for people who need this? I grant that
>>> >>it's going to be a minority requirement, maybe even a small minority
>>> >>requirement. People who have the chops to get this sort of thing right
>>> >>can probably manage a custom aggregate definition.
>> >So we'd put a footgun into the hands of people who don't know what they're
>> >doing, to be fired for performance's sake, and leave it to the people
>> >who know what they are doing to put the safety on?
> If I may put words in Kevin's mouth, I think his point is that having
> float8 sum() at all is a foot-gun, and that's hard to deny. You need
> to know how to use it safely.

And IMHO if you've got something that's going to produce bad data if you do it wrong, I'd rather that the error be as large as possible so that you're more likely to discover it and fix it...
--
Jim C. Nasby, Data Architect jim(at)nasby(dot)net
512.569.9461 (cell) http://jim.nasby.net

On Jan10, 2014, at 17:46 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Florian Pflug <fgp(at)phlo(dot)org> writes:
>> On Jan10, 2014, at 15:49 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> Also, it might be reasonable for both the regular and the inverse
>>> transition functions to be strict. If a null entering the window
>>> does not matter, then a null exiting the window doesn't either, no?
>
>> That's not true, I think, unless we're special-casing strict transition
>> functions somewhere. AFAICS, an aggregate with a strict transition function
>> will produce the state NULL whenever any of the inputs was NULL, i.e. we won't
>> ever transition out of the NULL state once we got there.
>
> Nope, not the case; read xaggr.sgml and/or the CREATE AGGREGATE reference
> page. An aggregate with a strict transition function essentially just
> ignores null input rows.

I wasn't aware of that, sorry for the noise.

> I suspect the inverse transition function could
> just be made strict with a similar special-case rule (viz, keep the old
> transition value when deleting a null input from the window); but maybe
> I'm missing something and it has to work harder than that anyway.

This seems to hold at least if the state never becomes NULL, i.e. if there's
a non-NULL initiate state (S) and the transfer function never becomes NULL. If
the transfer function (I) and inverse transfer function (T) obey that
I(T(...T(T(S,a),b)...,z), a) = T(...T(S,b)...,z)
for a non-NULL a, then setting T(s,NULL) = I(s,NULL) = s makes the same
thing work for NULL and non-NULL values for a.

If, however, a strict state function T ever returns NULL, things break.
If T(S,a) is NULL in the above, the whole expression becomes NULL because
T is strict (we only special-case the *value* input, not the state input).
But T(...T(S,b)...,z) might very well be non-NULL. That's pretty much
the same situation, unsurprisingly, as with NaNs.

A variant of that problem arises also if the initial state is NULL.
We then wait for the first non-NULL value, and use that as the initial
state. When we later apply the inverse transition function, we might or
might not have to reset the state back to NULL, depending on whether there
are other non-NULL values in the frame or not. This case can be solved by
tracking the number of non-NULL rows in the current frame - whenever
that number if 0, the the output value is NULL, otherwise it's determined
by the state.

So in conclusion, things work for pairs of strict transfer and inverse
transfer functions AFAICS, as long as we do the non-null tracking and
complain should the transfer function ever return NULL.

best regards,
Florian Pflug

On Jan11, 2014, at 01:24 , Jim Nasby <jim(at)nasby(dot)net> wrote:
> On 1/10/14, 1:07 PM, Tom Lane wrote:
>> Florian Pflug<fgp(at)phlo(dot)org> writes:
>>> >On Jan10, 2014, at 19:08 , Tom Lane<tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>>> >>Although, having said that ... maybe "build your own aggregate" would
>>>> >>be a reasonable suggestion for people who need this? I grant that
>>>> >>it's going to be a minority requirement, maybe even a small minority
>>>> >>requirement. People who have the chops to get this sort of thing right
>>>> >>can probably manage a custom aggregate definition.
>>> >So we'd put a footgun into the hands of people who don't know what they're
>>> >doing, to be fired for performance's sake, and leave it to the people
>>> >who know what they are doing to put the safety on?
>> If I may put words in Kevin's mouth, I think his point is that having
>> float8 sum() at all is a foot-gun, and that's hard to deny. You need
>> to know how to use it safely.
>
> And IMHO if you've got something that's going to produce bad data if you do it
> wrong, I'd rather that the error be as large as possible so that you're more
> likely to discover it and fix it...

To that principle, I agree, I just don't think it applies here. An inverse
transition function greatly *increases* the chance of bogus results for
sum(float). It also breaks some rather natural assumptions that one might
make about sum(float)'s behaviour. For example, sums over single-element
frames current return the one row's value unchanged. That's no longer true
universally true with an inverse transition function. Even for an approximate
type, that's a bid too weird for my taste.

best regards,
Florian Pflug

On Fri, Jan 10, 2014 at 2:07 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Florian Pflug <fgp(at)phlo(dot)org> writes:
>> On Jan10, 2014, at 19:08 , Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> Although, having said that ... maybe "build your own aggregate" would
>>> be a reasonable suggestion for people who need this? I grant that
>>> it's going to be a minority requirement, maybe even a small minority
>>> requirement. People who have the chops to get this sort of thing right
>>> can probably manage a custom aggregate definition.
>
>> So we'd put a footgun into the hands of people who don't know what they're
>> doing, to be fired for performance's sake, and leave it to the people
>> who know what they are doing to put the safety on?
>
> If I may put words in Kevin's mouth, I think his point is that having
> float8 sum() at all is a foot-gun, and that's hard to deny. You need
> to know how to use it safely.

Yeah, but Florian's point is that not all foot-guns are created equal.
The fact that we're walking around with a loaded BB-gun in our hip
pocket is not a good reason to replace it with a howitzer.

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

On Jan10, 2014, at 22:27 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> As the patch stands at the moment, I currently have a regression test
> which currently fails due to these extra zeros after the decimal point:
>
> -- This test currently fails due extra trailing 0 digits.
> SELECT SUM(n::numeric) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
> FROM (VALUES(1,1.01),(2,2),(3,3)) v(i,n);
>
> Patched produces:
> 6.01
> 5.00
> 3.00
> Unpatched produces:
> 6.01
> 5
> 3

Hm, that's annoying. I checked the standard to see if it offers any guidance
here, but it doesn't look like it does - the standard just says that SUM() ought
to return a type with the same scale as the input type has. That's fine if
every NUMERIC type has a fixed scale, but that's not the case in postgres -
we allow values of unconstrained NUMERIC types (i.e., numeric types without an
explicitly specified precision or scale) to each define their own scale.

To fix this, we'd have to track the maximum scale within the current frame.
That's easier than the general problem of providing an inverse transition
function for MAX, because AFAIK we limit the scale to at most 1000. So it'd
be sufficient to track the number of times we saw each scale, and also the
current maximum. Once we reduce the current maximum's count back to zero
in the inverse transition function, we'd scan from that value to the left to
find the next non-zero entry.

We could also choose to ignore this, although I'm not sure I really like that.
It seems entirely OK at first sight - after all, the values all stay the same,
we just emit a different number of trailing zeros. But it still causes results
to be affected by values, even if only in the number of trailing zeros, which
lie outside the value's range. That seems like more non-determinism than as
database should show.

> With inverse transitions this query still produces correct results, it just does
> not produces the numeric in the same format as it does without performing inverse
> transitions. Personally I'd rather focus on trying to get SUM(numeric) in there
> for 9.4

I think it'd be worthwile to get this into 9.4, if that's still an option,
even if we only support COUNT.

best regards,
Florian Pflug

Florian Pflug <fgp(at)phlo(dot)org> writes:
> I think it'd be worthwile to get this into 9.4, if that's still an option,
> even if we only support COUNT.

My thought is

(1) we can certainly implement inverse transitions for COUNT() and the
integer variants of SUM(), and that alone would be a killer feature for
some people.

(2) the float and numeric variants should be implemented under nondefault
names (I'm thinking FAST_SUM(), but bikeshed away). People who need
extra speed and don't mind the slightly different results can alter
their queries to use these variants.

One reason I'm thinking this is that whatever we do to ameliorate
the semantic issues is going to slow down the forward transition
function --- to no benefit unless the aggregate is being used as a
window function in a moving window. So I'm less than convinced
that we *should* implement any of these designs in the default
aggregates, even if we get to the point where we arguably *could*
do it with little risk of functional differences.

regards, tom lane

On 14/01/14 14:29, Tom Lane wrote:
[...]
> (2) the float and numeric variants should be implemented under
> nondefault names (I'm thinking FAST_SUM(), but bikeshed away). People
> who need extra speed and don't mind the slightly different results can
> alter their queries to use these variants. One reason I'm thinking
> this is that whatever we do to ameliorate the semantic issues is going
> to slow down the forward transition function --- to no benefit unless
> the aggregate is being used as a window function in a moving window.
> So I'm less than convinced that we *should* implement any of these
> designs in the default aggregates, even if we get to the point where
> we arguably *could* do it with little risk of functional differences.
> regards, tom lane
How SUM_FAST() instead, then it will more likely to be close to SUM() in
an index?

Cheers,
Gavin

On Tue, Jan 14, 2014 at 2:00 PM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

> On Jan10, 2014, at 22:27 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> > As the patch stands at the moment, I currently have a regression test
> > which currently fails due to these extra zeros after the decimal point:
> >
> > -- This test currently fails due extra trailing 0 digits.
> > SELECT SUM(n::numeric) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND
> UNBOUNDED FOLLOWING)
> > FROM (VALUES(1,1.01),(2,2),(3,3)) v(i,n);
> >
> > Patched produces:
> > 6.01
> > 5.00
> > 3.00
> > Unpatched produces:
> > 6.01
> > 5
> > 3
>
> Hm, that's annoying. I checked the standard to see if it offers any
> guidance
> here, but it doesn't look like it does - the standard just says that SUM()
> ought
> to return a type with the same scale as the input type has. That's fine if
> every NUMERIC type has a fixed scale, but that's not the case in postgres -
> we allow values of unconstrained NUMERIC types (i.e., numeric types
> without an
> explicitly specified precision or scale) to each define their own scale.
>
>
Thanks for digging that out in the standard and thanks for all that
information you supplied here
http://www.postgresql.org/message-id/0FA6C08E-2166-405B-83F7-63B196B88CA3@phlo.org
too.
Sorry I've not had the chance to reply yet. I was kind of hoping that the
answer would be more in my favour to help with inverse transitions for
sum(numeric).

> To fix this, we'd have to track the maximum scale within the current frame.
> That's easier than the general problem of providing an inverse transition
> function for MAX, because AFAIK we limit the scale to at most 1000. So it'd
> be sufficient to track the number of times we saw each scale, and also the
> current maximum. Once we reduce the current maximum's count back to zero
> in the inverse transition function, we'd scan from that value to the left
> to
> find the next non-zero entry.
>
>
I've been thinking about this, but I had thought that the maximum dscale
was bigger than 1000. The docs seem to claim 16383 here -->
http://www.postgresql.org/docs/devel/static/datatype-numeric.html I'd go
ahead and implement this if that number was smaller, but I'm thinking
zeroing out an array of 16383 elements on first call to do_numeric_accum
might be too big an overhead to write off as "background noise". If it was
20 or even 100 then I'd probably try for that.

I think the overhead for each call after that would likely be ok as it
would probably just be an operation like
state->scaleCount[X.dscale]++; which I would imagine would be a very small
percentage overhead on normal aggregate functions. Of course the inverse
would have to do the harder work of looping backwards over the array until
it found an element with the count above 0 and setting that as the current
maximum. I think this would be a winner if it wasn't for the high initial
hit of zeroing that 16383 element array.. Or 1000 whichever.

> We could also choose to ignore this, although I'm not sure I really like
> that.
> It seems entirely OK at first sight - after all, the values all stay the
> same,
> we just emit a different number of trailing zeros. But it still causes
> results
> to be affected by values, even if only in the number of trailing zeros,
> which
> lie outside the value's range. That seems like more non-determinism than as
> database should show.
>
> > With inverse transitions this query still produces correct results, it
> just does
> > not produces the numeric in the same format as it does without
> performing inverse
> > transitions. Personally I'd rather focus on trying to get SUM(numeric)
> in there
> > for 9.4
>
> I think it'd be worthwile to get this into 9.4, if that's still an option,
> even if we only support COUNT.
>
> best regards,
> Florian Pflug
>
>

On Tue, Jan 14, 2014 at 2:29 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Florian Pflug <fgp(at)phlo(dot)org> writes:
> > I think it'd be worthwile to get this into 9.4, if that's still an
> option,
> > even if we only support COUNT.
>
> My thought is
>
> (1) we can certainly implement inverse transitions for COUNT() and the
> integer variants of SUM(), and that alone would be a killer feature for
> some people.
>
>
100% Agreed about sum(int) and count, but I've so far managed only to find
problems with SUM(numeric), other inverse transition functions seem just
fine with numeric types. e.g. AVG(numeric) and STDDEV(numeric), I can't
produce any results that differ from the unpatched head... but perhaps
someone can give me a case where things could vary?

I've been testing with something like:
select avg(n) over w,SUM(3::float) over w
from (values(1,10::numeric),(2,0),(3,0)) v(i,n)
window w as (order by i rows between current row and unbounded following);

where I included the sum(float) to force the old school brute force
transitions to be performed. I then compared the results to the ones given
without the sum(float) tagged on the end. I've so far not found anything
out of place.

(2) the float and numeric variants should be implemented under nondefault
> names (I'm thinking FAST_SUM(), but bikeshed away). People who need
> extra speed and don't mind the slightly different results can alter
> their queries to use these variants.
>

I'm not as keen on this idea, as if someone later thought of a nice way to
allow the inverse functions to provide exactly the same result as if they
were not used then the would become redundant legacy that would likely have
to be supported forever and a day, and I know we already have things like
that, but of course we want to minimise that as much as possible.

If AVG(numeric) and the stddev numeric aggregates turn out to be valid
then numeric_avg_accum_inv() must remain in core code to support that and
this is the exact function that is required for a user to define their own
SUM(numeric) with. We could leave it at that and document what a user must
do to create their own FAST_SUM then perhaps leave the including these in
core decision to later based maybe on the number of complaints about
SUM(numeric) being slow when used in windows with a moving frame head.

(For me) It does not seem too unreasonable to think that one day we might
decide that:

SELECT AVG(n) FROM (VALUES(10::NUMERIC(10,3)),(0),(0)) v(n);

return 3.333 instead of 3.3333333333333333 like it does now.

If we ever did that then we could support these numeric inverse transitions
on SUM() without having to worry about weird extra trailing zeros. Instead
we'd just give the user what they asked for, when they asked for it.
Reasons like that make me think that we might be jumping the gun a little
on FAST_SUM() as it could end up redundant more quickly than we might
initially think.

> One reason I'm thinking this is that whatever we do to ameliorate
> the semantic issues is going to slow down the forward transition
> function --- to no benefit unless the aggregate is being used as a
> window function in a moving window. So I'm less than convinced
> that we *should* implement any of these designs in the default
> aggregates, even if we get to the point where we arguably *could*
> do it with little risk of functional differences.
>
>
So far there's only 1 case of possible slowdown of forward transitions and
that's with numeric types.
I had to change do_numeric_accum() to add a NaN Counter increment and also
change the logic so that it continues summing non NaN values even after the
first NaN was encountered.

Would you see this as too big a performance risk to include in core?

If not then I think we might be able to support AVG(numeric) and
STDDEV(numeric) functions as the patch sits without having to worry that
there might be an extra overhead on forward transitions that include NaN
values.

Florian has done some really good work researching the standards around
this area. His research seems to indicate that the results should be of the
same scale as the inputs, which the current patch does not do, providing
you assume that the user is showing us the intended scale based on the
numbers that we're working with rather than a scale specified by the column
or cast. Florian's idea of how to fix the scale on inverse transition seems
pretty valid to me and I think the overhead of it could be made pretty
minimal. I'm just not sure that I can implement it in such a way as to make
the overhead small enough to look like background noise. But I'm very
willing to give it a try and see...

*** some moments pass ***

I think unless anyone has some objections I'm going to remove the inverse
transition for SUM(numeric) and modify the documents to tell the user how
to build their own FAST_SUM(numeric) using the built in functions to do it.
I'm starting to think that playing around with resetting numeric scale will
turn a possible 9.4 patch into a 9.5/10.0 patch. I see no reason why what's
there so far, minus sum(numeric), can't go in...

If so then there's 36 aggregate functions ticked off my "create an inverse
transition function for" list! I personally think that's a pretty good win.
I'd rather do this than battle and miss deadlines for 9.4. I'd find that
pretty annoying.

Regards

David Rowley

On Tue, Jan 14, 2014 at 9:09 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> I think unless anyone has some objections I'm going to remove the inverse
> transition for SUM(numeric) and modify the documents to tell the user how
> to build their own FAST_SUM(numeric) using the built in functions to do it.
> I'm starting to think that playing around with resetting numeric scale will
> turn a possible 9.4 patch into a 9.5/10.0 patch. I see no reason why what's
> there so far, minus sum(numeric), can't go in...
>
>
Of course its only now that I discover that this is not possible to do this:

CREATE AGGREGATE fast_sum (numeric)
(
stype = numeric,
sfunc = numeric_avg_accum,
invfunc = numeric_avg_accum_inv,
finalfunc = numeric_sum
);

because SUM(numeric) uses an internal type to store the transition state.

hmmm, built-in fast_sum anyone?
Is there any simple way to limit these to only be used in the context of a
window? If so is it worth it?
Would we want fast_sum() for float too?

Regards

David Rowley

On Tue, Jan 14, 2014 at 9:09 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> I think unless anyone has some objections I'm going to remove the inverse
> transition for SUM(numeric) and modify the documents to tell the user how
> to build their own FAST_SUM(numeric) using the built in functions to do it.
> I'm starting to think that playing around with resetting numeric scale will
> turn a possible 9.4 patch into a 9.5/10.0 patch. I see no reason why what's
> there so far, minus sum(numeric), can't go in...
>
> If so then there's 36 aggregate functions ticked off my "create an inverse
> transition function for" list! I personally think that's a pretty good win.
> I'd rather do this than battle and miss deadlines for 9.4. I'd find that
> pretty annoying.
>
>
Here's a patch which removes sum(numeric) and changes the documents a
little to remove a reference to using sum(numeric) to workaround the fact
that there's no inverse transitions for sum(float). I also made a small
change in the aggregates.sql tests to check that the aggfnoid <= 9999.

I've also pulled the regression tests that I had added for sum(numeric) as
they no longer test anything new. All tests are now passing.

With the attached patch I feel like I've left users a bit high and dry for
their sum(numeric) needs. I guess there is no true workaround as even if
they created their functions in SQL using simple + and - arithmetic, they
would likely suffer from NaN recovery problems. I'm starting to come around
to Tom's FAST_SUM idea as I simply can't see any fool proof workaround that
could be created without writing things in C.

The only problems I see with the FAST_SUM idea are that the number of
trailing zeros may appear a little random based on if inverse transitions
are used or are not used... Keep in mind that inverse transitions are not
performed if any aggregate in the window does not support them OR if any
aggregate in the frame contains a volatile function in the aggregate's
parameters or the FILTER (WHERE clause). Does this matter or can we just
document to warn about that?

If there's a few more +1s for FAST_SUM(numeric) then let me know and I'll
add it.
If anyone feels strongly against adding FAST_SUM then please let the
reasons for that known too.
Or failing that, if anyone has any other ideas that have not yet been
written on this thread, please post them so we can discuss.

Regards

David Rowley

> Regards
>
> David Rowley
>
>

On Jan14, 2014, at 11:06 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> Here's a patch which removes sum(numeric) and changes the documents a little to remove a reference to using sum(numeric) to workaround the fact that there's no inverse transitions for sum(float). I also made a small change in the aggregates.sql tests to check that the aggfnoid <= 9999.

I've looked over the patch, here a few comments.

For STRICT pairs of transfer and inverse transfer functions we should complain if any of them ever return NULL. That can never be correct anyway, since a STRICT function cannot undo a non-NULL -> NULL transition.

The same goes for non-STRICT, at least if we ever want to allow an inverse transfer function to indicate "Sorry, cannot undo in this case, please rescan". If we allowed NULL as just another state value now, we couldn't easily undo that later, so we'd rob ourselves of the obvious way for the inverse transfer function to indicate this condition to its caller.

The notnullcount machinery seems to apply to both STRICT and non-STRICT transfer function pairs. Shouldn't that be constrained to STRICT transfer function pairs? For non-STRICT pairs, it's up to the transfer functions to deal with NULL inputs however they please, no?

The logic around movedaggbase in eval_windowaggregates() seems a bit convoluted. Couldn't the if be moved before the code that pulls aggregatedbase up to frameheadpos using the inverse aggregation function?

Also, could we easily check whether the frames corresponding to the individual rows are all either identical or disjoint, and don't use the inverse transfer function then? Currently, for a frame which contains either just the current row, or all the current row's peers, I think we'd use the inverse transfer function to fully un-add the old frame, and then add back the new frame.

best regards,
Florian Pflug

On 1/13/14, 7:41 PM, Gavin Flower wrote:
> On 14/01/14 14:29, Tom Lane wrote:
> [...]
>> (2) the float and numeric variants should be implemented under nondefault names (I'm thinking FAST_SUM(), but bikeshed away). People who need extra speed and don't mind the slightly different results can alter their queries to use these variants. One reason I'm thinking this is that whatever we do to ameliorate the semantic issues is going to slow down the forward transition function --- to no benefit unless the aggregate is being used as a window function in a moving window. So I'm less than convinced that we *should* implement any of these designs in the default aggregates, even if we get to the point where we arguably *could* do it with little risk of functional differences. regards, tom lane
> How SUM_FAST() instead, then it will more likely to be close to SUM() in an index?

+1. That's what I do in cases like this.
--
Jim C. Nasby, Data Architect jim(at)nasby(dot)net
512.569.9461 (cell) http://jim.nasby.net

On Tue, Jan 14, 2014 at 4:16 AM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> On Tue, Jan 14, 2014 at 9:09 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>>
>> I think unless anyone has some objections I'm going to remove the inverse
>> transition for SUM(numeric) and modify the documents to tell the user how to
>> build their own FAST_SUM(numeric) using the built in functions to do it. I'm
>> starting to think that playing around with resetting numeric scale will turn
>> a possible 9.4 patch into a 9.5/10.0 patch. I see no reason why what's there
>> so far, minus sum(numeric), can't go in...
>>
>
> Of course its only now that I discover that this is not possible to do this:
>
> CREATE AGGREGATE fast_sum (numeric)
> (
> stype = numeric,
> sfunc = numeric_avg_accum,
> invfunc = numeric_avg_accum_inv,
> finalfunc = numeric_sum
> );
>
> because SUM(numeric) uses an internal type to store the transition state.
>
> hmmm, built-in fast_sum anyone?
> Is there any simple way to limit these to only be used in the context of a
> window? If so is it worth it?
> Would we want fast_sum() for float too?

Maybe these additional "fast" functions (one might also say
"inaccurate") should live in an extension, in contrib.

It strikes me that for numeric what you really need is to just tell
the sum operation, whether through a parameter or otherwise, how many
decimal places to show in the output. Obviously that's not a
practical change for sum() itself, but if we're inventing new stuff it
can be done.

For floats, things are not so good. The data type is inexact by
nature, and I think cases where you get substantially wrong answers
will be common enough that people who attempt to use whatever we
devise in this area will have sum trouble. *ducks*

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

On Jan15, 2014, at 19:56 , Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> It strikes me that for numeric what you really need is to just tell
> the sum operation, whether through a parameter or otherwise, how many
> decimal places to show in the output. Obviously that's not a
> practical change for sum() itself, but if we're inventing new stuff it
> can be done.

You can already do that, just cast the result of SUM(numeric) to
an appropriately constrained NUMERIC type, i.e. to NUMERIC(prec, scale).

BTW, AVG() and STDDEV() have the same issue. The problem is just partially
masked by the division by N (or N-1) at the end, because we always emit as
least 16 fractional digits when dividing. So you have to have an input
value with a larger scale than that to trigger it.

For the following query

select avg(x) over (order by i rows between current row and 1 following)
from (values
(1,1), (2,1), (3,0.000000000000000000000000000000001), (4,1), (5,1)
) t(i,x);

9.3 returns
avg
-------------------------------------
1.00000000000000000000
0.500000000000000000000000000000001
0.500000000000000000000000000000001
1.00000000000000000000
1.00000000000000000000

but HEAD+patch returns
avg
-------------------------------------
1.00000000000000000000
0.500000000000000000000000000000001
0.500000000000000000000000000000001
1.000000000000000000000000000000000
1.000000000000000000000000000000000

I have to admit that I'm *very* tempted to suggest we simply ignore this -
but that *would* mean accepting that windowed aggregates are non-
deterministic in the sense that their result (even if only in the number
of trailing zeros) depends on values outside of the frame. Which, I guess,
is a box that best stays closed...

I'm currently thinking the best way forward is to get a basic patch
without any NUMERIC stuff committed, and to revisit this after that's done.

best regards,
Florian Pflug

Florian Pflug <fgp(at)phlo(dot)org> writes:
> I'm currently thinking the best way forward is to get a basic patch
> without any NUMERIC stuff committed, and to revisit this after that's done.

+1. I liked Robert's suggestion that the "fast" aggregates be implemented
as a contrib module rather than directly in core, too. If we do that then
it's perfectly reasonable to handle that as a separate patch.

regards, tom lane

On Jan14, 2014, at 17:39 , Florian Pflug <fgp(at)phlo(dot)org> wrote:
> On Jan14, 2014, at 11:06 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>> Here's a patch which removes sum(numeric) and changes the documents a little to remove a reference to using sum(numeric) to workaround the fact that there's no inverse transitions for sum(float). I also made a small change in the aggregates.sql tests to check that the aggfnoid <= 9999.
>
> I've looked over the patch, here a few comments.
>
> For STRICT pairs of transfer and inverse transfer functions we should complain if any of them ever return NULL. That can never be correct anyway, since a STRICT function cannot undo a non-NULL -> NULL transition.
>
> The same goes for non-STRICT, at least if we ever want to allow an inverse transfer function to indicate "Sorry, cannot undo in this case, please rescan". If we allowed NULL as just another state value now, we couldn't easily undo that later, so we'd rob ourselves of the obvious way for the inverse transfer function to indicate this condition to its caller.
>
> The notnullcount machinery seems to apply to both STRICT and non-STRICT transfer function pairs. Shouldn't that be constrained to STRICT transfer function pairs? For non-STRICT pairs, it's up to the transfer functions to deal with NULL inputs however they please, no?

I modified the patch to do this, and ran into a problem. Currently, aggregates with state type "internal" cannot have a strict transfer function, even if they behave like they did, i.e. ignore non-NULL inputs. This is because the only possible initial value for state type "internal" is NULL, and it's up to the transfer function to create the state - usually upon seeing the first non-NULL input. Now, currently that isn't a huge problem - the transfer function simply has to check for NULL input values itself, and if it's indeed conceptually strict, it just returns in this case.

With inverse transfer functions, however, each such pair of forward and inverse transfer functions would also need to duplicate the NULL-counting logic from nodeWindowAgg.c if it want's to be conceptually strict, i.e. ignore NULL inputs, but return NULL if there are *only* NULL inputs (or no inputs at all). That seems like a lot of duplicated code in the long run.

In essence, what we'd want for strict pairs of forward and inverse transfer functions is for the forward transfer function to be strict in all arguments except the state, and the inverse to be strict according to the usual definition. We can't express that property of the forward transfer function within pg_proc, but we don't really have to - a local hack in nodeWindowAgg.c suffices. So what I'm proposing is:

We allow the forward transfer function to be non-strict even if the inverse is strict, but only if the initial value is NULL. In that case we behave as if the forward transfer function was strict, except that upon seeing the first non-NULL input we call it with a NULL state. The return value must still be non-NULL in all cases.

Thoughts?

best regards,
Florian Pflug

On Jan16, 2014, at 02:32 , Florian Pflug <fgp(at)phlo(dot)org> wrote:
> On Jan14, 2014, at 17:39 , Florian Pflug <fgp(at)phlo(dot)org> wrote:
>> On Jan14, 2014, at 11:06 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>>> Here's a patch which removes sum(numeric) and changes the documents a little to remove a reference to using sum(numeric) to workaround the fact that there's no inverse transitions for sum(float). I also made a small change in the aggregates.sql tests to check that the aggfnoid <= 9999.
>>
>> I've looked over the patch, here a few comments.
>>
>> For STRICT pairs of transfer and inverse transfer functions we should complain if any of them ever return NULL. That can never be correct anyway, since a STRICT function cannot undo a non-NULL -> NULL transition.
>>
>> The same goes for non-STRICT, at least if we ever want to allow an inverse transfer function to indicate "Sorry, cannot undo in this case, please rescan". If we allowed NULL as just another state value now, we couldn't easily undo that later, so we'd rob ourselves of the obvious way for the inverse transfer function to indicate this condition to its caller.
>>
>> The notnullcount machinery seems to apply to both STRICT and non-STRICT transfer function pairs. Shouldn't that be constrained to STRICT transfer function pairs? For non-STRICT pairs, it's up to the transfer functions to deal with NULL inputs however they please, no?
>
> I modified the patch to do this, and ran into a problem. Currently, aggregates with state type "internal" cannot have a strict transfer function, even if they behave like they did, i.e. ignore non-NULL inputs. This is because the only possible initial value for state type "internal" is NULL, and it's up to the transfer function to create the state - usually upon seeing the first non-NULL input. Now, currently that isn't a huge problem - the transfer function simply has to check for NULL input values itself, and if it's indeed conceptually strict, it just returns in this case.
>
> With inverse transfer functions, however, each such pair of forward and inverse transfer functions would also need to duplicate the NULL-counting logic from nodeWindowAgg.c if it want's to be conceptually strict, i.e. ignore NULL inputs, but return NULL if there are *only* NULL inputs (or no inputs at all). That seems like a lot of duplicated code in the long run.
>
> In essence, what we'd want for strict pairs of forward and inverse transfer functions is for the forward transfer function to be strict in all arguments except the state, and the inverse to be strict according to the usual definition. We can't express that property of the forward transfer function within pg_proc, but we don't really have to - a local hack in nodeWindowAgg.c suffices. So what I'm proposing is:
>
> We allow the forward transfer function to be non-strict even if the inverse is strict, but only if the initial value is NULL. In that case we behave as if the forward transfer function was strict, except that upon seeing the first non-NULL input we call it with a NULL state. The return value must still be non-NULL in all cases.

Ok, I tried this and it worked out quite OK.

Updated patch is attached. It passes regression tests, but those currently don't seem to include any aggregates which *don't* ignore NULL values, so that case is probably untested. Also, it allows non-strict forward transfer functions together with strict inverse transfer functions even for non-NULL initial states now. It seemed rather pedantic to forbid this.

BTW, as it stands, the patch currently uses the inverse transition function only when *all* the aggregates belonging to one window clause provide one. After working with the code a bit, I think that a bit of reshuffling would allow that distinction to be made on a per-aggregate basis. The question is, is it worth it?

best regards,
Florian Pflug

On Thu, Jan 16, 2014 at 3:47 PM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

> BTW, as it stands, the patch currently uses the inverse transition
> function only when *all* the aggregates belonging to one window clause
> provide one. After working with the code a bit, I think that a bit of
> reshuffling would allow that distinction to be made on a per-aggregate
> basis. The question is, is it worth it?
>
>
I didn't think it was all that worth it due to the fact that we'd still
need to process every tuple in the frame's scope for each aggregate which
has no inverse transition function, of course, there would be slightly less
work to do in such cases. I guess I just assumed that work load types that
would benefit from inverse transitions would have many rows instead of many
aggregates and few rows.

I guess to implement the aggregated up to marker variables would just need
to be per aggregate rather than per window.

If you think it would be worth it I can modify the patch to work that way.

Regards

David Rowley

> best regards,
> Florian Pflug
>

On Thu, Jan 16, 2014 at 9:45 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

> BTW, AVG() and STDDEV() have the same issue. The problem is just partially
> masked by the division by N (or N-1) at the end, because we always emit as
> least 16 fractional digits when dividing. So you have to have an input
> value with a larger scale than that to trigger it.
>
> For the following query
>
> select avg(x) over (order by i rows between current row and 1 following)
> from (values
> (1,1), (2,1), (3,0.000000000000000000000000000000001), (4,1), (5,1)
> ) t(i,x);
>
> 9.3 returns
> avg
> -------------------------------------
> 1.00000000000000000000
> 0.500000000000000000000000000000001
> 0.500000000000000000000000000000001
> 1.00000000000000000000
> 1.00000000000000000000
>
> but HEAD+patch returns
> avg
> -------------------------------------
> 1.00000000000000000000
> 0.500000000000000000000000000000001
> 0.500000000000000000000000000000001
> 1.000000000000000000000000000000000
> 1.000000000000000000000000000000000
>
>
Uhhh, that's bad news indeed. That means that I'll need to remove not only
all inverse transition functions for all aggregates on numeric types, but
also avg for int types, the stddev* functions for everything, since they
internally use numeric. I guess that only leaves SUM for smallint, int,
bigint, cash and interval, along with count(exp), count(*)...

> I have to admit that I'm *very* tempted to suggest we simply ignore this -
> but that *would* mean accepting that windowed aggregates are non-
> deterministic in the sense that their result (even if only in the number
> of trailing zeros) depends on values outside of the frame. Which, I guess,
> is a box that best stays closed...
>
>
Yeah, I can understand the temptation but I agree we can't go changing
results.

> I'm currently thinking the best way forward is to get a basic patch
> without any NUMERIC stuff committed, and to revisit this after that's done.
>
>
Agreed... I'll warm up my delete key.

Regards

David Rowley

> best regards,
> Florian Pflug
>
>

On Tue, Jan 14, 2014 at 2:29 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

>
> One reason I'm thinking this is that whatever we do to ameliorate
> the semantic issues is going to slow down the forward transition
> function --- to no benefit unless the aggregate is being used as a
> window function in a moving window. So I'm less than convinced
> that we *should* implement any of these designs in the default
> aggregates, even if we get to the point where we arguably *could*
> do it with little risk of functional differences.
>
> regards, tom lane
>

I was thinking about this earlier today and came up with an idea that
perhaps aggregates could support 2 transition functions. 1 for normal
aggregation and for windows with UNBOUNDED PRECEDING. The 2nd transition
function could be used when there is a possibility that we would need to
perform an inverse transition. This 2nd transition function could do all
the extra tracking it needed without having to worry that it would slow
down normal aggregation. With numeric that might be tracking each numeric's
scale as it enters and exits the window frame. It might even be possible to
perform inverse transitions with float and double here, we could just
internally use numeric, and have the final function convert back to the
original type. Though perhaps that might have the side effect of making
floating point calculations too accurate? Or at least not matching the IEEE
standards.

Of course, I'm not thinking this could be part of this patch, but I thought
that I'd post the idea while all this is fresh in people's heads.

David

On Wed, Jan 15, 2014 at 5:39 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

The notnullcount machinery seems to apply to both STRICT and non-STRICT
> transfer function pairs. Shouldn't that be constrained to STRICT transfer
> function pairs? For non-STRICT pairs, it's up to the transfer functions to
> deal with NULL inputs however they please, no?
>
>
The reason I had to track the notnullcount was because for non-strict was
because:

select sum(n) over (order by i rows between current row and unbounded
following) from (values(1,1),(2,NULL)) v(i,n);

would otherwise return

1
0

sum is not strict, so I guess we need to track notnullcount for non-strict
functions.

See the code around if (peraggstate->notnullcount == 0)
in retreat_windowaggregate().

> The logic around movedaggbase in eval_windowaggregates() seems a bit
> convoluted. Couldn't the if be moved before the code that pulls
> aggregatedbase up to frameheadpos using the inverse aggregation function?
>
>
I had a look at this and even tried moving the code to before the inverse
transitions, but it looks like that would only work if I added more tests
to the if condition to ensure that we're not about to perform inverse
transitions. To me it just seemed more bullet proof the way it is rather
than duplicating logic and having to ensure that it stays duplicated. But
saying that I don't think I've fully got my head around why the original
code is valid in the first place. I would have imagined that it should
contain a check for FRAMEOPTION_START_UNBOUNDED_FOLLOWING, but if that
sounds like complete rubbish then I'll put it down to my head still being
fried from work.

> Also, could we easily check whether the frames corresponding to the
> individual rows are all either identical or disjoint, and don't use the
> inverse transfer function then? Currently, for a frame which contains
> either just the current row, or all the current row's peers, I think we'd
> use the inverse transfer function to fully un-add the old frame, and then
> add back the new frame.
>
>
I didn't know there was a situation where this could happen. Could you give
me an example query and I'll run it through the debugger to have a look at
what's going on. But sure, if this is possible and I understand what you
mean then I guess it would be a good optimisation to detect this and throw
away the previous results and start fresh.

Thanks for all of your reviewing on this so far.

Regards

David Rowley

> best regards,
> Florian Pflug
>
>

On Thu, Jan 16, 2014 at 9:45 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

> I'm currently thinking the best way forward is to get a basic patch
> without any NUMERIC stuff committed, and to revisit this after that's done.
>
>
Attached is a version to that effect. The number of inverse transition
functions is down to 8 from 36.

I managed to keep avg(interval) in there as it's all integer based division.
sum for all int types remain, plus sum for interval and cash. count(exp)
and count(*) also naturally remain.

sum(bigint) became a bit weird as it uses numeric types internally, so I
had to keep the do_numeric_discard() function to support it. Previously
this function did NaNCount-- if it was removing a NaN numeric, but since I
got rid of the NaNCounter as it was no longer required I just decided to
throw an error if we encounter a numeric with NaN. I thought this was ok as
the only place the function is being called the numeric value being passed
is built from a bigint which obviously can't be NaN. It may be better to
just get rid of do_numeric_discard() and stick the sub_var(&(state->sumX),
newval, &(state->sumX)); into int8_avg_accum_inv(). I don't have a
preference as to which as I think there's reasons for both ways. Perhaps
even the name int8_avg_accum_inv() is misleading as we never use it for
avg(bigint). Anyway, I'll leave it as is for now as I just can't decide
which way is better.

Florian, I've not had a chance to look at your updated v2.2 patch yet
sorry. I'll try and get some time tomorrow evening.

Regards

David Rowley

> best regards,
> Florian Pflug
>
>

On Jan16, 2014, at 09:07 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> On Wed, Jan 15, 2014 at 5:39 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:
>> The notnullcount machinery seems to apply to both STRICT and non-STRICT transfer function pairs. Shouldn't that be constrained to STRICT transfer function pairs? For non-STRICT pairs, it's up to the transfer functions to deal with NULL inputs however they please, no?
>
> The reason I had to track the notnullcount was because for non-strict was because:
>
> select sum(n) over (order by i rows between current row and unbounded following) from (values(1,1),(2,NULL)) v(i,n);
>
> would otherwise return
> 1
> 0
>
> sum is not strict, so I guess we need to track notnullcount for non-strict functions.
> See the code around if (peraggstate->notnullcount == 0) in retreat_windowaggregate().

Yeah, I figured that was the reason, but you can't fix it that way. See http://www.postgresql.org/message-id/8E857D95-CBA4-4974-A238-9DD7F61BEA48@phlo.org for a detailed explanation why. My 2.2 patch allows pairs of non-strict forward and strict inverse transfer functions exactly because of this - i.e., basically it decrees that if there's an inverse transfer function, the strict setting of the *inverse* function determines the aggregates NULL behaviour. The forward transfer function is then never called
for NULL inputs, but it *is* called with the NULL state for the first non-NULL input, and *must* then return a non-NULL state (hence it's technically not strict, it's strict only in the inputs, not in the state).

BTW, I just realized I failed to update CREATE AGGREGATE's logic when I did that in 2.2. That doesn't matter for the built-in aggregates since these aren't created with CREATE AGGREGATE, but it's obviously wrong. I'll post a fixed patched.

>> The logic around movedaggbase in eval_windowaggregates() seems a bit convoluted. Couldn't the if be moved before the code that pulls aggregatedbase up to frameheadpos using the inverse aggregation function?

> I had a look at this and even tried moving the code to before the inverse transitions, but it looks like that would only work if I added more tests to the if condition to ensure that we're not about to perform inverse transitions. To me it just seemed more bullet proof the way it is rather than duplicating logic and having to ensure that it stays duplicated. But saying that I don't think I've fully got my head around why the original code is valid in the first place. I would have imagined that it should contain a check for FRAMEOPTION_START_UNBOUNDED_FOLLOWING, but if that sounds like complete rubbish then I'll put it down to my head still being fried from work.

Ok, I get this now. That code really just is asking "is the previous row's frame the same as the current row's frame" in that "if" where you added movedagg. What confused me was the rather weird way that condition is expressed, which turns out is due to the fact that at the point of the if, we don't know the new frame's end. Now, we could use update_frametailpos() to find that, but that's potentially costly, especially if the tuple store was spilled to disk. So instead, the code relies on the fact that only if the frame end is "n FOLLOWING/PRECEDING" can the current row lie within the previous row's frame without the two frame's ends being necessarily the same.

For added confusion, that "if" never explicitly checks whether the frame's *heads* coincide - the previous code seems to have relied on the impossibility of having "aggregatedbase <= current < aggregatedupto" after re-initializing the aggregation, because then aggregatedbase = aggregatedupto = 0. That's why you can't just move the "if" before the "frameheadpos == aggregatedbase" check. But you can *if* you also check whether "aggregatedbase == frameheadpos" in the if - which is clearer than relying on that rather subtle assumption anyway.

BTW, the your patch will also fail badly if the frame head ever moves backwards - the invariant that "aggregatedbase == frameheadpos" after the inverse transition loop will then be violated. Now, this should never happen, because we require that the offset in "n PRECEDING/FOLLOWING" is constant, but we should probably still check for this and elog().

That check was implicit in old code, because it advanced the tuplestore mark, so if the frame head moved backwards, re-scanning the frame would have failed. That brings me to another todo - as it stands, that mark gets never advanced if we're doing inverse aggregation. To fix that, we need a call to WinSetMarkPosition() somewhere in eval_windowaggregates().

After doing this things, eval_windowaggregates ended up calling initalize_windowframeaggregates at a single place again, so I inlined it back into eval_windowaggregates(). I also made it use temp_slot_1 in the inverse aggregation loop, since that seemed safe - the code assumes some invariants about aggregatedbase and agg_row_slow.

Updated patch is attached (2.4_fgp).

>> Also, could we easily check whether the frames corresponding to the individual rows are all either identical or disjoint, and don't use the inverse transfer function then? Currently, for a frame which contains either just the current row, or all the current row's peers, I think we'd use the inverse transfer function to fully un-add the old frame, and then add back the new frame.
>
> I didn't know there was a situation where this could happen. Could you give me an example query and I'll run it through the debugger to have a look at what's going on. But sure, if this is possible and I understand what you mean then I guess it would be a good optimisation to detect this and throw away the previous results and start fresh.

The case I had in mind there was "RANGE BETWEEN CURRENT ROW AND CURRENT ROW", i.e. each row's frame consists of all it's ordering peers. Haven't looked into this yet.

best regards,
Florian Pflug

On 01/16/2014 01:02 PM, David Rowley wrote:
> sum(bigint) became a bit weird as it uses numeric types internally, so I
> had to keep the do_numeric_discard() function to support it.

It's pretty weird that we have implemented sum(bigint) that way. I
understand that the result is a numeric so that it won't overflow, but
implementing it by converting every value to numeric is naive.

I propose that we reimplement sum(bigint) in a more efficient way: For
the internal state, let's use an int8 and a numeric overflow field. The
transition function adds to the int8 variable, and checks for overflow.
On overflow, increment the numeric field by one. In the final function,
multiply the numeric by 2^64, and add the residual int8 value.

- Heikki

Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
> I propose that we reimplement sum(bigint) in a more efficient way: For
> the internal state, let's use an int8 and a numeric overflow field. The
> transition function adds to the int8 variable, and checks for overflow.
> On overflow, increment the numeric field by one. In the final function,
> multiply the numeric by 2^64, and add the residual int8 value.

It'd probably be sufficient to handle it as two int64 fields (handmade
128-bit arithmetic, or maybe even not so handmade if that ever gets
reasonably common among C compilers). You're assuming the final output
is still numeric, right?

regards, tom lane

On 01/16/2014 08:59 PM, Tom Lane wrote:
> Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
>> I propose that we reimplement sum(bigint) in a more efficient way: For
>> the internal state, let's use an int8 and a numeric overflow field. The
>> transition function adds to the int8 variable, and checks for overflow.
>> On overflow, increment the numeric field by one. In the final function,
>> multiply the numeric by 2^64, and add the residual int8 value.
>
> It'd probably be sufficient to handle it as two int64 fields (handmade
> 128-bit arithmetic, or maybe even not so handmade if that ever gets
> reasonably common among C compilers).

True. That would be sufficient for summing 2^64 int8s of INT64_MAX. That
sounds like enough, especially considering that that count() will
overflow after that too.

> You're assuming the final output is still numeric, right?

Yep.

- Heikki

On 2014-01-16 21:07:33 +0200, Heikki Linnakangas wrote:
> On 01/16/2014 08:59 PM, Tom Lane wrote:
> >Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
> >>I propose that we reimplement sum(bigint) in a more efficient way: For
> >>the internal state, let's use an int8 and a numeric overflow field. The
> >>transition function adds to the int8 variable, and checks for overflow.
> >>On overflow, increment the numeric field by one. In the final function,
> >>multiply the numeric by 2^64, and add the residual int8 value.
> >
> >It'd probably be sufficient to handle it as two int64 fields (handmade
> >128-bit arithmetic, or maybe even not so handmade if that ever gets
> >reasonably common among C compilers).
>
> True. That would be sufficient for summing 2^64 int8s of INT64_MAX. That
> sounds like enough, especially considering that that count() will overflow
> after that too.

You'll have to handle adding negative values and underflow as
well.
Maybe it's instead sufficient to just have flag indicating that you're
working with a state that hasn't overflowed so far and just plain int8
math as long as that's the case, and entirely fall back to the current
path once overflowed. That will probably be slightly faster and easily
handle the majority of cases since overflowing int8 ought to be pretty
rare in the real world.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> You'll have to handle adding negative values and underflow as
> well.

Right.

> Maybe it's instead sufficient to just have flag indicating that you're
> working with a state that hasn't overflowed so far and just plain int8
> math as long as that's the case, and entirely fall back to the current
> path once overflowed. That will probably be slightly faster and easily
> handle the majority of cases since overflowing int8 ought to be pretty
> rare in the real world.

Dunno, I think that a transition state containing both an int64 and
a (presumably separately palloc'd) numeric will be a real PITA.
And it will not be faster, because the principal drag on performance
will just be the overflow test, which you have to do either way.

regards, tom lane

On 2014-01-16 14:23:47 -0500, Tom Lane wrote:
> > Maybe it's instead sufficient to just have flag indicating that you're
> > working with a state that hasn't overflowed so far and just plain int8
> > math as long as that's the case, and entirely fall back to the current
> > path once overflowed. That will probably be slightly faster and easily
> > handle the majority of cases since overflowing int8 ought to be pretty
> > rare in the real world.
>
> Dunno, I think that a transition state containing both an int64 and
> a (presumably separately palloc'd) numeric will be a real PITA.

Yea, not sure myself. I just dislike the idea of having a good part of a
128bit math implementation for a single transition function.

Another alternative would be a configure check for compiler/native
128bit math and fall back to the current implementation if none is
provided... That should give decent performance with a pretty low amount
of code for most platforms.

> And it will not be faster, because the principal drag on performance
> will just be the overflow test, which you have to do either way.

Well, you don't need to check the second variable for lots of
operations. Say, the current sum is 0 and you add a -1. With the two
variables scheme that requires checking the second variable,
manipulating it etc.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> On 2014-01-16 14:23:47 -0500, Tom Lane wrote:
>> Dunno, I think that a transition state containing both an int64 and
>> a (presumably separately palloc'd) numeric will be a real PITA.

> Yea, not sure myself. I just dislike the idea of having a good part of a
> 128bit math implementation for a single transition function.

Not sure how you figure that we need very much new code beyond the
overflow test.

> Well, you don't need to check the second variable for lots of
> operations. Say, the current sum is 0 and you add a -1. With the two
> variables scheme that requires checking the second variable,
> manipulating it etc.

I'm envisioning just

state->lowhalf += input;
if (overflowed_up)
state->highhalf++;
else if (overflowed_down)
state->highhalf--;

The only thing that might take a moment's thought, or extra cycles in the
normal case, is extending the overflow test so that it can tell whether
we need to increment or decrement the upper half.

[ thinks a bit... ] Note that I'm supposing that the state is defined
as (highhalf * 2^64) + lowhalf, not that we need the two variables to
be exactly a 128-bit twos-complement value, which is what I think
you're talking about.

regards, tom lane

I had some more fun with this, the result is v2.5 of the patch (attached). Changes are explained below.

On Jan16, 2014, at 19:10 , Florian Pflug <fgp(at)phlo(dot)org> wrote:
> On Jan16, 2014, at 09:07 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>> On Wed, Jan 15, 2014 at 5:39 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:
>>> The notnullcount machinery seems to apply to both STRICT and non-STRICT transfer function pairs. Shouldn't that be constrained to STRICT transfer function pairs? For non-STRICT pairs, it's up to the transfer functions to deal with NULL inputs however they please, no?
>>
>> The reason I had to track the notnullcount was because for non-strict was because:
>>
>> select sum(n) over (order by i rows between current row and unbounded following) from (values(1,1),(2,NULL)) v(i,n);
>>
>> would otherwise return
>> 1
>> 0
>>
>> sum is not strict, so I guess we need to track notnullcount for non-strict functions.
>> See the code around if (peraggstate->notnullcount == 0) in retreat_windowaggregate().
>
> Yeah, I figured that was the reason, but you can't fix it that way. See http://www.postgresql.org/message-id/8E857D95-CBA4-4974-A238-9DD7F61BEA48@phlo.org for a detailed explanation why. My 2.2 patch allows pairs of non-strict forward and strict inverse transfer functions exactly because of this - i.e., basically it decrees that if there's an inverse transfer function, the strict setting of the *inverse* function determines the aggregates NULL behaviour. The forward transfer function is then never called
> for NULL inputs, but it *is* called with the NULL state for the first non-NULL input, and *must* then return a non-NULL state (hence it's technically not strict, it's strict only in the inputs, not in the state).
>
> BTW, I just realized I failed to update CREATE AGGREGATE's logic when I did that in 2.2. That doesn't matter for the built-in aggregates since these aren't created with CREATE AGGREGATE, but it's obviously wrong. I'll post a fixed patched.

Fixed now.

>>> The logic around movedaggbase in eval_windowaggregates() seems a bit convoluted. Couldn't the if be moved before the code that pulls aggregatedbase up to frameheadpos using the inverse aggregation function?
>
>> I had a look at this and even tried moving the code to before the inverse transitions, but it looks like that would only work if I added more tests to the if condition to ensure that we're not about to perform inverse transitions. To me it just seemed more bullet proof the way it is rather than duplicating logic and having to ensure that it stays duplicated. But saying that I don't think I've fully got my head around why the original code is valid in the first place. I would have imagined that it should contain a check for FRAMEOPTION_START_UNBOUNDED_FOLLOWING, but if that sounds like complete rubbish then I'll put it down to my head still being fried from work.
>
> Ok, I get this now. That code really just is asking "is the previous row's frame the same as the current row's frame" in that "if" where you added movedagg. What confused me was the rather weird way that condition is expressed, which turns out is due to the fact that at the point of the if, we don't know the new frame's end. Now, we could use update_frametailpos() to find that, but that's potentially costly, especially if the tuple store was spilled to disk. So instead, the code relies on the fact that only if the frame end is "n FOLLOWING/PRECEDING" can the current row lie within the previous row's frame without the two frame's ends being necessarily the same.
>
> For added confusion, that "if" never explicitly checks whether the frame's *heads* coincide - the previous code seems to have relied on the impossibility of having "aggregatedbase <= current < aggregatedupto" after re-initializing the aggregation, because then aggregatedbase = aggregatedupto = 0. That's why you can't just move the "if" before the "frameheadpos == aggregatedbase" check. But you can *if* you also check whether "aggregatedbase == frameheadpos" in the if - which is clearer than relying on that rather subtle assumption anyway.
>
> BTW, the your patch will also fail badly if the frame head ever moves backwards - the invariant that "aggregatedbase == frameheadpos" after the inverse transition loop will then be violated. Now, this should never happen, because we require that the offset in "n PRECEDING/FOLLOWING" is constant, but we should probably still check for this and elog().
>
> That check was implicit in old code, because it advanced the tuplestore mark, so if the frame head moved backwards, re-scanning the frame would have failed. That brings me to another todo - as it stands, that mark gets never advanced if we're doing inverse aggregation. To fix that, we need a call to WinSetMarkPosition() somewhere in eval_windowaggregates().
>
> After doing this things, eval_windowaggregates ended up calling initalize_windowframeaggregates at a single place again, so I inlined it back into eval_windowaggregates(). I also made it use temp_slot_1 in the inverse aggregation loop, since that seemed safe - the code assumes some invariants about aggregatedbase and agg_row_slow.
>
> Updated patch is attached (2.4_fgp).

I've now shuffled things around so that we can use inverse transition functions
even if only some aggregates provide them, and to allow inverse transition
functions to force a restart by returning NULL. The rules regarding NULL handling
are now the following

(A) Transition functions without an inverse behave as they always did
(B) Forward transition functions with an inverse may not return NULL,
not even for all-NULL inputs.
(C) If the inverse transition function returns NULL, the aggregation is
restarted from the beginning, just as If no inverse transition
function had been provided.
(D) If the transition function is strict, the inverse must also be.
(E) NULLs are skipped if the inverse transition function is strict,
regardless of whether the forward transition function is.

The rules may seem a bit weird, but they're the only solution I found which

* Doesn't require every invertible transition function with "internal"
state to implement it's own NULL counting. This requires (E), since
transition functions with state type "internal" need to be callable
with a NULL state - since nobody else can allocate the state object.

* Still allows transition functions to handle NULL values however they
please - they just have to have a non-strict inverse to opt out of (E).
They cannot use NULL states however they please, though.

* Allows partial inverse transition functions, i.e. inverse transition
functions which sometimes report "sorry, please restart". The only
easy way to report this is to have the inverse transition function
return NULL, which means we cannot allow NULL as just another state
value, i.e. this mandates (B,C)

(D) is purely to avoid having to deal with any special-cases that might
arise from allowing this.

I've also moved the volatile functions check into initialize_peragg() -
having it in ExecWindowAgg() made no sense to me since it's dealing
with static information. Also, ExecWindowAgg() may get called multiple
times, e.g. if the window functions are on the inner side of a
nested loop join or within a subselect.

>>> Also, could we easily check whether the frames corresponding to the individual rows are all either identical or disjoint, and don't use the inverse transfer function then? Currently, for a frame which contains either just the current row, or all the current row's peers, I think we'd use the inverse transfer function to fully un-add the old frame, and then add back the new frame.
>>
>> I didn't know there was a situation where this could happen. Could you give me an example query and I'll run it through the debugger to have a look at what's going on. But sure, if this is possible and I understand what you mean then I guess it would be a good optimisation to detect this and throw away the previous results and start fresh.
>
> The case I had in mind there was "RANGE BETWEEN CURRENT ROW AND CURRENT ROW", i.e. each row's frame consists of all it's ordering peers. Haven't looked into this yet.

It now resets the aggregation when the new frame doesn't overlap the old one, i.e. if frameheadpos > aggregatedupto.

The patch passes regression test, but I haven't done any other testing yet.
Also, the documentation doesn't explain the NULL and STRICT semantics yet.

best regards,
Florian Pflug

On Fri, Jan 17, 2014 at 3:05 PM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

> I had some more fun with this, the result is v2.5 of the patch (attached).
> Changes are explained below.
>
>
Looks like you've been busy on this! Thank you for implementing all the
changes you talked about.
I've now started working the 2.5 patch you sent and I've ripped out all the
numeric inverse transition functions on that patch and implemented inverse
transitions for max and min using the new NULL returning method that you've
implemented. I've also made a very fast pass and fixed up a few comments
and some random white space. I've not gotten to the documents yet.

I did add a whole bunch of regression tests for all of the inverse
transition functions that are used for max and min. I'm just calling these
like:
SELECT int4larger_inv(3,2),int4larger_inv(3,3),int4larger_inv(3,4);
Rather than using the aggregate as a window function each time. I thought
it was better to validate each of those functions individually then put in
various tests that target a smaller number of aggregates with various
inputs.

A few things still to do that I'll try and get to soon.
1. More testing
2. Docs updated.
3. Perhaps I'll look at adding bitand and bitor inverse transition functions
4. ?

Thanks again for putting so much effort into this.
If you make any more changes would it be possible for you to base them on
the attached patch instead of the last one you sent?

Perhaps if there's much more hacking to do we could start pushing to a
guthub repo to make it easier to work together on this.

Regards

David Rowley

On Jan17, 2014, at 15:14 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> If you make any more changes would it be possible for you to base them on the attached patch instead of the last one you sent?

Sure! The only reason I didn't rebase my last patch onto yours was that having the numeric stuff in there meant potentially better test coverage. Thanks for doing the merge!

> Perhaps if there's much more hacking to do we could start pushing to a guthub repo to make it easier to work together on this.

Yeah, that seems like a good idea. Easier to keep track of then a bunch of patches floating around. Could you push your latest version?

best regards,
Florian Pflug

On Fri, Jan 17, 2014 at 3:05 PM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

>
> I've now shuffled things around so that we can use inverse transition
> functions
> even if only some aggregates provide them, and to allow inverse transition
> functions to force a restart by returning NULL. The rules regarding NULL
> handling
> are now the following
>
>
Maybe this is me thinking out loud, but I'm just thinking about the numeric
case again.
Since the patch can now handle inverse transition functions returning NULL
when they fail to perform inverse transitions, I'm wondering if we could
add an "expectedscale" to NumericAggState, set it to -1 initially, when we
get the first value set the expectedscale to the dscale of that numeric,
then if we get anything but that value we'll set the expectedscale back to
-1 again, if we are asked to perform an inverse transition with a
expectedscale as -1 we'll return null, otherwise we can perform the inverse
transition...

Thoughts?

Regards

David Rowley

On Jan17, 2014, at 20:34 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> On Fri, Jan 17, 2014 at 3:05 PM, Florian Pflug <fgp(at)phlo(dot)org> wrote:
>
>> I've now shuffled things around so that we can use inverse transition functions
>> even if only some aggregates provide them, and to allow inverse transition
>> functions to force a restart by returning NULL. The rules regarding NULL handling
>> are now the following
>
> Maybe this is me thinking out loud, but I'm just thinking about the numeric case again.
> Since the patch can now handle inverse transition functions returning NULL when they
> fail to perform inverse transitions, I'm wondering if we could add an "expectedscale"
> to NumericAggState, set it to -1 initially, when we get the first value set the
> expectedscale to the dscale of that numeric, then if we get anything but that value
> we'll set the expectedscale back to -1 again, if we are asked to perform an inverse
> transition with a expectedscale as -1 we'll return null, otherwise we can perform
> the inverse transition...

You could do better than that - the numeric problem amounts to tracking the maximum
scale AFAICS, so it'd be sufficient to restart if we remove a value whose scale equals
the current maximum. But if we do SUM(numeric) at all, I think we should do so
without requiring restarts - I still think the overhead of tracking the maximum scale
within the aggregated values isn't that bad. If we zero the dscale counters lazily,
the numbers of entries we have to zero is bound by the maximum dscale we encounter.
Since actually summing N digits is probably more expensive than zeroing them, and since
we pay the zeroing overhead only once per aggregation but save potentially many
summations, I'm pretty sure we come out ahead by quite some margin.

It'd be interesting to do float() similar to the way you describe, though. We might
not be able to guarantee that we yield exactly the same result as without inverse
aggregation, but we might be able to bound the error. That might make it acceptable
to do this - as Kevin pointed out, float is always an approximation anyway. I haven't
really thought that through, though...

Anyway, with time running out fast if we want to get this into 9.4, I think we should
focus on getting this into a committable state right now.

I've started to look over what you've pushed to github, and it looks mostly fine.
I have a few comments - mostly cosmetic stuff - that I'll post once I finished reading
through it. I also plan to do some basic performance testing to verify that my
reshuffling of eval_windowaggregates() doesn't hurt aggregates without an inverse
transition function.

best regards,
Florian Pflug

On Sat, Jan 18, 2014 at 10:17 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

> On Jan17, 2014, at 20:34 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> > On Fri, Jan 17, 2014 at 3:05 PM, Florian Pflug <fgp(at)phlo(dot)org> wrote:
> >
> >> I've now shuffled things around so that we can use inverse transition
> functions
> >> even if only some aggregates provide them, and to allow inverse
> transition
> >> functions to force a restart by returning NULL. The rules regarding
> NULL handling
> >> are now the following
> >
> > Maybe this is me thinking out loud, but I'm just thinking about the
> numeric case again.
> > Since the patch can now handle inverse transition functions returning
> NULL when they
> > fail to perform inverse transitions, I'm wondering if we could add an
> "expectedscale"
> > to NumericAggState, set it to -1 initially, when we get the first value
> set the
> > expectedscale to the dscale of that numeric, then if we get anything but
> that value
> > we'll set the expectedscale back to -1 again, if we are asked to perform
> an inverse
> > transition with a expectedscale as -1 we'll return null, otherwise we
> can perform
> > the inverse transition...
>
> You could do better than that - the numeric problem amounts to tracking
> the maximum
> scale AFAICS, so it'd be sufficient to restart if we remove a value whose
> scale equals
> the current maximum. But if we do SUM(numeric) at all, I think we should
> do so
> without requiring restarts - I still think the overhead of tracking the
> maximum scale
> within the aggregated values isn't that bad. If we zero the dscale
> counters lazily,
> the numbers of entries we have to zero is bound by the maximum dscale we
> encounter.
> Since actually summing N digits is probably more expensive than zeroing
> them, and since
> we pay the zeroing overhead only once per aggregation but save potentially
> many
> summations, I'm pretty sure we come out ahead by quite some margin.
>
>
We'll work that out, I don't think it will take very long to code up your
idea either.
I just thought that my idea was good enough and very cheap too, won't all
numerics that are actually stored in a column have the same scale anyway?
Is it not only been a problem because we've been testing with random
numeric literals the whole time?

The test turned out to become:
if (state->expectedScale == -1)
state->expectedScale = X.dscale;
else if (state->expectedScale != X.dscale)
state->expectedScale = -2;

In do_numeric_accum, then when we do the inverse I just check if
expectedScale < 0 then return NULL.

I'm not set on it, and I'm willing to try the lazy zeroing of the scale
tracker array, but I'm just not quite sure what extra real use cases it
covers that the one above does not. Perhaps my way won't perform inverse
transitions if the query did sum(numericCol / 10) or so.

I'll be committing this to the github repo very soon, so we can hack away
at the scale tracking code once it's back in.

David Rowley

On Sat, Jan 18, 2014 at 10:42 AM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

>
>> You could do better than that - the numeric problem amounts to tracking
>> the maximum
>> scale AFAICS, so it'd be sufficient to restart if we remove a value whose
>> scale equals
>> the current maximum. But if we do SUM(numeric) at all, I think we should
>> do so
>> without requiring restarts - I still think the overhead of tracking the
>> maximum scale
>> within the aggregated values isn't that bad. If we zero the dscale
>> counters lazily,
>> the numbers of entries we have to zero is bound by the maximum dscale we
>> encounter.
>> Since actually summing N digits is probably more expensive than zeroing
>> them, and since
>> we pay the zeroing overhead only once per aggregation but save
>> potentially many
>> summations, I'm pretty sure we come out ahead by quite some margin.
>>
>>
> We'll work that out, I don't think it will take very long to code up your
> idea either.
> I just thought that my idea was good enough and very cheap too, won't all
> numerics that are actually stored in a column have the same scale anyway?
> Is it not only been a problem because we've been testing with random
> numeric literals the whole time?
>
> The test turned out to become:
> if (state->expectedScale == -1)
> state->expectedScale = X.dscale;
> else if (state->expectedScale != X.dscale)
> state->expectedScale = -2;
>
> In do_numeric_accum, then when we do the inverse I just check if
> expectedScale < 0 then return NULL.
>
> I'm not set on it, and I'm willing to try the lazy zeroing of the scale
> tracker array, but I'm just not quite sure what extra real use cases it
> covers that the one above does not. Perhaps my way won't perform inverse
> transitions if the query did sum(numericCol / 10) or so.
>
> I'll be committing this to the github repo very soon, so we can hack away
> at the scale tracking code once it's back in.
>
>
Ok, we're back up to 86 aggregate function / type combinations with inverse
transition functions.
I've commited my latest work up to github and here's a fresh patch which I
will need to do more tests on.

The test (below) that used to fail a few versions ago is back in there and
it's now passing.

SELECT SUM(n::numeric) OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND
UNBOUNDED FOLLOWING)
FROM (VALUES(1,1.01),(2,2),(3,3)) v(i,n);

In this case it won't use inverse transitions because the forward
transition function detects that the scale is not fixed.

I tested throwing some numerics into a table and I'm pretty happy with the
results.

create table num (num numeric(10,2) not null);
insert into num (num) select * from generate_series(1,20000);
select sum(num) over(order by num rows between current row and unbounded
following) from num; -- 124ms
select sum(num / 10) over(order by num rows between current row and
unbounded following) from num; -- 254ms
select sum(num / 1) over(order by num rows between current row and
unbounded following) from num; -- 108156.917 ms

The divide by 1 case is slow because of that weird 20 trailing zero instead
of 16 when dividing a numeric by 1 and that causes the inverse transition
function to return NULL because the scale changes.

I've not tested an unpatched version yet to see how that divide by 1 query
performs on that but I'll get to that soon.

I'm thinking that the idea about detecting the numeric range with floating
point types and performing an inverse transition providing the range has
not gone beyond some defined danger zone is not material for this patch...
I think it would be not a great deal of work to code, but the testing
involved would probably make this patch not possible for 9.4

The latest version of the patch is attached.

Regards

David Rowley

David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> I just thought that my idea was good enough and very cheap too, won't all
> numerics that are actually stored in a column have the same scale anyway?

No; unconstrained numeric columns (ie, if you just say "numeric") don't
force their contents to any particular scale. It might be that we don't
have to optimize for that case, since it's not in the SQL spec, but it
is definitely supported by PG.

regards, tom lane