NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commite69d644

committed

Rotate instead of shifting hash join batch number.

Our algorithm for choosing batch numbers turned out not to workeffectively for multi-billion key inner relations. We would usemore hash bits than we have, and effectively concentrate all tuplesinto a smaller number of batches than we intended. While ideallywe should switch to wider hashes, for now, change the algorithm toone that effectively gives up bits from the bucket number when wedon't have enough bits. That means we'll finish up with longerbucket chains than would be ideal, but that's better than havingbatches that don't fit in work_mem and can't be divided.Batch-patch to all supported releases.Author: Thomas MunroReviewed-by: Tom Lane, thanks also to Tomas Vondra, Alvaro Herrera, Andres Freund for testing and discussionReported-by: James ColemanDiscussion:https://postgr.es/m/16104-dc11ed911f1ab9df%40postgresql.org

1 parentd5b9c2b commite69d644Copy full SHA for e69d644

File tree

2 files changed

+18

-4

lines changed

src
- backend/executor
  - nodeHash.c
- include/port
  - pg_bitutils.h

2 files changed

+18

-4

lines changed

`‎src/backend/executor/nodeHash.c`

Lines changed: 9 additions & 4 deletions

Original file line number	Diff line number	Diff line change
`@@ -37,6 +37,7 @@`
`37`	`37`	`#include"miscadmin.h"`
`38`	`38`	`#include"pgstat.h"`
`39`	`39`	`#include"port/atomics.h"`
	`40`	`+#include"port/pg_bitutils.h"`
`40`	`41`	`#include"utils/dynahash.h"`
`41`	`42`	`#include"utils/lsyscache.h"`
`42`	`43`	`#include"utils/memutils.h"`
`@@ -1877,7 +1878,7 @@ ExecHashGetHashValue(HashJoinTable hashtable,`
`1877`	`1878`	`* chains), and must only cause the batch number to remain the same or`
`1878`	`1879`	`* increase. Our algorithm is`
`1879`	`1880`	`*bucketno = hashvalue MOD nbuckets`
`1880`		`- *batchno = (hashvalue DIV nbuckets) MOD nbatch`
	`1881`	`+ *batchno =ROR(hashvalue, log2_nbuckets) MOD nbatch`
`1881`	`1882`	`* where nbuckets and nbatch are both expected to be powers of 2, so we can`
`1882`	`1883`	`* do the computations by shifting and masking. (This assumes that all hash`
`1883`	`1884`	`* functions are good about randomizing all their output bits, else we are`
`@@ -1889,7 +1890,11 @@ ExecHashGetHashValue(HashJoinTable hashtable,`
`1889`	`1890`	`* number the way we do here).`
`1890`	`1891`	`*`
`1891`	`1892`	`* nbatch is always a power of 2; we increase it only by doubling it. This`
`1892`		`- * effectively adds one more bit to the top of the batchno.`
	`1893`	`+ * effectively adds one more bit to the top of the batchno. In very large`
	`1894`	`+ * joins, we might run out of bits to add, so we do this by rotating the hash`
	`1895`	`+ * value. This causes batchno to steal bits from bucketno when the number of`
	`1896`	`+ * virtual buckets exceeds 2^32. It's better to have longer bucket chains`
	`1897`	`+ * than to lose the ability to divide batches.`
`1893`	`1898`	`*/`
`1894`	`1899`	`void`
`1895`	`1900`	`ExecHashGetBucketAndBatch(HashJoinTablehashtable,`
`@@ -1902,9 +1907,9 @@ ExecHashGetBucketAndBatch(HashJoinTable hashtable,`
`1902`	`1907`
`1903`	`1908`	`if (nbatch>1)`
`1904`	`1909`	`{`
`1905`		`-/* we can do MOD by masking, DIV by shifting */`
`1906`	`1910`	`*bucketno=hashvalue& (nbuckets-1);`
`1907`		`-*batchno= (hashvalue >>hashtable->log2_nbuckets)& (nbatch-1);`
	`1911`	`+*batchno=pg_rotate_right32(hashvalue,`
	`1912`	`+hashtable->log2_nbuckets)& (nbatch-1);`
`1908`	`1913`	`}`
`1909`	`1914`	`else`
`1910`	`1915`	`{`

`‎src/include/port/pg_bitutils.h`

Lines changed: 9 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -136,4 +136,13 @@ extern int(*pg_popcount64) (uint64 word);`
`136`	`136`	`/* Count the number of one-bits in a byte array */`
`137`	`137`	`externuint64pg_popcount(constchar*buf,intbytes);`
`138`	`138`
	`139`	`+/*`
	`140`	`+ * Rotate the bits of "word" to the right by n bits.`
	`141`	`+ */`
	`142`	`+staticinlineuint32`
	`143`	`+pg_rotate_right32(uint32word,intn)`
	`144`	`+{`
	`145`	`+return (word >>n) \| (word << (sizeof(word)*BITS_PER_BYTE-n));`
	`146`	`+}`
	`147`	`+`
`139`	`148`	`#endif/* PG_BITUTILS_H */`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commite69d644

File tree

2 files changed

2 files changed

`‎src/backend/executor/nodeHash.c`

`‎src/include/port/pg_bitutils.h`

0 commit comments