SERVER-12939 prefer non-blocking sort plans when no plans produce or hit EOF

2 files changed, 62 insertions, 10 deletions

diff --git a/src/mongo/db/query/plan_ranker.cpp b/src/mongo/db/query/plan_ranker.cpp
index 84884db9bdb..af110dcdefc 100644
--- a/src/mongo/db/query/plan_ranker.cpp
+++ b/src/mongo/db/query/plan_ranker.cpp
@@ -189,17 +189,23 @@ namespace mongo {
         double productivity = static_cast<double>(stats->common.advanced)
                             / static_cast<double>(workUnits);
 
-        // If we have to perform a fetch, that's not great.
+        // Just enough to break a tie.
+        static const double epsilon = 0.0001;
+
+        // We prefer covered projections.
         //
         // We only do this when we have a projection stage because we have so many jstests that
         // check bounds even when a collscan plan is just as good as the ixscan'd plan :(
-        double noFetchBonus = 1;
-        double epsilon = 0.001;
-
-        // We prefer covered projections.
+        double noFetchBonus = epsilon;
         if (hasStage(STAGE_PROJECTION, stats) && hasStage(STAGE_FETCH, stats)) {
-            // Just enough to break a tie.
-            noFetchBonus = 1 - epsilon;
+            noFetchBonus = 0;
+        }
+
+        // In the case of ties, prefer solutions without a blocking sort
+        // to solutions with a blocking sort.
+        double noSortBonus = epsilon;
+        if (hasStage(STAGE_SORT, stats)) {
+            noSortBonus = 0;
         }
 
         // In the case of ties, prefer single index solutions to ixisect. Index
@@ -216,7 +222,8 @@ namespace mongo {
             noIxisectBonus = 0;
         }
 
-        double score = baseScore + productivity + noFetchBonus + noIxisectBonus;
+        double tieBreakers = noFetchBonus + noSortBonus + noIxisectBonus;
+        double score = baseScore + productivity + tieBreakers;
 
         QLOG() << "score (" << score << ") = baseScore(" << baseScore << ")"
                                      <<  " + productivity((" << stats->common.advanced
@@ -226,8 +233,13 @@ namespace mongo {
                                                              << stats->common.needFetch
                                                              << " needFetch) = "
                                                              << productivity << ")"
-                                     <<  " + noFetchBonus(" << noFetchBonus << ")"
-                                     <<  " + noIxisectBonus(" << noIxisectBonus << ")"
+                                     <<  " + tieBreakers(" << noFetchBonus
+                                                           << " noFetchBonus + "
+                                                           << noSortBonus
+                                                           << " noSortBonus + "
+                                                           << noIxisectBonus
+                                                           << " noIxisectBonus = "
+                                                           << tieBreakers << ")"
                                      << endl;
 
         if (forceIntersectionPlans) {
diff --git a/src/mongo/dbtests/plan_ranking.cpp b/src/mongo/dbtests/plan_ranking.cpp
index 5d15a00fd45..1be5d0ad9d0 100644
--- a/src/mongo/dbtests/plan_ranking.cpp
+++ b/src/mongo/dbtests/plan_ranking.cpp
@@ -700,6 +700,45 @@ namespace PlanRankingTests {
         }
     };
 
+    /**
+     * When no other information is available, prefer solutions without
+     * a blocking sort stage.
+     */
+    class PlanRankingAvoidBlockingSort : public PlanRankingTestBase {
+    public:
+        void run() {
+            static const int N = 10000;
+
+            for (int i = 0; i < N; ++i) {
+                insert(BSON("a" << 1 << "d" << i));
+            }
+
+            // The index {d: 1, e: 1} provides the desired sort order,
+            // while index {a: 1, b: 1} can be used to answer the
+            // query predicate, but does not provide the sort.
+            addIndex(BSON("a" << 1 << "b" << 1));
+            addIndex(BSON("d" << 1 << "e" << 1));
+
+            // Query: find({a: 1}).sort({d: 1})
+            CanonicalQuery* cq;
+            ASSERT(CanonicalQuery::canonicalize(ns,
+                                                BSON("a" << 1),
+                                                BSON("d" << 1), // sort
+                                                BSONObj(), // projection
+                                                &cq).isOK());
+            ASSERT(NULL != cq);
+
+            // No results will be returned during the trial period,
+            // so we expect to choose {d: 1, e: 1}, as it allows us
+            // to avoid the sort stage.
+            QuerySolution* soln = pickBestPlan(cq);
+            ASSERT(QueryPlannerTestLib::solutionMatches(
+                        "{fetch: {filter: {a:1}, node: "
+                            "{ixscan: {filter: null, pattern: {d:1,e:1}}}}}",
+                        soln->root.get()));
+        }
+    };
+
     class All : public Suite {
     public:
         All() : Suite( "query_plan_ranking" ) {}
@@ -718,6 +757,7 @@ namespace PlanRankingTests {
             add<PlanRankingNonCoveredIxisectFetchesLess>();
             add<PlanRankingIxisectHitsEOFFirst>();
             add<PlanRankingChooseBetweenIxisectPlans>();
+            add<PlanRankingAvoidBlockingSort>();
         }
     } planRankingAll;