You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ji...@apache.org on 2026/06/05 17:37:55 UTC
(lucene) branch main updated: Batch sorted-set doc-values range queries (#16172)
This is an automated email from the ASF dual-hosted git repository.
jimczi 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 b039e121eb2 Batch sorted-set doc-values range queries (#16172)
b039e121eb2 is described below
commit b039e121eb20b84eb62247f085759186c16e456e
Author: Costin Leau <co...@users.noreply.github.com>
AuthorDate: Fri Jun 5 10:37:48 2026 -0700
Batch sorted-set doc-values range queries (#16172)
Route skip-indexed sorted and sorted-set range queries through the
two-phase DocValuesRangeIterator and bulk-evaluate its blocks in an
ordinal-aware intoBitSet override, instead of a standalone iterator.
This aligns the optimization with the single two-phase strategy for
doc-values range queries: YES runs are set in one shot, YES_IF_PRESENT
runs are marked by value presence, and only MAYBE runs confirm the
ordinal predicate per doc. The bulk scorer unwraps the two-phase
iterator and drives positioning, so no separate DocIdSetIterator is
needed. Arbitrary ordinal sets (alwaysCheckPredicate) keep the per-doc
fallback.
---
lucene/CHANGES.txt | 3 +
.../jmh/SortedSetDocValuesRangeQueryBenchmark.java | 188 +++++++++++++++++++++
.../document/SortedSetDocValuesRangeQuery.java | 4 +
.../lucene/search/DocValuesRangeIterator.java | 61 ++++++-
.../search/TestDocValuesOrdinalRangeIterator.java | 39 +++++
.../apache/lucene/search/TestDocValuesQueries.java | 67 ++++++++
6 files changed, 359 insertions(+), 3 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index d58db69ce48..4bdaf4c198a 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -156,6 +156,9 @@ Optimizations
* GITHUB#15597, GITHUB#15777: Reduce memory usage of NeighborArray (Viliam Durina)
+* GITHUB#16172: Bulk-evaluate skip-indexed sorted and sorted-set doc-values range queries via a block-aware
+ DocValuesRangeIterator#intoBitSet. (Costin Leau)
+
Bug Fixes
---------------------
* GITHUB#14049: Randomize KNN codec params in RandomCodec. Fixes scalar quantization div-by-zero
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedSetDocValuesRangeQueryBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedSetDocValuesRangeQueryBenchmark.java
new file mode 100644
index 00000000000..b0a6bf08ea9
--- /dev/null
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/SortedSetDocValuesRangeQueryBenchmark.java
@@ -0,0 +1,188 @@
+/*
+ * 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.Comparator;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.Stream;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.LongPoint;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.search.ConstantScoreScorerSupplier;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.MMapDirectory;
+import org.apache.lucene.util.BytesRef;
+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 {@link SortedSetDocValuesField#newSlowRangeQuery} when skip-indexed sorted-set doc
+ * values route through a two-phase {@link DocValuesRangeIterator} (whose {@code intoBitSet}
+ * bulk-evaluates skip blocks) and dense bulk scoring.
+ */
+@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 SortedSetDocValuesRangeQueryBenchmark {
+
+ private static final String FIELD = "dv";
+ private static final int VALUE_MODULUS = 1024;
+ private static final long RANGE_MIN = 256;
+ private static final long RANGE_MAX = 511;
+
+ private Directory dir;
+ private IndexReader reader;
+ private Path path;
+ private Query query;
+
+ @State(Scope.Benchmark)
+ public static class Params {
+ @Param({"100000", "1000000"})
+ public int docCount;
+
+ @Param({"1", "2"})
+ public int valuesPerDoc;
+ }
+
+ @Setup(Level.Trial)
+ public void setup(Params params) throws Exception {
+ path = Files.createTempDirectory("sortedSetDvRangeBench");
+ dir = MMapDirectory.open(path);
+
+ IndexWriterConfig iwc = new IndexWriterConfig();
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (int i = 0; i < params.docCount; i++) {
+ Document doc = new Document();
+ addSortedSetValue(doc, i % VALUE_MODULUS);
+ if (params.valuesPerDoc == 2) {
+ addSortedSetValue(doc, VALUE_MODULUS + (i % VALUE_MODULUS));
+ }
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ reader = DirectoryReader.open(w);
+ }
+
+ query =
+ SortedSetDocValuesField.newSlowRangeQuery(
+ FIELD, encodedValue(RANGE_MIN), encodedValue(RANGE_MAX), true, true);
+
+ verifyBenchmarkPath(params);
+ }
+
+ private void verifyBenchmarkPath(Params params) throws IOException {
+ IndexSearcher searcher = new IndexSearcher(reader);
+ LeafReaderContext leaf = reader.leaves().get(0);
+ if (leaf.reader().getDocValuesSkipper(FIELD) == null) {
+ throw new IllegalStateException("benchmark requires a doc-values skipper");
+ }
+ boolean singleton =
+ DocValues.unwrapSingleton(DocValues.getSortedSet(leaf.reader(), FIELD)) != null;
+ if (singleton != (params.valuesPerDoc == 1)) {
+ throw new IllegalStateException(
+ "unexpected sorted-set singleton state for valuesPerDoc=" + params.valuesPerDoc);
+ }
+
+ Weight weight = query.createWeight(searcher, ScoreMode.COMPLETE_NO_SCORES, 1f);
+ ScorerSupplier scorerSupplier = weight.scorerSupplier(leaf);
+ if (scorerSupplier instanceof ConstantScoreScorerSupplier == false) {
+ throw new IllegalStateException(
+ "expected ConstantScoreScorerSupplier but got " + scorerSupplier.getClass().getName());
+ }
+ DocIdSetIterator iterator =
+ ((ConstantScoreScorerSupplier) scorerSupplier).iterator(Long.MAX_VALUE);
+ TwoPhaseIterator twoPhase = TwoPhaseIterator.unwrap(iterator);
+ if (twoPhase instanceof DocValuesRangeIterator == false) {
+ throw new IllegalStateException(
+ "expected a two-phase DocValuesRangeIterator but got "
+ + (twoPhase == null ? iterator.getClass().getName() : twoPhase.getClass().getName()));
+ }
+ String bulkScorerClass = scorerSupplier.bulkScorer().getClass().getName();
+ if (bulkScorerClass.endsWith(".DenseConjunctionBulkScorer") == false) {
+ throw new IllegalStateException(
+ "expected DenseConjunctionBulkScorer but got " + bulkScorerClass);
+ }
+ }
+
+ private static void addSortedSetValue(Document doc, long value) {
+ doc.add(SortedSetDocValuesField.indexedField(FIELD, encodedValue(value)));
+ }
+
+ private static BytesRef encodedValue(long value) {
+ byte[] encoded = new byte[Long.BYTES];
+ LongPoint.encodeDimension(value, encoded, 0);
+ return new BytesRef(encoded);
+ }
+
+ @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 searchSortedSetRange(Params params) throws IOException {
+ IndexSearcher searcher = new IndexSearcher(reader);
+ return searcher.count(query);
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/document/SortedSetDocValuesRangeQuery.java b/lucene/core/src/java/org/apache/lucene/document/SortedSetDocValuesRangeQuery.java
index f22fd33f68f..3022ade0f85 100644
--- a/lucene/core/src/java/org/apache/lucene/document/SortedSetDocValuesRangeQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/SortedSetDocValuesRangeQuery.java
@@ -151,6 +151,10 @@ final class SortedSetDocValuesRangeQuery extends Query {
return DocIdSetIterator.all(skipper.docCount());
}
+ // A single two-phase iterator covers every density: its approximation rides the
+ // skipper (no over-scan) and its intoBitSet bulk-evaluates blocks (YES runs set at
+ // once, YES_IF_PRESENT runs marked by presence, MAYBE runs confirmed per doc). The bulk
+ // scorer unwraps it and picks the right strategy from there.
if (singleton != null) {
return TwoPhaseIterator.asDocIdSetIterator(
DocValuesRangeIterator.forOrdinalRange(singleton, skipper, minOrd, maxOrd));
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 ff9353a621f..3f22484ef91 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
@@ -338,9 +338,17 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
@Override
public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
if (numericValues == null) {
- // Generic doc values: confirm each candidate one doc at a time (the TwoPhaseIterator
- // default). Only single-valued numeric fields can be range-evaluated block at a time.
- super.intoBitSet(upTo, bitSet, offset);
+ 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;
}
while (blockIterator.docID() < upTo) {
@@ -373,6 +381,53 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
}
}
+ /**
+ * 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.
+ 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);
+ }
+ }
+ }
+ }
+ blockIterator.advance(blockEnd);
+ }
+ }
+
@Override
public float matchCost() {
return matchCost;
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalRangeIterator.java b/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalRangeIterator.java
index 11df66ef765..fe891565687 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalRangeIterator.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestDocValuesOrdinalRangeIterator.java
@@ -23,6 +23,7 @@ import org.apache.lucene.index.DocValuesSkipper;
import org.apache.lucene.index.SortedDocValues;
import org.apache.lucene.index.SortedSetDocValues;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.FixedBitSet;
/**
* Tests {@link DocValuesRangeIterator#forOrdinalRange} for both single-valued ({@link
@@ -51,6 +52,30 @@ public class TestDocValuesOrdinalRangeIterator extends BaseDocValuesSkipperTests
return matches;
}
+ /**
+ * Drives {@link DocValuesRangeIterator#intoBitSet} over the whole doc space and asserts the bulk
+ * result matches the documents a per-doc {@link TwoPhaseIterator#matches()} linear scan would
+ * produce (the {@code expected} list, computed independently from the mock's ordinals).
+ */
+ private static void assertIntoBitSetMatchesLinearScan(
+ DocValuesRangeIterator iter, List<Integer> expectedMatches) throws IOException {
+ DocIdSetIterator approx = iter.approximation();
+ assertEquals(0, approx.nextDoc());
+
+ FixedBitSet actual = new FixedBitSet(2048);
+ iter.intoBitSet(2048, actual, 0);
+ // intoBitSet must leave the approximation on the first doc >= upTo (exhausted here).
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, approx.docID());
+
+ FixedBitSet expected = new FixedBitSet(2048);
+ for (int doc : expectedMatches) {
+ expected.set(doc);
+ }
+ assertEquals(expected.cardinality(), actual.cardinality());
+ expected.xor(actual);
+ assertEquals(0, expected.cardinality());
+ }
+
// ==========================================================================
// SortedDocValues (single-valued ordinals)
// ==========================================================================
@@ -236,6 +261,13 @@ public class TestDocValuesOrdinalRangeIterator extends BaseDocValuesSkipperTests
assertEquals(1089, iter.docIDRunEnd());
}
+ // --- SortedDocValues: intoBitSet bulk evaluation ---
+
+ public void testSortedDocValuesIntoBitSetMatchesLinearScan() throws IOException {
+ assertIntoBitSetMatchesLinearScan(
+ createSortedDocValuesIterator(true), expectedSingleOrdMatches());
+ }
+
// ==========================================================================
// SortedSetDocValues (multi-valued ordinals)
// ==========================================================================
@@ -503,4 +535,11 @@ public class TestDocValuesOrdinalRangeIterator extends BaseDocValuesSkipperTests
assertEquals(SkipBlockRangeIterator.Match.YES_IF_PRESENT, approx.getMatch());
assertEquals(1089, iter.docIDRunEnd());
}
+
+ // --- SortedSetDocValues: intoBitSet bulk evaluation ---
+
+ public void testSortedSetDocValuesIntoBitSetMatchesLinearScan() throws IOException {
+ assertIntoBitSetMatchesLinearScan(
+ createSortedSetDocValuesIterator(true), expectedMultiOrdMatches());
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestDocValuesQueries.java b/lucene/core/src/test/org/apache/lucene/search/TestDocValuesQueries.java
index 355de1138a2..a932dc0061c 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestDocValuesQueries.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestDocValuesQueries.java
@@ -41,7 +41,10 @@ import org.apache.lucene.document.SortedDocValuesField;
import org.apache.lucene.document.SortedNumericDocValuesField;
import org.apache.lucene.document.SortedSetDocValuesField;
import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.DocValues;
import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.IndexableField;
import org.apache.lucene.index.LeafReaderContext;
@@ -308,6 +311,70 @@ public class TestDocValuesQueries extends LuceneTestCaseJupiter {
doTestDuelPointRangeSortedRangeQuery(random, true, 3, true);
}
+ @Test
+ public void testSortedSetRangeQueryUsesTwoPhaseRangeIteratorWithSkipper() throws IOException {
+ assertSortedSetRangeQueryUsesTwoPhaseRangeIteratorWithSkipper(false);
+ assertSortedSetRangeQueryUsesTwoPhaseRangeIteratorWithSkipper(true);
+ }
+
+ private void assertSortedSetRangeQueryUsesTwoPhaseRangeIteratorWithSkipper(boolean multiValued)
+ throws IOException {
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig config = new IndexWriterConfig().setCodec(getCodec(8));
+ try (IndexWriter iw = new IndexWriter(dir, config)) {
+ for (int i = 0; i < 512; i++) {
+ Document doc = new Document();
+ addSortedSetValue(doc, i % 100);
+ if (multiValued) {
+ addSortedSetValue(doc, 100 + (i % 100));
+ }
+ iw.addDocument(doc);
+ }
+ iw.forceMerge(1);
+
+ try (IndexReader reader = DirectoryReader.open(iw)) {
+ IndexSearcher searcher = newSearcher(reader, false);
+ byte[] encodedMin = new byte[Long.BYTES];
+ byte[] encodedMax = new byte[Long.BYTES];
+ LongPoint.encodeDimension(20, encodedMin, 0);
+ LongPoint.encodeDimension(40, encodedMax, 0);
+ Query query =
+ SortedSetDocValuesField.newSlowRangeQuery(
+ "dv", newBytesRef(encodedMin), newBytesRef(encodedMax), true, true);
+
+ LeafReaderContext leaf = reader.leaves().get(0);
+ assertSame(query, searcher.rewrite(query));
+ assertNull(leaf.reader().getMetaData().sort());
+ assertNotNull(leaf.reader().getDocValuesSkipper("dv"));
+ assertEquals(
+ multiValued == false,
+ DocValues.unwrapSingleton(DocValues.getSortedSet(leaf.reader(), "dv")) != null);
+
+ Weight weight = query.createWeight(searcher, ScoreMode.COMPLETE_NO_SCORES, 1f);
+ ScorerSupplier scorerSupplier = weight.scorerSupplier(leaf);
+
+ assertNotNull(scorerSupplier);
+ assertTrue(
+ scorerSupplier.getClass().getName(),
+ scorerSupplier instanceof ConstantScoreScorerSupplier);
+ DocIdSetIterator iterator =
+ ((ConstantScoreScorerSupplier) scorerSupplier).iterator(Long.MAX_VALUE);
+ // The skipper route exposes a two-phase DocValuesRangeIterator whose intoBitSet
+ // bulk-evaluates skip blocks, rather than a per-doc plain iterator.
+ TwoPhaseIterator twoPhase = TwoPhaseIterator.unwrap(iterator);
+ assertNotNull(iterator.getClass().getName(), twoPhase);
+ assertTrue(twoPhase.getClass().getName(), twoPhase instanceof DocValuesRangeIterator);
+ }
+ }
+ }
+ }
+
+ private void addSortedSetValue(Document doc, long value) {
+ byte[] encoded = new byte[Long.BYTES];
+ LongPoint.encodeDimension(value, encoded, 0);
+ doc.add(SortedSetDocValuesField.indexedField("dv", newBytesRef(encoded)));
+ }
+
@Test
public void testDuelPointRangeSortedRangeQuery(Random random) throws IOException {
doTestDuelPointRangeSortedRangeQuery(random, false, 1, false);