diff options
author | Matt Boros <matt.boros@mongodb.com> | 2022-08-29 14:46:10 +0000 |
---|---|---|
committer | Evergreen Agent <no-reply@evergreen.mongodb.com> | 2022-08-29 16:08:45 +0000 |
commit | fb2209b3a862e819fed0f21eecd15b8fd4fa9a45 (patch) | |
tree | c285080910e97cd8dd14d3a8f8feae38de3ee798 | |
parent | 0fbba9495da3c621deddbee47cff3fda00b07bec (diff) | |
download | mongo-fb2209b3a862e819fed0f21eecd15b8fd4fa9a45.tar.gz |
SERVER-66783 Explain improvement add triggering rules to memo
19 files changed, 371 insertions, 115 deletions
diff --git a/src/mongo/db/query/optimizer/SConscript b/src/mongo/db/query/optimizer/SConscript index c050a0d79e7..579404a64a0 100644 --- a/src/mongo/db/query/optimizer/SConscript +++ b/src/mongo/db/query/optimizer/SConscript @@ -42,6 +42,7 @@ env.Library( 'utils/ce_math.cpp', "utils/interval_utils.cpp", "utils/memo_utils.cpp", + "utils/rewriter_utils.cpp", "utils/utils.cpp", ], LIBDEPS=[ diff --git a/src/mongo/db/query/optimizer/cascades/enforcers.cpp b/src/mongo/db/query/optimizer/cascades/enforcers.cpp index 483a5140ae8..a218043c881 100644 --- a/src/mongo/db/query/optimizer/cascades/enforcers.cpp +++ b/src/mongo/db/query/optimizer/cascades/enforcers.cpp @@ -29,6 +29,7 @@ #include "mongo/db/query/optimizer/cascades/enforcers.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" #include "mongo/db/query/optimizer/utils/memo_utils.h" namespace mongo::optimizer::cascades { @@ -107,7 +108,7 @@ public: } ABT enforcer = make<CollationNode>(prop, make<MemoLogicalDelegatorNode>(_groupId)); - optimizeChild<CollationNode>( + optimizeChild<CollationNode, PhysicalRewriteType::EnforceCollation>( _queue, kDefaultPriority, std::move(enforcer), std::move(childProps)); } @@ -127,7 +128,7 @@ public: childProps, LimitEstimate{static_cast<CEType>(prop.getAbsoluteLimit())}); ABT enforcer = make<LimitSkipNode>(prop, make<MemoLogicalDelegatorNode>(_groupId)); - optimizeChild<LimitSkipNode>( + optimizeChild<LimitSkipNode, PhysicalRewriteType::EnforceLimitSkip>( _queue, kDefaultPriority, std::move(enforcer), std::move(childProps)); } @@ -181,7 +182,7 @@ public: getProperty<DistributionRequirement>(childProps).setDisableExchanges(true); ABT enforcer = make<ExchangeNode>(prop, make<MemoLogicalDelegatorNode>(_groupId)); - optimizeChild<ExchangeNode>( + optimizeChild<ExchangeNode, PhysicalRewriteType::EnforceDistribution>( _queue, kDefaultPriority, std::move(enforcer), std::move(childProps)); } } @@ -237,10 +238,11 @@ public: prop.getDedupRID(), prop.getSatisfiedPartialIndexesGroupId()}); - optimizeUnderNewProperties(_queue, - kDefaultPriority, - make<MemoLogicalDelegatorNode>(_groupId), - std::move(newProps)); + optimizeUnderNewProperties<PhysicalRewriteType::AttemptCoveringQuery>( + _queue, + kDefaultPriority, + make<MemoLogicalDelegatorNode>(_groupId), + std::move(newProps)); } } diff --git a/src/mongo/db/query/optimizer/cascades/implementers.cpp b/src/mongo/db/query/optimizer/cascades/implementers.cpp index 2a0c4cfaac0..d09fc7d2622 100644 --- a/src/mongo/db/query/optimizer/cascades/implementers.cpp +++ b/src/mongo/db/query/optimizer/cascades/implementers.cpp @@ -29,6 +29,8 @@ #include "mongo/db/query/optimizer/cascades/implementers.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" +#include "mongo/db/query/optimizer/props.h" #include "mongo/db/query/optimizer/utils/ce_math.h" #include "mongo/db/query/optimizer/utils/memo_utils.h" @@ -138,15 +140,20 @@ public: make<LimitSkipNode>(LimitSkipRequirement{1, 0}, std::move(physicalSeek)); nodeCEMap.emplace(limitSkip.cast<Node>(), 1.0); - optimizeChildrenNoAssert( - _queue, kDefaultPriority, std::move(limitSkip), {}, std::move(nodeCEMap)); + optimizeChildrenNoAssert(_queue, + kDefaultPriority, + PhysicalRewriteType::Seek, + std::move(limitSkip), + {}, + std::move(nodeCEMap)); } else { if (needsRID) { fieldProjectionMap._ridProjection = ridProjName; } ABT physicalScan = make<PhysicalScanNode>( std::move(fieldProjectionMap), node.getScanDefName(), canUseParallelScan); - optimizeChild<PhysicalScanNode>(_queue, kDefaultPriority, std::move(physicalScan)); + optimizeChild<PhysicalScanNode, PhysicalRewriteType::PhysicalScan>( + _queue, kDefaultPriority, std::move(physicalScan)); } } @@ -216,8 +223,12 @@ public: } } - optimizeChildrenNoAssert( - _queue, kDefaultPriority, std::move(physNode), {}, std::move(nodeCEMap)); + optimizeChildrenNoAssert(_queue, + kDefaultPriority, + PhysicalRewriteType::ValueScan, + std::move(physNode), + {}, + std::move(nodeCEMap)); } void operator()(const ABT& /*n*/, const MemoLogicalDelegatorNode& /*node*/) { @@ -244,7 +255,7 @@ public: getProperty<DistributionRequirement>(newProps).setDisableExchanges(true); ABT physicalFilter = n; - optimizeChild<FilterNode>( + optimizeChild<FilterNode, PhysicalRewriteType::Filter>( _queue, kDefaultPriority, std::move(physicalFilter), std::move(newProps)); } @@ -285,7 +296,7 @@ public: } ABT physicalEval = n; - optimizeChild<EvaluationNode>( + optimizeChild<EvaluationNode, PhysicalRewriteType::RenameProjection>( _queue, kDefaultPriority, std::move(physicalEval), std::move(newProps)); return; } @@ -302,7 +313,8 @@ public: if (!propertyAffectsProjection<ProjectionRequirement>(_physProps, projectionName)) { // We do not require the projection. Do not place a physical evaluation node and // continue optimizing the child. - optimizeUnderNewProperties(_queue, kDefaultPriority, node.getChild(), _physProps); + optimizeUnderNewProperties<PhysicalRewriteType::EvaluationPassthrough>( + _queue, kDefaultPriority, node.getChild(), _physProps); return; } @@ -322,7 +334,7 @@ public: getProperty<DistributionRequirement>(newProps).setDisableExchanges(true); ABT physicalEval = n; - optimizeChild<EvaluationNode>( + optimizeChild<EvaluationNode, PhysicalRewriteType::Evaluation>( _queue, kDefaultPriority, std::move(physicalEval), std::move(newProps)); } @@ -557,8 +569,12 @@ public: nodeCEMap.emplace(physNode.cast<Node>(), currentGroupCE); } - optimizeChildrenNoAssert( - _queue, kDefaultPriority, std::move(physNode), {}, std::move(nodeCEMap)); + optimizeChildrenNoAssert(_queue, + kDefaultPriority, + PhysicalRewriteType::SargableToIndex, + std::move(physNode), + {}, + std::move(nodeCEMap)); } } else { const auto& scanParams = node.getScanParams(); @@ -590,6 +606,7 @@ public: ABT physNode = make<Blackhole>(); CEType baseCE = 0.0; + PhysicalRewriteType rule = PhysicalRewriteType::Uninitialized; if (indexReqTarget == IndexReqTarget::Complete) { baseCE = scanGroupCE; @@ -597,6 +614,7 @@ public: physNode = make<PhysicalScanNode>( std::move(fieldProjectionMap), scanDefName, canUseParallelScan); nodeCEMap.emplace(physNode.cast<Node>(), baseCE); + rule = PhysicalRewriteType::SargableToPhysicalScan; } else { baseCE = 1.0; @@ -606,6 +624,7 @@ public: physNode = make<LimitSkipNode>(LimitSkipRequirement{1, 0}, std::move(physNode)); nodeCEMap.emplace(physNode.cast<Node>(), baseCE); + rule = PhysicalRewriteType::SargableToSeek; } ResidualRequirementsWithCE residualReqsWithCE; @@ -617,7 +636,7 @@ public: lowerPartialSchemaRequirements( baseCE, {} /*indexPredSels*/, residualReqsWithCE, physNode, nodeCEMap); optimizeChildrenNoAssert( - _queue, kDefaultPriority, std::move(physNode), {}, std::move(nodeCEMap)); + _queue, kDefaultPriority, rule, std::move(physNode), {}, std::move(nodeCEMap)); } } @@ -898,7 +917,7 @@ public: ABT physicalJoin = n; BinaryJoinNode& newNode = *physicalJoin.cast<BinaryJoinNode>(); - optimizeChildren<BinaryJoinNode>( + optimizeChildren<BinaryJoinNode, PhysicalRewriteType::NLJ>( _queue, kDefaultPriority, std::move(physicalJoin), @@ -929,7 +948,7 @@ public: childProps.emplace_back(&child, std::move(newProps)); } - optimizeChildren<UnionNode>( + optimizeChildren<UnionNode, PhysicalRewriteType::Union>( _queue, kDefaultPriority, std::move(physicalUnion), std::move(childProps)); } @@ -1039,7 +1058,7 @@ public: std::move(aggregationProjections), node.getType(), node.getChild()); - optimizeChild<GroupByNode>( + optimizeChild<GroupByNode, PhysicalRewriteType::HashGroup>( _queue, kDefaultPriority, std::move(physicalGroupBy), std::move(newProps)); } @@ -1072,7 +1091,7 @@ public: getProperty<DistributionRequirement>(newProps).setDisableExchanges(false); ABT physicalUnwind = n; - optimizeChild<UnwindNode>( + optimizeChild<UnwindNode, PhysicalRewriteType::Unwind>( _queue, kDefaultPriority, std::move(physicalUnwind), std::move(newProps)); } @@ -1085,7 +1104,9 @@ public: return; } - optimizeSimplePropertyNode<CollationNode, CollationRequirement>(node); + optimizeSimplePropertyNode<CollationNode, + CollationRequirement, + PhysicalRewriteType::Collation>(node); } void operator()(const ABT& /*n*/, const LimitSkipNode& node) { @@ -1110,11 +1131,14 @@ public: setPropertyOverwrite<LimitSkipRequirement>(newProps, std::move(newProp)); getProperty<DistributionRequirement>(newProps).setDisableExchanges(false); - optimizeUnderNewProperties(_queue, kDefaultPriority, node.getChild(), std::move(newProps)); + optimizeUnderNewProperties<PhysicalRewriteType::LimitSkip>( + _queue, kDefaultPriority, node.getChild(), std::move(newProps)); } void operator()(const ABT& /*n*/, const ExchangeNode& node) { - optimizeSimplePropertyNode<ExchangeNode, DistributionRequirement>(node); + optimizeSimplePropertyNode<ExchangeNode, + DistributionRequirement, + PhysicalRewriteType::Exchange>(node); } void operator()(const ABT& n, const RootNode& node) { @@ -1132,7 +1156,8 @@ public: getProperty<DistributionRequirement>(newProps).setDisableExchanges(false); ABT rootNode = n; - optimizeChild<RootNode>(_queue, kDefaultPriority, std::move(rootNode), std::move(newProps)); + optimizeChild<RootNode, PhysicalRewriteType::Root>( + _queue, kDefaultPriority, std::move(rootNode), std::move(newProps)); } template <typename T> @@ -1156,14 +1181,15 @@ public: _logicalProps(logicalProps) {} private: - template <class NodeType, class PropType> + template <class NodeType, class PropType, PhysicalRewriteType rule> void optimizeSimplePropertyNode(const NodeType& node) { const PropType& nodeProp = node.getProperty(); PhysProps newProps = _physProps; setPropertyOverwrite<PropType>(newProps, nodeProp); getProperty<DistributionRequirement>(newProps).setDisableExchanges(false); - optimizeUnderNewProperties(_queue, kDefaultPriority, node.getChild(), std::move(newProps)); + optimizeUnderNewProperties<rule>( + _queue, kDefaultPriority, node.getChild(), std::move(newProps)); } struct IndexAvailableDirections { @@ -1441,6 +1467,7 @@ private: childProps); optimizeChildrenNoAssert(_queue, kDefaultPriority, + PhysicalRewriteType::RIDIntersectMergeJoin, std::move(physNode), std::move(childProps), std::move(nodeCEMap)); @@ -1476,6 +1503,7 @@ private: childProps); optimizeChildrenNoAssert(_queue, kDefaultPriority, + PhysicalRewriteType::RIDIntersectHashJoin, std::move(physNode), std::move(childProps), std::move(nodeCEMap)); @@ -1510,6 +1538,7 @@ private: childProps); optimizeChildrenNoAssert(_queue, kDefaultPriority, + PhysicalRewriteType::RIDIntersectGroupBy, std::move(physNode), std::move(childProps), std::move(nodeCEMap)); @@ -1527,11 +1556,12 @@ private: setCollationForRIDIntersect( collationLeftRightSplit, leftPhysPropsLocal, rightPhysPropsLocal); - optimizeChildren<BinaryJoinNode>(_queue, - kDefaultPriority, - std::move(physicalJoin), - std::move(leftPhysPropsLocal), - std::move(rightPhysPropsLocal)); + optimizeChildren<BinaryJoinNode, PhysicalRewriteType::RIDIntersectNLJ>( + _queue, + kDefaultPriority, + std::move(physicalJoin), + std::move(leftPhysPropsLocal), + std::move(rightPhysPropsLocal)); } } diff --git a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp index 24d970f4ea6..2c6dd059166 100644 --- a/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp +++ b/src/mongo/db/query/optimizer/cascades/logical_rewriter.cpp @@ -29,6 +29,7 @@ #include "mongo/db/query/optimizer/cascades/logical_rewriter.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" namespace mongo::optimizer::cascades { @@ -104,11 +105,12 @@ LogicalRewriter::LogicalRewriter(Memo& memo, } GroupIdType LogicalRewriter::addRootNode(const ABT& node) { - return addNode(node, -1, false /*addExistingNodeWithNewChild*/).first; + return addNode(node, -1, LogicalRewriteType::Root, false /*addExistingNodeWithNewChild*/).first; } std::pair<GroupIdType, NodeIdSet> LogicalRewriter::addNode(const ABT& node, const GroupIdType targetGroupId, + const LogicalRewriteType rule, const bool addExistingNodeWithNewChild) { NodeIdSet insertNodeIds; @@ -120,6 +122,7 @@ std::pair<GroupIdType, NodeIdSet> LogicalRewriter::addNode(const ABT& node, const GroupIdType resultGroupId = _memo.integrate(node, std::move(targetGroupMap), insertNodeIds, + rule, addExistingNodeWithNewChild, _useHeuristicCE); @@ -150,12 +153,15 @@ void LogicalRewriter::clearGroup(const GroupIdType groupId) { class RewriteContext { public: RewriteContext(LogicalRewriter& rewriter, + const LogicalRewriteType rule, const MemoLogicalNodeId aboveNodeId, const MemoLogicalNodeId belowNodeId) - : RewriteContext(rewriter, aboveNodeId, true /*hasBelowNodeId*/, belowNodeId){}; + : RewriteContext(rewriter, rule, aboveNodeId, true /*hasBelowNodeId*/, belowNodeId){}; - RewriteContext(LogicalRewriter& rewriter, const MemoLogicalNodeId aboveNodeId) - : RewriteContext(rewriter, aboveNodeId, false /*hasBelowNodeId*/, {}){}; + RewriteContext(LogicalRewriter& rewriter, + const LogicalRewriteType rule, + const MemoLogicalNodeId aboveNodeId) + : RewriteContext(rewriter, rule, aboveNodeId, false /*hasBelowNodeId*/, {}){}; std::pair<GroupIdType, NodeIdSet> addNode(const ABT& node, const bool substitute, @@ -169,7 +175,7 @@ public: _rewriter.clearGroup(_belowNodeId._groupId); } } - return _rewriter.addNode(node, _aboveNodeId._groupId, addExistingNodeWithNewChild); + return _rewriter.addNode(node, _aboveNodeId._groupId, _rule, addExistingNodeWithNewChild); } Memo& getMemo() const { @@ -210,6 +216,7 @@ public: private: RewriteContext(LogicalRewriter& rewriter, + const LogicalRewriteType rule, const MemoLogicalNodeId aboveNodeId, const bool hasBelowNodeId, const MemoLogicalNodeId belowNodeId) @@ -217,7 +224,8 @@ private: _hasBelowNodeId(hasBelowNodeId), _belowNodeId(belowNodeId), _rewriter(rewriter), - _hasSubstituted(false){}; + _hasSubstituted(false), + _rule(rule){}; const MemoLogicalNodeId _aboveNodeId; const bool _hasBelowNodeId; @@ -227,6 +235,8 @@ private: LogicalRewriter& _rewriter; bool _hasSubstituted; + + const LogicalRewriteType _rule; }; struct ReorderDependencies { @@ -1382,12 +1392,13 @@ void LogicalRewriter::rewriteGroup(const GroupIdType groupId) { // TODO: check if rewriteEntry is different than previous (remove duplicates). queue.pop(); - _rewriteMap.at(rewriteEntry._type)(this, rewriteEntry._nodeId); + _rewriteMap.at(rewriteEntry._type)(this, rewriteEntry._nodeId, rewriteEntry._type); } } template <class AboveType, class BelowType, template <class, class> class R> -void LogicalRewriter::bindAboveBelow(const MemoLogicalNodeId nodeMemoId) { +void LogicalRewriter::bindAboveBelow(const MemoLogicalNodeId nodeMemoId, + const LogicalRewriteType rule) { // Get a reference to the node instead of the node itself. // Rewrites insert into the memo and can move it. ABT::reference_type node = _memo.getNode(nodeMemoId); @@ -1404,7 +1415,7 @@ void LogicalRewriter::bindAboveBelow(const MemoLogicalNodeId nodeMemoId) { const MemoLogicalNodeId targetNodeId{targetGroupId, i}; auto targetNode = _memo.getNode(targetNodeId); if (targetNode.is<BelowType>()) { - RewriteContext ctx(*this, nodeMemoId, targetNodeId); + RewriteContext ctx(*this, rule, nodeMemoId, targetNodeId); R<AboveType, BelowType>()(node, targetNode, ctx); if (ctx.hasSubstituted()) { return; @@ -1434,7 +1445,7 @@ void LogicalRewriter::bindAboveBelow(const MemoLogicalNodeId nodeMemoId) { .template cast<MemoLogicalDelegatorNode>() ->getGroupId() == currentGroupId); - RewriteContext ctx(*this, parentNodeId, nodeMemoId); + RewriteContext ctx(*this, rule, parentNodeId, nodeMemoId); R<AboveType, BelowType>()(targetNode, node, ctx); if (ctx.hasSubstituted()) { return; @@ -1445,12 +1456,13 @@ void LogicalRewriter::bindAboveBelow(const MemoLogicalNodeId nodeMemoId) { } template <class Type, template <class> class R> -void LogicalRewriter::bindSingleNode(const MemoLogicalNodeId nodeMemoId) { +void LogicalRewriter::bindSingleNode(const MemoLogicalNodeId nodeMemoId, + const LogicalRewriteType rule) { // Get a reference to the node instead of the node itself. // Rewrites insert into the memo and can move it. ABT::reference_type node = _memo.getNode(nodeMemoId); if (node.is<Type>()) { - RewriteContext ctx(*this, nodeMemoId); + RewriteContext ctx(*this, rule, nodeMemoId); R<Type>()(node, ctx); } } diff --git a/src/mongo/db/query/optimizer/cascades/logical_rewriter.h b/src/mongo/db/query/optimizer/cascades/logical_rewriter.h index eb595e26bd8..c9a79c617c3 100644 --- a/src/mongo/db/query/optimizer/cascades/logical_rewriter.h +++ b/src/mongo/db/query/optimizer/cascades/logical_rewriter.h @@ -31,8 +31,8 @@ #include <queue> -#include "mongo/db/query/optimizer/cascades/logical_rewriter_rules.h" #include "mongo/db/query/optimizer/cascades/memo.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" #include "mongo/db/query/optimizer/utils/utils.h" namespace mongo::optimizer::cascades { @@ -71,6 +71,7 @@ public: GroupIdType addRootNode(const ABT& node); std::pair<GroupIdType, NodeIdSet> addNode(const ABT& node, GroupIdType targetGroupId, + LogicalRewriteType rule, bool addExistingNodeWithNewChild); void clearGroup(GroupIdType groupId); @@ -90,21 +91,21 @@ public: static const RewriteSet& getSubstitutionSet(); private: - using RewriteFn = - std::function<void(LogicalRewriter* rewriter, const MemoLogicalNodeId nodeId)>; + using RewriteFn = std::function<void( + LogicalRewriter* rewriter, const MemoLogicalNodeId nodeId, const LogicalRewriteType rule)>; using RewriteFnMap = opt::unordered_map<LogicalRewriteType, RewriteFn>; /** * Attempts to perform a reordering rewrite specified by the R template argument. */ template <class AboveType, class BelowType, template <class, class> class R> - void bindAboveBelow(MemoLogicalNodeId nodeMemoId); + void bindAboveBelow(MemoLogicalNodeId nodeMemoId, LogicalRewriteType rule); /** * Attempts to perform a simple rewrite specified by the R template argument. */ template <class Type, template <class> class R> - void bindSingleNode(MemoLogicalNodeId nodeMemoId); + void bindSingleNode(MemoLogicalNodeId nodeMemoId, LogicalRewriteType rule); void initializeRewrites(); diff --git a/src/mongo/db/query/optimizer/cascades/memo.cpp b/src/mongo/db/query/optimizer/cascades/memo.cpp index d827d450191..a97fccb3088 100644 --- a/src/mongo/db/query/optimizer/cascades/memo.cpp +++ b/src/mongo/db/query/optimizer/cascades/memo.cpp @@ -27,9 +27,11 @@ * it in the license file. */ +#include "mongo/db/query/optimizer/cascades/memo.h" + #include <set> -#include "mongo/db/query/optimizer/cascades/memo.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" #include "mongo/db/query/optimizer/explain.h" #include "mongo/db/query/optimizer/utils/abt_hash.h" #include "mongo/db/query/optimizer/utils/utils.h" @@ -86,10 +88,12 @@ const ABTVector& OrderPreservingABTSet::getVector() const { } 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)) {} @@ -192,11 +196,13 @@ public: explicit MemoIntegrator(Memo& memo, Memo::NodeTargetGroupMap targetGroupMap, NodeIdSet& insertedNodeIds, + const LogicalRewriteType rule, const bool addExistingNodeWithNewChild, const bool useHeuristicCE) : _memo(memo), _insertedNodeIds(insertedNodeIds), _targetGroupMap(std::move(targetGroupMap)), + _rule(rule), _addExistingNodeWithNewChild(addExistingNodeWithNewChild), _useHeuristicCE(useHeuristicCE) {} @@ -421,6 +427,7 @@ private: targetGroupId, _insertedNodeIds, std::move(forMemo), + _rule, _useHeuristicCE); return result._groupId; } @@ -560,6 +567,9 @@ private: */ Memo::NodeTargetGroupMap _targetGroupMap; + // Rewrite rule that triggered this node to be created. + const LogicalRewriteType _rule; + // If set we enable modification of target group based on existing nodes. In practical terms, we // would not assume that if F(x) = F(y) then x = y. This is currently used in conjunction with // $elemMatch rewrite (PathTraverse over PathCompose). @@ -614,14 +624,21 @@ GroupIdType Memo::addGroup(ProjectionNameSet projections) { return _groups.size() - 1; } -std::pair<MemoLogicalNodeId, bool> Memo::addNode(GroupIdType groupId, ABT n) { +std::pair<MemoLogicalNodeId, bool> Memo::addNode(GroupIdType groupId, + ABT n, + LogicalRewriteType rule) { uassert(6624052, "Attempting to insert a physical node", !n.is<PhysicalNode>()); uassert(6624053, "Attempting to insert a logical delegator node", !n.is<MemoLogicalDelegatorNode>()); - OrderPreservingABTSet& nodes = _groups.at(groupId)->_logicalNodes; + Group& group = *_groups.at(groupId); + OrderPreservingABTSet& nodes = group._logicalNodes; + auto [index, inserted] = nodes.emplace_back(std::move(n)); + if (inserted) { + group._rules.push_back(rule); + } return {{groupId, index}, inserted}; } @@ -684,6 +701,7 @@ MemoLogicalNodeId Memo::addNode(GroupIdVector groupVector, const GroupIdType targetGroupId, NodeIdSet& insertedNodeIds, ABT n, + const LogicalRewriteType rule, const bool useHeuristicCE) { for (const GroupIdType groupId : groupVector) { // Invalid tree: node is its own child. @@ -708,7 +726,7 @@ MemoLogicalNodeId Memo::addNode(GroupIdVector groupVector, // Current node is not in the memo. Insert unchanged. const GroupIdType groupId = noTargetGroup ? addGroup(std::move(projections)) : targetGroupId; - auto [newId, inserted] = addNode(groupId, std::move(n)); + auto [newId, inserted] = addNode(groupId, std::move(n), rule); if (inserted || noTargetGroup) { insertedNodeIds.insert(newId); _inputGroupsToNodeIdMap[groupVector].insert(newId); @@ -735,12 +753,14 @@ MemoLogicalNodeId Memo::addNode(GroupIdVector groupVector, GroupIdType Memo::integrate(const ABT& node, NodeTargetGroupMap targetGroupMap, NodeIdSet& insertedNodeIds, + const LogicalRewriteType rule, const bool addExistingNodeWithNewChild, const bool useHeuristicCE) { _stats._numIntegrations++; MemoIntegrator integrator(*this, std::move(targetGroupMap), insertedNodeIds, + rule, addExistingNodeWithNewChild, useHeuristicCE); return integrator.integrate(node); @@ -763,6 +783,7 @@ void Memo::clearLogicalNodes(const GroupIdType groupId) { logicalNodes.clear(); group._logicalRewriteQueue = {}; + group._rules.clear(); } const Memo::InputGroupsToNodeIdMap& Memo::getInputGroupsToNodeIdMap() const { diff --git a/src/mongo/db/query/optimizer/cascades/memo.h b/src/mongo/db/query/optimizer/cascades/memo.h index 7038f236634..cb7a86c546d 100644 --- a/src/mongo/db/query/optimizer/cascades/memo.h +++ b/src/mongo/db/query/optimizer/cascades/memo.h @@ -37,6 +37,8 @@ #include "mongo/db/query/optimizer/cascades/ce_heuristic.h" #include "mongo/db/query/optimizer/cascades/interfaces.h" #include "mongo/db/query/optimizer/cascades/rewrite_queues.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" +#include "mongo/db/query/optimizer/defs.h" #include "mongo/db/query/optimizer/reference_tracker.h" namespace mongo::optimizer::cascades { @@ -81,6 +83,9 @@ struct PhysNodeInfo { // For display purposes, adjusted cardinality based on physical properties (e.g. Repetition and // Limit-Skip). CEType _adjustedCE; + + // Rule that triggered the creation of this node. + PhysicalRewriteType _rule; }; struct PhysOptimizationResult { @@ -141,6 +146,8 @@ struct Group { // Associated logical nodes. OrderPreservingABTSet _logicalNodes; + // Rule that triggered each logical node. + std::vector<LogicalRewriteType> _rules; // Group logical properties. properties::LogicalProps _logicalProperties; ABT _binder; @@ -208,11 +215,13 @@ public: GroupIdType targetGroupId, NodeIdSet& insertedNodeIds, ABT n, + LogicalRewriteType rule, bool useHeuristicCE = false); GroupIdType integrate(const ABT& node, NodeTargetGroupMap targetGroupMap, NodeIdSet& insertedNodeIds, + LogicalRewriteType rule = LogicalRewriteType::Root, bool addExistingNodeWithNewChild = false, bool useHeuristicCE = false); @@ -234,7 +243,7 @@ public: private: GroupIdType addGroup(ProjectionNameSet projections); - std::pair<MemoLogicalNodeId, bool> addNode(GroupIdType groupId, ABT n); + std::pair<MemoLogicalNodeId, bool> addNode(GroupIdType groupId, ABT n, LogicalRewriteType rule); std::pair<MemoLogicalNodeId, bool> findNode(const GroupIdVector& groups, const ABT& node); diff --git a/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp b/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp index 9be06e8b76b..526fa8468b4 100644 --- a/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp +++ b/src/mongo/db/query/optimizer/cascades/physical_rewriter.cpp @@ -31,8 +31,9 @@ #include "mongo/db/query/optimizer/cascades/enforcers.h" #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/memo_utils.h" +#include "mongo/db/query/optimizer/utils/rewriter_utils.h" namespace mongo::optimizer::cascades { @@ -137,6 +138,7 @@ static void printCandidateInfo(const ABT& node, void PhysicalRewriter::costAndRetainBestNode(ABT node, ChildPropsType childProps, NodeCEMap nodeCEMap, + const PhysicalRewriteType rule, const GroupIdType groupId, PrefixId& prefixId, PhysOptimizationResult& bestResult) { @@ -163,8 +165,11 @@ void PhysicalRewriter::costAndRetainBestNode(ABT node, 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}; + unwrapConstFilter(std::move(node)), cost, nodeCost, nodeCostAndCE._ce, rule}; const bool keepRejectedPlans = _hints._keepRejectedPlans; if (improvement) { if (keepRejectedPlans && bestResult._nodeInfo) { @@ -371,6 +376,7 @@ PhysicalRewriter::OptimizeGroupResult PhysicalRewriter::optimizeGroup(const Grou costAndRetainBestNode(std::move(rewrite._node), std::move(rewrite._childProps), std::move(nodeCEMap), + rewrite._rule, groupId, prefixId, bestResult); diff --git a/src/mongo/db/query/optimizer/cascades/physical_rewriter.h b/src/mongo/db/query/optimizer/cascades/physical_rewriter.h index 0e59e732845..592be39ac20 100644 --- a/src/mongo/db/query/optimizer/cascades/physical_rewriter.h +++ b/src/mongo/db/query/optimizer/cascades/physical_rewriter.h @@ -72,6 +72,7 @@ private: void costAndRetainBestNode(ABT node, ChildPropsType childProps, NodeCEMap nodeCEMap, + PhysicalRewriteType rule, GroupIdType groupId, PrefixId& prefixId, PhysOptimizationResult& bestResult); diff --git a/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp b/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp index 8d0ef6809b7..c27ed44dd84 100644 --- a/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp +++ b/src/mongo/db/query/optimizer/cascades/rewrite_queues.cpp @@ -28,13 +28,14 @@ */ #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 { LogicalRewriteEntry::LogicalRewriteEntry(const double priority, - LogicalRewriteType type, + const LogicalRewriteType type, MemoLogicalNodeId nodeId) : _priority(priority), _type(type), _nodeId(nodeId) {} @@ -59,18 +60,12 @@ bool LogicalRewriteEntryComparator::operator()( void optimizeChildrenNoAssert(PhysRewriteQueue& queue, const double priority, + const PhysicalRewriteType rule, ABT node, ChildPropsType childProps, NodeCEMap nodeCEMap) { queue.emplace(std::make_unique<PhysRewriteEntry>( - priority, std::move(node), std::move(childProps), std::move(nodeCEMap))); -} - -void optimizeUnderNewProperties(cascades::PhysRewriteQueue& queue, - const double priority, - ABT child, - properties::PhysProps props) { - optimizeChild<FilterNode>(queue, priority, wrapConstFilter(std::move(child)), std::move(props)); + priority, rule, 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 a64b7d000a1..b8e6ec66530 100644 --- a/src/mongo/db/query/optimizer/cascades/rewrite_queues.h +++ b/src/mongo/db/query/optimizer/cascades/rewrite_queues.h @@ -31,8 +31,9 @@ #include <queue> -#include "mongo/db/query/optimizer/cascades/logical_rewriter_rules.h" +#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 { @@ -72,7 +73,11 @@ static constexpr double kDefaultPriority = 10.0; * Keeps track of candidate physical rewrites. */ struct PhysRewriteEntry { - PhysRewriteEntry(double priority, ABT node, ChildPropsType childProps, NodeCEMap nodeCEMap); + PhysRewriteEntry(double priority, + PhysicalRewriteType rule, + ABT node, + ChildPropsType childProps, + NodeCEMap nodeCEMap); PhysRewriteEntry() = delete; PhysRewriteEntry(const PhysRewriteEntry& other) = delete; @@ -80,6 +85,8 @@ struct PhysRewriteEntry { // Numerically lower priority gets applied first. double _priority; + // Rewrite rule that triggered this entry. + PhysicalRewriteType _rule; ABT _node; ChildPropsType _childProps; @@ -98,40 +105,46 @@ using PhysRewriteQueue = std::priority_queue<std::unique_ptr<PhysRewriteEntry>, void optimizeChildrenNoAssert(PhysRewriteQueue& queue, double priority, + PhysicalRewriteType rule, ABT node, ChildPropsType childProps, - NodeCEMap nodeCEMap = {}); + NodeCEMap nodeCEMap); -template <class T> +template <class T, PhysicalRewriteType rule> static void optimizeChildren(PhysRewriteQueue& queue, double priority, ABT node, ChildPropsType childProps) { static_assert(canBePhysicalNode<T>(), "Can only optimize a physical node."); - optimizeChildrenNoAssert(queue, priority, std::move(node), std::move(childProps)); + optimizeChildrenNoAssert(queue, priority, rule, std::move(node), std::move(childProps), {}); } -template <class T> +template <class T, PhysicalRewriteType rule> static void optimizeChild(PhysRewriteQueue& queue, double priority, ABT node, properties::PhysProps childProps) { ABT& childRef = node.cast<T>()->getChild(); - optimizeChildren<T>( + optimizeChildren<T, rule>( queue, priority, std::move(node), ChildPropsType{{&childRef, std::move(childProps)}}); } -template <class T> +template <class T, PhysicalRewriteType rule> static void optimizeChild(PhysRewriteQueue& queue, const double priority, ABT node) { - optimizeChildren<T>(queue, priority, std::move(node), {}); + optimizeChildren<T, rule>(queue, priority, std::move(node), {}); } -void optimizeUnderNewProperties(PhysRewriteQueue& queue, - double priority, + +template <PhysicalRewriteType rule> +void optimizeUnderNewProperties(cascades::PhysRewriteQueue& queue, + const double priority, ABT child, - properties::PhysProps props); + properties::PhysProps props) { + optimizeChild<FilterNode, rule>( + queue, priority, wrapConstFilter(std::move(child)), std::move(props)); +} -template <class T> +template <class T, PhysicalRewriteType rule> static void optimizeChildren(PhysRewriteQueue& queue, double priority, ABT node, @@ -139,7 +152,7 @@ static void optimizeChildren(PhysRewriteQueue& queue, properties::PhysProps rightProps) { ABT& leftChildRef = node.cast<T>()->getLeftChild(); ABT& rightChildRef = node.cast<T>()->getRightChild(); - optimizeChildren<T>( + optimizeChildren<T, rule>( queue, priority, std::move(node), diff --git a/src/mongo/db/query/optimizer/cascades/logical_rewriter_rules.h b/src/mongo/db/query/optimizer/cascades/rewriter_rules.h index 227b2b7ba03..4f564434032 100644 --- a/src/mongo/db/query/optimizer/cascades/logical_rewriter_rules.h +++ b/src/mongo/db/query/optimizer/cascades/rewriter_rules.h @@ -34,6 +34,7 @@ namespace mongo::optimizer::cascades { #define LOGICALREWRITER_NAMES(F) \ + F(Root) \ /* "Linear" reordering rewrites. */ \ F(FilterEvaluationReorder) \ F(FilterCollationReorder) \ @@ -87,4 +88,40 @@ MAKE_PRINTABLE_ENUM_STRING_ARRAY(LogicalRewriterTypeEnum, LOGICALREWRITER_NAMES); #undef LOGICALREWRITER_NAMES +#define PHYSICALREWRITER_NAMES(F) \ + F(Root) \ + F(Uninitialized) \ + F(EnforceCollation) \ + F(EnforceLimitSkip) \ + F(EnforceDistribution) \ + F(AttemptCoveringQuery) \ + F(Seek) \ + F(PhysicalScan) \ + F(ValueScan) \ + F(Evaluation) \ + F(Union) \ + F(LimitSkip) \ + F(HashGroup) \ + F(Unwind) \ + F(Collation) \ + F(Exchange) \ + F(NLJ) \ + F(Filter) \ + F(RenameProjection) \ + F(EvaluationPassthrough) \ + F(SargableIxScanConvert) \ + F(SargableToIndex) \ + F(SargableToPhysicalScan) \ + F(SargableToSeek) \ + F(RIDIntersectMergeJoin) \ + F(RIDIntersectHashJoin) \ + F(RIDIntersectGroupBy) \ + F(RIDIntersectNLJ) + +MAKE_PRINTABLE_ENUM(PhysicalRewriteType, PHYSICALREWRITER_NAMES); +MAKE_PRINTABLE_ENUM_STRING_ARRAY(PhysicalRewriterTypeEnum, + PhysicalRewriterType, + PHYSICALREWRITER_NAMES); +#undef PHYSICALREWRITER_NAMES + } // namespace mongo::optimizer::cascades diff --git a/src/mongo/db/query/optimizer/explain.cpp b/src/mongo/db/query/optimizer/explain.cpp index bb2973c31c3..206b7bf0d8b 100644 --- a/src/mongo/db/query/optimizer/explain.cpp +++ b/src/mongo/db/query/optimizer/explain.cpp @@ -31,6 +31,8 @@ #include "mongo/db/exec/sbe/values/bson.h" #include "mongo/db/query/optimizer/cascades/memo.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" +#include "mongo/db/query/optimizer/defs.h" #include "mongo/db/query/optimizer/node.h" #include "mongo/util/assert_util.h" @@ -2203,7 +2205,11 @@ public: const ABTVector& logicalNodes = group._logicalNodes.getVector(); for (size_t i = 0; i < logicalNodes.size(); i++) { ExplainPrinter local; - local.fieldName("logicalNodeId").print(i); + local.fieldName("logicalNodeId").print(i).separator(", "); + const auto rule = group._rules.at(i); + local.fieldName("rule").print( + cascades::LogicalRewriterTypeEnum::toString[static_cast<int>(rule)]); + ExplainPrinter nodePrinter = generate(logicalNodes.at(i)); local.fieldName("node", ExplainVersion::V3).print(nodePrinter); @@ -2230,6 +2236,12 @@ public: local.print(physOptResult->_costLimit.getCost()); } + if (physOptResult->_nodeInfo) { + const cascades::PhysicalRewriteType rule = physOptResult->_nodeInfo->_rule; + local.separator(", ").fieldName("rule").print( + cascades::PhysicalRewriterTypeEnum::toString[static_cast<int>(rule)]); + } + ExplainPrinter propPrinter = printPhysProps("Physical properties", physOptResult->_physProps); local.fieldName("physicalProperties", ExplainVersion::V3).print(propPrinter); 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 d5664d3cc2b..9912c2fb5a2 100644 --- a/src/mongo/db/query/optimizer/logical_rewriter_optimizer_test.cpp +++ b/src/mongo/db/query/optimizer/logical_rewriter_optimizer_test.cpp @@ -29,6 +29,7 @@ #include "mongo/db/query/optimizer/cascades/ce_heuristic.h" #include "mongo/db/query/optimizer/cascades/logical_props_derivation.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" #include "mongo/db/query/optimizer/explain.h" #include "mongo/db/query/optimizer/node.h" #include "mongo/db/query/optimizer/opt_phase_manager.h" @@ -138,7 +139,7 @@ TEST(LogicalRewriter, Memo) { " | | distribution: \n" " | | type: Centralized\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Scan [test]\n" " | BindBlock:\n" " | [ptest]\n" @@ -158,7 +159,7 @@ TEST(LogicalRewriter, Memo) { " | | distribution: \n" " | | type: Centralized\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Filter []\n" " | | EvalFilter []\n" " | | | Variable [ptest]\n" @@ -182,7 +183,7 @@ TEST(LogicalRewriter, Memo) { " | | distribution: \n" " | | type: Centralized\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Evaluation []\n" " | | BindBlock:\n" " | | [P1]\n" @@ -1234,7 +1235,7 @@ TEST(LogicalRewriter, UnionPreservesCommonLogicalProps) { " | | distribution: \n" " | | type: UnknownPartitioning\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Scan [test1]\n" " | BindBlock:\n" " | [ptest1]\n" @@ -1266,7 +1267,7 @@ TEST(LogicalRewriter, UnionPreservesCommonLogicalProps) { " | | distribution: \n" " | | type: UnknownPartitioning\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Sargable [Complete]\n" " | | | | | | requirementsMap: \n" " | | | | | | refProjection: ptest1, path: 'PathGet [a] " @@ -1296,7 +1297,7 @@ TEST(LogicalRewriter, UnionPreservesCommonLogicalProps) { " | | distribution: \n" " | | type: UnknownPartitioning\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Scan [test2]\n" " | BindBlock:\n" " | [ptest2]\n" @@ -1328,7 +1329,7 @@ TEST(LogicalRewriter, UnionPreservesCommonLogicalProps) { " | | distribution: \n" " | | type: UnknownPartitioning\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Sargable [Complete]\n" " | | | | | | requirementsMap: \n" " | | | | | | refProjection: ptest2, path: 'PathGet [a] " @@ -1364,7 +1365,7 @@ TEST(LogicalRewriter, UnionPreservesCommonLogicalProps) { " | | distribution: \n" " | | type: UnknownPartitioning\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Union []\n" " | | | BindBlock:\n" " | | | [a]\n" @@ -1393,7 +1394,7 @@ TEST(LogicalRewriter, UnionPreservesCommonLogicalProps) { " | | distribution: \n" " | | type: UnknownPartitioning\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Root []\n" " | | | projections: \n" " | | | a\n" @@ -1404,10 +1405,7 @@ TEST(LogicalRewriter, UnionPreservesCommonLogicalProps) { phaseManager.getMemo()); } -TEST(LogicalRewriter, SargableCE) { - using namespace properties; - PrefixId prefixId; - +ABT sargableCETestSetup() { ABT scanNode = make<ScanNode>("ptest", "test"); ABT filterANode = make<FilterNode>( @@ -1419,9 +1417,15 @@ TEST(LogicalRewriter, SargableCE) { make<Variable>("ptest")), std::move(filterANode)); - ABT rootNode = make<RootNode>(properties::ProjectionRequirement{ProjectionNameVector{"ptest"}}, - std::move(filterBNode)); + return make<RootNode>(properties::ProjectionRequirement{ProjectionNameVector{"ptest"}}, + std::move(filterBNode)); +} +TEST(LogicalRewriter, SargableCE) { + using namespace properties; + + PrefixId prefixId; + ABT rootNode = sargableCETestSetup(); OptPhaseManager phaseManager({OptPhaseManager::OptPhase::MemoSubstitutionPhase, OptPhaseManager::OptPhase::MemoExplorationPhase}, prefixId, @@ -1447,7 +1451,7 @@ TEST(LogicalRewriter, SargableCE) { " | | distribution: \n" " | | type: Centralized\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Scan [test]\n" " | BindBlock:\n" " | [ptest]\n" @@ -1472,7 +1476,7 @@ TEST(LogicalRewriter, SargableCE) { " | | distribution: \n" " | | type: Centralized\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Sargable [Complete]\n" " | | | | | | requirementsMap: \n" " | | | | | | refProjection: ptest, path: 'PathGet [a] " @@ -1506,7 +1510,7 @@ TEST(LogicalRewriter, SargableCE) { " | | distribution: \n" " | | type: Centralized\n" " | logicalNodes: \n" - " | logicalNodeId: 0\n" + " | logicalNodeId: 0, rule: Root\n" " | Root []\n" " | | | projections: \n" " | | | ptest\n" diff --git a/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp b/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp index ac07379ea77..19738412d93 100644 --- a/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp +++ b/src/mongo/db/query/optimizer/physical_rewriter_optimizer_test.cpp @@ -30,6 +30,7 @@ #include "mongo/db/query/optimizer/cascades/ce_heuristic.h" #include "mongo/db/query/optimizer/cascades/ce_hinted.h" #include "mongo/db/query/optimizer/cascades/cost_derivation.h" +#include "mongo/db/query/optimizer/cascades/rewriter_rules.h" #include "mongo/db/query/optimizer/explain.h" #include "mongo/db/query/optimizer/metadata.h" #include "mongo/db/query/optimizer/node.h" @@ -1060,6 +1061,45 @@ TEST(PhysRewriter, FilterIndexing2NonSarg) { " [rid_0]\n" " Source []\n", optimized); + + LogicalRewriteType logicalRules[] = {LogicalRewriteType::Root, + LogicalRewriteType::Root, + LogicalRewriteType::SargableSplit, + LogicalRewriteType::SargableSplit, + LogicalRewriteType::EvaluationRIDIntersectReorder, + LogicalRewriteType::Root, + LogicalRewriteType::FilterRIDIntersectReorder, + LogicalRewriteType::Root, + LogicalRewriteType::SargableSplit, + LogicalRewriteType::EvaluationRIDIntersectReorder, + LogicalRewriteType::FilterRIDIntersectReorder}; + PhysicalRewriteType physicalRules[] = {PhysicalRewriteType::Seek, + PhysicalRewriteType::Seek, + PhysicalRewriteType::RIDIntersectNLJ, + PhysicalRewriteType::Evaluation, + PhysicalRewriteType::RIDIntersectNLJ, + PhysicalRewriteType::Root, + PhysicalRewriteType::SargableToIndex, + PhysicalRewriteType::SargableToIndex, + PhysicalRewriteType::Evaluation, + PhysicalRewriteType::Evaluation, + PhysicalRewriteType::Filter}; + + int logicalRuleIndex = 0; + int physicalRuleIndex = 0; + const Memo& memo = phaseManager.getMemo(); + for (size_t groupId = 0; groupId < memo.getGroupCount(); groupId++) { + const Group& group = memo.getGroup(groupId); + for (const auto rule : group._rules) { + ASSERT(rule == logicalRules[logicalRuleIndex]); + logicalRuleIndex++; + } + for (const auto& physOptResult : group._physicalNodes.getNodes()) { + const auto rule = physOptResult->_nodeInfo->_rule; + ASSERT(rule == physicalRules[physicalRuleIndex]); + physicalRuleIndex++; + } + } } TEST(PhysRewriter, FilterIndexing3) { diff --git a/src/mongo/db/query/optimizer/utils/memo_utils.cpp b/src/mongo/db/query/optimizer/utils/memo_utils.cpp index 9dfa3e595a2..e4faab813f7 100644 --- a/src/mongo/db/query/optimizer/utils/memo_utils.cpp +++ b/src/mongo/db/query/optimizer/utils/memo_utils.cpp @@ -34,18 +34,6 @@ 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; -} - class MemoLatestPlanExtractor { public: explicit MemoLatestPlanExtractor(const cascades::Memo& memo) : _memo(memo) {} diff --git a/src/mongo/db/query/optimizer/utils/memo_utils.h b/src/mongo/db/query/optimizer/utils/memo_utils.h index af28a2c3ef8..1363633b9c5 100644 --- a/src/mongo/db/query/optimizer/utils/memo_utils.h +++ b/src/mongo/db/query/optimizer/utils/memo_utils.h @@ -37,9 +37,6 @@ namespace mongo::optimizer { -ABT wrapConstFilter(ABT node); -ABT unwrapConstFilter(ABT node); - template <class ToAddType, class ToRemoveType> static void addRemoveProjectionsToProperties(properties::PhysProps& properties, const ToAddType& toAdd, diff --git a/src/mongo/db/query/optimizer/utils/rewriter_utils.cpp b/src/mongo/db/query/optimizer/utils/rewriter_utils.cpp new file mode 100644 index 00000000000..88c1427c8df --- /dev/null +++ b/src/mongo/db/query/optimizer/utils/rewriter_utils.cpp @@ -0,0 +1,47 @@ +/** + * 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 new file mode 100644 index 00000000000..e81190a5ce6 --- /dev/null +++ b/src/mongo/db/query/optimizer/utils/rewriter_utils.h @@ -0,0 +1,40 @@ +/** + * 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 |