msokolov commented on code in PR #16627:
URL: https://github.com/apache/lucene/pull/16627#discussion_r3934745043
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java:
##########
@@ -352,105 +411,36 @@ private void repairDisconnectedNodes(
}
}
- /**
- * Fixes disconnected nodes at a specific level by performing graph searches
from their existing
- * neighbors to find additional connections.
- *
- * <p>For each disconnected node:
- *
- * <ol>
- * <li>Use existing neighbors as entry points for graph search
- * <li>Search the level to find candidate neighbors
- * <li>Add diverse neighbors using the HNSW heuristic selection algorithm
- * </ol>
- *
- * <p>If a node has no neighbors at all, it cannot be repaired at this level
and will rely on the
- * rebalancing phase.
- *
- * @param disconnectedNodes list of node ordinals that need additional
neighbors
- * @param level the level at which to repair connections
- * @param scorer vector similarity scorer for distance calculations
- * @throws IOException if an I/O error occurs during search operations
- */
- private void fixDisconnectedNodes(
- List<Integer> disconnectedNodes, int level, UpdateableRandomVectorScorer
scorer)
- throws IOException {
- if (disconnectedNodes.isEmpty()) return;
-
- int beamWidth = beamCandidates.k();
- GraphBuilderKnnCollector candidates = new
GraphBuilderKnnCollector(beamWidth);
- NeighborArray scratchArray = new NeighborArray(beamWidth, false);
-
- for (int node : disconnectedNodes) {
- maybeAbort();
- scorer.setScoringOrdinal(node);
- NeighborArray existingNeighbors = hnsw.getNeighbors(level, node);
-
- // Only repair if node has at least one neighbor to use as entry point
- if (existingNeighbors.size() > 0) {
- // Use all existing neighbors as entry points for search
- int[] entryPoints = new int[existingNeighbors.size()];
- System.arraycopy(existingNeighbors.nodes(), 0, entryPoints, 0,
existingNeighbors.size());
-
- // Search from entry points to find candidate neighbors
- graphSearcher.searchLevel(candidates, scorer, level, entryPoints,
hnsw, null);
- popToScratch(candidates, scratchArray);
-
- // Add diverse neighbors using HNSW heuristic (prunes similar
neighbors)
- addDiverseNeighbors(level, node, scratchArray, scorer, true);
- } else {
- // Node has no nighbors, add connections from scratch
- addConnections(node, level, scorer);
- }
-
- // Clear for next iteration
- scratchArray.clear();
- candidates.clear();
- }
- }
-
/**
* Rebalances the graph hierarchy by promoting nodes from lower levels to
higher levels to
- * maintain the expected exponential decay in level sizes according to the
HNSW probabilistic
- * model.
- *
- * <p>The expected number of nodes at each level follows the formula: <br>
- * {@code maxNodesAtLevel = totalNodes * (1/M)^level}
- *
- * <p>For each level that has fewer nodes than expected, this method
randomly promotes nodes from
- * the level below with probability 1/M until the target count is reached.
- *
- * <p>This rebalancing is necessary during merging graph where deletions may
have disrupted the
- * proper hierarchical distribution, which could degrade semantic matches
quality.
+ * maintain the expected exponential decay in level sizes ({@code totalNodes
* (1/M)^level}) after
+ * deletions disrupted the distribution during a merge-reuse. For each
under-populated level,
+ * nodes from the level below are promoted with probability {@code 1/M}.
*
* @throws IOException if an I/O error occurs during node promotion
*/
- private void rebalanceGraph() throws IOException {
- SplittableRandom random = new SplittableRandom();
+ void rebalanceGraph() throws IOException {
+ SplittableRandom random = new SplittableRandom(seed);
int size = hnsw.size();
double invMaxConn = 1.0 / M;
// Process each level starting from level 1 (level 0 always contains all
nodes)
for (int level = 1; ; level++) {
- // Calculate expected number of nodes at this level
Review Comment:
why did we remove all the comments in this method?
##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswFloatVectorGraph.java:
##########
@@ -188,6 +218,282 @@ public void testAbortCheckInterruptsGraphInitAndRepair()
throws IOException {
}
}
+ /**
Review Comment:
how long do these tests take to run? We try to keep unit tests fast
(definitely less than 1 second each). If they're slower than that we should
reduce iteration counts, nuymber of documents, etc, if possible while still
retaining the value of the test. Otherwise if we need a heavy test we can also
mark it @Nightly to run it less frequently
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -117,6 +155,40 @@ public OnHeapHnswGraph build(int maxOrd) throws
IOException {
return getCompletedGraph();
}
+ /**
+ * Repairs the copied graph's disconnected nodes across the worker pool, one
level at a time from
+ * the top down. The per-level {@link TaskExecutor#invokeAll} is a barrier,
so {@link
Review Comment:
a barrier to what? This comment is confusing to me -- can you expand/explain?
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -117,6 +155,40 @@ public OnHeapHnswGraph build(int maxOrd) throws
IOException {
return getCompletedGraph();
}
+ /**
+ * Repairs the copied graph's disconnected nodes across the worker pool, one
level at a time from
+ * the top down. The per-level {@link TaskExecutor#invokeAll} is a barrier,
so {@link
+ * HnswGraphBuilder#addConnections} always navigates finished upper levels.
+ */
+ private void repairDisconnectedNodes() throws IOException {
+ for (int level = copied.numLevels() - 1; level >= 0; level--) {
+ List<Integer> disconnectedNodes =
copied.disconnectedNodesByLevel().get(level);
+ if (disconnectedNodes == null || disconnectedNodes.isEmpty()) {
+ continue;
+ }
+ int total = disconnectedNodes.size();
+ int taskCount = Math.min(workers.length, 1 + (total - 1) /
REPAIR_BATCH_SIZE);
Review Comment:
please add a comment explaining the logic here -- I think we are trying to
divide the disconnected nodes evenly amopng worker threads?
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -419,8 +419,21 @@ void addDiverseNeighbors(
*/
NeighborArray neighbors = hnsw.getNeighbors(level, node);
int maxConnOnLevel = level == 0 ? M * 2 : M;
- boolean[] mask =
- selectAndLinkDiverse(node, neighbors, candidates, maxConnOnLevel,
scorer, isLinkRepair);
+ boolean[] mask;
+ if (isLinkRepair && hnswLock != null) {
Review Comment:
do we need the `hnswLock` null check? Shouldn't it always be non-null in the
case of link repair?
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -117,6 +155,40 @@ public OnHeapHnswGraph build(int maxOrd) throws
IOException {
return getCompletedGraph();
}
+ /**
+ * Repairs the copied graph's disconnected nodes across the worker pool, one
level at a time from
+ * the top down. The per-level {@link TaskExecutor#invokeAll} is a barrier,
so {@link
Review Comment:
I think it means we guarantee that each level is completed before the next
level is started?
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -419,8 +419,21 @@ void addDiverseNeighbors(
*/
NeighborArray neighbors = hnsw.getNeighbors(level, node);
int maxConnOnLevel = level == 0 ? M * 2 : M;
- boolean[] mask =
- selectAndLinkDiverse(node, neighbors, candidates, maxConnOnLevel,
scorer, isLinkRepair);
+ boolean[] mask;
+ if (isLinkRepair && hnswLock != null) {
Review Comment:
I think the comment about "release before the per-neighbor loop" is
gratuitous - we always want locks to cover the minimum scope
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java:
##########
@@ -229,6 +232,62 @@ private InitializedHnswGraphBuilder(
throws IOException {
super(scorerSupplier, beamWidth, seed, initializedGraph);
this.initializedNodes = initializedNodes;
+ this.seed = seed;
+ }
+
+ /**
+ * Copies the initializer graph without repairing or rebalancing it,
returning the copied graph
+ * plus the state a caller needs to run those phases itself.
+ *
+ * @param scorerSupplier provides vector similarity scoring for graph
operations
+ * @param beamWidth the search beam width for graph construction
+ * @param initializerGraph the source graph to copy structure from
+ * @param newOrdMap maps old ordinals to new ordinals; -1 indicates deleted
documents
+ * @param totalNumberOfVectors the total number of vectors in the merged
graph
+ * @param abortCheck optional check invoked during the copy; may be null
+ * @return the copied graph and its deferred repair/rebalance state
+ * @throws IOException if an I/O error occurs during the copy
+ */
+ static CopiedGraph copyGraph(
+ RandomVectorScorerSupplier scorerSupplier,
+ int beamWidth,
+ HnswGraph initializerGraph,
+ int[] newOrdMap,
+ int totalNumberOfVectors,
+ IORunnable abortCheck)
+ throws IOException {
+ InitializedHnswGraphBuilder builder =
+ new InitializedHnswGraphBuilder(
+ scorerSupplier,
+ beamWidth,
+ randSeed,
+ new OnHeapHnswGraph(initializerGraph.maxConn(),
totalNumberOfVectors),
+ null);
+ if (abortCheck != null) {
+ builder.setAbortCheck(abortCheck);
+ }
+ Map<Integer, List<Integer>> disconnectedNodesByLevel =
Review Comment:
Could we also take this opportunity to replace the boxed Integers with
primitives? Lucene has an IntsRefBuilder designed for this purpose -- also, the
disconnectedNodesByLevel can be an array -- we don't need a map for this
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -90,6 +111,23 @@ public OnHeapHnswGraph build(int maxOrd) throws IOException
{
worker.setMergeStartTimeNs(mergeStartTimeNs);
worker.setCumulativeWorkTimeNs(cumulativeWorkTimeNs);
}
+ if (copied != null && copied.hasDeletes()) {
Review Comment:
Can we make it so `copied.hasDeletes()` is always true, or equivalently,
that `copied` is always null when there are no deletes?
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -42,10 +42,12 @@ public class HnswConcurrentMergeBuilder implements
HnswBuilder {
private static final int DEFAULT_BATCH_SIZE =
2048; // number of vectors the worker handles sequentially at one batch
+ private static final int REPAIR_BATCH_SIZE = 64;
Review Comment:
please add a comment explaining
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java:
##########
@@ -229,6 +232,62 @@ private InitializedHnswGraphBuilder(
throws IOException {
super(scorerSupplier, beamWidth, seed, initializedGraph);
this.initializedNodes = initializedNodes;
+ this.seed = seed;
+ }
+
+ /**
+ * Copies the initializer graph without repairing or rebalancing it,
returning the copied graph
+ * plus the state a caller needs to run those phases itself.
+ *
+ * @param scorerSupplier provides vector similarity scoring for graph
operations
+ * @param beamWidth the search beam width for graph construction
+ * @param initializerGraph the source graph to copy structure from
+ * @param newOrdMap maps old ordinals to new ordinals; -1 indicates deleted
documents
+ * @param totalNumberOfVectors the total number of vectors in the merged
graph
+ * @param abortCheck optional check invoked during the copy; may be null
+ * @return the copied graph and its deferred repair/rebalance state
+ * @throws IOException if an I/O error occurs during the copy
+ */
+ static CopiedGraph copyGraph(
Review Comment:
Let's rename this method and the associated record. We're not so much
copying the graph (the new one is different) as we are removing deletes.
Maybe `pruneGraph` and `PrunedGraph` would be better?
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -117,6 +155,40 @@ public OnHeapHnswGraph build(int maxOrd) throws
IOException {
return getCompletedGraph();
}
+ /**
+ * Repairs the copied graph's disconnected nodes across the worker pool, one
level at a time from
+ * the top down. The per-level {@link TaskExecutor#invokeAll} is a barrier,
so {@link
+ * HnswGraphBuilder#addConnections} always navigates finished upper levels.
+ */
+ private void repairDisconnectedNodes() throws IOException {
+ for (int level = copied.numLevels() - 1; level >= 0; level--) {
+ List<Integer> disconnectedNodes =
copied.disconnectedNodesByLevel().get(level);
+ if (disconnectedNodes == null || disconnectedNodes.isEmpty()) {
Review Comment:
it should be either one or the other -- let's decide how we communicate "no
deleted nodes on level" -- probably null and we shouldn't need this defensive
check for isEmpty
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -665,6 +678,94 @@ private void link(int level, int n0, int n1, float score,
FixedBitSet notFullyCo
}
}
+ /**
+ * Fixes disconnected nodes at a specific level by searching from each
node's existing neighbors
Review Comment:
Let's preserve the javadocs from the original implementation please, unless
we (a human, not the AI, please) read them and think they need correcting.
Honestly I'm finding it really tedious reviewing the AI's javadocs. Could you
please take a pass over them all yourself and see if you think they are OK
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -117,6 +155,40 @@ public OnHeapHnswGraph build(int maxOrd) throws
IOException {
return getCompletedGraph();
}
+ /**
+ * Repairs the copied graph's disconnected nodes across the worker pool, one
level at a time from
+ * the top down. The per-level {@link TaskExecutor#invokeAll} is a barrier,
so {@link
+ * HnswGraphBuilder#addConnections} always navigates finished upper levels.
+ */
+ private void repairDisconnectedNodes() throws IOException {
+ for (int level = copied.numLevels() - 1; level >= 0; level--) {
+ List<Integer> disconnectedNodes =
copied.disconnectedNodesByLevel().get(level);
+ if (disconnectedNodes == null || disconnectedNodes.isEmpty()) {
+ continue;
+ }
+ int total = disconnectedNodes.size();
+ int taskCount = Math.min(workers.length, 1 + (total - 1) /
REPAIR_BATCH_SIZE);
Review Comment:
the integer math is a little confusing
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -665,6 +678,94 @@ private void link(int level, int n0, int n1, float score,
FixedBitSet notFullyCo
}
}
+ /**
+ * Fixes disconnected nodes at a specific level by searching from each
node's existing neighbors
+ * to find additional connections. A node with no neighbors is instead
connected from scratch via
+ * {@link #addConnections}.
+ *
+ * <p>When {@link #hnswLock} is set (concurrent repair) each node's existing
neighbors are
Review Comment:
I think `hnswLock` is always non-null, isn't it? If so we don't need these
two branches below
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -665,6 +678,94 @@ private void link(int level, int n0, int n1, float score,
FixedBitSet notFullyCo
}
}
+ /**
+ * Fixes disconnected nodes at a specific level by searching from each
node's existing neighbors
Review Comment:
sorry if you did that, but I'm finding enough things that sounds like AI to
me ...
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -665,6 +678,94 @@ private void link(int level, int n0, int n1, float score,
FixedBitSet notFullyCo
}
}
+ /**
+ * Fixes disconnected nodes at a specific level by searching from each
node's existing neighbors
+ * to find additional connections. A node with no neighbors is instead
connected from scratch via
+ * {@link #addConnections}.
+ *
+ * <p>When {@link #hnswLock} is set (concurrent repair) each node's existing
neighbors are
Review Comment:
It's only ever called from `HnswConcurrentMergeBuilder`. This method should
be in that class to make this clearer.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
