SERVER-73482 Fix $natural hint with clustered collection sorts

4 files changed, 126 insertions, 13 deletions

diff --git a/etc/backports_required_for_multiversion_tests.yml b/etc/backports_required_for_multiversion_tests.yml
index 56e36f3cc87..ad3ed92d060 100644
--- a/etc/backports_required_for_multiversion_tests.yml
+++ b/etc/backports_required_for_multiversion_tests.yml
@@ -328,6 +328,8 @@ last-continuous:
     ticket: SERVER-74245
   - test_file: jstests/core/field_name_validation.js
     ticket: SERVER-75517
+  - test_file: jstests/core/clustered/clustered_collection_hint.js
+    ticket: SERVER-73482
   suites: null
 last-lts:
   all:
@@ -719,4 +721,6 @@ last-lts:
     ticket: SERVER-74124
   - test_file: jstests/core/field_name_validation.js
     ticket: SERVER-75517
+  - test_file: jstests/core/clustered/clustered_collection_hint.js
+    ticket: SERVER-73482
   suites: null
diff --git a/jstests/libs/clustered_collections/clustered_collection_hint_common.js b/jstests/libs/clustered_collections/clustered_collection_hint_common.js
index a65939698e2..c96fa821bd3 100644
--- a/jstests/libs/clustered_collections/clustered_collection_hint_common.js
+++ b/jstests/libs/clustered_collections/clustered_collection_hint_common.js
@@ -196,6 +196,91 @@ function testClusteredCollectionHint(coll, clusterKey, clusterKeyName) {
             }
         });
 
