Fix overflow of nbatch

From 2805b09ebb5e71908ca34e4c355f1eaccab97ef4 Mon Sep 17 00:00:00 2001
From: Vaibhav Jain <jainva@google.com>
Date: Mon, 22 Sep 2025 18:11:08 +0530
Subject: Fix overflow of nbatch

With a1b4f28, to compute current_space, nbatch is being multiplied
by BLCKSZ. nbatch is int and when multiplied with BLCKSZ, it can
easily overflow the int limit. To keep the calculation safe for
current_space, convert nbatch to size_t.

---
 src/backend/executor/nodeHash.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index a3415db4e20..4e0e18314d1 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -912,10 +912,10 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	while (nbatch > 0)
 	{
 		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
+		size_t		current_space = hash_table_bytes + (2 * (size_t) nbatch * BLCKSZ);
 
 		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		size_t		new_space = hash_table_bytes * 2 + ((size_t) nbatch * BLCKSZ);
 
 		/* If the memory usage would not decrease, we found the optimum. */
 		if (current_space < new_space)
@@ -994,7 +994,7 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = ((size_t) hashtable->nbatch * 2 * BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the

From d1f0bdc6c4a666fa9e7d4bb1836d656bfec6b4a3 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@vondra.me>
Date: Wed, 24 Sep 2025 22:03:30 +0200
Subject: [PATCH vfix 4/4] reword balancing comment

---
 src/backend/executor/nodeHash.c | 64 +++++++++++----------------------
 1 file changed, 21 insertions(+), 43 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index b2be2091fb2..145c19db8f8 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -851,59 +851,37 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	/*
 	 * Optimize the total amount of memory consumed by the hash node.
 	 *
-	 * The nbatch calculation above focuses on the size of the in-memory hash
-	 * table, assuming no per-batch overhead. Now adjust the number of batches
-	 * and the size of the hash table to minimize total memory consumed by the
-	 * hash node.
-	 *
-	 * Each batch file has a BLCKSZ buffer, and we may need two files per
-	 * batch (inner and outer side). So with enough batches this can be
-	 * significantly more memory than the hashtable itself.
+	 * The nbatch calculation above focuses on the the in-memory hash table,
+	 * assuming no per-batch overhead. But each batch may have two files, each
+	 * with a BLCKSZ buffer. With enough batches these buffers may use
+	 * significantly more memory than the hash table.
 	 *
 	 * The total memory usage may be expressed by this formula:
 	 *
-	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ) <= hash_table_bytes
+	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
 	 *
 	 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
 	 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
-	 * buffers. But for sufficiently large values of inner_rel_bytes value
-	 * there may not be a nbatch value that would make both parts fit into
-	 * hash_table_bytes.
-	 *
-	 * In this case we can't enforce the memory limit - we're going to exceed
-	 * it. We can however minimize the impact and use as little memory as
-	 * possible. (We haven't really enforced it before either, as we simply
-	 * ignored the batch files.)
+	 * buffers. We can't optimize both parts at the same time, and for large
+	 * inner_rel_bytes values there may not be a nbatch value that would keep
+	 * memory usage below the memory limit (work_mem * hash_mem_multiplier).
 	 *
-	 * The formula for total memory usage says that given an inner relation of
-	 * size inner_rel_bytes, we may divide it into an arbitrary number of
-	 * batches. This determines both the size of the in-memory hash table and
-	 * the amount of memory needed for batch files. These two terms work in
-	 * opposite ways - when one decreases, the other increases.
+	 * In this case we're going to exceed the memory limit no matter what. We
+	 * can at least minimize the impact and minimize the amount of memory
+	 * used. (We haven't enforced it before either, we simply ignored the
+	 * batch files.)
 	 *
-	 * For low nbatch values, the hash table takes most of the memory, but at
-	 * some point the batch files start to dominate. If you combine these two
-	 * terms, the memory consumption (for a fixed size of the inner relation)
-	 * has a u-shape, with a minimum at some nbatch value.
-	 *
-	 * Our goal is to find this nbatch value, minimizing the memory usage. We
-	 * calculate the memory usage with half the batches (i.e. nbatch/2), and
-	 * if it's lower than the current memory usage we know it's better to use
-	 * fewer batches. We repeat this until reducing the number of batches does
-	 * not reduce the memory usage - we found the optimum. We know the optimum
-	 * exists, thanks to the u-shape.
+	 * These two terms in the formula work in opposite ways - one decreases,
+	 * the other increases. The plot has a u-shape, with a minimum at some
+	 * nbatch value. We find the minimum by "walking back" - check if using
+	 * (nbatch/2) batches would lower the memory usage. We stop when the
+	 * memory usage would not improve.
 	 *
 	 * We only want to do this when exceeding the memory limit, not every
-	 * time. The goal is not to minimize memory usage in every case, but to
-	 * minimize the memory usage when we can't stay within the memory limit.
-	 *
-	 * For this reason we only consider reducing the number of batches. We
-	 * could try the opposite direction too, but that would save memory only
-	 * when most of the memory is used by the hash table. And the hash table
-	 * was used for the initial sizing, so we shouldn't be exceeding the
-	 * memory limit too much. We might save memory by using more batches, but
-	 * it would result in spilling more batch files, which does not seem like
-	 * a great trade off.
+	 * time. This is why we try only reducing number of batches. We could try
+	 * increasing nbatch too, but what would lower memory usage only with most
+	 * of the memory being used by the hash table. It might even force using
+	 * batching even when not needed. We don't want that.
 	 *
 	 * While growing the hashtable, we also adjust the number of buckets, to
 	 * not have more than one tuple per bucket (load factor 1). We can only do
-- 
2.51.0

From 7f6d163d99651406d36bef712f6fc87f1e3e801c Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@vondra.me>
Date: Wed, 24 Sep 2025 14:56:14 +0200
Subject: [PATCH vfix 3/4] nbuckets overflow protection

---
 src/backend/executor/nodeHash.c | 44 ++++++++++++++++++++++++++++++---
 1 file changed, 40 insertions(+), 4 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 972b5b58583..b2be2091fb2 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -925,14 +925,50 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 			break;
 
 		/*
-		 * It's better to use half the batches, so do that and adjust the
-		 * nbucket in the opposite direction, and double the allowance.
+		 * Make sure hash_table_bytes doesn't overflow. If it would, stop and
+		 * use the current nbatch value.
+		 */
+		if (hash_table_bytes > SIZE_MAX / 2)
+			break;
+
+		/*
+		 * It's better to use half the batches, so do that, and adjust the
+		 * allowance in the opposite direction. Then adjust the nbuckets to
+		 * reflect the higher allowance, but be careful about overflow.
 		 */
 		nbatch /= 2;
-		nbuckets *= 2;
 		hash_table_bytes *= 2;
-
 		*space_allowed = (*space_allowed) * 2;
+
+		/*
+		 * Adjust nbuckets, with overflow protection.
+		 *
+		 * Recalculate max_pointers, because the earlier value was based on a
+		 * lower hash_table_bytes, before we adjusted that.
+		 *
+		 * XXX Maybe this is too much, and we need to care only about
+		 * MaxAllocSize? Then we'd not need to recalculate this over and over
+		 * in every loop.
+		 *
+		 * XXX An alternative would be to not grow nbuckets, and stick to the
+		 * originally planned value. The cost is we'll increase the load
+		 * factor (tuples per bucket).
+		 */
+		max_pointers = hash_table_bytes / sizeof(HashJoinTuple);
+		max_pointers = Min(max_pointers, MaxAllocSize / sizeof(HashJoinTuple));
+		/* If max_pointers isn't a power of 2, must round it down to one */
+		max_pointers = pg_prevpower2_size_t(max_pointers);
+
+		/* Also ensure we avoid integer overflow in nbatch and nbuckets */
+		/* (this step is redundant given the current value of MaxAllocSize) */
+		max_pointers = Min(max_pointers, INT_MAX / 2 + 1);
+
+		/* don't break, just cap the number of buckets */
+		dbuckets = (double) nbuckets * 2;
+		dbuckets = Min(dbuckets, max_pointers);
+
+		nbuckets = (int) dbuckets;
+		nbuckets = pg_nextpower2_32(nbuckets);
 	}
 
 	Assert(nbuckets > 0);
-- 
2.51.0

From a7995c8e6a149e3444e7e48b618a117cda588770 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@vondra.me>
Date: Wed, 24 Sep 2025 14:32:29 +0200
Subject: [PATCH vfix 2/4] adjust hash_table_bytes for balancing

---
 src/backend/executor/nodeHash.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index ef589b90339..972b5b58583 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -930,6 +930,7 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 		 */
 		nbatch /= 2;
 		nbuckets *= 2;
+		hash_table_bytes *= 2;
 
 		*space_allowed = (*space_allowed) * 2;
 	}
