SERVER-40825 In-progress index builds only record the set difference of removed and inserted keys on update

10 files changed, 283 insertions, 209 deletions

diff --git a/src/mongo/db/catalog/index_catalog_impl.cpp b/src/mongo/db/catalog/index_catalog_impl.cpp
index 6692d29eca7..76e8c9b02ac 100644
--- a/src/mongo/db/catalog/index_catalog_impl.cpp
+++ b/src/mongo/db/catalog/index_catalog_impl.cpp
@@ -1251,6 +1251,45 @@ const IndexDescriptor* IndexCatalogImpl::refreshEntry(OperationContext* opCtx,
 
 // ---------------------------
 
+Status IndexCatalogImpl::_indexKeys(OperationContext* opCtx,
+                                    IndexCatalogEntry* index,
+                                    const std::vector<BSONObj>& keys,
+                                    const BSONObjSet& multikeyMetadataKeys,
+                                    const MultikeyPaths& multikeyPaths,
+                                    RecordId loc,
+                                    const InsertDeleteOptions& options,
+                                    int64_t* keysInsertedOut) {
+    Status status = Status::OK();
+    if (index->isHybridBuilding()) {
+        int64_t inserted;
+        status = index->indexBuildInterceptor()->sideWrite(opCtx,
+                                                           keys,
+                                                           multikeyMetadataKeys,
+                                                           multikeyPaths,
+                                                           loc,
+                                                           IndexBuildInterceptor::Op::kInsert,
+                                                           &inserted);
+        if (keysInsertedOut) {
+            *keysInsertedOut += inserted;
+        }
+    } else {
+        InsertResult result;
+        status = index->accessMethod()->insertKeys(
+            opCtx,
+            keys,
+            {multikeyMetadataKeys.begin(), multikeyMetadataKeys.end()},
+            multikeyPaths,
+            loc,
+            options,
+            &result);
+        if (keysInsertedOut) {
+            *keysInsertedOut += result.numInserted;
+        }
+    }
+
+    return status;
+}
+
 Status IndexCatalogImpl::_indexFilteredRecords(OperationContext* opCtx,
                                                IndexCatalogEntry* index,
                                                const std::vector<BsonRecord>& bsonRecords,
@@ -1267,32 +1306,26 @@ Status IndexCatalogImpl::_indexFilteredRecords(OperationContext* opCtx,
                 return status;
         }
 
-        Status status = Status::OK();
-        if (index->isHybridBuilding()) {
-            int64_t inserted;
-            status = index->indexBuildInterceptor()->sideWrite(opCtx,
-                                                               index->accessMethod(),
-                                                               bsonRecord.docPtr,
-                                                               options,
-                                                               bsonRecord.id,
-                                                               IndexBuildInterceptor::Op::kInsert,
-                                                               &inserted);
-            if (keysInsertedOut) {
-                *keysInsertedOut += inserted;
-            }
-        } else {
-            InsertResult result;
-            status = index->accessMethod()->insert(
-                opCtx, *bsonRecord.docPtr, bsonRecord.id, options, &result);
-            if (keysInsertedOut) {
-                *keysInsertedOut += result.numInserted;
-            }
-        }
-
+        BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+        BSONObjSet multikeyMetadataKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+        MultikeyPaths multikeyPaths;
+
+        index->accessMethod()->getKeys(
+            *bsonRecord.docPtr, options.getKeysMode, &keys, &multikeyMetadataKeys, &multikeyPaths);
+
+        Status status = _indexKeys(opCtx,
+                                   index,
+                                   {keys.begin(), keys.end()},
+                                   multikeyMetadataKeys,
+                                   multikeyPaths,
+                                   bsonRecord.id,
+                                   options,
+                                   keysInsertedOut);
         if (!status.isOK()) {
             return status;
         }
     }
+
     return Status::OK();
 }
 
@@ -1313,12 +1346,58 @@ Status IndexCatalogImpl::_indexRecords(OperationContext* opCtx,
     return _indexFilteredRecords(opCtx, index, filteredBsonRecords, keysInsertedOut);
 }
 
