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: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to