Implementation of GROUPING SETS (T431: Extended grouping capabilities)

In future i know how to implement ROLLUP more optimal (executor
iterator) and use this ROLLUP for optimisation another GROUP BY,
GROUPING SETS.

Thanks.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Hello

some other info is on  http://wiki.postgresql.org/wiki/Grouping_Sets

Maybe in e few weak I'll have some a prototype based on CTE. My older
technique based on hashed tables should be well, but it carry lot of
unshared code. Using CTE means so we can optimize CTE and GROUPING
SETS together. I plan to transform query

SELECT * FROM some GROUP BY GROUPING SETS(a, b)

to

WITH q AS (SELECT * FROM some)
 SELECT * FROM q GROUP BY a
 UNION ALL
 SELECT * FROM q GROUP BY b

2009/5/10 Олег Царев <zabivator@gmail.com>:

Hello all.
Please, approve my ideas for implementation.

Standart has feature T431: Extended grouping capabilities.
This feature i found in TODO-list:
http://wiki.postgresql.org/wiki/Todo -> SQL Commands -> TO DO

MS SQL 2005 partial support this feature:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
http://blogs.msdn.com/craigfr/archive/2007/09/21/aggregation-with-rollup.aspx

MS SQL 2008 support this feature:
http://blogs.msdn.com/craigfr/archive/2007/10/11/grouping-sets-in-sql-server-2008.aspx

Oracle support this feature:
http://www.compshack.com/sql/oracle-group-rollup

So, it's short notes about GROUPING SETS, but more complete
information have in a official documentation of MS SQL and Oracle
(copyright limited for send as attach).

First. GROUPG SETS.

select A,B,C,SUM(D) from table group by GROUPING SETS( (A,B,C), (A),
() ) - it's example of use grouping sets.
Semantic of this construction - make group by over source more, than
one group of column.
It's very wide key - A,B C. In result set of this example we can find
result set of select   select A,B,C,SUM(D) from table group by A,B,C -
as subset. It's mind: "GROUP BY A,B,C" - subset of "GROUP BY GROUPING
SETS( (A,B,C), (A), () )
Two subset - is GROUP BY A B, and instead C column we look NULL.
Third subset - GROUP BY (), instead A,B,C - NULL, one row - it's name
"GRAND TOTAL". - calculate over all subset without grouping

Also have function "GROUPING"  it's function say about null - "real
null" (from table) or generated by "GROUP BY GROUPING SETS"

My point: this feature can implement over GROUP BY and UNION ALL
We can make decomposition of "GROUP BY GROUPING SETS( (A,B,C),(A),()
)" to  select A,B,C fron table GROUP BY A,B,C .UNION  ALL select
A,B,NULL from table group BY A,B UNION ALL NUll,NUll,NULL from table
group by();

So, it's very simple, don't require modification of executor and
callibrate cost - only parser and semantic anylysis,
'
So, ROLLUP(A1,...An) is alias to "GROUP BY GROUPING SETS(
(A1,...,An),(A1,...,An-1),... (An-1,An),(An),() ),
CUBE - analogue.

If this idea it's good -  i can write code base on old patch
http://archives.postgresql.org/pgsql-hackers/2008-10/msg00838.php or
from clean list (as you wish).

This is suboptimal. When SELECT * FROM X GROUP BY GROUPING SETS ...,
where X is some joined data, then you repeat JOIN on every grouping
set. So your solution is simple for implementation, but it should be
really slow.

Regards
Pavel Stehule

In future i know how to implement ROLLUP more optimal (executor
iterator) and use this ROLLUP for optimisation another GROUP BY,
GROUPING SETS.

Thanks.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Look for MS SQL:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
Why MS SQL don't support distinct aggregations? I think - because
every distinct aggregations in MS SQL require hash, and many
aggregations - it's so slow.

Thank you!
2009/5/10 Pavel Stehule <pavel.stehule@gmail.com>:

Hello

some other info is on  http://wiki.postgresql.org/wiki/Grouping_Sets

Maybe in e few weak I'll have some a prototype based on CTE. My older
technique based on hashed tables should be well, but it carry lot of
unshared code. Using CTE means so we can optimize CTE and GROUPING
SETS together. I plan to transform query

SELECT * FROM some GROUP BY GROUPING SETS(a, b)

to

