apache / apache/lucene

[ENH]: Support Concurrent Segment-Level Aggregation in `SortedSetDocValuesFacetCounts` via `Executor`

Open
#16,448 0 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

## 1. Motivation

Currently, Lucene's collection phase is easily parallelized using the concurrent search capabilities of `IndexSearcher` combined with `FacetsCollectorManager`. Slices of segments are searched in parallel, and their matching doc IDs are collected into thread-local `FacetsCollector` instances, which are later merged into a single `FacetsCollector` (list of `MatchingDocs`).

However, the **aggregation phase**—where term ordinals are read from `SortedSetDocValues` and their counts are accumulated—remains strictly single-threaded in the standard `SortedSetDocValuesFacetCounts` constructor:
```java
// Sequential segment aggregation in constructor
for (MatchingDocs hits : matchingDocs) {
countOneSegment(ordinalMap, hits.context().reader(), hits.context().ord, hits, null);
}
```
If an index has a large number of segments and query match density is high, executing this loop sequentially on a single thread becomes a significant bottleneck, completely underutilizing multi-core CPU architectures.

While Lucene provides a separate `ConcurrentSortedSetDocValuesFacetCounts` class, it:
1. Mandates a different class instantiating schema and requires a full `ExecutorService`.
2. Forces the use of an `AtomicIntegerArray` spanning the entire global ordinal space, which is memory-heavy and can suffer from false sharing / CPU cache-line bouncing under high contention.
3. Cannot be configured directly on the standard `SortedSetDocValuesFacetCounts` class.

---

## 2. Proposed Solution

We propose introducing a new constructor overload in `SortedSetDocValuesFacetCounts` that accepts a standard `java.util.concurrent.Executor`:
```java
public SortedSetDocValuesFacetCounts(
SortedSetDocValuesReaderState state, FacetsCollector hits, Executor executor)
```

### Implementation Details:
* **TaskExecutor**: Reuses Lucene's internal `TaskExecutor` to execute segment counting tasks (`countOneSegmentConcurrent`) concurrently.
* **Thread-Local / Task-Local Collection**: Each segment task accumulates counts into its own isolated segment-local structure:
* **Sparse Mode** (if `hits.totalHits() < numSegOrds / 10`): Collects global ordinals directly into a thread-local HPPC `IntIntHashMap`. This avoids allocating massive count arrays on worker threads.
* **Dense Mode**: Collects into a segment-local `int[] segCounts` of size `numSegOrds`.
* **Lock-Free Reduction**: Once all segment tasks complete, the main thread merges the segment-local results into the shared `counts` array. This completely avoids write locks, synchronization, and atomic write contention on worker threads.

---

## 3. Benchmark Results

### 3.1. Synthetic Benchmark
Tested on a multi-segment index (200,000 documents partitioned across 8 segments, using 100 unique facet categories per document):
* **CPU**: 8-core Processor
* **Worker Threads**: 8 threads
* **Query**: `MatchAllDocsQuery`

| Implementation | Latency (ms/op) | Throughput (ops/sec) | QPS Change |
| :--- | :---: | :---: | :---: |
| **1. Sequential Baseline** | 39.572 ms/op | 25.27 ops/sec | Baseline |
| **2. Concurrent (AtomicIntegerArray class)** | 18.583 ms/op | 53.81 ops/sec | **🚀 +112.9%** |
| **3. Concurrent ThreadLocal (This Proposal)** | 20.761 ms/op | 48.17 ops/sec | **🚀 +90.6%** |

### 3.2. Wikimedia Dataset Benchmark (`wikimedium1m`)
We ran standard search queries on a **1,000,000 document** Wikimedia dataset using `luceneutil` on all 4 CPU cores:
* **BrowseDateSSDVFacets** (High Cardinality): 21.27 QPS (Sequential) vs 36.12 QPS (Concurrent) [**+69.8% 🚀**]
* **BrowseRandomLabelSSDVFacets** (High Cardinality): 40.06 QPS (Sequential) vs 63.66 QPS (Concurrent) [**+58.9% 🚀**]
* **BrowseDayOfYearSSDVFacets** (Medium Cardinality): 115.00 QPS (Sequential) vs 131.73 QPS (Concurrent) [**+14.5% 🚀**]
* **BrowseMonthSSDVFacets** (Low Cardinality - 12): 228.80 QPS (Sequential) vs 120.53 QPS (Concurrent) [**-47.3%**]

### Key Observations:
1. **Parallel Speedup**: On healthy segment sizes (like 12.5k documents/segment for 1M doc index), concurrent aggregation delivers **+59% to +70% QPS improvement** on high-cardinality fields.
2. **Cardinality vs. Thread Overhead**: For tiny collections (like `wikimedium10k` with 1,250 docs/segment) or extremely low-cardinality facets (like `Month` with 12 unique buckets), the JIT-compiled sequential aggregation is incredibly fast, and scheduling worker threads introduces reduction overhead that can slow down performance. Concurrency is best suited for realistic index scales and high-cardinality fields.
3. **Memory Efficiency**: Unlike `ConcurrentSortedSetDocValuesFacetCounts` which allocates a static `AtomicIntegerArray` of global cardinality size (which can be millions of entries), our thread-local implementation scales dynamically and keeps memory usage minimal under low hit counts via sparse maps.

---

## 4. Testing & Verification

All existing 305 tests in `:lucene:facet` compiled and passed cleanly. A new benchmark test class `TestSortedSetDocValuesConcurrentBenchmark` was added to verify correctness and assert that counts from all three aggregation paths are 100% identical.

---

## 5. Work in Progress

> [!IMPORTANT]
> **A Pull Request implementing this concurrent aggregation is currently in progress.** We have successfully verified correct behavior and measured significant performance improvements. Please do not duplicate efforts on this feature. We will link the PR here shortly!

CC: @gsmiller, @mikemccand, @rmuir

Contributor guide

Open the contributing guide

Research direction

Start with SortedSetDocValuesFacetCounts and the existing ConcurrentSortedSetDocValuesFacetCounts implementation, then review the proposed TestSortedSetDocValuesConcurrentBenchmark. Verify how segment aggregation and Executor-based task execution should fit the existing facet APIs; done means the new constructor preserves identical counts and the benchmark and facet tests pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.