SERVER-38164 $or pushdown optimization does not correctly handle $not within an $elemMatch

(cherry picked from commit 94d0e046baa64d1aa1a6af97e2d19bb466cc1ff5)

3 files changed, 253 insertions, 58 deletions

diff --git a/jstests/core/elemmatch_or_pushdown.js b/jstests/core/elemmatch_or_pushdown.js
index f1a1dacd7ad..b33afcc23b8 100644
--- a/jstests/core/elemmatch_or_pushdown.js
+++ b/jstests/core/elemmatch_or_pushdown.js
@@ -1,5 +1,6 @@
 /**
- * Tests that an $elemMatch-$or query is evaluated correctly. Designed to reproduce SERVER-33005.
+ * Tests that an $elemMatch-$or query is evaluated correctly. Designed to reproduce SERVER-33005 and
+ * SERVER-38164.
  */
 (function() {
     "use strict";
@@ -38,4 +39,46 @@
                   .sort({_id: 1})
                   .toArray(),
               [{_id: 0, a: 5, b: [{c: [{f: 8}], d: 6}]}, {_id: 4, a: 5, b: [{c: [{f: 8}], e: 7}]}]);
+
+    // Test that $not predicates in $elemMatch can be pushed into an $or sibling of the $elemMatch.
+    coll.drop();
+    assert.writeOK(coll.insert({_id: 0, arr: [{a: 0, b: 2}], c: 4, d: 5}));
+    assert.writeOK(coll.insert({_id: 1, arr: [{a: 1, b: 2}], c: 4, d: 5}));
+    assert.writeOK(coll.insert({_id: 2, arr: [{a: 0, b: 3}], c: 4, d: 5}));
+    assert.writeOK(coll.insert({_id: 3, arr: [{a: 1, b: 3}], c: 4, d: 5}));
+    assert.writeOK(coll.insert({_id: 4, arr: [{a: 0, b: 2}], c: 6, d: 7}));
+    assert.writeOK(coll.insert({_id: 5, arr: [{a: 1, b: 2}], c: 6, d: 7}));
+    assert.writeOK(coll.insert({_id: 6, arr: [{a: 0, b: 3}], c: 6, d: 7}));
+    assert.writeOK(coll.insert({_id: 7, arr: [{a: 1, b: 3}], c: 6, d: 7}));
+
+    const keyPattern = {"arr.a": 1, "arr.b": 1, c: 1, d: 1};
+    assert.commandWorked(coll.createIndex(keyPattern));
+
+    const elemMatchOr = {
+        arr: {$elemMatch: {a: {$ne: 1}, $or: [{b: 2}, {b: 3}]}},
+        $or: [
+            {c: 4, d: 5},
+            {c: 6, d: 7},
+        ],
+    };
+
+    // Confirm that we get the same results using the index and a COLLSCAN.
+    for (let hint of[keyPattern, {$natural: 1}]) {
+        assert.eq(coll.find(elemMatchOr, {_id: 1}).sort({_id: 1}).hint(hint).toArray(),
+                  [{_id: 0}, {_id: 2}, {_id: 4}, {_id: 6}]);
+
+        assert.eq(
+            coll.aggregate(
+                    [
+                      {
+                        $match:
+                            {arr: {$elemMatch: {a: {$ne: 1}}}, $or: [{c: 4, d: 5}, {c: 6, d: 7}]}
+                      },
+                      {$project: {_id: 1}},
+                      {$sort: {_id: 1}}
+                    ],
+                    {hint: hint})
+                .toArray(),
+            [{_id: 0}, {_id: 2}, {_id: 4}, {_id: 6}]);
+    }
 }());
diff --git a/src/mongo/db/query/index_tag.cpp b/src/mongo/db/query/index_tag.cpp
index ab37d2b781e..bf6ccc93fa4 100644
--- a/src/mongo/db/query/index_tag.cpp
+++ b/src/mongo/db/query/index_tag.cpp
@@ -219,9 +219,42 @@ void getElemMatchOrPushdownDescendants(MatchExpression* node, std::vector<MatchE
         for (size_t i = 0; i < node->numChildren(); ++i) {
             getElemMatchOrPushdownDescendants(node->getChild(i), out);
         }
+    } else if (node->matchType() == MatchExpression::NOT) {
+        // The immediate child of NOT may be tagged, but there should be no tags deeper than this.
+        auto* childNode = node->getChild(0);
+        if (childNode->getTag() && childNode->getTag()->getType() == TagType::OrPushdownTag) {
+            out->push_back(node);
+        }
     }
 }
 
