TransformationRules.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / TransformationRules.cs / 1305376 / TransformationRules.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System; 
using System.Collections.Generic;
using System.Collections.ObjectModel;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization; 
using System.Linq;
using System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees; 

namespace System.Data.Query.PlanCompiler 
{
    internal class TransformationRulesContext : RuleProcessingContext
    {
        #region public methods and properties 

        ///  
        /// Whether any rule was applied that may have caused modifications such that projection pruning 
        /// may be useful
        ///  
        internal bool ProjectionPrunningRequired { get { return this.m_projectionPrunningRequired; } }

        /// 
        /// Whether any rule was applied that may have caused modifications such that reapplying 
        /// the nullability rules may be useful
        ///  
        internal bool ReapplyNullabilityRules { get { return this.m_reapplyNullabilityRules; } } 

        ///  
        /// Remap the given subree using the current remapper
        /// 
        /// 
        internal void RemapSubtree(Node subTree) 
        {
            this.m_remapper.RemapSubtree(subTree); 
        } 

        ///  
        /// Adds a mapping from oldVar to newVar
        /// 
        /// 
        ///  
        internal void AddVarMapping(Var oldVar, Var newVar)
        { 
            m_remapper.AddMapping(oldVar, newVar); 
            m_remappedVars.Set(oldVar);
        } 

        /// 
        /// "Remap" an expression tree, replacing all references to vars in varMap with
        /// copies of the corresponding expression 
        /// The subtree is modified *inplace* - it is the caller's responsibility to make
        /// a copy of the subtree if necessary. 
        /// The "replacement" expression (the replacement for the VarRef) is copied and then 
        /// inserted into the appropriate location into the subtree.
        /// 
        /// Note: we only support replacements in simple ScalarOp trees. This must be
        /// validated by the caller.
        ///
        ///  
        /// Current subtree to process
        ///  
        /// The updated subtree 
        internal Node ReMap(Node node, Dictionary varMap)
        { 
            PlanCompiler.Assert(node.Op.IsScalarOp, "Expected a scalarOp: Found " + Dump.AutoString.ToString(node.Op.OpType));

            // Replace varRefOps by the corresponding expression in the map, if any
            if (node.Op.OpType == OpType.VarRef) 
            {
                VarRefOp varRefOp = node.Op as VarRefOp; 
                Node newNode = null; 
                if (varMap.TryGetValue(varRefOp.Var, out newNode))
                { 
                    newNode = this.Copy(newNode);
                    return newNode;
                }
                else 
                {
                    return node; 
                } 
            }
 
            // Simply process the result of the children.
            for (int i = 0; i < node.Children.Count; i++)
            {
                node.Children[i] = ReMap(node.Children[i], varMap); 
            }
 
            // We may have changed something deep down 
            this.Command.RecomputeNodeInfo(node);
            return node; 
        }

        /// 
        /// Makes a copy of the appropriate subtree - with a simple accelerator for VarRefOp 
        /// since that's likely to be the most command case
        ///  
        /// the subtree to copy 
        /// the copy of the subtree
        internal Node Copy(Node node) 
        {
            if (node.Op.OpType == OpType.VarRef)
            {
                VarRefOp op = node.Op as VarRefOp; 
                return this.Command.CreateNode(this.Command.CreateVarRefOp(op.Var));
            } 
            else 
            {
                return OpCopier.Copy(this.Command, node); 
            }
        }

        ///  
        /// Checks to see if the current subtree only contains ScalarOps
        ///  
        /// current subtree 
        /// true, if the subtree contains only ScalarOps
        internal bool IsScalarOpTree(Node node) 
        {
            int nodeCount = 0;
            return IsScalarOpTree(node, null, ref nodeCount);
        } 

        ///  
        /// Is the given var guaranteed to be non-nullable with regards to the node 
        /// that is currently being processed.
        /// True, if it is listed as such on any on the node infos on any of the 
        /// current relop ancestors.
        /// 
        /// 
        ///  
        internal bool IsNonNullable(Var var)
        { 
            foreach (Node relOpAncestor in m_relOpAncestors) 
            {
                // Rules applied to the children of the relOpAncestor may have caused it change. 
                // Thus, if the node is used, it has to have its node info recomputed
                Command.RecomputeNodeInfo(relOpAncestor);
                ExtendedNodeInfo nodeInfo = Command.GetExtendedNodeInfo(relOpAncestor);
                if (nodeInfo.NonNullableVisibleDefinitions.IsSet(var)) 
                {
                    return true; 
                } 
                else if (nodeInfo.LocalDefinitions.IsSet(var))
                { 
                    //The var is defined on this ancestor but is not non-nullable,
                    // therefore there is no need to further check other ancestors
                    return false;
                } 
            }
            return false; 
        } 

        ///  
        /// Is it safe to use a null sentinel with any value?
        /// It may not be safe if:
        /// 1. The top most sort includes null sentinels. If the null sentinel is replaced with a different value
        /// and is used as a sort key it may change the sorting results 
        /// 2. If any of the ancestors is Distinct, GroupBy, Intersect or Except,
        /// because the null sentinel may be used as a key. 
        /// 3. If the null sentinel is defined in the left child of an apply it may be used at the right side, 
        /// thus in these cases we also verify that the right hand side does not have any Distinct, GroupBy,
        /// Intersect or Except. 
        /// 
        internal bool CanChangeNullSentinelValue
        {
            get 
            {
                //Is there a sort that includes null sentinels 
                if (this.m_compilerState.HasSortingOnNullSentinels) 
                {
                    return false; 
                }

                //Is any of the ancestors Distinct, GroupBy, Intersect or Except
                if (this.m_relOpAncestors.Any(a => IsOpNotSafeForNullSentinelValueChange(a.Op.OpType))) 
                {
                    return false; 
                } 

                // Is the null sentinel defined in the left child of an apply and if so, 
                // does the right hand side have any Distinct, GroupBy, Intersect or Except.
                var applyAncestors = this.m_relOpAncestors.Where(a =>
                         a.Op.OpType == OpType.CrossApply ||
                         a.Op.OpType == OpType.OuterApply); 

                //If the sentinel comes from the right hand side it is ok. 
                foreach (Node applyAncestor in applyAncestors) 
                {
                    if (!this.m_relOpAncestors.Contains(applyAncestor.Child1) && HasOpNotSafeForNullSentinelValueChange(applyAncestor.Child1)) 
                    {
                        return false;
                    }
                } 
                return true;
            } 
        } 

        ///  
        /// Is the op not safe for null sentinel value change
        /// 
        /// 
        ///  
        internal static bool IsOpNotSafeForNullSentinelValueChange(OpType optype)
        { 
            return optype == OpType.Distinct || 
                    optype == OpType.GroupBy ||
                    optype == OpType.Intersect || 
                    optype == OpType.Except;
        }

        ///  
        /// Does the given subtree contain a node with an op that
        /// is not safer for null sentinel value change 
        ///  
        /// 
        ///  
        internal static bool HasOpNotSafeForNullSentinelValueChange(Node n)
        {
            if (IsOpNotSafeForNullSentinelValueChange(n.Op.OpType))
            { 
                return true;
            } 
            foreach (Node child in n.Children) 
            {
                if (HasOpNotSafeForNullSentinelValueChange(child)) 
                {
                    return true;
                }
            } 
            return false;
        } 
 
        /// 
        /// Is this is a scalar-op tree? Also return a dictionary of var refcounts (ie) 
        /// for each var encountered in the tree, determine the number of times it has
        /// been seen
        /// 
        /// current subtree 
        /// dictionary of var refcounts to fill in
        ///  
        internal bool IsScalarOpTree(Node node, Dictionary varRefMap) 
        {
            PlanCompiler.Assert(varRefMap != null, "Null varRef map"); 

            int nodeCount = 0;
            return IsScalarOpTree(node, varRefMap, ref nodeCount);
        } 

        ///  
        /// Get a mapping from Var->Expression for a VarDefListOp tree. This information 
        /// will be used by later stages to replace all references to the Vars by the
        /// corresponding expressions 
        ///
        /// This function uses a few heuristics along the way. It uses the varRefMap
        /// parameter to determine if a computed Var (defined by this VarDefListOp)
        /// has been referenced multiple times, and if it has, it checks to see if 
        /// the defining expression is too big (> 100 nodes). This is to avoid
        /// bloating up the entire query tree with too many copies. 
        /// 
        /// 
        /// The varDefListOp subtree 
        /// ref counts for each referenced var
        /// mapping from Var->replacement xpressions
        internal Dictionary GetVarMap(Node varDefListNode, Dictionary varRefMap)
        { 
            VarDefListOp varDefListOp = (VarDefListOp)varDefListNode.Op;
 
            Dictionary varMap = new Dictionary(); 
            foreach (Node chi in varDefListNode.Children)
            { 
                VarDefOp varDefOp = (VarDefOp)chi.Op;
                int nonLeafNodeCount = 0;
                int refCount = 0;
                if (!IsScalarOpTree(chi.Child0, null, ref nonLeafNodeCount)) 
                {
                    return null; 
                } 
                //
                // More heuristics. If there are multiple references to this Var *and* 
                // the defining expression for the Var is "expensive" (ie) has larger than
                // 100 nodes, then simply pretend that this is too hard to do
                // Note: we check for more than 2 references, (rather than just more than 1) - this
                // is simply to let some additional cases through 
                //
                if ((nonLeafNodeCount > 100) && 
                    (varRefMap != null) && 
                    varRefMap.TryGetValue(varDefOp.Var, out refCount) &&
                    (refCount > 2)) 
                {
                    return null;
                }
 
                Node n;
                if (varMap.TryGetValue(varDefOp.Var, out n)) 
                { 
                    PlanCompiler.Assert(n == chi.Child0, "reusing varDef for different Node?");
                } 
                else
                {
                    varMap.Add(varDefOp.Var, chi.Child0);
                } 
            }
 
            return varMap; 
        }
 
        /// 
        /// Builds a NULLIF expression (ie) a Case expression that looks like
        ///    CASE WHEN v is null THEN null ELSE expr END
        /// where v is the conditionVar parameter, and expr is the value of the expression 
        /// when v is non-null
        ///  
        /// null discriminator var 
        /// expression
        ///  
        internal Node BuildNullIfExpression(Var conditionVar, Node expr)
        {
            VarRefOp varRefOp = this.Command.CreateVarRefOp(conditionVar);
            Node varRefNode = this.Command.CreateNode(varRefOp); 
            Node whenNode = this.Command.CreateNode(this.Command.CreateConditionalOp(OpType.IsNull), varRefNode);
            Node elseNode = expr; 
            Node thenNode = this.Command.CreateNode(this.Command.CreateNullOp(elseNode.Op.Type)); 
            Node caseNode = this.Command.CreateNode(this.Command.CreateCaseOp(elseNode.Op.Type), whenNode, thenNode, elseNode);
 
            return caseNode;
        }

        #region Rule Interactions 
        /// 
        /// Shut off filter pushdown for this subtree 
        ///  
        /// 
        internal void SuppressFilterPushdown(Node n) 
        {
            m_suppressions[n] = n;
        }
 
        /// 
        /// Is filter pushdown shut off for this subtree? 
        ///  
        /// 
        ///  
        internal bool IsFilterPushdownSuppressed(Node n)
        {
            return m_suppressions.ContainsKey(n);
        } 

        ///  
        /// Given a list of vars try to get one that is of type Int32 
        /// 
        ///  
        /// 
        /// 
        internal static bool TryGetInt32Var(IEnumerable varList, out Var int32Var)
        { 
            foreach (Var v in varList)
            { 
                // Any Int32 var regardless of the fasets will do 
                System.Data.Metadata.Edm.PrimitiveTypeKind typeKind;
                if (System.Data.Common.TypeHelpers.TryGetPrimitiveTypeKind(v.Type, out typeKind) && typeKind == System.Data.Metadata.Edm.PrimitiveTypeKind.Int32) 
                {
                    int32Var = v;
                    return true;
                } 
            }
            int32Var = null; 
            return false; 
        }
 
        #endregion

        #endregion
 
        #region constructors
        internal TransformationRulesContext(PlanCompiler compilerState) 
            : base(compilerState.Command) 
        {
            m_compilerState = compilerState; 
            m_remapper = new VarRemapper(compilerState.Command);
            m_suppressions = new Dictionary();
            m_remappedVars = compilerState.Command.CreateVarVec();
        } 

        #endregion 
 
        #region private state
        private readonly PlanCompiler m_compilerState; 
        private readonly VarRemapper m_remapper;
        private readonly Dictionary m_suppressions;
        private readonly VarVec m_remappedVars;
        private bool m_projectionPrunningRequired = false; 
        private bool m_reapplyNullabilityRules = false;
        private Stack m_relOpAncestors = new Stack(); 
#if DEBUG 
        /// 
        /// Used to see all the applied rules. 
        /// One way to use it is to put a conditional breakpoint at the end of
        /// PostProcessSubTree with the condition m_relOpAncestors.Count == 0
        /// 
        internal readonly System.Text.StringBuilder appliedRules = new System.Text.StringBuilder(); 
#endif
        #endregion 
 
        #region RuleProcessingContext Overrides
        ///  
        /// Callback function to invoke *before* rules are applied.
        /// Calls the VarRemapper to update any Vars in this node, and recomputes
        /// the nodeinfo
        ///  
        /// 
        internal override void PreProcess(Node n) 
        { 
            m_remapper.RemapNode(n);
            Command.RecomputeNodeInfo(n); 
        }

        /// 
        /// Callback function to invoke *before* rules are applied. 
        /// Calls the VarRemapper to update any Vars in the entire subtree
        /// If the given node has a RelOp it is pushed on the relOp ancestors stack. 
        ///  
        /// 
        internal override void PreProcessSubTree(Node subTree) 
        {
            if (subTree.Op.IsRelOp)
            {
                m_relOpAncestors.Push(subTree); 
            }
 
            if (m_remappedVars.IsEmpty) 
            {
                return; 
            }

            NodeInfo nodeInfo = this.Command.GetNodeInfo(subTree);
 
            //We need to do remapping only if m_remappedVars overlaps with nodeInfo.ExternalReferences
            foreach (Var v in nodeInfo.ExternalReferences) 
            { 
                if (m_remappedVars.IsSet(v))
                { 
                    m_remapper.RemapSubtree(subTree);
                    break;
                }
            } 
        }
 
        ///  
        /// If the given node has a RelOp it is popped from the relOp ancestors stack.
        ///  
        /// 
        internal override void PostProcessSubTree(Node subtree)
        {
            if (subtree.Op.IsRelOp) 
            {
                PlanCompiler.Assert(m_relOpAncestors.Count != 0, "The RelOp ancestors stack is empty when post processing a RelOp subtree"); 
                Node poppedNode = m_relOpAncestors.Pop(); 
                PlanCompiler.Assert(Object.ReferenceEquals(subtree, poppedNode), "The popped ancestor is not equal to the root of the subtree being post processed");
            } 
        }

        /// 
        /// Callback function to invoke *after* rules are applied 
        /// Recomputes the node info, if this node has changed
        /// If the rule is among the rules after which projection pruning may be beneficial, 
        /// m_projectionPrunningRequired is set to true. 
        /// If the rule is among the rules after which reapplying the nullability rules may be beneficial,
        /// m_reapplyNullabilityRules is set to true. 
        /// 
        /// 
        /// the rule that was applied
        internal override void PostProcess(Node n, InternalTrees.Rule rule) 
        {
            if (rule != null) 
            { 
#if DEBUG
                appliedRules.Append(rule.MethodName); 
                appliedRules.AppendLine();
#endif
                if (!this.m_projectionPrunningRequired && TransformationRules.RulesRequiringProjectionPruning.Contains(rule))
                { 
                    this.m_projectionPrunningRequired = true;
                } 
                if (!this.m_reapplyNullabilityRules && TransformationRules.RulesRequiringNullabilityRulesToBeReapplied.Contains(rule)) 
                {
                    this.m_reapplyNullabilityRules = true; 
                }
                Command.RecomputeNodeInfo(n);
            }
        } 

        ///  
        /// Get the hash value for this subtree 
        /// 
        ///  
        /// 
        internal override int GetHashCode(Node node)
        {
            NodeInfo nodeInfo = Command.GetNodeInfo(node); 
            return nodeInfo.HashValue;
        } 
        #endregion 

        #region private methods 
        /// 
        /// Check to see if the current subtree is a scalar-op subtree (ie) does
        /// the subtree only comprise of scalarOps?
        /// Additionally, compute the number of non-leaf nodes (ie) nodes with at least one child 
        /// that are found in the subtree. Note that this count is approximate - it is only
        /// intended to be used as a hint. It is the caller's responsibility to initialize 
        /// nodeCount to a sane value on entry into this function 
        /// And finally, if the varRefMap parameter is non-null, we keep track of
        /// how often a Var is referenced within the subtree 
        ///
        /// The non-leaf-node count and the varRefMap are used by GetVarMap to determine
        /// if expressions can be composed together
        ///  
        /// root of the subtree
        /// Ref counts for each Var encountered in the subtree 
        /// count of non-leaf nodes encountered in the subtree 
        /// true, if this node only contains scalarOps
        private bool IsScalarOpTree(Node node, Dictionary varRefMap, ref int nonLeafNodeCount) 
        {
            if (!node.Op.IsScalarOp)
            {
                return false; 
            }
 
            if (node.HasChild0) 
            {
                nonLeafNodeCount++; 
            }

            if (varRefMap != null && node.Op.OpType == OpType.VarRef)
            { 
                VarRefOp varRefOp = (VarRefOp)node.Op;
                int refCount; 
                if (!varRefMap.TryGetValue(varRefOp.Var, out refCount)) 
                {
                    refCount = 1; 
                }
                else
                {
                    refCount++; 
                }
                varRefMap[varRefOp.Var] = refCount; 
            } 

            foreach (Node chi in node.Children) 
            {
                if (!IsScalarOpTree(chi, varRefMap, ref nonLeafNodeCount))
                {
                    return false; 
                }
            } 
            return true; 
        }
        #endregion 
    }

    /// 
    /// The list of all transformation rules to apply 
    /// 
    internal static class TransformationRules 
    { 
        /// 
        /// A lookup table for built from all rules 
        /// The lookup table is an array indexed by OpType and each entry has a list of rules.
        /// 
        internal static readonly ReadOnlyCollection> AllRulesTable = BuildLookupTableForRules(AllRules);
 
        /// 
        /// A lookup table for built only from ProjectRules 
        /// The lookup table is an array indexed by OpType and each entry has a list of rules. 
        /// 
        internal static readonly ReadOnlyCollection> ProjectRulesTable = BuildLookupTableForRules(ProjectOpRules.Rules); 


        /// 
        /// A lookup table built only from rules that use key info 
        /// The lookup table is an array indexed by OpType and each entry has a list of rules.
        ///  
        internal static readonly ReadOnlyCollection> PostJoinEliminationRulesTable = BuildLookupTableForRules(PostJoinEliminationRules); 

        ///  
        /// A lookup table built only from rules that rely on nullability of vars and other rules
        /// that may be able to perform simplificatios if these have been applied.
        /// The lookup table is an array indexed by OpType and each entry has a list of rules.
        ///  
        internal static readonly ReadOnlyCollection> NullabilityRulesTable = BuildLookupTableForRules(NullabilityRules);
 
        ///  
        /// A look-up table of rules that may cause modifications such that projection pruning may be useful
        /// after they have been applied. 
        /// 
        internal static readonly HashSet RulesRequiringProjectionPruning = InitializeRulesRequiringProjectionPruning();

        ///  
        /// A look-up table of rules that may cause modifications such that reapplying the nullability rules
        /// may be useful after they have been applied. 
        ///  
        internal static readonly HashSet RulesRequiringNullabilityRulesToBeReapplied = InitializeRulesRequiringNullabilityRulesToBeReapplied();
 

        #region private state maintenance
        private static List allRules;
        private static List AllRules 
        {
            get 
            { 
                if (allRules == null)
                { 
                    allRules = new List();
                    allRules.AddRange(ScalarOpRules.Rules);
                    allRules.AddRange(FilterOpRules.Rules);
                    allRules.AddRange(ProjectOpRules.Rules); 
                    allRules.AddRange(ApplyOpRules.Rules);
                    allRules.AddRange(JoinOpRules.Rules); 
                    allRules.AddRange(SingleRowOpRules.Rules); 
                    allRules.AddRange(SetOpRules.Rules);
                    allRules.AddRange(GroupByOpRules.Rules); 
                    allRules.AddRange(SortOpRules.Rules);
                    allRules.AddRange(ConstrainedSortOpRules.Rules);
                    allRules.AddRange(DistinctOpRules.Rules);
                } 
                return allRules;
            } 
        } 

        private static List postJoinEliminationRules; 
        private static List PostJoinEliminationRules
        {
            get
            { 
                if (postJoinEliminationRules == null)
                { 
                    postJoinEliminationRules = new List(); 
                    postJoinEliminationRules.AddRange(ProjectOpRules.Rules); //these don't use key info per-se, but can help after the distinct op rules.
                    postJoinEliminationRules.AddRange(DistinctOpRules.Rules); 
                    postJoinEliminationRules.AddRange(FilterOpRules.Rules);
                    postJoinEliminationRules.AddRange(JoinOpRules.Rules);
                    postJoinEliminationRules.AddRange(NullabilityRules);
                } 
                return postJoinEliminationRules;
            } 
        } 

