(lucene) branch main updated: Better handle dynamic pruning when the leading clause has a single impact block. (#13904)

[jp...@apache.org]

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 5fd45254d39 Better handle dynamic pruning when the leading clause has a single impact block. (#13904)
5fd45254d39 is described below

commit 5fd45254d39f74cd037ecaf2eb07eee301de3261
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Tue Oct 15 16:17:20 2024 +0200

    Better handle dynamic pruning when the leading clause has a single impact block. (#13904)
    
    `BlockMaxConjunctionBulkScorer` only checks if it can early exit based on
    impacts once per window, and windows are computed using impact blocks of the
    leading clause. So this logic is defeated if the leading clause produces a
    single block (e.g. `ConstantScoreQuery`). This commit addresses this problem by
    artificially lowering the window size to contain ~128 docs of the leading
    clause.
---
 lucene/CHANGES.txt                                      |  4 ++++
 .../lucene/search/BlockMaxConjunctionBulkScorer.java    | 17 ++++++++++++++---
 2 files changed, 18 insertions(+), 3 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 5d9343bca2a..32510a62c5e 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -53,6 +53,10 @@ Optimizations
 * GITHUB#13800: MaxScoreBulkScorer now recomputes scorer partitions when the
   minimum competitive allows for a more favorable partitioning. (Adrien Grand)
 
+* GITHUB#13904: BlockMaxConjunctionBulkScorer can now early exit when the
+  leading clause has a single impact block (e.g. ConstantScoreQuery).
+  (Adrien Grand)
+
 Bug Fixes
 ---------------------
 * GITHUB#13832: Fixed an issue where the DefaultPassageFormatter.format method did not format passages as intended
diff --git a/lucene/core/src/java/org/apache/lucene/search/BlockMaxConjunctionBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/BlockMaxConjunctionBulkScorer.java
index 9f4531540a5..d7e939f4c13 100644
--- a/lucene/core/src/java/org/apache/lucene/search/BlockMaxConjunctionBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/BlockMaxConjunctionBulkScorer.java
@@ -85,9 +85,20 @@ final class BlockMaxConjunctionBulkScorer extends BulkScorer {
 
     int windowMin = Math.max(lead1.docID(), min);
     while (windowMin < max) {
-      // Use impacts of the least costly scorer to compute windows
-      // NOTE: windowMax is inclusive
-      int windowMax = Math.min(scorers[0].advanceShallow(windowMin), max - 1);
+      // Use impacts of the least costly scorer to compute windows to keep the per-block overhead
+      // under control.
+      // NOTE: windowMax is inclusive.
+      int windowMax = scorer1.advanceShallow(windowMin);
+      if (windowMax == DocIdSetIterator.NO_MORE_DOCS) {
+        // If the query doesn't have impacts anymore, or has a single block for the whole doc ID
+        // space (e.g. ConstantScoreQuery), then we try to create a block that has ~128 docs of the
+        // leading clause. This gives us higher chances to exit early based on the maximum scores of
+        // other clauses.
+        long windowSize = 128L * maxDoc / Math.max(1, lead1.cost());
+        windowSize = Math.max(windowSize, 128L);
+        windowMax = (int) Math.min(Integer.MAX_VALUE, windowMin + windowSize);
+      }
+      windowMax = Math.min(windowMax, max - 1);
 
       float maxWindowScore = Float.POSITIVE_INFINITY;
       if (0 < scorable.minCompetitiveScore) {