pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedHashAgg degenerate case
9+ messages / 3 participants
[nested] [flat]
* HashAgg degenerate case
@ 2024-11-06 00:59 Jeff Davis <pgsql@j-davis.com>
2024-11-06 02:50 ` Re: HashAgg degenerate case David Rowley <dgrowleyml@gmail.com>
2024-11-08 16:41 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
0 siblings, 2 replies; 9+ messages in thread
From: Jeff Davis @ 2024-11-06 00:59 UTC (permalink / raw)
To: pgsql-bugs
HashAgg tracks the hash table bucket array (only TupleHashEntryData)
memory differently than the overall hash table (including the
firstTuple) memory.
It can run into a degenerate case when the bucket array grows larger
than the allotted memory for the overall hash table. That, by itself,
shouldn't be a major problem because it would just spill any new groups
and then start over in the next batch.
However, ResetTupleHashTable() calls tuplehash_reset(), and that
preserves the bucket array (just clearing it). That means that the next
time around it's already over the limit, and degenerates to holding a
single tuple.
Unfortunately I don't have a small reproducible case yet. I believe it
would need to be a case where the bucket array is more than half of the
memory limit, and then the hash table needs to grow again (doubling).
The actual case involves parallelism, so maybe that throws off the
estimates in an interesting way.
Fixing it seems fairly easy though: we just need to completely destroy
the hash table each time and recreate it. Something close to the
attached patch (rough).
We might also want to make the degenerate case less painful -- should
we raise the minimum number of groups per batch? One possible problem
would be around groups where the state is large, like ARRAY_AGG(), but
we could have different limits.
Regards,
Jeff Davis
Attachments:
v1-0001-HashAgg-completely-rebuild-hash-tables-each-itera.patch (text/x-patch, 1.3K) download
From 775750fd59ef6f6214d41b187c3f1e7b23961520 Mon Sep 17 00:00:00 2001
From: Jeff Davis <jeff@j-davis.com>
Date: Tue, 5 Nov 2024 16:52:17 -0800
Subject: [PATCH v1] HashAgg: completely rebuild hash tables each iteration.
---
src/backend/executor/nodeAgg.c | 10 ++--------
1 file changed, 2 insertions(+), 8 deletions(-)
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 53ead77ece..9b29d67b7d 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1469,18 +1469,13 @@ build_hash_tables(AggState *aggstate)
{
int setno;
+ MemoryContextReset(aggstate->hash_metacxt);
for (setno = 0; setno < aggstate->num_hashes; ++setno)
{
AggStatePerHash perhash = &aggstate->perhash[setno];
long nbuckets;
Size memory;
- if (perhash->hashtable != NULL)
- {
- ResetTupleHashTable(perhash->hashtable);
- continue;
- }
-
Assert(perhash->aggnode->numGroups > 0);
memory = aggstate->hash_mem_limit / aggstate->num_hashes;
@@ -2622,8 +2617,7 @@ agg_refill_hash_table(AggState *aggstate)
/* free memory and reset hash tables */
ReScanExprContext(aggstate->hashcontext);
- for (int setno = 0; setno < aggstate->num_hashes; setno++)
- ResetTupleHashTable(aggstate->perhash[setno].hashtable);
+ build_hash_tables(aggstate);
aggstate->hash_ngroups_current = 0;
--
2.34.1
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
@ 2024-11-06 02:50 ` David Rowley <dgrowleyml@gmail.com>
2024-11-08 04:26 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
1 sibling, 1 reply; 9+ messages in thread
From: David Rowley @ 2024-11-06 02:50 UTC (permalink / raw)
To: Jeff Davis <pgsql@j-davis.com>; +Cc: pgsql-bugs
On Wed, 6 Nov 2024 at 14:00, Jeff Davis <pgsql@j-davis.com> wrote:
> Fixing it seems fairly easy though: we just need to completely destroy
> the hash table each time and recreate it. Something close to the
> attached patch (rough).
I don't think it could be that exactly though as that could lead to
JIT compilation over and over again from the following chain of
function calls: build_hash_tables() -> build_hash_table() ->
BuildTupleHashTableExt() -> ExecBuildGroupingEqual() ->
ExecReadyExpr() -> jit_compile_expr()
David
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-06 02:50 ` Re: HashAgg degenerate case David Rowley <dgrowleyml@gmail.com>
@ 2024-11-08 04:26 ` Jeff Davis <pgsql@j-davis.com>
0 siblings, 0 replies; 9+ messages in thread
From: Jeff Davis @ 2024-11-08 04:26 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: pgsql-bugs
On Wed, 2024-11-06 at 15:50 +1300, David Rowley wrote:
> I don't think it could be that exactly though as that could lead to
> JIT compilation over and over again from the following chain of
> function calls: build_hash_tables() -> build_hash_table() ->
> BuildTupleHashTableExt() -> ExecBuildGroupingEqual() ->
> ExecReadyExpr() -> jit_compile_expr()
New patch attached. It extends ResetTupleHashTable() so that the caller
can force setting a new nbuckets, which recreates the tuplehash_hash.
agg_refill_hash_table() now uses that to recalculate and set the
nbuckets for the current grouping set's hashtab, and frees the hashtab
for all other grouping sets (it "frees" them by setting to a minimal
size bucket array).
Regards,
Jeff Davis
Attachments:
v2-0001-HashAgg-free-hash-table-memory-each-iteration.patch (text/x-patch, 5.5K) download
From eac1ce2a3b49e0fa54d97695a599c66538407f7a Mon Sep 17 00:00:00 2001
From: Jeff Davis <jeff@j-davis.com>
Date: Thu, 7 Nov 2024 20:15:44 -0800
Subject: [PATCH v2] HashAgg: free hash table memory each iteration.
---
src/backend/executor/execGrouping.c | 22 ++++++++++++++---
src/backend/executor/nodeAgg.c | 30 +++++++++++++++++++++--
src/backend/executor/nodeRecursiveunion.c | 2 +-
src/backend/executor/nodeSetOp.c | 2 +-
src/backend/executor/nodeSubplan.c | 4 +--
src/include/executor/executor.h | 2 +-
6 files changed, 51 insertions(+), 11 deletions(-)
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 774e4de882..dd5c3e852a 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -279,13 +279,27 @@ BuildTupleHashTable(PlanState *parent,
/*
* Reset contents of the hashtable to be empty, preserving all the non-content
- * state. Note that the tablecxt passed to BuildTupleHashTableExt() should
- * also be reset, otherwise there will be leaks.
+ * state. If nbuckets is -1, or if the bucket array is already the right size,
+ * then preserve it; otherwise rebuild it. Note that the tablecxt passed to
+ * BuildTupleHashTableExt() should also be reset, otherwise there will be
+ * leaks.
*/
void
-ResetTupleHashTable(TupleHashTable hashtable)
+ResetTupleHashTable(TupleHashTable hashtable, long nbuckets)
{
- tuplehash_reset(hashtable->hashtab);
+ tuplehash_hash *hashtab = hashtable->hashtab;
+
+ if (nbuckets < 0 || nbuckets == hashtable->hashtab->size)
+ {
+ tuplehash_reset(hashtab);
+ }
+ else
+ {
+ MemoryContext metacxt = hashtab->ctx;
+
+ tuplehash_destroy(hashtab);
+ hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
+ }
}
/*
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 53ead77ece..40900a89bd 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1477,7 +1477,7 @@ build_hash_tables(AggState *aggstate)
if (perhash->hashtable != NULL)
{
- ResetTupleHashTable(perhash->hashtable);
+ ResetTupleHashTable(perhash->hashtable, -1);
continue;
}
@@ -2623,7 +2623,33 @@ agg_refill_hash_table(AggState *aggstate)
/* free memory and reset hash tables */
ReScanExprContext(aggstate->hashcontext);
for (int setno = 0; setno < aggstate->num_hashes; setno++)
- ResetTupleHashTable(aggstate->perhash[setno].hashtable);
+ {
+ TupleHashTable hashtable = aggstate->perhash[setno].hashtable;
+
+ if (setno == batch->setno)
+ {
+ /*
+ * Recalculate nbuckets for this batch. This is important when a
+ * previous iteration caused the number of buckets to grow to an
+ * unexpectedly large value, crowding out space for the tuples.
+ */
+ long nbuckets;
+
+ nbuckets = hash_choose_num_buckets(aggstate->hashentrysize,
+ batch->input_card,
+ aggstate->hash_mem_limit);
+
+ ResetTupleHashTable(hashtable, nbuckets);
+ }
+ else
+ {
+ /*
+ * Free memory but leave metadata intact by setting nbuckets to
+ * minimal value.
+ */
+ ResetTupleHashTable(hashtable, 1);
+ }
+ }
aggstate->hash_ngroups_current = 0;
diff --git a/src/backend/executor/nodeRecursiveunion.c b/src/backend/executor/nodeRecursiveunion.c
index 22e7b83b2e..0a67083079 100644
--- a/src/backend/executor/nodeRecursiveunion.c
+++ b/src/backend/executor/nodeRecursiveunion.c
@@ -328,7 +328,7 @@ ExecReScanRecursiveUnion(RecursiveUnionState *node)
/* Empty hashtable if needed */
if (plan->numCols > 0)
- ResetTupleHashTable(node->hashtable);
+ ResetTupleHashTable(node->hashtable, -1);
/* reset processing state */
node->recursing = false;
diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c
index a8ac68b482..e9a0bdd36d 100644
--- a/src/backend/executor/nodeSetOp.c
+++ b/src/backend/executor/nodeSetOp.c
@@ -636,7 +636,7 @@ ExecReScanSetOp(SetOpState *node)
/* And rebuild empty hashtable if needed */
if (((SetOp *) node->ps.plan)->strategy == SETOP_HASHED)
{
- ResetTupleHashTable(node->hashtable);
+ ResetTupleHashTable(node->hashtable, -1);
node->table_filled = false;
}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 236222d72a..792c3e2494 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -529,7 +529,7 @@ buildSubPlanHash(SubPlanState *node, ExprContext *econtext)
nbuckets = 1;
if (node->hashtable)
- ResetTupleHashTable(node->hashtable);
+ ResetTupleHashTable(node->hashtable, -1);
else
node->hashtable = BuildTupleHashTableExt(node->parent,
node->descRight,
@@ -557,7 +557,7 @@ buildSubPlanHash(SubPlanState *node, ExprContext *econtext)
}
if (node->hashnulls)
- ResetTupleHashTable(node->hashnulls);
+ ResetTupleHashTable(node->hashnulls, -1);
else
node->hashnulls = BuildTupleHashTableExt(node->parent,
node->descRight,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..f210861ec8 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -161,7 +161,7 @@ extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
FmgrInfo *hashfunctions);
-extern void ResetTupleHashTable(TupleHashTable hashtable);
+extern void ResetTupleHashTable(TupleHashTable hashtable, long nbuckets);
/*
* prototypes from functions in execJunk.c
--
2.34.1
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
@ 2024-11-08 16:41 ` Andres Freund <andres@anarazel.de>
2024-11-08 18:48 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
1 sibling, 1 reply; 9+ messages in thread
From: Andres Freund @ 2024-11-08 16:41 UTC (permalink / raw)
To: Jeff Davis <pgsql@j-davis.com>; +Cc: pgsql-bugs
Hi,
On 2024-11-05 16:59:56 -0800, Jeff Davis wrote:
> Fixing it seems fairly easy though: we just need to completely destroy
> the hash table each time and recreate it. Something close to the
> attached patch (rough).
That'll often be *way* slower though. Both because acquiring and faulting-in
memory is far from free and because it'd often lead to starting to grow the
hashtable from a small size again.
I think this patch would lead to way bigger regressions than the occasionally
too large hashtable does. I'm not saying that we shouldn't do something about
that, but I don't think it can be this.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 16:41 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
@ 2024-11-08 18:48 ` Jeff Davis <pgsql@j-davis.com>
2024-11-08 20:40 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
0 siblings, 1 reply; 9+ messages in thread
From: Jeff Davis @ 2024-11-08 18:48 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: pgsql-bugs
On Fri, 2024-11-08 at 11:41 -0500, Andres Freund wrote:
> That'll often be *way* slower though. Both because acquiring and
> faulting-in
> memory is far from free and because it'd often lead to starting to
> grow the
> hashtable from a small size again.
I assume this statement also applies to my more recent message?
https://www.postgresql.org/message-id/4e9bfa724b301b55a2a242ebebcddea62b2e1292.camel%40j-davis.com
> I think this patch would lead to way bigger regressions than the
> occasionally
> too large hashtable does. I'm not saying that we shouldn't do
> something about
> that, but I don't think it can be this.
The case I observed had a bucket array of ~8M, which took about 200MB,
while the hash_mem_limit was only 128MB. I'm not quite sure how it got
into that state (probably related to the doubling behavior of the
bucket array), but once it did, it was incredibly slow because the
first tuple always triggered spilling to disk.
I can think of two approaches to solve it:
1. Detect the case when there is an obvious imbalance, like the metacxt
using 90+% of the memory limit before a batch even begins, and then
destroy/recreate the hash table.
2. Change the rules in hash_agg_check_limits() so that reasonable
progress can be made regardless of the size of metacxt. For instance,
don't count meta_mem as taking more than 75% of the limit. Or always
permit a new group if there are fewer than 25% of the
hash_ngroups_limit.
Thoughts?
Regards,
Jeff Davis
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 16:41 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
2024-11-08 18:48 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
@ 2024-11-08 20:40 ` Jeff Davis <pgsql@j-davis.com>
2024-11-12 15:48 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
0 siblings, 1 reply; 9+ messages in thread
From: Jeff Davis @ 2024-11-08 20:40 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: pgsql-bugs
On Fri, 2024-11-08 at 10:48 -0800, Jeff Davis wrote:
> I can think of two approaches to solve it:
Another thought: the point of spilling is to avoid using additional
memory by adding a group.
If the bucket array is 89.8% full, adding a new group doesn't require
new buckets need to be allocated, so we only have the firstTuple and
pergroup data to worry about. If that causes the memory limit to be
exceeded, it's the perfect time to switch to spill mode.
But if the bucket array is 89.9% full, then adding a new group will
cause the bucket array to double. If that causes the memory limit to be
exceeded, then we can switch to spill mode, but it's wasteful to do so
because (a) we won't be using most of those new buckets; (b) the new
buckets will crowd out space for subsequent batches and even fewer of
the buckets will be used; and (c) the memory accounting can be off by
quite a bit.
What if we have a check where, if the metacxt is using more than 40% of
the memory, and if adding a new group would reach the grow_threshold,
then enter spill mode immediately? To make this work, I think we either
need to use a tuplehash_lookup() followed by a tuplehash_insert() (two
lookups for each new group), or we would need a new API into simplehash
like tuplehash_insert_without_growing() that would return NULL instead
of growing. This approach might not be backportable, but it might be a
good approach for 18+.
Regards,
Jeff Davis
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 16:41 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
2024-11-08 18:48 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 20:40 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
@ 2024-11-12 15:48 ` Andres Freund <andres@anarazel.de>
2024-11-12 23:15 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
0 siblings, 1 reply; 9+ messages in thread
From: Andres Freund @ 2024-11-12 15:48 UTC (permalink / raw)
To: Jeff Davis <pgsql@j-davis.com>; +Cc: pgsql-bugs
Hi,
On 2024-11-08 12:40:39 -0800, Jeff Davis wrote:
> On Fri, 2024-11-08 at 10:48 -0800, Jeff Davis wrote:
> > I can think of two approaches to solve it:
>
> Another thought: the point of spilling is to avoid using additional
> memory by adding a group.
>
> If the bucket array is 89.8% full, adding a new group doesn't require
> new buckets need to be allocated, so we only have the firstTuple and
> pergroup data to worry about. If that causes the memory limit to be
> exceeded, it's the perfect time to switch to spill mode.
> But if the bucket array is 89.9% full, then adding a new group will
> cause the bucket array to double. If that causes the memory limit to be
> exceeded, then we can switch to spill mode, but it's wasteful to do so
> because (a) we won't be using most of those new buckets; (b) the new
> buckets will crowd out space for subsequent batches and even fewer of
> the buckets will be used; and (c) the memory accounting can be off by
> quite a bit.
> What if we have a check where, if the metacxt is using more than 40% of
> the memory, and if adding a new group would reach the grow_threshold,
> then enter spill mode immediately?
That assumes the bucket array is a significant portion of the memory usage -
but that's not a given, right? We also might need to grow to keep the number
of conflict chains at a manageable level.
> To make this work, I think we either need to use a tuplehash_lookup()
> followed by a tuplehash_insert() (two lookups for each new group), or we
> would need a new API into simplehash like tuplehash_insert_without_growing()
> that would return NULL instead of growing.
The former seems entirely non-viable on performance grounds. The latter might
be ok, but I'm vary on code complexity grounds.
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?
> This approach might not be backportable, but it might be a good approach for
> 18+.
I doubt any change around this ought to be backpatched. The likelihood of
regressions seems to high.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 16:41 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
2024-11-08 18:48 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 20:40 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-12 15:48 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
@ 2024-11-12 23:15 ` Jeff Davis <pgsql@j-davis.com>
2024-11-13 07:18 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
0 siblings, 1 reply; 9+ messages in thread
From: Jeff Davis @ 2024-11-12 23:15 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: pgsql-bugs
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.h
index 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.c
index 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.c
index 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.h
index 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.h
index 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
* Re: HashAgg degenerate case
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 16:41 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
2024-11-08 18:48 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-08 20:40 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-12 15:48 ` Re: HashAgg degenerate case Andres Freund <andres@anarazel.de>
2024-11-12 23:15 ` Re: HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
@ 2024-11-13 07:18 ` Jeff Davis <pgsql@j-davis.com>
0 siblings, 0 replies; 9+ messages in thread
From: Jeff Davis @ 2024-11-13 07:18 UTC (permalink / raw)
To: Andres Freund <andres@anarazel.de>; +Cc: pgsql-bugs
On Tue, 2024-11-12 at 15:15 -0800, Jeff Davis wrote:
> 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).
Previous version was incorrect, v2 attached, which is still rough, but
hopefully better.
Regards,
Jeff Davis
Attachments: download all (2 files, .tar.gz)
v2-0001-simplehash-add-grow_ok-to-API.patch (text/x-patch, 4.5K) download
From c1c4f563f3f3b954f27d8576f0f34fef78c095e9 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 v2 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 | 40 ++++++++++++++++++++++++++++++------
1 file changed, 34 insertions(+), 6 deletions(-)
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index 3e1b1f9461..9c49410cef 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;
@@ -624,7 +633,7 @@ restart:
* Note that this also reached when resizing the table due to
* SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE.
*/
- if (unlikely(tb->members >= tb->grow_threshold))
+ if (unlikely(grow_ok && tb->members >= tb->grow_threshold))
{
if (unlikely(tb->size == SH_MAX_SIZE))
sh_error("hash table size exceeded");
@@ -651,6 +660,9 @@ restart:
/* any empty bucket can directly be used */
if (entry->status == SH_STATUS_EMPTY)
{
+ if (unlikely(!grow_ok && tb->members >= tb->grow_threshold))
+ return NULL;
+
tb->members++;
entry->SH_KEY = key;
#ifdef SH_STORE_HASH
@@ -687,6 +699,9 @@ restart:
uint32 moveelem;
int32 emptydist = 0;
+ if (unlikely(!grow_ok && tb->members >= tb->grow_threshold))
+ return NULL;
+
/* find next empty bucket */
while (true)
{
@@ -778,7 +793,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 +804,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 +1230,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
v2-0002-HashAgg-avoid-unexpected-hash-table-growth-near-m.patch (text/x-patch, 11.9K) download
From 40ee623627e49068ce8b3a7da8df31e17d0bb0d6 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 v2 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.c
index 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.c
index 53ead77ece..9991c01e43 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,
+ aggstate->hash_grow_ok, 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.h
index 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.h
index 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
end of thread, other threads:[~2024-11-13 07:18 UTC | newest]
Thread overview: 9+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2024-11-06 00:59 HashAgg degenerate case Jeff Davis <pgsql@j-davis.com>
2024-11-06 02:50 ` David Rowley <dgrowleyml@gmail.com>
2024-11-08 04:26 ` Jeff Davis <pgsql@j-davis.com>
2024-11-08 16:41 ` Andres Freund <andres@anarazel.de>
2024-11-08 18:48 ` Jeff Davis <pgsql@j-davis.com>
2024-11-08 20:40 ` Jeff Davis <pgsql@j-davis.com>
2024-11-12 15:48 ` Andres Freund <andres@anarazel.de>
2024-11-12 23:15 ` Jeff Davis <pgsql@j-davis.com>
2024-11-13 07:18 ` Jeff Davis <pgsql@j-davis.com>
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