You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by to...@apache.org on 2020/01/12 06:11:37 UTC

[lucene-solr] 02/10: Support segment merging

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

tomoko pushed a commit to branch jira/lucene-9004-aknn-2
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git

commit f22b4b5e2201f32c7fe69dc108499da227411855
Author: Tomoko Uchida <to...@apache.org>
AuthorDate: Sun Dec 8 16:39:31 2019 +0900

    Support segment merging
---
 .../org/apache/lucene/codecs/KnnGraphReader.java   |   8 +
 .../org/apache/lucene/codecs/KnnGraphWriter.java   | 242 +++++++++++++++++++++
 .../codecs/lucene90/Lucene90KnnGraphReader.java    |   7 +-
 .../codecs/lucene90/Lucene90KnnGraphWriter.java    |  21 +-
 .../apache/lucene/index/DefaultIndexingChain.java  |   4 +-
 .../org/apache/lucene/index/KnnGraphValues.java    |  15 +-
 .../apache/lucene/index/KnnGraphValuesWriter.java  | 167 ++++----------
 .../java/org/apache/lucene/index/MergeState.java   |  11 +
 .../org/apache/lucene/index/SegmentMerger.java     |  19 ++
 .../org/apache/lucene/util/hnsw/HNSWGraph.java     |  37 ++--
 .../apache/lucene/util/hnsw/HNSWGraphBuilder.java  | 111 ----------
 .../apache/lucene/util/hnsw/HNSWGraphReader.java   |   7 +-
 .../apache/lucene/util/hnsw/HNSWGraphWriter.java   | 229 +++++++++++++++++++
 .../java/org/apache/lucene/util/hnsw/Layer.java    |  11 +-
 14 files changed, 615 insertions(+), 274 deletions(-)

diff --git a/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphReader.java b/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphReader.java
index fbf5bfd..58b0904 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphReader.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphReader.java
@@ -47,4 +47,12 @@ public abstract class KnnGraphReader implements Closeable, Accountable {
   /** Returns the {@link KnnGraphValues} for the given {@code field} */
   public abstract KnnGraphValues getGraphValues(String field) throws IOException;
 
+  /**
+   * Returns an instance optimized for merging. This instance may only be
+   * consumed in the thread that called {@link #getMergeInstance()}.
+   * <p>
+   * The default implementation returns {@code this} */
+  public KnnGraphReader getMergeInstance() {
+    return this;
+  }
 }
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphWriter.java
index c0b5638..a8d9834 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/KnnGraphWriter.java
@@ -19,8 +19,18 @@ package org.apache.lucene.codecs;
 
 import java.io.Closeable;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
 
+import org.apache.lucene.index.DocIDMerger;
 import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.KnnGraphValues;
+import org.apache.lucene.index.MergeState;
+import org.apache.lucene.index.VectorValues;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.IntsRefBuilder;
 
 /**
  * Writes vectors and knn-graph to an index.
@@ -36,4 +46,236 @@ public abstract class KnnGraphWriter implements Closeable {
   /** Called once at the end before close */
   public abstract void finish() throws IOException;
 