+// Attempts to push the given node down into the 'indexedOr' subtree. Returns true if the predicate
+// can subsequently be trimmed from the MatchExpression tree, false otherwise.
+bool processOrPushdownNode(MatchExpression* node, MatchExpression* indexedOr) {
+    // If the node is a negation, then its child is the predicate node that may be tagged.
+    auto* predNode = node->matchType() == MatchExpression::NOT ? node->getChild(0) : node;
+
+    // If the predicate node is not tagged for pushdown, return false immediately.
+    if (!predNode->getTag() || predNode->getTag()->getType() != TagType::OrPushdownTag) {
+        return false;
+    }
+    invariant(indexedOr);
+
+    // Predicate node is tagged for pushdown. Extract its route through the $or and its index tag.
+    auto* orPushdownTag = static_cast<OrPushdownTag*>(predNode->getTag());
+    auto destinations = orPushdownTag->releaseDestinations();
+    auto indexTag = orPushdownTag->releaseIndexTag();
+    predNode->setTag(nullptr);
+
+    // Attempt to push the node into the indexedOr, then re-set its tag to the indexTag.
+    const bool pushedDown = pushdownNode(node, indexedOr, std::move(destinations));
+    predNode->setTag(indexTag.release());
+
+    // Return true if we can trim the predicate. We could trim the node even if it had an index tag
+    // for this position, but that could make the index tagging of the tree wrong.
+    return pushedDown && !predNode->getTag();
+}
+
 // Finds all the nodes in the tree with OrPushdownTags and copies them to the Destinations specified
 // in the OrPushdownTag, tagging them with the TagData in the Destination. Removes the node from its
 // current location if possible.
