summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/mongo/db/catalog/SConscript1
-rw-r--r--src/mongo/db/catalog/index_catalog.h14
-rw-r--r--src/mongo/db/catalog/index_catalog_entry_impl.cpp12
-rw-r--r--src/mongo/db/catalog/index_catalog_impl.cpp118
-rw-r--r--src/mongo/db/catalog/index_catalog_impl.h14
-rw-r--r--src/mongo/db/catalog/index_catalog_noop.h4
-rw-r--r--src/mongo/db/catalog/index_signature_test.cpp242
-rw-r--r--src/mongo/db/commands/create_indexes.cpp10
-rw-r--r--src/mongo/db/index/SConscript2
-rw-r--r--src/mongo/db/index/index_descriptor.cpp80
-rw-r--r--src/mongo/db/index/index_descriptor.h14
-rw-r--r--src/mongo/db/index_builds_coordinator.cpp59
-rw-r--r--src/mongo/db/index_builds_coordinator.h16
-rw-r--r--src/mongo/db/matcher/expression.cpp71
-rw-r--r--src/mongo/db/matcher/expression.h24
-rw-r--r--src/mongo/db/matcher/expression_parser.cpp9
-rw-r--r--src/mongo/db/matcher/expression_parser.h10
-rw-r--r--src/mongo/db/query/canonical_query.cpp70
-rw-r--r--src/mongo/db/query/canonical_query.h6
-rw-r--r--src/mongo/db/query/canonical_query_test.cpp8
-rw-r--r--src/mongo/db/query/query_planner_partialidx_test.cpp44
-rw-r--r--src/mongo/db/query/query_planner_test_lib.cpp4
-rw-r--r--src/mongo/dbtests/plan_executor_invalidation_test.cpp13
-rw-r--r--src/mongo/dbtests/query_stage_near.cpp10
24 files changed, 656 insertions, 199 deletions
diff --git a/src/mongo/db/catalog/SConscript b/src/mongo/db/catalog/SConscript
index 298478faa9b..aedda2ed6af 100644
--- a/src/mongo/db/catalog/SConscript
+++ b/src/mongo/db/catalog/SConscript
@@ -472,6 +472,7 @@ env.CppUnitTest(
'index_build_entry_test.cpp',
'index_builds_manager_test.cpp',
'index_key_validate_test.cpp',
+ 'index_signature_test.cpp',
'index_spec_validate_test.cpp',
'multi_index_block_test.cpp',
'rename_collection_test.cpp',
diff --git a/src/mongo/db/catalog/index_catalog.h b/src/mongo/db/catalog/index_catalog.h
index 79add4ec623..9a97a935405 100644
--- a/src/mongo/db/catalog/index_catalog.h
+++ b/src/mongo/db/catalog/index_catalog.h
@@ -215,19 +215,15 @@ public:
const bool includeUnfinishedIndexes = false) const = 0;
/**
- * Find index by matching key pattern and collation spec. The key pattern and collation spec
- * uniquely identify an index.
+ * Find index by matching key pattern and options. The key pattern, collation spec, and partial
+ * filter expression together uniquely identify an index.
*
- * Collation is specified as a normalized collation spec as returned by
- * CollationInterface::getSpec. An empty object indicates the simple collation.
- *
- * @return null if cannot find index, otherwise the index with a matching key pattern and
- * collation.
+ * @return null if cannot find index, otherwise the index with a matching signature.
*/
- virtual const IndexDescriptor* findIndexByKeyPatternAndCollationSpec(
+ virtual const IndexDescriptor* findIndexByKeyPatternAndOptions(
OperationContext* const opCtx,
const BSONObj& key,
- const BSONObj& collationSpec,
+ const BSONObj& indexSpec,
const bool includeUnfinishedIndexes = false) const = 0;
/**
diff --git a/src/mongo/db/catalog/index_catalog_entry_impl.cpp b/src/mongo/db/catalog/index_catalog_entry_impl.cpp
index cca329b0007..16a69488248 100644
--- a/src/mongo/db/catalog/index_catalog_entry_impl.cpp
+++ b/src/mongo/db/catalog/index_catalog_entry_impl.cpp
@@ -105,13 +105,11 @@ IndexCatalogEntryImpl::IndexCatalogEntryImpl(OperationContext* const opCtx,
// Parsing the partial filter expression is not expected to fail here since the
// expression would have been successfully parsed upstream during index creation.
- StatusWithMatchExpression statusWithMatcher =
- MatchExpressionParser::parse(filter,
- _expCtxForFilter,
- ExtensionsCallbackNoop(),
- MatchExpressionParser::kBanAllSpecialFeatures);
- invariant(statusWithMatcher.getStatus());
- _filterExpression = std::move(statusWithMatcher.getValue());
+ _filterExpression =
+ MatchExpressionParser::parseAndNormalize(filter,
+ _expCtxForFilter,
+ ExtensionsCallbackNoop(),
+ MatchExpressionParser::kBanAllSpecialFeatures);
LOGV2_DEBUG(20350,
2,
"have filter expression for {ns} {descriptor_indexName} {filter}",
diff --git a/src/mongo/db/catalog/index_catalog_impl.cpp b/src/mongo/db/catalog/index_catalog_impl.cpp
index c1e444128ff..c49b1b9424b 100644
--- a/src/mongo/db/catalog/index_catalog_impl.cpp
+++ b/src/mongo/db/catalog/index_catalog_impl.cpp
@@ -773,86 +773,93 @@ Status IndexCatalogImpl::_isSpecOk(OperationContext* opCtx, const BSONObj& spec)
Status IndexCatalogImpl::_doesSpecConflictWithExisting(OperationContext* opCtx,
const BSONObj& spec,
const bool includeUnfinishedIndexes) const {
- const char* name = spec.getStringField("name");
+ const char* name = spec.getStringField(IndexDescriptor::kIndexNameFieldName);
invariant(name[0]);
- const BSONObj key = spec.getObjectField("key");
- const BSONObj collation = spec.getObjectField("collation");
+ const BSONObj key = spec.getObjectField(IndexDescriptor::kKeyPatternFieldName);
{
+ // Check whether an index with the specified candidate name already exists in the catalog.
const IndexDescriptor* desc = findIndexByName(opCtx, name, includeUnfinishedIndexes);
- if (desc) {
- // index already exists with same name
- if (SimpleBSONObjComparator::kInstance.evaluate(desc->keyPattern() == key) &&
- SimpleBSONObjComparator::kInstance.evaluate(
- desc->infoObj().getObjectField("collation") != collation)) {
- // key patterns are equal but collations differ.
- return Status(ErrorCodes::IndexOptionsConflict,
- str::stream()
- << "An index with the same key pattern, but a different "
- << "collation already exists with the same name. Try again with "
- << "a unique name. "
- << "Existing index: " << desc->infoObj()
- << " Requested index: " << spec);
- }
+ if (desc) {
+ // Index already exists with same name. Check whether the options are the same as well.
+ IndexDescriptor candidate(_collection, _getAccessMethodName(key), spec);
+ auto indexComparison = candidate.compareIndexOptions(opCtx, getEntry(desc));
- if (SimpleBSONObjComparator::kInstance.evaluate(desc->keyPattern() != key) ||
- SimpleBSONObjComparator::kInstance.evaluate(
- desc->infoObj().getObjectField("collation") != collation)) {
+ // Key pattern or another uniquely-identifying option differs. We can build this index,
+ // but not with the specified (duplicate) name. User must specify another index name.
+ if (indexComparison == IndexDescriptor::Comparison::kDifferent) {
return Status(ErrorCodes::IndexKeySpecsConflict,
- str::stream()
- << "Index must have unique name."
- << "The existing index: " << desc->infoObj()
- << " has the same name as the requested index: " << spec);
+ str::stream() << "An existing index has the same name as the "
+ "requested index. Requested index: "
+ << spec << ", existing index: " << desc->infoObj());
}
- IndexDescriptor temp(_collection, _getAccessMethodName(key), spec);
- if (!desc->areIndexOptionsEquivalent(&temp))
+ // The candidate's key and uniquely-identifying options are equivalent to an existing
+ // index, but some other options are not identical. Return a message to that effect.
+ if (indexComparison == IndexDescriptor::Comparison::kEquivalent) {
return Status(ErrorCodes::IndexOptionsConflict,
- str::stream() << "Index with name: " << name
- << " already exists with different options");
+ str::stream() << "An equivalent index already exists with the same "
+ "name but different options. Requested index: "
+ << spec << ", existing index: " << desc->infoObj());
+ }
+ // If we've reached this point, the requested index is identical to an existing index.
+ invariant(indexComparison == IndexDescriptor::Comparison::kIdentical);
// If an identical index exists, but it is frozen, return an error with a different
- // code to the user, forcing the user to drop before recreating the index.
+ // error code to the user, forcing the user to drop before recreating the index.
auto entry = getEntry(desc);
if (entry->isFrozen()) {
return Status(ErrorCodes::CannotCreateIndex,
- str::stream() << "An identical, unfinished index already exists. The "
- "index must be dropped first: "
- << name << ", spec: " << desc->infoObj());
+ str::stream()
+ << "An identical, unfinished index '" << name
+ << "' already exists. Must drop before recreating. Spec: "
+ << desc->infoObj());
}
- // Index already exists with the same options, so no need to build a new
- // one (not an error). Most likely requested by a client using ensureIndex.
+ // Index already exists with the same options, so there is no need to build a new one.
+ // This is not an error condition.
return Status(ErrorCodes::IndexAlreadyExists,
str::stream() << "Identical index already exists: " << name);
}
}
{
+ // No index with the candidate name exists. Check for an index with conflicting options.
const IndexDescriptor* desc =
- findIndexByKeyPatternAndCollationSpec(opCtx, key, collation, includeUnfinishedIndexes);
+ findIndexByKeyPatternAndOptions(opCtx, key, spec, includeUnfinishedIndexes);
+
if (desc) {
LOGV2_DEBUG(20353,
2,
- "Index already exists with a different name: {name} pattern: {key} "
- "collation: {collation}",
- "name"_attr = name,
- "key"_attr = key,
- "collation"_attr = collation);
-
- IndexDescriptor temp(_collection, _getAccessMethodName(key), spec);
- if (!desc->areIndexOptionsEquivalent(&temp))
+ "Index already exists with a different name: {name}, spec: {spec}",
+ "Index already exists with a different name",
+ "name"_attr = desc->indexName(),
+ "spec"_attr = desc->infoObj());
+
+ // Index already exists with a different name. Check whether the options are identical.
+ // We will return an error in either case, but this check allows us to generate a more
+ // informative error message.
+ IndexDescriptor candidate(_collection, _getAccessMethodName(key), spec);
+ auto indexComparison = candidate.compareIndexOptions(opCtx, getEntry(desc));
+
+ // The candidate's key and uniquely-identifying options are equivalent to an existing
+ // index, but some other options are not identical. Return a message to that effect.
+ if (indexComparison == IndexDescriptor::Comparison::kEquivalent)
return Status(ErrorCodes::IndexOptionsConflict,
- str::stream()
- << "Index: " << spec
- << " already exists with different options: " << desc->infoObj());
+ str::stream() << "An equivalent index already exists with a "
+ "different name and options. Requested index: "
+ << spec << ", existing index: " << desc->infoObj());
+ // If we've reached this point, the requested index is identical to an existing index.
+ invariant(indexComparison == IndexDescriptor::Comparison::kIdentical);
+
+ // An identical index already exists with a different name. We cannot build this index.
return Status(ErrorCodes::IndexOptionsConflict,
- str::stream() << "Index with name: " << name
- << " already exists with a different name");
+ str::stream() << "Index already exists with a different name: "
+ << desc->indexName());
}
}
@@ -1203,18 +1210,17 @@ const IndexDescriptor* IndexCatalogImpl::findIndexByName(OperationContext* opCtx
return nullptr;
}
-const IndexDescriptor* IndexCatalogImpl::findIndexByKeyPatternAndCollationSpec(
+const IndexDescriptor* IndexCatalogImpl::findIndexByKeyPatternAndOptions(
OperationContext* opCtx,
const BSONObj& key,
- const BSONObj& collationSpec,
+ const BSONObj& indexSpec,
bool includeUnfinishedIndexes) const {
std::unique_ptr<IndexIterator> ii = getIndexIterator(opCtx, includeUnfinishedIndexes);
+ IndexDescriptor needle(_collection, _getAccessMethodName(key), indexSpec);
while (ii->more()) {
- const IndexDescriptor* desc = ii->next()->descriptor();
- if (SimpleBSONObjComparator::kInstance.evaluate(desc->keyPattern() == key) &&
- SimpleBSONObjComparator::kInstance.evaluate(
- desc->infoObj().getObjectField("collation") == collationSpec)) {
- return desc;
+ const auto* entry = ii->next();
+ if (needle.compareIndexOptions(opCtx, entry) != IndexDescriptor::Comparison::kDifferent) {
+ return entry->descriptor();
}
}
return nullptr;
@@ -1242,7 +1248,7 @@ const IndexDescriptor* IndexCatalogImpl::findShardKeyPrefixedIndex(OperationCont
std::unique_ptr<IndexIterator> ii = getIndexIterator(opCtx, false);
while (ii->more()) {
const IndexDescriptor* desc = ii->next()->descriptor();
- bool hasSimpleCollation = desc->infoObj().getObjectField("collation").isEmpty();
+ bool hasSimpleCollation = desc->collation().isEmpty();
if (desc->isPartial() || desc->isSparse())
continue;
diff --git a/src/mongo/db/catalog/index_catalog_impl.h b/src/mongo/db/catalog/index_catalog_impl.h
index fb3ec499a0d..fa195004756 100644
--- a/src/mongo/db/catalog/index_catalog_impl.h
+++ b/src/mongo/db/catalog/index_catalog_impl.h
@@ -95,19 +95,15 @@ public:
bool includeUnfinishedIndexes = false) const override;
/**
- * Find index by matching key pattern and collation spec. The key pattern and collation spec
- * uniquely identify an index.
+ * Find index by matching key pattern and options. The key pattern, collation spec, and partial
+ * filter expression together uniquely identify an index.
*
- * Collation is specified as a normalized collation spec as returned by
- * CollationInterface::getSpec. An empty object indicates the simple collation.
- *
- * @return null if cannot find index, otherwise the index with a matching key pattern and
- * collation.
+ * @return null if cannot find index, otherwise the index with a matching signature.
*/
- const IndexDescriptor* findIndexByKeyPatternAndCollationSpec(
+ const IndexDescriptor* findIndexByKeyPatternAndOptions(
OperationContext* opCtx,
const BSONObj& key,
- const BSONObj& collationSpec,
+ const BSONObj& indexSpec,
bool includeUnfinishedIndexes = false) const override;
/**
diff --git a/src/mongo/db/catalog/index_catalog_noop.h b/src/mongo/db/catalog/index_catalog_noop.h
index ebe91ec2b72..3c66fcd90b1 100644
--- a/src/mongo/db/catalog/index_catalog_noop.h
+++ b/src/mongo/db/catalog/index_catalog_noop.h
@@ -81,10 +81,10 @@ public:
return nullptr;
}
- IndexDescriptor* findIndexByKeyPatternAndCollationSpec(
+ IndexDescriptor* findIndexByKeyPatternAndOptions(
OperationContext* const opCtx,
const BSONObj& key,
- const BSONObj& collationSpec,
+ const BSONObj& indexSpec,
const bool includeUnfinishedIndexes = false) const override {
return nullptr;
}
diff --git a/src/mongo/db/catalog/index_signature_test.cpp b/src/mongo/db/catalog/index_signature_test.cpp
new file mode 100644
index 00000000000..07f8d70d755
--- /dev/null
+++ b/src/mongo/db/catalog/index_signature_test.cpp
@@ -0,0 +1,242 @@
+/**
+ * Copyright (C) 2020-present MongoDB, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the Server Side Public License, version 1,
+ * as published by MongoDB, Inc.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * Server Side Public License for more details.
+ *
+ * You should have received a copy of the Server Side Public License
+ * along with this program. If not, see
+ * <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the Server Side Public License in all respects for
+ * all of the code used other than as permitted herein. If you modify file(s)
+ * with this exception, you may extend this exception to your version of the
+ * file(s), but you are not obligated to do so. If you do not wish to do so,
+ * delete this exception statement from your version. If you delete this
+ * exception statement from all source files in the program, then also delete
+ * it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/catalog/catalog_test_fixture.h"
+#include "mongo/db/catalog/collection.h"
+#include "mongo/db/catalog/index_catalog_entry_impl.h"
+#include "mongo/db/catalog_raii.h"
+#include "mongo/db/index/index_descriptor.h"
+#include "mongo/db/query/collection_query_info.h"
+
+namespace mongo {
+namespace {
+
+class IndexSignatureTest : public CatalogTestFixture {
+public:
+ IndexSignatureTest() : CatalogTestFixture() {}
+
+ StatusWith<const IndexCatalogEntry*> createIndex(BSONObj spec) {
+ // Get the index catalog associated with the test collection.
+ auto* indexCatalog = coll()->getIndexCatalog();
+ // Build the specified index on the collection.
+ WriteUnitOfWork wuow(opCtx());
+ auto status = indexCatalog->createIndexOnEmptyCollection(opCtx(), spec);
+ if (!status.isOK()) {
+ return status.getStatus();
+ }
+ wuow.commit();
+ // Find the index entry and return it.
+ return indexCatalog->getEntry(indexCatalog->findIndexByName(
+ opCtx(), spec.getStringField(IndexDescriptor::kIndexNameFieldName)));
+ }
+
+ std::unique_ptr<IndexDescriptor> makeIndexDescriptor(BSONObj spec) {
+ auto keyPattern = spec.getObjectField(IndexDescriptor::kKeyPatternFieldName);
+ return std::make_unique<IndexDescriptor>(
+ coll(), IndexNames::findPluginName(keyPattern), spec);
+ }
+
+ const NamespaceString& nss() const {
+ return _nss;
+ }
+
+ Collection* coll() const {
+ return _coll->getCollection();
+ }
+
+ OperationContext* opCtx() {
+ return operationContext();
+ }
+
+protected:
+ void setUp() override {
+ CatalogTestFixture::setUp();
+ ASSERT_OK(storageInterface()->createCollection(opCtx(), _nss, {}));
+ _coll.emplace(opCtx(), _nss, MODE_X);
+ }
+
+ void tearDown() override {
+ _coll.reset();
+ CatalogTestFixture::tearDown();
+ }
+
+ // Helper function to add all elements in 'fields' into 'input', replacing any existing fields.
+ // Returns a new object containing the added fields.
+ BSONObj _addFields(BSONObj input, BSONObj fields) {
+ for (auto&& field : fields) {
+ input = input.addField(field);
+ }
+ return input;
+ }
+
+private:
+ boost::optional<AutoGetCollection> _coll;
+ NamespaceString _nss{"fooDB.barColl"};
+};
+
+TEST_F(IndexSignatureTest, CanCreateMultipleIndexesOnSameKeyPatternWithDifferentCollations) {
+ // Create an index on {a: 1} with an 'en_US' collation.
+ auto indexSpec = fromjson("{v: 2, name: 'a_1', key: {a: 1}, collation: {locale: 'en_US'}}");
+ auto* basicIndex = unittest::assertGet(createIndex(indexSpec));
+
+ // Create an index descriptor on the same keyPattern whose collation has an explicit strength.
+ // The two indexes compare as kIdentical, because the collation comparison is performed using
+ // the parsed collator rather than the static collation object from the BSON index specs.
+ auto collationDesc = makeIndexDescriptor(
+ _addFields(indexSpec, fromjson("{collation: {locale: 'en_US', strength: 3}}")));
+ ASSERT(collationDesc->compareIndexOptions(opCtx(), basicIndex) ==
+ IndexDescriptor::Comparison::kIdentical);
+
+ // Confirm that attempting to build this index will result in ErrorCodes::IndexAlreadyExists.
+ ASSERT_EQ(createIndex(collationDesc->infoObj()), ErrorCodes::IndexAlreadyExists);
+
+ // Now set the unique field. The indexes now compare kEquivalent, but not kIdentical. This means
+ // that all signature fields which uniquely identify the index match, but other fields differ.
+ auto collationUniqueDesc =
+ makeIndexDescriptor(_addFields(collationDesc->infoObj(), fromjson("{unique: true}")));
+ ASSERT(collationUniqueDesc->compareIndexOptions(opCtx(), basicIndex) ==
+ IndexDescriptor::Comparison::kEquivalent);
+
+ // Attempting to build the index, whether with the same name or a different name, now throws
+ // IndexOptionsConflict. The error message returned with the exception specifies whether the
+ // name matches an existing index.
+ ASSERT_EQ(createIndex(collationUniqueDesc->infoObj()), ErrorCodes::IndexOptionsConflict);
+ ASSERT_EQ(createIndex(_addFields(collationUniqueDesc->infoObj(),
+ fromjson("{name: 'collationUnique'}"))),
+ ErrorCodes::IndexOptionsConflict);
+
+ // Now create an index spec with an entirely different collation. The two indexes compare as
+ // being kDifferent; this means that both of these indexes can co-exist together.
+ auto differentCollationDesc = makeIndexDescriptor(
+ _addFields(collationDesc->infoObj(), fromjson("{collation: {locale: 'fr'}}")));
+ ASSERT(differentCollationDesc->compareIndexOptions(opCtx(), basicIndex) ==
+ IndexDescriptor::Comparison::kDifferent);
+
+ // Verify that we can build this index alongside the existing indexes.
+ ASSERT_OK(createIndex(
+ _addFields(differentCollationDesc->infoObj(), fromjson("{name: 'differentCollation'}"))));
+}
+
+TEST_F(IndexSignatureTest,
+ CanCreateMultipleIndexesOnSameKeyPatternWithDifferentPartialFilterExpressions) {
+ // Create a basic index on {a: 1} with no partialFilterExpression.
+ auto indexSpec = fromjson("{v: 2, name: 'a_1', key: {a: 1}}");
+ auto* basicIndex = unittest::assertGet(createIndex(indexSpec));
+
+ // Create an index descriptor on the same keyPattern with a partialFilterExpression. The two
+ // indexes compare as kDifferent, because the partialFilterExpression is one of the fields in
+ // the index's signature.
+ auto partialFilterDesc = makeIndexDescriptor(_addFields(
+ indexSpec, fromjson("{partialFilterExpression: {a: {$gt: 5, $lt: 10}, b: 'blah'}}")));
+ ASSERT(partialFilterDesc->compareIndexOptions(opCtx(), basicIndex) ==
+ IndexDescriptor::Comparison::kDifferent);
+
+ // Verify that we can build an index with this spec alongside the original index.
+ auto* partialFilterIndex = unittest::assertGet(
+ createIndex(_addFields(partialFilterDesc->infoObj(), fromjson("{name: 'partialFilter'}"))));
+
+ // Verify that partialFilterExpressions are normalized before being compared. Here, the filter
+ // is expressed differently than in the existing index, but the two still compare as kIdentical.
+ auto partialFilterDupeDesc = makeIndexDescriptor(
+ _addFields(indexSpec,
+ fromjson("{name: 'partialFilter', partialFilterExpression: {$and: [{b: 'blah'}, "
+ "{a: {$lt: 10}}, {a: {$gt: 5}}]}}")));
+ ASSERT(partialFilterDupeDesc->compareIndexOptions(opCtx(), partialFilterIndex) ==
+ IndexDescriptor::Comparison::kIdentical);
+
+ // Confirm that attempting to build this index will result in ErrorCodes::IndexAlreadyExists.
+ ASSERT_EQ(createIndex(partialFilterDupeDesc->infoObj()), ErrorCodes::IndexAlreadyExists);
+
+ // Now set the unique field. The indexes now compare kEquivalent, but not kIdentical. This means
+ // that all signature fields which uniquely identify the index match, but other fields differ.
+ auto partialFilterUniqueDesc =
+ makeIndexDescriptor(_addFields(partialFilterDesc->infoObj(), fromjson("{unique: true}")));
+ ASSERT(partialFilterUniqueDesc->compareIndexOptions(opCtx(), partialFilterIndex) ==
+ IndexDescriptor::Comparison::kEquivalent);
+
+ // Attempting to build the index, whether with the same name or a different name, now throws
+ // IndexOptionsConflict. The error message returned with the exception specifies whether the
+ // name matches an existing index.
+ ASSERT_EQ(createIndex(_addFields(partialFilterUniqueDesc->infoObj(),
+ fromjson("{name: 'partialFilterExpression'}"))),
+ ErrorCodes::IndexOptionsConflict);
+ ASSERT_EQ(createIndex(_addFields(partialFilterUniqueDesc->infoObj(),
+ fromjson("{name: 'partialFilterUnique'}"))),
+ ErrorCodes::IndexOptionsConflict);
+
+ // Now create an index spec with an entirely different partialFilterExpression. The two indexes
+ // compare as kDifferent; this means that both of these indexes can co-exist together.
+ auto differentPartialFilterDesc = makeIndexDescriptor(
+ _addFields(partialFilterDesc->infoObj(),
+ fromjson("{partialFilterExpression: {a: {$gt: 0, $lt: 10}, b: 'blah'}}")));
+ ASSERT(differentPartialFilterDesc->compareIndexOptions(opCtx(), partialFilterIndex) ==
+ IndexDescriptor::Comparison::kDifferent);
+
+ // Verify that we can build this index alongside the existing indexes.
+ ASSERT_OK(createIndex(_addFields(differentPartialFilterDesc->infoObj(),
+ fromjson("{name: 'differentPartialFilter'}"))));
+}
+
+TEST_F(IndexSignatureTest, CannotCreateMultipleIndexesOnSameKeyPatternIfNonSignatureFieldsDiffer) {
+ // Create a basic index on {a: 1} with all other options set to their default values.
+ auto indexSpec = fromjson("{v: 2, name: 'a_1', key: {a: 1}}");
+ auto* basicIndex = unittest::assertGet(createIndex(indexSpec));
+
+ // TODO SERVER-47657: unique and sparse should be part of the signature.
+ std::vector<BSONObj> nonSigOptions = {
+ BSON(IndexDescriptor::kUniqueFieldName << true),
+ BSON(IndexDescriptor::kSparseFieldName << true),
+ BSON(IndexDescriptor::kExpireAfterSecondsFieldName << 10)};
+
+ // Verify that changing each of the non-signature fields does not distinguish this index from
+ // the existing index. The two are considered equivalent, and we cannot build the new index.
+ for (auto&& nonSigOpt : nonSigOptions) {
+ auto nonSigDesc = makeIndexDescriptor(_addFields(indexSpec, nonSigOpt));
+ ASSERT(nonSigDesc->compareIndexOptions(opCtx(), basicIndex) ==
+ IndexDescriptor::Comparison::kEquivalent);
+ ASSERT_EQ(createIndex(nonSigDesc->infoObj()), ErrorCodes::IndexOptionsConflict);
+ }
+
+ // Build a wildcard index and confirm that 'wildcardProjection' is a non-signature field.
+ // TODO SERVER-47659: wildcardProjection should be part of the signature.
+ auto* wildcardIndex =
+ unittest::assertGet(createIndex(fromjson("{v: 2, name: '$**_1', key: {'$**': 1}}")));
+ auto nonSigWildcardDesc = makeIndexDescriptor(_addFields(
+ wildcardIndex->descriptor()->infoObj(), fromjson("{wildcardProjection: {a: 1}}")));
+ ASSERT(nonSigWildcardDesc->compareIndexOptions(opCtx(), wildcardIndex) ==
+ IndexDescriptor::Comparison::kEquivalent);
+ ASSERT_EQ(createIndex(
+ _addFields(nonSigWildcardDesc->infoObj(), fromjson("{name: 'nonSigWildcard'}"))),
+ ErrorCodes::IndexOptionsConflict);
+}
+
+} // namespace
+} // namespace mongo
diff --git a/src/mongo/db/commands/create_indexes.cpp b/src/mongo/db/commands/create_indexes.cpp
index f4c2297eadc..689f66e2b6c 100644
--- a/src/mongo/db/commands/create_indexes.cpp
+++ b/src/mongo/db/commands/create_indexes.cpp
@@ -319,13 +319,11 @@ boost::optional<CommitQuorumOptions> parseAndGetCommitQuorum(OperationContext* o
std::vector<BSONObj> resolveDefaultsAndRemoveExistingIndexes(OperationContext* opCtx,
const Collection* collection,
std::vector<BSONObj> indexSpecs) {
- auto swDefaults = collection->addCollationDefaultsToIndexSpecsForCreate(opCtx, indexSpecs);
- uassertStatusOK(swDefaults.getStatus());
+ // Normalize the specs' collations, wildcard projections, and partial filters as applicable.
+ auto normalSpecs = IndexBuildsCoordinator::normalizeIndexSpecs(opCtx, collection, indexSpecs);
- auto indexCatalog = collection->getIndexCatalog();
-
- return indexCatalog->removeExistingIndexes(
- opCtx, swDefaults.getValue(), false /*removeIndexBuildsToo*/);
+ return collection->getIndexCatalog()->removeExistingIndexes(
+ opCtx, normalSpecs, false /*removeIndexBuildsToo*/);
}
/**
diff --git a/src/mongo/db/index/SConscript b/src/mongo/db/index/SConscript
index fcff88d1e14..eaa3ebaaf40 100644
--- a/src/mongo/db/index/SConscript
+++ b/src/mongo/db/index/SConscript
@@ -17,6 +17,8 @@ env.Library(
LIBDEPS_PRIVATE=[
'$BUILD_DIR/mongo/db/index_names',
'$BUILD_DIR/mongo/db/namespace_string',
+ '$BUILD_DIR/mongo/db/matcher/expressions',
+ '$BUILD_DIR/mongo/db/query/collation/collator_factory_interface',
],
)
diff --git a/src/mongo/db/index/index_descriptor.cpp b/src/mongo/db/index/index_descriptor.cpp
index 17f765d87cf..c4da010008c 100644
--- a/src/mongo/db/index/index_descriptor.cpp
+++ b/src/mongo/db/index/index_descriptor.cpp
@@ -34,6 +34,8 @@
#include "mongo/db/catalog/collection.h"
#include "mongo/db/catalog/index_catalog.h"
#include "mongo/db/index/index_descriptor.h"
+#include "mongo/db/matcher/expression_parser.h"
+#include "mongo/db/query/collation/collator_factory_interface.h"
#include <algorithm>
@@ -50,9 +52,9 @@ void populateOptionsMap(std::map<StringData, BSONElement>& theMap, const BSONObj
const BSONElement e = it.next();
StringData fieldName = e.fieldNameStringData();
- if (fieldName == IndexDescriptor::kKeyPatternFieldName ||
- fieldName == IndexDescriptor::kNamespaceFieldName || // removed in 4.4
- fieldName == IndexDescriptor::kIndexNameFieldName ||
+ if (fieldName == IndexDescriptor::kKeyPatternFieldName || // checked specially
+ fieldName == IndexDescriptor::kNamespaceFieldName || // removed in 4.4
+ fieldName == IndexDescriptor::kIndexNameFieldName || // checked separately
fieldName ==
IndexDescriptor::kIndexVersionFieldName || // not considered for equivalence
fieldName == IndexDescriptor::kTextVersionFieldName || // same as index version
@@ -60,9 +62,9 @@ void populateOptionsMap(std::map<StringData, BSONElement>& theMap, const BSONObj
fieldName ==
IndexDescriptor::kBackgroundFieldName || // this is a creation time option only
fieldName == IndexDescriptor::kDropDuplicatesFieldName || // this is now ignored
- fieldName == IndexDescriptor::kSparseFieldName || // checked specially
- fieldName == IndexDescriptor::kHiddenFieldName || // not considered for equivalence
- fieldName == IndexDescriptor::kUniqueFieldName // check specially
+ fieldName == IndexDescriptor::kHiddenFieldName || // not considered for equivalence
+ fieldName == IndexDescriptor::kCollationFieldName || // checked specially
+ fieldName == IndexDescriptor::kPartialFilterExprFieldName // checked specially
) {
continue;
}
@@ -176,25 +178,69 @@ const NamespaceString& IndexDescriptor::parentNS() const {
return _collection->ns();
}
-bool IndexDescriptor::areIndexOptionsEquivalent(const IndexDescriptor* other) const {
- if (isSparse() != other->isSparse()) {
- return false;
+IndexDescriptor::Comparison IndexDescriptor::compareIndexOptions(
+ OperationContext* opCtx, const IndexCatalogEntry* other) const {
+ // We first check whether the key pattern is identical for both indexes.
+ if (SimpleBSONObjComparator::kInstance.evaluate(keyPattern() !=
+ other->descriptor()->keyPattern())) {
+ return Comparison::kDifferent;
}
- if (!isIdIndex() && unique() != other->unique()) {
- // Note: { _id: 1 } or { _id: -1 } implies unique: true.
- return false;
+ // Check whether both indexes have the same collation. If not, then they are not equivalent.
+ auto collator = collation().isEmpty()
+ ? nullptr
+ : uassertStatusOK(
+ CollatorFactoryInterface::get(opCtx->getServiceContext())->makeFromBSON(collation()));
+ if (!CollatorInterface::collatorsMatch(collator.get(), other->getCollator())) {
+ return Comparison::kDifferent;
}
- // Then compare the rest of the options.
+ // The partialFilterExpression is only part of the index signature if FCV has been set to 4.6.
+ // TODO SERVER-47766: remove these FCV checks after we branch for 4.7.
+ auto isFCV46 = serverGlobalParams.featureCompatibility.isVersion(
+ ServerGlobalParams::FeatureCompatibility::Version::kFullyUpgradedTo46);
+
+ // If we have a partial filter expression and the other index doesn't, or vice-versa, then the
+ // two indexes are not equivalent. We therefore return Comparison::kDifferent immediately.
+ if (isFCV46 && isPartial() != other->descriptor()->isPartial()) {
+ return Comparison::kDifferent;
+ }
+ // Compare 'partialFilterExpression' in each descriptor to see if they are equivalent. We use
+ // the collator that we parsed earlier to create the filter's ExpressionContext, although we
+ // don't currently consider collation when comparing string predicates for filter equivalence.
+ // For instance, under a case-sensitive collation, the predicates {a: "blah"} and {a: "BLAH"}
+ // would match the same set of documents, but these are not currently considered equivalent.
+ // TODO SERVER-47664: take collation into account while comparing string predicates.
+ if (isFCV46 && other->getFilterExpression()) {
+ auto expCtx =
+ make_intrusive<ExpressionContext>(opCtx, std::move(collator), _collection->ns());
+ auto filter = MatchExpressionParser::parseAndNormalize(partialFilterExpression(), expCtx);
+ if (!filter->equivalent(other->getFilterExpression())) {
+ return Comparison::kDifferent;
+ }
+ }
+
+ // If we are here, then the two descriptors match on all option fields that uniquely distinguish
+ // an index, and so the return value will be at least Comparison::kEquivalent. We now proceed to
+ // compare the rest of the options to see if we should return Comparison::kIdentical instead.
std::map<StringData, BSONElement> existingOptionsMap;
populateOptionsMap(existingOptionsMap, infoObj());
std::map<StringData, BSONElement> newOptionsMap;
- populateOptionsMap(newOptionsMap, other->infoObj());
+ populateOptionsMap(newOptionsMap, other->descriptor()->infoObj());
+
+ // If the FCV has not been upgraded to 4.6, add partialFilterExpression to the options map. It
+ // does not contribute to the index signature, but can determine whether or not the candidate
+ // index is identical to the existing index.
+ if (!isFCV46) {
+ existingOptionsMap[IndexDescriptor::kPartialFilterExprFieldName] =
+ other->descriptor()->infoObj()[IndexDescriptor::kPartialFilterExprFieldName];
+ newOptionsMap[IndexDescriptor::kPartialFilterExprFieldName] =
+ infoObj()[IndexDescriptor::kPartialFilterExprFieldName];
+ }
- return existingOptionsMap.size() == newOptionsMap.size() &&
+ const bool optsIdentical = existingOptionsMap.size() == newOptionsMap.size() &&
std::equal(existingOptionsMap.begin(),
existingOptionsMap.end(),
newOptionsMap.begin(),
@@ -204,6 +250,10 @@ bool IndexDescriptor::areIndexOptionsEquivalent(const IndexDescriptor* other) co
SimpleBSONElementComparator::kInstance.evaluate(lhs.second ==
rhs.second);
});
+
+ // If all non-identifying options also match, the descriptors are identical. Otherwise, we
+ // consider them equivalent; two indexes with these options and the same key cannot coexist.
+ return optsIdentical ? Comparison::kIdentical : Comparison::kEquivalent;
}
} // namespace mongo
diff --git a/src/mongo/db/index/index_descriptor.h b/src/mongo/db/index/index_descriptor.h
index 4eab168a65a..c3d68d7a65d 100644
--- a/src/mongo/db/index/index_descriptor.h
+++ b/src/mongo/db/index/index_descriptor.h
@@ -59,6 +59,13 @@ public:
enum class IndexVersion { kV1 = 1, kV2 = 2 };
static constexpr IndexVersion kLatestIndexVersion = IndexVersion::kV2;
+ // Used to report the result of a comparison between two indexes.
+ enum class Comparison {
+ kDifferent, // Indicates that the indexes do not match.
+ kEquivalent, // Indicates that the options which uniquely identify an index match.
+ kIdentical // Indicates that all applicable index options match.
+ };
+
static constexpr StringData k2dIndexBitsFieldName = "bits"_sd;
static constexpr StringData k2dIndexMinFieldName = "min"_sd;
static constexpr StringData k2dIndexMaxFieldName = "max"_sd;
@@ -218,7 +225,12 @@ public:
}
const IndexCatalog* getIndexCatalog() const;
- bool areIndexOptionsEquivalent(const IndexDescriptor* other) const;
+ /**
+ * Compares the current IndexDescriptor against the given index entry. Returns kIdentical if all
+ * index options are logically identical, kEquivalent if all options which uniquely identify an
+ * index are logically identical, and kDifferent otherwise.
+ */
+ Comparison compareIndexOptions(OperationContext* opCtx, const IndexCatalogEntry* other) const;
const BSONObj& collation() const {
return _collation;
diff --git a/src/mongo/db/index_builds_coordinator.cpp b/src/mongo/db/index_builds_coordinator.cpp
index 89502ea72cd..0c3e6e794db 100644
--- a/src/mongo/db/index_builds_coordinator.cpp
+++ b/src/mongo/db/index_builds_coordinator.cpp
@@ -45,6 +45,7 @@
#include "mongo/db/concurrency/write_conflict_exception.h"
#include "mongo/db/curop.h"
#include "mongo/db/db_raii.h"
+#include "mongo/db/index/wildcard_key_generator.h"
#include "mongo/db/index_build_entry_helpers.h"
#include "mongo/db/op_observer.h"
#include "mongo/db/operation_context.h"
@@ -2453,15 +2454,15 @@ std::vector<BSONObj> IndexBuildsCoordinator::prepareSpecListForCreate(
return indexSpecs;
}
- auto specsWithCollationDefaults =
- uassertStatusOK(collection->addCollationDefaultsToIndexSpecsForCreate(opCtx, indexSpecs));
+ // Normalize the specs' collations, wildcard projections, and partial filters as applicable.
+ auto normalSpecs = normalizeIndexSpecs(opCtx, collection, indexSpecs);
+ // Remove any index specifications which already exist in the catalog.
auto indexCatalog = collection->getIndexCatalog();
- std::vector<BSONObj> resultSpecs;
-
- resultSpecs = indexCatalog->removeExistingIndexes(
- opCtx, specsWithCollationDefaults, true /*removeIndexBuildsToo*/);
+ auto resultSpecs =
+ indexCatalog->removeExistingIndexes(opCtx, normalSpecs, true /*removeIndexBuildsToo*/);
+ // Verify that each spec is compatible with the collection's sharding state.
for (const BSONObj& spec : resultSpecs) {
if (spec[kUniqueFieldName].trueValue()) {
checkShardKeyRestrictions(opCtx, nss, spec[kKeyFieldName].Obj());
@@ -2471,4 +2472,50 @@ std::vector<BSONObj> IndexBuildsCoordinator::prepareSpecListForCreate(
return resultSpecs;
}
+std::vector<BSONObj> IndexBuildsCoordinator::normalizeIndexSpecs(
+ OperationContext* opCtx, const Collection* collection, const std::vector<BSONObj>& indexSpecs) {
+ // This helper function may be called before the collection is created, when we are attempting
+ // to check whether the candidate index collides with any existing indexes. If 'collection' is
+ // nullptr, skip normalization. Since the collection does not exist there cannot be a conflict,
+ // and we will normalize once the candidate spec is submitted to the IndexBuildsCoordinator.
+ if (!collection) {
+ return indexSpecs;
+ }
+
+ // Add collection-default collation where needed and normalize the collation in each index spec.
+ auto normalSpecs =
+ uassertStatusOK(collection->addCollationDefaultsToIndexSpecsForCreate(opCtx, indexSpecs));
+
+ // If the index spec has a partialFilterExpression, we normalize it by parsing to an optimized,
+ // sorted MatchExpression tree, re-serialize it to BSON, and add it back into the index spec.
+ const auto expCtx = make_intrusive<ExpressionContext>(opCtx, nullptr, collection->ns());
+ std::transform(normalSpecs.begin(), normalSpecs.end(), normalSpecs.begin(), [&](auto& spec) {
+ const auto kPartialFilterName = IndexDescriptor::kPartialFilterExprFieldName;
+ auto partialFilterExpr = spec.getObjectField(kPartialFilterName);
+ if (partialFilterExpr.isEmpty()) {
+ return spec;
+ }
+ // Parse, optimize and sort the MatchExpression to reduce it to its normalized form.
+ // Serialize the normalized filter back into the index spec before returning.
+ auto partialFilter = MatchExpressionParser::parseAndNormalize(partialFilterExpr, expCtx);
+ return spec.addField(BSON(kPartialFilterName << partialFilter->serialize()).firstElement());
+ });
+
+ // If any of the specs describe wildcard indexes, normalize the wildcard projections if present.
+ // This will change all specs of the form {"a.b.c": 1} to normalized form {a: {b: {c : 1}}}.
+ std::transform(normalSpecs.begin(), normalSpecs.end(), normalSpecs.begin(), [](auto& spec) {
+ const auto kProjectionName = IndexDescriptor::kPathProjectionFieldName;
+ const auto pathProjectionSpec = spec.getObjectField(kProjectionName);
+ static const auto kWildcardKeyPattern = BSON("$**" << 1);
+ if (pathProjectionSpec.isEmpty()) {
+ return spec;
+ }
+ auto wildcardProjection =
+ WildcardKeyGenerator::createProjectionExecutor(kWildcardKeyPattern, pathProjectionSpec);
+ auto normalizedProjection =
+ wildcardProjection.exec()->serializeTransformation(boost::none).toBson();
+ return spec.addField(BSON(kProjectionName << normalizedProjection).firstElement());
+ });
+ return normalSpecs;
+}
} // namespace mongo
diff --git a/src/mongo/db/index_builds_coordinator.h b/src/mongo/db/index_builds_coordinator.h
index aecb7de265b..10464097996 100644
--- a/src/mongo/db/index_builds_coordinator.h
+++ b/src/mongo/db/index_builds_coordinator.h
@@ -424,6 +424,22 @@ public:
const std::vector<BSONObj>& indexSpecs);
/**
+ * Helper function which normalizes a vector of index specs. This function will populate a
+ * complete collation spec in cases where the index spec specifies a collation, and will add
+ * the collection-default collation, if present, in cases where collation is omitted. If the
+ * index spec omits the collation and the collection does not have a default, the collation
+ * field is omitted from the spec. This function also converts 'wildcardProjection' and
+ * 'partialFilterExpression' to canonical form in any cases where they exist.
+ *
+ * If 'collection' is null, no changes are made to the input specs.
+ *
+ * This function throws on error.
+ */
+ static std::vector<BSONObj> normalizeIndexSpecs(OperationContext* opCtx,
+ const Collection* collection,
+ const std::vector<BSONObj>& indexSpecs);
+
+ /**
* Returns total number of indexes in collection, including unfinished/in-progress indexes.
*
* Used to set statistics on index build results.
diff --git a/src/mongo/db/matcher/expression.cpp b/src/mongo/db/matcher/expression.cpp
index c035e417848..680b75a8001 100644
--- a/src/mongo/db/matcher/expression.cpp
+++ b/src/mongo/db/matcher/expression.cpp
@@ -40,12 +40,77 @@ namespace mongo {
*/
MONGO_FAIL_POINT_DEFINE(disableMatchExpressionOptimization);
+namespace {
+/**
+ * Comparator for MatchExpression nodes. Returns an integer less than, equal to, or greater
+ * than zero if 'lhs' is less than, equal to, or greater than 'rhs', respectively.
+ *
+ * Sorts by:
+ * 1) operator type (MatchExpression::MatchType)
+ * 2) path name (MatchExpression::path())
+ * 3) sort order of children
+ * 4) number of children (MatchExpression::numChildren())
+ *
+ * The third item is needed to ensure that match expression trees which should have the same
+ * cache key always sort the same way. If you're wondering when the tuple (operator type, path
+ * name) could ever be equal, consider this query:
+ *
+ * {$and:[{$or:[{a:1},{a:2}]},{$or:[{a:1},{b:2}]}]}
+ *
+ * The two OR nodes would compare as equal in this case were it not for tuple item #3 (sort
+ * order of children).
+ */
+int matchExpressionComparator(const MatchExpression* lhs, const MatchExpression* rhs) {
+ MatchExpression::MatchType lhsMatchType = lhs->matchType();
+ MatchExpression::MatchType rhsMatchType = rhs->matchType();
+ if (lhsMatchType != rhsMatchType) {
+ return lhsMatchType < rhsMatchType ? -1 : 1;
+ }
+
+ StringData lhsPath = lhs->path();
+ StringData rhsPath = rhs->path();
+ int pathsCompare = lhsPath.compare(rhsPath);
+ if (pathsCompare != 0) {
+ return pathsCompare;
+ }
+
+ const size_t numChildren = std::min(lhs->numChildren(), rhs->numChildren());
+ for (size_t childIdx = 0; childIdx < numChildren; ++childIdx) {
+ int childCompare =
+ matchExpressionComparator(lhs->getChild(childIdx), rhs->getChild(childIdx));
+ if (childCompare != 0) {
+ return childCompare;
+ }
+ }
+
+ if (lhs->numChildren() != rhs->numChildren()) {
+ return lhs->numChildren() < rhs->numChildren() ? -1 : 1;
+ }
+
+ // They're equal!
+ return 0;
+}
+
+bool matchExpressionLessThan(const MatchExpression* lhs, const MatchExpression* rhs) {
+ return matchExpressionComparator(lhs, rhs) < 0;
+}
+
+} // namespace
+
MatchExpression::MatchExpression(MatchType type) : _matchType(type) {}
+// static
+void MatchExpression::sortTree(MatchExpression* tree) {
+ for (size_t i = 0; i < tree->numChildren(); ++i) {
+ sortTree(tree->getChild(i));
+ }
+ if (auto&& children = tree->getChildVector()) {
+ std::stable_sort(children->begin(), children->end(), matchExpressionLessThan);
+ }
+}
+
std::string MatchExpression::toString() const {
- BSONObjBuilder bob;
- serialize(&bob, true);
- return bob.obj().toString();
+ return serialize().toString();
}
std::string MatchExpression::debugString() const {
diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
index f870dbcbcda..052ab19c7ea 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -158,6 +158,21 @@ public:
}
}
+ /**
+ * Traverses expression tree post-order. Sorts children at each non-leaf node by (MatchType,
+ * path(), children, number of children).
+ */
+ static void sortTree(MatchExpression* tree);
+
+ /**
+ * Convenience method which normalizes a MatchExpression tree by optimizing and then sorting it.
+ */
+ static std::unique_ptr<MatchExpression> normalize(std::unique_ptr<MatchExpression> tree) {
+ tree = optimize(std::move(tree));
+ sortTree(tree.get());
+ return tree;
+ }
+
MatchExpression(MatchType type);
virtual ~MatchExpression() {}
@@ -299,6 +314,15 @@ public:
virtual void serialize(BSONObjBuilder* out, bool includePath = true) const = 0;
/**
+ * Convenience method which serializes this MatchExpression to a BSONObj.
+ */
+ BSONObj serialize(bool includePath = true) const {
+ BSONObjBuilder bob;
+ serialize(&bob, includePath);
+ return bob.obj();
+ }
+
+ /**
* Returns true if this expression will always evaluate to false, such as an $or with no
* children.
*/
diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index a06e07b82d7..91caf31241c 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -1741,6 +1741,15 @@ StatusWithMatchExpression MatchExpressionParser::parse(
}
}
+std::unique_ptr<MatchExpression> MatchExpressionParser::parseAndNormalize(
+ const BSONObj& obj,
+ const boost::intrusive_ptr<ExpressionContext>& expCtx,
+ const ExtensionsCallback& extensionsCallback,
+ AllowedFeatureSet allowedFeatures) {
+ auto parsedTree = uassertStatusOK(parse(obj, expCtx, extensionsCallback, allowedFeatures));
+ return MatchExpression::normalize(std::move(parsedTree));
+}
+
namespace {
// Maps from query operator string name to function.
std::unique_ptr<StringMap<
diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h
index b4048949055..c0b7691d108 100644
--- a/src/mongo/db/matcher/expression_parser.h
+++ b/src/mongo/db/matcher/expression_parser.h
@@ -124,5 +124,15 @@ public:
const boost::intrusive_ptr<ExpressionContext>& expCtx,
const ExtensionsCallback& extensionsCallback = ExtensionsCallbackNoop(),
AllowedFeatureSet allowedFeatures = kDefaultSpecialFeatures);
+
+ /**
+ * Parse the given MatchExpression and normalize the resulting tree by optimizing and then
+ * sorting it. Throws if the given BSONObj fails to parse.
+ */
+ static std::unique_ptr<MatchExpression> parseAndNormalize(
+ const BSONObj& obj,
+ const boost::intrusive_ptr<ExpressionContext>& expCtx,
+ const ExtensionsCallback& extensionsCallback = ExtensionsCallbackNoop(),
+ AllowedFeatureSet allowedFeatures = kDefaultSpecialFeatures);
};
} // namespace mongo
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index fdb8cc496ec..b27040895ba 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -46,60 +46,6 @@
namespace mongo {
namespace {
-/**
- * Comparator for MatchExpression nodes. Returns an integer less than, equal to, or greater
- * than zero if 'lhs' is less than, equal to, or greater than 'rhs', respectively.
- *
- * Sorts by:
- * 1) operator type (MatchExpression::MatchType)
- * 2) path name (MatchExpression::path())
- * 3) sort order of children
- * 4) number of children (MatchExpression::numChildren())
- *
- * The third item is needed to ensure that match expression trees which should have the same
- * cache key always sort the same way. If you're wondering when the tuple (operator type, path
- * name) could ever be equal, consider this query:
- *
- * {$and:[{$or:[{a:1},{a:2}]},{$or:[{a:1},{b:2}]}]}
- *
- * The two OR nodes would compare as equal in this case were it not for tuple item #3 (sort
- * order of children).
- */
-int matchExpressionComparator(const MatchExpression* lhs, const MatchExpression* rhs) {
- MatchExpression::MatchType lhsMatchType = lhs->matchType();
- MatchExpression::MatchType rhsMatchType = rhs->matchType();
- if (lhsMatchType != rhsMatchType) {
- return lhsMatchType < rhsMatchType ? -1 : 1;
- }
-
- StringData lhsPath = lhs->path();
- StringData rhsPath = rhs->path();
- int pathsCompare = lhsPath.compare(rhsPath);
- if (pathsCompare != 0) {
- return pathsCompare;
- }
-
- const size_t numChildren = std::min(lhs->numChildren(), rhs->numChildren());
- for (size_t childIdx = 0; childIdx < numChildren; ++childIdx) {
- int childCompare =
- matchExpressionComparator(lhs->getChild(childIdx), rhs->getChild(childIdx));
- if (childCompare != 0) {
- return childCompare;
- }
- }
-
- if (lhs->numChildren() != rhs->numChildren()) {
- return lhs->numChildren() < rhs->numChildren() ? -1 : 1;
- }
-
- // They're equal!
- return 0;
-}
-
-bool matchExpressionLessThan(const MatchExpression* lhs, const MatchExpression* rhs) {
- return matchExpressionComparator(lhs, rhs) < 0;
-}
-
bool parsingCanProduceNoopMatchNodes(const ExtensionsCallback& extensionsCallback,
MatchExpressionParser::AllowedFeatureSet allowedFeatures) {
return extensionsCallback.hasNoopExtensions() &&
@@ -225,9 +171,8 @@ Status CanonicalQuery::init(OperationContext* opCtx,
_canHaveNoopMatchNodes = canHaveNoopMatchNodes;
- // Normalize, sort and validate tree.
- _root = MatchExpression::optimize(std::move(root));
- sortTree(_root.get());
+ // Normalize and validate tree.
+ _root = MatchExpression::normalize(std::move(root));
auto validStatus = isValid(_root.get(), *_qr);
if (!validStatus.isOK()) {
return validStatus.getStatus();
@@ -335,17 +280,6 @@ bool CanonicalQuery::isSimpleIdQuery(const BSONObj& query) {
return hasID;
}
-// static
-void CanonicalQuery::sortTree(MatchExpression* tree) {
- for (size_t i = 0; i < tree->numChildren(); ++i) {
- sortTree(tree->getChild(i));
- }
- if (auto&& children = tree->getChildVector()) {
- std::stable_sort(children->begin(), children->end(), matchExpressionLessThan);
- }
-}
-
-// static
size_t CanonicalQuery::countNodes(const MatchExpression* root, MatchExpression::MatchType type) {
size_t sum = 0;
if (type == root->matchType()) {
diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h
index e1261805e20..ca5199e3502 100644
--- a/src/mongo/db/query/canonical_query.h
+++ b/src/mongo/db/query/canonical_query.h
@@ -191,12 +191,6 @@ public:
std::string toStringShort() const;
/**
- * Traverses expression tree post-order.
- * Sorts children at each non-leaf node by (MatchType, path(), children, number of children)
- */
- static void sortTree(MatchExpression* tree);
-
- /**
* Returns a count of 'type' nodes in expression tree.
*/
static size_t countNodes(const MatchExpression* root, MatchExpression::MatchType type);
diff --git a/src/mongo/db/query/canonical_query_test.cpp b/src/mongo/db/query/canonical_query_test.cpp
index 1afb06988f7..7d159ae47f2 100644
--- a/src/mongo/db/query/canonical_query_test.cpp
+++ b/src/mongo/db/query/canonical_query_test.cpp
@@ -118,11 +118,11 @@ TEST(CanonicalQueryTest, IsValidSortKeyMetaProjection) {
}
//
-// Tests for CanonicalQuery::sortTree
+// Tests for MatchExpression::sortTree
//
/**
- * Helper function for testing CanonicalQuery::sortTree().
+ * Helper function for testing MatchExpression::sortTree().
*
* Verifies that sorting the expression 'unsortedQueryStr' yields an expression equivalent to
* the expression 'sortedQueryStr'.
@@ -140,12 +140,12 @@ void testSortTree(const char* unsortedQueryStr, const char* sortedQueryStr) {
// Sanity check that sorting the sorted expression is a no-op.
{
unique_ptr<MatchExpression> sortedQueryExprClone(parseMatchExpression(sortedQueryObj));
- CanonicalQuery::sortTree(sortedQueryExprClone.get());
+ MatchExpression::sortTree(sortedQueryExprClone.get());
assertEquivalent(unsortedQueryStr, sortedQueryExpr.get(), sortedQueryExprClone.get());
}
// Test that sorting the unsorted expression yields the sorted expression.
- CanonicalQuery::sortTree(unsortedQueryExpr.get());
+ MatchExpression::sortTree(unsortedQueryExpr.get());
assertEquivalent(unsortedQueryStr, unsortedQueryExpr.get(), sortedQueryExpr.get());
}
diff --git a/src/mongo/db/query/query_planner_partialidx_test.cpp b/src/mongo/db/query/query_planner_partialidx_test.cpp
index ecb574fa728..46adc5869ab 100644
--- a/src/mongo/db/query/query_planner_partialidx_test.cpp
+++ b/src/mongo/db/query/query_planner_partialidx_test.cpp
@@ -502,5 +502,49 @@ TEST_F(QueryPlannerTest, InternalExprEqCannotUsePartialIndex) {
assertNoSolutions();
}
+TEST_F(QueryPlannerTest, MultipleOverlappingPartialIndexes) {
+ params.options = QueryPlannerParams::NO_TABLE_SCAN;
+
+ // Create two partial indexes with an overlapping range on the same key pattern.
+ BSONObj minus5To5 = fromjson("{a: {$gte: -5, $lte: 5}}");
+ BSONObj gte0 = fromjson("{a: {$gte: 0}}");
+ std::unique_ptr<MatchExpression> minus5To5Filter = parseMatchExpression(minus5To5);
+ std::unique_ptr<MatchExpression> gte0Filter = parseMatchExpression(gte0);
+ addIndex(fromjson("{a: 1}"), minus5To5Filter.get());
+ params.indices.back().identifier = CoreIndexInfo::Identifier{"minus5To5"};
+ addIndex(fromjson("{a: 1}"), gte0Filter.get());
+ params.indices.back().identifier = CoreIndexInfo::Identifier{"gte0"};
+
+ // Test that both indexes are eligible when the query falls within the intersecting range.
+ runQuery(fromjson("{a: 1}"));
+ assertNumSolutions(2U);
+ assertSolutionExists(
+ "{fetch: {filter: null, node: {ixscan: "
+ "{filter: null, pattern: {a: 1}, name: 'minus5To5', "
+ "bounds: {a: [[1, 1, true, true]]}}}}}");
+ assertSolutionExists(
+ "{fetch: {filter: null, node: {ixscan: "
+ "{filter: null, pattern: {a: 1}, name: 'gte0', "
+ "bounds: {a: [[1, 1, true, true]]}}}}}");
+
+ // Test that only a single index is eligible when the query falls within a single range.
+ runQuery(fromjson("{a: -5}"));
+ assertNumSolutions(1U);
+ assertSolutionExists(
+ "{fetch: {filter: null, node: {ixscan: "
+ "{filter: null, pattern: {a: 1}, name: 'minus5To5', "
+ "bounds: {a: [[-5, -5, true, true]]}}}}}");
+ runQuery(fromjson("{a: 10}"));
+ assertNumSolutions(1U);
+ assertSolutionExists(
+ "{fetch: {filter: null, node: {ixscan: "
+ "{filter: null, pattern: {a: 1}, name: 'gte0', "
+ "bounds: {a: [[10, 10, true, true]]}}}}}");
+
+ // Test that neither index is eligible when the query falls outside both ranges.
+ runInvalidQuery(fromjson("{a: -10}"));
+ assertNoSolutions();
+}
+
} // namespace
} // namespace mongo
diff --git a/src/mongo/db/query/query_planner_test_lib.cpp b/src/mongo/db/query/query_planner_test_lib.cpp
index 6082fc79e61..7e424c23c2a 100644
--- a/src/mongo/db/query/query_planner_test_lib.cpp
+++ b/src/mongo/db/query/query_planner_test_lib.cpp
@@ -82,9 +82,9 @@ bool filterMatches(const BSONObj& testFilter,
return false;
}
const std::unique_ptr<MatchExpression> root = std::move(statusWithMatcher.getValue());
- CanonicalQuery::sortTree(root.get());
+ MatchExpression::sortTree(root.get());
std::unique_ptr<MatchExpression> trueFilter(trueFilterNode->filter->shallowClone());
- CanonicalQuery::sortTree(trueFilter.get());
+ MatchExpression::sortTree(trueFilter.get());
return trueFilter->equivalent(root.get());
}
diff --git a/src/mongo/dbtests/plan_executor_invalidation_test.cpp b/src/mongo/dbtests/plan_executor_invalidation_test.cpp
index a7e949465bd..23acefa8019 100644
--- a/src/mongo/dbtests/plan_executor_invalidation_test.cpp
+++ b/src/mongo/dbtests/plan_executor_invalidation_test.cpp
@@ -38,6 +38,7 @@
#include "mongo/db/dbdirectclient.h"
#include "mongo/db/exec/collection_scan.h"
#include "mongo/db/exec/plan_stage.h"
+#include "mongo/db/index/index_descriptor.h"
#include "mongo/db/json.h"
#include "mongo/db/matcher/expression_parser.h"
#include "mongo/db/query/internal_plans.h"
@@ -100,9 +101,8 @@ public:
std::unique_ptr<PlanExecutor, PlanExecutor::Deleter> makeIxscanPlan(BSONObj keyPattern,
BSONObj startKey,
BSONObj endKey) {
- auto indexDescriptor =
- collection()->getIndexCatalog()->findIndexByKeyPatternAndCollationSpec(
- &_opCtx, keyPattern, {});
+ auto indexDescriptor = collection()->getIndexCatalog()->findIndexByKeyPatternAndOptions(
+ &_opCtx, keyPattern, _makeMinimalIndexSpec(keyPattern));
ASSERT(indexDescriptor);
return InternalPlanner::indexScan(&_opCtx,
collection(),
@@ -134,6 +134,13 @@ public:
DBDirectClient _client;
boost::intrusive_ptr<ExpressionContext> _expCtx;
+
+private:
+ BSONObj _makeMinimalIndexSpec(BSONObj keyPattern) {
+ return BSON(IndexDescriptor::kKeyPatternFieldName
+ << keyPattern << IndexDescriptor::kIndexVersionFieldName
+ << IndexDescriptor::getDefaultIndexVersion());
+ }
};
TEST_F(PlanExecutorInvalidationTest, ExecutorToleratesDeletedDocumentsDuringYield) {
diff --git a/src/mongo/dbtests/query_stage_near.cpp b/src/mongo/dbtests/query_stage_near.cpp
index 938a98e2f88..2976c4cfeb1 100644
--- a/src/mongo/dbtests/query_stage_near.cpp
+++ b/src/mongo/dbtests/query_stage_near.cpp
@@ -69,12 +69,18 @@ public:
_autoColl.emplace(_opCtx, NamespaceString{kTestNamespace});
auto* coll = _autoColl->getCollection();
ASSERT(coll);
- _mockGeoIndex = coll->getIndexCatalog()->findIndexByKeyPatternAndCollationSpec(
- _opCtx, kTestKeyPattern, BSONObj{});
+ _mockGeoIndex = coll->getIndexCatalog()->findIndexByKeyPatternAndOptions(
+ _opCtx, kTestKeyPattern, _makeMinimalIndexSpec(kTestKeyPattern));
ASSERT(_mockGeoIndex);
}
protected:
+ BSONObj _makeMinimalIndexSpec(BSONObj keyPattern) {
+ return BSON(IndexDescriptor::kKeyPatternFieldName
+ << keyPattern << IndexDescriptor::kIndexVersionFieldName
+ << IndexDescriptor::getDefaultIndexVersion());
+ }
+
const ServiceContext::UniqueOperationContext _uniqOpCtx = cc().makeOperationContext();
OperationContext* const _opCtx = _uniqOpCtx.get();
DBDirectClient directClient{_opCtx};