Waiting for 9.5 – Support GROUPING SETS, CUBE and ROLLUP.

On 16th of May, Andres Freund committed patch:

Support GROUPING SETS, CUBE and ROLLUP.
 
This SQL standard functionality allows to aggregate data by different
GROUP BY clauses at once. Each grouping set returns rows with columns
grouped by in other sets set to NULL.
 
This could previously be achieved by doing each grouping as a separate
query, conjoined by UNION ALLs. Besides being considerably more concise,
grouping sets will in many cases be faster, requiring only one scan over
the underlying data.
 
The current implementation of grouping sets only supports using sorting
for input. Individual sets that share a sort order are computed in one
pass. If there are sets that don't share a sort order, additional sort &
aggregation steps are performed. These additional passes are sourced by
the previous sort step; thus avoiding repeated scans of the source data.
 
The code is structured in a way that adding support for purely using
hash aggregation or a mix of hashing and sorting is possible. Sorting
was chosen to be supported first, as it is the most generic method of
implementation.
 
Instead of, as in an earlier versions of the patch, representing the
chain of sort and aggregation steps as full blown planner and executor
nodes, all but the first sort are performed inside the aggregation node
itself. This avoids the need to do some unusual gymnastics to handle
having to return aggregated and non-aggregated tuples from underlying
nodes, as well as having to shut down underlying nodes early to limit
memory usage.  The optimizer still builds Sort/Agg node to describe each
phase, but they're not part of the plan tree, but instead additional
data for the aggregation node. They're a convenient and preexisting way
to describe aggregation and sorting.  The first (and possibly only) sort
step is still performed as a separate execution step. That retains
similarity with existing group by plans, makes rescans fairly simple,
avoids very deep plans (leading to slow explains) and easily allows to
avoid the sorting step if the underlying data is sorted by other means.
 
A somewhat ugly side of this patch is having to deal with a grammar
ambiguity between the new CUBE keyword and the cube extension/functions
named cube (and rollup). To avoid breaking existing deployments of the
cube extension it has not been renamed, neither has cube been made a
reserved keyword. Instead precedence hacking is used to make GROUP BY
cube(..) refer to the CUBE grouping sets feature, and not the function
cube(). To actually group by a function cube(), unlikely as that might
be, the function name has to be quoted.
 
Needs a catversion bump because stored rules may change.
 
Author: Andrew Gierth and Atri Sharma, with contributions from Andres Freund
Reviewed-By: Andres Freund, Noah Misch, Tom Lane, Svenne Krap, Tomas
    Vondra, Erik Rijkers, Marti Raudsepp, Pavel Stehule
Discussion: CAOeZVidmVRe2jU6aMk_5qkxnB7dfmPROzM7Ur8JPW5j8Y5X-Lw@mail.gmail.com

This looks complicated. So, let's try to dig through the words into actual usecases.

It looks that for really seeing the functionality, I will need some data.

So, let's use some random values, with some db-related schema:

$ CREATE TABLE db_details (
    appnumber int4,
    DAY DATE,
    inserts int8,
    updates int8,
    deletes int8,
    transactions int8,
    PRIMARY KEY (appnumber, DAY)
);
CREATE TABLE
 
$ CREATE SEQUENCE x INCREMENT BY 7;
CREATE SEQUENCE
 
$ INSERT INTO db_details
SELECT
    i,
    j,
    NEXTVAL('x'),
    NEXTVAL('x'),
    NEXTVAL('x'),
    NEXTVAL('x')
FROM
    generate_series(1,3) i,
    generate_series(now() - '2 days'::INTERVAL, now(), '1 day'::INTERVAL) j;
INSERT 0 9
 
$ DROP SEQUENCE x;
DROP SEQUENCE
 
$ SELECT * FROM db_details;
 appnumber |    DAY     | inserts | updates | deletes | transactions 
