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/07/07 09:45:31 UTC
(lucene) branch main updated: Add TwoPhaseIterator.applyMask() method (#16362)
This is an automated email from the ASF dual-hosted git repository.
romseygeek 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 9b6ca1356f5 Add TwoPhaseIterator.applyMask() method (#16362)
9b6ca1356f5 is described below
commit 9b6ca1356f532a252a9e710abf6d4931b9604463
Author: Alan Woodward <ro...@apache.org>
AuthorDate: Tue Jul 7 10:45:25 2026 +0100
Add TwoPhaseIterator.applyMask() method (#16362)
TwoPhaseIterator.intoBitSet() can vectorize two-phase matching across a
window of documents, but it does not take into account any previous
conjunction clauses that could have excluded documents in the window from
consideration. This can cause inefficiencies in DenseConjunctionBulkScorer,
where we use intoBitSet for windows that we know have more than 25%
matches - for example, a window with 26% matching documents when combined
with a two-phase iterator whose approximation matches everything will
call `match()` on the 74% of documents in the window that have already
been excluded.
This adds a complementary method `applyMask()` to TwoPhaseIterator that
will call matches() on all documents marked as selected in a passed-in
BitSet, and clear them if they do not pass. DocValuesRangeIterator
can use a bulk implementation, while the default implementation
still avoids matching documents already excluded by earlier clauses.
DenseConjunctionBulkScorer always calls applyMask() when presented
with a TwoPhaseIterator as a trailing clause.
---
lucene/CHANGES.txt | 3 +
.../lucene/search/DenseConjunctionBulkScorer.java | 33 +-
.../lucene/search/DocValuesRangeIterator.java | 57 ++-
.../org/apache/lucene/search/TwoPhaseIterator.java | 36 ++
...estSkipBlockRangeIteratorBitSetOperations.java} | 484 ++++++++++++++++++++-
.../apache/lucene/search/TestTwoPhaseIterator.java | 222 ++++++++++
6 files changed, 803 insertions(+), 32 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index df8de90e623..12b928dae11 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -331,6 +331,9 @@ Optimizations
* GITHUB#16352: Better cost() estimation for SkipBlockRangeIterator. (Alan Woodward)
+* GITHUB#16362: Add TwoPhaseIterator.applyMask() to support bulk matching for more
+ expensive queries. (Alan Woodward)
+
* GITHUB#16355: Add ASCII fast-path to CharacterUtils.toLowerCase, avoiding per-char codepoint
conversion for ASCII-only tokens. 2.16x throughput on English text. (Costin Leau)
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 6dfd8a18f19..41f5e71f2d9 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
@@ -225,7 +225,9 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
break;
}
}
- // "sparse" mirrors the bit set's own WINDOW_SIZE/4 bulk-confirm cutoff (leadCost <= maxDoc/4).
+ // "sparse" means the lead clause's cost estimates it matches at most 1/4 of the document
+ // space -- cheap enough that leap-frog's per-survivor confirmation beats materializing a bit
+ // set for the whole window.
boolean sparse =
windowClauses.isEmpty() == false
&& windowClauses.get(0).approximation().cost() <= (long) maxDoc / 4;
@@ -279,9 +281,6 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
int windowSize = windowMax - windowBase;
int threshold = windowSize / DENSITY_THRESHOLD_INVERSE;
- // Above this many surviving docs, decoding a two-phase clause's whole window in one shot beats
- // confirming each survivor one at a time; below it we confirm survivors only.
- int bulkConfirmThreshold = windowSize / 4;
int upTo = 1; // the leading clause at index 0 is already applied
for (int cardinality = windowMatches.cardinality();
upTo < iterators.size() && cardinality >= threshold;
@@ -291,26 +290,14 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
other.approximation().advance(windowBase);
}
TwoPhaseIterator twoPhase = other.twoPhase();
- if (twoPhase != null && cardinality < bulkConfirmThreshold) {
- // Sparse survivors + per-doc confirmation: confirm only the docs that survived the cheaper
- // clauses (the bit set gates matches()), never decoding a doc another clause excluded.
- DocIdSetIterator approximation = other.approximation();
- for (int windowMatch = windowMatches.nextSetBit(0);
- windowMatch != DocIdSetIterator.NO_MORE_DOCS; ) {
- int doc = windowBase + windowMatch;
- int otherDoc = approximation.docID();
- if (otherDoc < doc) {
- otherDoc = approximation.advance(doc);
- }
- if (otherDoc != doc || twoPhase.matches() == false) {
- windowMatches.clear(windowMatch);
- }
- windowMatch = advance(windowMatches, windowMatch + 1);
- }
+ if (twoPhase != null) {
+ // Confirm only against docs that are still candidates: the default implementation walks
+ // survivors one at a time, never decoding a doc another clause already excluded, while
+ // implementations with real bulk support (e.g. a block-based skip index) can classify
+ // whole spans of the candidate set without calling matches() at all.
+ twoPhase.applyMask(windowMax, windowMatches, windowBase);
} else {
- // Dense survivors, or a plain iterator: load this clause's matches in bulk and intersect.
- // For a two-phase clause this still confirms matches() via its (possibly vectorized)
- // intoBitSet.
+ // Plain iterator: load its own matches in bulk and intersect.
other.intoBitSet(windowMax, clauseWindowMatches, windowBase);
windowMatches.and(clauseWindowMatches);
clauseWindowMatches.clear();
diff --git a/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java b/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
index 9bba0cec5dd..64077fa4efd 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java
@@ -337,12 +337,7 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
while (blockIterator.docID() < upTo) {
int blockStart = blockIterator.docID();
SkipBlockRangeIterator.Match match = blockIterator.getMatch();
- // For MAYBE blocks docIDRunEnd() is conservative (doc+1), so use the full block boundary to
- // evaluate the whole block at once.
- int blockEnd =
- match == SkipBlockRangeIterator.Match.MAYBE
- ? Math.min(upTo, blockIterator.blockEnd())
- : Math.min(upTo, blockIterator.docIDRunEnd());
+ int blockEnd = blockEnd(upTo, match);
switch (match) {
case YES -> bitSet.set(blockStart - offset, blockEnd - offset);
case YES_IF_PRESENT -> {
@@ -364,6 +359,56 @@ public abstract sealed class DocValuesRangeIterator extends TwoPhaseIterator {
/** Confirms the docs of a single MAYBE block in {@code [blockStart, blockEnd)}. */
abstract void intoMaybeBlock(int blockStart, int blockEnd, FixedBitSet bitSet, int offset)
throws IOException;
+
+ // For MAYBE blocks docIDRunEnd() is conservative (doc+1), so use the full block boundary to
+ // evaluate/classify the whole block at once.
+ private int blockEnd(int upTo, SkipBlockRangeIterator.Match match) throws IOException {
+ return match == SkipBlockRangeIterator.Match.MAYBE
+ ? Math.min(upTo, blockIterator.blockEnd())
+ : Math.min(upTo, blockIterator.docIDRunEnd());
+ }
+
+ @Override
+ public final void applyMask(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+ int cursor = offset;
+ FixedBitSet scratch = null;
+ while (blockIterator.docID() < upTo) {
+ int blockStart = blockIterator.docID();
+ if (cursor < blockStart) {
+ // [cursor, blockStart) doesn't intersect the query range at all -- clear all bits
+ // in this range
+ bitSet.clear(cursor - offset, blockStart - offset);
+ }
+ SkipBlockRangeIterator.Match match = blockIterator.getMatch();
+ int blockEnd = blockEnd(upTo, match);
+
+ if (match != SkipBlockRangeIterator.Match.YES
+ && bitSet.nextSetBit(blockStart - offset, blockEnd - offset)
+ != DocIdSetIterator.NO_MORE_DOCS) {
+ int blockLength = blockEnd - blockStart;
+ if (scratch == null || scratch.length() < blockLength) {
+ scratch = new FixedBitSet(blockLength);
+ }
+ if (match == SkipBlockRangeIterator.Match.YES_IF_PRESENT) {
+ if (disi.docID() < blockStart) {
+ disi.advance(blockStart);
+ }
+ disi.intoBitSet(blockEnd, scratch, blockStart);
+ } else {
+ intoMaybeBlock(blockStart, blockEnd, scratch, blockStart);
+ }
+ FixedBitSet.andRange(scratch, 0, bitSet, blockStart - offset, blockLength);
+ scratch.clear(0, blockLength);
+ }
+ cursor = blockEnd;
+ blockIterator.advance(blockEnd);
+ }
+ if (cursor < upTo) {
+ // The blockIterator has moved past upTo so any remaining bits above the cursor
+ // do not match
+ bitSet.clear(cursor - offset, upTo - offset);
+ }
+ }
}
/** Bulk range iterator over single-valued numeric doc values. */
diff --git a/lucene/core/src/java/org/apache/lucene/search/TwoPhaseIterator.java b/lucene/core/src/java/org/apache/lucene/search/TwoPhaseIterator.java
index 8a83e865480..91988acd37e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TwoPhaseIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TwoPhaseIterator.java
@@ -145,4 +145,40 @@ public abstract class TwoPhaseIterator {
}
}
}
+
+ /**
+ * Confirms {@link #matches()} only for the doc IDs whose bit is set in {@code bitSet} (the
+ * document whose ID is {@code i} being stored at bit {@code i - offset}), clearing bits for docs
+ * that turn out not to match. Upon return {@link #approximation()} is positioned on the first doc
+ * that is {@code >= upTo}, mirroring {@link #intoBitSet}.
+ *
+ * <p>Prefer this over {@link #intoBitSet} followed by a separate intersection when {@code bitSet}
+ * already holds a candidate set narrowed down by other clauses of a conjunction: it avoids
+ * confirming matches for docs that are already known not to be candidates.
+ *
+ * <p>The default implementation walks the set bits of {@code bitSet} one at a time, advancing
+ * {@link #approximation()} to each and calling {@link #matches()}. Implementations that can
+ * classify a whole span of a sparse candidate set in bulk -- for instance a block-based skip
+ * index that can tell that an entire span is fully matching or fully non-matching without
+ * visiting doc values -- should override this.
+ */
+ public void applyMask(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+ DocIdSetIterator approximation = approximation();
+ int upperBound = Math.min(bitSet.length(), upTo - offset);
+ for (int i = bitSet.nextSetBit(0);
+ i != DocIdSetIterator.NO_MORE_DOCS && i < upperBound;
+ i = i + 1 >= bitSet.length() ? DocIdSetIterator.NO_MORE_DOCS : bitSet.nextSetBit(i + 1)) {
+ int doc = offset + i;
+ int approxDoc = approximation.docID();
+ if (approxDoc < doc) {
+ approxDoc = approximation.advance(doc);
+ }
+ if (approxDoc != doc || matches() == false) {
+ bitSet.clear(i);
+ }
+ }
+ if (approximation.docID() < upTo) {
+ approximation.advance(upTo);
+ }
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java b/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorBitSetOperations.java
similarity index 66%
rename from lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java
rename to lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorBitSetOperations.java
index 379fb7a0fd0..01c22552921 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorIntoBitSet.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSkipBlockRangeIteratorBitSetOperations.java
@@ -38,10 +38,11 @@ import org.apache.lucene.store.Directory;
import org.apache.lucene.util.FixedBitSet;
/**
- * Tests the {@code intoBitSet()} bulk path of {@link DocValuesRangeIterator} over single-valued
- * numeric doc values, including YES, YES_IF_PRESENT, and MAYBE block states.
+ * Tests the {@code intoBitSet()} and {@code applyMask()} bulk paths of {@link
+ * DocValuesRangeIterator} over single-valued numeric doc values, including YES, YES_IF_PRESENT, and
+ * MAYBE block states.
*/
-public class TestSkipBlockRangeIteratorIntoBitSet extends BaseDocValuesSkipperTests {
+public class TestSkipBlockRangeIteratorBitSetOperations extends BaseDocValuesSkipperTests {
// Use enough docs to span at least 4 skip blocks (default skip block size = 4096 docs).
private static final int DOC_COUNT = 4096 * 4;
@@ -579,6 +580,483 @@ public class TestSkipBlockRangeIteratorIntoBitSet extends BaseDocValuesSkipperTe
}
}
+ /**
+ * With every doc a candidate, {@code applyMask} must confirm exactly the same docs as {@code
+ * intoBitSet} would set from scratch.
+ */
+ public void testApplyMaskWithFullCandidateSetMatchesIntoBitSet() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator intoBitSetIter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ intoBitSetIter.approximation().nextDoc();
+ FixedBitSet expected = new FixedBitSet(2048);
+ intoBitSetIter.intoBitSet(2048, expected, 0);
+
+ values = docValues(queryMin, queryMax);
+ skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator maskIter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ maskIter.approximation().nextDoc();
+ FixedBitSet allCandidates = new FixedBitSet(2048);
+ allCandidates.set(0, 2048);
+ maskIter.applyMask(2048, allCandidates, 0);
+
+ assertEquals(
+ "applyMask with every doc a candidate must match intoBitSet", expected, allCandidates);
+ }
+
+ /** {@code applyMask} must only ever clear candidate bits, never set new ones. */
+ public void testApplyMaskNeverSetsBitsOutsideInitialCandidates() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ iter.approximation().nextDoc();
+
+ Random rng = random();
+ FixedBitSet candidates = new FixedBitSet(2048);
+ FixedBitSet originalCandidates = new FixedBitSet(2048);
+ for (int d = 0; d < 2048; d++) {
+ if (rng.nextInt(5) == 0) {
+ candidates.set(d);
+ originalCandidates.set(d);
+ }
+ }
+
+ iter.applyMask(2048, candidates, 0);
+
+ FixedBitSet extra = candidates.clone();
+ extra.andNot(originalCandidates);
+ assertEquals(
+ "applyMask must never set a bit that wasn't already a candidate", 0, extra.cardinality());
+ }
+
+ /**
+ * Directly tests applyMask() against a linear scan restricted to a random candidate set, across
+ * all block types (YES, NO, MAYBE, YES_IF_PRESENT).
+ */
+ public void testApplyMaskMatchesLinearScanRestrictedToCandidates() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ Random rng = random();
+ FixedBitSet candidates = new FixedBitSet(2048);
+ for (int d = 0; d < 2048; d++) {
+ if (rng.nextBoolean()) {
+ candidates.set(d);
+ }
+ }
+
+ NumericDocValues refValues = docValues(queryMin, queryMax);
+ FixedBitSet expected = new FixedBitSet(2048);
+ for (int d = refValues.nextDoc();
+ d != DocIdSetIterator.NO_MORE_DOCS && d < 2048;
+ d = refValues.nextDoc()) {
+ if (candidates.get(d)
+ && refValues.longValue() >= queryMin
+ && refValues.longValue() <= queryMax) {
+ expected.set(d);
+ }
+ }
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ iter.approximation().nextDoc();
+
+ FixedBitSet actual = candidates.clone();
+ iter.applyMask(2048, actual, 0);
+
+ assertEquals("applyMask must match linear scan restricted to candidates", expected, actual);
+ }
+
+ /** A YES block means every doc in it matches, so its candidate bits must remain untouched. */
+ public void testApplyMaskLeavesYesBlockCandidatesSet() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ iter.approximation().nextDoc();
+
+ // Docs [0, 128) are dense and within [queryMin, queryMax]: a YES block.
+ FixedBitSet candidates = new FixedBitSet(2048);
+ candidates.set(0, 128);
+
+ iter.applyMask(128, candidates, 0);
+
+ assertEquals("Every candidate in a YES block must remain set", 128, candidates.cardinality());
+ }
+
+ /**
+ * A YES_IF_PRESENT block means every doc that has a value matches; applyMask must clear
+ * candidates whose doc has no value while leaving present candidates set.
+ */
+ public void testApplyMaskClearsAbsentCandidatesInYesIfPresentBlock() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ // Docs [1088, 1152) are sparse (only even docs have a value) but every present value is
+ // within [queryMin, queryMax]: a YES_IF_PRESENT block.
+ assertEquals(1088, iter.approximation().advance(1088));
+
+ FixedBitSet candidates = new FixedBitSet(2048);
+ candidates.set(1088, 1152);
+
+ iter.applyMask(1152, candidates, 0);
+
+ for (int d = 1088; d < 1152; d++) {
+ if (d % 2 == 0) {
+ assertTrue(
+ "Present doc " + d + " in a YES_IF_PRESENT block must remain a candidate",
+ candidates.get(d));
+ } else {
+ assertFalse("Absent doc " + d + " must be cleared", candidates.get(d));
+ }
+ }
+ }
+
+ /**
+ * A MAYBE block has no block-level shortcut; applyMask must confirm each candidate doc
+ * individually against the predicate.
+ */
+ public void testApplyMaskConfirmsIndividualCandidatesInMaybeBlock() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ // Docs [512, 1024) mix in-range and out-of-range values depending on (d/2)%3: a MAYBE block.
+ NumericDocValues refValues = docValues(queryMin, queryMax);
+ FixedBitSet expected = new FixedBitSet(2048);
+ for (int d = 512; d < 1024; d++) {
+ refValues.advanceExact(d);
+ if (refValues.longValue() >= queryMin && refValues.longValue() <= queryMax) {
+ expected.set(d);
+ }
+ }
+ assertTrue(
+ "Test requires a genuine mix of matches and non-matches",
+ expected.cardinality() > 0 && expected.cardinality() < 512);
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ iter.approximation().advance(512);
+
+ FixedBitSet candidates = new FixedBitSet(2048);
+ candidates.set(512, 1024);
+ iter.applyMask(1024, candidates, 0);
+
+ assertEquals(
+ "applyMask must confirm each candidate individually in a MAYBE block",
+ expected,
+ candidates);
+ }
+
+ /**
+ * When there are no candidates anywhere in the requested range, applyMask must never touch doc
+ * values -- not even to bulk-scan presence for a YES_IF_PRESENT block or evaluate the predicate
+ * for a MAYBE block.
+ */
+ public void testApplyMaskTouchesNoDocValuesWhenNoCandidates() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ int[] callCount = {0};
+ NumericDocValues delegate = docValues(queryMin, queryMax);
+ NumericDocValues counting =
+ new NumericDocValues() {
+ @Override
+ public long longValue() throws IOException {
+ callCount[0]++;
+ return delegate.longValue();
+ }
+
+ @Override
+ public boolean advanceExact(int target) throws IOException {
+ callCount[0]++;
+ return delegate.advanceExact(target);
+ }
+
+ @Override
+ public int docID() {
+ return delegate.docID();
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ callCount[0]++;
+ return delegate.nextDoc();
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ callCount[0]++;
+ return delegate.advance(target);
+ }
+
+ @Override
+ public long cost() {
+ return delegate.cost();
+ }
+ };
+
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(counting, skipper, queryMin, queryMax);
+ // approximation() is the block iterator over the skipper, not `counting`, so positioning it
+ // never touches doc values.
+ iter.approximation().nextDoc();
+ assertEquals(0, callCount[0]);
+
+ FixedBitSet noCandidates = new FixedBitSet(2048); // nothing is a candidate anywhere
+ iter.applyMask(2048, noCandidates, 0);
+
+ assertEquals(
+ "applyMask must not touch doc values when there are no candidates", 0, callCount[0]);
+ assertEquals(0, noCandidates.cardinality());
+ }
+
+ /** applyMask must leave the approximation positioned at or beyond upTo, mirroring intoBitSet. */
+ public void testApplyMaskAdvancesApproximationToUpTo() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+ DocIdSetIterator approximation = iter.approximation();
+ assertEquals(0, approximation.nextDoc());
+
+ FixedBitSet candidates = new FixedBitSet(2048);
+ candidates.set(0, 128);
+ iter.applyMask(128, candidates, 0);
+
+ assertTrue(
+ "approximation must be positioned at or beyond upTo after applyMask, but was "
+ + approximation.docID(),
+ approximation.docID() >= 128);
+ }
+
+ /**
+ * Regression test for a leading NO-gap: if the caller has already advanced the approximation past
+ * {@code offset} into a {@code [offset, blockStart)} span that doesn't intersect the query range
+ * at all -- as DenseConjunctionBulkScorer does when a middle clause's block covering windowBase
+ * is a NO block -- applyMask must still clear any candidates sitting in that gap rather than
+ * leaving them untouched because no block ever "lands" on them.
+ */
+ public void testApplyMaskClearsLeadingNoGap() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+
+ // 300 is inside the [256, 512) NO region (values queryMin-1, entirely out of range), so
+ // advancing from there jumps straight past it -- exactly what DenseConjunctionBulkScorer's
+ // own advance(windowBase) does for a middle clause.
+ int windowBase = 300;
+ int landedAt = iter.approximation().advance(windowBase);
+ assertTrue(
+ "test requires advancing from within a NO region to jump forward", landedAt > windowBase);
+
+ FixedBitSet candidates = new FixedBitSet(2048 - windowBase);
+ candidates.set(0, candidates.length()); // every doc from windowBase onward is a candidate
+
+ iter.applyMask(2048, candidates, windowBase);
+
+ for (int d = windowBase; d < landedAt; d++) {
+ assertFalse(
+ "doc " + d + " is in the leading NO gap and must be cleared",
+ candidates.get(d - windowBase));
+ }
+ }
+
+ /**
+ * Regression test for the degenerate case where the approximation is already positioned at or
+ * beyond {@code upTo} when applyMask is called, because the whole requested window falls inside a
+ * NO gap. The while loop body never runs, so applyMask must still clear every candidate via the
+ * trailing gap check rather than leaving the loop having done nothing.
+ */
+ public void testApplyMaskWhenApproximationStartsAtOrPastUpTo() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ NumericDocValues values = docValues(queryMin, queryMax);
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(values, skipper, queryMin, queryMax);
+
+ int windowBase = 300;
+ int landedAt = iter.approximation().advance(windowBase);
+ int upTo = windowBase + 50;
+ assertTrue("test requires the approximation to land beyond a small window", landedAt >= upTo);
+
+ FixedBitSet candidates = new FixedBitSet(upTo - windowBase);
+ candidates.set(0, candidates.length());
+
+ iter.applyMask(upTo, candidates, windowBase);
+
+ assertEquals(
+ "the whole window is a NO gap; every candidate must be cleared",
+ 0,
+ candidates.cardinality());
+ }
+
+ /**
+ * Regression test ensuring the MAYBE branch of applyMask keeps confirming via the bulk (SIMD-
+ * capable) {@link NumericDocValues#rangeIntoBitSet} path instead of falling back to a scalar
+ * per-doc {@code matches()} loop, which would silently lose vectorization once a range clause
+ * becomes a trailing clause in a conjunction rather than the sole/leading clause.
+ */
+ public void testApplyMaskMaybeBlockUsesVectorizedPath() throws Exception {
+ long queryMin = 10;
+ long queryMax = 20;
+
+ int[] rangeIntoBitSetCalls = {0};
+ NumericDocValues delegate = docValues(queryMin, queryMax);
+ NumericDocValues counting =
+ new NumericDocValues() {
+ @Override
+ public long longValue() throws IOException {
+ return delegate.longValue();
+ }
+
+ @Override
+ public boolean advanceExact(int target) throws IOException {
+ return delegate.advanceExact(target);
+ }
+
+ @Override
+ public int docID() {
+ return delegate.docID();
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ return delegate.nextDoc();
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ return delegate.advance(target);
+ }
+
+ @Override
+ public long cost() {
+ return delegate.cost();
+ }
+
+ @Override
+ public void rangeIntoBitSet(
+ int fromDoc, int toDoc, long minValue, long maxValue, FixedBitSet bitSet, int offset)
+ throws IOException {
+ rangeIntoBitSetCalls[0]++;
+ super.rangeIntoBitSet(fromDoc, toDoc, minValue, maxValue, bitSet, offset);
+ }
+ };
+
+ DocValuesSkipper skipper = docValuesSkipper(queryMin, queryMax, true);
+ DocValuesRangeIterator iter =
+ DocValuesRangeIterator.forRange(counting, skipper, queryMin, queryMax);
+ // Docs [512, 1024) mix in-range and out-of-range values: a MAYBE region.
+ iter.approximation().advance(512);
+
+ FixedBitSet candidates = new FixedBitSet(2048);
+ candidates.set(512, 1024);
+
+ iter.applyMask(1024, candidates, 0);
+
+ assertTrue(
+ "MAYBE block confirmation must use the vectorized rangeIntoBitSet path, not a scalar"
+ + " per-doc fallback",
+ rangeIntoBitSetCalls[0] > 0);
+ }
+
+ /**
+ * Randomized end-to-end check on a real index: applyMask must match per-doc evaluation restricted
+ * to a random candidate set, across random data and range selectivities.
+ */
+ public void testApplyMaskMatchesPerDocEvaluationOnRealIndex() throws Exception {
+ Random rng = random();
+ for (int iter = 0; iter < 10; iter++) {
+ int numDocs = rng.nextInt(4096, 4096 * 3);
+ long maxValue = rng.nextInt(100, 10000);
+ long rangeMin = rng.nextLong(0, maxValue / 2);
+ long rangeMax = rangeMin + rng.nextLong(1, maxValue / 2);
+
+ try (Directory dir = newDirectory()) {
+ IndexWriterConfig iwc = new IndexWriterConfig().setCodec(new Lucene104Codec());
+ long[] values = new long[numDocs];
+ try (IndexWriter w = new IndexWriter(dir, iwc)) {
+ for (int i = 0; i < numDocs; i++) {
+ values[i] = rng.nextLong(0, maxValue);
+ Document doc = new Document();
+ doc.add(NumericDocValuesField.indexedField("val", values[i]));
+ w.addDocument(doc);
+ }
+ w.forceMerge(1);
+ }
+
+ try (DirectoryReader reader = DirectoryReader.open(dir)) {
+ LeafReaderContext ctx = reader.leaves().get(0);
+ DocValuesSkipper skipper = ctx.reader().getDocValuesSkipper("val");
+ assertNotNull("Field must have a skip index", skipper);
+
+ FixedBitSet candidates = new FixedBitSet(numDocs);
+ for (int d = 0; d < numDocs; d++) {
+ if (rng.nextInt(3) != 0) {
+ candidates.set(d);
+ }
+ }
+
+ FixedBitSet expected = candidates.clone();
+ for (int d = 0; d < numDocs; d++) {
+ if (expected.get(d) && (values[d] < rangeMin || values[d] > rangeMax)) {
+ expected.clear(d);
+ }
+ }
+
+ NumericDocValues dv = ctx.reader().getNumericDocValues("val");
+ DocValuesRangeIterator rangeIter =
+ DocValuesRangeIterator.forRange(dv, skipper, rangeMin, rangeMax);
+ rangeIter.approximation().nextDoc();
+
+ FixedBitSet actual = candidates.clone();
+ rangeIter.applyMask(numDocs, actual, 0);
+
+ assertEquals(
+ "applyMask must match per-doc evaluation restricted to candidates (numDocs="
+ + numDocs
+ + ", range=["
+ + rangeMin
+ + ","
+ + rangeMax
+ + "])",
+ expected,
+ actual);
+ }
+ }
+ }
+ }
+
/**
* Tests that rangeIntoBitSet (SIMD/fast path) produces the exact same results as per-doc
* evaluation (slow path) across random data with various densities and range selectivities.
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestTwoPhaseIterator.java b/lucene/core/src/test/org/apache/lucene/search/TestTwoPhaseIterator.java
new file mode 100644
index 00000000000..4c67d0aba04
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/search/TestTwoPhaseIterator.java
@@ -0,0 +1,222 @@
+/*
+ * 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.util.Random;
+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.FixedBitSet;
+
+/**
+ * Tests the default (non-overridden) {@link TwoPhaseIterator#applyMask} implementation, using
+ * {@link RandomTwoPhaseView} as a generic two-phase iterator whose approximation is a random
+ * superset of the true matches -- exactly the shape {@code applyMask} must handle correctly without
+ * any subclass-specific bulk optimization. {@link RandomTwoPhaseView} itself asserts that {@code
+ * matches()} is never called on an unpositioned doc and never called twice for the same doc, so
+ * these tests also validate that the default implementation drives the two-phase protocol
+ * correctly, not just that it produces the right bits.
+ */
+public class TestTwoPhaseIterator extends LuceneTestCase {
+
+ private static FixedBitSet randomBitSet(Random rng, int numDocs, double density) {
+ FixedBitSet bitSet = new FixedBitSet(numDocs);
+ for (int d = 0; d < numDocs; d++) {
+ if (rng.nextDouble() < density) {
+ bitSet.set(d);
+ }
+ }
+ return bitSet;
+ }
+
+ /**
+ * The default applyMask must match a linear scan restricted to the initial candidates, across
+ * random true-match and candidate densities.
+ */
+ public void testApplyMaskMatchesLinearScanRestrictedToCandidates() throws Exception {
+ Random rng = random();
+ for (int iter = 0; iter < 20; iter++) {
+ int numDocs = TestUtil.nextInt(rng, 100, 5000);
+ double matchDensity = rng.nextDouble();
+ double candidateDensity = rng.nextDouble();
+
+ FixedBitSet trueMatches = randomBitSet(rng, numDocs, matchDensity);
+ FixedBitSet candidates = randomBitSet(rng, numDocs, candidateDensity);
+
+ FixedBitSet expected = candidates.clone();
+ expected.and(trueMatches);
+
+ TwoPhaseIterator twoPhase =
+ new RandomTwoPhaseView(
+ rng, new BitSetIterator(trueMatches, trueMatches.approximateCardinality()));
+ FixedBitSet actual = candidates.clone();
+ twoPhase.applyMask(numDocs, actual, 0);
+
+ assertEquals(
+ "applyMask must match linear scan restricted to candidates (numDocs="
+ + numDocs
+ + ", matchDensity="
+ + matchDensity
+ + ", candidateDensity="
+ + candidateDensity
+ + ")",
+ expected,
+ actual);
+ }
+ }
+
+ /** The default applyMask must never set a bit that wasn't already a candidate. */
+ public void testApplyMaskNeverSetsBitsOutsideInitialCandidates() throws Exception {
+ Random rng = random();
+ int numDocs = TestUtil.nextInt(rng, 100, 5000);
+ FixedBitSet trueMatches = randomBitSet(rng, numDocs, rng.nextDouble());
+ FixedBitSet candidates = randomBitSet(rng, numDocs, rng.nextDouble());
+ FixedBitSet originalCandidates = candidates.clone();
+
+ TwoPhaseIterator twoPhase =
+ new RandomTwoPhaseView(
+ rng, new BitSetIterator(trueMatches, trueMatches.approximateCardinality()));
+ twoPhase.applyMask(numDocs, candidates, 0);
+
+ FixedBitSet extra = candidates.clone();
+ extra.andNot(originalCandidates);
+ assertEquals(
+ "applyMask must never set a bit that wasn't already a candidate", 0, extra.cardinality());
+ }
+
+ /**
+ * applyMask must correctly clear candidates that the approximation doesn't even cover (i.e. a
+ * candidate bit for a doc where approximation().advance() lands past it), without ever calling
+ * matches() for such a doc. RandomTwoPhaseView's approximation is a superset of the true matches
+ * with random extra false-positive positions, so a dense candidate set exercises this alongside
+ * genuine confirmations.
+ */
+ public void testApplyMaskHandlesCandidatesNotReachedByApproximation() throws Exception {
+ Random rng = random();
+ int numDocs = TestUtil.nextInt(rng, 100, 5000);
+ // Sparse true matches so most candidates fall in gaps the approximation may skip over.
+ FixedBitSet trueMatches = randomBitSet(rng, numDocs, 0.01);
+ FixedBitSet candidates = new FixedBitSet(numDocs);
+ candidates.set(0, numDocs); // every doc is a candidate
+
+ FixedBitSet expected = candidates.clone();
+ expected.and(trueMatches);
+
+ TwoPhaseIterator twoPhase =
+ new RandomTwoPhaseView(
+ rng, new BitSetIterator(trueMatches, trueMatches.approximateCardinality()));
+ twoPhase.applyMask(numDocs, candidates, 0);
+
+ assertEquals(expected, candidates);
+ }
+
+ /** applyMask must leave the approximation positioned at or beyond upTo, mirroring intoBitSet. */
+ public void testApplyMaskAdvancesApproximationToUpTo() throws Exception {
+ Random rng = random();
+ int numDocs = TestUtil.nextInt(rng, 100, 5000);
+ FixedBitSet trueMatches = randomBitSet(rng, numDocs, rng.nextDouble());
+ FixedBitSet candidates = randomBitSet(rng, numDocs, rng.nextDouble());
+
+ TwoPhaseIterator twoPhase =
+ new RandomTwoPhaseView(
+ rng, new BitSetIterator(trueMatches, trueMatches.approximateCardinality()));
+ twoPhase.applyMask(numDocs, candidates, 0);
+
+ assertTrue(
+ "approximation must be positioned at or beyond upTo after applyMask, but was "
+ + twoPhase.approximation().docID(),
+ twoPhase.approximation().docID() >= numDocs);
+ }
+
+ /**
+ * The bitSet passed to applyMask may be larger than the requested window ({@code upTo - offset})
+ * -- DenseConjunctionBulkScorer's windowMatches is a fixed WINDOW_SIZE bitset reused across
+ * windows that are often smaller than that. applyMask must not confirm, clear, or otherwise touch
+ * bits at or beyond upTo, even though they're addressable in bitSet.
+ */
+ public void testApplyMaskDoesNotTouchBitsAtOrBeyondUpTo() throws Exception {
+ Random rng = random();
+ int bitSetLength = TestUtil.nextInt(rng, 200, 5000);
+ int upTo = TestUtil.nextInt(rng, 10, bitSetLength - 10); // strictly smaller than bitSetLength
+
+ FixedBitSet trueMatches = randomBitSet(rng, bitSetLength, rng.nextDouble());
+ FixedBitSet candidates = randomBitSet(rng, bitSetLength, rng.nextDouble());
+
+ // Guarantee at least one candidate at or beyond upTo that is a false positive (a candidate
+ // that is NOT a true match): a buggy implementation that processes bits beyond upTo would
+ // observably clear it, since matches() correctly returns false for it.
+ int falsePositiveDoc = TestUtil.nextInt(rng, upTo, bitSetLength - 1);
+ trueMatches.clear(falsePositiveDoc);
+ candidates.set(falsePositiveDoc);
+
+ FixedBitSet original = candidates.clone();
+
+ FixedBitSet expectedBelowUpTo = candidates.clone();
+ expectedBelowUpTo.and(trueMatches);
+
+ TwoPhaseIterator twoPhase =
+ new RandomTwoPhaseView(
+ rng, new BitSetIterator(trueMatches, trueMatches.approximateCardinality()));
+ twoPhase.applyMask(upTo, candidates, 0);
+
+ for (int d = 0; d < upTo; d++) {
+ assertEquals(
+ "bit " + d + " is below upTo and must match linear scan",
+ expectedBelowUpTo.get(d),
+ candidates.get(d));
+ }
+ for (int d = upTo; d < bitSetLength; d++) {
+ assertEquals(
+ "bit " + d + " is at or beyond upTo and must not be touched by applyMask",
+ original.get(d),
+ candidates.get(d));
+ }
+ }
+
+ /**
+ * applyMask must be correct when the mask represents a window offset from doc 0, mirroring how
+ * DenseConjunctionBulkScorer calls it once per window.
+ */
+ public void testApplyMaskWithNonZeroOffset() throws Exception {
+ Random rng = random();
+ int numDocs = TestUtil.nextInt(rng, 1000, 5000);
+ int windowBase = TestUtil.nextInt(rng, 1, numDocs - 500);
+ int windowSize = TestUtil.nextInt(rng, 1, Math.min(500, numDocs - windowBase));
+ int windowMax = windowBase + windowSize;
+
+ FixedBitSet trueMatches = randomBitSet(rng, numDocs, rng.nextDouble());
+ FixedBitSet windowCandidates = randomBitSet(rng, windowSize, rng.nextDouble());
+
+ FixedBitSet expected = new FixedBitSet(windowSize);
+ for (int i = 0; i < windowSize; i++) {
+ if (windowCandidates.get(i) && trueMatches.get(windowBase + i)) {
+ expected.set(i);
+ }
+ }
+
+ TwoPhaseIterator twoPhase =
+ new RandomTwoPhaseView(
+ rng, new BitSetIterator(trueMatches, trueMatches.approximateCardinality()));
+ twoPhase.approximation().advance(windowBase);
+
+ FixedBitSet actual = windowCandidates.clone();
+ twoPhase.applyMask(windowMax, actual, windowBase);
+
+ assertEquals(expected, actual);
+ }
+}