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