Subject: Re: Reduce TupleHashEntryData struct size by half

From: Heikki Linnakangas <[email-masked]>
Date: Mon, 18 Nov 2024 12:13:50 +0200

On 18/11/2024 02:01, Jeff Davis wrote:
> 
> TupleHashEntryData is the size of a hash bucket, and it's currently 24
> bytes. The size of the structure is important for HashAgg and other
> callers that can build up large hashtables of small tuples. Waste in
> this structure is even worse when the hash table is sparse, because the
> space is consumed whether the bucket is occupied or not.
> 
> The attached patch series brings it down to 12. There are several
> unappealing hacks, so ideally we'd find something cleaner, but halving
> the bucket size seems quite desirable if it can be done in an
> acceptable way.

Makes sense.

> 0001: This patch makes the structure private, so that it's easier to
> control the way the structure is accessed.

Seems pretty uncontroversial. You removed the typedef for struct 
TupleHashEntryData, which is a bit unusual for our usual source style. 
Was there a reason for that?

> 0002: Removes the "additional" pointer, instead storing it right after
> the tuple, which is already stored in a separate chunk. Hack: this
> crams the "additional" pointer after the MinimalTuple in the same chunk
> of memory to avoid adding additional palloc()s.

Hmm, it would seem more straightforward to store it in the beginning, 
i.e. have something like this:

struct {
      void *additional;
      MinimalTupleData mtup;
} ;

Come to think of it, how important is it that we use MinimalTuple here 
at all? Some other representation could be faster to deal with in 
TupleHashTableMatch() anyway.

> 0003: simplehash: allow the caller to decide which entries are empty vs
> in-use rather than requiring a separate "status" field. This may limit
> other possible status values in the future (i.e. adding on to the
> enum), but I'm not sure what those other stutus values might be.

+1. I've wanted to have this in the past.

> 0004: Removes the "status" field from TupleHashEntryData, using
> firstTuple==NULL to mean "empty", otherwise "in use". Hack: need an
> additional "special" pointer value to mean "input slot" now that NULL
> means "empty".

+1

> 0005: Pack TupleHashEntryData. IIUC, this is fine even on machines that
> can't do unaligned access, so long as we are accessing the fields
> through the struct, and not taking the address of individual members.

Seems OK.

I wonder if the compiler understands that the elements are still 4-byte 
aligned, or if it forces byte-per-byte access? Playing with godbolt a 
little, it seems like GCC at least understands it, but clang does not. 
On architectures with non-strict alignment, it doesn't matter as a 
simple load/store instruction is the fastest option anyway.

-- 
Heikki Linnakangas
Neon (https://neon.tech)

---

From: Jeff Davis <[email-masked]>
Date: Mon, 18 Nov 2024 12:22:28 -0800

> Was there a reason for that?

If it's private to a file and I don't intend to use it a lot, I do it
to cut down typedefs.list bloat. I'll go ahead and add the typedef back
to match the style, though.

> i.e. have something like this:

That was my first approach, but it requires an additional memcpy,
because ExecCopySlotMinimalTuple() does it's own palloc. I used
repalloc() because it will often have space at the end of the chunk
anyway, and not need to memcpy(). Maybe that's not significant but it
did seem detectable in some perf tests.

But perhaps we can go further and get rid of the "additional" pointer
and inline the pergroup data and the grouping key tuple into the same
palloc chunk? That would cut out a palloc and the 8 wasted bytes on the
pointer.

> TupleHashTableMatch() anyway.

What did you have in mind? That sounds like a good idea orthogonal to
reducing the bucket size.

Alternatively, MinimalTuple is not very "minimal", and perhaps we can
just make it better.

> > additional "special" pointer value to mean "input slot" now that

For the FIRSTTUPLE_INPUTSLOT marker, do you think it's cleaner to use
what I did:

  const static MinimalTuple FIRSTTUPLE_INPUTSLOT = (MinimalTuple) 0x1;

or something like:

  static MinimalTupleData dummy = {0};
  const static MinimalTuple FIRSTTUPLE_INPUTSLOT = &dummy;

?

> simple load/store instruction is the fastest option anyway.

My intuition is that the cost of dereferencing that pointer (to memory
which is not expected to be in cache) is going to be way higher than
the cost of a couple extra instructions to do the unaligned access.

Regards,
	Jeff Davis

---

From: Heikki Linnakangas <[email-masked]>
Date: Tue, 19 Nov 2024 01:30:28 +0200

> palloc chunk? That would cut out a palloc and the 8 wasted bytes on the

Sounds like a good idea. Needs some changes to the TupleTableSlotOps 
interface to avoid the memcpy I presume.

> reducing the bucket size.

Queries that have a only a small number of groups might might benefit 
from storing a plain Datum/isnull array instead of a MinimalTuple. That 
would take more memory when you have a lot of groups though.

> Alternatively, MinimalTuple is not very "minimal", and perhaps we can

Yeah. It tries to be compatible with HeapTuple, but perhaps we should 
give up on that and pack it more tightly instead.

>    const static MinimalTuple FIRSTTUPLE_INPUTSLOT = &dummy;

I think I'd do "(MinimalTuple) 0x1" myself, but no strong opinion.

-- 
Heikki Linnakangas
Neon (https://neon.tech)

---

From: Jeff Davis <[email-masked]>
Date: Thu, 21 Nov 2024 12:37:56 -0800

New patch series attached.

  * a few cleanup patches, but 0001 and 0004 can affect initial hash
table sizing
  * also pack AggStatePerGroupData (to 10 bytes)
  * put additional data in the same chunk as firstTuple to avoid an
extra pointer an an extra allocation

> interface to avoid the memcpy I presume.

Neither firstTuple nor the additional data have a size known at compile
time, so it can't be represented by a struct. It seems best to keep
firstTuple at the beginning so that it matches the SH_KEY_TYPE, and
then just repalloc() to make room at the end for the additional data,
which avoids the memcpy unless it crosses a power-of-two boundary.

> would take more memory when you have a lot of groups though.

The current MinimalTuple representation is pretty wasteful for small
grouping keys, so I don't think it would be hard to beat.

>From the perspective of HashAgg, that seems worthwhile.

In my current patch set, depending on the grouping key and aggregates,
the chunk size for the combination of the firstTuple with the
additional data can be just above 32 bytes, which pushes the chunk size
to 64 bytes. If we cut down the mintuple overhead a bit, more cases
would fit in 32 bytes. And I think we can: 32 bytes seems reasonable to
hold a lot of common cases where there's a small grouping key and a
small pergroup state.

Regards,
	Jeff Davis

From 95a2becb251415af6f82d6df871b66e8a429768b Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Wed, 20 Nov 2024 12:33:11 -0800
Subject: [PATCH v2 1/8] ExecInitAgg: update aggstate->numaggs and ->numtrans
 earlier.

Functions hash_agg_entry_size() and build_hash_tables() and are
relying on those to make accurate estimates.
---
 src/backend/executor/nodeAgg.c | 11 ++---------
 1 file changed, 2 insertions(+), 9 deletions(-)

diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 53ead77ece..300163538a 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -3379,8 +3379,8 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 		max_aggno = Max(max_aggno, aggref->aggno);
 		max_transno = Max(max_transno, aggref->aggtransno);
 	}
-	numaggs = max_aggno + 1;
-	numtrans = max_transno + 1;
+	aggstate->numaggs = numaggs = max_aggno + 1;
+	aggstate->numtrans = numtrans = max_transno + 1;
 
 	/*
 	 * For each phase, prepare grouping set data and fmgr lookup data for
@@ -3943,13 +3943,6 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 		ReleaseSysCache(aggTuple);
 	}
 
-	/*
-	 * Update aggstate->numaggs to be the number of unique aggregates found.
-	 * Also set numstates to the number of unique transition states found.
-	 */
-	aggstate->numaggs = numaggs;
-	aggstate->numtrans = numtrans;
-
 	/*
 	 * Last, check whether any more aggregates got added onto the node while
 	 * we processed the expressions for the aggregate arguments (including not
-- 
2.34.1

From 8e31098ffd338ad9e3d4797f11baed386b1bd714 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Thu, 21 Nov 2024 12:06:53 -0800
Subject: [PATCH v2 2/8] Add missing typedefs.list entry for
 AggStatePerGroupData.

---
 src/include/executor/nodeAgg.h   | 2 +-
 src/tools/pgindent/typedefs.list | 1 +
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/include/executor/nodeAgg.h b/src/include/executor/nodeAgg.h
index 684779a6a3..db633fd672 100644
--- a/src/include/executor/nodeAgg.h
+++ b/src/include/executor/nodeAgg.h
@@ -264,7 +264,7 @@ typedef struct AggStatePerGroupData
 	 * NULL and not auto-replace it with a later input value. Only the first
 	 * non-NULL input will be auto-substituted.
 	 */
-}			AggStatePerGroupData;
+} AggStatePerGroupData;
 
 /*
  * AggStatePerPhaseData - per-grouping-set-phase state
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 08521d51a9..d52bdd2ff1 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -47,6 +47,7 @@ AggSplit
 AggState
 AggStatePerAgg
 AggStatePerGroup
+AggStatePerGroupData
 AggStatePerHash
 AggStatePerPhase
 AggStatePerTrans
-- 
2.34.1

From b372446f046736c40f7f10762623144d8a06aa9f Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Wed, 20 Nov 2024 12:59:16 -0800
Subject: [PATCH v2 3/8] Remove unused TupleHashTableData->entrysize.

---
 src/backend/executor/execGrouping.c | 1 -
 src/include/nodes/execnodes.h       | 1 -
 2 files changed, 2 deletions(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 774e4de882..467dbdc4cc 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -187,7 +187,6 @@ BuildTupleHashTableExt(PlanState *parent,
 	hashtable->tab_collations = collations;
 	hashtable->tablecxt = tablecxt;
 	hashtable->tempcxt = tempcxt;
-	hashtable->entrysize = entrysize;
 	hashtable->tableslot = NULL;	/* will be made on first lookup */
 	hashtable->inputslot = NULL;
 	hashtable->in_hash_funcs = NULL;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 182a6956bb..0e6ec6d3a6 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -835,7 +835,6 @@ typedef struct TupleHashTableData
 	Oid		   *tab_collations; /* collations for hash and comparison */
 	MemoryContext tablecxt;		/* memory context containing table */
 	MemoryContext tempcxt;		/* context for function evaluations */
-	Size		entrysize;		/* actual size to make each hash entry */
 	TupleTableSlot *tableslot;	/* slot for referencing table entries */
 	/* The following fields are set transiently for each table search: */
 	TupleTableSlot *inputslot;	/* current input tuple's slot */
-- 
2.34.1

From c61d82728dd1454ffa62487e41d1c2bc9ee11564 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Wed, 20 Nov 2024 12:50:53 -0800
Subject: [PATCH v2 4/8] nodeSetOp.c: missing additionalsize for
 BuildTupleHashTable().

This can affect the calculations for 'nbuckets'.

Also, furure work for HashAgg will rely on the correct
'additionalsize'.
---
 src/backend/executor/nodeSetOp.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c
index a8ac68b482..4e58a571b7 100644
--- a/src/backend/executor/nodeSetOp.c
+++ b/src/backend/executor/nodeSetOp.c
@@ -134,7 +134,7 @@ build_hash_table(SetOpState *setopstate)
 												   setopstate->hashfunctions,
 												   node->dupCollations,
 												   node->numGroups,
-												   0,
+												   sizeof(SetOpStatePerGroupData),
 												   setopstate->ps.state->es_query_cxt,
 												   setopstate->tableContext,
 												   econtext->ecxt_per_tuple_memory,
-- 
2.34.1

From 6a764dfb883a4153d22fc73901fc2ddbf80e2083 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Thu, 14 Nov 2024 11:47:51 -0800
Subject: [PATCH v2 5/8] TupleHashTable: store additional data along with
 tuple.

Previously, the caller needed to allocate the memory and the
TupleHashTable would store a pointer to it. That wastes space for the
palloc overhead as well as the size of the pointer itself.

Now, the TupleHashTable relies on the caller to correctly specify the
additionalsize, and allocates that amount of space. The caller can
then request a pointer into that space.
---
 src/backend/executor/execGrouping.c | 59 ++++++++++++++++++++++++++++-
 src/backend/executor/nodeAgg.c      | 20 ++++------
 src/backend/executor/nodeSetOp.c    | 19 ++++------
 src/backend/executor/nodeSubplan.c  |  2 +-
 src/include/executor/executor.h     |  3 ++
 src/include/nodes/execnodes.h       | 10 +----
 6 files changed, 78 insertions(+), 35 deletions(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 467dbdc4cc..d4a3b3280e 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -20,6 +20,13 @@
 #include "miscadmin.h"
 #include "utils/lsyscache.h"
 
+typedef struct TupleHashEntryData
+{
+	MinimalTuple firstTuple;	/* copy of first tuple in this group */
+	uint32		status;			/* hash status */
+	uint32		hash;			/* hash value (cached) */
+} TupleHashEntryData;
+
 static int	TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2);
 static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb,
 												 const MinimalTuple tuple);
@@ -187,6 +194,7 @@ BuildTupleHashTableExt(PlanState *parent,
 	hashtable->tab_collations = collations;
 	hashtable->tablecxt = tablecxt;
 	hashtable->tempcxt = tempcxt;
+	hashtable->additionalsize = additionalsize;
 	hashtable->tableslot = NULL;	/* will be made on first lookup */
 	hashtable->inputslot = NULL;
 	hashtable->in_hash_funcs = NULL;
@@ -287,6 +295,15 @@ ResetTupleHashTable(TupleHashTable hashtable)
 	tuplehash_reset(hashtable->hashtab);
 }
 
