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/07/29 09:20:40 UTC

[lucene] branch branch_9x updated: LUCENE-10633: Dynamic pruning for sorting on SORTED(_SET) fields. (#1023)

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 261db55806c LUCENE-10633: Dynamic pruning for sorting on SORTED(_SET) fields. (#1023)
261db55806c is described below

commit 261db55806cd352520e406d5e5a684ce45afa9f4
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Fri Jul 29 11:12:32 2022 +0200

    LUCENE-10633: Dynamic pruning for sorting on SORTED(_SET) fields. (#1023)
    
    This commit enables dynamic pruning for queries sorted on SORTED(_SET) fields
    by using postings to filter competitive documents.
---
 lucene/CHANGES.txt                                 |   4 +
 .../org/apache/lucene/search/FieldComparator.java  | 277 ----------
 .../java/org/apache/lucene/search/SortField.java   |   4 +-
 .../apache/lucene/search/SortedSetSortField.java   |   4 +-
 .../search/comparators/TermOrdValComparator.java   | 608 +++++++++++++++++++++
 .../apache/lucene/search/TestSortOptimization.java | 265 +++++++++
 .../search/join/ToParentBlockJoinSortField.java    |  35 +-
 7 files changed, 900 insertions(+), 297 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 28ad9fa2e00..fbaa99d3301 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -24,6 +24,10 @@ Optimizations
 
 * GITHUB#1020: Support #scoreSupplier and small optimizations to DocValuesRewriteMethod. (Greg Miller)
 
+* LUCENE-10633: Added support for dynamic pruning to queries sorted by a string
+  field that is indexed with terms and SORTED or SORTED_SET doc values.
+  (Adrien Grand)
+
 Bug Fixes
 ---------------------
 (No changes)
diff --git a/lucene/core/src/java/org/apache/lucene/search/FieldComparator.java b/lucene/core/src/java/org/apache/lucene/search/FieldComparator.java
index e92436c423c..99c5a480ed1 100644
--- a/lucene/core/src/java/org/apache/lucene/search/FieldComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/FieldComparator.java
@@ -20,7 +20,6 @@ import java.io.IOException;
 import org.apache.lucene.index.BinaryDocValues;
 import org.apache.lucene.index.DocValues;
 import org.apache.lucene.index.LeafReaderContext;
-import org.apache.lucene.index.SortedDocValues;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.BytesRefBuilder;
 
@@ -211,282 +210,6 @@ public abstract class FieldComparator<T> {
     }
   }
 
-  /**
-   * Sorts by field's natural Term sort order, using ordinals. This is functionally equivalent to
-   * {@link org.apache.lucene.search.FieldComparator.TermValComparator}, but it first resolves the
-   * string to their relative ordinal positions (using the index returned by {@link
-   * org.apache.lucene.index.LeafReader#getSortedDocValues(String)}), and does most comparisons
-   * using the ordinals. For medium to large results, this comparator will be much faster than
-   * {@link org.apache.lucene.search.FieldComparator.TermValComparator}. For very small result sets
-   * it may be slower.
-   */
-  public static class TermOrdValComparator extends FieldComparator<BytesRef>
-      implements LeafFieldComparator {
-    /* Ords for each slot.
-    @lucene.internal */
-    final int[] ords;
-
-    /* Values for each slot.
-    @lucene.internal */
-    final BytesRef[] values;
-    private final BytesRefBuilder[] tempBRs;
-
-    /* Which reader last copied a value into the slot. When
-    we compare two slots, we just compare-by-ord if the
-    readerGen is the same; else we must compare the
-    values (slower).
-    @lucene.internal */
-    final int[] readerGen;
-
-    /* Gen of current reader we are on.
-    @lucene.internal */
-    int currentReaderGen = -1;
-
-    /* Current reader's doc ord/values.
-    @lucene.internal */
-    SortedDocValues termsIndex;
-
-    private final String field;
-
-    /* Bottom slot, or -1 if queue isn't full yet
-    @lucene.internal */
-    int bottomSlot = -1;
-
-    /* Bottom ord (same as ords[bottomSlot] once bottomSlot
-    is set).  Cached for faster compares.
-    @lucene.internal */
-    int bottomOrd;
-
-    /* True if current bottom slot matches the current
-    reader.
-    @lucene.internal */
-    boolean bottomSameReader;
-
-    /* Bottom value (same as values[bottomSlot] once
-     bottomSlot is set).  Cached for faster compares.
-    @lucene.internal */
-    BytesRef bottomValue;
-
-    /** Set by setTopValue. */
-    BytesRef topValue;
-
-    boolean topSameReader;
-    int topOrd;
-
-    /** -1 if missing values are sorted first, 1 if they are sorted last */
-    final int missingSortCmp;
-
-    /** Which ordinal to use for a missing value. */
-    final int missingOrd;
-
-    /** Creates this, sorting missing values first. */
-    public TermOrdValComparator(int numHits, String field) {
-      this(numHits, field, false);
-    }
-
-    /**
-     * Creates this, with control over how missing values are sorted. Pass sortMissingLast=true to
-     * put missing values at the end.
-     */
-    public TermOrdValComparator(int numHits, String field, boolean sortMissingLast) {
-      ords = new int[numHits];
-      values = new BytesRef[numHits];
-      tempBRs = new BytesRefBuilder[numHits];
-      readerGen = new int[numHits];
-      this.field = field;
-      if (sortMissingLast) {
-        missingSortCmp = 1;
-        missingOrd = Integer.MAX_VALUE;
-      } else {
-        missingSortCmp = -1;
-        missingOrd = -1;
-      }
-    }
-
-    private int getOrdForDoc(int doc) throws IOException {
-      if (termsIndex.advanceExact(doc)) {
-        return termsIndex.ordValue();
-      } else {
-        return -1;
-      }
-    }
-
-    @Override
-    public int compare(int slot1, int slot2) {
-      if (readerGen[slot1] == readerGen[slot2]) {
-        return ords[slot1] - ords[slot2];
-      }
-
-      final BytesRef val1 = values[slot1];
-      final BytesRef val2 = values[slot2];
-      if (val1 == null) {
-        if (val2 == null) {
-          return 0;
-        }
-        return missingSortCmp;
-      } else if (val2 == null) {
-        return -missingSortCmp;
-      }
-      return val1.compareTo(val2);
-    }
-
-    @Override
-    public int compareBottom(int doc) throws IOException {
-      assert bottomSlot != -1;
-      int docOrd = getOrdForDoc(doc);
-      if (docOrd == -1) {
-        docOrd = missingOrd;
-      }
-      if (bottomSameReader) {
-        // ord is precisely comparable, even in the equal case
-        return bottomOrd - docOrd;
-      } else if (bottomOrd >= docOrd) {
-        // the equals case always means bottom is > doc
-        // (because we set bottomOrd to the lower bound in
-        // setBottom):
-        return 1;
-      } else {
-        return -1;
-      }
-    }
-
-    @Override
-    public void copy(int slot, int doc) throws IOException {
-      int ord = getOrdForDoc(doc);
-      if (ord == -1) {
-        ord = missingOrd;
-        values[slot] = null;
-      } else {
-        assert ord >= 0;
-        if (tempBRs[slot] == null) {
-          tempBRs[slot] = new BytesRefBuilder();
-        }
-        tempBRs[slot].copyBytes(termsIndex.lookupOrd(ord));
-        values[slot] = tempBRs[slot].get();
-      }
-      ords[slot] = ord;
-      readerGen[slot] = currentReaderGen;
-    }
-
-    /** Retrieves the SortedDocValues for the field in this segment */
-    protected SortedDocValues getSortedDocValues(LeafReaderContext context, String field)
-        throws IOException {
-      return DocValues.getSorted(context.reader(), field);
-    }
-
-    @Override
-    public LeafFieldComparator getLeafComparator(LeafReaderContext context) throws IOException {
-      termsIndex = getSortedDocValues(context, field);
-      currentReaderGen++;
-
-      if (topValue != null) {
-        // Recompute topOrd/SameReader
-        int ord = termsIndex.lookupTerm(topValue);
-        if (ord >= 0) {
-          topSameReader = true;
-          topOrd = ord;
-        } else {
-          topSameReader = false;
-          topOrd = -ord - 2;
-        }
-      } else {
-        topOrd = missingOrd;
-        topSameReader = true;
-      }
-      // System.out.println("  getLeafComparator topOrd=" + topOrd + " topSameReader=" +
-      // topSameReader);
-
-      if (bottomSlot != -1) {
-        // Recompute bottomOrd/SameReader
-        setBottom(bottomSlot);
-      }
-
-      return this;
-    }
-
-    @Override
-    public void setBottom(final int bottom) throws IOException {
-      bottomSlot = bottom;
-
-      bottomValue = values[bottomSlot];
-      if (currentReaderGen == readerGen[bottomSlot]) {
-        bottomOrd = ords[bottomSlot];
-        bottomSameReader = true;
-      } else {
-        if (bottomValue == null) {
-          // missingOrd is null for all segments
-          assert ords[bottomSlot] == missingOrd;
-          bottomOrd = missingOrd;
-          bottomSameReader = true;
-          readerGen[bottomSlot] = currentReaderGen;
-        } else {
-          final int ord = termsIndex.lookupTerm(bottomValue);
-          if (ord < 0) {
-            bottomOrd = -ord - 2;
-            bottomSameReader = false;
-          } else {
-            bottomOrd = ord;
-            // exact value match
-            bottomSameReader = true;
-            readerGen[bottomSlot] = currentReaderGen;
-            ords[bottomSlot] = bottomOrd;
-          }
-        }
-      }
-    }
-
-    @Override
-    public void setTopValue(BytesRef value) {
-      // null is fine: it means the last doc of the prior
-      // search was missing this value
-      topValue = value;
-      // System.out.println("setTopValue " + topValue);
-    }
-
-    @Override
-    public BytesRef value(int slot) {
-      return values[slot];
-    }
-
-    @Override
-    public int compareTop(int doc) throws IOException {
-
-      int ord = getOrdForDoc(doc);
-      if (ord == -1) {
-        ord = missingOrd;
-      }
-
-      if (topSameReader) {
-        // ord is precisely comparable, even in the equal
-        // case
-        // System.out.println("compareTop doc=" + doc + " ord=" + ord + " ret=" + (topOrd-ord));
-        return topOrd - ord;
-      } else if (ord <= topOrd) {
-        // the equals case always means doc is < value
-        // (because we set lastOrd to the lower bound)
-        return 1;
-      } else {
-        return -1;
-      }
-    }
-
-    @Override
-    public int compareValues(BytesRef val1, BytesRef val2) {
-      if (val1 == null) {
-        if (val2 == null) {
-          return 0;
-        }
-        return missingSortCmp;
-      } else if (val2 == null) {
-        return -missingSortCmp;
-      }
-      return val1.compareTo(val2);
-    }
-
-    @Override
-    public void setScorer(Scorable scorer) {}
-  }
-
   /**
    * Sorts by field's natural Term sort order. All comparisons are done using BytesRef.compareTo,
    * which is slow for medium to large result sets but possibly very fast for very small results
diff --git a/lucene/core/src/java/org/apache/lucene/search/SortField.java b/lucene/core/src/java/org/apache/lucene/search/SortField.java
index 76815c5fffa..0240dc32d45 100644
--- a/lucene/core/src/java/org/apache/lucene/search/SortField.java
+++ b/lucene/core/src/java/org/apache/lucene/search/SortField.java
@@ -31,6 +31,7 @@ import org.apache.lucene.search.comparators.DoubleComparator;
 import org.apache.lucene.search.comparators.FloatComparator;
 import org.apache.lucene.search.comparators.IntComparator;
 import org.apache.lucene.search.comparators.LongComparator;
+import org.apache.lucene.search.comparators.TermOrdValComparator;
 import org.apache.lucene.store.DataInput;
 import org.apache.lucene.store.DataOutput;
 import org.apache.lucene.util.BytesRef;
@@ -536,8 +537,7 @@ public class SortField {
         break;
 
       case STRING:
-        return new FieldComparator.TermOrdValComparator(
-            numHits, field, missingValue == STRING_LAST);
+        return new TermOrdValComparator(numHits, field, missingValue == STRING_LAST, reverse);
 
       case STRING_VAL:
         fieldComparator =
diff --git a/lucene/core/src/java/org/apache/lucene/search/SortedSetSortField.java b/lucene/core/src/java/org/apache/lucene/search/SortedSetSortField.java
index a44e4a84e89..80db1ebecc9 100644
--- a/lucene/core/src/java/org/apache/lucene/search/SortedSetSortField.java
+++ b/lucene/core/src/java/org/apache/lucene/search/SortedSetSortField.java
@@ -24,6 +24,7 @@ import org.apache.lucene.index.LeafReaderContext;
 import org.apache.lucene.index.SortFieldProvider;
 import org.apache.lucene.index.SortedDocValues;
 import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.search.comparators.TermOrdValComparator;
 import org.apache.lucene.store.DataInput;
 import org.apache.lucene.store.DataOutput;
 
@@ -178,8 +179,7 @@ public class SortedSetSortField extends SortField {
 
   @Override
   public FieldComparator<?> getComparator(int numHits, boolean enableSkipping) {
-    return new FieldComparator.TermOrdValComparator(
-        numHits, getField(), missingValue == STRING_LAST) {
+    return new TermOrdValComparator(numHits, getField(), missingValue == STRING_LAST, reverse) {
       @Override
       protected SortedDocValues getSortedDocValues(LeafReaderContext context, String field)
           throws IOException {
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
new file mode 100644
index 00000000000..36e64f6df89
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java
@@ -0,0 +1,608 @@
+/*
+ * 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.ArrayDeque;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.IndexOptions;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.PostingsEnum;
+import org.apache.lucene.index.SortedDocValues;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.FieldComparator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.LeafFieldComparator;
+import org.apache.lucene.search.Scorable;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefBuilder;
+import org.apache.lucene.util.PriorityQueue;
+
+/**
+ * Sorts by field's natural Term sort order, using ordinals. This is functionally equivalent to
+ * {@link org.apache.lucene.search.FieldComparator.TermValComparator}, but it first resolves the
+ * string to their relative ordinal positions (using the index returned by {@link
+ * org.apache.lucene.index.LeafReader#getSortedDocValues(String)}), and does most comparisons using
+ * the ordinals. For medium to large results, this comparator will be much faster than {@link
+ * org.apache.lucene.search.FieldComparator.TermValComparator}. For very small result sets it may be
+ * slower.
+ */
+public class TermOrdValComparator extends FieldComparator<BytesRef> {
+
+  /* Ords for each slot.
+  @lucene.internal */
+  final int[] ords;
+
+  /* Values for each slot.
+  @lucene.internal */
+  final BytesRef[] values;
+  private final BytesRefBuilder[] tempBRs;
+
+  /* Which reader last copied a value into the slot. When
+  we compare two slots, we just compare-by-ord if the
+  readerGen is the same; else we must compare the
+  values (slower).
+  @lucene.internal */
+  final int[] readerGen;
+
+  /* Gen of current reader we are on.
+  @lucene.internal */
+  int currentReaderGen = -1;
+
+  private final String field;
+  private final boolean reverse;
+  private final boolean sortMissingLast;
+
+  /* Bottom value (same as values[bottomSlot] once
+   bottomSlot is set).  Cached for faster compares.
+  @lucene.internal */
+  BytesRef bottomValue;
+
+  /* Bottom slot, or -1 if queue isn't full yet */
+  int bottomSlot = -1;
+
+  /** Set by setTopValue. */
+  BytesRef topValue;
+
+  /** -1 if missing values are sorted first, 1 if they are sorted last */
+  final int missingSortCmp;
+
+  /** Whether this is the only comparator. */
+  private boolean singleSort;
+
+  /** Whether this comparator is allowed to skip documents. */
+  private boolean canSkipDocuments = true;
+
+  /** Whether the collector is done with counting hits so that we can start skipping documents. */
+  private boolean hitsThresholdReached = false;
+
+  /**
+   * Creates this, with control over how missing values are sorted. Pass sortMissingLast=true to put
+   * missing values at the end.
+   */
+  public TermOrdValComparator(int numHits, String field, boolean sortMissingLast, boolean reverse) {
+    ords = new int[numHits];
+    values = new BytesRef[numHits];
+    tempBRs = new BytesRefBuilder[numHits];
+    readerGen = new int[numHits];
+    this.field = field;
+    this.reverse = reverse;
+    this.sortMissingLast = sortMissingLast;
+    if (sortMissingLast) {
+      missingSortCmp = 1;
+    } else {
+      missingSortCmp = -1;
+    }
+  }
+
+  @Override
+  public void disableSkipping() {
+    canSkipDocuments = false;
+  }
+
+  @Override
+  public void setSingleSort() {
+    singleSort = true;
+  }
+
+  @Override
+  public int compare(int slot1, int slot2) {
+    if (readerGen[slot1] == readerGen[slot2]) {
+      return ords[slot1] - ords[slot2];
+    }
+
+    final BytesRef val1 = values[slot1];
+    final BytesRef val2 = values[slot2];
+    if (val1 == null) {
+      if (val2 == null) {
+        return 0;
+      }
+      return missingSortCmp;
+    } else if (val2 == null) {
+      return -missingSortCmp;
+    }
+    return val1.compareTo(val2);
+  }
+
+  /** Retrieves the SortedDocValues for the field in this segment */
+  protected SortedDocValues getSortedDocValues(LeafReaderContext context, String field)
+      throws IOException {
+    return DocValues.getSorted(context.reader(), field);
+  }
+
+  @Override
+  public LeafFieldComparator getLeafComparator(LeafReaderContext context) throws IOException {
+    currentReaderGen++;
+    return new TermOrdValLeafComparator(context, getSortedDocValues(context, field));
+  }
+
+  @Override
+  public void setTopValue(BytesRef value) {
+    // null is fine: it means the last doc of the prior
+    // search was missing this value
+    topValue = value;
+    // System.out.println("setTopValue " + topValue);
+  }
+
+  @Override
+  public BytesRef value(int slot) {
+    return values[slot];
+  }
+
+  @Override
+  public int compareValues(BytesRef val1, BytesRef val2) {
+    if (val1 == null) {
+      if (val2 == null) {
+        return 0;
+      }
+      return missingSortCmp;
+    } else if (val2 == null) {
+      return -missingSortCmp;
+    }
+    return val1.compareTo(val2);
+  }
+
+  private class TermOrdValLeafComparator implements LeafFieldComparator {
+
+    /* Current reader's doc ord/values. */
+    final SortedDocValues termsIndex;
+
+    /* True if current bottom slot matches the current reader. */
+    boolean bottomSameReader;
+
+    /* Bottom ord (same as ords[bottomSlot] once bottomSlot is set).  Cached for faster compares. */
+    int bottomOrd;
+
+    final boolean topSameReader;
+    final int topOrd;
+
+    /** Which ordinal to use for a missing value. */
+    final int missingOrd;
+
+    private final CompetitiveIterator competitiveIterator;
+
+    private final boolean dense;
+
+    TermOrdValLeafComparator(LeafReaderContext context, SortedDocValues values) throws IOException {
+      termsIndex = values;
+
+      if (sortMissingLast) {
+        missingOrd = Integer.MAX_VALUE;
+      } else {
+        missingOrd = -1;
+      }
+
+      if (topValue != null) {
+        // Recompute topOrd/SameReader
+        int ord = termsIndex.lookupTerm(topValue);
+        if (ord >= 0) {
+          topSameReader = true;
+          topOrd = ord;
+        } else {
+          topSameReader = false;
+          topOrd = -ord - 2;
+        }
+      } else {
+        topOrd = missingOrd;
+        topSameReader = true;
+      }
+      // System.out.println("  getLeafComparator topOrd=" + topOrd + " topSameReader=" +
+      // topSameReader);
+
+      if (bottomSlot != -1) {
+        // Recompute bottomOrd/SameReader
+        setBottom(bottomSlot);
+      }
+
+      final boolean enableSkipping;
+      if (canSkipDocuments == false) {
+        dense = false;
+        enableSkipping = false;
+      } else {
+        FieldInfo fieldInfo = context.reader().getFieldInfos().fieldInfo(field);
+        if (fieldInfo == null) {
+          if (termsIndex.getValueCount() != 0) {
+            throw new IllegalStateException("Field [" + field + "] cannot be found in field infos");
+          }
+          dense = false;
+          enableSkipping = true;
+        } else if (fieldInfo.getIndexOptions() == IndexOptions.NONE) {
+          // No terms index
+          dense = false;
+          enableSkipping = false;
+        } else {
+          Terms terms = context.reader().terms(field);
+          dense = terms.getDocCount() == context.reader().maxDoc();
+          if (dense || topValue != null) {
+            enableSkipping = true;
+          } else if (reverse == sortMissingLast) {
+            // Missing values are always competitive, we can never skip
+            enableSkipping = false;
+          } else {
+            enableSkipping = true;
+          }
+        }
+      }
+      if (enableSkipping) {
+        competitiveIterator = new CompetitiveIterator(context, field, dense, values.termsEnum());
+      } else {
+        competitiveIterator = null;
+      }
+      updateCompetitiveIterator();
+    }
+
+    private int getOrdForDoc(int doc) throws IOException {
+      if (termsIndex.advanceExact(doc)) {
+        return termsIndex.ordValue();
+      } else {
+        return -1;
+      }
+    }
+
+    @Override
+    public void setHitsThresholdReached() throws IOException {
+      hitsThresholdReached = true;
+      updateCompetitiveIterator();
+    }
+
+    @Override
+    public int compareBottom(int doc) throws IOException {
+      assert bottomSlot != -1;
+      int docOrd = getOrdForDoc(doc);
+      if (docOrd == -1) {
+        docOrd = missingOrd;
+      }
+      if (bottomSameReader) {
+        // ord is precisely comparable, even in the equal case
+        return bottomOrd - docOrd;
+      } else if (bottomOrd >= docOrd) {
+        // the equals case always means bottom is > doc
+        // (because we set bottomOrd to the lower bound in
+        // setBottom):
+        return 1;
+      } else {
+        return -1;
+      }
+    }
+
+    @Override
+    public void copy(int slot, int doc) throws IOException {
+      int ord = getOrdForDoc(doc);
+      if (ord == -1) {
+        ord = missingOrd;
+        values[slot] = null;
+      } else {
+        assert ord >= 0;
+        if (tempBRs[slot] == null) {
+          tempBRs[slot] = new BytesRefBuilder();
+        }
+        tempBRs[slot].copyBytes(termsIndex.lookupOrd(ord));
+        values[slot] = tempBRs[slot].get();
+      }
+      ords[slot] = ord;
+      readerGen[slot] = currentReaderGen;
+    }
+
+    @Override
+    public void setBottom(final int bottom) throws IOException {
+      bottomSlot = bottom;
+
+      bottomValue = values[bottomSlot];
+      if (currentReaderGen == readerGen[bottomSlot]) {
+        bottomOrd = ords[bottomSlot];
+        bottomSameReader = true;
+      } else {
+        if (bottomValue == null) {
+          // missingOrd is null for all segments
+          assert ords[bottomSlot] == missingOrd;
+          bottomOrd = missingOrd;
+          bottomSameReader = true;
+          readerGen[bottomSlot] = currentReaderGen;
+        } else {
+          final int ord = termsIndex.lookupTerm(bottomValue);
+          if (ord < 0) {
+            bottomOrd = -ord - 2;
+            bottomSameReader = false;
+          } else {
+            bottomOrd = ord;
+            // exact value match
+            bottomSameReader = true;
+            readerGen[bottomSlot] = currentReaderGen;
+            ords[bottomSlot] = bottomOrd;
+          }
+        }
+      }
+
+      updateCompetitiveIterator();
+    }
+
+    @Override
+    public int compareTop(int doc) throws IOException {
+
+      int ord = getOrdForDoc(doc);
+      if (ord == -1) {
+        ord = missingOrd;
+      }
+
+      if (topSameReader) {
+        // ord is precisely comparable, even in the equal case
+        // System.out.println("compareTop doc=" + doc + " ord=" + ord + " ret=" + (topOrd-ord));
+        return topOrd - ord;
+      } else if (ord <= topOrd) {
+        // the equals case always means doc is < value
+        // (because we set topOrd to the lower bound)
+        return 1;
+      } else {
+        return -1;
+      }
+    }
+
+    @Override
+    public void setScorer(Scorable scorer) {}
+
+    private void updateCompetitiveIterator() throws IOException {
+      if (competitiveIterator == null || hitsThresholdReached == false || bottomSlot == -1) {
+        return;
+      }
+      // This logic to figure out min and max ords is quite complex and verbose, can it be made
+      // simpler?
+      final int minOrd;
+      final int maxOrd;
+      if (reverse == false) {
+
+        if (topValue != null) {
+          if (topSameReader) {
+            minOrd = topOrd;
+          } else {
+            // In the case when the top value doesn't exist in the segment, topOrd is set as the
+            // previous ord, and we are only interested in values that compare strictly greater than
+            // this.
+            minOrd = topOrd + 1;
+          }
+        } else if (sortMissingLast || dense) {
+          minOrd = 0;
+        } else {
+          // Missing values are still competitive.
+          minOrd = -1;
+        }
+
+        if (bottomOrd == Integer.MAX_VALUE) {
+          // The queue still contains missing values.
+          if (singleSort) {
+            // If there is no tie breaker, we can start ignoring missing values from now on.
+            maxOrd = termsIndex.getValueCount() - 1;
+          } else {
+            maxOrd = Integer.MAX_VALUE;
+          }
+        } else if (bottomSameReader) {
+          // If there is no tie breaker, we can start ignoring values that compare equal to the
+          // current top value too.
+          maxOrd = singleSort ? bottomOrd - 1 : bottomOrd;
+        } else {
+          maxOrd = bottomOrd;
+        }
+
+      } else {
+
+        if (bottomOrd == -1) {
+          // The queue still contains missing values.
+          if (singleSort) {
+            // If there is no tie breaker, we can start ignoring missing values from now on.
+            minOrd = 0;
+          } else {
+            minOrd = -1;
+          }
+        } else if (bottomSameReader) {
+          // If there is no tie breaker, we can start ignoring values that compare equal to the
+          // current top value too.
+          minOrd = singleSort ? bottomOrd + 1 : bottomOrd;
+        } else {
+          minOrd = bottomOrd + 1;
+        }
+
+        if (topValue != null) {
+          maxOrd = topOrd;
+        } else if (sortMissingLast == false || dense) {
+          maxOrd = termsIndex.getValueCount() - 1;
+        } else {
+          maxOrd = Integer.MAX_VALUE;
+        }
+      }
+
+      if (minOrd == -1 || maxOrd == Integer.MAX_VALUE) {
+        // Missing values are still competitive, we can't skip yet.
+        return;
+      }
+      assert minOrd >= 0;
+      assert maxOrd < termsIndex.getValueCount();
+      competitiveIterator.update(minOrd, maxOrd);
+    }
+
+    @Override
+    public DocIdSetIterator competitiveIterator() {
+      return competitiveIterator;
+    }
+  }
+
+  private static class PostingsEnumAndOrd {
+    private final PostingsEnum postings;
+    private final int ord;
+
+    PostingsEnumAndOrd(PostingsEnum postings, int ord) {
+      this.postings = postings;
+      this.ord = ord;
+    }
+  }
+
+  private class CompetitiveIterator extends DocIdSetIterator {
+
+    private static final int MAX_TERMS = 128;
+
+    private final LeafReaderContext context;
+    private final int maxDoc;
+    private final String field;
+    private final boolean dense;
+    private final TermsEnum docValuesTerms;
+    private int doc = -1;
+    private ArrayDeque<PostingsEnumAndOrd> postings;
+    private DocIdSetIterator docsWithField;
+    private PriorityQueue<PostingsEnumAndOrd> disjunction;
+
+    CompetitiveIterator(
+        LeafReaderContext context, String field, boolean dense, TermsEnum docValuesTerms) {
+      this.context = context;
+      this.maxDoc = context.reader().maxDoc();
+      this.field = field;
+      this.dense = dense;
+      this.docValuesTerms = docValuesTerms;
+    }
+
+    @Override
+    public int docID() {
+      return doc;
+    }
+
+    @Override
+    public int nextDoc() throws IOException {
+      return advance(docID() + 1);
+    }
+
+    @Override
+    public int advance(int target) throws IOException {
+      if (target >= maxDoc) {
+        return doc = NO_MORE_DOCS;
+      } else if (disjunction == null) {
+        if (docsWithField != null) {
+          // The field is sparse and we're only interested in documents that have a value.
+          assert dense == false;
+          return doc = docsWithField.advance(target);
+        } else {
+          // We haven't started skipping yet
+          return doc = target;
+        }
+      } else {
+        PostingsEnumAndOrd top = disjunction.top();
+        if (top == null) {
+          // priority queue is empty, none of the remaining documents are competitive
+          return doc = NO_MORE_DOCS;
+        }
+        while (top.postings.docID() < target) {
+          top.postings.advance(target);
+          top = disjunction.updateTop();
+        }
+        return doc = top.postings.docID();
+      }
+    }
+
+    @Override
+    public long cost() {
+      return context.reader().maxDoc();
+    }
+
+    /**
+     * Update this iterator to only match postings whose term has an ordinal between {@code minOrd}
+     * included and {@code maxOrd} included.
+     */
+    private void update(int minOrd, int maxOrd) throws IOException {
+      final int maxTerms = Math.min(MAX_TERMS, IndexSearcher.getMaxClauseCount());
+      final int size = Math.max(0, maxOrd - minOrd + 1);
+      if (size > maxTerms) {
+        if (dense == false && docsWithField == null) {
+          docsWithField = getSortedDocValues(context, field);
+        }
+      } else if (postings == null) {
+        init(minOrd, maxOrd);
+      } else if (size < postings.size()) {
+        // One or more ords got removed
+        assert postings.isEmpty() || postings.getFirst().ord <= minOrd;
+        while (postings.isEmpty() == false && postings.getFirst().ord < minOrd) {
+          postings.removeFirst();
+        }
+        assert postings.isEmpty() || postings.getLast().ord >= maxOrd;
+        while (postings.isEmpty() == false && postings.getLast().ord > maxOrd) {
+          postings.removeLast();
+        }
+        disjunction.clear();
+        disjunction.addAll(postings);
+      }
+    }
+
+    /**
+     * For the first time, this iterator is allowed to skip documents. It needs to pull {@link
+     * PostingsEnum}s from the terms dictionary of the inverted index and create a priority queue
+     * out of them.
+     */
+    private void init(int minOrd, int maxOrd) throws IOException {
+      final int size = Math.max(0, maxOrd - minOrd + 1);
+      postings = new ArrayDeque<>(size);
+      if (size > 0) {
+        docValuesTerms.seekExact(minOrd);
+        BytesRef minTerm = docValuesTerms.term();
+        TermsEnum terms = context.reader().terms(field).iterator();
+        if (terms.seekExact(minTerm) == false) {
+          throw new IllegalStateException(
+              "Term " + minTerm + " exists in doc values but not in the terms index");
+        }
+        postings.add(new PostingsEnumAndOrd(terms.postings(null, PostingsEnum.NONE), minOrd));
+        for (int ord = minOrd + 1; ord <= maxOrd; ++ord) {
+          BytesRef next = terms.next();
+          if (next == null) {
+            throw new IllegalStateException(
+                "Terms have more than "
+                    + ord
+                    + " unique terms while doc values have exactly "
+                    + ord
+                    + " terms");
+          }
+          assert docValuesTerms.seekExact(next) && docValuesTerms.ord() == ord;
+          postings.add(new PostingsEnumAndOrd(terms.postings(null, PostingsEnum.NONE), ord));
+        }
+      }
+      disjunction =
+          new PriorityQueue<PostingsEnumAndOrd>(size) {
+            @Override
+            protected boolean lessThan(PostingsEnumAndOrd a, PostingsEnumAndOrd b) {
+              return a.postings.docID() < b.postings.docID();
+            }
+          };
+      disjunction.addAll(postings);
+    }
+  }
+}
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 419cc055d47..6e99f586719 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSortOptimization.java
@@ -26,24 +26,39 @@ import java.util.Collections;
 import java.util.List;
 import org.apache.lucene.document.Document;
 import org.apache.lucene.document.Field;
+import org.apache.lucene.document.Field.Store;
 import org.apache.lucene.document.FloatDocValuesField;
 import org.apache.lucene.document.FloatPoint;
 import org.apache.lucene.document.IntPoint;
 import org.apache.lucene.document.IntRange;
 import org.apache.lucene.document.LongPoint;
 import org.apache.lucene.document.NumericDocValuesField;
+import org.apache.lucene.document.SortedDocValuesField;
 import org.apache.lucene.document.SortedNumericDocValuesField;
 import org.apache.lucene.document.StoredField;
 import org.apache.lucene.document.StringField;
 import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.FieldInfos;
+import org.apache.lucene.index.FilterDirectoryReader;
+import org.apache.lucene.index.FilterLeafReader;
+import org.apache.lucene.index.IndexOptions;
 import org.apache.lucene.index.IndexReader;
 import org.apache.lucene.index.IndexWriter;
 import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.PointValues;
 import org.apache.lucene.index.Term;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.search.SortField.Type;
 import org.apache.lucene.store.Directory;
 import org.apache.lucene.tests.index.RandomIndexWriter;
+import org.apache.lucene.tests.search.CheckHits;
 import org.apache.lucene.tests.util.LuceneTestCase;
 import org.apache.lucene.tests.util.TestUtil;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.IOUtils;
 
 public class TestSortOptimization extends LuceneTestCase {
@@ -869,4 +884,254 @@ public class TestSortOptimization extends LuceneTestCase {
               + numDocs);
     }
   }
+
+  public void testStringSortOptimization() 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();
+      final BytesRef value = new BytesRef(Integer.toString(random().nextInt(1000)));
+      doc.add(new StringField("my_field", value, Store.NO));
+      doc.add(new SortedDocValuesField("my_field", value));
+      writer.addDocument(doc);
+      if (i % 2000 == 0) writer.flush(); // multiple segments
+    }
+    final DirectoryReader reader = DirectoryReader.open(writer);
+    writer.close();
+    doTestStringSortOptimization(reader);
+    reader.close();
+    dir.close();
+  }
+
+  public void testStringSortOptimizationWithMissingValues() throws IOException {
+    final Directory dir = newDirectory();
+    final IndexWriter writer =
+        new IndexWriter(dir, new IndexWriterConfig().setMergePolicy(newLogMergePolicy()));
+    final int numDocs = atLeast(10000);
+    // one segment with all values missing to start with
+    writer.addDocument(new Document());
+    for (int i = 0; i < numDocs - 2; ++i) {
+      if (i % 2000 == 0) writer.flush(); // multiple segments
+      final Document doc = new Document();
+      if (random().nextInt(2) == 0) {
+        final BytesRef value = new BytesRef(Integer.toString(random().nextInt(1000)));
+        doc.add(new StringField("my_field", value, Store.NO));
+        doc.add(new SortedDocValuesField("my_field", value));
+      }
+      writer.addDocument(doc);
+    }
+    writer.flush();
+    // And one empty segment with all values missing to finish with
+    writer.addDocument(new Document());
+    final DirectoryReader reader = DirectoryReader.open(writer);
+    writer.close();
+    doTestStringSortOptimization(reader);
+    reader.close();
+    dir.close();
+  }
+
+  private void doTestStringSortOptimization(DirectoryReader reader) throws IOException {
+    final int numDocs = reader.numDocs();
+    final int numHits = 5;
+
+    { // simple ascending sort
+      SortField sortField = new SortField("my_field", SortField.Type.STRING);
+      sortField.setMissingValue(SortField.STRING_LAST);
+      Sort sort = new Sort(sortField);
+      TopDocs topDocs = assertSort(reader, sort, numHits, null);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value, numDocs);
+    }
+
+    { // simple descending sort
+      SortField sortField = new SortField("my_field", SortField.Type.STRING, true);
+      sortField.setMissingValue(SortField.STRING_FIRST);
+      Sort sort = new Sort(sortField);
+      TopDocs topDocs = assertSort(reader, sort, numHits, null);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value, numDocs);
+    }
+
+    { // ascending sort that returns missing values first
+      SortField sortField = new SortField("my_field", SortField.Type.STRING);
+      sortField.setMissingValue(SortField.STRING_FIRST);
+      Sort sort = new Sort(sortField);
+      assertSort(reader, sort, numHits, null);
+    }
+
+    { // descending sort that returns missing values last
+      SortField sortField = new SortField("my_field", SortField.Type.STRING, true);
+      sortField.setMissingValue(SortField.STRING_LAST);
+      Sort sort = new Sort(sortField);
+      assertSort(reader, sort, numHits, null);
+    }
+
+    { // paging ascending sort with after
+      SortField sortField = new SortField("my_field", SortField.Type.STRING);
+      sortField.setMissingValue(SortField.STRING_LAST);
+      Sort sort = new Sort(sortField);
+      BytesRef afterValue = new BytesRef(random().nextBoolean() ? "23" : "230000000");
+      FieldDoc after = new FieldDoc(2, Float.NaN, new Object[] {afterValue});
+      TopDocs topDocs = assertSort(reader, sort, numHits, after);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value, numDocs);
+    }
+
+    { // paging descending sort with after
+      SortField sortField = new SortField("my_field", SortField.Type.STRING, true);
+      sortField.setMissingValue(SortField.STRING_FIRST);
+      Sort sort = new Sort(sortField);
+      BytesRef afterValue = new BytesRef(random().nextBoolean() ? "17" : "170000000");
+      FieldDoc after = new FieldDoc(2, Float.NaN, new Object[] {afterValue});
+      TopDocs topDocs = assertSort(reader, sort, numHits, after);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value, numDocs);
+    }
+
+    { // paging ascending sort with after that returns missing values first
+      SortField sortField = new SortField("my_field", SortField.Type.STRING);
+      sortField.setMissingValue(SortField.STRING_FIRST);
+      Sort sort = new Sort(sortField);
+      BytesRef afterValue = new BytesRef(random().nextBoolean() ? "23" : "230000000");
+      FieldDoc after = new FieldDoc(2, Float.NaN, new Object[] {afterValue});
+      TopDocs topDocs = assertSort(reader, sort, numHits, after);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value, numDocs);
+    }
+
+    { // paging descending sort with after that returns missing values first
+      SortField sortField = new SortField("my_field", SortField.Type.STRING, true);
+      sortField.setMissingValue(SortField.STRING_LAST);
+      Sort sort = new Sort(sortField);
+      BytesRef afterValue = new BytesRef(random().nextBoolean() ? "17" : "170000000");
+      FieldDoc after = new FieldDoc(2, Float.NaN, new Object[] {afterValue});
+      TopDocs topDocs = assertSort(reader, sort, numHits, after);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value, numDocs);
+    }
+
+    { // test that if there is the secondary sort on _score, hits are still skipped
+      SortField sortField = new SortField("my_field", SortField.Type.STRING);
+      sortField.setMissingValue(SortField.STRING_LAST);
+      Sort sort = new Sort(sortField, FIELD_SCORE);
+      TopDocs topDocs = assertSort(reader, sort, numHits, null);
+      assertNonCompetitiveHitsAreSkipped(topDocs.totalHits.value, numDocs);
+    }
+
+    { // test that if string field is a secondary sort, no optimization is run
+      SortField sortField = new SortField("my_field", SortField.Type.STRING);
+      sortField.setMissingValue(SortField.STRING_LAST);
+      Sort sort = new Sort(FIELD_SCORE, sortField);
+      TopDocs topDocs = assertSort(reader, sort, numHits, null);
+      assertEquals(
+          topDocs.totalHits.value,
+          numDocs); // assert that all documents were collected => optimization was not run
+    }
+  }
+
+  private TopDocs assertSort(DirectoryReader reader, Sort sort, int n, FieldDoc after)
+      throws IOException {
+    TopDocs topDocs = assertSearchHits(reader, sort, n, after);
+    SortField[] sortField2 = ArrayUtil.growExact(sort.getSort(), sort.getSort().length + 1);
+    // A secondary sort on reverse doc ID is the best way to catch bugs if the comparator filters
+    // too aggressively
+    sortField2[sortField2.length - 1] = new SortField(null, Type.DOC, true);
+    FieldDoc after2 = null;
+    if (after != null) {
+      Object[] afterFields2 = ArrayUtil.growExact(after.fields, after.fields.length + 1);
+      afterFields2[afterFields2.length - 1] = Integer.MAX_VALUE;
+      after2 = new FieldDoc(after.doc, after.score, afterFields2);
+    }
+    assertSearchHits(reader, new Sort(sortField2), n, after2);
+    return topDocs;
+  }
+
+  private TopDocs assertSearchHits(DirectoryReader reader, Sort sort, int n, FieldDoc after)
+      throws IOException {
+    // single threaded so totalhits is deterministic
+    IndexSearcher searcher = newSearcher(reader, true, true, false);
+    Query query = new MatchAllDocsQuery();
+    CollectorManager<TopFieldCollector, TopFieldDocs> manager =
+        TopFieldCollector.createSharedManager(sort, n, after, n);
+    TopDocs topDocs = searcher.search(query, manager);
+    IndexSearcher unoptimizedSearcher =
+        newSearcher(new NoIndexDirectoryReader(reader), true, true, false);
+    TopDocs unoptimizedTopDocs = unoptimizedSearcher.search(query, manager);
+    CheckHits.checkEqual(query, unoptimizedTopDocs.scoreDocs, topDocs.scoreDocs);
+    return topDocs;
+  }
+
+  private static final class NoIndexDirectoryReader extends FilterDirectoryReader {
+
+    public NoIndexDirectoryReader(DirectoryReader in) throws IOException {
+      super(
+          in,
+          new SubReaderWrapper() {
+            @Override
+            public LeafReader wrap(LeafReader reader) {
+              return new NoIndexLeafReader(reader);
+            }
+          });
+    }
+
+    @Override
+    protected DirectoryReader doWrapDirectoryReader(DirectoryReader in) throws IOException {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public CacheHelper getReaderCacheHelper() {
+      return null;
+    }
+  }
+
+  private static final class NoIndexLeafReader extends FilterLeafReader {
+
+    NoIndexLeafReader(LeafReader in) {
+      super(in);
+    }
+
+    @Override
+    public CacheHelper getCoreCacheHelper() {
+      return null;
+    }
+
+    @Override
+    public CacheHelper getReaderCacheHelper() {
+      return null;
+    }
+
+    @Override
+    public Terms terms(String field) throws IOException {
+      return null;
+    }
+
+    @Override
+    public PointValues getPointValues(String field) throws IOException {
+      return null;
+    }
+
+    @Override
+    public FieldInfos getFieldInfos() {
+      FieldInfo[] newInfos = new FieldInfo[super.getFieldInfos().size()];
+      int i = 0;
+      for (FieldInfo fi : super.getFieldInfos()) {
+        FieldInfo noIndexFI =
+            new FieldInfo(
+                fi.name,
+                fi.number,
+                false,
+                false,
+                false,
+                IndexOptions.NONE,
+                fi.getDocValuesType(),
+                fi.getDocValuesGen(),
+                fi.attributes(),
+                0,
+                0,
+                0,
+                0,
+                VectorSimilarityFunction.DOT_PRODUCT,
+                fi.isSoftDeletesField());
+        newInfos[i] = noIndexFI;
+        i++;
+      }
+      return new FieldInfos(newInfos);
+    }
+  }
 }
