AggregatePushdown.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 / AggregatePushdown.cs / 1305376 / AggregatePushdown.cs

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

using System; 
using System.Collections.Generic;
using System.Data.Common;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization; 
using System.Text;
 
using System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees;
 
namespace System.Data.Query.PlanCompiler
{
    internal delegate bool TryGetValue(Node key, out Node value);
 
    #region Helper Classes
    ///  
    /// Helper class to track the aggregate nodes that are candidates to be 
    /// pushed into the definingGroupByNode.
    ///  
    internal class GroupAggregateVarInfo
    {
        #region Private Fields
        private readonly Node _definingGroupByNode; 
        private HashSet> _candidateAggregateNodes;
        private readonly Var _groupAggregateVar; 
        #endregion 

        #region Constructor 
        /// 
        /// Public constructor
        /// 
        /// The GroupIntoOp node 
        /// 
        internal GroupAggregateVarInfo(Node defingingGroupNode, Var groupAggregateVar) 
        { 
            _definingGroupByNode = defingingGroupNode;
            _groupAggregateVar = groupAggregateVar; 
        }
        #endregion

        #region 'Public' Properties 
        /// 
        /// Each key value pair represents a candidate aggregate. 
        /// The key is the function aggregate subtree and the value is a 'template' of translation of the 
        /// function aggregate's argument over the var representing the group aggregate.
        /// A valid candidate has an argument that does not have any external references 
        /// except for the group aggregate corresponding to the DefiningGroupNode.
        /// 
        internal HashSet> CandidateAggregateNodes
        { 
            get
            { 
                if (_candidateAggregateNodes == null) 
                {
                    _candidateAggregateNodes = new HashSet>(); 
                }
                return _candidateAggregateNodes;
            }
        } 

        ///  
        /// Are there are agregates that are candidates to be pushed into the DefiningGroupNode 
        /// 
        internal bool HasCandidateAggregateNodes 
        {
            get
            {
                return (_candidateAggregateNodes != null && _candidateAggregateNodes.Count != 0); 
            }
        } 
 
        /// 
        /// The GroupIntoOp node that this GroupAggregateVarInfo represents 
        /// 
        internal Node DefiningGroupNode
        {
            get { return _definingGroupByNode; } 
        }
 
        internal Var GroupAggregateVar 
        {
            get { return _groupAggregateVar; } 
        }
        #endregion
    }
 
    /// 
    /// Helper class to track usage of GroupAggregateVarInfo 
    /// It represents the usage of a single GroupAggregateVar. 
    /// The usage is defined by the computation, it should be a subree whose only
    /// external reference is the group var represented by the GroupAggregateVarInfo. 
    /// 
    internal class GroupAggregateVarRefInfo
    {
        #region Private fields 
        private readonly Node _computation;
        private readonly GroupAggregateVarInfo _groupAggregateVarInfo; 
        private readonly bool _isUnnested; 
        #endregion
 
        #region Constructor
        /// 
        /// Public constructor
        ///  
        /// 
        ///  
        internal GroupAggregateVarRefInfo(GroupAggregateVarInfo groupAggregateVarInfo, Node computation, bool isUnnested) 
        {
            this._groupAggregateVarInfo = groupAggregateVarInfo; 
            this._computation = computation;
            this._isUnnested = isUnnested;
        }
 
        #endregion
 
        #region 'Public' Properties 
        /// 
        /// Subtree whose only external reference is 
        /// the group var represented by the GroupAggregateVarInfo
        /// 
        internal Node Computation
        { 
            get { return _computation; }
        } 
 
        /// 
        /// The GroupAggregateVarInfo (possibly) referenced by the computation 
        /// 
        internal GroupAggregateVarInfo GroupAggregateVarInfo
        {
            get { return _groupAggregateVarInfo; } 
        }
 
        ///  
        /// Is the computation over unnested group aggregate var
        ///  
        internal bool IsUnnested
        {
            get { return _isUnnested; }
        } 
        #endregion
    } 
 
    /// 
    /// Manages refereces to groupAggregate variables. 
    /// 
    internal class GroupAggregateVarInfoManager
    {
        #region Private state 
        private readonly Dictionary _groupAggregateVarRelatedVarToInfo = new Dictionary();
        private Dictionary> _groupAggregateVarRelatedVarPropertyToInfo; 
        private HashSet _groupAggregateVarInfos = new HashSet(); 
        #endregion
 
        #region Public Surface
        /// 
        /// Get all the groupAggregateVarInfos
        ///  
        internal IEnumerable GroupAggregateVarInfos
        { 
            get 
            {
                return _groupAggregateVarInfos; 
            }
        }

        ///  
        /// Add an entry that var is a computation represented by the computationTemplate
        /// over the var represented by the given groupAggregateVarInfo 
        ///  
        /// 
        ///  
        /// 
        /// 
        internal void Add(Var var, GroupAggregateVarInfo groupAggregateVarInfo, Node computationTemplate, bool isUnnested)
        { 
            this._groupAggregateVarRelatedVarToInfo.Add(var, new GroupAggregateVarRefInfo(groupAggregateVarInfo, computationTemplate, isUnnested));
            _groupAggregateVarInfos.Add(groupAggregateVarInfo); 
        } 

        ///  
        /// Add an entry that the given property of the given var is a computation represented
        /// by the computationTemplate over the var represented by the given groupAggregateVarInfo
        /// 
        ///  
        /// 
        ///  
        ///  
        /// 
        internal void Add(Var var, GroupAggregateVarInfo groupAggregateVarInfo, Node computationTemplate, bool isUnnested, EdmMember property) 
        {
            if (property == null)
            {
                Add(var, groupAggregateVarInfo, computationTemplate, isUnnested); 
                return;
            } 
            if (this._groupAggregateVarRelatedVarPropertyToInfo == null) 
            {
                this._groupAggregateVarRelatedVarPropertyToInfo = new Dictionary>(); 
            }
            Dictionary varPropertyDictionary;
            if (!_groupAggregateVarRelatedVarPropertyToInfo.TryGetValue(var, out varPropertyDictionary))
            { 
                varPropertyDictionary = new Dictionary();
                _groupAggregateVarRelatedVarPropertyToInfo.Add(var, varPropertyDictionary); 
            } 
            varPropertyDictionary.Add(property, new GroupAggregateVarRefInfo(groupAggregateVarInfo, computationTemplate, isUnnested));
 
            // Note: The following line is not necessary with the current usage pattern, this method is
            // never called with a new groupAggregateVarInfo thus it is a no-op.
            _groupAggregateVarInfos.Add(groupAggregateVarInfo);
        } 

        ///  
        /// Gets the groupAggregateVarRefInfo representing the definition of the given var over 
        /// a group aggregate var if any.
        ///  
        /// 
        /// 
        /// 
        internal bool TryGetReferencedGroupAggregateVarInfo(Var var, out GroupAggregateVarRefInfo groupAggregateVarRefInfo) 
        {
            return this._groupAggregateVarRelatedVarToInfo.TryGetValue(var, out groupAggregateVarRefInfo); 
        } 

        ///  
        /// Gets the groupAggregateVarRefInfo representing the definition of the given property of the given
        /// var over a group aggregate var if any.
        /// 
        ///  
        /// 
        ///  
        ///  
        internal bool TryGetReferencedGroupAggregateVarInfo(Var var, EdmMember property, out GroupAggregateVarRefInfo groupAggregateVarRefInfo)
        { 
            if (property == null)
            {
                return TryGetReferencedGroupAggregateVarInfo(var, out groupAggregateVarRefInfo);
            } 

            Dictionary varPropertyDictionary; 
            if (_groupAggregateVarRelatedVarPropertyToInfo == null || !_groupAggregateVarRelatedVarPropertyToInfo.TryGetValue(var, out varPropertyDictionary)) 
            {
                groupAggregateVarRefInfo = null; 
                return false;
            }
            return varPropertyDictionary.TryGetValue(property, out groupAggregateVarRefInfo);
        } 
        #endregion
    } 
    #endregion 

