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/10/17 06:54:05 UTC
[PR] Add Sbbf hash, sharded insert and Arrow array batch APIs [arrow-rs]
adriangb opened a new pull request, #11641:
URL: https://github.com/apache/arrow-rs/pull/11641
# Which issue does this PR close?
- Relates to apache/datafusion#26169 (DataFusion PR: DFPR_LINK)
- Related: #11549 (`ArrowSbbf`, open), #11088 (`Sbbf::estimated_fpp`, merged), #9628 (folding, merged)
# Rationale for this change
DataFusion wants to use one parquet `Sbbf` as the membership test in the dynamic filter of a hash join. The filter holds all build side keys and DataFusion tests every probe row against it. Today this is not possible or is slow with the public API:
| Need | Today |
| --- | --- |
| Hash a value once, insert or check the hash later | `insert_hash` / `check_hash` are private |
| Fill one large filter from many threads | Only `&mut self` inserts: one thread |
| Insert or check a whole Arrow array, hashed as `ArrowWriter` writes it | Only per-value `insert` / `check` of parquet physical values |
Micro benchmark (`cargo bench -p parquet --features arrow --bench bloom_filter_arrow`, laptop under load, indicative only):
| Case | Time |
| --- | --- |
| Check 1M `Int64` with `check_array` | 8.2 ms |
| Check 1M `Int64` with `hash_array` + `check_hash` per row | 15.5 ms |
| Check 1M `Utf8` with `check_array` | 13.0 ms |
| Check 1M `Utf8` with `hash_array` + `check_hash` per row | 20.7 ms |
| Insert 16M hashes, one thread (32 MiB filter) | 485 ms |
| Insert 16M hashes, `shards_mut(8)` (bucketing included) | 81 ms |
In DataFusion (draft PR above), the global bloom filter replaces a per-partition `CASE` routing expression. On TPC-H SF100 it cuts query CPU time to 0.22x-0.65x of `main` for Q17, Q9, Q5 and Q18.
# What changes are included in this PR?
All additions are in `parquet::bloom_filter`.
| API | Why |
| --- | --- |
| `Sbbf::hash_value(&T) -> u64` | Public form of the spec hash (xxHash64, seed 0, plain encoding) |
| `Sbbf::insert_hash`, `Sbbf::check_hash` (now `pub`) | Use a hash many times, or compute hashes on other threads |
| `Sbbf::shard_index(hash, n)`, `Sbbf::shards_mut(n) -> Vec<SbbfShard>`, `SbbfShard::insert_hash` | Split the filter into `n` disjoint block ranges. Threads fill their own shard without locks or atomics. The result is equal to a serial fill (tested) |
| `Sbbf::hash_array`, `Sbbf::insert_array`, `Sbbf::check_array`, `Sbbf::supports_data_type` (feature `arrow`) | Batch insert/check of Arrow arrays. Each value is hashed as the parquet physical value that `ArrowWriter` writes (`Int8` as `INT32`, decimals by precision, strings as bytes, ...). The type dispatch is done once per array. `check_array` uses a branch-free block test. Null slots are skipped (insert) or `false` (check) |
Notes:
- `estimated_fpp` and `fold_to_target_fpp` are already on `main` (#11088, #9628). This PR reuses them and does not add `union` or fold variants.
- Overlap with #11549: that PR adds `ArrowSbbf`, which checks Arrow arrays against a filter read from a file, with a `ColumnDescriptor`. This PR needs filters that are built from Arrow data, with no parquet schema, and needs insert and a parallel fill. The type mapping is the same (`ArrowWriter` defaults). If #11549 merges first, I can make `hash_array` reuse its `visit_i32` / `visit_i64` visitors, or move these methods to `ArrowSbbf`. Feedback on the preferred shape is welcome.
- Floats are not supported (`-0.0`/`0.0` and `NaN` have more than one bit pattern), and neither are booleans, dictionaries and nested types. They return an error.
- `hash_array` uses an inlined xxHash64 for 4 and 8 byte values. A test checks it against `twox_hash` for many values.
# Are these changes tested?
- Unit tests: `hash_value` / `insert_hash` / `check_hash`, branch-free check equals `check`, `shards_mut` fill equals a serial fill (1, 3, 8, 64 shards; more shards than blocks; panic on a wrong shard).
- Arrow tests: insert then check for 19 Arrow types (with nulls), `hash_array` equals `hash_value` of the physical value, unsupported types return errors, and a round trip with `ArrowWriter`: the written filter finds every value with `check_array`, and a filter from `insert_array` (folded to the same fpp) is bit-for-bit equal to the written one.
- New criterion bench `bloom_filter_arrow`.
# Are there any user-facing changes?
New public API only. No breaking changes.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6863650222
@etseidl addressed your review. I also replaced `insert_hashes` with `insert_hash` which moves the loop to the caller but is a more flexible API (avoids materializing a slice, etc.). It was a loop internally.
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "mbutrovich (via GitHub) via github" <gi...@arrow.apache.org>.
mbutrovich commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6864440459
FYI I'm taking a review pass now.
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "etseidl (via GitHub) via github" <gi...@arrow.apache.org>.
etseidl commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6863988561
Thanks @adriangb, this is next up in my queue.
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "mbutrovich (via GitHub) via github" <gi...@arrow.apache.org>.
mbutrovich commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568537149
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
Review Comment:
> Nonetheless, I softened the wording on the comment and kept it generally correct without going into this level of detail.
The comment on [`Block::check_branch_free`](https://github.com/apache/arrow-rs/blob/314d407c7018af3f6ea32e228bae7599207ce9cc/parquet/src/bloom_filter/mod.rs#L248-L250) still says "so it is faster when many hashes are checked in a loop", the same text as in the first commit. Your table shows the early exit winning on all-miss queries against filters with 1% and 5% of bits set. Could we say when each one wins? For example:
```rust
/// Same result as [`Block::check`], but tests all 8 words without an early
/// exit. This avoids a mispredicted branch when hits and misses are mixed
/// or the filter is well filled. The early exit is faster when nearly
/// every hash misses a sparse filter.
```
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "mbutrovich (via GitHub) via github" <gi...@arrow.apache.org>.
mbutrovich commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568553608
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -536,8 +552,15 @@ impl Sbbf {
self.insert_hash(hash_as_bytes(value));
}
- /// Insert a hash into the filter
- fn insert_hash(&mut self, hash: u64) {
+ /// Inserts a precomputed 64-bit hash.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// so values can be hashed in bulk with the caller's own hash function
+ /// (for example, a columnar hash of a multi-column key). [`Self::check`]
+ /// only finds values whose hashes were computed as the Parquet
+ /// specification requires (xxHash64, seed 0, of the plain encoding); use
+ /// [`Self::check_hashes`] with the same hash function instead.
+ pub fn insert_hash(&mut self, hash: u64) {
Review Comment:
`insert_hash` is public in every build, but `check_hashes` is the only way to query those hashes, and it needs the `arrow` feature. Without `arrow`, a caller can fill a filter with their own hashes and never check it. With `arrow`, a caller that has one probe hash has to build a `BooleanBuffer`.
Should `check_hash` be public too? The early exit is a reason to offer `check_hashes` for bulk probes, but it doesn't stop `check_hash` from being the single-hash counterpart to `insert_hash`. If it becomes public, the `insert_hash` docs could point to it alongside `check_hashes`.
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +586,60 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hash`]) in bulk,
+ /// without data-dependent branches.
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
Review Comment:
`check_hashes` panics on a filter with no blocks, because `hash_to_block_index` returns 0 and `self.0[0]` is out of bounds. [`Sbbf::new`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/parquet/src/bloom_filter/mod.rs#L363-L379) returns such a filter for any bitset shorter than 32 bytes, so `Sbbf::new(&[0; 31]).check_hashes(&[1])` panics. `insert_hash` panics the same way.
This predates the PR: `insert` and `check` on `main` go through the same [`hash_to_block_index`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/parquet/src/bloom_filter/mod.rs#L530-L532) and index. But `union` in this PR returns an error for an empty filter, so the three new methods disagree on that input. Do you want to handle it here, or in a separate PR? Here, an empty filter contains nothing, so `check_hashes` could return all unset bits, and `insert_hash` could document the panic in a `# Panics` section. A separate PR could stop `Sbbf::new` from producing an empty filter.
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -536,8 +552,15 @@ impl Sbbf {
self.insert_hash(hash_as_bytes(value));
}
- /// Insert a hash into the filter
- fn insert_hash(&mut self, hash: u64) {
+ /// Inserts a precomputed 64-bit hash.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// so values can be hashed in bulk with the caller's own hash function
+ /// (for example, a columnar hash of a multi-column key). [`Self::check`]
+ /// only finds values whose hashes were computed as the Parquet
+ /// specification requires (xxHash64, seed 0, of the plain encoding); use
+ /// [`Self::check_hashes`] with the same hash function instead.
Review Comment:
A filter filled through `insert_hash` with a non-spec hash can still be written with `Sbbf::write`, and [`header()`](https://github.com/apache/arrow-rs/blob/314d407c7018af3f6ea32e228bae7599207ce9cc/parquet/src/bloom_filter/mod.rs#L440-L448) always records `BloomFilterHash::XXHASH`. A reader would then hash its probe values with xxHash64, miss them, and skip row groups that hold matching rows. Could we say so here?
```suggestion
/// Inserts a precomputed 64-bit hash.
///
/// The filter can hold hashes from any well-mixed 64-bit hash function,
/// so values can be hashed in bulk with the caller's own hash function
/// (for example, a columnar hash of a multi-column key). [`Self::check`]
/// only finds values whose hashes were computed as the Parquet
/// specification requires (xxHash64, seed 0, of the plain encoding); use
/// [`Self::check_hashes`] with the same hash function instead.
///
/// Only write a filter to a Parquet file (with [`Self::write`]) if every
/// hash was computed as the specification requires. The header always
/// names xxHash64, so readers would get false negatives and skip row
/// groups that hold matching rows.
```
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +586,60 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hash`]) in bulk,
+ /// without data-dependent branches.
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
+ arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
+ self.check_hash_branch_free(hashes[i])
+ })
+ }
+
+ /// Adds the values of `other` to this filter, so that afterwards it
+ /// contains every value that either filter contained.
+ ///
+ /// `other` must have at least as many blocks as this filter, and a
+ /// multiple of them. When it has more, it is folded to the size of this
+ /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
+ /// `other`. Folding and union commute: the result is the same as
+ /// inserting the values of both filters into one filter and folding it
+ /// to this size. This lets independent filters (for example, one per
+ /// thread) be built and then merged.
+ ///
+ /// Both filters must have been populated with the same hash function
+ /// (the Parquet xxHash64 used by [`Self::insert`], or the same function
+ /// used for [`Self::insert_hash`]); otherwise the result is
+ /// meaningless. This cannot be checked.
+ ///
+ /// Returns an error if the sizes are incompatible, including if this
+ /// filter has no blocks.
Review Comment:
The new public methods have no examples. Could we add one that runs as a doctest? This one on `union` calls `insert_hash` and `check_hashes` too, and it covers folding on the fly and the size error.
```suggestion
/// Returns an error if the sizes are incompatible, including if this
/// filter has no blocks.
///
/// # Example
///
/// ```
/// # use parquet::bloom_filter::Sbbf;
/// // One filter per partition, filled with precomputed hashes
/// let mut a = Sbbf::new_with_num_of_bytes(1024);
/// a.insert_hash(0x0123_4567_89ab_cdef);
/// let mut b = Sbbf::new_with_num_of_bytes(4096);
/// b.insert_hash(0xfedc_ba98_7654_3210);
///
/// // `b` has 4 times as many blocks as `a`, so it is folded on the fly
/// a.union(&b).unwrap();
/// let found = a.check_hashes(&[0x0123_4567_89ab_cdef, 0xfedc_ba98_7654_3210]);
/// assert!(found.value(0) && found.value(1));
///
/// // A smaller filter cannot be unioned into a larger one
/// assert!(b.union(&a).is_err());
/// ```
```
--
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::insert_hashes, Sbbf::check_hashes and Sbbf::union [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568048179
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
+ /// checking one hash at a time.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
+ arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
+ self.check_hash_branch_free(hashes[i])
+ })
+ }
+
+ /// Adds the values of `other` to this filter, so that afterwards it
+ /// contains every value that either filter contained.
+ ///
+ /// `other` must have at least as many blocks as this filter, and a
+ /// multiple of them. When it has more, it is folded to the size of this
+ /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
+ /// `other`. Folding and union commute: the result is the same as
+ /// inserting the values of both filters into one filter and folding it
+ /// to this size. This lets independent filters (for example, one per
+ /// thread) be built and then merged.
+ pub fn union(&mut self, other: &Sbbf) -> Result<(), ParquetError> {
+ let (len, other_len) = (self.0.len(), other.0.len());
+ if other_len < len || other_len % len != 0 {
Review Comment:
Addressed in e828a78
--
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 hash and Arrow array batch APIs [arrow-rs]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6250875417
Thanks @mbutrovich . I reviewed #11549 and plan to restack this work on it once it merges (experiment for that in https://github.com/apache/arrow-rs/pull/11685)
--
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::insert_hashes, Sbbf::check_hashes and Sbbf::union [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6775818671
I've rebased. I can't mark this as ready / non-draft because I've hit my PR limit.
--
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 hash and Arrow array batch APIs [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6250987026
> Thanks @mbutrovich . I reviewed #11549 and plan to restack this work on it once it merges (experiment for that in #11685)
Sounds good, thanks for the review pass! I was excited to see someone with another use for it so wanted to make sure it lands with what you need.
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568121802
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -857,6 +931,65 @@ fn read_bloom_filter_header_and_length(buffer: &[u8]) -> Result<(BloomFilterHead
mod tests {
use super::*;
+ fn bitset(f: &Sbbf) -> Vec<u8> {
+ let mut out = vec![];
+ f.write_bitset(&mut out).unwrap();
+ out
+ }
+
+ #[test]
+ fn test_branch_free_check_matches_check() {
+ let mut filter = Sbbf::new_with_num_of_bytes(256);
+ for i in 0..200u64 {
+ filter.insert(&(i * 7));
+ }
+ for i in 0..5000u64 {
+ let h = hash_as_bytes(&i);
+ assert_eq!(filter.check_hash(h), filter.check_hash_branch_free(h));
+ }
+ }
+
+ #[cfg(feature = "arrow")]
+ #[test]
+ fn test_check_hashes_matches_check_hash() {
+ let hashes: Vec<u64> = (0..5000u64).map(|i| hash_as_bytes(&i)).collect();
+ let mut filter = Sbbf::new_with_num_of_bytes(256);
+ filter.insert_hashes(&hashes[..200]);
+ let result = filter.check_hashes(&hashes);
+ for (i, &h) in hashes.iter().enumerate() {
+ assert_eq!(result.value(i), filter.check_hash(h));
+ }
+ assert!((0..200).all(|i| result.value(i)));
+ }
+
+ #[test]
+ fn test_union_of_parts_matches_one_filter() {
+ let hashes: Vec<u64> = (0..100_000u64).map(|i| hash_as_bytes(&i)).collect();
+ let mut whole = Sbbf::new_with_num_of_bytes(1 << 20);
+ whole.insert_hashes(&hashes);
+ let mut merged = Sbbf::new_with_num_of_bytes(1 << 20);
+ for chunk in hashes.chunks(7_000) {
+ let mut part = Sbbf::new_with_num_of_bytes(1 << 20);
+ part.insert_hashes(chunk);
+ merged.union(&part).unwrap();
+ }
+ assert_eq!(bitset(&whole), bitset(&merged));
+ // union then fold == fold then union
+ let mut folded = whole.clone();
+ folded.fold_to_target_fpp(0.01);
+ merged.fold_to_target_fpp(0.01);
+ assert_eq!(bitset(&folded), bitset(&merged));
Review Comment:
Done in 314d407c7018af3f6ea32e228bae7599207ce9cc
--
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 hash, sharded insert and Arrow array batch APIs [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6235912545
Can we get some extra review cycles on #11549 and land that first, since it already brings in `Sbbf`?
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "etseidl (via GitHub) via github" <gi...@arrow.apache.org>.
etseidl commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6868640282
Thanks for the review @mbutrovich. Hopefully merging will clear the audit CI failure. I think this is ready to go. 🚀
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "etseidl (via GitHub) via github" <gi...@arrow.apache.org>.
etseidl commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6868685410
Thanks again @adriangb. Do you think we're ready for #11681 now? And do you have time to take a whack at it? I think you have more downstream context than I do.
--
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::insert_hashes, Sbbf::check_hashes and Sbbf::union [arrow-rs]
Posted by "etseidl (via GitHub) via github" <gi...@arrow.apache.org>.
etseidl commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6587797081
@adriangb do you want to dust this one off? I think we're close to the point of pulling bloom filters into a new crate.
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6868927173
wohoo! thanks folks
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4569591309
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
Review Comment:
Sorry looks like 71e9f1e7ab5cc709a27608391fe06ef773ccae7a had gotten lost / overwritten. I now adopted your wording from https://github.com/apache/arrow-rs/pull/11641#discussion_r4568537149 (bfa6657e3)
--
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::insert_hashes, Sbbf::check_hashes and Sbbf::union [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568054087
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
+ /// checking one hash at a time.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
+ arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
+ self.check_hash_branch_free(hashes[i])
+ })
+ }
+
+ /// Adds the values of `other` to this filter, so that afterwards it
+ /// contains every value that either filter contained.
+ ///
+ /// `other` must have at least as many blocks as this filter, and a
+ /// multiple of them. When it has more, it is folded to the size of this
+ /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
+ /// `other`. Folding and union commute: the result is the same as
+ /// inserting the values of both filters into one filter and folding it
+ /// to this size. This lets independent filters (for example, one per
+ /// thread) be built and then merged.
Review Comment:
👍🏻 done in 0b135b53c17cdddf8d7d0f5f297d87d5f1618518
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568165288
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
Review Comment:
You're right. It's not *always* faster. I ran some benchmarks and tried to distill the results into a comment (71e9f1e7ab5cc709a27608391fe06ef773ccae7a).
You're right, it's not always faster, so I dropped the performance claim: the doc now just says it is a branch-free bulk check.
TLDR of my benchmarks (2 MiB filter, precomputed hashes, the early-exit check called once per hash via `BooleanBuffer::collect_bool`, as a caller would write it):
With hits and misses mixed, branch-free is faster. At 50% hits it is 1.7–2.2x faster, depending on filter size.
When every hash misses, it depends on how full the filter is:
bits set | early exit vs branch-free
-- | --
1% | 0.85x (early exit wins)
5% | 0.92x
13% | 1.04x
28% | 1.43x
51% (sized for 1% fpp) | 2.38x
A miss in a nearly empty filter fails on the first word, so the early exit predicts well. In a filter sized for its target fpp, a miss fails at an unpredictable word and the branch mispredicts. Both versions pay the same one-cache-line load, so testing all 8 words costs little extra.
So the early exit only wins on a nearly empty filter, and even then by less than 15%. The new `hash_api` benchmark in `parquet/benches/bloom_filter.rs` covers sparse and 1%-fpp filters with miss, hit and mixed queries.
Nonetheless, I softened the wording on the comment and kept it generally correct without going into this level of detail.
--
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::insert_hashes, Sbbf::check_hashes and Sbbf::union [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#issuecomment-6817599275
@etseidl I've marked this as ready
--
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::insert_hashes, Sbbf::check_hashes and Sbbf::union [arrow-rs]
Posted by "etseidl (via GitHub) via github" <gi...@arrow.apache.org>.
etseidl commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4556143783
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -857,6 +931,65 @@ fn read_bloom_filter_header_and_length(buffer: &[u8]) -> Result<(BloomFilterHead
mod tests {
use super::*;
+ fn bitset(f: &Sbbf) -> Vec<u8> {
+ let mut out = vec![];
+ f.write_bitset(&mut out).unwrap();
+ out
+ }
+
+ #[test]
+ fn test_branch_free_check_matches_check() {
+ let mut filter = Sbbf::new_with_num_of_bytes(256);
+ for i in 0..200u64 {
+ filter.insert(&(i * 7));
+ }
+ for i in 0..5000u64 {
+ let h = hash_as_bytes(&i);
+ assert_eq!(filter.check_hash(h), filter.check_hash_branch_free(h));
+ }
+ }
+
+ #[cfg(feature = "arrow")]
+ #[test]
+ fn test_check_hashes_matches_check_hash() {
+ let hashes: Vec<u64> = (0..5000u64).map(|i| hash_as_bytes(&i)).collect();
+ let mut filter = Sbbf::new_with_num_of_bytes(256);
+ filter.insert_hashes(&hashes[..200]);
+ let result = filter.check_hashes(&hashes);
+ for (i, &h) in hashes.iter().enumerate() {
+ assert_eq!(result.value(i), filter.check_hash(h));
+ }
+ assert!((0..200).all(|i| result.value(i)));
+ }
+
+ #[test]
+ fn test_union_of_parts_matches_one_filter() {
+ let hashes: Vec<u64> = (0..100_000u64).map(|i| hash_as_bytes(&i)).collect();
+ let mut whole = Sbbf::new_with_num_of_bytes(1 << 20);
+ whole.insert_hashes(&hashes);
+ let mut merged = Sbbf::new_with_num_of_bytes(1 << 20);
+ for chunk in hashes.chunks(7_000) {
+ let mut part = Sbbf::new_with_num_of_bytes(1 << 20);
+ part.insert_hashes(chunk);
+ merged.union(&part).unwrap();
+ }
+ assert_eq!(bitset(&whole), bitset(&merged));
+ // union then fold == fold then union
+ let mut folded = whole.clone();
+ folded.fold_to_target_fpp(0.01);
+ merged.fold_to_target_fpp(0.01);
+ assert_eq!(bitset(&folded), bitset(&merged));
Review Comment:
This is folding two filters we've already established above are identical. I think the loop above needs to be repeated, with each part folded before unioning into `merged`.
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
+ /// checking one hash at a time.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
+ arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
+ self.check_hash_branch_free(hashes[i])
+ })
+ }
+
+ /// Adds the values of `other` to this filter, so that afterwards it
+ /// contains every value that either filter contained.
+ ///
+ /// `other` must have at least as many blocks as this filter, and a
+ /// multiple of them. When it has more, it is folded to the size of this
+ /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
+ /// `other`. Folding and union commute: the result is the same as
+ /// inserting the values of both filters into one filter and folding it
+ /// to this size. This lets independent filters (for example, one per
+ /// thread) be built and then merged.
+ pub fn union(&mut self, other: &Sbbf) -> Result<(), ParquetError> {
+ let (len, other_len) = (self.0.len(), other.0.len());
+ if other_len < len || other_len % len != 0 {
Review Comment:
This will panic if `len == 0`. should guard against that.
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
+ /// checking one hash at a time.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
+ arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
+ self.check_hash_branch_free(hashes[i])
+ })
+ }
+
+ /// Adds the values of `other` to this filter, so that afterwards it
+ /// contains every value that either filter contained.
+ ///
+ /// `other` must have at least as many blocks as this filter, and a
+ /// multiple of them. When it has more, it is folded to the size of this
+ /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
+ /// `other`. Folding and union commute: the result is the same as
+ /// inserting the values of both filters into one filter and folding it
+ /// to this size. This lets independent filters (for example, one per
+ /// thread) be built and then merged.
Review Comment:
Should we also state that the same hash needs to be used for `other`?
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
Review Comment:
Is it always much faster? Should this be qualified at all?
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "etseidl (via GitHub) via github" <gi...@arrow.apache.org>.
etseidl merged PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4569711514
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -536,8 +552,15 @@ impl Sbbf {
self.insert_hash(hash_as_bytes(value));
}
- /// Insert a hash into the filter
- fn insert_hash(&mut self, hash: u64) {
+ /// Inserts a precomputed 64-bit hash.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// so values can be hashed in bulk with the caller's own hash function
+ /// (for example, a columnar hash of a multi-column key). [`Self::check`]
+ /// only finds values whose hashes were computed as the Parquet
+ /// specification requires (xxHash64, seed 0, of the plain encoding); use
+ /// [`Self::check_hashes`] with the same hash function instead.
+ pub fn insert_hash(&mut self, hash: u64) {
Review Comment:
I'd propose we wait until someone requests it (the use I have in Datafusion doesn't need it) but happy to do it now for API parity if you'd like.
--
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::check_hashes and Sbbf::union, make Sbbf::insert_hash public [arrow-rs]
Posted by "adriangb (via GitHub) via github" <gi...@arrow.apache.org>.
adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4569715561
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +586,60 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hash`]) in bulk,
+ /// without data-dependent branches.
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
Review Comment:
Handled as per your suggestion in 0cc21e1a3. I agree a followup should make `Sbbf::new` return an error.
--
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