You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2025/03/10 17:45:12 UTC
(lucene) branch branch_10x updated: Make Lucene better at skipping long runs of matches. (#14312)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_10x by this push:
new 864ad5d787e Make Lucene better at skipping long runs of matches. (#14312)
864ad5d787e is described below
commit 864ad5d787ebc673a7e5cb5bf9fb7509c1364975
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Mon Mar 10 18:08:14 2025 +0100
Make Lucene better at skipping long runs of matches. (#14312)
This is an attempt to resurrect #12194 in a (hopefully) better way. Now that
many queries run with `DenseConjunctionBulkScorer`, which scores windows of doc
IDs at a time, it becomes natural to skip clauses that have long runs of
matches by checking if they match the whole window.
This introduces the same `DocIdSetIterator#peekNextNonMatchingDocID()` API that
PR #12194 suggested, implements it in `DocIdSetIterator#all`, and uses it in
`DenseConjunctionBulkScorer` to skip clauses that match the whole window.
For better test coverage, `DenseConjunctionBulkScorer` was refactored to
require at least one iterator, which can be a `DocIdSetIterator#all` instance
if all docs match.
In follow-ups, we should look into supporting other queries that are likely to
have long runs of matches, in particular doc-value range queries on fields that
are part of the index sort and take advantage of a doc-value skipper.
Closes #11915
---
lucene/CHANGES.txt | 5 +
.../document/SortedNumericDocValuesRangeQuery.java | 3 +-
.../lucene/search/ConstantScoreScorerSupplier.java | 5 +
.../lucene/search/DenseConjunctionBulkScorer.java | 139 ++++++++------
.../org/apache/lucene/search/DocIdSetIterator.java | 30 +++
.../apache/lucene/search/MatchAllDocsQuery.java | 2 +-
.../lucene/search/MatchAllScorerSupplier.java | 58 ------
.../org/apache/lucene/search/PointRangeQuery.java | 2 +-
.../lucene/search/ReadAheadMatchAllDocsQuery.java | 16 +-
.../search/TestDenseConjunctionBulkScorer.java | 212 ++++++++++++++++++++-
.../apache/lucene/search/TestDocIdSetIterator.java | 19 ++
.../apache/lucene/search/TestSortOptimization.java | 2 +-
.../tests/search/AssertingLeafCollector.java | 9 +
.../lucene/tests/search/AssertingScorer.java | 8 +
14 files changed, 370 insertions(+), 140 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 400fb7abab7..5b39fac6cea 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -29,6 +29,11 @@ API Changes
* GITHUB#14237: Add utils for sandbox facets module for the most common tasks. (Egor Potemkin)
+* GITHUB#14312: Added DocIdSetIterator#docIDRunEnd to let iterators tell when
+ they have runs of matches. This is then leveraged by conjunctions to
+ automatically ignore clauses that have long runs of matches over these runs,
+ resulting in better efficiency. (Adrien Grand)
+
New Features
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/document/SortedNumericDocValuesRangeQuery.java b/lucene/core/src/java/org/apache/lucene/document/SortedNumericDocValuesRangeQuery.java
index 56e13ac8efd..409f31df2bb 100644
--- a/lucene/core/src/java/org/apache/lucene/document/SortedNumericDocValuesRangeQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/document/SortedNumericDocValuesRangeQuery.java
@@ -31,7 +31,6 @@ import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.search.DocValuesRangeIterator;
import org.apache.lucene.search.FieldExistsQuery;
import org.apache.lucene.search.IndexSearcher;
-import org.apache.lucene.search.MatchAllScorerSupplier;
import org.apache.lucene.search.MatchNoDocsQuery;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.QueryVisitor;
@@ -127,7 +126,7 @@ final class SortedNumericDocValuesRangeQuery extends Query {
&& skipper.minValue() >= lowerValue
&& skipper.maxValue() <= upperValue) {
- return new MatchAllScorerSupplier(score(), scoreMode, maxDoc);
+ return ConstantScoreScorerSupplier.matchAll(score(), scoreMode, maxDoc);
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/ConstantScoreScorerSupplier.java b/lucene/core/src/java/org/apache/lucene/search/ConstantScoreScorerSupplier.java
index 741f3c36307..749f50c706e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/ConstantScoreScorerSupplier.java
+++ b/lucene/core/src/java/org/apache/lucene/search/ConstantScoreScorerSupplier.java
@@ -27,6 +27,11 @@ import org.apache.lucene.search.Weight.DefaultBulkScorer;
*/
public abstract class ConstantScoreScorerSupplier extends ScorerSupplier {
+ /** Create a {@link ConstantScoreScorerSupplier} that matches all docs in [0, maxDoc). */
+ public static ConstantScoreScorerSupplier matchAll(float score, ScoreMode scoreMode, int maxDoc) {
+ return fromIterator(DocIdSetIterator.all(maxDoc), score, scoreMode, maxDoc);
+ }
+
/** Create a {@link ConstantScoreScorerSupplier} for the given iterator. */
public static ConstantScoreScorerSupplier fromIterator(
DocIdSetIterator iterator, float score, ScoreMode scoreMode, int maxDoc) {
diff --git a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
index 706b8d7da55..411699019c3 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
@@ -27,8 +27,6 @@ import org.apache.lucene.util.FixedBitSet;
* BulkScorer implementation of {@link ConjunctionScorer} that is specialized for dense clauses.
* Whenever sensible, it intersects clauses by loading their matches into a bit set and computing
* the intersection of clauses by and-ing these bit sets.
- *
- * <p>An empty set of iterators is interpreted as meaning that all docs in [0, maxDoc) match.
*/
final class DenseConjunctionBulkScorer extends BulkScorer {
@@ -46,12 +44,16 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
private final FixedBitSet windowMatches = new FixedBitSet(WINDOW_SIZE);
private final FixedBitSet clauseWindowMatches = new FixedBitSet(WINDOW_SIZE);
+ private final List<DocIdSetIterator> windowIterators = new ArrayList<>();
private final DocIdStreamView docIdStreamView = new DocIdStreamView();
private final RangeDocIdStream rangeDocIdStream = new RangeDocIdStream();
private final SingleIteratorDocIdStream singleIteratorDocIdStream =
new SingleIteratorDocIdStream();
DenseConjunctionBulkScorer(List<DocIdSetIterator> iterators, int maxDoc, float constantScore) {
+ if (iterators.isEmpty()) {
+ throw new IllegalArgumentException("Expected one or more iterators, got 0");
+ }
this.maxDoc = maxDoc;
iterators = new ArrayList<>(iterators);
iterators.sort(Comparator.comparingLong(DocIdSetIterator::cost));
@@ -63,6 +65,7 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
@Override
public int score(LeafCollector collector, Bits acceptDocs, int min, int max) throws IOException {
collector.setScorer(scorable);
+
List<DocIdSetIterator> iterators = this.iterators;
if (collector.competitiveIterator() != null) {
iterators = new ArrayList<>(iterators);
@@ -75,37 +78,24 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
max = Math.min(max, maxDoc);
- DocIdSetIterator lead = null;
- if (iterators.isEmpty() == false) {
- lead = iterators.get(0);
- if (lead.docID() < min) {
- min = lead.advance(min);
- }
+ DocIdSetIterator lead = iterators.get(0);
+ if (lead.docID() < min) {
+ min = lead.advance(min);
}
- if (min >= max) {
- return min >= maxDoc ? DocIdSetIterator.NO_MORE_DOCS : min;
- }
-
- int windowMax = min;
- do {
+ while (min < max) {
if (scorable.minCompetitiveScore > scorable.score) {
return DocIdSetIterator.NO_MORE_DOCS;
}
+ min = scoreWindow(collector, acceptDocs, iterators, min, max);
+ }
- int windowBase = lead == null ? windowMax : lead.docID();
- windowMax = (int) Math.min(max, (long) windowBase + WINDOW_SIZE);
- if (windowMax > windowBase) {
- scoreWindowUsingBitSet(collector, acceptDocs, iterators, windowBase, windowMax);
- }
- } while (windowMax < max);
-
- if (lead != null) {
+ if (lead.docID() > max) {
return lead.docID();
- } else if (windowMax >= maxDoc) {
+ } else if (max >= maxDoc) {
return DocIdSetIterator.NO_MORE_DOCS;
} else {
- return windowMax;
+ return max;
}
}
@@ -117,6 +107,65 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
}
}
+ private int scoreWindow(
+ LeafCollector collector, Bits acceptDocs, List<DocIdSetIterator> iterators, int min, int max)
+ throws IOException {
+
+ // Advance all iterators to the first doc that is greater than or equal to min. This is
+ // important as this is the only place where we can take advantage of a large gap between
+ // consecutive matches in any clause.
+ for (DocIdSetIterator iterator : iterators) {
+ if (iterator.docID() >= min) {
+ min = iterator.docID();
+ } else {
+ min = iterator.advance(min);
+ }
+ }
+ if (min >= max) {
+ return min;
+ }
+
+ if (acceptDocs == null) {
+ int minDocIDRunEnd = max;
+ for (DocIdSetIterator iterator : iterators) {
+ if (iterator.docID() > min) {
+ minDocIDRunEnd = min;
+ break;
+ } else {
+ minDocIDRunEnd = Math.min(minDocIDRunEnd, iterator.docIDRunEnd());
+ }
+ }
+
+ if (minDocIDRunEnd - min >= WINDOW_SIZE / 2) {
+ // We have a large range of doc IDs that all match.
+ rangeDocIdStream.from = min;
+ rangeDocIdStream.to = minDocIDRunEnd;
+ collector.collect(rangeDocIdStream);
+ return minDocIDRunEnd;
+ }
+ }
+
+ int bitsetWindowMax = (int) Math.min(max, (long) min + WINDOW_SIZE);
+
+ for (DocIdSetIterator it : iterators) {
+ if (it.docID() > min || it.docIDRunEnd() < bitsetWindowMax) {
+ windowIterators.add(it);
+ }
+ }
+
+ if (acceptDocs == null && windowIterators.size() == 1) {
+ // We have a range of doc IDs where all matches of an iterator are matches of the conjunction.
+ singleIteratorDocIdStream.iterator = windowIterators.get(0);
+ singleIteratorDocIdStream.from = min;
+ singleIteratorDocIdStream.to = bitsetWindowMax;
+ collector.collect(singleIteratorDocIdStream);
+ } else {
+ scoreWindowUsingBitSet(collector, acceptDocs, windowIterators, min, bitsetWindowMax);
+ }
+ windowIterators.clear();
+ return bitsetWindowMax;
+ }
+
private void scoreWindowUsingBitSet(
LeafCollector collector,
Bits acceptDocs,
@@ -128,26 +177,14 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
assert windowMatches.scanIsEmpty();
assert clauseWindowMatches.scanIsEmpty();
- if (acceptDocs == null) {
- if (iterators.isEmpty()) {
- // All docs in the range match.
- rangeDocIdStream.from = windowBase;
- rangeDocIdStream.to = windowMax;
- collector.collect(rangeDocIdStream);
- return;
- } else if (iterators.size() == 1) {
- singleIteratorDocIdStream.iterator = iterators.get(0);
- singleIteratorDocIdStream.from = windowBase;
- singleIteratorDocIdStream.to = windowMax;
- collector.collect(singleIteratorDocIdStream);
- return;
- }
- }
-
if (iterators.isEmpty()) {
+ // This happens if all clauses fully matched the window and there are deleted docs.
windowMatches.set(0, windowMax - windowBase);
} else {
DocIdSetIterator lead = iterators.get(0);
+ if (lead.docID() < windowBase) {
+ lead.advance(windowBase);
+ }
lead.intoBitSet(windowMax, windowMatches, windowBase);
}
@@ -199,28 +236,11 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
docIdStreamView.windowBase = windowBase;
collector.collect(docIdStreamView);
windowMatches.clear();
-
- // If another clause is more advanced than the leading clause then advance the leading clause,
- // it's important to take advantage of large gaps in the postings lists of other clauses.
- if (iterators.size() >= 2) {
- DocIdSetIterator lead = iterators.get(0);
- int maxOtherDocID = -1;
- for (int i = 1; i < iterators.size(); ++i) {
- maxOtherDocID = Math.max(maxOtherDocID, iterators.get(i).docID());
- }
- if (lead.docID() < maxOtherDocID) {
- lead.advance(maxOtherDocID);
- }
- }
}
@Override
public long cost() {
- if (iterators.isEmpty()) {
- return maxDoc;
- } else {
- return iterators.get(0).cost();
- }
+ return iterators.get(0).cost();
}
final class DocIdStreamView extends DocIdStream {
@@ -287,6 +307,9 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
// If the collector is just interested in the count, loading in a bit set and counting bits is
// often faster than incrementing a counter on every call to nextDoc().
assert windowMatches.scanIsEmpty();
+ if (iterator.docID() < from) {
+ iterator.advance(from);
+ }
iterator.intoBitSet(to, clauseWindowMatches, from);
int count = clauseWindowMatches.cardinality();
clauseWindowMatches.clear();
diff --git a/lucene/core/src/java/org/apache/lucene/search/DocIdSetIterator.java b/lucene/core/src/java/org/apache/lucene/search/DocIdSetIterator.java
index 07c4a4f95e3..abfc985b688 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DocIdSetIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DocIdSetIterator.java
@@ -97,6 +97,11 @@ public abstract class DocIdSetIterator {
advance(upTo);
}
}
+
+ @Override
+ public int docIDRunEnd() throws IOException {
+ return maxDoc;
+ }
};
}
@@ -151,6 +156,11 @@ public abstract class DocIdSetIterator {
advance(upTo);
}
}
+
+ @Override
+ public int docIDRunEnd() throws IOException {
+ return maxDoc;
+ }
};
}
@@ -258,4 +268,24 @@ public abstract class DocIdSetIterator {
bitSet.set(doc - offset);
}
}
+
+ /**
+ * Returns the end of the run of consecutive doc IDs that match this {@link DocIdSetIterator} and
+ * that contains the current {@link #docID()}, that is: one plus the last doc ID of the run.
+ *
+ * <ol>
+ * <li>The returned doc is greater than {@link #docID()}.
+ * <li>All docs in range {@code [docID(), docIDRunEnd())} match this iterator.
+ * <li>The current position of this iterator is not affected by calling {@link #docIDRunEnd()}.
+ * </ol>
+ *
+ * <p><b>Note</b>: It is illegal to call this method when the iterator is exhausted or not
+ * positioned.
+ *
+ * <p>The default implementation assumes runs of a single doc ID and returns {@link #docID()}) +
+ * 1.
+ */
+ public int docIDRunEnd() throws IOException {
+ return docID() + 1;
+ }
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/MatchAllDocsQuery.java b/lucene/core/src/java/org/apache/lucene/search/MatchAllDocsQuery.java
index e3eaa5aa5e7..6beeaf9589b 100644
--- a/lucene/core/src/java/org/apache/lucene/search/MatchAllDocsQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/MatchAllDocsQuery.java
@@ -32,7 +32,7 @@ public final class MatchAllDocsQuery extends Query {
@Override
public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
- return new MatchAllScorerSupplier(score(), scoreMode, context.reader().maxDoc());
+ return ConstantScoreScorerSupplier.matchAll(score(), scoreMode, context.reader().maxDoc());
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/search/MatchAllScorerSupplier.java b/lucene/core/src/java/org/apache/lucene/search/MatchAllScorerSupplier.java
deleted file mode 100644
index 61e08be5bdf..00000000000
--- a/lucene/core/src/java/org/apache/lucene/search/MatchAllScorerSupplier.java
+++ /dev/null
@@ -1,58 +0,0 @@
-/*
- * 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.search;
-
-import java.io.IOException;
-import java.util.Collections;
-
-/**
- * {@link ScorerSupplier} that matches all docs.
- *
- * @lucene.internal
- */
-public final class MatchAllScorerSupplier extends ScorerSupplier {
-
- private final float score;
- private final ScoreMode scoreMode;
- private final int maxDoc;
-
- /** Sole constructor */
- public MatchAllScorerSupplier(float score, ScoreMode scoreMode, int maxDoc) {
- this.score = score;
- this.scoreMode = scoreMode;
- this.maxDoc = maxDoc;
- }
-
- @Override
- public Scorer get(long leadCost) throws IOException {
- return new ConstantScoreScorer(score, scoreMode, DocIdSetIterator.all(maxDoc));
- }
-
- @Override
- public BulkScorer bulkScorer() throws IOException {
- if (maxDoc >= DenseConjunctionBulkScorer.WINDOW_SIZE / 2) {
- return new DenseConjunctionBulkScorer(Collections.emptyList(), maxDoc, score);
- } else {
- return super.bulkScorer();
- }
- }
-
- @Override
- public long cost() {
- return maxDoc;
- }
-}
diff --git a/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java b/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
index 478b43ec406..23bdaffa10c 100644
--- a/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
@@ -341,7 +341,7 @@ public abstract class PointRangeQuery extends Query {
if (allDocsMatch) {
// all docs have a value and all points are within bounds, so everything matches
- return new MatchAllScorerSupplier(score(), scoreMode, reader.maxDoc());
+ return ConstantScoreScorerSupplier.matchAll(score(), scoreMode, reader.maxDoc());
} else {
return new ConstantScoreScorerSupplier(score(), scoreMode, reader.maxDoc()) {
diff --git a/lucene/core/src/test/org/apache/lucene/search/ReadAheadMatchAllDocsQuery.java b/lucene/core/src/test/org/apache/lucene/search/ReadAheadMatchAllDocsQuery.java
index 8dbec52e06e..49902ba13fe 100644
--- a/lucene/core/src/test/org/apache/lucene/search/ReadAheadMatchAllDocsQuery.java
+++ b/lucene/core/src/test/org/apache/lucene/search/ReadAheadMatchAllDocsQuery.java
@@ -19,7 +19,6 @@ package org.apache.lucene.search;
import java.io.IOException;
import java.util.Collections;
import java.util.List;
-import java.util.Random;
import org.apache.lucene.index.LeafReaderContext;
/**
@@ -29,12 +28,8 @@ import org.apache.lucene.index.LeafReaderContext;
*/
public final class ReadAheadMatchAllDocsQuery extends Query {
- private final Random random;
-
/** Sole constructor */
- public ReadAheadMatchAllDocsQuery(Random random) {
- this.random = new Random(random.nextLong());
- }
+ public ReadAheadMatchAllDocsQuery() {}
@Override
public String toString(String field) {
@@ -80,13 +75,8 @@ public final class ReadAheadMatchAllDocsQuery extends Query {
@Override
public BulkScorer bulkScorer() throws IOException {
- List<DocIdSetIterator> clauses;
- if (random.nextBoolean()) {
- clauses = Collections.emptyList();
- } else {
- clauses = Collections.singletonList(DocIdSetIterator.all(context.reader().maxDoc()));
- }
-
+ List<DocIdSetIterator> clauses =
+ Collections.singletonList(DocIdSetIterator.all(context.reader().maxDoc()));
return new DenseConjunctionBulkScorer(clauses, context.reader().maxDoc(), score());
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java b/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
index e2e16d69029..62d98a45a8a 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
@@ -19,6 +19,7 @@ package org.apache.lucene.search;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
+import java.util.List;
import org.apache.lucene.tests.search.AssertingBulkScorer;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.util.BitSetIterator;
@@ -287,9 +288,11 @@ public class TestDenseConjunctionBulkScorer extends LuceneTestCase {
assertEquals(expected.cardinality(), collector.count);
}
- public void testZeroClauseNoLiveDocs() throws IOException {
+ public void testMatchAllNoLiveDocs() throws IOException {
int maxDoc = 100_000;
- BulkScorer scorer = new DenseConjunctionBulkScorer(Collections.emptyList(), maxDoc, 0f);
+ BulkScorer scorer =
+ new DenseConjunctionBulkScorer(
+ Collections.singletonList(DocIdSetIterator.all(maxDoc)), maxDoc, 0f);
// AssertingBulkScorer randomly splits the scored range into smaller ranges
scorer = AssertingBulkScorer.wrap(random(), scorer, maxDoc);
FixedBitSet result = new FixedBitSet(maxDoc);
@@ -311,15 +314,19 @@ public class TestDenseConjunctionBulkScorer extends LuceneTestCase {
assertEquals(DocIdSetIterator.NO_MORE_DOCS, result.nextSetBit(0));
// Now exercise DocIdStream.count()
- scorer = new DenseConjunctionBulkScorer(Collections.emptyList(), maxDoc, 0f);
+ scorer =
+ new DenseConjunctionBulkScorer(
+ Collections.singletonList(DocIdSetIterator.all(maxDoc)), maxDoc, 0f);
CountingLeafCollector collector = new CountingLeafCollector();
scorer.score(collector, null, 0, DocIdSetIterator.NO_MORE_DOCS);
assertEquals(maxDoc, collector.count);
}
- public void testZeroClauseWithLiveDocs() throws IOException {
+ public void testMatchAllWithLiveDocs() throws IOException {
int maxDoc = 100_000;
- BulkScorer scorer = new DenseConjunctionBulkScorer(Collections.emptyList(), maxDoc, 0f);
+ BulkScorer scorer =
+ new DenseConjunctionBulkScorer(
+ Collections.singletonList(DocIdSetIterator.all(maxDoc)), maxDoc, 0f);
// AssertingBulkScorer randomly splits the scored range into smaller ranges
scorer = AssertingBulkScorer.wrap(random(), scorer, maxDoc);
FixedBitSet acceptDocs = new FixedBitSet(maxDoc);
@@ -345,7 +352,9 @@ public class TestDenseConjunctionBulkScorer extends LuceneTestCase {
assertEquals(acceptDocs, result);
// Now exercise DocIdStream.count()
- scorer = new DenseConjunctionBulkScorer(Collections.emptyList(), maxDoc, 0f);
+ scorer =
+ new DenseConjunctionBulkScorer(
+ Collections.singletonList(DocIdSetIterator.all(maxDoc)), maxDoc, 0f);
CountingLeafCollector collector = new CountingLeafCollector();
scorer.score(collector, acceptDocs, 0, DocIdSetIterator.NO_MORE_DOCS);
assertEquals(acceptDocs.cardinality(), collector.count);
@@ -508,4 +517,195 @@ public class TestDenseConjunctionBulkScorer extends LuceneTestCase {
count += stream.count();
}
}
+
+ public void testRangeIntersection() throws IOException {
+ int maxDoc = 100_000;
+ DocIdSetIterator clause1 = DocIdSetIterator.range(10_000, 60_000);
+ DocIdSetIterator clause2 = DocIdSetIterator.range(30_000, 80_000);
+ List<DocIdSetIterator> clauses = Arrays.asList(clause1, clause2);
+ Collections.shuffle(clauses, random());
+
+ BulkScorer scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ // Matches are collected as a single DocIdStream
+ scorer.score(
+ new LeafCollector() {
+
+ private boolean called = false;
+ private int expected = 30_000;
+
+ @Override
+ public void setScorer(Scorable scorer) throws IOException {}
+
+ @Override
+ public void collect(int doc) throws IOException {
+ fail();
+ }
+
+ @Override
+ public void collect(DocIdStream stream) throws IOException {
+ assertFalse(called);
+ called = true;
+ stream.forEach(
+ doc -> {
+ assertEquals(expected++, doc);
+ });
+ }
+
+ @Override
+ public void finish() throws IOException {
+ assertEquals(60_001, expected);
+ }
+ },
+ null,
+ 0,
+ DocIdSetIterator.NO_MORE_DOCS);
+
+ clause1 = DocIdSetIterator.range(10_000, 60_000);
+ clause2 = DocIdSetIterator.range(30_000, 80_000);
+ clauses = Arrays.asList(clause1, clause2);
+ Collections.shuffle(clauses, random());
+ scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ CountingLeafCollector collector = new CountingLeafCollector();
+ scorer.score(collector, null, 0, DocIdSetIterator.NO_MORE_DOCS);
+ assertEquals(30_000, collector.count);
+ }
+
+ public void testRangeIntersectionWithLiveDocs() throws IOException {
+ int maxDoc = 100_000;
+ DocIdSetIterator clause1 = DocIdSetIterator.range(10_000, 60_000);
+ DocIdSetIterator clause2 = DocIdSetIterator.range(30_000, 80_000);
+ List<DocIdSetIterator> clauses = Arrays.asList(clause1, clause2);
+ Collections.shuffle(clauses, random());
+
+ FixedBitSet acceptDocs = new FixedBitSet(maxDoc);
+ for (int i = 0; i < maxDoc; i += 2) {
+ acceptDocs.set(i);
+ }
+
+ BulkScorer scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ // AssertingBulkScorer randomly splits the scored range into smaller ranges
+ scorer = AssertingBulkScorer.wrap(random(), scorer, maxDoc);
+ FixedBitSet result = new FixedBitSet(maxDoc);
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void setScorer(Scorable scorer) throws IOException {}
+
+ @Override
+ public void collect(int doc) throws IOException {
+ result.set(doc);
+ }
+ },
+ acceptDocs,
+ 0,
+ DocIdSetIterator.NO_MORE_DOCS);
+
+ FixedBitSet expected = new FixedBitSet(maxDoc);
+ for (int i = 30_000; i < 60_000; i += 2) {
+ expected.set(i);
+ }
+ assertEquals(expected, result);
+
+ // Now exercise DocIdStream.count()
+ clause1 = DocIdSetIterator.range(10_000, 60_000);
+ clause2 = DocIdSetIterator.range(30_000, 80_000);
+ clauses = Arrays.asList(clause1, clause2);
+ Collections.shuffle(clauses, random());
+ scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ CountingLeafCollector collector = new CountingLeafCollector();
+ scorer.score(collector, acceptDocs, 0, DocIdSetIterator.NO_MORE_DOCS);
+ assertEquals(expected.cardinality(), collector.count);
+ }
+
+ public void testMixedRangeIntersection() throws IOException {
+ int maxDoc = 100_000;
+ FixedBitSet clause2 = new FixedBitSet(maxDoc);
+ for (int i = 0; i < maxDoc; i += 2) {
+ clause2.set(i);
+ }
+ List<DocIdSetIterator> clauses =
+ Arrays.asList(DocIdSetIterator.range(10_000, 60_000), new BitSetIterator(clause2, 50_000));
+ Collections.shuffle(clauses, random());
+ BulkScorer scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ // AssertingBulkScorer randomly splits the scored range into smaller ranges
+ scorer = AssertingBulkScorer.wrap(random(), scorer, maxDoc);
+ FixedBitSet result = new FixedBitSet(maxDoc);
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void setScorer(Scorable scorer) throws IOException {}
+
+ @Override
+ public void collect(int doc) throws IOException {
+ result.set(doc);
+ }
+ },
+ null,
+ 0,
+ DocIdSetIterator.NO_MORE_DOCS);
+
+ FixedBitSet expected = new FixedBitSet(maxDoc);
+ for (int i = 10_000; i < 60_000; i += 2) {
+ expected.set(i);
+ }
+ assertEquals(expected, result);
+
+ // Now exercise DocIdStream.count()
+ clauses =
+ Arrays.asList(DocIdSetIterator.range(10_000, 60_000), new BitSetIterator(clause2, 50_000));
+ Collections.shuffle(clauses, random());
+ scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ CountingLeafCollector collector = new CountingLeafCollector();
+ scorer.score(collector, null, 0, DocIdSetIterator.NO_MORE_DOCS);
+ assertEquals(expected.cardinality(), collector.count);
+ }
+
+ public void testMixedRangeIntersectionWithLiveDocs() throws IOException {
+ int maxDoc = 100_000;
+ FixedBitSet clause2 = new FixedBitSet(maxDoc);
+ for (int i = 0; i < maxDoc; i += 3) {
+ clause2.set(i);
+ }
+ List<DocIdSetIterator> clauses =
+ Arrays.asList(DocIdSetIterator.range(10_000, 60_000), new BitSetIterator(clause2, 50_000));
+ Collections.shuffle(clauses, random());
+
+ FixedBitSet acceptDocs = new FixedBitSet(maxDoc);
+ for (int i = 0; i < maxDoc; i += 2) {
+ acceptDocs.set(i);
+ }
+
+ BulkScorer scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ // AssertingBulkScorer randomly splits the scored range into smaller ranges
+ scorer = AssertingBulkScorer.wrap(random(), scorer, maxDoc);
+ FixedBitSet result = new FixedBitSet(maxDoc);
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void setScorer(Scorable scorer) throws IOException {}
+
+ @Override
+ public void collect(int doc) throws IOException {
+ result.set(doc);
+ }
+ },
+ acceptDocs,
+ 0,
+ DocIdSetIterator.NO_MORE_DOCS);
+
+ FixedBitSet expected = new FixedBitSet(maxDoc);
+ for (int i = 10_002; i < 60_000; i += 6) {
+ expected.set(i);
+ }
+ assertEquals(expected, result);
+
+ // Now exercise DocIdStream.count()
+ clauses =
+ Arrays.asList(DocIdSetIterator.range(10_000, 60_000), new BitSetIterator(clause2, 50_000));
+ Collections.shuffle(clauses, random());
+ scorer = new DenseConjunctionBulkScorer(clauses, maxDoc, 0f);
+ CountingLeafCollector collector = new CountingLeafCollector();
+ scorer.score(collector, acceptDocs, 0, DocIdSetIterator.NO_MORE_DOCS);
+ assertEquals(expected.cardinality(), collector.count);
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestDocIdSetIterator.java b/lucene/core/src/test/org/apache/lucene/search/TestDocIdSetIterator.java
index 97decb4249d..2643c5ab366 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestDocIdSetIterator.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestDocIdSetIterator.java
@@ -19,6 +19,7 @@ package org.apache.lucene.search;
import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
+import java.io.IOException;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.util.FixedBitSet;
@@ -115,4 +116,22 @@ public class TestDocIdSetIterator extends LuceneTestCase {
}
}
}
+
+ public void testDocIDRunEnd() throws IOException {
+ DocIdSetIterator it = DocIdSetIterator.all(13);
+ assertEquals(0, it.nextDoc());
+ assertEquals(13, it.docIDRunEnd());
+ assertEquals(10, it.advance(10));
+ assertEquals(13, it.docIDRunEnd());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, it.advance(13));
+ }
+
+ public void testDocIDRunEndRange() throws IOException {
+ DocIdSetIterator it = DocIdSetIterator.range(4, 13);
+ assertEquals(4, it.nextDoc());
+ assertEquals(13, it.docIDRunEnd());
+ assertEquals(10, it.advance(10));
+ assertEquals(13, it.docIDRunEnd());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, it.advance(13));
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java b/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
index 96813ec0dd5..bc8a6e0125a 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
@@ -1163,7 +1163,7 @@ public class TestSortOptimization extends LuceneTestCase {
// behavior when the bulk scorer reads ahead
Query randomQuery;
if (query instanceof MatchAllDocsQuery) {
- randomQuery = new ReadAheadMatchAllDocsQuery(random());
+ randomQuery = new ReadAheadMatchAllDocsQuery();
} else {
randomQuery = query;
}
diff --git a/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingLeafCollector.java b/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingLeafCollector.java
index debca2cf3c6..c0a6eb9a34d 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingLeafCollector.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingLeafCollector.java
@@ -98,6 +98,15 @@ class AssertingLeafCollector extends FilterLeafCollector {
in.intoBitSet(upTo, bitSet, offset);
assert in.docID() >= upTo;
}
+
+ @Override
+ public int docIDRunEnd() throws IOException {
+ assert docID() != -1;
+ assert docID() != NO_MORE_DOCS;
+ int nextNonMatchingDocID = in.docIDRunEnd();
+ assert nextNonMatchingDocID > docID();
+ return nextNonMatchingDocID;
+ }
};
}
diff --git a/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingScorer.java b/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingScorer.java
index 9717f738e82..dfb85efccb9 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingScorer.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/tests/search/AssertingScorer.java
@@ -201,6 +201,14 @@ public class AssertingScorer extends Scorer {
in.intoBitSet(upTo, bitSet, offset);
assert docID() >= upTo;
}
+
+ @Override
+ public int docIDRunEnd() throws IOException {
+ assert state == IteratorState.ITERATING;
+ int nextNonMatchingDocID = in.docIDRunEnd();
+ assert nextNonMatchingDocID > docID();
+ return nextNonMatchingDocID;
+ }
};
}