Bloomfilter Alternatives

bloomfilter reviews and mentions

• Word-Aligned Bloom Filters
  5 projects | news.ycombinator.com | 3 Oct 2021

  > 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.

  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 (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...