        private static List nullabilityRules; 
        private static List NullabilityRules
        {
            get
            { 
                if (nullabilityRules == null)
                { 
                    nullabilityRules = new List(); 
                    nullabilityRules.Add(ScalarOpRules.Rule_IsNullOverVarRef);
                    nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred1); 
                    nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred2);
                    nullabilityRules.Add(ScalarOpRules.Rule_SimplifyCase);
                }
                return nullabilityRules; 
            }
        } 
 
        private static ReadOnlyCollection> BuildLookupTableForRules(IEnumerable rules)
        { 
            ReadOnlyCollection NoRules = new ReadOnlyCollection(new InternalTrees.Rule[0]);

            List[] lookupTable = new List[(int)OpType.MaxMarker];
 
            foreach (InternalTrees.Rule rule in rules)
            { 
                List opRules = lookupTable[(int)rule.RuleOpType]; 
                if (opRules == null)
                { 
                    opRules = new List();
                    lookupTable[(int)rule.RuleOpType] = opRules;
                }
                opRules.Add(rule); 
            }
 
            ReadOnlyCollection[] rulesPerType = new ReadOnlyCollection[lookupTable.Length]; 
            for (int i = 0; i < lookupTable.Length; ++i)
            { 
                if (null != lookupTable[i])
                {
                    rulesPerType[i] = new ReadOnlyCollection(lookupTable[i].ToArray());
                } 
                else
                { 
                    rulesPerType[i] = NoRules; 
                }
            } 
            return new ReadOnlyCollection>(rulesPerType);
        }

        private static HashSet InitializeRulesRequiringProjectionPruning() 
        {
            HashSet rulesRequiringProjectionPruning = new HashSet(); 
 
            rulesRequiringProjectionPruning.Add(ApplyOpRules.Rule_OuterApplyOverProject);
 
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject1);
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject2);
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject1);
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject2); 
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_OuterJoinOverProject2);
 
            rulesRequiringProjectionPruning.Add(ProjectOpRules.Rule_ProjectWithNoLocalDefs); 

            rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterOverProject); 
            rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterWithConstantPredicate);

            rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOverProject);
            rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions); 

            return rulesRequiringProjectionPruning; 
        } 

        private static HashSet InitializeRulesRequiringNullabilityRulesToBeReapplied() 
        {
            HashSet rulesRequiringNullabilityRulesToBeReapplied = new HashSet();

            rulesRequiringNullabilityRulesToBeReapplied.Add(FilterOpRules.Rule_FilterOverLeftOuterJoin); 

            return rulesRequiringNullabilityRulesToBeReapplied; 
        } 

        #endregion 


        /// 
        /// Apply the rules that belong to the specified group to the given query tree. 
        /// 
        ///  
        ///  
        internal static bool Process(PlanCompiler compilerState, TransformationRulesGroup rulesGroup)
        { 
            ReadOnlyCollection> rulesTable = null;
            switch (rulesGroup)
            {
                case TransformationRulesGroup.All: 
                    rulesTable = AllRulesTable;
                    break; 
                case TransformationRulesGroup.PostJoinElimination: 
                    rulesTable = PostJoinEliminationRulesTable;
                    break; 
                case TransformationRulesGroup.Project:
                    rulesTable = ProjectRulesTable;
                    break;
            } 

            // If any rule has been applied after which reapplying nullability rules may be useful, 
            // reapply nullability rules. 
            bool projectionPrunningRequired;
            if (Process(compilerState, rulesTable, out projectionPrunningRequired)) 
            {
                bool projectionPrunningRequired2;
                Process(compilerState, NullabilityRulesTable, out projectionPrunningRequired2);
                projectionPrunningRequired = projectionPrunningRequired || projectionPrunningRequired2; 
            }
            return projectionPrunningRequired; 
        } 

        ///  
        /// Apply the rules that belong to the specified rules table to the given query tree.
        /// 
        /// 
        ///  
        /// is projection pruning  required after the rule application
        /// Whether any rule has been applied after which reapplying nullability rules may be useful 
        private static bool Process(PlanCompiler compilerState, ReadOnlyCollection> rulesTable, out bool projectionPruningRequired) 
        {
            RuleProcessor ruleProcessor = new RuleProcessor(); 
            TransformationRulesContext context = new TransformationRulesContext(compilerState);
            compilerState.Command.Root = ruleProcessor.ApplyRulesToSubtree(context, rulesTable, compilerState.Command.Root);
            projectionPruningRequired = context.ProjectionPrunningRequired;
            return context.ReapplyNullabilityRules; 
        }
    } 
 
    /// 
    /// Available groups of rules, not necessarily mutually exclusive 
    /// 
    internal enum TransformationRulesGroup
    {
        All, 
        Project,
        PostJoinElimination 
    } 

    #region ScalarOpRules 
    /// 
    /// Transformation rules for ScalarOps
    /// 
    internal static class ScalarOpRules 
    {
        #region CaseOp Rules 
        internal static readonly SimpleRule Rule_SimplifyCase = new SimpleRule(OpType.Case, ProcessSimplifyCase); 
        internal static readonly SimpleRule Rule_FlattenCase = new SimpleRule(OpType.Case, ProcessFlattenCase);
        ///  
        /// We perform the following simple transformation for CaseOps. If every single
        /// then/else expression in the CaseOp is equivalent, then we can simply replace
        /// the Op with the first then/expression. Specifically,
        /// case when w1 then t1 when w2 then t2 ... when wn then tn else e end 
        ///   => t1
        /// assuming that t1 is equivalent to t2 is equivalent to ... to e 
        ///  
        /// Rule Processing context
        /// The current subtree for the CaseOp 
        /// the (possibly) modified subtree
        /// true, if we performed any transformations
        static bool ProcessSimplifyCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
        { 
            CaseOp caseOp = (CaseOp)caseOpNode.Op;
            newNode = caseOpNode; 
 
            //
            // Can I collapse the entire case-expression into a single expression - yes, 
            // if all the then/else clauses are the same expression
            //
            if (ProcessSimplifyCase_Collapse(caseOp, caseOpNode, out newNode))
            { 
                return true;
            } 
 
            //
            // Can I remove any unnecessary when-then pairs ? 
            //
            if (ProcessSimplifyCase_EliminateWhenClauses(context, caseOp, caseOpNode, out newNode))
            {
                return true; 
            }
 
            // Nothing else I can think of 
            return false;
        } 

        /// 
        /// Try and collapse the case expression into a single expression.
        /// If every single then/else expression in the CaseOp is equivalent, then we can 
        /// simply replace the CaseOp with the first then/expression. Specifically,
        /// case when w1 then t1 when w2 then t2 ... when wn then tn else e end 
        ///   => t1 
        ///  if t1 is equivalent to t2 is equivalent to ... to e
        ///  
        /// the current caseOp
        /// current subtree
        /// new subtree
        /// true, if we performed a transformation 
        private static bool ProcessSimplifyCase_Collapse(CaseOp caseOp, Node caseOpNode, out Node newNode)
        { 
            newNode = caseOpNode; 
            Node firstThenNode = caseOpNode.Child1;
            Node elseNode = caseOpNode.Children[caseOpNode.Children.Count - 1]; 
            if (!firstThenNode.IsEquivalent(elseNode))
            {
                return false;
            } 
            for (int i = 3; i < caseOpNode.Children.Count - 1; i += 2)
            { 
                if (!caseOpNode.Children[i].IsEquivalent(firstThenNode)) 
                {
                    return false; 
                }
            }

            // All nodes are equivalent - simply return the first then node 
            newNode = firstThenNode;
            return true; 
        } 

        ///  
        /// Try and remove spurious branches from the case expression.
        /// If any of the WHEN clauses is the 'FALSE' expression, simply remove that
        /// branch (when-then pair) from the case expression.
        /// If any of the WHEN clauses is the 'TRUE' expression, then all branches to the 
        /// right of it are irrelevant - eliminate them. Eliminate this branch as well,
        /// and make the THEN expression of this branch the ELSE expression for the entire 
        /// Case expression. If the WHEN expression represents the first branch, then 
        /// replace the entire case expression by the corresponding THEN expression
        ///  
        /// rule processing context
        /// current caseOp
        /// Current subtree
        /// the new subtree 
        /// true, if there was a transformation
        private static bool ProcessSimplifyCase_EliminateWhenClauses(RuleProcessingContext context, CaseOp caseOp, Node caseOpNode, out Node newNode) 
        { 
            List newNodeArgs = null;
            newNode = caseOpNode; 

            for (int i = 0; i < caseOpNode.Children.Count; )
            {
                // Special handling for the else clause 
                if (i == caseOpNode.Children.Count - 1)
                { 
                    // If the else clause is a SoftCast then we do not attempt to simplify 
                    // the case operation, since this may change the result type.
                    // This really belongs in more general SoftCastOp logic in the CTreeGenerator 
                    // that converts SoftCasts that could affect the result type of the query into
                    // a real cast or a trivial case statement, to preserve the result type.
                    // This is tracked by SQL PT Work Item #300003327.
                    if (OpType.SoftCast == caseOpNode.Children[i].Op.OpType) 
                    {
                        return false; 
                    } 

                    if (newNodeArgs != null) 
                    {
                        newNodeArgs.Add(caseOpNode.Children[i]);
                    }
                    break; 
                }
 
                // If the current then clause is a SoftCast then we do not attempt to simplify 
                // the case operation, since this may change the result type.
                // Again, this really belongs in the CTreeGenerator as per SQL PT Work Item #300003327. 
                if (OpType.SoftCast == caseOpNode.Children[i + 1].Op.OpType)
                {
                    return false;
                } 

                // Check to see if the when clause is a ConstantPredicate 
                if (caseOpNode.Children[i].Op.OpType != OpType.ConstantPredicate) 
                {
                    if (newNodeArgs != null) 
                    {
                        newNodeArgs.Add(caseOpNode.Children[i]);
                        newNodeArgs.Add(caseOpNode.Children[i + 1]);
                    } 
                    i += 2;
                    continue; 
                } 

                // Found a when-clause which is a constant predicate 
                ConstantPredicateOp constPred = (ConstantPredicateOp)caseOpNode.Children[i].Op;
                // Create the newArgs list, if we haven't done so already
                if (newNodeArgs == null)
                { 
                    newNodeArgs = new List();
                    for (int j = 0; j < i; j++) 
                    { 
                        newNodeArgs.Add(caseOpNode.Children[j]);
                    } 
                }

                // If the when-clause is the "true" predicate, then we simply ignore all
                // the succeeding arguments. We make the "then" clause of this when-clause 
                // as the "else-clause" of the resulting caseOp
                if (constPred.IsTrue) 
                { 
                    newNodeArgs.Add(caseOpNode.Children[i + 1]);
                    break; 
                }
                else
                {
                    // Otherwise, we simply skip the when-then pair 
                    PlanCompiler.Assert(constPred.IsFalse, "constant predicate must be either true or false");
                    i += 2; 
                    continue; 
                }
            } 

            // Did we see any changes? Simply return
            if (newNodeArgs == null)
            { 
                return false;
            } 
 
            // Otherwise, we did do some processing
            PlanCompiler.Assert(newNodeArgs.Count > 0, "new args list must not be empty"); 
            // Is there only one expression in the args list - simply return that expression
            if (newNodeArgs.Count == 1)
            {
                newNode = newNodeArgs[0]; 
            }
            else 
            { 
                newNode = context.Command.CreateNode(caseOp, newNodeArgs);
            } 

            return true;
        }
 
        /// 
        /// If the else clause of the CaseOp is another CaseOp, when two can be collapsed into one. 
        /// In particular, 
        ///
        /// CASE 
        ///     WHEN W1 THEN T1
        ///     WHEN W2 THEN T2 ...
        ///     ELSE (CASE
        ///             WHEN WN1 THEN TN1, � 
        ///             ELSE E)
        /// 
        /// Is transformed into 
        ///
        /// CASE 
        ///     WHEN W1 THEN T1
        ///     WHEN W2 THEN T2 ...
        ///     WHEN WN1  THEN TN1 ...
        ///     ELSE E 
        /// 
        /// the current caseOp 
        /// current subtree 
        /// new subtree
        /// true, if we performed a transformation 
        static bool ProcessFlattenCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
        {
            newNode = caseOpNode;
            Node elseChild = caseOpNode.Children[caseOpNode.Children.Count - 1]; 
            if (elseChild.Op.OpType != OpType.Case)
            { 
                return false; 
            }
 
            //
            // Flatten the case statements.
            // The else child is removed from the outer CaseOp op
            // and the else child's children are reparented to the outer CaseOp 
            // Node info recomputation does not need to happen, the outer CaseOp
            // node still has the same descendants. 
            // 
            caseOpNode.Children.RemoveAt(caseOpNode.Children.Count - 1);
            caseOpNode.Children.AddRange(elseChild.Children); 

            return true;
        }
 
        #endregion
 
        #region EqualsOverConstant Rules 
        internal static readonly PatternMatchRule Rule_EqualsOverConstant =
            new PatternMatchRule(new Node(ComparisonOp.PatternEq, 
                                          new Node(InternalConstantOp.Pattern),
                                          new Node(InternalConstantOp.Pattern)),
                                 ProcessComparisonsOverConstant);
        ///  
        /// Convert an Equals(X, Y) to a "true" predicate if X=Y, or a "false" predicate if X!=Y
        /// Convert a NotEquals(X,Y) in the reverse fashion 
        ///  
        /// Rule processing context
        /// current node 
        /// possibly modified subtree
        /// true, if transformation was successful
        static bool ProcessComparisonsOverConstant(RuleProcessingContext context, Node node, out Node newNode)
        { 
            newNode = node;
            PlanCompiler.Assert(node.Op.OpType == OpType.EQ || node.Op.OpType == OpType.NE, "unexpected comparison op type?"); 
 
            bool? comparisonStatus = node.Child0.Op.IsEquivalent(node.Child1.Op);
            // Don't mess with nulls or with non-internal constants 
            if (comparisonStatus == null)
            {
                return false;
            } 
            bool result = (node.Op.OpType == OpType.EQ) ? (bool)comparisonStatus : !((bool)comparisonStatus);
            ConstantPredicateOp newOp = context.Command.CreateConstantPredicateOp(result); 
            newNode = context.Command.CreateNode(newOp); 
            return true;
        } 
        #endregion

        #region LikeOp Rules
        private static bool? MatchesPattern(string str, string pattern) 
        {
            // What we're trying to see is if the pattern is something that ends with a '%' 
            // And if the "str" is something that matches everything before that 

            // Make sure that the terminal character of the pattern is a '%' character. Also 
            // ensure that this character does not occur anywhere else. And finally, ensure
            // that the pattern is atmost one character longer than the string itself
            int wildCardIndex = pattern.IndexOf('%');
            if ((wildCardIndex == -1) || 
                (wildCardIndex != pattern.Length - 1) ||
                (pattern.Length > str.Length + 1)) 
            { 
                return null;
            } 

            bool match = true;

            int i = 0; 
            for (i = 0; i < str.Length && i < pattern.Length - 1; i++)
            { 
                if (pattern[i] != str[i]) 
                {
                    match = false; 
                    break;
                }
            }
 
            return match;
        } 
 
        internal static readonly PatternMatchRule Rule_LikeOverConstants =
            new PatternMatchRule(new Node(LikeOp.Pattern, 
                                          new Node(InternalConstantOp.Pattern),
                                          new Node(InternalConstantOp.Pattern),
                                          new Node(NullOp.Pattern)),
                                 ProcessLikeOverConstant); 
        static bool ProcessLikeOverConstant(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n; 
            InternalConstantOp patternOp = (InternalConstantOp)n.Child1.Op;
            InternalConstantOp strOp = (InternalConstantOp)n.Child0.Op; 

            string str = (string)strOp.Value;
            string pattern = (string)patternOp.Value;
 
            bool? match = MatchesPattern((string)strOp.Value, (string)patternOp.Value);
            if (match == null) 
            { 
                return false;
            } 

            ConstantPredicateOp constOp = context.Command.CreateConstantPredicateOp((bool)match);
            newNode = context.Command.CreateNode(constOp);
            return true; 
        }
 
        #endregion 

        #region LogicalOp (and,or,not) Rules 
        internal static readonly PatternMatchRule Rule_AndOverConstantPred1 =
            new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
                                          new Node(LeafOp.Pattern),
                                          new Node(ConstantPredicateOp.Pattern)), 
                                 ProcessAndOverConstantPredicate1);
        internal static readonly PatternMatchRule Rule_AndOverConstantPred2 = 
            new PatternMatchRule(new Node(ConditionalOp.PatternAnd, 
                                          new Node(ConstantPredicateOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessAndOverConstantPredicate2);
        internal static readonly PatternMatchRule Rule_OrOverConstantPred1 =
            new PatternMatchRule(new Node(ConditionalOp.PatternOr,
                                          new Node(LeafOp.Pattern), 
                                          new Node(ConstantPredicateOp.Pattern)),
                                 ProcessOrOverConstantPredicate1); 
        internal static readonly PatternMatchRule Rule_OrOverConstantPred2 = 
            new PatternMatchRule(new Node(ConditionalOp.PatternOr,
                                          new Node(ConstantPredicateOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessOrOverConstantPredicate2);
        internal static readonly PatternMatchRule Rule_NotOverConstantPred =
            new PatternMatchRule(new Node(ConditionalOp.PatternNot, 
                                          new Node(ConstantPredicateOp.Pattern)),
                                 ProcessNotOverConstantPredicate); 
        ///  
        /// Transform
        ///   AND(x, true) => x; 
        ///   AND(true, x) => x
        ///   AND(x, false) => false
        ///   AND(false, x) => false
        /// 
        /// 
        /// Rule Processing context 
        /// Current LogOp (And, Or, Not) node 
        /// constant predicate node
        /// The other child of the LogOp (possibly null) 
        /// new subtree
        /// transformation status
        static bool ProcessLogOpOverConstant(RuleProcessingContext context, Node node,
            Node constantPredicateNode, Node otherNode, 
            out Node newNode)
        { 
            PlanCompiler.Assert(constantPredicateNode != null, "null constantPredicateOp?"); 
            ConstantPredicateOp pred = (ConstantPredicateOp)constantPredicateNode.Op;
 
            switch (node.Op.OpType)
            {
                case OpType.And:
                    newNode = pred.IsTrue ? otherNode : constantPredicateNode; 
                    break;
                case OpType.Or: 
                    newNode = pred.IsTrue ? constantPredicateNode : otherNode; 
                    break;
                case OpType.Not: 
                    PlanCompiler.Assert(otherNode == null, "Not Op with more than 1 child. Gasp!");
                    newNode = context.Command.CreateNode(context.Command.CreateConstantPredicateOp(!pred.Value));
                    break;
                default: 
                    PlanCompiler.Assert(false, "Unexpected OpType - " + node.Op.OpType);
                    newNode = null; 
                    break; 
            }
            return true; 
        }

        static bool ProcessAndOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
        { 
            return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
        } 
        static bool ProcessAndOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode) 
        {
            return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode); 
        }
        static bool ProcessOrOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
        {
            return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode); 
        }
        static bool ProcessOrOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode) 
        { 
            return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
        } 
        static bool ProcessNotOverConstantPredicate(RuleProcessingContext context, Node node, out Node newNode)
        {
            return ProcessLogOpOverConstant(context, node, node.Child0, null, out newNode);
        } 
        #endregion
 
        #region IsNull Rules 
        internal static readonly PatternMatchRule Rule_IsNullOverConstant =
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull, 
                                          new Node(InternalConstantOp.Pattern)),
                                 ProcessIsNullOverConstant);
        internal static readonly PatternMatchRule Rule_IsNullOverNullSentinel =
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull, 
                                          new Node(NullSentinelOp.Pattern)),
                                 ProcessIsNullOverConstant); 
        ///  
        /// Convert a
        ///    IsNull(constant) 
        /// to just the
        ///    False predicate
        /// 
        ///  
        /// 
        /// new subtree 
        ///  
        static bool ProcessIsNullOverConstant(RuleProcessingContext context, Node isNullNode, out Node newNode)
        { 
            newNode = context.Command.CreateNode(context.Command.CreateFalseOp());
            return true;
        }
 
        internal static readonly PatternMatchRule Rule_IsNullOverNull =
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull, 
                                          new Node(NullOp.Pattern)), 
                         ProcessIsNullOverNull);
        ///  
        /// Convert an IsNull(null) to just the 'true' predicate
        /// 
        /// 
        ///  
        /// new subtree
        ///  
        static bool ProcessIsNullOverNull(RuleProcessingContext context, Node isNullNode, out Node newNode) 
        {
            newNode = context.Command.CreateNode(context.Command.CreateTrueOp()); 
            return true;
        }
        #endregion
 
        #region CastOp(NullOp) Rule
        internal static readonly PatternMatchRule Rule_NullCast = new PatternMatchRule( 
                                                            new Node(CastOp.Pattern, 
                                                                    new Node(NullOp.Pattern)),
                                                            ProcessNullCast); 

        /// 
        /// eliminates nested null casts into a single cast of the outermost cast type.
        /// basically the transformation applied is: cast(null[x] as T) => null[t] 
        /// 
        ///  
        ///  
        /// modified subtree
        ///  
        static bool ProcessNullCast(RuleProcessingContext context, Node castNullOp, out Node newNode)
        {
            newNode = context.Command.CreateNode(context.Command.CreateNullOp(castNullOp.Op.Type));
            return true; 
        }
        #endregion 
 
        #region IsNull over VarRef
        internal static readonly PatternMatchRule Rule_IsNullOverVarRef = 
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
                                          new Node(VarRefOp.Pattern)),
                                 ProcessIsNullOverVarRef);
        ///  
        /// Convert a
        ///    IsNull(VarRef(v)) 
        /// to just the 
        ///    False predicate
        /// 
        /// if v is guaranteed to be non nullable.
        /// 
        /// 
        ///  
        /// new subtree
        ///  
        static bool ProcessIsNullOverVarRef(RuleProcessingContext context, Node isNullNode, out Node newNode) 
        {
            Command command = context.Command; 
            TransformationRulesContext trc = (TransformationRulesContext)context;

            Var v = ((VarRefOp)isNullNode.Child0.Op).Var;
 
            if (trc.IsNonNullable(v))
            { 
 
                newNode = command.CreateNode(context.Command.CreateFalseOp());
                return true; 
            }
            else
            {
                newNode = isNullNode; 
                return false;
            } 
        } 
        #endregion
 
        #region All ScalarOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
            Rule_SimplifyCase,
            Rule_FlattenCase, 
            Rule_LikeOverConstants,
            Rule_EqualsOverConstant, 
            Rule_AndOverConstantPred1, 
            Rule_AndOverConstantPred2,
            Rule_OrOverConstantPred1, 
            Rule_OrOverConstantPred2,
            Rule_NotOverConstantPred,
            Rule_IsNullOverConstant,
            Rule_IsNullOverNullSentinel, 
            Rule_IsNullOverNull,
            Rule_NullCast, 
            Rule_IsNullOverVarRef, 
        };
        #endregion 
    }
    #endregion

    #region Filter Rules 
    /// 
    /// Transformation rules for FilterOps 
    ///  
    internal static class FilterOpRules
    { 
        #region Helpers
        /// 
        /// Split up a predicate into 2 parts - the pushdown and the non-pushdown predicate.
        /// 
        /// If the filter node has no external references *and* the "columns" parameter is null,
        /// then the entire predicate can be pushed down 
        /// 
        /// We then compute the set of valid column references - if the "columns" parameter
        /// is non-null, this set is used. Otherwise, we get the definitions of the 
        /// input relop node of the filterOp, and use that.
        ///
        /// We use this list of valid column references to identify which parts of the filter
        /// predicate can be pushed down - only those parts of the predicate that do not 
        /// reference anything beyond these columns are considered for pushdown. The rest are
        /// stuffed into the nonPushdownPredicate output parameter 
        /// 
        /// 
        /// Command object 
        /// the FilterOp subtree
        /// (Optional) List of columns to consider for "pushdown"
        /// (output) Part of the predicate that cannot be pushed down
        /// part of the predicate that can be pushed down 
        private static Node GetPushdownPredicate(Command command, Node filterNode, VarVec columns, out Node nonPushdownPredicateNode)
        { 
            Node pushdownPredicateNode = filterNode.Child1; 
            nonPushdownPredicateNode = null;
            ExtendedNodeInfo filterNodeInfo = command.GetExtendedNodeInfo(filterNode); 
            if (columns == null && filterNodeInfo.ExternalReferences.IsEmpty)
            {
                return pushdownPredicateNode;
            } 

            if (columns == null) 
            { 
                ExtendedNodeInfo inputNodeInfo = command.GetExtendedNodeInfo(filterNode.Child0);
                columns = inputNodeInfo.Definitions; 
            }

            Predicate predicate = new Predicate(command, pushdownPredicateNode);
            Predicate nonPushdownPredicate; 
            predicate = predicate.GetSingleTablePredicates(columns, out nonPushdownPredicate);
            pushdownPredicateNode = predicate.BuildAndTree(); 
            nonPushdownPredicateNode = nonPushdownPredicate.BuildAndTree(); 
            return pushdownPredicateNode;
        } 

        #endregion

        #region FilterOverFilter 
        internal static readonly PatternMatchRule Rule_FilterOverFilter =
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                          new Node(FilterOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessFilterOverFilter);
        /// 
        /// Convert Filter(Filter(X, p1), p2) => Filter(X, (p1 and p2)) 
        /// 
        /// rule processing context 
        /// FilterOp node 
        /// modified subtree
        /// transformed subtree 
        static bool ProcessFilterOverFilter(RuleProcessingContext context, Node filterNode, out Node newNode)
        {
            Node newAndNode = context.Command.CreateNode(
                context.Command.CreateConditionalOp(OpType.And), 
                filterNode.Child0.Child1, filterNode.Child1);
 
            newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), filterNode.Child0.Child0, newAndNode); 
            return true;
        } 
        #endregion

        #region FilterOverProject
        internal static readonly PatternMatchRule Rule_FilterOverProject = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessFilterOverProject);
        /// 
        /// Convert Filter(Project(X, ...), p) => Project(Filter(X, p'), ...)
        ///  
        /// Rule processing context
        /// FilterOp subtree 
        /// modified subtree 
        /// transformed subtree
        static bool ProcessFilterOverProject(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode;
            Node predicateNode = filterNode.Child1;
 
            //
            // If the filter is a constant predicate, then don't push the filter below the 
            // project 
            //
            if (predicateNode.Op.OpType == OpType.ConstantPredicate) 
            {
                // There's a different rule to process this case. Simply return
                return false;
            } 

            TransformationRulesContext trc = (TransformationRulesContext)context; 
            // 
            // check to see that this is a simple predicate
            // 
            Dictionary varRefMap = new Dictionary();
            if (!trc.IsScalarOpTree(predicateNode, varRefMap))
            {
                return false; 
            }
            // 
            // check to see if all expressions in the project can be inlined 
            //
            Node projectNode = filterNode.Child0; 
            Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
            if (varMap == null)
            {
                return false; 
            }
 
            // 
            // Try to remap the predicate in terms of the definitions of the Vars
            // 
            Node remappedPredicateNode = trc.ReMap(predicateNode, varMap);

            //
            // Now push the filter below the project 
            //
            Node newFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), projectNode.Child0, remappedPredicateNode); 
            Node newProjectNode = trc.Command.CreateNode(projectNode.Op, newFilterNode, projectNode.Child1); 

            newNode = newProjectNode; 
            return true;
        }
        #endregion
 
        #region FilterOverSetOp
        internal static readonly PatternMatchRule Rule_FilterOverUnionAll = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                          new Node(UnionAllOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)),
                                 ProcessFilterOverSetOp);
        internal static readonly PatternMatchRule Rule_FilterOverIntersect = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                          new Node(IntersectOp.Pattern, 
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessFilterOverSetOp);
        internal static readonly PatternMatchRule Rule_FilterOverExcept =
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                          new Node(ExceptOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessFilterOverSetOp);
        ///  
        /// Transform Filter(UnionAll(X1, X2), p) => UnionAll(Filter(X1, p1), Filter(X, p2))
        ///           Filter(Intersect(X1, X2), p) => Intersect(Filter(X1, p1), Filter(X2, p2))
        ///           Filter(Except(X1, X2), p) => Except(Filter(X1, p1), X2)
        /// where p1 and p2 are the "mapped" versions of the predicate "p" for each branch 
        /// 
        /// Rule processing context 
        /// FilterOp subtree 
        /// modified subtree
        /// true, if successful transformation 
        static bool ProcessFilterOverSetOp(RuleProcessingContext context, Node filterNode, out Node newNode)
        {
            newNode = filterNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 

            // 
            // Identify parts of the filter predicate that can be pushed down, and parts that 
            // cannot be. If nothing can be pushed down, then return
            // 
            Node nonPushdownPredicate;
            Node pushdownPredicate = GetPushdownPredicate(trc.Command, filterNode, null, out nonPushdownPredicate);
            if (pushdownPredicate == null)
            { 
                return false;
            } 
            // Handle only simple predicates 
            if (!trc.IsScalarOpTree(pushdownPredicate))
            { 
                return false;
            }

            // 
            // Now push the predicate (the part that can be pushed down) into each of the
            // branches (as appropriate) 
            // 
            Node setOpNode = filterNode.Child0;
            SetOp setOp = (SetOp)setOpNode.Op; 
            List newSetOpChildren = new List();
            int branchId = 0;
            foreach (VarMap varMap in setOp.VarMap)
            { 
                // For exceptOp, the filter should only be pushed below the zeroth child
                if (setOp.OpType == OpType.Except && branchId == 1) 
                { 
                    newSetOpChildren.Add(setOpNode.Child1);
                    break; 
                }

                Dictionary remapMap = new Dictionary();
                foreach (KeyValuePair kv in varMap) 
                {
                    Node varRefNode = trc.Command.CreateNode(trc.Command.CreateVarRefOp(kv.Value)); 
                    remapMap.Add(kv.Key, varRefNode); 
                }
 
                //
                // Now fix up the predicate.
                // Make a copy of the predicate first - except if we're dealing with the last
                // branch, in which case, we can simply reuse the predicate 
                //
                Node predicateNode = pushdownPredicate; 
                if (branchId == 0 && filterNode.Op.OpType != OpType.Except) 
                {
                    predicateNode = trc.Copy(predicateNode); 
                }
                Node newPredicateNode = trc.ReMap(predicateNode, remapMap);
                trc.Command.RecomputeNodeInfo(newPredicateNode);
 
                // create a new filter node below the setOp child
                Node newFilterNode = trc.Command.CreateNode( 
                    trc.Command.CreateFilterOp(), 
                    setOpNode.Children[branchId],
                    newPredicateNode); 
                newSetOpChildren.Add(newFilterNode);

                branchId++;
            } 
            Node newSetOpNode = trc.Command.CreateNode(setOpNode.Op, newSetOpChildren);
 
            // 
            // We've now pushed down the relevant parts of the filter below the SetOps
            // We may still however some predicates left over - create a new filter node 
            // to account for that
            //
            if (nonPushdownPredicate != null)
            { 
                newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newSetOpNode, nonPushdownPredicate);
            } 
            else 
            {
                newNode = newSetOpNode; 
            }
            return true;
        }
        #endregion 

        #region FilterOverDistinct 
        internal static readonly PatternMatchRule Rule_FilterOverDistinct = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(DistinctOp.Pattern, 
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverDistinct);
        ///  
        /// Transforms Filter(Distinct(x), p) => Filter(Distinct(Filter(X, p1), p2)
        ///    where p2 is the part of the filter that can be pushed down, while p1 represents 
        ///    any external references 
        /// 
        /// Rule processing context 
        /// FilterOp subtree
        /// modified subtree
        /// Transformation status
        static bool ProcessFilterOverDistinct(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode; 
            // 
            // Split up the filter predicate into two parts - the part that can be pushed down
            // and the part that can't. If there is no part that can be pushed down, simply return 
            //
            Node nonPushdownPredicate;
            Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, null, out nonPushdownPredicate);
            if (pushdownPredicate == null) 
            {
                return false; 
            } 

            // 
            // Create a new filter node below the current distinct node for the predicate
            // that can be pushed down - create a new distinct node as well
            //
            Node distinctNode = filterNode.Child0; 
            Node pushdownFilterNode = context.Command.CreateNode(context.Command.CreateFilterOp(), distinctNode.Child0, pushdownPredicate);
            Node newDistinctNode = context.Command.CreateNode(distinctNode.Op, pushdownFilterNode); 
 
            //
            // If we have a predicate part that cannot be pushed down, build up a new 
            // filter node above the new Distinct op that we just created
            //
            if (nonPushdownPredicate != null)
            { 
                newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), newDistinctNode, nonPushdownPredicate);
            } 
            else 
            {
                newNode = newDistinctNode; 
            }
            return true;
        }
        #endregion 

        #region FilterOverGroupBy 
        internal static readonly PatternMatchRule Rule_FilterOverGroupBy = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(GroupByOp.Pattern, 
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)), 
                         ProcessFilterOverGroupBy);
        ///  
        /// Transforms Filter(GroupBy(X, k1.., a1...), p) => 
        ///            Filter(GroupBy(Filter(X, p1'), k1..., a1...), p2)
        ///   p1 and p2 represent the parts of p that can and cannot be pushed down 
        ///    respectively - specifically, p1 must only reference the key columns from
        ///    the GroupByOp.
        ///   "p1'" is the mapped version of "p1",
        ///  
        /// Rule processing context
        /// Current FilterOp subtree 
        /// modified subtree 
        /// Transformation status
        static bool ProcessFilterOverGroupBy(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode;
            Node groupByNode = filterNode.Child0;
            GroupByOp groupByOp = (GroupByOp)groupByNode.Op; 
            TransformationRulesContext trc = (TransformationRulesContext)context;
 
            // Check to see that we have a simple predicate 
            Dictionary varRefMap = new Dictionary();
            if (!trc.IsScalarOpTree(filterNode.Child1, varRefMap)) 
            {
                return false;
            }
 
            //
            // Split up the predicate into two parts - the part that can be pushed down below 
            // the groupByOp (specifically, the part that only refers to keys of the groupByOp), 
            // and the part that cannot be pushed below
            // If nothing can be pushed below, quit now 
            //
            Node nonPushdownPredicate;
            Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, groupByOp.Keys, out nonPushdownPredicate);
            if (pushdownPredicate == null) 
            {
                return false; 
            } 

            // 
            // We need to push the filter down; but we need to remap the predicate, so
            // that any references to variables defined locally by the groupBy are fixed up
            // Make sure that the predicate is not too complex to remap
            // 
            Dictionary varMap = trc.GetVarMap(groupByNode.Child1, varRefMap);
            if (varMap == null) 
            { 
                return false; // complex expressions
            } 
            Node remappedPushdownPredicate = trc.ReMap(pushdownPredicate, varMap);

            //
            // Push the filter below the groupBy now 
            //
            Node subFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), groupByNode.Child0, remappedPushdownPredicate); 
            Node newGroupByNode = trc.Command.CreateNode(groupByNode.Op, subFilterNode, groupByNode.Child1, groupByNode.Child2); 

            // 
            // If there was any part of the original predicate that could not be pushed down,
            // create a new filterOp node above the new groupBy node to represent that
            // predicate
            // 
            if (nonPushdownPredicate == null)
            { 
                newNode = newGroupByNode; 
            }
            else 
            {
                newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newGroupByNode, nonPushdownPredicate);
            }
            return true; 
        }
        #endregion 
 
        #region FilterOverJoin
        internal static readonly PatternMatchRule Rule_FilterOverCrossJoin = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(CrossJoinOp.Pattern,
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)), 
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverJoin); 
        internal static readonly PatternMatchRule Rule_FilterOverInnerJoin = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(InnerJoinOp.Pattern, 
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)), 
                         ProcessFilterOverJoin);
        internal static readonly PatternMatchRule Rule_FilterOverLeftOuterJoin = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                  new Node(LeftOuterJoinOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverJoin); 
        /// 
        /// Transform Filter() 
        ///  
        /// Rule Processing context
        /// Current FilterOp subtree 
        /// Modified subtree
        /// Transformation status
        static bool ProcessFilterOverJoin(RuleProcessingContext context, Node filterNode, out Node newNode)
        { 
            newNode = filterNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 
 
            //
            // Have we shut off filter pushdown for this node? Return 
            //
            if (trc.IsFilterPushdownSuppressed(filterNode))
            {
                return false; 
            }
 
            Node joinNode = filterNode.Child0; 
            Op joinOp = joinNode.Op;
            Node leftInputNode = joinNode.Child0; 
            Node rightInputNode = joinNode.Child1;
            Command command = trc.Command;
            bool needsTransformation = false;
 
            //
            // If we're dealing with an outer-join, first check to see if the current 
            // predicate preserves nulls for the right table. 
            // If it doesn't then we can convert the outer join into an inner join,
            // and then continue with the rest of our processing here 
            //
            ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(rightInputNode);
            Predicate predicate = new Predicate(command, filterNode.Child1);
            if (joinOp.OpType == OpType.LeftOuterJoin) 
            {
                if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true)) 
                { 
                    joinOp = command.CreateInnerJoinOp();
                    needsTransformation = true; 
                }
            }
            ExtendedNodeInfo leftTableInfo = command.GetExtendedNodeInfo(leftInputNode);
 
            //
            // Check to see if the predicate contains any "single-table-filters". In those 
            // cases, we could simply push that filter down to the child. 
            // We can do this for inner joins and cross joins - for both inputs.
            // For left-outer joins, however, we can only do this for the left-side input 
            // Further note that we only want to do the pushdown if it will help us - if
            // the join input is a ScanTable (or some other cases), then it doesn't help us.
            //
            Node leftSingleTablePredicateNode = null; 
            if (leftInputNode.Op.OpType != OpType.ScanTable)
            { 
                Predicate leftSingleTablePredicates = predicate.GetSingleTablePredicates(leftTableInfo.Definitions, out predicate); 
                leftSingleTablePredicateNode = leftSingleTablePredicates.BuildAndTree();
            } 

            Node rightSingleTablePredicateNode = null;
            if ((rightInputNode.Op.OpType != OpType.ScanTable) &&
                (joinOp.OpType != OpType.LeftOuterJoin)) 
            {
                Predicate rightSingleTablePredicates = predicate.GetSingleTablePredicates(rightTableNodeInfo.Definitions, out predicate); 
                rightSingleTablePredicateNode = rightSingleTablePredicates.BuildAndTree(); 
            }
 
            //
            // Now check to see if the predicate contains some "join predicates". We can
            // add these to the existing join predicate (if any).
            // We can only do this for inner joins and cross joins - not for LOJs 
            //
            Node newJoinPredicateNode = null; 
            if (joinOp.OpType == OpType.CrossJoin || joinOp.OpType == OpType.InnerJoin) 
            {
                Predicate joinPredicate = predicate.GetJoinPredicates(leftTableInfo.Definitions, rightTableNodeInfo.Definitions, out predicate); 
                newJoinPredicateNode = joinPredicate.BuildAndTree();
            }

            // 
            // Now for the dirty work. We've identified some predicates that could be pushed
            // into the left table, some predicates that could be pushed into the right table 
            // and some that could become join predicates. 
            //
            if (leftSingleTablePredicateNode != null) 
            {
                leftInputNode = command.CreateNode(command.CreateFilterOp(), leftInputNode, leftSingleTablePredicateNode);
                needsTransformation = true;
            } 
            if (rightSingleTablePredicateNode != null)
            { 
                rightInputNode = command.CreateNode(command.CreateFilterOp(), rightInputNode, rightSingleTablePredicateNode); 
                needsTransformation = true;
            } 

            // Identify the new join predicate
            if (newJoinPredicateNode != null)
            { 
                needsTransformation = true;
                if (joinOp.OpType == OpType.CrossJoin) 
                { 
                    joinOp = command.CreateInnerJoinOp();
                } 
                else
                {
                    PlanCompiler.Assert(joinOp.OpType == OpType.InnerJoin, "unexpected non-InnerJoin?");
                    newJoinPredicateNode = PlanCompilerUtil.CombinePredicates(joinNode.Child2, newJoinPredicateNode, command); 
                }
            } 
            else 
            {
                newJoinPredicateNode = (joinOp.OpType == OpType.CrossJoin) ? null : joinNode.Child2; 
            }

            //
            // If nothing has changed, then just return the current node. Otherwise, 
            // we will loop forever
            // 
            if (!needsTransformation) 
            {
                return false; 
            }

            Node newJoinNode;
            // 
            // Finally build up a new join node
            // 
            if (joinOp.OpType == OpType.CrossJoin) 
            {
                newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode); 
            }
            else
            {
                newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode, newJoinPredicateNode); 
            }
 
            // 
            // Build up a new filterNode above this join node. But only if we have a filter left
            // 
            Node newFilterPredicateNode = predicate.BuildAndTree();
            if (newFilterPredicateNode == null)
            {
                newNode = newJoinNode; 
            }
            else 
            { 
                newNode = command.CreateNode(command.CreateFilterOp(), newJoinNode, newFilterPredicateNode);
            } 
            return true;
        }
        #endregion
 
        #region Filter over OuterApply
        internal static readonly PatternMatchRule Rule_FilterOverOuterApply = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                  new Node(OuterApplyOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverOuterApply);
        ///  
        /// Convert Filter(OuterApply(X,Y), p) into
        ///    Filter(CrossApply(X,Y), p) 
        /// if "p" is not null-preserving for Y (ie) "p" does not preserve null values from Y 
        /// 
        /// Rule processing context 
        /// Filter node
        /// modified subtree
        /// transformation status
        static bool ProcessFilterOverOuterApply(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode; 
            Node applyNode = filterNode.Child0; 
            Op applyOp = applyNode.Op;
            Node applyRightInputNode = applyNode.Child1; 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command;

            // 
            // Check to see if the current predicate preserves nulls for the right table.
            // If it doesn't then we can convert the outer apply into a cross-apply, 
            // 
            ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(applyRightInputNode);
            Predicate predicate = new Predicate(command, filterNode.Child1); 
            if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
            {
                Node newApplyNode = command.CreateNode(command.CreateCrossApplyOp(), applyNode.Child0, applyRightInputNode);
                Node newFilterNode = command.CreateNode(command.CreateFilterOp(), newApplyNode, filterNode.Child1); 
                newNode = newFilterNode;
                return true; 
            } 

            return false; 
        }

        #endregion
 
        #region FilterWithConstantPredicate
        internal static readonly PatternMatchRule Rule_FilterWithConstantPredicate = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                          new Node(LeafOp.Pattern),
                          new Node(ConstantPredicateOp.Pattern)), 
                 ProcessFilterWithConstantPredicate);
        /// 
        /// Convert
        ///    Filter(X, true)  => X 
        ///    Filter(X, false) => Project(Filter(SingleRowTableOp, ...), false)
        /// where ... represent variables that are equivalent to the table columns 
        ///  
        /// Rule processing context
        /// Current subtree 
        /// modified subtree
        /// transformation status
        static bool ProcessFilterWithConstantPredicate(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n;
            ConstantPredicateOp predOp = (ConstantPredicateOp)n.Child1.Op; 
 
            // If we're dealing with a "true" predicate, then simply return the RelOp
            // input to the filter 
            if (predOp.IsTrue)
            {
                newNode = n.Child0;
                return true; 
            }
 
            PlanCompiler.Assert(predOp.IsFalse, "unexpected non-false predicate?"); 
            // We're dealing with a "false" predicate, then we can get rid of the
            // input, and replace it with a dummy project 

            //
            // If the input is already a singlerowtableOp, then there's nothing
            // further to do 
            //
            if (n.Child0.Op.OpType == OpType.SingleRowTable || 
                (n.Child0.Op.OpType == OpType.Project && 
                 n.Child0.Child0.Op.OpType == OpType.SingleRowTable))
            { 
                return false;
            }

            TransformationRulesContext trc = (TransformationRulesContext)context; 
            ExtendedNodeInfo childNodeInfo = trc.Command.GetExtendedNodeInfo(n.Child0);
            List varDefNodeList = new List(); 
            VarVec newVars = trc.Command.CreateVarVec(); 
            foreach (Var v in childNodeInfo.Definitions)
            { 
                NullOp nullConst = trc.Command.CreateNullOp(v.Type);
                Node constNode = trc.Command.CreateNode(nullConst);
                Var computedVar;
                Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar); 
                trc.AddVarMapping(v, computedVar);
                newVars.Set(computedVar); 
                varDefNodeList.Add(varDefNode); 
            }
            // If no vars have been selected out, add a dummy var 
            if (newVars.IsEmpty)
            {
                NullOp nullConst = trc.Command.CreateNullOp(trc.Command.BooleanType);
                Node constNode = trc.Command.CreateNode(nullConst); 
                Var computedVar;
                Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar); 
                newVars.Set(computedVar); 
                varDefNodeList.Add(varDefNode);
            } 

            Node singleRowTableNode = trc.Command.CreateNode(trc.Command.CreateSingleRowTableOp());
            n.Child0 = singleRowTableNode;
 
            Node varDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp(), varDefNodeList);
            ProjectOp projectOp = trc.Command.CreateProjectOp(newVars); 
            Node projectNode = trc.Command.CreateNode(projectOp, n, varDefListNode); 

            projectNode.Child0 = n; 
            newNode = projectNode;
            return true;
        }
 
        #endregion
 
        #region All FilterOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
                 FilterOpRules.Rule_FilterWithConstantPredicate, 
                 FilterOpRules.Rule_FilterOverCrossJoin,
                 FilterOpRules.Rule_FilterOverDistinct,
                 FilterOpRules.Rule_FilterOverExcept,
                 FilterOpRules.Rule_FilterOverFilter, 
                 FilterOpRules.Rule_FilterOverGroupBy,
                 FilterOpRules.Rule_FilterOverInnerJoin, 
                 FilterOpRules.Rule_FilterOverIntersect, 
                 FilterOpRules.Rule_FilterOverLeftOuterJoin,
                 FilterOpRules.Rule_FilterOverProject, 
                 FilterOpRules.Rule_FilterOverUnionAll,
                 FilterOpRules.Rule_FilterOverOuterApply,
        };
 
        #endregion
    } 
    #endregion 

    #region Project Rules 
    /// 
    /// Transformation rules for ProjectOp
    /// 
    internal static class ProjectOpRules 
    {
        #region ProjectOverProject 
        internal static readonly PatternMatchRule Rule_ProjectOverProject = 
            new PatternMatchRule(new Node(ProjectOp.Pattern,
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)),
                                 ProcessProjectOverProject); 
        /// 
        /// Converts a Project(Project(X, c1,...), d1,...) => 
        ///            Project(X, d1', d2'...) 
        /// where d1', d2' etc. are the "mapped" versions of d1, d2 etc.
        ///  
        /// Rule processing context
        /// Current ProjectOp node
        /// modified subtree
        /// Transformation status 
        static bool ProcessProjectOverProject(RuleProcessingContext context, Node projectNode, out Node newNode)
        { 
            newNode = projectNode; 
            ProjectOp projectOp = (ProjectOp)projectNode.Op;
            Node varDefListNode = projectNode.Child1; 
            Node subProjectNode = projectNode.Child0;
            ProjectOp subProjectOp = (ProjectOp)subProjectNode.Op;
            TransformationRulesContext trc = (TransformationRulesContext)context;
 
            // If any of the defining expressions is not a scalar op tree, then simply
            // quit 
            Dictionary varRefMap = new Dictionary(); 
            foreach (Node varDefNode in varDefListNode.Children)
            { 
                if (!trc.IsScalarOpTree(varDefNode.Child0, varRefMap))
                {
                    return false;
                } 
            }
 
            Dictionary varMap = trc.GetVarMap(subProjectNode.Child1, varRefMap); 
            if (varMap == null)
            { 
                return false;
            }

            // create a new varDefList node... 
            Node newVarDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp());
 
            // Remap any local definitions, I have 
            foreach (Node varDefNode in varDefListNode.Children)
            { 
                // update the defining expression
                varDefNode.Child0 = trc.ReMap(varDefNode.Child0, varMap);
                trc.Command.RecomputeNodeInfo(varDefNode);
                newVarDefListNode.Children.Add(varDefNode); 
            }
 
            // Now, pull up any definitions of the subProject that I publish myself 
            ExtendedNodeInfo projectNodeInfo = trc.Command.GetExtendedNodeInfo(projectNode);
            foreach (Node chi in subProjectNode.Child1.Children) 
            {
                VarDefOp varDefOp = (VarDefOp)chi.Op;
                if (projectNodeInfo.Definitions.IsSet(varDefOp.Var))
                { 
                    newVarDefListNode.Children.Add(chi);
                } 
            } 

            // 
            // now that we have remapped all our computed vars, simply bypass the subproject
            // node
            //
            projectNode.Child0 = subProjectNode.Child0; 
            projectNode.Child1 = newVarDefListNode;
            return true; 
        } 
        #endregion
 
        #region ProjectWithNoLocalDefinitions
        internal static readonly PatternMatchRule Rule_ProjectWithNoLocalDefs =
            new PatternMatchRule(new Node(ProjectOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(VarDefListOp.Pattern)),
                                 ProcessProjectWithNoLocalDefinitions); 
        ///  
        /// Eliminate a ProjectOp that has no local definitions at all and
        /// no external references, (ie) if Child1 
        /// of the ProjectOp (the VarDefListOp child) has no children, then the ProjectOp
        /// is serving no useful purpose. Get rid of the ProjectOp, and replace it with its
        /// child
        ///  
        /// rule processing context
        /// current subtree 
        /// transformed subtree 
        /// transformation status
        static bool ProcessProjectWithNoLocalDefinitions(RuleProcessingContext context, Node n, out Node newNode) 
        {
            newNode = n;
            NodeInfo nodeInfo = context.Command.GetNodeInfo(n);
 
            // We cannot eliminate this node because it can break other rules,
            // e.g. ProcessApplyOverAnything which relies on existance of external refs to substitute 
            // CrossApply(x, y) => CrossJoin(x, y). See SQLBU #481719. 
            if (!nodeInfo.ExternalReferences.IsEmpty)
            { 
                return false;
            }

            newNode = n.Child0; 
            return true;
        } 
 
        #endregion
 
        #region ProjectOpWithSimpleVarRedefinitions
        internal static readonly SimpleRule Rule_ProjectOpWithSimpleVarRedefinitions = new SimpleRule(OpType.Project, ProcessProjectWithSimpleVarRedefinitions);
        /// 
        /// If the ProjectOp defines some computedVars, but those computedVars are simply 
        /// redefinitions of other Vars, then eliminate the computedVars.
        /// 
        /// Project(X, VarDefList(VarDef(cv1, VarRef(v1)), ...)) 
        ///    can be transformed into
        /// Project(X, VarDefList(...)) 
        /// where cv1 has now been replaced by v1
        /// 
        /// Rule processing context
        /// current subtree 
        /// transformed subtree
        /// transformation status 
        static bool ProcessProjectWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode) 
        {
            newNode = n; 
            ProjectOp projectOp = (ProjectOp)n.Op;

            if (n.Child1.Children.Count == 0)
            { 
                return false;
            } 
 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command; 

            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);

            // 
            // Check to see if any of the computed Vars defined by this ProjectOp
            // are simple redefinitions of other VarRefOps. Consider only those 
            // VarRefOps that are not "external" references 
            bool canEliminateSomeVars = false;
            foreach (Node varDefNode in n.Child1.Children) 
            {
                Node definingExprNode = varDefNode.Child0;
                if (definingExprNode.Op.OpType == OpType.VarRef)
                { 
                    VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
                    if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var)) 
                    { 
                        // this is a Var that we should remove
                        canEliminateSomeVars = true; 
                        break;
                    }
                }
            } 

            // Did we have any redefinitions 
            if (!canEliminateSomeVars) 
            {
                return false; 
            }

            //
            // OK. We've now identified a set of vars that are simple redefinitions. 
            // Try and replace the computed Vars with the Vars that they're redefining
            // 
 
            // Lets now build up a new VarDefListNode
            List newVarDefNodes = new List(); 
            foreach (Node varDefNode in n.Child1.Children)
            {
                VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp; 
                if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
                { 
                    projectOp.Outputs.Clear(varDefOp.Var); 
                    projectOp.Outputs.Set(varRefOp.Var);
                    trc.AddVarMapping(varDefOp.Var, varRefOp.Var); 
                }
                else
                {
                    newVarDefNodes.Add(varDefNode); 
                }
            } 
 
            // Note: Even if we don't have any local var definitions left, we should not remove
            // this project yet because: 
            //  (1) this project node may be prunning out some outputs;
            //  (2) the rule Rule_ProjectWithNoLocalDefs, would do that later anyway.

            // Create a new vardeflist node, and set that as Child1 for the projectOp 
            Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
            n.Child1 = newVarDefListNode; 
            return true; // some part of the subtree was modified 
        }
 

        #endregion

        #region ProjectOpWithNullSentinel 
        internal static readonly SimpleRule Rule_ProjectOpWithNullSentinel = new SimpleRule(OpType.Project, ProcessProjectOpWithNullSentinel);
        ///  
        /// Tries to remove null sentinel definitions by replacing them to vars that are guaranteed 
        /// to be non-nullable and of integer type, or with reference to other constants defined in the
        /// same project. In particular, 
        ///
        ///  - If based on the ancestors, the value of the null sentinel can be changed and the
        /// input of the project has a var that is guaranteed to be non-nullable and
        /// is of integer type, then the definitions of the vars defined as NullSentinels in the ProjectOp 
        /// are replaced with a reference to that var. I.eg:
        /// 
        /// Project(X, VarDefList(VarDef(ns_var, NullSentinel), ...)) 
        ///    can be transformed into
        /// Project(X, VarDefList(VarDef(ns_var, VarRef(v))...)) 
        /// where v is known to be non-nullable
        ///
        /// - Else, if based on the ancestors, the value of the null sentinel can be changed and
        /// the project already has definitions of other int constants, the definitions of the null sentinels 
        /// are removed and the respective vars are remapped to the var representing the constant.
        /// 
        /// - Else, the definitions of the all null sentinels except for one are removed, and the 
        /// the respective vars are remapped to the remaining null sentinel.
        ///  
        /// Rule processing context
        /// current subtree
        /// transformed subtree
        /// transformation status 
        static bool ProcessProjectOpWithNullSentinel(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n; 
            ProjectOp projectOp = (ProjectOp)n.Op;
            Node varDefListNode = n.Child1; 

            if (varDefListNode.Children.Where(c => c.Child0.Op.OpType == OpType.NullSentinel).Count() == 0)
            {
                return false; 
            }
 
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            Command command = trc.Command;
            ExtendedNodeInfo relOpInputNodeInfo = command.GetExtendedNodeInfo(n.Child0); 
            Var inputSentinel;
            bool reusingConstantFromSameProjectAsSentinel = false;

            bool canChangeNullSentinelValue = trc.CanChangeNullSentinelValue; 

            if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(relOpInputNodeInfo.NonNullableDefinitions, out inputSentinel)) 
            { 
                reusingConstantFromSameProjectAsSentinel = true;
                if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.Constant || child.Child0.Op.OpType == OpType.InternalConstant).Select(child => ((VarDefOp)(child.Op)).Var), out inputSentinel)) 
                {
                    inputSentinel = n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.NullSentinel).Select(child => ((VarDefOp)(child.Op)).Var).FirstOrDefault();
                    if (inputSentinel == null)
                    { 
                        return false;
                    } 
                } 
            }
 
            bool modified = false;

            for (int i = n.Child1.Children.Count-1; i >= 0; i--)
            { 
                Node varDefNode = n.Child1.Children[i];
                Node definingExprNode = varDefNode.Child0; 
                if (definingExprNode.Op.OpType == OpType.NullSentinel) 
                {
                    if (!reusingConstantFromSameProjectAsSentinel) 
                    {
                        VarRefOp varRefOp = command.CreateVarRefOp(inputSentinel);
                        varDefNode.Child0 = command.CreateNode(varRefOp);
                        command.RecomputeNodeInfo(varDefNode); 
                        modified = true;
                    } 
                    else if (!inputSentinel.Equals(((VarDefOp)varDefNode.Op).Var)) 
                    {
                        projectOp.Outputs.Clear(((VarDefOp)varDefNode.Op).Var); 
                        n.Child1.Children.RemoveAt(i);
                        trc.AddVarMapping(((VarDefOp)varDefNode.Op).Var, inputSentinel);
                        modified = true;
                    } 
                }
            } 
 
            if (modified)
            { 
                command.RecomputeNodeInfo(n.Child1);
            }
            return modified;
        } 
        #endregion
 
        #region All ProjectOp Rules 
        //The order of the rules is important
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 ProjectOpRules.Rule_ProjectOpWithNullSentinel,
                 ProjectOpRules.Rule_ProjectOpWithSimpleVarRedefinitions,
                 ProjectOpRules.Rule_ProjectOverProject,
                 ProjectOpRules.Rule_ProjectWithNoLocalDefs, 
        };
        #endregion 
    } 
    #endregion
 
    #region Apply Rules
    /// 
    /// Transformation rules for ApplyOps - CrossApply, OuterApply
    ///  
    internal static class ApplyOpRules
    { 
        #region ApplyOverFilter 
        internal static readonly PatternMatchRule Rule_CrossApplyOverFilter =
            new PatternMatchRule(new Node(CrossApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern))), 
                                 ProcessApplyOverFilter);
        internal static readonly PatternMatchRule Rule_OuterApplyOverFilter = 
            new PatternMatchRule(new Node(OuterApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(FilterOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern))),
                                 ProcessApplyOverFilter);
        ///  
        /// Convert CrossApply(X, Filter(Y, p)) => InnerJoin(X, Y, p)
        ///         OuterApply(X, Filter(Y, p)) => LeftOuterJoin(X, Y, p) 
        /// if "Y" has no external references to X 
        /// 
        /// Rule processing context 
        /// Current ApplyOp
        /// transformed subtree
        /// Transformation status
        static bool ProcessApplyOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode) 
        {
            newNode = applyNode; 
            Node filterNode = applyNode.Child1; 
            Command command = context.Command;
 
            NodeInfo filterInputNodeInfo = command.GetNodeInfo(filterNode.Child0);
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);

            // 
            // check to see if the inputNode to the FilterOp has any external references
            // to the left child of the ApplyOp. If it does, we simply return, we 
            // can't do much more here 
            //
            if (filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions)) 
            {
                return false;
            }
 
            //
            // We've now gotten to the stage where the only external references (if any) 
            // are from the filter predicate. 
            // We can now simply convert the apply into an inner/leftouter join with the
            // filter predicate acting as the join condition 
            //
            JoinBaseOp joinOp = null;
            if (applyNode.Op.OpType == OpType.CrossApply)
            { 
                joinOp = command.CreateInnerJoinOp();
            } 
            else 
            {
                joinOp = command.CreateLeftOuterJoinOp(); 
            }

            newNode = command.CreateNode(joinOp, applyNode.Child0, filterNode.Child0, filterNode.Child1);
            return true; 
        }
 
        internal static readonly PatternMatchRule Rule_OuterApplyOverProjectInternalConstantOverFilter = 
             new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(ProjectOp.Pattern,
                                                    new Node(FilterOp.Pattern,
                                                             new Node(LeafOp.Pattern),
                                                             new Node(LeafOp.Pattern)), 
                                                    new Node(VarDefListOp.Pattern,
                                                             new Node(VarDefOp.Pattern, 
                                                                      new Node(InternalConstantOp.Pattern))))), 
                         ProcessOuterApplyOverDummyProjectOverFilter);
 
        internal static readonly PatternMatchRule Rule_OuterApplyOverProjectNullSentinelOverFilter =
           new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                         new Node(LeafOp.Pattern),
                                         new Node(ProjectOp.Pattern, 
                                                  new Node(FilterOp.Pattern,
                                                           new Node(LeafOp.Pattern), 
                                                           new Node(LeafOp.Pattern)), 
                                                  new Node(VarDefListOp.Pattern,
                                                           new Node(VarDefOp.Pattern, 
                                                                    new Node(NullSentinelOp.Pattern))))),
                       ProcessOuterApplyOverDummyProjectOverFilter);

        ///  
        /// Convert OuterApply(X, Project(Filter(Y, p), constant)) =>
        ///     LeftOuterJoin(X, Project(Y, constant), p) 
        /// if "Y" has no external references to X 
        ///
        /// In an ideal world, we would be able to push the Project below the Filter, 
        /// and then have the normal ApplyOverFilter rule handle this - but that causes us
        /// problems because we always try to pull up ProjectOp's as high as possible. Hence,
        /// the special case for this rule
        /// 
        /// 
        /// Rule processing context 
        /// Current ApplyOp 
        /// transformed subtree
        /// Transformation status 
        static bool ProcessOuterApplyOverDummyProjectOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            newNode = applyNode;
            Node projectNode = applyNode.Child1; 
            ProjectOp projectOp = (ProjectOp)projectNode.Op;
            Node filterNode = projectNode.Child0; 
            Node filterInputNode = filterNode.Child0; 
            Command command = context.Command;
 
            ExtendedNodeInfo filterInputNodeInfo = command.GetExtendedNodeInfo(filterInputNode);
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);

            // 
            // Check if the outputs of the ProjectOp or the inputNode to the FilterOp
            // have any external references to the left child of the ApplyOp. 
            // If they do, we simply return, we can't do much more here 
            //
            if (projectOp.Outputs.Overlaps(applyLeftChildNodeInfo.Definitions) || filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions)) 
            {
                return false;
            }
 
            //
            // We've now gotten to the stage where the only external references (if any) 
            // are from the filter predicate. 
            // First, push the Project node down below the filter - but make sure that
            // all the Vars needed by the Filter are projected out 
            //
            bool capWithProject = false;
            Node joinNodeRightInput = null;
 
            //
            // Check to see whether there is a sentinel var available - if there is, then 
            // we can simply move the ProjectOp above the join we're going to construct 
            // and of course, build a NullIf expression for the constant.
            // Otherwise, the ProjectOp will need to be the child of the joinOp that we're 
            // building - and we'll need to make sure that the ProjectOp projects out
            // any vars that are required for the Filter in the first place
            //
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            Var sentinelVar;
            bool sentinelIsInt32; 
 
            if (TransformationRulesContext.TryGetInt32Var(filterInputNodeInfo.NonNullableDefinitions, out sentinelVar))
            { 
                sentinelIsInt32 = true;
            }
            else
            { 
                sentinelVar = filterInputNodeInfo.NonNullableDefinitions.First;
                sentinelIsInt32 = false; 
            } 

            if (sentinelVar != null) 
            {
                capWithProject = true;
                Node varDefNode = projectNode.Child1.Child0;
                if (varDefNode.Child0.Op.OpType == OpType.NullSentinel && sentinelIsInt32 && trc.CanChangeNullSentinelValue) 
                {
                    varDefNode.Child0 = context.Command.CreateNode(context.Command.CreateVarRefOp(sentinelVar)); 
                } 
                else
                { 
                    varDefNode.Child0 = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
                }
                command.RecomputeNodeInfo(varDefNode);
                command.RecomputeNodeInfo(projectNode.Child1); 
                joinNodeRightInput = filterInputNode;
            } 
            else 
            {
                // We need to keep the projectNode - unfortunately 
                joinNodeRightInput = projectNode;
                //
                // Make sure that every Var that is needed for the filter predicate
                // is captured in the projectOp outputs list 
                //
                NodeInfo filterPredicateNodeInfo = command.GetNodeInfo(filterNode.Child1); 
                foreach (Var v in filterPredicateNodeInfo.ExternalReferences) 
                {
                    if (filterInputNodeInfo.Definitions.IsSet(v)) 
                    {
                        projectOp.Outputs.Set(v);
                    }
                } 
                projectNode.Child0 = filterInputNode;
            } 
 
            context.Command.RecomputeNodeInfo(projectNode);
 
            //
            // We can now simply convert the apply into an inner/leftouter join with the
            // filter predicate acting as the join condition
            // 
            Node joinNode = command.CreateNode(command.CreateLeftOuterJoinOp(), applyNode.Child0, joinNodeRightInput, filterNode.Child1);
            if (capWithProject) 
            { 
                ExtendedNodeInfo joinNodeInfo = command.GetExtendedNodeInfo(joinNode);
                projectNode.Child0 = joinNode; 
                projectOp.Outputs.Or(joinNodeInfo.Definitions);
                newNode = projectNode;
            }
            else 
            {
                newNode = joinNode; 
            } 
            return true;
        } 
        #endregion

        #region ApplyOverProject
        internal static readonly PatternMatchRule Rule_CrossApplyOverProject = 
            new PatternMatchRule(new Node(CrossApplyOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern))), 
                                 ProcessCrossApplyOverProject);

        /// 
        /// Converts a CrossApply(X, Project(Y, ...)) => Project(CrossApply(X, Y), ...) 
        /// where the projectVars are simply pulled up
        ///  
        /// RuleProcessing context 
        /// The ApplyOp subtree
        /// transformed subtree 
        /// Transfomation status
        static bool ProcessCrossApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            newNode = applyNode; 
            Node projectNode = applyNode.Child1;
            ProjectOp projectOp = (ProjectOp)projectNode.Op as ProjectOp; 
            Command command = context.Command; 

            // We can simply pull up the project over the apply; provided we make sure 
            // that all the definitions of the apply are represented in the projectOp
            ExtendedNodeInfo applyNodeInfo = command.GetExtendedNodeInfo(applyNode);
            VarVec vec = command.CreateVarVec(projectOp.Outputs);
            vec.Or(applyNodeInfo.Definitions); 
            projectOp.Outputs.InitFrom(vec);
 
            // pull up the project over the apply node 
            applyNode.Child1 = projectNode.Child0;
            context.Command.RecomputeNodeInfo(applyNode); 
            projectNode.Child0 = applyNode;

            newNode = projectNode;
            return true; 
        }
 
        internal static readonly PatternMatchRule Rule_OuterApplyOverProject = 
             new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(ProjectOp.Pattern,
                                                    new Node(LeafOp.Pattern),
                                                    new Node(LeafOp.Pattern))),
                         ProcessOuterApplyOverProject); 
        /// 
        /// Converts a 
        ///     OuterApply(X, Project(Y, ...)) 
        /// =>
        ///     Project(OuterApply(X, Project(Y, ...)), ...) or 
        ///     Project(OuterApply(X, Y), ...)
        ///
        /// The second (simpler) form is used if a "sentinel" var can be located (ie)
        /// some Var of Y that is guaranteed to be non-null. Otherwise, we create a 
        /// dummy ProjectNode as the right child of the Apply - which
        /// simply projects out all the vars of the Y, and adds on a constant (say "1"). This 
        /// constant is now treated as the sentinel var 
        ///
        /// Then the existing ProjectOp is pulled up above the the outer-apply, but all the locally defined 
        /// Vars have their defining expressions now expressed as
        ///     case when sentinelVar is null then null else oldDefiningExpr end
        /// where oldDefiningExpr represents the original defining expression
        /// This allows us to get nulls for the appropriate columns when necessary. 
        ///
        /// Special cases. 
        /// * If the oldDefiningExpr is itself an internal constant equivalent to the null sentinel ("1"), 
        ///   we simply project a ref to the null sentinel, no need for cast
        /// * If the ProjectOp contained exactly one locally defined Var, and it was a constant, then 
        ///   we simply return - we will be looping endlessly otherwise
        /// * If the ProjectOp contained no local definitions, then we don't need to create the
        ///   dummy projectOp - we can simply pull up the Project
        /// * If any of the defining expressions of the local definitions was simply a VarRefOp 
        ///   referencing a Var that was defined by Y, then there is no need to add the case
        ///   expression for that. 
        /// 
        /// 
        /// RuleProcessing context 
        /// The ApplyOp subtree
        /// transformed subtree
        /// Transfomation status
        static bool ProcessOuterApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode) 
        {
            newNode = applyNode; 
            Node projectNode = applyNode.Child1; 
            Node varDefListNode = projectNode.Child1;
 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            ExtendedNodeInfo inputNodeInfo = context.Command.GetExtendedNodeInfo(projectNode.Child0);
            Var sentinelVar = inputNodeInfo.NonNullableDefinitions.First;
 
            //
            // special case handling first - we'll end up in an infinite loop otherwise. 
            // If the ProjectOp is the dummy ProjectOp that we would be building (ie) 
            // it defines only 1 var - and the defining expression is simply a constant
            // 
            if (sentinelVar == null &&
                varDefListNode.Children.Count == 1 &&
                (varDefListNode.Child0.Child0.Op.OpType == OpType.InternalConstant || varDefListNode.Child0.Child0.Op.OpType == OpType.NullSentinel))
            { 
                return false;
            } 
 
            Command command = context.Command;
            Node dummyProjectNode = null; 
            InternalConstantOp nullSentinelDefinitionOp = null;

            // get node information for the project's child
            ExtendedNodeInfo projectInputNodeInfo = command.GetExtendedNodeInfo(projectNode.Child0); 

            // 
            // Build up a dummy project node. 
            // Walk through each local definition of the current project Node, and convert
            // all expressions into case expressions whose value depends on the var 
            // produced by the dummy project node
            //

            // Dev10 #480443: If any of the definitions changes we need to recompute the node info. 
            bool anyVarDefChagned = false;
            foreach (Node varDefNode in varDefListNode.Children) 
            { 
                PlanCompiler.Assert(varDefNode.Op.OpType == OpType.VarDef, "Expected VarDefOp. Found " + varDefNode.Op.OpType + " instead");
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp; 
                if (varRefOp == null || !projectInputNodeInfo.Definitions.IsSet(varRefOp.Var))
                {
                    // do we need to build a dummy project node
                    if (sentinelVar == null) 
                    {
                        nullSentinelDefinitionOp = command.CreateInternalConstantOp(command.IntegerType, 1); 
                        Node dummyConstantExpr = command.CreateNode(nullSentinelDefinitionOp); 
                        Node dummyProjectVarDefListNode = command.CreateVarDefListNode(dummyConstantExpr, out sentinelVar);
                        ProjectOp dummyProjectOp = command.CreateProjectOp(sentinelVar); 
                        dummyProjectOp.Outputs.Or(projectInputNodeInfo.Definitions);
                        dummyProjectNode = command.CreateNode(dummyProjectOp, projectNode.Child0, dummyProjectVarDefListNode);
                    }
 
                    Node currentDefinition;
 
                    // If the null sentinel was just created, and the local definition of the current project Node 
                    // is an internal constant equivalent to the null sentinel, it can be rewritten as a reference
                    // to the null sentinel. 
                    if (nullSentinelDefinitionOp != null && ((true == nullSentinelDefinitionOp.IsEquivalent(varDefNode.Child0.Op)) ||
                        //The null sentinel has the same value of 1, thus it is safe.
                        varDefNode.Child0.Op.OpType == OpType.NullSentinel))
                    { 
                        currentDefinition = command.CreateNode(command.CreateVarRefOp(sentinelVar));
                    } 
                    else 
                    {
                        currentDefinition = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0); 
                    }
                    varDefNode.Child0 = currentDefinition;
                    command.RecomputeNodeInfo(varDefNode);
                    anyVarDefChagned = true; 
                }
            } 
 
            // Recompute node info if needed
            if (anyVarDefChagned) 
            {
                command.RecomputeNodeInfo(varDefListNode);
            }
 
            //
            // If we've created a dummy project node, make that the new child of the applyOp 
            // 
            applyNode.Child1 = dummyProjectNode != null ? dummyProjectNode : projectNode.Child0;
            command.RecomputeNodeInfo(applyNode); 

            //
            // Pull up the project node above the apply node now. Also, make sure that every Var of
            // the applyNode's definitions actually shows up in the new Project 
            //
            projectNode.Child0 = applyNode; 
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0); 
            ProjectOp projectOp = (ProjectOp)projectNode.Op;
            projectOp.Outputs.Or(applyLeftChildNodeInfo.Definitions); 

            newNode = projectNode;
            return true;
        } 
        #endregion
 
        #region ApplyOverAnything 
        internal static readonly PatternMatchRule Rule_CrossApplyOverAnything =
            new PatternMatchRule(new Node(CrossApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)),
                                 ProcessApplyOverAnything);
        internal static readonly PatternMatchRule Rule_OuterApplyOverAnything = 
            new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessApplyOverAnything);
 
        /// 
        /// Converts a CrossApply(X,Y) => CrossJoin(X,Y)
        ///            OuterApply(X,Y) => LeftOuterJoin(X, Y, true)
        ///  only if Y has no external references to X 
        /// 
        /// Rule processing context 
        /// The ApplyOp subtree 
        /// transformed subtree
        /// the transformation status 
        static bool ProcessApplyOverAnything(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            newNode = applyNode;
            Node applyLeftChild = applyNode.Child0; 
            Node applyRightChild = applyNode.Child1;
            ApplyBaseOp applyOp = (ApplyBaseOp)applyNode.Op; 
            Command command = context.Command; 

            ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyRightChild); 
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyLeftChild);

            //
            // If we're currently dealing with an OuterApply, and the right child is guaranteed 
            // to produce at least one row, then we can convert the outer-apply into a cross apply
            // 
            bool convertedToCrossApply = false; 
            if (applyOp.OpType == OpType.OuterApply &&
                applyRightChildNodeInfo.MinRows >= RowCount.One) 
            {
                applyOp = command.CreateCrossApplyOp();
                convertedToCrossApply = true;
            } 

            // 
            // Does the right child reference any of the definitions of the left child? If it 
            // does, then simply return from this function
            // 
            if (applyRightChildNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
            {
                if (convertedToCrossApply)
                { 
                    newNode = command.CreateNode(applyOp, applyLeftChild, applyRightChild);
                    return true; 
                } 
                else
                { 
                    return false;
                }
            }
 
            //
            // So, we now know that the right child does not reference any definitions 
            // from the left. 
            // So, we simply convert the apply into an appropriate join Op
            // 
            if (applyOp.OpType == OpType.CrossApply)
            {
                //
                // Convert "x CrossApply y" into "x CrossJoin y" 
                //
                newNode = command.CreateNode(command.CreateCrossJoinOp(), 
                    applyLeftChild, applyRightChild); 
            }
            else // outer apply 
            {
                //
                // Convert "x OA y" into "x LOJ y on (true)"
                // 
                LeftOuterJoinOp joinOp = command.CreateLeftOuterJoinOp();
                ConstantPredicateOp trueOp = command.CreateTrueOp(); 
                Node trueNode = command.CreateNode(trueOp); 
                newNode = command.CreateNode(joinOp, applyLeftChild, applyRightChild, trueNode);
            } 
            return true;
        }
        #endregion
 
        #region ApplyIntoScalarSubquery
        internal static readonly PatternMatchRule Rule_CrossApplyIntoScalarSubquery = 
            new PatternMatchRule(new Node(CrossApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessApplyIntoScalarSubquery);
        internal static readonly PatternMatchRule Rule_OuterApplyIntoScalarSubquery =
            new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessApplyIntoScalarSubquery); 
 
        /// 
        /// Converts a Apply(X,Y) => Project(X, Y1), where Y1 is a scalar subquery version of Y 
        /// The transformation is valid only if all of the following conditions hold:
        ///     1. Y produces only one output
        ///     2. Y produces at most one row
        ///     3. Y produces at least one row, or the Apply operator in question is an OuterApply 
        /// 
        /// Rule processing context 
        /// The ApplyOp subtree 
        /// transformed subtree
        /// the transformation status 
        static bool ProcessApplyIntoScalarSubquery(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            Command command = context.Command;
            ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child1); 
            OpType applyKind = applyNode.Op.OpType;
 
            if (!CanRewriteApply(applyNode.Child1, applyRightChildNodeInfo, applyKind)) 
            {
                newNode = applyNode; 
                return false;
            }

            // Create the project node over the original input with element over the apply as new projected var 
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
 
            Var oldVar = applyRightChildNodeInfo.Definitions.First; 

            // Project all the outputs from the left child 
            VarVec projectOpOutputs = command.CreateVarVec(applyLeftChildNodeInfo.Definitions);

            //
            // Remap the var defining tree to get it into a consistent state 
            // and then remove all references to oldVar from it to avoid them being wrongly remapped to newVar
            // in subsequent remappings. 
            // 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            trc.RemapSubtree(applyNode.Child1); 
            VarDefinitionRemapper.RemapSubtree(applyNode.Child1, command, oldVar);

            Node elementNode = command.CreateNode(command.CreateElementOp(oldVar.Type), applyNode.Child1);
 
            Var newVar;
            Node varDefListNode = command.CreateVarDefListNode(elementNode, out newVar); 
            projectOpOutputs.Set(newVar); 

            newNode = command.CreateNode( 
                command.CreateProjectOp(projectOpOutputs),
                applyNode.Child0,
                varDefListNode);
 
            // Add the var mapping from oldVar to newVar
            trc.AddVarMapping(oldVar, newVar); 
            return true; 
        }
 
        /// 
        /// Determines whether an applyNode can be rewritten into a projection with a scalar subquery.
        /// It can be done if all of the following conditions hold:
        ///     1. The right child or the apply has only one output 
        ///     2. The right child of the apply produces at most one row
        ///     3. The right child of the apply produces at least one row, or the Apply operator in question is an OuterApply 
        ///  
        /// 
        ///  
        /// 
        /// 
        private static bool CanRewriteApply(Node rightChild, ExtendedNodeInfo applyRightChildNodeInfo, OpType applyKind)
        { 
            //Check whether it produces only one definition
            if (applyRightChildNodeInfo.Definitions.Count != 1) 
            { 
                return false;
            } 

            //Check whether it produces at most one row
            if (applyRightChildNodeInfo.MaxRows != RowCount.One)
            { 
                return false;
            } 
 
            //For cross apply it must also return exactly one row
            if (applyKind == OpType.CrossApply && (applyRightChildNodeInfo.MinRows != RowCount.One)) 
            {
                return false;
            }
 
            //Dev10 #488632: Make sure the right child not only declares to produce only one definition,
            // but has exactly one output. For example, ScanTableOp really outputs all the columns from the table, 
            // but in its ExtendedNodeInfo.Definitions only these that are referenced are shown. 
            // This is to allow for projection pruning of the unreferenced columns.
            if (OutputCountVisitor.CountOutputs(rightChild) != 1) 
            {
                return false;
            }
 
            return true;
        } 
 
        /// 
        /// A visitor that calculates the number of output columns for a subree 
        /// with a given root
        /// 
        internal class OutputCountVisitor : BasicOpVisitorOfT
        { 
            #region Constructors
            internal OutputCountVisitor() 
            { 
            }
            #endregion 

            #region Public Methods
            /// 
            /// Calculates the number of output columns for the subree 
            /// rooted at the given node
            ///  
            ///  
            /// 
            internal static int CountOutputs(Node node) 
            {
                OutputCountVisitor visitor = new OutputCountVisitor();
                return visitor.VisitNode(node);
            } 

            #endregion 
 
            #region Visitor Methods
 
            #region Helpers
            /// 
            /// Visitor for children. Simply visit all children,
            /// and sum the number of their outputs. 
            /// 
            /// Current node 
            ///  
            internal new int VisitChildren(Node n)
            { 
                int result = 0;
                foreach (Node child in n.Children)
                {
                    result += VisitNode(child); 
                }
                return result; 
            } 

            ///  
            /// A default processor for any node.
            /// Returns the sum of the children outputs
            /// 
            ///  
            /// /returns>
            protected override int VisitDefault(Node n) 
            { 
                return VisitChildren(n);
            } 

            #endregion

            #region RelOp Visitors 

            #region SetOp Visitors 
 
            /// 
            /// The number of outputs is same as for any of the inputs 
            /// 
            /// 
            /// 
            ///  
            protected override int VisitSetOp(SetOp op, Node n)
            { 
                return op.Outputs.Count; 
            }
 
            #endregion

            /// 
            /// Distinct 
            /// 
            ///  
            ///  
            /// 
            public override int Visit(DistinctOp op, Node n) 
            {
                return op.Keys.Count;
            }
 
            /// 
            /// FilterOp 
            ///  
            /// 
            ///  
            /// 
            public override int Visit(FilterOp op, Node n)
            {
                return VisitNode(n.Child0); 
            }
 
            ///  
            /// GroupByOp
            ///  
            /// 
            /// 
            /// 
            public override int Visit(GroupByOp op, Node n) 
            {
                return op.Outputs.Count; 
            } 

            ///  
            /// ProjectOp
            /// 
            /// 
            ///  
            /// 
            public override int Visit(ProjectOp op, Node n) 
            { 
                return op.Outputs.Count;
            } 

            #region TableOps
            /// 
            /// ScanTableOp 
            /// 
            ///  
            ///  
            /// 
            public override int Visit(ScanTableOp op, Node n) 
            {
                return op.Table.Columns.Count;
            }
 
            /// 
            /// SingleRowTableOp 
            ///  
            /// 
            ///  
            /// 
            public override int Visit(SingleRowTableOp op, Node n)
            {
                return 0; 
            }
 
            ///  
            /// Same as the input
            ///  
            /// 
            /// 
            /// 
            protected override int VisitSortOp(SortBaseOp op, Node n) 
            {
                return VisitNode(n.Child0); 
            } 
            #endregion
            #endregion 

            #endregion
        }
 
        /// 
        /// A utility class that remaps a given var at its definition and also remaps all its references. 
        /// The given var is remapped to an arbitrary new var. 
        /// If the var is defined by a ScanTable, all the vars defined by that table and all their references
        /// are remapped as well. 
        /// 
        internal class VarDefinitionRemapper : VarRemapper
        {
            private readonly Var m_oldVar; 

            private VarDefinitionRemapper(Var oldVar, Command command) 
                : base(command) 
            {
                this.m_oldVar = oldVar; 
            }

            /// 
            /// Public entry point. 
            /// Remaps the subree rooted at the given tree
            ///  
            ///  
            /// 
            ///  
            internal static void RemapSubtree(Node root, Command command, Var oldVar)
            {
                VarDefinitionRemapper remapper = new VarDefinitionRemapper(oldVar, command);
                remapper.RemapSubtree(root); 
            }
 
            ///  
            /// Update vars in this subtree. Recompute the nodeinfo along the way
            /// Unlike the base implementation, we want to visit the childrent, even if no vars are in the 
            /// remapping dictionary.
            /// 
            /// 
            internal override void RemapSubtree(Node subTree) 
            {
                foreach (Node chi in subTree.Children) 
                { 
                    RemapSubtree(chi);
                } 

                VisitNode(subTree);
                m_command.RecomputeNodeInfo(subTree);
            } 

            ///  
            /// If the node defines the node that needs to be remapped, 
            /// it remaps it to a new var.
            ///  
            /// 
            /// 
            /// 
            public override void Visit(VarDefOp op, Node n) 
            {
                if (op.Var == m_oldVar) 
                { 
                    Var newVar = m_command.CreateComputedVar(n.Child0.Op.Type);
                    n.Op = m_command.CreateVarDefOp(newVar); 
                    AddMapping(m_oldVar, newVar);
                }
            }
 
            /// 
            /// If the columnVars defined by the table contain the var that needs to be remapped 
            /// all the column vars produces by the table are remaped to new vars. 
            /// 
            ///  
            /// 
            /// 
            public override void Visit(ScanTableOp op, Node n)
            { 
                if (op.Table.Columns.Contains(m_oldVar))
                { 
                    ScanTableOp newScanTableOp = m_command.CreateScanTableOp(op.Table.TableMetadata); 
                    VarDefListOp varDefListOp = m_command.CreateVarDefListOp();
                    for (int i = 0; i < op.Table.Columns.Count; i++) 
                    {
                        AddMapping(op.Table.Columns[i], newScanTableOp.Table.Columns[i]);
                    }
                    n.Op = newScanTableOp; 
                }
            } 
 
            /// 
            /// The var that needs to be remapped may be produced by a set op, 
            /// in which case the varmaps need to be updated too.
            /// 
            /// 
            ///  
            protected override void VisitSetOp(SetOp op, Node n)
            { 
                base.VisitSetOp(op, n); 

                if (op.Outputs.IsSet(m_oldVar)) 
                {
                    Var newVar = m_command.CreateSetOpVar(m_oldVar.Type);
                    op.Outputs.Clear(m_oldVar);
                    op.Outputs.Set(newVar); 
                    RemapVarMapKey(op.VarMap[0], newVar);
                    RemapVarMapKey(op.VarMap[1], newVar); 
                    AddMapping(m_oldVar, newVar); 
                }
            } 

            /// 
            /// Replaces the entry in the varMap in which m_oldVar is a key
            /// with an entry in which newVAr is the key and the value remains the same. 
            /// 
            ///  
            ///  
            private void RemapVarMapKey(VarMap varMap, Var newVar)
            { 
                Var value = varMap[m_oldVar];
                varMap.Remove(m_oldVar);
                varMap.Add(newVar, value);
            } 
        }
        #endregion 
 
        #region CrossApply over LeftOuterJoin of SingleRowTable with anything and with constant predicate
        internal static readonly PatternMatchRule Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable = 
            new PatternMatchRule(new Node(CrossApplyOp.Pattern,
                new Node(LeafOp.Pattern),
                new Node(LeftOuterJoinOp.Pattern,
                                          new Node(SingleRowTableOp.Pattern), 
                                          new Node(LeafOp.Pattern),
                                          new Node(ConstantPredicateOp.Pattern))), 
                                 ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable); 
        /// 
        /// Convert a CrossApply(X, LeftOuterJoin(SingleRowTable, Y, on true)) 
        ///    into just OuterApply(X, Y)
        /// 
        /// rule processing context
        /// the join node 
        /// transformed subtree
        /// transformation status 
        static bool ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable(RuleProcessingContext context, Node applyNode, out Node newNode) 
        {
            newNode = applyNode; 
            Node joinNode = applyNode.Child1;

            //Check the value of the predicate
            ConstantPredicateOp joinPredicate = (ConstantPredicateOp)joinNode.Child2.Op; 
            if (joinPredicate.IsFalse)
            { 
                return false; 
            }
 
            applyNode.Op = context.Command.CreateOuterApplyOp();
            applyNode.Child1 = joinNode.Child1;
            return true;
        } 
        #endregion
 
        #region All ApplyOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
                 ApplyOpRules.Rule_CrossApplyOverAnything, 
                 ApplyOpRules.Rule_CrossApplyOverFilter,
                 ApplyOpRules.Rule_CrossApplyOverProject,
                 ApplyOpRules.Rule_OuterApplyOverAnything,
                 ApplyOpRules.Rule_OuterApplyOverProjectInternalConstantOverFilter, 
                 ApplyOpRules.Rule_OuterApplyOverProjectNullSentinelOverFilter,
                 ApplyOpRules.Rule_OuterApplyOverProject, 
                 ApplyOpRules.Rule_OuterApplyOverFilter, 
                 ApplyOpRules.Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable,
                 ApplyOpRules.Rule_CrossApplyIntoScalarSubquery, 
                 ApplyOpRules.Rule_OuterApplyIntoScalarSubquery,
        };
        #endregion
    } 
    #endregion
 
    #region Join Rules 
    /// 
    /// Transformation rules for JoinOps 
    /// 
    internal static class JoinOpRules
    {
        #region JoinOverProject 
        internal static readonly PatternMatchRule Rule_CrossJoinOverProject1 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(LeafOp.Pattern), 
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern))),
                                 ProcessJoinOverProject);
        internal static readonly PatternMatchRule Rule_CrossJoinOverProject2 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverProject); 
        internal static readonly PatternMatchRule Rule_InnerJoinOverProject1 =
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(LeafOp.Pattern),
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverProject);
        internal static readonly PatternMatchRule Rule_InnerJoinOverProject2 = 
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverProject); 
        internal static readonly PatternMatchRule Rule_OuterJoinOverProject2 =
            new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern, 
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverProject); 
        ///  
        /// CrossJoin(Project(A), B) => Project(CrossJoin(A, B), modifiedvars)
        /// InnerJoin(Project(A), B, p) => Project(InnerJoin(A, B, p'), modifiedvars) 
        /// LeftOuterJoin(Project(A), B, p) => Project(LeftOuterJoin(A, B, p'), modifiedvars)
        /// 
        /// Rule processing context
        /// Current JoinOp tree to process 
        /// Transformed subtree
        /// transformation status 
        static bool ProcessJoinOverProject(RuleProcessingContext context, Node joinNode, out Node newNode) 
        {
            newNode = joinNode; 

            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command;
 
            Node joinConditionNode = joinNode.HasChild2 ? joinNode.Child2 : (Node)null;
            Dictionary varRefMap = new Dictionary(); 
            if (joinConditionNode != null && !trc.IsScalarOpTree(joinConditionNode, varRefMap)) 
            {
                return false; 
            }

            Node newJoinNode;
            Node newProjectNode; 

            // Now locate the ProjectOps 
            VarVec newVarSet = command.CreateVarVec(); 
            List varDefNodes = new List();
 
            //
            // Try and handle "project" on both sides only if we're not dealing with
            // an LOJ.
            // 
            if ((joinNode.Op.OpType != OpType.LeftOuterJoin) &&
                (joinNode.Child0.Op.OpType == OpType.Project) && 
                (joinNode.Child1.Op.OpType == OpType.Project)) 
            {
                ProjectOp projectOp1 = (ProjectOp)joinNode.Child0.Op; 
                ProjectOp projectOp2 = (ProjectOp)joinNode.Child1.Op;

                Dictionary varMap1 = trc.GetVarMap(joinNode.Child0.Child1, varRefMap);
                Dictionary varMap2 = trc.GetVarMap(joinNode.Child1.Child1, varRefMap); 
                if (varMap1 == null || varMap2 == null)
                { 
                    return false; 
                }
 
                if (joinConditionNode != null)
                {
                    joinConditionNode = trc.ReMap(joinConditionNode, varMap1);
                    joinConditionNode = trc.ReMap(joinConditionNode, varMap2); 
                    newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0, joinConditionNode);
                } 
                else 
                {
                    newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0); 
                }

                newVarSet.InitFrom(projectOp1.Outputs);
                foreach (Var v in projectOp2.Outputs) 
                {
                    newVarSet.Set(v); 
                } 
                ProjectOp newProjectOp = command.CreateProjectOp(newVarSet);
                varDefNodes.AddRange(joinNode.Child0.Child1.Children); 
                varDefNodes.AddRange(joinNode.Child1.Child1.Children);
                Node varDefListNode = command.CreateNode(
                    command.CreateVarDefListOp(),
                    varDefNodes); 
                newProjectNode = command.CreateNode(newProjectOp,
                    newJoinNode, varDefListNode); 
                newNode = newProjectNode; 
                return true;
            } 

            int projectNodeIdx = -1;
            int otherNodeIdx = -1;
            if (joinNode.Child0.Op.OpType == OpType.Project) 
            {
                projectNodeIdx = 0; 
                otherNodeIdx = 1; 
            }
            else 
            {
                PlanCompiler.Assert(joinNode.Op.OpType != OpType.LeftOuterJoin, "unexpected non-LeftOuterJoin");
                projectNodeIdx = 1;
                otherNodeIdx = 0; 
            }
            Node projectNode = joinNode.Children[projectNodeIdx]; 
 
            ProjectOp projectOp = projectNode.Op as ProjectOp;
            Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap); 
            if (varMap == null)
            {
                return false;
            } 
            ExtendedNodeInfo otherChildInfo = command.GetExtendedNodeInfo(joinNode.Children[otherNodeIdx]);
            VarVec vec = command.CreateVarVec(projectOp.Outputs); 
            vec.Or(otherChildInfo.Definitions); 
            projectOp.Outputs.InitFrom(vec);
            if (joinConditionNode != null) 
            {
                joinConditionNode = trc.ReMap(joinConditionNode, varMap);
                joinNode.Child2 = joinConditionNode;
            } 
            joinNode.Children[projectNodeIdx] = projectNode.Child0; // bypass the projectOp
            context.Command.RecomputeNodeInfo(joinNode); 
 
            newNode = context.Command.CreateNode(projectOp, joinNode, projectNode.Child1);
            return true; 
        }
        #endregion

        #region JoinOverFilter 
        internal static readonly PatternMatchRule Rule_CrossJoinOverFilter1 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(LeafOp.Pattern), 
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern))),
                                 ProcessJoinOverFilter);
        internal static readonly PatternMatchRule Rule_CrossJoinOverFilter2 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverFilter); 
        internal static readonly PatternMatchRule Rule_InnerJoinOverFilter1 =
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(LeafOp.Pattern),
                                          new Node(FilterOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverFilter);
        internal static readonly PatternMatchRule Rule_InnerJoinOverFilter2 = 
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverFilter); 
        internal static readonly PatternMatchRule Rule_OuterJoinOverFilter2 =
            new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern, 
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverFilter); 
        ///  
        /// CrossJoin(Filter(A,p), B) => Filter(CrossJoin(A, B), p)
        /// CrossJoin(A, Filter(B,p)) => Filter(CrossJoin(A, B), p) 
        ///
        /// InnerJoin(Filter(A,p), B, c) => Filter(InnerJoin(A, B, c), p)
        /// InnerJoin(A, Filter(B,p), c) => Filter(InnerJoin(A, B, c), p)
        /// 
        /// LeftOuterJoin(Filter(A,p), B, c) => Filter(LeftOuterJoin(A, B, c), p)
        /// 
        /// Note that the predicate on the right table in a left-outer-join cannot be pulled 
        /// up above the join.
        /// 
        /// 
        /// Rule processing context
        /// Current JoinOp tree to process
        /// transformed subtree 
        /// transformation status
        static bool ProcessJoinOverFilter(RuleProcessingContext context, Node joinNode, out Node newNode) 
        { 
            newNode = joinNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            Command command = trc.Command;

            Node predicateNode = null;
            Node newLeftInput = joinNode.Child0; 
            // get the predicate from the first filter
            if (joinNode.Child0.Op.OpType == OpType.Filter) 
            { 
                predicateNode = joinNode.Child0.Child1;
                newLeftInput = joinNode.Child0.Child0; // bypass the filter 
            }

            // get the predicate from the second filter
            Node newRightInput = joinNode.Child1; 
            if (joinNode.Child1.Op.OpType == OpType.Filter && joinNode.Op.OpType != OpType.LeftOuterJoin)
            { 
                if (predicateNode == null) 
                {
                    predicateNode = joinNode.Child1.Child1; 
                }
                else
                {
                    predicateNode = command.CreateNode( 
                        command.CreateConditionalOp(OpType.And),
                        predicateNode, joinNode.Child1.Child1); 
                } 
                newRightInput = joinNode.Child1.Child0; // bypass the filter
            } 

            // No optimizations to perform if we can't locate the appropriate predicate
            if (predicateNode == null)
            { 
                return false;
            } 
 
            //
            // Create a new join node with the new inputs 
            //
            Node newJoinNode;
            if (joinNode.Op.OpType == OpType.CrossJoin)
            { 
                newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput);
            } 
            else 
            {
                newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput, joinNode.Child2); 
            }

            //
            // create a new filterOp with the combined predicates, and with the 
            // newjoinNode as the input
            // 
            FilterOp newFilterOp = command.CreateFilterOp(); 
            newNode = command.CreateNode(newFilterOp, newJoinNode, predicateNode);
 
            //
            // Mark this subtree so that we don't try to push filters down again
            //
            trc.SuppressFilterPushdown(newNode); 
            return true;
        } 
        #endregion 

        #region Join over SingleRowTable 
        internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable1 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern,
                                          new Node(SingleRowTableOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverSingleRowTable);
        internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable2 = 
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(SingleRowTableOp.Pattern)), 
                                 ProcessJoinOverSingleRowTable);

        internal static readonly PatternMatchRule Rule_LeftOuterJoinOverSingleRowTable =
           new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern, 
                                         new Node(LeafOp.Pattern),
                                         new Node(SingleRowTableOp.Pattern), 
                                         new Node(LeafOp.Pattern)), 
                                ProcessJoinOverSingleRowTable);
        ///  
        /// Convert a CrossJoin(SingleRowTable, X) or CrossJoin(X, SingleRowTable) or LeftOuterJoin(X, SingleRowTable)
        ///    into just "X"
        /// 
        /// rule processing context 
        /// the join node
        /// transformed subtree 
        /// transformation status 
        static bool ProcessJoinOverSingleRowTable(RuleProcessingContext context, Node joinNode, out Node newNode)
        { 
            newNode = joinNode;

            if (joinNode.Child0.Op.OpType == OpType.SingleRowTable)
            { 
                newNode = joinNode.Child1;
            } 
            else 
            {
                newNode = joinNode.Child0; 
            }
            return true;
        }
        #endregion 

        #region Misc 
        #endregion 

        #region All JoinOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
            Rule_CrossJoinOverProject1,
            Rule_CrossJoinOverProject2,
            Rule_InnerJoinOverProject1, 
            Rule_InnerJoinOverProject2,
            Rule_OuterJoinOverProject2, 
 
            Rule_CrossJoinOverFilter1,
            Rule_CrossJoinOverFilter2, 
            Rule_InnerJoinOverFilter1,
            Rule_InnerJoinOverFilter2,
            Rule_OuterJoinOverFilter2,
 
            Rule_CrossJoinOverSingleRowTable1,
            Rule_CrossJoinOverSingleRowTable2, 
            Rule_LeftOuterJoinOverSingleRowTable, 
        };
 
        #endregion
    }
    #endregion
 
    #region SingleRowOp Rules
    ///  
    /// Rules for SingleRowOp 
    /// 
    internal static class SingleRowOpRules 
    {
        internal static readonly PatternMatchRule Rule_SingleRowOpOverAnything =
            new PatternMatchRule(new Node(SingleRowOp.Pattern,
                                     new Node(LeafOp.Pattern)), 
                                 ProcessSingleRowOpOverAnything);
        ///  
        /// Convert a 
        ///    SingleRowOp(X) => X
        /// if X produces at most one row 
        /// 
        /// Rule Processing context
        /// Current subtree
        /// transformed subtree 
        /// Transformation status
        static bool ProcessSingleRowOpOverAnything(RuleProcessingContext context, Node singleRowNode, out Node newNode) 
        { 
            newNode = singleRowNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            ExtendedNodeInfo childNodeInfo = context.Command.GetExtendedNodeInfo(singleRowNode.Child0);

            // If the input to this Op can produce at most one row, then we don't need the
            // singleRowOp - simply return the input 
            if (childNodeInfo.MaxRows <= RowCount.One)
            { 
                newNode = singleRowNode.Child0; 
                return true;
            } 

            //
            // if the current node is a FilterOp, then try and determine if the FilterOp
            // produces one row at most 
            //
            if (singleRowNode.Child0.Op.OpType == OpType.Filter) 
            { 
                Predicate predicate = new Predicate(context.Command, singleRowNode.Child0.Child1);
                if (predicate.SatisfiesKey(childNodeInfo.Keys.KeyVars, childNodeInfo.Definitions)) 
                {
                    childNodeInfo.MaxRows = RowCount.One;
                    newNode = singleRowNode.Child0;
                    return true; 
                }
            } 
 
            // we couldn't do anything
            return false; 
        }

        internal static readonly PatternMatchRule Rule_SingleRowOpOverProject =
           new PatternMatchRule(new Node(SingleRowOp.Pattern, 
                             new Node(ProjectOp.Pattern,
                                   new Node(LeafOp.Pattern), new Node(LeafOp.Pattern))), 
                         ProcessSingleRowOpOverProject); 
        /// 
        /// Convert 
        ///    SingleRowOp(Project) => Project(SingleRowOp)
        /// 
        /// Rule Processing context
        /// current subtree 
        /// transformeed subtree
        /// transformation status 
        static bool ProcessSingleRowOpOverProject(RuleProcessingContext context, Node singleRowNode, out Node newNode) 
        {
            newNode = singleRowNode; 
            Node projectNode = singleRowNode.Child0;
            Node projectNodeInput = projectNode.Child0;

            // Simply push the SingleRowOp below the ProjectOp 
            singleRowNode.Child0 = projectNodeInput;
            context.Command.RecomputeNodeInfo(singleRowNode); 
            projectNode.Child0 = singleRowNode; 

            newNode = projectNode; 
            return true; // subtree modified internally
        }

        #region All SingleRowOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
            Rule_SingleRowOpOverAnything, 
            Rule_SingleRowOpOverProject, 
        };
        #endregion 
    }
    #endregion

    #region SetOp Rules 
    /// 
    /// SetOp Transformation Rules 
    ///  
    internal static class SetOpRules
    { 
        #region SetOpOverFilters
        internal static readonly SimpleRule Rule_UnionAllOverEmptySet =
            new SimpleRule(OpType.UnionAll, ProcessSetOpOverEmptySet);
        internal static readonly SimpleRule Rule_IntersectOverEmptySet = 
            new SimpleRule(OpType.Intersect, ProcessSetOpOverEmptySet);
        internal static readonly SimpleRule Rule_ExceptOverEmptySet = 
            new SimpleRule(OpType.Except, ProcessSetOpOverEmptySet); 

        ///  
        /// Process a SetOp when one of the inputs is an emptyset.
        ///
        /// An emptyset is represented by a Filter(X, ConstantPredicate)
        ///    where the ConstantPredicate has a value of "false" 
        ///
        /// The general rules are 
        ///    UnionAll(X, EmptySet) => X 
        ///    UnionAll(EmptySet, X) => X
        ///    Intersect(EmptySet, X) => EmptySet 
        ///    Intersect(X, EmptySet) => EmptySet
        ///    Except(EmptySet, X) => EmptySet
        ///    Except(X, EmptySet) => X
        /// 
        /// These rules then translate into
        ///    UnionAll: return the non-empty input 
        ///    Intersect: return the empty input 
        ///    Except: return the "left" input
        ///  
        /// Rule processing context
        /// the current setop tree
        /// Index of the filter node in the setop
        /// transformed subtree 
        /// transformation status
        private static bool ProcessSetOpOverEmptySet(RuleProcessingContext context, Node setOpNode, out Node newNode) 
        { 
            bool leftChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child0).MaxRows == RowCount.Zero;
            bool rightChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child1).MaxRows == RowCount.Zero; 

            if (!leftChildIsEmptySet && !rightChildIsEmptySet)
            {
                newNode = setOpNode; 
                return false;
            } 
 
            int indexToReturn;
            SetOp setOp = (SetOp)setOpNode.Op; 
            if (!rightChildIsEmptySet && setOp.OpType == OpType.UnionAll ||
                !leftChildIsEmptySet && setOp.OpType == OpType.Intersect)
            {
                indexToReturn = 1; 
            }
            else 
            { 
                indexToReturn = 0;
            } 

            newNode = setOpNode.Children[indexToReturn];

            TransformationRulesContext trc = (TransformationRulesContext)context; 
            foreach (KeyValuePair kv in setOp.VarMap[indexToReturn])
            { 
                trc.AddVarMapping(kv.Key, kv.Value); 
            }
            return true; 
        }

        #endregion
 
        #region All SetOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
            Rule_UnionAllOverEmptySet, 
            Rule_IntersectOverEmptySet,
            Rule_ExceptOverEmptySet, 
        };
        #endregion
    }
    #endregion 

    #region GroupByOp Rules 
    ///  
    /// Transformation Rules for GroupByOps
    ///  
    internal static class GroupByOpRules
    {
        #region GroupByOpWithSimpleVarRedefinitions
        internal static readonly SimpleRule Rule_GroupByOpWithSimpleVarRedefinitions = new SimpleRule(OpType.GroupBy, ProcessGroupByWithSimpleVarRedefinitions); 
        /// 
        /// If the GroupByOp defines some computedVars as part of its keys, but those computedVars are simply 
        /// redefinitions of other Vars, then eliminate the computedVars. 
        ///
        /// GroupBy(X, VarDefList(VarDef(cv1, VarRef(v1)), ...), VarDefList(...)) 
        ///    can be transformed into
        /// GroupBy(X, VarDefList(...))
        /// where cv1 has now been replaced by v1
        ///  
        /// Rule processing context
        /// current subtree 
        /// transformed subtree 
        /// transformation status
        static bool ProcessGroupByWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode) 
        {
            newNode = n;
            GroupByOp groupByOp = (GroupByOp)n.Op;
            // no local keys? nothing to do 
            if (n.Child1.Children.Count == 0)
            { 
                return false; 
            }
 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command;

            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n); 

            // 
            // Check to see if any of the computed Vars defined by this GroupByOp 
            // are simple redefinitions of other VarRefOps. Consider only those
            // VarRefOps that are not "external" references 
            //
            bool canEliminateSomeVars = false;
            foreach (Node varDefNode in n.Child1.Children)
            { 
                Node definingExprNode = varDefNode.Child0;
                if (definingExprNode.Op.OpType == OpType.VarRef) 
                { 
                    VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
                    if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var)) 
                    {
                        // this is a Var that we should remove
                        canEliminateSomeVars = true;
                    } 
                }
            } 
 
            // Did we have any redefinitions
            if (!canEliminateSomeVars) 
            {
                return false;
            }
 
            //
            // OK. We've now identified a set of vars that are simple redefinitions. 
            // Try and replace the computed Vars with the Vars that they're redefining 
            //
 
            // Lets now build up a new VarDefListNode
            List newVarDefNodes = new List();
            foreach (Node varDefNode in n.Child1.Children)
            { 
                VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp; 
                if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var)) 
                {
                    groupByOp.Outputs.Clear(varDefOp.Var); 
                    groupByOp.Outputs.Set(varRefOp.Var);
                    groupByOp.Keys.Clear(varDefOp.Var);
                    groupByOp.Keys.Set(varRefOp.Var);
                    trc.AddVarMapping(varDefOp.Var, varRefOp.Var); 
                }
                else 
                { 
                    newVarDefNodes.Add(varDefNode);
                } 
            }

            // Create a new vardeflist node, and set that as Child1 for the group by op
            Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes); 
            n.Child1 = newVarDefListNode;
            return true; // subtree modified 
        } 
        #endregion
 
        #region GroupByOverProject
        internal static readonly PatternMatchRule Rule_GroupByOverProject =
            new PatternMatchRule(new Node(GroupByOp.Pattern,
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessGroupByOverProject); 
        /// 
        /// Converts a GroupBy(Project(X, c1,..ck), agg1, agg2, .. aggm) =>
        ///            GroupBy(X, agg1', agg2', .. aggm')
        /// where agg1', agg2', .. aggm'  are the "mapped" versions 
        /// of agg1, agg2, .. aggm, such that the references to c1, ... ck are
        /// replaced by their definitions. 
        /// 
        /// We only do this if each c1, ..ck is refereneced (in aggregates) at most once or it is a constant.
        ///  
        /// Rule processing context
        /// Current ProjectOp node
        /// modified subtree
        /// Transformation status 
        static bool ProcessGroupByOverProject(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n; 
            GroupByOp op = (GroupByOp)n.Op;
            Command command = ((TransformationRulesContext)context).Command; 
            Node projectNode = n.Child0;
            Node projectNodeVarDefList = projectNode.Child1;

            Node keys = n.Child1; 
            Node aggregates = n.Child2;
 
            // If there are any keys, we should not remove the inner project 
            if (keys.Children.Count > 0)
            { 
                return false;
            }

            //Get a list of all defining vars 
            VarVec projectDefinitions = command.GetExtendedNodeInfo(projectNode).LocalDefinitions;
 
            //If any of the defined vars is output, than we need the extra project anyway. 
            if (op.Outputs.Overlaps(projectDefinitions))
            { 
                return false;
            }

            bool createdNewProjectDefinitions = false; 

            //If there are any constants remove them from the list that needs to be tested, 
            //These can safely be replaced 
            for (int i = 0; i < projectNodeVarDefList.Children.Count; i++)
            { 
                Node varDefNode = projectNodeVarDefList.Children[i];
                if (varDefNode.Child0.Op.OpType == OpType.Constant || varDefNode.Child0.Op.OpType == OpType.InternalConstant || varDefNode.Child0.Op.OpType == OpType.NullSentinel)
                {
                    //We shouldn't modify the original project definitions, thus we copy it 
                    // the first time we encounter a constant
                    if (!createdNewProjectDefinitions) 
                    { 
                        projectDefinitions = command.CreateVarVec(projectDefinitions);
                        createdNewProjectDefinitions = true; 
                    }
                    projectDefinitions.Clear(((VarDefOp)varDefNode.Op).Var);
                }
            } 

            if (VarRefUsageFinder.AnyVarUsedMoreThanOnce(projectDefinitions, aggregates, command)) 
            { 
                return false;
            } 

            //If we got here it means that all vars were either constants, or used at most once
            // Create a dictionary to be used for remapping the keys and the aggregates
            Dictionary varToDefiningNode = new Dictionary(projectNodeVarDefList.Children.Count); 
            for (int j = 0; j < projectNodeVarDefList.Children.Count; j++)
            { 
                Node varDefNode = projectNodeVarDefList.Children[j]; 
                Var var = ((VarDefOp)varDefNode.Op).Var;
                varToDefiningNode.Add(var, varDefNode.Child0); 
            }

            newNode.Child2 = VarRefReplacer.Replace(varToDefiningNode, aggregates, command);
 
            newNode.Child0 = projectNode.Child0;
            return true; 
        } 

        ///  
        /// Replaces each occurance of the given vars with their definitions.
        /// 
        internal class VarRefReplacer : BasicOpVisitorOfNode
        { 
            private Dictionary m_varReplacementTable;
            private Command m_command; 
 
            private VarRefReplacer(Dictionary varReplacementTable, Command command)
            { 
                this.m_varReplacementTable = varReplacementTable;
                this.m_command = command;
            }
 
            /// 
            /// "Public" entry point. In the subtree rooted at the given root, 
            /// replace each occurance of the given vars with their definitions, 
            /// where each key-value pair in the dictionary is a var-definition pair.
            ///  
            /// 
            /// 
            /// 
            ///  
            internal static Node Replace(Dictionary varReplacementTable, Node root, Command command)
            { 
                VarRefReplacer replacer = new VarRefReplacer(varReplacementTable, command); 
                return replacer.VisitNode(root);
            } 

            public override Node Visit(VarRefOp op, Node n)
            {
                Node replacementNode; 
                if (m_varReplacementTable.TryGetValue(op.Var, out replacementNode))
                { 
                    return replacementNode; 
                }
                else 
                {
                    return n;
                }
            } 

            ///  
            /// Recomputes node info post regular processing. 
            /// 
            ///  
            /// 
            protected override Node VisitDefault(Node n)
            {
                Node result = base.VisitDefault(n); 
                m_command.RecomputeNodeInfo(result);
                return result; 
            } 
        }
 
        /// 
        /// Used to determine whether any of the given vars occurs more than once
        /// in a given subtree.
        ///  
        internal class VarRefUsageFinder : BasicOpVisitor
        { 
            private bool m_anyUsedMoreThenOnce = false; 
            private VarVec m_varVec;
            private VarVec m_usedVars; 

            private VarRefUsageFinder(VarVec varVec, Command command)
            {
                this.m_varVec = varVec; 
                this.m_usedVars = command.CreateVarVec();
            } 
 
            /// 
            /// Public entry point. Returns true if at least one of the given vars occurs more than 
            /// once in the subree rooted at the given root.
            /// 
            /// 
            ///  
            /// 
            ///  
            internal static bool AnyVarUsedMoreThanOnce(VarVec varVec, Node root, Command command) 
            {
                VarRefUsageFinder usageFinder = new VarRefUsageFinder(varVec, command); 
                usageFinder.VisitNode(root);
                return usageFinder.m_anyUsedMoreThenOnce;
            }
 
            public override void Visit(VarRefOp op, Node n)
            { 
                Var referencedVar = op.Var; 
                if (m_varVec.IsSet(referencedVar))
                { 
                    if (m_usedVars.IsSet(referencedVar))
                    {
                        this.m_anyUsedMoreThenOnce = true;
                    } 
                    else
                    { 
                        m_usedVars.Set(referencedVar); 
                    }
                } 
            }

            protected override void VisitChildren(Node n)
            { 
                //small optimization: no need to continue if we have the answer
                if (m_anyUsedMoreThenOnce) 
                { 
                    return;
                } 
                base.VisitChildren(n);
            }
        }
        #endregion 

        #region GroupByOpWithNoAggregates 
        internal static readonly PatternMatchRule Rule_GroupByOpWithNoAggregates = 
            new PatternMatchRule(new Node(GroupByOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern),
                                          new Node(VarDefListOp.Pattern)),
                                 ProcessGroupByOpWithNoAggregates);
        ///  
        /// If the GroupByOp has no aggregates:
        /// 
        /// (1) and if it includes all all the keys of the input, than it is unnecessary 
        /// GroupBy (X, keys) -> Project(X, keys) where keys includes all keys of X.
        /// 
        /// (2) else it can be turned into a Distinct:
        /// GroupBy (X, keys) -> Distinct(X, keys)
        ///
        ///  
        /// Rule processing context
        /// current subtree 
        /// transformed subtree 
        /// transformation status
        static bool ProcessGroupByOpWithNoAggregates(RuleProcessingContext context, Node n, out Node newNode) 
        {
            Command command = context.Command;
            GroupByOp op = (GroupByOp)n.Op;
 
            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
            ProjectOp newOp = command.CreateProjectOp(op.Keys); 
 
            VarDefListOp varDefListOp = command.CreateVarDefListOp();
            Node varDefListNode = command.CreateNode(varDefListOp); 

            newNode = command.CreateNode(newOp, n.Child0, n.Child1);

            //If we know the keys of the input and the list of keys includes them all, 
            // this is the result, otherwise add distinct
            if (nodeInfo.Keys.NoKeys || !op.Keys.Subsumes(nodeInfo.Keys.KeyVars)) 
            { 
                newNode = command.CreateNode(command.CreateDistinctOp(command.CreateVarVec(op.Keys)), newNode);
            } 
            return true;
        }
        #endregion
 
        #region All GroupByOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions, 
                 GroupByOpRules.Rule_GroupByOverProject,
                 GroupByOpRules.Rule_GroupByOpWithNoAggregates, 
        };
        #endregion
    }
    #endregion 

    #region Sorting Rules 
    ///  
    /// Transformation Rules for SortOp
    ///  
    internal static class SortOpRules
    {
        #region SortOpOverAtMostOneRow
        internal static readonly SimpleRule Rule_SortOpOverAtMostOneRow = new SimpleRule(OpType.Sort, ProcessSortOpOverAtMostOneRow); 
        /// 
        /// If the SortOp's input is guaranteed to produce at most 1 row, remove the node with the SortOp: 
        ///  Sort(X) => X, if X is guaranteed to produce no more than 1 row 
        /// 
        /// Rule processing context 
        /// current subtree
        /// transformed subtree
        /// transformation status
        static bool ProcessSortOpOverAtMostOneRow(RuleProcessingContext context, Node n, out Node newNode) 
        {
            ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0); 
 
            //If the input has at most one row, omit the SortOp
            if (nodeInfo.MaxRows == RowCount.Zero || nodeInfo.MaxRows == RowCount.One) 
            {
                newNode = n.Child0;
                return true;
            } 

            //Otherwise return the node as is 
            newNode = n; 
            return false;
        } 
        #endregion

        #region All SortOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 SortOpRules.Rule_SortOpOverAtMostOneRow,
        }; 
        #endregion 
    }
 
    /// 
    /// Transformation Rules for ConstrainedSortOp
    /// 
    internal static class ConstrainedSortOpRules 
    {
        #region ConstrainedSortOpOverEmptySet 
        internal static readonly SimpleRule Rule_ConstrainedSortOpOverEmptySet = new SimpleRule(OpType.ConstrainedSort, ProcessConstrainedSortOpOverEmptySet); 
        /// 
        /// If the ConstrainedSortOp's input is guaranteed to produce no rows, remove the ConstrainedSortOp completly: 
        ///    CSort(EmptySet) => EmptySet
        /// 
        /// Rule processing context
        /// current subtree 
        /// transformed subtree
        /// transformation status 
        static bool ProcessConstrainedSortOpOverEmptySet(RuleProcessingContext context, Node n, out Node newNode) 
        {
            ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0); 

            //If the input has no rows, remove the ConstraintSortOp node completly
            if (nodeInfo.MaxRows == RowCount.Zero)
            { 
                newNode = n.Child0;
                return true; 
            } 

            newNode = n; 
            return false;
        }
        #endregion
 
        #region All ConstrainedSortOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 ConstrainedSortOpRules.Rule_ConstrainedSortOpOverEmptySet, 
        };
        #endregion 
    }
    #endregion

    #region DistinctOp Rules 
    /// 
    /// Transformation Rules for DistinctOp 
    ///  
    internal static class DistinctOpRules
    { 
        #region DistinctOpOfKeys
        internal static readonly SimpleRule Rule_DistinctOpOfKeys = new SimpleRule(OpType.Distinct, ProcessDistinctOpOfKeys);
        /// 
        /// If the DistinctOp includes all all the keys of the input, than it is unnecessary. 
        /// Distinct (X, distinct_keys) -> Project( X, distinct_keys) where distinct_keys includes all keys of X.
        ///  
        /// Rule processing context 
        /// current subtree
        /// transformed subtree 
        /// transformation status
        static bool ProcessDistinctOpOfKeys(RuleProcessingContext context, Node n, out Node newNode)
        {
            Command command = context.Command; 

            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0); 
 
            DistinctOp op = (DistinctOp)n.Op;
 
            //If we know the keys of the input and the list of distinct keys includes them all, omit the distinct
            if (!nodeInfo.Keys.NoKeys && op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
            {
                ProjectOp newOp = command.CreateProjectOp(op.Keys); 

                //Create empty vardef list 
                VarDefListOp varDefListOp = command.CreateVarDefListOp(); 
                Node varDefListNode = command.CreateNode(varDefListOp);
 
                newNode = command.CreateNode(newOp, n.Child0, varDefListNode);
                return true;
            }
 
            //Otherwise return the node as is
            newNode = n; 
            return false; 
        }
        #endregion 

        #region All DistinctOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
                 DistinctOpRules.Rule_DistinctOpOfKeys, 
        };
        #endregion 
    } 
    #endregion
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System; 
using System.Collections.Generic;
using System.Collections.ObjectModel;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization; 
using System.Linq;
using System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees; 

