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));
+    }
+  }
+}