SERVER-15200 Optimize projection to occur before sort when possible.

When the projection is statically known to reduce the size
of the data (i.e. when the projection does not add any newly
computed fields), then evaluating the projection first is
beneficial because it reduces the size of the data which
must be sorted.

10 files changed, 296 insertions, 58 deletions

diff --git a/jstests/core/wildcard_index_nonblocking_sort.js b/jstests/core/wildcard_index_nonblocking_sort.js
index 2537906b412..7e2ab7e073f 100644
--- a/jstests/core/wildcard_index_nonblocking_sort.js
+++ b/jstests/core/wildcard_index_nonblocking_sort.js
@@ -7,6 +7,7 @@ load("jstests/libs/analyze_plan.js");         // For getPlanStages().
 load("jstests/libs/fixture_helpers.js");      // For numberOfShardsForCollection().
 
 const coll = db.wildcard_nonblocking_sort;
+coll.drop();
 
 assert.commandWorked(coll.createIndex({"$**": 1}, {wildcardProjection: {"excludedField": 0}}));
 
@@ -28,14 +29,14 @@ function checkQueryUsesSortType(query, sort, projection, isBlocking) {
     const sorts = getPlanStages(plan, "SORT");
 
     if (isBlocking) {
-        assert.eq(sorts.length, FixtureHelpers.numberOfShardsForCollection(coll));
-        assert.eq(sorts[0].sortPattern, sort);
+        assert.eq(sorts.length, FixtureHelpers.numberOfShardsForCollection(coll), explain);
+        assert.eq(sorts[0].sortPattern, sort, explain);
 
         // A blocking sort may or may not use the index, so we don't check the length of
         // 'ixScans'.
     } else {
-        assert.eq(sorts.length, 0);
-        assert.eq(ixScans.length, FixtureHelpers.numberOfShardsForCollection(coll));
+        assert.eq(sorts.length, 0, explain);
+        assert.eq(ixScans.length, FixtureHelpers.numberOfShardsForCollection(coll), explain);
 
         const sortKey = Object.keys(sort)[0];
         assert.docEq(ixScans[0].keyPattern, {$_path: 1, [sortKey]: 1});
diff --git a/src/mongo/db/query/planner_analysis.cpp b/src/mongo/db/query/planner_analysis.cpp
index d002f6ab390..6432e1cbe4b 100644
--- a/src/mongo/db/query/planner_analysis.cpp
+++ b/src/mongo/db/query/planner_analysis.cpp
@@ -390,6 +390,89 @@ std::unique_ptr<ProjectionNode> analyzeProjection(const CanonicalQuery& query,
         *query.root(),
         *query.getProj());
 }
+
+/**
+ * Given the solution tree 'root', attempts to push a projection at the root of the tree beneath a
+ * SORT node. Returns the tree with this optimization applied, or the unmodified tree if the
+ * optimization was not legal.
+ *
+ * Applying the projection before the sort is beneficial when it reduces the amount of data that
+ * needs to be sorted.
+ */
+std::unique_ptr<QuerySolutionNode> tryPushdownProjectBeneathSort(
+    std::unique_ptr<QuerySolutionNode> root) {
+    if (StageType::STAGE_PROJECTION_DEFAULT != root->getType() &&
+        StageType::STAGE_PROJECTION_COVERED != root->getType() &&
+        StageType::STAGE_PROJECTION_SIMPLE != root->getType()) {
+        // There's no projection to push down.
+        return root;
+    }
+
+    auto projectNode = static_cast<ProjectionNode*>(root.get());
+    if (projectNode->proj.hasExpressions()) {
+        // If the projection has any expressions, then we refrain from moving it underneath the
+        // sort. It's possible that the addition of computed fields increases the size of the data
+        // to sort, in which case it would be better to sort first and then project.
+        return root;
+    }
+
+    if (projectNode->children[0]->getType() != StageType::STAGE_SORT) {
+        return root;
+    }
+
+    auto sortNode = static_cast<SortNode*>(root->children[0]);
+
+    // Don't perform this optimization if the sort is a top-k sort. We would be wasting work
+    // computing projections for documents that are discarded since they are not in the top-k set.
+    if (sortNode->limit > 0) {
+        return root;
+    }
+
+    if (sortNode->children[0]->getType() != StageType::STAGE_SORT_KEY_GENERATOR) {
+        return root;
+    }
+
+    auto sortKeyGenerator = static_cast<SortKeyGeneratorNode*>(sortNode->children[0]);
+
+    // It is only legal to push down the projection it if preserves all of the fields on which we
+    // need to sort.
+    for (auto&& sortComponent : sortNode->pattern) {
+        if (!projectNode->hasField(sortComponent.fieldNameStringData().toString())) {
+            return root;
+        }
+    }
+
+    // Perform the swap. We are starting with the following structure:
+    //   PROJECT => SORT => SORT_KEY_GENERATOR => CHILD
+    //
+    // This needs to be transformed to the following:
+    //   SORT => SORT_KEY_GENERATOR => PROJECT => CHILD
+    //
+    // First, detach the sort key generator node from the tree by clearing its
+    // child vector.
+    std::unique_ptr<QuerySolutionNode> restOfTree{sortKeyGenerator->children[0]};
+    invariant(sortKeyGenerator->children.size() == 1u);
+    sortKeyGenerator->children.clear();
+
+    // Next, detach the sort from the projection and assume ownership of it.
+    std::unique_ptr<QuerySolutionNode> ownedSortNode{sortNode};
+    sortNode = nullptr;
+    invariant(projectNode->children.size() == 1u);
+    projectNode->children.clear();
+
+    // Attach the lower part of the tree as the child of the projection.
+    std::unique_ptr<QuerySolutionNode> ownedProjectionNode = std::move(root);
+    ownedProjectionNode->children.push_back(restOfTree.release());
+
+    // Attach the projection as the child of the sort key generator.
+    sortKeyGenerator->children.push_back(ownedProjectionNode.release());
+
+    // Re-compute properties so that they reflect the new structure of the tree.
+    ownedSortNode->computeProperties();
+
+    return ownedSortNode;
+}
+
 }  // namespace
 
 // static