+/*
+ * Return size of the hash bucket. Useful for estimating memory usage.
+ */
+size_t
+TupleHashEntrySize(void)
+{
+	return sizeof(TupleHashEntryData);
+}
+
 /*
  * Find or create a hashtable entry for the tuple group containing the
  * given tuple.  The tuple must be the same type as the hashtable entries.
@@ -353,6 +370,26 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
 	return hash;
 }
 
+MinimalTuple
+TupleHashEntryGetTuple(TupleHashEntry entry)
+{
+	return entry->firstTuple;
+}
+
+/*
+ * Get a pointer into the additional space allocated for this entry. The
+ * amount of space available is the additionalsize specified to
+ * BuildTupleHashTable(). If additionalsize was specified as zero, no
+ * additional space is available and this function should not be called.
+ */
+void *
+TupleHashEntryGetAdditional(TupleHashEntry entry)
+{
+	Assert(GetMemoryChunkSpace(entry->firstTuple) > MAXALIGN(entry->firstTuple->t_len));
+
+	return (char *) entry->firstTuple + MAXALIGN(entry->firstTuple->t_len);
+}
+
 /*
  * A variant of LookupTupleHashEntry for callers that have already computed
  * the hash value.
@@ -513,13 +550,31 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 		}
 		else
 		{
+			MinimalTuple firstTuple;
+			size_t totalsize; /* including alignment and additionalsize */
+
 			/* created new entry */
 			*isnew = true;
 			/* zero caller data */
-			entry->additional = NULL;
 			MemoryContextSwitchTo(hashtable->tablecxt);
+
 			/* Copy the first tuple into the table context */
-			entry->firstTuple = ExecCopySlotMinimalTuple(slot);
+			firstTuple = ExecCopySlotMinimalTuple(slot);
+
+			/*
+			 * Allocate additional space right after the MinimalTuple of size
+			 * additionalsize. The caller can get a pointer to this data with
+			 * TupleHashEntryGetAdditional(), and store arbitrary data there.
+			 *
+			 * This avoids the need to store an extra pointer or allocate an
+			 * additional chunk, which would waste memory.
+			 */
+			totalsize = MAXALIGN(firstTuple->t_len) + hashtable->additionalsize;
+			firstTuple = repalloc(firstTuple, totalsize);
+			memset((char *) firstTuple + firstTuple->t_len, 0,
+				   totalsize - firstTuple->t_len);
+
+			entry->firstTuple = firstTuple;
 		}
 	}
 	else
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 300163538a..bb20006e9e 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1713,7 +1713,7 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace)
 		transitionChunkSize = 0;
 
 	return
-		sizeof(TupleHashEntryData) +
+		TupleHashEntrySize() +
 		tupleChunkSize +
 		pergroupChunkSize +
 		transitionChunkSize;
@@ -1954,7 +1954,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 	if (aggstate->hash_ngroups_current > 0)
 	{
 		aggstate->hashentrysize =
-			sizeof(TupleHashEntryData) +
+			TupleHashEntrySize() +
 			(hashkey_mem / (double) aggstate->hash_ngroups_current);
 	}
 }
@@ -2055,11 +2055,7 @@ initialize_hash_entry(AggState *aggstate, TupleHashTable hashtable,
 	if (aggstate->numtrans == 0)
 		return;
 
-	pergroup = (AggStatePerGroup)
-		MemoryContextAlloc(hashtable->tablecxt,
-						   sizeof(AggStatePerGroupData) * aggstate->numtrans);
-
-	entry->additional = pergroup;
+	pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry);
 
 	/*
 	 * Initialize aggregates for new tuple group, lookup_hash_entries()
@@ -2123,7 +2119,7 @@ lookup_hash_entries(AggState *aggstate)
 		{
 			if (isnew)
 				initialize_hash_entry(aggstate, hashtable, entry);
-			pergroup[setno] = entry->additional;
+			pergroup[setno] = TupleHashEntryGetAdditional(entry);
 		}
 		else
 		{
@@ -2681,7 +2677,7 @@ agg_refill_hash_table(AggState *aggstate)
 		{
 			if (isnew)
 				initialize_hash_entry(aggstate, perhash->hashtable, entry);
-			aggstate->hash_pergroup[batch->setno] = entry->additional;
+			aggstate->hash_pergroup[batch->setno] = TupleHashEntryGetAdditional(entry);
 			advance_aggregates(aggstate);
 		}
 		else
@@ -2773,7 +2769,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 	ExprContext *econtext;
 	AggStatePerAgg peragg;
 	AggStatePerGroup pergroup;
-	TupleHashEntryData *entry;
+	TupleHashEntry entry;
 	TupleTableSlot *firstSlot;
 	TupleTableSlot *result;
 	AggStatePerHash perhash;
@@ -2845,7 +2841,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 		 * Transform representative tuple back into one with the right
 		 * columns.
 		 */
-		ExecStoreMinimalTuple(entry->firstTuple, hashslot, false);
+		ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashslot, false);
 		slot_getallattrs(hashslot);
 
 		ExecClearTuple(firstSlot);
@@ -2861,7 +2857,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 		}
 		ExecStoreVirtualTuple(firstSlot);
 
-		pergroup = (AggStatePerGroup) entry->additional;
+		pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry);
 
 		/*
 		 * Use the representative input tuple for any references to
diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c
index 4e58a571b7..efbc455cee 100644
--- a/src/backend/executor/nodeSetOp.c
+++ b/src/backend/executor/nodeSetOp.c
@@ -364,7 +364,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 	{
 		TupleTableSlot *outerslot;
 		int			flag;
-		TupleHashEntryData *entry;
+		TupleHashEntry entry;
 		bool		isnew;
 
 		outerslot = ExecProcNode(outerPlan);
@@ -385,15 +385,10 @@ setop_fill_hash_table(SetOpState *setopstate)
 
 			/* If new tuple group, initialize counts */
 			if (isnew)
-			{
-				entry->additional = (SetOpStatePerGroup)
-					MemoryContextAlloc(setopstate->hashtable->tablecxt,
-									   sizeof(SetOpStatePerGroupData));
-				initialize_counts((SetOpStatePerGroup) entry->additional);
-			}
+				initialize_counts((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry));
 
 			/* Advance the counts */
-			advance_counts((SetOpStatePerGroup) entry->additional, flag);
+			advance_counts((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry), flag);
 		}
 		else
 		{
@@ -406,7 +401,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 
 			/* Advance the counts if entry is already present */
 			if (entry)
-				advance_counts((SetOpStatePerGroup) entry->additional, flag);
+				advance_counts((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry), flag);
 		}
 
 		/* Must reset expression context after each hashtable lookup */
@@ -424,7 +419,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 static TupleTableSlot *
 setop_retrieve_hash_table(SetOpState *setopstate)
 {
-	TupleHashEntryData *entry;
+	TupleHashEntry entry;
 	TupleTableSlot *resultTupleSlot;
 
 	/*
@@ -454,12 +449,12 @@ setop_retrieve_hash_table(SetOpState *setopstate)
 		 * See if we should emit any copies of this tuple, and if so return
 		 * the first copy.
 		 */
-		set_output_count(setopstate, (SetOpStatePerGroup) entry->additional);
+		set_output_count(setopstate, (SetOpStatePerGroup) TupleHashEntryGetAdditional(entry));
 
 		if (setopstate->numOutput > 0)
 		{
 			setopstate->numOutput--;
-			return ExecStoreMinimalTuple(entry->firstTuple,
+			return ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry),
 										 resultTupleSlot,
 										 false);
 		}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 236222d72a..63aff24251 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -746,7 +746,7 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot,
 	{
 		CHECK_FOR_INTERRUPTS();
 
-		ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false);
+		ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashtable->tableslot, false);
 		if (!execTuplesUnequal(slot, hashtable->tableslot,
 							   numCols, keyColIdx,
 							   eqfunctions,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..d26968ecf7 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -154,9 +154,12 @@ extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable,
 										   bool *isnew, uint32 *hash);
 extern uint32 TupleHashTableHash(TupleHashTable hashtable,
 								 TupleTableSlot *slot);
+extern size_t TupleHashEntrySize(void);
 extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,
 											   TupleTableSlot *slot,
 											   bool *isnew, uint32 hash);
+extern MinimalTuple TupleHashEntryGetTuple(TupleHashEntry entry);
+extern void *TupleHashEntryGetAdditional(TupleHashEntry entry);
 extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
 										 TupleTableSlot *slot,
 										 ExprState *eqcomp,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 0e6ec6d3a6..68b8b28803 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -806,17 +806,10 @@ typedef struct ExecAuxRowMark
  * tab_eq_func respectively.
  * ----------------------------------------------------------------
  */
+typedef struct TupleHashEntryData TupleHashEntryData;
 typedef struct TupleHashEntryData *TupleHashEntry;
 typedef struct TupleHashTableData *TupleHashTable;
 
-typedef struct TupleHashEntryData
-{
-	MinimalTuple firstTuple;	/* copy of first tuple in this group */
-	void	   *additional;		/* user data */
-	uint32		status;			/* hash status */
-	uint32		hash;			/* hash value (cached) */
-} TupleHashEntryData;
-
 /* define parameters necessary to generate the tuple hash table interface */
 #define SH_PREFIX tuplehash
 #define SH_ELEMENT_TYPE TupleHashEntryData
@@ -835,6 +828,7 @@ typedef struct TupleHashTableData
 	Oid		   *tab_collations; /* collations for hash and comparison */
 	MemoryContext tablecxt;		/* memory context containing table */
 	MemoryContext tempcxt;		/* context for function evaluations */
+	Size		additionalsize;	/* size of additional data */
 	TupleTableSlot *tableslot;	/* slot for referencing table entries */
 	/* The following fields are set transiently for each table search: */
 	TupleTableSlot *inputslot;	/* current input tuple's slot */
-- 
2.34.1

From 5c67d3943a9e02b933d8e18771b0fee797a8856f Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 12:21:04 -0800
Subject: [PATCH v2 6/8] simplehash: don't require a "status" field.

Callers may define SH_ENTRY_IS_EMPTY(), SH_ENTRY_SET_EMPTY(), and
SH_ENTRY_SET_IN_USE() as an alternative, which can allow for a more
compact entry size. That reduces the memory overhead, especially when
the hash table is sparse.
---
 src/include/lib/simplehash.h | 68 ++++++++++++++++++++++++------------
 1 file changed, 45 insertions(+), 23 deletions(-)

diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index 3e1b1f9461..213d8c372e 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -50,9 +50,18 @@
  *	  - SH_HASH_KEY(table, key) - generate hash for the key
  *	  - SH_STORE_HASH - if defined the hash is stored in the elements
  *	  - SH_GET_HASH(tb, a) - return the field to store the hash in
+ *	  - SH_ENTRY_IS_EMPTY(tb, a) - return true if the entry is empty
+ *	  - SH_ENTRY_SET_EMPTY(tb, a) - set entry to empty
+ *	  - SH_ENTRY_SET_IN_USE(tb, a) - set entry to "in use"
  *
  *	  The element type is required to contain a "status" member that can store
- *	  the range of values defined in the SH_STATUS enum.
+ *	  the range of values defined in the SH_STATUS enum. Alternatively,
+ *	  callers may define all of SH_ENTRY_IS_EMPTY, SH_ENTRY_SET_EMPTY,
+ *	  SH_ENTRY_SET_IN_USE to allow for a more compact entry size. For example,
+ *	  if the SH_ELEMENT_TYPE contains a pointer, the caller may decide that
+ *	  the entry is empty if the pointer is NULL and "in use" if the pointer is
+ *	  non-NULL. NB: if the entire entry is zero, then SH_ENTRY_IS_EMPTY()
+ *	  *must* evaluate to true.
  *
  *	  While SH_STORE_HASH (and subsequently SH_GET_HASH) are optional, because
  *	  the hash table implementation needs to compare hashes to move elements
@@ -277,6 +286,18 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb);
 #define SH_GROW_MIN_FILLFACTOR 0.1
 #endif
 
+#ifndef SH_ENTRY_IS_EMPTY
+#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->status == SH_STATUS_EMPTY)
+#endif
+
+#ifndef SH_ENTRY_SET_EMPTY
+#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->status = SH_STATUS_EMPTY; } while (0)
+#endif
+
+#ifndef SH_ENTRY_SET_IN_USE
+#define SH_ENTRY_SET_IN_USE(tb, a) do { (a)->status = SH_STATUS_IN_USE; } while (0)
+#endif
+
 #ifdef SH_STORE_HASH
 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
 #else
@@ -540,7 +561,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize)
 		uint32		hash;
 		uint32		optimal;
 
