mcs/class/referencesource/System.Data.Entity/System/Data/Query/PlanCompiler/AggregatePushdown.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="AggregatePushdown.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Data.Common;
  13 //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
  14
  15 // It is fine to use Debug.Assert in cases where you assert an obvious thing that is supposed
  16 // to prevent from simple mistakes during development (e.g. method argument validation
  17 // in cases where it was you who created the variables or the variables had already been validated or
  18 // in "else" clauses where due to code changes (e.g. adding a new value to an enum type) the default
  19 // "else" block is chosen why the new condition should be treated separately). This kind of asserts are
  20 // (can be) helpful when developing new code to avoid simple mistakes but have no or little value in
  21 // the shipped product.
  22 // PlanCompiler.Assert *MUST* be used to verify conditions in the trees. These would be assumptions
  23 // about how the tree was built etc. - in these cases we probably want to throw an exception (this is
  24 // what PlanCompiler.Assert does when the condition is not met) if either the assumption is not correct
  25 // or the tree was built/rewritten not the way we thought it was.
  26 // Use your judgment - if you rather remove an assert than ship it use Debug.Assert otherwise use
  27 // PlanCompiler.Assert.
  28
  29 using System.Globalization;
  30 using System.Text;
  31
  32 using System.Data.Metadata.Edm;
  33 using System.Data.Query.InternalTrees;
  34
  35 namespace System.Data.Query.PlanCompiler
  36 {
  37     internal delegate bool TryGetValue(Node key, out Node value);
  38
  39     #region Helper Classes
  40     /// <summary>
  41     /// Helper class to track the aggregate nodes that are candidates to be
  42     /// pushed into the definingGroupByNode.
  43     /// </summary>
  44     internal class GroupAggregateVarInfo
  45     {
  46         #region Private Fields
  47         private readonly Node _definingGroupByNode;
  48         private HashSet<KeyValuePair<Node, Node>> _candidateAggregateNodes;
  49         private readonly Var _groupAggregateVar;
  50         #endregion
  51
  52         #region Constructor
  53         /// <summary>
  54         /// Public constructor
  55         /// </summary>
  56         /// <param name="defingingGroupNode">The GroupIntoOp node</param>
  57         /// <param name="groupAggregateVar"></param>
  58         internal GroupAggregateVarInfo(Node defingingGroupNode, Var groupAggregateVar)
  59         {
  60             _definingGroupByNode = defingingGroupNode;
  61             _groupAggregateVar = groupAggregateVar;
  62         }
  63         #endregion
  64
  65         #region 'Public' Properties
  66         /// <summary>
  67         /// Each key value pair represents a candidate aggregate.
  68         /// The key is the function aggregate subtree and the value is a 'template' of translation of the
  69         /// function aggregate's argument over the var representing the group aggregate.
  70         /// A valid candidate has an argument that does not have any external references
  71         /// except for the group aggregate corresponding to the DefiningGroupNode.
  72         /// </summary>
  73         internal HashSet<KeyValuePair<Node, Node>> CandidateAggregateNodes
  74         {
  75             get
  76             {
  77                 if (_candidateAggregateNodes == null)
  78                 {
  79                     _candidateAggregateNodes = new HashSet<KeyValuePair<Node, Node>>();
  80                 }
  81                 return _candidateAggregateNodes;
  82             }
  83         }
  84
  85         /// <summary>
  86         /// Are there are agregates that are candidates to be pushed into the DefiningGroupNode
  87         /// </summary>
  88         internal bool HasCandidateAggregateNodes
  89         {
  90             get
  91             {
  92                 return (_candidateAggregateNodes != null && _candidateAggregateNodes.Count != 0);
  93             }
  94         }
  95
  96         /// <summary>
  97         /// The GroupIntoOp node that this GroupAggregateVarInfo represents
  98         /// </summary>
  99         internal Node DefiningGroupNode
 100         {
 101             get { return _definingGroupByNode; }
 102         }
 103
 104         internal Var GroupAggregateVar
 105         {
 106             get { return _groupAggregateVar; }
 107         }
 108         #endregion
 109     }
 110
 111     /// <summary>
 112     /// Helper class to track usage of GroupAggregateVarInfo
 113     /// It represents the usage of a single GroupAggregateVar.
 114     /// The usage is defined by the computation, it should be a subree whose only
 115     /// external reference is the group var represented by the GroupAggregateVarInfo.
 116     /// </summary>
 117     internal class GroupAggregateVarRefInfo
 118     {
 119         #region Private fields
 120         private readonly Node _computation;
 121         private readonly GroupAggregateVarInfo _groupAggregateVarInfo;
 122         private readonly bool _isUnnested;
 123         #endregion
 124
 125         #region Constructor
 126         /// <summary>
 127         /// Public constructor
 128         /// </summary>
 129         /// <param name="groupAggregateVarInfo"></param>
 130         /// <param name="computation"></param>
 131         internal GroupAggregateVarRefInfo(GroupAggregateVarInfo groupAggregateVarInfo, Node computation, bool isUnnested)
 132         {
 133             this._groupAggregateVarInfo = groupAggregateVarInfo;
 134             this._computation = computation;
 135             this._isUnnested = isUnnested;
 136         }
 137
 138         #endregion
 139
 140         #region 'Public' Properties
 141         /// <summary>
 142         /// Subtree whose only external reference is
 143         /// the group var represented by the GroupAggregateVarInfo
 144         /// </summary>
 145         internal Node Computation
 146         {
 147             get { return _computation; }
 148         }
 149
 150         /// <summary>
 151         /// The GroupAggregateVarInfo (possibly) referenced by the computation
 152         /// </summary>
 153         internal GroupAggregateVarInfo GroupAggregateVarInfo
 154         {
 155             get { return _groupAggregateVarInfo; }
 156         }
 157
 158         /// <summary>
 159         /// Is the computation over unnested group aggregate var
 160         /// </summary>
 161         internal bool IsUnnested
 162         {
 163             get { return _isUnnested; }
 164         }
 165         #endregion
 166     }
 167
 168     /// <summary>
 169     /// Manages refereces to groupAggregate variables.
 170     /// </summary>
 171     internal class GroupAggregateVarInfoManager
 172     {
 173         #region Private state
 174         private readonly Dictionary<Var, GroupAggregateVarRefInfo> _groupAggregateVarRelatedVarToInfo = new Dictionary<Var, GroupAggregateVarRefInfo>();
 175         private Dictionary<Var, Dictionary<EdmMember, GroupAggregateVarRefInfo>> _groupAggregateVarRelatedVarPropertyToInfo;
 176         private HashSet<GroupAggregateVarInfo> _groupAggregateVarInfos = new HashSet<GroupAggregateVarInfo>();
 177         #endregion
 178
 179         #region Public Surface
 180         /// <summary>
 181         /// Get all the groupAggregateVarInfos
 182         /// </summary>
 183         internal IEnumerable<GroupAggregateVarInfo> GroupAggregateVarInfos
 184         {
 185             get
 186             {
 187                 return _groupAggregateVarInfos;
 188             }
 189         }
 190
 191         /// <summary>
 192         /// Add an entry that var is a computation represented by the computationTemplate
 193         /// over the var represented by the given groupAggregateVarInfo
 194         /// </summary>
 195         /// <param name="var"></param>
 196         /// <param name="groupAggregateVarInfo"></param>
 197         /// <param name="computationTemplate"></param>
 198         /// <param name="isUnnested"></param>
 199         internal void Add(Var var, GroupAggregateVarInfo groupAggregateVarInfo, Node computationTemplate, bool isUnnested)
 200         {
 201             this._groupAggregateVarRelatedVarToInfo.Add(var, new GroupAggregateVarRefInfo(groupAggregateVarInfo, computationTemplate, isUnnested));
 202             _groupAggregateVarInfos.Add(groupAggregateVarInfo);
 203         }
 204
 205         /// <summary>
 206         /// Add an entry that the given property of the given var is a computation represented
 207         /// by the computationTemplate over the var represented by the given groupAggregateVarInfo
 208         /// </summary>
 209         /// <param name="var"></param>
 210         /// <param name="groupAggregateVarInfo"></param>
 211         /// <param name="computationTemplate"></param>
 212         /// <param name="isUnnested"></param>
 213         /// <param name="property"></param>
 214         internal void Add(Var var, GroupAggregateVarInfo groupAggregateVarInfo, Node computationTemplate, bool isUnnested, EdmMember property)
 215         {
 216             if (property == null)
 217             {
 218                 Add(var, groupAggregateVarInfo, computationTemplate, isUnnested);
 219                 return;
 220             }
 221             if (this._groupAggregateVarRelatedVarPropertyToInfo == null)
 222             {
 223                 this._groupAggregateVarRelatedVarPropertyToInfo = new Dictionary<Var, Dictionary<System.Data.Metadata.Edm.EdmMember, GroupAggregateVarRefInfo>>();
 224             }
 225             Dictionary<EdmMember, GroupAggregateVarRefInfo> varPropertyDictionary;
 226             if (!_groupAggregateVarRelatedVarPropertyToInfo.TryGetValue(var, out varPropertyDictionary))
 227             {
 228                 varPropertyDictionary = new Dictionary<System.Data.Metadata.Edm.EdmMember, GroupAggregateVarRefInfo>();
 229                 _groupAggregateVarRelatedVarPropertyToInfo.Add(var, varPropertyDictionary);
 230             }
 231             varPropertyDictionary.Add(property, new GroupAggregateVarRefInfo(groupAggregateVarInfo, computationTemplate, isUnnested));
 232
 233             // Note: The following line is not necessary with the current usage pattern, this method is
 234             // never called with a new groupAggregateVarInfo thus it is a no-op.
 235             _groupAggregateVarInfos.Add(groupAggregateVarInfo);
 236         }
 237
 238         /// <summary>
 239         /// Gets the groupAggregateVarRefInfo representing the definition of the given var over
 240         /// a group aggregate var if any.
 241         /// </summary>
 242         /// <param name="var"></param>
 243         /// <param name="groupAggregateVarRefInfo"></param>
 244         /// <returns></returns>
 245         internal bool TryGetReferencedGroupAggregateVarInfo(Var var, out GroupAggregateVarRefInfo groupAggregateVarRefInfo)
 246         {
 247             return this._groupAggregateVarRelatedVarToInfo.TryGetValue(var, out groupAggregateVarRefInfo);
 248         }
 249
 250         /// <summary>
 251         /// Gets the groupAggregateVarRefInfo representing the definition of the given property of the given
 252         /// var over a group aggregate var if any.
 253         /// </summary>
 254         /// <param name="var"></param>
 255         /// <param name="property"></param>
 256         /// <param name="groupAggregateVarRefInfo"></param>
 257         /// <returns></returns>
 258         internal bool TryGetReferencedGroupAggregateVarInfo(Var var, EdmMember property, out GroupAggregateVarRefInfo groupAggregateVarRefInfo)
 259         {
 260             if (property == null)
 261             {
 262                 return TryGetReferencedGroupAggregateVarInfo(var, out groupAggregateVarRefInfo);
 263             }
 264
 265             Dictionary<EdmMember, GroupAggregateVarRefInfo> varPropertyDictionary;
 266             if (_groupAggregateVarRelatedVarPropertyToInfo == null || !_groupAggregateVarRelatedVarPropertyToInfo.TryGetValue(var, out varPropertyDictionary))
 267             {
 268                 groupAggregateVarRefInfo = null;
 269                 return false;
 270             }
 271             return varPropertyDictionary.TryGetValue(property, out groupAggregateVarRefInfo);
 272         }
 273         #endregion
 274     }
 275     #endregion
 276
 277     /// <summary>
 278     /// Utility class that tries to produce an equivalent tree to the input tree over
 279     /// a single group aggregate variable and no other external references
 280     /// </summary>
 281     internal class GroupAggregateVarComputationTranslator : BasicOpVisitorOfNode
 282     {
 283         #region Private State
 284         private GroupAggregateVarInfo _targetGroupAggregateVarInfo;
 285         private bool _isUnnested;
 286         private readonly Command _command;
 287         private readonly GroupAggregateVarInfoManager _groupAggregateVarInfoManager;
 288         #endregion
 289
 290         #region Constructor
 291         /// <summary>
 292         /// Private constructor
 293         /// </summary>
 294         /// <param name="command"></param>
 295         /// <param name="groupAggregateVarInfoManager"></param>
 296         private GroupAggregateVarComputationTranslator(
 297             Command command,
 298             GroupAggregateVarInfoManager groupAggregateVarInfoManager)
 299         {
 300             this._command = command;
 301             this._groupAggregateVarInfoManager = groupAggregateVarInfoManager;
 302         }
 303         #endregion
 304
 305         #region 'Public' Surface
 306         /// <summary>
 307         /// Try to produce an equivalent tree to the input subtree, over a single group aggregate variable.
 308         /// Such translation can only be produced if all external references of the input subtree are to a
 309         /// single group aggregate var, or to vars that are can be translated over that single group
 310         /// aggregate var
 311         /// </summary>
 312         /// <param name="subtree">The input subtree</param>
 313         /// <param name="isVarDefinition"></param>
 314         /// <param name="command"></param>
 315         /// <param name="groupAggregateVarInfoManager"></param>
 316         /// <param name="groupAggregateVarInfo">The groupAggregateVarInfo over which the input subtree can be translated </param>
 317         /// <param name="templateNode">A tree that is equvalent to the input tree, but over the group aggregate variable
 318         /// represented by the groupAggregetVarInfo</param>
 319         /// <param name="isUnnested"></param>
 320         /// <returns>True, if the translation can be done, false otherwise</returns>
 321         public static bool TryTranslateOverGroupAggregateVar(
 322             Node subtree,
 323             bool isVarDefinition,
 324             Command command,
 325             GroupAggregateVarInfoManager groupAggregateVarInfoManager,
 326             out GroupAggregateVarInfo groupAggregateVarInfo,
 327             out Node templateNode,
 328             out bool isUnnested)
 329         {
 330             GroupAggregateVarComputationTranslator handler = new GroupAggregateVarComputationTranslator(command, groupAggregateVarInfoManager);
 331
 332             Node inputNode = subtree;
 333             SoftCastOp softCastOp = null;
 334             bool isCollect;
 335             if (inputNode.Op.OpType == OpType.SoftCast)
 336             {
 337                 softCastOp = (SoftCastOp)inputNode.Op;
 338                 inputNode = inputNode.Child0;
 339             }
 340
 341             if (inputNode.Op.OpType == OpType.Collect)
 342             {
 343                 templateNode = handler.VisitCollect(inputNode);
 344                 isCollect = true;
 345             }
 346             else
 347             {
 348                 templateNode = handler.VisitNode(inputNode);
 349                 isCollect = false;
 350             }
 351
 352             groupAggregateVarInfo = handler._targetGroupAggregateVarInfo;
 353             isUnnested = handler._isUnnested;
 354
 355             if (handler._targetGroupAggregateVarInfo == null || templateNode == null)
 356             {
 357                 return false;
 358             }
 359             if (softCastOp != null)
 360             {
 361                 SoftCastOp newSoftCastOp;
 362                 //
 363                 // The type needs to be fixed only if the unnesting happened during this translation.
 364                 // That can be recognized by these two cases:
 365                 //      1) if the input node was a collect, or
 366                 //      2) if the input did not represent a var definition, but a function aggregate argument and
 367                 //              the template is VarRef of a group aggregate var.
 368                 //
 369                 if (isCollect || !isVarDefinition && AggregatePushdownUtil.IsVarRefOverGivenVar(templateNode, handler._targetGroupAggregateVarInfo.GroupAggregateVar))
 370                 {
 371                     newSoftCastOp = command.CreateSoftCastOp(TypeHelpers.GetEdmType<CollectionType>(softCastOp.Type).TypeUsage);
 372                 }
 373                 else
 374                 {
 375                     newSoftCastOp = softCastOp;
 376                 }
 377                 templateNode = command.CreateNode(newSoftCastOp, templateNode);
 378             }
 379             return true;
 380         }
 381         #endregion
 382
 383         #region Visitor Methods
 384         /// <summary>
 385         /// See <cref="TryTranslateOverGroupAggregateVar"/>
 386         /// </summary>
 387         /// <param name="op"></param>
 388         /// <param name="n"></param>
 389         /// <returns></returns>
 390         public override Node Visit(VarRefOp op, Node n)
 391         {
 392             return TranslateOverGroupAggregateVar(op.Var, null);
 393         }
 394
 395         /// <summary>
 396         /// If the child is VarRef check if the subtree PropertyOp(VarRef) is reference to a
 397         /// group aggregate var.
 398         /// Otherwise do default processing
 399         /// </summary>
 400         /// <param name="op"></param>
 401         /// <param name="n"></param>
 402         /// <returns></returns>
 403         public override Node Visit(PropertyOp op, Node n)
 404         {
 405             if (n.Child0.Op.OpType != OpType.VarRef)
 406             {
 407                 return base.Visit(op, n);
 408             }
 409             VarRefOp varRefOp = (VarRefOp)n.Child0.Op;
 410             return TranslateOverGroupAggregateVar(varRefOp.Var, op.PropertyInfo);
 411         }
 412
 413         /// <summary>
 414         /// If the Subtree rooted at the collect is of the following structure:
 415         ///
 416         /// PhysicalProject(outputVar)
 417         /// |
 418         /// Project(s)
 419         /// |
 420         /// Unnest
 421         ///
 422         /// where the unnest is over the group aggregate var and the output var
 423         /// is either a reference to the group aggregate var or to a constant, it returns the
 424         /// translation of the ouput var.
 425         /// </summary>
 426         /// <param name="n"></param>
 427         /// <returns></returns>
 428         private Node VisitCollect(Node n)
 429         {
 430             //Make sure the only children are projects over unnest
 431             Node currentNode = n.Child0;
 432             Dictionary<Var, Node> constantDefinitions = new Dictionary<Var, Node>();
 433             while (currentNode.Child0.Op.OpType == OpType.Project)
 434             {
 435                 currentNode = currentNode.Child0;
 436                 //Visit the VarDefListOp child
 437                 if (VisitDefault(currentNode.Child1) == null)
 438                 {
 439                     return null;
 440                 }
 441                 foreach (Node definitionNode in currentNode.Child1.Children)
 442                 {
 443                     if (IsConstant(definitionNode.Child0))
 444                     {
 445                         constantDefinitions.Add(((VarDefOp)definitionNode.Op).Var, definitionNode.Child0);
 446                     }
 447                 }
 448             }
 449
 450             if (currentNode.Child0.Op.OpType != OpType.Unnest)
 451             {
 452                 return null;
 453             }
 454
 455             // Handle the unnest
 456             UnnestOp unnestOp = (UnnestOp)currentNode.Child0.Op;
 457             GroupAggregateVarRefInfo groupAggregateVarRefInfo;
 458             if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(unnestOp.Var, out groupAggregateVarRefInfo))
 459             {
 460                 if (_targetGroupAggregateVarInfo == null)
 461                 {
 462                     _targetGroupAggregateVarInfo = groupAggregateVarRefInfo.GroupAggregateVarInfo;
 463                 }
 464                 else if (_targetGroupAggregateVarInfo != groupAggregateVarRefInfo.GroupAggregateVarInfo)
 465                 {
 466                     return null;
 467                 }
 468                 if (!_isUnnested)
 469                 {
 470                     return null;
 471                 }
 472             }
 473             else
 474             {
 475                 return null;
 476             }
 477
 478             PhysicalProjectOp physicalProjectOp = (PhysicalProjectOp)n.Child0.Op;
 479             PlanCompiler.Assert(physicalProjectOp.Outputs.Count == 1, "PhysicalProject should only have one output at this stage");
 480             Var outputVar = physicalProjectOp.Outputs[0];
 481
 482             Node computationTemplate = TranslateOverGroupAggregateVar(outputVar, null);
 483             if (computationTemplate != null)
 484             {
 485                 _isUnnested = true;
 486                 return computationTemplate;
 487             }
 488
 489             Node constantDefinitionNode;
 490             if (constantDefinitions.TryGetValue(outputVar, out constantDefinitionNode))
 491             {
 492                 _isUnnested = true;
 493                 return constantDefinitionNode;
 494             }
 495             return null;
 496         }
 497
 498         /// <summary>
 499         /// Determines whether the given Node is a constant subtree
 500         /// It only recognizes any of the constant base ops
 501         /// and possibly casts over these nodes.
 502         /// </summary>
 503         /// <param name="node"></param>
 504         /// <returns></returns>
 505         private static bool IsConstant(Node node)
 506         {
 507             Node currentNode = node;
 508             while (currentNode.Op.OpType == OpType.Cast)
 509             {
 510                 currentNode = currentNode.Child0;
 511             }
 512             return PlanCompilerUtil.IsConstantBaseOp(currentNode.Op.OpType);
 513         }
 514
 515         /// <summary>
 516         /// (1) If the given var or the given property of the given var are defined over a group aggregate var,
 517         /// (2) and if that group aggregate var matches the var represented by represented by _targetGroupAggregateVarInfo
 518         /// if any
 519         ///
 520         /// it returns the corresponding translation over the group aggregate var. Also, if _targetGroupAggregateVarInfo
 521         /// is not set, it sets it to the group aggregate var representing the referenced var.
 522         /// </summary>
 523         /// <param name="var"></param>
 524         /// <param name="property"></param>
 525         /// <returns></returns>
 526         private Node TranslateOverGroupAggregateVar(Var var, EdmMember property)
 527         {
 528             GroupAggregateVarRefInfo groupAggregateVarRefInfo;
 529             EdmMember localProperty;
 530             if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(var, out groupAggregateVarRefInfo))
 531             {
 532                 localProperty = property;
 533             }
 534             else if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(var, property, out  groupAggregateVarRefInfo))
 535             {
 536                 localProperty = null;
 537             }
 538             else
 539             {
 540                 return null;
 541             }
 542
 543             if (_targetGroupAggregateVarInfo == null)
 544             {
 545                 _targetGroupAggregateVarInfo = groupAggregateVarRefInfo.GroupAggregateVarInfo;
 546                 _isUnnested = groupAggregateVarRefInfo.IsUnnested;
 547             }
 548             else if (_targetGroupAggregateVarInfo != groupAggregateVarRefInfo.GroupAggregateVarInfo || _isUnnested != groupAggregateVarRefInfo.IsUnnested)
 549             {
 550                 return null;
 551             }
 552
 553             Node computationTemplate = groupAggregateVarRefInfo.Computation;
 554             if (localProperty != null)
 555             {
 556                 computationTemplate = this._command.CreateNode(this._command.CreatePropertyOp(localProperty), computationTemplate);
 557             }
 558             return computationTemplate;
 559         }
 560
 561         /// <summary>
 562         /// Default processing for nodes.
 563         /// Visits the children and if any child has changed it creates a new node
 564         /// for the parent.
 565         /// If the reference of the child node did not change, the child node did not change either,
 566         /// this is because a node can only be reused "as is" when building a template.
 567         /// </summary>
 568         /// <param name="n"></param>
 569         /// <returns></returns>
 570         protected override Node VisitDefault(Node n)
 571         {
 572             List<Node> newChildren = new List<Node>(n.Children.Count);
 573             bool anyChildChanged = false;
 574             for (int i = 0; i < n.Children.Count; i++)
 575             {
 576                 Node processedChild = VisitNode(n.Children[i]);
 577                 if (processedChild == null)
 578                 {
 579                     return null;
 580                 }
 581                 if (!anyChildChanged && !Object.ReferenceEquals(n.Children[i], processedChild))
 582                 {
 583                     anyChildChanged = true;
 584                 }
 585                 newChildren.Add(processedChild);
 586             }
 587
 588             if (!anyChildChanged)
 589             {
 590                 return n;
 591             }
 592             else
 593             {
 594                 return _command.CreateNode(n.Op, newChildren);
 595             }
 596         }
 597
 598         #region Unsupported node types
 599
 600         protected override Node VisitRelOpDefault(RelOp op, Node n)
 601         {
 602             return null;
 603         }
 604
 605         public override Node Visit(AggregateOp op, Node n)
 606         {
 607             return null;
 608         }
 609
 610         public override Node Visit(CollectOp op, Node n)
 611         {
 612             return null;
 613         }
 614
 615         public override Node Visit(ElementOp op, Node n)
 616         {
 617             return null;
 618         }
 619
 620         #endregion
 621
 622         #endregion
 623     }
 624
 625     /// <summary>
 626     /// A visitor that collects all group aggregates and the corresponding function aggregates
 627     /// that are defined over them, referred to as 'candidate aggregates'. The candidate aggregates are aggregates
 628     /// that have an argument that has the corresponding group aggregate as the only external reference
 629     /// </summary>
 630     internal class GroupAggregateRefComputingVisitor : BasicOpVisitor
 631     {
 632         #region private state
 633         private readonly Command _command;
 634         private readonly GroupAggregateVarInfoManager _groupAggregateVarInfoManager = new GroupAggregateVarInfoManager();
 635         private readonly Dictionary<Node, Node> _childToParent = new Dictionary<Node, Node>();
 636         #endregion
 637
 638         #region 'Public'
 639         /// <summary>
 640         /// Produces a list of all GroupAggregateVarInfos, each of which represents a single group aggregate
 641         /// and it candidate function aggregates. It also produces a delegate that given a child node returns the parent node
 642         /// </summary>
 643         /// <param name="itree"></param>
 644         /// <param name="tryGetParent"></param>
 645         /// <returns></returns>
 646         internal static IEnumerable<GroupAggregateVarInfo> Process(Command itree, out TryGetValue tryGetParent)
 647         {
 648             GroupAggregateRefComputingVisitor groupRefComputingVisitor = new GroupAggregateRefComputingVisitor(itree);
 649             groupRefComputingVisitor.VisitNode(itree.Root);
 650             tryGetParent = groupRefComputingVisitor._childToParent.TryGetValue;
 651
 652             return groupRefComputingVisitor._groupAggregateVarInfoManager.GroupAggregateVarInfos;
 653         }
 654         #endregion
 655
 656         #region Private Constructor
 657         /// <summary>
 658         /// Private constructor
 659         /// </summary>
 660         /// <param name="itree"></param>
 661         private GroupAggregateRefComputingVisitor(Command itree)
 662         {
 663             this._command = itree;
 664         }
 665         #endregion
 666
 667         #region Visitor Methods
 668
 669         #region AncillaryOps
 670         /// <summary>
 671         /// Determines whether the var or a property of the var (if the var is defined as a NewRecord)
 672         /// is defined exclusively over a single group aggregate. If so, it registers it as such with the
 673         /// group aggregate var info manager.
 674         /// </summary>
 675         /// <param name="op"></param>
 676         /// <param name="n"></param>
 677         public override void Visit(VarDefOp op, Node n)
 678         {
 679             VisitDefault(n);
 680
 681             Node definingNode = n.Child0;
 682             Op definingNodeOp = definingNode.Op;
 683
 684             GroupAggregateVarInfo referencedVarInfo;
 685             Node templateNode;
 686             bool isUnnested;
 687             if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(definingNode, true, this._command, this._groupAggregateVarInfoManager, out  referencedVarInfo, out templateNode, out isUnnested))
 688             {
 689                 _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested);
 690             }
 691             else if (definingNodeOp.OpType == OpType.NewRecord)
 692             {
 693                 NewRecordOp newRecordOp = (NewRecordOp)definingNodeOp;
 694                 for (int i = 0; i < definingNode.Children.Count; i++)
 695                 {
 696                     Node argumentNode = definingNode.Children[i];
 697                     if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(argumentNode, true, this._command, this._groupAggregateVarInfoManager, out referencedVarInfo, out templateNode, out isUnnested))
 698                     {
 699                         _groupAggregateVarInfoManager.Add(op.Var, referencedVarInfo, templateNode, isUnnested, newRecordOp.Properties[i]);
 700                     }
 701                 }
 702             }
 703         }
 704
 705         #endregion
 706
 707         #region RelOp Visitors
 708         /// <summary>
 709         /// Registers the group aggregate var with the group aggregate var info manager
 710         /// </summary>
 711         /// <param name="op"></param>
 712         /// <param name="n"></param>
 713         public override void Visit(GroupByIntoOp op, Node n)
 714         {
 715             VisitGroupByOp(op, n);
 716             foreach (Node child in n.Child3.Children)
 717             {
 718                 Var groupAggregateVar = ((VarDefOp)child.Op).Var;
 719                 GroupAggregateVarRefInfo groupAggregateVarRefInfo;
 720                 // If the group by is over a group, it may be already tracked as referencing a group var
 721                 // An optimization would be to separately track this groupAggregateVar too, for the cases when the aggregate can
 722                 // not be pushed to the group by node over which this one is defined but can be propagated to this group by node.
 723                 if (!_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(groupAggregateVar, out groupAggregateVarRefInfo))
 724                 {
 725                     _groupAggregateVarInfoManager.Add(groupAggregateVar, new GroupAggregateVarInfo(n, groupAggregateVar), this._command.CreateNode(this._command.CreateVarRefOp(groupAggregateVar)), false);
 726                 }
 727             }
 728         }
 729
 730         /// <summary>
 731         /// If the unnestOp's var is defined as a reference of a group aggregate var,
 732         /// then the columns it produces should be registered too, but as 'unnested' references
 733         /// </summary>
 734         /// <param name="op">the unnestOp</param>
 735         /// <param name="n">current subtree</param>
 736         /// <returns>modified subtree</returns>
 737         public override void Visit(UnnestOp op, Node n)
 738         {
 739             VisitDefault(n);
 740             GroupAggregateVarRefInfo groupAggregateVarRefInfo;
 741             if (_groupAggregateVarInfoManager.TryGetReferencedGroupAggregateVarInfo(op.Var, out groupAggregateVarRefInfo))
 742             {
 743                 PlanCompiler.Assert(op.Table.Columns.Count == 1, "Expected one column before NTE");
 744                 _groupAggregateVarInfoManager.Add(op.Table.Columns[0], groupAggregateVarRefInfo.GroupAggregateVarInfo, groupAggregateVarRefInfo.Computation, true);
 745             }
 746         }
 747
 748         #endregion
 749
 750         #region ScalarOps Visitors
 751         /// <summary>
 752         /// If the op is a collection aggregate function it checks whether its arguement can be translated over
 753         /// a single group aggregate var. If so, it is tracked as a candidate to be pushed into that
 754         /// group by into node.
 755         /// </summary>
 756         /// <param name="op"></param>
 757         /// <param name="n"></param>
 758         public override void Visit(FunctionOp op, Node n)
 759         {
 760             VisitDefault(n);
 761             if (!PlanCompilerUtil.IsCollectionAggregateFunction(op, n))
 762             {
 763                 return;
 764             }
 765             PlanCompiler.Assert(n.Children.Count == 1, "Aggregate Function must have one argument");
 766
 767             Node argumentNode = n.Child0;
 768
 769             GroupAggregateVarInfo referencedGroupAggregateVarInfo;
 770             Node templateNode;
 771             bool isUnnested;
 772             if (GroupAggregateVarComputationTranslator.TryTranslateOverGroupAggregateVar(n.Child0, false, _command, _groupAggregateVarInfoManager, out referencedGroupAggregateVarInfo, out templateNode, out isUnnested)
 773                 && (isUnnested || AggregatePushdownUtil.IsVarRefOverGivenVar(templateNode, referencedGroupAggregateVarInfo.GroupAggregateVar)))
 774             {
 775                 referencedGroupAggregateVarInfo.CandidateAggregateNodes.Add(new KeyValuePair<Node, Node>(n, templateNode));
 776             }
 777         }
 778
 779         #endregion
 780
 781         /// <summary>
 782         /// Default visitor for nodes.
 783         /// It tracks the child-parent relationship.
 784         /// </summary>
 785         /// <param name="n"></param>
 786         protected override void VisitDefault(Node n)
 787         {
 788             VisitChildren(n);
 789             foreach (Node child in n.Children)
 790             {
 791                 //No need to track terminal nodes, plus some of these may be reused.
 792                 if (child.Op.Arity != 0)
 793                 {
 794                     _childToParent.Add(child, n);
 795                 }
 796             }
 797         }
 798         #endregion
 799
 800     }
 801
 802     /// <summary>
 803     /// Utility class to gather helper methods used by more than one class in the Aggregate Pushdown feature.
 804     /// </summary>
 805     internal static class AggregatePushdownUtil
 806     {
 807         /// <summary>
 808         /// Determines whether the given node is a VarRef over the given var
 809         /// </summary>
 810         /// <param name="node"></param>
 811         /// <param name="var"></param>
 812         /// <returns></returns>
 813         internal static bool IsVarRefOverGivenVar(Node node, Var var)
 814         {
 815             if (node.Op.OpType != OpType.VarRef)
 816             {
 817                 return false;
 818             }
 819             return ((VarRefOp)node.Op).Var == var;
 820         }
 821     }
 822
 823     /// <summary>
 824     /// The Aggregate Pushdown feature tries to identify function aggregates defined over a
 825     /// group aggregate and push their definitions in the group by into node corresponding to
 826     /// the group aggregate.
 827     /// </summary>
 828     internal class AggregatePushdown
 829     {
 830         #region Private fields
 831         private readonly Command m_command;
 832         private TryGetValue m_tryGetParent;
 833         #endregion
 834
 835         #region Private Constructor
 836         private AggregatePushdown(Command command)
 837         {
 838             this.m_command = command;
 839         }
 840         #endregion
 841
 842         #region 'Public' Surface
 843         /// <summary>
 844         /// Apply Aggregate Pushdown over the tree in the given plan complier state.
 845         /// </summary>
 846         /// <param name="planCompilerState"></param>
 847         internal static void Process(PlanCompiler planCompilerState)
 848         {
 849             AggregatePushdown aggregatePushdown = new AggregatePushdown(planCompilerState.Command);
 850             aggregatePushdown.Process();
 851         }
 852         #endregion
 853
 854         #region Private Methods
 855
 856         /// <summary>
 857         /// The main driver
 858         /// </summary>
 859         private void Process()
 860         {
 861             IEnumerable<GroupAggregateVarInfo> groupAggregateVarInfos = GroupAggregateRefComputingVisitor.Process(m_command, out m_tryGetParent);
 862             foreach (GroupAggregateVarInfo groupAggregateVarInfo in groupAggregateVarInfos)
 863             {
 864                 if (groupAggregateVarInfo.HasCandidateAggregateNodes)
 865                 {
 866                     foreach (KeyValuePair<Node, Node> candidate in groupAggregateVarInfo.CandidateAggregateNodes)
 867                     {
 868                         TryProcessCandidate(candidate, groupAggregateVarInfo);
 869                     }
 870                 }
 871             }
 872         }
 873
 874         /// <summary>
 875         /// Try to push the given function aggregate candidate to the corresponding group into node.
 876         /// The candidate can be pushed if all ancestors of the group into node up to the least common
 877         /// ancestor between the group into node and the function aggregate have one of the following node op types:
 878         ///     Project
 879         ///     Filter
 880         ///     ConstraintSortOp
 881         /// </summary>
 882         /// <param name="command"></param>
 883         /// <param name="candidate"></param>
 884         /// <param name="groupAggregateVarInfo"></param>
 885         /// <param name="m_childToParent"></param>
 886         private void TryProcessCandidate(
 887             KeyValuePair<Node, Node> candidate,
 888             GroupAggregateVarInfo groupAggregateVarInfo)
 889         {
 890             IList<Node> functionAncestors;
 891             IList<Node> groupByAncestors;
 892             Node definingGroupNode = groupAggregateVarInfo.DefiningGroupNode;
 893             FindPathsToLeastCommonAncestor(candidate.Key, definingGroupNode, out functionAncestors, out groupByAncestors);
 894
 895             //Check whether all ancestors of the GroupByInto node are of type that we support propagating through
 896             if (!AreAllNodesSupportedForPropagation(groupByAncestors))
 897             {
 898                 return;
 899             }
 900
 901             //Add the function to the group by node
 902             GroupByIntoOp definingGroupOp = (GroupByIntoOp)definingGroupNode.Op;
 903             PlanCompiler.Assert(definingGroupOp.Inputs.Count == 1, "There should be one input var to GroupByInto at this stage");
 904             Var inputVar = definingGroupOp.Inputs.First;
 905             FunctionOp functionOp = (FunctionOp)candidate.Key.Op;
 906
 907             //
 908             // Remap the template from referencing the groupAggregate var to reference the input to
 909             // the group by into
 910             //
 911             Node argumentNode = OpCopier.Copy(m_command, candidate.Value);
 912             Dictionary<Var, Var> dictionary = new Dictionary<Var, Var>(1);
 913             dictionary.Add(groupAggregateVarInfo.GroupAggregateVar, inputVar);
 914             VarRemapper remapper = new VarRemapper(m_command, dictionary);
 915             remapper.RemapSubtree(argumentNode);
 916
 917             Node newFunctionDefiningNode = m_command.CreateNode(
 918                 m_command.CreateAggregateOp(functionOp.Function, false),
 919                 argumentNode);
 920
 921             Var newFunctionVar;
 922             Node varDefNode = m_command.CreateVarDefNode(newFunctionDefiningNode, out newFunctionVar);
 923
 924             // Add the new aggregate to the list of aggregates
 925             definingGroupNode.Child2.Children.Add(varDefNode);
 926             GroupByIntoOp groupByOp = (GroupByIntoOp)definingGroupNode.Op;
 927             groupByOp.Outputs.Set(newFunctionVar);
 928
 929             //Propagate the new var throught the ancestors of the GroupByInto
 930             for (int i = 0; i < groupByAncestors.Count; i++)
 931             {
 932                 Node groupByAncestor = groupByAncestors[i];
 933                 if (groupByAncestor.Op.OpType == OpType.Project)
 934                 {
 935                     ProjectOp ancestorProjectOp = (ProjectOp)groupByAncestor.Op;
 936                     ancestorProjectOp.Outputs.Set(newFunctionVar);
 937                 }
 938             }
 939
 940             //Update the functionNode
 941             candidate.Key.Op = m_command.CreateVarRefOp(newFunctionVar);
 942             candidate.Key.Children.Clear();
 943         }
 944
 945         /// <summary>
 946         /// Check whether all nodes in the given list of nodes are of types
 947         /// that we know how to propagate an aggregate through
 948         /// </summary>
 949         /// <param name="nodes"></param>
 950         /// <returns></returns>
 951         private static bool AreAllNodesSupportedForPropagation(IList<Node> nodes)
 952         {
 953             foreach (Node node in nodes)
 954             {
 955                 if (node.Op.OpType != OpType.Project
 956                     && node.Op.OpType != OpType.Filter
 957                     && node.Op.OpType != OpType.ConstrainedSort
 958                     )
 959                 {
 960                     return false;
 961                 }
 962             }
 963             return true;
 964         }
 965
 966         /// <summary>
 967         /// Finds the paths from each of node1 and node2 to their least common ancestor
 968         /// </summary>
 969         /// <param name="node1"></param>
 970         /// <param name="node2"></param>
 971         /// <param name="ancestors1"></param>
 972         /// <param name="ancestors2"></param>
 973         private void FindPathsToLeastCommonAncestor(Node node1, Node node2, out IList<Node> ancestors1, out IList<Node> ancestors2)
 974         {
 975             ancestors1 = FindAncestors(node1);
 976             ancestors2 = FindAncestors(node2);
 977
 978             int currentIndex1 = ancestors1.Count - 1;
 979             int currentIndex2 = ancestors2.Count - 1;
 980             while (ancestors1[currentIndex1] == ancestors2[currentIndex2])
 981             {
 982                 currentIndex1--;
 983                 currentIndex2--;
 984             }
 985
 986             for (int i = ancestors1.Count - 1; i > currentIndex1; i--)
 987             {
 988                 ancestors1.RemoveAt(i);
 989             }
 990             for (int i = ancestors2.Count - 1; i > currentIndex2; i--)
 991             {
 992                 ancestors2.RemoveAt(i);
 993             }
 994         }
 995
 996         /// <summary>
 997         /// Finds all ancestors of the given node.
 998         /// </summary>
 999         /// <param name="node"></param>
1000         /// <returns>An ordered list of the all the ancestors of the given node starting from the immediate parent
1001         /// to the root of the tree</returns>
1002         private IList<Node> FindAncestors(Node node)
1003         {
1004             List<Node> ancestors = new List<Node>();
1005             Node currentNode = node;
1006             Node ancestor;
1007             while (m_tryGetParent(currentNode, out ancestor))
1008             {
1009                 ancestors.Add(ancestor);
1010                 currentNode = ancestor;
1011             }
1012             return ancestors;
1013         }
1014         #endregion
1015     }
1016 }