[lucene] 01/02: LUCENE-10496: avoid unnecessary attempts to evaluate skipping doc if index sort and search sort are in opposite direction (#780)

[jp...@apache.org]

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

commit 6a973cfa269b42f4a77f41a70bdab387bfa37bf9
Author: xiaoping <wj...@gmail.com>
AuthorDate: Wed May 11 17:32:07 2022 +0800

    LUCENE-10496: avoid unnecessary attempts to evaluate skipping doc if index sort and search sort are in opposite direction (#780)
---
 .../search/comparators/NumericComparator.java      | 28 +++++++++++++++++++++-
 1 file changed, 27 insertions(+), 1 deletion(-)

diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
index 1e7bebb9dca..0ac859d40f1 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
@@ -42,6 +42,10 @@ import org.apache.lucene.util.DocIdSetBuilder;
  * but in this case you must override both of these methods.
  */
 public abstract class NumericComparator<T extends Number> extends FieldComparator<T> {
+
+  // MIN_SKIP_INTERVAL and MAX_SKIP_INTERVAL both should be powers of 2
+  private static final int MIN_SKIP_INTERVAL = 32;
+  private static final int MAX_SKIP_INTERVAL = 8192;
   protected final T missingValue;
   protected final String field;
   protected final boolean reverse;
@@ -94,6 +98,9 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
     private long iteratorCost = -1;
     private int maxDocVisited = -1;
     private int updateCounter = 0;
+    private int currentSkipInterval = MIN_SKIP_INTERVAL;
+    // helps to be conservative about increasing the sampling interval
+    private int tryUpdateFailCount = 0;
 
     public NumericLeafComparator(LeafReaderContext context) throws IOException {
       this.docValues = getNumericDocValues(context, field);
@@ -191,8 +198,9 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
       }
 
       updateCounter++;
+      // Start sampling if we get called too much
       if (updateCounter > 256
-          && (updateCounter & 0x1f) != 0x1f) { // Start sampling if we get called too much
+          && (updateCounter & (currentSkipInterval - 1)) != currentSkipInterval - 1) {
         return;
       }
       if (reverse == false) {
@@ -272,11 +280,29 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
       if (estimatedNumberOfMatches >= threshold) {
         // the new range is not selective enough to be worth materializing, it doesn't reduce number
         // of docs at least 8x
+        updateSkipInterval(false);
         return;
       }
       pointValues.intersect(visitor);
       competitiveIterator = result.build().iterator();
       iteratorCost = competitiveIterator.cost();
+      updateSkipInterval(true);
+    }
+
+    private void updateSkipInterval(boolean success) {
+      if (updateCounter > 256) {
+        if (success) {
+          currentSkipInterval = Math.max(currentSkipInterval / 2, MIN_SKIP_INTERVAL);
+          tryUpdateFailCount = 0;
+        } else {
+          if (tryUpdateFailCount >= 3) {
+            currentSkipInterval = Math.min(currentSkipInterval * 2, MAX_SKIP_INTERVAL);
+            tryUpdateFailCount = 0;
+          } else {
+            tryUpdateFailCount++;
+          }
+        }
+      }
     }
 
     @Override