pg.ddx.io pgsql-hackers@postgresql.org mailing list archive
help / color / mirror / Atom feedWIP: bloom filter in Hash Joins with batches
26+ messages / 8 participants
[nested] [flat]
* WIP: bloom filter in Hash Joins with batches
@ 2015-12-15 22:30 Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 6 replies; 26+ messages in thread
From: Tomas Vondra @ 2015-12-15 22:30 UTC (permalink / raw)
To: pgsql-hackers
Hi,
while working on the Hash Join improvements, I've been repeatedly
running into the idea of bloom filter - various papers on hash joins
mention bloom filters as a way to optimize access to the hash table by
doing fewer lookups, etc.
Sadly, I've been unable to actually see any real benefit of using a
bloom filter, which I believe is mostly due to NTUP_PER_BUCKET=1, which
makes the lookups much more efficient (so the room for bloom filter
improvements is narrow).
The one case where bloom filter might still help, and that's when the
bloom filter fits into L3 cache (a few MBs) while the hash table (or
more accurately the buckets) do not. Then there's a chance that the
bloom filter (which needs to do multiple lookups) might help.
But I think there's another case where bloom filter might be way more
useful in Hash Join - when we do batching. What we do currently is that
we simply
1) build the batches for the hash table (inner relation)
2) read the outer relation (usually the larger one), and split it
into batches just like the hash table
3) while doing (2) we join the first batch, and write the remaining
batches to disk (temporary files)
4) we read the batches one by one (for both tables) and do the join
Now, imagine that only some of the rows in the outer table actually
match a row in the hash table. Currently, we do write those rows into
the temporary file, but with a bloom filter on the whole hash table (all
the batches at once) we can skip that for some types of joins.
For inner join we can immediately discard the outer row, for left join
we can immediately output the row. In both cases we can completely
eliminate the overhead with writing the tuple to the temporary file and
then reading it again.
The attached patch is a PoC of this approach - I'm pretty sure it's not
perfectly correct (e.g. I only tried it with inner join), but it's good
enough for demonstrating the benefits. It's rather incomplete (see the
end of this e-mail), and I'm mostly soliciting some early feedback at
this point.
The numbers presented here are for a test case like this:
CREATE TABLE dim (id INT, dval TEXT);
CREATE TABLE fact (id INT, fval TEXT);
INSERT INTO dim SELECT i, md5(i::text)
FROM generate_series(1,10000000) s(i);
-- repeat 10x
INSERT INTO fact SELECT * FROM dim;
and a query like this
SELECT COUNT(fval) FROM fact JOIN dim USING (id) WHERE dval < 'a';
with different values in the WHERE condition to select a fraction of the
inner 'dim' table - this directly affects what portion of the 'fact'
table has a matching row, and also the size of the hash table (and
number of batches).
Now, some numbers from a machine with 8GB of RAM (the 'fact' table has
~6.5GB of data, so there's actually quite a bit of memory pressure,
forcing the temp files to disk etc.).
With work_mem=16MB, it looks like this:
batches filter select. bloom master bloom/master
-----------------------------------------------------------
4 1 6.25% 23871 48631 49.09%
8 2 12.50% 25752 56692 45.42%
8 3 18.75% 31273 57455 54.43%
16 4 25.01% 37430 62325 60.06%
16 5 31.25% 39005 61143 63.79%
16 6 37.50% 46157 63533 72.65%
16 7 43.75% 53500 65483 81.70%
32 8 49.99% 53952 65730 82.08%
32 9 56.23% 55187 67521 81.73%
32 a 62.49% 64454 69448 92.81%
32 b 68.73% 66937 71692 93.37%
32 c 74.97% 73323 72060 101.75%
32 d 81.23% 76703 73513 104.34%
32 e 87.48% 81970 74890 109.45%
32 f 93.74% 86102 76257 112.91%
The 'batches' means how many batches were used for the join, 'filter' is
the value used in the WHERE condition, selectivity is the fraction of
the 'dim' table that matches the condition (and also the 'fact'). Bloom
and master are timings of the query in miliseconds, and bloom/master is
comparison of the runtimes - so for example 49% means the hash join with
bloom filter was running ~2x as fast.
Admittedly, work_mem=16MB is quite low, but that's just a way to force
batching. What really matters is the number of batches and selectivity
(how many tuples we can eliminate using the bloom filter).
For work_mem=64MB it looks like this:
batches filter select. bloom master bloom/master
-----------------------------------------------------------
1 1 6.25% 24846 23854 104.16%
2 2 12.50% 24369 45672 53.36%
2 3 18.75% 30432 47454 64.13%
4 4 25.01% 36175 59741 60.55%
4 5 31.25% 43103 62631 68.82%
4 6 37.50% 48179 64079 75.19%
So initially it's a bit slower (it's not doing any batching in this
case, but the code is a bit silly and while not building the bloom
filter it still does some checks). But once we start batching, it gets
2x as fast again, and then slowly degrades as the selectivity increases.
Attached is a spreadsheet with results for various work_mem values, and
also with a smaller data set (just 30M rows in the fact table), which
easily fits into memory. Yet it shows similar gains, shaving off ~40% in
the best case, suggesting that this is not just thanks to reduction of
I/O when forcing the temp files to disk.
As I mentioned, the patch is incomplete in several ways:
1) It does not count the bloom filter (which may be quite big) into
work_mem properly.
2) It probably does not work for outer joins at this point.
3) Currently the bloom filter is used whenever we do batching, but it
should really be driven by selectivity too - it'd be good to (a)
estimate the fraction of 'fact' tuples having a match in the hash
table, and not to do bloom if it's over ~60% or so. Also, maybe
the could should count the matches at runtime, and disable the
bloom filter if we reach some threshold.
But overall, this seems like a nice optimization opportunity for hash
joins on large data sets, where batching is necessary.
Ideas?
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
hashjoin-bloom.sql (application/sql, 398B) download
bloom-hashjoin-v1.patch (text/x-diff, 18.6K) download
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 <stdint.h>
+
+#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_
hashjoin-bloom.png (image/png, 30.0K) download
view image
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-17 09:50 Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
5 siblings, 1 reply; 26+ messages in thread
From: Shulgin, Oleksandr @ 2015-12-17 09:50 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers
On Tue, Dec 15, 2015 at 11:30 PM, Tomas Vondra <tomas.vondra@2ndquadrant.com
> wrote:
>
> Attached is a spreadsheet with results for various work_mem values, and
> also with a smaller data set (just 30M rows in the fact table), which
> easily fits into memory. Yet it shows similar gains, shaving off ~40% in
> the best case, suggesting that this is not just thanks to reduction of I/O
> when forcing the temp files to disk.
A neat idea! Have you possibly tried to also collect statistics about
actual false-positive rates and filter allocation sizes in every of the
collected data points?
--
Alex
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-17 10:44 Simon Riggs <simon@2ndQuadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
5 siblings, 1 reply; 26+ messages in thread
From: Simon Riggs @ 2015-12-17 10:44 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers
On 15 December 2015 at 22:30, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
3) Currently the bloom filter is used whenever we do batching, but it
> should really be driven by selectivity too - it'd be good to (a)
> estimate the fraction of 'fact' tuples having a match in the hash
> table, and not to do bloom if it's over ~60% or so. Also, maybe
> the could should count the matches at runtime, and disable the
> bloom filter if we reach some threshold.
>
Cool results.
It seems a good idea to build the bloom filter always, then discard it if
it would be ineffective.
My understanding is that the bloom filter would be ineffective in any of
these cases
* Hash table is too small
* Bloom filter too large
* Bloom selectivity > 50% - perhaps that can be applied dynamically, so
stop using it if it becomes ineffective
--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/;
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-17 15:34 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>
0 siblings, 1 reply; 26+ messages in thread
From: Tomas Vondra @ 2015-12-17 15:34 UTC (permalink / raw)
To: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>; +Cc: pgsql-hackers
Hi,
On 12/17/2015 10:50 AM, Shulgin, Oleksandr wrote:
> On Tue, Dec 15, 2015 at 11:30 PM, Tomas Vondra
> <tomas.vondra@2ndquadrant.com <mailto:tomas.vondra@2ndquadrant.com>> wrote:
>
>> Attached is a spreadsheet with results for various work_mem
>> values, and also with a smaller data set (just 30M rows in the fact
>> table), which easily fits into memory. Yet it shows similar gains,
>> shaving off ~40% in the best case, suggesting that this is not just
>> thanks to reduction of I/O when forcing the temp files to disk.
>
> A neat idea! Have you possibly tried to also collect statistics
> about actual false-positive rates and filter allocation sizes in
> every of the collected data points?
The patch counts and prints the total number of lookups, and the number
of eliminated rows. The bloom filter is currently sized for 5% false
positives rate, and the numbers I've seen match that.
I think ultimately we'll need to measure the false positive rate, so
that we can use it to dynamically disable the bloom filter if it gets
inefficient. Also maybe put some of that into EXPLAIN ANALYZE.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-17 16:00 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
0 siblings, 1 reply; 26+ messages in thread
From: Tomas Vondra @ 2015-12-17 16:00 UTC (permalink / raw)
To: Simon Riggs <simon@2ndQuadrant.com>; +Cc: pgsql-hackers
On 12/17/2015 11:44 AM, Simon Riggs wrote:
>
> My understanding is that the bloom filter would be ineffective in any of
> these cases
> * Hash table is too small
Yes, although it depends what you mean by "too small".
Essentially if we can do with a single batch, then it's cheaper to do a
single lookup in the hash table instead of multiple lookups in the bloom
filter. The bloom filter might still win if it fits into L3 cache, but
that seems rather unlikely.
> * Bloom filter too large
Too large with respect to what?
One obvious problem is that the bloom filter is built for all batches at
once, i.e. for all tuples, so it may be so big won't fit into work_mem
(or takes a significant part of it). Currently it's not accounted for,
but that'll need to change.
> * Bloom selectivity > 50% - perhaps that can be applied dynamically,
> so stop using it if it becomes ineffective
Yes. I think doing some preliminary selectivity estimation should not be
difficult - that's pretty much what calc_joinrel_size_estimate() already
does.
Doing that at dynamically is also possible, but quite tricky. Imagine
for example the outer relation is sorted - in that case we may get long
sequences of the same value (hash), and all of them will either have a
match in the inner relation, or not have a match. That may easily skew
the counters used for disabling the bloom filter dynamically.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-20 04:46 Oleg Bartunov <obartunov@gmail.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
5 siblings, 1 reply; 26+ messages in thread
From: Oleg Bartunov @ 2015-12-20 04:46 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers
Tomas,
have you seen
http://www.postgresql.org/message-id/4B4DD67F.9010506@sigaev.ru
I have very limited internet connection (no graphics) , so I may miss
something
Oleg
On Wed, Dec 16, 2015 at 4:15 AM, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
> Hi,
>
> while working on the Hash Join improvements, I've been repeatedly running
> into the idea of bloom filter - various papers on hash joins mention bloom
> filters as a way to optimize access to the hash table by doing fewer
> lookups, etc.
>
> Sadly, I've been unable to actually see any real benefit of using a bloom
> filter, which I believe is mostly due to NTUP_PER_BUCKET=1, which makes the
> lookups much more efficient (so the room for bloom filter improvements is
> narrow).
>
> The one case where bloom filter might still help, and that's when the
> bloom filter fits into L3 cache (a few MBs) while the hash table (or more
> accurately the buckets) do not. Then there's a chance that the bloom filter
> (which needs to do multiple lookups) might help.
>
> But I think there's another case where bloom filter might be way more
> useful in Hash Join - when we do batching. What we do currently is that we
> simply
>
> 1) build the batches for the hash table (inner relation)
>
> 2) read the outer relation (usually the larger one), and split it
> into batches just like the hash table
>
> 3) while doing (2) we join the first batch, and write the remaining
> batches to disk (temporary files)
>
> 4) we read the batches one by one (for both tables) and do the join
>
> Now, imagine that only some of the rows in the outer table actually match
> a row in the hash table. Currently, we do write those rows into the
> temporary file, but with a bloom filter on the whole hash table (all the
> batches at once) we can skip that for some types of joins.
>
> For inner join we can immediately discard the outer row, for left join we
> can immediately output the row. In both cases we can completely eliminate
> the overhead with writing the tuple to the temporary file and then reading
> it again.
>
> The attached patch is a PoC of this approach - I'm pretty sure it's not
> perfectly correct (e.g. I only tried it with inner join), but it's good
> enough for demonstrating the benefits. It's rather incomplete (see the end
> of this e-mail), and I'm mostly soliciting some early feedback at this
> point.
>
> The numbers presented here are for a test case like this:
>
> CREATE TABLE dim (id INT, dval TEXT);
> CREATE TABLE fact (id INT, fval TEXT);
>
> INSERT INTO dim SELECT i, md5(i::text)
> FROM generate_series(1,10000000) s(i);
>
> -- repeat 10x
> INSERT INTO fact SELECT * FROM dim;
>
> and a query like this
>
> SELECT COUNT(fval) FROM fact JOIN dim USING (id) WHERE dval < 'a';
>
> with different values in the WHERE condition to select a fraction of the
> inner 'dim' table - this directly affects what portion of the 'fact' table
> has a matching row, and also the size of the hash table (and number of
> batches).
>
> Now, some numbers from a machine with 8GB of RAM (the 'fact' table has
> ~6.5GB of data, so there's actually quite a bit of memory pressure, forcing
> the temp files to disk etc.).
>
> With work_mem=16MB, it looks like this:
>
> batches filter select. bloom master bloom/master
> -----------------------------------------------------------
> 4 1 6.25% 23871 48631 49.09%
> 8 2 12.50% 25752 56692 45.42%
> 8 3 18.75% 31273 57455 54.43%
> 16 4 25.01% 37430 62325 60.06%
> 16 5 31.25% 39005 61143 63.79%
> 16 6 37.50% 46157 63533 72.65%
> 16 7 43.75% 53500 65483 81.70%
> 32 8 49.99% 53952 65730 82.08%
> 32 9 56.23% 55187 67521 81.73%
> 32 a 62.49% 64454 69448 92.81%
> 32 b 68.73% 66937 71692 93.37%
> 32 c 74.97% 73323 72060 101.75%
> 32 d 81.23% 76703 73513 104.34%
> 32 e 87.48% 81970 74890 109.45%
> 32 f 93.74% 86102 76257 112.91%
>
> The 'batches' means how many batches were used for the join, 'filter' is
> the value used in the WHERE condition, selectivity is the fraction of the
> 'dim' table that matches the condition (and also the 'fact'). Bloom and
> master are timings of the query in miliseconds, and bloom/master is
> comparison of the runtimes - so for example 49% means the hash join with
> bloom filter was running ~2x as fast.
>
> Admittedly, work_mem=16MB is quite low, but that's just a way to force
> batching. What really matters is the number of batches and selectivity (how
> many tuples we can eliminate using the bloom filter).
>
> For work_mem=64MB it looks like this:
>
> batches filter select. bloom master bloom/master
> -----------------------------------------------------------
> 1 1 6.25% 24846 23854 104.16%
> 2 2 12.50% 24369 45672 53.36%
> 2 3 18.75% 30432 47454 64.13%
> 4 4 25.01% 36175 59741 60.55%
> 4 5 31.25% 43103 62631 68.82%
> 4 6 37.50% 48179 64079 75.19%
>
> So initially it's a bit slower (it's not doing any batching in this case,
> but the code is a bit silly and while not building the bloom filter it
> still does some checks). But once we start batching, it gets 2x as fast
> again, and then slowly degrades as the selectivity increases.
>
> Attached is a spreadsheet with results for various work_mem values, and
> also with a smaller data set (just 30M rows in the fact table), which
> easily fits into memory. Yet it shows similar gains, shaving off ~40% in
> the best case, suggesting that this is not just thanks to reduction of I/O
> when forcing the temp files to disk.
>
> As I mentioned, the patch is incomplete in several ways:
>
> 1) It does not count the bloom filter (which may be quite big) into
> work_mem properly.
>
> 2) It probably does not work for outer joins at this point.
>
> 3) Currently the bloom filter is used whenever we do batching, but it
> should really be driven by selectivity too - it'd be good to (a)
> estimate the fraction of 'fact' tuples having a match in the hash
> table, and not to do bloom if it's over ~60% or so. Also, maybe
> the could should count the matches at runtime, and disable the
> bloom filter if we reach some threshold.
>
> But overall, this seems like a nice optimization opportunity for hash
> joins on large data sets, where batching is necessary.
>
> Ideas?
>
> --
> Tomas Vondra http://www.2ndQuadrant.com
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>
>
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-20 17:18 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Oleg Bartunov <obartunov@gmail.com>
0 siblings, 0 replies; 26+ messages in thread
From: Tomas Vondra @ 2015-12-20 17:18 UTC (permalink / raw)
To: obartunov@gmail.com; +Cc: pgsql-hackers
Hi,
On 12/20/2015 05:46 AM, Oleg Bartunov wrote:
> Tomas,
>
> have you seen
> http://www.postgresql.org/message-id/4B4DD67F.9010506@sigaev.ru
> I have very limited internet connection (no graphics) , so I may miss
> something
I haven't seen that, but I don't really see how that's related - your
post is about indexes, mine is about building temporary bloom filters
when executing hash joins.
FWIW, I think bloom filters should be easy to add to BRIN indexes, as
another type of 'summary'. That should address most of the missing
pieces in your implementation (e.g. WAL).
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-24 11:43 Aleksander Alekseev <a.alekseev@postgrespro.ru>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
5 siblings, 0 replies; 26+ messages in thread
From: Aleksander Alekseev @ 2015-12-24 11:43 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers
Hello, Tomas.
Great idea!
Did you consider to cache bloom filter or at least part(s) of it
somehow? I think this way we could gain some more TPS. This of course
assuming that creating a bloom filter is really a bottleneck here,
which would be nice be investigated first.
Best regards,
Aleksander
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-24 13:51 Simon Riggs <simon@2ndQuadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 2 replies; 26+ messages in thread
From: Simon Riggs @ 2015-12-24 13:51 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
On 17 December 2015 at 16:00, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
> On 12/17/2015 11:44 AM, Simon Riggs wrote:
>
>>
>> My understanding is that the bloom filter would be ineffective in any of
>> these cases
>> * Hash table is too small
>>
>
> Yes, although it depends what you mean by "too small".
>
> Essentially if we can do with a single batch, then it's cheaper to do a
> single lookup in the hash table instead of multiple lookups in the bloom
> filter. The bloom filter might still win if it fits into L3 cache, but that
> seems rather unlikely.
>
> * Bloom filter too large
>>
>
> Too large with respect to what?
>
> One obvious problem is that the bloom filter is built for all batches at
> once, i.e. for all tuples, so it may be so big won't fit into work_mem (or
> takes a significant part of it). Currently it's not accounted for, but
> that'll need to change.
The benefit seems to be related to cacheing, or at least that memory speed
is critical. If the hash table is too small, or the bloom filter too large
then there would be no benefit from performing the action (Lookup Bloom
then maybe Lookup Hash) compared with just doing (LookupHash).
So the objective must be to get a Bloom Filter that is small enough that it
lives in a higher/faster level of cache than the main Hash table. Or
possibly that we separate that into a two stage process so that the first
level can be applied by a GPU and then later checked against hash outside
of a GPU.
I think you also need to consider whether we use a hash bloom filter or
just simply apply an additional range predicate. The latter idea is similar
to my earlier thoughts here
http://www.postgresql.org/message-id/CA+U5nMLYf2cgbq+YUw-ArLBTcPrqanBf5QiFEC-PBRJCFzOngg@mail.gmail....
--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/;
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-24 16:55 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
1 sibling, 0 replies; 26+ messages in thread
From: Tomas Vondra @ 2015-12-24 16:55 UTC (permalink / raw)
To: Simon Riggs <simon@2ndQuadrant.com>; +Cc: pgsql-hackers
On 12/24/2015 02:51 PM, Simon Riggs wrote:
> On 17 December 2015 at 16:00, Tomas Vondra <tomas.vondra@2ndquadrant.com
> <mailto:tomas.vondra@2ndquadrant.com>> wrote:
>
> On 12/17/2015 11:44 AM, Simon Riggs wrote:
>
>
> My understanding is that the bloom filter would be ineffective
> in any of
> these cases
> * Hash table is too small
>
>
> Yes, although it depends what you mean by "too small".
>
> Essentially if we can do with a single batch, then it's cheaper to
> do a single lookup in the hash table instead of multiple lookups in
> the bloom filter. The bloom filter might still win if it fits into
> L3 cache, but that seems rather unlikely.
>
> * Bloom filter too large
>
>
> Too large with respect to what?
>
> One obvious problem is that the bloom filter is built for all
> batches at once, i.e. for all tuples, so it may be so big won't fit
> into work_mem (or takes a significant part of it). Currently it's
> not accounted for, but that'll need to change.
>
>
> The benefit seems to be related to cacheing, or at least that memory
> speed is critical. If the hash table is too small, or the bloom
> filter too large then there would be no benefit from performing the
> action (Lookup Bloom then maybe Lookup Hash) compared with just
> doing(LookupHash).
>
> So the objective must be to get a Bloom Filter that is small enough
> that it lives in a higher/faster level of cache than the main Hash
> table. Or possibly that we separate that into a two stage process so
> that the first level can be applied by a GPU and then later checked
> against hash outside of a GPU.
I don't think that's quite true.
Had the primary goal been to replace expensive hashtable lookups with
cheap bloom filter checks, then sure - the size of the bloom filter
would be crucial (namely getting the whole bloom filter into L3, which
is an order of magnitude faster compared to RAM).
But that's not what the patch does - it aims to reduce the amount of
data that need to be serialized/deserialized when batching is necessary,
trading those costs for the bloom overhead. The size of the bloom filter
may still matter, but it's way less important because the
(de)serialization overhead is much more expensive than the hash lookup.
FWIW I've been trying to use the bloom filters in the "traditional" way
(doing "cheap" bloom checks before hashtable lookups), but I've been
unable to get any measurable benefit. Either I was doing it wrong
somehow, or perhaps NTUP_PER_BUCKET=1 made the hashtable too fast (it
essentially means we need a single lookup to see if the entry exists,
while bloom filter needs several lookups, depending on the desired false
positive ratio).
So I concluded that the attempt to use the bloom filter that way is
futile, and that the batching case seems like the only scenario where
the bloom filters may still be useful.
There's a number of additional problems with sizing the bloom filter to
fit into L3:
(1) We have no idea how much L3 there is, although this might be fixed
by either adding a GUC, read it from /proc/cpuinfo or just use some
reasonable default (say, most Xeon CPUs today have ~20 MB)
(2) The L3 is not per-process, but shared by all processes, so we don't
really have all the L3, but perhaps just L3/N where N is the number
of backends.
(3) The size of the bloom filter depends on the number of items it
should handle and false positive rate. I've used 5% in the patch,
but maybe it'd make sense to increase this in order to get smaller
filter?
Also, the bloom filter does not compete with the whole hash table, but
"just" with the "buckets" as that's sufficient to determine if there's a
tuple for a key or not.
Let's do some math for a hash table with 100k rows (so a fairly small
hash table):
* nbuckets = 131072 (2^17), so 1MB
* bloom filter (5% false positive rate [1]): 76kB, k=4 (see [1])
So both the buckets and bloom fit into L3, and the bloom filter is
unlikely to speed things up.
The difference between buckets and bloom filter is about 10x, and both
sizes scale about linearly (with 1M items it'll be ~10MB vs. 760kB), so
there clearly is an area where bloom filter fits into L3 while buckets
don't.
Sadly I haven't been able to exploit that, but I'll try again.
In any case, none of this can help unless the bloom filter really
eliminates many lookups.
[1] http://hur.st/bloomfilter?n=100000&p=0.05
>
> I think you also need to consider whether we use a hash bloom filter or
> just simply apply an additional range predicate. The latter idea is
> similar to my earlier thoughts here
> http://www.postgresql.org/message-id/CA+U5nMLYf2cgbq+YUw-ArLBTcPrqanBf5QiFEC-PBRJCFzOngg@mail.gmail....
Interesting, but I don't really see how this is related to bloom filters?
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-28 02:15 David Rowley <david.rowley@2ndquadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 1 reply; 26+ messages in thread
From: David Rowley @ 2015-12-28 02:15 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>; pgsql-hackers
On 18 December 2015 at 04:34, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
> I think ultimately we'll need to measure the false positive rate, so that
> we can use it to dynamically disable the bloom filter if it gets
> inefficient. Also maybe put some of that into EXPLAIN ANALYZE.
>
I'm not so convinced that will be a good idea. What if the filter does not
help much to start with, we disable it because of that, then we get some
different probe values later in the scan which the bloom filter would have
helped to eliminate earlier.
Maybe it would be better to, once the filter is built, simply count the
number of 1 bits and only use the filter if there's less than <threshold> 1
bits compared to the size of the filter in bits. There's functionality in
bms_num_members() to do this, and there's also __builtin_popcount() in
newer version of GCC, which we could have some wrapper around, perhaps.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-28 10:23 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: David Rowley <david.rowley@2ndquadrant.com>
0 siblings, 1 reply; 26+ messages in thread
From: Tomas Vondra @ 2015-12-28 10:23 UTC (permalink / raw)
To: David Rowley <david.rowley@2ndquadrant.com>; +Cc: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>; pgsql-hackers
On 12/28/2015 03:15 AM, David Rowley wrote:
> On 18 December 2015 at 04:34, Tomas Vondra <tomas.vondra@2ndquadrant.com
> <mailto:tomas.vondra@2ndquadrant.com>> wrote:
>
> I think ultimately we'll need to measure the false positive rate, so
> that we can use it to dynamically disable the bloom filter if it
> gets inefficient. Also maybe put some of that into EXPLAIN ANALYZE.
>
>
> I'm not so convinced that will be a good idea. What if the filter does
> not help much to start with, we disable it because of that, then we get
> some different probe values later in the scan which the bloom filter
> would have helped to eliminate earlier.
Yes, that's true. This might happen quite easily for example when then
outer table is sorted - in that case what we'll see are (possibly long)
sequences of the same value, which might bias the decision quite easily.
I don't know how to fix this perfectly (if at all possible). But maybe
we don't really need to do that. The overall goal is to improve the
overall performance, and this check (disabling the bloom filter) is
meant to limit the loss when the filter returns "true" for most values
(making it somewhat pointless).
The costs however are asymmetric - once we build the hash table (and
build the filter), the cost for dropping the bloom filter is constant,
as we simply loose the time we spent building it. But the cost for
continuing to use of inefficient filter is O(N) where N is the number of
lookups (i.e. rows of outer table). So it's probably better to drop the
filter a bit too early and sacrifice the small amount of time we spent
building it, so that we have a change of not being much slower than the
current implementation.
That is not to say we can't come up with better solutions - for example
we can count (or estimate) the number of distinct hash values we've
seen, and only do the decision once we see enough of them. For example
we could use HyperLogLog to do that, or simply see the number of times a
value changed (hash value not equal to the previous value). That should
be better than simply waiting to X lookups, but I'm sure it's still
possible to come up with counter-examples.
>
> Maybe it would be better to, once the filter is built, simply count the
> number of 1 bits and only use the filter if there's less than
> <threshold> 1 bits compared to the size of the filter in bits. There's
> functionality in bms_num_members() to do this, and there's
> also __builtin_popcount() in newer version of GCC, which we could have
> some wrapper around, perhaps.
I don't really see how this is relevant with the previous point. The
number of 1s in the bitmap can tell you the false positive rate for the
bloom filter, not what fraction of lookups will be answered with "true".
So while this needs to be watched, so that we stop using the bloom
filter when it gets too full (e.g. due to under-estimate), it's
completely unrelated to the previous issue.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-28 10:38 David Rowley <david.rowley@2ndquadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 1 reply; 26+ messages in thread
From: David Rowley @ 2015-12-28 10:38 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>; pgsql-hackers
On 28 December 2015 at 23:23, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
> On 12/28/2015 03:15 AM, David Rowley wrote:
>
>> Maybe it would be better to, once the filter is built, simply count the
>>
> number of 1 bits and only use the filter if there's less than
>> <threshold> 1 bits compared to the size of the filter in bits. There's
>> functionality in bms_num_members() to do this, and there's
>> also __builtin_popcount() in newer version of GCC, which we could have
>> some wrapper around, perhaps.
>>
>
> I don't really see how this is relevant with the previous point. The
> number of 1s in the bitmap can tell you the false positive rate for the
> bloom filter, not what fraction of lookups will be answered with "true".
>
> So while this needs to be watched, so that we stop using the bloom filter
> when it gets too full (e.g. due to under-estimate), it's completely
> unrelated to the previous issue.
Why is it not related? this has got me confused. If a bloom filter has all
of the bits set to 1, then it will never filter any Tuples right?
If so, then a filter with all 1 bits set should be thrown away, as it'll
never help us, and the filter should generally become more worthwhile as it
contains a higher ratio of 0 bits vs 1 bits. Of course we don't have a
count of how many Tuples matched each bit, so this is based on the
assumption that each bit matches an equal number of Tuples. Are you saying
this is not an assumption that we should make?
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-28 10:44 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: David Rowley <david.rowley@2ndquadrant.com>
0 siblings, 1 reply; 26+ messages in thread
From: Tomas Vondra @ 2015-12-28 10:44 UTC (permalink / raw)
To: David Rowley <david.rowley@2ndquadrant.com>; +Cc: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>; pgsql-hackers
On 12/28/2015 11:38 AM, David Rowley wrote:
> On 28 December 2015 at 23:23, Tomas Vondra <tomas.vondra@2ndquadrant.com
> <mailto:tomas.vondra@2ndquadrant.com>> wrote:
>
> On 12/28/2015 03:15 AM, David Rowley wrote:
>
> Maybe it would be better to, once the filter is built, simply
> count the
>
> number of 1 bits and only use the filter if there's less than
> <threshold> 1 bits compared to the size of the filter in bits.
> There's
> functionality in bms_num_members() to do this, and there's
> also __builtin_popcount() in newer version of GCC, which we
> could have
> some wrapper around, perhaps.
>
>
> I don't really see how this is relevant with the previous point. The
> number of 1s in the bitmap can tell you the false positive rate for
> the bloom filter, not what fraction of lookups will be answered with
> "true".
>
> So while this needs to be watched, so that we stop using the bloom
> filter when it gets too full (e.g. due to under-estimate), it's
> completely unrelated to the previous issue.
>
>
> Why is it not related? this has got me confused. If a bloom filter has
> all of the bits set to 1, then it will never filter any Tuples right?
Because the false positive rate can be computed without having to look
at the lookups. So it's inherently independent on the ordering of outer
relation, and so on.
> If so, then a filter with all 1 bits set should be thrown away, as
> it'll never help us, and the filter should generally become more
> worthwhile as it contains a higher ratio of 0 bits vs 1 bits. Of
> course we don't have a count of how many Tuples matched each bit, so
> this is based on the assumption that each bit matches an equal number
> of Tuples. Are you saying this is not an assumption that we should
> make?
Sure we should check that. All I'm saying is it has nothing to do with
the first problem described in the first part of the e-mail.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-28 10:52 David Rowley <david.rowley@2ndquadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 1 reply; 26+ messages in thread
From: David Rowley @ 2015-12-28 10:52 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>; pgsql-hackers
On 28 December 2015 at 23:44, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
> On 12/28/2015 11:38 AM, David Rowley wrote:
>
>> If so, then a filter with all 1 bits set should be thrown away, as
>>
> it'll never help us, and the filter should generally become more
>> worthwhile as it contains a higher ratio of 0 bits vs 1 bits. Of
>> course we don't have a count of how many Tuples matched each bit, so
>> this is based on the assumption that each bit matches an equal number
>> of Tuples. Are you saying this is not an assumption that we should
>> make?
>>
>
> Sure we should check that. All I'm saying is it has nothing to do with the
> first problem described in the first part of the e-mail.
Okay. I was merely suggesting this method as an alternative to checking
tracking and checking the usefulness of the filter during the hash probe. I
assumed that tracking and checking the usefulness during the hash probe
won't be free, and that it may be better if we can estimate or determine
the expected usefulness of the filter before the probe stage, and throw it
away before we waste cycles using it.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-28 11:18 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: David Rowley <david.rowley@2ndquadrant.com>
0 siblings, 0 replies; 26+ messages in thread
From: Tomas Vondra @ 2015-12-28 11:18 UTC (permalink / raw)
To: David Rowley <david.rowley@2ndquadrant.com>; +Cc: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>; pgsql-hackers
On 12/28/2015 11:52 AM, David Rowley wrote:
> On 28 December 2015 at 23:44, Tomas Vondra <tomas.vondra@2ndquadrant.com
> <mailto:tomas.vondra@2ndquadrant.com>> wrote:
>
> On 12/28/2015 11:38 AM, David Rowley wrote:
>
> If so, then a filter with all 1 bits set should be thrown away, as
>
> it'll never help us, and the filter should generally become more
> worthwhile as it contains a higher ratio of 0 bits vs 1 bits. Of
> course we don't have a count of how many Tuples matched each bit, so
> this is based on the assumption that each bit matches an equal
> number
> of Tuples. Are you saying this is not an assumption that we should
> make?
>
>
> Sure we should check that. All I'm saying is it has nothing to do
> with the first problem described in the first part of the e-mail.
>
>
> Okay. I was merely suggesting this method as an alternative to checking
> tracking and checking the usefulness of the filter during the hash
> probe. I assumed that tracking and checking the usefulness during the
> hash probe won't be free, and that it may be better if we can estimate
> or determine the expected usefulness of the filter before the probe
> stage, and throw it away before we waste cycles using it.
Consider this example:
CREATE TABLE t (id INT);
INSERT INTO t SELECT i FROM generate_series(1,1000000) s(i);
ANALYZE;
SELECT * FROM t AS t1 JOIN t AS t2 ON (t1.id = t2.id)
WHERE t1.id < 10000 AND t2.id < 10000;
This will be executed like this:
QUERY PLAN
-----------------------------------------------------------------------
Hash Join (cost=17046.26..34008.58 rows=94 width=8)
Hash Cond: (t1.id = t2.id)
-> Seq Scan on t t1 (cost=0.00..16925.00 rows=9701 width=4)
Filter: (id < 10000)
-> Hash (cost=16925.00..16925.00 rows=9701 width=4)
-> Seq Scan on t t2 (cost=0.00..16925.00 rows=9701 width=4)
Filter: (id < 10000)
(7 rows)
But of course the problem is that the two relations are (trivially)
correlated, which means that in reality it works like this:
QUERY PLAN
---------------------------------------------------------
Hash Join (actual rows=9999 loops=1)
Hash Cond: (t1.id = t2.id)
-> Seq Scan on t t1 (actual rows=9999 loops=1)
Filter: (id < 10000)
Rows Removed by Filter: 990001
-> Hash (actual rows=9999 loops=1)
Buckets: 16384 Batches: 1 Memory Usage: 480kB
-> Seq Scan on t t2 (actual rows=9999 loops=1)
Filter: (id < 10000)
Rows Removed by Filter: 990001
Planning time: 0.316 ms
Execution time: 176.283 ms
(12 rows)
So while we have very good estimates on the scan nodes, the final
estimate is off - we expect about the bloom filter to eliminate ~99% of
rows, in reality 100% of rows matches (due to the correlation). And
that's even if the bloom filter is "perfect" in the sense that it has
very low false probability etc.
This example illustrates that such cases can't be really solved before
actually doing the lookups. Which does not make the checks you propose
pointless, but they simply address different cases (and I indeed planned
to implement them).
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2015-12-31 20:38 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
5 siblings, 0 replies; 26+ messages in thread
From: Tomas Vondra @ 2015-12-31 20:38 UTC (permalink / raw)
To: pgsql-hackers
Hi,
attached is v2 of the patch, with a number of improvements:
0) This relies on the the other hashjoin patches (delayed build of
buckets and batching), as it allows sizing the bloom filter.
1) enable_hashjoin_bloom GUC
This is mostly meant for debugging and testing, not for committing.
2) Outer joins should be working fine now. That is, the results should
be correct and faster as the outer rows without matches should not
be batched at all.
3) The bloom filter is now built for all hash joins, not just when
batching is happening. I've been a bit skeptical about the
non-batched cases, but it seems that I can get a sizable speedup
(~20-30%, depending on the selectivity of the join).
4) The code is refactored quite a bit, adding BloomFilterData instead
of just sprinkling the fields on HashJoinState or HashJoinTableData.
5) To size the bloom filter, we now use HyperLogLog couter, which we
now have in core thanks to the sorting improvements done by Peter
Geoghegan. This allows making the bloom filter much smaller when
possible.
The patch also extends the HyperLogLog API a bit (which I'll submit
to the CF independently).
There's a bunch of comments in the code, mostly with ideas about more
possible improvements.
The main piece missing in the patch (IMHO) is optimizer code making
decisions whether to enable bloom filters for the hash join, based on
cardinality estimates. And also the executor code disabling the bloom
filter if they turn inefficient. I don't think that's a major issue at
this point, though, and I think it'll be easier to do based on testing
the current patch.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments: download all (2 files, .tar.gz)
0001-extend-the-HyperLogLog-API-a-bit-by-adding-two-more-.patch (text/x-diff, 2.0K) download
From 8f207693faa65e65e8a1e5e894c2ad96ad1f3cea Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Mon, 28 Dec 2015 14:20:17 +0100
Subject: [PATCH 1/2] extend the HyperLogLog API a bit by adding two more
methods
- initHyperLogLogError (initialize the counter for error rate)
- freeHyperLogLog (release the memory allocated for counter state)
---
src/backend/lib/hyperloglog.c | 29 +++++++++++++++++++++++++++++
src/include/lib/hyperloglog.h | 2 ++
2 files changed, 31 insertions(+)
diff --git a/src/backend/lib/hyperloglog.c b/src/backend/lib/hyperloglog.c
index 718afb8..2949a8d 100644
--- a/src/backend/lib/hyperloglog.c
+++ b/src/backend/lib/hyperloglog.c
@@ -108,6 +108,35 @@ initHyperLogLog(hyperLogLogState *cState, uint8 bwidth)
}
/*
+ * Initialize HyperLogLog track state
+ */
+void
+initHyperLogLogError(hyperLogLogState *cState, double error)
+{
+ uint8 bwidth = 4;
+
+ while (bwidth < 16)
+ {
+ double m = (Size)1 << bwidth;
+ if (1.04 / sqrt(m) < error)
+ break;
+ bwidth++;
+ }
+
+ initHyperLogLog(cState, bwidth);
+}
+
+/*
+ * Free HyperLogLog track state
+ */
+void
+freeHyperLogLog(hyperLogLogState *cState)
+{
+ Assert(cState->hashesArr != NULL);
+ pfree(cState->hashesArr);
+}
+
+/*
* Adds element to the estimator, from caller-supplied hash.
*
* It is critical that the hash value passed be an actual hash value, typically
diff --git a/src/include/lib/hyperloglog.h b/src/include/lib/hyperloglog.h
index fd8280c..004490a 100644
--- a/src/include/lib/hyperloglog.h
+++ b/src/include/lib/hyperloglog.h
@@ -60,8 +60,10 @@ typedef struct hyperLogLogState
} hyperLogLogState;
extern void initHyperLogLog(hyperLogLogState *cState, uint8 bwidth);
+extern void initHyperLogLogError(hyperLogLogState *cState, double error);
extern void addHyperLogLog(hyperLogLogState *cState, uint32 hash);
extern double estimateHyperLogLog(hyperLogLogState *cState);
extern void mergeHyperLogLog(hyperLogLogState *cState, const hyperLogLogState *oState);
+extern void freeHyperLogLog(hyperLogLogState *cState);
#endif /* HYPERLOGLOG_H */
--
2.1.0
0002-hash-bloom-filters-v2.patch (text/x-diff, 25.9K) download
From fbb2baf9b60d9f57182be3b58b3678cfe52b2931 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Sun, 27 Dec 2015 18:26:34 +0100
Subject: [PATCH 2/2] hash bloom filters v2
- extend bloom filters to unbatched case
- always start with nbatch=1 even when we assume we'll need to batch
(helps with over-estimates and also sizing of the bloom filter)
- use HyperLogLog to count distinct values and size the bloom filter
(we can do this thanks to always starting with nbatch=1)
- refactorings and cleanups
---
src/backend/executor/nodeHash.c | 259 +++++++++++++++++++++++++++++
src/backend/executor/nodeHashjoin.c | 24 ++-
src/backend/utils/adt/Makefile | 2 +-
src/backend/utils/adt/murmur3.c | 315 ++++++++++++++++++++++++++++++++++++
src/backend/utils/misc/guc.c | 9 ++
src/include/executor/hashjoin.h | 18 +++
src/include/optimizer/cost.h | 1 +
src/include/utils/murmur3.h | 29 ++++
8 files changed, 655 insertions(+), 2 deletions(-)
create mode 100644 src/backend/utils/adt/murmur3.c
create mode 100644 src/include/utils/murmur3.h
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index c53d485..ebfc6c2 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -31,12 +31,15 @@
#include "executor/hashjoin.h"
#include "executor/nodeHash.h"
#include "executor/nodeHashjoin.h"
+#include "lib/hyperloglog.h"
#include "miscadmin.h"
#include "utils/dynahash.h"
#include "utils/memutils.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"
+#include "utils/murmur3.h"
+bool enable_hashjoin_bloom = true;
static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
static void ExecHashBuildBuckets(HashJoinTable hashtable);
@@ -47,9 +50,17 @@ static void ExecHashSkewTableInsert(HashJoinTable hashtable,
uint32 hashvalue,
int bucketNumber);
static void ExecHashRemoveNextSkewBucket(HashJoinTable hashtable);
+static void ExecHashHLLAddValue(HashJoinTable hashtable, uint32 hashvalue);
+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 +123,22 @@ MultiExecHash(HashState *node)
{
int bucketNumber;
+ /*
+ * If we're interested in building the bloom filter, add the hash
+ * value either to the hyperloglog counter or to the bloom filter,
+ * depending on which phase we're in. If we're still not batching,
+ * we only have the hyperloglog counter, otherwise we have the
+ * bloom filter.
+ *
+ * XXX We may still not build any of the two things (HLL, bloom),
+ * e.g. if we decide not to based on estimates or at runtime.
+ */
+ if (enable_hashjoin_bloom)
+ {
+ ExecHashHLLAddValue(hashtable, hashvalue);
+ ExecHashBloomAddValue(hashtable, hashvalue);
+ }
+
bucketNumber = ExecHashGetSkewBucket(hashtable, hashvalue);
if (bucketNumber != INVALID_SKEW_BUCKET_NO)
{
@@ -307,6 +334,35 @@ ExecHashTableCreate(Hash *node, List *hashOperators, bool keepNulls)
hashtable->spaceAllowed * SKEW_WORK_MEM_PERCENT / 100;
hashtable->chunks = NULL;
+ /* only one of those is assumed to be non-NULL */
+ hashtable->bloomFilter = NULL;
+ hashtable->hll = NULL;
+
+ /*
+ * We don't quite know how many distinct values to expect, so we'll use
+ * the estimated number of rowsto be added to the hash table, and assume
+ * they're all distinct.
+ *
+ * But if we already know there'll be multiple batches, we can't use hll
+ * because we need to start building the bloom filter right away. In that
+ * case we simply assume all the values are unique - we'll probably use
+ * larger (and thus less efficient) bloom filter. It may not matter that
+ * much because the possible savings (reduced I/O etc.) are much more
+ * significant.
+ *
+ * XXX What we could do is always build the first batch in memory, thus
+ * get ndistinct estimate from hyperloglog and then immediately
+ * switch to the originally estimated number of batches.
+ *
+ * XXX Not really sure how to size the HLL, so the bwidth value may be
+ * too high (and the counter too big).
+ */
+ if (enable_hashjoin_bloom)
+ {
+ hashtable->hll = palloc0(sizeof(hyperLogLogState));
+ initHyperLogLogError(hashtable->hll, 0.05);
+ }
+
/*
* Get info about the hash functions to be used for each hash key. Also
* remember whether the join operators are strict.
@@ -588,6 +644,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)
@@ -649,6 +706,61 @@ ExecHashIncreaseNumBatches(HashJoinTable hashtable)
ninmemory = nfreed = 0;
/*
+ * If we're switching to batched mode (and the bloom filters are enabled),
+ * we need to start build the bloom filter.
+ *
+ * To size the bloom filter, we'll use the hyperloglog counter to estimate
+ * the number of distinct values in the first batch, multiplied by the
+ * expected number of batches. This may not work when the estimate is wrong,
+ * but we can't really do better.
+ *
+ * XXX The problem here is that if we started with nbatch=1 and we're
+ * starting to batch now, it means we've under-estimated the cardinality
+ * somehow. And we don't know how much, but it's quite likely it's not
+ * just by a factor of 2 (which is assumed in the next block). So maybe
+ * we should be more pessimistic and use a higher 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 We can't really resize the bloom filter if we reach the number of
+ * distinct values, but 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.
+ *
+ * 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).
+ */
+ if (enable_hashjoin_bloom && (oldnbatch == 1))
+ {
+ double ndistinct;
+
+ /* must have the counter to size bloom filter properly */
+ Assert(hashtable->hll);
+
+ ndistinct = estimateHyperLogLog(hashtable->hll);
+
+ /* We don't really want tiny bloom filters. */
+ if (ndistinct < 1024)
+ ndistinct = 1024;
+
+ elog(WARNING, "ExecHashIncreaseNumBatches: ndistinct %ld",
+ (int64)(nbatch * ndistinct));
+
+ hashtable->bloomFilter = BloomFilterInit(nbatch * ndistinct,
+ BLOOM_ERROR_RATE);
+
+ /* Free the HLL state (entirely). */
+ freeHyperLogLog(hashtable->hll);
+ pfree(hashtable->hll);
+ hashtable->hll = NULL;
+
+ 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
* already been processed. We will free the old chunks as we go.
@@ -677,6 +789,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 */
@@ -736,6 +851,7 @@ ExecHashIncreaseNumBatches(HashJoinTable hashtable)
static void
ExecHashBuildBuckets(HashJoinTable hashtable)
{
+ bool build_bloom_filter = false;
HashMemoryChunk chunk;
#ifdef HJDEBUG
@@ -760,6 +876,33 @@ ExecHashBuildBuckets(HashJoinTable hashtable)
/* Don't forget to zero the buckets (AllocHuge does not do that). */
memset(hashtable->buckets, 0, hashtable->nbuckets * sizeof(HashJoinTuple));
+ /*
+ * If we're still in the 'count-ndistinct phase, we need to build the
+ * bloom filter at this point.
+ */
+ if (hashtable->hll != NULL)
+ {
+ double ndistinct;
+
+ ndistinct = estimateHyperLogLog(hashtable->hll);
+
+ if (ndistinct < 1024)
+ ndistinct = 1024;
+
+ elog(WARNING, "ExecHashBuildBuckets: building bloom filter (ndistinct %ld)",
+ (int64)(2*ndistinct));
+
+ hashtable->bloomFilter = BloomFilterInit(2 * ndistinct,
+ BLOOM_ERROR_RATE);
+
+ /* Free the HLL state. */
+ freeHyperLogLog(hashtable->hll);
+ pfree(hashtable->hll);
+ hashtable->hll = NULL;
+
+ build_bloom_filter = true;
+ }
+
/* scan through all tuples in all chunks to rebuild the hash table */
for (chunk = hashtable->chunks; chunk != NULL; chunk = chunk->next)
{
@@ -775,6 +918,9 @@ ExecHashBuildBuckets(HashJoinTable hashtable)
ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
&bucketno, &batchno);
+ if (build_bloom_filter)
+ ExecHashBloomAddValue(hashtable, hashTuple->hashvalue);
+
/* add the tuple to the proper bucket */
hashTuple->next = hashtable->buckets[bucketno];
hashtable->buckets[bucketno] = hashTuple;
@@ -1683,3 +1829,116 @@ dense_alloc(HashJoinTable hashtable, Size size)
/* return pointer to the start of the tuple memory */
return ptr;
}
+
+static void
+ExecHashHLLAddValue(HashJoinTable hashtable, uint32 hashvalue)
+{
+ hyperLogLogState *hll = hashtable->hll;
+
+ /*
+ * If we don't have a HLL counter, then we're not supposed to build
+ * it and we can just bail out.
+ */
+ if (hll == NULL)
+ return;
+
+ /* We can't have both counter and filter at the same time. */
+ Assert(hashtable->bloomFilter == NULL);
+
+ addHyperLogLog(hashtable->hll, hashvalue);
+}
+
+static void
+ExecHashBloomAddValue(HashJoinTable hashtable, uint32 hashvalue)
+{
+ int i, byteIdx, bitIdx;
+ BloomFilter filter = hashtable->bloomFilter;
+
+ /*
+ * If we don't have a bloom filter, then we're not supposed to build
+ * it and we can just bail out.
+ */
+ if (filter == NULL)
+ return;
+
+ /* We can't have both counter and filter at the same time. */
+ Assert(hashtable->hll == NULL);
+
+ /*
+ * We only build bloom filters while in the first batch (with all
+ * tuples, so it makes no sense to re-add them over and over).
+ */
+ if (hashtable->curbatch > 0)
+ return;
+
+ /*
+ * To get multiple independent hash functions, we simply use
+ * different seeds for them. We use murmur3 with 32-bit values here,
+ * but we might use anything sufficiently random and fast (e.g.
+ * jenkinks hash or such).
+ */
+ 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;
+
+ filter->nlookups++;
+
+ 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;
+ }
+
+ /* if we got here, we know it's a match */
+ filter->nmatches++;
+
+ 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..101f39a 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 */
@@ -238,6 +238,15 @@ ExecHashJoin(HashJoinState *node)
hashvalue);
node->hj_CurTuple = NULL;
+ /* If still in the first batch, we check the bloom filter. */
+ if ((hashtable->curbatch == 0) &&
+ (! ExecHashBloomCheckValue(hashtable, hashvalue)))
+ {
+ /* no matches; check for possible outer-join fill */
+ node->hj_JoinState = HJ_FILL_OUTER_TUPLE;
+ continue;
+ }
+
/*
* The tuple might not belong to the current batch (where
* "current batch" includes the skew buckets if any).
@@ -608,6 +617,19 @@ ExecEndHashJoin(HashJoinState *node)
*/
if (node->hj_HashTable)
{
+ HashJoinTable hashtable = node->hj_HashTable;
+
+ /*
+ * If there's a bloom filter, print some debug info before destroying the
+ * hash table.
+ */
+ if (hashtable->bloomFilter)
+ {
+ BloomFilter filter = hashtable->bloomFilter;
+ elog(WARNING, "bloom filter lookups=%lu matches=%lu eliminated=%lu%%",
+ filter->nlookups, filter->nmatches, 100 - (100 * filter->nmatches) / Max(1,filter->nlookups));
+ }
+
ExecHashTableDestroy(node->hj_HashTable);
node->hj_HashTable = NULL;
}
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/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index a185749..ffc1281 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -864,6 +864,15 @@ static struct config_bool ConfigureNamesBool[] =
NULL, NULL, NULL
},
{
+ {"enable_hashjoin_bloom", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables the use of bloom filters in hash joins."),
+ NULL
+ },
+ &enable_hashjoin_bloom,
+ true,
+ NULL, NULL, NULL
+ },
+ {
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
gettext_noop("This algorithm attempts to do planning without "
diff --git a/src/include/executor/hashjoin.h b/src/include/executor/hashjoin.h
index 255c506..df22361 100644
--- a/src/include/executor/hashjoin.h
+++ b/src/include/executor/hashjoin.h
@@ -16,6 +16,7 @@
#include "nodes/execnodes.h"
#include "storage/buffile.h"
+#include "lib/hyperloglog.h"
/* ----------------------------------------------------------------
* hash-join hash table structures
@@ -72,6 +73,17 @@ typedef struct HashJoinTupleData
#define HJTUPLE_MINTUPLE(hjtup) \
((MinimalTuple) ((char *) (hjtup) + HJTUPLE_OVERHEAD))
+typedef struct BloomFilterData
+{
+ uint64 nlookups; /* number of lookups */
+ uint64 nmatches; /* number of matches */
+ 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
@@ -181,6 +193,12 @@ 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 */
+ hyperLogLogState *hll; /* used to to size bloom filter */
} HashJoinTableData;
+bool ExecHashBloomCheckValue(HashJoinTable hashtable, uint32 hashvalue);
+
#endif /* HASHJOIN_H */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index ac21a3a..999bf84 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -66,6 +66,7 @@ extern bool enable_nestloop;
extern bool enable_material;
extern bool enable_mergejoin;
extern bool enable_hashjoin;
+extern bool enable_hashjoin_bloom;
extern int constraint_exclusion;
extern double clamp_row_est(double nrows);
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 <stdint.h>
+
+#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_
--
2.1.0
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-09 19:02 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Simon Riggs <simon@2ndQuadrant.com>
1 sibling, 2 replies; 26+ messages in thread
From: Tomas Vondra @ 2016-01-09 19:02 UTC (permalink / raw)
To: Simon Riggs <simon@2ndQuadrant.com>; +Cc: pgsql-hackers
Hi,
attached are results for some basic performance evaluation of the patch
(and also scripts used for the evaluation). I've used a simple join of
two tables ("fact" and "dim"), with three different dataset sizes.
CREATE TABLE dim (id INT, r INT, val TEXT);
CREATE TABLE fact (id INT, val TEXT);
-- 1M rows into "dim"
INSERT INTO dim
SELECT i, mod(i,100), md5(i::text) FROM generate_series(1,1000000) s(i);
-- 10M rows into "fact"
INSERT INTO fact
SELECT mod(i,1000000)+1, md5((mod(i,1000000)+1)::text)
FROM generate_series(1,10000000) s(i);
Which means the "dim.r" column has 100 different values (0-99) with
uniform distribution. So e.g. "WHERE r < 15" matches 15%.
There are three dataset sizes:
1) small: dim 1M rows (73MB), fact 10M rows (650MB)
2) medium: dim: 10M rows (730MB), fact 100M rows (6.5GB)
3) large: dim: 5M rows (365MB), fact 250M rows (16GB)
The machine has 8GB of RAM, so "small" easily fits into RAM, "medium" is
just at the border, and "large" is clearly over (especially when batching).
For each dataset size there are two queries - one with inner and one
with outer join, with a filter on the smaller one ("dim") determining
the "selectivity".
-- inner join
SELECT COUNT(dim.val), COUNT(fact.val)
FROM fact JOIN dim ON (fact.id = dim.id) WHERE r < $1
-- outer join
SELECT COUNT(dim.val), COUNT(fact.val)
FROM fact LEFT JOIN (SELECT * FROM dim WHERE r < $1) dim
ON (fact.id = dim.id)
Those queries were executed with various work_mem sizes (to either use
no batching or different number of batches), and also with different
filter values (to filter to 10%, 20%, 30%, ...., 100% of data).
After collecting data both on master and with all the patches applied,
I've computed the speedup factor as
(time with patches) / (time on master)
and plotted that as a pivot tables with heat map. Values <1.0 (red) mean
"bloom filter made the query faster" while values > 1.0 (blue) means it
slowed the query down.
Let's quickly skim through the results for each dataset size. The
attached charts only show results for the "inner" queries, but the
results for "outer" queries are pretty much exactly the same.
1) small (hash-joins-bloom-1-10.png)
------------------------------------
There's a clear speedup as long as the hash join requires batching and
the selectivity is below 50-60%. In the best case (10% selectivity,
small work_mem and thus multiple batches) we save up to ~30% of time.
Once we get to non-batching mode, the bloom filter is ineffective no
matter the selectivity. I assume this is because for the small
selectivities (e.g. 10%) it's simply cheaper to check the hash table,
which is small and likely fits into L3 on the CPU (which is ~6MB on the
i5-2500 CPU in the system).
2) medium (hash-joins-bloom-10-100.png)
---------------------------------------
The results are similar to the "small" results, except that the speedup
is somewhat larger (up to 40%), and there's no sudden jump when the
queries stop batching (work_mem=1GB is enough to run the query in a
single batch even with 100% selectivity). The "break-even" selectivity
is again somewhere around 50% (a bit lower in non-batching mode).
3) large (hash-joins-bloom-5-250.png)
-------------------------------------
Pretty much the same as "medium".
So, this seems to bring reasonable speedup, as long as the selectivity
is below 50%, and the data set is sufficiently large.
It's however clear that the patch won't work without some sort of
selectivity estimation - either at planning time or optimization time
(or both). I've speculated about how to do that, but the current patches
don't implement any of that yet and any ideas are welcome.
Another open question is sizing the bloom filter in the multi-batch
case, which turns out to be quite tricky. What the patch does right now
is estimating the number of distinct values to store in the filter based
on the first batch (the other hashjoin patch in this CF makes this
possible). That is, there's a hyperloglog counter that gives us (very
accurate) ndistinct estimate for the first batch, and then we do (nbatch
* ndistinct), to estimate the ndistinct values in the whole data set.
That estimate is of course rather naive, and often produces too high -
for example we might have already seen all the distinct values in the
first batch. So the result is a bloom filter much larger than necessary.
Not sure how to fix this :-(
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
hash-joins-bloom-5-250.png (image/png, 29.1K) download
view image
hash-joins-bloom-10-100.png (image/png, 29.3K) download
view image
hash-joins-bloom-1-10.png (image/png, 41.6K) download
view image
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-10 00:08 Peter Geoghegan <pg@heroku.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
1 sibling, 2 replies; 26+ messages in thread
From: Peter Geoghegan @ 2016-01-10 00:08 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
On Sat, Jan 9, 2016 at 11:02 AM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> So, this seems to bring reasonable speedup, as long as the selectivity is
> below 50%, and the data set is sufficiently large.
What about semijoins? Apparently they can use bloom filters
particularly effectively. Have you considered them as a special case?
Also, have you considered Hash join conditions with multiple
attributes as a special case? I'm thinking of cases like this:
regression=# set enable_mergejoin = off;
SET
regression=# explain analyze select * from tenk1 o join tenk2 t on
o.twenty = t.twenty and t.hundred = o.hundred;
QUERY PLAN
──────────────────────────────────────────────────────────────────────
Hash Join (cost=595.00..4103.00 rows=50000 width=488) (actual
time=12.086..1026.194 rows=1000000 loops=1)
Hash Cond: ((o.twenty = t.twenty) AND (o.hundred = t.hundred))
-> Seq Scan on tenk1 o (cost=0.00..458.00 rows=10000 width=244)
(actual time=0.017..4.212 rows=10000 loops=1)
-> Hash (cost=445.00..445.00 rows=10000 width=244) (actual
time=12.023..12.023 rows=10000 loops=1)
Buckets: 16384 Batches: 1 Memory Usage: 2824kB
-> Seq Scan on tenk2 t (cost=0.00..445.00 rows=10000
width=244) (actual time=0.006..3.453 rows=10000 loops=1)
Planning time: 0.567 ms
Execution time: 1116.094 ms
(8 rows)
(Note that while the optimizer has a slight preference for a merge
join in this case, the plan I show here is a bit faster on my
machine).
--
Peter Geoghegan
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-10 03:03 Peter Geoghegan <pg@heroku.com>
parent: Peter Geoghegan <pg@heroku.com>
1 sibling, 1 reply; 26+ messages in thread
From: Peter Geoghegan @ 2016-01-10 03:03 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
On Sat, Jan 9, 2016 at 4:08 PM, Peter Geoghegan <pg@heroku.com> wrote:
> Also, have you considered Hash join conditions with multiple
> attributes as a special case? I'm thinking of cases like this:
Sorry, accidentally fat-fingered my enter key before I was finished
drafting that mail. That example isn't useful, because there is no
early/cheap elimination of tuples while scanning the outer relation.
My point about bloom filters on only one attribute (or perhaps
multiple bloom filters on multiple attributes) is that you might be
able to make the bloom filter more effective, particularly relative to
the amount of memory available, by only building it for one attribute
where that distinction (one attribute vs multiple) happens to exist.
Simon said: "So the objective must be to get a Bloom Filter that is
small enough that it lives in a higher/faster level of cache than the
main Hash table". I agree that that's really important here, although
I did note that Tomas wasn't so sure, emphasizing the importance of
avoiding serialization and deserialization overhead -- and certainly,
that's why the patch helps some cases a lot. But Simon's point applies
more to the worst case than the best or average cases, and evidently
we have plenty of worrying about the worst case left to do here.
So, one attribute could have relatively low cardinality, and thus
fewer distinct items in the bloom filter's set, making it far slower
to degrade (i.e. have increased probability of false positives) as
compared to a composite of two or more attributes, and yet perhaps not
significantly less useful in terms of its ability to eliminate
(de)serialization overhead. Or, with two bloom filters (one per
attribute), one bloom filter could degrade far faster than the other
(due to having more distinct values), often very unpredictably, and
yet it wouldn't matter because we'd discard the bad one (maybe really
early, during the scan of the inner relation, using HLL).
I notice that all these example queries involve less-than operators
(inner relation tuples are thereby prevented from being entered into
the hash table). It might not be a terrible idea to hash abbreviated
keys (or even truncated abbreviated keys) for the bloom filter in
certain cases, in particular when there is a correlation in the inner
relation attributes (equi-joined attribute, and attribute that is
other part of qual). There might not be a correlation, of course, but
with some care hashing abbreviated keys may have virtually no
additional overhead, making it worth doing despite the general
uncertainty about any correlation existing. If you're going to accept
that the bloom filter can't be very large, which I think you must,
then hashing an entire value may be no better than hashing an
abbreviated key (those 8 bytes tend to have a lot of entropy). This
point is rather hand-wavy, though.
I suspect that BLOOM_ERROR_RATE isn't the most useful constraint here.
Is the degree to which it helps in sympathetic cases at all
commensurate with the degree to which it hurts in unsympathetic cases?
In your "low selectivity" cases (the sympathetic cases), there are
relatively few values represented in the main hash table, and
therefore in the bloom filter, and so a smaller bloom filter results
automatically anyway. But in the bad cases, the BLOOM_ERROR_RATE
constraint just wastes memory bandwidth for no gain, I think. If the
number of elements is so large that a reasonable fixed sized bloom
filter has a poor false positive rate anyway, we may have already
lost.
My sense is that we should try to make the bloom filter as cheap as
possible more so than trying to make sure it's useful before much work
has been done.
Is it okay that you don't treat MCV/skew values as special? Actually,
looking at this code, I think I notice something:
@@ -238,6 +238,15 @@ ExecHashJoin(HashJoinState *node)
hashvalue);
node->hj_CurTuple = NULL;
+ /* If still in the first batch, we check the bloom filter. */
+ if ((hashtable->curbatch == 0) &&
+ (! ExecHashBloomCheckValue(hashtable, hashvalue)))
+ {
+ /* no matches; check for possible outer-join fill */
+ node->hj_JoinState = HJ_FILL_OUTER_TUPLE;
+ continue;
+ }
Haven't we already established by now that the value of
"node->hj_CurSkewBucketNo" may not be INVALID_SKEW_BUCKET_NO, and so
the value certainly was found in the inner relation scan? Why bother
doing anything with the bloom filter in that common case? (Note that
I'm not suggesting that we don't establish "node->hj_CurSkewBucketNo"
first).
Also, are you aware of this?
http://www.nus.edu.sg/nurop/2010/Proceedings/SoC/NUROP_Congress_Cheng%20Bin.pdf
It talks about bloom filters for hash joins in PostgreSQL
specifically. Interestingly, they talk about specific TPC-H queries.
BTW, I think code like this needs better comments:
+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;
Have you experimentally verified that you get the expected probability
of false positives in practice?
--
Peter Geoghegan
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-10 04:11 Peter Geoghegan <pg@heroku.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
1 sibling, 1 reply; 26+ messages in thread
From: Peter Geoghegan @ 2016-01-10 04:11 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
On Sat, Jan 9, 2016 at 11:02 AM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> Which means the "dim.r" column has 100 different values (0-99) with uniform
> distribution. So e.g. "WHERE r < 15" matches 15%.
I think that the use of a uniform distribution to demonstrate this
patch is a bad idea, unless you want to have a conversation about the
worst case.
Look at the use cases for bloom filters in general. They're almost all
some variation on the same theme: checking a bloom filter
inexpensively, to avoid an expensive cache miss (of some fashion). The
Google Chrome web browser uses a bloom filter for malicious URLs. It
usually avoids consulting Google's servers about whether or not any
given URL that is visited is malicious by using the bloom filter. This
is effective in large part because the top 100 websites ranked by
popularity have a huge falloff in popularity as you go down the list.
It looks like a Zipfian distribution, and so I imagine they get pretty
far with a very small bloom filter, even though in theory the chances
of any given valid URL resulting in a cache miss is very high.
Generally, uniform distributions are rare in a non-canonical list of
things, like a hash join outer relation's attribute.
--
Peter Geoghegan
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-10 19:12 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Peter Geoghegan <pg@heroku.com>
1 sibling, 0 replies; 26+ messages in thread
From: Tomas Vondra @ 2016-01-10 19:12 UTC (permalink / raw)
To: Peter Geoghegan <pg@heroku.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
Hi,
On 01/10/2016 01:08 AM, Peter Geoghegan wrote:
> On Sat, Jan 9, 2016 at 11:02 AM, Tomas Vondra
> <tomas.vondra@2ndquadrant.com> wrote:
>> So, this seems to bring reasonable speedup, as long as the selectivity is
>> below 50%, and the data set is sufficiently large.
>
> What about semijoins? Apparently they can use bloom filters
> particularly effectively. Have you considered them as a special case?
You mean to handle them in a special way in the code, or just to perform
benchmark semijoins (and not just regular joins)?
> Also, have you considered Hash join conditions with multiple
> attributes as a special case? I'm thinking of cases like this:
>
> regression=# set enable_mergejoin = off;
> SET
> regression=# explain analyze select * from tenk1 o join tenk2 t on
> o.twenty = t.twenty and t.hundred = o.hundred;
> QUERY PLAN
> ──────────────────────────────────────────────────────────────────────
> Hash Join (cost=595.00..4103.00 rows=50000 width=488) (actual
> time=12.086..1026.194 rows=1000000 loops=1)
> Hash Cond: ((o.twenty = t.twenty) AND (o.hundred = t.hundred))
> -> Seq Scan on tenk1 o (cost=0.00..458.00 rows=10000 width=244)
> (actual time=0.017..4.212 rows=10000 loops=1)
> -> Hash (cost=445.00..445.00 rows=10000 width=244) (actual
> time=12.023..12.023 rows=10000 loops=1)
> Buckets: 16384 Batches: 1 Memory Usage: 2824kB
> -> Seq Scan on tenk2 t (cost=0.00..445.00 rows=10000
> width=244) (actual time=0.006..3.453 rows=10000 loops=1)
> Planning time: 0.567 ms
> Execution time: 1116.094 ms
> (8 rows)
>
> (Note that while the optimizer has a slight preference for a merge
> join in this case, the plan I show here is a bit faster on my
> machine).
The patch I posted actually does not build bloom filter on the values
directly, but on the hashvalue we already use. So it handles hashjoins
with arbitrary number of attributes just fine.
Or perhaps you're thinking about some special optimization that might
improve such cases (I can't think of any)?
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-10 20:30 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Peter Geoghegan <pg@heroku.com>
0 siblings, 1 reply; 26+ messages in thread
From: Tomas Vondra @ 2016-01-10 20:30 UTC (permalink / raw)
To: Peter Geoghegan <pg@heroku.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
Hi,
On 01/10/2016 04:03 AM, Peter Geoghegan wrote:
> On Sat, Jan 9, 2016 at 4:08 PM, Peter Geoghegan <pg@heroku.com> wrote:
>> Also, have you considered Hash join conditions with multiple
>> attributes as a special case? I'm thinking of cases like this:
>
> Sorry, accidentally fat-fingered my enter key before I was finished
> drafting that mail. That example isn't useful, because there is no
> early/cheap elimination of tuples while scanning the outer relation.
>
> My point about bloom filters on only one attribute (or perhaps
> multiple bloom filters on multiple attributes) is that you might be
> able to make the bloom filter more effective, particularly relative
> to the amount of memory available, by only building it for one
> attribute where that distinction (one attribute vs multiple) happens
> to exist.
I'm not sure what you mean. The patch builds bloom filter on hashvalue,
not the attribute values directly. I find this very efficient as we
don't have to hash the original values again and instead work with just
a short 32-bit hashvalue.
I really doubt doing some magic by only building the bloom filter on one
of the attributes is useful - it's way more complicated, requires
estimating the ndistinct for each attribute, and also somehow estimate
the impact on the accuracy of the bloom filter. That seems rather
complex and I don't have a good idea how to do that.
>
> Simon said: "So the objective must be to get a Bloom Filter that is
> small enough that it lives in a higher/faster level of cache than the
> main Hash table". I agree that that's really important here, although
> I did note that Tomas wasn't so sure, emphasizing the importance of
> avoiding serialization and deserialization overhead -- and certainly,
> that's why the patch helps some cases a lot.
I think the impact of the bloom filter size really depends on the size
of the hash join. I see three cases, as indicated in the benchmarks I posted
(a) single batch (1M:10M)
- fitting into CPU cache really important (otherwise almost no
improvement)
- impossible to speed up for very small hash tables (that fit into
L3 cache)
(b) multiple batches w. medium data set (10M:100M)
- important, but not as much as for (a), as we still eliminate the
(de)serialization overhead
(c) large data set (5M:250M)
- not important, it's mostly about eliminating (de)serialization
overhead and/or I/O overhead
> But Simon's point applies more to the worst case than the best or
> average cases, and evidently we have plenty of worrying about the
> worst case left to do here.
So what do you consider to be the worst case?
> So, one attribute could have relatively low cardinality, and thus
> fewer distinct items in the bloom filter's set, making it far slower
> to degrade (i.e. have increased probability of false positives) as
> compared to a composite of two or more attributes, and yet perhaps
> not significantly less useful in terms of its ability to eliminate
> (de)serialization overhead. Or, with two bloom filters (one per
> attribute), one bloom filter could degrade far faster than the other
> (due to having more distinct values), often very unpredictably, and
> yet it wouldn't matter because we'd discard the bad one (maybe
> really early, during the scan of the inner relation, using HLL).
I don't think so.
Firstly, I don't know what you mean by "slower to degrade" as the false
positive rate of a bloom filter does not depend on the cardinality of
the column used to build the bloom filter, but rather on the "load
factor" of the bloom filter (i.e. number of items added to the filter
compared to the initial capacity). Not to mention that you still have to
estimate the cardinality of the columns, which is tricky (and one of the
main issues of the current patch, IMHO).
Secondly, by splitting the "composite" bloom filter into per-column
filters you make it impossible to track correlation between the columns.
For example let's say we have two attributes (a,b), 'a' having 1000
distinct values while 'b' only has 10. But let's assume that there's a
correlation between 'a' and 'b' so that (mod(a,10) = b). If you build
the bloom filter on the columns separately, it's going to be entirely
useless. Sure, this is a rather trivial (and perhaps naive) example, but
it shows how easy it's to break it.
I'd also like to point out that vast majority of joins is on a single
column, so perhaps we should try to solve those first, and then perhaps
improve the multi-column case if possible.
>
> I notice that all these example queries involve less-than operators
> (inner relation tuples are thereby prevented from being entered into
> the hash table). It might not be a terrible idea to hash abbreviated
> keys (or even truncated abbreviated keys) for the bloom filter in
> certain cases, in particular when there is a correlation in the inner
> relation attributes (equi-joined attribute, and attribute that is
> other part of qual). There might not be a correlation, of course, but
> with some care hashing abbreviated keys may have virtually no
> additional overhead, making it worth doing despite the general
> uncertainty about any correlation existing. If you're going to accept
> that the bloom filter can't be very large, which I think you must,
> then hashing an entire value may be no better than hashing an
> abbreviated key (those 8 bytes tend to have a lot of entropy). This
> point is rather hand-wavy, though.
I have to admit that I have zero idea on how to do that. Also, there's
nothing really special about the '<' operator - the reason why I used it
is that it makes it very simple to filter arbitrary fraction of the
table (i.e. specify how many tuples of the outer relation have a
matching tuple in the hash table).
I'm not saying we can't apply the abbreviated keys somehow, but at this
point it seems rather like a hammer looking for a nail.
>
> I suspect that BLOOM_ERROR_RATE isn't the most useful constraint
> here. Is the degree to which it helps in sympathetic cases at all
> commensurate with the degree to which it hurts in unsympathetic
> cases? In your "low selectivity" cases (the sympathetic cases), there
> are relatively few values represented in the main hash table, and
> therefore in the bloom filter, and so a smaller bloom filter results
> automatically anyway. But in the bad cases, the BLOOM_ERROR_RATE
> constraint just wastes memory bandwidth for no gain, I think. If the
> number of elements is so large that a reasonable fixed sized bloom
> filter has a poor false positive rate anyway, we may have already
> lost.
I agree that having a fixed error rate is somewhat annoying. What I
imagined would be something like this:
(1) estimate the number of distinct values the bloom filter
(2) see what error rate would make the bloom filter "small enough"
(so that it fits into L3)
(3) see if the error rate makes the bloom filter efficient (some
simple costing, or perhaps hard-coded threshold)
This however requires knowledge of the L3 cache size for (2), or rather
how much of it is available for the process (which is tricky to get).
And then (3) requires some costing function, which seems tricky too.
>
> My sense is that we should try to make the bloom filter as cheap as
> possible more so than trying to make sure it's useful before much
> work has been done.
Well, yeah. Fail fast. But how?
> Is it okay that you don't treat MCV/skew values as special? Actually,
> looking at this code, I think I notice something:
>
> @@ -238,6 +238,15 @@ ExecHashJoin(HashJoinState *node)
> hashvalue);
> node->hj_CurTuple = NULL;
>
> + /* If still in the first batch, we check the bloom filter. */
> + if ((hashtable->curbatch == 0) &&
> + (! ExecHashBloomCheckValue(hashtable, hashvalue)))
> + {
> + /* no matches; check for possible outer-join fill */
> + node->hj_JoinState = HJ_FILL_OUTER_TUPLE;
> + continue;
> + }
>
> Haven't we already established by now that the value of
> "node->hj_CurSkewBucketNo" may not be INVALID_SKEW_BUCKET_NO, and so
> the value certainly was found in the inner relation scan? Why bother
> doing anything with the bloom filter in that common case? (Note that
> I'm not suggesting that we don't establish "node->hj_CurSkewBucketNo"
> first).
Hmmmm, maybe. The bloom filter should contain all values, including
those from skew buckets. So what the code could / should do is check the
bloom filter first, and only do ExecHashGetSkewBucket() if we still
think the tuple may be in the hash table. So something like this:
node->hj_CurHashValue = hashvalue;
node->hj_CurTuple = NULL;
/* If still in the first batch, we check the bloom filter. */
if ((hashtable->curbatch == 0) &&
ExecHashBloomCheckValue(hashtable, hashvalue)))
{
/* no matches; check for possible outer-join fill */
node->hj_JoinState = HJ_FILL_OUTER_TUPLE;
continue;
}
ExecHashGetBucketAndBatch(hashtable, hashvalue,
&node->hj_CurBucketNo, &batchno);
node->hj_CurSkewBucketNo = ExecHashGetSkewBucket(hashtable,
hashvalue);
Not sure how expensive those two functions (ExecHashGetBucketAndBatch
and ExecHashGetSkewBucket) are, but this seems like a good idea. Haven't
tried that, though, so maybe HJ_FILL_OUTER_TUPLE needs that info or
something like that.
Makes sense?
>
> Also, are you aware of this?
>
> http://www.nus.edu.sg/nurop/2010/Proceedings/SoC/NUROP_Congress_Cheng%20Bin.pdf
>
> It talks about bloom filters for hash joins in PostgreSQL
> specifically. Interestingly, they talk about specific TPC-H queries.
Interesting. The way that paper uses bloom filters is very different
from what I do in the patch. They build the bloom filters and then
propagate them into the scan nodes to eliminate the tuples early.
The problem is they'd be facing mostly the same problems with sizing the
bloom filter I'm facing in the patch. The only way they managed to get
around them is that they used a dataset with fixed size (1GB, which is a
bit small), and bloom 1kB or 8kB bloom filters.
I suspect they'd get much worse results with datasets of "reasonable"
size (say, 100GB or more) because the bloom fixed-size filters would
stop being effective.
>
> BTW, I think code like this needs better comments:
Yeah.
>
> +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;
>
> Have you experimentally verified that you get the expected probability
> of false positives in practice?
I have seen that when the bloom filter is properly sized, and the data
set is not somehow skewed, the bloom filters have about the right false
positive rate.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-10 21:11 Tomas Vondra <tomas.vondra@2ndquadrant.com>
parent: Peter Geoghegan <pg@heroku.com>
0 siblings, 0 replies; 26+ messages in thread
From: Tomas Vondra @ 2016-01-10 21:11 UTC (permalink / raw)
To: Peter Geoghegan <pg@heroku.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
Hi,
On 01/10/2016 05:11 AM, Peter Geoghegan wrote:
> On Sat, Jan 9, 2016 at 11:02 AM, Tomas Vondra
> <tomas.vondra@2ndquadrant.com> wrote:
>> Which means the "dim.r" column has 100 different values (0-99) with uniform
>> distribution. So e.g. "WHERE r < 15" matches 15%.
>
> I think that the use of a uniform distribution to demonstrate this
> patch is a bad idea, unless you want to have a conversation about the
> worst case.
>
> Look at the use cases for bloom filters in general. They're almost
> all some variation on the same theme: checking a bloom filter
> inexpensively, to avoid an expensive cache miss (of some fashion).
Right.
> The Google Chrome web browser uses a bloom filter for malicious URLs.
FWIW I don't think Chrome is using bloom filter for this purpose
anymore. Chromium certainly does not (it's using PrefixSet instead).
> It usually avoids consulting Google's servers about whether or not
> any given URL that is visited is malicious by using the bloom filter.
> This is effective in large part because the top 100 websites ranked
> by popularity have a huge falloff in popularity as you go down the
> list. It looks like a Zipfian distribution, and so I imagine they get
> pretty far with a very small bloom filter, even though in theory the
> chances of any given valid URL resulting in a cache miss is very
> high.
I'm not familiar with how Chrome used bloom filters, but I'd expect them
to be very careful about false positives (and also false negatives, as
the bloom filter can't contain all malicious URLs).
My assumptions is that they've been able to make that work because they
do have detailed stats about how frequently people visit those URLs, and
use that when building the bloom filter. But we don't have such
information in hashjoin.
>
> Generally, uniform distributions are rare in a non-canonical list of
> things, like a hash join outer relation's attribute.
Well, I'm not claiming testing uniform distribution is enough, but
surely it's one of the cases we should handle just fine.
The problem with non-uniform cases is that it really depends on the
outer side of the join.
For example let's say the hash table contains 1000 values, and the bloom
filter has 1% false positive rate. But let's assume that the outer side
has a value that triggers the false positive rate, and that it's
actually 99% of the outer table. Suddenly, you have 99% false positive
rate, rendering the bloom filter pointless.
I don't think this is fixable while creating the bloom filter. All we
can do is watch the bloom filter lookups and disable the bloom filter
once the false positive rate reaches some threshold.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-01-10 21:38 David Rowley <david.rowley@2ndquadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 0 replies; 26+ messages in thread
From: David Rowley @ 2016-01-10 21:38 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Peter Geoghegan <pg@heroku.com>; Simon Riggs <simon@2ndquadrant.com>; pgsql-hackers
On 11 January 2016 at 09:30, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:
> Hi,
>
> On 01/10/2016 04:03 AM, Peter Geoghegan wrote:
>
>> On Sat, Jan 9, 2016 at 4:08 PM, Peter Geoghegan <pg@heroku.com> wrote:
>
> Also, are you aware of this?
>>
>>
>> http://www.nus.edu.sg/nurop/2010/Proceedings/SoC/NUROP_Congress_Cheng%20Bin.pdf
>>
>> It talks about bloom filters for hash joins in PostgreSQL
>> specifically. Interestingly, they talk about specific TPC-H queries.
>>
>
> Interesting. The way that paper uses bloom filters is very different from
> what I do in the patch. They build the bloom filters and then propagate
> them into the scan nodes to eliminate the tuples early.
>
>
That does sound interesting, but unless I'm somehow mistaken, I guess to do
that you'd have to abandon the more efficient hashing of the hash value
that you're doing in the current patch, and hash the complete value in the
scan node, then hash them again if they make it into the hash join node.
That does not sound like it would be a win if hashing longer varlana values.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: WIP: bloom filter in Hash Joins with batches
@ 2016-02-08 20:02 Alvaro Herrera <alvherre@2ndquadrant.com>
parent: Tomas Vondra <tomas.vondra@2ndquadrant.com>
5 siblings, 0 replies; 26+ messages in thread
From: Alvaro Herrera @ 2016-02-08 20:02 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: pgsql-hackers
I'm closing this as returned-with-feedback; AFAICS even the last version
submitted is still in research stage. Please resubmit once you make
further progress.
Thanks,
--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 26+ messages in thread
end of thread, other threads:[~2016-02-08 20:02 UTC | newest]
Thread overview: 26+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2015-12-15 22:30 WIP: bloom filter in Hash Joins with batches Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-17 09:50 ` Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>
2015-12-17 15:34 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-28 02:15 ` David Rowley <david.rowley@2ndquadrant.com>
2015-12-28 10:23 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-28 10:38 ` David Rowley <david.rowley@2ndquadrant.com>
2015-12-28 10:44 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-28 10:52 ` David Rowley <david.rowley@2ndquadrant.com>
2015-12-28 11:18 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-17 10:44 ` Simon Riggs <simon@2ndQuadrant.com>
2015-12-17 16:00 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-24 13:51 ` Simon Riggs <simon@2ndQuadrant.com>
2015-12-24 16:55 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2016-01-09 19:02 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2016-01-10 00:08 ` Peter Geoghegan <pg@heroku.com>
2016-01-10 03:03 ` Peter Geoghegan <pg@heroku.com>
2016-01-10 20:30 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2016-01-10 21:38 ` David Rowley <david.rowley@2ndquadrant.com>
2016-01-10 19:12 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2016-01-10 04:11 ` Peter Geoghegan <pg@heroku.com>
2016-01-10 21:11 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-20 04:46 ` Oleg Bartunov <obartunov@gmail.com>
2015-12-20 17:18 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2015-12-24 11:43 ` Aleksander Alekseev <a.alekseev@postgrespro.ru>
2015-12-31 20:38 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2016-02-08 20:02 ` Alvaro Herrera <alvherre@2ndquadrant.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox