You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ro...@apache.org on 2026/06/10 14:17:24 UTC
(lucene) branch main updated: Add batch evaluation for sorted numeric ranges (#16166)
This is an automated email from the ASF dual-hosted git repository.
romseygeek 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 1c99a1eccf9 Add batch evaluation for sorted numeric ranges (#16166)
1c99a1eccf9 is described below
commit 1c99a1eccf9c2fb09a25da081d6857b5faf85232
Author: Costin Leau <co...@users.noreply.github.com>
AuthorDate: Wed Jun 10 07:17:17 2026 -0700
Add batch evaluation for sorted numeric ranges (#16166)
Implements rangeIntoBitSet on SortedNumericDocValues and uses it
in DocValuesRangeIterator to speed up matching on MAYBE blocks.
Lucene90DocValuesFormat can detect when a SortedNumericDocValues
field has a fixed cardinality and vectorize comparisons to accelerate
range queries.
---
lucene/CHANGES.txt | 2 +
.../SortedNumericDocValuesRangeQueryBenchmark.java | 201 +++++++++++++++
.../codecs/lucene90/Lucene90DocValuesProducer.java | 119 ++++++++-
.../lucene/index/SortedNumericDocValues.java | 37 +++
.../lucene/search/DocValuesRangeIterator.java | 281 +++++++++++----------
.../search/TestDocValuesOrdinalSetIterator.java | 4 +-
.../TestSkipBlockRangeIteratorIntoBitSet.java | 85 +++++++
.../TestSortedNumericDocValuesRangeIterator.java | 31 ++-
8 files changed, 621 insertions(+), 139 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index aa4e0d3d0e4..408099edf65 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -500,6 +500,8 @@ Optimizations
* GITHUB#16172: Bulk-evaluate skip-indexed sorted and sorted-set doc-values range queries via a block-aware
DocValuesRangeIterator#intoBitSet. (Costin Leau)
+* GITHUB#16166: Add bulk range evaluation for multi-valued sorted numeric doc values. (Costin Leau)
+
Bug Fixes
---------------------
* GITHUB#15754: Fix HTMLStripCharFilter to prevent tags from incorrectly consuming subsequent
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedNumericDocValuesRangeQueryBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedNumericDocValuesRangeQueryBenchmark.java
new file mode 100644
index 00000000000..dcfc0196c5f
--- /dev/null
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedNumericDocValuesRangeQueryBenchmark.java
@@ -0,0 +1,201 @@
+/*
+ * 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.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.Stream;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field.Store;
+import org.apache.lucene.document.SortedNumericDocValuesField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.BooleanClause.Occur;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.TermQuery;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.MMapDirectory;
+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.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.TearDown;
+import org.openjdk.jmh.annotations.Warmup;
+
+/** Benchmarks skip-indexed sorted-numeric doc values range queries. */
+@State(Scope.Thread)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.SECONDS)
+@Warmup(iterations = 3, time = 3)
+@Measurement(iterations = 5, time = 5)
+@Fork(value = 1, warmups = 1)
+public class SortedNumericDocValuesRangeQueryBenchmark {
+
+ private static final String CLUSTERED = "clustered";
+ private static final String MIXED = "mixed";
+ private static final String RANDOM = "random";
+ private static final String DENSE = "dense";
+ private static final String SPARSE = "sparse";
+ private static final String FIXED = "fixed";
+ private static final String VARIABLE = "variable";
+ private static final String PLAIN = "plain";
+ private static final String CONJUNCTION = "conjunction";
+ private static final long VALUE_SPACE = 1_000_000L;
+
+ private Directory dir;
+ private IndexReader reader;
+ private Path path;
+ private Query query;
+
+ @State(Scope.Benchmark)
+ public static class Params {
+ @Param({"1000000"})
+ public int docCount;
+
+ @Param({CLUSTERED, MIXED, RANDOM})
+ public String dataPattern;
+
+ @Param({"2", "4", "8"})
+ public int valuesPerDoc;
+
+ @Param({FIXED, VARIABLE})
+ public String cardinality;
+
+ @Param({DENSE, SPARSE})
+ public String density;
+
+ @Param({"0.01", "0.1", "0.5"})
+ public double selectivity;
+
+ @Param({PLAIN, CONJUNCTION})
+ public String queryShape;
+ }
+
+ @Setup(Level.Trial)
+ public void setup(Params params) throws Exception {
+ path = Files.createTempDirectory("sortedNumericRangeBench");
+ dir = MMapDirectory.open(path);
+
+ IndexWriterConfig iwc = new IndexWriterConfig();
+ IndexWriter writer = new IndexWriter(dir, iwc);
+ Random random = new Random(42);
+ long[] values = new long[params.valuesPerDoc];
+
+ for (int docID = 0; docID < params.docCount; docID++) {
+ Document doc = new Document();
+ doc.add(new StringField("all", "yes", Store.NO));
+ if (params.density.equals(DENSE) || (docID & 1) == 0) {
+ int valueCount =
+ params.cardinality.equals(FIXED)
+ ? params.valuesPerDoc
+ : 1 + random.nextInt(params.valuesPerDoc);
+ fillValues(values, valueCount, params.dataPattern, docID, params.docCount, random);
+ for (int i = 0; i < valueCount; i++) {
+ doc.add(SortedNumericDocValuesField.indexedField("sn", values[i]));
+ }
+ }
+ writer.addDocument(doc);
+ }
+ writer.forceMerge(1);
+ reader = DirectoryReader.open(writer);
+ writer.close();
+
+ long rangeWidth = Math.max(1L, (long) (VALUE_SPACE * params.selectivity));
+ long rangeStart = (VALUE_SPACE - rangeWidth) / 2;
+ Query rangeQuery =
+ SortedNumericDocValuesField.newSlowRangeQuery("sn", rangeStart, rangeStart + rangeWidth);
+ query =
+ switch (params.queryShape) {
+ case PLAIN -> rangeQuery;
+ case CONJUNCTION ->
+ new BooleanQuery.Builder()
+ .add(new TermQuery(new Term("all", "yes")), Occur.FILTER)
+ .add(rangeQuery, Occur.FILTER)
+ .build();
+ default ->
+ throw new IllegalArgumentException("Unknown query shape: " + params.queryShape);
+ };
+ }
+
+ private static void fillValues(
+ long[] values, int valueCount, String dataPattern, int docID, int docCount, Random random) {
+ for (int i = 0; i < valueCount; i++) {
+ values[i] =
+ switch (dataPattern) {
+ case CLUSTERED -> clusteredValue(docID, docCount, i, valueCount);
+ case MIXED ->
+ i == 0
+ ? clusteredValue(docID, docCount, i, valueCount)
+ : random.nextLong(VALUE_SPACE);
+ case RANDOM -> random.nextLong(VALUE_SPACE);
+ default -> throw new IllegalArgumentException("Unknown pattern: " + dataPattern);
+ };
+ }
+ Arrays.sort(values, 0, valueCount);
+ }
+
+ private static long clusteredValue(int docID, int docCount, int valueIndex, int valueCount) {
+ long base = docID * VALUE_SPACE / docCount;
+ long spread = Math.max(1L, VALUE_SPACE / docCount);
+ return Math.min(VALUE_SPACE - 1L, base + valueIndex * spread / valueCount);
+ }
+
+ @TearDown(Level.Trial)
+ public void tearDown() throws Exception {
+ reader.close();
+ if (dir != null) {
+ dir.close();
+ dir = null;
+ }
+ if (Files.exists(path)) {
+ try (Stream<Path> walk = Files.walk(path)) {
+ walk.sorted(Comparator.reverseOrder())
+ .forEach(
+ p -> {
+ try {
+ Files.delete(p);
+ } catch (IOException _) {
+ }
+ });
+ }
+ }
+ }
+
+ @Benchmark
+ public int searchSortedNumericRange() throws IOException {
+ IndexSearcher searcher = new IndexSearcher(reader);
+ return searcher.count(query);
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java
index 5cd3e7afac3..61f4f294242 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java
@@ -480,6 +480,55 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
values, fromDoc, toDoc, minValue, maxValue, bitSet, offset);
}
+ private static int fixedCardinality(
+ SortedNumericEntry entry, DocValuesSkipperEntry skipperEntry) {
+ if (skipperEntry == null
+ || skipperEntry.maxValueCount <= 1
+ || entry.numDocsWithField == 0
+ || entry.numValues % entry.numDocsWithField != 0) {
+ return -1;
+ }
+ long cardinality = entry.numValues / entry.numDocsWithField;
+ if (cardinality > Integer.MAX_VALUE || cardinality != skipperEntry.maxValueCount) {
+ return -1;
+ }
+ return (int) cardinality;
+ }
+
+ private static void sortedNumericScalarRangeIntoBitSet(
+ LongValues values,
+ int fromDoc,
+ int toDoc,
+ int cardinality,
+ long minValue,
+ long maxValue,
+ FixedBitSet bitSet,
+ int offset) {
+ for (int doc = fromDoc; doc < toDoc; doc++) {
+ long valueOffset = (long) doc * cardinality;
+ for (int i = 0; i < cardinality; i++) {
+ long value = values.get(valueOffset + i);
+ if (value >= minValue) {
+ if (value <= maxValue) {
+ bitSet.set(doc - offset);
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ private static boolean sortedNumericMatchesRange(
+ LongValues values, long start, long end, long minValue, long maxValue) {
+ for (long valueOffset = start; valueOffset < end; valueOffset++) {
+ long value = values.get(valueOffset);
+ if (value >= minValue) {
+ return value <= maxValue;
+ }
+ }
+ return false;
+ }
+
private static boolean canBulkDecodeByteAligned(NumericEntry entry) {
return entry.blockShift < 0 && entry.bitsPerValue > 0 && (entry.bitsPerValue & 0x07) == 0;
}
@@ -1767,10 +1816,11 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
@Override
public SortedNumericDocValues getSortedNumeric(FieldInfo field) throws IOException {
SortedNumericEntry entry = sortedNumerics.get(field.number);
- return getSortedNumeric(entry);
+ return getSortedNumeric(entry, skippers.get(field.number));
}
- private SortedNumericDocValues getSortedNumeric(SortedNumericEntry entry) throws IOException {
+ private SortedNumericDocValues getSortedNumeric(
+ SortedNumericEntry entry, DocValuesSkipperEntry skipperEntry) throws IOException {
if (entry.numValues == entry.numDocsWithField) {
return DocValues.singleton(getNumeric(entry));
}
@@ -1786,6 +1836,7 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
DirectMonotonicReader.getInstance(entry.addressesMeta, addressesInput, merging);
final LongValues values = getNumericValues(entry);
+ final int denseFixedCardinality = fixedCardinality(entry, skipperEntry);
if (entry.docsWithFieldOffset == -1) {
// dense
@@ -1840,6 +1891,34 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
return count;
}
+ @Override
+ public void rangeIntoBitSet(
+ int fromDoc, int toDoc, long minValue, long maxValue, FixedBitSet bitSet, int offset) {
+ int endDoc = Math.min(toDoc, maxDoc);
+ if (fromDoc >= endDoc) {
+ return;
+ }
+ if (entry.bitsPerValue == 0) {
+ if (entry.minValue >= minValue && entry.minValue <= maxValue) {
+ bitSet.set(fromDoc - offset, endDoc - offset);
+ }
+ return;
+ }
+ int cardinality = denseFixedCardinality;
+ if (cardinality > 1) {
+ sortedNumericScalarRangeIntoBitSet(
+ values, fromDoc, endDoc, cardinality, minValue, maxValue, bitSet, offset);
+ return;
+ }
+ for (int currentDoc = fromDoc; currentDoc < endDoc; currentDoc++) {
+ long startOffset = addresses.get(currentDoc);
+ long endOffset = addresses.get(currentDoc + 1L);
+ if (sortedNumericMatchesRange(values, startOffset, endOffset, minValue, maxValue)) {
+ bitSet.set(currentDoc - offset);
+ }
+ }
+ }
+
@Override
public int docIDRunEnd() throws IOException {
return maxDoc;
@@ -1911,6 +1990,40 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
return count;
}
+ @Override
+ public void rangeIntoBitSet(
+ int fromDoc, int toDoc, long minValue, long maxValue, FixedBitSet bitSet, int offset)
+ throws IOException {
+ set = false;
+ int endDoc = Math.min(toDoc, maxDoc);
+ if (fromDoc >= endDoc) {
+ return;
+ }
+ int currentDoc = disi.docID();
+ if (currentDoc < fromDoc) {
+ currentDoc = disi.advance(fromDoc);
+ }
+ if (currentDoc >= endDoc) {
+ return;
+ }
+ if (entry.bitsPerValue == 0) {
+ if (entry.minValue >= minValue && entry.minValue <= maxValue) {
+ disi.intoBitSet(endDoc, bitSet, offset);
+ }
+ set = false;
+ return;
+ }
+ for (; currentDoc < endDoc; currentDoc = disi.nextDoc()) {
+ int index = disi.index();
+ long startOffset = addresses.get(index);
+ long endOffset = addresses.get(index + 1L);
+ if (sortedNumericMatchesRange(values, startOffset, endOffset, minValue, maxValue)) {
+ bitSet.set(currentDoc - offset);
+ }
+ }
+ set = false;
+ }
+
@Override
public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
set = false;
@@ -2116,7 +2229,7 @@ final class Lucene90DocValuesProducer extends DocValuesProducer {
}
}
- final SortedNumericDocValues ords = getSortedNumeric(ordsEntry);
+ final SortedNumericDocValues ords = getSortedNumeric(ordsEntry, null);
return new BaseSortedSetDocValues(entry, data) {
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/index/SortedNumericDocValues.java b/lucene/core/src/java/org/apache/lucene/index/SortedNumericDocValues.java
index 438bfbf69f8..6367cd170ba 100644
--- a/lucene/core/src/java/org/apache/lucene/index/SortedNumericDocValues.java
+++ b/lucene/core/src/java/org/apache/lucene/index/SortedNumericDocValues.java
@@ -17,6 +17,7 @@
package org.apache.lucene.index;
import java.io.IOException;
+import org.apache.lucene.util.FixedBitSet;
/** A list of per-document numeric values, sorted according to {@link Long#compare(long, long)}. */
public abstract class SortedNumericDocValues extends DocValuesIterator {
@@ -35,4 +36,40 @@ public abstract class SortedNumericDocValues extends DocValuesIterator {
* It is illegal to call this method after {@link #advanceExact(int)} returned {@code false}.
*/
public abstract int docValueCount();
+
+ /**
+ * Fills a {@link FixedBitSet} with the doc IDs in {@code [fromDoc, toDoc)} whose sorted numeric
+ * values contain at least one value in {@code [minValue, maxValue]}.
+ *
+ * <p>The default implementation falls back to per-doc evaluation via {@link #advanceExact(int)},
+ * {@link #docValueCount()}, and {@link #nextValue()}. Subclasses with random-access storage can
+ * override this to avoid per-doc virtual dispatch.
+ *
+ * <p>Callers should not rely on the final iterator position after this method returns.
+ * Implementations may advance through some or all of the requested range.
+ *
+ * @param fromDoc first doc ID to evaluate (inclusive)
+ * @param toDoc last doc ID to evaluate (exclusive)
+ * @param minValue lower bound of the range (inclusive)
+ * @param maxValue upper bound of the range (inclusive)
+ * @param bitSet the bitset to fill
+ * @param offset subtracted from each doc ID before setting the bit
+ */
+ public void rangeIntoBitSet(
+ int fromDoc, int toDoc, long minValue, long maxValue, FixedBitSet bitSet, int offset)
+ throws IOException {
+ for (int doc = fromDoc; doc < toDoc; doc++) {
+ if (advanceExact(doc)) {
+ for (int i = 0, count = docValueCount(); i < count; i++) {
+ long value = nextValue();
+ if (value >= minValue) {
+ if (value <= maxValue) {
+ bitSet.set(doc - offset);
+ }
+ break;
+ }
+ }
+ }
+ }
+ }
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java b/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
index 3f22484ef91..f414fabfed6 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
@@ -52,15 +52,8 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
};
return skipper == null
? new DocValuesValueRangeIterator(values, check, 2)
- : new DocValuesBlockRangeIterator(
- values,
- new SkipBlockRangeIterator(skipper, min, max),
- check,
- 2,
- false,
- values,
- min,
- max);
+ : new BulkNumericRangeIterator(
+ values, new SkipBlockRangeIterator(skipper, min, max), check, 2, min, max);
}
/**
@@ -85,8 +78,8 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
};
return skipper == null
? new DocValuesValueRangeIterator(values, check, 5)
- : new DocValuesBlockRangeIterator(
- values, new SkipBlockRangeIterator(skipper, min, max), check, 2, false);
+ : new BulkSortedNumericRangeIterator(
+ values, new SkipBlockRangeIterator(skipper, min, max), check, 2, min, max);
}
/**
@@ -106,8 +99,8 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
};
return skipper == null
? new DocValuesValueRangeIterator(values, check, 2)
- : new DocValuesBlockRangeIterator(
- values, new SkipBlockRangeIterator(skipper, min, max), check, 2, false);
+ : new BulkOrdinalRangeIterator(
+ values, new SkipBlockRangeIterator(skipper, min, max), check, 2);
}
/**
@@ -132,8 +125,8 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
};
return skipper == null
? new DocValuesValueRangeIterator(values, check, 5)
- : new DocValuesBlockRangeIterator(
- values, new SkipBlockRangeIterator(skipper, min, max), check, 5, false);
+ : new BulkOrdinalRangeIterator(
+ values, new SkipBlockRangeIterator(skipper, min, max), check, 5);
}
/**
@@ -195,11 +188,7 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
return skipper == null
? new DocValuesValueRangeIterator(values, check, 2)
: new DocValuesBlockRangeIterator(
- values,
- new SkipBlockRangeIterator(skipper, ordinalSet.min, ordinalSet.max),
- check,
- 2,
- true);
+ values, new SkipBlockRangeIterator(skipper, ordinalSet.min, ordinalSet.max), check, 2);
}
/**
@@ -259,56 +248,38 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
return skipper == null
? new DocValuesValueRangeIterator(values, check, 5)
: new DocValuesBlockRangeIterator(
- values,
- new SkipBlockRangeIterator(skipper, ordinalSet.min, ordinalSet.max),
- check,
- 5,
- true);
+ values, new SkipBlockRangeIterator(skipper, ordinalSet.min, ordinalSet.max), check, 5);
}
- private static final class DocValuesBlockRangeIterator extends DocValuesRangeIterator {
+ /**
+ * Skip-indexed range iterator that confirms every candidate one doc at a time. Used for arbitrary
+ * ordinal sets, where even a YES block (all docs have a value within the [min, max] ord bounds)
+ * may contain docs whose ordinals fall in the gaps of the set, so there is no block-level
+ * shortcut and {@code intoBitSet} falls back to the per-doc {@link TwoPhaseIterator} default.
+ *
+ * <p>The block-aware bulk variants extend this class and override {@link #matches()}, {@link
+ * #docIDRunEnd()} and {@link #intoBitSet} to exploit the block classification.
+ */
+ private static sealed class DocValuesBlockRangeIterator extends DocValuesRangeIterator {
- private final SkipBlockRangeIterator blockIterator;
- private final DocIdSetIterator disi;
- private final IOBooleanSupplier predicate;
+ final SkipBlockRangeIterator blockIterator;
+ final DocIdSetIterator disi;
+ final IOBooleanSupplier predicate;
private final float matchCost;
- private final boolean alwaysCheckPredicate;
- // Non-null only for single-valued numeric doc values, in which case a whole block can be
- // range-evaluated in one shot in intoBitSet rather than confirming matches() one doc at a time.
- private final NumericDocValues numericValues;
- private final long minValue;
- private final long maxValue;
-
- private DocValuesBlockRangeIterator(
- DocIdSetIterator disi,
- SkipBlockRangeIterator blockIterator,
- IOBooleanSupplier predicate,
- float matchCost,
- boolean alwaysCheckPredicate) {
- this(disi, blockIterator, predicate, matchCost, alwaysCheckPredicate, null, 0, 0);
- }
private DocValuesBlockRangeIterator(
DocIdSetIterator disi,
SkipBlockRangeIterator blockIterator,
IOBooleanSupplier predicate,
- float matchCost,
- boolean alwaysCheckPredicate,
- NumericDocValues numericValues,
- long minValue,
- long maxValue) {
+ float matchCost) {
super(blockIterator);
this.disi = disi;
this.blockIterator = blockIterator;
this.predicate = predicate;
this.matchCost = matchCost;
- this.alwaysCheckPredicate = alwaysCheckPredicate;
- this.numericValues = numericValues;
- this.minValue = minValue;
- this.maxValue = maxValue;
}
- private boolean advanceDisi(int target) throws IOException {
+ final boolean advanceDisi(int target) throws IOException {
if (disi.docID() >= target) {
return disi.docID() == target;
}
@@ -317,9 +288,38 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
@Override
public boolean matches() throws IOException {
- if (alwaysCheckPredicate) {
- return advanceDisi(blockIterator.docID()) && predicate.get();
- }
+ return advanceDisi(blockIterator.docID()) && predicate.get();
+ }
+
+ @Override
+ public int docIDRunEnd() throws IOException {
+ return blockIterator.docID() + 1;
+ }
+
+ @Override
+ public final float matchCost() {
+ return matchCost;
+ }
+ }
+
+ /**
+ * Base class for the block-aware variants: a whole YES run is set in one shot, a YES_IF_PRESENT
+ * run's present docs are marked via {@link DocIdSetIterator#intoBitSet}, and only MAYBE runs need
+ * per-block confirmation. Subclasses supply the MAYBE handling in {@link #intoMaybeBlock}, which
+ * is the only piece that depends on the underlying doc-values type.
+ */
+ private abstract static sealed class BulkBlockRangeIterator extends DocValuesBlockRangeIterator {
+
+ private BulkBlockRangeIterator(
+ DocIdSetIterator disi,
+ SkipBlockRangeIterator blockIterator,
+ IOBooleanSupplier predicate,
+ float matchCost) {
+ super(disi, blockIterator, predicate, matchCost);
+ }
+
+ @Override
+ public final boolean matches() throws IOException {
return switch (blockIterator.getMatch()) {
case YES -> true;
case YES_IF_PRESENT -> advanceDisi(blockIterator.docID());
@@ -328,29 +328,12 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
}
@Override
- public int docIDRunEnd() throws IOException {
- if (alwaysCheckPredicate) {
- return blockIterator.docID() + 1;
- }
+ public final int docIDRunEnd() throws IOException {
return blockIterator.docIDRunEnd();
}
@Override
- public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
- if (numericValues == null) {
- if (alwaysCheckPredicate) {
- // Arbitrary ordinal set: every block (even YES) must run the per-doc predicate, so there
- // is no block-level shortcut to exploit. Confirm each candidate one doc at a time (the
- // TwoPhaseIterator default).
- super.intoBitSet(upTo, bitSet, offset);
- return;
- }
- // Ordinal range (sorted / sorted-set): there is no columnar range-decode like the numeric
- // path, but the block classification still lets us bulk-set YES runs and bulk-mark present
- // docs in YES_IF_PRESENT runs, confirming the ordinal predicate per doc only in MAYBE runs.
- ordinalRangeIntoBitSet(upTo, bitSet, offset);
- return;
- }
+ public final void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
while (blockIterator.docID() < upTo) {
int blockStart = blockIterator.docID();
SkipBlockRangeIterator.Match match = blockIterator.getMatch();
@@ -363,74 +346,106 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
switch (match) {
case YES -> bitSet.set(blockStart - offset, blockEnd - offset);
case YES_IF_PRESENT -> {
- // All present values are in range, but the field is sparse: set a bit for every
- // doc that has a value. Delegate to intoBitSet so dense codecs can bulk-set the run
- // rather than probing one doc at a time. Only advance forward; a preceding YES block
- // leaves the iterator behind blockStart, while MAYBE/YES_IF_PRESENT blocks leave it
- // at or past it.
- if (numericValues.docID() < blockStart) {
- numericValues.advance(blockStart);
- }
- numericValues.intoBitSet(blockEnd, bitSet, offset);
- }
- case MAYBE ->
- numericValues.rangeIntoBitSet(
- blockStart, blockEnd, minValue, maxValue, bitSet, offset);
- }
- blockIterator.advance(blockEnd);
- }
- }
-
- /**
- * Bulk-evaluates an ordinal range over the block structure. Functionally identical to per-doc
- * {@link #matches()} evaluation, but a whole YES run is set in one shot and a YES_IF_PRESENT
- * run's present docs are marked via {@link DocIdSetIterator#intoBitSet}; only MAYBE runs
- * confirm the ordinal predicate per doc. Like {@code matches()}, {@code disi} is the doc-values
- * iterator and {@code predicate} the range check. Mirrors the numeric block loop in {@link
- * #intoBitSet}: keep the two block walks in sync if the block-boundary handling changes.
- */
- private void ordinalRangeIntoBitSet(int upTo, FixedBitSet bitSet, int offset)
- throws IOException {
- while (blockIterator.docID() < upTo) {
- int blockStart = blockIterator.docID();
- SkipBlockRangeIterator.Match match = blockIterator.getMatch();
- // For MAYBE blocks docIDRunEnd() is conservative (doc+1), so use the full block boundary to
- // evaluate the whole block at once.
- int blockEnd =
- match == SkipBlockRangeIterator.Match.MAYBE
- ? Math.min(upTo, blockIterator.blockEnd())
- : Math.min(upTo, blockIterator.docIDRunEnd());
- switch (match) {
- case YES -> bitSet.set(blockStart - offset, blockEnd - offset);
- case YES_IF_PRESENT -> {
- // Every present value is in range, so mark each doc that has a value. Only advance
- // forward: a preceding YES block leaves disi behind blockStart, MAYBE/YES_IF_PRESENT
- // leave it at or past it.
+ // All present values are in range, so mark every doc that has a value. Delegate to
+ // intoBitSet so dense codecs can bulk-set the run rather than probing one doc at a
+ // time. Only advance forward; a preceding YES block leaves disi behind blockStart,
+ // while MAYBE/YES_IF_PRESENT blocks leave it at or past it.
if (disi.docID() < blockStart) {
disi.advance(blockStart);
}
disi.intoBitSet(blockEnd, bitSet, offset);
}
- case MAYBE -> {
- // Visit only docs that have a value (like matches() does) and confirm the ordinal
- // predicate one doc at a time.
- if (disi.docID() < blockStart) {
- disi.advance(blockStart);
- }
- for (int doc = disi.docID(); doc < blockEnd; doc = disi.nextDoc()) {
- if (predicate.get()) {
- bitSet.set(doc - offset);
- }
- }
- }
+ case MAYBE -> intoMaybeBlock(blockStart, blockEnd, bitSet, offset);
}
blockIterator.advance(blockEnd);
}
}
+ /** Confirms the docs of a single MAYBE block in {@code [blockStart, blockEnd)}. */
+ abstract void intoMaybeBlock(int blockStart, int blockEnd, FixedBitSet bitSet, int offset)
+ throws IOException;
+ }
+
+ /** Bulk range iterator over single-valued numeric doc values. */
+ private static final class BulkNumericRangeIterator extends BulkBlockRangeIterator {
+
+ private final NumericDocValues numericValues;
+ private final long minValue;
+ private final long maxValue;
+
+ private BulkNumericRangeIterator(
+ NumericDocValues values,
+ SkipBlockRangeIterator blockIterator,
+ IOBooleanSupplier predicate,
+ float matchCost,
+ long minValue,
+ long maxValue) {
+ super(values, blockIterator, predicate, matchCost);
+ this.numericValues = values;
+ this.minValue = minValue;
+ this.maxValue = maxValue;
+ }
+
@Override
- public float matchCost() {
- return matchCost;
+ void intoMaybeBlock(int blockStart, int blockEnd, FixedBitSet bitSet, int offset)
+ throws IOException {
+ numericValues.rangeIntoBitSet(blockStart, blockEnd, minValue, maxValue, bitSet, offset);
+ }
+ }
+
+ /** Bulk range iterator over multi-valued sorted-numeric doc values. */
+ private static final class BulkSortedNumericRangeIterator extends BulkBlockRangeIterator {
+
+ private final SortedNumericDocValues sortedNumericValues;
+ private final long minValue;
+ private final long maxValue;
+
+ private BulkSortedNumericRangeIterator(
+ SortedNumericDocValues values,
+ SkipBlockRangeIterator blockIterator,
+ IOBooleanSupplier predicate,
+ float matchCost,
+ long minValue,
+ long maxValue) {
+ super(values, blockIterator, predicate, matchCost);
+ this.sortedNumericValues = values;
+ this.minValue = minValue;
+ this.maxValue = maxValue;
+ }
+
+ @Override
+ void intoMaybeBlock(int blockStart, int blockEnd, FixedBitSet bitSet, int offset)
+ throws IOException {
+ sortedNumericValues.rangeIntoBitSet(blockStart, blockEnd, minValue, maxValue, bitSet, offset);
+ }
+ }
+
+ /**
+ * Bulk range iterator over ordinal (sorted / sorted-set) doc values. There is no columnar
+ * range-decode like the numeric path, so MAYBE blocks confirm the ordinal predicate one doc at a
+ * time, visiting only docs that have a value.
+ */
+ private static final class BulkOrdinalRangeIterator extends BulkBlockRangeIterator {
+
+ private BulkOrdinalRangeIterator(
+ DocIdSetIterator values,
+ SkipBlockRangeIterator blockIterator,
+ IOBooleanSupplier predicate,
+ float matchCost) {
+ super(values, blockIterator, predicate, matchCost);
+ }
+
+ @Override
+ void intoMaybeBlock(int blockStart, int blockEnd, FixedBitSet bitSet, int offset)
+ throws IOException {
+ if (disi.docID() < blockStart) {
+ disi.advance(blockStart);
+ }
+ for (int doc = disi.docID(); doc < blockEnd; doc = disi.nextDoc()) {
+ if (predicate.get()) {
+ bitSet.set(doc - offset);
+ }
+ }
}
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalSetIterator.java b/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalSetIterator.java
index 789b94561be..b5734d08e4d 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalSetIterator.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalSetIterator.java
@@ -36,7 +36,7 @@ import org.apache.lucene.util.IOBooleanSupplier;
*
* <p>Unlike the ordinal range tests, the ordinal set has a gap: ordinal 15 (the midpoint of [10,
* 20]) is excluded. This means docs with ordinal 15 are within the bounding range but NOT in the
- * matching set, exercising the predicate-always-checked behavior of {@code alwaysCheckPredicate}.
+ * matching set, exercising the per-doc predicate confirmation that arbitrary ordinal sets require.
*/
public class TestDocValuesOrdinalSetIterator extends BaseDocValuesSkipperTests {
@@ -386,7 +386,7 @@ public class TestDocValuesOrdinalSetIterator extends BaseDocValuesSkipperTests {
assertFalse(iter.matches());
// The key signal: docIDRunEnd must collapse to doc+1 because the set is not contiguous and
- // alwaysCheckPredicate is still true.
+ // every doc still needs per-doc predicate confirmation.
assertEquals(1, iter.docIDRunEnd());
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java b/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java
index 858b185e29b..76e01cae13c 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java
@@ -60,6 +60,8 @@ public class TestSkipBlockRangeIteratorIntoBitSet extends BaseDocValuesSkipperTe
values[i] = i % 100; // deterministic: 0..99 repeating
Document doc = new Document();
doc.add(NumericDocValuesField.indexedField("age", values[i]));
+ doc.add(SortedNumericDocValuesField.indexedField("multi_age", values[i] - 1000));
+ doc.add(SortedNumericDocValuesField.indexedField("multi_age", values[i]));
doc.add(NumericDocValuesField.indexedField("score", (i * 7L) % 1000));
w.addDocument(doc);
}
@@ -100,6 +102,28 @@ public class TestSkipBlockRangeIteratorIntoBitSet extends BaseDocValuesSkipperTe
twoPhase instanceof DocValuesRangeIterator);
}
+ public void testMultiValuedTwoPhaseIteratorIsWired() throws Exception {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ Query q = SortedNumericDocValuesField.newSlowRangeQuery("multi_age", 20, 40);
+ Weight weight = q.createWeight(searcher, ScoreMode.COMPLETE_NO_SCORES, 1f);
+ ScorerSupplier ss = weight.scorerSupplier(ctx);
+ assertNotNull("ScorerSupplier must not be null", ss);
+
+ assertTrue(
+ "ScorerSupplier must be a ConstantScoreScorerSupplier",
+ ss instanceof ConstantScoreScorerSupplier);
+ DocIdSetIterator iter = ((ConstantScoreScorerSupplier) ss).iterator(Long.MAX_VALUE);
+ TwoPhaseIterator twoPhase = TwoPhaseIterator.unwrap(iter);
+ assertTrue(
+ "Range query on multi-valued field with skip index must use a DocValuesRangeIterator,"
+ + " but got: "
+ + (twoPhase == null ? iter.getClass() : twoPhase.getClass()).getSimpleName(),
+ twoPhase instanceof DocValuesRangeIterator);
+ assertEquals(
+ searcher.count(SortedNumericDocValuesField.newSlowRangeQuery("age", 20, 40)),
+ searcher.count(q));
+ }
+
public void testSingleFieldRangeCorrectness() throws Exception {
// Count expected matches by scanning values[] directly
int expected = 0;
@@ -609,4 +633,65 @@ public class TestSkipBlockRangeIteratorIntoBitSet extends BaseDocValuesSkipperTe
}
}
}
+
+ public void testSortedNumericRangeIntoBitSetDenseFixedCardinality() throws Exception {
+ doTestSortedNumericRangeIntoBitSet(true, true);
+ }
+
+ public void testSortedNumericRangeIntoBitSetDenseVariableCardinality() throws Exception {
+ doTestSortedNumericRangeIntoBitSet(true, false);
+ }
+
+ public void testSortedNumericRangeIntoBitSetSparseFixedCardinality() throws Exception {
+ doTestSortedNumericRangeIntoBitSet(false, true);
+ }
+
+ public void testSortedNumericRangeIntoBitSetSparseVariableCardinality() throws Exception {
+ doTestSortedNumericRangeIntoBitSet(false, false);
+ }
+
+ private void doTestSortedNumericRangeIntoBitSet(boolean dense, boolean fixedCardinality)
+ throws Exception {
+ int numDocs = 4096 * 2;
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig iwc = new IndexWriterConfig().setCodec(new Lucene104Codec());
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (int docID = 0; docID < numDocs; docID++) {
+ Document doc = new Document();
+ if (dense || docID % 3 != 0) {
+ int valueCount = fixedCardinality ? 4 : 1 + (docID & 3);
+ long firstValue = (docID * 13L) % 100;
+ for (int i = 0; i < valueCount; i++) {
+ doc.add(SortedNumericDocValuesField.indexedField("sn", firstValue + i * 3L));
+ }
+ }
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ }
+
+ try (DirectoryReader reader = DirectoryReader.open(dir)) {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ FixedBitSet expected = new FixedBitSet(numDocs);
+ var expectedValues = ctx.reader().getSortedNumericDocValues("sn");
+ for (int docID = 0; docID < numDocs; docID++) {
+ if (expectedValues.advanceExact(docID)) {
+ for (int i = 0, count = expectedValues.docValueCount(); i < count; i++) {
+ long value = expectedValues.nextValue();
+ if (value >= 20) {
+ if (value <= 40) {
+ expected.set(docID);
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ FixedBitSet actual = new FixedBitSet(numDocs);
+ ctx.reader().getSortedNumericDocValues("sn").rangeIntoBitSet(0, numDocs, 20, 40, actual, 0);
+ assertEquals(expected, actual);
+ }
+ }
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestSortedNumericDocValuesRangeIterator.java b/lucene/core/src/test/org/apache/lucene/search/TestSortedNumericDocValuesRangeIterator.java
index fc4535a19c1..d1f8a9b4ff7 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSortedNumericDocValuesRangeIterator.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSortedNumericDocValuesRangeIterator.java
@@ -21,6 +21,7 @@ import java.util.ArrayList;
import java.util.List;
import org.apache.lucene.index.DocValuesSkipper;
import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.util.FixedBitSet;
/**
* Tests {@link DocValuesRangeIterator#forRange(SortedNumericDocValues, DocValuesSkipper, long,
@@ -95,7 +96,9 @@ public class TestSortedNumericDocValuesRangeIterator extends BaseDocValuesSkippe
@Override
public boolean advanceExact(int target) throws IOException {
- throw new UnsupportedOperationException();
+ doc = target;
+ valueIdx = 0;
+ return docHasValue(target);
}
@Override
@@ -156,6 +159,14 @@ public class TestSortedNumericDocValuesRangeIterator extends BaseDocValuesSkippe
return DocValuesRangeIterator.forRange(values, skipper, QUERY_MIN, QUERY_MAX);
}
+ private static FixedBitSet expectedBitSet() {
+ FixedBitSet bitSet = new FixedBitSet(2048);
+ for (int doc : expectedMatches()) {
+ bitSet.set(doc);
+ }
+ return bitSet;
+ }
+
// --- Correctness: all matching docs are found and no false positives ---
public void testCorrectResultsSingleLevel() throws IOException {
@@ -166,6 +177,24 @@ public class TestSortedNumericDocValuesRangeIterator extends BaseDocValuesSkippe
assertEquals(expectedMatches(), collectMatches(createIterator(true)));
}
+ public void testTwoPhaseIntoBitSetMatchesExpected() throws IOException {
+ DocValuesRangeIterator iterator = createIterator(true);
+ assertEquals(0, iterator.approximation().nextDoc());
+
+ FixedBitSet actual = new FixedBitSet(2048);
+ iterator.intoBitSet(2048, actual, 0);
+
+ assertEquals(expectedBitSet(), actual);
+ }
+
+ public void testDefaultRangeIntoBitSetMatchesExpected() throws IOException {
+ SortedNumericDocValues values = sortedNumericDocValues(QUERY_MIN, QUERY_MAX);
+ FixedBitSet actual = new FixedBitSet(2048);
+ values.rangeIntoBitSet(0, 2048, QUERY_MIN, QUERY_MAX, actual, 0);
+
+ assertEquals(expectedBitSet(), actual);
+ }
+
// --- Multi-value specific behavior ---
public void testMatchOnFirstValueInRange() throws IOException {