You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2025/09/05 13:58:41 UTC
(lucene) 01/02: Add bulk-retrieval API to NumericDocValues. (#15149)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit af1883a4110d472eae4f5e402c7eae090a731dd8
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Fri Sep 5 15:53:05 2025 +0200
Add bulk-retrieval API to NumericDocValues. (#15149)
Lucene recently got very good performance improvements by introducing APIs that
apply to batches of doc IDs at once: `DocIdSetIterator#intoBitSet`,
`PostingsEnum#nextPostings`, `Scorer#nextDocsAndScores` and `SimScorer#score`.
This helps better amortize the cost of virtual function calls across many doc
IDs, and also apply additional optimizations, e.g. it's more efficient to
bulk-iterate set bits in a `FixedBitSet` than to iterate them one-by-one via
`FixedBitSet#nextSetBit`.
This PR introduces bulk retrieval for numeric doc values. It is currently only
implemented on norms and used to retrieve norms for doc IDs to score, but I
tried to design the API in a way that also works for numeric doc values and is
sustainable. Specifically, I'm thinking that optimizing the single-valued and
dense case should go a very long way, so I did not try to help users retrieve
information about which docs have a value or not. In some cases, this is not
even needed. E.g. if you want to compute the sum of the values of a field,
returning 0 for docs that don't have a value is good. In the event when knowing
which docs have a value is important (such as Lucene's `HistogramCollector`),
it is still possible to optimize the case when there are long runs of docs with
a value with something like below:
```java
void doSomethingWith(int size, int[] docs, NumericDocValues values) {
if (size > 0 && values.advanceExact(docs[0]) && values.docIDRunEnd() > docs[size - 1]) {
long[] longValues = new long[size];
values.longValues(size, docs, longValues);
// do something with the `longValues` array
} else {
// use #advanceExact / #longValue directly
for (int i = 0; i < size; i++) {
if (values.advanceExact(docs[i])) {
// do something with values#longValue
} else {
// handle the case when docs don't have a value
}
}
}
}
```
---
lucene/CHANGES.txt | 3 +-
.../benchmark/jmh/PolymorphismBenchmark.java | 191 +++++++++++++++++++++
.../codecs/lucene90/Lucene90NormsProducer.java | 16 ++
.../java/org/apache/lucene/index/CheckIndex.java | 44 ++++-
.../org/apache/lucene/index/NumericDocValues.java | 59 +++++++
.../java/org/apache/lucene/search/TermScorer.java | 8 +-
.../lucene/tests/index/AssertingLeafReader.java | 17 ++
.../tests/index/BaseNormsFormatTestCase.java | 22 +++
8 files changed, 350 insertions(+), 10 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 244d7d6b741..0a2862bfcc1 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -7,7 +7,8 @@ http://s.apache.org/luceneversions
API Changes
---------------------
-(No changes)
+* GITHUB#15149: Introduce NumericDocValues#longValues to help speed up the
+ retrieval of many doc values at once. (Adrien Grand)
New Features
---------------------
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/PolymorphismBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/PolymorphismBenchmark.java
new file mode 100644
index 00000000000..f3a561207f8
--- /dev/null
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/PolymorphismBenchmark.java
@@ -0,0 +1,191 @@
+/*
+ * 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.benchmark.jmh;
+
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@State(Scope.Benchmark)
+@Warmup(iterations = 5, time = 1)
+@Measurement(iterations = 5, time = 1)
+@Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx1g", "-Xms1g", "-XX:+AlwaysPreTouch"})
+public class PolymorphismBenchmark {
+
+ public abstract static class IntList {
+
+ public abstract int size();
+
+ public abstract int get(int index);
+
+ public final long sum1() {
+ long sum = 0;
+ for (int i = 0; i < size(); ++i) {
+ sum += get(i);
+ }
+ return sum;
+ }
+
+ public long sum2() {
+ long sum = 0;
+ for (int i = 0; i < size(); ++i) {
+ sum += get(i);
+ }
+ return sum;
+ }
+
+ public abstract long sum3();
+ }
+
+ public static class List1 extends IntList {
+
+ @Override
+ public int size() {
+ return 128;
+ }
+
+ @Override
+ public int get(int index) {
+ return 1;
+ }
+
+ @Override
+ public long sum2() {
+ return super.sum2();
+ }
+
+ @Override
+ public long sum3() {
+ long sum = 0;
+ for (int i = 0; i < size(); ++i) {
+ sum += get(i);
+ }
+ return sum;
+ }
+ }
+
+ public static class List2 extends IntList {
+
+ @Override
+ public int size() {
+ return 128;
+ }
+
+ @Override
+ public int get(int index) {
+ return 2;
+ }
+
+ @Override
+ public long sum2() {
+ return super.sum2();
+ }
+
+ @Override
+ public long sum3() {
+ long sum = 0;
+ for (int i = 0; i < size(); ++i) {
+ sum += get(i);
+ }
+ return sum;
+ }
+ }
+
+ public static class List3 extends IntList {
+
+ @Override
+ public int size() {
+ return 128;
+ }
+
+ @Override
+ public int get(int index) {
+ return 3;
+ }
+
+ @Override
+ public long sum2() {
+ return super.sum2();
+ }
+
+ @Override
+ public long sum3() {
+ long sum = 0;
+ for (int i = 0; i < size(); ++i) {
+ sum += get(i);
+ }
+ return sum;
+ }
+ }
+
+ private IntList[] lists;
+
+ @Setup(Level.Trial)
+ public void setup() throws Exception {
+ lists = new IntList[100];
+ Random r = new Random(0);
+ for (int i = 0; i < lists.length; ++i) {
+ lists[i] =
+ switch (r.nextInt(4)) {
+ case 0 -> new List1();
+ case 1 -> new List2();
+ default -> new List3();
+ };
+ }
+ }
+
+ @Benchmark
+ public long defaultImpl() {
+ long sum = 0;
+ for (IntList list : lists) {
+ sum += list.sum1();
+ }
+ return sum;
+ }
+
+ @Benchmark
+ public long delegateToDefaultImpl() {
+ long sum = 0;
+ for (IntList list : lists) {
+ sum += list.sum2();
+ }
+ return sum;
+ }
+
+ @Benchmark
+ public long specializedImpl() {
+ long sum = 0;
+ for (IntList list : lists) {
+ sum += list.sum3();
+ }
+ return sum;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90NormsProducer.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90NormsProducer.java
index 2cb55cc83ad..eee20a766aa 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90NormsProducer.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90NormsProducer.java
@@ -398,6 +398,14 @@ final class Lucene90NormsProducer extends NormsProducer implements Cloneable {
public long longValue() throws IOException {
return slice.readByte(doc);
}
+
+ @Override
+ public void longValues(int size, int[] docs, long[] values, long defaultValue)
+ throws IOException {
+ // Delegate to help performance: when the super call inlines, calls to
+ // #advanceExact/#longValue become monomorphic.
+ super.longValues(size, docs, values, defaultValue);
+ }
};
case 2:
return new DenseNormsIterator(maxDoc) {
@@ -452,6 +460,14 @@ final class Lucene90NormsProducer extends NormsProducer implements Cloneable {
public long longValue() throws IOException {
return slice.readByte(disi.index());
}
+
+ @Override
+ public void longValues(int size, int[] docs, long[] values, long defaultValue)
+ throws IOException {
+ // Delegate to help performance: when the super call inlines, calls to
+ // #advanceExact/#longValue become monomorphic.
+ super.longValues(size, docs, values, defaultValue);
+ }
};
case 2:
return new SparseNormsIterator(disi) {
diff --git a/lucene/core/src/java/org/apache/lucene/index/CheckIndex.java b/lucene/core/src/java/org/apache/lucene/index/CheckIndex.java
index 02dc9888b78..e5d643933a8 100644
--- a/lucene/core/src/java/org/apache/lucene/index/CheckIndex.java
+++ b/lucene/core/src/java/org/apache/lucene/index/CheckIndex.java
@@ -1381,6 +1381,8 @@ public final class CheckIndex implements Closeable {
for (FieldInfo info : reader.getFieldInfos()) {
if (info.hasNorms()) {
checkNumericDocValues(info.name, normsReader.getNorms(info), normsReader.getNorms(info));
+ checkBulkFetchNumericDocValues(
+ info.name, normsReader.getNorms(info), normsReader.getNorms(info), reader.maxDoc());
++status.totFields;
}
}
@@ -3330,7 +3332,7 @@ public final class CheckIndex implements Closeable {
for (FieldInfo fieldInfo : reader.getFieldInfos()) {
if (fieldInfo.getDocValuesType() != DocValuesType.NONE) {
status.totalValueFields++;
- checkDocValues(fieldInfo, dvReader, status);
+ checkDocValues(fieldInfo, reader.maxDoc(), dvReader, status);
}
}
@@ -3824,8 +3826,44 @@ public final class CheckIndex implements Closeable {
}
}
+ private static void checkBulkFetchNumericDocValues(
+ String fieldName, NumericDocValues ndv, NumericDocValues ndv2, int maxDoc)
+ throws IOException {
+
+ int[] docs = new int[16];
+ long[] values = new long[16];
+
+ for (int doc = -1; doc < maxDoc; ) {
+ int size = 0;
+ for (int j = 0; j < docs.length; ++j) {
+ doc += 1 + (j & 0x03);
+ if (doc >= maxDoc) {
+ break;
+ }
+ docs[size++] = doc;
+ }
+
+ long defaultValue = 42L;
+ ndv.longValues(size, docs, values, defaultValue);
+
+ for (int j = 0; j < size; ++j) {
+ long expected;
+ if (ndv2.advanceExact(docs[j])) {
+ expected = ndv2.longValue();
+ } else {
+ expected = defaultValue;
+ }
+ if (values[j] != expected) {
+ throw new CheckIndexException(
+ "#longValues reports different value: " + values[j] + " != " + expected);
+ }
+ }
+ }
+ }
+
private static void checkDocValues(
- FieldInfo fi, DocValuesProducer dvReader, DocValuesStatus status) throws Exception {
+ FieldInfo fi, int maxDoc, DocValuesProducer dvReader, DocValuesStatus status)
+ throws Exception {
if (fi.docValuesSkipIndexType() != DocValuesSkipIndexType.NONE) {
status.totalSkippingIndex++;
checkDocValueSkipper(fi, dvReader.getSkipper(fi));
@@ -3856,6 +3894,8 @@ public final class CheckIndex implements Closeable {
status.totalNumericFields++;
checkDVIterator(fi, dvReader::getNumeric);
checkNumericDocValues(fi.name, dvReader.getNumeric(fi), dvReader.getNumeric(fi));
+ checkBulkFetchNumericDocValues(
+ fi.name, dvReader.getNumeric(fi), dvReader.getNumeric(fi), maxDoc);
break;
case NONE:
default:
diff --git a/lucene/core/src/java/org/apache/lucene/index/NumericDocValues.java b/lucene/core/src/java/org/apache/lucene/index/NumericDocValues.java
index 7e6984e2686..4e89f3b3d80 100644
--- a/lucene/core/src/java/org/apache/lucene/index/NumericDocValues.java
+++ b/lucene/core/src/java/org/apache/lucene/index/NumericDocValues.java
@@ -18,6 +18,8 @@
package org.apache.lucene.index;
import java.io.IOException;
+import org.apache.lucene.search.BooleanClause.Occur;
+import org.apache.lucene.search.FieldExistsQuery;
/** A per-document numeric value. */
public abstract class NumericDocValues extends DocValuesIterator {
@@ -32,4 +34,61 @@ public abstract class NumericDocValues extends DocValuesIterator {
* @return numeric value
*/
public abstract long longValue() throws IOException;
+
+ /**
+ * Bulk retrieval of numeric doc values. This API helps reduce the performance impact of virtual
+ * function calls.
+ *
+ * <p>This API behaves as if implemented as below, which is the default implementation:
+ *
+ * <pre class="prettyprint">
+ * public void longValues(int size, int[] docs, long[] values, long defaultValue) throws IOException {
+ * for (int i = 0; i < size; ++i) {
+ * int doc = docs[i];
+ * long value;
+ * if (advanceExact(doc)) {
+ * value = longValue();
+ * } else {
+ * value = defaultValue;
+ * }
+ * values[i] = value;
+ * }
+ * }
+ * </pre>
+ *
+ * <p><b>NOTE</b>: The {@code docs} array is required to be sorted in ascending order with no
+ * duplicates.
+ *
+ * <p><b>NOTE</b>: This API doesn't allow callers to know which doc IDs have a value or not. If
+ * you need to exclude documents that don't have a value for this field, then you could apply a
+ * {@link FieldExistsQuery} as a {@link Occur#FILTER} clause. Another option is to fall back to
+ * using {@link #advanceExact} and {@link #longValue()} on ranges of doc IDs that may not be
+ * dense, e.g.
+ *
+ * <pre class="prettyprint">
+ * if (size > 0 && values.advannceExact(docs[0]) && values.docIDRunEnd() > docs[size - 1]) {
+ * // use values#longValues to retrieve values
+ * } else {
+ * // some docs may not have a value, use #advanceExact and #longValue
+ * }
+ * </pre>
+ *
+ * @param size the number of values to retrieve
+ * @param docs the buffer of doc IDs whose values should be looked up
+ * @param values the buffer of values to fill
+ * @param defaultValue the value to put in the buffer when a document doesn't have a value
+ */
+ public void longValues(int size, int[] docs, long[] values, long defaultValue)
+ throws IOException {
+ for (int i = 0; i < size; ++i) {
+ int doc = docs[i];
+ long value;
+ if (advanceExact(doc)) {
+ value = longValue();
+ } else {
+ value = defaultValue;
+ }
+ values[i] = value;
+ }
+ }
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/TermScorer.java b/lucene/core/src/java/org/apache/lucene/search/TermScorer.java
index 46cf1753441..991b3a83171 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TermScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TermScorer.java
@@ -160,13 +160,7 @@ public final class TermScorer extends Scorer {
}
}
if (norms != null) {
- for (int i = 0; i < size; ++i) {
- if (norms.advanceExact(buffer.docs[i])) {
- normValues[i] = norms.longValue();
- } else {
- normValues[i] = 1L;
- }
- }
+ norms.longValues(size, buffer.docs, normValues, 1L);
}
bulkScorer.score(buffer.size, buffer.features, normValues, buffer.features);
diff --git a/lucene/test-framework/src/java/org/apache/lucene/tests/index/AssertingLeafReader.java b/lucene/test-framework/src/java/org/apache/lucene/tests/index/AssertingLeafReader.java
index 6715c157a4d..b90139abb5e 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/tests/index/AssertingLeafReader.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/tests/index/AssertingLeafReader.java
@@ -840,6 +840,23 @@ public class AssertingLeafReader extends FilterLeafReader {
return in.longValue();
}
+ @Override
+ public void longValues(int size, int[] docs, long[] values, long defaultValue)
+ throws IOException {
+ assertThread("Numeric doc values", creationThread);
+ assert size >= 0;
+ assert size == 0 || docs[0] >= docID();
+ assert size == 0 || docs[0] >= 0;
+ for (int i = 1; i < size; ++i) {
+ assert docs[i] > docs[i - 1];
+ }
+ assert size == 0 || docs[size - 1] < maxDoc;
+ int expectedDocIdOnReturn = size == 0 ? docID() : docs[size - 1];
+ super.longValues(size, docs, values, defaultValue);
+ lastDocID = in.docID();
+ assert lastDocID == expectedDocIdOnReturn;
+ }
+
@Override
public String toString() {
return "AssertingNumericDocValues(" + in + ")";
diff --git a/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseNormsFormatTestCase.java b/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseNormsFormatTestCase.java
index 2c25b1315cb..5c3f97db33c 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseNormsFormatTestCase.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseNormsFormatTestCase.java
@@ -588,6 +588,28 @@ public abstract class BaseNormsFormatTestCase extends BaseIndexFileFormatTestCas
assertEquals("doc " + d, expected.longValue(), actual.longValue());
}
assertEquals(NO_MORE_DOCS, actual.nextDoc());
+
+ // Now check bulk fetching
+ expected = r.getNumericDocValues("dv");
+ actual = r.getNormValues("indexed");
+
+ int[] docs = new int[16];
+ long[] expectedValues = new long[16];
+ long[] actualValues = new long[16];
+ for (int doc = -1; doc < r.maxDoc(); ) {
+ int size = 0;
+ for (int j = 0; j < docs.length; ++j) {
+ doc += 1 + (j & 0x03);
+ if (doc >= r.maxDoc()) {
+ break;
+ }
+ docs[size++] = doc;
+ }
+
+ expected.longValues(size, docs, expectedValues, size);
+ actual.longValues(size, docs, actualValues, size);
+ assertArrayEquals(expectedValues, actualValues);
+ }
}
}
}