Repository navigation
Commit e4d721a
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
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
353 | 353 | | |
354 | 354 | | |
355 | 355 | | |
| 356 | + | |
356 | 357 | | |
357 | 358 | | |
358 | 359 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
206 | 206 | | |
207 | 207 | | |
208 | 208 | | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
209 | 276 | | |
210 | 277 | | |
211 | 278 | | |
212 | 279 | | |
213 | 280 | | |
214 | 281 | | |
215 | 282 | | |
| 283 | + | |
216 | 284 | | |
217 | 285 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
244 | 244 | | |
245 | 245 | | |
246 | 246 | | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
247 | 264 | | |
248 | 265 | | |
249 | 266 | | |
| |||
536 | 553 | | |
537 | 554 | | |
538 | 555 | | |
539 | | - | |
540 | | - | |
| 556 | + | |
| 557 | + | |
| 558 | + | |
| 559 | + | |
| 560 | + | |
| 561 | + | |
| 562 | + | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
| 566 | + | |
| 567 | + | |
| 568 | + | |
| 569 | + | |
| 570 | + | |
| 571 | + | |
| 572 | + | |
| 573 | + | |
| 574 | + | |
541 | 575 | | |
542 | 576 | | |
543 | 577 | | |
| |||
563 | 597 | | |
564 | 598 | | |
565 | 599 | | |
| 600 | + | |
| 601 | + | |
| 602 | + | |
| 603 | + | |
| 604 | + | |
| 605 | + | |
| 606 | + | |
| 607 | + | |
| 608 | + | |
| 609 | + | |
| 610 | + | |
| 611 | + | |
| 612 | + | |
| 613 | + | |
| 614 | + | |
| 615 | + | |
| 616 | + | |
| 617 | + | |
| 618 | + | |
| 619 | + | |
| 620 | + | |
| 621 | + | |
| 622 | + | |
| 623 | + | |
| 624 | + | |
| 625 | + | |
| 626 | + | |
| 627 | + | |
| 628 | + | |
| 629 | + | |
| 630 | + | |
| 631 | + | |
| 632 | + | |
| 633 | + | |
| 634 | + | |
| 635 | + | |
| 636 | + | |
| 637 | + | |
| 638 | + | |
| 639 | + | |
| 640 | + | |
| 641 | + | |
| 642 | + | |
| 643 | + | |
| 644 | + | |
| 645 | + | |
| 646 | + | |
| 647 | + | |
| 648 | + | |
| 649 | + | |
| 650 | + | |
| 651 | + | |
| 652 | + | |
| 653 | + | |
| 654 | + | |
| 655 | + | |
| 656 | + | |
| 657 | + | |
| 658 | + | |
| 659 | + | |
| 660 | + | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
| 678 | + | |
| 679 | + | |
| 680 | + | |
| 681 | + | |
| 682 | + | |
| 683 | + | |
| 684 | + | |
566 | 685 | | |
567 | 686 | | |
568 | 687 | | |
| |||
857 | 976 | | |
858 | 977 | | |
859 | 978 | | |
| 979 | + | |
| 980 | + | |
| 981 | + | |
| 982 | + | |
| 983 | + | |
| 984 | + | |
| 985 | + | |
| 986 | + | |
| 987 | + | |
| 988 | + | |
| 989 | + | |
| 990 | + | |
| 991 | + | |
| 992 | + | |
| 993 | + | |
| 994 | + | |
| 995 | + | |
| 996 | + | |
| 997 | + | |
| 998 | + | |
| 999 | + | |
| 1000 | + | |
| 1001 | + | |
| 1002 | + | |
| 1003 | + | |
| 1004 | + | |
| 1005 | + | |
| 1006 | + | |
| 1007 | + | |
| 1008 | + | |
| 1009 | + | |
| 1010 | + | |
| 1011 | + | |
| 1012 | + | |
| 1013 | + | |
| 1014 | + | |
| 1015 | + | |
| 1016 | + | |
| 1017 | + | |
| 1018 | + | |
| 1019 | + | |
| 1020 | + | |
| 1021 | + | |
| 1022 | + | |
| 1023 | + | |
| 1024 | + | |
| 1025 | + | |
| 1026 | + | |
| 1027 | + | |
| 1028 | + | |
| 1029 | + | |
| 1030 | + | |
| 1031 | + | |
| 1032 | + | |
| 1033 | + | |
| 1034 | + | |
| 1035 | + | |
| 1036 | + | |
| 1037 | + | |
| 1038 | + | |
| 1039 | + | |
| 1040 | + | |
| 1041 | + | |
| 1042 | + | |
| 1043 | + | |
| 1044 | + | |
| 1045 | + | |
| 1046 | + | |
| 1047 | + | |
| 1048 | + | |
| 1049 | + | |
| 1050 | + | |
| 1051 | + | |
| 1052 | + | |
| 1053 | + | |
| 1054 | + | |
| 1055 | + | |
| 1056 | + | |
| 1057 | + | |
| 1058 | + | |
| 1059 | + | |
| 1060 | + | |
| 1061 | + | |
| 1062 | + | |
| 1063 | + | |
| 1064 | + | |
| 1065 | + | |
| 1066 | + | |
| 1067 | + | |
| 1068 | + | |
| 1069 | + | |
| 1070 | + | |
| 1071 | + | |
| 1072 | + | |
| 1073 | + | |
| 1074 | + | |
| 1075 | + | |
| 1076 | + | |
| 1077 | + | |
| 1078 | + | |
| 1079 | + | |
| 1080 | + | |
| 1081 | + | |
| 1082 | + | |
860 | 1083 | | |
861 | 1084 | | |
862 | 1085 | | |
| |||
0 commit comments