-- 
2.51.0

From 4f128c5cbdb11c4d9b1882d39b75338c854ba30e Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@vondra.me>
Date: Wed, 24 Sep 2025 14:30:31 +0200
Subject: [PATCH vfix 1/4] fix size overflow

---
 src/backend/executor/nodeHash.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 8d2201ab67f..ef589b90339 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -913,10 +913,12 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	while (nbatch > 0)
 	{
 		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
+		size_t		current_space =
+			hash_table_bytes + (2 * nbatch * (size_t) BLCKSZ);
 
 		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		size_t		new_space =
+			hash_table_bytes * 2 + (nbatch * (size_t) BLCKSZ);
 
 		/* If the memory usage would not decrease, we found the optimum. */
 		if (current_space < new_space)
@@ -995,7 +997,7 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the
-- 
2.51.0

From 477fad740ca9abcfcb57440f3f9d0d5474d61601 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 7 Oct 2025 13:21:14 -0400
Subject: [PATCH v1] Fix overflow risk in hashtable size calculation

---
 src/backend/executor/nodeHash.c | 108 ++++++++++++++------------------
 1 file changed, 47 insertions(+), 61 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index a3415db4e20..70723aeb558 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -850,92 +850,78 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	/*
 	 * Optimize the total amount of memory consumed by the hash node.
 	 *
-	 * The nbatch calculation above focuses on the size of the in-memory hash
-	 * table, assuming no per-batch overhead. Now adjust the number of batches
-	 * and the size of the hash table to minimize total memory consumed by the
-	 * hash node.
-	 *
-	 * Each batch file has a BLCKSZ buffer, and we may need two files per
-	 * batch (inner and outer side). So with enough batches this can be
-	 * significantly more memory than the hashtable itself.
+	 * The nbatch calculation above focuses on the the in-memory hash table,
+	 * assuming no per-batch overhead. But each batch may have two files, each
+	 * with a BLCKSZ buffer. With enough batches these buffers may use
+	 * significantly more memory than the hash table.
 	 *
 	 * The total memory usage may be expressed by this formula:
 	 *
-	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ) <= hash_table_bytes
+	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
 	 *
 	 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
 	 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
-	 * buffers. But for sufficiently large values of inner_rel_bytes value
-	 * there may not be a nbatch value that would make both parts fit into
-	 * hash_table_bytes.
-	 *
-	 * In this case we can't enforce the memory limit - we're going to exceed
-	 * it. We can however minimize the impact and use as little memory as
-	 * possible. (We haven't really enforced it before either, as we simply
-	 * ignored the batch files.)
+	 * buffers.
 	 *
-	 * The formula for total memory usage says that given an inner relation of
-	 * size inner_rel_bytes, we may divide it into an arbitrary number of
-	 * batches. This determines both the size of the in-memory hash table and
-	 * the amount of memory needed for batch files. These two terms work in
-	 * opposite ways - when one decreases, the other increases.
+	 * For very large inner_rel_bytes, there may be no nbatch that keeps total
+	 * memory usage under the budget (work_mem * hash_mem_multiplier). In that
+	 * case, we choose nbatch to minimize total memory consumption across both
+	 * the hashtable and file buffers.
 	 *
-	 * For low nbatch values, the hash table takes most of the memory, but at
-	 * some point the batch files start to dominate. If you combine these two
-	 * terms, the memory consumption (for a fixed size of the inner relation)
-	 * has a u-shape, with a minimum at some nbatch value.
+	 * As we increase the size of the hashtable and decrease the number of
+	 * batches, the total memory usage follows a U-shaped curve. We find the
+	 * minimum nbatch by "walking back" -- checking if halving nbatch would
+	 * lower total memory usage. We stop when it no longer helps.
 	 *
-	 * Our goal is to find this nbatch value, minimizing the memory usage. We
-	 * calculate the memory usage with half the batches (i.e. nbatch/2), and
-	 * if it's lower than the current memory usage we know it's better to use
-	 * fewer batches. We repeat this until reducing the number of batches does
-	 * not reduce the memory usage - we found the optimum. We know the optimum
-	 * exists, thanks to the u-shape.
+	 * We only want to do this when we are already over the memory budget. We
+	 * don't explore increasing nbatch since that could force batching when it
+	 * is not needed.
 	 *
-	 * We only want to do this when exceeding the memory limit, not every
-	 * time. The goal is not to minimize memory usage in every case, but to
-	 * minimize the memory usage when we can't stay within the memory limit.
+	 * While growing the hashtable, we also adjust the number of buckets to
+	 * maintain a load factor of NTUP_PER_BUCKET while squeezing tuples back
+	 * from batches into the hashtable.
 	 *
-	 * For this reason we only consider reducing the number of batches. We
-	 * could try the opposite direction too, but that would save memory only
-	 * when most of the memory is used by the hash table. And the hash table
-	 * was used for the initial sizing, so we shouldn't be exceeding the
-	 * memory limit too much. We might save memory by using more batches, but
-	 * it would result in spilling more batch files, which does not seem like
-	 * a great trade off.
-	 *
-	 * While growing the hashtable, we also adjust the number of buckets, to
-	 * not have more than one tuple per bucket (load factor 1). We can only do
-	 * this during the initial sizing - once we start building the hash,
-	 * nbucket is fixed.
+	 * Note that we can only change nbuckets during initial hashtable sizing.
+	 * Once we start building the hash, nbuckets is fixed.
 	 */
-	while (nbatch > 0)
+	while (nbatch > 1)
 	{
-		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
-
-		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		/* Ensure that nbuckets * 2 doesn't overflow an int */
+		if (nbuckets > INT_MAX / 2)
+			break;
 
-		/* If the memory usage would not decrease, we found the optimum. */
-		if (current_space < new_space)
+		/*
+		 * Ensure that hash_table_bytes * 2 doesn't exceed MaxAllocSize /
+		 * sizeof(HashJoinTuple)
+		 */
+		if (hash_table_bytes > MaxAllocSize / sizeof(HashJoinTuple) / 2)
 			break;
 
 		/*
-		 * It's better to use half the batches, so do that and adjust the
-		 * nbucket in the opposite direction, and double the allowance.
+		 * This is the same as:
+		 *
+		 * hash_table_bytes + 2 * nbatch * BLCKSZ < hash_table_bytes * 2 +
+		 * nbatch * BLCKSZ
+		 *
+		 * avoiding intermediate overflow.
+		 *
+		 * which is to say: will halving the number of batches and doubling
+		 * the size of the hashtable reduce overall memory usage?
 		 */
-		nbatch /= 2;
+		if (nbatch / 4 < hash_table_bytes / BLCKSZ)
+			break;
+
 		nbuckets *= 2;
+		hash_table_bytes *= 2;
 
-		*space_allowed = (*space_allowed) * 2;
+		nbatch /= 2;
 	}
 
 	Assert(nbuckets > 0);
 	Assert(nbatch > 0);
-
 	*numbuckets = nbuckets;
 	*numbatches = nbatch;
+	*space_allowed = hash_table_bytes;
 }
 
 
