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

On Jan25, 2014, at 09:50 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> On Thu, Jan 23, 2014 at 1:57 PM, Florian Pflug <fgp(at)phlo(dot)org> wrote:
>> On Jan23, 2014, at 01:17 , David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>> > On Wed, Jan 22, 2014 at 12:46 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:
>> >> If you want to play with
>> >> this, I think the first step has to be to find a set of guarantees that
>> >> SUM(float) is supposed to meet. Currently, SUM(float) guarantees that if the
>> >> summands all have the same sign, the error is bound by C * N, where C is some
>> >> (machine-specific?) constant (about 1e-15 or so), and N is the number of input
>> >> rows. Or at least so I think from looking at SUMs over floats in descending
>> >> order, which I guess is the worst case. You could, for example, try to see if
>> >> you can find a invertibility conditions which guarantees the same, but allows
>> >> C to be larger. That would put a bound on the number of digits lost by the new
>> >> SUM(float) compared to the old one.
>> >
>> > I guess if the case is that normal (non-window) sum(float) results are undefined
>> > unless you add an order by to the aggregate then I guess there is no possible
>> > logic to put in for inverse transitions that will make them behave the same as
>> > an undefined behaviour.
>>
>> Actually, if sum(float) was really undefined, it'd be *very* easy to provide an
>> inverse transition function - just make it a no-op. Heck, you could then even
>> make the forward transition function a no-op, since the very definition of
>> "undefined behaviour" is "result can be anything, including setting your house
>> on fire". The point is, it's *not* undefined - it's just imprecise. And the
>> imprecision can even be quantified, it just depends on the number of
>> input rows (the equal-sign requirement is mostly there to make "imprecision"
>> equivalent to "relative error").
>
> My apologies, I meant to use the term nondeterministic rather than undefined.
> There's really not any need that I can see to turn things silly here.

I wasn't trying to be absurd, I was trying to get a point across.

> My point was more that since sum(float) can give different results if it used
> an index scan rather than a seq scan, trying to get the inverse transition to
> match something that gives varying results sounds like a tricky task to take on.

You don't have to match it digit-by-digit! In that I fully agree with Kevin -
floats are *always* an approximation, and so is thus SUM(float). Summarization
order is BTW not the only source of non-determinism for SUM(float) - the exact
result can very between architectures, and for some architectures between
compilers. (Intel is one of these, due to their 80-bit extended precision format
that gets truncated to 64-bit when stored to main memory).

But in a large number of cases, they won't vary by *much*, which is *the* reason
why SUM(float) is *not* totally useless. And reasoning about SUM(float) which
ignores that by simply calling it "non-deterministic", "undefined" or whatever,
without any quantification of the possible error, has thus zero chance of
leading to interesting conclusions.

>> Secondly, you'd really need a second aggregate definition - usually, the
>> non-invertible aggregate will get away with a much smaller state representation.
>> Aggregates with state type "internal" could hack their way around that by
>> simply not using the additional parts of their state structure, but e.g.
>> plpgsql aggregates would still incur overhead due to repeated copying of
>> a unnecessary large state value. If it's possible to represent the
>> forward-only but not the invertible state state with a copy-by-value type,
>> that overhead could easily be a large part of the total overhead you paid
>> for having an inverse transition function.
>
> I had imagined they keep the same state type and don't use any extra variables
> that are defined for the forward transition function that is invertible.

Yeah, and the above explains that at least for non-C-language aggregates,
passing around that unnecessarily large state may very well prove to be the
source of a large part, if not almost all, of the overhead. So having just
a separate forward transition function will buy you almost nothing or some
cases.

I just tried this. I defined two aggregates mymax(int4) and myfastmax(int4),
both with just a forward transition function, both SQL-language functions.
mymax uses a composite type for the state containing an int4 field holding
the current maximum, and a dummy int8 field. myfastmax uses a plain int4
for the state, holding the current maximum. Both forward transition
functions essentially do

case when current_max > v then current_max else v end

On my laptop, computing the maximum of 1e6 rows takes about 4.5 seconds with
myfastmax and 7.8 seconds with mymax. If make mymax's transition function
increment the dummy field on every transition, the time increases from 7.8
to 8.2 seconds. So here, using a composite type for the state accounts for
about 3.3 seconds, or 40%, of the total runtime of 9 seconds, whereas the
increment costs about 0.4 seconds or 5% of the total runtime.

>> And lastly, we could achieve much of the benefit of a second transition
>> function by simply telling the forward transition function whether to
>> expect inverse transition function calls. We already expose things like
>> the aggregation memory context to C-language transition functions, so the
>> basic mechanism is already there. In fact, I pondered whether to do this -
>> but then figured I'd leave it to however needs that facility first. Though
>> it wouldn't be much code - basically, setting a flag in the WindowAggState,
>> and exporting a function to be used by aggregates to read it, similar
>> to what AggCheckCallContext does.
>
> Sounds like a good idea, but what would the solution aggregate transition
> functions that are not written in C?

See above - non-C aggregates are exactly the ones that benefit least from
a specialized non-invertible forward transition function, because the have
to serialize and deserialize the state type on every transition...

best regards,
Florian Pflug