diff options
author | Svilen Mihaylov <svilen.mihaylov@mongodb.com> | 2022-09-29 17:54:40 +0000 |
---|---|---|
committer | Evergreen Agent <no-reply@evergreen.mongodb.com> | 2022-09-29 18:40:01 +0000 |
commit | 5f40051ccd887859a43bf0e456773759f5d93ddc (patch) | |
tree | b29cd0d754dd1eee8ab1af8b2e1c1a0bb9358e78 | |
parent | 646eed48d0da896588759030f2ec546ac6fbbd48 (diff) | |
download | mongo-5f40051ccd887859a43bf0e456773759f5d93ddc.tar.gz |
SERVER-69216 [CQF] Remove need to use filter with const true
14 files changed, 95 insertions, 136 deletions
diff --git a/src/mongo/db/query/optimizer/SConscript b/src/mongo/db/query/optimizer/SConscript index 769cb2c3bdb..3791d2bdd0e 100644 --- a/src/mongo/db/query/optimizer/SConscript +++ b/src/mongo/db/query/optimizer/SConscript @@ -42,7 +42,6 @@ env.Library( 'utils/ce_math.cpp', "utils/interval_utils.cpp", "utils/memo_utils.cpp", - "utils/rewriter_utils.cpp", "utils/utils.cpp", ], LIBDEPS=[ @@ -72,6 +71,16 @@ env.CppUnitTest( "reference_tracker_test.cpp", "rewrites/path_optimizer_test.cpp", "interval_intersection_test.cpp", + ], + LIBDEPS=[ + "optimizer", + "unit_test_utils", + ], +) + +env.CppUnitTest( + target='optimizer_failure_test', + source=[ "optimizer_failure_test.cpp", ], LIBDEPS=[ diff --git a/src/mongo/db/query/optimizer/cascades/cost_derivation.cpp b/src/mongo/db/query/optimizer/cascades/cost_derivation.cpp index d212c32c5a7..35be4caa4a3 100644 --- a/src/mongo/db/query/optimizer/cascades/cost_derivation.cpp +++ b/src/mongo/db/query/optimizer/cascades/cost_derivation.cpp @@ -124,7 +124,7 @@ public: const LogicalProps& childLogicalProps = _memo.getGroup(node.getGroupId())._logicalProperties; // Notice that unlike all physical nodes, this logical node takes it cardinality directly - // from the memo group logical property, igrnoring _cardinalityEstimate. + // from the memo group logical property, ignoring _cardinalityEstimate. CEType baseCE = getPropertyConst<CardinalityEstimate>(childLogicalProps).getEstimate(); if (hasProperty<IndexingRequirement>(_physProps)) { diff --git a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp index dcd744b14ef..afed7401960 100644 --- a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp +++ b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp @@ -690,11 +690,13 @@ static void convertFilterToSargableNode(ABT::reference_type node, } } - // If the filter has no constraints after removing no-ops, then rewrite the filter with a - // predicate using the constant True. if (conversion->_reqMap.empty()) { - ctx.addNode(make<FilterNode>(Constant::boolean(true), filterNode.getChild()), - true /*subtitute*/); + // If the filter has no constraints after removing no-ops, then replace with its child. We + // need to copy the child since we hold it by reference from the memo, and during + // subtitution the current group will be erased. + + ABT newNode = filterNode.getChild(); + ctx.addNode(newNode, true /*substitute*/); return; } diff --git a/src/mongo/db/query/optimizer/cascades/memo.cpp b/src/mongo/db/query/optimizer/cascades/memo.cpp index c702175bd4e..ec31837a919 100644 --- a/src/mongo/db/query/optimizer/cascades/memo.cpp +++ b/src/mongo/db/query/optimizer/cascades/memo.cpp @@ -87,17 +87,6 @@ const ABTVector& OrderPreservingABTSet::getVector() const { return _vector; } -PhysRewriteEntry::PhysRewriteEntry(const double priority, - PhysicalRewriteType rule, - ABT node, - std::vector<std::pair<ABT*, properties::PhysProps>> childProps, - NodeCEMap nodeCEMap) - : _priority(priority), - _rule(rule), - _node(std::move(node)), - _childProps(std::move(childProps)), - _nodeCEMap(std::move(nodeCEMap)) {} - PhysOptimizationResult::PhysOptimizationResult() : PhysOptimizationResult(0, {}, CostType::kInfinity) {} @@ -237,10 +226,14 @@ public: // noop } - GroupIdType transport(const ABT& /*n*/, + GroupIdType transport(const ABT& n, const MemoLogicalDelegatorNode& node, - const VariableEnvironment& /*env*/) { - return node.getGroupId(); + const VariableEnvironment& env) { + if (_targetGroupMap.count(n.ref()) == 0) { + return node.getGroupId(); + } + + return addNodes(n, node, n, env, {}); } void prepare(const ABT& n, const FilterNode& node, const VariableEnvironment& /*env*/) { @@ -628,9 +621,6 @@ std::pair<MemoLogicalNodeId, bool> Memo::addNode(GroupIdType groupId, ABT n, LogicalRewriteType rule) { uassert(6624052, "Attempting to insert a physical node", !n.is<ExclusivelyPhysicalNode>()); - uassert(6624053, - "Attempting to insert a logical delegator node", - !n.is<MemoLogicalDelegatorNode>()); Group& group = *_groups.at(groupId); OrderPreservingABTSet& nodes = group._logicalNodes; diff --git a/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp b/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp index 82eedbd4ec7..4388f015f1a 100644 --- a/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp +++ b/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp @@ -33,7 +33,6 @@ #include "mongo/db/query/optimizer/cascades/implementers.h" #include "mongo/db/query/optimizer/cascades/rewriter_rules.h" #include "mongo/db/query/optimizer/explain.h" -#include "mongo/db/query/optimizer/utils/rewriter_utils.h" namespace mongo::optimizer::cascades { @@ -139,21 +138,21 @@ static void printCandidateInfo(const ABT& node, } } -void PhysicalRewriter::costAndRetainBestNode(ABT node, +void PhysicalRewriter::costAndRetainBestNode(std::unique_ptr<ABT> node, ChildPropsType childProps, NodeCEMap nodeCEMap, const PhysicalRewriteType rule, const GroupIdType groupId, PrefixId& prefixId, PhysOptimizationResult& bestResult) { - const CostAndCE nodeCostAndCE = - _costDerivation.deriveCost(_memo, bestResult._physProps, node.ref(), childProps, nodeCEMap); + const CostAndCE nodeCostAndCE = _costDerivation.deriveCost( + _memo, bestResult._physProps, node->ref(), childProps, nodeCEMap); const CostType nodeCost = nodeCostAndCE._cost; uassert(6624056, "Must get non-infinity cost for physical node.", !nodeCost.isInfinite()); if (_memo.getDebugInfo().hasDebugLevel(3)) { std::cout << "Requesting optimization\n"; - printCandidateInfo(node, groupId, nodeCost, childProps, bestResult); + printCandidateInfo(*node, groupId, nodeCost, childProps, bestResult); } const CostType childCostLimit = @@ -166,14 +165,13 @@ void PhysicalRewriter::costAndRetainBestNode(ABT node, std::cout << (success ? (improvement ? "Improved" : "Did not improve") : "Failed optimizing") << "\n"; - printCandidateInfo(node, groupId, nodeCost, childProps, bestResult); + printCandidateInfo(*node, groupId, nodeCost, childProps, bestResult); } tassert(6678300, "Retaining node with uninitialized rewrite rule", rule != cascades::PhysicalRewriteType::Uninitialized); - PhysNodeInfo candidateNodeInfo{ - unwrapConstFilter(std::move(node)), cost, nodeCost, nodeCostAndCE._ce, rule}; + PhysNodeInfo candidateNodeInfo{std::move(*node), cost, nodeCost, nodeCostAndCE._ce, rule}; const bool keepRejectedPlans = _hints._keepRejectedPlans; if (improvement) { if (keepRejectedPlans && bestResult._nodeInfo) { @@ -379,7 +377,7 @@ PhysicalRewriter::OptimizeGroupResult PhysicalRewriter::optimizeGroup(const Grou NodeCEMap nodeCEMap = std::move(rewrite._nodeCEMap); if (nodeCEMap.empty()) { nodeCEMap.emplace( - rewrite._node.cast<Node>(), + rewrite._node->cast<Node>(), getPropertyConst<CardinalityEstimate>(logicalProps).getEstimate()); } diff --git a/src/mongo/db/query/optimizer/cascades/physical_rewriter.h b/src/mongo/db/query/optimizer/cascades/physical_rewriter.h index 205ecc62c3a..cb1b1b395af 100644 --- a/src/mongo/db/query/optimizer/cascades/physical_rewriter.h +++ b/src/mongo/db/query/optimizer/cascades/physical_rewriter.h @@ -71,7 +71,7 @@ public: CostType costLimit); private: - void costAndRetainBestNode(ABT node, + void costAndRetainBestNode(std::unique_ptr<ABT> node, ChildPropsType childProps, NodeCEMap nodeCEMap, PhysicalRewriteType rule, diff --git a/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp b/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp index c27ed44dd84..6475b704d0f 100644 --- a/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp +++ b/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp @@ -29,7 +29,6 @@ #include "mongo/db/query/optimizer/cascades/rewrite_queues.h" #include "mongo/db/query/optimizer/cascades/rewriter_rules.h" -#include "mongo/db/query/optimizer/utils/memo_utils.h" #include <mongo/db/query/optimizer/defs.h> namespace mongo::optimizer::cascades { @@ -58,14 +57,39 @@ bool LogicalRewriteEntryComparator::operator()( return x->_nodeId._index < y->_nodeId._index; } +PhysRewriteEntry::PhysRewriteEntry(const double priority, + PhysicalRewriteType rule, + std::unique_ptr<ABT> node, + std::vector<std::pair<ABT*, properties::PhysProps>> childProps, + NodeCEMap nodeCEMap) + : _priority(priority), + _rule(rule), + _node(std::move(node)), + _childProps(std::move(childProps)), + _nodeCEMap(std::move(nodeCEMap)) {} + void optimizeChildrenNoAssert(PhysRewriteQueue& queue, const double priority, const PhysicalRewriteType rule, - ABT node, + std::unique_ptr<ABT> node, ChildPropsType childProps, NodeCEMap nodeCEMap) { queue.emplace(std::make_unique<PhysRewriteEntry>( priority, rule, std::move(node), std::move(childProps), std::move(nodeCEMap))); } +void optimizeChildrenNoAssert(PhysRewriteQueue& queue, + double priority, + PhysicalRewriteType rule, + ABT node, + ChildPropsType childProps, + NodeCEMap nodeCEMap) { + optimizeChildrenNoAssert(queue, + priority, + rule, + std::make_unique<ABT>(std::move(node)), + std::move(childProps), + std::move(nodeCEMap)); +} + } // namespace mongo::optimizer::cascades diff --git a/src/mongo/db/query/optimizer/cascades/rewrite_queues.h b/src/mongo/db/query/optimizer/cascades/rewrite_queues.h index b8e6ec66530..732d338a153 100644 --- a/src/mongo/db/query/optimizer/cascades/rewrite_queues.h +++ b/src/mongo/db/query/optimizer/cascades/rewrite_queues.h @@ -33,7 +33,6 @@ #include "mongo/db/query/optimizer/cascades/rewriter_rules.h" #include "mongo/db/query/optimizer/node_defs.h" -#include "mongo/db/query/optimizer/utils/rewriter_utils.h" namespace mongo::optimizer::cascades { @@ -75,7 +74,7 @@ static constexpr double kDefaultPriority = 10.0; struct PhysRewriteEntry { PhysRewriteEntry(double priority, PhysicalRewriteType rule, - ABT node, + std::unique_ptr<ABT> node, ChildPropsType childProps, NodeCEMap nodeCEMap); @@ -88,9 +87,15 @@ struct PhysRewriteEntry { // Rewrite rule that triggered this entry. PhysicalRewriteType _rule; - ABT _node; + // Node we are optimizing. This is typically a single node such as Filter with a + // MemoLogicalDelegator child, but could be a more complex tree. + std::unique_ptr<ABT> _node; + // For each child to optimize, we have associated physical properties. If we are optimizing the + // node under new properties (e.g. via enforcement) the map will contain a single entry using + // the address of the node itself (as opposed to the children to optimize). ChildPropsType _childProps; + // Optional per-node CE. Used if the node is complex tree. NodeCEMap _nodeCEMap; }; @@ -106,6 +111,13 @@ using PhysRewriteQueue = std::priority_queue<std::unique_ptr<PhysRewriteEntry>, void optimizeChildrenNoAssert(PhysRewriteQueue& queue, double priority, PhysicalRewriteType rule, + std::unique_ptr<ABT> node, + ChildPropsType childProps, + NodeCEMap nodeCEMap); + +void optimizeChildrenNoAssert(PhysRewriteQueue& queue, + double priority, + PhysicalRewriteType rule, ABT node, ChildPropsType childProps, NodeCEMap nodeCEMap); @@ -116,7 +128,8 @@ static void optimizeChildren(PhysRewriteQueue& queue, ABT node, ChildPropsType childProps) { static_assert(canBePhysicalNode<T>(), "Can only optimize a physical node."); - optimizeChildrenNoAssert(queue, priority, rule, std::move(node), std::move(childProps), {}); + optimizeChildrenNoAssert( + queue, priority, rule, std::move(node), std::move(childProps), {} /*nodeCEMap*/); } template <class T, PhysicalRewriteType rule> @@ -131,7 +144,7 @@ static void optimizeChild(PhysRewriteQueue& queue, template <class T, PhysicalRewriteType rule> static void optimizeChild(PhysRewriteQueue& queue, const double priority, ABT node) { - optimizeChildren<T, rule>(queue, priority, std::move(node), {}); + optimizeChildren<T, rule>(queue, priority, std::move(node), {} /*nodeCEMap*/); } @@ -140,8 +153,10 @@ void optimizeUnderNewProperties(cascades::PhysRewriteQueue& queue, const double priority, ABT child, properties::PhysProps props) { - optimizeChild<FilterNode, rule>( - queue, priority, wrapConstFilter(std::move(child)), std::move(props)); + auto nodePtr = std::make_unique<ABT>(std::move(child)); + ChildPropsType childProps{{nodePtr.get(), std::move(props)}}; + optimizeChildrenNoAssert( + queue, priority, rule, std::move(nodePtr), std::move(childProps), {} /*nodeCEMap*/); } template <class T, PhysicalRewriteType rule> diff --git a/src/mongo/db/query/optimizer/logical_rewriter_optimizer_test.cpp b/src/mongo/db/query/optimizer/logical_rewriter_optimizer_test.cpp index bd6049947ea..6f4f90a6a50 100644 --- a/src/mongo/db/query/optimizer/logical_rewriter_optimizer_test.cpp +++ b/src/mongo/db/query/optimizer/logical_rewriter_optimizer_test.cpp @@ -1546,8 +1546,6 @@ TEST(LogicalRewriter, RemoveNoopFilter) { "| | ptest\n" "| RefBlock: \n" "| Variable [ptest]\n" - "Filter []\n" - "| Const [true]\n" "Scan [test]\n" " BindBlock:\n" " [ptest]\n" diff --git a/src/mongo/db/query/optimizer/optimizer_failure_test.cpp b/src/mongo/db/query/optimizer/optimizer_failure_test.cpp index 14c1a4a4cc6..3b57295d606 100644 --- a/src/mongo/db/query/optimizer/optimizer_failure_test.cpp +++ b/src/mongo/db/query/optimizer/optimizer_failure_test.cpp @@ -29,13 +29,9 @@ #include "mongo/db/query/optimizer/cascades/ce_hinted.h" #include "mongo/db/query/optimizer/cascades/cost_derivation.h" -#include "mongo/db/query/optimizer/explain.h" #include "mongo/db/query/optimizer/node.h" #include "mongo/db/query/optimizer/opt_phase_manager.h" -#include "mongo/db/query/optimizer/reference_tracker.h" -#include "mongo/db/query/optimizer/rewrites/const_eval.h" #include "mongo/db/query/optimizer/syntax/syntax.h" -#include "mongo/db/query/optimizer/syntax/syntax_fwd_declare.h" #include "mongo/db/query/optimizer/utils/unit_test_utils.h" #include "mongo/db/query/optimizer/utils/utils.h" #include "mongo/unittest/death_test.h" @@ -261,7 +257,7 @@ DEATH_TEST_REGEX(Optimizer, OptGroupFailed, "Tripwire assertion.*6808706") { OptPhaseManager phaseManager( {OptPhase::MemoExplorationPhase, OptPhase::MemoImplementationPhase}, prefixId, - true, + true /*requireRID*/, {{{"test", {{}, {}}}}}, std::make_unique<HintedCE>(std::move(hints)), std::make_unique<DefaultCosting>(), diff --git a/src/mongo/db/query/optimizer/rewrites/const_eval.cpp b/src/mongo/db/query/optimizer/rewrites/const_eval.cpp index 5ced7f0d93f..ff87d3b5bbd 100644 --- a/src/mongo/db/query/optimizer/rewrites/const_eval.cpp +++ b/src/mongo/db/query/optimizer/rewrites/const_eval.cpp @@ -483,6 +483,18 @@ void ConstEval::transport(ABT&, const LambdaAbstraction&, ABT&) { --_inCostlyCtx; } +void ConstEval::transport(ABT& n, const FilterNode& op, ABT& child, ABT& expr) { + if (expr == Constant::boolean(true)) { + // Remove trivially true filter. + + // First, pull out the child and put in a blackhole. + auto result = std::exchange(child, make<Blackhole>()); + + // Replace the filter node itself with the extracted child. + swapAndUpdate(n, std::move(result)); + } +} + void ConstEval::transport(ABT& n, const EvaluationNode& op, ABT& child, ABT& expr) { if (_noRefProj.erase(&op)) { // The evaluation node is unused so replace it with its own child. diff --git a/src/mongo/db/query/optimizer/rewrites/const_eval.h b/src/mongo/db/query/optimizer/rewrites/const_eval.h index 171b7665fa1..3c31bc93f86 100644 --- a/src/mongo/db/query/optimizer/rewrites/const_eval.h +++ b/src/mongo/db/query/optimizer/rewrites/const_eval.h @@ -64,6 +64,8 @@ public: void transport(ABT& n, const BinaryOp& op, ABT& lhs, ABT& rhs); void transport(ABT& n, const FunctionCall& op, std::vector<ABT>& args); void transport(ABT& n, const If& op, ABT& cond, ABT& thenBranch, ABT& elseBranch); + + void transport(ABT& n, const FilterNode& op, ABT& child, ABT& expr); void transport(ABT& n, const EvaluationNode& op, ABT& child, ABT& expr); void prepare(ABT&, const PathTraverse&); diff --git a/src/mongo/db/query/optimizer/utils/rewriter_utils.cpp b/src/mongo/db/query/optimizer/utils/rewriter_utils.cpp deleted file mode 100644 index 88c1427c8df..00000000000 --- a/src/mongo/db/query/optimizer/utils/rewriter_utils.cpp +++ /dev/null @@ -1,47 +0,0 @@ -/** - * Copyright (C) 2022-present MongoDB, Inc. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the Server Side Public License, version 1, - * as published by MongoDB, Inc. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * Server Side Public License for more details. - * - * You should have received a copy of the Server Side Public License - * along with this program. If not, see - * <http://www.mongodb.com/licensing/server-side-public-license>. - * - * As a special exception, the copyright holders give permission to link the - * code of portions of this program with the OpenSSL library under certain - * conditions as described in each individual source file and distribute - * linked combinations including the program with the OpenSSL library. You - * must comply with the Server Side Public License in all respects for - * all of the code used other than as permitted herein. If you modify file(s) - * with this exception, you may extend this exception to your version of the - * file(s), but you are not obligated to do so. If you do not wish to do so, - * delete this exception statement from your version. If you delete this - * exception statement from all source files in the program, then also delete - * it in the license file. - */ - -#include "mongo/db/query/optimizer/utils/rewriter_utils.h" - - -namespace mongo::optimizer { - -ABT wrapConstFilter(ABT node) { - return make<FilterNode>(Constant::boolean(true), std::move(node)); -} - -ABT unwrapConstFilter(ABT node) { - if (auto nodePtr = node.cast<FilterNode>(); - nodePtr != nullptr && nodePtr->getFilter() == Constant::boolean(true)) { - return nodePtr->getChild(); - } - return node; -} - -} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/utils/rewriter_utils.h b/src/mongo/db/query/optimizer/utils/rewriter_utils.h deleted file mode 100644 index e81190a5ce6..00000000000 --- a/src/mongo/db/query/optimizer/utils/rewriter_utils.h +++ /dev/null @@ -1,40 +0,0 @@ -/** - * Copyright (C) 2022-present MongoDB, Inc. - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the Server Side Public License, version 1, - * as published by MongoDB, Inc. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * Server Side Public License for more details. - * - * You should have received a copy of the Server Side Public License - * along with this program. If not, see - * <http://www.mongodb.com/licensing/server-side-public-license>. - * - * As a special exception, the copyright holders give permission to link the - * code of portions of this program with the OpenSSL library under certain - * conditions as described in each individual source file and distribute - * linked combinations including the program with the OpenSSL library. You - * must comply with the Server Side Public License in all respects for - * all of the code used other than as permitted herein. If you modify file(s) - * with this exception, you may extend this exception to your version of the - * file(s), but you are not obligated to do so. If you do not wish to do so, - * delete this exception statement from your version. If you delete this - * exception statement from all source files in the program, then also delete - * it in the license file. - */ - -#pragma once - -#include "mongo/db/query/optimizer/node.h" - - -namespace mongo::optimizer { - -ABT wrapConstFilter(ABT node); -ABT unwrapConstFilter(ABT node); - -} // namespace mongo::optimizer |