[ENH] Opt-In Roaring Bitmap Indexing for High-Cardinality Multi-Valued Aggregations

Aperta
  • Qualcosa non va?
#16,477 1 commento 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
30/100
Tipo di issue
Funzionalità
Chiarezza
Abbastanza chiara
Stato di attività
Tranquilla
Stack tecnologico
java
Ambito
backend, performance, search

Direzione di ricerca

Leggi prima il percorso di faceting esistente di SortedSetDocValues, quindi esamina gli entry point proposti RoaringDocValuesFormat, RoaringDocValuesConsumer, RoaringDocValuesProducer, RoaringBitmapFacetCounts, FacetsConfig e VectorUtil. Il lavoro è completato quando la community ha concordato un design e dispone di un’implementazione completa e testata per l’indicizzazione, l’archiviazione, il routing e l’aggregazione a livello di blocco.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

type:enhancement

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:
   \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.

Lingua principale
Java
Stelle
3.6k
Fork
1.5k
Merge medio
3g 13h
PR unite (30g)
70

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di apache/lucene

Tutte le issue di apache/lucene

Issue simili

Altre issue su Java

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.