|
//---------------------------------------------------------------------
// <copyright file="TransformationRules.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
// It is fine to use Debug.Assert in cases where you assert an obvious thing that is supposed
// to prevent from simple mistakes during development (e.g. method argument validation
// in cases where it was you who created the variables or the variables had already been validated or
// in "else" clauses where due to code changes (e.g. adding a new value to an enum type) the default
// "else" block is chosen why the new condition should be treated separately). This kind of asserts are
// (can be) helpful when developing new code to avoid simple mistakes but have no or little value in
// the shipped product.
// PlanCompiler.Assert *MUST* be used to verify conditions in the trees. These would be assumptions
// about how the tree was built etc. - in these cases we probably want to throw an exception (this is
// what PlanCompiler.Assert does when the condition is not met) if either the assumption is not correct
// or the tree was built/rewritten not the way we thought it was.
// Use your judgment - if you rather remove an assert than ship it use Debug.Assert otherwise use
// PlanCompiler.Assert.
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
/// <summary>
/// Whether any rule was applied that may have caused modifications such that projection pruning
/// may be useful
/// </summary>
internal bool ProjectionPrunningRequired { get { return this.m_projectionPrunningRequired; } }
/// <summary>
/// Whether any rule was applied that may have caused modifications such that reapplying
/// the nullability rules may be useful
/// </summary>
internal bool ReapplyNullabilityRules { get { return this.m_reapplyNullabilityRules; } }
/// <summary>
/// Remap the given subree using the current remapper
/// </summary>
/// <param name="subTree"></param>
internal void RemapSubtree(Node subTree)
{
this.m_remapper.RemapSubtree(subTree);
}
/// <summary>
/// Adds a mapping from oldVar to newVar
/// </summary>
/// <param name="oldVar"></param>
/// <param name="newVar"></param>
internal void AddVarMapping(Var oldVar, Var newVar)
{
m_remapper.AddMapping(oldVar, newVar);
m_remappedVars.Set(oldVar);
}
/// <summary>
/// "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.
///
/// </summary>
/// <param name="node">Current subtree to process</param>
/// <param name="varMap"></param>
/// <returns>The updated subtree</returns>
internal Node ReMap(Node node, Dictionary<Var, Node> 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;
}
/// <summary>
/// Makes a copy of the appropriate subtree - with a simple accelerator for VarRefOp
/// since that's likely to be the most command case
/// </summary>
/// <param name="node">the subtree to copy</param>
/// <returns>the copy of the subtree</returns>
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);
}
}
/// <summary>
/// Checks to see if the current subtree only contains ScalarOps
/// </summary>
/// <param name="node">current subtree</param>
/// <returns>true, if the subtree contains only ScalarOps</returns>
internal bool IsScalarOpTree(Node node)
{
int nodeCount = 0;
return IsScalarOpTree(node, null, ref nodeCount);
}
/// <summary>
/// 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.
/// </summary>
/// <param name="var"></param>
/// <returns></returns>
internal bool IsNonNullable(Var var)
{
foreach (Node relOpAncestor in m_relOpAncestors)
{
// Rules applied to the children of the relOpAncestor may have caused it change.
// Thus, if the node is used, it has to have its node info recomputed
Command.RecomputeNodeInfo(relOpAncestor);
ExtendedNodeInfo nodeInfo = Command.GetExtendedNodeInfo(relOpAncestor);
if (nodeInfo.NonNullableVisibleDefinitions.IsSet(var))
{
return true;
}
else if (nodeInfo.LocalDefinitions.IsSet(var))
{
//The var is defined on this ancestor but is not non-nullable,
// therefore there is no need to further check other ancestors
return false;
}
}
return false;
}
/// <summary>
/// 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.
/// </summary>
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;
}
}
/// <summary>
/// Is the op not safe for null sentinel value change
/// </summary>
/// <param name="optype"></param>
/// <returns></returns>
internal static bool IsOpNotSafeForNullSentinelValueChange(OpType optype)
{
return optype == OpType.Distinct ||
optype == OpType.GroupBy ||
optype == OpType.Intersect ||
optype == OpType.Except;
}
/// <summary>
/// Does the given subtree contain a node with an op that
/// is not safer for null sentinel value change
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
internal static bool HasOpNotSafeForNullSentinelValueChange(Node n)
{
if (IsOpNotSafeForNullSentinelValueChange(n.Op.OpType))
{
return true;
}
foreach (Node child in n.Children)
{
if (HasOpNotSafeForNullSentinelValueChange(child))
{
return true;
}
}
return false;
}
/// <summary>
/// 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
/// </summary>
/// <param name="node">current subtree</param>
/// <param name="varRefMap">dictionary of var refcounts to fill in</param>
/// <returns></returns>
internal bool IsScalarOpTree(Node node, Dictionary<Var, int> varRefMap)
{
PlanCompiler.Assert(varRefMap != null, "Null varRef map");
int nodeCount = 0;
return IsScalarOpTree(node, varRefMap, ref nodeCount);
}
/// <summary>
/// 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.
///
/// </summary>
/// <param name="varDefListNode">The varDefListOp subtree</param>
/// <param name="varRefMap">ref counts for each referenced var</param>
/// <returns>mapping from Var->replacement xpressions</returns>
internal Dictionary<Var, Node> GetVarMap(Node varDefListNode, Dictionary<Var, int> varRefMap)
{
VarDefListOp varDefListOp = (VarDefListOp)varDefListNode.Op;
Dictionary<Var, Node> varMap = new Dictionary<Var, Node>();
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;
}
/// <summary>
/// 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
/// </summary>
/// <param name="conditionVar">null discriminator var</param>
/// <param name="expr">expression</param>
/// <returns></returns>
internal Node BuildNullIfExpression(Var conditionVar, Node expr)
{
VarRefOp varRefOp = this.Command.CreateVarRefOp(conditionVar);
Node varRefNode = this.Command.CreateNode(varRefOp);
Node whenNode = this.Command.CreateNode(this.Command.CreateConditionalOp(OpType.IsNull), varRefNode);
Node elseNode = expr;
Node thenNode = this.Command.CreateNode(this.Command.CreateNullOp(elseNode.Op.Type));
Node caseNode = this.Command.CreateNode(this.Command.CreateCaseOp(elseNode.Op.Type), whenNode, thenNode, elseNode);
return caseNode;
}
#region Rule Interactions
/// <summary>
/// Shut off filter pushdown for this subtree
/// </summary>
/// <param name="n"></param>
internal void SuppressFilterPushdown(Node n)
{
m_suppressions[n] = n;
}
/// <summary>
/// Is filter pushdown shut off for this subtree?
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
internal bool IsFilterPushdownSuppressed(Node n)
{
return m_suppressions.ContainsKey(n);
}
/// <summary>
/// Given a list of vars try to get one that is of type Int32
/// </summary>
/// <param name="varList"></param>
/// <param name="int32Var"></param>
/// <returns></returns>
internal static bool TryGetInt32Var(IEnumerable<Var> varList, out Var int32Var)
{
foreach (Var v in varList)
{
// Any Int32 var regardless of the fasets will do
System.Data.Metadata.Edm.PrimitiveTypeKind typeKind;
if (System.Data.Common.TypeHelpers.TryGetPrimitiveTypeKind(v.Type, out typeKind) && typeKind == System.Data.Metadata.Edm.PrimitiveTypeKind.Int32)
{
int32Var = v;
return true;
}
}
int32Var = null;
return false;
}
#endregion
#endregion
#region constructors
internal TransformationRulesContext(PlanCompiler compilerState)
: base(compilerState.Command)
{
m_compilerState = compilerState;
m_remapper = new VarRemapper(compilerState.Command);
m_suppressions = new Dictionary<Node, Node>();
m_remappedVars = compilerState.Command.CreateVarVec();
}
#endregion
#region private state
private readonly PlanCompiler m_compilerState;
private readonly VarRemapper m_remapper;
private readonly Dictionary<Node, Node> m_suppressions;
private readonly VarVec m_remappedVars;
private bool m_projectionPrunningRequired = false;
private bool m_reapplyNullabilityRules = false;
private Stack<Node> m_relOpAncestors = new Stack<Node>();
#if DEBUG
/// <summary>
/// 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
/// </summary>
internal readonly System.Text.StringBuilder appliedRules = new System.Text.StringBuilder();
#endif
#endregion
#region RuleProcessingContext Overrides
/// <summary>
/// Callback function to invoke *before* rules are applied.
/// Calls the VarRemapper to update any Vars in this node, and recomputes
/// the nodeinfo
/// </summary>
/// <param name="n"></param>
internal override void PreProcess(Node n)
{
m_remapper.RemapNode(n);
Command.RecomputeNodeInfo(n);
}
/// <summary>
/// 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.
/// </summary>
/// <param name="subTree"></param>
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;
}
}
}
/// <summary>
/// If the given node has a RelOp it is popped from the relOp ancestors stack.
/// </summary>
/// <param name="subtree"></param>
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");
}
}
/// <summary>
/// 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.
/// </summary>
/// <param name="n"></param>
/// <param name="rule">the rule that was applied</param>
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);
}
}
/// <summary>
/// Get the hash value for this subtree
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
internal override int GetHashCode(Node node)
{
NodeInfo nodeInfo = Command.GetNodeInfo(node);
return nodeInfo.HashValue;
}
#endregion
#region private methods
/// <summary>
/// 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
/// </summary>
/// <param name="node">root of the subtree</param>
/// <param name="varRefMap">Ref counts for each Var encountered in the subtree</param>
/// <param name="nonLeafNodeCount">count of non-leaf nodes encountered in the subtree</param>
/// <returns>true, if this node only contains scalarOps</returns>
private bool IsScalarOpTree(Node node, Dictionary<Var, int> 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
}
/// <summary>
/// The list of all transformation rules to apply
/// </summary>
internal static class TransformationRules
{
/// <summary>
/// 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.
/// </summary>
internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> AllRulesTable = BuildLookupTableForRules(AllRules);
/// <summary>
/// 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.
/// </summary>
internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> ProjectRulesTable = BuildLookupTableForRules(ProjectOpRules.Rules);
/// <summary>
/// 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.
/// </summary>
internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> PostJoinEliminationRulesTable = BuildLookupTableForRules(PostJoinEliminationRules);
/// <summary>
/// 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.
/// </summary>
internal static readonly ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> NullabilityRulesTable = BuildLookupTableForRules(NullabilityRules);
/// <summary>
/// A look-up table of rules that may cause modifications such that projection pruning may be useful
/// after they have been applied.
/// </summary>
internal static readonly HashSet<InternalTrees.Rule> RulesRequiringProjectionPruning = InitializeRulesRequiringProjectionPruning();
/// <summary>
/// A look-up table of rules that may cause modifications such that reapplying the nullability rules
/// may be useful after they have been applied.
/// </summary>
internal static readonly HashSet<InternalTrees.Rule> RulesRequiringNullabilityRulesToBeReapplied = InitializeRulesRequiringNullabilityRulesToBeReapplied();
#region private state maintenance
private static List<InternalTrees.Rule> allRules;
private static List<InternalTrees.Rule> AllRules
{
get
{
if (allRules == null)
{
allRules = new List<InternalTrees.Rule>();
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<InternalTrees.Rule> postJoinEliminationRules;
private static List<InternalTrees.Rule> PostJoinEliminationRules
{
get
{
if (postJoinEliminationRules == null)
{
postJoinEliminationRules = new List<InternalTrees.Rule>();
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<InternalTrees.Rule> nullabilityRules;
private static List<InternalTrees.Rule> NullabilityRules
{
get
{
if (nullabilityRules == null)
{
nullabilityRules = new List<InternalTrees.Rule>();
nullabilityRules.Add(ScalarOpRules.Rule_IsNullOverVarRef);
nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred1);
nullabilityRules.Add(ScalarOpRules.Rule_AndOverConstantPred2);
nullabilityRules.Add(ScalarOpRules.Rule_SimplifyCase);
nullabilityRules.Add(ScalarOpRules.Rule_NotOverConstantPred);
}
return nullabilityRules;
}
}
private static ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> BuildLookupTableForRules(IEnumerable<InternalTrees.Rule> rules)
{
ReadOnlyCollection<InternalTrees.Rule> NoRules = new ReadOnlyCollection<InternalTrees.Rule>(new InternalTrees.Rule[0]);
List<InternalTrees.Rule>[] lookupTable = new List<InternalTrees.Rule>[(int)OpType.MaxMarker];
foreach (InternalTrees.Rule rule in rules)
{
List<InternalTrees.Rule> opRules = lookupTable[(int)rule.RuleOpType];
if (opRules == null)
{
opRules = new List<InternalTrees.Rule>();
lookupTable[(int)rule.RuleOpType] = opRules;
}
opRules.Add(rule);
}
ReadOnlyCollection<InternalTrees.Rule>[] rulesPerType = new ReadOnlyCollection<InternalTrees.Rule>[lookupTable.Length];
for (int i = 0; i < lookupTable.Length; ++i)
{
if (null != lookupTable[i])
{
rulesPerType[i] = new ReadOnlyCollection<InternalTrees.Rule>(lookupTable[i].ToArray());
}
else
{
rulesPerType[i] = NoRules;
}
}
return new ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>>(rulesPerType);
}
private static HashSet<InternalTrees.Rule> InitializeRulesRequiringProjectionPruning()
{
HashSet<InternalTrees.Rule> rulesRequiringProjectionPruning = new HashSet<InternalTrees.Rule>();
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<InternalTrees.Rule> InitializeRulesRequiringNullabilityRulesToBeReapplied()
{
HashSet<InternalTrees.Rule> rulesRequiringNullabilityRulesToBeReapplied = new HashSet<InternalTrees.Rule>();
rulesRequiringNullabilityRulesToBeReapplied.Add(FilterOpRules.Rule_FilterOverLeftOuterJoin);
return rulesRequiringNullabilityRulesToBeReapplied;
}
#endregion
/// <summary>
/// Apply the rules that belong to the specified group to the given query tree.
/// </summary>
/// <param name="compilerState"></param>
/// <param name="rulesGroup"></param>
internal static bool Process(PlanCompiler compilerState, TransformationRulesGroup rulesGroup)
{
ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> 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;
}
/// <summary>
/// Apply the rules that belong to the specified rules table to the given query tree.
/// </summary>
/// <param name="compilerState"></param>
/// <param name="rulesTable"></param>
/// <param name="projectionPruningRequired">is projection pruning required after the rule application</param>
/// <returns>Whether any rule has been applied after which reapplying nullability rules may be useful</returns>
private static bool Process(PlanCompiler compilerState, ReadOnlyCollection<ReadOnlyCollection<InternalTrees.Rule>> 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;
}
}
/// <summary>
/// Available groups of rules, not necessarily mutually exclusive
/// </summary>
internal enum TransformationRulesGroup
{
All,
Project,
PostJoinElimination
}
#region ScalarOpRules
/// <summary>
/// Transformation rules for ScalarOps
/// </summary>
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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule Processing context</param>
/// <param name="caseOpNode">The current subtree for the CaseOp</param>
/// <param name="newNode">the (possibly) modified subtree</param>
/// <returns>true, if we performed any transformations</returns>
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;
}
/// <summary>
/// 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
/// </summary>
/// <param name="caseOp">the current caseOp</param>
/// <param name="caseOpNode">current subtree</param>
/// <param name="newNode">new subtree</param>
/// <returns>true, if we performed a transformation</returns>
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;
}
/// <summary>
/// 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
/// </summary>
/// <param name="context">rule processing context</param>
/// <param name="caseOp">current caseOp</param>
/// <param name="caseOpNode">Current subtree</param>
/// <param name="newNode">the new subtree</param>
/// <returns>true, if there was a transformation</returns>
private static bool ProcessSimplifyCase_EliminateWhenClauses(RuleProcessingContext context, CaseOp caseOp, Node caseOpNode, out Node newNode)
{
List<Node> 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<Node>();
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;
}
/// <summary>
/// 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
/// </summary>
/// <param name="caseOp">the current caseOp</param>
/// <param name="caseOpNode">current subtree</param>
/// <param name="newNode">new subtree</param>
/// <returns>true, if we performed a transformation</returns>
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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="node">current node</param>
/// <param name="newNode">possibly modified subtree</param>
/// <returns>true, if transformation was successful</returns>
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);
/// <summary>
/// Transform
/// AND(x, true) => x;
/// AND(true, x) => x
/// AND(x, false) => false
/// AND(false, x) => false
///
/// </summary>
/// <param name="context">Rule Processing context</param>
/// <param name="node">Current LogOp (And, Or, Not) node</param>
/// <param name="constantPredicateNode">constant predicate node</param>
/// <param name="otherNode">The other child of the LogOp (possibly null)</param>
/// <param name="newNode">new subtree</param>
/// <returns>transformation status</returns>
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);
/// <summary>
/// Convert a
/// IsNull(constant)
/// to just the
/// False predicate
/// </summary>
/// <param name="context"></param>
/// <param name="isNullNode"></param>
/// <param name="newNode">new subtree</param>
/// <returns></returns>
static bool ProcessIsNullOverConstant(RuleProcessingContext context, Node isNullNode, out Node newNode)
{
newNode = context.Command.CreateNode(context.Command.CreateFalseOp());
return true;
}
internal static readonly PatternMatchRule Rule_IsNullOverNull =
new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
new Node(NullOp.Pattern)),
ProcessIsNullOverNull);
/// <summary>
/// Convert an IsNull(null) to just the 'true' predicate
/// </summary>
/// <param name="context"></param>
/// <param name="isNullNode"></param>
/// <param name="newNode">new subtree</param>
/// <returns></returns>
static bool ProcessIsNullOverNull(RuleProcessingContext context, Node isNullNode, out Node newNode)
{
newNode = context.Command.CreateNode(context.Command.CreateTrueOp());
return true;
}
#endregion
#region CastOp(NullOp) Rule
internal static readonly PatternMatchRule Rule_NullCast = new PatternMatchRule(
new Node(CastOp.Pattern,
new Node(NullOp.Pattern)),
ProcessNullCast);
/// <summary>
/// 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]
/// </summary>
/// <param name="context"></param>
/// <param name="castNullOp"></param>
/// <param name="newNode">modified subtree</param>
/// <returns></returns>
static bool ProcessNullCast(RuleProcessingContext context, Node castNullOp, out Node newNode)
{
newNode = context.Command.CreateNode(context.Command.CreateNullOp(castNullOp.Op.Type));
return true;
}
#endregion
#region IsNull over VarRef
internal static readonly PatternMatchRule Rule_IsNullOverVarRef =
new PatternMatchRule(new Node(ConditionalOp.PatternIsNull,
new Node(VarRefOp.Pattern)),
ProcessIsNullOverVarRef);
/// <summary>
/// Convert a
/// IsNull(VarRef(v))
/// to just the
/// False predicate
///
/// if v is guaranteed to be non nullable.
/// </summary>
/// <param name="context"></param>
/// <param name="isNullNode"></param>
/// <param name="newNode">new subtree</param>
/// <returns></returns>
static bool ProcessIsNullOverVarRef(RuleProcessingContext context, Node isNullNode, out Node newNode)
{
Command command = context.Command;
TransformationRulesContext trc = (TransformationRulesContext)context;
Var v = ((VarRefOp)isNullNode.Child0.Op).Var;
if (trc.IsNonNullable(v))
{
newNode = command.CreateNode(context.Command.CreateFalseOp());
return true;
}
else
{
newNode = isNullNode;
return false;
}
}
#endregion
#region All ScalarOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
Rule_SimplifyCase,
Rule_FlattenCase,
Rule_LikeOverConstants,
Rule_EqualsOverConstant,
Rule_AndOverConstantPred1,
Rule_AndOverConstantPred2,
Rule_OrOverConstantPred1,
Rule_OrOverConstantPred2,
Rule_NotOverConstantPred,
Rule_IsNullOverConstant,
Rule_IsNullOverNullSentinel,
Rule_IsNullOverNull,
Rule_NullCast,
Rule_IsNullOverVarRef,
};
#endregion
}
#endregion
#region Filter Rules
/// <summary>
/// Transformation rules for FilterOps
/// </summary>
internal static class FilterOpRules
{
#region Helpers
/// <summary>
/// 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
///
/// </summary>
/// <param name="command">Command object</param>
/// <param name="filterNode">the FilterOp subtree</param>
/// <param name="columns">(Optional) List of columns to consider for "pushdown"</param>
/// <param name="nonPushdownPredicateNode">(output) Part of the predicate that cannot be pushed down</param>
/// <returns>part of the predicate that can be pushed down</returns>
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);
/// <summary>
/// Convert Filter(Filter(X, p1), p2) => Filter(X, (p1 and p2))
/// </summary>
/// <param name="context">rule processing context</param>
/// <param name="filterNode">FilterOp node</param>
/// <param name="newNode">modified subtree</param>
/// <returns>transformed subtree</returns>
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);
/// <summary>
/// Convert Filter(Project(X, ...), p) => Project(Filter(X, p'), ...)
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="filterNode">FilterOp subtree</param>
/// <param name="newNode">modified subtree</param>
/// <returns>transformed subtree</returns>
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<Var, int> varRefMap = new Dictionary<Var, int>();
if (!trc.IsScalarOpTree(predicateNode, varRefMap))
{
return false;
}
//
// check to see if all expressions in the project can be inlined
//
Node projectNode = filterNode.Child0;
Dictionary<Var, Node> 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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="filterNode">FilterOp subtree</param>
/// <param name="newNode">modified subtree</param>
/// <returns>true, if successful transformation</returns>
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<Node> newSetOpChildren = new List<Node>();
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<Var, Node> remapMap = new Dictionary<Var, Node>();
foreach (KeyValuePair<Var, Var> 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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="filterNode">FilterOp subtree</param>
/// <param name="newNode">modified subtree</param>
/// <returns>Transformation status</returns>
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);
/// <summary>
/// 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",
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="filterNode">Current FilterOp subtree</param>
/// <param name="newNode">modified subtree</param>
/// <returns>Transformation status</returns>
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<Var, int> varRefMap = new Dictionary<Var, int>();
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<Var, Node> 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);
/// <summary>
/// Transform Filter()
/// </summary>
/// <param name="context">Rule Processing context</param>
/// <param name="filterNode">Current FilterOp subtree</param>
/// <param name="newNode">Modified subtree</param>
/// <returns>Transformation status</returns>
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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="filterNode">Filter node</param>
/// <param name="newNode">modified subtree</param>
/// <returns>transformation status</returns>
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);
/// <summary>
/// Convert
/// Filter(X, true) => X
/// Filter(X, false) => Project(Filter(SingleRowTableOp, ...), false)
/// where ... represent variables that are equivalent to the table columns
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">Current subtree</param>
/// <param name="newNode">modified subtree</param>
/// <returns>transformation status</returns>
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<Node> varDefNodeList = new List<Node>();
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
/// <summary>
/// Transformation rules for ProjectOp
/// </summary>
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);
/// <summary>
/// Converts a Project(Project(X, c1,...), d1,...) =>
/// Project(X, d1', d2'...)
/// where d1', d2' etc. are the "mapped" versions of d1, d2 etc.
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="projectNode">Current ProjectOp node</param>
/// <param name="newNode">modified subtree</param>
/// <returns>Transformation status</returns>
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<Var, int> varRefMap = new Dictionary<Var, int>();
foreach (Node varDefNode in varDefListNode.Children)
{
if (!trc.IsScalarOpTree(varDefNode.Child0, varRefMap))
{
return false;
}
}
Dictionary<Var, Node> 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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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<Node> newVarDefNodes = new List<Node>();
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);
/// <summary>
/// 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.
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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
/// <summary>
/// Transformation rules for ApplyOps - CrossApply, OuterApply
/// </summary>
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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="applyNode">Current ApplyOp</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>Transformation status</returns>
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);
/// <summary>
/// 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
///
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="applyNode">Current ApplyOp</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>Transformation status</returns>
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);
/// <summary>
/// Converts a CrossApply(X, Project(Y, ...)) => Project(CrossApply(X, Y), ...)
/// where the projectVars are simply pulled up
/// </summary>
/// <param name="context">RuleProcessing context</param>
/// <param name="applyNode">The ApplyOp subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>Transfomation status</returns>
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);
/// <summary>
/// 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.
///
/// </summary>
/// <param name="context">RuleProcessing context</param>
/// <param name="applyNode">The ApplyOp subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>Transfomation status</returns>
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);
/// <summary>
/// Converts a CrossApply(X,Y) => CrossJoin(X,Y)
/// OuterApply(X,Y) => LeftOuterJoin(X, Y, true)
/// only if Y has no external references to X
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="applyNode">The ApplyOp subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>the transformation status</returns>
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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="applyNode">The ApplyOp subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>the transformation status</returns>
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;
}
/// <summary>
/// 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
/// </summary>
/// <param name="rightChild"></param>
/// <param name="applyRightChildNodeInfo"></param>
/// <param name="applyKind"></param>
/// <returns></returns>
private static bool CanRewriteApply(Node rightChild, ExtendedNodeInfo applyRightChildNodeInfo, OpType applyKind)
{
//Check whether it produces only one definition
if (applyRightChildNodeInfo.Definitions.Count != 1)
{
return false;
}
//Check whether it produces at most one row
if (applyRightChildNodeInfo.MaxRows != RowCount.One)
{
return false;
}
//For cross apply it must also return exactly one row
if (applyKind == OpType.CrossApply && (applyRightChildNodeInfo.MinRows != RowCount.One))
{
return false;
}
//Dev10 #488632: Make sure the right child not only declares to produce only one definition,
// but has exactly one output. For example, ScanTableOp really outputs all the columns from the table,
// but in its ExtendedNodeInfo.Definitions only these that are referenced are shown.
// This is to allow for projection pruning of the unreferenced columns.
if (OutputCountVisitor.CountOutputs(rightChild) != 1)
{
return false;
}
return true;
}
/// <summary>
/// A visitor that calculates the number of output columns for a subree
/// with a given root
/// </summary>
internal class OutputCountVisitor : BasicOpVisitorOfT<int>
{
#region Constructors
internal OutputCountVisitor()
{
}
#endregion
#region Public Methods
/// <summary>
/// Calculates the number of output columns for the subree
/// rooted at the given node
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
internal static int CountOutputs(Node node)
{
OutputCountVisitor visitor = new OutputCountVisitor();
return visitor.VisitNode(node);
}
#endregion
#region Visitor Methods
#region Helpers
/// <summary>
/// Visitor for children. Simply visit all children,
/// and sum the number of their outputs.
/// </summary>
/// <param name="n">Current node</param>
/// <returns></returns>
internal new int VisitChildren(Node n)
{
int result = 0;
foreach (Node child in n.Children)
{
result += VisitNode(child);
}
return result;
}
/// <summary>
/// A default processor for any node.
/// Returns the sum of the children outputs
/// </summary>
/// <param name="n"></param>
/// <returns>/returns>
protected override int VisitDefault(Node n)
{
return VisitChildren(n);
}
#endregion
#region RelOp Visitors
#region SetOp Visitors
/// <summary>
/// The number of outputs is same as for any of the inputs
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
protected override int VisitSetOp(SetOp op, Node n)
{
return op.Outputs.Count;
}
#endregion
/// <summary>
/// Distinct
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override int Visit(DistinctOp op, Node n)
{
return op.Keys.Count;
}
/// <summary>
/// FilterOp
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override int Visit(FilterOp op, Node n)
{
return VisitNode(n.Child0);
}
/// <summary>
/// GroupByOp
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override int Visit(GroupByOp op, Node n)
{
return op.Outputs.Count;
}
/// <summary>
/// ProjectOp
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override int Visit(ProjectOp op, Node n)
{
return op.Outputs.Count;
}
#region TableOps
/// <summary>
/// ScanTableOp
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override int Visit(ScanTableOp op, Node n)
{
return op.Table.Columns.Count;
}
/// <summary>
/// SingleRowTableOp
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override int Visit(SingleRowTableOp op, Node n)
{
return 0;
}
/// <summary>
/// Same as the input
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
protected override int VisitSortOp(SortBaseOp op, Node n)
{
return VisitNode(n.Child0);
}
#endregion
#endregion
#endregion
}
/// <summary>
/// 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.
/// </summary>
internal class VarDefinitionRemapper : VarRemapper
{
private readonly Var m_oldVar;
private VarDefinitionRemapper(Var oldVar, Command command)
: base(command)
{
this.m_oldVar = oldVar;
}
/// <summary>
/// Public entry point.
/// Remaps the subree rooted at the given tree
/// </summary>
/// <param name="root"></param>
/// <param name="command"></param>
/// <param name="oldVar"></param>
internal static void RemapSubtree(Node root, Command command, Var oldVar)
{
VarDefinitionRemapper remapper = new VarDefinitionRemapper(oldVar, command);
remapper.RemapSubtree(root);
}
/// <summary>
/// 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.
/// </summary>
/// <param name="subTree"></param>
internal override void RemapSubtree(Node subTree)
{
foreach (Node chi in subTree.Children)
{
RemapSubtree(chi);
}
VisitNode(subTree);
m_command.RecomputeNodeInfo(subTree);
}
/// <summary>
/// If the node defines the node that needs to be remapped,
/// it remaps it to a new var.
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override void Visit(VarDefOp op, Node n)
{
if (op.Var == m_oldVar)
{
Var newVar = m_command.CreateComputedVar(n.Child0.Op.Type);
n.Op = m_command.CreateVarDefOp(newVar);
AddMapping(m_oldVar, newVar);
}
}
/// <summary>
/// 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.
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
/// <returns></returns>
public override void Visit(ScanTableOp op, Node n)
{
if (op.Table.Columns.Contains(m_oldVar))
{
ScanTableOp newScanTableOp = m_command.CreateScanTableOp(op.Table.TableMetadata);
VarDefListOp varDefListOp = m_command.CreateVarDefListOp();
for (int i = 0; i < op.Table.Columns.Count; i++)
{
AddMapping(op.Table.Columns[i], newScanTableOp.Table.Columns[i]);
}
n.Op = newScanTableOp;
}
}
/// <summary>
/// The var that needs to be remapped may be produced by a set op,
/// in which case the varmaps need to be updated too.
/// </summary>
/// <param name="op"></param>
/// <param name="n"></param>
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);
}
}
/// <summary>
/// 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.
/// </summary>
/// <param name="varMap"></param>
/// <param name="newVar"></param>
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);
/// <summary>
/// Convert a CrossApply(X, LeftOuterJoin(SingleRowTable, Y, on true))
/// into just OuterApply(X, Y)
/// </summary>
/// <param name="context">rule processing context</param>
/// <param name="joinNode">the join node</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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
/// <summary>
/// Transformation rules for JoinOps
/// </summary>
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);
/// <summary>
/// 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)
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="joinNode">Current JoinOp tree to process</param>
/// <param name="newNode">Transformed subtree</param>
/// <returns>transformation status</returns>
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<Var, int> varRefMap = new Dictionary<Var, int>();
if (joinConditionNode != null && !trc.IsScalarOpTree(joinConditionNode, varRefMap))
{
return false;
}
Node newJoinNode;
Node newProjectNode;
// Now locate the ProjectOps
VarVec newVarSet = command.CreateVarVec();
List<Node> varDefNodes = new List<Node>();
//
// 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<Var, Node> varMap1 = trc.GetVarMap(joinNode.Child0.Child1, varRefMap);
Dictionary<Var, Node> 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<Var, Node> 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);
/// <summary>
/// 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.
///
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="joinNode">Current JoinOp tree to process</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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);
/// <summary>
/// Convert a CrossJoin(SingleRowTable, X) or CrossJoin(X, SingleRowTable) or LeftOuterJoin(X, SingleRowTable)
/// into just "X"
/// </summary>
/// <param name="context">rule processing context</param>
/// <param name="joinNode">the join node</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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
/// <summary>
/// Rules for SingleRowOp
/// </summary>
internal static class SingleRowOpRules
{
internal static readonly PatternMatchRule Rule_SingleRowOpOverAnything =
new PatternMatchRule(new Node(SingleRowOp.Pattern,
new Node(LeafOp.Pattern)),
ProcessSingleRowOpOverAnything);
/// <summary>
/// Convert a
/// SingleRowOp(X) => X
/// if X produces at most one row
/// </summary>
/// <param name="context">Rule Processing context</param>
/// <param name="singleRowNode">Current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>Transformation status</returns>
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);
/// <summary>
/// Convert
/// SingleRowOp(Project) => Project(SingleRowOp)
/// </summary>
/// <param name="context">Rule Processing context</param>
/// <param name="singleRowNode">current subtree</param>
/// <param name="newNode">transformeed subtree</param>
/// <returns>transformation status</returns>
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
/// <summary>
/// SetOp Transformation Rules
/// </summary>
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);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="setOpNode">the current setop tree</param>
/// <param name="filterNodeIndex">Index of the filter node in the setop</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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<Var, Var> 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
/// <summary>
/// Transformation Rules for GroupByOps
/// </summary>
internal static class GroupByOpRules
{
#region GroupByOpWithSimpleVarRedefinitions
internal static readonly SimpleRule Rule_GroupByOpWithSimpleVarRedefinitions = new SimpleRule(OpType.GroupBy, ProcessGroupByWithSimpleVarRedefinitions);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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<Node> newVarDefNodes = new List<Node>();
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);
/// <summary>
/// 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.
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="projectNode">Current ProjectOp node</param>
/// <param name="newNode">modified subtree</param>
/// <returns>Transformation status</returns>
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<Var, Node> varToDefiningNode = new Dictionary<Var, Node>(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;
}
/// <summary>
/// Replaces each occurance of the given vars with their definitions.
/// </summary>
internal class VarRefReplacer : BasicOpVisitorOfNode
{
private Dictionary<Var, Node> m_varReplacementTable;
private Command m_command;
private VarRefReplacer(Dictionary<Var, Node> varReplacementTable, Command command)
{
this.m_varReplacementTable = varReplacementTable;
this.m_command = command;
}
/// <summary>
/// "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.
/// </summary>
/// <param name="varReplacementTable"></param>
/// <param name="root"></param>
/// <param name="command"></param>
/// <returns></returns>
internal static Node Replace(Dictionary<Var, Node> 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;
}
}
/// <summary>
/// Recomputes node info post regular processing.
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
protected override Node VisitDefault(Node n)
{
Node result = base.VisitDefault(n);
m_command.RecomputeNodeInfo(result);
return result;
}
}
/// <summary>
/// Used to determine whether any of the given vars occurs more than once
/// in a given subtree.
/// </summary>
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();
}
/// <summary>
/// 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.
/// </summary>
/// <param name="varVec"></param>
/// <param name="root"></param>
/// <param name="command"></param>
/// <returns></returns>
internal static bool AnyVarUsedMoreThanOnce(VarVec varVec, Node root, Command command)
{
VarRefUsageFinder usageFinder = new VarRefUsageFinder(varVec, command);
usageFinder.VisitNode(root);
return usageFinder.m_anyUsedMoreThenOnce;
}
public override void Visit(VarRefOp op, Node n)
{
Var referencedVar = op.Var;
if (m_varVec.IsSet(referencedVar))
{
if (m_usedVars.IsSet(referencedVar))
{
this.m_anyUsedMoreThenOnce = true;
}
else
{
m_usedVars.Set(referencedVar);
}
}
}
protected override void VisitChildren(Node n)
{
//small optimization: no need to continue if we have the answer
if (m_anyUsedMoreThenOnce)
{
return;
}
base.VisitChildren(n);
}
}
#endregion
#region GroupByOpWithNoAggregates
internal static readonly PatternMatchRule Rule_GroupByOpWithNoAggregates =
new PatternMatchRule(new Node(GroupByOp.Pattern,
new Node(LeafOp.Pattern),
new Node(LeafOp.Pattern),
new Node(VarDefListOp.Pattern)),
ProcessGroupByOpWithNoAggregates);
/// <summary>
/// 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)
///
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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 GroupByOpOnAllInputColumnsWithAggregateOperation
internal static readonly SimpleRule Rule_GroupByOpOnAllInputColumnsWithAggregateOperation = new SimpleRule(
OpType.GroupBy, ProcessGroupByOpOnAllInputColumnsWithAggregateOperation);
/// <summary>
/// Converts a GroupBy(X, Y, Z) => OuterApply(X', GroupBy(Filter(X, key(X') == key(X)), Y, Z))
/// if and only if X is a ScanTableOp, and Z is the upper node of an aggregate function and
/// the group by operation uses all the columns of X as the key.
/// Additionally, the top-level physical projection must only expose one variable. If it exposes
/// more than one (more than just the aggregate itself), then this rule must not apply.
/// This is a fix for devdiv bug 851732. Since now we're supporting NewRecordOp nodes as
/// part of the GroupBy aggregate variable computations, we are also respecting the fact that
/// group by (e => e) means that we're grouping by all columns of entity e. This was not a
/// problem when the NewRecordOp node was not being processed since this caused the GroupBy
/// statement to be simplified to a form with no keys and no output columns. The generated SQL
/// is correct, but it is different from what it used to be and may be incompatible if the
/// entity contains fields with datatypes that do not support being grouped by, such as blobs
/// and images.
/// This rule simplifies the tree so that we remain compatible with the way we were generating
/// queries that contain group by (e => e).
/// What this does is enabling the tree to take a shape that further optimization can convert
/// into an expression that groups by the key of the table and calls the aggregate function
/// as expected.
/// </summary>
/// <param name="context"> Rule processing context </param>
/// <param name="n"> Current ProjectOp node </param>
/// <param name="newNode"> modified subtree </param>
/// <returns> Transformation status </returns>
private static bool ProcessGroupByOpOnAllInputColumnsWithAggregateOperation(RuleProcessingContext context, Node n, out Node newNode)
{
newNode = n;
var rootOp = context.Command.Root.Op as PhysicalProjectOp;
if (rootOp == null ||
rootOp.Outputs.Count > 1)
{
return false;
}
if (n.Child0.Op.OpType != OpType.ScanTable)
{
return false;
}
if (n.Child2 == null
|| n.Child2.Child0 == null
|| n.Child2.Child0.Child0 == null
|| n.Child2.Child0.Child0.Op.OpType != OpType.Aggregate)
{
return false;
}
var groupByOp = (GroupByOp)n.Op;
var sourceTable = ((ScanTableOp)n.Child0.Op).Table;
var allInputColumns = sourceTable.Columns;
// Exit if the group's keys do not contain all the columns defined by Child0
foreach (var column in allInputColumns)
{
if (!groupByOp.Keys.IsSet(column))
{
return false;
}
}
// All the columns of Child0 are used, so remove them from the outputs and the keys
foreach (var column in allInputColumns)
{
groupByOp.Outputs.Clear(column);
groupByOp.Keys.Clear(column);
}
// Build the OuterApply and also set the filter around the GroupBy's scan table.
var command = context.Command;
var scanTableOp = command.CreateScanTableOp(sourceTable.TableMetadata);
var scanTable = command.CreateNode(scanTableOp);
var outerApplyNode = command.CreateNode(command.CreateOuterApplyOp(), scanTable, n);
Var newVar;
var varDefListNode = command.CreateVarDefListNode(command.CreateNode(command.CreateVarRefOp(groupByOp.Outputs.First)), out newVar);
newNode = command.CreateNode(
command.CreateProjectOp(newVar),
outerApplyNode,
varDefListNode);
Node equality = null;
var leftKeys = scanTableOp.Table.Keys.GetEnumerator();
var rightKeys = sourceTable.Keys.GetEnumerator();
for (int i = 0; i < sourceTable.Keys.Count; ++i)
{
leftKeys.MoveNext();
rightKeys.MoveNext();
var comparison = command.CreateNode(
command.CreateComparisonOp(OpType.EQ),
command.CreateNode(command.CreateVarRefOp(leftKeys.Current)),
command.CreateNode(command.CreateVarRefOp(rightKeys.Current)));
if (equality != null)
{
equality = command.CreateNode(
command.CreateConditionalOp(OpType.And),
equality, comparison);
}
else
{
equality = comparison;
}
}
var filter = command.CreateNode(command.CreateFilterOp(),
n.Child0,
equality);
n.Child0 = filter;
return true; // subtree modified
}
#endregion
#region All GroupByOp Rules
internal static readonly InternalTrees.Rule[] Rules = new InternalTrees.Rule[] {
GroupByOpRules.Rule_GroupByOpWithSimpleVarRedefinitions,
GroupByOpRules.Rule_GroupByOverProject,
GroupByOpRules.Rule_GroupByOpWithNoAggregates,
GroupByOpRules.Rule_GroupByOpOnAllInputColumnsWithAggregateOperation,
};
#endregion
}
#endregion
#region Sorting Rules
/// <summary>
/// Transformation Rules for SortOp
/// </summary>
internal static class SortOpRules
{
#region SortOpOverAtMostOneRow
internal static readonly SimpleRule Rule_SortOpOverAtMostOneRow = new SimpleRule(OpType.Sort, ProcessSortOpOverAtMostOneRow);
/// <summary>
/// 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
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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
}
/// <summary>
/// Transformation Rules for ConstrainedSortOp
/// </summary>
internal static class ConstrainedSortOpRules
{
#region ConstrainedSortOpOverEmptySet
internal static readonly SimpleRule Rule_ConstrainedSortOpOverEmptySet = new SimpleRule(OpType.ConstrainedSort, ProcessConstrainedSortOpOverEmptySet);
/// <summary>
/// If the ConstrainedSortOp's input is guaranteed to produce no rows, remove the ConstrainedSortOp completly:
/// CSort(EmptySet) => EmptySet
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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
/// <summary>
/// Transformation Rules for DistinctOp
/// </summary>
internal static class DistinctOpRules
{
#region DistinctOpOfKeys
internal static readonly SimpleRule Rule_DistinctOpOfKeys = new SimpleRule(OpType.Distinct, ProcessDistinctOpOfKeys);
/// <summary>
/// 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.
/// </summary>
/// <param name="context">Rule processing context</param>
/// <param name="n">current subtree</param>
/// <param name="newNode">transformed subtree</param>
/// <returns>transformation status</returns>
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
}
|