SERVER-61939 Tighter bounds for clustered collection scans

8 files changed, 160 insertions, 56 deletions

diff --git a/src/mongo/db/query/internal_plans.cpp b/src/mongo/db/query/internal_plans.cpp
index 0f45d3b4649..425d2857eb5 100644
--- a/src/mongo/db/query/internal_plans.cpp
+++ b/src/mongo/db/query/internal_plans.cpp
@@ -79,12 +79,12 @@ CollectionScanParams convertIndexScanParamsToCollScanParams(
             clustered_util::matchesClusterKey(keyPattern, collection->getClusteredInfo()));
     invariant(collection->getDefaultCollator() == nullptr);
 
-    boost::optional<RecordId> startRecord, endRecord;
+    boost::optional<RecordIdBound> startRecord, endRecord;
     if (!startKey.isEmpty()) {
-        startRecord = RecordId(record_id_helpers::keyForElem(startKey.firstElement(), nullptr));
+        startRecord = RecordIdBound(record_id_helpers::keyForElem(startKey.firstElement()));
     }
     if (!endKey.isEmpty()) {
-        endRecord = RecordId(record_id_helpers::keyForElem(endKey.firstElement(), nullptr));
+        endRecord = RecordIdBound(record_id_helpers::keyForElem(endKey.firstElement()));
     }
 
     // For a forward scan, the startKey is the minRecord. For a backward scan, it is the maxRecord.