WITH q AS (SELECT * FROM some)
 SELECT * FROM q GROUP BY a
 UNION ALL
 SELECT * FROM q GROUP BY b

2009/5/10 Олег Царев <zabivator@gmail.com>:

Hello all.
Please, approve my ideas for implementation.

Standart has feature T431: Extended grouping capabilities.
This feature i found in TODO-list:
http://wiki.postgresql.org/wiki/Todo -> SQL Commands -> TO DO

MS SQL 2005 partial support this feature:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
http://blogs.msdn.com/craigfr/archive/2007/09/21/aggregation-with-rollup.aspx

MS SQL 2008 support this feature:
http://blogs.msdn.com/craigfr/archive/2007/10/11/grouping-sets-in-sql-server-2008.aspx

Oracle support this feature:
http://www.compshack.com/sql/oracle-group-rollup

So, it's short notes about GROUPING SETS, but more complete
information have in a official documentation of MS SQL and Oracle
(copyright limited for send as attach).

First. GROUPG SETS.

select A,B,C,SUM(D) from table group by GROUPING SETS( (A,B,C), (A),
() ) - it's example of use grouping sets.
Semantic of this construction - make group by over source more, than
one group of column.
It's very wide key - A,B C. In result set of this example we can find
result set of select   select A,B,C,SUM(D) from table group by A,B,C -
as subset. It's mind: "GROUP BY A,B,C" - subset of "GROUP BY GROUPING
SETS( (A,B,C), (A), () )
Two subset - is GROUP BY A B, and instead C column we look NULL.
Third subset - GROUP BY (), instead A,B,C - NULL, one row - it's name
"GRAND TOTAL". - calculate over all subset without grouping

Also have function "GROUPING"  it's function say about null - "real
null" (from table) or generated by "GROUP BY GROUPING SETS"

My point: this feature can implement over GROUP BY and UNION ALL
We can make decomposition of "GROUP BY GROUPING SETS( (A,B,C),(A),()
)" to  select A,B,C fron table GROUP BY A,B,C .UNION  ALL select
A,B,NULL from table group BY A,B UNION ALL NUll,NUll,NULL from table
group by();

So, it's very simple, don't require modification of executor and
callibrate cost - only parser and semantic anylysis,
'
So, ROLLUP(A1,...An) is alias to "GROUP BY GROUPING SETS(
(A1,...,An),(A1,...,An-1),... (An-1,An),(An),() ),
CUBE - analogue.

If this idea it's good -  i can write code base on old patch
http://archives.postgresql.org/pgsql-hackers/2008-10/msg00838.php or
from clean list (as you wish).

This is suboptimal. When SELECT * FROM X GROUP BY GROUPING SETS ...,
where X is some joined data, then you repeat JOIN on every grouping
set. So your solution is simple for implementation, but it should be
really slow.

Regards
Pavel Stehule

In future i know how to implement ROLLUP more optimal (executor
iterator) and use this ROLLUP for optimisation another GROUP BY,
GROUPING SETS.

Thanks.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

2009/5/10 Олег Царев <zabivator@gmail.com>:

Hello, Pavel.

I read you letter, and found some points:

a) Simple transformation any GROUPING SETS in GROUP BY + UNION ALL
require clone source for every group.
It's so slow.
My point: we can make for start simple implementation.
b) Your sollution it's so good, IMHO
WITH q AS (SELECT * FROM some)
 SELECT * FROM q GROUP BY a
 UNION ALL
 SELECT * FROM q GROUP BY b
But can you describe me how it's used on planner (calculate cost) and exector.

look on CTE source code or ask to CTE author.

Sharing source - it's mind - we don't process tree, we process
DIRECTED GRAPH. Hard, many bugs, so on, not?

for example - code for DISTINCT is shared with code for aggregation.
My idea is based on similarity

GROUPING SETS is subset of CTE, nonrecursive CTE is subset of UNION ALL

PostgreSQL support sharing nodes of executor? How? Where i can read?

I don't know, what do you thing exactly sharing nodes? Before CTE I
had to write special holder node, but it isn't necessary now.

Next. Ok, we spool source. After we use simple hash group/sort group +
union all? Or more advanced techniques?  If different group by - it's
not different from my idea, it's logic additional (spool source for
fast rewind)

