SERVER-22786 update index bounds builder for collations

The IndexBoundsBuilder must use collator-generated comparison keys
when generating bounds for strings, rather than the string itself.

The bounds builder also enforces the property that regex predicates
cannot use tight bounds if the index has a collation.

12 files changed, 1031 insertions, 140 deletions

diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript
index 65c93dcff6c..083c40442a7 100644
--- a/src/mongo/db/query/SConscript
+++ b/src/mongo/db/query/SConscript
@@ -108,11 +108,13 @@ env.Library(
     ],
     LIBDEPS=[
         "$BUILD_DIR/mongo/base",
-        "$BUILD_DIR/mongo/db/index_names",
         "$BUILD_DIR/mongo/db/index/expression_params",
+        "$BUILD_DIR/mongo/db/index_names",
         "$BUILD_DIR/mongo/db/matcher/expressions_geo",
         "$BUILD_DIR/mongo/db/mongohasher",
         "$BUILD_DIR/mongo/db/server_parameters",
+        "collation/collation_index_key",
+        "collation/collator_interface",
     ],
 )
 
@@ -226,6 +228,7 @@ env.CppUnitTest(
         "index_bounds_builder_test.cpp"
     ],
     LIBDEPS=[
+        "collation/collator_interface_mock",
         "index_bounds",
     ],
 )
diff --git a/src/mongo/db/query/collation/SConscript b/src/mongo/db/query/collation/SConscript
index 45fa1eec2b5..0ea9a1df513 100644
--- a/src/mongo/db/query/collation/SConscript
+++ b/src/mongo/db/query/collation/SConscript
@@ -75,6 +75,28 @@ env.CppUnitTest(
     ],
 )
 