@@ -994,7 +980,7 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the
-- 
2.43.0

From 716b7c939019294c2e006e55da44180f61072fe2 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 7 Oct 2025 13:21:14 -0400
Subject: [PATCH v2] Fix overflow risk in hashtable size calculation

ci-os-only:
---
 src/backend/executor/nodeHash.c | 115 +++++++++++++++-----------------
 1 file changed, 55 insertions(+), 60 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index a3415db4e20..e8be61e40ed 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -850,90 +850,85 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	/*
 	 * Optimize the total amount of memory consumed by the hash node.
 	 *
-	 * The nbatch calculation above focuses on the size of the in-memory hash
-	 * table, assuming no per-batch overhead. Now adjust the number of batches
-	 * and the size of the hash table to minimize total memory consumed by the
-	 * hash node.
-	 *
-	 * Each batch file has a BLCKSZ buffer, and we may need two files per
-	 * batch (inner and outer side). So with enough batches this can be
-	 * significantly more memory than the hashtable itself.
+	 * The nbatch calculation above focuses on the the in-memory hash table,
+	 * assuming no per-batch overhead. But each batch may have two files, each
+	 * with a BLCKSZ buffer. With enough batches these buffers may use
+	 * significantly more memory than the hash table.
 	 *
 	 * The total memory usage may be expressed by this formula:
 	 *
-	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ) <= hash_table_bytes
+	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
 	 *
 	 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
 	 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
-	 * buffers. But for sufficiently large values of inner_rel_bytes value
-	 * there may not be a nbatch value that would make both parts fit into
-	 * hash_table_bytes.
-	 *
-	 * In this case we can't enforce the memory limit - we're going to exceed
-	 * it. We can however minimize the impact and use as little memory as
-	 * possible. (We haven't really enforced it before either, as we simply
-	 * ignored the batch files.)
-	 *
-	 * The formula for total memory usage says that given an inner relation of
-	 * size inner_rel_bytes, we may divide it into an arbitrary number of
-	 * batches. This determines both the size of the in-memory hash table and
-	 * the amount of memory needed for batch files. These two terms work in
-	 * opposite ways - when one decreases, the other increases.
+	 * buffers.
 	 *
-	 * For low nbatch values, the hash table takes most of the memory, but at
-	 * some point the batch files start to dominate. If you combine these two
-	 * terms, the memory consumption (for a fixed size of the inner relation)
-	 * has a u-shape, with a minimum at some nbatch value.
+	 * For very large inner_rel_bytes, there may be no nbatch that keeps total
+	 * memory usage under the budget (work_mem * hash_mem_multiplier). In that
+	 * case, we choose nbatch to minimize total memory consumption across both
+	 * the hashtable and file buffers.
 	 *
-	 * Our goal is to find this nbatch value, minimizing the memory usage. We
-	 * calculate the memory usage with half the batches (i.e. nbatch/2), and
-	 * if it's lower than the current memory usage we know it's better to use
-	 * fewer batches. We repeat this until reducing the number of batches does
-	 * not reduce the memory usage - we found the optimum. We know the optimum
-	 * exists, thanks to the u-shape.
+	 * As we increase the size of the hashtable and decrease the number of
+	 * batches, the total memory usage follows a U-shaped curve. We find the
+	 * minimum nbatch by "walking back" -- checking if halving nbatch would
+	 * lower total memory usage. We stop when it no longer helps.
 	 *
-	 * We only want to do this when exceeding the memory limit, not every
-	 * time. The goal is not to minimize memory usage in every case, but to
-	 * minimize the memory usage when we can't stay within the memory limit.
+	 * We only want to do this when we are already over the memory budget. We
+	 * don't explore increasing nbatch since that could force batching when it
+	 * is not needed.
 	 *
-	 * For this reason we only consider reducing the number of batches. We
-	 * could try the opposite direction too, but that would save memory only
-	 * when most of the memory is used by the hash table. And the hash table
-	 * was used for the initial sizing, so we shouldn't be exceeding the
-	 * memory limit too much. We might save memory by using more batches, but
-	 * it would result in spilling more batch files, which does not seem like
-	 * a great trade off.
+	 * While growing the hashtable, we also adjust the number of buckets to
+	 * maintain a load factor of NTUP_PER_BUCKET while squeezing tuples back
+	 * from batches into the hashtable.
 	 *
-	 * While growing the hashtable, we also adjust the number of buckets, to
-	 * not have more than one tuple per bucket (load factor 1). We can only do
-	 * this during the initial sizing - once we start building the hash,
-	 * nbucket is fixed.
+	 * Note that we can only change nbuckets during initial hashtable sizing.
+	 * Once we start building the hash, nbuckets is fixed.
 	 */
-	while (nbatch > 0)
+	while (nbatch > 1)
 	{
-		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
+		/*
+		 * Ensure that nbuckets can be allocated. nbuckets may have been
+		 * increased above hash_table_size / sizeof(HashJoinTuple) if work_mem
+		 * was very small, so checking if MaxAllocSize is enough for the
+		 * buckets is the safest check.
+		 */
+		if (nbuckets > MaxAllocSize / sizeof(HashJoinTuple) / 2)
+			break;
 
-		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		/*
+		 * We shouldn't overflow a size_t if we break before hash_table_bytes
+		 * would exceed MaxAllocSize. We use space_allowed because it will be
+		 * larger than hash_table_bytes when there is a skew hashtable.
+		 */
+		Assert((*space_allowed) < SIZE_MAX / 2);
 
-		/* If the memory usage would not decrease, we found the optimum. */
-		if (current_space < new_space)
+		/*
+		 * This is the same as:
+		 *
+		 * hash_table_bytes + 2 * nbatch * BLCKSZ < hash_table_bytes * 2 +
+		 * nbatch * BLCKSZ
+		 *
+		 * avoiding intermediate overflow.
+		 *
+		 * which is to say: will halving the number of batches and doubling
+		 * the size of the hashtable reduce overall memory usage?
+		 */
+		if (nbatch < hash_table_bytes / BLCKSZ)
 			break;
 
 		/*
-		 * It's better to use half the batches, so do that and adjust the
-		 * nbucket in the opposite direction, and double the allowance.
+		 * MaxAllocSize is sufficiently small that we are not worried about
+		 * overflowing nbuckets.
 		 */
-		nbatch /= 2;
 		nbuckets *= 2;
-
+		hash_table_bytes *= 2;
 		*space_allowed = (*space_allowed) * 2;
+
+		nbatch /= 2;
 	}
 
 	Assert(nbuckets > 0);
 	Assert(nbatch > 0);
-
 	*numbuckets = nbuckets;
 	*numbatches = nbatch;
 }
@@ -994,7 +989,7 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the
-- 
2.43.0

From 91cd15ac95e7a5943213bf6d88c08f36b4c0c17b Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 7 Oct 2025 13:21:14 -0400
Subject: [PATCH v3] Fix overflow risk in hashtable size calculation

