You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ro...@apache.org on 2026/02/17 09:23:54 UTC

(lucene) branch main updated: Disable skipper-based term competitive iterators if they are not effective (#15709)

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 7501422c2e6 Disable skipper-based term competitive iterators if they are not effective (#15709)
7501422c2e6 is described below

commit 7501422c2e6ba9d2c54353ffed6931cb2880bed3
Author: Alan Woodward <ro...@apache.org>
AuthorDate: Tue Feb 17 09:23:47 2026 +0000

    Disable skipper-based term competitive iterators if they are not effective (#15709)
    
    Skipper-based competitive iterators for term sorts are only useful
    if the field being sorted on has a rough correlation with the overall
    index sort. For cases where these competitive iterators are not
    helping, we detect that no skipping is actually occurring and disable
    the competitive iterator updates, to remove per-document overhead.
---
 lucene/CHANGES.txt                                 |   3 +-
 .../search/comparators/TermOrdValComparator.java   | 112 ++++++++-
 .../TestTermOrdValComparatorAdaptiveSkipping.java  | 249 +++++++++++++++++++++
 3 files changed, 360 insertions(+), 4 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index a610e0ff796..935ecd655e7 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -363,7 +363,8 @@ Optimizations
 
 * GITHUB#15498: ExitableDirectoryReader keeps singleton SortedSetDocValues or SortedNumericDocValues as singletons. (Houston Putman)
 
-* GITHUB#15511, GITHUB#15696: Dynamic pruning for SORTED(_SET) fields with doc values skipper (Pan Guixin, Alan Woodward)
+* GITHUB#15511, GITHUB#15696, GITHUB#15709: Dynamic pruning for SORTED(_SET) fields with doc
+  values skipper (Pan Guixin, Alan Woodward)
 
 * GITHUB#15560: Avoid unnecessary getGraph() call. (Shubham Chaudhary)
 
diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java
index 7b6b45bfc49..6a9962fa356 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java
@@ -38,6 +38,7 @@ import org.apache.lucene.search.Scorable;
 import org.apache.lucene.search.SkipBlockRangeIterator;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.BytesRefBuilder;
+import org.apache.lucene.util.FixedBitSet;
 import org.apache.lucene.util.PriorityQueue;
 
 /**
@@ -196,7 +197,7 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
     return val1.compareTo(val2);
   }
 
-  private class TermOrdValLeafComparator implements LeafFieldComparator {
+  class TermOrdValLeafComparator implements LeafFieldComparator {
 
     /* Current reader's doc ord/values. */
     final SortedDocValues termsIndex;
@@ -488,6 +489,13 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
     public DocIdSetIterator competitiveIterator() {
       return competitiveState != null ? competitiveState.iterator : null;
     }
+
+    // package-private for testing
+    boolean isSkippingDisabled() {
+      // index-based competitive iterators are never disabled
+      return competitiveState instanceof SkipperBasedCompetitiveState skipperState
+          && skipperState.state == SkipperBasedCompetitiveState.State.DISABLED;
+    }
   }
 
   private record PostingsEnumAndOrd(PostingsEnum postings, int ord) {}
@@ -625,17 +633,115 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
   }
 
   private static class SkipperBasedCompetitiveState extends CompetitiveState {
+
+    private static final int WARMUP_BOUNDARY_CROSSINGS = 16;
+
+    private enum State {
+      WARMING,
+      ACTIVE,
+      DISABLED
+    }
+
     private final DocValuesSkipper skipper;
+    private final int maxDoc;
+    private int prevMinOrd = Integer.MIN_VALUE;
+    private int prevMaxOrd = Integer.MIN_VALUE;
+    private State state = State.WARMING;
 
     SkipperBasedCompetitiveState(LeafReaderContext context, DocValuesSkipper skipper) {
       super(context);
       this.skipper = skipper;
-      this.iterator.update(DocIdSetIterator.all(context.reader().maxDoc()));
+      this.maxDoc = context.reader().maxDoc();
+      this.iterator.update(DocIdSetIterator.all(maxDoc));
     }
 
     @Override
     public void update(int minOrd, int maxOrd) {
-      iterator.update(new SkipBlockRangeIterator(skipper, minOrd, maxOrd));
+      if (state == State.DISABLED) {
+        return;
+      }
+      if (minOrd == prevMinOrd && maxOrd == prevMaxOrd) {
+        return;
+      }
+      prevMinOrd = minOrd;
+      prevMaxOrd = maxOrd;
+      iterator.update(
+          new AdaptiveSkipIterator(new SkipBlockRangeIterator(skipper, minOrd, maxOrd)));
+    }
+
+    /**
+     * Wraps a {@link SkipBlockRangeIterator} and monitors whether skipping is effective. Tracks
+     * block boundary crossings using the skipper's level-0 block end so that within-block advances
+     * (which always return target) do not dilute the signal. After {@link
+     * #WARMUP_BOUNDARY_CROSSINGS} boundary crossings with no effective skip observed, the wrapper
+     * disables itself and becomes a trivial pass-through iterator. If any boundary crossing
+     * produces an effective skip, the wrapper stops monitoring and continues using the skip
+     * iterator permanently.
+     */
+    private class AdaptiveSkipIterator extends AbstractDocIdSetIterator {
+      private final SkipBlockRangeIterator in;
+      private int blockEndDoc = -1;
+      private int boundaryCrossings;
+
+      AdaptiveSkipIterator(SkipBlockRangeIterator in) {
+        this.in = in;
+      }
+
+      @Override
+      public int nextDoc() throws IOException {
+        return advance(doc + 1);
+      }
+
+      @Override
+      public int advance(int target) throws IOException {
+        return doc =
+            switch (state) {
+              case DISABLED -> target;
+              case ACTIVE -> in.advance(target);
+              case WARMING -> {
+                int result = in.advance(target);
+                if (target > blockEndDoc) {
+                  blockEndDoc = skipper.maxDocID(0);
+                  boundaryCrossings++;
+                  if (result > target) {
+                    // skipping has happened, so switch to permanently active skipping
+                    state = State.ACTIVE;
+                  } else if (boundaryCrossings >= WARMUP_BOUNDARY_CROSSINGS) {
+                    // we've crossed a number of block boundaries without any skipping
+                    // happening, so it's not helping.  Switch to no skipping to avoid
+                    // overhead.
+                    state = State.DISABLED;
+                    iterator.update(DocIdSetIterator.all(maxDoc));
+                  }
+                }
+                yield result;
+              }
+            };
+      }
+
+      @Override
+      public long cost() {
+        return in.cost();
+      }
+
+      @Override
+      public int docIDRunEnd() throws IOException {
+        if (state == State.DISABLED) {
+          return NO_MORE_DOCS;
+        }
+        return in.docIDRunEnd();
+      }
+
+      @Override
+      public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+        if (state == State.DISABLED) {
+          bitSet.set(doc - offset, upTo - offset);
+          doc = upTo;
+          return;
+        }
+        in.intoBitSet(upTo, bitSet, offset);
+        doc = in.docID();
+      }
     }
   }
 }
