You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2026/05/18 13:15:25 UTC
(lucene) branch main updated: Add a BulkScorer for queries that match a dense range (#16080)
This is an automated email from the ASF dual-hosted git repository.
iverase 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 ff110e83c79 Add a BulkScorer for queries that match a dense range (#16080)
ff110e83c79 is described below
commit ff110e83c79fc1519b68b5e1735c32456112c99a
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Mon May 18 14:15:17 2026 +0100
Add a BulkScorer for queries that match a dense range (#16080)
---
lucene/CHANGES.txt | 2 +
.../apache/lucene/document/RangeBulkScorer.java | 98 ++++++++++++++
.../document/SortedSetDocValuesRangeQuery.java | 6 +-
.../document/SortedSkipperScorerSupplier.java | 92 +++++++++----
.../document/TestRangeFilteredBulkScorer.java | 144 +++++++++++++++++++++
5 files changed, 312 insertions(+), 30 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 2bc5b8abee6..52748a51f9f 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -388,6 +388,8 @@ Optimizations
* GITHUB#16077: Added efficient implementations if the method #docIDRunEnd for the iterators used
by RoaringDocIdSet. (Ignacio Vera)
+* GITHUB#16080: Add a BulkScrer implementation spcialized for filters that match dense ranges. (Ignacio Vera)
+
Bug Fixes
---------------------
* GITHUB#15754: Fix HTMLStripCharFilter to prevent tags from incorrectly consuming subsequent
diff --git a/lucene/core/src/java/org/apache/lucene/document/RangeBulkScorer.java b/lucene/core/src/java/org/apache/lucene/document/RangeBulkScorer.java
new file mode 100644
index 00000000000..1a62cdffd57
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/document/RangeBulkScorer.java
@@ -0,0 +1,98 @@
+/*
+ * 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.document;
+
+import java.io.IOException;
+import java.util.Objects;
+import org.apache.lucene.search.BulkScorer;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.LeafCollector;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.util.Bits;
+
+/**
+ * A {@link BulkScorer} that restricts collection to the half-open doc ID interval {@code [minDocID,
+ * maxDocID)}.
+ *
+ * <p>Typical use is a constant-score query backed by {@link DocIdSetIterator#range}, where
+ * collecting the whole interval in one or few {@code collectRange} calls is cheaper than per-doc
+ * {@link LeafCollector#collect}.
+ */
+final class RangeBulkScorer extends BulkScorer {
+ private final int minDocID;
+ private final int maxDocID;
+ private final Scorer scorer;
+ private final DocIdSetIterator iterator;
+
+ /** Creates a bulk scorer that collects only within {@code [minDocID, maxDocID)}. */
+ public RangeBulkScorer(Scorer scorer, int minDocID, int maxDocID) {
+ if (minDocID >= maxDocID) {
+ throw new IllegalArgumentException("minDocID must be less than maxDocID");
+ }
+ this.minDocID = minDocID;
+ this.maxDocID = maxDocID;
+ this.scorer = Objects.requireNonNull(scorer);
+ this.iterator = scorer.iterator();
+ }
+
+ @Override
+ public int score(LeafCollector collector, Bits acceptDocs, int min, int max) throws IOException {
+ collector.setScorer(scorer);
+ DocIdSetIterator competitiveIterator = collector.competitiveIterator();
+ if (competitiveIterator != null) {
+ if (competitiveIterator.docID() > min) {
+ min = competitiveIterator.docID();
+ // The competitive iterator may not match any docs in the range.
+ min = Math.min(min, max);
+ }
+ }
+ if (max <= minDocID) {
+ iterator.advance(minDocID);
+ } else if (min >= maxDocID) {
+ iterator.advance(maxDocID);
+ } else {
+ int filteredMin = Math.max(min, minDocID);
+ final int filteredMax = Math.min(max, maxDocID);
+ iterator.advance(filteredMin);
+ if (acceptDocs == null) {
+ collector.collectRange(filteredMin, filteredMax);
+ } else {
+ int rangeStart = -1;
+ for (int doc = filteredMin; doc < filteredMax; doc++) {
+ if (acceptDocs.get(doc)) {
+ if (rangeStart < 0) {
+ rangeStart = doc;
+ }
+ } else if (rangeStart >= 0) {
+ collector.collectRange(rangeStart, doc);
+ rangeStart = -1;
+ }
+ }
+ if (rangeStart >= 0) {
+ collector.collectRange(rangeStart, filteredMax);
+ }
+ }
+ iterator.advance(filteredMax);
+ }
+ return iterator.docID();
+ }
+
+ @Override
+ public long cost() {
+ return maxDocID - minDocID;
+ }
+}
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 66acf63277a..4cc497aca15 100644
--- a/lucene/core/src/java/org/apache/lucene/document/SortedSetDocValuesRangeQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/SortedSetDocValuesRangeQuery.java
@@ -126,7 +126,7 @@ final class SortedSetDocValuesRangeQuery extends Query {
&& skipper != null
&& (primarySortField = densePrimarySort(context.reader(), skipper)) != null) {
return getScorerSupplierFromDensePrimarySort(
- context, singleton, values, skipper, primarySortField);
+ singleton, values, skipper, primarySortField);
}
// implement ScorerSupplier, since we do some expensive stuff to make a scorer
return new ConstantScoreScorerSupplier(score(), scoreMode, context.reader().maxDoc()) {
@@ -167,13 +167,11 @@ final class SortedSetDocValuesRangeQuery extends Query {
}
private ScorerSupplier getScorerSupplierFromDensePrimarySort(
- LeafReaderContext context,
SortedDocValues singleton,
SortedSetDocValues values,
DocValuesSkipper skipper,
SortField sortField) {
- return new SortedSkipperScorerSupplier(
- skipper, sortField, score(), scoreMode, context.reader().maxDoc()) {
+ return new SortedSkipperScorerSupplier(skipper, sortField, score(), scoreMode) {
long minOrd = -1, maxOrd = -1;
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/document/SortedSkipperScorerSupplier.java b/lucene/core/src/java/org/apache/lucene/document/SortedSkipperScorerSupplier.java
index d840a75c8fe..2100f94b265 100644
--- a/lucene/core/src/java/org/apache/lucene/document/SortedSkipperScorerSupplier.java
+++ b/lucene/core/src/java/org/apache/lucene/document/SortedSkipperScorerSupplier.java
@@ -20,10 +20,15 @@ import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.function.LongPredicate;
import org.apache.lucene.index.DocValuesSkipper;
-import org.apache.lucene.search.ConstantScoreScorerSupplier;
+import org.apache.lucene.search.BulkScorer;
+import org.apache.lucene.search.ConstantScoreScorer;
import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.LeafCollector;
import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
import org.apache.lucene.search.SortField;
+import org.apache.lucene.util.Bits;
/**
* Constant-score supplier that uses a {@link DocValuesSkipper} to approximate the document interval
@@ -35,10 +40,12 @@ import org.apache.lucene.search.SortField;
* from that doc to the first document whose value satisfies the appropriate comparison, producing a
* tight {@link DocIdSetIterator#range} iterator.
*/
-abstract class SortedSkipperScorerSupplier extends ConstantScoreScorerSupplier {
+abstract class SortedSkipperScorerSupplier extends ScorerSupplier {
private final DocValuesSkipper skipper;
private final SortField sortField;
+ private final ScoreMode scoreMode;
+ private final float score;
private int skipperMinDocId = -1, skipperMaxDocId = -1;
private boolean skipperMinDocIdExact = false, skipperMaxDocIdExact = false;
@@ -47,13 +54,12 @@ abstract class SortedSkipperScorerSupplier extends ConstantScoreScorerSupplier {
* @param sortField leaf primary sort; {@link SortField#getReverse()} controls how range endpoints
* map to ordinal or value predicates
* @param score constant score assigned to hits
- * @param scoreMode scoring mode passed to {@link ConstantScoreScorerSupplier}
- * @param maxDoc exclusive upper bound of doc IDs on this leaf (typically {@link
- * org.apache.lucene.index.LeafReader#maxDoc()})
+ * @param scoreMode scoring mode passed to {@link RangeBulkScorer}
*/
SortedSkipperScorerSupplier(
- DocValuesSkipper skipper, SortField sortField, float score, ScoreMode scoreMode, int maxDoc) {
- super(score, scoreMode, maxDoc);
+ DocValuesSkipper skipper, SortField sortField, float score, ScoreMode scoreMode) {
+ this.scoreMode = scoreMode;
+ this.score = score;
this.skipper = skipper;
this.sortField = sortField;
}
@@ -75,26 +81,24 @@ abstract class SortedSkipperScorerSupplier extends ConstantScoreScorerSupplier {
protected abstract int nextDoc(int startDocID, LongPredicate predicate) throws IOException;
@Override
- public DocIdSetIterator iterator(long leadCost) throws IOException {
- if (skipperMinDocId == -1) {
- computeSkipperDocIds();
- }
- long minOrd = getLowerValue();
- long maxOrd = getUpperValue();
- final int minDocID;
- final int maxDocID;
- if (sortField.getReverse()) {
- minDocID =
- skipperMinDocIdExact ? skipperMinDocId : nextDoc(skipperMinDocId, l -> l <= maxOrd);
- maxDocID = skipperMaxDocIdExact ? skipperMaxDocId : nextDoc(skipperMaxDocId, l -> l < minOrd);
- } else {
- minDocID =
- skipperMinDocIdExact ? skipperMinDocId : nextDoc(skipperMinDocId, l -> l >= minOrd);
- maxDocID = skipperMaxDocIdExact ? skipperMaxDocId : nextDoc(skipperMaxDocId, l -> l > maxOrd);
+ public final Scorer get(long leadCost) throws IOException {
+ DocIdRange range = range();
+ DocIdSetIterator iterator =
+ range.minDocID() == range.maxDocID()
+ ? DocIdSetIterator.empty()
+ : DocIdSetIterator.range(range.minDocID(), range.maxDocID());
+ return new ConstantScoreScorer(score, scoreMode, iterator);
+ }
+
+ @Override
+ public final BulkScorer bulkScorer() throws IOException {
+ DocIdRange range = range();
+ if (range.minDocID() == range.maxDocID()) {
+ return emptyBulkScorer();
}
- return minDocID == maxDocID
- ? DocIdSetIterator.empty()
- : DocIdSetIterator.range(minDocID, maxDocID);
+ DocIdSetIterator iterator = DocIdSetIterator.range(range.minDocID(), range.maxDocID());
+ return new RangeBulkScorer(
+ new ConstantScoreScorer(score, scoreMode, iterator), range.minDocID(), range.maxDocID());
}
@Override
@@ -114,6 +118,26 @@ abstract class SortedSkipperScorerSupplier extends ConstantScoreScorerSupplier {
return skipperMaxDocId - skipperMinDocId + skipper.docCount(0);
}
+ private DocIdRange range() throws IOException {
+ if (skipperMinDocId == -1) {
+ computeSkipperDocIds();
+ }
+ long minOrd = getLowerValue();
+ long maxOrd = getUpperValue();
+ final int minDocID;
+ final int maxDocID;
+ if (sortField.getReverse()) {
+ minDocID =
+ skipperMinDocIdExact ? skipperMinDocId : nextDoc(skipperMinDocId, l -> l <= maxOrd);
+ maxDocID = skipperMaxDocIdExact ? skipperMaxDocId : nextDoc(skipperMaxDocId, l -> l < minOrd);
+ } else {
+ minDocID =
+ skipperMinDocIdExact ? skipperMinDocId : nextDoc(skipperMinDocId, l -> l >= minOrd);
+ maxDocID = skipperMaxDocIdExact ? skipperMaxDocId : nextDoc(skipperMaxDocId, l -> l > maxOrd);
+ }
+ return new DocIdRange(minDocID, maxDocID);
+ }
+
private void computeSkipperDocIds() throws IOException {
long minOrd = getLowerValue();
long maxOrd = getUpperValue();
@@ -176,4 +200,20 @@ abstract class SortedSkipperScorerSupplier extends ConstantScoreScorerSupplier {
}
}
}
+
+ record DocIdRange(int minDocID, int maxDocID) {}
+
+ private static BulkScorer emptyBulkScorer() {
+ return new BulkScorer() {
+ @Override
+ public int score(LeafCollector collector, Bits acceptDocs, int min, int max) {
+ return DocIdSetIterator.NO_MORE_DOCS;
+ }
+
+ @Override
+ public long cost() {
+ return 0;
+ }
+ };
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestRangeFilteredBulkScorer.java b/lucene/core/src/test/org/apache/lucene/document/TestRangeFilteredBulkScorer.java
new file mode 100644
index 00000000000..3e915365f02
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/document/TestRangeFilteredBulkScorer.java
@@ -0,0 +1,144 @@
+/*
+ * 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.document;
+
+import java.util.ArrayList;
+import java.util.List;
+import org.apache.lucene.search.BulkScorer;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.LeafCollector;
+import org.apache.lucene.search.Scorable;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.FixedBitSet;
+
+public class TestRangeFilteredBulkScorer extends LuceneTestCase {
+
+ public void testCollectRangeClipsToQueryInterval() throws Exception {
+ BulkScorer bs = newBulkScorer(20, 80);
+ var collector = new RangeRecordingCollector();
+ int next = bs.score(collector, null, 0, 100);
+ assertCollectedRanges(List.of(new int[] {20, 80}), collector.ranges);
+ assertTrue(next >= 100);
+ }
+
+ public void testScoreWhenWindowEndsBeforeRange() throws Exception {
+ BulkScorer bs = newBulkScorer(50, 100);
+ var collector = new RangeRecordingCollector();
+ int next = bs.score(collector, null, 0, 40);
+ assertTrue(collector.ranges.isEmpty());
+ assertEquals(50, next);
+ }
+
+ public void testScoreWhenWindowStartsAtOrAfterRangeEnd() throws Exception {
+ BulkScorer bs = newBulkScorer(10, 50);
+ var collector = new RangeRecordingCollector();
+ int next = bs.score(collector, null, 55, 200);
+ assertTrue(collector.ranges.isEmpty());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, next);
+ }
+
+ public void testCost() {
+ assertEquals(30L, newBulkScorer(10, 40).cost());
+ }
+
+ public void testCompetitiveIteratorRaisesMin() throws Exception {
+ BulkScorer bs = newBulkScorer(10, 60);
+ var collector = new RangeRecordingCollector();
+ DocIdSetIterator competitive = DocIdSetIterator.range(25, 100);
+ assertEquals(25, competitive.nextDoc());
+ collector.setCompetitiveIterator(competitive);
+
+ int next = bs.score(collector, null, 0, 100);
+ assertCollectedRanges(List.of(new int[] {25, 60}), collector.ranges);
+ assertTrue(next >= 100);
+ }
+
+ public void testAcceptDocsAllLiveMatchesNoAcceptDocs() throws Exception {
+ BulkScorer bs = newBulkScorer(10, 40);
+ var bits = new FixedBitSet(200);
+ bits.set(0, 200);
+ var collector = new RangeRecordingCollector();
+ int next = bs.score(collector, bits, 0, 100);
+ assertCollectedRanges(List.of(new int[] {10, 40}), collector.ranges);
+ assertTrue(next >= 100);
+ }
+
+ public void testAcceptDocsSplitsAroundDeletedDoc() throws Exception {
+ BulkScorer bs = newBulkScorer(10, 20);
+ var bits = new FixedBitSet(30);
+ bits.set(10, 20);
+ bits.clear(15);
+
+ var collector = new RangeRecordingCollector();
+ bs.score(collector, bits, 0, 100);
+ assertCollectedRanges(List.of(new int[] {10, 15}, new int[] {16, 20}), collector.ranges);
+ }
+
+ public void testAcceptDocsNoDocsLiveInWindow() throws Exception {
+ BulkScorer bs = newBulkScorer(10, 30);
+ var bits = new FixedBitSet(50);
+ // nothing set => all deleted
+
+ var collector = new RangeRecordingCollector();
+ int next = bs.score(collector, bits, 0, 100);
+ assertTrue(collector.ranges.isEmpty());
+ assertTrue(next >= 100);
+ }
+
+ private static RangeBulkScorer newBulkScorer(int rangeMin, int rangeMaxExclusive) {
+ var iterator = DocIdSetIterator.range(rangeMin, rangeMaxExclusive);
+ var scorer = new ConstantScoreScorer(1f, ScoreMode.COMPLETE, iterator);
+ return new RangeBulkScorer(scorer, rangeMin, rangeMaxExclusive);
+ }
+
+ /** Records {@link LeafCollector#collectRange} calls as {@code [min inclusive, max exclusive)}. */
+ private static class RangeRecordingCollector implements LeafCollector {
+ final List<int[]> ranges = new ArrayList<>();
+ private DocIdSetIterator competitiveIterator;
+
+ void setCompetitiveIterator(DocIdSetIterator competitiveIterator) {
+ this.competitiveIterator = competitiveIterator;
+ }
+
+ @Override
+ public void setScorer(Scorable scorer) {}
+
+ @Override
+ public void collect(int doc) {
+ fail("collect should not be used when testing collectRange path");
+ }
+
+ @Override
+ public void collectRange(int min, int max) {
+ ranges.add(new int[] {min, max});
+ }
+
+ @Override
+ public DocIdSetIterator competitiveIterator() {
+ return competitiveIterator;
+ }
+ }
+
+ private static void assertCollectedRanges(List<int[]> expected, List<int[]> actual) {
+ assertEquals(expected.size(), actual.size());
+ for (int i = 0; i < expected.size(); i++) {
+ assertArrayEquals(expected.get(i), actual.get(i));
+ }
+ }
+}