-		if (oldentry->status != SH_STATUS_IN_USE)
+		if (SH_ENTRY_IS_EMPTY(tb, oldentry))
 		{
 			startelem = i;
 			break;
@@ -562,7 +583,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize)
 	{
 		SH_ELEMENT_TYPE *oldentry = &olddata[copyelem];
 
-		if (oldentry->status == SH_STATUS_IN_USE)
+		if (!SH_ENTRY_IS_EMPTY(tb, oldentry))
 		{
 			uint32		hash;
 			uint32		startelem2;
@@ -578,7 +599,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize)
 			{
 				newentry = &newdata[curelem];
 
-				if (newentry->status == SH_STATUS_EMPTY)
+				if (SH_ENTRY_IS_EMPTY(tb, newentry))
 				{
 					break;
 				}
@@ -649,14 +670,14 @@ restart:
 		SH_ELEMENT_TYPE *entry = &data[curelem];
 
 		/* any empty bucket can directly be used */
-		if (entry->status == SH_STATUS_EMPTY)
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 		{
 			tb->members++;
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
 #endif
-			entry->status = SH_STATUS_IN_USE;
+			SH_ENTRY_SET_IN_USE(tb, entry);
 			*found = false;
 			return entry;
 		}
@@ -671,7 +692,7 @@ restart:
 
 		if (SH_COMPARE_KEYS(tb, hash, key, entry))
 		{
-			Assert(entry->status == SH_STATUS_IN_USE);
+			Assert(!SH_ENTRY_IS_EMPTY(tb, entry));
 			*found = true;
 			return entry;
 		}
@@ -695,7 +716,7 @@ restart:
 				emptyelem = SH_NEXT(tb, emptyelem, startelem);
 				emptyentry = &data[emptyelem];
 
-				if (emptyentry->status == SH_STATUS_EMPTY)
+				if (SH_ENTRY_IS_EMPTY(tb, emptyentry))
 				{
 					lastentry = emptyentry;
 					break;
@@ -744,7 +765,7 @@ restart:
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
 #endif
-			entry->status = SH_STATUS_IN_USE;
+			SH_ENTRY_SET_IN_USE(tb, entry);
 			*found = false;
 			return entry;
 		}
@@ -806,13 +827,11 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
 	{
 		SH_ELEMENT_TYPE *entry = &tb->data[curelem];
 
-		if (entry->status == SH_STATUS_EMPTY)
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 		{
 			return NULL;
 		}
 
-		Assert(entry->status == SH_STATUS_IN_USE);
-
 		if (SH_COMPARE_KEYS(tb, hash, key, entry))
 			return entry;
 
@@ -864,10 +883,10 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 	{
 		SH_ELEMENT_TYPE *entry = &tb->data[curelem];
 
-		if (entry->status == SH_STATUS_EMPTY)
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 			return false;
 
-		if (entry->status == SH_STATUS_IN_USE &&
+		if (!SH_ENTRY_IS_EMPTY(tb, entry) &&
 			SH_COMPARE_KEYS(tb, hash, key, entry))
 		{
 			SH_ELEMENT_TYPE *lastentry = entry;
@@ -890,9 +909,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 				curelem = SH_NEXT(tb, curelem, startelem);
 				curentry = &tb->data[curelem];
 
-				if (curentry->status != SH_STATUS_IN_USE)
+				if (SH_ENTRY_IS_EMPTY(tb, curentry))
 				{
-					lastentry->status = SH_STATUS_EMPTY;
+					SH_ENTRY_SET_EMPTY(tb, lastentry);
 					break;
 				}
 
@@ -902,7 +921,7 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 				/* current is at optimal position, done */
 				if (curoptimal == curelem)
 				{
-					lastentry->status = SH_STATUS_EMPTY;
+					SH_ENTRY_SET_EMPTY(tb, lastentry);
 					break;
 				}
 
@@ -953,9 +972,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 		curelem = SH_NEXT(tb, curelem, startelem);
 		curentry = &tb->data[curelem];
 
-		if (curentry->status != SH_STATUS_IN_USE)
+		if (SH_ENTRY_IS_EMPTY(tb, curentry))
 		{
-			lastentry->status = SH_STATUS_EMPTY;
+			SH_ENTRY_SET_EMPTY(tb, lastentry);
 			break;
 		}
 
@@ -965,7 +984,7 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 		/* current is at optimal position, done */
 		if (curoptimal == curelem)
 		{
-			lastentry->status = SH_STATUS_EMPTY;
+			SH_ENTRY_SET_EMPTY(tb, lastentry);
 			break;
 		}
 
@@ -993,7 +1012,7 @@ SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
 	{
 		SH_ELEMENT_TYPE *entry = &tb->data[i];
 
-		if (entry->status != SH_STATUS_IN_USE)
+		if (SH_ENTRY_IS_EMPTY(tb, entry))
 		{
 			startelem = i;
 			break;
@@ -1055,7 +1074,7 @@ SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
 
 		if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
 			iter->done = true;
-		if (elem->status == SH_STATUS_IN_USE)
+		if (!SH_ENTRY_IS_EMPTY(tb, elem))
 		{
 			return elem;
 		}
@@ -1091,7 +1110,7 @@ SH_STAT(SH_TYPE * tb)
 
 		elem = &tb->data[i];
 
-		if (elem->status != SH_STATUS_IN_USE)
+		if (SH_ENTRY_IS_EMPTY(tb, elem))
 			continue;
 
 		hash = SH_ENTRY_HASH(tb, elem);
@@ -1149,6 +1168,9 @@ SH_STAT(SH_TYPE * tb)
 #undef SH_KEY
 #undef SH_ELEMENT_TYPE
 #undef SH_HASH_KEY
+#undef SH_ENTRY_IS_EMPTY
+#undef SH_ENTRY_SET_EMPTY
+#undef SH_ENTRY_SET_IN_USE
 #undef SH_SCOPE
 #undef SH_DECLARE
 #undef SH_DEFINE
-- 
2.34.1

From cdd20115968128571134eebe94e00a8b0adb18e0 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 13:03:32 -0800
Subject: [PATCH v2 7/8] TupleHashTable: reduce overhead by removing "status"
 field.

Make use of new simplehash API introduced in commit 1234567890.

Because NULL now means that the entry is empty, use a unique dummy
pointer to refer to the inputslot instead. It also makes the code more
readable.
---
 src/backend/executor/execGrouping.c | 33 +++++++++++++++++++----------
 1 file changed, 22 insertions(+), 11 deletions(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index d4a3b3280e..81ccd0e6d0 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -23,7 +23,6 @@
 typedef struct TupleHashEntryData
 {
 	MinimalTuple firstTuple;	/* copy of first tuple in this group */
-	uint32		status;			/* hash status */
 	uint32		hash;			/* hash value (cached) */
 } TupleHashEntryData;
 
@@ -34,6 +33,14 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta
 														   TupleTableSlot *slot,
 														   bool *isnew, uint32 hash);
 
+/*
+ * Create a dummy pointer used to mean the input slot. The pointer will only
+ * be used for comparison and never dereferenced, and must not be equal to a
+ * valid pointer. Distinct from NULL, because NULL means that the hash entry
+ * itself is empty.
+ */
+const static MinimalTuple FIRSTTUPLE_INPUTSLOT = (MinimalTuple) 0x1;
+
 /*
  * Define parameters for tuple hash table code generation. The interface is
  * *also* declared in execnodes.h (to generate the types, which are externally
@@ -48,6 +55,9 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta
 #define SH_SCOPE extern
 #define SH_STORE_HASH
 #define SH_GET_HASH(tb, a) a->hash
+#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->firstTuple == NULL)
+#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->firstTuple = NULL; } while (0)
+#define SH_ENTRY_SET_IN_USE(tb, a) Assert((a)->firstTuple != NULL)
 #define SH_DEFINE
 #include "lib/simplehash.h"
 
@@ -335,7 +345,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 	hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
 	hashtable->cur_eq_func = hashtable->tab_eq_func;
 
-	local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
+	local_hash = TupleHashTableHash_internal(hashtable->hashtab, FIRSTTUPLE_INPUTSLOT);
 	entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, local_hash);
 
 	if (hash != NULL)
@@ -363,7 +373,8 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
 	/* Need to run the hash functions in short-lived context */
 	oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
-	hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
+	hash = TupleHashTableHash_internal(hashtable->hashtab,
+									   FIRSTTUPLE_INPUTSLOT);
 
 	MemoryContextSwitchTo(oldContext);
 
@@ -444,7 +455,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 	hashtable->cur_eq_func = eqcomp;
 
 	/* Search the hash table */
-	key = NULL;					/* flag to reference inputslot */
+	key = FIRSTTUPLE_INPUTSLOT;
 	entry = tuplehash_lookup(hashtable->hashtab, key);
 	MemoryContextSwitchTo(oldContext);
 
@@ -452,9 +463,9 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 }
 
 /*
- * If tuple is NULL, use the input slot instead. This convention avoids the
- * need to materialize virtual input tuples unless they actually need to get
- * copied into the table.
+ * If tuple is FIRSTTUPLE_INPUTSLOT, use the input slot instead. This
+ * convention avoids the need to materialize virtual input tuples unless they
+ * actually need to get copied into the table.
  *
  * Also, the caller must select an appropriate memory context for running
  * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
@@ -471,7 +482,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
 	FmgrInfo   *hashfunctions;
 	int			i;
 
-	if (tuple == NULL)
+	if (tuple == FIRSTTUPLE_INPUTSLOT)
 	{
 		/* Process the current input tuple for the table */
 		slot = hashtable->inputslot;
@@ -537,7 +548,7 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 	bool		found;
 	MinimalTuple key;
 
-	key = NULL;					/* flag to reference inputslot */
+	key = FIRSTTUPLE_INPUTSLOT;
 
 	if (isnew)
 	{
@@ -602,10 +613,10 @@ TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const
 	 * LookupTupleHashEntry's dummy TupleHashEntryData.  The other direction
 	 * could be supported too, but is not currently required.
 	 */
-	Assert(tuple1 != NULL);
+	Assert(tuple1 && tuple1 != FIRSTTUPLE_INPUTSLOT);
 	slot1 = hashtable->tableslot;
 	ExecStoreMinimalTuple(tuple1, slot1, false);
-	Assert(tuple2 == NULL);
+	Assert(tuple2 == FIRSTTUPLE_INPUTSLOT);
 	slot2 = hashtable->inputslot;
 
 	/* For crosstype comparisons, the inputslot must be first */
-- 
2.34.1

From 6a1ef8eb846d76c77958050e8aafc50d528064b1 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 18:52:06 -0800
Subject: [PATCH v2 8/8] Pack TupleHashEntryData and AggStatePerGroupData.

---
 src/backend/executor/execGrouping.c | 6 +++++-
 src/include/executor/nodeAgg.h      | 6 +++++-
 2 files changed, 10 insertions(+), 2 deletions(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 81ccd0e6d0..d28d420fd8 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -24,7 +24,11 @@ typedef struct TupleHashEntryData
 {
 	MinimalTuple firstTuple;	/* copy of first tuple in this group */
 	uint32		hash;			/* hash value (cached) */
-} TupleHashEntryData;
+}
+#ifdef pg_attribute_packed
+	pg_attribute_packed()
+#endif
+TupleHashEntryData;
 
 static int	TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2);
 static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb,
diff --git a/src/include/executor/nodeAgg.h b/src/include/executor/nodeAgg.h
index db633fd672..c11b3a31fb 100644
--- a/src/include/executor/nodeAgg.h
+++ b/src/include/executor/nodeAgg.h
@@ -264,7 +264,11 @@ typedef struct AggStatePerGroupData
 	 * NULL and not auto-replace it with a later input value. Only the first
 	 * non-NULL input will be auto-substituted.
 	 */
-} AggStatePerGroupData;
+}
+#ifdef pg_attribute_packed
+	pg_attribute_packed()
+#endif
+AggStatePerGroupData;
 
 /*
  * AggStatePerPhaseData - per-grouping-set-phase state
-- 
2.34.1

---

From: Jeff Davis <[email-masked]>
Date: Tue, 07 Jan 2025 15:32:07 -0800

> New patch series attached.

I committed the earlier cleanup patches and rebased the rest. Attached.

0001 is not quite as clean as I'd like it to be; suggestions welcome.
It does save a pointer per entry, though, which is substantial.

Regards,
	Jeff Davis

From 399f0e175c23f275b54efd4ec8eaa58b1a7d96c8 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Thu, 14 Nov 2024 11:47:51 -0800
Subject: [PATCH v3 1/4] TupleHashTable: store additional data along with
 tuple.

 src/backend/executor/nodeSetOp.c    | 17 +++++----
 6 files changed, 80 insertions(+), 31 deletions(-)

index 33b124fbb0a..29bd3162ad5 100644
 
@@ -196,6 +203,7 @@ BuildTupleHashTable(PlanState *parent,
 	hashtable->in_hash_expr = NULL;
@@ -273,6 +281,15 @@ ResetTupleHashTable(TupleHashTable hashtable)
 
+/*
@@ -339,6 +356,26 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
 	return hash;
 }
 
+MinimalTuple
@@ -477,13 +514,31 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
index 3005b5c0e3b..19640752967 100644
 
 	return

 	/*

 
 		/*
 		 * Use the representative input tuple for any references to
diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c
index 5b7ff9c3748..2a50d56fc87 100644
--- a/src/backend/executor/nodeSetOp.c
+++ b/src/backend/executor/nodeSetOp.c
@@ -425,6 +425,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 	{
 		TupleTableSlot *outerslot;
 		TupleHashEntryData *entry;
+		SetOpStatePerGroup pergroup;
 		bool		isnew;
 
 		outerslot = ExecProcNode(outerPlan);
@@ -437,16 +438,16 @@ setop_fill_hash_table(SetOpState *setopstate)
 									 outerslot,
 									 &isnew, NULL);
 
+		pergroup = TupleHashEntryGetAdditional(entry);
 		/* If new tuple group, initialize counts to zero */
 		if (isnew)
 		{
-			entry->additional = (SetOpStatePerGroup)
-				MemoryContextAllocZero(setopstate->hashtable->tablecxt,
-									   sizeof(SetOpStatePerGroupData));
+			pergroup->numLeft = 0;
+			pergroup->numRight = 0;
 		}
 
 		/* Advance the counts */
-		((SetOpStatePerGroup) entry->additional)->numLeft++;
+		pergroup->numLeft++;
 
 		/* Must reset expression context after each hashtable lookup */
 		ResetExprContext(econtext);
@@ -478,7 +479,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 
 			/* Advance the counts if entry is already present */
 			if (entry)
-				((SetOpStatePerGroup) entry->additional)->numRight++;
+				((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry))->numRight++;
 
 			/* Must reset expression context after each hashtable lookup */
 			ResetExprContext(econtext);
@@ -496,7 +497,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 static TupleTableSlot *
 setop_retrieve_hash_table(SetOpState *setopstate)
 {
-	TupleHashEntryData *entry;
+	TupleHashEntry entry;
 	TupleTableSlot *resultTupleSlot;
 
 	/*
@@ -526,12 +527,12 @@ setop_retrieve_hash_table(SetOpState *setopstate)
 		 * See if we should emit any copies of this tuple, and if so return
 		 * the first copy.
 		 */
-		set_output_count(setopstate, (SetOpStatePerGroup) entry->additional);
+		set_output_count(setopstate, (SetOpStatePerGroup) TupleHashEntryGetAdditional(entry));
 
 		if (setopstate->numOutput > 0)
 		{
 			setopstate->numOutput--;
-			return ExecStoreMinimalTuple(entry->firstTuple,
+			return ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry),
 										 resultTupleSlot,
 										 false);
 		}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 49767ed6a52..f7f6fc2da0b 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -753,7 +753,7 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot,
 	{
 		CHECK_FOR_INTERRUPTS();
 
index f8a8d03e533..a49c32072e3 100644
@@ -148,9 +148,12 @@ extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable,
index b3f7aa299f5..7d5871d6fac 100644
  * point to tab_hash_expr and tab_eq_func respectively.

From 1d3ee5d04adf729cff93544cf9a9b768d47fa805 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 12:21:04 -0800
Subject: [PATCH v3 2/4] simplehash: don't require a "status" field.

index 327274c2340..0b9b0cdfde0 100644

 

 

 

 

 

 

 
 		elem = &tb->data[i];

From 393dfcb784bed5c162fe5c9d5b1bb287288312cf Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 13:03:32 -0800
Subject: [PATCH v3 3/4] TupleHashTable: reduce overhead by removing "status"
 field.

index 29bd3162ad5..43165375946 100644

+/*
 
@@ -321,7 +331,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 	hashtable->in_hash_expr = hashtable->tab_hash_expr;
 	hashtable->cur_eq_func = hashtable->tab_eq_func;

 	if (hash != NULL)
@@ -349,7 +359,8 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
 	/* Need to run the hash functions in short-lived context */
 	oldContext = MemoryContextSwitchTo(hashtable->tempcxt);

 
@@ -430,7 +441,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 	hashtable->cur_eq_func = eqcomp;

@@ -438,9 +449,9 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 }
 
 /*
  * the hash functions.
@@ -454,7 +465,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
 	TupleTableSlot *slot;
 	bool		isnull;
 
-	if (tuple == NULL)
+	if (tuple == FIRSTTUPLE_INPUTSLOT)
 	{
 		/* Process the current input tuple for the table */
 		hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
@@ -501,7 +512,7 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 	bool		found;
 	MinimalTuple key;

 	if (isnew)
 	{
@@ -566,10 +577,10 @@ TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const

From 160b8bee7c56305fc881dbe8187c13eebce7bf92 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 18:52:06 -0800
Subject: [PATCH v3 4/4] Pack TupleHashEntryData and AggStatePerGroupData.

---

index 43165375946..70f79abe86b 100644
 
index 34b82d0f5d1..d519b2a57a4 100644
 
 /*

---

From: David Rowley <[email-masked]>
Date: Sun, 12 Jan 2025 14:54:51 +1300

> I committed the earlier cleanup patches and rebased the rest. Attached.

While I do understand the desire to reduce Hash Agg's memory usage,
has this really been through enough performance testing to be getting
committed?

I looked at the changes e0ece2a98 made to
LookupTupleHashEntry_internal() and saw that you're doing repalloc()
on the memory for the MinimalTuple just after the
ExecCopySlotMinimalTuple() pallocs that memory. Some of these tuples
might be quite big and I see your test case has a single INT4 GROUP
BY, in which case the tuple is narrow. Remember this code is also used
for set operations, where the tuples to compare might be quite wide.
Since AllocSet rounds non-external chunks up to the next power-of-2,
many repallocs() won't require a new chunk as there's likely to be
space in the existing chunk, but I still seem to be able to measure
this even when the memcpy() to populate the new chunk from the old one
isn't needed.

For example:

create table a (a text not null);
insert into a select repeat(md5(a::text),10) from generate_Series(1,1000) a;
vacuum freeze analyze a;

groupbya.sql:
select a,count(*) from a group by a;

psql -c "select pg_prewarm('a');" postgres > /dev/null && for i in
{1..3}; do pgbench -n -f groupbya.sql -T 10 -M prepared postgres |
grep tps; done

Before (34c6e6524):
tps = 1197.271513 (without initial connection time)
tps = 1201.798286 (without initial connection time)
tps = 1189.191958 (without initial connection time)

After (e0ece2a98):
tps = 1036.424401 (without initial connection time)
tps = 1094.528577 (without initial connection time)
tps = 1067.820026 (without initial connection time)

12% slower.

Or if I craft the tuple so that the repalloc() needs to switch from a
256 byte to 512 byte chunk, I get:

create table b (b text not null);
insert into b select left(repeat(md5(b::text),8),236) from
generate_Series(1,1000) b;
vacuum freeze analyze b;

groupbyb.sql:
select b,count(*) from b group by b;

psql -c "select pg_prewarm('b');" postgres && for i in {1..3}; do
pgbench -n -f groupbyb.sql -T 10 -M prepared postgres | grep tps; done

Before (34c6e6524)
tps = 1258.542072 (without initial connection time)
tps = 1260.423425 (without initial connection time)
tps = 1244.229721 (without initial connection time)

After (e0ece2a98):
tps = 1088.773442 (without initial connection time)
tps = 1068.253603 (without initial connection time)
tps = 1121.814669 (without initial connection time)

14% slower.

While I understand that this likely helps for when the hashtable size
is larger than L3 and also when HashAgg is spilling to disk. I don't
think that making that faster at the expense of slowing down workloads
that fit into memory does not seem like a nice trade-off.

I wonder if there's some other better way of doing this. Would it be
worth having some function like ExecCopySlotMinimalTuple() that
accepts an additional parameter so that the palloc allocates N more
bytes at the end?  Maybe it's worth hunting around to see if there's
any other executor nodes that could benefit from that infrastructure.
The other problem you've created by doing the repalloc() is that, if
you still want the patch you posted in [1] then the repalloc() can't
be done since bump context don't allow it.

It would be quite nice if there were some way to have both of these
optimisations in a way that didn't need any repalloc().

David

[1] https://postgr.es/m/[email-masked]

---

From: Jeff Davis <[email-masked]>
Date: Fri, 07 Feb 2025 17:13:06 -0800

On Sun, 2025-01-12 at 14:54 +1300, David Rowley wrote:
> bytes at the end?

Attached a new series that implements this idea.

I also added in the change to use the Bump allocator for the tablecxt.
In my simple test, the whole patch series reduces HashAgg memory usage
by more than 40% and increases speed by a few percent.

In your test, patch 0003 seemed to have a regression, but then 0007
made up for it (and maybe a hair faster). I investigated, but the
profile was a bit misleading so I'm not clear on why 0003 came out
slower. I can investigate further, but the primary purpose of this
patch series is reducing memory usage, so as long as the overall series
has no regression then I think it's fine.

Regards,
	Jeff Davis

From 9c01b9ac8e1f51d19f4a83521fe1ed98782701f2 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Mon, 13 Jan 2025 14:37:02 -0800
Subject: [PATCH v6 1/7] Create accessor functions for TupleHashEntry.

---
 src/backend/executor/execGrouping.c | 49 +++++++++++++++++++++++++++--
 src/backend/executor/nodeAgg.c      | 20 +++++-------
 src/backend/executor/nodeSetOp.c    | 17 +++++-----
 src/backend/executor/nodeSubplan.c  |  2 +-
 src/include/executor/executor.h     |  3 ++
 src/include/nodes/execnodes.h       | 11 ++-----
 6 files changed, 71 insertions(+), 31 deletions(-)

index 33b124fbb0a..6763c35457c 100644
@@ -20,6 +20,14 @@
 
+struct TupleHashEntryData
+{
+	MinimalTuple firstTuple;	/* copy of first tuple in this group */
+	void	   *additional;		/* user data */
+	uint32		status;			/* hash status */
+	uint32		hash;			/* hash value (cached) */
+};
+
 static int	TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2);
 static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb,
 												 const MinimalTuple tuple);
@@ -196,6 +204,7 @@ BuildTupleHashTable(PlanState *parent,
 	hashtable->tab_collations = collations;
 	hashtable->tablecxt = tablecxt;
 	hashtable->tempcxt = tempcxt;
+	hashtable->additionalsize = additionalsize;
 	hashtable->tableslot = NULL;	/* will be made on first lookup */
 	hashtable->inputslot = NULL;
 	hashtable->in_hash_expr = NULL;
@@ -273,6 +282,37 @@ ResetTupleHashTable(TupleHashTable hashtable)
 	tuplehash_reset(hashtable->hashtab);
 }
 
+/*
+ * Return size of the hash bucket. Useful for estimating memory usage.
+ */
+size_t
+TupleHashEntrySize(void)
+{
+	return sizeof(TupleHashEntryData);
+}
+
+/*
+ * Return tuple from hash entry.
+ */
+MinimalTuple
+TupleHashEntryGetTuple(TupleHashEntry entry)
+{
+	return entry->firstTuple;
+}
+
+/*
+ * Get a pointer into the additional space allocated for this entry. The
+ * amount of space available is the additionalsize specified to
+ * BuildTupleHashTable(). If additionalsize was specified as zero, no
+ * additional space is available and this function should not be called.
+ */
+void *
+TupleHashEntryGetAdditional(TupleHashEntry entry)
+{
+	Assert(entry->additional != NULL);
+	return entry->additional;
+}
+
 /*
  * Find or create a hashtable entry for the tuple group containing the
  * given tuple.  The tuple must be the same type as the hashtable entries.
@@ -479,11 +519,16 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 		{
 			/* created new entry */
 			*isnew = true;
-			/* zero caller data */
-			entry->additional = NULL;
+
 			MemoryContextSwitchTo(hashtable->tablecxt);
+
 			/* Copy the first tuple into the table context */
 			entry->firstTuple = ExecCopySlotMinimalTuple(slot);
+
+			if (hashtable->additionalsize > 0)
+				entry->additional = palloc0(hashtable->additionalsize);
+			else
+				entry->additional = NULL;
 		}
 	}
 	else
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 3005b5c0e3b..19640752967 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1713,7 +1713,7 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace)
 		transitionChunkSize = 0;
 
 	return

 	/*

 
 		/*

 
 		/* Advance the counts */

 
 
 	/*

index 30e2a82346f..26d1877b1f3 100644
@@ -148,6 +148,9 @@ extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable,
index e2d1dc1e067..d46ce9b4996 100644
@@ -831,17 +831,11 @@ typedef struct ExecAuxRowMark
+struct TupleHashEntryData;
 
@@ -860,6 +854,7 @@ typedef struct TupleHashTableData

From 5db233e1fd02636b25399fa4db521fd464d3c504 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 7 Feb 2025 13:14:50 -0800
Subject: [PATCH v6 2/7] Add ExecCopySlotMinimalTupleExtra().

Allows an "extra" argument that allocates extra memory at the end of
the MinimalTuple. This is important for callers that need to store
additional data, but do not want to perform an additional allocation.
---
 src/backend/access/common/heaptuple.c      | 43 ++++++++++++++++++----
 src/backend/executor/execTuples.c          | 24 ++++++------
 src/backend/executor/nodeGatherMerge.c     |  2 +-
 src/backend/utils/sort/tuplesortvariants.c |  2 +-
 src/backend/utils/sort/tuplestore.c        |  6 +--
 src/include/access/htup_details.h          |  7 ++--
 src/include/executor/tuptable.h            | 19 +++++++++-
 7 files changed, 74 insertions(+), 29 deletions(-)

diff --git a/src/backend/access/common/heaptuple.c b/src/backend/access/common/heaptuple.c
index b43cb9ccff4..36df2b31f2d 100644
--- a/src/backend/access/common/heaptuple.c
+++ b/src/backend/access/common/heaptuple.c
@@ -1452,7 +1452,8 @@ heap_freetuple(HeapTuple htup)
 MinimalTuple
 heap_form_minimal_tuple(TupleDesc tupleDescriptor,
 						const Datum *values,
-						const bool *isnull)
+						const bool *isnull,
+						Size extra)
 {
 	MinimalTuple tuple;			/* return tuple */
 	Size		len,
