SERVER-22785 Update QueryPlannerIXSelect's index selection code to be collation-aware

6 files changed, 550 insertions, 27 deletions

diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index 574bc0ede8e..65c93dcff6c 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -305,6 +305,7 @@ env.CppUnitTest(
         "planner_ixselect_test.cpp"
     ],
     LIBDEPS=[
+        "collation/collator_interface_mock",
         "query_planner",
     ],
 )
diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h
index a68bf3f328a..6c8ce44bbb8 100644
--- a/src/mongo/db/query/indexability.h
+++ b/src/mongo/db/query/indexability.h
@@ -131,6 +131,15 @@ public:
         return isBoundsGeneratingNot(me) || nodeCanUseIndexOnOwnField(me);
     }
 
+    /**
+     * Returns true if 'me' is of type EQ, GT, GTE, LT, or LTE.
+     */
+    static bool isEqualityOrInequality(const MatchExpression* me) {
+        return (me->matchType() == MatchExpression::EQ || me->matchType() == MatchExpression::GT ||
+                me->matchType() == MatchExpression::GTE || me->matchType() == MatchExpression::LT ||
+                me->matchType() == MatchExpression::LTE);
+    }
+
 private:
     /**
      * Returns true if 'me' is "sargable" but is not a negation and
diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp
index 52a357eb95b..f340f39915a 100644
--- a/src/mongo/db/query/planner_ixselect.cpp
+++ b/src/mongo/db/query/planner_ixselect.cpp
@@ -39,6 +39,7 @@
 #include "mongo/db/matcher/expression_array.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/matcher/expression_text.h"
+#include "mongo/db/query/collation/collator_interface.h"
 #include "mongo/db/query/indexability.h"
 #include "mongo/db/query/index_tag.h"
 #include "mongo/db/query/query_planner_common.h"
@@ -72,6 +73,57 @@ static bool twoDWontWrap(const Circle& circle, const IndexEntry& index) {
     return ret;
 }
 
+static bool collatorsMatch(const CollatorInterface* lhs, const CollatorInterface* rhs) {
+    if (lhs == nullptr && rhs == nullptr) {
+        return true;
+    }
+    if (lhs == nullptr || rhs == nullptr) {
+        return false;
+    }
+    return (*lhs == *rhs);
+}
+
+// Checks whether 'node' contains any string comparison. We assume 'node' is bounds-generating or is
+// a recursive child of a bounds-generating node, i.e. it does not contain AND, OR,
+// ELEM_MATCH_OBJECT, or NOR.
+static bool boundsGeneratingNodeContainsStringComparison(MatchExpression* node) {
+    invariant(node->matchType() != MatchExpression::AND &&
+              node->matchType() != MatchExpression::OR &&
+              node->matchType() != MatchExpression::NOR &&
+              node->matchType() != MatchExpression::ELEM_MATCH_OBJECT);
+
+    if (Indexability::isEqualityOrInequality(node)) {
+        const ComparisonMatchExpression* expr = static_cast<const ComparisonMatchExpression*>(node);
+        return expr->getData().type() == BSONType::String;
+    }
+
+    if (node->matchType() == MatchExpression::MATCH_IN) {
+        const InMatchExpression* expr = static_cast<const InMatchExpression*>(node);
+        for (auto const& equality : expr->getData().equalities()) {
+            if (equality.type() == BSONType::String) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    if (node->matchType() == MatchExpression::NOT) {
+        invariant(node->numChildren() == 1U);
+        return boundsGeneratingNodeContainsStringComparison(node->getChild(0));
+    }
+
+    if (node->matchType() == MatchExpression::ELEM_MATCH_VALUE) {
+        for (size_t i = 0; i < node->numChildren(); ++i) {
+            if (boundsGeneratingNodeContainsStringComparison(node->getChild(i))) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    return false;
+}
+
 // static
 void QueryPlannerIXSelect::getFields(const MatchExpression* node,
                                      string prefix,
@@ -123,7 +175,14 @@ void QueryPlannerIXSelect::findRelevantIndices(const unordered_set<string>& fiel
 // static
 bool QueryPlannerIXSelect::compatible(const BSONElement& elt,
                                       const IndexEntry& index,
-                                      MatchExpression* node) {
+                                      MatchExpression* node,
+                                      const CollatorInterface* collator) {
+    // String comparisons require the collators to match.
+    if (boundsGeneratingNodeContainsStringComparison(node) &&
+        !collatorsMatch(collator, index.collator)) {
+        return false;
+    }
+
     // Historically one could create indices with any particular value for the index spec,
     // including values that now indicate a special index.  As such we have to make sure the
     // index type wasn't overridden before we pay attention to the string in the index key
@@ -306,7 +365,8 @@ bool QueryPlannerIXSelect::compatible(const BSONElement& elt,
 // static
 void QueryPlannerIXSelect::rateIndices(MatchExpression* node,
                                        string prefix,
-                                       const vector<IndexEntry>& indices) {
+                                       const vector<IndexEntry>& indices,
+                                       const CollatorInterface* collator) {
     // Do not traverse tree beyond logical NOR node
     MatchExpression::MatchType exprtype = node->matchType();
     if (exprtype == MatchExpression::NOR) {
@@ -332,12 +392,12 @@ void QueryPlannerIXSelect::rateIndices(MatchExpression* node,
         for (size_t i = 0; i < indices.size(); ++i) {
             BSONObjIterator it(indices[i].keyPattern);
             BSONElement elt = it.next();
-            if (elt.fieldName() == fullPath && compatible(elt, indices[i], node)) {
+            if (elt.fieldName() == fullPath && compatible(elt, indices[i], node, collator)) {
                 rt->first.push_back(i);
             }
             while (it.more()) {
                 elt = it.next();
-                if (elt.fieldName() == fullPath && compatible(elt, indices[i], node)) {
+                if (elt.fieldName() == fullPath && compatible(elt, indices[i], node, collator)) {
                     rt->notFirst.push_back(i);
                 }
             }
@@ -356,11 +416,11 @@ void QueryPlannerIXSelect::rateIndices(MatchExpression* node,
             prefix += node->path().toString() + ".";
         }
         for (size_t i = 0; i < node->numChildren(); ++i) {
-            rateIndices(node->getChild(i), prefix, indices);
+            rateIndices(node->getChild(i), prefix, indices, collator);
         }
     } else if (node->isLogical()) {
         for (size_t i = 0; i < node->numChildren(); ++i) {
-            rateIndices(node->getChild(i), prefix, indices);
+            rateIndices(node->getChild(i), prefix, indices, collator);
         }
     }
 }
diff --git a/src/mongo/db/query/planner_ixselect.h b/src/mongo/db/query/planner_ixselect.h
index 2928b708677..914e9265d9b 100644
--- a/src/mongo/db/query/planner_ixselect.h
+++ b/src/mongo/db/query/planner_ixselect.h
@@ -35,6 +35,8 @@
 
 namespace mongo {
 
+class CollatorInterface;
+
 /**
  * Methods for determining what fields and predicates can use indices.
  */