diff --git a/lucene/core/src/test/org/apache/lucene/search/comparators/TestTermOrdValComparatorAdaptiveSkipping.java b/lucene/core/src/test/org/apache/lucene/search/comparators/TestTermOrdValComparatorAdaptiveSkipping.java
new file mode 100644
index 00000000000..21641366736
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/search/comparators/TestTermOrdValComparatorAdaptiveSkipping.java
@@ -0,0 +1,249 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search.comparators;
+
+import java.io.IOException;
+import java.util.function.IntFunction;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.SortedDocValuesField;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.FieldDoc;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.LeafFieldComparator;
+import org.apache.lucene.search.Pruning;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.Sort;
+import org.apache.lucene.search.SortField;
+import org.apache.lucene.search.TermQuery;
+import org.apache.lucene.search.TopFieldCollectorManager;
+import org.apache.lucene.search.TopFieldDocs;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.BytesRef;
+
+/**
+ * Tests that the adaptive skipping logic in TermOrdValComparator's SkipperBasedCompetitiveState
+ * preserves correctness across data distributions, and that it disables skipping when the skip
+ * index is ineffective.
+ */
+public class TestTermOrdValComparatorAdaptiveSkipping extends LuceneTestCase {
+
+  private static final String SORT_FIELD_SKIP = "sort.skip";
+  private static final String SORT_FIELD_NO_SKIP = "sort.noskip";
+  private static final String QUERY_FIELD = "match";
+  private static final String QUERY_VALUE = "yes";
+  private static final int NUM_DOCS = 200_000;
+  private static final int NUM_HITS = 10;
+  private static final int TOTAL_HITS_THRESHOLD = 1;
+
+  /**
+   * For interleaved data (alternating values uncorrelated with doc order), the adaptive logic may
+   * disable skipping. Verify that top-N results are identical to the non-skip baseline.
+   */
+  public void testResultsCorrectForInterleavedData() throws Exception {
+    BytesRef a = new BytesRef("a");
+    BytesRef z = new BytesRef("z");
+    try (Directory dir = newDirectory()) {
+      buildIndex(dir, i -> (i & 1) == 0 ? a : z);
+      try (IndexReader reader = DirectoryReader.open(dir)) {
+        assertTopNMatch(new IndexSearcher(reader));
+      }
+    }
+  }
+
+  /**
+   * For clustered data (values sorted with doc order), skipping should remain active and prune
+   * non-competitive blocks. Verify results are correct AND that totalHits is significantly lower
+   * with skipping, showing that the adaptive logic did not incorrectly disable.
+   */
+  public void testSkippingEffectiveForClusteredData() throws Exception {
+    BytesRef a = new BytesRef("a");
+    BytesRef z = new BytesRef("z");
+    try (Directory dir = newDirectory()) {
+      buildIndex(dir, i -> i < NUM_DOCS / 2 ? a : z);
+      try (IndexReader reader = DirectoryReader.open(dir)) {
+        IndexSearcher searcher = new IndexSearcher(reader);
+
+        assertTopNMatch(searcher);
+
+        TopFieldDocs withSkip = searchSort(searcher, SORT_FIELD_SKIP);
+        TopFieldDocs withoutSkip = searchSort(searcher, SORT_FIELD_NO_SKIP);
+
+        assertTrue(
+            "Expected skip-enabled totalHits ("
+                + withSkip.totalHits.value()
+                + ") to be significantly lower than non-skip ("
+                + withoutSkip.totalHits.value()
+                + "), proving skipping was not incorrectly disabled",
+            withSkip.totalHits.value() < withoutSkip.totalHits.value() * 3 / 4);
+      }
+    }
+  }
+
+  /**
+   * For random data, results must still be correct regardless of whether skipping is active or
+   * adaptively disabled.
+   */
+  public void testResultsCorrectForRandomData() throws Exception {
+    BytesRef[] values = new BytesRef[26];
+    for (int i = 0; i < 26; i++) {
+      values[i] = new BytesRef(Character.toString((char) ('a' + i)));
+    }
+    try (Directory dir = newDirectory()) {
+      buildIndex(dir, _ -> values[random().nextInt(values.length)]);
+      try (IndexReader reader = DirectoryReader.open(dir)) {
+        assertTopNMatch(new IndexSearcher(reader));
+      }
+    }
+  }
+
+  /**
+   * Directly exercises the comparator with interleaved data and verifies that adaptive disabling
+   * fires via {@link TermOrdValComparator.TermOrdValLeafComparator#isSkippingDisabled()}.
+   */
+  public void testAdaptiveDisablingFiresForInterleavedData() throws Exception {
+    BytesRef a = new BytesRef("a");
+    BytesRef z = new BytesRef("z");
+    try (Directory dir = newDirectory()) {
+      buildIndex(dir, i -> (i & 1) == 0 ? a : z);
+      try (IndexReader reader = DirectoryReader.open(dir)) {
+        assertEquals(1, reader.leaves().size());
+        LeafReaderContext leafContext = reader.leaves().get(0);
+        int maxDoc = leafContext.reader().maxDoc();
+
+        TermOrdValComparator comparator =
+            new TermOrdValComparator(1, SORT_FIELD_SKIP, false, false, Pruning.GREATER_THAN);
+        LeafFieldComparator leafComp = comparator.getLeafComparator(leafContext);
+        assertTrue(leafComp instanceof TermOrdValComparator.TermOrdValLeafComparator);
+        var typedLeafComp = (TermOrdValComparator.TermOrdValLeafComparator) leafComp;
+
+        leafComp.copy(0, 0);
+        leafComp.setBottom(0);
+        leafComp.setHitsThresholdReached();
+
+        DocIdSetIterator competitiveIter = leafComp.competitiveIterator();
+        assumeTrue(
+            "Competitive iterator not available (codec may not support skip index)",
+            competitiveIter != null);
+
+        assertFalse(
+            "Skipping should not be disabled before iteration", typedLeafComp.isSkippingDisabled());
+
+        // Advance through the entire segment
+        int doc = 0;
+        while (doc < maxDoc) {
+          int next = competitiveIter.advance(doc);
+          if (next == DocIdSetIterator.NO_MORE_DOCS) break;
+          doc = next + 1;
+        }
+
+        assertTrue(
+            "Skipping should be adaptively disabled after traversing interleaved data",
+            typedLeafComp.isSkippingDisabled());
+      }
+    }
+  }
+
+  /**
+   * Directly exercises the comparator with clustered data and verifies that adaptive disabling does
+   * NOT fire, because the skip iterator successfully skips non-competitive blocks.
+   */
+  public void testAdaptiveDisablingDoesNotFireForClusteredData() throws Exception {
+    BytesRef a = new BytesRef("a");
+    BytesRef z = new BytesRef("z");
+    try (Directory dir = newDirectory()) {
+      buildIndex(dir, i -> i < NUM_DOCS / 2 ? a : z);
+      try (IndexReader reader = DirectoryReader.open(dir)) {
+        assertEquals(1, reader.leaves().size());
+        LeafReaderContext leafContext = reader.leaves().get(0);
+        int maxDoc = leafContext.reader().maxDoc();
+
+        TermOrdValComparator comparator =
+            new TermOrdValComparator(1, SORT_FIELD_SKIP, false, false, Pruning.GREATER_THAN);
+        LeafFieldComparator leafComp = comparator.getLeafComparator(leafContext);
+        assertTrue(leafComp instanceof TermOrdValComparator.TermOrdValLeafComparator);
+        var typedLeafComp = (TermOrdValComparator.TermOrdValLeafComparator) leafComp;
+
+        leafComp.copy(0, 0);
+        leafComp.setBottom(0);
+        leafComp.setHitsThresholdReached();
+
+        DocIdSetIterator competitiveIter = leafComp.competitiveIterator();
+        assumeTrue(
+            "Competitive iterator not available (codec may not support skip index)",
+            competitiveIter != null);
+
+        // Advance through the entire segment
+        int doc = 0;
+        while (doc < maxDoc) {
+          int next = competitiveIter.advance(doc);
+          if (next == DocIdSetIterator.NO_MORE_DOCS) break;
+          doc = next + 1;
+        }
+
+        assertFalse(
+            "Skipping should remain active for clustered data", typedLeafComp.isSkippingDisabled());
+      }
+    }
+  }
+
+  private void buildIndex(Directory dir, IntFunction<BytesRef> valueSupplier) throws IOException {
+    IndexWriterConfig config = newIndexWriterConfig();
+    try (IndexWriter writer = new IndexWriter(dir, config)) {
+      for (int i = 0; i < NUM_DOCS; i++) {
+        Document doc = new Document();
+        doc.add(new StringField(QUERY_FIELD, QUERY_VALUE, Field.Store.NO));
+        BytesRef value = valueSupplier.apply(i);
+        doc.add(new SortedDocValuesField(SORT_FIELD_NO_SKIP, value));
+        doc.add(SortedDocValuesField.indexedField(SORT_FIELD_SKIP, value));
+        writer.addDocument(doc);
+      }
+      writer.forceMerge(1);
+    }
+  }
+
+  private void assertTopNMatch(IndexSearcher searcher) throws IOException {
+    TopFieldDocs withSkip = searchSort(searcher, SORT_FIELD_SKIP);
+    TopFieldDocs withoutSkip = searchSort(searcher, SORT_FIELD_NO_SKIP);
+
+    assertEquals(
+        "Top-N result count should match", withSkip.scoreDocs.length, withoutSkip.scoreDocs.length);
+    for (int i = 0; i < withSkip.scoreDocs.length; i++) {
+      FieldDoc skipDoc = (FieldDoc) withSkip.scoreDocs[i];
+      FieldDoc noSkipDoc = (FieldDoc) withoutSkip.scoreDocs[i];
+      assertEquals(
+          "Sort value at position " + i + " should match", skipDoc.fields[0], noSkipDoc.fields[0]);
+    }
+  }
+
+  private TopFieldDocs searchSort(IndexSearcher searcher, String field) throws IOException {
+    Query query = new TermQuery(new Term(QUERY_FIELD, QUERY_VALUE));
+    SortField sortField = new SortField(field, SortField.Type.STRING);
+    Sort sort = new Sort(sortField, SortField.FIELD_SCORE);
+    TopFieldCollectorManager manager =
+        new TopFieldCollectorManager(sort, NUM_HITS, null, TOTAL_HITS_THRESHOLD);
+    return searcher.search(query, manager);
+  }
+}