@@ -1497,7 +1498,10 @@ heap_form_minimal_tuple(TupleDesc tupleDescriptor,
 	/*
 	 * Allocate and zero the space needed.
 	 */
-	tuple = (MinimalTuple) palloc0(len);
+	if (extra == 0)
+		tuple = (MinimalTuple) palloc0(len);
+	else
+		tuple = (MinimalTuple) palloc0(MAXALIGN(len) + extra);
 
 	/*
 	 * And fill in the information.
@@ -1533,12 +1537,23 @@ heap_free_minimal_tuple(MinimalTuple mtup)
  * The result is allocated in the current memory context.
  */
 MinimalTuple
-heap_copy_minimal_tuple(MinimalTuple mtup)
+heap_copy_minimal_tuple(MinimalTuple mtup, Size extra)
 {
 	MinimalTuple result;
 
-	result = (MinimalTuple) palloc(mtup->t_len);
-	memcpy(result, mtup, mtup->t_len);
+	if (extra == 0)
+	{
+		result = (MinimalTuple) palloc(mtup->t_len);
+		memcpy(result, mtup, mtup->t_len);
+	}
+	else
+	{
+		Size		totalsize = MAXALIGN(mtup->t_len) + extra;
+
+		result = (MinimalTuple) palloc(totalsize);
+		memcpy(result, mtup, mtup->t_len);
+		memset((char *) result + mtup->t_len, 0, totalsize - mtup->t_len);
+	}
 	return result;
 }
 
@@ -1574,15 +1589,27 @@ heap_tuple_from_minimal_tuple(MinimalTuple mtup)
  * The result is allocated in the current memory context.
  */
 MinimalTuple
-minimal_tuple_from_heap_tuple(HeapTuple htup)
+minimal_tuple_from_heap_tuple(HeapTuple htup, Size extra)
 {
 	MinimalTuple result;
 	uint32		len;
 
 	Assert(htup->t_len > MINIMAL_TUPLE_OFFSET);
 	len = htup->t_len - MINIMAL_TUPLE_OFFSET;
-	result = (MinimalTuple) palloc(len);
-	memcpy(result, (char *) htup->t_data + MINIMAL_TUPLE_OFFSET, len);
+	if (extra == 0)
+	{
+		result = (MinimalTuple) palloc(len);
+		memcpy(result, (char *) htup->t_data + MINIMAL_TUPLE_OFFSET, len);
+	}
+	else
+	{
+		Size		totalsize = MAXALIGN(len) + extra;
+
+		result = (MinimalTuple) palloc(totalsize);
+		memcpy(result, (char *) htup->t_data + MINIMAL_TUPLE_OFFSET, len);
+		memset((char *) result + len, 0, totalsize - len);
+	}
+
 	result->t_len = len;
 	return result;
 }
diff --git a/src/backend/executor/execTuples.c b/src/backend/executor/execTuples.c
index 7de490462d4..8e02d68824f 100644
--- a/src/backend/executor/execTuples.c
+++ b/src/backend/executor/execTuples.c
@@ -298,13 +298,14 @@ tts_virtual_copy_heap_tuple(TupleTableSlot *slot)
 }
 
 static MinimalTuple
