This is an automated email from the ASF dual-hosted git repository.
alamb pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new c505dfc7aa Add `Sbbf::estimated_fpp` to expose the bloom filter FPP
estimate (#11088)
c505dfc7aa is described below
commit c505dfc7aa6cb9796d33af69d015afc8c6b59a25
Author: Adrian Garcia Badaracco <[email protected]>
AuthorDate: Wed Sep 16 13:30:29 2026 -0500
Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate (#11088)
# Which issue does this PR close?
No issue filed. This is a small API addition and the rationale is below;
I can file one if you prefer.
# Rationale for this change
`Sbbf::fold_to_target_fpp` (added in #9628) already estimates a filter's
false positive probability from its average per-block fill, but callers
cannot read that estimate. A caller that needs it before folding, for
example to discard a filter that is already over its target FPP at build
size, must serialize the bitset and count set bits in the bytes. That
copies the full bitset and duplicates the formula outside the crate.
# What changes are included in this PR?
- Add `Sbbf::estimated_fpp`, which counts set bits directly on the
blocks and returns `fill^8`. It returns `1.0` for a filter with no
blocks.
- `num_folds_for_target_fpp` now uses the same fill calculation, so the
public estimate and the folding decision cannot drift apart.
# Are these changes tested?
Yes.
- `test_estimated_fpp_matches_serialized_bitset` checks that the result
is bit-for-bit equal to counting set bits in the `write_bitset` output,
for 32 B, 1 KiB, and 64 KiB filters with 0 to 100,000 inserted values.
- `test_estimated_fpp_bounds` covers an empty filter, a full filter, and
a filter with no blocks.
- `test_estimated_fpp_increases_when_folded` checks that folding does
not lower the estimate.
The existing folding tests continue to pass.
# Are there any user-facing changes?
Yes, one new public method, `Sbbf::estimated_fpp`. There are no breaking
changes.
---------
Co-authored-by: Claude Opus 5 <[email protected]>
---
parquet/src/bloom_filter/mod.rs | 68 +++++++++++++++++++++++++++++++++++++++--
1 file changed, 66 insertions(+), 2 deletions(-)
diff --git a/parquet/src/bloom_filter/mod.rs b/parquet/src/bloom_filter/mod.rs
index e66d1bbcfa..164b4c9444 100644
--- a/parquet/src/bloom_filter/mod.rs
+++ b/parquet/src/bloom_filter/mod.rs
@@ -578,6 +578,26 @@ impl Sbbf {
self.0.len()
}
+ /// Estimate the false positive probability (FPP) of this filter at its
current size.
+ ///
+ /// This is the same estimate [`Self::fold_to_target_fpp`] uses to choose
how far to fold.
+ ///
+ /// This lets a caller inspect a filter before folding or writing it, for
example to
+ /// discard a filter that already exceeds its target FPP. Returns `1.0`
for a filter
+ /// with no blocks.
+ pub fn estimated_fpp(&self) -> f64 {
+ if self.0.is_empty() {
+ return 1.0;
+ }
+ self.average_fill().powi(8)
+ }
+
+ /// Average fraction of bits set per block. The filter must have at least
one block.
+ fn average_fill(&self) -> f64 {
+ let total_set_bits: u64 = self.0.iter().map(|b|
u64::from(b.count_ones())).sum();
+ total_set_bits as f64 / (self.0.len() as f64 * 256.0)
+ }
+
/// Fold the bloom filter down to the smallest size that still meets the
target FPP
/// (False Positive Percentage).
///
@@ -646,8 +666,7 @@ impl Sbbf {
}
// Single pass: compute average per-block fill rate.
- let total_set_bits: u64 = self.0.iter().map(|b|
u64::from(b.count_ones())).sum();
- let avg_fill = total_set_bits as f64 / (len as f64 * 256.0);
+ let avg_fill = self.average_fill();
// Empty filter: can fold all the way down.
if avg_fill == 0.0 {
@@ -954,6 +973,51 @@ mod tests {
assert_eq!(sbbf.num_blocks(), 1);
}
+ #[test]
+ fn test_estimated_fpp_matches_serialized_bitset() {
+ for num_bytes in [BITSET_MIN_LENGTH, 1024, 64 * 1024] {
+ for ndv in [0u64, 1, 10, 100, 1_000, 10_000, 100_000] {
+ let mut sbbf = Sbbf::new_with_num_of_bytes(num_bytes);
+ for i in 0..ndv {
+ sbbf.insert(&i);
+ }
+
+ let mut bitset = Vec::new();
+ sbbf.write_bitset(&mut bitset).unwrap();
+ let set_bits: u64 = bitset.iter().map(|b|
u64::from(b.count_ones())).sum();
+ let expected = (set_bits as f64 / (bitset.len() as f64 *
8.0)).powi(8);
+
+ assert_eq!(
+ sbbf.estimated_fpp().to_bits(),
+ expected.to_bits(),
+ "{num_bytes} bytes, {ndv} values"
+ );
+ }
+ }
+ }
+
+ #[test]
+ fn test_estimated_fpp_bounds() {
+ assert_eq!(Sbbf::new_with_num_of_bytes(1024).estimated_fpp(), 0.0);
+ assert_eq!(Sbbf::new(&[0xFF; 1024]).estimated_fpp(), 1.0);
+ assert_eq!(Sbbf::new(&[]).estimated_fpp(), 1.0);
+ }
+
+ #[test]
+ fn test_estimated_fpp_increases_when_folded() {
+ let mut sbbf = Sbbf::new_with_num_of_bytes(64 * 1024);
+ for i in 0..1_000 {
+ sbbf.insert(&i);
+ }
+ let before = sbbf.estimated_fpp();
+ sbbf.fold_n(3);
+ assert!(
+ sbbf.estimated_fpp() > before,
+ "folding must not lower the estimate: {before} -> {}",
+ sbbf.estimated_fpp()
+ );
+ }
+
#[test]
#[should_panic(expected = "Cannot fold 1 times: need at least 2 blocks,
have 1")]
fn test_fold_n_panics_at_minimum_size() {