ci-os-only:
---
 src/backend/executor/nodeHash.c | 115 +++++++++++++++-----------------
 1 file changed, 55 insertions(+), 60 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index a3415db4e20..0f815674c9f 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -850,90 +850,85 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	/*
 	 * Optimize the total amount of memory consumed by the hash node.
 	 *
-	 * The nbatch calculation above focuses on the size of the in-memory hash
-	 * table, assuming no per-batch overhead. Now adjust the number of batches
-	 * and the size of the hash table to minimize total memory consumed by the
-	 * hash node.
-	 *
-	 * Each batch file has a BLCKSZ buffer, and we may need two files per
-	 * batch (inner and outer side). So with enough batches this can be
-	 * significantly more memory than the hashtable itself.
+	 * The nbatch calculation above focuses on the the in-memory hash table,
+	 * assuming no per-batch overhead. But each batch may have two files, each
+	 * with a BLCKSZ buffer. With enough batches these buffers may use
+	 * significantly more memory than the hash table.
 	 *
 	 * The total memory usage may be expressed by this formula:
 	 *
-	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ) <= hash_table_bytes
+	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
 	 *
 	 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
 	 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
-	 * buffers. But for sufficiently large values of inner_rel_bytes value
-	 * there may not be a nbatch value that would make both parts fit into
-	 * hash_table_bytes.
-	 *
-	 * In this case we can't enforce the memory limit - we're going to exceed
-	 * it. We can however minimize the impact and use as little memory as
-	 * possible. (We haven't really enforced it before either, as we simply
-	 * ignored the batch files.)
-	 *
-	 * The formula for total memory usage says that given an inner relation of
-	 * size inner_rel_bytes, we may divide it into an arbitrary number of
-	 * batches. This determines both the size of the in-memory hash table and
-	 * the amount of memory needed for batch files. These two terms work in
-	 * opposite ways - when one decreases, the other increases.
+	 * buffers.
 	 *
-	 * For low nbatch values, the hash table takes most of the memory, but at
-	 * some point the batch files start to dominate. If you combine these two
-	 * terms, the memory consumption (for a fixed size of the inner relation)
-	 * has a u-shape, with a minimum at some nbatch value.
+	 * For very large inner_rel_bytes, there may be no nbatch that keeps total
+	 * memory usage under the budget (work_mem * hash_mem_multiplier). In that
+	 * case, we choose nbatch to minimize total memory consumption across both
+	 * the hashtable and file buffers.
 	 *
-	 * Our goal is to find this nbatch value, minimizing the memory usage. We
-	 * calculate the memory usage with half the batches (i.e. nbatch/2), and
-	 * if it's lower than the current memory usage we know it's better to use
-	 * fewer batches. We repeat this until reducing the number of batches does
-	 * not reduce the memory usage - we found the optimum. We know the optimum
-	 * exists, thanks to the u-shape.
+	 * As we increase the size of the hashtable and decrease the number of
+	 * batches, the total memory usage follows a U-shaped curve. We find the
+	 * minimum nbatch by "walking back" -- checking if halving nbatch would
+	 * lower total memory usage. We stop when it no longer helps.
 	 *
-	 * We only want to do this when exceeding the memory limit, not every
-	 * time. The goal is not to minimize memory usage in every case, but to
-	 * minimize the memory usage when we can't stay within the memory limit.
+	 * We only want to do this when we are already over the memory budget. We
+	 * don't explore increasing nbatch since that could force batching when it
+	 * is not needed.
 	 *
-	 * For this reason we only consider reducing the number of batches. We
-	 * could try the opposite direction too, but that would save memory only
-	 * when most of the memory is used by the hash table. And the hash table
-	 * was used for the initial sizing, so we shouldn't be exceeding the
-	 * memory limit too much. We might save memory by using more batches, but
-	 * it would result in spilling more batch files, which does not seem like
-	 * a great trade off.
+	 * While growing the hashtable, we also adjust the number of buckets to
+	 * maintain a load factor of NTUP_PER_BUCKET while squeezing tuples back
+	 * from batches into the hashtable.
 	 *
-	 * While growing the hashtable, we also adjust the number of buckets, to
-	 * not have more than one tuple per bucket (load factor 1). We can only do
-	 * this during the initial sizing - once we start building the hash,
-	 * nbucket is fixed.
+	 * Note that we can only change nbuckets during initial hashtable sizing.
+	 * Once we start building the hash, nbuckets is fixed.
 	 */
-	while (nbatch > 0)
+	while (nbatch > 1)
 	{
-		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
+		/*
+		 * Ensure that nbuckets can be allocated. nbuckets may have been
+		 * increased above hash_table_size / sizeof(HashJoinTuple) if work_mem
+		 * was very small, so checking if MaxAllocSize is enough for the
+		 * buckets is the safest check.
+		 */
+		if (nbuckets > MaxAllocSize / sizeof(HashJoinTuple) / 2)
+			break;
 
-		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		/*
+		 * We check that space_allowed wouldn't overflow because it will be
+		 * larger than hash_table_bytes if there is a skew hashtable.
+		 */
+		if ((*space_allowed) > SIZE_MAX / 2)
+			break;
 
-		/* If the memory usage would not decrease, we found the optimum. */
-		if (current_space < new_space)
+		/*
+		 * This is the same as:
+		 *
+		 * hash_table_bytes + 2 * nbatch * BLCKSZ < hash_table_bytes * 2 +
+		 * nbatch * BLCKSZ
+		 *
+		 * avoiding intermediate overflow.
+		 *
+		 * which is to say: will halving the number of batches and doubling
+		 * the size of the hashtable reduce overall memory usage?
+		 */
+		if (nbatch < hash_table_bytes / BLCKSZ)
 			break;
 
 		/*
-		 * It's better to use half the batches, so do that and adjust the
-		 * nbucket in the opposite direction, and double the allowance.
+		 * MaxAllocSize is sufficiently small that we are not worried about
+		 * overflowing nbuckets.
 		 */
-		nbatch /= 2;
 		nbuckets *= 2;
-
+		hash_table_bytes *= 2;
 		*space_allowed = (*space_allowed) * 2;
+
+		nbatch /= 2;
 	}
 
 	Assert(nbuckets > 0);
 	Assert(nbatch > 0);
-
 	*numbuckets = nbuckets;
 	*numbatches = nbatch;
 }
@@ -994,7 +989,7 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the
-- 
2.43.0

From d3c67d91f68cadec7c395da933d6e56ba600b94d Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@vondra.me>
Date: Fri, 10 Oct 2025 00:38:05 +0200
Subject: [PATCH v4 2/2] adjustments

---
 src/backend/executor/nodeHash.c | 43 ++++++++++++++++++++++-----------
 1 file changed, 29 insertions(+), 14 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 0f815674c9f..264c5b7ed40 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -883,37 +883,51 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	 *
 	 * Note that we can only change nbuckets during initial hashtable sizing.
 	 * Once we start building the hash, nbuckets is fixed.