@@ -235,66 +268,19 @@ void resolveOrPushdowns(MatchExpression* tree) {
 
         for (size_t i = 0; i < andNode->numChildren(); ++i) {
             auto child = andNode->getChild(i);
-            if (child->getTag() && child->getTag()->getType() == TagType::OrPushdownTag) {
-                invariant(indexedOr);
-                OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(child->getTag());
-                auto destinations = orPushdownTag->releaseDestinations();
-                auto indexTag = orPushdownTag->releaseIndexTag();
-                child->setTag(nullptr);
-                if (pushdownNode(child, indexedOr, std::move(destinations)) && !indexTag) {
-
-                    // indexedOr can completely satisfy the predicate specified in child, so we can
-                    // trim it. We could remove the child even if it had an index tag for this
-                    // position, but that could make the index tagging of the tree wrong.
-                    auto ownedChild = andNode->removeChild(i);
-
-                    // We removed child i, so decrement the child index.
-                    --i;
-                } else {
-                    child->setTag(indexTag.release());
-                }
-            } else if (child->matchType() == MatchExpression::NOT && child->getChild(0)->getTag() &&
-                       child->getChild(0)->getTag()->getType() == TagType::OrPushdownTag) {
-                invariant(indexedOr);
-                OrPushdownTag* orPushdownTag =
-                    static_cast<OrPushdownTag*>(child->getChild(0)->getTag());
-                auto destinations = orPushdownTag->releaseDestinations();
-                auto indexTag = orPushdownTag->releaseIndexTag();
-                child->getChild(0)->setTag(nullptr);
-
-                // Push down the NOT and its child.
-                if (pushdownNode(child, indexedOr, std::move(destinations)) && !indexTag) {
-
-                    // indexedOr can completely satisfy the predicate specified in child, so we can
-                    // trim it. We could remove the child even if it had an index tag for this
-                    // position, but that could make the index tagging of the tree wrong.
-                    auto ownedChild = andNode->removeChild(i);
-
-                    // We removed child i, so decrement the child index.
-                    --i;
-                } else {
-                    child->getChild(0)->setTag(indexTag.release());
-                }
-            } else if (child->matchType() == MatchExpression::ELEM_MATCH_OBJECT) {
 
-                // Push down all descendants of child with OrPushdownTags.
+            // For ELEM_MATCH_OBJECT, we push down all tagged descendants. However, we cannot trim
+            // any of these predicates, since the $elemMatch filter must be applied in its entirety.
+            if (child->matchType() == MatchExpression::ELEM_MATCH_OBJECT) {
                 std::vector<MatchExpression*> orPushdownDescendants;
                 getElemMatchOrPushdownDescendants(child, &orPushdownDescendants);
-                if (!orPushdownDescendants.empty()) {
-                    invariant(indexedOr);
-                }
                 for (auto descendant : orPushdownDescendants) {
-                    OrPushdownTag* orPushdownTag =
-                        static_cast<OrPushdownTag*>(descendant->getTag());
-                    auto destinations = orPushdownTag->releaseDestinations();
-                    auto indexTag = orPushdownTag->releaseIndexTag();
-                    descendant->setTag(nullptr);
-                    pushdownNode(descendant, indexedOr, std::move(destinations));
-                    descendant->setTag(indexTag.release());
-
-                    // We cannot trim descendants of an $elemMatch object, since the filter must
-                    // be applied in its entirety.
+                    processOrPushdownNode(descendant, indexedOr);
                 }
+            } else if (processOrPushdownNode(child, indexedOr)) {
+                // The indexed $or can completely satisfy the child predicate, so we trim it.
+                auto ownedChild = andNode->removeChild(i);
+                --i;
             }
         }
     }
diff --git a/src/mongo/db/query/query_planner_array_test.cpp b/src/mongo/db/query/query_planner_array_test.cpp
index fc3c81968f3..6fc0fb8d85b 100644
--- a/src/mongo/db/query/query_planner_array_test.cpp
+++ b/src/mongo/db/query/query_planner_array_test.cpp
@@ -882,8 +882,7 @@ TEST_F(QueryPlannerTest, MultikeyComplexDoubleDotted2) {
         " 'a.e.d':[['MinKey','MaxKey',true,true]]}}}}}");
 }
 
