parquet/bloom_filter/mod.rs
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! Bloom filter implementation specific to Parquet, as described
6//! in the [spec][parquet-bf-spec].
7//!
8//! # Bloom Filter Size
9//!
10//! Parquet uses the [Split Block Bloom Filter][sbbf-paper] (SBBF) as its bloom filter
11//! implementation. For each column upon which bloom filters are enabled, the offset and length of an SBBF
12//! is stored in the metadata for each row group in the parquet file. The size of each filter is
13//! initialized using a calculation based on the desired number of distinct values (NDV) and false
14//! positive probability (FPP). The FPP for a SBBF can be approximated as<sup>[1][bf-formulae]</sup>:
15//!
16//! ```text
17//! f = (1 - e^(-k * n / m))^k
18//! ```
19//!
20//! Where, `f` is the FPP, `k` the number of hash functions, `n` the NDV, and `m` the total number
21//! of bits in the bloom filter. This can be re-arranged to determine the total number of bits
22//! required to achieve a given FPP and NDV:
23//!
24//! ```text
25//! m = -k * n / ln(1 - f^(1/k))
26//! ```
27//!
28//! SBBFs use eight hash functions to cleanly fit in SIMD lanes<sup>[2][sbbf-paper]</sup>, therefore
29//! `k` is set to 8. The SBBF will spread those `m` bits across a set of `b` blocks that
30//! are each 256 bits, i.e., 32 bytes, in size. The number of blocks is chosen as:
31//!
32//! ```text
33//! b = NP2(m/8) / 32
34//! ```
35//!
36//! Where, `NP2` denotes *the next power of two*, and `m` is divided by 8 to be represented as bytes.
37//!
38//! Here is a table of calculated sizes for various FPP and NDV:
39//!
40//! | NDV | FPP | b | Size (KB) |
41//! |-----------|-----------|---------|-----------|
42//! | 10,000 | 0.1 | 256 | 8 |
43//! | 10,000 | 0.01 | 512 | 16 |
44//! | 10,000 | 0.001 | 1,024 | 32 |
45//! | 10,000 | 0.0001 | 1,024 | 32 |
46//! | 100,000 | 0.1 | 4,096 | 128 |
47//! | 100,000 | 0.01 | 4,096 | 128 |
48//! | 100,000 | 0.001 | 8,192 | 256 |
49//! | 100,000 | 0.0001 | 16,384 | 512 |
50//! | 100,000 | 0.00001 | 16,384 | 512 |
51//! | 1,000,000 | 0.1 | 32,768 | 1,024 |
52//! | 1,000,000 | 0.01 | 65,536 | 2,048 |
53//! | 1,000,000 | 0.001 | 65,536 | 2,048 |
54//! | 1,000,000 | 0.0001 | 131,072 | 4,096 |
55//! | 1,000,000 | 0.00001 | 131,072 | 4,096 |
56//! | 1,000,000 | 0.000001 | 262,144 | 8,192 |
57//!
58//! # Structure: Filter → Blocks → Words → Bits
59//!
60//! An SBBF is an array of **blocks**. Each block is 256 bits (32 bytes),
61//! divided into eight 32-bit **words**. A word is just a `u32` — an array of
62//! 32 individual bits that can each be "set" (1) or "not set" (0).
63//!
64//! ```text
65//! Sbbf (the whole filter)
66//! ┌──────────┬──────────┬──────────┬─── ─── ──┬──────────┐
67//! │ Block 0 │ Block 1 │ Block 2 │ ... │ Block N-1│
68//! └──────────┴──────────┴──────────┴─── ─── ──┴──────────┘
69//! │
70//! ▼
71//! One Block = 256 bits = 8 words
72//! ┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
73//! │ word 0 │ word 1 │ word 2 │ word 3 │ word 4 │ word 5 │ word 6 │ word 7 │
74//! │ (u32) │ (u32) │ (u32) │ (u32) │ (u32) │ (u32) │ (u32) │ (u32) │
75//! └────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘
76//! │
77//! ▼
78//! One Word = 32 individual bits
79//! ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
80//! │0│0│1│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│ ← bit 29 is set
81//! └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
82//! ```
83//!
84//! **Inserting** a value hashes it to a 64-bit number, then:
85//! 1. The upper 32 bits pick which **block** (via `Sbbf::hash_to_block_index`).
86//! 2. The lower 32 bits pick one bit position in each of the 8 **words** (via `Block::mask`).
87//! So each insert sets exactly **8 bits** (one per word) in a single block.
88//!
89//! **Checking** does the same two steps and returns `true` only if all 8 bits
90//! are already set — meaning the value was *probably* inserted (or is a false
91//! positive).
92//!
93//! # Bloom Filter Folding
94//!
95//! After inserting all values into a bloom filter it can be "folded" to minimize it's size.
96//! See [`Sbbf::fold_to_target_fpp`] for details on the algorithm and its mathematical basis.
97//!
98//! [parquet-bf-spec]: https://github.com/apache/parquet-format/blob/master/BloomFilter.md
99//! [sbbf-paper]: https://arxiv.org/pdf/2101.01719
100//! [bf-formulae]: http://tfk.mit.edu/pdf/bloom.pdf
101
102#[cfg(all(feature = "arrow", feature = "async"))]
103use crate::arrow::async_reader::{AsyncFileReader, MetadataFetch};
104use crate::basic::{BloomFilterAlgorithm, BloomFilterCompression, BloomFilterHash};
105use crate::data_type::AsBytes;
106use crate::errors::{ParquetError, Result};
107use crate::file::metadata::ColumnChunkMetaData;
108use crate::file::reader::ChunkReader;
109use crate::parquet_thrift::{
110 ElementType, FieldType, ReadThrift, ThriftCompactInputProtocol, ThriftCompactOutputProtocol,
111 ThriftSliceInputProtocol, WriteThrift, WriteThriftField,
112};
113use crate::{DecodeResult, thrift_struct};
114use bytes::Bytes;
115#[cfg(all(feature = "arrow", feature = "async"))]
116use futures::future::BoxFuture;
117use std::io::Write;
118use std::ops::Range;
119use twox_hash::XxHash64;
120
121mod push;
122pub use push::SbbfPushDecoder;
123
124/// Salt as defined in the [spec](https://github.com/apache/parquet-format/blob/master/BloomFilter.md#technical-approach).
125const SALT: [u32; 8] = [
126 0x47b6137b_u32,
127 0x44974d91_u32,
128 0x8824ad5b_u32,
129 0xa2b7289d_u32,
130 0x705495c7_u32,
131 0x2df1424b_u32,
132 0x9efc4947_u32,
133 0x5c6bfb31_u32,
134];
135
136thrift_struct!(
137/// Bloom filter header is stored at beginning of Bloom filter data of each column
138/// and followed by its bitset.
139///
140pub struct BloomFilterHeader {
141 /// The size of bitset in bytes
142 1: required i32 num_bytes;
143 /// The algorithm for setting bits.
144 2: required BloomFilterAlgorithm algorithm;
145 /// The hash function used for Bloom filter
146 3: required BloomFilterHash hash;
147 /// The compression used in the Bloom filter
148 4: required BloomFilterCompression compression;
149}
150);
151
152/// A single 256-bit block, the basic unit of the Split Block Bloom Filter.
153///
154/// A block is eight contiguous 32-bit **words** (`[u32; 8]`).
155/// Each word is an independent bit-array of 32 positions:
156///
157/// ```text
158/// Block (256 bits total)
159/// ┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
160/// │ word 0 │ word 1 │ word 2 │ word 3 │ word 4 │ word 5 │ word 6 │ word 7 │
161/// │ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│
162/// └────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘
163/// ```
164///
165/// When a value is inserted, [`Block::mask`] picks one bit in each word
166/// (8 bits total), and those bits are OR'd in. When checking, we verify
167/// all 8 bits are set.
168#[derive(Debug, Copy, Clone)]
169#[repr(transparent)]
170struct Block([u32; 8]);
171impl Block {
172 const ZERO: Block = Block([0; 8]);
173
174 /// Produce a block where each of the 8 words has exactly one bit set.
175 ///
176 /// For each word `i` the bit position is derived from `x`:
177 ///
178 /// ```text
179 /// y = (x wrapping* SALT[i]) >> 27 // top 5 bits → value in 0..31
180 /// word[i] = 1 << y // exactly one bit set per word
181 /// ```
182 ///
183 /// Because only the top 5 bits survive the shift, each word picks one of
184 /// 32 possible bit positions. The eight SALT constants spread the choices
185 /// so different words usually light up different positions.
186 ///
187 /// Key property: the mask depends *only* on `x` (a u32) and the fixed
188 /// SALT constants — it is independent of the filter size. This is why
189 /// folding preserves bit patterns (see Lemma 2 in tests).
190 fn mask(x: u32) -> Self {
191 let mut result = [0_u32; 8];
192 for i in 0..8 {
193 let y = x.wrapping_mul(SALT[i]); // spread bits via multiply
194 let y = y >> 27; // keep top 5 bits → 0..31
195 result[i] = 1 << y; // set exactly that one bit
196 }
197 Self(result)
198 }
199
200 #[inline]
201 #[cfg(not(target_endian = "little"))]
202 fn to_ne_bytes(self) -> [u8; 32] {
203 // SAFETY: [u32; 8] and [u8; 32] have the same size and neither has invalid bit patterns.
204 unsafe { std::mem::transmute(self.0) }
205 }
206
207 #[inline]
208 #[cfg(not(target_endian = "little"))]
209 fn to_le_bytes(self) -> [u8; 32] {
210 self.swap_bytes().to_ne_bytes()
211 }
212
213 #[inline]
214 #[cfg(not(target_endian = "little"))]
215 fn swap_bytes(mut self) -> Self {
216 self.0.iter_mut().for_each(|x| *x = x.swap_bytes());
217 self
218 }
219
220 /// OR the mask bits into this block (`block[i] |= mask[i]`).
221 ///
222 /// After insertion the 8 bits chosen by `mask(hash)` are guaranteed set;
223 /// bits previously set by other hashes are preserved.
224 fn insert(&mut self, hash: u32) {
225 let mask = Self::mask(hash);
226 for i in 0..8 {
227 self[i] |= mask[i];
228 }
229 }
230
231 /// Check membership: returns `true` when *every* bit from `mask(hash)` is
232 /// already set in this block (`block[i] & mask[i] != 0` for all 8 words).
233 ///
234 /// A `true` result means "probably present" (other inserts may have set
235 /// the same bits). A `false` is definitive — the value was never inserted.
236 fn check(&self, hash: u32) -> bool {
237 let mask = Self::mask(hash);
238 for i in 0..8 {
239 if self[i] & mask[i] == 0 {
240 return false;
241 }
242 }
243 true
244 }
245}
246
247impl Block {
248 /// Same result as [`Block::check`], but tests all 8 words without an early
249 /// exit. This avoids a mispredicted branch when hits and misses are mixed
250 /// or the filter is well filled. The early exit is faster when nearly
251 /// every hash misses a sparse filter.
252 #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
253 #[inline(always)]
254 fn check_branch_free(&self, hash: u32) -> bool {
255 let mut missing = 0u32;
256 for (word, salt) in self.0.iter().zip(SALT) {
257 let bit = 1u32 << (hash.wrapping_mul(salt) >> 27);
258 missing |= !word & bit;
259 }
260 missing == 0
261 }
262}
263
264impl std::ops::Index<usize> for Block {
265 type Output = u32;
266
267 #[inline]
268 fn index(&self, index: usize) -> &Self::Output {
269 self.0.index(index)
270 }
271}
272
273impl std::ops::IndexMut<usize> for Block {
274 #[inline]
275 fn index_mut(&mut self, index: usize) -> &mut Self::Output {
276 self.0.index_mut(index)
277 }
278}
279
280impl std::ops::BitOr for Block {
281 type Output = Self;
282
283 #[inline]
284 fn bitor(self, rhs: Self) -> Self {
285 let mut result = [0u32; 8];
286 for (i, item) in result.iter_mut().enumerate() {
287 *item = self.0[i] | rhs.0[i];
288 }
289 Self(result)
290 }
291}
292
293impl std::ops::BitOrAssign for Block {
294 #[inline]
295 fn bitor_assign(&mut self, rhs: Self) {
296 for i in 0..8 {
297 self.0[i] |= rhs.0[i];
298 }
299 }
300}
301
302impl Block {
303 /// Count the total number of set bits across all 8 words.
304 ///
305 /// Computes popcount on each word separately and sums. Keeping the popcount
306 /// separate from the OR allows the compiler to batch SIMD popcount instructions
307 /// (e.g., `cnt.16b` on ARM NEON) instead of interleaving them with OR operations.
308 #[inline]
309 fn count_ones(self) -> u32 {
310 // Written as a fold over the array so the compiler sees 8 independent
311 // popcount operations it can vectorize into cnt.16b + horizontal sum.
312 self.0.iter().map(|w| w.count_ones()).sum()
313 }
314}
315
316/// A split block Bloom filter (SBBF).
317///
318/// An SBBF partitions its bit space into fixed-size 256-bit (32-byte) blocks, each fitting in a
319/// single CPU cache line. Each block contains eight 32-bit words, aligned with SIMD lanes for
320/// parallel bit manipulation. When checking membership, only one block is accessed per query,
321/// eliminating the cache-miss penalty of standard Bloom filters.
322///
323/// ## Sizing and folding
324///
325/// Filters are initially sized for a maximum expected number of distinct values (NDV) via
326/// [`Sbbf::new_with_ndv_fpp`]. After all values are inserted, the filter is compacted by
327/// calling [`Sbbf::fold_to_target_fpp`], which folds the filter down to the smallest size
328/// that still meets the target false positive probability.
329///
330/// The creation of this structure is based on the [`crate::file::properties::BloomFilterProperties`]
331/// struct set via [`crate::file::properties::WriterProperties`] and is thus hidden by default.
332#[derive(Debug, Clone)]
333pub struct Sbbf(Vec<Block>);
334
335/// The minimum number of bytes for a bloom filter bitset.
336pub const BITSET_MIN_LENGTH: usize = 32;
337/// The maximum number of bytes for a bloom filter bitset.
338pub const BITSET_MAX_LENGTH: usize = 128 * 1024 * 1024;
339
340#[inline]
341fn optimal_num_of_bytes(num_bytes: usize) -> usize {
342 let num_bytes = num_bytes.min(BITSET_MAX_LENGTH);
343 let num_bytes = num_bytes.max(BITSET_MIN_LENGTH);
344 num_bytes.next_power_of_two()
345}
346
347// see http://algo2.iti.kit.edu/documents/cacheefficientbloomfilters-jea.pdf
348// given fpp = (1 - e^(-k * n / m)) ^ k
349// we have m = - k * n / ln(1 - fpp ^ (1 / k))
350// where k = number of hash functions, m = number of bits, n = number of distinct values
351#[inline]
352fn num_of_bits_from_ndv_fpp(ndv: u64, fpp: f64) -> usize {
353 let num_bits = -8.0 * ndv as f64 / (1.0 - fpp.powf(1.0 / 8.0)).ln();
354 num_bits as usize
355}
356
357impl Sbbf {
358 /// Create a new [Sbbf] with given number of distinct values and false positive probability.
359 /// Will return an error if `fpp` is greater than or equal to 1.0 or less than 0.0.
360 pub fn new_with_ndv_fpp(ndv: u64, fpp: f64) -> Result<Self, ParquetError> {
361 if !(0.0..1.0).contains(&fpp) {
362 return Err(ParquetError::General(format!(
363 "False positive probability must be between 0.0 and 1.0, got {fpp}"
364 )));
365 }
366 let num_bits = num_of_bits_from_ndv_fpp(ndv, fpp);
367 Ok(Self::new_with_num_of_bytes(num_bits / 8))
368 }
369
370 /// Create a new [Sbbf] with given number of bytes, the exact number of bytes will be adjusted
371 /// to the next power of two bounded by [BITSET_MIN_LENGTH] and [BITSET_MAX_LENGTH].
372 pub fn new_with_num_of_bytes(num_bytes: usize) -> Self {
373 let num_bytes = optimal_num_of_bytes(num_bytes);
374 assert_eq!(num_bytes % size_of::<Block>(), 0);
375 let num_blocks = num_bytes / size_of::<Block>();
376 let bitset = vec![Block::ZERO; num_blocks];
377 Self(bitset)
378 }
379
380 /// Creates a new [Sbbf] from a raw byte slice.
381 pub fn new(bitset: &[u8]) -> Self {
382 let data = bitset
383 .as_chunks::<32>()
384 .0
385 .iter()
386 .map(|chunk| {
387 let mut block = Block::ZERO;
388 let (words, _remainder) = chunk.as_chunks::<4>();
389 for (i, word) in words.iter().enumerate() {
390 block[i] = u32::from_le_bytes(*word);
391 }
392 block
393 })
394 .collect::<Vec<Block>>();
395 Self(data)
396 }
397
398 /// Write the bloom filter data (header and then bitset) to the output. This doesn't
399 /// flush the writer in order to boost performance of bulk writing all blocks. Caller
400 /// must remember to flush the writer.
401 /// This method usually is used in conjunction with [`Self::from_bytes`] for serialization/deserialization.
402 pub fn write<W: Write>(&self, mut writer: W) -> Result<(), ParquetError> {
403 let mut protocol = ThriftCompactOutputProtocol::new(&mut writer);
404 self.header().write_thrift(&mut protocol).map_err(|e| {
405 ParquetError::General(format!("Could not write bloom filter header: {e}"))
406 })?;
407 self.write_bitset(&mut writer)?;
408 Ok(())
409 }
410
411 /// Write the bitset in serialized form to the writer.
412 #[cfg(not(target_endian = "little"))]
413 pub fn write_bitset<W: Write>(&self, mut writer: W) -> Result<(), ParquetError> {
414 for block in &self.0 {
415 writer
416 .write_all(block.to_le_bytes().as_slice())
417 .map_err(|e| {
418 ParquetError::General(format!("Could not write bloom filter bit set: {e}"))
419 })?;
420 }
421 Ok(())
422 }
423
424 /// Write the bitset in serialized form to the writer.
425 #[cfg(target_endian = "little")]
426 pub fn write_bitset<W: Write>(&self, mut writer: W) -> Result<(), ParquetError> {
427 // Safety: Block is repr(transparent) and [u32; 8] can be reinterpreted as [u8; 32].
428 let slice = unsafe {
429 std::slice::from_raw_parts(
430 self.0.as_ptr().cast::<u8>(),
431 self.0.len() * size_of::<Block>(),
432 )
433 };
434 writer.write_all(slice).map_err(|e| {
435 ParquetError::General(format!("Could not write bloom filter bit set: {e}"))
436 })?;
437 Ok(())
438 }
439
440 /// Create and populate [`BloomFilterHeader`] from this bitset for writing to serialized form
441 fn header(&self) -> BloomFilterHeader {
442 BloomFilterHeader {
443 // 8 i32 per block, 4 bytes per i32
444 num_bytes: self.0.len() as i32 * 4 * 8,
445 algorithm: BloomFilterAlgorithm::BLOCK,
446 hash: BloomFilterHash::XXHASH,
447 compression: BloomFilterCompression::UNCOMPRESSED,
448 }
449 }
450
451 /// Read a Bloom filter from existing column-chunk metadata.
452 ///
453 /// The metadata and reader must refer to the same file. A missing offset
454 /// returns `None` without I/O. Invalid metadata, malformed filters, and read
455 /// failures return an error.
456 ///
457 /// When the total filter length is present, one range is fetched. Otherwise,
458 /// the header prefix and bitset are fetched separately.
459 pub fn read_from_column_chunk<R: ChunkReader>(
460 column_metadata: &ColumnChunkMetaData,
461 reader: &R,
462 ) -> Result<Option<Self>> {
463 let Some(mut decoder) = SbbfPushDecoder::try_new(column_metadata)? else {
464 return Ok(None);
465 };
466
467 loop {
468 let result = decoder.try_decode()?;
469 match result {
470 DecodeResult::NeedsData(ranges) => {
471 for range in ranges {
472 let buffer = read_bloom_filter_bytes(reader, &range)?;
473 decoder.push_range(range, buffer)?;
474 }
475 }
476 DecodeResult::Data(sbbf) => return Ok(Some(sbbf)),
477 DecodeResult::Finished => {
478 return Err(general_err!("invalid value returned from SbbfPushDecoder"));
479 }
480 }
481 }
482 }
483
484 /// Read a Bloom filter asynchronously from existing column-chunk metadata.
485 ///
486 /// The metadata and reader must refer to the same file.
487 ///
488 /// A missing Bloom filter offset returns `None` without performing I/O. Invalid
489 /// metadata, malformed filters, and read failures return an error.
490 ///
491 /// When the total filter length is present, one range is fetched. Otherwise,
492 /// this may perform additional fetches.
493 #[cfg(all(feature = "arrow", feature = "async"))]
494 pub async fn read_from_column_chunk_async<R: AsyncFileReader + ?Sized>(
495 column_metadata: &ColumnChunkMetaData,
496 reader: &mut R,
497 ) -> Result<Option<Self>> {
498 Self::read_from_column_chunk_with_fetch(column_metadata, AsyncReaderFetch(reader)).await
499 }
500
501 #[cfg(all(feature = "arrow", feature = "async"))]
502 pub(crate) async fn read_from_column_chunk_with_fetch<F: MetadataFetch>(
503 column_metadata: &ColumnChunkMetaData,
504 mut fetch: F,
505 ) -> Result<Option<Self>> {
506 let Some(mut decoder) = SbbfPushDecoder::try_new(column_metadata)? else {
507 return Ok(None);
508 };
509
510 loop {
511 let result = decoder.try_decode()?;
512 match result {
513 DecodeResult::NeedsData(ranges) => {
514 for range in ranges {
515 let buffer = read_bloom_filter_bytes_async(&mut fetch, &range).await?;
516 decoder.push_range(range, buffer)?;
517 }
518 }
519 DecodeResult::Data(sbbf) => return Ok(Some(sbbf)),
520 DecodeResult::Finished => {
521 return Err(general_err!("invalid value returned from SbbfPushDecoder"));
522 }
523 }
524 }
525 }
526
527 /// Map a 64-bit hash to a block index in `[0, num_blocks)`.
528 ///
529 /// Uses the "multiply-and-shift" trick (a fast alternative to modulo):
530 ///
531 /// ```text
532 /// upper32 = hash >> 32 // take the top 32 bits of the hash
533 /// index = (upper32 * N) >> 32 // ∈ [0, N) where N = num_blocks
534 /// ```
535 ///
536 /// Why this matters for folding (Lemma 1): when N is a power of two and
537 /// you halve it to N/2, the index also halves:
538 ///
539 /// ```text
540 /// index_N = (upper32 * N) >> 32
541 /// index_N/2 = (upper32 * N/2) >> 32 = index_N / 2 (integer division)
542 /// ```
543 ///
544 /// So the block that held hash `h` in the big filter is at `index / 2` in
545 /// the half-sized filter — exactly where `fold` ORs it.
546 #[inline]
547 fn hash_to_block_index(&self, hash: u64) -> usize {
548 (((hash >> 32).saturating_mul(self.0.len() as u64)) >> 32) as usize
549 }
550
551 /// Insert an [AsBytes] value into the filter
552 pub fn insert<T: AsBytes + ?Sized>(&mut self, value: &T) {
553 self.insert_hash(hash_as_bytes(value));
554 }
555
556 /// Inserts a precomputed 64-bit hash.
557 ///
558 /// The filter can hold hashes from any well-mixed 64-bit hash function,
559 /// so values can be hashed in bulk with the caller's own hash function
560 /// (for example, a columnar hash of a multi-column key). [`Self::check`]
561 /// only finds values whose hashes were computed as the Parquet
562 /// specification requires (xxHash64, seed 0, of the plain encoding); use
563 /// [`Self::check_hashes`] with the same hash function instead.
564 ///
565 /// Only write a filter to a Parquet file (with [`Self::write`]) if every
566 /// hash was computed as the specification requires. The header always
567 /// names xxHash64, so readers would get false negatives and skip row
568 /// groups that hold matching rows.
569 ///
570 /// # Panics
571 ///
572 /// Panics if the filter has no blocks. [`Self::new`] returns such a
573 /// filter for a bitset shorter than 32 bytes.
574 pub fn insert_hash(&mut self, hash: u64) {
575 let block_index = self.hash_to_block_index(hash);
576 self.0[block_index].insert(hash as u32)
577 }
578
579 /// Check if an [AsBytes] value is probably present or definitely absent in the filter
580 ///
581 /// `value` must have the Parquet physical type of the column. To check a
582 /// filter written by [`ArrowWriter`] with Arrow values, which may have been
583 /// converted to a different type before they were written, use
584 /// [`ArrowSbbf`].
585 ///
586 /// [`ArrowWriter`]: crate::arrow::ArrowWriter
587 /// [`ArrowSbbf`]: crate::arrow::bloom_filter::ArrowSbbf
588 pub fn check<T: AsBytes + ?Sized>(&self, value: &T) -> bool {
589 self.check_hash(hash_as_bytes(value))
590 }
591
592 /// Check if a hash is in the filter. May return
593 /// true for values that was never inserted ("false positive")
594 /// but will always return false if a hash has not been inserted.
595 fn check_hash(&self, hash: u64) -> bool {
596 let block_index = self.hash_to_block_index(hash);
597 self.0[block_index].check(hash as u32)
598 }
599
600 /// Same result as [`Self::check_hash`], without data-dependent branches.
601 #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
602 #[inline(always)]
603 fn check_hash_branch_free(&self, hash: u64) -> bool {
604 let block_index = self.hash_to_block_index(hash);
605 self.0[block_index].check_branch_free(hash as u32)
606 }
607
608 /// Checks precomputed 64-bit hashes (see [`Self::insert_hash`]).
609 ///
610 /// Bit `i` of the result is set if `hashes[i]` may be in the filter.
611 /// A filter with no blocks contains nothing, so every bit is unset.
612 ///
613 /// Each check tests all 8 bits of its block without an early exit, so
614 /// it has no data-dependent branches. This is typically faster than
615 /// checking one hash at a time when hits and misses are mixed (and the
616 /// branch predictor cannot learn the pattern), and slightly slower when
617 /// nearly every hash misses, where the early exit pays off.
618 #[cfg(feature = "arrow")]
619 pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
620 if self.0.is_empty() {
621 return arrow_buffer::BooleanBuffer::new_unset(hashes.len());
622 }
623 arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
624 self.check_hash_branch_free(hashes[i])
625 })
626 }
627
628 /// Adds the values of `other` to this filter, so that afterwards it
629 /// contains every value that either filter contained.
630 ///
631 /// `other` must have at least as many blocks as this filter, and a
632 /// multiple of them. When it has more, it is folded to the size of this
633 /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
634 /// `other`. Folding and union commute: the result is the same as
635 /// inserting the values of both filters into one filter and folding it
636 /// to this size. This lets independent filters (for example, one per
637 /// thread) be built and then merged.
638 ///
639 /// Both filters must have been populated with the same hash function
640 /// (the Parquet xxHash64 used by [`Self::insert`], or the same function
641 /// used for [`Self::insert_hash`]); otherwise the result is
642 /// meaningless. This cannot be checked.
643 ///
644 /// Returns an error if the sizes are incompatible, including if this
645 /// filter has no blocks.
646 ///
647 /// # Example
648 ///
649 /// ```
650 /// # use parquet::bloom_filter::Sbbf;
651 /// // One filter per partition, filled with precomputed hashes
652 /// let mut a = Sbbf::new_with_num_of_bytes(1024);
653 /// a.insert_hash(0x0123_4567_89ab_cdef);
654 /// let mut b = Sbbf::new_with_num_of_bytes(4096);
655 /// b.insert_hash(0xfedc_ba98_7654_3210);
656 ///
657 /// // `b` has 4 times as many blocks as `a`, so it is folded on the fly
658 /// a.union(&b).unwrap();
659 /// # #[cfg(feature = "arrow")]
660 /// # {
661 /// let found = a.check_hashes(&[0x0123_4567_89ab_cdef, 0xfedc_ba98_7654_3210]);
662 /// assert!(found.value(0) && found.value(1));
663 /// # }
664 ///
665 /// // A smaller filter cannot be unioned into a larger one
666 /// assert!(b.union(&a).is_err());
667 /// ```
668 pub fn union(&mut self, other: &Sbbf) -> Result<(), ParquetError> {
669 let (len, other_len) = (self.0.len(), other.0.len());
670 // `checked_rem` also rejects an empty `self` (`len == 0`).
671 if other_len < len || other_len.checked_rem(len) != Some(0) {
672 return Err(ParquetError::General(format!(
673 "Cannot union a bloom filter of {other_len} blocks into one of {len} blocks"
674 )));
675 }
676 let group_size = other_len / len;
677 for (block, group) in self.0.iter_mut().zip(other.0.chunks_exact(group_size)) {
678 for other_block in group {
679 *block |= *other_block;
680 }
681 }
682 Ok(())
683 }
684
685 /// Return the total in memory size of this bloom filter in bytes
686 pub(crate) fn estimated_memory_size(&self) -> usize {
687 self.0.capacity() * std::mem::size_of::<Block>()
688 }
689
690 /// Returns the number of blocks in this bloom filter.
691 pub fn num_blocks(&self) -> usize {
692 self.0.len()
693 }
694
695 /// Estimate the false positive probability (FPP) of this filter at its current size.
696 ///
697 /// This is the same estimate [`Self::fold_to_target_fpp`] uses to choose how far to fold.
698 ///
699 /// This lets a caller inspect a filter before folding or writing it, for example to
700 /// discard a filter that already exceeds its target FPP. Returns `1.0` for a filter
701 /// with no blocks.
702 pub fn estimated_fpp(&self) -> f64 {
703 if self.0.is_empty() {
704 return 1.0;
705 }
706 self.average_fill().powi(8)
707 }
708
709 /// Average fraction of bits set per block. The filter must have at least one block.
710 fn average_fill(&self) -> f64 {
711 let total_set_bits: u64 = self.0.iter().map(|b| u64::from(b.count_ones())).sum();
712 total_set_bits as f64 / (self.0.len() as f64 * 256.0)
713 }
714
715 /// Fold the bloom filter down to the smallest size that still meets the target FPP
716 /// (False Positive Percentage).
717 ///
718 /// Folds the filter by merging groups of adjacent blocks via bitwise OR, where each
719 /// fold level halves the number of blocks. The fold count is chosen as the maximum
720 /// number of folds whose estimated FPP stays within `target_fpp`. The filter stops
721 /// at a minimum size of 1 block (32 bytes).
722 ///
723 /// ## How it works
724 ///
725 /// SBBFs use multiplicative hashing for block selection:
726 ///
727 /// ```text
728 /// block_index = ((hash >> 32) * num_blocks) >> 32
729 /// ```
730 ///
731 /// A single fold halves the block count: when `num_blocks` is halved, the new index
732 /// becomes `floor(original_index / 2)`, so blocks `2i` and `2i+1` map to the same
733 /// position. More generally, `k` folds reduce the block count by `2^k`, merging
734 /// groups of `2^k` adjacent blocks in a single pass:
735 ///
736 /// ```text
737 /// folded[i] = blocks[i*2^k] | blocks[i*2^k + 1] | ... | blocks[i*2^k + 2^k - 1]
738 /// ```
739 ///
740 /// This differs from standard Bloom filter folding, which merges the two halves
741 /// (`B[i] | B[i + m/2]`) because standard filters use modular hashing where
742 /// `h(x) mod (m/2)` maps indices `i` and `i + m/2` to the same position.
743 ///
744 /// ## Correctness
745 ///
746 /// Folding **never introduces false negatives**. Every bit that was set in the original
747 /// filter remains set in the folded filter (via bitwise OR). The only effect is a controlled
748 /// increase in FPP as set bits from different blocks are merged together.
749 /// This is was originally proven in [Sailhan & Stehr 2012] for standard bloom filters and is empirically
750 /// demonstrated for SBBFs in Lemma 1 and Lemma 2 of the tests.
751 ///
752 /// ## References
753 ///
754 /// [Sailhan & Stehr 2012]: https://doi.org/10.1109/GreenCom.2012.16
755 pub fn fold_to_target_fpp(&mut self, target_fpp: f64) {
756 let num_folds = self.num_folds_for_target_fpp(target_fpp);
757 if num_folds > 0 {
758 self.fold_n(num_folds);
759 }
760 }
761
762 /// Determine how many folds can be applied without exceeding `target_fpp`.
763 ///
764 /// Computes the average per-block fill rate in a single pass (no allocation),
765 /// then analytically estimates the FPP at each fold level.
766 ///
767 /// When two blocks with independent fill rate `f` are OR'd, the expected fill
768 /// of the merged block is `1 - (1-f)^2`. After `k` folds (merging `2^k` blocks):
769 ///
770 /// ```text
771 /// f_k = 1 - (1 - f)^(2^k)
772 /// ```
773 ///
774 /// SBBF membership checks perform `k=8` bit checks within one 256-bit block,
775 /// so the estimated FPP at fold level k is `f_k^8`.
776 fn num_folds_for_target_fpp(&self, target_fpp: f64) -> u32 {
777 let len = self.0.len();
778 if len < 2 {
779 return 0;
780 }
781
782 // Single pass: compute average per-block fill rate.
783 let avg_fill = self.average_fill();
784
785 // Empty filter: can fold all the way down.
786 if avg_fill == 0.0 {
787 return len.trailing_zeros();
788 }
789
790 // Find max folds where estimated FPP stays within target.
791 // f_k = 1 - (1 - avg_fill)^(2^k), FPP_k = f_k^8
792 assert!(
793 len.is_power_of_two(),
794 "Number of blocks must be a power of 2 for folding"
795 );
796 let max_folds = len.trailing_zeros(); // log2(len) since len is power of 2
797 let one_minus_f = 1.0 - avg_fill;
798 let mut num_folds = 0u32;
799 let mut one_minus_fk = one_minus_f; // (1-f)^1 initially
800
801 for _ in 0..max_folds {
802 // After one more fold: (1-f)^(2^(k+1)) = ((1-f)^(2^k))^2
803 one_minus_fk = one_minus_fk * one_minus_fk;
804 let fk = 1.0 - one_minus_fk;
805 let estimated_fpp = fk.powi(8);
806 if estimated_fpp > target_fpp {
807 break;
808 }
809 num_folds += 1;
810 }
811
812 num_folds
813 }
814
815 /// Fold the filter `num_folds` times in a single pass.
816 ///
817 /// Merges groups of `2^num_folds` adjacent blocks via bitwise OR, producing
818 /// `len / 2^num_folds` output blocks. The original allocation is reused.
819 ///
820 /// # Panics
821 ///
822 /// Panics if `num_folds` is 0 or would reduce the filter below 1 block.
823 fn fold_n(&mut self, num_folds: u32) {
824 assert!(num_folds > 0, "num_folds must be at least 1");
825 let len = self.0.len();
826 let group_size = 1usize << num_folds;
827 assert!(
828 group_size <= len,
829 "Cannot fold {num_folds} times: need at least {group_size} blocks, have {len}"
830 );
831 let new_len = len / group_size;
832 for i in 0..new_len {
833 let start = i * group_size;
834 let mut merged = self.0[start];
835 for j in 1..group_size {
836 merged |= self.0[start + j];
837 }
838 self.0[i] = merged;
839 }
840 self.0.truncate(new_len);
841 // `truncate` keeps the capacity; release it so filters retained until the file is closed
842 // (e.g. `BloomFilterPosition::End`) only hold their folded size.
843 self.0.shrink_to_fit();
844 }
845
846 /// Reads an Sbbf from Thrift encoded bytes.
847 ///
848 /// Returns an error if the header is malformed, the bitset is not a positive
849 /// multiple of 32 bytes, or its size does not match the header.
850 ///
851 /// # Examples
852 ///
853 /// ```no_run
854 /// # use parquet::errors::Result;
855 /// # use parquet::bloom_filter::Sbbf;
856 /// # fn main() -> Result<()> {
857 /// // In a real application, you would read serialized bloom filter bytes from a cache.
858 /// // This example demonstrates the deserialization process.
859 /// // Assuming you have bloom filter bytes from a Parquet file:
860 /// # let serialized_bytes: Vec<u8> = vec![];
861 /// let bloom_filter = Sbbf::from_bytes(&serialized_bytes)?;
862 /// // Now you can use the bloom filter to check for values
863 /// if bloom_filter.check(&"some_value") {
864 /// println!("Value might be present (or false positive)");
865 /// } else {
866 /// println!("Value is definitely not present");
867 /// }
868 /// # Ok(())
869 /// # }
870 /// ```
871 pub fn from_bytes(bytes: &[u8]) -> Result<Self, ParquetError> {
872 let range = bloom_filter_bitset_range(bytes, Some(bytes.len()))?;
873 Ok(Self::new(&bytes[range]))
874 }
875}
876
877// per spec we use xxHash with seed=0
878const SEED: u64 = 0;
879
880#[inline]
881fn hash_as_bytes<A: AsBytes + ?Sized>(value: &A) -> u64 {
882 XxHash64::oneshot(SEED, value.as_bytes())
883}
884
885const SBBF_HEADER_SIZE_ESTIMATE: usize = 20;
886
887fn read_bloom_filter_bytes<R: ChunkReader>(reader: &R, range: &Range<u64>) -> Result<Bytes> {
888 let length = usize::try_from(range.end - range.start)?;
889 validate_bloom_filter_read(reader.get_bytes(range.start, length)?, length)
890}
891
892// Adapt unsized async readers without widening the public MetadataFetch blanket impl.
893#[cfg(all(feature = "arrow", feature = "async"))]
894struct AsyncReaderFetch<'a, R: ?Sized>(&'a mut R);
895
896#[cfg(all(feature = "arrow", feature = "async"))]
897impl<R: AsyncFileReader + ?Sized> MetadataFetch for AsyncReaderFetch<'_, R> {
898 fn fetch(&mut self, range: Range<u64>) -> BoxFuture<'_, Result<Bytes>> {
899 self.0.get_bytes(range)
900 }
901}
902
903#[cfg(all(feature = "arrow", feature = "async"))]
904async fn read_bloom_filter_bytes_async<F: MetadataFetch>(
905 fetch: &mut F,
906 range: &Range<u64>,
907) -> Result<Bytes> {
908 let length = usize::try_from(range.end - range.start)?;
909 validate_bloom_filter_read(fetch.fetch(range.clone()).await?, length)
910}
911
912/// Parses the header and returns the bitset's range relative to the filter start.
913/// When the complete filter length is known, the bitset must consume it exactly.
914fn bloom_filter_bitset_range(buffer: &[u8], length: Option<usize>) -> Result<Range<usize>> {
915 let (header, header_length) = read_bloom_filter_header_and_length(buffer)?;
916
917 // Force an explicit decision if supported variants change.
918 match header.algorithm {
919 BloomFilterAlgorithm::BLOCK => {}
920 }
921 match header.hash {
922 BloomFilterHash::XXHASH => {}
923 }
924 match header.compression {
925 BloomFilterCompression::UNCOMPRESSED => {}
926 }
927
928 let bitset_length = usize::try_from(header.num_bytes)
929 .map_err(|_| general_err!("Bloom filter bitset length is invalid"))?;
930 if bitset_length < BITSET_MIN_LENGTH || !bitset_length.is_multiple_of(size_of::<Block>()) {
931 return Err(general_err!(
932 "Bloom filter bitset length must be a positive multiple of 32"
933 ));
934 }
935 let end = header_length
936 .checked_add(bitset_length)
937 .ok_or_else(|| general_err!("Bloom filter length overflow"))?;
938 if length.is_some_and(|length| length != end) {
939 return Err(general_err!(
940 "Bloom filter length does not match its header"
941 ));
942 }
943 Ok(header_length..end)
944}
945
946/// Converts a filter-relative range to a file range without overflowing.
947fn bloom_filter_read_range(offset: u64, range: Range<usize>) -> Result<Range<u64>> {
948 let start = offset
949 .checked_add(range.start as u64)
950 .ok_or_else(|| general_err!("Bloom filter read range overflow"))?;
951 let end = offset
952 .checked_add(range.end as u64)
953 .ok_or_else(|| general_err!("Bloom filter read range overflow"))?;
954 Ok(start..end)
955}
956
957fn validate_bloom_filter_read(bytes: Bytes, length: usize) -> Result<Bytes> {
958 if bytes.len() != length {
959 return Err(general_err!(
960 "Bloom filter read length mismatch: expected {length} bytes, got {}",
961 bytes.len()
962 ));
963 }
964 Ok(bytes)
965}
966
967/// Parses a Bloom filter header and returns the number of bytes consumed.
968fn read_bloom_filter_header_and_length(buffer: &[u8]) -> Result<(BloomFilterHeader, usize)> {
969 let mut prot = ThriftSliceInputProtocol::new(buffer);
970 let header = BloomFilterHeader::read_thrift(&mut prot)
971 .map_err(|e| ParquetError::General(format!("Could not read bloom filter header: {e}")))?;
972 Ok((header, buffer.len() - prot.as_slice().len()))
973}
974
975#[cfg(test)]
976mod tests {
977 use super::*;
978
979 fn insert_all(f: &mut Sbbf, hashes: &[u64]) {
980 for &h in hashes {
981 f.insert_hash(h);
982 }
983 }
984
985 #[test]
986 fn test_insert_hash_matches_insert() {
987 let mut by_value = Sbbf::new_with_num_of_bytes(256);
988 let mut by_hash = Sbbf::new_with_num_of_bytes(256);
989 for i in 0..200u64 {
990 by_value.insert(&i);
991 by_hash.insert_hash(hash_as_bytes(&i));
992 }
993 assert_eq!(bitset(&by_value), bitset(&by_hash));
994 }
995
996 fn bitset(f: &Sbbf) -> Vec<u8> {
997 let mut out = vec![];
998 f.write_bitset(&mut out).unwrap();
999 out
1000 }
1001
1002 #[test]
1003 fn test_branch_free_check_matches_check() {
1004 let mut filter = Sbbf::new_with_num_of_bytes(256);
1005 for i in 0..200u64 {
1006 filter.insert(&(i * 7));
1007 }
1008 for i in 0..5000u64 {
1009 let h = hash_as_bytes(&i);
1010 assert_eq!(filter.check_hash(h), filter.check_hash_branch_free(h));
1011 }
1012 }
1013
1014 #[cfg(feature = "arrow")]
1015 #[test]
1016 fn test_check_hashes_matches_check_hash() {
1017 let hashes: Vec<u64> = (0..5000u64).map(|i| hash_as_bytes(&i)).collect();
1018 let mut filter = Sbbf::new_with_num_of_bytes(256);
1019 insert_all(&mut filter, &hashes[..200]);
1020 let result = filter.check_hashes(&hashes);
1021 for (i, &h) in hashes.iter().enumerate() {
1022 assert_eq!(result.value(i), filter.check_hash(h));
1023 }
1024 assert!((0..200).all(|i| result.value(i)));
1025 }
1026
1027 #[test]
1028 fn test_union_of_parts_matches_one_filter() {
1029 let hashes: Vec<u64> = (0..100_000u64).map(|i| hash_as_bytes(&i)).collect();
1030 let mut whole = Sbbf::new_with_num_of_bytes(1 << 20);
1031 insert_all(&mut whole, &hashes);
1032 let mut merged = Sbbf::new_with_num_of_bytes(1 << 20);
1033 for chunk in hashes.chunks(7_000) {
1034 let mut part = Sbbf::new_with_num_of_bytes(1 << 20);
1035 insert_all(&mut part, chunk);
1036 merged.union(&part).unwrap();
1037 }
1038 assert_eq!(bitset(&whole), bitset(&merged));
1039 // union then fold == fold then union
1040 let mut folded = whole.clone();
1041 folded.fold_to_target_fpp(0.01);
1042 let num_folds = (whole.num_blocks() / folded.num_blocks()).trailing_zeros();
1043 assert!(num_folds > 0);
1044 let mut merged_folded = Sbbf::new_with_num_of_bytes(folded.num_blocks() * 32);
1045 for chunk in hashes.chunks(7_000) {
1046 let mut part = Sbbf::new_with_num_of_bytes(1 << 20);
1047 insert_all(&mut part, chunk);
1048 part.fold_n(num_folds);
1049 merged_folded.union(&part).unwrap();
1050 }
1051 assert_eq!(bitset(&folded), bitset(&merged_folded));
1052 // a larger filter is folded on the fly
1053 let mut small = Sbbf::new_with_num_of_bytes(1 << 16);
1054 insert_all(&mut small, &hashes[..10]);
1055 small.union(&whole).unwrap();
1056 let mut expected = Sbbf::new_with_num_of_bytes(1 << 16);
1057 insert_all(&mut expected, &hashes);
1058 assert_eq!(bitset(&small), bitset(&expected));
1059 // a smaller filter cannot be unioned into a larger one
1060 assert!(whole.clone().union(&small).is_err());
1061 }
1062
1063 #[cfg(feature = "arrow")]
1064 #[test]
1065 fn test_check_hashes_empty_filter() {
1066 let empty = Sbbf::new(&[0; 31]);
1067 assert_eq!(empty.num_blocks(), 0);
1068 let result = empty.check_hashes(&[0, 1, u64::MAX]);
1069 assert_eq!(result.len(), 3);
1070 assert_eq!(result.count_set_bits(), 0);
1071 }
1072
1073 #[test]
1074 fn test_union_empty_filter_is_error() {
1075 let mut empty = Sbbf::new(&[]);
1076 assert_eq!(empty.num_blocks(), 0);
1077 let other = Sbbf::new_with_num_of_bytes(1024);
1078 assert!(empty.union(&other).is_err());
1079 assert!(empty.union(&Sbbf::new(&[])).is_err());
1080 assert!(other.clone().union(&empty).is_err());
1081 }
1082
1083 #[test]
1084 fn test_bloom_filter_read_range_overflow() {
1085 assert!(bloom_filter_read_range(u64::MAX, 0..1).is_err());
1086 assert!(bloom_filter_read_range(u64::MAX, 1..2).is_err());
1087 }
1088
1089 #[test]
1090 fn test_hash_bytes() {
1091 assert_eq!(hash_as_bytes(""), 17241709254077376921);
1092 }
1093
1094 #[test]
1095 #[cfg_attr(miri, ignore)] // Takes too long
1096 fn test_mask_set_quick_check() {
1097 for i in 0..1_000_000 {
1098 let result = Block::mask(i);
1099 assert!(result.0.iter().all(|&x| x.is_power_of_two()));
1100 }
1101 }
1102
1103 #[test]
1104 #[cfg_attr(miri, ignore)] // Takes too long
1105 fn test_block_insert_and_check() {
1106 for i in 0..1_000_000 {
1107 let mut block = Block::ZERO;
1108 block.insert(i);
1109 assert!(block.check(i));
1110 }
1111 }
1112
1113 #[test]
1114 #[cfg_attr(miri, ignore)] // Takes too long
1115 fn test_sbbf_insert_and_check() {
1116 let mut sbbf = Sbbf(vec![Block::ZERO; 1_000]);
1117 for i in 0..1_000_000 {
1118 sbbf.insert(&i);
1119 assert!(sbbf.check(&i));
1120 }
1121 }
1122
1123 #[test]
1124 fn test_with_fixture() {
1125 // bloom filter produced by parquet-mr/spark for a column of i64 f"a{i}" for i in 0..10
1126 let bitset: &[u8] = &[
1127 200, 1, 80, 20, 64, 68, 8, 109, 6, 37, 4, 67, 144, 80, 96, 32, 8, 132, 43, 33, 0, 5,
1128 99, 65, 2, 0, 224, 44, 64, 78, 96, 4,
1129 ];
1130 let sbbf = Sbbf::new(bitset);
1131 for a in 0..10i64 {
1132 let value = format!("a{a}");
1133 assert!(sbbf.check(&value.as_str()));
1134 }
1135 }
1136
1137 /// test the assumption that bloom filter header size should not exceed SBBF_HEADER_SIZE_ESTIMATE
1138 /// essentially we are testing that the struct is packed with 4 i32 fields, each can be 1-5 bytes
1139 /// so altogether it'll be 20 bytes at most.
1140 #[test]
1141 fn test_bloom_filter_header_size_assumption() {
1142 let buffer: &[u8; 16] = &[21, 64, 28, 28, 0, 0, 28, 28, 0, 0, 28, 28, 0, 0, 0, 99];
1143 let (
1144 BloomFilterHeader {
1145 algorithm,
1146 compression,
1147 hash,
1148 num_bytes,
1149 },
1150 read_length,
1151 ) = read_bloom_filter_header_and_length(buffer).unwrap();
1152 assert_eq!(read_length, 15);
1153 assert_eq!(algorithm, BloomFilterAlgorithm::BLOCK);
1154 assert_eq!(compression, BloomFilterCompression::UNCOMPRESSED);
1155 assert_eq!(hash, BloomFilterHash::XXHASH);
1156 assert_eq!(num_bytes, 32_i32);
1157 assert_eq!(20, SBBF_HEADER_SIZE_ESTIMATE);
1158 }
1159
1160 #[test]
1161 fn test_optimal_num_of_bytes() {
1162 for (input, expected) in &[
1163 (0, 32),
1164 (9, 32),
1165 (31, 32),
1166 (32, 32),
1167 (33, 64),
1168 (99, 128),
1169 (1024, 1024),
1170 (999_000_000, 128 * 1024 * 1024),
1171 ] {
1172 assert_eq!(*expected, optimal_num_of_bytes(*input));
1173 }
1174 }
1175
1176 #[test]
1177 fn test_num_of_bits_from_ndv_fpp() {
1178 for (fpp, ndv, num_bits) in &[
1179 (0.1, 10, 57),
1180 (0.01, 10, 96),
1181 (0.001, 10, 146),
1182 (0.1, 100, 577),
1183 (0.01, 100, 968),
1184 (0.001, 100, 1460),
1185 (0.1, 1000, 5772),
1186 (0.01, 1000, 9681),
1187 (0.001, 1000, 14607),
1188 (0.1, 10000, 57725),
1189 (0.01, 10000, 96815),
1190 (0.001, 10000, 146076),
1191 (0.1, 100000, 577254),
1192 (0.01, 100000, 968152),
1193 (0.001, 100000, 1460769),
1194 (0.1, 1000000, 5772541),
1195 (0.01, 1000000, 9681526),
1196 (0.001, 1000000, 14607697),
1197 (1e-50, 1_000_000_000_000, 14226231280773240832),
1198 ] {
1199 assert_eq!(*num_bits, num_of_bits_from_ndv_fpp(*ndv, *fpp) as u64);
1200 }
1201 }
1202
1203 #[test]
1204 fn test_fold_n_halves_block_count() {
1205 let mut sbbf = Sbbf::new_with_num_of_bytes(1024); // 32 blocks
1206 assert_eq!(sbbf.num_blocks(), 32);
1207 sbbf.fold_n(1);
1208 assert_eq!(sbbf.num_blocks(), 16);
1209 assert_eq!(sbbf.0.capacity(), 16);
1210 sbbf.fold_n(1);
1211 assert_eq!(sbbf.num_blocks(), 8);
1212 assert_eq!(sbbf.0.capacity(), 8);
1213 }
1214
1215 #[test]
1216 fn test_fold_preserves_inserted_values() {
1217 // Create a large filter, insert values, fold, verify no false negatives
1218 let mut sbbf = Sbbf::new_with_num_of_bytes(32 * 1024); // 32KB = 1024 blocks
1219 let values: Vec<String> = (0..1000).map(|i| format!("value_{i}")).collect();
1220 for v in &values {
1221 sbbf.insert(v.as_str());
1222 }
1223
1224 // Fold several times
1225 let original_blocks = sbbf.num_blocks();
1226 sbbf.fold_to_target_fpp(0.05);
1227 assert!(
1228 sbbf.num_blocks() < original_blocks,
1229 "should have folded at least once"
1230 );
1231
1232 // All inserted values must still be found (no false negatives)
1233 for v in &values {
1234 assert!(
1235 sbbf.check(v.as_str()),
1236 "Value '{v}' missing after folding (false negative!)"
1237 );
1238 }
1239 }
1240
1241 #[test]
1242 fn test_fold_to_target_fpp_stops_before_exceeding_target() {
1243 let mut sbbf = Sbbf::new_with_num_of_bytes(64 * 1024); // 64KB
1244 // Insert enough values to set some bits
1245 for i in 0..5000 {
1246 sbbf.insert(&i);
1247 }
1248
1249 let target_fpp = 0.01;
1250 sbbf.fold_to_target_fpp(target_fpp);
1251
1252 // After folding, the estimated FPP should be at or below target
1253 // (the current state should not exceed target — we stopped before that would happen)
1254 let total_bits = (sbbf.num_blocks() * 256) as f64;
1255 let set_bits: u64 = sbbf
1256 .0
1257 .iter()
1258 .flat_map(|b| b.0.iter())
1259 .map(|w| w.count_ones() as u64)
1260 .sum();
1261 let fill = set_bits as f64 / total_bits;
1262 let current_fpp = fill.powi(8);
1263 assert!(
1264 current_fpp <= target_fpp,
1265 "FPP {current_fpp} exceeds target {target_fpp}"
1266 );
1267 }
1268
1269 #[test]
1270 fn test_fold_empty_filter_folds_to_minimum() {
1271 // An empty filter has fill=0, so estimated FPP is always 0 — should fold all the way down
1272 let mut sbbf = Sbbf::new_with_num_of_bytes(1024); // 32 blocks
1273 sbbf.fold_to_target_fpp(0.01);
1274 assert_eq!(sbbf.num_blocks(), 1);
1275 }
1276
1277 #[test]
1278 fn test_estimated_fpp_matches_serialized_bitset() {
1279 for num_bytes in [BITSET_MIN_LENGTH, 1024, 64 * 1024] {
1280 for ndv in [0u64, 1, 10, 100, 1_000, 10_000, 100_000] {
1281 let mut sbbf = Sbbf::new_with_num_of_bytes(num_bytes);
1282 for i in 0..ndv {
1283 sbbf.insert(&i);
1284 }
1285
1286 let mut bitset = Vec::new();
1287 sbbf.write_bitset(&mut bitset).unwrap();
1288 let set_bits: u64 = bitset.iter().map(|b| u64::from(b.count_ones())).sum();
1289 let expected = (set_bits as f64 / (bitset.len() as f64 * 8.0)).powi(8);
1290
1291 assert_eq!(
1292 sbbf.estimated_fpp().to_bits(),
1293 expected.to_bits(),
1294 "{num_bytes} bytes, {ndv} values"
1295 );
1296 }
1297 }
1298 }
1299
1300 #[test]
1301 fn test_estimated_fpp_bounds() {
1302 assert_eq!(Sbbf::new_with_num_of_bytes(1024).estimated_fpp(), 0.0);
1303 assert_eq!(Sbbf::new(&[0xFF; 1024]).estimated_fpp(), 1.0);
1304 assert_eq!(Sbbf::new(&[]).estimated_fpp(), 1.0);
1305 }
1306
1307 #[test]
1308 fn test_estimated_fpp_increases_when_folded() {
1309 let mut sbbf = Sbbf::new_with_num_of_bytes(64 * 1024);
1310 for i in 0..1_000 {
1311 sbbf.insert(&i);
1312 }
1313 let before = sbbf.estimated_fpp();
1314 sbbf.fold_n(3);
1315 assert!(
1316 sbbf.estimated_fpp() > before,
1317 "folding must not lower the estimate: {before} -> {}",
1318 sbbf.estimated_fpp()
1319 );
1320 }
1321
1322 #[test]
1323 #[should_panic(expected = "Cannot fold 1 times: need at least 2 blocks, have 1")]
1324 fn test_fold_n_panics_at_minimum_size() {
1325 let mut sbbf = Sbbf::new_with_num_of_bytes(32); // 1 block (minimum)
1326 sbbf.fold_n(1);
1327 }
1328
1329 #[test]
1330 fn test_sbbf_write_round_trip() {
1331 // Create a bloom filter with a 32-byte bitset (minimum size)
1332 let bitset_bytes = vec![0u8; 32];
1333 let mut original = Sbbf::new(&bitset_bytes);
1334
1335 // Insert some test values
1336 let test_values = ["hello", "world", "rust", "parquet", "bloom", "filter"];
1337 for value in &test_values {
1338 original.insert(value);
1339 }
1340
1341 // Serialize to bytes
1342 let mut output = Vec::new();
1343 original.write(&mut output).unwrap();
1344
1345 // Validate header was written correctly
1346 let mut protocol = ThriftSliceInputProtocol::new(&output);
1347 let header = BloomFilterHeader::read_thrift(&mut protocol).unwrap();
1348 assert_eq!(header.num_bytes, bitset_bytes.len() as i32);
1349 assert_eq!(header.algorithm, BloomFilterAlgorithm::BLOCK);
1350 assert_eq!(header.hash, BloomFilterHash::XXHASH);
1351 assert_eq!(header.compression, BloomFilterCompression::UNCOMPRESSED);
1352
1353 // Deserialize using from_bytes
1354 let reconstructed = Sbbf::from_bytes(&output).unwrap();
1355
1356 // Most importantly: verify the bloom filter WORKS correctly after round-trip
1357 // Note: bloom filters can have false positives, but should never have false negatives
1358 // So we can't assert !check(), but we should verify inserted values are found
1359 for value in &test_values {
1360 assert!(
1361 reconstructed.check(value),
1362 "Value '{value}' should be present after round-trip"
1363 );
1364 }
1365 }
1366
1367 /// Prove that folding an SBBF by one level produces the exact same bits
1368 /// as building a fresh filter at the smaller size from scratch.
1369 ///
1370 /// # What is folding?
1371 ///
1372 /// ```text
1373 /// Original (N = 8 blocks):
1374 /// ┌───┬───┬───┬───┬───┬───┬───┬───┐
1375 /// │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
1376 /// └─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┘
1377 /// │ │ │ │ │ │ │ │
1378 /// └─OR┘ └─OR┘ └─OR┘ └─OR┘ pair-wise OR
1379 /// │ │ │ │
1380 /// ┌───┴──┬────┴──┬────┴──┬────┴──┐
1381 /// │ 0|1 │ 2|3 │ 4|5 │ 6|7 │ Folded (N/2 = 4 blocks)
1382 /// └──────┴───────┴───────┴───────┘
1383 /// ```
1384 ///
1385 /// # Why folded == fresh (the two lemmas)
1386 ///
1387 /// An SBBF insertion does two things with a 64-bit hash `h`:
1388 ///
1389 /// 1. **Pick a block** — uses the upper 32 bits via `hash_to_block_index`
1390 /// 2. **Set 8 bits in that block** — uses the lower 32 bits via `Block::mask`
1391 ///
1392 /// **Lemma 1 (block index halves):** `hash_to_block_index` uses
1393 /// `(upper32 * N) >> 32`. When N halves, the index halves too:
1394 /// `index_in(N/2) == index_in(N) / 2`. So the hash lands in the same
1395 /// destination block whether you fold or build fresh.
1396 ///
1397 /// **Lemma 2 (mask is size-independent):** `Block::mask(h as u32)` depends
1398 /// only on the lower 32 bits and the fixed SALT constants — the filter
1399 /// size N is not involved. So the same 8 bits get set regardless.
1400 ///
1401 /// Combined: every hash sets the *same bits* in the *same destination
1402 /// block* whether you fold or build fresh → filters are bit-identical.
1403 #[test]
1404 #[cfg_attr(miri, ignore)] // Takes too long
1405 fn test_sbbf_folded_equals_fresh() {
1406 let values = (0..5000).map(|i| format!("elem_{i}")).collect::<Vec<_>>();
1407 let hashes = values
1408 .iter()
1409 .map(|v| hash_as_bytes(v.as_str()))
1410 .collect::<Vec<_>>();
1411
1412 for num_blocks in [64, 256, 1024] {
1413 let half = num_blocks / 2;
1414
1415 // Build a filter with N blocks and insert all values.
1416 let mut original = Sbbf::new_with_num_of_bytes(num_blocks * 32);
1417 assert_eq!(original.num_blocks(), num_blocks);
1418 for &h in &hashes {
1419 original.insert_hash(h);
1420 }
1421
1422 // --- Per-hash verification of the two lemmas ---
1423 for &h in &hashes {
1424 // mask(h as u32) gives the 8-bit pattern that this hash sets
1425 // inside whichever block it lands in. It uses only the lower
1426 // 32 bits of h, so it's the same regardless of filter size.
1427 let mask = Block::mask(h as u32);
1428
1429 // Lemma 1 check: the block index in the original N-block
1430 // filter, divided by 2, should equal the block index in a
1431 // fresh N/2-block filter.
1432 let orig_idx = original.hash_to_block_index(h);
1433 assert!(orig_idx < num_blocks);
1434
1435 let fresh_idx = {
1436 let tmp = Sbbf(vec![Block::ZERO; half]);
1437 tmp.hash_to_block_index(h)
1438 };
1439 let folded_idx = orig_idx / 2;
1440 assert_eq!(
1441 fresh_idx, folded_idx,
1442 "Lemma 1 failed: fresh index {fresh_idx} != folded index {folded_idx}"
1443 );
1444
1445 // Lemma 2 check: every bit that mask wants to set is actually
1446 // present in the original block.
1447 //
1448 // mask.0[w] has exactly ONE bit set (see Block::mask: `1 << y`).
1449 // The block at orig_idx has many bits set from many inserts, so
1450 // we can't test equality — we test that the specific mask bit is
1451 // *present*:
1452 //
1453 // block_word & mask_word != 0
1454 // ⟺ "the one bit in the mask is set in the block"
1455 //
1456 // (Since mask_word has exactly 1 bit, `& mask != 0` is the same
1457 // as `& mask == mask` — but `!= 0` reads more naturally.)
1458 for w in 0..8 {
1459 assert_ne!(
1460 original.0[orig_idx].0[w] & mask.0[w],
1461 0,
1462 "Lemma 2 failed: mask bit not set in word {w} of block {orig_idx}"
1463 );
1464 }
1465 }
1466
1467 // --- Final bit-identical comparison ---
1468 // Fold the original N-block filter down to N/2 blocks.
1469 let mut folded = original.clone();
1470 folded.fold_n(1);
1471 assert_eq!(folded.num_blocks(), half);
1472
1473 // Build a fresh N/2-block filter with the same values.
1474 let mut fresh = Sbbf::new_with_num_of_bytes(half * 32);
1475 for &h in &hashes {
1476 fresh.insert_hash(h);
1477 }
1478
1479 // By lemmas 1 + 2, every block should be bit-identical.
1480 for j in 0..half {
1481 assert_eq!(
1482 folded.0[j].0, fresh.0[j].0,
1483 "Block {j} differs after fold (N={num_blocks} → {half})"
1484 );
1485 }
1486 }
1487 }
1488
1489 /// Inductive multi-step folding: folding k times from N blocks produces
1490 /// a filter bit-identical to a fresh N/2^k-block filter.
1491 ///
1492 /// `test_sbbf_folded_equals_fresh` proves the base case (one fold).
1493 /// This test applies folds *repeatedly*, checking after each step:
1494 ///
1495 /// ```text
1496 /// 512 ─fold→ 256 ─fold→ 128 ─…→ 1 (9 folds total)
1497 /// ```
1498 ///
1499 /// At each intermediate size we build a fresh filter and assert
1500 /// bit-equality, confirming the lemma composes across folds.
1501 #[test]
1502 #[cfg_attr(miri, ignore)] // Takes too long
1503 fn test_multi_step_fold() {
1504 let values = (0..3000).map(|i| format!("x_{i}")).collect::<Vec<_>>();
1505
1506 // Start with a 512-block filter.
1507 let mut filter = Sbbf::new_with_num_of_bytes(512 * 32);
1508 for v in &values {
1509 filter.insert(v.as_str());
1510 }
1511
1512 // Fold one level at a time, comparing against a fresh filter each step.
1513 for expected_blocks in [256, 128, 64, 32, 16, 8, 4, 2, 1] {
1514 filter.fold_n(1);
1515 assert_eq!(filter.num_blocks(), expected_blocks);
1516
1517 let mut fresh = Sbbf::new_with_num_of_bytes(expected_blocks * 32);
1518 for v in &values {
1519 fresh.insert(v.as_str());
1520 }
1521 for (fb, rb) in filter.0.iter().zip(fresh.0.iter()) {
1522 assert_eq!(fb.0, rb.0);
1523 }
1524 }
1525 }
1526
1527 /// test that the fpp estimator's overestimation doesn't cause fold_to_target_fpp
1528 /// to produce significantly oversized filters
1529 ///
1530 /// compare the final size after folding against the theoretical optimal size
1531 #[test]
1532 #[cfg_attr(miri, ignore)] // Takes too long
1533 fn test_fold_size_vs_optimal_fixed_size() {
1534 for (ndv, target_fpp) in [
1535 (1000, 0.05),
1536 (1000, 0.01),
1537 (5000, 0.05),
1538 (5000, 0.01),
1539 (10000, 0.05),
1540 ] {
1541 let values = (0..ndv).map(|i| format!("d_{i}")).collect::<Vec<_>>();
1542
1543 let mut folded = Sbbf::new_with_num_of_bytes(128 * 1024); // 128KB
1544 for v in &values {
1545 folded.insert(v.as_str());
1546 }
1547 folded.fold_to_target_fpp(target_fpp);
1548
1549 let folded_bytes = folded.num_blocks() * 32;
1550
1551 let optimal = Sbbf::new_with_ndv_fpp(ndv as u64, target_fpp).unwrap();
1552 let optimal_bytes = optimal.num_blocks() * 32;
1553
1554 let ratio = folded_bytes as f64 / optimal_bytes as f64;
1555
1556 assert_eq!(ratio, 1.0);
1557 }
1558 }
1559
1560 /// verify that a folded sbbf has the same empirical fpp as a fresh filter of the same size
1561 /// this bridges the bit-identity proof above with the FPP guarantee from the folding paper
1562 /// since the bits are identical, the false-positive rate must be too
1563 ///
1564 /// we measure fpp empirically by probing with values that were never inserted
1565 /// and counting how many are incorrectly marked as present
1566 #[test]
1567 #[cfg_attr(miri, ignore)] // Takes too long
1568 fn test_folded_fpp_matches_fresh_fpp() {
1569 let ndv = 2000;
1570 let num_probes = 50_000;
1571 let inserted = (0..ndv)
1572 .map(|i| format!("ins_{i}"))
1573 .collect::<Vec<String>>();
1574
1575 // probe values that were NOT inserted (different prefix guarantees no overlap)
1576 let probes = (0..num_probes)
1577 .map(|i| format!("probe_{i}"))
1578 .collect::<Vec<String>>();
1579
1580 // build a large filter and fold it down several times
1581 let mut folded = Sbbf::new_with_num_of_bytes(512 * 32); // 512 blocks
1582 for v in &inserted {
1583 folded.insert(v.as_str());
1584 }
1585
1586 // check FPP at each fold level
1587 for expected_blocks in [256, 128, 64, 32, 16, 8, 4, 2, 1] {
1588 folded.fold_n(1);
1589 assert_eq!(folded.num_blocks(), expected_blocks);
1590
1591 // build a fresh filter of the same size with the same values
1592 let mut fresh = Sbbf::new_with_num_of_bytes(expected_blocks * 32);
1593 for v in &inserted {
1594 fresh.insert(v.as_str());
1595 }
1596
1597 // measure empirical FPP on both
1598 let mut folded_fp = 0u64;
1599 let mut fresh_fp = 0u64;
1600 for p in &probes {
1601 if folded.check(p.as_str()) {
1602 folded_fp += 1;
1603 }
1604 if fresh.check(p.as_str()) {
1605 fresh_fp += 1;
1606 }
1607 }
1608
1609 // bit-identity means these must be exactly equal
1610 assert_eq!(folded_fp, fresh_fp);
1611 }
1612 }
1613}