SERVER-16042 generate a candidate plan for each predicate over the leading field of a multikey index

(cherry picked from commit 4372e7b826bbaff94d995c0a37d9a8bf29378e48)

Conflicts:
	src/mongo/db/query/query_planner_array_test.cpp
	src/mongo/db/query/query_planner_geo_test.cpp
	src/mongo/db/query/query_planner_test.cpp

2 files changed, 203 insertions, 53 deletions

diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index e7221a0ece6..e89f40ce090 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -590,40 +590,50 @@ void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst,
 
     // For each FIRST, we assign nodes to it.
     for (IndexToPredMap::const_iterator it = idxToFirst.begin(); it != idxToFirst.end(); ++it) {
-        // The assignment we're filling out.
-        OneIndexAssignment indexAssign;
-
-        // This is the index we assign to.
-        indexAssign.index = it->first;
-
         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) {
-            // TODO: could pick better pred than first but not too worried since we should
-            // really be isecting indices here.  Just take the first pred.  We don't assign
-            // any other preds to this index.  The planner will intersect the preds and this
-            // enumeration strategy is just one index at a time.
-            indexAssign.preds.push_back(it->second[0]);
-            indexAssign.positions.push_back(0);
-
-            // 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;
+            // 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.
+            for (auto pred : it->second) {
+                OneIndexAssignment indexAssign;
+                indexAssign.index = it->first;
+
+                indexAssign.preds.push_back(pred);
+                indexAssign.positions.push_back(0);
 
-                // ...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);
+                // 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;
+
+                    // ...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);
+                    }
                 }
+
+                // Output the assignment.
+                AndEnumerableState state;
+                state.assignments.push_back(indexAssign);
+                andAssignment->choices.push_back(state);
             }
         } else {
+            // The assignment we're filling out.
+            OneIndexAssignment indexAssign;
+
+            // This is the index we assign to.
+            indexAssign.index = it->first;
+
             // The index isn't multikey.  Assign all preds to it.  The planner will
             // intersect the bounds.
             indexAssign.preds = it->second;
@@ -638,11 +648,12 @@ void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst,
             if (compIt != idxToNotFirst.end()) {
                 compound(compIt->second, thisIndex, &indexAssign);
             }
-        }
 
-        AndEnumerableState state;
-        state.assignments.push_back(indexAssign);
-        andAssignment->choices.push_back(state);
+            // Output the assignment.
+            AndEnumerableState state;
+            state.assignments.push_back(indexAssign);
+            andAssignment->choices.push_back(state);
+        }
     }
 }
 
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 673ad998f3c..4a29870f408 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1135,7 +1135,7 @@ TEST_F(QueryPlannerTest, OrElemMatchObjectBeneathAnd) {
         "{$or: [{'a.b': 0, a: {$elemMatch: {b: {$lte: 1}}}},"
         "{a: {$elemMatch: {b: {$gte: 4}}}}]}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{or: {nodes: ["
@@ -1145,6 +1145,14 @@ TEST_F(QueryPlannerTest, OrElemMatchObjectBeneathAnd) {
         "{fetch: {filter: {a:{$elemMatch:{b:{$gte:4}}}}, node: "
         "{ixscan: {filter: null, pattern: {'a.b': 1},"
         "bounds: {'a.b': [[4,Infinity,true,true]]}}}}}]}}");
+     assertSolutionExists(
+         "{or: {nodes: ["
+         "{fetch: {filter: {a:{$elemMatch:{b:{$lte:1}}}},"
+         "node: {ixscan: {filter: null, pattern: {'a.b': 1}, "
+         "bounds: {'a.b': [[0,0,true,true]]}}}}},"
+         "{fetch: {filter: {a:{$elemMatch:{b:{$gte:4}}}}, node: "
+         "{ixscan: {filter: null, pattern: {'a.b': 1},"
+         "bounds: {'a.b': [[4,Infinity,true,true]]}}}}}]}}");
 }
 
 // SERVER-13960: $or below $elemMatch with an inexact covered predicate.
@@ -1908,11 +1916,14 @@ TEST_F(QueryPlannerTest, ElemMatchWithAllElemMatchChild2) {
         "{'a.b': {$elemMatch: {c: {$all: "
         "[{$elemMatch: {d: {$gt: 1, $lt: 3}}}]}}}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {node: {ixscan: {pattern: {'a.b.c.d': 1}, "
         "bounds: {'a.b.c.d': [[-Infinity,3,true,false]]}}}}}");
