Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / TransformationRules.cs / 1305376 / TransformationRules.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....]
// @backupOwner [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization;
using System.Linq;
using System.Data.Metadata.Edm;
using System.Data.Query.InternalTrees;
namespace System.Data.Query.PlanCompiler
{
internal class TransformationRulesContext : RuleProcessingContext
{
#region public methods and properties
///
/// Whether any rule was applied that may have caused modifications such that projection pruning
/// may be useful
///
internal bool ProjectionPrunningRequired { get { return this.m_projectionPrunningRequired; } }
///
/// Whether any rule was applied that may have caused modifications such that reapplying
/// the nullability rules may be useful
///
internal bool ReapplyNullabilityRules { get { return this.m_reapplyNullabilityRules; } }
///
/// Remap the given subree using the current remapper
///
///
internal void RemapSubtree(Node subTree)
{
this.m_remapper.RemapSubtree(subTree);
}
///
/// Adds a mapping from oldVar to newVar
///
///
///
internal void AddVarMapping(Var oldVar, Var newVar)
{
m_remapper.AddMapping(oldVar, newVar);
m_remappedVars.Set(oldVar);
}
///
/// "Remap" an expression tree, replacing all references to vars in varMap with
/// copies of the corresponding expression
/// The subtree is modified *inplace* - it is the caller's responsibility to make
/// a copy of the subtree if necessary.
/// The "replacement" expression (the replacement for the VarRef) is copied and then
/// inserted into the appropriate location into the subtree.
///
/// Note: we only support replacements in simple ScalarOp trees. This must be
/// validated by the caller.
///
///
/// Current subtree to process
///
/// The updated subtree
internal Node ReMap(Node node, Dictionary varMap)
{
PlanCompiler.Assert(node.Op.IsScalarOp, "Expected a scalarOp: Found " + Dump.AutoString.ToString(node.Op.OpType));
// Replace varRefOps by the corresponding expression in the map, if any
if (node.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = node.Op as VarRefOp;
Node newNode = null;
if (varMap.TryGetValue(varRefOp.Var, out newNode))
{
newNode = this.Copy(newNode);
return newNode;
}
else
{
return node;
}
}
// Simply process the result of the children.
for (int i = 0; i < node.Children.Count; i++)
{
node.Children[i] = ReMap(node.Children[i], varMap);
}
// We may have changed something deep down
this.Command.RecomputeNodeInfo(node);
return node;
}
///
/// Makes a copy of the appropriate subtree - with a simple accelerator for VarRefOp
/// since that's likely to be the most command case
///
/// the subtree to copy
/// the copy of the subtree
internal Node Copy(Node node)
{
if (node.Op.OpType == OpType.VarRef)
{
VarRefOp op = node.Op as VarRefOp;
return this.Command.CreateNode(this.Command.CreateVarRefOp(op.Var));
}
else
{
return OpCopier.Copy(this.Command, node);
}
}
///
/// Checks to see if the current subtree only contains ScalarOps
///
/// current subtree
/// true, if the subtree contains only ScalarOps
internal bool IsScalarOpTree(Node node)
{
int nodeCount = 0;
return IsScalarOpTree(node, null, ref nodeCount);
}
///
/// Is the given var guaranteed to be non-nullable with regards to the node
/// that is currently being processed.
/// True, if it is listed as such on any on the node infos on any of the
/// current relop ancestors.
///
///
///
/// Is it safe to use a null sentinel with any value?
/// It may not be safe if:
/// 1. The top most sort includes null sentinels. If the null sentinel is replaced with a different value
/// and is used as a sort key it may change the sorting results
/// 2. If any of the ancestors is Distinct, GroupBy, Intersect or Except,
/// because the null sentinel may be used as a key.
/// 3. If the null sentinel is defined in the left child of an apply it may be used at the right side,
/// thus in these cases we also verify that the right hand side does not have any Distinct, GroupBy,
/// Intersect or Except.
///
internal bool CanChangeNullSentinelValue
{
get
{
//Is there a sort that includes null sentinels
if (this.m_compilerState.HasSortingOnNullSentinels)
{
return false;
}
//Is any of the ancestors Distinct, GroupBy, Intersect or Except
if (this.m_relOpAncestors.Any(a => IsOpNotSafeForNullSentinelValueChange(a.Op.OpType)))
{
return false;
}
// Is the null sentinel defined in the left child of an apply and if so,
// does the right hand side have any Distinct, GroupBy, Intersect or Except.
var applyAncestors = this.m_relOpAncestors.Where(a =>
a.Op.OpType == OpType.CrossApply ||
a.Op.OpType == OpType.OuterApply);
//If the sentinel comes from the right hand side it is ok.
foreach (Node applyAncestor in applyAncestors)
{
if (!this.m_relOpAncestors.Contains(applyAncestor.Child1) && HasOpNotSafeForNullSentinelValueChange(applyAncestor.Child1))
{
return false;
}
}
return true;
}
}
///
/// Is the op not safe for null sentinel value change
///
///
///
/// Does the given subtree contain a node with an op that
/// is not safer for null sentinel value change
///
///
///
/// Is this is a scalar-op tree? Also return a dictionary of var refcounts (ie)
/// for each var encountered in the tree, determine the number of times it has
/// been seen
///
/// current subtree
/// dictionary of var refcounts to fill in
/// varRefMap)
{
PlanCompiler.Assert(varRefMap != null, "Null varRef map");
int nodeCount = 0;
return IsScalarOpTree(node, varRefMap, ref nodeCount);
}
///
/// Get a mapping from Var->Expression for a VarDefListOp tree. This information
/// will be used by later stages to replace all references to the Vars by the
/// corresponding expressions
///
/// This function uses a few heuristics along the way. It uses the varRefMap
/// parameter to determine if a computed Var (defined by this VarDefListOp)
/// has been referenced multiple times, and if it has, it checks to see if
/// the defining expression is too big (> 100 nodes). This is to avoid
/// bloating up the entire query tree with too many copies.
///
///
/// The varDefListOp subtree
/// ref counts for each referenced var
/// mapping from Var->replacement xpressions
internal Dictionary GetVarMap(Node varDefListNode, Dictionary varRefMap)
{
VarDefListOp varDefListOp = (VarDefListOp)varDefListNode.Op;
Dictionary varMap = new Dictionary();
foreach (Node chi in varDefListNode.Children)
{
VarDefOp varDefOp = (VarDefOp)chi.Op;
int nonLeafNodeCount = 0;
int refCount = 0;
if (!IsScalarOpTree(chi.Child0, null, ref nonLeafNodeCount))
{
return null;
}
//
// More heuristics. If there are multiple references to this Var *and*
// the defining expression for the Var is "expensive" (ie) has larger than
// 100 nodes, then simply pretend that this is too hard to do
// Note: we check for more than 2 references, (rather than just more than 1) - this
// is simply to let some additional cases through
//
if ((nonLeafNodeCount > 100) &&
(varRefMap != null) &&
varRefMap.TryGetValue(varDefOp.Var, out refCount) &&
(refCount > 2))
{
return null;
}
Node n;
if (varMap.TryGetValue(varDefOp.Var, out n))
{
PlanCompiler.Assert(n == chi.Child0, "reusing varDef for different Node?");
}
else
{
varMap.Add(varDefOp.Var, chi.Child0);
}
}
return varMap;
}
///
/// Builds a NULLIF expression (ie) a Case expression that looks like
/// CASE WHEN v is null THEN null ELSE expr END
/// where v is the conditionVar parameter, and expr is the value of the expression
/// when v is non-null
///
/// null discriminator var
/// expression
///
/// Shut off filter pushdown for this subtree
///
///
internal void SuppressFilterPushdown(Node n)
{
m_suppressions[n] = n;
}
///
/// Is filter pushdown shut off for this subtree?
///
///
///
/// Given a list of vars try to get one that is of type Int32
///
///
///
/// ();
m_remappedVars = compilerState.Command.CreateVarVec();
}
#endregion
#region private state
private readonly PlanCompiler m_compilerState;
private readonly VarRemapper m_remapper;
private readonly Dictionary m_suppressions;
private readonly VarVec m_remappedVars;
private bool m_projectionPrunningRequired = false;
private bool m_reapplyNullabilityRules = false;
private Stack m_relOpAncestors = new Stack();
#if DEBUG
///
/// Used to see all the applied rules.
/// One way to use it is to put a conditional breakpoint at the end of
/// PostProcessSubTree with the condition m_relOpAncestors.Count == 0
///
internal readonly System.Text.StringBuilder appliedRules = new System.Text.StringBuilder();
#endif
#endregion
#region RuleProcessingContext Overrides
///
/// Callback function to invoke *before* rules are applied.
/// Calls the VarRemapper to update any Vars in this node, and recomputes
/// the nodeinfo
///
///
internal override void PreProcess(Node n)
{
m_remapper.RemapNode(n);
Command.RecomputeNodeInfo(n);
}
///
/// Callback function to invoke *before* rules are applied.
/// Calls the VarRemapper to update any Vars in the entire subtree
/// If the given node has a RelOp it is pushed on the relOp ancestors stack.
///
///
internal override void PreProcessSubTree(Node subTree)
{
if (subTree.Op.IsRelOp)
{
m_relOpAncestors.Push(subTree);
}
if (m_remappedVars.IsEmpty)
{
return;
}
NodeInfo nodeInfo = this.Command.GetNodeInfo(subTree);
//We need to do remapping only if m_remappedVars overlaps with nodeInfo.ExternalReferences
foreach (Var v in nodeInfo.ExternalReferences)
{
if (m_remappedVars.IsSet(v))
{
m_remapper.RemapSubtree(subTree);
break;
}
}
}
///
/// If the given node has a RelOp it is popped from the relOp ancestors stack.
///
///
internal override void PostProcessSubTree(Node subtree)
{
if (subtree.Op.IsRelOp)
{
PlanCompiler.Assert(m_relOpAncestors.Count != 0, "The RelOp ancestors stack is empty when post processing a RelOp subtree");
Node poppedNode = m_relOpAncestors.Pop();
PlanCompiler.Assert(Object.ReferenceEquals(subtree, poppedNode), "The popped ancestor is not equal to the root of the subtree being post processed");
}
}
///
/// Callback function to invoke *after* rules are applied
/// Recomputes the node info, if this node has changed
/// If the rule is among the rules after which projection pruning may be beneficial,
/// m_projectionPrunningRequired is set to true.
/// If the rule is among the rules after which reapplying the nullability rules may be beneficial,
/// m_reapplyNullabilityRules is set to true.
///
///
/// the rule that was applied
internal override void PostProcess(Node n, InternalTrees.Rule rule)
{
if (rule != null)
{
#if DEBUG
appliedRules.Append(rule.MethodName);
appliedRules.AppendLine();
#endif
if (!this.m_projectionPrunningRequired && TransformationRules.RulesRequiringProjectionPruning.Contains(rule))
{
this.m_projectionPrunningRequired = true;
}
if (!this.m_reapplyNullabilityRules && TransformationRules.RulesRequiringNullabilityRulesToBeReapplied.Contains(rule))
{
this.m_reapplyNullabilityRules = true;
}
Command.RecomputeNodeInfo(n);
}
}
///
/// Get the hash value for this subtree
///
///
///
/// Check to see if the current subtree is a scalar-op subtree (ie) does
/// the subtree only comprise of scalarOps?
/// Additionally, compute the number of non-leaf nodes (ie) nodes with at least one child
/// that are found in the subtree. Note that this count is approximate - it is only
/// intended to be used as a hint. It is the caller's responsibility to initialize
/// nodeCount to a sane value on entry into this function
/// And finally, if the varRefMap parameter is non-null, we keep track of
/// how often a Var is referenced within the subtree
///
/// The non-leaf-node count and the varRefMap are used by GetVarMap to determine
/// if expressions can be composed together
///
/// root of the subtree
/// Ref counts for each Var encountered in the subtree
/// count of non-leaf nodes encountered in the subtree
/// true, if this node only contains scalarOps
private bool IsScalarOpTree(Node node, Dictionary varRefMap, ref int nonLeafNodeCount)
{
if (!node.Op.IsScalarOp)
{
return false;
}
if (node.HasChild0)
{
nonLeafNodeCount++;
}
if (varRefMap != null && node.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = (VarRefOp)node.Op;
int refCount;
if (!varRefMap.TryGetValue(varRefOp.Var, out refCount))
{
refCount = 1;
}
else
{
refCount++;
}
varRefMap[varRefOp.Var] = refCount;
}
foreach (Node chi in node.Children)
{
if (!IsScalarOpTree(chi, varRefMap, ref nonLeafNodeCount))
{
return false;
}
}
return true;
}
#endregion
}
///
/// The list of all transformation rules to apply
///
internal static class TransformationRules
{
///
/// A lookup table for built from all rules
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> AllRulesTable = BuildLookupTableForRules(AllRules);
///
/// A lookup table for built only from ProjectRules
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> ProjectRulesTable = BuildLookupTableForRules(ProjectOpRules.Rules);
///
/// A lookup table built only from rules that use key info
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> PostJoinEliminationRulesTable = BuildLookupTableForRules(PostJoinEliminationRules);
///
/// A lookup table built only from rules that rely on nullability of vars and other rules
/// that may be able to perform simplificatios if these have been applied.
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> NullabilityRulesTable = BuildLookupTableForRules(NullabilityRules);
///
/// A look-up table of rules that may cause modifications such that projection pruning may be useful
/// after they have been applied.
///
internal static readonly HashSet RulesRequiringProjectionPruning = InitializeRulesRequiringProjectionPruning();
///
/// A look-up table of rules that may cause modifications such that reapplying the nullability rules
/// may be useful after they have been applied.
///
internal static readonly HashSet RulesRequiringNullabilityRulesToBeReapplied = InitializeRulesRequiringNullabilityRulesToBeReapplied();
#region private state maintenance
private static List allRules;
private static List AllRules
{
get
{
if (allRules == null)
{
allRules = new List();
allRules.AddRange(ScalarOpRules.Rules);
allRules.AddRange(FilterOpRules.Rules);
allRules.AddRange(ProjectOpRules.Rules);
allRules.AddRange(ApplyOpRules.Rules);
allRules.AddRange(JoinOpRules.Rules);
allRules.AddRange(SingleRowOpRules.Rules);
allRules.AddRange(SetOpRules.Rules);
allRules.AddRange(GroupByOpRules.Rules);
allRules.AddRange(SortOpRules.Rules);
allRules.AddRange(ConstrainedSortOpRules.Rules);
allRules.AddRange(DistinctOpRules.Rules);
}
return allRules;
}
}
private static List postJoinEliminationRules;
private static List PostJoinEliminationRules
{
get
{
if (postJoinEliminationRules == null)
{
postJoinEliminationRules = new List();
postJoinEliminationRules.AddRange(ProjectOpRules.Rules); //these don't use key info per-se, but can help after the distinct op rules.
postJoinEliminationRules.AddRange(DistinctOpRules.Rules);
postJoinEliminationRules.AddRange(FilterOpRules.Rules);
postJoinEliminationRules.AddRange(JoinOpRules.Rules);
postJoinEliminationRules.AddRange(NullabilityRules);
}
return postJoinEliminationRules;
}
}
private static List nullabilityRules;
private static List NullabilityRules
{
get
{
if (nullabilityRules == null)
{
nullabilityRules = new List();
nullabilityRules.Add(ScalarOpRules.Rule_IsNullOverVarRef);
nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred1);
nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred2);
nullabilityRules.Add(ScalarOpRules.Rule_SimplifyCase);
}
return nullabilityRules;
}
}
private static ReadOnlyCollection> BuildLookupTableForRules(IEnumerable rules)
{
ReadOnlyCollection NoRules = new ReadOnlyCollection(new InternalTrees.Rule[0]);
List[] lookupTable = new List[(int)OpType.MaxMarker];
foreach (InternalTrees.Rule rule in rules)
{
List opRules = lookupTable[(int)rule.RuleOpType];
if (opRules == null)
{
opRules = new List();
lookupTable[(int)rule.RuleOpType] = opRules;
}
opRules.Add(rule);
}
ReadOnlyCollection[] rulesPerType = new ReadOnlyCollection[lookupTable.Length];
for (int i = 0; i < lookupTable.Length; ++i)
{
if (null != lookupTable[i])
{
rulesPerType[i] = new ReadOnlyCollection(lookupTable[i].ToArray());
}
else
{
rulesPerType[i] = NoRules;
}
}
return new ReadOnlyCollection>(rulesPerType);
}
private static HashSet InitializeRulesRequiringProjectionPruning()
{
HashSet rulesRequiringProjectionPruning = new HashSet();
rulesRequiringProjectionPruning.Add(ApplyOpRules.Rule_OuterApplyOverProject);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject1);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject2);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject1);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject2);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_OuterJoinOverProject2);
rulesRequiringProjectionPruning.Add(ProjectOpRules.Rule_ProjectWithNoLocalDefs);
rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterOverProject);
rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterWithConstantPredicate);
rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOverProject);
rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions);
return rulesRequiringProjectionPruning;
}
private static HashSet InitializeRulesRequiringNullabilityRulesToBeReapplied()
{
HashSet rulesRequiringNullabilityRulesToBeReapplied = new HashSet();
rulesRequiringNullabilityRulesToBeReapplied.Add(FilterOpRules.Rule_FilterOverLeftOuterJoin);
return rulesRequiringNullabilityRulesToBeReapplied;
}
#endregion
///
/// Apply the rules that belong to the specified group to the given query tree.
///
///
///
internal static bool Process(PlanCompiler compilerState, TransformationRulesGroup rulesGroup)
{
ReadOnlyCollection> rulesTable = null;
switch (rulesGroup)
{
case TransformationRulesGroup.All:
rulesTable = AllRulesTable;
break;
case TransformationRulesGroup.PostJoinElimination:
rulesTable = PostJoinEliminationRulesTable;
break;
case TransformationRulesGroup.Project:
rulesTable = ProjectRulesTable;
break;
}
// If any rule has been applied after which reapplying nullability rules may be useful,
// reapply nullability rules.
bool projectionPrunningRequired;
if (Process(compilerState, rulesTable, out projectionPrunningRequired))
{
bool projectionPrunningRequired2;
Process(compilerState, NullabilityRulesTable, out projectionPrunningRequired2);
projectionPrunningRequired = projectionPrunningRequired || projectionPrunningRequired2;
}
return projectionPrunningRequired;
}
///
/// Apply the rules that belong to the specified rules table to the given query tree.
///
///
///
/// is projection pruning required after the rule application
/// Whether any rule has been applied after which reapplying nullability rules may be useful
private static bool Process(PlanCompiler compilerState, ReadOnlyCollection> rulesTable, out bool projectionPruningRequired)
{
RuleProcessor ruleProcessor = new RuleProcessor();
TransformationRulesContext context = new TransformationRulesContext(compilerState);
compilerState.Command.Root = ruleProcessor.ApplyRulesToSubtree(context, rulesTable, compilerState.Command.Root);
projectionPruningRequired = context.ProjectionPrunningRequired;
return context.ReapplyNullabilityRules;
}
}
///
/// Available groups of rules, not necessarily mutually exclusive
///
internal enum TransformationRulesGroup
{
All,
Project,
PostJoinElimination
}
#region ScalarOpRules
///
/// Transformation rules for ScalarOps
///
internal static class ScalarOpRules
{
#region CaseOp Rules
internal static readonly SimpleRule Rule_SimplifyCase = new SimpleRule(OpType.Case, ProcessSimplifyCase);
internal static readonly SimpleRule Rule_FlattenCase = new SimpleRule(OpType.Case, ProcessFlattenCase);
///
/// We perform the following simple transformation for CaseOps. If every single
/// then/else expression in the CaseOp is equivalent, then we can simply replace
/// the Op with the first then/expression. Specifically,
/// case when w1 then t1 when w2 then t2 ... when wn then tn else e end
/// => t1
/// assuming that t1 is equivalent to t2 is equivalent to ... to e
///
/// Rule Processing context
/// The current subtree for the CaseOp
/// the (possibly) modified subtree
/// true, if we performed any transformations
static bool ProcessSimplifyCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
{
CaseOp caseOp = (CaseOp)caseOpNode.Op;
newNode = caseOpNode;
//
// Can I collapse the entire case-expression into a single expression - yes,
// if all the then/else clauses are the same expression
//
if (ProcessSimplifyCase_Collapse(caseOp, caseOpNode, out newNode))
{
return true;
}
//
// Can I remove any unnecessary when-then pairs ?
//
if (ProcessSimplifyCase_EliminateWhenClauses(context, caseOp, caseOpNode, out newNode))
{
return true;
}
// Nothing else I can think of
return false;
}
///
/// Try and collapse the case expression into a single expression.
/// If every single then/else expression in the CaseOp is equivalent, then we can
/// simply replace the CaseOp with the first then/expression. Specifically,
/// case when w1 then t1 when w2 then t2 ... when wn then tn else e end
/// => t1
/// if t1 is equivalent to t2 is equivalent to ... to e
///
/// the current caseOp
/// current subtree
/// new subtree
/// true, if we performed a transformation
private static bool ProcessSimplifyCase_Collapse(CaseOp caseOp, Node caseOpNode, out Node newNode)
{
newNode = caseOpNode;
Node firstThenNode = caseOpNode.Child1;
Node elseNode = caseOpNode.Children[caseOpNode.Children.Count - 1];
if (!firstThenNode.IsEquivalent(elseNode))
{
return false;
}
for (int i = 3; i < caseOpNode.Children.Count - 1; i += 2)
{
if (!caseOpNode.Children[i].IsEquivalent(firstThenNode))
{
return false;
}
}
// All nodes are equivalent - simply return the first then node
newNode = firstThenNode;
return true;
}
///
/// Try and remove spurious branches from the case expression.
/// If any of the WHEN clauses is the 'FALSE' expression, simply remove that
/// branch (when-then pair) from the case expression.
/// If any of the WHEN clauses is the 'TRUE' expression, then all branches to the
/// right of it are irrelevant - eliminate them. Eliminate this branch as well,
/// and make the THEN expression of this branch the ELSE expression for the entire
/// Case expression. If the WHEN expression represents the first branch, then
/// replace the entire case expression by the corresponding THEN expression
///
/// rule processing context
/// current caseOp
/// Current subtree
/// the new subtree
/// true, if there was a transformation
private static bool ProcessSimplifyCase_EliminateWhenClauses(RuleProcessingContext context, CaseOp caseOp, Node caseOpNode, out Node newNode)
{
List newNodeArgs = null;
newNode = caseOpNode;
for (int i = 0; i < caseOpNode.Children.Count; )
{
// Special handling for the else clause
if (i == caseOpNode.Children.Count - 1)
{
// If the else clause is a SoftCast then we do not attempt to simplify
// the case operation, since this may change the result type.
// This really belongs in more general SoftCastOp logic in the CTreeGenerator
// that converts SoftCasts that could affect the result type of the query into
// a real cast or a trivial case statement, to preserve the result type.
// This is tracked by SQL PT Work Item #300003327.
if (OpType.SoftCast == caseOpNode.Children[i].Op.OpType)
{
return false;
}
if (newNodeArgs != null)
{
newNodeArgs.Add(caseOpNode.Children[i]);
}
break;
}
// If the current then clause is a SoftCast then we do not attempt to simplify
// the case operation, since this may change the result type.
// Again, this really belongs in the CTreeGenerator as per SQL PT Work Item #300003327.
if (OpType.SoftCast == caseOpNode.Children[i + 1].Op.OpType)
{
return false;
}
// Check to see if the when clause is a ConstantPredicate
if (caseOpNode.Children[i].Op.OpType != OpType.ConstantPredicate)
{
if (newNodeArgs != null)
{
newNodeArgs.Add(caseOpNode.Children[i]);
newNodeArgs.Add(caseOpNode.Children[i + 1]);
}
i += 2;
continue;
}
// Found a when-clause which is a constant predicate
ConstantPredicateOp constPred = (ConstantPredicateOp)caseOpNode.Children[i].Op;
// Create the newArgs list, if we haven't done so already
if (newNodeArgs == null)
{
newNodeArgs = new List();
for (int j = 0; j < i; j++)
{
newNodeArgs.Add(caseOpNode.Children[j]);
}
}
// If the when-clause is the "true" predicate, then we simply ignore all
// the succeeding arguments. We make the "then" clause of this when-clause
// as the "else-clause" of the resulting caseOp
if (constPred.IsTrue)
{
newNodeArgs.Add(caseOpNode.Children[i + 1]);
break;
}
else
{
// Otherwise, we simply skip the when-then pair
PlanCompiler.Assert(constPred.IsFalse, "constant predicate must be either true or false");
i += 2;
continue;
}
}
// Did we see any changes? Simply return
if (newNodeArgs == null)
{
return false;
}
// Otherwise, we did do some processing
PlanCompiler.Assert(newNodeArgs.Count > 0, "new args list must not be empty");
// Is there only one expression in the args list - simply return that expression
if (newNodeArgs.Count == 1)
{
newNode = newNodeArgs[0];
}
else
{
newNode = context.Command.CreateNode(caseOp, newNodeArgs);
}
return true;
}
///
/// If the else clause of the CaseOp is another CaseOp, when two can be collapsed into one.
/// In particular,
///
/// CASE
/// WHEN W1 THEN T1
/// WHEN W2 THEN T2 ...
/// ELSE (CASE
/// WHEN WN1 THEN TN1, …
/// ELSE E)
///
/// Is transformed into
///
/// CASE
/// WHEN W1 THEN T1
/// WHEN W2 THEN T2 ...
/// WHEN WN1 THEN TN1 ...
/// ELSE E
///
/// the current caseOp
/// current subtree
/// new subtree
/// true, if we performed a transformation
static bool ProcessFlattenCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
{
newNode = caseOpNode;
Node elseChild = caseOpNode.Children[caseOpNode.Children.Count - 1];
if (elseChild.Op.OpType != OpType.Case)
{
return false;
}
//
// Flatten the case statements.
// The else child is removed from the outer CaseOp op
// and the else child's children are reparented to the outer CaseOp
// Node info recomputation does not need to happen, the outer CaseOp
// node still has the same descendants.
//
caseOpNode.Children.RemoveAt(caseOpNode.Children.Count - 1);
caseOpNode.Children.AddRange(elseChild.Children);
return true;
}
#endregion
#region EqualsOverConstant Rules
internal static readonly PatternMatchRule Rule_EqualsOverConstant =
new PatternMatchRule(new Node(ComparisonOp.PatternEq,
new Node(InternalConstantOp.Pattern),
new Node(InternalConstantOp.Pattern)),
ProcessComparisonsOverConstant);
///
/// Convert an Equals(X, Y) to a "true" predicate if X=Y, or a "false" predicate if X!=Y
/// Convert a NotEquals(X,Y) in the reverse fashion
///
/// Rule processing context
/// current node
/// possibly modified subtree
/// true, if transformation was successful
static bool ProcessComparisonsOverConstant(RuleProcessingContext context, Node node, out Node newNode)
{
newNode = node;
PlanCompiler.Assert(node.Op.OpType == OpType.EQ || node.Op.OpType == OpType.NE, "unexpected comparison op type?");
bool? comparisonStatus = node.Child0.Op.IsEquivalent(node.Child1.Op);
// Don't mess with nulls or with non-internal constants
if (comparisonStatus == null)
{
return false;
}
bool result = (node.Op.OpType == OpType.EQ) ? (bool)comparisonStatus : !((bool)comparisonStatus);
ConstantPredicateOp newOp = context.Command.CreateConstantPredicateOp(result);
newNode = context.Command.CreateNode(newOp);
return true;
}
#endregion
#region LikeOp Rules
private static bool? MatchesPattern(string str, string pattern)
{
// What we're trying to see is if the pattern is something that ends with a '%'
// And if the "str" is something that matches everything before that
// Make sure that the terminal character of the pattern is a '%' character. Also
// ensure that this character does not occur anywhere else. And finally, ensure
// that the pattern is atmost one character longer than the string itself
int wildCardIndex = pattern.IndexOf('%');
if ((wildCardIndex == -1) ||
(wildCardIndex != pattern.Length - 1) ||
(pattern.Length > str.Length + 1))
{
return null;
}
bool match = true;
int i = 0;
for (i = 0; i < str.Length && i < pattern.Length - 1; i++)
{
if (pattern[i] != str[i])
{
match = false;
break;
}
}
return match;
}
internal static readonly PatternMatchRule Rule_LikeOverConstants =
new PatternMatchRule(new Node(LikeOp.Pattern,
new Node(InternalConstantOp.Pattern),
new Node(InternalConstantOp.Pattern),
new Node(NullOp.Pattern)),
ProcessLikeOverConstant);
static bool ProcessLikeOverConstant(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
InternalConstantOp patternOp = (InternalConstantOp)n.Child1.Op;
InternalConstantOp strOp = (InternalConstantOp)n.Child0.Op;
string str = (string)strOp.Value;
string pattern = (string)patternOp.Value;
bool? match = MatchesPattern((string)strOp.Value, (string)patternOp.Value);
if (match == null)
{
return false;
}
ConstantPredicateOp constOp = context.Command.CreateConstantPredicateOp((bool)match);
newNode = context.Command.CreateNode(constOp);
return true;
}
#endregion
#region LogicalOp (and,or,not) Rules
internal static readonly PatternMatchRule Rule_AndOverConstantPred1 =
new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern)),
ProcessAndOverConstantPredicate1);
internal static readonly PatternMatchRule Rule_AndOverConstantPred2 =
new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
new Node(ConstantPredicateOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessAndOverConstantPredicate2);
internal static readonly PatternMatchRule Rule_OrOverConstantPred1 =
new PatternMatchRule(new Node(ConditionalOp.PatternOr,
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern)),
ProcessOrOverConstantPredicate1);
internal static readonly PatternMatchRule Rule_OrOverConstantPred2 =
new PatternMatchRule(new Node(ConditionalOp.PatternOr,
new Node(ConstantPredicateOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessOrOverConstantPredicate2);
internal static readonly PatternMatchRule Rule_NotOverConstantPred =
new PatternMatchRule(new Node(ConditionalOp.PatternNot,
new Node(ConstantPredicateOp.Pattern)),
ProcessNotOverConstantPredicate);
///
/// Transform
/// AND(x, true) => x;
/// AND(true, x) => x
/// AND(x, false) => false
/// AND(false, x) => false
///
///
/// Rule Processing context
/// Current LogOp (And, Or, Not) node
/// constant predicate node
/// The other child of the LogOp (possibly null)
/// new subtree
/// transformation status
static bool ProcessLogOpOverConstant(RuleProcessingContext context, Node node,
Node constantPredicateNode, Node otherNode,
out Node newNode)
{
PlanCompiler.Assert(constantPredicateNode != null, "null constantPredicateOp?");
ConstantPredicateOp pred = (ConstantPredicateOp)constantPredicateNode.Op;
switch (node.Op.OpType)
{
case OpType.And:
newNode = pred.IsTrue ? otherNode : constantPredicateNode;
break;
case OpType.Or:
newNode = pred.IsTrue ? constantPredicateNode : otherNode;
break;
case OpType.Not:
PlanCompiler.Assert(otherNode == null, "Not Op with more than 1 child. Gasp!");
newNode = context.Command.CreateNode(context.Command.CreateConstantPredicateOp(!pred.Value));
break;
default:
PlanCompiler.Assert(false, "Unexpected OpType - " + node.Op.OpType);
newNode = null;
break;
}
return true;
}
static bool ProcessAndOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
}
static bool ProcessAndOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
}
static bool ProcessOrOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
}
static bool ProcessOrOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
}
static bool ProcessNotOverConstantPredicate(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child0, null, out newNode);
}
#endregion
#region IsNull Rules
internal static readonly PatternMatchRule Rule_IsNullOverConstant =
new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
new Node(InternalConstantOp.Pattern)),
ProcessIsNullOverConstant);
internal static readonly PatternMatchRule Rule_IsNullOverNullSentinel =
new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
new Node(NullSentinelOp.Pattern)),
ProcessIsNullOverConstant);
///
/// Convert a
/// IsNull(constant)
/// to just the
/// False predicate
///
///
///
/// new subtree
///
/// Convert an IsNull(null) to just the 'true' predicate
///
///
///
/// new subtree
///
/// eliminates nested null casts into a single cast of the outermost cast type.
/// basically the transformation applied is: cast(null[x] as T) => null[t]
///
///
///
/// modified subtree
///
/// Convert a
/// IsNull(VarRef(v))
/// to just the
/// False predicate
///
/// if v is guaranteed to be non nullable.
///
///
///
/// new subtree
///
/// Transformation rules for FilterOps
///
internal static class FilterOpRules
{
#region Helpers
///
/// Split up a predicate into 2 parts - the pushdown and the non-pushdown predicate.
///
/// If the filter node has no external references *and* the "columns" parameter is null,
/// then the entire predicate can be pushed down
///
/// We then compute the set of valid column references - if the "columns" parameter
/// is non-null, this set is used. Otherwise, we get the definitions of the
/// input relop node of the filterOp, and use that.
///
/// We use this list of valid column references to identify which parts of the filter
/// predicate can be pushed down - only those parts of the predicate that do not
/// reference anything beyond these columns are considered for pushdown. The rest are
/// stuffed into the nonPushdownPredicate output parameter
///
///
/// Command object
/// the FilterOp subtree
/// (Optional) List of columns to consider for "pushdown"
/// (output) Part of the predicate that cannot be pushed down
/// part of the predicate that can be pushed down
private static Node GetPushdownPredicate(Command command, Node filterNode, VarVec columns, out Node nonPushdownPredicateNode)
{
Node pushdownPredicateNode = filterNode.Child1;
nonPushdownPredicateNode = null;
ExtendedNodeInfo filterNodeInfo = command.GetExtendedNodeInfo(filterNode);
if (columns == null && filterNodeInfo.ExternalReferences.IsEmpty)
{
return pushdownPredicateNode;
}
if (columns == null)
{
ExtendedNodeInfo inputNodeInfo = command.GetExtendedNodeInfo(filterNode.Child0);
columns = inputNodeInfo.Definitions;
}
Predicate predicate = new Predicate(command, pushdownPredicateNode);
Predicate nonPushdownPredicate;
predicate = predicate.GetSingleTablePredicates(columns, out nonPushdownPredicate);
pushdownPredicateNode = predicate.BuildAndTree();
nonPushdownPredicateNode = nonPushdownPredicate.BuildAndTree();
return pushdownPredicateNode;
}
#endregion
#region FilterOverFilter
internal static readonly PatternMatchRule Rule_FilterOverFilter =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverFilter);
///
/// Convert Filter(Filter(X, p1), p2) => Filter(X, (p1 and p2))
///
/// rule processing context
/// FilterOp node
/// modified subtree
/// transformed subtree
static bool ProcessFilterOverFilter(RuleProcessingContext context, Node filterNode, out Node newNode)
{
Node newAndNode = context.Command.CreateNode(
context.Command.CreateConditionalOp(OpType.And),
filterNode.Child0.Child1, filterNode.Child1);
newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), filterNode.Child0.Child0, newAndNode);
return true;
}
#endregion
#region FilterOverProject
internal static readonly PatternMatchRule Rule_FilterOverProject =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverProject);
///
/// Convert Filter(Project(X, ...), p) => Project(Filter(X, p'), ...)
///
/// Rule processing context
/// FilterOp subtree
/// modified subtree
/// transformed subtree
static bool ProcessFilterOverProject(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
Node predicateNode = filterNode.Child1;
//
// If the filter is a constant predicate, then don't push the filter below the
// project
//
if (predicateNode.Op.OpType == OpType.ConstantPredicate)
{
// There's a different rule to process this case. Simply return
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
//
// check to see that this is a simple predicate
//
Dictionary varRefMap = new Dictionary();
if (!trc.IsScalarOpTree(predicateNode, varRefMap))
{
return false;
}
//
// check to see if all expressions in the project can be inlined
//
Node projectNode = filterNode.Child0;
Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
if (varMap == null)
{
return false;
}
//
// Try to remap the predicate in terms of the definitions of the Vars
//
Node remappedPredicateNode = trc.ReMap(predicateNode, varMap);
//
// Now push the filter below the project
//
Node newFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), projectNode.Child0, remappedPredicateNode);
Node newProjectNode = trc.Command.CreateNode(projectNode.Op, newFilterNode, projectNode.Child1);
newNode = newProjectNode;
return true;
}
#endregion
#region FilterOverSetOp
internal static readonly PatternMatchRule Rule_FilterOverUnionAll =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(UnionAllOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverSetOp);
internal static readonly PatternMatchRule Rule_FilterOverIntersect =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(IntersectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverSetOp);
internal static readonly PatternMatchRule Rule_FilterOverExcept =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(ExceptOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverSetOp);
///
/// Transform Filter(UnionAll(X1, X2), p) => UnionAll(Filter(X1, p1), Filter(X, p2))
/// Filter(Intersect(X1, X2), p) => Intersect(Filter(X1, p1), Filter(X2, p2))
/// Filter(Except(X1, X2), p) => Except(Filter(X1, p1), X2)
/// where p1 and p2 are the "mapped" versions of the predicate "p" for each branch
///
/// Rule processing context
/// FilterOp subtree
/// modified subtree
/// true, if successful transformation
static bool ProcessFilterOverSetOp(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
//
// Identify parts of the filter predicate that can be pushed down, and parts that
// cannot be. If nothing can be pushed down, then return
//
Node nonPushdownPredicate;
Node pushdownPredicate = GetPushdownPredicate(trc.Command, filterNode, null, out nonPushdownPredicate);
if (pushdownPredicate == null)
{
return false;
}
// Handle only simple predicates
if (!trc.IsScalarOpTree(pushdownPredicate))
{
return false;
}
//
// Now push the predicate (the part that can be pushed down) into each of the
// branches (as appropriate)
//
Node setOpNode = filterNode.Child0;
SetOp setOp = (SetOp)setOpNode.Op;
List newSetOpChildren = new List();
int branchId = 0;
foreach (VarMap varMap in setOp.VarMap)
{
// For exceptOp, the filter should only be pushed below the zeroth child
if (setOp.OpType == OpType.Except && branchId == 1)
{
newSetOpChildren.Add(setOpNode.Child1);
break;
}
Dictionary remapMap = new Dictionary();
foreach (KeyValuePair kv in varMap)
{
Node varRefNode = trc.Command.CreateNode(trc.Command.CreateVarRefOp(kv.Value));
remapMap.Add(kv.Key, varRefNode);
}
//
// Now fix up the predicate.
// Make a copy of the predicate first - except if we're dealing with the last
// branch, in which case, we can simply reuse the predicate
//
Node predicateNode = pushdownPredicate;
if (branchId == 0 && filterNode.Op.OpType != OpType.Except)
{
predicateNode = trc.Copy(predicateNode);
}
Node newPredicateNode = trc.ReMap(predicateNode, remapMap);
trc.Command.RecomputeNodeInfo(newPredicateNode);
// create a new filter node below the setOp child
Node newFilterNode = trc.Command.CreateNode(
trc.Command.CreateFilterOp(),
setOpNode.Children[branchId],
newPredicateNode);
newSetOpChildren.Add(newFilterNode);
branchId++;
}
Node newSetOpNode = trc.Command.CreateNode(setOpNode.Op, newSetOpChildren);
//
// We've now pushed down the relevant parts of the filter below the SetOps
// We may still however some predicates left over - create a new filter node
// to account for that
//
if (nonPushdownPredicate != null)
{
newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newSetOpNode, nonPushdownPredicate);
}
else
{
newNode = newSetOpNode;
}
return true;
}
#endregion
#region FilterOverDistinct
internal static readonly PatternMatchRule Rule_FilterOverDistinct =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(DistinctOp.Pattern,
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverDistinct);
///
/// Transforms Filter(Distinct(x), p) => Filter(Distinct(Filter(X, p1), p2)
/// where p2 is the part of the filter that can be pushed down, while p1 represents
/// any external references
///
/// Rule processing context
/// FilterOp subtree
/// modified subtree
/// Transformation status
static bool ProcessFilterOverDistinct(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
//
// Split up the filter predicate into two parts - the part that can be pushed down
// and the part that can't. If there is no part that can be pushed down, simply return
//
Node nonPushdownPredicate;
Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, null, out nonPushdownPredicate);
if (pushdownPredicate == null)
{
return false;
}
//
// Create a new filter node below the current distinct node for the predicate
// that can be pushed down - create a new distinct node as well
//
Node distinctNode = filterNode.Child0;
Node pushdownFilterNode = context.Command.CreateNode(context.Command.CreateFilterOp(), distinctNode.Child0, pushdownPredicate);
Node newDistinctNode = context.Command.CreateNode(distinctNode.Op, pushdownFilterNode);
//
// If we have a predicate part that cannot be pushed down, build up a new
// filter node above the new Distinct op that we just created
//
if (nonPushdownPredicate != null)
{
newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), newDistinctNode, nonPushdownPredicate);
}
else
{
newNode = newDistinctNode;
}
return true;
}
#endregion
#region FilterOverGroupBy
internal static readonly PatternMatchRule Rule_FilterOverGroupBy =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(GroupByOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverGroupBy);
///
/// Transforms Filter(GroupBy(X, k1.., a1...), p) =>
/// Filter(GroupBy(Filter(X, p1'), k1..., a1...), p2)
/// p1 and p2 represent the parts of p that can and cannot be pushed down
/// respectively - specifically, p1 must only reference the key columns from
/// the GroupByOp.
/// "p1'" is the mapped version of "p1",
///
/// Rule processing context
/// Current FilterOp subtree
/// modified subtree
/// Transformation status
static bool ProcessFilterOverGroupBy(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
Node groupByNode = filterNode.Child0;
GroupByOp groupByOp = (GroupByOp)groupByNode.Op;
TransformationRulesContext trc = (TransformationRulesContext)context;
// Check to see that we have a simple predicate
Dictionary varRefMap = new Dictionary();
if (!trc.IsScalarOpTree(filterNode.Child1, varRefMap))
{
return false;
}
//
// Split up the predicate into two parts - the part that can be pushed down below
// the groupByOp (specifically, the part that only refers to keys of the groupByOp),
// and the part that cannot be pushed below
// If nothing can be pushed below, quit now
//
Node nonPushdownPredicate;
Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, groupByOp.Keys, out nonPushdownPredicate);
if (pushdownPredicate == null)
{
return false;
}
//
// We need to push the filter down; but we need to remap the predicate, so
// that any references to variables defined locally by the groupBy are fixed up
// Make sure that the predicate is not too complex to remap
//
Dictionary varMap = trc.GetVarMap(groupByNode.Child1, varRefMap);
if (varMap == null)
{
return false; // complex expressions
}
Node remappedPushdownPredicate = trc.ReMap(pushdownPredicate, varMap);
//
// Push the filter below the groupBy now
//
Node subFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), groupByNode.Child0, remappedPushdownPredicate);
Node newGroupByNode = trc.Command.CreateNode(groupByNode.Op, subFilterNode, groupByNode.Child1, groupByNode.Child2);
//
// If there was any part of the original predicate that could not be pushed down,
// create a new filterOp node above the new groupBy node to represent that
// predicate
//
if (nonPushdownPredicate == null)
{
newNode = newGroupByNode;
}
else
{
newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newGroupByNode, nonPushdownPredicate);
}
return true;
}
#endregion
#region FilterOverJoin
internal static readonly PatternMatchRule Rule_FilterOverCrossJoin =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverJoin);
internal static readonly PatternMatchRule Rule_FilterOverInnerJoin =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(InnerJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverJoin);
internal static readonly PatternMatchRule Rule_FilterOverLeftOuterJoin =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(LeftOuterJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverJoin);
///
/// Transform Filter()
///
/// Rule Processing context
/// Current FilterOp subtree
/// Modified subtree
/// Transformation status
static bool ProcessFilterOverJoin(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
//
// Have we shut off filter pushdown for this node? Return
//
if (trc.IsFilterPushdownSuppressed(filterNode))
{
return false;
}
Node joinNode = filterNode.Child0;
Op joinOp = joinNode.Op;
Node leftInputNode = joinNode.Child0;
Node rightInputNode = joinNode.Child1;
Command command = trc.Command;
bool needsTransformation = false;
//
// If we're dealing with an outer-join, first check to see if the current
// predicate preserves nulls for the right table.
// If it doesn't then we can convert the outer join into an inner join,
// and then continue with the rest of our processing here
//
ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(rightInputNode);
Predicate predicate = new Predicate(command, filterNode.Child1);
if (joinOp.OpType == OpType.LeftOuterJoin)
{
if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
{
joinOp = command.CreateInnerJoinOp();
needsTransformation = true;
}
}
ExtendedNodeInfo leftTableInfo = command.GetExtendedNodeInfo(leftInputNode);
//
// Check to see if the predicate contains any "single-table-filters". In those
// cases, we could simply push that filter down to the child.
// We can do this for inner joins and cross joins - for both inputs.
// For left-outer joins, however, we can only do this for the left-side input
// Further note that we only want to do the pushdown if it will help us - if
// the join input is a ScanTable (or some other cases), then it doesn't help us.
//
Node leftSingleTablePredicateNode = null;
if (leftInputNode.Op.OpType != OpType.ScanTable)
{
Predicate leftSingleTablePredicates = predicate.GetSingleTablePredicates(leftTableInfo.Definitions, out predicate);
leftSingleTablePredicateNode = leftSingleTablePredicates.BuildAndTree();
}
Node rightSingleTablePredicateNode = null;
if ((rightInputNode.Op.OpType != OpType.ScanTable) &&
(joinOp.OpType != OpType.LeftOuterJoin))
{
Predicate rightSingleTablePredicates = predicate.GetSingleTablePredicates(rightTableNodeInfo.Definitions, out predicate);
rightSingleTablePredicateNode = rightSingleTablePredicates.BuildAndTree();
}
//
// Now check to see if the predicate contains some "join predicates". We can
// add these to the existing join predicate (if any).
// We can only do this for inner joins and cross joins - not for LOJs
//
Node newJoinPredicateNode = null;
if (joinOp.OpType == OpType.CrossJoin || joinOp.OpType == OpType.InnerJoin)
{
Predicate joinPredicate = predicate.GetJoinPredicates(leftTableInfo.Definitions, rightTableNodeInfo.Definitions, out predicate);
newJoinPredicateNode = joinPredicate.BuildAndTree();
}
//
// Now for the dirty work. We've identified some predicates that could be pushed
// into the left table, some predicates that could be pushed into the right table
// and some that could become join predicates.
//
if (leftSingleTablePredicateNode != null)
{
leftInputNode = command.CreateNode(command.CreateFilterOp(), leftInputNode, leftSingleTablePredicateNode);
needsTransformation = true;
}
if (rightSingleTablePredicateNode != null)
{
rightInputNode = command.CreateNode(command.CreateFilterOp(), rightInputNode, rightSingleTablePredicateNode);
needsTransformation = true;
}
// Identify the new join predicate
if (newJoinPredicateNode != null)
{
needsTransformation = true;
if (joinOp.OpType == OpType.CrossJoin)
{
joinOp = command.CreateInnerJoinOp();
}
else
{
PlanCompiler.Assert(joinOp.OpType == OpType.InnerJoin, "unexpected non-InnerJoin?");
newJoinPredicateNode = PlanCompilerUtil.CombinePredicates(joinNode.Child2, newJoinPredicateNode, command);
}
}
else
{
newJoinPredicateNode = (joinOp.OpType == OpType.CrossJoin) ? null : joinNode.Child2;
}
//
// If nothing has changed, then just return the current node. Otherwise,
// we will loop forever
//
if (!needsTransformation)
{
return false;
}
Node newJoinNode;
//
// Finally build up a new join node
//
if (joinOp.OpType == OpType.CrossJoin)
{
newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode);
}
else
{
newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode, newJoinPredicateNode);
}
//
// Build up a new filterNode above this join node. But only if we have a filter left
//
Node newFilterPredicateNode = predicate.BuildAndTree();
if (newFilterPredicateNode == null)
{
newNode = newJoinNode;
}
else
{
newNode = command.CreateNode(command.CreateFilterOp(), newJoinNode, newFilterPredicateNode);
}
return true;
}
#endregion
#region Filter over OuterApply
internal static readonly PatternMatchRule Rule_FilterOverOuterApply =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverOuterApply);
///
/// Convert Filter(OuterApply(X,Y), p) into
/// Filter(CrossApply(X,Y), p)
/// if "p" is not null-preserving for Y (ie) "p" does not preserve null values from Y
///
/// Rule processing context
/// Filter node
/// modified subtree
/// transformation status
static bool ProcessFilterOverOuterApply(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
Node applyNode = filterNode.Child0;
Op applyOp = applyNode.Op;
Node applyRightInputNode = applyNode.Child1;
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
//
// Check to see if the current predicate preserves nulls for the right table.
// If it doesn't then we can convert the outer apply into a cross-apply,
//
ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(applyRightInputNode);
Predicate predicate = new Predicate(command, filterNode.Child1);
if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
{
Node newApplyNode = command.CreateNode(command.CreateCrossApplyOp(), applyNode.Child0, applyRightInputNode);
Node newFilterNode = command.CreateNode(command.CreateFilterOp(), newApplyNode, filterNode.Child1);
newNode = newFilterNode;
return true;
}
return false;
}
#endregion
#region FilterWithConstantPredicate
internal static readonly PatternMatchRule Rule_FilterWithConstantPredicate =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern)),
ProcessFilterWithConstantPredicate);
///
/// Convert
/// Filter(X, true) => X
/// Filter(X, false) => Project(Filter(SingleRowTableOp, ...), false)
/// where ... represent variables that are equivalent to the table columns
///
/// Rule processing context
/// Current subtree
/// modified subtree
/// transformation status
static bool ProcessFilterWithConstantPredicate(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
ConstantPredicateOp predOp = (ConstantPredicateOp)n.Child1.Op;
// If we're dealing with a "true" predicate, then simply return the RelOp
// input to the filter
if (predOp.IsTrue)
{
newNode = n.Child0;
return true;
}
PlanCompiler.Assert(predOp.IsFalse, "unexpected non-false predicate?");
// We're dealing with a "false" predicate, then we can get rid of the
// input, and replace it with a dummy project
//
// If the input is already a singlerowtableOp, then there's nothing
// further to do
//
if (n.Child0.Op.OpType == OpType.SingleRowTable ||
(n.Child0.Op.OpType == OpType.Project &&
n.Child0.Child0.Op.OpType == OpType.SingleRowTable))
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
ExtendedNodeInfo childNodeInfo = trc.Command.GetExtendedNodeInfo(n.Child0);
List varDefNodeList = new List();
VarVec newVars = trc.Command.CreateVarVec();
foreach (Var v in childNodeInfo.Definitions)
{
NullOp nullConst = trc.Command.CreateNullOp(v.Type);
Node constNode = trc.Command.CreateNode(nullConst);
Var computedVar;
Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
trc.AddVarMapping(v, computedVar);
newVars.Set(computedVar);
varDefNodeList.Add(varDefNode);
}
// If no vars have been selected out, add a dummy var
if (newVars.IsEmpty)
{
NullOp nullConst = trc.Command.CreateNullOp(trc.Command.BooleanType);
Node constNode = trc.Command.CreateNode(nullConst);
Var computedVar;
Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
newVars.Set(computedVar);
varDefNodeList.Add(varDefNode);
}
Node singleRowTableNode = trc.Command.CreateNode(trc.Command.CreateSingleRowTableOp());
n.Child0 = singleRowTableNode;
Node varDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp(), varDefNodeList);
ProjectOp projectOp = trc.Command.CreateProjectOp(newVars);
Node projectNode = trc.Command.CreateNode(projectOp, n, varDefListNode);
projectNode.Child0 = n;
newNode = projectNode;
return true;
}
#endregion
#region All FilterOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
FilterOpRules.Rule_FilterWithConstantPredicate,
FilterOpRules.Rule_FilterOverCrossJoin,
FilterOpRules.Rule_FilterOverDistinct,
FilterOpRules.Rule_FilterOverExcept,
FilterOpRules.Rule_FilterOverFilter,
FilterOpRules.Rule_FilterOverGroupBy,
FilterOpRules.Rule_FilterOverInnerJoin,
FilterOpRules.Rule_FilterOverIntersect,
FilterOpRules.Rule_FilterOverLeftOuterJoin,
FilterOpRules.Rule_FilterOverProject,
FilterOpRules.Rule_FilterOverUnionAll,
FilterOpRules.Rule_FilterOverOuterApply,
};
#endregion
}
#endregion
#region Project Rules
///
/// Transformation rules for ProjectOp
///
internal static class ProjectOpRules
{
#region ProjectOverProject
internal static readonly PatternMatchRule Rule_ProjectOverProject =
new PatternMatchRule(new Node(ProjectOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessProjectOverProject);
///
/// Converts a Project(Project(X, c1,...), d1,...) =>
/// Project(X, d1', d2'...)
/// where d1', d2' etc. are the "mapped" versions of d1, d2 etc.
///
/// Rule processing context
/// Current ProjectOp node
/// modified subtree
/// Transformation status
static bool ProcessProjectOverProject(RuleProcessingContext context, Node projectNode, out Node newNode)
{
newNode = projectNode;
ProjectOp projectOp = (ProjectOp)projectNode.Op;
Node varDefListNode = projectNode.Child1;
Node subProjectNode = projectNode.Child0;
ProjectOp subProjectOp = (ProjectOp)subProjectNode.Op;
TransformationRulesContext trc = (TransformationRulesContext)context;
// If any of the defining expressions is not a scalar op tree, then simply
// quit
Dictionary varRefMap = new Dictionary();
foreach (Node varDefNode in varDefListNode.Children)
{
if (!trc.IsScalarOpTree(varDefNode.Child0, varRefMap))
{
return false;
}
}
Dictionary varMap = trc.GetVarMap(subProjectNode.Child1, varRefMap);
if (varMap == null)
{
return false;
}
// create a new varDefList node...
Node newVarDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp());
// Remap any local definitions, I have
foreach (Node varDefNode in varDefListNode.Children)
{
// update the defining expression
varDefNode.Child0 = trc.ReMap(varDefNode.Child0, varMap);
trc.Command.RecomputeNodeInfo(varDefNode);
newVarDefListNode.Children.Add(varDefNode);
}
// Now, pull up any definitions of the subProject that I publish myself
ExtendedNodeInfo projectNodeInfo = trc.Command.GetExtendedNodeInfo(projectNode);
foreach (Node chi in subProjectNode.Child1.Children)
{
VarDefOp varDefOp = (VarDefOp)chi.Op;
if (projectNodeInfo.Definitions.IsSet(varDefOp.Var))
{
newVarDefListNode.Children.Add(chi);
}
}
//
// now that we have remapped all our computed vars, simply bypass the subproject
// node
//
projectNode.Child0 = subProjectNode.Child0;
projectNode.Child1 = newVarDefListNode;
return true;
}
#endregion
#region ProjectWithNoLocalDefinitions
internal static readonly PatternMatchRule Rule_ProjectWithNoLocalDefs =
new PatternMatchRule(new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(VarDefListOp.Pattern)),
ProcessProjectWithNoLocalDefinitions);
///
/// Eliminate a ProjectOp that has no local definitions at all and
/// no external references, (ie) if Child1
/// of the ProjectOp (the VarDefListOp child) has no children, then the ProjectOp
/// is serving no useful purpose. Get rid of the ProjectOp, and replace it with its
/// child
///
/// rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessProjectWithNoLocalDefinitions(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
NodeInfo nodeInfo = context.Command.GetNodeInfo(n);
// We cannot eliminate this node because it can break other rules,
// e.g. ProcessApplyOverAnything which relies on existance of external refs to substitute
// CrossApply(x, y) => CrossJoin(x, y). See SQLBU #481719.
if (!nodeInfo.ExternalReferences.IsEmpty)
{
return false;
}
newNode = n.Child0;
return true;
}
#endregion
#region ProjectOpWithSimpleVarRedefinitions
internal static readonly SimpleRule Rule_ProjectOpWithSimpleVarRedefinitions = new SimpleRule(OpType.Project, ProcessProjectWithSimpleVarRedefinitions);
///
/// If the ProjectOp defines some computedVars, but those computedVars are simply
/// redefinitions of other Vars, then eliminate the computedVars.
///
/// Project(X, VarDefList(VarDef(cv1, VarRef(v1)), ...))
/// can be transformed into
/// Project(X, VarDefList(...))
/// where cv1 has now been replaced by v1
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessProjectWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
ProjectOp projectOp = (ProjectOp)n.Op;
if (n.Child1.Children.Count == 0)
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
//
// Check to see if any of the computed Vars defined by this ProjectOp
// are simple redefinitions of other VarRefOps. Consider only those
// VarRefOps that are not "external" references
bool canEliminateSomeVars = false;
foreach (Node varDefNode in n.Child1.Children)
{
Node definingExprNode = varDefNode.Child0;
if (definingExprNode.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
// this is a Var that we should remove
canEliminateSomeVars = true;
break;
}
}
}
// Did we have any redefinitions
if (!canEliminateSomeVars)
{
return false;
}
//
// OK. We've now identified a set of vars that are simple redefinitions.
// Try and replace the computed Vars with the Vars that they're redefining
//
// Lets now build up a new VarDefListNode
List newVarDefNodes = new List();
foreach (Node varDefNode in n.Child1.Children)
{
VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
projectOp.Outputs.Clear(varDefOp.Var);
projectOp.Outputs.Set(varRefOp.Var);
trc.AddVarMapping(varDefOp.Var, varRefOp.Var);
}
else
{
newVarDefNodes.Add(varDefNode);
}
}
// Note: Even if we don't have any local var definitions left, we should not remove
// this project yet because:
// (1) this project node may be prunning out some outputs;
// (2) the rule Rule_ProjectWithNoLocalDefs, would do that later anyway.
// Create a new vardeflist node, and set that as Child1 for the projectOp
Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
n.Child1 = newVarDefListNode;
return true; // some part of the subtree was modified
}
#endregion
#region ProjectOpWithNullSentinel
internal static readonly SimpleRule Rule_ProjectOpWithNullSentinel = new SimpleRule(OpType.Project, ProcessProjectOpWithNullSentinel);
///
/// Tries to remove null sentinel definitions by replacing them to vars that are guaranteed
/// to be non-nullable and of integer type, or with reference to other constants defined in the
/// same project. In particular,
///
/// - If based on the ancestors, the value of the null sentinel can be changed and the
/// input of the project has a var that is guaranteed to be non-nullable and
/// is of integer type, then the definitions of the vars defined as NullSentinels in the ProjectOp
/// are replaced with a reference to that var. I.eg:
///
/// Project(X, VarDefList(VarDef(ns_var, NullSentinel), ...))
/// can be transformed into
/// Project(X, VarDefList(VarDef(ns_var, VarRef(v))...))
/// where v is known to be non-nullable
///
/// - Else, if based on the ancestors, the value of the null sentinel can be changed and
/// the project already has definitions of other int constants, the definitions of the null sentinels
/// are removed and the respective vars are remapped to the var representing the constant.
///
/// - Else, the definitions of the all null sentinels except for one are removed, and the
/// the respective vars are remapped to the remaining null sentinel.
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessProjectOpWithNullSentinel(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
ProjectOp projectOp = (ProjectOp)n.Op;
Node varDefListNode = n.Child1;
if (varDefListNode.Children.Where(c => c.Child0.Op.OpType == OpType.NullSentinel).Count() == 0)
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
ExtendedNodeInfo relOpInputNodeInfo = command.GetExtendedNodeInfo(n.Child0);
Var inputSentinel;
bool reusingConstantFromSameProjectAsSentinel = false;
bool canChangeNullSentinelValue = trc.CanChangeNullSentinelValue;
if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(relOpInputNodeInfo.NonNullableDefinitions, out inputSentinel))
{
reusingConstantFromSameProjectAsSentinel = true;
if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.Constant || child.Child0.Op.OpType == OpType.InternalConstant).Select(child => ((VarDefOp)(child.Op)).Var), out inputSentinel))
{
inputSentinel = n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.NullSentinel).Select(child => ((VarDefOp)(child.Op)).Var).FirstOrDefault();
if (inputSentinel == null)
{
return false;
}
}
}
bool modified = false;
for (int i = n.Child1.Children.Count-1; i >= 0; i--)
{
Node varDefNode = n.Child1.Children[i];
Node definingExprNode = varDefNode.Child0;
if (definingExprNode.Op.OpType == OpType.NullSentinel)
{
if (!reusingConstantFromSameProjectAsSentinel)
{
VarRefOp varRefOp = command.CreateVarRefOp(inputSentinel);
varDefNode.Child0 = command.CreateNode(varRefOp);
command.RecomputeNodeInfo(varDefNode);
modified = true;
}
else if (!inputSentinel.Equals(((VarDefOp)varDefNode.Op).Var))
{
projectOp.Outputs.Clear(((VarDefOp)varDefNode.Op).Var);
n.Child1.Children.RemoveAt(i);
trc.AddVarMapping(((VarDefOp)varDefNode.Op).Var, inputSentinel);
modified = true;
}
}
}
if (modified)
{
command.RecomputeNodeInfo(n.Child1);
}
return modified;
}
#endregion
#region All ProjectOp Rules
//The order of the rules is important
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
ProjectOpRules.Rule_ProjectOpWithNullSentinel,
ProjectOpRules.Rule_ProjectOpWithSimpleVarRedefinitions,
ProjectOpRules.Rule_ProjectOverProject,
ProjectOpRules.Rule_ProjectWithNoLocalDefs,
};
#endregion
}
#endregion
#region Apply Rules
///
/// Transformation rules for ApplyOps - CrossApply, OuterApply
///
internal static class ApplyOpRules
{
#region ApplyOverFilter
internal static readonly PatternMatchRule Rule_CrossApplyOverFilter =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessApplyOverFilter);
internal static readonly PatternMatchRule Rule_OuterApplyOverFilter =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessApplyOverFilter);
///
/// Convert CrossApply(X, Filter(Y, p)) => InnerJoin(X, Y, p)
/// OuterApply(X, Filter(Y, p)) => LeftOuterJoin(X, Y, p)
/// if "Y" has no external references to X
///
/// Rule processing context
/// Current ApplyOp
/// transformed subtree
/// Transformation status
static bool ProcessApplyOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node filterNode = applyNode.Child1;
Command command = context.Command;
NodeInfo filterInputNodeInfo = command.GetNodeInfo(filterNode.Child0);
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
//
// check to see if the inputNode to the FilterOp has any external references
// to the left child of the ApplyOp. If it does, we simply return, we
// can't do much more here
//
if (filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
{
return false;
}
//
// We've now gotten to the stage where the only external references (if any)
// are from the filter predicate.
// We can now simply convert the apply into an inner/leftouter join with the
// filter predicate acting as the join condition
//
JoinBaseOp joinOp = null;
if (applyNode.Op.OpType == OpType.CrossApply)
{
joinOp = command.CreateInnerJoinOp();
}
else
{
joinOp = command.CreateLeftOuterJoinOp();
}
newNode = command.CreateNode(joinOp, applyNode.Child0, filterNode.Child0, filterNode.Child1);
return true;
}
internal static readonly PatternMatchRule Rule_OuterApplyOverProjectInternalConstantOverFilter =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(VarDefListOp.Pattern,
new Node(VarDefOp.Pattern,
new Node(InternalConstantOp.Pattern))))),
ProcessOuterApplyOverDummyProjectOverFilter);
internal static readonly PatternMatchRule Rule_OuterApplyOverProjectNullSentinelOverFilter =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(VarDefListOp.Pattern,
new Node(VarDefOp.Pattern,
new Node(NullSentinelOp.Pattern))))),
ProcessOuterApplyOverDummyProjectOverFilter);
///
/// Convert OuterApply(X, Project(Filter(Y, p), constant)) =>
/// LeftOuterJoin(X, Project(Y, constant), p)
/// if "Y" has no external references to X
///
/// In an ideal world, we would be able to push the Project below the Filter,
/// and then have the normal ApplyOverFilter rule handle this - but that causes us
/// problems because we always try to pull up ProjectOp's as high as possible. Hence,
/// the special case for this rule
///
///
/// Rule processing context
/// Current ApplyOp
/// transformed subtree
/// Transformation status
static bool ProcessOuterApplyOverDummyProjectOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node projectNode = applyNode.Child1;
ProjectOp projectOp = (ProjectOp)projectNode.Op;
Node filterNode = projectNode.Child0;
Node filterInputNode = filterNode.Child0;
Command command = context.Command;
ExtendedNodeInfo filterInputNodeInfo = command.GetExtendedNodeInfo(filterInputNode);
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
//
// Check if the outputs of the ProjectOp or the inputNode to the FilterOp
// have any external references to the left child of the ApplyOp.
// If they do, we simply return, we can't do much more here
//
if (projectOp.Outputs.Overlaps(applyLeftChildNodeInfo.Definitions) || filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
{
return false;
}
//
// We've now gotten to the stage where the only external references (if any)
// are from the filter predicate.
// First, push the Project node down below the filter - but make sure that
// all the Vars needed by the Filter are projected out
//
bool capWithProject = false;
Node joinNodeRightInput = null;
//
// Check to see whether there is a sentinel var available - if there is, then
// we can simply move the ProjectOp above the join we're going to construct
// and of course, build a NullIf expression for the constant.
// Otherwise, the ProjectOp will need to be the child of the joinOp that we're
// building - and we'll need to make sure that the ProjectOp projects out
// any vars that are required for the Filter in the first place
//
TransformationRulesContext trc = (TransformationRulesContext)context;
Var sentinelVar;
bool sentinelIsInt32;
if (TransformationRulesContext.TryGetInt32Var(filterInputNodeInfo.NonNullableDefinitions, out sentinelVar))
{
sentinelIsInt32 = true;
}
else
{
sentinelVar = filterInputNodeInfo.NonNullableDefinitions.First;
sentinelIsInt32 = false;
}
if (sentinelVar != null)
{
capWithProject = true;
Node varDefNode = projectNode.Child1.Child0;
if (varDefNode.Child0.Op.OpType == OpType.NullSentinel && sentinelIsInt32 && trc.CanChangeNullSentinelValue)
{
varDefNode.Child0 = context.Command.CreateNode(context.Command.CreateVarRefOp(sentinelVar));
}
else
{
varDefNode.Child0 = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
}
command.RecomputeNodeInfo(varDefNode);
command.RecomputeNodeInfo(projectNode.Child1);
joinNodeRightInput = filterInputNode;
}
else
{
// We need to keep the projectNode - unfortunately
joinNodeRightInput = projectNode;
//
// Make sure that every Var that is needed for the filter predicate
// is captured in the projectOp outputs list
//
NodeInfo filterPredicateNodeInfo = command.GetNodeInfo(filterNode.Child1);
foreach (Var v in filterPredicateNodeInfo.ExternalReferences)
{
if (filterInputNodeInfo.Definitions.IsSet(v))
{
projectOp.Outputs.Set(v);
}
}
projectNode.Child0 = filterInputNode;
}
context.Command.RecomputeNodeInfo(projectNode);
//
// We can now simply convert the apply into an inner/leftouter join with the
// filter predicate acting as the join condition
//
Node joinNode = command.CreateNode(command.CreateLeftOuterJoinOp(), applyNode.Child0, joinNodeRightInput, filterNode.Child1);
if (capWithProject)
{
ExtendedNodeInfo joinNodeInfo = command.GetExtendedNodeInfo(joinNode);
projectNode.Child0 = joinNode;
projectOp.Outputs.Or(joinNodeInfo.Definitions);
newNode = projectNode;
}
else
{
newNode = joinNode;
}
return true;
}
#endregion
#region ApplyOverProject
internal static readonly PatternMatchRule Rule_CrossApplyOverProject =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessCrossApplyOverProject);
///
/// Converts a CrossApply(X, Project(Y, ...)) => Project(CrossApply(X, Y), ...)
/// where the projectVars are simply pulled up
///
/// RuleProcessing context
/// The ApplyOp subtree
/// transformed subtree
/// Transfomation status
static bool ProcessCrossApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node projectNode = applyNode.Child1;
ProjectOp projectOp = (ProjectOp)projectNode.Op as ProjectOp;
Command command = context.Command;
// We can simply pull up the project over the apply; provided we make sure
// that all the definitions of the apply are represented in the projectOp
ExtendedNodeInfo applyNodeInfo = command.GetExtendedNodeInfo(applyNode);
VarVec vec = command.CreateVarVec(projectOp.Outputs);
vec.Or(applyNodeInfo.Definitions);
projectOp.Outputs.InitFrom(vec);
// pull up the project over the apply node
applyNode.Child1 = projectNode.Child0;
context.Command.RecomputeNodeInfo(applyNode);
projectNode.Child0 = applyNode;
newNode = projectNode;
return true;
}
internal static readonly PatternMatchRule Rule_OuterApplyOverProject =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessOuterApplyOverProject);
///
/// Converts a
/// OuterApply(X, Project(Y, ...))
/// =>
/// Project(OuterApply(X, Project(Y, ...)), ...) or
/// Project(OuterApply(X, Y), ...)
///
/// The second (simpler) form is used if a "sentinel" var can be located (ie)
/// some Var of Y that is guaranteed to be non-null. Otherwise, we create a
/// dummy ProjectNode as the right child of the Apply - which
/// simply projects out all the vars of the Y, and adds on a constant (say "1"). This
/// constant is now treated as the sentinel var
///
/// Then the existing ProjectOp is pulled up above the the outer-apply, but all the locally defined
/// Vars have their defining expressions now expressed as
/// case when sentinelVar is null then null else oldDefiningExpr end
/// where oldDefiningExpr represents the original defining expression
/// This allows us to get nulls for the appropriate columns when necessary.
///
/// Special cases.
/// * If the oldDefiningExpr is itself an internal constant equivalent to the null sentinel ("1"),
/// we simply project a ref to the null sentinel, no need for cast
/// * If the ProjectOp contained exactly one locally defined Var, and it was a constant, then
/// we simply return - we will be looping endlessly otherwise
/// * If the ProjectOp contained no local definitions, then we don't need to create the
/// dummy projectOp - we can simply pull up the Project
/// * If any of the defining expressions of the local definitions was simply a VarRefOp
/// referencing a Var that was defined by Y, then there is no need to add the case
/// expression for that.
///
///
/// RuleProcessing context
/// The ApplyOp subtree
/// transformed subtree
/// Transfomation status
static bool ProcessOuterApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node projectNode = applyNode.Child1;
Node varDefListNode = projectNode.Child1;
TransformationRulesContext trc = (TransformationRulesContext)context;
ExtendedNodeInfo inputNodeInfo = context.Command.GetExtendedNodeInfo(projectNode.Child0);
Var sentinelVar = inputNodeInfo.NonNullableDefinitions.First;
//
// special case handling first - we'll end up in an infinite loop otherwise.
// If the ProjectOp is the dummy ProjectOp that we would be building (ie)
// it defines only 1 var - and the defining expression is simply a constant
//
if (sentinelVar == null &&
varDefListNode.Children.Count == 1 &&
(varDefListNode.Child0.Child0.Op.OpType == OpType.InternalConstant || varDefListNode.Child0.Child0.Op.OpType == OpType.NullSentinel))
{
return false;
}
Command command = context.Command;
Node dummyProjectNode = null;
InternalConstantOp nullSentinelDefinitionOp = null;
// get node information for the project's child
ExtendedNodeInfo projectInputNodeInfo = command.GetExtendedNodeInfo(projectNode.Child0);
//
// Build up a dummy project node.
// Walk through each local definition of the current project Node, and convert
// all expressions into case expressions whose value depends on the var
// produced by the dummy project node
//
// Dev10 #480443: If any of the definitions changes we need to recompute the node info.
bool anyVarDefChagned = false;
foreach (Node varDefNode in varDefListNode.Children)
{
PlanCompiler.Assert(varDefNode.Op.OpType == OpType.VarDef, "Expected VarDefOp. Found " + varDefNode.Op.OpType + " instead");
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp == null || !projectInputNodeInfo.Definitions.IsSet(varRefOp.Var))
{
// do we need to build a dummy project node
if (sentinelVar == null)
{
nullSentinelDefinitionOp = command.CreateInternalConstantOp(command.IntegerType, 1);
Node dummyConstantExpr = command.CreateNode(nullSentinelDefinitionOp);
Node dummyProjectVarDefListNode = command.CreateVarDefListNode(dummyConstantExpr, out sentinelVar);
ProjectOp dummyProjectOp = command.CreateProjectOp(sentinelVar);
dummyProjectOp.Outputs.Or(projectInputNodeInfo.Definitions);
dummyProjectNode = command.CreateNode(dummyProjectOp, projectNode.Child0, dummyProjectVarDefListNode);
}
Node currentDefinition;
// If the null sentinel was just created, and the local definition of the current project Node
// is an internal constant equivalent to the null sentinel, it can be rewritten as a reference
// to the null sentinel.
if (nullSentinelDefinitionOp != null && ((true == nullSentinelDefinitionOp.IsEquivalent(varDefNode.Child0.Op)) ||
//The null sentinel has the same value of 1, thus it is safe.
varDefNode.Child0.Op.OpType == OpType.NullSentinel))
{
currentDefinition = command.CreateNode(command.CreateVarRefOp(sentinelVar));
}
else
{
currentDefinition = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
}
varDefNode.Child0 = currentDefinition;
command.RecomputeNodeInfo(varDefNode);
anyVarDefChagned = true;
}
}
// Recompute node info if needed
if (anyVarDefChagned)
{
command.RecomputeNodeInfo(varDefListNode);
}
//
// If we've created a dummy project node, make that the new child of the applyOp
//
applyNode.Child1 = dummyProjectNode != null ? dummyProjectNode : projectNode.Child0;
command.RecomputeNodeInfo(applyNode);
//
// Pull up the project node above the apply node now. Also, make sure that every Var of
// the applyNode's definitions actually shows up in the new Project
//
projectNode.Child0 = applyNode;
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
ProjectOp projectOp = (ProjectOp)projectNode.Op;
projectOp.Outputs.Or(applyLeftChildNodeInfo.Definitions);
newNode = projectNode;
return true;
}
#endregion
#region ApplyOverAnything
internal static readonly PatternMatchRule Rule_CrossApplyOverAnything =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyOverAnything);
internal static readonly PatternMatchRule Rule_OuterApplyOverAnything =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyOverAnything);
///
/// Converts a CrossApply(X,Y) => CrossJoin(X,Y)
/// OuterApply(X,Y) => LeftOuterJoin(X, Y, true)
/// only if Y has no external references to X
///
/// Rule processing context
/// The ApplyOp subtree
/// transformed subtree
/// the transformation status
static bool ProcessApplyOverAnything(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node applyLeftChild = applyNode.Child0;
Node applyRightChild = applyNode.Child1;
ApplyBaseOp applyOp = (ApplyBaseOp)applyNode.Op;
Command command = context.Command;
ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyRightChild);
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyLeftChild);
//
// If we're currently dealing with an OuterApply, and the right child is guaranteed
// to produce at least one row, then we can convert the outer-apply into a cross apply
//
bool convertedToCrossApply = false;
if (applyOp.OpType == OpType.OuterApply &&
applyRightChildNodeInfo.MinRows >= RowCount.One)
{
applyOp = command.CreateCrossApplyOp();
convertedToCrossApply = true;
}
//
// Does the right child reference any of the definitions of the left child? If it
// does, then simply return from this function
//
if (applyRightChildNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
{
if (convertedToCrossApply)
{
newNode = command.CreateNode(applyOp, applyLeftChild, applyRightChild);
return true;
}
else
{
return false;
}
}
//
// So, we now know that the right child does not reference any definitions
// from the left.
// So, we simply convert the apply into an appropriate join Op
//
if (applyOp.OpType == OpType.CrossApply)
{
//
// Convert "x CrossApply y" into "x CrossJoin y"
//
newNode = command.CreateNode(command.CreateCrossJoinOp(),
applyLeftChild, applyRightChild);
}
else // outer apply
{
//
// Convert "x OA y" into "x LOJ y on (true)"
//
LeftOuterJoinOp joinOp = command.CreateLeftOuterJoinOp();
ConstantPredicateOp trueOp = command.CreateTrueOp();
Node trueNode = command.CreateNode(trueOp);
newNode = command.CreateNode(joinOp, applyLeftChild, applyRightChild, trueNode);
}
return true;
}
#endregion
#region ApplyIntoScalarSubquery
internal static readonly PatternMatchRule Rule_CrossApplyIntoScalarSubquery =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyIntoScalarSubquery);
internal static readonly PatternMatchRule Rule_OuterApplyIntoScalarSubquery =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyIntoScalarSubquery);
///
/// Converts a Apply(X,Y) => Project(X, Y1), where Y1 is a scalar subquery version of Y
/// The transformation is valid only if all of the following conditions hold:
/// 1. Y produces only one output
/// 2. Y produces at most one row
/// 3. Y produces at least one row, or the Apply operator in question is an OuterApply
///
/// Rule processing context
/// The ApplyOp subtree
/// transformed subtree
/// the transformation status
static bool ProcessApplyIntoScalarSubquery(RuleProcessingContext context, Node applyNode, out Node newNode)
{
Command command = context.Command;
ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child1);
OpType applyKind = applyNode.Op.OpType;
if (!CanRewriteApply(applyNode.Child1, applyRightChildNodeInfo, applyKind))
{
newNode = applyNode;
return false;
}
// Create the project node over the original input with element over the apply as new projected var
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
Var oldVar = applyRightChildNodeInfo.Definitions.First;
// Project all the outputs from the left child
VarVec projectOpOutputs = command.CreateVarVec(applyLeftChildNodeInfo.Definitions);
//
// Remap the var defining tree to get it into a consistent state
// and then remove all references to oldVar from it to avoid them being wrongly remapped to newVar
// in subsequent remappings.
//
TransformationRulesContext trc = (TransformationRulesContext)context;
trc.RemapSubtree(applyNode.Child1);
VarDefinitionRemapper.RemapSubtree(applyNode.Child1, command, oldVar);
Node elementNode = command.CreateNode(command.CreateElementOp(oldVar.Type), applyNode.Child1);
Var newVar;
Node varDefListNode = command.CreateVarDefListNode(elementNode, out newVar);
projectOpOutputs.Set(newVar);
newNode = command.CreateNode(
command.CreateProjectOp(projectOpOutputs),
applyNode.Child0,
varDefListNode);
// Add the var mapping from oldVar to newVar
trc.AddVarMapping(oldVar, newVar);
return true;
}
///
/// Determines whether an applyNode can be rewritten into a projection with a scalar subquery.
/// It can be done if all of the following conditions hold:
/// 1. The right child or the apply has only one output
/// 2. The right child of the apply produces at most one row
/// 3. The right child of the apply produces at least one row, or the Apply operator in question is an OuterApply
///
///
///
///
///
/// A visitor that calculates the number of output columns for a subree
/// with a given root
///
internal class OutputCountVisitor : BasicOpVisitorOfT
{
#region Constructors
internal OutputCountVisitor()
{
}
#endregion
#region Public Methods
///
/// Calculates the number of output columns for the subree
/// rooted at the given node
///
///
///
/// Visitor for children. Simply visit all children,
/// and sum the number of their outputs.
///
/// Current node
///
/// A default processor for any node.
/// Returns the sum of the children outputs
///
///
/// /returns>
protected override int VisitDefault(Node n)
{
return VisitChildren(n);
}
#endregion
#region RelOp Visitors
#region SetOp Visitors
///
/// The number of outputs is same as for any of the inputs
///
///
///
///
/// Distinct
///
///
///
///
/// FilterOp
///
///
///
///
/// GroupByOp
///
///
///
///
/// ProjectOp
///
///
///
///
/// ScanTableOp
///
///
///
///
/// SingleRowTableOp
///
///
///
///
/// Same as the input
///
///
///
///
/// A utility class that remaps a given var at its definition and also remaps all its references.
/// The given var is remapped to an arbitrary new var.
/// If the var is defined by a ScanTable, all the vars defined by that table and all their references
/// are remapped as well.
///
internal class VarDefinitionRemapper : VarRemapper
{
private readonly Var m_oldVar;
private VarDefinitionRemapper(Var oldVar, Command command)
: base(command)
{
this.m_oldVar = oldVar;
}
///
/// Public entry point.
/// Remaps the subree rooted at the given tree
///
///
///
///
internal static void RemapSubtree(Node root, Command command, Var oldVar)
{
VarDefinitionRemapper remapper = new VarDefinitionRemapper(oldVar, command);
remapper.RemapSubtree(root);
}
///
/// Update vars in this subtree. Recompute the nodeinfo along the way
/// Unlike the base implementation, we want to visit the childrent, even if no vars are in the
/// remapping dictionary.
///
///
internal override void RemapSubtree(Node subTree)
{
foreach (Node chi in subTree.Children)
{
RemapSubtree(chi);
}
VisitNode(subTree);
m_command.RecomputeNodeInfo(subTree);
}
///
/// If the node defines the node that needs to be remapped,
/// it remaps it to a new var.
///
///
///
///
/// If the columnVars defined by the table contain the var that needs to be remapped
/// all the column vars produces by the table are remaped to new vars.
///
///
///
///
/// The var that needs to be remapped may be produced by a set op,
/// in which case the varmaps need to be updated too.
///
///
///
protected override void VisitSetOp(SetOp op, Node n)
{
base.VisitSetOp(op, n);
if (op.Outputs.IsSet(m_oldVar))
{
Var newVar = m_command.CreateSetOpVar(m_oldVar.Type);
op.Outputs.Clear(m_oldVar);
op.Outputs.Set(newVar);
RemapVarMapKey(op.VarMap[0], newVar);
RemapVarMapKey(op.VarMap[1], newVar);
AddMapping(m_oldVar, newVar);
}
}
///
/// Replaces the entry in the varMap in which m_oldVar is a key
/// with an entry in which newVAr is the key and the value remains the same.
///
///
///
private void RemapVarMapKey(VarMap varMap, Var newVar)
{
Var value = varMap[m_oldVar];
varMap.Remove(m_oldVar);
varMap.Add(newVar, value);
}
}
#endregion
#region CrossApply over LeftOuterJoin of SingleRowTable with anything and with constant predicate
internal static readonly PatternMatchRule Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeftOuterJoinOp.Pattern,
new Node(SingleRowTableOp.Pattern),
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern))),
ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable);
///
/// Convert a CrossApply(X, LeftOuterJoin(SingleRowTable, Y, on true))
/// into just OuterApply(X, Y)
///
/// rule processing context
/// the join node
/// transformed subtree
/// transformation status
static bool ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node joinNode = applyNode.Child1;
//Check the value of the predicate
ConstantPredicateOp joinPredicate = (ConstantPredicateOp)joinNode.Child2.Op;
if (joinPredicate.IsFalse)
{
return false;
}
applyNode.Op = context.Command.CreateOuterApplyOp();
applyNode.Child1 = joinNode.Child1;
return true;
}
#endregion
#region All ApplyOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
ApplyOpRules.Rule_CrossApplyOverAnything,
ApplyOpRules.Rule_CrossApplyOverFilter,
ApplyOpRules.Rule_CrossApplyOverProject,
ApplyOpRules.Rule_OuterApplyOverAnything,
ApplyOpRules.Rule_OuterApplyOverProjectInternalConstantOverFilter,
ApplyOpRules.Rule_OuterApplyOverProjectNullSentinelOverFilter,
ApplyOpRules.Rule_OuterApplyOverProject,
ApplyOpRules.Rule_OuterApplyOverFilter,
ApplyOpRules.Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable,
ApplyOpRules.Rule_CrossApplyIntoScalarSubquery,
ApplyOpRules.Rule_OuterApplyIntoScalarSubquery,
};
#endregion
}
#endregion
#region Join Rules
///
/// Transformation rules for JoinOps
///
internal static class JoinOpRules
{
#region JoinOverProject
internal static readonly PatternMatchRule Rule_CrossJoinOverProject1 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_CrossJoinOverProject2 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_InnerJoinOverProject1 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_InnerJoinOverProject2 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_OuterJoinOverProject2 =
new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
///
/// CrossJoin(Project(A), B) => Project(CrossJoin(A, B), modifiedvars)
/// InnerJoin(Project(A), B, p) => Project(InnerJoin(A, B, p'), modifiedvars)
/// LeftOuterJoin(Project(A), B, p) => Project(LeftOuterJoin(A, B, p'), modifiedvars)
///
/// Rule processing context
/// Current JoinOp tree to process
/// Transformed subtree
/// transformation status
static bool ProcessJoinOverProject(RuleProcessingContext context, Node joinNode, out Node newNode)
{
newNode = joinNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
Node joinConditionNode = joinNode.HasChild2 ? joinNode.Child2 : (Node)null;
Dictionary varRefMap = new Dictionary();
if (joinConditionNode != null && !trc.IsScalarOpTree(joinConditionNode, varRefMap))
{
return false;
}
Node newJoinNode;
Node newProjectNode;
// Now locate the ProjectOps
VarVec newVarSet = command.CreateVarVec();
List varDefNodes = new List();
//
// Try and handle "project" on both sides only if we're not dealing with
// an LOJ.
//
if ((joinNode.Op.OpType != OpType.LeftOuterJoin) &&
(joinNode.Child0.Op.OpType == OpType.Project) &&
(joinNode.Child1.Op.OpType == OpType.Project))
{
ProjectOp projectOp1 = (ProjectOp)joinNode.Child0.Op;
ProjectOp projectOp2 = (ProjectOp)joinNode.Child1.Op;
Dictionary varMap1 = trc.GetVarMap(joinNode.Child0.Child1, varRefMap);
Dictionary varMap2 = trc.GetVarMap(joinNode.Child1.Child1, varRefMap);
if (varMap1 == null || varMap2 == null)
{
return false;
}
if (joinConditionNode != null)
{
joinConditionNode = trc.ReMap(joinConditionNode, varMap1);
joinConditionNode = trc.ReMap(joinConditionNode, varMap2);
newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0, joinConditionNode);
}
else
{
newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0);
}
newVarSet.InitFrom(projectOp1.Outputs);
foreach (Var v in projectOp2.Outputs)
{
newVarSet.Set(v);
}
ProjectOp newProjectOp = command.CreateProjectOp(newVarSet);
varDefNodes.AddRange(joinNode.Child0.Child1.Children);
varDefNodes.AddRange(joinNode.Child1.Child1.Children);
Node varDefListNode = command.CreateNode(
command.CreateVarDefListOp(),
varDefNodes);
newProjectNode = command.CreateNode(newProjectOp,
newJoinNode, varDefListNode);
newNode = newProjectNode;
return true;
}
int projectNodeIdx = -1;
int otherNodeIdx = -1;
if (joinNode.Child0.Op.OpType == OpType.Project)
{
projectNodeIdx = 0;
otherNodeIdx = 1;
}
else
{
PlanCompiler.Assert(joinNode.Op.OpType != OpType.LeftOuterJoin, "unexpected non-LeftOuterJoin");
projectNodeIdx = 1;
otherNodeIdx = 0;
}
Node projectNode = joinNode.Children[projectNodeIdx];
ProjectOp projectOp = projectNode.Op as ProjectOp;
Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
if (varMap == null)
{
return false;
}
ExtendedNodeInfo otherChildInfo = command.GetExtendedNodeInfo(joinNode.Children[otherNodeIdx]);
VarVec vec = command.CreateVarVec(projectOp.Outputs);
vec.Or(otherChildInfo.Definitions);
projectOp.Outputs.InitFrom(vec);
if (joinConditionNode != null)
{
joinConditionNode = trc.ReMap(joinConditionNode, varMap);
joinNode.Child2 = joinConditionNode;
}
joinNode.Children[projectNodeIdx] = projectNode.Child0; // bypass the projectOp
context.Command.RecomputeNodeInfo(joinNode);
newNode = context.Command.CreateNode(projectOp, joinNode, projectNode.Child1);
return true;
}
#endregion
#region JoinOverFilter
internal static readonly PatternMatchRule Rule_CrossJoinOverFilter1 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_CrossJoinOverFilter2 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_InnerJoinOverFilter1 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_InnerJoinOverFilter2 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_OuterJoinOverFilter2 =
new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
///
/// CrossJoin(Filter(A,p), B) => Filter(CrossJoin(A, B), p)
/// CrossJoin(A, Filter(B,p)) => Filter(CrossJoin(A, B), p)
///
/// InnerJoin(Filter(A,p), B, c) => Filter(InnerJoin(A, B, c), p)
/// InnerJoin(A, Filter(B,p), c) => Filter(InnerJoin(A, B, c), p)
///
/// LeftOuterJoin(Filter(A,p), B, c) => Filter(LeftOuterJoin(A, B, c), p)
///
/// Note that the predicate on the right table in a left-outer-join cannot be pulled
/// up above the join.
///
///
/// Rule processing context
/// Current JoinOp tree to process
/// transformed subtree
/// transformation status
static bool ProcessJoinOverFilter(RuleProcessingContext context, Node joinNode, out Node newNode)
{
newNode = joinNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
Node predicateNode = null;
Node newLeftInput = joinNode.Child0;
// get the predicate from the first filter
if (joinNode.Child0.Op.OpType == OpType.Filter)
{
predicateNode = joinNode.Child0.Child1;
newLeftInput = joinNode.Child0.Child0; // bypass the filter
}
// get the predicate from the second filter
Node newRightInput = joinNode.Child1;
if (joinNode.Child1.Op.OpType == OpType.Filter && joinNode.Op.OpType != OpType.LeftOuterJoin)
{
if (predicateNode == null)
{
predicateNode = joinNode.Child1.Child1;
}
else
{
predicateNode = command.CreateNode(
command.CreateConditionalOp(OpType.And),
predicateNode, joinNode.Child1.Child1);
}
newRightInput = joinNode.Child1.Child0; // bypass the filter
}
// No optimizations to perform if we can't locate the appropriate predicate
if (predicateNode == null)
{
return false;
}
//
// Create a new join node with the new inputs
//
Node newJoinNode;
if (joinNode.Op.OpType == OpType.CrossJoin)
{
newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput);
}
else
{
newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput, joinNode.Child2);
}
//
// create a new filterOp with the combined predicates, and with the
// newjoinNode as the input
//
FilterOp newFilterOp = command.CreateFilterOp();
newNode = command.CreateNode(newFilterOp, newJoinNode, predicateNode);
//
// Mark this subtree so that we don't try to push filters down again
//
trc.SuppressFilterPushdown(newNode);
return true;
}
#endregion
#region Join over SingleRowTable
internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable1 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(SingleRowTableOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverSingleRowTable);
internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable2 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(SingleRowTableOp.Pattern)),
ProcessJoinOverSingleRowTable);
internal static readonly PatternMatchRule Rule_LeftOuterJoinOverSingleRowTable =
new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(SingleRowTableOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverSingleRowTable);
///
/// Convert a CrossJoin(SingleRowTable, X) or CrossJoin(X, SingleRowTable) or LeftOuterJoin(X, SingleRowTable)
/// into just "X"
///
/// rule processing context
/// the join node
/// transformed subtree
/// transformation status
static bool ProcessJoinOverSingleRowTable(RuleProcessingContext context, Node joinNode, out Node newNode)
{
newNode = joinNode;
if (joinNode.Child0.Op.OpType == OpType.SingleRowTable)
{
newNode = joinNode.Child1;
}
else
{
newNode = joinNode.Child0;
}
return true;
}
#endregion
#region Misc
#endregion
#region All JoinOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
Rule_CrossJoinOverProject1,
Rule_CrossJoinOverProject2,
Rule_InnerJoinOverProject1,
Rule_InnerJoinOverProject2,
Rule_OuterJoinOverProject2,
Rule_CrossJoinOverFilter1,
Rule_CrossJoinOverFilter2,
Rule_InnerJoinOverFilter1,
Rule_InnerJoinOverFilter2,
Rule_OuterJoinOverFilter2,
Rule_CrossJoinOverSingleRowTable1,
Rule_CrossJoinOverSingleRowTable2,
Rule_LeftOuterJoinOverSingleRowTable,
};
#endregion
}
#endregion
#region SingleRowOp Rules
///
/// Rules for SingleRowOp
///
internal static class SingleRowOpRules
{
internal static readonly PatternMatchRule Rule_SingleRowOpOverAnything =
new PatternMatchRule(new Node(SingleRowOp.Pattern,
new Node(LeafOp.Pattern)),
ProcessSingleRowOpOverAnything);
///
/// Convert a
/// SingleRowOp(X) => X
/// if X produces at most one row
///
/// Rule Processing context
/// Current subtree
/// transformed subtree
/// Transformation status
static bool ProcessSingleRowOpOverAnything(RuleProcessingContext context, Node singleRowNode, out Node newNode)
{
newNode = singleRowNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
ExtendedNodeInfo childNodeInfo = context.Command.GetExtendedNodeInfo(singleRowNode.Child0);
// If the input to this Op can produce at most one row, then we don't need the
// singleRowOp - simply return the input
if (childNodeInfo.MaxRows <= RowCount.One)
{
newNode = singleRowNode.Child0;
return true;
}
//
// if the current node is a FilterOp, then try and determine if the FilterOp
// produces one row at most
//
if (singleRowNode.Child0.Op.OpType == OpType.Filter)
{
Predicate predicate = new Predicate(context.Command, singleRowNode.Child0.Child1);
if (predicate.SatisfiesKey(childNodeInfo.Keys.KeyVars, childNodeInfo.Definitions))
{
childNodeInfo.MaxRows = RowCount.One;
newNode = singleRowNode.Child0;
return true;
}
}
// we couldn't do anything
return false;
}
internal static readonly PatternMatchRule Rule_SingleRowOpOverProject =
new PatternMatchRule(new Node(SingleRowOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern), new Node(LeafOp.Pattern))),
ProcessSingleRowOpOverProject);
///
/// Convert
/// SingleRowOp(Project) => Project(SingleRowOp)
///
/// Rule Processing context
/// current subtree
/// transformeed subtree
/// transformation status
static bool ProcessSingleRowOpOverProject(RuleProcessingContext context, Node singleRowNode, out Node newNode)
{
newNode = singleRowNode;
Node projectNode = singleRowNode.Child0;
Node projectNodeInput = projectNode.Child0;
// Simply push the SingleRowOp below the ProjectOp
singleRowNode.Child0 = projectNodeInput;
context.Command.RecomputeNodeInfo(singleRowNode);
projectNode.Child0 = singleRowNode;
newNode = projectNode;
return true; // subtree modified internally
}
#region All SingleRowOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
Rule_SingleRowOpOverAnything,
Rule_SingleRowOpOverProject,
};
#endregion
}
#endregion
#region SetOp Rules
///
/// SetOp Transformation Rules
///
internal static class SetOpRules
{
#region SetOpOverFilters
internal static readonly SimpleRule Rule_UnionAllOverEmptySet =
new SimpleRule(OpType.UnionAll, ProcessSetOpOverEmptySet);
internal static readonly SimpleRule Rule_IntersectOverEmptySet =
new SimpleRule(OpType.Intersect, ProcessSetOpOverEmptySet);
internal static readonly SimpleRule Rule_ExceptOverEmptySet =
new SimpleRule(OpType.Except, ProcessSetOpOverEmptySet);
///
/// Process a SetOp when one of the inputs is an emptyset.
///
/// An emptyset is represented by a Filter(X, ConstantPredicate)
/// where the ConstantPredicate has a value of "false"
///
/// The general rules are
/// UnionAll(X, EmptySet) => X
/// UnionAll(EmptySet, X) => X
/// Intersect(EmptySet, X) => EmptySet
/// Intersect(X, EmptySet) => EmptySet
/// Except(EmptySet, X) => EmptySet
/// Except(X, EmptySet) => X
///
/// These rules then translate into
/// UnionAll: return the non-empty input
/// Intersect: return the empty input
/// Except: return the "left" input
///
/// Rule processing context
/// the current setop tree
/// Index of the filter node in the setop
/// transformed subtree
/// transformation status
private static bool ProcessSetOpOverEmptySet(RuleProcessingContext context, Node setOpNode, out Node newNode)
{
bool leftChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child0).MaxRows == RowCount.Zero;
bool rightChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child1).MaxRows == RowCount.Zero;
if (!leftChildIsEmptySet && !rightChildIsEmptySet)
{
newNode = setOpNode;
return false;
}
int indexToReturn;
SetOp setOp = (SetOp)setOpNode.Op;
if (!rightChildIsEmptySet && setOp.OpType == OpType.UnionAll ||
!leftChildIsEmptySet && setOp.OpType == OpType.Intersect)
{
indexToReturn = 1;
}
else
{
indexToReturn = 0;
}
newNode = setOpNode.Children[indexToReturn];
TransformationRulesContext trc = (TransformationRulesContext)context;
foreach (KeyValuePair kv in setOp.VarMap[indexToReturn])
{
trc.AddVarMapping(kv.Key, kv.Value);
}
return true;
}
#endregion
#region All SetOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
Rule_UnionAllOverEmptySet,
Rule_IntersectOverEmptySet,
Rule_ExceptOverEmptySet,
};
#endregion
}
#endregion
#region GroupByOp Rules
///
/// Transformation Rules for GroupByOps
///
internal static class GroupByOpRules
{
#region GroupByOpWithSimpleVarRedefinitions
internal static readonly SimpleRule Rule_GroupByOpWithSimpleVarRedefinitions = new SimpleRule(OpType.GroupBy, ProcessGroupByWithSimpleVarRedefinitions);
///
/// If the GroupByOp defines some computedVars as part of its keys, but those computedVars are simply
/// redefinitions of other Vars, then eliminate the computedVars.
///
/// GroupBy(X, VarDefList(VarDef(cv1, VarRef(v1)), ...), VarDefList(...))
/// can be transformed into
/// GroupBy(X, VarDefList(...))
/// where cv1 has now been replaced by v1
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessGroupByWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
GroupByOp groupByOp = (GroupByOp)n.Op;
// no local keys? nothing to do
if (n.Child1.Children.Count == 0)
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
//
// Check to see if any of the computed Vars defined by this GroupByOp
// are simple redefinitions of other VarRefOps. Consider only those
// VarRefOps that are not "external" references
//
bool canEliminateSomeVars = false;
foreach (Node varDefNode in n.Child1.Children)
{
Node definingExprNode = varDefNode.Child0;
if (definingExprNode.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
// this is a Var that we should remove
canEliminateSomeVars = true;
}
}
}
// Did we have any redefinitions
if (!canEliminateSomeVars)
{
return false;
}
//
// OK. We've now identified a set of vars that are simple redefinitions.
// Try and replace the computed Vars with the Vars that they're redefining
//
// Lets now build up a new VarDefListNode
List newVarDefNodes = new List();
foreach (Node varDefNode in n.Child1.Children)
{
VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
groupByOp.Outputs.Clear(varDefOp.Var);
groupByOp.Outputs.Set(varRefOp.Var);
groupByOp.Keys.Clear(varDefOp.Var);
groupByOp.Keys.Set(varRefOp.Var);
trc.AddVarMapping(varDefOp.Var, varRefOp.Var);
}
else
{
newVarDefNodes.Add(varDefNode);
}
}
// Create a new vardeflist node, and set that as Child1 for the group by op
Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
n.Child1 = newVarDefListNode;
return true; // subtree modified
}
#endregion
#region GroupByOverProject
internal static readonly PatternMatchRule Rule_GroupByOverProject =
new PatternMatchRule(new Node(GroupByOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessGroupByOverProject);
///
/// Converts a GroupBy(Project(X, c1,..ck), agg1, agg2, .. aggm) =>
/// GroupBy(X, agg1', agg2', .. aggm')
/// where agg1', agg2', .. aggm' are the "mapped" versions
/// of agg1, agg2, .. aggm, such that the references to c1, ... ck are
/// replaced by their definitions.
///
/// We only do this if each c1, ..ck is refereneced (in aggregates) at most once or it is a constant.
///
/// Rule processing context
/// Current ProjectOp node
/// modified subtree
/// Transformation status
static bool ProcessGroupByOverProject(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
GroupByOp op = (GroupByOp)n.Op;
Command command = ((TransformationRulesContext)context).Command;
Node projectNode = n.Child0;
Node projectNodeVarDefList = projectNode.Child1;
Node keys = n.Child1;
Node aggregates = n.Child2;
// If there are any keys, we should not remove the inner project
if (keys.Children.Count > 0)
{
return false;
}
//Get a list of all defining vars
VarVec projectDefinitions = command.GetExtendedNodeInfo(projectNode).LocalDefinitions;
//If any of the defined vars is output, than we need the extra project anyway.
if (op.Outputs.Overlaps(projectDefinitions))
{
return false;
}
bool createdNewProjectDefinitions = false;
//If there are any constants remove them from the list that needs to be tested,
//These can safely be replaced
for (int i = 0; i < projectNodeVarDefList.Children.Count; i++)
{
Node varDefNode = projectNodeVarDefList.Children[i];
if (varDefNode.Child0.Op.OpType == OpType.Constant || varDefNode.Child0.Op.OpType == OpType.InternalConstant || varDefNode.Child0.Op.OpType == OpType.NullSentinel)
{
//We shouldn't modify the original project definitions, thus we copy it
// the first time we encounter a constant
if (!createdNewProjectDefinitions)
{
projectDefinitions = command.CreateVarVec(projectDefinitions);
createdNewProjectDefinitions = true;
}
projectDefinitions.Clear(((VarDefOp)varDefNode.Op).Var);
}
}
if (VarRefUsageFinder.AnyVarUsedMoreThanOnce(projectDefinitions, aggregates, command))
{
return false;
}
//If we got here it means that all vars were either constants, or used at most once
// Create a dictionary to be used for remapping the keys and the aggregates
Dictionary varToDefiningNode = new Dictionary(projectNodeVarDefList.Children.Count);
for (int j = 0; j < projectNodeVarDefList.Children.Count; j++)
{
Node varDefNode = projectNodeVarDefList.Children[j];
Var var = ((VarDefOp)varDefNode.Op).Var;
varToDefiningNode.Add(var, varDefNode.Child0);
}
newNode.Child2 = VarRefReplacer.Replace(varToDefiningNode, aggregates, command);
newNode.Child0 = projectNode.Child0;
return true;
}
///
/// Replaces each occurance of the given vars with their definitions.
///
internal class VarRefReplacer : BasicOpVisitorOfNode
{
private Dictionary m_varReplacementTable;
private Command m_command;
private VarRefReplacer(Dictionary varReplacementTable, Command command)
{
this.m_varReplacementTable = varReplacementTable;
this.m_command = command;
}
///
/// "Public" entry point. In the subtree rooted at the given root,
/// replace each occurance of the given vars with their definitions,
/// where each key-value pair in the dictionary is a var-definition pair.
///
///
///
///
/// varReplacementTable, Node root, Command command)
{
VarRefReplacer replacer = new VarRefReplacer(varReplacementTable, command);
return replacer.VisitNode(root);
}
public override Node Visit(VarRefOp op, Node n)
{
Node replacementNode;
if (m_varReplacementTable.TryGetValue(op.Var, out replacementNode))
{
return replacementNode;
}
else
{
return n;
}
}
///
/// Recomputes node info post regular processing.
///
///
///
/// Used to determine whether any of the given vars occurs more than once
/// in a given subtree.
///
internal class VarRefUsageFinder : BasicOpVisitor
{
private bool m_anyUsedMoreThenOnce = false;
private VarVec m_varVec;
private VarVec m_usedVars;
private VarRefUsageFinder(VarVec varVec, Command command)
{
this.m_varVec = varVec;
this.m_usedVars = command.CreateVarVec();
}
///
/// Public entry point. Returns true if at least one of the given vars occurs more than
/// once in the subree rooted at the given root.
///
///
///
///
///
/// If the GroupByOp has no aggregates:
///
/// (1) and if it includes all all the keys of the input, than it is unnecessary
/// GroupBy (X, keys) -> Project(X, keys) where keys includes all keys of X.
///
/// (2) else it can be turned into a Distinct:
/// GroupBy (X, keys) -> Distinct(X, keys)
///
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessGroupByOpWithNoAggregates(RuleProcessingContext context, Node n, out Node newNode)
{
Command command = context.Command;
GroupByOp op = (GroupByOp)n.Op;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
ProjectOp newOp = command.CreateProjectOp(op.Keys);
VarDefListOp varDefListOp = command.CreateVarDefListOp();
Node varDefListNode = command.CreateNode(varDefListOp);
newNode = command.CreateNode(newOp, n.Child0, n.Child1);
//If we know the keys of the input and the list of keys includes them all,
// this is the result, otherwise add distinct
if (nodeInfo.Keys.NoKeys || !op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
{
newNode = command.CreateNode(command.CreateDistinctOp(command.CreateVarVec(op.Keys)), newNode);
}
return true;
}
#endregion
#region All GroupByOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions,
GroupByOpRules.Rule_GroupByOverProject,
GroupByOpRules.Rule_GroupByOpWithNoAggregates,
};
#endregion
}
#endregion
#region Sorting Rules
///
/// Transformation Rules for SortOp
///
internal static class SortOpRules
{
#region SortOpOverAtMostOneRow
internal static readonly SimpleRule Rule_SortOpOverAtMostOneRow = new SimpleRule(OpType.Sort, ProcessSortOpOverAtMostOneRow);
///
/// If the SortOp's input is guaranteed to produce at most 1 row, remove the node with the SortOp:
/// Sort(X) => X, if X is guaranteed to produce no more than 1 row
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessSortOpOverAtMostOneRow(RuleProcessingContext context, Node n, out Node newNode)
{
ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
//If the input has at most one row, omit the SortOp
if (nodeInfo.MaxRows == RowCount.Zero || nodeInfo.MaxRows == RowCount.One)
{
newNode = n.Child0;
return true;
}
//Otherwise return the node as is
newNode = n;
return false;
}
#endregion
#region All SortOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
SortOpRules.Rule_SortOpOverAtMostOneRow,
};
#endregion
}
///
/// Transformation Rules for ConstrainedSortOp
///
internal static class ConstrainedSortOpRules
{
#region ConstrainedSortOpOverEmptySet
internal static readonly SimpleRule Rule_ConstrainedSortOpOverEmptySet = new SimpleRule(OpType.ConstrainedSort, ProcessConstrainedSortOpOverEmptySet);
///
/// If the ConstrainedSortOp's input is guaranteed to produce no rows, remove the ConstrainedSortOp completly:
/// CSort(EmptySet) => EmptySet
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessConstrainedSortOpOverEmptySet(RuleProcessingContext context, Node n, out Node newNode)
{
ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
//If the input has no rows, remove the ConstraintSortOp node completly
if (nodeInfo.MaxRows == RowCount.Zero)
{
newNode = n.Child0;
return true;
}
newNode = n;
return false;
}
#endregion
#region All ConstrainedSortOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
ConstrainedSortOpRules.Rule_ConstrainedSortOpOverEmptySet,
};
#endregion
}
#endregion
#region DistinctOp Rules
///
/// Transformation Rules for DistinctOp
///
internal static class DistinctOpRules
{
#region DistinctOpOfKeys
internal static readonly SimpleRule Rule_DistinctOpOfKeys = new SimpleRule(OpType.Distinct, ProcessDistinctOpOfKeys);
///
/// If the DistinctOp includes all all the keys of the input, than it is unnecessary.
/// Distinct (X, distinct_keys) -> Project( X, distinct_keys) where distinct_keys includes all keys of X.
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessDistinctOpOfKeys(RuleProcessingContext context, Node n, out Node newNode)
{
Command command = context.Command;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
DistinctOp op = (DistinctOp)n.Op;
//If we know the keys of the input and the list of distinct keys includes them all, omit the distinct
if (!nodeInfo.Keys.NoKeys && op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
{
ProjectOp newOp = command.CreateProjectOp(op.Keys);
//Create empty vardef list
VarDefListOp varDefListOp = command.CreateVarDefListOp();
Node varDefListNode = command.CreateNode(varDefListOp);
newNode = command.CreateNode(newOp, n.Child0, varDefListNode);
return true;
}
//Otherwise return the node as is
newNode = n;
return false;
}
#endregion
#region All DistinctOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
DistinctOpRules.Rule_DistinctOpOfKeys,
};
#endregion
}
#endregion
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....]
// @backupOwner [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization;
using System.Linq;
using System.Data.Metadata.Edm;
using System.Data.Query.InternalTrees;
namespace System.Data.Query.PlanCompiler
{
internal class TransformationRulesContext : RuleProcessingContext
{
#region public methods and properties
///
/// Whether any rule was applied that may have caused modifications such that projection pruning
/// may be useful
///
internal bool ProjectionPrunningRequired { get { return this.m_projectionPrunningRequired; } }
///
/// Whether any rule was applied that may have caused modifications such that reapplying
/// the nullability rules may be useful
///
internal bool ReapplyNullabilityRules { get { return this.m_reapplyNullabilityRules; } }
///
/// Remap the given subree using the current remapper
///
///
internal void RemapSubtree(Node subTree)
{
this.m_remapper.RemapSubtree(subTree);
}
///
/// Adds a mapping from oldVar to newVar
///
///
///
internal void AddVarMapping(Var oldVar, Var newVar)
{
m_remapper.AddMapping(oldVar, newVar);
m_remappedVars.Set(oldVar);
}
///
/// "Remap" an expression tree, replacing all references to vars in varMap with
/// copies of the corresponding expression
/// The subtree is modified *inplace* - it is the caller's responsibility to make
/// a copy of the subtree if necessary.
/// The "replacement" expression (the replacement for the VarRef) is copied and then
/// inserted into the appropriate location into the subtree.
///
/// Note: we only support replacements in simple ScalarOp trees. This must be
/// validated by the caller.
///
///
/// Current subtree to process
///
/// The updated subtree
internal Node ReMap(Node node, Dictionary varMap)
{
PlanCompiler.Assert(node.Op.IsScalarOp, "Expected a scalarOp: Found " + Dump.AutoString.ToString(node.Op.OpType));
// Replace varRefOps by the corresponding expression in the map, if any
if (node.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = node.Op as VarRefOp;
Node newNode = null;
if (varMap.TryGetValue(varRefOp.Var, out newNode))
{
newNode = this.Copy(newNode);
return newNode;
}
else
{
return node;
}
}
// Simply process the result of the children.
for (int i = 0; i < node.Children.Count; i++)
{
node.Children[i] = ReMap(node.Children[i], varMap);
}
// We may have changed something deep down
this.Command.RecomputeNodeInfo(node);
return node;
}
///
/// Makes a copy of the appropriate subtree - with a simple accelerator for VarRefOp
/// since that's likely to be the most command case
///
/// the subtree to copy
/// the copy of the subtree
internal Node Copy(Node node)
{
if (node.Op.OpType == OpType.VarRef)
{
VarRefOp op = node.Op as VarRefOp;
return this.Command.CreateNode(this.Command.CreateVarRefOp(op.Var));
}
else
{
return OpCopier.Copy(this.Command, node);
}
}
///
/// Checks to see if the current subtree only contains ScalarOps
///
/// current subtree
/// true, if the subtree contains only ScalarOps
internal bool IsScalarOpTree(Node node)
{
int nodeCount = 0;
return IsScalarOpTree(node, null, ref nodeCount);
}
///
/// Is the given var guaranteed to be non-nullable with regards to the node
/// that is currently being processed.
/// True, if it is listed as such on any on the node infos on any of the
/// current relop ancestors.
///
///
///
/// Is it safe to use a null sentinel with any value?
/// It may not be safe if:
/// 1. The top most sort includes null sentinels. If the null sentinel is replaced with a different value
/// and is used as a sort key it may change the sorting results
/// 2. If any of the ancestors is Distinct, GroupBy, Intersect or Except,
/// because the null sentinel may be used as a key.
/// 3. If the null sentinel is defined in the left child of an apply it may be used at the right side,
/// thus in these cases we also verify that the right hand side does not have any Distinct, GroupBy,
/// Intersect or Except.
///
internal bool CanChangeNullSentinelValue
{
get
{
//Is there a sort that includes null sentinels
if (this.m_compilerState.HasSortingOnNullSentinels)
{
return false;
}
//Is any of the ancestors Distinct, GroupBy, Intersect or Except
if (this.m_relOpAncestors.Any(a => IsOpNotSafeForNullSentinelValueChange(a.Op.OpType)))
{
return false;
}
// Is the null sentinel defined in the left child of an apply and if so,
// does the right hand side have any Distinct, GroupBy, Intersect or Except.
var applyAncestors = this.m_relOpAncestors.Where(a =>
a.Op.OpType == OpType.CrossApply ||
a.Op.OpType == OpType.OuterApply);
//If the sentinel comes from the right hand side it is ok.
foreach (Node applyAncestor in applyAncestors)
{
if (!this.m_relOpAncestors.Contains(applyAncestor.Child1) && HasOpNotSafeForNullSentinelValueChange(applyAncestor.Child1))
{
return false;
}
}
return true;
}
}
///
/// Is the op not safe for null sentinel value change
///
///
///
/// Does the given subtree contain a node with an op that
/// is not safer for null sentinel value change
///
///
///
/// Is this is a scalar-op tree? Also return a dictionary of var refcounts (ie)
/// for each var encountered in the tree, determine the number of times it has
/// been seen
///
/// current subtree
/// dictionary of var refcounts to fill in
/// varRefMap)
{
PlanCompiler.Assert(varRefMap != null, "Null varRef map");
int nodeCount = 0;
return IsScalarOpTree(node, varRefMap, ref nodeCount);
}
///
/// Get a mapping from Var->Expression for a VarDefListOp tree. This information
/// will be used by later stages to replace all references to the Vars by the
/// corresponding expressions
///
/// This function uses a few heuristics along the way. It uses the varRefMap
/// parameter to determine if a computed Var (defined by this VarDefListOp)
/// has been referenced multiple times, and if it has, it checks to see if
/// the defining expression is too big (> 100 nodes). This is to avoid
/// bloating up the entire query tree with too many copies.
///
///
/// The varDefListOp subtree
/// ref counts for each referenced var
/// mapping from Var->replacement xpressions
internal Dictionary GetVarMap(Node varDefListNode, Dictionary varRefMap)
{
VarDefListOp varDefListOp = (VarDefListOp)varDefListNode.Op;
Dictionary varMap = new Dictionary();
foreach (Node chi in varDefListNode.Children)
{
VarDefOp varDefOp = (VarDefOp)chi.Op;
int nonLeafNodeCount = 0;
int refCount = 0;
if (!IsScalarOpTree(chi.Child0, null, ref nonLeafNodeCount))
{
return null;
}
//
// More heuristics. If there are multiple references to this Var *and*
// the defining expression for the Var is "expensive" (ie) has larger than
// 100 nodes, then simply pretend that this is too hard to do
// Note: we check for more than 2 references, (rather than just more than 1) - this
// is simply to let some additional cases through
//
if ((nonLeafNodeCount > 100) &&
(varRefMap != null) &&
varRefMap.TryGetValue(varDefOp.Var, out refCount) &&
(refCount > 2))
{
return null;
}
Node n;
if (varMap.TryGetValue(varDefOp.Var, out n))
{
PlanCompiler.Assert(n == chi.Child0, "reusing varDef for different Node?");
}
else
{
varMap.Add(varDefOp.Var, chi.Child0);
}
}
return varMap;
}
///
/// Builds a NULLIF expression (ie) a Case expression that looks like
/// CASE WHEN v is null THEN null ELSE expr END
/// where v is the conditionVar parameter, and expr is the value of the expression
/// when v is non-null
///
/// null discriminator var
/// expression
///
/// Shut off filter pushdown for this subtree
///
///
internal void SuppressFilterPushdown(Node n)
{
m_suppressions[n] = n;
}
///
/// Is filter pushdown shut off for this subtree?
///
///
///
/// Given a list of vars try to get one that is of type Int32
///
///
///
/// ();
m_remappedVars = compilerState.Command.CreateVarVec();
}
#endregion
#region private state
private readonly PlanCompiler m_compilerState;
private readonly VarRemapper m_remapper;
private readonly Dictionary m_suppressions;
private readonly VarVec m_remappedVars;
private bool m_projectionPrunningRequired = false;
private bool m_reapplyNullabilityRules = false;
private Stack m_relOpAncestors = new Stack();
#if DEBUG
///
/// Used to see all the applied rules.
/// One way to use it is to put a conditional breakpoint at the end of
/// PostProcessSubTree with the condition m_relOpAncestors.Count == 0
///
internal readonly System.Text.StringBuilder appliedRules = new System.Text.StringBuilder();
#endif
#endregion
#region RuleProcessingContext Overrides
///
/// Callback function to invoke *before* rules are applied.
/// Calls the VarRemapper to update any Vars in this node, and recomputes
/// the nodeinfo
///
///
internal override void PreProcess(Node n)
{
m_remapper.RemapNode(n);
Command.RecomputeNodeInfo(n);
}
///
/// Callback function to invoke *before* rules are applied.
/// Calls the VarRemapper to update any Vars in the entire subtree
/// If the given node has a RelOp it is pushed on the relOp ancestors stack.
///
///
internal override void PreProcessSubTree(Node subTree)
{
if (subTree.Op.IsRelOp)
{
m_relOpAncestors.Push(subTree);
}
if (m_remappedVars.IsEmpty)
{
return;
}
NodeInfo nodeInfo = this.Command.GetNodeInfo(subTree);
//We need to do remapping only if m_remappedVars overlaps with nodeInfo.ExternalReferences
foreach (Var v in nodeInfo.ExternalReferences)
{
if (m_remappedVars.IsSet(v))
{
m_remapper.RemapSubtree(subTree);
break;
}
}
}
///
/// If the given node has a RelOp it is popped from the relOp ancestors stack.
///
///
internal override void PostProcessSubTree(Node subtree)
{
if (subtree.Op.IsRelOp)
{
PlanCompiler.Assert(m_relOpAncestors.Count != 0, "The RelOp ancestors stack is empty when post processing a RelOp subtree");
Node poppedNode = m_relOpAncestors.Pop();
PlanCompiler.Assert(Object.ReferenceEquals(subtree, poppedNode), "The popped ancestor is not equal to the root of the subtree being post processed");
}
}
///
/// Callback function to invoke *after* rules are applied
/// Recomputes the node info, if this node has changed
/// If the rule is among the rules after which projection pruning may be beneficial,
/// m_projectionPrunningRequired is set to true.
/// If the rule is among the rules after which reapplying the nullability rules may be beneficial,
/// m_reapplyNullabilityRules is set to true.
///
///
/// the rule that was applied
internal override void PostProcess(Node n, InternalTrees.Rule rule)
{
if (rule != null)
{
#if DEBUG
appliedRules.Append(rule.MethodName);
appliedRules.AppendLine();
#endif
if (!this.m_projectionPrunningRequired && TransformationRules.RulesRequiringProjectionPruning.Contains(rule))
{
this.m_projectionPrunningRequired = true;
}
if (!this.m_reapplyNullabilityRules && TransformationRules.RulesRequiringNullabilityRulesToBeReapplied.Contains(rule))
{
this.m_reapplyNullabilityRules = true;
}
Command.RecomputeNodeInfo(n);
}
}
///
/// Get the hash value for this subtree
///
///
///
/// Check to see if the current subtree is a scalar-op subtree (ie) does
/// the subtree only comprise of scalarOps?
/// Additionally, compute the number of non-leaf nodes (ie) nodes with at least one child
/// that are found in the subtree. Note that this count is approximate - it is only
/// intended to be used as a hint. It is the caller's responsibility to initialize
/// nodeCount to a sane value on entry into this function
/// And finally, if the varRefMap parameter is non-null, we keep track of
/// how often a Var is referenced within the subtree
///
/// The non-leaf-node count and the varRefMap are used by GetVarMap to determine
/// if expressions can be composed together
///
/// root of the subtree
/// Ref counts for each Var encountered in the subtree
/// count of non-leaf nodes encountered in the subtree
/// true, if this node only contains scalarOps
private bool IsScalarOpTree(Node node, Dictionary varRefMap, ref int nonLeafNodeCount)
{
if (!node.Op.IsScalarOp)
{
return false;
}
if (node.HasChild0)
{
nonLeafNodeCount++;
}
if (varRefMap != null && node.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = (VarRefOp)node.Op;
int refCount;
if (!varRefMap.TryGetValue(varRefOp.Var, out refCount))
{
refCount = 1;
}
else
{
refCount++;
}
varRefMap[varRefOp.Var] = refCount;
}
foreach (Node chi in node.Children)
{
if (!IsScalarOpTree(chi, varRefMap, ref nonLeafNodeCount))
{
return false;
}
}
return true;
}
#endregion
}
///
/// The list of all transformation rules to apply
///
internal static class TransformationRules
{
///
/// A lookup table for built from all rules
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> AllRulesTable = BuildLookupTableForRules(AllRules);
///
/// A lookup table for built only from ProjectRules
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> ProjectRulesTable = BuildLookupTableForRules(ProjectOpRules.Rules);
///
/// A lookup table built only from rules that use key info
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> PostJoinEliminationRulesTable = BuildLookupTableForRules(PostJoinEliminationRules);
///
/// A lookup table built only from rules that rely on nullability of vars and other rules
/// that may be able to perform simplificatios if these have been applied.
/// The lookup table is an array indexed by OpType and each entry has a list of rules.
///
internal static readonly ReadOnlyCollection> NullabilityRulesTable = BuildLookupTableForRules(NullabilityRules);
///
/// A look-up table of rules that may cause modifications such that projection pruning may be useful
/// after they have been applied.
///
internal static readonly HashSet RulesRequiringProjectionPruning = InitializeRulesRequiringProjectionPruning();
///
/// A look-up table of rules that may cause modifications such that reapplying the nullability rules
/// may be useful after they have been applied.
///
internal static readonly HashSet RulesRequiringNullabilityRulesToBeReapplied = InitializeRulesRequiringNullabilityRulesToBeReapplied();
#region private state maintenance
private static List allRules;
private static List AllRules
{
get
{
if (allRules == null)
{
allRules = new List();
allRules.AddRange(ScalarOpRules.Rules);
allRules.AddRange(FilterOpRules.Rules);
allRules.AddRange(ProjectOpRules.Rules);
allRules.AddRange(ApplyOpRules.Rules);
allRules.AddRange(JoinOpRules.Rules);
allRules.AddRange(SingleRowOpRules.Rules);
allRules.AddRange(SetOpRules.Rules);
allRules.AddRange(GroupByOpRules.Rules);
allRules.AddRange(SortOpRules.Rules);
allRules.AddRange(ConstrainedSortOpRules.Rules);
allRules.AddRange(DistinctOpRules.Rules);
}
return allRules;
}
}
private static List postJoinEliminationRules;
private static List PostJoinEliminationRules
{
get
{
if (postJoinEliminationRules == null)
{
postJoinEliminationRules = new List();
postJoinEliminationRules.AddRange(ProjectOpRules.Rules); //these don't use key info per-se, but can help after the distinct op rules.
postJoinEliminationRules.AddRange(DistinctOpRules.Rules);
postJoinEliminationRules.AddRange(FilterOpRules.Rules);
postJoinEliminationRules.AddRange(JoinOpRules.Rules);
postJoinEliminationRules.AddRange(NullabilityRules);
}
return postJoinEliminationRules;
}
}
private static List nullabilityRules;
private static List NullabilityRules
{
get
{
if (nullabilityRules == null)
{
nullabilityRules = new List();
nullabilityRules.Add(ScalarOpRules.Rule_IsNullOverVarRef);
nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred1);
nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred2);
nullabilityRules.Add(ScalarOpRules.Rule_SimplifyCase);
}
return nullabilityRules;
}
}
private static ReadOnlyCollection> BuildLookupTableForRules(IEnumerable rules)
{
ReadOnlyCollection NoRules = new ReadOnlyCollection(new InternalTrees.Rule[0]);
List[] lookupTable = new List[(int)OpType.MaxMarker];
foreach (InternalTrees.Rule rule in rules)
{
List opRules = lookupTable[(int)rule.RuleOpType];
if (opRules == null)
{
opRules = new List();
lookupTable[(int)rule.RuleOpType] = opRules;
}
opRules.Add(rule);
}
ReadOnlyCollection[] rulesPerType = new ReadOnlyCollection[lookupTable.Length];
for (int i = 0; i < lookupTable.Length; ++i)
{
if (null != lookupTable[i])
{
rulesPerType[i] = new ReadOnlyCollection(lookupTable[i].ToArray());
}
else
{
rulesPerType[i] = NoRules;
}
}
return new ReadOnlyCollection>(rulesPerType);
}
private static HashSet InitializeRulesRequiringProjectionPruning()
{
HashSet rulesRequiringProjectionPruning = new HashSet();
rulesRequiringProjectionPruning.Add(ApplyOpRules.Rule_OuterApplyOverProject);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject1);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_CrossJoinOverProject2);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject1);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_InnerJoinOverProject2);
rulesRequiringProjectionPruning.Add(JoinOpRules.Rule_OuterJoinOverProject2);
rulesRequiringProjectionPruning.Add(ProjectOpRules.Rule_ProjectWithNoLocalDefs);
rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterOverProject);
rulesRequiringProjectionPruning.Add(FilterOpRules.Rule_FilterWithConstantPredicate);
rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOverProject);
rulesRequiringProjectionPruning.Add(GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions);
return rulesRequiringProjectionPruning;
}
private static HashSet InitializeRulesRequiringNullabilityRulesToBeReapplied()
{
HashSet rulesRequiringNullabilityRulesToBeReapplied = new HashSet();
rulesRequiringNullabilityRulesToBeReapplied.Add(FilterOpRules.Rule_FilterOverLeftOuterJoin);
return rulesRequiringNullabilityRulesToBeReapplied;
}
#endregion
///
/// Apply the rules that belong to the specified group to the given query tree.
///
///
///
internal static bool Process(PlanCompiler compilerState, TransformationRulesGroup rulesGroup)
{
ReadOnlyCollection> rulesTable = null;
switch (rulesGroup)
{
case TransformationRulesGroup.All:
rulesTable = AllRulesTable;
break;
case TransformationRulesGroup.PostJoinElimination:
rulesTable = PostJoinEliminationRulesTable;
break;
case TransformationRulesGroup.Project:
rulesTable = ProjectRulesTable;
break;
}
// If any rule has been applied after which reapplying nullability rules may be useful,
// reapply nullability rules.
bool projectionPrunningRequired;
if (Process(compilerState, rulesTable, out projectionPrunningRequired))
{
bool projectionPrunningRequired2;
Process(compilerState, NullabilityRulesTable, out projectionPrunningRequired2);
projectionPrunningRequired = projectionPrunningRequired || projectionPrunningRequired2;
}
return projectionPrunningRequired;
}
///
/// Apply the rules that belong to the specified rules table to the given query tree.
///
///
///
/// is projection pruning required after the rule application
/// Whether any rule has been applied after which reapplying nullability rules may be useful
private static bool Process(PlanCompiler compilerState, ReadOnlyCollection> rulesTable, out bool projectionPruningRequired)
{
RuleProcessor ruleProcessor = new RuleProcessor();
TransformationRulesContext context = new TransformationRulesContext(compilerState);
compilerState.Command.Root = ruleProcessor.ApplyRulesToSubtree(context, rulesTable, compilerState.Command.Root);
projectionPruningRequired = context.ProjectionPrunningRequired;
return context.ReapplyNullabilityRules;
}
}
///
/// Available groups of rules, not necessarily mutually exclusive
///
internal enum TransformationRulesGroup
{
All,
Project,
PostJoinElimination
}
#region ScalarOpRules
///
/// Transformation rules for ScalarOps
///
internal static class ScalarOpRules
{
#region CaseOp Rules
internal static readonly SimpleRule Rule_SimplifyCase = new SimpleRule(OpType.Case, ProcessSimplifyCase);
internal static readonly SimpleRule Rule_FlattenCase = new SimpleRule(OpType.Case, ProcessFlattenCase);
///
/// We perform the following simple transformation for CaseOps. If every single
/// then/else expression in the CaseOp is equivalent, then we can simply replace
/// the Op with the first then/expression. Specifically,
/// case when w1 then t1 when w2 then t2 ... when wn then tn else e end
/// => t1
/// assuming that t1 is equivalent to t2 is equivalent to ... to e
///
/// Rule Processing context
/// The current subtree for the CaseOp
/// the (possibly) modified subtree
/// true, if we performed any transformations
static bool ProcessSimplifyCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
{
CaseOp caseOp = (CaseOp)caseOpNode.Op;
newNode = caseOpNode;
//
// Can I collapse the entire case-expression into a single expression - yes,
// if all the then/else clauses are the same expression
//
if (ProcessSimplifyCase_Collapse(caseOp, caseOpNode, out newNode))
{
return true;
}
//
// Can I remove any unnecessary when-then pairs ?
//
if (ProcessSimplifyCase_EliminateWhenClauses(context, caseOp, caseOpNode, out newNode))
{
return true;
}
// Nothing else I can think of
return false;
}
///
/// Try and collapse the case expression into a single expression.
/// If every single then/else expression in the CaseOp is equivalent, then we can
/// simply replace the CaseOp with the first then/expression. Specifically,
/// case when w1 then t1 when w2 then t2 ... when wn then tn else e end
/// => t1
/// if t1 is equivalent to t2 is equivalent to ... to e
///
/// the current caseOp
/// current subtree
/// new subtree
/// true, if we performed a transformation
private static bool ProcessSimplifyCase_Collapse(CaseOp caseOp, Node caseOpNode, out Node newNode)
{
newNode = caseOpNode;
Node firstThenNode = caseOpNode.Child1;
Node elseNode = caseOpNode.Children[caseOpNode.Children.Count - 1];
if (!firstThenNode.IsEquivalent(elseNode))
{
return false;
}
for (int i = 3; i < caseOpNode.Children.Count - 1; i += 2)
{
if (!caseOpNode.Children[i].IsEquivalent(firstThenNode))
{
return false;
}
}
// All nodes are equivalent - simply return the first then node
newNode = firstThenNode;
return true;
}
///
/// Try and remove spurious branches from the case expression.
/// If any of the WHEN clauses is the 'FALSE' expression, simply remove that
/// branch (when-then pair) from the case expression.
/// If any of the WHEN clauses is the 'TRUE' expression, then all branches to the
/// right of it are irrelevant - eliminate them. Eliminate this branch as well,
/// and make the THEN expression of this branch the ELSE expression for the entire
/// Case expression. If the WHEN expression represents the first branch, then
/// replace the entire case expression by the corresponding THEN expression
///
/// rule processing context
/// current caseOp
/// Current subtree
/// the new subtree
/// true, if there was a transformation
private static bool ProcessSimplifyCase_EliminateWhenClauses(RuleProcessingContext context, CaseOp caseOp, Node caseOpNode, out Node newNode)
{
List newNodeArgs = null;
newNode = caseOpNode;
for (int i = 0; i < caseOpNode.Children.Count; )
{
// Special handling for the else clause
if (i == caseOpNode.Children.Count - 1)
{
// If the else clause is a SoftCast then we do not attempt to simplify
// the case operation, since this may change the result type.
// This really belongs in more general SoftCastOp logic in the CTreeGenerator
// that converts SoftCasts that could affect the result type of the query into
// a real cast or a trivial case statement, to preserve the result type.
// This is tracked by SQL PT Work Item #300003327.
if (OpType.SoftCast == caseOpNode.Children[i].Op.OpType)
{
return false;
}
if (newNodeArgs != null)
{
newNodeArgs.Add(caseOpNode.Children[i]);
}
break;
}
// If the current then clause is a SoftCast then we do not attempt to simplify
// the case operation, since this may change the result type.
// Again, this really belongs in the CTreeGenerator as per SQL PT Work Item #300003327.
if (OpType.SoftCast == caseOpNode.Children[i + 1].Op.OpType)
{
return false;
}
// Check to see if the when clause is a ConstantPredicate
if (caseOpNode.Children[i].Op.OpType != OpType.ConstantPredicate)
{
if (newNodeArgs != null)
{
newNodeArgs.Add(caseOpNode.Children[i]);
newNodeArgs.Add(caseOpNode.Children[i + 1]);
}
i += 2;
continue;
}
// Found a when-clause which is a constant predicate
ConstantPredicateOp constPred = (ConstantPredicateOp)caseOpNode.Children[i].Op;
// Create the newArgs list, if we haven't done so already
if (newNodeArgs == null)
{
newNodeArgs = new List();
for (int j = 0; j < i; j++)
{
newNodeArgs.Add(caseOpNode.Children[j]);
}
}
// If the when-clause is the "true" predicate, then we simply ignore all
// the succeeding arguments. We make the "then" clause of this when-clause
// as the "else-clause" of the resulting caseOp
if (constPred.IsTrue)
{
newNodeArgs.Add(caseOpNode.Children[i + 1]);
break;
}
else
{
// Otherwise, we simply skip the when-then pair
PlanCompiler.Assert(constPred.IsFalse, "constant predicate must be either true or false");
i += 2;
continue;
}
}
// Did we see any changes? Simply return
if (newNodeArgs == null)
{
return false;
}
// Otherwise, we did do some processing
PlanCompiler.Assert(newNodeArgs.Count > 0, "new args list must not be empty");
// Is there only one expression in the args list - simply return that expression
if (newNodeArgs.Count == 1)
{
newNode = newNodeArgs[0];
}
else
{
newNode = context.Command.CreateNode(caseOp, newNodeArgs);
}
return true;
}
///
/// If the else clause of the CaseOp is another CaseOp, when two can be collapsed into one.
/// In particular,
///
/// CASE
/// WHEN W1 THEN T1
/// WHEN W2 THEN T2 ...
/// ELSE (CASE
/// WHEN WN1 THEN TN1, …
/// ELSE E)
///
/// Is transformed into
///
/// CASE
/// WHEN W1 THEN T1
/// WHEN W2 THEN T2 ...
/// WHEN WN1 THEN TN1 ...
/// ELSE E
///
/// the current caseOp
/// current subtree
/// new subtree
/// true, if we performed a transformation
static bool ProcessFlattenCase(RuleProcessingContext context, Node caseOpNode, out Node newNode)
{
newNode = caseOpNode;
Node elseChild = caseOpNode.Children[caseOpNode.Children.Count - 1];
if (elseChild.Op.OpType != OpType.Case)
{
return false;
}
//
// Flatten the case statements.
// The else child is removed from the outer CaseOp op
// and the else child's children are reparented to the outer CaseOp
// Node info recomputation does not need to happen, the outer CaseOp
// node still has the same descendants.
//
caseOpNode.Children.RemoveAt(caseOpNode.Children.Count - 1);
caseOpNode.Children.AddRange(elseChild.Children);
return true;
}
#endregion
#region EqualsOverConstant Rules
internal static readonly PatternMatchRule Rule_EqualsOverConstant =
new PatternMatchRule(new Node(ComparisonOp.PatternEq,
new Node(InternalConstantOp.Pattern),
new Node(InternalConstantOp.Pattern)),
ProcessComparisonsOverConstant);
///
/// Convert an Equals(X, Y) to a "true" predicate if X=Y, or a "false" predicate if X!=Y
/// Convert a NotEquals(X,Y) in the reverse fashion
///
/// Rule processing context
/// current node
/// possibly modified subtree
/// true, if transformation was successful
static bool ProcessComparisonsOverConstant(RuleProcessingContext context, Node node, out Node newNode)
{
newNode = node;
PlanCompiler.Assert(node.Op.OpType == OpType.EQ || node.Op.OpType == OpType.NE, "unexpected comparison op type?");
bool? comparisonStatus = node.Child0.Op.IsEquivalent(node.Child1.Op);
// Don't mess with nulls or with non-internal constants
if (comparisonStatus == null)
{
return false;
}
bool result = (node.Op.OpType == OpType.EQ) ? (bool)comparisonStatus : !((bool)comparisonStatus);
ConstantPredicateOp newOp = context.Command.CreateConstantPredicateOp(result);
newNode = context.Command.CreateNode(newOp);
return true;
}
#endregion
#region LikeOp Rules
private static bool? MatchesPattern(string str, string pattern)
{
// What we're trying to see is if the pattern is something that ends with a '%'
// And if the "str" is something that matches everything before that
// Make sure that the terminal character of the pattern is a '%' character. Also
// ensure that this character does not occur anywhere else. And finally, ensure
// that the pattern is atmost one character longer than the string itself
int wildCardIndex = pattern.IndexOf('%');
if ((wildCardIndex == -1) ||
(wildCardIndex != pattern.Length - 1) ||
(pattern.Length > str.Length + 1))
{
return null;
}
bool match = true;
int i = 0;
for (i = 0; i < str.Length && i < pattern.Length - 1; i++)
{
if (pattern[i] != str[i])
{
match = false;
break;
}
}
return match;
}
internal static readonly PatternMatchRule Rule_LikeOverConstants =
new PatternMatchRule(new Node(LikeOp.Pattern,
new Node(InternalConstantOp.Pattern),
new Node(InternalConstantOp.Pattern),
new Node(NullOp.Pattern)),
ProcessLikeOverConstant);
static bool ProcessLikeOverConstant(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
InternalConstantOp patternOp = (InternalConstantOp)n.Child1.Op;
InternalConstantOp strOp = (InternalConstantOp)n.Child0.Op;
string str = (string)strOp.Value;
string pattern = (string)patternOp.Value;
bool? match = MatchesPattern((string)strOp.Value, (string)patternOp.Value);
if (match == null)
{
return false;
}
ConstantPredicateOp constOp = context.Command.CreateConstantPredicateOp((bool)match);
newNode = context.Command.CreateNode(constOp);
return true;
}
#endregion
#region LogicalOp (and,or,not) Rules
internal static readonly PatternMatchRule Rule_AndOverConstantPred1 =
new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern)),
ProcessAndOverConstantPredicate1);
internal static readonly PatternMatchRule Rule_AndOverConstantPred2 =
new PatternMatchRule(new Node(ConditionalOp.PatternAnd,
new Node(ConstantPredicateOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessAndOverConstantPredicate2);
internal static readonly PatternMatchRule Rule_OrOverConstantPred1 =
new PatternMatchRule(new Node(ConditionalOp.PatternOr,
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern)),
ProcessOrOverConstantPredicate1);
internal static readonly PatternMatchRule Rule_OrOverConstantPred2 =
new PatternMatchRule(new Node(ConditionalOp.PatternOr,
new Node(ConstantPredicateOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessOrOverConstantPredicate2);
internal static readonly PatternMatchRule Rule_NotOverConstantPred =
new PatternMatchRule(new Node(ConditionalOp.PatternNot,
new Node(ConstantPredicateOp.Pattern)),
ProcessNotOverConstantPredicate);
///
/// Transform
/// AND(x, true) => x;
/// AND(true, x) => x
/// AND(x, false) => false
/// AND(false, x) => false
///
///
/// Rule Processing context
/// Current LogOp (And, Or, Not) node
/// constant predicate node
/// The other child of the LogOp (possibly null)
/// new subtree
/// transformation status
static bool ProcessLogOpOverConstant(RuleProcessingContext context, Node node,
Node constantPredicateNode, Node otherNode,
out Node newNode)
{
PlanCompiler.Assert(constantPredicateNode != null, "null constantPredicateOp?");
ConstantPredicateOp pred = (ConstantPredicateOp)constantPredicateNode.Op;
switch (node.Op.OpType)
{
case OpType.And:
newNode = pred.IsTrue ? otherNode : constantPredicateNode;
break;
case OpType.Or:
newNode = pred.IsTrue ? constantPredicateNode : otherNode;
break;
case OpType.Not:
PlanCompiler.Assert(otherNode == null, "Not Op with more than 1 child. Gasp!");
newNode = context.Command.CreateNode(context.Command.CreateConstantPredicateOp(!pred.Value));
break;
default:
PlanCompiler.Assert(false, "Unexpected OpType - " + node.Op.OpType);
newNode = null;
break;
}
return true;
}
static bool ProcessAndOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
}
static bool ProcessAndOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
}
static bool ProcessOrOverConstantPredicate1(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child1, node.Child0, out newNode);
}
static bool ProcessOrOverConstantPredicate2(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child0, node.Child1, out newNode);
}
static bool ProcessNotOverConstantPredicate(RuleProcessingContext context, Node node, out Node newNode)
{
return ProcessLogOpOverConstant(context, node, node.Child0, null, out newNode);
}
#endregion
#region IsNull Rules
internal static readonly PatternMatchRule Rule_IsNullOverConstant =
new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
new Node(InternalConstantOp.Pattern)),
ProcessIsNullOverConstant);
internal static readonly PatternMatchRule Rule_IsNullOverNullSentinel =
new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
new Node(NullSentinelOp.Pattern)),
ProcessIsNullOverConstant);
///
/// Convert a
/// IsNull(constant)
/// to just the
/// False predicate
///
///
///
/// new subtree
///
/// Convert an IsNull(null) to just the 'true' predicate
///
///
///
/// new subtree
///
/// eliminates nested null casts into a single cast of the outermost cast type.
/// basically the transformation applied is: cast(null[x] as T) => null[t]
///
///
///
/// modified subtree
///
/// Convert a
/// IsNull(VarRef(v))
/// to just the
/// False predicate
///
/// if v is guaranteed to be non nullable.
///
///
///
/// new subtree
///
/// Transformation rules for FilterOps
///
internal static class FilterOpRules
{
#region Helpers
///
/// Split up a predicate into 2 parts - the pushdown and the non-pushdown predicate.
///
/// If the filter node has no external references *and* the "columns" parameter is null,
/// then the entire predicate can be pushed down
///
/// We then compute the set of valid column references - if the "columns" parameter
/// is non-null, this set is used. Otherwise, we get the definitions of the
/// input relop node of the filterOp, and use that.
///
/// We use this list of valid column references to identify which parts of the filter
/// predicate can be pushed down - only those parts of the predicate that do not
/// reference anything beyond these columns are considered for pushdown. The rest are
/// stuffed into the nonPushdownPredicate output parameter
///
///
/// Command object
/// the FilterOp subtree
/// (Optional) List of columns to consider for "pushdown"
/// (output) Part of the predicate that cannot be pushed down
/// part of the predicate that can be pushed down
private static Node GetPushdownPredicate(Command command, Node filterNode, VarVec columns, out Node nonPushdownPredicateNode)
{
Node pushdownPredicateNode = filterNode.Child1;
nonPushdownPredicateNode = null;
ExtendedNodeInfo filterNodeInfo = command.GetExtendedNodeInfo(filterNode);
if (columns == null && filterNodeInfo.ExternalReferences.IsEmpty)
{
return pushdownPredicateNode;
}
if (columns == null)
{
ExtendedNodeInfo inputNodeInfo = command.GetExtendedNodeInfo(filterNode.Child0);
columns = inputNodeInfo.Definitions;
}
Predicate predicate = new Predicate(command, pushdownPredicateNode);
Predicate nonPushdownPredicate;
predicate = predicate.GetSingleTablePredicates(columns, out nonPushdownPredicate);
pushdownPredicateNode = predicate.BuildAndTree();
nonPushdownPredicateNode = nonPushdownPredicate.BuildAndTree();
return pushdownPredicateNode;
}
#endregion
#region FilterOverFilter
internal static readonly PatternMatchRule Rule_FilterOverFilter =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverFilter);
///
/// Convert Filter(Filter(X, p1), p2) => Filter(X, (p1 and p2))
///
/// rule processing context
/// FilterOp node
/// modified subtree
/// transformed subtree
static bool ProcessFilterOverFilter(RuleProcessingContext context, Node filterNode, out Node newNode)
{
Node newAndNode = context.Command.CreateNode(
context.Command.CreateConditionalOp(OpType.And),
filterNode.Child0.Child1, filterNode.Child1);
newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), filterNode.Child0.Child0, newAndNode);
return true;
}
#endregion
#region FilterOverProject
internal static readonly PatternMatchRule Rule_FilterOverProject =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverProject);
///
/// Convert Filter(Project(X, ...), p) => Project(Filter(X, p'), ...)
///
/// Rule processing context
/// FilterOp subtree
/// modified subtree
/// transformed subtree
static bool ProcessFilterOverProject(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
Node predicateNode = filterNode.Child1;
//
// If the filter is a constant predicate, then don't push the filter below the
// project
//
if (predicateNode.Op.OpType == OpType.ConstantPredicate)
{
// There's a different rule to process this case. Simply return
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
//
// check to see that this is a simple predicate
//
Dictionary varRefMap = new Dictionary();
if (!trc.IsScalarOpTree(predicateNode, varRefMap))
{
return false;
}
//
// check to see if all expressions in the project can be inlined
//
Node projectNode = filterNode.Child0;
Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
if (varMap == null)
{
return false;
}
//
// Try to remap the predicate in terms of the definitions of the Vars
//
Node remappedPredicateNode = trc.ReMap(predicateNode, varMap);
//
// Now push the filter below the project
//
Node newFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), projectNode.Child0, remappedPredicateNode);
Node newProjectNode = trc.Command.CreateNode(projectNode.Op, newFilterNode, projectNode.Child1);
newNode = newProjectNode;
return true;
}
#endregion
#region FilterOverSetOp
internal static readonly PatternMatchRule Rule_FilterOverUnionAll =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(UnionAllOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverSetOp);
internal static readonly PatternMatchRule Rule_FilterOverIntersect =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(IntersectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverSetOp);
internal static readonly PatternMatchRule Rule_FilterOverExcept =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(ExceptOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverSetOp);
///
/// Transform Filter(UnionAll(X1, X2), p) => UnionAll(Filter(X1, p1), Filter(X, p2))
/// Filter(Intersect(X1, X2), p) => Intersect(Filter(X1, p1), Filter(X2, p2))
/// Filter(Except(X1, X2), p) => Except(Filter(X1, p1), X2)
/// where p1 and p2 are the "mapped" versions of the predicate "p" for each branch
///
/// Rule processing context
/// FilterOp subtree
/// modified subtree
/// true, if successful transformation
static bool ProcessFilterOverSetOp(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
//
// Identify parts of the filter predicate that can be pushed down, and parts that
// cannot be. If nothing can be pushed down, then return
//
Node nonPushdownPredicate;
Node pushdownPredicate = GetPushdownPredicate(trc.Command, filterNode, null, out nonPushdownPredicate);
if (pushdownPredicate == null)
{
return false;
}
// Handle only simple predicates
if (!trc.IsScalarOpTree(pushdownPredicate))
{
return false;
}
//
// Now push the predicate (the part that can be pushed down) into each of the
// branches (as appropriate)
//
Node setOpNode = filterNode.Child0;
SetOp setOp = (SetOp)setOpNode.Op;
List newSetOpChildren = new List();
int branchId = 0;
foreach (VarMap varMap in setOp.VarMap)
{
// For exceptOp, the filter should only be pushed below the zeroth child
if (setOp.OpType == OpType.Except && branchId == 1)
{
newSetOpChildren.Add(setOpNode.Child1);
break;
}
Dictionary remapMap = new Dictionary();
foreach (KeyValuePair kv in varMap)
{
Node varRefNode = trc.Command.CreateNode(trc.Command.CreateVarRefOp(kv.Value));
remapMap.Add(kv.Key, varRefNode);
}
//
// Now fix up the predicate.
// Make a copy of the predicate first - except if we're dealing with the last
// branch, in which case, we can simply reuse the predicate
//
Node predicateNode = pushdownPredicate;
if (branchId == 0 && filterNode.Op.OpType != OpType.Except)
{
predicateNode = trc.Copy(predicateNode);
}
Node newPredicateNode = trc.ReMap(predicateNode, remapMap);
trc.Command.RecomputeNodeInfo(newPredicateNode);
// create a new filter node below the setOp child
Node newFilterNode = trc.Command.CreateNode(
trc.Command.CreateFilterOp(),
setOpNode.Children[branchId],
newPredicateNode);
newSetOpChildren.Add(newFilterNode);
branchId++;
}
Node newSetOpNode = trc.Command.CreateNode(setOpNode.Op, newSetOpChildren);
//
// We've now pushed down the relevant parts of the filter below the SetOps
// We may still however some predicates left over - create a new filter node
// to account for that
//
if (nonPushdownPredicate != null)
{
newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newSetOpNode, nonPushdownPredicate);
}
else
{
newNode = newSetOpNode;
}
return true;
}
#endregion
#region FilterOverDistinct
internal static readonly PatternMatchRule Rule_FilterOverDistinct =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(DistinctOp.Pattern,
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverDistinct);
///
/// Transforms Filter(Distinct(x), p) => Filter(Distinct(Filter(X, p1), p2)
/// where p2 is the part of the filter that can be pushed down, while p1 represents
/// any external references
///
/// Rule processing context
/// FilterOp subtree
/// modified subtree
/// Transformation status
static bool ProcessFilterOverDistinct(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
//
// Split up the filter predicate into two parts - the part that can be pushed down
// and the part that can't. If there is no part that can be pushed down, simply return
//
Node nonPushdownPredicate;
Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, null, out nonPushdownPredicate);
if (pushdownPredicate == null)
{
return false;
}
//
// Create a new filter node below the current distinct node for the predicate
// that can be pushed down - create a new distinct node as well
//
Node distinctNode = filterNode.Child0;
Node pushdownFilterNode = context.Command.CreateNode(context.Command.CreateFilterOp(), distinctNode.Child0, pushdownPredicate);
Node newDistinctNode = context.Command.CreateNode(distinctNode.Op, pushdownFilterNode);
//
// If we have a predicate part that cannot be pushed down, build up a new
// filter node above the new Distinct op that we just created
//
if (nonPushdownPredicate != null)
{
newNode = context.Command.CreateNode(context.Command.CreateFilterOp(), newDistinctNode, nonPushdownPredicate);
}
else
{
newNode = newDistinctNode;
}
return true;
}
#endregion
#region FilterOverGroupBy
internal static readonly PatternMatchRule Rule_FilterOverGroupBy =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(GroupByOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverGroupBy);
///
/// Transforms Filter(GroupBy(X, k1.., a1...), p) =>
/// Filter(GroupBy(Filter(X, p1'), k1..., a1...), p2)
/// p1 and p2 represent the parts of p that can and cannot be pushed down
/// respectively - specifically, p1 must only reference the key columns from
/// the GroupByOp.
/// "p1'" is the mapped version of "p1",
///
/// Rule processing context
/// Current FilterOp subtree
/// modified subtree
/// Transformation status
static bool ProcessFilterOverGroupBy(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
Node groupByNode = filterNode.Child0;
GroupByOp groupByOp = (GroupByOp)groupByNode.Op;
TransformationRulesContext trc = (TransformationRulesContext)context;
// Check to see that we have a simple predicate
Dictionary varRefMap = new Dictionary();
if (!trc.IsScalarOpTree(filterNode.Child1, varRefMap))
{
return false;
}
//
// Split up the predicate into two parts - the part that can be pushed down below
// the groupByOp (specifically, the part that only refers to keys of the groupByOp),
// and the part that cannot be pushed below
// If nothing can be pushed below, quit now
//
Node nonPushdownPredicate;
Node pushdownPredicate = GetPushdownPredicate(context.Command, filterNode, groupByOp.Keys, out nonPushdownPredicate);
if (pushdownPredicate == null)
{
return false;
}
//
// We need to push the filter down; but we need to remap the predicate, so
// that any references to variables defined locally by the groupBy are fixed up
// Make sure that the predicate is not too complex to remap
//
Dictionary varMap = trc.GetVarMap(groupByNode.Child1, varRefMap);
if (varMap == null)
{
return false; // complex expressions
}
Node remappedPushdownPredicate = trc.ReMap(pushdownPredicate, varMap);
//
// Push the filter below the groupBy now
//
Node subFilterNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), groupByNode.Child0, remappedPushdownPredicate);
Node newGroupByNode = trc.Command.CreateNode(groupByNode.Op, subFilterNode, groupByNode.Child1, groupByNode.Child2);
//
// If there was any part of the original predicate that could not be pushed down,
// create a new filterOp node above the new groupBy node to represent that
// predicate
//
if (nonPushdownPredicate == null)
{
newNode = newGroupByNode;
}
else
{
newNode = trc.Command.CreateNode(trc.Command.CreateFilterOp(), newGroupByNode, nonPushdownPredicate);
}
return true;
}
#endregion
#region FilterOverJoin
internal static readonly PatternMatchRule Rule_FilterOverCrossJoin =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverJoin);
internal static readonly PatternMatchRule Rule_FilterOverInnerJoin =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(InnerJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverJoin);
internal static readonly PatternMatchRule Rule_FilterOverLeftOuterJoin =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(LeftOuterJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverJoin);
///
/// Transform Filter()
///
/// Rule Processing context
/// Current FilterOp subtree
/// Modified subtree
/// Transformation status
static bool ProcessFilterOverJoin(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
//
// Have we shut off filter pushdown for this node? Return
//
if (trc.IsFilterPushdownSuppressed(filterNode))
{
return false;
}
Node joinNode = filterNode.Child0;
Op joinOp = joinNode.Op;
Node leftInputNode = joinNode.Child0;
Node rightInputNode = joinNode.Child1;
Command command = trc.Command;
bool needsTransformation = false;
//
// If we're dealing with an outer-join, first check to see if the current
// predicate preserves nulls for the right table.
// If it doesn't then we can convert the outer join into an inner join,
// and then continue with the rest of our processing here
//
ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(rightInputNode);
Predicate predicate = new Predicate(command, filterNode.Child1);
if (joinOp.OpType == OpType.LeftOuterJoin)
{
if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
{
joinOp = command.CreateInnerJoinOp();
needsTransformation = true;
}
}
ExtendedNodeInfo leftTableInfo = command.GetExtendedNodeInfo(leftInputNode);
//
// Check to see if the predicate contains any "single-table-filters". In those
// cases, we could simply push that filter down to the child.
// We can do this for inner joins and cross joins - for both inputs.
// For left-outer joins, however, we can only do this for the left-side input
// Further note that we only want to do the pushdown if it will help us - if
// the join input is a ScanTable (or some other cases), then it doesn't help us.
//
Node leftSingleTablePredicateNode = null;
if (leftInputNode.Op.OpType != OpType.ScanTable)
{
Predicate leftSingleTablePredicates = predicate.GetSingleTablePredicates(leftTableInfo.Definitions, out predicate);
leftSingleTablePredicateNode = leftSingleTablePredicates.BuildAndTree();
}
Node rightSingleTablePredicateNode = null;
if ((rightInputNode.Op.OpType != OpType.ScanTable) &&
(joinOp.OpType != OpType.LeftOuterJoin))
{
Predicate rightSingleTablePredicates = predicate.GetSingleTablePredicates(rightTableNodeInfo.Definitions, out predicate);
rightSingleTablePredicateNode = rightSingleTablePredicates.BuildAndTree();
}
//
// Now check to see if the predicate contains some "join predicates". We can
// add these to the existing join predicate (if any).
// We can only do this for inner joins and cross joins - not for LOJs
//
Node newJoinPredicateNode = null;
if (joinOp.OpType == OpType.CrossJoin || joinOp.OpType == OpType.InnerJoin)
{
Predicate joinPredicate = predicate.GetJoinPredicates(leftTableInfo.Definitions, rightTableNodeInfo.Definitions, out predicate);
newJoinPredicateNode = joinPredicate.BuildAndTree();
}
//
// Now for the dirty work. We've identified some predicates that could be pushed
// into the left table, some predicates that could be pushed into the right table
// and some that could become join predicates.
//
if (leftSingleTablePredicateNode != null)
{
leftInputNode = command.CreateNode(command.CreateFilterOp(), leftInputNode, leftSingleTablePredicateNode);
needsTransformation = true;
}
if (rightSingleTablePredicateNode != null)
{
rightInputNode = command.CreateNode(command.CreateFilterOp(), rightInputNode, rightSingleTablePredicateNode);
needsTransformation = true;
}
// Identify the new join predicate
if (newJoinPredicateNode != null)
{
needsTransformation = true;
if (joinOp.OpType == OpType.CrossJoin)
{
joinOp = command.CreateInnerJoinOp();
}
else
{
PlanCompiler.Assert(joinOp.OpType == OpType.InnerJoin, "unexpected non-InnerJoin?");
newJoinPredicateNode = PlanCompilerUtil.CombinePredicates(joinNode.Child2, newJoinPredicateNode, command);
}
}
else
{
newJoinPredicateNode = (joinOp.OpType == OpType.CrossJoin) ? null : joinNode.Child2;
}
//
// If nothing has changed, then just return the current node. Otherwise,
// we will loop forever
//
if (!needsTransformation)
{
return false;
}
Node newJoinNode;
//
// Finally build up a new join node
//
if (joinOp.OpType == OpType.CrossJoin)
{
newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode);
}
else
{
newJoinNode = command.CreateNode(joinOp, leftInputNode, rightInputNode, newJoinPredicateNode);
}
//
// Build up a new filterNode above this join node. But only if we have a filter left
//
Node newFilterPredicateNode = predicate.BuildAndTree();
if (newFilterPredicateNode == null)
{
newNode = newJoinNode;
}
else
{
newNode = command.CreateNode(command.CreateFilterOp(), newJoinNode, newFilterPredicateNode);
}
return true;
}
#endregion
#region Filter over OuterApply
internal static readonly PatternMatchRule Rule_FilterOverOuterApply =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessFilterOverOuterApply);
///
/// Convert Filter(OuterApply(X,Y), p) into
/// Filter(CrossApply(X,Y), p)
/// if "p" is not null-preserving for Y (ie) "p" does not preserve null values from Y
///
/// Rule processing context
/// Filter node
/// modified subtree
/// transformation status
static bool ProcessFilterOverOuterApply(RuleProcessingContext context, Node filterNode, out Node newNode)
{
newNode = filterNode;
Node applyNode = filterNode.Child0;
Op applyOp = applyNode.Op;
Node applyRightInputNode = applyNode.Child1;
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
//
// Check to see if the current predicate preserves nulls for the right table.
// If it doesn't then we can convert the outer apply into a cross-apply,
//
ExtendedNodeInfo rightTableNodeInfo = command.GetExtendedNodeInfo(applyRightInputNode);
Predicate predicate = new Predicate(command, filterNode.Child1);
if (!predicate.PreservesNulls(rightTableNodeInfo.Definitions, true))
{
Node newApplyNode = command.CreateNode(command.CreateCrossApplyOp(), applyNode.Child0, applyRightInputNode);
Node newFilterNode = command.CreateNode(command.CreateFilterOp(), newApplyNode, filterNode.Child1);
newNode = newFilterNode;
return true;
}
return false;
}
#endregion
#region FilterWithConstantPredicate
internal static readonly PatternMatchRule Rule_FilterWithConstantPredicate =
new PatternMatchRule(new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern)),
ProcessFilterWithConstantPredicate);
///
/// Convert
/// Filter(X, true) => X
/// Filter(X, false) => Project(Filter(SingleRowTableOp, ...), false)
/// where ... represent variables that are equivalent to the table columns
///
/// Rule processing context
/// Current subtree
/// modified subtree
/// transformation status
static bool ProcessFilterWithConstantPredicate(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
ConstantPredicateOp predOp = (ConstantPredicateOp)n.Child1.Op;
// If we're dealing with a "true" predicate, then simply return the RelOp
// input to the filter
if (predOp.IsTrue)
{
newNode = n.Child0;
return true;
}
PlanCompiler.Assert(predOp.IsFalse, "unexpected non-false predicate?");
// We're dealing with a "false" predicate, then we can get rid of the
// input, and replace it with a dummy project
//
// If the input is already a singlerowtableOp, then there's nothing
// further to do
//
if (n.Child0.Op.OpType == OpType.SingleRowTable ||
(n.Child0.Op.OpType == OpType.Project &&
n.Child0.Child0.Op.OpType == OpType.SingleRowTable))
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
ExtendedNodeInfo childNodeInfo = trc.Command.GetExtendedNodeInfo(n.Child0);
List varDefNodeList = new List();
VarVec newVars = trc.Command.CreateVarVec();
foreach (Var v in childNodeInfo.Definitions)
{
NullOp nullConst = trc.Command.CreateNullOp(v.Type);
Node constNode = trc.Command.CreateNode(nullConst);
Var computedVar;
Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
trc.AddVarMapping(v, computedVar);
newVars.Set(computedVar);
varDefNodeList.Add(varDefNode);
}
// If no vars have been selected out, add a dummy var
if (newVars.IsEmpty)
{
NullOp nullConst = trc.Command.CreateNullOp(trc.Command.BooleanType);
Node constNode = trc.Command.CreateNode(nullConst);
Var computedVar;
Node varDefNode = trc.Command.CreateVarDefNode(constNode, out computedVar);
newVars.Set(computedVar);
varDefNodeList.Add(varDefNode);
}
Node singleRowTableNode = trc.Command.CreateNode(trc.Command.CreateSingleRowTableOp());
n.Child0 = singleRowTableNode;
Node varDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp(), varDefNodeList);
ProjectOp projectOp = trc.Command.CreateProjectOp(newVars);
Node projectNode = trc.Command.CreateNode(projectOp, n, varDefListNode);
projectNode.Child0 = n;
newNode = projectNode;
return true;
}
#endregion
#region All FilterOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
FilterOpRules.Rule_FilterWithConstantPredicate,
FilterOpRules.Rule_FilterOverCrossJoin,
FilterOpRules.Rule_FilterOverDistinct,
FilterOpRules.Rule_FilterOverExcept,
FilterOpRules.Rule_FilterOverFilter,
FilterOpRules.Rule_FilterOverGroupBy,
FilterOpRules.Rule_FilterOverInnerJoin,
FilterOpRules.Rule_FilterOverIntersect,
FilterOpRules.Rule_FilterOverLeftOuterJoin,
FilterOpRules.Rule_FilterOverProject,
FilterOpRules.Rule_FilterOverUnionAll,
FilterOpRules.Rule_FilterOverOuterApply,
};
#endregion
}
#endregion
#region Project Rules
///
/// Transformation rules for ProjectOp
///
internal static class ProjectOpRules
{
#region ProjectOverProject
internal static readonly PatternMatchRule Rule_ProjectOverProject =
new PatternMatchRule(new Node(ProjectOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessProjectOverProject);
///
/// Converts a Project(Project(X, c1,...), d1,...) =>
/// Project(X, d1', d2'...)
/// where d1', d2' etc. are the "mapped" versions of d1, d2 etc.
///
/// Rule processing context
/// Current ProjectOp node
/// modified subtree
/// Transformation status
static bool ProcessProjectOverProject(RuleProcessingContext context, Node projectNode, out Node newNode)
{
newNode = projectNode;
ProjectOp projectOp = (ProjectOp)projectNode.Op;
Node varDefListNode = projectNode.Child1;
Node subProjectNode = projectNode.Child0;
ProjectOp subProjectOp = (ProjectOp)subProjectNode.Op;
TransformationRulesContext trc = (TransformationRulesContext)context;
// If any of the defining expressions is not a scalar op tree, then simply
// quit
Dictionary varRefMap = new Dictionary();
foreach (Node varDefNode in varDefListNode.Children)
{
if (!trc.IsScalarOpTree(varDefNode.Child0, varRefMap))
{
return false;
}
}
Dictionary varMap = trc.GetVarMap(subProjectNode.Child1, varRefMap);
if (varMap == null)
{
return false;
}
// create a new varDefList node...
Node newVarDefListNode = trc.Command.CreateNode(trc.Command.CreateVarDefListOp());
// Remap any local definitions, I have
foreach (Node varDefNode in varDefListNode.Children)
{
// update the defining expression
varDefNode.Child0 = trc.ReMap(varDefNode.Child0, varMap);
trc.Command.RecomputeNodeInfo(varDefNode);
newVarDefListNode.Children.Add(varDefNode);
}
// Now, pull up any definitions of the subProject that I publish myself
ExtendedNodeInfo projectNodeInfo = trc.Command.GetExtendedNodeInfo(projectNode);
foreach (Node chi in subProjectNode.Child1.Children)
{
VarDefOp varDefOp = (VarDefOp)chi.Op;
if (projectNodeInfo.Definitions.IsSet(varDefOp.Var))
{
newVarDefListNode.Children.Add(chi);
}
}
//
// now that we have remapped all our computed vars, simply bypass the subproject
// node
//
projectNode.Child0 = subProjectNode.Child0;
projectNode.Child1 = newVarDefListNode;
return true;
}
#endregion
#region ProjectWithNoLocalDefinitions
internal static readonly PatternMatchRule Rule_ProjectWithNoLocalDefs =
new PatternMatchRule(new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(VarDefListOp.Pattern)),
ProcessProjectWithNoLocalDefinitions);
///
/// Eliminate a ProjectOp that has no local definitions at all and
/// no external references, (ie) if Child1
/// of the ProjectOp (the VarDefListOp child) has no children, then the ProjectOp
/// is serving no useful purpose. Get rid of the ProjectOp, and replace it with its
/// child
///
/// rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessProjectWithNoLocalDefinitions(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
NodeInfo nodeInfo = context.Command.GetNodeInfo(n);
// We cannot eliminate this node because it can break other rules,
// e.g. ProcessApplyOverAnything which relies on existance of external refs to substitute
// CrossApply(x, y) => CrossJoin(x, y). See SQLBU #481719.
if (!nodeInfo.ExternalReferences.IsEmpty)
{
return false;
}
newNode = n.Child0;
return true;
}
#endregion
#region ProjectOpWithSimpleVarRedefinitions
internal static readonly SimpleRule Rule_ProjectOpWithSimpleVarRedefinitions = new SimpleRule(OpType.Project, ProcessProjectWithSimpleVarRedefinitions);
///
/// If the ProjectOp defines some computedVars, but those computedVars are simply
/// redefinitions of other Vars, then eliminate the computedVars.
///
/// Project(X, VarDefList(VarDef(cv1, VarRef(v1)), ...))
/// can be transformed into
/// Project(X, VarDefList(...))
/// where cv1 has now been replaced by v1
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessProjectWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
ProjectOp projectOp = (ProjectOp)n.Op;
if (n.Child1.Children.Count == 0)
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
//
// Check to see if any of the computed Vars defined by this ProjectOp
// are simple redefinitions of other VarRefOps. Consider only those
// VarRefOps that are not "external" references
bool canEliminateSomeVars = false;
foreach (Node varDefNode in n.Child1.Children)
{
Node definingExprNode = varDefNode.Child0;
if (definingExprNode.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
// this is a Var that we should remove
canEliminateSomeVars = true;
break;
}
}
}
// Did we have any redefinitions
if (!canEliminateSomeVars)
{
return false;
}
//
// OK. We've now identified a set of vars that are simple redefinitions.
// Try and replace the computed Vars with the Vars that they're redefining
//
// Lets now build up a new VarDefListNode
List newVarDefNodes = new List();
foreach (Node varDefNode in n.Child1.Children)
{
VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
projectOp.Outputs.Clear(varDefOp.Var);
projectOp.Outputs.Set(varRefOp.Var);
trc.AddVarMapping(varDefOp.Var, varRefOp.Var);
}
else
{
newVarDefNodes.Add(varDefNode);
}
}
// Note: Even if we don't have any local var definitions left, we should not remove
// this project yet because:
// (1) this project node may be prunning out some outputs;
// (2) the rule Rule_ProjectWithNoLocalDefs, would do that later anyway.
// Create a new vardeflist node, and set that as Child1 for the projectOp
Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
n.Child1 = newVarDefListNode;
return true; // some part of the subtree was modified
}
#endregion
#region ProjectOpWithNullSentinel
internal static readonly SimpleRule Rule_ProjectOpWithNullSentinel = new SimpleRule(OpType.Project, ProcessProjectOpWithNullSentinel);
///
/// Tries to remove null sentinel definitions by replacing them to vars that are guaranteed
/// to be non-nullable and of integer type, or with reference to other constants defined in the
/// same project. In particular,
///
/// - If based on the ancestors, the value of the null sentinel can be changed and the
/// input of the project has a var that is guaranteed to be non-nullable and
/// is of integer type, then the definitions of the vars defined as NullSentinels in the ProjectOp
/// are replaced with a reference to that var. I.eg:
///
/// Project(X, VarDefList(VarDef(ns_var, NullSentinel), ...))
/// can be transformed into
/// Project(X, VarDefList(VarDef(ns_var, VarRef(v))...))
/// where v is known to be non-nullable
///
/// - Else, if based on the ancestors, the value of the null sentinel can be changed and
/// the project already has definitions of other int constants, the definitions of the null sentinels
/// are removed and the respective vars are remapped to the var representing the constant.
///
/// - Else, the definitions of the all null sentinels except for one are removed, and the
/// the respective vars are remapped to the remaining null sentinel.
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessProjectOpWithNullSentinel(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
ProjectOp projectOp = (ProjectOp)n.Op;
Node varDefListNode = n.Child1;
if (varDefListNode.Children.Where(c => c.Child0.Op.OpType == OpType.NullSentinel).Count() == 0)
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
ExtendedNodeInfo relOpInputNodeInfo = command.GetExtendedNodeInfo(n.Child0);
Var inputSentinel;
bool reusingConstantFromSameProjectAsSentinel = false;
bool canChangeNullSentinelValue = trc.CanChangeNullSentinelValue;
if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(relOpInputNodeInfo.NonNullableDefinitions, out inputSentinel))
{
reusingConstantFromSameProjectAsSentinel = true;
if (!canChangeNullSentinelValue || !TransformationRulesContext.TryGetInt32Var(n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.Constant || child.Child0.Op.OpType == OpType.InternalConstant).Select(child => ((VarDefOp)(child.Op)).Var), out inputSentinel))
{
inputSentinel = n.Child1.Children.Where(child => child.Child0.Op.OpType == OpType.NullSentinel).Select(child => ((VarDefOp)(child.Op)).Var).FirstOrDefault();
if (inputSentinel == null)
{
return false;
}
}
}
bool modified = false;
for (int i = n.Child1.Children.Count-1; i >= 0; i--)
{
Node varDefNode = n.Child1.Children[i];
Node definingExprNode = varDefNode.Child0;
if (definingExprNode.Op.OpType == OpType.NullSentinel)
{
if (!reusingConstantFromSameProjectAsSentinel)
{
VarRefOp varRefOp = command.CreateVarRefOp(inputSentinel);
varDefNode.Child0 = command.CreateNode(varRefOp);
command.RecomputeNodeInfo(varDefNode);
modified = true;
}
else if (!inputSentinel.Equals(((VarDefOp)varDefNode.Op).Var))
{
projectOp.Outputs.Clear(((VarDefOp)varDefNode.Op).Var);
n.Child1.Children.RemoveAt(i);
trc.AddVarMapping(((VarDefOp)varDefNode.Op).Var, inputSentinel);
modified = true;
}
}
}
if (modified)
{
command.RecomputeNodeInfo(n.Child1);
}
return modified;
}
#endregion
#region All ProjectOp Rules
//The order of the rules is important
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
ProjectOpRules.Rule_ProjectOpWithNullSentinel,
ProjectOpRules.Rule_ProjectOpWithSimpleVarRedefinitions,
ProjectOpRules.Rule_ProjectOverProject,
ProjectOpRules.Rule_ProjectWithNoLocalDefs,
};
#endregion
}
#endregion
#region Apply Rules
///
/// Transformation rules for ApplyOps - CrossApply, OuterApply
///
internal static class ApplyOpRules
{
#region ApplyOverFilter
internal static readonly PatternMatchRule Rule_CrossApplyOverFilter =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessApplyOverFilter);
internal static readonly PatternMatchRule Rule_OuterApplyOverFilter =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessApplyOverFilter);
///
/// Convert CrossApply(X, Filter(Y, p)) => InnerJoin(X, Y, p)
/// OuterApply(X, Filter(Y, p)) => LeftOuterJoin(X, Y, p)
/// if "Y" has no external references to X
///
/// Rule processing context
/// Current ApplyOp
/// transformed subtree
/// Transformation status
static bool ProcessApplyOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node filterNode = applyNode.Child1;
Command command = context.Command;
NodeInfo filterInputNodeInfo = command.GetNodeInfo(filterNode.Child0);
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
//
// check to see if the inputNode to the FilterOp has any external references
// to the left child of the ApplyOp. If it does, we simply return, we
// can't do much more here
//
if (filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
{
return false;
}
//
// We've now gotten to the stage where the only external references (if any)
// are from the filter predicate.
// We can now simply convert the apply into an inner/leftouter join with the
// filter predicate acting as the join condition
//
JoinBaseOp joinOp = null;
if (applyNode.Op.OpType == OpType.CrossApply)
{
joinOp = command.CreateInnerJoinOp();
}
else
{
joinOp = command.CreateLeftOuterJoinOp();
}
newNode = command.CreateNode(joinOp, applyNode.Child0, filterNode.Child0, filterNode.Child1);
return true;
}
internal static readonly PatternMatchRule Rule_OuterApplyOverProjectInternalConstantOverFilter =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(VarDefListOp.Pattern,
new Node(VarDefOp.Pattern,
new Node(InternalConstantOp.Pattern))))),
ProcessOuterApplyOverDummyProjectOverFilter);
internal static readonly PatternMatchRule Rule_OuterApplyOverProjectNullSentinelOverFilter =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(VarDefListOp.Pattern,
new Node(VarDefOp.Pattern,
new Node(NullSentinelOp.Pattern))))),
ProcessOuterApplyOverDummyProjectOverFilter);
///
/// Convert OuterApply(X, Project(Filter(Y, p), constant)) =>
/// LeftOuterJoin(X, Project(Y, constant), p)
/// if "Y" has no external references to X
///
/// In an ideal world, we would be able to push the Project below the Filter,
/// and then have the normal ApplyOverFilter rule handle this - but that causes us
/// problems because we always try to pull up ProjectOp's as high as possible. Hence,
/// the special case for this rule
///
///
/// Rule processing context
/// Current ApplyOp
/// transformed subtree
/// Transformation status
static bool ProcessOuterApplyOverDummyProjectOverFilter(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node projectNode = applyNode.Child1;
ProjectOp projectOp = (ProjectOp)projectNode.Op;
Node filterNode = projectNode.Child0;
Node filterInputNode = filterNode.Child0;
Command command = context.Command;
ExtendedNodeInfo filterInputNodeInfo = command.GetExtendedNodeInfo(filterInputNode);
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
//
// Check if the outputs of the ProjectOp or the inputNode to the FilterOp
// have any external references to the left child of the ApplyOp.
// If they do, we simply return, we can't do much more here
//
if (projectOp.Outputs.Overlaps(applyLeftChildNodeInfo.Definitions) || filterInputNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
{
return false;
}
//
// We've now gotten to the stage where the only external references (if any)
// are from the filter predicate.
// First, push the Project node down below the filter - but make sure that
// all the Vars needed by the Filter are projected out
//
bool capWithProject = false;
Node joinNodeRightInput = null;
//
// Check to see whether there is a sentinel var available - if there is, then
// we can simply move the ProjectOp above the join we're going to construct
// and of course, build a NullIf expression for the constant.
// Otherwise, the ProjectOp will need to be the child of the joinOp that we're
// building - and we'll need to make sure that the ProjectOp projects out
// any vars that are required for the Filter in the first place
//
TransformationRulesContext trc = (TransformationRulesContext)context;
Var sentinelVar;
bool sentinelIsInt32;
if (TransformationRulesContext.TryGetInt32Var(filterInputNodeInfo.NonNullableDefinitions, out sentinelVar))
{
sentinelIsInt32 = true;
}
else
{
sentinelVar = filterInputNodeInfo.NonNullableDefinitions.First;
sentinelIsInt32 = false;
}
if (sentinelVar != null)
{
capWithProject = true;
Node varDefNode = projectNode.Child1.Child0;
if (varDefNode.Child0.Op.OpType == OpType.NullSentinel && sentinelIsInt32 && trc.CanChangeNullSentinelValue)
{
varDefNode.Child0 = context.Command.CreateNode(context.Command.CreateVarRefOp(sentinelVar));
}
else
{
varDefNode.Child0 = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
}
command.RecomputeNodeInfo(varDefNode);
command.RecomputeNodeInfo(projectNode.Child1);
joinNodeRightInput = filterInputNode;
}
else
{
// We need to keep the projectNode - unfortunately
joinNodeRightInput = projectNode;
//
// Make sure that every Var that is needed for the filter predicate
// is captured in the projectOp outputs list
//
NodeInfo filterPredicateNodeInfo = command.GetNodeInfo(filterNode.Child1);
foreach (Var v in filterPredicateNodeInfo.ExternalReferences)
{
if (filterInputNodeInfo.Definitions.IsSet(v))
{
projectOp.Outputs.Set(v);
}
}
projectNode.Child0 = filterInputNode;
}
context.Command.RecomputeNodeInfo(projectNode);
//
// We can now simply convert the apply into an inner/leftouter join with the
// filter predicate acting as the join condition
//
Node joinNode = command.CreateNode(command.CreateLeftOuterJoinOp(), applyNode.Child0, joinNodeRightInput, filterNode.Child1);
if (capWithProject)
{
ExtendedNodeInfo joinNodeInfo = command.GetExtendedNodeInfo(joinNode);
projectNode.Child0 = joinNode;
projectOp.Outputs.Or(joinNodeInfo.Definitions);
newNode = projectNode;
}
else
{
newNode = joinNode;
}
return true;
}
#endregion
#region ApplyOverProject
internal static readonly PatternMatchRule Rule_CrossApplyOverProject =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessCrossApplyOverProject);
///
/// Converts a CrossApply(X, Project(Y, ...)) => Project(CrossApply(X, Y), ...)
/// where the projectVars are simply pulled up
///
/// RuleProcessing context
/// The ApplyOp subtree
/// transformed subtree
/// Transfomation status
static bool ProcessCrossApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node projectNode = applyNode.Child1;
ProjectOp projectOp = (ProjectOp)projectNode.Op as ProjectOp;
Command command = context.Command;
// We can simply pull up the project over the apply; provided we make sure
// that all the definitions of the apply are represented in the projectOp
ExtendedNodeInfo applyNodeInfo = command.GetExtendedNodeInfo(applyNode);
VarVec vec = command.CreateVarVec(projectOp.Outputs);
vec.Or(applyNodeInfo.Definitions);
projectOp.Outputs.InitFrom(vec);
// pull up the project over the apply node
applyNode.Child1 = projectNode.Child0;
context.Command.RecomputeNodeInfo(applyNode);
projectNode.Child0 = applyNode;
newNode = projectNode;
return true;
}
internal static readonly PatternMatchRule Rule_OuterApplyOverProject =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessOuterApplyOverProject);
///
/// Converts a
/// OuterApply(X, Project(Y, ...))
/// =>
/// Project(OuterApply(X, Project(Y, ...)), ...) or
/// Project(OuterApply(X, Y), ...)
///
/// The second (simpler) form is used if a "sentinel" var can be located (ie)
/// some Var of Y that is guaranteed to be non-null. Otherwise, we create a
/// dummy ProjectNode as the right child of the Apply - which
/// simply projects out all the vars of the Y, and adds on a constant (say "1"). This
/// constant is now treated as the sentinel var
///
/// Then the existing ProjectOp is pulled up above the the outer-apply, but all the locally defined
/// Vars have their defining expressions now expressed as
/// case when sentinelVar is null then null else oldDefiningExpr end
/// where oldDefiningExpr represents the original defining expression
/// This allows us to get nulls for the appropriate columns when necessary.
///
/// Special cases.
/// * If the oldDefiningExpr is itself an internal constant equivalent to the null sentinel ("1"),
/// we simply project a ref to the null sentinel, no need for cast
/// * If the ProjectOp contained exactly one locally defined Var, and it was a constant, then
/// we simply return - we will be looping endlessly otherwise
/// * If the ProjectOp contained no local definitions, then we don't need to create the
/// dummy projectOp - we can simply pull up the Project
/// * If any of the defining expressions of the local definitions was simply a VarRefOp
/// referencing a Var that was defined by Y, then there is no need to add the case
/// expression for that.
///
///
/// RuleProcessing context
/// The ApplyOp subtree
/// transformed subtree
/// Transfomation status
static bool ProcessOuterApplyOverProject(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node projectNode = applyNode.Child1;
Node varDefListNode = projectNode.Child1;
TransformationRulesContext trc = (TransformationRulesContext)context;
ExtendedNodeInfo inputNodeInfo = context.Command.GetExtendedNodeInfo(projectNode.Child0);
Var sentinelVar = inputNodeInfo.NonNullableDefinitions.First;
//
// special case handling first - we'll end up in an infinite loop otherwise.
// If the ProjectOp is the dummy ProjectOp that we would be building (ie)
// it defines only 1 var - and the defining expression is simply a constant
//
if (sentinelVar == null &&
varDefListNode.Children.Count == 1 &&
(varDefListNode.Child0.Child0.Op.OpType == OpType.InternalConstant || varDefListNode.Child0.Child0.Op.OpType == OpType.NullSentinel))
{
return false;
}
Command command = context.Command;
Node dummyProjectNode = null;
InternalConstantOp nullSentinelDefinitionOp = null;
// get node information for the project's child
ExtendedNodeInfo projectInputNodeInfo = command.GetExtendedNodeInfo(projectNode.Child0);
//
// Build up a dummy project node.
// Walk through each local definition of the current project Node, and convert
// all expressions into case expressions whose value depends on the var
// produced by the dummy project node
//
// Dev10 #480443: If any of the definitions changes we need to recompute the node info.
bool anyVarDefChagned = false;
foreach (Node varDefNode in varDefListNode.Children)
{
PlanCompiler.Assert(varDefNode.Op.OpType == OpType.VarDef, "Expected VarDefOp. Found " + varDefNode.Op.OpType + " instead");
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp == null || !projectInputNodeInfo.Definitions.IsSet(varRefOp.Var))
{
// do we need to build a dummy project node
if (sentinelVar == null)
{
nullSentinelDefinitionOp = command.CreateInternalConstantOp(command.IntegerType, 1);
Node dummyConstantExpr = command.CreateNode(nullSentinelDefinitionOp);
Node dummyProjectVarDefListNode = command.CreateVarDefListNode(dummyConstantExpr, out sentinelVar);
ProjectOp dummyProjectOp = command.CreateProjectOp(sentinelVar);
dummyProjectOp.Outputs.Or(projectInputNodeInfo.Definitions);
dummyProjectNode = command.CreateNode(dummyProjectOp, projectNode.Child0, dummyProjectVarDefListNode);
}
Node currentDefinition;
// If the null sentinel was just created, and the local definition of the current project Node
// is an internal constant equivalent to the null sentinel, it can be rewritten as a reference
// to the null sentinel.
if (nullSentinelDefinitionOp != null && ((true == nullSentinelDefinitionOp.IsEquivalent(varDefNode.Child0.Op)) ||
//The null sentinel has the same value of 1, thus it is safe.
varDefNode.Child0.Op.OpType == OpType.NullSentinel))
{
currentDefinition = command.CreateNode(command.CreateVarRefOp(sentinelVar));
}
else
{
currentDefinition = trc.BuildNullIfExpression(sentinelVar, varDefNode.Child0);
}
varDefNode.Child0 = currentDefinition;
command.RecomputeNodeInfo(varDefNode);
anyVarDefChagned = true;
}
}
// Recompute node info if needed
if (anyVarDefChagned)
{
command.RecomputeNodeInfo(varDefListNode);
}
//
// If we've created a dummy project node, make that the new child of the applyOp
//
applyNode.Child1 = dummyProjectNode != null ? dummyProjectNode : projectNode.Child0;
command.RecomputeNodeInfo(applyNode);
//
// Pull up the project node above the apply node now. Also, make sure that every Var of
// the applyNode's definitions actually shows up in the new Project
//
projectNode.Child0 = applyNode;
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
ProjectOp projectOp = (ProjectOp)projectNode.Op;
projectOp.Outputs.Or(applyLeftChildNodeInfo.Definitions);
newNode = projectNode;
return true;
}
#endregion
#region ApplyOverAnything
internal static readonly PatternMatchRule Rule_CrossApplyOverAnything =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyOverAnything);
internal static readonly PatternMatchRule Rule_OuterApplyOverAnything =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyOverAnything);
///
/// Converts a CrossApply(X,Y) => CrossJoin(X,Y)
/// OuterApply(X,Y) => LeftOuterJoin(X, Y, true)
/// only if Y has no external references to X
///
/// Rule processing context
/// The ApplyOp subtree
/// transformed subtree
/// the transformation status
static bool ProcessApplyOverAnything(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node applyLeftChild = applyNode.Child0;
Node applyRightChild = applyNode.Child1;
ApplyBaseOp applyOp = (ApplyBaseOp)applyNode.Op;
Command command = context.Command;
ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyRightChild);
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyLeftChild);
//
// If we're currently dealing with an OuterApply, and the right child is guaranteed
// to produce at least one row, then we can convert the outer-apply into a cross apply
//
bool convertedToCrossApply = false;
if (applyOp.OpType == OpType.OuterApply &&
applyRightChildNodeInfo.MinRows >= RowCount.One)
{
applyOp = command.CreateCrossApplyOp();
convertedToCrossApply = true;
}
//
// Does the right child reference any of the definitions of the left child? If it
// does, then simply return from this function
//
if (applyRightChildNodeInfo.ExternalReferences.Overlaps(applyLeftChildNodeInfo.Definitions))
{
if (convertedToCrossApply)
{
newNode = command.CreateNode(applyOp, applyLeftChild, applyRightChild);
return true;
}
else
{
return false;
}
}
//
// So, we now know that the right child does not reference any definitions
// from the left.
// So, we simply convert the apply into an appropriate join Op
//
if (applyOp.OpType == OpType.CrossApply)
{
//
// Convert "x CrossApply y" into "x CrossJoin y"
//
newNode = command.CreateNode(command.CreateCrossJoinOp(),
applyLeftChild, applyRightChild);
}
else // outer apply
{
//
// Convert "x OA y" into "x LOJ y on (true)"
//
LeftOuterJoinOp joinOp = command.CreateLeftOuterJoinOp();
ConstantPredicateOp trueOp = command.CreateTrueOp();
Node trueNode = command.CreateNode(trueOp);
newNode = command.CreateNode(joinOp, applyLeftChild, applyRightChild, trueNode);
}
return true;
}
#endregion
#region ApplyIntoScalarSubquery
internal static readonly PatternMatchRule Rule_CrossApplyIntoScalarSubquery =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyIntoScalarSubquery);
internal static readonly PatternMatchRule Rule_OuterApplyIntoScalarSubquery =
new PatternMatchRule(new Node(OuterApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessApplyIntoScalarSubquery);
///
/// Converts a Apply(X,Y) => Project(X, Y1), where Y1 is a scalar subquery version of Y
/// The transformation is valid only if all of the following conditions hold:
/// 1. Y produces only one output
/// 2. Y produces at most one row
/// 3. Y produces at least one row, or the Apply operator in question is an OuterApply
///
/// Rule processing context
/// The ApplyOp subtree
/// transformed subtree
/// the transformation status
static bool ProcessApplyIntoScalarSubquery(RuleProcessingContext context, Node applyNode, out Node newNode)
{
Command command = context.Command;
ExtendedNodeInfo applyRightChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child1);
OpType applyKind = applyNode.Op.OpType;
if (!CanRewriteApply(applyNode.Child1, applyRightChildNodeInfo, applyKind))
{
newNode = applyNode;
return false;
}
// Create the project node over the original input with element over the apply as new projected var
ExtendedNodeInfo applyLeftChildNodeInfo = command.GetExtendedNodeInfo(applyNode.Child0);
Var oldVar = applyRightChildNodeInfo.Definitions.First;
// Project all the outputs from the left child
VarVec projectOpOutputs = command.CreateVarVec(applyLeftChildNodeInfo.Definitions);
//
// Remap the var defining tree to get it into a consistent state
// and then remove all references to oldVar from it to avoid them being wrongly remapped to newVar
// in subsequent remappings.
//
TransformationRulesContext trc = (TransformationRulesContext)context;
trc.RemapSubtree(applyNode.Child1);
VarDefinitionRemapper.RemapSubtree(applyNode.Child1, command, oldVar);
Node elementNode = command.CreateNode(command.CreateElementOp(oldVar.Type), applyNode.Child1);
Var newVar;
Node varDefListNode = command.CreateVarDefListNode(elementNode, out newVar);
projectOpOutputs.Set(newVar);
newNode = command.CreateNode(
command.CreateProjectOp(projectOpOutputs),
applyNode.Child0,
varDefListNode);
// Add the var mapping from oldVar to newVar
trc.AddVarMapping(oldVar, newVar);
return true;
}
///
/// Determines whether an applyNode can be rewritten into a projection with a scalar subquery.
/// It can be done if all of the following conditions hold:
/// 1. The right child or the apply has only one output
/// 2. The right child of the apply produces at most one row
/// 3. The right child of the apply produces at least one row, or the Apply operator in question is an OuterApply
///
///
///
///
///
/// A visitor that calculates the number of output columns for a subree
/// with a given root
///
internal class OutputCountVisitor : BasicOpVisitorOfT
{
#region Constructors
internal OutputCountVisitor()
{
}
#endregion
#region Public Methods
///
/// Calculates the number of output columns for the subree
/// rooted at the given node
///
///
///
/// Visitor for children. Simply visit all children,
/// and sum the number of their outputs.
///
/// Current node
///
/// A default processor for any node.
/// Returns the sum of the children outputs
///
///
/// /returns>
protected override int VisitDefault(Node n)
{
return VisitChildren(n);
}
#endregion
#region RelOp Visitors
#region SetOp Visitors
///
/// The number of outputs is same as for any of the inputs
///
///
///
///
/// Distinct
///
///
///
///
/// FilterOp
///
///
///
///
/// GroupByOp
///
///
///
///
/// ProjectOp
///
///
///
///
/// ScanTableOp
///
///
///
///
/// SingleRowTableOp
///
///
///
///
/// Same as the input
///
///
///
///
/// A utility class that remaps a given var at its definition and also remaps all its references.
/// The given var is remapped to an arbitrary new var.
/// If the var is defined by a ScanTable, all the vars defined by that table and all their references
/// are remapped as well.
///
internal class VarDefinitionRemapper : VarRemapper
{
private readonly Var m_oldVar;
private VarDefinitionRemapper(Var oldVar, Command command)
: base(command)
{
this.m_oldVar = oldVar;
}
///
/// Public entry point.
/// Remaps the subree rooted at the given tree
///
///
///
///
internal static void RemapSubtree(Node root, Command command, Var oldVar)
{
VarDefinitionRemapper remapper = new VarDefinitionRemapper(oldVar, command);
remapper.RemapSubtree(root);
}
///
/// Update vars in this subtree. Recompute the nodeinfo along the way
/// Unlike the base implementation, we want to visit the childrent, even if no vars are in the
/// remapping dictionary.
///
///
internal override void RemapSubtree(Node subTree)
{
foreach (Node chi in subTree.Children)
{
RemapSubtree(chi);
}
VisitNode(subTree);
m_command.RecomputeNodeInfo(subTree);
}
///
/// If the node defines the node that needs to be remapped,
/// it remaps it to a new var.
///
///
///
///
/// If the columnVars defined by the table contain the var that needs to be remapped
/// all the column vars produces by the table are remaped to new vars.
///
///
///
///
/// The var that needs to be remapped may be produced by a set op,
/// in which case the varmaps need to be updated too.
///
///
///
protected override void VisitSetOp(SetOp op, Node n)
{
base.VisitSetOp(op, n);
if (op.Outputs.IsSet(m_oldVar))
{
Var newVar = m_command.CreateSetOpVar(m_oldVar.Type);
op.Outputs.Clear(m_oldVar);
op.Outputs.Set(newVar);
RemapVarMapKey(op.VarMap[0], newVar);
RemapVarMapKey(op.VarMap[1], newVar);
AddMapping(m_oldVar, newVar);
}
}
///
/// Replaces the entry in the varMap in which m_oldVar is a key
/// with an entry in which newVAr is the key and the value remains the same.
///
///
///
private void RemapVarMapKey(VarMap varMap, Var newVar)
{
Var value = varMap[m_oldVar];
varMap.Remove(m_oldVar);
varMap.Add(newVar, value);
}
}
#endregion
#region CrossApply over LeftOuterJoin of SingleRowTable with anything and with constant predicate
internal static readonly PatternMatchRule Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable =
new PatternMatchRule(new Node(CrossApplyOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeftOuterJoinOp.Pattern,
new Node(SingleRowTableOp.Pattern),
new Node(LeafOp.Pattern),
new Node(ConstantPredicateOp.Pattern))),
ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable);
///
/// Convert a CrossApply(X, LeftOuterJoin(SingleRowTable, Y, on true))
/// into just OuterApply(X, Y)
///
/// rule processing context
/// the join node
/// transformed subtree
/// transformation status
static bool ProcessCrossApplyOverLeftOuterJoinOverSingleRowTable(RuleProcessingContext context, Node applyNode, out Node newNode)
{
newNode = applyNode;
Node joinNode = applyNode.Child1;
//Check the value of the predicate
ConstantPredicateOp joinPredicate = (ConstantPredicateOp)joinNode.Child2.Op;
if (joinPredicate.IsFalse)
{
return false;
}
applyNode.Op = context.Command.CreateOuterApplyOp();
applyNode.Child1 = joinNode.Child1;
return true;
}
#endregion
#region All ApplyOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
ApplyOpRules.Rule_CrossApplyOverAnything,
ApplyOpRules.Rule_CrossApplyOverFilter,
ApplyOpRules.Rule_CrossApplyOverProject,
ApplyOpRules.Rule_OuterApplyOverAnything,
ApplyOpRules.Rule_OuterApplyOverProjectInternalConstantOverFilter,
ApplyOpRules.Rule_OuterApplyOverProjectNullSentinelOverFilter,
ApplyOpRules.Rule_OuterApplyOverProject,
ApplyOpRules.Rule_OuterApplyOverFilter,
ApplyOpRules.Rule_CrossApplyOverLeftOuterJoinOverSingleRowTable,
ApplyOpRules.Rule_CrossApplyIntoScalarSubquery,
ApplyOpRules.Rule_OuterApplyIntoScalarSubquery,
};
#endregion
}
#endregion
#region Join Rules
///
/// Transformation rules for JoinOps
///
internal static class JoinOpRules
{
#region JoinOverProject
internal static readonly PatternMatchRule Rule_CrossJoinOverProject1 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_CrossJoinOverProject2 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_InnerJoinOverProject1 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_InnerJoinOverProject2 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
internal static readonly PatternMatchRule Rule_OuterJoinOverProject2 =
new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverProject);
///
/// CrossJoin(Project(A), B) => Project(CrossJoin(A, B), modifiedvars)
/// InnerJoin(Project(A), B, p) => Project(InnerJoin(A, B, p'), modifiedvars)
/// LeftOuterJoin(Project(A), B, p) => Project(LeftOuterJoin(A, B, p'), modifiedvars)
///
/// Rule processing context
/// Current JoinOp tree to process
/// Transformed subtree
/// transformation status
static bool ProcessJoinOverProject(RuleProcessingContext context, Node joinNode, out Node newNode)
{
newNode = joinNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
Node joinConditionNode = joinNode.HasChild2 ? joinNode.Child2 : (Node)null;
Dictionary varRefMap = new Dictionary();
if (joinConditionNode != null && !trc.IsScalarOpTree(joinConditionNode, varRefMap))
{
return false;
}
Node newJoinNode;
Node newProjectNode;
// Now locate the ProjectOps
VarVec newVarSet = command.CreateVarVec();
List varDefNodes = new List();
//
// Try and handle "project" on both sides only if we're not dealing with
// an LOJ.
//
if ((joinNode.Op.OpType != OpType.LeftOuterJoin) &&
(joinNode.Child0.Op.OpType == OpType.Project) &&
(joinNode.Child1.Op.OpType == OpType.Project))
{
ProjectOp projectOp1 = (ProjectOp)joinNode.Child0.Op;
ProjectOp projectOp2 = (ProjectOp)joinNode.Child1.Op;
Dictionary varMap1 = trc.GetVarMap(joinNode.Child0.Child1, varRefMap);
Dictionary varMap2 = trc.GetVarMap(joinNode.Child1.Child1, varRefMap);
if (varMap1 == null || varMap2 == null)
{
return false;
}
if (joinConditionNode != null)
{
joinConditionNode = trc.ReMap(joinConditionNode, varMap1);
joinConditionNode = trc.ReMap(joinConditionNode, varMap2);
newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0, joinConditionNode);
}
else
{
newJoinNode = context.Command.CreateNode(joinNode.Op, joinNode.Child0.Child0, joinNode.Child1.Child0);
}
newVarSet.InitFrom(projectOp1.Outputs);
foreach (Var v in projectOp2.Outputs)
{
newVarSet.Set(v);
}
ProjectOp newProjectOp = command.CreateProjectOp(newVarSet);
varDefNodes.AddRange(joinNode.Child0.Child1.Children);
varDefNodes.AddRange(joinNode.Child1.Child1.Children);
Node varDefListNode = command.CreateNode(
command.CreateVarDefListOp(),
varDefNodes);
newProjectNode = command.CreateNode(newProjectOp,
newJoinNode, varDefListNode);
newNode = newProjectNode;
return true;
}
int projectNodeIdx = -1;
int otherNodeIdx = -1;
if (joinNode.Child0.Op.OpType == OpType.Project)
{
projectNodeIdx = 0;
otherNodeIdx = 1;
}
else
{
PlanCompiler.Assert(joinNode.Op.OpType != OpType.LeftOuterJoin, "unexpected non-LeftOuterJoin");
projectNodeIdx = 1;
otherNodeIdx = 0;
}
Node projectNode = joinNode.Children[projectNodeIdx];
ProjectOp projectOp = projectNode.Op as ProjectOp;
Dictionary varMap = trc.GetVarMap(projectNode.Child1, varRefMap);
if (varMap == null)
{
return false;
}
ExtendedNodeInfo otherChildInfo = command.GetExtendedNodeInfo(joinNode.Children[otherNodeIdx]);
VarVec vec = command.CreateVarVec(projectOp.Outputs);
vec.Or(otherChildInfo.Definitions);
projectOp.Outputs.InitFrom(vec);
if (joinConditionNode != null)
{
joinConditionNode = trc.ReMap(joinConditionNode, varMap);
joinNode.Child2 = joinConditionNode;
}
joinNode.Children[projectNodeIdx] = projectNode.Child0; // bypass the projectOp
context.Command.RecomputeNodeInfo(joinNode);
newNode = context.Command.CreateNode(projectOp, joinNode, projectNode.Child1);
return true;
}
#endregion
#region JoinOverFilter
internal static readonly PatternMatchRule Rule_CrossJoinOverFilter1 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern))),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_CrossJoinOverFilter2 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_InnerJoinOverFilter1 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_InnerJoinOverFilter2 =
new PatternMatchRule(new Node(InnerJoinOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
internal static readonly PatternMatchRule Rule_OuterJoinOverFilter2 =
new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
new Node(FilterOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverFilter);
///
/// CrossJoin(Filter(A,p), B) => Filter(CrossJoin(A, B), p)
/// CrossJoin(A, Filter(B,p)) => Filter(CrossJoin(A, B), p)
///
/// InnerJoin(Filter(A,p), B, c) => Filter(InnerJoin(A, B, c), p)
/// InnerJoin(A, Filter(B,p), c) => Filter(InnerJoin(A, B, c), p)
///
/// LeftOuterJoin(Filter(A,p), B, c) => Filter(LeftOuterJoin(A, B, c), p)
///
/// Note that the predicate on the right table in a left-outer-join cannot be pulled
/// up above the join.
///
///
/// Rule processing context
/// Current JoinOp tree to process
/// transformed subtree
/// transformation status
static bool ProcessJoinOverFilter(RuleProcessingContext context, Node joinNode, out Node newNode)
{
newNode = joinNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
Node predicateNode = null;
Node newLeftInput = joinNode.Child0;
// get the predicate from the first filter
if (joinNode.Child0.Op.OpType == OpType.Filter)
{
predicateNode = joinNode.Child0.Child1;
newLeftInput = joinNode.Child0.Child0; // bypass the filter
}
// get the predicate from the second filter
Node newRightInput = joinNode.Child1;
if (joinNode.Child1.Op.OpType == OpType.Filter && joinNode.Op.OpType != OpType.LeftOuterJoin)
{
if (predicateNode == null)
{
predicateNode = joinNode.Child1.Child1;
}
else
{
predicateNode = command.CreateNode(
command.CreateConditionalOp(OpType.And),
predicateNode, joinNode.Child1.Child1);
}
newRightInput = joinNode.Child1.Child0; // bypass the filter
}
// No optimizations to perform if we can't locate the appropriate predicate
if (predicateNode == null)
{
return false;
}
//
// Create a new join node with the new inputs
//
Node newJoinNode;
if (joinNode.Op.OpType == OpType.CrossJoin)
{
newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput);
}
else
{
newJoinNode = command.CreateNode(joinNode.Op, newLeftInput, newRightInput, joinNode.Child2);
}
//
// create a new filterOp with the combined predicates, and with the
// newjoinNode as the input
//
FilterOp newFilterOp = command.CreateFilterOp();
newNode = command.CreateNode(newFilterOp, newJoinNode, predicateNode);
//
// Mark this subtree so that we don't try to push filters down again
//
trc.SuppressFilterPushdown(newNode);
return true;
}
#endregion
#region Join over SingleRowTable
internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable1 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(SingleRowTableOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverSingleRowTable);
internal static readonly PatternMatchRule Rule_CrossJoinOverSingleRowTable2 =
new PatternMatchRule(new Node(CrossJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(SingleRowTableOp.Pattern)),
ProcessJoinOverSingleRowTable);
internal static readonly PatternMatchRule Rule_LeftOuterJoinOverSingleRowTable =
new PatternMatchRule(new Node(LeftOuterJoinOp.Pattern,
new Node(LeafOp.Pattern),
new Node(SingleRowTableOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessJoinOverSingleRowTable);
///
/// Convert a CrossJoin(SingleRowTable, X) or CrossJoin(X, SingleRowTable) or LeftOuterJoin(X, SingleRowTable)
/// into just "X"
///
/// rule processing context
/// the join node
/// transformed subtree
/// transformation status
static bool ProcessJoinOverSingleRowTable(RuleProcessingContext context, Node joinNode, out Node newNode)
{
newNode = joinNode;
if (joinNode.Child0.Op.OpType == OpType.SingleRowTable)
{
newNode = joinNode.Child1;
}
else
{
newNode = joinNode.Child0;
}
return true;
}
#endregion
#region Misc
#endregion
#region All JoinOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
Rule_CrossJoinOverProject1,
Rule_CrossJoinOverProject2,
Rule_InnerJoinOverProject1,
Rule_InnerJoinOverProject2,
Rule_OuterJoinOverProject2,
Rule_CrossJoinOverFilter1,
Rule_CrossJoinOverFilter2,
Rule_InnerJoinOverFilter1,
Rule_InnerJoinOverFilter2,
Rule_OuterJoinOverFilter2,
Rule_CrossJoinOverSingleRowTable1,
Rule_CrossJoinOverSingleRowTable2,
Rule_LeftOuterJoinOverSingleRowTable,
};
#endregion
}
#endregion
#region SingleRowOp Rules
///
/// Rules for SingleRowOp
///
internal static class SingleRowOpRules
{
internal static readonly PatternMatchRule Rule_SingleRowOpOverAnything =
new PatternMatchRule(new Node(SingleRowOp.Pattern,
new Node(LeafOp.Pattern)),
ProcessSingleRowOpOverAnything);
///
/// Convert a
/// SingleRowOp(X) => X
/// if X produces at most one row
///
/// Rule Processing context
/// Current subtree
/// transformed subtree
/// Transformation status
static bool ProcessSingleRowOpOverAnything(RuleProcessingContext context, Node singleRowNode, out Node newNode)
{
newNode = singleRowNode;
TransformationRulesContext trc = (TransformationRulesContext)context;
ExtendedNodeInfo childNodeInfo = context.Command.GetExtendedNodeInfo(singleRowNode.Child0);
// If the input to this Op can produce at most one row, then we don't need the
// singleRowOp - simply return the input
if (childNodeInfo.MaxRows <= RowCount.One)
{
newNode = singleRowNode.Child0;
return true;
}
//
// if the current node is a FilterOp, then try and determine if the FilterOp
// produces one row at most
//
if (singleRowNode.Child0.Op.OpType == OpType.Filter)
{
Predicate predicate = new Predicate(context.Command, singleRowNode.Child0.Child1);
if (predicate.SatisfiesKey(childNodeInfo.Keys.KeyVars, childNodeInfo.Definitions))
{
childNodeInfo.MaxRows = RowCount.One;
newNode = singleRowNode.Child0;
return true;
}
}
// we couldn't do anything
return false;
}
internal static readonly PatternMatchRule Rule_SingleRowOpOverProject =
new PatternMatchRule(new Node(SingleRowOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern), new Node(LeafOp.Pattern))),
ProcessSingleRowOpOverProject);
///
/// Convert
/// SingleRowOp(Project) => Project(SingleRowOp)
///
/// Rule Processing context
/// current subtree
/// transformeed subtree
/// transformation status
static bool ProcessSingleRowOpOverProject(RuleProcessingContext context, Node singleRowNode, out Node newNode)
{
newNode = singleRowNode;
Node projectNode = singleRowNode.Child0;
Node projectNodeInput = projectNode.Child0;
// Simply push the SingleRowOp below the ProjectOp
singleRowNode.Child0 = projectNodeInput;
context.Command.RecomputeNodeInfo(singleRowNode);
projectNode.Child0 = singleRowNode;
newNode = projectNode;
return true; // subtree modified internally
}
#region All SingleRowOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
Rule_SingleRowOpOverAnything,
Rule_SingleRowOpOverProject,
};
#endregion
}
#endregion
#region SetOp Rules
///
/// SetOp Transformation Rules
///
internal static class SetOpRules
{
#region SetOpOverFilters
internal static readonly SimpleRule Rule_UnionAllOverEmptySet =
new SimpleRule(OpType.UnionAll, ProcessSetOpOverEmptySet);
internal static readonly SimpleRule Rule_IntersectOverEmptySet =
new SimpleRule(OpType.Intersect, ProcessSetOpOverEmptySet);
internal static readonly SimpleRule Rule_ExceptOverEmptySet =
new SimpleRule(OpType.Except, ProcessSetOpOverEmptySet);
///
/// Process a SetOp when one of the inputs is an emptyset.
///
/// An emptyset is represented by a Filter(X, ConstantPredicate)
/// where the ConstantPredicate has a value of "false"
///
/// The general rules are
/// UnionAll(X, EmptySet) => X
/// UnionAll(EmptySet, X) => X
/// Intersect(EmptySet, X) => EmptySet
/// Intersect(X, EmptySet) => EmptySet
/// Except(EmptySet, X) => EmptySet
/// Except(X, EmptySet) => X
///
/// These rules then translate into
/// UnionAll: return the non-empty input
/// Intersect: return the empty input
/// Except: return the "left" input
///
/// Rule processing context
/// the current setop tree
/// Index of the filter node in the setop
/// transformed subtree
/// transformation status
private static bool ProcessSetOpOverEmptySet(RuleProcessingContext context, Node setOpNode, out Node newNode)
{
bool leftChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child0).MaxRows == RowCount.Zero;
bool rightChildIsEmptySet = context.Command.GetExtendedNodeInfo(setOpNode.Child1).MaxRows == RowCount.Zero;
if (!leftChildIsEmptySet && !rightChildIsEmptySet)
{
newNode = setOpNode;
return false;
}
int indexToReturn;
SetOp setOp = (SetOp)setOpNode.Op;
if (!rightChildIsEmptySet && setOp.OpType == OpType.UnionAll ||
!leftChildIsEmptySet && setOp.OpType == OpType.Intersect)
{
indexToReturn = 1;
}
else
{
indexToReturn = 0;
}
newNode = setOpNode.Children[indexToReturn];
TransformationRulesContext trc = (TransformationRulesContext)context;
foreach (KeyValuePair kv in setOp.VarMap[indexToReturn])
{
trc.AddVarMapping(kv.Key, kv.Value);
}
return true;
}
#endregion
#region All SetOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
Rule_UnionAllOverEmptySet,
Rule_IntersectOverEmptySet,
Rule_ExceptOverEmptySet,
};
#endregion
}
#endregion
#region GroupByOp Rules
///
/// Transformation Rules for GroupByOps
///
internal static class GroupByOpRules
{
#region GroupByOpWithSimpleVarRedefinitions
internal static readonly SimpleRule Rule_GroupByOpWithSimpleVarRedefinitions = new SimpleRule(OpType.GroupBy, ProcessGroupByWithSimpleVarRedefinitions);
///
/// If the GroupByOp defines some computedVars as part of its keys, but those computedVars are simply
/// redefinitions of other Vars, then eliminate the computedVars.
///
/// GroupBy(X, VarDefList(VarDef(cv1, VarRef(v1)), ...), VarDefList(...))
/// can be transformed into
/// GroupBy(X, VarDefList(...))
/// where cv1 has now been replaced by v1
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessGroupByWithSimpleVarRedefinitions(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
GroupByOp groupByOp = (GroupByOp)n.Op;
// no local keys? nothing to do
if (n.Child1.Children.Count == 0)
{
return false;
}
TransformationRulesContext trc = (TransformationRulesContext)context;
Command command = trc.Command;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n);
//
// Check to see if any of the computed Vars defined by this GroupByOp
// are simple redefinitions of other VarRefOps. Consider only those
// VarRefOps that are not "external" references
//
bool canEliminateSomeVars = false;
foreach (Node varDefNode in n.Child1.Children)
{
Node definingExprNode = varDefNode.Child0;
if (definingExprNode.Op.OpType == OpType.VarRef)
{
VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
if (!nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
// this is a Var that we should remove
canEliminateSomeVars = true;
}
}
}
// Did we have any redefinitions
if (!canEliminateSomeVars)
{
return false;
}
//
// OK. We've now identified a set of vars that are simple redefinitions.
// Try and replace the computed Vars with the Vars that they're redefining
//
// Lets now build up a new VarDefListNode
List newVarDefNodes = new List();
foreach (Node varDefNode in n.Child1.Children)
{
VarDefOp varDefOp = (VarDefOp)varDefNode.Op;
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp != null && !nodeInfo.ExternalReferences.IsSet(varRefOp.Var))
{
groupByOp.Outputs.Clear(varDefOp.Var);
groupByOp.Outputs.Set(varRefOp.Var);
groupByOp.Keys.Clear(varDefOp.Var);
groupByOp.Keys.Set(varRefOp.Var);
trc.AddVarMapping(varDefOp.Var, varRefOp.Var);
}
else
{
newVarDefNodes.Add(varDefNode);
}
}
// Create a new vardeflist node, and set that as Child1 for the group by op
Node newVarDefListNode = command.CreateNode(command.CreateVarDefListOp(), newVarDefNodes);
n.Child1 = newVarDefListNode;
return true; // subtree modified
}
#endregion
#region GroupByOverProject
internal static readonly PatternMatchRule Rule_GroupByOverProject =
new PatternMatchRule(new Node(GroupByOp.Pattern,
new Node(ProjectOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern)),
ProcessGroupByOverProject);
///
/// Converts a GroupBy(Project(X, c1,..ck), agg1, agg2, .. aggm) =>
/// GroupBy(X, agg1', agg2', .. aggm')
/// where agg1', agg2', .. aggm' are the "mapped" versions
/// of agg1, agg2, .. aggm, such that the references to c1, ... ck are
/// replaced by their definitions.
///
/// We only do this if each c1, ..ck is refereneced (in aggregates) at most once or it is a constant.
///
/// Rule processing context
/// Current ProjectOp node
/// modified subtree
/// Transformation status
static bool ProcessGroupByOverProject(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
GroupByOp op = (GroupByOp)n.Op;
Command command = ((TransformationRulesContext)context).Command;
Node projectNode = n.Child0;
Node projectNodeVarDefList = projectNode.Child1;
Node keys = n.Child1;
Node aggregates = n.Child2;
// If there are any keys, we should not remove the inner project
if (keys.Children.Count > 0)
{
return false;
}
//Get a list of all defining vars
VarVec projectDefinitions = command.GetExtendedNodeInfo(projectNode).LocalDefinitions;
//If any of the defined vars is output, than we need the extra project anyway.
if (op.Outputs.Overlaps(projectDefinitions))
{
return false;
}
bool createdNewProjectDefinitions = false;
//If there are any constants remove them from the list that needs to be tested,
//These can safely be replaced
for (int i = 0; i < projectNodeVarDefList.Children.Count; i++)
{
Node varDefNode = projectNodeVarDefList.Children[i];
if (varDefNode.Child0.Op.OpType == OpType.Constant || varDefNode.Child0.Op.OpType == OpType.InternalConstant || varDefNode.Child0.Op.OpType == OpType.NullSentinel)
{
//We shouldn't modify the original project definitions, thus we copy it
// the first time we encounter a constant
if (!createdNewProjectDefinitions)
{
projectDefinitions = command.CreateVarVec(projectDefinitions);
createdNewProjectDefinitions = true;
}
projectDefinitions.Clear(((VarDefOp)varDefNode.Op).Var);
}
}
if (VarRefUsageFinder.AnyVarUsedMoreThanOnce(projectDefinitions, aggregates, command))
{
return false;
}
//If we got here it means that all vars were either constants, or used at most once
// Create a dictionary to be used for remapping the keys and the aggregates
Dictionary varToDefiningNode = new Dictionary(projectNodeVarDefList.Children.Count);
for (int j = 0; j < projectNodeVarDefList.Children.Count; j++)
{
Node varDefNode = projectNodeVarDefList.Children[j];
Var var = ((VarDefOp)varDefNode.Op).Var;
varToDefiningNode.Add(var, varDefNode.Child0);
}
newNode.Child2 = VarRefReplacer.Replace(varToDefiningNode, aggregates, command);
newNode.Child0 = projectNode.Child0;
return true;
}
///
/// Replaces each occurance of the given vars with their definitions.
///
internal class VarRefReplacer : BasicOpVisitorOfNode
{
private Dictionary m_varReplacementTable;
private Command m_command;
private VarRefReplacer(Dictionary varReplacementTable, Command command)
{
this.m_varReplacementTable = varReplacementTable;
this.m_command = command;
}
///
/// "Public" entry point. In the subtree rooted at the given root,
/// replace each occurance of the given vars with their definitions,
/// where each key-value pair in the dictionary is a var-definition pair.
///
///
///
///
/// varReplacementTable, Node root, Command command)
{
VarRefReplacer replacer = new VarRefReplacer(varReplacementTable, command);
return replacer.VisitNode(root);
}
public override Node Visit(VarRefOp op, Node n)
{
Node replacementNode;
if (m_varReplacementTable.TryGetValue(op.Var, out replacementNode))
{
return replacementNode;
}
else
{
return n;
}
}
///
/// Recomputes node info post regular processing.
///
///
///
/// Used to determine whether any of the given vars occurs more than once
/// in a given subtree.
///
internal class VarRefUsageFinder : BasicOpVisitor
{
private bool m_anyUsedMoreThenOnce = false;
private VarVec m_varVec;
private VarVec m_usedVars;
private VarRefUsageFinder(VarVec varVec, Command command)
{
this.m_varVec = varVec;
this.m_usedVars = command.CreateVarVec();
}
///
/// Public entry point. Returns true if at least one of the given vars occurs more than
/// once in the subree rooted at the given root.
///
///
///
///
///
/// If the GroupByOp has no aggregates:
///
/// (1) and if it includes all all the keys of the input, than it is unnecessary
/// GroupBy (X, keys) -> Project(X, keys) where keys includes all keys of X.
///
/// (2) else it can be turned into a Distinct:
/// GroupBy (X, keys) -> Distinct(X, keys)
///
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessGroupByOpWithNoAggregates(RuleProcessingContext context, Node n, out Node newNode)
{
Command command = context.Command;
GroupByOp op = (GroupByOp)n.Op;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
ProjectOp newOp = command.CreateProjectOp(op.Keys);
VarDefListOp varDefListOp = command.CreateVarDefListOp();
Node varDefListNode = command.CreateNode(varDefListOp);
newNode = command.CreateNode(newOp, n.Child0, n.Child1);
//If we know the keys of the input and the list of keys includes them all,
// this is the result, otherwise add distinct
if (nodeInfo.Keys.NoKeys || !op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
{
newNode = command.CreateNode(command.CreateDistinctOp(command.CreateVarVec(op.Keys)), newNode);
}
return true;
}
#endregion
#region All GroupByOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions,
GroupByOpRules.Rule_GroupByOverProject,
GroupByOpRules.Rule_GroupByOpWithNoAggregates,
};
#endregion
}
#endregion
#region Sorting Rules
///
/// Transformation Rules for SortOp
///
internal static class SortOpRules
{
#region SortOpOverAtMostOneRow
internal static readonly SimpleRule Rule_SortOpOverAtMostOneRow = new SimpleRule(OpType.Sort, ProcessSortOpOverAtMostOneRow);
///
/// If the SortOp's input is guaranteed to produce at most 1 row, remove the node with the SortOp:
/// Sort(X) => X, if X is guaranteed to produce no more than 1 row
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessSortOpOverAtMostOneRow(RuleProcessingContext context, Node n, out Node newNode)
{
ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
//If the input has at most one row, omit the SortOp
if (nodeInfo.MaxRows == RowCount.Zero || nodeInfo.MaxRows == RowCount.One)
{
newNode = n.Child0;
return true;
}
//Otherwise return the node as is
newNode = n;
return false;
}
#endregion
#region All SortOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
SortOpRules.Rule_SortOpOverAtMostOneRow,
};
#endregion
}
///
/// Transformation Rules for ConstrainedSortOp
///
internal static class ConstrainedSortOpRules
{
#region ConstrainedSortOpOverEmptySet
internal static readonly SimpleRule Rule_ConstrainedSortOpOverEmptySet = new SimpleRule(OpType.ConstrainedSort, ProcessConstrainedSortOpOverEmptySet);
///
/// If the ConstrainedSortOp's input is guaranteed to produce no rows, remove the ConstrainedSortOp completly:
/// CSort(EmptySet) => EmptySet
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessConstrainedSortOpOverEmptySet(RuleProcessingContext context, Node n, out Node newNode)
{
ExtendedNodeInfo nodeInfo = ((TransformationRulesContext)context).Command.GetExtendedNodeInfo(n.Child0);
//If the input has no rows, remove the ConstraintSortOp node completly
if (nodeInfo.MaxRows == RowCount.Zero)
{
newNode = n.Child0;
return true;
}
newNode = n;
return false;
}
#endregion
#region All ConstrainedSortOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
ConstrainedSortOpRules.Rule_ConstrainedSortOpOverEmptySet,
};
#endregion
}
#endregion
#region DistinctOp Rules
///
/// Transformation Rules for DistinctOp
///
internal static class DistinctOpRules
{
#region DistinctOpOfKeys
internal static readonly SimpleRule Rule_DistinctOpOfKeys = new SimpleRule(OpType.Distinct, ProcessDistinctOpOfKeys);
///
/// If the DistinctOp includes all all the keys of the input, than it is unnecessary.
/// Distinct (X, distinct_keys) -> Project( X, distinct_keys) where distinct_keys includes all keys of X.
///
/// Rule processing context
/// current subtree
/// transformed subtree
/// transformation status
static bool ProcessDistinctOpOfKeys(RuleProcessingContext context, Node n, out Node newNode)
{
Command command = context.Command;
ExtendedNodeInfo nodeInfo = command.GetExtendedNodeInfo(n.Child0);
DistinctOp op = (DistinctOp)n.Op;
//If we know the keys of the input and the list of distinct keys includes them all, omit the distinct
if (!nodeInfo.Keys.NoKeys && op.Keys.Subsumes(nodeInfo.Keys.KeyVars))
{
ProjectOp newOp = command.CreateProjectOp(op.Keys);
//Create empty vardef list
VarDefListOp varDefListOp = command.CreateVarDefListOp();
Node varDefListNode = command.CreateNode(varDefListOp);
newNode = command.CreateNode(newOp, n.Child0, varDefListNode);
return true;
}
//Otherwise return the node as is
newNode = n;
return false;
}
#endregion
#region All DistinctOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
DistinctOpRules.Rule_DistinctOpOfKeys,
};
#endregion
}
#endregion
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ArgIterator.cs
- _Semaphore.cs
- ExtensionSimplifierMarkupObject.cs
- IgnoreSection.cs
- ContentPropertyAttribute.cs
- MultiBinding.cs
- Compensate.cs
- ellipse.cs
- EnumValidator.cs
- WSSecurityXXX2005.cs
- QuerySettings.cs
- StandardToolWindows.cs
- XmlCollation.cs
- GeneralTransformCollection.cs
- TypeHelper.cs
- CodeDomDesignerLoader.cs
- DataBoundControlAdapter.cs
- BinaryMessageEncodingBindingElement.cs
- VirtualPathUtility.cs
- SubtreeProcessor.cs
- IconHelper.cs
- ISessionStateStore.cs
- MatchingStyle.cs
- DefaultTextStoreTextComposition.cs
- XmlSerializerSection.cs
- RequestQueryProcessor.cs
- SEHException.cs
- DialogWindow.cs
- CaseInsensitiveComparer.cs
- UIElement.cs
- DesignerLoader.cs
- PropertyItemInternal.cs
- ImageCodecInfoPrivate.cs
- WmlCalendarAdapter.cs
- DataTemplateKey.cs
- DocumentPaginator.cs
- PeerInvitationResponse.cs
- XmlSchemaAny.cs
- NumberAction.cs
- EntityDataSourceChangedEventArgs.cs
- PaintValueEventArgs.cs
- SiteMapDataSourceDesigner.cs
- XpsPackagingPolicy.cs
- GetTokenRequest.cs
- ScriptHandlerFactory.cs
- HTTPNotFoundHandler.cs
- FormViewAutoFormat.cs
- TextTreeDeleteContentUndoUnit.cs
- StorageConditionPropertyMapping.cs
- DbProviderFactories.cs
- OutputCacheSettingsSection.cs
- MenuItemStyleCollection.cs
- PackagePart.cs
- HierarchicalDataSourceDesigner.cs
- DbConnectionPoolIdentity.cs
- TextSegment.cs
- SqlWebEventProvider.cs
- PropertyPathWorker.cs
- StringToken.cs
- WarningException.cs
- ChildrenQuery.cs
- MsmqBindingElementBase.cs
- DetailsView.cs
- SerTrace.cs
- ConstraintCollection.cs
- SchemaNotation.cs
- CodeConstructor.cs
- PolicyManager.cs
- SafeWaitHandle.cs
- EtwTrace.cs
- connectionpool.cs
- Point.cs
- SecuritySessionSecurityTokenProvider.cs
- TextSimpleMarkerProperties.cs
- ExpressionsCollectionEditor.cs
- ListenerElementsCollection.cs
- URL.cs
- HashCodeCombiner.cs
- QueryAsyncResult.cs
- CompositeControl.cs
- EpmSyndicationContentDeSerializer.cs
- WebPartZone.cs
- IndexerNameAttribute.cs
- WebZoneDesigner.cs
- XPathNavigatorKeyComparer.cs
- SqlDataSourceDesigner.cs
- MLangCodePageEncoding.cs
- HighContrastHelper.cs
- KeyConstraint.cs
- EditorZone.cs
- MessageContractExporter.cs
- HyperLinkColumn.cs
- OracleSqlParser.cs
- Int32Storage.cs
- DrawingGroup.cs
- TextWriterEngine.cs
- TimeoutValidationAttribute.cs
- WindowsListViewScroll.cs
- CustomActivityDesigner.cs
- DesignerAttribute.cs