You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ro...@apache.org on 2026/09/24 08:41:13 UTC
(lucene) branch branch_10x updated: Use intoBitSet to speed up ReqExclBulkScorer (#16669)
This is an automated email from the ASF dual-hosted git repository.
romseygeek 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 92ce3eaf4bf Use intoBitSet to speed up ReqExclBulkScorer (#16669)
92ce3eaf4bf is described below
commit 92ce3eaf4bf524ee24d7dc742cedeaa812695db8
Author: kkewwei <ke...@bytedance.com>
AuthorDate: Thu Sep 24 16:30:33 2026 +0800
Use intoBitSet to speed up ReqExclBulkScorer (#16669)
---
lucene/CHANGES.txt | 2 +
.../jmh/MustNotBooleanQueryBenchmark.java | 52 ++++---
.../apache/lucene/search/ReqExclBulkScorer.java | 96 ++++++++++---
.../lucene/search/TestReqExclBulkScorer.java | 158 ++++++++++++++++++++-
4 files changed, 269 insertions(+), 39 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index c4254c777f7..9e6ce3714a5 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -171,6 +171,8 @@ Optimizations
* GITHUB#16520: Support two-phase filters in MaxScoreBulkScorer bitset path. (Ke Wei)
+* GITHUB#16669: Use intoBitSet to speed up ReqExclBulkScorer with dense exclusions. (Ke Wei)
+
Bug Fixes
---------------------
* GITHUB#16546: Prevent RangeBulkScorer from passing empty ranges to LeafCollector. (jxy)
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/MustNotBooleanQueryBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/MustNotBooleanQueryBenchmark.java
index 1527314142a..d8cecc97fef 100644
--- a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/MustNotBooleanQueryBenchmark.java
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/MustNotBooleanQueryBenchmark.java
@@ -53,14 +53,10 @@ import org.openjdk.jmh.annotations.TearDown;
import org.openjdk.jmh.annotations.Warmup;
/**
- * Benchmarks dense interleaved MUST_NOT term disjunctions over a MatchAllDocsQuery.
+ * Benchmarks dense and sparse MUST_NOT term disjunctions over a {@link MatchAllDocsQuery}.
*
- * <p>Most documents are indexed with every prohibited term except one rotating hole, which keeps
- * term posting lists dense enough that {@code DisjunctionDISIApproximation} splits some clauses
- * into linear-scanned iterators. Periodic pass-through documents have no prohibited terms, so the
- * query returns a small non-zero hit count while repeatedly invoking {@code ReqExclBulkScorer} and
- * the exclusion disjunction's {@code docIDRunEnd()} path. The default setup builds 10M documents
- * and force-merges to one segment to match the target regression scenario.
+ * <p>Excluded documents are assigned one prohibited term in round-robin order. The dense scenario
+ * excludes most documents, while the sparse scenario excludes one document per interval.
*/
@State(Scope.Benchmark)
@BenchmarkMode(Mode.Throughput)
@@ -75,7 +71,8 @@ public class MustNotBooleanQueryBenchmark {
private static final String EXCLUDED_FIELD = "excluded";
private static final String EXCLUDED_TERM_PREFIX = "term";
- private static final int PASS_THROUGH_INTERVAL = 128;
+ private static final String DENSE = "dense";
+ private static final String SPARSE = "sparse";
private Directory dir;
private IndexReader reader;
@@ -91,6 +88,12 @@ public class MustNotBooleanQueryBenchmark {
@Param({"3", "7", "11"})
public int mustNotTermCount;
+
+ @Param({DENSE})
+ public String distribution;
+
+ @Param({"128"})
+ public int interval;
}
@Setup(Level.Trial)
@@ -100,7 +103,8 @@ public class MustNotBooleanQueryBenchmark {
try (IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig())) {
for (int docID = 0; docID < params.docCount; docID++) {
- writer.addDocument(document(docID, params.mustNotTermCount));
+ writer.addDocument(
+ document(docID, params.mustNotTermCount, params.distribution, params.interval));
}
writer.forceMerge(1);
reader = DirectoryReader.open(writer);
@@ -110,23 +114,33 @@ public class MustNotBooleanQueryBenchmark {
searcher.setQueryCache(null);
query = query(params.mustNotTermCount);
collectorManager = new TotalHitCountCollectorManager(searcher.getSlices());
- int expectedHitCount = (params.docCount - 1) / PASS_THROUGH_INTERVAL + 1;
+ int intervalDocCount = (params.docCount - 1) / params.interval + 1;
+ int expectedHitCount =
+ DENSE.equals(params.distribution) ? intervalDocCount : params.docCount - intervalDocCount;
int actualHitCount = searcher.search(query, collectorManager);
if (actualHitCount != expectedHitCount) {
throw new AssertionError("expected " + expectedHitCount + " hits but got " + actualHitCount);
}
}
- private static Document document(int docID, int mustNotTermCount) {
+ private static Document document(
+ int docID, int mustNotTermCount, String distribution, int interval) {
Document doc = new Document();
- if (docID % PASS_THROUGH_INTERVAL == 0) {
- return doc;
- }
- int missingTerm = docID % mustNotTermCount;
- for (int termOrd = 0; termOrd < mustNotTermCount; termOrd++) {
- if (termOrd != missingTerm) {
- doc.add(new StringField(EXCLUDED_FIELD, term(termOrd), Field.Store.NO));
- }
+ switch (distribution) {
+ case DENSE:
+ if (docID % interval != 0) {
+ doc.add(new StringField(EXCLUDED_FIELD, term(docID % mustNotTermCount), Field.Store.NO));
+ }
+ break;
+ case SPARSE:
+ if (docID % interval == 0) {
+ doc.add(
+ new StringField(
+ EXCLUDED_FIELD, term((docID / interval) % mustNotTermCount), Field.Store.NO));
+ }
+ break;
+ default:
+ throw new IllegalArgumentException("Unknown distribution: " + distribution);
}
return doc;
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/ReqExclBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/ReqExclBulkScorer.java
index 2fbe3ea5558..179265aee06 100644
--- a/lucene/core/src/java/org/apache/lucene/search/ReqExclBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/ReqExclBulkScorer.java
@@ -18,12 +18,15 @@ package org.apache.lucene.search;
import java.io.IOException;
import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
final class ReqExclBulkScorer extends BulkScorer {
+ private static final int WINDOW_SIZE = 4096;
private final BulkScorer req;
private final DocIdSetIterator exclApproximation;
private final TwoPhaseIterator exclTwoPhase;
+ private final WindowBits windowBits = new WindowBits();
ReqExclBulkScorer(BulkScorer req, Scorer excl) {
this.req = req;
@@ -49,34 +52,43 @@ final class ReqExclBulkScorer extends BulkScorer {
@Override
public int score(LeafCollector collector, Bits acceptDocs, int min, int max) throws IOException {
+ FixedBitSet windowMask = windowBits.windowMask;
+
int upTo = min;
- int exclDoc = exclApproximation.docID();
while (upTo < max) {
- if (exclDoc < upTo) {
- exclDoc = exclApproximation.advance(upTo);
+ int windowMin = upTo;
+ int windowMax = (int) Math.min((long) max, (long) windowMin + WINDOW_SIZE);
+
+ if (exclApproximation.docID() < windowMin) {
+ exclApproximation.advance(windowMin);
}
- if (exclDoc == upTo) {
- if (exclTwoPhase == null) {
- // from upTo to docIdRunEnd() are excluded, so we scored up to docIdRunEnd()
- upTo = Math.min(exclApproximation.docIDRunEnd(), max);
- } else if (exclTwoPhase.matches()) {
- // upTo is excluded (matches() just confirmed it), so skip the whole run of consecutive
- // excluded docs at once, like the non-two-phase branch above. The default
- // TwoPhaseIterator#docIDRunEnd() conservatively returns the current doc, so clamp to at
- // least upTo+1 to guarantee progress when the run end is not overridden.
- upTo = Math.max(upTo + 1, Math.min(exclTwoPhase.docIDRunEnd(), max));
- }
- exclDoc = exclApproximation.nextDoc();
+
+ windowMask.clear();
+ if (exclTwoPhase == null) {
+ exclApproximation.intoBitSet(windowMax, windowMask, windowMin);
} else {
- upTo = req.score(collector, acceptDocs, upTo, Math.min(exclDoc, max));
+ exclTwoPhase.intoBitSet(windowMax, windowMask, windowMin);
}
+ int windowLength = windowMax - windowMin;
+ int validWindowLength =
+ acceptDocs == null
+ ? windowLength
+ : Math.max(0, Math.min(windowLength, acceptDocs.length() - windowMin));
+ windowMask.flip(0, validWindowLength);
+ if (validWindowLength < windowLength) {
+ windowMask.clear(validWindowLength, windowLength);
+ }
+ if (acceptDocs != null) {
+ acceptDocs.applyMask(windowMask, windowMin);
+ }
+ windowBits.reset(windowMin, windowMax, acceptDocs == null ? max : acceptDocs.length());
+ upTo = req.score(collector, windowBits, windowMin, windowMax);
}
if (upTo == max) {
- upTo = req.score(collector, acceptDocs, upTo, upTo);
+ upTo = req.score(collector, acceptDocs, max, max);
}
-
return upTo;
}
@@ -84,4 +96,52 @@ final class ReqExclBulkScorer extends BulkScorer {
public long cost() {
return req.cost();
}
+
+ static final class WindowBits implements Bits {
+ final FixedBitSet windowMask = new FixedBitSet(WINDOW_SIZE);
+ private int windowBase;
+ private int windowEnd;
+ private int length;
+
+ void reset(int windowBase, int windowEnd, int length) {
+ this.windowBase = windowBase;
+ this.windowEnd = windowEnd;
+ this.length = length;
+ }
+
+ @Override
+ public boolean get(int index) {
+ assert index >= windowBase && index < windowEnd;
+ return windowMask.get(index - windowBase);
+ }
+
+ @Override
+ public int length() {
+ return length;
+ }
+
+ @Override
+ public void applyMask(FixedBitSet bitSet, int offset) {
+ int bitSetEnd = Math.min(DocIdSetIterator.NO_MORE_DOCS, offset + bitSet.length());
+ // The absolute doc ID ranges for bitSet and the current window.
+ int from = Math.max(windowBase, offset);
+ int to = Math.min(windowEnd, bitSetEnd);
+ if (from >= to) {
+ bitSet.clear();
+ return;
+ }
+
+ int targetFrom = from - offset;
+ if (targetFrom > 0) {
+ bitSet.clear(0, targetFrom);
+ }
+
+ int targetTo = to - offset;
+ if (targetTo < bitSet.length()) {
+ bitSet.clear(targetTo, bitSet.length());
+ }
+
+ FixedBitSet.andRange(windowMask, from - windowBase, bitSet, targetFrom, to - from);
+ }
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestReqExclBulkScorer.java b/lucene/core/src/test/org/apache/lucene/search/TestReqExclBulkScorer.java
index d0c989024a2..8c569f0b9f4 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestReqExclBulkScorer.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestReqExclBulkScorer.java
@@ -20,6 +20,7 @@ import java.io.IOException;
import org.apache.lucene.tests.search.RandomApproximationQuery.RandomTwoPhaseView;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.tests.util.TestUtil;
+import org.apache.lucene.util.BitSetIterator;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.FixedBitSet;
@@ -92,6 +93,13 @@ public class TestReqExclBulkScorer extends LuceneTestCase {
reqExcl = new ReqExclBulkScorer(reqBulkScorer, excl.iterator());
}
final FixedBitSet actualMatches = new FixedBitSet(maxDoc);
+ final FixedBitSet acceptedDocs = new FixedBitSet(maxDoc);
+ for (int doc = 0; doc < maxDoc; doc++) {
+ if (random().nextBoolean()) {
+ acceptedDocs.set(doc);
+ }
+ }
+ Bits acceptDocs = random().nextBoolean() ? null : acceptedDocs.asReadOnlyBits();
if (random().nextBoolean()) {
reqExcl.score(
new LeafCollector() {
@@ -103,7 +111,7 @@ public class TestReqExclBulkScorer extends LuceneTestCase {
actualMatches.set(doc);
}
},
- null,
+ acceptDocs,
0,
DocIdSetIterator.NO_MORE_DOCS);
} else {
@@ -122,7 +130,7 @@ public class TestReqExclBulkScorer extends LuceneTestCase {
actualMatches.set(doc);
}
},
- null,
+ acceptDocs,
min,
max);
assertTrue(next >= max);
@@ -134,7 +142,153 @@ public class TestReqExclBulkScorer extends LuceneTestCase {
FixedBitSet excludedSet = new FixedBitSet(maxDoc);
excludedSet.or(excl.iterator());
expectedMatches.andNot(excludedSet);
+ if (acceptDocs != null) {
+ expectedMatches.and(acceptedDocs);
+ }
assertArrayEquals(expectedMatches.getBits(), actualMatches.getBits());
}
+
+ public void testDenseScore() throws IOException {
+ int maxDoc = 10_000;
+ FixedBitSet required = new FixedBitSet(maxDoc);
+ FixedBitSet excluded = new FixedBitSet(maxDoc);
+ FixedBitSet accepted = null;
+ FixedBitSet expected = new FixedBitSet(maxDoc);
+
+ boolean hasDelete = random().nextBoolean();
+ if (hasDelete) {
+ accepted = new FixedBitSet(maxDoc);
+ }
+
+ for (int doc = 0; doc < maxDoc; doc++) {
+ if (doc % 3 == 1) {
+ required.set(doc);
+ }
+ if ((doc & 1) == 0) {
+ excluded.set(doc);
+ }
+
+ if (required.get(doc) && excluded.get(doc) == false) {
+ expected.set(doc);
+ }
+
+ if (hasDelete) {
+ if (doc % 5 != 0) {
+ accepted.set(doc);
+ } else {
+ expected.clear(doc);
+ }
+ }
+ }
+ Bits acceptDocs = hasDelete ? accepted.asReadOnlyBits() : null;
+
+ BitSetIterator exclusion = new BitSetIterator(excluded, excluded.cardinality());
+ ReqExclBulkScorer scorer =
+ new ReqExclBulkScorer(
+ new ConstantScoreBulkScorer(
+ 0f,
+ ScoreMode.COMPLETE_NO_SCORES,
+ new BitSetIterator(required, required.cardinality())),
+ exclusion);
+ FixedBitSet actual = new FixedBitSet(maxDoc);
+ assertEquals(
+ DocIdSetIterator.NO_MORE_DOCS,
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void setScorer(Scorable scorer) {}
+
+ @Override
+ public void collect(int doc) {
+ actual.set(doc);
+ }
+ },
+ acceptDocs,
+ 0,
+ maxDoc));
+
+ assertArrayEquals(expected.getBits(), actual.getBits());
+ }
+
+ public void testSparseScore() throws IOException {
+ int maxDoc = 10_000;
+ FixedBitSet excluded = new FixedBitSet(maxDoc);
+ FixedBitSet accepted = null;
+ FixedBitSet expected = new FixedBitSet(maxDoc);
+ expected.set(0, maxDoc);
+
+ excluded.set(42);
+ excluded.set(600);
+
+ expected.clear(42);
+ expected.clear(600);
+
+ boolean hasDelete = random().nextBoolean();
+ if (hasDelete) {
+ accepted = new FixedBitSet(maxDoc);
+ accepted.set(0, maxDoc);
+ accepted.clear(42);
+ accepted.clear(601);
+ expected.clear(42);
+ expected.clear(601);
+ }
+
+ BitSetIterator exclusion = new BitSetIterator(excluded, excluded.cardinality());
+ ReqExclBulkScorer scorer =
+ new ReqExclBulkScorer(
+ new ConstantScoreBulkScorer(
+ 0f, ScoreMode.COMPLETE_NO_SCORES, DocIdSetIterator.all(maxDoc)),
+ exclusion);
+ FixedBitSet collected = new FixedBitSet(maxDoc);
+ assertEquals(
+ DocIdSetIterator.NO_MORE_DOCS,
+ scorer.score(
+ new LeafCollector() {
+ @Override
+ public void setScorer(Scorable scorer) {}
+
+ @Override
+ public void collect(int doc) {
+ collected.set(doc);
+ }
+ },
+ accepted != null ? accepted.asReadOnlyBits() : null,
+ 0,
+ maxDoc));
+
+ assertArrayEquals(expected.getBits(), collected.getBits());
+ }
+
+ public void testWindowBitsApplyMask() {
+ ReqExclBulkScorer.WindowBits windowBits = new ReqExclBulkScorer.WindowBits();
+ windowBits.reset(100, 108, 1_000);
+ windowBits.windowMask.set(1);
+ windowBits.windowMask.set(3);
+ windowBits.windowMask.set(6);
+
+ // intersection
+ FixedBitSet target = new FixedBitSet(12);
+ target.set(0, 12);
+ target.clear(5);
+ windowBits.applyMask(target, 98);
+ FixedBitSet expected = new FixedBitSet(12);
+ // 100+1-98=3
+ // 100+6-98=8
+ expected.set(3);
+ expected.set(8);
+ assertArrayEquals(expected.getBits(), target.getBits());
+
+ // no intersection
+ target = new FixedBitSet(4);
+ target.set(0, target.length());
+ windowBits.applyMask(target, 96);
+ assertEquals(0, target.cardinality());
+
+ // no intersection
+ target = new FixedBitSet(4);
+ target.set(0, target.length());
+ windowBits.applyMask(target, 108);
+ assertEquals(0, target.cardinality());
+ }
}