You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "benwtrent (via GitHub)" <gi...@apache.org> on 2025/02/18 19:33:51 UTC

[PR] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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

   Spinning out of: https://github.com/apache/lucene/pull/14226
   
   That particular evolution of kNN querying is attempting to re-entry individual segment graphs with new exit and search criteria. To prevent having to rescore the new entry points, this PR provides the ability to (optionally) keep track of the scores for entry points. 
   
   Additionally, this will take advantage of entry point score retention during graph building and searching. The performance improvements are marginal.


-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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

   > I also tried something based on the simpler approach I mentioned and also saw very minor gains in the seeded search with reentry when reusing scores.
   
   Yeah, I don't expect this to be a huge performance gain. I would expect the actual bottlenecks addressed in your changes (thrashing, over exploration, etc.) would dominate any savings.


-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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

   >  it might suffice to create a wrapping RandomVectorScorer  that would supply the cached scores, while delegating the others to the underlying scorer?
   
   🤔 Maybe we could wrap the scorer at the vector format level. But an iterator/score provider will need to still be given via the collector so that the format even knows that these things are providing valid scores.
   
   This PR is certainly making a ton of changes. I can split out some of the work, focusing at query time, instead of fully extending the HNSW builder to take advantage of the changes.


-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent closed pull request #14256: Reuse entry point scores and provide mechanisms to provide scores for directly entry points
URL: https://github.com/apache/lucene/pull/14256


-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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

   I also tried something based on the simpler approach I mentioned and also saw very minor gains in the seeded search with reentry when reusing scores.


-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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

   This proved not particularly useful. Maybe it can be a future optimization, but for now, it seems the added complexity isn't worth its cost. 


-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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


##########
lucene/core/src/java/org/apache/lucene/search/knn/MappedDISI.java:
##########
@@ -0,0 +1,102 @@
+/*
+ * 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.search.knn;
+
+import java.io.IOException;
+import org.apache.lucene.index.KnnVectorValues;
+import org.apache.lucene.search.DocIdSetIterator;
+
+/**
+ * A {@link DocIdSetIterator} that maps the doc ids from a {@link TopDocsDISI} to the corresponding
+ * vector ordinal
+ *
+ * @lucene.internal
+ */
+public sealed class MappedDISI extends DocIdSetIterator {

Review Comment:
   correct



-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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


##########
lucene/core/src/java/org/apache/lucene/search/knn/MappedDISI.java:
##########
@@ -0,0 +1,102 @@
+/*
+ * 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.search.knn;
+
+import java.io.IOException;
+import org.apache.lucene.index.KnnVectorValues;
+import org.apache.lucene.search.DocIdSetIterator;
+
+/**
+ * A {@link DocIdSetIterator} that maps the doc ids from a {@link TopDocsDISI} to the corresponding
+ * vector ordinal
+ *
+ * @lucene.internal
+ */
+public sealed class MappedDISI extends DocIdSetIterator {

Review Comment:
   whoa I had to look up what a sealed class is - I guess it is like final but you can allow some classes to inherit?



##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -229,25 +230,32 @@ public void addGraphNode(int node, UpdateableRandomVectorScorer scorer) throws I
       // NOTE: the entry node and max level may not be paired, but because we get the level first
       // we ensure that the entry node we get later will always exist on the curMaxLevel
       int[] eps = new int[] {hnsw.entryNode()};
+      float[] epsScores = new float[] {scorer.score(eps[0])};
 
       // we first do the search from top to bottom
       // for levels > nodeLevel search with topk = 1
       GraphBuilderKnnCollector candidates = entryCandidates;
       for (int level = curMaxLevel; level > nodeLevel; level--) {
         candidates.clear();
-        graphSearcher.searchLevel(candidates, scorer, level, eps, hnsw, null);
+        graphSearcher.searchLevel(candidates, scorer, level, eps, epsScores, hnsw, null);
+        epsScores[0] = candidates.queue.topScore();
         eps[0] = candidates.popNode();
       }
 
       // for levels <= nodeLevel search with topk = beamWidth, and add connections
       candidates = beamCandidates;
       NeighborArray[] scratchPerLevel =
           new NeighborArray[Math.min(nodeLevel, curMaxLevel) - lowestUnsetLevel + 1];
+      int epCount = eps.length;
       for (int i = scratchPerLevel.length - 1; i >= 0; i--) {
         int level = i + lowestUnsetLevel;
         candidates.clear();
-        graphSearcher.searchLevel(candidates, scorer, level, eps, hnsw, null);
-        eps = candidates.popUntilNearestKNodes();
+        graphSearcher.searchLevel(candidates, scorer, level, eps, epsScores, epCount, hnsw, null);
+        candidates.popUntilNearestKNodes();
+        eps = ArrayUtil.growExact(eps, candidates.size());
+        epsScores = ArrayUtil.growExact(epsScores, candidates.size());
+        epCount = candidates.size();
+        candidates.collectNodesAndScores(eps, epsScores);

Review Comment:
   you are re-using the scores from upper levels when scoring the lower levels? 



-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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

   Hi, @benwtrent , this bakes support for this supplying scores feature pretty deeply. I was thinking if we were to use this only for the SeededKnnVectorQuery, it might suffice to create a wrapping `RandomVectorScorer ` that would supply the cached scores, while delegating the others to the underlying scorer?


-- 
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] Reuse entry point scores and provide mechanisms to provide scores for directly entry points [lucene]

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


##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -229,25 +230,32 @@ public void addGraphNode(int node, UpdateableRandomVectorScorer scorer) throws I
       // NOTE: the entry node and max level may not be paired, but because we get the level first
       // we ensure that the entry node we get later will always exist on the curMaxLevel
       int[] eps = new int[] {hnsw.entryNode()};
+      float[] epsScores = new float[] {scorer.score(eps[0])};
 
       // we first do the search from top to bottom
       // for levels > nodeLevel search with topk = 1
       GraphBuilderKnnCollector candidates = entryCandidates;
       for (int level = curMaxLevel; level > nodeLevel; level--) {
         candidates.clear();
-        graphSearcher.searchLevel(candidates, scorer, level, eps, hnsw, null);
+        graphSearcher.searchLevel(candidates, scorer, level, eps, epsScores, hnsw, null);
+        epsScores[0] = candidates.queue.topScore();
         eps[0] = candidates.popNode();
       }
 
       // for levels <= nodeLevel search with topk = beamWidth, and add connections
       candidates = beamCandidates;
       NeighborArray[] scratchPerLevel =
           new NeighborArray[Math.min(nodeLevel, curMaxLevel) - lowestUnsetLevel + 1];
+      int epCount = eps.length;
       for (int i = scratchPerLevel.length - 1; i >= 0; i--) {
         int level = i + lowestUnsetLevel;
         candidates.clear();
-        graphSearcher.searchLevel(candidates, scorer, level, eps, hnsw, null);
-        eps = candidates.popUntilNearestKNodes();
+        graphSearcher.searchLevel(candidates, scorer, level, eps, epsScores, epCount, hnsw, null);
+        candidates.popUntilNearestKNodes();
+        eps = ArrayUtil.growExact(eps, candidates.size());
+        epsScores = ArrayUtil.growExact(epsScores, candidates.size());
+        epCount = candidates.size();
+        candidates.collectNodesAndScores(eps, epsScores);

Review Comment:
   Yes, we were recalculating entry point scores every time we add a node to a layer.



-- 
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