parquet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From b...@apache.org
Subject [parquet-format] branch master updated: PARQUET-1630: Clarify the Bloom filter algorithm (#147)
Date Fri, 09 Aug 2019 00:19:01 GMT
This is an automated email from the ASF dual-hosted git repository.

blue pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/parquet-format.git


The following commit(s) were added to refs/heads/master by this push:
     new fa53342  PARQUET-1630: Clarify the Bloom filter algorithm (#147)
fa53342 is described below

commit fa53342948f79a71d040402a9b44b5413e7bfa6a
Author: Jim Apple <jbapple@apache.org>
AuthorDate: Thu Aug 8 17:18:56 2019 -0700

    PARQUET-1630: Clarify the Bloom filter algorithm (#147)
    
    The specific questions answered from
    https://lists.apache.org/thread.html/82d2e50f8c1007720564c5dc64aeae7947e949f3954a83436dc36760@%3Cdev.parquet.apache.org%3E
    are
    
    How is the bloom filter block selected from the 32 most-significant
    bits from of the hash function? These details must be in the spec and
    not in papers linked from the spec.
    
    How is the number of blocks determined? From the overall filter size?
    
    I think that the exact procedure for a lookup in each block should be
    covered in a section, followed by a section for how to perform a look
    up in the multi-block filter. The wording also needs to be cleaned up
    so that it is always clear whether the filter that is referenced is a
    block or the multi-block filter.
    
    The spec should give more detail on how to choose the number of blocks
    and on false positive rates. The sentence with “11.54 bits for each
    distinct value inserted into the filter” is vague: is this the
    multi-block filter? Why is a 1% false-positive rate “recommended”?
    
    I think it is okay to use 0.5% as each block’s false-positive rate,
    but then this should state how to achieve an overall false-positive
    rate as a function of the number of distinct values.
---
 BloomFilter.md | 251 ++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 177 insertions(+), 74 deletions(-)

diff --git a/BloomFilter.md b/BloomFilter.md
index e51b412..8ce22ae 100644
--- a/BloomFilter.md
+++ b/BloomFilter.md
@@ -33,11 +33,6 @@ overapproximates a set. It can respond to membership queries with either
"defini
 "probably yes", where the probability of false positives is configured when the filter is
 initialized. Bloom filters do not have false negatives.
 
-A Bloom filter typically contains a bit array of `m` bits, `k` different hash functions,
-and `n` elements inserted. Each of hash functions maps or hashes some set element to one
of the
-`m` array positions, generating a uniform random distribution. To add an element, feed it
to each
-of the `k` hash functions to get `k` array positions. Set the bits at all these positions
to 1. 
-
 Because Bloom filters are small compared to dictionaries, they can be used for predicate
 pushdown even in columns with high cardinality and when space is at a premium.
 
@@ -49,87 +44,195 @@ pushdown even in columns with high cardinality and when space is at a
premium.
   filters attached or when executing non-selective queries.
 
 ### Technical Approach
-The initial Bloom filter algorithm in Parquet is implemented using a combination of two
-Bloom filter techniques.
-
-First, the block Bloom filter algorithm from Putze et al.'s [Cache-, Hash- and Space-Efficient
-Bloom filters](http://algo2.iti.kit.edu/documents/cacheefficientbloomfilters-jea.pdf) is
used.
-The block Bloom filter consists of a sequence of small Bloom filters, each of which can fit
-into one cache-line. For best performance, those small Bloom filters are loaded into memory
-cache-line-aligned. For each potential element, the first hash value selects the Bloom filter
block
-to be used. Additional hash values are then used to set or test bits as usual, but only inside
-this one block. As for Parquet's initial implementation, each block is 256 bits. When inserting
or
-finding value, the first hash of that value is used to index into the array of blocks and
pick a
-single one. This single block is then used for the remaining part of the operation.
-
-Second, the remaining part of the operation within the single block uses the folklore split
Bloom
-filter technique, as described in section 2.1 of [Network Applications of Bloom Filters:
-A Survey](https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf). Instead of having
one
-array of size `m` shared among all the hash functions, each hash function has a range of
`m/k`
-consecutive bit locations disjoint from all the others. The total number of bits is still
-`m`, but the bits are divided equally among the `k` hash functions. This approach
-can be useful for implementation reasons, for example, dividing the bits among the hash functions
-may make parallelization of array accesses easier and take utilization of SSE. As for Parquet's
-implementation, it divides the 256 bits in each block up into eight contiguous 32-bit lanes
and
-sets or checks one bit in each lane.
-
-#### Algorithm
-In the initial algorithm, the most significant 32 bits from the hash value are used as the
-index to select a block from bitset. The lower 32 bits of the hash value, along with eight
-constant salt values, are used to compute the bit to set in each lane of the block.
-The salt values are used to construct following different hash functions as described in
-[Multiplicative hashing](https://en.wikipedia.org/wiki/Hash_function#Multiplicative_hashing):
-
-hash<sub>i</sub>(x) = salt<sub>i</sub> * x >> y
-
-Since the target hash value is `[0, 31]`, so we right shift `y = 27` bits. As a result, eight
-hash values, which are indexes of the tiny bloom filter, are generated.
-
-```c
-// 8 SALT values used to compute bit pattern
-static const uint32_t SALT[8] = {0x47b6137bU, 0x44974d91U, 0x8824ad5bU, 0xa2b7289dU,
-  0x705495c7U, 0x2df1424bU, 0x9efc4947U, 0x5c6bfb31U};
-
-// key: the lower 32 bits of hash result
-// mask: the output bit pattern for a tiny Bloom filter
-void Mask(uint32_t key, uint32_t mask[8]) {
-  for (int i = 0; i < 8; ++i) {
-    mask[i] = key * SALT[i];
+
+The section describes split block Bloom filters, which is the first
+(and, at time of writing, only) Bloom filter representation supported
+in Parquet.
+
+First we will describe a "block". This is the main component split
+block Bloom filters are composed of.
+
+Each block is 256 bits, broken up into eight contiguous "words", each
+consisting of 32 bits. Each word is thought of as an array of bits;
+each bit is either "set" or "not set".
+
+When initialized, a block is "empty", which means each of the eight
+component words has no bits set. In addition to initialization, a
+block supports two other operations: `block_insert` and
+`block_check`. Both take a single unsigned 32-bit integer as input;
+`block_insert` returns no value, but modifies the block, while
+`block_check` returns a boolean. The semantics of `block_check` are
+that it must return `true` if `block_insert` was previously called on
+the block with the same argument, and otherwise it returns `false`
+with high probability. For more details of the probability, see below.
+
+The operations `block_insert` and `block_check` depend on some
+auxiliary artifacts. First, there is a sequence of eight odd unsigned
+32-bit integer constants called the `salt`. Second, there is a method
+called `mask` that takes as its argument a single unsigned 32-bit
+integer and returns a block in which each word has exactly one bit
+set.
+
+```
+unsigned int32 salt[8] = {0x47b6137bU, 0x44974d91U, 0x8824ad5bU,
+                          0xa2b7289dU, 0x705495c7U, 0x2df1424bU,
+                          0x9efc4947U, 0x5c6bfb31U}
+
+block mask(unsigned int32 x) {
+  block result
+  for i in [0..7] {
+    unsigned int32 y = x * salt[i]
+    result.getWord(i).setBit(y >> 27)
   }
-  for (int i = 0; i < 8; ++i) {
-    mask[i] = mask[i] >> 27;
+  return result
+}
+```
+
+Since there are eight words in the block and eight integers in the
+salt, there is a correspondence between them. To set a bit in the nth
+word of the block, `mask` first multiplies its argument by the nth
+integer in the `salt`, keeping only the least significant 32 bits of
+the 64-bit product, then divides that 32-bit unsigned integer by 2 to
+the 27th power, denoted above using the C language's right shift
+operator "`>>`". The resulting integer is between 0 and 31,
+inclusive. That integer is the bit that gets set in the word in the
+block.
+
+From the `mask` operation, `block_insert` is defined as setting every
+bit in the block that was also set in the result from mask. Similarly,
+`block_check` returns `true` when every bit that is set in the result
+of `mask` is also set in the block.
+
+```
+void block_insert(block b, unsigned int32 x) {
+  block masked = mask(x)
+  for i in [0..7] {
+    for j in [0..31] {
+      if (masked.getWord(i).isSet(j)) {
+        b.getWord(i).setBit(j)
+      }
+    }
   }
-  for (int i = 0; i < 8; ++i) {
-    mask[i] = UINT32_C(1) << mask[i];
+}
+```
+
+```
+boolean block_check(block b, unsigned int32 x) {
+  block masked = mask(x)
+  for i in [0..7] {
+    for j in [0..31] {
+      if (masked.getWord(i).isSet(j)) {
+        if (not b.getWord(i).setBit(j)) {
+          return false
+        }
+      }
+    }
   }
+  return true
+}
+```
+
+The reader will note that a block, as defined here, is actually a
+special kind of Bloom filter. Specifically it is a "split" Bloom
+filter, as described in section 2.1 of [Network Applications of Bloom
+Filters: A
+Survey](https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf). The
+use of multiplication by an odd constant and then shifting right is a
+method of hashing integers as described in section 2.2 of
+Dietzfelbinger et al.'s [A reliable randomized algorithm for the
+closest-pair
+problem](http://hjemmesider.diku.dk/~jyrki/Paper/CP-11.4.1997.pdf).
+
+This closes the definition of a block and the operations on it.
+
+Now that a block is defined, we can describe Parquet's split block
+Bloom filters. A split block Bloom filter (henceforth "SBBF") is
+composed of `z` blocks, where `z` is a power of two greater than or
+equal to one and less than 2 to the 27th power. When an SBBF is
+initialized, each block in it is initialized, which means each bit in
+each word in each block in the SBBF is unset.
+
+In addition to initialization, an SBBF supports an operation called
+`filter_insert` and one called `filter_check`. Each takes as an
+argument a 64-bit unsigned integer; `filter_check` returns a boolean
+and `filter_insert` does not return a value, but does modify the SBBF.
+
+The `filter_insert` operation first uses the most significant 32 bits
+of its argument, modulo the number of blocks, to select a block to
+operate on. It then uses the least significant 32 bits of the argument
+to `filter_insert` as an argument to `block_insert` called on that
+block.
+
+The `filter_check` operation uses the same method as `filter_insert`
+to select a block to operate on, then uses the least significant 32
+bits of its argument as an argument to `block_check` called on that
+block, returning the result.
+
+In the pseudocode below, the modulus operator is represented with the C
+language's "`%`" operator. The "`>>`" operator is used to denote the
+conversion of an unsigned 64-bit integer to an unsigned 32-bit integer
+containing only the most significant 32 bits, and C's cast operator
+"`(unsigned int32)`" is used to denote the conversion of an unsigned
+64-bit integer to an unsigned 32-bit integer containing only the least
+significant 32 bits.
+
+```
+void filter_insert(SBBF filter, unsigned int64 x) {
+  block b = filter.getBlock((x >> 32) % filter.numberOfBlocks());
+  block_insert(b, (unsigned int32)x)
 }
+```
 
 ```
+boolean filter_check(SBBF filter, unsigned int64 x) {
+  block b = filter.getBlock((x >> 32) % filter.numberOfBlocks());
+  return block_check(b, (unsigned int32)x)
+}
+```
+
+The use of blocks is from Putze et al.'s [Cache-, Hash- and
+Space-Efficient Bloom
+filters](http://algo2.iti.kit.edu/documents/cacheefficientbloomfilters-jea.pdf)
 
-#### Hash Function
-The function used to hash values in the initial implementation is
-[xxHash](https://cyan4973.github.io/xxHash/), using the function XXH64 with a
-seed of 0 and [following the specification version
+To use an SBBF for values of arbitrary Parquet types, we apply a hash
+function to that value - at the time of writing,
+[xxHash](https://cyan4973.github.io/xxHash/), using the function XXH64
+with a seed of 0 and [following the specification version
 0.1.1](https://github.com/Cyan4973/xxHash/blob/v0.7.0/doc/xxhash_spec.md).
 
-#### Build a Bloom filter
-The fact that exactly eight bits are checked during each lookup means that these filters
-are most space efficient when used with an expected false positive rate of about
-0.5%. This is achieved when there are about 11.54 bits for every distinct value inserted
-into the filter.
+#### Sizing an SBBF
 
-To calculate the size the filter should be for another false positive rate `p`, use the
-following formula. The output is in bits per distinct element:
+The `check` operation in SBBFs can return `true` for an argument that
+was never inserted into the SBBF. These are called "false
+positives". The "false positive probabilty" is the probability that
+any given hash value that was never `insert`ed into the SBBF will
+cause `check` to return `true` (a false positive). There is not a
+simple closed-form calculation of this probability, but here is an
+example:
 
-```c
-c = -8 / log(1 - pow(p, 1.0 / 8))
-```
+A filter that uses 1024 blocks and has had 26,214 hash values
+`insert`ed will have a false positive probabilty of around 1.26%. Each
+of those 1024 blocks occupies 256 bits of space, so the total space
+usage is 262,144. That means that the ratio of bits of space to hash
+values is 10-to-1. Adding more hash values increases the denominator
+and lowers the ratio, which increases the false positive
+probability. For instance, inserting twice as many hash values
+(52,428) decreases the ratio of bits of space per hash value inserted
+to 5-to-1 and increases the false positive probability to
+18%. Inserting half as many hash values (13,107) increases the ratio
+of bits of space per hash value inserted to 20-to-1 and decreases the
+false positive probability to 0.04%.
+
+Here are some sample values of the ratios needed to achieve certain
+false positive rates:
 
-In the real scenario, the size of the Bloom filter and the false positive rate may vary from
-different implementations. It is recommended to set false positive to 1% so that a Bloom
filter
-with 1.2MB size can contain one million distinct values, which should satisfy most cases
according
-to default row group size. It is also recommended to expose the ability for setting these
-parameters to end users.
+| Bits of space per `insert` | False positive probability |
+| -------------------------- | -------------------------- |
+|                        6.0 | 10 %                       |
+|                       10.5 |  1 %                       |
+|                       16.9 |  0.1 %                     |
+|                       26.4 |  0.01 %                    |
+|                       41   |  0.001 %                   |
 
 #### File Format
 The Bloom filter data of a column chunk, which contains the size of the filter in bytes,
the


Mime
View raw message