-tts_virtual_copy_minimal_tuple(TupleTableSlot *slot)
+tts_virtual_copy_minimal_tuple(TupleTableSlot *slot, Size extra)
 {
 	Assert(!TTS_EMPTY(slot));
 
 	return heap_form_minimal_tuple(slot->tts_tupleDescriptor,
 								   slot->tts_values,
-								   slot->tts_isnull);
+								   slot->tts_isnull,
+								   extra);
 }

@@ -472,14 +473,14 @@ tts_heap_copy_heap_tuple(TupleTableSlot *slot)
 }
 
 static MinimalTuple
-tts_heap_copy_minimal_tuple(TupleTableSlot *slot)
+tts_heap_copy_minimal_tuple(TupleTableSlot *slot, Size extra)
 {
 	HeapTupleTableSlot *hslot = (HeapTupleTableSlot *) slot;
 
 	if (!hslot->tuple)
 		tts_heap_materialize(slot);
 
-	return minimal_tuple_from_heap_tuple(hslot->tuple);
+	return minimal_tuple_from_heap_tuple(hslot->tuple, extra);
 }
 
 static void
@@ -607,7 +608,8 @@ tts_minimal_materialize(TupleTableSlot *slot)
 	{
 		mslot->mintuple = heap_form_minimal_tuple(slot->tts_tupleDescriptor,
 												  slot->tts_values,
-												  slot->tts_isnull);
+												  slot->tts_isnull,
+												  0);
 	}
 	else
 	{
@@ -617,7 +619,7 @@ tts_minimal_materialize(TupleTableSlot *slot)
 		 * TTS_FLAG_SHOULDFREE set).  Copy the minimal tuple into the given
 		 * slot's memory context.
 		 */
-		mslot->mintuple = heap_copy_minimal_tuple(mslot->mintuple);
+		mslot->mintuple = heap_copy_minimal_tuple(mslot->mintuple, 0);
 	}
 
 	slot->tts_flags |= TTS_FLAG_SHOULDFREE;
@@ -666,14 +668,14 @@ tts_minimal_copy_heap_tuple(TupleTableSlot *slot)
 }
 
 static MinimalTuple
-tts_minimal_copy_minimal_tuple(TupleTableSlot *slot)
+tts_minimal_copy_minimal_tuple(TupleTableSlot *slot, Size extra)
 {
 	MinimalTupleTableSlot *mslot = (MinimalTupleTableSlot *) slot;
 
 	if (!mslot->mintuple)
 		tts_minimal_materialize(slot);
 
-	return heap_copy_minimal_tuple(mslot->mintuple);
+	return heap_copy_minimal_tuple(mslot->mintuple, extra);
 }
 
 static void
@@ -926,7 +928,7 @@ tts_buffer_heap_copy_heap_tuple(TupleTableSlot *slot)
 }
 
 static MinimalTuple
-tts_buffer_heap_copy_minimal_tuple(TupleTableSlot *slot)
+tts_buffer_heap_copy_minimal_tuple(TupleTableSlot *slot, Size extra)
 {
 	BufferHeapTupleTableSlot *bslot = (BufferHeapTupleTableSlot *) slot;
 
@@ -935,7 +937,7 @@ tts_buffer_heap_copy_minimal_tuple(TupleTableSlot *slot)
 	if (!bslot->base.tuple)
 		tts_buffer_heap_materialize(slot);
 
-	return minimal_tuple_from_heap_tuple(bslot->base.tuple);
+	return minimal_tuple_from_heap_tuple(bslot->base.tuple, extra);
 }
 
 static inline void
@@ -1895,7 +1897,7 @@ ExecFetchSlotMinimalTuple(TupleTableSlot *slot,
 	{
 		if (shouldFree)
 			*shouldFree = true;
-		return slot->tts_ops->copy_minimal_tuple(slot);
+		return slot->tts_ops->copy_minimal_tuple(slot, 0);
 	}
 }
 
diff --git a/src/backend/executor/nodeGatherMerge.c b/src/backend/executor/nodeGatherMerge.c
index 01a6e3a8553..15f84597067 100644
--- a/src/backend/executor/nodeGatherMerge.c
+++ b/src/backend/executor/nodeGatherMerge.c
@@ -735,7 +735,7 @@ gm_readnext_tuple(GatherMergeState *gm_state, int nreader, bool nowait,
 	 * Since we'll be buffering these across multiple calls, we need to make a
 	 * copy.
 	 */
-	return tup ? heap_copy_minimal_tuple(tup) : NULL;
+	return tup ? heap_copy_minimal_tuple(tup, 0) : NULL;
 }
 
 /*
diff --git a/src/backend/utils/sort/tuplesortvariants.c b/src/backend/utils/sort/tuplesortvariants.c
index 913c4ef455e..03bd3e0d2f1 100644
--- a/src/backend/utils/sort/tuplesortvariants.c
+++ b/src/backend/utils/sort/tuplesortvariants.c
@@ -892,7 +892,7 @@ tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy,
 			*abbrev = stup.datum1;
 
 		if (copy)
-			stup.tuple = heap_copy_minimal_tuple((MinimalTuple) stup.tuple);
+			stup.tuple = heap_copy_minimal_tuple((MinimalTuple) stup.tuple, 0);
 
 		ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy);
 		return true;
diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index d61b601053c..c9aecab8d66 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -787,7 +787,7 @@ tuplestore_putvalues(Tuplestorestate *state, TupleDesc tdesc,
 	MinimalTuple tuple;
 	MemoryContext oldcxt = MemoryContextSwitchTo(state->context);
 
-	tuple = heap_form_minimal_tuple(tdesc, values, isnull);
+	tuple = heap_form_minimal_tuple(tdesc, values, isnull, 0);
 	USEMEM(state, GetMemoryChunkSpace(tuple));
 
 	tuplestore_puttuple_common(state, tuple);
@@ -1139,7 +1139,7 @@ tuplestore_gettupleslot(Tuplestorestate *state, bool forward,
 	{
 		if (copy && !should_free)
 		{
-			tuple = heap_copy_minimal_tuple(tuple);
+			tuple = heap_copy_minimal_tuple(tuple, 0);
 			should_free = true;
 		}
 		ExecStoreMinimalTuple(tuple, slot, should_free);
@@ -1590,7 +1590,7 @@ copytup_heap(Tuplestorestate *state, void *tup)
 {
 	MinimalTuple tuple;
 
-	tuple = minimal_tuple_from_heap_tuple((HeapTuple) tup);
+	tuple = minimal_tuple_from_heap_tuple((HeapTuple) tup, 0);
 	USEMEM(state, GetMemoryChunkSpace(tuple));
 	return tuple;
 }
diff --git a/src/include/access/htup_details.h b/src/include/access/htup_details.h
index 6cd4b95bfdb..aa957cf3b01 100644
--- a/src/include/access/htup_details.h
+++ b/src/include/access/htup_details.h
@@ -839,11 +839,12 @@ extern void heap_deform_tuple(HeapTuple tuple, TupleDesc tupleDesc,
 							  Datum *values, bool *isnull);
 extern void heap_freetuple(HeapTuple htup);
 extern MinimalTuple heap_form_minimal_tuple(TupleDesc tupleDescriptor,
-											const Datum *values, const bool *isnull);
+											const Datum *values, const bool *isnull,
+											Size extra);
 extern void heap_free_minimal_tuple(MinimalTuple mtup);
-extern MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup);
+extern MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup, Size extra);
 extern HeapTuple heap_tuple_from_minimal_tuple(MinimalTuple mtup);
-extern MinimalTuple minimal_tuple_from_heap_tuple(HeapTuple htup);
+extern MinimalTuple minimal_tuple_from_heap_tuple(HeapTuple htup, Size extra);
 extern size_t varsize_any(void *p);
 extern HeapTuple heap_expand_tuple(HeapTuple sourceTuple, TupleDesc tupleDesc);
 extern MinimalTuple minimal_expand_tuple(HeapTuple sourceTuple, TupleDesc tupleDesc);
diff --git a/src/include/executor/tuptable.h b/src/include/executor/tuptable.h
index a044d78e4d0..b901fef41f0 100644
--- a/src/include/executor/tuptable.h
+++ b/src/include/executor/tuptable.h
@@ -218,8 +218,12 @@ struct TupleTableSlotOps
 	 * meaningful "system columns" in the copy. The copy is not be "owned" by
 	 * the slot i.e. the caller has to take responsibility to free memory
 	 * consumed by the slot.
+	 *
+	 * The copy has "extra" bytes (maxaligned and zeroed) available at the
+	 * end, which is useful so that some callers may store extra data along
+	 * with the minimal tuple without the need for an additional allocation.
 	 */
-	MinimalTuple (*copy_minimal_tuple) (TupleTableSlot *slot);
+	MinimalTuple (*copy_minimal_tuple) (TupleTableSlot *slot, Size extra);
 };
 
 /*
@@ -491,7 +495,18 @@ ExecCopySlotHeapTuple(TupleTableSlot *slot)
 static inline MinimalTuple
 ExecCopySlotMinimalTuple(TupleTableSlot *slot)
 {
-	return slot->tts_ops->copy_minimal_tuple(slot);
+	return slot->tts_ops->copy_minimal_tuple(slot, 0);
+}
+
+/*
+ * ExecCopySlotMinimalTupleExtra - return MinimalTuple allocated in caller's
+ * context, with extra bytes (maxaligned and zeroed) after the end of the
+ * tuple.
+ */
+static inline MinimalTuple
+ExecCopySlotMinimalTupleExtra(TupleTableSlot *slot, Size extra)
+{
+	return slot->tts_ops->copy_minimal_tuple(slot, extra);
 }
 
 /*
-- 
2.34.1

From 449563fcdbaad76fa0841cdb82ce4e4f55d75163 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Tue, 14 Jan 2025 16:17:00 -0800
Subject: [PATCH v6 3/7] Store additional data after mintuple

---
 src/backend/executor/execGrouping.c | 28 ++++++++++++++++------------
 1 file changed, 16 insertions(+), 12 deletions(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 6763c35457c..90833216e3b 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -23,7 +23,6 @@
 struct TupleHashEntryData
 {
 	MinimalTuple firstTuple;	/* copy of first tuple in this group */
-	void	   *additional;		/* user data */
 	uint32		status;			/* hash status */
 	uint32		hash;			/* hash value (cached) */
 };
