SERVER-17659 Move CQ::getPlanCacheKey() => PlanCache::computeKey()

Includes partial revert of e5f17aaf.  In particular, CanonicalQuery
objects no longer pre-generate their PlanCacheKey.

12 files changed, 433 insertions, 447 deletions

diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index 786de245ca9..dfd4733631a 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -25,6 +25,7 @@ env.Library(
         "index_bounds",
         "lite_parsed_query",
         "$BUILD_DIR/mongo/bson",
+        "$BUILD_DIR/mongo/expression_algo",
         "$BUILD_DIR/mongo/expressions",
         "$BUILD_DIR/mongo/expressions_text",
         "$BUILD_DIR/mongo/index_names",
@@ -48,7 +49,6 @@ env.Library(
         "internal_plans",
         "query_planner",
         "query_planner_test_lib",
-        "$BUILD_DIR/mongo/expression_algo",
         "$BUILD_DIR/mongo/db/exec/exec"
     ],
 )
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 315e7fe87d5..c4124b8acab 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -31,50 +31,13 @@
 #include "mongo/db/query/canonical_query.h"
 
 #include "mongo/db/jsobj.h"
-#include "mongo/db/matcher/expression_array.h"
-#include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/query/query_planner_common.h"
 #include "mongo/util/log.h"
 
 
