Horton

Thread

Commits

  1. Support hashed aggregation with grouping sets.

  1. Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-01-06T03:48:58Z

    Herewith a patch for doing grouping sets via hashing or mixed hashing
and sorting.

The principal objective is to pick whatever combination of grouping sets
has an estimated size that fits in work_mem, and minimizes the number of
sorting passes we need to do over the data, and hash those.  (Yes, this
is a knapsack problem.)

This is achieved by adding another strategy to the Agg node; AGG_MIXED
means that both hashing and (sorted or plain) grouping happens.  In
addition, support for multiple hash tables in AGG_HASHED mode is added.

Sample plans look like this:

explain select two,ten from onek group by cube(two,ten);
                          QUERY PLAN                          
--------------------------------------------------------------
 MixedAggregate  (cost=0.00..89.33 rows=33 width=8)
   Hash Key: two, ten
   Hash Key: two
   Hash Key: ten
   Group Key: ()
   ->  Seq Scan on onek  (cost=0.00..79.00 rows=1000 width=8)

explain select two,ten from onek group by two, cube(ten,twenty);
                          QUERY PLAN                           
---------------------------------------------------------------
 HashAggregate  (cost=86.50..100.62 rows=162 width=12)
   Hash Key: two, ten, twenty
   Hash Key: two, ten
   Hash Key: two
   Hash Key: two, twenty
   ->  Seq Scan on onek  (cost=0.00..79.00 rows=1000 width=12)

set work_mem='64kB';
explain select count(*) from tenk1
  group by grouping sets (unique1,thousand,hundred,ten,two);
                               QUERY PLAN                               
------------------------------------------------------------------------
 MixedAggregate  (cost=1535.39..3023.89 rows=11112 width=28)
   Hash Key: two
   Hash Key: ten
   Hash Key: hundred
   Group Key: unique1
   Sort Key: thousand
     Group Key: thousand
   ->  Sort  (cost=1535.39..1560.39 rows=10000 width=20)
         Sort Key: unique1
         ->  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=20)
(10 rows)

Columns with unhashable or unsortable data types are handled
appropriately, though obviously every individual grouping set must end
up containing compatible column types.

There is one current weakness which I don't see a good solution for: the
planner code still has to pick a single value for group_pathkeys before
planning the input path.  This means that we sometimes can't choose a
minimal set of sorts, because we may have chosen a sort order for a
grouping set that should have been hashed, for example:

explain select count(*) from tenk1
  group by grouping sets (two,unique1,thousand,hundred,ten);
                               QUERY PLAN                               
------------------------------------------------------------------------
 MixedAggregate  (cost=1535.39..4126.28 rows=11112 width=28)
   Hash Key: ten
   Hash Key: hundred
   Group Key: two
   Sort Key: unique1
     Group Key: unique1
   Sort Key: thousand
     Group Key: thousand
   ->  Sort  (cost=1535.39..1560.39 rows=10000 width=20)
         Sort Key: two
         ->  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=20)

(3 sorts, vs. 2 in the previous example that listed the same grouping
sets in different order)

Current status of the work: probably still needs cleanup, maybe some
better regression tests, and Andres has expressed some concern over the
performance impact of additional complexity in advance_aggregates; it
would be useful if this could be tested.  But it should be reviewable
as-is.

-- 
Andrew (irc:RhodiumToad)

  2. Re: Hash support for grouping sets

    Robert Haas <robertmhaas@gmail.com> — 2017-01-10T15:22:58Z

    On Thu, Jan 5, 2017 at 10:48 PM, Andrew Gierth
<andrew@tao11.riddles.org.uk> wrote:
> Herewith a patch for doing grouping sets via hashing or mixed hashing
> and sorting.

Cool.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  3. Re: Hash support for grouping sets

    Finnerty, Jim <jfinnert@amazon.com> — 2017-01-16T15:59:59Z

    The ability to exploit hashed aggregation within sorted groups, when the order of the input stream can be exploited this way, is potentially a useful way to improve aggregation performance more generally.  This would potentially be beneficial when the input size is expected to be larger than the amount of working memory available for hashed aggregation, but where there is enough memory to hash-aggregate just the unsorted grouping key combinations, and when the cumulative cost of rebuilding the hash table for each sorted subgroup is less than the cost of sorting the entire input.  In other words, if most of the grouping key combinations are already segregated by virtue of the input order, then hashing the remaining combinations within each sorted group might be done in memory, at the cost of rebuilding the hash table for each sorted subgroup.

I haven’t looked at the code for this change yet (I hope I will have the time to do that).  Ideally the decision to choose the aggregation method as sorted, hashed, or mixed hash/sort should be integrated into the cost model, but given the notorious difficulty of estimating intermediate cardinalities accurately it would be difficult to develop a cardinality model and a cost model accurate enough to choose among these options consistently well.

Jim Finnerty
Amazon Corp.

On 1/10/17, 10:22 AM, "pgsql-hackers-owner@postgresql.org on behalf of Robert Haas" <pgsql-hackers-owner@postgresql.org on behalf of robertmhaas@gmail.com> wrote:

    On Thu, Jan 5, 2017 at 10:48 PM, Andrew Gierth
    <andrew@tao11.riddles.org.uk> wrote:
    > Herewith a patch for doing grouping sets via hashing or mixed hashing
    > and sorting.
    
    Cool.
    
    -- 
    Robert Haas
    EnterpriseDB: http://www.enterprisedb.com
    The Enterprise PostgreSQL Company
    
    
    -- 
    Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
    To make changes to your subscription:
    http://www.postgresql.org/mailpref/pgsql-hackers

  4. Re: Hash support for grouping sets

    Robert Haas <robertmhaas@gmail.com> — 2017-01-17T16:59:36Z

    On Mon, Jan 16, 2017 at 10:59 AM, Finnerty, Jim <jfinnert@amazon.com> wrote:
> The ability to exploit hashed aggregation within sorted groups, when the order of the input stream can be exploited this way, is potentially a useful way to improve aggregation performance more generally.  This would potentially be beneficial when the input size is expected to be larger than the amount of working memory available for hashed aggregation, but where there is enough memory to hash-aggregate just the unsorted grouping key combinations, and when the cumulative cost of rebuilding the hash table for each sorted subgroup is less than the cost of sorting the entire input.  In other words, if most of the grouping key combinations are already segregated by virtue of the input order, then hashing the remaining combinations within each sorted group might be done in memory, at the cost of rebuilding the hash table for each sorted subgroup.

Neat idea.

> I haven’t looked at the code for this change yet (I hope I will have the time to do that).  Ideally the decision to choose the aggregation method as sorted, hashed, or mixed hash/sort should be integrated into the cost model, but given the notorious difficulty of estimating intermediate cardinalities accurately it would be difficult to develop a cardinality model and a cost model accurate enough to choose among these options consistently well.

Yes, that might be a little tricky.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  5. Re: Hash support for grouping sets

    Thom Brown <thom@linux.com> — 2017-02-22T13:59:33Z

    On 6 January 2017 at 03:48, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
