Code:
/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / JoinGraph.cs / 3 / JoinGraph.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization;
using System.Data.Query.InternalTrees;
using md = System.Data.Metadata.Edm;
//
// The JoinGraph module is responsible for performing the following kinds of
// join elimination.
// This module deals with the following kinds of joins
// * Self-joins: The join can be eliminated, and either of the table instances can be
// used instead
// * Implied self-joins: Same as above
// * PK-FK joins: (More generally, UK-FK joins): Eliminate the join, and use just the FK table, if no
// column of the PK table is used (other than the join condition)
// * PK-PK joins: Eliminate the right side table, if we have a left-outer join
//
// This module is organized into the following phases.
// * Building an Augmented Tree: In this phase, the original node tree is annotated
// with additional information, and a new "augmented" tree is built up
// * Building up Join Edges: In this phase, the augmented tree is used to populate
// the join graph with equi-join edges
// * Generating transitive edges: Generate transitive join edges
// * Parent-Child (PK-FK) Join Elimination: We walk through the list of join edges, and
// eliminate any redundant tables in parent-child joins
// * Self-join Elimination: We walk through the list of join edges, and eliminate
// any redundant tables
// * Rebuilding the node tree: The augmented node tree is now converted back into
// a regular node tree.
//
namespace System.Data.Query.PlanCompiler
{
#region AugmentedNode
//
// This region describes a number of classes that are used to build an annotated
// (or augmented) node tree. There are 3 main classes defined here
// AugmentedNode - this is the base class for all annotations. This class
// wraps a Node, an id for the node (where the "id" is assigned in DFS order),
// and a list of children. All Nodes that are neither joins, nor scanTables
// are represented by this class
// AugmentedTableNode - the augmentedTableNode is a subclass of AugmentedNode,
// and represents a ScanTable node. In addition to the information above, this
// class keeps track of all join edges that this node participates in,
// whether this table has been eliminated, and finally, how high in the tree
// this node is visible
// AugmentedJoinNode - represents all joins (cross-joins, leftouter, fullouter
// and innerjoins). This class represents a number of column equijoin conditions
// via the LeftVars and RightVars properties, and also keeps track of additional
// (non-equijoin column) join predicates
//
///
/// Additional information for a node.
///
internal class AugmentedNode
{
#region private state
private int m_id;
private Node m_node;
protected AugmentedNode m_parent;
private List m_children;
#endregion
#region constructors
///
/// basic constructor
///
/// Id for this node
/// current node
internal AugmentedNode(int id, Node node)
: this(id, node, new List())
{
}
///
/// Yet another constructor
///
/// Id for this node
/// current node
/// list of children
internal AugmentedNode(int id, Node node, List children)
{
m_id = id;
m_node = node;
m_children = children;
PlanCompiler.Assert(children != null, "null children (gasp!)");
foreach (AugmentedNode chi in m_children)
{
chi.m_parent = this;
}
}
#endregion
#region public properties
///
/// Id of this node
///
internal int Id { get { return m_id; } }
///
/// The node
///
internal Node Node { get { return m_node; } }
///
/// Parent node
///
internal AugmentedNode Parent
{
get { return m_parent; }
}
///
/// List of children
///
internal List Children
{
get { return m_children; }
}
#endregion
}
///
/// Additional information for a "Table" node
///
internal sealed class AugmentedTableNode : AugmentedNode
{
#region private state
private int m_lastVisibleId;
private Table m_table;
private List m_joinEdges;
// The replacement table
private AugmentedTableNode m_replacementTable;
// Is this table being moved
private int m_newLocationId;
// List of columns of this table that are nullable (and must have nulls pruned out)
private VarVec m_nullableColumns;
#endregion
#region constructors
///
/// Basic constructor
///
/// node id
/// scan table node
internal AugmentedTableNode(int id, Node node) : base(id, node)
{
ScanTableOp scanTableOp = (ScanTableOp)node.Op;
m_table = scanTableOp.Table;
m_joinEdges = new List();
m_lastVisibleId = id;
m_replacementTable = this;
m_newLocationId = id;
}
#endregion
#region public properties
///
/// The Table
///
internal Table Table { get { return m_table; } }
///
/// List of directed edges in which this table is the "left" table
///
internal List JoinEdges
{
get { return m_joinEdges; }
}
///
/// The highest node (id) at which this table is visible
///
internal int LastVisibleId
{
get { return m_lastVisibleId; }
set { m_lastVisibleId = value; }
}
///
/// Has this table been eliminated
///
internal bool IsEliminated
{
get { return m_replacementTable != this; }
}
///
/// The replacement table (if any) for this table
///
internal AugmentedTableNode ReplacementTable
{
get { return m_replacementTable; }
set { m_replacementTable = value; }
}
///
/// New location for this table
///
internal int NewLocationId
{
get { return m_newLocationId; }
set { m_newLocationId = value; }
}
///
/// Has this table "moved" ?
///
internal bool IsMoved
{
get { return m_newLocationId != this.Id; }
}
///
/// Get the list of nullable columns (that require special handling)
///
internal VarVec NullableColumns
{
get { return m_nullableColumns; }
set { m_nullableColumns = value; }
}
#endregion
}
///
/// Additional information for a JoinNode
///
internal sealed class AugmentedJoinNode : AugmentedNode
{
#region private state
private List m_leftVars;
private List m_rightVars;
private Node m_otherPredicate;
#endregion
#region constructors
///
/// basic constructor
///
/// current node id
/// the join node
/// left side of the join (innerJoin, LOJ and FOJ only)
/// right side of the join
/// left-side equijoin vars
/// right-side equijoin vars
/// any remaining predicate
internal AugmentedJoinNode(int id, Node node,
AugmentedNode leftChild, AugmentedNode rightChild,
List leftVars, List rightVars,
Node otherPredicate)
: this(id, node, new List(new AugmentedNode[] {leftChild, rightChild}))
{
m_otherPredicate = otherPredicate;
m_rightVars = rightVars;
m_leftVars = leftVars;
}
///
/// Yet another constructor - used for crossjoins
///
/// node id
/// current node
/// list of children
internal AugmentedJoinNode(int id, Node node, List children)
: base(id, node, children)
{
m_leftVars = new List();
m_rightVars = new List();
}
#endregion
#region public properties
///
/// Non-equijoin predicate
///
internal Node OtherPredicate { get { return m_otherPredicate; } }
///
/// Equijoin columns of the left side
///
internal List LeftVars { get { return m_leftVars; } }
///
/// Equijoin columns of the right side
///
internal List RightVars { get { return m_rightVars; } }
#endregion
#region private methods
#endregion
}
#endregion
#region JoinGraph
///
/// The only join kinds we care about
///
internal enum JoinKind
{
Inner,
LeftOuter
}
///
/// Represents an "edge" in the join graph.
/// A JoinEdge is a directed equijoin between the left and the right table. The equijoin
/// columns are represented by the LeftVars and the RightVars properties
///
internal class JoinEdge
{
#region private state
private AugmentedTableNode m_left;
private AugmentedTableNode m_right;
private AugmentedJoinNode m_joinNode;
private JoinKind m_joinKind;
private List m_leftVars;
private List m_rightVars;
#endregion
#region constructors
///
/// Internal constructor
///
/// the left table
/// the right table
/// the owner join node
/// the Join Kind
/// list of equijoin columns of the left table
/// equijoin columns of the right table
private JoinEdge(AugmentedTableNode left, AugmentedTableNode right,
AugmentedJoinNode joinNode, JoinKind joinKind,
List leftVars, List rightVars)
{
m_left = left;
m_right = right;
m_joinKind = joinKind;
m_joinNode = joinNode;
m_leftVars = leftVars;
m_rightVars = rightVars;
PlanCompiler.Assert(m_leftVars.Count == m_rightVars.Count, "Count mismatch: " + m_leftVars.Count + "," + m_rightVars.Count);
}
#endregion
#region public apis
///
/// The left table
///
internal AugmentedTableNode Left { get { return m_left; } }
///
/// The right table of the join
///
internal AugmentedTableNode Right { get { return m_right; } }
///
/// The underlying join node, may be null
///
internal AugmentedJoinNode JoinNode { get { return m_joinNode; } }
///
/// The join kind
///
internal JoinKind JoinKind { get { return m_joinKind; } }
///
/// Equijoin columns of the left table
///
internal List LeftVars { get { return m_leftVars; } }
///
/// Equijoin columns of the right table
///
internal List RightVars { get { return m_rightVars; } }
///
/// Is this join edge useless?
///
internal bool IsEliminated
{
get { return this.Left.IsEliminated || this.Right.IsEliminated; }
}
///
/// Factory method
///
/// left table
/// right table
/// the owner join node
/// equijoin column of the left table
/// equijoin column of the right table
/// the new join edge
internal static JoinEdge CreateJoinEdge(AugmentedTableNode left, AugmentedTableNode right,
AugmentedJoinNode joinNode,
ColumnVar leftVar, ColumnVar rightVar)
{
List leftVars = new List();
List rightVars = new List();
leftVars.Add(leftVar);
rightVars.Add(rightVar);
OpType joinOpType = joinNode.Node.Op.OpType;
PlanCompiler.Assert((joinOpType == OpType.LeftOuterJoin || joinOpType == OpType.InnerJoin),
"Unexpected join type for join edge: " + joinOpType);
JoinKind joinKind = joinOpType == OpType.LeftOuterJoin ? JoinKind.LeftOuter : JoinKind.Inner;
JoinEdge joinEdge = new JoinEdge(left, right, joinNode, joinKind, leftVars, rightVars);
return joinEdge;
}
///
/// Creates a transitively generated join edge
///
/// the left table
/// the right table
/// the join kind
/// left equijoin vars
/// right equijoin vars
/// the join edge
internal static JoinEdge CreateTransitiveJoinEdge(AugmentedTableNode left, AugmentedTableNode right, JoinKind joinKind,
List leftVars, List rightVars)
{
JoinEdge joinEdge = new JoinEdge(left, right, null, joinKind, leftVars, rightVars);
return joinEdge;
}
///
/// Add a new "equi-join" condition to this edge
///
/// join node producing this condition
/// the left-side column
/// the right-side column
/// true, if this condition can be added
internal bool AddCondition(AugmentedJoinNode joinNode, ColumnVar leftVar, ColumnVar rightVar)
{
if (joinNode != m_joinNode)
{
return false;
}
m_leftVars.Add(leftVar);
m_rightVars.Add(rightVar);
return true;
}
#endregion
}
///
/// Represents a join graph. The uber-class for join elimination
///
internal class JoinGraph
{
#region private state
private Command m_command;
private AugmentedJoinNode m_root;
private List m_vertexes;
private List m_tableVertexes;
private Dictionary m_tableVertexMap;
private VarMap m_varMap;
private Dictionary m_varToDefiningNodeMap; //Includes all replacing vars and referenced vars from replacing tables
private Dictionary m_processedNodes;
private bool m_modifiedGraph;
private ConstraintManager m_constraintManager;
private VarRefManager m_varRefManager;
#endregion
#region constructors
///
/// The basic constructor. Builds up the annotated node tree, and the set of
/// join edges
///
/// Current IQT command
/// current constraint manager
/// the var ref manager for the tree
/// current join node
internal JoinGraph(Command command, ConstraintManager constraintManager, VarRefManager varRefManager, Node joinNode)
{
m_command = command;
m_constraintManager = constraintManager;
m_varRefManager = varRefManager;
m_vertexes = new List();
m_tableVertexes = new List();
m_tableVertexMap = new Dictionary();
m_varMap = new VarMap();
m_varToDefiningNodeMap = new Dictionary();
m_processedNodes = new Dictionary();
// Build the augmented node tree
m_root = BuildAugmentedNodeTree(joinNode) as AugmentedJoinNode;
PlanCompiler.Assert(m_root != null, "The root isn't a join?");
// Build the join edges
BuildJoinEdges(m_root, m_root.Id);
}
#endregion
#region public methods
///
/// Perform all kinds of join elimination. The output is the transformed join tree.
/// The varMap output is a dictionary that maintains var renames - this will be used
/// by the consumer of this module to fix up references to columns of tables
/// that have been eliminated
///
/// The processedNodes dictionary is simply a set of all nodes that have been processed
/// in this module - and need no further "join graph" processing
///
/// remapped vars
/// list of nodes that need no further processing
internal Node DoJoinElimination(out VarMap varMap,
out Dictionary processedNodes)
{
// Generate transitive edges
GenerateTransitiveEdges();
// Do real join elimination
EliminateSelfJoins();
EliminateParentChildJoins();
// Build the result tree
Node result = BuildNodeTree();
// Get other output properties
varMap = m_varMap;
processedNodes = m_processedNodes;
return result;
}
#endregion
#region private methods
#region Building the annotated node tree
//
// The goal of this submodule is to build up an annotated node tree for a
// node tree. As described earlier, we attempt to represent all nodes by
// one of the following classes - AugmentedTableNode (for ScanTableOp),
// AugmentedJoinNode (for all joins), and AugmentedNode for anything else.
// We use this information to help enable later stages of this module
//
// We employ a "greedy" strategy to handle as much of the node tree as possible.
// We follow all children of joins - and stop when we see a non-join, non-scan node
//
///
/// Get the subset of vars that are Columns
///
/// a varVec
/// a subsetted VarVec that only contains the columnVars from the input vec
private VarVec GetColumnVars(VarVec varVec)
{
VarVec columnVars = m_command.CreateVarVec();
foreach (Var v in varVec)
{
if (v.VarType == VarType.Column)
{
columnVars.Set(v);
}
}
return columnVars;
}
///
/// Generate a list of column Vars from the input vec
///
/// the list of vars to fill in
/// the var set
private static void GetColumnVars(List columnVars, IEnumerable vec)
{
foreach (Var v in vec)
{
PlanCompiler.Assert(v.VarType == VarType.Column, "Expected a columnVar. Found " + v.VarType);
columnVars.Add((ColumnVar)v);
}
}
///
/// Split up the join predicate into equijoin columns and other predicates.
///
/// For example, if I have a predicate of the form T1.C1 = T2.D1 and T1.C2 > T2.D2
/// we would generate
/// LeftVars = T1.C1
/// RightVars = T2.C1
/// OtherPredicate = T1.C2 > T2.D2
///
/// Special Cases:
/// For fullouter joins, we don't do any splitting - the "OtherPredicate" captures the
/// entire join condition.
///
/// the current join node
/// equijoin columns of the left side
/// equijoin columns of the right side
/// any other predicates
private void SplitPredicate(Node joinNode,
out List leftVars, out List rightVars,
out Node otherPredicateNode)
{
leftVars = new List();
rightVars = new List();
otherPredicateNode = joinNode.Child2;
//
// If this is a full-outer join, then don't do any splitting
//
if (joinNode.Op.OpType == OpType.FullOuterJoin)
{
return;
}
Predicate predicate = new Predicate(m_command, joinNode.Child2);
//
// Split the predicate
//
ExtendedNodeInfo leftInputNodeInfo = m_command.GetExtendedNodeInfo(joinNode.Child0);
ExtendedNodeInfo rightInputNodeInfo = m_command.GetExtendedNodeInfo(joinNode.Child1);
VarVec leftDefinitions = GetColumnVars(leftInputNodeInfo.Definitions);
VarVec rightDefinitions = GetColumnVars(rightInputNodeInfo.Definitions);
Predicate otherPredicate;
List tempLeftVars;
List tempRightVars;
predicate.GetEquiJoinPredicates(leftDefinitions, rightDefinitions, out tempLeftVars, out tempRightVars, out otherPredicate);
// Get the non-equijoin conditions
otherPredicateNode = otherPredicate.BuildAndTree();
GetColumnVars(leftVars, tempLeftVars);
GetColumnVars(rightVars, tempRightVars);
}
///
/// Build up the annotated node tree for the input subtree.
/// If the current node is
/// a ScanTableOp - we build an AugmentedTableNode
/// a join (Inner, LOJ, FOJ, CrossJoin) - we build an AugmentedJoinNode,
/// after first building annotated node trees for the inputs.
/// anything else - we build an AugmentedNode
///
/// We also mark the node as "processed" - so that the caller will not need
/// to build join graphs for this again
///
/// input node tree
/// the annotated node tree
private AugmentedNode BuildAugmentedNodeTree(Node node)
{
AugmentedNode augmentedNode;
switch (node.Op.OpType)
{
case OpType.ScanTable:
m_processedNodes[node] = node;
ScanTableOp scanTableOp = (ScanTableOp)node.Op;
augmentedNode = new AugmentedTableNode(m_vertexes.Count, node);
m_tableVertexMap[scanTableOp.Table] = (AugmentedTableNode)augmentedNode;
break;
case OpType.InnerJoin:
case OpType.LeftOuterJoin:
case OpType.FullOuterJoin:
m_processedNodes[node] = node;
AugmentedNode left = BuildAugmentedNodeTree(node.Child0);
AugmentedNode right = BuildAugmentedNodeTree(node.Child1);
List leftVars;
List rightVars;
Node otherPredicate;
SplitPredicate(node, out leftVars, out rightVars, out otherPredicate);
m_varRefManager.AddChildren(node);
augmentedNode = new AugmentedJoinNode(m_vertexes.Count, node, left, right, leftVars, rightVars, otherPredicate);
break;
case OpType.CrossJoin:
m_processedNodes[node] = node;
List children = new List();
foreach (Node chi in node.Children)
{
children.Add(BuildAugmentedNodeTree(chi));
}
augmentedNode = new AugmentedJoinNode(m_vertexes.Count, node, children);
m_varRefManager.AddChildren(node);
break;
default:
augmentedNode = new AugmentedNode(m_vertexes.Count, node);
break;
}
m_vertexes.Add(augmentedNode);
return augmentedNode;
}
#endregion
#region Building JoinEdges
//
// The goal of this module is to take the annotated node tree, and build up a
// a set of JoinEdges - this is arguably, the guts of the joingraph.
//
// Each join edge represents a directed, equijoin (inner, or leftouter) between
// two tables.
//
// We impose various constraints on the input node tree
//
///
/// Add a new join edge if possible.
///
/// - Check to see whether the input columns are columns of a table that we're tracking.
/// - Make sure that both the tables are "visible" to the current join node
/// - If there is already a link between the two tables, make sure that the link's
/// join kind is compatible with what we have
///
/// current join Node
/// left-side column
/// right-side column
///
private bool AddJoinEdge(AugmentedJoinNode joinNode, ColumnVar leftVar, ColumnVar rightVar)
{
AugmentedTableNode leftTableNode;
AugmentedTableNode rightTableNode;
// Are these tables even visible to me?
if (!m_tableVertexMap.TryGetValue(leftVar.Table, out leftTableNode))
{
return false;
}
if (!m_tableVertexMap.TryGetValue(rightVar.Table, out rightTableNode))
{
return false;
}
//
// If the tables participating in the join are not visible at this node,
// then simply return. We will not add the join edge
//
if (leftTableNode.LastVisibleId < joinNode.Id ||
rightTableNode.LastVisibleId < joinNode.Id)
{
return false;
}
//
// Check to see if there is already an "edge" between the 2 tables.
// If there is, then simply add a predicate to that edge. Otherwise, create
// an edge
//
foreach (JoinEdge joinEdge in leftTableNode.JoinEdges)
{
if (joinEdge.Right.Table.Equals(rightVar.Table))
{
// Try and add this new condition to the existing edge
return joinEdge.AddCondition(joinNode, leftVar, rightVar);
}
}
// Create a new join edge
JoinEdge newJoinEdge = JoinEdge.CreateJoinEdge(leftTableNode, rightTableNode, joinNode, leftVar, rightVar);
leftTableNode.JoinEdges.Add(newJoinEdge);
return true;
}
///
/// Check to see if all columns in the input varList are from the same table
/// Degenerate case: if the list is empty, we still return true
///
/// list of columns
/// true, if every column is from the same table
private static bool SingleTableVars(IEnumerable varList)
{
Table table = null;
foreach (ColumnVar v in varList)
{
if (table == null)
{
table = v.Table;
}
else if (v.Table != table)
{
return false;
}
}
return true;
}
///
/// Build a set of JoinEdges for this join.
/// For cross joins, we simply invoke this function recursively on the children, and return
///
/// For other joins,
/// - We first compute the "visibility" for the left and right branches
/// - For full outer joins, the "visibility" is the current join node's id. (ie)
/// the tables below are not to be considered as candidates for JoinEdges anywhere
/// above this FOJ node
/// - For left outer joins, the "visibility" of the left child is the input "maxVisibility"
/// parameter. For the right child, the "visibility" is the current join node's id
/// - For inner joins, the visibility for both children is the "maxVisibility" parameter
/// - We then check to see if the join condition is "ok". If the current join node
/// is a full-outer join, OR if the joinNode has an OtherPredicate (ie) stuff
/// other than equijoin column conditions, then we don't build any joinedges.
/// - Otherwise, we build join edges for each equijoin column
///
///
/// current join node
/// the highest node where any of the tables below is visible
private void BuildJoinEdges(AugmentedJoinNode joinNode, int maxVisibility)
{
OpType opType = joinNode.Node.Op.OpType;
//
// Simply visit the children for cross-joins
//
if (opType == OpType.CrossJoin)
{
foreach (AugmentedNode chi in joinNode.Children)
{
BuildJoinEdges(chi, maxVisibility);
}
return;
}
//
// If the current node is a leftouterjoin, or a full outer join, then
// none of the tables below should be visible anymore
//
int leftMaxVisibility;
int rightMaxVisibility;
if (opType == OpType.FullOuterJoin)
{
leftMaxVisibility = joinNode.Id;
rightMaxVisibility = joinNode.Id;
}
else if (opType == OpType.LeftOuterJoin)
{
leftMaxVisibility = maxVisibility;
rightMaxVisibility = joinNode.Id;
}
else
{
leftMaxVisibility = maxVisibility;
rightMaxVisibility = maxVisibility;
}
BuildJoinEdges(joinNode.Children[0], leftMaxVisibility);
BuildJoinEdges(joinNode.Children[1], rightMaxVisibility);
// Now handle the predicate
// Special cases. Nothing further if there exists anything other than
// a set of equi-join predicates
if (joinNode.Node.Op.OpType == OpType.FullOuterJoin ||
joinNode.OtherPredicate != null ||
joinNode.LeftVars.Count == 0)
{
return;
}
//
// If we have a left-outer join, and the join predicate involves more than one table on the
// right side, then quit
//
if ((opType == OpType.LeftOuterJoin) &&
(!SingleTableVars(joinNode.RightVars) || !SingleTableVars(joinNode.LeftVars)))
{
return;
}
JoinKind joinKind = (opType == OpType.LeftOuterJoin) ? JoinKind.LeftOuter : JoinKind.Inner;
for (int i = 0; i < joinNode.LeftVars.Count; i++)
{
// Add a join edge.
if (AddJoinEdge(joinNode, joinNode.LeftVars[i], joinNode.RightVars[i]))
{
// If we have an inner join, then add a "reverse" edge, but only
// if the previous AddEdge was successful
if (joinKind == JoinKind.Inner)
{
AddJoinEdge(joinNode, joinNode.RightVars[i], joinNode.LeftVars[i]);
}
}
}
}
///
/// Builds up the list of join edges. If the current node is
/// a ScanTable - we simply set the "LastVisibleId" property to the maxVisibility
/// parameter
/// a join - we invoke the BuildJoinEdges() function on the join node
/// anything else - do nothing
///
///
/// highest node that this node is visible at
private void BuildJoinEdges(AugmentedNode node, int maxVisibility)
{
switch (node.Node.Op.OpType)
{
case OpType.FullOuterJoin:
case OpType.LeftOuterJoin:
case OpType.InnerJoin:
case OpType.CrossJoin:
BuildJoinEdges(node as AugmentedJoinNode, maxVisibility);
// Now visit the predicate
break;
case OpType.ScanTable:
AugmentedTableNode tableNode = (AugmentedTableNode)node;
tableNode.LastVisibleId = maxVisibility;
break;
default:
break;
}
return;
}
#endregion
#region Transitive Edge generation
//
// The goal of this module is to generate transitive join edges.
// In general, if A is joined to B, and B is joined to C, then A can be joined to
// C as well.
// We apply the rules below to determine if we can indeed generate transitive
// join edges
// Assume that J1 = (A, B), and J2=(B,C)
// - J1.Kind must be the same as J2.Kind (both must be Inner, or both must be LeftOuterJoins)
// - If J1 is a left-outer join, then A,B and C must all be instances of the same table
// - The same columns of B must participate in the joins with A and C
// If all of these conditions are satisfied, we generate a new edge between A and C
// If we're dealing with an inner join, we also generate a C-A edge
//
// Note: We never produce any duplicate edges (ie) if an edge already exists between
// A and C in the example above, we don't try to generate a new edge, or modify the existing
// edge
//
///
/// If edge1 represents (T1, T2), and edge2 represents (T2, T3), try and
/// create a (T1,T3) edge.
///
/// If an edge already exists between these tables, then don't add a new edge
///
///
///
private bool GenerateTransitiveEdge(JoinEdge edge1, JoinEdge edge2)
{
PlanCompiler.Assert(edge1.Right == edge2.Left, "need a common table for transitive predicate generation");
// Ignore the "mirror" image.
if (edge2.Right == edge1.Left)
{
return false;
}
// Check to see if the joins are of the same type. Allow left-outer-joins
// only for self-joins
if (edge1.JoinKind != edge2.JoinKind)
{
return false;
}
if (edge1.JoinKind == JoinKind.LeftOuter &&
(edge1.Left != edge1.Right || edge2.Left != edge2.Right))
{
return false;
}
// Check to see if the joins are on the same columns
if (edge1.RightVars.Count != edge2.LeftVars.Count)
{
return false;
}
// check to see whether there already exists an edge for the combination
// of these tables
foreach (JoinEdge edge3 in edge1.Left.JoinEdges)
{
if (edge3.Right == edge2.Right)
{
return false;
}
}
VarVec vec1 = m_command.CreateVarVec();
foreach (Var v in edge1.RightVars)
{
vec1.Set(v);
}
foreach (Var v in edge2.LeftVars)
{
if (!vec1.IsSet(v))
{
return false;
}
}
// Ok, so we've finally identified an edge that looks to be transitive
Dictionary varMap1 = new Dictionary();
for (int i = 0; i < edge1.LeftVars.Count; i++)
{
varMap1[edge1.RightVars[i]] = edge1.LeftVars[i];
}
List leftVars = new List();
List rightVars = new List(edge2.RightVars);
for (int i = 0; i < edge1.LeftVars.Count; i++)
{
ColumnVar newLeftVar = varMap1[edge2.LeftVars[i]];
leftVars.Add(newLeftVar);
}
// Ok, we're now ready to finally create a new edge
JoinEdge newEdge = JoinEdge.CreateTransitiveJoinEdge(edge1.Left, edge2.Right, edge1.JoinKind,
leftVars, rightVars);
edge1.Left.JoinEdges.Add(newEdge);
if (edge1.JoinKind == JoinKind.Inner)
{
JoinEdge reverseEdge = JoinEdge.CreateTransitiveJoinEdge(edge2.Right, edge1.Left, edge1.JoinKind,
rightVars, leftVars);
edge2.Right.JoinEdges.Add(reverseEdge);
}
return true;
}
///
/// Generate a set of transitive edges
///
private void GenerateTransitiveEdges()
{
foreach (AugmentedNode augmentedNode in m_vertexes)
{
AugmentedTableNode tableNode = augmentedNode as AugmentedTableNode;
if (tableNode == null)
{
continue;
}
//
// The reason we use absolute indexing rather than 'foreach'ing is because
// the inner calls may add new entries to the collections, and cause the
// enumeration to throw
//
int i = 0;
while (i < tableNode.JoinEdges.Count)
{
JoinEdge e1 = tableNode.JoinEdges[i];
int j = 0;
AugmentedTableNode rightTable = e1.Right;
while (j < rightTable.JoinEdges.Count)
{
JoinEdge e2 = rightTable.JoinEdges[j];
GenerateTransitiveEdge(e1, e2);
j++;
}
i++;
}
}
}
#endregion
#region Join Elimination Helpers
//
// Utility routines used both by selfjoin elimination and parent-child join
// elimination
//
///
/// Checks whether a given table can be eliminated to be replaced by the given replacingTable
/// with regards to possible participation in the driving (left) subtree of Left Outer Joins.
///
/// In order for elimination to happen, one of the two tables has to logically move,
/// either the replacement table to the original table's location, or the table to the
/// replacing table's location.
///
/// For the table that would have to move, it checks whether such move would be valid
/// with regards to its participation as driver in Left Outer Joins ()
///
///
///
///
private static bool CanBeEliminated(AugmentedTableNode table, AugmentedTableNode replacingTable)
{
//The table with lower id, would have to be logically located at the other table's location
//Check whether it can be moved there
if (replacingTable.Id < table.NewLocationId)
{
return CanBeMoved(table, replacingTable);
}
else
{
return CanBeMoved(replacingTable, table);
}
}
///
/// Determines whether the given table can be moved to the replacing table's location
/// with regards to participation in the driving (left) subtree of Left Outer Joins.
/// If the table to be moved is part of the driving (left) subtree of a Left Outer Join
/// and the replacing table is not part of that subtree then the table cannot be moved,
/// otherwise it can.
///
///
///
///
private static bool CanBeMoved(AugmentedTableNode table, AugmentedTableNode replacingTable)
{
AugmentedNode leastCommonAncesstor = GetLeastCommonAncestor(table, replacingTable);
AugmentedNode currentNode = table;
while (currentNode.Parent != null && currentNode != leastCommonAncesstor)
{
//If the current node is a left child of an left outer join return
if (currentNode.Parent.Node.Op.OpType == OpType.LeftOuterJoin &&
currentNode.Parent.Children[0] == currentNode)
{
return false;
}
currentNode = currentNode.Parent;
}
return true;
}
///
/// Gets the least common ancestor for two given nodes in the tree
///
///
///
///
private static AugmentedNode GetLeastCommonAncestor(AugmentedNode node1, AugmentedNode node2)
{
if (node1.Id == node2.Id)
{
return node1;
}
AugmentedNode currentParent;
AugmentedNode rigthNode;
if (node1.Id < node2.Id)
{
currentParent = node1;
rigthNode = node2;
}
else
{
currentParent = node2;
rigthNode = node1;
}
while (currentParent.Id < rigthNode.Id)
{
currentParent = currentParent.Parent;
}
return currentParent;
}
///
/// This function marks a table as eliminated. The replacement varmap
/// is updated with columns of the table being mapped to the corresponding columns
/// of the replacement table
///
/// table being replaced
/// the table being used in its place
/// list of vars to replace
/// list of vars to replace with
/// Var or one of its subtypes
private void MarkTableAsEliminated(AugmentedTableNode tableNode, AugmentedTableNode replacementNode,
List tableVars, List replacementVars) where T : Var
{
PlanCompiler.Assert(tableVars != null && replacementVars != null, "null vars");
PlanCompiler.Assert(tableVars.Count == replacementVars.Count, "var count mismatch");
PlanCompiler.Assert(tableVars.Count > 0, "no vars in the table ?");
m_modifiedGraph = true;
// Set up the replacement table (if necessary)
if (tableNode.Id < replacementNode.NewLocationId)
{
tableNode.ReplacementTable = replacementNode;
replacementNode.NewLocationId = tableNode.Id;
}
else
{
tableNode.ReplacementTable = null;
}
// Add mappings for each var of the table
for (int i = 0; i < tableVars.Count; i++)
{
//
// Bug 446708: Make sure that the "replacement" column is
// referenced, if the the current column is referenced
//
if (tableNode.Table.ReferencedColumns.IsSet(tableVars[i]))
{
m_varMap[tableVars[i]] = replacementVars[i];
replacementNode.Table.ReferencedColumns.Set(replacementVars[i]);
}
}
//
// It should be possible to retrieve the location of each replacing var
// It should also be possible to retrieve the location of each referenced var
// defined on a replacing table, because replacing tables may get moved.
//
foreach (Var var in replacementNode.Table.ReferencedColumns)
{
m_varToDefiningNodeMap[var] = replacementNode;
}
}
#endregion
#region SelfJoin Elimination
//
// The goal of this submodule is to eliminate selfjoins. We consider two kinds
// of selfjoins here - explicit, and implicit.
//
// An explicit selfjoin J is a join between tables T1 and T2, where T1 and T2
// are instances of the same table. Furthemore, T1 and T2 must be joined on their
// key columns (and no more).
//
// An implicit self-join is of the form (X, A1, A2, ...) where A1, A2 etc.
// are all instances of the same table, and X is joined to A1, A2 etc. on the same
// columns. We also call this a "star" selfjoin, since "X" is logically the
// being star-joined to all the other tables here
//
///
/// This function marks a table (part of a selfjoin) as eliminated. The replacement varmap
/// is updated with columns of the table being mapped to the corresponding columns
/// of the replacement table
///
/// table being replaced
/// the table being used in its place
private void EliminateSelfJoinedTable(AugmentedTableNode tableNode, AugmentedTableNode replacementNode)
{
MarkTableAsEliminated(tableNode, replacementNode, tableNode.Table.Columns, replacementNode.Table.Columns);
}
///
/// This function is a helper function for star selfjoin elimination. All the
/// "right" tables of the join edges in the input list are instances of the same table.
///
/// Precondition: Each joinedge is of the form (X, Ai),
/// where X is the star-joined table, and A1...An are all instances of the same
/// table A
///
/// This function checks to see if all the tables are in fact joined on the same columns,
/// all the edges are of the same kind, and all the key columns of the table are used
///
/// If all the conditions are satisfied, we then identify the table with the
/// smallest "Id", and choose that to replace all the other tables
///
///
/// list of join edges
private void EliminateStarSelfJoin(List joinEdges)
{
JoinEdge firstJoinEdge = joinEdges[0];
//
// Now make sure that all key columns of the right table are used
//
VarVec keyVars = m_command.CreateVarVec(firstJoinEdge.Right.Table.Keys);
foreach (Var v in firstJoinEdge.RightVars)
{
// Make sure that no other column is referenced in case of an outer join
if (firstJoinEdge.JoinKind == JoinKind.LeftOuter && !keyVars.IsSet(v))
{
return;
}
keyVars.Clear(v);
}
if (!keyVars.IsEmpty)
{
return;
}
//
// Now make sure that all the joins are on the same columns
//
for (int i = 1; i < joinEdges.Count; i++)
{
JoinEdge joinEdge = joinEdges[i];
// Not compatible, if we're not joining on the same number of columns,
// or if the joinkind does not match
if (joinEdge.LeftVars.Count != firstJoinEdge.LeftVars.Count ||
joinEdge.JoinKind != firstJoinEdge.JoinKind)
{
return;
}
// Now make sure that we're joining on the same columns
for (int j = 0; j < joinEdge.LeftVars.Count; j++)
{
// Check for reference equality on the left-table Vars. Check for
// name equality on the right table vars
if (!joinEdge.LeftVars[j].Equals(firstJoinEdge.LeftVars[j]) ||
!joinEdge.RightVars[j].ColumnMetadata.Name.Equals(firstJoinEdge.RightVars[j].ColumnMetadata.Name))
{
return;
}
}
}
//
// Ok. We've now found that the tables can in fact be eliminated. Identify the
// table with the smallest id, and use that as the candidate
//
JoinEdge smallestEdge = firstJoinEdge;
foreach (JoinEdge joinEdge in joinEdges)
{
if (smallestEdge.Right.Id > joinEdge.Right.Id)
{
smallestEdge = joinEdge;
}
}
//
// Now walk through all the edges, and mark all the tables as eliminated
//
foreach (JoinEdge joinEdge in joinEdges)
{
if (joinEdge == smallestEdge)
{
continue;
}
if (CanBeEliminated(joinEdge.Right, smallestEdge.Right))
{
EliminateSelfJoinedTable(joinEdge.Right, smallestEdge.Right);
}
}
// Done
}
///
/// Eliminates any star self joins. This function looks at all the tables that
/// this table is joined to, groups the tables based on the table name (metadata),
/// and then tries selfjoin elimination on each group (see function above)
///
/// the star-joined table?
private void EliminateStarSelfJoins(AugmentedTableNode tableNode)
{
// First build up a number of equivalence classes. Each equivalence class
// contains instances of the same table
Dictionary> groupedEdges = new Dictionary>();
foreach (JoinEdge joinEdge in tableNode.JoinEdges)
{
// Ignore useless edges
if (joinEdge.IsEliminated)
{
continue;
}
List edges;
if (!groupedEdges.TryGetValue(joinEdge.Right.Table.TableMetadata.Extent, out edges))
{
edges = new List();
groupedEdges[joinEdge.Right.Table.TableMetadata.Extent] = edges;
}
edges.Add(joinEdge);
}
// Now walk through each equivalence class, and identify if we can eliminate some of
// the self-joins
foreach (KeyValuePair> kv in groupedEdges)
{
// If there's only one table in the class, skip this and move on
if (kv.Value.Count <= 1)
{
continue;
}
// Try and do the real dirty work
EliminateStarSelfJoin(kv.Value);
}
}
///
/// Eliminate a self-join edge.
///
/// the join edge
/// tur, if we did eliminate the self-join
private bool EliminateSelfJoin(JoinEdge joinEdge)
{
// Nothing further to do, if the right-side has already been eliminated
if (joinEdge.IsEliminated)
{
return false;
}
// Am I a self-join?
if (!joinEdge.Left.Table.TableMetadata.Extent.Equals(joinEdge.Right.Table.TableMetadata.Extent))
{
return false;
}
// Check to see that only the corresponding columns are being compared
for (int i = 0; i < joinEdge.LeftVars.Count; i++)
{
if (!joinEdge.LeftVars[i].ColumnMetadata.Name.Equals(joinEdge.RightVars[i].ColumnMetadata.Name))
{
return false;
}
}
//
// Now make sure that the join edge includes every single key column
// For left-outer joins, we must have no columns other than the key columns
//
VarVec keyVars = m_command.CreateVarVec(joinEdge.Left.Table.Keys);
foreach (Var v in joinEdge.LeftVars)
{
if (joinEdge.JoinKind == JoinKind.LeftOuter && !keyVars.IsSet(v))
{
return false;
}
keyVars.Clear(v);
}
// Are some keys left over?
if (!keyVars.IsEmpty)
{
return false;
}
if (!CanBeEliminated(joinEdge.Right, joinEdge.Left))
{
return false;
}
// Mark the right-table as eliminated
// Get the parent node for the right node, and replace the parent by the corresponding
// left node
EliminateSelfJoinedTable(joinEdge.Right, joinEdge.Left);
return true;
}
///
/// Eliminate self-joins for this table (if any)
///
/// current table
private void EliminateSelfJoins(AugmentedTableNode tableNode)
{
// Is this node already eliminated?
if (tableNode.IsEliminated)
{
return;
}
// First try and eliminate all explicit self-joins
foreach (JoinEdge joinEdge in tableNode.JoinEdges)
{
EliminateSelfJoin(joinEdge);
}
}
///
/// Eliminate all selfjoins
///
private void EliminateSelfJoins()
{
foreach (AugmentedNode augmentedNode in m_vertexes)
{
AugmentedTableNode tableNode = augmentedNode as AugmentedTableNode;
if (tableNode != null)
{
EliminateSelfJoins(tableNode);
EliminateStarSelfJoins(tableNode);
}
}
}
#endregion
#region Parent-Child join elimination
//
// The goal of this submodule is to eliminate parent-child joins. We consider two kinds
// of parent-child joins here.
//
// The first category of joins involves a 1-1 or 1-n relationship between a parent
// and child table, where the tables are (inner) joined on the key columns (pk, fk), and no
// other columns of the parent table are referenced. In this case, the parent table
// can be eliminated, and the child table used in place. There are two special considerations
// here.
// First, the foreign key columns may be nullable - in this case, we need to prune
// out rows where these null values might occur (since they would have been pruned
// out by the join). In effect, we add a filter node above the table node, if there
// are any nullable foreign keys.
// The second case is where the parent table appears "lexically" before the child
// table in the query. In this case, the child table will need to "move" to the
// parent table's location - this is needed for scenarios where there may be other
// intervening tables where the parent table's key columns are referenced - and these
// cannot see the equivalent columns of the child table, unless the child table is
// moved to that location.
//
// The second category of joins involves a 1-1 relationship between the parent and
// child table, where the parent table is left outer joined to the child table
// on the key columns. If no other columns of the child table are referenced in the
// query, then the child table can be eliminated.
//
///
/// Eliminate the parent table
///
///
private void EliminateParentTable(JoinEdge joinEdge)
{
PlanCompiler.Assert(joinEdge.JoinKind == JoinKind.Inner, "Expected inner join");
MarkTableAsEliminated(joinEdge.Left, joinEdge.Right, joinEdge.LeftVars, joinEdge.RightVars);
//
// Find the list of non-nullable columns
//
if (joinEdge.Right.NullableColumns == null)
{
joinEdge.Right.NullableColumns = m_command.CreateVarVec();
}
foreach (ColumnVar v in joinEdge.RightVars)
{
//
// if the column is known to be non-nullable, then we don't need to
// add a filter condition to prune out nulls later.
//
if (v.ColumnMetadata.IsNullable)
{
joinEdge.Right.NullableColumns.Set(v);
}
}
}
///
/// Eliminate the child table
///
///
private void EliminateChildTable(JoinEdge joinEdge)
{
PlanCompiler.Assert(joinEdge.JoinKind == JoinKind.LeftOuter, "Expected left-outer-join");
PlanCompiler.Assert(joinEdge.Left.Id < joinEdge.Right.Id,
"(left-id, right-id) = (" + joinEdge.Left.Id + "," + joinEdge.Right.Id + ")");
MarkTableAsEliminated(joinEdge.Right, joinEdge.Left, joinEdge.RightVars, joinEdge.LeftVars);
}
///
/// Do we reference any nonkey columns from this table
///
/// the table instance
/// true, if there are any nonkey references
private static bool HasNonKeyReferences(Table table)
{
return !table.Keys.Subsumes(table.ReferencedColumns);
}
///
/// Are any of the key columns from the child (right) table of the given join edge referenced
/// elsewhere (outside the join condition)
///
///
///
private bool ChildTableHasKeyReferences(JoinEdge joinEdge)
{
//For transitive edges we don't have a joinNode.
if (joinEdge.JoinNode == null)
{
// Note: We have not been able to hit this yet. If we find many cases in which we hit this,
// we can see if we can do more tracking. This way we may be missing cases that could be optimized.
return true;
}
return m_varRefManager.HasKeyReferences(joinEdge.Right.Table.Keys, joinEdge.Right.Node, joinEdge.JoinNode.Node);
}
///
/// Eliminate a parent-child join, given a fk constraint
///
/// the current join edge
/// the referential integrity constraint
///
private bool TryEliminateParentChildJoin(JoinEdge joinEdge, ForeignKeyConstraint fkConstraint)
{
//
// Consider join elimination for left-outer-joins only if we have a 1 - 1 or 1 - 0..1 relationship
//
if (joinEdge.JoinKind == JoinKind.LeftOuter && fkConstraint.ChildMultiplicity == md.RelationshipMultiplicity.Many)
{
return false;
}
//
// Make sure that every one of the parent key properties is referenced
//
foreach (string keyProp in fkConstraint.ParentKeys)
{
bool foundKey = false;
foreach (ColumnVar cv in joinEdge.LeftVars)
{
if (cv.ColumnMetadata.Name.Equals(keyProp))
{
foundKey = true;
break;
}
}
if (!foundKey)
{
return false;
}
}
//
// Make sure that every one of the child key properties is referenced
// and furthermore equi-joined to the corresponding parent key properties
//
foreach (string keyProp in fkConstraint.ChildKeys)
{
bool foundKey = false;
for (int pos = 0; pos < joinEdge.LeftVars.Count; pos++)
{
ColumnVar rightVar = joinEdge.RightVars[pos];
if (rightVar.ColumnMetadata.Name.Equals(keyProp))
{
foundKey = true;
string parentPropertyName;
ColumnVar leftVar = joinEdge.LeftVars[pos];
if (!fkConstraint.GetParentProperty(rightVar.ColumnMetadata.Name, out parentPropertyName) ||
!parentPropertyName.Equals(leftVar.ColumnMetadata.Name))
{
return false;
}
break;
}
}
if (!foundKey)
{
return false;
}
}
//
// For inner joins, try and eliminate the parent table
//
if (joinEdge.JoinKind == JoinKind.Inner)
{
if (HasNonKeyReferences(joinEdge.Left.Table))
{
return false;
}
if (!CanBeEliminated(joinEdge.Right, joinEdge.Left))
{
return false;
}
// Mark the left-side table as "eliminated"
EliminateParentTable(joinEdge);
}
//
// For left outer joins, try and eliminate the child table
//
else if (joinEdge.JoinKind == JoinKind.LeftOuter)
{
if (HasNonKeyReferences(joinEdge.Right.Table) ||
// SQLBUDT #512375: For the 1 - 0..1 we also verify that the child's columns are not
// referenced outside the join condition
(fkConstraint.ChildMultiplicity == md.RelationshipMultiplicity.ZeroOrOne && ChildTableHasKeyReferences(joinEdge)))
{
return false;
}
if (!CanBeEliminated(joinEdge.Right, joinEdge.Left))
{
return false;
}
// Eliminate the child table
EliminateChildTable(joinEdge);
}
return true;
}
///
/// Eliminate the join if possible, for this edge
///
/// the current join edge
private void EliminateParentChildJoin(JoinEdge joinEdge)
{
List fkConstraints;
// Is there a foreign key constraint between these 2 tables?
if (!m_constraintManager.IsParentChildRelationship(joinEdge.Left.Table.TableMetadata.Extent, joinEdge.Right.Table.TableMetadata.Extent,
out fkConstraints))
{
return;
}
PlanCompiler.Assert(fkConstraints != null && fkConstraints.Count > 0, "invalid fk constraints?");
// Now walk through the list of foreign key constraints and attempt join
// elimination
foreach (ForeignKeyConstraint fkConstraint in fkConstraints)
{
if (TryEliminateParentChildJoin(joinEdge, fkConstraint))
{
return;
}
}
}
///
/// Eliminate parent child nodes that this node participates in
///
/// the "left" table in a join
private void EliminateParentChildJoins(AugmentedTableNode tableNode)
{
foreach (JoinEdge joinEdge in tableNode.JoinEdges)
{
EliminateParentChildJoin(joinEdge);
if (tableNode.IsEliminated)
{
return;
}
}
}
///
/// Eliminate all parent-child joins in the join graph
///
private void EliminateParentChildJoins()
{
foreach (AugmentedNode node in m_vertexes)
{
AugmentedTableNode tableNode = node as AugmentedTableNode;
if (tableNode != null && !tableNode.IsEliminated)
{
EliminateParentChildJoins(tableNode);
}
}
}
#endregion
#region Rebuilding the Node Tree
//
// The goal of this submodule is to rebuild the node tree from the annotated node tree,
// and getting rid of eliminated tables along the way
//
#region Main Rebuilding Methods
///
/// Return the result of join elimination
///
/// the transformed node tree
private Node BuildNodeTree()
{
// Has anything changed? If not, then simply return the original tree.
if (!m_modifiedGraph)
{
return m_root.Node;
}
// Generate transitive closure for all Vars in the varMap
VarMap newVarMap = new VarMap();
foreach (KeyValuePair kv in m_varMap)
{
Var newVar1 = kv.Value;
Var newVar2;
while (m_varMap.TryGetValue(newVar1, out newVar2))
{
PlanCompiler.Assert(newVar2 != null, "null var mapping?");
newVar1 = newVar2;
}
newVarMap[kv.Key] = newVar1;
}
m_varMap = newVarMap;
// Otherwise build the tree
Dictionary predicates;
Node newNode = RebuildNodeTree(m_root, out predicates);
PlanCompiler.Assert(newNode != null, "Resulting node tree is null");
PlanCompiler.Assert(predicates == null || predicates.Count == 0, "Leaking predicates?");
return newNode;
}
///
/// Build a filter node (if necessary) to prune out null values for the specified
/// columns
///
///
///
///
private Node BuildFilterForNullableColumns(Node inputNode, VarVec nonNullableColumns)
{
if (nonNullableColumns == null)
{
return inputNode;
}
VarVec remappedVarVec = nonNullableColumns.Remap(m_varMap);
if (remappedVarVec.IsEmpty)
{
return inputNode;
}
Node predNode = null;
foreach (Var v in remappedVarVec)
{
Node varRefNode = m_command.CreateNode(m_command.CreateVarRefOp(v));
Node isNotNullNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.IsNull), varRefNode);
isNotNullNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.Not), isNotNullNode);
if (predNode == null)
{
predNode = isNotNullNode;
}
else
{
predNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
predNode, isNotNullNode);
}
}
PlanCompiler.Assert(predNode != null, "Null predicate?");
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), inputNode, predNode);
return filterNode;
}
///
/// Adds a filter node (if necessary) on top of the input node.
/// Returns the input node, if the filter predicate is null - otherwise, adds a
/// a new filter node above the input
///
/// the input node
/// the filter predicate
///
private Node BuildFilterNode(Node inputNode, Node predicateNode)
{
if (predicateNode == null)
{
return inputNode;
}
else
{
return m_command.CreateNode(m_command.CreateFilterOp(), inputNode, predicateNode);
}
}
///
/// Rebuilds the predicate for a join node and caculates the minimum location id at which it can be specified.
/// The predicate is an AND of the equijoin conditions and the "otherPredicate".
///
/// We first remap all columns in the equijoin predicates - if a column pair
/// resolves to the same column, then we skip that pair.
///
/// The minimum location id at which a predicate can be specified is the minimum location id that is
/// still at or above the minimum location id of all participating vars. By default, it is the location id
/// of the input join node. However, because a table producing a participating var may be moved or
/// replaced by another table, the rebuilt predicate may need to be specified at higher location id.
///
/// the current join node
/// the minimum location id (AugumentedNode.Id) at which this predicate can be specified
/// the rebuilt predicate
private Node RebuildPredicate(AugmentedJoinNode joinNode, out int minLocationId)
{
//
// It is safe to initilaze the output location id to the location id of the joinNode. The nodes at lower
// location ids have already been processed, thus even if the least common ancestor of all participating
// vars is lower than the location id of the joinNode, the rebuilt predicate would not be propagated
// to nodes at lower location ids.
//
minLocationId = joinNode.Id;
//Get the minimum location Id at which the other predicate can be specified.
if (joinNode.OtherPredicate != null)
{
foreach (Var var in joinNode.OtherPredicate.GetNodeInfo(this.m_command).ExternalReferences)
{
Var newVar;
if (!m_varMap.TryGetValue(var, out newVar))
{
newVar = var;
}
minLocationId = GetLeastCommonAncestor(minLocationId, GetLocationId(newVar, minLocationId));
}
}
Node predicateNode = joinNode.OtherPredicate;
for (int i = 0; i < joinNode.LeftVars.Count; i++)
{
Var newLeftVar;
Var newRightVar;
if (!m_varMap.TryGetValue(joinNode.LeftVars[i], out newLeftVar))
{
newLeftVar = joinNode.LeftVars[i];
}
if (!m_varMap.TryGetValue(joinNode.RightVars[i], out newRightVar))
{
newRightVar = joinNode.RightVars[i];
}
if (newLeftVar.Equals(newRightVar))
{
continue;
}
minLocationId = GetLeastCommonAncestor(minLocationId, GetLocationId(newLeftVar, minLocationId));
minLocationId = GetLeastCommonAncestor(minLocationId, GetLocationId(newRightVar, minLocationId));
Node leftVarNode = m_command.CreateNode(m_command.CreateVarRefOp(newLeftVar));
Node rightVarNode = m_command.CreateNode(m_command.CreateVarRefOp(newRightVar));
Node equalsNode = m_command.CreateNode(m_command.CreateComparisonOp(OpType.EQ),
leftVarNode, rightVarNode);
if (predicateNode != null)
{
predicateNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
equalsNode, predicateNode);
}
else
{
predicateNode = equalsNode;
}
}
return predicateNode;
}
///
/// Rebuilds a crossjoin node tree. We visit each child of the cross join, and get
/// back a list of nodes. If the list of nodes has
/// 0 children - we return null
/// 1 child - we return the single child
/// otherwise - we build a new crossjoin op with all the children
///
/// the crossjoin node
/// new node tree
private Node RebuildNodeTreeForCrossJoins(AugmentedJoinNode joinNode)
{
List newChildren = new List();
foreach (AugmentedNode chi in joinNode.Children)
{
Dictionary predicates;
newChildren.Add(RebuildNodeTree(chi, out predicates));
PlanCompiler.Assert(predicates == null || predicates.Count == 0, "Leaking predicates");
}
if (newChildren.Count == 0)
{
return null;
}
else if (newChildren.Count == 1)
{
return newChildren[0];
}
else
{
Node newJoinNode = m_command.CreateNode(m_command.CreateCrossJoinOp(), newChildren);
m_processedNodes[newJoinNode] = newJoinNode;
return newJoinNode;
}
}
///
/// Rebuilds the node tree for a join.
/// For crossjoins, we delegate to the function above. For other cases, we first
/// invoke this function recursively on the left and the right inputs.
///
///
/// the annotated join node tree
/// A dictionary of output predicates that should be included in ancesstor joins
/// along with the minimum location id at which they can be specified
/// rebuilt tree
private Node RebuildNodeTree(AugmentedJoinNode joinNode, out Dictionary predicates)
{
//
// Handle the simple cases first - cross joins
//
if (joinNode.Node.Op.OpType == OpType.CrossJoin)
{
predicates = null;
return RebuildNodeTreeForCrossJoins(joinNode);
}
Dictionary leftPredicates;
Dictionary rightPredicates;
Node leftNode = RebuildNodeTree(joinNode.Children[0], out leftPredicates);
Node rightNode = RebuildNodeTree(joinNode.Children[1], out rightPredicates);
int localPredicateMinLocationId;
Node localPredicateNode;
// The special case first, when we may 'eat' the local predicate
if (leftNode != null && rightNode == null && joinNode.Node.Op.OpType == OpType.LeftOuterJoin)
{
// Ignore the local predicate
// Is this correct always? What kind of assertions can we make here?
localPredicateMinLocationId = joinNode.Id;
localPredicateNode = null;
}
else
{
localPredicateNode = RebuildPredicate(joinNode, out localPredicateMinLocationId);
}
localPredicateNode = CombinePredicateNodes(joinNode.Id, localPredicateNode, localPredicateMinLocationId, leftPredicates, rightPredicates, out predicates);
if (leftNode == null && rightNode == null)
{
if (localPredicateNode == null)
{
return null;
}
else
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
return BuildFilterNode(singleRowTableNode, localPredicateNode);
}
}
else if (leftNode == null)
{
return BuildFilterNode(rightNode, localPredicateNode);
}
else if (rightNode == null)
{
return BuildFilterNode(leftNode, localPredicateNode);
}
else
{
if (localPredicateNode == null)
{
localPredicateNode = m_command.CreateNode(m_command.CreateTrueOp());
}
Node newJoinNode = m_command.CreateNode(joinNode.Node.Op,
leftNode, rightNode, localPredicateNode);
m_processedNodes[newJoinNode] = newJoinNode;
return newJoinNode;
}
}
///
/// Rebuild the node tree for a TableNode.
///
/// - Keep following the ReplacementTable links until we get to a node that
/// is either null, or has a "false" value for the IsEliminated property
/// - If the result is null, then simply return null
/// - If the tableNode we ended up with has already been "placed" in the resulting
/// node tree, then return null again
/// - If the tableNode has a set of non-nullable columns, then build a filterNode
/// above the ScanTable node (pruning out null values); otherwise, simply return
/// the ScanTable node
///
/// the "augmented" tableNode
/// rebuilt node tree for this node
private Node RebuildNodeTree(AugmentedTableNode tableNode)
{
AugmentedTableNode replacementNode = tableNode;
//
// If this table has already been moved - nothing further to do.
//
if (tableNode.IsMoved)
{
return null;
}
//
// Identify the replacement table for this node
//
while (replacementNode.IsEliminated)
{
replacementNode = replacementNode.ReplacementTable;
if (replacementNode == null)
{
return null;
}
}
//
// Check to see if the replacement node has already been put
// in place in the node tree (possibly as part of eliminating some other join).
// In that case, we don't need to do anything further - simply return null
//
if (replacementNode.NewLocationId < tableNode.Id)
{
return null;
}
//
// ok: so we now have a replacement node that must be used in place
// of the current table. Check to see if the replacement node has any
// columns that would require nulls to be pruned out
//
Node filterNode = BuildFilterForNullableColumns(replacementNode.Node, replacementNode.NullableColumns);
return filterNode;
}
///
/// Rebuilds the node tree from the annotated node tree. This function is
/// simply a dispatcher
/// ScanTable - call RebuildNodeTree for ScanTable
/// Join - call RebuildNodeTree for joinOp
/// Anything else - return the underlying node
///
/// annotated node tree
/// the output predicate that should be included in the parent join
/// the rebuilt node tree
private Node RebuildNodeTree(AugmentedNode augmentedNode, out Dictionary predicates)
{
switch (augmentedNode.Node.Op.OpType)
{
case OpType.ScanTable:
predicates = null;
return RebuildNodeTree((AugmentedTableNode)augmentedNode);
case OpType.CrossJoin:
case OpType.LeftOuterJoin:
case OpType.InnerJoin:
case OpType.FullOuterJoin:
return RebuildNodeTree((AugmentedJoinNode)augmentedNode, out predicates);
default:
predicates = null;
return augmentedNode.Node;
}
}
#endregion
#region Helper Methods for Rebuilding the Node Tree
///
/// Helper method for RebuildNodeTree.
/// Given predicate nodes and the minimum location ids at which they can be specified, it creates:
/// 1. A single predicate AND-ing all input predicates with a minimum location id that is less or equal to the given targetNodeId.
/// 2. A dictionary of all other input predicates and their target minimum location ids.
///
/// The location id of the resulting predicate
/// A predicate
/// The location id for the localPredicateNode
/// A dictionary of predicates and the minimum location id at which they can be specified
/// A dictionary of predicates and the minimum location id at which they can be specified
/// An output dictionary of predicates and the minimum location id at which they can be specified
/// that includes all input predicates with minimum location id greater then targetNodeId
/// A single predicate "AND"-ing all input predicates with a minimum location id that is less or equal to the tiven targetNodeId.
private Node CombinePredicateNodes(int targetNodeId, Node localPredicateNode, int localPredicateMinLocationId, Dictionary leftPredicates, Dictionary rightPredicates, out Dictionary outPredicates)
{
Node result = null;
outPredicates = new Dictionary();
if (localPredicateNode != null)
{
result = ClassifyPredicate(targetNodeId, localPredicateNode, localPredicateMinLocationId, result, outPredicates);
}
if (leftPredicates != null)
{
foreach (KeyValuePair predicatePair in leftPredicates)
{
result = ClassifyPredicate(targetNodeId, predicatePair.Key, predicatePair.Value, result, outPredicates);
}
}
if (rightPredicates != null)
{
foreach (KeyValuePair predicatePair in rightPredicates)
{
result = ClassifyPredicate(targetNodeId, predicatePair.Key, predicatePair.Value, result, outPredicates);
}
}
return result;
}
///
/// Helper method for
/// If the predicateMinimuLocationId is less or equal to the target location id of the current result, it is AND-ed with the
/// current result, otherwise it is included in the list of predicates that need to be propagated up (outPredicates)
///
///
///
///
///
///
///
private Node ClassifyPredicate(int targetNodeId, Node predicateNode, int predicateMinLocationId, Node result, Dictionary outPredicates)
{
if (targetNodeId >= predicateMinLocationId)
{
result = CombinePredicates(result, predicateNode);
}
else
{
outPredicates.Add(predicateNode, predicateMinLocationId);
}
return result;
}
///
/// Combines two predicates into one by AND-ing them.
///
///
///
///
private Node CombinePredicates(Node node1, Node node2)
{
if (node1 == null)
{
return node2;
}
if (node2 == null)
{
return node1;
}
return m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
node1, node2);
}
///
/// Get the location id of the AugumentedTableNode at which the given var is defined.
/// If the var is not in th m_varToDefiningNodeMap, then it return the input defaultLocationId
///
///
///
///
private int GetLocationId(Var var, int defaultLocationId)
{
AugmentedTableNode node;
if (m_varToDefiningNodeMap.TryGetValue(var, out node))
{
if (node.IsMoved)
{
return node.NewLocationId;
}
return node.Id;
}
return defaultLocationId;
}
///
/// Gets the location id of least common ancestor for two nodes in the tree given their location ids
///
///
///
///
private int GetLeastCommonAncestor(int nodeId1, int nodeId2)
{
if (nodeId1 == nodeId2)
{
return nodeId1;
}
AugmentedNode currentNode = m_root;
AugmentedNode child1Parent = currentNode;
AugmentedNode child2Parent = currentNode;
while (child1Parent == child2Parent)
{
currentNode = child1Parent;
if (currentNode.Id == nodeId1 || currentNode.Id == nodeId2)
{
return currentNode.Id;
}
child1Parent = PickSubtree(nodeId1, currentNode);
child2Parent = PickSubtree(nodeId2, currentNode);
}
return currentNode.Id;
}
///
/// Helper method for
/// Given a root node pick its immediate child to which the node identifed with the given nodeId bellongs.
///
///
///
///
/// The immediate child of the given root that is root of the subree that
/// contains the node with the given nodeId.
///
private static AugmentedNode PickSubtree(int nodeId, AugmentedNode root)
{
AugmentedNode subree = root.Children[0];
int i = 1;
while ((subree.Id < nodeId) && (i < root.Children.Count))
{
subree = root.Children[i];
i++;
}
return subree;
}
#endregion
#endregion
#endregion
}
#endregion
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization;
using System.Data.Query.InternalTrees;
using md = System.Data.Metadata.Edm;
//
// The JoinGraph module is responsible for performing the following kinds of
// join elimination.
// This module deals with the following kinds of joins
// * Self-joins: The join can be eliminated, and either of the table instances can be
// used instead
// * Implied self-joins: Same as above
// * PK-FK joins: (More generally, UK-FK joins): Eliminate the join, and use just the FK table, if no
// column of the PK table is used (other than the join condition)
// * PK-PK joins: Eliminate the right side table, if we have a left-outer join
//
// This module is organized into the following phases.
// * Building an Augmented Tree: In this phase, the original node tree is annotated
// with additional information, and a new "augmented" tree is built up
// * Building up Join Edges: In this phase, the augmented tree is used to populate
// the join graph with equi-join edges
// * Generating transitive edges: Generate transitive join edges
// * Parent-Child (PK-FK) Join Elimination: We walk through the list of join edges, and
// eliminate any redundant tables in parent-child joins
// * Self-join Elimination: We walk through the list of join edges, and eliminate
// any redundant tables
// * Rebuilding the node tree: The augmented node tree is now converted back into
// a regular node tree.
//
namespace System.Data.Query.PlanCompiler
{
#region AugmentedNode
//
// This region describes a number of classes that are used to build an annotated
// (or augmented) node tree. There are 3 main classes defined here
// AugmentedNode - this is the base class for all annotations. This class
// wraps a Node, an id for the node (where the "id" is assigned in DFS order),
// and a list of children. All Nodes that are neither joins, nor scanTables
// are represented by this class
// AugmentedTableNode - the augmentedTableNode is a subclass of AugmentedNode,
// and represents a ScanTable node. In addition to the information above, this
// class keeps track of all join edges that this node participates in,
// whether this table has been eliminated, and finally, how high in the tree
// this node is visible
// AugmentedJoinNode - represents all joins (cross-joins, leftouter, fullouter
// and innerjoins). This class represents a number of column equijoin conditions
// via the LeftVars and RightVars properties, and also keeps track of additional
// (non-equijoin column) join predicates
//
///
/// Additional information for a node.
///
internal class AugmentedNode
{
#region private state
private int m_id;
private Node m_node;
protected AugmentedNode m_parent;
private List m_children;
#endregion
#region constructors
///
/// basic constructor
///
/// Id for this node
/// current node
internal AugmentedNode(int id, Node node)
: this(id, node, new List())
{
}
///
/// Yet another constructor
///
/// Id for this node
/// current node
/// list of children
internal AugmentedNode(int id, Node node, List children)
{
m_id = id;
m_node = node;
m_children = children;
PlanCompiler.Assert(children != null, "null children (gasp!)");
foreach (AugmentedNode chi in m_children)
{
chi.m_parent = this;
}
}
#endregion
#region public properties
///
/// Id of this node
///
internal int Id { get { return m_id; } }
///
/// The node
///
internal Node Node { get { return m_node; } }
///
/// Parent node
///
internal AugmentedNode Parent
{
get { return m_parent; }
}
///
/// List of children
///
internal List Children
{
get { return m_children; }
}
#endregion
}
///
/// Additional information for a "Table" node
///
internal sealed class AugmentedTableNode : AugmentedNode
{
#region private state
private int m_lastVisibleId;
private Table m_table;
private List m_joinEdges;
// The replacement table
private AugmentedTableNode m_replacementTable;
// Is this table being moved
private int m_newLocationId;
// List of columns of this table that are nullable (and must have nulls pruned out)
private VarVec m_nullableColumns;
#endregion
#region constructors
///
/// Basic constructor
///
/// node id
/// scan table node
internal AugmentedTableNode(int id, Node node) : base(id, node)
{
ScanTableOp scanTableOp = (ScanTableOp)node.Op;
m_table = scanTableOp.Table;
m_joinEdges = new List();
m_lastVisibleId = id;
m_replacementTable = this;
m_newLocationId = id;
}
#endregion
#region public properties
///
/// The Table
///
internal Table Table { get { return m_table; } }
///
/// List of directed edges in which this table is the "left" table
///
internal List JoinEdges
{
get { return m_joinEdges; }
}
///
/// The highest node (id) at which this table is visible
///
internal int LastVisibleId
{
get { return m_lastVisibleId; }
set { m_lastVisibleId = value; }
}
///
/// Has this table been eliminated
///
internal bool IsEliminated
{
get { return m_replacementTable != this; }
}
///
/// The replacement table (if any) for this table
///
internal AugmentedTableNode ReplacementTable
{
get { return m_replacementTable; }
set { m_replacementTable = value; }
}
///
/// New location for this table
///
internal int NewLocationId
{
get { return m_newLocationId; }
set { m_newLocationId = value; }
}
///
/// Has this table "moved" ?
///
internal bool IsMoved
{
get { return m_newLocationId != this.Id; }
}
///
/// Get the list of nullable columns (that require special handling)
///
internal VarVec NullableColumns
{
get { return m_nullableColumns; }
set { m_nullableColumns = value; }
}
#endregion
}
///
/// Additional information for a JoinNode
///
internal sealed class AugmentedJoinNode : AugmentedNode
{
#region private state
private List m_leftVars;
private List m_rightVars;
private Node m_otherPredicate;
#endregion
#region constructors
///
/// basic constructor
///
/// current node id
/// the join node
/// left side of the join (innerJoin, LOJ and FOJ only)
/// right side of the join
/// left-side equijoin vars
/// right-side equijoin vars
/// any remaining predicate
internal AugmentedJoinNode(int id, Node node,
AugmentedNode leftChild, AugmentedNode rightChild,
List leftVars, List rightVars,
Node otherPredicate)
: this(id, node, new List(new AugmentedNode[] {leftChild, rightChild}))
{
m_otherPredicate = otherPredicate;
m_rightVars = rightVars;
m_leftVars = leftVars;
}
///
/// Yet another constructor - used for crossjoins
///
/// node id
/// current node
/// list of children
internal AugmentedJoinNode(int id, Node node, List children)
: base(id, node, children)
{
m_leftVars = new List();
m_rightVars = new List();
}
#endregion
#region public properties
///
/// Non-equijoin predicate
///
internal Node OtherPredicate { get { return m_otherPredicate; } }
///
/// Equijoin columns of the left side
///
internal List LeftVars { get { return m_leftVars; } }
///
/// Equijoin columns of the right side
///
internal List RightVars { get { return m_rightVars; } }
#endregion
#region private methods
#endregion
}
#endregion
#region JoinGraph
///
/// The only join kinds we care about
///
internal enum JoinKind
{
Inner,
LeftOuter
}
///
/// Represents an "edge" in the join graph.
/// A JoinEdge is a directed equijoin between the left and the right table. The equijoin
/// columns are represented by the LeftVars and the RightVars properties
///
internal class JoinEdge
{
#region private state
private AugmentedTableNode m_left;
private AugmentedTableNode m_right;
private AugmentedJoinNode m_joinNode;
private JoinKind m_joinKind;
private List m_leftVars;
private List m_rightVars;
#endregion
#region constructors
///
/// Internal constructor
///
/// the left table
/// the right table
/// the owner join node
/// the Join Kind
/// list of equijoin columns of the left table
/// equijoin columns of the right table
private JoinEdge(AugmentedTableNode left, AugmentedTableNode right,
AugmentedJoinNode joinNode, JoinKind joinKind,
List leftVars, List rightVars)
{
m_left = left;
m_right = right;
m_joinKind = joinKind;
m_joinNode = joinNode;
m_leftVars = leftVars;
m_rightVars = rightVars;
PlanCompiler.Assert(m_leftVars.Count == m_rightVars.Count, "Count mismatch: " + m_leftVars.Count + "," + m_rightVars.Count);
}
#endregion
#region public apis
///
/// The left table
///
internal AugmentedTableNode Left { get { return m_left; } }
///
/// The right table of the join
///
internal AugmentedTableNode Right { get { return m_right; } }
///
/// The underlying join node, may be null
///
internal AugmentedJoinNode JoinNode { get { return m_joinNode; } }
///
/// The join kind
///
internal JoinKind JoinKind { get { return m_joinKind; } }
///
/// Equijoin columns of the left table
///
internal List LeftVars { get { return m_leftVars; } }
///
/// Equijoin columns of the right table
///
internal List RightVars { get { return m_rightVars; } }
///
/// Is this join edge useless?
///
internal bool IsEliminated
{
get { return this.Left.IsEliminated || this.Right.IsEliminated; }
}
///
/// Factory method
///
/// left table
/// right table
/// the owner join node
/// equijoin column of the left table
/// equijoin column of the right table
/// the new join edge
internal static JoinEdge CreateJoinEdge(AugmentedTableNode left, AugmentedTableNode right,
AugmentedJoinNode joinNode,
ColumnVar leftVar, ColumnVar rightVar)
{
List leftVars = new List();
List rightVars = new List();
leftVars.Add(leftVar);
rightVars.Add(rightVar);
OpType joinOpType = joinNode.Node.Op.OpType;
PlanCompiler.Assert((joinOpType == OpType.LeftOuterJoin || joinOpType == OpType.InnerJoin),
"Unexpected join type for join edge: " + joinOpType);
JoinKind joinKind = joinOpType == OpType.LeftOuterJoin ? JoinKind.LeftOuter : JoinKind.Inner;
JoinEdge joinEdge = new JoinEdge(left, right, joinNode, joinKind, leftVars, rightVars);
return joinEdge;
}
///
/// Creates a transitively generated join edge
///
/// the left table
/// the right table
/// the join kind
/// left equijoin vars
/// right equijoin vars
/// the join edge
internal static JoinEdge CreateTransitiveJoinEdge(AugmentedTableNode left, AugmentedTableNode right, JoinKind joinKind,
List leftVars, List rightVars)
{
JoinEdge joinEdge = new JoinEdge(left, right, null, joinKind, leftVars, rightVars);
return joinEdge;
}
///
/// Add a new "equi-join" condition to this edge
///
/// join node producing this condition
/// the left-side column
/// the right-side column
/// true, if this condition can be added
internal bool AddCondition(AugmentedJoinNode joinNode, ColumnVar leftVar, ColumnVar rightVar)
{
if (joinNode != m_joinNode)
{
return false;
}
m_leftVars.Add(leftVar);
m_rightVars.Add(rightVar);
return true;
}
#endregion
}
///
/// Represents a join graph. The uber-class for join elimination
///
internal class JoinGraph
{
#region private state
private Command m_command;
private AugmentedJoinNode m_root;
private List m_vertexes;
private List m_tableVertexes;
private Dictionary m_tableVertexMap;
private VarMap m_varMap;
private Dictionary m_varToDefiningNodeMap; //Includes all replacing vars and referenced vars from replacing tables
private Dictionary m_processedNodes;
private bool m_modifiedGraph;
private ConstraintManager m_constraintManager;
private VarRefManager m_varRefManager;
#endregion
#region constructors
///
/// The basic constructor. Builds up the annotated node tree, and the set of
/// join edges
///
/// Current IQT command
/// current constraint manager
/// the var ref manager for the tree
/// current join node
internal JoinGraph(Command command, ConstraintManager constraintManager, VarRefManager varRefManager, Node joinNode)
{
m_command = command;
m_constraintManager = constraintManager;
m_varRefManager = varRefManager;
m_vertexes = new List();
m_tableVertexes = new List();
m_tableVertexMap = new Dictionary();
m_varMap = new VarMap();
m_varToDefiningNodeMap = new Dictionary();
m_processedNodes = new Dictionary();
// Build the augmented node tree
m_root = BuildAugmentedNodeTree(joinNode) as AugmentedJoinNode;
PlanCompiler.Assert(m_root != null, "The root isn't a join?");
// Build the join edges
BuildJoinEdges(m_root, m_root.Id);
}
#endregion
#region public methods
///
/// Perform all kinds of join elimination. The output is the transformed join tree.
/// The varMap output is a dictionary that maintains var renames - this will be used
/// by the consumer of this module to fix up references to columns of tables
/// that have been eliminated
///
/// The processedNodes dictionary is simply a set of all nodes that have been processed
/// in this module - and need no further "join graph" processing
///
/// remapped vars
/// list of nodes that need no further processing
internal Node DoJoinElimination(out VarMap varMap,
out Dictionary processedNodes)
{
// Generate transitive edges
GenerateTransitiveEdges();
// Do real join elimination
EliminateSelfJoins();
EliminateParentChildJoins();
// Build the result tree
Node result = BuildNodeTree();
// Get other output properties
varMap = m_varMap;
processedNodes = m_processedNodes;
return result;
}
#endregion
#region private methods
#region Building the annotated node tree
//
// The goal of this submodule is to build up an annotated node tree for a
// node tree. As described earlier, we attempt to represent all nodes by
// one of the following classes - AugmentedTableNode (for ScanTableOp),
// AugmentedJoinNode (for all joins), and AugmentedNode for anything else.
// We use this information to help enable later stages of this module
//
// We employ a "greedy" strategy to handle as much of the node tree as possible.
// We follow all children of joins - and stop when we see a non-join, non-scan node
//
///
/// Get the subset of vars that are Columns
///
/// a varVec
/// a subsetted VarVec that only contains the columnVars from the input vec
private VarVec GetColumnVars(VarVec varVec)
{
VarVec columnVars = m_command.CreateVarVec();
foreach (Var v in varVec)
{
if (v.VarType == VarType.Column)
{
columnVars.Set(v);
}
}
return columnVars;
}
///
/// Generate a list of column Vars from the input vec
///
/// the list of vars to fill in
/// the var set
private static void GetColumnVars(List columnVars, IEnumerable vec)
{
foreach (Var v in vec)
{
PlanCompiler.Assert(v.VarType == VarType.Column, "Expected a columnVar. Found " + v.VarType);
columnVars.Add((ColumnVar)v);
}
}
///
/// Split up the join predicate into equijoin columns and other predicates.
///
/// For example, if I have a predicate of the form T1.C1 = T2.D1 and T1.C2 > T2.D2
/// we would generate
/// LeftVars = T1.C1
/// RightVars = T2.C1
/// OtherPredicate = T1.C2 > T2.D2
///
/// Special Cases:
/// For fullouter joins, we don't do any splitting - the "OtherPredicate" captures the
/// entire join condition.
///
/// the current join node
/// equijoin columns of the left side
/// equijoin columns of the right side
/// any other predicates
private void SplitPredicate(Node joinNode,
out List leftVars, out List rightVars,
out Node otherPredicateNode)
{
leftVars = new List();
rightVars = new List();
otherPredicateNode = joinNode.Child2;
//
// If this is a full-outer join, then don't do any splitting
//
if (joinNode.Op.OpType == OpType.FullOuterJoin)
{
return;
}
Predicate predicate = new Predicate(m_command, joinNode.Child2);
//
// Split the predicate
//
ExtendedNodeInfo leftInputNodeInfo = m_command.GetExtendedNodeInfo(joinNode.Child0);
ExtendedNodeInfo rightInputNodeInfo = m_command.GetExtendedNodeInfo(joinNode.Child1);
VarVec leftDefinitions = GetColumnVars(leftInputNodeInfo.Definitions);
VarVec rightDefinitions = GetColumnVars(rightInputNodeInfo.Definitions);
Predicate otherPredicate;
List tempLeftVars;
List tempRightVars;
predicate.GetEquiJoinPredicates(leftDefinitions, rightDefinitions, out tempLeftVars, out tempRightVars, out otherPredicate);
// Get the non-equijoin conditions
otherPredicateNode = otherPredicate.BuildAndTree();
GetColumnVars(leftVars, tempLeftVars);
GetColumnVars(rightVars, tempRightVars);
}
///
/// Build up the annotated node tree for the input subtree.
/// If the current node is
/// a ScanTableOp - we build an AugmentedTableNode
/// a join (Inner, LOJ, FOJ, CrossJoin) - we build an AugmentedJoinNode,
/// after first building annotated node trees for the inputs.
/// anything else - we build an AugmentedNode
///
/// We also mark the node as "processed" - so that the caller will not need
/// to build join graphs for this again
///
/// input node tree
/// the annotated node tree
private AugmentedNode BuildAugmentedNodeTree(Node node)
{
AugmentedNode augmentedNode;
switch (node.Op.OpType)
{
case OpType.ScanTable:
m_processedNodes[node] = node;
ScanTableOp scanTableOp = (ScanTableOp)node.Op;
augmentedNode = new AugmentedTableNode(m_vertexes.Count, node);
m_tableVertexMap[scanTableOp.Table] = (AugmentedTableNode)augmentedNode;
break;
case OpType.InnerJoin:
case OpType.LeftOuterJoin:
case OpType.FullOuterJoin:
m_processedNodes[node] = node;
AugmentedNode left = BuildAugmentedNodeTree(node.Child0);
AugmentedNode right = BuildAugmentedNodeTree(node.Child1);
List leftVars;
List rightVars;
Node otherPredicate;
SplitPredicate(node, out leftVars, out rightVars, out otherPredicate);
m_varRefManager.AddChildren(node);
augmentedNode = new AugmentedJoinNode(m_vertexes.Count, node, left, right, leftVars, rightVars, otherPredicate);
break;
case OpType.CrossJoin:
m_processedNodes[node] = node;
List children = new List();
foreach (Node chi in node.Children)
{
children.Add(BuildAugmentedNodeTree(chi));
}
augmentedNode = new AugmentedJoinNode(m_vertexes.Count, node, children);
m_varRefManager.AddChildren(node);
break;
default:
augmentedNode = new AugmentedNode(m_vertexes.Count, node);
break;
}
m_vertexes.Add(augmentedNode);
return augmentedNode;
}
#endregion
#region Building JoinEdges
//
// The goal of this module is to take the annotated node tree, and build up a
// a set of JoinEdges - this is arguably, the guts of the joingraph.
//
// Each join edge represents a directed, equijoin (inner, or leftouter) between
// two tables.
//
// We impose various constraints on the input node tree
//
///
/// Add a new join edge if possible.
///
/// - Check to see whether the input columns are columns of a table that we're tracking.
/// - Make sure that both the tables are "visible" to the current join node
/// - If there is already a link between the two tables, make sure that the link's
/// join kind is compatible with what we have
///
/// current join Node
/// left-side column
/// right-side column
///
private bool AddJoinEdge(AugmentedJoinNode joinNode, ColumnVar leftVar, ColumnVar rightVar)
{
AugmentedTableNode leftTableNode;
AugmentedTableNode rightTableNode;
// Are these tables even visible to me?
if (!m_tableVertexMap.TryGetValue(leftVar.Table, out leftTableNode))
{
return false;
}
if (!m_tableVertexMap.TryGetValue(rightVar.Table, out rightTableNode))
{
return false;
}
//
// If the tables participating in the join are not visible at this node,
// then simply return. We will not add the join edge
//
if (leftTableNode.LastVisibleId < joinNode.Id ||
rightTableNode.LastVisibleId < joinNode.Id)
{
return false;
}
//
// Check to see if there is already an "edge" between the 2 tables.
// If there is, then simply add a predicate to that edge. Otherwise, create
// an edge
//
foreach (JoinEdge joinEdge in leftTableNode.JoinEdges)
{
if (joinEdge.Right.Table.Equals(rightVar.Table))
{
// Try and add this new condition to the existing edge
return joinEdge.AddCondition(joinNode, leftVar, rightVar);
}
}
// Create a new join edge
JoinEdge newJoinEdge = JoinEdge.CreateJoinEdge(leftTableNode, rightTableNode, joinNode, leftVar, rightVar);
leftTableNode.JoinEdges.Add(newJoinEdge);
return true;
}
///
/// Check to see if all columns in the input varList are from the same table
/// Degenerate case: if the list is empty, we still return true
///
/// list of columns
/// true, if every column is from the same table
private static bool SingleTableVars(IEnumerable varList)
{
Table table = null;
foreach (ColumnVar v in varList)
{
if (table == null)
{
table = v.Table;
}
else if (v.Table != table)
{
return false;
}
}
return true;
}
///
/// Build a set of JoinEdges for this join.
/// For cross joins, we simply invoke this function recursively on the children, and return
///
/// For other joins,
/// - We first compute the "visibility" for the left and right branches
/// - For full outer joins, the "visibility" is the current join node's id. (ie)
/// the tables below are not to be considered as candidates for JoinEdges anywhere
/// above this FOJ node
/// - For left outer joins, the "visibility" of the left child is the input "maxVisibility"
/// parameter. For the right child, the "visibility" is the current join node's id
/// - For inner joins, the visibility for both children is the "maxVisibility" parameter
/// - We then check to see if the join condition is "ok". If the current join node
/// is a full-outer join, OR if the joinNode has an OtherPredicate (ie) stuff
/// other than equijoin column conditions, then we don't build any joinedges.
/// - Otherwise, we build join edges for each equijoin column
///
///
/// current join node
/// the highest node where any of the tables below is visible
private void BuildJoinEdges(AugmentedJoinNode joinNode, int maxVisibility)
{
OpType opType = joinNode.Node.Op.OpType;
//
// Simply visit the children for cross-joins
//
if (opType == OpType.CrossJoin)
{
foreach (AugmentedNode chi in joinNode.Children)
{
BuildJoinEdges(chi, maxVisibility);
}
return;
}
//
// If the current node is a leftouterjoin, or a full outer join, then
// none of the tables below should be visible anymore
//
int leftMaxVisibility;
int rightMaxVisibility;
if (opType == OpType.FullOuterJoin)
{
leftMaxVisibility = joinNode.Id;
rightMaxVisibility = joinNode.Id;
}
else if (opType == OpType.LeftOuterJoin)
{
leftMaxVisibility = maxVisibility;
rightMaxVisibility = joinNode.Id;
}
else
{
leftMaxVisibility = maxVisibility;
rightMaxVisibility = maxVisibility;
}
BuildJoinEdges(joinNode.Children[0], leftMaxVisibility);
BuildJoinEdges(joinNode.Children[1], rightMaxVisibility);
// Now handle the predicate
// Special cases. Nothing further if there exists anything other than
// a set of equi-join predicates
if (joinNode.Node.Op.OpType == OpType.FullOuterJoin ||
joinNode.OtherPredicate != null ||
joinNode.LeftVars.Count == 0)
{
return;
}
//
// If we have a left-outer join, and the join predicate involves more than one table on the
// right side, then quit
//
if ((opType == OpType.LeftOuterJoin) &&
(!SingleTableVars(joinNode.RightVars) || !SingleTableVars(joinNode.LeftVars)))
{
return;
}
JoinKind joinKind = (opType == OpType.LeftOuterJoin) ? JoinKind.LeftOuter : JoinKind.Inner;
for (int i = 0; i < joinNode.LeftVars.Count; i++)
{
// Add a join edge.
if (AddJoinEdge(joinNode, joinNode.LeftVars[i], joinNode.RightVars[i]))
{
// If we have an inner join, then add a "reverse" edge, but only
// if the previous AddEdge was successful
if (joinKind == JoinKind.Inner)
{
AddJoinEdge(joinNode, joinNode.RightVars[i], joinNode.LeftVars[i]);
}
}
}
}
///
/// Builds up the list of join edges. If the current node is
/// a ScanTable - we simply set the "LastVisibleId" property to the maxVisibility
/// parameter
/// a join - we invoke the BuildJoinEdges() function on the join node
/// anything else - do nothing
///
///
/// highest node that this node is visible at
private void BuildJoinEdges(AugmentedNode node, int maxVisibility)
{
switch (node.Node.Op.OpType)
{
case OpType.FullOuterJoin:
case OpType.LeftOuterJoin:
case OpType.InnerJoin:
case OpType.CrossJoin:
BuildJoinEdges(node as AugmentedJoinNode, maxVisibility);
// Now visit the predicate
break;
case OpType.ScanTable:
AugmentedTableNode tableNode = (AugmentedTableNode)node;
tableNode.LastVisibleId = maxVisibility;
break;
default:
break;
}
return;
}
#endregion
#region Transitive Edge generation
//
// The goal of this module is to generate transitive join edges.
// In general, if A is joined to B, and B is joined to C, then A can be joined to
// C as well.
// We apply the rules below to determine if we can indeed generate transitive
// join edges
// Assume that J1 = (A, B), and J2=(B,C)
// - J1.Kind must be the same as J2.Kind (both must be Inner, or both must be LeftOuterJoins)
// - If J1 is a left-outer join, then A,B and C must all be instances of the same table
// - The same columns of B must participate in the joins with A and C
// If all of these conditions are satisfied, we generate a new edge between A and C
// If we're dealing with an inner join, we also generate a C-A edge
//
// Note: We never produce any duplicate edges (ie) if an edge already exists between
// A and C in the example above, we don't try to generate a new edge, or modify the existing
// edge
//
///
/// If edge1 represents (T1, T2), and edge2 represents (T2, T3), try and
/// create a (T1,T3) edge.
///
/// If an edge already exists between these tables, then don't add a new edge
///
///
///
private bool GenerateTransitiveEdge(JoinEdge edge1, JoinEdge edge2)
{
PlanCompiler.Assert(edge1.Right == edge2.Left, "need a common table for transitive predicate generation");
// Ignore the "mirror" image.
if (edge2.Right == edge1.Left)
{
return false;
}
// Check to see if the joins are of the same type. Allow left-outer-joins
// only for self-joins
if (edge1.JoinKind != edge2.JoinKind)
{
return false;
}
if (edge1.JoinKind == JoinKind.LeftOuter &&
(edge1.Left != edge1.Right || edge2.Left != edge2.Right))
{
return false;
}
// Check to see if the joins are on the same columns
if (edge1.RightVars.Count != edge2.LeftVars.Count)
{
return false;
}
// check to see whether there already exists an edge for the combination
// of these tables
foreach (JoinEdge edge3 in edge1.Left.JoinEdges)
{
if (edge3.Right == edge2.Right)
{
return false;
}
}
VarVec vec1 = m_command.CreateVarVec();
foreach (Var v in edge1.RightVars)
{
vec1.Set(v);
}
foreach (Var v in edge2.LeftVars)
{
if (!vec1.IsSet(v))
{
return false;
}
}
// Ok, so we've finally identified an edge that looks to be transitive
Dictionary varMap1 = new Dictionary();
for (int i = 0; i < edge1.LeftVars.Count; i++)
{
varMap1[edge1.RightVars[i]] = edge1.LeftVars[i];
}
List leftVars = new List();
List rightVars = new List(edge2.RightVars);
for (int i = 0; i < edge1.LeftVars.Count; i++)
{
ColumnVar newLeftVar = varMap1[edge2.LeftVars[i]];
leftVars.Add(newLeftVar);
}
// Ok, we're now ready to finally create a new edge
JoinEdge newEdge = JoinEdge.CreateTransitiveJoinEdge(edge1.Left, edge2.Right, edge1.JoinKind,
leftVars, rightVars);
edge1.Left.JoinEdges.Add(newEdge);
if (edge1.JoinKind == JoinKind.Inner)
{
JoinEdge reverseEdge = JoinEdge.CreateTransitiveJoinEdge(edge2.Right, edge1.Left, edge1.JoinKind,
rightVars, leftVars);
edge2.Right.JoinEdges.Add(reverseEdge);
}
return true;
}
///
/// Generate a set of transitive edges
///
private void GenerateTransitiveEdges()
{
foreach (AugmentedNode augmentedNode in m_vertexes)
{
AugmentedTableNode tableNode = augmentedNode as AugmentedTableNode;
if (tableNode == null)
{
continue;
}
//
// The reason we use absolute indexing rather than 'foreach'ing is because
// the inner calls may add new entries to the collections, and cause the
// enumeration to throw
//
int i = 0;
while (i < tableNode.JoinEdges.Count)
{
JoinEdge e1 = tableNode.JoinEdges[i];
int j = 0;
AugmentedTableNode rightTable = e1.Right;
while (j < rightTable.JoinEdges.Count)
{
JoinEdge e2 = rightTable.JoinEdges[j];
GenerateTransitiveEdge(e1, e2);
j++;
}
i++;
}
}
}
#endregion
#region Join Elimination Helpers
//
// Utility routines used both by selfjoin elimination and parent-child join
// elimination
//
///
/// Checks whether a given table can be eliminated to be replaced by the given replacingTable
/// with regards to possible participation in the driving (left) subtree of Left Outer Joins.
///
/// In order for elimination to happen, one of the two tables has to logically move,
/// either the replacement table to the original table's location, or the table to the
/// replacing table's location.
///
/// For the table that would have to move, it checks whether such move would be valid
/// with regards to its participation as driver in Left Outer Joins ()
///
///
///
///
private static bool CanBeEliminated(AugmentedTableNode table, AugmentedTableNode replacingTable)
{
//The table with lower id, would have to be logically located at the other table's location
//Check whether it can be moved there
if (replacingTable.Id < table.NewLocationId)
{
return CanBeMoved(table, replacingTable);
}
else
{
return CanBeMoved(replacingTable, table);
}
}
///
/// Determines whether the given table can be moved to the replacing table's location
/// with regards to participation in the driving (left) subtree of Left Outer Joins.
/// If the table to be moved is part of the driving (left) subtree of a Left Outer Join
/// and the replacing table is not part of that subtree then the table cannot be moved,
/// otherwise it can.
///
///
///
///
private static bool CanBeMoved(AugmentedTableNode table, AugmentedTableNode replacingTable)
{
AugmentedNode leastCommonAncesstor = GetLeastCommonAncestor(table, replacingTable);
AugmentedNode currentNode = table;
while (currentNode.Parent != null && currentNode != leastCommonAncesstor)
{
//If the current node is a left child of an left outer join return
if (currentNode.Parent.Node.Op.OpType == OpType.LeftOuterJoin &&
currentNode.Parent.Children[0] == currentNode)
{
return false;
}
currentNode = currentNode.Parent;
}
return true;
}
///
/// Gets the least common ancestor for two given nodes in the tree
///
///
///
///
private static AugmentedNode GetLeastCommonAncestor(AugmentedNode node1, AugmentedNode node2)
{
if (node1.Id == node2.Id)
{
return node1;
}
AugmentedNode currentParent;
AugmentedNode rigthNode;
if (node1.Id < node2.Id)
{
currentParent = node1;
rigthNode = node2;
}
else
{
currentParent = node2;
rigthNode = node1;
}
while (currentParent.Id < rigthNode.Id)
{
currentParent = currentParent.Parent;
}
return currentParent;
}
///
/// This function marks a table as eliminated. The replacement varmap
/// is updated with columns of the table being mapped to the corresponding columns
/// of the replacement table
///
/// table being replaced
/// the table being used in its place
/// list of vars to replace
/// list of vars to replace with
/// Var or one of its subtypes
private void MarkTableAsEliminated(AugmentedTableNode tableNode, AugmentedTableNode replacementNode,
List tableVars, List replacementVars) where T : Var
{
PlanCompiler.Assert(tableVars != null && replacementVars != null, "null vars");
PlanCompiler.Assert(tableVars.Count == replacementVars.Count, "var count mismatch");
PlanCompiler.Assert(tableVars.Count > 0, "no vars in the table ?");
m_modifiedGraph = true;
// Set up the replacement table (if necessary)
if (tableNode.Id < replacementNode.NewLocationId)
{
tableNode.ReplacementTable = replacementNode;
replacementNode.NewLocationId = tableNode.Id;
}
else
{
tableNode.ReplacementTable = null;
}
// Add mappings for each var of the table
for (int i = 0; i < tableVars.Count; i++)
{
//
// Bug 446708: Make sure that the "replacement" column is
// referenced, if the the current column is referenced
//
if (tableNode.Table.ReferencedColumns.IsSet(tableVars[i]))
{
m_varMap[tableVars[i]] = replacementVars[i];
replacementNode.Table.ReferencedColumns.Set(replacementVars[i]);
}
}
//
// It should be possible to retrieve the location of each replacing var
// It should also be possible to retrieve the location of each referenced var
// defined on a replacing table, because replacing tables may get moved.
//
foreach (Var var in replacementNode.Table.ReferencedColumns)
{
m_varToDefiningNodeMap[var] = replacementNode;
}
}
#endregion
#region SelfJoin Elimination
//
// The goal of this submodule is to eliminate selfjoins. We consider two kinds
// of selfjoins here - explicit, and implicit.
//
// An explicit selfjoin J is a join between tables T1 and T2, where T1 and T2
// are instances of the same table. Furthemore, T1 and T2 must be joined on their
// key columns (and no more).
//
// An implicit self-join is of the form (X, A1, A2, ...) where A1, A2 etc.
// are all instances of the same table, and X is joined to A1, A2 etc. on the same
// columns. We also call this a "star" selfjoin, since "X" is logically the
// being star-joined to all the other tables here
//
///
/// This function marks a table (part of a selfjoin) as eliminated. The replacement varmap
/// is updated with columns of the table being mapped to the corresponding columns
/// of the replacement table
///
/// table being replaced
/// the table being used in its place
private void EliminateSelfJoinedTable(AugmentedTableNode tableNode, AugmentedTableNode replacementNode)
{
MarkTableAsEliminated(tableNode, replacementNode, tableNode.Table.Columns, replacementNode.Table.Columns);
}
///
/// This function is a helper function for star selfjoin elimination. All the
/// "right" tables of the join edges in the input list are instances of the same table.
///
/// Precondition: Each joinedge is of the form (X, Ai),
/// where X is the star-joined table, and A1...An are all instances of the same
/// table A
///
/// This function checks to see if all the tables are in fact joined on the same columns,
/// all the edges are of the same kind, and all the key columns of the table are used
///
/// If all the conditions are satisfied, we then identify the table with the
/// smallest "Id", and choose that to replace all the other tables
///
///
/// list of join edges
private void EliminateStarSelfJoin(List joinEdges)
{
JoinEdge firstJoinEdge = joinEdges[0];
//
// Now make sure that all key columns of the right table are used
//
VarVec keyVars = m_command.CreateVarVec(firstJoinEdge.Right.Table.Keys);
foreach (Var v in firstJoinEdge.RightVars)
{
// Make sure that no other column is referenced in case of an outer join
if (firstJoinEdge.JoinKind == JoinKind.LeftOuter && !keyVars.IsSet(v))
{
return;
}
keyVars.Clear(v);
}
if (!keyVars.IsEmpty)
{
return;
}
//
// Now make sure that all the joins are on the same columns
//
for (int i = 1; i < joinEdges.Count; i++)
{
JoinEdge joinEdge = joinEdges[i];
// Not compatible, if we're not joining on the same number of columns,
// or if the joinkind does not match
if (joinEdge.LeftVars.Count != firstJoinEdge.LeftVars.Count ||
joinEdge.JoinKind != firstJoinEdge.JoinKind)
{
return;
}
// Now make sure that we're joining on the same columns
for (int j = 0; j < joinEdge.LeftVars.Count; j++)
{
// Check for reference equality on the left-table Vars. Check for
// name equality on the right table vars
if (!joinEdge.LeftVars[j].Equals(firstJoinEdge.LeftVars[j]) ||
!joinEdge.RightVars[j].ColumnMetadata.Name.Equals(firstJoinEdge.RightVars[j].ColumnMetadata.Name))
{
return;
}
}
}
//
// Ok. We've now found that the tables can in fact be eliminated. Identify the
// table with the smallest id, and use that as the candidate
//
JoinEdge smallestEdge = firstJoinEdge;
foreach (JoinEdge joinEdge in joinEdges)
{
if (smallestEdge.Right.Id > joinEdge.Right.Id)
{
smallestEdge = joinEdge;
}
}
//
// Now walk through all the edges, and mark all the tables as eliminated
//
foreach (JoinEdge joinEdge in joinEdges)
{
if (joinEdge == smallestEdge)
{
continue;
}
if (CanBeEliminated(joinEdge.Right, smallestEdge.Right))
{
EliminateSelfJoinedTable(joinEdge.Right, smallestEdge.Right);
}
}
// Done
}
///
/// Eliminates any star self joins. This function looks at all the tables that
/// this table is joined to, groups the tables based on the table name (metadata),
/// and then tries selfjoin elimination on each group (see function above)
///
/// the star-joined table?
private void EliminateStarSelfJoins(AugmentedTableNode tableNode)
{
// First build up a number of equivalence classes. Each equivalence class
// contains instances of the same table
Dictionary> groupedEdges = new Dictionary>();
foreach (JoinEdge joinEdge in tableNode.JoinEdges)
{
// Ignore useless edges
if (joinEdge.IsEliminated)
{
continue;
}
List edges;
if (!groupedEdges.TryGetValue(joinEdge.Right.Table.TableMetadata.Extent, out edges))
{
edges = new List();
groupedEdges[joinEdge.Right.Table.TableMetadata.Extent] = edges;
}
edges.Add(joinEdge);
}
// Now walk through each equivalence class, and identify if we can eliminate some of
// the self-joins
foreach (KeyValuePair> kv in groupedEdges)
{
// If there's only one table in the class, skip this and move on
if (kv.Value.Count <= 1)
{
continue;
}
// Try and do the real dirty work
EliminateStarSelfJoin(kv.Value);
}
}
///
/// Eliminate a self-join edge.
///
/// the join edge
/// tur, if we did eliminate the self-join
private bool EliminateSelfJoin(JoinEdge joinEdge)
{
// Nothing further to do, if the right-side has already been eliminated
if (joinEdge.IsEliminated)
{
return false;
}
// Am I a self-join?
if (!joinEdge.Left.Table.TableMetadata.Extent.Equals(joinEdge.Right.Table.TableMetadata.Extent))
{
return false;
}
// Check to see that only the corresponding columns are being compared
for (int i = 0; i < joinEdge.LeftVars.Count; i++)
{
if (!joinEdge.LeftVars[i].ColumnMetadata.Name.Equals(joinEdge.RightVars[i].ColumnMetadata.Name))
{
return false;
}
}
//
// Now make sure that the join edge includes every single key column
// For left-outer joins, we must have no columns other than the key columns
//
VarVec keyVars = m_command.CreateVarVec(joinEdge.Left.Table.Keys);
foreach (Var v in joinEdge.LeftVars)
{
if (joinEdge.JoinKind == JoinKind.LeftOuter && !keyVars.IsSet(v))
{
return false;
}
keyVars.Clear(v);
}
// Are some keys left over?
if (!keyVars.IsEmpty)
{
return false;
}
if (!CanBeEliminated(joinEdge.Right, joinEdge.Left))
{
return false;
}
// Mark the right-table as eliminated
// Get the parent node for the right node, and replace the parent by the corresponding
// left node
EliminateSelfJoinedTable(joinEdge.Right, joinEdge.Left);
return true;
}
///
/// Eliminate self-joins for this table (if any)
///
/// current table
private void EliminateSelfJoins(AugmentedTableNode tableNode)
{
// Is this node already eliminated?
if (tableNode.IsEliminated)
{
return;
}
// First try and eliminate all explicit self-joins
foreach (JoinEdge joinEdge in tableNode.JoinEdges)
{
EliminateSelfJoin(joinEdge);
}
}
///
/// Eliminate all selfjoins
///
private void EliminateSelfJoins()
{
foreach (AugmentedNode augmentedNode in m_vertexes)
{
AugmentedTableNode tableNode = augmentedNode as AugmentedTableNode;
if (tableNode != null)
{
EliminateSelfJoins(tableNode);
EliminateStarSelfJoins(tableNode);
}
}
}
#endregion
#region Parent-Child join elimination
//
// The goal of this submodule is to eliminate parent-child joins. We consider two kinds
// of parent-child joins here.
//
// The first category of joins involves a 1-1 or 1-n relationship between a parent
// and child table, where the tables are (inner) joined on the key columns (pk, fk), and no
// other columns of the parent table are referenced. In this case, the parent table
// can be eliminated, and the child table used in place. There are two special considerations
// here.
// First, the foreign key columns may be nullable - in this case, we need to prune
// out rows where these null values might occur (since they would have been pruned
// out by the join). In effect, we add a filter node above the table node, if there
// are any nullable foreign keys.
// The second case is where the parent table appears "lexically" before the child
// table in the query. In this case, the child table will need to "move" to the
// parent table's location - this is needed for scenarios where there may be other
// intervening tables where the parent table's key columns are referenced - and these
// cannot see the equivalent columns of the child table, unless the child table is
// moved to that location.
//
// The second category of joins involves a 1-1 relationship between the parent and
// child table, where the parent table is left outer joined to the child table
// on the key columns. If no other columns of the child table are referenced in the
// query, then the child table can be eliminated.
//
///
/// Eliminate the parent table
///
///
private void EliminateParentTable(JoinEdge joinEdge)
{
PlanCompiler.Assert(joinEdge.JoinKind == JoinKind.Inner, "Expected inner join");
MarkTableAsEliminated(joinEdge.Left, joinEdge.Right, joinEdge.LeftVars, joinEdge.RightVars);
//
// Find the list of non-nullable columns
//
if (joinEdge.Right.NullableColumns == null)
{
joinEdge.Right.NullableColumns = m_command.CreateVarVec();
}
foreach (ColumnVar v in joinEdge.RightVars)
{
//
// if the column is known to be non-nullable, then we don't need to
// add a filter condition to prune out nulls later.
//
if (v.ColumnMetadata.IsNullable)
{
joinEdge.Right.NullableColumns.Set(v);
}
}
}
///
/// Eliminate the child table
///
///
private void EliminateChildTable(JoinEdge joinEdge)
{
PlanCompiler.Assert(joinEdge.JoinKind == JoinKind.LeftOuter, "Expected left-outer-join");
PlanCompiler.Assert(joinEdge.Left.Id < joinEdge.Right.Id,
"(left-id, right-id) = (" + joinEdge.Left.Id + "," + joinEdge.Right.Id + ")");
MarkTableAsEliminated(joinEdge.Right, joinEdge.Left, joinEdge.RightVars, joinEdge.LeftVars);
}
///
/// Do we reference any nonkey columns from this table
///
/// the table instance
/// true, if there are any nonkey references
private static bool HasNonKeyReferences(Table table)
{
return !table.Keys.Subsumes(table.ReferencedColumns);
}
///
/// Are any of the key columns from the child (right) table of the given join edge referenced
/// elsewhere (outside the join condition)
///
///
///
private bool ChildTableHasKeyReferences(JoinEdge joinEdge)
{
//For transitive edges we don't have a joinNode.
if (joinEdge.JoinNode == null)
{
// Note: We have not been able to hit this yet. If we find many cases in which we hit this,
// we can see if we can do more tracking. This way we may be missing cases that could be optimized.
return true;
}
return m_varRefManager.HasKeyReferences(joinEdge.Right.Table.Keys, joinEdge.Right.Node, joinEdge.JoinNode.Node);
}
///
/// Eliminate a parent-child join, given a fk constraint
///
/// the current join edge
/// the referential integrity constraint
///
private bool TryEliminateParentChildJoin(JoinEdge joinEdge, ForeignKeyConstraint fkConstraint)
{
//
// Consider join elimination for left-outer-joins only if we have a 1 - 1 or 1 - 0..1 relationship
//
if (joinEdge.JoinKind == JoinKind.LeftOuter && fkConstraint.ChildMultiplicity == md.RelationshipMultiplicity.Many)
{
return false;
}
//
// Make sure that every one of the parent key properties is referenced
//
foreach (string keyProp in fkConstraint.ParentKeys)
{
bool foundKey = false;
foreach (ColumnVar cv in joinEdge.LeftVars)
{
if (cv.ColumnMetadata.Name.Equals(keyProp))
{
foundKey = true;
break;
}
}
if (!foundKey)
{
return false;
}
}
//
// Make sure that every one of the child key properties is referenced
// and furthermore equi-joined to the corresponding parent key properties
//
foreach (string keyProp in fkConstraint.ChildKeys)
{
bool foundKey = false;
for (int pos = 0; pos < joinEdge.LeftVars.Count; pos++)
{
ColumnVar rightVar = joinEdge.RightVars[pos];
if (rightVar.ColumnMetadata.Name.Equals(keyProp))
{
foundKey = true;
string parentPropertyName;
ColumnVar leftVar = joinEdge.LeftVars[pos];
if (!fkConstraint.GetParentProperty(rightVar.ColumnMetadata.Name, out parentPropertyName) ||
!parentPropertyName.Equals(leftVar.ColumnMetadata.Name))
{
return false;
}
break;
}
}
if (!foundKey)
{
return false;
}
}
//
// For inner joins, try and eliminate the parent table
//
if (joinEdge.JoinKind == JoinKind.Inner)
{
if (HasNonKeyReferences(joinEdge.Left.Table))
{
return false;
}
if (!CanBeEliminated(joinEdge.Right, joinEdge.Left))
{
return false;
}
// Mark the left-side table as "eliminated"
EliminateParentTable(joinEdge);
}
//
// For left outer joins, try and eliminate the child table
//
else if (joinEdge.JoinKind == JoinKind.LeftOuter)
{
if (HasNonKeyReferences(joinEdge.Right.Table) ||
// SQLBUDT #512375: For the 1 - 0..1 we also verify that the child's columns are not
// referenced outside the join condition
(fkConstraint.ChildMultiplicity == md.RelationshipMultiplicity.ZeroOrOne && ChildTableHasKeyReferences(joinEdge)))
{
return false;
}
if (!CanBeEliminated(joinEdge.Right, joinEdge.Left))
{
return false;
}
// Eliminate the child table
EliminateChildTable(joinEdge);
}
return true;
}
///
/// Eliminate the join if possible, for this edge
///
/// the current join edge
private void EliminateParentChildJoin(JoinEdge joinEdge)
{
List fkConstraints;
// Is there a foreign key constraint between these 2 tables?
if (!m_constraintManager.IsParentChildRelationship(joinEdge.Left.Table.TableMetadata.Extent, joinEdge.Right.Table.TableMetadata.Extent,
out fkConstraints))
{
return;
}
PlanCompiler.Assert(fkConstraints != null && fkConstraints.Count > 0, "invalid fk constraints?");
// Now walk through the list of foreign key constraints and attempt join
// elimination
foreach (ForeignKeyConstraint fkConstraint in fkConstraints)
{
if (TryEliminateParentChildJoin(joinEdge, fkConstraint))
{
return;
}
}
}
///
/// Eliminate parent child nodes that this node participates in
///
/// the "left" table in a join
private void EliminateParentChildJoins(AugmentedTableNode tableNode)
{
foreach (JoinEdge joinEdge in tableNode.JoinEdges)
{
EliminateParentChildJoin(joinEdge);
if (tableNode.IsEliminated)
{
return;
}
}
}
///
/// Eliminate all parent-child joins in the join graph
///
private void EliminateParentChildJoins()
{
foreach (AugmentedNode node in m_vertexes)
{
AugmentedTableNode tableNode = node as AugmentedTableNode;
if (tableNode != null && !tableNode.IsEliminated)
{
EliminateParentChildJoins(tableNode);
}
}
}
#endregion
#region Rebuilding the Node Tree
//
// The goal of this submodule is to rebuild the node tree from the annotated node tree,
// and getting rid of eliminated tables along the way
//
#region Main Rebuilding Methods
///
/// Return the result of join elimination
///
/// the transformed node tree
private Node BuildNodeTree()
{
// Has anything changed? If not, then simply return the original tree.
if (!m_modifiedGraph)
{
return m_root.Node;
}
// Generate transitive closure for all Vars in the varMap
VarMap newVarMap = new VarMap();
foreach (KeyValuePair kv in m_varMap)
{
Var newVar1 = kv.Value;
Var newVar2;
while (m_varMap.TryGetValue(newVar1, out newVar2))
{
PlanCompiler.Assert(newVar2 != null, "null var mapping?");
newVar1 = newVar2;
}
newVarMap[kv.Key] = newVar1;
}
m_varMap = newVarMap;
// Otherwise build the tree
Dictionary predicates;
Node newNode = RebuildNodeTree(m_root, out predicates);
PlanCompiler.Assert(newNode != null, "Resulting node tree is null");
PlanCompiler.Assert(predicates == null || predicates.Count == 0, "Leaking predicates?");
return newNode;
}
///
/// Build a filter node (if necessary) to prune out null values for the specified
/// columns
///
///
///
///
private Node BuildFilterForNullableColumns(Node inputNode, VarVec nonNullableColumns)
{
if (nonNullableColumns == null)
{
return inputNode;
}
VarVec remappedVarVec = nonNullableColumns.Remap(m_varMap);
if (remappedVarVec.IsEmpty)
{
return inputNode;
}
Node predNode = null;
foreach (Var v in remappedVarVec)
{
Node varRefNode = m_command.CreateNode(m_command.CreateVarRefOp(v));
Node isNotNullNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.IsNull), varRefNode);
isNotNullNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.Not), isNotNullNode);
if (predNode == null)
{
predNode = isNotNullNode;
}
else
{
predNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
predNode, isNotNullNode);
}
}
PlanCompiler.Assert(predNode != null, "Null predicate?");
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), inputNode, predNode);
return filterNode;
}
///
/// Adds a filter node (if necessary) on top of the input node.
/// Returns the input node, if the filter predicate is null - otherwise, adds a
/// a new filter node above the input
///
/// the input node
/// the filter predicate
///
private Node BuildFilterNode(Node inputNode, Node predicateNode)
{
if (predicateNode == null)
{
return inputNode;
}
else
{
return m_command.CreateNode(m_command.CreateFilterOp(), inputNode, predicateNode);
}
}
///
/// Rebuilds the predicate for a join node and caculates the minimum location id at which it can be specified.
/// The predicate is an AND of the equijoin conditions and the "otherPredicate".
///
/// We first remap all columns in the equijoin predicates - if a column pair
/// resolves to the same column, then we skip that pair.
///
/// The minimum location id at which a predicate can be specified is the minimum location id that is
/// still at or above the minimum location id of all participating vars. By default, it is the location id
/// of the input join node. However, because a table producing a participating var may be moved or
/// replaced by another table, the rebuilt predicate may need to be specified at higher location id.
///
/// the current join node
/// the minimum location id (AugumentedNode.Id) at which this predicate can be specified
/// the rebuilt predicate
private Node RebuildPredicate(AugmentedJoinNode joinNode, out int minLocationId)
{
//
// It is safe to initilaze the output location id to the location id of the joinNode. The nodes at lower
// location ids have already been processed, thus even if the least common ancestor of all participating
// vars is lower than the location id of the joinNode, the rebuilt predicate would not be propagated
// to nodes at lower location ids.
//
minLocationId = joinNode.Id;
//Get the minimum location Id at which the other predicate can be specified.
if (joinNode.OtherPredicate != null)
{
foreach (Var var in joinNode.OtherPredicate.GetNodeInfo(this.m_command).ExternalReferences)
{
Var newVar;
if (!m_varMap.TryGetValue(var, out newVar))
{
newVar = var;
}
minLocationId = GetLeastCommonAncestor(minLocationId, GetLocationId(newVar, minLocationId));
}
}
Node predicateNode = joinNode.OtherPredicate;
for (int i = 0; i < joinNode.LeftVars.Count; i++)
{
Var newLeftVar;
Var newRightVar;
if (!m_varMap.TryGetValue(joinNode.LeftVars[i], out newLeftVar))
{
newLeftVar = joinNode.LeftVars[i];
}
if (!m_varMap.TryGetValue(joinNode.RightVars[i], out newRightVar))
{
newRightVar = joinNode.RightVars[i];
}
if (newLeftVar.Equals(newRightVar))
{
continue;
}
minLocationId = GetLeastCommonAncestor(minLocationId, GetLocationId(newLeftVar, minLocationId));
minLocationId = GetLeastCommonAncestor(minLocationId, GetLocationId(newRightVar, minLocationId));
Node leftVarNode = m_command.CreateNode(m_command.CreateVarRefOp(newLeftVar));
Node rightVarNode = m_command.CreateNode(m_command.CreateVarRefOp(newRightVar));
Node equalsNode = m_command.CreateNode(m_command.CreateComparisonOp(OpType.EQ),
leftVarNode, rightVarNode);
if (predicateNode != null)
{
predicateNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
equalsNode, predicateNode);
}
else
{
predicateNode = equalsNode;
}
}
return predicateNode;
}
///
/// Rebuilds a crossjoin node tree. We visit each child of the cross join, and get
/// back a list of nodes. If the list of nodes has
/// 0 children - we return null
/// 1 child - we return the single child
/// otherwise - we build a new crossjoin op with all the children
///
/// the crossjoin node
/// new node tree
private Node RebuildNodeTreeForCrossJoins(AugmentedJoinNode joinNode)
{
List newChildren = new List();
foreach (AugmentedNode chi in joinNode.Children)
{
Dictionary predicates;
newChildren.Add(RebuildNodeTree(chi, out predicates));
PlanCompiler.Assert(predicates == null || predicates.Count == 0, "Leaking predicates");
}
if (newChildren.Count == 0)
{
return null;
}
else if (newChildren.Count == 1)
{
return newChildren[0];
}
else
{
Node newJoinNode = m_command.CreateNode(m_command.CreateCrossJoinOp(), newChildren);
m_processedNodes[newJoinNode] = newJoinNode;
return newJoinNode;
}
}
///
/// Rebuilds the node tree for a join.
/// For crossjoins, we delegate to the function above. For other cases, we first
/// invoke this function recursively on the left and the right inputs.
///
///
/// the annotated join node tree
/// A dictionary of output predicates that should be included in ancesstor joins
/// along with the minimum location id at which they can be specified
/// rebuilt tree
private Node RebuildNodeTree(AugmentedJoinNode joinNode, out Dictionary predicates)
{
//
// Handle the simple cases first - cross joins
//
if (joinNode.Node.Op.OpType == OpType.CrossJoin)
{
predicates = null;
return RebuildNodeTreeForCrossJoins(joinNode);
}
Dictionary leftPredicates;
Dictionary rightPredicates;
Node leftNode = RebuildNodeTree(joinNode.Children[0], out leftPredicates);
Node rightNode = RebuildNodeTree(joinNode.Children[1], out rightPredicates);
int localPredicateMinLocationId;
Node localPredicateNode;
// The special case first, when we may 'eat' the local predicate
if (leftNode != null && rightNode == null && joinNode.Node.Op.OpType == OpType.LeftOuterJoin)
{
// Ignore the local predicate
// Is this correct always? What kind of assertions can we make here?
localPredicateMinLocationId = joinNode.Id;
localPredicateNode = null;
}
else
{
localPredicateNode = RebuildPredicate(joinNode, out localPredicateMinLocationId);
}
localPredicateNode = CombinePredicateNodes(joinNode.Id, localPredicateNode, localPredicateMinLocationId, leftPredicates, rightPredicates, out predicates);
if (leftNode == null && rightNode == null)
{
if (localPredicateNode == null)
{
return null;
}
else
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
return BuildFilterNode(singleRowTableNode, localPredicateNode);
}
}
else if (leftNode == null)
{
return BuildFilterNode(rightNode, localPredicateNode);
}
else if (rightNode == null)
{
return BuildFilterNode(leftNode, localPredicateNode);
}
else
{
if (localPredicateNode == null)
{
localPredicateNode = m_command.CreateNode(m_command.CreateTrueOp());
}
Node newJoinNode = m_command.CreateNode(joinNode.Node.Op,
leftNode, rightNode, localPredicateNode);
m_processedNodes[newJoinNode] = newJoinNode;
return newJoinNode;
}
}
///
/// Rebuild the node tree for a TableNode.
///
/// - Keep following the ReplacementTable links until we get to a node that
/// is either null, or has a "false" value for the IsEliminated property
/// - If the result is null, then simply return null
/// - If the tableNode we ended up with has already been "placed" in the resulting
/// node tree, then return null again
/// - If the tableNode has a set of non-nullable columns, then build a filterNode
/// above the ScanTable node (pruning out null values); otherwise, simply return
/// the ScanTable node
///
/// the "augmented" tableNode
/// rebuilt node tree for this node
private Node RebuildNodeTree(AugmentedTableNode tableNode)
{
AugmentedTableNode replacementNode = tableNode;
//
// If this table has already been moved - nothing further to do.
//
if (tableNode.IsMoved)
{
return null;
}
//
// Identify the replacement table for this node
//
while (replacementNode.IsEliminated)
{
replacementNode = replacementNode.ReplacementTable;
if (replacementNode == null)
{
return null;
}
}
//
// Check to see if the replacement node has already been put
// in place in the node tree (possibly as part of eliminating some other join).
// In that case, we don't need to do anything further - simply return null
//
if (replacementNode.NewLocationId < tableNode.Id)
{
return null;
}
//
// ok: so we now have a replacement node that must be used in place
// of the current table. Check to see if the replacement node has any
// columns that would require nulls to be pruned out
//
Node filterNode = BuildFilterForNullableColumns(replacementNode.Node, replacementNode.NullableColumns);
return filterNode;
}
///
/// Rebuilds the node tree from the annotated node tree. This function is
/// simply a dispatcher
/// ScanTable - call RebuildNodeTree for ScanTable
/// Join - call RebuildNodeTree for joinOp
/// Anything else - return the underlying node
///
/// annotated node tree
/// the output predicate that should be included in the parent join
/// the rebuilt node tree
private Node RebuildNodeTree(AugmentedNode augmentedNode, out Dictionary predicates)
{
switch (augmentedNode.Node.Op.OpType)
{
case OpType.ScanTable:
predicates = null;
return RebuildNodeTree((AugmentedTableNode)augmentedNode);
case OpType.CrossJoin:
case OpType.LeftOuterJoin:
case OpType.InnerJoin:
case OpType.FullOuterJoin:
return RebuildNodeTree((AugmentedJoinNode)augmentedNode, out predicates);
default:
predicates = null;
return augmentedNode.Node;
}
}
#endregion
#region Helper Methods for Rebuilding the Node Tree
///
/// Helper method for RebuildNodeTree.
/// Given predicate nodes and the minimum location ids at which they can be specified, it creates:
/// 1. A single predicate AND-ing all input predicates with a minimum location id that is less or equal to the given targetNodeId.
/// 2. A dictionary of all other input predicates and their target minimum location ids.
///
/// The location id of the resulting predicate
/// A predicate
/// The location id for the localPredicateNode
/// A dictionary of predicates and the minimum location id at which they can be specified
/// A dictionary of predicates and the minimum location id at which they can be specified
/// An output dictionary of predicates and the minimum location id at which they can be specified
/// that includes all input predicates with minimum location id greater then targetNodeId
/// A single predicate "AND"-ing all input predicates with a minimum location id that is less or equal to the tiven targetNodeId.
private Node CombinePredicateNodes(int targetNodeId, Node localPredicateNode, int localPredicateMinLocationId, Dictionary leftPredicates, Dictionary rightPredicates, out Dictionary outPredicates)
{
Node result = null;
outPredicates = new Dictionary();
if (localPredicateNode != null)
{
result = ClassifyPredicate(targetNodeId, localPredicateNode, localPredicateMinLocationId, result, outPredicates);
}
if (leftPredicates != null)
{
foreach (KeyValuePair predicatePair in leftPredicates)
{
result = ClassifyPredicate(targetNodeId, predicatePair.Key, predicatePair.Value, result, outPredicates);
}
}
if (rightPredicates != null)
{
foreach (KeyValuePair predicatePair in rightPredicates)
{
result = ClassifyPredicate(targetNodeId, predicatePair.Key, predicatePair.Value, result, outPredicates);
}
}
return result;
}
///
/// Helper method for
/// If the predicateMinimuLocationId is less or equal to the target location id of the current result, it is AND-ed with the
/// current result, otherwise it is included in the list of predicates that need to be propagated up (outPredicates)
///
///
///
///
///
///
///
private Node ClassifyPredicate(int targetNodeId, Node predicateNode, int predicateMinLocationId, Node result, Dictionary outPredicates)
{
if (targetNodeId >= predicateMinLocationId)
{
result = CombinePredicates(result, predicateNode);
}
else
{
outPredicates.Add(predicateNode, predicateMinLocationId);
}
return result;
}
///
/// Combines two predicates into one by AND-ing them.
///
///
///
///
private Node CombinePredicates(Node node1, Node node2)
{
if (node1 == null)
{
return node2;
}
if (node2 == null)
{
return node1;
}
return m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
node1, node2);
}
///
/// Get the location id of the AugumentedTableNode at which the given var is defined.
/// If the var is not in th m_varToDefiningNodeMap, then it return the input defaultLocationId
///
///
///
///
private int GetLocationId(Var var, int defaultLocationId)
{
AugmentedTableNode node;
if (m_varToDefiningNodeMap.TryGetValue(var, out node))
{
if (node.IsMoved)
{
return node.NewLocationId;
}
return node.Id;
}
return defaultLocationId;
}
///
/// Gets the location id of least common ancestor for two nodes in the tree given their location ids
///
///
///
///
private int GetLeastCommonAncestor(int nodeId1, int nodeId2)
{
if (nodeId1 == nodeId2)
{
return nodeId1;
}
AugmentedNode currentNode = m_root;
AugmentedNode child1Parent = currentNode;
AugmentedNode child2Parent = currentNode;
while (child1Parent == child2Parent)
{
currentNode = child1Parent;
if (currentNode.Id == nodeId1 || currentNode.Id == nodeId2)
{
return currentNode.Id;
}
child1Parent = PickSubtree(nodeId1, currentNode);
child2Parent = PickSubtree(nodeId2, currentNode);
}
return currentNode.Id;
}
///
/// Helper method for
/// Given a root node pick its immediate child to which the node identifed with the given nodeId bellongs.
///
///
///
///
/// The immediate child of the given root that is root of the subree that
/// contains the node with the given nodeId.
///
private static AugmentedNode PickSubtree(int nodeId, AugmentedNode root)
{
AugmentedNode subree = root.Children[0];
int i = 1;
while ((subree.Id < nodeId) && (i < root.Children.Count))
{
subree = root.Children[i];
i++;
}
return subree;
}
#endregion
#endregion
#endregion
}
#endregion
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.