(lucene) branch main updated: GITHUB#12370: early-terminate string sort when field is missing from the whole index (#16411)

[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 c541d76048f GITHUB#12370: early-terminate string sort when field is missing from the whole index (#16411)
c541d76048f is described below

commit c541d76048f0e0fbb0da35f91d8fa8198bf5fb91
Author: Serhiy Bzhezytskyy <me...@serhiy-bzhezytskyy.com>
AuthorDate: Mon Aug 10 16:48:06 2026 +0300

    GITHUB#12370: early-terminate string sort when field is missing from the whole index (#16411)
    
    When sorting on a string (SortedSet/SortedDoc) field that does not exist
    anywhere in the index and the sort has no tie breaker, all documents tie on
    the missing value. Once the top-N queue is full, a further missing value can
    no longer compete, so the remaining documents should be skipped instead of
    fully collected.
---
 lucene/CHANGES.txt                                 |   6 ++
 .../search/comparators/TermOrdValComparator.java   |  13 ++-
 .../apache/lucene/search/TestSortOptimization.java | 118 +++++++++++++++++++++
 3 files changed, 135 insertions(+), 2 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 410fb5bb3ab..5d0775a30de 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -406,6 +406,12 @@ Optimizations
 
 * GITHUB#16180: Add bulk intoBitSet for SortedDocValues ordinal ranges. (Prithvi S)
 
+* GITHUB#12370: Sorting on a string field no longer scans every document when the top-N queue fills
+  with missing values -- whether because the field is missing from the whole index, or because
+  sort-missing-first put missing values at the top. When the sort has no tie breaker, a further
+  missing value cannot displace one already in the queue, so the rest can be skipped.
+  (Serhiy Bzhezytskyy)
+
 Bug Fixes
 ---------------------
 
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 406f5061224..23b6ece00d4 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
@@ -297,8 +297,10 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
       if (dense || topValue != null) {
         return true;
       } else if (reverse == sortMissingLast) {
-        // Missing values are always competitive, we can never skip
-        return false;
+        // Missing values sort best here, so they stay competitive for as long as the queue is not
+        // full of them. With no tie breaker they stop competing once it is, so skipping is still
+        // worth enabling; updateCompetitiveIterator decides when it can actually start.
+        return singleSort;
       } else {
         return true;
       }
@@ -434,6 +436,13 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
           }
         } else if (sortMissingLast || dense) {
           minOrd = 0;
+        } else if (bottomValue == null && singleSort) {
+          // The worst entry in the queue is itself a missing value and there is no tie breaker, so
+          // another missing value can no longer compete: missing values are no longer competitive.
+          // (bottomValue==null is stronger than bottomOrd==missingOrd, which can also be produced
+          // by
+          // a real value that maps before ord 0 in this segment.)
+          minOrd = 0;
         } else {
           // Missing values are still competitive.
           minOrd = -1;
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java b/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
index 2442d7dbf21..e0afe589fdd 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
@@ -1239,6 +1239,124 @@ public class TestSortOptimization extends LuceneTestCase {
     dir.close();
   }
 
+  /**
+   * GITHUB#12370: when the sort field is missing from the whole index (not just one segment) and
+   * the sort has no tie breaker, all documents tie on the missing value, so once the top-N queue is
+   * full the remaining documents are non-competitive and must be skipped rather than fully
+   * collected.
+   */
+  public void testStringSortOptimizationFieldMissingInWholeIndex() throws IOException {
+    final Directory dir = newDirectory();
+    final IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig());
+
+    // None of the documents index the sort field, so it is absent from every segment's FieldInfos.
+    final int numDocs = atLeast(10000);
+    for (int i = 0; i < numDocs; i++) {
+      final Document doc = new Document();
+      doc.add(new StringField("other", Integer.toString(i), Field.Store.NO));
+      writer.addDocument(doc);
+    }
+
+    final DirectoryReader reader = DirectoryReader.open(writer);
+    writer.close();
+
+    final int numHits = 5;
+
+    { // ascending, sort-missing-first (the default for SortedSetSortField): missing is the best
+      // value, but with no tie breaker a second missing value can never displace one already in the
+      // queue, so the tail should be skipped.
+      SortField sortField = new SortedSetSortField("field_does_not_exist", false);
+      TopDocs topDocs = assertSearchHits(reader, new Sort(sortField), numHits, null);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value(), numDocs);
+    }
+
+    { // descending, sort-missing-first
+      SortField sortField = new SortedSetSortField("field_does_not_exist", true);
+      TopDocs topDocs = assertSearchHits(reader, new Sort(sortField), numHits, null);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value(), numDocs);
+    }
+
+    reader.close();
+    dir.close();
+  }
+
+  /**
+   * GITHUB#12370: every document carries the SAME single value for the sort field, so with no tie
+   * breaker they all compare equal and the tail is non-competitive once the queue is full, exactly
+   * as when the field is missing from every segment.
+   */
+  public void testStringSortOptimizationSingleValueInWholeIndex() throws IOException {
+    final Directory dir = newDirectory();
+    final IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig());
+
+    final int numDocs = atLeast(10000);
+    for (int i = 0; i < numDocs; i++) {
+      final Document doc = new Document();
+      doc.add(new SortedDocValuesField("field", new BytesRef("the only value")));
+      doc.add(new StringField("field", "the only value", Field.Store.NO));
+      doc.add(new StringField("other", Integer.toString(i), Field.Store.NO));
+      writer.addDocument(doc);
+    }
+
+    final DirectoryReader reader = DirectoryReader.open(writer);
+    writer.close();
+
+    final int numHits = 5;
+
+    { // ascending
+      SortField sortField = new SortField("field", SortField.Type.STRING, false);
+      TopDocs topDocs = assertSearchHits(reader, new Sort(sortField), numHits, null);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value(), numDocs);
+    }
+
+    { // descending
+      SortField sortField = new SortField("field", SortField.Type.STRING, true);
+      TopDocs topDocs = assertSearchHits(reader, new Sort(sortField), numHits, null);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value(), numDocs);
+    }
+
+    reader.close();
+    dir.close();
+  }
+
+  /**
+   * GITHUB#12370, the remaining case: the sort field DOES exist and some documents have a value,
+   * but with sort-missing-first the top-N queue fills entirely with missing values. With no tie
+   * breaker a further missing value cannot displace one already in the queue, so the tail must be
+   * skipped.
+   */
+  public void testStringSortOptimizationQueueAllMissingSortMissingFirst() throws IOException {
+    final Directory dir = newDirectory();
+    final IndexWriter writer = new IndexWriter(dir, new IndexWriterConfig());
+
+    // Most documents lack the sort field, a few carry a value, so the field is present in
+    // FieldInfos but not dense -- unlike the missing-from-the-whole-index case above.
+    final int numDocs = atLeast(10000);
+    for (int i = 0; i < numDocs; i++) {
+      final Document doc = new Document();
+      if (i % 1000 == 0) {
+        doc.add(new SortedDocValuesField("field", new BytesRef("value" + i)));
+        doc.add(new StringField("field", "value" + i, Field.Store.NO));
+      }
+      doc.add(new StringField("other", Integer.toString(i), Field.Store.NO));
+      writer.addDocument(doc);
+    }
+
+    final DirectoryReader reader = DirectoryReader.open(writer);
+    writer.close();
+
+    final int numHits = 5;
+
+    // sortMissingFirst ascending: missing sorts best, so the queue is all-missing once full.
+    SortField sortField =
+        new SortField("field", SortField.Type.STRING, false, SortField.STRING_FIRST);
+    TopDocs topDocs = assertSearchHits(reader, new Sort(sortField), numHits, null);
+    assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value(), numDocs);
+
+    reader.close();
+    dir.close();
+  }
+
   private void doTestStringSortOptimization(DirectoryReader reader) throws IOException {
     final int numDocs = reader.numDocs();
     final int numHits = 5;