SERVER-19402 Change find command semantics for sorting on an array field.

This eliminates the behavior in which the lowest-valued
in-bounds index key was chosen as the sort key. After this
change, we instead choose the lowest key overall, which may
or may not be in-bounds. This change prevents the sort order
from depending on either the query predicate or the
implementation details of the query planner.

Note that it is no longer correct for a multikey index to
provide a sort over an array field. However, a non-array
field of a multikey index can provide a sort when that index
has path-level multikeyness metadata.

13 files changed, 171 insertions, 235 deletions

diff --git a/src/mongo/db/exec/sort_key_generator.cpp b/src/mongo/db/exec/sort_key_generator.cpp
index c562be7ed26..8f145dffaf0 100644
--- a/src/mongo/db/exec/sort_key_generator.cpp
+++ b/src/mongo/db/exec/sort_key_generator.cpp
@@ -42,7 +42,6 @@
 #include "mongo/db/exec/working_set_computed_data.h"
 #include "mongo/db/matcher/extensions_callback_noop.h"
 #include "mongo/db/query/collation/collator_interface.h"
-#include "mongo/db/query/query_planner.h"
 #include "mongo/stdx/memory.h"
 #include "mongo/util/log.h"
 
@@ -54,13 +53,8 @@ namespace mongo {
 
 SortKeyGenerator::SortKeyGenerator(OperationContext* opCtx,
                                    const BSONObj& sortSpec,
-                                   const BSONObj& queryObj,
                                    const CollatorInterface* collator)
-    : _collator(collator) {
-    _hasBounds = false;
-    _sortHasMeta = false;
-    _rawSortSpec = sortSpec;
-
+    : _collator(collator), _rawSortSpec(sortSpec) {
     // 'sortSpec' can be a mix of $meta and index key expressions.  We pick it apart so that
     // we only generate Btree keys for the index key expressions.
 
@@ -68,17 +62,14 @@ SortKeyGenerator::SortKeyGenerator(OperationContext* opCtx,
     // key generator below as part of generating sort keys for the docs.
     BSONObjBuilder btreeBob;
 
-    BSONObjIterator it(sortSpec);
-    while (it.more()) {
-        BSONElement elt = it.next();
+    for (auto&& elt : sortSpec) {
         if (elt.isNumber()) {
-            // Btree key.  elt (should be) foo: 1 or foo: -1.
             btreeBob.append(elt);
-        } else if (QueryRequest::isTextScoreMeta(elt)) {
-            _sortHasMeta = true;
         } else {
-            // Sort spec. should have been validated before here.
-            verify(false);
+            // If this field of the sort pattern is non-numeric, we expect it to be a text-score
+            // meta sort. This is validated upstream.
+            invariant(QueryRequest::isTextScoreMeta(elt));
+            _sortHasMeta = true;
         }
     }
 
@@ -95,21 +86,13 @@ SortKeyGenerator::SortKeyGenerator(OperationContext* opCtx,
     // the sort order.
     std::vector<const char*> fieldNames;
     std::vector<BSONElement> fixed;
-    BSONObjIterator btreeIt(_btreeObj);
-    while (btreeIt.more()) {
-        BSONElement patternElt = btreeIt.next();
+    for (auto&& patternElt : _btreeObj) {
         fieldNames.push_back(patternElt.fieldName());
         fixed.push_back(BSONElement());
     }
 
-    _keyGen.reset(new BtreeKeyGeneratorV1(fieldNames, fixed, false /* not sparse */, _collator));
-
-    // The bounds checker only works on the Btree part of the sort key.
-    getBoundsForSort(opCtx, queryObj, _btreeObj);
-
-    if (_hasBounds) {
-        _boundsChecker.reset(new IndexBoundsChecker(&_bounds, _btreeObj, 1 /* == order */));
-    }
+    constexpr bool isSparse = false;
+    _keyGen = stdx::make_unique<BtreeKeyGeneratorV1>(fieldNames, fixed, isSparse, _collator);
 }
 
 Status SortKeyGenerator::getSortKey(const WorkingSetMember& member, BSONObj* objOut) const {
@@ -203,93 +186,10 @@ StatusWith<BSONObj> SortKeyGenerator::getSortKeyFromObject(const WorkingSetMembe
     // Key generator isn't sparse so we should at least get an all-null key.
     invariant(!keys.empty());
 
-    // No bounds?  No problem!  Use the first key.
-    if (!_hasBounds) {
-        // Note that we sort 'keys' according to the pattern '_btreeObj'.
-        return *keys.begin();
-    }
-
-    // To decide which key to use in sorting, we must consider not only the sort pattern but
-    // the query.  Assume we have the query {a: {$gte: 5}} and a document {a:1}.  That
-    // document wouldn't match the query.  As such, the key '1' in an array {a: [1, 10]}
-    // should not be considered as being part of the result set and thus that array cannot
-    // sort using the key '1'.  To ensure that the keys we sort by are valid w.r.t. the
-    // query we use a bounds checker.
-    verify(NULL != _boundsChecker.get());
-    for (BSONObjSet::const_iterator it = keys.begin(); it != keys.end(); ++it) {
-        if (_boundsChecker->isValidKey(*it)) {
-            return *it;
-        }
-    }
-
-    // No key is in our bounds.
-    // TODO: will this ever happen?  don't think it should.
+    // The sort key is the first index key, ordered according to the pattern '_btreeObj'.
     return *keys.begin();
 }
 
-void SortKeyGenerator::getBoundsForSort(OperationContext* opCtx,
-                                        const BSONObj& queryObj,
-                                        const BSONObj& sortObj) {
-    QueryPlannerParams params;
-    params.options = QueryPlannerParams::NO_TABLE_SCAN;
-
-    // We're creating a "virtual index" with key pattern equal to the sort order. The "virtual
-    // index" has the collation which the query is using.
-    IndexEntry sortOrder(sortObj,
-                         IndexNames::BTREE,
-                         true,
-                         MultikeyPaths{},
-                         false,
-                         false,
-                         "doesnt_matter",
-                         NULL,
-                         BSONObj(),
-                         _collator);
-    params.indices.push_back(sortOrder);
-
-    auto qr = stdx::make_unique<QueryRequest>(NamespaceString("fake.ns"));
-    qr->setFilter(queryObj);
-    if (_collator) {
-        qr->setCollation(_collator->getSpec().toBSON());
-    }
-
-    auto statusWithQueryForSort =
-        CanonicalQuery::canonicalize(opCtx, std::move(qr), ExtensionsCallbackNoop());
-    verify(statusWithQueryForSort.isOK());
-    std::unique_ptr<CanonicalQuery> queryForSort = std::move(statusWithQueryForSort.getValue());
-
-    std::vector<QuerySolution*> solns;
-    LOG(5) << "Sort key generation: Planning to obtain bounds for sort.";
-    QueryPlanner::plan(*queryForSort, params, &solns).transitional_ignore();
-
-    // TODO: are there ever > 1 solns?  If so, do we look for a specific soln?
-    if (1 == solns.size()) {
-        IndexScanNode* ixScan = NULL;
-        QuerySolutionNode* rootNode = solns[0]->root.get();
-
-        if (rootNode->getType() == STAGE_FETCH) {
-            FetchNode* fetchNode = static_cast<FetchNode*>(rootNode);
-            if (fetchNode->children[0]->getType() != STAGE_IXSCAN) {
-                delete solns[0];
-                // No bounds.
-                return;
-            }
-            ixScan = static_cast<IndexScanNode*>(fetchNode->children[0]);
-        } else if (rootNode->getType() == STAGE_IXSCAN) {
-            ixScan = static_cast<IndexScanNode*>(rootNode);
-        }
-
-        if (ixScan) {
-            _bounds.fields.swap(ixScan->bounds.fields);
-            _hasBounds = true;
-        }
-    }
-
-    for (size_t i = 0; i < solns.size(); ++i) {
-        delete solns[i];
-    }
-}
-
 //
 // SortKeyGeneratorStage
 //
@@ -300,13 +200,8 @@ SortKeyGeneratorStage::SortKeyGeneratorStage(OperationContext* opCtx,
                                              PlanStage* child,
                                              WorkingSet* ws,
                                              const BSONObj& sortSpecObj,
-                                             const BSONObj& queryObj,
                                              const CollatorInterface* collator)
-    : PlanStage(kStageType, opCtx),
-      _ws(ws),
-      _sortSpec(sortSpecObj),
-      _query(queryObj),
-      _collator(collator) {
+    : PlanStage(kStageType, opCtx), _ws(ws), _sortSpec(sortSpecObj), _collator(collator) {
     _children.emplace_back(child);
 }
 
@@ -316,7 +211,7 @@ bool SortKeyGeneratorStage::isEOF() {
 
 PlanStage::StageState SortKeyGeneratorStage::doWork(WorkingSetID* out) {
     if (!_sortKeyGen) {
-        _sortKeyGen = stdx::make_unique<SortKeyGenerator>(getOpCtx(), _sortSpec, _query, _collator);
+        _sortKeyGen = stdx::make_unique<SortKeyGenerator>(getOpCtx(), _sortSpec, _collator);
         return PlanStage::NEED_TIME;
     }
 
diff --git a/src/mongo/db/exec/sort_key_generator.h b/src/mongo/db/exec/sort_key_generator.h
index d284bad443d..986ad1b7633 100644
--- a/src/mongo/db/exec/sort_key_generator.h
+++ b/src/mongo/db/exec/sort_key_generator.h
@@ -50,16 +50,11 @@ public:
     /**
      * 'sortSpec' is the BSONObj in the .sort(...) clause.
      *
-     * 'queryObj' is the BSONObj in the .find(...) clause.  For multikey arrays we have to
-     * ensure that the value we select to sort by is within bounds generated by
-     * executing 'queryObj' using the virtual index with key pattern 'sortSpec'.
-     *
      * 'opCtx' must point to a valid OperationContext, but 'opCtx' does not need to outlive the
      * constructed SortKeyGenerator.
      */
     SortKeyGenerator(OperationContext* opCtx,
                      const BSONObj& sortSpec,
-                     const BSONObj& queryObj,
                      const CollatorInterface* collator);
 
     /**
@@ -75,17 +70,7 @@ private:
     StatusWith<BSONObj> getSortKeyFromIndexKey(const WorkingSetMember& member) const;
     StatusWith<BSONObj> getSortKeyFromObject(const WorkingSetMember& member) const;
 
-    /**
-     * In order to emulate the existing sort behavior we must make unindexed sort behavior as
-     * consistent as possible with indexed sort behavior.  As such, we must only consider index
-     * keys that we would encounter if we were answering the query using the sort-providing
-     * index.
-     *
-     * Populates _hasBounds and _bounds.
-     */
-    void getBoundsForSort(OperationContext* opCtx, const BSONObj& queryObj, const BSONObj& sortObj);
-
-    const CollatorInterface* _collator;
+    const CollatorInterface* _collator = nullptr;
 
     // The raw object in .sort()
     BSONObj _rawSortSpec;
@@ -94,19 +79,10 @@ private:
     BSONObj _btreeObj;
 
     // If we're not sorting with a $meta value we can short-cut some work.
-    bool _sortHasMeta;
-
-    // True if the bounds are valid.
-    bool _hasBounds;
-
-    // The bounds generated from the query we're sorting.
-    IndexBounds _bounds;
+    bool _sortHasMeta = false;
 
     // Helper to extract sorting keys from documents.
     std::unique_ptr<BtreeKeyGenerator> _keyGen;
-
-    // Helper to filter keys, ensuring keys generated with _keyGen are within _bounds.
-    std::unique_ptr<IndexBoundsChecker> _boundsChecker;
 };
 
 /**
@@ -119,7 +95,6 @@ public:
                           PlanStage* child,
                           WorkingSet* ws,
                           const BSONObj& sortSpecObj,
-                          const BSONObj& queryObj,
                           const CollatorInterface* collator);
 
     bool isEOF() final;
@@ -142,9 +117,6 @@ private:
     // The raw sort pattern as expressed by the user.
     const BSONObj _sortSpec;
 
-    // The raw query as expressed by the user.
-    const BSONObj _query;
-
     const CollatorInterface* _collator;
 
     std::unique_ptr<SortKeyGenerator> _sortKeyGen;
diff --git a/src/mongo/db/exec/sort_test.cpp b/src/mongo/db/exec/sort_test.cpp
index 8f200ffb0a3..68a2240db7b 100644
--- a/src/mongo/db/exec/sort_test.cpp
+++ b/src/mongo/db/exec/sort_test.cpp
@@ -66,7 +66,7 @@ public:
 
     /**
      * Test function to verify sort stage.
-     * SortStageParams will be initialized using patternStr, collator, queryStr and limit.
+     * SortStageParams will be initialized using patternStr, collator, and limit.
      * inputStr represents the input data set in a BSONObj.
      *     {input: [doc1, doc2, doc3, ...]}
      * expectedStr represents the expected sorted data set.
@@ -74,7 +74,6 @@ public:
      */
     void testWork(const char* patternStr,
                   CollatorInterface* collator,
-                  const char* queryStr,
                   int limit,
                   const char* inputStr,
                   const char* expectedStr) {
@@ -107,12 +106,8 @@ public:
         params.pattern = fromjson(patternStr);
         params.limit = limit;
 
-        auto sortKeyGen = stdx::make_unique<SortKeyGeneratorStage>(getOpCtx(),
-                                                                   queuedDataStage.release(),
-                                                                   &ws,
-                                                                   params.pattern,
-                                                                   fromjson(queryStr),
-                                                                   collator);
+        auto sortKeyGen = stdx::make_unique<SortKeyGeneratorStage>(
+            getOpCtx(), queuedDataStage.release(), &ws, params.pattern, collator);
 
         SortStage sort(getOpCtx(), params, &ws, sortKeyGen.release());
 
@@ -151,8 +146,8 @@ public:
             mongoutils::str::stream ss;
             // Even though we have the original string representation of the expected output,
             // we invoke BSONObj::toString() to get a format consistent with outputObj.
-            ss << "Unexpected sort result with query=" << queryStr << "; pattern=" << patternStr
-               << "; limit=" << limit << ":\n"
+            ss << "Unexpected sort result with pattern=" << patternStr << "; limit=" << limit
+               << ":\n"
                << "Expected: " << expectedObj.toString() << "\n"
                << "Actual:   " << outputObj.toString() << "\n";
             FAIL(ss);
@@ -177,7 +172,7 @@ TEST_F(SortStageTest, SortEmptyWorkingSet) {
     // QueuedDataStage will be owned by SortStage.
     auto queuedDataStage = stdx::make_unique<QueuedDataStage>(getOpCtx(), &ws);
     auto sortKeyGen = stdx::make_unique<SortKeyGeneratorStage>(
-        getOpCtx(), queuedDataStage.release(), &ws, BSONObj(), BSONObj(), nullptr);
+        getOpCtx(), queuedDataStage.release(), &ws, BSONObj(), nullptr);
     SortStageParams params;
     SortStage sort(getOpCtx(), params, &ws, sortKeyGen.release());
 
@@ -216,7 +211,6 @@ TEST_F(SortStageTest, SortEmptyWorkingSet) {
 TEST_F(SortStageTest, SortAscending) {
     testWork("{a: 1}",
              nullptr,
-             "{}",
              0,
              "{input: [{a: 2}, {a: 1}, {a: 3}]}",
              "{output: [{a: 1}, {a: 2}, {a: 3}]}");
@@ -225,7 +219,6 @@ TEST_F(SortStageTest, SortAscending) {
 TEST_F(SortStageTest, SortDescending) {
     testWork("{a: -1}",
              nullptr,
-             "{}",
              0,
              "{input: [{a: 2}, {a: 1}, {a: 3}]}",
              "{output: [{a: 3}, {a: 2}, {a: 1}]}");
@@ -234,7 +227,6 @@ TEST_F(SortStageTest, SortDescending) {
 TEST_F(SortStageTest, SortIrrelevantSortKey) {
     testWork("{b: 1}",
              nullptr,
-             "{}",
              0,
              "{input: [{a: 2}, {a: 1}, {a: 3}]}",
              "{output: [{a: 2}, {a: 1}, {a: 3}]}");
@@ -247,21 +239,13 @@ TEST_F(SortStageTest, SortIrrelevantSortKey) {
 //
 
 TEST_F(SortStageTest, SortAscendingWithLimit) {
-    testWork("{a: 1}",
-             nullptr,
-             "{}",
-             2,
-             "{input: [{a: 2}, {a: 1}, {a: 3}]}",
-             "{output: [{a: 1}, {a: 2}]}");
+    testWork(
+        "{a: 1}", nullptr, 2, "{input: [{a: 2}, {a: 1}, {a: 3}]}", "{output: [{a: 1}, {a: 2}]}");
 }
 
 TEST_F(SortStageTest, SortDescendingWithLimit) {
-    testWork("{a: -1}",
-             nullptr,
-             "{}",
-             2,
-             "{input: [{a: 2}, {a: 1}, {a: 3}]}",
-             "{output: [{a: 3}, {a: 2}]}");
+    testWork(
+        "{a: -1}", nullptr, 2, "{input: [{a: 2}, {a: 1}, {a: 3}]}", "{output: [{a: 3}, {a: 2}]}");
 }
 
 //
@@ -273,7 +257,6 @@ TEST_F(SortStageTest, SortDescendingWithLimit) {
 TEST_F(SortStageTest, SortAscendingWithLimitGreaterThanInputSize) {
     testWork("{a: 1}",
              nullptr,
-             "{}",
              10,
              "{input: [{a: 2}, {a: 1}, {a: 3}]}",
              "{output: [{a: 1}, {a: 2}, {a: 3}]}");
@@ -282,7 +265,6 @@ TEST_F(SortStageTest, SortAscendingWithLimitGreaterThanInputSize) {
 TEST_F(SortStageTest, SortDescendingWithLimitGreaterThanInputSize) {
     testWork("{a: -1}",
              nullptr,
-             "{}",
              10,
              "{input: [{a: 2}, {a: 1}, {a: 3}]}",
              "{output: [{a: 3}, {a: 2}, {a: 1}]}");
@@ -294,19 +276,17 @@ TEST_F(SortStageTest, SortDescendingWithLimitGreaterThanInputSize) {
 //
 
 TEST_F(SortStageTest, SortAscendingWithLimitOfOne) {
-    testWork("{a: 1}", nullptr, "{}", 1, "{input: [{a: 2}, {a: 1}, {a: 3}]}", "{output: [{a: 1}]}");
+    testWork("{a: 1}", nullptr, 1, "{input: [{a: 2}, {a: 1}, {a: 3}]}", "{output: [{a: 1}]}");
 }
 
 TEST_F(SortStageTest, SortDescendingWithLimitOfOne) {
-    testWork(
-        "{a: -1}", nullptr, "{}", 1, "{input: [{a: 2}, {a: 1}, {a: 3}]}", "{output: [{a: 3}]}");
+    testWork("{a: -1}", nullptr, 1, "{input: [{a: 2}, {a: 1}, {a: 3}]}", "{output: [{a: 3}]}");
 }
 
 TEST_F(SortStageTest, SortAscendingWithCollation) {
     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
     testWork("{a: 1}",
              &collator,
-             "{}",
              0,
              "{input: [{a: 'ba'}, {a: 'aa'}, {a: 'ab'}]}",
              "{output: [{a: 'aa'}, {a: 'ba'}, {a: 'ab'}]}");
@@ -316,7 +296,6 @@ TEST_F(SortStageTest, SortDescendingWithCollation) {
     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
     testWork("{a: -1}",
              &collator,
-             "{}",
              0,
              "{input: [{a: 'ba'}, {a: 'aa'}, {a: 'ab'}]}",
              "{output: [{a: 'ab'}, {a: 'ba'}, {a: 'aa'}]}");
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp
index 40c52f5b74c..5367ce9c82b 100644
--- a/src/mongo/db/query/get_executor.cpp
+++ b/src/mongo/db/query/get_executor.cpp
@@ -300,13 +300,12 @@ StatusWith<PrepareExecutionResult> prepareExecution(OperationContext* opCtx,
 
             // Add a SortKeyGeneratorStage if there is a $meta sortKey projection.
             if (canonicalQuery->getProj()->wantSortKey()) {
-                root = make_unique<SortKeyGeneratorStage>(
-                    opCtx,
-                    root.release(),
-                    ws,
-                    canonicalQuery->getQueryRequest().getSort(),
-                    canonicalQuery->getQueryRequest().getFilter(),
-                    canonicalQuery->getCollator());
+                root =
+                    make_unique<SortKeyGeneratorStage>(opCtx,
+                                                       root.release(),
+                                                       ws,
+                                                       canonicalQuery->getQueryRequest().getSort(),
+                                                       canonicalQuery->getCollator());
             }
 
             // Stuff the right data into the params depending on what proj impl we use.
diff --git a/src/mongo/db/query/planner_analysis.cpp b/src/mongo/db/query/planner_analysis.cpp
index 19bda7e3cd1..5b72f1c98fa 100644
--- a/src/mongo/db/query/planner_analysis.cpp
+++ b/src/mongo/db/query/planner_analysis.cpp
@@ -525,7 +525,6 @@ QuerySolutionNode* QueryPlannerAnalysis::analyzeSort(const CanonicalQuery& query
     // And build the full sort stage. The sort stage has to have a sort key generating stage
     // as its child, supplying it with the appropriate sort keys.
     SortKeyGeneratorNode* keyGenNode = new SortKeyGeneratorNode();
-    keyGenNode->queryObj = qr.getFilter();
     keyGenNode->sortSpec = sortObj;
     keyGenNode->children.push_back(solnRoot);
     solnRoot = keyGenNode;
@@ -796,7 +795,6 @@ QuerySolution* QueryPlannerAnalysis::analyzeDataAccess(
         // generate the sort key computed data.
         if (!hasSortStage && query.getProj()->wantSortKey()) {
             SortKeyGeneratorNode* keyGenNode = new SortKeyGeneratorNode();
-            keyGenNode->queryObj = qr.getFilter();
             keyGenNode->sortSpec = qr.getSort();
             keyGenNode->children.push_back(solnRoot.release());
             solnRoot.reset(keyGenNode);
diff --git a/src/mongo/db/query/query_planner_geo_test.cpp b/src/mongo/db/query/query_planner_geo_test.cpp
index 96b71acdb3d..a4efc42195b 100644
--- a/src/mongo/db/query/query_planner_geo_test.cpp
+++ b/src/mongo/db/query/query_planner_geo_test.cpp
@@ -708,7 +708,8 @@ TEST_F(QueryPlannerTest, CompoundGeoNoGeoPredicateMultikey) {
         "{sort: {pattern: {creationDate: 1}, limit: 0, node: {sortKeyGen: "
         "{node: {cscan: {dir: 1}}}}}}");
     assertSolutionExists(
-        "{fetch: {node: {ixscan: {pattern: {creationDate: 1, 'foo.bar': '2dsphere'}}}}}");
+        "{sort: {pattern: {creationDate: 1}, limit: 0, node: {sortKeyGen: {node: {fetch: {node: "
+        "{ixscan: {pattern: {creationDate: 1, 'foo.bar': '2dsphere'}}}}}}}}}");
 }
 
 // Test that a 2dsphere index can satisfy a whole index scan solution if the query has a GEO
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index 191924eda68..5eec4719842 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -653,9 +653,30 @@ std::set<StringData> IndexScanNode::getFieldsWithStringBounds(const IndexBounds&
     return ret;
 }
 
+namespace {
+std::set<StringData> getMultikeyFields(const BSONObj& keyPattern,
+                                       const MultikeyPaths& multikeyPaths) {
+    std::set<StringData> multikeyFields;
+    size_t i = 0;
+    for (auto&& elem : keyPattern) {
+        if (!multikeyPaths[i].empty()) {
+            multikeyFields.insert(elem.fieldNameStringData());
+        }
+        ++i;
+    }
+    return multikeyFields;
+}
+}  // namespace
+
 void IndexScanNode::computeProperties() {
     _sorts.clear();
 
+    // If the index is multikey but does not have path-level multikey metadata, then this index
+    // cannot provide any sorts.
+    if (index.multikey && index.multikeyPaths.empty()) {
+        return;
+    }
+
     BSONObj sortPattern = QueryPlannerAnalysis::getSortPattern(index.keyPattern);
     if (direction == -1) {
         sortPattern = QueryPlannerCommon::reverseSortObj(sortPattern);
@@ -732,6 +753,27 @@ void IndexScanNode::computeProperties() {
             }
         }
     }
+
+    // We cannot provide a sort which involves a multikey field. Prune such sort orders, if the
+    // index is multikey.
+    if (index.multikey) {
+        auto multikeyFields = getMultikeyFields(index.keyPattern, index.multikeyPaths);
+        for (auto sortsIt = _sorts.begin(); sortsIt != _sorts.end();) {
+            bool foundMultikeyField = false;
+            for (auto&& elt : *sortsIt) {
+                if (multikeyFields.find(elt.fieldNameStringData()) != multikeyFields.end()) {
+                    foundMultikeyField = true;
+                    break;
+                }
+            }
+
+            if (foundMultikeyField) {
+                sortsIt = _sorts.erase(sortsIt);
+            } else {
+                ++sortsIt;
+            }
+        }
+    }
 }
 
 QuerySolutionNode* IndexScanNode::clone() const {
@@ -840,8 +882,6 @@ void SortKeyGeneratorNode::appendToString(mongoutils::str::stream* ss, int inden
     *ss << "SORT_KEY_GENERATOR\n";
     addIndent(ss, indent + 1);
     *ss << "sortSpec = " << sortSpec.toString() << '\n';
-    addIndent(ss, indent + 1);
-    *ss << "queryObj = " << queryObj.toString() << '\n';
     addCommon(ss, indent);
     addIndent(ss, indent + 1);
     *ss << "Child:" << '\n';
@@ -851,7 +891,6 @@ void SortKeyGeneratorNode::appendToString(mongoutils::str::stream* ss, int inden
 QuerySolutionNode* SortKeyGeneratorNode::clone() const {
     SortKeyGeneratorNode* copy = new SortKeyGeneratorNode();
     cloneBaseData(copy);
-    copy->queryObj = this->queryObj;
     copy->sortSpec = this->sortSpec;
     return copy;
 }
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index 7e68378042d..c2187385adb 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -597,10 +597,6 @@ struct SortKeyGeneratorNode : public QuerySolutionNode {
 
     void appendToString(mongoutils::str::stream* ss, int indent) const final;
 
-    // The query predicate provided by the user. For sorted by an array field, the sort key depends
-    // on the predicate.
-    BSONObj queryObj;
-
     // The user-supplied sort pattern.
     BSONObj sortSpec;
 };
diff --git a/src/mongo/db/query/query_solution_test.cpp b/src/mongo/db/query/query_solution_test.cpp
index fe9749d49c3..a3a76deaa43 100644
--- a/src/mongo/db/query/query_solution_test.cpp
+++ b/src/mongo/db/query/query_solution_test.cpp
@@ -830,4 +830,70 @@ TEST(QuerySolutionTest, MultikeyIndexCannotCoverFieldWithAnyMultikeyPathComponen
     ASSERT_TRUE(node->hasField("e"));
 }
 
+TEST(QuerySolutionTest, MultikeyIndexWithoutPathLevelInfoCannotProvideAnySorts) {
+    IndexScanNode node{IndexEntry(BSON("a" << 1 << "b" << 1 << "c" << 1))};
+    node.index.multikey = true;
+
+    {
+        OrderedIntervalList oil{};
+        oil.name = "a";
+        oil.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1)));
+        node.bounds.fields.push_back(oil);
+    }
+
+    for (auto&& name : {"b"_sd, "c"_sd}) {
+        OrderedIntervalList oil{};
+        oil.name = name.toString();
+        oil.intervals.push_back(IndexBoundsBuilder::makeRangeInterval(
+            BSON("" << 1 << "" << 2), BoundInclusion::kIncludeBothStartAndEndKeys));
+        node.bounds.fields.push_back(oil);
+    }
+
+    node.computeProperties();
+    ASSERT(node.getSort().empty());
+}
+
+TEST(QuerySolutionTest, SimpleRangeAllEqualExcludesFieldWithMultikeyComponent) {
+    IndexScanNode node{
+        IndexEntry(BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1))};
+    node.bounds.isSimpleRange = true;
+    node.bounds.startKey = BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1);
+    node.bounds.endKey = BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1);
+
+    // Add metadata indicating that "c.z" is multikey.
+    node.index.multikey = true;
+    node.index.multikeyPaths = MultikeyPaths{{}, {}, {1U}, {}, {}};
+
+    node.computeProperties();
+
+    ASSERT_EQUALS(node.getSort().size(), 4U);
+    ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1)));
+    ASSERT(node.getSort().count(BSON("a" << 1)));
+    ASSERT(node.getSort().count(BSON("d" << 1 << "e" << 1)));
+    ASSERT(node.getSort().count(BSON("e" << 1)));
+}
+
+TEST(QuerySolutionTest, NonSimpleRangeAllEqualExcludesFieldWithMultikeyComponent) {
+    IndexScanNode node{
+        IndexEntry(BSON("a" << 1 << "b" << 1 << "c.z" << 1 << "d" << 1 << "e" << 1))};
+    // Add metadata indicating that "c.z" is multikey.
+    node.index.multikey = true;
+    node.index.multikeyPaths = MultikeyPaths{{}, {}, {1U}, {}, {}};
+
+    for (auto&& name : {"a"_sd, "b"_sd, "c.z"_sd, "d"_sd, "e"_sd}) {
+        OrderedIntervalList oil{};
+        oil.name = name.toString();
+        oil.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1)));
+        node.bounds.fields.push_back(oil);
+    }
+
+    node.computeProperties();
+
+    ASSERT_EQUALS(node.getSort().size(), 4U);
+    ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1)));
+    ASSERT(node.getSort().count(BSON("a" << 1)));
+    ASSERT(node.getSort().count(BSON("d" << 1 << "e" << 1)));
+    ASSERT(node.getSort().count(BSON("e" << 1)));
+}
+
 }  // namespace
diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp
index 3636b2e8424..88200659335 100644
--- a/src/mongo/db/query/stage_builder.cpp
+++ b/src/mongo/db/query/stage_builder.cpp
@@ -129,12 +129,8 @@ PlanStage* buildStages(OperationContext* opCtx,
             if (nullptr == childStage) {
                 return nullptr;
             }
-            return new SortKeyGeneratorStage(opCtx,
-                                             childStage,
-                                             ws,
-                                             keyGenNode->sortSpec,
-                                             keyGenNode->queryObj,
-                                             cq.getCollator());
+            return new SortKeyGeneratorStage(
+                opCtx, childStage, ws, keyGenNode->sortSpec, cq.getCollator());
         }
         case STAGE_PROJECTION: {
             const ProjectionNode* pn = static_cast<const ProjectionNode*>(root);
diff --git a/src/mongo/dbtests/query_stage_ensure_sorted.cpp b/src/mongo/dbtests/query_stage_ensure_sorted.cpp
index 982da6ad70a..29fe3fe5708 100644
--- a/src/mongo/dbtests/query_stage_ensure_sorted.cpp
+++ b/src/mongo/dbtests/query_stage_ensure_sorted.cpp
@@ -79,7 +79,7 @@ public:
         // Initialization.
         BSONObj pattern = fromjson(patternStr);
         auto sortKeyGen = stdx::make_unique<SortKeyGeneratorStage>(
-            opCtx.get(), queuedDataStage.release(), &ws, pattern, BSONObj(), collator);
+            opCtx.get(), queuedDataStage.release(), &ws, pattern, collator);
         EnsureSortedStage ess(opCtx.get(), pattern, &ws, sortKeyGen.release());
         WorkingSetID id = WorkingSet::INVALID_ID;
         PlanStage::StageState state = PlanStage::NEED_TIME;
@@ -117,7 +117,7 @@ TEST_F(QueryStageEnsureSortedTest, EnsureSortedEmptyWorkingSet) {
     WorkingSet ws;
     auto queuedDataStage = stdx::make_unique<QueuedDataStage>(opCtx.get(), &ws);
     auto sortKeyGen = stdx::make_unique<SortKeyGeneratorStage>(
-        opCtx.get(), queuedDataStage.release(), &ws, BSONObj(), BSONObj(), nullptr);
+        opCtx.get(), queuedDataStage.release(), &ws, BSONObj(), nullptr);
     EnsureSortedStage ess(opCtx.get(), BSONObj(), &ws, sortKeyGen.release());
 
     WorkingSetID id = WorkingSet::INVALID_ID;
diff --git a/src/mongo/dbtests/query_stage_sort.cpp b/src/mongo/dbtests/query_stage_sort.cpp
index efe7c4c5ece..9ab3fb4fd32 100644
--- a/src/mongo/dbtests/query_stage_sort.cpp
+++ b/src/mongo/dbtests/query_stage_sort.cpp
@@ -120,7 +120,7 @@ public:
         params.limit = limit();
 
         auto keyGenStage = make_unique<SortKeyGeneratorStage>(
-            &_opCtx, queuedDataStage.release(), ws.get(), params.pattern, BSONObj(), nullptr);
+            &_opCtx, queuedDataStage.release(), ws.get(), params.pattern, nullptr);
 
         auto ss = make_unique<SortStage>(&_opCtx, params, ws.get(), keyGenStage.release());
 
@@ -159,7 +159,7 @@ public:
         params.limit = limit();
 
         auto keyGenStage = make_unique<SortKeyGeneratorStage>(
-            &_opCtx, queuedDataStage.release(), ws.get(), params.pattern, BSONObj(), nullptr);
+            &_opCtx, queuedDataStage.release(), ws.get(), params.pattern, nullptr);
 
         auto sortStage = make_unique<SortStage>(&_opCtx, params, ws.get(), keyGenStage.release());
 
@@ -560,7 +560,7 @@ public:
         params.limit = 0;
 
         auto keyGenStage = make_unique<SortKeyGeneratorStage>(
-            &_opCtx, queuedDataStage.release(), ws.get(), params.pattern, BSONObj(), nullptr);
+            &_opCtx, queuedDataStage.release(), ws.get(), params.pattern, nullptr);
 
         auto sortStage = make_unique<SortStage>(&_opCtx, params, ws.get(), keyGenStage.release());
 
diff --git a/src/mongo/dbtests/sort_key_generator_test.cpp b/src/mongo/dbtests/sort_key_generator_test.cpp
index 0f25f214c07..c7baa9c664a 100644
--- a/src/mongo/dbtests/sort_key_generator_test.cpp
+++ b/src/mongo/dbtests/sort_key_generator_test.cpp
@@ -50,10 +50,7 @@ namespace {
  *
  * Returns the BSON representation of the sort key, to be checked against the expected sort key.
  */
-BSONObj extractSortKey(const char* sortSpec,
-                       const char* doc,
-                       const char* query,
-                       const CollatorInterface* collator) {
+BSONObj extractSortKey(const char* sortSpec, const char* doc, const CollatorInterface* collator) {
     QueryTestServiceContext serviceContext;
     auto opCtx = serviceContext.makeOperationContext();
 
@@ -62,8 +59,8 @@ BSONObj extractSortKey(const char* sortSpec,
     wsm.transitionToOwnedObj();
 
     BSONObj sortKey;
-    auto sortKeyGen = stdx::make_unique<SortKeyGenerator>(
-        opCtx.get(), fromjson(sortSpec), fromjson(query), collator);
+    auto sortKeyGen =
+        stdx::make_unique<SortKeyGenerator>(opCtx.get(), fromjson(sortSpec), collator);
     ASSERT_OK(sortKeyGen->getSortKey(wsm, &sortKey));
 
     return sortKey;
@@ -93,49 +90,49 @@ BSONObj extractSortKeyCovered(const char* sortSpec,
 
     BSONObj sortKey;
     auto sortKeyGen =
-        stdx::make_unique<SortKeyGenerator>(opCtx.get(), fromjson(sortSpec), BSONObj(), collator);
+        stdx::make_unique<SortKeyGenerator>(opCtx.get(), fromjson(sortSpec), collator);
     ASSERT_OK(sortKeyGen->getSortKey(*wsm, &sortKey));
 
     return sortKey;
 }
 
 TEST(SortKeyGeneratorTest, SortKeyNormal) {
-    BSONObj actualOut = extractSortKey("{a: 1}", "{_id: 0, a: 5}", "", nullptr);
+    BSONObj actualOut = extractSortKey("{a: 1}", "{_id: 0, a: 5}", nullptr);
     BSONObj expectedOut = BSON("" << 5);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
 TEST(SortKeyGeneratorTest, SortKeyNormal2) {
-    BSONObj actualOut = extractSortKey("{a: 1}", "{_id: 0, z: 10, a: 6, b: 16}", "", nullptr);
+    BSONObj actualOut = extractSortKey("{a: 1}", "{_id: 0, z: 10, a: 6, b: 16}", nullptr);
     BSONObj expectedOut = BSON("" << 6);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
 TEST(SortKeyGeneratorTest, SortKeyString) {
     BSONObj actualOut =
-        extractSortKey("{a: 1}", "{_id: 0, z: 'thing1', a: 'thing2', b: 16}", "", nullptr);
+        extractSortKey("{a: 1}", "{_id: 0, z: 'thing1', a: 'thing2', b: 16}", nullptr);
     BSONObj expectedOut = BSON(""
                                << "thing2");
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
 TEST(SortKeyGeneratorTest, SortKeyCompound) {
-    BSONObj actualOut = extractSortKey(
-        "{a: 1, b: 1}", "{_id: 0, z: 'thing1', a: 99, c: {a: 4}, b: 16}", "", nullptr);
+    BSONObj actualOut =
+        extractSortKey("{a: 1, b: 1}", "{_id: 0, z: 'thing1', a: 99, c: {a: 4}, b: 16}", nullptr);
     BSONObj expectedOut = BSON("" << 99 << "" << 16);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
 TEST(SortKeyGeneratorTest, SortKeyEmbedded) {
     BSONObj actualOut = extractSortKey(
-        "{'c.a': 1, b: 1}", "{_id: 0, z: 'thing1', a: 99, c: {a: 4}, b: 16}", "", nullptr);
+        "{'c.a': 1, b: 1}", "{_id: 0, z: 'thing1', a: 99, c: {a: 4}, b: 16}", nullptr);
     BSONObj expectedOut = BSON("" << 4 << "" << 16);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
 TEST(SortKeyGeneratorTest, SortKeyArray) {
     BSONObj actualOut = extractSortKey(
-        "{'c': 1, b: 1}", "{_id: 0, z: 'thing1', a: 99, c: [2, 4, 1], b: 16}", "", nullptr);
+        "{'c': 1, b: 1}", "{_id: 0, z: 'thing1', a: 99, c: [2, 4, 1], b: 16}", nullptr);
     BSONObj expectedOut = BSON("" << 1 << "" << 16);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
@@ -194,7 +191,7 @@ TEST(SortKeyGeneratorTest, SortKeyCoveredCompound3) {
 TEST(SortKeyGeneratorTest, ExtractStringSortKeyWithCollatorUsesComparisonKey) {
     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
     BSONObj actualOut =
-        extractSortKey("{a: 1}", "{_id: 0, z: 'thing1', a: 'thing2', b: 16}", "", &collator);
+        extractSortKey("{a: 1}", "{_id: 0, z: 'thing1', a: 'thing2', b: 16}", &collator);
     BSONObj expectedOut = BSON(""
                                << "2gniht");
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
@@ -202,7 +199,7 @@ TEST(SortKeyGeneratorTest, ExtractStringSortKeyWithCollatorUsesComparisonKey) {
 
 TEST(SortKeyGeneratorTest, CollatorHasNoEffectWhenExtractingNonStringSortKey) {
     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
-    BSONObj actualOut = extractSortKey("{a: 1}", "{_id: 0, z: 10, a: 6, b: 16}", "", &collator);
+    BSONObj actualOut = extractSortKey("{a: 1}", "{_id: 0, z: 10, a: 6, b: 16}", &collator);
     BSONObj expectedOut = BSON("" << 6);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
@@ -220,28 +217,26 @@ TEST(SortKeyGeneratorTest, CollatorHasNoAffectWhenExtractingCoveredSortKey) {
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
-TEST(SortKeyGeneratorTest, SortKeyGenerationForArraysUsesTheQueryPredicate) {
-    BSONObj actualOut =
-        extractSortKey("{a: -1}", "{_id: 0, a: [1, 2, 3, 4]}", "{a: {$lt: 3}}", nullptr);
-    BSONObj expectedOut = BSON("" << 2);
+TEST(SortKeyGeneratorTest, SortKeyGenerationForArraysChoosesCorrectKey) {
+    BSONObj actualOut = extractSortKey("{a: -1}", "{_id: 0, a: [1, 2, 3, 4]}", nullptr);
+    BSONObj expectedOut = BSON("" << 4);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
 TEST(SortKeyGeneratorTest, EnsureSortKeyGenerationForArraysRespectsCollation) {
     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
     BSONObj actualOut =
-        extractSortKey("{a: 1}", "{_id: 0, a: ['aaz', 'zza', 'yya', 'zzb']}", "", &collator);
+        extractSortKey("{a: 1}", "{_id: 0, a: ['aaz', 'zza', 'yya', 'zzb']}", &collator);
     BSONObj expectedOut = BSON(""
                                << "ayy");
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }
 
-TEST(SortKeyGeneratorTest, EnsureSortKeyGenerationForArraysWithPredicateRespectsCollation) {
-    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
-    BSONObj actualOut = extractSortKey(
-        "{a: 1}", "{_id: 0, a: ['aaz', 'zza', 'yya', 'zzb']}", "{a: {$gt: 'yya'}}", &collator);
-    BSONObj expectedOut = BSON(""
-                               << "azz");
+TEST(SortKeyGeneratorTest, SortKeyGenerationForArraysRespectsCompoundOrdering) {
+    BSONObj actualOut = extractSortKey("{'a.b': 1, 'a.c': -1}",
+                                       "{_id: 0, a: [{b: 1, c: 0}, {b: 0, c: 3}, {b: 0, c: 1}]}",
+                                       nullptr);
+    BSONObj expectedOut = BSON("" << 0 << "" << 3);
     ASSERT_BSONOBJ_EQ(actualOut, expectedOut);
 }