SERVER-27904 Extend support for moving predicates into contained ORs to multikey indexes

8 files changed, 948 insertions, 313 deletions

diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 50bacf795b4..4ef22584133 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -33,6 +33,7 @@
 #include "mongo/db/query/canonical_query.h"
 
 #include "mongo/db/jsobj.h"
+#include "mongo/db/matcher/expression_array.h"
 #include "mongo/db/namespace_string.h"
 #include "mongo/db/operation_context.h"
 #include "mongo/db/query/collation/collator_factory_interface.h"
@@ -335,6 +336,13 @@ MatchExpression* CanonicalQuery::normalizeTree(MatchExpression* root) {
         // normalizeTree(...) takes ownership of 'child', and then
         // transfers ownership of its return value to 'nme'.
         nme->resetChild(normalizeTree(child));
+    } else if (MatchExpression::ELEM_MATCH_OBJECT == root->matchType()) {
+        // Normalize the rest of the tree hanging off this ELEM_MATCH_OBJECT node.
+        ElemMatchObjectMatchExpression* emome = static_cast<ElemMatchObjectMatchExpression*>(root);
+        auto child = emome->releaseChild();
+        // normalizeTree(...) takes ownership of 'child', and then
+        // transfers ownership of its return value to 'emome'.
+        emome->resetChild(std::unique_ptr<MatchExpression>(normalizeTree(child.release())));
     } else if (MatchExpression::ELEM_MATCH_VALUE == root->matchType()) {
         // Just normalize our children.
         for (size_t i = 0; i < root->getChildVector()->size(); ++i) {
diff --git a/src/mongo/db/query/canonical_query_test.cpp b/src/mongo/db/query/canonical_query_test.cpp
index c7a1f2a05a2..292425167f7 100644
--- a/src/mongo/db/query/canonical_query_test.cpp
+++ b/src/mongo/db/query/canonical_query_test.cpp
@@ -521,6 +521,8 @@ TEST(CanonicalQueryTest, NormalizeQueryTree) {
     // $in with 0 or more than 1 argument is not modified.
     testNormalizeQuery("{a: {$in: []}}", "{a: {$in: []}}");
     testNormalizeQuery("{a: {$in: [/./, 3]}}", "{a: {$in: [/./, 3]}}");
+    // Child of $elemMatch object expression is normalized.
+    testNormalizeQuery("{a: {$elemMatch: {$or: [{b: 1}]}}}", "{a: {$elemMatch: {b: 1}}}");
 }
 
 TEST(CanonicalQueryTest, NormalizeWithInPreservesTags) {
diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp
index fd77c971357..752afe99fa2 100644
--- a/src/mongo/db/query/plan_cache_test.cpp
+++ b/src/mongo/db/query/plan_cache_test.cpp
@@ -1292,6 +1292,29 @@ TEST_F(CachePlanSelectionTest, ContainedOr) {
         "]}}}}");
 }
 
+TEST_F(CachePlanSelectionTest, ContainedOrAndIntersection) {
+    bool oldEnableHashIntersection = internalQueryPlannerEnableHashIntersection.load();
+    ON_BLOCK_EXIT([oldEnableHashIntersection] {
+        internalQueryPlannerEnableHashIntersection.store(oldEnableHashIntersection);
+    });
+    internalQueryPlannerEnableHashIntersection.store(true);
+    params.options = QueryPlannerParams::INCLUDE_COLLSCAN | QueryPlannerParams::INDEX_INTERSECTION;
+    addIndex(BSON("a" << 1 << "b" << 1), "a_1_b_1");
+    addIndex(BSON("c" << 1), "c_1");
+    BSONObj query = fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}");
+    runQuery(query);
+    assertPlanCacheRecoversSolution(
+        query,
+        "{fetch: {filter: null, node: {andHash: {nodes: ["
+        "{or: {nodes: ["
+        "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [[6, 6, true, "
+        "true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}]}},"
+        "{ixscan: {pattern: {a: 1, b: 1}, bounds: {a: [[5, 5, true, true]], b: [['MinKey', "
+        "'MaxKey', true, true]]}}}"
+        "]}}}}");
+}
+
 /**
  * Test functions for computeKey.  Cache keys are intentionally obfuscated and are
  * meaningful only within the current lifetime of the server process. Users should treat plan
diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index 66c79e266c1..e85214cbaf5 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -288,20 +288,7 @@ std::string PlanEnumerator::dumpMemo() {
 }
 
 string PlanEnumerator::NodeAssignment::toString() const {
-    if (NULL != pred) {
-        mongoutils::str::stream ss;
-        ss << "predicate\n";
-        ss << "\tfirst indices: [";
-        for (size_t i = 0; i < pred->indexes.size(); ++i) {
-            ss << pred->indexes[i];
-            if (i < pred->indexes.size() - 1)
-                ss << ", ";
-        }
-        ss << "]\n";
-        ss << "\tpred: " << pred->expr->toString();
-        ss << "\tindexToAssign: " << pred->indexToAssign;
-        return ss;
-    } else if (NULL != andAssignment) {
+    if (NULL != andAssignment) {
         mongoutils::str::stream ss;
         ss << "AND enumstate counter " << andAssignment->counter;
         for (size_t i = 0; i < andAssignment->choices.size(); ++i) {
@@ -396,69 +383,7 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) {
     childContext.elemMatchExpr = context.elemMatchExpr;
     childContext.outsidePreds = context.outsidePreds;
 
-    if (Indexability::nodeCanUseIndexOnOwnField(node)) {
-        // We only get here if our parent is an OR, an array operator, or we're the root.
-
-        // If we have no index tag there are no indices we can use.
-        if (NULL == node->getTag()) {
-            return false;
-        }
-
-        RelevantTag* rt = static_cast<RelevantTag*>(node->getTag());
-
-        size_t myMemoID;
-        NodeAssignment* assign;
-        allocateAssignment(node, &assign, &myMemoID);
-
-        assign->pred.reset(new PredicateAssignment());
-        assign->pred->expr = node;
-
-        // 'expr' can use any index in 'first'.
-        if (!rt->first.empty()) {
-            assign->pred->indexes.swap(rt->first);
-
-            for (auto index : assign->pred->indexes) {
-                assign->pred->positions.push_back(0);
-                assign->pred->orPushdowns.push_back(
-                    getOrPushdowns(index, childContext.outsidePreds));
-            }
-        }
-
-        // 'expr' can use an index in 'notFirst' if an outside predicate can be combined with this
-        // node and use the first position in the index.
-        for (auto index : rt->notFirst) {
-            auto orPushdowns = getOrPushdowns(index, childContext.outsidePreds);
-            for (const auto& orPushdown : orPushdowns) {
-                IndexTag* indexTag = static_cast<IndexTag*>(orPushdown.second.tagData.get());
-                if (indexTag->pos == 0) {
-                    const auto indexEntry = (*_indices)[index];
-                    assign->pred->indexes.push_back(index);
-                    assign->pred->positions.push_back(getPosition(indexEntry, rt->path));
-                    assign->pred->orPushdowns.push_back(std::move(orPushdowns));
-                    break;
-                }
-            }
-        }
-
-        return !assign->pred->indexes.empty();
-    } else if (Indexability::isBoundsGeneratingNot(node)) {
-        bool childIndexable = prepMemo(node->getChild(0), childContext);
-        // If the child isn't indexable then bail out now.
-        if (!childIndexable) {
-            return false;
-        }
-
-        // Our parent node, if any exists, will expect a memo entry keyed on 'node'.  As such we
-        // have the node ID for 'node' just point to the memo created for the child that
-        // actually generates the bounds.
-        size_t myMemoID;
-        NodeAssignment* assign;
-        allocateAssignment(node, &assign, &myMemoID);
-        OrAssignment* orAssignment = new OrAssignment();
-        orAssignment->subnodes.push_back(memoIDForNode(node->getChild(0)));
-        assign->orAssignment.reset(orAssignment);
-        return true;
-    } else if (MatchExpression::OR == node->matchType()) {
+    if (MatchExpression::OR == node->matchType()) {
         // For an OR to be indexed, all its children must be indexed.
         for (size_t i = 0; i < node->numChildren(); ++i) {
 
@@ -510,7 +435,9 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) {
 
         assign->arrayAssignment.reset(aa.release());
         return true;
-    } else if (MatchExpression::AND == node->matchType()) {
+    } else if (Indexability::nodeCanUseIndexOnOwnField(node) ||
+               Indexability::isBoundsGeneratingNot(node) ||
+               (MatchExpression::AND == node->matchType())) {
         // Map from idx id to children that have a pred over it.
 
         // TODO: The index intersection logic could be simplified if we could iterate over these
@@ -701,12 +628,16 @@ bool PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
                 if (compIt != idxToNotFirst.end()) {
                     // Assign any predicates on the non-leading index fields to 'indexAssign' that
                     // don't violate the intersecting or compounding rules for multikey indexes.
-                    assignMultikeySafePredicates(compIt->second, &indexAssign);
+                    // We do not currently try to assign outside predicates to mandatory indexes.
+                    const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds{};
+                    assignMultikeySafePredicates(compIt->second, outsidePreds, &indexAssign);
                 }
             } else {
                 // Assign any predicates on the leading index field to 'indexAssign' that don't
                 // violate the intersecting rules for multikey indexes.
-                assignMultikeySafePredicates(predsOverLeadingField, &indexAssign);
+                // We do not currently try to assign outside predicates to mandatory indexes.
+                const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds{};
+                assignMultikeySafePredicates(predsOverLeadingField, outsidePreds, &indexAssign);
 
                 // Assign the mandatory predicate to 'thisIndex'. Due to how keys are generated for
                 // 2dsphere indexes, it is always safe to assign a predicate on a distinct path to
@@ -730,7 +661,9 @@ bool PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
 
                     // Assign any predicates on the non-leading index fields to 'indexAssign' that
                     // don't violate the intersecting or compounding rules for multikey indexes.
-                    assignMultikeySafePredicates(predsOverNonLeadingFields, &indexAssign);
+                    // We do not currently try to assign outside predicates to mandatory indexes.
+                    assignMultikeySafePredicates(
+                        predsOverNonLeadingFields, outsidePreds, &indexAssign);
                 }
             }
         } else if (thisIndex.multikey) {
@@ -812,75 +745,45 @@ bool PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
 
         // Output the assignments for this index.
         AndEnumerableState state;
-        state.assignments.push_back(indexAssign);
+        state.assignments.push_back(std::move(indexAssign));
         andAssignment->choices.push_back(std::move(state));
     }
 
     return andAssignment->choices.size() > 0;
 }
 
-std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> PlanEnumerator::getOrPushdowns(
-    IndexID index, const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds) {
-    std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> orPushdowns;
-    const auto indexEntry = (*_indices)[index];
-
-    // TODO SERVER-27904: Determine whether we can combine bounds.
-    if (indexEntry.multikey) {
-        return orPushdowns;
-    }
+void PlanEnumerator::assignPredicate(
+    const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+    MatchExpression* pred,
+    size_t position,
+    OneIndexAssignment* indexAssignment) {
+    if (outsidePreds.find(pred) != outsidePreds.end()) {
+        OrPushdownTag::Destination dest;
+        dest.route = outsidePreds.at(pred);
 
-    for (const auto& pred : outsidePreds) {
-        RelevantTag* relevantTag = static_cast<RelevantTag*>(pred.first->getTag());
-        const auto& first = relevantTag->first;
-        const auto& notFirst = relevantTag->notFirst;
-        if ((std::find(first.begin(), first.end(), index) != first.end()) ||
-            (std::find(notFirst.begin(), notFirst.end(), index) != notFirst.end())) {
-            OrPushdownTag::Destination dest;
-            dest.route = pred.second;
-
-            // The index is not multikey, so we can combine bounds.
-            const bool canCombineBounds = true;
-
-            dest.tagData = stdx::make_unique<IndexTag>(
-                index, getPosition(indexEntry, relevantTag->path), canCombineBounds);
-            orPushdowns.emplace_back(pred.first, std::move(dest));
-        }
+        // This method should only be called if we can combine bounds.
+        const bool canCombineBounds = true;
+        dest.tagData =
+            stdx::make_unique<IndexTag>(indexAssignment->index, position, canCombineBounds);
+        indexAssignment->orPushdowns.emplace_back(pred, std::move(dest));
+    } else {
+        indexAssignment->preds.push_back(pred);
+        indexAssignment->positions.push_back(position);
     }
-    return orPushdowns;
 }
 
 void PlanEnumerator::enumerateOneIndex(
-    const IndexToPredMap& idxToFirst,
-    const IndexToPredMap& idxToNotFirst,
+    IndexToPredMap idxToFirst,
+    IndexToPredMap idxToNotFirst,
     const vector<MemoID>& subnodes,
-    const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds,
+    const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
     AndAssignment* andAssignment) {
-    // In the simplest case, an AndAssignment picks indices like a PredicateAssignment.  To
-    // be indexed we must only pick one index
-    //
-    // Complications:
-    //
-    // Some of our child predicates cannot be answered without an index.  As such, the
-    // indices that those predicates require must always be outputted.  We store these
-    // mandatory index assignments in 'mandatoryIndices'.
-    //
-    // Some of our children may not be predicates.  We may have ORs (or array operators) as
-    // children.  If one of these subtrees provides an index, the AND is indexed.  We store
-    // these subtree choices in 'subnodes'.
-    //
-    // With the above two cases out of the way, we can focus on the remaining case: what to
-    // do with our children that are leaf predicates.
-    //
-    // Guiding principles for index assignment to leaf predicates:
-    //
-    // 1. If we assign an index to {x:{$gt: 5}} we should assign the same index to
-    //    {x:{$lt: 50}}.  That is, an index assignment should include all predicates
-    //    over its leading field.
-    //
-    // 2. If we have the index {a:1, b:1} and we assign it to {a: 5} we should assign it
-    //    to {b:7}, since with a predicate over the first field of the compound index,
-    //    the second field can be bounded as well.  We may only assign indices to predicates
-    //    if all fields to the left of the index field are constrained.
+    // Each choice in the 'andAssignment' will consist of a single subnode to index (an OR or array
+    // operator) or a OneIndexAssignment. When creating a OneIndexAssignment, we ensure that at
+    // least one predicate can fulfill the first position in the key pattern, then we assign all
+    // predicates that can use the key pattern to the index. However, if the index is multikey,
+    // certain predicates cannot be combined/compounded. We determine which predicates can be
+    // combined/compounded using path-level multikey info, if available.
 
     // First, add the state of using each subnode.
     for (size_t i = 0; i < subnodes.size(); ++i) {
@@ -889,7 +792,31 @@ void PlanEnumerator::enumerateOneIndex(
         andAssignment->choices.push_back(std::move(aes));
     }
 
-    // For each FIRST, we assign nodes to it.
+    // Next we create OneIndexAssignments.
+
+    // If there are any 'outsidePreds', then we are in a contained OR, and the 'outsidePreds' are
+    // AND-related to the contained OR and can be pushed inside of it. Add all of the 'outsidePreds'
+    // to 'idxToFirst' and 'idxToNotFirst'. We will treat them as normal predicates that can be
+    // assigned to the index, but we will ensure that any OneIndexAssignment contains some
+    // predicates from the current node.
+    for (const auto& pred : outsidePreds) {
+        invariant(pred.first->getTag());
+        RelevantTag* relevantTag = static_cast<RelevantTag*>(pred.first->getTag());
+        for (auto index : relevantTag->first) {
+            if (idxToFirst.find(index) != idxToFirst.end() ||
+                idxToNotFirst.find(index) != idxToNotFirst.end()) {
+                idxToFirst[index].push_back(pred.first);
+            }
+        }
+        for (auto index : relevantTag->notFirst) {
+            if (idxToFirst.find(index) != idxToFirst.end() ||
+                idxToNotFirst.find(index) != idxToNotFirst.end()) {
+                idxToNotFirst[index].push_back(pred.first);
+            }
+        }
+    }
+
+    // For each FIRST, we assign predicates to it.
     for (IndexToPredMap::const_iterator it = idxToFirst.begin(); it != idxToFirst.end(); ++it) {
         const IndexEntry& thisIndex = (*_indices)[it->first];
 
@@ -909,20 +836,24 @@ void PlanEnumerator::enumerateOneIndex(
             for (const auto& firstAssignment : possibleFirstAssignments) {
                 OneIndexAssignment indexAssign;
                 indexAssign.index = it->first;
-                indexAssign.preds = firstAssignment;
-                indexAssign.positions.resize(indexAssign.preds.size(), 0);
+
+                for (auto pred : firstAssignment) {
+                    assignPredicate(outsidePreds, pred, 0, &indexAssign);
+                }
 
                 auto compIt = idxToNotFirst.find(indexAssign.index);
                 if (compIt != idxToNotFirst.end()) {
                     // Assign any predicates on the non-leading index fields to 'indexAssign' that
                     // don't violate the intersecting and compounding rules for multikey indexes.
-                    assignMultikeySafePredicates(compIt->second, &indexAssign);
+                    assignMultikeySafePredicates(compIt->second, outsidePreds, &indexAssign);
                 }
 
-                AndEnumerableState state;
-                state.assignments.push_back(indexAssign);
-                // TODO SERVER-27904: Use outsidePreds to get orPushdowns.
-                andAssignment->choices.push_back(std::move(state));
+                // Do not output this assignment if it consists only of outside predicates.
+                if (!indexAssign.preds.empty()) {
+                    AndEnumerableState state;
+                    state.assignments.push_back(std::move(indexAssign));
+                    andAssignment->choices.push_back(std::move(state));
+                }
             }
         } else if (thisIndex.multikey) {
             // We don't have path-level information about what causes 'thisIndex' to be multikey.
@@ -934,29 +865,34 @@ void PlanEnumerator::enumerateOneIndex(
                 OneIndexAssignment indexAssign;
                 indexAssign.index = it->first;
 
-                indexAssign.preds.push_back(pred);
-                indexAssign.positions.push_back(0);
+                assignPredicate(outsidePreds, pred, 0, &indexAssign);
 
                 // If there are any preds that could possibly be compounded with this
                 // index...
                 IndexToPredMap::const_iterator compIt = idxToNotFirst.find(indexAssign.index);
                 if (compIt != idxToNotFirst.end()) {
                     const vector<MatchExpression*>& couldCompound = compIt->second;
-                    vector<MatchExpression*> tryCompound;
+                    vector<MatchExpression*> toCompound;
+                    vector<MatchExpression*> assigned = indexAssign.preds;
+                    for (const auto& orPushdown : indexAssign.orPushdowns) {
+                        assigned.push_back(orPushdown.first);
+                    }
+
+                    // ...select the predicates that are safe to compound and compound them.
+                    getMultikeyCompoundablePreds(assigned, couldCompound, &toCompound);
 
-                    // ...select the predicates that are safe to compound and try to
-                    // compound them.
-                    getMultikeyCompoundablePreds(indexAssign.preds, couldCompound, &tryCompound);
-                    if (tryCompound.size()) {
-                        compound(tryCompound, thisIndex, &indexAssign);
+                    for (auto pred : toCompound) {
+                        assignPredicate(
+                            outsidePreds, pred, getPosition(thisIndex, pred), &indexAssign);
                     }
                 }
 
-                // Output the assignment.
-                AndEnumerableState state;
-                state.assignments.push_back(indexAssign);
-                // TODO SERVER-27904: Use outsidePreds to get orPushdowns.
-                andAssignment->choices.push_back(std::move(state));
+                // Do not output this assignment if it consists only of outside predicates.
+                if (!indexAssign.preds.empty()) {
+                    AndEnumerableState state;
+                    state.assignments.push_back(std::move(indexAssign));
+                    andAssignment->choices.push_back(std::move(state));
+                }
             }
         } else {
             // The assignment we're filling out.
@@ -967,48 +903,26 @@ void PlanEnumerator::enumerateOneIndex(
 
             // The index isn't multikey.  Assign all preds to it.  The planner will
             // intersect the bounds.
-            indexAssign.preds = it->second;
-
-            // Since everything in assign.preds prefixes the index, they all go
-            // at position '0' in the index, the first position.
-            indexAssign.positions.resize(indexAssign.preds.size(), 0);
+            for (auto pred : it->second) {
+                assignPredicate(outsidePreds, pred, 0, &indexAssign);
+            }
 
             // Find everything that could use assign.index but isn't a pred over
             // the first field of that index.
             IndexToPredMap::const_iterator compIt = idxToNotFirst.find(indexAssign.index);
             if (compIt != idxToNotFirst.end()) {
-                compound(compIt->second, thisIndex, &indexAssign);
+                for (auto pred : compIt->second) {
+                    assignPredicate(outsidePreds, pred, getPosition(thisIndex, pred), &indexAssign);
+                }
             }
 
             // Output the assignment.
+            invariant(!indexAssign.preds.empty());
             AndEnumerableState state;
-            state.assignments.push_back(indexAssign);
-            state.orPushdowns = getOrPushdowns(indexAssign.index, outsidePreds);
+            state.assignments.push_back(std::move(indexAssign));
             andAssignment->choices.push_back(std::move(state));
         }
     }
-
-    // If an outside predicate can fulfill the first position in the index, we can use it.
-    for (const auto& index : idxToNotFirst) {
-        if (idxToFirst.find(index.first) != idxToFirst.end()) {
-            continue;
-        }
-        auto orPushdowns = getOrPushdowns(index.first, outsidePreds);
-        for (const auto& orPushdown : orPushdowns) {
-            IndexTag* indexTag = static_cast<IndexTag*>(orPushdown.second.tagData.get());
-            if (indexTag->pos == 0) {
-                OneIndexAssignment indexAssign;
-                indexAssign.index = index.first;
-                const IndexEntry& indexEntry = (*_indices)[index.first];
-                compound(index.second, indexEntry, &indexAssign);
-                AndEnumerableState state;
-                state.assignments.push_back(indexAssign);
-                state.orPushdowns = std::move(orPushdowns);
-                andAssignment->choices.push_back(std::move(state));
-                break;
-            }
-        }
-    }
 }
 
 void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
@@ -1077,7 +991,7 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
                 oneAssign.positions.resize(kMaxSelfIntersections);
             }
             AndEnumerableState state;
-            state.assignments.push_back(oneAssign);
+            state.assignments.push_back(std::move(oneAssign));
             andAssignment->choices.push_back(std::move(state));
             continue;
         }
@@ -1085,7 +999,7 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
         // Output (subnode, firstAssign) pairs.
         for (size_t i = 0; i < subnodes.size(); ++i) {
             AndEnumerableState indexAndSubnode;
-            indexAndSubnode.assignments.push_back(oneAssign);
+            indexAndSubnode.assignments.push_back(std::move(oneAssign));
             indexAndSubnode.subnodesToIndex.push_back(subnodes[i]);
             andAssignment->choices.push_back(std::move(indexAndSubnode));
             // Limit n^2.
@@ -1252,8 +1166,8 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
             // We're done with this particular pair of indices; output
             // the resulting assignments.
             AndEnumerableState state;
-            state.assignments.push_back(firstAssign);
-            state.assignments.push_back(secondAssign);
+            state.assignments.push_back(std::move(firstAssign));
+            state.assignments.push_back(std::move(secondAssign));
             andAssignment->choices.push_back(std::move(state));
         }
     }
@@ -1278,32 +1192,33 @@ void PlanEnumerator::enumerateAndIntersect(const IndexToPredMap& idxToFirst,
 void PlanEnumerator::getIndexedPreds(MatchExpression* node,
                                      PrepMemoContext context,
                                      vector<MatchExpression*>* indexedPreds) {
-    for (size_t i = 0; i < node->numChildren(); ++i) {
-        MatchExpression* child = node->getChild(i);
-        if (Indexability::nodeCanUseIndexOnOwnField(child)) {
-            RelevantTag* rt = static_cast<RelevantTag*>(child->getTag());
-            if (context.elemMatchExpr) {
-                // If we're in an $elemMatch context, store the
-                // innermost parent $elemMatch, as well as the
-                // inner path prefix.
-                rt->elemMatchExpr = context.elemMatchExpr;
-                rt->pathPrefix = getPathPrefix(child->path().toString());
-            } else {
-                // We're not an $elemMatch context, so we should store
-                // the prefix of the full path.
-                rt->pathPrefix = getPathPrefix(rt->path);
-            }
+    if (Indexability::nodeCanUseIndexOnOwnField(node)) {
+        RelevantTag* rt = static_cast<RelevantTag*>(node->getTag());
+        if (context.elemMatchExpr) {
+            // If we're in an $elemMatch context, store the
+            // innermost parent $elemMatch, as well as the
+            // inner path prefix.
+            rt->elemMatchExpr = context.elemMatchExpr;
+            rt->pathPrefix = getPathPrefix(node->path().toString());
+        } else {
+            // We're not an $elemMatch context, so we should store
+            // the prefix of the full path.
+            rt->pathPrefix = getPathPrefix(rt->path);
+        }
 
-            // Output this as a pred that can use the index.
-            indexedPreds->push_back(child);
-        } else if (Indexability::isBoundsGeneratingNot(child)) {
-            getIndexedPreds(child, context, indexedPreds);
-        } else if (MatchExpression::ELEM_MATCH_OBJECT == child->matchType()) {
-            PrepMemoContext childContext;
-            childContext.elemMatchExpr = child;
-            getIndexedPreds(child, childContext, indexedPreds);
-        } else if (MatchExpression::AND == child->matchType()) {
-            getIndexedPreds(child, context, indexedPreds);
+        // Output this as a pred that can use the index.
+        indexedPreds->push_back(node);
+    } else if (Indexability::isBoundsGeneratingNot(node)) {
+        getIndexedPreds(node->getChild(0), context, indexedPreds);
+    } else if (MatchExpression::ELEM_MATCH_OBJECT == node->matchType()) {
+        PrepMemoContext childContext;
+        childContext.elemMatchExpr = node;
+        for (size_t i = 0; i < node->numChildren(); ++i) {
+            getIndexedPreds(node->getChild(i), childContext, indexedPreds);
+        }
+    } else if (MatchExpression::AND == node->matchType()) {
+        for (size_t i = 0; i < node->numChildren(); ++i) {
+            getIndexedPreds(node->getChild(i), context, indexedPreds);
         }
     }
 }
@@ -1422,8 +1337,10 @@ void PlanEnumerator::getMultikeyCompoundablePreds(const vector<MatchExpression*>
     }
 }
 
-void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpression*>& couldAssign,
-                                                  OneIndexAssignment* indexAssignment) {
+void PlanEnumerator::assignMultikeySafePredicates(
+    const std::vector<MatchExpression*>& couldAssign,
+    const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+    OneIndexAssignment* indexAssignment) {
     invariant(indexAssignment);
     invariant(indexAssignment->preds.size() == indexAssignment->positions.size());
 
@@ -1458,6 +1375,19 @@ void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpress
         }
     }
 
+    // Update 'used' with all outside predicates already assigned to 'thisIndex';
+    for (const auto& orPushdown : indexAssignment->orPushdowns) {
+        invariant(orPushdown.first->getTag());
+        RelevantTag* rt = static_cast<RelevantTag*>(orPushdown.first->getTag());
+
+        // Any outside predicates already assigned to 'thisIndex' were assigned in the first
+        // position.
+        const size_t position = 0;
+        const bool shouldHaveAssigned =
+            canAssignPredToIndex(rt, thisIndex.multikeyPaths[position], &used);
+        invariant(shouldHaveAssigned);
+    }
+
     size_t posInIdx = 0;
 
     for (const auto keyElem : thisIndex.keyPattern) {
@@ -1474,8 +1404,7 @@ void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpress
             if (thisIndex.multikeyPaths[posInIdx].empty()) {
                 // We can always intersect or compound the bounds when no prefix of the queried path
                 // causes the index to be multikey.
-                indexAssignment->preds.push_back(couldAssignPred);
-                indexAssignment->positions.push_back(posInIdx);
+                assignPredicate(outsidePreds, couldAssignPred, posInIdx, indexAssignment);
                 continue;
             }
 
@@ -1485,8 +1414,7 @@ void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpress
                 canAssignPredToIndex(rt, thisIndex.multikeyPaths[posInIdx], &used);
 
             if (shouldAssign) {
-                indexAssignment->preds.push_back(couldAssignPred);
-                indexAssignment->positions.push_back(posInIdx);
+                assignPredicate(outsidePreds, couldAssignPred, posInIdx, indexAssignment);
             }
         }
 
@@ -1536,10 +1464,12 @@ bool PlanEnumerator::alreadyCompounded(const set<MatchExpression*>& ixisectAssig
     return false;
 }
 
-size_t PlanEnumerator::getPosition(const IndexEntry& indexEntry, const std::string& path) {
+size_t PlanEnumerator::getPosition(const IndexEntry& indexEntry, MatchExpression* predicate) {
+    invariant(predicate->getTag());
+    RelevantTag* relevantTag = static_cast<RelevantTag*>(predicate->getTag());
     size_t position = 0;
     for (auto&& element : indexEntry.keyPattern) {
-        if (element.fieldName() == path) {
+        if (element.fieldName() == relevantTag->path) {
             return position;
         }
         ++position;
@@ -1594,25 +1524,7 @@ void PlanEnumerator::tagMemo(size_t id) {
     NodeAssignment* assign = _memo[id];
     verify(NULL != assign);
 
-    if (NULL != assign->pred) {
-        PredicateAssignment* pa = assign->pred.get();
-        verify(NULL == pa->expr->getTag());
-        verify(pa->indexToAssign < pa->indexes.size());
-        auto index = pa->indexes[pa->indexToAssign];
-        auto position = pa->positions[pa->indexToAssign];
-        const bool canCombineBounds = true;
-        pa->expr->setTag(new IndexTag(index, position, canCombineBounds));
-
-        // Add all OrPushdownTags for this index assignment.
-        for (const auto& orPushdown : pa->orPushdowns[pa->indexToAssign]) {
-            auto expr = orPushdown.first;
-            if (!expr->getTag()) {
-                expr->setTag(new OrPushdownTag());
-            }
-            OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(expr->getTag());
-            orPushdownTag->addDestination(orPushdown.second.clone());
-        }
-    } else if (NULL != assign->orAssignment) {
+    if (NULL != assign->orAssignment) {
         OrAssignment* oa = assign->orAssignment.get();
         for (size_t i = 0; i < oa->subnodes.size(); ++i) {
             tagMemo(oa->subnodes[i]);
@@ -1644,16 +1556,16 @@ void PlanEnumerator::tagMemo(size_t id) {
                         new IndexTag(assign.index, assign.positions[j], assign.canCombineBounds));
                 }
             }
-        }
 
-        // Add all OrPushdownTags for this index assignment.
-        for (const auto& orPushdown : aes.orPushdowns) {
-            auto expr = orPushdown.first;
-            if (!expr->getTag()) {
-                expr->setTag(new OrPushdownTag());
+            // Add all OrPushdownTags for this index assignment.
+            for (const auto& orPushdown : assign.orPushdowns) {
+                auto expr = orPushdown.first;
+                if (!expr->getTag()) {
+                    expr->setTag(new OrPushdownTag());
+                }
+                OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(expr->getTag());
+                orPushdownTag->addDestination(orPushdown.second.clone());
             }
-            OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(expr->getTag());
-            orPushdownTag->addDestination(orPushdown.second.clone());
         }
     } else {
         verify(0);
@@ -1664,15 +1576,7 @@ bool PlanEnumerator::nextMemo(size_t id) {
     NodeAssignment* assign = _memo[id];
     verify(NULL != assign);
 
-    if (NULL != assign->pred) {
-        PredicateAssignment* pa = assign->pred.get();
-        pa->indexToAssign++;
-        if (pa->indexToAssign >= pa->indexes.size()) {
-            pa->indexToAssign = 0;
-            return true;
-        }
-        return false;
-    } else if (NULL != assign->orAssignment) {
+    if (NULL != assign->orAssignment) {
         OrAssignment* oa = assign->orAssignment.get();
 
         // Limit the number of OR enumerations
diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
index 456464845b4..97a7549e6ad 100644
--- a/src/mongo/db/query/plan_enumerator.h
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -167,11 +167,6 @@ private:
      * The PlanEnumerator is interested in matching predicates and indices.  Predicates
      * are leaf nodes in the parse tree.  {x:5}, {x: {$geoWithin:...}} are both predicates.
      *
-     * When we have simple predicates, like {x:5}, the task is easy: any indices prefixed
-     * with 'x' can be used to answer the predicate.  This is where the PredicateAssignment
-     * is used.
-     *
-     * With logical operators, things are more complicated.  Let's start with OR, the simplest.
      * Since the output of an OR is the union of its results, each of its children must be
      * indexed for the entire OR to be indexed.  If each subtree of an OR is indexable, the
      * OR is as well.
@@ -179,26 +174,11 @@ private:
      * For an AND to be indexed, only one of its children must be indexed.  AND is an
      * intersection of its children, so each of its children describes a superset of the
      * produced results.
+     *
+     * Leaf predicates are also given AND assignments, since they may index outside predicates that
+     * have been pushed down through OR nodes.
      */
 
-    struct PredicateAssignment {
-        PredicateAssignment() : indexToAssign(0) {}
-
-        std::vector<IndexID> indexes;
-        // Not owned here.
-        MatchExpression* expr;
-
-        // The position of 'expr' in each index key pattern.
-        std::vector<size_t> positions;
-
-        // Enumeration state. The current index in 'indexes', 'positions', and 'orPushdowns'.
-        size_t indexToAssign;
-
-        // The expressions that should receive an OrPushdownTag for each index.
-        std::vector<std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>>>
-            orPushdowns;
-    };
-
     struct OrAssignment {
         OrAssignment() : counter(0) {}
 
@@ -224,14 +204,14 @@ private:
         // multiple predicates are assigned to the same position of a multikey index, then the
         // access planner should generate a self-intersection plan.
         bool canCombineBounds = true;
+
+        // The expressions that should receive an OrPushdownTag when this assignment is made.
+        std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> orPushdowns;
     };
 
     struct AndEnumerableState {
         std::vector<OneIndexAssignment> assignments;
         std::vector<MemoID> subnodesToIndex;
-
-        // The expressions that should receive an OrPushdownTag when this assignment is made.
-        std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> orPushdowns;
     };
 
     struct AndAssignment {
@@ -253,7 +233,6 @@ private:
      * Associates indices with predicates.
      */
     struct NodeAssignment {
-        std::unique_ptr<PredicateAssignment> pred;
         std::unique_ptr<OrAssignment> orAssignment;
         std::unique_ptr<AndAssignment> andAssignment;
         std::unique_ptr<ArrayAssignment> arrayAssignment;
@@ -384,11 +363,18 @@ private:
      *       (b) a shared prefix of the paths X and Y inside the innermost $elemMatch causes the
      *           index to be multikey.
      *
+     * If a predicate in 'couldAssign' is also in 'outsidePreds', then it is assumed to be an
+     * outside predicate that was pushed down through an OR. Instead of adding it to
+     * indexAssignment->preds, we add it to indexAssignment->orPushdowns. We create its
+     * OrPushdownTag using the route specified in 'outsidePreds'.
+     *
      * This function should only be called if the index has path-level multikey information.
      * Otherwise, getMultikeyCompoundablePreds() and compound() should be used instead.
      */
-    void assignMultikeySafePredicates(const std::vector<MatchExpression*>& couldAssign,
-                                      OneIndexAssignment* indexAssignment);
+    void assignMultikeySafePredicates(
+        const std::vector<MatchExpression*>& couldAssign,
+        const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+        OneIndexAssignment* indexAssignment);
 
     /**
      * 'andAssignment' contains assignments that we've already committed to outputting,
@@ -431,10 +417,10 @@ private:
      * and idxToNotFirst (and the sub-trees in 'subnodes').  Outputs the assignments into
      * 'andAssignment'. The predicates in 'outsidePreds' are considered for OrPushdownTags.
      */
-    void enumerateOneIndex(const IndexToPredMap& idxToFirst,
-                           const IndexToPredMap& idxToNotFirst,
+    void enumerateOneIndex(IndexToPredMap idxToFirst,
+                           IndexToPredMap idxToNotFirst,
                            const std::vector<MemoID>& subnodes,
-                           const unordered_map<MatchExpression*, std::deque<size_t>> outsidePreds,
+                           const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
                            AndAssignment* andAssignment);
 
     /**
@@ -460,17 +446,23 @@ private:
                   OneIndexAssignment* assign);
 
     /**
-     * Returns the position of 'path' in the key pattern for 'indexEntry'. It is illegal to call
-     * this if 'path' is not present in the key pattern.
+     * Returns the position that 'predicate' can use in the key pattern for 'indexEntry'. It is
+     * illegal to call this if 'predicate' does not have a RelevantTag, or it cannot use the index.
      */
-    size_t getPosition(const IndexEntry& indexEntry, const std::string& path);
+    size_t getPosition(const IndexEntry& indexEntry, MatchExpression* predicate);
 
-    /*
-     * Finds all predicates in 'outsidePreds' for which 'index' is relevant, and constructs
-     * OrPushdownTag::Destinations for those predicates.
+    /**
+     * Adds 'pred' to 'indexAssignment', using 'position' as its position in the index. If 'pred' is
+     * in 'outsidePreds', then it is assumed to be an outside predicate that was pushed down through
+     * an OR. Instead of adding it to indexAssignment->preds, we add it to
+     * indexAssignment->orPushdowns. We create its OrPushdownTag using the route specified in
+     * 'outsidePreds'. 'pred' must be able to use the index and be multikey-safe to add to
+     * 'indexAssignment'.
      */
-    std::vector<std::pair<MatchExpression*, OrPushdownTag::Destination>> getOrPushdowns(
-        IndexID index, const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds);
+    void assignPredicate(const unordered_map<MatchExpression*, std::deque<size_t>>& outsidePreds,
+                         MatchExpression* pred,
+                         size_t position,
+                         OneIndexAssignment* indexAssignment);
 
     /**
      * Return the memo entry for 'node'.  Does some sanity checking to ensure that a memo entry
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 6d39ffe6934..0eb4b574820 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -299,6 +299,21 @@ Status QueryPlanner::cacheDataFromTaggedTree(const MatchExpression* const tagged
     } else if (taggedTree->getTag() &&
                taggedTree->getTag()->getType() == MatchExpression::TagData::Type::OrPushdownTag) {
         OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(taggedTree->getTag());
+
+        if (orPushdownTag->getIndexTag()) {
+            const IndexTag* itag = static_cast<const IndexTag*>(orPushdownTag->getIndexTag());
+
+            if (is2DIndex(relevantIndices[itag->index].keyPattern)) {
+                return Status(ErrorCodes::BadValue, "can't cache '2d' index");
+            }
+
+            std::unique_ptr<IndexEntry> indexEntry =
+                stdx::make_unique<IndexEntry>(relevantIndices[itag->index]);
+            indexTree->entry.reset(indexEntry.release());
+            indexTree->index_pos = itag->pos;
+            indexTree->canCombineBounds = itag->canCombineBounds;
+        }
+
         for (const auto& dest : orPushdownTag->getDestinations()) {
             PlanCacheIndexTree::OrPushdown orPushdown;
             orPushdown.route = dest.route;
@@ -355,16 +370,7 @@ Status QueryPlanner::tagAccordingToCache(MatchExpression* filter,
         }
     }
 
-    if (NULL != indexTree->entry.get()) {
-        map<StringData, size_t>::const_iterator got = indexMap.find(indexTree->entry->name);
-        if (got == indexMap.end()) {
-            mongoutils::str::stream ss;
-            ss << "Did not find index with name: " << indexTree->entry->name;
-            return Status(ErrorCodes::BadValue, ss);
-        }
-        filter->setTag(
-            new IndexTag(got->second, indexTree->index_pos, indexTree->canCombineBounds));
-    } else if (!indexTree->orPushdowns.empty()) {
+    if (!indexTree->orPushdowns.empty()) {
         filter->setTag(new OrPushdownTag());
         OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(filter->getTag());
         for (const auto& orPushdown : indexTree->orPushdowns) {
@@ -382,6 +388,23 @@ Status QueryPlanner::tagAccordingToCache(MatchExpression* filter,
         }
     }
 
+    if (indexTree->entry.get()) {
+        map<StringData, size_t>::const_iterator got = indexMap.find(indexTree->entry->name);
+        if (got == indexMap.end()) {
+            mongoutils::str::stream ss;
+            ss << "Did not find index with name: " << indexTree->entry->name;
+            return Status(ErrorCodes::BadValue, ss);
+        }
+        if (filter->getTag()) {
+            OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(filter->getTag());
+            orPushdownTag->setIndexTag(
+                new IndexTag(got->second, indexTree->index_pos, indexTree->canCombineBounds));
+        } else {
+            filter->setTag(
+                new IndexTag(got->second, indexTree->index_pos, indexTree->canCombineBounds));
+        }
+    }
+
     return Status::OK();
 }
 
diff --git a/src/mongo/db/query/query_planner_array_test.cpp b/src/mongo/db/query/query_planner_array_test.cpp
index 0595e2f5ac7..87882799331 100644
--- a/src/mongo/db/query/query_planner_array_test.cpp
+++ b/src/mongo/db/query/query_planner_array_test.cpp
@@ -337,7 +337,7 @@ TEST_F(QueryPlannerTest, ElemMatchIndexedNestedOr) {
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {filter: {$and: [{foo:1},"
-        "{bar:{$elemMatch:{$or:[{baz:2}]}}}]}, "
+        "{bar:{$elemMatch:{baz:2}}}]}, "
         "node: {ixscan: {pattern: {'bar.baz': 1}, "
         "bounds: {'bar.baz': [[2,2,true,true]]}}}}}");
 }
@@ -371,7 +371,7 @@ TEST_F(QueryPlannerTest, ElemMatchIndexedNestedOrMultikey) {
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {filter: {$and: [{foo:1},"
-        "{bar: {$elemMatch: {$or: [{$and: [{baz:2}, {z:3}]}]}}}]},"
+        "{bar: {$elemMatch: {$and: [{baz:2}, {z:3}]}}}]},"
         "node: {ixscan: {pattern: {'bar.baz': 1, 'bar.z': 1}, "
         "bounds: {'bar.baz': [[2,2,true,true]],"
         "'bar.z': [[3,3,true,true]]}}}}}");
@@ -1651,4 +1651,407 @@ TEST_F(QueryPlannerTest, ContainedOrElemMatchPredicateIsLeadingFieldIndexInterse
     assertSolutionExists("{cscan: {dir: 1}}}}");
 }
 
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineLeadingFields) {
+    const bool multikey = true;
+    addIndex(BSON("a.b" << 1), multikey);
+    addIndex(BSON("a.c" << 1), multikey);
+
+    runQuery(
+        fromjson("{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: 6}]}]}}}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: "
+        "6}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]]}}},"
+        "{ixscan: {pattern: {'a.c': 1}, bounds: {'a.c': [[6, 6, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: "
+        "6}]}]}}}, node: "
+        "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, Infinity, true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineLeadingFields) {
+    MultikeyPaths multikeyPaths{{0U}};
+    addIndex(BSON("a.b" << 1), multikeyPaths);
+    addIndex(BSON("a.c" << 1), multikeyPaths);
+
+    runQuery(
+        fromjson("{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: 6}]}]}}}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{$and: [{b: {$lte: 10}}, "
+        "{b: {$gte: 0}}]}, {c: 6}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, 10, true, true]]}}},"
+        "{ixscan: {pattern: {'a.c': 1}, bounds: {'a.c': [[6, 6, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {$or: [{b: {$lte: 10}}, {c: "
+        "6}]}]}}}, node: "
+        "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, Infinity, true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineLeadingFields) {
+    MultikeyPaths multikeyPaths{{0U}};
+    addIndex(BSON("a.b" << 1), multikeyPaths);
+    addIndex(BSON("a.c" << 1), multikeyPaths);
+
+    runQuery(
+        fromjson("{$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {$or: [{b: {$lte: "
+                 "10}}, {c: 6}]}}}]}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {$or: [{b: "
+        "{$lte: 10}}, {c: 6}]}}}]}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]]}}},"
+        "{ixscan: {pattern: {'a.c': 1}, bounds: {'a.c': [[6, 6, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {$or: [{b: "
+        "{$lte: 10}}, {c: 6}]}}}]}, node: "
+        "{ixscan: {pattern: {'a.b': 1}, bounds: {'a.b': [[0, Infinity, true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundFields) {
+    const bool multikey = true;
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikey);
+    addIndex(BSON("a.d" << 1), multikey);
+
+    runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{$and: [{b: 5}, {c: 6}]}, {d: "
+        "7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+        "[[6, 6, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}, node: "
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+        "[['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundFields) {
+    const bool multikey = true;
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikey);
+    addIndex(BSON("a.d" << 1), multikey);
+
+    runQuery(fromjson(
+        "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: 7}]}}}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: "
+        "7}]}}}]}, node: "
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+        "[['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundFields) {
+    MultikeyPaths multikeyPaths1{{0U}, {0U}};
+    MultikeyPaths multikeyPaths2{{0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths1);
+    addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+    runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{$and: [{b: 5}, {c: 6}]}, {d: "
+        "7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+        "[[6, 6, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {$or: [{c: 6}, {d: 7}]}]}}}, node: "
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+        "[['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundFields) {
+    MultikeyPaths multikeyPaths1{{0U}, {0U}};
+    MultikeyPaths multikeyPaths2{{0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths1);
+    addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+    runQuery(fromjson(
+        "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: 7}]}}}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {$or: [{c: 6}, {d: "
+        "7}]}}}]}, node: "
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[5, 5, true, true]], 'a.c': "
+        "[['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineLeadingOutsidePreds) {
+    const bool multikey = true;
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikey);
+    addIndex(BSON("a.d" << 1), multikey);
+
+    runQuery(fromjson(
+        "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+    assertNumSolutions(5);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+        "[{b: {$lte: 10}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], "
+        "'a.c': [[6, 6, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+        "[{b: {$gte: 0}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, Infinity, true, true]], "
+        "'a.c': [[6, 6, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, "
+        "{d: 7}]}]}}}, node: "
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], "
+        "'a.c': [['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, "
+        "{d: 7}]}]}}}, node: "
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, Infinity, true, true]], "
+        "'a.c': [['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineLeadingOutsidePreds) {
+    MultikeyPaths multikeyPaths1{{0U}, {0U}};
+    MultikeyPaths multikeyPaths2{{0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths1);
+    addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+    runQuery(fromjson(
+        "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+        "[{b: {$lte: 10}}, {b: {$gte: 0}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, 10, true, true]], 'a.c': "
+        "[[6, 6, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, "
+        "{d: 7}]}]}}}, node: "
+        "{ixscan: {pattern: {'a.b': 1, 'a.c': 1}, bounds: {'a.b': [[0, 10, true, true]], 'a.c': "
+        "[['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineLeadingOutsidePreds) {
+    MultikeyPaths multikeyPaths{{0U}, {}};
+    addIndex(BSON("a.b" << 1 << "c" << 1), multikeyPaths);
+    addIndex(BSON("d" << 1));
+
+    runQuery(
+        fromjson("{$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: 10}}}}, "
+                 "{$or: [{c: 6}, {d: 7}]}]}"));
+    assertNumSolutions(5);
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+        "10}}}}]}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], c: "
+        "[[6, 6, true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+        "10}}}}]}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[0, Infinity, true, true]], c: [[6, "
+        "6, true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+        "10}}}}, {$or: [{c: 6}, {d: 7}]}]}, node: "
+        "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[-Infinity, 10, true, true]], c: "
+        "[['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+        "10}}}}, {$or: [{c: 6}, {d: 7}]}]}, node: "
+        "{ixscan: {pattern: {'a.b': 1, c: 1}, bounds: {'a.b': [[0, Infinity, true, true]], c: "
+        "[['MinKey', 'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineTrailingOutsidePreds) {
+    const bool multikey = true;
+    addIndex(BSON("a.c" << 1 << "a.b" << 1), multikey);
+    addIndex(BSON("a.d" << 1), multikey);
+
+    runQuery(fromjson(
+        "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+    assertNumSolutions(2);
+    std::vector<std::string> alternates;
+    alternates.push_back(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+        "[{b: {$gte: 0}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+        "[[0, Infinity, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    alternates.push_back(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+        "[{b: {$lte: 10}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+        "[[-Infinity, 10, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertHasOneSolutionOf(alternates);
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineTrailingOutsidePreds) {
+    MultikeyPaths multikeyPaths1{{0U}, {0U}};
+    MultikeyPaths multikeyPaths2{{0U}};
+    addIndex(BSON("a.c" << 1 << "a.b" << 1), multikeyPaths1);
+    addIndex(BSON("a.d" << 1), multikeyPaths2);
+
+    runQuery(fromjson(
+        "{a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{c: 6}, {d: 7}]}]}}}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: {$gte: 0}}, {b: {$lte: 10}}, {$or: [{$and: "
+        "[{b: {$gte: 0}}, {b: {$lte: 10}}, {c: 6}]}, {d: 7}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+        "[[0, 10, true, true]]}}},"
+        "{ixscan: {pattern: {'a.d': 1}, bounds: {'a.d': [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineTrailingOutsidePreds) {
+    MultikeyPaths multikeyPaths{{}, {0U}};
+    addIndex(BSON("c" << 1 << "a.b" << 1), multikeyPaths);
+    addIndex(BSON("d" << 1));
+
+    runQuery(
+        fromjson("{$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: 10}}}}, "
+                 "{$or: [{c: 6}, {d: 7}]}]}"));
+    assertNumSolutions(2);
+    std::vector<std::string> alternates;
+    alternates.push_back(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+        "10}}}}]}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {c: 1, 'a.b': 1}, bounds: {c: [[6, 6, true, true]], 'a.b': [[0, "
+        "Infinity, true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    alternates.push_back(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}}}}, {a: {$elemMatch: {b: {$lte: "
+        "10}}}}]}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {c: 1, 'a.b': 1}, bounds: {c: [[6, 6, true, true]], 'a.b': "
+        "[[-Infinity, 10, true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertHasOneSolutionOf(alternates);
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundTrailingOutsidePreds) {
+    const bool multikey = true;
+    addIndex(BSON("a.d" << 1 << "a.c" << 1 << "a.b" << 1), multikey);
+    addIndex(BSON("a.e" << 1), multikey);
+
+    runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{d: 7}, {e: 8}]}]}}}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{$and: [{b: 5}, {c: 6}, "
+        "{d: 7}]}, {e: 8}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.d': 1, 'a.c': 1, 'a.b': 1}, bounds: {'a.d': [[7, 7, true, true]], "
+        "'a.c': [[6, 6, true, true]], 'a.b': [[5, 5, true, true]]}}},"
+        "{ixscan: {pattern: {'a.e': 1}, bounds: {'a.e': [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundTrailingOutsidePreds) {
+    const bool multikey = true;
+    addIndex(BSON("d" << 1 << "a.c" << 1 << "a.b" << 1), multikey);
+    addIndex(BSON("e" << 1));
+
+    runQuery(fromjson(
+        "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}, {$or: [{d: 7}, {e: 8}]}]}"));
+    assertNumSolutions(2);
+    std::vector<std::string> alternates;
+    alternates.push_back(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}]}, node: "
+        "{or: {nodes: ["
+        "{ixscan: {pattern: {d: 1, 'a.c': 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.c': "
+        "[[6, 6, true, true]], 'a.b': [['MinKey', 'MaxKey', true, true]]}}},"
+        "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    alternates.push_back(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}]}, node: "
+        "{or: {nodes: ["
+        "{ixscan: {pattern: {d: 1, 'a.c': 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.c': "
+        "[['MinKey', 'MaxKey', true, true]], 'a.b': [[5, 5, true, true]]}}},"
+        "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertHasOneSolutionOf(alternates);
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundTrailingOutsidePreds) {
+    MultikeyPaths multikeyPaths1{{0U}, {0U}, {0U}};
+    MultikeyPaths multikeyPaths2{{0U}};
+    addIndex(BSON("a.d" << 1 << "a.c" << 1 << "a.b" << 1), multikeyPaths1);
+    addIndex(BSON("a.e" << 1), multikeyPaths2);
+
+    runQuery(fromjson("{a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{d: 7}, {e: 8}]}]}}}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$elemMatch: {$and: [{b: 5}, {c: 6}, {$or: [{$and: [{b: 5}, {c: 6}, "
+        "{d: 7}]}, {e: 8}]}]}}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.d': 1, 'a.c': 1, 'a.b': 1}, bounds: {'a.d': [[7, 7, true, true]], "
+        "'a.c': [[6, 6, true, true]], 'a.b': [[5, 5, true, true]]}}},"
+        "{ixscan: {pattern: {'a.e': 1}, bounds: {'a.e': [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundTrailingOutsidePreds) {
+    MultikeyPaths multikeyPaths{{}, {0U}, {0U}};
+    addIndex(BSON("d" << 1 << "a.c" << 1 << "a.b" << 1), multikeyPaths);
+    addIndex(BSON("e" << 1));
+
+    runQuery(fromjson(
+        "{$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}, {$or: [{d: 7}, {e: 8}]}]}"));
+    assertNumSolutions(2);
+    // When we have path-level multikey info, we ensure that predicates are assigned in order of
+    // index position.
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a: {$elemMatch: {b: 5}}}, {a: {$elemMatch: {c: 6}}}]}, node: "
+        "{or: {nodes: ["
+        "{ixscan: {pattern: {d: 1, 'a.c': 1, 'a.b': 1}, bounds: {d: [[7, 7, true, true]], 'a.c': "
+        "[[6, 6, true, true]], 'a.b': [['MinKey', 'MaxKey', true, true]]}}},"
+        "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
 }  // namespace
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 3e433b450fa..de3607bf0af 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -4989,4 +4989,284 @@ TEST_F(QueryPlannerTest, ContainedOrNotPredicateIsLeadingFieldInBothBranchesInde
     assertSolutionExists("{cscan: {dir: 1}}}}");
 }
 
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineLeadingFields) {
+    const bool multikey = true;
+    addIndex(BSON("a" << 1), multikey);
+    addIndex(BSON("b" << 1));
+
+    runQuery(fromjson("{$and: [{a: {$gte: 0}}, {$or: [{a: {$lte: 10}}, {b: 6}]}]}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {a: 1}, bounds: {a: [[-Infinity, 10, true, true]]}}},"
+        "{ixscan: {pattern: {b: 1}, bounds: {b: [[6, 6, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$or: [{a: {$lte: 10}}, {b: 6}]}, node: "
+        "{ixscan: {pattern: {a: 1}, bounds: {a: [[0, Infinity, true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineLeadingFields) {
+    MultikeyPaths multikeyPaths{{0U}};
+    addIndex(BSON("a" << 1), multikeyPaths);
+    addIndex(BSON("b" << 1));
+
+    runQuery(fromjson("{$and: [{a: {$gte: 0}}, {$or: [{a: {$lte: 10}}, {b: 6}]}]}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {a: 1}, bounds: {a: [[-Infinity, 10, true, true]]}}},"
+        "{ixscan: {pattern: {b: 1}, bounds: {b: [[6, 6, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$or: [{a: {$lte: 10}}, {b: 6}]}, node: "
+        "{ixscan: {pattern: {a: 1}, bounds: {a: [[0, Infinity, true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineLeadingFields) {
+    MultikeyPaths multikeyPaths{{}, {0U}};
+    addIndex(BSON("a" << 1 << "c" << 1), multikeyPaths);
+    addIndex(BSON("b" << 1));
+
+    runQuery(fromjson("{$and: [{a: {$gte: 0}}, {$or: [{a: {$lte: 10}}, {b: 6}]}]}"));
+    assertNumSolutions(3);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[0, 10, true, true]]}}},"
+        "{ixscan: {pattern: {b: 1}, bounds: {b: [[6, 6, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$or: [{a: {$lte: 10}}, {b: 6}]}, node: "
+        "{ixscan: {pattern: {a: 1, c: 1}, bounds: {a: [[0, Infinity, true, true]], c: [['MinKey', "
+        "'MaxKey', true, true]]}}}"
+        "}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundFields) {
+    const bool multikey = true;
+    addIndex(BSON("b" << 1 << "a" << 1), multikey);
+    addIndex(BSON("c" << 1));
+
+    runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+        "true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundFields) {
+    const bool multikey = true;
+    addIndex(BSON("a.c" << 1 << "a.b" << 1), multikey);
+    addIndex(BSON("d" << 1));
+
+    runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{'a.c': 6}, {d: 7}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+        "[['MinKey', 'MaxKey', true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundFields) {
+    MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("b" << 1 << "a" << 1), multikeyPaths);
+    addIndex(BSON("c" << 1));
+
+    runQuery(fromjson("{$and: [{a: 5}, {$or: [{b: 6}, {c: 7}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+        "true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundDottedFields) {
+    MultikeyPaths multikeyPaths{{1U}, {1U}};
+    addIndex(BSON("a.c" << 1 << "a.b" << 1), multikeyPaths);
+    addIndex(BSON("d" << 1));
+
+    runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{'a.c': 6}, {d: 7}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+        "[[5, 5, true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundFields) {
+    MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a.c" << 1 << "a.b" << 1), multikeyPaths);
+    addIndex(BSON("d" << 1));
+
+    runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{'a.c': 6}, {d: 7}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {'a.c': 1, 'a.b': 1}, bounds: {'a.c': [[6, 6, true, true]], 'a.b': "
+        "[['MinKey', 'MaxKey', true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCombineTrailingFields) {
+    const bool multikey = true;
+    addIndex(BSON("b" << 1 << "a" << 1), multikey);
+    addIndex(BSON("c" << 1));
+
+    runQuery(
+        fromjson("{$and: [{a: {$gte: 0}}, {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}]}"));
+    assertNumSolutions(2);
+    std::vector<std::string> alternates;
+    alternates.push_back(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[-Infinity, 10, "
+        "true, true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    alternates.push_back(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[0, Infinity, "
+        "true, true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertHasOneSolutionOf(alternates);
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCombineTrailingFields) {
+    MultikeyPaths multikeyPaths{{}, {0U}};
+    addIndex(BSON("b" << 1 << "a" << 1), multikeyPaths);
+    addIndex(BSON("c" << 1));
+
+    runQuery(
+        fromjson("{$and: [{a: {$gte: 0}}, {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}]}"));
+    assertNumSolutions(2);
+    std::vector<std::string> alternates;
+    alternates.push_back(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[-Infinity, 10, "
+        "true, true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    alternates.push_back(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[0, Infinity, "
+        "true, true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertHasOneSolutionOf(alternates);
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCombineTrailingFields) {
+    MultikeyPaths multikeyPaths{{0U}, {}};
+    addIndex(BSON("b" << 1 << "a" << 1), multikeyPaths);
+    addIndex(BSON("c" << 1));
+
+    runQuery(
+        fromjson("{$and: [{a: {$gte: 0}}, {$or: [{$and: [{a: {$lte: 10}}, {b: 6}]}, {c: 7}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1}, bounds: {b: [[6, 6, true, true]], a: [[0, 10, true, "
+        "true]]}}},"
+        "{ixscan: {pattern: {c: 1}, bounds: {c: [[7, 7, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCompoundTrailingFields) {
+    const bool multikey = true;
+    addIndex(BSON("b" << 1 << "a" << 1 << "c" << 1), multikey);
+    addIndex(BSON("d" << 1));
+
+    runQuery(fromjson("{$and: [{a: 5}, {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1, c: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+        "true]], c: [[7, 7, true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrMultikeyCannotCompoundTrailingFields) {
+    const bool multikey = true;
+    addIndex(BSON("d" << 1 << "a.b" << 1 << "a.c" << 1), multikey);
+    addIndex(BSON("e" << 1));
+
+    runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{$and: [{'a.c': 6}, {d: 7}]}, {e: 8}]}]}"));
+    assertNumSolutions(2);
+    std::vector<std::string> alternates;
+    alternates.push_back(
+        "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {d: 1, 'a.b': 1, 'a.c': 1}, bounds: {d: [[7, 7, true, true]], 'a.b': "
+        "[['MinKey', 'MaxKey', true, true]], 'a.c': [[6, 6, true, true]]}}},"
+        "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    alternates.push_back(
+        "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {d: 1, 'a.b': 1, 'a.c': 1}, bounds: {d: [[7, 7, true, true]], 'a.b': "
+        "[[5, 5, true, true]], 'a.c': [['MinKey', 'MaxKey', true, true]]}}},"
+        "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertHasOneSolutionOf(alternates);
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCompoundTrailingFields) {
+    MultikeyPaths multikeyPaths{{}, {0U}, {}};
+    addIndex(BSON("b" << 1 << "a" << 1 << "c" << 1), multikeyPaths);
+    addIndex(BSON("d" << 1));
+
+    runQuery(fromjson("{$and: [{a: 5}, {$or: [{$and: [{b: 6}, {c: 7}]}, {d: 8}]}]}"));
+    assertNumSolutions(2);
+    assertSolutionExists(
+        "{fetch: {filter: {a: 5}, node: {or: {nodes: ["
+        "{ixscan: {pattern: {b: 1, a: 1, c: 1}, bounds: {b: [[6, 6, true, true]], a: [[5, 5, true, "
+        "true]], c: [[7, 7, true, true]]}}},"
+        "{ixscan: {pattern: {d: 1}, bounds: {d: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundTrailingFields) {
+    MultikeyPaths multikeyPaths{{}, {0U}, {0U}};
+    addIndex(BSON("d" << 1 << "a.b" << 1 << "a.c" << 1), multikeyPaths);
+    addIndex(BSON("e" << 1));
+
+    runQuery(fromjson("{$and: [{'a.b': 5}, {$or: [{$and: [{'a.c': 6}, {d: 7}]}, {e: 8}]}]}"));
+    assertNumSolutions(2);
+    // When we have path-level multikey info, we ensure that predicates are assigned in order of
+    // index position.
+    assertSolutionExists(
+        "{fetch: {filter: {'a.b': 5}, node: {or: {nodes: ["
+        "{fetch: {filter: {'a.c': 6}, node: {ixscan: {pattern: {d: 1, 'a.b': 1, 'a.c': 1}, bounds: "
+        "{d: [[7, 7, true, true]], 'a.b': [[5, 5, true, true]], 'a.c': [['MinKey', 'MaxKey', true, "
+        "true]]}}}}},"
+        "{ixscan: {pattern: {e: 1}, bounds: {e: [[8, 8, true, true]]}}}"
+        "]}}}}");
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
 }  // namespace