I thing so trivial implementation via UNION ALL should work, but any
optimisations means lot of work - and when you add rewind
functionality, you will got trivial nonrecursive CTE implementation.
When I wrote patch, there wasn't possible an use CTE, so I played wit
own nodes. Now, the more clean solution is probably based on current
CTE base.

c) Don't forget also about node requiments - if we use hash table as
container for source -  we reduce some sorting properties - and query
select A,B from TABLE group by ((A,B),(B)) order by a,b require
sorting on output of grouping sets.
It's mind - we need insert sort.

Yes, probably there should be possible some techniques - that should
to eliminate final sort op. I am not sure if it is really important.
Now I thinking what is the bigger devil a) patch complexity b) some
suboptimality  (mainly redundant call of agg nodes). For me a.
Aggregates are not gratis, but significantly more expensive is
repeated seq data scan. So it is first goal. Later we should to thing
about next optimalizations.

d) We can make SORT ROLLUP and SORT REDUCE ROLLUP.
first - sort group by use sorting for grouping data and calculate aggregations.
So, 'order by A,B,C' also 'order by A,B' also order by 'A' also order by ''
What it's mind? It's mind we can use sort features for implement SORT
ROLLUP. For every sub group we calculate self aggregates... oh, i bad
say. Look on "select a,sum(b) from table group by a".  Sort group
grouping by a, and for every a-group calculate aggregations (sum), for
ROLLUP A,B we can make three aggregations ; for A,B than A than () -
and use one path on source calculate aggregations on every step, and
for split source on different subsets.
It's more perfomance, than different group by and union all.

Maybe, I don't know. What I know:

* UNION ALL will have better result on indexed sets and MIN, MAX
aggregates. CTE isn't optimized now for these cases.
* UNION ALL will be slow for large sets (over cache),
* CTE needs some more optimalizations,
* pg core hackers dislike big and complex patches,
* pg core hackers like any improved current code base.

I am thinking so Grouping Sets based on CTE should be more commitable
code. It doesn't mean so your ideas are wrong, but these
optimalization should to work on CTE too.

select * from table group by rollup(a,b,c)

have to have generate same plan as

with q as (select * from table)
 select * from q group by a,b,c
 union all
 select * from q group by a,b
 union all
 select * from q group by a
 union all
 select * from q;

and CTE is more general then Grouping Sets, so it is better do
optimalization over CTE than Grouping Sets.

Regards
Pavel Stehule

Look for MS SQL:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
Why MS SQL don't support distinct aggregations? I think - because
every distinct aggregations in MS SQL require hash, and many
aggregations - it's so slow.

Thank you!
2009/5/10 Pavel Stehule <pavel.stehule@gmail.com>:

Hello

some other info is on  http://wiki.postgresql.org/wiki/Grouping_Sets

Maybe in e few weak I'll have some a prototype based on CTE. My older
technique based on hashed tables should be well, but it carry lot of
unshared code. Using CTE means so we can optimize CTE and GROUPING
SETS together. I plan to transform query

SELECT * FROM some GROUP BY GROUPING SETS(a, b)

to

WITH q AS (SELECT * FROM some)
 SELECT * FROM q GROUP BY a
 UNION ALL
 SELECT * FROM q GROUP BY b

2009/5/10 Олег Царев <zabivator@gmail.com>:

Hello all.
Please, approve my ideas for implementation.

Standart has feature T431: Extended grouping capabilities.
This feature i found in TODO-list:
http://wiki.postgresql.org/wiki/Todo -> SQL Commands -> TO DO

MS SQL 2005 partial support this feature:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
http://blogs.msdn.com/craigfr/archive/2007/09/21/aggregation-with-rollup.aspx

MS SQL 2008 support this feature:
http://blogs.msdn.com/craigfr/archive/2007/10/11/grouping-sets-in-sql-server-2008.aspx

Oracle support this feature:
http://www.compshack.com/sql/oracle-group-rollup

So, it's short notes about GROUPING SETS, but more complete
information have in a official documentation of MS SQL and Oracle
(copyright limited for send as attach).

First. GROUPG SETS.

select A,B,C,SUM(D) from table group by GROUPING SETS( (A,B,C), (A),
() ) - it's example of use grouping sets.
Semantic of this construction - make group by over source more, than
one group of column.
It's very wide key - A,B C. In result set of this example we can find
result set of select   select A,B,C,SUM(D) from table group by A,B,C -
as subset. It's mind: "GROUP BY A,B,C" - subset of "GROUP BY GROUPING
SETS( (A,B,C), (A), () )
Two subset - is GROUP BY A B, and instead C column we look NULL.
Third subset - GROUP BY (), instead A,B,C - NULL, one row - it's name
"GRAND TOTAL". - calculate over all subset without grouping

