SERVER-8067 do not use sparse index to provide sort order

8 files changed, 117 insertions, 10 deletions

diff --git a/jstests/index_sparse1.js b/jstests/index_sparse1.js
index f2805b3a793..eab3c7fec95 100644
--- a/jstests/index_sparse1.js
+++ b/jstests/index_sparse1.js
@@ -19,7 +19,7 @@ assert.eq( 1 , t.getIndexes().length , "B3" )
 
 t.ensureIndex( { x : 1 } , { sparse : 1 } )
 assert.eq( 2 , t.getIndexes().length , "C1" )
-assert.eq( 3 , t.find().sort( { x : 1 } ).itcount() , "C2" )
+assert.eq( 5 , t.find().sort( { x : 1 } ).itcount() , "C2" )
 t.dropIndex( { x : 1 } )
 assert.eq( 1 , t.getIndexes().length , "C3" )
 
diff --git a/jstests/index_sparse2.js b/jstests/index_sparse2.js
index 2b16c9d0627..56a59db3711 100644
--- a/jstests/index_sparse2.js
+++ b/jstests/index_sparse2.js
@@ -7,13 +7,15 @@ t.insert( { _id : 3 } )
 
 t.ensureIndex( { x : 1 , y : 1 } )
 assert.eq( 2 , t.getIndexes().length , "A1" )
-assert.eq( 3 , t.find().sort( { x : 1 , y : 1 } ).itcount() , "A2" )
+assert.eq( 3 , t.find().sort( { x : 1 , y : 1 } ).count() , "A2 count()" )
+assert.eq( 3 , t.find().sort( { x : 1 , y : 1 } ).itcount() , "A2 itcount()" )
 t.dropIndex( { x : 1 , y : 1 } )
 assert.eq( 1 , t.getIndexes().length , "A3" )
 
 t.ensureIndex( { x : 1 , y : 1 } , { sparse : 1 }  )
 assert.eq( 2 , t.getIndexes().length , "B1" )