+env.Library(
+    target="collation_index_key",
+    source=[
+        "collation_index_key.cpp",
+    ],
+    LIBDEPS=[
+        "$BUILD_DIR/mongo/base",
+        "collator_interface",
+    ],
+)
+
+env.CppUnitTest(
+    target="collation_index_key_test",
+    source=[
+        "collation_index_key_test.cpp",
+    ],
+    LIBDEPS=[
+        "collation_index_key",
+        "collator_interface_mock",
+    ],
+)
+
 if icuEnabled:
     env.Library(
         target="collator_icu",
diff --git a/src/mongo/db/query/collation/collation_index_key.cpp b/src/mongo/db/query/collation/collation_index_key.cpp
new file mode 100644
index 00000000000..8d30061d8a9
--- /dev/null
+++ b/src/mongo/db/query/collation/collation_index_key.cpp
@@ -0,0 +1,57 @@
+/**
+ *    Copyright (C) 2016 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    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
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    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 GNU Affero General 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/query/collation/collation_index_key.h"
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/query/collation/collator_interface.h"
+
+namespace mongo {
+
+// TODO SERVER-23172: Update this to consider strings inside nested objects or arrays.
+bool CollationIndexKey::shouldUseCollationIndexKey(BSONElement elt, CollatorInterface* collator) {
+    return collator && elt.type() == BSONType::String;
+}
+
+// TODO SERVER-23172: Update this to convert strings inside nested objects or arrays to their
+// corresponding comparison keys.
+void CollationIndexKey::collationAwareIndexKeyAppend(BSONElement elt,
+                                                     CollatorInterface* collator,
+                                                     BSONObjBuilder* out) {
+    if (shouldUseCollationIndexKey(elt, collator)) {
+        auto comparisonKey = collator->getComparisonKey(elt.valueStringData());
+        out->append("", comparisonKey.getKeyData());
+    } else {
+        out->appendAs(elt, "");
+    }
+}
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/collation/collation_index_key.h b/src/mongo/db/query/collation/collation_index_key.h
new file mode 100644
index 00000000000..480ab464934
--- /dev/null
+++ b/src/mongo/db/query/collation/collation_index_key.h
@@ -0,0 +1,57 @@
+/**
+ *    Copyright (C) 2016 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    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
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    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 GNU Affero General 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.
+ */
+
+#pragma once
+
+namespace mongo {
+
+class BSONElement;
+class BSONObjBuilder;
+class CollatorInterface;
+
+/**
+ * Provides functionality related to the mapping of user data to collator-generated comparison keys
+ * in index keys.
+ */
+class CollationIndexKey {
+public:
+    /**
+     * Returns true if the index key for 'elt' should be a comparison key generated by 'collator'.
+     */
+    static bool shouldUseCollationIndexKey(BSONElement elt, CollatorInterface* collator);
+
+    /**
+     * Appends 'elt' to 'out' with an empty field name, converting strings to comparison keys
+     * generated by 'collator' if necessary.
+     */
+    static void collationAwareIndexKeyAppend(BSONElement elt,
+                                             CollatorInterface* collator,
+                                             BSONObjBuilder* out);
+};
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/collation/collation_index_key_test.cpp b/src/mongo/db/query/collation/collation_index_key_test.cpp
new file mode 100644
index 00000000000..773eda2b858
--- /dev/null
+++ b/src/mongo/db/query/collation/collation_index_key_test.cpp
@@ -0,0 +1,102 @@
+/**
+ *    Copyright (C) 2016 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    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
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    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 GNU Affero General 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/query/collation/collation_index_key.h"
+
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/query/collation/collator_interface_mock.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+using namespace mongo;
+
+TEST(CollationIndexKeyTest, ShouldUseCollationKeyFalseWithNullCollator) {
+    BSONObj obj = BSON("foo"
+                       << "string");
+    ASSERT_FALSE(CollationIndexKey::shouldUseCollationIndexKey(obj.firstElement(), nullptr));
+}
+
+TEST(CollationIndexKeyTest, ShouldUseCollationKeyFalseWithNonStringElement) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    BSONObj obj = BSON("foo" << BSON("bar"
+                                     << "string"));
+    ASSERT_FALSE(CollationIndexKey::shouldUseCollationIndexKey(obj.firstElement(), &collator));
+}
+
+TEST(CollationIndexKeyTest, ShouldUseCollationKeyTrueWithStringElement) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    BSONObj obj = BSON("foo"
+                       << "string");
+    ASSERT_TRUE(CollationIndexKey::shouldUseCollationIndexKey(obj.firstElement(), &collator));
+}
+
+TEST(CollationIndexKeyTest, CollationAwareAppendReversesStringWithReverseMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    BSONObj dataObj = BSON("foo"
+                           << "string");
+    BSONObjBuilder out;
+    CollationIndexKey::collationAwareIndexKeyAppend(dataObj.firstElement(), &collator, &out);
+    ASSERT_EQ(out.obj(),
+              BSON(""
+                   << "gnirts"));
+}
+
+TEST(CollationIndexKeyTest, CollationAwareAppendCorrectlySerializesEmptyComparisonKey) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    BSONObjBuilder builder;
+    builder.append("foo", StringData());
+    BSONObj dataObj = builder.obj();
+
+    BSONObjBuilder expectedBuilder;
+    expectedBuilder.append("", StringData());
+    BSONObj expectedObj = expectedBuilder.obj();
+
+    BSONObjBuilder out;
+    CollationIndexKey::collationAwareIndexKeyAppend(dataObj.firstElement(), &collator, &out);
+    ASSERT_EQ(out.obj(), expectedObj);
+}
+
+TEST(CollationIndexKeyTest, CollationAwareAppendCorrectlySerializesWithEmbeddedNullByte) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    BSONObjBuilder builder;
+    builder.append("foo", StringData("a\0b", StringData::LiteralTag()));
+    BSONObj dataObj = builder.obj();
+
+    BSONObjBuilder expectedBuilder;
+    expectedBuilder.append("", StringData("b\0a", StringData::LiteralTag()));
+    BSONObj expectedObj = expectedBuilder.obj();
+
+    BSONObjBuilder out;
+    CollationIndexKey::collationAwareIndexKeyAppend(dataObj.firstElement(), &collator, &out);
+    ASSERT_EQ(out.obj(), expectedObj);
+}
+
+}  // namespace
diff --git a/src/mongo/db/query/collation/collation_serializer.cpp b/src/mongo/db/query/collation/collation_serializer.cpp
index a14e0d34ca6..6c49ef141ec 100644
--- a/src/mongo/db/query/collation/collation_serializer.cpp
+++ b/src/mongo/db/query/collation/collation_serializer.cpp
@@ -86,13 +86,4 @@ BSONObj CollationSerializer::specToBSON(const CollationSpec& spec) {
     return builder.obj();
 }
 
-void CollationSerializer::appendCollationKey(StringData fieldName,
-                                             const CollatorInterface::ComparisonKey& key,
-                                             BSONObjBuilder* bob) {
-    const auto keyData = key.getKeyData();
-    // 'keyData' should not contain a trailing null byte, but the BSONObjBuilder will add one after
-    // appending the string.
-    bob->append(fieldName, keyData);
-}
-
 }  // namespace mongo
diff --git a/src/mongo/db/query/collation/collation_serializer.h b/src/mongo/db/query/collation/collation_serializer.h
index 4a273abd451..ecf381ef7c1 100644
--- a/src/mongo/db/query/collation/collation_serializer.h
+++ b/src/mongo/db/query/collation/collation_serializer.h
@@ -33,8 +33,6 @@
 namespace mongo {
 
 class BSONObj;
-class BSONObjBuilder;
-class StringData;
 
 struct CollationSpec;
 
@@ -50,13 +48,6 @@ public:
      * The resulting BSONObj is owned by the caller.
      */
     static BSONObj specToBSON(const CollationSpec& spec);
-
-    /**
-     * Appends 'key' to 'bob' as a BSONElement of BSONType string with field name 'fieldName'.
-     */
-    static void appendCollationKey(StringData fieldName,
-                                   const CollatorInterface::ComparisonKey& key,
-                                   BSONObjBuilder* bob);
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/query/collation/collation_serializer_test.cpp b/src/mongo/db/query/collation/collation_serializer_test.cpp
index 03bd1c5a04c..60e1e63d9f6 100644
--- a/src/mongo/db/query/collation/collation_serializer_test.cpp
+++ b/src/mongo/db/query/collation/collation_serializer_test.cpp
@@ -199,39 +199,4 @@ TEST(CollationSerializerTest, ToBSONCorrectlySerializesMaxVariableSpace) {
     ASSERT_EQ(expectedObj, CollationSerializer::specToBSON(collationSpec));
 }
 
-TEST(CollationSerializerTest, CorrectlySerializeASCIIComparisonKey) {
-    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
-    auto comparisonKey = collator.getComparisonKey("abc");
-
-    BSONObjBuilder builder;
-    CollationSerializer::appendCollationKey("foo", comparisonKey, &builder);
-    ASSERT_EQ(builder.obj(),
-              BSON("foo"
-                   << "cba"));
-}
-
-TEST(CollationSerializerTest, CorrectlySerializeEmptyComparisonKey) {
-    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
-    auto comparisonKey = collator.getComparisonKey(StringData());
-
-    BSONObjBuilder builder;
-    CollationSerializer::appendCollationKey("foo", comparisonKey, &builder);
-    ASSERT_EQ(builder.obj(),
-              BSON("foo"
-                   << ""));
-}
-
-TEST(CollationSerializerTest, CorrectlySerializeComparisonKeyWithEmbeddedNullByte) {
-    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
-    auto comparisonKey = collator.getComparisonKey(StringData("a\0b", StringData::LiteralTag()));
-
-    BSONObjBuilder builder;
-    CollationSerializer::appendCollationKey("foo", comparisonKey, &builder);
-    BSONObj resultingObj = builder.obj();
-
-    BSONObjBuilder expectedBuilder;
-    expectedBuilder.append("foo", StringData("b\0a", StringData::LiteralTag()));
-    ASSERT_EQ(resultingObj, expectedBuilder.obj());
-}
-
 }  // namespace
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index 364f9577adb..3f89d5dd605 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -35,24 +35,58 @@
 
 #include "mongo/base/string_data.h"
 #include "mongo/db/geo/geoconstants.h"
+#include "mongo/db/geo/s2.h"
 #include "mongo/db/index/expression_params.h"
 #include "mongo/db/index/s2_common.h"
 #include "mongo/db/matcher/expression_geo.h"
+#include "mongo/db/query/collation/collation_index_key.h"
+#include "mongo/db/query/collation/collator_interface.h"
 #include "mongo/db/query/expression_index.h"
 #include "mongo/db/query/expression_index_knobs.h"
 #include "mongo/db/query/indexability.h"
 #include "mongo/db/query/query_knobs.h"
 #include "mongo/util/log.h"
 #include "mongo/util/mongoutils/str.h"
-#include "mongo/db/geo/s2.h"
 #include "third_party/s2/s2cell.h"
 #include "third_party/s2/s2regioncoverer.h"
 
 namespace mongo {
 
+namespace {
+
+// Tightness rules are shared for $lt, $lte, $gt, $gte.
+IndexBoundsBuilder::BoundsTightness getInequalityPredicateTightness(const BSONElement& dataElt,
+                                                                    const IndexEntry& index) {
+    // TODO SERVER-23093: Right now we consider a string comparison in the presence of a
+    // collator to be inexact fetch, since such queries cannot be covered. Although it is
+    // necessary to fetch the keyed documents, it is not necessary to reapply the filter.
+    if (CollationIndexKey::shouldUseCollationIndexKey(dataElt, index.collator)) {
+        return IndexBoundsBuilder::INEXACT_FETCH;
+    }
+
+    if (dataElt.isSimpleType() || dataElt.type() == BSONType::BinData) {
+        return IndexBoundsBuilder::EXACT;
+    }
+
+    return IndexBoundsBuilder::INEXACT_FETCH;
+}
+
+}  // namespace
+
 string IndexBoundsBuilder::simpleRegex(const char* regex,
                                        const char* flags,
+                                       const IndexEntry& index,
                                        BoundsTightness* tightnessOut) {
+    if (index.collator) {
+        // Bounds building for simple regular expressions assumes that the index is in ASCII order,
+        // which is not necessarily true for an index with a collator.  Therefore, a regex can never
+        // use tight bounds if the index has a non-null collator. In this case, the regex must be
+        // applied to the fetched document rather than the index key, so the tightness is
+        // INEXACT_FETCH.
+        *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
+        return "";
+    }
+
     string r = "";
     *tightnessOut = IndexBoundsBuilder::INEXACT_COVERED;
 
@@ -292,15 +326,24 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         translate(child, elt, index, oilOut, tightnessOut);
         oilOut->complement();
 
-        // If the index is multikey, it doesn't matter what the tightness
-        // of the child is, we must return INEXACT_FETCH. Consider a multikey
-        // index on 'a' with document {a: [1, 2, 3]} and query {a: {$ne: 3}}.
-        // If we treated the bounds [MinKey, 3), (3, MaxKey] as exact, then
-        // we would erroneously return the document!
-        if (index.multikey) {
+        // If the index is multikey, it doesn't matter what the tightness of the child is, we must
+        // return INEXACT_FETCH. Consider a multikey index on 'a' with document {a: [1, 2, 3]} and
+        // query {a: {$ne: 3}}.  If we treated the bounds [MinKey, 3), (3, MaxKey] as exact, then we
+        // would erroneously return the document!
+        //
+        // If the index has a collator, then complementing the bounds generally results in strings
+        // being in-bounds. Such index bounds cannot be used in a covered plan, since we should
+        // never return collator comparison keys to the user. As such, we must make the bounds
+        // INEXACT_FETCH in this case.
+        //
+        // TODO SERVER-23093: Although it is necessary to fetch the keyed documents, it is not
+        // necessary to reapply the filter.
+        if (index.multikey || index.collator) {
             *tightnessOut = INEXACT_FETCH;
         }
     } else if (MatchExpression::EXISTS == expr->matchType()) {
+        oilOut->intervals.push_back(allValues());
+
         // We only handle the {$exists:true} case, as {$exists:false}
         // will have been translated to {$not:{ $exists:true }}.
         //
@@ -319,8 +362,13 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         // {a:{ $exists:false }} - sparse indexes cannot be used at all.
         //
         // Noted in SERVER-12869, in case this ever changes some day.
-        if (index.sparse) {
-            oilOut->intervals.push_back(allValues());
+        //
+        // Bounds are always INEXACT_FETCH if there is a collator on the index, since the bounds
+        // include collator-generated sort keys that shouldn't be returned to the user.
+        //
+        // TODO SERVER-23093: Although it is necessary to fetch the keyed documents when there is a
+        // collator, it is not necessary to reapply the filter.
+        if (index.sparse && !index.collator) {
             // A sparse, compound index on { a:1, b:1 } will include entries
             // for all of the following documents:
             //    { a:1 }, { b:1 }, { a:1, b:1 }
@@ -331,12 +379,11 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
                 *tightnessOut = IndexBoundsBuilder::EXACT;
             }
         } else {
-            oilOut->intervals.push_back(allValues());
             *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
         }
     } else if (MatchExpression::EQ == expr->matchType()) {
         const EqualityMatchExpression* node = static_cast<const EqualityMatchExpression*>(expr);
-        translateEquality(node->getData(), isHashed, oilOut, tightnessOut);
+        translateEquality(node->getData(), index, isHashed, oilOut, tightnessOut);
     } else if (MatchExpression::LTE == expr->matchType()) {
         const LTEMatchExpression* node = static_cast<const LTEMatchExpression*>(expr);
         BSONElement dataElt = node->getData();
@@ -344,7 +391,8 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         // Everything is <= MaxKey.
         if (MaxKey == dataElt.type()) {
             oilOut->intervals.push_back(allValues());
-            *tightnessOut = IndexBoundsBuilder::EXACT;
+            *tightnessOut =
+                index.collator ? IndexBoundsBuilder::INEXACT_FETCH : IndexBoundsBuilder::EXACT;
             return;
         }
 
@@ -363,16 +411,12 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         } else {
             bob.appendMinForType("", dataElt.type());
         }
-        bob.appendAs(dataElt, "");
+        CollationIndexKey::collationAwareIndexKeyAppend(dataElt, index.collator, &bob);
         BSONObj dataObj = bob.obj();
         verify(dataObj.isOwned());
         oilOut->intervals.push_back(makeRangeInterval(dataObj, typeMatch(dataObj), true));
 
-        if (dataElt.isSimpleType() || dataElt.type() == BSONType::BinData) {
-            *tightnessOut = IndexBoundsBuilder::EXACT;
-        } else {
-            *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
-        }
+        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
     } else if (MatchExpression::LT == expr->matchType()) {
         const LTMatchExpression* node = static_cast<const LTMatchExpression*>(expr);
         BSONElement dataElt = node->getData();
@@ -380,7 +424,8 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         // Everything is <= MaxKey.
         if (MaxKey == dataElt.type()) {
             oilOut->intervals.push_back(allValues());
-            *tightnessOut = IndexBoundsBuilder::EXACT;
+            *tightnessOut =
+                index.collator ? IndexBoundsBuilder::INEXACT_FETCH : IndexBoundsBuilder::EXACT;
             return;
         }
 
@@ -397,7 +442,7 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         } else {
             bob.appendMinForType("", dataElt.type());
         }
-        bob.appendAs(dataElt, "");
+        CollationIndexKey::collationAwareIndexKeyAppend(dataElt, index.collator, &bob);
         BSONObj dataObj = bob.obj();
         verify(dataObj.isOwned());
         Interval interval = makeRangeInterval(dataObj, typeMatch(dataObj), false);
@@ -408,11 +453,7 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
             oilOut->intervals.push_back(interval);
         }
 
-        if (dataElt.isSimpleType() || dataElt.type() == BSONType::BinData) {
-            *tightnessOut = IndexBoundsBuilder::EXACT;
-        } else {
-            *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
-        }
+        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
     } else if (MatchExpression::GT == expr->matchType()) {
         const GTMatchExpression* node = static_cast<const GTMatchExpression*>(expr);
         BSONElement dataElt = node->getData();
@@ -420,7 +461,8 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         // Everything is > MinKey.
         if (MinKey == dataElt.type()) {
             oilOut->intervals.push_back(allValues());
-            *tightnessOut = IndexBoundsBuilder::EXACT;
+            *tightnessOut =
+                index.collator ? IndexBoundsBuilder::INEXACT_FETCH : IndexBoundsBuilder::EXACT;
             return;
         }
 
@@ -431,7 +473,7 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         }
 
         BSONObjBuilder bob;
