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

On Sun, Dec 15, 2013 at 2: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.
>
>
It came to me that it might be possible to implement inverse transitions
for floating point aggregates by just detecting if precision has been lost
during forward transitions.

I've written the test to do this as:

IF state.value + value = state.value AND value <> 0 THEN
newstate.precision_lost := true; newstate.value := state.value; ELSE
newstate.precision_lost := false; newstate.value := state.value + value;
END IF;
The inverse transition function checks the precision_lost and if it's true
it returns NULL. The core code is now implemented (thanks to Florian) to
re-aggregate when NULL is returned from the inverse transition function.

I've attached an implementation of this with the transition functions
written in plpgsql.
I don't really know for sure yet if it can handle all cases and give the
exact same results as it would without inverse transitions, but it
certainly fixes the error case which was presented

Using the attached on HEAD of
https://github.com/david-rowley/postgres/commits/invtrans

explain (analyze, verbose)
select mysum(v) over (order by i rows between current row and unbounded
following) from (values(1,1e20),(2,1)) b(i,v);

Gives me the expected results of 1e20 and 1, instead of my original attempt
which gave 1e20 and 0.

I guess the extra tracking on forward transition might mean this would not
be practical to implement in C for sum(float), but I just wanted to run the
idea through a few heads to see if anyone can present a case where it can
still produce wrong results.

If it seems sound enough, then I may implement it in C to see how much
overhead it adds to forward aggregation for floating point types, but even
if it did add too much overhead to forward aggregation it might be worth
allowing aggregates to have 2 forward transition functions and if the 2nd
one exists then it could be used in windowing functions where the frame
does not have "unbounded following".

Any thoughts?

Regards

David Rowley