JoinGraph.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / JoinGraph.cs / 1610115 / JoinGraph.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

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.Linq; 

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; 
        private readonly List m_joinEdges = new List();
        #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; }
        } 

        ///  
        /// List of directed edges in which: 
        ///     - If this is an AugmentedTableNode, it is the "left" table
        ///     - If it is an AugumentedJoinNode, it is the join on which the edge is based 
        /// 
        internal List JoinEdges
        {
            get { return m_joinEdges; } 
        }
        #endregion 
    } 

    ///  
    /// Additional information for a "Table" node
    /// 
    internal sealed class AugmentedTableNode : AugmentedNode
    { 
        #region private state
        private int m_lastVisibleId; 
        private Table m_table; 

        // 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_lastVisibleId = id;
            m_replacementTable = this; 
            m_newLocationId = id;
        } 
        #endregion 

        #region public properties 
        /// 
        /// The Table
        /// 
        internal Table Table { get { return m_table; } } 

        ///  
        /// 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; } set { m_joinKind = value; } } 

        /// 
        /// 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)
        {
            //Turn left outer joins into inner joins when possible 
            TryTurnLeftOuterJoinsIntoInnerJoins();
 
            // 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);
            joinNode.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.
        /// 
        /// The transitive edge is created if all of the following conditions hold:
        /// 1. edge1 and edge2 are of the same join kind 
        /// 2. If edge1 and edge2 are Left Outer Joins, then 
        ///     a. both edges represent joins on the same columns, and
        ///     b. at least one of the edges represents a self join 
        /// 3. For inner joins:
        ///     The intersection of the columns on which are the joins represented
        ///     by edge1 and edge2 is non-empty, the transitive edge is created to represent
        ///     a join on that intersection. 
        /// 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.
            if (edge1.JoinKind != edge2.JoinKind)
            {
                return false; 
            }
 
            // Allow left-outer-joins only for self-joins 
            if (edge1.JoinKind == JoinKind.LeftOuter &&
                (edge1.Left != edge1.Right || edge2.Left != edge2.Right)) 
            {
                    return false;
            }
 
            // For LeftOuterJoin, the joins must be on the same columns.
            // Prerequisite for that is they have the same number of vars. 
            if (edge1.JoinKind == JoinKind.LeftOuter && 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; 
                }
            }

            // 
            // Find the subset of columns that are common between the edges
            // For Left Outer Join, that should be all columns from the edges. 
            // The algorithm for finding the common columns is based on 
            // sort - merge join. In particular, for each edge we create an ordered key-value pair list
            // where the key value pair has the var coming from the inner (shared table)as a key 
            // and the corresponding var from the other table

            IEnumerable> orderedEdge1Vars = CreateOrderedKeyValueList(edge1.RightVars, edge1.LeftVars);
            IEnumerable> orderedEdge2Vars = CreateOrderedKeyValueList(edge2.LeftVars, edge2.RightVars); 

            IEnumerator> orderedEdge1VarsEnumerator = orderedEdge1Vars.GetEnumerator(); 
            IEnumerator> orderedEdge2VarsEnumerator = orderedEdge2Vars.GetEnumerator(); 

            List leftVars = new List(); 
            List rightVars = new List();

            bool hasMore = orderedEdge1VarsEnumerator.MoveNext() && orderedEdge2VarsEnumerator.MoveNext();
            while (hasMore) 
            {
                if (orderedEdge1VarsEnumerator.Current.Key == orderedEdge2VarsEnumerator.Current.Key) 
                { 
                    leftVars.Add(orderedEdge1VarsEnumerator.Current.Value);
                    rightVars.Add(orderedEdge2VarsEnumerator.Current.Value); 
                    hasMore = orderedEdge1VarsEnumerator.MoveNext() &&
                    orderedEdge2VarsEnumerator.MoveNext();
                }
                else if (edge1.JoinKind == JoinKind.LeftOuter) 
                {
                    return false; 
                } 
                else if (orderedEdge1VarsEnumerator.Current.Key.Id > orderedEdge2VarsEnumerator.Current.Key.Id)
                { 
                    hasMore = orderedEdge2VarsEnumerator.MoveNext();
                }
                else
                { 
                    hasMore = orderedEdge1VarsEnumerator.MoveNext();
                } 
            } 

 
            // 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;
        } 

        ///  
        /// Given a list of key vars a list of corresponding value vars, creates a list 
        /// of key-value pairs that is ordered based on the keys
        ///  
        /// 
        /// 
        /// 
        private static IEnumerable> CreateOrderedKeyValueList(List keyVars, List valueVars) 
        {
            List> edgeVars = new List>(keyVars.Count); 
            for (int i = 0; i < keyVars.Count; i++) 
            {
                edgeVars.Add(new KeyValuePair(keyVars[i], valueVars[i])); 
            }
           return edgeVars.OrderBy(kv => kv.Key.Id);
        }
 
        /// 
        /// Try to turn left outer joins into inner joins 
        /// 
        /// Turn an augmented join node that represents a Left Outer Join into an Inner join
        /// if all its edges are candidates to be turned into an Inner Join 
        ///
        /// An edge representing A LOJ B is a candidate to be turned into an inner join if
        /// one of the following conditions hold:
        /// 
        /// 1. There is a foreign key constraint between B and A, the join is on the constraint,
        /// and the joined columns in B are non-nullable, or 
        /// 
        /// 2. There is a foreign key constraint between A and B, the join is on the constraint,
        /// and the child multiplicity is One. However, this scenario cannot be specified in the ssdl, 
        /// thus this case has not be implemented
        /// 
        private void TryTurnLeftOuterJoinsIntoInnerJoins()
        { 
            foreach (AugmentedJoinNode augmentedJoinNode in m_vertexes.OfType().Where(j => j.Node.Op.OpType == OpType.LeftOuterJoin && j.JoinEdges.Count > 0))
            { 
                if (augmentedJoinNode.Children.All(c => c is AugmentedTableNode) && 
                    CanAllJoinEdgesBeTurnedIntoInnerJoins(augmentedJoinNode.JoinEdges))
                { 
                    augmentedJoinNode.Node.Op = m_command.CreateInnerJoinOp();
                    m_modifiedGraph = true;
                    List newJoinEdges = new List(augmentedJoinNode.JoinEdges.Count);
                    foreach (JoinEdge joinEdge in augmentedJoinNode.JoinEdges) 
                    {
                        joinEdge.JoinKind = JoinKind.Inner; 
                        if (!ContainsJoinEdgeForTable(joinEdge.Right.JoinEdges, joinEdge.Left.Table)) 
                        {
                            //create the mirroring join edge 
                            JoinEdge newJoinEdge = JoinEdge.CreateJoinEdge(joinEdge.Right, joinEdge.Left, augmentedJoinNode, joinEdge.RightVars[0], joinEdge.LeftVars[0]);
                            joinEdge.Right.JoinEdges.Add(newJoinEdge);
                            newJoinEdges.Add(newJoinEdge);
                            for (int i = 1; i < joinEdge.LeftVars.Count; i++) 
                            {
                                newJoinEdge.AddCondition(augmentedJoinNode, joinEdge.RightVars[i], joinEdge.LeftVars[i]); 
                            } 
                        }
                    } 
                    augmentedJoinNode.JoinEdges.AddRange(newJoinEdges);
                }
            }
        } 

        ///  
        /// Does the set of given joinEdges contain a join edge to a given table 
        /// 
        ///  
        /// 
        /// 
        private bool ContainsJoinEdgeForTable(IEnumerable joinEdges, Table table)
        { 
            foreach (JoinEdge joinEdge in joinEdges)
            { 
                if (joinEdge.Right.Table.Equals(table)) 
                {
                    return true; 
                }
            }
            return false;
        } 

        ///  
        /// Determines whether each of the given joinEdges can be turned into an inner join 
        /// NOTE: Due to how we create join edges, currenlty there can only be one join edge in this group
        /// See  for details. 
        /// 
        /// 
        /// 
        private bool CanAllJoinEdgesBeTurnedIntoInnerJoins(IEnumerable joinEdges) 
        {
            foreach (JoinEdge joinEdge in joinEdges) 
            { 
                if (!CanJoinEdgeBeTurnedIntoInnerJoin(joinEdge))
                { 
                    return false;
                }
            }
            return true; 
        }
 
        ///  
        /// A LOJ B edge can be turned into an inner join if:
        /// 
        /// (1) There is a foreign key constraint between B and A,
        ///     the join is on the constraint, and the joined columns in B are non-nullable, or
        ///
        /// (2) There is a foreign key constraint between A and B, the join is on the constraint, 
        ///     and the child multiplicity is One. However, this scenario cannot be specified in the ssdl,
        ///     thus this case has not be implemented 
        ///  
        /// 
        ///  
        private bool CanJoinEdgeBeTurnedIntoInnerJoin(JoinEdge joinEdge)
        {
            List fkConstraints;
 
            if (m_constraintManager.IsParentChildRelationship(joinEdge.Right.Table.TableMetadata.Extent, joinEdge.Left.Table.TableMetadata.Extent, out fkConstraints))
            { 
                PlanCompiler.Assert(fkConstraints != null && fkConstraints.Count > 0, "invalid fk constraints?"); 
                foreach (ForeignKeyConstraint fkConstraint in fkConstraints)
                { 
                    IList columnVars;
                    if (IsJoinOnFkConstraint(fkConstraint, joinEdge.RightVars, joinEdge.LeftVars, out columnVars))
                    {
                        if (fkConstraint.ParentKeys.Count == joinEdge.RightVars.Count && 
                            columnVars.Where(v => v.ColumnMetadata.IsNullable).Count() == 0)
                        { 
                            return true; 
                        }
                    } 
                }
            }
            return false;
        } 

        ///  
        /// 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 CanBeEliminatedBasedOnLojParticipation(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 first creates groups of join edges such that all tables 
        /// in a group: 
        ///     1. are joined to the center (X) on the same columns
        ///     2. are of the same join kind 
        ///     3. are joined on all key columns of table A
        ///     4. if the join type is Left Outer Join, they are not joined on any other columns
        ///
        /// For each group, we then identify the table with the 
        /// smallest "Id", and choose that to replace all the other tables from that group
        /// 
        ///  
        /// list of join edges
        private void EliminateStarSelfJoin(List joinEdges) 
        {
            List> compatibleGroups = new List>();

            foreach (JoinEdge joinEdge in joinEdges) 
            {
                // Try to put the join edge in some of the existing groups 
                bool matched = false; 
                foreach (List joinEdgeList in compatibleGroups)
                { 
                    if (AreMatchingForStarSelfJoinElimination(joinEdgeList[0], joinEdge))
                    {
                        joinEdgeList.Add(joinEdge);
                        matched = true; 
                        break;
                    } 
                } 

                // If the join edge could not be part of any of the existing groups, 
                // see whether it quailifes for leading a new group
                if (!matched && QualifiesForStarSelfJoinGroup(joinEdge))
                {
                    List newList = new List(); 
                    newList.Add(joinEdge);
                    compatibleGroups.Add(newList); 
                } 
            }
 
            foreach (List joinList in compatibleGroups.Where(l => l.Count > 1))
            {
                // Identify the table with the smallest id, and use that as the candidate
                JoinEdge smallestEdge = joinList[0]; 
                foreach (JoinEdge joinEdge in joinList)
                { 
                    if (smallestEdge.Right.Id > joinEdge.Right.Id) 
                    {
                        smallestEdge = joinEdge; 
                    }
                }

                // Now walk through all the edges in the group, and mark all the tables as eliminated 
                foreach (JoinEdge joinEdge in joinList)
                { 
                    if (joinEdge == smallestEdge) 
                    {
                        continue; 
                    }
                    if (CanBeEliminatedBasedOnLojParticipation(joinEdge.Right, smallestEdge.Right))
                    {
                        EliminateSelfJoinedTable(joinEdge.Right, smallestEdge.Right); 
                    }
                } 
            } 
        }
 
        /// 
        /// Two edges match for star self join elimination if:
        ///     1. are joined to the center (X) on the same columns
        ///     2. are of the same join kind 
        /// 
        ///  
        ///  
        /// 
        private bool AreMatchingForStarSelfJoinElimination(JoinEdge edge1, JoinEdge edge2) 
        {
            // In order for the join edges to be compatible thay have to
            // represent joins on the same number of columns and of the same join kinds.
            if (edge2.LeftVars.Count != edge1.LeftVars.Count || 
                edge2.JoinKind != edge1.JoinKind)
            { 
                return false; 
            }
 
            // Now make sure that we're joining on the same columns
            for (int j = 0; j < edge2.LeftVars.Count; j++)
            {
                // Check for reference equality on the left-table Vars. Check for 
                // name equality on the right table vars
                if (!edge2.LeftVars[j].Equals(edge1.LeftVars[j]) || 
                    !edge2.RightVars[j].ColumnMetadata.Name.Equals(edge1.RightVars[j].ColumnMetadata.Name)) 
                {
                    return false; 
                }
            }
            return true;
        } 

        ///  
        /// A join edge qualifies for starting a group for star self join elimination if: 
        ///     1. the join is on all key columns of the right table,
        ///     2. if the join type is Left Outer Join, the join is on no columns 
        ///     other than the keys of the right table.
        ///     NOTE:  The second limitation is really arbitrary, to should be possible
        ///     to also allow other conditions
        ///  
        /// 
        ///  
        private bool QualifiesForStarSelfJoinGroup(JoinEdge joinEdge) 
        {
            // 
            // Now make sure that all key columns of the right table are used
            //
            VarVec keyVars = m_command.CreateVarVec(joinEdge.Right.Table.Keys);
            foreach (Var v in joinEdge.RightVars) 
            {
                // Make sure that no other column is referenced in case of an outer join 
                if (joinEdge.JoinKind == JoinKind.LeftOuter && !keyVars.IsSet(v)) 
                {
                    return false; 
                }
                keyVars.Clear(v);
            }
            if (!keyVars.IsEmpty) 
            {
                return false; 
            } 
            return true;
        } 

        /// 
        /// 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 (!CanBeEliminatedBasedOnLojParticipation(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 left table
        ///  
        /// 
        private void EliminateLeftTable(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 right table
        /// 
        /// 
        private void EliminateRightTable(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 right table of the given join edge referenced
        /// elsewhere (outside the join condition) 
        ///  
        /// 
        ///  
        private bool RightTableHasKeyReferences(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;
            } 

            IList childColumnVars;
            if (!IsJoinOnFkConstraint(fkConstraint, joinEdge.LeftVars, joinEdge.RightVars, out childColumnVars))
            { 
                return false;
            } 
 
            //
            // For inner joins, try and eliminate the parent table 
            //
            if (joinEdge.JoinKind == JoinKind.Inner)
            {
                if (HasNonKeyReferences(joinEdge.Left.Table)) 
                {
                    return false; 
                } 

                if (!CanBeEliminatedBasedOnLojParticipation(joinEdge.Right, joinEdge.Left)) 
                {
                    return false;
                }
 
                // Mark the parent (left-side) table as "eliminated"
                EliminateLeftTable(joinEdge); 
                return true; 
            }
            // 
            // For left outer joins, try and eliminate the child table
            //
            else
            { 
                // SQLBUDT #512375: For the 1 - 0..1 we also verify that the child's columns are not
                // referenced outside the join condition, thus passing true for allowRefsForJoinedOnFkOnly only 
                // if the multiplicity is 1 - 1 
                return TryEliminateRightTable(joinEdge, fkConstraint.ChildKeys.Count, fkConstraint.ChildMultiplicity == md.RelationshipMultiplicity.One);
            } 
        }

        /// 
        /// Given a ForeignKeyConstraint and lists of vars on which the tables are joined, 
        /// it checks whether the join condition includes (but is not necessarily joined only on)
        /// the foreign key constraint. 
        ///  
        /// 
        ///  
        /// 
        /// 
        /// 
        private static bool IsJoinOnFkConstraint(ForeignKeyConstraint fkConstraint, IList parentVars, IList childVars, out IList childForeignKeyVars) 
        {
            childForeignKeyVars = new List(fkConstraint.ChildKeys.Count); 
            // 
            // 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 parentVars) 
                {
                    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 < parentVars.Count; pos++) 
                {
                    ColumnVar rightVar = childVars[pos]; 
                    if (rightVar.ColumnMetadata.Name.Equals(keyProp))
                    {
                        childForeignKeyVars.Add(rightVar);
                        foundKey = true; 
                        string parentPropertyName;
                        ColumnVar leftVar = parentVars[pos]; 
                        if (!fkConstraint.GetParentProperty(rightVar.ColumnMetadata.Name, out parentPropertyName) || 
                            !parentPropertyName.Equals(leftVar.ColumnMetadata.Name))
                        { 
                            return false;
                        }
                        break;
                    } 
                }
                if (!foundKey) 
                { 
                    return false;
                } 
            }
            return true;
        }
 
        /// 
        /// Try to eliminate the parent table from a 
        ///         child Left Outer Join parent 
        /// join, given a fk constraint
        /// 
        /// More specific:
        ///
        /// P(p1, p2, p3,�) is the parent table, and C(c1, c2, c3, �) is the child table.
        /// Say p1,p2 is the PK of P, and c1,c2 is the FK from C to P 
        ///
        /// SELECT � 
        /// From C LOJ P ON (p1 = c1 and p2 = c2) 
        /// WHERE �
        /// 
        /// If only the keys are used from P, we should but should be carefull about composite keys with nullable foreign key columns.
        /// If a composite foreign key has been defined on columns that allow nulls,
        /// and at least one of the columns, upon the insert or update of a row, is set to null, then the foreign key constraint will be satisfied
        /// on SqlServer. 
        ///
        /// Thus we should do the elimination only if 
        /// 1.	The key is not composite 
        /// 2.	All columns on the child side are non nullable
        ///  
        /// the current join edge
        /// the referential integrity constraint
        /// 
        private bool TryEliminateChildParentJoin(JoinEdge joinEdge, ForeignKeyConstraint fkConstraint) 
        {
            IList childColumnVars; 
            if (!IsJoinOnFkConstraint(fkConstraint, joinEdge.RightVars, joinEdge.LeftVars, out childColumnVars)) 
            {
                return false; 
            }

            //Verify that either the foreign key is:
            //  1. Non composite, or 
            //  2. All columns on the child side are non nullable
            // NOTE: Technically we could also allow the case when only one column on the child side is nullable 
            // and its corresponding column on the parent side is the only column referenced from the parent table. 
            if (childColumnVars.Count > 1 && childColumnVars.Where(v => v.ColumnMetadata.IsNullable).Count() > 0)
            { 
                return false;
            }

            return TryEliminateRightTable(joinEdge, fkConstraint.ParentKeys.Count, true); 
        }
 
        ///  
        /// Helper method to try to eliminate the right table given a join edge.
        /// The right table should be eliminated if: 
        /// 1. It does not have non key references, and
        /// 2. Either its columns are not referenced anywhere outside the join condition or,
        /// if allowRefsForJoinedOnFkOnly is true, the join condition is only on the fk constraint
        /// (which we deduct by only checking the count, since we already checked that the conditions do 
        /// include the fk constraint.
        /// 3. It can be eliminated based on possible participation in a left outer join 
        ///  
        /// 
        ///  
        /// 
        private bool TryEliminateRightTable(JoinEdge joinEdge, int fkConstraintKeyCount, bool allowRefsForJoinedOnFkOnly)
        { 
            if (HasNonKeyReferences(joinEdge.Right.Table))
            { 
                return false; 
            }
 
            if ((!allowRefsForJoinedOnFkOnly || joinEdge.RightVars.Count != fkConstraintKeyCount) && RightTableHasKeyReferences(joinEdge))
            {
                return false;
            } 

            if (!CanBeEliminatedBasedOnLojParticipation(joinEdge.Right, joinEdge.Left)) 
            { 
                return false;
            } 

            // Eliminate the child table
            EliminateRightTable(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)) 
            {
                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; 
                    }
                }
            }
 
            // For LeftOuterJoin we should check for the opportunity to eliminate based on a parent-child
            // relationship in the opposite direction too. For inner joins that should not be an issue 
            // as the opposite join edge would have been generated too. 
            if (joinEdge.JoinKind == JoinKind.LeftOuter)
            { 
                if (m_constraintManager.IsParentChildRelationship(joinEdge.Right.Table.TableMetadata.Extent, joinEdge.Left.Table.TableMetadata.Extent,
                out fkConstraints))
                {
                    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 (TryEliminateChildParentJoin(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 = PlanCompilerUtil.CombinePredicates(equalsNode, predicateNode, m_command); 
                } 
                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 PlanCompilerUtil.CombinePredicates(node1, node2, m_command);
        }

        ///  
        /// 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  [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

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.Linq; 

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; 
        private readonly List m_joinEdges = new List();
        #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; }
        } 

        ///  
        /// List of directed edges in which: 
        ///     - If this is an AugmentedTableNode, it is the "left" table
        ///     - If it is an AugumentedJoinNode, it is the join on which the edge is based 
        /// 
        internal List JoinEdges
        {
            get { return m_joinEdges; } 
        }
        #endregion 
    } 

    ///  
    /// Additional information for a "Table" node
    /// 
    internal sealed class AugmentedTableNode : AugmentedNode
    { 
        #region private state
        private int m_lastVisibleId; 
        private Table m_table; 

        // 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_lastVisibleId = id;
            m_replacementTable = this; 
            m_newLocationId = id;
        } 
        #endregion 

        #region public properties 
        /// 
        /// The Table
        /// 
        internal Table Table { get { return m_table; } } 

        ///  
        /// 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; } set { m_joinKind = value; } } 

        /// 
        /// 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)
        {
            //Turn left outer joins into inner joins when possible 
            TryTurnLeftOuterJoinsIntoInnerJoins();
 
            // 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);
            joinNode.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.
        /// 
        /// The transitive edge is created if all of the following conditions hold:
        /// 1. edge1 and edge2 are of the same join kind 
        /// 2. If edge1 and edge2 are Left Outer Joins, then 
        ///     a. both edges represent joins on the same columns, and
        ///     b. at least one of the edges represents a self join 
        /// 3. For inner joins:
        ///     The intersection of the columns on which are the joins represented
        ///     by edge1 and edge2 is non-empty, the transitive edge is created to represent
        ///     a join on that intersection. 
        /// 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.
            if (edge1.JoinKind != edge2.JoinKind)
            {
                return false; 
            }
 
            // Allow left-outer-joins only for self-joins 
            if (edge1.JoinKind == JoinKind.LeftOuter &&
                (edge1.Left != edge1.Right || edge2.Left != edge2.Right)) 
            {
                    return false;
            }
 
            // For LeftOuterJoin, the joins must be on the same columns.
            // Prerequisite for that is they have the same number of vars. 
            if (edge1.JoinKind == JoinKind.LeftOuter && 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; 
                }
            }

            // 
            // Find the subset of columns that are common between the edges
            // For Left Outer Join, that should be all columns from the edges. 
            // The algorithm for finding the common columns is based on 
            // sort - merge join. In particular, for each edge we create an ordered key-value pair list
            // where the key value pair has the var coming from the inner (shared table)as a key 
            // and the corresponding var from the other table

            IEnumerable> orderedEdge1Vars = CreateOrderedKeyValueList(edge1.RightVars, edge1.LeftVars);
            IEnumerable> orderedEdge2Vars = CreateOrderedKeyValueList(edge2.LeftVars, edge2.RightVars); 

            IEnumerator> orderedEdge1VarsEnumerator = orderedEdge1Vars.GetEnumerator(); 
            IEnumerator> orderedEdge2VarsEnumerator = orderedEdge2Vars.GetEnumerator(); 

            List leftVars = new List(); 
            List rightVars = new List();

            bool hasMore = orderedEdge1VarsEnumerator.MoveNext() && orderedEdge2VarsEnumerator.MoveNext();
            while (hasMore) 
            {
                if (orderedEdge1VarsEnumerator.Current.Key == orderedEdge2VarsEnumerator.Current.Key) 
                { 
                    leftVars.Add(orderedEdge1VarsEnumerator.Current.Value);
                    rightVars.Add(orderedEdge2VarsEnumerator.Current.Value); 
                    hasMore = orderedEdge1VarsEnumerator.MoveNext() &&
                    orderedEdge2VarsEnumerator.MoveNext();
                }
                else if (edge1.JoinKind == JoinKind.LeftOuter) 
                {
                    return false; 
                } 
                else if (orderedEdge1VarsEnumerator.Current.Key.Id > orderedEdge2VarsEnumerator.Current.Key.Id)
                { 
                    hasMore = orderedEdge2VarsEnumerator.MoveNext();
                }
                else
                { 
                    hasMore = orderedEdge1VarsEnumerator.MoveNext();
                } 
            } 

 
            // 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;
        } 

        ///  
        /// Given a list of key vars a list of corresponding value vars, creates a list 
        /// of key-value pairs that is ordered based on the keys
        ///  
        /// 
        /// 
        /// 
        private static IEnumerable> CreateOrderedKeyValueList(List keyVars, List valueVars) 
        {
            List> edgeVars = new List>(keyVars.Count); 
            for (int i = 0; i < keyVars.Count; i++) 
            {
                edgeVars.Add(new KeyValuePair(keyVars[i], valueVars[i])); 
            }
           return edgeVars.OrderBy(kv => kv.Key.Id);
        }
 
        /// 
        /// Try to turn left outer joins into inner joins 
        /// 
        /// Turn an augmented join node that represents a Left Outer Join into an Inner join
        /// if all its edges are candidates to be turned into an Inner Join 
        ///
        /// An edge representing A LOJ B is a candidate to be turned into an inner join if
        /// one of the following conditions hold:
        /// 
        /// 1. There is a foreign key constraint between B and A, the join is on the constraint,
        /// and the joined columns in B are non-nullable, or 
        /// 
        /// 2. There is a foreign key constraint between A and B, the join is on the constraint,
        /// and the child multiplicity is One. However, this scenario cannot be specified in the ssdl, 
        /// thus this case has not be implemented
        /// 
        private void TryTurnLeftOuterJoinsIntoInnerJoins()
        { 
            foreach (AugmentedJoinNode augmentedJoinNode in m_vertexes.OfType().Where(j => j.Node.Op.OpType == OpType.LeftOuterJoin && j.JoinEdges.Count > 0))
            { 
                if (augmentedJoinNode.Children.All(c => c is AugmentedTableNode) && 
                    CanAllJoinEdgesBeTurnedIntoInnerJoins(augmentedJoinNode.JoinEdges))
                { 
                    augmentedJoinNode.Node.Op = m_command.CreateInnerJoinOp();
                    m_modifiedGraph = true;
                    List newJoinEdges = new List(augmentedJoinNode.JoinEdges.Count);
                    foreach (JoinEdge joinEdge in augmentedJoinNode.JoinEdges) 
                    {
                        joinEdge.JoinKind = JoinKind.Inner; 
                        if (!ContainsJoinEdgeForTable(joinEdge.Right.JoinEdges, joinEdge.Left.Table)) 
                        {
                            //create the mirroring join edge 
                            JoinEdge newJoinEdge = JoinEdge.CreateJoinEdge(joinEdge.Right, joinEdge.Left, augmentedJoinNode, joinEdge.RightVars[0], joinEdge.LeftVars[0]);
                            joinEdge.Right.JoinEdges.Add(newJoinEdge);
                            newJoinEdges.Add(newJoinEdge);
                            for (int i = 1; i < joinEdge.LeftVars.Count; i++) 
                            {
                                newJoinEdge.AddCondition(augmentedJoinNode, joinEdge.RightVars[i], joinEdge.LeftVars[i]); 
                            } 
                        }
                    } 
                    augmentedJoinNode.JoinEdges.AddRange(newJoinEdges);
                }
            }
        } 

        ///  
        /// Does the set of given joinEdges contain a join edge to a given table 
        /// 
        ///  
        /// 
        /// 
        private bool ContainsJoinEdgeForTable(IEnumerable joinEdges, Table table)
        { 
            foreach (JoinEdge joinEdge in joinEdges)
            { 
                if (joinEdge.Right.Table.Equals(table)) 
                {
                    return true; 
                }
            }
            return false;
        } 

        ///  
        /// Determines whether each of the given joinEdges can be turned into an inner join 
        /// NOTE: Due to how we create join edges, currenlty there can only be one join edge in this group
        /// See  for details. 
        /// 
        /// 
        /// 
        private bool CanAllJoinEdgesBeTurnedIntoInnerJoins(IEnumerable joinEdges) 
        {
            foreach (JoinEdge joinEdge in joinEdges) 
            { 
                if (!CanJoinEdgeBeTurnedIntoInnerJoin(joinEdge))
                { 
                    return false;
                }
            }
            return true; 
        }
 
        ///  
        /// A LOJ B edge can be turned into an inner join if:
        /// 
        /// (1) There is a foreign key constraint between B and A,
        ///     the join is on the constraint, and the joined columns in B are non-nullable, or
        ///
        /// (2) There is a foreign key constraint between A and B, the join is on the constraint, 
        ///     and the child multiplicity is One. However, this scenario cannot be specified in the ssdl,
        ///     thus this case has not be implemented 
        ///  
        /// 
        ///  
        private bool CanJoinEdgeBeTurnedIntoInnerJoin(JoinEdge joinEdge)
        {
            List fkConstraints;
 
            if (m_constraintManager.IsParentChildRelationship(joinEdge.Right.Table.TableMetadata.Extent, joinEdge.Left.Table.TableMetadata.Extent, out fkConstraints))
            { 
                PlanCompiler.Assert(fkConstraints != null && fkConstraints.Count > 0, "invalid fk constraints?"); 
                foreach (ForeignKeyConstraint fkConstraint in fkConstraints)
                { 
                    IList columnVars;
                    if (IsJoinOnFkConstraint(fkConstraint, joinEdge.RightVars, joinEdge.LeftVars, out columnVars))
                    {
                        if (fkConstraint.ParentKeys.Count == joinEdge.RightVars.Count && 
                            columnVars.Where(v => v.ColumnMetadata.IsNullable).Count() == 0)
                        { 
                            return true; 
                        }
                    } 
                }
            }
            return false;
        } 

        ///  
        /// 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 CanBeEliminatedBasedOnLojParticipation(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 first creates groups of join edges such that all tables 
        /// in a group: 
        ///     1. are joined to the center (X) on the same columns
        ///     2. are of the same join kind 
        ///     3. are joined on all key columns of table A
        ///     4. if the join type is Left Outer Join, they are not joined on any other columns
        ///
        /// For each group, we then identify the table with the 
        /// smallest "Id", and choose that to replace all the other tables from that group
        /// 
        ///  
        /// list of join edges
        private void EliminateStarSelfJoin(List joinEdges) 
        {
            List> compatibleGroups = new List>();

            foreach (JoinEdge joinEdge in joinEdges) 
            {
                // Try to put the join edge in some of the existing groups 
                bool matched = false; 
                foreach (List joinEdgeList in compatibleGroups)
                { 
                    if (AreMatchingForStarSelfJoinElimination(joinEdgeList[0], joinEdge))
                    {
                        joinEdgeList.Add(joinEdge);
                        matched = true; 
                        break;
                    } 
                } 

                // If the join edge could not be part of any of the existing groups, 
                // see whether it quailifes for leading a new group
                if (!matched && QualifiesForStarSelfJoinGroup(joinEdge))
                {
                    List newList = new List(); 
                    newList.Add(joinEdge);
                    compatibleGroups.Add(newList); 
                } 
            }
 
            foreach (List joinList in compatibleGroups.Where(l => l.Count > 1))
            {
                // Identify the table with the smallest id, and use that as the candidate
                JoinEdge smallestEdge = joinList[0]; 
                foreach (JoinEdge joinEdge in joinList)
                { 
                    if (smallestEdge.Right.Id > joinEdge.Right.Id) 
                    {
                        smallestEdge = joinEdge; 
                    }
                }

                // Now walk through all the edges in the group, and mark all the tables as eliminated 
                foreach (JoinEdge joinEdge in joinList)
                { 
                    if (joinEdge == smallestEdge) 
                    {
                        continue; 
                    }
                    if (CanBeEliminatedBasedOnLojParticipation(joinEdge.Right, smallestEdge.Right))
                    {
                        EliminateSelfJoinedTable(joinEdge.Right, smallestEdge.Right); 
                    }
                } 
            } 
        }
 
        /// 
        /// Two edges match for star self join elimination if:
        ///     1. are joined to the center (X) on the same columns
        ///     2. are of the same join kind 
        /// 
        ///  
        ///  
        /// 
        private bool AreMatchingForStarSelfJoinElimination(JoinEdge edge1, JoinEdge edge2) 
        {
            // In order for the join edges to be compatible thay have to
            // represent joins on the same number of columns and of the same join kinds.
            if (edge2.LeftVars.Count != edge1.LeftVars.Count || 
                edge2.JoinKind != edge1.JoinKind)
            { 
                return false; 
            }
 
            // Now make sure that we're joining on the same columns
            for (int j = 0; j < edge2.LeftVars.Count; j++)
            {
                // Check for reference equality on the left-table Vars. Check for 
                // name equality on the right table vars
                if (!edge2.LeftVars[j].Equals(edge1.LeftVars[j]) || 
                    !edge2.RightVars[j].ColumnMetadata.Name.Equals(edge1.RightVars[j].ColumnMetadata.Name)) 
                {
                    return false; 
                }
            }
            return true;
        } 

        ///  
        /// A join edge qualifies for starting a group for star self join elimination if: 
        ///     1. the join is on all key columns of the right table,
        ///     2. if the join type is Left Outer Join, the join is on no columns 
        ///     other than the keys of the right table.
        ///     NOTE:  The second limitation is really arbitrary, to should be possible
        ///     to also allow other conditions
        ///  
        /// 
        ///  
        private bool QualifiesForStarSelfJoinGroup(JoinEdge joinEdge) 
        {
            // 
            // Now make sure that all key columns of the right table are used
            //
            VarVec keyVars = m_command.CreateVarVec(joinEdge.Right.Table.Keys);
            foreach (Var v in joinEdge.RightVars) 
            {
                // Make sure that no other column is referenced in case of an outer join 
                if (joinEdge.JoinKind == JoinKind.LeftOuter && !keyVars.IsSet(v)) 
                {
                    return false; 
                }
                keyVars.Clear(v);
            }
            if (!keyVars.IsEmpty) 
            {
                return false; 
            } 
            return true;
        } 

        /// 
        /// 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 (!CanBeEliminatedBasedOnLojParticipation(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 left table
        ///  
        /// 
        private void EliminateLeftTable(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 right table
        /// 
        /// 
        private void EliminateRightTable(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 right table of the given join edge referenced
        /// elsewhere (outside the join condition) 
        ///  
        /// 
        ///  
        private bool RightTableHasKeyReferences(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;
            } 

            IList childColumnVars;
            if (!IsJoinOnFkConstraint(fkConstraint, joinEdge.LeftVars, joinEdge.RightVars, out childColumnVars))
            { 
                return false;
            } 
 
            //
            // For inner joins, try and eliminate the parent table 
            //
            if (joinEdge.JoinKind == JoinKind.Inner)
            {
                if (HasNonKeyReferences(joinEdge.Left.Table)) 
                {
                    return false; 
                } 

                if (!CanBeEliminatedBasedOnLojParticipation(joinEdge.Right, joinEdge.Left)) 
                {
                    return false;
                }
 
                // Mark the parent (left-side) table as "eliminated"
                EliminateLeftTable(joinEdge); 
                return true; 
            }
            // 
            // For left outer joins, try and eliminate the child table
            //
            else
            { 
                // SQLBUDT #512375: For the 1 - 0..1 we also verify that the child's columns are not
                // referenced outside the join condition, thus passing true for allowRefsForJoinedOnFkOnly only 
                // if the multiplicity is 1 - 1 
                return TryEliminateRightTable(joinEdge, fkConstraint.ChildKeys.Count, fkConstraint.ChildMultiplicity == md.RelationshipMultiplicity.One);
            } 
        }

        /// 
        /// Given a ForeignKeyConstraint and lists of vars on which the tables are joined, 
        /// it checks whether the join condition includes (but is not necessarily joined only on)
        /// the foreign key constraint. 
        ///  
        /// 
        ///  
        /// 
        /// 
        /// 
        private static bool IsJoinOnFkConstraint(ForeignKeyConstraint fkConstraint, IList parentVars, IList childVars, out IList childForeignKeyVars) 
        {
            childForeignKeyVars = new List(fkConstraint.ChildKeys.Count); 
            // 
            // 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 parentVars) 
                {
                    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 < parentVars.Count; pos++) 
                {
                    ColumnVar rightVar = childVars[pos]; 
                    if (rightVar.ColumnMetadata.Name.Equals(keyProp))
                    {
                        childForeignKeyVars.Add(rightVar);
                        foundKey = true; 
                        string parentPropertyName;
                        ColumnVar leftVar = parentVars[pos]; 
                        if (!fkConstraint.GetParentProperty(rightVar.ColumnMetadata.Name, out parentPropertyName) || 
                            !parentPropertyName.Equals(leftVar.ColumnMetadata.Name))
                        { 
                            return false;
                        }
                        break;
                    } 
                }
                if (!foundKey) 
                { 
                    return false;
                } 
            }
            return true;
        }
 
        /// 
        /// Try to eliminate the parent table from a 
        ///         child Left Outer Join parent 
        /// join, given a fk constraint
        /// 
        /// More specific:
        ///
        /// P(p1, p2, p3,�) is the parent table, and C(c1, c2, c3, �) is the child table.
        /// Say p1,p2 is the PK of P, and c1,c2 is the FK from C to P 
        ///
        /// SELECT � 
        /// From C LOJ P ON (p1 = c1 and p2 = c2) 
        /// WHERE �
        /// 
        /// If only the keys are used from P, we should but should be carefull about composite keys with nullable foreign key columns.
        /// If a composite foreign key has been defined on columns that allow nulls,
        /// and at least one of the columns, upon the insert or update of a row, is set to null, then the foreign key constraint will be satisfied
        /// on SqlServer. 
        ///
        /// Thus we should do the elimination only if 
        /// 1.	The key is not composite 
        /// 2.	All columns on the child side are non nullable
        ///  
        /// the current join edge
        /// the referential integrity constraint
        /// 
        private bool TryEliminateChildParentJoin(JoinEdge joinEdge, ForeignKeyConstraint fkConstraint) 
        {
            IList childColumnVars; 
            if (!IsJoinOnFkConstraint(fkConstraint, joinEdge.RightVars, joinEdge.LeftVars, out childColumnVars)) 
            {
                return false; 
            }

            //Verify that either the foreign key is:
            //  1. Non composite, or 
            //  2. All columns on the child side are non nullable
            // NOTE: Technically we could also allow the case when only one column on the child side is nullable 
            // and its corresponding column on the parent side is the only column referenced from the parent table. 
            if (childColumnVars.Count > 1 && childColumnVars.Where(v => v.ColumnMetadata.IsNullable).Count() > 0)
            { 
                return false;
            }

            return TryEliminateRightTable(joinEdge, fkConstraint.ParentKeys.Count, true); 
        }
 
        ///  
        /// Helper method to try to eliminate the right table given a join edge.
        /// The right table should be eliminated if: 
        /// 1. It does not have non key references, and
        /// 2. Either its columns are not referenced anywhere outside the join condition or,
        /// if allowRefsForJoinedOnFkOnly is true, the join condition is only on the fk constraint
        /// (which we deduct by only checking the count, since we already checked that the conditions do 
        /// include the fk constraint.
        /// 3. It can be eliminated based on possible participation in a left outer join 
        ///  
        /// 
        ///  
        /// 
        private bool TryEliminateRightTable(JoinEdge joinEdge, int fkConstraintKeyCount, bool allowRefsForJoinedOnFkOnly)
        { 
            if (HasNonKeyReferences(joinEdge.Right.Table))
            { 
                return false; 
            }
 
            if ((!allowRefsForJoinedOnFkOnly || joinEdge.RightVars.Count != fkConstraintKeyCount) && RightTableHasKeyReferences(joinEdge))
            {
                return false;
            } 

            if (!CanBeEliminatedBasedOnLojParticipation(joinEdge.Right, joinEdge.Left)) 
            { 
                return false;
            } 

            // Eliminate the child table
            EliminateRightTable(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)) 
            {
                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; 
                    }
                }
            }
 
            // For LeftOuterJoin we should check for the opportunity to eliminate based on a parent-child
            // relationship in the opposite direction too. For inner joins that should not be an issue 
            // as the opposite join edge would have been generated too. 
            if (joinEdge.JoinKind == JoinKind.LeftOuter)
            { 
                if (m_constraintManager.IsParentChildRelationship(joinEdge.Right.Table.TableMetadata.Extent, joinEdge.Left.Table.TableMetadata.Extent,
                out fkConstraints))
                {
                    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 (TryEliminateChildParentJoin(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 = PlanCompilerUtil.CombinePredicates(equalsNode, predicateNode, m_command); 
                } 
                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 PlanCompilerUtil.CombinePredicates(node1, node2, m_command);
        }

        ///  
        /// 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.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK