Skip to main content

Sbbf

Struct Sbbf 

Source
pub struct Sbbf(Vec<Block>);
Expand description

A split block Bloom filter (SBBF).

An SBBF partitions its bit space into fixed-size 256-bit (32-byte) blocks, each fitting in a single CPU cache line. Each block contains eight 32-bit words, aligned with SIMD lanes for parallel bit manipulation. When checking membership, only one block is accessed per query, eliminating the cache-miss penalty of standard Bloom filters.

§Sizing and folding

Filters are initially sized for a maximum expected number of distinct values (NDV) via Sbbf::new_with_ndv_fpp. After all values are inserted, the filter is compacted by calling Sbbf::fold_to_target_fpp, which folds the filter down to the smallest size that still meets the target false positive probability.

The creation of this structure is based on the crate::file::properties::BloomFilterProperties struct set via crate::file::properties::WriterProperties and is thus hidden by default.

Tuple Fields§

§0: Vec<Block>

Implementations§

Source§

impl Sbbf

Source

pub fn new_with_ndv_fpp(ndv: u64, fpp: f64) -> Result<Self, ParquetError>

Create a new Sbbf with given number of distinct values and false positive probability. Will return an error if fpp is greater than or equal to 1.0 or less than 0.0.

Source

pub fn new_with_num_of_bytes(num_bytes: usize) -> Self

Create a new Sbbf with given number of bytes, the exact number of bytes will be adjusted to the next power of two bounded by BITSET_MIN_LENGTH and BITSET_MAX_LENGTH.

Source

pub fn new(bitset: &[u8]) -> Self

Creates a new Sbbf from a raw byte slice.

Source

pub fn write<W: Write>(&self, writer: W) -> Result<(), ParquetError>

Write the bloom filter data (header and then bitset) to the output. This doesn’t flush the writer in order to boost performance of bulk writing all blocks. Caller must remember to flush the writer. This method usually is used in conjunction with Self::from_bytes for serialization/deserialization.

Source

pub fn write_bitset<W: Write>(&self, writer: W) -> Result<(), ParquetError>

Write the bitset in serialized form to the writer.

Source

fn header(&self) -> BloomFilterHeader

Create and populate BloomFilterHeader from this bitset for writing to serialized form

Source

pub fn read_from_column_chunk<R: ChunkReader>( column_metadata: &ColumnChunkMetaData, reader: &R, ) -> Result<Option<Self>>

Read a Bloom filter from existing column-chunk metadata.

The metadata and reader must refer to the same file. A missing offset returns None without I/O. Invalid metadata, malformed filters, and read failures return an error.

When the total filter length is present, one range is fetched. Otherwise, the header prefix and bitset are fetched separately.

Source

pub async fn read_from_column_chunk_async<R: AsyncFileReader + ?Sized>( column_metadata: &ColumnChunkMetaData, reader: &mut R, ) -> Result<Option<Self>>

Read a Bloom filter asynchronously from existing column-chunk metadata.

The metadata and reader must refer to the same file.

A missing Bloom filter offset returns None without performing I/O. Invalid metadata, malformed filters, and read failures return an error.

When the total filter length is present, one range is fetched. Otherwise, this may perform additional fetches.

Source

pub(crate) async fn read_from_column_chunk_with_fetch<F: MetadataFetch>( column_metadata: &ColumnChunkMetaData, fetch: F, ) -> Result<Option<Self>>

Source

fn hash_to_block_index(&self, hash: u64) -> usize

Map a 64-bit hash to a block index in [0, num_blocks).

Uses the “multiply-and-shift” trick (a fast alternative to modulo):

  upper32 = hash >> 32           // take the top 32 bits of the hash
  index   = (upper32 * N) >> 32  // ∈ [0, N)  where N = num_blocks

Why this matters for folding (Lemma 1): when N is a power of two and you halve it to N/2, the index also halves:

  index_N   = (upper32 * N)   >> 32
  index_N/2 = (upper32 * N/2) >> 32 = index_N / 2  (integer division)

So the block that held hash h in the big filter is at index / 2 in the half-sized filter — exactly where fold ORs it.