-----------+------------+---------+---------+---------+--------------
         1 | 2015-05-19 |       1 |       8 |      15 |           22
         1 | 2015-05-20 |      29 |      36 |      43 |           50
         1 | 2015-05-21 |      57 |      64 |      71 |           78
         2 | 2015-05-19 |      85 |      92 |      99 |          106
         2 | 2015-05-20 |     113 |     120 |     127 |          134
         2 | 2015-05-21 |     141 |     148 |     155 |          162
         3 | 2015-05-19 |     169 |     176 |     183 |          190
         3 | 2015-05-20 |     197 |     204 |     211 |          218
         3 | 2015-05-21 |     225 |     232 |     239 |          246
(9 ROWS)

now that I have my test data in place, let's see what I can do with this new functionality.

There are 3 parts in here, so let's start with the simplest – GROUPING SETS.

With the data above, I can quickly check how many inserts/updates/deletes/transaction where there for any given app:

$ SELECT appnumber, SUM(inserts), SUM(updates), SUM(deletes), SUM(transactions)
FROM db_details
GROUP BY appnumber;
 appnumber | SUM | SUM | SUM | SUM 
-----------+-----+-----+-----+-----
         1 |  87 | 108 | 129 | 150
         3 | 591 | 612 | 633 | 654
         2 | 339 | 360 | 381 | 402
(3 ROWS)

I can also check the same thing by day:

$ SELECT DAY, SUM(inserts), SUM(updates), SUM(deletes), SUM(transactions)
FROM db_details
GROUP BY DAY;
    DAY     | SUM | SUM | SUM | SUM 
------------+-----+-----+-----+-----
 2015-05-20 | 339 | 360 | 381 | 402
 2015-05-21 | 423 | 444 | 465 | 486
 2015-05-19 | 255 | 276 | 297 | 318
(3 ROWS)

But getting both stats would require multiple queries (or complicated single query).

The major problem with multiple queries is that it would have to scan the table twice. Which is of course not an issue with 9 rows, but when your input data is 100,000,000 rows, it might get hairy.

Grouping sets allow me to specify multiple groupings in single query. Let's see how it looks:

$ SELECT
    appnumber,
    DAY,
    SUM(inserts),
    SUM(updates),
    SUM(deletes),
    SUM(transactions)
FROM
    db_details
GROUP BY GROUPING SETS ( appnumber, DAY );
 appnumber |    DAY     | SUM | SUM | SUM | SUM 
-----------+------------+-----+-----+-----+-----
         1 | [NULL]     |  87 | 108 | 129 | 150
         2 | [NULL]     | 339 | 360 | 381 | 402
         3 | [NULL]     | 591 | 612 | 633 | 654
    [NULL] | 2015-05-19 | 255 | 276 | 297 | 318
    [NULL] | 2015-05-20 | 339 | 360 | 381 | 402
    [NULL] | 2015-05-21 | 423 | 444 | 465 | 486
(6 ROWS)

Wow – we have both groupings calculated with one query.

In case given column doesn't make sense in given grouping (like appnumber when grouping by day) – it is filled with null values.

What's also cool, I can add empty grouping, which gives me total:

$ SELECT
    appnumber,
    DAY,
    SUM(inserts)
FROM
    db_details
GROUP BY GROUPING SETS ( (appnumber), (DAY), () );
 appnumber |    DAY     | SUM  
-----------+------------+------
         1 | [NULL]     |   87
         2 | [NULL]     |  339
         3 | [NULL]     |  591
    [NULL] | [NULL]     | 1017
    [NULL] | 2015-05-19 |  255
    [NULL] | 2015-05-20 |  339
    [NULL] | 2015-05-21 |  423
(7 ROWS)

In here, we got another row, with (appnumber, day) being (null, null), which simply contains sum(inserts) over all rows.

At this moment, I realized that, to be able to show the cube/rollup things, I should have more dimentions than just two. And, I don't really need so many columns to sum. So let's redo the test table:

$ CREATE TABLE test (
    d1 text,
    d2 text,
    d3 text,
    v int4,
    PRIMARY KEY (d1, d2, d3)
);
CREATE TABLE
 
$ INSERT INTO test
SELECT
    a, b, c,
    CAST( random() * 50 AS int4)
FROM
    (VALUES ('a'),('b') ) AS d1(a),
    (VALUES ('c'),('d') ) AS d2(b),
    (VALUES ('e'),('f') ) AS d3(c)
