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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