+  public void merge(MergeState mergeState) throws IOException {
+    for (KnnGraphReader reader : mergeState.knnGraphReaders) {
+      if (reader != null) {
+        reader.checkIntegrity();
+      }
+    }
+
+    for (FieldInfo fieldInfo : mergeState.mergeFieldInfos) {
+      mergeOneField(fieldInfo, mergeState);
+    }
+    finish();
+  }
+
+  private void mergeOneField(FieldInfo fieldInfo, MergeState mergeState) throws IOException {
+    List<VectorValuesSub> vectorSubs = new ArrayList<>();
+    List<KnnGraphValuesSub> graphSubs = new ArrayList<>();
+    int topLevel = 0;
+    final Set<EnterPoint> mappedEnterPoints = new HashSet<>();
+
+    long cost = 0;
+    for (int i = 0; i < mergeState.knnGraphReaders.length; i++) {
+      KnnGraphReader knnGraphReader = mergeState.knnGraphReaders[i];
+      if (knnGraphReader != null) {
+        FieldInfo readerFieldInfo = mergeState.fieldInfos[i].fieldInfo(fieldInfo.name);
+        if (readerFieldInfo != null && readerFieldInfo.getVectorNumDimensions() != 0) {
+          VectorValues vectorValues = knnGraphReader.getVectorValues(readerFieldInfo.name);
+          KnnGraphValues graphValues = knnGraphReader.getGraphValues(readerFieldInfo.name);
+          if (vectorValues != null && graphValues != null && graphValues.getTopLevel() >= 0) {
+            cost += vectorValues.cost();
+            vectorSubs.add(new VectorValuesSub(mergeState.docMaps[i], vectorValues));
+            graphSubs.add(new KnnGraphValuesSub(mergeState.docMaps[i], graphValues));
+            if (graphValues.getTopLevel() > topLevel) {
+              topLevel = graphValues.getTopLevel();
+            }
+            int enterPoint = graphValues.getEnterPoints()[0];
+            mappedEnterPoints.add(new EnterPoint(mergeState.docMaps[i].get(enterPoint), graphValues.getTopLevel()));
+          }
+        }
+      }
+    }
+
+    final DocIDMerger<VectorValuesSub> vectorDocIdMerger = DocIDMerger.of(vectorSubs, mergeState.needsIndexSort);
+    final DocIDMerger<KnnGraphValuesSub> graphDocIdMerger = DocIDMerger.of(graphSubs, mergeState.needsIndexSort);
+    final long finalCost = cost;
+    final int finalTopLevel = topLevel;
+
+    final VectorValues meregdVectorValues = mergedVectorValues(vectorDocIdMerger, finalCost);
+    final KnnGraphValues mergedGraphValues = mergedGraphValues(graphDocIdMerger, finalCost, finalTopLevel, mappedEnterPoints);
+
+    writeField(fieldInfo, new KnnGraphReader() {
+      @Override
+      public void checkIntegrity() throws IOException {
+      }
+
+      @Override
+      public VectorValues getVectorValues(String field) throws IOException {
+        return meregdVectorValues;
+      }
+
+      @Override
+      public KnnGraphValues getGraphValues(String field) throws IOException {
+        return mergedGraphValues;
+      }
+
+      @Override
+      public void close() throws IOException {
+      }
+
+      @Override
+      public long ramBytesUsed() {
+        return 0L;
+      }
+    });
+  }
+
+  private VectorValues mergedVectorValues(DocIDMerger<VectorValuesSub> docIDMerger, long finalCost) {
+    return new VectorValues() {
+      private VectorValuesSub current;
+      private int docID = -1;
+
+      @Override
+      public float[] vectorValue() throws IOException {
+        return current.values.vectorValue();
+      }
+
+      @Override
+      public boolean seek(int target) throws IOException {
+        throw new UnsupportedOperationException();
+      }
+
+      @Override
+      public int docID() {
+        return docID;
+      }
+
+      @Override
+      public int nextDoc() throws IOException {
+        current = docIDMerger.next();
+        if (current == null) {
+          docID = NO_MORE_DOCS;
+        } else {
+          docID = current.mappedDocID;
+        }
+        return docID;
+      }
+
+      @Override
+      public int advance(int target) throws IOException {
+        return 0;
+      }
+
+      @Override
+      public long cost() {
+        return finalCost;
+      }
+    };
+  }
+
+  private KnnGraphValues mergedGraphValues(DocIDMerger<KnnGraphValuesSub> docIDMerger, long finalCost, int finalTopLevel, Set<EnterPoint> enterPoints) throws IOException{
+    return new KnnGraphValues() {
+      private KnnGraphValuesSub current;
+      private int docID = -1;
+
+      @Override
+      public int getTopLevel() {
+        return finalTopLevel;
+      }
+
+      @Override
+      public int[] getEnterPoints() {
+        return enterPoints.stream().mapToInt(ep -> ep.docId).toArray();
+      }
+
+      @Override
+      public int getMaxLevel() {
+        return current.values.getMaxLevel();
+      }
+
+      @Override
+      public IntsRef getFriends(int level) {
+        // re-map friend ids
+        IntsRef friends = current.values.getFriends(level);
+        IntsRefBuilder mappedFriends = new IntsRefBuilder();
+        mappedFriends.copyInts(friends);
+        for (int i = 0; i < friends.length; i++) {
+          mappedFriends.setIntAt(i, current.docMap.get(friends.ints[i]));
+        }
+        // make links to other graphs
+        if (enterPoints.stream().anyMatch(ep -> ep.docId == docID)) {
+          enterPoints.stream().filter(ep -> ep.docId != docID && ep.topLevel >= level).forEach(ep -> {
+            mappedFriends.append(ep.docId);
+          });
+        }
+        return mappedFriends.toIntsRef();
+      }
+
+      @Override
+      public boolean advanceExact(int target) throws IOException {
+        throw new UnsupportedOperationException();
+      }
+
+      @Override
+      public int docID() {
+        return docID;
+      }
+
+      @Override
+      public int nextDoc() throws IOException {
+        current = docIDMerger.next();
+        if (current == null) {
+          docID = NO_MORE_DOCS;
+        } else {
+          docID = current.mappedDocID;
+        }
+        return docID;
+      }
+
+      @Override
+      public int advance(int target) throws IOException {
+        throw new UnsupportedOperationException();
+      }
+
+      @Override
+      public long cost() {
+        return finalCost;
+      }
+    };
+  }
+
+  private static class VectorValuesSub extends DocIDMerger.Sub {
+
+    private final VectorValues values;
+
+    VectorValuesSub(MergeState.DocMap docMap, VectorValues values) {
+      super(docMap);
+      this.values = values;
+      assert values.docID() == -1;
+    }
+
+
+    @Override
+    public int nextDoc() throws IOException {
+      return values.nextDoc();
+    }
+  }
+
+  private class KnnGraphValuesSub extends DocIDMerger.Sub {
+
+    private final KnnGraphValues values;
+    private final MergeState.DocMap docMap;
+
+    KnnGraphValuesSub(MergeState.DocMap docMap, KnnGraphValues values) {
+      super(docMap);
+      this.docMap = docMap;
+      this.values = values;
+      assert values.docID() == -1;
+    }
+
+    @Override
+    public int nextDoc() throws IOException {
+      return values.nextDoc();
+    }
+  }
+
+  private class EnterPoint {
+    final int docId;
+    final int topLevel;
+    EnterPoint(int docId, int topLevel) {
+      this.docId = docId;
+      this.topLevel = topLevel;
+    }
+  }
 }
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphReader.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphReader.java
index e53e260..34a6f3d 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphReader.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphReader.java
@@ -346,6 +346,11 @@ public final class Lucene90KnnGraphReader extends KnnGraphReader {
     }
 
     @Override
+    public int[] getEnterPoints() {
+      return entry.enterPoints;
+    }
+
+    @Override
     public int getMaxLevel() {
       return maxLevel;
     }
@@ -392,7 +397,7 @@ public final class Lucene90KnnGraphReader extends KnnGraphReader {
       }
       dataIn.seek(offset);
       int maxLevel = dataIn.readInt();
-      assert maxLevel > 0;
+      assert maxLevel >= 0;
       this.maxLevel = maxLevel;
       this.friendsRef = readFriends(maxLevel);
       return doc;
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphWriter.java
index 6c16fdf..4c7f4fd 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90KnnGraphWriter.java
@@ -18,10 +18,8 @@
 package org.apache.lucene.codecs.lucene90;
 
 import java.io.IOException;
-import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashMap;
-import java.util.List;
 import java.util.Map;
 
 import org.apache.lucene.codecs.CodecUtil;