@@ -302,15 +301,16 @@ TupleHashEntryGetTuple(TupleHashEntry entry)
 
 /*
  * Get a pointer into the additional space allocated for this entry. The
- * amount of space available is the additionalsize specified to
- * BuildTupleHashTable(). If additionalsize was specified as zero, no
+ * memory will be maxaligned and zeroed.
+ *
+ * The amount of space available is the additionalsize requested in the call
+ * to BuildTupleHashTable(). If additionalsize was specified as zero, no
  * additional space is available and this function should not be called.
  */
 void *
 TupleHashEntryGetAdditional(TupleHashEntry entry)
 {
-	Assert(entry->additional != NULL);
-	return entry->additional;
+	return (char *) entry->firstTuple + MAXALIGN(entry->firstTuple->t_len);
 }
 
 /*
@@ -522,13 +522,17 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,

-			/* Copy the first tuple into the table context */
-			entry->firstTuple = ExecCopySlotMinimalTuple(slot);
-
-			if (hashtable->additionalsize > 0)
-				entry->additional = palloc0(hashtable->additionalsize);
-			else
-				entry->additional = NULL;
+			/*
+			 * Copy the first tuple into the table context, and request
+			 * additionalsize extra bytes at the end of the allocation.
+			 *
+			 * The caller can get a pointer to this data with
+			 * TupleHashEntryGetAdditional(), and store arbitrary data there.
+			 * This avoids the need to store an extra pointer or allocate an
+			 * additional chunk, which would waste memory.
+			 */
+			entry->firstTuple = ExecCopySlotMinimalTupleExtra(slot,
+															  hashtable->additionalsize);
 		}
 	}
 	else
-- 
2.34.1

From 2c2506f14adc51625b577ececef36b6feb159a22 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 12:21:04 -0800
Subject: [PATCH v6 4/7] simplehash: don't require a "status" field.

 

 

 

 

 

 

 

 		elem = &tb->data[i];

From c7bcdc8493137b15b3b8f7b9f9bbfe8b5e640e9e Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 13:03:32 -0800
Subject: [PATCH v6 5/7] TupleHashTable: reduce overhead by removing "status"
 field.

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 90833216e3b..7f41b03324f 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -23,7 +23,6 @@
 struct TupleHashEntryData
 {
 	MinimalTuple firstTuple;	/* copy of first tuple in this group */
-	uint32		status;			/* hash status */
 	uint32		hash;			/* hash value (cached) */
 };

+/*
 
@@ -344,7 +354,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 	hashtable->in_hash_expr = hashtable->tab_hash_expr;
 	hashtable->cur_eq_func = hashtable->tab_eq_func;

 	if (hash != NULL)
@@ -372,7 +382,8 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
 	/* Need to run the hash functions in short-lived context */
 	oldContext = MemoryContextSwitchTo(hashtable->tempcxt);

 
@@ -433,7 +444,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 	hashtable->cur_eq_func = eqcomp;

@@ -441,9 +452,9 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
 }
 
 /*
@@ -457,7 +468,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
 	TupleTableSlot *slot;
 	bool		isnull;
 
-	if (tuple == NULL)
+	if (tuple == FIRSTTUPLE_INPUTSLOT)
 	{
 		/* Process the current input tuple for the table */
 		hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
@@ -504,7 +515,7 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 	bool		found;
 	MinimalTuple key;

 	if (isnew)
 	{
@@ -560,10 +571,10 @@ TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const

From 64b049cd850c2e9c60574def618967eb7f0c0343 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Fri, 15 Nov 2024 18:52:06 -0800
Subject: [PATCH v6 6/7] Pack TupleHashEntryData and AggStatePerGroupData.

---

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 7f41b03324f..cea28ce4bd7 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -24,7 +24,11 @@ struct TupleHashEntryData
 {
 	MinimalTuple firstTuple;	/* copy of first tuple in this group */
 	uint32		hash;			/* hash value (cached) */
-};
+}
+#ifdef pg_attribute_packed
+			pg_attribute_packed()
+#endif
+		   ;
 
index 34b82d0f5d1..cb756a912a6 100644
 
 /*

From 7e324de479998b8b773185db946e8788bc6a9201 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Wed, 8 Jan 2025 11:46:35 -0800
Subject: [PATCH v6 7/7] HashAgg: use Bump allocator for hash TupleHashTable
 entries.

The entries aren't freed until the entire hash table is destroyed, so
use the Bump allocator to improve allocation speed, avoid wasting
space on the chunk header, and avoid wasting space due to the
power-of-two allocations.

Discussion: https://postgr.es/m/[email-masked]
Reviewed-by: David Rowley
---
 src/backend/executor/nodeAgg.c             | 110 +++++++++++++++++----
 src/include/nodes/execnodes.h              |   5 +-
 src/test/regress/expected/groupingsets.out |   2 +-
 src/test/regress/sql/groupingsets.sql      |   2 +-
 4 files changed, 97 insertions(+), 22 deletions(-)

diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 19640752967..d5bed9ec48e 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -405,6 +405,7 @@ static void build_hash_tables(AggState *aggstate);
 static void build_hash_table(AggState *aggstate, int setno, long nbuckets);
 static void hashagg_recompile_expressions(AggState *aggstate, bool minslot,
 										  bool nullcheck);
+static void hash_create_memory(AggState *aggstate);
 static long hash_choose_num_buckets(double hashentrysize,
 									long ngroups, Size memory);
 static int	hash_choose_num_partitions(double input_groups,
@@ -1503,7 +1504,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets)
 {
 	AggStatePerHash perhash = &aggstate->perhash[setno];
 	MemoryContext metacxt = aggstate->hash_metacxt;
-	MemoryContext hashcxt = aggstate->hashcontext->ecxt_per_tuple_memory;
+	MemoryContext tablecxt = aggstate->hash_tablecxt;
 	MemoryContext tmpcxt = aggstate->tmpcontext->ecxt_per_tuple_memory;
 	Size		additionalsize;
 
@@ -1529,7 +1530,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets)
 											 nbuckets,
 											 additionalsize,
 											 metacxt,
-											 hashcxt,
+											 tablecxt,
 											 tmpcxt,
 											 DO_AGGSPLIT_SKIPFINAL(aggstate->aggsplit));
 }
@@ -1700,15 +1701,24 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace)
 							 tupleWidth);
 	Size		pergroupSize = numTrans * sizeof(AggStatePerGroupData);
 
-	tupleChunkSize = CHUNKHDRSZ + tupleSize;
-
-	if (pergroupSize > 0)
-		pergroupChunkSize = CHUNKHDRSZ + pergroupSize;
-	else
-		pergroupChunkSize = 0;
+	/*
+	 * Entries use the Bump allocator, so the chunk sizes are the same as the
+	 * requested sizes.
+	 */
+	tupleChunkSize = tupleSize;
+	pergroupChunkSize = pergroupSize;
 
+	/*
+	 * Transition values use AllocSet, which has a chunk header and also uses
+	 * power-of-two allocations.
+	 */
 	if (transitionSpace > 0)
-		transitionChunkSize = CHUNKHDRSZ + transitionSpace;
+	{
+		Size		pow2 = (Size) 1 << my_log2(transitionSpace);
+
+		/* use Max to protect against overflow */
+		transitionChunkSize = Max(CHUNKHDRSZ + pow2, transitionSpace);
+	}
 	else
 		transitionChunkSize = 0;
 
@@ -1858,15 +1868,18 @@ hash_agg_check_limits(AggState *aggstate)
 	uint64		ngroups = aggstate->hash_ngroups_current;
 	Size		meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt,
 													 true);
-	Size		hashkey_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory,
-														true);
+	Size		entry_mem = MemoryContextMemAllocated(aggstate->hash_tablecxt,
+													  true);
+	Size		tval_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory,
+													 true);
+	Size		total_mem = meta_mem + entry_mem + tval_mem;
 
 	/*
 	 * Don't spill unless there's at least one group in the hash table so we
 	 * can be sure to make progress even in edge cases.
 	 */
 	if (aggstate->hash_ngroups_current > 0 &&
-		(meta_mem + hashkey_mem > aggstate->hash_mem_limit ||
+		(total_mem > aggstate->hash_mem_limit ||
 		 ngroups > aggstate->hash_ngroups_limit))
 	{
 		hash_agg_enter_spill_mode(aggstate);
@@ -1917,6 +1930,7 @@ static void
 hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 {
 	Size		meta_mem;
+	Size		entry_mem;
 	Size		hashkey_mem;
 	Size		buffer_mem;
 	Size		total_mem;
@@ -1928,7 +1942,10 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 	/* memory for the hash table itself */
 	meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt, true);
 
-	/* memory for the group keys and transition states */
+	/* memory for hash entries */
+	entry_mem = MemoryContextMemAllocated(aggstate->hash_tablecxt, true);
+
+	/* memory for byref transition states */
 	hashkey_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory, true);
 
 	/* memory for read/write tape buffers, if spilled */
@@ -1937,7 +1954,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 		buffer_mem += HASHAGG_READ_BUFFER_SIZE;
 
 	/* update peak mem */
-	total_mem = meta_mem + hashkey_mem + buffer_mem;
+	total_mem = meta_mem + entry_mem + hashkey_mem + buffer_mem;
 	if (total_mem > aggstate->hash_mem_peak)
 		aggstate->hash_mem_peak = total_mem;
 
@@ -1959,6 +1976,58 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 	}
 }
 
+/*
+ * Create memory contexts used for hash aggregation.
+ */
+static void
+hash_create_memory(AggState *aggstate)
+{
+	Size		minContextSize = ALLOCSET_DEFAULT_MINSIZE;
+	Size		initBlockSize = ALLOCSET_DEFAULT_INITSIZE;
+	Size		maxBlockSize = ALLOCSET_DEFAULT_MAXSIZE;
+
+	/*
+	 * The hashcontext's per-tuple memory will be used for byref transition
+	 * values and returned by AggCheckCallContext().
+	 */
+	aggstate->hashcontext = CreateWorkExprContext(aggstate->ss.ps.state);
+
+	/*
+	 * The meta context will be used for the bucket array of
+	 * TupleHashEntryData (or arrays, in the case of grouping sets). As the
+	 * hash table grows, the bucket array will double in size and the old one
+	 * will be freed, so an AllocSet is appropriate. For large bucket arrays,
+	 * the large allocation path will be used, so it's not worth worrying
+	 * about wasting space due to power-of-two allocations.
+	 */
+	aggstate->hash_metacxt = AllocSetContextCreate(aggstate->ss.ps.state->es_query_cxt,
+												   "HashAgg meta context",
+												   ALLOCSET_DEFAULT_SIZES);
+
+	/*
+	 * The hash entries themselves, which include the grouping key
+	 * (firstTuple) and pergroup data, are stored in the table context. The
+	 * bump allocator can be used because the entries are not freed until the
+	 * entire hash table is reset. The bump allocator is faster for
+	 * allocations and avoids wasting space on the chunk header or
+	 * power-of-two allocations.
+	 *
+	 * Like CreateWorkExprContext(), use smaller sizings for smaller work_mem,
+	 * to avoid large jumps in memory usage.
+	 */
+	while (16 * maxBlockSize > work_mem * 1024L)
+		maxBlockSize >>= 1;
+
+	if (maxBlockSize < ALLOCSET_DEFAULT_INITSIZE)
+		maxBlockSize = ALLOCSET_DEFAULT_INITSIZE;
+
+	aggstate->hash_tablecxt = BumpContextCreate(aggstate->ss.ps.state->es_query_cxt,
+												"HashAgg table context",
+												minContextSize, initBlockSize,
+												maxBlockSize);
+
+}
+
 /*
  * Choose a reasonable number of buckets for the initial hash table size.
  */
@@ -2618,6 +2687,7 @@ agg_refill_hash_table(AggState *aggstate)
 
 	/* free memory and reset hash tables */
 	ReScanExprContext(aggstate->hashcontext);
+	MemoryContextReset(aggstate->hash_tablecxt);
 	for (int setno = 0; setno < aggstate->num_hashes; setno++)
 		ResetTupleHashTable(aggstate->perhash[setno].hashtable);
 
@@ -3285,7 +3355,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 	}
 
 	if (use_hashing)
-		aggstate->hashcontext = CreateWorkExprContext(estate);
+		hash_create_memory(aggstate);
 
 	ExecAssignExprContext(estate, &aggstate->ss.ps);
 
@@ -3580,9 +3650,6 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 		Plan	   *outerplan = outerPlan(node);
 		uint64		totalGroups = 0;
 
-		aggstate->hash_metacxt = AllocSetContextCreate(aggstate->ss.ps.state->es_query_cxt,
-													   "HashAgg meta context",
-													   ALLOCSET_DEFAULT_SIZES);
 		aggstate->hash_spill_rslot = ExecInitExtraTupleSlot(estate, scanDesc,
 															&TTSOpsMinimalTuple);
 		aggstate->hash_spill_wslot = ExecInitExtraTupleSlot(estate, scanDesc,
@@ -4327,6 +4394,12 @@ ExecEndAgg(AggState *node)
 		MemoryContextDelete(node->hash_metacxt);
 		node->hash_metacxt = NULL;
 	}
