SERVER-26672 Generate exact bounds for timestamps in index bounds builder

This commit also replaces BSONElement::isSimpleType with
Indexability::isExactBoundsGenerating, since the isSimpleType construct
was only used within the query system.

8 files changed, 186 insertions, 27 deletions

diff --git a/jstests/core/constructors.js b/jstests/core/constructors.js
index 38f00dc58ed..9e2cd26bbe8 100644
--- a/jstests/core/constructors.js
+++ b/jstests/core/constructors.js
@@ -166,6 +166,12 @@ var timestampConstructors = {
         'Timestamp(true,true)',
         'Timestamp(true,0)',
         'Timestamp(0,true)',
+        'Timestamp(Math.pow(2,32),Math.pow(2,32))',
+        'Timestamp(0,Math.pow(2,32))',
+        'Timestamp(Math.pow(2,32),0)',
+        'Timestamp(-1,-1)',
+        'Timestamp(-1,0)',
+        'Timestamp(0,-1)'
     ]
 };
 
diff --git a/jstests/core/index_bounds_timestamp.js b/jstests/core/index_bounds_timestamp.js
new file mode 100644
index 00000000000..8acb842869a
--- /dev/null
+++ b/jstests/core/index_bounds_timestamp.js
@@ -0,0 +1,153 @@
+// Index bounds generation tests for Timestamp values.
+// This file tests whether index bounds for timestamps are generated properly in terms of
+// inclusiveness and exactness.
+
+(function() {
+    "use strict";
+
+    load("jstests/libs/analyze_plan.js");
+
+    // Helper function to get the nCounted from the COUNT stage in an explain plan's executionStats.
+    function getCountFromExecutionStats(executionStats) {
+        let stages = getPlanStages(executionStats.executionStages, "COUNT");
+        assert.eq(1, stages.length, "executionStats should have 1 COUNT stage");
+        return stages[0].nCounted;
+    }
+
+    // Setup the test collection.
+    let coll = db.index_bounds_timestamp;
+    coll.drop();
+
+    // Create an index on the ts and _id fields.
+    assert.commandWorked(coll.createIndex({ts: 1, _id: 1}));
+
+    // Insert some test documents.
+    // NOTE: Inserting Timestamp() or Timestamp(0, 0) into a collection creates a Timestamp for the
+    // current time. Max Timestamp value is Timestamp(2^32 - 1, 2^32 - 1).
+    const documents = [
+        {_id: 0, ts: new Timestamp(0, 1)},
+        {_id: 1, ts: new Timestamp(0, Math.pow(2, 31))},
+        {_id: 2, ts: new Timestamp(0, Math.pow(2, 32) - 1)},
+        {_id: 3, ts: new Timestamp(1, 0)},
+        {_id: 4, ts: new Timestamp(Math.pow(2, 32) - 1, Math.pow(2, 32) - 1)}
+    ];
+    assert.writeOK(coll.insert(documents));
+
+    // Sanity check the timestamp bounds generation plan.
+    let plan;
+
+    // Check that count over (Timestamp(0, 0), Timestamp(2^32 - 1, 2^32 - 1)] is a covered query.
+    plan = coll.explain("executionStats").find({ts: {$gt: Timestamp(0, 0)}}).count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan), "ts $gt count should be a covered query");
+    assert.eq(5, getCountFromExecutionStats(plan.executionStats), "ts $gt count should be 5");
+
+    // Check that find over (Timestamp(0, 0), Timestamp(2^32 - 1, 2^32 - 1)] does not require a
+    // FETCH stage when the query is covered by an index.
+    plan =
+        coll.explain("executionStats").find({ts: {$gt: Timestamp(0, 0)}}, {ts: 1, _id: 0}).finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gt find with project should be a covered query");
+
+    // Check that count over [Timestamp(0, 0), Timestamp(2^32 - 1, 2^32 - 1)] is a covered query.
+    plan = coll.explain("executionStats").find({ts: {$gte: Timestamp(0, 0)}}).count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan), "ts $gte count should be a covered query");
+    assert.eq(5, getCountFromExecutionStats(plan.executionStats), "ts $gte count should be 5");
+
+    // Check that find over [Timestamp(0, 0), Timestamp(2^32 - 1, 2^32 - 1)] does not require a
+    // FETCH stage when the query is covered by an index.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gte: Timestamp(0, 0)}}, {ts: 1, _id: 0})
+               .finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gte find with project should be a covered query");
+
+    // Check that count over [Timestamp(0, 0), Timestamp(1, 0)) is a covered query.
+    plan = coll.explain("executionStats").find({ts: {$lt: Timestamp(1, 0)}}).count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan), "ts $lt count should be a covered query");
+    assert.eq(3, getCountFromExecutionStats(plan.executionStats), "ts $lt count should be 3");
+
+    // Check that find over [Timestamp(0, 0), Timestamp(1, 0)) does not require a FETCH stage when
+    // the query is covered by an index.
+    plan =
+        coll.explain("executionStats").find({ts: {$lt: Timestamp(1, 0)}}, {ts: 1, _id: 0}).finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $lt find with project should be a covered query");
+
+    // Check that count over [Timestamp(0, 0), Timestamp(1, 0)] is a covered query.
+    plan = coll.explain("executionStats").find({ts: {$lte: Timestamp(1, 0)}}).count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan), "ts $lte count should be a covered query");
+    assert.eq(4, getCountFromExecutionStats(plan.executionStats), "ts $lte count should be 4");
+
+    // Check that find over [Timestamp(0, 0), Timestamp(1, 0)] does not require a FETCH stage when
+    // the query is covered by an index.
+    plan = coll.explain("executionStats")
+               .find({ts: {$lte: Timestamp(1, 0)}}, {ts: 1, _id: 0})
+               .finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $lte find with project should be a covered query");
+
+    // Check that count over (Timestamp(0, 1), Timestamp(1, 0)) is a covered query.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gt: Timestamp(0, 1), $lt: Timestamp(1, 0)}})
+               .count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gt, $lt count should be a covered query");
+    assert.eq(2, getCountFromExecutionStats(plan.executionStats), "ts $gt, $lt count should be 2");
+
+    // Check that find over (Timestamp(0, 1), Timestamp(1, 0)) does not require a FETCH stage when
+    // the query is covered by an index.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gt: Timestamp(0, 1), $lt: Timestamp(1, 0)}}, {ts: 1, _id: 0})
+               .finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gt, $lt find with project should be a covered query");
+
+    // Check that count over (Timestamp(0, 1), Timestamp(1, 0)] is a covered query.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gt: Timestamp(0, 1), $lte: Timestamp(1, 0)}})
+               .count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gt, $lte count should be a covered query");
+    assert.eq(3, getCountFromExecutionStats(plan.executionStats), "ts $gt, $lte count should be 3");
+
+    // Check that find over (Timestamp(0, 1), Timestamp(1, 0)] does not require a FETCH stage when
+    // the query is covered by an index.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gt: Timestamp(0, 1), $lte: Timestamp(1, 0)}}, {ts: 1, _id: 0})
+               .finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gt, $lte find with project should be a covered query");
+
+    // Check that count over [Timestamp(0, 1), Timestamp(1, 0)) is a covered query.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gte: Timestamp(0, 1), $lt: Timestamp(1, 0)}})
+               .count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gte, $lt count should be a covered query");
+    assert.eq(3, getCountFromExecutionStats(plan.executionStats), "ts $gte, $lt count should be 3");
+
+    // Check that find over [Timestamp(0, 1), Timestamp(1, 0)) does not require a FETCH stage when
+    // the query is covered by an index.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gte: Timestamp(0, 1), $lt: Timestamp(1, 0)}}, {ts: 1, _id: 0})
+               .finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gte, $lt find with project should be a covered query");
+
+    // Check that count over [Timestamp(0, 1), Timestamp(1, 0)] is a covered query.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gte: Timestamp(0, 1), $lte: Timestamp(1, 0)}})
+               .count();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gte, $lte count should be a covered query");
+    assert.eq(
+        4, getCountFromExecutionStats(plan.executionStats), "ts $gte, $lte count should be 4");
+
+    // Check that find over [Timestamp(0, 1), Timestamp(1, 0)] does not require a FETCH stage when
+    // the query is covered by an index.
+    plan = coll.explain("executionStats")
+               .find({ts: {$gte: Timestamp(0, 1), $lte: Timestamp(1, 0)}}, {ts: 1, _id: 0})
+               .finish();
+    assert(isIndexOnly(plan.queryPlanner.winningPlan),
+           "ts $gte, $lte find with project should be a covered query");
+})();
diff --git a/src/mongo/bson/bsonelement.h b/src/mongo/bson/bsonelement.h
index 9e9ee9e60da..111cbad442f 100644
--- a/src/mongo/bson/bsonelement.h
+++ b/src/mongo/bson/bsonelement.h
@@ -297,9 +297,6 @@ public:
     */
     bool trueValue() const;
 
