SERVER-13687 fix plan enumeration for compound multikey 2d or 2dsphere indices

4 files changed, 534 insertions, 80 deletions

diff --git a/jstests/core/multikey_geonear.js b/jstests/core/multikey_geonear.js
new file mode 100644
index 00000000000..7f5bbe3f75f
--- /dev/null
+++ b/jstests/core/multikey_geonear.js
@@ -0,0 +1,72 @@
+// Test that we correct return results for compound 2d and 2dsphere indices in
+// both the multikey and non-multikey cases.
+
+var t = db.jstests_multikey_geonear;
+t.drop();
+
+// Check that the result set from the cursor is the document with _id: 2,
+// followed by _id: 1, and _id: 0.
+function checkResults(cursor) {
+    for (var i = 2; i >= 0; i--) {
+        assert.eq(i, cursor.next()["_id"]);
+    }
+    assert(!cursor.hasNext());
+}
+
+t.ensureIndex({a: 1, b: "2dsphere"});
+
+t.insert({_id: 0, a: 0, b: {type: "Point", coordinates: [0, 0]}});
+t.insert({_id: 1, a: 0, b: {type: "Point", coordinates: [1, 1]}});
+t.insert({_id: 2, a: 0, b: {type: "Point", coordinates: [2, 2]}});
+
+// Ensure that the results are returned sorted by increasing distance.
+var cursor = t.find({a: {$gte: 0}, b: {$near: {$geometry: {type: "Point", coordinates: [2, 2]}}}});
+checkResults(cursor);
+
+// The results should be the same if we make the "a" field multikey.
+t.insert({_id: 3, a: ["multi", "key"], b: {type: "Point", coordinates: [-1, -1]}});
+cursor = t.find({a: {$gte: 0}, b: {$near: {$geometry: {type: "Point", coordinates: [2, 2]}}}});
+checkResults(cursor);
+
+// Repeat these tests for a 2d index.
+t.drop();
+t.ensureIndex({a: "2d", b: 1});
+t.insert({_id: 0, a: [0, 0], b: 0});
+t.insert({_id: 1, a: [1, 1], b: 1});
+t.insert({_id: 2, a: [2, 2], b: 2});
+
+cursor = t.find({a: {$near: [2, 2]}, b: {$gte: 0}});
+checkResults(cursor);
+
+t.insert({_id: 3, a: [-1, -1], b: ["multi", "key"]});
+cursor = t.find({a: {$near: [2, 2]}, b: {$gte: 0}});
+checkResults(cursor);
+
+// The fields in the compound 2dsphere index share a prefix.
+t.drop();
+t.ensureIndex({"a.b": 1, "a.c": "2dsphere"});
+t.insert({_id: 0, a: [{b: 0}, {c: {type: "Point", coordinates: [0, 0]}}]});
+t.insert({_id: 1, a: [{b: 1}, {c: {type: "Point", coordinates: [1, 1]}}]});
+t.insert({_id: 2, a: [{b: 2}, {c: {type: "Point", coordinates: [2, 2]}}]});
+
+cursor = t.find({"a.b": {$gte: 0}, "a.c": {$near:
+                    {$geometry: {type: "Point", coordinates: [2, 2]}}}});
+checkResults(cursor);
+
+// Double check that we're not intersecting bounds. Doing so should cause us to
+// miss the result here.
+t.insert({_id: 3, a: [{b: 10}, {b: -1}, {c: {type: "Point", coordinates: [0, 0]}}]});
+cursor = t.find({"a.b": {$lt: 0, $gt: 9}, "a.c": {$near:
+                    {$geometry: {type: "Point", coordinates: [0, 0]}}}});
+assert.eq(3, cursor.next()["_id"]);
+assert(!cursor.hasNext());
+
+// The fields in the compound 2d index share a prefix.
+t.drop();
+t.ensureIndex({"a.b": "2d", "a.c": 1});
+t.insert({_id: 0, a: [{b: [0, 0]}, {c: 0}]});
+t.insert({_id: 1, a: [{b: [1, 1]}, {c: 1}]});
+t.insert({_id: 2, a: [{b: [2, 2]}, {c: 2}]});
+
+cursor = t.find({"a.b": {$near: [2, 2]}, "a.c": {$gte: 0}});
+checkResults(cursor);
diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index 584dce000b7..c958dc3d3a2 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -51,7 +51,7 @@ namespace {
      * Returns true if either 'node' or a descendent of 'node'
      * is a predicate that is required to use an index.
      */
-    bool isIndexMandatory(const MatchExpression* node) {
+    bool expressionRequiresIndex(const MatchExpression* node) {
         return CanonicalQuery::countNodes(node, MatchExpression::GEO_NEAR) > 0
             || CanonicalQuery::countNodes(node, MatchExpression::TEXT) > 0;
     }
@@ -330,7 +330,14 @@ namespace mongo {
                 return false;
             }
 
-            // Indices we *must* use.  TEXT or GEO.
+            // There can only be one mandatory predicate (at most one $text, at most one
+            // $geoNear, can't combine $text/$geoNear).
+            MatchExpression* mandatoryPred = NULL;
+
+            // There could be multiple indices which we could use to satisfy the mandatory
+            // predicate. Keep the set of such indices. Currently only one text index is
+            // allowed per collection, but there could be multiple 2d or 2dsphere indices
+            // available to answer a $geoNear predicate.
             set<IndexID> mandatoryIndices;
 
             // Go through 'indexedPreds' and add the predicates to the
@@ -340,25 +347,36 @@ namespace mongo {
 
                 invariant(Indexability::nodeCanUseIndexOnOwnField(child));
 
-                bool childRequiresIndex = isIndexMandatory(child);
-
                 RelevantTag* rt = static_cast<RelevantTag*>(child->getTag());
 
+                if (expressionRequiresIndex(child)) {
+                    // 'child' is a predicate which *must* be tagged with an index.
+                    // This should include only TEXT and GEO_NEAR preds.
+
+                    // We expect either 0 or 1 mandatory predicates.
+                    invariant(NULL == mandatoryPred);
+
+                    // Mandatory predicates are TEXT or GEO_NEAR.
+                    invariant(MatchExpression::TEXT == child->matchType() ||
+                              MatchExpression::GEO_NEAR == child->matchType());
+
+                    // The mandatory predicate must have a corresponding "mandatory index".
+                    invariant(rt->first.size() != 0 || rt->notFirst.size() != 0);
+
+                    mandatoryPred = child;
+
+                    // Find all of the indices that could be used to satisfy the pred,
+                    // and add them to the 'mandatoryIndices' set.
+                    mandatoryIndices.insert(rt->first.begin(), rt->first.end());
+                    mandatoryIndices.insert(rt->notFirst.begin(), rt->notFirst.end());
+                }
+
                 for (size_t j = 0; j < rt->first.size(); ++j) {
                     idxToFirst[rt->first[j]].push_back(child);
-                    if (childRequiresIndex) {
-                        // We could have >1 index that could be used to answer the pred for
-                        // things like geoNear.  Just pick the first and make it mandatory.
-                        mandatoryIndices.insert(rt->first[j]);
-                    }
                 }
 
                 for (size_t j = 0 ; j< rt->notFirst.size(); ++j) {
                     idxToNotFirst[rt->notFirst[j]].push_back(child);
-                    if (childRequiresIndex) {
-                        // See comment above about mandatory indices.
-                        mandatoryIndices.insert(rt->notFirst[j]);
-                    }
                 }
             }
 
@@ -387,63 +405,141 @@ namespace mongo {
                 return true;
             }
 
-            // Only near queries and text queries have mandatory indices.
-            // In this case there's no point to enumerating anything here; both geoNear
-            // and text do fetches internally so we can't use any other indices in conjunction.
-            if (mandatoryIndices.size() > 0) {
-                // Just use the first mandatory index, why not.
-                IndexToPredMap::iterator it = idxToFirst.find(*mandatoryIndices.begin());
+            if (NULL != mandatoryPred) {
+                // We must have at least one index which can be used to answer 'mandatoryPred'.
+                invariant(!mandatoryIndices.empty());
+                enumerateMandatoryIndex(idxToFirst, idxToNotFirst, mandatoryPred,
+                                        mandatoryIndices, andAssignment);
+                return true;
+            }
+
+            enumerateOneIndex(idxToFirst, idxToNotFirst, subnodes, andAssignment);
+
+            if (_ixisect) {
+                enumerateAndIntersect(idxToFirst, idxToNotFirst, subnodes, andAssignment);
+            }
+
+            return true;
+        }
+
+        // Don't know what the node is at this point.
+        return false;
+    }
 
-                OneIndexAssignment indexAssign;
+    void PlanEnumerator::enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
+                                                 const IndexToPredMap& idxToNotFirst,
+                                                 MatchExpression* mandatoryPred,
+                                                 const set<IndexID>& mandatoryIndices,
+                                                 AndAssignment* andAssignment) {
+        // Generate index assignments for each index in 'mandatoryIndices'. We
+        // must assign 'mandatoryPred' to one of these indices, but we try all
+        // possibilities in 'mandatoryIndices' because some might be better than
+        // others for this query.
+        for (set<IndexID>::const_iterator indexIt = mandatoryIndices.begin();
+                indexIt != mandatoryIndices.end();
+                ++indexIt) {
+
+            // We have a predicate which *must* be tagged to use an index.
+            // Get the index entry for the index it should use.
+            const IndexEntry& thisIndex = (*_indices)[*indexIt];
+
+            // Only text, 2d, and 2dsphere index types should be able to satisfy
+            // mandatory predicates.
+            invariant(INDEX_TEXT == thisIndex.type ||
+                      INDEX_2D == thisIndex.type ||
+                      INDEX_2DSPHERE == thisIndex.type);
 
-                // This is the index we assign to.
-                indexAssign.index = it->first;
+            OneIndexAssignment indexAssign;
+            indexAssign.index = *indexIt;
 
-                const IndexEntry& thisIndex = (*_indices)[it->first];
+            IndexToPredMap::const_iterator it = idxToFirst.find(*indexIt);
+            const vector<MatchExpression*>& predsOverLeadingField = it->second;
 
-                // 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?  (How do we get covering for them?)
-                if (thisIndex.multikey && (INDEX_TEXT != thisIndex.type)) {
-                    indexAssign.preds.push_back(it->second[0]);
+            if (thisIndex.multikey) {
+                // Special handling for multikey mandatory indices.
+                if (predsOverLeadingField.end() != std::find(predsOverLeadingField.begin(),
+                                                             predsOverLeadingField.end(),
+                                                             mandatoryPred)) {
+                    // The mandatory predicate is over the first field of the index. Assign
+                    // it now.
+                    indexAssign.preds.push_back(mandatoryPred);
                     indexAssign.positions.push_back(0);
                 }
                 else {
-                    // The index isn't multikey.  Assign all preds to it.  The planner will
-                    // do something smart with the bounds.
-                    indexAssign.preds = it->second;
+                    // The mandatory pred is notFirst. Assign an arbitrary predicate
+                    // over the first position.
+                    invariant(!predsOverLeadingField.empty());
+                    indexAssign.preds.push_back(predsOverLeadingField[0]);
+                    indexAssign.positions.push_back(0);
 
-                    // 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);
+                    // Assign the mandatory predicate at the matching position in the compound
+                    // index. We do this in order to ensure that the mandatory predicate (and not
+                    // some other predicate over the same position in the compound index) gets
+                    // assigned.
+                    //
+                    // The bad thing that could happen otherwise: A non-mandatory predicate gets
+                    // chosen by getMultikeyCompoundablePreds(...) instead of 'mandatoryPred'.
+                    // We would then fail to assign the mandatory predicate, and hence generate
+                    // a bad data access plan.
+                    //
+                    // The mandatory predicate is assigned by calling compound(...) because
+                    // compound(...) has logic for matching up a predicate with the proper
+                    // position in the compound index.
+                    vector<MatchExpression*> mandatoryToCompound;
+                    mandatoryToCompound.push_back(mandatoryPred);
+                    compound(mandatoryToCompound, thisIndex, &indexAssign);
+
+                    // At this point we have assigned a predicate over the leading field and
+                    // we have assigned the mandatory predicate to a trailing field.
+                    //
+                    // Ex:
+                    //   Say we have index {a: 1, b: 1, c: "2dsphere", d: 1}. Also suppose that
+                    //   there is a $near predicate over "c", with additional predicates over
+                    //   "a", "b", "c", and "d". We will have assigned the $near predicate at
+                    //   position 2 and a predicate with path "a" at position 0.
+                }
 
-                    // And now we begin compound analysis.
+                // Compound remaining predicates in a multikey-safe way.
+                IndexToPredMap::const_iterator compIt = idxToNotFirst.find(indexAssign.index);
+                if (compIt != idxToNotFirst.end()) {
+                    const vector<MatchExpression*>& couldCompound = compIt->second;
+                    vector<MatchExpression*> tryCompound;
 
-                    // Find everything that could use assign.index but isn't a pred over
-                    // the first field of that index.
-                    IndexToPredMap::iterator compIt = idxToNotFirst.find(indexAssign.index);
-                    if (compIt != idxToNotFirst.end()) {
-                        compound(compIt->second, thisIndex, &indexAssign);
+                    getMultikeyCompoundablePreds(indexAssign.preds, couldCompound, &tryCompound);
+                    if (tryCompound.size()) {
+                        compound(tryCompound, thisIndex, &indexAssign);
                     }
                 }
-
-                AndEnumerableState state;
-                state.assignments.push_back(indexAssign);
-                andAssignment->choices.push_back(state);
-                return true;
             }
+            else {
+                // For non-multikey, we don't have to do anything too special.
+                // Just assign all "first" predicates and try to compound like usual.
+                indexAssign.preds = it->second;
 
-            enumerateOneIndex(idxToFirst, idxToNotFirst, subnodes, andAssignment);
+                // 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);
 
-            if (_ixisect) {
-                enumerateAndIntersect(idxToFirst, idxToNotFirst, subnodes, andAssignment);
+                // And now we begin compound analysis.
+
+                // 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);
+                }
             }
 
-            return true;
-        }
+            // The mandatory predicate must be assigned.
+            invariant(indexAssign.preds.end() != std::find(indexAssign.preds.begin(),
+                                                           indexAssign.preds.end(),
+                                                           mandatoryPred));
 
-        // Don't know what the node is at this point.
-        return false;
+            // Output the assignments for this index.
+            AndEnumerableState state;
+            state.assignments.push_back(indexAssign);
+            andAssignment->choices.push_back(state);
+        }
     }
 
     void PlanEnumerator::enumerateOneIndex(const IndexToPredMap& idxToFirst,
@@ -514,7 +610,7 @@ namespace mongo {
 
                     // ...select the predicates that are safe to compound and try to
                     // compound them.
-                    getMultikeyCompoundablePreds(indexAssign.preds[0], couldCompound, &tryCompound);
+                    getMultikeyCompoundablePreds(indexAssign.preds, couldCompound, &tryCompound);
                     if (tryCompound.size()) {
                         compound(tryCompound, thisIndex, &indexAssign);
                     }
@@ -844,7 +940,7 @@ namespace mongo {
                 partitionPreds(child, context, indexOut, subnodesOut, mandatorySubnodes);
             }
             else {
-                bool mandatory = isIndexMandatory(child);
+                bool mandatory = expressionRequiresIndex(child);
 
                 // Recursively prepMemo for the subnode. We fall through
                 // to this case for logical nodes other than AND (e.g. OR)
@@ -872,7 +968,7 @@ namespace mongo {
         return true;
     }
 
-    void PlanEnumerator::getMultikeyCompoundablePreds(const MatchExpression* assigned,
+    void PlanEnumerator::getMultikeyCompoundablePreds(const vector<MatchExpression*>& assigned,
                                                       const vector<MatchExpression*>& couldCompound,
                                                       vector<MatchExpression*>* out) {
         // Map from a particular $elemMatch expression to the set of prefixes
@@ -887,28 +983,31 @@ namespace mongo {
         // of the used prefixes both inside and outside of an $elemMatch context.
         unordered_map<MatchExpression*, set<string> > used;
 
-        // Initialize 'used' with the starting predicate, 'assigned'. Begin by
+        // Initialize 'used' with the starting predicates in 'assigned'. Begin by
         // initializing the top-level scope with the prefix of the full path.
-        invariant(NULL != assigned->getTag());
-        RelevantTag* usedRt = static_cast<RelevantTag*>(assigned->getTag());
-        set<string> usedPrefixes;
-        usedPrefixes.insert(getPathPrefix(usedRt->path));
-        used[NULL] = usedPrefixes;
-
-        // If 'assigned' is a predicate inside an $elemMatch, we have to
-        // add the prefix not only to the top-level context, but also to the
-        // the $elemMatch context. For example, if 'assigned' is {a: {$elemMatch: {b: 1}}},
-        // then we will have already added "a" to the set for NULL. We now
-        // also need to add "b" to the set for the $elemMatch.
-        if (NULL != usedRt->elemMatchExpr) {
-            set<string> elemMatchUsed;
-            // Whereas getPathPrefix(usedRt->path) is the prefix of the full path,
-            // usedRt->pathPrefix contains the prefix of the portion of the
-            // path that is inside the $elemMatch. These two prefixes are the same
-            // in the top-level context, but here must be different because 'usedRt'
-            // is in an $elemMatch context.
-            elemMatchUsed.insert(usedRt->pathPrefix);
-            used[usedRt->elemMatchExpr] = elemMatchUsed;
+        for (size_t i = 0; i < assigned.size(); i++) {
+            const MatchExpression* assignedPred = assigned[i];
+            invariant(NULL != assignedPred->getTag());
+            RelevantTag* usedRt = static_cast<RelevantTag*>(assignedPred->getTag());
+            set<string> usedPrefixes;
+            usedPrefixes.insert(getPathPrefix(usedRt->path));
+            used[NULL] = usedPrefixes;
+
+            // If 'assigned' is a predicate inside an $elemMatch, we have to
+            // add the prefix not only to the top-level context, but also to the
+            // the $elemMatch context. For example, if 'assigned' is {a: {$elemMatch: {b: 1}}},
+            // then we will have already added "a" to the set for NULL. We now
+            // also need to add "b" to the set for the $elemMatch.
+            if (NULL != usedRt->elemMatchExpr) {
+                set<string> elemMatchUsed;
+                // Whereas getPathPrefix(usedRt->path) is the prefix of the full path,
+                // usedRt->pathPrefix contains the prefix of the portion of the
+                // path that is inside the $elemMatch. These two prefixes are the same
+                // in the top-level context, but here must be different because 'usedRt'
+                // is in an $elemMatch context.
+                elemMatchUsed.insert(usedRt->pathPrefix);
+                used[usedRt->elemMatchExpr] = elemMatchUsed;
+            }
         }
 
         for (size_t i = 0; i < couldCompound.size(); ++i) {
diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h
index 65fb9d7b290..8cccbab61c8 100644
--- a/src/mongo/db/query/plan_enumerator.h
+++ b/src/mongo/db/query/plan_enumerator.h
@@ -273,9 +273,9 @@ namespace mongo {
                             vector<MemoID>* mandatorySubnodes);
 
         /**
-         * Finds a set of predicates that can be safely compounded with 'assigned',
-         * under the assumption that we are assignining predicates to a compound,
-         * multikey index.
+         * Finds a set of predicates that can be safely compounded with the set
+         * of predicates in 'assigned', under the assumption that we are assigning
+         * predicates to a compound, multikey index.
          *
          * The list of candidate predicates that we could compound is passed
          * in 'couldCompound'. A subset of these predicates that is safe to
@@ -313,8 +313,28 @@ namespace mongo {
          *    2) {'a.b': 1, a: {$elemMatch: {b: {$gt: 0}}}}. We cannot combine the
          *    bounds here because the prefix 'a' is shared by two predicates which
          *    are not joined together by an $elemMatch.
+         *
+         * NOTE:
+         *   Usually 'assigned' has just one predicate. However, in order to support
+         *   mandatory predicate assignment (TEXT and GEO_NEAR), we allow multiple
+         *   already-assigned predicates to be passed. If a mandatory predicate is over
+         *   a trailing field in a multikey compound index, then we assign both a predicate
+         *   over the leading field as well as the mandatory predicate prior to calling
+         *   this function.
+         *
+         *   Ex:
+         *      Say we have index {a: 1, b: 1, c: "2dsphere", d: 1} as well as a $near
+         *      predicate and a $within predicate over "c". The $near predicate is mandatory
+         *      and must be assigned. The $within predicate is not mandatory. Furthermore,
+         *      it cannot be assigned in addition to the $near predicate because the index
+         *      is multikey.
+         *
+         *      In this case the enumerator must assign the $near predicate, and pass it in
+         *      in 'assigned'. Otherwise it would be possible to assign the $within predicate,
+         *      and then not assign the $near because the $within is already assigned (and
+         *      has the same path).
          */
-        void getMultikeyCompoundablePreds(const MatchExpression* assigned,
+        void getMultikeyCompoundablePreds(const vector<MatchExpression*>& assigned,
                                           const vector<MatchExpression*>& couldCompound,
                                           vector<MatchExpression*>* out);
 
@@ -365,6 +385,17 @@ namespace mongo {
                                AndAssignment* andAssignment);
 
         /**
+         * Generate single-index assignments for queries which contain mandatory
+         * predicates (TEXT and GEO_NEAR, which are required to use a compatible index).
+         * Outputs these assignments into 'andAssignment'.
+         */
+        void enumerateMandatoryIndex(const IndexToPredMap& idxToFirst,
+                                     const IndexToPredMap& idxToNotFirst,
+                                     MatchExpression* mandatoryPred,
+                                     const set<IndexID>& mandatoryIndices,
+                                     AndAssignment* andAssignment);
+
+        /**
          * Try to assign predicates in 'tryCompound' to 'thisIndex' as compound assignments.
          * Output the assignments in 'assign'.
          */
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 58550e88a1f..d56efe11051 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1464,6 +1464,18 @@ namespace {
         assertSolutionExists("{fetch: {node: {geoNear2dsphere: {loc: '2dsphere'}}}}");
     }
 
+    TEST_F(QueryPlannerTest, Multikey2DSphereCompound) {
+        // true means multikey
+        addIndex(BSON("a" << 1 << "b" << 1), true);
+        addIndex(BSON("loc" << "2dsphere"), true);
+
+        runQuery(fromjson("{loc:{$near:{$geometry:{type:'Point',"
+                                                  "coordinates : [-81.513743,28.369947] },"
+                               " $maxDistance :100}},a: 'mouse'}"));
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {node: {geoNear2dsphere: {loc: '2dsphere'}}}}");
+    }
+
     TEST_F(QueryPlannerTest, Basic2DSphereNonNear) {
         // 2dsphere can do: within+geometry, intersects+geometry
         addIndex(BSON("a" << "2dsphere"));
@@ -1482,6 +1494,25 @@ namespace {
         // TODO: test that we *don't* annotate for things we shouldn't.
     }
 
+    TEST_F(QueryPlannerTest, Multikey2DSphereNonNear) {
+        // 2dsphere can do: within+geometry, intersects+geometry
+        // true means multikey
+        addIndex(BSON("a" << "2dsphere"), true);
+
+        runQuery(fromjson("{a: {$geoIntersects: {$geometry: {type: 'Point',"
+                                                           "coordinates: [10.0, 10.0]}}}}"));
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}}");
+
+        runQuery(fromjson("{a : { $geoWithin : { $centerSphere : [[ 10, 20 ], 0.01 ] } }}"));
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}}");
+
+        // TODO: test that we *don't* annotate for things we shouldn't.
+    }
+
     TEST_F(QueryPlannerTest, Basic2DGeoNear) {
         // Can only do near + old point.
         addIndex(BSON("a" << "2d"));
@@ -1504,6 +1535,21 @@ namespace {
         assertSolutionExists("{geoNear2dsphere: {a: '2dsphere'}}");
     }
 
+    TEST_F(QueryPlannerTest, Multikey2DSphereGeoNear) {
+        // Can do nearSphere + old point, near + new point.
+        // true means multikey
+        addIndex(BSON("a" << "2dsphere"), true);
+
+        runQuery(fromjson("{a: {$nearSphere: [0,0], $maxDistance: 0.31 }}"));
+        ASSERT_EQUALS(getNumSolutions(), 1U);
+        assertSolutionExists("{geoNear2dsphere: {a: '2dsphere'}}");
+
+        runQuery(fromjson("{a: {$geoNear: {$geometry: {type: 'Point', coordinates: [0,0]},"
+                                          "$maxDistance:100}}}"));
+        assertNumSolutions(1U);
+        assertSolutionExists("{geoNear2dsphere: {a: '2dsphere'}}");
+    }
+
     TEST_F(QueryPlannerTest, Basic2DSphereGeoNearReverseCompound) {
         addIndex(BSON("x" << 1));
         addIndex(BSON("x" << 1 << "a" << "2dsphere"));
@@ -1513,6 +1559,15 @@ namespace {
         assertSolutionExists("{geoNear2dsphere: {x: 1, a: '2dsphere'}}");
     }
 
+    TEST_F(QueryPlannerTest, Multikey2DSphereGeoNearReverseCompound) {
+        addIndex(BSON("x" << 1), true);
+        addIndex(BSON("x" << 1 << "a" << "2dsphere"), true);
+        runQuery(fromjson("{x:1, a: {$nearSphere: [0,0], $maxDistance: 0.31 }}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{geoNear2dsphere: {x: 1, a: '2dsphere'}}");
+    }
+
     TEST_F(QueryPlannerTest, NearNoIndex) {
         addIndex(BSON("x" << 1));
         runInvalidQuery(fromjson("{x:1, a: {$nearSphere: [0,0], $maxDistance: 0.31 }}"));
@@ -1527,6 +1582,15 @@ namespace {
         assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1, a: '2dsphere'}}}}}");
     }
 
+    TEST_F(QueryPlannerTest, TwoDSphereNoGeoPredMultikey) {
+        addIndex(BSON("x" << 1 << "a" << "2dsphere"), true);
+        runQuery(fromjson("{x:1}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1, a: '2dsphere'}}}}}");
+    }
+
     // SERVER-3984, $or 2d index
     TEST_F(QueryPlannerTest, Or2DNonNear) {
         addIndex(BSON("a" << "2d"));
@@ -1563,6 +1627,22 @@ namespace {
                                            "{fetch: {node: {ixscan: {pattern: {b: '2dsphere'}}}}}]}}");
     }
 
+    // SERVER-3984, $or 2dsphere index
+    TEST_F(QueryPlannerTest, Or2DSphereNonNearMultikey) {
+        // true means multikey
+        addIndex(BSON("a" << "2dsphere"), true);
+        addIndex(BSON("b" << "2dsphere"), true);
+        runQuery(fromjson("{$or: [ {a: {$geoIntersects: {$geometry: "
+                                        "{type: 'Point', coordinates: [10.0, 10.0]}}}},"
+                                 " {b: {$geoWithin: { $centerSphere: [[ 10, 20 ], 0.01 ] } }} ]}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{or: {nodes: "
+                                "[{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}},"
+                                "{fetch: {node: {ixscan: {pattern: {b: '2dsphere'}}}}}]}}");
+    }
+
     TEST_F(QueryPlannerTest, And2DSameFieldNonNear) {
         addIndex(BSON("a" << "2d"));
         runQuery(fromjson("{$and: [ {a : { $within : { $polygon : [[0,0], [2,0], [4,0]] } }},"
@@ -1598,6 +1678,21 @@ namespace {
         assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}}");
     }
 
+    TEST_F(QueryPlannerTest, And2DSphereSameFieldNonNearMultikey) {
+        // true means multikey
+        addIndex(BSON("a" << "2dsphere"), true);
+        runQuery(fromjson("{$and: [ {a: {$geoIntersects: {$geometry: "
+                                        "{type: 'Point', coordinates: [3.0, 1.0]}}}},"
+                                 "  {a: {$geoIntersects: {$geometry: "
+                                        "{type: 'Point', coordinates: [4.0, 1.0]}}}}]}"));
+
+        assertNumSolutions(2U);
+        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'}}}}}");
+    }
+
     TEST_F(QueryPlannerTest, And2DSphereWithNearSameField) {
         addIndex(BSON("a" << "2dsphere"));
         runQuery(fromjson("{$and: [{a: {$geoIntersects: {$geometry: "
@@ -1610,6 +1705,19 @@ namespace {
         assertSolutionExists("{fetch: {node: {geoNear2dsphere: {a: '2dsphere'}}}}");
     }
 
+    TEST_F(QueryPlannerTest, And2DSphereWithNearSameFieldMultikey) {
+        // true means multikey
+        addIndex(BSON("a" << "2dsphere"), true);
+        runQuery(fromjson("{$and: [{a: {$geoIntersects: {$geometry: "
+                                        "{type: 'Point', coordinates: [3.0, 1.0]}}}},"
+                                  "{a: {$near: {$geometry: "
+                                        "{type: 'Point', coordinates: [10.0, 10.0]}}}}]}"));
+
+        // GEO_NEAR must use the index, and GEO predicate becomes a filter.
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {node: {geoNear2dsphere: {a: '2dsphere'}}}}");
+    }
+
     TEST_F(QueryPlannerTest, Or2DSphereSameFieldNonNear) {
         addIndex(BSON("a" << "2dsphere"));
         runQuery(fromjson("{$or: [ {a: {$geoIntersects: {$geometry: "
@@ -1624,6 +1732,99 @@ namespace {
                                 "{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}}]}}");
     }
 
+    TEST_F(QueryPlannerTest, Or2DSphereSameFieldNonNearMultikey) {
+        // true means multikey
+        addIndex(BSON("a" << "2dsphere"), true);
+        runQuery(fromjson("{$or: [ {a: {$geoIntersects: {$geometry: "
+                                      "{type: 'Point', coordinates: [3.0, 1.0]}}}},"
+                                 "  {a: {$geoIntersects: {$geometry: "
+                                      "{type: 'Point', coordinates: [4.0, 1.0]}}}}]}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{or: {nodes: ["
+                                "{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}},"
+                                "{fetch: {node: {ixscan: {pattern: {a: '2dsphere'}}}}}]}}");
+    }
+
+    TEST_F(QueryPlannerTest, CompoundMultikey2DSphereNear) {
+        // true means multikey
+        addIndex(BSON("a" << 1 << "b" << "2dsphere"), true);
+        runQuery(fromjson("{a: {$gte: 0}, b: {$near: {$geometry: "
+                                             "{type: 'Point', coordinates: [2, 2]}}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{geoNear2dsphere: {a: 1, b: '2dsphere'}}");
+    }
+
+    TEST_F(QueryPlannerTest, CompoundMultikey2DSphereNearFetchRequired) {
+        // true means multikey
+        addIndex(BSON("a" << 1 << "b" << "2dsphere"), true);
+        runQuery(fromjson("{a: {$gte: 0, $lt: 5}, b: {$near: {$geometry: "
+                                                     "{type: 'Point', coordinates: [2, 2]}}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: {a:{$gte:0}}, node: "
+                                "{geoNear2dsphere: {a: 1, b: '2dsphere'}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CompoundMultikey2DSphereNearMultipleIndices) {
+        // true means multikey
+        addIndex(BSON("a" << 1 << "b" << "2dsphere"), true);
+        addIndex(BSON("c" << 1 << "b" << "2dsphere"), true);
+        runQuery(fromjson("{a: {$gte: 0}, c: 3, b: {$near: {$geometry: "
+                                                     "{type: 'Point', coordinates: [2, 2]}}}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{fetch: {filter: {c:3}, node: "
+                                "{geoNear2dsphere: {a: 1, b: '2dsphere'}}}}");
+        assertSolutionExists("{fetch: {filter: {a:{$gte:0}}, node: "
+                                "{geoNear2dsphere: {c: 1, b: '2dsphere'}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CompoundMultikey2DSphereNearMultipleLeadingFields) {
+        // true means multikey
+        addIndex(BSON("a" << 1 << "b" << 1 << "c" << "2dsphere"), true);
+        runQuery(fromjson("{a: {$lt: 5, $gt: 1}, b: 6, c: {$near: {$geometry: "
+                            "{type: 'Point', coordinates: [2, 2]}}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: {a:{$gt:1}}, node: "
+                                "{geoNear2dsphere: {a: 1, b: 1, c: '2dsphere'}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CompoundMultikey2DSphereNearMultipleGeoPreds) {
+        // true means multikey
+        addIndex(BSON("a" << 1 << "b" << 1 << "c" << "2dsphere"), true);
+        runQuery(fromjson("{a: 1, b: 6, $and: ["
+                            "{c: {$near: {$geometry: {type: 'Point', coordinates: [2, 2]}}}},"
+                            "{c: {$geoWithin: {$box: [ [1, 1], [3, 3] ] } } } ] }"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {node: {geoNear2dsphere: {a:1, b:1, c:'2dsphere'}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CompoundMultikey2DSphereNearCompoundTest) {
+        // true means multikey
+        addIndex(BSON("a" << 1 << "b" << "2dsphere" << "c" << 1 << "d" << 1), true);
+        runQuery(fromjson("{a: {$gte: 0}, c: {$gte: 0, $lt: 4}, d: {$gt: 1, $lt: 5},"
+                               "b: {$near: {$geometry: "
+                                    "{type: 'Point', coordinates: [2, 2]}}}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: {d:{$gt:1},c:{$gte:0}}, node: "
+                                "{geoNear2dsphere: {a: 1, b: '2dsphere', c: 1, d: 1}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CompoundMultikey2DNear) {
+        // true means multikey
+        addIndex(BSON("a" << "2d" << "b" << 1), true);
+        runQuery(fromjson("{a: {$near: [0, 0]}, b: {$gte: 0}}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{geoNear2d: {a: '2d', b: 1}}");
+    }
+
     //
     // $in
     //
@@ -1897,6 +2098,22 @@ namespace {
         assertSolutionExists("{fetch: {node: {ixscan: {pattern: {timestamp: -1, position: '2dsphere'}}}}}");
     }
 
+    // SERVER-10801
+    TEST_F(QueryPlannerTest, SortOnGeoQueryMultikey) {
+        // true means multikey
+        addIndex(BSON("timestamp" << -1 << "position" << "2dsphere"), true);
+        BSONObj query = fromjson("{position: {$geoWithin: {$geometry: {type: \"Polygon\", "
+            "coordinates: [[[1, 1], [1, 90], [180, 90], [180, 1], [1, 1]]]}}}}");
+        BSONObj sort = fromjson("{timestamp: -1}");
+        runQuerySortProj(query, sort, BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+        assertSolutionExists("{sort: {pattern: {timestamp: -1}, limit: 0, "
+                                "node: {cscan: {dir: 1}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: "
+                                "{timestamp: -1, position: '2dsphere'}}}}}");
+    }
+
     // SERVER-9257
     TEST_F(QueryPlannerTest, CompoundGeoNoGeoPredicate) {
         addIndex(BSON("creationDate" << 1 << "foo.bar" << "2dsphere"));
@@ -1909,6 +2126,19 @@ namespace {
         assertSolutionExists("{fetch: {node: {ixscan: {pattern: {creationDate: 1, 'foo.bar': '2dsphere'}}}}}");
     }
 
+    // SERVER-9257
+    TEST_F(QueryPlannerTest, CompoundGeoNoGeoPredicateMultikey) {
+        // true means multikey
+        addIndex(BSON("creationDate" << 1 << "foo.bar" << "2dsphere"), true);
+        runQuerySortProj(fromjson("{creationDate: { $gt: 7}}"),
+                         fromjson("{creationDate: 1}"), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+        assertSolutionExists("{sort: {pattern: {creationDate: 1}, limit: 0, "
+                                "node: {cscan: {dir: 1}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {pattern: {creationDate: 1, 'foo.bar': '2dsphere'}}}}}");
+    }
+
     // Basic "keep sort in mind with an OR"
     TEST_F(QueryPlannerTest, MergeSortEvenIfSameIndex) {
         addIndex(BSON("a" << 1 << "b" << 1));
@@ -2485,6 +2715,28 @@ namespace {
     }
 
     //
+    // 2DSphere geo negation
+    // Filter is embedded in a separate fetch node.
+    //
+    TEST_F(QueryPlannerTest, Negation2DSphereGeoNearMultikey) {
+        // Can do nearSphere + old point, near + new point.
+        // true means multikey
+        addIndex(BSON("a" << "2dsphere"), true);
+
+        runQuery(fromjson("{$and: [{a: {$nearSphere: [0,0], $maxDistance: 0.31}}, "
+                          "{b: {$ne: 1}}]}"));
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {node: {geoNear2dsphere: {a: '2dsphere'}}}}");
+
+        runQuery(fromjson("{$and: [{a: {$geoNear: {$geometry: {type: 'Point', "
+                                                              "coordinates: [0, 0]},"
+                                                  "$maxDistance: 100}}},"
+                                  "{b: {$ne: 1}}]}"));
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {node: {geoNear2dsphere: {a: '2dsphere'}}}}");
+    }
+
+    //
     // Multikey indices
     //