@@ -79,7 +77,6 @@ public final class Lucene90KnnGraphWriter extends KnnGraphWriter {
   @Override
   public void writeField(FieldInfo fieldInfo, KnnGraphReader values) throws IOException {
     Map<Integer, Long> docToOffset = new HashMap<>();
-    List<Integer> enterPoints = new ArrayList<>();
     long vectorDataOffset = vectorData.getFilePointer();
     long graphDataOffset = graphData.getFilePointer();
 
@@ -100,13 +97,13 @@ public final class Lucene90KnnGraphWriter extends KnnGraphWriter {
 
       // write knn graph value
       docToOffset.put(docG, graphData.getFilePointer() - graphDataOffset);
-      if (graph.isEnterPoint()) {
-        enterPoints.add(docG);
-      }
-      graphData.writeInt(graph.getMaxLevel());
+
+      int maxLevel = graph.getMaxLevel();
+      assert maxLevel >= 0;
+      graphData.writeInt(maxLevel);
       for (int l = graph.getMaxLevel(); l >= 0; l--) {
         IntsRef friends = graph.getFriends(l);
-        assert friends.length > 0;
+        assert friends.length > 0 : "doc " + docG + " has empty friends list at level=" + l;
         graphData.writeInt(friends.length);
         int stop = friends.offset + friends.length;
         // sort friend ids
@@ -121,24 +118,22 @@ public final class Lucene90KnnGraphWriter extends KnnGraphWriter {
         }
       }
     }
-    assert vectors.nextDoc() == DocIdSetIterator.NO_MORE_DOCS;  // must be exhausted
-    assert graph.nextDoc() == DocIdSetIterator.NO_MORE_DOCS;    // must be exhausted
 
     long vectorDataLength = vectorData.getFilePointer() - vectorDataOffset;
     long graphDataLength = graphData.getFilePointer() - graphDataOffset;
 
-    writeMeta(fieldInfo, vectorDataOffset, vectorDataLength, graphDataOffset, graphDataLength, graph.getTopLevel(), enterPoints, docToOffset);
+    writeMeta(fieldInfo, vectorDataOffset, vectorDataLength, graphDataOffset, graphDataLength, graph.getTopLevel(), graph.getEnterPoints(), docToOffset);
   }
 
   private void writeMeta(FieldInfo field, long vectorDataOffset, long vectorDataLength, long graphDataOffset, long graphDataLength,
-                         int topLevel, List<Integer> eps, Map<Integer, Long> docToOffset) throws IOException {
+                         int topLevel, int[] eps, Map<Integer, Long> docToOffset) throws IOException {
     meta.writeInt(field.number);
     meta.writeVLong(vectorDataOffset);
     meta.writeVLong(vectorDataLength);
     meta.writeVLong(graphDataOffset);
     meta.writeVLong(graphDataLength);
     meta.writeInt(topLevel);
-    meta.writeInt(eps.size());
+    meta.writeInt(eps.length);
     for (Integer ep : eps) {
       meta.writeVInt(ep);
     }
diff --git a/lucene/core/src/java/org/apache/lucene/index/DefaultIndexingChain.java b/lucene/core/src/java/org/apache/lucene/index/DefaultIndexingChain.java
index 3ce1246..4d1de5d 100644
--- a/lucene/core/src/java/org/apache/lucene/index/DefaultIndexingChain.java
+++ b/lucene/core/src/java/org/apache/lucene/index/DefaultIndexingChain.java
@@ -692,7 +692,7 @@ final class DefaultIndexingChain extends DocConsumer {
     }
   }
 
-  /** Called from processDocument to index one field's doc value */
+  /** Called from processDocument to index one field's vector value */
   private void indexVector(PerField fp, IndexableField field) throws IOException {
     int numDimensions = field.fieldType().vectorNumDimensions();
     VectorValues.DistanceFunction distFunc = field.fieldType().vectorDistFunc();
@@ -705,7 +705,7 @@ final class DefaultIndexingChain extends DocConsumer {
     fp.fieldInfo.setVectorDimensionsAndDistanceFunction(numDimensions, distFunc);
 
     if (fp.knnGraphValuesWriter == null) {
-      fp.knnGraphValuesWriter = new KnnGraphValuesWriter(docWriter, fp.fieldInfo);
+      fp.knnGraphValuesWriter = new KnnGraphValuesWriter(fp.fieldInfo, docWriter.bytesUsed);
     }
     fp.knnGraphValuesWriter.addValue(docState.docID, field.binaryValue());
   }
diff --git a/lucene/core/src/java/org/apache/lucene/index/KnnGraphValues.java b/lucene/core/src/java/org/apache/lucene/index/KnnGraphValues.java
index f4d4659..55c41ce 100644
--- a/lucene/core/src/java/org/apache/lucene/index/KnnGraphValues.java
+++ b/lucene/core/src/java/org/apache/lucene/index/KnnGraphValues.java
@@ -37,14 +37,10 @@ public abstract class KnnGraphValues extends DocIdSetIterator {
   public abstract int getTopLevel();
 
   /**
-   * Returns true if the current document ID is the enter point of the graph;
-   * this means {@link #getMaxLevel()} is equal to {@link #getTopLevel()}.
-   * It is illegal to call this method after {@link #advanceExact(int)}
-   * returned {@code false}.
+   * Returns the enter points of the graph.
+   * @return enter points
    */
-  public boolean isEnterPoint() {
-    return getMaxLevel() == getTopLevel();
-  }
+  public abstract int[] getEnterPoints();
 
   /**
    * Returns the max level (height) for the current document ID.
@@ -79,6 +75,11 @@ public abstract class KnnGraphValues extends DocIdSetIterator {
     }
 
     @Override
+    public int[] getEnterPoints() {
+      return new int[0];
+    }
+
+    @Override
     public int getMaxLevel() {
       return -1;
     }
diff --git a/lucene/core/src/java/org/apache/lucene/index/KnnGraphValuesWriter.java b/lucene/core/src/java/org/apache/lucene/index/KnnGraphValuesWriter.java
index 0b657dc..0a6f491 100644
--- a/lucene/core/src/java/org/apache/lucene/index/KnnGraphValuesWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/index/KnnGraphValuesWriter.java
@@ -18,24 +18,17 @@
 package org.apache.lucene.index;
 
 import java.io.IOException;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
 
 import org.apache.lucene.codecs.KnnGraphReader;
 import org.apache.lucene.codecs.KnnGraphWriter;
 import org.apache.lucene.search.DocIdSetIterator;
-import org.apache.lucene.store.ByteBuffersDataInput;
-import org.apache.lucene.store.ByteBuffersDataOutput;
-import org.apache.lucene.store.DataInput;
 import org.apache.lucene.util.Accountable;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.Counter;
 import org.apache.lucene.util.IntsRef;
-import org.apache.lucene.util.IntsRefBuilder;
 import org.apache.lucene.util.RamUsageEstimator;
 import org.apache.lucene.util.hnsw.HNSWGraph;
-import org.apache.lucene.util.hnsw.HNSWGraphBuilder;
+import org.apache.lucene.util.hnsw.HNSWGraphWriter;
 
 /** Buffers up pending vector value(s) and knn graph per doc, then flushes when segment flushes. */
 public class KnnGraphValuesWriter implements Accountable {
@@ -44,31 +37,26 @@ public class KnnGraphValuesWriter implements Accountable {
   private final Counter iwBytesUsed;
   private final DocsWithFieldSet docsWithFieldVec;
   private final DocsWithFieldSet docsWithFieldGrp;
-  private final IntsRefBuilder docsRef;
-  private final List<float[]> buffer;
-  private final ByteBuffersDataOutput bufferOut;
-  private final int numDimensions;
-  private final VectorValues.DistanceFunction distFunc;
-  private final HNSWGraphBuilder hnswBuilder;
-
-  private int addedDocs = 0;
+  private final HNSWGraphWriter hnswGraphWriter;
+
   private int lastDocID = -1;
 
   private long bytesUsed = 0L;
 
-  public KnnGraphValuesWriter(DocumentsWriterPerThread docWriter, FieldInfo fieldInfo) {
+  public KnnGraphValuesWriter(FieldInfo fieldInfo) {
+    this(fieldInfo, null);
+  }
+
+  public KnnGraphValuesWriter(FieldInfo fieldInfo, Counter iwBytesUsed) {
     this.fieldInfo = fieldInfo;
-    this.iwBytesUsed = docWriter.bytesUsed;
+    this.iwBytesUsed = iwBytesUsed;
     this.docsWithFieldVec = new DocsWithFieldSet();
     this.docsWithFieldGrp = new DocsWithFieldSet();
-    this.docsRef = new IntsRefBuilder();
-    this.buffer = new ArrayList<>();
-    this.bufferOut = new ByteBuffersDataOutput();
-    this.numDimensions = fieldInfo.getVectorNumDimensions();
-    this.distFunc = fieldInfo.getVectorDistFunc();
-    this.hnswBuilder = new HNSWGraphBuilder(distFunc);
-    this.bytesUsed = docsWithFieldGrp.ramBytesUsed() + docsWithFieldGrp.ramBytesUsed() + RamUsageEstimator.shallowSizeOf(hnswBuilder);
-    iwBytesUsed.addAndGet(bytesUsed);
+    this.hnswGraphWriter = new HNSWGraphWriter(fieldInfo.getVectorNumDimensions(), fieldInfo.getVectorDistFunc());
+    this.bytesUsed = docsWithFieldGrp.ramBytesUsed() + docsWithFieldGrp.ramBytesUsed() + RamUsageEstimator.shallowSizeOf(hnswGraphWriter);
+    if (iwBytesUsed != null) {
+      iwBytesUsed.addAndGet(bytesUsed);
+    }
   }
 
   public void addValue(int docID, BytesRef binaryValue) throws IOException {
@@ -79,23 +67,9 @@ public class KnnGraphValuesWriter implements Accountable {
       throw new IllegalArgumentException("field=\"" + fieldInfo.name + "\": null value not allowed");
     }
 
-    // write the vector
-    bufferOut.writeBytes(binaryValue.bytes);
+    hnswGraphWriter.insert(docID, binaryValue);
     docsWithFieldVec.add(docID);
-    docsRef.grow(docID + 1);
-    docsRef.setIntAt(docID, addedDocs++);
-    docsRef.setLength(docID + 1);
-    if (docID > lastDocID + 1) {
-      Arrays.fill(docsRef.ints(), lastDocID + 1, docID, -1);
-    }
-
-    // write the graph
-    buffer.add(VectorValues.decode(binaryValue.bytes, numDimensions));
-    if (distFunc != VectorValues.DistanceFunction.NONE) {
-      float[] query = VectorValues.decode(binaryValue.bytes, numDimensions);
-      hnswBuilder.insert(docID, query, getVectorValues());
-      docsWithFieldGrp.add(docID);
-    }
+    docsWithFieldGrp.add(docID);
 
     updateBytesUsed();
 
@@ -103,18 +77,17 @@ public class KnnGraphValuesWriter implements Accountable {
   }
 
   private void updateBytesUsed() {
-    final long newBytesUsed = docsWithFieldVec.ramBytesUsed() + docsWithFieldGrp.ramBytesUsed() +
-        bufferOut.ramBytesUsed() +
-        RamUsageEstimator.sizeOf(docsRef.ints()) +
-        RamUsageEstimator.shallowSizeOf(buffer) +
-        RamUsageEstimator.shallowSizeOf(hnswBuilder);
-    iwBytesUsed.addAndGet(newBytesUsed - bytesUsed);
+    final long newBytesUsed = docsWithFieldVec.ramBytesUsed() + docsWithFieldGrp.ramBytesUsed() + hnswGraphWriter.ramBytesUsed();
+    if (iwBytesUsed != null) {
+      iwBytesUsed.addAndGet(newBytesUsed - bytesUsed);
+    }
     bytesUsed = newBytesUsed;
   }
 
   public void flush(SegmentWriteState state, Sorter.DocMap sortMap, KnnGraphWriter graphWriter) throws IOException {
-    VectorValues vectors = new BufferedVectorValues(numDimensions, bufferOut.toDataInput(), docsWithFieldVec.iterator());
-    KnnGraphValues graph = new BufferedKnnGraphValues(hnswBuilder.build(), docsWithFieldGrp.iterator());
+    hnswGraphWriter.finish();
+    VectorValues vectors = new BufferedVectorValues(docsWithFieldVec.iterator(), hnswGraphWriter.rawVectorsArray());
+    KnnGraphValues graph = new BufferedKnnGraphValues(docsWithFieldGrp.iterator(), hnswGraphWriter.hnswGraph());
 
     final VectorValues vectorValues;
     final KnnGraphValues graphValues;
@@ -154,57 +127,6 @@ public class KnnGraphValuesWriter implements Accountable {
         });
   }
 
-  private VectorValues getVectorValues() {
-    return new VectorValues() {
-      int docID = -1;
-      float[] value = new float[0];
-
-      @Override
-      public float[] vectorValue() throws IOException {
-        return value;
-      }
-
-      @Override
-      public boolean seek(int target) throws IOException {
-        if (target < 0) {
-          throw new IllegalArgumentException("target must be a positive integer: " + target);
-        }
-        if (target >= KnnGraphValuesWriter.this.docsRef.length()) {
-          docID = NO_MORE_DOCS;
-          return false;
-        }
-        docID = target;
-
-        int position = docsRef.ints()[target];
-        if (position < 0) {
-          throw new IllegalArgumentException("no vector value for doc: " + target);
-        }
-        value = KnnGraphValuesWriter.this.buffer.get(position);
-        return true;
-      }
-
-      @Override
-      public int docID() {
-        return docID;
-      }
-
-      @Override
-      public int nextDoc() throws IOException {
-        throw new UnsupportedOperationException();
-      }
-
-      @Override
-      public int advance(int target) throws IOException {
-        throw new UnsupportedOperationException();
-      }
-
-      @Override
-      public long cost() {
-        return KnnGraphValuesWriter.this.docsRef.length();
-      }
-    };
-  }
-
   @Override
   public long ramBytesUsed() {
     return bytesUsed;
@@ -213,33 +135,22 @@ public class KnnGraphValuesWriter implements Accountable {
   private static class BufferedVectorValues extends VectorValues {
 
     final DocIdSetIterator docsWithField;
-    final DataInput bytesIterator;
-    final byte[] value;
-    final int numDims;
-
-    BufferedVectorValues(int numDims, DataInput bytesIterator, DocIdSetIterator docsWithField) {
-      this.numDims = numDims;
-      this.value = new byte[Float.BYTES * numDims];
-      this.bytesIterator = bytesIterator;
+    final float[][] vectorsArray;
+
+    float[] value = new float[0];
+    int bufferPos = 0;
+
+    BufferedVectorValues(DocIdSetIterator docsWithField, float[][] vectorsArray) {
       this.docsWithField = docsWithField;
+      this.vectorsArray = vectorsArray;
     }
 
     @Override
     public float[] vectorValue() throws IOException {
-      throw new UnsupportedOperationException();
-    }
-
-    @Override
-    public byte[] binaryValue() throws IOException {
       return value;
     }
 
     @Override
-    public boolean seek(int target) throws IOException {
-      throw new UnsupportedOperationException();
-    }
-
-    @Override
     public int docID() {
       return docsWithField.docID();
     }
@@ -248,7 +159,7 @@ public class KnnGraphValuesWriter implements Accountable {
     public int nextDoc() throws IOException {
       int docID = docsWithField.nextDoc();
       if (docID != NO_MORE_DOCS) {
-        bytesIterator.readBytes(value, 0, value.length);
+        value = vectorsArray[bufferPos++];
       }
       return docID;
     }
@@ -259,6 +170,11 @@ public class KnnGraphValuesWriter implements Accountable {
     }
 
     @Override
+    public boolean seek(int target) throws IOException {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
     public long cost() {
       return docsWithField.cost();
     }
@@ -266,14 +182,14 @@ public class KnnGraphValuesWriter implements Accountable {
 
   private static class BufferedKnnGraphValues extends KnnGraphValues {
 
-    final HNSWGraph hnswGraph;
     final DocIdSetIterator docsWithField;
+    final HNSWGraph hnswGraph;
 
     private int maxLevel = -1;
 
-    BufferedKnnGraphValues(HNSWGraph hnsw, DocIdSetIterator docsWithField) {
-      this.hnswGraph = hnsw;
+    BufferedKnnGraphValues(DocIdSetIterator docsWithField, HNSWGraph hnsw) {
       this.docsWithField = docsWithField;
+      this.hnswGraph = hnsw;
     }
 
     @Override
@@ -282,6 +198,11 @@ public class KnnGraphValuesWriter implements Accountable {
     }
 
     @Override
+    public int[] getEnterPoints() {
+      return hnswGraph.getEnterPoints().stream().mapToInt(Integer::intValue).toArray();
+    }
+
+    @Override
     public int getMaxLevel() {
       return maxLevel;
     }
diff --git a/lucene/core/src/java/org/apache/lucene/index/MergeState.java b/lucene/core/src/java/org/apache/lucene/index/MergeState.java
index 0e47a5a..30763fc 100644
--- a/lucene/core/src/java/org/apache/lucene/index/MergeState.java
+++ b/lucene/core/src/java/org/apache/lucene/index/MergeState.java
@@ -24,6 +24,7 @@ import java.util.Locale;
 
 import org.apache.lucene.codecs.DocValuesProducer;
 import org.apache.lucene.codecs.FieldsProducer;
+import org.apache.lucene.codecs.KnnGraphReader;
 import org.apache.lucene.codecs.NormsProducer;
 import org.apache.lucene.codecs.PointsReader;
 import org.apache.lucene.codecs.StoredFieldsReader;
@@ -77,6 +78,9 @@ public class MergeState {
   /** Point readers to merge */
   public final PointsReader[] pointsReaders;
 
+  /** Knn graph readers to merge */
+  public final KnnGraphReader[] knnGraphReaders;
+
   /** Max docs per reader */
   public final int[] maxDocs;
 
@@ -103,6 +107,7 @@ public class MergeState {
     termVectorsReaders = new TermVectorsReader[numReaders];
     docValuesProducers = new DocValuesProducer[numReaders];
     pointsReaders = new PointsReader[numReaders];
+    knnGraphReaders = new KnnGraphReader[numReaders];
     fieldInfos = new FieldInfos[numReaders];
     liveDocs = new Bits[numReaders];
 
@@ -139,6 +144,12 @@ public class MergeState {
       if (pointsReaders[i] != null) {
         pointsReaders[i] = pointsReaders[i].getMergeInstance();
       }
+
+      knnGraphReaders[i] = reader.getKnnGraphReader();
+      if (knnGraphReaders[i] != null) {
+        knnGraphReaders[i] = knnGraphReaders[i].getMergeInstance();
+      }
+
       numDocs += reader.numDocs();
     }
 
diff --git a/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java b/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java
index c2677c9..974212a 100644
--- a/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java
+++ b/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java
@@ -24,6 +24,7 @@ import java.util.List;
 import org.apache.lucene.codecs.Codec;
 import org.apache.lucene.codecs.DocValuesConsumer;
 import org.apache.lucene.codecs.FieldsConsumer;
+import org.apache.lucene.codecs.KnnGraphWriter;
 import org.apache.lucene.codecs.NormsConsumer;
 import org.apache.lucene.codecs.NormsProducer;
 import org.apache.lucene.codecs.PointsWriter;
@@ -166,6 +167,17 @@ final class SegmentMerger {
       mergeState.infoStream.message("SM", ((t1-t0)/1000000) + " msec to merge points [" + numMerged + " docs]");
     }
 
+    if (mergeState.infoStream.isEnabled("SM")) {
+      t0 = System.nanoTime();
+    }
+    if (mergeState.mergeFieldInfos.hasVectorValues()) {
+      mergeKnnGraphValues(segmentWriteState);
+    }
+    if (mergeState.infoStream.isEnabled("SM")) {
+      long t1 = System.nanoTime();
+      mergeState.infoStream.message("SM", ((t1-t0)/1000000) + " msec to merge knn graph [" + numMerged + " docs]");
+    }
+
     if (mergeState.mergeFieldInfos.hasVectors()) {
       if (mergeState.infoStream.isEnabled("SM")) {
         t0 = System.nanoTime();
@@ -245,4 +257,11 @@ final class SegmentMerger {
       consumer.merge(mergeState, norms);
     }
   }
+
+  private void mergeKnnGraphValues(SegmentWriteState segmentWriteState) throws IOException {
+    try (KnnGraphWriter writer = codec.knnGraphFormat().fieldsWriter(segmentWriteState)) {
+      writer.merge(mergeState);
+    }
+  }
+
 }
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraph.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraph.java
index a62b862..d2acbef 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraph.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraph.java
@@ -68,13 +68,12 @@ public final class HNSWGraph implements Accountable {
     }
 
     Set<Integer> visited = new HashSet<>(ep.docId());
-    NearestNeighbors candidates = new NearestNeighbors(layer.size() + 1, ep);
-    FurthestNeighbors results = new FurthestNeighbors(layer.size() + 1, ep);
+    NearestNeighbors candidates = new NearestNeighbors(ef, ep);
+    FurthestNeighbors results = new FurthestNeighbors(ef, ep);
 
     if (ep.isDeferred()) {
       ep.prepareQuery(query, vectorValues, distFunc);
     }
-    float upperBound = ep.distance();
 
     while (candidates.size() > 0) {
       Neighbor c = candidates.pop();
@@ -100,18 +99,19 @@ public final class HNSWGraph implements Accountable {
           f.prepareQuery(query, vectorValues, distFunc);
         }
         float dist = distance(query, e.docId(), vectorValues);
-        if ((dist < upperBound && dist < f.distance()) || results.size() < ef) {
-          Neighbor n = new ImmutableNeighbor(e.docId(), dist);
-          candidates.add(n);
-          results.add(n);
-          if (results.size() > ef) {
+        if (dist < f.distance() || results.size() < ef) {
+          if (results.size() == ef) {
             results.pop();
           }
+          Neighbor n = new ImmutableNeighbor(e.docId(), dist);
+          candidates.insertWithOverflow(n);
+          results.add(n);
         }
       }
     }
 
-    return pickNearestNeighbor(results, ef);
+    //System.out.println("level=" + level + ", visited nodes=" + visited.size());
+    return pickNearestNeighbor(results);
   }
 
   private float distance(float[] query, int docId, VectorValues vectorValues) throws IOException {
@@ -122,10 +122,10 @@ public final class HNSWGraph implements Accountable {
     return VectorValues.distance(query, other, distFunc);
   }
 
-  private NearestNeighbors pickNearestNeighbor(FurthestNeighbors queue, int ef) {
-    NearestNeighbors nearests = new NearestNeighbors(ef);
+  private NearestNeighbors pickNearestNeighbor(FurthestNeighbors queue) {
+    NearestNeighbors nearests = new NearestNeighbors(queue.size());
     Set<Integer> addedDocs = new HashSet<>();
-    for (int i = 0; i < ef && queue.size() > 0; i++) {
+    while (queue.size() > 0) {
       Neighbor c = queue.pop();
       if (!addedDocs.contains(c.docId())) {
         nearests.add(c);
@@ -158,7 +158,7 @@ public final class HNSWGraph implements Accountable {
     return layers.isEmpty() || layers.get(0).getNodes().isEmpty();
   }
 
-  public int getEnterPoint() {
+  public int getFirstEnterPoint() {
     if (layers.isEmpty()) {
       throw new IllegalStateException("the graph has no layers!");
     }
@@ -169,6 +169,17 @@ public final class HNSWGraph implements Accountable {
     return nodesAtMaxLevel.get(0);
   }
 
+  public List<Integer> getEnterPoints() {
+    if (layers.isEmpty()) {
+      throw new IllegalStateException("the graph has no layers!");
+    }
+    List<Integer> nodesAtMaxLevel = layers.get(topLevel).getNodes();
+    if (nodesAtMaxLevel.isEmpty()) {
+      throw new IllegalStateException("the max level of this graph is empty!");
+    }
+    return List.copyOf(nodesAtMaxLevel);
+  }
+
   public boolean hasNodes(int level) {
     Layer layer = layers.get(level);
     if (layer == null) {
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
deleted file mode 100644
index 85e17ed..0000000
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphBuilder.java
+++ /dev/null
@@ -1,111 +0,0 @@
-/*
- * 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 java.io.IOException;
-
-import org.apache.lucene.index.VectorValues;
-
-/** Builder of {@link HNSWGraph} */
-public final class HNSWGraphBuilder {
-
-  private static final int MAX_LEVEL_LIMIT = 5;
-  // default random seed for level generation
-  private static final long DEFAULT_RAND_SEED = System.currentTimeMillis();
-  // default max connections per node
-  public static final int DEFAULT_MAX_CONNECTIONS = 6;
-  // default max connections per node at layer zero
-  public static final int DEFAULT_MAX_CONNECTIONS_L0 = DEFAULT_MAX_CONNECTIONS * 2;
-  // default candidate list size
-  public static final int DEFAULT_EF_CONST = 50;
-
-  private final int maxConn;
-  private final int maxConn0;
-  private final int efConst;
-  private final VectorValues.DistanceFunction distFunc;
-  private final HNSWGraph hnsw;
-  private final RandomLevelGenerator levelGenerator;
-
-  /** Construct the builder with default configurations */
-  public HNSWGraphBuilder(VectorValues.DistanceFunction distFunc) {
-    this(DEFAULT_MAX_CONNECTIONS, DEFAULT_MAX_CONNECTIONS_L0, DEFAULT_EF_CONST, DEFAULT_RAND_SEED, distFunc);
-  }
-
-  /** Full constructor */
-  public HNSWGraphBuilder(int maxConn, int maxConn0, int efConst, long seed, VectorValues.DistanceFunction distFunc) {
-    this.maxConn = maxConn;
-    this.maxConn0 = maxConn0;
-    this.efConst = efConst;
-    this.distFunc = distFunc;
-    this.hnsw = new HNSWGraph(distFunc);
-    float ml = (float) (1.0 / Math.log(maxConn));
-    this.levelGenerator = new RandomLevelGenerator(seed, ml, MAX_LEVEL_LIMIT);
-  }
-
-  /** Inserts a doc with vector value to the graph */
-  public void insert(int docId, float[] value, VectorValues vectorValues) throws IOException {
-    if (hnsw.isEmpty()) {
-      // initialize the graph
-      hnsw.ensureLevel(0);
-      hnsw.addNode(0, docId);
-      return;
-    }
-
-    int enterPoint = hnsw.getEnterPoint();
-    if (!vectorValues.seek(enterPoint)) {
-      throw new IllegalStateException("enter point (=" + enterPoint + ") has no vector value");
-    }
-    float distFromEp = VectorValues.distance(value, vectorValues.vectorValue(), distFunc);
-    Neighbor ep = new ImmutableNeighbor(enterPoint, distFromEp);
-
-    int level = levelGenerator.randomLevel();
-
-    // down to the level from the hnsw's top level
-    for (int l = hnsw.topLevel(); l > level; l--) {
-      NearestNeighbors neighbors = hnsw.searchLayer(value, ep, 1, l, vectorValues);
-      ep = neighbors.top();
-    }
-
-    // down to level 0 with placing the doc to each layer
-    hnsw.ensureLevel(level);
-    for (int l = level; l >= 0; l--) {
-      if (!hnsw.hasNodes(l)) {
-        hnsw.addNode(l, docId);
-        continue;
-      }
-
-      NearestNeighbors neighbors = hnsw.searchLayer(value, ep, efConst, l, vectorValues);
-      ep = neighbors.top();
-      int maxConnections = l == 0 ? maxConn0 : maxConn;
-      for (int i = 0; i < maxConnections; i++) {
-        if (neighbors.size() == 0) {
-          break;
-        }
-        Neighbor n = neighbors.pop();
-        hnsw.connectNodes(l, docId, n.docId(), n.distance(), maxConnections);
-      }
-    }
-  }
-
-  /** Returns the built HNSW graph*/
-  public HNSWGraph build() {
-    hnsw.finish();
-    return hnsw;
-  }
-
-}
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphReader.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphReader.java
index 4e6385a..8a9d0dd 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphReader.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphReader.java
@@ -47,7 +47,7 @@ public final class HNSWGraphReader {
 
   public Neighbors searchNeighbors(float[] query, int ef, VectorValues vectorValues) throws IOException {
     HNSWGraph hnsw = get(field, context, false);
-    int enterPoint = hnsw.getEnterPoint();
+    int enterPoint = hnsw.getFirstEnterPoint();
     if (!vectorValues.seek(enterPoint)) {
       throw new IllegalStateException("enterPoint=" + enterPoint + " has no vector value");
     }
@@ -101,6 +101,10 @@ public final class HNSWGraphReader {
     VectorValues.DistanceFunction distFunc = fi.getVectorDistFunc();
 
     KnnGraphValues graphValues = context.reader().getKnnGraphValues(field);
+    return load(field, distFunc, graphValues);
+  }
+
+  public static HNSWGraph load(String field, VectorValues.DistanceFunction distFunc, KnnGraphValues graphValues) throws IOException {
     HNSWGraph hnsw = new HNSWGraph(distFunc);
     for (int doc = graphValues.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = graphValues.nextDoc()) {
       int maxLevel = graphValues.getMaxLevel();
@@ -112,7 +116,6 @@ public final class HNSWGraphReader {
       }
     }
     hnsw.finish();
-
     return hnsw;
   }
 
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphWriter.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphWriter.java
new file mode 100644
index 0000000..70f7b4e
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HNSWGraphWriter.java
@@ -0,0 +1,229 @@
+/*
+ * 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 java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.lucene.index.VectorValues;
+import org.apache.lucene.util.Accountable;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.IntsRefBuilder;
+import org.apache.lucene.util.RamUsageEstimator;
+
+public final class HNSWGraphWriter implements Accountable {
+
+  private static final int MAX_LEVEL_LIMIT = 5;
+  // default random seed for level generation
+  private static final long DEFAULT_RAND_SEED = System.currentTimeMillis();
+  // default max connections per node
+  public static final int DEFAULT_MAX_CONNECTIONS = 6;
+  // default max connections per node at layer zero
+  public static final int DEFAULT_MAX_CONNECTIONS_L0 = DEFAULT_MAX_CONNECTIONS * 2;
+  // default candidate list size
+  public static final int DEFAULT_EF_CONST = 50;
+
+  private final int maxConn;
+  private final int maxConn0;
+  private final int efConst;
+  private final IntsRefBuilder docsRef;
+  private final List<float[]> rawVectors;
+  private final int numDimensions;
+  private final VectorValues.DistanceFunction distFunc;
+  private final HNSWGraph hnsw;
+  private final RandomLevelGenerator levelGenerator;
+
+  private int addedDocs = 0;
+  private int lastDocID = -1;
+
+  /** Construct the builder with default configurations */
+  public HNSWGraphWriter(int numDimensions, VectorValues.DistanceFunction distFunc) {
+    this(DEFAULT_MAX_CONNECTIONS, DEFAULT_MAX_CONNECTIONS_L0, DEFAULT_EF_CONST, DEFAULT_RAND_SEED, numDimensions, distFunc);
+  }
+
+  /** Full constructor */
+  public HNSWGraphWriter(int maxConn, int maxConn0, int efConst, long seed, int numDimensions, VectorValues.DistanceFunction distFunc) {
+    this.maxConn = maxConn;
+    this.maxConn0 = maxConn0;
+    this.efConst = efConst;
+    this.numDimensions = numDimensions;
+    this.distFunc = distFunc;
+    this.docsRef = new IntsRefBuilder();
+    this.rawVectors = new ArrayList<>();
+    this.hnsw = new HNSWGraph(distFunc);
+    float ml = (float) (1.0 / Math.log(maxConn));
+    this.levelGenerator = new RandomLevelGenerator(seed, ml, MAX_LEVEL_LIMIT);
+  }
+
+  /** Inserts a doc with vector value to the graph */
+  public void insert(int docId, BytesRef binaryValue) throws IOException {
+    // add the vector value
+    float[] value = VectorValues.decode(binaryValue.bytes, numDimensions);
+    rawVectors.add(value);
+    docsRef.grow(docId + 1);
+    docsRef.setIntAt(docId, addedDocs++);
+    docsRef.setLength(docId + 1);
+    if (docId > lastDocID + 1) {
+      Arrays.fill(docsRef.ints(), lastDocID + 1, docId, -1);
+    }
+    lastDocID = docId;
+
+    if (distFunc == VectorValues.DistanceFunction.NONE) {
+      return;
+    }
+
+    // add the graph node
+    if (hnsw.isEmpty()) {
+      // initialize the graph
+      hnsw.ensureLevel(0);
+      hnsw.addNode(0, docId);
+      return;
+    }
+
+    VectorValues vectorValues = getVectorValues();
+
+    int enterPoint = hnsw.getFirstEnterPoint();
+    if (!vectorValues.seek(enterPoint)) {
+      throw new IllegalStateException("enter point (=" + enterPoint + ") has no vector value");
+    }
+    float distFromEp = VectorValues.distance(value, vectorValues.vectorValue(), distFunc);
+    Neighbor ep = new ImmutableNeighbor(enterPoint, distFromEp);
+
+    int level = levelGenerator.randomLevel();
+
+    // down to the level from the hnsw's top level
+    for (int l = hnsw.topLevel(); l > level; l--) {
+      NearestNeighbors neighbors = hnsw.searchLayer(value, ep, 1, l, vectorValues);
+      ep = neighbors.top();
+    }
+
+    // down to level 0 with placing the doc to each layer
+    hnsw.ensureLevel(level);
+    for (int l = level; l >= 0; l--) {
+      if (!hnsw.hasNodes(l)) {
+        hnsw.addNode(l, docId);
+        continue;
+      }
+
+      NearestNeighbors neighbors = hnsw.searchLayer(value, ep, efConst, l, vectorValues);
+      ep = neighbors.top();
+      int maxConnections = l == 0 ? maxConn0 : maxConn;
+      for (int i = 0; i < maxConnections; i++) {
+        if (neighbors.size() == 0) {
+          break;
+        }
+        Neighbor n = neighbors.pop();
+        hnsw.connectNodes(l, docId, n.docId(), n.distance(), maxConnections);
+      }
+    }
+  }
+
+  public void finish() {
+    hnsw.finish();
+  }
+
+  public float[][] rawVectorsArray() {
+    return rawVectors.toArray(new float[0][]);
+  }
+
+  /** Returns the built HNSW graph*/
+  public HNSWGraph hnswGraph() {
+    return hnsw;
+  }
+
+  private VectorValues getVectorValues() {
+    return new RandomAccessVectorValues(docsRef.toIntsRef(), rawVectors);
+  }
+
+  private static class RandomAccessVectorValues extends VectorValues {
+
+    final IntsRef docsRef;
+    final List<float[]> buffer;
+
+    int docID = -1;
+    float[] value = new float[0];
+
+    RandomAccessVectorValues(IntsRef docsRef, List<float[]> buffer) {
+      this.docsRef = docsRef;
+      this.buffer = buffer;
+    }
+
+    @Override
+    public float[] vectorValue() throws IOException {
+      return value;
+    }
+
+    @Override
+    public boolean seek(int target) throws IOException {
+      if (target < 0) {
+        throw new IllegalArgumentException("target must be a positive integer: " + target);
+      }
+      if (target >= docsRef.length) {
+        docID = NO_MORE_DOCS;
+        return false;
+      }
+      docID = target;
+
+      int position = docsRef.ints[target];
+      if (position < 0) {
+        throw new IllegalArgumentException("no vector value for doc: " + target);
+      }
+      value = buffer.get(position);
+      return true;
+    }
+
+    @Override
+    public int docID() {
+      return docID;
+    }
+
+    @Override
+    public int nextDoc() throws IOException {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public int advance(int target) throws IOException {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long cost() {
+      return docsRef.length;
+    }
+  }
+
+  @Override
+  public long ramBytesUsed() {
+    // calculating the exact ram usage is time consuming so we make rough estimation here
+    long bytesUsed = RamUsageEstimator.sizeOf(docsRef.ints()) +
+        Float.BYTES * numDimensions * rawVectors.size() +
+        RamUsageEstimator.shallowSizeOfInstance(HNSWGraph.class) +
+        RamUsageEstimator.shallowSizeOfInstance(Layer.class) +
+        Integer.BYTES * 2 * DEFAULT_MAX_CONNECTIONS_L0 * addedDocs;
+    if (hnsw.topLevel() > 0) {
+      for (int l = hnsw.topLevel(); l > 0; l--) {
+        bytesUsed += Integer.BYTES * 2 * DEFAULT_MAX_CONNECTIONS * addedDocs;
+      }
+    }
+    return bytesUsed;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/Layer.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/Layer.java
index aa4b145..18befd3 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/Layer.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/Layer.java
@@ -17,6 +17,7 @@
 
 package org.apache.lucene.util.hnsw;
 
+import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Iterator;
@@ -75,8 +76,14 @@ final class Layer implements Accountable {
     }
     if (friends.size() > maxFriends) {
       TreeSet<Neighbor> newFriends = new TreeSet<>();
-      for (Iterator<Neighbor> itr = friends.iterator(); itr.hasNext() && newFriends.size() < maxFriends; ) {
-        newFriends.add(itr.next());
+      Iterator<Neighbor> itr = friends.iterator();
+      while(itr.hasNext()) {
+        Neighbor n = itr.next();
+        if (newFriends.size() < maxFriends || friendsMap.get(n.docId()).size() == 1) {
+          newFriends.add(n);
+        } else {
+          friendsMap.get(n.docId()).removeIf(n2 -> n2.docId() == node);
+        }
       }
       friendsMap.put(node, newFriends);
     }