SERVER-41279 Eliminate failed plans from consideration during query planning

4 files changed, 65 insertions, 27 deletions

diff --git a/src/mongo/db/query/explain.cpp b/src/mongo/db/query/explain.cpp
index 4f6093959b4..709d8ffda4a 100644
--- a/src/mongo/db/query/explain.cpp
+++ b/src/mongo/db/query/explain.cpp
@@ -331,6 +331,8 @@ void Explain::statsToBSON(const PlanStageStats& stats,
         bob->appendNumber("needYield", stats.common.needYield);
         bob->appendNumber("saveState", stats.common.yields);
         bob->appendNumber("restoreState", stats.common.unyields);
+        if (stats.common.failed)
+            bob->appendBool("failed", stats.common.failed);
         bob->appendNumber("isEOF", stats.common.isEOF);
     }
 
@@ -739,6 +741,8 @@ void Explain::generateSinglePlanExecutionInfo(const PlanStageStats* stats,
 
     out->appendNumber("totalKeysExamined", totalKeysExamined);
     out->appendNumber("totalDocsExamined", totalDocsExamined);
+    if (stats->common.failed)
+        out->appendBool("failed", stats->common.failed);
 
     // Add the tree of stages, with individual execution stats for each stage.
     BSONObjBuilder stagesBob(out->subobjStart("executionStages"));
@@ -1051,6 +1055,11 @@ void Explain::planCacheEntryToBSON(const PlanCacheEntry& entry, BSONObjBuilder*
     for (double score : entry.decision->scores) {
         scoresBuilder.append(score);
     }
+
+    std::for_each(entry.decision->failedCandidates.begin(),
+                  entry.decision->failedCandidates.end(),
+                  [&scoresBuilder](const auto&) { scoresBuilder.append(0.0); });
+
     scoresBuilder.doneFast();
 
     out->append("indexFilterSet", entry.plannerData[0]->indexFilterApplied);
diff --git a/src/mongo/db/query/plan_cache.cpp b/src/mongo/db/query/plan_cache.cpp
index 3464c22a86f..171d227bc32 100644
--- a/src/mongo/db/query/plan_cache.cpp
+++ b/src/mongo/db/query/plan_cache.cpp
@@ -472,13 +472,15 @@ Status PlanCache::set(const CanonicalQuery& query,
         return Status(ErrorCodes::BadValue, "number of stats in decision must match solutions");
     }
 
-    if (why->scores.size() != solns.size()) {
-        return Status(ErrorCodes::BadValue, "number of scores in decision must match solutions");
+    if (why->scores.size() != why->candidateOrder.size()) {
+        return Status(ErrorCodes::BadValue,
+                      "number of scores in decision must match viable candidates");
     }
 
-    if (why->candidateOrder.size() != solns.size()) {
+    if (why->candidateOrder.size() + why->failedCandidates.size() != solns.size()) {
         return Status(ErrorCodes::BadValue,
-                      "candidate ordering entries in decision must match solutions");
+                      "the number of viable candidates plus the number of failed candidates must "
+                      "match the number of solutions");
     }
 
     const auto key = computeKey(query);
diff --git a/src/mongo/db/query/plan_ranker.cpp b/src/mongo/db/query/plan_ranker.cpp
index ff2e636a28a..2970428be3b 100644
--- a/src/mongo/db/query/plan_ranker.cpp
+++ b/src/mongo/db/query/plan_ranker.cpp
@@ -65,10 +65,9 @@ using std::endl;
 using std::vector;
 
 // static
-size_t PlanRanker::pickBestPlan(const vector<CandidatePlan>& candidates, PlanRankingDecision* why) {
+StatusWith<std::unique_ptr<PlanRankingDecision>> PlanRanker::pickBestPlan(
+    const vector<CandidatePlan>& candidates) {
     invariant(!candidates.empty());
-    invariant(why);
-
     // A plan that hits EOF is automatically scored above
     // its peers. If multiple plans hit EOF during the same
     // set of round-robin calls to work(), then all such plans
@@ -89,28 +88,44 @@ size_t PlanRanker::pickBestPlan(const vector<CandidatePlan>& candidates, PlanRan
     // Holds (score, candidateInndex).
     // Used to derive scores and candidate ordering.
     vector<std::pair<double, size_t>> scoresAndCandidateindices;
+    vector<size_t> failed;
 
     // Compute score for each tree.  Record the best.
     for (size_t i = 0; i < statTrees.size(); ++i) {
-        LOG(5) << "Scoring plan " << i << ":" << endl
-               << redact(candidates[i].solution->toString()) << "Stats:\n"
-               << redact(Explain::statsToBSON(*statTrees[i]).jsonString(Strict, true));
-        LOG(2) << "Scoring query plan: " << Explain::getPlanSummary(candidates[i].root)
-               << " planHitEOF=" << statTrees[i]->common.isEOF;
-
-        double score = scoreTree(statTrees[i].get());
-        LOG(5) << "score = " << score;
-        if (statTrees[i]->common.isEOF) {
-            LOG(5) << "Adding +" << eofBonus << " EOF bonus to score.";
-            score += 1;
+        if (!candidates[i].failed) {
+            LOG(5) << "Scoring plan " << i << ":" << endl
+                   << redact(candidates[i].solution->toString()) << "Stats:\n"
+                   << redact(Explain::statsToBSON(*statTrees[i]).jsonString(Strict, true));
+            LOG(2) << "Scoring query plan: " << Explain::getPlanSummary(candidates[i].root)
+                   << " planHitEOF=" << statTrees[i]->common.isEOF;
+
+            double score = scoreTree(statTrees[i].get());
+            LOG(5) << "score = " << score;
+            if (statTrees[i]->common.isEOF) {
+                LOG(5) << "Adding +" << eofBonus << " EOF bonus to score.";
+                score += 1;
+            }
+
+            scoresAndCandidateindices.push_back(std::make_pair(score, i));
+        } else {
+            failed.push_back(i);
+            LOG(2) << "Not scording plan: " << Explain::getPlanSummary(candidates[i].root)
+                   << " because the plan failed.";
         }
-        scoresAndCandidateindices.push_back(std::make_pair(score, i));
+    }
+
+    // If there isn't a viable plan we should error.
+    if (scoresAndCandidateindices.size() == 0U) {
+        return {ErrorCodes::Error(31157),
+                "No viable plan was found because all candidate plans failed."};
     }
 
     // Sort (scores, candidateIndex). Get best child and populate candidate ordering.
     std::stable_sort(
         scoresAndCandidateindices.begin(), scoresAndCandidateindices.end(), scoreComparator);
 
+    auto why = std::make_unique<PlanRankingDecision>();
+
     // Determine whether plans tied for the win.
     if (scoresAndCandidateindices.size() > 1U) {
         double bestScore = scoresAndCandidateindices[0].first;
@@ -124,6 +139,7 @@ size_t PlanRanker::pickBestPlan(const vector<CandidatePlan>& candidates, PlanRan
     why->stats.clear();
     why->scores.clear();
     why->candidateOrder.clear();
+    why->failedCandidates = std::move(failed);
     for (size_t i = 0; i < scoresAndCandidateindices.size(); ++i) {
         double score = scoresAndCandidateindices[i].first;
         size_t candidateIndex = scoresAndCandidateindices[i].second;
@@ -155,9 +171,11 @@ size_t PlanRanker::pickBestPlan(const vector<CandidatePlan>& candidates, PlanRan
         why->scores.push_back(score);
         why->candidateOrder.push_back(candidateIndex);
     }
+    for (auto& i : why->failedCandidates) {
+        why->stats.push_back(std::move(statTrees[i]));
+    }
 
-    size_t bestChild = scoresAndCandidateindices[0].second;
-    return bestChild;
+    return StatusWith<std::unique_ptr<PlanRankingDecision>>(std::move(why));
 }
 
 // TODO: Move this out.  This is a signal for ranking but will become its own complicated
diff --git a/src/mongo/db/query/plan_ranker.h b/src/mongo/db/query/plan_ranker.h
index 20c64e35b82..bb194c69f5f 100644
--- a/src/mongo/db/query/plan_ranker.h
+++ b/src/mongo/db/query/plan_ranker.h
@@ -50,13 +50,14 @@ struct PlanRankingDecision;
 class PlanRanker {
 public:
     /**
-     * Returns index in 'candidates' of which plan is best.
-     * Populates 'why' with information relevant to how each plan fared in the ranking process.
-     * Caller owns pointers in 'why'.
-     * 'candidateOrder' holds indices into candidates ordered by score (winner in first element).
+     * Returns a PlanRankingDecision which has the ranking and the information about the ranking
+     * process with status OK if everything worked. 'candidateOrder' within the PlanRankingDecision
+     * holds indices into candidates ordered by score (winner in first element).
+     *
+     * Returns an error if there was an issue with plan ranking (e.g. there was no viable plan).
      */
-    static size_t pickBestPlan(const std::vector<CandidatePlan>& candidates,
-                               PlanRankingDecision* why);
+    static StatusWith<std::unique_ptr<PlanRankingDecision>> pickBestPlan(
+        const std::vector<CandidatePlan>& candidates);
 
     /**
      * Assign the stats tree a 'goodness' score. The higher the score, the better
@@ -102,6 +103,7 @@ struct PlanRankingDecision {
         }
         decision->scores = scores;
         decision->candidateOrder = candidateOrder;
+        decision->failedCandidates = failedCandidates;
         return decision;
     }
 
@@ -119,8 +121,15 @@ struct PlanRankingDecision {
     // with corresponding cores[0] and stats[0]. Runner-up would be
     // candidates[candidateOrder[1]] followed by
     // candidates[candidateOrder[2]], ...
+    //
+    // Contains only non-failing plans.
     std::vector<size_t> candidateOrder;
 
+    // Contains the list of original plans that failed.
+    //
+    // Like 'candidateOrder', the contents of this array are indicies into the 'candidates' array.
+    std::vector<size_t> failedCandidates;
+
     // Whether two plans tied for the win.
     //
     // Reading this flag is the only reliable way for callers to determine if there was a tie,