namespace System.Data.Query.PlanCompiler 
{
    internal class TransformationRulesContext : RuleProcessingContext
    {
        #region public methods and properties 

        ///  
        /// Whether any rule was applied that may have caused modifications such that projection pruning 
        /// may be useful
        ///  
        internal bool ProjectionPrunningRequired { get { return this.m_projectionPrunningRequired; } }

        /// 
        /// Whether any rule was applied that may have caused modifications such that reapplying 
        /// the nullability rules may be useful
        ///  
        internal bool ReapplyNullabilityRules { get { return this.m_reapplyNullabilityRules; } } 

        ///  
        /// Remap the given subree using the current remapper
        /// 
        /// 
        internal void RemapSubtree(Node subTree) 
        {
            this.m_remapper.RemapSubtree(subTree); 
        } 

        ///  
        /// Adds a mapping from oldVar to newVar
        /// 
        /// 
        ///  
        internal void AddVarMapping(Var oldVar, Var newVar)
        { 
            m_remapper.AddMapping(oldVar, newVar); 
            m_remappedVars.Set(oldVar);
        } 

        /// 
        /// "Remap" an expression tree, replacing all references to vars in varMap with
        /// copies of the corresponding expression 
        /// The subtree is modified *inplace* - it is the caller's responsibility to make
        /// a copy of the subtree if necessary. 
        /// The "replacement" expression (the replacement for the VarRef) is copied and then 
        /// inserted into the appropriate location into the subtree.
        /// 
        /// Note: we only support replacements in simple ScalarOp trees. This must be
        /// validated by the caller.
        ///
        ///  
        /// Current subtree to process
        ///  
        /// The updated subtree 
        internal Node ReMap(Node node, Dictionary varMap)
        { 
            PlanCompiler.Assert(node.Op.IsScalarOp, "Expected a scalarOp: Found " + Dump.AutoString.ToString(node.Op.OpType));

            // Replace varRefOps by the corresponding expression in the map, if any
            if (node.Op.OpType == OpType.VarRef) 
            {
                VarRefOp varRefOp = node.Op as VarRefOp; 
                Node newNode = null; 
                if (varMap.TryGetValue(varRefOp.Var, out newNode))
                { 
                    newNode = this.Copy(newNode);
                    return newNode;
                }
                else 
                {
                    return node; 
                } 
            }
 
            // Simply process the result of the children.
            for (int i = 0; i < node.Children.Count; i++)
            {
                node.Children[i] = ReMap(node.Children[i], varMap); 
            }
 
            // We may have changed something deep down 
            this.Command.RecomputeNodeInfo(node);
            return node; 
        }