Also have function "GROUPING"  it's function say about null - "real
null" (from table) or generated by "GROUP BY GROUPING SETS"

My point: this feature can implement over GROUP BY and UNION ALL
We can make decomposition of "GROUP BY GROUPING SETS( (A,B,C),(A),()
)" to  select A,B,C fron table GROUP BY A,B,C .UNION  ALL select
A,B,NULL from table group BY A,B UNION ALL NUll,NUll,NULL from table
group by();

So, it's very simple, don't require modification of executor and
callibrate cost - only parser and semantic anylysis,
'
So, ROLLUP(A1,...An) is alias to "GROUP BY GROUPING SETS(
(A1,...,An),(A1,...,An-1),... (An-1,An),(An),() ),
CUBE - analogue.

If this idea it's good -  i can write code base on old patch
http://archives.postgresql.org/pgsql-hackers/2008-10/msg00838.php or
from clean list (as you wish).

This is suboptimal. When SELECT * FROM X GROUP BY GROUPING SETS ...,
where X is some joined data, then you repeat JOIN on every grouping
set. So your solution is simple for implementation, but it should be
really slow.

Regards
Pavel Stehule

In future i know how to implement ROLLUP more optimal (executor
iterator) and use this ROLLUP for optimisation another GROUP BY,
GROUPING SETS.

Thanks.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Regards,

--
Hitoshi Harada

Hello all.
Please, approve my ideas for implementation.

Standart has feature T431: Extended grouping capabilities.
This feature i found in TODO-list:
http://wiki.postgresql.org/wiki/Todo -> SQL Commands -> TO DO

MS SQL 2005 partial support this feature:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
http://blogs.msdn.com/craigfr/archive/2007/09/21/aggregation-with-rollup.aspx

MS SQL 2008 support this feature:
http://blogs.msdn.com/craigfr/archive/2007/10/11/grouping-sets-in-sql-server-2008.aspx

Oracle support this feature:
http://www.compshack.com/sql/oracle-group-rollup

So, it's short notes about GROUPING SETS, but more complete
information have in a official documentation of MS SQL and Oracle
(copyright limited for send as attach).

First. GROUPG SETS.

select A,B,C,SUM(D) from table group by GROUPING SETS( (A,B,C), (A),
() ) - it's example of use grouping sets.
Semantic of this construction - make group by over source more, than
one group of column.
It's very wide key - A,B C. In result set of this example we can find
result set of select   select A,B,C,SUM(D) from table group by A,B,C -
as subset. It's mind: "GROUP BY A,B,C" - subset of "GROUP BY GROUPING
SETS( (A,B,C), (A), () )
Two subset - is GROUP BY A B, and instead C column we look NULL.
Third subset - GROUP BY (), instead A,B,C - NULL, one row - it's name
"GRAND TOTAL". - calculate over all subset without grouping

Also have function "GROUPING"  it's function say about null - "real
null" (from table) or generated by "GROUP BY GROUPING SETS"

My point: this feature can implement over GROUP BY and UNION ALL
We can make decomposition of "GROUP BY GROUPING SETS( (A,B,C),(A),()
)" to  select A,B,C fron table GROUP BY A,B,C .UNION  ALL select
A,B,NULL from table group BY A,B UNION ALL NUll,NUll,NULL from table
group by();

So, it's very simple, don't require modification of executor and
callibrate cost - only parser and semantic anylysis,
'
So, ROLLUP(A1,...An) is alias to "GROUP BY GROUPING SETS(
(A1,...,An),(A1,...,An-1),... (An-1,An),(An),() ),
CUBE - analogue.

If this idea it's good -  i can write code base on old patch
http://archives.postgresql.org/pgsql-hackers/2008-10/msg00838.php or
from clean list (as you wish).

In future i know how to implement ROLLUP more optimal (executor
iterator) and use this ROLLUP for optimisation another GROUP BY,
GROUPING SETS.

Thanks.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Hello Oleg

I am sending a new CTE based variant of my GROUPING SETS patch,

