aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/backend/executor/nodeHash.c13
-rw-r--r--src/include/port/pg_bitutils.h9
2 files changed, 18 insertions, 4 deletions
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 224cbb32bad..517ded822e3 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -37,6 +37,7 @@
#include "miscadmin.h"
#include "pgstat.h"
#include "port/atomics.h"
+#include "port/pg_bitutils.h"
#include "utils/dynahash.h"
#include "utils/memutils.h"
#include "utils/lsyscache.h"
@@ -1878,7 +1879,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 = ROR(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
@@ -1890,7 +1891,11 @@ ExecHashGetHashValue(HashJoinTable hashtable,
* number the way we do here).
*
* nbatch is always a power of 2; we increase it only by doubling it. This
- * effectively adds one more bit to the top of the batchno.
+ * effectively adds one more bit to the top of the batchno. In very large
+ * joins, we might run out of bits to add, so we do this by rotating the hash
+ * value. This causes batchno to steal bits from bucketno when the number of
+ * virtual buckets exceeds 2^32. It's better to have longer bucket chains
+ * than to lose the ability to divide batches.
*/
void
ExecHashGetBucketAndBatch(HashJoinTable hashtable,
@@ -1903,9 +1908,9 @@ ExecHashGetBucketAndBatch(HashJoinTable hashtable,
if (nbatch > 1)
{
- /* we can do MOD by masking, DIV by shifting */
*bucketno = hashvalue & (nbuckets - 1);
- *batchno = (hashvalue >> hashtable->log2_nbuckets) & (nbatch - 1);
+ *batchno = pg_rotate_right32(hashvalue,
+ hashtable->log2_nbuckets) & (nbatch - 1);
}
else
{
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 5197926696f..d1544834a6b 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -136,4 +136,13 @@ extern int (*pg_popcount64) (uint64 word);
/* Count the number of one-bits in a byte array */
extern uint64 pg_popcount(const char *buf, int bytes);
+/*
+ * Rotate the bits of "word" to the right by n bits.
+ */
+static inline uint32
+pg_rotate_right32(uint32 word, int n)
+{
+ return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
+}
+
#endif /* PG_BITUTILS_H */