+     assertSolutionExists(
+         "{fetch: {node: {ixscan: {pattern: {'a.b.c.d': 1}, "
+         "bounds: {'a.b.c.d': [[1,Infinity,false,true]]}}}}}");
 }
 
 // SERVER-13677
@@ -1921,11 +1932,17 @@ TEST_F(QueryPlannerTest, ElemMatchWithAllChild) {
     addIndex(BSON("a.b.c" << 1), true);
     runQuery(fromjson("{z: 1, 'a.b': {$elemMatch: {c: {$all: [4, 5, 6]}}}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(4U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1}, "
         "bounds: {'a.b.c': [[4,4,true,true]]}}}}}");
+     assertSolutionExists(
+         "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1}, "
+         "bounds: {'a.b.c': [[5,5,true,true]]}}}}}");
+     assertSolutionExists(
+         "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1}, "
+         "bounds: {'a.b.c': [[6,6,true,true]]}}}}}");
 }
 
 TEST_F(QueryPlannerTest, ElemMatchValueMatch) {
@@ -2012,13 +2029,18 @@ TEST_F(QueryPlannerTest, ElemMatchEmbeddedAnd) {
     addIndex(BSON("a.b" << 1 << "a.c" << 1), true);
     runQuery(fromjson("{a: {$elemMatch: {b: {$gte: 2, $lt: 4}, c: 25}}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {filter: {a:{$elemMatch:{b:{$gte:2,$lt: 4},c:25}}}, node: "
         "{ixscan: {filter: null, pattern: {'a.b': 1, 'a.c': 1}, "
         "bounds: {'a.b': [[-Infinity,4,true,false]], "
         "'a.c': [[25,25,true,true]]}}}}}");
+     assertSolutionExists(
+         "{fetch: {filter: {a:{$elemMatch:{b:{$gte:2,$lt: 4},c:25}}}, node: "
+         "{ixscan: {filter: null, pattern: {'a.b': 1, 'a.c': 1}, "
+         "bounds: {'a.b': [[2,Infinity,true,true]], "
+         "'a.c': [[25,25,true,true]]}}}}}");
 }
 
 // SERVER-13664
@@ -2540,11 +2562,9 @@ TEST_F(QueryPlannerTest, And2DSphereSameFieldNonNearMultikey) {
         "  {a: {$geoIntersects: {$geometry: "
         "{type: 'Point', coordinates: [4.0, 1.0]}}}}]}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
-    // Bounds of the two 2dsphere geo predicates are combined into
-    // a single index scan.
-    assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}}");
+    assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}}", 2U);
 }
 
 TEST_F(QueryPlannerTest, And2DSphereWithNearSameField) {
@@ -3419,11 +3439,15 @@ TEST_F(QueryPlannerTest, HintElemMatch) {
     addIndex(fromjson("{'a.b': 1}"), true);
     runQueryHint(fromjson("{'a.b': 1, a: {$elemMatch: {b: 2}}}"), fromjson("{'a.b': 1}"));
 
-    assertNumSolutions(1U);
+    assertNumSolutions(2U);
     assertSolutionExists(
         "{fetch: {filter: {$and: [{a:{$elemMatch:{b:2}}}, {'a.b': 1}]}, "
         "node: {ixscan: {filter: null, pattern: {'a.b': 1}, bounds: "
         "{'a.b': [[2, 2, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {a:{$elemMatch:{b:2}}}, "
+        "node: {ixscan: {filter: null, pattern: {'a.b': 1}, bounds: "
+        "{'a.b': [[1, 1, true, true]]}}}}}");
 }
 
 TEST_F(QueryPlannerTest, HintInvalid) {
@@ -3638,11 +3662,20 @@ TEST_F(QueryPlannerTest, ThreeRegexSameFieldMultikey) {
     addIndex(BSON("a" << 1), true);
     runQuery(fromjson("{$and: [{a: /0/}, {a: /1/}, {a: /2/}]}"));
 
-    ASSERT_EQUALS(getNumSolutions(), 2U);
+    ASSERT_EQUALS(getNumSolutions(), 4U);
     assertSolutionExists("{cscan: {filter: {$and:[{a:/0/},{a:/1/},{a:/2/}]}, dir: 1}}");
     assertSolutionExists(
         "{fetch: {filter: {$and:[{a:/0/},{a:/1/},{a:/2/}]}, node: {ixscan: "
-        "{pattern: {a: 1}, filter: null}}}}");
+        "{pattern: {a: 1}, filter: null, "
+        "bounds: {a: [['', {}, true, false], [/0/, /0/, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and:[{a:/1/},{a:/0/},{a:/2/}]}, node: {ixscan: "
+        "{pattern: {a: 1}, filter: null, "
+        "bounds: {a: [['', {}, true, false], [/1/, /1/, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and:[{a:/2/},{a:/0/},{a:/1/}]}, node: {ixscan: "
+        "{pattern: {a: 1}, filter: null, "
+        "bounds: {a: [['', {}, true, false], [/2/, /2/, true, true]]}}}}}");
 }
 
 //
@@ -4017,17 +4050,14 @@ TEST_F(QueryPlannerTest, MultikeyTwoConstraintsSameField) {
     addIndex(BSON("a" << 1), true);
     runQuery(fromjson("{a: {$gt: 0, $lt: 5}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {filter: {$and: [{a: {$lt: 5}}, {a: {$gt: 0}}]}, dir: 1}}");
-
-    vector<string> alternates;
-    alternates.push_back(
+    assertSolutionExists(
         "{fetch: {filter: {a: {$lt: 5}}, node: {ixscan: {filter: null, "
         "pattern: {a: 1}, bounds: {a: [[0, Infinity, false, true]]}}}}}");
-    alternates.push_back(
+    assertSolutionExists(
         "{fetch: {filter: {a: {$gt: 0}}, node: {ixscan: {filter: null, "
         "pattern: {a: 1}, bounds: {a: [[-Infinity, 5, true, false]]}}}}}");
-    assertHasOneSolutionOf(alternates);
 }
 
 /**
@@ -4297,11 +4327,14 @@ TEST_F(QueryPlannerTest, MultikeyNestedElemMatch) {
     addIndex(BSON("a.b.c" << 1), true);
     runQuery(fromjson("{a: {$elemMatch: {b: {$elemMatch: {c: {$gte: 1, $lte: 1}}}}}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1}, bounds: "
         "{'a.b.c': [[-Infinity, 1, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1}, bounds: "
+        "{'a.b.c': [[1, Infinity, true, true]]}}}}}");
 }
 
 // The index bounds cannot be intersected because the index is multikey.
@@ -4313,11 +4346,14 @@ TEST_F(QueryPlannerTest, MultikeyNestedElemMatchIn) {
     addIndex(BSON("a.b.c" << 1), true);
     runQuery(fromjson("{a: {$elemMatch: {b: {$elemMatch: {c: {$gte: 1, $in:[2]}}}}}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1}, bounds: "
         "{'a.b.c': [[1, Infinity, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b.c': 1}, bounds: "
+        "{'a.b.c': [[2, 2, true, true]]}}}}}");
 }
 
 // The bounds can be compounded because the index is not multikey.
@@ -4370,7 +4406,7 @@ TEST_F(QueryPlannerTest, MultikeyElemMatchValue) {
 
 // We can intersect the bounds for all three predicates because
 // the index is not multikey.
-TEST_F(QueryPlannerTest, ElemMatchInterectBoundsNotMultikey) {
+TEST_F(QueryPlannerTest, ElemMatchIntersectBoundsNotMultikey) {
     addIndex(BSON("a.b" << 1));
     runQuery(fromjson(
         "{a: {$elemMatch: {b: {$elemMatch: {$gte: 1, $lte: 4}}}},"
@@ -4388,18 +4424,21 @@ TEST_F(QueryPlannerTest, ElemMatchInterectBoundsNotMultikey) {
 // from the $in predicate are not intersected with the bounds from the
 // remaining to predicates because the $in is not joined to the other
 // predicates with an $elemMatch.
-TEST_F(QueryPlannerTest, ElemMatchInterectBoundsMultikey) {
+TEST_F(QueryPlannerTest, ElemMatchIntersectBoundsMultikey) {
     // true means multikey
     addIndex(BSON("a.b" << 1), true);
     runQuery(fromjson(
         "{a: {$elemMatch: {b: {$elemMatch: {$gte: 1, $lte: 4}}}},"
         "'a.b': {$in: [2,5]}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {node: {ixscan: {pattern: {'a.b': 1}, bounds: "
         "{'a.b': [[1, 4, true, true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b': 1}, bounds: "
+        "{'a.b': [[2,2,true,true], [5,5,true,true]]}}}}}");
 }
 
 // Bounds can be intersected because the predicates are joined by an
@@ -4486,12 +4525,16 @@ TEST_F(QueryPlannerTest, MultikeySharedPrefixNoIntersectOutsideElemMatch) {
     addIndex(BSON("a.b" << 1 << "a.c" << 1), true);
     runQuery(fromjson("{'a.b': 1, a: {$elemMatch: {b: {$gt: 0}, c: 1}}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {node: {ixscan: {pattern: {'a.b':1,'a.c':1}, bounds: "
         "{'a.b': [[0,Infinity,false,true]], "
         " 'a.c': [[1,1,true,true]]}}}}}");
+     assertSolutionExists(
+         "{fetch: {node: {ixscan: {pattern: {'a.b':1,'a.c':1}, bounds: "
+         "{'a.b': [[1,1,true,true]], "
+         " 'a.c': [['MinKey','MaxKey',true,true]]}}}}}");
 }
 
 // Bounds for the predicates joined by the $elemMatch over the shared prefix
@@ -4502,12 +4545,16 @@ TEST_F(QueryPlannerTest, MultikeySharedPrefixNoIntersectOutsideElemMatch2) {
     addIndex(BSON("a.b" << 1 << "a.c" << 1), true);
     runQuery(fromjson("{a: {$elemMatch: {b: 1, c: 1}}, 'a.b': 1}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(3U);
     assertSolutionExists("{cscan: {dir: 1}}");
     assertSolutionExists(
         "{fetch: {node: {ixscan: {pattern: {'a.b':1,'a.c':1}, bounds: "
         "{'a.b': [[1,1,true,true]], "
         " 'a.c': [[1,1,true,true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {node: {ixscan: {pattern: {'a.b':1,'a.c':1}, bounds: "
+        "{'a.b': [[1,1,true,true]], "
+        " 'a.c': [['MinKey','MaxKey',true,true]]}}}}}");
 }
 
 // Bounds for the predicates joined by the $elemMatch over the shared prefix
@@ -5739,11 +5786,17 @@ TEST_F(QueryPlannerTest, CannotTrimIxisectParamSelfIntersection) {
 
     runQuery(fromjson("{a: {$all: [1, 2, 3]}}"));
 
-    assertNumSolutions(2U);
+    assertNumSolutions(4U);
     assertSolutionExists(
         "{fetch: {filter: {$and: [{a:2}, {a:3}]}, node: "
         "{ixscan: {filter: null, pattern: {a: 1}}}}}");
     assertSolutionExists(
+        "{fetch: {filter: {$and: [{a:1}, {a:3}]}, node: "
+        "{ixscan: {filter: null, pattern: {a: 1}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a:1}, {a:2}]}, node: "
+        "{ixscan: {filter: null, pattern: {a: 1}}}}}");
+    assertSolutionExists(
         "{fetch: {filter: null, node: {andSorted: {nodes: ["
         "{ixscan: {filter: null, pattern: {a:1},"
         "bounds: {a: [[1,1,true,true]]}}},"
@@ -5865,6 +5918,92 @@ TEST_F(QueryPlannerTest, CoveredOrUniqueIndexLookup) {
         "{ixscan: {filter: null, pattern: {a: 1, b: 1}}}}}");
 }
 
+// SERVER-16042
+TEST_F(QueryPlannerTest, MultikeyElemMatchAll) {
+    addIndex(BSON("a.b" << 1), true);
+    runQuery(fromjson("{a: {$all: [{$elemMatch: {b: {$gt: 1}}}, {$elemMatch: {b: {$lt: 0}}}]}}"));
+
+    assertNumSolutions(3U);
+    assertSolutionExists("{cscan: {dir: 1}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a:{$elemMatch:{b:{$lt:0}}}},{a:{$elemMatch:{b:{$gt:1}}}}]},"
+        "node: {ixscan: {pattern: {'a.b': 1}, filter: null,"
+        "bounds: {'a.b': [[-Infinity, 0, true, false]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a:{$elemMatch:{b:{$lt:0}}}},{a:{$elemMatch:{b:{$gt:1}}}}]},"
+        "node: {ixscan: {pattern: {'a.b': 1}, filter: null,"
+        "bounds: {'a.b': [[1, Infinity, false, true]]}}}}}");
+}
+
+// SERVER-16042
+TEST_F(QueryPlannerTest, MultikeyElemMatchAllCompound) {
+    addIndex(BSON("a.b" << 1 << "c" << 1), true);
+    runQuery(fromjson(
+        "{a: {$all: [{$elemMatch: {b: {$gt: 1}}}, "
+        "{$elemMatch: {b: {$lt: 0}}}]}, c: 3}"));
+
+    assertNumSolutions(3U);
+    assertSolutionExists("{cscan: {dir: 1}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a:{$elemMatch:{b:{$lt:0}}}},{a:{$elemMatch:{b:{$gt:1}}}}]},"
+        "node: {ixscan: {pattern: {'a.b': 1, c: 1}, filter: null,"
+        "bounds: {'a.b': [[-Infinity,0,true,false]], c: [[3,3,true,true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and: [{a:{$elemMatch:{b:{$lt:0}}}},{a:{$elemMatch:{b:{$gt:1}}}}]},"
+        "node: {ixscan: {pattern: {'a.b': 1, c: 1}, filter: null,"
+        "bounds: {'a.b': [[1,Infinity,false,true]], c: [[3,3,true,true]]}}}}}");
+}
+
+// SERVER-16042
+TEST_F(QueryPlannerTest, MultikeyElemMatchAllCompound2) {
+    addIndex(BSON("a.b" << 1 << "c" << 1), true);
+    runQuery(fromjson(
+        "{a: {$all: [{$elemMatch: {b: {$gt: 1}}}, "
+        "{$elemMatch: {b: {$lt: 0}}}]}, c: {$gte: 3, $lte: 4}}"));
+
+    assertNumSolutions(3U);
+    assertSolutionExists("{cscan: {dir: 1}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and:"
+        "[{a:{$elemMatch:{b:{$lt:0}}}},{a:{$elemMatch:{b:{$gt:1}}}},{c:{$gte:3}}]},"
+        "node: {ixscan: {pattern: {'a.b': 1, c: 1}, filter: null,"
+        "bounds: {'a.b': [[-Infinity,0,true,false]], c: [[-Infinity,4,true,true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: {$and:"
+        "[{a:{$elemMatch:{b:{$lt:0}}}},{a:{$elemMatch:{b:{$gt:1}}}},{c:{$gte:3}}]},"
+        "node: {ixscan: {pattern: {'a.b': 1, c: 1}, filter: null,"
+        "bounds: {'a.b': [[1,Infinity,false,true]], c: [[-Infinity,4,true,true]]}}}}}");
+}
+
+// SERVER-16042
+TEST_F(QueryPlannerTest, MultikeyElemMatchAllCompound3) {
+    addIndex(BSON("arr.k" << 1 << "arr.v" << 1), true);
+    runQuery(fromjson(
+        "{arr: {$all: ["
+        "{$elemMatch: {k: 1, v: 1}}, {$elemMatch: {k: 2, v: 2}}, {$elemMatch: {k: 3, v: 3}}]}}"));
+
+    assertNumSolutions(4U);
+    assertSolutionExists("{cscan: {dir: 1}}");
+    assertSolutionExists(
+        "{fetch: {filter: "
+        "{$and:[{arr:{$elemMatch:{k:1,v:1}}},"
+        "{arr:{$elemMatch:{k:2,v:2}}},{arr:{$elemMatch:{k:3,v:3}}}]},"
+        "node: {ixscan: {pattern: {'arr.k': 1, 'arr.v': 1}, filter: null, "
+        "bounds: {'arr.k': [[1,1,true,true]], 'arr.v': [[1,1,true,true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: "
+        "{$and:[{arr:{$elemMatch:{k:2,v:2}}},"
+        "{arr:{$elemMatch:{k:1,v:1}}},{arr:{$elemMatch:{k:3,v:3}}}]},"
+        "node: {ixscan: {pattern: {'arr.k': 1, 'arr.v': 1}, filter: null, "
+        "bounds: {'arr.k': [[2,2,true,true]], 'arr.v': [[2,2,true,true]]}}}}}");
+    assertSolutionExists(
+        "{fetch: {filter: "
+        "{$and:[{arr:{$elemMatch:{k:3,v:3}}},"
+        "{arr:{$elemMatch:{k:1,v:1}}},{arr:{$elemMatch:{k:2,v:2}}}]},"
+        "node: {ixscan: {pattern: {'arr.k': 1, 'arr.v': 1}, filter: null, "
+        "bounds: {'arr.k': [[3,3,true,true]], 'arr.v': [[3,3,true,true]]}}}}}");
+}
+
 //
 // Test bad input to query planner helpers.
 //