;
INSERT 0 8
 
$ SELECT * FROM test;
 d1 | d2 | d3 | v  
----+----+----+----
 a  | c  | e  |  4
 a  | c  | f  | 14
 a  | d  | e  |  8
 a  | d  | f  | 49
 b  | c  | e  | 42
 b  | c  | f  | 30
 b  | d  | e  | 39
 b  | d  | f  | 27
(8 ROWS)

Three dimensions should be enough.

As you perhaps noticed, in previous example, I used:

GROUPING SETS ( (appnumber), (day), () )

I used parentheses because I wanted to add empty grouping set, but you should know that you can also have multi-column sets. Like here:

$ SELECT
    d1, d2, d3,
    SUM(v)
FROM
    test
GROUP BY GROUPING sets ( (d1), (d2, d3) );
   d1   |   d2   |   d3   | SUM 
--------+--------+--------+-----
 a      | [NULL] | [NULL] |  75
 b      | [NULL] | [NULL] | 138
 [NULL] | c      | e      |  46
 [NULL] | c      | f      |  44
 [NULL] | d      | e      |  47
 [NULL] | d      | f      |  76
(6 ROWS)

We got two first rows because of grouping set (d1), and four more rows because of grouping (d2, d3).

I assume that it is all clear for now.

Now, let's assume we'd want to group by all possible combinations of (d1, d2, d3). Enumerating them:

(d1,d2,d3)
(d1,d2 )
(d1, d3)
( d2,d3)
(d1 )
( d2 )
( d3)
( )

Is tedious. Here comes the CUBE() part. Instead of listing all possible options, I can simply:

$ SELECT
    d1, d2, d3,
    SUM(v)
FROM
    test
GROUP BY cube( d1, d2, d3 );
   d1   |   d2   |   d3   | SUM 
--------+--------+--------+-----
 a      | c      | e      |   4
 a      | c      | f      |  14
 a      | c      | [NULL] |  18
 a      | d      | e      |   8
 a      | d      | f      |  49
 a      | d      | [NULL] |  57
 a      | [NULL] | [NULL] |  75
 b      | c      | e      |  42
 b      | c      | f      |  30
 b      | c      | [NULL] |  72
 b      | d      | e      |  39
 b      | d      | f      |  27
 b      | d      | [NULL] |  66
 b      | [NULL] | [NULL] | 138
 [NULL] | [NULL] | [NULL] | 213
 a      | [NULL] | e      |  12
 b      | [NULL] | e      |  81
 [NULL] | [NULL] | e      |  93
 a      | [NULL] | f      |  63
 b      | [NULL] | f      |  57
 [NULL] | [NULL] | f      | 120
 [NULL] | c      | e      |  46
 [NULL] | c      | f      |  44
 [NULL] | c      | [NULL] |  90
 [NULL] | d      | e      |  47
 [NULL] | d      | f      |  76
 [NULL] | d      | [NULL] | 123
(27 ROWS)

That's a lot of rows, but quick check validates that all groupings are there.

So, CUBE(a,b,c) will work the same as GROUPING SETS ( (all), (possible), (combinations), (of), (a), (b), (and), (c) )

Of course, as previously, you can use CUBE with multi-column elements. Like:

CUBE( (d1), (d2, d3) )

This will generate grouping sets:

( (d1), (d2,d3) )
( (d1) )
( (d2,d3) )
( () )

Pretty cool, isn't it?

Now, the ROLLUP. If you understand CUBE(), then ROLLUP is simple, as it also generates GROUPING SETS, but only by removing elements from ROLLUP args.

That is – call: ROLLUP( d1, d2, d3 ), will generate GROUPING SETS:

( d1, d2, d3 )
( d1, d2 )
( d1 )
( )

So far, so good.

To wrap information about what you can put in GROUP BY clause, I have to note that you can put multiple elements there, like:

GROUP BY d1, cube(d2, d3);

