From d8a6a927105e9b898d85a5db16ef97f3b24d8c40 Mon Sep 17 00:00:00 2001 From: Charlie Swanson Date: Mon, 2 Nov 2020 16:43:17 -0500 Subject: Revert "SERVER-36393 Add new opt-in $or enumeration order" This reverts commit f95fe9a05da63905e7e8699f61d4a0b2ad67074b. --- src/mongo/db/query/get_executor.cpp | 4 - src/mongo/db/query/plan_enumerator.cpp | 189 ++------------- src/mongo/db/query/plan_enumerator.h | 55 +---- src/mongo/db/query/query_knobs.cpp | 2 - src/mongo/db/query/query_knobs.h | 15 -- src/mongo/db/query/query_planner.cpp | 15 +- src/mongo/db/query/query_planner_params.h | 17 -- src/mongo/db/query/query_planner_test.cpp | 389 ------------------------------ src/mongo/db/query/query_solution.cpp | 3 +- 9 files changed, 32 insertions(+), 657 deletions(-) diff --git a/src/mongo/db/query/get_executor.cpp b/src/mongo/db/query/get_executor.cpp index e37208af857..322e3ed5872 100644 --- a/src/mongo/db/query/get_executor.cpp +++ b/src/mongo/db/query/get_executor.cpp @@ -193,10 +193,6 @@ void fillOutPlannerParams(OperationContext* opCtx, plannerParams->options |= QueryPlannerParams::INDEX_INTERSECTION; } - if (internalQueryEnumerationPreferLockstepOrEnumeration.load()) { - plannerParams->options |= QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - } - if (internalQueryPlannerGenerateCoveredWholeIndexScans.load()) { plannerParams->options |= QueryPlannerParams::GENERATE_COVERED_IXSCANS; } diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp index 6f312416722..8bc83286817 100644 --- a/src/mongo/db/query/plan_enumerator.cpp +++ b/src/mongo/db/query/plan_enumerator.cpp @@ -42,10 +42,10 @@ namespace { using namespace mongo; +using std::unique_ptr; using std::endl; using std::set; using std::string; -using std::unique_ptr; using std::vector; std::string getPathPrefix(std::string path) { @@ -259,7 +259,6 @@ PlanEnumerator::PlanEnumerator(const PlanEnumeratorParams& params) : _root(params.root), _indices(params.indices), _ixisect(params.intersect), - _enumerateOrChildrenLockstep(params.enumerateOrChildrenLockstep), _orLimit(params.maxSolutionsPerOr), _intersectLimit(params.maxIntersectPerAnd) {} @@ -320,7 +319,8 @@ string PlanEnumerator::NodeAssignment::toString() const { } ss << "]"; return ss; - } else if (nullptr != orAssignment) { + } else { + verify(NULL != orAssignment); mongoutils::str::stream ss; ss << "ALL OF: [ "; for (size_t i = 0; i < orAssignment->subnodes.size(); ++i) { @@ -328,26 +328,7 @@ string PlanEnumerator::NodeAssignment::toString() const { } ss << "]"; return ss; - } else if (nullptr != lockstepOrAssignment) { - mongoutils::str::stream ss; - ss << "ALL OF (lockstep): {"; - ss << "\n\ttotalEnumerated: " << lockstepOrAssignment->totalEnumerated; - ss << "\n\tsubnodes: [ "; - for (auto&& node : lockstepOrAssignment->subnodes) { - ss << "\n\t\t{"; - ss << "memoId: " << node.memoId << ", "; - ss << "iterationCount: " << node.iterationCount << ", "; - if (node.maxIterCount) { - ss << "maxIterCount: " << node.maxIterCount; - } else { - ss << "maxIterCount: none"; - } - ss << "},"; - } - ss << "\n]"; - return ss; } - MONGO_UNREACHABLE; } PlanEnumerator::MemoID PlanEnumerator::memoIDForNode(MatchExpression* node) { @@ -440,19 +421,11 @@ bool PlanEnumerator::prepMemo(MatchExpression* node, PrepMemoContext context) { NodeAssignment* assign; allocateAssignment(node, &assign, &myMemoID); - if (_enumerateOrChildrenLockstep) { - LockstepOrAssignment* newOrAssign = new LockstepOrAssignment(); - for (size_t i = 0; i < node->numChildren(); ++i) { - newOrAssign->subnodes.push_back({memoIDForNode(node->getChild(i)), 0, boost::none}); - } - assign->lockstepOrAssignment.reset(newOrAssign); - } else { - OrAssignment* orAssignment = new OrAssignment(); - for (size_t i = 0; i < node->numChildren(); ++i) { - orAssignment->subnodes.push_back(memoIDForNode(node->getChild(i))); - } - assign->orAssignment.reset(orAssignment); + OrAssignment* orAssignment = new OrAssignment(); + for (size_t i = 0; i < node->numChildren(); ++i) { + orAssignment->subnodes.push_back(memoIDForNode(node->getChild(i))); } + assign->orAssignment.reset(orAssignment); return true; } else if (Indexability::arrayUsesIndexOnChildren(node)) { // Add each of our children as a subnode. We enumerate through each subnode one at a @@ -1599,12 +1572,7 @@ void PlanEnumerator::tagMemo(size_t id) { for (size_t i = 0; i < oa->subnodes.size(); ++i) { tagMemo(oa->subnodes[i]); } - } else if (nullptr != assign->lockstepOrAssignment) { - LockstepOrAssignment* oa = assign->lockstepOrAssignment.get(); - for (auto&& node : oa->subnodes) { - tagMemo(node.memoId); - } - } else if (nullptr != assign->arrayAssignment) { + } else if (NULL != assign->arrayAssignment) { ArrayAssignment* aa = assign->arrayAssignment.get(); tagMemo(aa->subnodes[aa->counter]); } else if (NULL != assign->andAssignment) { @@ -1647,117 +1615,6 @@ void PlanEnumerator::tagMemo(size_t id) { } } -bool PlanEnumerator::LockstepOrAssignment::allIdentical() const { - const auto firstCounter = subnodes[0].iterationCount; - for (auto&& subnode : subnodes) { - if (subnode.iterationCount != firstCounter) { - return false; - } - } - return true; -} - -bool PlanEnumerator::LockstepOrAssignment::shouldResetBeforeProceeding( - size_t totalEnumerated) const { - if (totalEnumerated == 0 || !exhaustedLockstepIteration) { - return false; - } - - size_t totalPossibleEnumerations = 1; - for (auto&& subnode : subnodes) { - if (!subnode.maxIterCount) { - return false; // Haven't yet looped over this child entirely, not ready yet. - } - totalPossibleEnumerations *= subnode.maxIterCount.get(); - } - - // If we're able to compute a total number expected enumerations, we must have already cycled - // through each of the subnodes at least once. So if we've done that and then iterated all - // possible enumerations, we're about to repeat ourselves. - return totalEnumerated % totalPossibleEnumerations == 0; -} - -bool PlanEnumerator::_nextMemoForLockstepOrAssignment( - PlanEnumerator::LockstepOrAssignment* assignment) { - - if (!assignment->exhaustedLockstepIteration) { - // We have not yet finished advancing all children simultaneously, so we'll loop over - // each child and advance it. - - // Because we're doing things in a special order, we have to be careful to not duplicate - // ourselves. If each child has the same number of alternatives, we will eventually - // "carry" or roll over each child back to the beginning. When this happens, we should - // not return that plan again. - bool everyoneRolledOver = true; - - for (auto&& node : assignment->subnodes) { - ++node.iterationCount; - const bool wrappedAround = nextMemo(node.memoId); - if (wrappedAround) { - node.maxIterCount = node.iterationCount; - node.iterationCount = 0; - // We ran out of "lockstep runway" of sorts. At least one of the subnodes was - // exhausted, so this will be our last time advancing all children in lockstep. - assignment->exhaustedLockstepIteration = true; - } else { - everyoneRolledOver = false; - } - } - // Edge case: if every child has only one option available, we are already finished - // enumerating. - if (assignment->shouldResetBeforeProceeding(assignment->totalEnumerated)) { - assignment->exhaustedLockstepIteration = false; - return true; // We're back at the beginning, no need to reset. - } - if (!everyoneRolledOver) { - // Either there's more lockstep iteration to come, or the subnodes have different - // amounts of options. In either case, we are now in a new enumeration state so just - // return. - return false; - } - // Otherwise we just rolled over and went back to the first enumeration state, so we need to - // keep going to avoid duplicating that state. Fall through to below to start "normal", not - // lockstep iteration. - } - - auto advanceOnce = [this, assignment]() { - for (auto&& node : assignment->subnodes) { - ++node.iterationCount; - const bool wrappedAround = nextMemo(node.memoId); - if (!wrappedAround) { - return; - } - node.maxIterCount = node.iterationCount; - node.iterationCount = 0; - } - }; - advanceOnce(); - while (assignment->allIdentical()) { - // All sub-nodes have the same enumeration state, skip this one since we already did - // it above. This is expected to happen pretty often. For example, if we have two subnodes - // each enumerating two states, we'd expect the order to be: 00, 11 (these two iterated - // above), then 00 (skipped by falling through above after finishing lockstep iteration), - // then 10, 11 (skipped here), 00 (skipped here), then finally 01. - advanceOnce(); - } - - // This special ordering is tricky to reset. Because it iterates the sub nodes in such a - // unique order, it can be difficult to know when it has actually finished iterating. Our - // strategy is just to compute a total and go back to the beginning once we hit that total. - if (!assignment->shouldResetBeforeProceeding(assignment->totalEnumerated)) { - return false; - } - // Reset! - for (auto&& subnode : assignment->subnodes) { - while (!nextMemo(subnode.memoId)) { - // Keep advancing till it rolls over. - } - subnode.iterationCount = 0; - } - assignment->exhaustedLockstepIteration = false; - return true; -} - bool PlanEnumerator::nextMemo(size_t id) { NodeAssignment* assign = _memo[id]; verify(NULL != assign); @@ -1765,18 +1622,16 @@ bool PlanEnumerator::nextMemo(size_t id) { if (NULL != assign->orAssignment) { OrAssignment* oa = assign->orAssignment.get(); - // Limit the number of OR enumerations. + // Limit the number of OR enumerations oa->counter++; if (oa->counter >= _orLimit) { - LOG(1) - << "plan enumerator exceeded threshold for OR enumerations. orEnumerationLimit = " - << _orLimit; return true; } - // OR just walks through telling its children to move forward. + // OR just walks through telling its children to + // move forward. for (size_t i = 0; i < oa->subnodes.size(); ++i) { - // If there's no carry, we just stop. If there's a carry, we move the next child + // If there's no carry, we just stop. If there's a carry, we move the next child // forward. if (!nextMemo(oa->subnodes[i])) { return false; @@ -1784,19 +1639,7 @@ bool PlanEnumerator::nextMemo(size_t id) { } // If we're here, the last subnode had a carry, therefore the OR has a carry. return true; - } else if (nullptr != assign->lockstepOrAssignment) { - LockstepOrAssignment* assignment = assign->lockstepOrAssignment.get(); - - // Limit the number of OR enumerations. - ++assignment->totalEnumerated; - if (assignment->totalEnumerated >= _orLimit) { - LOG(1) - << "plan enumerator exceeded threshold for OR enumerations. orEnumerationLimit = " - << _orLimit; - return true; - } - return _nextMemoForLockstepOrAssignment(assignment); - } else if (nullptr != assign->arrayAssignment) { + } else if (NULL != assign->arrayAssignment) { ArrayAssignment* aa = assign->arrayAssignment.get(); // moving to next on current subnode is OK if (!nextMemo(aa->subnodes[aa->counter])) { @@ -1828,9 +1671,11 @@ bool PlanEnumerator::nextMemo(size_t id) { } aa->counter = 0; return true; - } else { - MONGO_UNREACHABLE; } + + // This shouldn't happen. + verify(0); + return false; } } // namespace mongo diff --git a/src/mongo/db/query/plan_enumerator.h b/src/mongo/db/query/plan_enumerator.h index f5edd281fc9..8b563ed145b 100644 --- a/src/mongo/db/query/plan_enumerator.h +++ b/src/mongo/db/query/plan_enumerator.h @@ -44,16 +44,13 @@ namespace mongo { struct PlanEnumeratorParams { PlanEnumeratorParams() - : maxSolutionsPerOr(internalQueryEnumerationMaxOrSolutions.load()), + : intersect(false), + maxSolutionsPerOr(internalQueryEnumerationMaxOrSolutions.load()), maxIntersectPerAnd(internalQueryEnumerationMaxIntersectPerAnd.load()) {} // Do we provide solutions that use more indices than the minimum required to provide // an indexed solution? - bool intersect = false; - - // Do we enumerate children of an $or in a special order to prioritize solutions which have the - // same assignment on each branch? - bool enumerateOrChildrenLockstep = false; + bool intersect; // Not owned here. MatchExpression* root; @@ -98,13 +95,14 @@ public: Status init(); /** - * Outputs a possible plan. Leaves in the plan are tagged with an index to use. Returns a - * MatchExpression representing a point in the query tree (which can be used to build a - * QuerySolutionNode tree) or nullptr if no more plans will be outputted. While owned by the - * caller, the MatchExpression returned points into data that is owned elsewhere. + * Outputs a possible plan. Leaves in the plan are tagged with an index to use. + * Returns a MatchExpression representing a point in the query tree (which can be + * used to build a QueryAssignment) or nullptr if no more plans will be outputted. + * While owned by the caller, the MatchExpression returned points into data that is + * owned elsewhere. * - * Nodes in 'tree' are tagged with indices that should be used to answer the tagged nodes. Only - * nodes that have a field name (getCategory() != kLogical) will be tagged. + * Nodes in 'tree' are tagged with indices that should be used to answer the tagged nodes. + * Only nodes that have a field name (getCategory() != kLogical) will be tagged. * * The output tree is a clone identical to that used to initialize the enumerator, with tags * added in order to indicate index usage. @@ -227,29 +225,6 @@ private: size_t counter; }; - struct LockstepOrAssignment { - struct PreferFirstSubNode { - MemoID memoId; - size_t iterationCount; - boost::optional maxIterCount; - }; - std::vector subnodes; - - bool exhaustedLockstepIteration = false; - size_t totalEnumerated = 0; - - /** - * Returns true if 'totalEnumerated' matches the total number of expected plans for this - * assignment. - */ - bool shouldResetBeforeProceeding(size_t totalEnumerated) const; - - /** - * Returns true if each sub node is at the same iterationCount. - */ - bool allIdentical() const; - }; - // This is used by AndAssignment and is not an actual assignment. struct OneIndexAssignment { // 'preds[i]' is uses index 'index' at position 'positions[i]' @@ -292,7 +267,6 @@ private: */ struct NodeAssignment { std::unique_ptr orAssignment; - std::unique_ptr lockstepOrAssignment; std::unique_ptr andAssignment; std::unique_ptr arrayAssignment; std::string toString() const; @@ -551,11 +525,6 @@ private: */ MemoID memoIDForNode(MatchExpression* node); - /** - * Helper for advancing the enumeration for a LockstepOrAssignment node. - */ - bool _nextMemoForLockstepOrAssignment(LockstepOrAssignment*); - std::string dumpMemo(); // Map from expression to its MemoID. @@ -581,10 +550,6 @@ private: // Do we output >1 index per AND (index intersection)? bool _ixisect; - // Do we enumerate children of an $or in a special order to prioritize solutions which have the - // same assignment on each branch? - bool _enumerateOrChildrenLockstep; - // How many enumerations are we willing to produce from each OR? size_t _orLimit; diff --git a/src/mongo/db/query/query_knobs.cpp b/src/mongo/db/query/query_knobs.cpp index 90788d77bba..9e4a9aa3931 100644 --- a/src/mongo/db/query/query_knobs.cpp +++ b/src/mongo/db/query/query_knobs.cpp @@ -50,8 +50,6 @@ MONGO_EXPORT_SERVER_PARAMETER(internalQueryCacheEvictionRatio, double, 10.0); MONGO_EXPORT_SERVER_PARAMETER(internalQueryPlannerMaxIndexedSolutions, int, 64); -MONGO_EXPORT_SERVER_PARAMETER(internalQueryEnumerationPreferLockstepOrEnumeration, bool, false); - MONGO_EXPORT_SERVER_PARAMETER(internalQueryEnumerationMaxOrSolutions, int, 10); MONGO_EXPORT_SERVER_PARAMETER(internalQueryEnumerationMaxIntersectPerAnd, int, 3); diff --git a/src/mongo/db/query/query_knobs.h b/src/mongo/db/query/query_knobs.h index cc28b097c96..ed4304de4ae 100644 --- a/src/mongo/db/query/query_knobs.h +++ b/src/mongo/db/query/query_knobs.h @@ -81,21 +81,6 @@ extern AtomicDouble internalQueryCacheEvictionRatio; // How many indexed solutions will QueryPlanner::plan output? extern AtomicInt32 internalQueryPlannerMaxIndexedSolutions; -// If set to true, instructs the plan enumerator to enumerate contained $ors in a special order. $or -// enumeration can generate an exponential number of plans, and is therefore limited at some -// arbitrary cutoff controlled by a parameter. When this limit is hit, the order of enumeration is -// important. For example, a query like the following has a 'contained $or' (within an $and): {a: 1, -// $or: [{b: 1, c: 1}, {b: 2, c: 2}]} For this query if there are indexes a_b={a: 1, b: 1} and -// a_c={a: 1, c: 1}, the normal enumeration order would output assignments [a_b, a_b], [a_c, a_b], -// [a_b, a_c], then [a_c, a_c]. This flag will instruct the enumerator to instead prefer a different -// order. It's hard to summarize, but perhaps the phrases 'lockstep enumeration', 'simultaneous -// advancement', or 'parallel iteration' will help the reader. The effect is to give earlier -// enumeration to plans which use the same choice across all branches. In this order, we would get -// assignments [a_b, a_b], [a_c, a_c], [a_c, a_b], then [a_b, a_c]. This is thought to be helpful in -// general, but particularly in cases where all children of the $or use the same fields and have the -// same indexes available, as in this example. -extern AtomicBool internalQueryEnumerationPreferLockstepOrEnumeration; - // How many solutions will the enumerator consider at each OR? extern AtomicInt32 internalQueryEnumerationMaxOrSolutions; diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp index 270a395af93..9de0aec1c73 100644 --- a/src/mongo/db/query/query_planner.cpp +++ b/src/mongo/db/query/query_planner.cpp @@ -58,8 +58,8 @@ namespace mongo { -using std::numeric_limits; using std::unique_ptr; +using std::numeric_limits; namespace dps = ::mongo::dotted_path_support; @@ -137,10 +137,6 @@ string optionString(size_t options) { break; case QueryPlannerParams::TRACK_LATEST_OPLOG_TS: ss << "TRACK_LATEST_OPLOG_TS "; - break; - case QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP: - ss << "ENUMERATE_OR_CHILDREN_LOCKSTEP "; - break; case QueryPlannerParams::DEFAULT: MONGO_UNREACHABLE; break; @@ -867,15 +863,12 @@ Status QueryPlanner::plan(const CanonicalQuery& query, enumParams.intersect = params.options & QueryPlannerParams::INDEX_INTERSECTION; enumParams.root = query.root(); enumParams.indices = &relevantIndices; - enumParams.enumerateOrChildrenLockstep = - params.options & QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - PlanEnumerator planEnumerator(enumParams); - uassertStatusOK(planEnumerator.init()); + PlanEnumerator isp(enumParams); + isp.init().transitional_ignore(); unique_ptr nextTaggedTree; - while ((nextTaggedTree = planEnumerator.getNext()) && - (out->size() < params.maxIndexedSolutions)) { + while ((nextTaggedTree = isp.getNext()) && (out->size() < params.maxIndexedSolutions)) { LOG(5) << "About to build solntree from tagged tree:" << endl << redact(nextTaggedTree->toString()); diff --git a/src/mongo/db/query/query_planner_params.h b/src/mongo/db/query/query_planner_params.h index 806456f0508..4b8a5f54904 100644 --- a/src/mongo/db/query/query_planner_params.h +++ b/src/mongo/db/query/query_planner_params.h @@ -103,23 +103,6 @@ struct QueryPlannerParams { // Set this to track the most recent timestamp seen by this cursor while scanning the oplog. TRACK_LATEST_OPLOG_TS = 1 << 12, - - // Instruct the plan enumerator to enumerate contained $ors in a special order. $or - // enumeration can generate an exponential number of plans, and is therefore limited at some - // arbitrary cutoff controlled by a parameter. When this limit is hit, the order of - // enumeration is important. For example, a query like the following has a "contained $or" - // (within an $and): - // {a: 1, $or: [{b: 1, c: 1}, {b: 2, c: 2}]} - // For this query if there are indexes a_b={a: 1, b: 1} and a_c={a: 1, c: 1}, the normal - // enumeration order would output assignments [a_b, a_b], [a_c, a_b], [a_b, a_c], then [a_c, - // a_c]. This flag will instruct the enumerator to instead prefer a different order. It's - // hard to summarize, but perhaps the phrases "lockstep enumeration", "simultaneous - // advancement", or "parallel iteration" will help the reader. The effect is to give earlier - // enumeration to plans which use the same index of alternative across all branches. In this - // order, we would get assignments [a_b, a_b], [a_c, a_c], [a_c, a_b], then [a_b, a_c]. This - // is thought to be helpful in general, but particularly in cases where all children of the - // $or use the same fields and have the same indexes available, as in this example. - ENUMERATE_OR_CHILDREN_LOCKSTEP = 1 << 13, }; // See Options enum above. diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp index 417081795a6..58645fc9efc 100644 --- a/src/mongo/db/query/query_planner_test.cpp +++ b/src/mongo/db/query/query_planner_test.cpp @@ -5687,395 +5687,6 @@ TEST_F(QueryPlannerTest, SolutionSetStableWhenOrEnumerationLimitIsReached) { "1}}}}}]}}"); } -// Test that we enumerate the expected plans with the special parameter set. In this test we have -// two branches of an $or, each with two possible indexed solutions. -TEST_F(QueryPlannerTest, LockstepOrEnumerationSanityCheckTwoChildrenTwoIndexesEach) { - params.options = - QueryPlannerParams::NO_TABLE_SCAN | QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - addIndex(BSON("a" << 1 << "b" << 1)); - addIndex(BSON("a" << 1 << "c" << 1)); - - runQueryAsCommand( - fromjson("{find: 'testns', filter: {a: 1, $or: [{b: 1, c: 1}, {b: 2, c: 2}]}}")); - - assertNumSolutions(6U); - - assertSolutionExists( - "{or: {nodes: [{fetch: {filter: {c: {$eq: 1} }, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}]}}"); - assertSolutionExists( - "{or: {nodes: [{fetch: {filter: {b: {$eq: 1} }, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}]}}"); - assertSolutionExists( - "{or: {nodes: [{fetch: {filter: {c: {$eq: 1} }, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}]}}"); - assertSolutionExists( - "{or: {nodes: [{fetch: {filter: {b: {$eq: 1} }, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}]}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [{b: {$eq: 1}, c: {$eq: 1}}, {b: {$eq: 2}, c: {$eq: 2}}]}, node: " - "{ixscan: {pattern: {a: 1, b: 1}}}}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [{b: {$eq: 1}, c: {$eq: 1}}, {b: {$eq: 2}, c: {$eq: 2}}]}, node: " - "{ixscan: {pattern: {a: 1, c: 1}}}}}}}"); -} - -// Test that we enumerate the expected plans with the special parameter set. In this test we have -// two branches of an $or, each with one possible indexed solution. -TEST_F(QueryPlannerTest, LockstepOrEnumerationSanityCheckTwoChildrenOneIndexEach) { - params.options = - QueryPlannerParams::NO_TABLE_SCAN | QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - addIndex(BSON("a" << 1 << "b" << 1)); - addIndex(BSON("a" << 1 << "c" << 1)); - - runQueryAsCommand(fromjson("{find: 'testns', filter: {a: 1, $or: [{b: 1}, {c: 2}]}}")); - - assertNumSolutions(3U); - - assertSolutionExists( - "{fetch: {filter: null, node: {or: {nodes: [{ixscan: {pattern: {a: 1, b: 1}}}, {ixscan: " - "{pattern: {a: 1, c: 1}}}]}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [{b: {$eq: 1}}, {c: {$eq: 2}}]}, node: {ixscan: {pattern: {a: 1, " - "b: 1}}}}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [{b: {$eq: 1}}, {c: {$eq: 2}}]}, node: {ixscan: {pattern: {a: 1, " - "c: 1}}}}}}}"); -} - -// Test that we enumerate the expected plans with the special parameter set. In this test we have -// two branches of an $or, one with one possible indexed solution, the other with two possible -// indexed solutions. -TEST_F(QueryPlannerTest, LockstepOrEnumerationSanityCheckTwoChildrenDifferentNumSolutions) { - params.options = - QueryPlannerParams::NO_TABLE_SCAN | QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - addIndex(BSON("a" << 1 << "b" << 1)); - addIndex(BSON("a" << 1 << "c" << 1)); - - runQueryAsCommand(fromjson("{find: 'testns', filter: {a: 1, $or: [{b: 1}, {b: 2, c: 2}]}}")); - - assertNumSolutions(4U); - - assertSolutionExists( - "{fetch: {filter: null, node: {or: {nodes: [{ixscan: {pattern: {a: 1, b: 1}}}, {fetch: " - "{filter: {c: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}]}}}}"); - assertSolutionExists( - "{fetch: {filter: null, node: {or: {nodes: [{ixscan: {pattern: {a: 1, b: 1}}}, {fetch: " - "{filter: {b: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}]}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [{b: {$eq: 1}}, {b: {$eq: 2}, c: {$eq: 2}}]}, node: {ixscan: " - "{pattern: {a: 1, b: 1}}}}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [{b: {$eq: 1}}, {b: {$eq: 2}, c: {$eq: 2}}]}, node: {ixscan: " - "{pattern: {a: 1, c: 1}}}}}}}"); -} - -// Test that the special parameter does in fact impact the order of enumeration. Here we rely on the -// cap of number of or enumerations to prove that the plans we're interested in are enumerated -// before we hit the limit. -TEST_F(QueryPlannerTest, NormalOrEnumerationDoesNotPrioritizeLockstepIteration) { - params.options = QueryPlannerParams::NO_TABLE_SCAN; - ASSERT_EQ(internalQueryEnumerationMaxOrSolutions.load(), 10); - addIndex(BSON("a" << 1 << "b" << 1)); - addIndex(BSON("a" << 1 << "c" << 1)); - addIndex(BSON("a" << 1 << "d" << 1)); - - // For this query and the above indexes, each clause of the $or has three options to choose - // from, for a total of 3 * 3 * 3 = 27 possible enumerations for just that $or sub-branch. - runQueryAsCommand( - fromjson("{find: 'testns', filter: {a: 1, $or: [{b: 1, c: 1, d: 1}, {b: 2, c: 2, d: 2}, " - "{b: 3, c: 3, d: 3}]}}")); - - // The $or enumeration is limited to 10, and then we have three plans where just the {a: 1} - // predicate is indexed. - assertNumSolutions(13U); - - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {c: {$eq: 1}, d: {$eq: 1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2}, d: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}} " - "]}}"); - // Because we did not set the 'ENUMERATE_OR_CHILDREN_LOCKSTEP' flag, we don't expect this - // solution to be generated. This is in contrast to the next test case. - ASSERT_THROWS( - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 1}, c: {$eq: 1}}, node: {ixscan: {pattern: {a: 1, d: " - "1}}}}}, " - "{fetch: {filter: {b: {$eq: 2}, c: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, d: " - "1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, c: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, d: " - "1}}}}} " - "]}}"), - unittest::TestAssertionFailureException); - - // We still expect to generate the solutions which don't index the $or. - assertSolutionExists( - "{fetch: {filter: {$or: [" - "{b: {$eq: 1}, c: {$eq: 1}, d: {$eq: 1}}, " - "{b: {$eq: 2}, c: {$eq: 2}, d: {$eq: 2}}, " - "{b: {$eq: 3}, c: {$eq: 3}, d: {$eq: 3}} " - "]}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}}"); -} - -TEST_F(QueryPlannerTest, LockstepOrEnumerationDoesPrioritizeLockstepIteration) { - params.options = - QueryPlannerParams::NO_TABLE_SCAN | QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - ASSERT_EQ(internalQueryEnumerationMaxOrSolutions.load(), 10); - addIndex(BSON("a" << 1 << "b" << 1)); - addIndex(BSON("a" << 1 << "c" << 1)); - addIndex(BSON("a" << 1 << "d" << 1)); - - // For this query and the above indexes, each clause of the $or has three options to choose - // from, for a total of 3 * 3 * 3 = 27 possible enumerations for just that $or sub-branch. - runQueryAsCommand( - fromjson("{find: 'testns', filter: {a: 1, $or: [{b: 1, c: 1, d: 1}, {b: 2, c: 2, d: 2}, " - "{b: 3, c: 3, d: 3}]}}")); - - // The $or enumeration is limited to 10, and then we have three plans where just the {a: 1} - // predicate is indexed. - assertNumSolutions(13U); - - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {c: {$eq: 1}, d: {$eq: 1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2}, d: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}} " - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 1}, d: {$eq: 1}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2}, d: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}} " - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 1}, c: {$eq: 1}}, node: {ixscan: {pattern: {a: 1, d: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2}, c: {$eq: 2}}, node: {ixscan: {pattern: {a: 1, d: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, c: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, d: 1}}}}} " - "]}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [" - "{b: {$eq: 1}, c: {$eq: 1}, d: {$eq: 1}}, " - "{b: {$eq: 2}, c: {$eq: 2}, d: {$eq: 2}}, " - "{b: {$eq: 3}, c: {$eq: 3}, d: {$eq: 3}} " - "]}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}}"); -} - -TEST_F(QueryPlannerTest, LockstepOrEnumerationDoesPrioritizeLockstepIterationMixedChildren) { - params.options = - QueryPlannerParams::NO_TABLE_SCAN | QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - ASSERT_EQ(internalQueryEnumerationMaxOrSolutions.load(), 10); - addIndex(BSON("a" << 1 << "b" << 1)); - addIndex(BSON("a" << 1 << "c" << 1)); - addIndex(BSON("a" << 1 << "d" << 1)); - addIndex(BSON("a" << 1 << "e" << 1)); - - // For this query and the above indexes, each clause of the $or has a varying number options to - // choose from, for a total of 2 * 3 * 4 * 2 = 48 possible enumerations for just that $or - // sub-branch. - runQueryAsCommand( - fromjson("{find: 'testns', filter: {" - " a: 1," - " $or: [" - " {b: 2.1, c: 2.1}," - " {b: 3, c: 3, d: 3}," - " {b: 4, c: 4, d: 4, e: 4}," - " {b: 2.2, c: 2.2}" - "]}}")); - - // The $or enumeration is limited to 10, and then we have four plans where just the {a: 1} - // predicate is indexed. - assertNumSolutions(14U); - - // Lockstep enumerations. Definitely expected. - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {c: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 4}, d: {$eq: 4}, e: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, d: {$eq: 4}, e: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}" - "]}}"); - // Everyone advances one more time, no longer lock step. - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {c: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, c: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, d: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, e: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, d: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}" - "]}}"); - // Normal enumeration. Here we observe an interesting phenomena. Before we get into plan - // enumeration, the query is parsed and "normalized". This process involves putting the query in - // a canonical order, in part so that similar queries can be recognized as such for caching. In - // this case, it orders the $or children by their respective number of children. So our original - // query will be enumerated as if it were typed in this order: - // {a: 1, - // $or: [ - // {b: 2.1, c: 2.1}, - // {b: 2.2, c: 2.2}, - // {b: 3, c: 3, d: 3}, - // {b: 4, c: 4, d: 4, e: 4} - // ] - // } - // Here are the exact plans: - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, c: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, d: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, e: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, d: 1}}}}}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {c: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, c: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, d: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, e: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, d: 1}}}}}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 3}, c: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, d: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, e: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, d: 1}}}}}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {c: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, e: 1}}}}}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, e: 1}}}}}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {c: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, e: 1}}}}}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - "{fetch: {filter: {b: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - "{fetch: {filter: {c: {$eq: 3}, d: {$eq: 3}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - "{fetch: {filter: {b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}}," - " node: {ixscan: {pattern: {a: 1, e: 1}}}}}" - "]}}"); - - // Now to the solutions which don't index the $or. - assertSolutionExists( - "{fetch: {filter: {$or: [" - "{b: {$eq: 2.1}, c: {$eq: 2.1}}, " - "{b: {$eq: 2.2}, c: {$eq: 2.2}}, " - "{b: {$eq: 3}, c: {$eq: 3}, d: {$eq: 3}}, " - "{b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}, e: {$eq: 4}} " - "]}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [" - "{b: {$eq: 2.1}, c: {$eq: 2.1}}, " - "{b: {$eq: 2.2}, c: {$eq: 2.2}}, " - "{b: {$eq: 3}, c: {$eq: 3}, d: {$eq: 3}}, " - "{b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}, e: {$eq: 4}} " - "]}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [" - "{b: {$eq: 2.1}, c: {$eq: 2.1}}, " - "{b: {$eq: 2.2}, c: {$eq: 2.2}}, " - "{b: {$eq: 3}, c: {$eq: 3}, d: {$eq: 3}}, " - "{b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}, e: {$eq: 4}} " - "]}, node: {ixscan: {pattern: {a: 1, d: 1}}}}}}"); - assertSolutionExists( - "{fetch: {filter: {$or: [" - "{b: {$eq: 2.1}, c: {$eq: 2.1}}, " - "{b: {$eq: 2.2}, c: {$eq: 2.2}}, " - "{b: {$eq: 3}, c: {$eq: 3}, d: {$eq: 3}}, " - "{b: {$eq: 4}, c: {$eq: 4}, d: {$eq: 4}, e: {$eq: 4}} " - "]}, node: {ixscan: {pattern: {a: 1, e: 1}}}}}}"); -} - -TEST_F(QueryPlannerTest, LockstepOrEnumerationApplysToEachOrInTree) { - params.options = - QueryPlannerParams::NO_TABLE_SCAN | QueryPlannerParams::ENUMERATE_OR_CHILDREN_LOCKSTEP; - ASSERT_EQ(internalQueryEnumerationMaxOrSolutions.load(), 10); - addIndex(BSON("a" << 1 << "b" << 1)); - addIndex(BSON("a" << 1 << "c" << 1)); - addIndex(BSON("a" << 1 << "x" << 1)); - addIndex(BSON("a" << 1 << "y" << 1)); - - // For this query and the above indexes, each clause of the $or has 2 indexes to choose from, - // for a total of 2 * 2 * 2 * 2 = 16 possible enumerations for just that $or sub-branch. - runQueryAsCommand( - fromjson("{find: 'testns', filter: {" - " a: 1," - " $or: [" - " {b: 2.1, c: 2.1}," - " {b: 2.2, c: 2.2}," - " {$and: [" - " {unindexed: 'thisPredicateToEnsureNestedOrsAreNotCombined'}," - " {$or: [" - " {x: 3.0, y: 3.0}," - " {x: 3.1, y: 3.1}" - " ]}" - " ]}" - "]}}")); - - // The $or enumeration is limited to 10, and then we have 4 plans where just the {a: 1} - // predicate is indexed. - assertNumSolutions(14U); - - // Both lockstep enumerations should be present. - assertSolutionExists( - "{or: {nodes: [" - " {fetch: {filter: {c: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - " {fetch: {filter: {c: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, b: 1}}}}}, " - " {fetch: {" - " filter: {unindexed: {$eq: 'thisPredicateToEnsureNestedOrsAreNotCombined'}}," - " node: {" - " or: {nodes: [" - " {fetch: {filter: {y: {$eq: 3.0}}, node: {ixscan: {pattern: {a: 1, x: 1}}}}}," - " {fetch: {filter: {y: {$eq: 3.1}}, node: {ixscan: {pattern: {a: 1, x: 1}}}}}" - " ]}}" - " }}" - "]}}"); - assertSolutionExists( - "{or: {nodes: [" - " {fetch: {filter: {b: {$eq: 2.1}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - " {fetch: {filter: {b: {$eq: 2.2}}, node: {ixscan: {pattern: {a: 1, c: 1}}}}}, " - " {fetch: {" - " filter: {unindexed: {$eq: 'thisPredicateToEnsureNestedOrsAreNotCombined'}}," - " node: {" - " or: {nodes: [" - " {fetch: {filter: {x: {$eq: 3.0}}, node: {ixscan: {pattern: {a: 1, y: 1}}}}}," - " {fetch: {filter: {x: {$eq: 3.1}}, node: {ixscan: {pattern: {a: 1, y: 1}}}}}" - " ]}}" - " }}" - "]}}"); -} - TEST_F(QueryPlannerTest, InvalidUtf8CodePointDoesNotLeadToInvalidIndexBoundsInvariantFailure) { params.options &= ~QueryPlannerParams::INCLUDE_COLLSCAN; addIndex(BSON("a" << 1)); diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp index d8957e28f17..2f41348526c 100644 --- a/src/mongo/db/query/query_solution.cpp +++ b/src/mongo/db/query/query_solution.cpp @@ -151,7 +151,7 @@ void addEqualityFieldSorts(const BSONObj& sortPattern, sortsOut->insert(prefixBob.obj()); } } -} // namespace +} string QuerySolutionNode::toString() const { mongoutils::str::stream ss; @@ -528,7 +528,6 @@ void IndexScanNode::appendToString(mongoutils::str::stream* ss, int indent) cons *ss << "IXSCAN\n"; addIndent(ss, indent + 1); *ss << "indexName = " << index.name << '\n'; - addIndent(ss, indent + 1); *ss << "keyPattern = " << index.keyPattern << '\n'; if (NULL != filter) { addIndent(ss, indent + 1); -- cgit v1.2.1