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/28 20:12:12 UTC
(lucene) branch main updated: Make DenseConjunctionBulkScorer align scoring windows with #docIDRunEnd(). (#14400)
This is an automated email from the ASF dual-hosted git repository.
jpountz 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 a7ff87fdb54 Make DenseConjunctionBulkScorer align scoring windows with #docIDRunEnd(). (#14400)
a7ff87fdb54 is described below
commit a7ff87fdb5479a2f1e89746d88c80023b0aecbb1
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Fri Mar 28 21:12:07 2025 +0100
Make DenseConjunctionBulkScorer align scoring windows with #docIDRunEnd(). (#14400)
This improves the way how `DenseConjunctionBulkScorer` computes scoring windows
by aligning the end of the window with the `#docIDRunEnd()` of its clauses, as
long as it would result in a window that is at least half the expected size.
This helps reduce the number of clauses to evaluate per window in some cases.
---
.../lucene/search/DenseConjunctionBulkScorer.java | 43 +++++++++++-----------
.../search/TestDenseConjunctionBulkScorer.java | 23 +++++++++---
2 files changed, 39 insertions(+), 27 deletions(-)
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 48190d6b5a1..f3a08842e52 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
@@ -167,35 +167,36 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
}
}
- if (acceptDocs == null) {
- int minDocIDRunEnd = max;
- for (DisiWrapper w : iterators) {
- if (w.docID() > min) {
- minDocIDRunEnd = min;
- break;
- } else {
- minDocIDRunEnd = Math.min(minDocIDRunEnd, w.docIDRunEnd());
- }
- }
-
- if (minDocIDRunEnd - min >= WINDOW_SIZE / 2) {
- // We have a large range of doc IDs that all match.
- collector.collect(new RangeDocIdStream(min, minDocIDRunEnd));
- return minDocIDRunEnd;
- }
- }
-
- int bitsetWindowMax = (int) Math.min(max, (long) min + WINDOW_SIZE);
-
+ // Partition clauses of the conjunction into:
+ // - clauses that don't fully match the first half of the window and get evaluated via
+ // #loadIntoBitSet or leaf-frog,
+ // - other clauses that are used to compute the greatest possible window size that they fully
+ // match.
+ // This logic helps align scoring windows with the natural #docIDRunEnd() boundaries of the
+ // data, which helps evaluate fewer clauses per window - without allowing windows to become too
+ // small thanks to the WINDOW_SIZE/2 threshold.
+ int minDocIDRunEnd = max;
+ final int minRunEndThreshold = (int) Math.min((long) min + WINDOW_SIZE / 2, max);
for (DisiWrapper w : iterators) {
- if (w.docID() > min || w.docIDRunEnd() < bitsetWindowMax) {
+ int docIdRunEnd = w.docIDRunEnd();
+ if (w.docID() > min || docIdRunEnd < minRunEndThreshold) {
windowApproximations.add(w.approximation());
if (w.twoPhase() != null) {
windowTwoPhases.add(w.twoPhase());
}
+ } else {
+ minDocIDRunEnd = Math.min(minDocIDRunEnd, docIdRunEnd);
}
}
+ if (acceptDocs == null && windowApproximations.isEmpty()) {
+ // We have a large range of doc IDs that all match.
+ collector.collect(new RangeDocIdStream(min, minDocIDRunEnd));
+ return minDocIDRunEnd;
+ }
+
+ int bitsetWindowMax = (int) Math.min(minDocIDRunEnd, (long) WINDOW_SIZE + min);
+
if (windowTwoPhases.isEmpty()) {
if (acceptDocs == null && windowApproximations.size() == 1) {
// We have a range of doc IDs where all matches of an iterator are matches of the
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 cc077516c42..ff220e2d0e2 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
@@ -648,18 +648,29 @@ public class TestDenseConjunctionBulkScorer extends LuceneTestCase {
}
public void testMixedRangeIntersection() throws IOException {
- int maxDoc = 100_000;
+ int maxDoc = 80_000;
FixedBitSet clause2 = new FixedBitSet(maxDoc);
for (int i = 0; i < maxDoc; i += 2) {
clause2.set(i);
}
+ DocIdSetIterator rangeIterator =
+ new FilterDocIdSetIterator(DocIdSetIterator.range(10_000, 50_000)) {
+ @Override
+ public int docIDRunEnd() throws IOException {
+ return in.docIDRunEnd();
+ }
+
+ @Override
+ public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+ fail(
+ "intoBitSet should not be called if scoring windows get aligned with #docIDRunEnd");
+ }
+ };
List<DocIdSetIterator> clauses =
- Arrays.asList(DocIdSetIterator.range(10_000, 60_000), new BitSetIterator(clause2, 50_000));
+ Arrays.asList(rangeIterator, new BitSetIterator(clause2, 40_000));
Collections.shuffle(clauses, random());
BulkScorer scorer =
new DenseConjunctionBulkScorer(clauses, Collections.emptyList(), 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() {
@@ -676,14 +687,14 @@ public class TestDenseConjunctionBulkScorer extends LuceneTestCase {
DocIdSetIterator.NO_MORE_DOCS);
FixedBitSet expected = new FixedBitSet(maxDoc);
- for (int i = 10_000; i < 60_000; i += 2) {
+ for (int i = 10_000; i < 50_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));
+ Arrays.asList(DocIdSetIterator.range(10_000, 50_000), new BitSetIterator(clause2, 40_000));
Collections.shuffle(clauses, random());
scorer = new DenseConjunctionBulkScorer(clauses, Collections.emptyList(), maxDoc, 0f);
CountingLeafCollector collector = new CountingLeafCollector();