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

   1 //---------------------------------------------------------------------
   2 // <copyright file="TransformationRules.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  [....]
   7 // @backupOwner [....]
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Collections.ObjectModel;
  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.Linq;
  31 using System.Data.Metadata.Edm;
  32 using System.Data.Query.InternalTrees;
  33
  34 namespace System.Data.Query.PlanCompiler
  35 {
  36     internal class TransformationRulesContext : RuleProcessingContext
  37     {
  38         #region public methods and properties
  39
  40         /// <summary>
  41         /// Whether any rule was applied that may have caused modifications such that projection pruning
  42         /// may be useful
  43         /// </summary>
  44         internal bool ProjectionPrunningRequired { get { return this.m_projectionPrunningRequired; } }
  45
  46         /// <summary>
  47         /// Whether any rule was applied that may have caused modifications such that reapplying
  48         /// the nullability rules may be useful
  49         /// </summary>
  50         internal bool ReapplyNullabilityRules { get { return this.m_reapplyNullabilityRules; } }
  51
  52         /// <summary>
  53         /// Remap the given subree using the current remapper
  54         /// </summary>
  55         /// <param name="subTree"></param>
  56         internal void RemapSubtree(Node subTree)
  57         {
  58             this.m_remapper.RemapSubtree(subTree);
  59         }
  60
  61         /// <summary>
  62         /// Adds a mapping from oldVar to newVar
  63         /// </summary>
  64         /// <param name="oldVar"></param>
  65         /// <param name="newVar"></param>
  66         internal void AddVarMapping(Var oldVar, Var newVar)
  67         {
  68             m_remapper.AddMapping(oldVar, newVar);
  69             m_remappedVars.Set(oldVar);
  70         }
  71
  72         /// <summary>
  73         /// "Remap" an expression tree, replacing all references to vars in varMap with
  74         /// copies of the corresponding expression
  75         /// The subtree is modified *inplace* - it is the caller's responsibility to make
  76         /// a copy of the subtree if necessary.
  77         /// The "replacement" expression (the replacement for the VarRef) is copied and then
  78         /// inserted into the appropriate location into the subtree.
  79         ///
  80         /// Note: we only support replacements in simple ScalarOp trees. This must be
  81         /// validated by the caller.
  82         ///
  83         /// </summary>
  84         /// <param name="node">Current subtree to process</param>
  85         /// <param name="varMap"></param>
  86         /// <returns>The updated subtree</returns>
  87         internal Node ReMap(Node node, Dictionary<Var, Node> varMap)
  88         {
  89             PlanCompiler.Assert(node.Op.IsScalarOp, "Expected a scalarOp: Found " + Dump.AutoString.ToString(node.Op.OpType));
  90
  91             // Replace varRefOps by the corresponding expression in the map, if any
  92             if (node.Op.OpType == OpType.VarRef)
  93             {
  94                 VarRefOp varRefOp = node.Op as VarRefOp;
  95                 Node newNode = null;
  96                 if (varMap.TryGetValue(varRefOp.Var, out newNode))
  97                 {
  98                     newNode = this.Copy(newNode);
  99                     return newNode;
 100                 }
 101                 else
 102                 {
 103                     return node;
 104                 }
 105             }
 106
 107             // Simply process the result of the children.
 108             for (int i = 0; i < node.Children.Count; i++)
 109             {
 110                 node.Children[i] = ReMap(node.Children[i], varMap);
 111             }
 112
 113             // We may have changed something deep down
 114             this.Command.RecomputeNodeInfo(node);
 115             return node;
 116         }
 117
 118         /// <summary>
 119         /// Makes a copy of the appropriate subtree - with a simple accelerator for VarRefOp
 120         /// since that's likely to be the most command case
 121         /// </summary>
 122         /// <param name="node">the subtree to copy</param>
 123         /// <returns>the copy of the subtree</returns>
 124         internal Node Copy(Node node)
 125         {
 126             if (node.Op.OpType == OpType.VarRef)
 127             {
 128                 VarRefOp op = node.Op as VarRefOp;
 129                 return this.Command.CreateNode(this.Command.CreateVarRefOp(op.Var));
 130             }
 131             else
 132             {
 133                 return OpCopier.Copy(this.Command, node);
 134             }
 135         }
 136
 137         /// <summary>
 138         /// Checks to see if the current subtree only contains ScalarOps
 139         /// </summary>
 140         /// <param name="node">current subtree</param>
 141         /// <returns>true, if the subtree contains only ScalarOps</returns>
 142         internal bool IsScalarOpTree(Node node)
 143         {
 144             int nodeCount = 0;
 145             return IsScalarOpTree(node, null, ref nodeCount);
 146         }
 147
 148         /// <summary>
 149         /// Is the given var guaranteed to be non-nullable with regards to the node
 150         /// that is currently being processed.
 151         /// True, if it is listed as such on any on the node infos on any of the
 152         /// current relop ancestors.
 153         /// </summary>
 154         /// <param name="var"></param>
 155         /// <returns></returns>
 156         internal bool IsNonNullable(Var var)
 157         {
 158             foreach (Node relOpAncestor in m_relOpAncestors)
 159             {
 160                 // Rules applied to the children of the relOpAncestor may have caused it change.
 161                 // Thus, if the node is used, it has to have its node info recomputed
 162                 Command.RecomputeNodeInfo(relOpAncestor);
 163                 ExtendedNodeInfo nodeInfo = Command.GetExtendedNodeInfo(relOpAncestor);
 164                 if (nodeInfo.NonNullableVisibleDefinitions.IsSet(var))
 165                 {
 166                     return true;
 167                 }
 168                 else if (nodeInfo.LocalDefinitions.IsSet(var))
 169                 {
 170                     //The var is defined on this ancestor but is not non-nullable,
 171                     // therefore there is no need to further check other ancestors
 172                     return false;
 173                 }
 174             }
 175             return false;
 176         }
 177
 178         /// <summary>
 179         /// Is it safe to use a null sentinel with any value?
 180         /// It may not be safe if:
 181         /// 1. The top most sort includes null sentinels. If the null sentinel is replaced with a different value
 182         /// and is used as a sort key it may change the sorting results
 183         /// 2. If any of the ancestors is Distinct, GroupBy, Intersect or Except,
 184         /// because the null sentinel may be used as a key.
 185         /// 3. If the null sentinel is defined in the left child of an apply it may be used at the right side,
 186         /// thus in these cases we also verify that the right hand side does not have any Distinct, GroupBy,
 187         /// Intersect or Except.
 188         /// </summary>
 189         internal bool CanChangeNullSentinelValue
 190         {
 191             get
 192             {
 193                 //Is there a sort that includes null sentinels
 194                 if (this.m_compilerState.HasSortingOnNullSentinels)
 195                 {
 196                     return false;
 197                 }
 198
 199                 //Is any of the ancestors Distinct, GroupBy, Intersect or Except
 200                 if (this.m_relOpAncestors.Any(a => IsOpNotSafeForNullSentinelValueChange(a.Op.OpType)))
 201                 {
 202                     return false;
 203                 }
 204
 205                 // Is the null sentinel defined in the left child of an apply and if so,
 206                 // does the right hand side have any Distinct, GroupBy, Intersect or Except.
 207                 var applyAncestors = this.m_relOpAncestors.Where(a =>
 208                          a.Op.OpType == OpType.CrossApply ||
 209                          a.Op.OpType == OpType.OuterApply);
 210
 211                 //If the sentinel comes from the right hand side it is ok.
 212                 foreach (Node applyAncestor in applyAncestors)
 213                 {
 214                     if (!this.m_relOpAncestors.Contains(applyAncestor.Child1) && HasOpNotSafeForNullSentinelValueChange(applyAncestor.Child1))
 215                     {
 216                         return false;
 217                     }
 218                 }
 219                 return true;
 220             }
 221         }
 222
 223         /// <summary>
 224         /// Is the op not safe for null sentinel value change
 225         /// </summary>
 226         /// <param name="optype"></param>
 227         /// <returns></returns>
 228         internal static bool IsOpNotSafeForNullSentinelValueChange(OpType optype)
 229         {
 230             return optype == OpType.Distinct ||
 231                     optype == OpType.GroupBy ||
 232                     optype == OpType.Intersect ||
 233                     optype == OpType.Except;
 234         }
 235
 236         /// <summary>
 237         /// Does the given subtree contain a node with an op that
 238         /// is not safer for null sentinel value change
 239         /// </summary>
 240         /// <param name="n"></param>
 241         /// <returns></returns>
 242         internal static bool HasOpNotSafeForNullSentinelValueChange(Node n)
 243         {
 244             if (IsOpNotSafeForNullSentinelValueChange(n.Op.OpType))
 245             {
 246                 return true;
 247             }
 248             foreach (Node child in n.Children)
 249             {
 250                 if (HasOpNotSafeForNullSentinelValueChange(child))
 251                 {
 252                     return true;
 253                 }
 254             }
 255             return false;
 256         }
 257
 258         /// <summary>
 259         /// Is this is a scalar-op tree? Also return a dictionary of var refcounts (ie)
 260         /// for each var encountered in the tree, determine the number of times it has
 261         /// been seen
 262         /// </summary>
 263         /// <param name="node">current subtree</param>
 264         /// <param name="varRefMap">dictionary of var refcounts to fill in</param>
 265         /// <returns></returns>
 266         internal bool IsScalarOpTree(Node node, Dictionary<Var, int> varRefMap)
 267         {
 268             PlanCompiler.Assert(varRefMap != null, "Null varRef map");
 269
 270             int nodeCount = 0;
 271             return IsScalarOpTree(node, varRefMap, ref nodeCount);
 272         }
 273
 274         /// <summary>
 275         /// Get a mapping from Var->Expression for a VarDefListOp tree. This information
 276         /// will be used by later stages to replace all references to the Vars by the
 277         /// corresponding expressions
 278         ///
 279         /// This function uses a few heuristics along the way. It uses the varRefMap
 280         /// parameter to determine if a computed Var (defined by this VarDefListOp)
 281         /// has been referenced multiple times, and if it has, it checks to see if
 282         /// the defining expression is too big (> 100 nodes). This is to avoid
 283         /// bloating up the entire query tree with too many copies.
 284         ///
 285         /// </summary>
 286         /// <param name="varDefListNode">The varDefListOp subtree</param>
 287         /// <param name="varRefMap">ref counts for each referenced var</param>
 288         /// <returns>mapping from Var->replacement xpressions</returns>
 289         internal Dictionary<Var, Node> GetVarMap(Node varDefListNode, Dictionary<Var, int> varRefMap)
 290         {
 291             VarDefListOp varDefListOp = (VarDefListOp)varDefListNode.Op;
 292
 293             Dictionary<Var, Node> varMap = new Dictionary<Var, Node>();
 294             foreach (Node chi in varDefListNode.Children)
 295             {
 296                 VarDefOp varDefOp = (VarDefOp)chi.Op;
 297                 int nonLeafNodeCount = 0;
 298                 int refCount = 0;
 299                 if (!IsScalarOpTree(chi.Child0, null, ref nonLeafNodeCount))
 300                 {
 301                     return null;
 302                 }
 303                 //
 304                 // More heuristics. If there are multiple references to this Var *and*
 305                 // the defining expression for the Var is "expensive" (ie) has larger than
 306                 // 100 nodes, then simply pretend that this is too hard to do
 307                 // Note: we check for more than 2 references, (rather than just more than 1) - this
 308                 // is simply to let some additional cases through
 309                 //
 310                 if ((nonLeafNodeCount > 100) &&
 311                     (varRefMap != null) &&
 312                     varRefMap.TryGetValue(varDefOp.Var, out refCount) &&
 313                     (refCount > 2))
 314                 {
 315                     return null;
 316                 }
 317
 318                 Node n;
 319                 if (varMap.TryGetValue(varDefOp.Var, out n))
 320                 {
 321                     PlanCompiler.Assert(n == chi.Child0, "reusing varDef for different Node?");
 322                 }
 323                 else
 324                 {
 325                     varMap.Add(varDefOp.Var, chi.Child0);
 326                 }
 327             }
 328
 329             return varMap;
 330         }
 331
 332         /// <summary>
 333         /// Builds a NULLIF expression (ie) a Case expression that looks like
 334         ///    CASE WHEN v is null THEN null ELSE expr END
 335         /// where v is the conditionVar parameter, and expr is the value of the expression
 336         /// when v is non-null
 337         /// </summary>
 338         /// <param name="conditionVar">null discriminator var</param>
 339         /// <param name="expr">expression</param>
 340         /// <returns></returns>
 341         internal Node BuildNullIfExpression(Var conditionVar, Node expr)
 342         {
 343             VarRefOp varRefOp = this.Command.CreateVarRefOp(conditionVar);
 344             Node varRefNode = this.Command.CreateNode(varRefOp);
 345             Node whenNode = this.Command.CreateNode(this.Command.CreateConditionalOp(OpType.IsNull), varRefNode);
 346             Node elseNode = expr;
 347             Node thenNode = this.Command.CreateNode(this.Command.CreateNullOp(elseNode.Op.Type));
 348             Node caseNode = this.Command.CreateNode(this.Command.CreateCaseOp(elseNode.Op.Type), whenNode, thenNode, elseNode);
 349
 350             return caseNode;
 351         }
 352
 353         #region Rule Interactions
 354         /// <summary>
 355         /// Shut off filter pushdown for this subtree
 356         /// </summary>
 357         /// <param name="n"></param>
 358         internal void SuppressFilterPushdown(Node n)
 359         {
 360             m_suppressions[n] = n;
 361         }
 362
 363         /// <summary>
 364         /// Is filter pushdown shut off for this subtree?
 365         /// </summary>
 366         /// <param name="n"></param>
 367         /// <returns></returns>
 368         internal bool IsFilterPushdownSuppressed(Node n)
 369         {
 370             return m_suppressions.ContainsKey(n);
 371         }
 372
 373         /// <summary>
 374         /// Given a list of vars try to get one that is of type Int32
 375         /// </summary>
 376         /// <param name="varList"></param>
 377         /// <param name="int32Var"></param>
 378         /// <returns></returns>
 379         internal static bool TryGetInt32Var(IEnumerable<Var> varList, out Var int32Var)
 380         {
 381             foreach (Var v in varList)
 382             {
 383                 // Any Int32 var regardless of the fasets will do
 384                 System.Data.Metadata.Edm.PrimitiveTypeKind typeKind;
 385                 if (System.Data.Common.TypeHelpers.TryGetPrimitiveTypeKind(v.Type, out typeKind) && typeKind == System.Data.Metadata.Edm.PrimitiveTypeKind.Int32)
 386                 {
 387                     int32Var = v;
 388                     return true;
 389                 }
 390             }
 391             int32Var = null;
 392             return false;
 393         }
 394
 395         #endregion
 396
 397         #endregion
 398
 399         #region constructors
 400         internal TransformationRulesContext(PlanCompiler compilerState)
 401             : base(compilerState.Command)
 402         {
 403             m_compilerState = compilerState;
 404             m_remapper = new VarRemapper(compilerState.Command);
 405             m_suppressions = new Dictionary<Node, Node>();
 406             m_remappedVars = compilerState.Command.CreateVarVec();
 407         }
 408
 409         #endregion
 410
 411         #region private state
 412         private readonly PlanCompiler m_compilerState;
 413         private readonly VarRemapper m_remapper;
 414         private readonly Dictionary<Node, Node> m_suppressions;
 415         private readonly VarVec m_remappedVars;
 416         private bool m_projectionPrunningRequired = false;
 417         private bool m_reapplyNullabilityRules = false;
 418         private Stack<Node> m_relOpAncestors = new Stack<Node>();
 419 #if DEBUG
 420         /// <summary>
 421         /// Used to see all the applied rules.
 422         /// One way to use it is to put a conditional breakpoint at the end of
 423         /// PostProcessSubTree with the condition m_relOpAncestors.Count == 0
 424         /// </summary>
 425         internal readonly System.Text.StringBuilder appliedRules = new System.Text.StringBuilder();
 426 #endif
 427         #endregion
 428
 429         #region RuleProcessingContext Overrides
 430         /// <summary>
 431         /// Callback function to invoke *before* rules are applied.
 432         /// Calls the VarRemapper to update any Vars in this node, and recomputes
 433         /// the nodeinfo
 434         /// </summary>
 435         /// <param name="n"></param>
 436         internal override void PreProcess(Node n)
 437         {
 438             m_remapper.RemapNode(n);
 439             Command.RecomputeNodeInfo(n);
 440         }
 441
 442         /// <summary>
 443         /// Callback function to invoke *before* rules are applied.
 444         /// Calls the VarRemapper to update any Vars in the entire subtree
 445         /// If the given node has a RelOp it is pushed on the relOp ancestors stack.
 446         /// </summary>
 447         /// <param name="subTree"></param>
 448         internal override void PreProcessSubTree(Node subTree)
 449         {
 450             if (subTree.Op.IsRelOp)
 451             {
 452                 m_relOpAncestors.Push(subTree);
 453             }
 454
 455             if (m_remappedVars.IsEmpty)
 456             {
 457                 return;
 458             }
 459
 460             NodeInfo nodeInfo = this.Command.GetNodeInfo(subTree);
 461
 462             //We need to do remapping only if m_remappedVars overlaps with nodeInfo.ExternalReferences
 463             foreach (Var v in nodeInfo.ExternalReferences)
 464             {
 465                 if (m_remappedVars.IsSet(v))
 466                 {
 467                     m_remapper.RemapSubtree(subTree);
 468                     break;
 469                 }
 470             }
 471         }
 472
 473         /// <summary>
 474         /// If the given node has a RelOp it is popped from the relOp ancestors stack.
 475         /// </summary>
 476         /// <param name="subtree"></param>
 477         internal override void PostProcessSubTree(Node subtree)
 478         {
 479             if (subtree.Op.IsRelOp)
 480             {
 481                 PlanCompiler.Assert(m_relOpAncestors.Count != 0, "The RelOp ancestors stack is empty when post processing a RelOp subtree");
 482                 Node poppedNode = m_relOpAncestors.Pop();
 483                 PlanCompiler.Assert(Object.ReferenceEquals(subtree, poppedNode), "The popped ancestor is not equal to the root of the subtree being post processed");
 484             }
 485         }
 486
 487         /// <summary>
 488         /// Callback function to invoke *after* rules are applied
 489         /// Recomputes the node info, if this node has changed
 490         /// If the rule is among the rules after which projection pruning may be beneficial,
 491         /// m_projectionPrunningRequired is set to true.
 492         /// If the rule is among the rules after which reapplying the nullability rules may be beneficial,
 493         /// m_reapplyNullabilityRules is set to true.
 494         /// </summary>
 495         /// <param name="n"></param>
 496         /// <param name="rule">the rule that was applied</param>
 497         internal override void PostProcess(Node n, InternalTrees.Rule rule)
 498         {
 499             if (rule != null)
 500             {
 501 #if DEBUG
 502                 appliedRules.Append(rule.MethodName);
 503                 appliedRules.AppendLine();
 504 #endif
 505                 if (!this.m_projectionPrunningRequired && TransformationRules.RulesRequiringProjectionPruning.Contains(rule))
 506                 {
 507                     this.m_projectionPrunningRequired = true;
 508                 }
 509                 if (!this.m_reapplyNullabilityRules && TransformationRules.RulesRequiringNullabilityRulesToBeReapplied.Contains(rule))
 510                 {
 511                     this.m_reapplyNullabilityRules = true;
 512                 }
 513                 Command.RecomputeNodeInfo(n);
 514             }
 515         }
 516
 517         /// <summary>
 518         /// Get the hash value for this subtree
 519         /// </summary>
 520         /// <param name="node"></param>
 521         /// <returns></returns>
 522         internal override int GetHashCode(Node node)
 523         {
 524             NodeInfo nodeInfo = Command.GetNodeInfo(node);
 525             return nodeInfo.HashValue;
 526         }
 527         #endregion
 528
 529         #region private methods
 530         /// <summary>
 531         /// Check to see if the current subtree is a scalar-op subtree (ie) does
 532         /// the subtree only comprise of scalarOps?
 533         /// Additionally, compute the number of non-leaf nodes (ie) nodes with at least one child
 534         /// that are found in the subtree. Note that this count is approximate - it is only
 535         /// intended to be used as a hint. It is the caller's responsibility to initialize
 536         /// nodeCount to a sane value on entry into this function
 537         /// And finally, if the varRefMap parameter is non-null, we keep track of
 538         /// how often a Var is referenced within the subtree
 539         ///
 540         /// The non-leaf-node count and the varRefMap are used by GetVarMap to determine
 541         /// if expressions can be composed together
 542         /// </summary>
 543         /// <param name="node">root of the subtree</param>
 544         /// <param name="varRefMap">Ref counts for each Var encountered in the subtree</param>
 545         /// <param name="nonLeafNodeCount">count of non-leaf nodes encountered in the subtree</param>
 546         /// <returns>true, if this node only contains scalarOps</returns>
 547         private bool IsScalarOpTree(Node node, Dictionary<Var, int> varRefMap, ref int nonLeafNodeCount)
 548         {
 549             if (!node.Op.IsScalarOp)
 550             {
 551                 return false;
 552             }
 553
 554             if (node.HasChild0)
 555             {
 556                 nonLeafNodeCount++;
 557             }
 558
 559             if (varRefMap != null && node.Op.OpType == OpType.VarRef)
 560             {
 561                 VarRefOp varRefOp = (VarRefOp)node.Op;
 562                 int refCount;
 563                 if (!varRefMap.TryGetValue(varRefOp.Var, out refCount))
 564                 {
 565                     refCount = 1;
 566                 }
 567                 else
 568                 {
 569                     refCount++;
 570                 }
 571                 varRefMap[varRefOp.Var] = refCount;
 572             }
 573
 574             foreach (Node chi in node.Children)
 575             {
 576                 if (!IsScalarOpTree(chi, varRefMap, ref nonLeafNodeCount))
 577                 {
 578                     return false;
 579                 }
 580             }
 581             return true;
 582         }
 583         #endregion
 584     }
 585
 586     /// <summary>
 587     /// The list of all transformation rules to apply
 588     /// </summary>
 589     internal static class TransformationRules
 590     {
 591         /// <summary>
 592         /// A lookup table for built from all rules
 593         /// The lookup table is an array indexed by OpType and each entry has a list of rules.
 594         /// </summary>
 595         internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> AllRulesTable = BuildLookupTableForRules(AllRules);
 596
 597         /// <summary>
 598         /// A lookup table for built only from ProjectRules
 599         /// The lookup table is an array indexed by OpType and each entry has a list of rules.
 600         /// </summary>
 601         internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> ProjectRulesTable = BuildLookupTableForRules(ProjectOpRules.Rules);
 602
 603
 604         /// <summary>
 605         /// A lookup table built only from rules that use key info
 606         /// The lookup table is an array indexed by OpType and each entry has a list of rules.
 607         /// </summary>
 608         internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> PostJoinEliminationRulesTable = BuildLookupTableForRules(PostJoinEliminationRules);
 609
 610         /// <summary>
 611         /// A lookup table built only from rules that rely on nullability of vars and other rules
 612         /// that may be able to perform simplificatios if these have been applied.
 613         /// The lookup table is an array indexed by OpType and each entry has a list of rules.
 614         /// </summary>
 615         internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> NullabilityRulesTable = BuildLookupTableForRules(NullabilityRules);
 616
 617         /// <summary>
 618         /// A look-up table of rules that may cause modifications such that projection pruning may be useful
 619         /// after they have been applied.
 620         /// </summary>
 621         internal static readonly HashSet<InternalTrees.Rule> RulesRequiringProjectionPruning = InitializeRulesRequiringProjectionPruning();
 622
 623         /// <summary>
 624         /// A look-up table of rules that may cause modifications such that reapplying the nullability rules
 625         /// may be useful after they have been applied.
 626         /// </summary>
 627         internal static readonly HashSet<InternalTrees.Rule> RulesRequiringNullabilityRulesToBeReapplied = InitializeRulesRequiringNullabilityRulesToBeReapplied();
 628
 629
 630         #region private state maintenance
 631         private static List<InternalTrees.Rule> allRules;
 632         private static List<InternalTrees.Rule> AllRules
 633         {
 634             get
 635             {
 636                 if (allRules == null)
 637                 {
 638                     allRules = new List<InternalTrees.Rule>();
 639                     allRules.AddRange(ScalarOpRules.Rules);
 640                     allRules.AddRange(FilterOpRules.Rules);
 641                     allRules.AddRange(ProjectOpRules.Rules);
 642                     allRules.AddRange(ApplyOpRules.Rules);
 643                     allRules.AddRange(JoinOpRules.Rules);
 644                     allRules.AddRange(SingleRowOpRules.Rules);
 645                     allRules.AddRange(SetOpRules.Rules);
 646                     allRules.AddRange(GroupByOpRules.Rules);
 647                     allRules.AddRange(SortOpRules.Rules);
 648                     allRules.AddRange(ConstrainedSortOpRules.Rules);
 649                     allRules.AddRange(DistinctOpRules.Rules);
 650                 }
 651                 return allRules;
 652             }
 653         }
 654
 655         private static List<InternalTrees.Rule> postJoinEliminationRules;
 656         private static List<InternalTrees.Rule> PostJoinEliminationRules
 657         {
 658             get
 659             {
 660                 if (postJoinEliminationRules == null)
 661                 {
 662                     postJoinEliminationRules = new List<InternalTrees.Rule>();
 663                     postJoinEliminationRules.AddRange(ProjectOpRules.Rules); //these don't use key info per-se, but can help after the distinct op rules.
 664                     postJoinEliminationRules.AddRange(DistinctOpRules.Rules);
 665                     postJoinEliminationRules.AddRange(FilterOpRules.Rules);
 666                     postJoinEliminationRules.AddRange(JoinOpRules.Rules);
 667                     postJoinEliminationRules.AddRange(NullabilityRules);
 668                 }
 669                 return postJoinEliminationRules;
 670             }
 671         }
 672
 673         private static List<InternalTrees.Rule> nullabilityRules;
 674         private static List<InternalTrees.Rule> NullabilityRules
 675         {
 676             get
 677             {
 678                 if (nullabilityRules == null)
 679                 {
 680                     nullabilityRules = new List<InternalTrees.Rule>();
 681                     nullabilityRules.Add(ScalarOpRules.Rule_IsNullOverVarRef);
 682                     nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred1);
 683                     nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred2);
 684                     nullabilityRules.Add(ScalarOpRules.Rule_SimplifyCase);
 685                     nullabilityRules.Add(ScalarOpRules.Rule_NotOverConstantPred);
 686                 }
 687                 return nullabilityRules;
 688             }
 689         }
 690
 691         private static ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> BuildLookupTableForRules(IEnumerable<InternalTrees.Rule> rules)
 692         {
 693             ReadOnlyCollection<InternalTrees.Rule> NoRules = new ReadOnlyCollection<InternalTrees.Rule>(new InternalTrees.Rule[0]);
 694
 695             List<InternalTrees.Rule>[] lookupTable = new List<InternalTrees.Rule>[(int)OpType.MaxMarker];
 696
 697             foreach (InternalTrees.Rule rule in rules)
 698             {
 699                 List<InternalTrees.Rule> opRules = lookupTable[(int)rule.RuleOpType];
 700                 if (opRules == null)
 701                 {
 702                     opRules = new List<InternalTrees.Rule>();
 703                     lookupTable[(int)rule.RuleOpType] = opRules;
 704                 }
 705                 opRules.Add(rule);
 706             }
 707
 708             ReadOnlyCollection<InternalTrees.Rule>[] rulesPerType = new ReadOnlyCollection<InternalTrees.Rule>[lookupTable.Length];
 709             for (int i = 0; i < lookupTable.Length; ++i)
 710             {
 711                 if (null != lookupTable[i])
 712                 {
 713                     rulesPerType[i] = new ReadOnlyCollection<InternalTrees.Rule>(lookupTable[i].ToArray());
 714                 }
 715                 else
 716                 {
 717                     rulesPerType[i] = NoRules;
 718                 }
 719             }
 720             return new ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>>(rulesPerType);
 721         }
 722
 723         private static HashSet<InternalTrees.Rule> InitializeRulesRequiringProjectionPruning()
 724         {
 725             HashSet<InternalTrees.Rule> rulesRequiringProjectionPruning = new HashSet<InternalTrees.Rule>();
 726
 727             rulesRequiringProjectionPruning.Add(ApplyOpRules.Rule_OuterApplyOverProject);
 728
 729             rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject1);
 730             rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject2);
 731             rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject1);
 732             rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject2);
 733             rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_OuterJoinOverProject2);
 734
 735             rulesRequiringProjectionPruning.Add(ProjectOpRules.Rule_ProjectWithNoLocalDefs);
 736
 737             rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterOverProject);
 738             rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterWithConstantPredicate);
 739
 740             rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOverProject);
 741             rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions);
 742
 743             return rulesRequiringProjectionPruning;
 744         }
 745
 746         private static HashSet<InternalTrees.Rule> InitializeRulesRequiringNullabilityRulesToBeReapplied()
 747         {
 748             HashSet<InternalTrees.Rule> rulesRequiringNullabilityRulesToBeReapplied = new HashSet<InternalTrees.Rule>();
 749
 750             rulesRequiringNullabilityRulesToBeReapplied.Add(FilterOpRules.Rule_FilterOverLeftOuterJoin);
 751
 752             return rulesRequiringNullabilityRulesToBeReapplied;
 753         }
 754
 755         #endregion
 756
 757
 758         /// <summary>
 759         /// Apply the rules that belong to the specified group to the given query tree.
 760         /// </summary>
 761         /// <param name="compilerState"></param>
 762         /// <param name="rulesGroup"></param>
 763         internal static bool Process(PlanCompiler compilerState, TransformationRulesGroup rulesGroup)
 764         {
 765             ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rulesTable = null;
 766             switch (rulesGroup)
 767             {
 768                 case TransformationRulesGroup.All:
 769                     rulesTable = AllRulesTable;
 770                     break;
 771                 case TransformationRulesGroup.PostJoinElimination:
 772                     rulesTable = PostJoinEliminationRulesTable;
 773                     break;
 774                 case TransformationRulesGroup.Project:
 775                     rulesTable = ProjectRulesTable;
 776                     break;
 777             }
 778
 779             // If any rule has been applied after which reapplying nullability rules may be useful,
 780             // reapply nullability rules.
 781             bool projectionPrunningRequired;
 782             if (Process(compilerState, rulesTable, out projectionPrunningRequired))
 783             {
 784                 bool projectionPrunningRequired2;
 785                 Process(compilerState, NullabilityRulesTable, out projectionPrunningRequired2);
 786                 projectionPrunningRequired = projectionPrunningRequired || projectionPrunningRequired2;
 787             }
 788             return projectionPrunningRequired;
 789         }
 790
 791         /// <summary>
 792         /// Apply the rules that belong to the specified rules table to the given query tree.
 793         /// </summary>
 794         /// <param name="compilerState"></param>
 795         /// <param name="rulesTable"></param>
 796         /// <param name="projectionPruningRequired">is projection pruning  required after the rule application</param>
 797         /// <returns>Whether any rule has been applied after which reapplying nullability rules may be useful</returns>
 798         private static bool Process(PlanCompiler compilerState, ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rulesTable, out bool projectionPruningRequired)
 799         {
 800             RuleProcessor ruleProcessor = new RuleProcessor();
 801             TransformationRulesContext context = new TransformationRulesContext(compilerState);
 802             compilerState.Command.Root = ruleProcessor.ApplyRulesToSubtree(context, rulesTable, compilerState.Command.Root);
 803             projectionPruningRequired = context.ProjectionPrunningRequired;
 804             return context.ReapplyNullabilityRules;
 805         }
 806     }
 807
 808     /// <summary>
 809     /// Available groups of rules, not necessarily mutually exclusive
 810     /// </summary>
 811     internal enum TransformationRulesGroup
 812     {
 813         All,
 814         Project,
 815         PostJoinElimination
 816     }
 817
 818     #region ScalarOpRules
 819     /// <summary>
 820     /// Transformation rules for ScalarOps
 821     /// </summary>
 822     internal static class ScalarOpRules
 823     {
 824         #region CaseOp Rules
 825         internal static readonly SimpleRule Rule_SimplifyCase = new SimpleRule(OpType.Case, ProcessSimplifyCase);
 826         internal static readonly SimpleRule Rule_FlattenCase = new SimpleRule(OpType.Case, ProcessFlattenCase);
 827         /// <summary>
 828         /// We perform the following simple transformation for CaseOps. If every single
 829         /// then/else expression in the CaseOp is equivalent, then we can simply replace
 830         /// the Op with the first then/expression. Specifically,
 831         /// case when w1 then t1 when w2 then t2 ... when wn then tn else e end
 832         ///   => t1
 833         /// assuming that t1 is equivalent to t2 is equivalent to ... to e
 834         /// </summary>
 835         /// <param name="context">Rule Processing context</param>
 836         /// <param name="caseOpNode">The current subtree for the CaseOp</param>
 837         /// <param name="newNode">the (possibly) modified subtree</param>
 838         /// <returns>true, if we performed any transformations</returns>
 839         static bool ProcessSimplifyCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
 840         {
 841             CaseOp caseOp = (CaseOp)caseOpNode.Op;
 842             newNode = caseOpNode;
 843
 844             //
 845             // Can I collapse the entire case-expression into a single expression - yes,
 846             // if all the then/else clauses are the same expression
 847             //
 848             if (ProcessSimplifyCase_Collapse(caseOp, caseOpNode, out newNode))
 849             {
 850                 return true;
 851             }
 852
 853             //
 854             // Can I remove any unnecessary when-then pairs ?
 855             //
 856             if (ProcessSimplifyCase_EliminateWhenClauses(context, caseOp, caseOpNode, out newNode))
 857             {
 858                 return true;
 859             }
 860
 861             // Nothing else I can think of
 862             return false;
 863         }
 864
 865         /// <summary>
 866         /// Try and collapse the case expression into a single expression.
 867         /// If every single then/else expression in the CaseOp is equivalent, then we can
 868         /// simply replace the CaseOp with the first then/expression. Specifically,
 869         /// case when w1 then t1 when w2 then t2 ... when wn then tn else e end
 870         ///   => t1
 871         ///  if t1 is equivalent to t2 is equivalent to ... to e
 872         /// </summary>
 873         /// <param name="caseOp">the current caseOp</param>
 874         /// <param name="caseOpNode">current subtree</param>
 875         /// <param name="newNode">new subtree</param>
 876         /// <returns>true, if we performed a transformation</returns>
 877         private static bool ProcessSimplifyCase_Collapse(CaseOp caseOp, Node caseOpNode, out Node newNode)
 878         {
 879             newNode = caseOpNode;
 880             Node firstThenNode = caseOpNode.Child1;
 881             Node elseNode = caseOpNode.Children[caseOpNode.Children.Count - 1];
 882             if (!firstThenNode.IsEquivalent(elseNode))
 883             {
 884                 return false;
 885             }
 886             for (int i = 3; i < caseOpNode.Children.Count - 1; i += 2)
 887             {
 888                 if (!caseOpNode.Children[i].IsEquivalent(firstThenNode))
 889                 {
 890                     return false;
 891                 }
 892             }
 893
 894             // All nodes are equivalent - simply return the first then node
 895             newNode = firstThenNode;
 896             return true;
 897         }
 898
 899         /// <summary>
 900         /// Try and remove spurious branches from the case expression.
 901         /// If any of the WHEN clauses is the 'FALSE' expression, simply remove that
 902         /// branch (when-then pair) from the case expression.
 903         /// If any of the WHEN clauses is the 'TRUE' expression, then all branches to the
 904         /// right of it are irrelevant - eliminate them. Eliminate this branch as well,
 905         /// and make the THEN expression of this branch the ELSE expression for the entire
 906         /// Case expression. If the WHEN expression represents the first branch, then
 907         /// replace the entire case expression by the corresponding THEN expression
 908         /// </summary>
 909         /// <param name="context">rule processing context</param>
 910         /// <param name="caseOp">current caseOp</param>
 911         /// <param name="caseOpNode">Current subtree</param>
 912         /// <param name="newNode">the new subtree</param>
 913         /// <returns>true, if there was a transformation</returns>
 914         private static bool ProcessSimplifyCase_EliminateWhenClauses(RuleProcessingContext context, CaseOp caseOp, Node caseOpNode, out Node newNode)
 915         {
 916             List<Node> newNodeArgs = null;
 917             newNode = caseOpNode;
 918
 919             for (int i = 0; i < caseOpNode.Children.Count; )
 920             {
 921                 // Special handling for the else clause
 922                 if (i == caseOpNode.Children.Count - 1)
 923                 {
 924                     // If the else clause is a SoftCast then we do not attempt to simplify
 925                     // the case operation, since this may change the result type.
 926                     // This really belongs in more general SoftCastOp logic in the CTreeGenerator
 927                     // that converts SoftCasts that could affect the result type of the query into
 928                     // a real cast or a trivial case statement, to preserve the result type.
 929                     // This is tracked by SQL PT Work Item #300003327.
 930                     if (OpType.SoftCast == caseOpNode.Children[i].Op.OpType)
 931                     {
 932                         return false;
 933                     }
 934
 935                     if (newNodeArgs != null)
 936                     {
 937                         newNodeArgs.Add(caseOpNode.Children[i]);
 938                     }
 939                     break;
 940                 }
 941
 942                 // If the current then clause is a SoftCast then we do not attempt to simplify
 943                 // the case operation, since this may change the result type.
 944                 // Again, this really belongs in the CTreeGenerator as per SQL PT Work Item #300003327.
 945                 if (OpType.SoftCast == caseOpNode.Children[i + 1].Op.OpType)
 946                 {
 947                     return false;
 948                 }
 949
 950                 // Check to see if the when clause is a ConstantPredicate
 951                 if (caseOpNode.Children[i].Op.OpType != OpType.ConstantPredicate)
 952                 {
 953                     if (newNodeArgs != null)
 954                     {
 955                         newNodeArgs.Add(caseOpNode.Children[i]);
 956                         newNodeArgs.Add(caseOpNode.Children[i + 1]);
 957                     }
 958                     i += 2;
 959                     continue;
 960                 }
 961
 962                 // Found a when-clause which is a constant predicate
 963                 ConstantPredicateOp constPred = (ConstantPredicateOp)caseOpNode.Children[i].Op;
 964                 // Create the newArgs list, if we haven't done so already
 965                 if (newNodeArgs == null)
 966                 {
 967                     newNodeArgs = new List<Node>();
 968                     for (int j = 0; j < i; j++)
 969                     {
 970                         newNodeArgs.Add(caseOpNode.Children[j]);
 971                     }
 972                 }
 973
 974                 // If the when-clause is the "true" predicate, then we simply ignore all
 975                 // the succeeding arguments. We make the "then" clause of this when-clause
 976                 // as the "else-clause" of the resulting caseOp
 977                 if (constPred.IsTrue)
 978                 {
 979                     newNodeArgs.Add(caseOpNode.Children[i + 1]);
 980                     break;
 981                 }
 982                 else
 983                 {
 984                     // Otherwise, we simply skip the when-then pair
 985                     PlanCompiler.Assert(constPred.IsFalse, "constant predicate must be either true or false");
 986                     i += 2;
 987                     continue;
 988                 }
 989             }
 990
 991             // Did we see any changes? Simply return
 992             if (newNodeArgs == null)
 993             {
 994                 return false;
 995             }
 996
 997             // Otherwise, we did do some processing
 998             PlanCompiler.Assert(newNodeArgs.Count > 0, "new args list must not be empty");
 999             // Is there only one expression in the args list - simply return that expression
1000             if (newNodeArgs.Count == 1)
1001             {
1002                 newNode = newNodeArgs[0];
1003             }
1004             else
1005             {
1006                 newNode = context.Command.CreateNode(caseOp, newNodeArgs);
1007             }
1008
1009             return true;
1010         }
1011
1012         /// <summary>
1013         /// If the else clause of the CaseOp is another CaseOp, when two can be collapsed into one.
1014         /// In particular,
1015         ///
1016         /// CASE
1017         ///     WHEN W1 THEN T1
1018         ///     WHEN W2 THEN T2 ...
1019         ///     ELSE (CASE
1020         ///             WHEN WN1 THEN TN1, \85
1021         ///             ELSE E)
1022         ///
1023         /// Is transformed into
1024         ///
1025         /// CASE
1026         ///     WHEN W1 THEN T1
1027         ///     WHEN W2 THEN T2 ...
1028         ///     WHEN WN1  THEN TN1 ...
1029         ///     ELSE E
1030         /// </summary>
1031         /// <param name="caseOp">the current caseOp</param>
1032         /// <param name="caseOpNode">current subtree</param>
1033         /// <param name="newNode">new subtree</param>
1034         /// <returns>true, if we performed a transformation</returns>
1035         static bool ProcessFlattenCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
1036         {
1037             newNode = caseOpNode;
1038             Node elseChild = caseOpNode.Children[caseOpNode.Children.Count - 1];
1039             if (elseChild.Op.OpType != OpType.Case)
1040             {
1041                 return false;
1042             }
1043
1044             //
1045             // Flatten the case statements.
1046             // The else child is removed from the outer CaseOp op
1047             // and the else child's children are reparented to the outer CaseOp
1048             // Node info recomputation does not need to happen, the outer CaseOp
1049             // node still has the same descendants.
1050             //
1051             caseOpNode.Children.RemoveAt(caseOpNode.Children.Count - 1);
1052             caseOpNode.Children.AddRange(elseChild.Children);
1053
1054             return true;
1055         }
1056
1057         #endregion
1058
1059         #region EqualsOverConstant Rules
1060         internal static readonly PatternMatchRule Rule_EqualsOverConstant =
1061             new PatternMatchRule(new Node(ComparisonOp.PatternEq,
1062                                           new Node(InternalConstantOp.Pattern),
1063                                           new Node(InternalConstantOp.Pattern)),
1064                                  ProcessComparisonsOverConstant);
1065         /// <summary>
1066         /// Convert an Equals(X, Y) to a "true" predicate if X=Y, or a "false" predicate if X!=Y
1067         /// Convert a NotEquals(X,Y) in the reverse fashion
1068         /// </summary>
1069         /// <param name="context">Rule processing context</param>
1070         /// <param name="node">current node</param>
1071         /// <param name="newNode">possibly modified subtree</param>
1072         /// <returns>true, if transformation was successful</returns>
1073         static bool ProcessComparisonsOverConstant(RuleProcessingContext context, Node node, out Node newNode)
1074         {
1075             newNode = node;
1076             PlanCompiler.Assert(node.Op.OpType == OpType.EQ || node.Op.OpType == OpType.NE, "unexpected comparison op type?");
1077
1078             bool? comparisonStatus = node.Child0.Op.IsEquivalent(node.Child1.Op);
1079             // Don't mess with nulls or with non-internal constants
1080             if (comparisonStatus == null)
1081             {
1082                 return false;
1083             }
1084             bool result = (node.Op.OpType == OpType.EQ) ? (bool)comparisonStatus : !((bool)comparisonStatus);
1085             ConstantPredicateOp newOp = context.Command.CreateConstantPredicateOp(result);
1086             newNode = context.Command.CreateNode(newOp);
1087             return true;
1088         }
1089         #endregion
1090
1091         #region LikeOp Rules
1092         private static bool? MatchesPattern(string str, string pattern)
1093         {
1094             // What we're trying to see is if the pattern is something that ends with a '%'
1095             // And if the "str" is something that matches everything before that
1096
1097             // Make sure that the terminal character of the pattern is a '%' character. Also
1098             // ensure that this character does not occur anywhere else. And finally, ensure
1099             // that the pattern is atmost one character longer than the string itself
1100             int wildCardIndex = pattern.IndexOf('%');
1101             if ((wildCardIndex == -1) ||
1102                 (wildCardIndex != pattern.Length - 1) ||
1103                 (pattern.Length > str.Length + 1))
1104             {
1105                 return null;
1106             }
1107
1108             bool match = true;
1109
1110             int i = 0;
1111             for (i = 0; i < str.Length && i < pattern.Length - 1; i++)
1112             {
1113                 if (pattern[i] != str[i])
1114                 {
1115                     match = false;
1116                     break;
1117                 }
1118             }
1119
1120             return match;
1121         }
1122
1123         internal static readonly PatternMatchRule Rule_LikeOverConstants =
1124             new PatternMatchRule(new Node(LikeOp.Pattern,
1125                                           new Node(InternalConstantOp.Pattern),
1126                                           new Node(InternalConstantOp.Pattern),
1127                                           new Node(NullOp.Pattern)),
1128                                  ProcessLikeOverConstant);
1129         static bool ProcessLikeOverConstant(RuleProcessingContext context, Node n, out Node newNode)
1130         {
1131             newNode = n;
1132             InternalConstantOp patternOp = (InternalConstantOp)n.Child1.Op;
1133             InternalConstantOp strOp = (InternalConstantOp)n.Child0.Op;
1134
1135             string str = (string)strOp.Value;
1136             string pattern = (string)patternOp.Value;
1137
1138             bool? match = MatchesPattern((string)strOp.Value, (string)patternOp.Value);
1139             if (match == null)
1140             {
1141                 return false;
1142             }
1143
1144             ConstantPredicateOp constOp = context.Command.CreateConstantPredicateOp((bool)match);
1145             newNode = context.Command.CreateNode(constOp);
1146             return true;
1147         }
1148
1149         #endregion
1150
1151         #region LogicalOp (and,or,not) Rules
1152         internal static readonly PatternMatchRule Rule_AndOverConstantPred1 =
1153             new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
1154                                           new Node(LeafOp.Pattern),
1155                                           new Node(ConstantPredicateOp.Pattern)),
1156                                  ProcessAndOverConstantPredicate1);
1157         internal static readonly PatternMatchRule Rule_AndOverConstantPred2 =
1158             new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
1159                                           new Node(ConstantPredicateOp.Pattern),
1160                                           new Node(LeafOp.Pattern)),
1161                                  ProcessAndOverConstantPredicate2);
1162         internal static readonly PatternMatchRule Rule_OrOverConstantPred1 =
1163             new PatternMatchRule(new Node(ConditionalOp.PatternOr,
1164                                           new Node(LeafOp.Pattern),
1165                                           new Node(ConstantPredicateOp.Pattern)),
1166                                  ProcessOrOverConstantPredicate1);
1167         internal static readonly PatternMatchRule Rule_OrOverConstantPred2 =
1168             new PatternMatchRule(new Node(ConditionalOp.PatternOr,
1169                                           new Node(ConstantPredicateOp.Pattern),
1170                                           new Node(LeafOp.Pattern)),
1171                                  ProcessOrOverConstantPredicate2);
1172         internal static readonly PatternMatchRule Rule_NotOverConstantPred =
1173             new PatternMatchRule(new Node(ConditionalOp.PatternNot,
1174                                           new Node(ConstantPredicateOp.Pattern)),
1175                                  ProcessNotOverConstantPredicate);
1176         /// <summary>
1177         /// Transform
1178         ///   AND(x, true) => x;
1179         ///   AND(true, x) => x
1180         ///   AND(x, false) => false
1181         ///   AND(false, x) => false
1182         ///
1183         /// </summary>
1184         /// <param name="context">Rule Processing context</param>
1185         /// <param name="node">Current LogOp (And, Or, Not) node</param>
1186         /// <param name="constantPredicateNode">constant predicate node</param>
1187         /// <param name="otherNode">The other child of the LogOp (possibly null)</param>
1188         /// <param name="newNode">new subtree</param>
1189         /// <returns>transformation status</returns>
1190         static bool ProcessLogOpOverConstant(RuleProcessingContext context, Node node,
1191             Node constantPredicateNode, Node otherNode,
1192             out Node newNode)
1193         {
1194             PlanCompiler.Assert(constantPredicateNode != null, "null constantPredicateOp?");
1195             ConstantPredicateOp pred = (ConstantPredicateOp)constantPredicateNode.Op;
1196
1197             switch (node.Op.OpType)
1198             {
1199                 case OpType.And:
1200                     newNode = pred.IsTrue ? otherNode : constantPredicateNode;
1201                     break;
1202                 case OpType.Or:
1203                     newNode = pred.IsTrue ? constantPredicateNode : otherNode;
1204                     break;
1205                 case OpType.Not:
1206                     PlanCompiler.Assert(otherNode == null, "Not Op with more than 1 child. Gasp!");
1207                     newNode = context.Command.CreateNode(context.Command.CreateConstantPredicateOp(!pred.Value));
1208                     break;
1209                 default:
1210                     PlanCompiler.Assert(false, "Unexpected OpType - " + node.Op.OpType);
1211                     newNode = null;
1212                     break;
1213             }
1214             return true;
1215         }
1216
1217         static bool ProcessAndOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
1218         {
1219             return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
1220         }
1221         static bool ProcessAndOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
1222         {
1223             return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
1224         }
1225         static bool ProcessOrOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
1226         {
1227             return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
1228         }
1229         static bool ProcessOrOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
1230         {
1231             return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
1232         }
1233         static bool ProcessNotOverConstantPredicate(RuleProcessingContext context, Node node, out Node newNode)
1234         {
1235             return ProcessLogOpOverConstant(context, node, node.Child0, null, out newNode);
1236         }
1237         #endregion
1238
1239         #region IsNull Rules
1240         internal static readonly PatternMatchRule Rule_IsNullOverConstant =
1241             new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
1242                                           new Node(InternalConstantOp.Pattern)),
1243                                  ProcessIsNullOverConstant);
1244         internal static readonly PatternMatchRule Rule_IsNullOverNullSentinel =
1245             new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
1246                                           new Node(NullSentinelOp.Pattern)),
1247                                  ProcessIsNullOverConstant);
1248         /// <summary>
1249         /// Convert a
1250         ///    IsNull(constant)
1251         /// to just the
1252         ///    False predicate
1253         /// </summary>
1254         /// <param name="context"></param>
1255         /// <param name="isNullNode"></param>
1256         /// <param name="newNode">new subtree</param>
1257         /// <returns></returns>
1258         static bool ProcessIsNullOverConstant(RuleProcessingContext context, Node isNullNode, out Node newNode)
1259         {
1260             newNode = context.Command.CreateNode(context.Command.CreateFalseOp());
1261             return true;
1262         }
1263
1264         internal static readonly PatternMatchRule Rule_IsNullOverNull =
1265             new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
1266                                           new Node(NullOp.Pattern)),
1267                          ProcessIsNullOverNull);
1268         /// <summary>
1269         /// Convert an IsNull(null) to just the 'true' predicate
1270         /// </summary>
1271         /// <param name="context"></param>
1272         /// <param name="isNullNode"></param>
1273         /// <param name="newNode">new subtree</param>
1274         /// <returns></returns>
1275         static bool ProcessIsNullOverNull(RuleProcessingContext context, Node isNullNode, out Node newNode)
1276         {
1277             newNode = context.Command.CreateNode(context.Command.CreateTrueOp());
1278             return true;
1279         }
1280         #endregion
1281
1282         #region CastOp(NullOp) Rule
1283         internal static readonly PatternMatchRule Rule_NullCast = new PatternMatchRule(
1284                                                             new Node(CastOp.Pattern,
1285                                                                     new Node(NullOp.Pattern)),
1286                                                             ProcessNullCast);
1287
1288         /// <summary>
1289         /// eliminates nested null casts into a single cast of the outermost cast type.
1290         /// basically the transformation applied is: cast(null[x] as T) => null[t]
1291         /// </summary>
1292         /// <param name="context"></param>
1293         /// <param name="castNullOp"></param>
1294         /// <param name="newNode">modified subtree</param>
1295         /// <returns></returns>
1296         static bool ProcessNullCast(RuleProcessingContext context, Node castNullOp, out Node newNode)
1297         {
1298             newNode = context.Command.CreateNode(context.Command.CreateNullOp(castNullOp.Op.Type));
1299             return true;
1300         }
1301         #endregion
1302
1303         #region IsNull over VarRef
1304         internal static readonly PatternMatchRule Rule_IsNullOverVarRef =
1305             new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
1306                                           new Node(VarRefOp.Pattern)),
1307                                  ProcessIsNullOverVarRef);
1308         /// <summary>
1309         /// Convert a
1310         ///    IsNull(VarRef(v))
1311         /// to just the
1312         ///    False predicate
1313         ///
1314         /// if v is guaranteed to be non nullable.
1315         /// </summary>
1316         /// <param name="context"></param>
1317         /// <param name="isNullNode"></param>
1318         /// <param name="newNode">new subtree</param>
1319         /// <returns></returns>
1320         static bool ProcessIsNullOverVarRef(RuleProcessingContext context, Node isNullNode, out Node newNode)
1321         {
1322             Command command = context.Command;
1323             TransformationRulesContext trc = (TransformationRulesContext)context;
1324
1325             Var v = ((VarRefOp)isNullNode.Child0.Op).Var;
1326
1327             if (trc.IsNonNullable(v))
1328             {
1329
1330                 newNode = command.CreateNode(context.Command.CreateFalseOp());
1331                 return true;
1332             }
1333             else
1334             {
1335                 newNode = isNullNode;
1336                 return false;
1337             }
1338         }
1339         #endregion
1340
1341         #region All ScalarOp Rules
1342         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
1343             Rule_SimplifyCase,
1344             Rule_FlattenCase,
1345             Rule_LikeOverConstants,
1346             Rule_EqualsOverConstant,
1347             Rule_AndOverConstantPred1,
1348             Rule_AndOverConstantPred2,
1349             Rule_OrOverConstantPred1,
1350             Rule_OrOverConstantPred2,
1351             Rule_NotOverConstantPred,
1352             Rule_IsNullOverConstant,
1353             Rule_IsNullOverNullSentinel,
1354             Rule_IsNullOverNull,
1355             Rule_NullCast,
1356             Rule_IsNullOverVarRef,
1357         };
1358         #endregion
1359     }
1360     #endregion
1361
1362     #region Filter Rules
1363     /// <summary>
1364     /// Transformation rules for FilterOps
1365     /// </summary>
1366     internal static class FilterOpRules
1367     {
1368         #region Helpers
1369         /// <summary>
1370         /// Split up a predicate into 2 parts - the pushdown and the non-pushdown predicate.
1371         ///
1372         /// If the filter node has no external references *and* the "columns" parameter is null,
1373         /// then the entire predicate can be pushed down
1374         ///
1375         /// We then compute the set of valid column references - if the "columns" parameter
1376         /// is non-null, this set is used. Otherwise, we get the definitions of the
1377         /// input relop node of the filterOp, and use that.
1378         ///
1379         /// We use this list of valid column references to identify which parts of the filter
1380         /// predicate can be pushed down - only those parts of the predicate that do not
1381         /// reference anything beyond these columns are considered for pushdown. The rest are
1382         /// stuffed into the nonPushdownPredicate output parameter
1383         ///
1384         /// </summary>
1385         /// <param name="command">Command object</param>
1386         /// <param name="filterNode">the FilterOp subtree</param>
1387         /// <param name="columns">(Optional) List of columns to consider for "pushdown"</param>
1388         /// <param name="nonPushdownPredicateNode">(output) Part of the predicate that cannot be pushed down</param>
1389         /// <returns>part of the predicate that can be pushed down</returns>
1390         private static Node GetPushdownPredicate(Command command, Node filterNode, VarVec columns, out Node nonPushdownPredicateNode)
1391         {
1392             Node pushdownPredicateNode = filterNode.Child1;
1393             nonPushdownPredicateNode = null;
1394             ExtendedNodeInfo filterNodeInfo = command.GetExtendedNodeInfo(filterNode);
1395             if (columns == null && filterNodeInfo.ExternalReferences.IsEmpty)
1396             {
1397                 return pushdownPredicateNode;
1398             }
1399
1400             if (columns == null)
1401             {
1402                 ExtendedNodeInfo inputNodeInfo = command.GetExtendedNodeInfo(filterNode.Child0);
1403                 columns = inputNodeInfo.Definitions;
1404             }
1405
1406             Predicate predicate = new Predicate(command, pushdownPredicateNode);
1407             Predicate nonPushdownPredicate;
1408             predicate = predicate.GetSingleTablePredicates(columns, out nonPushdownPredicate);
1409             pushdownPredicateNode = predicate.BuildAndTree();
1410             nonPushdownPredicateNode = nonPushdownPredicate.BuildAndTree();
1411             return pushdownPredicateNode;
1412         }
1413
1414         #endregion
1415
1416         #region FilterOverFilter
1417         internal static readonly PatternMatchRule Rule_FilterOverFilter =
1418             new PatternMatchRule(new Node(FilterOp.Pattern,
1419                                           new Node(FilterOp.Pattern,
1420                                                    new Node(LeafOp.Pattern),
1421                                                    new Node(LeafOp.Pattern)),
1422                                           new Node(LeafOp.Pattern)),
1423                                  ProcessFilterOverFilter);
1424         /// <summary>
1425         /// Convert Filter(Filter(X, p1), p2) => Filter(X, (p1 and p2))
1426         /// </summary>
1427         /// <param name="context">rule processing context</param>
1428         /// <param name="filterNode">FilterOp node</param>
1429         /// <param name="newNode">modified subtree</param>
1430         /// <returns>transformed subtree</returns>
1431         static bool ProcessFilterOverFilter(RuleProcessingContext context, Node filterNode, out Node newNode)
1432         {
1433             Node newAndNode = context.Command.CreateNode(
1434                 context.Command.CreateConditionalOp(OpType.And),
1435                 filterNode.Child0.Child1, filterNode.Child1);
1436
1437             newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), filterNode.Child0.Child0, newAndNode);
1438             return true;
1439         }
1440         #endregion
1441
1442         #region FilterOverProject
1443         internal static readonly PatternMatchRule Rule_FilterOverProject =
1444             new PatternMatchRule(new Node(FilterOp.Pattern,
1445                                           new Node(ProjectOp.Pattern,
1446                                                    new Node(LeafOp.Pattern),
1447                                                    new Node(LeafOp.Pattern)),
1448                                           new Node(LeafOp.Pattern)),
1449                                  ProcessFilterOverProject);
1450         /// <summary>
1451         /// Convert Filter(Project(X, ...), p) => Project(Filter(X, p'), ...)
1452         /// </summary>
1453         /// <param name="context">Rule processing context</param>
1454         /// <param name="filterNode">FilterOp subtree</param>
1455         /// <param name="newNode">modified subtree</param>
1456         /// <returns>transformed subtree</returns>
1457         static bool ProcessFilterOverProject(RuleProcessingContext context, Node filterNode, out Node newNode)
1458         {
1459             newNode = filterNode;
1460             Node predicateNode = filterNode.Child1;
1461
1462             //
1463             // If the filter is a constant predicate, then don't push the filter below the
1464             // project
1465             //
1466             if (predicateNode.Op.OpType == OpType.ConstantPredicate)
1467             {
1468                 // There's a different rule to process this case. Simply return
1469                 return false;
1470             }
1471
1472             TransformationRulesContext trc = (TransformationRulesContext)context;
1473             //
1474             // check to see that this is a simple predicate
1475             //
1476             Dictionary<Var, int> varRefMap = new Dictionary<Var, int>();
1477             if (!trc.IsScalarOpTree(predicateNode, varRefMap))
1478             {
1479                 return false;
1480             }
1481             //
1482             // check to see if all expressions in the project can be inlined
1483             //
1484             Node projectNode = filterNode.Child0;
1485             Dictionary<Var, Node> varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
1486             if (varMap == null)
1487             {
1488                 return false;
1489             }
1490
1491             //
1492             // Try to remap the predicate in terms of the definitions of the Vars
1493             //
1494             Node remappedPredicateNode = trc.ReMap(predicateNode, varMap);
1495
1496             //
1497             // Now push the filter below the project
1498             //
1499             Node newFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), projectNode.Child0, remappedPredicateNode);
1500             Node newProjectNode = trc.Command.CreateNode(projectNode.Op, newFilterNode, projectNode.Child1);
1501
1502             newNode = newProjectNode;
1503             return true;
1504         }
1505         #endregion
1506
1507         #region FilterOverSetOp
1508         internal static readonly PatternMatchRule Rule_FilterOverUnionAll =
1509             new PatternMatchRule(new Node(FilterOp.Pattern,
1510                                           new Node(UnionAllOp.Pattern,
1511                                                    new Node(LeafOp.Pattern),
1512                                                    new Node(LeafOp.Pattern)),
1513                                           new Node(LeafOp.Pattern)),
1514                                  ProcessFilterOverSetOp);
1515         internal static readonly PatternMatchRule Rule_FilterOverIntersect =
1516             new PatternMatchRule(new Node(FilterOp.Pattern,
1517                                           new Node(IntersectOp.Pattern,
1518                                                    new Node(LeafOp.Pattern),
1519                                                    new Node(LeafOp.Pattern)),
1520                                           new Node(LeafOp.Pattern)),
1521                                  ProcessFilterOverSetOp);
1522         internal static readonly PatternMatchRule Rule_FilterOverExcept =
1523             new PatternMatchRule(new Node(FilterOp.Pattern,
1524                                           new Node(ExceptOp.Pattern,
1525                                                    new Node(LeafOp.Pattern),
1526                                                    new Node(LeafOp.Pattern)),
1527                                           new Node(LeafOp.Pattern)),
1528                                  ProcessFilterOverSetOp);
1529         /// <summary>
1530         /// Transform Filter(UnionAll(X1, X2), p) => UnionAll(Filter(X1, p1), Filter(X, p2))
1531         ///           Filter(Intersect(X1, X2), p) => Intersect(Filter(X1, p1), Filter(X2, p2))
1532         ///           Filter(Except(X1, X2), p) => Except(Filter(X1, p1), X2)
1533         /// where p1 and p2 are the "mapped" versions of the predicate "p" for each branch
1534         /// </summary>
1535         /// <param name="context">Rule processing context</param>
1536         /// <param name="filterNode">FilterOp subtree</param>
1537         /// <param name="newNode">modified subtree</param>
1538         /// <returns>true, if successful transformation</returns>
1539         static bool ProcessFilterOverSetOp(RuleProcessingContext context, Node filterNode, out Node newNode)
1540         {
1541             newNode = filterNode;
1542             TransformationRulesContext trc = (TransformationRulesContext)context;
1543
1544             //
1545             // Identify parts of the filter predicate that can be pushed down, and parts that
1546             // cannot be. If nothing can be pushed down, then return
1547             //
1548             Node nonPushdownPredicate;
1549             Node pushdownPredicate = GetPushdownPredicate(trc.Command, filterNode, null, out nonPushdownPredicate);
1550             if (pushdownPredicate == null)
1551             {
1552                 return false;
1553             }
1554             // Handle only simple predicates
1555             if (!trc.IsScalarOpTree(pushdownPredicate))
1556             {
1557                 return false;
1558             }
1559
1560             //
1561             // Now push the predicate (the part that can be pushed down) into each of the
1562             // branches (as appropriate)
1563             //
1564             Node setOpNode = filterNode.Child0;
1565             SetOp setOp = (SetOp)setOpNode.Op;
1566             List<Node> newSetOpChildren = new List<Node>();
1567             int branchId = 0;
1568             foreach (VarMap varMap in setOp.VarMap)
1569             {
1570                 // For exceptOp, the filter should only be pushed below the zeroth child
1571                 if (setOp.OpType == OpType.Except && branchId == 1)
1572                 {
1573                     newSetOpChildren.Add(setOpNode.Child1);
1574                     break;
1575                 }
1576
1577                 Dictionary<Var, Node> remapMap = new Dictionary<Var, Node>();
1578                 foreach (KeyValuePair<Var, Var> kv in varMap)
1579                 {
1580                     Node varRefNode = trc.Command.CreateNode(trc.Command.CreateVarRefOp(kv.Value));
1581                     remapMap.Add(kv.Key, varRefNode);
1582                 }
1583
1584                 //
1585                 // Now fix up the predicate.
1586                 // Make a copy of the predicate first - except if we're dealing with the last
1587                 // branch, in which case, we can simply reuse the predicate
1588                 //
1589                 Node predicateNode = pushdownPredicate;
1590                 if (branchId == 0 && filterNode.Op.OpType != OpType.Except)
1591                 {
1592                     predicateNode = trc.Copy(predicateNode);
1593                 }
1594                 Node newPredicateNode = trc.ReMap(predicateNode, remapMap);
1595                 trc.Command.RecomputeNodeInfo(newPredicateNode);
1596
1597                 // create a new filter node below the setOp child
1598                 Node newFilterNode = trc.Command.CreateNode(
1599                     trc.Command.CreateFilterOp(),
1600                     setOpNode.Children[branchId],
1601                     newPredicateNode);
1602                 newSetOpChildren.Add(newFilterNode);
1603
1604                 branchId++;
1605             }
1606             Node newSetOpNode = trc.Command.CreateNode(setOpNode.Op, newSetOpChildren);
1607
1608             //
1609             // We've now pushed down the relevant parts of the filter below the SetOps
1610             // We may still however some predicates left over - create a new filter node
1611             // to account for that
1612             //
1613             if (nonPushdownPredicate != null)
1614             {
1615                 newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newSetOpNode, nonPushdownPredicate);
1616             }
1617             else
1618             {
1619                 newNode = newSetOpNode;
1620             }
1621             return true;
1622         }
1623         #endregion
1624
1625         #region FilterOverDistinct
1626         internal static readonly PatternMatchRule Rule_FilterOverDistinct =
1627             new PatternMatchRule(new Node(FilterOp.Pattern,
1628                                   new Node(DistinctOp.Pattern,
1629                                            new Node(LeafOp.Pattern)),
1630                                   new Node(LeafOp.Pattern)),
1631                          ProcessFilterOverDistinct);
1632         /// <summary>
1633         /// Transforms Filter(Distinct(x), p) => Filter(Distinct(Filter(X, p1), p2)
1634         ///    where p2 is the part of the filter that can be pushed down, while p1 represents
1635         ///    any external references
1636         /// </summary>
1637         /// <param name="context">Rule processing context</param>
1638         /// <param name="filterNode">FilterOp subtree</param>
1639         /// <param name="newNode">modified subtree</param>
1640         /// <returns>Transformation status</returns>
1641         static bool ProcessFilterOverDistinct(RuleProcessingContext context, Node filterNode, out Node newNode)
1642         {
1643             newNode = filterNode;
1644             //
1645             // Split up the filter predicate into two parts - the part that can be pushed down
1646             // and the part that can't. If there is no part that can be pushed down, simply return
1647             //
1648             Node nonPushdownPredicate;
1649             Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, null, out nonPushdownPredicate);
1650             if (pushdownPredicate == null)
1651             {
1652                 return false;
1653             }
1654
1655             //
1656             // Create a new filter node below the current distinct node for the predicate
1657             // that can be pushed down - create a new distinct node as well
1658             //
1659             Node distinctNode = filterNode.Child0;
1660             Node pushdownFilterNode = context.Command.CreateNode(context.Command.CreateFilterOp(), distinctNode.Child0, pushdownPredicate);
1661             Node newDistinctNode = context.Command.CreateNode(distinctNode.Op, pushdownFilterNode);
1662
1663             //
1664             // If we have a predicate part that cannot be pushed down, build up a new
1665             // filter node above the new Distinct op that we just created
1666             //
1667             if (nonPushdownPredicate != null)
1668             {
1669                 newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), newDistinctNode, nonPushdownPredicate);
1670             }
1671             else
1672             {
1673                 newNode = newDistinctNode;
1674             }
1675             return true;
1676         }
1677         #endregion
1678
1679         #region FilterOverGroupBy
1680         internal static readonly PatternMatchRule Rule_FilterOverGroupBy =
1681             new PatternMatchRule(new Node(FilterOp.Pattern,
1682                                   new Node(GroupByOp.Pattern,
1683                                            new Node(LeafOp.Pattern),
1684                                            new Node(LeafOp.Pattern),
1685                                            new Node(LeafOp.Pattern)),
1686                                   new Node(LeafOp.Pattern)),
1687                          ProcessFilterOverGroupBy);
1688         /// <summary>
1689         /// Transforms Filter(GroupBy(X, k1.., a1...), p) =>
1690         ///            Filter(GroupBy(Filter(X, p1'), k1..., a1...), p2)
1691         ///   p1 and p2 represent the parts of p that can and cannot be pushed down
1692         ///    respectively - specifically, p1 must only reference the key columns from
1693         ///    the GroupByOp.
1694         ///   "p1'" is the mapped version of "p1",
1695         /// </summary>
1696         /// <param name="context">Rule processing context</param>
1697         /// <param name="filterNode">Current FilterOp subtree</param>
1698         /// <param name="newNode">modified subtree</param>
1699         /// <returns>Transformation status</returns>
1700         static bool ProcessFilterOverGroupBy(RuleProcessingContext context, Node filterNode, out Node newNode)
1701         {
1702             newNode = filterNode;
1703             Node groupByNode = filterNode.Child0;
1704             GroupByOp groupByOp = (GroupByOp)groupByNode.Op;
1705             TransformationRulesContext trc = (TransformationRulesContext)context;
1706
1707             // Check to see that we have a simple predicate
1708             Dictionary<Var, int> varRefMap = new Dictionary<Var, int>();
1709             if (!trc.IsScalarOpTree(filterNode.Child1, varRefMap))
1710             {
1711                 return false;
1712             }
1713
1714             //
1715             // Split up the predicate into two parts - the part that can be pushed down below
1716             // the groupByOp (specifically, the part that only refers to keys of the groupByOp),
1717             // and the part that cannot be pushed below
1718             // If nothing can be pushed below, quit now
1719             //
1720             Node nonPushdownPredicate;
1721             Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, groupByOp.Keys, out nonPushdownPredicate);
1722             if (pushdownPredicate == null)
1723             {
1724                 return false;
1725             }
1726
1727             //
1728             // We need to push the filter down; but we need to remap the predicate, so
1729             // that any references to variables defined locally by the groupBy are fixed up
1730             // Make sure that the predicate is not too complex to remap
1731             //
1732             Dictionary<Var, Node> varMap = trc.GetVarMap(groupByNode.Child1, varRefMap);
1733             if (varMap == null)
1734             {
1735                 return false; // complex expressions
1736             }
1737             Node remappedPushdownPredicate = trc.ReMap(pushdownPredicate, varMap);
1738
1739             //
1740             // Push the filter below the groupBy now
1741             //
1742             Node subFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), groupByNode.Child0, remappedPushdownPredicate);
1743             Node newGroupByNode = trc.Command.CreateNode(groupByNode.Op, subFilterNode, groupByNode.Child1, groupByNode.Child2);
1744
1745             //
1746             // If there was any part of the original predicate that could not be pushed down,
1747             // create a new filterOp node above the new groupBy node to represent that
1748             // predicate
1749             //
1750             if (nonPushdownPredicate == null)
1751             {
1752                 newNode = newGroupByNode;
1753             }
1754             else
1755             {
1756                 newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newGroupByNode, nonPushdownPredicate);
1757             }
1758             return true;
1759         }
1760         #endregion
1761
1762         #region FilterOverJoin
1763         internal static readonly PatternMatchRule Rule_FilterOverCrossJoin =
1764             new PatternMatchRule(new Node(FilterOp.Pattern,
1765                                   new Node(CrossJoinOp.Pattern,
1766                                            new Node(LeafOp.Pattern),
1767                                            new Node(LeafOp.Pattern)),
1768                                   new Node(LeafOp.Pattern)),
1769                          ProcessFilterOverJoin);
1770         internal static readonly PatternMatchRule Rule_FilterOverInnerJoin =
1771             new PatternMatchRule(new Node(FilterOp.Pattern,
1772                                   new Node(InnerJoinOp.Pattern,
1773                                            new Node(LeafOp.Pattern),
1774                                            new Node(LeafOp.Pattern),
1775                                            new Node(LeafOp.Pattern)),
1776                                   new Node(LeafOp.Pattern)),
1777                          ProcessFilterOverJoin);
1778         internal static readonly PatternMatchRule Rule_FilterOverLeftOuterJoin =
1779             new PatternMatchRule(new Node(FilterOp.Pattern,
1780                                   new Node(LeftOuterJoinOp.Pattern,
1781                                            new Node(LeafOp.Pattern),
1782                                            new Node(LeafOp.Pattern),
1783                                            new Node(LeafOp.Pattern)),
1784                                   new Node(LeafOp.Pattern)),
1785                          ProcessFilterOverJoin);
1786         /// <summary>
1787         /// Transform Filter()
1788         /// </summary>
1789         /// <param name="context">Rule Processing context</param>
1790         /// <param name="filterNode">Current FilterOp subtree</param>
1791         /// <param name="newNode">Modified subtree</param>
1792         /// <returns>Transformation status</returns>
1793         static bool ProcessFilterOverJoin(RuleProcessingContext context, Node filterNode, out Node newNode)
1794         {
1795             newNode = filterNode;
1796             TransformationRulesContext trc = (TransformationRulesContext)context;
1797
1798             //
1799             // Have we shut off filter pushdown for this node? Return
1800             //
1801             if (trc.IsFilterPushdownSuppressed(filterNode))
1802             {
1803                 return false;
1804             }
1805
1806             Node joinNode = filterNode.Child0;
1807             Op joinOp = joinNode.Op;
1808             Node leftInputNode = joinNode.Child0;
1809             Node rightInputNode = joinNode.Child1;
1810             Command command = trc.Command;
1811             bool needsTransformation = false;
1812
1813             //
1814             // If we're dealing with an outer-join, first check to see if the current
1815             // predicate preserves nulls for the right table.
1816             // If it doesn't then we can convert the outer join into an inner join,
1817             // and then continue with the rest of our processing here
1818             //
1819             ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(rightInputNode);
1820             Predicate predicate = new Predicate(command, filterNode.Child1);
1821             if (joinOp.OpType == OpType.LeftOuterJoin)
1822             {
1823                 if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
1824                 {
1825                     joinOp = command.CreateInnerJoinOp();
1826                     needsTransformation = true;
1827                 }
1828             }
1829             ExtendedNodeInfo leftTableInfo = command.GetExtendedNodeInfo(leftInputNode);
1830
1831             //
1832             // Check to see if the predicate contains any "single-table-filters". In those
1833             // cases, we could simply push that filter down to the child.
1834             // We can do this for inner joins and cross joins - for both inputs.
1835             // For left-outer joins, however, we can only do this for the left-side input
1836             // Further note that we only want to do the pushdown if it will help us - if
1837             // the join input is a ScanTable (or some other cases), then it doesn't help us.
1838             //
1839             Node leftSingleTablePredicateNode = null;
1840             if (leftInputNode.Op.OpType != OpType.ScanTable)
1841             {
1842                 Predicate leftSingleTablePredicates = predicate.GetSingleTablePredicates(leftTableInfo.Definitions, out predicate);
1843                 leftSingleTablePredicateNode = leftSingleTablePredicates.BuildAndTree();
1844             }
1845
1846             Node rightSingleTablePredicateNode = null;
1847             if ((rightInputNode.Op.OpType != OpType.ScanTable) &&
1848                 (joinOp.OpType != OpType.LeftOuterJoin))
1849             {
1850                 Predicate rightSingleTablePredicates = predicate.GetSingleTablePredicates(rightTableNodeInfo.Definitions, out predicate);
1851                 rightSingleTablePredicateNode = rightSingleTablePredicates.BuildAndTree();
1852             }
1853
1854             //
1855             // Now check to see if the predicate contains some "join predicates". We can
1856             // add these to the existing join predicate (if any).
1857             // We can only do this for inner joins and cross joins - not for LOJs
1858             //
1859             Node newJoinPredicateNode = null;
1860             if (joinOp.OpType == OpType.CrossJoin || joinOp.OpType == OpType.InnerJoin)
1861             {
1862                 Predicate joinPredicate = predicate.GetJoinPredicates(leftTableInfo.Definitions, rightTableNodeInfo.Definitions, out predicate);
1863                 newJoinPredicateNode = joinPredicate.BuildAndTree();
1864             }
1865
1866             //
1867             // Now for the dirty work. We've identified some predicates that could be pushed
1868             // into the left table, some predicates that could be pushed into the right table
1869             // and some that could become join predicates.
1870             //
1871             if (leftSingleTablePredicateNode != null)
1872             {
1873                 leftInputNode = command.CreateNode(command.CreateFilterOp(), leftInputNode, leftSingleTablePredicateNode);
1874                 needsTransformation = true;
1875             }
1876             if (rightSingleTablePredicateNode != null)
1877             {
1878                 rightInputNode = command.CreateNode(command.CreateFilterOp(), rightInputNode, rightSingleTablePredicateNode);
1879                 needsTransformation = true;
1880             }
1881
1882             // Identify the new join predicate
1883             if (newJoinPredicateNode != null)
1884             {
1885                 needsTransformation = true;
1886                 if (joinOp.OpType == OpType.CrossJoin)
1887                 {
1888                     joinOp = command.CreateInnerJoinOp();
1889                 }
1890                 else
1891                 {
1892                     PlanCompiler.Assert(joinOp.OpType == OpType.InnerJoin, "unexpected non-InnerJoin?");
1893                     newJoinPredicateNode = PlanCompilerUtil.CombinePredicates(joinNode.Child2, newJoinPredicateNode, command);
1894                 }
1895             }
1896             else
1897             {
1898                 newJoinPredicateNode = (joinOp.OpType == OpType.CrossJoin) ? null : joinNode.Child2;
1899             }
1900
1901             //
1902             // If nothing has changed, then just return the current node. Otherwise,
1903             // we will loop forever
1904             //
1905             if (!needsTransformation)
1906             {
1907                 return false;
1908             }
1909
1910             Node newJoinNode;
1911             //
1912             // Finally build up a new join node
1913             //
1914             if (joinOp.OpType == OpType.CrossJoin)
1915             {
1916                 newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode);
1917             }
1918             else
1919             {
1920                 newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode, newJoinPredicateNode);
1921             }
1922
1923             //
1924             // Build up a new filterNode above this join node. But only if we have a filter left
1925             //
1926             Node newFilterPredicateNode = predicate.BuildAndTree();
1927             if (newFilterPredicateNode == null)
1928             {
1929                 newNode = newJoinNode;
1930             }
1931             else
1932             {
1933                 newNode = command.CreateNode(command.CreateFilterOp(), newJoinNode, newFilterPredicateNode);
1934             }
1935             return true;
1936         }
1937         #endregion
1938
1939         #region Filter over OuterApply
1940         internal static readonly PatternMatchRule Rule_FilterOverOuterApply =
1941             new PatternMatchRule(new Node(FilterOp.Pattern,
1942                                   new Node(OuterApplyOp.Pattern,
1943                                            new Node(LeafOp.Pattern),
1944                                            new Node(LeafOp.Pattern)),
1945                                   new Node(LeafOp.Pattern)),
1946                          ProcessFilterOverOuterApply);
1947         /// <summary>
1948         /// Convert Filter(OuterApply(X,Y), p) into
1949         ///    Filter(CrossApply(X,Y), p)
1950         /// if "p" is not null-preserving for Y (ie) "p" does not preserve null values from Y
1951         /// </summary>
1952         /// <param name="context">Rule processing context</param>
1953         /// <param name="filterNode">Filter node</param>
1954         /// <param name="newNode">modified subtree</param>
1955         /// <returns>transformation status</returns>
1956         static bool ProcessFilterOverOuterApply(RuleProcessingContext context, Node filterNode, out Node newNode)
1957         {
1958             newNode = filterNode;
1959             Node applyNode = filterNode.Child0;
1960             Op applyOp = applyNode.Op;
1961             Node applyRightInputNode = applyNode.Child1;
1962             TransformationRulesContext trc = (TransformationRulesContext)context;
1963             Command command = trc.Command;
1964
1965             //
1966             // Check to see if the current predicate preserves nulls for the right table.
1967             // If it doesn't then we can convert the outer apply into a cross-apply,
1968             //
1969             ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(applyRightInputNode);
1970             Predicate predicate = new Predicate(command, filterNode.Child1);
1971             if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
1972             {
1973                 Node newApplyNode = command.CreateNode(command.CreateCrossApplyOp(), applyNode.Child0, applyRightInputNode);
1974                 Node newFilterNode = command.CreateNode(command.CreateFilterOp(), newApplyNode, filterNode.Child1);
1975                 newNode = newFilterNode;
1976                 return true;
1977             }
1978
1979             return false;
1980         }
1981
1982         #endregion
1983
1984         #region FilterWithConstantPredicate
1985         internal static readonly PatternMatchRule Rule_FilterWithConstantPredicate =
1986             new PatternMatchRule(new Node(FilterOp.Pattern,
1987                           new Node(LeafOp.Pattern),
1988                           new Node(ConstantPredicateOp.Pattern)),
1989                  ProcessFilterWithConstantPredicate);
1990         /// <summary>
1991         /// Convert
1992         ///    Filter(X, true)  => X
1993         ///    Filter(X, false) => Project(Filter(SingleRowTableOp, ...), false)
1994         /// where ... represent variables that are equivalent to the table columns
1995         /// </summary>
1996         /// <param name="context">Rule processing context</param>
1997         /// <param name="n">Current subtree</param>
1998         /// <param name="newNode">modified subtree</param>
1999         /// <returns>transformation status</returns>
2000         static bool ProcessFilterWithConstantPredicate(RuleProcessingContext context, Node n, out Node newNode)
2001         {
2002             newNode = n;
2003             ConstantPredicateOp predOp = (ConstantPredicateOp)n.Child1.Op;
2004
2005             // If we're dealing with a "true" predicate, then simply return the RelOp
2006             // input to the filter
2007             if (predOp.IsTrue)
2008             {
2009                 newNode = n.Child0;
2010                 return true;
2011             }
2012
2013             PlanCompiler.Assert(predOp.IsFalse, "unexpected non-false predicate?");
2014             // We're dealing with a "false" predicate, then we can get rid of the
2015             // input, and replace it with a dummy project
2016
2017             //
2018             // If the input is already a singlerowtableOp, then there's nothing
2019             // further to do
2020             //
2021             if (n.Child0.Op.OpType == OpType.SingleRowTable ||
2022                 (n.Child0.Op.OpType == OpType.Project &&
2023                  n.Child0.Child0.Op.OpType == OpType.SingleRowTable))
2024             {
2025                 return false;
2026             }
2027
2028             TransformationRulesContext trc = (TransformationRulesContext)context;
2029             ExtendedNodeInfo childNodeInfo = trc.Command.GetExtendedNodeInfo(n.Child0);
2030             List<Node> varDefNodeList = new List<Node>();
2031             VarVec newVars = trc.Command.CreateVarVec();
2032             foreach (Var v in childNodeInfo.Definitions)
2033             {
2034                 NullOp nullConst = trc.Command.CreateNullOp(v.Type);
2035                 Node constNode = trc.Command.CreateNode(nullConst);
2036                 Var computedVar;
2037                 Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
2038                 trc.AddVarMapping(v, computedVar);
2039                 newVars.Set(computedVar);
2040                 varDefNodeList.Add(varDefNode);
2041             }
2042             // If no vars have been selected out, add a dummy var
2043             if (newVars.IsEmpty)
2044             {
2045                 NullOp nullConst = trc.Command.CreateNullOp(trc.Command.BooleanType);
2046                 Node constNode = trc.Command.CreateNode(nullConst);
2047                 Var computedVar;
2048                 Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
2049                 newVars.Set(computedVar);
2050                 varDefNodeList.Add(varDefNode);
2051             }
2052
2053             Node singleRowTableNode = trc.Command.CreateNode(trc.Command.CreateSingleRowTableOp());
2054             n.Child0 = singleRowTableNode;
2055
2056             Node varDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp(), varDefNodeList);
2057             ProjectOp projectOp = trc.Command.CreateProjectOp(newVars);
2058             Node projectNode = trc.Command.CreateNode(projectOp, n, varDefListNode);
2059
2060             projectNode.Child0 = n;
2061             newNode = projectNode;
2062             return true;
2063         }
2064
2065         #endregion
2066
2067         #region All FilterOp Rules
2068         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
2069                  FilterOpRules.Rule_FilterWithConstantPredicate,
2070                  FilterOpRules.Rule_FilterOverCrossJoin,
2071                  FilterOpRules.Rule_FilterOverDistinct,
2072                  FilterOpRules.Rule_FilterOverExcept,
2073                  FilterOpRules.Rule_FilterOverFilter,
2074                  FilterOpRules.Rule_FilterOverGroupBy,
2075                  FilterOpRules.Rule_FilterOverInnerJoin,
2076                  FilterOpRules.Rule_FilterOverIntersect,
2077                  FilterOpRules.Rule_FilterOverLeftOuterJoin,
2078                  FilterOpRules.Rule_FilterOverProject,
2079                  FilterOpRules.Rule_FilterOverUnionAll,
2080                  FilterOpRules.Rule_FilterOverOuterApply,
2081         };
2082
2083         #endregion
2084     }
2085     #endregion
2086
2087     #region Project Rules
2088     /// <summary>
2089     /// Transformation rules for ProjectOp
2090     /// </summary>
2091     internal static class ProjectOpRules
2092     {
2093         #region ProjectOverProject
2094         internal static readonly PatternMatchRule Rule_ProjectOverProject =
2095             new PatternMatchRule(new Node(ProjectOp.Pattern,
2096                                           new Node(ProjectOp.Pattern,
2097                                                    new Node(LeafOp.Pattern),
2098                                                    new Node(LeafOp.Pattern)),
2099                                           new Node(LeafOp.Pattern)),
2100                                  ProcessProjectOverProject);
2101         /// <summary>
2102         /// Converts a Project(Project(X, c1,...), d1,...) =>
2103         ///            Project(X, d1', d2'...)
2104         /// where d1', d2' etc. are the "mapped" versions of d1, d2 etc.
2105         /// </summary>
2106         /// <param name="context">Rule processing context</param>
2107         /// <param name="projectNode">Current ProjectOp node</param>
2108         /// <param name="newNode">modified subtree</param>
2109         /// <returns>Transformation status</returns>
2110         static bool ProcessProjectOverProject(RuleProcessingContext context, Node projectNode, out Node newNode)
2111         {
2112             newNode = projectNode;
2113             ProjectOp projectOp = (ProjectOp)projectNode.Op;
2114             Node varDefListNode = projectNode.Child1;
2115             Node subProjectNode = projectNode.Child0;
2116             ProjectOp subProjectOp = (ProjectOp)subProjectNode.Op;
2117             TransformationRulesContext trc = (TransformationRulesContext)context;
2118
2119             // If any of the defining expressions is not a scalar op tree, then simply
2120             // quit
2121             Dictionary<Var, int> varRefMap = new Dictionary<Var, int>();
2122             foreach (Node varDefNode in varDefListNode.Children)
2123             {
2124                 if (!trc.IsScalarOpTree(varDefNode.Child0, varRefMap))
2125                 {
2126                     return false;
2127                 }
2128             }
2129
2130             Dictionary<Var, Node> varMap = trc.GetVarMap(subProjectNode.Child1, varRefMap);
2131             if (varMap == null)
2132             {
2133                 return false;
2134             }
2135
2136             // create a new varDefList node...
2137             Node newVarDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp());
2138
2139             // Remap any local definitions, I have
2140             foreach (Node varDefNode in varDefListNode.Children)
2141             {
2142                 // update the defining expression
2143                 varDefNode.Child0 = trc.ReMap(varDefNode.Child0, varMap);
2144                 trc.Command.RecomputeNodeInfo(varDefNode);
2145                 newVarDefListNode.Children.Add(varDefNode);
2146             }
2147
2148             // Now, pull up any definitions of the subProject that I publish myself
2149             ExtendedNodeInfo projectNodeInfo = trc.Command.GetExtendedNodeInfo(projectNode);
2150             foreach (Node chi in subProjectNode.Child1.Children)
2151             {
2152                 VarDefOp varDefOp = (VarDefOp)chi.Op;
2153                 if (projectNodeInfo.Definitions.IsSet(varDefOp.Var))
2154                 {
2155                     newVarDefListNode.Children.Add(chi);
2156                 }
2157             }
2158
2159             //
2160             // now that we have remapped all our computed vars, simply bypass the subproject
2161             // node
2162             //
2163             projectNode.Child0 = subProjectNode.Child0;
2164             projectNode.Child1 = newVarDefListNode;
2165             return true;
2166         }
2167         #endregion
2168
2169         #region ProjectWithNoLocalDefinitions
2170         internal static readonly PatternMatchRule Rule_ProjectWithNoLocalDefs =
2171             new PatternMatchRule(new Node(ProjectOp.Pattern,
2172                                           new Node(LeafOp.Pattern),
2173                                           new Node(VarDefListOp.Pattern)),
2174                                  ProcessProjectWithNoLocalDefinitions);
2175         /// <summary>
2176         /// Eliminate a ProjectOp that has no local definitions at all and
2177         /// no external references, (ie) if Child1
2178         /// of the ProjectOp (the VarDefListOp child) has no children, then the ProjectOp
2179         /// is serving no useful purpose. Get rid of the ProjectOp, and replace it with its
2180         /// child
2181         /// </summary>
2182         /// <param name="context">rule processing context</param>
2183         /// <param name="n">current subtree</param>
2184         /// <param name="newNode">transformed subtree</param>
2185         /// <returns>transformation status</returns>
2186         static bool ProcessProjectWithNoLocalDefinitions(RuleProcessingContext context, Node n, out Node newNode)
2187         {
2188             newNode = n;
2189             NodeInfo nodeInfo = context.Command.GetNodeInfo(n);
2190
2191             // We cannot eliminate this node because it can break other rules,
2192             // e.g. ProcessApplyOverAnything which relies on existance of external refs to substitute
2193             // CrossApply(x, y) => CrossJoin(x, y). See SQLBU #481719.
2194             if (!nodeInfo.ExternalReferences.IsEmpty)
2195             {
2196                 return false;
2197             }
2198
2199             newNode = n.Child0;
2200             return true;
2201         }
2202
2203         #endregion
2204
2205         #region ProjectOpWithSimpleVarRedefinitions
2206         internal static readonly SimpleRule Rule_ProjectOpWithSimpleVarRedefinitions = new SimpleRule(OpType.Project, ProcessProjectWithSimpleVarRedefinitions);
2207         /// <summary>
2208         /// If the ProjectOp defines some computedVars, but those computedVars are simply
2209         /// redefinitions of other Vars, then eliminate the computedVars.
2210         ///
2211         /// Project(X, VarDefList(VarDef(cv1, VarRef(v1)), ...))
2212         ///    can be transformed into
2213         /// Project(X, VarDefList(...))
2214         /// where cv1 has now been replaced by v1
2215         /// </summary>
2216         /// <param name="context">Rule processing context</param>
2217         /// <param name="n">current subtree</param>
2218         /// <param name="newNode">transformed subtree</param>
2219         /// <returns>transformation status</returns>
2220         static bool ProcessProjectWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode)
2221         {
2222             newNode = n;
2223             ProjectOp projectOp = (ProjectOp)n.Op;
2224
2225             if (n.Child1.Children.Count == 0)
2226             {
2227                 return false;
2228             }
2229
2230             TransformationRulesContext trc = (TransformationRulesContext)context;
2231             Command command = trc.Command;
2232
2233             ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
2234
2235             //
2236             // Check to see if any of the computed Vars defined by this ProjectOp
2237             // are simple redefinitions of other VarRefOps. Consider only those
2238             // VarRefOps that are not "external" references
2239             bool canEliminateSomeVars = false;
2240             foreach (Node varDefNode in n.Child1.Children)
2241             {
2242                 Node definingExprNode = varDefNode.Child0;
2243                 if (definingExprNode.Op.OpType == OpType.VarRef)
2244                 {
2245                     VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
2246                     if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
2247                     {
2248                         // this is a Var that we should remove
2249                         canEliminateSomeVars = true;
2250                         break;
2251                     }
2252                 }
2253             }
2254
2255             // Did we have any redefinitions
2256             if (!canEliminateSomeVars)
2257             {
2258                 return false;
2259             }
2260
2261             //
2262             // OK. We've now identified a set of vars that are simple redefinitions.
2263             // Try and replace the computed Vars with the Vars that they're redefining
2264             //
2265
2266             // Lets now build up a new VarDefListNode
2267             List<Node> newVarDefNodes = new List<Node>();
2268             foreach (Node varDefNode in n.Child1.Children)
2269             {
2270                 VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
2271                 VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
2272                 if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
2273                 {
2274                     projectOp.Outputs.Clear(varDefOp.Var);
2275                     projectOp.Outputs.Set(varRefOp.Var);
2276                     trc.AddVarMapping(varDefOp.Var, varRefOp.Var);
2277                 }
2278                 else
2279                 {
2280                     newVarDefNodes.Add(varDefNode);
2281                 }
2282             }
2283
2284             // Note: Even if we don't have any local var definitions left, we should not remove
2285             // this project yet because:
2286             //  (1) this project node may be prunning out some outputs;
2287             //  (2) the rule Rule_ProjectWithNoLocalDefs, would do that later anyway.
2288
2289             // Create a new vardeflist node, and set that as Child1 for the projectOp
2290             Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
2291             n.Child1 = newVarDefListNode;
2292             return true; // some part of the subtree was modified
2293         }
2294
2295
2296         #endregion
2297
2298         #region ProjectOpWithNullSentinel
2299         internal static readonly SimpleRule Rule_ProjectOpWithNullSentinel = new SimpleRule(OpType.Project, ProcessProjectOpWithNullSentinel);
2300         /// <summary>
2301         /// Tries to remove null sentinel definitions by replacing them to vars that are guaranteed
2302         /// to be non-nullable and of integer type, or with reference to other constants defined in the
2303         /// same project. In particular,
2304         ///
2305         ///  - If based on the ancestors, the value of the null sentinel can be changed and the
2306         /// input of the project has a var that is guaranteed to be non-nullable and
2307         /// is of integer type, then the definitions of the vars defined as NullSentinels in the ProjectOp
2308         /// are replaced with a reference to that var. I.eg:
2309         ///
2310         /// Project(X, VarDefList(VarDef(ns_var, NullSentinel), ...))
2311         ///    can be transformed into
2312         /// Project(X, VarDefList(VarDef(ns_var, VarRef(v))...))
2313         /// where v is known to be non-nullable
2314         ///
2315         /// - Else, if based on the ancestors, the value of the null sentinel can be changed and
2316         /// the project already has definitions of other int constants, the definitions of the null sentinels
2317         /// are removed and the respective vars are remapped to the var representing the constant.
2318         ///
2319         /// - Else, the definitions of the all null sentinels except for one are removed, and the
2320         /// the respective vars are remapped to the remaining null sentinel.
2321         /// </summary>
2322         /// <param name="context">Rule processing context</param>
2323         /// <param name="n">current subtree</param>
2324         /// <param name="newNode">transformed subtree</param>
2325         /// <returns>transformation status</returns>
2326         static bool ProcessProjectOpWithNullSentinel(RuleProcessingContext context, Node n, out Node newNode)
2327         {
2328             newNode = n;
2329             ProjectOp projectOp = (ProjectOp)n.Op;
2330             Node varDefListNode = n.Child1;
2331
2332             if (varDefListNode.Children.Where(c => c.Child0.Op.OpType == OpType.NullSentinel).Count() == 0)
2333             {
2334                 return false;
2335             }
2336
2337             TransformationRulesContext trc = (TransformationRulesContext)context;
2338             Command command = trc.Command;
2339             ExtendedNodeInfo relOpInputNodeInfo = command.GetExtendedNodeInfo(n.Child0);
2340             Var inputSentinel;
2341             bool reusingConstantFromSameProjectAsSentinel = false;
2342
2343             bool canChangeNullSentinelValue = trc.CanChangeNullSentinelValue;
2344
2345             if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(relOpInputNodeInfo.NonNullableDefinitions, out inputSentinel))
2346             {
2347                 reusingConstantFromSameProjectAsSentinel = true;
2348                 if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.Constant || child.Child0.Op.OpType == OpType.InternalConstant).Select(child => ((VarDefOp)(child.Op)).Var), out inputSentinel))
2349                 {
2350                     inputSentinel = n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.NullSentinel).Select(child => ((VarDefOp)(child.Op)).Var).FirstOrDefault();
2351                     if (inputSentinel == null)
2352                     {
2353                         return false;
2354                     }
2355                 }
2356             }
2357
2358             bool modified = false;
2359
2360             for (int i = n.Child1.Children.Count-1; i >= 0; i--)
2361             {
2362                 Node varDefNode = n.Child1.Children[i];
2363                 Node definingExprNode = varDefNode.Child0;
2364                 if (definingExprNode.Op.OpType == OpType.NullSentinel)
2365                 {
2366                     if (!reusingConstantFromSameProjectAsSentinel)
2367                     {
2368                         VarRefOp varRefOp = command.CreateVarRefOp(inputSentinel);
2369                         varDefNode.Child0 = command.CreateNode(varRefOp);
2370                         command.RecomputeNodeInfo(varDefNode);
2371                         modified = true;
2372                     }
2373                     else if (!inputSentinel.Equals(((VarDefOp)varDefNode.Op).Var))
2374                     {
2375                         projectOp.Outputs.Clear(((VarDefOp)varDefNode.Op).Var);
2376                         n.Child1.Children.RemoveAt(i);
2377                         trc.AddVarMapping(((VarDefOp)varDefNode.Op).Var, inputSentinel);
2378                         modified = true;
2379                     }
2380                 }
2381             }
2382
2383             if (modified)
2384             {
2385                 command.RecomputeNodeInfo(n.Child1);
2386             }
2387             return modified;
2388         }
2389         #endregion
2390
2391         #region All ProjectOp Rules
2392         //The order of the rules is important
2393         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
2394                  ProjectOpRules.Rule_ProjectOpWithNullSentinel,
2395                  ProjectOpRules.Rule_ProjectOpWithSimpleVarRedefinitions,
2396                  ProjectOpRules.Rule_ProjectOverProject,
2397                  ProjectOpRules.Rule_ProjectWithNoLocalDefs,
2398         };
2399         #endregion
2400     }
2401     #endregion
2402
2403     #region Apply Rules
2404     /// <summary>
2405     /// Transformation rules for ApplyOps - CrossApply, OuterApply
2406     /// </summary>
2407     internal static class ApplyOpRules
2408     {
2409         #region ApplyOverFilter
2410         internal static readonly PatternMatchRule Rule_CrossApplyOverFilter =
2411             new PatternMatchRule(new Node(CrossApplyOp.Pattern,
2412                                           new Node(LeafOp.Pattern),
2413                                           new Node(FilterOp.Pattern,
2414                                                    new Node(LeafOp.Pattern),
2415                                                    new Node(LeafOp.Pattern))),
2416                                  ProcessApplyOverFilter);
2417         internal static readonly PatternMatchRule Rule_OuterApplyOverFilter =
2418             new PatternMatchRule(new Node(OuterApplyOp.Pattern,
2419                                           new Node(LeafOp.Pattern),
2420                                           new Node(FilterOp.Pattern,
2421                                                    new Node(LeafOp.Pattern),
2422                                                    new Node(LeafOp.Pattern))),
2423                                  ProcessApplyOverFilter);
2424         /// <summary>
2425         /// Convert CrossApply(X, Filter(Y, p)) => InnerJoin(X, Y, p)
2426         ///         OuterApply(X, Filter(Y, p)) => LeftOuterJoin(X, Y, p)
2427         /// if "Y" has no external references to X
2428         /// </summary>
2429         /// <param name="context">Rule processing context</param>
2430         /// <param name="applyNode">Current ApplyOp</param>
2431         /// <param name="newNode">transformed subtree</param>
2432         /// <returns>Transformation status</returns>
2433         static bool ProcessApplyOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
2434         {
2435             newNode = applyNode;
2436             Node filterNode = applyNode.Child1;
2437             Command command = context.Command;
2438
2439             NodeInfo filterInputNodeInfo = command.GetNodeInfo(filterNode.Child0);
2440             ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
2441
2442             //
2443             // check to see if the inputNode to the FilterOp has any external references
2444             // to the left child of the ApplyOp. If it does, we simply return, we
2445             // can't do much more here
2446             //
2447             if (filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
2448             {
2449                 return false;
2450             }
2451
2452             //
2453             // We've now gotten to the stage where the only external references (if any)
2454             // are from the filter predicate.
2455             // We can now simply convert the apply into an inner/leftouter join with the
2456             // filter predicate acting as the join condition
2457             //
2458             JoinBaseOp joinOp = null;
2459             if (applyNode.Op.OpType == OpType.CrossApply)
2460             {
2461                 joinOp = command.CreateInnerJoinOp();
2462             }
2463             else
2464             {
2465                 joinOp = command.CreateLeftOuterJoinOp();
2466             }
2467
2468             newNode = command.CreateNode(joinOp, applyNode.Child0, filterNode.Child0, filterNode.Child1);
2469             return true;
2470         }
2471
2472         internal static readonly PatternMatchRule Rule_OuterApplyOverProjectInternalConstantOverFilter =
2473              new PatternMatchRule(new Node(OuterApplyOp.Pattern,
2474                                            new Node(LeafOp.Pattern),
2475                                            new Node(ProjectOp.Pattern,
2476                                                     new Node(FilterOp.Pattern,
2477                                                              new Node(LeafOp.Pattern),
2478                                                              new Node(LeafOp.Pattern)),
2479                                                     new Node(VarDefListOp.Pattern,
2480                                                              new Node(VarDefOp.Pattern,
2481                                                                       new Node(InternalConstantOp.Pattern))))),
2482                          ProcessOuterApplyOverDummyProjectOverFilter);
2483
2484         internal static readonly PatternMatchRule Rule_OuterApplyOverProjectNullSentinelOverFilter =
2485            new PatternMatchRule(new Node(OuterApplyOp.Pattern,
2486                                          new Node(LeafOp.Pattern),
2487                                          new Node(ProjectOp.Pattern,
2488                                                   new Node(FilterOp.Pattern,
2489                                                            new Node(LeafOp.Pattern),
2490                                                            new Node(LeafOp.Pattern)),
2491                                                   new Node(VarDefListOp.Pattern,
2492                                                            new Node(VarDefOp.Pattern,
2493                                                                     new Node(NullSentinelOp.Pattern))))),
2494                        ProcessOuterApplyOverDummyProjectOverFilter);
2495
2496         /// <summary>
2497         /// Convert OuterApply(X, Project(Filter(Y, p), constant)) =>
2498         ///     LeftOuterJoin(X, Project(Y, constant), p)
2499         /// if "Y" has no external references to X
2500         ///
2501         /// In an ideal world, we would be able to push the Project below the Filter,
2502         /// and then have the normal ApplyOverFilter rule handle this - but that causes us
2503         /// problems because we always try to pull up ProjectOp's as high as possible. Hence,
2504         /// the special case for this rule
2505         ///
2506         /// </summary>
2507         /// <param name="context">Rule processing context</param>
2508         /// <param name="applyNode">Current ApplyOp</param>
2509         /// <param name="newNode">transformed subtree</param>
2510         /// <returns>Transformation status</returns>
2511         static bool ProcessOuterApplyOverDummyProjectOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
2512         {
2513             newNode = applyNode;
2514             Node projectNode = applyNode.Child1;
2515             ProjectOp projectOp = (ProjectOp)projectNode.Op;
2516             Node filterNode = projectNode.Child0;
2517             Node filterInputNode = filterNode.Child0;
2518             Command command = context.Command;
2519
2520             ExtendedNodeInfo filterInputNodeInfo = command.GetExtendedNodeInfo(filterInputNode);
2521             ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
2522
2523             //
2524             // Check if the outputs of the ProjectOp or the inputNode to the FilterOp
2525             // have any external references to the left child of the ApplyOp.
2526             // If they do, we simply return, we can't do much more here
2527             //
2528             if (projectOp.Outputs.Overlaps(applyLeftChildNodeInfo.Definitions) || filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
2529             {
2530                 return false;
2531             }
2532
2533             //
2534             // We've now gotten to the stage where the only external references (if any)
2535             // are from the filter predicate.
2536             // First, push the Project node down below the filter - but make sure that
2537             // all the Vars needed by the Filter are projected out
2538             //
2539             bool capWithProject = false;
2540             Node joinNodeRightInput = null;
2541
2542             //
2543             // Check to see whether there is a sentinel var available - if there is, then
2544             // we can simply move the ProjectOp above the join we're going to construct
2545             // and of course, build a NullIf expression for the constant.
2546             // Otherwise, the ProjectOp will need to be the child of the joinOp that we're
2547             // building - and we'll need to make sure that the ProjectOp projects out
2548             // any vars that are required for the Filter in the first place
2549             //
2550             TransformationRulesContext trc = (TransformationRulesContext)context;
2551             Var sentinelVar;
2552             bool sentinelIsInt32;
2553
2554             if (TransformationRulesContext.TryGetInt32Var(filterInputNodeInfo.NonNullableDefinitions, out sentinelVar))
2555             {
2556                 sentinelIsInt32 = true;
2557             }
2558             else
2559             {
2560                 sentinelVar = filterInputNodeInfo.NonNullableDefinitions.First;
2561                 sentinelIsInt32 = false;
2562             }
2563
2564             if (sentinelVar != null)
2565             {
2566                 capWithProject = true;
2567                 Node varDefNode = projectNode.Child1.Child0;
2568                 if (varDefNode.Child0.Op.OpType == OpType.NullSentinel && sentinelIsInt32 && trc.CanChangeNullSentinelValue)
2569                 {
2570                     varDefNode.Child0 = context.Command.CreateNode(context.Command.CreateVarRefOp(sentinelVar));
2571                 }
2572                 else
2573                 {
2574                     varDefNode.Child0 = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
2575                 }
2576                 command.RecomputeNodeInfo(varDefNode);
2577                 command.RecomputeNodeInfo(projectNode.Child1);
2578                 joinNodeRightInput = filterInputNode;
2579             }
2580             else
2581             {
2582                 // We need to keep the projectNode - unfortunately
2583                 joinNodeRightInput = projectNode;
2584                 //
2585                 // Make sure that every Var that is needed for the filter predicate
2586                 // is captured in the projectOp outputs list
2587                 //
2588                 NodeInfo filterPredicateNodeInfo = command.GetNodeInfo(filterNode.Child1);
2589                 foreach (Var v in filterPredicateNodeInfo.ExternalReferences)
2590                 {
2591                     if (filterInputNodeInfo.Definitions.IsSet(v))
2592                     {
2593                         projectOp.Outputs.Set(v);
2594                     }
2595                 }
2596                 projectNode.Child0 = filterInputNode;
2597             }
2598
2599             context.Command.RecomputeNodeInfo(projectNode);
2600
2601             //
2602             // We can now simply convert the apply into an inner/leftouter join with the
2603             // filter predicate acting as the join condition
2604             //
2605             Node joinNode = command.CreateNode(command.CreateLeftOuterJoinOp(), applyNode.Child0, joinNodeRightInput, filterNode.Child1);
2606             if (capWithProject)
2607             {
2608                 ExtendedNodeInfo joinNodeInfo = command.GetExtendedNodeInfo(joinNode);
2609                 projectNode.Child0 = joinNode;
2610                 projectOp.Outputs.Or(joinNodeInfo.Definitions);
2611                 newNode = projectNode;
2612             }
2613             else
2614             {
2615                 newNode = joinNode;
2616             }
2617             return true;
2618         }
2619         #endregion
2620
2621         #region ApplyOverProject
2622         internal static readonly PatternMatchRule Rule_CrossApplyOverProject =
2623             new PatternMatchRule(new Node(CrossApplyOp.Pattern,
2624                                           new Node(LeafOp.Pattern),
2625                                           new Node(ProjectOp.Pattern,
2626                                                    new Node(LeafOp.Pattern),
2627                                                    new Node(LeafOp.Pattern))),
2628                                  ProcessCrossApplyOverProject);
2629
2630         /// <summary>
2631         /// Converts a CrossApply(X, Project(Y, ...)) => Project(CrossApply(X, Y), ...)
2632         /// where the projectVars are simply pulled up
2633         /// </summary>
2634         /// <param name="context">RuleProcessing context</param>
2635         /// <param name="applyNode">The ApplyOp subtree</param>
2636         /// <param name="newNode">transformed subtree</param>
2637         /// <returns>Transfomation status</returns>
2638         static bool ProcessCrossApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
2639         {
2640             newNode = applyNode;
2641             Node projectNode = applyNode.Child1;
2642             ProjectOp projectOp = (ProjectOp)projectNode.Op as ProjectOp;
2643             Command command = context.Command;
2644
2645             // We can simply pull up the project over the apply; provided we make sure
2646             // that all the definitions of the apply are represented in the projectOp
2647             ExtendedNodeInfo applyNodeInfo = command.GetExtendedNodeInfo(applyNode);
2648             VarVec vec = command.CreateVarVec(projectOp.Outputs);
2649             vec.Or(applyNodeInfo.Definitions);
2650             projectOp.Outputs.InitFrom(vec);
2651
2652             // pull up the project over the apply node
2653             applyNode.Child1 = projectNode.Child0;
2654             context.Command.RecomputeNodeInfo(applyNode);
2655             projectNode.Child0 = applyNode;
2656
2657             newNode = projectNode;
2658             return true;
2659         }
2660
2661         internal static readonly PatternMatchRule Rule_OuterApplyOverProject =
2662              new PatternMatchRule(new Node(OuterApplyOp.Pattern,
2663                                            new Node(LeafOp.Pattern),
2664                                            new Node(ProjectOp.Pattern,
2665                                                     new Node(LeafOp.Pattern),
2666                                                     new Node(LeafOp.Pattern))),
2667                          ProcessOuterApplyOverProject);
2668         /// <summary>
2669         /// Converts a
2670         ///     OuterApply(X, Project(Y, ...))
2671         /// =>
2672         ///     Project(OuterApply(X, Project(Y, ...)), ...) or
2673         ///     Project(OuterApply(X, Y), ...)
2674         ///
2675         /// The second (simpler) form is used if a "sentinel" var can be located (ie)
2676         /// some Var of Y that is guaranteed to be non-null. Otherwise, we create a
2677         /// dummy ProjectNode as the right child of the Apply - which
2678         /// simply projects out all the vars of the Y, and adds on a constant (say "1"). This
2679         /// constant is now treated as the sentinel var
2680         ///
2681         /// Then the existing ProjectOp is pulled up above the the outer-apply, but all the locally defined
2682         /// Vars have their defining expressions now expressed as
2683         ///     case when sentinelVar is null then null else oldDefiningExpr end
2684         /// where oldDefiningExpr represents the original defining expression
2685         /// This allows us to get nulls for the appropriate columns when necessary.
2686         ///
2687         /// Special cases.
2688         /// * If the oldDefiningExpr is itself an internal constant equivalent to the null sentinel ("1"),
2689         ///   we simply project a ref to the null sentinel, no need for cast
2690         /// * If the ProjectOp contained exactly one locally defined Var, and it was a constant, then
2691         ///   we simply return - we will be looping endlessly otherwise
2692         /// * If the ProjectOp contained no local definitions, then we don't need to create the
2693         ///   dummy projectOp - we can simply pull up the Project
2694         /// * If any of the defining expressions of the local definitions was simply a VarRefOp
2695         ///   referencing a Var that was defined by Y, then there is no need to add the case
2696         ///   expression for that.
2697         ///
2698         /// </summary>
2699         /// <param name="context">RuleProcessing context</param>
2700         /// <param name="applyNode">The ApplyOp subtree</param>
2701         /// <param name="newNode">transformed subtree</param>
2702         /// <returns>Transfomation status</returns>
2703         static bool ProcessOuterApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
2704         {
2705             newNode = applyNode;
2706             Node projectNode = applyNode.Child1;
2707             Node varDefListNode = projectNode.Child1;
2708
2709             TransformationRulesContext trc = (TransformationRulesContext)context;
2710             ExtendedNodeInfo inputNodeInfo = context.Command.GetExtendedNodeInfo(projectNode.Child0);
2711             Var sentinelVar = inputNodeInfo.NonNullableDefinitions.First;
2712
2713             //
2714             // special case handling first - we'll end up in an infinite loop otherwise.
2715             // If the ProjectOp is the dummy ProjectOp that we would be building (ie)
2716             // it defines only 1 var - and the defining expression is simply a constant
2717             //
2718             if (sentinelVar == null &&
2719                 varDefListNode.Children.Count == 1 &&
2720                 (varDefListNode.Child0.Child0.Op.OpType == OpType.InternalConstant || varDefListNode.Child0.Child0.Op.OpType == OpType.NullSentinel))
2721             {
2722                 return false;
2723             }
2724
2725             Command command = context.Command;
2726             Node dummyProjectNode = null;
2727             InternalConstantOp nullSentinelDefinitionOp = null;
2728
2729             // get node information for the project's child
2730             ExtendedNodeInfo projectInputNodeInfo = command.GetExtendedNodeInfo(projectNode.Child0);
2731
2732             //
2733             // Build up a dummy project node.
2734             // Walk through each local definition of the current project Node, and convert
2735             // all expressions into case expressions whose value depends on the var
2736             // produced by the dummy project node
2737             //
2738
2739             // Dev10 #480443: If any of the definitions changes we need to recompute the node info.
2740             bool anyVarDefChagned = false;
2741             foreach (Node varDefNode in varDefListNode.Children)
2742             {
2743                 PlanCompiler.Assert(varDefNode.Op.OpType == OpType.VarDef, "Expected VarDefOp. Found " + varDefNode.Op.OpType + " instead");
2744                 VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
2745                 if (varRefOp == null || !projectInputNodeInfo.Definitions.IsSet(varRefOp.Var))
2746                 {
2747                     // do we need to build a dummy project node
2748                     if (sentinelVar == null)
2749                     {
2750                         nullSentinelDefinitionOp = command.CreateInternalConstantOp(command.IntegerType, 1);
2751                         Node dummyConstantExpr = command.CreateNode(nullSentinelDefinitionOp);
2752                         Node dummyProjectVarDefListNode = command.CreateVarDefListNode(dummyConstantExpr, out sentinelVar);
2753                         ProjectOp dummyProjectOp = command.CreateProjectOp(sentinelVar);
2754                         dummyProjectOp.Outputs.Or(projectInputNodeInfo.Definitions);
2755                         dummyProjectNode = command.CreateNode(dummyProjectOp, projectNode.Child0, dummyProjectVarDefListNode);
2756                     }
2757
2758                     Node currentDefinition;
2759
2760                     // If the null sentinel was just created, and the local definition of the current project Node
2761                     // is an internal constant equivalent to the null sentinel, it can be rewritten as a reference
2762                     // to the null sentinel.
2763                     if (nullSentinelDefinitionOp != null && ((true == nullSentinelDefinitionOp.IsEquivalent(varDefNode.Child0.Op)) ||
2764                         //The null sentinel has the same value of 1, thus it is safe.
2765                         varDefNode.Child0.Op.OpType == OpType.NullSentinel))
2766                     {
2767                         currentDefinition = command.CreateNode(command.CreateVarRefOp(sentinelVar));
2768                     }
2769                     else
2770                     {
2771                         currentDefinition = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
2772                     }
2773                     varDefNode.Child0 = currentDefinition;
2774                     command.RecomputeNodeInfo(varDefNode);
2775                     anyVarDefChagned = true;
2776                 }
2777             }
2778
2779             // Recompute node info if needed
2780             if (anyVarDefChagned)
2781             {
2782                 command.RecomputeNodeInfo(varDefListNode);
2783             }
2784
2785             //
2786             // If we've created a dummy project node, make that the new child of the applyOp
2787             //
2788             applyNode.Child1 = dummyProjectNode != null ? dummyProjectNode : projectNode.Child0;
2789             command.RecomputeNodeInfo(applyNode);
2790
2791             //
2792             // Pull up the project node above the apply node now. Also, make sure that every Var of
2793             // the applyNode's definitions actually shows up in the new Project
2794             //
2795             projectNode.Child0 = applyNode;
2796             ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
2797             ProjectOp projectOp = (ProjectOp)projectNode.Op;
2798             projectOp.Outputs.Or(applyLeftChildNodeInfo.Definitions);
2799
2800             newNode = projectNode;
2801             return true;
2802         }
2803         #endregion
2804
2805         #region ApplyOverAnything
2806         internal static readonly PatternMatchRule Rule_CrossApplyOverAnything =
2807             new PatternMatchRule(new Node(CrossApplyOp.Pattern,
2808                                           new Node(LeafOp.Pattern),
2809                                           new Node(LeafOp.Pattern)),
2810                                  ProcessApplyOverAnything);
2811         internal static readonly PatternMatchRule Rule_OuterApplyOverAnything =
2812             new PatternMatchRule(new Node(OuterApplyOp.Pattern,
2813                                           new Node(LeafOp.Pattern),
2814                                           new Node(LeafOp.Pattern)),
2815                                  ProcessApplyOverAnything);
2816
2817         /// <summary>
2818         /// Converts a CrossApply(X,Y) => CrossJoin(X,Y)
2819         ///            OuterApply(X,Y) => LeftOuterJoin(X, Y, true)
2820         ///  only if Y has no external references to X
2821         /// </summary>
2822         /// <param name="context">Rule processing context</param>
2823         /// <param name="applyNode">The ApplyOp subtree</param>
2824         /// <param name="newNode">transformed subtree</param>
2825         /// <returns>the transformation status</returns>
2826         static bool ProcessApplyOverAnything(RuleProcessingContext context, Node applyNode, out Node newNode)
2827         {
2828             newNode = applyNode;
2829             Node applyLeftChild = applyNode.Child0;
2830             Node applyRightChild = applyNode.Child1;
2831             ApplyBaseOp applyOp = (ApplyBaseOp)applyNode.Op;
2832             Command command = context.Command;
2833
2834             ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyRightChild);
2835             ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyLeftChild);
2836
2837             //
2838             // If we're currently dealing with an OuterApply, and the right child is guaranteed
2839             // to produce at least one row, then we can convert the outer-apply into a cross apply
2840             //
2841             bool convertedToCrossApply = false;
2842             if (applyOp.OpType == OpType.OuterApply &&
2843                 applyRightChildNodeInfo.MinRows >= RowCount.One)
2844             {
2845                 applyOp = command.CreateCrossApplyOp();
2846                 convertedToCrossApply = true;
2847             }
2848
2849             //
2850             // Does the right child reference any of the definitions of the left child? If it
2851             // does, then simply return from this function
2852             //
2853             if (applyRightChildNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
2854             {
2855                 if (convertedToCrossApply)
2856                 {
2857                     newNode = command.CreateNode(applyOp, applyLeftChild, applyRightChild);
2858                     return true;
2859                 }
2860                 else
2861                 {
2862                     return false;
2863                 }
2864             }
2865
2866             //
2867             // So, we now know that the right child does not reference any definitions
2868             // from the left.
2869             // So, we simply convert the apply into an appropriate join Op
2870             //
2871             if (applyOp.OpType == OpType.CrossApply)
2872             {
2873                 //
2874                 // Convert "x CrossApply y" into "x CrossJoin y"
2875                 //
2876                 newNode = command.CreateNode(command.CreateCrossJoinOp(),
2877                     applyLeftChild, applyRightChild);
2878             }
2879             else // outer apply
2880             {
2881                 //
2882                 // Convert "x OA y" into "x LOJ y on (true)"
2883                 //
2884                 LeftOuterJoinOp joinOp = command.CreateLeftOuterJoinOp();
2885                 ConstantPredicateOp trueOp = command.CreateTrueOp();
2886                 Node trueNode = command.CreateNode(trueOp);
2887                 newNode = command.CreateNode(joinOp, applyLeftChild, applyRightChild, trueNode);
2888             }
2889             return true;
2890         }
2891         #endregion
2892
2893         #region ApplyIntoScalarSubquery
2894         internal static readonly PatternMatchRule Rule_CrossApplyIntoScalarSubquery =
2895             new PatternMatchRule(new Node(CrossApplyOp.Pattern,
2896                                           new Node(LeafOp.Pattern),
2897                                           new Node(LeafOp.Pattern)),
2898                                  ProcessApplyIntoScalarSubquery);
2899         internal static readonly PatternMatchRule Rule_OuterApplyIntoScalarSubquery =
2900             new PatternMatchRule(new Node(OuterApplyOp.Pattern,
2901                                           new Node(LeafOp.Pattern),
2902                                           new Node(LeafOp.Pattern)),
2903                                  ProcessApplyIntoScalarSubquery);
2904
2905         /// <summary>
2906         /// Converts a Apply(X,Y) => Project(X, Y1), where Y1 is a scalar subquery version of Y
2907         /// The transformation is valid only if all of the following conditions hold:
2908         ///     1. Y produces only one output
2909         ///     2. Y produces at most one row
2910         ///     3. Y produces at least one row, or the Apply operator in question is an OuterApply
2911         /// </summary>
2912         /// <param name="context">Rule processing context</param>
2913         /// <param name="applyNode">The ApplyOp subtree</param>
2914         /// <param name="newNode">transformed subtree</param>
2915         /// <returns>the transformation status</returns>
2916         static bool ProcessApplyIntoScalarSubquery(RuleProcessingContext context, Node applyNode, out Node newNode)
2917         {
2918             Command command = context.Command;
2919             ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child1);
2920             OpType applyKind = applyNode.Op.OpType;
2921
2922             if (!CanRewriteApply(applyNode.Child1, applyRightChildNodeInfo, applyKind))
2923             {
2924                 newNode = applyNode;
2925                 return false;
2926             }
2927
2928             // Create the project node over the original input with element over the apply as new projected var
2929             ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
2930
2931             Var oldVar = applyRightChildNodeInfo.Definitions.First;
2932
2933             // Project all the outputs from the left child
2934             VarVec projectOpOutputs = command.CreateVarVec(applyLeftChildNodeInfo.Definitions);
2935
2936             //
2937             // Remap the var defining tree to get it into a consistent state
2938             // and then remove all references to oldVar from it to avoid them being wrongly remapped to newVar
2939             // in subsequent remappings.
2940             //
2941             TransformationRulesContext trc = (TransformationRulesContext)context;
2942             trc.RemapSubtree(applyNode.Child1);
2943             VarDefinitionRemapper.RemapSubtree(applyNode.Child1, command, oldVar);
2944
2945             Node elementNode = command.CreateNode(command.CreateElementOp(oldVar.Type), applyNode.Child1);
2946
2947             Var newVar;
2948             Node varDefListNode = command.CreateVarDefListNode(elementNode, out newVar);
2949             projectOpOutputs.Set(newVar);
2950
2951             newNode = command.CreateNode(
2952                 command.CreateProjectOp(projectOpOutputs),
2953                 applyNode.Child0,
2954                 varDefListNode);
2955
2956             // Add the var mapping from oldVar to newVar
2957             trc.AddVarMapping(oldVar, newVar);
2958             return true;
2959         }
2960
2961         /// <summary>
2962         /// Determines whether an applyNode can be rewritten into a projection with a scalar subquery.
2963         /// It can be done if all of the following conditions hold:
2964         ///     1. The right child or the apply has only one output
2965         ///     2. The right child of the apply produces at most one row
2966         ///     3. The right child of the apply produces at least one row, or the Apply operator in question is an OuterApply
2967         /// </summary>
2968         /// <param name="rightChild"></param>
2969         /// <param name="applyRightChildNodeInfo"></param>
2970         /// <param name="applyKind"></param>
2971         /// <returns></returns>
2972         private static bool CanRewriteApply(Node rightChild, ExtendedNodeInfo applyRightChildNodeInfo, OpType applyKind)
2973         {
2974             //Check whether it produces only one definition
2975             if (applyRightChildNodeInfo.Definitions.Count != 1)
2976             {
2977                 return false;
2978             }
2979
2980             //Check whether it produces at most one row
2981             if (applyRightChildNodeInfo.MaxRows != RowCount.One)
2982             {
2983                 return false;
2984             }
2985
2986             //For cross apply it must also return exactly one row
2987             if (applyKind == OpType.CrossApply && (applyRightChildNodeInfo.MinRows != RowCount.One))
2988             {
2989                 return false;
2990             }
2991
2992             //Dev10 #488632: Make sure the right child not only declares to produce only one definition,
2993             // but has exactly one output. For example, ScanTableOp really outputs all the columns from the table,
2994             // but in its ExtendedNodeInfo.Definitions only these that are referenced are shown.
2995             // This is to allow for projection pruning of the unreferenced columns.
2996             if (OutputCountVisitor.CountOutputs(rightChild) != 1)
2997             {
2998                 return false;
2999             }
3000
3001             return true;
3002         }
3003
3004         /// <summary>
3005         /// A visitor that calculates the number of output columns for a subree
3006         /// with a given root
3007         /// </summary>
3008         internal class OutputCountVisitor : BasicOpVisitorOfT<int>
3009         {
3010             #region Constructors
3011             internal OutputCountVisitor()
3012             {
3013             }
3014             #endregion
3015
3016             #region Public Methods
3017             /// <summary>
3018             /// Calculates the number of output columns for the subree
3019             /// rooted at the given node
3020             /// </summary>
3021             /// <param name="node"></param>
3022             /// <returns></returns>
3023             internal static int CountOutputs(Node node)
3024             {
3025                 OutputCountVisitor visitor = new OutputCountVisitor();
3026                 return visitor.VisitNode(node);
3027             }
3028
3029             #endregion
3030
3031             #region Visitor Methods
3032
3033             #region Helpers
3034             /// <summary>
3035             /// Visitor for children. Simply visit all children,
3036             /// and sum the number of their outputs.
3037             /// </summary>
3038             /// <param name="n">Current node</param>
3039             /// <returns></returns>
3040             internal new int VisitChildren(Node n)
3041             {
3042                 int result = 0;
3043                 foreach (Node child in n.Children)
3044                 {
3045                     result += VisitNode(child);
3046                 }
3047                 return result;
3048             }
3049
3050             /// <summary>
3051             /// A default processor for any node.
3052             /// Returns the sum of the children outputs
3053             /// </summary>
3054             /// <param name="n"></param>
3055             /// <returns>/returns>
3056             protected override int VisitDefault(Node n)
3057             {
3058                 return VisitChildren(n);
3059             }
3060
3061             #endregion
3062
3063             #region RelOp Visitors
3064
3065             #region SetOp Visitors
3066
3067             /// <summary>
3068             /// The number of outputs is same as for any of the inputs
3069             /// </summary>
3070             /// <param name="op"></param>
3071             /// <param name="n"></param>
3072             /// <returns></returns>
3073             protected override int VisitSetOp(SetOp op, Node n)
3074             {
3075                 return op.Outputs.Count;
3076             }
3077
3078             #endregion
3079
3080             /// <summary>
3081             /// Distinct
3082             /// </summary>
3083             /// <param name="op"></param>
3084             /// <param name="n"></param>
3085             /// <returns></returns>
3086             public override int Visit(DistinctOp op, Node n)
3087             {
3088                 return op.Keys.Count;
3089             }
3090
3091             /// <summary>
3092             /// FilterOp
3093             /// </summary>
3094             /// <param name="op"></param>
3095             /// <param name="n"></param>
3096             /// <returns></returns>
3097             public override int Visit(FilterOp op, Node n)
3098             {
3099                 return VisitNode(n.Child0);
3100             }
3101
3102             /// <summary>
3103             /// GroupByOp
3104             /// </summary>
3105             /// <param name="op"></param>
3106             /// <param name="n"></param>
3107             /// <returns></returns>
3108             public override int Visit(GroupByOp op, Node n)
3109             {
3110                 return op.Outputs.Count;
3111             }
3112
3113             /// <summary>
3114             /// ProjectOp
3115             /// </summary>
3116             /// <param name="op"></param>
3117             /// <param name="n"></param>
3118             /// <returns></returns>
3119             public override int Visit(ProjectOp op, Node n)
3120             {
3121                 return op.Outputs.Count;
3122             }
3123
3124             #region TableOps
3125             /// <summary>
3126             /// ScanTableOp
3127             /// </summary>
3128             /// <param name="op"></param>
3129             /// <param name="n"></param>
3130             /// <returns></returns>
3131             public override int Visit(ScanTableOp op, Node n)
3132             {
3133                 return op.Table.Columns.Count;
3134             }
3135
3136             /// <summary>
3137             /// SingleRowTableOp
3138             /// </summary>
3139             /// <param name="op"></param>
3140             /// <param name="n"></param>
3141             /// <returns></returns>
3142             public override int Visit(SingleRowTableOp op, Node n)
3143             {
3144                 return 0;
3145             }
3146
3147             /// <summary>
3148             /// Same as the input
3149             /// </summary>
3150             /// <param name="op"></param>
3151             /// <param name="n"></param>
3152             /// <returns></returns>
3153             protected override int VisitSortOp(SortBaseOp op, Node n)
3154             {
3155                 return VisitNode(n.Child0);
3156             }
3157             #endregion
3158             #endregion
3159
3160             #endregion
3161         }
3162
3163         /// <summary>
3164         /// A utility class that remaps a given var at its definition and also remaps all its references.
3165         /// The given var is remapped to an arbitrary new var.
3166         /// If the var is defined by a ScanTable, all the vars defined by that table and all their references
3167         /// are remapped as well.
3168         /// </summary>
3169         internal class VarDefinitionRemapper : VarRemapper
3170         {
3171             private readonly Var m_oldVar;
3172
3173             private VarDefinitionRemapper(Var oldVar, Command command)
3174                 : base(command)
3175             {
3176                 this.m_oldVar = oldVar;
3177             }
3178
3179             /// <summary>
3180             /// Public entry point.
3181             /// Remaps the subree rooted at the given tree
3182             /// </summary>
3183             /// <param name="root"></param>
3184             /// <param name="command"></param>
3185             /// <param name="oldVar"></param>
3186             internal static void RemapSubtree(Node root, Command command, Var oldVar)
3187             {
3188                 VarDefinitionRemapper remapper = new VarDefinitionRemapper(oldVar, command);
3189                 remapper.RemapSubtree(root);
3190             }
3191
3192             /// <summary>
3193             /// Update vars in this subtree. Recompute the nodeinfo along the way
3194             /// Unlike the base implementation, we want to visit the childrent, even if no vars are in the
3195             /// remapping dictionary.
3196             /// </summary>
3197             /// <param name="subTree"></param>
3198             internal override void RemapSubtree(Node subTree)
3199             {
3200                 foreach (Node chi in subTree.Children)
3201                 {
3202                     RemapSubtree(chi);
3203                 }
3204
3205                 VisitNode(subTree);
3206                 m_command.RecomputeNodeInfo(subTree);
3207             }
3208
3209             /// <summary>
3210             /// If the node defines the node that needs to be remapped,
3211             /// it remaps it to a new var.
3212             /// </summary>
3213             /// <param name="op"></param>
3214             /// <param name="n"></param>
3215             /// <returns></returns>
3216             public override void Visit(VarDefOp op, Node n)
3217             {
3218                 if (op.Var == m_oldVar)
3219                 {
3220                     Var newVar = m_command.CreateComputedVar(n.Child0.Op.Type);
3221                     n.Op = m_command.CreateVarDefOp(newVar);
3222                     AddMapping(m_oldVar, newVar);
3223                 }
3224             }
3225
3226             /// <summary>
3227             /// If the columnVars defined by the table contain the var that needs to be remapped
3228             /// all the column vars produces by the table are remaped to new vars.
3229             /// </summary>
3230             /// <param name="op"></param>
3231             /// <param name="n"></param>
3232             /// <returns></returns>
3233             public override void Visit(ScanTableOp op, Node n)
3234             {
3235                 if (op.Table.Columns.Contains(m_oldVar))
3236                 {
3237                     ScanTableOp newScanTableOp = m_command.CreateScanTableOp(op.Table.TableMetadata);
3238                     VarDefListOp varDefListOp = m_command.CreateVarDefListOp();
3239                     for (int i = 0; i < op.Table.Columns.Count; i++)
3240                     {
3241                         AddMapping(op.Table.Columns[i], newScanTableOp.Table.Columns[i]);
3242                     }
3243                     n.Op = newScanTableOp;
3244                 }
3245             }
3246
3247             /// <summary>
3248             /// The var that needs to be remapped may be produced by a set op,
3249             /// in which case the varmaps need to be updated too.
3250             /// </summary>
3251             /// <param name="op"></param>
3252             /// <param name="n"></param>
3253             protected override void VisitSetOp(SetOp op, Node n)
3254             {
3255                 base.VisitSetOp(op, n);
3256
3257                 if (op.Outputs.IsSet(m_oldVar))
3258                 {
3259                     Var newVar = m_command.CreateSetOpVar(m_oldVar.Type);
3260                     op.Outputs.Clear(m_oldVar);
3261                     op.Outputs.Set(newVar);
3262                     RemapVarMapKey(op.VarMap[0], newVar);
3263                     RemapVarMapKey(op.VarMap[1], newVar);
3264                     AddMapping(m_oldVar, newVar);
3265                 }
3266             }
3267
3268             /// <summary>
3269             /// Replaces the entry in the varMap in which m_oldVar is a key
3270             /// with an entry in which newVAr is the key and the value remains the same.
3271             /// </summary>
3272             /// <param name="varMap"></param>
3273             /// <param name="newVar"></param>
3274             private void RemapVarMapKey(VarMap varMap, Var newVar)
3275             {
3276                 Var value = varMap[m_oldVar];
3277                 varMap.Remove(m_oldVar);
3278                 varMap.Add(newVar, value);
3279             }
3280         }
3281         #endregion
3282
3283         #region CrossApply over LeftOuterJoin of SingleRowTable with anything and with constant predicate
3284         internal static readonly PatternMatchRule Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable =
3285             new PatternMatchRule(new Node(CrossApplyOp.Pattern,
3286                 new Node(LeafOp.Pattern),
3287                 new Node(LeftOuterJoinOp.Pattern,
3288                                           new Node(SingleRowTableOp.Pattern),
3289                                           new Node(LeafOp.Pattern),
3290                                           new Node(ConstantPredicateOp.Pattern))),
3291                                  ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable);
3292         /// <summary>
3293         /// Convert a CrossApply(X, LeftOuterJoin(SingleRowTable, Y, on true))
3294         ///    into just OuterApply(X, Y)
3295         /// </summary>
3296         /// <param name="context">rule processing context</param>
3297         /// <param name="joinNode">the join node</param>
3298         /// <param name="newNode">transformed subtree</param>
3299         /// <returns>transformation status</returns>
3300         static bool ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable(RuleProcessingContext context, Node applyNode, out Node newNode)
3301         {
3302             newNode = applyNode;
3303             Node joinNode = applyNode.Child1;
3304
3305             //Check the value of the predicate
3306             ConstantPredicateOp joinPredicate = (ConstantPredicateOp)joinNode.Child2.Op;
3307             if (joinPredicate.IsFalse)
3308             {
3309                 return false;
3310             }
3311
3312             applyNode.Op = context.Command.CreateOuterApplyOp();
3313             applyNode.Child1 = joinNode.Child1;
3314             return true;
3315         }
3316         #endregion
3317
3318         #region All ApplyOp Rules
3319         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
3320                  ApplyOpRules.Rule_CrossApplyOverAnything,
3321                  ApplyOpRules.Rule_CrossApplyOverFilter,
3322                  ApplyOpRules.Rule_CrossApplyOverProject,
3323                  ApplyOpRules.Rule_OuterApplyOverAnything,
3324                  ApplyOpRules.Rule_OuterApplyOverProjectInternalConstantOverFilter,
3325                  ApplyOpRules.Rule_OuterApplyOverProjectNullSentinelOverFilter,
3326                  ApplyOpRules.Rule_OuterApplyOverProject,
3327                  ApplyOpRules.Rule_OuterApplyOverFilter,
3328                  ApplyOpRules.Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable,
3329                  ApplyOpRules.Rule_CrossApplyIntoScalarSubquery,
3330                  ApplyOpRules.Rule_OuterApplyIntoScalarSubquery,
3331         };
3332         #endregion
3333     }
3334     #endregion
3335
3336     #region Join Rules
3337     /// <summary>
3338     /// Transformation rules for JoinOps
3339     /// </summary>
3340     internal static class JoinOpRules
3341     {
3342         #region JoinOverProject
3343         internal static readonly PatternMatchRule Rule_CrossJoinOverProject1 =
3344             new PatternMatchRule(new Node(CrossJoinOp.Pattern,
3345                                           new Node(LeafOp.Pattern),
3346                                           new Node(ProjectOp.Pattern,
3347                                                    new Node(LeafOp.Pattern),
3348                                                    new Node(LeafOp.Pattern))),
3349                                  ProcessJoinOverProject);
3350         internal static readonly PatternMatchRule Rule_CrossJoinOverProject2 =
3351             new PatternMatchRule(new Node(CrossJoinOp.Pattern,
3352                                           new Node(ProjectOp.Pattern,
3353                                                    new Node(LeafOp.Pattern),
3354                                                    new Node(LeafOp.Pattern)),
3355                                           new Node(LeafOp.Pattern)),
3356                                  ProcessJoinOverProject);
3357         internal static readonly PatternMatchRule Rule_InnerJoinOverProject1 =
3358             new PatternMatchRule(new Node(InnerJoinOp.Pattern,
3359                                           new Node(LeafOp.Pattern),
3360                                           new Node(ProjectOp.Pattern,
3361                                                    new Node(LeafOp.Pattern),
3362                                                    new Node(LeafOp.Pattern)),
3363                                           new Node(LeafOp.Pattern)),
3364                                  ProcessJoinOverProject);
3365         internal static readonly PatternMatchRule Rule_InnerJoinOverProject2 =
3366             new PatternMatchRule(new Node(InnerJoinOp.Pattern,
3367                                           new Node(ProjectOp.Pattern,
3368                                                    new Node(LeafOp.Pattern),
3369                                                    new Node(LeafOp.Pattern)),
3370                                           new Node(LeafOp.Pattern),
3371                                           new Node(LeafOp.Pattern)),
3372                                  ProcessJoinOverProject);
3373         internal static readonly PatternMatchRule Rule_OuterJoinOverProject2 =
3374             new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
3375                                           new Node(ProjectOp.Pattern,
3376                                                    new Node(LeafOp.Pattern),
3377                                                    new Node(LeafOp.Pattern)),
3378                                           new Node(LeafOp.Pattern),
3379                                           new Node(LeafOp.Pattern)),
3380                                  ProcessJoinOverProject);
3381         /// <summary>
3382         /// CrossJoin(Project(A), B) => Project(CrossJoin(A, B), modifiedvars)
3383         /// InnerJoin(Project(A), B, p) => Project(InnerJoin(A, B, p'), modifiedvars)
3384         /// LeftOuterJoin(Project(A), B, p) => Project(LeftOuterJoin(A, B, p'), modifiedvars)
3385         /// </summary>
3386         /// <param name="context">Rule processing context</param>
3387         /// <param name="joinNode">Current JoinOp tree to process</param>
3388         /// <param name="newNode">Transformed subtree</param>
3389         /// <returns>transformation status</returns>
3390         static bool ProcessJoinOverProject(RuleProcessingContext context, Node joinNode, out Node newNode)
3391         {
3392             newNode = joinNode;
3393
3394             TransformationRulesContext trc = (TransformationRulesContext)context;
3395             Command command = trc.Command;
3396
3397             Node joinConditionNode = joinNode.HasChild2 ? joinNode.Child2 : (Node)null;
3398             Dictionary<Var, int> varRefMap = new Dictionary<Var, int>();
3399             if (joinConditionNode != null && !trc.IsScalarOpTree(joinConditionNode, varRefMap))
3400             {
3401                 return false;
3402             }
3403
3404             Node newJoinNode;
3405             Node newProjectNode;
3406
3407             // Now locate the ProjectOps
3408             VarVec newVarSet = command.CreateVarVec();
3409             List<Node> varDefNodes = new List<Node>();
3410
3411             //
3412             // Try and handle "project" on both sides only if we're not dealing with
3413             // an LOJ.
3414             //
3415             if ((joinNode.Op.OpType != OpType.LeftOuterJoin) &&
3416                 (joinNode.Child0.Op.OpType == OpType.Project) &&
3417                 (joinNode.Child1.Op.OpType == OpType.Project))
3418             {
3419                 ProjectOp projectOp1 = (ProjectOp)joinNode.Child0.Op;
3420                 ProjectOp projectOp2 = (ProjectOp)joinNode.Child1.Op;
3421
3422                 Dictionary<Var, Node> varMap1 = trc.GetVarMap(joinNode.Child0.Child1, varRefMap);
3423                 Dictionary<Var, Node> varMap2 = trc.GetVarMap(joinNode.Child1.Child1, varRefMap);
3424                 if (varMap1 == null || varMap2 == null)
3425                 {
3426                     return false;
3427                 }
3428
3429                 if (joinConditionNode != null)
3430                 {
3431                     joinConditionNode = trc.ReMap(joinConditionNode, varMap1);
3432                     joinConditionNode = trc.ReMap(joinConditionNode, varMap2);
3433                     newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0, joinConditionNode);
3434                 }
3435                 else
3436                 {
3437                     newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0);
3438                 }
3439
3440                 newVarSet.InitFrom(projectOp1.Outputs);
3441                 foreach (Var v in projectOp2.Outputs)
3442                 {
3443                     newVarSet.Set(v);
3444                 }
3445                 ProjectOp newProjectOp = command.CreateProjectOp(newVarSet);
3446                 varDefNodes.AddRange(joinNode.Child0.Child1.Children);
3447                 varDefNodes.AddRange(joinNode.Child1.Child1.Children);
3448                 Node varDefListNode = command.CreateNode(
3449                     command.CreateVarDefListOp(),
3450                     varDefNodes);
3451                 newProjectNode = command.CreateNode(newProjectOp,
3452                     newJoinNode, varDefListNode);
3453                 newNode = newProjectNode;
3454                 return true;
3455             }
3456
3457             int projectNodeIdx = -1;
3458             int otherNodeIdx = -1;
3459             if (joinNode.Child0.Op.OpType == OpType.Project)
3460             {
3461                 projectNodeIdx = 0;
3462                 otherNodeIdx = 1;
3463             }
3464             else
3465             {
3466                 PlanCompiler.Assert(joinNode.Op.OpType != OpType.LeftOuterJoin, "unexpected non-LeftOuterJoin");
3467                 projectNodeIdx = 1;
3468                 otherNodeIdx = 0;
3469             }
3470             Node projectNode = joinNode.Children[projectNodeIdx];
3471
3472             ProjectOp projectOp = projectNode.Op as ProjectOp;
3473             Dictionary<Var, Node> varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
3474             if (varMap == null)
3475             {
3476                 return false;
3477             }
3478             ExtendedNodeInfo otherChildInfo = command.GetExtendedNodeInfo(joinNode.Children[otherNodeIdx]);
3479             VarVec vec = command.CreateVarVec(projectOp.Outputs);
3480             vec.Or(otherChildInfo.Definitions);
3481             projectOp.Outputs.InitFrom(vec);
3482             if (joinConditionNode != null)
3483             {
3484                 joinConditionNode = trc.ReMap(joinConditionNode, varMap);
3485                 joinNode.Child2 = joinConditionNode;
3486             }
3487             joinNode.Children[projectNodeIdx] = projectNode.Child0; // bypass the projectOp
3488             context.Command.RecomputeNodeInfo(joinNode);
3489
3490             newNode = context.Command.CreateNode(projectOp, joinNode, projectNode.Child1);
3491             return true;
3492         }
3493         #endregion
3494
3495         #region JoinOverFilter
3496         internal static readonly PatternMatchRule Rule_CrossJoinOverFilter1 =
3497             new PatternMatchRule(new Node(CrossJoinOp.Pattern,
3498                                           new Node(LeafOp.Pattern),
3499                                           new Node(FilterOp.Pattern,
3500                                                    new Node(LeafOp.Pattern),
3501                                                    new Node(LeafOp.Pattern))),
3502                                  ProcessJoinOverFilter);
3503         internal static readonly PatternMatchRule Rule_CrossJoinOverFilter2 =
3504             new PatternMatchRule(new Node(CrossJoinOp.Pattern,
3505                                           new Node(FilterOp.Pattern,
3506                                                    new Node(LeafOp.Pattern),
3507                                                    new Node(LeafOp.Pattern)),
3508                                           new Node(LeafOp.Pattern)),
3509                                  ProcessJoinOverFilter);
3510         internal static readonly PatternMatchRule Rule_InnerJoinOverFilter1 =
3511             new PatternMatchRule(new Node(InnerJoinOp.Pattern,
3512                                           new Node(LeafOp.Pattern),
3513                                           new Node(FilterOp.Pattern,
3514                                                    new Node(LeafOp.Pattern),
3515                                                    new Node(LeafOp.Pattern)),
3516                                           new Node(LeafOp.Pattern)),
3517                                  ProcessJoinOverFilter);
3518         internal static readonly PatternMatchRule Rule_InnerJoinOverFilter2 =
3519             new PatternMatchRule(new Node(InnerJoinOp.Pattern,
3520                                           new Node(FilterOp.Pattern,
3521                                                    new Node(LeafOp.Pattern),
3522                                                    new Node(LeafOp.Pattern)),
3523                                           new Node(LeafOp.Pattern),
3524                                           new Node(LeafOp.Pattern)),
3525                                  ProcessJoinOverFilter);
3526         internal static readonly PatternMatchRule Rule_OuterJoinOverFilter2 =
3527             new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
3528                                           new Node(FilterOp.Pattern,
3529                                                    new Node(LeafOp.Pattern),
3530                                                    new Node(LeafOp.Pattern)),
3531                                           new Node(LeafOp.Pattern),
3532                                           new Node(LeafOp.Pattern)),
3533                                  ProcessJoinOverFilter);
3534         /// <summary>
3535         /// CrossJoin(Filter(A,p), B) => Filter(CrossJoin(A, B), p)
3536         /// CrossJoin(A, Filter(B,p)) => Filter(CrossJoin(A, B), p)
3537         ///
3538         /// InnerJoin(Filter(A,p), B, c) => Filter(InnerJoin(A, B, c), p)
3539         /// InnerJoin(A, Filter(B,p), c) => Filter(InnerJoin(A, B, c), p)
3540         ///
3541         /// LeftOuterJoin(Filter(A,p), B, c) => Filter(LeftOuterJoin(A, B, c), p)
3542         ///
3543         /// Note that the predicate on the right table in a left-outer-join cannot be pulled
3544         /// up above the join.
3545         ///
3546         /// </summary>
3547         /// <param name="context">Rule processing context</param>
3548         /// <param name="joinNode">Current JoinOp tree to process</param>
3549         /// <param name="newNode">transformed subtree</param>
3550         /// <returns>transformation status</returns>
3551         static bool ProcessJoinOverFilter(RuleProcessingContext context, Node joinNode, out Node newNode)
3552         {
3553             newNode = joinNode;
3554             TransformationRulesContext trc = (TransformationRulesContext)context;
3555             Command command = trc.Command;
3556
3557             Node predicateNode = null;
3558             Node newLeftInput = joinNode.Child0;
3559             // get the predicate from the first filter
3560             if (joinNode.Child0.Op.OpType == OpType.Filter)
3561             {
3562                 predicateNode = joinNode.Child0.Child1;
3563                 newLeftInput = joinNode.Child0.Child0; // bypass the filter
3564             }
3565
3566             // get the predicate from the second filter
3567             Node newRightInput = joinNode.Child1;
3568             if (joinNode.Child1.Op.OpType == OpType.Filter && joinNode.Op.OpType != OpType.LeftOuterJoin)
3569             {
3570                 if (predicateNode == null)
3571                 {
3572                     predicateNode = joinNode.Child1.Child1;
3573                 }
3574                 else
3575                 {
3576                     predicateNode = command.CreateNode(
3577                         command.CreateConditionalOp(OpType.And),
3578                         predicateNode, joinNode.Child1.Child1);
3579                 }
3580                 newRightInput = joinNode.Child1.Child0; // bypass the filter
3581             }
3582
3583             // No optimizations to perform if we can't locate the appropriate predicate
3584             if (predicateNode == null)
3585             {
3586                 return false;
3587             }
3588
3589             //
3590             // Create a new join node with the new inputs
3591             //
3592             Node newJoinNode;
3593             if (joinNode.Op.OpType == OpType.CrossJoin)
3594             {
3595                 newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput);
3596             }
3597             else
3598             {
3599                 newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput, joinNode.Child2);
3600             }
3601
3602             //
3603             // create a new filterOp with the combined predicates, and with the
3604             // newjoinNode as the input
3605             //
3606             FilterOp newFilterOp = command.CreateFilterOp();
3607             newNode = command.CreateNode(newFilterOp, newJoinNode, predicateNode);
3608
3609             //
3610             // Mark this subtree so that we don't try to push filters down again
3611             //
3612             trc.SuppressFilterPushdown(newNode);
3613             return true;
3614         }
3615         #endregion
3616
3617         #region Join over SingleRowTable
3618         internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable1 =
3619             new PatternMatchRule(new Node(CrossJoinOp.Pattern,
3620                                           new Node(SingleRowTableOp.Pattern),
3621                                           new Node(LeafOp.Pattern)),
3622                                  ProcessJoinOverSingleRowTable);
3623         internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable2 =
3624             new PatternMatchRule(new Node(CrossJoinOp.Pattern,
3625                                           new Node(LeafOp.Pattern),
3626                                           new Node(SingleRowTableOp.Pattern)),
3627                                  ProcessJoinOverSingleRowTable);
3628
3629         internal static readonly PatternMatchRule Rule_LeftOuterJoinOverSingleRowTable =
3630            new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
3631                                          new Node(LeafOp.Pattern),
3632                                          new Node(SingleRowTableOp.Pattern),
3633                                          new Node(LeafOp.Pattern)),
3634                                 ProcessJoinOverSingleRowTable);
3635         /// <summary>
3636         /// Convert a CrossJoin(SingleRowTable, X) or CrossJoin(X, SingleRowTable) or LeftOuterJoin(X, SingleRowTable)
3637         ///    into just "X"
3638         /// </summary>
3639         /// <param name="context">rule processing context</param>
3640         /// <param name="joinNode">the join node</param>
3641         /// <param name="newNode">transformed subtree</param>
3642         /// <returns>transformation status</returns>
3643         static bool ProcessJoinOverSingleRowTable(RuleProcessingContext context, Node joinNode, out Node newNode)
3644         {
3645             newNode = joinNode;
3646
3647             if (joinNode.Child0.Op.OpType == OpType.SingleRowTable)
3648             {
3649                 newNode = joinNode.Child1;
3650             }
3651             else
3652             {
3653                 newNode = joinNode.Child0;
3654             }
3655             return true;
3656         }
3657         #endregion
3658
3659         #region Misc
3660         #endregion
3661
3662         #region All JoinOp Rules
3663         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
3664             Rule_CrossJoinOverProject1,
3665             Rule_CrossJoinOverProject2,
3666             Rule_InnerJoinOverProject1,
3667             Rule_InnerJoinOverProject2,
3668             Rule_OuterJoinOverProject2,
3669
3670             Rule_CrossJoinOverFilter1,
3671             Rule_CrossJoinOverFilter2,
3672             Rule_InnerJoinOverFilter1,
3673             Rule_InnerJoinOverFilter2,
3674             Rule_OuterJoinOverFilter2,
3675
3676             Rule_CrossJoinOverSingleRowTable1,
3677             Rule_CrossJoinOverSingleRowTable2,
3678             Rule_LeftOuterJoinOverSingleRowTable,
3679         };
3680
3681         #endregion
3682     }
3683     #endregion
3684
3685     #region SingleRowOp Rules
3686     /// <summary>
3687     /// Rules for SingleRowOp
3688     /// </summary>
3689     internal static class SingleRowOpRules
3690     {
3691         internal static readonly PatternMatchRule Rule_SingleRowOpOverAnything =
3692             new PatternMatchRule(new Node(SingleRowOp.Pattern,
3693                                      new Node(LeafOp.Pattern)),
3694                                  ProcessSingleRowOpOverAnything);
3695         /// <summary>
3696         /// Convert a
3697         ///    SingleRowOp(X) => X
3698         /// if X produces at most one row
3699         /// </summary>
3700         /// <param name="context">Rule Processing context</param>
3701         /// <param name="singleRowNode">Current subtree</param>
3702         /// <param name="newNode">transformed subtree</param>
3703         /// <returns>Transformation status</returns>
3704         static bool ProcessSingleRowOpOverAnything(RuleProcessingContext context, Node singleRowNode, out Node newNode)
3705         {
3706             newNode = singleRowNode;
3707             TransformationRulesContext trc = (TransformationRulesContext)context;
3708             ExtendedNodeInfo childNodeInfo = context.Command.GetExtendedNodeInfo(singleRowNode.Child0);
3709
3710             // If the input to this Op can produce at most one row, then we don't need the
3711             // singleRowOp - simply return the input
3712             if (childNodeInfo.MaxRows <= RowCount.One)
3713             {
3714                 newNode = singleRowNode.Child0;
3715                 return true;
3716             }
3717
3718             //
3719             // if the current node is a FilterOp, then try and determine if the FilterOp
3720             // produces one row at most
3721             //
3722             if (singleRowNode.Child0.Op.OpType == OpType.Filter)
3723             {
3724                 Predicate predicate = new Predicate(context.Command, singleRowNode.Child0.Child1);
3725                 if (predicate.SatisfiesKey(childNodeInfo.Keys.KeyVars, childNodeInfo.Definitions))
3726                 {
3727                     childNodeInfo.MaxRows = RowCount.One;
3728                     newNode = singleRowNode.Child0;
3729                     return true;
3730                 }
3731             }
3732
3733             // we couldn't do anything
3734             return false;
3735         }
3736
3737         internal static readonly PatternMatchRule Rule_SingleRowOpOverProject =
3738            new PatternMatchRule(new Node(SingleRowOp.Pattern,
3739                              new Node(ProjectOp.Pattern,
3740                                    new Node(LeafOp.Pattern), new Node(LeafOp.Pattern))),
3741                          ProcessSingleRowOpOverProject);
3742         /// <summary>
3743         /// Convert
3744         ///    SingleRowOp(Project) => Project(SingleRowOp)
3745         /// </summary>
3746         /// <param name="context">Rule Processing context</param>
3747         /// <param name="singleRowNode">current subtree</param>
3748         /// <param name="newNode">transformeed subtree</param>
3749         /// <returns>transformation status</returns>
3750         static bool ProcessSingleRowOpOverProject(RuleProcessingContext context, Node singleRowNode, out Node newNode)
3751         {
3752             newNode = singleRowNode;
3753             Node projectNode = singleRowNode.Child0;
3754             Node projectNodeInput = projectNode.Child0;
3755
3756             // Simply push the SingleRowOp below the ProjectOp
3757             singleRowNode.Child0 = projectNodeInput;
3758             context.Command.RecomputeNodeInfo(singleRowNode);
3759             projectNode.Child0 = singleRowNode;
3760
3761             newNode = projectNode;
3762             return true; // subtree modified internally
3763         }
3764
3765         #region All SingleRowOp Rules
3766         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
3767             Rule_SingleRowOpOverAnything,
3768             Rule_SingleRowOpOverProject,
3769         };
3770         #endregion
3771     }
3772     #endregion
3773
3774     #region SetOp Rules
3775     /// <summary>
3776     /// SetOp Transformation Rules
3777     /// </summary>
3778     internal static class SetOpRules
3779     {
3780         #region SetOpOverFilters
3781         internal static readonly SimpleRule Rule_UnionAllOverEmptySet =
3782             new SimpleRule(OpType.UnionAll, ProcessSetOpOverEmptySet);
3783         internal static readonly SimpleRule Rule_IntersectOverEmptySet =
3784             new SimpleRule(OpType.Intersect, ProcessSetOpOverEmptySet);
3785         internal static readonly SimpleRule Rule_ExceptOverEmptySet =
3786             new SimpleRule(OpType.Except, ProcessSetOpOverEmptySet);
3787
3788         /// <summary>
3789         /// Process a SetOp when one of the inputs is an emptyset.
3790         ///
3791         /// An emptyset is represented by a Filter(X, ConstantPredicate)
3792         ///    where the ConstantPredicate has a value of "false"
3793         ///
3794         /// The general rules are
3795         ///    UnionAll(X, EmptySet) => X
3796         ///    UnionAll(EmptySet, X) => X
3797         ///    Intersect(EmptySet, X) => EmptySet
3798         ///    Intersect(X, EmptySet) => EmptySet
3799         ///    Except(EmptySet, X) => EmptySet
3800         ///    Except(X, EmptySet) => X
3801         ///
3802         /// These rules then translate into
3803         ///    UnionAll: return the non-empty input
3804         ///    Intersect: return the empty input
3805         ///    Except: return the "left" input
3806         /// </summary>
3807         /// <param name="context">Rule processing context</param>
3808         /// <param name="setOpNode">the current setop tree</param>
3809         /// <param name="filterNodeIndex">Index of the filter node in the setop</param>
3810         /// <param name="newNode">transformed subtree</param>
3811         /// <returns>transformation status</returns>
3812         private static bool ProcessSetOpOverEmptySet(RuleProcessingContext context, Node setOpNode, out Node newNode)
3813         {
3814             bool leftChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child0).MaxRows == RowCount.Zero;
3815             bool rightChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child1).MaxRows == RowCount.Zero;
3816
3817             if (!leftChildIsEmptySet && !rightChildIsEmptySet)
3818             {
3819                 newNode = setOpNode;
3820                 return false;
3821             }
3822
3823             int indexToReturn;
3824             SetOp setOp = (SetOp)setOpNode.Op;
3825             if (!rightChildIsEmptySet && setOp.OpType == OpType.UnionAll ||
3826                 !leftChildIsEmptySet && setOp.OpType == OpType.Intersect)
3827             {
3828                 indexToReturn = 1;
3829             }
3830             else
3831             {
3832                 indexToReturn = 0;
3833             }
3834
3835             newNode = setOpNode.Children[indexToReturn];
3836
3837             TransformationRulesContext trc = (TransformationRulesContext)context;
3838             foreach (KeyValuePair<Var, Var> kv in setOp.VarMap[indexToReturn])
3839             {
3840                 trc.AddVarMapping(kv.Key, kv.Value);
3841             }
3842             return true;
3843         }
3844
3845         #endregion
3846
3847         #region All SetOp Rules
3848         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
3849             Rule_UnionAllOverEmptySet,
3850             Rule_IntersectOverEmptySet,
3851             Rule_ExceptOverEmptySet,
3852         };
3853         #endregion
3854     }
3855     #endregion
3856
3857     #region GroupByOp Rules
3858     /// <summary>
3859     /// Transformation Rules for GroupByOps
3860     /// </summary>
3861     internal static class GroupByOpRules
3862     {
3863         #region GroupByOpWithSimpleVarRedefinitions
3864         internal static readonly SimpleRule Rule_GroupByOpWithSimpleVarRedefinitions = new SimpleRule(OpType.GroupBy, ProcessGroupByWithSimpleVarRedefinitions);
3865         /// <summary>
3866         /// If the GroupByOp defines some computedVars as part of its keys, but those computedVars are simply
3867         /// redefinitions of other Vars, then eliminate the computedVars.
3868         ///
3869         /// GroupBy(X, VarDefList(VarDef(cv1, VarRef(v1)), ...), VarDefList(...))
3870         ///    can be transformed into
3871         /// GroupBy(X, VarDefList(...))
3872         /// where cv1 has now been replaced by v1
3873         /// </summary>
3874         /// <param name="context">Rule processing context</param>
3875         /// <param name="n">current subtree</param>
3876         /// <param name="newNode">transformed subtree</param>
3877         /// <returns>transformation status</returns>
3878         static bool ProcessGroupByWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode)
3879         {
3880             newNode = n;
3881             GroupByOp groupByOp = (GroupByOp)n.Op;
3882             // no local keys? nothing to do
3883             if (n.Child1.Children.Count == 0)
3884             {
3885                 return false;
3886             }
3887
3888             TransformationRulesContext trc = (TransformationRulesContext)context;
3889             Command command = trc.Command;
3890
3891             ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
3892
3893             //
3894             // Check to see if any of the computed Vars defined by this GroupByOp
3895             // are simple redefinitions of other VarRefOps. Consider only those
3896             // VarRefOps that are not "external" references
3897             //
3898             bool canEliminateSomeVars = false;
3899             foreach (Node varDefNode in n.Child1.Children)
3900             {
3901                 Node definingExprNode = varDefNode.Child0;
3902                 if (definingExprNode.Op.OpType == OpType.VarRef)
3903                 {
3904                     VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
3905                     if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
3906                     {
3907                         // this is a Var that we should remove
3908                         canEliminateSomeVars = true;
3909                     }
3910                 }
3911             }
3912
3913             // Did we have any redefinitions
3914             if (!canEliminateSomeVars)
3915             {
3916                 return false;
3917             }
3918
3919             //
3920             // OK. We've now identified a set of vars that are simple redefinitions.
3921             // Try and replace the computed Vars with the Vars that they're redefining
3922             //
3923
3924             // Lets now build up a new VarDefListNode
3925             List<Node> newVarDefNodes = new List<Node>();
3926             foreach (Node varDefNode in n.Child1.Children)
3927             {
3928                 VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
3929                 VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
3930                 if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
3931                 {
3932                     groupByOp.Outputs.Clear(varDefOp.Var);
3933                     groupByOp.Outputs.Set(varRefOp.Var);
3934                     groupByOp.Keys.Clear(varDefOp.Var);
3935                     groupByOp.Keys.Set(varRefOp.Var);
3936                     trc.AddVarMapping(varDefOp.Var, varRefOp.Var);
3937                 }
3938                 else
3939                 {
3940                     newVarDefNodes.Add(varDefNode);
3941                 }
3942             }
3943
3944             // Create a new vardeflist node, and set that as Child1 for the group by op
3945             Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
3946             n.Child1 = newVarDefListNode;
3947             return true; // subtree modified
3948         }
3949         #endregion
3950
3951         #region GroupByOverProject
3952         internal static readonly PatternMatchRule Rule_GroupByOverProject =
3953             new PatternMatchRule(new Node(GroupByOp.Pattern,
3954                                           new Node(ProjectOp.Pattern,
3955                                                    new Node(LeafOp.Pattern),
3956                                                    new Node(LeafOp.Pattern)),
3957                                           new Node(LeafOp.Pattern),
3958                                           new Node(LeafOp.Pattern)),
3959                                  ProcessGroupByOverProject);
3960         /// <summary>
3961         /// Converts a GroupBy(Project(X, c1,..ck), agg1, agg2, .. aggm) =>
3962         ///            GroupBy(X, agg1', agg2', .. aggm')
3963         /// where agg1', agg2', .. aggm'  are the "mapped" versions
3964         /// of agg1, agg2, .. aggm, such that the references to c1, ... ck are
3965         /// replaced by their definitions.
3966         ///
3967         /// We only do this if each c1, ..ck is refereneced (in aggregates) at most once or it is a constant.
3968         /// </summary>
3969         /// <param name="context">Rule processing context</param>
3970         /// <param name="projectNode">Current ProjectOp node</param>
3971         /// <param name="newNode">modified subtree</param>
3972         /// <returns>Transformation status</returns>
3973         static bool ProcessGroupByOverProject(RuleProcessingContext context, Node n, out Node newNode)
3974         {
3975             newNode = n;
3976             GroupByOp op = (GroupByOp)n.Op;
3977             Command command = ((TransformationRulesContext)context).Command;
3978             Node projectNode = n.Child0;
3979             Node projectNodeVarDefList = projectNode.Child1;
3980
3981             Node keys = n.Child1;
3982             Node aggregates = n.Child2;
3983
3984             // If there are any keys, we should not remove the inner project
3985             if (keys.Children.Count > 0)
3986             {
3987                 return false;
3988             }
3989
3990             //Get a list of all defining vars
3991             VarVec projectDefinitions = command.GetExtendedNodeInfo(projectNode).LocalDefinitions;
3992
3993             //If any of the defined vars is output, than we need the extra project anyway.
3994             if (op.Outputs.Overlaps(projectDefinitions))
3995             {
3996                 return false;
3997             }
3998
3999             bool createdNewProjectDefinitions = false;
4000
4001             //If there are any constants remove them from the list that needs to be tested,
4002             //These can safely be replaced
4003             for (int i = 0; i < projectNodeVarDefList.Children.Count; i++)
4004             {
4005                 Node varDefNode = projectNodeVarDefList.Children[i];
4006                 if (varDefNode.Child0.Op.OpType == OpType.Constant || varDefNode.Child0.Op.OpType == OpType.InternalConstant || varDefNode.Child0.Op.OpType == OpType.NullSentinel)
4007                 {
4008                     //We shouldn't modify the original project definitions, thus we copy it
4009                     // the first time we encounter a constant
4010                     if (!createdNewProjectDefinitions)
4011                     {
4012                         projectDefinitions = command.CreateVarVec(projectDefinitions);
4013                         createdNewProjectDefinitions = true;
4014                     }
4015                     projectDefinitions.Clear(((VarDefOp)varDefNode.Op).Var);
4016                 }
4017             }
4018
4019             if (VarRefUsageFinder.AnyVarUsedMoreThanOnce(projectDefinitions, aggregates, command))
4020             {
4021                 return false;
4022             }
4023
4024             //If we got here it means that all vars were either constants, or used at most once
4025             // Create a dictionary to be used for remapping the keys and the aggregates
4026             Dictionary<Var, Node> varToDefiningNode = new Dictionary<Var, Node>(projectNodeVarDefList.Children.Count);
4027             for (int j = 0; j < projectNodeVarDefList.Children.Count; j++)
4028             {
4029                 Node varDefNode = projectNodeVarDefList.Children[j];
4030                 Var var = ((VarDefOp)varDefNode.Op).Var;
4031                 varToDefiningNode.Add(var, varDefNode.Child0);
4032             }
4033
4034             newNode.Child2 = VarRefReplacer.Replace(varToDefiningNode, aggregates, command);
4035
4036             newNode.Child0 = projectNode.Child0;
4037             return true;
4038         }
4039
4040         /// <summary>
4041         /// Replaces each occurance of the given vars with their definitions.
4042         /// </summary>
4043         internal class VarRefReplacer : BasicOpVisitorOfNode
4044         {
4045             private Dictionary<Var, Node> m_varReplacementTable;
4046             private Command m_command;
4047
4048             private VarRefReplacer(Dictionary<Var, Node> varReplacementTable, Command command)
4049             {
4050                 this.m_varReplacementTable = varReplacementTable;
4051                 this.m_command = command;
4052             }
4053
4054             /// <summary>
4055             /// "Public" entry point. In the subtree rooted at the given root,
4056             /// replace each occurance of the given vars with their definitions,
4057             /// where each key-value pair in the dictionary is a var-definition pair.
4058             /// </summary>
4059             /// <param name="varReplacementTable"></param>
4060             /// <param name="root"></param>
4061             /// <param name="command"></param>
4062             /// <returns></returns>
4063             internal static Node Replace(Dictionary<Var, Node> varReplacementTable, Node root, Command command)
4064             {
4065                 VarRefReplacer replacer = new VarRefReplacer(varReplacementTable, command);
4066                 return replacer.VisitNode(root);
4067             }
4068
4069             public override Node Visit(VarRefOp op, Node n)
4070             {
4071                 Node replacementNode;
4072                 if (m_varReplacementTable.TryGetValue(op.Var, out replacementNode))
4073                 {
4074                     return replacementNode;
4075                 }
4076                 else
4077                 {
4078                     return n;
4079                 }
4080             }
4081
4082             /// <summary>
4083             /// Recomputes node info post regular processing.
4084             /// </summary>
4085             /// <param name="n"></param>
4086             /// <returns></returns>
4087             protected override Node VisitDefault(Node n)
4088             {
4089                 Node result = base.VisitDefault(n);
4090                 m_command.RecomputeNodeInfo(result);
4091                 return result;
4092             }
4093         }
4094
4095         /// <summary>
4096         /// Used to determine whether any of the given vars occurs more than once
4097         /// in a given subtree.
4098         /// </summary>
4099         internal class VarRefUsageFinder : BasicOpVisitor
4100         {
4101             private bool m_anyUsedMoreThenOnce = false;
4102             private VarVec m_varVec;
4103             private VarVec m_usedVars;
4104
4105             private VarRefUsageFinder(VarVec varVec, Command command)
4106             {
4107                 this.m_varVec = varVec;
4108                 this.m_usedVars = command.CreateVarVec();
4109             }
4110
4111             /// <summary>
4112             /// Public entry point. Returns true if at least one of the given vars occurs more than
4113             /// once in the subree rooted at the given root.
4114             /// </summary>
4115             /// <param name="varVec"></param>
4116             /// <param name="root"></param>
4117             /// <param name="command"></param>
4118             /// <returns></returns>
4119             internal static bool AnyVarUsedMoreThanOnce(VarVec varVec, Node root, Command command)
4120             {
4121                 VarRefUsageFinder usageFinder = new VarRefUsageFinder(varVec, command);
4122                 usageFinder.VisitNode(root);
4123                 return usageFinder.m_anyUsedMoreThenOnce;
4124             }
4125
4126             public override void Visit(VarRefOp op, Node n)
4127             {
4128                 Var referencedVar = op.Var;
4129                 if (m_varVec.IsSet(referencedVar))
4130                 {
4131                     if (m_usedVars.IsSet(referencedVar))
4132                     {
4133                         this.m_anyUsedMoreThenOnce = true;
4134                     }
4135                     else
4136                     {
4137                         m_usedVars.Set(referencedVar);
4138                     }
4139                 }
4140             }
4141
4142             protected override void VisitChildren(Node n)
4143             {
4144                 //small optimization: no need to continue if we have the answer
4145                 if (m_anyUsedMoreThenOnce)
4146                 {
4147                     return;
4148                 }
4149                 base.VisitChildren(n);
4150             }
4151         }
4152         #endregion
4153
4154         #region GroupByOpWithNoAggregates
4155         internal static readonly PatternMatchRule Rule_GroupByOpWithNoAggregates =
4156             new PatternMatchRule(new Node(GroupByOp.Pattern,
4157                                           new Node(LeafOp.Pattern),
4158                                           new Node(LeafOp.Pattern),
4159                                           new Node(VarDefListOp.Pattern)),
4160                                  ProcessGroupByOpWithNoAggregates);
4161         /// <summary>
4162         /// If the GroupByOp has no aggregates:
4163         ///
4164         /// (1) and if it includes all all the keys of the input, than it is unnecessary
4165         /// GroupBy (X, keys) -> Project(X, keys) where keys includes all keys of X.
4166         ///
4167         /// (2) else it can be turned into a Distinct:
4168         /// GroupBy (X, keys) -> Distinct(X, keys)
4169         ///
4170         /// </summary>
4171         /// <param name="context">Rule processing context</param>
4172         /// <param name="n">current subtree</param>
4173         /// <param name="newNode">transformed subtree</param>
4174         /// <returns>transformation status</returns>
4175         static bool ProcessGroupByOpWithNoAggregates(RuleProcessingContext context, Node n, out Node newNode)
4176         {
4177             Command command = context.Command;
4178             GroupByOp op = (GroupByOp)n.Op;
4179
4180             ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
4181             ProjectOp newOp = command.CreateProjectOp(op.Keys);
4182
4183             VarDefListOp varDefListOp = command.CreateVarDefListOp();
4184             Node varDefListNode = command.CreateNode(varDefListOp);
4185
4186             newNode = command.CreateNode(newOp, n.Child0, n.Child1);
4187
4188             //If we know the keys of the input and the list of keys includes them all,
4189             // this is the result, otherwise add distinct
4190             if (nodeInfo.Keys.NoKeys || !op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
4191             {
4192                 newNode = command.CreateNode(command.CreateDistinctOp(command.CreateVarVec(op.Keys)), newNode);
4193             }
4194             return true;
4195         }
4196         #endregion
4197
4198         #region GroupByOpOnAllInputColumnsWithAggregateOperation
4199
4200         internal static readonly SimpleRule Rule_GroupByOpOnAllInputColumnsWithAggregateOperation = new SimpleRule(
4201             OpType.GroupBy, ProcessGroupByOpOnAllInputColumnsWithAggregateOperation);
4202
4203         /// <summary>
4204         /// Converts a GroupBy(X, Y, Z) => OuterApply(X', GroupBy(Filter(X, key(X') == key(X)), Y, Z))
4205         /// if and only if X is a ScanTableOp, and Z is the upper node of an aggregate function and
4206         /// the group by operation uses all the columns of X as the key.
4207         /// Additionally, the top-level physical projection must only expose one variable. If it exposes
4208         /// more than one (more than just the aggregate itself), then this rule must not apply.
4209         /// This is a fix for devdiv bug 851732. Since now we're supporting NewRecordOp nodes as
4210         /// part of the GroupBy aggregate variable computations, we are also respecting the fact that
4211         /// group by (e => e) means that we're grouping by all columns of entity e. This was not a
4212         /// problem when the NewRecordOp node was not being processed since this caused the GroupBy
4213         /// statement to be simplified to a form with no keys and no output columns. The generated SQL
4214         /// is correct, but it is different from what it used to be and may be incompatible if the
4215         /// entity contains fields with datatypes that do not support being grouped by, such as blobs
4216         /// and images.
4217         /// This rule simplifies the tree so that we remain compatible with the way we were generating
4218         /// queries that contain group by (e => e).
4219         /// What this does is enabling the tree to take a shape that further optimization can convert
4220         /// into an expression that groups by the key of the table and calls the aggregate function
4221         /// as expected.
4222         /// </summary>
4223         /// <param name="context"> Rule processing context </param>
4224         /// <param name="n"> Current ProjectOp node </param>
4225         /// <param name="newNode"> modified subtree </param>
4226         /// <returns> Transformation status </returns>
4227         private static bool ProcessGroupByOpOnAllInputColumnsWithAggregateOperation(RuleProcessingContext context, Node n, out Node newNode)
4228         {
4229             newNode = n;
4230
4231             var rootOp = context.Command.Root.Op as PhysicalProjectOp;
4232             if (rootOp == null ||
4233                 rootOp.Outputs.Count > 1)
4234             {
4235                 return false;
4236             }
4237
4238             if (n.Child0.Op.OpType != OpType.ScanTable)
4239             {
4240                 return false;
4241             }
4242
4243             if (n.Child2 == null
4244                 || n.Child2.Child0 == null
4245                 || n.Child2.Child0.Child0 == null
4246                 || n.Child2.Child0.Child0.Op.OpType != OpType.Aggregate)
4247             {
4248                 return false;
4249             }
4250
4251             var groupByOp = (GroupByOp)n.Op;
4252
4253             var sourceTable = ((ScanTableOp)n.Child0.Op).Table;
4254             var allInputColumns = sourceTable.Columns;
4255
4256             // Exit if the group's keys do not contain all the columns defined by Child0
4257             foreach (var column in allInputColumns)
4258             {
4259                 if (!groupByOp.Keys.IsSet(column))
4260                 {
4261                     return false;
4262                 }
4263             }
4264
4265             // All the columns of Child0 are used, so remove them from the outputs and the keys
4266             foreach (var column in allInputColumns)
4267             {
4268                 groupByOp.Outputs.Clear(column);
4269                 groupByOp.Keys.Clear(column);
4270             }
4271
4272             // Build the OuterApply and also set the filter around the GroupBy's scan table.
4273             var command = context.Command;
4274
4275             var scanTableOp = command.CreateScanTableOp(sourceTable.TableMetadata);
4276             var scanTable = command.CreateNode(scanTableOp);
4277             var outerApplyNode = command.CreateNode(command.CreateOuterApplyOp(), scanTable, n);
4278
4279             Var newVar;
4280             var varDefListNode = command.CreateVarDefListNode(command.CreateNode(command.CreateVarRefOp(groupByOp.Outputs.First)), out newVar);
4281
4282             newNode = command.CreateNode(
4283                     command.CreateProjectOp(newVar),
4284                     outerApplyNode,
4285                     varDefListNode);
4286
4287             Node equality = null;
4288             var leftKeys = scanTableOp.Table.Keys.GetEnumerator();
4289             var rightKeys = sourceTable.Keys.GetEnumerator();
4290             for (int i = 0; i < sourceTable.Keys.Count; ++i)
4291             {
4292                 leftKeys.MoveNext();
4293                 rightKeys.MoveNext();
4294                 var comparison = command.CreateNode(
4295                                     command.CreateComparisonOp(OpType.EQ),
4296                                     command.CreateNode(command.CreateVarRefOp(leftKeys.Current)),
4297                                     command.CreateNode(command.CreateVarRefOp(rightKeys.Current)));
4298                 if (equality != null)
4299                 {
4300                     equality = command.CreateNode(
4301                                     command.CreateConditionalOp(OpType.And),
4302                                     equality, comparison);
4303                 }
4304                 else
4305                 {
4306                     equality = comparison;
4307                 }
4308             }
4309
4310             var filter = command.CreateNode(command.CreateFilterOp(),
4311                         n.Child0,
4312                         equality);
4313             n.Child0 = filter;
4314
4315             return true; // subtree modified
4316         }
4317
4318         #endregion
4319
4320         #region All GroupByOp Rules
4321         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
4322                  GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions,
4323                  GroupByOpRules.Rule_GroupByOverProject,
4324                  GroupByOpRules.Rule_GroupByOpWithNoAggregates,
4325                  GroupByOpRules.Rule_GroupByOpOnAllInputColumnsWithAggregateOperation,
4326         };
4327         #endregion
4328     }
4329     #endregion
4330
4331     #region Sorting Rules
4332     /// <summary>
4333     /// Transformation Rules for SortOp
4334     /// </summary>
4335     internal static class SortOpRules
4336     {
4337         #region SortOpOverAtMostOneRow
4338         internal static readonly SimpleRule Rule_SortOpOverAtMostOneRow = new SimpleRule(OpType.Sort, ProcessSortOpOverAtMostOneRow);
4339         /// <summary>
4340         /// If the SortOp's input is guaranteed to produce at most 1 row, remove the node with the SortOp:
4341         ///  Sort(X) => X, if X is guaranteed to produce no more than 1 row
4342         /// </summary>
4343         /// <param name="context">Rule processing context</param>
4344         /// <param name="n">current subtree</param>
4345         /// <param name="newNode">transformed subtree</param>
4346         /// <returns>transformation status</returns>
4347         static bool ProcessSortOpOverAtMostOneRow(RuleProcessingContext context, Node n, out Node newNode)
4348         {
4349             ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
4350
4351             //If the input has at most one row, omit the SortOp
4352             if (nodeInfo.MaxRows == RowCount.Zero || nodeInfo.MaxRows == RowCount.One)
4353             {
4354                 newNode = n.Child0;
4355                 return true;
4356             }
4357
4358             //Otherwise return the node as is
4359             newNode = n;
4360             return false;
4361         }
4362         #endregion
4363
4364         #region All SortOp Rules
4365         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
4366                  SortOpRules.Rule_SortOpOverAtMostOneRow,
4367         };
4368         #endregion
4369     }
4370
4371     /// <summary>
4372     /// Transformation Rules for ConstrainedSortOp
4373     /// </summary>
4374     internal static class ConstrainedSortOpRules
4375     {
4376         #region ConstrainedSortOpOverEmptySet
4377         internal static readonly SimpleRule Rule_ConstrainedSortOpOverEmptySet = new SimpleRule(OpType.ConstrainedSort, ProcessConstrainedSortOpOverEmptySet);
4378         /// <summary>
4379         /// If the ConstrainedSortOp's input is guaranteed to produce no rows, remove the ConstrainedSortOp completly:
4380         ///    CSort(EmptySet) => EmptySet
4381         /// </summary>
4382         /// <param name="context">Rule processing context</param>
4383         /// <param name="n">current subtree</param>
4384         /// <param name="newNode">transformed subtree</param>
4385         /// <returns>transformation status</returns>
4386         static bool ProcessConstrainedSortOpOverEmptySet(RuleProcessingContext context, Node n, out Node newNode)
4387         {
4388             ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
4389
4390             //If the input has no rows, remove the ConstraintSortOp node completly
4391             if (nodeInfo.MaxRows == RowCount.Zero)
4392             {
4393                 newNode = n.Child0;
4394                 return true;
4395             }
4396
4397             newNode = n;
4398             return false;
4399         }
4400         #endregion
4401
4402         #region All ConstrainedSortOp Rules
4403         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
4404                  ConstrainedSortOpRules.Rule_ConstrainedSortOpOverEmptySet,
4405         };
4406         #endregion
4407     }
4408     #endregion
4409
4410     #region DistinctOp Rules
4411     /// <summary>
4412     /// Transformation Rules for DistinctOp
4413     /// </summary>
4414     internal static class DistinctOpRules
4415     {
4416         #region DistinctOpOfKeys
4417         internal static readonly SimpleRule Rule_DistinctOpOfKeys = new SimpleRule(OpType.Distinct, ProcessDistinctOpOfKeys);
4418         /// <summary>
4419         /// If the DistinctOp includes all all the keys of the input, than it is unnecessary.
4420         /// Distinct (X, distinct_keys) -> Project( X, distinct_keys) where distinct_keys includes all keys of X.
4421         /// </summary>
4422         /// <param name="context">Rule processing context</param>
4423         /// <param name="n">current subtree</param>
4424         /// <param name="newNode">transformed subtree</param>
4425         /// <returns>transformation status</returns>
4426         static bool ProcessDistinctOpOfKeys(RuleProcessingContext context, Node n, out Node newNode)
4427         {
4428             Command command = context.Command;
4429
4430             ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
4431
4432             DistinctOp op = (DistinctOp)n.Op;
4433
4434             //If we know the keys of the input and the list of distinct keys includes them all, omit the distinct
4435             if (!nodeInfo.Keys.NoKeys && op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
4436             {
4437                 ProjectOp newOp = command.CreateProjectOp(op.Keys);
4438
4439                 //Create empty vardef list
4440                 VarDefListOp varDefListOp = command.CreateVarDefListOp();
4441                 Node varDefListNode = command.CreateNode(varDefListOp);
4442
4443                 newNode = command.CreateNode(newOp, n.Child0, varDefListNode);
4444                 return true;
4445             }
4446
4447             //Otherwise return the node as is
4448             newNode = n;
4449             return false;
4450         }
4451         #endregion
4452
4453         #region All DistinctOp Rules
4454         internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
4455                  DistinctOpRules.Rule_DistinctOpOfKeys,
4456         };
4457         #endregion
4458     }
4459     #endregion
4460 }