diff options
author | samontea <merciers.merciers@gmail.com> | 2019-05-31 14:05:37 -0400 |
---|---|---|
committer | samontea <merciers.merciers@gmail.com> | 2019-07-10 16:07:42 -0400 |
commit | 6bba6446e632b557ccc03834d4d48e90336679fc (patch) | |
tree | 8f550393c99b15f4b27d9bbb27115fc451930be7 | |
parent | 0434f018920206c197ab06b96e1a74dcbdf8885a (diff) | |
download | mongo-6bba6446e632b557ccc03834d4d48e90336679fc.tar.gz |
SERVER-41279 Eliminate failed plans from consideration during query planning
-rw-r--r-- | jstests/noPassthrough/plan_cache_list_failed_plans.js | 37 | ||||
-rw-r--r-- | jstests/noPassthrough/plan_cache_list_plans_new_format.js | 28 | ||||
-rw-r--r-- | src/mongo/db/commands/plan_cache_commands.cpp | 11 | ||||
-rw-r--r-- | src/mongo/db/exec/multi_plan.cpp | 28 | ||||
-rw-r--r-- | src/mongo/db/exec/plan_stage.cpp | 2 | ||||
-rw-r--r-- | src/mongo/db/exec/plan_stats.h | 2 | ||||
-rw-r--r-- | src/mongo/db/query/explain.cpp | 9 | ||||
-rw-r--r-- | src/mongo/db/query/plan_cache.cpp | 10 | ||||
-rw-r--r-- | src/mongo/db/query/plan_ranker.cpp | 52 | ||||
-rw-r--r-- | src/mongo/db/query/plan_ranker.h | 21 | ||||
-rw-r--r-- | src/mongo/dbtests/plan_ranking.cpp | 83 |
11 files changed, 246 insertions, 37 deletions
diff --git a/jstests/noPassthrough/plan_cache_list_failed_plans.js b/jstests/noPassthrough/plan_cache_list_failed_plans.js new file mode 100644 index 00000000000..96eea6ab27b --- /dev/null +++ b/jstests/noPassthrough/plan_cache_list_failed_plans.js @@ -0,0 +1,37 @@ +// Confirms the planCacheListPlans output format includes information about failed plans. +(function() { + "use strict"; + + const conn = MongoRunner.runMongod(); + assert.neq(null, conn, "mongod was unable to start up"); + const testDB = conn.getDB("jstests_plan_cache_list_failed_plans"); + const coll = testDB.test; + + coll.drop(); + + // Setup the database such that it will generate a failing plan and a succeeding plan. + const numDocs = 32; + const smallNumber = 10; + assert.commandWorked( + testDB.adminCommand({setParameter: 1, internalQueryExecMaxBlockingSortBytes: smallNumber})); + for (let i = 0; i < numDocs * 2; ++i) + assert.commandWorked(coll.insert({a: ((i >= (numDocs * 2) - smallNumber) ? 1 : 0), d: i})); + + // Create the indexes to create competing plans. + assert.commandWorked(coll.createIndex({a: 1})); + assert.commandWorked(coll.createIndex({d: 1})); + + // Assert that the find command found documents. + const key = {query: {a: 1}, sort: {d: 1}, projection: {}}; + assert.eq(smallNumber, coll.find(key.query).sort(key.sort).itcount()); + let res = assert.commandWorked(coll.runCommand("planCacheListPlans", key)); + + // There should have been two plans generated. + assert.eq(res["plans"].length, 2); + // The second plan should fail. + assert.eq(res["plans"][1]["reason"]["failed"], true); + + // The failing plan should have a score of 0. + assert.eq(res["plans"][1]["reason"]["score"], 0); + MongoRunner.stopMongod(conn); +})(); diff --git a/jstests/noPassthrough/plan_cache_list_plans_new_format.js b/jstests/noPassthrough/plan_cache_list_plans_new_format.js index f8f96d56cbf..cd0a7fb0320 100644 --- a/jstests/noPassthrough/plan_cache_list_plans_new_format.js +++ b/jstests/noPassthrough/plan_cache_list_plans_new_format.js @@ -55,5 +55,33 @@ assert.eq(cachedStage, winningExecStage, `Information about the winning plan in "cachedPlan" is inconsistent with the first element in "creationExecStats".`); + // Ensures that the new format preservers information about the failed plans. + assert(coll.drop()); + + // Setup the database such that it will generate a failing plan and a succeeding plan. + const numDocs = 32; + const smallNumber = 10; + assert.commandWorked( + testDB.adminCommand({setParameter: 1, internalQueryExecMaxBlockingSortBytes: smallNumber})); + for (let i = 0; i < numDocs * 2; ++i) + assert.commandWorked(coll.insert({a: ((i >= (numDocs * 2) - smallNumber) ? 1 : 0), d: i})); + + // Create the indexes to create competing plans. + assert.commandWorked(coll.createIndex({a: 1})); + assert.commandWorked(coll.createIndex({d: 1})); + + // Assert that the find command found documents. + key = {query: {a: 1}, sort: {d: 1}, projection: {}}; + assert.eq(smallNumber, coll.find(key.query).sort(key.sort).itcount()); + res = assert.commandWorked(coll.runCommand('planCacheListPlans', key)); + + // There should have been two plans generated. + assert.eq(res["creationExecStats"].length, 2); + + // The second plan should have failed. + assert(res["creationExecStats"][1].failed); + + // The failing plan should have a score of 0. + assert.eq(res["candidatePlanScores"][1], 0); MongoRunner.stopMongod(conn); })(); 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, diff --git a/src/mongo/dbtests/plan_ranking.cpp b/src/mongo/dbtests/plan_ranking.cpp index 4709a63c8bc..21f9deaade6 100644 --- a/src/mongo/dbtests/plan_ranking.cpp +++ b/src/mongo/dbtests/plan_ranking.cpp @@ -60,6 +60,10 @@ extern AtomicWord<bool> internalQueryForceIntersectionPlans; extern AtomicWord<bool> internalQueryPlannerEnableHashIntersection; +extern AtomicWord<int> internalQueryExecMaxBlockingSortBytes; + +extern AtomicWord<int> internalQueryPlanEvaluationMaxResults; + } // namespace mongo namespace PlanRankingTests { @@ -179,6 +183,84 @@ private: }; /** + * Ensures that if a plan fails, but scores higher than a succeeding plan, then the plan which + * doesn't fail is chosen. + */ +class PlanRankingPreferNonFailed : public PlanRankingTestBase { +public: + PlanRankingPreferNonFailed() + : PlanRankingTestBase(), + _internalQueryExecMaxBlockingSortBytes(internalQueryExecMaxBlockingSortBytes.load()), + // We set the max results to decrease the amount of work that is done during the trial + // period. We want it to do less work than there are docs to ensure that no plan reaches + // EOF. + _internalQueryPlanEvaluationMaxResults(internalQueryPlanEvaluationMaxResults.load()) { + internalQueryExecMaxBlockingSortBytes.store(10); + internalQueryPlanEvaluationMaxResults.store(100); + } + + ~PlanRankingPreferNonFailed() { + internalQueryExecMaxBlockingSortBytes.store(_internalQueryExecMaxBlockingSortBytes); + internalQueryPlanEvaluationMaxResults.store(_internalQueryPlanEvaluationMaxResults); + } + + void run() { + // We get the number of works done during the trial period in order to make sure that there + // are more documents in the collection than works done in the trial period. This ensures + // neither of the plans reach EOF or produce results. + size_t numWorks = MultiPlanStage::getTrialPeriodWorks(opCtx(), nullptr); + size_t smallNumber = 10; + // The following condition must be met in order for the following test to work. Specifically + // this condition guarantees that the score of the plan using the index on d will score + // higher than the the plan using the index on a. + ASSERT(smallNumber < numWorks); + for (size_t i = 0; i < numWorks * 2; ++i) { + insert(BSON("a" << static_cast<int>(i >= ((numWorks * 2) - smallNumber)) << "d" + << static_cast<int>(i))); + } + + // The index {a: 1} is what we expect to be used. The index {d: 1} is just to produce a + // competing plan. + addIndex(BSON("a" << 1)); + addIndex(BSON("d" << 1)); + + // Query: find({a: 1}).sort({d: 1}) + auto qr = stdx::make_unique<QueryRequest>(nss); + qr->setFilter(BSON("a" << 1)); + qr->setSort(BSON("d" << 1)); + auto statusWithCQ = CanonicalQuery::canonicalize(opCtx(), std::move(qr)); + ASSERT_OK(statusWithCQ.getStatus()); + unique_ptr<CanonicalQuery> cq = std::move(statusWithCQ.getValue()); + ASSERT(cq); + + QuerySolution* soln = pickBestPlan(cq.get()); + ASSERT( + QueryPlannerTestLib::solutionMatches("{fetch: {filter: {a:1}, node: " + "{ixscan: {filter: null, pattern: {d:1}}}}}", + soln->root.get())); + + AutoGetCollectionForReadCommand ctx(&_opCtx, nss); + Collection* collection = ctx.getCollection(); + + StatusWith<std::unique_ptr<PlanCacheEntry>> planCacheEntryWithStatus = + collection->infoCache()->getPlanCache()->getEntry(*(cq.get())); + ASSERT_OK(planCacheEntryWithStatus.getStatus()); + + // We assert that there was only one plan scored, implying that there was only one + // non-failing plan. + ASSERT(planCacheEntryWithStatus.getValue()->decision->scores.size() == 1); + // We assert that there was one failing plan. + ASSERT(planCacheEntryWithStatus.getValue()->decision->failedCandidates.size() == 1); + } + +private: + // Holds the value of global "internalQueryExecMaxBlockingSortBytes" setParameter flag. + // Restored at end of test invocation regardless of test result. + int _internalQueryExecMaxBlockingSortBytes; + int _internalQueryPlanEvaluationMaxResults; +}; + +/** * Test that the "prefer ixisect" parameter works. */ class PlanRankingIntersectOverride : public PlanRankingTestBase { @@ -622,6 +704,7 @@ public: add<PlanRankingPreferCoveredEvenIfNoResults>(); add<PlanRankingPreferImmediateEOF>(); add<PlanRankingPreferImmediateEOFAgainstHashed>(); + add<PlanRankingPreferNonFailed>(); add<PlanRankingNoCollscan>(); add<PlanRankingCollscan>(); add<PlanRankingAvoidBlockingSort>(); |