+	if (node->hash_tablecxt != NULL)
+	{
+		MemoryContextDelete(node->hash_tablecxt);
+		node->hash_tablecxt = NULL;
+	}
+
 
 	for (transno = 0; transno < node->numtrans; transno++)
 	{
@@ -4443,6 +4516,7 @@ ExecReScanAgg(AggState *node)
 		node->hash_ngroups_current = 0;
 
 		ReScanExprContext(node->hashcontext);
+		MemoryContextReset(node->hash_tablecxt);
 		/* Rebuild an empty hash table */
 		build_hash_tables(node);
 		node->table_filled = false;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index d46ce9b4996..999d06aa570 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2558,7 +2558,8 @@ typedef struct AggState
 	/* these fields are used in AGG_HASHED and AGG_MIXED modes: */
 	bool		table_filled;	/* hash table filled yet? */
 	int			num_hashes;
-	MemoryContext hash_metacxt; /* memory for hash table itself */
+	MemoryContext hash_metacxt; /* memory for hash table bucket array */
+	MemoryContext hash_tablecxt;	/* memory for hash table entries */
 	struct LogicalTapeSet *hash_tapeset;	/* tape set for hash spill tapes */
 	struct HashAggSpill *hash_spills;	/* HashAggSpill for each grouping set,
 										 * exists only during first pass */
@@ -2584,7 +2585,7 @@ typedef struct AggState
 										 * per-group pointers */
 
 	/* support for evaluation of agg input expressions: */
-#define FIELDNO_AGGSTATE_ALL_PERGROUPS 53
+#define FIELDNO_AGGSTATE_ALL_PERGROUPS 54
 	AggStatePerGroup *all_pergroups;	/* array of first ->pergroups, than
 										 * ->hash_pergroup */
 	SharedAggInfo *shared_info; /* one entry per worker */
diff --git a/src/test/regress/expected/groupingsets.out b/src/test/regress/expected/groupingsets.out
index d7c9b44605d..0e86e31fe90 100644
--- a/src/test/regress/expected/groupingsets.out
+++ b/src/test/regress/expected/groupingsets.out
@@ -1711,7 +1711,7 @@ explain (costs off)
          ->  Seq Scan on tenk1
 (9 rows)
 
-set work_mem = '384kB';
+set work_mem = '256kB';
 explain (costs off)
   select unique1,
          count(two), count(four), count(ten),
diff --git a/src/test/regress/sql/groupingsets.sql b/src/test/regress/sql/groupingsets.sql
index 21cd3121940..10f3c36d5c6 100644
--- a/src/test/regress/sql/groupingsets.sql
+++ b/src/test/regress/sql/groupingsets.sql
@@ -467,7 +467,7 @@ explain (costs off)
          count(*)
     from tenk1 group by grouping sets (unique1,hundred,ten,four,two);
 
-set work_mem = '384kB';
+set work_mem = '256kB';
 explain (costs off)
   select unique1,
          count(two), count(four), count(ten),
-- 
2.34.1

---

From: Jeff Davis <[email-masked]>
Date: Wed, 12 Feb 2025 17:01:29 -0800

> Attached a new series that implements this idea.

Attached a new patchset that doesn't change the API for
ExecCopySlotMinimalTuple(). Instead, I'm using
ExecFetchSlotMinimalTuple(), which avoids the extra memcpy if the slot
is TTSOpsMinimalTuple, which is what HashAgg uses. I separated out the
change to use ExecFetchSlotMinimalTuple() into 0004 to illustrate the
performance impact.

DATA:
  create table a (a text not null);
  insert into a select repeat(md5(a::text),10)
    from generate_Series(1,1000) a;
  vacuum freeze analyze a;
  create table b (b text not null);
  insert into b select repeat(md5(b::text),10)
    from generate_Series(1001,2000) b;
  vacuum freeze analyze b;

QUERY: select a,count(*) from a group by a;

  master: tps = 2054.742658 (without initial connection time)
  0001:   tps = 2068.620429 (without initial connection time)
  0002:   tps = 2027.046422 (without initial connection time)
  0003:   tps = 1951.392904 (without initial connection time)
  0004:   tps = 2071.690037 (without initial connection time)

QUERY: select * from a except select * from b;

  master: tps = 1720.168862 (without initial connection time)
  0001:   tps = 1703.040810 (without initial connection time)
  0002:   tps = 1687.191715 (without initial connection time)
  0003:   tps = 1579.975535 (without initial connection time)
  0004:   tps = 1616.741447 (without initial connection time)

So the GROUP BY query has no regression (because there's no additional
copy) and the EXCEPT query has about a 6% regression.

The v6 series doesn't have that regression for set operations, but it
requires the somewhat-messy ExecCopySlotMinimalTupleExtra() API. If you
think you'll use that in nodeMemoize, then the API change is worth it.
If not, it feels a bit like a hack.

Another thing I did in the v7 series is I stored the additional data
before the firstTuple. It seems cleaner to store the fixed-length data
first -- I could do the same thing if we go with
ExecCopySlotMinimalTupleExtra().

In any case, it seems like we have agreement to switch to the Bump
context, so I'll do another round of tests to see if there are any
downsides, then clean it up and commit v7-0001.

Regards,
	Jeff Davis

From b0023cde3798a481c7a7f1f453be3d037ef4c2f5 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Wed, 8 Jan 2025 11:46:35 -0800
Subject: [PATCH v7 1/4] HashAgg: use Bump allocator for hash TupleHashTable
 entries.

index ae9cc256b8c..340a2010101 100644
@@ -406,6 +406,7 @@ static void build_hash_tables(AggState *aggstate);
@@ -1512,7 +1513,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets)
 
@@ -1538,7 +1539,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets)
 											 nbuckets,
 											 additionalsize,
 											 metacxt,
-											 hashcxt,
+											 tablecxt,
 											 tmpcxt,
 											 DO_AGGSPLIT_SKIPFINAL(aggstate->aggsplit));
 }
@@ -1709,15 +1710,24 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace)
 							 tupleWidth);
 	Size		pergroupSize = numTrans * sizeof(AggStatePerGroupData);

+	/*
 
@@ -1867,8 +1877,11 @@ hash_agg_check_limits(AggState *aggstate)
 	bool		do_spill = false;
 
 #ifdef USE_INJECTION_POINTS
@@ -1887,7 +1900,7 @@ hash_agg_check_limits(AggState *aggstate)
 	 * can be sure to make progress even in edge cases.
 	 */
 	if (aggstate->hash_ngroups_current > 0 &&
-		(meta_mem + hashkey_mem > aggstate->hash_mem_limit ||
+		(total_mem > aggstate->hash_mem_limit ||
 		 ngroups > aggstate->hash_ngroups_limit))
 	{
 		do_spill = true;
@@ -1942,6 +1955,7 @@ static void
 hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 {
 	Size		meta_mem;
+	Size		entry_mem;
 	Size		hashkey_mem;
 	Size		buffer_mem;
 	Size		total_mem;
@@ -1953,7 +1967,10 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 	/* memory for the hash table itself */
 	meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt, true);

 	/* memory for read/write tape buffers, if spilled */
@@ -1962,7 +1979,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 		buffer_mem += HASHAGG_READ_BUFFER_SIZE;
 
 	/* update peak mem */
 
@@ -1984,6 +2001,58 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 	}
 }
 
+/*
@@ -2647,6 +2716,7 @@ agg_refill_hash_table(AggState *aggstate)

@@ -3331,7 +3401,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 	}
 
 	if (use_hashing)

@@ -3626,9 +3696,6 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
 		Plan	   *outerplan = outerPlan(node);
 		uint64		totalGroups = 0;
 
@@ -4373,6 +4440,12 @@ ExecEndAgg(AggState *node)
 
 	for (transno = 0; transno < node->numtrans; transno++)
 	{
@@ -4489,6 +4562,7 @@ ExecReScanAgg(AggState *node)
 		node->hash_ngroups_current = 0;
 
index e2d1dc1e067..1aacad936af 100644
@@ -2563,7 +2563,8 @@ typedef struct AggState
@@ -2589,7 +2590,7 @@ typedef struct AggState
 										 * per-group pointers */

-set work_mem = '384kB';
+set work_mem = '256kB';
 explain (costs off)
   select unique1,
 
-set work_mem = '384kB';
+set work_mem = '256kB';
 explain (costs off)
   select unique1,

From d76e51114cb4e50fd36905ffcb446652fa64a62c Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Mon, 13 Jan 2025 14:37:02 -0800
Subject: [PATCH v7 2/4] Refactor: accessors for TupleHashEntryData.

Previously, callers were accessing fields directly, making it more
difficult to optimize.

A subsequent patch will combine firstTuple and the additionalsize into
a single allocation.

Discussion: https://postgr.es/m/817d244237878cebdff0bc363718feaf49a1ea7d.camel%40j-davis.com
---
 src/backend/executor/execGrouping.c |  7 ++++--
 src/backend/executor/nodeAgg.c      | 32 +++++++++++++---------------
 src/backend/executor/nodeSetOp.c    | 23 +++++++++++---------
 src/backend/executor/nodeSubplan.c  |  2 +-
 src/include/executor/executor.h     | 33 +++++++++++++++++++++++++++++
 src/include/nodes/execnodes.h       |  1 +
 6 files changed, 68 insertions(+), 30 deletions(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 33b124fbb0a..450fe74bec5 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -196,6 +196,7 @@ BuildTupleHashTable(PlanState *parent,
 	hashtable->tab_collations = collations;
 	hashtable->tablecxt = tablecxt;
 	hashtable->tempcxt = tempcxt;
+	hashtable->additionalsize = additionalsize;
 	hashtable->tableslot = NULL;	/* will be made on first lookup */
 	hashtable->inputslot = NULL;
 	hashtable->in_hash_expr = NULL;
@@ -479,11 +480,13 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 		{
 			/* created new entry */
 			*isnew = true;
-			/* zero caller data */
-			entry->additional = NULL;
+
 			MemoryContextSwitchTo(hashtable->tablecxt);
+
 			/* Copy the first tuple into the table context */
 			entry->firstTuple = ExecCopySlotMinimalTuple(slot);
+
+			entry->additional = palloc0(hashtable->additionalsize);
 		}
 	}
 	else
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 340a2010101..af0b7b27383 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1494,7 +1494,7 @@ build_hash_tables(AggState *aggstate)
 #ifdef USE_INJECTION_POINTS
 		if (IS_INJECTION_POINT_ATTACHED("hash-aggregate-oversize-table"))
 		{
-			nbuckets = memory / sizeof(TupleHashEntryData);
+			nbuckets = memory / TupleHashEntrySize();
 			INJECTION_POINT_CACHED("hash-aggregate-oversize-table");
 		}
 #endif
@@ -1732,7 +1732,7 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace)
 		transitionChunkSize = 0;
 
 	return
-		sizeof(TupleHashEntryData) +
+		TupleHashEntrySize() +
 		tupleChunkSize +
 		pergroupChunkSize +
 		transitionChunkSize;
@@ -1996,7 +1996,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions)
 	if (aggstate->hash_ngroups_current > 0)
 	{
 		aggstate->hashentrysize =
-			sizeof(TupleHashEntryData) +
+			TupleHashEntrySize() +
 			(hashkey_mem / (double) aggstate->hash_ngroups_current);
 	}
 }
@@ -2149,11 +2149,7 @@ initialize_hash_entry(AggState *aggstate, TupleHashTable hashtable,
 	if (aggstate->numtrans == 0)
 		return;
 
+	pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(hashtable, entry);
 
 	/*
 	 * Initialize aggregates for new tuple group, lookup_hash_entries()
@@ -2217,7 +2213,7 @@ lookup_hash_entries(AggState *aggstate)
 		{
 			if (isnew)
 				initialize_hash_entry(aggstate, hashtable, entry);
-			pergroup[setno] = entry->additional;
+			pergroup[setno] = TupleHashEntryGetAdditional(hashtable, entry);
 		}
 		else
 		{
@@ -2750,6 +2746,7 @@ agg_refill_hash_table(AggState *aggstate)
 	INJECTION_POINT("hash-aggregate-process-batch");
 	for (;;)
 	{
+		TupleHashTable hashtable = perhash->hashtable;
 		TupleTableSlot *spillslot = aggstate->hash_spill_rslot;
 		TupleTableSlot *hashslot = perhash->hashslot;
 		TupleHashEntry entry;
@@ -2770,14 +2767,14 @@ agg_refill_hash_table(AggState *aggstate)
 		prepare_hash_slot(perhash,
 						  aggstate->tmpcontext->ecxt_outertuple,
 						  hashslot);
-		entry = LookupTupleHashEntryHash(perhash->hashtable, hashslot,
+		entry = LookupTupleHashEntryHash(hashtable, hashslot,
 										 p_isnew, hash);
 
 		if (entry != NULL)
 		{
 			if (isnew)
-				initialize_hash_entry(aggstate, perhash->hashtable, entry);
-			aggstate->hash_pergroup[batch->setno] = entry->additional;
+				initialize_hash_entry(aggstate, hashtable, entry);
+			aggstate->hash_pergroup[batch->setno] = TupleHashEntryGetAdditional(hashtable, entry);
 			advance_aggregates(aggstate);
 		}
 		else
@@ -2869,7 +2866,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 	ExprContext *econtext;
 	AggStatePerAgg peragg;
 	AggStatePerGroup pergroup;
-	TupleHashEntryData *entry;
+	TupleHashEntry entry;
 	TupleTableSlot *firstSlot;
 	TupleTableSlot *result;
 	AggStatePerHash perhash;
@@ -2895,6 +2892,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 	 */
 	for (;;)
 	{
+		TupleHashTable hashtable = perhash->hashtable;
 		TupleTableSlot *hashslot = perhash->hashslot;
 		int			i;
 
@@ -2903,7 +2901,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 		/*
 		 * Find the next entry in the hash table
 		 */
-		entry = ScanTupleHashTable(perhash->hashtable, &perhash->hashiter);
+		entry = ScanTupleHashTable(hashtable, &perhash->hashiter);
 		if (entry == NULL)
 		{
 			int			nextset = aggstate->current_set + 1;
@@ -2918,7 +2916,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 
 				perhash = &aggstate->perhash[aggstate->current_set];
 
-				ResetTupleHashIterator(perhash->hashtable, &perhash->hashiter);
+				ResetTupleHashIterator(hashtable, &perhash->hashiter);
 
 				continue;
 			}
@@ -2941,7 +2939,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 
 		ExecClearTuple(firstSlot);
@@ -2957,7 +2955,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate)
 		}
 		ExecStoreVirtualTuple(firstSlot);
 
