rajat315315 opened a new issue, #16426:
URL: https://github.com/apache/lucene/issues/16426
### Description
## Background & Problem Statement
Currently, facet counting in Lucene (`lucene-facet`) relies primarily on
columnar **DocValues** lookups (`SortedSetDocValues`, `NumericDocValues`) or a
**Taxonomy Index**. While DocValues work well across high-cardinality fields,
they introduce a performance bottleneck for queries matching large result sets.
When a query matches $100,000$ documents in a segment, traditional faceting
performs $100,000$ individual random-access lookups into DocValues
(`docValues.ordValue()`) and array increments (`counts[ord]++`). The time
complexity is $O(\text{MatchingDocs})$, causing memory cache misses and high
latency when match density is large.
---
## Proposed Improvement: Single-Pass Posting-Based Aggregation
For low-cardinality facet fields (e.g. `status`, `category`, `brand`,
`availability` with $K \le 50$ unique categories), we can invert the lookup
pattern:
1. **Posting List Intersections**: Index category values as indexed terms.
Instead of looking up DocValues for every matched document, compute facet
counts via fast SIMD bitset intersections between the query posting list $P_Q$
and category posting lists $P_{C_k}$:
$$\text{Count}(C_k) = |P_Q \cap P_{C_k}|$$
2. **Adaptive Zero-Overhead Router**: Before starting the search pass, use
$O(1)$ index metadata (`TermsEnum.docFreq()`, `weight.cost()`, `maxDoc()`) to
dynamically route execution:
* **Route A (Posting-Based Flow)**: Triggered when category count $K$ is
small and estimated hits exceed the threshold $K \times
\frac{\text{maxDoc}}{64}$.
* **Route B (Legacy DocValues Flow)**: Triggered when match density is
low or field cardinality $K$ is large.
---
## Benchmark Results (JMH)
We implemented JMH micro-benchmarks (`PostingVsDocValuesFacetBenchmark.java`
and `BitSetVectorizationBenchmark.java`) on an index of $1,000,000$ documents
across varying match densities and category counts ($K$).
### 1. Posting-Based vs. DocValues Aggregation (OpenJDK 25)
| Match Density | Matching Docs | Categories ($K$) | Traditional DocValues |
Posting-Based Aggregation | **Throughput Speedup** |
| :---: | :---: | :---: | :---: | :---: | :---: |
| **10%** | **100,000 docs** | **5** | 2,589 ops/sec | **14,643 ops/sec** |
🚀 **+465.4% (5.65x FASTER)** |
| **1%** | **10,000 docs** | **5** | 9,947 ops/sec | **16,378 ops/sec** | 🚀
**+64.6% FASTER** |
| **10%** | **100,000 docs** | **20** | 2,501 ops/sec | **3,747 ops/sec** |
🚀 **+49.8% FASTER** |
| **1%** | **10,000 docs** | **20** | 8,943 ops/sec | 3,762 ops/sec |
DocValues better for high $K$, low matches |
### 2. SIMD BitSet Hardware Acceleration
* HotSpot C2 auto-vectorization compiles tight
`FixedBitSet.intersectionCount` loops directly into native `POPCNT` /
`VPOPCNTDQ` hardware vector instructions, reaching **84,000+ ops/sec** on 1M
doc bitsets.
---
## Implementation Details & Notice
I have already completed the initial design, JMH benchmarks, and prototype
implementation for this feature on branch `feature/simd-bitset-optimization`.
> ⚠️ **Notice**: I am actively working on submitting the PR for this feature
and benchmark suite shortly. Please coordinate here before opening a duplicate
PR or starting parallel work on this component!
--
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]