+        // Find with $natural hints and sorts: we should scan the collection in the hinted
+        // direction regardless of sort direction, and provide a blocking sort if needed.
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: 1}, sort: {[clusterKeyFieldName]: 1}},
+            expectedWinningPlanStats: {
+                stage: "COLLSCAN",
+                direction: "forward",
+            },
+            unexpectedWinningPlanStats: ["SORT"]  // We shouldn't need a blocking sort here.
+        });
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: -1}, sort: {[clusterKeyFieldName]: 1}},
+            expectedWinningPlanStats: [
+                {stage: "SORT", sortPattern: {[clusterKeyFieldName]: 1}},
+                {
+                    stage: "COLLSCAN",
+                    direction: "backward",
+                }
+            ]
+        });
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: 1}, sort: {[clusterKeyFieldName]: -1}},
+            expectedWinningPlanStats: [
+                {stage: "SORT", sortPattern: {[clusterKeyFieldName]: -1}},
+                {
+                    stage: "COLLSCAN",
+                    direction: "forward",
+                }
+            ]
+        });
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: -1}, sort: {[clusterKeyFieldName]: -1}},
+            expectedWinningPlanStats: {
+                stage: "COLLSCAN",
+                direction: "backward",
+            },
+            unexpectedWinningPlanStats: ["SORT"]  // We shouldn't need a blocking sort here.
+        });
+
+        // We always need a blocking sort when the sort pattern does not match the provided sort for
+        // the clustered collection.
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: 1}, sort: {a: 1}},
+            expectedWinningPlanStats: [
+                {stage: "SORT", sortPattern: {a: 1}},
+                {
+                    stage: "COLLSCAN",
+                    direction: "forward",
+                }
+            ]
+        });
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: -1}, sort: {a: 1}},
+            expectedWinningPlanStats: [
+                {stage: "SORT", sortPattern: {a: 1}},
+                {
+                    stage: "COLLSCAN",
+                    direction: "backward",
+                }
+            ]
+        });
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: 1}, sort: {a: -1}},
+            expectedWinningPlanStats: [
+                {stage: "SORT", sortPattern: {a: -1}},
+                {
+                    stage: "COLLSCAN",
+                    direction: "forward",
+                }
+            ]
+        });
+        validateClusteredCollectionHint(coll, {
+            expectedNReturned: batchSize,
+            cmd: {find: collName, hint: {$natural: -1}, sort: {a: -1}},
+            expectedWinningPlanStats:
+                [{stage: "SORT", sortPattern: {a: -1}}, {stage: "COLLSCAN", direction: "backward"}],
+        });
+
         // Find on a standard index.
         validateClusteredCollectionHint(coll, {
             expectedNReturned: batchSize,
@@ -280,25 +365,39 @@ function testClusteredCollectionHint(coll, clusterKey, clusterKeyName) {
     return testHint(coll, clusterKey, clusterKeyName);
 }
 
-function validateClusteredCollectionHint(coll,
-                                         {expectedNReturned, cmd, expectedWinningPlanStats = {}}) {
+function validateClusteredCollectionHint(
+    coll,
+    {expectedNReturned, cmd, expectedWinningPlanStats = {}, unexpectedWinningPlanStats = []}) {
     const explain = assert.commandWorked(coll.runCommand({explain: cmd}));
     assert.eq(explain.executionStats.nReturned, expectedNReturned, tojson(explain));
 
     const actualWinningPlan = getWinningPlan(explain.queryPlanner);
-    const stageOfInterest = getPlanStage(actualWinningPlan, expectedWinningPlanStats.stage);
-    assert.neq(null, stageOfInterest);
 
-    for (const [key, value] of Object.entries(expectedWinningPlanStats)) {
-        assert(stageOfInterest[key] !== undefined, tojson(explain));
-        assert.eq(stageOfInterest[key], value, tojson(explain));
+    if (!Array.isArray(expectedWinningPlanStats)) {
+        expectedWinningPlanStats = [expectedWinningPlanStats];
     }
 
-    // Explicitly check that the plan is not bounded by default.
-    if (!expectedWinningPlanStats.hasOwnProperty("minRecord")) {
-        assert(!actualWinningPlan.hasOwnProperty("minRecord"), tojson(explain));
+    for (const excludedStage of unexpectedWinningPlanStats) {
+        const stageOfInterest = getPlanStage(actualWinningPlan, excludedStage);
+        assert.eq(null, stageOfInterest);
     }
-    if (!expectedWinningPlanStats.hasOwnProperty("maxRecord")) {
-        assert(!actualWinningPlan.hasOwnProperty("maxRecord"), tojson(explain));
+
+    for (const expectedWinningPlanStageStats of expectedWinningPlanStats) {
+        const stageOfInterest =
+            getPlanStage(actualWinningPlan, expectedWinningPlanStageStats.stage);
+        assert.neq(null, stageOfInterest);
+
+        for (const [key, value] of Object.entries(expectedWinningPlanStageStats)) {
+            assert(stageOfInterest[key] !== undefined, tojson(explain));
+            assert.eq(stageOfInterest[key], value, tojson(explain));
+        }
+
+        // Explicitly check that the plan is not bounded by default.
+        if (!expectedWinningPlanStageStats.hasOwnProperty("minRecord")) {
+            assert(!actualWinningPlan.hasOwnProperty("minRecord"), tojson(explain));
+        }
+        if (!expectedWinningPlanStageStats.hasOwnProperty("maxRecord")) {
+            assert(!actualWinningPlan.hasOwnProperty("maxRecord"), tojson(explain));
+        }
     }
 }
diff --git a/src/mongo/db/query/planner_analysis.cpp b/src/mongo/db/query/planner_analysis.cpp
index ab80925d666..e38a9d04a6e 100644
--- a/src/mongo/db/query/planner_analysis.cpp
+++ b/src/mongo/db/query/planner_analysis.cpp
@@ -1052,7 +1052,12 @@ std::unique_ptr<QuerySolutionNode> QueryPlannerAnalysis::analyzeSort(
     // Sort is not provided.  See if we provide the reverse of our sort pattern.
     // If so, we can reverse the scan direction(s).
     BSONObj reverseSort = QueryPlannerCommon::reverseSortObj(sortObj);
-    if (providedSorts.contains(reverseSort)) {
+    // The only collection scan that includes a sort order in 'providedSorts' is a scan on a
+    // clustered collection. However, we cannot reverse this scan if its direction is specified by a
+    // $natural hint.
+    const bool naturalCollScan = solnRoot->getType() == StageType::STAGE_COLLSCAN &&
+        query.getFindCommandRequest().getHint()[query_request_helper::kNaturalSortField];
+    if (providedSorts.contains(reverseSort) && !naturalCollScan) {
         QueryPlannerCommon::reverseScans(solnRoot.get());
         LOGV2_DEBUG(20951,
                     5,
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index aaebf012193..64e1cbe2066 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -324,6 +324,11 @@ CollectionScanNode::CollectionScanNode()
 void CollectionScanNode::computeProperties() {
     if (clusteredIndex && hasCompatibleCollation) {
         auto sort = clustered_util::getSortPattern(*clusteredIndex);
+        if (direction == -1) {
+            // If we are scanning the collection in the descending direction, we provide the reverse
+            // sort order.
+            sort = QueryPlannerCommon::reverseSortObj(sort);
+        }
         sortSet = ProvidedSortSet(sort);
     }
 }