-		pergroup = (AggStatePerGroup) entry->additional;
+		pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(hashtable, entry);
 
 		/*
 		 * Use the representative input tuple for any references to
diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c
index 5b7ff9c3748..cbdc717850c 100644
--- a/src/backend/executor/nodeSetOp.c
+++ b/src/backend/executor/nodeSetOp.c
@@ -424,7 +424,9 @@ setop_fill_hash_table(SetOpState *setopstate)
 	for (;;)
 	{
 		TupleTableSlot *outerslot;
+		TupleHashTable hashtable = setopstate->hashtable;
 		TupleHashEntryData *entry;
+		SetOpStatePerGroup pergroup;
 		bool		isnew;
 
 		outerslot = ExecProcNode(outerPlan);
@@ -433,20 +435,20 @@ setop_fill_hash_table(SetOpState *setopstate)
 		have_tuples = true;
 
 		/* Find or build hashtable entry for this tuple's group */
-		entry = LookupTupleHashEntry(setopstate->hashtable,
+		entry = LookupTupleHashEntry(hashtable,
 									 outerslot,
 									 &isnew, NULL);
 
+		pergroup = TupleHashEntryGetAdditional(hashtable, entry);
 
 		/* Advance the counts */
 
 		/* Must reset expression context after each hashtable lookup */
 		ResetExprContext(econtext);
@@ -464,6 +466,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 		 */
 		for (;;)
 		{
+			TupleHashTable hashtable = setopstate->hashtable;
 			TupleTableSlot *innerslot;
 			TupleHashEntryData *entry;
 
@@ -472,13 +475,13 @@ setop_fill_hash_table(SetOpState *setopstate)
 				break;
 
 			/* For tuples not seen previously, do not make hashtable entry */
-			entry = LookupTupleHashEntry(setopstate->hashtable,
+			entry = LookupTupleHashEntry(hashtable,
 										 innerslot,
 										 NULL, NULL);
 
 			/* Advance the counts if entry is already present */
 			if (entry)
-				((SetOpStatePerGroup) entry->additional)->numRight++;
+				((SetOpStatePerGroup) TupleHashEntryGetAdditional(hashtable, entry))->numRight++;
 
@@ -496,7 +499,7 @@ setop_fill_hash_table(SetOpState *setopstate)
 
 	/*
@@ -526,12 +529,12 @@ setop_retrieve_hash_table(SetOpState *setopstate)
 		 * See if we should emit any copies of this tuple, and if so return
 		 * the first copy.
 		 */
-		set_output_count(setopstate, (SetOpStatePerGroup) entry->additional);
+		set_output_count(setopstate, (SetOpStatePerGroup) TupleHashEntryGetAdditional(setopstate->hashtable, entry));

-		ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false);
+		ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashtable->tableslot, false);
 		if (!execTuplesUnequal(slot, hashtable->tableslot,
 							   numCols, keyColIdx,
 							   eqfunctions,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 30e2a82346f..ee93b479c92 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -157,6 +157,39 @@ extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
 										 ExprState *hashexpr);
 extern void ResetTupleHashTable(TupleHashTable hashtable);
 
+#ifndef FRONTEND
+/*
+static inline size_t
+static inline void *
+TupleHashEntryGetAdditional(TupleHashTable hashtable, TupleHashEntry entry)
  * prototypes from functions in execJunk.c
index 1aacad936af..11aa110cf9c 100644
@@ -860,6 +860,7 @@ typedef struct TupleHashTableData

From 3e21d4328af39e52df0e1ec49a8234a328506f75 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Tue, 14 Jan 2025 16:17:00 -0800
Subject: [PATCH v7 3/4] Combine firstTuple and additionalsize into a single
 allocation.

Saves space in TupleHashEntryData by removing the "additional"
pointer. TupleHashEntryData is required for each bucket, whether
occupied or not, so that space is more valuable than other hash table
allocations.

Discussion: https://postgr.es/m/817d244237878cebdff0bc363718feaf49a1ea7d.camel%40j-davis.com
---
 src/backend/executor/execGrouping.c | 33 +++++++++++++++++++++++------
 src/include/executor/executor.h     |  9 ++++----
 src/include/nodes/execnodes.h       |  1 -
 3 files changed, 31 insertions(+), 12 deletions(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 450fe74bec5..76b16101dbd 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -196,7 +196,7 @@ BuildTupleHashTable(PlanState *parent,
 	hashtable->tab_collations = collations;
 	hashtable->tablecxt = tablecxt;
 	hashtable->tempcxt = tempcxt;
-	hashtable->additionalsize = additionalsize;
+	hashtable->additionalsize = MAXALIGN(additionalsize);
 	hashtable->tableslot = NULL;	/* will be made on first lookup */
 	hashtable->inputslot = NULL;
 	hashtable->in_hash_expr = NULL;
@@ -478,15 +478,34 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 		}
 		else
 		{
+			char	   *data;
+			MinimalTuple tmpTuple;
+			Size		totalsize;
+
 			/* created new entry */
 			*isnew = true;
 
-			MemoryContextSwitchTo(hashtable->tablecxt);
-
-			/* Copy the first tuple into the table context */
-			entry->firstTuple = ExecCopySlotMinimalTuple(slot);
-
-			entry->additional = palloc0(hashtable->additionalsize);
+			/* get minimal tuple in temp context */
+			MemoryContextSwitchTo(hashtable->tempcxt);
+			tmpTuple = ExecCopySlotMinimalTuple(slot);
+
+			/*
+			 * Allocate space for additionalsize followed by the MinimalTuple
+			 * in the table context, and copy the tuple. A single allocation
+			 * avoids the need to store two pointers in TupleHashEntryData.
+			 */
+			totalsize = hashtable->additionalsize + tmpTuple->t_len;
+			data = MemoryContextAlloc(hashtable->tablecxt, totalsize);
+			memset(data, 0, hashtable->additionalsize);
+
+			/*
+			 * firstTuple points in the middle of the allocated space. The
+			 * additional data pointer can be computed by subtracting
+			 * additionalsize from firstTuple.
+			 */
+			data += hashtable->additionalsize;
+			entry->firstTuple = (MinimalTuple) data;
+			memcpy(entry->firstTuple, tmpTuple, tmpTuple->t_len);
 		}
 	}
 	else
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index ee93b479c92..344c5f8a54b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -178,15 +178,16 @@ TupleHashEntryGetTuple(TupleHashEntry entry)
 
 /*
 static inline void *
 TupleHashEntryGetAdditional(TupleHashTable hashtable, TupleHashEntry entry)
+	return (char *) entry->firstTuple - hashtable->additionalsize;
 }
 #endif
 
index 11aa110cf9c..a875335cb09 100644
@@ -837,7 +837,6 @@ typedef struct TupleHashTableData *TupleHashTable;

From c8f534aa7954fa30ee3271a1cf157652f086b559 Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email-masked]>
Date: Wed, 12 Feb 2025 13:05:26 -0800
Subject: [PATCH v7 4/4] Use ExecFetchSlotMinimalTuple().

---
 src/backend/executor/execGrouping.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 76b16101dbd..3712bcdf6f5 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -481,13 +481,14 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
 			char	   *data;
 			MinimalTuple tmpTuple;
 			Size		totalsize;
+			bool		shouldFree;
 
 			/* created new entry */
 			*isnew = true;
 
 			/* get minimal tuple in temp context */
 			MemoryContextSwitchTo(hashtable->tempcxt);
-			tmpTuple = ExecCopySlotMinimalTuple(slot);
+			tmpTuple = ExecFetchSlotMinimalTuple(slot, &shouldFree);
 
 			/*
 			 * Allocate space for additionalsize followed by the MinimalTuple
-- 
2.34.1

---

From: Jeff Davis <[email-masked]>
Date: Mon, 17 Feb 2025 21:49:51 -0800

> downsides, then clean it up and commit v7-0001.

Results for v7-0001 (switch to Bump Allocator for table entries).

Setup:

  SET work_mem='10GB';
  SET max_parallel_workers=0;
  SET max_parallel_workers_per_gather=0;

  -- T1: group size avg ~ 1.5
  create table t1(i int8, j numeric);
  insert into t1 select random(1,10000000),sqrt(g)
    from generate_series(1,10000000) g;
  vacuum freeze analyze t1; checkpoint;

  -- T100: group size avg ~100
  create table t100(i int8, j numeric);
  insert into t100 select random(1,100000),sqrt(g)
    from generate_series(1,10000000) g;
  vacuum freeze analyze t100; checkpoint;

Q1: explain analyze select i, count(j) from THETABLE group by i;

                     t1              t100
  master:      776MB / 4085ms    14MB / 1375ms
  patch:       632MB / 4192ms    10MB / 1375ms 

Q2: explain analyze select i, count(j), max(j), sum(j)
      from THETABLE group by i;

                     t1              t100
  master:     3280MB / 7817ms    54MB / 4194ms
  patch:      3048MB / 8103ms    54MB / 4492ms

While it's a memory reduction in all cases, and a ~20% memory reduction
for by-value types; there appears to be some slowdown for by-reference
types -- 7% for Q2 when the group size is 100.

I profiled it and it seems to be spending more time in
advance_aggregates. Since I didn't change that code, the only
explanation I have for that is that with everything in one memory
context, the by-reference values end up near enough to the group key
and pergroup state to benefit from caching effects.

I'm not sure that explanation makes sense though, because even in the
old code where they are both in the same memory context, why would we
expect the transition values to be close to the grouping key or
pergroup state?

Regards,
	Jeff Davis

---

From: David Rowley <[email-masked]>
Date: Fri, 28 Feb 2025 17:09:13 +1300

> change to use ExecFetchSlotMinimalTuple() into 0004 to illustrate the

Some review comments:

* my_log2() takes a "long" parameter type but transitionSpace is a
"Size". These types aren't the same width on all platforms we support.
Maybe pg_nextpower2_size_t() is a better option.

* Should the following have MAXALIGN(tupleSize) on the right side of
the expression?

tupleChunkSize = tupleSize

I understand this was missing before, but both bump.c does consume at
least MAXALIGN(<req_size>) in BumpAlloc().

* while (16 * maxBlockSize > work_mem * 1024L)

The 1024L predates the change made in 041e8b95. "1024L" needs to be
replaced with "(Size) 1024"

Maybe you could just replace the while loop and the subsequent "if" check with:

/*
 * Like CreateWorkExprContext(), use smaller sizings for smaller work_mem,
 * to avoid large jumps in memory usage.
 */
maxBlockSize = pg_prevpower2_size_t(work_mem * (Size) 1024 / 16);

/* But no bigger than ALLOCSET_DEFAULT_MAXSIZE */
maxBlockSize = Min(maxBlockSize, ALLOCSET_DEFAULT_MAXSIZE);

/* and no smaller than ALLOCSET_DEFAULT_INITSIZE */
maxBlockSize = Max(maxBlockSize, ALLOCSET_DEFAULT_INITSIZE);

I believe that gives the same result without the looping.

* In hash_create_memory(), can you get rid of the minContextSize and
initBlockSize variables?

* Is it worth an Assert() theck additionalsize > 0?

 * The amount of space available is the additionalsize requested in the call
 * to BuildTupleHashTable(). If additionalsize was specified as zero, no
 * additional space is available and this function should not be called.
 */
static inline void *
TupleHashEntryGetAdditional(TupleHashTable hashtable, TupleHashEntry entry)
{
return (char *) entry->firstTuple - hashtable->additionalsize;
}

Benchmarks:

I was also experimenting with the performance of this using the
following test case:

create table c (a int not null);
insert into c select a from generate_Series(1,1000) a;
vacuum freeze analyze c;

Query: select a,count(*) from c group by a;

Average TPS over 10x 10 second runs with -M prepared

master: 3653.9853988
v7-0001: 3741.815979
v7-0001+0002: 3737.4313064
v7-0001+0002+0003: 3834.6271706
v7-0001+0002+0004+0004: 3912.1158887

I also tried out changing hash_agg_check_limits() so that it no longer
calls MemoryContextMemAllocated and instead uses ->mem_allocated
directly and with all the other patches got:

v7-0001+0002+0004+0004+extra: 4049.0732381

We probably shouldn't do exactly that as it be better not to access
that internal field from outside the memory context code.  A static
inline function in memutils.h that handles the non-recursive callers
might be nice.

I've attached my results of running your test in graph form. I also
see a small regression for these small scale tests. I wondering if
it's worth mocking up some code to see what the performance would be
like without the additional memcpy() that's new to
LookupTupleHashEntry_internal().  How about hacking something up that
adds an additionalsize field to TupleDesc and then set that field to
your additional size and have heap_form_minimal_tuple() allocate that
much extra memory?

David