-// SERVER-13422: check that we plan $elemMatch object correctly with
-// index intersection.
+// SERVER-13422: check that we plan $elemMatch object correctly with index intersection.
 TEST_F(QueryPlannerTest, ElemMatchIndexIntersection) {
     params.options = QueryPlannerParams::NO_TABLE_SCAN | QueryPlannerParams::INDEX_INTERSECTION;
     addIndex(BSON("shortId" << 1));
@@ -2056,6 +2055,173 @@ TEST_F(QueryPlannerTest, ContainedOrPathLevelMultikeyCannotCompoundTrailingOutsi
     assertSolutionExists("{cscan: {dir: 1}}}}");
 }
 
+TEST_F(QueryPlannerTest, CanHoistNegatedPredFromElemMatchIntoSiblingOr) {
+    addIndex(BSON("arr.a" << 1 << "arr.b" << 1 << "c" << 1 << "d" << 1));
+
+    auto queryStr =
+        "{arr: {$elemMatch: {a: {$ne:1}, $or: [{b:2}, {b:3}]}}, $or: [{c:4, d:5}, {c:6, d:7}]}";
+    runQuery(fromjson(queryStr));
+
+    assertNumSolutions(4U);
+
+    // Solution 1: {'arr.a': {$ne: 1}} is hoisted by $elemMatch and pushed into the top-level $or.
+    assertSolutionExists(
+        "{fetch: {filter: {arr: {$elemMatch: {a: {$ne: 1}, $or: [{b: 2}, {b: 3}]}}}, node: {or: "
+        "{nodes: [{ixscan: {pattern: {'arr.a': 1, 'arr.b': 1, c: 1, d: 1}, bounds: {'arr.a': "
+        "[['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b' :[['MinKey', 'MaxKey', "
+        "true, true]], c: [[4, 4, true, true]], d: [[5, 5, true, true]]}}},{ixscan: {pattern: "
+        "{'arr.a': 1, 'arr.b': 1, c: 1, d: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, "
+        "'MaxKey', false, true]], 'arr.b' :[['MinKey', 'MaxKey', true, true]], c: [[6, 6, true, "
+        "true]], d: [[7, 7, true, true]]}}}]}}}}");
+
+    // Solution 2: {'arr.a': {$ne: 1}} is pushed down into its sibling $or within $elemMatch.
+    assertSolutionExists(
+        "{fetch: {filter: {arr: {$elemMatch: {a: {$ne:1}, $or: [{a: {$ne:1}, b:2}, {a: {$ne:1}, "
+        "b:3}]}}, $or: [{c:4, d:5}, {c:6, d:7}]}, node: {or: {nodes: [{ixscan: {pattern: {'arr.a': "
+        "1, 'arr.b': 1, c: 1, d: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', "
+        "false, true]], 'arr.b' :[[2, 2, true, true]], c: [['MinKey', 'MaxKey', true, true]], d: "
+        "[['MinKey', 'MaxKey', true, true]]}}},{ixscan: {pattern: {'arr.a': 1, 'arr.b': 1, c: 1, "
+        "d: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], "
+        "'arr.b' :[[3, 3, true, true]], c: [['MinKey', 'MaxKey', true, true]], d: [['MinKey', "
+        "'MaxKey', true, true]]}}}]}}}}");
+
+    // Solution 3: no pushdowns; {'arr.a': {$ne: 1}} is indexed directly, without any other fields.
+    assertSolutionExists(
+        "{fetch: {filter: {arr: {$elemMatch: {a: {$ne:1}, $or: [{b:2}, {b:3}]}}, $or: [{c:4, d:5}, "
+        "{c:6, d:7}]}, node: {ixscan: {pattern: {'arr.a': 1, 'arr.b': 1, c: 1, d: 1}, bounds: "
+        "{'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b': [['MinKey', "
+        "'MaxKey', true, true]], c: [['MinKey', 'MaxKey', true, true]], d: [['MinKey', 'MaxKey', "
+        "true, true]]}}}}}");
+
+    // Solution 4: COLLSCAN.
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, CanHoistNegatedPredFromElemMatchIntoSiblingOrWithMultikeyPaths) {
+    MultikeyPaths multikeyPaths{{0U}, {0U}, {}, {}};
+    addIndex(BSON("arr.a" << 1 << "arr.b" << 1 << "c" << 1 << "d" << 1), multikeyPaths);
+
+    auto queryStr =
+        "{arr: {$elemMatch: {a: {$ne:1}, $or: [{b:2}, {b:3}]}}, $or: [{c:4, d:5}, {c:6, d:7}]}";
+    runQuery(fromjson(queryStr));
+
+    assertNumSolutions(4U);
+
+    // Solution 1: {'arr.a': {$ne: 1}} is hoisted by $elemMatch and pushed into the top-level $or.
+    assertSolutionExists(
+        "{fetch: {filter: {arr: {$elemMatch: {a: {$ne: 1}, $or: [{b: 2}, {b: 3}]}}}, node: {or: "
+        "{nodes: [{fetch: {filter: {a: {$ne: 1}}, node: {ixscan: {pattern: {'arr.a': 1, 'arr.b': "
+        "1, c: 1, d: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, "
+        "true]], 'arr.b' :[['MinKey', 'MaxKey', true, true]], c: [[4, 4, true, true]], d: [[5, 5, "
+        "true, true]]}}}}}, {fetch: {filter: {a: {$ne: 1}}, node: {ixscan: {pattern: {'arr.a': 1, "
+        "'arr.b': 1, c: 1, d: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', "
+        "false, true]], 'arr.b' :[['MinKey', 'MaxKey', true, true]], c: [[6, 6, true, true]], d: "
+        "[[7, 7, true, true]]}}}}}]}}}}");
+
+    // Solution 2: {'arr.a': {$ne: 1}} is pushed down into its sibling $or within $elemMatch.
+    assertSolutionExists(
+        "{fetch: {filter: {arr: {$elemMatch: {a: {$ne:1}, $or: [{a: {$ne:1}, b:2}, {a: {$ne:1}, "
+        "b:3}]}}, $or: [{c:4, d:5}, {c:6, d:7}]}, node: {or: {nodes: [{ixscan: {pattern: {'arr.a': "
+        "1, 'arr.b': 1, c: 1, d: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', "
+        "false, true]], 'arr.b' :[[2, 2, true, true]], c: [['MinKey', 'MaxKey', true, true]], d: "
+        "[['MinKey', 'MaxKey', true, true]]}}},{ixscan: {pattern: {'arr.a': 1, 'arr.b': 1, c: 1, "
+        "d: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], "
+        "'arr.b' :[[3, 3, true, true]], c: [['MinKey', 'MaxKey', true, true]], d: [['MinKey', "
+        "'MaxKey', true, true]]}}}]}}}}");
+
+    // Solution 3: no pushdowns; {'arr.a': {$ne: 1}} is indexed directly, without any other fields.
+    assertSolutionExists(
+        "{fetch: {filter: {arr: {$elemMatch: {a: {$ne:1}, $or: [{b:2}, {b:3}]}}, $or: [{c:4, d:5}, "
+        "{c:6, d:7}]}, node: {ixscan: {pattern: {'arr.a': 1, 'arr.b': 1, c: 1, d: 1}, bounds: "
+        "{'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b': [['MinKey', "
+        "'MaxKey', true, true]], c: [['MinKey', 'MaxKey', true, true]], d: [['MinKey', 'MaxKey', "
+        "true, true]]}}}}}");
+
+    // Solution 4: COLLSCAN.
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+}
+
+TEST_F(QueryPlannerTest, MultipleNegatedElemMatchPredOrPushdownsDoNotSelfIntersect) {
+    params.options |= QueryPlannerParams::INDEX_INTERSECTION;
+    addIndex(BSON("arr.a" << 1 << "arr.b" << 1));
+    addIndex(BSON("arr.a" << 1 << "c" << 1));
+
+    auto queryStr = "{arr: {$elemMatch: {a: {$ne:1}, $or: [{b:2}, {b:3}]}}, $or: [{c:4}, {c:6}]}";
+    runQuery(fromjson(queryStr));
+
+    assertNumSolutions(9U);
+
+    // Solution 1: no pushdowns; {'arr.a': {$ne: 1}} is indexed directly by {arr.a: 1, arr.b: 1}.
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'arr.a': 1, 'arr.b': 1}, bounds: {'arr.a': [['MinKey', "
+        "1, true, false], [1, 'MaxKey', false, true]], 'arr.b': [['MinKey', 'MaxKey', true, "
+        "true]]}}}}}");
+
+    // Solution 2: no pushdowns; {'arr.a': {$ne: 1}} is indexed directly by {arr.a: 1, c: 1}.
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'arr.a': 1, c: 1}, bounds: {'arr.a': [['MinKey', 1, "
+        "true, false], [1, 'MaxKey', false, true]], c: [['MinKey', 'MaxKey', true, true]]}}}}}");
+
+    // Solution 3: {'arr.a': {$ne: 1}} pushed into sibling $or and indexed by {arr.a: 1, arr.b: 1}.
+    assertSolutionExists(
+        "{fetch: {node: {or: {nodes: [{ixscan: {pattern: {'arr.a': 1, 'arr.b': 1}, bounds: "
+        "{'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b' :[[2, 2, "
+        "true, true]]}}},{ixscan: {pattern: {'arr.a': 1, 'arr.b': 1}, bounds: {'arr.a': "
+        "[['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b' :[[3, 3, true, "
+        "true]]}}}]}}}}");
+
+    // Solution 4: {'arr.a': {$ne: 1}} pushed into top-level $or and indexed by {arr.a: 1, c: 1}.
+    assertSolutionExists(
+        "{fetch: {node: {or: {nodes: [{ixscan: {pattern: {'arr.a': 1, c: 1}, bounds: {'arr.a': "
+        "[['MinKey', 1, true, false], [1, 'MaxKey', false, true]], c: [[4, 4, true, "
+        "true]]}}},{ixscan: {pattern: {'arr.a': 1, c: 1}, bounds: {'arr.a': [['MinKey', 1, true, "
+        "false], [1, 'MaxKey', false, true]], c: [[6, 6, true, true]]}}}]}}}}");
+
+    // Solution 5: COLLSCAN.
+    assertSolutionExists("{cscan: {dir: 1}}}}");
+
+    // Verify that we do not produce a plan which intersects BOTH $ors to which the $ne predicate
+    // has been pushed down. That is, we do not intersect the candidate plans outlined in solution 3
+    // and 4 above with one another, but only with non-pushdown plans 1 and 2.
+
+    // Solution 6: AND_HASH Solutions 1 and 3.
+    assertSolutionExists(
+        "{fetch: {node: {andHash: {nodes: [{or: {nodes: [{ixscan: {pattern: {'arr.a': 1, 'arr.b': "
+        "1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b' "
+        ":[[2, 2, true, true]]}}}, {ixscan: {pattern: {'arr.a': 1, 'arr.b': 1}, bounds: {'arr.a': "
+        "[['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b' :[[3, 3, true, "
+        "true]]}}}]}}, {ixscan: {pattern: {'arr.a': 1, 'arr.b': 1}, bounds: {'arr.a': [['MinKey', "
+        "1, true, false], [1, 'MaxKey', false, true]], 'arr.b' :[['MinKey', 'MaxKey', true, "
+        "true]]}}}]}}}}");
+
+    // Solution 7: AND_HASH Solutions 1 and 4.
+    assertSolutionExists(
+        "{fetch: {node: {andHash: {nodes: [{or: {nodes: [{ixscan: {pattern: {'arr.a': 1, c: 1}, "
+        "bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], c :[[4, 4, "
+        "true, true]]}}}, {ixscan: {pattern: {'arr.a': 1, c: 1}, bounds: {'arr.a': [['MinKey', 1, "
+        "true, false], [1, 'MaxKey', false, true]], c :[[6, 6, true, true]]}}}]}}, {ixscan: "
+        "{pattern: {'arr.a': 1, 'arr.b': 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, "
+        "'MaxKey', false, true]], 'arr.b' :[['MinKey', 'MaxKey', true, true]]}}}]}}}}");
+
+    // Solution 8: AND_HASH Solutions 2 and 3.
+    assertSolutionExists(
+        "{fetch: {node: {andHash: {nodes: [{or: {nodes: [{ixscan: {pattern: {'arr.a': 1, 'arr.b': "
+        "1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b' "
+        ":[[2, 2, true, true]]}}}, {ixscan: {pattern: {'arr.a': 1, 'arr.b': 1}, bounds: {'arr.a': "
+        "[['MinKey', 1, true, false], [1, 'MaxKey', false, true]], 'arr.b' :[[3, 3, true, "
+        "true]]}}}]}}, {ixscan: {pattern: {'arr.a': 1, c: 1}, bounds: {'arr.a': [['MinKey', 1, "
+        "true, false], [1, 'MaxKey', false, true]], c: [['MinKey', 'MaxKey', true, true]]}}}]}}}}");
+
+    // Solution 9: AND_HASH Solutions 2 and 4.
+    assertSolutionExists(
+        "{fetch: {node: {andHash: {nodes: [{or: {nodes: [{ixscan: {pattern: {'arr.a': 1, c: 1}, "
+        "bounds: {'arr.a': [['MinKey', 1, true, false], [1, 'MaxKey', false, true]], c :[[4, 4, "
+        "true, true]]}}}, {ixscan: {pattern: {'arr.a': 1, c: 1}, bounds: {'arr.a': [['MinKey', 1, "
+        "true, false], [1, 'MaxKey', false, true]], c :[[6, 6, true, true]]}}}]}}, {ixscan: "
+        "{pattern: {'arr.a': 1, c: 1}, bounds: {'arr.a': [['MinKey', 1, true, false], [1, "
+        "'MaxKey', false, true]], c :[['MinKey', 'MaxKey', true, true]]}}}]}}}}");
+}
+
 TEST_F(QueryPlannerTest, ContainedOrCannotPushdownThroughElemMatchObj) {
     addIndex(BSON("a" << 1 << "b.c" << 1));