> Herewith a patch for doing grouping sets via hashing or mixed hashing
> and sorting.
>
> The principal objective is to pick whatever combination of grouping sets
> has an estimated size that fits in work_mem, and minimizes the number of
> sorting passes we need to do over the data, and hash those.  (Yes, this
> is a knapsack problem.)
>
> This is achieved by adding another strategy to the Agg node; AGG_MIXED
> means that both hashing and (sorted or plain) grouping happens.  In
> addition, support for multiple hash tables in AGG_HASHED mode is added.
>
> Sample plans look like this:
>
> explain select two,ten from onek group by cube(two,ten);
>                           QUERY PLAN
> --------------------------------------------------------------
>  MixedAggregate  (cost=0.00..89.33 rows=33 width=8)
>    Hash Key: two, ten
>    Hash Key: two
>    Hash Key: ten
>    Group Key: ()
>    ->  Seq Scan on onek  (cost=0.00..79.00 rows=1000 width=8)
>
> explain select two,ten from onek group by two, cube(ten,twenty);
>                           QUERY PLAN
> ---------------------------------------------------------------
>  HashAggregate  (cost=86.50..100.62 rows=162 width=12)
>    Hash Key: two, ten, twenty
>    Hash Key: two, ten
>    Hash Key: two
>    Hash Key: two, twenty
>    ->  Seq Scan on onek  (cost=0.00..79.00 rows=1000 width=12)
>
> set work_mem='64kB';
> explain select count(*) from tenk1
>   group by grouping sets (unique1,thousand,hundred,ten,two);
>                                QUERY PLAN
> ------------------------------------------------------------------------
>  MixedAggregate  (cost=1535.39..3023.89 rows=11112 width=28)
>    Hash Key: two
>    Hash Key: ten
>    Hash Key: hundred
>    Group Key: unique1
>    Sort Key: thousand
>      Group Key: thousand
>    ->  Sort  (cost=1535.39..1560.39 rows=10000 width=20)
>          Sort Key: unique1
>          ->  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=20)
> (10 rows)
>
> Columns with unhashable or unsortable data types are handled
> appropriately, though obviously every individual grouping set must end
> up containing compatible column types.
>
> There is one current weakness which I don't see a good solution for: the
> planner code still has to pick a single value for group_pathkeys before
> planning the input path.  This means that we sometimes can't choose a
> minimal set of sorts, because we may have chosen a sort order for a
> grouping set that should have been hashed, for example:
>
> explain select count(*) from tenk1
>   group by grouping sets (two,unique1,thousand,hundred,ten);
>                                QUERY PLAN
> ------------------------------------------------------------------------
>  MixedAggregate  (cost=1535.39..4126.28 rows=11112 width=28)
>    Hash Key: ten
>    Hash Key: hundred
>    Group Key: two
>    Sort Key: unique1
>      Group Key: unique1
>    Sort Key: thousand
>      Group Key: thousand
>    ->  Sort  (cost=1535.39..1560.39 rows=10000 width=20)
>          Sort Key: two
>          ->  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=20)
>
> (3 sorts, vs. 2 in the previous example that listed the same grouping
> sets in different order)
>
> Current status of the work: probably still needs cleanup, maybe some
> better regression tests, and Andres has expressed some concern over the
> performance impact of additional complexity in advance_aggregates; it
> would be useful if this could be tested.  But it should be reviewable
> as-is.

This doesn't apply cleanly to latest master.  Could you please post a
rebased patch?

Thanks

Thom

  6. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-02-24T17:15:50Z

    >>>>> "Thom" == Thom Brown <thom@linux.com> writes:

 Thom> This doesn't apply cleanly to latest master.  Could you please
 Thom> post a rebased patch?

Sure.

-- 
Andrew (irc:RhodiumToad)

  7. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-07T21:43:32Z

    The following review has been posted through the commitfest application:
make installcheck-world:  tested, failed
Implements feature:       not tested
Spec compliant:           not tested
Documentation:            not tested

On my MacBook, `make check-world` gives differences in the contrib modules:

cat contrib/postgres_fdw/regression.diffs
*** /Users/mark/hydra/postgresql.review/contrib/postgres_fdw/expected/postgres_fdw.out	2017-03-03 13:33:47.000000000 -0800
--- /Users/mark/hydra/postgresql.review/contrib/postgres_fdw/results/postgres_fdw.out	2017-03-07 13:27:56.000000000 -0800
***************
*** 3148,3163 ****
  -- Grouping sets
  explain (verbose, costs off)
  select c2, sum(c1) from ft1 where c2 < 3 group by rollup(c2) order by 1 nulls last;
!                                             QUERY PLAN                                             
! ---------------------------------------------------------------------------------------------------
!  GroupAggregate
!    Output: c2, sum(c1)
!    Group Key: ft1.c2
!    Group Key: ()
!    ->  Foreign Scan on public.ft1
!          Output: c2, c1
!          Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE ((c2 < 3)) ORDER BY c2 ASC NULLS LAST
! (7 rows)
  
  select c2, sum(c1) from ft1 where c2 < 3 group by rollup(c2) order by 1 nulls last;
   c2 |  sum   
--- 3148,3166 ----
  -- Grouping sets
  explain (verbose, costs off)
  select c2, sum(c1) from ft1 where c2 < 3 group by rollup(c2) order by 1 nulls last;
!                                   QUERY PLAN                                  
! ------------------------------------------------------------------------------
!  Sort
!    Output: c2, (sum(c1))
!    Sort Key: ft1.c2
!    ->  MixedAggregate
!          Output: c2, sum(c1)
!          Hash Key: ft1.c2
!          Group Key: ()
!          ->  Foreign Scan on public.ft1
!                Output: c2, c1
!                Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE ((c2 < 3))
! (10 rows)
  
  select c2, sum(c1) from ft1 where c2 < 3 group by rollup(c2) order by 1 nulls last;
   c2 |  sum   
***************
*** 3170,3185 ****
  
  explain (verbose, costs off)
  select c2, sum(c1) from ft1 where c2 < 3 group by cube(c2) order by 1 nulls last;
!                                             QUERY PLAN                                             
! ---------------------------------------------------------------------------------------------------
!  GroupAggregate
!    Output: c2, sum(c1)
!    Group Key: ft1.c2
!    Group Key: ()
!    ->  Foreign Scan on public.ft1
!          Output: c2, c1
!          Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE ((c2 < 3)) ORDER BY c2 ASC NULLS LAST
! (7 rows)
  
  select c2, sum(c1) from ft1 where c2 < 3 group by cube(c2) order by 1 nulls last;
   c2 |  sum   
--- 3173,3191 ----
  
  explain (verbose, costs off)
  select c2, sum(c1) from ft1 where c2 < 3 group by cube(c2) order by 1 nulls last;
!                                   QUERY PLAN                                  
! ------------------------------------------------------------------------------
!  Sort
!    Output: c2, (sum(c1))
!    Sort Key: ft1.c2
!    ->  MixedAggregate
!          Output: c2, sum(c1)
!          Hash Key: ft1.c2
!          Group Key: ()
!          ->  Foreign Scan on public.ft1
!                Output: c2, c1
!                Remote SQL: SELECT "C 1", c2 FROM "S 1"."T 1" WHERE ((c2 < 3))
! (10 rows)
  
  select c2, sum(c1) from ft1 where c2 < 3 group by cube(c2) order by 1 nulls last;
   c2 |  sum   
***************
*** 3192,3211 ****
  
  explain (verbose, costs off)
  select c2, c6, sum(c1) from ft1 where c2 < 3 group by grouping sets(c2, c6) order by 1 nulls last, 2 nulls last;
!                                                  QUERY PLAN                                                  
! -------------------------------------------------------------------------------------------------------------
   Sort
     Output: c2, c6, (sum(c1))
     Sort Key: ft1.c2, ft1.c6
!    ->  GroupAggregate
           Output: c2, c6, sum(c1)
!          Group Key: ft1.c2
!          Sort Key: ft1.c6
!            Group Key: ft1.c6
           ->  Foreign Scan on public.ft1
                 Output: c2, c6, c1
!                Remote SQL: SELECT "C 1", c2, c6 FROM "S 1"."T 1" WHERE ((c2 < 3)) ORDER BY c2 ASC NULLS LAST
! (11 rows)
  
  select c2, c6, sum(c1) from ft1 where c2 < 3 group by grouping sets(c2, c6) order by 1 nulls last, 2 nulls last;
   c2 | c6 |  sum  
--- 3198,3216 ----
  
  explain (verbose, costs off)
  select c2, c6, sum(c1) from ft1 where c2 < 3 group by grouping sets(c2, c6) order by 1 nulls last, 2 nulls last;
!                                     QUERY PLAN                                    
! ----------------------------------------------------------------------------------
   Sort
     Output: c2, c6, (sum(c1))
     Sort Key: ft1.c2, ft1.c6
!    ->  HashAggregate
           Output: c2, c6, sum(c1)
!          Hash Key: ft1.c2
!          Hash Key: ft1.c6
           ->  Foreign Scan on public.ft1
                 Output: c2, c6, c1
!                Remote SQL: SELECT "C 1", c2, c6 FROM "S 1"."T 1" WHERE ((c2 < 3))
! (10 rows)
  
  select c2, c6, sum(c1) from ft1 where c2 < 3 group by grouping sets(c2, c6) order by 1 nulls last, 2 nulls last;
   c2 | c6 |  sum  

======================================================================

  8. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-07T21:53:03Z

    > On Mar 7, 2017, at 1:43 PM, Mark Dilger <hornschnorter@gmail.com> wrote:
> 
> On my MacBook, `make check-world` gives differences in the contrib modules:

