>>>>> "Robert" == Robert Haas <robertmh...@gmail.com> writes:
>> I would be interested in seeing more good examples of the size and >> type of grouping sets used in typical queries. Robert> From what I have seen, there is interest in being able to do Robert> things like GROUP BY CUBE(a, b, c, d) and have that be Robert> efficient. Yes, but that's not telling me anything I didn't already know. What I'm curious about is things like: - what's the largest cube(...) people actually make use of in practice - do people make much use of the ability to mix cube and rollup, or take the cross product of multiple grouping sets - what's the most complex GROUPING SETS clause anyone has seen in common use Robert> That will require 16 different groupings, and we really want Robert> to minimize the number of times we have to re-sort to get all Robert> of those done. For example, if we start by sorting on (a, b, Robert> c, d), we want to then make a single pass over the data Robert> computing the aggregates with (a, b, c, d), (a, b, c), (a, Robert> b), (a), and () as the grouping columns. In the case of cube(a,b,c,d), our code currently gives: b,d,a,c: (b,d,a,c),(b,d) a,b,d: (a,b,d),(a,b) d,a,c: (d,a,c),(d,a),(d) c,d: (c,d),(c) b,c,d: (b,c,d),(b,c),(b) a,c,b: (a,c,b),(a,c),(a),() There is no solution in less than 6 sorts. (There are many possible solutions in 6 sorts, but we don't attempt to prefer one over another. The minimum number of sorts for a cube of N dimensions is obviously N! / (r! * (N-r)!) where r = floor(N/2).) If you want the theory: the set of grouping sets is a poset ordered by set inclusion; what we want is a minimal partition of this poset into chains (since any chain can be processed in one pass), which happens to be equivalent to the problem of maximum cardinality matching in a bipartite graph, which we solve in polynomial time with the Hopcroft-Karp algorithm. This guarantees us a minimal solution for any combination of grouping sets however specified, not just for cubes. -- Andrew (irc:RhodiumToad) -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