this patch has some bugs but it is good prototype (it's more stable
than old patch):

postgres=# select selling_date, baguette, sum(items) from
baguette_selling group by grouping sets(1,2);
 selling_date | baguette | sum
--------------+----------+-----
 2007-10-30   |          |  17
 2007-10-31   |          |  12
             | golf     |   9
             | buster   |  20
(4 rows)

postgres=# select selling_date, baguette, sum(items),
grouping(selling_date), grouping(baguette), grouping_id(selling_date,
baguette) from baguette_selling group by grouping sets(1,2);
 selling_date | baguette | sum | grouping | grouping | grouping_id
--------------+----------+-----+----------+----------+-------------
 2007-10-30   |          |  17 |        1 |        0 |           2
 2007-10-31   |          |  12 |        1 |        0 |           2
             | golf     |   9 |        0 |        1 |           1
             | buster   |  20 |        0 |        1 |           1
(4 rows)

postgres=# select selling_date, baguette, sum(items),
grouping(selling_date), grouping(baguette), grouping_id(selling_date,
baguette) from baguette_selling group by grouping sets(1,2,());
 selling_date | baguette | sum | grouping | grouping | grouping_id
--------------+----------+-----+----------+----------+-------------
 2007-10-30   |          |  17 |        1 |        0 |           2
 2007-10-31   |          |  12 |        1 |        0 |           2
             | golf     |   9 |        0 |        1 |           1
             | buster   |  20 |        0 |        1 |           1
             |          |  29 |        0 |        0 |           0
(5 rows)

I thing so parser part is well and correct (and ported to 8.4).

CTE works well, but not 100% effective, and will be better to use
direct tuplestore interface (as second technique - when hash tables
can't to be used).

I am thinking, so the best solution is enhancing current Aggregate
node for support of GroupingSets. The code base on UNION ALL is +/-
equal to CTE, and I don't thing, so this should be optimal. But work
freely, please. I have not free time for this patch next two months.
So if you have time, it's your.

regards
Pavel Stehule

2009/5/10 Олег Царев <zabivator@gmail.com>:

Hello all.
Please, approve my ideas for implementation.

Standart has feature T431: Extended grouping capabilities.
This feature i found in TODO-list:
http://wiki.postgresql.org/wiki/Todo -> SQL Commands -> TO DO

MS SQL 2005 partial support this feature:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
http://blogs.msdn.com/craigfr/archive/2007/09/21/aggregation-with-rollup.aspx

MS SQL 2008 support this feature:
http://blogs.msdn.com/craigfr/archive/2007/10/11/grouping-sets-in-sql-server-2008.aspx

Oracle support this feature:
http://www.compshack.com/sql/oracle-group-rollup

So, it's short notes about GROUPING SETS, but more complete
information have in a official documentation of MS SQL and Oracle
(copyright limited for send as attach).

First. GROUPG SETS.

select A,B,C,SUM(D) from table group by GROUPING SETS( (A,B,C), (A),
() ) - it's example of use grouping sets.
Semantic of this construction - make group by over source more, than
one group of column.
It's very wide key - A,B C. In result set of this example we can find
result set of select   select A,B,C,SUM(D) from table group by A,B,C -
as subset. It's mind: "GROUP BY A,B,C" - subset of "GROUP BY GROUPING
SETS( (A,B,C), (A), () )
Two subset - is GROUP BY A B, and instead C column we look NULL.
Third subset - GROUP BY (), instead A,B,C - NULL, one row - it's name
"GRAND TOTAL". - calculate over all subset without grouping

Also have function "GROUPING"  it's function say about null - "real
null" (from table) or generated by "GROUP BY GROUPING SETS"

My point: this feature can implement over GROUP BY and UNION ALL
We can make decomposition of "GROUP BY GROUPING SETS( (A,B,C),(A),()
)" to  select A,B,C fron table GROUP BY A,B,C .UNION  ALL select
A,B,NULL from table group BY A,B UNION ALL NUll,NUll,NULL from table
group by();

So, it's very simple, don't require modification of executor and
callibrate cost - only parser and semantic anylysis,
'
So, ROLLUP(A1,...An) is alias to "GROUP BY GROUPING SETS(
(A1,...,An),(A1,...,An-1),... (An-1,An),(An),() ),
CUBE - analogue.

