You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mv...@apache.org on 2013/04/15 11:34:08 UTC

svn commit: r1467914 - in /lucene/dev/trunk/lucene: ./ join/src/java/org/apache/lucene/search/join/ join/src/test/org/apache/lucene/search/join/

Author: mvg
Date: Mon Apr 15 09:34:07 2013
New Revision: 1467914

URL: http://svn.apache.org/r1467914
Log:
LUCENE-4774: Added FieldComparator that allows sorting parent documents based on fields on the child / nested document level.

Added:
    lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinFieldComparator.java   (with props)
    lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java   (with props)
    lucene/dev/trunk/lucene/join/src/test/org/apache/lucene/search/join/TestBlockJoinSorting.java   (with props)
Modified:
    lucene/dev/trunk/lucene/CHANGES.txt

Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1467914&r1=1467913&r2=1467914&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Mon Apr 15 09:34:07 2013
@@ -189,6 +189,9 @@ New Features
 * LUCENE-4895: Added support for the "IsDisjointTo" spatial predicate for
   RecursivePrefixTreeStrategy.  (David Smiley)
 
+* LUCENE-4774: Added FieldComparator that allows sorting parent documents based on
+  fields on the child / nested document level. (Martijn van Groningen)
+
 API Changes
 
 * LUCENE-4896: Made PassageFormatter abstract in PostingsHighlighter, made