-Status IndexCatalogImpl::_unindexRecord(OperationContext* opCtx,
-                                        IndexCatalogEntry* index,
-                                        const BSONObj& obj,
-                                        const RecordId& loc,
-                                        bool logIfError,
-                                        int64_t* keysDeletedOut) {
+Status IndexCatalogImpl::_updateRecord(OperationContext* const opCtx,
+                                       IndexCatalogEntry* index,
+                                       const BSONObj& oldDoc,
+                                       const BSONObj& newDoc,
+                                       const RecordId& recordId,
+                                       int64_t* const keysInsertedOut,
+                                       int64_t* const keysDeletedOut) {
+    IndexAccessMethod* iam = index->accessMethod();
+
+    InsertDeleteOptions options;
+    prepareInsertDeleteOptions(opCtx, index->descriptor(), &options);
+
+    UpdateTicket updateTicket;
+
+    iam->prepareUpdate(opCtx, index, oldDoc, newDoc, recordId, options, &updateTicket);
+
+    int64_t keysInserted;
+    int64_t keysDeleted;
+
+    auto status = Status::OK();
+    if (index->isHybridBuilding() || !index->isReady(opCtx)) {
+        bool logIfError = false;
+        _unindexKeys(
+            opCtx, index, updateTicket.removed, oldDoc, recordId, logIfError, &keysDeleted);
+        status = _indexKeys(opCtx,
+                            index,
+                            updateTicket.added,
+                            updateTicket.newMultikeyMetadataKeys,
+                            updateTicket.newMultikeyPaths,
+                            recordId,
+                            options,
+                            &keysInserted);
+    } else {
+        status = iam->update(opCtx, updateTicket, &keysInserted, &keysDeleted);
+    }
+
+    if (!status.isOK())
+        return status;
+
+    *keysInsertedOut += keysInserted;
+    *keysDeletedOut += keysDeleted;
+
+    return Status::OK();
+}
+
+void IndexCatalogImpl::_unindexKeys(OperationContext* opCtx,
+                                    IndexCatalogEntry* index,
+                                    const std::vector<BSONObj>& keys,
+                                    const BSONObj& obj,
+                                    RecordId loc,
+                                    bool logIfError,
+                                    int64_t* const keysDeletedOut) {
     InsertDeleteOptions options;
     prepareInsertDeleteOptions(opCtx, index->descriptor(), &options);
     options.logIfError = logIfError;
@@ -1330,23 +1409,25 @@ Status IndexCatalogImpl::_unindexRecord(OperationContext* opCtx,
         // the IndexAccessMethod. See SERVER-28975 for details.
         if (auto filter = index->getFilterExpression()) {
             if (!filter->matchesBSON(obj)) {
-                return Status::OK();
+                return;
             }
         }
 
         int64_t removed;
-        auto status = index->indexBuildInterceptor()->sideWrite(opCtx,
-                                                                index->accessMethod(),
-                                                                &obj,
-                                                                options,
-                                                                loc,
-                                                                IndexBuildInterceptor::Op::kDelete,
-                                                                &removed);
-        if (status.isOK() && keysDeletedOut) {
+        fassert(31155,
+                index->indexBuildInterceptor()->sideWrite(
+                    opCtx,
+                    keys,
+                    SimpleBSONObjComparator::kInstance.makeBSONObjSet(),
+                    {},
+                    loc,
+                    IndexBuildInterceptor::Op::kDelete,
+                    &removed));
+        if (keysDeletedOut) {
             *keysDeletedOut += removed;
         }
 
-        return status;
+        return;
     }
 
     // On WiredTiger, we do blind unindexing of records for efficiency.  However, when duplicates
@@ -1359,7 +1440,7 @@ Status IndexCatalogImpl::_unindexRecord(OperationContext* opCtx,
     options.dupsAllowed = options.dupsAllowed || !index->isReady(opCtx);
 
     int64_t removed;
-    Status status = index->accessMethod()->remove(opCtx, obj, loc, options, &removed);
+    Status status = index->accessMethod()->removeKeys(opCtx, keys, loc, options, &removed);
 
     if (!status.isOK()) {
         log() << "Couldn't unindex record " << redact(obj) << " from collection "
@@ -1369,8 +1450,23 @@ Status IndexCatalogImpl::_unindexRecord(OperationContext* opCtx,
     if (keysDeletedOut) {
         *keysDeletedOut += removed;
     }
+}
 
-    return Status::OK();
+void IndexCatalogImpl::_unindexRecord(OperationContext* opCtx,
+                                      IndexCatalogEntry* entry,
+                                      const BSONObj& obj,
+                                      const RecordId& loc,
+                                      bool logIfError,
+                                      int64_t* keysDeletedOut) {
+    // There's no need to compute the prefixes of the indexed fields that cause the index to be
+    // multikey when removing a document since the index metadata isn't updated when keys are
+    // deleted.
+    BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+
+    entry->accessMethod()->getKeys(
+        obj, IndexAccessMethod::GetKeysMode::kRelaxConstraintsUnfiltered, &keys, nullptr, nullptr);
+
+    _unindexKeys(opCtx, entry, {keys.begin(), keys.end()}, obj, loc, logIfError, keysDeletedOut);
 }
 
 Status IndexCatalogImpl::indexRecords(OperationContext* opCtx,
@@ -1409,41 +1505,19 @@ Status IndexCatalogImpl::updateRecord(OperationContext* const opCtx,
          it != _readyIndexes.end();
          ++it) {
         IndexCatalogEntry* entry = it->get();
-
-        IndexDescriptor* descriptor = entry->descriptor();
-        IndexAccessMethod* iam = entry->accessMethod();
-
-        InsertDeleteOptions options;
-        prepareInsertDeleteOptions(opCtx, descriptor, &options);
-
-        UpdateTicket updateTicket;
-
-        auto status = iam->validateUpdate(
-            opCtx, oldDoc, newDoc, recordId, options, &updateTicket, entry->getFilterExpression());
-        if (!status.isOK())
-            return status;
-
-        int64_t keysInserted;
-        int64_t keysDeleted;
-        status = iam->update(opCtx, updateTicket, &keysInserted, &keysDeleted);
+        auto status =
+            _updateRecord(opCtx, entry, oldDoc, newDoc, recordId, keysInsertedOut, keysDeletedOut);
         if (!status.isOK())
             return status;
-
-        *keysInsertedOut += keysInserted;
-        *keysDeletedOut += keysDeleted;
     }
 
     // Building indexes go through the interceptor.
-    BsonRecord record{recordId, Timestamp(), &newDoc};
     for (IndexCatalogEntryContainer::const_iterator it = _buildingIndexes.begin();
          it != _buildingIndexes.end();
          ++it) {
         IndexCatalogEntry* entry = it->get();
-
-        bool logIfError = false;
-        invariant(_unindexRecord(opCtx, entry, oldDoc, recordId, logIfError, keysDeletedOut));
-
-        auto status = _indexRecords(opCtx, entry, {record}, keysInsertedOut);
+        auto status =
+            _updateRecord(opCtx, entry, oldDoc, newDoc, recordId, keysInsertedOut, keysDeletedOut);
         if (!status.isOK())
             return status;
     }
@@ -1465,7 +1539,7 @@ void IndexCatalogImpl::unindexRecord(OperationContext* opCtx,
         IndexCatalogEntry* entry = it->get();
 
         bool logIfError = !noWarn;
-        invariant(_unindexRecord(opCtx, entry, obj, loc, logIfError, keysDeletedOut));
+        _unindexRecord(opCtx, entry, obj, loc, logIfError, keysDeletedOut);
     }
 
     for (IndexCatalogEntryContainer::const_iterator it = _buildingIndexes.begin();
@@ -1475,7 +1549,7 @@ void IndexCatalogImpl::unindexRecord(OperationContext* opCtx,
 
         // If it's a background index, we DO NOT want to log anything.
         bool logIfError = entry->isReady(opCtx) ? !noWarn : false;
-        invariant(_unindexRecord(opCtx, entry, obj, loc, logIfError, keysDeletedOut));
+        _unindexRecord(opCtx, entry, obj, loc, logIfError, keysDeletedOut);
     }
 }
 
diff --git a/src/mongo/db/catalog/index_catalog_impl.h b/src/mongo/db/catalog/index_catalog_impl.h
index 21445b5fba9..ddafafb515e 100644
--- a/src/mongo/db/catalog/index_catalog_impl.h
+++ b/src/mongo/db/catalog/index_catalog_impl.h
@@ -373,6 +373,15 @@ private:
 
     void _checkMagic() const;
 
+    Status _indexKeys(OperationContext* opCtx,
+                      IndexCatalogEntry* index,
+                      const std::vector<BSONObj>& keys,
+                      const BSONObjSet& multikeyMetadataKeys,
+                      const MultikeyPaths& multikeyPaths,
+                      RecordId loc,
+                      const InsertDeleteOptions& options,
+                      int64_t* keysInsertedOut);
+
     Status _indexFilteredRecords(OperationContext* opCtx,
                                  IndexCatalogEntry* index,
                                  const std::vector<BsonRecord>& bsonRecords,
@@ -383,12 +392,28 @@ private:
                          const std::vector<BsonRecord>& bsonRecords,
                          int64_t* keysInsertedOut);
 
-    Status _unindexRecord(OperationContext* opCtx,
-                          IndexCatalogEntry* index,
-                          const BSONObj& obj,
-                          const RecordId& loc,
-                          bool logIfError,
-                          int64_t* keysDeletedOut);
+    Status _updateRecord(OperationContext* const opCtx,
+                         IndexCatalogEntry* index,
+                         const BSONObj& oldDoc,
+                         const BSONObj& newDoc,
+                         const RecordId& recordId,
+                         int64_t* const keysInsertedOut,
+                         int64_t* const keysDeletedOut);
+
+    void _unindexKeys(OperationContext* opCtx,
+                      IndexCatalogEntry* index,
+                      const std::vector<BSONObj>& keys,
+                      const BSONObj& obj,
+                      RecordId loc,
+                      bool logIfError,
+                      int64_t* const keysDeletedOut);
+
+    void _unindexRecord(OperationContext* opCtx,
+                        IndexCatalogEntry* entry,
+                        const BSONObj& obj,
+                        const RecordId& loc,
+                        bool logIfError,
+                        int64_t* keysDeletedOut);
 
     /**
      * this does no sanity checks
diff --git a/src/mongo/db/catalog/private/record_store_validate_adaptor.cpp b/src/mongo/db/catalog/private/record_store_validate_adaptor.cpp
index 3d4f68eb66c..2fce67d788a 100644
--- a/src/mongo/db/catalog/private/record_store_validate_adaptor.cpp
+++ b/src/mongo/db/catalog/private/record_store_validate_adaptor.cpp
@@ -113,7 +113,10 @@ Status RecordStoreValidateAdaptor::validate(const RecordId& recordId,
                      &multikeyPaths);
 
         if (!descriptor->isMultikey(_opCtx) &&
-            iam->shouldMarkIndexAsMultikey(documentKeySet, multikeyMetadataKeys, multikeyPaths)) {
+            iam->shouldMarkIndexAsMultikey(
+                {documentKeySet.begin(), documentKeySet.end()},
+                {multikeyMetadataKeys.begin(), multikeyMetadataKeys.end()},
+                multikeyPaths)) {
             std::string msg = str::stream() << "Index " << descriptor->indexName()
                                             << " is not multi-key, but a multikey path "
                                             << " is present in document " << recordId;
diff --git a/src/mongo/db/index/index_access_method.cpp b/src/mongo/db/index/index_access_method.cpp
index d9afab69653..4fd9a9264bc 100644
--- a/src/mongo/db/index/index_access_method.cpp
+++ b/src/mongo/db/index/index_access_method.cpp
@@ -190,12 +190,18 @@ Status AbstractIndexAccessMethod::insert(OperationContext* opCtx,
     // Delegate to the subclass.
     getKeys(obj, options.getKeysMode, &keys, &multikeyMetadataKeys, &multikeyPaths);
 
-    return insertKeys(opCtx, keys, multikeyMetadataKeys, multikeyPaths, loc, options, result);
+    return insertKeys(opCtx,
+                      {keys.begin(), keys.end()},
+                      {multikeyMetadataKeys.begin(), multikeyMetadataKeys.end()},
+                      multikeyPaths,
+                      loc,
+                      options,
+                      result);
 }
 
 Status AbstractIndexAccessMethod::insertKeys(OperationContext* opCtx,
-                                             const BSONObjSet& keys,
-                                             const BSONObjSet& multikeyMetadataKeys,
+                                             const vector<BSONObj>& keys,
+                                             const vector<BSONObj>& multikeyMetadataKeys,
                                              const MultikeyPaths& multikeyPaths,
                                              const RecordId& loc,
                                              const InsertDeleteOptions& options,
@@ -205,9 +211,9 @@ Status AbstractIndexAccessMethod::insertKeys(OperationContext* opCtx,
     // Add all new data keys, and all new multikey metadata keys, into the index. When iterating
     // over the data keys, each of them should point to the doc's RecordId. When iterating over
     // the multikey metadata keys, they should point to the reserved 'kMultikeyMetadataKeyId'.
-    for (const auto keySet : {&keys, &multikeyMetadataKeys}) {
-        const auto& recordId = (keySet == &keys ? loc : kMultikeyMetadataKeyId);
-        for (const auto& key : *keySet) {
+    for (const auto keyVec : {&keys, &multikeyMetadataKeys}) {
+        const auto& recordId = (keyVec == &keys ? loc : kMultikeyMetadataKeyId);
+        for (const auto& key : *keyVec) {
             Status status = checkIndexKeySize ? checkKeySize(key) : Status::OK();
             if (status.isOK()) {
                 bool unique = _descriptor->unique();
@@ -275,33 +281,8 @@ std::unique_ptr<SortedDataInterface::Cursor> AbstractIndexAccessMethod::newCurso
     return newCursor(opCtx, true);
 }
 
-// Remove the provided doc from the index.
-Status AbstractIndexAccessMethod::remove(OperationContext* opCtx,
-                                         const BSONObj& obj,
-                                         const RecordId& loc,
-                                         const InsertDeleteOptions& options,
-                                         int64_t* numDeleted) {
-    invariant(!_btreeState->isHybridBuilding());
-    invariant(numDeleted);
-
-    *numDeleted = 0;
-    BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
-    // There's no need to compute the prefixes of the indexed fields that cause the index to be
-    // multikey when removing a document since the index metadata isn't updated when keys are
-    // deleted.
-    BSONObjSet* multikeyMetadataKeys = nullptr;
-    MultikeyPaths* multikeyPaths = nullptr;
-
-    // Relax key constraints on removal when deleting documents with invalid formats, but only
-    // those that don't apply to the partialIndex filter.
-    getKeys(
-        obj, GetKeysMode::kRelaxConstraintsUnfiltered, &keys, multikeyMetadataKeys, multikeyPaths);
-
-    return removeKeys(opCtx, keys, loc, options, numDeleted);
-}
-
 Status AbstractIndexAccessMethod::removeKeys(OperationContext* opCtx,
-                                             const BSONObjSet& keys,
+                                             const std::vector<BSONObj>& keys,
                                              const RecordId& loc,
                                              const InsertDeleteOptions& options,
                                              int64_t* numDeleted) {
@@ -428,20 +409,25 @@ pair<vector<BSONObj>, vector<BSONObj>> AbstractIndexAccessMethod::setDifference(
     return {std::move(onlyLeft), std::move(onlyRight)};
 }
 
-Status AbstractIndexAccessMethod::validateUpdate(OperationContext* opCtx,
-                                                 const BSONObj& from,
-                                                 const BSONObj& to,
-                                                 const RecordId& record,
-                                                 const InsertDeleteOptions& options,
-                                                 UpdateTicket* ticket,
-                                                 const MatchExpression* indexFilter) {
+void AbstractIndexAccessMethod::prepareUpdate(OperationContext* opCtx,
+                                              IndexCatalogEntry* index,
+                                              const BSONObj& from,
+                                              const BSONObj& to,
+                                              const RecordId& record,
+                                              const InsertDeleteOptions& options,
+                                              UpdateTicket* ticket) {
+    const MatchExpression* indexFilter = index->getFilterExpression();
     if (!indexFilter || indexFilter->matchesBSON(from)) {
+        // Override key constraints when generating keys for removal. This only applies to keys
+        // that do not apply to a partial filter expression.
+        const auto getKeysMode = index->isHybridBuilding()
+            ? IndexAccessMethod::GetKeysMode::kRelaxConstraintsUnfiltered
+            : options.getKeysMode;
+
         // There's no need to compute the prefixes of the indexed fields that possibly caused the
         // index to be multikey when the old version of the document was written since the index
         // metadata isn't updated when keys are deleted.
-        BSONObjSet* multikeyMetadataKeys = nullptr;
-        MultikeyPaths* multikeyPaths = nullptr;
-        getKeys(from, options.getKeysMode, &ticket->oldKeys, multikeyMetadataKeys, multikeyPaths);
+        getKeys(from, getKeysMode, &ticket->oldKeys, nullptr, nullptr);
     }
 
     if (!indexFilter || indexFilter->matchesBSON(to)) {
@@ -458,8 +444,6 @@ Status AbstractIndexAccessMethod::validateUpdate(OperationContext* opCtx,
     std::tie(ticket->removed, ticket->added) = setDifference(ticket->oldKeys, ticket->newKeys);
 
     ticket->_isValid = true;
-
-    return Status::OK();
 }
 
 Status AbstractIndexAccessMethod::update(OperationContext* opCtx,
@@ -507,7 +491,9 @@ Status AbstractIndexAccessMethod::update(OperationContext* opCtx,
     }
 
     if (shouldMarkIndexAsMultikey(
-            ticket.newKeys, ticket.newMultikeyMetadataKeys, ticket.newMultikeyPaths)) {
+            {ticket.newKeys.begin(), ticket.newKeys.end()},
+            {ticket.newMultikeyMetadataKeys.begin(), ticket.newMultikeyMetadataKeys.end()},
+            ticket.newMultikeyPaths)) {
         _btreeState->setMultikey(opCtx, ticket.newMultikeyPaths);
     }
 
@@ -607,8 +593,11 @@ Status AbstractIndexAccessMethod::BulkBuilderImpl::insert(OperationContext* opCt
         ++_keysInserted;
     }
 
-    _isMultiKey =
-        _isMultiKey || _real->shouldMarkIndexAsMultikey(keys, _multikeyMetadataKeys, multikeyPaths);
+    _isMultiKey = _isMultiKey ||
+        _real->shouldMarkIndexAsMultikey(
+            {keys.begin(), keys.end()},
+            {_multikeyMetadataKeys.begin(), _multikeyMetadataKeys.end()},
+            multikeyPaths);
 
     return Status::OK();
 }
@@ -800,8 +789,8 @@ void AbstractIndexAccessMethod::getKeys(const BSONObj& obj,
 }
 
 bool AbstractIndexAccessMethod::shouldMarkIndexAsMultikey(
-    const BSONObjSet& keys,
-    const BSONObjSet& multikeyMetadataKeys,
+    const vector<BSONObj>& keys,
+    const vector<BSONObj>& multikeyMetadataKeys,
     const MultikeyPaths& multikeyPaths) const {
     return (keys.size() > 1 || isMultikeyFromPaths(multikeyPaths));
 }
diff --git a/src/mongo/db/index/index_access_method.h b/src/mongo/db/index/index_access_method.h
index ff047aa1f43..39e98a3dfbb 100644
--- a/src/mongo/db/index/index_access_method.h
+++ b/src/mongo/db/index/index_access_method.h
@@ -47,7 +47,7 @@ namespace mongo {
 
 class BSONObjBuilder;
 class MatchExpression;
-class UpdateTicket;
+struct UpdateTicket;
 struct InsertResult;
 struct InsertDeleteOptions;
 
@@ -93,52 +93,40 @@ public:
                           InsertResult* result) = 0;
 
     virtual Status insertKeys(OperationContext* opCtx,
-                              const BSONObjSet& keys,
-                              const BSONObjSet& multikeyMetadataKeys,
+                              const std::vector<BSONObj>& keys,
+                              const std::vector<BSONObj>& multikeyMetadataKeys,
                               const MultikeyPaths& multikeyPaths,
                               const RecordId& loc,
                               const InsertDeleteOptions& options,
                               InsertResult* result) = 0;
 
     /**
-     * Analogous to above, but remove the records instead of inserting them.
-     * 'numDeleted' will be set to the number of keys removed from the index for the document.
+     * Analogous to insertKeys above, but remove the keys instead of inserting them.
+     * 'numDeleted' will be set to the number of keys removed from the index for the provided keys.
      */
-    virtual Status remove(OperationContext* opCtx,
-                          const BSONObj& obj,
-                          const RecordId& loc,
-                          const InsertDeleteOptions& options,
-                          int64_t* numDeleted) = 0;
-
     virtual Status removeKeys(OperationContext* opCtx,
-                              const BSONObjSet& keys,
+                              const std::vector<BSONObj>& keys,
                               const RecordId& loc,
                               const InsertDeleteOptions& options,
                               int64_t* numDeleted) = 0;
 
     /**
-     * Checks whether the index entries for the document 'from', which is placed at location
-     * 'loc' on disk, can be changed to the index entries for the doc 'to'. Provides a ticket
-     * for actually performing the update.
-     *
-     * Returns an error if the update is invalid.  The ticket will also be marked as invalid.
-     * Returns OK if the update should proceed without error.  The ticket is marked as valid.
-     *
-     * There is no obligation to perform the update after performing validation.
+     * Gets the keys of the documents 'from' and 'to' and prepares them for the update.
+     * Provides a ticket for actually performing the update.
      */
-    virtual Status validateUpdate(OperationContext* opCtx,
-                                  const BSONObj& from,
-                                  const BSONObj& to,
-                                  const RecordId& loc,
-                                  const InsertDeleteOptions& options,
-                                  UpdateTicket* ticket,
-                                  const MatchExpression* indexFilter) = 0;
+    virtual void prepareUpdate(OperationContext* opCtx,
+                               IndexCatalogEntry* index,
+                               const BSONObj& from,
+                               const BSONObj& to,
+                               const RecordId& loc,
+                               const InsertDeleteOptions& options,
+                               UpdateTicket* ticket) = 0;
 
     /**
      * Perform a validated update.  The keys for the 'from' object will be removed, and the keys
      * for the object 'to' will be added.  Returns OK if the update succeeded, failure if it did
      * not.  If an update does not succeed, the index will be unmodified, and the keys for
-     * 'from' will remain.  Assumes that the index has not changed since validateUpdate was
+     * 'from' will remain.  Assumes that the index has not changed since prepareUpdate was
      * called.  If the index was changed, we may return an error, as our ticket may have been
      * invalidated.
      *
@@ -329,8 +317,8 @@ public:
      * Given the set of keys, multikeyMetadataKeys and multikeyPaths generated by a particular
      * document, return 'true' if the index should be marked as multikey and 'false' otherwise.
      */
-    virtual bool shouldMarkIndexAsMultikey(const BSONObjSet& keys,
-                                           const BSONObjSet& multikeyMetadataKeys,
+    virtual bool shouldMarkIndexAsMultikey(const std::vector<BSONObj>& keys,
+                                           const std::vector<BSONObj>& multikeyMetadataKeys,
                                            const MultikeyPaths& multikeyPaths) const = 0;
 
     /**
@@ -391,18 +379,14 @@ public:
 
 /**
  * Updates are two steps: verify that it's a valid update, and perform it.
- * validateUpdate fills out the UpdateStatus and update actually applies it.
+ * prepareUpdate fills out the UpdateStatus and update actually applies it.
  */
-class UpdateTicket {
-public:
+struct UpdateTicket {
     UpdateTicket()
         : oldKeys(SimpleBSONObjComparator::kInstance.makeBSONObjSet()),
           newKeys(oldKeys),
           newMultikeyMetadataKeys(newKeys) {}
 
-private:
-    friend class AbstractIndexAccessMethod;
-
     bool _isValid{false};
 
     BSONObjSet oldKeys;
@@ -475,32 +459,26 @@ public:
                   InsertResult* result) final;
 
     Status insertKeys(OperationContext* opCtx,
-                      const BSONObjSet& keys,
-                      const BSONObjSet& multikeyMetadataKeys,
+                      const std::vector<BSONObj>& keys,
+                      const std::vector<BSONObj>& multikeyMetadataKeys,
                       const MultikeyPaths& multikeyPaths,
                       const RecordId& loc,
                       const InsertDeleteOptions& options,
                       InsertResult* result) final;
 
-    Status remove(OperationContext* opCtx,
-                  const BSONObj& obj,
-                  const RecordId& loc,
-                  const InsertDeleteOptions& options,
-                  int64_t* numDeleted) final;
-
     Status removeKeys(OperationContext* opCtx,
-                      const BSONObjSet& keys,
+                      const std::vector<BSONObj>& keys,
                       const RecordId& loc,
                       const InsertDeleteOptions& options,
                       int64_t* numDeleted) final;
 
-    Status validateUpdate(OperationContext* opCtx,
-                          const BSONObj& from,
-                          const BSONObj& to,
-                          const RecordId& loc,
-                          const InsertDeleteOptions& options,
-                          UpdateTicket* ticket,
-                          const MatchExpression* indexFilter) final;
+    void prepareUpdate(OperationContext* opCtx,
+                       IndexCatalogEntry* index,
+                       const BSONObj& from,
+                       const BSONObj& to,
+                       const RecordId& loc,
+                       const InsertDeleteOptions& options,
+                       UpdateTicket* ticket) final;
 
     Status update(OperationContext* opCtx,
                   const UpdateTicket& ticket,
@@ -547,8 +525,8 @@ public:
                  BSONObjSet* multikeyMetadataKeys,
                  MultikeyPaths* multikeyPaths) const final;
 
-    bool shouldMarkIndexAsMultikey(const BSONObjSet& keys,
-                                   const BSONObjSet& multikeyMetadataKeys,
+    bool shouldMarkIndexAsMultikey(const std::vector<BSONObj>& keys,
+                                   const std::vector<BSONObj>& multikeyMetadataKeys,
                                    const MultikeyPaths& multikeyPaths) const override;
 
     SortedDataInterface* getSortedDataInterface() const override final;
diff --git a/src/mongo/db/index/index_build_interceptor.cpp b/src/mongo/db/index/index_build_interceptor.cpp
index aaf57c66564..40f630c10aa 100644
--- a/src/mongo/db/index/index_build_interceptor.cpp
+++ b/src/mongo/db/index/index_build_interceptor.cpp
@@ -256,8 +256,8 @@ Status IndexBuildInterceptor::_applyWrite(OperationContext* opCtx,
     if (opType == Op::kInsert) {
         InsertResult result;
         auto status = accessMethod->insertKeys(opCtx,
-                                               keySet,
-                                               SimpleBSONObjComparator::kInstance.makeBSONObjSet(),
+                                               {keySet.begin(), keySet.end()},
+                                               {},
                                                MultikeyPaths{},
                                                opRecordId,
                                                options,
@@ -283,7 +283,8 @@ Status IndexBuildInterceptor::_applyWrite(OperationContext* opCtx,
         DEV invariant(strcmp(operation.getStringField("op"), "d") == 0);
 
         int64_t numDeleted;
-        Status s = accessMethod->removeKeys(opCtx, keySet, opRecordId, options, &numDeleted);
+        Status s = accessMethod->removeKeys(
+            opCtx, {keySet.begin(), keySet.end()}, opRecordId, options, &numDeleted);
         if (!s.isOK()) {
             return s;
         }
@@ -359,27 +360,14 @@ boost::optional<MultikeyPaths> IndexBuildInterceptor::getMultikeyPaths() const {
 }
 
 Status IndexBuildInterceptor::sideWrite(OperationContext* opCtx,
-                                        IndexAccessMethod* indexAccessMethod,
-                                        const BSONObj* obj,
-                                        const InsertDeleteOptions& options,
+                                        const std::vector<BSONObj>& keys,
+                                        const BSONObjSet& multikeyMetadataKeys,
+                                        const MultikeyPaths& multikeyPaths,
                                         RecordId loc,
                                         Op op,
                                         int64_t* const numKeysOut) {
     invariant(opCtx->lockState()->inAWriteUnitOfWork());
 
-    *numKeysOut = 0;
-    BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
-    BSONObjSet multikeyMetadataKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
-    MultikeyPaths multikeyPaths;
-
-    // Override key constraints when generating keys for removal. This is the same behavior as
-    // IndexAccessMethod::remove and only applies to keys that do not apply to a partial filter
-    // expression.
-    const auto getKeysMode = op == Op::kInsert
-        ? options.getKeysMode
-        : IndexAccessMethod::GetKeysMode::kRelaxConstraintsUnfiltered;
-    indexAccessMethod->getKeys(*obj, getKeysMode, &keys, &multikeyMetadataKeys, &multikeyPaths);
-
     // Maintain parity with IndexAccessMethods handling of key counting. Only include
     // `multikeyMetadataKeys` when inserting.
     *numKeysOut = keys.size() + (op == Op::kInsert ? multikeyMetadataKeys.size() : 0);
@@ -388,7 +376,7 @@ Status IndexBuildInterceptor::sideWrite(OperationContext* opCtx,
         return Status::OK();
     }
 
-    {
+    if (op == Op::kInsert) {
         stdx::unique_lock<stdx::mutex> lk(_multikeyPathMutex);
         if (_multikeyPaths) {
             MultikeyPathTracker::mergeMultikeyPaths(&_multikeyPaths.get(), multikeyPaths);
diff --git a/src/mongo/db/index/index_build_interceptor.h b/src/mongo/db/index/index_build_interceptor.h
index 4dcd8dfce2a..18f98cc72cf 100644
--- a/src/mongo/db/index/index_build_interceptor.h
+++ b/src/mongo/db/index/index_build_interceptor.h
@@ -69,9 +69,9 @@ public:
      * On success, `numKeysOut` if non-null will contain the number of keys added or removed.
      */
     Status sideWrite(OperationContext* opCtx,
-                     IndexAccessMethod* indexAccessMethod,
-                     const BSONObj* obj,
-                     const InsertDeleteOptions& options,
+                     const std::vector<BSONObj>& keys,
+                     const BSONObjSet& multikeyMetadataKeys,
+                     const MultikeyPaths& multikeyPaths,
                      RecordId loc,
                      Op op,
                      int64_t* const numKeysOut);
diff --git a/src/mongo/db/index/wildcard_access_method.cpp b/src/mongo/db/index/wildcard_access_method.cpp
index 72c6c06d098..4269d3dcab2 100644
--- a/src/mongo/db/index/wildcard_access_method.cpp
+++ b/src/mongo/db/index/wildcard_access_method.cpp
@@ -43,9 +43,10 @@ WildcardAccessMethod::WildcardAccessMethod(IndexCatalogEntry* wildcardState,
       _keyGen(
           _descriptor->keyPattern(), _descriptor->pathProjection(), _btreeState->getCollator()) {}
 
-bool WildcardAccessMethod::shouldMarkIndexAsMultikey(const BSONObjSet& keys,
-                                                     const BSONObjSet& multikeyMetadataKeys,
-                                                     const MultikeyPaths& multikeyPaths) const {
+bool WildcardAccessMethod::shouldMarkIndexAsMultikey(
+    const std::vector<BSONObj>& keys,
+    const std::vector<BSONObj>& multikeyMetadataKeys,
+    const MultikeyPaths& multikeyPaths) const {
     return !multikeyMetadataKeys.empty();
 }
 
diff --git a/src/mongo/db/index/wildcard_access_method.h b/src/mongo/db/index/wildcard_access_method.h
index 73017d4b10f..7fde78eb256 100644
--- a/src/mongo/db/index/wildcard_access_method.h
+++ b/src/mongo/db/index/wildcard_access_method.h
@@ -64,10 +64,10 @@ public:
      * Because it is possible for a $** index to generate multiple keys per document without any of
      * them lying along a multikey (i.e. array) path, this method will only return 'true' if one or
      * more multikey metadata keys have been generated; that is, if the 'multikeyMetadataKeys'
-     * BSONObjSet is non-empty.
+     * vector is non-empty.
      */
-    bool shouldMarkIndexAsMultikey(const BSONObjSet& keys,
-                                   const BSONObjSet& multikeyMetadataKeys,
+    bool shouldMarkIndexAsMultikey(const std::vector<BSONObj>& keys,
+                                   const std::vector<BSONObj>& multikeyMetadataKeys,
                                    const MultikeyPaths& multikeyPaths) const final;
 
     /**
diff --git a/src/mongo/dbtests/validate_tests.cpp b/src/mongo/dbtests/validate_tests.cpp
index f56a280f5f5..4073cbf5db5 100644
--- a/src/mongo/dbtests/validate_tests.cpp
+++ b/src/mongo/dbtests/validate_tests.cpp
@@ -869,7 +869,15 @@ public:
             InsertDeleteOptions options;
             options.dupsAllowed = true;
             options.logIfError = true;
-            auto removeStatus = iam->remove(&_opCtx, actualKey, id1, options, &numDeleted);
+
+            BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+            iam->getKeys(actualKey,
+                         IndexAccessMethod::GetKeysMode::kRelaxConstraintsUnfiltered,
+                         &keys,
+                         nullptr,
+                         nullptr);
+            auto removeStatus =
+                iam->removeKeys(&_opCtx, {keys.begin(), keys.end()}, id1, options, &numDeleted);
             auto insertStatus = iam->insert(&_opCtx, badKey, id1, options, &insertResult);
 
             ASSERT_EQUALS(numDeleted, 1);
@@ -1297,7 +1305,15 @@ public:
             InsertDeleteOptions options;
             options.logIfError = true;
             options.dupsAllowed = true;
-            auto removeStatus = iam->remove(&_opCtx, actualKey, rid, options, &numDeleted);
+
+            BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+            iam->getKeys(actualKey,
+                         IndexAccessMethod::GetKeysMode::kRelaxConstraintsUnfiltered,
+                         &keys,
+                         nullptr,
+                         nullptr);
+            auto removeStatus =
+                iam->removeKeys(&_opCtx, {keys.begin(), keys.end()}, rid, options, &numDeleted);
 
             ASSERT_EQUALS(numDeleted, 1);
             ASSERT_OK(removeStatus);