I feel like he skipped over something. Which part of his algorithm requires “about 12 bits” instead of about 10? He’s storing 5 entries per word which is 12.8 bits per entry (which is quite a rounding error). Why not 6 entries at 10.67 bits per entry?
Word-Aligned Bloom Filters
61–70 of 82 posts
Re: Word-Aligned Bloom Filters
#62I'm really suspicious about whether this would really work out in most workloads. On modern architectures, it's the random memory reference that kills performance. Predictive pre-fetching in the pipeline has a impossible time figuring out what to get ready in the caches with random lookups; it's not like a linear sweep. This style of bloom-filter needs to be quite large, and it pulls only one cache-line in per key lo…
> I'm really suspicious about whether this would really work out in most workloads. What kinds of workloads are those? Workloads where the Bloom filter itself fits in cache? > On modern architectures, it's the random memory reference that kills performance Yeah, the whole point of the article is that moving from a traditional Bloom filter to a block Bloom filter is to improve from N random accesses per query/update t…
> to improve from N random accesses per query/update to 1 random access per query/update.
I think their concern is that N (nondependent) random accesses can happen in parallel not much more slowly than 1 random access (assuming good speculation and sufficient memory bandwidth).
Re: Word-Aligned Bloom Filters
#63Earlier quoted context omitted.
let me butcher the concept for you :) say though nummerology you reduce the character values of a name to a number 0-10. Lots of names will reduce to the same number. We take 11 bits and for "jim" we set the first bit. We have only one name in our data set so all other bits are 0. Now if someone types "joe" in the search box and it reduces to 2 we look at the second bit, see it is a zero and know 100% *for sure* that…
Isn't this just similar to hash prefixes and not a true bloom filter?
I did say I'd butcher it. :-) imho one shouldn't be overly attached to an exact implementation but learn to reason about it. You could for example make an array and count how many times each bit was set. A textbook bloomfilter doesn't allow you to remove things but if you count how often a bit was set you obviously can.
Re: Word-Aligned Bloom Filters
#64Oh, that's elegant. If I math right, setting 5 bits in a 64-bit word extends the effective length of the hash function by approximately (5-1) * log_2(64) = (5-1) * 6 = 24 bits. In a simple bloom filter of storage size m bits, the hash functions have length log_2(m). All else being equal, the number of hash functions used -- hence the number of memory reads per lookup -- gets reduced by a factor of log_2(m) / [24 + lo…
Each word in this design is a little bloom filter. It has number of bits (m)=64; number of hashes (k)=5; and going for 1% false positive rate, which per formula (with n being number of items in the filter) in [1] is: fpr = (1 - e ^ -(k * n)/m ) ^ k OP solved for 1% and got n =~ 4. There is exactly 1 hash function (to compute the 64 bit key). 5 bits are pseudo-randomly selected (giving us k=5) and written to an array…
> Each word in this design is a little bloom filter.
It's effectively a hash table of bloom filters.
> So, you either have to keep track of elements assigned to words (3 bits / word to count 0..4), or you compute a probable value to minimize overloaded array elements
One option would be to just directly limit the number of marked bits in each bucket, which seems to correlate better to false positive rate than number of elements per se. (Eg a element with all k indexes equal (marking only one bit) causes less false positives than one with k distinct indexes.) You get 6bits * 4elements = 24bits marked, so just call a bin full if it has popcount >= 24.
Re: Word-Aligned Bloom Filters
#65wild tangent, focusing on the stated example, not the filter implementation:
> Suppose that you are given a database of users where only a small percentage are ‘paying customers’ (say 5% or less). You can write an SQL query to check whether a given user is indeed a paying customer, but it might require a round trip to your database engine. Instead, you would like to hold a small ‘filter’ in memory to quickly check whether the given user is a paying customer.
another way to avoid needing to solve this example filtering problem is to store the data in the database in a way that doesn't require any filtering. e.g. if it is often useful to distinguish paying customers from other kinds of users (sounds plausible), maybe paying customers could be segregated into their own separate table from non-paying users. then there's no need to filter.
this is a rule of thumb that is written about a bit in 'data-oriented design'. instead of operating on collections of heterogeneous entities that are obfuscated behind some facade of commonality, figure out which are the most frequent types of entities and put them in their own collections, where they can be computed upon in homogeneous batches -- with better performance.
c.f. https://www.dataorienteddesign.com/dodbook/dodmain.html
Re: Word-Aligned Bloom Filters
#66At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!
They finally clicked for me after reading about how they're used by the bitcoin network: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch08...
Re: Word-Aligned Bloom Filters
#67wild tangent, focusing on the stated example, not the filter implementation: > Suppose that you are given a database of users where only a small percentage are ‘paying customers’ (say 5% or less). You can write an SQL query to check whether a given user is indeed a paying customer, but it might require a round trip to your database engine. Instead, you would like to hold a small ‘filter’ in memory to quickly check wh…
> maybe paying customers could be segregated into their own separate table from non-paying users.
If you know that, for example, you just need the customer ID and name of paying customers, you can also make an index on (is_paying, customer_id, customer_name).
Any database engine worth its salt will then be able to satisfy such a query entirely from the index without reading any pages from the actual table, making this basically equivalent to the "separate table" approach but without the "administrative" overhead.
Re: Word-Aligned Bloom Filters
#68Earlier quoted context omitted.
Simd convinced me to take college courses in algorithms and to learn higher maths. Things like image decoding rely heavily on doing transformations, and you just have to know the math behind it to an exact point to be able to effectively turn scalar math to vector effectively. Ontop of this you have to identify what can and cannot be vectorized and how it can be integrated. Working in simd isn't too hard In itself on…
Thanks: Any books / blogs you'd recommend?
Reading Agner Fog's writings has taken my optimization to a whole new level.
Re: Word-Aligned Bloom Filters
#69Can anyone explain how the hash function maps to multiple values in the bit vector? I thought functions cant be one to many.
Re: Word-Aligned Bloom Filters
#70I'm really suspicious about whether this would really work out in most workloads. On modern architectures, it's the random memory reference that kills performance. Predictive pre-fetching in the pipeline has a impossible time figuring out what to get ready in the caches with random lookups; it's not like a linear sweep. This style of bloom-filter needs to be quite large, and it pulls only one cache-line in per key lo…
> whether this would really work out in most workloads
> just because it keeps the cache-lines hotter and less likely to be evicted.
Okay, so keeping cache for a bloom filter problem is real - but the real force evicting memory out of the cache line is the next row-group you read + all the other stuff you have to do when you implement this in a database product. Memory bandwidth is contested heavily and the caches will get knocked out every 1024 rows.
So the two things I work with, Apache Hive and Apache Impala switched to a blocked bloom filter at different points in time.
Hive BloomKFilter - https://github.com/apache/hive/blob/master/storage-api/src/j...
Impala/Kudu one - https://github.com/apache/impala/blob/master/be/src/kudu/uti...
The C++ one also has an AVX specialization, while the Java one relies on the JVM to do it (not always) - https://github.com/apache/impala/blob/master/be/src/kudu/uti...
We ran a lot of trivial benchmarks and several benchmarks where the shuffle-join+network (not sort-merge, this is just a partitioned hash join) generates a bloom filter (a semijoin) before sending rows out and the 1-cache line version won out when the bloom filter went slightly over the 1 Million + 5% rate [1].
The regular bloom filter went from (38ns -> 108ns for 1k -> 1m items), while the BloomK stuck at (27ns) despite making room for a million times more items in the bloom. The bloom-1 (which is the 64bit version) underperformed on accuracy (was ~2x faster at 16ns per op, but worse at filtering out items).
[1] - https://github.com/prasanthj/bloomfilter/tree/master/benchma...