SERVER-13899 Forbid whole index scan on plugin index to provide sort

(cherry picked from commit a6a0c243b6cd6a5d45c876ab100a21073c070a00)

3 files changed, 73 insertions, 3 deletions

diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp
index 15fc5170611..8a25e9b00e3 100644
--- a/src/mongo/db/query/plan_cache_test.cpp
+++ b/src/mongo/db/query/plan_cache_test.cpp
@@ -888,7 +888,8 @@ namespace {
                 "{ixscan: {filter: null, pattern: {b: 1, c: 1}}}]}}}}");
     }
 
-    // SERVER-10801
+    // Disabled: SERVER-10801.
+    /*
     TEST_F(CachePlanSelectionTest, SortOnGeoQuery) {
         addIndex(BSON("timestamp" << -1 << "position" << "2dsphere"));
         BSONObj query = fromjson("{position: {$geoWithin: {$geometry: {type: \"Polygon\", "
@@ -900,6 +901,7 @@ namespace {
         assertPlanCacheRecoversSolution(query, sort, BSONObj(),
             "{fetch: {node: {ixscan: {pattern: {timestamp: -1, position: '2dsphere'}}}}}");
     }
+    */
 
     // SERVER-9257
     TEST_F(CachePlanSelectionTest, CompoundGeoNoGeoPredicate) {
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 0439b49fb96..72964ff90ce 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -811,9 +811,27 @@ namespace mongo {
             if (!usingIndexToSort) {
                 for (size_t i = 0; i < params.indices.size(); ++i) {
                     const IndexEntry& index = params.indices[i];
+                    // Only regular (non-plugin) indexes can be used to provide a sort.
+                    if (index.type != INDEX_BTREE) {
+                        continue;
+                    }
+                    // Only non-sparse indexes can be used to provide a sort.
                     if (index.sparse) {
                         continue;
                     }
+
+                    // TODO: Sparse indexes can't normally provide a sort, because non-indexed
+                    // documents could potentially be missing from the result set.  However, if the
+                    // query predicate can be used to guarantee that all documents to be returned
+                    // are indexed, then the index should be able to provide the sort.
+                    //
+                    // For example:
+                    // - Sparse index {a: 1, b: 1} should be able to provide a sort for
+                    //   find({b: 1}).sort({a: 1}).  SERVER-13908.
+                    // - Index {a: 1, b: "2dsphere"} (which is "geo-sparse", if
+                    //   2dsphereIndexVersion=2) should be able to provide a sort for
+                    //   find({b: GEO}).sort({a:1}).  SERVER-10801.
+
                     const BSONObj kp = LiteParsedQuery::normalizeSortOrder(index.keyPattern);
                     if (providesSort(query, kp)) {
                         QLOG() << "Planner: outputting soln that uses index to provide sort."
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index 5da03f05540..acb8fb09b98 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1045,6 +1045,53 @@ namespace {
     //
 
     TEST_F(QueryPlannerTest, BasicSort) {
+        addIndex(BSON("x" << 1));
+        runQuerySortProj(BSONObj(), BSON("x" << 1), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 2U);
+        assertSolutionExists("{fetch: {filter: null, node: {ixscan: "
+                                "{filter: null, pattern: {x: 1}}}}}");
+        assertSolutionExists("{sort: {pattern: {x: 1}, limit: 0, "
+                                "node: {cscan: {dir: 1, filter: {}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CantUseHashedIndexToProvideSort) {
+        addIndex(BSON("x" << "hashed"));
+        runQuerySortProj(BSONObj(), BSON("x" << 1), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 1U);
+        assertSolutionExists("{sort: {pattern: {x: 1}, limit: 0, "
+                                "node: {cscan: {dir: 1, filter: {}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CantUseTextIndexToProvideSort) {
+        addIndex(BSON("x" << 1 << "_fts" << "text" << "_ftsx" << 1));
+        runQuerySortProj(BSONObj(), BSON("x" << 1), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 1U);
+        assertSolutionExists("{sort: {pattern: {x: 1}, limit: 0, "
+                                "node: {cscan: {dir: 1, filter: {}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CantUseNonCompoundGeoIndexToProvideSort) {
+        addIndex(BSON("x" << "2dsphere"));
+        runQuerySortProj(BSONObj(), BSON("x" << 1), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 1U);
+        assertSolutionExists("{sort: {pattern: {x: 1}, limit: 0, "
+                                "node: {cscan: {dir: 1, filter: {}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, CantUseCompoundGeoIndexToProvideSort) {
+        addIndex(BSON("x" << 1 << "y" << "2dsphere"));
+        runQuerySortProj(BSONObj(), BSON("x" << 1), BSONObj());
+
+        ASSERT_EQUALS(getNumSolutions(), 1U);
+        assertSolutionExists("{sort: {pattern: {x: 1}, limit: 0, "
+                                "node: {cscan: {dir: 1, filter: {}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, BasicSortWithIndexablePred) {
         addIndex(BSON("a" << 1));
         addIndex(BSON("b" << 1));
         runQuerySortProj(fromjson("{ a : 5 }"), BSON("b" << 1), BSONObj());
@@ -2285,7 +2332,10 @@ namespace {
                                 "{ixscan: {filter: null, pattern: {b: 1, c: 1}}}]}}}}");
     }
 
-    // SERVER-10801
+    // Test that a 2dsphere index can satisfy a whole index scan solution if the query has a GEO
+    // predicate on at least one of the indexed geo fields.
+    // Currently fails.  Tracked by SERVER-10801.
+    /*
     TEST_F(QueryPlannerTest, SortOnGeoQuery) {
         addIndex(BSON("timestamp" << -1 << "position" << "2dsphere"));
         BSONObj query = fromjson("{position: {$geoWithin: {$geometry: {type: \"Polygon\", coordinates: [[[1, 1], [1, 90], [180, 90], [180, 1], [1, 1]]]}}}}");
@@ -2298,7 +2348,6 @@ namespace {
         assertSolutionExists("{fetch: {node: {ixscan: {pattern: {timestamp: -1, position: '2dsphere'}}}}}");
     }
 
-    // SERVER-10801
     TEST_F(QueryPlannerTest, SortOnGeoQueryMultikey) {
         // true means multikey
         addIndex(BSON("timestamp" << -1 << "position" << "2dsphere"), true);
@@ -2313,6 +2362,7 @@ namespace {
         assertSolutionExists("{fetch: {node: {ixscan: {pattern: "
                                 "{timestamp: -1, position: '2dsphere'}}}}}");
     }
+    */
 
     // SERVER-9257
     TEST_F(QueryPlannerTest, CompoundGeoNoGeoPredicate) {