Fix up grouping sets reorder

[Richard Guo]

Hi all,

During the reorder of grouping sets into correct prefix order, if only
one aggregation pass is needed, we follow the order of the ORDER BY
clause to the extent possible, to minimize the chance that we add
unnecessary sorts. This is implemented in preprocess_grouping_sets -->
reorder_grouping_sets.

However, current codes fail to do that. For instance:

# set enable_hashagg to off;
SET

# explain verbose select * from t group by grouping sets((a,b,c),(c)) order
by c,b,a;
                                  QUERY PLAN
-------------------------------------------------------------------------------
 Sort  (cost=184.47..185.48 rows=404 width=12)
   Output: a, b, c
   Sort Key: t.c, t.b, t.a
   ->  GroupAggregate  (cost=142.54..166.98 rows=404 width=12)
         Output: a, b, c
         Group Key: t.c, t.a, t.b
         Group Key: t.c
         ->  Sort  (cost=142.54..147.64 rows=2040 width=12)
               Output: a, b, c
               Sort Key: t.c, t.a, t.b
               ->  Seq Scan on public.t  (cost=0.00..30.40 rows=2040
width=12)
                     Output: a, b, c
(12 rows)

This sort node in the above plan can be avoided if we reorder the
grouping sets more properly.

Attached is a patch for the fixup. With the patch, the above plan would
become:

# explain verbose select * from t group by grouping sets((a,b,c),(c)) order
by c,b,a;
                               QUERY PLAN
-------------------------------------------------------------------------
 GroupAggregate  (cost=142.54..166.98 rows=404 width=12)
   Output: a, b, c
   Group Key: t.c, t.b, t.a
   Group Key: t.c
   ->  Sort  (cost=142.54..147.64 rows=2040 width=12)
         Output: a, b, c
         Sort Key: t.c, t.b, t.a
         ->  Seq Scan on public.t  (cost=0.00..30.40 rows=2040 width=12)
               Output: a, b, c
(9 rows)

The fix happens in reorder_grouping_sets and is very simple. In each
iteration to reorder one grouping set, if the next item in sortclause
matches one element in new_elems, we add that item to the grouing set
list and meanwhile remove it from the new_elems list. When all the
elements in new_elems have been removed, we can know we are done with
current grouping set. We should break out to continue with next grouping
set.

Any thoughts?

Thanks
Richard

v1-0001-Fix-up-grouping-sets-reorder.patch
Description: Binary data