diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c index 5e05ec3..aad5e98 100644 --- a/src/backend/executor/nodeHash.c +++ b/src/backend/executor/nodeHash.c @@ -36,6 +36,7 @@ #include "utils/memutils.h" #include "utils/lsyscache.h" #include "utils/syscache.h" +#include "utils/murmur3.h" static void ExecHashIncreaseNumBatches(HashJoinTable hashtable); @@ -47,9 +48,16 @@ static void ExecHashSkewTableInsert(HashJoinTable hashtable, uint32 hashvalue, int bucketNumber); static void ExecHashRemoveNextSkewBucket(HashJoinTable hashtable); +static void ExecHashBloomAddValue(HashJoinTable hashtable, uint32 hashvalue); static void *dense_alloc(HashJoinTable hashtable, Size size); +static BloomFilter BloomFilterInit(double nrows, double error); + +/* let's shoot for 5% false positives error rate (arbitrary value) */ +#define BLOOM_ERROR_RATE 0.05 + + /* ---------------------------------------------------------------- * ExecHash * @@ -112,6 +120,8 @@ MultiExecHash(HashState *node) { int bucketNumber; + ExecHashBloomAddValue(hashtable, hashvalue); + bucketNumber = ExecHashGetSkewBucket(hashtable, hashvalue); if (bucketNumber != INVALID_SKEW_BUCKET_NO) { @@ -310,6 +320,11 @@ ExecHashTableCreate(Hash *node, List *hashOperators, bool keepNulls) hashtable->spaceAllowedSkew = hashtable->spaceAllowed * SKEW_WORK_MEM_PERCENT / 100; hashtable->chunks = NULL; + hashtable->bloomFilter = NULL; + + /* do bloom filter only when batching */ + if (nbatch > 1) + hashtable->bloomFilter = BloomFilterInit(outerNode->plan_rows, BLOOM_ERROR_RATE); /* * Get info about the hash functions to be used for each hash key. Also @@ -602,6 +617,7 @@ ExecHashIncreaseNumBatches(HashJoinTable hashtable) long ninmemory; long nfreed; HashMemoryChunk oldchunks; + bool build_bloom_filter = false; /* do nothing if we've decided to shut off growth */ if (!hashtable->growEnabled) @@ -667,6 +683,36 @@ ExecHashIncreaseNumBatches(HashJoinTable hashtable) sizeof(HashJoinTuple) * hashtable->nbuckets); } + /* if we're switching to batched mode, we need to build the bloom filter */ + if (oldnbatch == 1) + { + /* + * We can't use outerNode->plan_rows here, firstly because we don't + * have access to it, but most importantly because it's inaccurate + * anyway (we've expected to do no batching based on the value). So + * we'll just use double the number of entries in the hash table. + * + * We also need to make sure we added the hash values into the bloom + * filter in this case (that's what build_bloom_filter is for). + * + * XXX Maybe we should be more pessimistic and use a higher values, + * in case we need to further increment the number of batches. + * + * XXX We also need to set some maximum number of tuples when the + * false positive rate gets too bad, and stop using the bloom + * filter if we reach it (we can't resize the filter). + * + * XXX There was a paper about adding a larger bloom filter once + * we fill the existing one, and using them at the same time. + * Might be worth implementing if the whole bloom filter idea + * works in general. + */ + hashtable->bloomFilter + = BloomFilterInit(2 * hashtable->totalTuples, BLOOM_ERROR_RATE); + + build_bloom_filter = true; + } + /* * We will scan through the chunks directly, so that we can reset the * buckets now and not have to keep track which tuples in the buckets have @@ -697,6 +743,9 @@ ExecHashIncreaseNumBatches(HashJoinTable hashtable) ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue, &bucketno, &batchno); + if (build_bloom_filter) + ExecHashBloomAddValue(hashtable, hashTuple->hashvalue); + if (batchno == curbatch) { /* keep tuple in memory - copy it into the new chunk */ @@ -1705,3 +1754,78 @@ dense_alloc(HashJoinTable hashtable, Size size) /* return pointer to the start of the tuple memory */ return ptr; } + +static void +ExecHashBloomAddValue(HashJoinTable hashtable, uint32 hashvalue) +{ + int i, byteIdx, bitIdx; + BloomFilter filter = hashtable->bloomFilter; + + if (! filter) + return; + + if (hashtable->curbatch > 0) + return; + + Assert(hashtable->nbatch > 1); /* nbatch=1 implies bloomData=NULL */ + + for (i = 0; i < filter->nhashes; i++) + { + uint32_t seed = i; + uint32_t hash = 0; + + MurmurHash3_x86_32(&hashvalue, sizeof(uint32), seed, &hash); + + hash = hash % filter->nbits; + + byteIdx = (hash / 8); + bitIdx = (hash % 8); + + filter->data[byteIdx] |= (0x01 << bitIdx); + } +} + +bool +ExecHashBloomCheckValue(HashJoinTable hashtable, uint32 hashvalue) +{ + int i, byteIdx, bitIdx; + BloomFilter filter = hashtable->bloomFilter; + + if (! filter) + return true; + + for (i = 0; i < filter->nhashes; i++) + { + uint32_t seed = i; + uint32_t hash = 0; + + MurmurHash3_x86_32(&hashvalue, sizeof(uint32), seed, &hash); + + hash = hash % filter->nbits; + + byteIdx = (hash / 8); + bitIdx = (hash % 8); + + if (! (filter->data[byteIdx] & (0x01 << bitIdx))) + return false; + } + + return true; +} + +static BloomFilter +BloomFilterInit(double nrows, double error) +{ + /* perhaps we should round nbits to multiples of 8 ? */ + int nbits = ceil((nrows * log(error)) / log(1.0 / (pow(2.0, log(2.0))))); + int nhashes = round(log(2.0) * nbits / nrows); + + BloomFilter filter = palloc0(offsetof(BloomFilterData, data) + ((nbits + 7) / 8)); + + filter->nbits = nbits; + filter->nhashes = nhashes; + + elog(WARNING, "bloom filter: %d bits (%d bytes), %d hashes", nbits, (nbits + 7) / 8, nhashes); + + return filter; +} diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c index 1d78cdf..708877e 100644 --- a/src/backend/executor/nodeHashjoin.c +++ b/src/backend/executor/nodeHashjoin.c @@ -48,7 +48,6 @@ static TupleTableSlot *ExecHashJoinGetSavedTuple(HashJoinState *hjstate, TupleTableSlot *tupleSlot); static bool ExecHashJoinNewBatch(HashJoinState *hjstate); - /* ---------------------------------------------------------------- * ExecHashJoin * @@ -210,6 +209,7 @@ ExecHashJoin(HashJoinState *node) outerTupleSlot = ExecHashJoinOuterGetTuple(outerNode, node, &hashvalue); + if (TupIsNull(outerTupleSlot)) { /* end of batch, or maybe whole join */ @@ -224,6 +224,19 @@ ExecHashJoin(HashJoinState *node) continue; } + /* If still in the first batch, we check the bloom filter. */ + if (hashtable->curbatch == 0) + { + node->hj_BloomLookups += 1; + + if (! ExecHashBloomCheckValue(hashtable, hashvalue)) + { + /* Loop around, staying in HJ_NEED_NEW_OUTER state */ + node->hj_BloomEliminated += 1; + continue; + } + } + econtext->ecxt_outertuple = outerTupleSlot; node->hj_MatchedOuter = false; @@ -423,6 +436,9 @@ ExecHashJoin(HashJoinState *node) (int) node->hj_JoinState); } } + + elog(WARNING, "bloom filter lookups=%lu eliminated=%lu", + node->hj_BloomLookups, node->hj_BloomEliminated); } /* ---------------------------------------------------------------- @@ -591,6 +607,9 @@ ExecInitHashJoin(HashJoin *node, EState *estate, int eflags) hjstate->hj_MatchedOuter = false; hjstate->hj_OuterNotEmpty = false; + hjstate->hj_BloomLookups = 0; + hjstate->hj_BloomEliminated = 0; + return hjstate; } @@ -629,6 +648,9 @@ ExecEndHashJoin(HashJoinState *node) */ ExecEndNode(outerPlanState(node)); ExecEndNode(innerPlanState(node)); + + elog(WARNING, "bloom filter lookups=%lu eliminated=%lu", + node->hj_BloomLookups, node->hj_BloomEliminated); } /* diff --git a/src/backend/utils/adt/Makefile b/src/backend/utils/adt/Makefile index 2cb7bab..365123b 100644 --- a/src/backend/utils/adt/Makefile +++ b/src/backend/utils/adt/Makefile @@ -16,7 +16,7 @@ OBJS = acl.o arrayfuncs.o array_expanded.o array_selfuncs.o \ float.o format_type.o formatting.o genfile.o \ geo_ops.o geo_selfuncs.o inet_cidr_ntop.o inet_net_pton.o int.o \ int8.o json.o jsonb.o jsonb_gin.o jsonb_op.o jsonb_util.o \ - jsonfuncs.o like.o lockfuncs.o mac.o misc.o nabstime.o name.o \ + jsonfuncs.o like.o lockfuncs.o mac.o misc.o murmur3.o nabstime.o name.o \ network.o network_gist.o network_selfuncs.o \ numeric.o numutils.o oid.o oracle_compat.o \ orderedsetaggs.o pg_locale.o pg_lsn.o pg_upgrade_support.o \ diff --git a/src/backend/utils/adt/murmur3.c b/src/backend/utils/adt/murmur3.c new file mode 100644 index 0000000..764aeab --- /dev/null +++ b/src/backend/utils/adt/murmur3.c @@ -0,0 +1,315 @@ +//----------------------------------------------------------------------------- +// MurmurHash3 was written by Austin Appleby, and is placed in the public +// domain. The author hereby disclaims copyright to this source code. + +// Note - The x86 and x64 versions do _not_ produce the same results, as the +// algorithms are optimized for their respective platforms. You can still +// compile and run any of them on any platform, but your performance with the +// non-native version will be less than optimal. + +#include "utils/murmur3.h" + +//----------------------------------------------------------------------------- +// Platform-specific functions and macros + +#ifdef __GNUC__ +#define FORCE_INLINE __attribute__((always_inline)) inline +#else +#define FORCE_INLINE inline +#endif + +static FORCE_INLINE uint32_t rotl32 ( uint32_t x, int8_t r ) +{ + return (x << r) | (x >> (32 - r)); +} + +static FORCE_INLINE uint64_t rotl64 ( uint64_t x, int8_t r ) +{ + return (x << r) | (x >> (64 - r)); +} + +#define ROTL32(x,y) rotl32(x,y) +#define ROTL64(x,y) rotl64(x,y) + +#define BIG_CONSTANT(x) (x##LLU) + +//----------------------------------------------------------------------------- +// Block read - if your platform needs to do endian-swapping or can only +// handle aligned reads, do the conversion here + +#define getblock(p, i) (p[i]) + +//----------------------------------------------------------------------------- +// Finalization mix - force all bits of a hash block to avalanche + +static FORCE_INLINE uint32_t fmix32 ( uint32_t h ) +{ + h ^= h >> 16; + h *= 0x85ebca6b; + h ^= h >> 13; + h *= 0xc2b2ae35; + h ^= h >> 16; + + return h; +} + +//---------- + +static FORCE_INLINE uint64_t fmix64 ( uint64_t k ) +{ + k ^= k >> 33; + k *= BIG_CONSTANT(0xff51afd7ed558ccd); + k ^= k >> 33; + k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53); + k ^= k >> 33; + + return k; +} + +//----------------------------------------------------------------------------- + +void MurmurHash3_x86_32 ( const void * key, int len, + uint32_t seed, void * out ) +{ + const uint8_t * data = (const uint8_t*)key; + const int nblocks = len / 4; + int i; + + uint32_t h1 = seed; + + uint32_t c1 = 0xcc9e2d51; + uint32_t c2 = 0x1b873593; + + //---------- + // body + + const uint32_t * blocks = (const uint32_t *)(data + nblocks*4); + + for(i = -nblocks; i; i++) + { + uint32_t k1 = getblock(blocks,i); + + k1 *= c1; + k1 = ROTL32(k1,15); + k1 *= c2; + + h1 ^= k1; + h1 = ROTL32(h1,13); + h1 = h1*5+0xe6546b64; + } + + //---------- + // tail + + const uint8_t * tail = (const uint8_t*)(data + nblocks*4); + + uint32_t k1 = 0; + + switch(len & 3) + { + case 3: k1 ^= tail[2] << 16; + case 2: k1 ^= tail[1] << 8; + case 1: k1 ^= tail[0]; + k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; + }; + + //---------- + // finalization + + h1 ^= len; + + h1 = fmix32(h1); + + *(uint32_t*)out = h1; +} + +//----------------------------------------------------------------------------- + +void MurmurHash3_x86_128 ( const void * key, const int len, + uint32_t seed, void * out ) +{ + const uint8_t * data = (const uint8_t*)key; + const int nblocks = len / 16; + int i; + + uint32_t h1 = seed; + uint32_t h2 = seed; + uint32_t h3 = seed; + uint32_t h4 = seed; + + uint32_t c1 = 0x239b961b; + uint32_t c2 = 0xab0e9789; + uint32_t c3 = 0x38b34ae5; + uint32_t c4 = 0xa1e38b93; + + //---------- + // body + + const uint32_t * blocks = (const uint32_t *)(data + nblocks*16); + + for(i = -nblocks; i; i++) + { + uint32_t k1 = getblock(blocks,i*4+0); + uint32_t k2 = getblock(blocks,i*4+1); + uint32_t k3 = getblock(blocks,i*4+2); + uint32_t k4 = getblock(blocks,i*4+3); + + k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; + + h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b; + + k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; + + h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747; + + k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; + + h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35; + + k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; + + h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17; + } + + //---------- + // tail + + const uint8_t * tail = (const uint8_t*)(data + nblocks*16); + + uint32_t k1 = 0; + uint32_t k2 = 0; + uint32_t k3 = 0; + uint32_t k4 = 0; + + switch(len & 15) + { + case 15: k4 ^= tail[14] << 16; + case 14: k4 ^= tail[13] << 8; + case 13: k4 ^= tail[12] << 0; + k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; + + case 12: k3 ^= tail[11] << 24; + case 11: k3 ^= tail[10] << 16; + case 10: k3 ^= tail[ 9] << 8; + case 9: k3 ^= tail[ 8] << 0; + k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; + + case 8: k2 ^= tail[ 7] << 24; + case 7: k2 ^= tail[ 6] << 16; + case 6: k2 ^= tail[ 5] << 8; + case 5: k2 ^= tail[ 4] << 0; + k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; + + case 4: k1 ^= tail[ 3] << 24; + case 3: k1 ^= tail[ 2] << 16; + case 2: k1 ^= tail[ 1] << 8; + case 1: k1 ^= tail[ 0] << 0; + k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; + }; + + //---------- + // finalization + + h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; + + h1 += h2; h1 += h3; h1 += h4; + h2 += h1; h3 += h1; h4 += h1; + + h1 = fmix32(h1); + h2 = fmix32(h2); + h3 = fmix32(h3); + h4 = fmix32(h4); + + h1 += h2; h1 += h3; h1 += h4; + h2 += h1; h3 += h1; h4 += h1; + + ((uint32_t*)out)[0] = h1; + ((uint32_t*)out)[1] = h2; + ((uint32_t*)out)[2] = h3; + ((uint32_t*)out)[3] = h4; +} + +//----------------------------------------------------------------------------- + +void MurmurHash3_x64_128 ( const void * key, const int len, + const uint32_t seed, void * out ) +{ + const uint8_t * data = (const uint8_t*)key; + const int nblocks = len / 16; + int i; + + uint64_t h1 = seed; + uint64_t h2 = seed; + + uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5); + uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f); + + //---------- + // body + + const uint64_t * blocks = (const uint64_t *)(data); + + for(i = 0; i < nblocks; i++) + { + uint64_t k1 = getblock(blocks,i*2+0); + uint64_t k2 = getblock(blocks,i*2+1); + + k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; + + h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729; + + k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; + + h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5; + } + + //---------- + // tail + + const uint8_t * tail = (const uint8_t*)(data + nblocks*16); + + uint64_t k1 = 0; + uint64_t k2 = 0; + + switch(len & 15) + { + case 15: k2 ^= (uint64_t)(tail[14]) << 48; + case 14: k2 ^= (uint64_t)(tail[13]) << 40; + case 13: k2 ^= (uint64_t)(tail[12]) << 32; + case 12: k2 ^= (uint64_t)(tail[11]) << 24; + case 11: k2 ^= (uint64_t)(tail[10]) << 16; + case 10: k2 ^= (uint64_t)(tail[ 9]) << 8; + case 9: k2 ^= (uint64_t)(tail[ 8]) << 0; + k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; + + case 8: k1 ^= (uint64_t)(tail[ 7]) << 56; + case 7: k1 ^= (uint64_t)(tail[ 6]) << 48; + case 6: k1 ^= (uint64_t)(tail[ 5]) << 40; + case 5: k1 ^= (uint64_t)(tail[ 4]) << 32; + case 4: k1 ^= (uint64_t)(tail[ 3]) << 24; + case 3: k1 ^= (uint64_t)(tail[ 2]) << 16; + case 2: k1 ^= (uint64_t)(tail[ 1]) << 8; + case 1: k1 ^= (uint64_t)(tail[ 0]) << 0; + k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; + }; + + //---------- + // finalization + + h1 ^= len; h2 ^= len; + + h1 += h2; + h2 += h1; + + h1 = fmix64(h1); + h2 = fmix64(h2); + + h1 += h2; + h2 += h1; + + ((uint64_t*)out)[0] = h1; + ((uint64_t*)out)[1] = h2; +} + +//----------------------------------------------------------------------------- + diff --git a/src/include/executor/hashjoin.h b/src/include/executor/hashjoin.h index 7a51ea6..f2bee7f 100644 --- a/src/include/executor/hashjoin.h +++ b/src/include/executor/hashjoin.h @@ -72,6 +72,15 @@ typedef struct HashJoinTupleData #define HJTUPLE_MINTUPLE(hjtup) \ ((MinimalTuple) ((char *) (hjtup) + HJTUPLE_OVERHEAD)) +typedef struct BloomFilterData +{ + int nbits; /* m */ + int nhashes; /* k */ + char data[1]; /* bits */ +} BloomFilterData; + +typedef BloomFilterData *BloomFilter; + /* * If the outer relation's distribution is sufficiently nonuniform, we attempt * to optimize the join by treating the hash values corresponding to the outer @@ -186,6 +195,11 @@ typedef struct HashJoinTableData /* used for dense allocation of tuples (into linked chunks) */ HashMemoryChunk chunks; /* one list for the whole batch */ + + /* used only when the hash join has multiple batches */ + BloomFilter bloomFilter; /* bloom filter on the hash values */ } HashJoinTableData; +bool ExecHashBloomCheckValue(HashJoinTable hashtable, uint32 hashvalue); + #endif /* HASHJOIN_H */ diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 5ccf470..e4660bd 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -1764,6 +1764,10 @@ typedef struct HashJoinState int hj_JoinState; bool hj_MatchedOuter; bool hj_OuterNotEmpty; + + /* debugging and profiling of bloom filters */ + uint64 hj_BloomLookups; + uint64 hj_BloomEliminated; } HashJoinState; diff --git a/src/include/utils/murmur3.h b/src/include/utils/murmur3.h new file mode 100644 index 0000000..e12bf08 --- /dev/null +++ b/src/include/utils/murmur3.h @@ -0,0 +1,29 @@ +//----------------------------------------------------------------------------- +// MurmurHash3 was written by Austin Appleby, and is placed in the +// public domain. The author hereby disclaims copyright to this source +// code. + +#ifndef _MURMURHASH3_H_ +#define _MURMURHASH3_H_ + +#include + +#ifdef __cplusplus +extern "C" { +#endif + +//----------------------------------------------------------------------------- + +void MurmurHash3_x86_32 (const void *key, int len, uint32_t seed, void *out); + +void MurmurHash3_x86_128(const void *key, int len, uint32_t seed, void *out); + +void MurmurHash3_x64_128(const void *key, int len, uint32_t seed, void *out); + +//----------------------------------------------------------------------------- + +#ifdef __cplusplus +} +#endif + +#endif // _MURMURHASH3_H_