    ///  
    /// Utility class that tries to produce an equivalent tree to the input tree over
    /// a single group aggregate variable and no other external references
    /// 
    internal class GroupAggregateVarComputationTranslator : BasicOpVisitorOfNode 
    {
        #region Private State 
        private GroupAggregateVarInfo _targetGroupAggregateVarInfo; 
        private bool _isUnnested;
        private readonly Command _command; 
        private readonly GroupAggregateVarInfoManager _groupAggregateVarInfoManager;
        #endregion

        #region Constructor 
        /// 
        /// Private constructor 
        ///  
        /// 
        ///  
        private GroupAggregateVarComputationTranslator(
            Command command,
            GroupAggregateVarInfoManager groupAggregateVarInfoManager)
        { 
            this._command = command;
            this._groupAggregateVarInfoManager = groupAggregateVarInfoManager; 
        } 
        #endregion
 
        #region 'Public' Surface
        /// 
        /// Try to produce an equivalent tree to the input subtree, over a single group aggregate variable.
        /// Such translation can only be produced if all external references of the input subtree are to a 
        /// single group aggregate var, or to vars that are can be translated over that single group
        /// aggregate var 
        ///  
        /// The input subtree
        ///  
        /// 
        /// 
        /// The groupAggregateVarInfo over which the input subtree can be translated 
        /// A tree that is equvalent to the input tree, but over the group aggregate variable 
        /// represented by the groupAggregetVarInfo
        ///  
        /// True, if the translation can be done, false otherwise 
        public static bool TryTranslateOverGroupAggregateVar(
            Node subtree, 
            bool isVarDefinition,
            Command command,
            GroupAggregateVarInfoManager groupAggregateVarInfoManager,
            out GroupAggregateVarInfo groupAggregateVarInfo, 
            out Node templateNode,
            out bool isUnnested) 
        { 
            GroupAggregateVarComputationTranslator handler = new GroupAggregateVarComputationTranslator(command, groupAggregateVarInfoManager);
 
            Node inputNode = subtree;
            SoftCastOp softCastOp = null;
            bool isCollect;
            if (inputNode.Op.OpType == OpType.SoftCast) 
            {
                softCastOp = (SoftCastOp)inputNode.Op; 
                inputNode = inputNode.Child0; 
            }
 
            if (inputNode.Op.OpType == OpType.Collect)
            {
                templateNode = handler.VisitCollect(inputNode);
                isCollect = true; 
            }
            else 
            { 
                templateNode = handler.VisitNode(inputNode);
                isCollect = false; 
            }

            groupAggregateVarInfo = handler._targetGroupAggregateVarInfo;
            isUnnested = handler._isUnnested; 

            if (handler._targetGroupAggregateVarInfo == null || templateNode == null) 
            { 
                return false;
            } 
            if (softCastOp != null)
            {
                SoftCastOp newSoftCastOp;
                // 
                // The type needs to be fixed only if the unnesting happened during this translation.
                // That can be recognized by these two cases: 
                //      1) if the input node was a collect, or 
                //      2) if the input did not represent a var definition, but a function aggregate argument and
                //              the template is VarRef of a group aggregate var. 
                //
                if (isCollect || !isVarDefinition && AggregatePushdownUtil.IsVarRefOverGivenVar(templateNode, handler._targetGroupAggregateVarInfo.GroupAggregateVar))
                {
                    newSoftCastOp = command.CreateSoftCastOp(TypeHelpers.GetEdmType(softCastOp.Type).TypeUsage); 
                }
                else 
                { 
                    newSoftCastOp = softCastOp;
                } 
                templateNode = command.CreateNode(newSoftCastOp, templateNode);
            }
            return true;
        } 
        #endregion
 
        #region Visitor Methods 
        /// 
        /// See  
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(VarRefOp op, Node n)
        { 
            return TranslateOverGroupAggregateVar(op.Var, null); 
        }
 
        /// 
        /// If the child is VarRef check if the subtree PropertyOp(VarRef) is reference to a
        /// group aggregate var.
        /// Otherwise do default processing 
        /// 
        ///  
        ///  
        /// 
        public override Node Visit(PropertyOp op, Node n) 
        {
            if (n.Child0.Op.OpType != OpType.VarRef)
            {
                return base.Visit(op, n); 
            }
            VarRefOp varRefOp = (VarRefOp)n.Child0.Op; 
            return TranslateOverGroupAggregateVar(varRefOp.Var, op.PropertyInfo); 
        }
 
        /// 
        /// If the Subtree rooted at the collect is of the following structure:
        ///
        /// PhysicalProject(outputVar) 
        /// |
        /// Project(s) 
        /// | 
        /// Unnest
        /// 
        /// where the unnest is over  the group aggregate var and the output var
        /// is either a reference to the group aggregate var or to a constant, it returns the
        /// translation of the ouput var.
        ///  
        /// 
        ///  
        private Node VisitCollect(Node n) 
        {
            //Make sure the only children are projects over unnest 
            Node currentNode = n.Child0;
            Dictionary constantDefinitions = new Dictionary();
            while (currentNode.Child0.Op.OpType == OpType.Project)
            { 
                currentNode = currentNode.Child0;
                //Visit the VarDefListOp child 
                if (VisitDefault(currentNode.Child1) == null) 
                {
                    return null; 
                }
                foreach (Node definitionNode in currentNode.Child1.Children)
                {
                    if (IsConstant(definitionNode.Child0)) 
                    {
                        constantDefinitions.Add(((VarDefOp)definitionNode.Op).Var, definitionNode.Child0); 
                    } 
                }
            } 

            if (currentNode.Child0.Op.OpType != OpType.Unnest)
            {
                return null; 
            }
 
            // Handle the unnest 
            UnnestOp unnestOp = (UnnestOp)currentNode.Child0.Op;
            GroupAggregateVarRefInfo groupAggregateVarRefInfo; 
            if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(unnestOp.Var, out groupAggregateVarRefInfo))
            {
                if (_targetGroupAggregateVarInfo == null)
                { 
                    _targetGroupAggregateVarInfo = groupAggregateVarRefInfo.GroupAggregateVarInfo;
                } 
                else if (_targetGroupAggregateVarInfo != groupAggregateVarRefInfo.GroupAggregateVarInfo) 
                {
                    return null; 
                }
                if (!_isUnnested)
                {
                    return null; 
                }
            } 
            else 
            {
                return null; 
            }

            PhysicalProjectOp physicalProjectOp = (PhysicalProjectOp)n.Child0.Op;
            PlanCompiler.Assert(physicalProjectOp.Outputs.Count == 1, "PhysicalProject should only have one output at this stage"); 
            Var outputVar = physicalProjectOp.Outputs[0];
 
            Node computationTemplate = TranslateOverGroupAggregateVar(outputVar, null); 
            if (computationTemplate != null)
            { 
                _isUnnested = true;
                return computationTemplate;
            }
 
            Node constantDefinitionNode;
            if (constantDefinitions.TryGetValue(outputVar, out constantDefinitionNode)) 
            { 
                _isUnnested = true;
                return constantDefinitionNode; 
            }
            return null;
        }
 
        /// 
        /// Determines whether the given Node is a constant subtree 
        /// It only recognizes any of the constant base ops 
        /// and possibly casts over these nodes.
        ///  
        /// 
        /// 
        private static bool IsConstant(Node node)
        { 
            Node currentNode = node;
            while (currentNode.Op.OpType == OpType.Cast) 
            { 
                currentNode = currentNode.Child0;
            } 
            return PlanCompilerUtil.IsConstantBaseOp(currentNode.Op.OpType);
        }