+namespace mongo {
 namespace {
 
-    using boost::shared_ptr;
-    using std::auto_ptr;
-    using std::string;
-    using namespace mongo;
-
-    // Delimiters for cache key encoding.
-    const char kEncodeChildrenBegin = '[';
-    const char kEncodeChildrenEnd = ']';
-    const char kEncodeChildrenSeparator = ',';
-    const char kEncodeSortSection = '~';
-    const char kEncodeProjectionSection = '|';
-
-    /**
-     * Encode user-provided string. Cache key delimiters seen in the
-     * user string are escaped with a backslash.
-     */
-    void encodeUserString(StringData s, mongoutils::str::stream* os) {
-        for (size_t i = 0; i < s.size(); ++i) {
-            char c = s[i];
-            switch (c) {
-            case kEncodeChildrenBegin:
-            case kEncodeChildrenEnd:
-            case kEncodeChildrenSeparator:
-            case kEncodeSortSection:
-            case kEncodeProjectionSection:
-            case '\\':
-                  *os << '\\';
-                // Fall through to default case.
-            default:
-                *os << c;
-            }
-        }
-    }
-
-    void encodePlanCacheKeyTree(const MatchExpression* tree, mongoutils::str::stream* os);
-
     /**
      * Comparator for MatchExpression nodes.  Returns an integer less than, equal to, or greater
      * than zero if 'lhs' is less than, equal to, or greater than 'rhs', respectively.
@@ -129,221 +92,14 @@ namespace {
         return matchExpressionComparator(lhs, rhs) < 0;
     }
 
-    /**
-     * 2-character encoding of MatchExpression::MatchType.
-     */
-    const char* encodeMatchType(MatchExpression::MatchType mt) {
-        switch(mt) {
-        case MatchExpression::AND: return "an"; break;
-        case MatchExpression::OR: return "or"; break;
-        case MatchExpression::NOR: return "nr"; break;
-        case MatchExpression::NOT: return "nt"; break;
-        case MatchExpression::ELEM_MATCH_OBJECT: return "eo"; break;
-        case MatchExpression::ELEM_MATCH_VALUE: return "ev"; break;
-        case MatchExpression::SIZE: return "sz"; break;
-        case MatchExpression::LTE: return "le"; break;
-        case MatchExpression::LT: return "lt"; break;
-        case MatchExpression::EQ: return "eq"; break;
-        case MatchExpression::GT: return "gt"; break;
-        case MatchExpression::GTE: return "ge"; break;
-        case MatchExpression::REGEX: return "re"; break;
-        case MatchExpression::MOD: return "mo"; break;
-        case MatchExpression::EXISTS: return "ex"; break;
-        case MatchExpression::MATCH_IN: return "in"; break;
-        case MatchExpression::NIN: return "ni"; break;
-        case MatchExpression::TYPE_OPERATOR: return "ty"; break;
-        case MatchExpression::GEO: return "go"; break;
-        case MatchExpression::WHERE: return "wh"; break;
-        case MatchExpression::ATOMIC: return "at"; break;
-        case MatchExpression::ALWAYS_FALSE: return "af"; break;
-        case MatchExpression::GEO_NEAR: return "gn"; break;
-        case MatchExpression::TEXT: return "te"; break;
-        default: verify(0); return "";
-        }
-    }
-
-    /**
-     * Encodes GEO match expression.
-     * Encoding includes:
-     * - type of geo query (within/intersect/near)
-     * - geometry type
-     * - CRS (flat or spherical)
-     */
-    void encodeGeoMatchExpression(const GeoMatchExpression* tree, mongoutils::str::stream* os) {
-        const GeoExpression& geoQuery = tree->getGeoExpression();
-
-        // Type of geo query.
-        switch (geoQuery.getPred()) {
-        case GeoExpression::WITHIN: *os << "wi"; break;
-        case GeoExpression::INTERSECT: *os << "in"; break;
-        case GeoExpression::INVALID: *os << "id"; break;
-        }
-
-        // Geometry type.
-        // Only one of the shared_ptrs in GeoContainer may be non-NULL.
-        *os << geoQuery.getGeometry().getDebugType();
-
-        // CRS (flat or spherical)
-        if (FLAT == geoQuery.getGeometry().getNativeCRS()) {
-            *os << "fl";
-        }
-        else if (SPHERE == geoQuery.getGeometry().getNativeCRS()) {
-            *os << "sp";
-        }
-        else if (STRICT_SPHERE == geoQuery.getGeometry().getNativeCRS()) {
-            *os << "ss";
-        }
-        else {
-            error() << "unknown CRS type " << (int)geoQuery.getGeometry().getNativeCRS()
-                    << " in geometry of type " << geoQuery.getGeometry().getDebugType();
-            invariant(false);
-        }
-    }
-
-    /**
-     * Encodes GEO_NEAR match expression.
-     * Encode:
-     * - isNearSphere
-     * - CRS (flat or spherical)
-     */
-    void encodeGeoNearMatchExpression(const GeoNearMatchExpression* tree,
-                                      mongoutils::str::stream* os) {
-        const GeoNearExpression& nearQuery = tree->getData();
-
-        // isNearSphere
-        *os << (nearQuery.isNearSphere ? "ns" : "nr");
-
-        // CRS (flat or spherical or strict-winding spherical)
-        switch (nearQuery.centroid->crs) {
-        case FLAT: *os << "fl"; break;
-        case SPHERE: *os << "sp"; break;
-        case STRICT_SPHERE: *os << "ss"; break;
-        case UNSET:
-            error() << "unknown CRS type " << (int)nearQuery.centroid->crs
-                    << " in point geometry for near query";
-            invariant(false);
-            break;
-        }
-    }
-
-    /**
-     * Traverses expression tree pre-order.
-     * Appends an encoding of each node's match type and path name
-     * to the output stream.
-     */
-    void encodePlanCacheKeyTree(const MatchExpression* tree, mongoutils::str::stream* os) {
-        // Encode match type and path.
-        *os << encodeMatchType(tree->matchType());
-
-        encodeUserString(tree->path(), os);
-
-        // GEO and GEO_NEAR require additional encoding.
-        if (MatchExpression::GEO == tree->matchType()) {
-            encodeGeoMatchExpression(static_cast<const GeoMatchExpression*>(tree), os);
-        }
-        else if (MatchExpression::GEO_NEAR == tree->matchType()) {
-            encodeGeoNearMatchExpression(static_cast<const GeoNearMatchExpression*>(tree), os);
-        }
-
-        // Traverse child nodes.
-        // Enclose children in [].
-        if (tree->numChildren() > 0) {
-            *os << kEncodeChildrenBegin;
-        }
-        // Use comma to separate children encoding.
-        for (size_t i = 0; i < tree->numChildren(); ++i) {
-            if (i > 0) {
-                *os << kEncodeChildrenSeparator;
-            }
-            encodePlanCacheKeyTree(tree->getChild(i), os);
-        }
-        if (tree->numChildren() > 0) {
-            *os << kEncodeChildrenEnd;
-        }
-    }
-
-    /**
-     * Encodes sort order into cache key.
-     * Sort order is normalized because it provided by
-     * LiteParsedQuery.
-     */
-    void encodePlanCacheKeySort(const BSONObj& sortObj, mongoutils::str::stream* os) {
-        if (sortObj.isEmpty()) {
-            return;
-        }
-
-        *os << kEncodeSortSection;
-
-        BSONObjIterator it(sortObj);
-        while (it.more()) {
-            BSONElement elt = it.next();
-            // $meta text score
-            if (LiteParsedQuery::isTextScoreMeta(elt)) {
-                *os << "t";
-            }
-            // Ascending
-            else if (elt.numberInt() == 1) {
-                *os << "a";
-            }
-            // Descending
-            else {
-                *os << "d";
-            }
-            encodeUserString(elt.fieldName(), os);
-
-            // Sort argument separator
-            if (it.more()) {
-                *os << ",";
-            }
-        }
-    }
-
-    /**
-     * Encodes parsed projection into cache key.
-     * Does a simple toString() on each projected field
-     * in the BSON object.
-     * Orders the encoded elements in the projection by field name.
-     * This handles all the special projection types ($meta, $elemMatch, etc.)
-     */
-    void encodePlanCacheKeyProj(const BSONObj& projObj, mongoutils::str::stream* os) {
-        if (projObj.isEmpty()) {
-            return;
-        }
-
-        *os << kEncodeProjectionSection;
-
-        // Sorts the BSON elements by field name using a map.
-        std::map<StringData, BSONElement> elements;
-
-        BSONObjIterator it(projObj);
-        while (it.more()) {
-            BSONElement elt = it.next();
-            StringData fieldName = elt.fieldNameStringData();
-            elements[fieldName] = elt;
-        }
-
-        // Read elements in order of field name
-        for (std::map<StringData, BSONElement>::const_iterator i = elements.begin();
-             i != elements.end(); ++i) {
-            const BSONElement& elt = (*i).second;
-            // BSONElement::toString() arguments
-            // includeFieldName - skip field name (appending after toString() result). false.
-            // full: choose less verbose representation of child/data values. false.
-            encodeUserString(elt.toString(false, false), os);
-            encodeUserString(elt.fieldName(), os);
-        }
-    }
-
-} // namespace
-
-namespace mongo {
+}  // namespace
 
     //
     // These all punt to the many-argumented canonicalize below.
     //
 
     // static
-    Status CanonicalQuery::canonicalize(const string& ns,
+    Status CanonicalQuery::canonicalize(const std::string& ns,
                                         const BSONObj& query,
                                         CanonicalQuery** out,
                                         const MatchExpressionParser::WhereCallback& whereCallback) {
@@ -375,7 +131,7 @@ namespace mongo {
     }
 
     // static
-    Status CanonicalQuery::canonicalize(const string& ns,
+    Status CanonicalQuery::canonicalize(const std::string& ns,
                                         const BSONObj& query,
                                         long long skip,
                                         long long limit,
@@ -393,7 +149,7 @@ namespace mongo {
     }
 
     // static
-    Status CanonicalQuery::canonicalize(const string& ns,
+    Status CanonicalQuery::canonicalize(const std::string& ns,
                                         const BSONObj& query,
                                         const BSONObj& sort,
                                         const BSONObj& proj,
@@ -403,7 +159,7 @@ namespace mongo {
     }
 
     // static
-    Status CanonicalQuery::canonicalize(const string& ns,
+    Status CanonicalQuery::canonicalize(const std::string& ns,
                                         const BSONObj& query,
                                         const BSONObj& sort,
                                         const BSONObj& proj,
@@ -417,7 +173,7 @@ namespace mongo {
     }
 
     // static
-    Status CanonicalQuery::canonicalize(const string& ns,
+    Status CanonicalQuery::canonicalize(const std::string& ns,
                                         const BSONObj& query,
                                         const BSONObj& sort,
                                         const BSONObj& proj,
@@ -455,7 +211,7 @@ namespace mongo {
     Status CanonicalQuery::canonicalize(LiteParsedQuery* lpq,
                                         CanonicalQuery** out,
                                         const MatchExpressionParser::WhereCallback& whereCallback) {
-        auto_ptr<LiteParsedQuery> autoLpq(lpq);
+        std::auto_ptr<LiteParsedQuery> autoLpq(lpq);
 
         // Make MatchExpression.
         StatusWithMatchExpression swme = MatchExpressionParser::parse(autoLpq->getFilter(),
@@ -465,7 +221,7 @@ namespace mongo {
         }
 
         // Make the CQ we'll hopefully return.
-        auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
+        std::auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
         // Takes ownership of lpq and the MatchExpression* in swme.
         Status initStatus = cq->init(autoLpq.release(), whereCallback, swme.getValue());
 
@@ -498,7 +254,7 @@ namespace mongo {
         }
 
         // Make the CQ we'll hopefully return.
-        auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
+        std::auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
         Status initStatus = cq->init(lpq, whereCallback, root->shallowClone());
 
         if (!initStatus.isOK()) { return initStatus; }
@@ -507,7 +263,7 @@ namespace mongo {
     }
 
     // static
-    Status CanonicalQuery::canonicalize(const string& ns,
+    Status CanonicalQuery::canonicalize(const std::string& ns,
                                         const BSONObj& query,
                                         const BSONObj& sort,
                                         const BSONObj& proj,
@@ -529,7 +285,7 @@ namespace mongo {
         if (!parseStatus.isOK()) {
             return parseStatus;
         }
-        auto_ptr<LiteParsedQuery> lpq(lpqRaw);
+        std::auto_ptr<LiteParsedQuery> lpq(lpqRaw);
 
         // Build a parse tree from the BSONObj in the parsed query.
         StatusWithMatchExpression swme = 
@@ -539,7 +295,7 @@ namespace mongo {
         }
 
         // Make the CQ we'll hopefully return.
-        auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
+        std::auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
         // Takes ownership of lpq and the MatchExpression* in swme.
         Status initStatus = cq->init(lpq.release(), whereCallback, swme.getValue());
 
@@ -563,8 +319,6 @@ namespace mongo {
             return validStatus;
         }
 
-        this->generateCacheKey();
-
         // Validate the projection if there is one.
         if (!_pq->getProj().isEmpty()) {
             ParsedProjection* pp;
@@ -587,7 +341,7 @@ namespace mongo {
         BSONObjIterator it(query);
         while (it.more()) {
             BSONElement elt = it.next();
-            if (mongoutils::str::equals("_id", elt.fieldName() ) ) {
+            if (str::equals("_id", elt.fieldName() ) ) {
                 // Verify that the query on _id is a simple equality.
                 hasID = true;
 
@@ -605,8 +359,8 @@ namespace mongo {
                 }
             }
             else if (elt.fieldName()[0] == '$' &&
-                     (mongoutils::str::equals("$isolated", elt.fieldName())||
-                      mongoutils::str::equals("$atomic", elt.fieldName()))) {
+                     (str::equals("$isolated", elt.fieldName())||
+                      str::equals("$atomic", elt.fieldName()))) {
                 // ok, passthrough
             }
             else {
@@ -618,18 +372,6 @@ namespace mongo {
         return hasID;
     }
 
-    const PlanCacheKey& CanonicalQuery::getPlanCacheKey() const {
-        return _cacheKey;
-    }
-
-    void CanonicalQuery::generateCacheKey(void) {
-        mongoutils::str::stream ss;
-        encodePlanCacheKeyTree(_root.get(), &ss);
-        encodePlanCacheKeySort(_pq->getSort(), &ss);
-        encodePlanCacheKeyProj(_pq->getProj(), &ss);
-        _cacheKey = ss;
-    }
-
     // static
     MatchExpression* CanonicalQuery::normalizeTree(MatchExpression* root) {
         // root->isLogical() is true now.  We care about AND, OR, and NOT. NOR currently scares us.
@@ -643,7 +385,7 @@ namespace mongo {
 
             // If any of our children are of the same logical operator that we are, we remove the
             // child's children and append them to ourselves after we examine all children.
-            vector<MatchExpression*> absorbedChildren;
+            std::vector<MatchExpression*> absorbedChildren;
 
             for (size_t i = 0; i < root->numChildren();) {
                 MatchExpression* child = root->getChild(i);
@@ -802,7 +544,7 @@ namespace mongo {
             BSONObjIterator it(sortObj);
             while (it.more()) {
                 BSONElement elt = it.next();
-                if (mongoutils::str::equals("$natural", elt.fieldName())) {
+                if (str::equals("$natural", elt.fieldName())) {
                     return Status(ErrorCodes::BadValue,
                                   "text expression not allowed with $natural sort order");
                 }
@@ -845,7 +587,7 @@ namespace mongo {
 
         // Detach the OR from the root.
         invariant(NULL != tree->getChildVector());
-        vector<MatchExpression*>& rootChildren = *tree->getChildVector();
+        std::vector<MatchExpression*>& rootChildren = *tree->getChildVector();
         MatchExpression* orChild = NULL;
         for (size_t i = 0; i < rootChildren.size(); ++i) {
             if (MatchExpression::OR == rootChildren[i]->matchType()) {
@@ -858,7 +600,7 @@ namespace mongo {
         // AND the existing root with each or child.
         invariant(NULL != orChild);
         invariant(NULL != orChild->getChildVector());
-        vector<MatchExpression*>& orChildren = *orChild->getChildVector();
+        std::vector<MatchExpression*>& orChildren = *orChild->getChildVector();
         for (size_t i = 0; i < orChildren.size(); ++i) {
             AndMatchExpression* ama = new AndMatchExpression();
             ama->add(orChildren[i]);
@@ -872,7 +614,7 @@ namespace mongo {
     }
 
     std::string CanonicalQuery::toString() const {
-        mongoutils::str::stream ss;
+        str::stream ss;
         ss << "ns=" << _pq->ns() << " limit=" << _pq->getNumToReturn()
            << " skip=" << _pq->getSkip() << '\n';
         // The expression tree puts an endl on for us.
@@ -883,7 +625,7 @@ namespace mongo {
     }
 
     std::string CanonicalQuery::toStringShort() const {
-        mongoutils::str::stream ss;
+        str::stream ss;
         ss << "query: " << _pq->getFilter().toString()
            << " sort: " << _pq->getSort().toString()
            << " projection: " << _pq->getProj().toString()
diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h
index 2a57929c48b..b14fb29c233 100644
--- a/src/mongo/db/query/canonical_query.h
+++ b/src/mongo/db/query/canonical_query.h
@@ -39,9 +39,6 @@
 
 namespace mongo {
 
-    // TODO: Is this binary data really?
-    typedef std::string PlanCacheKey;
-
     class CanonicalQuery {
     public:
         /**
@@ -165,11 +162,6 @@ namespace mongo {
         const LiteParsedQuery& getParsed() const { return *_pq; }
         const ParsedProjection* getProj() const { return _proj.get(); }
 
-        /**
-         * Get the cache key for this canonical query.
-         */
-        const PlanCacheKey& getPlanCacheKey() const;
-
         // Debugging
         std::string toString() const;
         std::string toStringShort() const;
@@ -217,12 +209,6 @@ namespace mongo {
         CanonicalQuery() { }
 
         /**
-         * Computes and stores the cache key / query shape
-         * for this query.
-         */
-        void generateCacheKey(void);
-
-        /**
          * Takes ownership of 'root' and 'lpq'.
          */
         Status init(LiteParsedQuery* lpq,
@@ -235,12 +221,6 @@ namespace mongo {
         boost::scoped_ptr<MatchExpression> _root;
 
         boost::scoped_ptr<ParsedProjection> _proj;
-
-        /**
-         * Cache key is a string-ified combination of the query and sort obfuscated
-         * for minimal user comprehension.
-         */
-        PlanCacheKey _cacheKey;
     };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/canonical_query_test.cpp b/src/mongo/db/query/canonical_query_test.cpp
index 7ce2f78aa8f..b5e993bca71 100644
--- a/src/mongo/db/query/canonical_query_test.cpp
+++ b/src/mongo/db/query/canonical_query_test.cpp
@@ -599,108 +599,4 @@ namespace {
                            "{$and: [{a: 1}, {b: 1}, {c: 1}]}");
     }
 
-    /**
-     * Test functions for getPlanCacheKey.
-     * Cache keys are intentionally obfuscated and are meaningful only
-     * within the current lifetime of the server process. Users should treat
-     * plan cache keys as opaque.
-     */
-    void testGetPlanCacheKey(const char* queryStr, const char* sortStr,
-                             const char* projStr,
-                             const char *expectedStr) {
-        auto_ptr<CanonicalQuery> cq(canonicalize(queryStr, sortStr, projStr));
-        const PlanCacheKey& key = cq->getPlanCacheKey();
-        PlanCacheKey expectedKey(expectedStr);
-        if (key == expectedKey) {
-            return;
-        }
-        mongoutils::str::stream ss;
-        ss << "Unexpected plan cache key. Expected: " << expectedKey << ". Actual: " << key
-           << ". Query: " << cq->toString();
-        FAIL(ss);
-    }
-
-    TEST(PlanCacheTest, GetPlanCacheKey) {
-        // Generated cache keys should be treated as opaque to the user.
-
-        // No sorts
-        testGetPlanCacheKey("{}", "{}", "{}", "an");
-        testGetPlanCacheKey("{$or: [{a: 1}, {b: 2}]}", "{}", "{}", "or[eqa,eqb]");
-        testGetPlanCacheKey("{$or: [{a: 1}, {b: 1}, {c: 1}], d: 1}", "{}", "{}",
-                            "an[or[eqa,eqb,eqc],eqd]");
-        testGetPlanCacheKey("{$or: [{a: 1}, {b: 1}], c: 1, d: 1}", "{}", "{}",
-                            "an[or[eqa,eqb],eqc,eqd]");
-        testGetPlanCacheKey("{a: 1, b: 1, c: 1}", "{}", "{}", "an[eqa,eqb,eqc]");
-        testGetPlanCacheKey("{a: 1, beqc: 1}", "{}", "{}", "an[eqa,eqbeqc]");
-        testGetPlanCacheKey("{ap1a: 1}", "{}", "{}", "eqap1a");
-        testGetPlanCacheKey("{aab: 1}", "{}", "{}", "eqaab");
-
-        // With sort
-        testGetPlanCacheKey("{}", "{a: 1}", "{}", "an~aa");
-        testGetPlanCacheKey("{}", "{a: -1}", "{}", "an~da");
-        testGetPlanCacheKey("{}", "{a: {$meta: 'textScore'}}", "{a: {$meta: 'textScore'}}",
-                            "an~ta|{ $meta: \"textScore\" }a");
-        testGetPlanCacheKey("{a: 1}", "{b: 1}", "{}", "eqa~ab");
-
-        // With projection
-        testGetPlanCacheKey("{}", "{}", "{a: 1}", "an|1a");
-        testGetPlanCacheKey("{}", "{}", "{a: 0}", "an|0a");
-        testGetPlanCacheKey("{}", "{}", "{a: 99}", "an|99a");
-        testGetPlanCacheKey("{}", "{}", "{a: 'foo'}", "an|\"foo\"a");
-        testGetPlanCacheKey("{}", "{}", "{a: {$slice: [3, 5]}}", "an|{ $slice: \\[ 3\\, 5 \\] }a");
-        testGetPlanCacheKey("{}", "{}", "{a: {$elemMatch: {x: 2}}}",
-                            "an|{ $elemMatch: { x: 2 } }a");
-        testGetPlanCacheKey("{a: 1}", "{}", "{'a.$': 1}", "eqa|1a.$");
-        testGetPlanCacheKey("{a: 1}", "{}", "{a: 1}", "eqa|1a");
-
-        // Projection should be order-insensitive
-        testGetPlanCacheKey("{}", "{}", "{a: 1, b: 1}", "an|1a1b");
-        testGetPlanCacheKey("{}", "{}", "{b: 1, a: 1}", "an|1a1b");
-
-        // With or-elimination and projection
-        testGetPlanCacheKey("{$or: [{a: 1}]}", "{}", "{_id: 0, a: 1}", "eqa|0_id1a");
-        testGetPlanCacheKey("{$or: [{a: 1}]}", "{}", "{'a.$': 1}", "eqa|1a.$");
-    }
-
-    // Delimiters found in user field names or non-standard projection field values
-    // must be escaped.
-    TEST(PlanCacheTest, GetPlanCacheKeyEscaped) {
-        // Field name in query.
-        testGetPlanCacheKey("{'a,[]~|': 1}", "{}", "{}", "eqa\\,\\[\\]\\~\\|");
-
-        // Field name in sort.
-        testGetPlanCacheKey("{}", "{'a,[]~|': 1}", "{}", "an~aa\\,\\[\\]\\~\\|");
-
-        // Field name in projection.
-        testGetPlanCacheKey("{}", "{}", "{'a,[]~|': 1}", "an|1a\\,\\[\\]\\~\\|");
-
-        // Value in projection.
-        testGetPlanCacheKey("{}", "{}", "{a: 'foo,[]~|'}", "an|\"foo\\,\\[\\]\\~\\|\"a");
-    }
-
-    // Cache keys for $geoWithin queries with legacy and GeoJSON coordinates should
-    // not be the same.
-    TEST(PlanCacheTest, GetPlanCacheKeyGeoWithin) {
-        // Legacy coordinates.
-        auto_ptr<CanonicalQuery> cqLegacy(canonicalize("{a: {$geoWithin: "
-                                                       "{$box: [[-180, -90], [180, 90]]}}}"));
-        // GeoJSON coordinates.
-        auto_ptr<CanonicalQuery> cqNew(canonicalize("{a: {$geoWithin: "
-                                                    "{$geometry: {type: 'Polygon', coordinates: "
-                                                    "[[[0, 0], [0, 90], [90, 0], [0, 0]]]}}}}"));
-        ASSERT_NOT_EQUALS(cqLegacy->getPlanCacheKey(), cqNew->getPlanCacheKey());
-    }
-
-    // GEO_NEAR cache keys should include information on geometry and CRS in addition
-    // to the match type and field name.
-    TEST(PlanCacheTest, GetPlanCacheKeyGeoNear) {
-        testGetPlanCacheKey("{a: {$near: [0,0], $maxDistance:0.3 }}", "{}", "{}",
-                            "gnanrfl");
-        testGetPlanCacheKey("{a: {$nearSphere: [0,0], $maxDistance: 0.31 }}", "{}", "{}",
-                            "gnanssp");
-        testGetPlanCacheKey("{a: {$geoNear: {$geometry: {type: 'Point', coordinates: [0,0]},"
-                            "$maxDistance:100}}}", "{}", "{}",
-                            "gnanrsp");
-    }
-
 }
diff --git a/src/mongo/db/query/explain.cpp b/src/mongo/db/query/explain.cpp
index dc4bf614da8..b9a18f62067 100644
--- a/src/mongo/db/query/explain.cpp
+++ b/src/mongo/db/query/explain.cpp
@@ -500,10 +500,12 @@ namespace mongo {
         // field will always be false in the case of EOF or idhack plans.
         bool indexFilterSet = false;
         if (exec->collection() && exec->getCanonicalQuery()) {
-            const Collection* collection = exec->collection();
-            QuerySettings* querySettings = collection->infoCache()->getQuerySettings();
+            const CollectionInfoCache* infoCache = exec->collection()->infoCache();
+            const QuerySettings* querySettings = infoCache->getQuerySettings();
+            PlanCacheKey planCacheKey =
+                infoCache->getPlanCache()->computeKey(*exec->getCanonicalQuery());
             AllowedIndices* allowedIndicesRaw;
-            if (querySettings->getAllowedIndices(*exec->getCanonicalQuery(), &allowedIndicesRaw)) {
+            if (querySettings->getAllowedIndices(planCacheKey, &allowedIndicesRaw)) {
                 // Found an index filter set on the query shape.
                 boost::scoped_ptr<AllowedIndices> allowedIndices(allowedIndicesRaw);
                 indexFilterSet = true;
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp
index cfd6f5fa4d8..56fb18c5fe3 100644
--- a/src/mongo/db/query/get_executor.cpp
+++ b/src/mongo/db/query/get_executor.cpp
@@ -159,10 +159,12 @@ namespace mongo {
         // If query supports index filters, filter params.indices by indices in query settings.
         QuerySettings* querySettings = collection->infoCache()->getQuerySettings();
         AllowedIndices* allowedIndicesRaw;
+        PlanCacheKey planCacheKey =
+            collection->infoCache()->getPlanCache()->computeKey(*canonicalQuery);
 
         // Filter index catalog if index filters are specified for query.
         // Also, signal to planner that application hint should be ignored.
-        if (querySettings->getAllowedIndices(*canonicalQuery, &allowedIndicesRaw)) {
+        if (querySettings->getAllowedIndices(planCacheKey, &allowedIndicesRaw)) {
             boost::scoped_ptr<AllowedIndices> allowedIndices(allowedIndicesRaw);
             filterAllowedIndexEntries(*allowedIndices, &plannerParams->indices);
             plannerParams->indexFiltersApplied = true;
diff --git a/src/mongo/db/query/get_executor_test.cpp b/src/mongo/db/query/get_executor_test.cpp
index e65546502c5..85d97d3f1f7 100644
--- a/src/mongo/db/query/get_executor_test.cpp
+++ b/src/mongo/db/query/get_executor_test.cpp
@@ -75,23 +75,24 @@ namespace {
     void testAllowedIndices(const char* hintKeyPatterns[],
                             const char* indexCatalogKeyPatterns[],
                             const char* expectedFilteredKeyPatterns[]) {
+         PlanCache planCache;
          QuerySettings querySettings;
          AllowedIndices *allowedIndicesRaw;
 
          // getAllowedIndices should return false when query shape is not yet in query settings.
          auto_ptr<CanonicalQuery> cq(canonicalize("{a: 1}", "{}", "{}"));
-         ASSERT_FALSE(querySettings.getAllowedIndices(*cq, &allowedIndicesRaw));
+         PlanCacheKey key = planCache.computeKey(*cq);
+         ASSERT_FALSE(querySettings.getAllowedIndices(key, &allowedIndicesRaw));
 
          // Add entry to query settings.
-         const PlanCacheKey& key = cq->getPlanCacheKey();
          std::vector<BSONObj> indexKeyPatterns;
          for (int i=0; hintKeyPatterns[i] != NULL; ++i) {
              indexKeyPatterns.push_back(fromjson(hintKeyPatterns[i]));
          }
-         querySettings.setAllowedIndices(*cq, indexKeyPatterns);
+         querySettings.setAllowedIndices(*cq, key, indexKeyPatterns);
 
          // Index entry vector should contain 1 entry after filtering.
-         ASSERT_TRUE(querySettings.getAllowedIndices(*cq, &allowedIndicesRaw));
+         ASSERT_TRUE(querySettings.getAllowedIndices(key, &allowedIndicesRaw));
          ASSERT_FALSE(key.empty());
          ASSERT(NULL != allowedIndicesRaw);
          auto_ptr<AllowedIndices> allowedIndices(allowedIndicesRaw);
diff --git a/src/mongo/db/query/plan_cache.cpp b/src/mongo/db/query/plan_cache.cpp
index a73819ac8bd..7783afbd629 100644
--- a/src/mongo/db/query/plan_cache.cpp
+++ b/src/mongo/db/query/plan_cache.cpp
@@ -38,6 +38,8 @@
 #include "boost/thread/locks.hpp"
 #include "mongo/base/owned_pointer_vector.h"
 #include "mongo/client/dbclientinterface.h"   // For QueryOption_foobar
+#include "mongo/db/matcher/expression_array.h"
+#include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/query/plan_ranker.h"
 #include "mongo/db/query/query_solution.h"
 #include "mongo/db/query/query_knobs.h"
@@ -45,9 +47,245 @@
 #include "mongo/util/mongoutils/str.h"
 
 namespace mongo {
+namespace {
+
+    // Delimiters for cache key encoding.
+    const char kEncodeChildrenBegin = '[';
+    const char kEncodeChildrenEnd = ']';
+    const char kEncodeChildrenSeparator = ',';
+    const char kEncodeSortSection = '~';
+    const char kEncodeProjectionSection = '|';
+
+    /**
+     * Encode user-provided string. Cache key delimiters seen in the
+     * user string are escaped with a backslash.
+     */
+    void encodeUserString(StringData s, str::stream* os) {
+        for (size_t i = 0; i < s.size(); ++i) {
+            char c = s[i];
+            switch (c) {
+            case kEncodeChildrenBegin:
+            case kEncodeChildrenEnd:
+            case kEncodeChildrenSeparator:
+            case kEncodeSortSection:
+            case kEncodeProjectionSection:
+            case '\\':
+                  *os << '\\';
+                // Fall through to default case.
+            default:
+                *os << c;
+            }
+        }
+    }
+
+    void encodePlanCacheKeyTree(const MatchExpression* tree, str::stream* os);
+
+    /**
+     * 2-character encoding of MatchExpression::MatchType.
+     */
+    const char* encodeMatchType(MatchExpression::MatchType mt) {
+        switch(mt) {
+        case MatchExpression::AND: return "an"; break;
+        case MatchExpression::OR: return "or"; break;
+        case MatchExpression::NOR: return "nr"; break;
+        case MatchExpression::NOT: return "nt"; break;
+        case MatchExpression::ELEM_MATCH_OBJECT: return "eo"; break;
+        case MatchExpression::ELEM_MATCH_VALUE: return "ev"; break;
+        case MatchExpression::SIZE: return "sz"; break;
+        case MatchExpression::LTE: return "le"; break;
+        case MatchExpression::LT: return "lt"; break;
+        case MatchExpression::EQ: return "eq"; break;
+        case MatchExpression::GT: return "gt"; break;
+        case MatchExpression::GTE: return "ge"; break;
+        case MatchExpression::REGEX: return "re"; break;
+        case MatchExpression::MOD: return "mo"; break;
+        case MatchExpression::EXISTS: return "ex"; break;
+        case MatchExpression::MATCH_IN: return "in"; break;
+        case MatchExpression::NIN: return "ni"; break;
+        case MatchExpression::TYPE_OPERATOR: return "ty"; break;
+        case MatchExpression::GEO: return "go"; break;
+        case MatchExpression::WHERE: return "wh"; break;
+        case MatchExpression::ATOMIC: return "at"; break;
+        case MatchExpression::ALWAYS_FALSE: return "af"; break;
+        case MatchExpression::GEO_NEAR: return "gn"; break;
+        case MatchExpression::TEXT: return "te"; break;
+        default: verify(0); return "";
+        }
+    }
 
-    using std::string;
-    using std::vector;
+    /**
+     * Encodes GEO match expression.
+     * Encoding includes:
+     * - type of geo query (within/intersect/near)
+     * - geometry type
+     * - CRS (flat or spherical)
+     */
+    void encodeGeoMatchExpression(const GeoMatchExpression* tree, str::stream* os) {
+        const GeoExpression& geoQuery = tree->getGeoExpression();
+
+        // Type of geo query.
+        switch (geoQuery.getPred()) {
+        case GeoExpression::WITHIN: *os << "wi"; break;
+        case GeoExpression::INTERSECT: *os << "in"; break;
+        case GeoExpression::INVALID: *os << "id"; break;
+        }
+
+        // Geometry type.
+        // Only one of the shared_ptrs in GeoContainer may be non-NULL.
+        *os << geoQuery.getGeometry().getDebugType();
+
+        // CRS (flat or spherical)
+        if (FLAT == geoQuery.getGeometry().getNativeCRS()) {
+            *os << "fl";
+        }
+        else if (SPHERE == geoQuery.getGeometry().getNativeCRS()) {
+            *os << "sp";
+        }
+        else if (STRICT_SPHERE == geoQuery.getGeometry().getNativeCRS()) {
+            *os << "ss";
+        }
+        else {
+            error() << "unknown CRS type " << (int)geoQuery.getGeometry().getNativeCRS()
+                    << " in geometry of type " << geoQuery.getGeometry().getDebugType();
+            invariant(false);
+        }
+    }
+
+    /**
+     * Encodes GEO_NEAR match expression.
+     * Encode:
+     * - isNearSphere
+     * - CRS (flat or spherical)
+     */
+    void encodeGeoNearMatchExpression(const GeoNearMatchExpression* tree,
+                                      str::stream* os) {
+        const GeoNearExpression& nearQuery = tree->getData();
+
+        // isNearSphere
+        *os << (nearQuery.isNearSphere ? "ns" : "nr");
+
+        // CRS (flat or spherical or strict-winding spherical)
+        switch (nearQuery.centroid->crs) {
+        case FLAT: *os << "fl"; break;
+        case SPHERE: *os << "sp"; break;
+        case STRICT_SPHERE: *os << "ss"; break;
+        case UNSET:
+            error() << "unknown CRS type " << (int)nearQuery.centroid->crs
+                    << " in point geometry for near query";
+            invariant(false);
+            break;
+        }
+    }
+
+    /**
+     * Traverses expression tree pre-order.
+     * Appends an encoding of each node's match type and path name
+     * to the output stream.
+     */
+    void encodePlanCacheKeyTree(const MatchExpression* tree, str::stream* os) {
+        // Encode match type and path.
+        *os << encodeMatchType(tree->matchType());
+
+        encodeUserString(tree->path(), os);
+
+        // GEO and GEO_NEAR require additional encoding.
+        if (MatchExpression::GEO == tree->matchType()) {
+            encodeGeoMatchExpression(static_cast<const GeoMatchExpression*>(tree), os);
+        }
+        else if (MatchExpression::GEO_NEAR == tree->matchType()) {
+            encodeGeoNearMatchExpression(static_cast<const GeoNearMatchExpression*>(tree), os);
+        }
+
+        // Traverse child nodes.
+        // Enclose children in [].
+        if (tree->numChildren() > 0) {
+            *os << kEncodeChildrenBegin;
+        }
+        // Use comma to separate children encoding.
+        for (size_t i = 0; i < tree->numChildren(); ++i) {
+            if (i > 0) {
+                *os << kEncodeChildrenSeparator;
+            }
+            encodePlanCacheKeyTree(tree->getChild(i), os);
+        }
+        if (tree->numChildren() > 0) {
+            *os << kEncodeChildrenEnd;
+        }
+    }
+
+    /**
+     * Encodes sort order into cache key.
+     * Sort order is normalized because it provided by
+     * LiteParsedQuery.
+     */
+    void encodePlanCacheKeySort(const BSONObj& sortObj, str::stream* os) {
+        if (sortObj.isEmpty()) {
+            return;
+        }
+
+        *os << kEncodeSortSection;
+
+        BSONObjIterator it(sortObj);
+        while (it.more()) {
+            BSONElement elt = it.next();
+            // $meta text score
+            if (LiteParsedQuery::isTextScoreMeta(elt)) {
+                *os << "t";
+            }
+            // Ascending
+            else if (elt.numberInt() == 1) {
+                *os << "a";
+            }
+            // Descending
+            else {
+                *os << "d";
+            }
+            encodeUserString(elt.fieldName(), os);
+
+            // Sort argument separator
+            if (it.more()) {
+                *os << ",";
+            }
+        }
+    }
+
+    /**
+     * Encodes parsed projection into cache key.
+     * Does a simple toString() on each projected field
+     * in the BSON object.
+     * Orders the encoded elements in the projection by field name.
+     * This handles all the special projection types ($meta, $elemMatch, etc.)
+     */
+    void encodePlanCacheKeyProj(const BSONObj& projObj, str::stream* os) {
+        if (projObj.isEmpty()) {
+            return;
+        }
+
+        *os << kEncodeProjectionSection;
+
+        // Sorts the BSON elements by field name using a map.
+        std::map<StringData, BSONElement> elements;
+
+        BSONObjIterator it(projObj);
+        while (it.more()) {
+            BSONElement elt = it.next();
+            StringData fieldName = elt.fieldNameStringData();
+            elements[fieldName] = elt;
+        }
+
+        // Read elements in order of field name
+        for (std::map<StringData, BSONElement>::const_iterator i = elements.begin();
+             i != elements.end(); ++i) {
+            const BSONElement& elt = (*i).second;
+            // BSONElement::toString() arguments
+            // includeFieldName - skip field name (appending after toString() result). false.
+            // full: choose less verbose representation of child/data values. false.
+            encodeUserString(elt.toString(false, false), os);
+            encodeUserString(elt.fieldName(), os);
+        }
+    }
+
+}  // namespace
 
     //
     // Cache-related functions for CanonicalQuery
@@ -184,8 +422,8 @@ namespace mongo {
         return entry;
     }
 
-    string PlanCacheEntry::toString() const {
-        mongoutils::str::stream ss;
+    std::string PlanCacheEntry::toString() const {
+        str::stream ss;
         ss << "(query: " << query.toString()
            << ";sort: " << sort.toString()
            << ";projection: " << projection.toString()
@@ -194,8 +432,8 @@ namespace mongo {
         return ss;
     }
 
-    string CachedSolution::toString() const {
-        mongoutils::str::stream ss;
+    std::string CachedSolution::toString() const {
+        str::stream ss;
         ss << "key: " << key << '\n';
         return ss;
     }
@@ -215,7 +453,7 @@ namespace mongo {
             root->setIndexEntry(*entry.get());
         }
 
-        for (vector<PlanCacheIndexTree*>::const_iterator it = children.begin();
+        for (std::vector<PlanCacheIndexTree*>::const_iterator it = children.begin();
                 it != children.end(); ++it) {
             PlanCacheIndexTree* clonedChild = (*it)->clone();
             root->children.push_back(clonedChild);
@@ -224,18 +462,18 @@ namespace mongo {
     }
 
     std::string PlanCacheIndexTree::toString(int indents) const {
-        mongoutils::str::stream ss;
+        str::stream ss;
         if (!children.empty()) {
-            ss << string(3 * indents, '-') << "Node\n";
+            ss << std::string(3 * indents, '-') << "Node\n";
             int newIndent = indents + 1;
-            for (vector<PlanCacheIndexTree*>::const_iterator it = children.begin();
+            for (std::vector<PlanCacheIndexTree*>::const_iterator it = children.begin();
                     it != children.end(); ++it) {
                 ss << (*it)->toString(newIndent);
             }
             return ss;
         }
         else {
-            ss << string(3 * indents, '-') << "Leaf ";
+            ss << std::string(3 * indents, '-') << "Leaf ";
             if (NULL != entry.get()) {
                 ss << entry->keyPattern.toString() << ", pos: " << index_pos;
             }
@@ -262,7 +500,7 @@ namespace mongo {
     }
 
     std::string SolutionCacheData::toString() const {
-        mongoutils::str::stream ss;
+        str::stream ss;
         switch (this->solnType) {
         case WHOLE_IXSCAN_SOLN:
             verify(this->tree.get());
@@ -324,7 +562,7 @@ namespace mongo {
         entry->projection = pq.getProj().getOwned();
 
         boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
-        std::auto_ptr<PlanCacheEntry> evictedEntry = _cache.add(query.getPlanCacheKey(), entry);
+        std::auto_ptr<PlanCacheEntry> evictedEntry = _cache.add(computeKey(query), entry);
 
         if (NULL != evictedEntry.get()) {
             LOG(1) << _ns << ": plan cache maximum size exceeded - "
@@ -336,7 +574,7 @@ namespace mongo {
     }
 
     Status PlanCache::get(const CanonicalQuery& query, CachedSolution** crOut) const {
-        const PlanCacheKey& key = query.getPlanCacheKey();
+        PlanCacheKey key = computeKey(query);
         verify(crOut);
 
         boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
@@ -357,7 +595,7 @@ namespace mongo {
             return Status(ErrorCodes::BadValue, "feedback is NULL");
         }
         std::auto_ptr<PlanCacheEntryFeedback> autoFeedback(feedback);
-        const PlanCacheKey& ck = cq.getPlanCacheKey();
+        PlanCacheKey ck = computeKey(cq);
 
         boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
         PlanCacheEntry* entry;
@@ -377,7 +615,7 @@ namespace mongo {
 
     Status PlanCache::remove(const CanonicalQuery& canonicalQuery) {
         boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
-        return _cache.remove(canonicalQuery.getPlanCacheKey());
+        return _cache.remove(computeKey(canonicalQuery));
     }
 
     void PlanCache::clear() {
@@ -386,8 +624,16 @@ namespace mongo {
         _writeOperations.store(0);
     }
 
+    PlanCacheKey PlanCache::computeKey(const CanonicalQuery& cq) const {
+        str::stream ss;
+        encodePlanCacheKeyTree(cq.root(), &ss);
+        encodePlanCacheKeySort(cq.getParsed().getSort(), &ss);
+        encodePlanCacheKeyProj(cq.getParsed().getProj(), &ss);
+        return ss;
+    }
+
     Status PlanCache::getEntry(const CanonicalQuery& query, PlanCacheEntry** entryOut) const {
-        const PlanCacheKey& key = query.getPlanCacheKey();
+        PlanCacheKey key = computeKey(query);
         verify(entryOut);
 
         boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
@@ -417,7 +663,7 @@ namespace mongo {
 
     bool PlanCache::contains(const CanonicalQuery& cq) const {
         boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
-        return _cache.hasKey(cq.getPlanCacheKey());
+        return _cache.hasKey(computeKey(cq));
     }
 
     size_t PlanCache::size() const {
diff --git a/src/mongo/db/query/plan_cache.h b/src/mongo/db/query/plan_cache.h
index 850b1027d63..84d3527ad78 100644
--- a/src/mongo/db/query/plan_cache.h
+++ b/src/mongo/db/query/plan_cache.h
@@ -42,6 +42,9 @@
 
 namespace mongo {
 
+    // A PlanCacheKey is a string-ified version of a query's predicate/projection/sort.
+    typedef std::string PlanCacheKey;
+
     struct PlanRankingDecision;
     struct QuerySolution;
     struct QuerySolutionNode;
@@ -334,6 +337,15 @@ namespace mongo {
         void clear();
 
         /**
+         * Get the cache key corresponding to the given canonical query.  The query need not already
+         * be cached.
+         *
+         * This is provided in the public API simply as a convenience for consumers who need some
+         * description of query shape (e.g. index filters).
+         */
+        PlanCacheKey computeKey(const CanonicalQuery&) const;
+
+        /**
          * Returns a copy of a cache entry.
          * Used by planCacheListPlans to display plan details.
           *
diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp
index cb6156ad0eb..6fa77ff9c7c 100644
--- a/src/mongo/db/query/plan_cache_test.cpp
+++ b/src/mongo/db/query/plan_cache_test.cpp
@@ -142,7 +142,7 @@ namespace {
     MatchExpression* parseMatchExpression(const BSONObj& obj) {
         StatusWithMatchExpression status = MatchExpressionParser::parse(obj);
         if (!status.isOK()) {
-            mongoutils::str::stream ss;
+            str::stream ss;
             ss << "failed to parse query: " << obj.toString()
                << ". Reason: " << status.getStatus().toString();
             FAIL(ss);
@@ -155,7 +155,7 @@ namespace {
         if (actual->equivalent(expected)) {
             return;
         }
-        mongoutils::str::stream ss;
+        str::stream ss;
         ss << "Match expressions are not equivalent."
            << "\nOriginal query: " << queryStr
            << "\nExpected: " << expected->toString()
@@ -206,7 +206,7 @@ namespace {
         if (PlanCache::shouldCacheQuery(query)) {
             return;
         }
-        mongoutils::str::stream ss;
+        str::stream ss;
         ss << "Canonical query should be cacheable: " << query.toString();
         FAIL(ss);
     }
@@ -215,7 +215,7 @@ namespace {
         if (!PlanCache::shouldCacheQuery(query)) {
             return;
         }
-        mongoutils::str::stream ss;
+        str::stream ss;
         ss << "Canonical query should not be cacheable: " << query.toString();
         FAIL(ss);
     }
@@ -564,7 +564,7 @@ namespace {
         // Solution introspection.
         //
 
-        void dumpSolutions(mongoutils::str::stream& ost) const {
+        void dumpSolutions(str::stream& ost) const {
             for (vector<QuerySolution*>::const_iterator it = solns.begin();
                     it != solns.end();
                     ++it) {
@@ -601,7 +601,7 @@ namespace {
             if (numMatches == matches) {
                 return;
             }
-            mongoutils::str::stream ss;
+            str::stream ss;
             ss << "expected " << numMatches << " matches for solution " << solnJson
                << " but got " << matches
                << " instead. all solutions generated: " << '\n';
@@ -669,7 +669,7 @@ namespace {
                 }
             }
 
-            mongoutils::str::stream ss;
+            str::stream ss;
             ss << "Could not find a match for solution " << solnJson
                << " All solutions generated: " << '\n';
             dumpSolutions(ss);
@@ -687,7 +687,7 @@ namespace {
         void assertSolutionMatches(QuerySolution* trueSoln, const string& solnJson) const {
             BSONObj testSoln = fromjson(solnJson);
             if (!QueryPlannerTestLib::solutionMatches(testSoln, trueSoln->root.get())) {
-                mongoutils::str::stream ss;
+                str::stream ss;
                 ss << "Expected solution " << solnJson << " did not match true solution: "
                    << trueSoln->toString() << '\n';
                 FAIL(ss);
@@ -1052,4 +1052,110 @@ namespace {
                                       "{fetch: {node: {ixscan: {pattern: {b: '2d'}}}}}]}}");
     }
 
+    /**
+     * Test functions for computeKey.  Cache keys are intentionally obfuscated and are
+     * meaningful only within the current lifetime of the server process. Users should treat plan
+     * cache keys as opaque.
+     */
+    void testComputeKey(const char* queryStr,
+                        const char* sortStr,
+                        const char* projStr,
+                        const char *expectedStr) {
+        PlanCache planCache;
+        auto_ptr<CanonicalQuery> cq(canonicalize(queryStr, sortStr, projStr));
+        PlanCacheKey key = planCache.computeKey(*cq);
+        PlanCacheKey expectedKey(expectedStr);
+        if (key == expectedKey) {
+            return;
+        }
+        str::stream ss;
+        ss << "Unexpected plan cache key. Expected: " << expectedKey << ". Actual: " << key
+           << ". Query: " << cq->toString();
+        FAIL(ss);
+    }
+
+    TEST(PlanCacheTest, ComputeKey) {
+        // Generated cache keys should be treated as opaque to the user.
+
+        // No sorts
+        testComputeKey("{}", "{}", "{}", "an");
+        testComputeKey("{$or: [{a: 1}, {b: 2}]}", "{}", "{}", "or[eqa,eqb]");
+        testComputeKey("{$or: [{a: 1}, {b: 1}, {c: 1}], d: 1}", "{}", "{}",
+                       "an[or[eqa,eqb,eqc],eqd]");
+        testComputeKey("{$or: [{a: 1}, {b: 1}], c: 1, d: 1}", "{}", "{}",
+                       "an[or[eqa,eqb],eqc,eqd]");
+        testComputeKey("{a: 1, b: 1, c: 1}", "{}", "{}", "an[eqa,eqb,eqc]");
+        testComputeKey("{a: 1, beqc: 1}", "{}", "{}", "an[eqa,eqbeqc]");
+        testComputeKey("{ap1a: 1}", "{}", "{}", "eqap1a");
+        testComputeKey("{aab: 1}", "{}", "{}", "eqaab");
+
+        // With sort
+        testComputeKey("{}", "{a: 1}", "{}", "an~aa");
+        testComputeKey("{}", "{a: -1}", "{}", "an~da");
+        testComputeKey("{}", "{a: {$meta: 'textScore'}}", "{a: {$meta: 'textScore'}}",
+                       "an~ta|{ $meta: \"textScore\" }a");
+        testComputeKey("{a: 1}", "{b: 1}", "{}", "eqa~ab");
+
+        // With projection
+        testComputeKey("{}", "{}", "{a: 1}", "an|1a");
+        testComputeKey("{}", "{}", "{a: 0}", "an|0a");
+        testComputeKey("{}", "{}", "{a: 99}", "an|99a");
+        testComputeKey("{}", "{}", "{a: 'foo'}", "an|\"foo\"a");
+        testComputeKey("{}", "{}", "{a: {$slice: [3, 5]}}", "an|{ $slice: \\[ 3\\, 5 \\] }a");
+        testComputeKey("{}", "{}", "{a: {$elemMatch: {x: 2}}}",
+                       "an|{ $elemMatch: { x: 2 } }a");
+        testComputeKey("{a: 1}", "{}", "{'a.$': 1}", "eqa|1a.$");
+        testComputeKey("{a: 1}", "{}", "{a: 1}", "eqa|1a");
+
+        // Projection should be order-insensitive
+        testComputeKey("{}", "{}", "{a: 1, b: 1}", "an|1a1b");
+        testComputeKey("{}", "{}", "{b: 1, a: 1}", "an|1a1b");
+
+        // With or-elimination and projection
+        testComputeKey("{$or: [{a: 1}]}", "{}", "{_id: 0, a: 1}", "eqa|0_id1a");
+        testComputeKey("{$or: [{a: 1}]}", "{}", "{'a.$': 1}", "eqa|1a.$");
+    }
+
+    // Delimiters found in user field names or non-standard projection field values
+    // must be escaped.
+    TEST(PlanCacheTest, ComputeKeyEscaped) {
+        // Field name in query.
+        testComputeKey("{'a,[]~|': 1}", "{}", "{}", "eqa\\,\\[\\]\\~\\|");
+
+        // Field name in sort.
+        testComputeKey("{}", "{'a,[]~|': 1}", "{}", "an~aa\\,\\[\\]\\~\\|");
+
+        // Field name in projection.
+        testComputeKey("{}", "{}", "{'a,[]~|': 1}", "an|1a\\,\\[\\]\\~\\|");
+
+        // Value in projection.
+        testComputeKey("{}", "{}", "{a: 'foo,[]~|'}", "an|\"foo\\,\\[\\]\\~\\|\"a");
+    }
+
+    // Cache keys for $geoWithin queries with legacy and GeoJSON coordinates should
+    // not be the same.
+    TEST(PlanCacheTest, ComputeKeyGeoWithin) {
+        PlanCache planCache;
+
+        // Legacy coordinates.
+        auto_ptr<CanonicalQuery> cqLegacy(canonicalize("{a: {$geoWithin: "
+                                                       "{$box: [[-180, -90], [180, 90]]}}}"));
+        // GeoJSON coordinates.
+        auto_ptr<CanonicalQuery> cqNew(canonicalize("{a: {$geoWithin: "
+                                                    "{$geometry: {type: 'Polygon', coordinates: "
+                                                    "[[[0, 0], [0, 90], [90, 0], [0, 0]]]}}}}"));
+        ASSERT_NOT_EQUALS(planCache.computeKey(*cqLegacy),
+                          planCache.computeKey(*cqNew));
+    }
+
+    // GEO_NEAR cache keys should include information on geometry and CRS in addition
+    // to the match type and field name.
+    TEST(PlanCacheTest, ComputeKeyGeoNear) {
+        testComputeKey("{a: {$near: [0,0], $maxDistance:0.3 }}", "{}", "{}", "gnanrfl");
+        testComputeKey("{a: {$nearSphere: [0,0], $maxDistance: 0.31 }}", "{}", "{}", "gnanssp");
+        testComputeKey("{a: {$geoNear: {$geometry: {type: 'Point', coordinates: [0,0]},"
+                       "$maxDistance:100}}}", "{}", "{}", "gnanrsp");
+    }
+
+
 }  // namespace
diff --git a/src/mongo/db/query/query_settings.cpp b/src/mongo/db/query/query_settings.cpp
index 8de33cf4db8..6c12dbcc069 100644
--- a/src/mongo/db/query/query_settings.cpp
+++ b/src/mongo/db/query/query_settings.cpp
@@ -82,12 +82,10 @@ namespace mongo {
         _clear();
     }
 
-    bool QuerySettings::getAllowedIndices(const CanonicalQuery& query,
+    bool QuerySettings::getAllowedIndices(const PlanCacheKey& key,
                                           AllowedIndices** allowedIndicesOut) const {
         invariant(allowedIndicesOut);
 
-        const PlanCacheKey& key = query.getPlanCacheKey();
-
         boost::lock_guard<boost::mutex> cacheLock(_mutex);
         AllowedIndexEntryMap::const_iterator cacheIter = _allowedIndexEntryMap.find(key);
 
@@ -116,6 +114,7 @@ namespace mongo {
     }
 
     void QuerySettings::setAllowedIndices(const CanonicalQuery& canonicalQuery,
+                                          const PlanCacheKey& key,
                                           const std::vector<BSONObj>& indexes) {
         const LiteParsedQuery& lpq = canonicalQuery.getParsed();
         const BSONObj& query = lpq.getFilter();
@@ -123,7 +122,6 @@ namespace mongo {
         const BSONObj& projection = lpq.getProj();
         AllowedIndexEntry* entry = new AllowedIndexEntry(query, sort, projection, indexes);
 
-        const PlanCacheKey& key = canonicalQuery.getPlanCacheKey();
         boost::lock_guard<boost::mutex> cacheLock(_mutex);
         AllowedIndexEntryMap::iterator i = _allowedIndexEntryMap.find(key);
         // Replace existing entry.
@@ -134,8 +132,7 @@ namespace mongo {
         _allowedIndexEntryMap[key] = entry;
     }
 
-    void QuerySettings::removeAllowedIndices(const CanonicalQuery& canonicalQuery) {
-        const PlanCacheKey& key = canonicalQuery.getPlanCacheKey();
+    void QuerySettings::removeAllowedIndices(const PlanCacheKey& key) {
         boost::lock_guard<boost::mutex> cacheLock(_mutex);
         AllowedIndexEntryMap::iterator i = _allowedIndexEntryMap.find(key);
 
diff --git a/src/mongo/db/query/query_settings.h b/src/mongo/db/query/query_settings.h
index beb312daf91..a65ea88d901 100644
--- a/src/mongo/db/query/query_settings.h
+++ b/src/mongo/db/query/query_settings.h
@@ -35,6 +35,7 @@
 #include "mongo/bson/bsonobj.h"
 #include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/index_entry.h"
+#include "mongo/db/query/plan_cache.h"
 #include "mongo/platform/unordered_map.h"
 
 namespace mongo {
@@ -100,7 +101,7 @@ namespace mongo {
          * Returns false and sets allowedIndicesOut to NULL otherwise.
          * Caller owns AllowedIndices.
          */
-        bool getAllowedIndices(const CanonicalQuery& query,
+        bool getAllowedIndices(const PlanCacheKey& query,
                                AllowedIndices** allowedIndicesOut) const;
 
         /**
@@ -115,12 +116,13 @@ namespace mongo {
          * frees resources for existing entry before replacing.
          */
         void setAllowedIndices(const CanonicalQuery& canonicalQuery,
+                               const PlanCacheKey& key,
                                const std::vector<BSONObj>& indexes);
 
         /**
          * Removes single entry from query settings. No effect if query shape is not found.
          */
-        void removeAllowedIndices(const CanonicalQuery& canonicalQuery);
+        void removeAllowedIndices(const PlanCacheKey& canonicalQuery);
 
         /**
          * Clears all allowed indices from query settings.