@@ -67,7 +69,10 @@ public:
      *              {field: "2d"} can only be used with some geo predicates.
      *              {field: "2dsphere"} can only be used with some other geo predicates.
      */
-    static bool compatible(const BSONElement& elt, const IndexEntry& index, MatchExpression* node);
+    static bool compatible(const BSONElement& elt,
+                           const IndexEntry& index,
+                           MatchExpression* node,
+                           const CollatorInterface* collator);
 
     /**
      * Determine how useful all of our relevant 'indices' are to all predicates in the subtree
@@ -86,7 +91,8 @@ public:
      */
     static void rateIndices(MatchExpression* node,
                             std::string prefix,
-                            const std::vector<IndexEntry>& indices);
+                            const std::vector<IndexEntry>& indices,
+                            const CollatorInterface* collator);
 
     /**
      * Amend the RelevantTag lists for all predicates in the subtree rooted at 'node' to remove
diff --git a/src/mongo/db/query/planner_ixselect_test.cpp b/src/mongo/db/query/planner_ixselect_test.cpp
index 88fb6e44664..3dede18abc1 100644
--- a/src/mongo/db/query/planner_ixselect_test.cpp
+++ b/src/mongo/db/query/planner_ixselect_test.cpp
@@ -36,6 +36,7 @@
 #include "mongo/db/json.h"
 #include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/matcher/extensions_callback_disallow_extensions.h"
+#include "mongo/db/query/collation/collator_interface_mock.h"
 #include "mongo/db/query/index_tag.h"
 #include "mongo/unittest/unittest.h"
 #include "mongo/util/text.h"
@@ -155,8 +156,11 @@ TEST(QueryPlannerIXSelectTest, GetFieldsArrayNegation) {
 /**
  * Performs a pre-order traversal of expression tree. Validates
  * that all tagged nodes contain an instance of RelevantTag.
+ * Finds all indices included in RelevantTags, and returns them in the 'indices' out-parameter.
  */
