SERVER-22400 Compute multikey paths in BtreeKeyGeneratorV1::getKeys().

Propagates information about the prefixes of the indexed fields that
cause the index to be multikey as a result of inserting the generated
keys.

6 files changed, 468 insertions, 175 deletions

diff --git a/src/mongo/db/exec/sort_key_generator.cpp b/src/mongo/db/exec/sort_key_generator.cpp
index f7337a586c0..f186d9617ac 100644
--- a/src/mongo/db/exec/sort_key_generator.cpp
+++ b/src/mongo/db/exec/sort_key_generator.cpp
@@ -177,7 +177,10 @@ StatusWith<BSONObj> SortKeyGenerator::getSortKeyFromObject(const WorkingSetMembe
     BSONObjSet keys(patternCmp);
 
     try {
-        _keyGen->getKeys(member.obj.value(), &keys);
+        // There's no need to compute the prefixes of the indexed fields that cause the index to be
+        // multikey when getting the index keys for sorting.
+        MultikeyPaths* multikeyPaths = nullptr;
+        _keyGen->getKeys(member.obj.value(), &keys, multikeyPaths);
     } catch (const UserException& e) {
         // Probably a parallel array.
         if (BtreeKeyGenerator::ParallelArraysCode == e.getCode()) {
diff --git a/src/mongo/db/index/btree_access_method.cpp b/src/mongo/db/index/btree_access_method.cpp
index 6bc97956fe8..40c4bc77251 100644
--- a/src/mongo/db/index/btree_access_method.cpp
+++ b/src/mongo/db/index/btree_access_method.cpp
@@ -62,7 +62,11 @@ BtreeAccessMethod::BtreeAccessMethod(IndexCatalogEntry* btreeState, SortedDataIn
 }
 
 void BtreeAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
-    _keyGenerator->getKeys(obj, keys);
+    // SERVER-22726 represents the work to gather and persist the path-level multikey information.
+    // Until that's done, we may as well avoid computing the prefixes of the indexed fields that
+    // cause the index to be multikey.
+    MultikeyPaths* multikeyPaths = nullptr;
+    _keyGenerator->getKeys(obj, keys, multikeyPaths);
 }
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_key_generator.cpp b/src/mongo/db/index/btree_key_generator.cpp
index e323272b044..ccf4df2de96 100644
--- a/src/mongo/db/index/btree_key_generator.cpp
+++ b/src/mongo/db/index/btree_key_generator.cpp
@@ -26,8 +26,12 @@
 *    it in the license file.
 */
 
-#include "mongo/bson/bsonobjbuilder.h"
 #include "mongo/db/index/btree_key_generator.h"
+
+#include <boost/optional.hpp>
+
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/field_ref.h"
 #include "mongo/util/mongoutils/str.h"
 
 namespace mongo {
@@ -58,7 +62,9 @@ BtreeKeyGenerator::BtreeKeyGenerator(std::vector<const char*> fieldNames,
     _isIdIndex = fieldNames.size() == 1 && std::string("_id") == fieldNames[0];
 }
 
-void BtreeKeyGenerator::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+void BtreeKeyGenerator::getKeys(const BSONObj& obj,
+                                BSONObjSet* keys,
+                                MultikeyPaths* multikeyPaths) const {
     if (_isIdIndex) {
         // we special case for speed
         BSONElement e = obj["_id"];
@@ -76,7 +82,7 @@ void BtreeKeyGenerator::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
 
     // '_fieldNames' and '_fixed' are passed by value so that they can be mutated as part of the
     // getKeys call.  :|
-    getKeysImpl(_fieldNames, _fixed, obj, keys);
+    getKeysImpl(_fieldNames, _fixed, obj, keys, multikeyPaths);
     if (keys->empty() && !_isSparse) {
         keys->insert(_nullKey);
     }
@@ -96,7 +102,8 @@ BtreeKeyGeneratorV0::BtreeKeyGeneratorV0(std::vector<const char*> fieldNames,
 void BtreeKeyGeneratorV0::getKeysImpl(std::vector<const char*> fieldNames,
                                       std::vector<BSONElement> fixed,
                                       const BSONObj& obj,
-                                      BSONObjSet* keys) const {
+                                      BSONObjSet* keys,
+                                      MultikeyPaths* multikeyPaths) const {
     BSONElement arrElt;
     unsigned arrIdx = ~0;
     unsigned numNotFound = 0;
@@ -181,7 +188,7 @@ void BtreeKeyGeneratorV0::getKeysImpl(std::vector<const char*> fieldNames,
             while (i.more()) {
                 BSONElement e = i.next();
                 if (e.type() == Object) {
-                    getKeysImpl(fieldNames, fixed, e.embeddedObject(), keys);
+                    getKeysImpl(fieldNames, fixed, e.embeddedObject(), keys, multikeyPaths);
                 }
             }
         } else {
@@ -210,7 +217,13 @@ void BtreeKeyGeneratorV0::getKeysImpl(std::vector<const char*> fieldNames,
 BtreeKeyGeneratorV1::BtreeKeyGeneratorV1(std::vector<const char*> fieldNames,
                                          std::vector<BSONElement> fixed,
                                          bool isSparse)
-    : BtreeKeyGenerator(fieldNames, fixed, isSparse), _emptyPositionalInfo(fieldNames.size()) {}
+    : BtreeKeyGenerator(fieldNames, fixed, isSparse), _emptyPositionalInfo(fieldNames.size()) {
+    for (const char* fieldName : fieldNames) {
+        size_t pathLength = FieldRef{fieldName}.numParts();
+        invariant(pathLength > 0);
+        _pathLengths.push_back(pathLength);
+    }
+}
 
 BSONElement BtreeKeyGeneratorV1::extractNextElement(const BSONObj& obj,
                                                     const PositionalPathInfo& positionalInfo,
@@ -242,19 +255,18 @@ BSONElement BtreeKeyGeneratorV1::extractNextElement(const BSONObj& obj,
     return BSONElement();
 }
 
-void BtreeKeyGeneratorV1::_getKeysArrEltFixed(
-    std::vector<const char*>* fieldNames,
-    std::vector<BSONElement>* fixed,
-    const BSONElement& arrEntry,
-    BSONObjSet* keys,
-    unsigned numNotFound,
-    const BSONElement& arrObjElt,
-    const std::set<unsigned>& arrIdxs,
-    bool mayExpandArrayUnembedded,
-    const std::vector<PositionalPathInfo>& positionalInfo) const {
+void BtreeKeyGeneratorV1::_getKeysArrEltFixed(std::vector<const char*>* fieldNames,
+                                              std::vector<BSONElement>* fixed,
+                                              const BSONElement& arrEntry,
+                                              BSONObjSet* keys,
+                                              unsigned numNotFound,
+                                              const BSONElement& arrObjElt,
+                                              const std::set<size_t>& arrIdxs,
+                                              bool mayExpandArrayUnembedded,
+                                              const std::vector<PositionalPathInfo>& positionalInfo,
+                                              MultikeyPaths* multikeyPaths) const {
     // Set up any terminal array values.
-    for (std::set<unsigned>::const_iterator j = arrIdxs.begin(); j != arrIdxs.end(); ++j) {
-        unsigned idx = *j;
+    for (const auto idx : arrIdxs) {
         if (*(*fieldNames)[idx] == '\0') {
             (*fixed)[idx] = mayExpandArrayUnembedded ? arrEntry : arrObjElt;
         }
@@ -266,14 +278,19 @@ void BtreeKeyGeneratorV1::_getKeysArrEltFixed(
                          arrEntry.type() == Object ? arrEntry.embeddedObject() : BSONObj(),
                          keys,
                          numNotFound,
-                         positionalInfo);
+                         positionalInfo,
+                         multikeyPaths);
 }
 
 void BtreeKeyGeneratorV1::getKeysImpl(std::vector<const char*> fieldNames,
                                       std::vector<BSONElement> fixed,
                                       const BSONObj& obj,
-                                      BSONObjSet* keys) const {
-    getKeysImplWithArray(fieldNames, fixed, obj, keys, 0, _emptyPositionalInfo);
+                                      BSONObjSet* keys,
+                                      MultikeyPaths* multikeyPaths) const {
+    if (multikeyPaths) {
+        multikeyPaths->resize(fieldNames.size());
+    }
+    getKeysImplWithArray(fieldNames, fixed, obj, keys, 0, _emptyPositionalInfo, multikeyPaths);
 }
 
 void BtreeKeyGeneratorV1::getKeysImplWithArray(
@@ -282,11 +299,38 @@ void BtreeKeyGeneratorV1::getKeysImplWithArray(
     const BSONObj& obj,
     BSONObjSet* keys,
     unsigned numNotFound,
-    const std::vector<PositionalPathInfo>& positionalInfo) const {
+    const std::vector<PositionalPathInfo>& positionalInfo,
+    MultikeyPaths* multikeyPaths) const {
     BSONElement arrElt;
-    std::set<unsigned> arrIdxs;
+
+    // A set containing the position of any indexed fields in the key pattern that traverse through
+    // the 'arrElt' array value.
+    std::set<size_t> arrIdxs;
+
+    // A vector with size equal to the number of elements in the index key pattern. Each element in
+    // the vector, if initialized, refers to the component within the indexed field that traverses
+    // through the 'arrElt' array value. We say that this component within the indexed field
+    // corresponds to a path that causes the index to be multikey if the 'arrElt' array value
+    // contains multiple elements.
+    //
+    // For example, consider the index {'a.b': 1, 'a.c'} and the document
+    // {a: [{b: 1, c: 'x'}, {b: 2, c: 'y'}]}. The path "a" causes the index to be multikey, so we'd
+    // have a std::vector<boost::optional<size_t>>{{0U}, {0U}}.
+    //
+    // Furthermore, due to how positional key patterns are specified, it's possible for an indexed
+    // field to cause the index to be multikey at a different component than another indexed field
+    // that also traverses through the 'arrElt' array value. It's then also possible for an indexed
+    // field not to cause the index to be multikey, even if it traverses through the 'arrElt' array
+    // value, because only a particular element would be indexed.
+    //
+    // For example, consider the index {'a.b': 1, 'a.b.0'} and the document {a: {b: [1, 2]}}. The
+    // path "a.b" causes the index to be multikey, but the key pattern "a.b.0" only indexes the
+    // first element of the array, so we'd have a
+    // std::vector<boost::optional<size_t>>{{1U}, boost::none}.
+    std::vector<boost::optional<size_t>> arrComponents(fieldNames.size());
+
     bool mayExpandArrayUnembedded = true;
-    for (unsigned i = 0; i < fieldNames.size(); ++i) {
+    for (size_t i = 0; i < fieldNames.size(); ++i) {
         if (*fieldNames[i] == '\0') {
             continue;
         }
@@ -340,7 +384,8 @@ void BtreeKeyGeneratorV1::getKeysImplWithArray(
                             arrElt,
                             arrIdxs,
                             true,
-                            _emptyPositionalInfo);
+                            _emptyPositionalInfo,
+                            multikeyPaths);
     } else {
         BSONObj arrObj = arrElt.embeddedObject();
 
@@ -350,21 +395,61 @@ void BtreeKeyGeneratorV1::getKeysImplWithArray(
         // array element).
         std::vector<PositionalPathInfo> subPositionalInfo(fixed.size());
         for (size_t i = 0; i < fieldNames.size(); ++i) {
+            const bool fieldIsArray = arrIdxs.find(i) != arrIdxs.end();
+
             if (*fieldNames[i] == '\0') {
                 // We've reached the end of the path.
+                if (multikeyPaths && fieldIsArray && mayExpandArrayUnembedded) {
+                    // The 'arrElt' array value isn't expanded into multiple elements when the last
+                    // component of the indexed field is positional and 'arrElt' contains nested
+                    // array values. In all other cases, the 'arrElt' array value may be expanded
+                    // into multiple element and can therefore cause the index to be multikey.
+                    arrComponents[i] = _pathLengths[i] - 1;
+                }
                 continue;
             }
 
+            // The earlier call to BSONObj::getFieldDottedOrArray(fieldNames[i]) modified
+            // fieldNames[i] to refer to the suffix of the path immediately following the 'arrElt'
+            // array value. If we haven't reached the end of this indexed field yet, then we must
+            // have traversed through 'arrElt'.
+            invariant(fieldIsArray);
+
             StringData part = fieldNames[i];
             part = part.substr(0, part.find('.'));
             subPositionalInfo[i].positionallyIndexedElt = arrObj[part];
             if (subPositionalInfo[i].positionallyIndexedElt.eoo()) {
-                // Not indexing an array by position.
+                // We aren't indexing a particular element of the 'arrElt' array value, so it may be
+                // expanded into multiple elements. It can therefore cause the index to be multikey.
+                if (multikeyPaths) {
+                    // We need to determine which component of the indexed field causes the index to
+                    // be multikey as a result of the 'arrElt' array value. Since
+                    //
+                    //   NumComponents("<pathPrefix>") + NumComponents("<pathSuffix>")
+                    //       = NumComponents("<pathPrefix>.<pathSuffix>"),
+                    //
+                    // we can compute the number of components in a prefix of the indexed field by
+                    // subtracting the number of components in the suffix 'fieldNames[i]' from the
+                    // number of components in the indexed field '_fieldNames[i]'.
+                    //
+                    // For example, consider the indexed field "a.b.c" and the suffix "c". The path
+                    // "a.b.c" has 3 components and the suffix "c" has 1 component. Subtracting the
+                    // latter from the former yields the number of components in the prefix "a.b",
+                    // i.e. 2.
+                    size_t fullPathLength = _pathLengths[i];
+                    size_t suffixPathLength = FieldRef{fieldNames[i]}.numParts();
+                    invariant(suffixPathLength < fullPathLength);
+                    arrComponents[i] = fullPathLength - suffixPathLength - 1;
+                }
                 continue;
             }
 
             // We're indexing an array element by its position. Traverse the remainder of the
             // field path now.
+            //
+            // Indexing an array element by its position selects a particular element of the
+            // 'arrElt' array value when generating keys. It therefore cannot cause the index to be
+            // multikey.
             subPositionalInfo[i].arrayObj = arrObj;
             subPositionalInfo[i].remainingPath = fieldNames[i];
             subPositionalInfo[i].dottedElt =
@@ -372,18 +457,31 @@ void BtreeKeyGeneratorV1::getKeysImplWithArray(
         }
 
         // Generate a key for each element of the indexed array.
-        BSONObjIterator i(arrObj);
-        while (i.more()) {
+        size_t nArrObjFields = 0;
+        for (const auto arrObjElem : arrObj) {
             _getKeysArrEltFixed(&fieldNames,
                                 &fixed,
-                                i.next(),
+                                arrObjElem,
                                 keys,
                                 numNotFound,
                                 arrElt,
                                 arrIdxs,
                                 mayExpandArrayUnembedded,
-                                subPositionalInfo);
+                                subPositionalInfo,
+                                multikeyPaths);
+            ++nArrObjFields;
+        }
+
+        if (multikeyPaths && nArrObjFields > 1) {
+            // The 'arrElt' array value contains multiple elements, so we say that it causes the
+            // index to be multikey.
+            for (size_t i = 0; i < arrComponents.size(); ++i) {
+                if (auto arrComponent = arrComponents[i]) {
+                    (*multikeyPaths)[i].insert(*arrComponent);
+                }
+            }
         }
     }
 }
+
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_key_generator.h b/src/mongo/db/index/btree_key_generator.h
index cb156354b51..85ada2c2c1a 100644
--- a/src/mongo/db/index/btree_key_generator.h
+++ b/src/mongo/db/index/btree_key_generator.h
@@ -28,8 +28,10 @@
 
 #pragma once
 
-#include <vector>
 #include <set>
+#include <vector>
+
+#include "mongo/db/index/multikey_paths.h"
 #include "mongo/db/jsobj.h"
 
 namespace mongo {
@@ -46,7 +48,7 @@ public:
 
     virtual ~BtreeKeyGenerator() {}
 
-    void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
+    void getKeys(const BSONObj& obj, BSONObjSet* keys, MultikeyPaths* multikeyPaths) const;
 
     static const int ParallelArraysCode;
 
@@ -63,7 +65,8 @@ private:
     virtual void getKeysImpl(std::vector<const char*> fieldNames,
                              std::vector<BSONElement> fixed,
                              const BSONObj& obj,
-                             BSONObjSet* keys) const = 0;
+                             BSONObjSet* keys,
+                             MultikeyPaths* multikeyPaths) const = 0;
 
     std::vector<BSONElement> _fixed;
 };
@@ -77,10 +80,18 @@ public:
     virtual ~BtreeKeyGeneratorV0() {}
 
 private:
-    virtual void getKeysImpl(std::vector<const char*> fieldNames,
-                             std::vector<BSONElement> fixed,
-                             const BSONObj& obj,
-                             BSONObjSet* keys) const;
+    /**
+     * Generates the index keys for the document 'obj' and stores them in the set 'keys'.
+     *
+     * It isn't possible to create a v0 index, so it's unnecessary to track the prefixes of the
+     * indexed fields that cause the index to be mulitkey. This function therefore ignores its
+     * 'multikeyPaths' parameter.
+     */
+    void getKeysImpl(std::vector<const char*> fieldNames,
+                     std::vector<BSONElement> fixed,
+                     const BSONObj& obj,
+                     BSONObjSet* keys,
+                     MultikeyPaths* multikeyPaths) const final;
 };
 
 class BtreeKeyGeneratorV1 : public BtreeKeyGenerator {
@@ -147,18 +158,24 @@ private:
     };
 
     /**
+     * Generates the index keys for the document 'obj' and stores them in the set 'keys'.
+     *
      * @param fieldNames - fields to index, may be postfixes in recursive calls
      * @param fixed - values that have already been identified for their index fields
      * @param obj - object from which keys should be extracted, based on names in fieldNames
      * @param keys - set where index keys are written
-     * @param numNotFound - number of index fields that have already been identified as missing
-     * @param array - array from which keys should be extracted, based on names in fieldNames
-     *        If obj and array are both nonempty, obj will be one of the elements of array.
+     *
+     * If the 'multikeyPaths' pointer is non-null, then it must point to an empty vector. If this
+     * index type supports tracking path-level multikey information, then this function resizes
+     * 'multikeyPaths' to have the same number of elements as the index key pattern and fills each
+     * element with the prefixes of the indexed field that would cause this index to be multikey as
+     * a result of inserting 'keys'.
      */
-    virtual void getKeysImpl(std::vector<const char*> fieldNames,
-                             std::vector<BSONElement> fixed,
-                             const BSONObj& obj,
-                             BSONObjSet* keys) const;
+    void getKeysImpl(std::vector<const char*> fieldNames,
+                     std::vector<BSONElement> fixed,
+                     const BSONObj& obj,
+                     BSONObjSet* keys,
+                     MultikeyPaths* multikeyPaths) const final;
 
     /**
      * This recursive method does the heavy-lifting for getKeysImpl().
@@ -168,7 +185,8 @@ private:
                               const BSONObj& obj,
                               BSONObjSet* keys,
                               unsigned numNotFound,
-                              const std::vector<PositionalPathInfo>& positionalInfo) const;
+                              const std::vector<PositionalPathInfo>& positionalInfo,
+                              MultikeyPaths* multikeyPaths) const;
     /**
      * A call to getKeysImplWithArray() begins by calling this for each field in the key
      * pattern. It uses getFieldDottedOrArray() to traverse the path '*field' in 'obj'.
@@ -217,11 +235,16 @@ private:
                              BSONObjSet* keys,
                              unsigned numNotFound,
                              const BSONElement& arrObjElt,
-                             const std::set<unsigned>& arrIdxs,
+                             const std::set<size_t>& arrIdxs,
                              bool mayExpandArrayUnembedded,
-                             const std::vector<PositionalPathInfo>& positionalInfo) const;
+                             const std::vector<PositionalPathInfo>& positionalInfo,
+                             MultikeyPaths* multikeyPaths) const;
 
     const std::vector<PositionalPathInfo> _emptyPositionalInfo;
+
+    // A vector with size equal to the number of elements in the index key pattern. Each element in
+    // the vector is the number of path components in the indexed field.
+    std::vector<size_t> _pathLengths;
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_key_generator_test.cpp b/src/mongo/db/index/btree_key_generator_test.cpp
index 23792fb9b87..834ce3fa61f 100644
--- a/src/mongo/db/index/btree_key_generator_test.cpp
+++ b/src/mongo/db/index/btree_key_generator_test.cpp
@@ -26,12 +26,17 @@
  *    it in the license file.
  */
 
+#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kIndex
+
+#include "mongo/platform/basic.h"
+
 #include "mongo/db/index/btree_key_generator.h"
 
 #include <iostream>
 
 #include "mongo/db/json.h"
 #include "mongo/unittest/unittest.h"
+#include "mongo/util/log.h"
 
 using namespace mongo;
 using std::unique_ptr;
@@ -56,24 +61,29 @@ std::string dumpKeyset(const BSONObjSet& objs) {
     return ss.str();
 }
 
-bool keysetsMatch(const BSONObjSet& expected, const BSONObjSet& actual) {
-    if (expected.size() != actual.size()) {
-        return false;
-    }
+std::string dumpMultikeyPaths(const MultikeyPaths& multikeyPaths) {
+    std::stringstream ss;
 
-    for (BSONObjSet::iterator i = expected.begin(); i != expected.end(); ++i) {
-        if (actual.end() == actual.find(*i)) {
-            return false;
+    ss << "[ ";
+    for (const auto multikeyComponents : multikeyPaths) {
+        ss << "[ ";
+        for (const auto multikeyComponent : multikeyComponents) {
+            ss << multikeyComponent << " ";
         }
+        ss << "] ";
     }
+    ss << "]";
 
-    return true;
+    return ss.str();
 }
 
 bool testKeygen(const BSONObj& kp,
                 const BSONObj& obj,
                 const BSONObjSet& expectedKeys,
+                const MultikeyPaths& expectedMultikeyPaths,
                 bool sparse = false) {
+    invariant(expectedMultikeyPaths.size() == static_cast<size_t>(kp.nFields()));
+
     //
     // Step 1: construct the btree key generator object, using the
     // index key pattern.
@@ -91,18 +101,28 @@ bool testKeygen(const BSONObj& kp,
     unique_ptr<BtreeKeyGenerator> keyGen(new BtreeKeyGeneratorV1(fieldNames, fixed, sparse));
 
     //
-    // Step 2: ask 'keyGen' to generate index keys for the object 'obj'.
+    // Step 2: ask 'keyGen' to generate index keys for the object 'obj' and report any prefixes of
+    // the indexed fields that would cause the index to be multikey as a result of inserting
+    // 'actualKeys'.
     //
     BSONObjSet actualKeys;
-    keyGen->getKeys(obj, &actualKeys);
+    MultikeyPaths actualMultikeyPaths;
+    keyGen->getKeys(obj, &actualKeys, &actualMultikeyPaths);
 
     //
     // Step 3: check that the results match the expected result.
     //
-    bool match = keysetsMatch(expectedKeys, actualKeys);
+    bool match = (expectedKeys == actualKeys);
     if (!match) {
-        cout << "Expected: " << dumpKeyset(expectedKeys) << ", "
-             << "Actual: " << dumpKeyset(actualKeys) << endl;
+        log() << "Expected: " << dumpKeyset(expectedKeys) << ", "
+              << "Actual: " << dumpKeyset(actualKeys);
+        return false;
+    }
+
+    match = (expectedMultikeyPaths == actualMultikeyPaths);
+    if (!match) {
+        log() << "Expected: " << dumpMultikeyPaths(expectedMultikeyPaths) << ", "
+              << "Actual: " << dumpMultikeyPaths(actualMultikeyPaths);
     }
 
     return match;
@@ -117,7 +137,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromObjectSimple) {
     BSONObj genKeysFrom = fromjson("{b: 4, a: 5}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 5}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromObjectDotted) {
@@ -125,7 +146,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromObjectDotted) {
     BSONObj genKeysFrom = fromjson("{a: {b: 4}, c: 'foo'}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 4}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromArraySimple) {
@@ -135,7 +157,26 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArraySimple) {
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
     expectedKeys.insert(fromjson("{'': 3}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArrayWithIdenticalValues) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{a: [0, 0, 0]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 0}"));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArrayWithEquivalentValues) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{a: [0, NumberInt(0), NumberLong(0)]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 0}"));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromArrayFirstElement) {
@@ -145,7 +186,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArrayFirstElement) {
     expectedKeys.insert(fromjson("{'': 1, '': 2}"));
     expectedKeys.insert(fromjson("{'': 2, '': 2}"));
     expectedKeys.insert(fromjson("{'': 3, '': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromArraySecondElement) {
@@ -155,7 +197,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArraySecondElement) {
     expectedKeys.insert(fromjson("{'': 5, '': 1}"));
     expectedKeys.insert(fromjson("{'': 5, '': 2}"));
     expectedKeys.insert(fromjson("{'': 5, '': 3}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, {0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromSecondLevelArray) {
@@ -165,14 +208,17 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromSecondLevelArray) {
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
     expectedKeys.insert(fromjson("{'': 3}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromParallelArraysBasic) {
     BSONObj keyPattern = fromjson("{'a': 1, 'b': 1}");
     BSONObj genKeysFrom = fromjson("{a: [1, 2, 3], b: [1, 2, 3]}}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectBasic) {
@@ -182,7 +228,18 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectBasic) {
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
     expectedKeys.insert(fromjson("{'': 3}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromSubobjectWithArrayOfSubobjects) {
+    BSONObj keyPattern = fromjson("{'a.b.c': 1}");
+    BSONObj genKeysFrom = fromjson("{a: {b: [{c: 1}, {c: 2}]}}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    MultikeyPaths expectedMultikeyPaths{{1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectCompoundIndex) {
@@ -192,7 +249,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectCompoundIndex) {
     expectedKeys.insert(fromjson("{'': 1, '': 99}"));
     expectedKeys.insert(fromjson("{'': 2, '': 99}"));
     expectedKeys.insert(fromjson("{'': 3, '': 99}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectSingleMissing) {
@@ -203,7 +261,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectSingleMissing) {
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
     expectedKeys.insert(fromjson("{'': 3}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectMissing) {
@@ -211,7 +270,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectMissing) {
     BSONObj genKeysFrom = fromjson("{a: [{foo: 41}, {foo: 41}, {foo: 41}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysMissingField) {
@@ -219,7 +279,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysMissingField) {
     BSONObj genKeysFrom = fromjson("{b: 1}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysSubobjectMissing) {
@@ -227,7 +288,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysSubobjectMissing) {
     BSONObj genKeysFrom = fromjson("{a: [1, 2]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromCompound) {
@@ -235,7 +297,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromCompound) {
     BSONObj genKeysFrom = fromjson("{x: 'a', y: 'b'}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 'a', '': 'b'}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromCompoundMissing) {
@@ -243,7 +306,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromCompoundMissing) {
     BSONObj genKeysFrom = fromjson("{x: 'a'}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 'a', '': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubelementComplex) {
@@ -251,14 +315,18 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubelementComplex) {
     BSONObj genKeysFrom = fromjson("{a:[{b:[2]}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    // Both the 'a' and 'a.b' arrays contain a single element.
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromParallelArraysComplex) {
     BSONObj keyPattern = fromjson("{'a.b': 1, 'a.c': 1}");
     BSONObj genKeysFrom = fromjson("{a:[{b:[1],c:[2]}]}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysAlternateMissing) {
@@ -267,7 +335,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysAlternateMissing) {
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null, '': 2}"));
     expectedKeys.insert(fromjson("{'': 1, '': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromMultiComplex) {
@@ -277,7 +346,30 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromMultiComplex) {
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
     expectedKeys.insert(fromjson("{'': 3}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U, 1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArrayOfSubobjectsWithArrayValues) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b: [1, 2]}, {b: [2, 3]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    MultikeyPaths expectedMultikeyPaths{{0U, 1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArrayOfSubobjectsWithNonDistinctArrayValues) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b: [1, 2, 3]}, {b: [2]}, {b: [3, 1]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    MultikeyPaths expectedMultikeyPaths{{0U, 1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysArrayEmpty) {
@@ -286,22 +378,24 @@ TEST(BtreeKeyGeneratorTest, GetKeysArrayEmpty) {
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a: [1]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    expectedMultikeyPaths[0].clear();
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a: null}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a: []}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleArray) {
@@ -310,7 +404,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleArray) {
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1, '': 1}"));
     expectedKeys.insert(fromjson("{'': 2, '': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleEmptyArray) {
@@ -318,7 +413,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': undefined, '': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromMultiEmptyArray) {
@@ -327,17 +423,19 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromMultiEmptyArray) {
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1, '': 1}"));
     expectedKeys.insert(fromjson("{'': 1, '': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, {0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a: 1, b: [1]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1, '': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    expectedMultikeyPaths[1].clear();
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a: 1, b: []}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1, '': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromNestedEmptyArray) {
@@ -345,7 +443,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromMultiNestedEmptyArray) {
@@ -353,7 +452,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromMultiNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null, '': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromUnevenNestedEmptyArray) {
@@ -361,17 +461,18 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromUnevenNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': undefined, '': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[{b: 1}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': {b:1}, '': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[{b: []}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': {b:[]}, '': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromReverseUnevenNestedEmptyArray) {
@@ -379,66 +480,66 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromReverseUnevenNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null, '': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, SparseReverseUnevenNestedEmptyArray) {
+    const bool sparse = true;
     BSONObj keyPattern = fromjson("{'a.b': 1, 'a': 1}");
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null, '': undefined}"));
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArray) {
+    const bool sparse = true;
     BSONObj keyPattern = fromjson("{'a.b': 1}");
     BSONObj genKeysFrom = fromjson("{a:1}");
     BSONObjSet expectedKeys;
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[]}");
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[{c:1}]}");
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArraySecond) {
+    const bool sparse = true;
     BSONObj keyPattern = fromjson("{z: 1, 'a.b': 1}");
     BSONObj genKeysFrom = fromjson("{a:1}");
     BSONObjSet expectedKeys;
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[]}");
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[{c:1}]}");
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 }
 
 TEST(BtreeKeyGeneratorTest, SparseNonObjectMissingNestedField) {
+    const bool sparse = true;
     BSONObj keyPattern = fromjson("{'a.b': 1}");
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys;
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[1]}");
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[1,{b:1}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    // true means sparse
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+    expectedMultikeyPaths = {{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromIndexedArrayIndex) {
@@ -446,34 +547,37 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromIndexedArrayIndex) {
     BSONObj genKeysFrom = fromjson("{a:[1]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[1]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': [1]}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:{'0':1}}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[{'0':1}]}");
     expectedKeys.clear();
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 
     genKeysFrom = fromjson("{a:[1,{'0':2}]}");
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleIndexedArrayIndex) {
@@ -481,22 +585,23 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleIndexedArrayIndex) {
     BSONObj genKeysFrom = fromjson("{a:[[1]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[[]]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromObjectWithinArray) {
@@ -504,37 +609,38 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromObjectWithinArray) {
     BSONObj genKeysFrom = fromjson("{a:[{b:1}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[{b:[1]}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[{b:[[1]]}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': [1]}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:1}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:[1]}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:[[1]]}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': [1]}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:[]}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': undefined}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFromArrayWithinObjectWithinArray) {
@@ -542,21 +648,26 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArrayWithinObjectWithinArray) {
     BSONObj genKeysFrom = fromjson("{a:[{b:[1]}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, ParallelArraysInNestedObjects) {
     BSONObj keyPattern = fromjson("{'a.a': 1, 'b.a': 1}");
     BSONObj genKeysFrom = fromjson("{a:{a:[1]}, b:{a:[1]}}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 TEST(BtreeKeyGeneratorTest, ParallelArraysUneven) {
     BSONObj keyPattern = fromjson("{'b.a': 1, 'a': 1}");
     BSONObj genKeysFrom = fromjson("{b:{a:[1]}, a:[1,2]}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallel) {
@@ -566,7 +677,8 @@ TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallel) {
     expectedKeys.insert(fromjson("{'': null}"));
     expectedKeys.insert(fromjson("{'': 3}"));
     expectedKeys.insert(fromjson("{'': 4}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U, 2U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallelCompound) {
@@ -576,7 +688,8 @@ TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallelCompound) {
     expectedKeys.insert(fromjson("{'': null, '': null}"));
     expectedKeys.insert(fromjson("{'': 3, '': 5}"));
     expectedKeys.insert(fromjson("{'': 4, '': 5}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U, 2U}, {0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysComplexNestedArrays) {
@@ -588,7 +701,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysComplexNestedArrays) {
     expectedKeys.insert(fromjson("{'':null, '':7, '':null, '':3, '':4}"));
     expectedKeys.insert(fromjson("{'':null, '':7, '':6, '':null, '':null}"));
     expectedKeys.insert(fromjson("{'':1, '':7, '':null, '':{d: 1}, '':4}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U, 1U, 2U}, {0U}, {0U, 1U}, {0U, 1U, 2U}, {0U, 1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. Should future index versions recursively index nested arrays?
@@ -597,7 +711,8 @@ TEST(BtreeKeyGeneratorTest, GetKeys2DArray) {
     BSONObj genKeysFrom = fromjson("{a: [[2]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': [2]}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. Should parallel indexed arrays be allowed? If not, should empty
@@ -606,21 +721,27 @@ TEST(BtreeKeyGeneratorTest, GetKeysParallelEmptyArrays) {
     BSONObj keyPattern = fromjson("{a: 1, b: 1}");
     BSONObj genKeysFrom = fromjson("{a: [], b: []}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysParallelArraysOneArrayEmpty) {
     BSONObj keyPattern = fromjson("{a: 1, b: 1}");
     BSONObj genKeysFrom = fromjson("{a: [], b: [1, 2, 3]}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysParallelArraysOneArrayEmptyNested) {
     BSONObj keyPattern = fromjson("{'a.b.c': 1, 'a.b.d': 1}");
     BSONObj genKeysFrom = fromjson("{a: [{b: [{c: [1, 2, 3], d: []}]}]}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
 // Descriptive test. The semantics for key generation are odd for positional key patterns.
@@ -629,7 +750,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternMissingElement) {
     BSONObj genKeysFrom = fromjson("{a: [{'2': 5}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 5}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. The semantics for key generation are odd for positional key patterns.
@@ -638,7 +760,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray) {
     BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. The semantics for key generation are odd for positional key patterns.
@@ -647,7 +770,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray2) {
     BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5], [3, 4, 6], [0, 1, 2]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': [0, 1, 2]}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. The semantics for key generation are odd for positional key patterns.
@@ -656,7 +780,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray3) {
     BSONObj genKeysFrom = fromjson("{a: [{'0': 1, '1': 2, '2': 5}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 5}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. The semantics for key generation are odd for positional key patterns.
@@ -665,7 +790,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray4) {
     BSONObj genKeysFrom = fromjson("{a: [{b: [[1, 2, 5]]}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. The semantics for key generation are odd for positional key patterns.
@@ -675,7 +801,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray5) {
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
     expectedKeys.insert(fromjson("{'': 6}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{0U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetNullKeyNestedArray) {
@@ -683,7 +810,8 @@ TEST(BtreeKeyGeneratorTest, GetNullKeyNestedArray) {
     BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysUnevenNestedArrays) {
@@ -694,7 +822,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysUnevenNestedArrays) {
     expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 2}"));
     expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 3}"));
     expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 4}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U, 1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. Should we define better semantics for future index versions in the case of
@@ -704,7 +833,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysRepeatedFieldName) {
     BSONObj genKeysFrom = fromjson("{a: 2, a: 3}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. Future index versions may want different or at least more consistent
@@ -715,7 +845,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysEmptyPathPiece) {
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test. Future index versions may want different or at least more consistent
@@ -726,12 +857,13 @@ TEST(BtreeKeyGeneratorTest, GetKeysLastPathPieceEmpty) {
     BSONObj genKeysFrom = fromjson("{a: 2}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a: {'': 2}}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': {'': 2}}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty) {
@@ -739,7 +871,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty) {
     BSONObj genKeysFrom = fromjson("{a: 2}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty2) {
@@ -749,50 +882,76 @@ TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty2) {
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
     expectedKeys.insert(fromjson("{'': 3}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, PositionalKeyPatternParallelArrays) {
     BSONObj keyPattern = fromjson("{a: 1, 'b.0': 1}");
     BSONObj genKeysFrom = fromjson("{a: [1], b: [2]}");
     BSONObjSet expectedKeys;
-    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+    MultikeyPaths expectedMultikeyPaths(keyPattern.nFields());
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths),
+                  UserException);
 }
 
-// Descriptive test.
-TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays) {
+TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_b_Extracts_b_ElementInsideSingleton2DArray) {
     BSONObj keyPattern = fromjson("{'a.0.b': 1}");
     BSONObj genKeysFrom = fromjson("{a: [[{b: 1}]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
-// Descriptive test.
-TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays2) {
+TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_0_b_Extracts_b_ElementInsideSingleton2DArray) {
     BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
     BSONObj genKeysFrom = fromjson("{a: [[{b: 1}]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
-// Descriptive test.
-TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays3) {
+TEST(BtreeKeyGeneratorTest,
+     KeyPattern_a_0_0_b_ExtractsEachValueFrom_b_ArrayInsideSingleton2DArray) {
+    BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[{b: [1, 2, 3]}]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    MultikeyPaths expectedMultikeyPaths{{3U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_0_b_Extracts_b_ElementInsideSingleton3DArray) {
     BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
     BSONObj genKeysFrom = fromjson("{a: [[[ {b: 1} ]]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
-// Descriptive test.
-TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays4) {
+TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_0_b_ExtractsEach_b_ElementInside3DArray) {
+    BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[[{b: 1}, {b: 2}, {b: 3}]]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    MultikeyPaths expectedMultikeyPaths{{2U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_0_b_ExtractsNullFrom4DArray) {
     BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
     BSONObj genKeysFrom = fromjson("{a: [[[[ {b: 1} ]]]]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': null}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays5) {
@@ -800,7 +959,8 @@ TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays5) {
     BSONObj genKeysFrom = fromjson("{a: [{b: [1, 2]}]}");
     BSONObjSet expectedKeys;
     expectedKeys.insert(fromjson("{'': 2}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test.
@@ -812,7 +972,8 @@ TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays6) {
     expectedKeys.insert(fromjson("{'': {b:3}, '': 3, '': 2, '': null, '': 1}"));
     expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 1, '': 1, '': 1, '': 1}"));
     expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 2, '': 2, '': 1, '': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U, 1U}, {2U}, {0U}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 // Descriptive test.
@@ -824,7 +985,8 @@ TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays7) {
     expectedKeys.insert(fromjson("{'': {b:{'0':3}}, '': {'0':3}, '': 2, '': 3, '': 1}"));
     expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 1, '': 1, '': 1, '': 1}"));
     expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 2, '': 2, '': 1, '': 1}"));
-    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U, 1U}, {2U}, {0U}, std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
 }  // namespace
diff --git a/src/mongo/db/index/external_key_generator.cpp b/src/mongo/db/index/external_key_generator.cpp
index e41131632c2..c7f09d78bf0 100644
--- a/src/mongo/db/index/external_key_generator.cpp
+++ b/src/mongo/db/index/external_key_generator.cpp
@@ -87,7 +87,10 @@ void getKeysForUpgradeChecking(const BSONObj& infoObj, const BSONObj& doc, BSONO
         // XXX: do we care about version
         BtreeKeyGeneratorV1 keyGen(fieldNames, fixed, infoObj["sparse"].trueValue());
 
-        keyGen.getKeys(doc, keys);
+        // There's no need to compute the prefixes of the indexed fields that cause the index to be
+        // multikey when checking if any index key is too large.
+        MultikeyPaths* multikeyPaths = nullptr;
+        keyGen.getKeys(doc, keys, multikeyPaths);
     }
 }