        /// 
        /// Makes a copy of the appropriate subtree - with a simple accelerator for VarRefOp 
        /// since that's likely to be the most command case
        ///  
        /// the subtree to copy 
        /// the copy of the subtree
        internal Node Copy(Node node) 
        {
            if (node.Op.OpType == OpType.VarRef)
            {
                VarRefOp op = node.Op as VarRefOp; 
                return this.Command.CreateNode(this.Command.CreateVarRefOp(op.Var));
            } 
            else 
            {
                return OpCopier.Copy(this.Command, node); 
            }
        }

        ///  
        /// Checks to see if the current subtree only contains ScalarOps
        ///  
        /// current subtree 
        /// true, if the subtree contains only ScalarOps
        internal bool IsScalarOpTree(Node node) 
        {
            int nodeCount = 0;
            return IsScalarOpTree(node, null, ref nodeCount);
        } 

        ///  
        /// Is the given var guaranteed to be non-nullable with regards to the node 
        /// that is currently being processed.
        /// True, if it is listed as such on any on the node infos on any of the 
        /// current relop ancestors.
        /// 
        /// 
        ///  
        internal bool IsNonNullable(Var var)
        { 
            foreach (Node relOpAncestor in m_relOpAncestors) 
            {
                // Rules applied to the children of the relOpAncestor may have caused it change. 
                // Thus, if the node is used, it has to have its node info recomputed
                Command.RecomputeNodeInfo(relOpAncestor);
                ExtendedNodeInfo nodeInfo = Command.GetExtendedNodeInfo(relOpAncestor);
                if (nodeInfo.NonNullableVisibleDefinitions.IsSet(var)) 
                {
                    return true; 
                } 
                else if (nodeInfo.LocalDefinitions.IsSet(var))
                { 
                    //The var is defined on this ancestor but is not non-nullable,
                    // therefore there is no need to further check other ancestors
                    return false;
                } 
            }
            return false; 
        } 

