You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "LantaoJin (via GitHub)" <gi...@apache.org> on 2026/09/29 08:02:06 UTC

[PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

LantaoJin opened a new pull request, #16739:
URL: https://github.com/apache/lucene/pull/16739

   ### Description
   
   `IncrementalHnswGraphMerger#addReader` picks the base graph for a merge with `candidateVectorCount > largestGraphReader.graphSize`. The left side is the candidate's **live** vector count. The right side is the current base's **total** node count, which includes deleted nodes. Before #15003 the two were always equal, because graphs with deletions were never admitted as the base. Since #15003, a graph with up to 40% deletions can become the base, so the comparison mixes units.
   
   As a result, which graph becomes the base depends on the order in which readers are added. Example: segment A has 1000 nodes with 300 deleted (700 live), and segment B has 900 nodes with no deletions. If A is added first, B would need 900 > 1000 to replace it, so A stays the base even though B has more live vectors. If B is added first, B is chosen. The merged graph is still correct either way, so this is a performance issue, not a correctness issue. With a worse base, more nodes must be joined or inserted. This hurts most in `ConcurrentHnswMerger`, which initializes only from the base graph and inserts every other node one by one. `MergingHnswGraphBuilder` joins the other deletion-free graphs, so the effect there is smaller.
   
   The fix adds a `liveVectorCount` component to the `GraphReader` record and compares live against live. `graphSize` stays the total node count, because `getNewOrdMapping` uses it to size the old-to-new ordinal arrays. Ties still keep the earlier reader. `ConcurrentHnswMerger` inherits `addReader`, so it is covered too. `GraphReader` is a `protected` record, so adding a component changes its canonical constructor. Nothing in Lucene constructs it outside `IncrementalHnswGraphMerger`.
   


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on PR #16739:
URL: https://github.com/apache/lucene/pull/16739#issuecomment-6073592250

   cc @kaivalnp @msokolov @mikemccand 


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on code in PR #16739:
URL: https://github.com/apache/lucene/pull/16739#discussion_r4152319996


##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {
+
+  private static final int DIM = 16;
+  private static final String FIELD = "v";
+
+  /**
+   * Segment A has 1000 nodes of which 300 are deleted (700 live, 30% deleted, under the 40%
+   * threshold); segment B has 900 nodes and no deletions. B holds more live vectors, so it must be
+   * chosen as the base regardless of the order in which the readers are added.
+   */
+  public void testBaseGraphChosenByLiveCount() throws IOException {
+    try (Directory dir = newDirectory()) {
+      IndexWriterConfig cfg = new IndexWriterConfig();
+      cfg.setCodec(TestUtil.alwaysKnnVectorsFormat(new Lucene99HnswVectorsFormat(16, 100, 0)));
+      cfg.setMergePolicy(NoMergePolicy.INSTANCE);
+      try (IndexWriter w = new IndexWriter(dir, cfg)) {
+        addSegment(w, "a", 1000);
+        addSegment(w, "b", 900);
+        for (int i = 0; i < 300; i++) {
+          w.deleteDocuments(new Term("id", "a" + i));
+        }
+        w.commit();
+      }
+
+      try (DirectoryReader reader = DirectoryReader.open(dir)) {
+        List<LeafReaderContext> leaves = reader.leaves();
+        assertEquals(2, leaves.size());
+        CodecReader a = segment(leaves, 1000);
+        CodecReader b = segment(leaves, 900);
+        assertEquals(700, a.numDocs());
+        assertEquals(900, b.numDocs());
+        FieldInfo fieldInfo = a.getFieldInfos().fieldInfo(FIELD);
+
+        for (boolean aFirst : new boolean[] {true, false}) {
+          for (boolean concurrent : new boolean[] {false, true}) {
+            IncrementalHnswGraphMerger merger =
+                concurrent
+                    ? new ConcurrentHnswMerger(fieldInfo, null, 16, 100, null, 2)
+                    : new IncrementalHnswGraphMerger(fieldInfo, null, 16, 100);

Review Comment:
   done



-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "Pulkitg64 (via GitHub)" <gi...@apache.org>.
Pulkitg64 commented on code in PR #16739:
URL: https://github.com/apache/lucene/pull/16739#discussion_r4140937891


##########
lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java:
##########
@@ -64,9 +64,14 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
    */
   private final int DELETE_PCT_THRESHOLD = 40;
 
-  /** Represents a vector reader that contains graph info. */
+  /**
+   * Represents a vector reader that contains graph info.
+   *

Review Comment:
   While you are here, let's add params for the other members as well here for completeness?



##########
lucene/CHANGES.txt:
##########
@@ -179,6 +179,11 @@ Improvements
 Optimizations
 ---------------------
 
+* GITHUB#16739: IncrementalHnswGraphMerger now picks the base graph for a merge by comparing live

Review Comment:
   I think this should go into Bug Fixes (But I am not sure so no strong opinion).



##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {
+
+  private static final int DIM = 16;
+  private static final String FIELD = "v";
+
+  /**
+   * Segment A has 1000 nodes of which 300 are deleted (700 live, 30% deleted, under the 40%
+   * threshold); segment B has 900 nodes and no deletions. B holds more live vectors, so it must be
+   * chosen as the base regardless of the order in which the readers are added.
+   */
+  public void testBaseGraphChosenByLiveCount() throws IOException {
+    try (Directory dir = newDirectory()) {
+      IndexWriterConfig cfg = new IndexWriterConfig();
+      cfg.setCodec(TestUtil.alwaysKnnVectorsFormat(new Lucene99HnswVectorsFormat(16, 100, 0)));
+      cfg.setMergePolicy(NoMergePolicy.INSTANCE);
+      try (IndexWriter w = new IndexWriter(dir, cfg)) {
+        addSegment(w, "a", 1000);
+        addSegment(w, "b", 900);
+        for (int i = 0; i < 300; i++) {
+          w.deleteDocuments(new Term("id", "a" + i));
+        }
+        w.commit();
+      }
+
+      try (DirectoryReader reader = DirectoryReader.open(dir)) {
+        List<LeafReaderContext> leaves = reader.leaves();
+        assertEquals(2, leaves.size());
+        CodecReader a = segment(leaves, 1000);
+        CodecReader b = segment(leaves, 900);
+        assertEquals(700, a.numDocs());
+        assertEquals(900, b.numDocs());
+        FieldInfo fieldInfo = a.getFieldInfos().fieldInfo(FIELD);
+
+        for (boolean aFirst : new boolean[] {true, false}) {
+          for (boolean concurrent : new boolean[] {false, true}) {
+            IncrementalHnswGraphMerger merger =
+                concurrent
+                    ? new ConcurrentHnswMerger(fieldInfo, null, 16, 100, null, 2)
+                    : new IncrementalHnswGraphMerger(fieldInfo, null, 16, 100);

Review Comment:
   Should we move the constant from here as well i.e M and beamWidth?



##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {
+
+  private static final int DIM = 16;
+  private static final String FIELD = "v";
+
+  /**
+   * Segment A has 1000 nodes of which 300 are deleted (700 live, 30% deleted, under the 40%
+   * threshold); segment B has 900 nodes and no deletions. B holds more live vectors, so it must be
+   * chosen as the base regardless of the order in which the readers are added.
+   */
+  public void testBaseGraphChosenByLiveCount() throws IOException {
+    try (Directory dir = newDirectory()) {
+      IndexWriterConfig cfg = new IndexWriterConfig();
+      cfg.setCodec(TestUtil.alwaysKnnVectorsFormat(new Lucene99HnswVectorsFormat(16, 100, 0)));
+      cfg.setMergePolicy(NoMergePolicy.INSTANCE);
+      try (IndexWriter w = new IndexWriter(dir, cfg)) {
+        addSegment(w, "a", 1000);

Review Comment:
   Should we make constant variable as we are using same value across multiple places?
   
   ```
   private static final int A_DOCS = 1000;
   private static final int B_DOCS = 900;
   private static final String FIELD_NAME = "id";
   ```



##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {

Review Comment:
   Non blocking: Should we make the test more robust which covers more scenario and not just `live(A) < live(B) with total(A) > total(B)`?



##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {
+
+  private static final int DIM = 16;
+  private static final String FIELD = "v";
+
+  /**
+   * Segment A has 1000 nodes of which 300 are deleted (700 live, 30% deleted, under the 40%
+   * threshold); segment B has 900 nodes and no deletions. B holds more live vectors, so it must be
+   * chosen as the base regardless of the order in which the readers are added.
+   */
+  public void testBaseGraphChosenByLiveCount() throws IOException {
+    try (Directory dir = newDirectory()) {
+      IndexWriterConfig cfg = new IndexWriterConfig();
+      cfg.setCodec(TestUtil.alwaysKnnVectorsFormat(new Lucene99HnswVectorsFormat(16, 100, 0)));
+      cfg.setMergePolicy(NoMergePolicy.INSTANCE);
+      try (IndexWriter w = new IndexWriter(dir, cfg)) {
+        addSegment(w, "a", 1000);
+        addSegment(w, "b", 900);
+        for (int i = 0; i < 300; i++) {

Review Comment:
   I think we are trying to keep the delete% under 40% which is set in ```IncrementalHnswGraphMerger.java.DELETE_PCT_THRESHOLD```. What is that threshold changes, this can make the test case buggy as it can fail/succeed for wrong reasons.
   
   We should derive the delete% here based on `IncrementalHnswGraphMerger.java.DELETE_PCT_THRESHOLD` instead of hardcoding.



-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on code in PR #16739:
URL: https://github.com/apache/lucene/pull/16739#discussion_r4152330148


##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {
+
+  private static final int DIM = 16;
+  private static final String FIELD = "v";
+
+  /**
+   * Segment A has 1000 nodes of which 300 are deleted (700 live, 30% deleted, under the 40%
+   * threshold); segment B has 900 nodes and no deletions. B holds more live vectors, so it must be
+   * chosen as the base regardless of the order in which the readers are added.
+   */
+  public void testBaseGraphChosenByLiveCount() throws IOException {
+    try (Directory dir = newDirectory()) {
+      IndexWriterConfig cfg = new IndexWriterConfig();
+      cfg.setCodec(TestUtil.alwaysKnnVectorsFormat(new Lucene99HnswVectorsFormat(16, 100, 0)));
+      cfg.setMergePolicy(NoMergePolicy.INSTANCE);
+      try (IndexWriter w = new IndexWriter(dir, cfg)) {
+        addSegment(w, "a", 1000);
+        addSegment(w, "b", 900);
+        for (int i = 0; i < 300; i++) {

Review Comment:
   Good point. Fixed.



-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on code in PR #16739:
URL: https://github.com/apache/lucene/pull/16739#discussion_r4152313406


##########
lucene/CHANGES.txt:
##########
@@ -179,6 +179,11 @@ Improvements
 Optimizations
 ---------------------
 
+* GITHUB#16739: IncrementalHnswGraphMerger now picks the base graph for a merge by comparing live

Review Comment:
   done



-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "HoustonPutman (via GitHub)" <gi...@apache.org>.
HoustonPutman commented on PR #16739:
URL: https://github.com/apache/lucene/pull/16739#issuecomment-6297491146

   Ok, I'm not an expert at all here, but this does look like a sane, good, and very concise change from a very birds-eye-view. Going through the original PR, and follow-ups, it doesn't look like this was an intentional choice, or at least there was no discussion on using graph size vs using live docs.
   
   However, there is maybe a better algorithm we could choose rather than just choosing the most vectors, such as taking into account deleted percentage to know whether or not we will go over the overall decay percentage that is allowed before doing some reconnection (added here: https://github.com/apache/lucene/pull/16559). But that's a bigger change, and this looks extremely well contained.
   
   @msokolov Do you have any thoughts here? I don't want this to hold up 10.6, and it looks like an easy commit and back port. But if you have concerns, we can easily hold it up for 10.6.1 (or a 10.7, if that ever happens).


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "Pulkitg64 (via GitHub)" <gi...@apache.org>.
Pulkitg64 commented on PR #16739:
URL: https://github.com/apache/lucene/pull/16739#issuecomment-5932977946

   We should try to send this PR in 10.6 release. I don't have permission to add the milestone. 
   Tagging @kaivalnp for the help here since he is release manager for 10.6 branch.


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on PR #16739:
URL: https://github.com/apache/lucene/pull/16739#issuecomment-6094877497

   @mayya-sharipova could you review this PR either?


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on code in PR #16739:
URL: https://github.com/apache/lucene/pull/16739#discussion_r4152323836


##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {

Review Comment:
   Added `testBaseGraphHasMostLiveVectorsAmongEligible`: 2-6 segments with random sizes and deletion counts (about half of them within the threshold), readers added in 5 shuffled orders, on both `IncrementalHnswGraphMerger` and `ConcurrentHnswMerger`. 



-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "HoustonPutman (via GitHub)" <gi...@apache.org>.
HoustonPutman commented on PR #16739:
URL: https://github.com/apache/lucene/pull/16739#issuecomment-6298786451

   Ok, I merged, but not all the changes made it into the commit, specifically the change for `DELETE_PCT_THRESHOLD` to be static. How strange..... Will get this fixed and committed.


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #16739:
URL: https://github.com/apache/lucene/pull/16739#issuecomment-5937554378

   LGTM at first glance, assuming we want to start with a graph having the highest live vector count.
   
   However, I'm not super familiar with the original change, and it would be great to get this reviewed by someone who is!
   
   Adding the 10.6 milestone for now, given it is a small fix.


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on code in PR #16739:
URL: https://github.com/apache/lucene/pull/16739#discussion_r4152318652


##########
lucene/core/src/test/org/apache/lucene/util/hnsw/TestIncrementalHnswGraphMergerBaseSelection.java:
##########
@@ -0,0 +1,118 @@
+/*
+ * 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.List;
+import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.NoMergePolicy;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
+
+/**
+ * Tests which source graph {@link IncrementalHnswGraphMerger} picks as the base graph when some
+ * candidates carry deletions.
+ */
+public class TestIncrementalHnswGraphMergerBaseSelection extends LuceneTestCase {
+
+  private static final int DIM = 16;
+  private static final String FIELD = "v";
+
+  /**
+   * Segment A has 1000 nodes of which 300 are deleted (700 live, 30% deleted, under the 40%
+   * threshold); segment B has 900 nodes and no deletions. B holds more live vectors, so it must be
+   * chosen as the base regardless of the order in which the readers are added.
+   */
+  public void testBaseGraphChosenByLiveCount() throws IOException {
+    try (Directory dir = newDirectory()) {
+      IndexWriterConfig cfg = new IndexWriterConfig();
+      cfg.setCodec(TestUtil.alwaysKnnVectorsFormat(new Lucene99HnswVectorsFormat(16, 100, 0)));
+      cfg.setMergePolicy(NoMergePolicy.INSTANCE);
+      try (IndexWriter w = new IndexWriter(dir, cfg)) {
+        addSegment(w, "a", 1000);

Review Comment:
   done



-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "LantaoJin (via GitHub)" <gi...@apache.org>.
LantaoJin commented on code in PR #16739:
URL: https://github.com/apache/lucene/pull/16739#discussion_r4152312069


##########
lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java:
##########
@@ -64,9 +64,14 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
    */
   private final int DELETE_PCT_THRESHOLD = 40;
 
-  /** Represents a vector reader that contains graph info. */
+  /**
+   * Represents a vector reader that contains graph info.
+   *

Review Comment:
   Done, added `@param` for `reader` and `initDocMap` as well.



-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Compare live vector counts when picking the HNSW merge base graph [lucene]

Posted by "HoustonPutman (via GitHub)" <gi...@apache.org>.
HoustonPutman merged PR #16739:
URL: https://github.com/apache/lucene/pull/16739


-- 
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: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org