rajat315315 opened a new issue, #16477:
URL: https://github.com/apache/lucene/issues/16477
### Description
## Background & Case
Currently, Apache Lucene relies on `SortedSetDocValues` for faceting and
aggregating multi-valued keyword fields. When a query executes, the aggregation
engine iterates through the matched `docIDs`, performs random-access lookups
into the DocValues column, retrieves the segment ordinals for each document,
and increments the corresponding bucket counts.
---
## Problem Statement
While `SortedSetDocValues` is the standard for multi-valued fields, it
introduces a severe performance bottleneck for high-cardinality datasets (e.g.,
100,000+ unique ordinals) when query match densities are high:
1. **Cache Misses & Memory Latency:** For a query matching millions of
documents, the engine executes millions of non-contiguous random-access memory
lookups. The time complexity is strictly bounded by $O(\text{MatchingDocs})$.
2. **Multi-Value Vectorization Penalty:** Because documents contain variable
numbers of ordinals per row, vectorizing the retrieval stream using SIMD is
difficult without expensive flattening and intermediate buffering.
---
## Motivation
High-performance analytical engines achieve sub-millisecond grouped
aggregations over high-cardinality data by replacing row-based ordinal lookups
with compressed bitmap intersections. By supporting an opt-in bitmap structure
optimized for high-cardinality multi-valued fields, Lucene can eliminate
$O(\text{MatchingDocs})$ random-access overhead and perform aggregations using
block-level skipping and bitwise arithmetic.
---
## Proposed Solution
Introduce an opt-in index configuration (e.g.,
`index_options="roaring_bitmap"`) for keyword fields to build an array of
Roaring Bitmaps at index time:
1. **Storage Layout:** Transpose the field representation into an array of
Roaring Bitmaps indexed by global ordinal, where each bitset represents
matching `docIDs`. Multi-valued documents set their `docID` bit across multiple
category bitsets.
2. **Block-Level Execution:** Divide the Query Result Bitset ($Q$) into
64k-document blocks during search execution.
3. **Zero-Cycle Skipping:** If a 64k block in $Q$ contains zero matching
documents, skip the intersection entirely across all category bitsets for that
block.
4. **SIMD Acceleration:** For active blocks, utilize Panama Vector API /
HotSpot C2 auto-vectorization to execute SIMD `VPOPCNTDQ` instructions over the
bitsets:
```math
\text{Count}(C_k) += \text{POPCNT}(Q_{\text{block}} \ \& \
C_{k\text{\_block}})
```
---
## Expected Speedup
* **5x – 20x Latency Reduction for High Match Densities:** Direct
hardware-level `AND` + `POPCNT` vector execution eliminates non-contiguous
memory access and L3 CPU cache misses associated with DocValues pointer
traversal.
* **Up to 50x+ Latency Reduction for Sparse/Filtered Queries:** Block-level
skipping bypasses empty 64k document chunks entirely, avoiding bitset
evaluations across large non-matching document ranges.
* **Heap Overhead Reduction:** Off-heap bitset scanning eliminates object
allocation churn during the collection phase.
---
## Implementation Plan & Expected File Changes
### 1. Indexing & Storage Layer
*
**`core/src/java/org/apache/lucene/codecs/roaring/RoaringDocValuesFormat.java`
(NEW)**
* Entry point for the new codec extending `DocValuesFormat`.
* Provides `fieldsConsumer` and `fieldsProducer` methods to read and write
the Roaring Bitmap structures.
*
**`core/src/java/org/apache/lucene/codecs/roaring/RoaringDocValuesConsumer.java`
(NEW)**
* Write-path implementation extending `DocValuesConsumer`.
* Overrides `addSortedSetField()`. Instead of writing ordinals
sequentially per document, buffers `docIDs` into off-heap Roaring Bitmaps (one
per ordinal) and flushes them to `.dvd` (data) and `.dvm` (meta) files.
*
**`core/src/java/org/apache/lucene/codecs/roaring/RoaringDocValuesProducer.java`
(NEW)**
* Read-path implementation extending `DocValuesProducer`.
* Exposes `getBitsets(FieldInfo field)` to access memory-mapped bitset
streams with $O(1)$ offset lookups per ordinal.
### 2. Aggregation & Execution Layer
*
**`facet/src/java/org/apache/lucene/facet/sortedset/RoaringBitmapFacetCounts.java`
(NEW)**
* Specialized facet collector implementing the 64k block-skipping logic
and delegating SIMD vector reductions.
* **`core/src/java/org/apache/lucene/util/VectorUtil.java` (MODIFICATION)**
* Add `bitwiseAndPopcnt(long[] qBlock, long[] catBlock, int length)`
utilizing Panama Vector API (`LongVector`) for hardware `VPOPCNTDQ` operations.
* **`facet/src/java/org/apache/lucene/facet/FacetsConfig.java`
(MODIFICATION)**
* Add auto-routing logic to dispatch queries to `RoaringBitmapFacetCounts`
when the field codec matches `RoaringDocValuesFormat`.
---
## Execution Flow
1. **Index Time:** `RoaringDocValuesConsumer` transposes incoming
multi-valued doc fields into inverted Roaring Bitmaps and writes compressed 64k
chunk streams to disk off-heap.
2. **Query Time:** `IndexSearcher` executes the boolean query and provides
the matching `docIDs` bitset ($Q$) to `FacetsCollector`.
3. **Routing & Collection:** `FacetsConfig` routes execution to
`RoaringBitmapFacetCounts`, which slices $Q$ into 64k blocks.
4. **Hardware Intersections:** Active 64k blocks undergo SIMD `AND` +
`POPCNT` accumulation via `VectorUtil`, skipping inactive chunks automatically.
---
## Dependencies & Technical Considerations
* Leverages **Panama Vector API** (`jdk.incubator.vector`) for SIMD
operations.
* Buffer structures should adhere to standard Roaring Bitmap specification
semantics, maintaining off-heap allocation during indexing to avoid GC pressure.
---
## Request for Review
I would appreciate feedback from the community and stakeholders on the
feasibility of introducing this as a specialized, opt-in `DocValuesFormat` or
`PostingsFormat`. Specifically, I would like to ask @jpountz and @mikemccand
for their thoughts on integration points for block-level skipping within the
current facet collection architecture and the best path forward for off-heap
SIMD integration.
--
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]