        ///  
        /// Is it safe to use a null sentinel with any value?
        /// It may not be safe if:
        /// 1. The top most sort includes null sentinels. If the null sentinel is replaced with a different value
        /// and is used as a sort key it may change the sorting results 
        /// 2. If any of the ancestors is Distinct, GroupBy, Intersect or Except,
        /// because the null sentinel may be used as a key. 
        /// 3. If the null sentinel is defined in the left child of an apply it may be used at the right side, 
        /// thus in these cases we also verify that the right hand side does not have any Distinct, GroupBy,
        /// Intersect or Except. 
        /// 
        internal bool CanChangeNullSentinelValue
        {
            get 
            {
                //Is there a sort that includes null sentinels 
                if (this.m_compilerState.HasSortingOnNullSentinels) 
                {
                    return false; 
                }

                //Is any of the ancestors Distinct, GroupBy, Intersect or Except
                if (this.m_relOpAncestors.Any(a => IsOpNotSafeForNullSentinelValueChange(a.Op.OpType))) 
                {
                    return false; 
                } 

                // Is the null sentinel defined in the left child of an apply and if so, 
                // does the right hand side have any Distinct, GroupBy, Intersect or Except.
                var applyAncestors = this.m_relOpAncestors.Where(a =>
                         a.Op.OpType == OpType.CrossApply ||
                         a.Op.OpType == OpType.OuterApply); 

                //If the sentinel comes from the right hand side it is ok. 
                foreach (Node applyAncestor in applyAncestors) 
                {
                    if (!this.m_relOpAncestors.Contains(applyAncestor.Child1) && HasOpNotSafeForNullSentinelValueChange(applyAncestor.Child1)) 
                    {
                        return false;
                    }
                } 
                return true;
            } 
        } 

        ///  
        /// Is the op not safe for null sentinel value change
        /// 
        /// 
        ///  
        internal static bool IsOpNotSafeForNullSentinelValueChange(OpType optype)
        { 
            return optype == OpType.Distinct || 
                    optype == OpType.GroupBy ||
                    optype == OpType.Intersect || 
                    optype == OpType.Except;
        }

        ///  
        /// Does the given subtree contain a node with an op that
        /// is not safer for null sentinel value change 
        ///  
        /// 
        ///  
        internal static bool HasOpNotSafeForNullSentinelValueChange(Node n)
        {
            if (IsOpNotSafeForNullSentinelValueChange(n.Op.OpType))
            { 
                return true;
            } 
            foreach (Node child in n.Children) 
            {
                if (HasOpNotSafeForNullSentinelValueChange(child)) 
                {
                    return true;
                }
            } 
            return false;
        } 
 
        /// 
        /// Is this is a scalar-op tree? Also return a dictionary of var refcounts (ie) 
        /// for each var encountered in the tree, determine the number of times it has
        /// been seen
        /// 
        /// current subtree 
        /// dictionary of var refcounts to fill in
        ///  
        internal bool IsScalarOpTree(Node node, Dictionary varRefMap) 
        {
            PlanCompiler.Assert(varRefMap != null, "Null varRef map"); 

            int nodeCount = 0;
            return IsScalarOpTree(node, varRefMap, ref nodeCount);
        } 

        ///  
        /// Get a mapping from Var->Expression for a VarDefListOp tree. This information 
        /// will be used by later stages to replace all references to the Vars by the
        /// corresponding expressions 
        ///
        /// This function uses a few heuristics along the way. It uses the varRefMap
        /// parameter to determine if a computed Var (defined by this VarDefListOp)
        /// has been referenced multiple times, and if it has, it checks to see if 
        /// the defining expression is too big (> 100 nodes). This is to avoid
        /// bloating up the entire query tree with too many copies. 
        /// 
        /// 
        /// The varDefListOp subtree 
        /// ref counts for each referenced var
        /// mapping from Var->replacement xpressions
        internal Dictionary GetVarMap(Node varDefListNode, Dictionary varRefMap)
        { 
            VarDefListOp varDefListOp = (VarDefListOp)varDefListNode.Op;
 
            Dictionary varMap = new Dictionary(); 
            foreach (Node chi in varDefListNode.Children)
            { 
                VarDefOp varDefOp = (VarDefOp)chi.Op;
                int nonLeafNodeCount = 0;
                int refCount = 0;
                if (!IsScalarOpTree(chi.Child0, null, ref nonLeafNodeCount)) 
                {
                    return null; 
                } 
                //
                // More heuristics. If there are multiple references to this Var *and* 
                // the defining expression for the Var is "expensive" (ie) has larger than
                // 100 nodes, then simply pretend that this is too hard to do
                // Note: we check for more than 2 references, (rather than just more than 1) - this
                // is simply to let some additional cases through 
                //
                if ((nonLeafNodeCount > 100) && 
                    (varRefMap != null) && 
                    varRefMap.TryGetValue(varDefOp.Var, out refCount) &&
                    (refCount > 2)) 
                {
                    return null;
                }
 
                Node n;
                if (varMap.TryGetValue(varDefOp.Var, out n)) 
                { 
                    PlanCompiler.Assert(n == chi.Child0, "reusing varDef for different Node?");
                } 
                else
                {
                    varMap.Add(varDefOp.Var, chi.Child0);
                } 
            }
 
            return varMap; 
        }
 
        /// 
        /// Builds a NULLIF expression (ie) a Case expression that looks like
        ///    CASE WHEN v is null THEN null ELSE expr END
        /// where v is the conditionVar parameter, and expr is the value of the expression 
        /// when v is non-null
        ///  
        /// null discriminator var 
        /// expression
        ///  
        internal Node BuildNullIfExpression(Var conditionVar, Node expr)
        {
            VarRefOp varRefOp = this.Command.CreateVarRefOp(conditionVar);
            Node varRefNode = this.Command.CreateNode(varRefOp); 
            Node whenNode = this.Command.CreateNode(this.Command.CreateConditionalOp(OpType.IsNull), varRefNode);
            Node elseNode = expr; 
            Node thenNode = this.Command.CreateNode(this.Command.CreateNullOp(elseNode.Op.Type)); 
            Node caseNode = this.Command.CreateNode(this.Command.CreateCaseOp(elseNode.Op.Type), whenNode, thenNode, elseNode);
 
            return caseNode;
        }

        #region Rule Interactions 
        /// 
        /// Shut off filter pushdown for this subtree 
        ///  
        /// 
        internal void SuppressFilterPushdown(Node n) 
        {
            m_suppressions[n] = n;
        }
 
        /// 
        /// Is filter pushdown shut off for this subtree? 
        ///  
        /// 
        ///  
        internal bool IsFilterPushdownSuppressed(Node n)
        {
            return m_suppressions.ContainsKey(n);
        } 

        ///  
        /// Given a list of vars try to get one that is of type Int32 
        /// 
        ///  
        /// 
        /// 
        internal static bool TryGetInt32Var(IEnumerable varList, out Var int32Var)
        { 
            foreach (Var v in varList)
            { 
                // Any Int32 var regardless of the fasets will do 
                System.Data.Metadata.Edm.PrimitiveTypeKind typeKind;
                if (System.Data.Common.TypeHelpers.TryGetPrimitiveTypeKind(v.Type, out typeKind) && typeKind == System.Data.Metadata.Edm.PrimitiveTypeKind.Int32) 
                {
                    int32Var = v;
                    return true;
                } 
            }
            int32Var = null; 
            return false; 
        }
 
        #endregion

        #endregion
 
        #region constructors
        internal TransformationRulesContext(PlanCompiler compilerState) 
            : base(compilerState.Command) 
        {
            m_compilerState = compilerState; 
            m_remapper = new VarRemapper(compilerState.Command);
            m_suppressions = new Dictionary();
            m_remappedVars = compilerState.Command.CreateVarVec();
        } 

        #endregion 
 
        #region private state
        private readonly PlanCompiler m_compilerState; 
        private readonly VarRemapper m_remapper;
        private readonly Dictionary m_suppressions;
        private readonly VarVec m_remappedVars;
        private bool m_projectionPrunningRequired = false; 
        private bool m_reapplyNullabilityRules = false;
        private Stack m_relOpAncestors = new Stack(); 
#if DEBUG 
        /// 
        /// Used to see all the applied rules. 
        /// One way to use it is to put a conditional breakpoint at the end of
        /// PostProcessSubTree with the condition m_relOpAncestors.Count == 0
        /// 
        internal readonly System.Text.StringBuilder appliedRules = new System.Text.StringBuilder(); 
#endif
        #endregion 
 
        #region RuleProcessingContext Overrides
        ///  
        /// Callback function to invoke *before* rules are applied.
        /// Calls the VarRemapper to update any Vars in this node, and recomputes
        /// the nodeinfo
        ///  
        /// 
        internal override void PreProcess(Node n) 
        { 
            m_remapper.RemapNode(n);
            Command.RecomputeNodeInfo(n); 
        }

        /// 
        /// Callback function to invoke *before* rules are applied. 
        /// Calls the VarRemapper to update any Vars in the entire subtree
        /// If the given node has a RelOp it is pushed on the relOp ancestors stack. 
        ///  
        /// 
        internal override void PreProcessSubTree(Node subTree) 
        {
            if (subTree.Op.IsRelOp)
            {
                m_relOpAncestors.Push(subTree); 
            }
 
            if (m_remappedVars.IsEmpty) 
            {
                return; 
            }

            NodeInfo nodeInfo = this.Command.GetNodeInfo(subTree);
 
            //We need to do remapping only if m_remappedVars overlaps with nodeInfo.ExternalReferences
            foreach (Var v in nodeInfo.ExternalReferences) 
            { 
                if (m_remappedVars.IsSet(v))
                { 
                    m_remapper.RemapSubtree(subTree);
                    break;
                }
            } 
        }
 
        ///  
        /// If the given node has a RelOp it is popped from the relOp ancestors stack.
        ///  
        /// 
        internal override void PostProcessSubTree(Node subtree)
        {
            if (subtree.Op.IsRelOp) 
            {
                PlanCompiler.Assert(m_relOpAncestors.Count != 0, "The RelOp ancestors stack is empty when post processing a RelOp subtree"); 
                Node poppedNode = m_relOpAncestors.Pop(); 
                PlanCompiler.Assert(Object.ReferenceEquals(subtree, poppedNode), "The popped ancestor is not equal to the root of the subtree being post processed");
            } 
        }

        /// 
        /// Callback function to invoke *after* rules are applied 
        /// Recomputes the node info, if this node has changed
        /// If the rule is among the rules after which projection pruning may be beneficial, 
        /// m_projectionPrunningRequired is set to true. 
        /// If the rule is among the rules after which reapplying the nullability rules may be beneficial,
        /// m_reapplyNullabilityRules is set to true. 
        /// 
        /// 
        /// the rule that was applied
        internal override void PostProcess(Node n, InternalTrees.Rule rule) 
        {
            if (rule != null) 
            { 
#if DEBUG
                appliedRules.Append(rule.MethodName); 
                appliedRules.AppendLine();
#endif
                if (!this.m_projectionPrunningRequired && TransformationRules.RulesRequiringProjectionPruning.Contains(rule))
                { 
                    this.m_projectionPrunningRequired = true;
                } 
                if (!this.m_reapplyNullabilityRules && TransformationRules.RulesRequiringNullabilityRulesToBeReapplied.Contains(rule)) 
                {
                    this.m_reapplyNullabilityRules = true; 
                }
                Command.RecomputeNodeInfo(n);
            }
        } 

        ///  
        /// Get the hash value for this subtree 
        /// 
        ///  
        /// 
        internal override int GetHashCode(Node node)
        {
            NodeInfo nodeInfo = Command.GetNodeInfo(node); 
            return nodeInfo.HashValue;
        } 
        #endregion 

        #region private methods 
        /// 
        /// Check to see if the current subtree is a scalar-op subtree (ie) does
        /// the subtree only comprise of scalarOps?
        /// Additionally, compute the number of non-leaf nodes (ie) nodes with at least one child 
        /// that are found in the subtree. Note that this count is approximate - it is only
        /// intended to be used as a hint. It is the caller's responsibility to initialize 
        /// nodeCount to a sane value on entry into this function 
        /// And finally, if the varRefMap parameter is non-null, we keep track of
        /// how often a Var is referenced within the subtree 
        ///
        /// The non-leaf-node count and the varRefMap are used by GetVarMap to determine
        /// if expressions can be composed together
        ///  
        /// root of the subtree
        /// Ref counts for each Var encountered in the subtree 
        /// count of non-leaf nodes encountered in the subtree 
        /// true, if this node only contains scalarOps
        private bool IsScalarOpTree(Node node, Dictionary varRefMap, ref int nonLeafNodeCount) 
        {
            if (!node.Op.IsScalarOp)
            {
                return false; 
            }
 
            if (node.HasChild0) 
            {
                nonLeafNodeCount++; 
            }

            if (varRefMap != null && node.Op.OpType == OpType.VarRef)
            { 
                VarRefOp varRefOp = (VarRefOp)node.Op;
                int refCount; 
                if (!varRefMap.TryGetValue(varRefOp.Var, out refCount)) 
                {
                    refCount = 1; 
                }
                else
                {
                    refCount++; 
                }
                varRefMap[varRefOp.Var] = refCount; 
            } 

            foreach (Node chi in node.Children) 
            {
                if (!IsScalarOpTree(chi, varRefMap, ref nonLeafNodeCount))
                {
                    return false; 
                }
            } 
            return true; 
        }
        #endregion 
    }

    /// 
    /// The list of all transformation rules to apply 
    /// 
    internal static class TransformationRules 
    { 
        /// 
        /// A lookup table for built from all rules 
        /// The lookup table is an array indexed by OpType and each entry has a list of rules.
        /// 
        internal static readonly ReadOnlyCollection> AllRulesTable = BuildLookupTableForRules(AllRules);
 
        /// 
        /// A lookup table for built only from ProjectRules 
        /// The lookup table is an array indexed by OpType and each entry has a list of rules. 
        /// 
        internal static readonly ReadOnlyCollection> ProjectRulesTable = BuildLookupTableForRules(ProjectOpRules.Rules); 


        /// 
        /// A lookup table built only from rules that use key info 
        /// The lookup table is an array indexed by OpType and each entry has a list of rules.
        ///  
        internal static readonly ReadOnlyCollection> PostJoinEliminationRulesTable = BuildLookupTableForRules(PostJoinEliminationRules); 

        ///  
        /// A lookup table built only from rules that rely on nullability of vars and other rules
        /// that may be able to perform simplificatios if these have been applied.
        /// The lookup table is an array indexed by OpType and each entry has a list of rules.
        ///  
        internal static readonly ReadOnlyCollection> NullabilityRulesTable = BuildLookupTableForRules(NullabilityRules);
 
        ///  
        /// A look-up table of rules that may cause modifications such that projection pruning may be useful
        /// after they have been applied. 
        /// 
        internal static readonly HashSet RulesRequiringProjectionPruning = InitializeRulesRequiringProjectionPruning();

        ///  
        /// A look-up table of rules that may cause modifications such that reapplying the nullability rules
        /// may be useful after they have been applied. 
        ///  
        internal static readonly HashSet RulesRequiringNullabilityRulesToBeReapplied = InitializeRulesRequiringNullabilityRulesToBeReapplied();
 

        #region private state maintenance
        private static List allRules;
        private static List AllRules 
        {
            get 
            { 
                if (allRules == null)
                { 
                    allRules = new List();
                    allRules.AddRange(ScalarOpRules.Rules);
                    allRules.AddRange(FilterOpRules.Rules);
                    allRules.AddRange(ProjectOpRules.Rules); 
                    allRules.AddRange(ApplyOpRules.Rules);
                    allRules.AddRange(JoinOpRules.Rules); 
                    allRules.AddRange(SingleRowOpRules.Rules); 
                    allRules.AddRange(SetOpRules.Rules);
                    allRules.AddRange(GroupByOpRules.Rules); 
                    allRules.AddRange(SortOpRules.Rules);
                    allRules.AddRange(ConstrainedSortOpRules.Rules);
                    allRules.AddRange(DistinctOpRules.Rules);
                } 
                return allRules;
            } 
        } 

        private static List postJoinEliminationRules; 
        private static List PostJoinEliminationRules
        {
            get
            { 
                if (postJoinEliminationRules == null)
                { 
                    postJoinEliminationRules = new List(); 
                    postJoinEliminationRules.AddRange(ProjectOpRules.Rules); //these don't use key info per-se, but can help after the distinct op rules.
                    postJoinEliminationRules.AddRange(DistinctOpRules.Rules); 
                    postJoinEliminationRules.AddRange(FilterOpRules.Rules);
                    postJoinEliminationRules.AddRange(JoinOpRules.Rules);
                    postJoinEliminationRules.AddRange(NullabilityRules);
                } 
                return postJoinEliminationRules;
            } 
        } 