@@ -93,7 +93,7 @@ CollectionScanParams convertIndexScanParamsToCollScanParams(
 
     if (minRecord && maxRecord) {
         // Regardless of direction, the minRecord should always be less than the maxRecord
-        dassert(minRecord < maxRecord,
+        dassert(minRecord->recordId() < maxRecord->recordId(),
                 str::stream() << "Expected the minRecord " << minRecord
                               << " to be less than the maxRecord " << maxRecord
                               << " on a bounded collection scan. Original startKey and endKey for "
@@ -105,6 +105,7 @@ CollectionScanParams convertIndexScanParamsToCollScanParams(
     CollectionScanParams params;
     params.minRecord = minRecord;
     params.maxRecord = maxRecord;
+
     if (InternalPlanner::FORWARD == direction) {
         params.direction = CollectionScanParams::FORWARD;
     } else {
@@ -120,8 +121,8 @@ CollectionScanParams createCollectionScanParams(
     const CollectionPtr* coll,
     InternalPlanner::Direction direction,
     boost::optional<RecordId> resumeAfterRecordId,
-    boost::optional<RecordId> minRecord,
-    boost::optional<RecordId> maxRecord) {
+    boost::optional<RecordIdBound> minRecord,
+    boost::optional<RecordIdBound> maxRecord) {
     const auto& collection = *coll;
     invariant(collection);
 
@@ -146,8 +147,8 @@ std::unique_ptr<PlanExecutor, PlanExecutor::Deleter> InternalPlanner::collection
     PlanYieldPolicy::YieldPolicy yieldPolicy,
     const Direction direction,
     boost::optional<RecordId> resumeAfterRecordId,
-    boost::optional<RecordId> minRecord,
-    boost::optional<RecordId> maxRecord) {
+    boost::optional<RecordIdBound> minRecord,
+    boost::optional<RecordIdBound> maxRecord) {
     const auto& collection = *coll;
     invariant(collection);
 
@@ -205,8 +206,8 @@ std::unique_ptr<PlanExecutor, PlanExecutor::Deleter> InternalPlanner::deleteWith
     std::unique_ptr<DeleteStageParams> params,
     PlanYieldPolicy::YieldPolicy yieldPolicy,
     Direction direction,
-    boost::optional<RecordId> minRecord,
-    boost::optional<RecordId> maxRecord) {
+    boost::optional<RecordIdBound> minRecord,
+    boost::optional<RecordIdBound> maxRecord) {
     const auto& collection = *coll;
     invariant(collection);
     auto ws = std::make_unique<WorkingSet>();
diff --git a/src/mongo/db/query/internal_plans.h b/src/mongo/db/query/internal_plans.h
index 387fb8f9d80..781b336526f 100644
--- a/src/mongo/db/query/internal_plans.h
+++ b/src/mongo/db/query/internal_plans.h
@@ -78,8 +78,8 @@ public:
         PlanYieldPolicy::YieldPolicy yieldPolicy,
         Direction direction = FORWARD,
         boost::optional<RecordId> resumeAfterRecordId = boost::none,
-        boost::optional<RecordId> minRecord = boost::none,
-        boost::optional<RecordId> maxRecord = boost::none);
+        boost::optional<RecordIdBound> minRecord = boost::none,
+        boost::optional<RecordIdBound> maxRecord = boost::none);
 
     static std::unique_ptr<PlanExecutor, PlanExecutor::Deleter> collectionScan(
         OperationContext* opCtx,
@@ -96,8 +96,8 @@ public:
         std::unique_ptr<DeleteStageParams> deleteStageParams,
         PlanYieldPolicy::YieldPolicy yieldPolicy,
         Direction direction = FORWARD,
-        boost::optional<RecordId> minRecord = boost::none,
-        boost::optional<RecordId> maxRecord = boost::none);
+        boost::optional<RecordIdBound> minRecord = boost::none,
+        boost::optional<RecordIdBound> maxRecord = boost::none);
 
     /**
      * Returns an index scan.  Caller owns returned pointer.
diff --git a/src/mongo/db/query/plan_explainer_impl.cpp b/src/mongo/db/query/plan_explainer_impl.cpp
index 04cd97980e9..1e34cf73ebe 100644
--- a/src/mongo/db/query/plan_explainer_impl.cpp
+++ b/src/mongo/db/query/plan_explainer_impl.cpp
@@ -257,10 +257,10 @@ void statsToBSON(const PlanStageStats& stats,
         CollectionScanStats* spec = static_cast<CollectionScanStats*>(stats.specific.get());
         bob->append("direction", spec->direction > 0 ? "forward" : "backward");
         if (spec->minRecord) {
-            record_id_helpers::appendToBSONAs(*spec->minRecord, bob, "minRecord");
+            spec->minRecord->appendToBSONAs(bob, "minRecord");
         }
         if (spec->maxRecord) {
-            record_id_helpers::appendToBSONAs(*spec->maxRecord, bob, "maxRecord");
+            spec->maxRecord->appendToBSONAs(bob, "maxRecord");
         }
         if (verbosity >= ExplainOptions::Verbosity::kExecStats) {
             bob->appendNumber("docsExamined", static_cast<long long>(spec->docsTested));
diff --git a/src/mongo/db/query/plan_explainer_sbe.cpp b/src/mongo/db/query/plan_explainer_sbe.cpp
index 35c9a2830ac..676994720a7 100644
--- a/src/mongo/db/query/plan_explainer_sbe.cpp
+++ b/src/mongo/db/query/plan_explainer_sbe.cpp
@@ -73,10 +73,10 @@ void statsToBSON(const QuerySolutionNode* node,
             auto csn = static_cast<const CollectionScanNode*>(node);
             bob->append("direction", csn->direction > 0 ? "forward" : "backward");
             if (csn->minRecord) {
-                record_id_helpers::appendToBSONAs(*csn->minRecord, bob, "minRecord");
+                csn->minRecord->appendToBSONAs(bob, "minRecord");
             }
             if (csn->maxRecord) {
-                record_id_helpers::appendToBSONAs(*csn->maxRecord, bob, "maxRecord");
+                csn->maxRecord->appendToBSONAs(bob, "maxRecord");
             }
             break;
         }
diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp
index 99073842737..3c6a8fdc0c0 100644
--- a/src/mongo/db/query/planner_access.cpp
+++ b/src/mongo/db/query/planner_access.cpp
@@ -228,6 +228,20 @@ bool affectedByCollator(const BSONElement& element) {
     }
 }
 
+void setMinRecord(CollectionScanNode* collScan, const BSONObj& min) {
+    const auto newMinRecord = record_id_helpers::keyForObj(min);
+    if (!collScan->minRecord || newMinRecord > collScan->minRecord->recordId()) {
+        collScan->minRecord = RecordIdBound(newMinRecord, min);
+    }
+}
+
+void setMaxRecord(CollectionScanNode* collScan, const BSONObj& max) {
+    const auto newMaxRecord = record_id_helpers::keyForObj(max);
+    if (!collScan->maxRecord || newMaxRecord < collScan->maxRecord->recordId()) {
+        collScan->maxRecord = RecordIdBound(newMaxRecord, max);
+    }
+}
+
 // Returns whether element is not affected by collators or query and collection collators are
 // compatible.
 bool compatibleCollator(const QueryPlannerParams& params,
@@ -267,30 +281,12 @@ void handleRIDRangeMinMax(const CanonicalQuery& query,
         // Assumes clustered collection scans are only supported with the forward direction.
         collScan->boundInclusion =
             CollectionScanParams::ScanBoundInclusion::kIncludeStartRecordOnly;
-        newMaxRecord = record_id_helpers::keyForElem(maxObj.firstElement(), collator);
+        setMaxRecord(collScan, IndexBoundsBuilder::objFromElement(maxObj.firstElement(), collator));
     }
 
     if (!minObj.isEmpty() && compatibleCollator(params, collator, minObj.firstElement())) {
         // The min() is inclusive as are bounded collection scans by default.
-        newMinRecord = record_id_helpers::keyForElem(minObj.firstElement(), collator);
-    }
-
-    if (!collScan->minRecord) {
-        collScan->minRecord = newMinRecord;
-    } else if (newMinRecord) {
-        if (*newMinRecord > *collScan->minRecord) {
-            // The newMinRecord is more restrictive than the existing minRecord.
-            collScan->minRecord = newMinRecord;
-        }
-    }
-
-    if (!collScan->maxRecord) {
-        collScan->maxRecord = newMaxRecord;
-    } else if (newMaxRecord) {
-        if (*newMaxRecord < *collScan->maxRecord) {
-            // The newMaxRecord is more restrictive than the existing maxRecord.
-            collScan->maxRecord = newMaxRecord;
-        }
+        setMinRecord(collScan, IndexBoundsBuilder::objFromElement(minObj.firstElement(), collator));
     }
 }
 
@@ -329,24 +325,31 @@ void handleRIDRangeScan(const MatchExpression* conjunct,
     }
 
     const auto& element = match->getData();
+
+    // Set coarse min/max bounds based on type in case we can't set tight bounds.
+    BSONObjBuilder minb;
+    minb.appendMinForType("", element.type());
+    setMinRecord(collScan, minb.obj());
+
+    BSONObjBuilder maxb;
+    maxb.appendMaxForType("", element.type());
+    setMaxRecord(collScan, maxb.obj());
+
     bool compatible = compatibleCollator(params, collator, element);
     if (!compatible) {
         return;  // Collator affects probe and it's not compatible with collection's collator.
     }
 
-    auto& maxRecord = collScan->maxRecord;
-    auto& minRecord = collScan->minRecord;
+    const auto collated = IndexBoundsBuilder::objFromElement(element, collator);
     if (dynamic_cast<const EqualityMatchExpression*>(match)) {
-        minRecord = record_id_helpers::keyForElem(element, collator);
-        maxRecord = minRecord;
-    } else if (!maxRecord &&
-               (dynamic_cast<const LTMatchExpression*>(match) ||
-                dynamic_cast<const LTEMatchExpression*>(match))) {
-        maxRecord = record_id_helpers::keyForElem(element, collator);
-    } else if (!minRecord &&
-               (dynamic_cast<const GTMatchExpression*>(match) ||
-                dynamic_cast<const GTEMatchExpression*>(match))) {
-        minRecord = record_id_helpers::keyForElem(element, collator);
+        setMinRecord(collScan, collated);
+        setMaxRecord(collScan, collated);
+    } else if (dynamic_cast<const LTMatchExpression*>(match) ||
+               dynamic_cast<const LTEMatchExpression*>(match)) {
+        setMaxRecord(collScan, collated);
+    } else if (dynamic_cast<const GTMatchExpression*>(match) ||
+               dynamic_cast<const GTEMatchExpression*>(match)) {
+        setMinRecord(collScan, collated);
     }
 }
 
@@ -398,7 +401,7 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::makeCollectionScan(
             if (minTs) {
                 StatusWith<RecordId> goal = record_id_helpers::keyForOptime(*minTs);
                 if (goal.isOK()) {
-                    csn->minRecord = goal.getValue();
+                    csn->minRecord = RecordIdBound(goal.getValue());
                 }
 
                 if (assertMinTsHasNotFallenOffOplog) {
@@ -408,7 +411,7 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAccess::makeCollectionScan(
             if (maxTs) {
                 StatusWith<RecordId> goal = record_id_helpers::keyForOptime(*maxTs);
                 if (goal.isOK()) {
-                    csn->maxRecord = goal.getValue();
+                    csn->maxRecord = RecordIdBound(goal.getValue());
                 }
             }
         }
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index e91bb18f7ab..d63704a3afa 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -40,6 +40,7 @@
 #include "mongo/db/query/classic_plan_cache.h"
 #include "mongo/db/query/index_bounds.h"
 #include "mongo/db/query/plan_enumerator_explain_info.h"
+#include "mongo/db/query/record_id_bound.h"
 #include "mongo/db/query/stage_types.h"
 #include "mongo/util/id_generator.h"
 
@@ -444,11 +445,11 @@ struct CollectionScanNode : public QuerySolutionNodeWithSortSet {
 
     // If present, this parameter sets the start point of a forward scan or the end point of a
     // reverse scan.
-    boost::optional<RecordId> minRecord;
+    boost::optional<RecordIdBound> minRecord;
 
     // If present, this parameter sets the start point of a reverse scan or the end point of a
     // forward scan.
-    boost::optional<RecordId> maxRecord;
+    boost::optional<RecordIdBound> maxRecord;
 
     // If true, the collection scan will return a token that can be used to resume the scan.
     bool requestResumeToken = false;
diff --git a/src/mongo/db/query/record_id_bound.h b/src/mongo/db/query/record_id_bound.h
new file mode 100644
index 00000000000..99400ae938d
--- /dev/null
+++ b/src/mongo/db/query/record_id_bound.h
@@ -0,0 +1,97 @@
+/**
+ *    Copyright (C) 2022-present MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the Server Side Public License, version 1,
+ *    as published by MongoDB, Inc.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    Server Side Public License for more details.
+ *
+ *    You should have received a copy of the Server Side Public License
+ *    along with this program. If not, see
+ *    <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the Server Side Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#pragma once
+
+#include <boost/optional.hpp>
+#include <fmt/format.h>
+#include <ostream>
+
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/util/builder.h"
+#include "mongo/db/record_id.h"
+#include "mongo/db/record_id_helpers.h"
+#include "mongo/db/storage/key_string.h"
+
+namespace mongo {
+
+/**
+ * A RecordId bound for a collection scan, with an optional BSON representation for pretty printing.
+ */
+class RecordIdBound {
+public:
+    RecordIdBound() = default;
+
+    explicit RecordIdBound(RecordId&& recordId, boost::optional<BSONObj> bson = boost::none)
+        : _recordId(recordId), _bson(bson) {}
+
+    explicit RecordIdBound(const RecordId& recordId, boost::optional<BSONObj> bson = boost::none)
+        : _recordId(recordId), _bson(bson) {}
+
+    RecordId recordId() const {
+        return _recordId;
+    }
+
+    /**
+     * Appends a BSON respresentation of the bound to a BSONObjBuilder. If one is not explicitily
+     * provided it reconstructs it from the RecordId.
+     */
+    void appendToBSONAs(BSONObjBuilder* builder, StringData fieldName) const {
+        if (_bson) {
+            builder->appendAs(_bson->firstElement(), fieldName);
+        } else {
+            record_id_helpers::appendToBSONAs(_recordId, builder, fieldName);
+        }
+    }
+
+    std::string toString() const {
+        return _recordId.toString();
+    }
+
+    /**
+     * Compares the underlying RecordIds.
+     */
+    int compare(const RecordIdBound& rhs) const {
+        return _recordId.compare(rhs._recordId);
+    }
+
+private:
+    RecordId _recordId;
+    boost::optional<BSONObj> _bson;
+};
+
+inline StringBuilder& operator<<(StringBuilder& stream, const RecordIdBound& id) {
+    return stream << "RecordIdBound(" << id.toString() << ')';
+}
+
+inline std::ostream& operator<<(std::ostream& stream, const RecordIdBound& id) {
+    return stream << "RecordIdBound(" << id.toString() << ')';
+}
+
+}  // namespace mongo
diff --git a/src/mongo/db/query/sbe_stage_builder_coll_scan.cpp b/src/mongo/db/query/sbe_stage_builder_coll_scan.cpp
index d2102cea044..9ec9bb1ace3 100644
--- a/src/mongo/db/query/sbe_stage_builder_coll_scan.cpp
+++ b/src/mongo/db/query/sbe_stage_builder_coll_scan.cpp
@@ -45,6 +45,7 @@
 #include "mongo/db/query/sbe_stage_builder.h"
 #include "mongo/db/query/sbe_stage_builder_filter.h"
 #include "mongo/db/query/util/make_data_structure.h"
+#include "mongo/db/record_id_helpers.h"
 #include "mongo/logv2/log.h"
 #include "mongo/util/str.h"
 
@@ -272,7 +273,7 @@ std::pair<std::unique_ptr<sbe::PlanStage>, PlanStageSlots> generateOptimizedOplo
             return {state.slotId(), makeConstant(tag, val)};
         } else if (csn->minRecord) {
             auto cursor = collection->getRecordStore()->getCursor(state.opCtx);
-            auto startRec = cursor->seekNear(*csn->minRecord);
+            auto startRec = cursor->seekNear(csn->minRecord->recordId());
             if (startRec) {
                 LOGV2_DEBUG(205841, 3, "Using direct oplog seek");
                 auto [tag, val] = sbe::value::makeCopyRecordId(startRec->id);
@@ -437,7 +438,8 @@ std::pair<std::unique_ptr<sbe::PlanStage>, PlanStageSlots> generateOptimizedOplo
             std::move(stage),
             makeBinaryOp(sbe::EPrimBinary::lessEq,
                          makeVariable(*tsSlot),
-                         makeConstant(sbe::value::TypeTags::Timestamp, csn->maxRecord->getLong())),
+                         makeConstant(sbe::value::TypeTags::Timestamp,
+                                      csn->maxRecord->recordId().getLong())),
             csn->nodeId());
     }