I get the same (or similar -- didn't check) regression failure on CentOS, so this
doesn't appear to be MacBook / hardware specific.

Mark Dilger

  9. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-07T21:58:53Z

    The following review has been posted through the commitfest application:
make installcheck-world:  tested, failed
Implements feature:       not tested
Spec compliant:           not tested
Documentation:            not tested

On linux/gcc the patch generates a warning in nodeAgg.c that is fairly easy
to fix.  Using -Werror to make catching the error easier, I get:

make[3]: Entering directory `/home/mark/postgresql.clean/src/backend/executor'
gcc -Wall -Wmissing-prototypes -Wpointer-arith -Wdeclaration-after-statement -Wendif-labels -Wmissing-format-attribute -Wformat-security -fno-strict-aliasing -fwrapv -O2 -Werror -I../../../src/include -D_GNU_SOURCE   -c -o nodeAgg.o nodeAgg.c -MMD -MP -MF .deps/nodeAgg.Po
cc1: warnings being treated as errors
nodeAgg.c: In function ‘ExecAgg’:
nodeAgg.c:2053: error: ‘result’ may be used uninitialized in this function
make[3]: *** [nodeAgg.o] Error 1
make[3]: Leaving directory `/home/mark/postgresql.clean/src/backend/executor'
make[2]: *** [executor-recursive] Error 2
make[2]: Leaving directory `/home/mark/postgresql.clean/src/backend'
make[1]: *** [all-backend-recurse] Error 2
make[1]: Leaving directory `/home/mark/postgresql.clean/src'
make: *** [all-src-recurse] Error 2


There are two obvious choices to silence the warning:

diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index f059560..8959f5b 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -2066,6 +2066,7 @@ ExecAgg(AggState *node)
                                break;
                        case AGG_PLAIN:
                        case AGG_SORTED:
+                       default:
                                result = agg_retrieve_direct(node);
                                break;
                }

which I like better, because I don't expect it would create
an extra instruction in the compiled code, but also:

diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index f059560..eab2605 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -2050,7 +2050,7 @@ lookup_hash_entries(AggState *aggstate)
 TupleTableSlot *
 ExecAgg(AggState *node)
 {
-       TupleTableSlot *result;
+       TupleTableSlot *result = NULL;
 
        if (!node->agg_done)
        {

  10. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-08T10:30:21Z

    >>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:

 Mark> On linux/gcc the patch generates a warning in nodeAgg.c that is
 Mark> fairly easy to fix.  Using -Werror to make catching the error
 Mark> easier, I get:

what gcc version is this exactly?

-- 
Andrew (irc:RhodiumToad)

  11. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-08T13:47:58Z

    >>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:

 Mark> On my MacBook, `make check-world` gives differences in the
 Mark> contrib modules:

Thanks! Latest cleaned up version of patch is attached.

-- 
Andrew (irc:RhodiumToad)

  12. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-08T15:16:59Z

    > On Mar 8, 2017, at 2:30 AM, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
> 
>>>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:
> 
> Mark> On linux/gcc the patch generates a warning in nodeAgg.c that is
> Mark> fairly easy to fix.  Using -Werror to make catching the error
> Mark> easier, I get:
> 
> what gcc version is this exactly?
> 

Linux version 2.6.32-573.18.1.el6.x86_64 (mockbuild@c6b8.bsys.dev.centos.org) (gcc version 4.4.7 20120313 (Red Hat 4.4.7-16) (GCC) ) #1 SMP Tue Feb 9 22:46:17 UTC 2016

  13. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-08T16:00:06Z

    > On Mar 8, 2017, at 5:47 AM, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
> 
>>>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:
> 
> Mark> On my MacBook, `make check-world` gives differences in the
> Mark> contrib modules:
> 
> Thanks! Latest cleaned up version of patch is attached.

This fixes both the warning and the contrib tests on linux and mac.

  14. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-08T16:39:37Z

    Hi Andrew,

Reviewing the patch a bit more, I find it hard to understand the comment about
passing -1 as a flag for finalize_aggregates.  Any chance you can spend a bit
more time word-smithing that code comment?


@@ -1559,7 +1647,9 @@ prepare_projection_slot(AggState *aggstate, TupleTableSlot *slot, int currentSet
 /*
  * Compute the final value of all aggregates for one group.
  *
- * This function handles only one grouping set at a time.
+ * This function handles only one grouping set at a time.  But in the hash
+ * case, it's the caller's responsibility to have selected the set already, and
+ * we pass in -1 here to flag that and to control the indexing into pertrans.
  *
  * Results are stored in the output econtext aggvalues/aggnulls.
  */
@@ -1575,10 +1665,11 @@ finalize_aggregates(AggState *aggstate,
    int         aggno;
    int         transno;

-   Assert(currentSet == 0 ||
-          ((Agg *) aggstate->ss.ps.plan)->aggstrategy != AGG_HASHED);
-
-   aggstate->current_set = currentSet;
+   /* ugly hack for hash */
+   if (currentSet >= 0)
+       select_current_set(aggstate, currentSet, false);
+   else
+       currentSet = 0;


> On Mar 8, 2017, at 8:00 AM, Mark Dilger <hornschnorter@gmail.com> wrote:
> 
> 
>> On Mar 8, 2017, at 5:47 AM, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
>> 
>>>>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:
>> 
>> Mark> On my MacBook, `make check-world` gives differences in the
>> Mark> contrib modules:
>> 
>> Thanks! Latest cleaned up version of patch is attached.
> 
> This fixes both the warning and the contrib tests on linux and mac.
>

  15. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-08T17:40:56Z

    >>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:

 Mark> Hi Andrew,

 Mark> Reviewing the patch a bit more, I find it hard to understand the
 Mark> comment about passing -1 as a flag for finalize_aggregates.  Any
 Mark> chance you can spend a bit more time word-smithing that code
 Mark> comment?

Sure.

How does this look for wording (I'll incorporate it into an updated
patch later):

/*
 * Compute the final value of all aggregates for one group.
 *
 * This function handles only one grouping set at a time.  But in the hash
 * case, it's the caller's responsibility to have selected the set already, and
 * we pass in -1 as currentSet here to flag that; this also changes how we
 * handle the indexing into AggStatePerGroup as explained below.
 *
 * Results are stored in the output econtext aggvalues/aggnulls.
 */
static void
finalize_aggregates(AggState *aggstate,
					AggStatePerAgg peraggs,
					AggStatePerGroup pergroup,
					int currentSet)
{
	ExprContext *econtext = aggstate->ss.ps.ps_ExprContext;
	Datum	   *aggvalues = econtext->ecxt_aggvalues;
	bool	   *aggnulls = econtext->ecxt_aggnulls;
	int			aggno;
	int			transno;

	/*
	 * If currentSet >= 0, then we're doing sorted grouping, and pergroup is an
	 * array of size numTrans*numSets which we have to index into using
	 * currentSet in addition to transno. The caller may not have selected the
	 * set, so we do that.
	 *
	 * If currentSet < 0, then we're doing hashed grouping, and pergroup is an
	 * array of only numTrans items (since for hashed grouping, each grouping
	 * set is in a separate hashtable).  We rely on the caller having done
	 * select_current_set, and we fudge currentSet to 0 in order to make the
	 * same indexing calculations work as for the grouping case.
	 */
	if (currentSet >= 0)
		select_current_set(aggstate, currentSet, false);
	else
		currentSet = 0;


-- 
Andrew (irc:RhodiumToad)

  16. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-08T17:54:22Z

    > On Mar 8, 2017, at 9:40 AM, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
> 
>>>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:
> 
> Mark> Hi Andrew,
> 
> Mark> Reviewing the patch a bit more, I find it hard to understand the
> Mark> comment about passing -1 as a flag for finalize_aggregates.  Any
> Mark> chance you can spend a bit more time word-smithing that code
> Mark> comment?
> 
> Sure.
> 
> How does this look for wording (I'll incorporate it into an updated
> patch later):

Much better.  Thanks!

> /*
> * Compute the final value of all aggregates for one group.
> *
> * This function handles only one grouping set at a time.  But in the hash
> * case, it's the caller's responsibility to have selected the set already, and
> * we pass in -1 as currentSet here to flag that; this also changes how we
> * handle the indexing into AggStatePerGroup as explained below.
> *
> * Results are stored in the output econtext aggvalues/aggnulls.
> */
> static void
> finalize_aggregates(AggState *aggstate,
> 					AggStatePerAgg peraggs,
> 					AggStatePerGroup pergroup,
> 					int currentSet)
> {
> 	ExprContext *econtext = aggstate->ss.ps.ps_ExprContext;
> 	Datum	   *aggvalues = econtext->ecxt_aggvalues;
> 	bool	   *aggnulls = econtext->ecxt_aggnulls;
> 	int			aggno;
> 	int			transno;
> 
> 	/*
> 	 * If currentSet >= 0, then we're doing sorted grouping, and pergroup is an
> 	 * array of size numTrans*numSets which we have to index into using
> 	 * currentSet in addition to transno. The caller may not have selected the
> 	 * set, so we do that.
> 	 *
> 	 * If currentSet < 0, then we're doing hashed grouping, and pergroup is an
> 	 * array of only numTrans items (since for hashed grouping, each grouping
> 	 * set is in a separate hashtable).  We rely on the caller having done
> 	 * select_current_set, and we fudge currentSet to 0 in order to make the
> 	 * same indexing calculations work as for the grouping case.
> 	 */
> 	if (currentSet >= 0)
> 		select_current_set(aggstate, currentSet, false);
> 	else
> 		currentSet = 0;
> 
> 
> -- 
> Andrew (irc:RhodiumToad)

  17. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-08T18:12:50Z

    >>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:

 Mark> Hi Andrew,

 Mark> Reviewing the patch a bit more, I find it hard to understand the
 Mark> comment about passing -1 as a flag for finalize_aggregates.  Any
 Mark> chance you can spend a bit more time word-smithing that code
 Mark> comment?

Actually, ignore that prior response, I'll refactor it a bit to remove
the need for the comment at all.

-- 
Andrew (irc:RhodiumToad)

  18. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-08T18:30:01Z

    >>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:

 Mark> Reviewing the patch a bit more, I find it hard to understand the
 Mark> comment about passing -1 as a flag for finalize_aggregates.  Any
 Mark> chance you can spend a bit more time word-smithing that code
 Mark> comment?
 
 >> Sure.
 >> 
 >> How does this look for wording (I'll incorporate it into an updated
 >> patch later):

 Mark> Much better.  Thanks!

Here's a version of the patch that obviates that comment entirely, by
moving the differences between the hashed and sorted cases out to the
separate callers of finalize_aggregates. 

-- 
Andrew (irc:RhodiumToad)

  19. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-15T21:51:55Z

    Another small update to the patch, this time to eliminate any
possibility of integer overflow when handling extremely large estimated
groupings.

Key change:

-                   k_weights[i] = (int) floor(sz / scale);
+                   /*
+                    * If sz is enormous, but work_mem (and hence scale) is
+                    * small, avoid integer overflow here.
+                    */
+                   k_weights[i] = (int) Min(floor(sz / scale),
+                                            k_capacity + 1.0);

-- 
Andrew (irc:RhodiumToad)

  20. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-22T14:55:27Z

    [snip]

This thread seems to have gone quiet - is it time for me to just go
ahead and commit the thing anyway? Anyone else want to weigh in?

-- 
Andrew (irc:RhodiumToad)

  21. Re: Hash support for grouping sets

    Andres Freund <andres@anarazel.de> — 2017-03-23T00:14:41Z

    Hi,

> +/*
> + * Switch to phase "newphase", which must either be 0 or 1 (to reset) or
>   * current_phase + 1. Juggle the tuplesorts accordingly.
>   */
>  static void
>  initialize_phase(AggState *aggstate, int newphase)
>  {
> -	Assert(newphase == 0 || newphase == aggstate->current_phase + 1);
> +	Assert(newphase <= 1 || newphase == aggstate->current_phase + 1);

I think this somewhere in the file header needs an expanded explanation
about what these "special" phases mean.


> @@ -838,17 +897,21 @@ advance_transition_function(AggState *aggstate,
>  /*
>   * Advance each aggregate transition state for one input tuple.  The input
>   * tuple has been stored in tmpcontext->ecxt_outertuple, so that it is
> - * accessible to ExecEvalExpr.  pergroup is the array of per-group structs to
> - * use (this might be in a hashtable entry).
> + * accessible to ExecEvalExpr.
> + *
> + * We have two sets of transition states to handle: one for sorted aggregation
> + * and one for hashed; we do them both here, to avoid multiple evaluation of
> + * the inputs.
>   *
>   * When called, CurrentMemoryContext should be the per-query context.
>   */

Changes to advance_aggregates() are, in my experience, quite likely to
have performance effects.  This needs some performance tests.

I scheduled a small TPCH comparison run:

master q01 min: 28924.766 dev-hash min: 28893.923 [diff -0.11]
master q02 min: 2448.135 dev-hash min: 2430.589 [diff -0.72]
master q03 min: 14596.292 dev-hash min: 14421.054 [diff -1.22]
master q04 min: 1999.684 dev-hash min: 1958.727 [diff -2.09]
master q05 min: 10638.148 dev-hash min: 10753.075 [diff +1.07]
master q06 min: 3679.955 dev-hash min: 3649.114 [diff -0.85]
master q07 min: 10097.272 dev-hash min: 10358.089 [diff +2.52]
master q08 min: 3103.698 dev-hash min: 3078.108 [diff -0.83]
master q09 min: 13034.87 dev-hash min: 13049.402 [diff +0.11]
master q10 min: 11702.966 dev-hash min: 11535.05 [diff -1.46]
master q11 min: 577.114 dev-hash min: 586.767 [diff +1.65]
master q12 min: 9087.413 dev-hash min: 9272.874 [diff +2.00]
master q13 min: 16353.813 dev-hash min: 16473.882 [diff +0.73]
master q14 min: 1564.321 dev-hash min: 1552.31 [diff -0.77]
master q15 min: 3958.565 dev-hash min: 3946.728 [diff -0.30]
master q16 min: 3793.345 dev-hash min: 3784.996 [diff -0.22]
master q17 min: 828.286 dev-hash min: 834.929 [diff +0.80]
master q18 min: 13473.084 dev-hash min: 13777.327 [diff +2.21]
master q19 min: 654.241 dev-hash min: 673.863 [diff +2.91]
master q20 min: 2906.811 dev-hash min: 2882.793 [diff -0.83]
master q22 min: 1226.397 dev-hash min: 1262.045 [diff +2.82]

master total min: 154649.176 dev-hash min: 155175.645 [diff +0.34]

Looks like it could all be noise, but it seems worthwhile to look into
some.



>   * GROUP BY columns.  The per-group data is allocated in lookup_hash_entry(),
>   * for each entry.
>   *
> - * The hash table always lives in the aggcontext memory context.
> + * We have a separate hashtable and associated perhash data structure for each
> + * grouping set for which we're doing hashing.
> + *
> + * The hash tables always live in the hashcontext's per-tuple memory context
> + * (there is only one of these for all tables together, since they are all
> + * reset at the same time).
>   */

I've not yet read up on the thread, or the whole patch, but an
explanation of the memory management for all those tables would be good
somewhere (maybe I've just not read that far).


> @@ -2388,7 +2597,36 @@ agg_retrieve_hash_table(AggState *aggstate)
>   * ExecInitAgg
>   *
>   *	Creates the run-time information for the agg node produced by the
> - *	planner and initializes its outer subtree
> + *	planner and initializes its outer subtree.
> + *
> + *	What we get from the planner is actually one "real" Agg node which is part
> + *	of the plan tree proper, but which optionally has an additional list of Agg
> + *	nodes hung off the side via the "chain" field.  This is because an Agg node
> + *	happens to be a convenient representation of all the data we need for
> + *	grouping sets.
> + *
> + *	For many purposes, we treat the "real" node as if it were just the first
> + *	node in the chain.  The chain must be ordered such that hashed entries come
> + *	before sorted/plain entries; the real node is marked AGG_MIXED if there are
> + *	mixed types (in which case the real node describes one of the hashed

"mixed types" sounds a bit weird.


> + *	We collect all hashed nodes into a single "phase", numbered 0, and create a
> + *	sorted phase (numbered 1..n) for each AGG_SORTED or AGG_PLAIN node.  Phase
> + *	0 is allocated even if there are no hashes, but remains unused in that
> + *	case.

Ah, here's the explanation I'd been looking for ;)



> +Bitmapset *
> +DiscreteKnapsack(int max_weight, int num_items,
> +				 int *item_weights, double *item_values)
> +{
> +	MemoryContext local_ctx = AllocSetContextCreate(CurrentMemoryContext,
> +													"Knapsack",
> +													ALLOCSET_SMALL_MINSIZE,
> +													ALLOCSET_SMALL_INITSIZE,
> +													ALLOCSET_SMALL_MAXSIZE);
> +	MemoryContext oldctx = MemoryContextSwitchTo(local_ctx);
> +	double	   *values;
> +	Bitmapset **sets;
> +	Bitmapset  *result;
> +	int			i,
> +				j;
> +
> +	Assert(max_weight >= 0);
> +	Assert(num_items > 0 && item_weights);
> +
> +	values = palloc((1 + max_weight) * sizeof(double));
> +	sets = palloc((1 + max_weight) * sizeof(Bitmapset *));

We usually cast the result of palloc.


> +	for (i = 0; i <= max_weight; ++i)
> +	{
> +		values[i] = 0;
> +		sets[i] = bms_make_singleton(num_items);
> +	}
> +
> +	for (i = 0; i < num_items; ++i)
> +	{
> +		int			iw = item_weights[i];
> +		double		iv = item_values ? item_values[i] : 1;
> +
> +		for (j = max_weight; j >= iw; --j)
> +		{
> +			int			ow = j - iw;
> +
> +			if (values[j] <= values[ow] + iv)
> +			{
> +				/* copy sets[ow] to sets[j] without realloc */
> +				if (j != ow)
> +				{
> +					sets[j] = bms_del_members(sets[j], sets[j]);
> +					sets[j] = bms_add_members(sets[j], sets[ow]);
> +				}
> +
> +				sets[j] = bms_add_member(sets[j], i);
> +
> +				values[j] = values[ow] + iv;
> +			}
> +		}
> +	}
> +
> +	MemoryContextSwitchTo(oldctx);
> +
> +	result = bms_del_member(bms_copy(sets[max_weight]), num_items);
> +
> +	MemoryContextDelete(local_ctx);
> +
> +	return result;
> +}

> diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
> index 252af5c870..ea1c538287 100644
> --- a/src/backend/nodes/bitmapset.c
> +++ b/src/backend/nodes/bitmapset.c
> @@ -21,7 +21,7 @@
>  #include "postgres.h"
>  
>  #include "access/hash.h"
> -
> +#include "nodes/pg_list.h"

Pedanticism^7: You're deleting a line here...


> +/*
>   * bms_nonempty_difference - do sets have a nonempty difference?
>   */
>  bool
> diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
> index 7418fbeded..d2d66f915b 100644
> --- a/src/backend/nodes/outfuncs.c
> +++ b/src/backend/nodes/outfuncs.c
> @@ -1936,6 +1936,28 @@ _outAggPath(StringInfo str, const AggPath *node)
>  }
>  
>  static void
> +_outRollupData(StringInfo str, const RollupData *node)
> +{
> +	WRITE_NODE_TYPE("ROLLUP");
> +
> +	WRITE_NODE_FIELD(groupClause);
> +	WRITE_NODE_FIELD(gsets);
> +	WRITE_NODE_FIELD(gsets_data);
> +	WRITE_FLOAT_FIELD(numGroups, "%.0f");
> +	WRITE_BOOL_FIELD(hashable);
> +	WRITE_BOOL_FIELD(is_hashed);
> +}
> +
> +static void
> +_outGroupingSetData(StringInfo str, const GroupingSetData *node)
> +{
> +	WRITE_NODE_TYPE("GSDATA");
> +
> +	WRITE_NODE_FIELD(set);
> +	WRITE_FLOAT_FIELD(numGroups, "%.0f");
> +}

.0f?


> +static grouping_sets_data *
> +preprocess_grouping_sets(PlannerInfo *root)
> +{

It'd not hurt to add a comment as to what this function is actually
doing.


Btw, this would be a lot easier to review if the move to
preprocess_grouping_sets were done in a separate preliminary commit.


> +	if (!bms_is_empty(gd->unsortable_refs))
> +	{
...
> +	}
> +	else
> +		sets = extract_rollup_sets(parse->groupingSets);

I hope there's tests for both these branches.


> +		/*
> +		 * Is it hashable? We pretend empty sets are hashable even though we
> +		 * actually force them not to be hashed later. But don't bother if
> +		 * there's nothing but empty sets.
> +		 */

Why?


> @@ -3214,6 +3407,11 @@ get_number_of_groups(PlannerInfo *root,
>   * estimate_hashagg_tablesize
>   *	  estimate the number of bytes that a hash aggregate hashtable will
>   *	  require based on the agg_costs, path width and dNumGroups.
> + *
> + * XXX this may be over-estimating the size now that hashagg knows to omit
> + * unneeded columns from the hashtable. Also for mixed-mode grouping sets,
> + * grouping columns not in the hashed set are counted here even though hashagg
> + * won't store them. Is this a problem?
>   */

Hm. This seems like it could move us to use sorting, even if not
actually warranted.


> +/*
> + * For a given input path, consider the possible ways of doing grouping sets on
> + * it, by combinations of hashing and sorting.  This can be called multiple
> + * times, so it's important that it not scribble on input.  No result is
> + * returned, but any generated paths are added to grouped_rel.
> + */
> +
> +static void
> +consider_groupingsets_paths(PlannerInfo *root,

What's the newline after the comment about?

> +							RelOptInfo *grouped_rel,
> +							Path *path,
> +							bool is_sorted,
> +							bool can_hash,
> +							PathTarget *target,
> +							grouping_sets_data *gd,
> +							const AggClauseCosts *agg_costs,
> +							double dNumGroups)
> +{
> +	Query	   *parse = root->parse;
> +
> +	/*
> +	 * If we're not being offered sorted input, then only consider plans that
> +	 * can be done entirely by hashing.
> +	 *
> +	 * We can hash everything if it looks like it'll fit in work_mem. But if
> +	 * the input is actually sorted despite not being advertised as such, we
> +	 * prefer to make use of that in order to use less memory.
> +	 * If none of the grouping sets are sortable, then ignore the work_mem
> +	 * limit and generate a path anyway, since otherwise we'll just fail.
> +	 */
> +	if (!is_sorted)
> +	{
> +		List	   *new_rollups = NIL;
> +		RollupData *unhashable_rollup = NULL;
> +		List	   *sets_data;
> +		List	   *empty_sets_data = NIL;
> +		List	   *empty_sets = NIL;
> +		ListCell   *lc;
> +		ListCell   *l_start = list_head(gd->rollups);
> +		AggStrategy strat = AGG_HASHED;
> +		Size		hashsize;
> +		double		exclude_groups = 0.0;
> +
> +		Assert(can_hash);
> +
> +		if (pathkeys_contained_in(root->group_pathkeys, path->pathkeys))
> +		{
> +			unhashable_rollup = lfirst(l_start);

a) cast result of lfirst/lnext/whatnot. b) Why is this guaranteed to be
unhashable?


> +			exclude_groups = unhashable_rollup->numGroups;
> +			l_start = lnext(l_start);
> +		}


What guarantees that such a rollup would be at the start?


> +		hashsize = estimate_hashagg_tablesize(path,
> +											  agg_costs,
> +											  dNumGroups - exclude_groups);
> +
> +		if (hashsize > work_mem * 1024L && gd->rollups)
> +			return;				/* nope, won't fit */

Didn't you above talk about generating a path anyway?  Or is rollups
guaranteed not to be set in that case (if so, not obvious on a casual
read)?


> +	/*
> +	 * If we have sorted input but nothing we can do with it, bail.
> +	 */
> +
> +	if (list_length(gd->rollups) == 0)
> +		return;

Postgres style usually doesn't add a newline before comment and the
block it concerns - you do that all over.


> +	if (can_hash && gd->any_hashable)
> +	{
> +		List	   *rollups = NIL;
> +		List	   *hash_sets = list_copy(gd->unsortable_sets);
> +		double		availspace = (work_mem * 1024.0);

Why the parens, and why the .0?

> +		ListCell   *lc;
> +
> +		/*
> +		 * Account first for space needed for groups we can't sort at all.
> +		 */
> +		availspace -= (double) estimate_hashagg_tablesize(path,
> +														  agg_costs,
> +														  gd->dNumHashGroups);
> +
> +		if (availspace > 0 && list_length(gd->rollups) > 1)
> +		{
> +			double		scale;
> +			int			num_rollups = list_length(gd->rollups);
> +			int			k_capacity;
> +			int		   *k_weights = palloc(num_rollups * sizeof(int));
> +			Bitmapset  *hash_items = NULL;
> +			int			i;
> +
> +			/*
> +			 * To use the discrete knapsack, we need to scale the values to a
> +			 * reasonably small bounded range.  We choose to allow a 5% error
> +			 * margin; we have no more than 4096 rollups in the worst possible
> +			 * case, which with a 5% error margin will require a bit over 42MB
> +			 * of workspace. (Anyone wanting to plan queries that complex had
> +			 * better have the memory for it.  In more reasonable cases, with
> +			 * no more than a couple of dozen rollups, the memory usage will
> +			 * be negligible.)
> +			 *
> +			 * k_capacity is naturally bounded, but we clamp the values for
> +			 * scale and weight (below) to avoid overflows or underflows (or
> +			 * uselessly trying to use a scale factor less than 1 byte).
> +			 */

I think you need a higher level explanation of how you're mapping the
work_mem issue to knapsack somewhere.



> +			/*
> +			 * Apply knapsack algorithm; compute the set of items which
> +			 * maximizes the value stored (in this case the number of sorts
> +			 * saved) while keeping the total size (approximately) within
> +			 * capacity.
> +			 */

Hm.  So we're solely optimizing for the number of sorts, rather the cost
of the sorts.  Probably an acceptable tradeoff.

> +}

Phew, this isn't simple. Need to be more awake than I'm 8 hours into a
flight.


> @@ -737,7 +739,8 @@ typedef enum AggStrategy
>  {
>  	AGG_PLAIN,					/* simple agg across all input rows */
>  	AGG_SORTED,					/* grouped agg, input must be sorted */
> -	AGG_HASHED					/* grouped agg, use internal hashtable */
> +	AGG_HASHED,					/* grouped agg, use internal hashtable */
> +	AGG_MIXED					/* grouped agg, hash and sort concurrently */
>  } AggStrategy;

Concurrently sounds a bit like using multiple processes / parallelism...


- Andres

  22. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-23T03:43:57Z

    >>>>> "Andres" == Andres Freund <andres@anarazel.de> writes:

 Andres> Changes to advance_aggregates() are, in my experience, quite
 Andres> likely to have performance effects.  This needs some
 Andres> performance tests.
 [...]
 Andres> Looks like it could all be noise, but it seems worthwhile to
 Andres> look into some.

Trying to sort out signal from noise when dealing with performance
impacts of no more than a few percent is _extremely hard_ these days.

Remember this, from a couple of years back?  http://tinyurl.com/op9qg8a

That's a graph of performance results from tests where the only change
being made was adding padding bytes to a function that was never called
during the test. Performance differences on the order of 3% were being
introduced by doing nothing more than changing the actual memory
locations of functions.

My latest round of tests on this patch shows a similar effect. Here's
one representative test timing (a select count(*) with no grouping sets
involved):

                         master: 5727ms
                     gsets_hash: 5949ms
 gsets_hash + 500 padding bytes: 5680ms

Since the effect of padding is going to vary over time as other,
unrelated, patches happen, I think I can safely claim that the
performance of the patch at least overlaps the noise range of the
performance of current code.  To get a more definitive result, it would
be necessary to run at least some dozens of tests, with different
padding sizes, and determine whether the average changes detectably
between the two versions.  I will go ahead and do this, out of sheer
curiosity if nothing else, but the preliminary results suggest there's
probably nothing worth holding up the patch for.

-- 
Andrew (irc:RhodiumToad)

  23. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-23T03:49:46Z

    > On Mar 22, 2017, at 8:09 AM, Mark Dilger <hornschnorter@gmail.com> wrote:
> 
> 
>> On Mar 22, 2017, at 7:55 AM, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
>> 
>> [snip]
>> 
>> This thread seems to have gone quiet - is it time for me to just go
>> ahead and commit the thing anyway? Anyone else want to weigh in?
> 
> Sorry for the delay.  I'll try to look at this today.  Others are most welcome
> to weigh in.

You define DiscreteKnapsack to take integer weights and double values,
and perform the usual Dynamic Programming algorithm to solve.  But
the only place you call this, you pass in NULL for the values, indicating
that all the values are equal.  I'm confused why in this degenerate case
you bother with the DP at all.  Can't you just load the knapsack from
lightest to heaviest after sorting, reducing the runtime complexity to O(nlogn)?
It's been a long day.  Sorry if I am missing something obvious.

I'm guessing you intend to extend the code at some later date to have
different values for items.  Is that right?

I reapplied your patch and reran the regression tests on my laptop and they
all pass.

mark

  24. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-23T05:09:46Z

    >>>>> "Andres" == Andres Freund <andres@anarazel.de> writes:

 >> -	Assert(newphase == 0 || newphase == aggstate->current_phase + 1);
 >> +	Assert(newphase <= 1 || newphase == aggstate->current_phase + 1);

 Andres> I think this somewhere in the file header needs an expanded
 Andres> explanation about what these "special" phases mean.

I could move most of the block comment for ExecInitAgg up into the file
header; would that be better?

 Andres> I've not yet read up on the thread, or the whole patch, but an
 Andres> explanation of the memory management for all those tables would
 Andres> be good somewhere (maybe I've just not read that far).

I can expand on that.

 Andres> "mixed types" sounds a bit weird.

changing to "if there are both types present"

 >> +	values = palloc((1 + max_weight) * sizeof(double));
 >> +	sets = palloc((1 + max_weight) * sizeof(Bitmapset *));

 Andres> We usually cast the result of palloc.

Rough count in the backend has ~400 without casts to ~1350 with, so this
doesn't seem to have been consistently enforced.

 >> +static void
 >> +_outGroupingSetData(StringInfo str, const GroupingSetData *node)
 >> +{
 >> +	WRITE_NODE_TYPE("GSDATA");
 >> +
 >> +	WRITE_NODE_FIELD(set);
 >> +	WRITE_FLOAT_FIELD(numGroups, "%.0f");
 >> +}

 Andres> .0f?

Copied from every other node that uses "%.0f" to write out a numGroups
value.

 >> +static grouping_sets_data *
 >> +preprocess_grouping_sets(PlannerInfo *root)
 >> +{

 Andres> It'd not hurt to add a comment as to what this function is
 Andres> actually doing.

Sure.

 Andres> I hope there's tests for both these branches.

A number of tests for both unsortable and unhashable cases are in the
regression test.

 >> +		/*
 >> +		 * Is it hashable? We pretend empty sets are hashable even though we
 >> +		 * actually force them not to be hashed later. But don't bother if
 >> +		 * there's nothing but empty sets.
 >> +		 */

 Andres> Why?

If there's no non-empty grouping set then there's nothing to hash (the
hash code assumes at least one column). I'll put that in the comment.

 >> @@ -3214,6 +3407,11 @@ get_number_of_groups(PlannerInfo *root,
 >> * estimate_hashagg_tablesize
 >> *	  estimate the number of bytes that a hash aggregate hashtable will
 >> *	  require based on the agg_costs, path width and dNumGroups.
 >> + *
 >> + * XXX this may be over-estimating the size now that hashagg knows to omit
 >> + * unneeded columns from the hashtable. Also for mixed-mode grouping sets,
 >> + * grouping columns not in the hashed set are counted here even though hashagg
 >> + * won't store them. Is this a problem?
 >> */

 Andres> Hm. This seems like it could move us to use sorting, even if
 Andres> not actually warranted.

This is largely a pre-existing issue that this patch doesn't try and
fix.  That would be an issue for a separate patch, I think.  I merely
added the comment to point it out.

 Andres> What's the newline after the comment about?

Old style habits die hard.

 >> +							RelOptInfo *grouped_rel,
 >> +							Path *path,
 >> +							bool is_sorted,
 >> +							bool can_hash,
 >> +							PathTarget *target,
 >> +							grouping_sets_data *gd,
 >> +							const AggClauseCosts *agg_costs,
 >> +							double dNumGroups)
 >> +{
 >> +	Query	   *parse = root->parse;
 >> +
 >> +	/*
 >> +	 * If we're not being offered sorted input, then only consider plans that
 >> +	 * can be done entirely by hashing.
 >> +	 *
 >> +	 * We can hash everything if it looks like it'll fit in work_mem. But if
 >> +	 * the input is actually sorted despite not being advertised as such, we
 >> +	 * prefer to make use of that in order to use less memory.
 >> +	 * If none of the grouping sets are sortable, then ignore the work_mem
 >> +	 * limit and generate a path anyway, since otherwise we'll just fail.
 >> +	 */
 >> +	if (!is_sorted)
 >> +	{
 >> +		List	   *new_rollups = NIL;
 >> +		RollupData *unhashable_rollup = NULL;
 >> +		List	   *sets_data;
 >> +		List	   *empty_sets_data = NIL;
 >> +		List	   *empty_sets = NIL;
 >> +		ListCell   *lc;
 >> +		ListCell   *l_start = list_head(gd->rollups);
 >> +		AggStrategy strat = AGG_HASHED;
 >> +		Size		hashsize;
 >> +		double		exclude_groups = 0.0;
 >> +
 >> +		Assert(can_hash);
 >> +
 >> +		if (pathkeys_contained_in(root->group_pathkeys, path->pathkeys))
 >> +		{
 >> +			unhashable_rollup = lfirst(l_start);

 Andres> a) cast result of lfirst/lnext/whatnot.

casting lfirst is defensible (and only about 10% of existing uses don't
cast it), but why would you ever cast the result of lnext?

 Andres> b) Why is this guaranteed to be unhashable?

It might not be unhashable; that probably needs a better name. It's the
rollup that we aren't going to hash because we're being presented with
input already in correct order. Also, it's the only rollup that can
contain empty grouping sets, which the hash code can't cope with.

Obviously this needs a comment and some consideration of naming.

 >> +		if (hashsize > work_mem * 1024L && gd->rollups)
 >> +			return;				/* nope, won't fit */

 Andres> Didn't you above talk about generating a path anyway?  Or is
 Andres> rollups guaranteed not to be set in that case (if so, not
 Andres> obvious on a casual read)?

Unsortable groups can't participate in rollups. The presence of a rollup
implies that we're going to be offered at least one is_sorted input
path.

 >> +	if (can_hash && gd->any_hashable)
 >> +	{
 >> +		List	   *rollups = NIL;
 >> +		List	   *hash_sets = list_copy(gd->unsortable_sets);
 >> +		double		availspace = (work_mem * 1024.0);

 Andres> Why the parens, and why the .0?

The .0 is because the * should be done as a double, not an int.  This
isn't an uncommon idiom, there are quite a few similar uses in the
planner alone.

The parens because I thought it was clearer that way.

 Andres> I think you need a higher level explanation of how you're
 Andres> mapping the work_mem issue to knapsack somewhere.

The general overview ("work_mem is the knapsack size, and we need to
figure out how best to pack it with hashtables"), or the specific issue
of the scale factor for discrete chunking of the size?

 Andres> Hm.  So we're solely optimizing for the number of sorts, rather
 Andres> the cost of the sorts.  Probably an acceptable tradeoff.

The existing cost model for sorts doesn't actually seem to help us here;
all of our sorts sort the same data, just with different comparison
columns, but cost_sort doesn't actually account for that (all its
callers except the CLUSTER planning code pass in 0.0 for
comparison_cost).

If the sort costs were correct, we could compute a "value" for each
rollup that reflected the cost difference between the sort+unique
comparisons for it, and the hash functions that would be called if we
hashed instead; and just pass that to the knapsack function.

-- 
Andrew (irc:RhodiumToad)

  25. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-23T18:22:10Z

    >>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:

 Mark> You define DiscreteKnapsack to take integer weights and double
 Mark> values, and perform the usual Dynamic Programming algorithm to
 Mark> solve.  But the only place you call this, you pass in NULL for
 Mark> the values, indicating that all the values are equal.  I'm
 Mark> confused why in this degenerate case you bother with the DP at
 Mark> all.  Can't you just load the knapsack from lightest to heaviest
 Mark> after sorting, reducing the runtime complexity to O(nlogn)?  It's
 Mark> been a long day.  Sorry if I am missing something obvious.

That's actually a very good question.

(Though in passing I should point out that the runtime cost is going to
be negligible in all practical cases. Even an 8-way cube (256 grouping
sets) has only 70 rollups, and a 4-way cube has only 6; the limit of
4096 grouping sets was only chosen because it was a nice round number
that was larger than comparable limits in other database products. Other
stuff in the grouping sets code has worse time bounds; the
bipartite-match code used to minimize the number of rollups is
potentially O(n^2.5) in the number of grouping sets.)

Thinking about it, it's not at all obvious what we should be optimizing
for here in the absence of accurate sort costs. Right now what matters
is saving as many sort steps as possible, since that's a saving likely
to be many orders of magnitude greater than the differences between two
sorts. The one heuristic that might be useful is to prefer the smaller
estimated size if other factors are equal, just on memory usage grounds,
but even that seems a bit tenuous.

I'm inclined to leave things as they are in the current patch, and maybe
revisit it during beta if we get any relevant feedback from people
actually using grouping sets?

 Mark> I'm guessing you intend to extend the code at some later date to
 Mark> have different values for items.  Is that right?

Well, as I mentioned in a reply to Andres, we probably should eventually
optimize for greatest reduction in cost, and the code as it stands would
allow that to be added easily, but that would require having more
accurate cost info than we have now. cost_sort doesn't take into
consideration the number or types of sort columns or the costs of their
comparison functions, so all sorts of the same input data are costed
equally.

-- 
Andrew (irc:RhodiumToad)

  26. Re: Hash support for grouping sets

    Andres Freund <andres@anarazel.de> — 2017-03-23T18:42:43Z

    On 2017-03-23 03:43:57 +0000, Andrew Gierth wrote:
> >>>>> "Andres" == Andres Freund <andres@anarazel.de> writes:
> 
>  Andres> Changes to advance_aggregates() are, in my experience, quite
>  Andres> likely to have performance effects.  This needs some
>  Andres> performance tests.
>  [...]
>  Andres> Looks like it could all be noise, but it seems worthwhile to
>  Andres> look into some.
> 
> Trying to sort out signal from noise when dealing with performance
> impacts of no more than a few percent is _extremely hard_ these days.

Indeed. But that doesn't mean we needn't try.  With some determination
and profiling you can often sepearate signal from noise - I managed to
track down 0.12% regressions in the expression evaluation work...


> I will go ahead and do this, out of sheer curiosity if nothing else,
> but the preliminary results suggest there's probably nothing worth
> holding up the patch for.

Agreed. I'd want to run one more profile, checking whether the profiles
indicate new hotspots, but other than that...

Greetings,

Andres Freund

  27. Re: Hash support for grouping sets

    Mark Dilger <hornschnorter@gmail.com> — 2017-03-23T18:46:39Z

    > On Mar 23, 2017, at 11:22 AM, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
> 
>>>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:
> 
> Mark> You define DiscreteKnapsack to take integer weights and double
> Mark> values, and perform the usual Dynamic Programming algorithm to
> Mark> solve.  But the only place you call this, you pass in NULL for
> Mark> the values, indicating that all the values are equal.  I'm
> Mark> confused why in this degenerate case you bother with the DP at
> Mark> all.  Can't you just load the knapsack from lightest to heaviest
> Mark> after sorting, reducing the runtime complexity to O(nlogn)?  It's
> Mark> been a long day.  Sorry if I am missing something obvious.
> 
> That's actually a very good question.
> 
> (Though in passing I should point out that the runtime cost is going to
> be negligible in all practical cases. Even an 8-way cube (256 grouping
> sets) has only 70 rollups, and a 4-way cube has only 6; the limit of
> 4096 grouping sets was only chosen because it was a nice round number
> that was larger than comparable limits in other database products. Other
> stuff in the grouping sets code has worse time bounds; the
> bipartite-match code used to minimize the number of rollups is
> potentially O(n^2.5) in the number of grouping sets.)
> 
> Thinking about it, it's not at all obvious what we should be optimizing
> for here in the absence of accurate sort costs.

Is there a performance test case where this patch should shine
brightest?  I'd like to load a schema with lots of data, and run
a grouping sets query, both before and after applying the patch,
to see what the performance advantage is.

mark

  28. Re: Hash support for grouping sets

    Andres Freund <andres@anarazel.de> — 2017-03-23T18:53:44Z

    On 2017-03-23 05:09:46 +0000, Andrew Gierth wrote:
> >>>>> "Andres" == Andres Freund <andres@anarazel.de> writes:
> 
>  >> -	Assert(newphase == 0 || newphase == aggstate->current_phase + 1);
>  >> +	Assert(newphase <= 1 || newphase == aggstate->current_phase + 1);
> 
>  Andres> I think this somewhere in the file header needs an expanded
>  Andres> explanation about what these "special" phases mean.
> 
> I could move most of the block comment for ExecInitAgg up into the file
> header; would that be better?

Yes, I think so.


>  >> +	values = palloc((1 + max_weight) * sizeof(double));
>  >> +	sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
> 
>  Andres> We usually cast the result of palloc.
> 
> Rough count in the backend has ~400 without casts to ~1350 with, so this
> doesn't seem to have been consistently enforced.

Yea, but we're still trying.

>  >> +							RelOptInfo *grouped_rel,
>  >> +							Path *path,
>  >> +							bool is_sorted,
>  >> +							bool can_hash,
>  >> +							PathTarget *target,
>  >> +							grouping_sets_data *gd,
>  >> +							const AggClauseCosts *agg_costs,
>  >> +							double dNumGroups)
>  >> +{
>  >> +	Query	   *parse = root->parse;
>  >> +
>  >> +	/*
>  >> +	 * If we're not being offered sorted input, then only consider plans that
>  >> +	 * can be done entirely by hashing.
>  >> +	 *
>  >> +	 * We can hash everything if it looks like it'll fit in work_mem. But if
>  >> +	 * the input is actually sorted despite not being advertised as such, we
>  >> +	 * prefer to make use of that in order to use less memory.
>  >> +	 * If none of the grouping sets are sortable, then ignore the work_mem
>  >> +	 * limit and generate a path anyway, since otherwise we'll just fail.
>  >> +	 */
>  >> +	if (!is_sorted)
>  >> +	{
>  >> +		List	   *new_rollups = NIL;
>  >> +		RollupData *unhashable_rollup = NULL;
>  >> +		List	   *sets_data;
>  >> +		List	   *empty_sets_data = NIL;
>  >> +		List	   *empty_sets = NIL;
>  >> +		ListCell   *lc;
>  >> +		ListCell   *l_start = list_head(gd->rollups);
>  >> +		AggStrategy strat = AGG_HASHED;
>  >> +		Size		hashsize;
>  >> +		double		exclude_groups = 0.0;
>  >> +
>  >> +		Assert(can_hash);
>  >> +
>  >> +		if (pathkeys_contained_in(root->group_pathkeys, path->pathkeys))
>  >> +		{
>  >> +			unhashable_rollup = lfirst(l_start);
> 
>  Andres> a) cast result of lfirst/lnext/whatnot.
> 
> casting lfirst is defensible (and only about 10% of existing uses don't
> cast it), but why would you ever cast the result of lnext?

Obviously lnext is bogus, was thinking of linitial...

>  >> +	if (can_hash && gd->any_hashable)
>  >> +	{
>  >> +		List	   *rollups = NIL;
>  >> +		List	   *hash_sets = list_copy(gd->unsortable_sets);
>  >> +		double		availspace = (work_mem * 1024.0);
> 
>  Andres> Why the parens, and why the .0?
> 
> The .0 is because the * should be done as a double, not an int.

I was just missing why - but now that I've not already been awake for 20
hours, 8 of those crammed into a plane, it's obviously beneficial
because of overflow concerns.


>  Andres> I think you need a higher level explanation of how you're
>  Andres> mapping the work_mem issue to knapsack somewhere.
> 
> The general overview ("work_mem is the knapsack size, and we need to
> figure out how best to pack it with hashtables"), or the specific issue
> of the scale factor for discrete chunking of the size?

The general overview - the scaling thing doesn't seem that important to
understand in detail, to understand the approach.  Briefly explaining
what we're trying to minimize (sort steps), what the constraint is
(memory), that the problem is representable as the classic "knapsack
problem".


>  Andres> Hm.  So we're solely optimizing for the number of sorts, rather
>  Andres> the cost of the sorts.  Probably an acceptable tradeoff.
> 
> The existing cost model for sorts doesn't actually seem to help us here;
> all of our sorts sort the same data, just with different comparison
> columns, but cost_sort doesn't actually account for that (all its
> callers except the CLUSTER planning code pass in 0.0 for
> comparison_cost).
> 
> If the sort costs were correct, we could compute a "value" for each
> rollup that reflected the cost difference between the sort+unique
> comparisons for it, and the hash functions that would be called if we
> hashed instead; and just pass that to the knapsack function.

That'd indeed be desirable - but I think we can punt on that for now.

Greetings,

Andres Freund

  29. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-23T20:07:38Z

    >>>>> "Mark" == Mark Dilger <hornschnorter@gmail.com> writes:

 Mark> Is there a performance test case where this patch should shine
 Mark> brightest?  I'd like to load a schema with lots of data, and run
 Mark> a grouping sets query, both before and after applying the patch,
 Mark> to see what the performance advantage is.

The area which I think is most important for performance is the handling
of small cubes; without this patch, a 2d cube needs 2 full sorts, a 3d
one needs 3, and a 4d one needs 6. In many real-world data sets these
would all hash entirely in memory.

So here's a very simple example (deliberately using integers for
grouping to minimize the advantage; grouping by text columns in a non-C
locale would show a much greater speedup for the patch):

create table sales (
  id serial,
  product_id integer,
  store_id integer,
  customer_id integer,
  qty integer);

-- random integer function
create function d(integer) returns integer language sql
 as $f$ select floor(random()*$1)::integer + 1; $f$;

-- 10 million random rows
insert into sales (product_id,store_id,customer_id,qty)
  select d(20), d(6), d(10), d(100) from generate_series(1,10000000);

-- example 2d cube:
select product_id, store_id, count(*), sum(qty)
  from sales
 group by cube(product_id, store_id);

-- example 3d cube:
select product_id, store_id, customer_id, count(*), sum(qty)
  from sales
 group by cube(product_id, store_id, customer_id);

-- example 4d cube with a computed column:
select product_id, store_id, customer_id, (qty / 10), count(*), sum(qty)
  from sales
 group by cube(product_id, store_id, customer_id, (qty / 10));

On my machine, the 2d cube is about 3.6 seconds with the patch, and
about 8 seconds without it; the 4d is about 18 seconds with the patch
and about 32 seconds without it (all with work_mem=1GB, compiled with
-O2 and assertions off).

-- 
Andrew (irc:RhodiumToad)

  30. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-23T22:45:36Z

    >>>>> "Andres" == Andres Freund <andres@anarazel.de> writes:

 Andres> We usually cast the result of palloc.

 >> Rough count in the backend has ~400 without casts to ~1350 with, so
 >> this doesn't seem to have been consistently enforced.

 Andres> Yea, but we're still trying.

Well, a lot of the uncasted ones are in fairly new code, from quite a
number of different committers.

So if this is a big deal, why don't we already have

#define palloc_array(etype,ecount) (((etype) *) palloc((ecount) * sizeof(etype)))
#define palloc_object(otype) (((otype) *) palloc(sizeof(otype)))

or something of that ilk?

-- 
Andrew (irc:RhodiumToad)

  31. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-23T23:10:45Z

    >>>>> "Andres" == Andres Freund <andres@anarazel.de> writes:

 Andres> a) cast result of lfirst/lnext/whatnot.

Again, what we need here is something like

#define lfirst_node(_type_, l) (castNode(_type_, lfirst(l)))

etc.

-- 
Andrew (irc:RhodiumToad)

  32. Re: Hash support for grouping sets

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2017-03-24T23:39:30Z

    >>>>> "Andres" == Andres Freund <andres@anarazel.de> writes:

 >> I could move most of the block comment for ExecInitAgg up into the
 >> file header; would that be better?

 Andres> Yes, I think so.

Done that and some other clarifications. Attached is the latest patch;
no substantive changes, only comments, formatting and a change to a
variable name.

The performance side of things I'm still working on; I think that would
be best handled as a followup patch.

-- 
Andrew (irc:RhodiumToad)