apache / apache/gluten

Bloom filter optimization: Port Spark's BloomFilter implementation to Velox

Open
#11,771 4 comments 2 reactions 0 assignees View on GitHub
enhancement
Dominant language
Scala
Stars
1.6k
Forks
657
Avg merge
2d 21h
Merged PRs (30d)
85

Description

### Description

Bloom Filter Distribution in Spark and Velox

Current Status:

Spark Bloom Filter:
Spark implements Bloom filters with multiple hash functions. The number of hash functions is calculated based on the expected number of elements and the desired false positive rate. This approach is memory efficient but introduces overhead when computing multiple hash functions for each element.

Velox Bloom Filter:
Velox currently uses a simpler Bloom filter implementation. While efficient for small datasets, it lacks the flexibility of controlling the number of hash functions independently, which can lead to suboptimal false positive rates or unnecessary computational overhead.

Proposed Improvement:

Implement a native Bloom filter in Velox similar to Spark’s design:

Support multiple hash functions

Optimize memory allocation for large datasets.

Reduce false positive rates by matching the hash function count to the dataset size and expected error rate.

Maintain API compatibility for existing Velox operators that rely on Bloom filters.

Benefits:

Align Velox’s Bloom filter behavior with Spark, improving interoperability for query execution plans.

Solve the current hash function number issue in Velox, where the fixed or suboptimal hash function count can impact performance and accuracy.

Enable more efficient distributed filtering in Velox-powered pipelines.

### Gluten version

None

Contributor guide

Open the contributing guide

Research direction

Compare Spark's Bloom filter design with Velox's current Bloom filter implementation, beginning with the existing filter code and the operators that depend on it. Define how multiple hash functions, memory sizing, false-positive targets, and API compatibility should work before implementing; done means the behavior matches the intended Spark design and existing operators remain compatible.

Written by the indexing model from the issue text.

Assessment

Domain
data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.