You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ma...@apache.org on 2025/03/20 18:43:14 UTC

(lucene) branch branch_10x updated: Speedup merging of HNSW graphs (#14331) (#14380)

This is an automated email from the ASF dual-hosted git repository.

mayya pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/branch_10x by this push:
     new aa1e9f34b37 Speedup merging of HNSW graphs (#14331) (#14380)
aa1e9f34b37 is described below

commit aa1e9f34b373882025726a01982b768e4948ccf4
Author: Mayya Sharipova <ma...@elastic.co>
AuthorDate: Thu Mar 20 14:43:07 2025 -0400

    Speedup merging of HNSW graphs (#14331) (#14380)
    
    Backport for #14331
    
    Currently when doing merging of HNSW graphs incrementally,
    we first initialize a graph from the biggest segment, and for other segments,
    we rebuild the graphs completely by going through a segment's vector values
    one by one, searching for it in the new graph to find best neighbours to connect it with.
    
    This PR proposes more efficient merging based on the idea if we know where
    we want to insert a node, we have a good idea of where we want to insert its neighbours.
    Similarly to the current approach, we initialize a new graph from the
    biggest segment. For all other segments, we find a smaller set of nodes
    that "covers" their graph, and we insert that set as usual. For other nodes,
    outside of J sets, we do lighter searches with pre-calculated eps.
    
    This allows substantial speedups in merging (up to 2x in force-merge).
    
    The algorithm is based on the following steps:
    
    1. Get all graphs that don't have deletions and sort them by size (descending).
    2. Copy the largest graph to the new graph (`gL`).
    3. For each remaining small graph (`gS`):
       - Find the nodes that best cover `gS` (join set `j`). These nodes will be inserted into `gL`
         as usual: by searching `gL` to find the best candidates (`w`) to which connect the nodes.
       - For each remaining node in `gS` do "lighter" searches:
         - We provide `eps` to search in `gL`. We form `eps` by the union of the node's
           neighbors in `gS` and the node's neighbors' neighbors in `gL`. We also limit
           `beamWidth` (`efConstruction` ) to `M * 3`.
    
    Algorithm designed by Thomas Veasey
---
 lucene/CHANGES.txt                                 |   2 +
 .../codecs/lucene99/Lucene99HnswVectorsWriter.java |   2 +-
 .../lucene/util/hnsw/ConcurrentHnswMerger.java     | 108 ++++++++++---
 .../apache/lucene/util/hnsw/HnswGraphBuilder.java  |  26 ++-
 .../util/hnsw/IncrementalHnswGraphMerger.java      | 153 +++++++++---------
 .../lucene/util/hnsw/MergingHnswGraphBuilder.java  | 180 +++++++++++++++++++++
 .../apache/lucene/util/hnsw/UpdateGraphsUtils.java | 114 +++++++++++++
 .../apache/lucene/util/hnsw/HnswGraphTestCase.java |  18 ++-
 8 files changed, 504 insertions(+), 99 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 4e207bacc63..6ac98ef5ca3 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -146,6 +146,8 @@ Optimizations
 
 # GITHUB#14361: Introduce new encoding of BPV 21 for DocIdsWriter used in BKD Tree. (Aniketh Jain, Guo Feng)
 
+* GITHUB#14331: Speedup merging of HNSW graphs. (Mayya Sharipova, Tom Veasey)
+
 Bug Fixes
 ---------------------
 
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java
index 07ddb8c98e3..9c43a822b0e 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java
@@ -531,7 +531,7 @@ public final class Lucene99HnswVectorsWriter extends KnnVectorsWriter {
       return new ConcurrentHnswMerger(
           fieldInfo, scorerSupplier, M, beamWidth, mergeExec, numMergeWorkers);
     }
-    if (parallelMergeTaskExecutor != null) {
+    if (parallelMergeTaskExecutor != null && numParallelMergeWorkers > 1) {
       return new ConcurrentHnswMerger(
           fieldInfo,
           scorerSupplier,
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java
index c4e7d159b48..25e7ceb45d5 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java
@@ -16,10 +16,16 @@
  */
 package org.apache.lucene.util.hnsw;
 
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
 import java.io.IOException;
+import java.util.Comparator;
+import org.apache.lucene.codecs.KnnVectorsReader;
 import org.apache.lucene.codecs.hnsw.HnswGraphProvider;
 import org.apache.lucene.index.FieldInfo;
 import org.apache.lucene.index.KnnVectorValues;
+import org.apache.lucene.index.MergeState;
+import org.apache.lucene.internal.hppc.IntIntHashMap;
 import org.apache.lucene.search.TaskExecutor;
 import org.apache.lucene.util.BitSet;
 import org.apache.lucene.util.FixedBitSet;
@@ -48,28 +54,90 @@ public class ConcurrentHnswMerger extends IncrementalHnswGraphMerger {
   @Override
   protected HnswBuilder createBuilder(KnnVectorValues mergedVectorValues, int maxOrd)
       throws IOException {
-    if (initReader == null) {
-      return new HnswConcurrentMergeBuilder(
-          taskExecutor,
-          numWorker,
-          scorerSupplier,
-          M,
-          beamWidth,
-          new OnHeapHnswGraph(M, maxOrd),
-          null);
-    }
+    OnHeapHnswGraph graph;
+    BitSet initializedNodes = null;
 
-    HnswGraph initializerGraph = ((HnswGraphProvider) initReader).getGraph(fieldInfo.name);
-    BitSet initializedNodes = new FixedBitSet(maxOrd);
-    int[] oldToNewOrdinalMap = getNewOrdMapping(mergedVectorValues, initializedNodes);
+    if (graphReaders.size() == 0) {
+      graph = new OnHeapHnswGraph(M, maxOrd);
+    } else {
+      graphReaders.sort(Comparator.comparingInt(GraphReader::graphSize).reversed());
+      GraphReader initGraphReader = graphReaders.get(0);
+      KnnVectorsReader initReader = initGraphReader.reader();
+      MergeState.DocMap initDocMap = initGraphReader.initDocMap();
+      int initGraphSize = initGraphReader.graphSize();
+      HnswGraph initializerGraph = ((HnswGraphProvider) initReader).getGraph(fieldInfo.name);
 
+      if (initializerGraph.size() == 0) {
+        graph = new OnHeapHnswGraph(M, maxOrd);
+      } else {
+        initializedNodes = new FixedBitSet(maxOrd);
+        int[] oldToNewOrdinalMap =
+            getNewOrdMapping(
+                fieldInfo,
+                initReader,
+                initDocMap,
+                initGraphSize,
+                mergedVectorValues,
+                initializedNodes);
+        graph =
+            InitializedHnswGraphBuilder.initGraph(M, initializerGraph, oldToNewOrdinalMap, maxOrd);
+      }
+    }
     return new HnswConcurrentMergeBuilder(
-        taskExecutor,
-        numWorker,
-        scorerSupplier,
-        M,
-        beamWidth,
-        InitializedHnswGraphBuilder.initGraph(M, initializerGraph, oldToNewOrdinalMap, maxOrd),
-        initializedNodes);
+        taskExecutor, numWorker, scorerSupplier, M, beamWidth, graph, initializedNodes);
+  }
+
+  /**
+   * Creates a new mapping from old ordinals to new ordinals and returns the total number of vectors
+   * in the newly merged segment.
+   *
+   * @param mergedVectorValues vector values in the merged segment
+   * @param initializedNodes track what nodes have been initialized
+   * @return the mapping from old ordinals to new ordinals
+   * @throws IOException If an error occurs while reading from the merge state
+   */
+  private static int[] getNewOrdMapping(
+      FieldInfo fieldInfo,
+      KnnVectorsReader initReader,
+      MergeState.DocMap initDocMap,
+      int initGraphSize,
+      KnnVectorValues mergedVectorValues,
+      BitSet initializedNodes)
+      throws IOException {
+    KnnVectorValues.DocIndexIterator initializerIterator = null;
+
+    switch (fieldInfo.getVectorEncoding()) {
+      case BYTE -> initializerIterator = initReader.getByteVectorValues(fieldInfo.name).iterator();
+      case FLOAT32 ->
+          initializerIterator = initReader.getFloatVectorValues(fieldInfo.name).iterator();
+    }
+
+    IntIntHashMap newIdToOldOrdinal = new IntIntHashMap(initGraphSize);
+    int maxNewDocID = -1;
+    for (int docId = initializerIterator.nextDoc();
+        docId != NO_MORE_DOCS;
+        docId = initializerIterator.nextDoc()) {
+      int newId = initDocMap.get(docId);
+      maxNewDocID = Math.max(newId, maxNewDocID);
+      assert newIdToOldOrdinal.containsKey(newId) == false;
+      newIdToOldOrdinal.put(newId, initializerIterator.index());
+    }
+
+    if (maxNewDocID == -1) {
+      return new int[0];
+    }
+    final int[] oldToNewOrdinalMap = new int[initGraphSize];
+    KnnVectorValues.DocIndexIterator mergedVectorIterator = mergedVectorValues.iterator();
+    for (int newDocId = mergedVectorIterator.nextDoc();
+        newDocId <= maxNewDocID;
+        newDocId = mergedVectorIterator.nextDoc()) {
+      int oldOrd = newIdToOldOrdinal.getOrDefault(newDocId, -1);
+      if (oldOrd != -1) {
+        int newOrd = mergedVectorIterator.index();
+        initializedNodes.set(newOrd);
+        oldToNewOrdinalMap[oldOrd] = newOrd;
+      }
+    }
+    return oldToNewOrdinalMap;
   }
 }
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
index 2acdb7715ec..81e16e16d27 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
@@ -28,6 +28,7 @@ import java.util.Objects;
 import java.util.SplittableRandom;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.locks.Lock;
+import org.apache.lucene.internal.hppc.IntHashSet;
 import org.apache.lucene.search.KnnCollector;
 import org.apache.lucene.search.TopDocs;
 import org.apache.lucene.search.knn.KnnSearchStrategy;
@@ -68,12 +69,13 @@ public class HnswGraphBuilder implements HnswBuilder {
   private final GraphBuilderKnnCollector entryCandidates; // for upper levels of graph search
   private final GraphBuilderKnnCollector
       beamCandidates; // for levels of graph where we add the node
+  private final GraphBuilderKnnCollector beamCandidates0;
 
   protected final OnHeapHnswGraph hnsw;
   protected final HnswLock hnswLock;
 
-  private InfoStream infoStream = InfoStream.getDefault();
-  private boolean frozen;
+  protected InfoStream infoStream = InfoStream.getDefault();
+  protected boolean frozen;
 
   public static HnswGraphBuilder create(
       RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed)
@@ -160,6 +162,7 @@ public class HnswGraphBuilder implements HnswBuilder {
     this.graphSearcher = graphSearcher;
     entryCandidates = new GraphBuilderKnnCollector(1);
     beamCandidates = new GraphBuilderKnnCollector(beamWidth);
+    beamCandidates0 = new GraphBuilderKnnCollector(Math.min(beamWidth / 2, M * 3));
   }
 
   @Override
@@ -216,6 +219,11 @@ public class HnswGraphBuilder implements HnswBuilder {
   }
 
   public void addGraphNode(int node, UpdateableRandomVectorScorer scorer) throws IOException {
+    addGraphNodeInternal(node, scorer, null);
+  }
+
+  private void addGraphNodeInternal(int node, UpdateableRandomVectorScorer scorer, IntHashSet eps0)
+      throws IOException {
     if (frozen) {
       throw new IllegalStateException("Graph builder is already frozen");
     }
@@ -255,9 +263,13 @@ public class HnswGraphBuilder implements HnswBuilder {
       for (int i = scratchPerLevel.length - 1; i >= 0; i--) {
         int level = i + lowestUnsetLevel;
         candidates.clear();
+        if (level == 0 && eps0 != null && eps0.size() > 0) {
+          eps = eps0.toArray();
+          candidates = beamCandidates0;
+        }
         graphSearcher.searchLevel(candidates, scorer, level, eps, hnsw, null);
         eps = candidates.popUntilNearestKNodes();
-        scratchPerLevel[i] = new NeighborArray(Math.max(beamCandidates.k(), M + 1), false);
+        scratchPerLevel[i] = new NeighborArray(Math.max(candidates.k(), M + 1), false);
         popToScratch(candidates, scratchPerLevel[i]);
       }
 
@@ -310,7 +322,13 @@ public class HnswGraphBuilder implements HnswBuilder {
     */
     UpdateableRandomVectorScorer scorer = scorerSupplier.scorer();
     scorer.setScoringOrdinal(node);
-    addGraphNode(node, scorer);
+    addGraphNodeInternal(node, scorer, null);
+  }
+
+  public void addGraphNodeWithEps(int node, IntHashSet eps0) throws IOException {
+    UpdateableRandomVectorScorer scorer = scorerSupplier.scorer();
+    scorer.setScoringOrdinal(node);
+    addGraphNodeInternal(node, scorer, eps0);
   }
 
   private long printGraphBuildStatus(int node, long start, long t) {
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
index d64961a02ee..4dc09087076 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
@@ -19,6 +19,9 @@ package org.apache.lucene.util.hnsw;
 import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
 
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
 import org.apache.lucene.codecs.KnnVectorsReader;
 import org.apache.lucene.codecs.hnsw.HnswGraphProvider;
 import org.apache.lucene.codecs.perfield.PerFieldKnnVectorsFormat;
@@ -34,8 +37,7 @@ import org.apache.lucene.util.FixedBitSet;
 import org.apache.lucene.util.InfoStream;
 
 /**
- * This selects the biggest Hnsw graph from the provided merge state and initializes a new
- * HnswGraphBuilder with that graph as a starting point.
+ * This merges multiple graphs in a single thread in incremental fashion.
  *
  * @lucene.experimental
  */
@@ -46,9 +48,12 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
   protected final int M;
   protected final int beamWidth;
 
-  protected KnnVectorsReader initReader;
-  protected MergeState.DocMap initDocMap;
-  protected int initGraphSize;
+  protected List<GraphReader> graphReaders = new ArrayList<>();
+  private int numReaders = 0;
+
+  /** Represents a vector reader that contains graph info. */
+  protected record GraphReader(
+      KnnVectorsReader reader, MergeState.DocMap initDocMap, int graphSize) {}
 
   /**
    * @param fieldInfo FieldInfo for the field being merged
@@ -62,21 +67,24 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
   }
 
   /**
-   * Adds a reader to the graph merger if it meets the following criteria: 1. Does not contain any
-   * deleted docs 2. Is a HnswGraphProvider/PerFieldKnnVectorReader 3. Has the most docs of any
-   * previous reader that met the above criteria
+   * Adds a reader to the graph merger if it meets the following criteria: 1. does not contain any
+   * deleted docs 2. is a HnswGraphProvider/PerFieldKnnVectorReader
    */
   @Override
   public IncrementalHnswGraphMerger addReader(
       KnnVectorsReader reader, MergeState.DocMap docMap, Bits liveDocs) throws IOException {
+    numReaders++;
     KnnVectorsReader currKnnVectorsReader = reader;
     if (reader instanceof PerFieldKnnVectorsFormat.FieldsReader candidateReader) {
       currKnnVectorsReader = candidateReader.getFieldReader(fieldInfo.name);
     }
-
     if (!(currKnnVectorsReader instanceof HnswGraphProvider) || !noDeletes(liveDocs)) {
       return this;
     }
+    HnswGraph graph = ((HnswGraphProvider) currKnnVectorsReader).getGraph(fieldInfo.name);
+    if (graph == null || graph.size() == 0) {
+      return this;
+    }
 
     int candidateVectorCount = 0;
     switch (fieldInfo.getVectorEncoding()) {
@@ -96,17 +104,12 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
         candidateVectorCount = vectorValues.size();
       }
     }
-    if (candidateVectorCount > initGraphSize) {
-      initReader = currKnnVectorsReader;
-      initDocMap = docMap;
-      initGraphSize = candidateVectorCount;
-    }
+    graphReaders.add(new GraphReader(currKnnVectorsReader, docMap, candidateVectorCount));
     return this;
   }
 
   /**
-   * Builds a new HnswGraphBuilder using the biggest graph from the merge state as a starting point.
-   * If no valid readers were added to the merge state, a new graph is created.
+   * Builds a new HnswGraphBuilder
    *
    * @param mergedVectorValues vector values in the merged segment
    * @param maxOrd max num of vectors that will be merged into the graph
@@ -115,81 +118,85 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
    */
   protected HnswBuilder createBuilder(KnnVectorValues mergedVectorValues, int maxOrd)
       throws IOException {
-    if (initReader == null) {
+    if (graphReaders.size() == 0) {
       return HnswGraphBuilder.create(
           scorerSupplier, M, beamWidth, HnswGraphBuilder.randSeed, maxOrd);
     }
-
-    HnswGraph initializerGraph = ((HnswGraphProvider) initReader).getGraph(fieldInfo.name);
-
-    BitSet initializedNodes = new FixedBitSet(maxOrd);
-    int[] oldToNewOrdinalMap = getNewOrdMapping(mergedVectorValues, initializedNodes);
-    return InitializedHnswGraphBuilder.fromGraph(
+    graphReaders.sort(Comparator.comparingInt(GraphReader::graphSize).reversed());
+    final BitSet initializedNodes =
+        graphReaders.size() == numReaders ? null : new FixedBitSet(maxOrd);
+    int[][] ordMaps = getNewOrdMapping(mergedVectorValues, initializedNodes);
+    HnswGraph[] graphs = new HnswGraph[graphReaders.size()];
+    for (int i = 0; i < graphReaders.size(); i++) {
+      HnswGraph graph = ((HnswGraphProvider) graphReaders.get(i).reader).getGraph(fieldInfo.name);
+      if (graph.size() == 0) {
+        throw new IllegalStateException("Graph should not be empty");
+      }
+      graphs[i] = graph;
+    }
+    return MergingHnswGraphBuilder.fromGraphs(
         scorerSupplier,
         M,
         beamWidth,
         HnswGraphBuilder.randSeed,
-        initializerGraph,
-        oldToNewOrdinalMap,
-        initializedNodes,
-        maxOrd);
+        graphs,
+        ordMaps,
+        maxOrd,
+        initializedNodes);
   }
 
-  @Override
-  public OnHeapHnswGraph merge(
-      KnnVectorValues mergedVectorValues, InfoStream infoStream, int maxOrd) throws IOException {
-    HnswBuilder builder = createBuilder(mergedVectorValues, maxOrd);
-    builder.setInfoStream(infoStream);
-    return builder.build(maxOrd);
-  }
-
-  /**
-   * Creates a new mapping from old ordinals to new ordinals and returns the total number of vectors
-   * in the newly merged segment.
-   *
-   * @param mergedVectorValues vector values in the merged segment
-   * @param initializedNodes track what nodes have been initialized
-   * @return the mapping from old ordinals to new ordinals
-   * @throws IOException If an error occurs while reading from the merge state
-   */
-  protected final int[] getNewOrdMapping(
+  protected final int[][] getNewOrdMapping(
       KnnVectorValues mergedVectorValues, BitSet initializedNodes) throws IOException {
-    KnnVectorValues.DocIndexIterator initializerIterator = null;
-
-    switch (fieldInfo.getVectorEncoding()) {
-      case BYTE -> initializerIterator = initReader.getByteVectorValues(fieldInfo.name).iterator();
-      case FLOAT32 ->
-          initializerIterator = initReader.getFloatVectorValues(fieldInfo.name).iterator();
-    }
-
-    IntIntHashMap newIdToOldOrdinal = new IntIntHashMap(initGraphSize);
-    int maxNewDocID = -1;
-    for (int docId = initializerIterator.nextDoc();
-        docId != NO_MORE_DOCS;
-        docId = initializerIterator.nextDoc()) {
-      int newId = initDocMap.get(docId);
-      maxNewDocID = Math.max(newId, maxNewDocID);
-      newIdToOldOrdinal.put(newId, initializerIterator.index());
+    final int numGraphs = graphReaders.size();
+    IntIntHashMap[] newDocIdToOldOrdinals = new IntIntHashMap[numGraphs];
+    final int[][] oldToNewOrdinalMap = new int[numGraphs][];
+    for (int i = 0; i < numGraphs; i++) {
+      KnnVectorValues.DocIndexIterator vectorsIter = null;
+      switch (fieldInfo.getVectorEncoding()) {
+        case BYTE ->
+            vectorsIter = graphReaders.get(i).reader.getByteVectorValues(fieldInfo.name).iterator();
+        case FLOAT32 ->
+            vectorsIter =
+                graphReaders.get(i).reader.getFloatVectorValues(fieldInfo.name).iterator();
+      }
+      newDocIdToOldOrdinals[i] = new IntIntHashMap(graphReaders.get(i).graphSize);
+      MergeState.DocMap docMap = graphReaders.get(i).initDocMap();
+      for (int docId = vectorsIter.nextDoc();
+          docId != NO_MORE_DOCS;
+          docId = vectorsIter.nextDoc()) {
+        int newDocId = docMap.get(docId);
+        newDocIdToOldOrdinals[i].put(newDocId, vectorsIter.index());
+      }
+      oldToNewOrdinalMap[i] = new int[graphReaders.get(i).graphSize];
     }
 
-    if (maxNewDocID == -1) {
-      return new int[0];
-    }
-    final int[] oldToNewOrdinalMap = new int[initGraphSize];
     KnnVectorValues.DocIndexIterator mergedVectorIterator = mergedVectorValues.iterator();
-    for (int newDocId = mergedVectorIterator.nextDoc();
-        newDocId <= maxNewDocID;
-        newDocId = mergedVectorIterator.nextDoc()) {
-      int hashDocIndex = newIdToOldOrdinal.indexOf(newDocId);
-      if (newIdToOldOrdinal.indexExists(hashDocIndex)) {
-        int newOrd = mergedVectorIterator.index();
-        initializedNodes.set(newOrd);
-        oldToNewOrdinalMap[newIdToOldOrdinal.indexGet(hashDocIndex)] = newOrd;
+    for (int docId = mergedVectorIterator.nextDoc();
+        docId < NO_MORE_DOCS;
+        docId = mergedVectorIterator.nextDoc()) {
+      int newOrd = mergedVectorIterator.index();
+      for (int i = 0; i < numGraphs; i++) {
+        int oldOrd = newDocIdToOldOrdinals[i].getOrDefault(docId, -1);
+        if (oldOrd != -1) {
+          oldToNewOrdinalMap[i][oldOrd] = newOrd;
+          if (initializedNodes != null) {
+            initializedNodes.set(newOrd);
+          }
+          break;
+        }
       }
     }
     return oldToNewOrdinalMap;
   }
 
+  @Override
+  public OnHeapHnswGraph merge(
+      KnnVectorValues mergedVectorValues, InfoStream infoStream, int maxOrd) throws IOException {
+    HnswBuilder builder = createBuilder(mergedVectorValues, maxOrd);
+    builder.setInfoStream(infoStream);
+    return builder.build(maxOrd);
+  }
+
   private static boolean noDeletes(Bits liveDocs) {
     if (liveDocs == null) {
       return true;
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java
new file mode 100644
index 00000000000..5c5ff442b16
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java
@@ -0,0 +1,180 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util.hnsw;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.Set;
+import org.apache.lucene.internal.hppc.IntHashSet;
+import org.apache.lucene.util.BitSet;
+
+/**
+ * A graph builder that is used during segments' merging.
+ *
+ * <p>This builder uses a smart algorithm to merge multiple graphs into a single graph. The
+ * algorithm is based on the idea that if we know where we want to insert a node, we have a good
+ * idea of where we want to insert its neighbors.
+ *
+ * <p>The algorithm is based on the following steps:
+ *
+ * <ul>
+ *   <li>Get all graphs that don't have deletions and sort them by size desc.
+ *   <li>Copy the largest graph to the new graph (gL).
+ *   <li>For each remaining small graph (gS):
+ *       <ul>
+ *         <li>Find the nodes that best cover gS: join set `j`. These nodes will be inserted into gL
+ *             as usual: by searching gL to find the best candidates `w` to which connect the nodes.
+ *         <li>For each remaining node in gS:
+ *             <ul>
+ *               <li>We provide eps to search in gL. We form `eps` by the union of the node's
+ *                   neighbors in gS and the node's neighbors' neighbors in gL. We also limit
+ *                   beamWidth (efConstruction to M*3)
+ *             </ul>
+ *       </ul>
+ * </ul>
+ *
+ * <p>We expect the size of join set `j` to be small, around 1/5 to 1/2 of the size of gS. For the
+ * rest of the nodes in gS, we expect savings by performing lighter searches in gL.
+ *
+ * @lucene.experimental
+ */
+public final class MergingHnswGraphBuilder extends HnswGraphBuilder {
+  private final HnswGraph[] graphs;
+  private final int[][] ordMaps;
+  private final BitSet initializedNodes;
+
+  private MergingHnswGraphBuilder(
+      RandomVectorScorerSupplier scorerSupplier,
+      int M,
+      int beamWidth,
+      long seed,
+      OnHeapHnswGraph initializedGraph,
+      HnswGraph[] graphs,
+      int[][] ordMaps,
+      BitSet initializedNodes)
+      throws IOException {
+    super(scorerSupplier, M, beamWidth, seed, initializedGraph);
+    this.graphs = graphs;
+    this.ordMaps = ordMaps;
+    this.initializedNodes = initializedNodes;
+  }
+
+  /**
+   * Create a new HnswGraphBuilder that is initialized with the provided HnswGraph.
+   *
+   * @param scorerSupplier the scorer to use for vectors
+   * @param beamWidth the number of nodes to explore in the search
+   * @param seed the seed for the random number generator
+   * @param graphs the graphs to merge
+   * @param ordMaps the ordinal maps for the graphs
+   * @param totalNumberOfVectors the total number of vectors in the new graph, this should include
+   *     all vectors expected to be added to the graph in the future
+   * @param initializedNodes the nodes will be initialized through the merging
+   * @return a new HnswGraphBuilder that is initialized with the provided HnswGraph
+   * @throws IOException when reading the graph fails
+   */
+  public static MergingHnswGraphBuilder fromGraphs(
+      RandomVectorScorerSupplier scorerSupplier,
+      int M,
+      int beamWidth,
+      long seed,
+      HnswGraph[] graphs,
+      int[][] ordMaps,
+      int totalNumberOfVectors,
+      BitSet initializedNodes)
+      throws IOException {
+    OnHeapHnswGraph graph =
+        InitializedHnswGraphBuilder.initGraph(M, graphs[0], ordMaps[0], totalNumberOfVectors);
+    return new MergingHnswGraphBuilder(
+        scorerSupplier, M, beamWidth, seed, graph, graphs, ordMaps, initializedNodes);
+  }
+
+  @Override
+  public OnHeapHnswGraph build(int maxOrd) throws IOException {
+    if (frozen) {
+      throw new IllegalStateException("This HnswGraphBuilder is frozen and cannot be updated");
+    }
+    if (infoStream.isEnabled(HNSW_COMPONENT)) {
+      String graphSizes = "";
+      for (HnswGraph g : graphs) {
+        graphSizes += g.size() + " ";
+      }
+      infoStream.message(
+          HNSW_COMPONENT,
+          "build graph from merging "
+              + graphs.length
+              + " graphs of "
+              + maxOrd
+              + " vectors, graph sizes:"
+              + graphSizes);
+    }
+    for (int i = 1; i < graphs.length; i++) {
+      updateGraph(graphs[i], ordMaps[i]);
+    }
+
+    // TODO: optimize to iterate only over unset bits in initializedNodes
+    if (initializedNodes != null) {
+      for (int node = 0; node < maxOrd; node++) {
+        if (initializedNodes.get(node) == false) {
+          addGraphNode(node);
+        }
+      }
+    }
+
+    return getCompletedGraph();
+  }
+
+  /** Merge the smaller graph into the current larger graph. */
+  private void updateGraph(HnswGraph gS, int[] ordMapS) throws IOException {
+    int size = gS.size();
+    Set<Integer> j = UpdateGraphsUtils.computeJoinSet(gS);
+
+    // for nodes that in the join set, add them directly to the graph
+    for (int node : j) {
+      addGraphNode(ordMapS[node]);
+    }
+
+    // for each node outside of j set:
+    // form the entry points set for the node
+    // by joining the node's neighbours in gS with
+    // the node's neighbours' neighbours in gL
+    for (int u = 0; u < size; u++) {
+      if (j.contains(u)) {
+        continue;
+      }
+      IntHashSet eps = new IntHashSet();
+      gS.seek(0, u);
+      for (int v = gS.nextNeighbor(); v != NO_MORE_DOCS; v = gS.nextNeighbor()) {
+        // if u's neighbour v is in the join set, or already added to gL (v < u),
+        // then we add v's neighbours from gL to the candidate list
+        if (v < u || j.contains(v)) {
+          int newv = ordMapS[v];
+          eps.add(newv);
+
+          hnsw.seek(0, newv);
+          int friendOrd;
+          while ((friendOrd = hnsw.nextNeighbor()) != NO_MORE_DOCS) {
+            eps.add(friendOrd);
+          }
+        }
+      }
+      addGraphNodeWithEps(ordMapS[u], eps);
+    }
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/UpdateGraphsUtils.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/UpdateGraphsUtils.java
new file mode 100644
index 00000000000..c1217175a43
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/UpdateGraphsUtils.java
@@ -0,0 +1,114 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util.hnsw;
+
+import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+
+import java.io.IOException;
+import java.util.HashSet;
+import java.util.Set;
+import org.apache.lucene.util.LongHeap;
+
+/**
+ * Utility class for updating a big graph with smaller graphs. This is used during merging of
+ * segments containing HNSW graphs.
+ */
+public class UpdateGraphsUtils {
+
+  /**
+   * Find nodes in the graph that best cover the graph. This is reminiscent of an edge cover
+   * problem. Here rather than choosing edges we pick nodes and increment a count at their
+   * neighbours.
+   *
+   * @return a set of nodes that best cover the graph
+   */
+  public static Set<Integer> computeJoinSet(HnswGraph graph) throws IOException {
+    int k; // coverage for the current node
+    int size = graph.size();
+    LongHeap heap = new LongHeap(size);
+    Set<Integer> j = new HashSet<>();
+    boolean[] stale = new boolean[size];
+    short[] counts = new short[size];
+    long gExit = 0L;
+    for (int v = 0; v < size; v++) {
+      graph.seek(0, v);
+      int degree = graph.neighborCount();
+      k = degree < 9 ? 2 : Math.ceilDiv(degree, 4);
+      gExit += k;
+      int gain = k + degree;
+      heap.push(encode(gain, v));
+    }
+
+    long gTot = 0L;
+    while (gTot < gExit) {
+      long el = heap.pop();
+      int gain = decodeValue1(el);
+      int v = decodeValue2(el);
+      graph.seek(0, v);
+      int degree = graph.neighborCount();
+      int[] ns = new int[degree];
+      int i = 0;
+      for (int u = graph.nextNeighbor(); u != NO_MORE_DOCS; u = graph.nextNeighbor()) {
+        ns[i++] = u;
+      }
+      k = degree < 9 ? 2 : Math.ceilDiv(degree, 4);
+      if (stale[v]) { // if stale, recalculate gain
+        int newGain = Math.max(0, k - counts[v]);
+        for (int u : ns) {
+          if (counts[u] < k && j.contains(u) == false) {
+            newGain += 1;
+          }
+        }
+        if (newGain > 0) {
+          heap.push(encode(newGain, v));
+          stale[v] = false;
+        }
+      } else {
+        j.add(v);
+        gTot += gain;
+        boolean markNeighboursStale = counts[v] < k;
+        for (int u : ns) {
+          if (markNeighboursStale) {
+            stale[u] = true;
+          }
+          if (counts[u] < (k - 1)) {
+            // make neighbours of u stale
+            graph.seek(0, u);
+            for (int uu = graph.nextNeighbor(); uu != NO_MORE_DOCS; uu = graph.nextNeighbor()) {
+              stale[uu] = true;
+            }
+          }
+          counts[u] += 1;
+        }
+      }
+    }
+    return j;
+  }
+
+  private static long encode(int value1, int value2) {
+    return (((long) -value1) << 32) | (value2 & 0xFFFFFFFFL);
+  }
+
+  private static int decodeValue1(long encoded) {
+    return (int) -(encoded >> 32);
+  }
+
+  private static int decodeValue2(long encoded) {
+    return (int) (encoded & 0xFFFFFFFFL);
+  }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/util/hnsw/HnswGraphTestCase.java b/lucene/core/src/test/org/apache/lucene/util/hnsw/HnswGraphTestCase.java
index af85fe2cb31..0d000a4407a 100644
--- a/lucene/core/src/test/org/apache/lucene/util/hnsw/HnswGraphTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/util/hnsw/HnswGraphTestCase.java
@@ -183,7 +183,6 @@ abstract class HnswGraphTestCase<T> extends LuceneTestCase {
                         similarityFunction));
               }
             }
-            ;
             doc.add(new StringField("id", Integer.toString(vectors.ordToDoc(ord)), Field.Store.NO));
             iw.addDocument(doc);
           }
@@ -527,6 +526,23 @@ abstract class HnswGraphTestCase<T> extends LuceneTestCase {
     }
   }
 
+  public void testBuildingJoinSet() throws IOException {
+    int dim = random().nextInt(100) + 1;
+    int nDoc = random().nextInt(5000) + 1;
+    int M = 16;
+    int beamWidth = random().nextInt(10) + 5;
+    long seed = random().nextLong();
+    KnnVectorValues vectors = vectorValues(nDoc, dim);
+    RandomVectorScorerSupplier scorerSupplier = buildScorerSupplier(vectors);
+    HnswGraphBuilder builder = HnswGraphBuilder.create(scorerSupplier, M, beamWidth, seed);
+    HnswGraph graph = builder.build(vectors.size());
+
+    Set<Integer> j = UpdateGraphsUtils.computeJoinSet(graph);
+    assertTrue(
+        "Join set size [" + j.size() + "] is not less than graph size [" + graph.size() + "]",
+        j.size() < graph.size());
+  }
+
   public void testHnswGraphBuilderInitializationFromGraph_withOffsetZero() throws IOException {
     int totalSize = atLeast(100);
     int initializerSize = random().nextInt(5, totalSize);