Module bloom 

Runtime Bloom Filter Propagation for Join Optimization

This module implements bloom filters that are built during hash join’s build phase and can be pushed down to the probe side’s scan to filter rows early.

How It Works

1. During hash join build phase, we build a bloom filter of join keys
2. The bloom filter is propagated (“pushed down”) to the probe side
3. Probe side scan uses the bloom filter to skip rows that definitely won’t match
4. Only potential matches are sent to the actual join

Benefits

• I/O Reduction: Filter rows before reading from storage
• Memory Reduction: Fewer rows materialized in probe pipeline
• CPU Reduction: Skip hash probes for non-matching rows

Example

SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id
WHERE c.country = 'US'

Without bloom filter: Read all orders, probe against customers hash table With bloom filter: Only read orders whose customer_id MIGHT be in the filtered customers

RadixDB-Specific: Edge Computing Optimization

We use a compact bloom filter design optimized for:

• Small memory footprint (suitable for edge devices)
• Fast canonical Value hashing
• Configurable false positive rate based on available memory

Structs

BloomEffectivenessTracker

Tracks the two outcomes directly observable at the Bloom boundary.

BloomFilter

A space-efficient probabilistic data structure for set membership testing

BloomFilterBuilder

Builder for creating bloom filters during hash join build phase

BloomFilterStats

Statistics about a bloom filter

RuntimeBloomFilter

A bloom filter with metadata for runtime propagation