Skip to content

Commit e4d721a

Browse files
adriangbclaudembutrovichetseidl
authored
Add Sbbf::check_hashes and Sbbf::union, make Sbbf::insert_hash public (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]>
1 parent df096d7 commit e4d721a

3 files changed

Lines changed: 294 additions & 2 deletions

File tree

‎parquet/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -353,6 +353,7 @@ required-features = ["arrow"]
353353

354354
[[bench]]
355355
name = "bloom_filter"
356+
required-features = ["arrow"]
356357
harness = false
357358

358359
[[bench]]

‎parquet/benches/bloom_filter.rs‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -206,12 +206,80 @@ fn bench_check(c: &mut Criterion) {
206206
group.finish();
207207
}
208208

209+
/// Benchmark `Sbbf::insert_hash` and `Sbbf::check_hashes` with precomputed
210+
/// hashes, as a caller that hashes values in bulk uses them.
211+
///
212+
/// `check_hashes` is measured on miss-only, hit-only and randomly mixed (50%)
213+
/// queries, against a sparse filter (`sparse`, about 5% of bits set) and one
214+
/// sized for 1% FPP (`fpp1`, about half the bits set).
215+
fn bench_hash_api(c: &mut Criterion) {
216+
const NUM_BYTES: usize = 2 * 1024 * 1024;
217+
const NUM_QUERIES: usize = 50_000;
218+
let fills: [(&str, usize); 2] = [("sparse", 100_000), ("fpp1", 1_500_000)];
219+
220+
let mut group = c.benchmark_group("hash_api");
221+
group.throughput(Throughput::Elements(NUM_QUERIES as u64));
222+
223+
for (label, ndv) in fills {
224+
let mut rng = StdRng::seed_from_u64(0xC0FFEE);
225+
// Inserted hashes have the low bit clear and misses have it set, so
226+
// the two sets are disjoint.
227+
let inserted: Vec<u64> = (0..ndv).map(|_| rng.random::<u64>() & !1).collect();
228+
let mut filter = Sbbf::new_with_num_of_bytes(NUM_BYTES);
229+
for &h in &inserted {
230+
filter.insert_hash(h);
231+
}
232+
let miss = |rng: &mut StdRng| rng.random::<u64>() | 1;
233+
let hit = |rng: &mut StdRng| inserted[rng.random_range(0..inserted.len())];
234+
let inputs: [(&str, Vec<u64>); 3] = [
235+
(
236+
"check_miss",
237+
(0..NUM_QUERIES).map(|_| miss(&mut rng)).collect(),
238+
),
239+
(
240+
"check_hit",
241+
(0..NUM_QUERIES).map(|_| hit(&mut rng)).collect(),
242+
),
243+
(
244+
"check_mixed",
245+
(0..NUM_QUERIES)
246+
.map(|_| {
247+
if rng.random::<bool>() {
248+
hit(&mut rng)
249+
} else {
250+
miss(&mut rng)
251+
}
252+
})
253+
.collect(),
254+
),
255+
];
256+
for (name, hashes) in &inputs {
257+
group.bench_with_input(BenchmarkId::new(*name, label), hashes, |b, hashes| {
258+
b.iter(|| filter.check_hashes(hint::black_box(hashes)))
259+
});
260+
}
261+
}
262+
263+
let mut rng = StdRng::seed_from_u64(0xC0FFEE);
264+
let to_insert: Vec<u64> = (0..NUM_QUERIES).map(|_| rng.random()).collect();
265+
let mut filter = Sbbf::new_with_num_of_bytes(NUM_BYTES);
266+
group.bench_function("insert", |b| {
267+
b.iter(|| {
268+
for &h in &to_insert {
269+
filter.insert_hash(hint::black_box(h));
270+
}
271+
})
272+
});
273+
group.finish();
274+
}
275+
209276
criterion_group!(
210277
benches,
211278
bench_fold_to_target_fpp,
212279
bench_insert_and_fold,
213280
bench_insert_only,
214281
bench_insert,
215282
bench_check,
283+
bench_hash_api,
216284
);
217285
criterion_main!(benches);

‎parquet/src/bloom_filter/mod.rs‎

Lines changed: 225 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -244,6 +244,23 @@ impl Block {
244244
}
245245
}
246246

247+
impl 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+
247264
impl std::ops::Index<usize> for Block {
248265
type Output = u32;
249266

@@ -536,8 +553,25 @@ impl Sbbf {
536553
self.insert_hash(hash_as_bytes(value));
537554
}
538555

539-
/// Insert a hash into the filter
540-
fn insert_hash(&mut self, hash: u64) {
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) {
541575
let block_index = self.hash_to_block_index(hash);
542576
self.0[block_index].insert(hash as u32)
543577
}
@@ -563,6 +597,91 @@ impl Sbbf {
563597
self.0[block_index].check(hash as u32)
564598
}
565599

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+
566685
/// Return the total in memory size of this bloom filter in bytes
567686
pub(crate) fn estimated_memory_size(&self) -> usize {
568687
self.0.capacity() * std::mem::size_of::<Block>()
@@ -857,6 +976,110 @@ fn read_bloom_filter_header_and_length(buffer: &[u8]) -> Result<(BloomFilterHead
857976
mod tests {
858977
use super::*;
859978

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+
8601083
#[test]
8611084
fn test_bloom_filter_read_range_overflow() {
8621085
assert!(bloom_filter_read_range(u64::MAX, 0..1).is_err());

0 commit comments

Comments
 (0)