+	 *
+	 * We will double a number of parameters (space_allowed, nbuckets and
+	 * num_skew_mcvs), which brings the overflow risk. We simply stop the loop
+	 * if that happens. We could do something smarter (e.g. cap nbuckets and
+	 * continue), but the complexity is not worth it. It's extremely rare and
+	 * this is best-effort attempt to reduce memory usage.
 	 */
 	while (nbatch > 1)
 	{
 		/*
-		 * Ensure that nbuckets can be allocated. nbuckets may have been
-		 * increased above hash_table_size / sizeof(HashJoinTuple) if work_mem
-		 * was very small, so checking if MaxAllocSize is enough for the
-		 * buckets is the safest check.
+		 * Check that nbuckets wont't overflow MaxAllocSize.
+		 *
+		 * With extremely low work_mem values, nbuckets may have been set
+		 * higher than hash_table_size / sizeof(HashJoinTuple). We don't try
+		 * to correct that here, we accept nbuckets to be oversized.
 		 */
 		if (nbuckets > MaxAllocSize / sizeof(HashJoinTuple) / 2)
 			break;
 
 		/*
-		 * We check that space_allowed wouldn't overflow because it will be
-		 * larger than hash_table_bytes if there is a skew hashtable.
+		 * Check that space_allowed won't overflow.
+		 *
+		 * We don't check hash_table_bytes, because we subtracted space for
+		 * skew hashtable from it (so it may not be equal to space_allowed).
 		 */
 		if ((*space_allowed) > SIZE_MAX / 2)
 			break;
 
 		/*
-		 * This is the same as:
+		 * Check that num_skew_mcvs won't overflow.
+		 */
+		if ((*num_skew_mcvs) > INT_MAX / 2)
+			break;
+
+		/*
+		 * Will halving the number of batches and doubling the size of the
+		 * hashtable reduce overall memory usage?
 		 *
-		 * hash_table_bytes + 2 * nbatch * BLCKSZ < hash_table_bytes * 2 +
-		 * nbatch * BLCKSZ
+		 * This is the same as (S = space_allowed):
 		 *
-		 * avoiding intermediate overflow.
+		 * (S + 2 * nbatch * BLCKSZ) < (S * 2 + nbatch * BLCKSZ)
 		 *
-		 * which is to say: will halving the number of batches and doubling
-		 * the size of the hashtable reduce overall memory usage?
+		 * but avoiding intermediate overflow.
 		 */
-		if (nbatch < hash_table_bytes / BLCKSZ)
+		if (nbatch < *space_allowed / BLCKSZ)
 			break;
 
 		/*
@@ -921,7 +935,8 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 		 * overflowing nbuckets.
 		 */
 		nbuckets *= 2;
-		hash_table_bytes *= 2;
+
+		*num_skew_mcvs = (*num_skew_mcvs) * 2;
 		*space_allowed = (*space_allowed) * 2;
 
 		nbatch /= 2;
-- 
2.51.0

From aee3da1fe907ba837a45825a158ab2e2507d3ed2 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 7 Oct 2025 13:21:14 -0400
Subject: [PATCH v4 1/2] Fix overflow risk in hashtable size calculation

ci-os-only:
---
 src/backend/executor/nodeHash.c | 115 +++++++++++++++-----------------
 1 file changed, 55 insertions(+), 60 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index a3415db4e20..0f815674c9f 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -850,90 +850,85 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	/*
 	 * Optimize the total amount of memory consumed by the hash node.
 	 *
-	 * The nbatch calculation above focuses on the size of the in-memory hash
-	 * table, assuming no per-batch overhead. Now adjust the number of batches
-	 * and the size of the hash table to minimize total memory consumed by the
-	 * hash node.
-	 *
-	 * Each batch file has a BLCKSZ buffer, and we may need two files per
-	 * batch (inner and outer side). So with enough batches this can be
-	 * significantly more memory than the hashtable itself.
+	 * The nbatch calculation above focuses on the the in-memory hash table,
+	 * assuming no per-batch overhead. But each batch may have two files, each
+	 * with a BLCKSZ buffer. With enough batches these buffers may use
+	 * significantly more memory than the hash table.
 	 *
 	 * The total memory usage may be expressed by this formula:
 	 *
-	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ) <= hash_table_bytes
+	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
 	 *
 	 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
 	 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
-	 * buffers. But for sufficiently large values of inner_rel_bytes value
-	 * there may not be a nbatch value that would make both parts fit into
-	 * hash_table_bytes.
-	 *
-	 * In this case we can't enforce the memory limit - we're going to exceed
-	 * it. We can however minimize the impact and use as little memory as
-	 * possible. (We haven't really enforced it before either, as we simply
-	 * ignored the batch files.)
-	 *
-	 * The formula for total memory usage says that given an inner relation of
-	 * size inner_rel_bytes, we may divide it into an arbitrary number of
-	 * batches. This determines both the size of the in-memory hash table and
-	 * the amount of memory needed for batch files. These two terms work in
-	 * opposite ways - when one decreases, the other increases.
+	 * buffers.
 	 *
-	 * For low nbatch values, the hash table takes most of the memory, but at
-	 * some point the batch files start to dominate. If you combine these two
-	 * terms, the memory consumption (for a fixed size of the inner relation)
-	 * has a u-shape, with a minimum at some nbatch value.
+	 * For very large inner_rel_bytes, there may be no nbatch that keeps total
+	 * memory usage under the budget (work_mem * hash_mem_multiplier). In that
+	 * case, we choose nbatch to minimize total memory consumption across both
+	 * the hashtable and file buffers.
 	 *
-	 * Our goal is to find this nbatch value, minimizing the memory usage. We
-	 * calculate the memory usage with half the batches (i.e. nbatch/2), and
-	 * if it's lower than the current memory usage we know it's better to use
-	 * fewer batches. We repeat this until reducing the number of batches does
-	 * not reduce the memory usage - we found the optimum. We know the optimum
-	 * exists, thanks to the u-shape.
+	 * As we increase the size of the hashtable and decrease the number of
+	 * batches, the total memory usage follows a U-shaped curve. We find the
+	 * minimum nbatch by "walking back" -- checking if halving nbatch would
+	 * lower total memory usage. We stop when it no longer helps.
 	 *
-	 * We only want to do this when exceeding the memory limit, not every
-	 * time. The goal is not to minimize memory usage in every case, but to
-	 * minimize the memory usage when we can't stay within the memory limit.
+	 * We only want to do this when we are already over the memory budget. We
+	 * don't explore increasing nbatch since that could force batching when it
+	 * is not needed.
 	 *
-	 * For this reason we only consider reducing the number of batches. We
-	 * could try the opposite direction too, but that would save memory only
-	 * when most of the memory is used by the hash table. And the hash table
-	 * was used for the initial sizing, so we shouldn't be exceeding the
-	 * memory limit too much. We might save memory by using more batches, but
-	 * it would result in spilling more batch files, which does not seem like
-	 * a great trade off.
+	 * While growing the hashtable, we also adjust the number of buckets to
+	 * maintain a load factor of NTUP_PER_BUCKET while squeezing tuples back
+	 * from batches into the hashtable.
 	 *
-	 * While growing the hashtable, we also adjust the number of buckets, to
-	 * not have more than one tuple per bucket (load factor 1). We can only do
-	 * this during the initial sizing - once we start building the hash,
-	 * nbucket is fixed.
+	 * Note that we can only change nbuckets during initial hashtable sizing.
+	 * Once we start building the hash, nbuckets is fixed.
 	 */
-	while (nbatch > 0)
+	while (nbatch > 1)
 	{
-		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
+		/*
+		 * Ensure that nbuckets can be allocated. nbuckets may have been
+		 * increased above hash_table_size / sizeof(HashJoinTuple) if work_mem
+		 * was very small, so checking if MaxAllocSize is enough for the
+		 * buckets is the safest check.
+		 */
+		if (nbuckets > MaxAllocSize / sizeof(HashJoinTuple) / 2)
+			break;
 
-		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		/*
+		 * We check that space_allowed wouldn't overflow because it will be
+		 * larger than hash_table_bytes if there is a skew hashtable.
+		 */
+		if ((*space_allowed) > SIZE_MAX / 2)
+			break;
 
-		/* If the memory usage would not decrease, we found the optimum. */
-		if (current_space < new_space)
+		/*
+		 * This is the same as:
+		 *
+		 * hash_table_bytes + 2 * nbatch * BLCKSZ < hash_table_bytes * 2 +
+		 * nbatch * BLCKSZ
+		 *
+		 * avoiding intermediate overflow.
+		 *
+		 * which is to say: will halving the number of batches and doubling
+		 * the size of the hashtable reduce overall memory usage?
+		 */
+		if (nbatch < hash_table_bytes / BLCKSZ)
 			break;
 
 		/*
-		 * It's better to use half the batches, so do that and adjust the
-		 * nbucket in the opposite direction, and double the allowance.
+		 * MaxAllocSize is sufficiently small that we are not worried about
+		 * overflowing nbuckets.
 		 */
-		nbatch /= 2;
 		nbuckets *= 2;
-
+		hash_table_bytes *= 2;
 		*space_allowed = (*space_allowed) * 2;
+
+		nbatch /= 2;
 	}
 
 	Assert(nbuckets > 0);
 	Assert(nbatch > 0);
-
 	*numbuckets = nbuckets;
 	*numbatches = nbatch;
 }
