…ache#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 apache#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]>

…ache#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 apache#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]>

…ache#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 apache#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]>

…ache#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 apache#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]>

Points the arrow-rs crates at adriangb/arrow-rs sbbf-batch-union-apis-60:
arrow-rs 60.0.0 + apache/arrow-rs#11088 + the commit of
apache/arrow-rs#11641. Remove once arrow-rs releases these APIs.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

Points the arrow-rs crates at adriangb/arrow-rs sbbf-batch-union-apis-60:
arrow-rs 60.0.0 + apache/arrow-rs#11088 + the commit of
apache/arrow-rs#11641. Remove once arrow-rs releases these APIs.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

…apache#11641)

# Which issue does this PR close?

- Relates to apache/datafusion#26169 (DataFusion PR:
apache/datafusion#26442)
- Related: apache#11088 (`Sbbf::estimated_fpp`, merged), apache#9628 (folding,
merged)

# Rationale for this change

DataFusion builds a parquet `Sbbf` as the membership test in the dynamic
filter of a hash join. Each build partition fills its own filter in
parallel with hashes it has already computed. The filters are merged
into one, the result is folded to the target fpp, and every probe row is
checked against it.

The public API cannot do this today:

| Need | Today |
| --- | --- |
| Insert precomputed hashes | `insert_hash` is private |
| Check many precomputed hashes fast | `check_hash` is private, and
exits early on a branch the CPU cannot predict |
| Merge filters built independently (one per thread or partition) | Not
possible |

Measured in DataFusion on 16M probe rows: a per-row branchy check takes
~104 ms, the branch-free check ~21 ms.

# What changes are included in this PR?

All additions are on `parquet::bloom_filter::Sbbf`:

| API | What |
| --- | --- |
| `insert_hash(&mut self, u64)` (now public) | Insert one precomputed
64-bit hash |
| `check_hashes(&self, &[u64]) -> BooleanBuffer` (feature `arrow`) |
Branch-free bulk check: tests all 8 words of the block with no early
exit |
| `union(&mut self, &Sbbf) -> Result<()>` | OR another filter into this
one. `other` must have the same number of blocks or a multiple of it. A
larger `other` is folded on the fly (same grouping as
`fold_to_target_fpp`), so `fold(a ∪ b) == fold(a) ∪ fold(b)` |

The hashes can come from any well-mixed 64-bit hash. `check` / `insert`
keep using the spec hash. The docs say the two only agree when the
caller uses the spec hash, and that `union` needs both filters built
with the same hash function.

There is no `insert_hashes`: it was a plain loop over `insert_hash`, so
a slice API gave no speedup. `check_hashes` stays because the `hash_api`
benchmark shows the branch-free check beats a per-hash early-exit loop
on mixed hit/miss queries. It is slightly slower when nearly every hash
misses.

# Are these changes tested?

- `check_hashes` equals `check_hash` for each hash.
- The union of per-chunk filters is bit-for-bit equal to one filter of
all hashes.
- Folding each part and then unioning equals folding the whole filter.
- A larger filter is folded on the fly. A smaller filter, or an empty
target, returns an error.
- Benchmark: `cargo bench -p parquet --bench bloom_filter -- hash_api`.

# Are there any user-facing changes?

New public API only. No breaking changes.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

---------

Co-authored-by: Claude Opus 5.5 <[email protected]>
Co-authored-by: Matt Butrovich <[email protected]>
Co-authored-by: Ed Seidl <[email protected]>