SERVER-45508 Fix crash when planning collated sort within multi point interval

3 files changed, 45 insertions, 8 deletions

diff --git a/jstests/core/index_sort_within_multiple_point_ranges.js b/jstests/core/index_sort_within_multiple_point_ranges.js
new file mode 100644
index 00000000000..51861742ea4
--- /dev/null
+++ b/jstests/core/index_sort_within_multiple_point_ranges.js
@@ -0,0 +1,24 @@
+/*
+ * This is a regression test for SERVER-45508, which was an invariant failure in the query planner.
+ *
+ * Previously the invariant would be triggered only when all of these happen together:
+ * - an index with a collation exists
+ * - the query planner chooses index bounds with more than one point range
+ * - the point ranges are indexed in descending order
+ * - more than one index can satisfy the query
+ * - the query asks for a sort within each point range
+ * @tags: [assumes_no_implicit_collection_creation_after_drop]
+ */
+(function() {
+    'use strict';
+
+    const coll = db.collation_multi_point_range;
+    coll.drop();
+    assert.commandWorked(db.createCollection(coll.getName(), {collation: {locale: 'fr'}}));
+    assert.commandWorked(coll.createIndex({x: -1}));
+    assert.commandWorked(coll.createIndex({x: -1, y: 1}));
+    coll.insert({x: 2, y: 99});
+
+    assert.commandWorked(coll.find({x: {$in: [2, 5]}}).sort({y: 1}).explain());
+    assert.eq(1, coll.find({x: {$in: [2, 5]}}).sort({y: 1}).itcount());
+})();
diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp
index 5e9375dbe56..e9c93d6b497 100644
--- a/src/mongo/db/query/index_bounds.cpp
+++ b/src/mongo/db/query/index_bounds.cpp
@@ -226,14 +226,19 @@ OrderedIntervalList OrderedIntervalList::reverseClone() const {
 }
 
 Interval::Direction OrderedIntervalList::computeDirection() const {
-    for (auto&& iv : intervals) {
-        const auto dir = iv.getDirection();
-        if (dir != Interval::Direction::kDirectionNone) {
-            return dir;
-        }
-    }
-
-    return Interval::Direction::kDirectionNone;
+    if (intervals.empty())
+        return Interval::Direction::kDirectionNone;
+
+    // Because the interval list is ordered, we only need to compare the two endpoints of the
+    // overall list. If the endpoints are ascending or descending, then each interval already
+    // respects that order. And if the endpoints are equal, then all the intervals must be squeezed
+    // into a single point.
+    bool compareFieldNames = false;
+    int res = intervals.front().start.woCompare(intervals.back().end, compareFieldNames);
+    if (res == 0)
+        return Interval::Direction::kDirectionNone;
+    return res < 0 ? Interval::Direction::kDirectionAscending
+                   : Interval::Direction::kDirectionDescending;
 }
 
 // static
diff --git a/src/mongo/db/query/index_bounds_test.cpp b/src/mongo/db/query/index_bounds_test.cpp
index 652ad0d9cd1..b7242e33031 100644
--- a/src/mongo/db/query/index_bounds_test.cpp
+++ b/src/mongo/db/query/index_bounds_test.cpp
@@ -174,6 +174,14 @@ TEST(IndexBoundsTest, OILReverseClone) {
                              Interval(BSON("" << 20 << "" << 7), false, true)};
     ASSERT(reverseList == listClone);
     ASSERT(listClone.computeDirection() == Interval::Direction::kDirectionDescending);
+
+    OrderedIntervalList descendingPoints("foo");
+    descendingPoints.intervals.push_back(Interval(BSON("" << 7 << "" << 7), true, true));
+    descendingPoints.intervals.push_back(Interval(BSON("" << 5 << "" << 5), true, true));
+    ASSERT(descendingPoints.computeDirection() == Interval::Direction::kDirectionDescending);
+
+    OrderedIntervalList ascendingPoints = descendingPoints.reverseClone();
+    ASSERT(ascendingPoints.computeDirection() == Interval::Direction::kDirectionAscending);
 }
 
 //