apache / apache/lucene

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

Open
#16,426 2 comments 0 reactions 0 assignees View on GitHub
type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.