SERVER-35333 caching plans for allPaths indexes

33 files changed, 766 insertions, 287 deletions

diff --git a/src/mongo/db/catalog/collection_info_cache_impl.cpp b/src/mongo/db/catalog/collection_info_cache_impl.cpp
index 9eacc4887fc..b005b10bad4 100644
--- a/src/mongo/db/catalog/collection_info_cache_impl.cpp
+++ b/src/mongo/db/catalog/collection_info_cache_impl.cpp
@@ -143,7 +143,7 @@ void CollectionInfoCacheImpl::computeIndexKeys(OperationContext* opCtx) {
         const MatchExpression* filter = entry->getFilterExpression();
         if (filter) {
             stdx::unordered_set<std::string> paths;
-            QueryPlannerIXSelect::getFields(filter, "", &paths);
+            QueryPlannerIXSelect::getFields(filter, &paths);
             for (auto it = paths.begin(); it != paths.end(); ++it) {
                 _indexedPaths.addPath(*it);
             }
@@ -207,7 +207,7 @@ void CollectionInfoCacheImpl::updatePlanCacheIndexEntries(OperationContext* opCt
                                   ice->getMultikeyPaths(opCtx),
                                   desc->isSparse(),
                                   desc->unique(),
-                                  desc->indexName(),
+                                  IndexEntry::Identifier{desc->indexName()},
                                   ice->getFilterExpression(),
                                   desc->infoObj(),
                                   ice->getCollator());
diff --git a/src/mongo/db/commands/index_filter_commands_test.cpp b/src/mongo/db/commands/index_filter_commands_test.cpp
index ffc0419616d..7a4a4497807 100644
--- a/src/mongo/db/commands/index_filter_commands_test.cpp
+++ b/src/mongo/db/commands/index_filter_commands_test.cpp
@@ -426,8 +426,13 @@ TEST(IndexFilterCommandsTest, SetAndClearFiltersCollation) {
 
     // Create a plan cache. Add an index so that indexability is included in the plan cache keys.
     PlanCache planCache;
-    planCache.notifyOfIndexEntries(
-        {IndexEntry(fromjson("{a: 1}"), false, false, false, "index_name", NULL, BSONObj())});
+    planCache.notifyOfIndexEntries({IndexEntry(fromjson("{a: 1}"),
+                                               false,
+                                               false,
+                                               false,
+                                               IndexEntry::Identifier{"index_name"},
+                                               NULL,
+                                               BSONObj())});
 
     // Inject query shapes with and without collation into plan cache.
     addQueryShapeToPlanCache(
@@ -494,17 +499,27 @@ TEST(IndexFilterCommandsTest, SetAndClearFiltersCollation) {
 
 TEST(IndexFilterCommandsTest, SetFilterAcceptsIndexNames) {
     CollatorInterfaceMock reverseCollator(CollatorInterfaceMock::MockType::kReverseString);
-    IndexEntry collatedIndex(
-        fromjson("{a: 1}"), false, false, false, "a_1:rev", nullptr, BSONObj());
+    IndexEntry collatedIndex(fromjson("{a: 1}"),
+                             false,
+                             false,
+                             false,
+                             IndexEntry::Identifier{"a_1:rev"},
+                             nullptr,
+                             BSONObj());
     collatedIndex.collator = &reverseCollator;
     QueryTestServiceContext serviceContext;
     auto opCtx = serviceContext.makeOperationContext();
     QuerySettings querySettings;
 
     PlanCache planCache;
-    planCache.notifyOfIndexEntries(
-        {IndexEntry(fromjson("{a: 1}"), false, false, false, "a_1", nullptr, BSONObj()),
-         collatedIndex});
+    planCache.notifyOfIndexEntries({IndexEntry(fromjson("{a: 1}"),
+                                               false,
+                                               false,
+                                               false,
+                                               IndexEntry::Identifier{"a_1"},
+                                               nullptr,
+                                               BSONObj()),
+                                    collatedIndex});
 
     addQueryShapeToPlanCache(opCtx.get(), &planCache, "{a: 2}", "{}", "{}", "{}");
     ASSERT_TRUE(planCacheContains(opCtx.get(), planCache, "{a: 2}", "{}", "{}", "{}"));
diff --git a/src/mongo/db/commands/plan_cache_commands_test.cpp b/src/mongo/db/commands/plan_cache_commands_test.cpp
index a540d9c68db..e635fff5224 100644
--- a/src/mongo/db/commands/plan_cache_commands_test.cpp
+++ b/src/mongo/db/commands/plan_cache_commands_test.cpp
@@ -388,8 +388,13 @@ TEST(PlanCacheCommandsTest, planCacheClearOneKeyCollation) {
     // Create plan cache with 2 entries. Add an index so that indexability is included in the plan
     // cache keys.
     PlanCache planCache;
-    planCache.notifyOfIndexEntries(
-        {IndexEntry(fromjson("{a: 1}"), false, false, false, "index_name", NULL, BSONObj())});
+    planCache.notifyOfIndexEntries({IndexEntry(fromjson("{a: 1}"),
+                                               false,
+                                               false,
+                                               false,
+                                               IndexEntry::Identifier{"index_name"},
+                                               NULL,
+                                               BSONObj())});
     QuerySolution qs;
     qs.cacheData.reset(createSolutionCacheData());
     std::vector<QuerySolution*> solns;
@@ -633,8 +638,13 @@ TEST(PlanCacheCommandsTest, planCacheListPlansCollation) {
     // Create plan cache with 2 entries. Add an index so that indexability is included in the plan
     // cache keys. Give query with collation two solutions.
     PlanCache planCache;
-    planCache.notifyOfIndexEntries(
-        {IndexEntry(fromjson("{a: 1}"), false, false, false, "index_name", NULL, BSONObj())});
+    planCache.notifyOfIndexEntries({IndexEntry(fromjson("{a: 1}"),
+                                               false,
+                                               false,
+                                               false,
+                                               IndexEntry::Identifier{"index_name"},
+                                               NULL,
+                                               BSONObj())});
     QuerySolution qs;
     qs.cacheData.reset(createSolutionCacheData());
     std::vector<QuerySolution*> solns;
diff --git a/src/mongo/db/exec/count_scan.h b/src/mongo/db/exec/count_scan.h
index f9c69cdede1..82edf4c3716 100644
--- a/src/mongo/db/exec/count_scan.h
+++ b/src/mongo/db/exec/count_scan.h
@@ -41,9 +41,6 @@ namespace mongo {
 
 class WorkingSet;
 
-// TODO SERVER-35333: when we have a means of uniquely identifying each $** sub-index generated
-// during planning, 'indexName' should change to be the unique ID for the specific sub-index used in
-// this solution.
 struct CountScanParams {
     CountScanParams(const IndexDescriptor& descriptor,
                     std::string indexName,
diff --git a/src/mongo/db/exec/index_scan.h b/src/mongo/db/exec/index_scan.h
index d1e1bffbe24..583acb52881 100644
--- a/src/mongo/db/exec/index_scan.h
+++ b/src/mongo/db/exec/index_scan.h
@@ -42,9 +42,6 @@ namespace mongo {
 
 class WorkingSet;
 
-// TODO SERVER-35333: when we have a means of uniquely identifying each $** sub-index generated
-// during planning, 'indexName' should change to be the unique ID for the specific sub-index used in
-// this solution.
 struct IndexScanParams {
     IndexScanParams(const IndexDescriptor& descriptor,
                     std::string indexName,
diff --git a/src/mongo/db/exec/projection_exec_agg.cpp b/src/mongo/db/exec/projection_exec_agg.cpp
index d841d5d93f0..7c292ac4a81 100644
--- a/src/mongo/db/exec/projection_exec_agg.cpp
+++ b/src/mongo/db/exec/projection_exec_agg.cpp
@@ -89,17 +89,22 @@ public:
         return applyTransformation(Document{inputDoc}).toBson();
     }
 
+    bool applyProjectionToOneField(StringData field) const {
+        MutableDocument doc;
+        const FieldPath f{field};
+        doc.setNestedField(f, Value(1.0));
+        const Document transformedDoc = applyTransformation(doc.freeze());
+        return !transformedDoc.getNestedField(f).missing();
+    }
+
     stdx::unordered_set<std::string> applyProjectionToFields(
         const stdx::unordered_set<std::string>& fields) const {
         stdx::unordered_set<std::string> out;
 
         for (const auto& field : fields) {
-            MutableDocument doc;
-            const FieldPath f = FieldPath(field);
-            doc.setNestedField(f, Value(1.0));
-            const Document transformedDoc = applyTransformation(doc.freeze());
-            if (!(transformedDoc.getNestedField(f).missing()))
+            if (applyProjectionToOneField(field)) {
                 out.insert(field);
+            }
         }
 
         return out;
@@ -137,6 +142,10 @@ BSONObj ProjectionExecAgg::applyProjection(BSONObj inputDoc) const {
     return _exec->applyProjection(inputDoc);
 }
 
+bool ProjectionExecAgg::applyProjectionToOneField(StringData field) const {
+    return _exec->applyProjectionToOneField(field);
+}
+
 stdx::unordered_set<std::string> ProjectionExecAgg::applyProjectionToFields(
     const stdx::unordered_set<std::string>& fields) const {
     return _exec->applyProjectionToFields(fields);
diff --git a/src/mongo/db/exec/projection_exec_agg.h b/src/mongo/db/exec/projection_exec_agg.h
index 6989478b812..90ad2b7ef55 100644
--- a/src/mongo/db/exec/projection_exec_agg.h
+++ b/src/mongo/db/exec/projection_exec_agg.h
@@ -68,6 +68,12 @@ public:
         const stdx::unordered_set<std::string>& fields) const;
 
     /**
+     * Apply the projection to a single field name. Returns whether or not the projection would
+     * allow that field to remain in a document.
+     **/
+    bool applyProjectionToOneField(StringData field) const;
+
+    /**
      * Returns the exhaustive set of all paths that will be preserved by this projection, or an
      * empty set if the exhaustive set cannot be determined. An inclusion will always produce an
      * exhaustive set; an exclusion will always produce an empty set.
diff --git a/src/mongo/db/exec/subplan.cpp b/src/mongo/db/exec/subplan.cpp
index d6a78a3853e..fff6d71f1e3 100644
--- a/src/mongo/db/exec/subplan.cpp
+++ b/src/mongo/db/exec/subplan.cpp
@@ -108,7 +108,9 @@ Status SubplanStage::planSubqueries() {
     _orExpression = _query->root()->shallowClone();
     for (size_t i = 0; i < _plannerParams.indices.size(); ++i) {
         const IndexEntry& ie = _plannerParams.indices[i];
-        _indexMap[ie.name] = i;
+        const auto insertionRes = _indexMap.insert(std::make_pair(ie.identifier, i));
+        // Be sure the key was not already in the map.
+        invariant(insertionRes.second);
         LOG(5) << "Subplanner: index " << i << " is " << ie;
     }
 
@@ -185,7 +187,7 @@ namespace {
 Status tagOrChildAccordingToCache(PlanCacheIndexTree* compositeCacheData,
                                   SolutionCacheData* branchCacheData,
                                   MatchExpression* orChild,
-                                  const std::map<StringData, size_t>& indexMap) {
+                                  const std::map<IndexEntry::Identifier, size_t>& indexMap) {
     invariant(compositeCacheData);
 
     // We want a well-formed *indexed* solution.
diff --git a/src/mongo/db/exec/subplan.h b/src/mongo/db/exec/subplan.h
index a05ac4e2955..862daf5a987 100644
--- a/src/mongo/db/exec/subplan.h
+++ b/src/mongo/db/exec/subplan.h
@@ -196,7 +196,7 @@ private:
     std::vector<std::unique_ptr<BranchPlanningResult>> _branchResults;
 
     // We need this to extract cache-friendly index data from the index assignments.
-    std::map<StringData, size_t> _indexMap;
+    std::map<IndexEntry::Identifier, size_t> _indexMap;
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp
index 62f5e25717d..6c1f4797acf 100644
--- a/src/mongo/db/query/get_executor.cpp
+++ b/src/mongo/db/query/get_executor.cpp
@@ -136,7 +136,7 @@ void fillOutPlannerParams(OperationContext* opCtx,
                                                     ice->getMultikeyPaths(opCtx),
                                                     desc->isSparse(),
                                                     desc->unique(),
-                                                    desc->indexName(),
+                                                    IndexEntry::Identifier{desc->indexName()},
                                                     ice->getFilterExpression(),
                                                     desc->infoObj(),
                                                     ice->getCollator()));
@@ -1447,7 +1447,7 @@ StatusWith<unique_ptr<PlanExecutor, PlanExecutor::Deleter>> getExecutorDistinct(
                                                        ice->getMultikeyPaths(opCtx),
                                                        desc->isSparse(),
                                                        desc->unique(),
-                                                       desc->indexName(),
+                                                       IndexEntry::Identifier{desc->indexName()},
                                                        ice->getFilterExpression(),
                                                        desc->infoObj(),
                                                        ice->getCollator()));
diff --git a/src/mongo/db/query/get_executor_test.cpp b/src/mongo/db/query/get_executor_test.cpp
index 002d4a427b3..0900af8f023 100644
--- a/src/mongo/db/query/get_executor_test.cpp
+++ b/src/mongo/db/query/get_executor_test.cpp
@@ -109,7 +109,8 @@ void testAllowedIndices(std::vector<IndexEntry> indexes,
     filterAllowedIndexEntries(filter, &indexes);
     size_t matchedIndexes = 0;
     for (const auto& indexEntry : indexes) {
-        ASSERT_TRUE(expectedFilteredNames.find(indexEntry.name) != expectedFilteredNames.end());
+        ASSERT_TRUE(expectedFilteredNames.find(indexEntry.identifier.catalogName) !=
+                    expectedFilteredNames.end());
         matchedIndexes++;
     }
     ASSERT_EQ(matchedIndexes, indexes.size());
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index 0130b84f84a..fa2496fd3f0 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -1102,7 +1102,7 @@ TEST(IndexBoundsBuilderTest, ExistsTrueSparse) {
                                       false,  // multikey
                                       true,   // sparse
                                       false,  // unique
-                                      "exists_true_sparse",
+                                      IndexEntry::Identifier{"exists_true_sparse"},
                                       nullptr,  // filterExpr
                                       BSONObj());
     BSONObj obj = fromjson("{a: {$exists: true}}");
diff --git a/src/mongo/db/query/index_entry.cpp b/src/mongo/db/query/index_entry.cpp
index 49898846d45..3d1226140f6 100644
--- a/src/mongo/db/query/index_entry.cpp
+++ b/src/mongo/db/query/index_entry.cpp
@@ -50,7 +50,7 @@ std::string IndexEntry::toString() const {
         sb << " unique";
     }
 
-    sb << " name: '" << name << "'";
+    sb << " name: '" << identifier << "'";
 
     if (filterExpr) {
         sb << " filterExpr: " << filterExpr->toString();
@@ -80,4 +80,14 @@ bool IndexEntry::pathHasMultikeyComponent(StringData indexedField) const {
     MONGO_UNREACHABLE;
 }
 
+std::ostream& operator<<(std::ostream& stream, const IndexEntry::Identifier& ident) {
+    stream << ident.toString();
+    return stream;
+}
+
+StringBuilder& operator<<(StringBuilder& builder, const IndexEntry::Identifier& ident) {
+    builder << ident.toString();
+    return builder;
+}
+
 }  // namespace mongo
diff --git a/src/mongo/db/query/index_entry.h b/src/mongo/db/query/index_entry.h
index 28ac79dfcd1..60e9c84b341 100644
--- a/src/mongo/db/query/index_entry.h
+++ b/src/mongo/db/query/index_entry.h
@@ -44,6 +44,51 @@ class MatchExpression;
  * This name sucks, but every name involving 'index' is used somewhere.
  */
 struct IndexEntry {
+
+    /**
+     * This struct is used to uniquely identify an index. The index "Identifier" has two
+     * components: catalog name, and "disambiguator". The catalog name is just the name of the
+     * index in the catalog. The disambiguator is used by the planner when multiple IndexEntries
+     * may refer to the same underlying index in the catalog. This can only happen with $**
+     * indices. Otherwise, the disambiguator should be empty.
+     *
+     * Has the same comparison and equality semantics as std::pair<string, string>.
+     *
+     */
+    struct Identifier {
+        explicit Identifier(std::string aCatalogName) : catalogName(std::move(aCatalogName)) {}
+
+        Identifier(std::string aCatalogName, std::string nameDisambiguator)
+            : catalogName(std::move(aCatalogName)), disambiguator(std::move(nameDisambiguator)) {}
+
+        bool operator==(const Identifier& other) const {
+            return other.catalogName == catalogName && other.disambiguator == disambiguator;
+        }
+
+        bool operator!=(const Identifier& other) const {
+            return !(*this == other);
+        }
+
+        bool operator<(const Identifier& other) const {
+            const auto cmpRes = catalogName.compare(other.catalogName);
+            if (cmpRes != 0) {
+                return cmpRes < 0;
+            }
+            return disambiguator < other.disambiguator;
+        }
+
+        std::string toString() const {
+            return "(" + catalogName + ", " + disambiguator + ")";
+        }
+
+        // The name of the index in the catalog.
+        std::string catalogName;
+
+        // A string used for disambiguating multiple IndexEntries with the same catalogName (such
+        // as in the case with an allPaths index).
+        std::string disambiguator;
+    };
+
     /**
      * Use this constructor if you're making an IndexEntry from the catalog.
      */
@@ -53,7 +98,7 @@ struct IndexEntry {
                const MultikeyPaths& mkp,
                bool sp,
                bool unq,
-               const std::string& n,
+               Identifier ident,
                const MatchExpression* fe,
                const BSONObj& io,
                const CollatorInterface* ci)
@@ -62,7 +107,7 @@ struct IndexEntry {
           multikeyPaths(mkp),
           sparse(sp),
           unique(unq),
-          name(n),
+          identifier(std::move(ident)),
           filterExpr(fe),
           infoObj(io),
           collator(ci) {
@@ -76,14 +121,14 @@ struct IndexEntry {
                bool mk,
                bool sp,
                bool unq,
-               const std::string& n,
+               Identifier ident,
                const MatchExpression* fe,
                const BSONObj& io)
         : keyPattern(kp),
           multikey(mk),
           sparse(sp),
           unique(unq),
-          name(n),
+          identifier(std::move(ident)),
           filterExpr(fe),
           infoObj(io) {
         type = IndexNames::nameToType(IndexNames::findPluginName(keyPattern));
@@ -97,7 +142,7 @@ struct IndexEntry {
           multikey(false),
           sparse(false),
           unique(false),
-          name(indexName),
+          identifier(indexName),
           filterExpr(nullptr),
           infoObj(BSONObj()) {
         type = IndexNames::nameToType(IndexNames::findPluginName(keyPattern));
@@ -116,7 +161,7 @@ struct IndexEntry {
 
     bool operator==(const IndexEntry& rhs) const {
         // Indexes are logically equal when names are equal.
-        return this->name == rhs.name;
+        return this->identifier == rhs.identifier;
     }
 
     std::string toString() const;
@@ -135,7 +180,7 @@ struct IndexEntry {
 
     bool unique;
 
-    std::string name;
+    Identifier identifier;
 
     const MatchExpression* filterExpr;
 
@@ -151,4 +196,6 @@ struct IndexEntry {
     const CollatorInterface* collator = nullptr;
 };
 
+std::ostream& operator<<(std::ostream& stream, const IndexEntry::Identifier& ident);
+StringBuilder& operator<<(StringBuilder& builder, const IndexEntry::Identifier& ident);
 }  // namespace mongo
diff --git a/src/mongo/db/query/plan_cache.cpp b/src/mongo/db/query/plan_cache.cpp
index cc56811b1ae..49020044448 100644
--- a/src/mongo/db/query/plan_cache.cpp
+++ b/src/mongo/db/query/plan_cache.cpp
@@ -49,7 +49,6 @@
 #include "mongo/util/assert_util.h"
 #include "mongo/util/hex.h"
 #include "mongo/util/log.h"
-#include "mongo/util/mongoutils/str.h"
 #include "mongo/util/transitional_tools_do_not_use/vector_spooling.h"
 
 namespace mongo {
@@ -310,6 +309,37 @@ void encodeGeoNearMatchExpression(const GeoNearMatchExpression* tree, StringBuil
     }
 }
 
+void encodeIndexabilityForDiscriminators(const MatchExpression* tree,
+                                         const IndexToDiscriminatorMap& discriminators,
+                                         StringBuilder* keyBuilder) {
+    for (auto&& indexAndDiscriminatorPair : discriminators) {
+        *keyBuilder << indexAndDiscriminatorPair.second.isMatchCompatibleWithIndex(tree);
+    }
+}
+
+void encodeIndexability(const MatchExpression* tree,
+                        const PlanCacheIndexabilityState& indexabilityState,
+                        StringBuilder* keyBuilder) {
+    if (tree->path().empty()) {
+        return;
+    }
+
+    const IndexToDiscriminatorMap& discriminators =
+        indexabilityState.getDiscriminators(tree->path());
+    IndexToDiscriminatorMap allPathsDiscriminators =
+        indexabilityState.buildAllPathsDiscriminators(tree->path());
+    if (discriminators.empty() && allPathsDiscriminators.empty()) {
+        return;
+    }
+
+    *keyBuilder << kEncodeDiscriminatorsBegin;
+    // For each discriminator on this path, append the character '0' or '1'.
+    encodeIndexabilityForDiscriminators(tree, discriminators, keyBuilder);
+    encodeIndexabilityForDiscriminators(tree, allPathsDiscriminators, keyBuilder);
+
+    *keyBuilder << kEncodeDiscriminatorsEnd;
+}
+
 }  // namespace
 
 //
@@ -493,7 +523,7 @@ std::string PlanCacheIndexTree::toString(int indents) const {
     } else {
         result << std::string(3 * indents, '-') << "Leaf ";
         if (NULL != entry.get()) {
-            result << entry->name << ", pos: " << index_pos << ", can combine? "
+            result << entry->identifier << ", pos: " << index_pos << ", can combine? "
                    << canCombineBounds;
         }
         for (const auto& orPushdown : orPushdowns) {
@@ -506,7 +536,7 @@ std::string PlanCacheIndexTree::toString(int indents) const {
                 firstPosition = false;
                 result << position;
             }
-            result << ": " << orPushdown.indexName << ", pos: " << orPushdown.position
+            result << ": " << orPushdown.indexEntryId << " pos: " << orPushdown.position
                    << ", can combine? " << orPushdown.canCombineBounds << ". ";
         }
         result << '\n';
@@ -601,17 +631,7 @@ void PlanCache::encodeKeyForMatch(const MatchExpression* tree, StringBuilder* ke
         encodeUserString(flags, keyBuilder);
     }
 
-    // Encode indexability.
-    const IndexToDiscriminatorMap& discriminators =
-        _indexabilityState.getDiscriminators(tree->path());
-    if (!discriminators.empty()) {
-        *keyBuilder << kEncodeDiscriminatorsBegin;
-        // For each discriminator on this path, append the character '0' or '1'.
-        for (auto&& indexAndDiscriminatorPair : discriminators) {
-            *keyBuilder << indexAndDiscriminatorPair.second.isMatchCompatibleWithIndex(tree);
-        }
-        *keyBuilder << kEncodeDiscriminatorsEnd;
-    }
+    encodeIndexability(tree, _indexabilityState, keyBuilder);
 
     // Traverse child nodes.
     // Enclose children in [].
diff --git a/src/mongo/db/query/plan_cache.h b/src/mongo/db/query/plan_cache.h
index a25b93722d1..7a89ce9ae38 100644
--- a/src/mongo/db/query/plan_cache.h
+++ b/src/mongo/db/query/plan_cache.h
@@ -77,7 +77,7 @@ struct PlanCacheIndexTree {
      * or satisfy the first field in the index.
      */
     struct OrPushdown {
-        std::string indexName;
+        IndexEntry::Identifier indexEntryId;
         size_t position;
         bool canCombineBounds;
         std::deque<size_t> route;
diff --git a/src/mongo/db/query/plan_cache_indexability.cpp b/src/mongo/db/query/plan_cache_indexability.cpp
index 4576d34c0ed..c541a2fe4af 100644
--- a/src/mongo/db/query/plan_cache_indexability.cpp
+++ b/src/mongo/db/query/plan_cache_indexability.cpp
@@ -32,6 +32,7 @@
 
 #include "mongo/base/init.h"
 #include "mongo/base/owned_pointer_vector.h"
+#include "mongo/db/index/all_paths_key_generator.h"
 #include "mongo/db/matcher/expression.h"
 #include "mongo/db/matcher/expression_algo.h"
 #include "mongo/db/matcher/expression_internal_expr_eq.h"
@@ -44,22 +45,92 @@
 
 namespace mongo {
 
+namespace {
+
+bool canUseAllPathsIndex(BSONElement elt, MatchExpression::MatchType matchType) {
+    if (elt.type() == BSONType::Object) {
+        return false;
+    }
+
+    if (elt.type() == BSONType::Array) {
+        // We only support equality to empty array.
+        return elt.embeddedObject().isEmpty() && matchType == MatchExpression::EQ;
+    }
+
+    return true;
+}
+
+bool supportedByAllPathsIndex(const MatchExpression* queryExpr) {
+    if (ComparisonMatchExpression::isComparisonMatchExpression(queryExpr)) {
+        const ComparisonMatchExpression* cmpExpr =
+            static_cast<const ComparisonMatchExpression*>(queryExpr);
+
+        return canUseAllPathsIndex(cmpExpr->getData(), cmpExpr->matchType());
+    } else if (queryExpr->matchType() == MatchExpression::MATCH_IN) {
+        const auto* queryExprIn = static_cast<const InMatchExpression*>(queryExpr);
+
+        return std::all_of(
+            queryExprIn->getEqualities().begin(),
+            queryExprIn->getEqualities().end(),
+            [](const BSONElement& elt) { return canUseAllPathsIndex(elt, MatchExpression::EQ); });
+    }
+
+    return true;
+};
+
+bool supportedBySparseIndex(const MatchExpression* queryExpr) {
+    if (queryExpr->matchType() == MatchExpression::EQ) {
+        const auto* queryExprEquality = static_cast<const EqualityMatchExpression*>(queryExpr);
+        return !queryExprEquality->getData().isNull();
+    } else if (queryExpr->matchType() == MatchExpression::MATCH_IN) {
+        const auto* queryExprIn = static_cast<const InMatchExpression*>(queryExpr);
+        return !queryExprIn->hasNull();
+    } else {
+        return true;
+    }
+};
+
+IndexabilityDiscriminator getPartialIndexDiscriminator(const MatchExpression* filterExpr) {
+    return [filterExpr](const MatchExpression* queryExpr) {
+        return expression::isSubsetOf(queryExpr, filterExpr);
+    };
+}
+
+IndexabilityDiscriminator getCollatedIndexDiscriminator(const CollatorInterface* collator) {
+    return [collator](const MatchExpression* queryExpr) {
+        if (const auto* queryExprComparison =
+                dynamic_cast<const ComparisonMatchExpressionBase*>(queryExpr)) {
+            const bool collatorsMatch =
+                CollatorInterface::collatorsMatch(queryExprComparison->getCollator(), collator);
+            const bool isCollatableType =
+                CollationIndexKey::isCollatableType(queryExprComparison->getData().type());
+            return collatorsMatch || !isCollatableType;
+        }
+
+        if (queryExpr->matchType() == MatchExpression::MATCH_IN) {
+            const auto* queryExprIn = static_cast<const InMatchExpression*>(queryExpr);
+            if (CollatorInterface::collatorsMatch(queryExprIn->getCollator(), collator)) {
+                return true;
+            }
+            for (const auto& equality : queryExprIn->getEqualities()) {
+                if (CollationIndexKey::isCollatableType(equality.type())) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        // The predicate never compares strings so it is not affected by collation.
+        return true;
+    };
+}
+}
+
 void PlanCacheIndexabilityState::processSparseIndex(const std::string& indexName,
                                                     const BSONObj& keyPattern) {
     for (BSONElement elem : keyPattern) {
         _pathDiscriminatorsMap[elem.fieldNameStringData()][indexName].addDiscriminator(
-            [](const MatchExpression* queryExpr) {
-                if (queryExpr->matchType() == MatchExpression::EQ) {
-                    const auto* queryExprEquality =
-                        static_cast<const EqualityMatchExpression*>(queryExpr);
-                    return !queryExprEquality->getData().isNull();
-                } else if (queryExpr->matchType() == MatchExpression::MATCH_IN) {
-                    const auto* queryExprIn = static_cast<const InMatchExpression*>(queryExpr);
-                    return !queryExprIn->hasNull();
-                } else {
-                    return true;
-                }
-            });
+            supportedBySparseIndex);
     }
 }
 
@@ -71,43 +142,27 @@ void PlanCacheIndexabilityState::processPartialIndex(const std::string& indexNam
     }
     if (filterExpr->getCategory() != MatchExpression::MatchCategory::kLogical) {
         _pathDiscriminatorsMap[filterExpr->path()][indexName].addDiscriminator(
-            [filterExpr](const MatchExpression* queryExpr) {
-                return expression::isSubsetOf(queryExpr, filterExpr);
-            });
+            getPartialIndexDiscriminator(filterExpr));
     }
 }
 
+void PlanCacheIndexabilityState::processAllPathsIndex(const IndexEntry& ie) {
+    invariant(ie.type == IndexType::INDEX_ALLPATHS);
+
+    _allPathsIndexDiscriminators.emplace_back(
+        AllPathsKeyGenerator::createProjectionExec(ie.keyPattern,
+                                                   ie.infoObj.getObjectField("starPathsTempName")),
+        ie.identifier.catalogName,
+        ie.filterExpr,
+        ie.collator);
+}
+
 void PlanCacheIndexabilityState::processIndexCollation(const std::string& indexName,
                                                        const BSONObj& keyPattern,
                                                        const CollatorInterface* collator) {
     for (BSONElement elem : keyPattern) {
-        _pathDiscriminatorsMap[elem.fieldNameStringData()][indexName].addDiscriminator([collator](
-            const MatchExpression* queryExpr) {
-            if (const auto* queryExprComparison =
-                    dynamic_cast<const ComparisonMatchExpressionBase*>(queryExpr)) {
-                const bool collatorsMatch =
-                    CollatorInterface::collatorsMatch(queryExprComparison->getCollator(), collator);
-                const bool isCollatableType =
-                    CollationIndexKey::isCollatableType(queryExprComparison->getData().type());
-                return collatorsMatch || !isCollatableType;
-            }
-
-            if (queryExpr->matchType() == MatchExpression::MATCH_IN) {
-                const auto* queryExprIn = static_cast<const InMatchExpression*>(queryExpr);
-                if (CollatorInterface::collatorsMatch(queryExprIn->getCollator(), collator)) {
-                    return true;
-                }
-                for (const auto& equality : queryExprIn->getEqualities()) {
-                    if (CollationIndexKey::isCollatableType(equality.type())) {
-                        return false;
-                    }
-                }
-                return true;
-            }
-
-            // The predicate never compares strings so it is not affected by collation.
-            return true;
-        });
+        _pathDiscriminatorsMap[elem.fieldNameStringData()][indexName].addDiscriminator(
+            getCollatedIndexDiscriminator(collator));
     }
 }
 
@@ -124,17 +179,43 @@ const IndexToDiscriminatorMap& PlanCacheIndexabilityState::getDiscriminators(
     return it->second;
 }
 
+IndexToDiscriminatorMap PlanCacheIndexabilityState::buildAllPathsDiscriminators(
+    StringData path) const {
+
+    IndexToDiscriminatorMap ret;
+    for (auto&& allPathsDiscriminator : _allPathsIndexDiscriminators) {
+        if (allPathsDiscriminator.projectionExec->applyProjectionToOneField(path)) {
+            CompositeIndexabilityDiscriminator& cid = ret[allPathsDiscriminator.catalogName];
+
+            cid.addDiscriminator(supportedByAllPathsIndex);
+            cid.addDiscriminator(supportedBySparseIndex);
+            cid.addDiscriminator(getCollatedIndexDiscriminator(allPathsDiscriminator.collator));
+            if (allPathsDiscriminator.filterExpr) {
+                cid.addDiscriminator(
+                    getPartialIndexDiscriminator(allPathsDiscriminator.filterExpr));
+            }
+        }
+    }
+    return ret;
+}
+
 void PlanCacheIndexabilityState::updateDiscriminators(const std::vector<IndexEntry>& indexEntries) {
     _pathDiscriminatorsMap = PathDiscriminatorsMap();
 
     for (const IndexEntry& idx : indexEntries) {
+        if (idx.type == IndexType::INDEX_ALLPATHS) {
+            processAllPathsIndex(idx);
+            continue;
+        }
+
         if (idx.sparse) {
-            processSparseIndex(idx.name, idx.keyPattern);
+            processSparseIndex(idx.identifier.catalogName, idx.keyPattern);
         }
         if (idx.filterExpr) {
-            processPartialIndex(idx.name, idx.filterExpr);
+            processPartialIndex(idx.identifier.catalogName, idx.filterExpr);
         }
-        processIndexCollation(idx.name, idx.keyPattern, idx.collator);
+
+        processIndexCollation(idx.identifier.catalogName, idx.keyPattern, idx.collator);
     }
 }
 
diff --git a/src/mongo/db/query/plan_cache_indexability.h b/src/mongo/db/query/plan_cache_indexability.h
index 3dd4e83ec3e..7f43a60cace 100644
--- a/src/mongo/db/query/plan_cache_indexability.h
+++ b/src/mongo/db/query/plan_cache_indexability.h
@@ -31,6 +31,7 @@
 #include <vector>
 
 #include "mongo/base/disallow_copying.h"
+#include "mongo/db/exec/projection_exec_agg.h"
 #include "mongo/stdx/functional.h"
 #include "mongo/util/string_map.h"
 
@@ -89,17 +90,48 @@ public:
      * Returns a map from index name to discriminator for each index associated with 'path'.
      * Returns an empty set if no discriminators are registered for 'path'.
      *
-     * The object returned by reference is valid until the next call to updateDiscriminators()
-     * or until destruction of 'this', whichever is first.
+     * The object returned by reference is valid until the next call to updateDiscriminators() or
+     * until destruction of 'this', whichever is first.
      */
     const IndexToDiscriminatorMap& getDiscriminators(StringData path) const;
 
     /**
+     * Construct an IndexToDiscriminator map for the given path, only for the allPaths indexes
+     * which have been included in the indexability state.
+     */
+    IndexToDiscriminatorMap buildAllPathsDiscriminators(StringData path) const;
+
+    /**
      * Clears discriminators for all paths, and regenerate them from 'indexEntries'.
      */
     void updateDiscriminators(const std::vector<IndexEntry>& indexEntries);
 
 private:
+    using PathDiscriminatorsMap = StringMap<IndexToDiscriminatorMap>;
+
+    /**
+     * A $** index may index an infinite number of fields. We cannot just store a discriminator for
+     * every possible field that it indexes, so we have to maintain some special context about the
+     * index.
+     */
+    struct AllPathsIndexDiscriminatorContext {
+        AllPathsIndexDiscriminatorContext(std::unique_ptr<ProjectionExecAgg> proj,
+                                          std::string name,
+                                          const MatchExpression* filter,
+                                          const CollatorInterface* coll)
+            : projectionExec(std::move(proj)),
+              catalogName(std::move(name)),
+              filterExpr(filter),
+              collator(coll) {}
+
+        std::unique_ptr<ProjectionExecAgg> projectionExec;
+        std::string catalogName;
+
+        // These are owned by the catalog.
+        const MatchExpression* filterExpr;  // For partial indexes.
+        const CollatorInterface* collator;
+    };
+
     /**
      * Adds sparse index discriminators for the sparse index with the given key pattern to
      * '_pathDiscriminatorsMap'.
@@ -136,10 +168,16 @@ private:
                                const CollatorInterface* collator);
 
     /**
-     * PathDiscriminatorsMap is a map from field path to index name to IndexabilityDiscriminator.
+     * Adds special state for a $** index. When the discriminators are retrieved for a certain
+     * path, appropriate discriminators for the allPaths index will be included if it includes the
+     * given path.
      */
-    using PathDiscriminatorsMap = StringMap<IndexToDiscriminatorMap>;
+    void processAllPathsIndex(const IndexEntry& ie);
+
+    // PathDiscriminatorsMap is a map from field path to index name to IndexabilityDiscriminator.
     PathDiscriminatorsMap _pathDiscriminatorsMap;
+
+    std::vector<AllPathsIndexDiscriminatorContext> _allPathsIndexDiscriminators;
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/plan_cache_indexability_test.cpp b/src/mongo/db/query/plan_cache_indexability_test.cpp
index bebec5ccdeb..bf409593859 100644
--- a/src/mongo/db/query/plan_cache_indexability_test.cpp
+++ b/src/mongo/db/query/plan_cache_indexability_test.cpp
@@ -55,11 +55,11 @@ std::unique_ptr<MatchExpression> parseMatchExpression(const BSONObj& obj,
 TEST(PlanCacheIndexabilityTest, SparseIndexSimple) {
     PlanCacheIndexabilityState state;
     state.updateDiscriminators({IndexEntry(BSON("a" << 1),
-                                           false,    // multikey
-                                           true,     // sparse
-                                           false,    // unique
-                                           "a_1",    // name
-                                           nullptr,  // filterExpr
+                                           false,                          // multikey
+                                           true,                           // sparse
+                                           false,                          // unique
+                                           IndexEntry::Identifier{"a_1"},  // name
+                                           nullptr,                        // filterExpr
                                            BSONObj())});
 
     auto discriminators = state.getDiscriminators("a");
@@ -88,11 +88,11 @@ TEST(PlanCacheIndexabilityTest, SparseIndexSimple) {
 TEST(PlanCacheIndexabilityTest, SparseIndexCompound) {
     PlanCacheIndexabilityState state;
     state.updateDiscriminators({IndexEntry(BSON("a" << 1 << "b" << 1),
-                                           false,      // multikey
-                                           true,       // sparse
-                                           false,      // unique
-                                           "a_1_b_1",  // name
-                                           nullptr,    // filterExpr
+                                           false,                              // multikey
+                                           true,                               // sparse
+                                           false,                              // unique
+                                           IndexEntry::Identifier{"a_1_b_1"},  // name
+                                           nullptr,                            // filterExpr
                                            BSONObj())});
 
     {
@@ -128,10 +128,10 @@ TEST(PlanCacheIndexabilityTest, PartialIndexSimple) {
     std::unique_ptr<MatchExpression> filterExpr(parseMatchExpression(filterObj));
     PlanCacheIndexabilityState state;
     state.updateDiscriminators({IndexEntry(BSON("a" << 1),
-                                           false,  // multikey
-                                           false,  // sparse
-                                           false,  // unique
-                                           "a_1",  // name
+                                           false,                          // multikey
+                                           false,                          // sparse
+                                           false,                          // unique
+                                           IndexEntry::Identifier{"a_1"},  // name
                                            filterExpr.get(),
                                            BSONObj())});
 
@@ -170,10 +170,10 @@ TEST(PlanCacheIndexabilityTest, PartialIndexAnd) {
     std::unique_ptr<MatchExpression> filterExpr(parseMatchExpression(filterObj));
     PlanCacheIndexabilityState state;
     state.updateDiscriminators({IndexEntry(BSON("a" << 1),
-                                           false,  // multikey
-                                           false,  // sparse
-                                           false,  // unique
-                                           "a_1",  // name
+                                           false,                          // multikey
+                                           false,                          // sparse
+                                           false,                          // unique
+                                           IndexEntry::Identifier{"a_1"},  // name
                                            filterExpr.get(),
                                            BSONObj())});
 
@@ -224,17 +224,17 @@ TEST(PlanCacheIndexabilityTest, MultiplePartialIndexes) {
 
     PlanCacheIndexabilityState state;
     state.updateDiscriminators({IndexEntry(BSON("a" << 1),
-                                           false,  // multikey
-                                           false,  // sparse
-                                           false,  // unique
-                                           "a_1",  // name
+                                           false,                          // multikey
+                                           false,                          // sparse
+                                           false,                          // unique
+                                           IndexEntry::Identifier{"a_1"},  // name
                                            filterExpr1.get(),
                                            BSONObj()),
                                 IndexEntry(BSON("b" << 1),
-                                           false,  // multikey
-                                           false,  // sparse
-                                           false,  // unique
-                                           "b_1",  // name
+                                           false,                          // multikey
+                                           false,                          // sparse
+                                           false,                          // unique
+                                           IndexEntry::Identifier{"b_1"},  // name
                                            filterExpr2.get(),
                                            BSONObj())});
 
@@ -297,10 +297,10 @@ TEST(PlanCacheIndexabilityTest, MultiplePartialIndexes) {
 TEST(PlanCacheIndexabilityTest, IndexNeitherSparseNorPartial) {
     PlanCacheIndexabilityState state;
     state.updateDiscriminators({IndexEntry(BSON("a" << 1),
-                                           false,  // multikey
-                                           false,  // sparse
-                                           false,  // unique
-                                           "a_1",  // name
+                                           false,                          // multikey
+                                           false,                          // sparse
+                                           false,                          // unique
+                                           IndexEntry::Identifier{"a_1"},  // name
                                            nullptr,
                                            BSONObj())});
     auto discriminators = state.getDiscriminators("a");
@@ -312,11 +312,11 @@ TEST(PlanCacheIndexabilityTest, IndexNeitherSparseNorPartial) {
 TEST(PlanCacheIndexabilityTest, DiscriminatorForCollationIndicatesWhenCollationsAreCompatible) {
     PlanCacheIndexabilityState state;
     IndexEntry entry(BSON("a" << 1),
-                     false,    // multikey
-                     false,    // sparse
-                     false,    // unique
-                     "a_1",    // name
-                     nullptr,  // filterExpr
+                     false,                          // multikey
+                     false,                          // sparse
+                     false,                          // unique
+                     IndexEntry::Identifier{"a_1"},  // name
+                     nullptr,                        // filterExpr
                      BSONObj());
     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
     entry.collator = &collator;
@@ -393,10 +393,10 @@ TEST(PlanCacheIndexabilityTest, DiscriminatorForCollationIndicatesWhenCollations
 TEST(PlanCacheIndexabilityTest, CompoundIndexCollationDiscriminator) {
     PlanCacheIndexabilityState state;
     state.updateDiscriminators({IndexEntry(BSON("a" << 1 << "b" << 1),
-                                           false,      // multikey
-                                           false,      // sparse
-                                           false,      // unique
-                                           "a_1_b_1",  // name
+                                           false,                              // multikey
+                                           false,                              // sparse
+                                           false,                              // unique
+                                           IndexEntry::Identifier{"a_1_b_1"},  // name
                                            nullptr,
                                            BSONObj())});
 
@@ -409,5 +409,98 @@ TEST(PlanCacheIndexabilityTest, CompoundIndexCollationDiscriminator) {
     ASSERT(discriminatorsB.find("a_1_b_1") != discriminatorsB.end());
 }
 
+TEST(PlanCacheIndexabilityTest, AllPathsDiscriminator) {
+    PlanCacheIndexabilityState state;
+    state.updateDiscriminators({IndexEntry(BSON("a.$**" << 1),
+                                           false,  // multikey
+                                           false,  // sparse
+                                           false,  // unique
+                                           IndexEntry::Identifier{"indexName"},
+                                           nullptr,
+                                           BSONObj())});
+
+    const auto unindexedPathDiscriminators = state.buildAllPathsDiscriminators("notIndexed");
+    ASSERT_EQ(0U, unindexedPathDiscriminators.size());
+
+    auto discriminatorsA = state.buildAllPathsDiscriminators("a");
+    ASSERT_EQ(1U, discriminatorsA.size());
+    ASSERT(discriminatorsA.find("indexName") != discriminatorsA.end());
+
+    const auto disc = discriminatorsA["indexName"];
+
+    ASSERT_TRUE(
+        disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: 'abc'}")).get()));
+
+    // Querying for object values isn't support by allPaths indexes.
+    ASSERT_FALSE(
+        disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: {b: 1}}")).get()));
+    ASSERT_FALSE(disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: {}}")).get()));
+    ASSERT_FALSE(
+        disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: {$lt: {}}}")).get()));
+    // Querying for array values isn't supported by allPaths indexes.
+    ASSERT_FALSE(
+        disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: [1, 2, 3]}")).get()));
+    // Querying for null isn't supported by allPaths indexes.
+    ASSERT_FALSE(
+        disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: null}")).get()));
+
+    // Equality on empty array is supported.
+    ASSERT_TRUE(disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: []}")).get()));
+    // Inequality isn't.
+    ASSERT_FALSE(
+        disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: {$gt: []}}")).get()));
+
+    // Cases which use $in.
+    ASSERT_TRUE(
+        disc.isMatchCompatibleWithIndex(parseMatchExpression(fromjson("{a: {$in: []}}")).get()));
+    ASSERT_TRUE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: {$in: [1, 2, 's']}}")).get()));
+    // Empty array inside the $in.
+    ASSERT_TRUE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: {$in: [1, [], 's']}}")).get()));
+
+    // Objects, non-empty arrays and null inside a $in.
+    ASSERT_FALSE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: {$in: [1, {}, 's']}}")).get()));
+    ASSERT_FALSE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: {$in: [1, {a: 1}, 's']}}")).get()));
+    ASSERT_FALSE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: {$in: [1, [1,2,3], 's']}}")).get()));
+    ASSERT_FALSE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: {$in: [1, 2, null]}}")).get()));
+}
+
+TEST(PlanCacheIndexabilityTest, AllPathsWithCollationDiscriminator) {
+    PlanCacheIndexabilityState state;
+    IndexEntry entry(BSON("a.$**" << 1),
+                     false,  // multikey
+                     false,  // sparse
+                     false,  // unique
+                     IndexEntry::Identifier{"indexName"},
+                     nullptr,
+                     BSONObj());
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    entry.collator = &collator;
+    state.updateDiscriminators({entry});
+
+    const auto unindexedPathDiscriminators = state.buildAllPathsDiscriminators("notIndexed");
+    ASSERT_EQ(0U, unindexedPathDiscriminators.size());
+
+    auto discriminatorsA = state.buildAllPathsDiscriminators("a");
+    ASSERT_EQ(1U, discriminatorsA.size());
+    ASSERT(discriminatorsA.find("indexName") != discriminatorsA.end());
+
+    const auto disc = discriminatorsA["indexName"];
+
+    // Match expression which uses the simple collation isn't compatible.
+    ASSERT_FALSE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: \"hello world\"}"), nullptr).get()));
+    // Match expression which uses the same collation as the index is.
+    ASSERT_TRUE(disc.isMatchCompatibleWithIndex(
+        parseMatchExpression(fromjson("{a: \"hello world\"}"), &collator).get()));
+}
+
+// TODO SERVER-35336: Update this test to use a partial $** index, and be sure indexability
+// discriminators also work for partial indices.
 }  // namespace
 }  // namespace mongo
diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp
index 0faf7902af6..410e7a60d3e 100644
--- a/src/mongo/db/query/plan_cache_test.cpp
+++ b/src/mongo/db/query/plan_cache_test.cpp
@@ -835,17 +835,28 @@ protected:
         // The first false means not multikey.
         // The second false means not sparse.
         // The NULL means no filter expression.
-        params.indices.push_back(
-            IndexEntry(keyPattern, multikey, false, false, indexName, NULL, BSONObj()));
+        params.indices.push_back(IndexEntry(keyPattern,
+                                            multikey,
+                                            false,
+                                            false,
+                                            IndexEntry::Identifier{indexName},
+                                            NULL,
+                                            BSONObj()));
     }
 
     void addIndex(BSONObj keyPattern, const std::string& indexName, bool multikey, bool sparse) {
-        params.indices.push_back(
-            IndexEntry(keyPattern, multikey, sparse, false, indexName, NULL, BSONObj()));
+        params.indices.push_back(IndexEntry(keyPattern,
+                                            multikey,
+                                            sparse,
+                                            false,
+                                            IndexEntry::Identifier{indexName},
+                                            NULL,
+                                            BSONObj()));
     }
 
     void addIndex(BSONObj keyPattern, const std::string& indexName, CollatorInterface* collator) {
-        IndexEntry entry(keyPattern, false, false, false, indexName, NULL, BSONObj());
+        IndexEntry entry(
+            keyPattern, false, false, false, IndexEntry::Identifier{indexName}, NULL, BSONObj());
         entry.collator = collator;
         params.indices.push_back(entry);
     }
@@ -1259,6 +1270,41 @@ TEST_F(CachePlanSelectionTest, AndWithinPolygonWithinCenterSphere) {
                                     "{fetch: {node: {ixscan: {pattern: {a: '2dsphere', b: 1}}}}}");
 }
 
+// $** index
+TEST_F(CachePlanSelectionTest, AllPathsIxScan) {
+    params.indices.push_back(IndexEntry(BSON("$**" << 1),
+                                        IndexNames::ALLPATHS,
+                                        false,  // multikey
+                                        {},     // multikey paths
+                                        true,   // sparse
+                                        false,  // unique
+                                        IndexEntry::Identifier{"anIndex"},
+                                        nullptr,
+                                        BSONObj(),
+                                        nullptr));
+    BSONObj query = fromjson("{a: 1, b: 1}");
+    runQuery(query);
+
+    const auto kPlanA =
+        "{fetch: {node: {ixscan: "
+        "{bounds: {$_path: [['a', 'a', true, true]], a: [[1, 1, true, true]]},"
+        "pattern: {$_path: 1, a:1}}}}}";
+
+    const auto kPlanB =
+        "{fetch: {node: {ixscan: "
+        "{bounds: {$_path: [['b', 'b', true, true]], b: [[1, 1, true, true]]},"
+        "pattern: {$_path: 1, b:1}}}}}";
+
+    assertPlanCacheRecoversSolution(query, kPlanA);
+    assertPlanCacheRecoversSolution(query, kPlanB);
+
+    // Query with fields in a different order, so that index entry expansion results in the list of
+    // indexes being in a different order. Should still yield the same plans.
+    BSONObj queryOtherDir = fromjson("{b: 1, a: 1}");
+    assertPlanCacheRecoversSolution(query, kPlanA);
+    assertPlanCacheRecoversSolution(query, kPlanB);
+}
+
 //
 // tree operations
 //
@@ -1818,11 +1864,11 @@ TEST(PlanCacheTest, ComputeKeyRegexDependsOnFlags) {
 TEST(PlanCacheTest, ComputeKeySparseIndex) {
     PlanCache planCache;
     planCache.notifyOfIndexEntries({IndexEntry(BSON("a" << 1),
-                                               false,    // multikey
-                                               true,     // sparse
-                                               false,    // unique
-                                               "",       // name
-                                               nullptr,  // filterExpr
+                                               false,                       // multikey
+                                               true,                        // sparse
+                                               false,                       // unique
+                                               IndexEntry::Identifier{""},  // name
+                                               nullptr,                     // filterExpr
                                                BSONObj())});
 
     unique_ptr<CanonicalQuery> cqEqNumber(canonicalize("{a: 0}}"));
@@ -1846,10 +1892,10 @@ TEST(PlanCacheTest, ComputeKeyPartialIndex) {
 
     PlanCache planCache;
     planCache.notifyOfIndexEntries({IndexEntry(BSON("a" << 1),
-                                               false,  // multikey
-                                               false,  // sparse
-                                               false,  // unique
-                                               "",     // name
+                                               false,                       // multikey
+                                               false,                       // sparse
+                                               false,                       // unique
+                                               IndexEntry::Identifier{""},  // name
                                                filterExpr.get(),
                                                BSONObj())});
 
@@ -1870,11 +1916,11 @@ TEST(PlanCacheTest, ComputeKeyCollationIndex) {
 
     PlanCache planCache;
     IndexEntry entry(BSON("a" << 1),
-                     false,    // multikey
-                     false,    // sparse
-                     false,    // unique
-                     "",       // name
-                     nullptr,  // filterExpr
+                     false,                       // multikey
+                     false,                       // sparse
+                     false,                       // unique
+                     IndexEntry::Identifier{""},  // name
+                     nullptr,                     // filterExpr
                      BSONObj());
     entry.collator = &collator;
     planCache.notifyOfIndexEntries({entry});
@@ -1919,4 +1965,66 @@ TEST(PlanCacheTest, ComputeKeyCollationIndex) {
               planCache.computeKey(*inContainsStringHasCollation));
 }
 
+TEST(PlanCacheTest, ComputeKeyAllPathsIndex) {
+    PlanCache planCache;
+    IndexEntry entry(BSON("a.$**" << 1),
+                     false,                       // multikey
+                     false,                       // sparse
+                     false,                       // unique
+                     IndexEntry::Identifier{""},  // name
+                     nullptr,                     // filterExpr
+                     BSONObj());
+    planCache.notifyOfIndexEntries({entry});
+
+    // Used to check that two queries have the same shape when no indexes are present.
+    PlanCache planCacheWithNoIndexes;
+
+    // Compatible with index.
+    unique_ptr<CanonicalQuery> usesPathWithScalar(canonicalize("{a: 'abcdef'}"));
+    unique_ptr<CanonicalQuery> usesPathWithEmptyArray(canonicalize("{a: []}"));
+
+    // Not compatible with index.
+    unique_ptr<CanonicalQuery> usesPathWithObject(canonicalize("{a: {b: 'abc'}}"));
+    unique_ptr<CanonicalQuery> usesPathWithArray(canonicalize("{a: [1, 2]}"));
+    unique_ptr<CanonicalQuery> usesPathWithArrayContainingObject(canonicalize("{a: [1, {b: 1}]}"));
+    unique_ptr<CanonicalQuery> usesPathWithEmptyObject(canonicalize("{a: {}}"));
+    unique_ptr<CanonicalQuery> doesNotUsePath(canonicalize("{b: 1234}"));
+
+    // Check that the queries which are compatible with the index have the same key.
+    ASSERT_EQ(planCache.computeKey(*usesPathWithScalar),
+              planCache.computeKey(*usesPathWithEmptyArray));
+
+    // Check that the queries which have the same path as the index, but aren't supported, have
+    // different keys.
+    ASSERT_EQ(planCacheWithNoIndexes.computeKey(*usesPathWithScalar),
+              planCacheWithNoIndexes.computeKey(*usesPathWithObject));
+    ASSERT_NE(planCache.computeKey(*usesPathWithScalar), planCache.computeKey(*usesPathWithObject));
+
+    ASSERT_EQ(planCache.computeKey(*usesPathWithObject), planCache.computeKey(*usesPathWithArray));
+    ASSERT_EQ(planCache.computeKey(*usesPathWithObject),
+              planCache.computeKey(*usesPathWithArrayContainingObject));
+    ASSERT_EQ(planCache.computeKey(*usesPathWithObject),
+              planCache.computeKey(*usesPathWithEmptyObject));
+
+    // The query on 'b' should have a completely different plan cache key (both with and without an
+    // allPaths index).
+    ASSERT_NE(planCacheWithNoIndexes.computeKey(*usesPathWithScalar),
+              planCacheWithNoIndexes.computeKey(*doesNotUsePath));
+    ASSERT_NE(planCache.computeKey(*usesPathWithScalar), planCache.computeKey(*doesNotUsePath));
+    ASSERT_NE(planCacheWithNoIndexes.computeKey(*usesPathWithObject),
+              planCacheWithNoIndexes.computeKey(*doesNotUsePath));
+    ASSERT_NE(planCache.computeKey(*usesPathWithObject), planCache.computeKey(*doesNotUsePath));
+
+    // More complex queries with similar shapes. This is to ensure that plan cache key encoding
+    // correctly traverses the expression tree.
+    auto orQueryAllowed = canonicalize("{$or: [{a: 3}, {a: {$gt: [1,2]}}]}");
+    // Same shape except 'a' is compared to an object.
+    auto orQueryNotAllowed = canonicalize("{$or: [{a: {someobject: 1}}, {a: {$gt: [1,2]}}]}");
+    // The two queries should have the same shape when no indexes are present, but different shapes
+    // when a $** index is present.
+    ASSERT_EQ(planCacheWithNoIndexes.computeKey(*orQueryAllowed),
+              planCacheWithNoIndexes.computeKey(*orQueryNotAllowed));
+    ASSERT_NE(planCache.computeKey(*orQueryAllowed), planCache.computeKey(*orQueryNotAllowed));
+}
+
 }  // namespace
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 86bd638c3fc..888c2c81717 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -56,7 +56,7 @@ std::size_t numPathComponents(StringData path) {
 }
 
 /**
- * Given a single allPaths index, and a set of fields which are being queried, create 'mock'
+ * Given a single allPaths index, and a set of fields which are being queried, create a virtual
  * IndexEntry for each of the appropriate fields.
  */
 void expandIndex(const IndexEntry& allPathsIndex,
@@ -77,10 +77,7 @@ void expandIndex(const IndexEntry& allPathsIndex,
                          {},     // multikey paths
                          true,   // sparse
                          false,  // unique
-                         // TODO: SERVER-35333: for plan caching to work, each IndexEntry must have
-                         // a unique name. We violate that requirement here by giving each
-                         // "expanded" index the same name. This must be fixed.
-                         allPathsIndex.name,
+                         {allPathsIndex.identifier.catalogName, fieldName},
                          allPathsIndex.filterExpr,
                          allPathsIndex.infoObj,
                          allPathsIndex.collator);
@@ -265,18 +262,16 @@ void QueryPlannerIXSelect::getFields(const MatchExpression* node,
     }
 }
 
+void QueryPlannerIXSelect::getFields(const MatchExpression* node,
+                                     stdx::unordered_set<string>* out) {
+    getFields(node, "", out);
+}
+
 // static
 void QueryPlannerIXSelect::findRelevantIndices(const stdx::unordered_set<std::string>& fields,
                                                const std::vector<IndexEntry>& allIndices,
                                                std::vector<IndexEntry>* out) {
     for (auto&& entry : allIndices) {
-        if (entry.type == INDEX_ALLPATHS) {
-            // Should only have one field of the form {"$**" : 1}.
-            invariant(entry.keyPattern.nFields() == 1);
-            expandIndex(entry, fields, out);
-            continue;
-        }
-
         BSONObjIterator it(entry.keyPattern);
         BSONElement elt = it.next();
         if (fields.end() != fields.find(elt.fieldName())) {
@@ -285,6 +280,21 @@ void QueryPlannerIXSelect::findRelevantIndices(const stdx::unordered_set<std::st
     }
 }
 
+std::vector<IndexEntry> QueryPlannerIXSelect::expandIndexes(
+    const stdx::unordered_set<std::string>& fields, const std::vector<IndexEntry>& allIndexes) {
+    std::vector<IndexEntry> out;
+    for (auto&& entry : allIndexes) {
+        if (entry.type == IndexType::INDEX_ALLPATHS) {
+            // Should only have one field of the form {"path.$**" : 1} or {"$**" : 1}.
+            invariant(entry.keyPattern.nFields() == 1);
+            expandIndex(entry, fields, &out);
+        } else {
+            out.push_back(entry);
+        }
+    }
+    return out;
+}
+
 // static
 // This is the public method which does not accept an ElemMatchContext.
 bool QueryPlannerIXSelect::compatible(const BSONElement& keyPatternElt,
diff --git a/src/mongo/db/query/planner_ixselect.h b/src/mongo/db/query/planner_ixselect.h
index 8e2f526b3c1..b1834a1610e 100644
--- a/src/mongo/db/query/planner_ixselect.h
+++ b/src/mongo/db/query/planner_ixselect.h
@@ -46,9 +46,14 @@ public:
     /**
      * Return all the fields in the tree rooted at 'node' that we can use an index on
      * in order to answer the query.
+     */
+    static void getFields(const MatchExpression* node, stdx::unordered_set<std::string>* out);
+
+    /**
+     * Similar to other getFields() method, but with 'prefix' argument which is a path prefix to be
+     * prepended to any fields mentioned in predicates encountered.
      *
-     * The 'prefix' argument is a path prefix to be prepended to any fields mentioned in
-     * predicates encountered.  Some array operators specify a path prefix.
+     * Public for testing.
      */
     static void getFields(const MatchExpression* node,
                           std::string prefix,
@@ -133,6 +138,13 @@ public:
     static void stripUnneededAssignments(MatchExpression* node,
                                          const std::vector<IndexEntry>& indices);
 
+    /**
+     * Given a list of IndexEntries and fields used by a query's match expression, return a list
+     * "expanded" indexes (where the $** indexes in the given list have been expanded).
+     */
+    static std::vector<IndexEntry> expandIndexes(const stdx::unordered_set<std::string>& fields,
+                                                 const std::vector<IndexEntry>& allIndexes);
+
 private:
     /**
      * Used to keep track of if any $elemMatch predicates were encountered when walking a
@@ -160,6 +172,7 @@ private:
                              const std::vector<IndexEntry>& indices,
                              const CollatorInterface* collator,
                              const ElemMatchContext& elemMatchContext);
+
     /**
      * Amend the RelevantTag lists for all predicates in the subtree rooted at 'node' to remove
      * invalid assignments to text indexes.
diff --git a/src/mongo/db/query/planner_ixselect_test.cpp b/src/mongo/db/query/planner_ixselect_test.cpp
index 1602e6f5669..dce6ac86950 100644
--- a/src/mongo/db/query/planner_ixselect_test.cpp
+++ b/src/mongo/db/query/planner_ixselect_test.cpp
@@ -1288,19 +1288,21 @@ TEST(QueryPlannerIXSelectTest, ExpandAllPathsIndices) {
     const auto indexEntry = makeIndexEntry(BSON("$**" << 1), {});
 
     // Case where no fields are specified.
-    std::vector<IndexEntry> result;
-    QueryPlannerIXSelect::findRelevantIndices(stdx::unordered_set<string>(), {indexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(stdx::unordered_set<string>(), {indexEntry});
     ASSERT_TRUE(result.empty());
 
     stdx::unordered_set<string> fields = {"fieldA", "fieldB"};
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {indexEntry}, &result);
-    ASSERT_EQ(result.size(), 2u);
-
+    result = QueryPlannerIXSelect::expandIndexes(fields, {indexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {BSON("fieldA" << 1), BSON("fieldB" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
 
     const auto allPathsIndexWithSubpath = makeIndexEntry(BSON("a.b.$**" << 1), {});
+    fields = {"a.b", "a.b.c", "a.d"};
+    result = QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexWithSubpath});
+    expectedKeyPatterns = {BSON("a.b" << 1), BSON("a.b.c" << 1)};
+    ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
 }
 
 TEST(QueryPlannerIXSelectTest, ExpandAllPathsIndicesInPresenceOfOtherIndices) {
@@ -1310,22 +1312,21 @@ TEST(QueryPlannerIXSelectTest, ExpandAllPathsIndicesInPresenceOfOtherIndices) {
     auto abIndexEntry = makeIndexEntry(BSON("fieldA" << 1 << "fieldB" << 1), {});
 
     const stdx::unordered_set<string> fields = {"fieldA", "fieldB", "fieldC"};
-    std::vector<IndexEntry> result;
     std::vector<BSONObj> expectedKeyPatterns = {
         BSON("fieldA" << 1), BSON("fieldA" << 1), BSON("fieldB" << 1), BSON("fieldC" << 1)};
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {aIndexEntry, allPathsIndexEntry}, &result);
+    auto result = QueryPlannerIXSelect::expandIndexes(fields, {aIndexEntry, allPathsIndexEntry});
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
     result.clear();
 
     expectedKeyPatterns = {
         BSON("fieldB" << 1), BSON("fieldA" << 1), BSON("fieldB" << 1), BSON("fieldC" << 1)};
-    QueryPlannerIXSelect::findRelevantIndices(fields, {bIndexEntry, allPathsIndexEntry}, &result);
+    result = QueryPlannerIXSelect::expandIndexes(fields, {bIndexEntry, allPathsIndexEntry});
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
     result.clear();
 
-    QueryPlannerIXSelect::findRelevantIndices(
-        fields, {aIndexEntry, allPathsIndexEntry, bIndexEntry}, &result);
+    result =
+        QueryPlannerIXSelect::expandIndexes(fields, {aIndexEntry, allPathsIndexEntry, bIndexEntry});
     expectedKeyPatterns = {BSON("fieldA" << 1),
                            BSON("fieldA" << 1),
                            BSON("fieldB" << 1),
@@ -1334,32 +1335,33 @@ TEST(QueryPlannerIXSelectTest, ExpandAllPathsIndicesInPresenceOfOtherIndices) {
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
     result.clear();
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry, abIndexEntry}, &result);
+    result = QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry, abIndexEntry});
     expectedKeyPatterns = {BSON("fieldA" << 1),
                            BSON("fieldB" << 1),
                            BSON("fieldC" << 1),
                            BSON("fieldA" << 1 << "fieldB" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
+    ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
 }
 
-TEST(QueryPlannerIXSelectTest, AllPathsIndicesExcludeIdField) {
-    auto indexEntry = makeIndexEntry(BSON("$**" << 1), {});
+TEST(QueryPlannerIXSelectTest, AllPathsIndexExpansionExcludesIdField) {
+    const auto indexEntry = makeIndexEntry(BSON("$**" << 1), {});
 
     stdx::unordered_set<string> fields = {"_id", "abc", "def"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {indexEntry}, &result);
+    std::vector<IndexEntry> result = QueryPlannerIXSelect::expandIndexes(fields, {indexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {BSON("abc" << 1), BSON("def" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
 }
 
 TEST(QueryPlannerIXSelectTest, AllPathsIndicesExpandedEntryHasCorrectProperties) {
     auto allPathsIndexEntry = makeIndexEntry(BSON("$**" << 1), {});
+    allPathsIndexEntry.identifier = IndexEntry::Identifier("someIndex");
 
     stdx::unordered_set<string> fields = {"abc", "def"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {BSON("abc" << 1), BSON("def" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
 
@@ -1373,9 +1375,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesExpandedEntryHasCorrectProperties)
         // AllPaths indexes are never unique.
         ASSERT_FALSE(ie.unique);
 
-        // TODO SERVER-35333: Check that the name of the generated IndexEntry is different from the
-        // original IndexEntry.
-        ASSERT_EQ(ie.name, allPathsIndexEntry.name);
+        ASSERT_EQ(ie.identifier,
+                  IndexEntry::Identifier(allPathsIndexEntry.identifier.catalogName,
+                                         ie.keyPattern.firstElementFieldName()));
     }
 }
 
@@ -1383,9 +1385,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesExcludeNonMatchingKeySubpath) {
     auto allPathsIndexEntry = makeIndexEntry(BSON("subpath.$**" << 1), {});
 
     stdx::unordered_set<string> fields = {"abc", "def", "subpath.abc", "subpath.def", "subpath"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {
         BSON("subpath.abc" << 1), BSON("subpath.def" << 1), BSON("subpath" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
@@ -1396,9 +1398,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesExcludeNonMatchingPathsWithInclusi
         BSON("$**" << 1), {}, BSON("starPathsTempName" << BSON("abc" << 1 << "subpath.abc" << 1)));
 
     stdx::unordered_set<string> fields = {"abc", "def", "subpath.abc", "subpath.def", "subpath"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {BSON("abc" << 1), BSON("subpath.abc" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
 }
@@ -1408,9 +1410,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesExcludeNonMatchingPathsWithExclusi
         BSON("$**" << 1), {}, BSON("starPathsTempName" << BSON("abc" << 0 << "subpath.abc" << 0)));
 
     stdx::unordered_set<string> fields = {"abc", "def", "subpath.abc", "subpath.def", "subpath"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {
         BSON("def" << 1), BSON("subpath.def" << 1), BSON("subpath" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
@@ -1424,9 +1426,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesWithInclusionProjectionAllowIdExcl
 
     stdx::unordered_set<string> fields = {
         "_id", "abc", "def", "subpath.abc", "subpath.def", "subpath"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {BSON("abc" << 1), BSON("subpath.abc" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
 }
@@ -1439,9 +1441,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesWithInclusionProjectionAllowIdIncl
 
     stdx::unordered_set<string> fields = {
         "_id", "abc", "def", "subpath.abc", "subpath.def", "subpath"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {
         BSON("_id" << 1), BSON("abc" << 1), BSON("subpath.abc" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
@@ -1455,9 +1457,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesWithExclusionProjectionAllowIdIncl
 
     stdx::unordered_set<string> fields = {
         "_id", "abc", "def", "subpath.abc", "subpath.def", "subpath"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {
         BSON("_id" << 1), BSON("def" << 1), BSON("subpath.def" << 1), BSON("subpath" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
@@ -1469,9 +1471,9 @@ TEST(QueryPlannerIXSelectTest, AllPathsIndicesIncludeMatchingInternalNodes) {
 
     stdx::unordered_set<string> fields = {
         "_id", "abc", "def", "subpath.abc", "subpath.def", "subpath"};
-    std::vector<IndexEntry> result;
 
-    QueryPlannerIXSelect::findRelevantIndices(fields, {allPathsIndexEntry}, &result);
+    std::vector<IndexEntry> result =
+        QueryPlannerIXSelect::expandIndexes(fields, {allPathsIndexEntry});
     std::vector<BSONObj> expectedKeyPatterns = {
         BSON("_id" << 1), BSON("subpath.abc" << 1), BSON("subpath.def" << 1), BSON("subpath" << 1)};
     ASSERT_TRUE(indexEntryKeyPatternsMatch(&expectedKeyPatterns, &result));
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index d7cef02ac34..7f867dc025e 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -38,6 +38,7 @@
 #include "mongo/base/string_data.h"
 #include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/db/bson/dotted_path_support.h"
+#include "mongo/db/index/all_paths_key_generator.h"
 #include "mongo/db/matcher/expression_algo.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/matcher/expression_text.h"
@@ -314,11 +315,6 @@ StatusWith<std::unique_ptr<PlanCacheIndexTree>> QueryPlanner::cacheDataFromTagge
             return Status(ErrorCodes::BadValue, "can't cache '2d' index");
         }
 
-        // TODO SERVER-35333: AllPaths indexes cannot currently be cached.
-        if (relevantIndices[itag->index].type == IndexType::INDEX_ALLPATHS) {
-            return Status(ErrorCodes::BadValue, "can't cache 'allPaths' index");
-        }
-
         IndexEntry* ientry = new IndexEntry(relevantIndices[itag->index]);
         indexTree->entry.reset(ientry);
         indexTree->index_pos = itag->pos;
@@ -334,11 +330,6 @@ StatusWith<std::unique_ptr<PlanCacheIndexTree>> QueryPlanner::cacheDataFromTagge
                 return Status(ErrorCodes::BadValue, "can't cache '2d' index");
             }
 
-            // TODO SERVER-35333: AllPaths indexes cannot currently be cached.
-            if (relevantIndices[itag->index].type == IndexType::INDEX_ALLPATHS) {
-                return Status(ErrorCodes::BadValue, "can't cache 'allPaths' index");
-            }
-
             std::unique_ptr<IndexEntry> indexEntry =
                 stdx::make_unique<IndexEntry>(relevantIndices[itag->index]);
             indexTree->entry.reset(indexEntry.release());
@@ -347,12 +338,11 @@ StatusWith<std::unique_ptr<PlanCacheIndexTree>> QueryPlanner::cacheDataFromTagge
         }
 
         for (const auto& dest : orPushdownTag->getDestinations()) {
-            PlanCacheIndexTree::OrPushdown orPushdown;
-            orPushdown.route = dest.route;
             IndexTag* indexTag = static_cast<IndexTag*>(dest.tagData.get());
-            orPushdown.indexName = relevantIndices[indexTag->index].name;
-            orPushdown.position = indexTag->pos;
-            orPushdown.canCombineBounds = indexTag->canCombineBounds;
+            PlanCacheIndexTree::OrPushdown orPushdown{relevantIndices[indexTag->index].identifier,
+                                                      indexTag->pos,
+                                                      indexTag->canCombineBounds,
+                                                      dest.route};
             indexTree->orPushdowns.push_back(std::move(orPushdown));
         }
     }
@@ -372,7 +362,7 @@ StatusWith<std::unique_ptr<PlanCacheIndexTree>> QueryPlanner::cacheDataFromTagge
 // static
 Status QueryPlanner::tagAccordingToCache(MatchExpression* filter,
                                          const PlanCacheIndexTree* const indexTree,
-                                         const map<StringData, size_t>& indexMap) {
+                                         const map<IndexEntry::Identifier, size_t>& indexMap) {
     if (NULL == filter) {
         return Status(ErrorCodes::BadValue, "Cannot tag tree: filter is NULL.");
     }
@@ -404,11 +394,10 @@ Status QueryPlanner::tagAccordingToCache(MatchExpression* filter,
         filter->setTag(new OrPushdownTag());
         OrPushdownTag* orPushdownTag = static_cast<OrPushdownTag*>(filter->getTag());
         for (const auto& orPushdown : indexTree->orPushdowns) {
-            auto index = indexMap.find(orPushdown.indexName);
+            auto index = indexMap.find(orPushdown.indexEntryId);
             if (index == indexMap.end()) {
                 return Status(ErrorCodes::BadValue,
-                              str::stream() << "Did not find index with name: "
-                                            << orPushdown.indexName);
+                              str::stream() << "Did not find index: " << orPushdown.indexEntryId);
             }
             OrPushdownTag::Destination dest;
             dest.route = orPushdown.route;
@@ -419,10 +408,10 @@ Status QueryPlanner::tagAccordingToCache(MatchExpression* filter,
     }
 
     if (indexTree->entry.get()) {
-        map<StringData, size_t>::const_iterator got = indexMap.find(indexTree->entry->name);
+        const auto got = indexMap.find(indexTree->entry->identifier);
         if (got == indexMap.end()) {
             mongoutils::str::stream ss;
-            ss << "Did not find index with name: " << indexTree->entry->name;
+            ss << "Did not find index with name: " << indexTree->entry->identifier.catalogName;
             return Status(ErrorCodes::BadValue, ss);
         }
         if (filter->getTag()) {
@@ -483,14 +472,19 @@ StatusWith<std::unique_ptr<QuerySolution>> QueryPlanner::planFromCache(
            << redact(clone->toString()) << "Cache data:" << endl
            << redact(winnerCacheData.toString());
 
+    stdx::unordered_set<string> fields;
+    QueryPlannerIXSelect::getFields(query.root(), &fields);
+    std::vector<IndexEntry> expandedIndexes =
+        QueryPlannerIXSelect::expandIndexes(fields, params.indices);
+
     // Map from index name to index number.
-    // TODO: can we assume that the index numbering has the same lifetime
-    // as the cache state?
-    map<StringData, size_t> indexMap;
-    for (size_t i = 0; i < params.indices.size(); ++i) {
-        const IndexEntry& ie = params.indices[i];
-        indexMap[ie.name] = i;
-        LOG(5) << "Index " << i << ": " << ie.name;
+    map<IndexEntry::Identifier, size_t> indexMap;
+    for (size_t i = 0; i < expandedIndexes.size(); ++i) {
+        const IndexEntry& ie = expandedIndexes[i];
+        const auto insertionRes = indexMap.insert(std::make_pair(ie.identifier, i));
+        // Be sure the key was not already in the map.
+        invariant(insertionRes.second);
+        LOG(5) << "Index " << i << ": " << ie.identifier;
     }
 
     Status s = tagAccordingToCache(clone.get(), winnerCacheData.tree.get(), indexMap);
@@ -505,7 +499,7 @@ StatusWith<std::unique_ptr<QuerySolution>> QueryPlanner::planFromCache(
 
     // Use the cached index assignments to build solnRoot.
     std::unique_ptr<QuerySolutionNode> solnRoot(QueryPlannerAccess::buildIndexedDataAccess(
-        query, std::move(clone), params.indices, params));
+        query, std::move(clone), expandedIndexes, params));
 
     if (!solnRoot) {
         return Status(ErrorCodes::BadValue,
@@ -582,13 +576,16 @@ StatusWith<std::vector<std::unique_ptr<QuerySolution>>> QueryPlanner::plan(
 
     // Figure out what fields we care about.
     stdx::unordered_set<string> fields;
-    QueryPlannerIXSelect::getFields(query.root(), "", &fields);
+    QueryPlannerIXSelect::getFields(query.root(), &fields);
 
     for (stdx::unordered_set<string>::const_iterator it = fields.begin(); it != fields.end();
          ++it) {
         LOG(5) << "Predicate over field '" << *it << "'";
     }
 
+    vector<IndexEntry> expandedIndexes =
+        QueryPlannerIXSelect::expandIndexes(fields, params.indices);
+
     // Filter our indices so we only look at indices that are over our predicates.
     vector<IndexEntry> relevantIndices;
 
@@ -604,14 +601,14 @@ StatusWith<std::vector<std::unique_ptr<QuerySolution>>> QueryPlanner::plan(
     boost::optional<size_t> hintIndexNumber;
 
     if (hintIndex.isEmpty()) {
-        QueryPlannerIXSelect::findRelevantIndices(fields, params.indices, &relevantIndices);
+        QueryPlannerIXSelect::findRelevantIndices(fields, expandedIndexes, &relevantIndices);
     } else {
         // Sigh.  If the hint is specified it might be using the index name.
         BSONElement firstHintElt = hintIndex.firstElement();
         if (str::equals("$hint", firstHintElt.fieldName()) && String == firstHintElt.type()) {
             string hintName = firstHintElt.String();
             for (size_t i = 0; i < params.indices.size(); ++i) {
-                if (params.indices[i].name == hintName) {
+                if (params.indices[i].identifier.catalogName == hintName) {
                     LOG(5) << "Hint by name specified, restricting indices to "
                            << params.indices[i].keyPattern.toString();
                     relevantIndices.clear();
diff --git a/src/mongo/db/query/query_planner.h b/src/mongo/db/query/query_planner.h
index ce11efaf7ba..88f8d551bad 100644
--- a/src/mongo/db/query/query_planner.h
+++ b/src/mongo/db/query/query_planner.h
@@ -97,7 +97,7 @@ public:
      */
     static Status tagAccordingToCache(MatchExpression* filter,
                                       const PlanCacheIndexTree* const indexTree,
-                                      const std::map<StringData, size_t>& indexMap);
+                                      const std::map<IndexEntry::Identifier, size_t>& indexMap);
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 1c566c78b4e..4b69a1fb8d8 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -4296,7 +4296,7 @@ TEST_F(QueryPlannerTest, TagAccordingToCacheFailsOnBadInput) {
     std::unique_ptr<PlanCacheIndexTree> indexTree(new PlanCacheIndexTree());
     indexTree->setIndexEntry(IndexEntry(BSON("a" << 1), "a_1"));
 
-    std::map<StringData, size_t> indexMap;
+    std::map<IndexEntry::Identifier, size_t> indexMap;
 
     // Null filter.
     Status s = QueryPlanner::tagAccordingToCache(NULL, indexTree.get(), indexMap);
@@ -4311,7 +4311,7 @@ TEST_F(QueryPlannerTest, TagAccordingToCacheFailsOnBadInput) {
     ASSERT_NOT_OK(s);
 
     // Index found once added to the map.
-    indexMap["a_1"_sd] = 0;
+    indexMap[IndexEntry::Identifier{"a_1"}] = 0;
     s = QueryPlanner::tagAccordingToCache(scopedCq->root(), indexTree.get(), indexMap);
     ASSERT_OK(s);
 
diff --git a/src/mongo/db/query/query_planner_test_fixture.cpp b/src/mongo/db/query/query_planner_test_fixture.cpp
index 63ec2465f56..4d11ba10903 100644
--- a/src/mongo/db/query/query_planner_test_fixture.cpp
+++ b/src/mongo/db/query/query_planner_test_fixture.cpp
@@ -62,7 +62,7 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern, bool multikey) {
                                         multikey,
                                         false,  // sparse
                                         false,  // unique
-                                        "hari_king_of_the_stove",
+                                        IndexEntry::Identifier{"hari_king_of_the_stove"},
                                         NULL,  // filterExpr
                                         BSONObj()));
 }
@@ -72,19 +72,20 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern, bool multikey, bool sparse)
                                         multikey,
                                         sparse,
                                         false,  // unique
-                                        "note_to_self_dont_break_build",
+                                        IndexEntry::Identifier{"note_to_self_dont_break_build"},
                                         NULL,  // filterExpr
                                         BSONObj()));
 }
 
 void QueryPlannerTest::addIndex(BSONObj keyPattern, bool multikey, bool sparse, bool unique) {
-    params.indices.push_back(IndexEntry(keyPattern,
-                                        multikey,
-                                        sparse,
-                                        unique,
-                                        "sql_query_walks_into_bar_and_says_can_i_join_you?",
-                                        NULL,  // filterExpr
-                                        BSONObj()));
+    params.indices.push_back(
+        IndexEntry(keyPattern,
+                   multikey,
+                   sparse,
+                   unique,
+                   IndexEntry::Identifier{"sql_query_walks_into_bar_and_says_can_i_join_you?"},
+                   NULL,  // filterExpr
+                   BSONObj()));
 }
 
 void QueryPlannerTest::addIndex(BSONObj keyPattern, BSONObj infoObj) {
@@ -92,7 +93,7 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern, BSONObj infoObj) {
                                         false,  // multikey
                                         false,  // sparse
                                         false,  // unique
-                                        "foo",
+                                        IndexEntry::Identifier{"foo"},
                                         NULL,  // filterExpr
                                         infoObj));
 }
@@ -102,7 +103,7 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern, MatchExpression* filterExpr)
                                         false,  // multikey
                                         false,  // sparse
                                         false,  // unique
-                                        "foo",
+                                        IndexEntry::Identifier{"foo"},
                                         filterExpr,
                                         BSONObj()));
 }
@@ -119,7 +120,8 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern, const MultikeyPaths& multike
     const char name[] = "my_index_with_path_level_multikey_info";
     const MatchExpression* filterExpr = nullptr;
     const BSONObj infoObj;
-    IndexEntry entry(keyPattern, multikey, sparse, unique, name, filterExpr, infoObj);
+    IndexEntry entry(
+        keyPattern, multikey, sparse, unique, IndexEntry::Identifier{name}, filterExpr, infoObj);
     entry.multikeyPaths = multikeyPaths;
     params.indices.push_back(entry);
 }
@@ -131,7 +133,8 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern, const CollatorInterface* col
     const char name[] = "my_index_with_collator";
     const MatchExpression* filterExpr = nullptr;
     const BSONObj infoObj;
-    IndexEntry entry(keyPattern, multikey, sparse, unique, name, filterExpr, infoObj);
+    IndexEntry entry(
+        keyPattern, multikey, sparse, unique, IndexEntry::Identifier{name}, filterExpr, infoObj);
     entry.collator = collator;
     params.indices.push_back(entry);
 }
@@ -145,7 +148,8 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern,
     const auto name = indexName.toString();
     const MatchExpression* filterExpr = nullptr;
     const BSONObj infoObj;
-    IndexEntry entry(keyPattern, multikey, sparse, unique, name, filterExpr, infoObj);
+    IndexEntry entry(
+        keyPattern, multikey, sparse, unique, IndexEntry::Identifier{name}, filterExpr, infoObj);
     entry.collator = collator;
     params.indices.push_back(entry);
 }
@@ -158,7 +162,8 @@ void QueryPlannerTest::addIndex(BSONObj keyPattern,
     const bool multikey = false;
     const char name[] = "my_partial_index_with_collator";
     const BSONObj infoObj;
-    IndexEntry entry(keyPattern, multikey, sparse, unique, name, filterExpr, infoObj);
+    IndexEntry entry(
+        keyPattern, multikey, sparse, unique, IndexEntry::Identifier{name}, filterExpr, infoObj);
     entry.collator = collator;
     params.indices.push_back(entry);
 }
diff --git a/src/mongo/db/query/query_planner_test_lib.cpp b/src/mongo/db/query/query_planner_test_lib.cpp
index 1a7029a6428..0e38e28b489 100644
--- a/src/mongo/db/query/query_planner_test_lib.cpp
+++ b/src/mongo/db/query/query_planner_test_lib.cpp
@@ -290,7 +290,7 @@ bool QueryPlannerTestLib::solutionMatches(const BSONObj& testSoln,
             if (name.type() != BSONType::String) {
                 return false;
             }
-            if (name.valueStringData() != ixn->index.name) {
+            if (name.valueStringData() != ixn->index.identifier.catalogName) {
                 return false;
             }
         }
diff --git a/src/mongo/db/query/query_settings.h b/src/mongo/db/query/query_settings.h
index c924b23d6f4..281721aaa68 100644
--- a/src/mongo/db/query/query_settings.h
+++ b/src/mongo/db/query/query_settings.h
@@ -62,7 +62,7 @@ public:
      */
     bool allows(const IndexEntry& entry) const {
         return indexKeyPatterns.find(entry.keyPattern) != indexKeyPatterns.end() ||
-            indexNames.find(entry.name) != indexNames.end();
+            indexNames.find(entry.identifier.catalogName) != indexNames.end();
     }
 
     // These are the index key patterns and names that
diff --git a/src/mongo/db/query/query_settings_test.cpp b/src/mongo/db/query/query_settings_test.cpp
index ba54a60c998..ef4178268f2 100644
--- a/src/mongo/db/query/query_settings_test.cpp
+++ b/src/mongo/db/query/query_settings_test.cpp
@@ -48,8 +48,20 @@ namespace {
 TEST(QuerySettingsTest, AllowedIndicesFilterAllowsIndexesByName) {
     SimpleBSONObjComparator bsonCmp;
     AllowedIndicesFilter filter(bsonCmp.makeBSONObjSet({fromjson("{a:1}")}), {"a_1"});
-    IndexEntry a_idx(fromjson("{a:1, b:1}"), false, false, false, "a_1", nullptr, BSONObj());
-    IndexEntry ab_idx(fromjson("{a:1, b:1}"), false, false, false, "a_1:2", nullptr, BSONObj());
+    IndexEntry a_idx(fromjson("{a:1, b:1}"),
+                     false,
+                     false,
+                     false,
+                     IndexEntry::Identifier{"a_1"},
+                     nullptr,
+                     BSONObj());
+    IndexEntry ab_idx(fromjson("{a:1, b:1}"),
+                      false,
+                      false,
+                      false,
+                      IndexEntry::Identifier{"a_1:2"},
+                      nullptr,
+                      BSONObj());
 
     ASSERT_TRUE(filter.allows(a_idx));
     ASSERT_FALSE(filter.allows(ab_idx));
@@ -58,8 +70,15 @@ TEST(QuerySettingsTest, AllowedIndicesFilterAllowsIndexesByName) {
 TEST(QuerySettingsTest, AllowedIndicesFilterAllowsIndexesByKeyPattern) {
     SimpleBSONObjComparator bsonCmp;
     AllowedIndicesFilter filter(bsonCmp.makeBSONObjSet({fromjson("{a:1}")}), {"a"});
-    IndexEntry a_idx(fromjson("{a:1}"), false, false, false, "foo", nullptr, BSONObj());
-    IndexEntry ab_idx(fromjson("{a:1, b:1}"), false, false, false, "bar", nullptr, BSONObj());
+    IndexEntry a_idx(
+        fromjson("{a:1}"), false, false, false, IndexEntry::Identifier{"foo"}, nullptr, BSONObj());
+    IndexEntry ab_idx(fromjson("{a:1, b:1}"),
+                      false,
+                      false,
+                      false,
+                      IndexEntry::Identifier{"bar"},
+                      nullptr,
+                      BSONObj());
 
     ASSERT_TRUE(filter.allows(a_idx));
     ASSERT_FALSE(filter.allows(ab_idx));
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index c31fc19008e..5b7d4dbd646 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -185,7 +185,7 @@ void TextNode::appendToString(mongoutils::str::stream* ss, int indent) const {
     addIndent(ss, indent);
     *ss << "TEXT\n";
     addIndent(ss, indent + 1);
-    *ss << "name = " << index.name << '\n';
+    *ss << "name = " << index.identifier.catalogName << '\n';
     addIndent(ss, indent + 1);
     *ss << "keyPattern = " << index.keyPattern.toString() << '\n';
     addIndent(ss, indent + 1);
@@ -521,7 +521,7 @@ void IndexScanNode::appendToString(mongoutils::str::stream* ss, int indent) cons
     addIndent(ss, indent);
     *ss << "IXSCAN\n";
     addIndent(ss, indent + 1);
-    *ss << "indexName = " << index.name << '\n';
+    *ss << "indexName = " << index.identifier.catalogName << '\n';
     *ss << "keyPattern = " << index.keyPattern << '\n';
     if (NULL != filter) {
         addIndent(ss, indent + 1);
@@ -988,7 +988,7 @@ void GeoNear2DNode::appendToString(mongoutils::str::stream* ss, int indent) cons
     addIndent(ss, indent);
     *ss << "GEO_NEAR_2D\n";
     addIndent(ss, indent + 1);
-    *ss << "name = " << index.name << '\n';
+    *ss << "name = " << index.identifier.catalogName << '\n';
     addIndent(ss, indent + 1);
     *ss << "keyPattern = " << index.keyPattern.toString() << '\n';
     addCommon(ss, indent);
@@ -1020,7 +1020,7 @@ void GeoNear2DSphereNode::appendToString(mongoutils::str::stream* ss, int indent
     addIndent(ss, indent);
     *ss << "GEO_NEAR_2DSPHERE\n";
     addIndent(ss, indent + 1);
-    *ss << "name = " << index.name << '\n';
+    *ss << "name = " << index.identifier.catalogName << '\n';
     addIndent(ss, indent + 1);
     *ss << "keyPattern = " << index.keyPattern.toString() << '\n';
     addCommon(ss, indent);
@@ -1080,7 +1080,7 @@ void DistinctNode::appendToString(mongoutils::str::stream* ss, int indent) const
     addIndent(ss, indent);
     *ss << "DISTINCT\n";
     addIndent(ss, indent + 1);
-    *ss << "name = " << index.name << '\n';
+    *ss << "name = " << index.identifier.catalogName << '\n';
     addIndent(ss, indent + 1);
     *ss << "keyPattern = " << index.keyPattern << '\n';
     addIndent(ss, indent + 1);
@@ -1109,7 +1109,7 @@ void CountScanNode::appendToString(mongoutils::str::stream* ss, int indent) cons
     addIndent(ss, indent);
     *ss << "COUNT\n";
     addIndent(ss, indent + 1);
-    *ss << "name = " << index.name << '\n';
+    *ss << "name = " << index.identifier.catalogName << '\n';
     addIndent(ss, indent + 1);
     *ss << "keyPattern = " << index.keyPattern << '\n';
     addIndent(ss, indent + 1);
diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp
index 76e0aba98af..d45f6592308 100644
--- a/src/mongo/db/query/stage_builder.cpp
+++ b/src/mongo/db/query/stage_builder.cpp
@@ -91,18 +91,17 @@ PlanStage* buildStages(OperationContext* opCtx,
                 return nullptr;
             }
 
-            auto descriptor =
-                collection->getIndexCatalog()->findIndexByName(opCtx, ixn->index.name);
+            auto descriptor = collection->getIndexCatalog()->findIndexByName(
+                opCtx, ixn->index.identifier.catalogName);
             invariant(descriptor);
 
             // We use the node's internal name, keyPattern and multikey details here. For $**
             // indexes, these may differ from the information recorded in the index's descriptor.
             IndexScanParams params{*descriptor,
-                                   ixn->index.name,
+                                   ixn->index.identifier.catalogName,
                                    ixn->index.keyPattern,
                                    ixn->index.multikeyPaths,
                                    ixn->index.multikey};
-
             params.bounds = ixn->bounds;
             params.direction = ixn->direction;
             params.addKeyMetadata = ixn->addKeyMetadata;
@@ -246,8 +245,8 @@ PlanStage* buildStages(OperationContext* opCtx,
             params.addPointMeta = node->addPointMeta;
             params.addDistMeta = node->addDistMeta;
 
-            IndexDescriptor* twoDIndex =
-                collection->getIndexCatalog()->findIndexByName(opCtx, node->index.name);
+            IndexDescriptor* twoDIndex = collection->getIndexCatalog()->findIndexByName(
+                opCtx, node->index.identifier.catalogName);
             invariant(twoDIndex);
 
             GeoNear2DStage* nearStage =
@@ -265,16 +264,16 @@ PlanStage* buildStages(OperationContext* opCtx,
             params.addPointMeta = node->addPointMeta;
             params.addDistMeta = node->addDistMeta;
 
-            IndexDescriptor* s2Index =
-                collection->getIndexCatalog()->findIndexByName(opCtx, node->index.name);
+            IndexDescriptor* s2Index = collection->getIndexCatalog()->findIndexByName(
+                opCtx, node->index.identifier.catalogName);
             invariant(s2Index);
 
             return new GeoNear2DSphereStage(params, opCtx, ws, collection, s2Index);
         }
         case STAGE_TEXT: {
             const TextNode* node = static_cast<const TextNode*>(root);
-            IndexDescriptor* desc =
-                collection->getIndexCatalog()->findIndexByName(opCtx, node->index.name);
+            IndexDescriptor* desc = collection->getIndexCatalog()->findIndexByName(
+                opCtx, node->index.identifier.catalogName);
             invariant(desc);
             const FTSAccessMethod* fam =
                 static_cast<FTSAccessMethod*>(collection->getIndexCatalog()->getIndex(desc));
@@ -314,8 +313,8 @@ PlanStage* buildStages(OperationContext* opCtx,
 
             DistinctParams params;
 
-            params.descriptor =
-                collection->getIndexCatalog()->findIndexByName(opCtx, dn->index.name);
+            params.descriptor = collection->getIndexCatalog()->findIndexByName(
+                opCtx, dn->index.identifier.catalogName);
             invariant(params.descriptor);
             params.direction = dn->direction;
             params.bounds = dn->bounds;
@@ -330,14 +329,14 @@ PlanStage* buildStages(OperationContext* opCtx,
                 return nullptr;
             }
 
-            auto descriptor =
-                collection->getIndexCatalog()->findIndexByName(opCtx, csn->index.name);
+            auto descriptor = collection->getIndexCatalog()->findIndexByName(
+                opCtx, csn->index.identifier.catalogName);
             invariant(descriptor);
 
             // We use the node's internal name, keyPattern and multikey details here. For $**
             // indexes, these may differ from the information recorded in the index's descriptor.
             CountScanParams params{*descriptor,
-                                   csn->index.name,
+                                   csn->index.identifier.catalogName,
                                    csn->index.keyPattern,
                                    csn->index.multikeyPaths,
                                    csn->index.multikey};
diff --git a/src/mongo/s/chunk_manager.cpp b/src/mongo/s/chunk_manager.cpp
index 7fca0c2e51b..09addf0d9c2 100644
--- a/src/mongo/s/chunk_manager.cpp
+++ b/src/mongo/s/chunk_manager.cpp
@@ -280,7 +280,7 @@ IndexBounds ChunkManager::getIndexBoundsForQuery(const BSONObj& key,
                           MultikeyPaths{},
                           false /* sparse */,
                           false /* unique */,
-                          "shardkey",
+                          IndexEntry::Identifier{"shardkey"},
                           NULL /* filterExpr */,
                           BSONObj(),
                           NULL /* collator */);