diff options
Diffstat (limited to 'src/backend/executor/nodeHash.c')
| -rw-r--r-- | src/backend/executor/nodeHash.c | 21 |
1 files changed, 17 insertions, 4 deletions
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c index 75637d586a8..a9a5a96e4b7 100644 --- a/src/backend/executor/nodeHash.c +++ b/src/backend/executor/nodeHash.c @@ -1006,6 +1006,15 @@ ExecHashGetHashValue(HashJoinTable hashtable, } /* + * 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)); +} + +/* * ExecHashGetBucketAndBatch * Determine the bucket number and batch number for a hash value * @@ -1014,7 +1023,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 @@ -1026,7 +1035,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, @@ -1039,9 +1052,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 { |