You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2022/12/14 08:58:58 UTC

[lucene] branch branch_9x updated: Add exponential growth to TimeLimitingBulkScorer (#11984)

This is an automated email from the ASF dual-hosted git repository.

jpountz pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/branch_9x by this push:
     new 7ce9dbbf65e Add exponential growth to TimeLimitingBulkScorer (#11984)
7ce9dbbf65e is described below

commit 7ce9dbbf65e522f9b463b8518f247a3e7d6332ae
Author: Costin Leau <co...@users.noreply.github.com>
AuthorDate: Fri Dec 2 09:20:48 2022 -0800

    Add exponential growth to TimeLimitingBulkScorer (#11984)
    
    Increase the timeout check inside TimeLimitBulkScorer at exponential rate.
    
    Fix #11676
---
 lucene/CHANGES.txt                                 |  4 ++
 .../lucene/search/TimeLimitingBulkScorer.java      |  9 +++-
 .../lucene/search/TestTimeLimitingBulkScorer.java  | 60 ++++++++++++++++++++++
 3 files changed, 72 insertions(+), 1 deletion(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index a05b9c1ab7a..323f3181e40 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -42,6 +42,10 @@ API Changes
 
 * GITHUB#11962: VectorValues#cost() now delegates to VectorValues#size().
   (Adrien Grand)
+  
+* GITHUB#11984: Improved TimeLimitBulkScorer to check the timeout at exponantial rate.
+  (Costin Leau)
+
 
 New Features
 ---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java
index 83687491a3d..5e33884ea4f 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java
@@ -61,8 +61,15 @@ final class TimeLimitingBulkScorer extends BulkScorer {
 
   @Override
   public int score(LeafCollector collector, Bits acceptDocs, int min, int max) throws IOException {
+    int interval = INTERVAL;
     while (min < max) {
-      final int newMax = (int) Math.min((long) min + INTERVAL, max);
+      final int newMax = (int) Math.min((long) min + interval, max);
+      final int newInterval =
+          interval + (interval >> 1); // increase the interval by 50% on each iteration
+      // overflow check
+      if (interval < newInterval) {
+        interval = newInterval;
+      }
       if (queryTimeout.shouldExit()) {
         throw new TimeLimitingBulkScorer.TimeExceededException();
       }
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestTimeLimitingBulkScorer.java b/lucene/core/src/test/org/apache/lucene/search/TestTimeLimitingBulkScorer.java
index b4332b46dfb..de5512a904a 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestTimeLimitingBulkScorer.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestTimeLimitingBulkScorer.java
@@ -17,15 +17,18 @@
 
 package org.apache.lucene.search;
 
+import java.io.IOException;
 import org.apache.lucene.document.Document;
 import org.apache.lucene.document.Field;
 import org.apache.lucene.index.DirectoryReader;
 import org.apache.lucene.index.IndexWriter;
 import org.apache.lucene.index.QueryTimeout;
+import org.apache.lucene.index.QueryTimeoutImpl;
 import org.apache.lucene.index.Term;
 import org.apache.lucene.store.Directory;
 import org.apache.lucene.tests.analysis.MockAnalyzer;
 import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.Bits;
 
 /** Tests the {@link TimeLimitingBulkScorer}. */
 public class TestTimeLimitingBulkScorer extends LuceneTestCase {
@@ -62,6 +65,51 @@ public class TestTimeLimitingBulkScorer extends LuceneTestCase {
     directory.close();
   }
 
+  public void testExponentialRate() throws Exception {
+    int MAX_DOCS = DocIdSetIterator.NO_MORE_DOCS - 1;
+    var bulkScorer =
+        new BulkScorer() {
+          int expectedInterval = TimeLimitingBulkScorer.INTERVAL;
+          int lastMax = 0;
+          int lastInterval = 0;
+
+          @Override
+          public int score(LeafCollector collector, Bits acceptDocs, int min, int max)
+              throws IOException {
+            var difference = max - min;
+            // the rate shouldn't overflow - only increase or remain equal
+            assertTrue("Rate should only go up", difference >= lastInterval);
+            // make sure no documents end up being skipped
+            assertTrue("Documents skipped", lastMax == min);
+            // the difference should be exactly the step except the last run where the difference is
+            // smaller since there are not enough docs
+            assertTrue(
+                "Incorrect rate encountered",
+                max == MAX_DOCS ? expectedInterval >= difference : expectedInterval == difference);
+
+            lastMax = max;
+            lastInterval = difference;
+
+            // use integer sum since the exponential growth formula yields different result due to
+            // rounding
+            expectedInterval = expectedInterval + expectedInterval / 2;
+            // overflow - stop at the previous one
+            if (expectedInterval < 0) {
+              expectedInterval = lastInterval;
+            }
+            return max;
+          }
+
+          @Override
+          public long cost() {
+            return 1;
+          }
+        };
+
+    var scorer = new TimeLimitingBulkScorer(bulkScorer, new QueryTimeoutImpl(-1));
+    scorer.score(dummyCollector(), new Bits.MatchAllBits(Integer.MAX_VALUE), 0, MAX_DOCS);
+  }
+
   private static QueryTimeout countingQueryTimeout(int timeallowed) {
 
     return new QueryTimeout() {
@@ -77,4 +125,16 @@ public class TestTimeLimitingBulkScorer extends LuceneTestCase {
       }
     };
   }
+
+  private static LeafCollector dummyCollector() {
+    return new SimpleCollector() {
+      @Override
+      public ScoreMode scoreMode() {
+        return ScoreMode.COMPLETE_NO_SCORES;
+      }
+
+      @Override
+      public void collect(int doc) throws IOException {}
+    };
+  }
 }