SERVER-41279 Eliminate failed plans from consideration during query planning

8 files changed, 98 insertions, 37 deletions

diff --git a/src/mongo/db/commands/plan_cache_commands.cpp b/src/mongo/db/commands/plan_cache_commands.cpp
index fff1ec0905d..4fc13e65c6a 100644
--- a/src/mongo/db/commands/plan_cache_commands.cpp
+++ b/src/mongo/db/commands/plan_cache_commands.cpp
@@ -390,7 +390,9 @@ Status listPlansOriginalFormat(std::unique_ptr<CanonicalQuery> cq,
 
     size_t numPlans = entry->plannerData.size();
     invariant(numPlans == entry->decision->stats.size());
-    invariant(numPlans == entry->decision->scores.size());
+    invariant(numPlans ==
+              entry->decision->scores.size() + entry->decision->failedCandidates.size());
+    invariant(entry->decision->candidateOrder.size() == entry->decision->scores.size());
     for (size_t i = 0; i < numPlans; ++i) {
         BSONObjBuilder planBob(plansBuilder.subobjStart());
 
@@ -404,7 +406,12 @@ Status listPlansOriginalFormat(std::unique_ptr<CanonicalQuery> cq,
         // reason is comprised of score and initial stats provided by
         // multi plan runner.
         BSONObjBuilder reasonBob(planBob.subobjStart("reason"));
-        reasonBob.append("score", entry->decision->scores[i]);
+        if (i < entry->decision->candidateOrder.size()) {
+            reasonBob.append("score", entry->decision->scores[i]);
+        } else {
+            reasonBob.append("score", 0.0);
+            reasonBob.append("failed", true);
+        }
         BSONObjBuilder statsBob(reasonBob.subobjStart("stats"));
         PlanStageStats* stats = entry->decision->stats[i].get();
         if (stats) {
diff --git a/src/mongo/db/exec/multi_plan.cpp b/src/mongo/db/exec/multi_plan.cpp
index fa5a3ded422..9cb692efa55 100644
--- a/src/mongo/db/exec/multi_plan.cpp
+++ b/src/mongo/db/exec/multi_plan.cpp
@@ -219,13 +219,23 @@ Status MultiPlanStage::pickBestPlan(PlanYieldPolicy* yieldPolicy) {
 
     // After picking best plan, ranking will own plan stats from
     // candidate solutions (winner and losers).
-    std::unique_ptr<PlanRankingDecision> ranking(new PlanRankingDecision);
-    _bestPlanIdx = PlanRanker::pickBestPlan(_candidates, ranking.get());
+    auto statusWithRanking = PlanRanker::pickBestPlan(_candidates);
+    if (!statusWithRanking.isOK()) {
+        return statusWithRanking.getStatus();
+    }
+
+    auto ranking = std::move(statusWithRanking.getValue());
+    // Since the status was ok there should be a ranking containing at least one successfully ranked
+    // plan.
+    invariant(ranking);
+    _bestPlanIdx = ranking->candidateOrder[0];
+
     verify(_bestPlanIdx >= 0 && _bestPlanIdx < static_cast<int>(_candidates.size()));
 
-    // Copy candidate order. We will need this to sort candidate stats for explain
-    // after transferring ownership of 'ranking' to plan cache.
+    // Copy candidate order and failed candidates. We will need this to sort candidate stats for
+    // explain after transferring ownership of 'ranking' to plan cache.
     std::vector<size_t> candidateOrder = ranking->candidateOrder;
+    std::vector<size_t> failedCandidates = ranking->failedCandidates;
 
     CandidatePlan& bestCandidate = _candidates[_bestPlanIdx];
     const auto& alreadyProduced = bestCandidate.results;
@@ -237,7 +247,7 @@ Status MultiPlanStage::pickBestPlan(PlanYieldPolicy* yieldPolicy) {
     _backupPlanIdx = kNoSuchPlan;
     if (bestSolution->hasBlockingStage && (0 == alreadyProduced.size())) {
         LOG(5) << "Winner has blocking stage, looking for backup plan...";
-        for (size_t ix = 0; ix < _candidates.size(); ++ix) {
+        for (auto&& ix : candidateOrder) {
             if (!_candidates[ix].solution->hasBlockingStage) {
                 LOG(5) << "Candidate " << ix << " is backup child";
                 _backupPlanIdx = ix;
@@ -296,9 +306,11 @@ Status MultiPlanStage::pickBestPlan(PlanYieldPolicy* yieldPolicy) {
         std::vector<QuerySolution*> solutions;
 
         // Generate solutions and ranking decisions sorted by score.
-        for (size_t orderingIndex = 0; orderingIndex < candidateOrder.size(); ++orderingIndex) {
-            // index into candidates/ranking
-            size_t ix = candidateOrder[orderingIndex];
+        for (auto&& ix : candidateOrder) {
+            solutions.push_back(_candidates[ix].solution.get());
+        }
+        // Insert the failed plans in the back.
+        for (auto&& ix : failedCandidates) {
             solutions.push_back(_candidates[ix].solution.get());
         }
 
diff --git a/src/mongo/db/exec/plan_stage.cpp b/src/mongo/db/exec/plan_stage.cpp
index e94807676e8..06ae012db86 100644
--- a/src/mongo/db/exec/plan_stage.cpp
+++ b/src/mongo/db/exec/plan_stage.cpp
@@ -52,6 +52,8 @@ PlanStage::StageState PlanStage::work(WorkingSetID* out) {
         ++_commonStats.needTime;
     } else if (StageState::NEED_YIELD == workResult) {
         ++_commonStats.needYield;
+    } else if (StageState::FAILURE == workResult) {
+        _commonStats.failed = true;
     }
 
     return workResult;
diff --git a/src/mongo/db/exec/plan_stats.h b/src/mongo/db/exec/plan_stats.h
index 35f4c334eb2..e85a508979f 100644
--- a/src/mongo/db/exec/plan_stats.h
+++ b/src/mongo/db/exec/plan_stats.h
@@ -64,6 +64,7 @@ struct CommonStats {
           needTime(0),
           needYield(0),
           executionTimeMillis(0),
+          failed(false),
           isEOF(false) {}
     // String giving the type of the stage. Not owned.
     const char* stageTypeStr;
@@ -93,6 +94,7 @@ struct CommonStats {
 
     // TODO: keep track of the total yield time / fetch time done for a plan.
 
+    bool failed;
     bool isEOF;
 
 private:
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,