If this idea it's good -  i can write code base on old patch
http://archives.postgresql.org/pgsql-hackers/2008-10/msg00838.php or
from clean list (as you wish).

In future i know how to implement ROLLUP more optimal (executor
iterator) and use this ROLLUP for optimisation another GROUP BY,
GROUPING SETS.

Thanks.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

5432 josh@josh*# select * from (select prod_id, cust_id, sum(quantity) from
gsettest group by cube (prod_id, cust_id)) f order by 1, 2;
 prod_id | cust_id | sum
---------+---------+-----
      0 |       2 |   8
      0 |       4 |   8
      0 |       5 |   2
      0 |       7 |  11
      0 |       8 |   7
      0 |       9 |   1
      0 |      12 |   3
      0 |      14 |   7
      0 |      16 |   5
      0 |      17 |   8
      0 |      18 |   9
      0 |      19 |   2
      0 |         |  71
</snip>

EXPLAIN output is as follows:
5432 josh@josh*# explain select prod_id, cust_id, sum(quantity) from gsettest
group by cube (prod_id, cust_id) order by 1, 2;
                               QUERY PLAN
---------------------------------------------------------------------------
 Append  (cost=193.54..347.71 rows=601 width=9)
  CTE **g**
    ->  Sort  (cost=135.34..140.19 rows=1940 width=12)
          Sort Key: gsettest.prod_id, gsettest.cust_id
          ->  Seq Scan on gsettest  (cost=0.00..29.40 rows=1940 width=12)
  ->  HashAggregate  (cost=53.35..55.85 rows=200 width=12)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=12)
  ->  HashAggregate  (cost=48.50..51.00 rows=200 width=8)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=8)
  ->  HashAggregate  (cost=48.50..51.00 rows=200 width=8)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=8)
  ->  Aggregate  (cost=43.65..43.66 rows=1 width=4)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=4)
(13 rows)

...and without the ORDER BY clause just to prove that it really is the reason
for the Sort step...

5432 josh@josh*# explain select prod_id, cust_id, sum(quantity) from gsettest
group by cube (prod_id, cust_id);
                              QUERY PLAN
------------------------------------------------------------------------
 Append  (cost=82.75..236.92 rows=601 width=9)
  CTE **g**
    ->  Seq Scan on gsettest  (cost=0.00..29.40 rows=1940 width=12)
  ->  HashAggregate  (cost=53.35..55.85 rows=200 width=12)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=12)
  ->  HashAggregate  (cost=48.50..51.00 rows=200 width=8)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=8)
  ->  HashAggregate  (cost=48.50..51.00 rows=200 width=8)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=8)
  ->  Aggregate  (cost=43.65..43.66 rows=1 width=4)
        ->  CTE Scan on "**g**"  (cost=0.00..38.80 rows=1940 width=4)
(11 rows)

I'm hoping I'll get a chance to poke at the patch some. This could be very
useful...

- Josh / eggyknap

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkoKOdUACgkQRiRfCGf1UMOpFQCeJGQftMheSi6blMwheK4HI89p
E7cAnjdWi4FaerR/+RTBeSv9Zc0RRXQ3
=xW04
-----END PGP SIGNATURE-----

- Josh

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkoKxLQACgkQRiRfCGf1UMOj/wCgkPnRiheRr+BNPLBCjzA9XlFW
0rsAoI0eOGSGlxIv0eNB8zqum7kw/Cqw
=FCTz
-----END PGP SIGNATURE-----

On Wed, May 13, 2009 at 03:12:51PM +0200, Pavel Stehule wrote:

2009/5/13 Joshua Tolley <eggyknap@gmail.com>:

On Wed, May 13, 2009 at 06:29:41AM +0200, Pavel Stehule wrote:

2009/5/13 Joshua Tolley <eggyknap@gmail.com>:

On Tue, May 12, 2009 at 11:20:14PM +0200, Pavel Stehule wrote:

this patch has some bugs but it is good prototype (it's more stable
than old patch):

I'm not sure if you're at the point that you're interested in bug reports, but
here's something that didn't behave as expected:

5432 josh@josh*# create table gsettest (prod_id integer, cust_id integer,
quantity integer);
CREATE TABLE
5432 josh@josh*# insert into gsettest select floor(random() * 10)::int,
floor(random() * 20)::int, floor(random() * 10)::int from generate_series(1,
100);
INSERT 0 100
5432 josh@josh*# select prod_id, cust_id, sum(quantity) from gsettest group by
cube (prod_id, cust_id) order by 1, 2;
 prod_id | cust_id | sum