(I could have added more, but that's irrelevant for now).

In such case, it works by making grouping sets by “cross joining" all possible GROUP BY elements.

So, we have two elements:

d1 – which is just single plain column
cube(d2,d3) – which becomes GROUPING SETS ( (d2,d3), (d2), (d3), () )

After doing “cross join", we simply get grouping sets:

( d1, d2, d3 )
( d1, d2 )
( d1, d3 )
( d1 )

Hope that it's clear.

One final thing to mention is “grouping()" function. This is (from what I can tell now) purely informational function. How it works? Let's see:

$ SELECT
    d1, d2, d3, GROUPING(d1, d2, d3), COUNT(*)
FROM
    test
GROUP BY
    CUBE( (d1), (d2, d3) )
ORDER BY 4
;
   d1   |   d2   |   d3   | GROUPING | COUNT 
--------+--------+--------+----------+-------
 a      | c      | e      |        0 |     1
 a      | c      | f      |        0 |     1
 a      | d      | e      |        0 |     1
 a      | d      | f      |        0 |     1
 b      | c      | e      |        0 |     1
 b      | c      | f      |        0 |     1
 b      | d      | e      |        0 |     1
 b      | d      | f      |        0 |     1
 a      | [NULL] | [NULL] |        3 |     4
 b      | [NULL] | [NULL] |        3 |     4
 [NULL] | d      | f      |        4 |     2
 [NULL] | c      | e      |        4 |     2
 [NULL] | c      | f      |        4 |     2
 [NULL] | d      | e      |        4 |     2
 [NULL] | [NULL] | [NULL] |        7 |     8
(15 ROWS)

Value in grouping column is a bitfield, where “0" on any given position means that given field is used in current grouping, and 1 means that it's not being used.

Is it hard to understand? Let's try to unpack the integer into 3 binary digits (3 because there are 3 possible columns):

$ SELECT
    d1, d2, d3, GROUPING(d1, d2, d3)::bit(3), COUNT(*)
FROM
    test
GROUP BY
    CUBE( (d1), (d2, d3) )
ORDER BY 4
;
   d1   |   d2   |   d3   | GROUPING | COUNT 
--------+--------+--------+----------+-------
 a      | c      | e      | 000      |     1
 a      | c      | f      | 000      |     1
 a      | d      | e      | 000      |     1
 a      | d      | f      | 000      |     1
 b      | c      | e      | 000      |     1
 b      | c      | f      | 000      |     1
 b      | d      | e      | 000      |     1
 b      | d      | f      | 000      |     1
 a      | [NULL] | [NULL] | 011      |     4
 b      | [NULL] | [NULL] | 011      |     4
 [NULL] | d      | f      | 100      |     2
 [NULL] | c      | e      | 100      |     2
 [NULL] | c      | f      | 100      |     2
 [NULL] | d      | e      | 100      |     2
 [NULL] | [NULL] | [NULL] | 111      |     8
(15 ROWS)

Now, it should be clearer. 1 in any position in grouping means that this particular row was made using grouping set that didn't include this column – hence the nulls in d1, d2 or d3 columns.

You could say that the same information can be obtained by simply checking which columns are null, but then – some real-life data can contain nulls, and this would throw your heuristics off.

In any way – to be honest, the feature looked much more complex than it really is (from the standpoint of user, not pg developer). I seem to understand it pretty well now (which I can't say about ordered/hypothetical sets).

Anyway – thanks a lot guys, I (and I guess that not only me) really appreciate your work on this.

8 thoughts on “Waiting for 9.5 – Support GROUPING SETS, CUBE and ROLLUP.”

Tony says:

2015-05-24 at 07:13

WOW, very nice!!! +10
akretschmer says:

2015-05-24 at 08:38

Thx for the explanation.
Glyn says:

2015-05-28 at 17:05

10 out of 10 for that explanation, thanks!
Anonymous says:

2015-08-02 at 09:50

Well explained!
Justin says:

2015-12-19 at 06:22

Excellent as always, Depesz. Thanks!
Monalee Bhandge says:

2016-05-23 at 14:40

Superb….Explanation!
Anonymous says:

2016-11-11 at 09:27

Good one,,, Thanks for sparing your time.
laurent says:

2017-07-30 at 04:57

thanks a lot for that post

Comments are closed.