From: Jeff Davis <pgsql@j-davis.com>
To: Andres Freund <andres@anarazel.de>
Cc: pgsql-bugs@postgresql.org
Subject: Re: HashAgg degenerate case
Date: Tue, 12 Nov 2024 15:15:55 -0800
Message-ID: <e061c5439996e13c0fb51997e92d6a09834a7796.camel@j-davis.com> (raw)
In-Reply-To: <3btw7dgj56k5samfzyrxnqdoiocbiycp44osza3iahzn3jqdro@ecxairlbdzqx>
References: <a050b6067334cf513bf34f9c7bc925d651160f3a.camel@j-davis.com>
<4tbbgdqqxvmy37fk75p36azkovyhrjhnul46lntj52jlobphf3@nxaqlaqupg2l>
<33bcc1ef6c4acf80f4fb87c4d9d284c61abb3652.camel@j-davis.com>
<8c60e698428962f33fdfbfab2206eedba09029fc.camel@j-davis.com>
<3btw7dgj56k5samfzyrxnqdoiocbiycp44osza3iahzn3jqdro@ecxairlbdzqx>
On Tue, 2024-11-12 at 10:48 -0500, Andres Freund wrote:
> That assumes the bucket array is a significant portion of the memory
> usage -
> but that's not a given, right?
TupleHashEntryData is 24 bytes, and a the smallest firstTuple (an
integer key and that's it) is 20 bytes plus palloc overhead. So even if
the hash table is perfectly full, it can still be ~50% of total memory
usage. The fraction can of course be smaller with compound grouping
keys and multiple aggregates, but it is still likely to be a
significant fraction.
For example:
create table big(i int, j int);
insert into big select g, 1 from generate_series(1,10000000) g;
vacuum freeze analyze big; checkpoint;
set hash_mem_multiplier = 1;
set work_mem = '430MB';
explain analyze select count(*) from
(select i from big group by i) s;
At peak, it uses ~630MB total (exceeding the memory limit by 40%), of
which ~400MB is in the metacxt. The hashtab has a size of 16777216 and
5896580 members.
Due to the cases that cause grow_threshold to be set to zero, the
bucket array is often about 3X the number of members just after
growing. And if the bucket array consumes most or all of the available
memory, that crowds out memory for the next batch, which may
recursively spill with a very sparse bucket array. That makes it all
the more important that we get that memory usage of the bucket array
under control.
A silver lining is that smaller hash tables often perform better, so
restricting batch size doesn't necessarily cause a regression and may
even improve things. I've known this since I originally wrote the disk-
based HashAgg, and perhaps we should explore this more.
While I'm looking, I also see a couple other areas of potential
improvement:
* can we reduce the size of TupleHashEntryData by having only one
pointer?
* it looks like we should be even more aggressive about partitioning
widely. Sometimes a larger work mem creates a smaller number of
partitions, and it can end up recursing more and producing more total
batches
> The former seems entirely non-viable on performance grounds.
Yeah, I think that was discussed during the original feature
development.
> The latter might
> be ok, but I'm vary on code complexity grounds.
I attached a proof of concept patch, and it does add some complexity,
but it's not terrible. If tuplehash is going to be used for large hash
tables, I don't think we can hide the doubling nature from the caller
forever, assuming that the caller can do something about it (like
spill).
> What about simply checking whether the bucket array was a significant
> portion
> of the memory usage at spill time and recreating the hashtable
> instead of
> resetting IFF it was?
I think that would basically solve the degenerate case, but:
(a) if "significant" means ~40%, then it will trigger recreation for
a lot of cases, and it re-raises the questions about performance
regressions; and
(b) it doesn't correct the problem where we grow the hashtable just
to hold one additional element, causing it to exceed the available
memory and not be able to actually use those new buckets.
(c) it doesn't prevent overshooting the memory limit by a significant
amount
A slightly better approach might be to recreate the hashtable if the
last batch had a hashtable that is less than 10% filled or something,
which will hopefully avoid problem (a).
>
> I doubt any change around this ought to be backpatched. The
> likelihood of
> regressions seems to high.
Perhaps there's some low-risk change we can make, like having a higher
minimum number of groups before spilling, or something like that?
I can move this discussion to -hackers until we sort it out.
Regards,
Jeff Davis
Attachments:download all (2 files, .tar.gz)v1-0001-simplehash-add-grow_ok-to-API.patch (text/x-patch, 3.9K) download
From dc2d997c1a1abfbeb09ba5b63e0cec7df105e8c5 Mon Sep 17 00:00:00 2001
From: Jeff Davis <jeff@j-davis.com>
Date: Mon, 11 Nov 2024 13:56:59 -0800
Subject: [PATCH v1 1/2] simplehash: add "grow_ok" to API.
Allows memory-sensitive callers to add an element iff it will not
cause the bucket array to grow.
Without this API, callers such as HashAgg cannot control memory usage
incrementally because hash table growth means that the size doubles.
---
src/include/lib/simplehash.h | 35 ++++++++++++++++++++++++++++++-----
1 file changed, 30 insertions(+), 5 deletions(-)
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.hindex 3e1b1f9461..0bb3a1c1e2 100644--- a/src/include/lib/simplehash.h+++ b/src/include/lib/simplehash.h@@ -115,6 +115,7 @@
#define SH_RESET SH_MAKE_NAME(reset)
#define SH_INSERT SH_MAKE_NAME(insert)
#define SH_INSERT_HASH SH_MAKE_NAME(insert_hash)
+#define SH_INSERT_EXT SH_MAKE_NAME(insert_ext)
#define SH_DELETE_ITEM SH_MAKE_NAME(delete_item)
#define SH_DELETE SH_MAKE_NAME(delete)
#define SH_LOOKUP SH_MAKE_NAME(lookup)
@@ -135,7 +136,7 @@
#define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance)
#define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket)
#define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash)
-#define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal)+#define SH_INSERT_EXT_INTERNAL SH_MAKE_NAME(insert_ext_internal)
#define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal)
/* generate forward declarations necessary to use the hash table */
@@ -217,6 +218,13 @@ SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found);
SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
uint32 hash, bool *found);
+/*+ * <element> *<prefix>_insert_ext(<prefix>_hash *tb, <key> key, uint32 hash,+ * bool grow_ok, bool *found)+ */+SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT_EXT(SH_TYPE * tb, SH_KEY_TYPE key,+ uint32 hash, bool grow_ok, bool *found);+
/* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);
@@ -606,7 +614,8 @@ SH_GROW(SH_TYPE * tb, uint64 newsize)
* into its wrapper functions even if SH_SCOPE is extern.
*/
static inline SH_ELEMENT_TYPE *
-SH_INSERT_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)+SH_INSERT_EXT_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool grow_ok,+ bool *found)
{
uint32 startelem;
uint32 curelem;
@@ -629,6 +638,9 @@ restart:
if (unlikely(tb->size == SH_MAX_SIZE))
sh_error("hash table size exceeded");
+ if (!grow_ok)+ return NULL;+
/*
* When optimizing, it can be very useful to print these out.
*/
@@ -778,7 +790,7 @@ SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
{
uint32 hash = SH_HASH_KEY(tb, key);
- return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);+ return SH_INSERT_EXT_INTERNAL(tb, key, hash, true, found);
}
/*
@@ -789,7 +801,20 @@ SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
SH_SCOPE SH_ELEMENT_TYPE *
SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
{
- return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);+ return SH_INSERT_EXT_INTERNAL(tb, key, hash, true, found);+}++/*+ * Insert the key into the hash-table using an already-calculated hash. Set+ * *found to true if the key already exists, false otherwise. If growing is+ * necessary, and and !grow_ok, return NULL; otherwise returns the hash-table+ * entry.+ */+SH_SCOPE SH_ELEMENT_TYPE *+SH_INSERT_EXT(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool grow_ok,+ bool *found)+{+ return SH_INSERT_EXT_INTERNAL(tb, key, hash, grow_ok, found);
}
/*
@@ -1202,5 +1227,5 @@ SH_STAT(SH_TYPE * tb)
#undef SH_PREV
#undef SH_DISTANCE_FROM_OPTIMAL
#undef SH_ENTRY_HASH
-#undef SH_INSERT_HASH_INTERNAL+#undef SH_INSERT_EXT_INTERNAL
#undef SH_LOOKUP_HASH_INTERNAL
--
2.34.1
v1-0002-HashAgg-avoid-unexpected-hash-table-growth-near-m.patch (text/x-patch, 11.8K) download
From def25162acace9b9fdb32b1865ccc037de3b69c1 Mon Sep 17 00:00:00 2001
From: Jeff Davis <jeff@j-davis.com>
Date: Mon, 11 Nov 2024 21:28:31 -0800
Subject: [PATCH v1 2/2] HashAgg: avoid unexpected hash table growth near
memory limit.
When the simplehash table size is already a significant fraction of
the memory, and growing it would risk exceeding the memory limit, then
enter a mode in which new groups can be added iff there's room in the
existing bucket array (i.e. it wouldn't trigger SH_GROW()).
---
src/backend/executor/execGrouping.c | 61 ++++++++++++++++++++++++-----
src/backend/executor/nodeAgg.c | 61 +++++++++++++++++++++++------
src/include/executor/executor.h | 11 ++++--
src/include/nodes/execnodes.h | 3 +-
4 files changed, 111 insertions(+), 25 deletions(-)
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.cindex 774e4de882..44dc48c981 100644--- a/src/backend/executor/execGrouping.c+++ b/src/backend/executor/execGrouping.c@@ -25,7 +25,8 @@ static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple);
static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashtable,
TupleTableSlot *slot,
- bool *isnew, uint32 hash);+ bool grow_ok, bool *isnew,+ uint32 hash);
/*
* Define parameters for tuple hash table code generation. The interface is
@@ -320,7 +321,42 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
hashtable->cur_eq_func = hashtable->tab_eq_func;
local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
- entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, local_hash);+ entry = LookupTupleHashEntry_internal(hashtable, slot, true, isnew,+ local_hash);++ if (hash != NULL)+ *hash = local_hash;++ Assert(entry == NULL || entry->hash == local_hash);++ MemoryContextSwitchTo(oldContext);++ return entry;+}++/*+ * Like LookupTupleHashEntry, but allows specifying grow_ok to false, which+ * prevents a new entry from growing the internal bucket array.+ */+TupleHashEntry+LookupTupleHashEntryExt(TupleHashTable hashtable, TupleTableSlot *slot,+ bool grow_ok, bool *isnew, uint32 *hash)+{+ TupleHashEntry entry;+ MemoryContext oldContext;+ uint32 local_hash;++ /* Need to run the hash functions in short-lived context */+ oldContext = MemoryContextSwitchTo(hashtable->tempcxt);++ /* set up data needed by hash and match functions */+ hashtable->inputslot = slot;+ hashtable->in_hash_funcs = hashtable->tab_hash_funcs;+ hashtable->cur_eq_func = hashtable->tab_eq_func;++ local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);+ entry = LookupTupleHashEntry_internal(hashtable, slot, grow_ok, isnew,+ local_hash);
if (hash != NULL)
*hash = local_hash;
@@ -356,11 +392,12 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
/*
* A variant of LookupTupleHashEntry for callers that have already computed
- * the hash value.+ * the hash value. Also allows specifying grow_ok to false, which prevents a+ * new entry from growing the internal bucket array.
*/
TupleHashEntry
-LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,- bool *isnew, uint32 hash)+LookupTupleHashEntryHashExt(TupleHashTable hashtable, TupleTableSlot *slot,+ bool grow_ok, bool *isnew, uint32 hash)
{
TupleHashEntry entry;
MemoryContext oldContext;
@@ -373,7 +410,8 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
hashtable->cur_eq_func = hashtable->tab_eq_func;
- entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);+ entry = LookupTupleHashEntry_internal(hashtable, slot, grow_ok, isnew,+ hash);
Assert(entry == NULL || entry->hash == hash);
MemoryContextSwitchTo(oldContext);
@@ -490,12 +528,15 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
* so that we can avoid switching the memory context multiple times for
* LookupTupleHashEntry.
*
+ * If grow_ok is false, returns NULL if adding a new entry would cause the+ * internal tuplehash bucket array to grow (that is, to double in size).+ *
* NB: This function may or may not change the memory context. Caller is
* expected to change it back.
*/
static inline TupleHashEntry
LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
- bool *isnew, uint32 hash)+ bool grow_ok, bool *isnew, uint32 hash)
{
TupleHashEntryData *entry;
bool found;
@@ -505,11 +546,11 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
if (isnew)
{
- entry = tuplehash_insert_hash(hashtable->hashtab, key, hash, &found);+ entry = tuplehash_insert_ext(hashtable->hashtab, key, hash, grow_ok,+ &found);- if (found)+ if (entry == NULL || found)
{
- /* found pre-existing entry */
*isnew = false;
}
else
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.cindex 53ead77ece..221cee1cd5 100644--- a/src/backend/executor/nodeAgg.c+++ b/src/backend/executor/nodeAgg.c@@ -1494,6 +1494,7 @@ build_hash_tables(AggState *aggstate)
}
aggstate->hash_ngroups_current = 0;
+ aggstate->hash_grow_ok = true;
}
/*
@@ -1861,6 +1862,19 @@ hash_agg_check_limits(AggState *aggstate)
Size hashkey_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory,
true);
+ /*+ * The bucket array is stored in hash_metacxt, and each time it grows, it+ * doubles. If doubling the bucket array would put us over the memory+ * limit, then we must set hash_grow_ok to false to prevent it.+ *+ * When multiple grouping sets are involved, this calculation is overly+ * conservative, because growing a single hashtable will not double the+ * overall meta_mem. But that only affects the first batch; subsequent+ * batches only deal with a single grouping set at a time.+ */+ if (meta_mem * 2 + hashkey_mem > aggstate->hash_mem_limit)+ aggstate->hash_grow_ok = false;+
/*
* 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.
@@ -2103,7 +2117,7 @@ lookup_hash_entries(AggState *aggstate)
AggStatePerHash perhash = &aggstate->perhash[setno];
TupleHashTable hashtable = perhash->hashtable;
TupleTableSlot *hashslot = perhash->hashslot;
- TupleHashEntry entry;+ TupleHashEntry entry = NULL;
uint32 hash;
bool isnew = false;
bool *p_isnew;
@@ -2116,16 +2130,25 @@ lookup_hash_entries(AggState *aggstate)
outerslot,
hashslot);
- entry = LookupTupleHashEntry(hashtable, hashslot,- p_isnew, &hash);-- if (entry != NULL)+ entry = LookupTupleHashEntryExt(hashtable, hashslot,+ aggstate->hash_grow_ok,+ p_isnew, &hash);+ if (entry)
{
if (isnew)
initialize_hash_entry(aggstate, hashtable, entry);
pergroup[setno] = entry->additional;
}
- else+ else if (!aggstate->hash_spill_mode)+ {+ /*+ * New entry would grow hash table bucket array, and may put us+ * over the memory limit.+ */+ hash_agg_enter_spill_mode(aggstate);+ }++ if (!entry)
{
HashAggSpill *spill = &aggstate->hash_spills[setno];
TupleTableSlot *slot = aggstate->tmpcontext->ecxt_outertuple;
@@ -2626,6 +2649,7 @@ agg_refill_hash_table(AggState *aggstate)
ResetTupleHashTable(aggstate->perhash[setno].hashtable);
aggstate->hash_ngroups_current = 0;
+ aggstate->hash_grow_ok = true;
/*
* In AGG_MIXED mode, hash aggregation happens in phase 1 and the output
@@ -2656,7 +2680,7 @@ agg_refill_hash_table(AggState *aggstate)
{
TupleTableSlot *spillslot = aggstate->hash_spill_rslot;
TupleTableSlot *hashslot = perhash->hashslot;
- TupleHashEntry entry;+ TupleHashEntry entry = NULL;
MinimalTuple tuple;
uint32 hash;
bool isnew = false;
@@ -2674,17 +2698,28 @@ agg_refill_hash_table(AggState *aggstate)
prepare_hash_slot(perhash,
aggstate->tmpcontext->ecxt_outertuple,
hashslot);
- entry = LookupTupleHashEntryHash(perhash->hashtable, hashslot,- p_isnew, hash);- if (entry != NULL)+ entry = LookupTupleHashEntryHashExt(perhash->hashtable, hashslot,+ true, p_isnew,+ hash);++ if (entry)
{
if (isnew)
initialize_hash_entry(aggstate, perhash->hashtable, entry);
aggstate->hash_pergroup[batch->setno] = entry->additional;
advance_aggregates(aggstate);
}
- else+ else if (!aggstate->hash_spill_mode)+ {+ /*+ * New entry would grow hash table bucket array, and may put us+ * over the memory limit.+ */+ hash_agg_enter_spill_mode(aggstate);+ }++ if (!entry)
{
if (!spill_initialized)
{
@@ -2723,6 +2758,7 @@ agg_refill_hash_table(AggState *aggstate)
else
hash_agg_update_metrics(aggstate, true, 0);
+ aggstate->hash_grow_ok = true;
aggstate->hash_spill_mode = false;
/* prepare to walk the first hash table */
@@ -3082,6 +3118,7 @@ hashagg_finish_initial_spills(AggState *aggstate)
hash_agg_update_metrics(aggstate, false, total_npartitions);
aggstate->hash_spill_mode = false;
+ aggstate->hash_grow_ok = true;
}
/*
@@ -3225,6 +3262,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags)
aggstate->grp_firstTuple = NULL;
aggstate->sort_in = NULL;
aggstate->sort_out = NULL;
+ aggstate->hash_grow_ok = true;
/*
* phases[0] always exists, but is dummy in sorted/plain mode
@@ -4449,6 +4487,7 @@ ExecReScanAgg(AggState *node)
{
hashagg_reset_spill_state(node);
+ node->hash_grow_ok = true;
node->hash_ever_spilled = false;
node->hash_spill_mode = false;
node->hash_ngroups_current = 0;
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.hindex 69c3ebff00..100facd155 100644--- a/src/include/executor/executor.h+++ b/src/include/executor/executor.h@@ -152,11 +152,16 @@ extern TupleHashTable BuildTupleHashTableExt(PlanState *parent,
extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
bool *isnew, uint32 *hash);
+extern TupleHashEntry LookupTupleHashEntryExt(TupleHashTable hashtable,+ TupleTableSlot *slot,+ bool grow_ok, bool *isnew,+ uint32 *hash);
extern uint32 TupleHashTableHash(TupleHashTable hashtable,
TupleTableSlot *slot);
-extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,- TupleTableSlot *slot,- bool *isnew, uint32 hash);+extern TupleHashEntry LookupTupleHashEntryHashExt(TupleHashTable hashtable,+ TupleTableSlot *slot,+ bool grow_ok, bool *isnew,+ uint32 hash);
extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.hindex 182a6956bb..0c25d706f9 100644--- a/src/include/nodes/execnodes.h+++ b/src/include/nodes/execnodes.h@@ -2543,6 +2543,7 @@ typedef struct AggState
TupleTableSlot *hash_spill_rslot; /* for reading spill files */
TupleTableSlot *hash_spill_wslot; /* for writing spill files */
List *hash_batches; /* hash batches remaining to be processed */
+ bool hash_grow_ok;
bool hash_ever_spilled; /* ever spilled during this execution? */
bool hash_spill_mode; /* we hit a limit during the current batch
* and we must not create new groups */
@@ -2562,7 +2563,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 */
--
2.34.1
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-bugs@postgresql.org
Cc: pgsql@j-davis.com, andres@anarazel.de
Subject: Re: HashAgg degenerate case
In-Reply-To: <e061c5439996e13c0fb51997e92d6a09834a7796.camel@j-davis.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox