Support wc fields in arbitrary index positions

4 files changed, 223 insertions, 63 deletions

diff --git a/src/mongo/db/query/index_entry.h b/src/mongo/db/query/index_entry.h
index 7c7ba04a532..f67c02167c1 100644
--- a/src/mongo/db/query/index_entry.h
+++ b/src/mongo/db/query/index_entry.h
@@ -250,6 +250,11 @@ struct IndexEntry : CoreIndexInfo {
 
     bool unique;
 
+    // After index expansion, we can't tell which field is the wildcard field in a compound index.
+    // We use this field to track the index into the keyPattern, multikeyPaths, and bounds of the
+    // wildcard field, if one exists.
+    size_t wildcardFieldIndex;
+
     // Geo indices have extra parameters.  We need those available to plan correctly.
     BSONObj infoObj;
 };
diff --git a/src/mongo/db/query/planner_wildcard_helpers.cpp b/src/mongo/db/query/planner_wildcard_helpers.cpp
index fe4c2fed9da..cfe32dc3bc3 100644
--- a/src/mongo/db/query/planner_wildcard_helpers.cpp
+++ b/src/mongo/db/query/planner_wildcard_helpers.cpp
@@ -53,10 +53,18 @@ auto getElement(const BSONObj& keyPattern, int i) {
     return it;
 }
 
-auto getLastElement(const BSONObj& keyPattern) {
-    return getElement(keyPattern, keyPattern.nFields() - 1);
+auto getWildcardIndex(const BSONObj& keyPattern) {
+    int i = 0;
+    for (auto& elem : keyPattern) {
+        if (elem.fieldNameStringData().endsWith("$**"_sd)) {
+            return i;
+        }
+        i++;
+    }
+    return -1;
 }
 
+// Creates a BSONObj representing 'keyPattern' with the wildcard field name replaced by 'fieldName'.
 auto expandIndexKey(const BSONObj& keyPattern, const StringData& fieldName) {
     BSONObjBuilder bb;
     for (auto& elem : keyPattern) {
@@ -69,16 +77,33 @@ auto expandIndexKey(const BSONObj& keyPattern, const StringData& fieldName) {
     return bb.obj();
 }
 
-auto insertPathPlaceHolder(const BSONObj& keyPattern) {
+/*
+ * Push a new entry into the bounds vector for the leading '$_path' bound, and push corresponding
+ * fields into the IndexScanNode's keyPattern and its multikeyPaths vector. Then, update the
+ * wildcardFieldIndex for 'index'.
+ */
+auto insertPathPlaceHolder(IndexEntry* index, IndexBounds* bounds) {
+    auto multikeyItr = index->multikeyPaths.begin();
+    auto fieldsItr = bounds->fields.begin();
+    for (int i = 0; i < (int)index->wildcardFieldIndex; i++) {
+        multikeyItr = std::next(multikeyItr);
+        fieldsItr = std::next(fieldsItr);
+    }
+    index->multikeyPaths.insert(multikeyItr, MultikeyComponents{});
+    bounds->fields.insert(fieldsItr, {"$_path"});
+
     BSONObjBuilder bb;
-    for (auto it = keyPattern.begin(); it != keyPattern.end(); it++) {
-        if (std::next(it) == keyPattern.end()) {
-            // 'it' is pointing to the wildcard element, the last field in the keyPattern.
-            bb.appendAs(*it, "$_path");
+    int j = 0;
+    for (auto& elem : index->keyPattern) {
+        if (j == (int)index->wildcardFieldIndex) {
+            bb.appendAs(elem, "$_path");
         }
-        bb.append(*it);
+        bb.append(elem);
+        j++;
     }
-    return bb.obj();
+    index->keyPattern = bb.obj();
+
+    index->wildcardFieldIndex += 1;
 }
 
 /**
@@ -175,9 +200,9 @@ FieldRef pathWithoutSpecifiedComponents(const FieldRef& path,
 }
 
 /**
- * Returns a MultikeyPaths which indicates which components of of the index key pattern are
- * multikey, by looking up multikeyness in 'multikeyPathSet'. 'indexedPath' is used as the new key
- * for the wildcard element.
+ * Returns a MultikeyPaths which indicates which components of the index key pattern are multikey
+ * by looking up multikeyness in 'multikeyPathSet'. 'indexedPath' is used as the new key for the
+ * wildcard element.
  */
 MultikeyPaths buildMultiKeyPathsForExpandedWildcardIndexEntry(
     const FieldRef& indexedPath,
@@ -279,11 +304,13 @@ std::set<FieldRef> generateFieldNameOrArrayIndexPathSet(const MultikeyComponents
  */
 bool validateNumericPathComponents(const MultikeyPaths& multikeyPaths,
                                    const std::set<FieldRef>& includedPaths,
-                                   const FieldRef& queryPath) {
+                                   const FieldRef& queryPath,
+                                   const int indexOfWildcardField) {
     // Find the positions of all multikey path components in 'queryPath' that have a numerical path
     // component immediately after. For a queryPath of 'a.2.b' this will return position 0; that is,
     // 'a'. If no such multikey path was found, we are clear to proceed with planning.
-    const auto arrayIndices = findArrayIndexPathComponents(multikeyPaths.back(), queryPath);
+    const auto arrayIndices =
+        findArrayIndexPathComponents(multikeyPaths[indexOfWildcardField], queryPath);
     if (arrayIndices.empty()) {
         return true;
     }
@@ -364,9 +391,12 @@ boost::optional<IndexEntry> expandAndValidateIndexEntry(const IndexEntry& wildca
     auto multikeyPaths = buildMultiKeyPathsForExpandedWildcardIndexEntry(
         queryPath, wildcardIndex.multikeyPathSet, wildcardIndex.keyPattern);
 
+    int wildcardPos = getWildcardIndex(wildcardIndex.keyPattern);
+    invariant(wildcardPos >= 0);
+
     // Check whether a query on the current fieldpath is answerable by the $** index, given any
     // numerical path components that may be present in the path string.
-    if (!validateNumericPathComponents(multikeyPaths, includedPaths, queryPath)) {
+    if (!validateNumericPathComponents(multikeyPaths, includedPaths, queryPath, wildcardPos)) {
         return boost::none;
     }
 
@@ -377,7 +407,7 @@ boost::optional<IndexEntry> expandAndValidateIndexEntry(const IndexEntry& wildca
     // will be marked as multikey because "a" is multikey, whereas the "c.d" entry will not be
     // marked as multikey.
     invariant((int)multikeyPaths.size() == wildcardIndex.keyPattern.nFields());
-    const bool isMultikey = !multikeyPaths.back().empty();
+    const bool isMultikey = !multikeyPaths[wildcardPos].empty();
 
     IndexEntry entry(expandIndexKey(wildcardIndex.keyPattern, fieldName),
                      IndexType::INDEX_WILDCARD,
@@ -394,6 +424,7 @@ boost::optional<IndexEntry> expandAndValidateIndexEntry(const IndexEntry& wildca
                      wildcardIndex.infoObj,
                      wildcardIndex.collator,
                      wildcardIndex.wildcardProjection);
+    entry.wildcardFieldIndex = wildcardPos;
 
     invariant("$_path"_sd != fieldName);
     return entry;
@@ -450,7 +481,8 @@ void expandWildcardIndexEntry(const IndexEntry& wildcardIndex,
     invariant(wildcardIndex.type == INDEX_WILDCARD);
 
     // Should have a wilcard key in the index.
-    invariant(getLastElement(wildcardIndex.keyPattern)->fieldNameStringData().endsWith("$**"));
+    int wildcardPos = getWildcardIndex(wildcardIndex.keyPattern);
+    invariant(wildcardPos >= 0);
 
     // $** indexes do not keep the multikey metadata inside the index catalog entry, as the amount
     // of metadata is not bounded. We do not expect IndexEntry objects for $** indexes to have a
@@ -479,8 +511,8 @@ void expandWildcardIndexEntry(const IndexEntry& wildcardIndex,
         // compound index, so we may still be able to support the query. For example, with index
         // {a: 1, 'b.$**': 1} and query {a: {$eq: 5}}, the index does support the query. Replace the
         // '$**' part of the wildcard element with a placeholder name, then output the index entry.
-        auto wcElemFieldName = getLastElement(wildcardIndex.keyPattern)->fieldNameStringData();
-        auto placeholder = wcElemFieldName.substr(0, wcElemFieldName.size() - 3) + "$_value";
+        auto wcElemName = getElement(wildcardIndex.keyPattern, wildcardPos)->fieldNameStringData();
+        auto placeholder = wcElemName.substr(0, wcElemName.size() - 3) + "$_value";
         if (auto entry = expandAndValidateIndexEntry(wildcardIndex, placeholder, includedPaths)) {
             out->push_back(std::move(entry.get()));
         }
@@ -516,9 +548,9 @@ BoundsTightness translateWildcardIndexBoundsAndTightness(const IndexEntry& index
     // If the query passes through any array indices, we must always fetch and filter the documents.
     // Here we know that the last field in key pattern is the wildcard field-- after expansion, we
     // can no longer tell just from looking at the keys.
-    auto wcElem = getLastElement(index.keyPattern);
-    const auto arrayIndicesTraversedByQuery =
-        findArrayIndexPathComponents(index.multikeyPaths.back(), FieldRef{wcElem->fieldName()});
+    auto wcElem = getElement(index.keyPattern, index.wildcardFieldIndex);
+    const auto arrayIndicesTraversedByQuery = findArrayIndexPathComponents(
+        index.multikeyPaths[index.wildcardFieldIndex], FieldRef{wcElem->fieldName()});
 
     // If the list of array indices we traversed is non-empty, set the tightness to INEXACT_FETCH.
     return (arrayIndicesTraversedByQuery.empty() ? tightnessIn : BoundsTightness::INEXACT_FETCH);
@@ -532,27 +564,23 @@ void finalizeWildcardIndexScanConfiguration(IndexScanNode* scan) {
     invariant(index && index->type == IndexType::INDEX_WILDCARD);
     invariant(index->keyPattern.nFields() == (int)index->multikeyPaths.size());
     invariant(bounds && bounds->fields.size() == index->multikeyPaths.size());
-    invariant(bounds->fields.front().name == index->keyPattern.firstElementFieldName());
+    invariant(index->wildcardFieldIndex >= 0);
 
     // For $** indexes, the IndexEntry key pattern is {'path.to.field': ±1} but the actual keys in
     // the index are of the form {'$_path': ±1, 'path.to.field': ±1}, where the value of the first
-    // field in each key is 'path.to.field'. We push a new entry into the bounds vector for the
-    // leading '$_path' bound here. We also push corresponding fields into the IndexScanNode's
-    // keyPattern and its multikeyPaths vector. Note that these key patterns may be prefixed by
-    // other fields, representing a compound index. The last field is the wildcard element, so we
-    // add the $_path placeholders right before it.
-    index->multikeyPaths.insert(std::prev(index->multikeyPaths.end()), MultikeyComponents{});
-    bounds->fields.insert(std::prev(bounds->fields.end()), {"$_path"});
-    index->keyPattern = insertPathPlaceHolder(index->keyPattern);
+    // field in each key is 'path.to.field'. We add the $_path field to the necessary objects here.
+    insertPathPlaceHolder(index, bounds);
 
     // Create a FieldRef to perform any necessary manipulations on the query path string.
-    FieldRef queryPath{getLastElement(index->keyPattern)->fieldNameStringData()};
-    auto& multikeyPaths = index->multikeyPaths.back();
+    FieldRef queryPath{
+        getElement(index->keyPattern, index->wildcardFieldIndex)->fieldNameStringData()};
+    auto& multikeyPaths = index->multikeyPaths[index->wildcardFieldIndex];
 
     // If the bounds overlap the object type bracket, then we must retrieve all documents which
     // include the given path. We must therefore add bounds that encompass all its subpaths,
     // specifically the interval ["path.","path/") on "$_path".
-    const bool requiresSubpathBounds = boundsOverlapObjectTypeBracket(bounds->fields.back());
+    const bool requiresSubpathBounds =
+        boundsOverlapObjectTypeBracket(bounds->fields[index->wildcardFieldIndex]);
 
     // Account for fieldname-or-array-index semantics. $** indexes do not explicitly encode array
     // indices in their keys, so if this query traverses one or more multikey fields via an array
@@ -561,10 +589,16 @@ void finalizeWildcardIndexScanConfiguration(IndexScanNode* scan) {
     auto paths =
         generateFieldNameOrArrayIndexPathSet(multikeyPaths, queryPath, requiresSubpathBounds);
 
+    // Get a pointer to the newly inserted $_path placeholder.
+    auto fieldsItr = bounds->fields.begin();
+    for (int i = 0; i < (int)index->wildcardFieldIndex - 1; i++) {
+        fieldsItr = std::next(fieldsItr);
+    }
+
     // Add a $_path point-interval for each path that needs to be traversed in the index. If subpath
     // bounds are required, then we must add a further range interval on ["path.","path/").
     static const char subPathStart = '.', subPathEnd = static_cast<char>('.' + 1);
-    auto& pathIntervals = std::prev(std::prev(bounds->fields.end()))->intervals;
+    auto& pathIntervals = fieldsItr->intervals;
     for (const auto& fieldPath : paths) {
         auto path = fieldPath.dottedField().toString();
         pathIntervals.push_back(IndexBoundsBuilder::makePointInterval(path));
@@ -591,15 +625,15 @@ bool isWildcardObjectSubpathScan(const IndexScanNode* node) {
     invariant((int)node->index.multikeyPaths.size() == numFields);
     invariant((int)node->bounds.fields.size() == numFields);
 
-    // The last two elements of the vounds and keyPattern are the $_path placeholder followed by the
-    // wildcard element.
-    auto wcElem = getLastElement(node->index.keyPattern);
-    invariant(node->bounds.fields[numFields - 2].name ==
-              getElement(node->index.keyPattern, numFields - 2)->fieldName());
-    invariant(node->bounds.fields[numFields - 1].name == wcElem->fieldName());
+    // The last two elements of the bounds and keyPattern should the $_path placeholder followed by
+    // the wildcard element. Verify that the field names at these indexes match.
+    invariant(node->bounds.fields[node->index.wildcardFieldIndex - 1].name ==
+              getElement(node->index.keyPattern, node->index.wildcardFieldIndex - 1)->fieldName());
+    invariant(node->bounds.fields[node->index.wildcardFieldIndex].name ==
+              getElement(node->index.keyPattern, node->index.wildcardFieldIndex)->fieldName());
 
     // Check the bounds on the query field for any intersections with the object type bracket.
-    return boundsOverlapObjectTypeBracket(node->bounds.fields.back());
+    return boundsOverlapObjectTypeBracket(node->bounds.fields[node->index.wildcardFieldIndex]);
 }
 
 }  // namespace wildcard_planning
diff --git a/src/mongo/db/query/planner_wildcard_helpers_test.cpp b/src/mongo/db/query/planner_wildcard_helpers_test.cpp
index 96fa36b7bbc..37dd092d717 100644
--- a/src/mongo/db/query/planner_wildcard_helpers_test.cpp
+++ b/src/mongo/db/query/planner_wildcard_helpers_test.cpp
@@ -45,14 +45,6 @@ namespace mongo {
 
 using PlannerWildcardHelpersTest = AggregationContextFixture;
 
-auto getLastElement(const BSONObj& keyPattern) {
-    auto it = keyPattern.begin();
-    while (std::next(it) != keyPattern.end()) {
-        it++;
-    }
-    return it;
-}
-
 /**************** The following section can be moved to planner_ixselect_test.cpp ****************/
 /*
  * Will compare 'keyPatterns' with 'entries'. As part of comparing, it will sort both of them.
@@ -86,8 +78,10 @@ auto makeIndexEntry(BSONObj keyPattern,
                     MultikeyPaths multiKeyPaths,
                     std::set<FieldRef> multiKeyPathSet = {},
                     BSONObj infoObj = BSONObj()) {
-    auto wcElem = getLastElement(keyPattern);
-    auto wcProj = wcElem->fieldNameStringData().endsWith("$**"_sd)
+    auto wcElem = std::find_if(keyPattern.begin(), keyPattern.end(), [](auto&& elem) {
+        return elem.fieldNameStringData().endsWith("$**"_sd);
+    });
+    auto wcProj = wcElem != keyPattern.end() && wcElem->fieldNameStringData().endsWith("$**"_sd)
         ? std::make_unique<WildcardProjection>(WildcardKeyGenerator::createProjectionExecutor(
               keyPattern, infoObj.getObjectField("wildcardProjection")))
         : std::unique_ptr<WildcardProjection>(nullptr);
@@ -188,6 +182,24 @@ TEST_F(PlannerWildcardHelpersTest, ExpandEnsureMultikeySetForAllCompoundFieldsDo
     ASSERT_BSONOBJ_EQ(out[0].keyPattern, {fromjson("{'a.b': 1, 'c.d.e': 1}")});
 }
 
+TEST_F(PlannerWildcardHelpersTest, ExpandEnsureMultikeySetForAllCompoundFieldsWithFlippedKeyOrder) {
+    std::vector<IndexEntry> out;
+    stdx::unordered_set<std::string> fields{"a.b", "c.d.e"};
+    const auto indexEntry = makeIndexEntry(
+        BSON("$**" << 1 << "a.b" << 1),
+        {},
+        {FieldRef("a"), FieldRef("a.b"), FieldRef("b"), FieldRef("c"), FieldRef("c.d.e")},
+        {fromjson("{wildcardProjection: {a: 0}}")});
+    wildcard_planning::expandWildcardIndexEntry(indexEntry.first, fields, &out);
+
+    ASSERT_EQ(out.size(), 1u);
+    ASSERT_TRUE(out[0].multikey);
+    ASSERT_EQ(out[0].multikeyPaths.size(), 2);
+    ASSERT((out[0].multikeyPaths[0] == MultikeyComponents{0u, 2u}));  // c and c.d.e are multikey
+    ASSERT((out[0].multikeyPaths[1] == MultikeyComponents{0u, 1u}));  // a and a.b are multikey
+    ASSERT_BSONOBJ_EQ(out[0].keyPattern, {fromjson("{'c.d.e': 1, 'a.b': 1}")});
+}
+
 /*************************************** end section ***************************************/
 
 // translateWildcardIndexBoundsAndTightness
@@ -216,6 +228,31 @@ TEST_F(PlannerWildcardHelpersTest, TranslateBoundsWithWildcard) {
     ASSERT(tightness == IndexBoundsBuilder::EXACT);
 }
 
+TEST_F(PlannerWildcardHelpersTest, TranslateBoundsWithWildcardFlippedIndexKeys) {
+    // expand first
+    std::vector<IndexEntry> out;
+    stdx::unordered_set<std::string> fields{"a", "b"};
+    const auto indexEntry = makeIndexEntry(
+        BSON("$**" << 1 << "a" << 1), {}, {}, {fromjson("{wildcardProjection: {a: 0}}")});
+    wildcard_planning::expandWildcardIndexEntry(indexEntry.first, fields, &out);
+
+    // This expression can only be over one field. WTS that given a query on field b and a compound
+    // index on a wildcard including b (followed by another field) that we translate properly.
+    BSONObj obj = fromjson("{b: {$lte: 1}}");
+    auto expr = parseMatchExpression(obj);
+    BSONElement elt = obj.firstElement();
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, out[0], &oil, &tightness);
+    ASSERT_EQUALS(oil.name, "b");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': -Infinity, '': 1}"), true, true)));
+    ASSERT(tightness == IndexBoundsBuilder::EXACT);
+}
+
+
 // How to test?
 // finalizeWildcardIndexScanConfiguration(IndexScanNode* scan);
 // isWildcardObjectSubpathScan(const IndexScanNode* node);
@@ -406,4 +443,96 @@ TEST_F(QueryPlannerWildcardTest,
         "bounds: {'x': [[2, 2, true, true]], '$_path': [['a.b','a.b',true,true]], 'a.b': "
         "[[-Infinity,9,true,false]]}}}}}");
 }
+
+
+// The following tests create compound wildcard indexes where the wildcard component is not last.
+
+TEST_F(QueryPlannerWildcardTest,
+       CompoundWildcardIndexQueryOnlyOnNonWCFieldWithProjectionFlippedOrder) {
+    addWildcardIndex(fromjson("{'$**': 1, a: 1}"), {}, fromjson("{a: 0}"));
+
+    runQuery(fromjson("{c: {$eq: 5}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'$_path': 1, 'c': 1, a: 1}, bounds: {'$_path': "
+        "[['c', 'c', true, true]], 'c': [[5, 5, true, true]],"
+        "'a': [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerWildcardTest, CompoundWildcardIndexQueryWCFieldInMiddleOfKey) {
+    addWildcardIndex(fromjson("{a: 1, 'b.$**': 1, x: 1}"), {});
+
+    runQuery(fromjson("{a: {$eq: 5}}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, '$_path': 1, 'b.$_value': 1, x: 1}, bounds: {'a':"
+        "[[5, 5, true, true]], '$_path': [['b.$_value', 'b.$_value', true, true]], 'b.$_value': "
+        "[['MinKey', 'MaxKey', true, true]], 'x': [['MinKey', 'MaxKey', true, true]]}}}}}");
+
+    runQuery(fromjson("{a: {$eq: 5}, 'b.c': {$lt: 2}}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, '$_path': 1, 'b.c': 1, x: 1}, bounds: {'a':"
+        "[[5, 5, true, true]], '$_path': [['b.c', 'b.c', true, true]], 'b.c': "
+        "[[-Infinity, 2, true, false]], 'x': [['MinKey', 'MaxKey', true, true]]}}}}}");
+
+    runQuery(fromjson("{a: {$eq: 5}, 'b.c': {$lt: 2}, 'x': {$eq: 4}}"));
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, '$_path': 1, 'b.c': 1, x: 1}, bounds: {'a':"
+        "[[5, 5, true, true]], '$_path': [['b.c', 'b.c', true, true]], 'b.c': "
+        "[[-Infinity, 2, true, false]], 'x': [[4, 4, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerWildcardTest, CompoundWildcardIndexBasicWithFlippedIndexKeys) {
+    addWildcardIndex(fromjson("{'$**': 1, a: 1}"), {}, fromjson("{a: 0}"));
+
+    runQuery(fromjson("{x: {$lt: 3}, a: {$eq: 5}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {$_path: 1, x: 1, a: 1}, bounds: {'$_path': "
+        "[['x', 'x', true, true]], 'x': [[-Infinity, 3, true, false]],"
+        "'a': [[5, 5, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerWildcardTest, CompoundWildcardIndexIsNotUsedWhenQueryNotOnPrefixFlippedKeys) {
+    addWildcardIndex(fromjson("{'$**': 1, a: 1}"), {}, fromjson("{a: 0}"));
+
+    runQuery(fromjson("{a: {$lt: 3}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists("{cscan: {dir: 1}}");
+}
+
+TEST_F(QueryPlannerWildcardTest, CompoundWildcardWithMultikeyFieldFlippedKeys) {
+    addWildcardIndex(
+        fromjson("{'$**': 1, a: 1}"), {"b"} /* 'b' marked as multikey field */, fromjson("{a: 0}"));
+    runQuery(fromjson("{b: {$gt: 0}, a: {$eq: 5}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {$_path: 1, b: 1, a: 1}, bounds: {'$_path': "
+        "[['b','b',true,true]], b: [[0,Infinity,false,true]], "
+        "'a': [[5, 5, true, true]]}}}}}}");
+}
+
+TEST_F(QueryPlannerWildcardTest,
+       CompoundWildcardMultiplePredicatesOverNestedFieldWithFirstComponentMultikeyFlippedKeys) {
+    addWildcardIndex(fromjson("{'$**': 1, x: 1}"), {"a"}, fromjson("{x: 0}"));
+    runQuery(fromjson("{'a.b': {$gt: 0, $lt: 9}, x: {$lt: 2}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{fetch: {filter: {'a.b': {$gt: 0}}, node: "
+        "{ixscan: {filter: null, pattern: {'$_path': 1, 'a.b': 1, 'x': 1},"
+        "bounds: {'$_path': [['a.b','a.b',true,true]], 'a.b': [[-Infinity,9,true,false]],"
+        "'x': [[-Infinity, 2, true, false]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {'a.b': {$lt: 9}}, node: "
+        "{ixscan: {filter: null, pattern: {'$_path': 1, 'a.b': 1, 'x': 1},"
+        "bounds: {'$_path': [['a.b','a.b',true,true]], 'a.b': [[0,Infinity,false,true]],"
+        "'x': [[-Infinity, 2, true, false]]}}}}}");
+}
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index c5eac153799..45582afd2cc 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -769,21 +769,13 @@ ProvidedSortSet computeSortsForScan(const IndexEntry& index,
         // 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. The '$_path' field must be the second to last field in bounds.
-        if (bounds.fields[bounds.fields.size() - 2].intervals.size() != 1u) {
+        // object are in bounds. The '$_path' field must be immediately before the wildcard field.
+        if (bounds.fields[index.wildcardFieldIndex - 1].intervals.size() != 1u) {
             return {};
         }
 
         // Strip '$_path' out of 'sortPattern' and then proceed with regular sort analysis.
-        BSONObjIterator it{sortPatternProvidedByIndex};
-        while (it.more()) {
-            auto pathElement = it.next();
-            if (pathElement.fieldNameStringData() == "$_path"_sd) {
-                invariant(it.more());
-                it.next();
-                invariant(!it.more());
-            }
-        }
+        invariant(sortPatternProvidedByIndex.hasField("$_path"));
         sortPatternProvidedByIndex = sortPatternProvidedByIndex.removeField("$_path"_sd);
     }