Module org.apache.lucene.core
Package org.apache.lucene.codecs.lucene99

Class Lucene99HnswVectorsFormat

java.lang.Object
org.apache.lucene.codecs.KnnVectorsFormat
org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat
All Implemented Interfaces:
NamedSPILoader.NamedSPI
public final class Lucene99HnswVectorsFormat extends KnnVectorsFormat
Lucene 9.9 vector format, which encodes numeric vector values into an associated graph connecting the documents having values. The graph is used to power HNSW search. The format consists of two files, and requires a FlatVectorsFormat to store the actual vectors:

.vex (vector index)

Stores graphs connecting the documents for each field organized as a list of nodes' neighbours as following:

  • For each level:
    • For each node:
      • [vint] the number of neighbor nodes
      • array[vint] the delta encoded neighbor ordinals
  • After all levels are encoded memory offsets for each node's neighbor nodes encoded by DirectMonotonicWriter are appended to the end of the file.

.vem (vector metadata) file

For each field:

  • [int32] field number
  • [int32] vector similarity function ordinal
  • [vlong] offset to this field's index in the .vex file
  • [vlong] length of this field's index data, in bytes
  • [vint] dimension of this field's vectors
  • [int] the number of documents having values for this field
  • [int8] if equals to -1, dense – all documents have values for a field. If equals to 0, sparse – some documents missing values.
  • DocIds were encoded by IndexedDISI.writeBitSet(DocIdSetIterator, IndexOutput, byte)
  • OrdToDoc was encoded by DirectMonotonicWriter, note that only in sparse case
  • [vint] the maximum number of connections (neighbours) that each node can have
  • [vint] number of levels in the graph
  • Graph nodes by level. For each level
    • [vint] the number of nodes on this level
    • array[vint] for levels greater than 0 list of nodes on this level, stored as the level 0th delta encoded nodes' ordinals.

  • Field Details

    • META_CODEC_NAME

      static final String META_CODEC_NAME
      See Also:

    • VECTOR_INDEX_CODEC_NAME

      static final String VECTOR_INDEX_CODEC_NAME
      See Also:

    • META_EXTENSION

      static final String META_EXTENSION
      See Also:

    • VECTOR_INDEX_EXTENSION

      static final String VECTOR_INDEX_EXTENSION
      See Also:

    • VERSION_START

      public static final int VERSION_START
      See Also:

    • VERSION_CURRENT

      public static final int VERSION_CURRENT
      See Also:

    • MAXIMUM_MAX_CONN

      public static final int MAXIMUM_MAX_CONN
      A maximum configurable maximum max conn.

      NOTE: We eagerly populate `float[MAX_CONN*2]` and `int[MAX_CONN*2]`, so exceptionally large numbers here will use an inordinate amount of heap

      See Also:

    • DEFAULT_MAX_CONN

      public static final int DEFAULT_MAX_CONN
      Default number of maximum connections per node
      See Also:

    • MAXIMUM_BEAM_WIDTH

      public static final int MAXIMUM_BEAM_WIDTH
      The maximum size of the queue to maintain while searching during graph construction This maximum value preserves the ratio of the DEFAULT_BEAM_WIDTH/DEFAULT_MAX_CONN i.e. `6.25 * 16 = 3200`
      See Also:

    • DEFAULT_BEAM_WIDTH

      public static final int DEFAULT_BEAM_WIDTH
      Default number of the size of the queue maintained while searching during a graph construction.
      See Also:

    • DEFAULT_NUM_MERGE_WORKER

      public static final int DEFAULT_NUM_MERGE_WORKER
      Default to use single thread merge
      See Also:

    • DIRECT_MONOTONIC_BLOCK_SHIFT

      static final int DIRECT_MONOTONIC_BLOCK_SHIFT
      See Also:

    • maxConn

      private final int maxConn
      Controls how many of the nearest neighbor candidates are connected to the new node. Defaults to DEFAULT_MAX_CONN. See HnswGraph for more details.

    • beamWidth

      private final int beamWidth
      The number of candidate neighbors to track while searching the graph for each newly inserted node. Defaults to DEFAULT_BEAM_WIDTH. See HnswGraph for details.

    • flatVectorsFormat

      private static final FlatVectorsFormat flatVectorsFormat
      The format for storing, reading, merging vectors on disk

    • numMergeWorkers

      private final int numMergeWorkers

    • mergeExec

      private final TaskExecutor mergeExec

  • Constructor Details

    • Lucene99HnswVectorsFormat

      public Lucene99HnswVectorsFormat()
      Constructs a format using default graph construction parameters

    • Lucene99HnswVectorsFormat

      public Lucene99HnswVectorsFormat(int maxConn, int beamWidth)
      Constructs a format using the given graph construction parameters.
      Parameters:
      maxConn - the maximum number of connections to a node in the HNSW graph
      beamWidth - the size of the queue maintained during graph construction.

    • Lucene99HnswVectorsFormat

      public Lucene99HnswVectorsFormat(int maxConn, int beamWidth, int numMergeWorkers, ExecutorService mergeExec)
      Constructs a format using the given graph construction parameters and scalar quantization.
      Parameters:
      maxConn - the maximum number of connections to a node in the HNSW graph
      beamWidth - the size of the queue maintained during graph construction.
      numMergeWorkers - number of workers (threads) that will be used when doing merge. If larger than 1, a non-null ExecutorService must be passed as mergeExec
      mergeExec - the ExecutorService that will be used by ALL vector writers that are generated by this format to do the merge. If null, the configured MergeScheduler.getIntraMergeExecutor(MergePolicy.OneMerge) is used.

  • Method Details