@@ -828,6 +911,8 @@ std::unique_ptr<QuerySolution> QueryPlannerAnalysis::analyzeDataAccess(
         }
     }
 
+    solnRoot = tryPushdownProjectBeneathSort(std::move(solnRoot));
+
     soln->root = std::move(solnRoot);
     return soln;
 }
diff --git a/src/mongo/db/query/projection.cpp b/src/mongo/db/query/projection.cpp
index 1aa9e2c1990..37921ec515e 100644
--- a/src/mongo/db/query/projection.cpp
+++ b/src/mongo/db/query/projection.cpp
@@ -237,7 +237,7 @@ std::pair<const ASTNode*, size_t> findCommonPoint(const ASTNode* astNode,
 }
 }  // namespace
 
-bool Projection::isFieldRetainedExactly(StringData path) {
+bool Projection::isFieldRetainedExactly(StringData path) const {
     FieldPath fieldPath(path);
 
     const auto [node, pathIndex] = findCommonPoint(&_root, fieldPath, 0);
diff --git a/src/mongo/db/query/projection.h b/src/mongo/db/query/projection.h
index 69f9df57b4c..a1ceb8754ba 100644
--- a/src/mongo/db/query/projection.h
+++ b/src/mongo/db/query/projection.h
@@ -108,7 +108,7 @@ public:
      * and false otherwise. For example, the projection {a: 1} will preserve the element located at
      * 'a.b', and the projection {'a.b': 0} will not preserve the element located at 'a'.
      */
-    bool isFieldRetainedExactly(StringData path);
+    bool isFieldRetainedExactly(StringData path) const;
 
     /**
      * A projection is considered "simple" if it doesn't require the full document, operates only
@@ -120,6 +120,14 @@ public:
             !_deps.metadataRequested.any() && !_deps.requiresDocument && !_deps.hasExpressions;
     }
 
+    /**
+     * Returns true if this projection has any fields which are the result of computing an
+     * expression.
+     */
+    bool hasExpressions() const {
+        return _deps.hasExpressions;
+    }
+
 private:
     ProjectionPathASTNode _root;
     ProjectType _type;
diff --git a/src/mongo/db/query/query_planner_collation_test.cpp b/src/mongo/db/query/query_planner_collation_test.cpp
index 5cefee957c1..806e0c0f54d 100644
--- a/src/mongo/db/query/query_planner_collation_test.cpp
+++ b/src/mongo/db/query/query_planner_collation_test.cpp
@@ -581,8 +581,8 @@ TEST_F(QueryPlannerTest, CanProduceCoveredSortPlanWhenQueryHasCollationButIndexD
 
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {a: 1, b: 1}, limit: 0, node: "
-        "{sortKeyGen:{node: {ixscan: {pattern: {a: 1, b: 1}}}}}}}}}");
+        "{sort: {pattern: {a: 1, b: 1}, limit: 0, node: {sortKeyGen: {node: "
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}}}}}");
 }
 
 TEST_F(QueryPlannerTest, CannotUseIndexWhenQueryHasNoCollationButIndexHasNonSimpleCollation) {
@@ -594,8 +594,8 @@ TEST_F(QueryPlannerTest, CannotUseIndexWhenQueryHasNoCollationButIndexHasNonSimp
 
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {a: 1, b: 1}, limit: 0, node: "
-        "{sortKeyGen:{node: {cscan: {dir: 1}}}}}}}}");
+        "{sort: {pattern: {a: 1, b: 1}, limit: 0, node: {sortKeyGen: {node: "
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node: {cscan: {dir: 1}}}}}}}}");
 }
 
 TEST_F(QueryPlannerTest, CannotUseIndexWhenQueryHasDifferentNonSimpleCollationThanIndex) {
@@ -608,8 +608,8 @@ TEST_F(QueryPlannerTest, CannotUseIndexWhenQueryHasDifferentNonSimpleCollationTh
 
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {a: 1, b: 1}, limit: 0, node: "
-        "{sortKeyGen:{node: {cscan: {dir: 1}}}}}}}}");
+        "{sort: {pattern: {a: 1, b: 1}, limit: 0, node: {sortKeyGen: {node: "
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node: {cscan: {dir: 1}}}}}}}}");
 }
 
 /**
@@ -625,14 +625,14 @@ TEST_F(QueryPlannerTest, MustFetchBeforeSortWhenQueryHasSameNonSimpleCollationAs
 
     runQueryAsCommand(
         fromjson("{find: 'testns', filter: {a: {$gt: 0}}, projection: {a: 1, b:1, _id: 0}, "
-                 "collation: {locale: "
-                 "'reverse'}, sort: {b: 1, a: 1}}"));
+                 "collation: {locale: 'reverse'}, sort: {b: 1, a: 1}}"));
 
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {b: 1, a: 1}, limit: 0, node: "
-        "{sortKeyGen:{node: {fetch: {filter: null, collation: {locale: 'reverse'}, node: {ixscan: "
-        "{pattern: {a: 1, b: 1}}}}}}}}}}}}}");
+        "{sort: {pattern: {b: 1, a: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node:"
+        "{fetch: {filter: null, collation: {locale: 'reverse'}, node:"
+        "{ixscan: {pattern: {a: 1, b: 1}}}}}}}}}}}}}");
 }
 
 TEST_F(QueryPlannerTest, NoSortStageWhenMinMaxIndexCollationDoesNotMatchButBoundsContainNoStrings) {
diff --git a/src/mongo/db/query/query_planner_index_test.cpp b/src/mongo/db/query/query_planner_index_test.cpp
index 1ec1f6e19ca..27500f73f9a 100644
--- a/src/mongo/db/query/query_planner_index_test.cpp
+++ b/src/mongo/db/query/query_planner_index_test.cpp
@@ -1258,9 +1258,9 @@ TEST_F(QueryPlannerTest, NoFetchStageWhenSingleFieldSortIsCoveredByIndex) {
                  "sort: {b: 1}}"));
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {b: 1}, limit: 0, node: "
-        "{sortKeyGen:{node: {ixscan: "
-        "{pattern: {a: 1, b: 1}}}}}}}}}");
+        "{sort: {pattern: {b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node:"
+        "{ixscan: {pattern: {a: 1, b: 1}}}}}}}}}");
 }
 
 TEST_F(QueryPlannerTest, NoFetchStageWhenTwoFieldAscendingSortIsCoveredByIndex) {
@@ -1273,9 +1273,9 @@ TEST_F(QueryPlannerTest, NoFetchStageWhenTwoFieldAscendingSortIsCoveredByIndex)
                  "sort: {b: 1, a: 1}}"));
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {b: 1, a: 1}, limit: 0, node: "
-        "{sortKeyGen:{node: {ixscan: "
-        "{pattern: {a: 1, b: 1}}}}}}}}}");
+        "{sort: {pattern: {b: 1, a: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node:"
+        "{ixscan: {pattern: {a: 1, b: 1}}}}}}}}}");
 }
 
 TEST_F(QueryPlannerTest, NoFetchStageWhenTwoFieldMixedSortOrderSortIsCoveredByIndex) {
@@ -1288,9 +1288,8 @@ TEST_F(QueryPlannerTest, NoFetchStageWhenTwoFieldMixedSortOrderSortIsCoveredByIn
                  "sort: {b: 1, a: -1}}"));
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {b: 1, a: -1}, limit: 0, node: "
-        "{sortKeyGen:{node: {ixscan: "
-        "{pattern: {a: 1, b: 1}}}}}}}}}");
+        "{sort: {pattern: {b: 1, a: -1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}}}}}");
 }
 
 TEST_F(QueryPlannerTest, MustFetchWhenNotAllSortKeysAreCoveredByIndex) {
diff --git a/src/mongo/db/query/query_planner_operator_test.cpp b/src/mongo/db/query/query_planner_operator_test.cpp
index 2e69c42e1cf..b84f22a7bcc 100644
--- a/src/mongo/db/query/query_planner_operator_test.cpp
+++ b/src/mongo/db/query/query_planner_operator_test.cpp
@@ -125,8 +125,9 @@ TEST_F(QueryPlannerTest, CoveredWhenQueryOnNonMultikeyDottedPath) {
 
     assertNumSolutions(1U);
     assertSolutionExists(
-        "{proj: {spec: {a: 1, 'b.c': 1, _id: 0}, node: {sort: {pattern: {'b.c': 1}, limit: 0, "
-        "node: {sortKeyGen:{node: {ixscan: {pattern: {a: 1, 'b.c': 1}}}}}}}}}}}");
+        "{sort: {pattern: {'b.c': 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {a: 1, 'b.c': 1, _id: 0}, node: "
+        "{ixscan: {pattern: {a: 1, 'b.c': 1}}}}}}}}}");
 }
 
 TEST_F(QueryPlannerTest, MustFetchWhenFilterNonEmptyButMissingLeadingField) {
@@ -191,8 +192,8 @@ TEST_F(QueryPlannerTest, CanProduceCoveredSortPlanWhenSortOrderDifferentThanInde
     assertNumSolutions(1U);
 
     assertSolutionExists(
-        "{proj: {spec: {a: 1, b:1, _id: 0}, node: {sort: {pattern: {b: 1, a: 1}, limit: 0, node: "
-        "{sortKeyGen:{node: {ixscan: {pattern: {a: 1, b: 1}}}}}}}}}");
+        "{sort: {pattern: {b: 1, a: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {a: 1, b: 1, _id: 0}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}}}}}");
 }
 
 // $eq can use a hashed index because it looks for values of type regex;
@@ -1483,8 +1484,8 @@ TEST_F(QueryPlannerTest, NENullWithSortAndProjection) {
 
     assertNumSolutions(2U);
     assertSolutionExists(
-        "{proj: {spec: {_id: 0, a: 1}, node: {sort: {pattern: {a: 1}, limit: 0, node: {sortKeyGen: "
-        "{node: {cscan: {dir: 1}}}}}}}}");
+        "{sort: {pattern: {a: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {_id: 0, a: 1}, node: {cscan: {dir: 1}}}}}}}}");
     assertSolutionExists(
         "{proj: {spec: {_id: 0, a: 1}, node: {"
         "  ixscan: {pattern: {a:1}, bounds: {"
@@ -1546,5 +1547,69 @@ TEST_F(QueryPlannerTest, FetchAfterSortWhenOnlyProjectNeedsDocuments) {
         "{pattern: {a: 1, b: 1}}}}}}}}}}}");
 }
 
+TEST_F(QueryPlannerTest, ExclusionProjectionCanSwapBeneathSort) {
+    runQueryAsCommand(fromjson("{find: 'testns', projection: {a: 0, b: 0}, sort: {c: 1, d: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{sort: {pattern: {c: 1, d: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {a: 0, b: 0}, node: {cscan: {dir: 1}}}}}}}}");
+}
+
+TEST_F(QueryPlannerTest, ProjectionWithExpressionDoesNotSwapBeneathSort) {
+    runQueryAsCommand(
+        fromjson("{find: 'testns', "
+                 "projection: {_id: 0, a: 1, b: 1, c: {$add: ['$c', '$e']}}, sort: {a: 1, b: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{proj: {spec: {_id: 0, a: 1, b: 1, c: {$add: ['$c', '$e']}}, node:"
+        "{sort: {pattern: {a: 1, b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{cscan: {dir: 1}}}}}}}}");
+}
+
+TEST_F(QueryPlannerTest, ProjectionWithConstantExpressionDoesNotSwapBeneathSort) {
+    runQueryAsCommand(
+        fromjson("{find: 'testns', "
+                 "projection: {_id: 0, a: 1, b: 1, c: 'constant'}, sort: {a: 1, b: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{proj: {spec: {_id: 0, a: 1, b: 1, c: 'constant'}, node:"
+        "{sort: {pattern: {a: 1, b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{cscan: {dir: 1}}}}}}}}");
+}
+
+TEST_F(QueryPlannerTest, InclusionProjectionCannotSwapBeneathSortIfItExcludesSortedOnField) {
+    runQueryAsCommand(fromjson("{find: 'testns', projection: {_id: 0, a: 1}, sort: {a: 1, b: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{proj: {spec: {_id: 0, a: 1}, node:"
+        "{sort: {pattern: {a: 1, b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{cscan: {dir: 1}}}}}}}}");
+}
+
+TEST_F(QueryPlannerTest, ExclusionProjectionCannotSwapBeneathSortIfItExcludesSortedOnField) {
+    runQueryAsCommand(fromjson("{find: 'testns', projection: {b: 0}, sort: {a: 1, b: 1}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{proj: {spec: {b: 0}, node:"
+        "{sort: {pattern: {a: 1, b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{cscan: {dir: 1}}}}}}}}");
+}
+
+TEST_F(QueryPlannerTest, ProjectionDoesNotSwapBeforeSortWithLimit) {
+    runQueryAsCommand(
+        fromjson("{find: 'testns', projection: {_id: 0, a: 1, b: 1}, sort: {a: 1}, limit: 3}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{proj: {spec: {_id: 0, a: 1, b: 1}, node:"
+        "{sort: {pattern: {a: 1}, limit: 3, node: {sortKeyGen: {node:"
+        "{cscan: {dir: 1}}}}}}}}");
+}
+
 }  // namespace
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner_wildcard_index_test.cpp b/src/mongo/db/query/query_planner_wildcard_index_test.cpp
index 4044262b10a..58a217c941e 100644
--- a/src/mongo/db/query/query_planner_wildcard_index_test.cpp
+++ b/src/mongo/db/query/query_planner_wildcard_index_test.cpp
@@ -1945,4 +1945,41 @@ TEST_F(QueryPlannerWildcardTest, StringComparisonWithEqualCollatorsAndWildcardIn
         "bounds: {'$_path': [['a','a',true,true]], 'a': [['','oof',true,false]]}}}}}");
 }
 
+TEST_F(QueryPlannerWildcardTest, CanUseWildcardIndexAndPushProjectionBeneathSort) {
+    addWildcardIndex(BSON("$**" << 1));
+    runQueryAsCommand(fromjson(
+        "{find: 'testns', filter: {a: 1, b: {$gt: 0}}, projection: {_id: 0, b: 1}, sort: {b: 1}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{proj: {spec: {_id: 0, b: 1}, node: {fetch: {filter: {a: 1}, node:"
+        "{ixscan: {filter: null, pattern: {$_path: 1, b: 1}, bounds: "
+        "{$_path: [['b','b',true,true]], b: [[0,Infinity,false,true]]}}}}}}}");
+    assertSolutionExists(
+        "{sort: {pattern: {b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {_id: 0, b: 1}, node: {fetch: {filter: {b: {$gt: 0}}, node:"
+        "{ixscan: {filter: null, pattern: {$_path: 1, a: 1}, bounds:"
+        "{$_path: [['a','a',true,true]], a: [[1,1,true,true]]}}}}}}}}}}}");
+}
+
+TEST_F(QueryPlannerWildcardTest, CanPushProjectionBeneathSortWithExistsPredicate) {
+    addWildcardIndex(BSON("$**" << 1));
+    runQueryAsCommand(
+        fromjson("{find: 'testns', filter: {a: 1, b: {$exists: true}}, projection: {_id: 0, b: 1}, "
+                 "sort: {b: 1}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{sort: {pattern: {b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {_id: 0, b: 1}, node: {fetch: {filter: {a: {$eq: 1}}, node:"
+        "{ixscan: {filter: null, pattern: {$_path: 1, b: 1}, bounds:"
+        "{$_path: [['b','b',true,true], ['b.', 'b/', true, false]],"
+        "b: [['MinKey','MaxKey',true,true]]}}}}}}}}}}}");
+    assertSolutionExists(
+        "{sort: {pattern: {b: 1}, limit: 0, node: {sortKeyGen: {node:"
+        "{proj: {spec: {_id: 0, b: 1}, node: {fetch: {filter: {b: {$exists: true}}, node:"
+        "{ixscan: {filter: null, pattern: {$_path: 1, a: 1}, bounds:"
+        "{$_path: [['a','a',true,true]], a: [[1,1,true,true]]}}}}}}}}}}}");
+}
+
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index 20a2746ec1a..63394c1559b 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -700,31 +700,53 @@ std::set<StringData> getMultikeyFields(const BSONObj& keyPattern,
     return multikeyFields;
 }
 
+
 /**
- * Computes sort orders for index scans, including DISTINCT_SCAN. The 'sortsOut' set gets populated
- * with all the sort orders that will be provided by the index scan, and the 'multikeyFieldsOut'
- * field gets populated with the names of all fields that the index indicates are multikey.
+ * Populates 'sortsOut' with the sort orders provided by an index scan over 'index', with the given
+ * 'bounds' and 'direction'.
+ *
+ * The caller must ensure that the set pointed to by 'sortsOut' is empty before calling this
+ * function.
  */