Source

pub fn insert<T: AsBytes + ?Sized>(&mut self, value: &T)

Insert an AsBytes value into the filter

Source

pub fn insert_hash(&mut self, hash: u64)

Inserts a precomputed 64-bit hash.

The filter can hold hashes from any well-mixed 64-bit hash function, so values can be hashed in bulk with the caller’s own hash function (for example, a columnar hash of a multi-column key). Self::check only finds values whose hashes were computed as the Parquet specification requires (xxHash64, seed 0, of the plain encoding); use Self::check_hashes with the same hash function instead.

Only write a filter to a Parquet file (with Self::write) if every hash was computed as the specification requires. The header always names xxHash64, so readers would get false negatives and skip row groups that hold matching rows.

§Panics

Panics if the filter has no blocks. Self::new returns such a filter for a bitset shorter than 32 bytes.

Source

pub fn check<T: AsBytes + ?Sized>(&self, value: &T) -> bool

Check if an AsBytes value is probably present or definitely absent in the filter

value must have the Parquet physical type of the column. To check a filter written by ArrowWriter with Arrow values, which may have been converted to a different type before they were written, use ArrowSbbf.

Source

fn check_hash(&self, hash: u64) -> bool

Check if a hash is in the filter. May return true for values that was never inserted (“false positive”) but will always return false if a hash has not been inserted.

Source

fn check_hash_branch_free(&self, hash: u64) -> bool

Same result as Self::check_hash, without data-dependent branches.

Source

pub fn check_hashes(&self, hashes: &[u64]) -> BooleanBuffer

Checks precomputed 64-bit hashes (see Self::insert_hash).

Bit i of the result is set if hashes[i] may be in the filter. A filter with no blocks contains nothing, so every bit is unset.

Each check tests all 8 bits of its block without an early exit, so it has no data-dependent branches. This is typically faster than checking one hash at a time when hits and misses are mixed (and the branch predictor cannot learn the pattern), and slightly slower when nearly every hash misses, where the early exit pays off.

Source

pub fn union(&mut self, other: &Sbbf) -> Result<(), ParquetError>

Adds the values of other to this filter, so that afterwards it contains every value that either filter contained.

other must have at least as many blocks as this filter, and a multiple of them. When it has more, it is folded to the size of this filter on the fly (see Self::fold_to_target_fpp), without changing other. Folding and union commute: the result is the same as inserting the values of both filters into one filter and folding it to this size. This lets independent filters (for example, one per thread) be built and then merged.

Both filters must have been populated with the same hash function (the Parquet xxHash64 used by Self::insert, or the same function used for Self::insert_hash); otherwise the result is meaningless. This cannot be checked.

Returns an error if the sizes are incompatible, including if this filter has no blocks.

§Example
// One filter per partition, filled with precomputed hashes
let mut a = Sbbf::new_with_num_of_bytes(1024);
a.insert_hash(0x0123_4567_89ab_cdef);
let mut b = Sbbf::new_with_num_of_bytes(4096);
b.insert_hash(0xfedc_ba98_7654_3210);

// `b` has 4 times as many blocks as `a`, so it is folded on the fly
a.union(&b).unwrap();
let found = a.check_hashes(&[0x0123_4567_89ab_cdef, 0xfedc_ba98_7654_3210]);
assert!(found.value(0) && found.value(1));

// A smaller filter cannot be unioned into a larger one
assert!(b.union(&a).is_err());
Source

pub(crate) fn estimated_memory_size(&self) -> usize

Return the total in memory size of this bloom filter in bytes

Source

pub fn num_blocks(&self) -> usize

Returns the number of blocks in this bloom filter.

Source

pub fn estimated_fpp(&self) -> f64

Estimate the false positive probability (FPP) of this filter at its current size.

This is the same estimate Self::fold_to_target_fpp uses to choose how far to fold.

This lets a caller inspect a filter before folding or writing it, for example to discard a filter that already exceeds its target FPP. Returns 1.0 for a filter with no blocks.

Source

fn average_fill(&self) -> f64

Average fraction of bits set per block. The filter must have at least one block.

