1 //---------------------------------------------------------------------
2 // <copyright file="TransformationRules.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
7 // @backupOwner Microsoft
8 //---------------------------------------------------------------------
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...
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.
29 using System.Globalization;
31 using System.Data.Metadata.Edm;
32 using System.Data.Query.InternalTrees;
34 namespace System.Data.Query.PlanCompiler
36 internal class TransformationRulesContext : RuleProcessingContext
38 #region public methods and properties
41 /// Whether any rule was applied that may have caused modifications such that projection pruning
44 internal bool ProjectionPrunningRequired { get { return this.m_projectionPrunningRequired; } }
47 /// Whether any rule was applied that may have caused modifications such that reapplying
48 /// the nullability rules may be useful
50 internal bool ReapplyNullabilityRules { get { return this.m_reapplyNullabilityRules; } }
53 /// Remap the given subree using the current remapper
55 /// <param name="subTree"></param>
56 internal void RemapSubtree(Node subTree)
58 this.m_remapper.RemapSubtree(subTree);
62 /// Adds a mapping from oldVar to newVar
64 /// <param name="oldVar"></param>
65 /// <param name="newVar"></param>
66 internal void AddVarMapping(Var oldVar, Var newVar)
68 m_remapper.AddMapping(oldVar, newVar);
69 m_remappedVars.Set(oldVar);
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.
80 /// Note: we only support replacements in simple ScalarOp trees. This must be
81 /// validated by the caller.
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)
89 PlanCompiler.Assert(node.Op.IsScalarOp, "Expected a scalarOp: Found " + Dump.AutoString.ToString(node.Op.OpType));
91 // Replace varRefOps by the corresponding expression in the map, if any
92 if (node.Op.OpType == OpType.VarRef)
94 VarRefOp varRefOp = node.Op as VarRefOp;
96 if (varMap.TryGetValue(varRefOp.Var, out newNode))
98 newNode = this.Copy(newNode);
107 // Simply process the result of the children.
108 for (int i = 0; i < node.Children.Count; i++)
110 node.Children[i] = ReMap(node.Children[i], varMap);
113 // We may have changed something deep down
114 this.Command.RecomputeNodeInfo(node);
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
122 /// <param name="node">the subtree to copy</param>
123 /// <returns>the copy of the subtree</returns>
124 internal Node Copy(Node node)
126 if (node.Op.OpType == OpType.VarRef)
128 VarRefOp op = node.Op as VarRefOp;
129 return this.Command.CreateNode(this.Command.CreateVarRefOp(op.Var));
133 return OpCopier.Copy(this.Command, node);
138 /// Checks to see if the current subtree only contains ScalarOps
140 /// <param name="node">current subtree</param>
141 /// <returns>true, if the subtree contains only ScalarOps</returns>
142 internal bool IsScalarOpTree(Node node)
145 return IsScalarOpTree(node, null, ref nodeCount);
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.
154 /// <param name="var"></param>
155 /// <returns></returns>
156 internal bool IsNonNullable(Var var)
158 foreach (Node relOpAncestor in m_relOpAncestors)
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))
168 else if (nodeInfo.LocalDefinitions.IsSet(var))
170 //The var is defined on this ancestor but is not non-nullable,
171 // therefore there is no need to further check other ancestors
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.
189 internal bool CanChangeNullSentinelValue
193 //Is there a sort that includes null sentinels
194 if (this.m_compilerState.HasSortingOnNullSentinels)
199 //Is any of the ancestors Distinct, GroupBy, Intersect or Except
200 if (this.m_relOpAncestors.Any(a => IsOpNotSafeForNullSentinelValueChange(a.Op.OpType)))
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);
211 //If the sentinel comes from the right hand side it is ok.
212 foreach (Node applyAncestor in applyAncestors)
214 if (!this.m_relOpAncestors.Contains(applyAncestor.Child1) && HasOpNotSafeForNullSentinelValueChange(applyAncestor.Child1))
224 /// Is the op not safe for null sentinel value change
226 /// <param name="optype"></param>
227 /// <returns></returns>
228 internal static bool IsOpNotSafeForNullSentinelValueChange(OpType optype)
230 return optype == OpType.Distinct ||
231 optype == OpType.GroupBy ||
232 optype == OpType.Intersect ||
233 optype == OpType.Except;
237 /// Does the given subtree contain a node with an op that
238 /// is not safer for null sentinel value change
240 /// <param name="n"></param>
241 /// <returns></returns>
242 internal static bool HasOpNotSafeForNullSentinelValueChange(Node n)
244 if (IsOpNotSafeForNullSentinelValueChange(n.Op.OpType))
248 foreach (Node child in n.Children)
250 if (HasOpNotSafeForNullSentinelValueChange(child))
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
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)
268 PlanCompiler.Assert(varRefMap != null, "Null varRef map");
271 return IsScalarOpTree(node, varRefMap, ref nodeCount);
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
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.
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)
291 VarDefListOp varDefListOp = (VarDefListOp)varDefListNode.Op;
293 Dictionary<Var, Node> varMap = new Dictionary<Var, Node>();
294 foreach (Node chi in varDefListNode.Children)
296 VarDefOp varDefOp = (VarDefOp)chi.Op;
297 int nonLeafNodeCount = 0;
299 if (!IsScalarOpTree(chi.Child0, null, ref nonLeafNodeCount))
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
310 if ((nonLeafNodeCount > 100) &&
311 (varRefMap != null) &&
312 varRefMap.TryGetValue(varDefOp.Var, out refCount) &&
319 if (varMap.TryGetValue(varDefOp.Var, out n))
321 PlanCompiler.Assert(n == chi.Child0, "reusing varDef for different Node?");
325 varMap.Add(varDefOp.Var, chi.Child0);
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
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)
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);
353 #region Rule Interactions
355 /// Shut off filter pushdown for this subtree
357 /// <param name="n"></param>
358 internal void SuppressFilterPushdown(Node n)
360 m_suppressions[n] = n;
364 /// Is filter pushdown shut off for this subtree?
366 /// <param name="n"></param>
367 /// <returns></returns>
368 internal bool IsFilterPushdownSuppressed(Node n)
370 return m_suppressions.ContainsKey(n);
374 /// Given a list of vars try to get one that is of type Int32
376 /// <param name="varList"></param>
377 /// <param name="int32Var"></param>
378 /// <returns></returns>
379 internal static bool TryGetInt32Var(IEnumerable<Var> varList, out Var int32Var)
381 foreach (Var v in varList)
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)
400 internal TransformationRulesContext(PlanCompiler compilerState)
401 : base(compilerState.Command)
403 m_compilerState = compilerState;
404 m_remapper = new VarRemapper(compilerState.Command);
405 m_suppressions = new Dictionary<Node, Node>();
406 m_remappedVars = compilerState.Command.CreateVarVec();
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>();
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
425 internal readonly System.Text.StringBuilder appliedRules = new System.Text.StringBuilder();
429 #region RuleProcessingContext Overrides
431 /// Callback function to invoke *before* rules are applied.
432 /// Calls the VarRemapper to update any Vars in this node, and recomputes
435 /// <param name="n"></param>
436 internal override void PreProcess(Node n)
438 m_remapper.RemapNode(n);
439 Command.RecomputeNodeInfo(n);
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.
447 /// <param name="subTree"></param>
448 internal override void PreProcessSubTree(Node subTree)
450 if (subTree.Op.IsRelOp)
452 m_relOpAncestors.Push(subTree);
455 if (m_remappedVars.IsEmpty)
460 NodeInfo nodeInfo = this.Command.GetNodeInfo(subTree);
462 //We need to do remapping only if m_remappedVars overlaps with nodeInfo.ExternalReferences
463 foreach (Var v in nodeInfo.ExternalReferences)
465 if (m_remappedVars.IsSet(v))
467 m_remapper.RemapSubtree(subTree);
474 /// If the given node has a RelOp it is popped from the relOp ancestors stack.
476 /// <param name="subtree"></param>
477 internal override void PostProcessSubTree(Node subtree)
479 if (subtree.Op.IsRelOp)
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");
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.
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)
502 appliedRules.Append(rule.MethodName);
503 appliedRules.AppendLine();
505 if (!this.m_projectionPrunningRequired && TransformationRules.RulesRequiringProjectionPruning.Contains(rule))
507 this.m_projectionPrunningRequired = true;
509 if (!this.m_reapplyNullabilityRules && TransformationRules.RulesRequiringNullabilityRulesToBeReapplied.Contains(rule))
511 this.m_reapplyNullabilityRules = true;
513 Command.RecomputeNodeInfo(n);
518 /// Get the hash value for this subtree
520 /// <param name="node"></param>
521 /// <returns></returns>
522 internal override int GetHashCode(Node node)
524 NodeInfo nodeInfo = Command.GetNodeInfo(node);
525 return nodeInfo.HashValue;
529 #region private methods
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
540 /// The non-leaf-node count and the varRefMap are used by GetVarMap to determine
541 /// if expressions can be composed together
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)
549 if (!node.Op.IsScalarOp)
559 if (varRefMap != null && node.Op.OpType == OpType.VarRef)
561 VarRefOp varRefOp = (VarRefOp)node.Op;
563 if (!varRefMap.TryGetValue(varRefOp.Var, out refCount))
571 varRefMap[varRefOp.Var] = refCount;
574 foreach (Node chi in node.Children)
576 if (!IsScalarOpTree(chi, varRefMap, ref nonLeafNodeCount))
587 /// The list of all transformation rules to apply
589 internal static class TransformationRules
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.
595 internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> AllRulesTable = BuildLookupTableForRules(AllRules);
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.
601 internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> ProjectRulesTable = BuildLookupTableForRules(ProjectOpRules.Rules);
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.
608 internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> PostJoinEliminationRulesTable = BuildLookupTableForRules(PostJoinEliminationRules);
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.
615 internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> NullabilityRulesTable = BuildLookupTableForRules(NullabilityRules);
618 /// A look-up table of rules that may cause modifications such that projection pruning may be useful
619 /// after they have been applied.
621 internal static readonly HashSet<InternalTrees.Rule> RulesRequiringProjectionPruning = InitializeRulesRequiringProjectionPruning();
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.
627 internal static readonly HashSet<InternalTrees.Rule> RulesRequiringNullabilityRulesToBeReapplied = InitializeRulesRequiringNullabilityRulesToBeReapplied();
630 #region private state maintenance
631 private static List<InternalTrees.Rule> allRules;
632 private static List<InternalTrees.Rule> AllRules
636 if (allRules == null)
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);
655 private static List<InternalTrees.Rule> postJoinEliminationRules;
656 private static List<InternalTrees.Rule> PostJoinEliminationRules
660 if (postJoinEliminationRules == null)
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);
669 return postJoinEliminationRules;
673 private static List<InternalTrees.Rule> nullabilityRules;
674 private static List<InternalTrees.Rule> NullabilityRules
678 if (nullabilityRules == null)
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);
687 return nullabilityRules;
691 private static ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> BuildLookupTableForRules(IEnumerable<InternalTrees.Rule> rules)
693 ReadOnlyCollection<InternalTrees.Rule> NoRules = new ReadOnlyCollection<InternalTrees.Rule>(new InternalTrees.Rule[0]);
695 List<InternalTrees.Rule>[] lookupTable = new List<InternalTrees.Rule>[(int)OpType.MaxMarker];
697 foreach (InternalTrees.Rule rule in rules)
699 List<InternalTrees.Rule> opRules = lookupTable[(int)rule.RuleOpType];
702 opRules = new List<InternalTrees.Rule>();
703 lookupTable[(int)rule.RuleOpType] = opRules;
708 ReadOnlyCollection<InternalTrees.Rule>[] rulesPerType = new ReadOnlyCollection<InternalTrees.Rule>[lookupTable.Length];
709 for (int i = 0; i < lookupTable.Length; ++i)
711 if (null != lookupTable[i])
713 rulesPerType[i] = new ReadOnlyCollection<InternalTrees.Rule>(lookupTable[i].ToArray());
717 rulesPerType[i] = NoRules;
720 return new ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>>(rulesPerType);
723 private static HashSet<InternalTrees.Rule> InitializeRulesRequiringProjectionPruning()
725 HashSet<InternalTrees.Rule> rulesRequiringProjectionPruning = new HashSet<InternalTrees.Rule>();
727 rulesRequiringProjectionPruning.Add(ApplyOpRules.Rule_OuterApplyOverProject);
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);
735 rulesRequiringProjectionPruning.Add(ProjectOpRules.Rule_ProjectWithNoLocalDefs);
737 rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterOverProject);
738 rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterWithConstantPredicate);
740 rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOverProject);
741 rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions);
743 return rulesRequiringProjectionPruning;
746 private static HashSet<InternalTrees.Rule> InitializeRulesRequiringNullabilityRulesToBeReapplied()
748 HashSet<InternalTrees.Rule> rulesRequiringNullabilityRulesToBeReapplied = new HashSet<InternalTrees.Rule>();
750 rulesRequiringNullabilityRulesToBeReapplied.Add(FilterOpRules.Rule_FilterOverLeftOuterJoin);
752 return rulesRequiringNullabilityRulesToBeReapplied;
759 /// Apply the rules that belong to the specified group to the given query tree.
761 /// <param name="compilerState"></param>
762 /// <param name="rulesGroup"></param>
763 internal static bool Process(PlanCompiler compilerState, TransformationRulesGroup rulesGroup)
765 ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> rulesTable = null;
768 case TransformationRulesGroup.All:
769 rulesTable = AllRulesTable;
771 case TransformationRulesGroup.PostJoinElimination:
772 rulesTable = PostJoinEliminationRulesTable;
774 case TransformationRulesGroup.Project:
775 rulesTable = ProjectRulesTable;
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))
784 bool projectionPrunningRequired2;
785 Process(compilerState, NullabilityRulesTable, out projectionPrunningRequired2);
786 projectionPrunningRequired = projectionPrunningRequired || projectionPrunningRequired2;
788 return projectionPrunningRequired;
792 /// Apply the rules that belong to the specified rules table to the given query tree.
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)
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;
809 /// Available groups of rules, not necessarily mutually exclusive
811 internal enum TransformationRulesGroup
818 #region ScalarOpRules
820 /// Transformation rules for ScalarOps
822 internal static class ScalarOpRules
825 internal static readonly SimpleRule Rule_SimplifyCase = new SimpleRule(OpType.Case, ProcessSimplifyCase);
826 internal static readonly SimpleRule Rule_FlattenCase = new SimpleRule(OpType.Case, ProcessFlattenCase);
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
833 /// assuming that t1 is equivalent to t2 is equivalent to ... to e
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)
841 CaseOp caseOp = (CaseOp)caseOpNode.Op;
842 newNode = caseOpNode;
845 // Can I collapse the entire case-expression into a single expression - yes,
846 // if all the then/else clauses are the same expression
848 if (ProcessSimplifyCase_Collapse(caseOp, caseOpNode, out newNode))
854 // Can I remove any unnecessary when-then pairs ?
856 if (ProcessSimplifyCase_EliminateWhenClauses(context, caseOp, caseOpNode, out newNode))
861 // Nothing else I can think of
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
871 /// if t1 is equivalent to t2 is equivalent to ... to e
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)
879 newNode = caseOpNode;
880 Node firstThenNode = caseOpNode.Child1;
881 Node elseNode = caseOpNode.Children[caseOpNode.Children.Count - 1];
882 if (!firstThenNode.IsEquivalent(elseNode))
886 for (int i = 3; i < caseOpNode.Children.Count - 1; i += 2)
888 if (!caseOpNode.Children[i].IsEquivalent(firstThenNode))
894 // All nodes are equivalent - simply return the first then node
895 newNode = firstThenNode;
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
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)
916 List<Node> newNodeArgs = null;
917 newNode = caseOpNode;
919 for (int i = 0; i < caseOpNode.Children.Count; )
921 // Special handling for the else clause
922 if (i == caseOpNode.Children.Count - 1)
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)
935 if (newNodeArgs != null)
937 newNodeArgs.Add(caseOpNode.Children[i]);
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)
950 // Check to see if the when clause is a ConstantPredicate
951 if (caseOpNode.Children[i].Op.OpType != OpType.ConstantPredicate)
953 if (newNodeArgs != null)
955 newNodeArgs.Add(caseOpNode.Children[i]);
956 newNodeArgs.Add(caseOpNode.Children[i + 1]);
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)
967 newNodeArgs = new List<Node>();
968 for (int j = 0; j < i; j++)
970 newNodeArgs.Add(caseOpNode.Children[j]);
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)
979 newNodeArgs.Add(caseOpNode.Children[i + 1]);
984 // Otherwise, we simply skip the when-then pair
985 PlanCompiler.Assert(constPred.IsFalse, "constant predicate must be either true or false");
991 // Did we see any changes? Simply return
992 if (newNodeArgs == null)
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)
1002 newNode = newNodeArgs[0];
1006 newNode = context.Command.CreateNode(caseOp, newNodeArgs);
1013 /// If the else clause of the CaseOp is another CaseOp, when two can be collapsed into one.
1018 /// WHEN W2 THEN T2 ...
1020 /// WHEN WN1 THEN TN1,
\85
1023 /// Is transformed into
1027 /// WHEN W2 THEN T2 ...
1028 /// WHEN WN1 THEN TN1 ...
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)
1037 newNode = caseOpNode;
1038 Node elseChild = caseOpNode.Children[caseOpNode.Children.Count - 1];
1039 if (elseChild.Op.OpType != OpType.Case)
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.
1051 caseOpNode.Children.RemoveAt(caseOpNode.Children.Count - 1);
1052 caseOpNode.Children.AddRange(elseChild.Children);
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);
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
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)
1076 PlanCompiler.Assert(node.Op.OpType == OpType.EQ || node.Op.OpType == OpType.NE, "unexpected comparison op type?");
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)
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);
1091 #region LikeOp Rules
1092 private static bool? MatchesPattern(string str, string pattern)
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
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))
1111 for (i = 0; i < str.Length && i < pattern.Length - 1; i++)
1113 if (pattern[i] != str[i])
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)
1132 InternalConstantOp patternOp = (InternalConstantOp)n.Child1.Op;
1133 InternalConstantOp strOp = (InternalConstantOp)n.Child0.Op;
1135 string str = (string)strOp.Value;
1136 string pattern = (string)patternOp.Value;
1138 bool? match = MatchesPattern((string)strOp.Value, (string)patternOp.Value);
1144 ConstantPredicateOp constOp = context.Command.CreateConstantPredicateOp((bool)match);
1145 newNode = context.Command.CreateNode(constOp);
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);
1178 /// AND(x, true) => x;
1179 /// AND(true, x) => x
1180 /// AND(x, false) => false
1181 /// AND(false, x) => false
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,
1194 PlanCompiler.Assert(constantPredicateNode != null, "null constantPredicateOp?");
1195 ConstantPredicateOp pred = (ConstantPredicateOp)constantPredicateNode.Op;
1197 switch (node.Op.OpType)
1200 newNode = pred.IsTrue ? otherNode : constantPredicateNode;
1203 newNode = pred.IsTrue ? constantPredicateNode : otherNode;
1206 PlanCompiler.Assert(otherNode == null, "Not Op with more than 1 child. Gasp!");
1207 newNode = context.Command.CreateNode(context.Command.CreateConstantPredicateOp(!pred.Value));
1210 PlanCompiler.Assert(false, "Unexpected OpType - " + node.Op.OpType);
1217 static bool ProcessAndOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
1219 return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
1221 static bool ProcessAndOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
1223 return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
1225 static bool ProcessOrOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
1227 return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
1229 static bool ProcessOrOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
1231 return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
1233 static bool ProcessNotOverConstantPredicate(RuleProcessingContext context, Node node, out Node newNode)
1235 return ProcessLogOpOverConstant(context, node, node.Child0, null, out newNode);
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);
1250 /// IsNull(constant)
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)
1260 newNode = context.Command.CreateNode(context.Command.CreateFalseOp());
1264 internal static readonly PatternMatchRule Rule_IsNullOverNull =
1265 new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
1266 new Node(NullOp.Pattern)),
1267 ProcessIsNullOverNull);
1269 /// Convert an IsNull(null) to just the 'true' predicate
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)
1277 newNode = context.Command.CreateNode(context.Command.CreateTrueOp());
1282 #region CastOp(NullOp) Rule
1283 internal static readonly PatternMatchRule Rule_NullCast = new PatternMatchRule(
1284 new Node(CastOp.Pattern,
1285 new Node(NullOp.Pattern)),
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]
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)
1298 newNode = context.Command.CreateNode(context.Command.CreateNullOp(castNullOp.Op.Type));
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);
1310 /// IsNull(VarRef(v))
1314 /// if v is guaranteed to be non nullable.
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)
1322 Command command = context.Command;
1323 TransformationRulesContext trc = (TransformationRulesContext)context;
1325 Var v = ((VarRefOp)isNullNode.Child0.Op).Var;
1327 if (trc.IsNonNullable(v))
1330 newNode = command.CreateNode(context.Command.CreateFalseOp());
1335 newNode = isNullNode;
1341 #region All ScalarOp Rules
1342 internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
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,
1356 Rule_IsNullOverVarRef,
1362 #region Filter Rules
1364 /// Transformation rules for FilterOps
1366 internal static class FilterOpRules
1370 /// Split up a predicate into 2 parts - the pushdown and the non-pushdown predicate.
1372 /// If the filter node has no external references *and* the "columns" parameter is null,
1373 /// then the entire predicate can be pushed down
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.
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
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)
1392 Node pushdownPredicateNode = filterNode.Child1;
1393 nonPushdownPredicateNode = null;
1394 ExtendedNodeInfo filterNodeInfo = command.GetExtendedNodeInfo(filterNode);
1395 if (columns == null && filterNodeInfo.ExternalReferences.IsEmpty)
1397 return pushdownPredicateNode;
1400 if (columns == null)
1402 ExtendedNodeInfo inputNodeInfo = command.GetExtendedNodeInfo(filterNode.Child0);
1403 columns = inputNodeInfo.Definitions;
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;
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);
1425 /// Convert Filter(Filter(X, p1), p2) => Filter(X, (p1 and p2))
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)
1433 Node newAndNode = context.Command.CreateNode(
1434 context.Command.CreateConditionalOp(OpType.And),
1435 filterNode.Child0.Child1, filterNode.Child1);
1437 newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), filterNode.Child0.Child0, newAndNode);
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);
1451 /// Convert Filter(Project(X, ...), p) => Project(Filter(X, p'), ...)
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)
1459 newNode = filterNode;
1460 Node predicateNode = filterNode.Child1;
1463 // If the filter is a constant predicate, then don't push the filter below the
1466 if (predicateNode.Op.OpType == OpType.ConstantPredicate)
1468 // There's a different rule to process this case. Simply return
1472 TransformationRulesContext trc = (TransformationRulesContext)context;
1474 // check to see that this is a simple predicate
1476 Dictionary<Var, int> varRefMap = new Dictionary<Var, int>();
1477 if (!trc.IsScalarOpTree(predicateNode, varRefMap))
1482 // check to see if all expressions in the project can be inlined
1484 Node projectNode = filterNode.Child0;
1485 Dictionary<Var, Node> varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
1492 // Try to remap the predicate in terms of the definitions of the Vars
1494 Node remappedPredicateNode = trc.ReMap(predicateNode, varMap);
1497 // Now push the filter below the project
1499 Node newFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), projectNode.Child0, remappedPredicateNode);
1500 Node newProjectNode = trc.Command.CreateNode(projectNode.Op, newFilterNode, projectNode.Child1);
1502 newNode = newProjectNode;
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);
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
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)
1541 newNode = filterNode;
1542 TransformationRulesContext trc = (TransformationRulesContext)context;
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
1548 Node nonPushdownPredicate;
1549 Node pushdownPredicate = GetPushdownPredicate(trc.Command, filterNode, null, out nonPushdownPredicate);
1550 if (pushdownPredicate == null)
1554 // Handle only simple predicates
1555 if (!trc.IsScalarOpTree(pushdownPredicate))
1561 // Now push the predicate (the part that can be pushed down) into each of the
1562 // branches (as appropriate)
1564 Node setOpNode = filterNode.Child0;
1565 SetOp setOp = (SetOp)setOpNode.Op;
1566 List<Node> newSetOpChildren = new List<Node>();
1568 foreach (VarMap varMap in setOp.VarMap)
1570 // For exceptOp, the filter should only be pushed below the zeroth child
1571 if (setOp.OpType == OpType.Except && branchId == 1)
1573 newSetOpChildren.Add(setOpNode.Child1);
1577 Dictionary<Var, Node> remapMap = new Dictionary<Var, Node>();
1578 foreach (KeyValuePair<Var, Var> kv in varMap)
1580 Node varRefNode = trc.Command.CreateNode(trc.Command.CreateVarRefOp(kv.Value));
1581 remapMap.Add(kv.Key, varRefNode);
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
1589 Node predicateNode = pushdownPredicate;
1590 if (branchId == 0 && filterNode.Op.OpType != OpType.Except)
1592 predicateNode = trc.Copy(predicateNode);
1594 Node newPredicateNode = trc.ReMap(predicateNode, remapMap);
1595 trc.Command.RecomputeNodeInfo(newPredicateNode);
1597 // create a new filter node below the setOp child
1598 Node newFilterNode = trc.Command.CreateNode(
1599 trc.Command.CreateFilterOp(),
1600 setOpNode.Children[branchId],
1602 newSetOpChildren.Add(newFilterNode);
1606 Node newSetOpNode = trc.Command.CreateNode(setOpNode.Op, newSetOpChildren);
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
1613 if (nonPushdownPredicate != null)
1615 newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newSetOpNode, nonPushdownPredicate);
1619 newNode = newSetOpNode;
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);
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
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)
1643 newNode = filterNode;
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
1648 Node nonPushdownPredicate;
1649 Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, null, out nonPushdownPredicate);
1650 if (pushdownPredicate == null)
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
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);
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
1667 if (nonPushdownPredicate != null)
1669 newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), newDistinctNode, nonPushdownPredicate);
1673 newNode = newDistinctNode;
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);
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
1694 /// "p1'" is the mapped version of "p1",
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)
1702 newNode = filterNode;
1703 Node groupByNode = filterNode.Child0;
1704 GroupByOp groupByOp = (GroupByOp)groupByNode.Op;
1705 TransformationRulesContext trc = (TransformationRulesContext)context;
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))
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
1720 Node nonPushdownPredicate;
1721 Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, groupByOp.Keys, out nonPushdownPredicate);
1722 if (pushdownPredicate == null)
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
1732 Dictionary<Var, Node> varMap = trc.GetVarMap(groupByNode.Child1, varRefMap);
1735 return false; // complex expressions
1737 Node remappedPushdownPredicate = trc.ReMap(pushdownPredicate, varMap);
1740 // Push the filter below the groupBy now
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);
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
1750 if (nonPushdownPredicate == null)
1752 newNode = newGroupByNode;
1756 newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newGroupByNode, nonPushdownPredicate);
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);
1787 /// Transform Filter()
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)
1795 newNode = filterNode;
1796 TransformationRulesContext trc = (TransformationRulesContext)context;
1799 // Have we shut off filter pushdown for this node? Return
1801 if (trc.IsFilterPushdownSuppressed(filterNode))
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;
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
1819 ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(rightInputNode);
1820 Predicate predicate = new Predicate(command, filterNode.Child1);
1821 if (joinOp.OpType == OpType.LeftOuterJoin)
1823 if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
1825 joinOp = command.CreateInnerJoinOp();
1826 needsTransformation = true;
1829 ExtendedNodeInfo leftTableInfo = command.GetExtendedNodeInfo(leftInputNode);
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.
1839 Node leftSingleTablePredicateNode = null;
1840 if (leftInputNode.Op.OpType != OpType.ScanTable)
1842 Predicate leftSingleTablePredicates = predicate.GetSingleTablePredicates(leftTableInfo.Definitions, out predicate);
1843 leftSingleTablePredicateNode = leftSingleTablePredicates.BuildAndTree();
1846 Node rightSingleTablePredicateNode = null;
1847 if ((rightInputNode.Op.OpType != OpType.ScanTable) &&
1848 (joinOp.OpType != OpType.LeftOuterJoin))
1850 Predicate rightSingleTablePredicates = predicate.GetSingleTablePredicates(rightTableNodeInfo.Definitions, out predicate);
1851 rightSingleTablePredicateNode = rightSingleTablePredicates.BuildAndTree();
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
1859 Node newJoinPredicateNode = null;
1860 if (joinOp.OpType == OpType.CrossJoin || joinOp.OpType == OpType.InnerJoin)
1862 Predicate joinPredicate = predicate.GetJoinPredicates(leftTableInfo.Definitions, rightTableNodeInfo.Definitions, out predicate);
1863 newJoinPredicateNode = joinPredicate.BuildAndTree();
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.
1871 if (leftSingleTablePredicateNode != null)
1873 leftInputNode = command.CreateNode(command.CreateFilterOp(), leftInputNode, leftSingleTablePredicateNode);
1874 needsTransformation = true;
1876 if (rightSingleTablePredicateNode != null)
1878 rightInputNode = command.CreateNode(command.CreateFilterOp(), rightInputNode, rightSingleTablePredicateNode);
1879 needsTransformation = true;
1882 // Identify the new join predicate
1883 if (newJoinPredicateNode != null)
1885 needsTransformation = true;
1886 if (joinOp.OpType == OpType.CrossJoin)
1888 joinOp = command.CreateInnerJoinOp();
1892 PlanCompiler.Assert(joinOp.OpType == OpType.InnerJoin, "unexpected non-InnerJoin?");
1893 newJoinPredicateNode = PlanCompilerUtil.CombinePredicates(joinNode.Child2, newJoinPredicateNode, command);
1898 newJoinPredicateNode = (joinOp.OpType == OpType.CrossJoin) ? null : joinNode.Child2;
1902 // If nothing has changed, then just return the current node. Otherwise,
1903 // we will loop forever
1905 if (!needsTransformation)
1912 // Finally build up a new join node
1914 if (joinOp.OpType == OpType.CrossJoin)
1916 newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode);
1920 newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode, newJoinPredicateNode);
1924 // Build up a new filterNode above this join node. But only if we have a filter left
1926 Node newFilterPredicateNode = predicate.BuildAndTree();
1927 if (newFilterPredicateNode == null)
1929 newNode = newJoinNode;
1933 newNode = command.CreateNode(command.CreateFilterOp(), newJoinNode, newFilterPredicateNode);
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);
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
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)
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;
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,
1969 ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(applyRightInputNode);
1970 Predicate predicate = new Predicate(command, filterNode.Child1);
1971 if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
1973 Node newApplyNode = command.CreateNode(command.CreateCrossApplyOp(), applyNode.Child0, applyRightInputNode);
1974 Node newFilterNode = command.CreateNode(command.CreateFilterOp(), newApplyNode, filterNode.Child1);
1975 newNode = newFilterNode;
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);
1992 /// Filter(X, true) => X
1993 /// Filter(X, false) => Project(Filter(SingleRowTableOp, ...), false)
1994 /// where ... represent variables that are equivalent to the table columns
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)
2003 ConstantPredicateOp predOp = (ConstantPredicateOp)n.Child1.Op;
2005 // If we're dealing with a "true" predicate, then simply return the RelOp
2006 // input to the filter
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
2018 // If the input is already a singlerowtableOp, then there's nothing
2021 if (n.Child0.Op.OpType == OpType.SingleRowTable ||
2022 (n.Child0.Op.OpType == OpType.Project &&
2023 n.Child0.Child0.Op.OpType == OpType.SingleRowTable))
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)
2034 NullOp nullConst = trc.Command.CreateNullOp(v.Type);
2035 Node constNode = trc.Command.CreateNode(nullConst);
2037 Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
2038 trc.AddVarMapping(v, computedVar);
2039 newVars.Set(computedVar);
2040 varDefNodeList.Add(varDefNode);
2042 // If no vars have been selected out, add a dummy var
2043 if (newVars.IsEmpty)
2045 NullOp nullConst = trc.Command.CreateNullOp(trc.Command.BooleanType);
2046 Node constNode = trc.Command.CreateNode(nullConst);
2048 Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
2049 newVars.Set(computedVar);
2050 varDefNodeList.Add(varDefNode);
2053 Node singleRowTableNode = trc.Command.CreateNode(trc.Command.CreateSingleRowTableOp());
2054 n.Child0 = singleRowTableNode;
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);
2060 projectNode.Child0 = n;
2061 newNode = projectNode;
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,
2087 #region Project Rules
2089 /// Transformation rules for ProjectOp
2091 internal static class ProjectOpRules
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);
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.
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)
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;
2119 // If any of the defining expressions is not a scalar op tree, then simply
2121 Dictionary<Var, int> varRefMap = new Dictionary<Var, int>();
2122 foreach (Node varDefNode in varDefListNode.Children)
2124 if (!trc.IsScalarOpTree(varDefNode.Child0, varRefMap))
2130 Dictionary<Var, Node> varMap = trc.GetVarMap(subProjectNode.Child1, varRefMap);
2136 // create a new varDefList node...
2137 Node newVarDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp());
2139 // Remap any local definitions, I have
2140 foreach (Node varDefNode in varDefListNode.Children)
2142 // update the defining expression
2143 varDefNode.Child0 = trc.ReMap(varDefNode.Child0, varMap);
2144 trc.Command.RecomputeNodeInfo(varDefNode);
2145 newVarDefListNode.Children.Add(varDefNode);
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)
2152 VarDefOp varDefOp = (VarDefOp)chi.Op;
2153 if (projectNodeInfo.Definitions.IsSet(varDefOp.Var))
2155 newVarDefListNode.Children.Add(chi);
2160 // now that we have remapped all our computed vars, simply bypass the subproject
2163 projectNode.Child0 = subProjectNode.Child0;
2164 projectNode.Child1 = newVarDefListNode;
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);
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
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)
2189 NodeInfo nodeInfo = context.Command.GetNodeInfo(n);
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)
2205 #region ProjectOpWithSimpleVarRedefinitions
2206 internal static readonly SimpleRule Rule_ProjectOpWithSimpleVarRedefinitions = new SimpleRule(OpType.Project, ProcessProjectWithSimpleVarRedefinitions);
2208 /// If the ProjectOp defines some computedVars, but those computedVars are simply
2209 /// redefinitions of other Vars, then eliminate the computedVars.
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
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)
2223 ProjectOp projectOp = (ProjectOp)n.Op;
2225 if (n.Child1.Children.Count == 0)
2230 TransformationRulesContext trc = (TransformationRulesContext)context;
2231 Command command = trc.Command;
2233 ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
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)
2242 Node definingExprNode = varDefNode.Child0;
2243 if (definingExprNode.Op.OpType == OpType.VarRef)
2245 VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
2246 if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
2248 // this is a Var that we should remove
2249 canEliminateSomeVars = true;
2255 // Did we have any redefinitions
2256 if (!canEliminateSomeVars)
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
2266 // Lets now build up a new VarDefListNode
2267 List<Node> newVarDefNodes = new List<Node>();
2268 foreach (Node varDefNode in n.Child1.Children)
2270 VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
2271 VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
2272 if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
2274 projectOp.Outputs.Clear(varDefOp.Var);
2275 projectOp.Outputs.Set(varRefOp.Var);
2276 trc.AddVarMapping(varDefOp.Var, varRefOp.Var);
2280 newVarDefNodes.Add(varDefNode);
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.
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
2298 #region ProjectOpWithNullSentinel
2299 internal static readonly SimpleRule Rule_ProjectOpWithNullSentinel = new SimpleRule(OpType.Project, ProcessProjectOpWithNullSentinel);
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,
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:
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
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.
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.
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)
2329 ProjectOp projectOp = (ProjectOp)n.Op;
2330 Node varDefListNode = n.Child1;
2332 if (varDefListNode.Children.Where(c => c.Child0.Op.OpType == OpType.NullSentinel).Count() == 0)
2337 TransformationRulesContext trc = (TransformationRulesContext)context;
2338 Command command = trc.Command;
2339 ExtendedNodeInfo relOpInputNodeInfo = command.GetExtendedNodeInfo(n.Child0);
2341 bool reusingConstantFromSameProjectAsSentinel = false;
2343 bool canChangeNullSentinelValue = trc.CanChangeNullSentinelValue;
2345 if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(relOpInputNodeInfo.NonNullableDefinitions, out inputSentinel))
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))
2350 inputSentinel = n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.NullSentinel).Select(child => ((VarDefOp)(child.Op)).Var).FirstOrDefault();
2351 if (inputSentinel == null)
2358 bool modified = false;
2360 for (int i = n.Child1.Children.Count-1; i >= 0; i--)
2362 Node varDefNode = n.Child1.Children[i];
2363 Node definingExprNode = varDefNode.Child0;
2364 if (definingExprNode.Op.OpType == OpType.NullSentinel)
2366 if (!reusingConstantFromSameProjectAsSentinel)
2368 VarRefOp varRefOp = command.CreateVarRefOp(inputSentinel);
2369 varDefNode.Child0 = command.CreateNode(varRefOp);
2370 command.RecomputeNodeInfo(varDefNode);
2373 else if (!inputSentinel.Equals(((VarDefOp)varDefNode.Op).Var))
2375 projectOp.Outputs.Clear(((VarDefOp)varDefNode.Op).Var);
2376 n.Child1.Children.RemoveAt(i);
2377 trc.AddVarMapping(((VarDefOp)varDefNode.Op).Var, inputSentinel);
2385 command.RecomputeNodeInfo(n.Child1);
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,
2405 /// Transformation rules for ApplyOps - CrossApply, OuterApply
2407 internal static class ApplyOpRules
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);
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
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)
2435 newNode = applyNode;
2436 Node filterNode = applyNode.Child1;
2437 Command command = context.Command;
2439 NodeInfo filterInputNodeInfo = command.GetNodeInfo(filterNode.Child0);
2440 ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
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
2447 if (filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
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
2458 JoinBaseOp joinOp = null;
2459 if (applyNode.Op.OpType == OpType.CrossApply)
2461 joinOp = command.CreateInnerJoinOp();
2465 joinOp = command.CreateLeftOuterJoinOp();
2468 newNode = command.CreateNode(joinOp, applyNode.Child0, filterNode.Child0, filterNode.Child1);
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);
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);
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
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
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)
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;
2520 ExtendedNodeInfo filterInputNodeInfo = command.GetExtendedNodeInfo(filterInputNode);
2521 ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
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
2528 if (projectOp.Outputs.Overlaps(applyLeftChildNodeInfo.Definitions) || filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
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
2539 bool capWithProject = false;
2540 Node joinNodeRightInput = null;
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
2550 TransformationRulesContext trc = (TransformationRulesContext)context;
2552 bool sentinelIsInt32;
2554 if (TransformationRulesContext.TryGetInt32Var(filterInputNodeInfo.NonNullableDefinitions, out sentinelVar))
2556 sentinelIsInt32 = true;
2560 sentinelVar = filterInputNodeInfo.NonNullableDefinitions.First;
2561 sentinelIsInt32 = false;
2564 if (sentinelVar != null)
2566 capWithProject = true;
2567 Node varDefNode = projectNode.Child1.Child0;
2568 if (varDefNode.Child0.Op.OpType == OpType.NullSentinel && sentinelIsInt32 && trc.CanChangeNullSentinelValue)
2570 varDefNode.Child0 = context.Command.CreateNode(context.Command.CreateVarRefOp(sentinelVar));
2574 varDefNode.Child0 = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
2576 command.RecomputeNodeInfo(varDefNode);
2577 command.RecomputeNodeInfo(projectNode.Child1);
2578 joinNodeRightInput = filterInputNode;
2582 // We need to keep the projectNode - unfortunately
2583 joinNodeRightInput = projectNode;
2585 // Make sure that every Var that is needed for the filter predicate
2586 // is captured in the projectOp outputs list
2588 NodeInfo filterPredicateNodeInfo = command.GetNodeInfo(filterNode.Child1);
2589 foreach (Var v in filterPredicateNodeInfo.ExternalReferences)
2591 if (filterInputNodeInfo.Definitions.IsSet(v))
2593 projectOp.Outputs.Set(v);
2596 projectNode.Child0 = filterInputNode;
2599 context.Command.RecomputeNodeInfo(projectNode);
2602 // We can now simply convert the apply into an inner/leftouter join with the
2603 // filter predicate acting as the join condition
2605 Node joinNode = command.CreateNode(command.CreateLeftOuterJoinOp(), applyNode.Child0, joinNodeRightInput, filterNode.Child1);
2608 ExtendedNodeInfo joinNodeInfo = command.GetExtendedNodeInfo(joinNode);
2609 projectNode.Child0 = joinNode;
2610 projectOp.Outputs.Or(joinNodeInfo.Definitions);
2611 newNode = projectNode;
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);
2631 /// Converts a CrossApply(X, Project(Y, ...)) => Project(CrossApply(X, Y), ...)
2632 /// where the projectVars are simply pulled up
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)
2640 newNode = applyNode;
2641 Node projectNode = applyNode.Child1;
2642 ProjectOp projectOp = (ProjectOp)projectNode.Op as ProjectOp;
2643 Command command = context.Command;
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);
2652 // pull up the project over the apply node
2653 applyNode.Child1 = projectNode.Child0;
2654 context.Command.RecomputeNodeInfo(applyNode);
2655 projectNode.Child0 = applyNode;
2657 newNode = projectNode;
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);
2670 /// OuterApply(X, Project(Y, ...))
2672 /// Project(OuterApply(X, Project(Y, ...)), ...) or
2673 /// Project(OuterApply(X, Y), ...)
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
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.
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.
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)
2705 newNode = applyNode;
2706 Node projectNode = applyNode.Child1;
2707 Node varDefListNode = projectNode.Child1;
2709 TransformationRulesContext trc = (TransformationRulesContext)context;
2710 ExtendedNodeInfo inputNodeInfo = context.Command.GetExtendedNodeInfo(projectNode.Child0);
2711 Var sentinelVar = inputNodeInfo.NonNullableDefinitions.First;
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
2718 if (sentinelVar == null &&
2719 varDefListNode.Children.Count == 1 &&
2720 (varDefListNode.Child0.Child0.Op.OpType == OpType.InternalConstant || varDefListNode.Child0.Child0.Op.OpType == OpType.NullSentinel))
2725 Command command = context.Command;
2726 Node dummyProjectNode = null;
2727 InternalConstantOp nullSentinelDefinitionOp = null;
2729 // get node information for the project's child
2730 ExtendedNodeInfo projectInputNodeInfo = command.GetExtendedNodeInfo(projectNode.Child0);
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
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)
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))
2747 // do we need to build a dummy project node
2748 if (sentinelVar == null)
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);
2758 Node currentDefinition;
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))
2767 currentDefinition = command.CreateNode(command.CreateVarRefOp(sentinelVar));
2771 currentDefinition = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
2773 varDefNode.Child0 = currentDefinition;
2774 command.RecomputeNodeInfo(varDefNode);
2775 anyVarDefChagned = true;
2779 // Recompute node info if needed
2780 if (anyVarDefChagned)
2782 command.RecomputeNodeInfo(varDefListNode);
2786 // If we've created a dummy project node, make that the new child of the applyOp
2788 applyNode.Child1 = dummyProjectNode != null ? dummyProjectNode : projectNode.Child0;
2789 command.RecomputeNodeInfo(applyNode);
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
2795 projectNode.Child0 = applyNode;
2796 ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
2797 ProjectOp projectOp = (ProjectOp)projectNode.Op;
2798 projectOp.Outputs.Or(applyLeftChildNodeInfo.Definitions);
2800 newNode = projectNode;
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);
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
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)
2828 newNode = applyNode;
2829 Node applyLeftChild = applyNode.Child0;
2830 Node applyRightChild = applyNode.Child1;
2831 ApplyBaseOp applyOp = (ApplyBaseOp)applyNode.Op;
2832 Command command = context.Command;
2834 ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyRightChild);
2835 ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyLeftChild);
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
2841 bool convertedToCrossApply = false;
2842 if (applyOp.OpType == OpType.OuterApply &&
2843 applyRightChildNodeInfo.MinRows >= RowCount.One)
2845 applyOp = command.CreateCrossApplyOp();
2846 convertedToCrossApply = true;
2850 // Does the right child reference any of the definitions of the left child? If it
2851 // does, then simply return from this function
2853 if (applyRightChildNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
2855 if (convertedToCrossApply)
2857 newNode = command.CreateNode(applyOp, applyLeftChild, applyRightChild);
2867 // So, we now know that the right child does not reference any definitions
2869 // So, we simply convert the apply into an appropriate join Op
2871 if (applyOp.OpType == OpType.CrossApply)
2874 // Convert "x CrossApply y" into "x CrossJoin y"
2876 newNode = command.CreateNode(command.CreateCrossJoinOp(),
2877 applyLeftChild, applyRightChild);
2882 // Convert "x OA y" into "x LOJ y on (true)"
2884 LeftOuterJoinOp joinOp = command.CreateLeftOuterJoinOp();
2885 ConstantPredicateOp trueOp = command.CreateTrueOp();
2886 Node trueNode = command.CreateNode(trueOp);
2887 newNode = command.CreateNode(joinOp, applyLeftChild, applyRightChild, trueNode);
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);
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
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)
2918 Command command = context.Command;
2919 ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child1);
2920 OpType applyKind = applyNode.Op.OpType;
2922 if (!CanRewriteApply(applyNode.Child1, applyRightChildNodeInfo, applyKind))
2924 newNode = applyNode;
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);
2931 Var oldVar = applyRightChildNodeInfo.Definitions.First;
2933 // Project all the outputs from the left child
2934 VarVec projectOpOutputs = command.CreateVarVec(applyLeftChildNodeInfo.Definitions);
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.
2941 TransformationRulesContext trc = (TransformationRulesContext)context;
2942 trc.RemapSubtree(applyNode.Child1);
2943 VarDefinitionRemapper.RemapSubtree(applyNode.Child1, command, oldVar);
2945 Node elementNode = command.CreateNode(command.CreateElementOp(oldVar.Type), applyNode.Child1);
2948 Node varDefListNode = command.CreateVarDefListNode(elementNode, out newVar);
2949 projectOpOutputs.Set(newVar);
2951 newNode = command.CreateNode(
2952 command.CreateProjectOp(projectOpOutputs),
2956 // Add the var mapping from oldVar to newVar
2957 trc.AddVarMapping(oldVar, newVar);
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
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)
2974 //Check whether it produces only one definition
2975 if (applyRightChildNodeInfo.Definitions.Count != 1)
2980 //Check whether it produces at most one row
2981 if (applyRightChildNodeInfo.MaxRows != RowCount.One)
2986 //For cross apply it must also return exactly one row
2987 if (applyKind == OpType.CrossApply && (applyRightChildNodeInfo.MinRows != RowCount.One))
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)
3005 /// A visitor that calculates the number of output columns for a subree
3006 /// with a given root
3008 internal class OutputCountVisitor : BasicOpVisitorOfT<int>
3010 #region Constructors
3011 internal OutputCountVisitor()
3016 #region Public Methods
3018 /// Calculates the number of output columns for the subree
3019 /// rooted at the given node
3021 /// <param name="node"></param>
3022 /// <returns></returns>
3023 internal static int CountOutputs(Node node)
3025 OutputCountVisitor visitor = new OutputCountVisitor();
3026 return visitor.VisitNode(node);
3031 #region Visitor Methods
3035 /// Visitor for children. Simply visit all children,
3036 /// and sum the number of their outputs.
3038 /// <param name="n">Current node</param>
3039 /// <returns></returns>
3040 internal new int VisitChildren(Node n)
3043 foreach (Node child in n.Children)
3045 result += VisitNode(child);
3051 /// A default processor for any node.
3052 /// Returns the sum of the children outputs
3054 /// <param name="n"></param>
3055 /// <returns>/returns>
3056 protected override int VisitDefault(Node n)
3058 return VisitChildren(n);
3063 #region RelOp Visitors
3065 #region SetOp Visitors
3068 /// The number of outputs is same as for any of the inputs
3070 /// <param name="op"></param>
3071 /// <param name="n"></param>
3072 /// <returns></returns>
3073 protected override int VisitSetOp(SetOp op, Node n)
3075 return op.Outputs.Count;
3083 /// <param name="op"></param>
3084 /// <param name="n"></param>
3085 /// <returns></returns>
3086 public override int Visit(DistinctOp op, Node n)
3088 return op.Keys.Count;
3094 /// <param name="op"></param>
3095 /// <param name="n"></param>
3096 /// <returns></returns>
3097 public override int Visit(FilterOp op, Node n)
3099 return VisitNode(n.Child0);
3105 /// <param name="op"></param>
3106 /// <param name="n"></param>
3107 /// <returns></returns>
3108 public override int Visit(GroupByOp op, Node n)
3110 return op.Outputs.Count;
3116 /// <param name="op"></param>
3117 /// <param name="n"></param>
3118 /// <returns></returns>
3119 public override int Visit(ProjectOp op, Node n)
3121 return op.Outputs.Count;
3128 /// <param name="op"></param>
3129 /// <param name="n"></param>
3130 /// <returns></returns>
3131 public override int Visit(ScanTableOp op, Node n)
3133 return op.Table.Columns.Count;
3137 /// SingleRowTableOp
3139 /// <param name="op"></param>
3140 /// <param name="n"></param>
3141 /// <returns></returns>
3142 public override int Visit(SingleRowTableOp op, Node n)
3148 /// Same as the input
3150 /// <param name="op"></param>
3151 /// <param name="n"></param>
3152 /// <returns></returns>
3153 protected override int VisitSortOp(SortBaseOp op, Node n)
3155 return VisitNode(n.Child0);
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.
3169 internal class VarDefinitionRemapper : VarRemapper
3171 private readonly Var m_oldVar;
3173 private VarDefinitionRemapper(Var oldVar, Command command)
3176 this.m_oldVar = oldVar;
3180 /// Public entry point.
3181 /// Remaps the subree rooted at the given tree
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)
3188 VarDefinitionRemapper remapper = new VarDefinitionRemapper(oldVar, command);
3189 remapper.RemapSubtree(root);
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.
3197 /// <param name="subTree"></param>
3198 internal override void RemapSubtree(Node subTree)
3200 foreach (Node chi in subTree.Children)
3206 m_command.RecomputeNodeInfo(subTree);
3210 /// If the node defines the node that needs to be remapped,
3211 /// it remaps it to a new var.
3213 /// <param name="op"></param>
3214 /// <param name="n"></param>
3215 /// <returns></returns>
3216 public override void Visit(VarDefOp op, Node n)
3218 if (op.Var == m_oldVar)
3220 Var newVar = m_command.CreateComputedVar(n.Child0.Op.Type);
3221 n.Op = m_command.CreateVarDefOp(newVar);
3222 AddMapping(m_oldVar, newVar);
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.
3230 /// <param name="op"></param>
3231 /// <param name="n"></param>
3232 /// <returns></returns>
3233 public override void Visit(ScanTableOp op, Node n)
3235 if (op.Table.Columns.Contains(m_oldVar))
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++)
3241 AddMapping(op.Table.Columns[i], newScanTableOp.Table.Columns[i]);
3243 n.Op = newScanTableOp;
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.
3251 /// <param name="op"></param>
3252 /// <param name="n"></param>
3253 protected override void VisitSetOp(SetOp op, Node n)
3255 base.VisitSetOp(op, n);
3257 if (op.Outputs.IsSet(m_oldVar))
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);
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.
3272 /// <param name="varMap"></param>
3273 /// <param name="newVar"></param>
3274 private void RemapVarMapKey(VarMap varMap, Var newVar)
3276 Var value = varMap[m_oldVar];
3277 varMap.Remove(m_oldVar);
3278 varMap.Add(newVar, value);
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);
3293 /// Convert a CrossApply(X, LeftOuterJoin(SingleRowTable, Y, on true))
3294 /// into just OuterApply(X, Y)
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)
3302 newNode = applyNode;
3303 Node joinNode = applyNode.Child1;
3305 //Check the value of the predicate
3306 ConstantPredicateOp joinPredicate = (ConstantPredicateOp)joinNode.Child2.Op;
3307 if (joinPredicate.IsFalse)
3312 applyNode.Op = context.Command.CreateOuterApplyOp();
3313 applyNode.Child1 = joinNode.Child1;
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,
3338 /// Transformation rules for JoinOps
3340 internal static class JoinOpRules
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);
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)
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)
3394 TransformationRulesContext trc = (TransformationRulesContext)context;
3395 Command command = trc.Command;
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))
3405 Node newProjectNode;
3407 // Now locate the ProjectOps
3408 VarVec newVarSet = command.CreateVarVec();
3409 List<Node> varDefNodes = new List<Node>();
3412 // Try and handle "project" on both sides only if we're not dealing with
3415 if ((joinNode.Op.OpType != OpType.LeftOuterJoin) &&
3416 (joinNode.Child0.Op.OpType == OpType.Project) &&
3417 (joinNode.Child1.Op.OpType == OpType.Project))
3419 ProjectOp projectOp1 = (ProjectOp)joinNode.Child0.Op;
3420 ProjectOp projectOp2 = (ProjectOp)joinNode.Child1.Op;
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)
3429 if (joinConditionNode != null)
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);
3437 newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0);
3440 newVarSet.InitFrom(projectOp1.Outputs);
3441 foreach (Var v in projectOp2.Outputs)
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(),
3451 newProjectNode = command.CreateNode(newProjectOp,
3452 newJoinNode, varDefListNode);
3453 newNode = newProjectNode;
3457 int projectNodeIdx = -1;
3458 int otherNodeIdx = -1;
3459 if (joinNode.Child0.Op.OpType == OpType.Project)
3466 PlanCompiler.Assert(joinNode.Op.OpType != OpType.LeftOuterJoin, "unexpected non-LeftOuterJoin");
3470 Node projectNode = joinNode.Children[projectNodeIdx];
3472 ProjectOp projectOp = projectNode.Op as ProjectOp;
3473 Dictionary<Var, Node> varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
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)
3484 joinConditionNode = trc.ReMap(joinConditionNode, varMap);
3485 joinNode.Child2 = joinConditionNode;
3487 joinNode.Children[projectNodeIdx] = projectNode.Child0; // bypass the projectOp
3488 context.Command.RecomputeNodeInfo(joinNode);
3490 newNode = context.Command.CreateNode(projectOp, joinNode, projectNode.Child1);
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);
3535 /// CrossJoin(Filter(A,p), B) => Filter(CrossJoin(A, B), p)
3536 /// CrossJoin(A, Filter(B,p)) => Filter(CrossJoin(A, B), p)
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)
3541 /// LeftOuterJoin(Filter(A,p), B, c) => Filter(LeftOuterJoin(A, B, c), p)
3543 /// Note that the predicate on the right table in a left-outer-join cannot be pulled
3544 /// up above the join.
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)
3554 TransformationRulesContext trc = (TransformationRulesContext)context;
3555 Command command = trc.Command;
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)
3562 predicateNode = joinNode.Child0.Child1;
3563 newLeftInput = joinNode.Child0.Child0; // bypass the filter
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)
3570 if (predicateNode == null)
3572 predicateNode = joinNode.Child1.Child1;
3576 predicateNode = command.CreateNode(
3577 command.CreateConditionalOp(OpType.And),
3578 predicateNode, joinNode.Child1.Child1);
3580 newRightInput = joinNode.Child1.Child0; // bypass the filter
3583 // No optimizations to perform if we can't locate the appropriate predicate
3584 if (predicateNode == null)
3590 // Create a new join node with the new inputs
3593 if (joinNode.Op.OpType == OpType.CrossJoin)
3595 newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput);
3599 newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput, joinNode.Child2);
3603 // create a new filterOp with the combined predicates, and with the
3604 // newjoinNode as the input
3606 FilterOp newFilterOp = command.CreateFilterOp();
3607 newNode = command.CreateNode(newFilterOp, newJoinNode, predicateNode);
3610 // Mark this subtree so that we don't try to push filters down again
3612 trc.SuppressFilterPushdown(newNode);
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);
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);
3636 /// Convert a CrossJoin(SingleRowTable, X) or CrossJoin(X, SingleRowTable) or LeftOuterJoin(X, SingleRowTable)
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)
3647 if (joinNode.Child0.Op.OpType == OpType.SingleRowTable)
3649 newNode = joinNode.Child1;
3653 newNode = joinNode.Child0;
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,
3670 Rule_CrossJoinOverFilter1,
3671 Rule_CrossJoinOverFilter2,
3672 Rule_InnerJoinOverFilter1,
3673 Rule_InnerJoinOverFilter2,
3674 Rule_OuterJoinOverFilter2,
3676 Rule_CrossJoinOverSingleRowTable1,
3677 Rule_CrossJoinOverSingleRowTable2,
3678 Rule_LeftOuterJoinOverSingleRowTable,
3685 #region SingleRowOp Rules
3687 /// Rules for SingleRowOp
3689 internal static class SingleRowOpRules
3691 internal static readonly PatternMatchRule Rule_SingleRowOpOverAnything =
3692 new PatternMatchRule(new Node(SingleRowOp.Pattern,
3693 new Node(LeafOp.Pattern)),
3694 ProcessSingleRowOpOverAnything);
3697 /// SingleRowOp(X) => X
3698 /// if X produces at most one row
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)
3706 newNode = singleRowNode;
3707 TransformationRulesContext trc = (TransformationRulesContext)context;
3708 ExtendedNodeInfo childNodeInfo = context.Command.GetExtendedNodeInfo(singleRowNode.Child0);
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)
3714 newNode = singleRowNode.Child0;
3719 // if the current node is a FilterOp, then try and determine if the FilterOp
3720 // produces one row at most
3722 if (singleRowNode.Child0.Op.OpType == OpType.Filter)
3724 Predicate predicate = new Predicate(context.Command, singleRowNode.Child0.Child1);
3725 if (predicate.SatisfiesKey(childNodeInfo.Keys.KeyVars, childNodeInfo.Definitions))
3727 childNodeInfo.MaxRows = RowCount.One;
3728 newNode = singleRowNode.Child0;
3733 // we couldn't do anything
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);
3744 /// SingleRowOp(Project) => Project(SingleRowOp)
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)
3752 newNode = singleRowNode;
3753 Node projectNode = singleRowNode.Child0;
3754 Node projectNodeInput = projectNode.Child0;
3756 // Simply push the SingleRowOp below the ProjectOp
3757 singleRowNode.Child0 = projectNodeInput;
3758 context.Command.RecomputeNodeInfo(singleRowNode);
3759 projectNode.Child0 = singleRowNode;
3761 newNode = projectNode;
3762 return true; // subtree modified internally
3765 #region All SingleRowOp Rules
3766 internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
3767 Rule_SingleRowOpOverAnything,
3768 Rule_SingleRowOpOverProject,
3776 /// SetOp Transformation Rules
3778 internal static class SetOpRules
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);
3789 /// Process a SetOp when one of the inputs is an emptyset.
3791 /// An emptyset is represented by a Filter(X, ConstantPredicate)
3792 /// where the ConstantPredicate has a value of "false"
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
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
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)
3814 bool leftChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child0).MaxRows == RowCount.Zero;
3815 bool rightChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child1).MaxRows == RowCount.Zero;
3817 if (!leftChildIsEmptySet && !rightChildIsEmptySet)
3819 newNode = setOpNode;
3824 SetOp setOp = (SetOp)setOpNode.Op;
3825 if (!rightChildIsEmptySet && setOp.OpType == OpType.UnionAll ||
3826 !leftChildIsEmptySet && setOp.OpType == OpType.Intersect)
3835 newNode = setOpNode.Children[indexToReturn];
3837 TransformationRulesContext trc = (TransformationRulesContext)context;
3838 foreach (KeyValuePair<Var, Var> kv in setOp.VarMap[indexToReturn])
3840 trc.AddVarMapping(kv.Key, kv.Value);
3847 #region All SetOp Rules
3848 internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
3849 Rule_UnionAllOverEmptySet,
3850 Rule_IntersectOverEmptySet,
3851 Rule_ExceptOverEmptySet,
3857 #region GroupByOp Rules
3859 /// Transformation Rules for GroupByOps
3861 internal static class GroupByOpRules
3863 #region GroupByOpWithSimpleVarRedefinitions
3864 internal static readonly SimpleRule Rule_GroupByOpWithSimpleVarRedefinitions = new SimpleRule(OpType.GroupBy, ProcessGroupByWithSimpleVarRedefinitions);
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.
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
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)
3881 GroupByOp groupByOp = (GroupByOp)n.Op;
3882 // no local keys? nothing to do
3883 if (n.Child1.Children.Count == 0)
3888 TransformationRulesContext trc = (TransformationRulesContext)context;
3889 Command command = trc.Command;
3891 ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
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
3898 bool canEliminateSomeVars = false;
3899 foreach (Node varDefNode in n.Child1.Children)
3901 Node definingExprNode = varDefNode.Child0;
3902 if (definingExprNode.Op.OpType == OpType.VarRef)
3904 VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
3905 if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
3907 // this is a Var that we should remove
3908 canEliminateSomeVars = true;
3913 // Did we have any redefinitions
3914 if (!canEliminateSomeVars)
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
3924 // Lets now build up a new VarDefListNode
3925 List<Node> newVarDefNodes = new List<Node>();
3926 foreach (Node varDefNode in n.Child1.Children)
3928 VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
3929 VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
3930 if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
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);
3940 newVarDefNodes.Add(varDefNode);
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
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);
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.
3967 /// We only do this if each c1, ..ck is refereneced (in aggregates) at most once or it is a constant.
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)
3976 GroupByOp op = (GroupByOp)n.Op;
3977 Command command = ((TransformationRulesContext)context).Command;
3978 Node projectNode = n.Child0;
3979 Node projectNodeVarDefList = projectNode.Child1;
3981 Node keys = n.Child1;
3982 Node aggregates = n.Child2;
3984 // If there are any keys, we should not remove the inner project
3985 if (keys.Children.Count > 0)
3990 //Get a list of all defining vars
3991 VarVec projectDefinitions = command.GetExtendedNodeInfo(projectNode).LocalDefinitions;
3993 //If any of the defined vars is output, than we need the extra project anyway.
3994 if (op.Outputs.Overlaps(projectDefinitions))
3999 bool createdNewProjectDefinitions = false;
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++)
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)
4008 //We shouldn't modify the original project definitions, thus we copy it
4009 // the first time we encounter a constant
4010 if (!createdNewProjectDefinitions)
4012 projectDefinitions = command.CreateVarVec(projectDefinitions);
4013 createdNewProjectDefinitions = true;
4015 projectDefinitions.Clear(((VarDefOp)varDefNode.Op).Var);
4019 if (VarRefUsageFinder.AnyVarUsedMoreThanOnce(projectDefinitions, aggregates, command))
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++)
4029 Node varDefNode = projectNodeVarDefList.Children[j];
4030 Var var = ((VarDefOp)varDefNode.Op).Var;
4031 varToDefiningNode.Add(var, varDefNode.Child0);
4034 newNode.Child2 = VarRefReplacer.Replace(varToDefiningNode, aggregates, command);
4036 newNode.Child0 = projectNode.Child0;
4041 /// Replaces each occurance of the given vars with their definitions.
4043 internal class VarRefReplacer : BasicOpVisitorOfNode
4045 private Dictionary<Var, Node> m_varReplacementTable;
4046 private Command m_command;
4048 private VarRefReplacer(Dictionary<Var, Node> varReplacementTable, Command command)
4050 this.m_varReplacementTable = varReplacementTable;
4051 this.m_command = command;
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.
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)
4065 VarRefReplacer replacer = new VarRefReplacer(varReplacementTable, command);
4066 return replacer.VisitNode(root);
4069 public override Node Visit(VarRefOp op, Node n)
4071 Node replacementNode;
4072 if (m_varReplacementTable.TryGetValue(op.Var, out replacementNode))
4074 return replacementNode;
4083 /// Recomputes node info post regular processing.
4085 /// <param name="n"></param>
4086 /// <returns></returns>
4087 protected override Node VisitDefault(Node n)
4089 Node result = base.VisitDefault(n);
4090 m_command.RecomputeNodeInfo(result);
4096 /// Used to determine whether any of the given vars occurs more than once
4097 /// in a given subtree.
4099 internal class VarRefUsageFinder : BasicOpVisitor
4101 private bool m_anyUsedMoreThenOnce = false;
4102 private VarVec m_varVec;
4103 private VarVec m_usedVars;
4105 private VarRefUsageFinder(VarVec varVec, Command command)
4107 this.m_varVec = varVec;
4108 this.m_usedVars = command.CreateVarVec();
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.
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)
4121 VarRefUsageFinder usageFinder = new VarRefUsageFinder(varVec, command);
4122 usageFinder.VisitNode(root);
4123 return usageFinder.m_anyUsedMoreThenOnce;
4126 public override void Visit(VarRefOp op, Node n)
4128 Var referencedVar = op.Var;
4129 if (m_varVec.IsSet(referencedVar))
4131 if (m_usedVars.IsSet(referencedVar))
4133 this.m_anyUsedMoreThenOnce = true;
4137 m_usedVars.Set(referencedVar);
4142 protected override void VisitChildren(Node n)
4144 //small optimization: no need to continue if we have the answer
4145 if (m_anyUsedMoreThenOnce)
4149 base.VisitChildren(n);
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);
4162 /// If the GroupByOp has no aggregates:
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.
4167 /// (2) else it can be turned into a Distinct:
4168 /// GroupBy (X, keys) -> Distinct(X, keys)
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)
4177 Command command = context.Command;
4178 GroupByOp op = (GroupByOp)n.Op;
4180 ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
4181 ProjectOp newOp = command.CreateProjectOp(op.Keys);
4183 VarDefListOp varDefListOp = command.CreateVarDefListOp();
4184 Node varDefListNode = command.CreateNode(varDefListOp);
4186 newNode = command.CreateNode(newOp, n.Child0, n.Child1);
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))
4192 newNode = command.CreateNode(command.CreateDistinctOp(command.CreateVarVec(op.Keys)), newNode);
4198 #region GroupByOpOnAllInputColumnsWithAggregateOperation
4200 internal static readonly SimpleRule Rule_GroupByOpOnAllInputColumnsWithAggregateOperation = new SimpleRule(
4201 OpType.GroupBy, ProcessGroupByOpOnAllInputColumnsWithAggregateOperation);
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
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
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)
4231 var rootOp = context.Command.Root.Op as PhysicalProjectOp;
4232 if (rootOp == null ||
4233 rootOp.Outputs.Count > 1)
4238 if (n.Child0.Op.OpType != OpType.ScanTable)
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)
4251 var groupByOp = (GroupByOp)n.Op;
4253 var sourceTable = ((ScanTableOp)n.Child0.Op).Table;
4254 var allInputColumns = sourceTable.Columns;
4256 // Exit if the group's keys do not contain all the columns defined by Child0
4257 foreach (var column in allInputColumns)
4259 if (!groupByOp.Keys.IsSet(column))
4265 // All the columns of Child0 are used, so remove them from the outputs and the keys
4266 foreach (var column in allInputColumns)
4268 groupByOp.Outputs.Clear(column);
4269 groupByOp.Keys.Clear(column);
4272 // Build the OuterApply and also set the filter around the GroupBy's scan table.
4273 var command = context.Command;
4275 var scanTableOp = command.CreateScanTableOp(sourceTable.TableMetadata);
4276 var scanTable = command.CreateNode(scanTableOp);
4277 var outerApplyNode = command.CreateNode(command.CreateOuterApplyOp(), scanTable, n);
4280 var varDefListNode = command.CreateVarDefListNode(command.CreateNode(command.CreateVarRefOp(groupByOp.Outputs.First)), out newVar);
4282 newNode = command.CreateNode(
4283 command.CreateProjectOp(newVar),
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)
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)
4300 equality = command.CreateNode(
4301 command.CreateConditionalOp(OpType.And),
4302 equality, comparison);
4306 equality = comparison;
4310 var filter = command.CreateNode(command.CreateFilterOp(),
4315 return true; // subtree modified
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,
4331 #region Sorting Rules
4333 /// Transformation Rules for SortOp
4335 internal static class SortOpRules
4337 #region SortOpOverAtMostOneRow
4338 internal static readonly SimpleRule Rule_SortOpOverAtMostOneRow = new SimpleRule(OpType.Sort, ProcessSortOpOverAtMostOneRow);
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
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)
4349 ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
4351 //If the input has at most one row, omit the SortOp
4352 if (nodeInfo.MaxRows == RowCount.Zero || nodeInfo.MaxRows == RowCount.One)
4358 //Otherwise return the node as is
4364 #region All SortOp Rules
4365 internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
4366 SortOpRules.Rule_SortOpOverAtMostOneRow,
4372 /// Transformation Rules for ConstrainedSortOp
4374 internal static class ConstrainedSortOpRules
4376 #region ConstrainedSortOpOverEmptySet
4377 internal static readonly SimpleRule Rule_ConstrainedSortOpOverEmptySet = new SimpleRule(OpType.ConstrainedSort, ProcessConstrainedSortOpOverEmptySet);
4379 /// If the ConstrainedSortOp's input is guaranteed to produce no rows, remove the ConstrainedSortOp completly:
4380 /// CSort(EmptySet) => EmptySet
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)
4388 ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
4390 //If the input has no rows, remove the ConstraintSortOp node completly
4391 if (nodeInfo.MaxRows == RowCount.Zero)
4402 #region All ConstrainedSortOp Rules
4403 internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
4404 ConstrainedSortOpRules.Rule_ConstrainedSortOpOverEmptySet,
4410 #region DistinctOp Rules
4412 /// Transformation Rules for DistinctOp
4414 internal static class DistinctOpRules
4416 #region DistinctOpOfKeys
4417 internal static readonly SimpleRule Rule_DistinctOpOfKeys = new SimpleRule(OpType.Distinct, ProcessDistinctOpOfKeys);
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.
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)
4428 Command command = context.Command;
4430 ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
4432 DistinctOp op = (DistinctOp)n.Op;
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))
4437 ProjectOp newOp = command.CreateProjectOp(op.Keys);
4439 //Create empty vardef list
4440 VarDefListOp varDefListOp = command.CreateVarDefListOp();
4441 Node varDefListNode = command.CreateNode(varDefListOp);
4443 newNode = command.CreateNode(newOp, n.Child0, varDefListNode);
4447 //Otherwise return the node as is
4453 #region All DistinctOp Rules
4454 internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
4455 DistinctOpRules.Rule_DistinctOpOfKeys,