-    /** True if number, string, bool, date, OID */
-    bool isSimpleType() const;
-
     /** True if element is of a numeric type. */
     bool isNumber() const;
 
@@ -709,22 +706,6 @@ inline bool BSONElement::isNumber() const {
     }
 }
 
-inline bool BSONElement::isSimpleType() const {
-    switch (type()) {
-        case NumberLong:
-        case NumberDouble:
-        case NumberInt:
-        case NumberDecimal:
-        case mongo::String:
-        case mongo::Bool:
-        case mongo::Date:
-        case jstOID:
-            return true;
-        default:
-            return false;
-    }
-}
-
 inline Decimal128 BSONElement::numberDecimal() const {
     switch (type()) {
         case NumberDouble:
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 00f8721a11d..50bacf795b4 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -36,6 +36,7 @@
 #include "mongo/db/namespace_string.h"
 #include "mongo/db/operation_context.h"
 #include "mongo/db/query/collation/collator_factory_interface.h"
+#include "mongo/db/query/indexability.h"
 #include "mongo/db/query/query_planner_common.h"
 #include "mongo/util/log.h"
 
@@ -249,7 +250,7 @@ bool CanonicalQuery::isSimpleIdQuery(const BSONObj& query) {
                 if (elt.Obj().firstElementFieldName()[0] == '$') {
                     return false;
                 }
-            } else if (!elt.isSimpleType() && BinData != elt.type()) {
+            } else if (!Indexability::isExactBoundsGenerating(elt)) {
                 // The _id fild cannot be something like { _id : { $gt : ...
                 // But it can be BinData.
                 return false;
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index 2268e3ef30c..b16ad43dc5e 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -57,11 +57,8 @@ namespace {
 // Tightness rules are shared for $lt, $lte, $gt, $gte.
 IndexBoundsBuilder::BoundsTightness getInequalityPredicateTightness(const BSONElement& dataElt,
                                                                     const IndexEntry& index) {
-    if (dataElt.isSimpleType() || dataElt.type() == BSONType::BinData) {
-        return IndexBoundsBuilder::EXACT;
-    }
-
-    return IndexBoundsBuilder::INEXACT_FETCH;
+    return Indexability::isExactBoundsGenerating(dataElt) ? IndexBoundsBuilder::EXACT
+                                                          : IndexBoundsBuilder::INEXACT_FETCH;
 }
 
 }  // namespace
diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp
index c894de8360e..45f11a2cc1d 100644
--- a/src/mongo/db/query/index_bounds_builder_test.cpp
+++ b/src/mongo/db/query/index_bounds_builder_test.cpp
@@ -301,7 +301,7 @@ TEST(IndexBoundsBuilderTest, TranslateGtTimestamp) {
                       fromjson("{'': Timestamp(2, 3), '': Timestamp(4294967295, 4294967295)}"),
                       false,
                       true)));
-    ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH);
+    ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT);
 }
 
 TEST(IndexBoundsBuilderTest, TranslateGtNumber) {
diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h
index 6c8ce44bbb8..1e3bf0b17b0 100644
--- a/src/mongo/db/query/indexability.h
+++ b/src/mongo/db/query/indexability.h
@@ -140,6 +140,27 @@ public:
                 me->matchType() == MatchExpression::LTE);
     }
 