        ///  
        /// (1) If the given var or the given property of the given var are defined over a group aggregate var,
        /// (2) and if that group aggregate var matches the var represented by represented by _targetGroupAggregateVarInfo 
        /// if any 
        ///
        /// it returns the corresponding translation over the group aggregate var. Also, if _targetGroupAggregateVarInfo 
        /// is not set, it sets it to the group aggregate var representing the referenced var.
        /// 
        /// 
        ///  
        /// 
        private Node TranslateOverGroupAggregateVar(Var var, EdmMember property) 
        { 
            GroupAggregateVarRefInfo groupAggregateVarRefInfo;
            EdmMember localProperty; 
            if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(var, out groupAggregateVarRefInfo))
            {
                localProperty = property;
            } 
            else if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(var, property, out  groupAggregateVarRefInfo))
            { 
                localProperty = null; 
            }
            else 
            {
                return null;
            }
 
            if (_targetGroupAggregateVarInfo == null)
            { 
                _targetGroupAggregateVarInfo = groupAggregateVarRefInfo.GroupAggregateVarInfo; 
                _isUnnested = groupAggregateVarRefInfo.IsUnnested;
            } 
            else if (_targetGroupAggregateVarInfo != groupAggregateVarRefInfo.GroupAggregateVarInfo || _isUnnested != groupAggregateVarRefInfo.IsUnnested)
            {
                return null;
            } 

            Node computationTemplate = groupAggregateVarRefInfo.Computation; 
            if (localProperty != null) 
            {
                computationTemplate = this._command.CreateNode(this._command.CreatePropertyOp(localProperty), computationTemplate); 
            }
            return computationTemplate;
        }
 
        /// 
        /// Default processing for nodes. 
        /// Visits the children and if any child has changed it creates a new node 
        /// for the parent.
        /// If the reference of the child node did not change, the child node did not change either, 
        /// this is because a node can only be reused "as is" when building a template.
        /// 
        /// 
        ///  
        protected override Node VisitDefault(Node n)
        { 
            List newChildren = new List(n.Children.Count); 
            bool anyChildChanged = false;
            for (int i = 0; i < n.Children.Count; i++) 
            {
                Node processedChild = VisitNode(n.Children[i]);
                if (processedChild == null)
                { 
                    return null;
                } 
                if (!anyChildChanged && !Object.ReferenceEquals(n.Children[i], processedChild)) 
                {
                    anyChildChanged = true; 
                }
                newChildren.Add(processedChild);
            }
 
            if (!anyChildChanged)
            { 
                return n; 
            }
            else 
            {
                return _command.CreateNode(n.Op, newChildren);
            }
        } 

        #region Unsupported node types 
 
        protected override Node VisitRelOpDefault(RelOp op, Node n)
        { 
            return null;
        }

        public override Node Visit(AggregateOp op, Node n) 
        {
            return null; 
        } 

        public override Node Visit(CollectOp op, Node n) 
        {
            return null;
        }
 
        public override Node Visit(ElementOp op, Node n)
        { 
            return null; 
        }
 
        #endregion

        #endregion
    } 

    ///  
    /// A visitor that collects all group aggregates and the corresponding function aggregates 
    /// that are defined over them, referred to as 'candidate aggregates'. The candidate aggregates are aggregates
    /// that have an argument that has the corresponding group aggregate as the only external reference 
    /// 
    internal class GroupAggregateRefComputingVisitor : BasicOpVisitor
    {
        #region private state 
        private readonly Command _command;
        private readonly GroupAggregateVarInfoManager _groupAggregateVarInfoManager = new GroupAggregateVarInfoManager(); 
        private readonly Dictionary _childToParent = new Dictionary(); 
        #endregion
 
        #region 'Public'
        /// 
        /// Produces a list of all GroupAggregateVarInfos, each of which represents a single group aggregate
        /// and it candidate function aggregates. It also produces a delegate that given a child node returns the parent node 
        /// 
        ///  
        ///  
        /// 
        internal static IEnumerable Process(Command itree, out TryGetValue tryGetParent) 
        {
            GroupAggregateRefComputingVisitor groupRefComputingVisitor = new GroupAggregateRefComputingVisitor(itree);
            groupRefComputingVisitor.VisitNode(itree.Root);
            tryGetParent = groupRefComputingVisitor._childToParent.TryGetValue; 

            return groupRefComputingVisitor._groupAggregateVarInfoManager.GroupAggregateVarInfos; 
        } 
        #endregion
 
        #region Private Constructor
        /// 
        /// Private constructor
        ///  
        /// 
        private GroupAggregateRefComputingVisitor(Command itree) 
        { 
            this._command = itree;
        } 
        #endregion

        #region Visitor Methods
 
        #region AncillaryOps
        ///  
        /// Determines whether the var or a property of the var (if the var is defined as a NewRecord) 
        /// is defined exclusively over a single group aggregate. If so, it registers it as such with the
        /// group aggregate var info manager. 
        /// 
        /// 
        /// 
        public override void Visit(VarDefOp op, Node n) 
        {
            VisitDefault(n); 
 
            Node definingNode = n.Child0;
            Op definingNodeOp = definingNode.Op; 

            GroupAggregateVarInfo referencedVarInfo;
            Node templateNode;
            bool isUnnested; 
            if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(definingNode, true, this._command, this._groupAggregateVarInfoManager, out  referencedVarInfo, out templateNode, out isUnnested))
            { 
                _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested); 
            }
            else if (definingNodeOp.OpType == OpType.NewRecord) 
            {
                NewRecordOp newRecordOp = (NewRecordOp)definingNodeOp;
                for (int i = 0; i < definingNode.Children.Count; i++)
                { 
                    Node argumentNode = definingNode.Children[i];
                    if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(argumentNode, true, this._command, this._groupAggregateVarInfoManager, out referencedVarInfo, out templateNode, out isUnnested)) 
                    { 
                        _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested, newRecordOp.Properties[i]);
                    } 
                }
            }
        }
 
        #endregion
 
        #region RelOp Visitors 
        /// 
        /// Registers the group aggregate var with the group aggregate var info manager 
        /// 
        /// 
        /// 
        public override void Visit(GroupByIntoOp op, Node n) 
        {
            VisitGroupByOp(op, n); 
            foreach (Node child in n.Child3.Children) 
            {
                Var groupAggregateVar = ((VarDefOp)child.Op).Var; 
                GroupAggregateVarRefInfo groupAggregateVarRefInfo;
                // If the group by is over a group, it may be already tracked as referencing a group var
                // An optimization would be to separately track this groupAggregateVar too, for the cases when the aggregate can
                // not be pushed to the group by node over which this one is defined but can be propagated to this group by node. 
                if (!_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(groupAggregateVar, out groupAggregateVarRefInfo))
                { 
                    _groupAggregateVarInfoManager.Add(groupAggregateVar, new GroupAggregateVarInfo(n, groupAggregateVar), this._command.CreateNode(this._command.CreateVarRefOp(groupAggregateVar)), false); 
                }
            } 
        }

        /// 
        /// If the unnestOp's var is defined as a reference of a group aggregate var, 
        /// then the columns it produces should be registered too, but as 'unnested' references
        ///  
        /// the unnestOp 
        /// current subtree
        /// modified subtree 
        public override void Visit(UnnestOp op, Node n)
        {
            VisitDefault(n);
            GroupAggregateVarRefInfo groupAggregateVarRefInfo; 
            if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(op.Var, out groupAggregateVarRefInfo))
            { 
                PlanCompiler.Assert(op.Table.Columns.Count == 1, "Expected one column before NTE"); 
                _groupAggregateVarInfoManager.Add(op.Table.Columns[0], groupAggregateVarRefInfo.GroupAggregateVarInfo, groupAggregateVarRefInfo.Computation, true);
            } 
        }

        #endregion
 
        #region ScalarOps Visitors
        ///  
        /// If the op is a collection aggregate function it checks whether its arguement can be translated over 
        /// a single group aggregate var. If so, it is tracked as a candidate to be pushed into that
        /// group by into node. 
        /// 
        /// 
        /// 
        public override void Visit(FunctionOp op, Node n) 
        {
            VisitDefault(n); 
            if (!PlanCompilerUtil.IsCollectionAggregateFunction(op, n)) 
            {
                return; 
            }
            PlanCompiler.Assert(n.Children.Count == 1, "Aggregate Function must have one argument");

            Node argumentNode = n.Child0; 

            GroupAggregateVarInfo referencedGroupAggregateVarInfo; 
            Node templateNode; 
            bool isUnnested;
            if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(n.Child0, false, _command, _groupAggregateVarInfoManager, out referencedGroupAggregateVarInfo, out templateNode, out isUnnested) 
                && (isUnnested || AggregatePushdownUtil.IsVarRefOverGivenVar(templateNode, referencedGroupAggregateVarInfo.GroupAggregateVar)))
            {
                referencedGroupAggregateVarInfo.CandidateAggregateNodes.Add(new KeyValuePair(n, templateNode));
            } 
        }
 
        #endregion 

        ///  
        /// Default visitor for nodes.
        /// It tracks the child-parent relationship.
        /// 
        ///  
        protected override void VisitDefault(Node n)
        { 
            VisitChildren(n); 
            foreach (Node child in n.Children)
            { 
                //No need to track terminal nodes, plus some of these may be reused.
                if (child.Op.Arity != 0)
                {
                    _childToParent.Add(child, n); 
                }
            } 
        } 
        #endregion
 
    }

    /// 
    /// Utility class to gather helper methods used by more than one class in the Aggregate Pushdown feature. 
    /// 
    internal static class AggregatePushdownUtil 
    { 
        /// 
        /// Determines whether the given node is a VarRef over the given var 
        /// 
        /// 
        /// 
        ///  
        internal static bool IsVarRefOverGivenVar(Node node, Var var)
        { 
            if (node.Op.OpType != OpType.VarRef) 
            {
                return false; 
            }
            return ((VarRefOp)node.Op).Var == var;
        }
    } 

    ///  
    /// The Aggregate Pushdown feature tries to identify function aggregates defined over a 
    /// group aggregate and push their definitions in the group by into node corresponding to
    /// the group aggregate. 
    /// 
    internal class AggregatePushdown
    {
        #region Private fields 
        private readonly Command m_command;
        private TryGetValue m_tryGetParent; 
        #endregion 

        #region Private Constructor 
        private AggregatePushdown(Command command)
        {
            this.m_command = command;
        } 
        #endregion
 
        #region 'Public' Surface 
        /// 
        /// Apply Aggregate Pushdown over the tree in the given plan complier state. 
        /// 
        /// 
        internal static void Process(PlanCompiler planCompilerState)
        { 
            AggregatePushdown aggregatePushdown = new AggregatePushdown(planCompilerState.Command);
            aggregatePushdown.Process(); 
        } 
        #endregion
 
        #region Private Methods

        /// 
        /// The main driver 
        /// 
        private void Process() 
        { 
            IEnumerable groupAggregateVarInfos = GroupAggregateRefComputingVisitor.Process(m_command, out m_tryGetParent);
            foreach (GroupAggregateVarInfo groupAggregateVarInfo in groupAggregateVarInfos) 
            {
                if (groupAggregateVarInfo.HasCandidateAggregateNodes)
                {
                    foreach (KeyValuePair candidate in groupAggregateVarInfo.CandidateAggregateNodes) 
                    {
                        TryProcessCandidate(candidate, groupAggregateVarInfo); 
                    } 
                }
            } 
        }

        /// 
        /// Try to push the given function aggregate candidate to the corresponding group into node. 
        /// The candidate can be pushed if all ancestors of the group into node up to the least common
        /// ancestor between the group into node and the function aggregate have one of the following node op types: 
        ///     Project 
        ///     Filter
        ///     ConstraintSortOp 
        /// 
        /// 
        /// 
        ///  
        /// 
        private void TryProcessCandidate( 
            KeyValuePair candidate, 
            GroupAggregateVarInfo groupAggregateVarInfo)
        { 
            IList functionAncestors;
            IList groupByAncestors;
            Node definingGroupNode = groupAggregateVarInfo.DefiningGroupNode;
            FindPathsToLeastCommonAncestor(candidate.Key, definingGroupNode, out functionAncestors, out groupByAncestors); 

            //Check whether all ancestors of the GroupByInto node are of type that we support propagating through 
            if (!AreAllNodesSupportedForPropagation(groupByAncestors)) 
            {
                return; 
            }

            //Add the function to the group by node
            GroupByIntoOp definingGroupOp = (GroupByIntoOp)definingGroupNode.Op; 
            PlanCompiler.Assert(definingGroupOp.Inputs.Count == 1, "There should be one input var to GroupByInto at this stage");
            Var inputVar = definingGroupOp.Inputs.First; 
            FunctionOp functionOp = (FunctionOp)candidate.Key.Op; 

            // 
            // Remap the template from referencing the groupAggregate var to reference the input to
            // the group by into
            //
            Node argumentNode = OpCopier.Copy(m_command, candidate.Value); 
            Dictionary dictionary = new Dictionary(1);
            dictionary.Add(groupAggregateVarInfo.GroupAggregateVar, inputVar); 
            VarRemapper remapper = new VarRemapper(m_command, dictionary); 
            remapper.RemapSubtree(argumentNode);
 
            Node newFunctionDefiningNode = m_command.CreateNode(
                m_command.CreateAggregateOp(functionOp.Function, false),
                argumentNode);
 
            Var newFunctionVar;
            Node varDefNode = m_command.CreateVarDefNode(newFunctionDefiningNode, out newFunctionVar); 
 
            // Add the new aggregate to the list of aggregates
            definingGroupNode.Child2.Children.Add(varDefNode); 
            GroupByIntoOp groupByOp = (GroupByIntoOp)definingGroupNode.Op;
            groupByOp.Outputs.Set(newFunctionVar);

            //Propagate the new var throught the ancestors of the GroupByInto 
            for (int i = 0; i < groupByAncestors.Count; i++)
            { 
                Node groupByAncestor = groupByAncestors[i]; 
                if (groupByAncestor.Op.OpType == OpType.Project)
                { 
                    ProjectOp ancestorProjectOp = (ProjectOp)groupByAncestor.Op;
                    ancestorProjectOp.Outputs.Set(newFunctionVar);
                }
            } 

            //Update the functionNode 
            candidate.Key.Op = m_command.CreateVarRefOp(newFunctionVar); 
            candidate.Key.Children.Clear();
        } 

        /// 
        /// Check whether all nodes in the given list of nodes are of types
        /// that we know how to propagate an aggregate through 
        /// 
        ///  
        ///  
        private static bool AreAllNodesSupportedForPropagation(IList nodes)
        { 
            foreach (Node node in nodes)
            {
                if (node.Op.OpType != OpType.Project
                    && node.Op.OpType != OpType.Filter 
                    && node.Op.OpType != OpType.ConstrainedSort
                    ) 
                { 
                    return false;
                } 
            }
            return true;
        }
 
        /// 
        /// Finds the paths from each of node1 and node2 to their least common ancestor 
        ///  
        /// 
        ///  
        /// 
        /// 
        private void FindPathsToLeastCommonAncestor(Node node1, Node node2, out IList ancestors1, out IList ancestors2)
        { 
            ancestors1 = FindAncestors(node1);
            ancestors2 = FindAncestors(node2); 
 
            int currentIndex1 = ancestors1.Count - 1;
            int currentIndex2 = ancestors2.Count - 1; 
            while (ancestors1[currentIndex1] == ancestors2[currentIndex2])
            {
                currentIndex1--;
                currentIndex2--; 
            }
 
            for (int i = ancestors1.Count - 1; i > currentIndex1; i--) 
            {
                ancestors1.RemoveAt(i); 
            }
            for (int i = ancestors2.Count - 1; i > currentIndex2; i--)
            {
                ancestors2.RemoveAt(i); 
            }
        } 
 
        /// 
        /// Finds all ancestors of the given node. 
        /// 
        /// 
        /// An ordered list of the all the ancestors of the given node starting from the immediate parent
        /// to the root of the tree 
        private IList FindAncestors(Node node)
        { 
            List ancestors = new List(); 
            Node currentNode = node;
            Node ancestor; 
            while (m_tryGetParent(currentNode, out ancestor))
            {
                ancestors.Add(ancestor);
                currentNode = ancestor; 
            }
            return ancestors; 
        } 
        #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.Data.Common;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization; 
using System.Text;
 
using System.Data.Metadata.Edm; 
using System.Data.Query.InternalTrees;
 
namespace System.Data.Query.PlanCompiler
{
    internal delegate bool TryGetValue(Node key, out Node value);
 
    #region Helper Classes
    ///  
    /// Helper class to track the aggregate nodes that are candidates to be 
    /// pushed into the definingGroupByNode.
    ///  
    internal class GroupAggregateVarInfo
    {
        #region Private Fields
        private readonly Node _definingGroupByNode; 
        private HashSet> _candidateAggregateNodes;
        private readonly Var _groupAggregateVar; 
        #endregion 

        #region Constructor 
        /// 
        /// Public constructor
        /// 
        /// The GroupIntoOp node 
        /// 
        internal GroupAggregateVarInfo(Node defingingGroupNode, Var groupAggregateVar) 
        { 
            _definingGroupByNode = defingingGroupNode;
            _groupAggregateVar = groupAggregateVar; 
        }
        #endregion

        #region 'Public' Properties 
        /// 
        /// Each key value pair represents a candidate aggregate. 
        /// The key is the function aggregate subtree and the value is a 'template' of translation of the 
        /// function aggregate's argument over the var representing the group aggregate.
        /// A valid candidate has an argument that does not have any external references 
        /// except for the group aggregate corresponding to the DefiningGroupNode.
        /// 
        internal HashSet> CandidateAggregateNodes
        { 
            get
            { 
                if (_candidateAggregateNodes == null) 
                {
                    _candidateAggregateNodes = new HashSet>(); 
                }
                return _candidateAggregateNodes;
            }
        } 

        ///  
        /// Are there are agregates that are candidates to be pushed into the DefiningGroupNode 
        /// 
        internal bool HasCandidateAggregateNodes 
        {
            get
            {
                return (_candidateAggregateNodes != null && _candidateAggregateNodes.Count != 0); 
            }
        } 
 
        /// 
        /// The GroupIntoOp node that this GroupAggregateVarInfo represents 
        /// 
        internal Node DefiningGroupNode
        {
            get { return _definingGroupByNode; } 
        }
 
        internal Var GroupAggregateVar 
        {
            get { return _groupAggregateVar; } 
        }
        #endregion
    }
 
    /// 
    /// Helper class to track usage of GroupAggregateVarInfo 
    /// It represents the usage of a single GroupAggregateVar. 
    /// The usage is defined by the computation, it should be a subree whose only
    /// external reference is the group var represented by the GroupAggregateVarInfo. 
    /// 
    internal class GroupAggregateVarRefInfo
    {
        #region Private fields 
        private readonly Node _computation;
        private readonly GroupAggregateVarInfo _groupAggregateVarInfo; 
        private readonly bool _isUnnested; 
        #endregion
 
        #region Constructor
        /// 
        /// Public constructor
        ///  
        /// 
        ///  
        internal GroupAggregateVarRefInfo(GroupAggregateVarInfo groupAggregateVarInfo, Node computation, bool isUnnested) 
        {
            this._groupAggregateVarInfo = groupAggregateVarInfo; 
            this._computation = computation;
            this._isUnnested = isUnnested;
        }
 
        #endregion
 
        #region 'Public' Properties 
        /// 
        /// Subtree whose only external reference is 
        /// the group var represented by the GroupAggregateVarInfo
        /// 
        internal Node Computation
        { 
            get { return _computation; }
        } 
 
        /// 
        /// The GroupAggregateVarInfo (possibly) referenced by the computation 
        /// 
        internal GroupAggregateVarInfo GroupAggregateVarInfo
        {
            get { return _groupAggregateVarInfo; } 
        }
 
        ///  
        /// Is the computation over unnested group aggregate var
        ///  
        internal bool IsUnnested
        {
            get { return _isUnnested; }
        } 
        #endregion
    } 
 
    /// 
    /// Manages refereces to groupAggregate variables. 
    /// 
    internal class GroupAggregateVarInfoManager
    {
        #region Private state 
        private readonly Dictionary _groupAggregateVarRelatedVarToInfo = new Dictionary();
        private Dictionary> _groupAggregateVarRelatedVarPropertyToInfo; 
        private HashSet _groupAggregateVarInfos = new HashSet(); 
        #endregion
 
        #region Public Surface
        /// 
        /// Get all the groupAggregateVarInfos
        ///  
        internal IEnumerable GroupAggregateVarInfos
        { 
            get 
            {
                return _groupAggregateVarInfos; 
            }
        }

        ///  
        /// Add an entry that var is a computation represented by the computationTemplate
        /// over the var represented by the given groupAggregateVarInfo 
        ///  
        /// 
        ///  
        /// 
        /// 
        internal void Add(Var var, GroupAggregateVarInfo groupAggregateVarInfo, Node computationTemplate, bool isUnnested)
        { 
            this._groupAggregateVarRelatedVarToInfo.Add(var, new GroupAggregateVarRefInfo(groupAggregateVarInfo, computationTemplate, isUnnested));
            _groupAggregateVarInfos.Add(groupAggregateVarInfo); 
        } 

        ///  
        /// Add an entry that the given property of the given var is a computation represented
        /// by the computationTemplate over the var represented by the given groupAggregateVarInfo
        /// 
        ///  
        /// 
        ///  
        ///  
        /// 
        internal void Add(Var var, GroupAggregateVarInfo groupAggregateVarInfo, Node computationTemplate, bool isUnnested, EdmMember property) 
        {
            if (property == null)
            {
                Add(var, groupAggregateVarInfo, computationTemplate, isUnnested); 
                return;
            } 
            if (this._groupAggregateVarRelatedVarPropertyToInfo == null) 
            {
                this._groupAggregateVarRelatedVarPropertyToInfo = new Dictionary>(); 
            }
            Dictionary varPropertyDictionary;
            if (!_groupAggregateVarRelatedVarPropertyToInfo.TryGetValue(var, out varPropertyDictionary))
            { 
                varPropertyDictionary = new Dictionary();
                _groupAggregateVarRelatedVarPropertyToInfo.Add(var, varPropertyDictionary); 
            } 
            varPropertyDictionary.Add(property, new GroupAggregateVarRefInfo(groupAggregateVarInfo, computationTemplate, isUnnested));
 
            // Note: The following line is not necessary with the current usage pattern, this method is
            // never called with a new groupAggregateVarInfo thus it is a no-op.
            _groupAggregateVarInfos.Add(groupAggregateVarInfo);
        } 

        ///  
        /// Gets the groupAggregateVarRefInfo representing the definition of the given var over 
        /// a group aggregate var if any.
        ///  
        /// 
        /// 
        /// 
        internal bool TryGetReferencedGroupAggregateVarInfo(Var var, out GroupAggregateVarRefInfo groupAggregateVarRefInfo) 
        {
            return this._groupAggregateVarRelatedVarToInfo.TryGetValue(var, out groupAggregateVarRefInfo); 
        } 

        ///  
        /// Gets the groupAggregateVarRefInfo representing the definition of the given property of the given
        /// var over a group aggregate var if any.
        /// 
        ///  
        /// 
        ///  
        ///  
        internal bool TryGetReferencedGroupAggregateVarInfo(Var var, EdmMember property, out GroupAggregateVarRefInfo groupAggregateVarRefInfo)
        { 
            if (property == null)
            {
                return TryGetReferencedGroupAggregateVarInfo(var, out groupAggregateVarRefInfo);
            } 

            Dictionary varPropertyDictionary; 
            if (_groupAggregateVarRelatedVarPropertyToInfo == null || !_groupAggregateVarRelatedVarPropertyToInfo.TryGetValue(var, out varPropertyDictionary)) 
            {
                groupAggregateVarRefInfo = null; 
                return false;
            }
            return varPropertyDictionary.TryGetValue(property, out groupAggregateVarRefInfo);
        } 
        #endregion
    } 
    #endregion 

    ///  
    /// Utility class that tries to produce an equivalent tree to the input tree over
    /// a single group aggregate variable and no other external references
    /// 
    internal class GroupAggregateVarComputationTranslator : BasicOpVisitorOfNode 
    {
        #region Private State 
        private GroupAggregateVarInfo _targetGroupAggregateVarInfo; 
        private bool _isUnnested;
        private readonly Command _command; 
        private readonly GroupAggregateVarInfoManager _groupAggregateVarInfoManager;
        #endregion

        #region Constructor 
        /// 
        /// Private constructor 
        ///  
        /// 
        ///  
        private GroupAggregateVarComputationTranslator(
            Command command,
            GroupAggregateVarInfoManager groupAggregateVarInfoManager)
        { 
            this._command = command;
            this._groupAggregateVarInfoManager = groupAggregateVarInfoManager; 
        } 
        #endregion
 
        #region 'Public' Surface
        /// 
        /// Try to produce an equivalent tree to the input subtree, over a single group aggregate variable.
        /// Such translation can only be produced if all external references of the input subtree are to a 
        /// single group aggregate var, or to vars that are can be translated over that single group
        /// aggregate var 
        ///  
        /// The input subtree
        ///  
        /// 
        /// 
        /// The groupAggregateVarInfo over which the input subtree can be translated 
        /// A tree that is equvalent to the input tree, but over the group aggregate variable 
        /// represented by the groupAggregetVarInfo
        ///  
        /// True, if the translation can be done, false otherwise 
        public static bool TryTranslateOverGroupAggregateVar(
            Node subtree, 
            bool isVarDefinition,
            Command command,
            GroupAggregateVarInfoManager groupAggregateVarInfoManager,
            out GroupAggregateVarInfo groupAggregateVarInfo, 
            out Node templateNode,
            out bool isUnnested) 
        { 
            GroupAggregateVarComputationTranslator handler = new GroupAggregateVarComputationTranslator(command, groupAggregateVarInfoManager);
 
            Node inputNode = subtree;
            SoftCastOp softCastOp = null;
            bool isCollect;
            if (inputNode.Op.OpType == OpType.SoftCast) 
            {
                softCastOp = (SoftCastOp)inputNode.Op; 
                inputNode = inputNode.Child0; 
            }
 
            if (inputNode.Op.OpType == OpType.Collect)
            {
                templateNode = handler.VisitCollect(inputNode);
                isCollect = true; 
            }
            else 
            { 
                templateNode = handler.VisitNode(inputNode);
                isCollect = false; 
            }

            groupAggregateVarInfo = handler._targetGroupAggregateVarInfo;
            isUnnested = handler._isUnnested; 

            if (handler._targetGroupAggregateVarInfo == null || templateNode == null) 
            { 
                return false;
            } 
            if (softCastOp != null)
            {
                SoftCastOp newSoftCastOp;
                // 
                // The type needs to be fixed only if the unnesting happened during this translation.
                // That can be recognized by these two cases: 
                //      1) if the input node was a collect, or 
                //      2) if the input did not represent a var definition, but a function aggregate argument and
                //              the template is VarRef of a group aggregate var. 
                //
                if (isCollect || !isVarDefinition && AggregatePushdownUtil.IsVarRefOverGivenVar(templateNode, handler._targetGroupAggregateVarInfo.GroupAggregateVar))
                {
                    newSoftCastOp = command.CreateSoftCastOp(TypeHelpers.GetEdmType(softCastOp.Type).TypeUsage); 
                }
                else 
                { 
                    newSoftCastOp = softCastOp;
                } 
                templateNode = command.CreateNode(newSoftCastOp, templateNode);
            }
            return true;
        } 
        #endregion
 
        #region Visitor Methods 
        /// 
        /// See  
        /// 
        /// 
        /// 
        ///  
        public override Node Visit(VarRefOp op, Node n)
        { 
            return TranslateOverGroupAggregateVar(op.Var, null); 
        }
 
        /// 
        /// If the child is VarRef check if the subtree PropertyOp(VarRef) is reference to a
        /// group aggregate var.
        /// Otherwise do default processing 
        /// 
        ///  
        ///  
        /// 
        public override Node Visit(PropertyOp op, Node n) 
        {
            if (n.Child0.Op.OpType != OpType.VarRef)
            {
                return base.Visit(op, n); 
            }
            VarRefOp varRefOp = (VarRefOp)n.Child0.Op; 
            return TranslateOverGroupAggregateVar(varRefOp.Var, op.PropertyInfo); 
        }
 
        /// 
        /// If the Subtree rooted at the collect is of the following structure:
        ///
        /// PhysicalProject(outputVar) 
        /// |
        /// Project(s) 
        /// | 
        /// Unnest
        /// 
        /// where the unnest is over  the group aggregate var and the output var
        /// is either a reference to the group aggregate var or to a constant, it returns the
        /// translation of the ouput var.
        ///  
        /// 
        ///  
        private Node VisitCollect(Node n) 
        {
            //Make sure the only children are projects over unnest 
            Node currentNode = n.Child0;
            Dictionary constantDefinitions = new Dictionary();
            while (currentNode.Child0.Op.OpType == OpType.Project)
            { 
                currentNode = currentNode.Child0;
                //Visit the VarDefListOp child 
                if (VisitDefault(currentNode.Child1) == null) 
                {
                    return null; 
                }
                foreach (Node definitionNode in currentNode.Child1.Children)
                {
                    if (IsConstant(definitionNode.Child0)) 
                    {
                        constantDefinitions.Add(((VarDefOp)definitionNode.Op).Var, definitionNode.Child0); 
                    } 
                }
            } 

            if (currentNode.Child0.Op.OpType != OpType.Unnest)
            {
                return null; 
            }
 
            // Handle the unnest 
            UnnestOp unnestOp = (UnnestOp)currentNode.Child0.Op;
            GroupAggregateVarRefInfo groupAggregateVarRefInfo; 
            if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(unnestOp.Var, out groupAggregateVarRefInfo))
            {
                if (_targetGroupAggregateVarInfo == null)
                { 
                    _targetGroupAggregateVarInfo = groupAggregateVarRefInfo.GroupAggregateVarInfo;
                } 
                else if (_targetGroupAggregateVarInfo != groupAggregateVarRefInfo.GroupAggregateVarInfo) 
                {
                    return null; 
                }
                if (!_isUnnested)
                {
                    return null; 
                }
            } 
            else 
            {
                return null; 
            }

            PhysicalProjectOp physicalProjectOp = (PhysicalProjectOp)n.Child0.Op;
            PlanCompiler.Assert(physicalProjectOp.Outputs.Count == 1, "PhysicalProject should only have one output at this stage"); 
            Var outputVar = physicalProjectOp.Outputs[0];
 
            Node computationTemplate = TranslateOverGroupAggregateVar(outputVar, null); 
            if (computationTemplate != null)
            { 
                _isUnnested = true;
                return computationTemplate;
            }
 
            Node constantDefinitionNode;
            if (constantDefinitions.TryGetValue(outputVar, out constantDefinitionNode)) 
            { 
                _isUnnested = true;
                return constantDefinitionNode; 
            }
            return null;
        }
 
        /// 
        /// Determines whether the given Node is a constant subtree 
        /// It only recognizes any of the constant base ops 
        /// and possibly casts over these nodes.
        ///  
        /// 
        /// 
        private static bool IsConstant(Node node)
        { 
            Node currentNode = node;
            while (currentNode.Op.OpType == OpType.Cast) 
            { 
                currentNode = currentNode.Child0;
            } 
            return PlanCompilerUtil.IsConstantBaseOp(currentNode.Op.OpType);
        }

        ///  
        /// (1) If the given var or the given property of the given var are defined over a group aggregate var,
        /// (2) and if that group aggregate var matches the var represented by represented by _targetGroupAggregateVarInfo 
        /// if any 
        ///
        /// it returns the corresponding translation over the group aggregate var. Also, if _targetGroupAggregateVarInfo 
        /// is not set, it sets it to the group aggregate var representing the referenced var.
        /// 
        /// 
        ///  
        /// 
        private Node TranslateOverGroupAggregateVar(Var var, EdmMember property) 
        { 
            GroupAggregateVarRefInfo groupAggregateVarRefInfo;
            EdmMember localProperty; 
            if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(var, out groupAggregateVarRefInfo))
            {
                localProperty = property;
            } 
            else if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(var, property, out  groupAggregateVarRefInfo))
            { 
                localProperty = null; 
            }
            else 
            {
                return null;
            }
 
            if (_targetGroupAggregateVarInfo == null)
            { 
                _targetGroupAggregateVarInfo = groupAggregateVarRefInfo.GroupAggregateVarInfo; 
                _isUnnested = groupAggregateVarRefInfo.IsUnnested;
            } 
            else if (_targetGroupAggregateVarInfo != groupAggregateVarRefInfo.GroupAggregateVarInfo || _isUnnested != groupAggregateVarRefInfo.IsUnnested)
            {
                return null;
            } 

            Node computationTemplate = groupAggregateVarRefInfo.Computation; 
            if (localProperty != null) 
            {
                computationTemplate = this._command.CreateNode(this._command.CreatePropertyOp(localProperty), computationTemplate); 
            }
            return computationTemplate;
        }
 
        /// 
        /// Default processing for nodes. 
        /// Visits the children and if any child has changed it creates a new node 
        /// for the parent.
        /// If the reference of the child node did not change, the child node did not change either, 
        /// this is because a node can only be reused "as is" when building a template.
        /// 
        /// 
        ///  
        protected override Node VisitDefault(Node n)
        { 
            List newChildren = new List(n.Children.Count); 
            bool anyChildChanged = false;
            for (int i = 0; i < n.Children.Count; i++) 
            {
                Node processedChild = VisitNode(n.Children[i]);
                if (processedChild == null)
                { 
                    return null;
                } 
                if (!anyChildChanged && !Object.ReferenceEquals(n.Children[i], processedChild)) 
                {
                    anyChildChanged = true; 
                }
                newChildren.Add(processedChild);
            }
 
            if (!anyChildChanged)
            { 
                return n; 
            }
            else 
            {
                return _command.CreateNode(n.Op, newChildren);
            }
        } 

        #region Unsupported node types 
 
        protected override Node VisitRelOpDefault(RelOp op, Node n)
        { 
            return null;
        }

        public override Node Visit(AggregateOp op, Node n) 
        {
            return null; 
        } 

        public override Node Visit(CollectOp op, Node n) 
        {
            return null;
        }
 
        public override Node Visit(ElementOp op, Node n)
        { 
            return null; 
        }
 
        #endregion

        #endregion
    } 

    ///  
    /// A visitor that collects all group aggregates and the corresponding function aggregates 
    /// that are defined over them, referred to as 'candidate aggregates'. The candidate aggregates are aggregates
    /// that have an argument that has the corresponding group aggregate as the only external reference 
    /// 
    internal class GroupAggregateRefComputingVisitor : BasicOpVisitor
    {
        #region private state 
        private readonly Command _command;
        private readonly GroupAggregateVarInfoManager _groupAggregateVarInfoManager = new GroupAggregateVarInfoManager(); 
        private readonly Dictionary _childToParent = new Dictionary(); 
        #endregion
 
        #region 'Public'
        /// 
        /// Produces a list of all GroupAggregateVarInfos, each of which represents a single group aggregate
        /// and it candidate function aggregates. It also produces a delegate that given a child node returns the parent node 
        /// 
        ///  
        ///  
        /// 
        internal static IEnumerable Process(Command itree, out TryGetValue tryGetParent) 
        {
            GroupAggregateRefComputingVisitor groupRefComputingVisitor = new GroupAggregateRefComputingVisitor(itree);
            groupRefComputingVisitor.VisitNode(itree.Root);
            tryGetParent = groupRefComputingVisitor._childToParent.TryGetValue; 

            return groupRefComputingVisitor._groupAggregateVarInfoManager.GroupAggregateVarInfos; 
        } 
        #endregion
 
        #region Private Constructor
        /// 
        /// Private constructor
        ///  
        /// 
        private GroupAggregateRefComputingVisitor(Command itree) 
        { 
            this._command = itree;
        } 
        #endregion

        #region Visitor Methods
 
        #region AncillaryOps
        ///  
        /// Determines whether the var or a property of the var (if the var is defined as a NewRecord) 
        /// is defined exclusively over a single group aggregate. If so, it registers it as such with the
        /// group aggregate var info manager. 
        /// 
        /// 
        /// 
        public override void Visit(VarDefOp op, Node n) 
        {
            VisitDefault(n); 
 
            Node definingNode = n.Child0;
            Op definingNodeOp = definingNode.Op; 

            GroupAggregateVarInfo referencedVarInfo;
            Node templateNode;
            bool isUnnested; 
            if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(definingNode, true, this._command, this._groupAggregateVarInfoManager, out  referencedVarInfo, out templateNode, out isUnnested))
            { 
                _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested); 
            }
            else if (definingNodeOp.OpType == OpType.NewRecord) 
            {
                NewRecordOp newRecordOp = (NewRecordOp)definingNodeOp;
                for (int i = 0; i < definingNode.Children.Count; i++)
                { 
                    Node argumentNode = definingNode.Children[i];
                    if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(argumentNode, true, this._command, this._groupAggregateVarInfoManager, out referencedVarInfo, out templateNode, out isUnnested)) 
                    { 
                        _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested, newRecordOp.Properties[i]);
                    } 
                }
            }
        }
 
        #endregion
 
        #region RelOp Visitors 
        /// 
        /// Registers the group aggregate var with the group aggregate var info manager 
        /// 
        /// 
        /// 
        public override void Visit(GroupByIntoOp op, Node n) 
        {
            VisitGroupByOp(op, n); 
            foreach (Node child in n.Child3.Children) 
            {
                Var groupAggregateVar = ((VarDefOp)child.Op).Var; 
                GroupAggregateVarRefInfo groupAggregateVarRefInfo;
                // If the group by is over a group, it may be already tracked as referencing a group var
                // An optimization would be to separately track this groupAggregateVar too, for the cases when the aggregate can
                // not be pushed to the group by node over which this one is defined but can be propagated to this group by node. 
                if (!_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(groupAggregateVar, out groupAggregateVarRefInfo))
                { 
                    _groupAggregateVarInfoManager.Add(groupAggregateVar, new GroupAggregateVarInfo(n, groupAggregateVar), this._command.CreateNode(this._command.CreateVarRefOp(groupAggregateVar)), false); 
                }
            } 
        }

        /// 
        /// If the unnestOp's var is defined as a reference of a group aggregate var, 
        /// then the columns it produces should be registered too, but as 'unnested' references
        ///  
        /// the unnestOp 
        /// current subtree
        /// modified subtree 
        public override void Visit(UnnestOp op, Node n)
        {
            VisitDefault(n);
            GroupAggregateVarRefInfo groupAggregateVarRefInfo; 
            if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(op.Var, out groupAggregateVarRefInfo))
            { 
                PlanCompiler.Assert(op.Table.Columns.Count == 1, "Expected one column before NTE"); 
                _groupAggregateVarInfoManager.Add(op.Table.Columns[0], groupAggregateVarRefInfo.GroupAggregateVarInfo, groupAggregateVarRefInfo.Computation, true);
            } 
        }

        #endregion
 
        #region ScalarOps Visitors
        ///  
        /// If the op is a collection aggregate function it checks whether its arguement can be translated over 
        /// a single group aggregate var. If so, it is tracked as a candidate to be pushed into that
        /// group by into node. 
        /// 
        /// 
        /// 
        public override void Visit(FunctionOp op, Node n) 
        {
            VisitDefault(n); 
            if (!PlanCompilerUtil.IsCollectionAggregateFunction(op, n)) 
            {
                return; 
            }
            PlanCompiler.Assert(n.Children.Count == 1, "Aggregate Function must have one argument");

            Node argumentNode = n.Child0; 

            GroupAggregateVarInfo referencedGroupAggregateVarInfo; 
            Node templateNode; 
            bool isUnnested;
            if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(n.Child0, false, _command, _groupAggregateVarInfoManager, out referencedGroupAggregateVarInfo, out templateNode, out isUnnested) 
                && (isUnnested || AggregatePushdownUtil.IsVarRefOverGivenVar(templateNode, referencedGroupAggregateVarInfo.GroupAggregateVar)))
            {
                referencedGroupAggregateVarInfo.CandidateAggregateNodes.Add(new KeyValuePair(n, templateNode));
            } 
        }
 
        #endregion 

        ///  
        /// Default visitor for nodes.
        /// It tracks the child-parent relationship.
        /// 
        ///  
        protected override void VisitDefault(Node n)
        { 
            VisitChildren(n); 
            foreach (Node child in n.Children)
            { 
                //No need to track terminal nodes, plus some of these may be reused.
                if (child.Op.Arity != 0)
                {
                    _childToParent.Add(child, n); 
                }
            } 
        } 
        #endregion
 
    }

    /// 
    /// Utility class to gather helper methods used by more than one class in the Aggregate Pushdown feature. 
    /// 
    internal static class AggregatePushdownUtil 
    { 
        /// 
        /// Determines whether the given node is a VarRef over the given var 
        /// 
        /// 
        /// 
        ///  
        internal static bool IsVarRefOverGivenVar(Node node, Var var)
        { 
            if (node.Op.OpType != OpType.VarRef) 
            {
                return false; 
            }
            return ((VarRefOp)node.Op).Var == var;
        }
    } 

    ///  
    /// The Aggregate Pushdown feature tries to identify function aggregates defined over a 
    /// group aggregate and push their definitions in the group by into node corresponding to
    /// the group aggregate. 
    /// 
    internal class AggregatePushdown
    {
        #region Private fields 
        private readonly Command m_command;
        private TryGetValue m_tryGetParent; 
        #endregion 

        #region Private Constructor 
        private AggregatePushdown(Command command)
        {
            this.m_command = command;
        } 
        #endregion
 
        #region 'Public' Surface 
        /// 
        /// Apply Aggregate Pushdown over the tree in the given plan complier state. 
        /// 
        /// 
        internal static void Process(PlanCompiler planCompilerState)
        { 
            AggregatePushdown aggregatePushdown = new AggregatePushdown(planCompilerState.Command);
            aggregatePushdown.Process(); 
        } 
        #endregion
 
        #region Private Methods

        /// 
        /// The main driver 
        /// 
        private void Process() 
        { 
            IEnumerable groupAggregateVarInfos = GroupAggregateRefComputingVisitor.Process(m_command, out m_tryGetParent);
            foreach (GroupAggregateVarInfo groupAggregateVarInfo in groupAggregateVarInfos) 
            {
                if (groupAggregateVarInfo.HasCandidateAggregateNodes)
                {
                    foreach (KeyValuePair candidate in groupAggregateVarInfo.CandidateAggregateNodes) 
                    {
                        TryProcessCandidate(candidate, groupAggregateVarInfo); 
                    } 
                }
            } 
        }

        /// 
        /// Try to push the given function aggregate candidate to the corresponding group into node. 
        /// The candidate can be pushed if all ancestors of the group into node up to the least common
        /// ancestor between the group into node and the function aggregate have one of the following node op types: 
        ///     Project 
        ///     Filter
        ///     ConstraintSortOp 
        /// 
        /// 
        /// 
        ///  
        /// 
        private void TryProcessCandidate( 
            KeyValuePair candidate, 
            GroupAggregateVarInfo groupAggregateVarInfo)
        { 
            IList functionAncestors;
            IList groupByAncestors;
            Node definingGroupNode = groupAggregateVarInfo.DefiningGroupNode;
            FindPathsToLeastCommonAncestor(candidate.Key, definingGroupNode, out functionAncestors, out groupByAncestors); 

            //Check whether all ancestors of the GroupByInto node are of type that we support propagating through 
            if (!AreAllNodesSupportedForPropagation(groupByAncestors)) 
            {
                return; 
            }

            //Add the function to the group by node
            GroupByIntoOp definingGroupOp = (GroupByIntoOp)definingGroupNode.Op; 
            PlanCompiler.Assert(definingGroupOp.Inputs.Count == 1, "There should be one input var to GroupByInto at this stage");
            Var inputVar = definingGroupOp.Inputs.First; 
            FunctionOp functionOp = (FunctionOp)candidate.Key.Op; 

            // 
            // Remap the template from referencing the groupAggregate var to reference the input to
            // the group by into
            //
            Node argumentNode = OpCopier.Copy(m_command, candidate.Value); 
            Dictionary dictionary = new Dictionary(1);
            dictionary.Add(groupAggregateVarInfo.GroupAggregateVar, inputVar); 
            VarRemapper remapper = new VarRemapper(m_command, dictionary); 
            remapper.RemapSubtree(argumentNode);
 
            Node newFunctionDefiningNode = m_command.CreateNode(
                m_command.CreateAggregateOp(functionOp.Function, false),
                argumentNode);
 
            Var newFunctionVar;
            Node varDefNode = m_command.CreateVarDefNode(newFunctionDefiningNode, out newFunctionVar); 
 
            // Add the new aggregate to the list of aggregates
            definingGroupNode.Child2.Children.Add(varDefNode); 
            GroupByIntoOp groupByOp = (GroupByIntoOp)definingGroupNode.Op;
            groupByOp.Outputs.Set(newFunctionVar);

            //Propagate the new var throught the ancestors of the GroupByInto 
            for (int i = 0; i < groupByAncestors.Count; i++)
            { 
                Node groupByAncestor = groupByAncestors[i]; 
                if (groupByAncestor.Op.OpType == OpType.Project)
                { 
                    ProjectOp ancestorProjectOp = (ProjectOp)groupByAncestor.Op;
                    ancestorProjectOp.Outputs.Set(newFunctionVar);
                }
            } 

            //Update the functionNode 
            candidate.Key.Op = m_command.CreateVarRefOp(newFunctionVar); 
            candidate.Key.Children.Clear();
        } 

        /// 
        /// Check whether all nodes in the given list of nodes are of types
        /// that we know how to propagate an aggregate through 
        /// 
        ///  
        ///  
        private static bool AreAllNodesSupportedForPropagation(IList nodes)
        { 
            foreach (Node node in nodes)
            {
                if (node.Op.OpType != OpType.Project
                    && node.Op.OpType != OpType.Filter 
                    && node.Op.OpType != OpType.ConstrainedSort
                    ) 
                { 
                    return false;
                } 
            }
            return true;
        }
 
        /// 
        /// Finds the paths from each of node1 and node2 to their least common ancestor 
        ///  
        /// 
        ///  
        /// 
        /// 
        private void FindPathsToLeastCommonAncestor(Node node1, Node node2, out IList ancestors1, out IList ancestors2)
        { 
            ancestors1 = FindAncestors(node1);
            ancestors2 = FindAncestors(node2); 
 
            int currentIndex1 = ancestors1.Count - 1;
            int currentIndex2 = ancestors2.Count - 1; 
            while (ancestors1[currentIndex1] == ancestors2[currentIndex2])
            {
                currentIndex1--;
                currentIndex2--; 
            }
 
            for (int i = ancestors1.Count - 1; i > currentIndex1; i--) 
            {
                ancestors1.RemoveAt(i); 
            }
            for (int i = ancestors2.Count - 1; i > currentIndex2; i--)
            {
                ancestors2.RemoveAt(i); 
            }
        } 
 
        /// 
        /// Finds all ancestors of the given node. 
        /// 
        /// 
        /// An ordered list of the all the ancestors of the given node starting from the immediate parent
        /// to the root of the tree 
        private IList FindAncestors(Node node)
        { 
            List ancestors = new List(); 
            Node currentNode = node;
            Node ancestor; 
            while (m_tryGetParent(currentNode, out ancestor))
            {
                ancestors.Add(ancestor);
                currentNode = ancestor; 
            }
            return ancestors; 
        } 
        #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