@@ -994,7 +989,7 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the
-- 
2.51.0

From 516de50b0fe2075955dab2168a7e46f0f9222278 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 7 Oct 2025 13:21:14 -0400
Subject: [PATCH v5 1/3] Fix overflow risk in hashtable size calculation

ci-os-only:
---
 src/backend/executor/nodeHash.c | 115 +++++++++++++++-----------------
 1 file changed, 55 insertions(+), 60 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index a3415db4e20..0f815674c9f 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -850,90 +850,85 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	/*
 	 * Optimize the total amount of memory consumed by the hash node.
 	 *
-	 * The nbatch calculation above focuses on the size of the in-memory hash
-	 * table, assuming no per-batch overhead. Now adjust the number of batches
-	 * and the size of the hash table to minimize total memory consumed by the
-	 * hash node.
-	 *
-	 * Each batch file has a BLCKSZ buffer, and we may need two files per
-	 * batch (inner and outer side). So with enough batches this can be
-	 * significantly more memory than the hashtable itself.
+	 * The nbatch calculation above focuses on the the in-memory hash table,
+	 * assuming no per-batch overhead. But each batch may have two files, each
+	 * with a BLCKSZ buffer. With enough batches these buffers may use
+	 * significantly more memory than the hash table.
 	 *
 	 * The total memory usage may be expressed by this formula:
 	 *
-	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ) <= hash_table_bytes
+	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
 	 *
 	 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
 	 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
-	 * buffers. But for sufficiently large values of inner_rel_bytes value
-	 * there may not be a nbatch value that would make both parts fit into
-	 * hash_table_bytes.
-	 *
-	 * In this case we can't enforce the memory limit - we're going to exceed
-	 * it. We can however minimize the impact and use as little memory as
-	 * possible. (We haven't really enforced it before either, as we simply
-	 * ignored the batch files.)
-	 *
-	 * The formula for total memory usage says that given an inner relation of
-	 * size inner_rel_bytes, we may divide it into an arbitrary number of
-	 * batches. This determines both the size of the in-memory hash table and
-	 * the amount of memory needed for batch files. These two terms work in
-	 * opposite ways - when one decreases, the other increases.
+	 * buffers.
 	 *
-	 * For low nbatch values, the hash table takes most of the memory, but at
-	 * some point the batch files start to dominate. If you combine these two
-	 * terms, the memory consumption (for a fixed size of the inner relation)
-	 * has a u-shape, with a minimum at some nbatch value.
+	 * For very large inner_rel_bytes, there may be no nbatch that keeps total
+	 * memory usage under the budget (work_mem * hash_mem_multiplier). In that
+	 * case, we choose nbatch to minimize total memory consumption across both
+	 * the hashtable and file buffers.
 	 *
-	 * Our goal is to find this nbatch value, minimizing the memory usage. We
-	 * calculate the memory usage with half the batches (i.e. nbatch/2), and
-	 * if it's lower than the current memory usage we know it's better to use
-	 * fewer batches. We repeat this until reducing the number of batches does
-	 * not reduce the memory usage - we found the optimum. We know the optimum
-	 * exists, thanks to the u-shape.
+	 * As we increase the size of the hashtable and decrease the number of
+	 * batches, the total memory usage follows a U-shaped curve. We find the
+	 * minimum nbatch by "walking back" -- checking if halving nbatch would
+	 * lower total memory usage. We stop when it no longer helps.
 	 *
-	 * We only want to do this when exceeding the memory limit, not every
-	 * time. The goal is not to minimize memory usage in every case, but to
-	 * minimize the memory usage when we can't stay within the memory limit.
+	 * We only want to do this when we are already over the memory budget. We
+	 * don't explore increasing nbatch since that could force batching when it
+	 * is not needed.
 	 *
-	 * For this reason we only consider reducing the number of batches. We
-	 * could try the opposite direction too, but that would save memory only
-	 * when most of the memory is used by the hash table. And the hash table
-	 * was used for the initial sizing, so we shouldn't be exceeding the
-	 * memory limit too much. We might save memory by using more batches, but
-	 * it would result in spilling more batch files, which does not seem like
-	 * a great trade off.
+	 * While growing the hashtable, we also adjust the number of buckets to
+	 * maintain a load factor of NTUP_PER_BUCKET while squeezing tuples back
+	 * from batches into the hashtable.
 	 *
-	 * While growing the hashtable, we also adjust the number of buckets, to
-	 * not have more than one tuple per bucket (load factor 1). We can only do
-	 * this during the initial sizing - once we start building the hash,
-	 * nbucket is fixed.
+	 * Note that we can only change nbuckets during initial hashtable sizing.
+	 * Once we start building the hash, nbuckets is fixed.
 	 */
-	while (nbatch > 0)
+	while (nbatch > 1)
 	{
-		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
+		/*
+		 * Ensure that nbuckets can be allocated. nbuckets may have been
+		 * increased above hash_table_size / sizeof(HashJoinTuple) if work_mem
+		 * was very small, so checking if MaxAllocSize is enough for the
+		 * buckets is the safest check.
+		 */
+		if (nbuckets > MaxAllocSize / sizeof(HashJoinTuple) / 2)
+			break;
 
-		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		/*
+		 * We check that space_allowed wouldn't overflow because it will be
+		 * larger than hash_table_bytes if there is a skew hashtable.
+		 */
+		if ((*space_allowed) > SIZE_MAX / 2)
+			break;
 
-		/* If the memory usage would not decrease, we found the optimum. */
-		if (current_space < new_space)
+		/*
+		 * This is the same as:
+		 *
+		 * hash_table_bytes + 2 * nbatch * BLCKSZ < hash_table_bytes * 2 +
+		 * nbatch * BLCKSZ
+		 *
+		 * avoiding intermediate overflow.
+		 *
+		 * which is to say: will halving the number of batches and doubling
+		 * the size of the hashtable reduce overall memory usage?
+		 */
+		if (nbatch < hash_table_bytes / BLCKSZ)
 			break;
 
 		/*
-		 * It's better to use half the batches, so do that and adjust the
-		 * nbucket in the opposite direction, and double the allowance.
+		 * MaxAllocSize is sufficiently small that we are not worried about
+		 * overflowing nbuckets.
 		 */
-		nbatch /= 2;
 		nbuckets *= 2;
-
+		hash_table_bytes *= 2;
 		*space_allowed = (*space_allowed) * 2;
+
+		nbatch /= 2;
 	}
 
 	Assert(nbuckets > 0);
 	Assert(nbatch > 0);
