diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/backend/executor/nodeHash.c | 13 | ||||
| -rw-r--r-- | src/include/port/pg_bitutils.h | 9 |
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 */ |