Skip to main content

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}