SERVER-22401 Add new rules for assigning predicates to multikey indexes.

The metadata in the IndexEntry struct indicates what prefixes of the
indexed fields cause the index to be multikey. This information is used
to get tighter bounds by assigning additional predicates to the index.

3 files changed, 560 insertions, 8 deletions

diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index 117a305c3fe..db9d19a1665 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -35,6 +35,7 @@
 #include "mongo/db/query/indexability.h"
 #include "mongo/db/query/index_tag.h"
 #include "mongo/util/log.h"
+#include "mongo/util/string_map.h"
 
 namespace {
 
@@ -62,6 +63,157 @@ bool expressionRequiresIndex(const MatchExpression* node) {
         CanonicalQuery::countNodes(node, MatchExpression::TEXT) > 0;
 }
 
+size_t getPathLength(const MatchExpression* expr) {
+    return FieldRef{expr->path()}.numParts();
+}
+
+/**
+ * Returns true if 'component' refers to a part of 'rt->path' outside the innermost $elemMatch
+ * expression, and returns false otherwise. In particular, this function returns false if an
+ * expression isn't contained in an $elemMatch.
+ *
+ * For example, consider the expression {a: {$elemMatch: {b: {$gte: 0, $lt: 10}}}. The path "a.b"
+ * (component=1) is inside the $elemMatch expression, whereas the path "a" (component=0) is outside
+ * the $elemMatch expression.
+ */
+bool isPathOutsideElemMatch(const RelevantTag* rt, size_t component) {
+    if (rt->elemMatchExpr == nullptr) {
+        return false;
+    }
+
+    const size_t elemMatchRootLength = getPathLength(rt->elemMatchExpr);
+    invariant(elemMatchRootLength > 0);
+    return component < elemMatchRootLength;
+}
+
+using PossibleFirstAssignment = std::vector<MatchExpression*>;
+
+void getPossibleFirstAssignments(const IndexEntry& thisIndex,
+                                 const vector<MatchExpression*>& predsOverLeadingField,
+                                 std::vector<PossibleFirstAssignment>* possibleFirstAssignments) {
+    invariant(thisIndex.multikey && thisIndex.multikeyPaths);
+    const auto& multikeyPaths = *thisIndex.multikeyPaths;
+
+    if (multikeyPaths[0].empty()) {
+        // No prefix of the leading index field causes the index to be multikey. In other words, the
+        // index isn't multikey as a result of the leading index field. We can then safely assign
+        // all predicates on it to the index and the access planner will intersect the bounds.
+        *possibleFirstAssignments = {predsOverLeadingField};
+        return;
+    }
+
+    // At least one prefix of the leading index field causes the index to be multikey. We can't
+    // intersect bounds on the leading index field unless the predicates are joined by an
+    // $elemMatch.
+    std::map<MatchExpression*, std::vector<MatchExpression*>> predsByElemMatchExpr;
+    for (auto* pred : predsOverLeadingField) {
+        invariant(pred->getTag());
+        RelevantTag* rt = static_cast<RelevantTag*>(pred->getTag());
+
+        if (rt->elemMatchExpr == nullptr) {
+            // 'pred' isn't part of an $elemMatch, so we can't assign any other predicates on the
+            // leading index field to the index.
+            possibleFirstAssignments->push_back({pred});
+        } else {
+            // 'pred' is part of an $elemMatch, so we group it together with any other leaf
+            // expressions in the same $elemMatch context.
+            predsByElemMatchExpr[rt->elemMatchExpr].push_back(pred);
+        }
+    }
+
+    // We can only assign all of the leaf expressions in the $elemMatch to the index if no prefix of
+    // the leading index field that is longer than the root of the $elemMatch causes the index to be
+    // multikey. For example, consider the index {'a.b': 1} and the query
+    // {a: $elemMatch: {b: {$gte: 0, $lt: 10}}}. If 'a.b' refers to an array value, then the two
+    // leaf expressions inside the $elemMatch can match distinct elements. We are therefore unable
+    // to assign both to the index and intersect the bounds.
+    for (const auto& elemMatchExprIt : predsByElemMatchExpr) {
+        invariant(!elemMatchExprIt.second.empty());
+        const auto* pred = elemMatchExprIt.second.front();
+
+        invariant(pred->getTag());
+        RelevantTag* rt = static_cast<RelevantTag*>(pred->getTag());
+        invariant(rt->elemMatchExpr != nullptr);
+
+        const size_t elemMatchRootLength = getPathLength(elemMatchExprIt.first);
+        invariant(elemMatchRootLength > 0);
+
+        // Since the multikey path components are 0-indexed, 'elemMatchRootLength' actually
+        // corresponds to the path component immediately following the root of the $elemMatch.
+        if (multikeyPaths[0].lower_bound(elemMatchRootLength) == multikeyPaths[0].end()) {
+            // The root of the $elemMatch is the longest prefix of the leading index field that
+            // causes the index to be multikey, so we can assign all of the leaf expressions in the
+            // $elemMatch to the index.
+            possibleFirstAssignments->push_back(elemMatchExprIt.second);
+        } else {
+            // There is a path longer than the root of the $elemMatch that causes the index to be
+            // multikey, so we can only assign one of the leaf expressions in the $elemMatch to the
+            // index. Since we don't know which one is the most selective, we generate a plan for
+            // each predicate and rank them against each other.
+            for (auto* predCannotIntersect : elemMatchExprIt.second) {
+                possibleFirstAssignments->push_back({predCannotIntersect});
+            }
+        }
+    }
+}
+
+/**
+ * Returns true if the leaf expression associated with 'rt' can be assigned to the index given the
+ * path prefixes of the queried field that cause the index to be multikey and the predicates already
+ * assigned to the index. Otherwise, this function returns false if the leaf expression associated
+ * with 'rt' can't be assigned to the index.
+ *
+ * This function modifies 'used' under the assumption that if it returns true, then the predicate
+ * will be assigned to the index.
+ */
+bool canAssignPredToIndex(const RelevantTag* rt,
+                          const std::set<size_t>& multikeyComponents,
+                          StringMap<MatchExpression*>* used) {
+    invariant(used);
+    const FieldRef path(rt->path);
+
+    // We start by checking with the shortest prefix of the queried path to avoid needing to undo
+    // any changes we make to 'used' as we go.
+    for (const auto multikeyComponent : multikeyComponents) {
+        // 'pathPrefix' is a prefix of a queried path that causes the index to be multikey.
+        StringData pathPrefix = path.dottedSubstring(0, multikeyComponent + 1);
+
+        auto search = used->find(pathPrefix);
+        if (search == used->end()) {
+            // 'pathPrefix' is a prefix of a queried path that we haven't seen before.
+            if (isPathOutsideElemMatch(rt, multikeyComponent)) {
+                // 'pathPrefix' is outside the innermost $elemMatch, so we record its $elemMatch
+                // context to ensure that we don't assign another predicate to 'thisIndex' along
+                // this path unless they are part of the same $elemMatch.
+                invariant(rt->elemMatchExpr != nullptr);
+                (*used)[pathPrefix] = rt->elemMatchExpr;
+            } else {
+                // 'pathPrefix' is either inside the innermost $elemMatch or not inside an
+                // $elemMatch at all. We record that we can't assign another predicate to
+                // 'thisIndex' either at or beyond 'pathPrefix' without violating the intersecting
+                // and compounding rules for multikey indexes.
+                (*used)[pathPrefix] = nullptr;
+
+                // Since we check starting with the shortest prefixes of the queried path that cause
+                // 'thisIndex' to be multikey, marking 'used' with nullptr here means that there
+                // will be no further attempts to intersect or compound bounds by assigning a
+                // different predicate at or beyond 'pathPrefix'.
+                break;
+            }
+        } else {
+            // 'pathPrefix' is a prefix of a queried path that we've already assigned to
+            // 'thisIndex'. We can only intersect or compound bounds by assigning 'couldAssignPred'
+            // to 'thisIndex' if the leaf expressions are joined by the same $elemMatch context.
+            const bool cannotAssignPred =
+                (search->second == nullptr || search->second != rt->elemMatchExpr);
+            if (cannotAssignPred) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
 }  // namespace
 
 
@@ -591,14 +743,42 @@ void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst,
     for (IndexToPredMap::const_iterator it = idxToFirst.begin(); it != idxToFirst.end(); ++it) {
         const IndexEntry& thisIndex = (*_indices)[it->first];
 
-        // If the index is multikey, we only assign one pred to it.  We also skip
-        // compounding.  TODO: is this also true for 2d and 2dsphere indices?  can they be
-        // multikey but still compoundable?
-        if (thisIndex.multikey) {
-            // Since the index is multikey, we can only use one of the predicates over the leading
-            // field of the index. However, we do not know which of these predicates is most
-            // selective. Therefore, we will generate a plan for each so that they can be ranked
-            // against each other.
+        if (thisIndex.multikey && thisIndex.multikeyPaths) {
+            // We have path-level information about what causes 'thisIndex' to be multikey and can
+            // use this information to get tighter bounds by assigning additional predicates to the
+            // index.
+            //
+            // Depending on the predicates specified and what parts of the leading index field cause
+            // the index to be multikey, we may not be able to assign all of predicates to the
+            // index. Since we don't know which set of predicates is the most selective, we generate
+            // multiple plans and rank them against each other.
+            std::vector<PossibleFirstAssignment> possibleFirstAssignments;
+            getPossibleFirstAssignments(thisIndex, it->second, &possibleFirstAssignments);
+
+            // Output an assignment for each of the possible assignments on the leading index field.
+            for (const auto& firstAssignment : possibleFirstAssignments) {
+                OneIndexAssignment indexAssign;
+                indexAssign.index = it->first;
+                indexAssign.preds = firstAssignment;
+                indexAssign.positions.resize(indexAssign.preds.size(), 0);
+
+                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);
+                }
+
+                AndEnumerableState state;
+                state.assignments.push_back(indexAssign);
+                andAssignment->choices.push_back(state);
+            }
+        } else if (thisIndex.multikey) {
+            // We don't have path-level information about what causes 'thisIndex' to be multikey.
+            // We therefore must assume the worst-case scenario: all prefixes of all indexed fields
+            // cause the index to be multikey. We therefore can only assign one of the predicates on
+            // the leading index field to the index. Since we don't know which one is the most
+            // selective, we generate a plan for each predicate and rank them against each other.
             for (auto pred : it->second) {
                 OneIndexAssignment indexAssign;
                 indexAssign.index = it->first;
@@ -1055,6 +1235,77 @@ void PlanEnumerator::getMultikeyCompoundablePreds(const vector<MatchExpression*>
     }
 }
 
+void PlanEnumerator::assignMultikeySafePredicates(const std::vector<MatchExpression*>& couldAssign,
+                                                  OneIndexAssignment* indexAssignment) {
+    invariant(indexAssignment);
+    invariant(indexAssignment->preds.size() == indexAssignment->positions.size());
+
+    const IndexEntry& thisIndex = (*_indices)[indexAssignment->index];
+    invariant(thisIndex.multikeyPaths);
+    const auto& multikeyPaths = *thisIndex.multikeyPaths;
+
+    // 'used' is a map from each prefix of a queried path that causes 'thisIndex' to be multikey to
+    // the 'elemMatchExpr' of the associated leaf expression's RelevantTag. We use it to ensure that
+    // leaf expressions sharing a prefix of their queried paths are only both assigned to
+    // 'thisIndex' if they are joined by the same $elemMatch context.
+    StringMap<MatchExpression*> used;
+
+    // Initialize 'used' with the predicates already assigned to 'thisIndex'.
+    for (size_t i = 0; i < indexAssignment->preds.size(); ++i) {
+        const auto* assignedPred = indexAssignment->preds[i];
+        const auto posInIdx = indexAssignment->positions[i];
+
+        // enumerateOneIndex() should have only already assigned predicates to 'thisIndex' that on
+        // the leading index field.
+        invariant(posInIdx == 0);
+
+        invariant(assignedPred->getTag());
+        RelevantTag* rt = static_cast<RelevantTag*>(assignedPred->getTag());
+
+        // 'assignedPred' has already been assigned to 'thisIndex', so canAssignPredToIndex() ought
+        // to return true.
+        invariant(canAssignPredToIndex(rt, multikeyPaths[posInIdx], &used));
+    }
+
+    size_t posInIdx = 0;
+
+    for (const auto keyElem : thisIndex.keyPattern) {
+        // Attempt to assign the predicates to 'thisIndex' according to their position in the index
+        // key pattern.
+        for (auto* couldAssignPred : couldAssign) {
+            invariant(Indexability::nodeCanUseIndexOnOwnField(couldAssignPred));
+            RelevantTag* rt = static_cast<RelevantTag*>(couldAssignPred->getTag());
+
+            if (keyElem.fieldNameStringData() != rt->path) {
+                continue;
+            }
+
+            // enumerateOneIndex() should only attempt to assign additional predicates to
+            // 'thisIndex' that are on the non-leading index fields.
+            invariant(posInIdx > 0);
+
+            if (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);
+                continue;
+            }
+
+            // See if any of the predicates that are already assigned to 'thisIndex' prevent us from
+            // assigning 'couldAssignPred' as well.
+            const bool shouldAssign = canAssignPredToIndex(rt, multikeyPaths[posInIdx], &used);
+
+            if (shouldAssign) {
+                indexAssignment->preds.push_back(couldAssignPred);
+                indexAssignment->positions.push_back(posInIdx);
+            }
+        }
+
+        ++posInIdx;
+    }
+}
+
 bool PlanEnumerator::alreadyCompounded(const set<MatchExpression*>& ixisectAssigned,
                                        const AndAssignment* andAssignment) {
     for (size_t i = 0; i < andAssignment->choices.size(); ++i) {
diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
index c547573ce2e..20994eedba7 100644
--- a/src/mongo/db/query/plan_enumerator.h
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -345,6 +345,31 @@ private:
                                       std::vector<MatchExpression*>* out);
 
     /**
+     * Assigns predicates from 'couldAssign' to 'indexAssignment' that can safely be assigned
+     * according to the intersecting and compounding rules for multikey indexes. The rules can
+     * loosely be stated as follows:
+     *
+     *   - It is always safe to assign a predicate on path Y to the index when no prefix of the path
+     *     Y causes the index to be multikey.
+     *
+     *   - For any non-$elemMatch predicate on path X already assigned to the index, it isn't safe
+     *     to assign a predicate on path Y (possibly equal to X) to the index when a shared prefix
+     *     of the paths X and Y causes the index to be multikey.
+     *
+     *   - For any $elemMatch predicate on path X already assigned to the index, it isn't safe to
+     *     assign a predicate on path Y (possibly equal to X) to the index when
+     *       (a) a shared prefix of the paths X and Y causes the index to be multikey and the
+     *           predicates aren't joined by the same $elemMatch context, or
+     *       (b) a shared prefix of the paths X and Y inside the innermost $elemMatch causes the
+     *           index to be multikey.
+     *
+     * 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);
+
+    /**
      * 'andAssignment' contains assignments that we've already committed to outputting,
      * including both single index assignments and ixisect assignments.
      *
diff --git a/src/mongo/db/query/query_planner_array_test.cpp b/src/mongo/db/query/query_planner_array_test.cpp
index 1f32860dbef..2123217780c 100644
--- a/src/mongo/db/query/query_planner_array_test.cpp
+++ b/src/mongo/db/query/query_planner_array_test.cpp
@@ -1137,4 +1137,280 @@ TEST_F(QueryPlannerTest, MultikeyElemMatchAllCompound3) {
         "bounds: {'arr.k': [[3,3,true,true]], 'arr.v': [[3,3,true,true]]}}}}}");
 }
 
+TEST_F(QueryPlannerTest, CanIntersectBoundsWhenFirstFieldIsNotMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{std::set<size_t>{}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$gte: 0, $lt: 10}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: {$gte: 0, $lt: 10}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[0, 10, true, false]], b: [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsOnFirstFieldWhenItAndSharedPrefixAreNotMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{std::set<size_t>{}, {1U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{'a.b': {$gte: 0, $lt: 10}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {'a.b': {$gte: 0, $lt: 10}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[0, 10, true, false]], 'a.c': [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotIntersectBoundsWhenFirstFieldIsMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, std::set<size_t>{}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$gte: 0, $lt: 10}}"));
+
+    assertNumSolutions(3U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: {$gte: 0, $lt: 10}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$lt: 10}}, node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[0, Infinity, true, true]], b: [['MinKey', 'MaxKey', true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a: {$gte: 0}}, node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[-Infinity, 10, true, false]], b: [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsWhenFirstFieldIsMultikeyButHasElemMatch) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, std::set<size_t>{}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {$gte: 0, $lt: 10}}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: {$elemMatch: {$gte: 0, $lt: 10}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[0, 10, true, false]], b: [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanComplementBoundsOnFirstFieldWhenItIsMultikeyAndHasNotEqualExpr) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, std::set<size_t>{}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$ne: 3}, b: 2}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [['MinKey', 3, true, false], [3, 'MaxKey', false, true]], "
+        "b: [[2, 2, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsWhenFirstFieldIsMultikeyAndHasNotInsideElemMatch) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, std::set<size_t>{}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {$not: {$gte: 10}, $gte: 0}}, b: 2}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[0, 10, true, false]], b: [[2, 2, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsOnFirstFieldWhenSharedPrefixIsMultikeyButHasElemMatch) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {b: {$gte: 0, $lt: 10}}}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: {$elemMatch: {b: {$gte: 0, $lt: 10}}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[0, 10, true, false]], 'a.c': [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotIntersectBoundsOnFirstFieldWhenItAndSharedPrefixAreMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U, 1U}, {0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {b: {$gte: 0, $lt: 10}, c: 2}}}"));
+
+    assertNumSolutions(3U);
+    assertSolutionExists(
+        "{cscan: {dir: 1, filter: {a: {$elemMatch: {b: {$gte: 0, $lt: 10}, c: 2}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[0, Infinity, true, true]], 'a.c': [[2, 2, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[-Infinity, 10, true, false]], 'a.c': [[2, 2, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsWhenSecondFieldIsNotMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, std::set<size_t>{}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: 2, b: {$gte: 0, $lt: 10}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: 2, b: {$gte: 0, $lt: 10}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[2, 2, true, true]], b: [[0, 10, true, false]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsOnSecondFieldWhenItAndSharedPrefixAreNotMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{1U}, std::set<size_t>{}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{'a.b': 2, 'a.c': {$gte: 0, $lt: 10}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {'a.b': 2, 'a.c': {$gte: 0, $lt: 10}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[2, 2, true, true]], 'a.c': [[0, 10, true, false]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotIntersectBoundsWhenSecondFieldIsMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{std::set<size_t>{}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: 2, b: {$gte: 0, $lt: 10}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: 2, b: {$gte: 0, $lt: 10}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[2, 2, true, true]], b: [[-Infinity, 10, true, false]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsWhenSecondFieldIsMultikeyButHasElemMatch) {
+    IndexEntry::MultikeyPaths multikeyPaths{std::set<size_t>{}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: 2, b: {$elemMatch: {$gte: 0, $lt: 10}}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: 2, b: {$elemMatch: {$gte: 0, $lt: 10}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[2, 2, true, true]], b: [[0, 10, true, false]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanComplementBoundsOnSecondFieldWhenItIsMultikeyAndHasNotEqualExpr) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+    IndexEntry::MultikeyPaths multikeyPaths{std::set<size_t>{}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: 2, b: {$ne: 3}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[2, 2, true, true]], "
+        "b: [['MinKey', 3, true, false], [3, 'MaxKey', false, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsWhenSecondFieldIsMultikeyAndHasNotInsideElemMatch) {
+    params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+    IndexEntry::MultikeyPaths multikeyPaths{std::set<size_t>{}, {0U}};
+    addIndex(BSON("a" << 1 << "b" << 1), multikeyPaths);
+    runQuery(fromjson("{a: 2, b: {$elemMatch: {$not: {$gte: 10}, $gte: 0}}}"));
+
+    assertNumSolutions(1U);
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {a: 1, b: 1}, "
+        "bounds: {a: [[2, 2, true, true]], b: [[0, 10, true, false]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanIntersectBoundsOnSecondFieldWhenSharedPrefixIsMultikeyButHasElemMatch) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {b: 2, c: {$gte: 0, $lt: 10}}}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{cscan: {dir: 1, filter: {a: {$elemMatch: {b: 2, c: {$gte: 0, $lt: 10}}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[2, 2, true, true]], 'a.c': [[0, 10, true, false]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotIntersectBoundsOnSecondFieldWhenItAndSharedPrefixAreMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, {0U, 1U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {b: 2, c: {$gte: 0, $lt: 10}}}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists(
+        "{cscan: {dir: 1, filter: {a: {$elemMatch: {b: 2, c: {$gte: 0, $lt: 10}}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[2, 2, true, true]], 'a.c': [[-Infinity, 10, true, false]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotIntersectBoundsOfTwoSeparateElemMatches) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+
+    runQuery(fromjson(
+        "{$and: [{a: {$elemMatch: {b: {$gte: 0}, c: {$lt: 20}}}}, "
+        "{a: {$elemMatch: {b: {$lt: 10}, c: {$gte: 5}}}}]}"));
+
+    assertNumSolutions(3U);
+    assertSolutionExists(
+        "{cscan: {dir: 1, "
+        "filter: {$and: [{a: {$elemMatch: {b: {$gte: 0}, c: {$lt: 20}}}}, "
+        "{a: {$elemMatch: {b: {$lt: 10}, c: {$gte: 5}}}}]}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[0, Infinity, true, true]], 'a.c': [[-Infinity, 20, true, false]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[-Infinity, 10, true, false]], 'a.c': [[5, Infinity, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanCompoundBoundsWhenSharedPrefixIsNotMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{1U}, {1U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{'a.b': 2, 'a.c': 3}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {'a.b': 2, 'a.c': 3}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[2, 2, true, true]], 'a.c': [[3, 3, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotCompoundBoundsWhenSharedPrefixIsMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{'a.b': 2, 'a.c': 3}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {'a.b': 2, 'a.c': 3}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {'a.b': [[2, 2, true, true]], 'a.c': [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanCompoundBoundsWhenSharedPrefixIsMultikeyButHasElemMatch) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U}, {0U}};
+    addIndex(BSON("a.b" << 1 << "a.c" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {b: 2, c: 3}}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: {$elemMatch: {b: 2, c: 3}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1, 'a.c': 1}, "
+        "bounds: {a: [[2, 2, true, true]], b: [[3, 3, true, true]]}}}}}");
+}
+
+TEST_F(QueryPlannerTest, CannotCompoundBoundsWhenSharedPrefixInsideElemMatchIsMultikey) {
+    IndexEntry::MultikeyPaths multikeyPaths{{0U, 1U}, {0U, 1U}};
+    addIndex(BSON("a.b.c" << 1 << "a.b.d" << 1), multikeyPaths);
+    runQuery(fromjson("{a: {$elemMatch: {'b.c': 2, 'b.d': 3}}}"));
+
+    assertNumSolutions(2U);
+    assertSolutionExists("{cscan: {dir: 1, filter: {a: {$elemMatch: {'b.c': 2, 'b.d': 3}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1, 'a.b.d': 1}, "
+        "bounds: {'a.b.c': [[2, 2, true, true]], 'a.b.d': [['MinKey', 'MaxKey', true, true]]}}}}}");
+}
+
 }  // namespace