Added: lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinFieldComparator.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinFieldComparator.java?rev=1467914&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinFieldComparator.java (added)
+++ lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinFieldComparator.java Mon Apr 15 09:34:07 2013
@@ -0,0 +1,346 @@
+package org.apache.lucene.search.join;
+
+/*
+ * 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.
+ */
+
+import org.apache.lucene.index.AtomicReaderContext;
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.FieldComparator;
+import org.apache.lucene.search.Filter;
+import org.apache.lucene.util.FixedBitSet;
+
+import java.io.IOException;
+
+/**
+ * A field comparator that allows parent documents to be sorted by fields
+ * from the nested / child documents.
+ *
+ * @lucene.experimental
+ */
+public abstract class ToParentBlockJoinFieldComparator extends FieldComparator<Object> {
+
+  private final Filter parentFilter;
+  private final Filter childFilter;
+  final int spareSlot;
+
+  FieldComparator<Object> wrappedComparator;
+  FixedBitSet parentDocuments;
+  FixedBitSet childDocuments;
+
+  ToParentBlockJoinFieldComparator(FieldComparator<Object> wrappedComparator, Filter parentFilter, Filter childFilter, int spareSlot) {
+    this.wrappedComparator = wrappedComparator;
+    this.parentFilter = parentFilter;
+    this.childFilter = childFilter;
+    this.spareSlot = spareSlot;
+  }
+
+  @Override
+  public int compare(int slot1, int slot2) {
+    return wrappedComparator.compare(slot1, slot2);
+  }
+
+  @Override
+  public void setBottom(int slot) {
+    wrappedComparator.setBottom(slot);
+  }
+
+  @Override
+  public FieldComparator<Object> setNextReader(AtomicReaderContext context) throws IOException {
+    DocIdSet innerDocuments = childFilter.getDocIdSet(context, null);
+    if (isEmpty(innerDocuments)) {
+      this.childDocuments = null;
+    } else if (innerDocuments instanceof FixedBitSet) {
+      this.childDocuments = (FixedBitSet) innerDocuments;
+    } else {
+      DocIdSetIterator iterator = innerDocuments.iterator();
+      if (iterator != null) {
+        this.childDocuments = toFixedBitSet(iterator, context.reader().maxDoc());
+      } else {
+        childDocuments = null;
+      }
+    }
+    DocIdSet rootDocuments = parentFilter.getDocIdSet(context, null);
+    if (isEmpty(rootDocuments)) {
+      this.parentDocuments = null;
+    } else if (rootDocuments instanceof FixedBitSet) {
+      this.parentDocuments = (FixedBitSet) rootDocuments;
+    } else {
+      DocIdSetIterator iterator = rootDocuments.iterator();
+      if (iterator != null) {
+        this.parentDocuments = toFixedBitSet(iterator, context.reader().maxDoc());
+      } else {
+        this.parentDocuments = null;
+      }
+    }
+
+    wrappedComparator = wrappedComparator.setNextReader(context);
+    return this;
+  }
+
+  private static boolean isEmpty(DocIdSet set) {
+    return set == null || set == DocIdSet.EMPTY_DOCIDSET;
+  }
+
+  private static FixedBitSet toFixedBitSet(DocIdSetIterator iterator, int numBits) throws IOException {
+    FixedBitSet set = new FixedBitSet(numBits);
+    int doc;
+    while ((doc = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
+      set.set(doc);
+    }
+    return set;
+  }
+
+  @Override
+  public Object value(int slot) {
+    return wrappedComparator.value(slot);
+  }
+
+  /**
+   * Concrete implementation of {@link ToParentBlockJoinSortField} to sorts the parent docs with the lowest values
+   * in the child / nested docs first.
+   */
+  public static final class Lowest extends ToParentBlockJoinFieldComparator {
+
+    /**
+     * Create ToParentBlockJoinFieldComparator.Lowest
+     *
+     * @param wrappedComparator The {@link FieldComparator} on the child / nested level.
+     * @param parentFilter Filter (must produce FixedBitSet per-segment) that identifies the parent documents.
+     * @param childFilter Filter that defines which child / nested documents participates in sorting.
+     * @param spareSlot The extra slot inside the wrapped comparator that is used to compare which nested document
+     *                  inside the parent document scope is most competitive.
+     */
+    public Lowest(FieldComparator<Object> wrappedComparator, Filter parentFilter, Filter childFilter, int spareSlot) {
+      super(wrappedComparator, parentFilter, childFilter, spareSlot);
+    }
+
+    @Override
+    public int compareBottom(int parentDoc) throws IOException {
+      if (parentDoc == 0 || parentDocuments == null || childDocuments == null) {
+        return 0;
+      }
+
+      // We need to copy the lowest value from all child docs into slot.
+      int prevParentDoc = parentDocuments.prevSetBit(parentDoc - 1);
+      int childDoc = childDocuments.nextSetBit(prevParentDoc + 1);
+      if (childDoc >= parentDoc || childDoc == -1) {
+        return 0;
+      }
+
+      // We only need to emit a single cmp value for any matching child doc
+      int cmp = wrappedComparator.compareBottom(childDoc);
+      if (cmp > 0) {
+        return cmp;
+      }
+
+      while (true) {
+        childDoc = childDocuments.nextSetBit(childDoc + 1);
+        if (childDoc >= parentDoc || childDoc == -1) {
+          return cmp;
+        }
+        int cmp1 = wrappedComparator.compareBottom(childDoc);
+        if (cmp1 > 0) {
+          return cmp1;
+        } else {
+          if (cmp1 == 0) {
+            cmp = 0;
+          }
+        }
+      }
+    }
+
+    @Override
+    public void copy(int slot, int parentDoc) throws IOException {
+      if (parentDoc == 0 || parentDocuments == null || childDocuments == null) {
+        return;
+      }
+
+      // We need to copy the lowest value from all child docs into slot.
+      int prevParentDoc = parentDocuments.prevSetBit(parentDoc - 1);
+      int childDoc = childDocuments.nextSetBit(prevParentDoc + 1);
+      if (childDoc >= parentDoc || childDoc == -1) {
+        return;
+      }
+      wrappedComparator.copy(spareSlot, childDoc);
+      wrappedComparator.copy(slot, childDoc);
+
+      while (true) {
+        childDoc = childDocuments.nextSetBit(childDoc + 1);
+        if (childDoc >= parentDoc || childDoc == -1) {
+          return;
+        }
+        wrappedComparator.copy(spareSlot, childDoc);
+        if (wrappedComparator.compare(spareSlot, slot) < 0) {
+          wrappedComparator.copy(slot, childDoc);
+        }
+      }
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public int compareDocToValue(int parentDoc, Object value) throws IOException {
+      if (parentDoc == 0 || parentDocuments == null || childDocuments == null) {
+        return 0;
+      }
+
+      // We need to copy the lowest value from all nested docs into slot.
+      int prevParentDoc = parentDocuments.prevSetBit(parentDoc - 1);
+      int childDoc = childDocuments.nextSetBit(prevParentDoc + 1);
+      if (childDoc >= parentDoc || childDoc == -1) {
+        return 0;
+      }
+
+      // We only need to emit a single cmp value for any matching child doc
+      int cmp = wrappedComparator.compareBottom(childDoc);
+      if (cmp > 0) {
+        return cmp;
+      }
+
+      while (true) {
+        childDoc = childDocuments.nextSetBit(childDoc + 1);
+        if (childDoc >= parentDoc || childDoc == -1) {
+          return cmp;
+        }
+        int cmp1 = wrappedComparator.compareDocToValue(childDoc, value);
+        if (cmp1 > 0) {
+          return cmp1;
+        } else {
+          if (cmp1 == 0) {
+            cmp = 0;
+          }
+        }
+      }
+    }
+
+  }
+
+  /**
+   * Concrete implementation of {@link ToParentBlockJoinSortField} to sorts the parent docs with the highest values
+   * in the child / nested docs first.
+   */
+  public static final class Highest extends ToParentBlockJoinFieldComparator {
+
+    /**
+     * Create ToParentBlockJoinFieldComparator.Highest
+     *
+     * @param wrappedComparator The {@link FieldComparator} on the child / nested level.
+     * @param parentFilter Filter (must produce FixedBitSet per-segment) that identifies the parent documents.
+     * @param childFilter Filter that defines which child / nested documents participates in sorting.
+     * @param spareSlot The extra slot inside the wrapped comparator that is used to compare which nested document
+     *                  inside the parent document scope is most competitive.
+     */
+    public Highest(FieldComparator<Object> wrappedComparator, Filter parentFilter, Filter childFilter, int spareSlot) {
+      super(wrappedComparator, parentFilter, childFilter, spareSlot);
+    }
+
+    @Override
+    public int compareBottom(int parentDoc) throws IOException {
+      if (parentDoc == 0 || parentDocuments == null || childDocuments == null) {
+        return 0;
+      }
+
+      int prevParentDoc = parentDocuments.prevSetBit(parentDoc - 1);
+      int childDoc = childDocuments.nextSetBit(prevParentDoc + 1);
+      if (childDoc >= parentDoc || childDoc == -1) {
+        return 0;
+      }
+
+      int cmp = wrappedComparator.compareBottom(childDoc);
+      if (cmp < 0) {
+        return cmp;
+      }
+
+      while (true) {
+        childDoc = childDocuments.nextSetBit(childDoc + 1);
+        if (childDoc >= parentDoc || childDoc == -1) {
+          return cmp;
+        }
+        int cmp1 = wrappedComparator.compareBottom(childDoc);
+        if (cmp1 < 0) {
+          return cmp1;
+        } else {
+          if (cmp1 == 0) {
+            cmp = 0;
+          }
+        }
+      }
+    }
+
+    @Override
+    public void copy(int slot, int parentDoc) throws IOException {
+      if (parentDoc == 0 || parentDocuments == null || childDocuments == null) {
+        return;
+      }
+
+      int prevParentDoc = parentDocuments.prevSetBit(parentDoc - 1);
+      int childDoc = childDocuments.nextSetBit(prevParentDoc + 1);
+      if (childDoc >= parentDoc || childDoc == -1) {
+        return;
+      }
+      wrappedComparator.copy(spareSlot, childDoc);
+      wrappedComparator.copy(slot, childDoc);
+
+      while (true) {
+        childDoc = childDocuments.nextSetBit(childDoc + 1);
+        if (childDoc >= parentDoc || childDoc == -1) {
+          return;
+        }
+        wrappedComparator.copy(spareSlot, childDoc);
+        if (wrappedComparator.compare(spareSlot, slot) > 0) {
+          wrappedComparator.copy(slot, childDoc);
+        }
+      }
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public int compareDocToValue(int parentDoc, Object value) throws IOException {
+      if (parentDoc == 0 || parentDocuments == null || childDocuments == null) {
+        return 0;
+      }
+
+      int prevParentDoc = parentDocuments.prevSetBit(parentDoc - 1);
+      int childDoc = childDocuments.nextSetBit(prevParentDoc + 1);
+      if (childDoc >= parentDoc || childDoc == -1) {
+        return 0;
+      }
+
+      int cmp = wrappedComparator.compareBottom(childDoc);
+      if (cmp < 0) {
+        return cmp;
+      }
+
+      while (true) {
+        childDoc = childDocuments.nextSetBit(childDoc + 1);
+        if (childDoc >= parentDoc || childDoc == -1) {
+          return cmp;
+        }
+        int cmp1 = wrappedComparator.compareDocToValue(childDoc, value);
+        if (cmp1 < 0) {
+          return cmp1;
+        } else {
+          if (cmp1 == 0) {
+            cmp = 0;
+          }
+        }
+      }
+    }
+
+  }
+
+}

Added: lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java?rev=1467914&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java (added)
+++ lucene/dev/trunk/lucene/join/src/java/org/apache/lucene/search/join/ToParentBlockJoinSortField.java Mon Apr 15 09:34:07 2013
@@ -0,0 +1,82 @@
+package org.apache.lucene.search.join;
+
+/*
+ * 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.
+ */
+
+import org.apache.lucene.search.FieldComparator;
+import org.apache.lucene.search.Filter;
+import org.apache.lucene.search.SortField;
+
+import java.io.IOException;
+
+/**
+ * A special sort field that allows sorting parent docs based on nested / child level fields.
+ * Based on the sort order it either takes the document with the lowest or highest field value into account.
+ *
+ * @lucene.experimental
+ */
+public class ToParentBlockJoinSortField extends SortField {
+
+  private final boolean order;
+  private final Filter parentFilter;
+  private final Filter childFilter;
+
+  /**
+   * Create ToParentBlockJoinSortField. The parent document ordering is based on child document ordering (reverse).
+   *
+   * @param field The sort field on the nested / child level.
+   * @param type The sort type on the nested / child level.
+   * @param reverse Whether natural order should be reversed on the nested / child level.
+   * @param parentFilter Filter that identifies the parent documents.
+   * @param childFilter Filter that defines which child documents participates in sorting.
+   */
+  public ToParentBlockJoinSortField(String field, Type type, boolean reverse, Filter parentFilter, Filter childFilter) {
+    super(field, type, reverse);
+    this.order = reverse;
+    this.parentFilter = parentFilter;
+    this.childFilter = childFilter;
+  }
+
+  /**
+   * Create ToParentBlockJoinSortField.
+   *
+   * @param field The sort field on the nested / child level.
+   * @param type The sort type on the nested / child level.
+   * @param reverse Whether natural order should be reversed on the nested / child document level.
+   * @param order Whether natural order should be reversed on the parent level.
+   * @param parentFilter Filter that identifies the parent documents.
+   * @param childFilter Filter that defines which child documents participates in sorting.
+   */
+  public ToParentBlockJoinSortField(String field, Type type, boolean reverse, boolean order, Filter parentFilter, Filter childFilter) {
+    super(field, type, reverse);
+    this.order = order;
+    this.parentFilter = parentFilter;
+    this.childFilter = childFilter;
+  }
+
+  @Override
+  @SuppressWarnings("unchecked")
+  public FieldComparator<?> getComparator(int numHits, int sortPos) throws IOException {
+    FieldComparator<Object> wrappedFieldComparator = (FieldComparator) super.getComparator(numHits + 1, sortPos);
+    if (order) {
+      return new ToParentBlockJoinFieldComparator.Highest(wrappedFieldComparator, parentFilter, childFilter, numHits);
+    } else {
+      return new ToParentBlockJoinFieldComparator.Lowest(wrappedFieldComparator, parentFilter, childFilter, numHits);
+    }
+  }
+
+}

Added: lucene/dev/trunk/lucene/join/src/test/org/apache/lucene/search/join/TestBlockJoinSorting.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/join/src/test/org/apache/lucene/search/join/TestBlockJoinSorting.java?rev=1467914&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/join/src/test/org/apache/lucene/search/join/TestBlockJoinSorting.java (added)
+++ lucene/dev/trunk/lucene/join/src/test/org/apache/lucene/search/join/TestBlockJoinSorting.java Mon Apr 15 09:34:07 2013
@@ -0,0 +1,308 @@
+package org.apache.lucene.search.join;
+
+/*
+ * 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.
+ */
+
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.RandomIndexWriter;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.CachingWrapperFilter;
+import org.apache.lucene.search.FieldDoc;
+import org.apache.lucene.search.Filter;
+import org.apache.lucene.search.FilteredQuery;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.MatchAllDocsQuery;
+import org.apache.lucene.search.PrefixQuery;
+import org.apache.lucene.search.QueryWrapperFilter;
+import org.apache.lucene.search.Sort;
+import org.apache.lucene.search.SortField;
+import org.apache.lucene.search.TermQuery;
+import org.apache.lucene.search.TopFieldDocs;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LuceneTestCase;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ */
+public class TestBlockJoinSorting extends LuceneTestCase {
+
+  @Test
+  public void testNestedSorting() throws Exception {
+    final Directory dir = newDirectory();
+    final RandomIndexWriter w = new RandomIndexWriter(random(), dir);
+
+    List<Document> docs = new ArrayList<>();
+    Document document = new Document();
+    document.add(new StringField("field2", "a", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "b", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "c", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "a", Field.Store.NO));
+    docs.add(document);
+    w.addDocuments(docs);
+    w.commit();
+
+    docs.clear();
+    document = new Document();
+    document.add(new StringField("field2", "c", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "d", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "e", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "b", Field.Store.NO));
+    docs.add(document);
+    w.addDocuments(docs);
+
+    docs.clear();
+    document = new Document();
+    document.add(new StringField("field2", "e", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "f", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "g", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "c", Field.Store.NO));
+    docs.add(document);
+    w.addDocuments(docs);
+
+    docs.clear();
+    document = new Document();
+    document.add(new StringField("field2", "g", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "h", Field.Store.NO));
+    document.add(new StringField("filter_1", "F", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "i", Field.Store.NO));
+    document.add(new StringField("filter_1", "F", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "d", Field.Store.NO));
+    docs.add(document);
+    w.addDocuments(docs);
+    w.commit();
+
+    docs.clear();
+    document = new Document();
+    document.add(new StringField("field2", "i", Field.Store.NO));
+    document.add(new StringField("filter_1", "F", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "j", Field.Store.NO));
+    document.add(new StringField("filter_1", "F", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "k", Field.Store.NO));
+    document.add(new StringField("filter_1", "F", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "f", Field.Store.NO));
+    docs.add(document);
+    w.addDocuments(docs);
+
+    docs.clear();
+    document = new Document();
+    document.add(new StringField("field2", "k", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "l", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "m", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "g", Field.Store.NO));
+    docs.add(document);
+    w.addDocuments(docs);
+
+    // This doc will not be included, because it doesn't have nested docs
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "h", Field.Store.NO));
+    w.addDocument(document);
+
+    docs.clear();
+    document = new Document();
+    document.add(new StringField("field2", "m", Field.Store.NO));
+    document.add(new StringField("filter_1", "T", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "n", Field.Store.NO));
+    document.add(new StringField("filter_1", "F", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("field2", "o", Field.Store.NO));
+    document.add(new StringField("filter_1", "F", Field.Store.NO));
+    docs.add(document);
+    document = new Document();
+    document.add(new StringField("__type", "parent", Field.Store.NO));
+    document.add(new StringField("field1", "i", Field.Store.NO));
+    docs.add(document);
+    w.addDocuments(docs);
+    w.commit();
+
+    // Some garbage docs, just to check if the NestedFieldComparator can deal with this.
+    document = new Document();
+    document.add(new StringField("fieldXXX", "x", Field.Store.NO));
+    w.addDocument(document);
+    document = new Document();
+    document.add(new StringField("fieldXXX", "x", Field.Store.NO));
+    w.addDocument(document);
+    document = new Document();
+    document.add(new StringField("fieldXXX", "x", Field.Store.NO));
+    w.addDocument(document);
+
+    IndexSearcher searcher = new IndexSearcher(DirectoryReader.open(w.w, false));
+    w.close();
+    Filter parentFilter = new QueryWrapperFilter(new TermQuery(new Term("__type", "parent")));
+    Filter childFilter = new QueryWrapperFilter(new PrefixQuery(new Term("field2")));
+    ToParentBlockJoinQuery query = new ToParentBlockJoinQuery(
+        new FilteredQuery(new MatchAllDocsQuery(), childFilter),
+        new CachingWrapperFilter(parentFilter),
+        ScoreMode.None
+    );
+
+    // Sort by field ascending, order first
+    ToParentBlockJoinSortField sortField = new ToParentBlockJoinSortField(
+        "field2", SortField.Type.STRING, false, wrap(parentFilter), wrap(childFilter)
+    );
+    Sort sort = new Sort(sortField);
+    TopFieldDocs topDocs = searcher.search(query, 5, sort);
+    assertEquals(7, topDocs.totalHits);
+    assertEquals(5, topDocs.scoreDocs.length);
+    assertEquals(3, topDocs.scoreDocs[0].doc);
+    assertEquals("a", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[0]).fields[0]).utf8ToString());
+    assertEquals(7, topDocs.scoreDocs[1].doc);
+    assertEquals("c", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[1]).fields[0]).utf8ToString());
+    assertEquals(11, topDocs.scoreDocs[2].doc);
+    assertEquals("e", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[2]).fields[0]).utf8ToString());
+    assertEquals(15, topDocs.scoreDocs[3].doc);
+    assertEquals("g", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[3]).fields[0]).utf8ToString());
+    assertEquals(19, topDocs.scoreDocs[4].doc);
+    assertEquals("i", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[4]).fields[0]).utf8ToString());
+
+    // Sort by field ascending, order last
+    sortField = new ToParentBlockJoinSortField(
+        "field2", SortField.Type.STRING, false, true, wrap(parentFilter), wrap(childFilter)
+    );
+    sort = new Sort(sortField);
+    topDocs = searcher.search(query, 5, sort);
+    assertEquals(7, topDocs.totalHits);
+    assertEquals(5, topDocs.scoreDocs.length);
+    assertEquals(3, topDocs.scoreDocs[0].doc);
+    assertEquals("c", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[0]).fields[0]).utf8ToString());
+    assertEquals(7, topDocs.scoreDocs[1].doc);
+    assertEquals("e", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[1]).fields[0]).utf8ToString());
+    assertEquals(11, topDocs.scoreDocs[2].doc);
+    assertEquals("g", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[2]).fields[0]).utf8ToString());
+    assertEquals(15, topDocs.scoreDocs[3].doc);
+    assertEquals("i", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[3]).fields[0]).utf8ToString());
+    assertEquals(19, topDocs.scoreDocs[4].doc);
+    assertEquals("k", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[4]).fields[0]).utf8ToString());
+
+    // Sort by field descending, order last
+    sortField = new ToParentBlockJoinSortField(
+        "field2", SortField.Type.STRING, true, wrap(parentFilter), wrap(childFilter)
+    );
+    sort = new Sort(sortField);
+    topDocs = searcher.search(query, 5, sort);
+    assertEquals(topDocs.totalHits, 7);
+    assertEquals(5, topDocs.scoreDocs.length);
+    assertEquals(28, topDocs.scoreDocs[0].doc);
+    assertEquals("o", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[0]).fields[0]).utf8ToString());
+    assertEquals(23, topDocs.scoreDocs[1].doc);
+    assertEquals("m", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[1]).fields[0]).utf8ToString());
+    assertEquals(19, topDocs.scoreDocs[2].doc);
+    assertEquals("k", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[2]).fields[0]).utf8ToString());
+    assertEquals(15, topDocs.scoreDocs[3].doc);
+    assertEquals("i", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[3]).fields[0]).utf8ToString());
+    assertEquals(11, topDocs.scoreDocs[4].doc);
+    assertEquals("g", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[4]).fields[0]).utf8ToString());
+
+    // Sort by field descending, order last, sort filter (filter_1:T)
+    childFilter = new QueryWrapperFilter(new TermQuery((new Term("filter_1", "T"))));
+    query = new ToParentBlockJoinQuery(
+        new FilteredQuery(new MatchAllDocsQuery(), childFilter),
+        new CachingWrapperFilter(parentFilter),
+        ScoreMode.None
+    );
+    sortField = new ToParentBlockJoinSortField(
+        "field2", SortField.Type.STRING, true, wrap(parentFilter), wrap(childFilter)
+    );
+    sort = new Sort(sortField);
+    topDocs = searcher.search(query, 5, sort);
+    assertEquals(6, topDocs.totalHits);
+    assertEquals(5, topDocs.scoreDocs.length);
+    assertEquals(23, topDocs.scoreDocs[0].doc);
+    assertEquals("m", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[0]).fields[0]).utf8ToString());
+    assertEquals(28, topDocs.scoreDocs[1].doc);
+    assertEquals("m", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[1]).fields[0]).utf8ToString());
+    assertEquals(11, topDocs.scoreDocs[2].doc);
+    assertEquals("g", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[2]).fields[0]).utf8ToString());
+    assertEquals(15, topDocs.scoreDocs[3].doc);
+    assertEquals("g", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[3]).fields[0]).utf8ToString());
+    assertEquals(7, topDocs.scoreDocs[4].doc);
+    assertEquals("e", ((BytesRef) ((FieldDoc) topDocs.scoreDocs[4]).fields[0]).utf8ToString());
+
+    searcher.getIndexReader().close();
+    dir.close();
+  }
+
+  private Filter wrap(Filter filter) {
+    return random().nextBoolean() ? new CachingWrapperFilter(filter) : filter;
+  }
+
+}