        private static List nullabilityRules; 
        private static List NullabilityRules
        {
            get
            { 
                if (nullabilityRules == null)
                { 
                    nullabilityRules = new List(); 
                    nullabilityRules.Add(ScalarOpRules.Rule_IsNullOverVarRef);
                    nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred1); 
                    nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred2);
                    nullabilityRules.Add(ScalarOpRules.Rule_SimplifyCase);
                }
                return nullabilityRules; 
            }
        } 
 
        private static ReadOnlyCollection> BuildLookupTableForRules(IEnumerable rules)
        { 
            ReadOnlyCollection NoRules = new ReadOnlyCollection(new InternalTrees.Rule[0]);

            List[] lookupTable = new List[(int)OpType.MaxMarker];
 
            foreach (InternalTrees.Rule rule in rules)
            { 
                List opRules = lookupTable[(int)rule.RuleOpType]; 
                if (opRules == null)
                { 
                    opRules = new List();
                    lookupTable[(int)rule.RuleOpType] = opRules;
                }
                opRules.Add(rule); 
            }
 
            ReadOnlyCollection[] rulesPerType = new ReadOnlyCollection[lookupTable.Length]; 
            for (int i = 0; i < lookupTable.Length; ++i)
            { 
                if (null != lookupTable[i])
                {
                    rulesPerType[i] = new ReadOnlyCollection(lookupTable[i].ToArray());
                } 
                else
                { 
                    rulesPerType[i] = NoRules; 
                }
            } 
            return new ReadOnlyCollection>(rulesPerType);
        }

        private static HashSet InitializeRulesRequiringProjectionPruning() 
        {
            HashSet rulesRequiringProjectionPruning = new HashSet(); 
 
            rulesRequiringProjectionPruning.Add(ApplyOpRules.Rule_OuterApplyOverProject);
 
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject1);
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject2);
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject1);
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject2); 
            rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_OuterJoinOverProject2);
 
            rulesRequiringProjectionPruning.Add(ProjectOpRules.Rule_ProjectWithNoLocalDefs); 

            rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterOverProject); 
            rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterWithConstantPredicate);

            rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOverProject);
            rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions); 

            return rulesRequiringProjectionPruning; 
        } 

        private static HashSet InitializeRulesRequiringNullabilityRulesToBeReapplied() 
        {
            HashSet rulesRequiringNullabilityRulesToBeReapplied = new HashSet();

            rulesRequiringNullabilityRulesToBeReapplied.Add(FilterOpRules.Rule_FilterOverLeftOuterJoin); 

            return rulesRequiringNullabilityRulesToBeReapplied; 
        } 

        #endregion 


        /// 
        /// Apply the rules that belong to the specified group to the given query tree. 
        /// 
        ///  
        ///  
        internal static bool Process(PlanCompiler compilerState, TransformationRulesGroup rulesGroup)
        { 
            ReadOnlyCollection> rulesTable = null;
            switch (rulesGroup)
            {
                case TransformationRulesGroup.All: 
                    rulesTable = AllRulesTable;
                    break; 
                case TransformationRulesGroup.PostJoinElimination: 
                    rulesTable = PostJoinEliminationRulesTable;
                    break; 
                case TransformationRulesGroup.Project:
                    rulesTable = ProjectRulesTable;
                    break;
            } 

            // If any rule has been applied after which reapplying nullability rules may be useful, 
            // reapply nullability rules. 
            bool projectionPrunningRequired;
            if (Process(compilerState, rulesTable, out projectionPrunningRequired)) 
            {
                bool projectionPrunningRequired2;
                Process(compilerState, NullabilityRulesTable, out projectionPrunningRequired2);
                projectionPrunningRequired = projectionPrunningRequired || projectionPrunningRequired2; 
            }
            return projectionPrunningRequired; 
        } 

        ///  
        /// Apply the rules that belong to the specified rules table to the given query tree.
        /// 
        /// 
        ///  
        /// is projection pruning  required after the rule application
        /// Whether any rule has been applied after which reapplying nullability rules may be useful 
        private static bool Process(PlanCompiler compilerState, ReadOnlyCollection> rulesTable, out bool projectionPruningRequired) 
        {
            RuleProcessor ruleProcessor = new RuleProcessor(); 
            TransformationRulesContext context = new TransformationRulesContext(compilerState);
            compilerState.Command.Root = ruleProcessor.ApplyRulesToSubtree(context, rulesTable, compilerState.Command.Root);
            projectionPruningRequired = context.ProjectionPrunningRequired;
            return context.ReapplyNullabilityRules; 
        }
    } 
 
    /// 
    /// Available groups of rules, not necessarily mutually exclusive 
    /// 
    internal enum TransformationRulesGroup
    {
        All, 
        Project,
        PostJoinElimination 
    } 

    #region ScalarOpRules 
    /// 
    /// Transformation rules for ScalarOps
    /// 
    internal static class ScalarOpRules 
    {
        #region CaseOp Rules 
        internal static readonly SimpleRule Rule_SimplifyCase = new SimpleRule(OpType.Case, ProcessSimplifyCase); 
        internal static readonly SimpleRule Rule_FlattenCase = new SimpleRule(OpType.Case, ProcessFlattenCase);
        ///  
        /// We perform the following simple transformation for CaseOps. If every single
        /// then/else expression in the CaseOp is equivalent, then we can simply replace
        /// the Op with the first then/expression. Specifically,
        /// case when w1 then t1 when w2 then t2 ... when wn then tn else e end 
        ///   => t1
        /// assuming that t1 is equivalent to t2 is equivalent to ... to e 
        ///  
        /// Rule Processing context
        /// The current subtree for the CaseOp 
        /// the (possibly) modified subtree
        /// true, if we performed any transformations
        static bool ProcessSimplifyCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
        { 
            CaseOp caseOp = (CaseOp)caseOpNode.Op;
            newNode = caseOpNode; 
 
            //
            // Can I collapse the entire case-expression into a single expression - yes, 
            // if all the then/else clauses are the same expression
            //
            if (ProcessSimplifyCase_Collapse(caseOp, caseOpNode, out newNode))
            { 
                return true;
            } 
 
            //
            // Can I remove any unnecessary when-then pairs ? 
            //
            if (ProcessSimplifyCase_EliminateWhenClauses(context, caseOp, caseOpNode, out newNode))
            {
                return true; 
            }
 
            // Nothing else I can think of 
            return false;
        } 

        /// 
        /// Try and collapse the case expression into a single expression.
        /// If every single then/else expression in the CaseOp is equivalent, then we can 
        /// simply replace the CaseOp with the first then/expression. Specifically,
        /// case when w1 then t1 when w2 then t2 ... when wn then tn else e end 
        ///   => t1 
        ///  if t1 is equivalent to t2 is equivalent to ... to e
        ///  
        /// the current caseOp
        /// current subtree
        /// new subtree
        /// true, if we performed a transformation 
        private static bool ProcessSimplifyCase_Collapse(CaseOp caseOp, Node caseOpNode, out Node newNode)
        { 
            newNode = caseOpNode; 
            Node firstThenNode = caseOpNode.Child1;
            Node elseNode = caseOpNode.Children[caseOpNode.Children.Count - 1]; 
            if (!firstThenNode.IsEquivalent(elseNode))
            {
                return false;
            } 
            for (int i = 3; i < caseOpNode.Children.Count - 1; i += 2)
            { 
                if (!caseOpNode.Children[i].IsEquivalent(firstThenNode)) 
                {
                    return false; 
                }
            }

            // All nodes are equivalent - simply return the first then node 
            newNode = firstThenNode;
            return true; 
        } 

        ///  
        /// Try and remove spurious branches from the case expression.
        /// If any of the WHEN clauses is the 'FALSE' expression, simply remove that
        /// branch (when-then pair) from the case expression.
        /// If any of the WHEN clauses is the 'TRUE' expression, then all branches to the 
        /// right of it are irrelevant - eliminate them. Eliminate this branch as well,
        /// and make the THEN expression of this branch the ELSE expression for the entire 
        /// Case expression. If the WHEN expression represents the first branch, then 
        /// replace the entire case expression by the corresponding THEN expression
        ///  
        /// rule processing context
        /// current caseOp
        /// Current subtree
        /// the new subtree 
        /// true, if there was a transformation
        private static bool ProcessSimplifyCase_EliminateWhenClauses(RuleProcessingContext context, CaseOp caseOp, Node caseOpNode, out Node newNode) 
        { 
            List newNodeArgs = null;
            newNode = caseOpNode; 

            for (int i = 0; i < caseOpNode.Children.Count; )
            {
                // Special handling for the else clause 
                if (i == caseOpNode.Children.Count - 1)
                { 
                    // If the else clause is a SoftCast then we do not attempt to simplify 
                    // the case operation, since this may change the result type.
                    // This really belongs in more general SoftCastOp logic in the CTreeGenerator 
                    // that converts SoftCasts that could affect the result type of the query into
                    // a real cast or a trivial case statement, to preserve the result type.
                    // This is tracked by SQL PT Work Item #300003327.
                    if (OpType.SoftCast == caseOpNode.Children[i].Op.OpType) 
                    {
                        return false; 
                    } 

                    if (newNodeArgs != null) 
                    {
                        newNodeArgs.Add(caseOpNode.Children[i]);
                    }
                    break; 
                }
 
                // If the current then clause is a SoftCast then we do not attempt to simplify 
                // the case operation, since this may change the result type.
                // Again, this really belongs in the CTreeGenerator as per SQL PT Work Item #300003327. 
                if (OpType.SoftCast == caseOpNode.Children[i + 1].Op.OpType)
                {
                    return false;
                } 

                // Check to see if the when clause is a ConstantPredicate 
                if (caseOpNode.Children[i].Op.OpType != OpType.ConstantPredicate) 
                {
                    if (newNodeArgs != null) 
                    {
                        newNodeArgs.Add(caseOpNode.Children[i]);
                        newNodeArgs.Add(caseOpNode.Children[i + 1]);
                    } 
                    i += 2;
                    continue; 
                } 

                // Found a when-clause which is a constant predicate 
                ConstantPredicateOp constPred = (ConstantPredicateOp)caseOpNode.Children[i].Op;
                // Create the newArgs list, if we haven't done so already
                if (newNodeArgs == null)
                { 
                    newNodeArgs = new List();
                    for (int j = 0; j < i; j++) 
                    { 
                        newNodeArgs.Add(caseOpNode.Children[j]);
                    } 
                }

                // If the when-clause is the "true" predicate, then we simply ignore all
                // the succeeding arguments. We make the "then" clause of this when-clause 
                // as the "else-clause" of the resulting caseOp
                if (constPred.IsTrue) 
                { 
                    newNodeArgs.Add(caseOpNode.Children[i + 1]);
                    break; 
                }
                else
                {
                    // Otherwise, we simply skip the when-then pair 
                    PlanCompiler.Assert(constPred.IsFalse, "constant predicate must be either true or false");
                    i += 2; 
                    continue; 
                }
            } 

            // Did we see any changes? Simply return
            if (newNodeArgs == null)
            { 
                return false;
            } 
 
            // Otherwise, we did do some processing
            PlanCompiler.Assert(newNodeArgs.Count > 0, "new args list must not be empty"); 
            // Is there only one expression in the args list - simply return that expression
            if (newNodeArgs.Count == 1)
            {
                newNode = newNodeArgs[0]; 
            }
            else 
            { 
                newNode = context.Command.CreateNode(caseOp, newNodeArgs);
            } 

            return true;
        }
 
        /// 
        /// If the else clause of the CaseOp is another CaseOp, when two can be collapsed into one. 
        /// In particular, 
        ///
        /// CASE 
        ///     WHEN W1 THEN T1
        ///     WHEN W2 THEN T2 ...
        ///     ELSE (CASE
        ///             WHEN WN1 THEN TN1, � 
        ///             ELSE E)
        /// 
        /// Is transformed into 
        ///
        /// CASE 
        ///     WHEN W1 THEN T1
        ///     WHEN W2 THEN T2 ...
        ///     WHEN WN1  THEN TN1 ...
        ///     ELSE E 
        /// 
        /// the current caseOp 
        /// current subtree 
        /// new subtree
        /// true, if we performed a transformation 
        static bool ProcessFlattenCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
        {
            newNode = caseOpNode;
            Node elseChild = caseOpNode.Children[caseOpNode.Children.Count - 1]; 
            if (elseChild.Op.OpType != OpType.Case)
            { 
                return false; 
            }
 
            //
            // Flatten the case statements.
            // The else child is removed from the outer CaseOp op
            // and the else child's children are reparented to the outer CaseOp 
            // Node info recomputation does not need to happen, the outer CaseOp
            // node still has the same descendants. 
            // 
            caseOpNode.Children.RemoveAt(caseOpNode.Children.Count - 1);
            caseOpNode.Children.AddRange(elseChild.Children); 

            return true;
        }
 
        #endregion
 
        #region EqualsOverConstant Rules 
        internal static readonly PatternMatchRule Rule_EqualsOverConstant =
            new PatternMatchRule(new Node(ComparisonOp.PatternEq, 
                                          new Node(InternalConstantOp.Pattern),
                                          new Node(InternalConstantOp.Pattern)),
                                 ProcessComparisonsOverConstant);
        ///  
        /// Convert an Equals(X, Y) to a "true" predicate if X=Y, or a "false" predicate if X!=Y
        /// Convert a NotEquals(X,Y) in the reverse fashion 
        ///  
        /// Rule processing context
        /// current node 
        /// possibly modified subtree
        /// true, if transformation was successful
        static bool ProcessComparisonsOverConstant(RuleProcessingContext context, Node node, out Node newNode)
        { 
            newNode = node;
            PlanCompiler.Assert(node.Op.OpType == OpType.EQ || node.Op.OpType == OpType.NE, "unexpected comparison op type?"); 
 
            bool? comparisonStatus = node.Child0.Op.IsEquivalent(node.Child1.Op);
            // Don't mess with nulls or with non-internal constants 
            if (comparisonStatus == null)
            {
                return false;
            } 
            bool result = (node.Op.OpType == OpType.EQ) ? (bool)comparisonStatus : !((bool)comparisonStatus);
            ConstantPredicateOp newOp = context.Command.CreateConstantPredicateOp(result); 
            newNode = context.Command.CreateNode(newOp); 
            return true;
        } 
        #endregion

        #region LikeOp Rules
        private static bool? MatchesPattern(string str, string pattern) 
        {
            // What we're trying to see is if the pattern is something that ends with a '%' 
            // And if the "str" is something that matches everything before that 

            // Make sure that the terminal character of the pattern is a '%' character. Also 
            // ensure that this character does not occur anywhere else. And finally, ensure
            // that the pattern is atmost one character longer than the string itself
            int wildCardIndex = pattern.IndexOf('%');
            if ((wildCardIndex == -1) || 
                (wildCardIndex != pattern.Length - 1) ||
                (pattern.Length > str.Length + 1)) 
            { 
                return null;
            } 

            bool match = true;

            int i = 0; 
            for (i = 0; i < str.Length && i < pattern.Length - 1; i++)
            { 
                if (pattern[i] != str[i]) 
                {
                    match = false; 
                    break;
                }
            }
 
            return match;
        } 
 
        internal static readonly PatternMatchRule Rule_LikeOverConstants =
            new PatternMatchRule(new Node(LikeOp.Pattern, 
                                          new Node(InternalConstantOp.Pattern),
                                          new Node(InternalConstantOp.Pattern),
                                          new Node(NullOp.Pattern)),
                                 ProcessLikeOverConstant); 
        static bool ProcessLikeOverConstant(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n; 
            InternalConstantOp patternOp = (InternalConstantOp)n.Child1.Op;
            InternalConstantOp strOp = (InternalConstantOp)n.Child0.Op; 

            string str = (string)strOp.Value;
            string pattern = (string)patternOp.Value;
 
            bool? match = MatchesPattern((string)strOp.Value, (string)patternOp.Value);
            if (match == null) 
            { 
                return false;
            } 

            ConstantPredicateOp constOp = context.Command.CreateConstantPredicateOp((bool)match);
            newNode = context.Command.CreateNode(constOp);
            return true; 
        }
 
        #endregion 

        #region LogicalOp (and,or,not) Rules 
        internal static readonly PatternMatchRule Rule_AndOverConstantPred1 =
            new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
                                          new Node(LeafOp.Pattern),
                                          new Node(ConstantPredicateOp.Pattern)), 
                                 ProcessAndOverConstantPredicate1);
        internal static readonly PatternMatchRule Rule_AndOverConstantPred2 = 
            new PatternMatchRule(new Node(ConditionalOp.PatternAnd, 
                                          new Node(ConstantPredicateOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessAndOverConstantPredicate2);
        internal static readonly PatternMatchRule Rule_OrOverConstantPred1 =
            new PatternMatchRule(new Node(ConditionalOp.PatternOr,
                                          new Node(LeafOp.Pattern), 
                                          new Node(ConstantPredicateOp.Pattern)),
                                 ProcessOrOverConstantPredicate1); 
        internal static readonly PatternMatchRule Rule_OrOverConstantPred2 = 
            new PatternMatchRule(new Node(ConditionalOp.PatternOr,
                                          new Node(ConstantPredicateOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessOrOverConstantPredicate2);
        internal static readonly PatternMatchRule Rule_NotOverConstantPred =
            new PatternMatchRule(new Node(ConditionalOp.PatternNot, 
                                          new Node(ConstantPredicateOp.Pattern)),
                                 ProcessNotOverConstantPredicate); 
        ///  
        /// Transform
        ///   AND(x, true) => x; 
        ///   AND(true, x) => x
        ///   AND(x, false) => false
        ///   AND(false, x) => false
        /// 
        /// 
        /// Rule Processing context 
        /// Current LogOp (And, Or, Not) node 
        /// constant predicate node
        /// The other child of the LogOp (possibly null) 
        /// new subtree
        /// transformation status
        static bool ProcessLogOpOverConstant(RuleProcessingContext context, Node node,
            Node constantPredicateNode, Node otherNode, 
            out Node newNode)
        { 
            PlanCompiler.Assert(constantPredicateNode != null, "null constantPredicateOp?"); 
            ConstantPredicateOp pred = (ConstantPredicateOp)constantPredicateNode.Op;
 
            switch (node.Op.OpType)
            {
                case OpType.And:
                    newNode = pred.IsTrue ? otherNode : constantPredicateNode; 
                    break;
                case OpType.Or: 
                    newNode = pred.IsTrue ? constantPredicateNode : otherNode; 
                    break;
                case OpType.Not: 
                    PlanCompiler.Assert(otherNode == null, "Not Op with more than 1 child. Gasp!");
                    newNode = context.Command.CreateNode(context.Command.CreateConstantPredicateOp(!pred.Value));
                    break;
                default: 
                    PlanCompiler.Assert(false, "Unexpected OpType - " + node.Op.OpType);
                    newNode = null; 
                    break; 
            }
            return true; 
        }

        static bool ProcessAndOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
        { 
            return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
        } 
        static bool ProcessAndOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode) 
        {
            return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode); 
        }
        static bool ProcessOrOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
        {
            return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode); 
        }
        static bool ProcessOrOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode) 
        { 
            return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
        } 
        static bool ProcessNotOverConstantPredicate(RuleProcessingContext context, Node node, out Node newNode)
        {
            return ProcessLogOpOverConstant(context, node, node.Child0, null, out newNode);
        } 
        #endregion
 
        #region IsNull Rules 
        internal static readonly PatternMatchRule Rule_IsNullOverConstant =
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull, 
                                          new Node(InternalConstantOp.Pattern)),
                                 ProcessIsNullOverConstant);
        internal static readonly PatternMatchRule Rule_IsNullOverNullSentinel =
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull, 
                                          new Node(NullSentinelOp.Pattern)),
                                 ProcessIsNullOverConstant); 
        ///  
        /// Convert a
        ///    IsNull(constant) 
        /// to just the
        ///    False predicate
        /// 
        ///  
        /// 
        /// new subtree 
        ///  
        static bool ProcessIsNullOverConstant(RuleProcessingContext context, Node isNullNode, out Node newNode)
        { 
            newNode = context.Command.CreateNode(context.Command.CreateFalseOp());
            return true;
        }
 
        internal static readonly PatternMatchRule Rule_IsNullOverNull =
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull, 
                                          new Node(NullOp.Pattern)), 
                         ProcessIsNullOverNull);
        ///  
        /// Convert an IsNull(null) to just the 'true' predicate
        /// 
        /// 
        ///  
        /// new subtree
        ///  
        static bool ProcessIsNullOverNull(RuleProcessingContext context, Node isNullNode, out Node newNode) 
        {
            newNode = context.Command.CreateNode(context.Command.CreateTrueOp()); 
            return true;
        }
        #endregion
 
        #region CastOp(NullOp) Rule
        internal static readonly PatternMatchRule Rule_NullCast = new PatternMatchRule( 
                                                            new Node(CastOp.Pattern, 
                                                                    new Node(NullOp.Pattern)),
                                                            ProcessNullCast); 

        /// 
        /// eliminates nested null casts into a single cast of the outermost cast type.
        /// basically the transformation applied is: cast(null[x] as T) => null[t] 
        /// 
        ///  
        ///  
        /// modified subtree
        ///  
        static bool ProcessNullCast(RuleProcessingContext context, Node castNullOp, out Node newNode)
        {
            newNode = context.Command.CreateNode(context.Command.CreateNullOp(castNullOp.Op.Type));
            return true; 
        }
        #endregion 
 
        #region IsNull over VarRef
        internal static readonly PatternMatchRule Rule_IsNullOverVarRef = 
            new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
                                          new Node(VarRefOp.Pattern)),
                                 ProcessIsNullOverVarRef);
        ///  
        /// Convert a
        ///    IsNull(VarRef(v)) 
        /// to just the 
        ///    False predicate
        /// 
        /// if v is guaranteed to be non nullable.
        /// 
        /// 
        ///  
        /// new subtree
        ///  
        static bool ProcessIsNullOverVarRef(RuleProcessingContext context, Node isNullNode, out Node newNode) 
        {
            Command command = context.Command; 
            TransformationRulesContext trc = (TransformationRulesContext)context;

            Var v = ((VarRefOp)isNullNode.Child0.Op).Var;
 
            if (trc.IsNonNullable(v))
            { 
 
                newNode = command.CreateNode(context.Command.CreateFalseOp());
                return true; 
            }
            else
            {
                newNode = isNullNode; 
                return false;
            } 
        } 
        #endregion
 
        #region All ScalarOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
            Rule_SimplifyCase,
            Rule_FlattenCase, 
            Rule_LikeOverConstants,
            Rule_EqualsOverConstant, 
            Rule_AndOverConstantPred1, 
            Rule_AndOverConstantPred2,
            Rule_OrOverConstantPred1, 
            Rule_OrOverConstantPred2,
            Rule_NotOverConstantPred,
            Rule_IsNullOverConstant,
            Rule_IsNullOverNullSentinel, 
            Rule_IsNullOverNull,
            Rule_NullCast, 
            Rule_IsNullOverVarRef, 
        };
        #endregion 
    }
    #endregion

    #region Filter Rules 
    /// 
    /// Transformation rules for FilterOps 
    ///  
    internal static class FilterOpRules
    { 
        #region Helpers
        /// 
        /// Split up a predicate into 2 parts - the pushdown and the non-pushdown predicate.
        /// 
        /// If the filter node has no external references *and* the "columns" parameter is null,
        /// then the entire predicate can be pushed down 
        /// 
        /// We then compute the set of valid column references - if the "columns" parameter
        /// is non-null, this set is used. Otherwise, we get the definitions of the 
        /// input relop node of the filterOp, and use that.
        ///
        /// We use this list of valid column references to identify which parts of the filter
        /// predicate can be pushed down - only those parts of the predicate that do not 
        /// reference anything beyond these columns are considered for pushdown. The rest are
        /// stuffed into the nonPushdownPredicate output parameter 
        /// 
        /// 
        /// Command object 
        /// the FilterOp subtree
        /// (Optional) List of columns to consider for "pushdown"
        /// (output) Part of the predicate that cannot be pushed down
        /// part of the predicate that can be pushed down 
        private static Node GetPushdownPredicate(Command command, Node filterNode, VarVec columns, out Node nonPushdownPredicateNode)
        { 
            Node pushdownPredicateNode = filterNode.Child1; 
            nonPushdownPredicateNode = null;
            ExtendedNodeInfo filterNodeInfo = command.GetExtendedNodeInfo(filterNode); 
            if (columns == null && filterNodeInfo.ExternalReferences.IsEmpty)
            {
                return pushdownPredicateNode;
            } 

            if (columns == null) 
            { 
                ExtendedNodeInfo inputNodeInfo = command.GetExtendedNodeInfo(filterNode.Child0);
                columns = inputNodeInfo.Definitions; 
            }

            Predicate predicate = new Predicate(command, pushdownPredicateNode);
            Predicate nonPushdownPredicate; 
            predicate = predicate.GetSingleTablePredicates(columns, out nonPushdownPredicate);
            pushdownPredicateNode = predicate.BuildAndTree(); 
            nonPushdownPredicateNode = nonPushdownPredicate.BuildAndTree(); 
            return pushdownPredicateNode;
        } 

        #endregion

        #region FilterOverFilter 
        internal static readonly PatternMatchRule Rule_FilterOverFilter =
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                          new Node(FilterOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessFilterOverFilter);
        /// 
        /// Convert Filter(Filter(X, p1), p2) => Filter(X, (p1 and p2)) 
        /// 
        /// rule processing context 
        /// FilterOp node 
        /// modified subtree
        /// transformed subtree 
        static bool ProcessFilterOverFilter(RuleProcessingContext context, Node filterNode, out Node newNode)
        {
            Node newAndNode = context.Command.CreateNode(
                context.Command.CreateConditionalOp(OpType.And), 
                filterNode.Child0.Child1, filterNode.Child1);
 
            newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), filterNode.Child0.Child0, newAndNode); 
            return true;
        } 
        #endregion

        #region FilterOverProject
        internal static readonly PatternMatchRule Rule_FilterOverProject = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessFilterOverProject);
        /// 
        /// Convert Filter(Project(X, ...), p) => Project(Filter(X, p'), ...)
        ///  
        /// Rule processing context
        /// FilterOp subtree 
        /// modified subtree 
        /// transformed subtree
        static bool ProcessFilterOverProject(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode;
            Node predicateNode = filterNode.Child1;
 
            //
            // If the filter is a constant predicate, then don't push the filter below the 
            // project 
            //
            if (predicateNode.Op.OpType == OpType.ConstantPredicate) 
            {
                // There's a different rule to process this case. Simply return
                return false;
            } 

            TransformationRulesContext trc = (TransformationRulesContext)context; 
            // 
            // check to see that this is a simple predicate
            // 
            Dictionary varRefMap = new Dictionary();
            if (!trc.IsScalarOpTree(predicateNode, varRefMap))
            {
                return false; 
            }
            // 
            // check to see if all expressions in the project can be inlined 
            //
            Node projectNode = filterNode.Child0; 
            Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
            if (varMap == null)
            {
                return false; 
            }
 
            // 
            // Try to remap the predicate in terms of the definitions of the Vars
            // 
            Node remappedPredicateNode = trc.ReMap(predicateNode, varMap);

            //
            // Now push the filter below the project 
            //
            Node newFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), projectNode.Child0, remappedPredicateNode); 
            Node newProjectNode = trc.Command.CreateNode(projectNode.Op, newFilterNode, projectNode.Child1); 

            newNode = newProjectNode; 
            return true;
        }
        #endregion
 
        #region FilterOverSetOp
        internal static readonly PatternMatchRule Rule_FilterOverUnionAll = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                          new Node(UnionAllOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)),
                                 ProcessFilterOverSetOp);
        internal static readonly PatternMatchRule Rule_FilterOverIntersect = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                          new Node(IntersectOp.Pattern, 
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessFilterOverSetOp);
        internal static readonly PatternMatchRule Rule_FilterOverExcept =
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                          new Node(ExceptOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessFilterOverSetOp);
        ///  
        /// Transform Filter(UnionAll(X1, X2), p) => UnionAll(Filter(X1, p1), Filter(X, p2))
        ///           Filter(Intersect(X1, X2), p) => Intersect(Filter(X1, p1), Filter(X2, p2))
        ///           Filter(Except(X1, X2), p) => Except(Filter(X1, p1), X2)
        /// where p1 and p2 are the "mapped" versions of the predicate "p" for each branch 
        /// 
        /// Rule processing context 
        /// FilterOp subtree 
        /// modified subtree
        /// true, if successful transformation 
        static bool ProcessFilterOverSetOp(RuleProcessingContext context, Node filterNode, out Node newNode)
        {
            newNode = filterNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 

            // 
            // Identify parts of the filter predicate that can be pushed down, and parts that 
            // cannot be. If nothing can be pushed down, then return
            // 
            Node nonPushdownPredicate;
            Node pushdownPredicate = GetPushdownPredicate(trc.Command, filterNode, null, out nonPushdownPredicate);
            if (pushdownPredicate == null)
            { 
                return false;
            } 
            // Handle only simple predicates 
            if (!trc.IsScalarOpTree(pushdownPredicate))
            { 
                return false;
            }

            // 
            // Now push the predicate (the part that can be pushed down) into each of the
            // branches (as appropriate) 
            // 
            Node setOpNode = filterNode.Child0;
            SetOp setOp = (SetOp)setOpNode.Op; 
            List newSetOpChildren = new List();
            int branchId = 0;
            foreach (VarMap varMap in setOp.VarMap)
            { 
                // For exceptOp, the filter should only be pushed below the zeroth child
                if (setOp.OpType == OpType.Except && branchId == 1) 
                { 
                    newSetOpChildren.Add(setOpNode.Child1);
                    break; 
                }

                Dictionary remapMap = new Dictionary();
                foreach (KeyValuePair kv in varMap) 
                {
                    Node varRefNode = trc.Command.CreateNode(trc.Command.CreateVarRefOp(kv.Value)); 
                    remapMap.Add(kv.Key, varRefNode); 
                }
 
                //
                // Now fix up the predicate.
                // Make a copy of the predicate first - except if we're dealing with the last
                // branch, in which case, we can simply reuse the predicate 
                //
                Node predicateNode = pushdownPredicate; 
                if (branchId == 0 && filterNode.Op.OpType != OpType.Except) 
                {
                    predicateNode = trc.Copy(predicateNode); 
                }
                Node newPredicateNode = trc.ReMap(predicateNode, remapMap);
                trc.Command.RecomputeNodeInfo(newPredicateNode);
 
                // create a new filter node below the setOp child
                Node newFilterNode = trc.Command.CreateNode( 
                    trc.Command.CreateFilterOp(), 
                    setOpNode.Children[branchId],
                    newPredicateNode); 
                newSetOpChildren.Add(newFilterNode);

                branchId++;
            } 
            Node newSetOpNode = trc.Command.CreateNode(setOpNode.Op, newSetOpChildren);
 
            // 
            // We've now pushed down the relevant parts of the filter below the SetOps
            // We may still however some predicates left over - create a new filter node 
            // to account for that
            //
            if (nonPushdownPredicate != null)
            { 
                newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newSetOpNode, nonPushdownPredicate);
            } 
            else 
            {
                newNode = newSetOpNode; 
            }
            return true;
        }
        #endregion 

        #region FilterOverDistinct 
        internal static readonly PatternMatchRule Rule_FilterOverDistinct = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(DistinctOp.Pattern, 
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverDistinct);
        ///  
        /// Transforms Filter(Distinct(x), p) => Filter(Distinct(Filter(X, p1), p2)
        ///    where p2 is the part of the filter that can be pushed down, while p1 represents 
        ///    any external references 
        /// 
        /// Rule processing context 
        /// FilterOp subtree
        /// modified subtree
        /// Transformation status
        static bool ProcessFilterOverDistinct(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode; 
            // 
            // Split up the filter predicate into two parts - the part that can be pushed down
            // and the part that can't. If there is no part that can be pushed down, simply return 
            //
            Node nonPushdownPredicate;
            Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, null, out nonPushdownPredicate);
            if (pushdownPredicate == null) 
            {
                return false; 
            } 

            // 
            // Create a new filter node below the current distinct node for the predicate
            // that can be pushed down - create a new distinct node as well
            //
            Node distinctNode = filterNode.Child0; 
            Node pushdownFilterNode = context.Command.CreateNode(context.Command.CreateFilterOp(), distinctNode.Child0, pushdownPredicate);
            Node newDistinctNode = context.Command.CreateNode(distinctNode.Op, pushdownFilterNode); 
 
            //
            // If we have a predicate part that cannot be pushed down, build up a new 
            // filter node above the new Distinct op that we just created
            //
            if (nonPushdownPredicate != null)
            { 
                newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), newDistinctNode, nonPushdownPredicate);
            } 
            else 
            {
                newNode = newDistinctNode; 
            }
            return true;
        }
        #endregion 

        #region FilterOverGroupBy 
        internal static readonly PatternMatchRule Rule_FilterOverGroupBy = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(GroupByOp.Pattern, 
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)), 
                         ProcessFilterOverGroupBy);
        ///  
        /// Transforms Filter(GroupBy(X, k1.., a1...), p) => 
        ///            Filter(GroupBy(Filter(X, p1'), k1..., a1...), p2)
        ///   p1 and p2 represent the parts of p that can and cannot be pushed down 
        ///    respectively - specifically, p1 must only reference the key columns from
        ///    the GroupByOp.
        ///   "p1'" is the mapped version of "p1",
        ///  
        /// Rule processing context
        /// Current FilterOp subtree 
        /// modified subtree 
        /// Transformation status
        static bool ProcessFilterOverGroupBy(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode;
            Node groupByNode = filterNode.Child0;
            GroupByOp groupByOp = (GroupByOp)groupByNode.Op; 
            TransformationRulesContext trc = (TransformationRulesContext)context;
 
            // Check to see that we have a simple predicate 
            Dictionary varRefMap = new Dictionary();
            if (!trc.IsScalarOpTree(filterNode.Child1, varRefMap)) 
            {
                return false;
            }
 
            //
            // Split up the predicate into two parts - the part that can be pushed down below 
            // the groupByOp (specifically, the part that only refers to keys of the groupByOp), 
            // and the part that cannot be pushed below
            // If nothing can be pushed below, quit now 
            //
            Node nonPushdownPredicate;
            Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, groupByOp.Keys, out nonPushdownPredicate);
            if (pushdownPredicate == null) 
            {
                return false; 
            } 

            // 
            // We need to push the filter down; but we need to remap the predicate, so
            // that any references to variables defined locally by the groupBy are fixed up
            // Make sure that the predicate is not too complex to remap
            // 
            Dictionary varMap = trc.GetVarMap(groupByNode.Child1, varRefMap);
            if (varMap == null) 
            { 
                return false; // complex expressions
            } 
            Node remappedPushdownPredicate = trc.ReMap(pushdownPredicate, varMap);

            //
            // Push the filter below the groupBy now 
            //
            Node subFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), groupByNode.Child0, remappedPushdownPredicate); 
            Node newGroupByNode = trc.Command.CreateNode(groupByNode.Op, subFilterNode, groupByNode.Child1, groupByNode.Child2); 

            // 
            // If there was any part of the original predicate that could not be pushed down,
            // create a new filterOp node above the new groupBy node to represent that
            // predicate
            // 
            if (nonPushdownPredicate == null)
            { 
                newNode = newGroupByNode; 
            }
            else 
            {
                newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newGroupByNode, nonPushdownPredicate);
            }
            return true; 
        }
        #endregion 
 
        #region FilterOverJoin
        internal static readonly PatternMatchRule Rule_FilterOverCrossJoin = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(CrossJoinOp.Pattern,
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)), 
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverJoin); 
        internal static readonly PatternMatchRule Rule_FilterOverInnerJoin = 
            new PatternMatchRule(new Node(FilterOp.Pattern,
                                  new Node(InnerJoinOp.Pattern, 
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)), 
                         ProcessFilterOverJoin);
        internal static readonly PatternMatchRule Rule_FilterOverLeftOuterJoin = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                  new Node(LeftOuterJoinOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(LeafOp.Pattern),
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverJoin); 
        /// 
        /// Transform Filter() 
        ///  
        /// Rule Processing context
        /// Current FilterOp subtree 
        /// Modified subtree
        /// Transformation status
        static bool ProcessFilterOverJoin(RuleProcessingContext context, Node filterNode, out Node newNode)
        { 
            newNode = filterNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 
 
            //
            // Have we shut off filter pushdown for this node? Return 
            //
            if (trc.IsFilterPushdownSuppressed(filterNode))
            {
                return false; 
            }
 
            Node joinNode = filterNode.Child0; 
            Op joinOp = joinNode.Op;
            Node leftInputNode = joinNode.Child0; 
            Node rightInputNode = joinNode.Child1;
            Command command = trc.Command;
            bool needsTransformation = false;
 
            //
            // If we're dealing with an outer-join, first check to see if the current 
            // predicate preserves nulls for the right table. 
            // If it doesn't then we can convert the outer join into an inner join,
            // and then continue with the rest of our processing here 
            //
            ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(rightInputNode);
            Predicate predicate = new Predicate(command, filterNode.Child1);
            if (joinOp.OpType == OpType.LeftOuterJoin) 
            {
                if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true)) 
                { 
                    joinOp = command.CreateInnerJoinOp();
                    needsTransformation = true; 
                }
            }
            ExtendedNodeInfo leftTableInfo = command.GetExtendedNodeInfo(leftInputNode);
 
            //
            // Check to see if the predicate contains any "single-table-filters". In those 
            // cases, we could simply push that filter down to the child. 
            // We can do this for inner joins and cross joins - for both inputs.
            // For left-outer joins, however, we can only do this for the left-side input 
            // Further note that we only want to do the pushdown if it will help us - if
            // the join input is a ScanTable (or some other cases), then it doesn't help us.
            //
            Node leftSingleTablePredicateNode = null; 
            if (leftInputNode.Op.OpType != OpType.ScanTable)
            { 
                Predicate leftSingleTablePredicates = predicate.GetSingleTablePredicates(leftTableInfo.Definitions, out predicate); 
                leftSingleTablePredicateNode = leftSingleTablePredicates.BuildAndTree();
            } 

            Node rightSingleTablePredicateNode = null;
            if ((rightInputNode.Op.OpType != OpType.ScanTable) &&
                (joinOp.OpType != OpType.LeftOuterJoin)) 
            {
                Predicate rightSingleTablePredicates = predicate.GetSingleTablePredicates(rightTableNodeInfo.Definitions, out predicate); 
                rightSingleTablePredicateNode = rightSingleTablePredicates.BuildAndTree(); 
            }
 
            //
            // Now check to see if the predicate contains some "join predicates". We can
            // add these to the existing join predicate (if any).
            // We can only do this for inner joins and cross joins - not for LOJs 
            //
            Node newJoinPredicateNode = null; 
            if (joinOp.OpType == OpType.CrossJoin || joinOp.OpType == OpType.InnerJoin) 
            {
                Predicate joinPredicate = predicate.GetJoinPredicates(leftTableInfo.Definitions, rightTableNodeInfo.Definitions, out predicate); 
                newJoinPredicateNode = joinPredicate.BuildAndTree();
            }

            // 
            // Now for the dirty work. We've identified some predicates that could be pushed
            // into the left table, some predicates that could be pushed into the right table 
            // and some that could become join predicates. 
            //
            if (leftSingleTablePredicateNode != null) 
            {
                leftInputNode = command.CreateNode(command.CreateFilterOp(), leftInputNode, leftSingleTablePredicateNode);
                needsTransformation = true;
            } 
            if (rightSingleTablePredicateNode != null)
            { 
                rightInputNode = command.CreateNode(command.CreateFilterOp(), rightInputNode, rightSingleTablePredicateNode); 
                needsTransformation = true;
            } 

            // Identify the new join predicate
            if (newJoinPredicateNode != null)
            { 
                needsTransformation = true;
                if (joinOp.OpType == OpType.CrossJoin) 
                { 
                    joinOp = command.CreateInnerJoinOp();
                } 
                else
                {
                    PlanCompiler.Assert(joinOp.OpType == OpType.InnerJoin, "unexpected non-InnerJoin?");
                    newJoinPredicateNode = PlanCompilerUtil.CombinePredicates(joinNode.Child2, newJoinPredicateNode, command); 
                }
            } 
            else 
            {
                newJoinPredicateNode = (joinOp.OpType == OpType.CrossJoin) ? null : joinNode.Child2; 
            }

            //
            // If nothing has changed, then just return the current node. Otherwise, 
            // we will loop forever
            // 
            if (!needsTransformation) 
            {
                return false; 
            }

            Node newJoinNode;
            // 
            // Finally build up a new join node
            // 
            if (joinOp.OpType == OpType.CrossJoin) 
            {
                newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode); 
            }
            else
            {
                newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode, newJoinPredicateNode); 
            }
 
            // 
            // Build up a new filterNode above this join node. But only if we have a filter left
            // 
            Node newFilterPredicateNode = predicate.BuildAndTree();
            if (newFilterPredicateNode == null)
            {
                newNode = newJoinNode; 
            }
            else 
            { 
                newNode = command.CreateNode(command.CreateFilterOp(), newJoinNode, newFilterPredicateNode);
            } 
            return true;
        }
        #endregion
 
        #region Filter over OuterApply
        internal static readonly PatternMatchRule Rule_FilterOverOuterApply = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                                  new Node(OuterApplyOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(LeafOp.Pattern)),
                                  new Node(LeafOp.Pattern)),
                         ProcessFilterOverOuterApply);
        ///  
        /// Convert Filter(OuterApply(X,Y), p) into
        ///    Filter(CrossApply(X,Y), p) 
        /// if "p" is not null-preserving for Y (ie) "p" does not preserve null values from Y 
        /// 
        /// Rule processing context 
        /// Filter node
        /// modified subtree
        /// transformation status
        static bool ProcessFilterOverOuterApply(RuleProcessingContext context, Node filterNode, out Node newNode) 
        {
            newNode = filterNode; 
            Node applyNode = filterNode.Child0; 
            Op applyOp = applyNode.Op;
            Node applyRightInputNode = applyNode.Child1; 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command;

            // 
            // Check to see if the current predicate preserves nulls for the right table.
            // If it doesn't then we can convert the outer apply into a cross-apply, 
            // 
            ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(applyRightInputNode);
            Predicate predicate = new Predicate(command, filterNode.Child1); 
            if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
            {
                Node newApplyNode = command.CreateNode(command.CreateCrossApplyOp(), applyNode.Child0, applyRightInputNode);
                Node newFilterNode = command.CreateNode(command.CreateFilterOp(), newApplyNode, filterNode.Child1); 
                newNode = newFilterNode;
                return true; 
            } 

            return false; 
        }

        #endregion
 
        #region FilterWithConstantPredicate
        internal static readonly PatternMatchRule Rule_FilterWithConstantPredicate = 
            new PatternMatchRule(new Node(FilterOp.Pattern, 
                          new Node(LeafOp.Pattern),
                          new Node(ConstantPredicateOp.Pattern)), 
                 ProcessFilterWithConstantPredicate);
        /// 
        /// Convert
        ///    Filter(X, true)  => X 
        ///    Filter(X, false) => Project(Filter(SingleRowTableOp, ...), false)
        /// where ... represent variables that are equivalent to the table columns 
        ///  
        /// Rule processing context
        /// Current subtree 
        /// modified subtree
        /// transformation status
        static bool ProcessFilterWithConstantPredicate(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n;
            ConstantPredicateOp predOp = (ConstantPredicateOp)n.Child1.Op; 
 
            // If we're dealing with a "true" predicate, then simply return the RelOp
            // input to the filter 
            if (predOp.IsTrue)
            {
                newNode = n.Child0;
                return true; 
            }
 
            PlanCompiler.Assert(predOp.IsFalse, "unexpected non-false predicate?"); 
            // We're dealing with a "false" predicate, then we can get rid of the
            // input, and replace it with a dummy project 

            //
            // If the input is already a singlerowtableOp, then there's nothing
            // further to do 
            //
            if (n.Child0.Op.OpType == OpType.SingleRowTable || 
                (n.Child0.Op.OpType == OpType.Project && 
                 n.Child0.Child0.Op.OpType == OpType.SingleRowTable))
            { 
                return false;
            }

            TransformationRulesContext trc = (TransformationRulesContext)context; 
            ExtendedNodeInfo childNodeInfo = trc.Command.GetExtendedNodeInfo(n.Child0);
            List varDefNodeList = new List(); 
            VarVec newVars = trc.Command.CreateVarVec(); 
            foreach (Var v in childNodeInfo.Definitions)
            { 
                NullOp nullConst = trc.Command.CreateNullOp(v.Type);
                Node constNode = trc.Command.CreateNode(nullConst);
                Var computedVar;
                Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar); 
                trc.AddVarMapping(v, computedVar);
                newVars.Set(computedVar); 
                varDefNodeList.Add(varDefNode); 
            }
            // If no vars have been selected out, add a dummy var 
            if (newVars.IsEmpty)
            {
                NullOp nullConst = trc.Command.CreateNullOp(trc.Command.BooleanType);
                Node constNode = trc.Command.CreateNode(nullConst); 
                Var computedVar;
                Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar); 
                newVars.Set(computedVar); 
                varDefNodeList.Add(varDefNode);
            } 

            Node singleRowTableNode = trc.Command.CreateNode(trc.Command.CreateSingleRowTableOp());
            n.Child0 = singleRowTableNode;
 
            Node varDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp(), varDefNodeList);
            ProjectOp projectOp = trc.Command.CreateProjectOp(newVars); 
            Node projectNode = trc.Command.CreateNode(projectOp, n, varDefListNode); 

            projectNode.Child0 = n; 
            newNode = projectNode;
            return true;
        }
 
        #endregion
 
        #region All FilterOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
                 FilterOpRules.Rule_FilterWithConstantPredicate, 
                 FilterOpRules.Rule_FilterOverCrossJoin,
                 FilterOpRules.Rule_FilterOverDistinct,
                 FilterOpRules.Rule_FilterOverExcept,
                 FilterOpRules.Rule_FilterOverFilter, 
                 FilterOpRules.Rule_FilterOverGroupBy,
                 FilterOpRules.Rule_FilterOverInnerJoin, 
                 FilterOpRules.Rule_FilterOverIntersect, 
                 FilterOpRules.Rule_FilterOverLeftOuterJoin,
                 FilterOpRules.Rule_FilterOverProject, 
                 FilterOpRules.Rule_FilterOverUnionAll,
                 FilterOpRules.Rule_FilterOverOuterApply,
        };
 
        #endregion
    } 
    #endregion 

    #region Project Rules 
    /// 
    /// Transformation rules for ProjectOp
    /// 
    internal static class ProjectOpRules 
    {
        #region ProjectOverProject 
        internal static readonly PatternMatchRule Rule_ProjectOverProject = 
            new PatternMatchRule(new Node(ProjectOp.Pattern,
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern)),
                                 ProcessProjectOverProject); 
        /// 
        /// Converts a Project(Project(X, c1,...), d1,...) => 
        ///            Project(X, d1', d2'...) 
        /// where d1', d2' etc. are the "mapped" versions of d1, d2 etc.
        ///  
        /// Rule processing context
        /// Current ProjectOp node
        /// modified subtree
        /// Transformation status 
        static bool ProcessProjectOverProject(RuleProcessingContext context, Node projectNode, out Node newNode)
        { 
            newNode = projectNode; 
            ProjectOp projectOp = (ProjectOp)projectNode.Op;
            Node varDefListNode = projectNode.Child1; 
            Node subProjectNode = projectNode.Child0;
            ProjectOp subProjectOp = (ProjectOp)subProjectNode.Op;
            TransformationRulesContext trc = (TransformationRulesContext)context;
 
            // If any of the defining expressions is not a scalar op tree, then simply
            // quit 
            Dictionary varRefMap = new Dictionary(); 
            foreach (Node varDefNode in varDefListNode.Children)
            { 
                if (!trc.IsScalarOpTree(varDefNode.Child0, varRefMap))
                {
                    return false;
                } 
            }
 
            Dictionary varMap = trc.GetVarMap(subProjectNode.Child1, varRefMap); 
            if (varMap == null)
            { 
                return false;
            }

            // create a new varDefList node... 
            Node newVarDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp());
 
            // Remap any local definitions, I have 
            foreach (Node varDefNode in varDefListNode.Children)
            { 
                // update the defining expression
                varDefNode.Child0 = trc.ReMap(varDefNode.Child0, varMap);
                trc.Command.RecomputeNodeInfo(varDefNode);
                newVarDefListNode.Children.Add(varDefNode); 
            }
 
            // Now, pull up any definitions of the subProject that I publish myself 
            ExtendedNodeInfo projectNodeInfo = trc.Command.GetExtendedNodeInfo(projectNode);
            foreach (Node chi in subProjectNode.Child1.Children) 
            {
                VarDefOp varDefOp = (VarDefOp)chi.Op;
                if (projectNodeInfo.Definitions.IsSet(varDefOp.Var))
                { 
                    newVarDefListNode.Children.Add(chi);
                } 
            } 

            // 
            // now that we have remapped all our computed vars, simply bypass the subproject
            // node
            //
            projectNode.Child0 = subProjectNode.Child0; 
            projectNode.Child1 = newVarDefListNode;
            return true; 
        } 
        #endregion
 
        #region ProjectWithNoLocalDefinitions
        internal static readonly PatternMatchRule Rule_ProjectWithNoLocalDefs =
            new PatternMatchRule(new Node(ProjectOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(VarDefListOp.Pattern)),
                                 ProcessProjectWithNoLocalDefinitions); 
        ///  
        /// Eliminate a ProjectOp that has no local definitions at all and
        /// no external references, (ie) if Child1 
        /// of the ProjectOp (the VarDefListOp child) has no children, then the ProjectOp
        /// is serving no useful purpose. Get rid of the ProjectOp, and replace it with its
        /// child
        ///  
        /// rule processing context
        /// current subtree 
        /// transformed subtree 
        /// transformation status
        static bool ProcessProjectWithNoLocalDefinitions(RuleProcessingContext context, Node n, out Node newNode) 
        {
            newNode = n;
            NodeInfo nodeInfo = context.Command.GetNodeInfo(n);
 
            // We cannot eliminate this node because it can break other rules,
            // e.g. ProcessApplyOverAnything which relies on existance of external refs to substitute 
            // CrossApply(x, y) => CrossJoin(x, y). See SQLBU #481719. 
            if (!nodeInfo.ExternalReferences.IsEmpty)
            { 
                return false;
            }

            newNode = n.Child0; 
            return true;
        } 
 
        #endregion
 
        #region ProjectOpWithSimpleVarRedefinitions
        internal static readonly SimpleRule Rule_ProjectOpWithSimpleVarRedefinitions = new SimpleRule(OpType.Project, ProcessProjectWithSimpleVarRedefinitions);
        /// 
        /// If the ProjectOp defines some computedVars, but those computedVars are simply 
        /// redefinitions of other Vars, then eliminate the computedVars.
        /// 
        /// Project(X, VarDefList(VarDef(cv1, VarRef(v1)), ...)) 
        ///    can be transformed into
        /// Project(X, VarDefList(...)) 
        /// where cv1 has now been replaced by v1
        /// 
        /// Rule processing context
        /// current subtree 
        /// transformed subtree
        /// transformation status 
        static bool ProcessProjectWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode) 
        {
            newNode = n; 
            ProjectOp projectOp = (ProjectOp)n.Op;

            if (n.Child1.Children.Count == 0)
            { 
                return false;
            } 
 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command; 

            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);

            // 
            // Check to see if any of the computed Vars defined by this ProjectOp
            // are simple redefinitions of other VarRefOps. Consider only those 
            // VarRefOps that are not "external" references 
            bool canEliminateSomeVars = false;
            foreach (Node varDefNode in n.Child1.Children) 
            {
                Node definingExprNode = varDefNode.Child0;
                if (definingExprNode.Op.OpType == OpType.VarRef)
                { 
                    VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
                    if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var)) 
                    { 
                        // this is a Var that we should remove
                        canEliminateSomeVars = true; 
                        break;
                    }
                }
            } 

            // Did we have any redefinitions 
            if (!canEliminateSomeVars) 
            {
                return false; 
            }

            //
            // OK. We've now identified a set of vars that are simple redefinitions. 
            // Try and replace the computed Vars with the Vars that they're redefining
            // 
 
            // Lets now build up a new VarDefListNode
            List newVarDefNodes = new List(); 
            foreach (Node varDefNode in n.Child1.Children)
            {
                VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp; 
                if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
                { 
                    projectOp.Outputs.Clear(varDefOp.Var); 
                    projectOp.Outputs.Set(varRefOp.Var);
                    trc.AddVarMapping(varDefOp.Var, varRefOp.Var); 
                }
                else
                {
                    newVarDefNodes.Add(varDefNode); 
                }
            } 
 
            // Note: Even if we don't have any local var definitions left, we should not remove
            // this project yet because: 
            //  (1) this project node may be prunning out some outputs;
            //  (2) the rule Rule_ProjectWithNoLocalDefs, would do that later anyway.

            // Create a new vardeflist node, and set that as Child1 for the projectOp 
            Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
            n.Child1 = newVarDefListNode; 
            return true; // some part of the subtree was modified 
        }
 

        #endregion

        #region ProjectOpWithNullSentinel 
        internal static readonly SimpleRule Rule_ProjectOpWithNullSentinel = new SimpleRule(OpType.Project, ProcessProjectOpWithNullSentinel);
        ///  
        /// Tries to remove null sentinel definitions by replacing them to vars that are guaranteed 
        /// to be non-nullable and of integer type, or with reference to other constants defined in the
        /// same project. In particular, 
        ///
        ///  - If based on the ancestors, the value of the null sentinel can be changed and the
        /// input of the project has a var that is guaranteed to be non-nullable and
        /// is of integer type, then the definitions of the vars defined as NullSentinels in the ProjectOp 
        /// are replaced with a reference to that var. I.eg:
        /// 
        /// Project(X, VarDefList(VarDef(ns_var, NullSentinel), ...)) 
        ///    can be transformed into
        /// Project(X, VarDefList(VarDef(ns_var, VarRef(v))...)) 
        /// where v is known to be non-nullable
        ///
        /// - Else, if based on the ancestors, the value of the null sentinel can be changed and
        /// the project already has definitions of other int constants, the definitions of the null sentinels 
        /// are removed and the respective vars are remapped to the var representing the constant.
        /// 
        /// - Else, the definitions of the all null sentinels except for one are removed, and the 
        /// the respective vars are remapped to the remaining null sentinel.
        ///  
        /// Rule processing context
        /// current subtree
        /// transformed subtree
        /// transformation status 
        static bool ProcessProjectOpWithNullSentinel(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n; 
            ProjectOp projectOp = (ProjectOp)n.Op;
            Node varDefListNode = n.Child1; 

            if (varDefListNode.Children.Where(c => c.Child0.Op.OpType == OpType.NullSentinel).Count() == 0)
            {
                return false; 
            }
 
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            Command command = trc.Command;
            ExtendedNodeInfo relOpInputNodeInfo = command.GetExtendedNodeInfo(n.Child0); 
            Var inputSentinel;
            bool reusingConstantFromSameProjectAsSentinel = false;

            bool canChangeNullSentinelValue = trc.CanChangeNullSentinelValue; 

            if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(relOpInputNodeInfo.NonNullableDefinitions, out inputSentinel)) 
            { 
                reusingConstantFromSameProjectAsSentinel = true;
                if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.Constant || child.Child0.Op.OpType == OpType.InternalConstant).Select(child => ((VarDefOp)(child.Op)).Var), out inputSentinel)) 
                {
                    inputSentinel = n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.NullSentinel).Select(child => ((VarDefOp)(child.Op)).Var).FirstOrDefault();
                    if (inputSentinel == null)
                    { 
                        return false;
                    } 
                } 
            }
 
            bool modified = false;

            for (int i = n.Child1.Children.Count-1; i >= 0; i--)
            { 
                Node varDefNode = n.Child1.Children[i];
                Node definingExprNode = varDefNode.Child0; 
                if (definingExprNode.Op.OpType == OpType.NullSentinel) 
                {
                    if (!reusingConstantFromSameProjectAsSentinel) 
                    {
                        VarRefOp varRefOp = command.CreateVarRefOp(inputSentinel);
                        varDefNode.Child0 = command.CreateNode(varRefOp);
                        command.RecomputeNodeInfo(varDefNode); 
                        modified = true;
                    } 
                    else if (!inputSentinel.Equals(((VarDefOp)varDefNode.Op).Var)) 
                    {
                        projectOp.Outputs.Clear(((VarDefOp)varDefNode.Op).Var); 
                        n.Child1.Children.RemoveAt(i);
                        trc.AddVarMapping(((VarDefOp)varDefNode.Op).Var, inputSentinel);
                        modified = true;
                    } 
                }
            } 
 
            if (modified)
            { 
                command.RecomputeNodeInfo(n.Child1);
            }
            return modified;
        } 
        #endregion
 
        #region All ProjectOp Rules 
        //The order of the rules is important
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 ProjectOpRules.Rule_ProjectOpWithNullSentinel,
                 ProjectOpRules.Rule_ProjectOpWithSimpleVarRedefinitions,
                 ProjectOpRules.Rule_ProjectOverProject,
                 ProjectOpRules.Rule_ProjectWithNoLocalDefs, 
        };
        #endregion 
    } 
    #endregion
 
    #region Apply Rules
    /// 
    /// Transformation rules for ApplyOps - CrossApply, OuterApply
    ///  
    internal static class ApplyOpRules
    { 
        #region ApplyOverFilter 
        internal static readonly PatternMatchRule Rule_CrossApplyOverFilter =
            new PatternMatchRule(new Node(CrossApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern))), 
                                 ProcessApplyOverFilter);
        internal static readonly PatternMatchRule Rule_OuterApplyOverFilter = 
            new PatternMatchRule(new Node(OuterApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(FilterOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern))),
                                 ProcessApplyOverFilter);
        ///  
        /// Convert CrossApply(X, Filter(Y, p)) => InnerJoin(X, Y, p)
        ///         OuterApply(X, Filter(Y, p)) => LeftOuterJoin(X, Y, p) 
        /// if "Y" has no external references to X 
        /// 
        /// Rule processing context 
        /// Current ApplyOp
        /// transformed subtree
        /// Transformation status
        static bool ProcessApplyOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode) 
        {
            newNode = applyNode; 
            Node filterNode = applyNode.Child1; 
            Command command = context.Command;
 
            NodeInfo filterInputNodeInfo = command.GetNodeInfo(filterNode.Child0);
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);

            // 
            // check to see if the inputNode to the FilterOp has any external references
            // to the left child of the ApplyOp. If it does, we simply return, we 
            // can't do much more here 
            //
            if (filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions)) 
            {
                return false;
            }
 
            //
            // We've now gotten to the stage where the only external references (if any) 
            // are from the filter predicate. 
            // We can now simply convert the apply into an inner/leftouter join with the
            // filter predicate acting as the join condition 
            //
            JoinBaseOp joinOp = null;
            if (applyNode.Op.OpType == OpType.CrossApply)
            { 
                joinOp = command.CreateInnerJoinOp();
            } 
            else 
            {
                joinOp = command.CreateLeftOuterJoinOp(); 
            }

            newNode = command.CreateNode(joinOp, applyNode.Child0, filterNode.Child0, filterNode.Child1);
            return true; 
        }
 
        internal static readonly PatternMatchRule Rule_OuterApplyOverProjectInternalConstantOverFilter = 
             new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(ProjectOp.Pattern,
                                                    new Node(FilterOp.Pattern,
                                                             new Node(LeafOp.Pattern),
                                                             new Node(LeafOp.Pattern)), 
                                                    new Node(VarDefListOp.Pattern,
                                                             new Node(VarDefOp.Pattern, 
                                                                      new Node(InternalConstantOp.Pattern))))), 
                         ProcessOuterApplyOverDummyProjectOverFilter);
 
        internal static readonly PatternMatchRule Rule_OuterApplyOverProjectNullSentinelOverFilter =
           new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                         new Node(LeafOp.Pattern),
                                         new Node(ProjectOp.Pattern, 
                                                  new Node(FilterOp.Pattern,
                                                           new Node(LeafOp.Pattern), 
                                                           new Node(LeafOp.Pattern)), 
                                                  new Node(VarDefListOp.Pattern,
                                                           new Node(VarDefOp.Pattern, 
                                                                    new Node(NullSentinelOp.Pattern))))),
                       ProcessOuterApplyOverDummyProjectOverFilter);

        ///  
        /// Convert OuterApply(X, Project(Filter(Y, p), constant)) =>
        ///     LeftOuterJoin(X, Project(Y, constant), p) 
        /// if "Y" has no external references to X 
        ///
        /// In an ideal world, we would be able to push the Project below the Filter, 
        /// and then have the normal ApplyOverFilter rule handle this - but that causes us
        /// problems because we always try to pull up ProjectOp's as high as possible. Hence,
        /// the special case for this rule
        /// 
        /// 
        /// Rule processing context 
        /// Current ApplyOp 
        /// transformed subtree
        /// Transformation status 
        static bool ProcessOuterApplyOverDummyProjectOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            newNode = applyNode;
            Node projectNode = applyNode.Child1; 
            ProjectOp projectOp = (ProjectOp)projectNode.Op;
            Node filterNode = projectNode.Child0; 
            Node filterInputNode = filterNode.Child0; 
            Command command = context.Command;
 
            ExtendedNodeInfo filterInputNodeInfo = command.GetExtendedNodeInfo(filterInputNode);
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);

            // 
            // Check if the outputs of the ProjectOp or the inputNode to the FilterOp
            // have any external references to the left child of the ApplyOp. 
            // If they do, we simply return, we can't do much more here 
            //
            if (projectOp.Outputs.Overlaps(applyLeftChildNodeInfo.Definitions) || filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions)) 
            {
                return false;
            }
 
            //
            // We've now gotten to the stage where the only external references (if any) 
            // are from the filter predicate. 
            // First, push the Project node down below the filter - but make sure that
            // all the Vars needed by the Filter are projected out 
            //
            bool capWithProject = false;
            Node joinNodeRightInput = null;
 
            //
            // Check to see whether there is a sentinel var available - if there is, then 
            // we can simply move the ProjectOp above the join we're going to construct 
            // and of course, build a NullIf expression for the constant.
            // Otherwise, the ProjectOp will need to be the child of the joinOp that we're 
            // building - and we'll need to make sure that the ProjectOp projects out
            // any vars that are required for the Filter in the first place
            //
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            Var sentinelVar;
            bool sentinelIsInt32; 
 
            if (TransformationRulesContext.TryGetInt32Var(filterInputNodeInfo.NonNullableDefinitions, out sentinelVar))
            { 
                sentinelIsInt32 = true;
            }
            else
            { 
                sentinelVar = filterInputNodeInfo.NonNullableDefinitions.First;
                sentinelIsInt32 = false; 
            } 

            if (sentinelVar != null) 
            {
                capWithProject = true;
                Node varDefNode = projectNode.Child1.Child0;
                if (varDefNode.Child0.Op.OpType == OpType.NullSentinel && sentinelIsInt32 && trc.CanChangeNullSentinelValue) 
                {
                    varDefNode.Child0 = context.Command.CreateNode(context.Command.CreateVarRefOp(sentinelVar)); 
                } 
                else
                { 
                    varDefNode.Child0 = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
                }
                command.RecomputeNodeInfo(varDefNode);
                command.RecomputeNodeInfo(projectNode.Child1); 
                joinNodeRightInput = filterInputNode;
            } 
            else 
            {
                // We need to keep the projectNode - unfortunately 
                joinNodeRightInput = projectNode;
                //
                // Make sure that every Var that is needed for the filter predicate
                // is captured in the projectOp outputs list 
                //
                NodeInfo filterPredicateNodeInfo = command.GetNodeInfo(filterNode.Child1); 
                foreach (Var v in filterPredicateNodeInfo.ExternalReferences) 
                {
                    if (filterInputNodeInfo.Definitions.IsSet(v)) 
                    {
                        projectOp.Outputs.Set(v);
                    }
                } 
                projectNode.Child0 = filterInputNode;
            } 
 
            context.Command.RecomputeNodeInfo(projectNode);
 
            //
            // We can now simply convert the apply into an inner/leftouter join with the
            // filter predicate acting as the join condition
            // 
            Node joinNode = command.CreateNode(command.CreateLeftOuterJoinOp(), applyNode.Child0, joinNodeRightInput, filterNode.Child1);
            if (capWithProject) 
            { 
                ExtendedNodeInfo joinNodeInfo = command.GetExtendedNodeInfo(joinNode);
                projectNode.Child0 = joinNode; 
                projectOp.Outputs.Or(joinNodeInfo.Definitions);
                newNode = projectNode;
            }
            else 
            {
                newNode = joinNode; 
            } 
            return true;
        } 
        #endregion

        #region ApplyOverProject
        internal static readonly PatternMatchRule Rule_CrossApplyOverProject = 
            new PatternMatchRule(new Node(CrossApplyOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern))), 
                                 ProcessCrossApplyOverProject);

        /// 
        /// Converts a CrossApply(X, Project(Y, ...)) => Project(CrossApply(X, Y), ...) 
        /// where the projectVars are simply pulled up
        ///  
        /// RuleProcessing context 
        /// The ApplyOp subtree
        /// transformed subtree 
        /// Transfomation status
        static bool ProcessCrossApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            newNode = applyNode; 
            Node projectNode = applyNode.Child1;
            ProjectOp projectOp = (ProjectOp)projectNode.Op as ProjectOp; 
            Command command = context.Command; 

            // We can simply pull up the project over the apply; provided we make sure 
            // that all the definitions of the apply are represented in the projectOp
            ExtendedNodeInfo applyNodeInfo = command.GetExtendedNodeInfo(applyNode);
            VarVec vec = command.CreateVarVec(projectOp.Outputs);
            vec.Or(applyNodeInfo.Definitions); 
            projectOp.Outputs.InitFrom(vec);
 
            // pull up the project over the apply node 
            applyNode.Child1 = projectNode.Child0;
            context.Command.RecomputeNodeInfo(applyNode); 
            projectNode.Child0 = applyNode;

            newNode = projectNode;
            return true; 
        }
 
        internal static readonly PatternMatchRule Rule_OuterApplyOverProject = 
             new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                           new Node(LeafOp.Pattern), 
                                           new Node(ProjectOp.Pattern,
                                                    new Node(LeafOp.Pattern),
                                                    new Node(LeafOp.Pattern))),
                         ProcessOuterApplyOverProject); 
        /// 
        /// Converts a 
        ///     OuterApply(X, Project(Y, ...)) 
        /// =>
        ///     Project(OuterApply(X, Project(Y, ...)), ...) or 
        ///     Project(OuterApply(X, Y), ...)
        ///
        /// The second (simpler) form is used if a "sentinel" var can be located (ie)
        /// some Var of Y that is guaranteed to be non-null. Otherwise, we create a 
        /// dummy ProjectNode as the right child of the Apply - which
        /// simply projects out all the vars of the Y, and adds on a constant (say "1"). This 
        /// constant is now treated as the sentinel var 
        ///
        /// Then the existing ProjectOp is pulled up above the the outer-apply, but all the locally defined 
        /// Vars have their defining expressions now expressed as
        ///     case when sentinelVar is null then null else oldDefiningExpr end
        /// where oldDefiningExpr represents the original defining expression
        /// This allows us to get nulls for the appropriate columns when necessary. 
        ///
        /// Special cases. 
        /// * If the oldDefiningExpr is itself an internal constant equivalent to the null sentinel ("1"), 
        ///   we simply project a ref to the null sentinel, no need for cast
        /// * If the ProjectOp contained exactly one locally defined Var, and it was a constant, then 
        ///   we simply return - we will be looping endlessly otherwise
        /// * If the ProjectOp contained no local definitions, then we don't need to create the
        ///   dummy projectOp - we can simply pull up the Project
        /// * If any of the defining expressions of the local definitions was simply a VarRefOp 
        ///   referencing a Var that was defined by Y, then there is no need to add the case
        ///   expression for that. 
        /// 
        /// 
        /// RuleProcessing context 
        /// The ApplyOp subtree
        /// transformed subtree
        /// Transfomation status
        static bool ProcessOuterApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode) 
        {
            newNode = applyNode; 
            Node projectNode = applyNode.Child1; 
            Node varDefListNode = projectNode.Child1;
 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            ExtendedNodeInfo inputNodeInfo = context.Command.GetExtendedNodeInfo(projectNode.Child0);
            Var sentinelVar = inputNodeInfo.NonNullableDefinitions.First;
 
            //
            // special case handling first - we'll end up in an infinite loop otherwise. 
            // If the ProjectOp is the dummy ProjectOp that we would be building (ie) 
            // it defines only 1 var - and the defining expression is simply a constant
            // 
            if (sentinelVar == null &&
                varDefListNode.Children.Count == 1 &&
                (varDefListNode.Child0.Child0.Op.OpType == OpType.InternalConstant || varDefListNode.Child0.Child0.Op.OpType == OpType.NullSentinel))
            { 
                return false;
            } 
 
            Command command = context.Command;
            Node dummyProjectNode = null; 
            InternalConstantOp nullSentinelDefinitionOp = null;

            // get node information for the project's child
            ExtendedNodeInfo projectInputNodeInfo = command.GetExtendedNodeInfo(projectNode.Child0); 

            // 
            // Build up a dummy project node. 
            // Walk through each local definition of the current project Node, and convert
            // all expressions into case expressions whose value depends on the var 
            // produced by the dummy project node
            //

            // Dev10 #480443: If any of the definitions changes we need to recompute the node info. 
            bool anyVarDefChagned = false;
            foreach (Node varDefNode in varDefListNode.Children) 
            { 
                PlanCompiler.Assert(varDefNode.Op.OpType == OpType.VarDef, "Expected VarDefOp. Found " + varDefNode.Op.OpType + " instead");
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp; 
                if (varRefOp == null || !projectInputNodeInfo.Definitions.IsSet(varRefOp.Var))
                {
                    // do we need to build a dummy project node
                    if (sentinelVar == null) 
                    {
                        nullSentinelDefinitionOp = command.CreateInternalConstantOp(command.IntegerType, 1); 
                        Node dummyConstantExpr = command.CreateNode(nullSentinelDefinitionOp); 
                        Node dummyProjectVarDefListNode = command.CreateVarDefListNode(dummyConstantExpr, out sentinelVar);
                        ProjectOp dummyProjectOp = command.CreateProjectOp(sentinelVar); 
                        dummyProjectOp.Outputs.Or(projectInputNodeInfo.Definitions);
                        dummyProjectNode = command.CreateNode(dummyProjectOp, projectNode.Child0, dummyProjectVarDefListNode);
                    }
 
                    Node currentDefinition;
 
                    // If the null sentinel was just created, and the local definition of the current project Node 
                    // is an internal constant equivalent to the null sentinel, it can be rewritten as a reference
                    // to the null sentinel. 
                    if (nullSentinelDefinitionOp != null && ((true == nullSentinelDefinitionOp.IsEquivalent(varDefNode.Child0.Op)) ||
                        //The null sentinel has the same value of 1, thus it is safe.
                        varDefNode.Child0.Op.OpType == OpType.NullSentinel))
                    { 
                        currentDefinition = command.CreateNode(command.CreateVarRefOp(sentinelVar));
                    } 
                    else 
                    {
                        currentDefinition = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0); 
                    }
                    varDefNode.Child0 = currentDefinition;
                    command.RecomputeNodeInfo(varDefNode);
                    anyVarDefChagned = true; 
                }
            } 
 
            // Recompute node info if needed
            if (anyVarDefChagned) 
            {
                command.RecomputeNodeInfo(varDefListNode);
            }
 
            //
            // If we've created a dummy project node, make that the new child of the applyOp 
            // 
            applyNode.Child1 = dummyProjectNode != null ? dummyProjectNode : projectNode.Child0;
            command.RecomputeNodeInfo(applyNode); 

            //
            // Pull up the project node above the apply node now. Also, make sure that every Var of
            // the applyNode's definitions actually shows up in the new Project 
            //
            projectNode.Child0 = applyNode; 
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0); 
            ProjectOp projectOp = (ProjectOp)projectNode.Op;
            projectOp.Outputs.Or(applyLeftChildNodeInfo.Definitions); 

            newNode = projectNode;
            return true;
        } 
        #endregion
 
        #region ApplyOverAnything 
        internal static readonly PatternMatchRule Rule_CrossApplyOverAnything =
            new PatternMatchRule(new Node(CrossApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)),
                                 ProcessApplyOverAnything);
        internal static readonly PatternMatchRule Rule_OuterApplyOverAnything = 
            new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessApplyOverAnything);
 
        /// 
        /// Converts a CrossApply(X,Y) => CrossJoin(X,Y)
        ///            OuterApply(X,Y) => LeftOuterJoin(X, Y, true)
        ///  only if Y has no external references to X 
        /// 
        /// Rule processing context 
        /// The ApplyOp subtree 
        /// transformed subtree
        /// the transformation status 
        static bool ProcessApplyOverAnything(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            newNode = applyNode;
            Node applyLeftChild = applyNode.Child0; 
            Node applyRightChild = applyNode.Child1;
            ApplyBaseOp applyOp = (ApplyBaseOp)applyNode.Op; 
            Command command = context.Command; 

            ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyRightChild); 
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyLeftChild);

            //
            // If we're currently dealing with an OuterApply, and the right child is guaranteed 
            // to produce at least one row, then we can convert the outer-apply into a cross apply
            // 
            bool convertedToCrossApply = false; 
            if (applyOp.OpType == OpType.OuterApply &&
                applyRightChildNodeInfo.MinRows >= RowCount.One) 
            {
                applyOp = command.CreateCrossApplyOp();
                convertedToCrossApply = true;
            } 

            // 
            // Does the right child reference any of the definitions of the left child? If it 
            // does, then simply return from this function
            // 
            if (applyRightChildNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
            {
                if (convertedToCrossApply)
                { 
                    newNode = command.CreateNode(applyOp, applyLeftChild, applyRightChild);
                    return true; 
                } 
                else
                { 
                    return false;
                }
            }
 
            //
            // So, we now know that the right child does not reference any definitions 
            // from the left. 
            // So, we simply convert the apply into an appropriate join Op
            // 
            if (applyOp.OpType == OpType.CrossApply)
            {
                //
                // Convert "x CrossApply y" into "x CrossJoin y" 
                //
                newNode = command.CreateNode(command.CreateCrossJoinOp(), 
                    applyLeftChild, applyRightChild); 
            }
            else // outer apply 
            {
                //
                // Convert "x OA y" into "x LOJ y on (true)"
                // 
                LeftOuterJoinOp joinOp = command.CreateLeftOuterJoinOp();
                ConstantPredicateOp trueOp = command.CreateTrueOp(); 
                Node trueNode = command.CreateNode(trueOp); 
                newNode = command.CreateNode(joinOp, applyLeftChild, applyRightChild, trueNode);
            } 
            return true;
        }
        #endregion
 
        #region ApplyIntoScalarSubquery
        internal static readonly PatternMatchRule Rule_CrossApplyIntoScalarSubquery = 
            new PatternMatchRule(new Node(CrossApplyOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessApplyIntoScalarSubquery);
        internal static readonly PatternMatchRule Rule_OuterApplyIntoScalarSubquery =
            new PatternMatchRule(new Node(OuterApplyOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessApplyIntoScalarSubquery); 
 
        /// 
        /// Converts a Apply(X,Y) => Project(X, Y1), where Y1 is a scalar subquery version of Y 
        /// The transformation is valid only if all of the following conditions hold:
        ///     1. Y produces only one output
        ///     2. Y produces at most one row
        ///     3. Y produces at least one row, or the Apply operator in question is an OuterApply 
        /// 
        /// Rule processing context 
        /// The ApplyOp subtree 
        /// transformed subtree
        /// the transformation status 
        static bool ProcessApplyIntoScalarSubquery(RuleProcessingContext context, Node applyNode, out Node newNode)
        {
            Command command = context.Command;
            ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child1); 
            OpType applyKind = applyNode.Op.OpType;
 
            if (!CanRewriteApply(applyNode.Child1, applyRightChildNodeInfo, applyKind)) 
            {
                newNode = applyNode; 
                return false;
            }

            // Create the project node over the original input with element over the apply as new projected var 
            ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
 
            Var oldVar = applyRightChildNodeInfo.Definitions.First; 

            // Project all the outputs from the left child 
            VarVec projectOpOutputs = command.CreateVarVec(applyLeftChildNodeInfo.Definitions);

            //
            // Remap the var defining tree to get it into a consistent state 
            // and then remove all references to oldVar from it to avoid them being wrongly remapped to newVar
            // in subsequent remappings. 
            // 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            trc.RemapSubtree(applyNode.Child1); 
            VarDefinitionRemapper.RemapSubtree(applyNode.Child1, command, oldVar);

            Node elementNode = command.CreateNode(command.CreateElementOp(oldVar.Type), applyNode.Child1);
 
            Var newVar;
            Node varDefListNode = command.CreateVarDefListNode(elementNode, out newVar); 
            projectOpOutputs.Set(newVar); 

            newNode = command.CreateNode( 
                command.CreateProjectOp(projectOpOutputs),
                applyNode.Child0,
                varDefListNode);
 
            // Add the var mapping from oldVar to newVar
            trc.AddVarMapping(oldVar, newVar); 
            return true; 
        }
 
        /// 
        /// Determines whether an applyNode can be rewritten into a projection with a scalar subquery.
        /// It can be done if all of the following conditions hold:
        ///     1. The right child or the apply has only one output 
        ///     2. The right child of the apply produces at most one row
        ///     3. The right child of the apply produces at least one row, or the Apply operator in question is an OuterApply 
        ///  
        /// 
        ///  
        /// 
        /// 
        private static bool CanRewriteApply(Node rightChild, ExtendedNodeInfo applyRightChildNodeInfo, OpType applyKind)
        { 
            //Check whether it produces only one definition
            if (applyRightChildNodeInfo.Definitions.Count != 1) 
            { 
                return false;
            } 

            //Check whether it produces at most one row
            if (applyRightChildNodeInfo.MaxRows != RowCount.One)
            { 
                return false;
            } 
 
            //For cross apply it must also return exactly one row
            if (applyKind == OpType.CrossApply && (applyRightChildNodeInfo.MinRows != RowCount.One)) 
            {
                return false;
            }
 
            //Dev10 #488632: Make sure the right child not only declares to produce only one definition,
            // but has exactly one output. For example, ScanTableOp really outputs all the columns from the table, 
            // but in its ExtendedNodeInfo.Definitions only these that are referenced are shown. 
            // This is to allow for projection pruning of the unreferenced columns.
            if (OutputCountVisitor.CountOutputs(rightChild) != 1) 
            {
                return false;
            }
 
            return true;
        } 
 
        /// 
        /// A visitor that calculates the number of output columns for a subree 
        /// with a given root
        /// 
        internal class OutputCountVisitor : BasicOpVisitorOfT
        { 
            #region Constructors
            internal OutputCountVisitor() 
            { 
            }
            #endregion 

            #region Public Methods
            /// 
            /// Calculates the number of output columns for the subree 
            /// rooted at the given node
            ///  
            ///  
            /// 
            internal static int CountOutputs(Node node) 
            {
                OutputCountVisitor visitor = new OutputCountVisitor();
                return visitor.VisitNode(node);
            } 

            #endregion 
 
            #region Visitor Methods
 
            #region Helpers
            /// 
            /// Visitor for children. Simply visit all children,
            /// and sum the number of their outputs. 
            /// 
            /// Current node 
            ///  
            internal new int VisitChildren(Node n)
            { 
                int result = 0;
                foreach (Node child in n.Children)
                {
                    result += VisitNode(child); 
                }
                return result; 
            } 

            ///  
            /// A default processor for any node.
            /// Returns the sum of the children outputs
            /// 
            ///  
            /// /returns>
            protected override int VisitDefault(Node n) 
            { 
                return VisitChildren(n);
            } 

            #endregion

            #region RelOp Visitors 

            #region SetOp Visitors 
 
            /// 
            /// The number of outputs is same as for any of the inputs 
            /// 
            /// 
            /// 
            ///  
            protected override int VisitSetOp(SetOp op, Node n)
            { 
                return op.Outputs.Count; 
            }
 
            #endregion

            /// 
            /// Distinct 
            /// 
            ///  
            ///  
            /// 
            public override int Visit(DistinctOp op, Node n) 
            {
                return op.Keys.Count;
            }
 
            /// 
            /// FilterOp 
            ///  
            /// 
            ///  
            /// 
            public override int Visit(FilterOp op, Node n)
            {
                return VisitNode(n.Child0); 
            }
 
            ///  
            /// GroupByOp
            ///  
            /// 
            /// 
            /// 
            public override int Visit(GroupByOp op, Node n) 
            {
                return op.Outputs.Count; 
            } 

            ///  
            /// ProjectOp
            /// 
            /// 
            ///  
            /// 
            public override int Visit(ProjectOp op, Node n) 
            { 
                return op.Outputs.Count;
            } 

            #region TableOps
            /// 
            /// ScanTableOp 
            /// 
            ///  
            ///  
            /// 
            public override int Visit(ScanTableOp op, Node n) 
            {
                return op.Table.Columns.Count;
            }
 
            /// 
            /// SingleRowTableOp 
            ///  
            /// 
            ///  
            /// 
            public override int Visit(SingleRowTableOp op, Node n)
            {
                return 0; 
            }
 
            ///  
            /// Same as the input
            ///  
            /// 
            /// 
            /// 
            protected override int VisitSortOp(SortBaseOp op, Node n) 
            {
                return VisitNode(n.Child0); 
            } 
            #endregion
            #endregion 

            #endregion
        }
 
        /// 
        /// A utility class that remaps a given var at its definition and also remaps all its references. 
        /// The given var is remapped to an arbitrary new var. 
        /// If the var is defined by a ScanTable, all the vars defined by that table and all their references
        /// are remapped as well. 
        /// 
        internal class VarDefinitionRemapper : VarRemapper
        {
            private readonly Var m_oldVar; 

            private VarDefinitionRemapper(Var oldVar, Command command) 
                : base(command) 
            {
                this.m_oldVar = oldVar; 
            }

            /// 
            /// Public entry point. 
            /// Remaps the subree rooted at the given tree
            ///  
            ///  
            /// 
            ///  
            internal static void RemapSubtree(Node root, Command command, Var oldVar)
            {
                VarDefinitionRemapper remapper = new VarDefinitionRemapper(oldVar, command);
                remapper.RemapSubtree(root); 
            }
 
            ///  
            /// Update vars in this subtree. Recompute the nodeinfo along the way
            /// Unlike the base implementation, we want to visit the childrent, even if no vars are in the 
            /// remapping dictionary.
            /// 
            /// 
            internal override void RemapSubtree(Node subTree) 
            {
                foreach (Node chi in subTree.Children) 
                { 
                    RemapSubtree(chi);
                } 

                VisitNode(subTree);
                m_command.RecomputeNodeInfo(subTree);
            } 

            ///  
            /// If the node defines the node that needs to be remapped, 
            /// it remaps it to a new var.
            ///  
            /// 
            /// 
            /// 
            public override void Visit(VarDefOp op, Node n) 
            {
                if (op.Var == m_oldVar) 
                { 
                    Var newVar = m_command.CreateComputedVar(n.Child0.Op.Type);
                    n.Op = m_command.CreateVarDefOp(newVar); 
                    AddMapping(m_oldVar, newVar);
                }
            }
 
            /// 
            /// If the columnVars defined by the table contain the var that needs to be remapped 
            /// all the column vars produces by the table are remaped to new vars. 
            /// 
            ///  
            /// 
            /// 
            public override void Visit(ScanTableOp op, Node n)
            { 
                if (op.Table.Columns.Contains(m_oldVar))
                { 
                    ScanTableOp newScanTableOp = m_command.CreateScanTableOp(op.Table.TableMetadata); 
                    VarDefListOp varDefListOp = m_command.CreateVarDefListOp();
                    for (int i = 0; i < op.Table.Columns.Count; i++) 
                    {
                        AddMapping(op.Table.Columns[i], newScanTableOp.Table.Columns[i]);
                    }
                    n.Op = newScanTableOp; 
                }
            } 
 
            /// 
            /// The var that needs to be remapped may be produced by a set op, 
            /// in which case the varmaps need to be updated too.
            /// 
            /// 
            ///  
            protected override void VisitSetOp(SetOp op, Node n)
            { 
                base.VisitSetOp(op, n); 

                if (op.Outputs.IsSet(m_oldVar)) 
                {
                    Var newVar = m_command.CreateSetOpVar(m_oldVar.Type);
                    op.Outputs.Clear(m_oldVar);
                    op.Outputs.Set(newVar); 
                    RemapVarMapKey(op.VarMap[0], newVar);
                    RemapVarMapKey(op.VarMap[1], newVar); 
                    AddMapping(m_oldVar, newVar); 
                }
            } 

            /// 
            /// Replaces the entry in the varMap in which m_oldVar is a key
            /// with an entry in which newVAr is the key and the value remains the same. 
            /// 
            ///  
            ///  
            private void RemapVarMapKey(VarMap varMap, Var newVar)
            { 
                Var value = varMap[m_oldVar];
                varMap.Remove(m_oldVar);
                varMap.Add(newVar, value);
            } 
        }
        #endregion 
 
        #region CrossApply over LeftOuterJoin of SingleRowTable with anything and with constant predicate
        internal static readonly PatternMatchRule Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable = 
            new PatternMatchRule(new Node(CrossApplyOp.Pattern,
                new Node(LeafOp.Pattern),
                new Node(LeftOuterJoinOp.Pattern,
                                          new Node(SingleRowTableOp.Pattern), 
                                          new Node(LeafOp.Pattern),
                                          new Node(ConstantPredicateOp.Pattern))), 
                                 ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable); 
        /// 
        /// Convert a CrossApply(X, LeftOuterJoin(SingleRowTable, Y, on true)) 
        ///    into just OuterApply(X, Y)
        /// 
        /// rule processing context
        /// the join node 
        /// transformed subtree
        /// transformation status 
        static bool ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable(RuleProcessingContext context, Node applyNode, out Node newNode) 
        {
            newNode = applyNode; 
            Node joinNode = applyNode.Child1;

            //Check the value of the predicate
            ConstantPredicateOp joinPredicate = (ConstantPredicateOp)joinNode.Child2.Op; 
            if (joinPredicate.IsFalse)
            { 
                return false; 
            }
 
            applyNode.Op = context.Command.CreateOuterApplyOp();
            applyNode.Child1 = joinNode.Child1;
            return true;
        } 
        #endregion
 
        #region All ApplyOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
                 ApplyOpRules.Rule_CrossApplyOverAnything, 
                 ApplyOpRules.Rule_CrossApplyOverFilter,
                 ApplyOpRules.Rule_CrossApplyOverProject,
                 ApplyOpRules.Rule_OuterApplyOverAnything,
                 ApplyOpRules.Rule_OuterApplyOverProjectInternalConstantOverFilter, 
                 ApplyOpRules.Rule_OuterApplyOverProjectNullSentinelOverFilter,
                 ApplyOpRules.Rule_OuterApplyOverProject, 
                 ApplyOpRules.Rule_OuterApplyOverFilter, 
                 ApplyOpRules.Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable,
                 ApplyOpRules.Rule_CrossApplyIntoScalarSubquery, 
                 ApplyOpRules.Rule_OuterApplyIntoScalarSubquery,
        };
        #endregion
    } 
    #endregion
 
    #region Join Rules 
    /// 
    /// Transformation rules for JoinOps 
    /// 
    internal static class JoinOpRules
    {
        #region JoinOverProject 
        internal static readonly PatternMatchRule Rule_CrossJoinOverProject1 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(LeafOp.Pattern), 
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern))),
                                 ProcessJoinOverProject);
        internal static readonly PatternMatchRule Rule_CrossJoinOverProject2 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverProject); 
        internal static readonly PatternMatchRule Rule_InnerJoinOverProject1 =
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(LeafOp.Pattern),
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverProject);
        internal static readonly PatternMatchRule Rule_InnerJoinOverProject2 = 
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverProject); 
        internal static readonly PatternMatchRule Rule_OuterJoinOverProject2 =
            new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern, 
                                          new Node(ProjectOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverProject); 
        ///  
        /// CrossJoin(Project(A), B) => Project(CrossJoin(A, B), modifiedvars)
        /// InnerJoin(Project(A), B, p) => Project(InnerJoin(A, B, p'), modifiedvars) 
        /// LeftOuterJoin(Project(A), B, p) => Project(LeftOuterJoin(A, B, p'), modifiedvars)
        /// 
        /// Rule processing context
        /// Current JoinOp tree to process 
        /// Transformed subtree
        /// transformation status 
        static bool ProcessJoinOverProject(RuleProcessingContext context, Node joinNode, out Node newNode) 
        {
            newNode = joinNode; 

            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command;
 
            Node joinConditionNode = joinNode.HasChild2 ? joinNode.Child2 : (Node)null;
            Dictionary varRefMap = new Dictionary(); 
            if (joinConditionNode != null && !trc.IsScalarOpTree(joinConditionNode, varRefMap)) 
            {
                return false; 
            }

            Node newJoinNode;
            Node newProjectNode; 

            // Now locate the ProjectOps 
            VarVec newVarSet = command.CreateVarVec(); 
            List varDefNodes = new List();
 
            //
            // Try and handle "project" on both sides only if we're not dealing with
            // an LOJ.
            // 
            if ((joinNode.Op.OpType != OpType.LeftOuterJoin) &&
                (joinNode.Child0.Op.OpType == OpType.Project) && 
                (joinNode.Child1.Op.OpType == OpType.Project)) 
            {
                ProjectOp projectOp1 = (ProjectOp)joinNode.Child0.Op; 
                ProjectOp projectOp2 = (ProjectOp)joinNode.Child1.Op;

                Dictionary varMap1 = trc.GetVarMap(joinNode.Child0.Child1, varRefMap);
                Dictionary varMap2 = trc.GetVarMap(joinNode.Child1.Child1, varRefMap); 
                if (varMap1 == null || varMap2 == null)
                { 
                    return false; 
                }
 
                if (joinConditionNode != null)
                {
                    joinConditionNode = trc.ReMap(joinConditionNode, varMap1);
                    joinConditionNode = trc.ReMap(joinConditionNode, varMap2); 
                    newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0, joinConditionNode);
                } 
                else 
                {
                    newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0); 
                }

                newVarSet.InitFrom(projectOp1.Outputs);
                foreach (Var v in projectOp2.Outputs) 
                {
                    newVarSet.Set(v); 
                } 
                ProjectOp newProjectOp = command.CreateProjectOp(newVarSet);
                varDefNodes.AddRange(joinNode.Child0.Child1.Children); 
                varDefNodes.AddRange(joinNode.Child1.Child1.Children);
                Node varDefListNode = command.CreateNode(
                    command.CreateVarDefListOp(),
                    varDefNodes); 
                newProjectNode = command.CreateNode(newProjectOp,
                    newJoinNode, varDefListNode); 
                newNode = newProjectNode; 
                return true;
            } 

            int projectNodeIdx = -1;
            int otherNodeIdx = -1;
            if (joinNode.Child0.Op.OpType == OpType.Project) 
            {
                projectNodeIdx = 0; 
                otherNodeIdx = 1; 
            }
            else 
            {
                PlanCompiler.Assert(joinNode.Op.OpType != OpType.LeftOuterJoin, "unexpected non-LeftOuterJoin");
                projectNodeIdx = 1;
                otherNodeIdx = 0; 
            }
            Node projectNode = joinNode.Children[projectNodeIdx]; 
 
            ProjectOp projectOp = projectNode.Op as ProjectOp;
            Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap); 
            if (varMap == null)
            {
                return false;
            } 
            ExtendedNodeInfo otherChildInfo = command.GetExtendedNodeInfo(joinNode.Children[otherNodeIdx]);
            VarVec vec = command.CreateVarVec(projectOp.Outputs); 
            vec.Or(otherChildInfo.Definitions); 
            projectOp.Outputs.InitFrom(vec);
            if (joinConditionNode != null) 
            {
                joinConditionNode = trc.ReMap(joinConditionNode, varMap);
                joinNode.Child2 = joinConditionNode;
            } 
            joinNode.Children[projectNodeIdx] = projectNode.Child0; // bypass the projectOp
            context.Command.RecomputeNodeInfo(joinNode); 
 
            newNode = context.Command.CreateNode(projectOp, joinNode, projectNode.Child1);
            return true; 
        }
        #endregion

        #region JoinOverFilter 
        internal static readonly PatternMatchRule Rule_CrossJoinOverFilter1 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(LeafOp.Pattern), 
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern))),
                                 ProcessJoinOverFilter);
        internal static readonly PatternMatchRule Rule_CrossJoinOverFilter2 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern), 
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverFilter); 
        internal static readonly PatternMatchRule Rule_InnerJoinOverFilter1 =
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(LeafOp.Pattern),
                                          new Node(FilterOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverFilter);
        internal static readonly PatternMatchRule Rule_InnerJoinOverFilter2 = 
            new PatternMatchRule(new Node(InnerJoinOp.Pattern,
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverFilter); 
        internal static readonly PatternMatchRule Rule_OuterJoinOverFilter2 =
            new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern, 
                                          new Node(FilterOp.Pattern,
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)),
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessJoinOverFilter); 
        ///  
        /// CrossJoin(Filter(A,p), B) => Filter(CrossJoin(A, B), p)
        /// CrossJoin(A, Filter(B,p)) => Filter(CrossJoin(A, B), p) 
        ///
        /// InnerJoin(Filter(A,p), B, c) => Filter(InnerJoin(A, B, c), p)
        /// InnerJoin(A, Filter(B,p), c) => Filter(InnerJoin(A, B, c), p)
        /// 
        /// LeftOuterJoin(Filter(A,p), B, c) => Filter(LeftOuterJoin(A, B, c), p)
        /// 
        /// Note that the predicate on the right table in a left-outer-join cannot be pulled 
        /// up above the join.
        /// 
        /// 
        /// Rule processing context
        /// Current JoinOp tree to process
        /// transformed subtree 
        /// transformation status
        static bool ProcessJoinOverFilter(RuleProcessingContext context, Node joinNode, out Node newNode) 
        { 
            newNode = joinNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            Command command = trc.Command;

            Node predicateNode = null;
            Node newLeftInput = joinNode.Child0; 
            // get the predicate from the first filter
            if (joinNode.Child0.Op.OpType == OpType.Filter) 
            { 
                predicateNode = joinNode.Child0.Child1;
                newLeftInput = joinNode.Child0.Child0; // bypass the filter 
            }

            // get the predicate from the second filter
            Node newRightInput = joinNode.Child1; 
            if (joinNode.Child1.Op.OpType == OpType.Filter && joinNode.Op.OpType != OpType.LeftOuterJoin)
            { 
                if (predicateNode == null) 
                {
                    predicateNode = joinNode.Child1.Child1; 
                }
                else
                {
                    predicateNode = command.CreateNode( 
                        command.CreateConditionalOp(OpType.And),
                        predicateNode, joinNode.Child1.Child1); 
                } 
                newRightInput = joinNode.Child1.Child0; // bypass the filter
            } 

            // No optimizations to perform if we can't locate the appropriate predicate
            if (predicateNode == null)
            { 
                return false;
            } 
 
            //
            // Create a new join node with the new inputs 
            //
            Node newJoinNode;
            if (joinNode.Op.OpType == OpType.CrossJoin)
            { 
                newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput);
            } 
            else 
            {
                newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput, joinNode.Child2); 
            }

            //
            // create a new filterOp with the combined predicates, and with the 
            // newjoinNode as the input
            // 
            FilterOp newFilterOp = command.CreateFilterOp(); 
            newNode = command.CreateNode(newFilterOp, newJoinNode, predicateNode);
 
            //
            // Mark this subtree so that we don't try to push filters down again
            //
            trc.SuppressFilterPushdown(newNode); 
            return true;
        } 
        #endregion 

        #region Join over SingleRowTable 
        internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable1 =
            new PatternMatchRule(new Node(CrossJoinOp.Pattern,
                                          new Node(SingleRowTableOp.Pattern),
                                          new Node(LeafOp.Pattern)), 
                                 ProcessJoinOverSingleRowTable);
        internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable2 = 
            new PatternMatchRule(new Node(CrossJoinOp.Pattern, 
                                          new Node(LeafOp.Pattern),
                                          new Node(SingleRowTableOp.Pattern)), 
                                 ProcessJoinOverSingleRowTable);

        internal static readonly PatternMatchRule Rule_LeftOuterJoinOverSingleRowTable =
           new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern, 
                                         new Node(LeafOp.Pattern),
                                         new Node(SingleRowTableOp.Pattern), 
                                         new Node(LeafOp.Pattern)), 
                                ProcessJoinOverSingleRowTable);
        ///  
        /// Convert a CrossJoin(SingleRowTable, X) or CrossJoin(X, SingleRowTable) or LeftOuterJoin(X, SingleRowTable)
        ///    into just "X"
        /// 
        /// rule processing context 
        /// the join node
        /// transformed subtree 
        /// transformation status 
        static bool ProcessJoinOverSingleRowTable(RuleProcessingContext context, Node joinNode, out Node newNode)
        { 
            newNode = joinNode;

            if (joinNode.Child0.Op.OpType == OpType.SingleRowTable)
            { 
                newNode = joinNode.Child1;
            } 
            else 
            {
                newNode = joinNode.Child0; 
            }
            return true;
        }
        #endregion 

        #region Misc 
        #endregion 

        #region All JoinOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
            Rule_CrossJoinOverProject1,
            Rule_CrossJoinOverProject2,
            Rule_InnerJoinOverProject1, 
            Rule_InnerJoinOverProject2,
            Rule_OuterJoinOverProject2, 
 
            Rule_CrossJoinOverFilter1,
            Rule_CrossJoinOverFilter2, 
            Rule_InnerJoinOverFilter1,
            Rule_InnerJoinOverFilter2,
            Rule_OuterJoinOverFilter2,
 
            Rule_CrossJoinOverSingleRowTable1,
            Rule_CrossJoinOverSingleRowTable2, 
            Rule_LeftOuterJoinOverSingleRowTable, 
        };
 
        #endregion
    }
    #endregion
 
    #region SingleRowOp Rules
    ///  
    /// Rules for SingleRowOp 
    /// 
    internal static class SingleRowOpRules 
    {
        internal static readonly PatternMatchRule Rule_SingleRowOpOverAnything =
            new PatternMatchRule(new Node(SingleRowOp.Pattern,
                                     new Node(LeafOp.Pattern)), 
                                 ProcessSingleRowOpOverAnything);
        ///  
        /// Convert a 
        ///    SingleRowOp(X) => X
        /// if X produces at most one row 
        /// 
        /// Rule Processing context
        /// Current subtree
        /// transformed subtree 
        /// Transformation status
        static bool ProcessSingleRowOpOverAnything(RuleProcessingContext context, Node singleRowNode, out Node newNode) 
        { 
            newNode = singleRowNode;
            TransformationRulesContext trc = (TransformationRulesContext)context; 
            ExtendedNodeInfo childNodeInfo = context.Command.GetExtendedNodeInfo(singleRowNode.Child0);

            // If the input to this Op can produce at most one row, then we don't need the
            // singleRowOp - simply return the input 
            if (childNodeInfo.MaxRows <= RowCount.One)
            { 
                newNode = singleRowNode.Child0; 
                return true;
            } 

            //
            // if the current node is a FilterOp, then try and determine if the FilterOp
            // produces one row at most 
            //
            if (singleRowNode.Child0.Op.OpType == OpType.Filter) 
            { 
                Predicate predicate = new Predicate(context.Command, singleRowNode.Child0.Child1);
                if (predicate.SatisfiesKey(childNodeInfo.Keys.KeyVars, childNodeInfo.Definitions)) 
                {
                    childNodeInfo.MaxRows = RowCount.One;
                    newNode = singleRowNode.Child0;
                    return true; 
                }
            } 
 
            // we couldn't do anything
            return false; 
        }

        internal static readonly PatternMatchRule Rule_SingleRowOpOverProject =
           new PatternMatchRule(new Node(SingleRowOp.Pattern, 
                             new Node(ProjectOp.Pattern,
                                   new Node(LeafOp.Pattern), new Node(LeafOp.Pattern))), 
                         ProcessSingleRowOpOverProject); 
        /// 
        /// Convert 
        ///    SingleRowOp(Project) => Project(SingleRowOp)
        /// 
        /// Rule Processing context
        /// current subtree 
        /// transformeed subtree
        /// transformation status 
        static bool ProcessSingleRowOpOverProject(RuleProcessingContext context, Node singleRowNode, out Node newNode) 
        {
            newNode = singleRowNode; 
            Node projectNode = singleRowNode.Child0;
            Node projectNodeInput = projectNode.Child0;

            // Simply push the SingleRowOp below the ProjectOp 
            singleRowNode.Child0 = projectNodeInput;
            context.Command.RecomputeNodeInfo(singleRowNode); 
            projectNode.Child0 = singleRowNode; 

            newNode = projectNode; 
            return true; // subtree modified internally
        }

        #region All SingleRowOp Rules 
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
            Rule_SingleRowOpOverAnything, 
            Rule_SingleRowOpOverProject, 
        };
        #endregion 
    }
    #endregion

    #region SetOp Rules 
    /// 
    /// SetOp Transformation Rules 
    ///  
    internal static class SetOpRules
    { 
        #region SetOpOverFilters
        internal static readonly SimpleRule Rule_UnionAllOverEmptySet =
            new SimpleRule(OpType.UnionAll, ProcessSetOpOverEmptySet);
        internal static readonly SimpleRule Rule_IntersectOverEmptySet = 
            new SimpleRule(OpType.Intersect, ProcessSetOpOverEmptySet);
        internal static readonly SimpleRule Rule_ExceptOverEmptySet = 
            new SimpleRule(OpType.Except, ProcessSetOpOverEmptySet); 

        ///  
        /// Process a SetOp when one of the inputs is an emptyset.
        ///
        /// An emptyset is represented by a Filter(X, ConstantPredicate)
        ///    where the ConstantPredicate has a value of "false" 
        ///
        /// The general rules are 
        ///    UnionAll(X, EmptySet) => X 
        ///    UnionAll(EmptySet, X) => X
        ///    Intersect(EmptySet, X) => EmptySet 
        ///    Intersect(X, EmptySet) => EmptySet
        ///    Except(EmptySet, X) => EmptySet
        ///    Except(X, EmptySet) => X
        /// 
        /// These rules then translate into
        ///    UnionAll: return the non-empty input 
        ///    Intersect: return the empty input 
        ///    Except: return the "left" input
        ///  
        /// Rule processing context
        /// the current setop tree
        /// Index of the filter node in the setop
        /// transformed subtree 
        /// transformation status
        private static bool ProcessSetOpOverEmptySet(RuleProcessingContext context, Node setOpNode, out Node newNode) 
        { 
            bool leftChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child0).MaxRows == RowCount.Zero;
            bool rightChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child1).MaxRows == RowCount.Zero; 

            if (!leftChildIsEmptySet && !rightChildIsEmptySet)
            {
                newNode = setOpNode; 
                return false;
            } 
 
            int indexToReturn;
            SetOp setOp = (SetOp)setOpNode.Op; 
            if (!rightChildIsEmptySet && setOp.OpType == OpType.UnionAll ||
                !leftChildIsEmptySet && setOp.OpType == OpType.Intersect)
            {
                indexToReturn = 1; 
            }
            else 
            { 
                indexToReturn = 0;
            } 

            newNode = setOpNode.Children[indexToReturn];

            TransformationRulesContext trc = (TransformationRulesContext)context; 
            foreach (KeyValuePair kv in setOp.VarMap[indexToReturn])
            { 
                trc.AddVarMapping(kv.Key, kv.Value); 
            }
            return true; 
        }

        #endregion
 
        #region All SetOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
            Rule_UnionAllOverEmptySet, 
            Rule_IntersectOverEmptySet,
            Rule_ExceptOverEmptySet, 
        };
        #endregion
    }
    #endregion 

    #region GroupByOp Rules 
    ///  
    /// Transformation Rules for GroupByOps
    ///  
    internal static class GroupByOpRules
    {
        #region GroupByOpWithSimpleVarRedefinitions
        internal static readonly SimpleRule Rule_GroupByOpWithSimpleVarRedefinitions = new SimpleRule(OpType.GroupBy, ProcessGroupByWithSimpleVarRedefinitions); 
        /// 
        /// If the GroupByOp defines some computedVars as part of its keys, but those computedVars are simply 
        /// redefinitions of other Vars, then eliminate the computedVars. 
        ///
        /// GroupBy(X, VarDefList(VarDef(cv1, VarRef(v1)), ...), VarDefList(...)) 
        ///    can be transformed into
        /// GroupBy(X, VarDefList(...))
        /// where cv1 has now been replaced by v1
        ///  
        /// Rule processing context
        /// current subtree 
        /// transformed subtree 
        /// transformation status
        static bool ProcessGroupByWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode) 
        {
            newNode = n;
            GroupByOp groupByOp = (GroupByOp)n.Op;
            // no local keys? nothing to do 
            if (n.Child1.Children.Count == 0)
            { 
                return false; 
            }
 
            TransformationRulesContext trc = (TransformationRulesContext)context;
            Command command = trc.Command;

            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n); 

            // 
            // Check to see if any of the computed Vars defined by this GroupByOp 
            // are simple redefinitions of other VarRefOps. Consider only those
            // VarRefOps that are not "external" references 
            //
            bool canEliminateSomeVars = false;
            foreach (Node varDefNode in n.Child1.Children)
            { 
                Node definingExprNode = varDefNode.Child0;
                if (definingExprNode.Op.OpType == OpType.VarRef) 
                { 
                    VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
                    if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var)) 
                    {
                        // this is a Var that we should remove
                        canEliminateSomeVars = true;
                    } 
                }
            } 
 
            // Did we have any redefinitions
            if (!canEliminateSomeVars) 
            {
                return false;
            }
 
            //
            // OK. We've now identified a set of vars that are simple redefinitions. 
            // Try and replace the computed Vars with the Vars that they're redefining 
            //
 
            // Lets now build up a new VarDefListNode
            List newVarDefNodes = new List();
            foreach (Node varDefNode in n.Child1.Children)
            { 
                VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp; 
                if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var)) 
                {
                    groupByOp.Outputs.Clear(varDefOp.Var); 
                    groupByOp.Outputs.Set(varRefOp.Var);
                    groupByOp.Keys.Clear(varDefOp.Var);
                    groupByOp.Keys.Set(varRefOp.Var);
                    trc.AddVarMapping(varDefOp.Var, varRefOp.Var); 
                }
                else 
                { 
                    newVarDefNodes.Add(varDefNode);
                } 
            }

            // Create a new vardeflist node, and set that as Child1 for the group by op
            Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes); 
            n.Child1 = newVarDefListNode;
            return true; // subtree modified 
        } 
        #endregion
 
        #region GroupByOverProject
        internal static readonly PatternMatchRule Rule_GroupByOverProject =
            new PatternMatchRule(new Node(GroupByOp.Pattern,
                                          new Node(ProjectOp.Pattern, 
                                                   new Node(LeafOp.Pattern),
                                                   new Node(LeafOp.Pattern)), 
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern)),
                                 ProcessGroupByOverProject); 
        /// 
        /// Converts a GroupBy(Project(X, c1,..ck), agg1, agg2, .. aggm) =>
        ///            GroupBy(X, agg1', agg2', .. aggm')
        /// where agg1', agg2', .. aggm'  are the "mapped" versions 
        /// of agg1, agg2, .. aggm, such that the references to c1, ... ck are
        /// replaced by their definitions. 
        /// 
        /// We only do this if each c1, ..ck is refereneced (in aggregates) at most once or it is a constant.
        ///  
        /// Rule processing context
        /// Current ProjectOp node
        /// modified subtree
        /// Transformation status 
        static bool ProcessGroupByOverProject(RuleProcessingContext context, Node n, out Node newNode)
        { 
            newNode = n; 
            GroupByOp op = (GroupByOp)n.Op;
            Command command = ((TransformationRulesContext)context).Command; 
            Node projectNode = n.Child0;
            Node projectNodeVarDefList = projectNode.Child1;

            Node keys = n.Child1; 
            Node aggregates = n.Child2;
 
            // If there are any keys, we should not remove the inner project 
            if (keys.Children.Count > 0)
            { 
                return false;
            }

            //Get a list of all defining vars 
            VarVec projectDefinitions = command.GetExtendedNodeInfo(projectNode).LocalDefinitions;
 
            //If any of the defined vars is output, than we need the extra project anyway. 
            if (op.Outputs.Overlaps(projectDefinitions))
            { 
                return false;
            }

            bool createdNewProjectDefinitions = false; 

            //If there are any constants remove them from the list that needs to be tested, 
            //These can safely be replaced 
            for (int i = 0; i < projectNodeVarDefList.Children.Count; i++)
            { 
                Node varDefNode = projectNodeVarDefList.Children[i];
                if (varDefNode.Child0.Op.OpType == OpType.Constant || varDefNode.Child0.Op.OpType == OpType.InternalConstant || varDefNode.Child0.Op.OpType == OpType.NullSentinel)
                {
                    //We shouldn't modify the original project definitions, thus we copy it 
                    // the first time we encounter a constant
                    if (!createdNewProjectDefinitions) 
                    { 
                        projectDefinitions = command.CreateVarVec(projectDefinitions);
                        createdNewProjectDefinitions = true; 
                    }
                    projectDefinitions.Clear(((VarDefOp)varDefNode.Op).Var);
                }
            } 

            if (VarRefUsageFinder.AnyVarUsedMoreThanOnce(projectDefinitions, aggregates, command)) 
            { 
                return false;
            } 

            //If we got here it means that all vars were either constants, or used at most once
            // Create a dictionary to be used for remapping the keys and the aggregates
            Dictionary varToDefiningNode = new Dictionary(projectNodeVarDefList.Children.Count); 
            for (int j = 0; j < projectNodeVarDefList.Children.Count; j++)
            { 
                Node varDefNode = projectNodeVarDefList.Children[j]; 
                Var var = ((VarDefOp)varDefNode.Op).Var;
                varToDefiningNode.Add(var, varDefNode.Child0); 
            }

            newNode.Child2 = VarRefReplacer.Replace(varToDefiningNode, aggregates, command);
 
            newNode.Child0 = projectNode.Child0;
            return true; 
        } 

        ///  
        /// Replaces each occurance of the given vars with their definitions.
        /// 
        internal class VarRefReplacer : BasicOpVisitorOfNode
        { 
            private Dictionary m_varReplacementTable;
            private Command m_command; 
 
            private VarRefReplacer(Dictionary varReplacementTable, Command command)
            { 
                this.m_varReplacementTable = varReplacementTable;
                this.m_command = command;
            }
 
            /// 
            /// "Public" entry point. In the subtree rooted at the given root, 
            /// replace each occurance of the given vars with their definitions, 
            /// where each key-value pair in the dictionary is a var-definition pair.
            ///  
            /// 
            /// 
            /// 
            ///  
            internal static Node Replace(Dictionary varReplacementTable, Node root, Command command)
            { 
                VarRefReplacer replacer = new VarRefReplacer(varReplacementTable, command); 
                return replacer.VisitNode(root);
            } 

            public override Node Visit(VarRefOp op, Node n)
            {
                Node replacementNode; 
                if (m_varReplacementTable.TryGetValue(op.Var, out replacementNode))
                { 
                    return replacementNode; 
                }
                else 
                {
                    return n;
                }
            } 

            ///  
            /// Recomputes node info post regular processing. 
            /// 
            ///  
            /// 
            protected override Node VisitDefault(Node n)
            {
                Node result = base.VisitDefault(n); 
                m_command.RecomputeNodeInfo(result);
                return result; 
            } 
        }
 
        /// 
        /// Used to determine whether any of the given vars occurs more than once
        /// in a given subtree.
        ///  
        internal class VarRefUsageFinder : BasicOpVisitor
        { 
            private bool m_anyUsedMoreThenOnce = false; 
            private VarVec m_varVec;
            private VarVec m_usedVars; 

            private VarRefUsageFinder(VarVec varVec, Command command)
            {
                this.m_varVec = varVec; 
                this.m_usedVars = command.CreateVarVec();
            } 
 
            /// 
            /// Public entry point. Returns true if at least one of the given vars occurs more than 
            /// once in the subree rooted at the given root.
            /// 
            /// 
            ///  
            /// 
            ///  
            internal static bool AnyVarUsedMoreThanOnce(VarVec varVec, Node root, Command command) 
            {
                VarRefUsageFinder usageFinder = new VarRefUsageFinder(varVec, command); 
                usageFinder.VisitNode(root);
                return usageFinder.m_anyUsedMoreThenOnce;
            }
 
            public override void Visit(VarRefOp op, Node n)
            { 
                Var referencedVar = op.Var; 
                if (m_varVec.IsSet(referencedVar))
                { 
                    if (m_usedVars.IsSet(referencedVar))
                    {
                        this.m_anyUsedMoreThenOnce = true;
                    } 
                    else
                    { 
                        m_usedVars.Set(referencedVar); 
                    }
                } 
            }

            protected override void VisitChildren(Node n)
            { 
                //small optimization: no need to continue if we have the answer
                if (m_anyUsedMoreThenOnce) 
                { 
                    return;
                } 
                base.VisitChildren(n);
            }
        }
        #endregion 

        #region GroupByOpWithNoAggregates 
        internal static readonly PatternMatchRule Rule_GroupByOpWithNoAggregates = 
            new PatternMatchRule(new Node(GroupByOp.Pattern,
                                          new Node(LeafOp.Pattern), 
                                          new Node(LeafOp.Pattern),
                                          new Node(VarDefListOp.Pattern)),
                                 ProcessGroupByOpWithNoAggregates);
        ///  
        /// If the GroupByOp has no aggregates:
        /// 
        /// (1) and if it includes all all the keys of the input, than it is unnecessary 
        /// GroupBy (X, keys) -> Project(X, keys) where keys includes all keys of X.
        /// 
        /// (2) else it can be turned into a Distinct:
        /// GroupBy (X, keys) -> Distinct(X, keys)
        ///
        ///  
        /// Rule processing context
        /// current subtree 
        /// transformed subtree 
        /// transformation status
        static bool ProcessGroupByOpWithNoAggregates(RuleProcessingContext context, Node n, out Node newNode) 
        {
            Command command = context.Command;
            GroupByOp op = (GroupByOp)n.Op;
 
            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
            ProjectOp newOp = command.CreateProjectOp(op.Keys); 
 
            VarDefListOp varDefListOp = command.CreateVarDefListOp();
            Node varDefListNode = command.CreateNode(varDefListOp); 

            newNode = command.CreateNode(newOp, n.Child0, n.Child1);

            //If we know the keys of the input and the list of keys includes them all, 
            // this is the result, otherwise add distinct
            if (nodeInfo.Keys.NoKeys || !op.Keys.Subsumes(nodeInfo.Keys.KeyVars)) 
            { 
                newNode = command.CreateNode(command.CreateDistinctOp(command.CreateVarVec(op.Keys)), newNode);
            } 
            return true;
        }
        #endregion
 
        #region All GroupByOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions, 
                 GroupByOpRules.Rule_GroupByOverProject,
                 GroupByOpRules.Rule_GroupByOpWithNoAggregates, 
        };
        #endregion
    }
    #endregion 

    #region Sorting Rules 
    ///  
    /// Transformation Rules for SortOp
    ///  
    internal static class SortOpRules
    {
        #region SortOpOverAtMostOneRow
        internal static readonly SimpleRule Rule_SortOpOverAtMostOneRow = new SimpleRule(OpType.Sort, ProcessSortOpOverAtMostOneRow); 
        /// 
        /// If the SortOp's input is guaranteed to produce at most 1 row, remove the node with the SortOp: 
        ///  Sort(X) => X, if X is guaranteed to produce no more than 1 row 
        /// 
        /// Rule processing context 
        /// current subtree
        /// transformed subtree
        /// transformation status
        static bool ProcessSortOpOverAtMostOneRow(RuleProcessingContext context, Node n, out Node newNode) 
        {
            ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0); 
 
            //If the input has at most one row, omit the SortOp
            if (nodeInfo.MaxRows == RowCount.Zero || nodeInfo.MaxRows == RowCount.One) 
            {
                newNode = n.Child0;
                return true;
            } 

            //Otherwise return the node as is 
            newNode = n; 
            return false;
        } 
        #endregion

        #region All SortOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 SortOpRules.Rule_SortOpOverAtMostOneRow,
        }; 
        #endregion 
    }
 
    /// 
    /// Transformation Rules for ConstrainedSortOp
    /// 
    internal static class ConstrainedSortOpRules 
    {
        #region ConstrainedSortOpOverEmptySet 
        internal static readonly SimpleRule Rule_ConstrainedSortOpOverEmptySet = new SimpleRule(OpType.ConstrainedSort, ProcessConstrainedSortOpOverEmptySet); 
        /// 
        /// If the ConstrainedSortOp's input is guaranteed to produce no rows, remove the ConstrainedSortOp completly: 
        ///    CSort(EmptySet) => EmptySet
        /// 
        /// Rule processing context
        /// current subtree 
        /// transformed subtree
        /// transformation status 
        static bool ProcessConstrainedSortOpOverEmptySet(RuleProcessingContext context, Node n, out Node newNode) 
        {
            ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0); 

            //If the input has no rows, remove the ConstraintSortOp node completly
            if (nodeInfo.MaxRows == RowCount.Zero)
            { 
                newNode = n.Child0;
                return true; 
            } 

            newNode = n; 
            return false;
        }
        #endregion
 
        #region All ConstrainedSortOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] { 
                 ConstrainedSortOpRules.Rule_ConstrainedSortOpOverEmptySet, 
        };
        #endregion 
    }
    #endregion

    #region DistinctOp Rules 
    /// 
    /// Transformation Rules for DistinctOp 
    ///  
    internal static class DistinctOpRules
    { 
        #region DistinctOpOfKeys
        internal static readonly SimpleRule Rule_DistinctOpOfKeys = new SimpleRule(OpType.Distinct, ProcessDistinctOpOfKeys);
        /// 
        /// If the DistinctOp includes all all the keys of the input, than it is unnecessary. 
        /// Distinct (X, distinct_keys) -> Project( X, distinct_keys) where distinct_keys includes all keys of X.
        ///  
        /// Rule processing context 
        /// current subtree
        /// transformed subtree 
        /// transformation status
        static bool ProcessDistinctOpOfKeys(RuleProcessingContext context, Node n, out Node newNode)
        {
            Command command = context.Command; 

            ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0); 
 
            DistinctOp op = (DistinctOp)n.Op;
 
            //If we know the keys of the input and the list of distinct keys includes them all, omit the distinct
            if (!nodeInfo.Keys.NoKeys && op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
            {
                ProjectOp newOp = command.CreateProjectOp(op.Keys); 

                //Create empty vardef list 
                VarDefListOp varDefListOp = command.CreateVarDefListOp(); 
                Node varDefListNode = command.CreateNode(varDefListOp);
 
                newNode = command.CreateNode(newOp, n.Child0, varDefListNode);
                return true;
            }
 
            //Otherwise return the node as is
            newNode = n; 
            return false; 
        }
        #endregion 

        #region All DistinctOp Rules
        internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
                 DistinctOpRules.Rule_DistinctOpOfKeys, 
        };
        #endregion 
    } 
    #endregion
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK