Tom Lane <tgl@xxxxxxxxxxxxx> writes: > Martijn van Oosterhout <kleptog@xxxxxxxxx> 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
