(lucene) branch main updated: Optimize MUST_NOT scoring based on required-clause selectivity (#16715)

[ro...@apache.org]

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 48a97520c26 Optimize MUST_NOT scoring based on required-clause selectivity (#16715)
48a97520c26 is described below

commit 48a97520c26ffb9182b4feadcdb03dbdc77171cf
Author: kkewwei <ke...@bytedance.com>
AuthorDate: Fri Oct 9 00:16:28 2026 +0800

    Optimize MUST_NOT scoring based on required-clause selectivity (#16715)
    
    When a required clause is sparser than an exclusion clause, using
    ReqExclBulkScorer can waste lots of time building its exclusion bitset
    against documents that would not be matched by the required clause
    in the first place.  For sufficiently sparse required clauses, we now
    fall back to using doc-by-doc scoring.
    
    In addition, the exclusion scorer is always built with a maximum lead
    cost in the bulk scorer to avoid using scorers with slow intoBitSet
    implementations.
---
 lucene/CHANGES.txt                                          |  2 ++
 .../org/apache/lucene/search/BooleanScorerSupplier.java     | 13 +++++++++++--
 .../org/apache/lucene/search/TestBooleanScorerSupplier.java |  3 +++
 3 files changed, 16 insertions(+), 2 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 2e519823e89..279700c709d 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -612,6 +612,8 @@ Optimizations
 * GITHUB#16667: Rewrite BooleanQuery to MatchNoDocsQuery when it has MUST_NOT clause matching one of
   its MUST boost or constant score query clauses. (Egor Potemkin)
 
+* GITHUB#16715: Optimize MUST_NOT scoring based on required-clause selectivity. (Ke Wei)
+
 * GITHUB#16769: Merges now also open their own mapping of the raw vectors behind the Faiss format,
   and the merge mapping keeps the hints the file was opened with, changing only how it is read.
   (Jim Ferenczi)
diff --git a/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java b/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java
index dbac4e61050..55d2be36d3e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java
+++ b/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java
@@ -200,6 +200,12 @@ final class BooleanScorerSupplier extends ScorerSupplier {
     final int numMustClauses = subs.get(Occur.MUST).size();
     final int numRequiredClauses = numMustClauses + subs.get(Occur.FILTER).size();
 
+    // ReqExclScorer avoids the overhead of bulk-loading prohibited matches when required clauses
+    // match at most 0.3% of documents; denser required clauses benefit from ReqExclBulkScorer.
+    if (subs.get(Occur.MUST_NOT).isEmpty() == false && cost() <= 3L * maxDoc / 1000) {
+      return null;
+    }
+
     BulkScorer positiveScorer;
     if (numRequiredClauses == 0) {
       // TODO: what is the right heuristic here?
@@ -238,16 +244,19 @@ final class BooleanScorerSupplier extends ScorerSupplier {
     if (positiveScorer == null) {
       return null;
     }
-    final long positiveScorerCost = positiveScorer.cost();
 
+    // Prohibited clauses are bulk-loaded within each window, so use an unbounded lead cost
+    // when selecting their implementations. Keep positiveScorerCost for the disjunction
+    // since the positive side drives which windows need exclusion.
     List<Scorer> prohibited = new ArrayList<>();
     for (ScorerSupplier ss : subs.get(Occur.MUST_NOT)) {
-      prohibited.add(ss.get(positiveScorerCost));
+      prohibited.add(ss.get(Long.MAX_VALUE));
     }
 
     if (prohibited.isEmpty()) {
       return positiveScorer;
     } else {
+      final long positiveScorerCost = positiveScorer.cost();
       Scorer prohibitedScorer =
           prohibited.size() == 1
               ? prohibited.get(0)
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestBooleanScorerSupplier.java b/lucene/core/src/test/org/apache/lucene/search/TestBooleanScorerSupplier.java
index 09910bf4085..6170764e215 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestBooleanScorerSupplier.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestBooleanScorerSupplier.java
@@ -432,6 +432,9 @@ public class TestBooleanScorerSupplier extends LuceneTestCase {
     new BooleanScorerSupplier(
             new FakeWeight(), subs, RandomPicks.randomFrom(random(), ScoreMode.values()), 0, 100)
         .get(100); // triggers assertions as a side-effect
+    subs.get(Occur.MUST_NOT).clear();
+    // MUST_NOT clauses must use an unbounded lead cost for bulk scoring.
+    subs.get(Occur.MUST_NOT).add(new FakeScorerSupplier(80, Long.MAX_VALUE));
     new BooleanScorerSupplier(
             new FakeWeight(), subs, RandomPicks.randomFrom(random(), ScoreMode.values()), 0, 100)
         .bulkScorer(); // triggers assertions as a side-effect