From c27685781d30a2646b5e75270ee81b6954303210 Mon Sep 17 00:00:00 2001
From: David Storch <david.storch@10gen.com>
Date: Thu, 17 Apr 2014 00:40:02 -0400
Subject: SERVER-13611 fix sort elimination in the case of trailing fields
 (cherry picked from commit 9ec25e399fc775361ed37fd5abb78960659a308b)

---
 src/mongo/db/query/query_planner_test.cpp | 27 ++++++++++++++++++++++++++-
 src/mongo/db/query/query_solution.cpp     | 30 +++++++++++++++++++++---------
 2 files changed, 47 insertions(+), 10 deletions(-)

diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 51c91cce918..692dcdf6ff6 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1086,7 +1086,7 @@ namespace {
     }
 
     //
-    // Basic sort elimination
+    // Sort elimination
     //
 
     TEST_F(QueryPlannerTest, BasicSortElim) {
@@ -1111,6 +1111,31 @@ namespace {
                                 "{filter: null, pattern: {a: 1, b: 1}}}}}");
     }
 
+    // SERVER-13611: test that sort elimination still works if there are
+    // trailing fields in the index.
+    TEST_F(QueryPlannerTest, SortElimTrailingFields) {
+        addIndex(BSON("a" << 1 << "b" << 1 << "c" << 1));
+        runQuerySortProj(fromjson("{a: 5}"), BSON("b" << 1), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+        assertSolutionExists("{sort: {pattern: {b: 1}, limit: 0, "
+                                "node: {cscan: {dir: 1, filter: {a: 5}}}}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: "
+                                "{filter: null, pattern: {a: 1, b: 1, c: 1}}}}}");
+    }
+
+    // Sort elimination with trailing fields where the sort direction is descending.
+    TEST_F(QueryPlannerTest, SortElimTrailingFieldsReverse) {
+        addIndex(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1));
+        runQuerySortProj(fromjson("{a: 5, b: 6}"), BSON("c" << -1), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+        assertSolutionExists("{sort: {pattern: {c: -1}, limit: 0, "
+                                "node: {cscan: {dir: 1, filter: {a: 5, b: 6}}}}}");
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: "
+                                "{filter: null, dir: -1, pattern: {a: 1, b: 1, c: 1, d: 1}}}}}");
+    }
+
     //
     // Basic compound
     //
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index 5df771b491d..9192760d51c 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -515,25 +515,37 @@ namespace mongo {
         // 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.
         BSONObjIterator it(sortPattern);
-        BSONObjBuilder prefixBob;
+        BSONObjBuilder suffixBob;
         while (it.more()) {
             BSONElement elt = it.next();
             // TODO: string slowness.  fix when bounds are stringdata not string.
             if (equalityFields.end() == equalityFields.find(string(elt.fieldName()))) {
-                prefixBob.append(elt);
+                suffixBob.append(elt);
                 // This field isn't a point interval, can't drop.
                 break;
             }
         }
 
         while (it.more()) {
-            prefixBob.append(it.next());
-        }
-
-        // If we have an index {a:1} and an equality on 'a' don't append an empty sort order.
-        BSONObj filterPointsObj = prefixBob.obj();
-        if (!filterPointsObj.isEmpty()) {
-            _sorts.insert(filterPointsObj);
+            suffixBob.append(it.next());
+        }
+
+        // We've found the suffix following the contiguous prefix of equality fields.
+        //   Ex. For index {a: 1, b: 1, c: 1, d: 1} and query {a: 3, b: 5}, this suffix
+        //   of the key pattern is {c: 1, d: 1}.
+        //
+        // Now we have to add all prefixes of this suffix as possible sort orders.
+        //   Ex. Continuing the example from above, we have to include sort orders
+        //   {c: 1} and {c: 1, d: 1}.
+        BSONObj filterPointsObj = suffixBob.obj();
+        for (int i = 0; i < filterPointsObj.nFields(); ++i) {
+            // Make obj out of fields [0,i]
+            BSONObjIterator it(filterPointsObj);
+            BSONObjBuilder prefixBob;
+            for (int j = 0; j <= i; ++j) {
+                prefixBob.append(it.next());
+            }
+            _sorts.insert(prefixBob.obj());
         }
     }
 
-- 
cgit v1.2.1