Source

pub fn fold_to_target_fpp(&mut self, target_fpp: f64)

Fold the bloom filter down to the smallest size that still meets the target FPP (False Positive Percentage).

Folds the filter by merging groups of adjacent blocks via bitwise OR, where each fold level halves the number of blocks. The fold count is chosen as the maximum number of folds whose estimated FPP stays within target_fpp. The filter stops at a minimum size of 1 block (32 bytes).

§How it works

SBBFs use multiplicative hashing for block selection:

block_index = ((hash >> 32) * num_blocks) >> 32

A single fold halves the block count: when num_blocks is halved, the new index becomes floor(original_index / 2), so blocks 2i and 2i+1 map to the same position. More generally, k folds reduce the block count by 2^k, merging groups of 2^k adjacent blocks in a single pass:

folded[i] = blocks[i*2^k] | blocks[i*2^k + 1] | ... | blocks[i*2^k + 2^k - 1]

This differs from standard Bloom filter folding, which merges the two halves (B[i] | B[i + m/2]) because standard filters use modular hashing where h(x) mod (m/2) maps indices i and i + m/2 to the same position.

§Correctness

Folding never introduces false negatives. Every bit that was set in the original filter remains set in the folded filter (via bitwise OR). The only effect is a controlled increase in FPP as set bits from different blocks are merged together. This is was originally proven in Sailhan & Stehr 2012 for standard bloom filters and is empirically demonstrated for SBBFs in Lemma 1 and Lemma 2 of the tests.

§References
Source

fn num_folds_for_target_fpp(&self, target_fpp: f64) -> u32

Determine how many folds can be applied without exceeding target_fpp.

Computes the average per-block fill rate in a single pass (no allocation), then analytically estimates the FPP at each fold level.

When two blocks with independent fill rate f are OR’d, the expected fill of the merged block is 1 - (1-f)^2. After k folds (merging 2^k blocks):

f_k = 1 - (1 - f)^(2^k)

SBBF membership checks perform k=8 bit checks within one 256-bit block, so the estimated FPP at fold level k is f_k^8.

Source

fn fold_n(&mut self, num_folds: u32)

Fold the filter num_folds times in a single pass.

Merges groups of 2^num_folds adjacent blocks via bitwise OR, producing len / 2^num_folds output blocks. The original allocation is reused.

§Panics

Panics if num_folds is 0 or would reduce the filter below 1 block.

Source

pub fn from_bytes(bytes: &[u8]) -> Result<Self, ParquetError>

Reads an Sbbf from Thrift encoded bytes.

Returns an error if the header is malformed, the bitset is not a positive multiple of 32 bytes, or its size does not match the header.

§Examples
// In a real application, you would read serialized bloom filter bytes from a cache.
// This example demonstrates the deserialization process.
// Assuming you have bloom filter bytes from a Parquet file:
let bloom_filter = Sbbf::from_bytes(&serialized_bytes)?;
// Now you can use the bloom filter to check for values
if bloom_filter.check(&"some_value") {
    println!("Value might be present (or false positive)");
} else {
    println!("Value is definitely not present");
}

Trait Implementations§

Source§

impl Clone for Sbbf

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for Sbbf

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl Forget for Sbbf

§

impl Freeze for Sbbf

§

impl Move for Sbbf

§

impl RefUnwindSafe for Sbbf

§

impl Send for Sbbf

§

impl Sync for Sbbf

§

impl Unpin for Sbbf

§

impl UnsafeUnpin for Sbbf

§

impl UnwindSafe for Sbbf

Blanket Implementations§

§

impl<T> Allocation for T
where T: RefUnwindSafe + Send + Sync,

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
§

impl<ST, DT> CastableFrom<ST, Initialized, Initialized> for DT
where ST: ?Sized, DT: ?Sized,

§

impl<ST, DT> CastableFrom<ST, Uninit, Uninit> for DT
where ST: ?Sized, DT: ?Sized,

Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

§

impl<T> Read<Exclusive, BecauseExclusive> for T
where T: ?Sized,

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<T> Ungil for T
where T: Send,