CH-Abhinav opened a new pull request, #16843:
URL: https://github.com/apache/lucene/pull/16843
### Description
Closes #16780.
This PR implements native, zero-dependency **Binary Fuse Filters** (Graf &
Lemire, 2022) in Lucene, alongside `BinaryFuseFilteringPostingsFormat` as a
high-performance, compact alternative to `BloomFilteringPostingsFormat`.
Binary Fuse filters are an optimal fit for Apache Lucene because Lucene
segments are immutable write-once data structures, the static construction
requirement of Binary Fuse filters is naturally satisfied, unlocking
substantial gains in both space efficiency and lookup throughput.
---
### Key Features & Design
1. **Zero External Dependencies:**
- Implemented entirely using Lucene core primitives
(`StringHelper.murmurhash3_x64_128`, `DataOutput`, `DataInput`, and
`ArrayUtil`).
2. **8-bit and 16-bit Filter Implementations:**
- **`BinaryFuse8`:** Uses ~9 bits/key, yielding a theoretical and
empirical FPR of $\approx 0.39\%$ ($2^{-8}$).
- **`BinaryFuse16`:** Uses ~18 bits/key, yielding an ultra-low FPR of
$\approx 0.0015\%$ ($2^{-16}$).
3. **`BinaryFuseFilteringPostingsFormat`:**
- Pluggable `PostingsFormat` wrapping any underlying delegate format
(e.g. default `Lucene104PostingsFormat`).
- Writes filter data to a segment-level `.bff` (Binary Fuse Filter) file.
- Intercepts `seekExact` and `prepareSeekExact` on term dictionaries to
fast-fail terms guaranteed not to exist without triggering disk I/O.
- **Small-Segment Fallback:** Gracefully falls back to Lucene's standard
`FuzzySet` (Bloom filter) for segments with fewer than 1,000 terms where the
linear graph peeling overhead of Binary Fuse is not warranted.
4. **Cache Locality & Speed:**
- While Bloom filter probes touch $k$ (typically 7–16) random cache lines
across memory, Binary Fuse queries check exactly **3 localized slots** in
adjacent array segments, drastically reducing CPU cache misses.
---
### Empirical Benchmark Results
Evaluated against Lucene's existing `FuzzySet` (Bloom with 1% target) across
5 scales (1k, 10k, 100k, 500k, and 1,000,000 keys). In each test, 1,000,000
distinct absent queries were executed to measure empirical false-positive rates
and absent query throughput:
| Keys | Filter | Size | Bits/Key | Build Time | False Positives | Empirical
FPR | Absent QPS | vs Bloom Speedup | FN |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| **1,000** | Lucene Bloom (1% target) | 2.0 KB | 16.46 | 2 ms | 473 /
1,000,000 | 0.0473% | 11.8 M/s | 1.0× | 0 |
| | **BinaryFuse 8-bit** | **1.4 KB** | **11.42** | **0 ms** | 3,907 /
1,000,000 | **0.3907%** | **92.6 M/s** | **7.8× faster** | 0 |
| | **BinaryFuse 16-bit** | 2.8 KB | 22.69 | 2 ms | 18 / 1,000,000 | 0.0018%
| 76.2 M/s | 6.5× faster | 0 |
| **10,000** | Lucene Bloom (1% target) | 16.0 KB | 13.11 | 1 ms | 1,852 /
1,000,000 | 0.1852% | 10.6 M/s | 1.0× | 0 |
| | **BinaryFuse 8-bit** | **12.5 KB** | **10.26** | **1 ms** | 3,925 /
1,000,000 | **0.3925%** | **92.7 M/s** | **8.7× faster** | 0 |
| | **BinaryFuse 16-bit** | 25.0 KB | 20.50 | 8 ms | 22 / 1,000,000 |
0.0022% | 84.1 M/s | 7.9× faster | 0 |
| **100,000** | Lucene Bloom (1% target) | 128.0 KB | 10.49 | 135 ms | 6,376
/ 1,000,000 | 0.6376% | 13.9 M/s | 1.0× | 0 |
| | **BinaryFuse 8-bit** | **116.0 KB** | **9.50** | **14 ms** | 3,940 /
1,000,000 | **0.3940%** | **85.6 M/s** | **6.1× faster** | 0 |
| | **BinaryFuse 16-bit** | 232.0 KB | 19.01 | 14 ms | 19 / 1,000,000 |
0.0019% | 73.2 M/s | 5.3× faster | 0 |
| **500,000** | Lucene Bloom (1% target) | 1.00 MB | 16.78 | 52 ms | 290 /
1,000,000 | 0.0290% | 9.6 M/s | 1.0× | 0 |
| | **BinaryFuse 8-bit** | **560.0 KB** | **9.18** | **55 ms** | 3,854 /
1,000,000 | **0.3854%** | **77.8 M/s** | **8.1× faster** | 0 |
| | **BinaryFuse 16-bit** | 1.09 MB | 18.35 | 63 ms | 12 / 1,000,000 |
0.0012% | 64.3 M/s | 6.7× faster | 0 |
| **1,000,000** | Lucene Bloom (1% target) | 2.00 MB | 16.78 | 267 ms | 307
/ 1,000,000 | 0.0307% | 13.6 M/s | 1.0× | 0 |
| | **BinaryFuse 8-bit** | **1.08 MB** | **9.04** | **123 ms** | 3,977 /
1,000,000 | **0.3977%** | **69.4 M/s** | **5.1× faster** | 0 |
| | **BinaryFuse 16-bit** | 2.16 MB | 18.09 | 168 ms | 16 / 1,000,000 |
0.0016% | 69.3 M/s | 5.1× faster | 0 |
---
### Performance Highlights
- **~46% Footprint Reduction:** At 1M keys, `BinaryFuse8` requires **1.08 MB
(9.04 bits/key)** compared to Bloom's **2.00 MB (16.78 bits/key)**.
- **2× to 10× Faster Filter Construction:** Building 1M keys took **123 ms**
for `BinaryFuse8` vs **267 ms** for Bloom. At 100k keys, construction completed
in **14 ms** vs **135 ms**.
- **5× to 8× Faster Absent Lookups:** Absent query throughput consistently
reached **69M–92M QPS** for Binary Fuse compared to **9M–13M QPS** for Bloom
due to localized 3-cache-line accesses.
---
### Tests & Verification
- Added `TestBinaryFusePostingsFormat`: inherits from
`BasePostingsFormatTestCase` and passes all 30 randomized tests (merging,
seekExact, impacts, multi-segment, terms enum).
- Added `TestBinaryFuseFilter`: verifies round-trip serialization and
empirical false-positive bounds across multiple key scales.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