-void computeSortsAndMultikeyPathsForScan(const IndexEntry& index,
-                                         int direction,
-                                         const IndexBounds& bounds,
-                                         const CollatorInterface* queryCollator,
-                                         BSONObjSet* sortsOut,
-                                         std::set<StringData>* multikeyFieldsOut) {
-    sortsOut->clear();
-    multikeyFieldsOut->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;
-    }
+void computeSortsForScan(const IndexEntry& index,
+                         int direction,
+                         const IndexBounds& bounds,
+                         const CollatorInterface* queryCollator,
+                         const std::set<StringData>& multikeyFields,
+                         BSONObjSet* sortsOut) {
+    invariant(sortsOut->empty());
 
     BSONObj sortPattern = QueryPlannerAnalysis::getSortPattern(index.keyPattern);
     if (direction == -1) {
         sortPattern = QueryPlannerCommon::reverseSortObj(sortPattern);
     }
 
+    // If 'index' is the result of expanding a wildcard index, then its key pattern should look like
+    // {$_path: 1, <field>: 1}. The "$_path" prefix stores the value of the path associated with the
+    // key as opposed to real user data. We shouldn't report any sort orders including "$_path". In
+    // fact, $-prefixed path components are illegal in queries in most contexts, so misinterpreting
+    // this as a path in user-data could trigger subsequent assertions.
+    if (index.type == IndexType::INDEX_WILDCARD) {
+        invariant(bounds.fields.size() == 2u);
+        // No sorts are provided if the bounds for '$_path' consist of multiple intervals. This can
+        // happen for existence queries. For example, {a: {$exists: true}} results in bounds
+        // [["a","a"], ["a.", "a/")] for '$_path' so that keys from documents where "a" is a nested
+        // object are in bounds.
+        if (bounds.fields[0].intervals.size() != 1u) {
+            return;
+        }
+
+        // Strip '$_path' out of 'sortPattern' and then proceed with regular sort analysis.
+        BSONObjIterator it{sortPattern};
+        invariant(it.more());
+        auto pathElement = it.next();
+        invariant(pathElement.fieldNameStringData() == "$_path"_sd);
+        invariant(it.more());
+        auto secondElement = it.next();
+        invariant(!it.more());
+        sortPattern = BSONObjBuilder{}.append(secondElement).obj();
+    }
+
     sortsOut->insert(sortPattern);
 
     const int nFields = sortPattern.nFields();
@@ -801,12 +823,10 @@ void computeSortsAndMultikeyPathsForScan(const IndexEntry& index,
     // We cannot provide a sort which involves a multikey field. Prune such sort orders, if the
     // index is multikey.
     if (index.multikey) {
-        *multikeyFieldsOut = getMultikeyFields(index.keyPattern, index.multikeyPaths);
         for (auto sortsIt = sortsOut->begin(); sortsIt != sortsOut->end();) {
             bool foundMultikeyField = false;
             for (auto&& elt : *sortsIt) {
-                if (multikeyFieldsOut->find(elt.fieldNameStringData()) !=
-                    multikeyFieldsOut->end()) {
+                if (multikeyFields.find(elt.fieldNameStringData()) != multikeyFields.end()) {
                     foundMultikeyField = true;
                     break;
                 }
@@ -820,6 +840,34 @@ void computeSortsAndMultikeyPathsForScan(const IndexEntry& index,
         }
     }
 }
+
+/**
+ * Computes sort orders for index scans, including DISTINCT_SCAN. The 'sortsOut' set gets populated
+ * with all the sort orders that will be provided by the index scan, and the 'multikeyFieldsOut'
+ * field gets populated with the names of all fields that the index indicates are multikey.
+ */
+void computeSortsAndMultikeyPathsForScan(const IndexEntry& index,
+                                         int direction,
+                                         const IndexBounds& bounds,
+                                         const CollatorInterface* queryCollator,
+                                         BSONObjSet* sortsOut,
+                                         std::set<StringData>* multikeyFieldsOut) {
+    sortsOut->clear();
+    multikeyFieldsOut->clear();
+
+    // If the index is multikey but does not have path-level multikey metadata, then this index
+    // cannot provide any sorts and we need not populate 'multikeyFieldsOut'.
+    if (index.multikey && index.multikeyPaths.empty()) {
+        return;
+    }
+
+    if (index.multikey) {
+        *multikeyFieldsOut = getMultikeyFields(index.keyPattern, index.multikeyPaths);
+    }
+
+    computeSortsForScan(index, direction, bounds, queryCollator, *multikeyFieldsOut, sortsOut);
+}
+
 }  // namespace
 
 void IndexScanNode::computeProperties() {
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index 109241a2d54..95161b63d57 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -596,12 +596,7 @@ struct ProjectionNode : QuerySolutionNode {
     }
 
     bool hasField(const std::string& field) const {
-        // TODO: Returning false isn't always the right answer -- we may either be including
-        // certain fields, or we may be dropping fields (in which case hasField returns true).
-        //
-        // Given that projection sits on top of everything else in .find() it doesn't matter
-        // what we do here.
-        return false;
+        return proj.isFieldRetainedExactly(StringData{field});
     }
 
     bool sortedByDiskLoc() const {