You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ms...@apache.org on 2026/03/12 21:28:06 UTC
(lucene) branch main updated: Add interface to do prefetch on KnnVectorValues and an example implementation to use prefetch in Scorer (#15722)
This is an automated email from the ASF dual-hosted git repository.
msfroh pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 6ca1d16a6cd Add interface to do prefetch on KnnVectorValues and an example implementation to use prefetch in Scorer (#15722)
6ca1d16a6cd is described below
commit 6ca1d16a6cd70081bac08fba9393f3863c1b70f0
Author: Navneet Verma <na...@amazon.com>
AuthorDate: Thu Mar 12 14:27:59 2026 -0700
Add interface to do prefetch on KnnVectorValues and an example implementation to use prefetch in Scorer (#15722)
Signed-off-by: Navneet Verma <na...@amazon.com>
---
lucene/CHANGES.txt | 3 +
.../codecs/hnsw/PrefetchableFlatVectorScorer.java | 255 +++++++++++++++++++++
.../codecs/lucene95/OffHeapByteVectorValues.java | 17 ++
.../codecs/lucene95/OffHeapFloatVectorValues.java | 18 ++
.../org/apache/lucene/index/KnnVectorValues.java | 8 +
.../hnsw/TestPrefetchableFlatVectorScorer.java | 63 +++++
.../codecs/lucene95/TestOffHeapVectorValues.java | 115 ++++++++++
7 files changed, 479 insertions(+)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index a6209f06ed0..08366c78888 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -221,6 +221,9 @@ New Features
to use this API, fixing the rewrite optimization for fields with PointValues but no skip index.
(Salvatore Campagna)
+* GITHUB#15722: Add interface to do prefetch on KnnVectorValues and an example implementation to use prefetch
+ in Scorer (Navneet Verma)
+
Improvements
---------------------
* GITHUB#15757: Better skipper-based numeric sort pruning from the start of segments (Alan Woodward)
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/hnsw/PrefetchableFlatVectorScorer.java b/lucene/core/src/java/org/apache/lucene/codecs/hnsw/PrefetchableFlatVectorScorer.java
new file mode 100644
index 00000000000..eca64dea9f4
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/hnsw/PrefetchableFlatVectorScorer.java
@@ -0,0 +1,255 @@
+/*
+ * 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.codecs.hnsw;
+
+import java.io.IOException;
+import org.apache.lucene.index.KnnVectorValues;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.hnsw.RandomVectorScorer;
+import org.apache.lucene.util.hnsw.RandomVectorScorerSupplier;
+import org.apache.lucene.util.hnsw.UpdateableRandomVectorScorer;
+
+/**
+ * A {@link FlatVectorsScorer} wrapper that enables prefetching of vector data before scoring.
+ *
+ * <p>This implementation demonstrates how to use prefetch operations with KNN search to preload
+ * vectors into memory before distance computations, potentially improving performance by reducing
+ * memory access latency during bulk scoring operations.
+ *
+ * <p>The prefetching occurs in {@link PrefetchableRandomVectorScorer#bulkScore} before delegating
+ * to the underlying scorer.
+ *
+ * @lucene.experimental
+ */
+public class PrefetchableFlatVectorScorer implements FlatVectorsScorer {
+
+ private final FlatVectorsScorer flatVectorsScorer;
+
+ /**
+ * Constructs a new prefetchable scorer wrapper.
+ *
+ * @param flatVectorsScorer the underlying scorer to delegate to
+ */
+ public PrefetchableFlatVectorScorer(FlatVectorsScorer flatVectorsScorer) {
+ this.flatVectorsScorer = flatVectorsScorer;
+ }
+
+ @Override
+ public RandomVectorScorerSupplier getRandomVectorScorerSupplier(
+ VectorSimilarityFunction similarityFunction, KnnVectorValues vectorValues)
+ throws IOException {
+ return new PrefetchableRandomVectorScorerSupplier(
+ flatVectorsScorer.getRandomVectorScorerSupplier(similarityFunction, vectorValues),
+ vectorValues);
+ }
+
+ @Override
+ public RandomVectorScorer getRandomVectorScorer(
+ VectorSimilarityFunction similarityFunction, KnnVectorValues vectorValues, float[] target)
+ throws IOException {
+ return new PrefetchableRandomVectorScorer(
+ (RandomVectorScorer.AbstractRandomVectorScorer)
+ flatVectorsScorer.getRandomVectorScorer(similarityFunction, vectorValues, target));
+ }
+
+ @Override
+ public RandomVectorScorer getRandomVectorScorer(
+ VectorSimilarityFunction similarityFunction, KnnVectorValues vectorValues, byte[] target)
+ throws IOException {
+ return new PrefetchableRandomVectorScorer(
+ (RandomVectorScorer.AbstractRandomVectorScorer)
+ flatVectorsScorer.getRandomVectorScorer(similarityFunction, vectorValues, target));
+ }
+
+ @Override
+ public String toString() {
+ return "PrefetchableFlatVectorScorer()";
+ }
+
+ /**
+ * A supplier that wraps another {@link RandomVectorScorerSupplier} to provide prefetchable
+ * scorers.
+ */
+ static class PrefetchableRandomVectorScorerSupplier implements RandomVectorScorerSupplier {
+
+ private final RandomVectorScorerSupplier randomVectorScorerSupplier;
+ private final KnnVectorValues vectorValues;
+
+ /**
+ * Constructs a new prefetchable scorer supplier.
+ *
+ * @param randomVectorScorerSupplier the underlying scorer supplier to delegate to
+ * @param vectorValues the vector values for prefetching
+ */
+ public PrefetchableRandomVectorScorerSupplier(
+ RandomVectorScorerSupplier randomVectorScorerSupplier, KnnVectorValues vectorValues) {
+ this.randomVectorScorerSupplier = randomVectorScorerSupplier;
+ this.vectorValues = vectorValues;
+ }
+
+ @Override
+ public UpdateableRandomVectorScorer scorer() throws IOException {
+ return new PrefetchableUpdatableRandomVectorScorer(
+ this.randomVectorScorerSupplier.scorer(), vectorValues);
+ }
+
+ @Override
+ public RandomVectorScorerSupplier copy() throws IOException {
+ return new PrefetchableRandomVectorScorerSupplier(
+ randomVectorScorerSupplier.copy(), vectorValues.copy());
+ }
+ }
+
+ /**
+ * A {@link RandomVectorScorer} that prefetches vector data before bulk scoring operations.
+ *
+ * <p>This scorer delegates all operations to an underlying scorer, but intercepts {@link
+ * #bulkScore} to prefetch the required vectors before scoring.
+ */
+ static class PrefetchableRandomVectorScorer
+ extends RandomVectorScorer.AbstractRandomVectorScorer {
+
+ private final RandomVectorScorer.AbstractRandomVectorScorer delegate;
+
+ /**
+ * Constructs a new prefetchable random vector scorer.
+ *
+ * @param delegate the underlying scorer to delegate to
+ */
+ public PrefetchableRandomVectorScorer(
+ final RandomVectorScorer.AbstractRandomVectorScorer delegate) {
+ super(delegate.values());
+ this.delegate = delegate;
+ }
+
+ @Override
+ public float score(int node) throws IOException {
+ return delegate.score(node);
+ }
+
+ /**
+ * Scores multiple nodes with prefetching optimization.
+ *
+ * <p>Prefetches vector data before delegating to the underlying scorer for improved
+ * performance.
+ *
+ * @param nodes array of node ordinals to score
+ * @param scores output array for computed scores
+ * @param numNodes number of nodes to score
+ * @return the maximum score computed
+ * @throws IOException if an I/O error occurs
+ */
+ @Override
+ public float bulkScore(int[] nodes, float[] scores, int numNodes) throws IOException {
+ values().prefetch(nodes, numNodes);
+ return delegate.bulkScore(nodes, scores, numNodes);
+ }
+
+ @Override
+ public int maxOrd() {
+ return delegate.maxOrd();
+ }
+
+ @Override
+ public int ordToDoc(int ord) {
+ return delegate.ordToDoc(ord);
+ }
+
+ @Override
+ public Bits getAcceptOrds(Bits acceptDocs) {
+ return delegate.getAcceptOrds(acceptDocs);
+ }
+
+ @Override
+ public KnnVectorValues values() {
+ return delegate.values();
+ }
+ }
+
+ /**
+ * An updateable random vector scorer that prefetches vector data before bulk scoring.
+ *
+ * <p>This scorer wraps an {@link UpdateableRandomVectorScorer} and adds prefetching capability to
+ * improve performance during bulk scoring operations.
+ */
+ static class PrefetchableUpdatableRandomVectorScorer
+ extends UpdateableRandomVectorScorer.AbstractUpdateableRandomVectorScorer {
+
+ private final UpdateableRandomVectorScorer delegate;
+
+ /**
+ * Constructs a new prefetchable updateable scorer.
+ *
+ * @param delegate the underlying scorer to delegate to
+ * @param vectorValues the vector values for prefetching
+ */
+ PrefetchableUpdatableRandomVectorScorer(
+ final UpdateableRandomVectorScorer delegate, final KnnVectorValues vectorValues) {
+ super(vectorValues);
+ this.delegate = delegate;
+ }
+
+ @Override
+ public void setScoringOrdinal(int node) throws IOException {
+ delegate.setScoringOrdinal(node);
+ }
+
+ @Override
+ public float score(int node) throws IOException {
+ return delegate.score(node);
+ }
+
+ /**
+ * Scores multiple nodes with prefetching optimization.
+ *
+ * <p>Prefetches vector data before performing bulk scoring.
+ *
+ * @param nodes array of node ordinals to score
+ * @param scores output array for computed scores
+ * @param numNodes number of nodes to score
+ * @return the maximum score computed
+ * @throws IOException if an I/O error occurs
+ */
+ @Override
+ public float bulkScore(int[] nodes, float[] scores, int numNodes) throws IOException {
+ values().prefetch(nodes, numNodes);
+ return super.bulkScore(nodes, scores, numNodes);
+ }
+
+ @Override
+ public int maxOrd() {
+ return delegate.maxOrd();
+ }
+
+ @Override
+ public int ordToDoc(int ord) {
+ return delegate.ordToDoc(ord);
+ }
+
+ @Override
+ public Bits getAcceptOrds(Bits acceptDocs) {
+ return delegate.getAcceptOrds(acceptDocs);
+ }
+
+ @Override
+ public KnnVectorValues values() {
+ return super.values();
+ }
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapByteVectorValues.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapByteVectorValues.java
index f6f63c41f87..6bc9963a579 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapByteVectorValues.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapByteVectorValues.java
@@ -81,6 +81,23 @@ public abstract class OffHeapByteVectorValues extends ByteVectorValues implement
return binaryValue;
}
+ @Override
+ public void prefetch(final int[] ordsToPrefetch, int numOrds) throws IOException {
+ if (ordsToPrefetch == null) {
+ return;
+ }
+ int finalNumOrds = Math.min(numOrds, ordsToPrefetch.length);
+ if (finalNumOrds <= 1) {
+ return;
+ }
+
+ // 1. calculate offset and prefetch immediately
+ for (int i = 0; i < finalNumOrds; i++) {
+ long offset = (long) ordsToPrefetch[i] * byteSize;
+ slice.prefetch(offset, byteSize);
+ }
+ }
+
@Override
public IndexInput getSlice() {
return slice;
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapFloatVectorValues.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapFloatVectorValues.java
index 7d221be3a90..3594e017076 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapFloatVectorValues.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene95/OffHeapFloatVectorValues.java
@@ -85,6 +85,24 @@ public abstract class OffHeapFloatVectorValues extends FloatVectorValues impleme
return value;
}
+ @Override
+ public void prefetch(final int[] ordsToPrefetch, int numOrds) throws IOException {
+ if (ordsToPrefetch == null) {
+ return;
+ }
+
+ int finalNumOrds = Math.min(numOrds, ordsToPrefetch.length);
+ if (finalNumOrds <= 1) {
+ return;
+ }
+
+ // 1. calculate offset and prefetch immediately
+ for (int i = 0; i < numOrds; i++) {
+ long offset = (long) ordsToPrefetch[i] * byteSize;
+ slice.prefetch(offset, byteSize);
+ }
+ }
+
public static OffHeapFloatVectorValues load(
VectorSimilarityFunction vectorSimilarityFunction,
FlatVectorsScorer flatVectorsScorer,
diff --git a/lucene/core/src/java/org/apache/lucene/index/KnnVectorValues.java b/lucene/core/src/java/org/apache/lucene/index/KnnVectorValues.java
index 8e58f387a33..a5718192435 100644
--- a/lucene/core/src/java/org/apache/lucene/index/KnnVectorValues.java
+++ b/lucene/core/src/java/org/apache/lucene/index/KnnVectorValues.java
@@ -49,6 +49,14 @@ public abstract class KnnVectorValues {
return ord;
}
+ /**
+ * Prefetches the provided ordinals
+ *
+ * @param ordsToPrefetch a list of ordinals to prefetch
+ * @param numOrds number of ords to prefetch from ordsToPrefetch array
+ */
+ public void prefetch(final int[] ordsToPrefetch, int numOrds) throws IOException {}
+
/**
* Creates a new copy of this {@link KnnVectorValues}. This is helpful when you need to access
* different values at once, to avoid overwriting the underlying vector returned.
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/hnsw/TestPrefetchableFlatVectorScorer.java b/lucene/core/src/test/org/apache/lucene/codecs/hnsw/TestPrefetchableFlatVectorScorer.java
new file mode 100644
index 00000000000..04dbed76ecc
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/codecs/hnsw/TestPrefetchableFlatVectorScorer.java
@@ -0,0 +1,63 @@
+/*
+ * 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.codecs.hnsw;
+
+import java.lang.reflect.Method;
+import java.lang.reflect.Modifier;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.hnsw.RandomVectorScorerSupplier;
+import org.junit.Test;
+
+/**
+ * Tests that {@link PrefetchableFlatVectorScorer} overrides all methods from {@link
+ * FlatVectorsScorer}.
+ */
+public class TestPrefetchableFlatVectorScorer extends LuceneTestCase {
+
+ @Test
+ public void testDeclaredMethodsOverridden() {
+ implTestDeclaredMethodsOverridden(FlatVectorsScorer.class, PrefetchableFlatVectorScorer.class);
+ implTestDeclaredMethodsOverridden(
+ RandomVectorScorerSupplier.class,
+ PrefetchableFlatVectorScorer.PrefetchableRandomVectorScorerSupplier.class);
+ implTestDeclaredMethodsOverridden(
+ PrefetchableFlatVectorScorer.PrefetchableRandomVectorScorer.class.getSuperclass(),
+ PrefetchableFlatVectorScorer.PrefetchableRandomVectorScorer.class);
+ implTestDeclaredMethodsOverridden(
+ PrefetchableFlatVectorScorer.PrefetchableUpdatableRandomVectorScorer.class.getSuperclass(),
+ PrefetchableFlatVectorScorer.PrefetchableUpdatableRandomVectorScorer.class);
+ }
+
+ private void implTestDeclaredMethodsOverridden(Class<?> interfaceClass, Class<?> implClass) {
+ for (final Method superClassMethod : interfaceClass.getDeclaredMethods()) {
+ final int modifiers = superClassMethod.getModifiers();
+ if (Modifier.isFinal(modifiers)) continue;
+ if (Modifier.isStatic(modifiers)) continue;
+ try {
+ final Method subClassMethod =
+ implClass.getDeclaredMethod(
+ superClassMethod.getName(), superClassMethod.getParameterTypes());
+ assertEquals(
+ "getReturnType() difference",
+ superClassMethod.getReturnType(),
+ subClassMethod.getReturnType());
+ } catch (NoSuchMethodException _) {
+ fail(implClass + " needs to override '" + superClassMethod + "'");
+ }
+ }
+ }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/lucene95/TestOffHeapVectorValues.java b/lucene/core/src/test/org/apache/lucene/codecs/lucene95/TestOffHeapVectorValues.java
new file mode 100644
index 00000000000..9b78f09f3f4
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/codecs/lucene95/TestOffHeapVectorValues.java
@@ -0,0 +1,115 @@
+/*
+ * 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.codecs.lucene95;
+
+import java.io.IOException;
+import java.util.concurrent.atomic.AtomicInteger;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.store.IndexInput;
+import org.apache.lucene.tests.util.LuceneTestCase;
+
+public class TestOffHeapVectorValues extends LuceneTestCase {
+
+ public void testPrefetchVectorValuesWithMoreThanOneOrds() throws IOException {
+ CountingIndexInput byteIndexInput = new CountingIndexInput();
+ OffHeapByteVectorValues values = createTestByteVectorValues(byteIndexInput);
+ values.prefetch(new int[] {1, 2, 5}, 2);
+ assertEquals(2, byteIndexInput.getPrefetchCount());
+
+ CountingIndexInput floatIndexInput = new CountingIndexInput();
+ OffHeapFloatVectorValues floatValues = createTestFloatVectorValues(floatIndexInput);
+ floatValues.prefetch(new int[] {1, 2, 5}, 2);
+ assertEquals(2, floatIndexInput.getPrefetchCount());
+ }
+
+ public void testPrefetchVectorValuesWithLessThanOneOrds() throws IOException {
+ CountingIndexInput byteIndexInput = new CountingIndexInput();
+ OffHeapByteVectorValues values = createTestByteVectorValues(byteIndexInput);
+ values.prefetch(null, 0);
+ assertEquals(0, byteIndexInput.getPrefetchCount());
+ values.prefetch(new int[] {1}, 1);
+ assertEquals(0, byteIndexInput.getPrefetchCount());
+
+ CountingIndexInput floatIndexInput = new CountingIndexInput();
+ OffHeapFloatVectorValues floatValues = createTestFloatVectorValues(floatIndexInput);
+ floatValues.prefetch(null, 0);
+ assertEquals(0, floatIndexInput.getPrefetchCount());
+ floatValues.prefetch(new int[] {1}, 1);
+ assertEquals(0, floatIndexInput.getPrefetchCount());
+ }
+
+ private OffHeapByteVectorValues createTestByteVectorValues(IndexInput indexInput)
+ throws IOException {
+ return new OffHeapByteVectorValues.DenseOffHeapVectorValues(
+ 100, 100, indexInput, 1, null, VectorSimilarityFunction.EUCLIDEAN);
+ }
+
+ private OffHeapFloatVectorValues createTestFloatVectorValues(IndexInput indexInput)
+ throws IOException {
+ return new OffHeapFloatVectorValues.DenseOffHeapVectorValues(
+ 100, 100, indexInput, 4, null, VectorSimilarityFunction.EUCLIDEAN);
+ }
+
+ private static final class CountingIndexInput extends IndexInput {
+
+ AtomicInteger counter;
+
+ public CountingIndexInput() {
+ super("closing index input");
+ counter = new AtomicInteger(0);
+ }
+
+ @Override
+ public void prefetch(long offset, long length) throws IOException {
+ counter.incrementAndGet();
+ }
+
+ public int getPrefetchCount() {
+ return counter.get();
+ }
+
+ @Override
+ public void close() throws IOException {}
+
+ @Override
+ public long getFilePointer() {
+ return 0;
+ }
+
+ @Override
+ public void seek(long pos) throws IOException {}
+
+ @Override
+ public long length() {
+ return 0;
+ }
+
+ @Override
+ public IndexInput slice(String sliceDescription, long offset, long length) throws IOException {
+ return null;
+ }
+
+ @Override
+ public byte readByte() throws IOException {
+ return 0;
+ }
+
+ @Override
+ public void readBytes(byte[] b, int offset, int len) throws IOException {}
+ }
+}