Re: SQL:2003 Window Functions for postgresql 8.3?

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Martijn van Oosterhout <kleptog(at)svana(dot)org> writes:
> > The main thing I want to use them for is for cumulative output.
> > ...
> > With window functions you define for each row a "window" which is from
> > the beginning of the table to that row and then sum the values, for
> > each row. Then you just divide by the total, nice.
>
> Egad. Wouldn't that involve O(N) memory and O(N^2) operations?
> Perhaps an extremely smart optimizer could improve this using knowledge
> of the specific aggregates' behaviors, but for "black box" aggregates
> it sounds pretty unworkable.

Yeah when I looked at it it seemed like it would in general require O(n) or
O(n^2) in either time or space. In particular you can have the windows be
ordered and ordered in a different order for each window function. So for
example you could generate the dense_rank for a list of people according to
various metrics both within their group and overall in a single query. I
couldn't see how the database could do that other than storing up the whole
group and sorting it n different ways and then somehow doing some kind of join
before proceeding to the next group.

I'm not sure if the spec is designed around the assumption that programmers
would be clever about writing things that the database could optimize or if it
was designed around the idea that programmers wouldn't care about O(n^2)
performance because they would just spend $^2 on hardware.

--
greg