SERVER-14070 sort analysis computes additional sort orders provided by an index scan

(cherry picked from commit 5120700460ef7a3240603a4307a0b1be2c358c3c)

3 files changed, 81 insertions, 3 deletions

diff --git a/src/mongo/db/query/planner_analysis_test.cpp b/src/mongo/db/query/planner_analysis_test.cpp
index e638228db50..10e23bfe032 100644
--- a/src/mongo/db/query/planner_analysis_test.cpp
+++ b/src/mongo/db/query/planner_analysis_test.cpp
@@ -29,6 +29,7 @@
 #include "mongo/db/query/planner_analysis.h"
 
 #include "mongo/db/json.h"
+#include "mongo/db/query/query_solution.h"
 #include "mongo/unittest/unittest.h"
 
 using namespace mongo;
@@ -109,4 +110,56 @@ namespace {
                                                                     " d: 1}")));
     }
 
+    // Test the generation of sort orders provided by an index scan done by
+    // IndexScanNode::computeProperties().
+    TEST(QueryPlannerAnalysis, IxscanSortOrdersBasic) {
+        IndexScanNode ixscan;
+        ixscan.indexKeyPattern = fromjson("{a: 1, b: 1, c: 1, d: 1, e: 1}");
+
+        // Bounds are {a: [[1,1]], b: [[2,2]], c: [[3,3]], d: [[1,5]], e:[[1,1],[2,2]]},
+        // all inclusive.
+        OrderedIntervalList oil1("a");
+        oil1.intervals.push_back(Interval(fromjson("{'': 1, '': 1}"), true, true));
+        ixscan.bounds.fields.push_back(oil1);
+
+        OrderedIntervalList oil2("b");
+        oil2.intervals.push_back(Interval(fromjson("{'': 2, '': 2}"), true, true));
+        ixscan.bounds.fields.push_back(oil2);
+
+        OrderedIntervalList oil3("c");
+        oil3.intervals.push_back(Interval(fromjson("{'': 3, '': 3}"), true, true));
+        ixscan.bounds.fields.push_back(oil3);
+
+        OrderedIntervalList oil4("d");
+        oil4.intervals.push_back(Interval(fromjson("{'': 1, '': 5}"), true, true));
+        ixscan.bounds.fields.push_back(oil4);
+
+        OrderedIntervalList oil5("e");
+        oil5.intervals.push_back(Interval(fromjson("{'': 1, '': 1}"), true, true));
+        oil5.intervals.push_back(Interval(fromjson("{'': 2, '': 2}"), true, true));
+        ixscan.bounds.fields.push_back(oil5);
+
+        // Compute and retrieve the set of sorts.
+        ixscan.computeProperties();
+        const BSONObjSet& sorts = ixscan.getSort();
+
+        // One possible sort is the index key pattern.
+        ASSERT(sorts.find(fromjson("{a: 1, b: 1, c: 1, d: 1, e: 1}")) != sorts.end());
+
+        // All prefixes of the key pattern.
+        ASSERT(sorts.find(fromjson("{a: 1}")) != sorts.end());
+        ASSERT(sorts.find(fromjson("{a: 1, b: 1}")) != sorts.end());
+        ASSERT(sorts.find(fromjson("{a: 1, b: 1, c: 1}")) != sorts.end());
+        ASSERT(sorts.find(fromjson("{a: 1, b: 1, c: 1, d: 1}")) != sorts.end());
+
+        // Additional sorts considered due to point intervals on 'a', 'b', and 'c'.
+        ASSERT(sorts.find(fromjson("{b: 1, c: 1, d: 1, e: 1}")) != sorts.end());
+        ASSERT(sorts.find(fromjson("{c: 1, d: 1, e: 1}")) != sorts.end());
+        ASSERT(sorts.find(fromjson("{d: 1, e: 1}")) != sorts.end());
+        ASSERT(sorts.find(fromjson("{d: 1}")) != sorts.end());
+
+        // There should be 9 total sorts: make sure no other ones snuck their way in.
+        ASSERT_EQUALS(9U, sorts.size());
+    }
+
 }  // namespace
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index cc4b4b36f67..b4bdac93a50 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1268,6 +1268,18 @@ namespace {
                                 "{filter: null, pattern: {a: true}}}}}");
     }
 
+    // SERVER-14070
+    TEST_F(QueryPlannerTest, CompoundIndexWithEqualityPredicatesProvidesSort) {
+        params.options = QueryPlannerParams::NO_TABLE_SCAN;
+        addIndex(BSON("a" << 1 << "b" << 1));
+        runQuerySortProj(fromjson("{a: 1, b: 1}"), fromjson("{b: 1}"), BSONObj());
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: {filter: null,"
+                                "pattern: {a: 1, b: 1}, "
+                                "bounds: {a:[[1,1,true,true]], b:[[1,1,true,true]]}}}}}");
+    }
+
     //
     // Sort with limit and/or skip
     //
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index 230efac3282..6bc06047a1f 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -501,9 +501,13 @@ namespace mongo {
         // For each sort in _sorts:
         //    For each drop in powerset(equalityFields):
         //        Remove fields in 'drop' from 'sort' and add resulting sort to output.
-
-        // Since this involves a powerset, we only remove point intervals that the prior sort
-        // planning code removed, namely the contiguous prefix of the key pattern.
+        //
+        // Since this involves a powerset, we don't generate the full set of possibilities.
+        // Instead, we generate sort orders by removing possible contiguous prefixes of equality
+        // predicates. For example, if the key pattern is {a: 1, b: 1, c: 1, d: 1, e: 1}
+        // and and there are equality predicates on 'a', 'b', and 'c', then here we add the sort
+        // orders {b: 1, c: 1, d: 1, e: 1} and {c: 1, d: 1, e: 1}. (We also end up adding
+        // {d: 1, e: 1} and {d: 1}, but this is done later on.)
         BSONObjIterator it(sortPattern);
         BSONObjBuilder suffixBob;
         while (it.more()) {
@@ -514,6 +518,15 @@ namespace mongo {
                 // This field isn't a point interval, can't drop.
                 break;
             }
+
+            // We add the sort obtained by dropping 'elt' and all preceding elements from the index
+            // key pattern.
+            BSONObjIterator droppedPrefixIt = it;
+            BSONObjBuilder droppedPrefixBob;
+            while (droppedPrefixIt.more()) {
+                droppedPrefixBob.append(droppedPrefixIt.next());
+            }
+            _sorts.insert(droppedPrefixBob.obj());
         }
 
         while (it.more()) {