---------+---------+-----
      5 |       7 |   4
      8 |      16 |   3
      9 |      19 |   8
      4 |      13 |   3
      8 |       8 |  15
      5 |       2 |   4
      7 |       6 |   7
      6 |       6 |   3
</snip>

Note that the results aren't sorted. The following, though, works around it:

I thing, so result should not be sorted - it's same like normal group by.

Normal GROUP BY wouldn't have ignored the ORDER BY clause I included.

sorry, now I understand - simply it is a bug. I fixed it

Where's the new patch?

Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778  AIM: dfetter666  Yahoo!: dfetter
Skype: davidfetter      XMPP: david.fetter@gmail.com

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

I will write separated mail about rollup.
Can you send me some links or information about "CTE"? What is it?
Also, I need some deep knownledge about postgresql aggregation
calculation (executor part) - can you help me (links, books, name of
source files, etc)?.
After get additional information i will can continue discussion.
Thanls
2009/5/10 Pavel Stehule <pavel.stehule@gmail.com>:

2009/5/10 Олег Царев <zabivator@gmail.com>:

Hello, Pavel.

I read you letter, and found some points:

a) Simple transformation any GROUPING SETS in GROUP BY + UNION ALL
require clone source for every group.
It's so slow.
My point: we can make for start simple implementation.
b) Your sollution it's so good, IMHO
WITH q AS (SELECT * FROM some)
 SELECT * FROM q GROUP BY a
 UNION ALL
 SELECT * FROM q GROUP BY b
But can you describe me how it's used on planner (calculate cost) and exector.

look on CTE source code or ask to CTE author.

Sharing source - it's mind - we don't process tree, we process
DIRECTED GRAPH. Hard, many bugs, so on, not?

for example - code for DISTINCT is shared with code for aggregation.
My idea is based on similarity

GROUPING SETS is subset of CTE, nonrecursive CTE is subset of UNION ALL

PostgreSQL support sharing nodes of executor? How? Where i can read?

I don't know, what do you thing exactly sharing nodes? Before CTE I
had to write special holder node, but it isn't necessary now.

Next. Ok, we spool source. After we use simple hash group/sort group +
union all? Or more advanced techniques?  If different group by - it's
not different from my idea, it's logic additional (spool source for
fast rewind)

I thing so trivial implementation via UNION ALL should work, but any
optimisations means lot of work - and when you add rewind
functionality, you will got trivial nonrecursive CTE implementation.
When I wrote patch, there wasn't possible an use CTE, so I played wit
own nodes. Now, the more clean solution is probably based on current
CTE base.

c) Don't forget also about node requiments - if we use hash table as
container for source -  we reduce some sorting properties - and query
select A,B from TABLE group by ((A,B),(B)) order by a,b require
sorting on output of grouping sets.
It's mind - we need insert sort.

Yes, probably there should be possible some techniques - that should
to eliminate final sort op. I am not sure if it is really important.
Now I thinking what is the bigger devil a) patch complexity b) some
suboptimality  (mainly redundant call of agg nodes). For me a.
Aggregates are not gratis, but significantly more expensive is
repeated seq data scan. So it is first goal. Later we should to thing
about next optimalizations.

d) We can make SORT ROLLUP and SORT REDUCE ROLLUP.
first - sort group by use sorting for grouping data and calculate aggregations.
So, 'order by A,B,C' also 'order by A,B' also order by 'A' also order by ''
What it's mind? It's mind we can use sort features for implement SORT
ROLLUP. For every sub group we calculate self aggregates... oh, i bad
say. Look on "select a,sum(b) from table group by a".  Sort group
grouping by a, and for every a-group calculate aggregations (sum), for
ROLLUP A,B we can make three aggregations ; for A,B than A than () -
and use one path on source calculate aggregations on every step, and
for split source on different subsets.
It's more perfomance, than different group by and union all.

Maybe, I don't know. What I know:

* UNION ALL will have better result on indexed sets and MIN, MAX
aggregates. CTE isn't optimized now for these cases.
* UNION ALL will be slow for large sets (over cache),
* CTE needs some more optimalizations,
* pg core hackers dislike big and complex patches,
* pg core hackers like any improved current code base.

