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

On Sun, Jan 19, 2014 at 3:22 AM, Florian Pflug <fgp(at)phlo(dot)org> wrote:

>
> BTW, this made me realize that MIN and MAX currently have the same issue -
> they'll rescan if the inputs are all equal. We could avoid that by doing
> what
> you did with dscale - track the number of times we've seen the maximum. I
> wonder if that would be worth it - it would, unfortunately, require use to
> use state type "internal" there too, and hence to add final functions for
> all
> the MIN/MAX aggregates. But that seems excessive. So for now, let's just
> live with that.
>
>
Yeah, it's an idea... I had actually talked a bit about it before when
first I posted about inverse transition functions.

http://www.postgresql.org/message-id/CAApHDvqu+yGW0vbPBb+yxHrPG5VcY_kiFYi8xmxFo8KYOczP3A@mail.gmail.com

But I've only realised today that it might be a no go. Let me explain...

I just finished implementing the inverse transition functions for bool_and
and bool_or, these aggregates had a sort operator which I assume would have
allowed an index scan to be performed, but since I had to change the first
argument of these aggregates to internal and that meant I had to get rid of
the sort operator... So I'm not actually sure that we really should
implement inverse transition functions for bool_and and bool_or because of
this. Never-the-less I commited a patch to the github repo which implements
them. I guess this sort operator problem completely writes off doing
something similar for MAX and MIN as that would mean no index scan would be
possible for these aggregates!

> If we really *do* want to optimize this case, we could
> come to it from a completely different angle. Aggregates already
> special-case
> MIN and MAX to be able to use an index to evalutate SELECT MAX(c) FROM t.
> If we provided a way for the transition function to call the sort operator
> specified by SORTOP in CREATE AGGREGATE, one generic triple of forward and
> inverse transition function and final function would work for all the
> MIN and MAX aggregates. But that's material for a separate patch for 9.5
>
> > Note that after this fix the results for my quick benchmark now look
> like:
> >
> > 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; -- 113 ms
> > select sum(num / 10) over(order by num rows between current row and
> unbounded following) from num; -- 156ms
> > select sum(num / 1) over(order by num rows between current row and
> unbounded following) from num; -- 144 ms
> >
> > So it seems to be much less prone to falling back to brute force forward
> > transitions.
> > It also seems the / 10 version must have had to previously do 1 brute
> > force rescan but now it looks like it can do it in 1 scan.
> >
> >>> 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.
> >>
> >> Dunno how many people SUM over numerics with different dscales. Easily
> >> possible that it's few enough to not be worth fussing over.
> >
> > Going by Tom's comments in the post above this is possible just by
> having an
> > unconstrained numeric column, but I guess there's still a good chance
> that
> > even those unconstrained numbers have the same scale or at least the
> scale
> > will likely not vary wildly enough to make us have to perform brute force
> > forward transitions for each row.
>
> Yeah, I'm convinced by now that your approach is the right trade-off there.
> Those who do have values with wildly different dscales in their columns can
> always add a cast to normalize them, if they experience a lot of restarts.
>
> So let's just add a sentence or two to the SUM(numeric) documentation about
> this, and be done.
>
>
I had a quick look and I couldn't decide the best place to write about
specific details on inverse transition functions. The best place I could
see was to add a note under the aggregates table here:
http://www.postgresql.org/docs/devel/static/functions-aggregate.html#FUNCTIONS-AGGREGATE-TABLE

> >
> > I did think of this when I wrote them. I thought that the removing 0
> case might
> > be quite common and worth it, but I thought the ~0 case would be less
> common,
> > but I just thought it was weird to do one without the other.
> > To do more tracking on these it looks like we'd need to change those
> aggregates
> > to use an state type that is internal and I think the extra tracking
> would mean
> > looping over a 8, 32 or 64 element array of int64's for each value, I
> just don't
> > think that would be a winner performance wise since the code that's
> there is
> > pretty much a handful of CPU cycles.
>
> Yeah, this is similar to the SUM(numeric) problem in that we *could* avoid
> all restarts, but the overhead of doing so is quite high. But whereas in
> the
> SUM(numeric) case we manage to reduce the overhead while still optimizing
> most
> cases, here I think we optimize nearly none. My vote is for dropping these
> functions entirely, but I don't feel particularly strongly about this...
>
>
Ok, I've reverted the patch which implemented the bitwise aggregate inverse
transition functions.

> >> It's probably far more worth it for the bool and/or aggregates. We
> could just
> >> keep track of the values aggregated and the count of values as "true"
> and return
> >> true if those are the same in the case of "AND", then check the true
> count
> >> is > 0 in the case of "OR". I'd feel more strongly to go and do that if
> I'd
> >> actually ever used those aggregates for anything.
>
> That, OTOH, would be worthwhile I think. I'll go do that, though probably
> not today. I hope to get to it sometime tomorrow.
>

I've commited a patch to the github repo to do this.
https://github.com/david-rowley/postgres/commit/121b0823753cedf33bb94f646df3176b77f28500
but I'm not sure if we can keep it as I had to remove the sort op as I
explained above.

>
> >> * Quite a few of the inverse transition functions are marked strict, yet
> >> contain code to handle NULL inputs. You can just remove that code -
> the system
> >> makes sure that strict functions never receive NULL arguments.
> Affected are,
> >> AFAICS numeric_accum_inv, numeric_avg_accum_inv, int2_accum_inv,
> >> int4_accum_inv, int8_accum_inv, int8_avg_accum_inv, int2_sum_inv,
> int4_sum_inv,
> >> int8_sum_inv. Not sure that list is exhaustive...
> >
> > Should be able to get a list from:
> > select proname,proisstrict from pg_proc where proisstrict = true and oid
> in(select
> > agginvtransfn from pg_aggregate);
> >
> > I might not have time for this today though, so if you feel like
> checking these
> > that would be really helpful.
>
> Yeah, I'll do that, also tomorrow hopefully.
>

I think I beat you to it.But I'm not quite sure what to do
in numeric_avg_accum_inv() where it does:
if (state == NULL)
state = makeNumericAggState(fcinfo, false);

Perhaps we should just add an Assert(state != NULL); here, since we
shouldn't be calling inverse transitions without actually calling the
transition function, and the transition function should initialise the
state. I think this is valid as we can't actually call that function
manually because of the internal type. So it won't be possible to cause an
assert failure by doing select numeric_avg_accum_inv(NULL,20);

>
> >> * For any of the new inverse transition functions, I'd be inclined to
> just
> >> elog() if they're called directly and not as an aggregate. In
> particular
> >> those which check for that anyway, plus the *smaller_inv and
> *larger_inv
> >> ones. I don't see why anyone would ever want to call these directly -
> and
> >> if we elog() now, we can easy change these functions later, because no
> external
> >> code can depend on them. E.g., maybe someone wants to keep the top N
> elements
> >> in the MIN/MAX aggregates one day...
> >
> > Yeah I guess the way it is now may mean we'd need to support legacy
> functions
> > for ever and a day if we changed the way they worked, but I'm not sure
> if adding
> > a check to see if it was used in an aggregate function changes that, as
> a user
> > could be using the built in function in their own user defined
> aggregate, so
> > there could still be complaints if we removed them from a major version.
> What
> > would be needed is some way to have functions internally but publish
> these
> > functions to the user, say only visible from initdb or something. I
> don't think
> > that's part of this patch though. Maybe just the fact that they're
> undocumented
> > helps give them more ability to be removed later.
>
> Hm, true. Still, I think I'd prefer us to elog() for those new functions
> which
> explicitly check whether there's an aggregation context anyway. Can do
> that if you
> want.
>
>
I've not done this yet, but may look at it later. I'd quite like a 2nd
opinion on it before I go and implement this as I'm not quite sure of what
value it will bring. I don't think it means that one day we can remove
these functions if we find a better way of doing things as there it would
still be possible to use them in a user defined aggregate. It just probably
narrows the chances, but it does stick a small overhead in each function to
test for this.

> >> * The number of new regression tests seems a bit excessive. I don't
> think there
> >> really a policy what to test and what not, but in this case I think it
> suffices
> >> if we test the basic machinery, plus the more complex functions. But
> e.g. most
> >> of the SUM and AVG aggregates use numeric_accum or numeric_avg_accum
> internally,
> >> and the wrapper code basically just does datatype conversion, so
> testing a few
> >> cases seems enough there. What I think we *should* test, but don't do
> currently,
> >> is whether the core machinery performs the expected calls of the
> forward and
> >> reverse transition function. I was thinking about creating an
> aggregate in the
> >> regression tests which simply concatenates all the calls into a
> string, e.g.
> >> you might get "F:1 F:2 F:3 I:1" if we aggregated 1,2,3 and then
> removed 1.
> >> I think that should be possible with an SQL-language forward and
> inverse
> >> transfer function, but I haven't tried. I can try, if you want.
> >
> > I agree that there are quite a lot of tests and I think that's why I
> took a different
> > approach when it came to all this little *larger_inv and smaller_inv
> functions, there
> > were just so many! I thought the aggregate tests would run in the blank
> of a eye
> > anyway, but perhaps I should consider other things than just processing
> time. I
> > created most of the aggregate call tests by writing a whole load of
> queries on an
> > unpatched version then ran the tests and took the output of that as my
> expected
> > results for my patched copy. These were really useful to check for
> regression when
> > I was working hard on nodeWindowAgg.c. I'd find it hard to pick and
> choose what to
> > remove giving that they all test something slightly different, even if
> it's just a
> > different final function. They did pick up some failures earlier when I
> forgot to
> > change the strict property on int8_avg_accum_inv. Maybe someone else has
> an opinion
> > on that the number of tests?
>
> I think the basic guideline for whether to test something in the
> regression test or
> not is not so much "did it catch an error during development", but rather
> "could this
> catch errors inadvertedly introduced later". That's not to say you
> shouldn't use
> more test during development - your procedure there's fine - the question
> is just
> whether to cut them down when the patch's done. For all these rather
> trivial inverse
> function, I think we can trust that if they work once, they're not going
> to break
> unless someone changes the function itself - they don't really have any
> outside
> dependencies. That's also what the window functions regression test does
> today, I
> think - it doesn't really test all possible cases exhaustively.
>
>
Ok, we can think about that later then. I don't want to remove any just
yet, even if we think the patch is getting close another review from
someone else could mean it needs more big changes before it's ready to go.

> best regards,
> Florian Pflug
>
>