-void findRelevantTaggedNodePaths(MatchExpression* root, vector<string>* paths) {
+void findRelevantTaggedNodePathsAndIndices(MatchExpression* root,
+                                           vector<string>* paths,
+                                           std::set<size_t>* indices) {
     MatchExpression::TagData* tag = root->getTag();
     if (tag) {
         StringBuilder buf;
@@ -169,38 +173,51 @@ void findRelevantTaggedNodePaths(MatchExpression* root, vector<string>* paths) {
             FAIL(ss);
         }
         paths->push_back(r->path);
+        for (auto const& index : r->first) {
+            indices->insert(index);
+        }
+        for (auto const& index : r->notFirst) {
+            indices->insert(index);
+        }
     }
     for (size_t i = 0; i < root->numChildren(); ++i) {
-        findRelevantTaggedNodePaths(root->getChild(i), paths);
+        findRelevantTaggedNodePathsAndIndices(root->getChild(i), paths, indices);
     }
 }
 
 /**
- * Parses a MatchExpression from query string and passes that along with
- * prefix to rateIndices.
- * Verifies results against list of expected paths.
- * For now, we're only interested in which nodes are tagged.
- * In future, we may expand this test function to include
- * validate which indices are assigned to a node.
+ * Parses a MatchExpression from query string and passes that along with prefix, collator, and
+ * indices to rateIndices. Verifies results against list of expected paths and expected indices. In
+ * future, we may expand this test function to validate which indices are assigned to which node.
  */
-void testRateIndicesTaggedNodePaths(const char* query,
-                                    const char* prefix,
-                                    const char* expectedPathsStr) {
+void testRateIndices(const char* query,
+                     const char* prefix,
+                     const CollatorInterface* collator,
+                     const vector<IndexEntry>& indices,
+                     const char* expectedPathsStr,
+                     const std::set<size_t>& expectedIndices) {
     // Parse and rate query. Some of the nodes in the rated tree
     // will be tagged after the rating process.
     BSONObj obj = fromjson(query);
     unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
 
-    // Currently, we tag every indexable node even when no compatible
-    // index is available. Hence, it is fine to pass an empty vector of
-    // indices to rateIndices().
-    vector<IndexEntry> indices;
-    QueryPlannerIXSelect::rateIndices(expr.get(), prefix, indices);
+    QueryPlannerIXSelect::rateIndices(expr.get(), prefix, indices, collator);
 
-    // Retrieve a list of paths embedded in
+    // Retrieve a list of paths and a set of indices embedded in
     // tagged nodes.
     vector<string> paths;
-    findRelevantTaggedNodePaths(expr.get(), &paths);
+    std::set<size_t> actualIndices;
+    findRelevantTaggedNodePathsAndIndices(expr.get(), &paths, &actualIndices);
+
+    // Compare the expected indices with the actual indices.
+    if (actualIndices != expectedIndices) {
+        mongoutils::str::stream ss;
+        ss << "rateIndices(query=" << query << ", prefix=" << prefix
+           << "): expected indices did not match actual indices. expected: "
+           << toString(expectedIndices.begin(), expectedIndices.end())
+           << ". actual: " << toString(actualIndices.begin(), actualIndices.end());
+        FAIL(ss);
+    }
 
     // Compare with expected list of paths.
     // First verify number of paths retrieved.
@@ -231,6 +248,21 @@ void testRateIndicesTaggedNodePaths(const char* query,
 }
 
 /**
+ * Calls testRateIndices with an empty set of indices and a null collation, so we only test which
+ * nodes are tagged.
+ */
+void testRateIndicesTaggedNodePaths(const char* query,
+                                    const char* prefix,
+                                    const char* expectedPathsStr) {
+    // Currently, we tag every indexable node even when no compatible
+    // index is available. Hence, it is fine to pass an empty vector of
+    // indices to rateIndices().
+    vector<IndexEntry> indices;
+    std::set<size_t> expectedIndices;
+    testRateIndices(query, prefix, nullptr, indices, expectedPathsStr, expectedIndices);
+}
+
+/**
  * Basic test cases for rateIndices().
  * Includes logical operators.
  */
@@ -270,4 +302,418 @@ TEST(QueryPlannerIXSelectTest, RateIndicesTaggedNodePathArrayNegation) {
     testRateIndicesTaggedNodePaths("{a: {$all: [{$elemMatch: {b: {$ne: 1}}}]}}", "", "a.b,a.b");
 }
 
+/**
+ * If the collator is null, we select the relevant index with a null collator.
+ */
+TEST(QueryPlannerIXSelectTest, NullCollatorsMatch) {
+    std::vector<IndexEntry> indices;
+    indices.push_back(IndexEntry(BSON("a" << 1)));
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: 'string'}", "", nullptr, indices, "a", expectedIndices);
+}
+
+/**
+ * If the collator is not null, we do not select the relevant index with a null collator.
+ */
+TEST(QueryPlannerIXSelectTest, NonNullCollatorDoesNotMatchIndexWithNullCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    std::vector<IndexEntry> indices;
+    indices.push_back(IndexEntry(BSON("a" << 1)));
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: 'string'}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If the collator is null, we do not select the relevant index with a non-null collator.
+ */
+TEST(QueryPlannerIXSelectTest, NullCollatorDoesNotMatchIndexWithNonNullCollator) {
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: 'string'}", "", nullptr, indices, "a", expectedIndices);
+}
+
+/**
+ * If the collator is non-null, we select the relevant index with an equal collator.
+ */
+TEST(QueryPlannerIXSelectTest, EqualCollatorsMatch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: 'string'}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If the collator is non-null, we do not select the relevant index with an unequal collator.
+ */
+TEST(QueryPlannerIXSelectTest, UnequalCollatorsDoNotMatch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: 'string'}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done, unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparison) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: 1}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * $gt string comparison requires matching collator.
+ */
+TEST(QueryPlannerIXSelectTest, StringGTRequiresMatchingCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$gt: 'string'}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$gt: 'string'}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * $gte string comparison requires matching collator.
+ */
+TEST(QueryPlannerIXSelectTest, StringGTERequiresMatchingCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$gte: 'string'}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$gte: 'string'}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * $lt string comparison requires matching collator.
+ */
+TEST(QueryPlannerIXSelectTest, StringLTRequiresMatchingCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$lt: 'string'}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$lt: 'string'}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * $lte string comparison requires matching collator.
+ */
+TEST(QueryPlannerIXSelectTest, StringLTERequiresMatchingCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$lte: 'string'}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$lte: 'string'}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in an 'in' expression, unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonInExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$in: [1, 2]}}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in an 'in' expression, matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonInExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$in: [1, 2, 'b', 3]}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices(
+        "{a: {$in: [1, 2, 'b', 3]}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in a 'not' expression, unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonNotExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$not: {$gt: 1}}}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in a 'not' expression, matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonNotExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$not: {$gt: 'a'}}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$not: {$gt: 'a'}}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in an elemMatch value, unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonElemMatchValueExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$elemMatch: {$gt: 1}}}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in an elemMatch value, matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonElemMatchValueExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices(
+        "{a: {$elemMatch: {$gt: 'string'}}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices(
+        "{a: {$elemMatch: {$gt: 'string'}}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in an 'in' in a 'not', unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonNotInExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$not: {$in: [1]}}}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in an 'in' in a 'not', matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonNotInExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$not: {$in: ['a']}}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$not: {$in: ['a']}}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in a 'nin', unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonNinExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$nin: [1]}}", "", &collator, indices, "a,a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in a 'nin', matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonNinExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$nin: ['a']}}", "", &collator, indices, "a,a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$nin: ['a']}}", "", &indexCollator, indices, "a,a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in an 'or', matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonOrExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{$or: [{a: 'string'}]}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{$or: [{a: 'string'}]}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in an 'and', matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonAndExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{$and: [{a: 'string'}]}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{$and: [{a: 'string'}]}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in an 'all', matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonAllExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices("{a: {$all: ['string']}}", "", &collator, indices, "a", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices("{a: {$all: ['string']}}", "", &indexCollator, indices, "a", expectedIndices);
+}
+
+/**
+ * If string comparison is done in an elemMatch object, matching collators are required.
+ */
+TEST(QueryPlannerIXSelectTest, StringComparisonElemMatchObjectExpression) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a.b" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices;
+    testRateIndices(
+        "{a: {$elemMatch: {b: 'string'}}}", "", &collator, indices, "a.b", expectedIndices);
+
+    expectedIndices.insert(0);
+    testRateIndices(
+        "{a: {$elemMatch: {b: 'string'}}}", "", &indexCollator, indices, "a.b", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in a query containing $mod, unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonMod) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$mod: [2, 0]}}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in a query containing $exists, unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonExists) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$exists: true}}", "", &collator, indices, "a", expectedIndices);
+}
+
+/**
+ * If no string comparison is done in a query containing $type, unequal collators are allowed.
+ */
+TEST(QueryPlannerIXSelectTest, NoStringComparisonType) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    IndexEntry index(BSON("a" << 1));
+    CollatorInterfaceMock indexCollator(CollatorInterfaceMock::MockType::kReverseString);
+    index.collator = &indexCollator;
+    std::vector<IndexEntry> indices;
+    indices.push_back(index);
+    std::set<size_t> expectedIndices = {0};
+    testRateIndices("{a: {$type: 'string'}}", "", &collator, indices, "a", expectedIndices);
+}
+
 }  // namespace
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 9540d40912e..eb39d9ae2db 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -659,7 +659,8 @@ Status QueryPlanner::plan(const CanonicalQuery& query,
     }
 
     // Figure out how useful each index is to each predicate.
-    QueryPlannerIXSelect::rateIndices(query.root(), "", relevantIndices);
+    // TODO: pass the appropriate collator to rateIndices instead of nullptr.
+    QueryPlannerIXSelect::rateIndices(query.root(), "", relevantIndices, nullptr);
     QueryPlannerIXSelect::stripInvalidAssignments(query.root(), relevantIndices);
 
     // Unless we have GEO_NEAR, TEXT, or a projection, we may be able to apply an optimization