Support hashed aggregation with grouping sets.

This extends the Aggregate node with two new features: HashAggregate
can now run multiple hashtables concurrently, and a new strategy
MixedAggregate populates hashtables while doing sorted grouping.

The planner will now attempt to save as many sorts as possible when
planning grouping sets queries, while not exceeding work_mem for the
estimated combined sizes of all hashtables used.  No SQL-level changes
are required.  There should be no user-visible impact other than the
new EXPLAIN output and possible changes to result ordering when ORDER
BY was not used (which affected a few regression tests).  The
enable_hashagg option is respected.

Author: Andrew Gierth
Reviewers: Mark Dilger, Andres Freund
Discussion: https://postgr.es/m/87vatszyhj.fsf@news-spur.riddles.org.uk

1 files changed, 30 insertions, 0 deletions

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 252af5c8709..bf8545d4378 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -21,6 +21,7 @@
 #include "postgres.h"
 
 #include "access/hash.h"
+#include "nodes/pg_list.h"
 
 
 #define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
@@ -458,6 +459,35 @@ bms_overlap(const Bitmapset *a, const Bitmapset *b)
 }
 
 /*
+ * bms_overlap_list - does a set overlap an integer list?
+ */
+bool
+bms_overlap_list(const Bitmapset *a, const List *b)
+{
+	ListCell   *lc;
+	int			wordnum,
+				bitnum;
+
+	if (a == NULL || b == NIL)
+		return false;
+
+	foreach(lc, b)
+	{
+		int			x = lfirst_int(lc);
+
+		if (x < 0)
+			elog(ERROR, "negative bitmapset member not allowed");
+		wordnum = WORDNUM(x);
+		bitnum = BITNUM(x);
+		if (wordnum < a->nwords)
+			if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
+				return true;
+	}
+
+	return false;
+}
+
+/*
  * bms_nonempty_difference - do sets have a nonempty difference?
  */
 bool