[ENH]: Adaptive Facet Engine: Single-Pass Posting-Based Aggregation for Low-Cardinality Fields (+465% QPS)
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### 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!
Contributor guide
Research direction
Start with the prototype on branch feature/simd-bitset-optimization and review PostingVsDocValuesFacetBenchmark.java and BitSetVectorizationBenchmark.java to understand the proposed comparison. The work is already underway, so coordinate before making changes; done means the adaptive facet flow and benchmark suite are submitted without duplicating that effort.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend, search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 18/100