[ENH]: Adaptive Facet Engine: Single-Pass Posting-Based Aggregation for Low-Cardinality Fields (+465% QPS)

[rajat315315]

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!