Re: BUG #16104: Invalid DSA Memory Alloc Request in Parallel Hash

On Wed, Dec 11, 2019 at 7:36 AM Tomas Vondra
<[email protected]> wrote:
> On Tue, Dec 10, 2019 at 02:35:16PM -0300, Alvaro Herrera wrote:
> >On 2019-Dec-10, Tomas Vondra wrote:
> >> It's probably still a good idea to do this, although I wonder if we
> >> might start doing this only when actually running out of bits (and use
> >> the current algorithm by default). But I have no idea if that would be
> >> any cheaper, and it would add complexity.

Yeah, I understand your desire to minimise the change here.  One thing
we could do to get exactly the same algorithm as today right up until
we run out of bits and then begin stealing bucket bits would be to
rotate instead of shifting:

-               *batchno = (hashvalue >> hashtable->log2_nbuckets) &
(nbatch - 1);
+               *batchno = rotate(hashvalue, hashtable->log2_nbuckets)
& (nbatch - 1);

Attached.  Thoughts?  At a glance, the definition of rotate() that I
used seems to be recognised by my compiler, so that the generated code
differs only by a SHR instruction changing to a ROR instruction on my
system.

The bit-reversing thing has once nice advantage: you are allowed to
increase nbuckets later. But then I thought of another way to achieve
that: take batchno from the low end, and bucketno from the high end.
I'm not persuing that, based on the suspicion that what we all want
here is the minimal possible change.

> >I'm under the impression that this patch is proposed for backpatching,
> >and that in master we can simply increase the hash width.
>
> Possibly, although AFAIK we don't have that patch yet, and I don't
> recall any measurements (so it might have overhead too, not sure). But
> it's true additional complexity might complicate backpatching.

What I'd like to experiment with in the new year is a code
specialisation scheme that further developers what I did with
ExecHashJoinImpl().  This would increase the executable size by
including a bunch of different variants of the hash join code, but
avoid adding new branches (and also remove some existing branches) in
the hot paths.  We'd still write one "template" version of the
algorithm that contains if statements for the points of variation, and
then we'd call it from a load of wrapper functions with constant
arguments and forced inlining.  For example, there might be a variant
for { non-parallel, 64 bit hashes, no skew optimisation }.  A more
extreme version of the idea inlines the actual hashing functions for a
handful of common cases like test and integer keys, but that gets into
combination explosion territory among other problems.  I have some
early prototype code along these lines but it's not good enough yet;
more soon.  I should probably think about Andres's proposal to merge
Hash and Hash Join nodes first.

From 359d06adb9924266bc9022295ae2c68964703f70 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email protected]>
Date: Sat, 14 Dec 2019 11:36:28 +1300
Subject: [PATCH] Rotate instead of shifting hash join batch number.

Our algorithm for choosing batch numbers turned out not to work
effectively for multi-billion key hash tables.  We would try to use
more hash bits than we have, and effectively concentrate all tuples
into a smaller number of batches than we intended.  While ideally
we should switch to wider hashes, for now, change the algorithm to
one that effectively gives up bits from the bucket number instead,
leaving some buckets empty.

Author: Thomas Munro
Reported-by: James Coleman
Discussion: https://postgr.es/m/16104-dc11ed911f1ab9df%40postgresql.org
---
 src/backend/executor/nodeHash.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index d6f4eda097..5bcdc5b5d5 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -1877,7 +1877,7 @@ ExecHashGetHashValue(HashJoinTable hashtable,
  * chains), and must only cause the batch number to remain the same or
  * increase.  Our algorithm is
  *		bucketno = hashvalue MOD nbuckets
- *		batchno = (hashvalue DIV nbuckets) MOD nbatch
+ *		batchno = ROT(hashvalue, log2_nbuckets) MOD nbatch
  * where nbuckets and nbatch are both expected to be powers of 2, so we can
  * do the computations by shifting and masking.  (This assumes that all hash
  * functions are good about randomizing all their output bits, else we are
@@ -1900,11 +1900,12 @@ ExecHashGetBucketAndBatch(HashJoinTable hashtable,
 	uint32		nbuckets = (uint32) hashtable->nbuckets;
 	uint32		nbatch = (uint32) hashtable->nbatch;
 
+#define rotate(v, n) (((v) >> (n)) | ((v) << (((sizeof(v) * CHAR_BIT) - (n)))))
+
 	if (nbatch > 1)
 	{
-		/* we can do MOD by masking, DIV by shifting */
 		*bucketno = hashvalue & (nbuckets - 1);
-		*batchno = (hashvalue >> hashtable->log2_nbuckets) & (nbatch - 1);
+		*batchno = rotate(hashvalue, hashtable->log2_nbuckets) & (nbatch - 1);
 	}
 	else
 	{
-- 
2.23.0