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

Abierto
  • ¿Algo no está bien?
#16,477 1 comentario 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
30/100
Tipo de issue
Nueva funcionalidad
Claridad
Bastante claro
Estado de actividad
Tranquilo
Stack tecnológico
java
Área
backend, performance, search

Línea de trabajo

Lee primero el flujo existente de faceting de SortedSetDocValues y, después, inspecciona los puntos de entrada propuestos RoaringDocValuesFormat, RoaringDocValuesConsumer, RoaringDocValuesProducer, RoaringBitmapFacetCounts, FacetsConfig y VectorUtil. Se considera terminado cuando la comunidad haya acordado un diseño y exista una implementación completa y probada para la indexación, el almacenamiento, el enrutamiento y la agregación a nivel de bloque.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
Java
Estrellas
3.6k
Forks
1.5k
Merge medio
3 d 13 h
PR fusionados (30 d)
70

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de apache/lucene

Todos los issues de apache/lucene

Issues similares

Más issues de Java

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.