You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "adriangb (via GitHub)" <gi...@apache.org> on 2026/09/15 01:16:41 UTC
[PR] Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate [arrow-rs]
adriangb opened a new pull request, #11088:
URL: https://github.com/apache/arrow-rs/pull/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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #11088:
URL: https://github.com/apache/arrow-rs/pull/11088#issuecomment-5702552534
Thanks @adriangb and @etseidl
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #11088:
URL: https://github.com/apache/arrow-rs/pull/11088
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate [arrow-rs]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on PR #11088:
URL: https://github.com/apache/arrow-rs/pull/11088#issuecomment-5673202926
@Jefffrey would appreciate a review on this 🙏🏻
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate [arrow-rs]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on PR #11088:
URL: https://github.com/apache/arrow-rs/pull/11088#issuecomment-5687814865
Thanks @alamb !
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate [arrow-rs]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on code in PR #11088:
URL: https://github.com/apache/arrow-rs/pull/11088#discussion_r4020028215
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -578,6 +578,32 @@ impl Sbbf {
self.0.len()
}
+ /// Estimate the false positive probability (FPP) of this filter at its current size.
+ ///
+ /// A membership check tests 8 bits within a single 256-bit block, so with an average
Review Comment:
Good call, trimmed it down to the shared-estimate note and the use case in 20121072c8.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add `Sbbf::estimated_fpp` to expose the bloom filter FPP estimate [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #11088:
URL: https://github.com/apache/arrow-rs/pull/11088#discussion_r4019850801
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -578,6 +578,32 @@ impl Sbbf {
self.0.len()
}
+ /// Estimate the false positive probability (FPP) of this filter at its current size.
+ ///
+ /// A membership check tests 8 bits within a single 256-bit block, so with an average
Review Comment:
I think we could reduce the verbosity of this comment to make it easier to read
For example, the details of how the membership test works seems unecessary. It seems like the core message here would be that "this is the same estimate ..." and "this lets a caller inspect ..."
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org