You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "romseygeek (via GitHub)" <gi...@apache.org> on 2026/07/06 12:24:44 UTC

[PR] Add TwoPhaseIterator.applyMask() method [lucene]

romseygeek opened a new pull request, #16362:
URL: https://github.com/apache/lucene/pull/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.
   
   We add 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.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add TwoPhaseIterator.applyMask() method [lucene]

Posted by "jimczi (via GitHub)" <gi...@apache.org>.
jimczi commented on code in PR #16362:
URL: https://github.com/apache/lucene/pull/16362#discussion_r3529348136


##########
lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java:
##########
@@ -364,6 +359,75 @@ public final void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IO
     /** 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 {
+      FixedBitSet scratch = null;
+      while (blockIterator.docID() < upTo) {

Review Comment:
   **Correctness: leading NO-gap candidates are never cleared.**
   
   This loop starts at `blockStart = blockIterator.docID()`, i.e. the first *matching* block `>= windowBase`, and only clears NO-gaps *between* and *after* processed blocks. It never clears `[offset, firstBlockStart)`, and if the block iterator starts `>= upTo` the loop body doesn't run and **nothing** is cleared — even though no doc in the window matches this clause. The removed dense path got this for free (`intoBitSet(...)` then `windowMatches.and(...)` zeroes the leading gap); the default `applyMask` also handles it by walking every candidate.
   
   Not reachable with a simple two-clause conjunction (the sole trailing two-phase clause always sits exactly at `windowBase` after `scoreWindow`'s alignment loop). It needs **3+ driving iterators** so the offending range is a *middle* clause — e.g. `+term +field1:[a TO b] +field2:[c TO d]` (all skip-indexed), three range filters, or a range + collector `competitiveIterator()`. A later clause raises `min` past the range's block, then `scoreWindowUsingBitSet` re-advances it to `windowBase`; if the block covering `windowBase` is a NO block, `advance` lands past `windowBase` and the leading candidate bits survive → docs that pass the lead clause but violate the range are collected as false matches.
   
   Suggest clearing ahead of each block, not just after it: track a cursor from `offset`, clear `[cursor, blockStart)` before each block and `[cursor, upTo)` after the loop. Worth a regression test with a non-zero `offset`, a leading NO-gap, and the approximation-`>= upTo` case — the current tests all position the approximation at the first candidate, so this path is uncovered.



##########
lucene/core/src/java/org/apache/lucene/search/TwoPhaseIterator.java:
##########
@@ -144,4 +144,39 @@ public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOExcept
       }
     }
   }
+
+  /**
+   * 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();
+    for (int i = bitSet.nextSetBit(0);
+        i != DocIdSetIterator.NO_MORE_DOCS;
+        i = i + 1 >= bitSet.length() ? DocIdSetIterator.NO_MORE_DOCS : bitSet.nextSetBit(i + 1)) {

Review Comment:
   Minor: this loop is bounded by `bitSet.length()` rather than `upTo - offset`, so the default `applyMask` will confirm/clear candidate bits for docs `>= upTo` and can advance the approximation past `upTo`. The `DocValuesRangeIterator` override strictly stops at `upTo`, so the two implementations disagree on bits beyond `upTo`. Latent today (the sole caller's `windowMatches` has no set bits `>= windowMax - windowBase`), but for a newly public method it'd be safer to bound by `upTo - offset` to match the override and `intoBitSet` semantics.



##########
lucene/core/src/java/org/apache/lucene/search/DocValuesRangeIterator.java:
##########
@@ -364,6 +359,75 @@ public final void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IO
     /** 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 {
+      FixedBitSet scratch = null;
+      while (blockIterator.docID() < upTo) {
+        int blockStart = blockIterator.docID();
+        SkipBlockRangeIterator.Match match = blockIterator.getMatch();
+        int blockEnd = blockEnd(upTo, match);
+
+        switch (match) {
+          case YES -> {
+            // Every doc in the block matches; candidate bits are already correct, nothing to
+            // confirm.
+          }
+          case YES_IF_PRESENT -> {
+            // All present values are in range, so only docs with no value need to be excluded.
+            // Skip the block entirely, without touching doc values, if it has no candidates.
+            // Otherwise bulk-scan disi's (possibly vectorized) presence for just this block into a
+            // scratch bitset sized to the block, then AND it into the candidate bits for the
+            // block's range -- this keeps the bulk scan while leaving candidate bits outside the
+            // block untouched.
+            if (bitSet.nextSetBit(blockStart - offset, blockEnd - offset)
+                != DocIdSetIterator.NO_MORE_DOCS) {
+              if (disi.docID() < blockStart) {
+                disi.advance(blockStart);
+              }
+              int blockLength = blockEnd - blockStart;
+              if (scratch == null || scratch.length() < blockLength) {
+                scratch = new FixedBitSet(blockLength);
+              }
+              disi.intoBitSet(blockEnd, scratch, blockStart);
+              FixedBitSet.andRange(scratch, 0, bitSet, blockStart - offset, blockLength);
+              scratch.clear(0, blockLength);
+            }
+          }
+          case MAYBE -> {

Review Comment:
   **The MAYBE branch drops the vectorized path for dense candidate windows.**
   
   This confirms candidates one at a time (scalar `advance` + `matches()`), whereas `intoBitSet`'s MAYBE case delegates to `intoMaybeBlock` → `numericValues.rangeIntoBitSet(...)` (SIMD). A *single* range query keeps SIMD because the range is the leading clause (`intoBitSet`), but in a conjunction the range sorts after plain approximations and becomes a *trailing* clause → `applyMask`. Since `WINDOW_SIZE == 4096 ==` the skip-block size, a dense candidate window is typically one MAYBE block — exactly where the old `bulkConfirmThreshold` split used the vectorized decode. So this reintroduces the doc-values range regression the PR is trying to avoid, just relocated to the conjunction case.
   
   The `YES_IF_PRESENT` branch just above already shows the fix shape: bulk-scan into a `scratch` bitset, then `FixedBitSet.andRange(scratch, ...)`. The MAYBE branch could do the same with `rangeIntoBitSet` into `scratch` — keeping SIMD while still never confirming a doc another clause already excluded.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add TwoPhaseIterator.applyMask() method [lucene]

Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek merged PR #16362:
URL: https://github.com/apache/lucene/pull/16362


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Add TwoPhaseIterator.applyMask() method [lucene]

Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on PR #16362:
URL: https://github.com/apache/lucene/pull/16362#issuecomment-4894873798

   Thanks for the review @jimczi!  I added tests for the cases you picked up and pushed fixes. 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org