-assert.eq( 2 , t.find().sort( { x : 1 , y : 1 } ).itcount() , "B2" )
+assert.eq( 3 , t.find().sort( { x : 1 , y : 1 } ).count() , "B2 count()" )
+assert.eq( 3 , t.find().sort( { x : 1 , y : 1 } ).itcount() , "B2 itcount()" )
 t.dropIndex( { x : 1 , y : 1 } )
 assert.eq( 1 , t.getIndexes().length , "B3" )
 
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index 200481d6ace..cda8a4eb2a1 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -74,10 +74,21 @@ namespace mongo {
                                         const BSONObj& sort, const BSONObj& proj,
                                         long long skip, long long limit,
                                         CanonicalQuery** out) {
+        BSONObj emptyObj;
+        return CanonicalQuery::canonicalize(ns, query, sort, proj, skip, limit, emptyObj, out);
+    }
+
+    // static
+    Status CanonicalQuery::canonicalize(const string& ns, const BSONObj& query,
+                                        const BSONObj& sort, const BSONObj& proj,
+                                        long long skip, long long limit,
+                                        const BSONObj& hint,
+                                        CanonicalQuery** out) {
         LiteParsedQuery* lpq;
         // Pass empty sort and projection.
         BSONObj emptyObj;
-        Status parseStatus = LiteParsedQuery::make(ns, skip, limit, 0, query, proj, sort, &lpq);
+        Status parseStatus = LiteParsedQuery::make(ns, skip, limit, 0, query, proj, sort,
+                                                   hint, &lpq);
         if (!parseStatus.isOK()) { return parseStatus; }
 
         auto_ptr<CanonicalQuery> cq(new CanonicalQuery());
diff --git a/src/mongo/db/query/canonical_query.h b/src/mongo/db/query/canonical_query.h
index 915138fff05..2ddcb3e56c2 100644
--- a/src/mongo/db/query/canonical_query.h
+++ b/src/mongo/db/query/canonical_query.h
@@ -53,7 +53,14 @@ namespace mongo {
                                    const BSONObj& proj, CanonicalQuery** out);
 
         static Status canonicalize(const string& ns, const BSONObj& query, const BSONObj& sort,
-                                   const BSONObj& proj, long long skip, long long limit,
+                                   const BSONObj& proj,
+                                   long long skip, long long limit,
+                                   CanonicalQuery** out);
+
+        static Status canonicalize(const string& ns, const BSONObj& query, const BSONObj& sort,
+                                   const BSONObj& proj,
+                                   long long skip, long long limit,
+                                   const BSONObj& hint,
                                    CanonicalQuery** out);
 
         // What namespace is this query over?
diff --git a/src/mongo/db/query/lite_parsed_query.cpp b/src/mongo/db/query/lite_parsed_query.cpp
index 2a46f4a7c4a..a9da482b520 100644
--- a/src/mongo/db/query/lite_parsed_query.cpp
+++ b/src/mongo/db/query/lite_parsed_query.cpp
@@ -39,9 +39,11 @@ namespace mongo {
     // static
     Status LiteParsedQuery::make(const string& ns, int ntoskip, int ntoreturn, int queryOptions,
                                  const BSONObj& query, const BSONObj& proj, const BSONObj& sort,
+                                 const BSONObj& hint,
                                  LiteParsedQuery** out) {
         auto_ptr<LiteParsedQuery> pq(new LiteParsedQuery());
         pq->_sort = sort;
+        pq->_hint = hint;
 
         Status status = pq->init(ns, ntoskip, ntoreturn, queryOptions, query, proj, false);
         if (status.isOK()) { *out = pq.release(); }
diff --git a/src/mongo/db/query/lite_parsed_query.h b/src/mongo/db/query/lite_parsed_query.h
index bc0c9229d81..74777b563a5 100644
--- a/src/mongo/db/query/lite_parsed_query.h
+++ b/src/mongo/db/query/lite_parsed_query.h
@@ -47,6 +47,7 @@ namespace mongo {
                            const BSONObj& query,
                            const BSONObj& proj,
                            const BSONObj& sort,
+                           const BSONObj& hint,
                            LiteParsedQuery** out);
 
         /**
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 90d78c3d1a3..76d67bbf62f 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -480,7 +480,11 @@ namespace mongo {
 
             if (!usingIndexToSort) {
                 for (size_t i = 0; i < params.indices.size(); ++i) {
-                    const BSONObj& kp = params.indices[i].keyPattern;
+                    const IndexEntry& index = params.indices[i];
+                    if (index.sparse) {
+                        continue;
+                    }
+                    const BSONObj& kp = index.keyPattern;
                     if (providesSort(query, kp)) {
                         QLOG() << "Planner: outputting soln that uses index to provide sort."
                                << endl;
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index c07de307b34..e1385a35f1a 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -30,6 +30,8 @@
  * This file contains tests for mongo/db/query/query_planner.cpp
  */
 
+#include <ostream>
+#include <sstream>
 #include "mongo/db/jsobj.h"
 #include "mongo/db/json.h"
 #include "mongo/db/matcher/expression_parser.h"
@@ -110,8 +112,19 @@ namespace {
         void runQuerySortProjSkipLimit(const BSONObj& query,
                                        const BSONObj& sort, const BSONObj& proj,
                                        long long skip, long long limit) {
+            runQueryFull(query, sort, proj, skip, limit, BSONObj());
+        }
+
+        void runQuerySortHint(const BSONObj& query, const BSONObj& sort, const BSONObj& hint) {
+            runQueryFull(query, sort, BSONObj(), 0, 0, hint);
+        }
+
+        void runQueryFull(const BSONObj& query,
+                          const BSONObj& sort, const BSONObj& proj,
+                          long long skip, long long limit,
+                          const BSONObj& hint) {
             solns.clear();
-            Status s = CanonicalQuery::canonicalize(ns, query, sort, proj, skip, limit, &cq);
+            Status s = CanonicalQuery::canonicalize(ns, query, sort, proj, skip, limit, hint, &cq);
             if (!s.isOK()) { cq = NULL; }
             ASSERT_OK(s);
             params.options = QueryPlannerParams::INCLUDE_COLLSCAN;
@@ -126,14 +139,33 @@ namespace {
             return solns.size();
         }
 
-        void dumpSolutions() const {
+        void dumpSolutions(ostream& ost) const {
             for (vector<QuerySolution*>::const_iterator it = solns.begin();
                     it != solns.end();
                     ++it) {
-                cout << (*it)->toString() << endl;
+                ost << (*it)->toString() << endl;
             }
         }
 
+        void dumpSolutions() const {
+            dumpSolutions(std::cout);
+        }
+
+        /**
+         * Checks number solutions. Generates assertion message
+         * containing solution dump if applicable.
+         */
+        void assertNumSolutions(size_t expectSolutions) const {
+            if (getNumSolutions() == expectSolutions) {
+                return;
+            }
+            std::stringstream ss;
+            ss << "expected " << expectSolutions << " solutions but got " << getNumSolutions()
+               << " instead. solutions generated: " << std::endl;
+            dumpSolutions(ss);
+            FAIL(ss.str());
+        }
+
         /**
          * Looks in the children stored in the 'nodes' field of 'testSoln'
          * to see if they match the 'children' field of 'trueSoln'.
@@ -314,7 +346,15 @@ namespace {
                     ++matches;
                 }
             }
-            ASSERT_EQUALS(matches, expectMatches);
+            if (matches == expectMatches) {
+                return;
+            }
+            std::stringstream ss;
+            ss << "expected " << expectMatches << " matches for solution " << solnJson
+               << " but got " << matches
+               << " instead. all solutions generated: " << std::endl;
+            dumpSolutions(ss);
+            FAIL(ss.str());
         }
 
         // TODO:
@@ -1007,6 +1047,46 @@ namespace {
         assertSolutionExists("{fetch: {ixscan: {_id: 1}}}");
     }
 
+    //
+    // Sparse indices, SERVER-8067
+    // Each index in this block of tests is sparse.
+    //
+
+    TEST_F(IndexAssignmentTest, SparseIndexIgnoreForSort) {
+        addIndex(fromjson("{a: 1}"), false, true);
+        runQuerySortProj(BSONObj(), fromjson("{a: 1}"), BSONObj());
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{sort: {pattern: {a: 1}, node: {cscan: 1}}}");
+    }
+
+    TEST_F(IndexAssignmentTest, SparseIndexHintForSort) {
+        addIndex(fromjson("{a: 1}"), false, true);
+        runQuerySortHint(BSONObj(), fromjson("{a: 1}"), fromjson("{a: 1}"));
+
+        assertNumSolutions(1U);
+        assertSolutionExists("{fetch: {ixscan: {a: 1}}}");
+    }
+
+    TEST_F(IndexAssignmentTest, SparseIndexPreferCompoundIndexForSort) {
+        addIndex(fromjson("{a: 1}"), false, true);
+        addIndex(fromjson("{a: 1, b: 1}"));
+        runQuerySortProj(BSONObj(), fromjson("{a: 1}"), BSONObj());
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{sort: {pattern: {a: 1}, node: {cscan: 1}}}");
+        assertSolutionExists("{fetch: {ixscan: {a: 1, b: 1}}}");
+    }
+
+    TEST_F(IndexAssignmentTest, SparseIndexForQuery) {
+        addIndex(fromjson("{a: 1}"), false, true);
+        runQuerySortProj(fromjson("{a: 1}"), BSONObj(), BSONObj());
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: 1}");
+        assertSolutionExists("{fetch: {ixscan: {a: 1}}}");
+    }
+
     // STOPPED HERE - need to hook up machinery for multiple indexed predicates
     //                second is not working (until the machinery is in place)
     //