diff --git a/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java b/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java
index 20307ba73e6..a29294c1cb8 100644
--- a/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java
+++ b/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java
@@ -33,6 +33,7 @@ import org.apache.lucene.search.comparators.DoubleComparator;
 import org.apache.lucene.search.comparators.FloatComparator;
 import org.apache.lucene.search.comparators.IntComparator;
 import org.apache.lucene.search.comparators.LongComparator;
+import org.apache.lucene.search.comparators.TermOrdValComparator;
 import org.apache.lucene.util.BitSet;
 import org.apache.lucene.util.NumericUtils;
 
@@ -134,23 +135,25 @@ public class ToParentBlockJoinSortField extends SortField {
   }
 
   private FieldComparator<?> getStringComparator(int numHits) {
-    return new FieldComparator.TermOrdValComparator(
-        numHits, getField(), missingValue == STRING_LAST) {
+    FieldComparator<?> cmp =
+        new TermOrdValComparator(numHits, getField(), missingValue == STRING_LAST, getReverse()) {
 
-      @Override
-      protected SortedDocValues getSortedDocValues(LeafReaderContext context, String field)
-          throws IOException {
-        SortedSetDocValues sortedSet = DocValues.getSortedSet(context.reader(), field);
-        final BlockJoinSelector.Type type =
-            order ? BlockJoinSelector.Type.MAX : BlockJoinSelector.Type.MIN;
-        final BitSet parents = parentFilter.getBitSet(context);
-        final BitSet children = childFilter.getBitSet(context);
-        if (children == null) {
-          return DocValues.emptySorted();
-        }
-        return BlockJoinSelector.wrap(sortedSet, type, parents, toIter(children));
-      }
-    };
+          @Override
+          protected SortedDocValues getSortedDocValues(LeafReaderContext context, String field)
+              throws IOException {
+            SortedSetDocValues sortedSet = DocValues.getSortedSet(context.reader(), field);
+            final BlockJoinSelector.Type type =
+                order ? BlockJoinSelector.Type.MAX : BlockJoinSelector.Type.MIN;
+            final BitSet parents = parentFilter.getBitSet(context);
+            final BitSet children = childFilter.getBitSet(context);
+            if (children == null) {
+              return DocValues.emptySorted();
+            }
+            return BlockJoinSelector.wrap(sortedSet, type, parents, toIter(children));
+          }
+        };
+    cmp.disableSkipping();
+    return cmp;
   }
 
   private FieldComparator<?> getIntComparator(int numHits) {