-        bob.appendAs(node->getData(), "");
+        CollationIndexKey::collationAwareIndexKeyAppend(dataElt, index.collator, &bob);
         if (dataElt.isNumber()) {
             bob.appendNumber("", std::numeric_limits<double>::infinity());
         } else {
@@ -447,11 +489,7 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
             oilOut->intervals.push_back(interval);
         }
 
-        if (dataElt.isSimpleType() || dataElt.type() == BSONType::BinData) {
-            *tightnessOut = IndexBoundsBuilder::EXACT;
-        } else {
-            *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
-        }
+        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
     } else if (MatchExpression::GTE == expr->matchType()) {
         const GTEMatchExpression* node = static_cast<const GTEMatchExpression*>(expr);
         BSONElement dataElt = node->getData();
@@ -459,7 +497,8 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         // Everything is >= MinKey.
         if (MinKey == dataElt.type()) {
             oilOut->intervals.push_back(allValues());
-            *tightnessOut = IndexBoundsBuilder::EXACT;
+            *tightnessOut =
+                index.collator ? IndexBoundsBuilder::INEXACT_FETCH : IndexBoundsBuilder::EXACT;
             return;
         }
 
@@ -472,7 +511,7 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         }
 
         BSONObjBuilder bob;
-        bob.appendAs(dataElt, "");
+        CollationIndexKey::collationAwareIndexKeyAppend(dataElt, index.collator, &bob);
         if (dataElt.isNumber()) {
             bob.appendNumber("", std::numeric_limits<double>::infinity());
         } else {
@@ -482,14 +521,11 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         verify(dataObj.isOwned());
 
         oilOut->intervals.push_back(makeRangeInterval(dataObj, true, typeMatch(dataObj)));
-        if (dataElt.isSimpleType() || dataElt.type() == BSONType::BinData) {
-            *tightnessOut = IndexBoundsBuilder::EXACT;
-        } else {
-            *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
-        }
+
+        *tightnessOut = getInequalityPredicateTightness(dataElt, index);
     } else if (MatchExpression::REGEX == expr->matchType()) {
         const RegexMatchExpression* rme = static_cast<const RegexMatchExpression*>(expr);
-        translateRegex(rme, oilOut, tightnessOut);
+        translateRegex(rme, index, oilOut, tightnessOut);
     } else if (MatchExpression::MOD == expr->matchType()) {
         BSONObjBuilder bob;
         bob.appendMinForType("", NumberDouble);
@@ -524,14 +560,14 @@ void IndexBoundsBuilder::translate(const MatchExpression* expr,
         IndexBoundsBuilder::BoundsTightness tightness;
         for (BSONElementSet::iterator it = afr.equalities().begin(); it != afr.equalities().end();
              ++it) {
-            translateEquality(*it, isHashed, oilOut, &tightness);
+            translateEquality(*it, index, isHashed, oilOut, &tightness);
             if (tightness != IndexBoundsBuilder::EXACT) {
                 *tightnessOut = tightness;
             }
         }
 
         for (size_t i = 0; i < afr.numRegexes(); ++i) {
-            translateRegex(afr.regex(i), oilOut, &tightness);
+            translateRegex(afr.regex(i), index, oilOut, &tightness);
             if (tightness != IndexBoundsBuilder::EXACT) {
                 *tightnessOut = tightness;
             }
@@ -733,9 +769,9 @@ Interval IndexBoundsBuilder::makePointInterval(double d) {
 }
 
 // static
-BSONObj IndexBoundsBuilder::objFromElement(const BSONElement& elt) {
+BSONObj IndexBoundsBuilder::objFromElement(const BSONElement& elt, CollatorInterface* collator) {
     BSONObjBuilder bob;
-    bob.appendAs(elt, "");
+    CollationIndexKey::collationAwareIndexKeyAppend(elt, collator, &bob);
     return bob.obj();
 }
 
@@ -752,10 +788,11 @@ void IndexBoundsBuilder::reverseInterval(Interval* ival) {
 
 // static
 void IndexBoundsBuilder::translateRegex(const RegexMatchExpression* rme,
+                                        const IndexEntry& index,
                                         OrderedIntervalList* oilOut,
                                         BoundsTightness* tightnessOut) {
     const string start =
-        simpleRegex(rme->getString().c_str(), rme->getFlags().c_str(), tightnessOut);
+        simpleRegex(rme->getString().c_str(), rme->getFlags().c_str(), index, tightnessOut);
 
     // Note that 'tightnessOut' is set by simpleRegex above.
     if (!start.empty()) {
@@ -779,22 +816,29 @@ void IndexBoundsBuilder::translateRegex(const RegexMatchExpression* rme,
 
 // static
 void IndexBoundsBuilder::translateEquality(const BSONElement& data,
+                                           const IndexEntry& index,
                                            bool isHashed,
                                            OrderedIntervalList* oil,
                                            BoundsTightness* tightnessOut) {
     // We have to copy the data out of the parse tree and stuff it into the index
     // bounds.  BSONValue will be useful here.
     if (Array != data.type()) {
-        BSONObj dataObj;
+        BSONObj dataObj = objFromElement(data, index.collator);
         if (isHashed) {
-            dataObj = ExpressionMapping::hash(data);
-        } else {
-            dataObj = objFromElement(data);
+            dataObj = ExpressionMapping::hash(dataObj.firstElement());
         }
 
         verify(dataObj.isOwned());
         oil->intervals.push_back(makePointInterval(dataObj));
 
+        // TODO SERVER-23093: Right now we consider a string comparison in the presence of a
+        // collator to be inexact fetch, since such queries cannot be covered. Although it is
+        // necessary to fetch the keyed documents, it is not necessary to reapply the filter.
+        if (CollationIndexKey::shouldUseCollationIndexKey(data, index.collator)) {
+            *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
+            return;
+        }
+
         if (dataObj.firstElement().isNull() || isHashed) {
             *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
         } else {
@@ -823,7 +867,7 @@ void IndexBoundsBuilder::translateEquality(const BSONElement& data,
     // {a: [1, 2, 3]} will match documents like {a: [[1, 2, 3], 4, 5]}.
 
     // Case 3.
-    oil->intervals.push_back(makePointInterval(objFromElement(data)));
+    oil->intervals.push_back(makePointInterval(objFromElement(data, index.collator)));
 
     if (data.Obj().isEmpty()) {
         // Case 2.
@@ -833,7 +877,7 @@ void IndexBoundsBuilder::translateEquality(const BSONElement& data,
     } else {
         // Case 1.
         BSONElement firstEl = data.Obj().firstElement();
-        oil->intervals.push_back(makePointInterval(objFromElement(firstEl)));
+        oil->intervals.push_back(makePointInterval(objFromElement(firstEl, index.collator)));
     }
 
     std::sort(oil->intervals.begin(), oil->intervals.end(), IntervalComparison);
diff --git a/src/mongo/db/query/index_bounds_builder.h b/src/mongo/db/query/index_bounds_builder.h
index 785f78feb6d..2a1adbd1241 100644
--- a/src/mongo/db/query/index_bounds_builder.h
+++ b/src/mongo/db/query/index_bounds_builder.h
@@ -36,6 +36,8 @@
 
 namespace mongo {
 
+class CollatorInterface;
+
 /**
  * Translates expressions over fields into bounds on an index.
  */
@@ -125,10 +127,11 @@ public:
     static Interval makePointInterval(double d);
 
     /**
-     * Since we have no BSONValue we must make an object that's a copy of a piece of another
-     * object.
+     * Wraps 'elt' in a BSONObj with an empty field name and returns the result. If 'elt' is a
+     * string, and 'collator' is non-null, the result contains the collator-generated comparison key
+     * rather than the original string.
      */
-    static BSONObj objFromElement(const BSONElement& elt);
+    static BSONObj objFromElement(const BSONElement& elt, CollatorInterface* collator);
 
     /**
      * Swap start/end in the provided interval.
@@ -136,16 +139,14 @@ public:
     static void reverseInterval(Interval* ival);
 
     /**
-     * Copied almost verbatim from db/queryutil.cpp.
-     *
-     *  returns a std::string that when used as a matcher, would match a super set of regex()
+     * Returns a std::string that when used as a matcher, would match a superset of regex. Used to
+     * optimize queries in some simple regex cases that start with '^'.
      *
-     *  returns "" for complex regular expressions
-     *
-     *  used to optimize queries in some simple regex cases that start with '^'
+     * Returns "" for complex regular expressions that cannot use tight index bounds.
      */
     static std::string simpleRegex(const char* regex,
                                    const char* flags,
+                                   const IndexEntry& index,
                                    BoundsTightness* tightnessOut);
 
     /**
@@ -154,10 +155,12 @@ public:
     static Interval allValues();
 
     static void translateRegex(const RegexMatchExpression* rme,
+                               const IndexEntry& index,
                                OrderedIntervalList* oil,
                                BoundsTightness* tightnessOut);
 
     static void translateEquality(const BSONElement& data,
+                                  const IndexEntry& index,
                                   bool isHashed,
                                   OrderedIntervalList* oil,
                                   BoundsTightness* tightnessOut);
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index 43a318523de..d29500d16cd 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -26,17 +26,18 @@
  *    it in the license file.
  */
 
-/**
- * This file contains tests for mongo/db/query/index_bounds_builder.cpp
- */
+#include "mongo/platform/basic.h"
 
 #include "mongo/db/query/index_bounds_builder.h"
 
 #include <limits>
 #include <memory>
+
 #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/expression_index.h"
 #include "mongo/unittest/unittest.h"
 
 using namespace mongo;
@@ -928,151 +929,183 @@ TEST(IndexBoundsBuilderTest, TranslateMod) {
 //
 
 TEST(SimpleRegexTest, RootedLine) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^foo", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^foo", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "foo");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedString) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("\\Afoo", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("\\Afoo", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "foo");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedOptionalFirstChar) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^f?oo", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^f?oo", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 TEST(SimpleRegexTest, RootedOptionalSecondChar) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^fz?oo", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^fz?oo", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "f");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 TEST(SimpleRegexTest, RootedMultiline) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^foo", "m", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^foo", "m", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 TEST(SimpleRegexTest, RootedStringMultiline) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("\\Afoo", "m", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("\\Afoo", "m", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "foo");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedCaseInsensitiveMulti) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("\\Afoo", "mi", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("\\Afoo", "mi", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 TEST(SimpleRegexTest, RootedComplex) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix =
-        IndexBoundsBuilder::simpleRegex("\\Af \t\vo\n\ro  \\ \\# #comment", "mx", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex(
+        "\\Af \t\vo\n\ro  \\ \\# #comment", "mx", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "foo #");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 TEST(SimpleRegexTest, RootedLiteral) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf\\E", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf\\E", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "asdf");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedLiteralWithExtra) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf\\E.*", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf\\E.*", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "asdf");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 TEST(SimpleRegexTest, RootedLiteralNoEnd) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "asdf");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedLiteralBackslash) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf\\\\E", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qasdf\\\\E", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "asdf\\");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedLiteralDotStar) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qas.*df\\E", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qas.*df\\E", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "as.*df");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedLiteralNestedEscape) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qas\\Q[df\\E", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qas\\Q[df\\E", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "as\\Q[df");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(SimpleRegexTest, RootedLiteralNestedEscapeEnd) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^\\Qas\\E\\\\E\\Q$df\\E", "", &tightness);
+    string prefix =
+        IndexBoundsBuilder::simpleRegex("^\\Qas\\E\\\\E\\Q$df\\E", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "as\\E$df");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 // A regular expression with the "|" character is not considered simple. See SERVER-15235.
 TEST(SimpleRegexTest, PipeCharacterDisallowed) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^(a(a|$)|b", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^(a(a|$)|b", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 TEST(SimpleRegexTest, PipeCharacterDisallowed2) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^(a(a|$)|^b", "", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^(a(a|$)|^b", "", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 // SERVER-9035
 TEST(SimpleRegexTest, RootedSingleLineMode) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("^foo", "s", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("^foo", "s", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "foo");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 // SERVER-9035
 TEST(SimpleRegexTest, NonRootedSingleLineMode) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix = IndexBoundsBuilder::simpleRegex("foo", "s", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex("foo", "s", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
 // SERVER-9035
 TEST(SimpleRegexTest, RootedComplexSingleLineMode) {
+    IndexEntry testIndex = IndexEntry(BSONObj());
     IndexBoundsBuilder::BoundsTightness tightness;
-    string prefix =
-        IndexBoundsBuilder::simpleRegex("\\Af \t\vo\n\ro  \\ \\# #comment", "msx", &tightness);
+    string prefix = IndexBoundsBuilder::simpleRegex(
+        "\\Af \t\vo\n\ro  \\ \\# #comment", "msx", testIndex, &tightness);
     ASSERT_EQUALS(prefix, "foo #");
     ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_COVERED);
 }
 
+TEST(SimpleRegexTest, RootedRegexCantBeIndexedTightlyIfIndexHasCollation) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    IndexBoundsBuilder::BoundsTightness tightness;
+    string prefix = IndexBoundsBuilder::simpleRegex("^foo", "", testIndex, &tightness);
+    ASSERT_EQUALS(prefix, "");
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
 //
 // Regex bounds
 //
@@ -1484,4 +1517,627 @@ TEST(IndexBoundsBuilderTest, DoubleTypeBounds) {
                   oil.intervals[0].compare(Interval(expectedInterval, true, true)));
     ASSERT(tightness == IndexBoundsBuilder::INEXACT_FETCH);
 }
+
+//
+// Collation-related tests.
+//
+
+TEST(IndexBoundsBuilderTest, TranslateEqualityToStringWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = BSON("a"
+                       << "foo");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': 'oof', '': 'oof'}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateEqualityToNonStringWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = BSON("a" << 3);
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': 3, '': 3}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateNotEqualToStringWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = BSON("a" << BSON("$ne"
+                                   << "bar"));
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    // Bounds should be [MinKey, "rab"), ("rab", MaxKey].
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 2U);
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+
+    {
+        BSONObjBuilder bob;
+        bob.appendMinKey("");
+        bob.append("", "rab");
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                      oil.intervals[0].compare(Interval(bob.obj(), true, false)));
+    }
+
+    {
+        BSONObjBuilder bob;
+        bob.append("", "rab");
+        bob.appendMaxKey("");
+        ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                      oil.intervals[1].compare(Interval(bob.obj(), false, true)));
+    }
+}
+
+TEST(IndexBoundsBuilderTest, TranslateEqualToStringElemMatchValueWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$elemMatch: {$eq: 'baz'}}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': 'zab', '': 'zab'}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateLTEToStringWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$lte: 'foo'}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': '', '': 'oof'}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateLTEToNumberWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$lte: 3}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': -Infinity, '': 3}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateLTStringWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$lt: 'foo'}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': '', '': 'oof'}"), true, false)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateLTNumberWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$lt: 3}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': -Infinity, '': 3}"), true, false)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateGTStringWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$gt: 'foo'}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': 'oof', '': {}}"), false, false)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateGTNumberWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$gt: 3}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': 3, '': Infinity}"), false, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateGTEToStringWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$gte: 'foo'}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': 'oof', '': {}}"), true, false)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, TranslateGTEToNumberWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$gte: 3}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': 3, '': Infinity}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
+}
+
+TEST(IndexBoundsBuilderTest, SimplePrefixRegexWithMockCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: /^foo/}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.intervals.size(), 2U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': '', '': {}}"), true, false)));
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[1].compare(Interval(fromjson("{'': /^foo/, '': /^foo/}"), true, true)));
+    ASSERT(tightness == IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, NotWithMockCollatorIsInexactFetch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$ne:  3}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.intervals.size(), 2U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(minKeyIntObj(3), true, false)));
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[1].compare(Interval(maxKeyIntObj(3), false, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, ExistsTrueWithMockCollatorAndSparseIsInexactFetch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+    testIndex.sparse = true;
+
+    BSONObj obj = fromjson("{a: {$exists: true}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(IndexBoundsBuilder::allValues()));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, ExistsFalseWithMockCollatorIsInexactFetch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$exists: false}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': null, '': null}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, TypeStringIsInexactFetch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$type: 'string'}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': '', '': {}}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, InWithStringAndCollatorIsInexactFetch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$in: ['foo']}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[0].compare(Interval(fromjson("{'': 'oof', '': 'oof'}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, InWithNumberAndStringAndCollatorIsInexactFetch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$in: [2, 'foo']}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 2U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': 2, '': 2}"), true, true)));
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[1].compare(Interval(fromjson("{'': 'oof', '': 'oof'}"), true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, InWithRegexAndCollatorIsInexactFetch) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$in: [/^foo/]}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.intervals.size(), 2U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': '', '': {}}"), true, false)));
+    ASSERT_EQUALS(
+        Interval::INTERVAL_EQUALS,
+        oil.intervals[1].compare(Interval(fromjson("{'': /^foo/, '': /^foo/}"), true, true)));
+    ASSERT(tightness == IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, InWithNumberAndCollatorIsExact) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$in: [2]}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(fromjson("{'': 2, '': 2}"), true, true)));
+    ASSERT(tightness == IndexBoundsBuilder::EXACT);
+}
+
+TEST(IndexBoundsBuilderTest, LTEMaxKeyWithCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$lte: {$maxKey: 1}}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(IndexBoundsBuilder::allValues()));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, LTMaxKeyWithCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$lt: {$maxKey: 1}}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(IndexBoundsBuilder::allValues()));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, GTEMinKeyWithCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$gte: {$minKey: 1}}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(IndexBoundsBuilder::allValues()));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, GTMinKeyWithCollator) {
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(BSONObj());
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$gt: {$minKey: 1}}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+    BSONElement elt = obj.firstElement();
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(IndexBoundsBuilder::allValues()));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, StringEqualityAgainstHashedIndexWithCollatorUsesHashOfCollationKey) {
+    BSONObj keyPattern = fromjson("{a: 'hashed'}");
+    BSONElement elt = keyPattern.firstElement();
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(keyPattern);
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: 'foo'}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    BSONObj expectedCollationKey = BSON(""
+                                        << "oof");
+    BSONObj expectedHash = ExpressionMapping::hash(expectedCollationKey.firstElement());
+    BSONObjBuilder intervalBuilder;
+    intervalBuilder.append("", expectedHash.firstElement().numberLong());
+    intervalBuilder.append("", expectedHash.firstElement().numberLong());
+    BSONObj intervalObj = intervalBuilder.obj();
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(intervalObj, true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, EqualityToNumberAgainstHashedIndexWithCollatorUsesHash) {
+    BSONObj keyPattern = fromjson("{a: 'hashed'}");
+    BSONElement elt = keyPattern.firstElement();
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(keyPattern);
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: 3}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    BSONObj expectedHash = ExpressionMapping::hash(obj.firstElement());
+    BSONObjBuilder intervalBuilder;
+    intervalBuilder.append("", expectedHash.firstElement().numberLong());
+    intervalBuilder.append("", expectedHash.firstElement().numberLong());
+    BSONObj intervalObj = intervalBuilder.obj();
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(intervalObj, true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
+TEST(IndexBoundsBuilderTest, InWithStringAgainstHashedIndexWithCollatorUsesHashOfCollationKey) {
+    BSONObj keyPattern = fromjson("{a: 'hashed'}");
+    BSONElement elt = keyPattern.firstElement();
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    IndexEntry testIndex = IndexEntry(keyPattern);
+    testIndex.collator = &collator;
+
+    BSONObj obj = fromjson("{a: {$in: ['foo']}}");
+    unique_ptr<MatchExpression> expr(parseMatchExpression(obj));
+
+    OrderedIntervalList oil;
+    IndexBoundsBuilder::BoundsTightness tightness;
+    IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness);
+
+    BSONObj expectedCollationKey = BSON(""
+                                        << "oof");
+    BSONObj expectedHash = ExpressionMapping::hash(expectedCollationKey.firstElement());
+    BSONObjBuilder intervalBuilder;
+    intervalBuilder.append("", expectedHash.firstElement().numberLong());
+    intervalBuilder.append("", expectedHash.firstElement().numberLong());
+    BSONObj intervalObj = intervalBuilder.obj();
+
+    ASSERT_EQUALS(oil.name, "a");
+    ASSERT_EQUALS(oil.intervals.size(), 1U);
+    ASSERT_EQUALS(Interval::INTERVAL_EQUALS,
+                  oil.intervals[0].compare(Interval(intervalObj, true, true)));
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+}
+
 }  // namespace
diff --git a/src/mongo/db/query/index_entry.h b/src/mongo/db/query/index_entry.h
index 7b336515954..8af72ce93db 100644
--- a/src/mongo/db/query/index_entry.h
+++ b/src/mongo/db/query/index_entry.h
@@ -125,7 +125,7 @@ struct IndexEntry {
 
     // Null if this index orders strings according to the simple binary compare. If non-null,
     // represents the collator used to generate index keys for indexed strings.
-    const CollatorInterface* collator = nullptr;
+    CollatorInterface* collator = nullptr;
 };
 
 }  // namespace mongo