+    /**
+     * Returns true if 'elt' is a BSONType for which exact index bounds can be generated.
+     */
+    static bool isExactBoundsGenerating(BSONElement elt) {
+        switch (elt.type()) {
+            case BSONType::NumberLong:
+            case BSONType::NumberDouble:
+            case BSONType::NumberInt:
+            case BSONType::NumberDecimal:
+            case BSONType::String:
+            case BSONType::Bool:
+            case BSONType::Date:
+            case BSONType::bsonTimestamp:
+            case BSONType::jstOID:
+            case BSONType::BinData:
+                return true;
+            default:
+                return false;
+        }
+    }
+
 private:
     /**
      * Returns true if 'me' is "sargable" but is not a negation and
diff --git a/src/mongo/db/query/plan_cache.cpp b/src/mongo/db/query/plan_cache.cpp
index b8df9789b74..d34df64ab88 100644
--- a/src/mongo/db/query/plan_cache.cpp
+++ b/src/mongo/db/query/plan_cache.cpp
@@ -605,7 +605,7 @@ void PlanCache::encodeKeyForProj(const BSONObj& projObj, StringBuilder* keyBuild
          ++i) {
         const BSONElement& elt = (*i).second;
 
-        if (elt.isSimpleType()) {
+        if (elt.type() != BSONType::Object) {
             // For inclusion/exclusion projections, we encode as "i" or "e".
             *keyBuilder << (elt.trueValue() ? "i" : "e");
         } else {