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);
}