-
 	*numbuckets = nbuckets;
 	*numbatches = nbatch;
 }
@@ -994,7 +989,7 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the
-- 
2.43.0

From 27544e1504a0f014165e1120e5230e22a424b8b4 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@vondra.me>
Date: Fri, 10 Oct 2025 00:38:05 +0200
Subject: [PATCH v5 2/3] adjustments

---
 src/backend/executor/nodeHash.c | 43 ++++++++++++++++++++++-----------
 1 file changed, 29 insertions(+), 14 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 0f815674c9f..264c5b7ed40 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -883,37 +883,51 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	 *
 	 * Note that we can only change nbuckets during initial hashtable sizing.
 	 * Once we start building the hash, nbuckets is fixed.
+	 *
+	 * We will double a number of parameters (space_allowed, nbuckets and
+	 * num_skew_mcvs), which brings the overflow risk. We simply stop the loop
+	 * if that happens. We could do something smarter (e.g. cap nbuckets and
+	 * continue), but the complexity is not worth it. It's extremely rare and
+	 * this is best-effort attempt to reduce memory usage.
 	 */
 	while (nbatch > 1)
 	{
 		/*
-		 * Ensure that nbuckets can be allocated. nbuckets may have been
-		 * increased above hash_table_size / sizeof(HashJoinTuple) if work_mem
-		 * was very small, so checking if MaxAllocSize is enough for the
-		 * buckets is the safest check.
+		 * Check that nbuckets wont't overflow MaxAllocSize.
+		 *
+		 * With extremely low work_mem values, nbuckets may have been set
+		 * higher than hash_table_size / sizeof(HashJoinTuple). We don't try
+		 * to correct that here, we accept nbuckets to be oversized.
 		 */
 		if (nbuckets > MaxAllocSize / sizeof(HashJoinTuple) / 2)
 			break;
 
 		/*
-		 * We check that space_allowed wouldn't overflow because it will be
-		 * larger than hash_table_bytes if there is a skew hashtable.
+		 * Check that space_allowed won't overflow.
+		 *
+		 * We don't check hash_table_bytes, because we subtracted space for
+		 * skew hashtable from it (so it may not be equal to space_allowed).
 		 */
 		if ((*space_allowed) > SIZE_MAX / 2)
 			break;
 
 		/*
-		 * This is the same as:
+		 * Check that num_skew_mcvs won't overflow.
+		 */
+		if ((*num_skew_mcvs) > INT_MAX / 2)
+			break;
+
+		/*
+		 * Will halving the number of batches and doubling the size of the
+		 * hashtable reduce overall memory usage?
 		 *
-		 * hash_table_bytes + 2 * nbatch * BLCKSZ < hash_table_bytes * 2 +
-		 * nbatch * BLCKSZ
+		 * This is the same as (S = space_allowed):
 		 *
-		 * avoiding intermediate overflow.
+		 * (S + 2 * nbatch * BLCKSZ) < (S * 2 + nbatch * BLCKSZ)
 		 *
-		 * which is to say: will halving the number of batches and doubling
-		 * the size of the hashtable reduce overall memory usage?
+		 * but avoiding intermediate overflow.
 		 */
-		if (nbatch < hash_table_bytes / BLCKSZ)
+		if (nbatch < *space_allowed / BLCKSZ)
 			break;
 
 		/*
@@ -921,7 +935,8 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 		 * overflowing nbuckets.
 		 */
 		nbuckets *= 2;
-		hash_table_bytes *= 2;
+
+		*num_skew_mcvs = (*num_skew_mcvs) * 2;
 		*space_allowed = (*space_allowed) * 2;
 
 		nbatch /= 2;
-- 
2.43.0

From 882905cabe42d061aad6b895602710beb5d81297 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Mon, 13 Oct 2025 12:03:54 -0400
Subject: [PATCH v5 3/3] more tweaks

---
 src/backend/executor/nodeHash.c | 39 ++++++++++++++-------------------
 1 file changed, 17 insertions(+), 22 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 264c5b7ed40..f562077df5e 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -884,37 +884,27 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	 * Note that we can only change nbuckets during initial hashtable sizing.
 	 * Once we start building the hash, nbuckets is fixed.
 	 *
-	 * We will double a number of parameters (space_allowed, nbuckets and
-	 * num_skew_mcvs), which brings the overflow risk. We simply stop the loop
-	 * if that happens. We could do something smarter (e.g. cap nbuckets and
-	 * continue), but the complexity is not worth it. It's extremely rare and
-	 * this is best-effort attempt to reduce memory usage.
+	 * We double several parameters (space_allowed, nbuckets, and
+	 * num_skew_mcvs), which introduces a risk of overflow. We avoid this by
+	 * exiting the loop. We could do something smarter (e.g. capping nbuckets
+	 * and continue), but the complexity is not worth it. Such cases are
+	 * extremely rare, and this is a best-effort attempt to reduce memory
+	 * usage.
 	 */
 	while (nbatch > 1)
 	{
-		/*
-		 * Check that nbuckets wont't overflow MaxAllocSize.
-		 *
-		 * With extremely low work_mem values, nbuckets may have been set
-		 * higher than hash_table_size / sizeof(HashJoinTuple). We don't try
-		 * to correct that here, we accept nbuckets to be oversized.
-		 */
+		/* Check that nbuckets wont't overflow MaxAllocSize */
 		if (nbuckets > MaxAllocSize / sizeof(HashJoinTuple) / 2)
 			break;
 
-		/*
-		 * Check that space_allowed won't overflow.
-		 *
-		 * We don't check hash_table_bytes, because we subtracted space for
-		 * skew hashtable from it (so it may not be equal to space_allowed).
-		 */
-		if ((*space_allowed) > SIZE_MAX / 2)
-			break;
+		/* num_skew_mcvs should be less than nbuckets */
+		Assert((*num_skew_mcvs) < INT_MAX / 2);
 
 		/*
-		 * Check that num_skew_mcvs won't overflow.
+		 * space_allowed will exceed hash_table_bytes when there is a
+		 * skew_hashtable. Just exit if doubling it will overflow.
 		 */
-		if ((*num_skew_mcvs) > INT_MAX / 2)
+		if ((*space_allowed) > SIZE_MAX / 2)
 			break;
 
 		/*
@@ -933,6 +923,10 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 		/*
 		 * MaxAllocSize is sufficiently small that we are not worried about
 		 * overflowing nbuckets.
+		 *
+		 * With extremely low work_mem values, nbuckets may have been set
+		 * higher than hash_table_bytes / sizeof(HashJoinTuple). We don't try
+		 * to correct that here.
 		 */
 		nbuckets *= 2;
 
@@ -944,6 +938,7 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 
 	Assert(nbuckets > 0);
 	Assert(nbatch > 0);
+
 	*numbuckets = nbuckets;
 	*numbatches = nbatch;
 }
-- 
2.43.0

From 5b0eabb40f12435d08efa2634925530ef0a8ba88 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 7 Oct 2025 13:21:14 -0400
Subject: [PATCH v6] Fix overflow risk in hashtable size calculation

ci-os-only:
---
 src/backend/executor/nodeHash.c | 125 +++++++++++++++++---------------
 1 file changed, 66 insertions(+), 59 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index a3415db4e20..3fe1fa4831c 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -850,85 +850,92 @@ ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
 	/*
 	 * Optimize the total amount of memory consumed by the hash node.
 	 *
-	 * The nbatch calculation above focuses on the size of the in-memory hash
-	 * table, assuming no per-batch overhead. Now adjust the number of batches
-	 * and the size of the hash table to minimize total memory consumed by the
-	 * hash node.
-	 *
-	 * Each batch file has a BLCKSZ buffer, and we may need two files per
-	 * batch (inner and outer side). So with enough batches this can be
-	 * significantly more memory than the hashtable itself.
+	 * The nbatch calculation above focuses on the the in-memory hash table,
+	 * assuming no per-batch overhead. But each batch may have two files, each
+	 * with a BLCKSZ buffer. With enough batches these buffers may use
+	 * significantly more memory than the hash table.
 	 *
 	 * The total memory usage may be expressed by this formula:
 	 *
-	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ) <= hash_table_bytes
+	 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
 	 *
 	 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
 	 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
-	 * buffers. But for sufficiently large values of inner_rel_bytes value
-	 * there may not be a nbatch value that would make both parts fit into
-	 * hash_table_bytes.
-	 *
-	 * In this case we can't enforce the memory limit - we're going to exceed
-	 * it. We can however minimize the impact and use as little memory as
-	 * possible. (We haven't really enforced it before either, as we simply
-	 * ignored the batch files.)
+	 * buffers.
 	 *
-	 * The formula for total memory usage says that given an inner relation of
-	 * size inner_rel_bytes, we may divide it into an arbitrary number of
-	 * batches. This determines both the size of the in-memory hash table and
-	 * the amount of memory needed for batch files. These two terms work in
-	 * opposite ways - when one decreases, the other increases.
+	 * For very large inner_rel_bytes, there may be no nbatch that keeps total
+	 * memory usage under the budget (work_mem * hash_mem_multiplier). In that
+	 * case, we choose nbatch to minimize total memory consumption across both
+	 * the hashtable and file buffers.
 	 *
-	 * For low nbatch values, the hash table takes most of the memory, but at
-	 * some point the batch files start to dominate. If you combine these two
-	 * terms, the memory consumption (for a fixed size of the inner relation)
-	 * has a u-shape, with a minimum at some nbatch value.
+	 * As we increase the size of the hashtable and decrease the number of
+	 * batches, the total memory usage follows a U-shaped curve. We find the
+	 * minimum nbatch by "walking back" -- checking if halving nbatch would
+	 * lower total memory usage. We stop when it no longer helps.
 	 *
-	 * Our goal is to find this nbatch value, minimizing the memory usage. We
-	 * calculate the memory usage with half the batches (i.e. nbatch/2), and
-	 * if it's lower than the current memory usage we know it's better to use
-	 * fewer batches. We repeat this until reducing the number of batches does
-	 * not reduce the memory usage - we found the optimum. We know the optimum
-	 * exists, thanks to the u-shape.
+	 * We only want to do this when we are already over the memory budget. We
+	 * don't explore increasing nbatch since that could force batching when it
+	 * is not needed.
 	 *
-	 * We only want to do this when exceeding the memory limit, not every
-	 * time. The goal is not to minimize memory usage in every case, but to
-	 * minimize the memory usage when we can't stay within the memory limit.
+	 * While growing the hashtable, we also adjust the number of buckets to
+	 * maintain a load factor of NTUP_PER_BUCKET while squeezing tuples back
+	 * from batches into the hashtable.
 	 *
-	 * For this reason we only consider reducing the number of batches. We
-	 * could try the opposite direction too, but that would save memory only
-	 * when most of the memory is used by the hash table. And the hash table
-	 * was used for the initial sizing, so we shouldn't be exceeding the
-	 * memory limit too much. We might save memory by using more batches, but
-	 * it would result in spilling more batch files, which does not seem like
-	 * a great trade off.
+	 * Note that we can only change nbuckets during initial hashtable sizing.
+	 * Once we start building the hash, nbuckets is fixed.
 	 *
-	 * While growing the hashtable, we also adjust the number of buckets, to
-	 * not have more than one tuple per bucket (load factor 1). We can only do
-	 * this during the initial sizing - once we start building the hash,
-	 * nbucket is fixed.
-	 */
-	while (nbatch > 0)
+	 * We double several parameters (space_allowed, nbuckets, and
+	 * num_skew_mcvs), which introduces a risk of overflow. We avoid this by
+	 * exiting the loop. We could do something smarter (e.g. capping nbuckets
+	 * and continue), but the complexity is not worth it. Such cases are
+	 * extremely rare, and this is a best-effort attempt to reduce memory
+	 * usage.
+	 */
+	while (nbatch > 1)
 	{
-		/* how much memory are we using with current nbatch value */
-		size_t		current_space = hash_table_bytes + (2 * nbatch * BLCKSZ);
+		/* Check that buckets wont't overflow MaxAllocSize */
+		if (nbuckets > (MaxAllocSize / sizeof(HashJoinTuple) / 2))
+			break;
+
+		/* num_skew_mcvs should be less than nbuckets */
+		Assert((*num_skew_mcvs) < (INT_MAX / 2));
 
-		/* how much memory would we use with half the batches */
-		size_t		new_space = hash_table_bytes * 2 + (nbatch * BLCKSZ);
+		/*
+		 * Check that space_allowed won't overlow SIZE_MAX.
+		 *
+		 * We don't use hash_table_bytes here, because it does not include the
+		 * skew buckets. And we want to limit the overall memory limit.
+		 */
+		if ((*space_allowed) > (SIZE_MAX / 2))
+			break;
 
-		/* If the memory usage would not decrease, we found the optimum. */
-		if (current_space < new_space)
+		/*
+		 * Will halving the number of batches and doubling the size of the
+		 * hashtable reduce overall memory usage?
+		 *
+		 * This is the same as (S = space_allowed):
+		 *
+		 * (S + 2 * nbatch * BLCKSZ) < (S * 2 + nbatch * BLCKSZ)
+		 *
+		 * but avoiding intermediate overflow.
+		 */
+		if (nbatch < (*space_allowed) / BLCKSZ)
 			break;
 
 		/*
-		 * It's better to use half the batches, so do that and adjust the
-		 * nbucket in the opposite direction, and double the allowance.
+		 * MaxAllocSize is sufficiently small that we are not worried about
+		 * overflowing nbuckets.
+		 *
+		 * With extremely low work_mem values, nbuckets may have been set to
+		 * 1024, and end up oversized here. We We don't try to correct that,
+		 * to keep the code simple. It may terminate the loop earlier.
 		 */
-		nbatch /= 2;
 		nbuckets *= 2;
 
+		*num_skew_mcvs = (*num_skew_mcvs) * 2;
 		*space_allowed = (*space_allowed) * 2;
+
+		nbatch /= 2;
 	}
 
 	Assert(nbuckets > 0);
@@ -994,14 +1001,14 @@ ExecHashIncreaseBatchSize(HashJoinTable hashtable)
 	 * How much additional memory would doubling nbatch use? Each batch may
 	 * require two buffered files (inner/outer), with a BLCKSZ buffer.
 	 */
-	size_t		batchSpace = (hashtable->nbatch * 2 * BLCKSZ);
+	size_t		batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
 
 	/*
 	 * Compare the new space needed for doubling nbatch and for enlarging the
 	 * in-memory hash table. If doubling the hash table needs less memory,
 	 * just do that. Otherwise, continue with doubling the nbatch.
 	 *
-	 * We're either doubling spaceAllowed of batchSpace, so which of those
+	 * We're either doubling spaceAllowed or batchSpace, so which of those
 	 * increases the memory usage the least is the same as comparing the
 	 * values directly.
 	 */
-- 
2.51.0