I am thinking so Grouping Sets based on CTE should be more commitable
code. It doesn't mean so your ideas are wrong, but these
optimalization should to work on CTE too.

select * from table group by rollup(a,b,c)

have to have generate same plan as

with q as (select * from table)
 select * from q group by a,b,c
 union all
 select * from q group by a,b
 union all
 select * from q group by a
 union all
 select * from q;

and CTE is more general then Grouping Sets, so it is better do
optimalization over CTE than Grouping Sets.

Regards
Pavel Stehule

Look for MS SQL:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
Why MS SQL don't support distinct aggregations? I think - because
every distinct aggregations in MS SQL require hash, and many
aggregations - it's so slow.

Thank you!
2009/5/10 Pavel Stehule <pavel.stehule@gmail.com>:

Hello

some other info is on  http://wiki.postgresql.org/wiki/Grouping_Sets

Maybe in e few weak I'll have some a prototype based on CTE. My older
technique based on hashed tables should be well, but it carry lot of
unshared code. Using CTE means so we can optimize CTE and GROUPING
SETS together. I plan to transform query

SELECT * FROM some GROUP BY GROUPING SETS(a, b)

to

WITH q AS (SELECT * FROM some)
 SELECT * FROM q GROUP BY a
 UNION ALL
 SELECT * FROM q GROUP BY b

2009/5/10 Олег Царев <zabivator@gmail.com>:

Hello all.
Please, approve my ideas for implementation.

Standart has feature T431: Extended grouping capabilities.
This feature i found in TODO-list:
http://wiki.postgresql.org/wiki/Todo -> SQL Commands -> TO DO

MS SQL 2005 partial support this feature:
http://www.kodyaz.com/articles/sql-server-2005-cube-rollup-cannot-compute-distinct-aggregates.aspx
http://blogs.msdn.com/craigfr/archive/2007/09/21/aggregation-with-rollup.aspx

MS SQL 2008 support this feature:
http://blogs.msdn.com/craigfr/archive/2007/10/11/grouping-sets-in-sql-server-2008.aspx

Oracle support this feature:
http://www.compshack.com/sql/oracle-group-rollup

So, it's short notes about GROUPING SETS, but more complete
information have in a official documentation of MS SQL and Oracle
(copyright limited for send as attach).

First. GROUPG SETS.

select A,B,C,SUM(D) from table group by GROUPING SETS( (A,B,C), (A),
() ) - it's example of use grouping sets.
Semantic of this construction - make group by over source more, than
one group of column.
It's very wide key - A,B C. In result set of this example we can find
result set of select   select A,B,C,SUM(D) from table group by A,B,C -
as subset. It's mind: "GROUP BY A,B,C" - subset of "GROUP BY GROUPING
SETS( (A,B,C), (A), () )
Two subset - is GROUP BY A B, and instead C column we look NULL.
Third subset - GROUP BY (), instead A,B,C - NULL, one row - it's name
"GRAND TOTAL". - calculate over all subset without grouping

Also have function "GROUPING"  it's function say about null - "real
null" (from table) or generated by "GROUP BY GROUPING SETS"

My point: this feature can implement over GROUP BY and UNION ALL
We can make decomposition of "GROUP BY GROUPING SETS( (A,B,C),(A),()
)" to  select A,B,C fron table GROUP BY A,B,C .UNION  ALL select
A,B,NULL from table group BY A,B UNION ALL NUll,NUll,NULL from table
group by();

So, it's very simple, don't require modification of executor and
callibrate cost - only parser and semantic anylysis,
'
So, ROLLUP(A1,...An) is alias to "GROUP BY GROUPING SETS(
(A1,...,An),(A1,...,An-1),... (An-1,An),(An),() ),
CUBE - analogue.

If this idea it's good -  i can write code base on old patch
http://archives.postgresql.org/pgsql-hackers/2008-10/msg00838.php or
from clean list (as you wish).

This is suboptimal. When SELECT * FROM X GROUP BY GROUPING SETS ...,
where X is some joined data, then you repeat JOIN on every grouping
set. So your solution is simple for implementation, but it should be
really slow.

Regards
Pavel Stehule

In future i know how to implement ROLLUP more optimal (executor
iterator) and use this ROLLUP for optimisation another GROUP BY,
GROUPING SETS.

Thanks.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers