NodeInfo.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Query / InternalTrees / NodeInfo.cs / 3 / NodeInfo.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections.Generic; 
using System.Globalization;
using System.Diagnostics;
using System.Data.Common;
using md=System.Data.Metadata.Edm; 

namespace System.Data.Query.InternalTrees 
{ 
    /// 
    /// The KeySet class encapsulates all information about the keys of a RelOp node in 
    /// the query tree.
    /// A KeyVec is logically a set of vars that uniquely identify the row of the current
    /// RelOp. Some RelOps may have no unique keys - such a state is identified by the
    /// "NoKeys" property 
    /// 
    internal class KeyVec 
    { 
        #region private state
        private VarVec m_keys; 
        private bool m_noKeys;
        #endregion

        #region constructors 
        internal KeyVec(Command itree)
        { 
            m_keys = itree.CreateVarVec(); 
            m_noKeys = true;
        } 
        #endregion

        internal void InitFrom(KeyVec keyset)
        { 
            m_keys.InitFrom(keyset.m_keys);
            m_noKeys = keyset.m_noKeys; 
        } 

        internal void InitFrom(IEnumerable varSet) 
        {
            InitFrom(varSet, false);
        }
 
        internal void InitFrom(IEnumerable varSet, bool ignoreParameters)
        { 
            m_keys.InitFrom(varSet, ignoreParameters); 
            // Bug 434541: An empty set of keys is not the same as "no" keys.
            // Caveat Emptor 
            m_noKeys = false;
        }
        internal void InitFrom(KeyVec left, KeyVec right)
        { 
            if (left.m_noKeys || right.m_noKeys)
            { 
                m_noKeys = true; 
            }
            else 
            {
                m_noKeys = false;
                m_keys.InitFrom(left.m_keys);
                m_keys.Or(right.m_keys); 
            }
        } 
        internal void InitFrom(List keyVecList) 
        {
            m_noKeys = false; 
            m_keys.Clear();
            foreach (KeyVec keyVec in keyVecList)
            {
                if (keyVec.m_noKeys) 
                {
                    m_noKeys = true; 
                    return; 
                }
                m_keys.Or(keyVec.m_keys); 
            }
        }
        internal void Clear()
        { 
            m_noKeys = true;
            m_keys.Clear(); 
        } 

        internal VarVec KeyVars { get { return m_keys; } } 
        internal bool NoKeys { get { return m_noKeys; } set { m_noKeys = value; } }
    }

    ///  
    /// The NodeInfo class represents additional information about a node in the tree.
    /// By default, this includes a set of external references for each node (ie) references 
    /// to Vars that are not defined in the same subtree 
    /// The NodeInfo class also includes a "hashValue" that is a hash value for the entire
    /// subtree rooted at this node 
    /// 
    internal class NodeInfo
    {
        #region private state 
        private VarVec m_externalReferences;
        protected int m_hashValue; // hash value for the node 
        #endregion 

        #region constructors 
        internal NodeInfo(Command cmd)
        {
            m_externalReferences = cmd.CreateVarVec();
        } 
        #endregion
 
        #region public methods 
        /// 
        /// Clear out all information - usually used by a Recompute 
        /// 
        internal virtual void Clear()
        {
            m_externalReferences.Clear(); 
            m_hashValue = 0;
        } 
 
        /// 
        /// All external references from this node 
        /// 
        internal VarVec ExternalReferences
        {
            get { return m_externalReferences; } 
        }
 
        ///  
        /// Get the hash value for this nodeInfo
        ///  
        internal int HashValue
        {
            get { return m_hashValue; }
        } 

        ///  
        /// Compute the hash value for a Vec 
        /// 
        ///  
        /// 
        internal static int GetHashValue(VarVec vec)
        {
            int hashValue = 0; 
            foreach (Var v in vec)
            { 
                hashValue ^= v.GetHashCode(); 
            }
            return hashValue; 
        }

        /// 
        /// Computes the hash value for this node. The hash value is simply the 
        /// local hash value for this node info added with the hash values of the child
        /// nodes 
        ///  
        /// current command
        /// current node 
        internal virtual void ComputeHashValue(Command cmd, Node n)
        {
            m_hashValue = 0;
            foreach (Node chi in n.Children) 
            {
                NodeInfo chiNodeInfo = cmd.GetNodeInfo(chi); 
                m_hashValue ^= chiNodeInfo.HashValue; 
            }
 
            m_hashValue = (m_hashValue << 4) ^ ((int)n.Op.OpType); // include the optype somehow
            // Now compute my local hash value
            m_hashValue = (m_hashValue << 4) ^ GetHashValue(m_externalReferences);
        } 
        #endregion
    } 
 
    /// 
    /// Enum describing row counts 
    /// 
    internal enum RowCount : byte
    {
        ///  
        /// Zero rows
        ///  
        Zero = 0, 

        ///  
        /// One row
        /// 
        One = 1,
 
        /// 
        /// Unbounded (unknown number of rows) 
        ///  
        Unbounded = 2,
    } 

    /// 
    /// An ExtendedNodeInfo class adds additional information to a standard NodeInfo.
    /// This class is usually applicable only to RelOps and PhysicalOps. 
    /// The ExtendedNodeInfo class has in addition to the information maintained by NodeInfo
    /// the following 
    /// - a set of local definitions 
    /// - a set of definitions
    /// - and a set of keys 
    /// 
    internal class ExtendedNodeInfo : NodeInfo
    {
        #region private 
        private VarVec m_localDefinitions;
        private VarVec m_definitions; 
        private KeyVec m_keys; 
        private RowCount m_minRows;
        private RowCount m_maxRows; 
        #endregion

        #region constructors
        internal ExtendedNodeInfo(Command cmd) 
            : base(cmd)
        { 
            m_localDefinitions = cmd.CreateVarVec(); 
            m_definitions = cmd.CreateVarVec();
            m_keys = new KeyVec(cmd); 
            m_minRows = RowCount.Zero;
            m_maxRows = RowCount.Unbounded;
        }
        #endregion 

        #region public methods 
 
        internal override void Clear()
        { 
            base.Clear();
            m_definitions.Clear();
            m_localDefinitions.Clear();
            m_keys.Clear(); 
            m_minRows = RowCount.Zero;
            m_maxRows = RowCount.Unbounded; 
        } 

        ///  
        /// Compute the hash value for this node
        /// 
        /// 
        ///  
        internal override void ComputeHashValue(Command cmd, Node n)
        { 
            base.ComputeHashValue(cmd, n); 
            m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Definitions);
            m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Keys.KeyVars); 
            return;
        }

        ///  
        /// Definitions made specifically by this node
        ///  
        internal VarVec LocalDefinitions { get { return m_localDefinitions; } } 
        /// 
        /// All definitions visible at this node 
        /// 
        internal VarVec Definitions { get { return m_definitions; } }
        /// 
        /// The keys for this node 
        /// 
        internal KeyVec Keys { get { return m_keys; } } 
 
        /// 
        /// Min number of rows returned from this node 
        /// 
        internal RowCount MinRows
        {
            get { return m_minRows; } 
            set { m_minRows = value; ValidateRowCount(); }
        } 
        ///  
        /// Max rows returned from this node
        ///  
        internal RowCount MaxRows
        {
            get { return m_maxRows; }
            set { m_maxRows = value; ValidateRowCount(); } 
        }
 
        ///  
        /// Set the rowcount for this node
        ///  
        /// min rows produced by this node
        /// max rows produced by this node
        internal void SetRowCount(RowCount minRows, RowCount maxRows)
        { 
            m_minRows = minRows;
            m_maxRows = maxRows; 
            ValidateRowCount(); 
        }
 
        /// 
        /// Initialize the rowcounts for this node from the source node
        /// 
        /// nodeinfo of source 
        internal void InitRowCountFrom(ExtendedNodeInfo source)
        { 
            m_minRows = source.m_minRows; 
            m_maxRows = source.m_maxRows;
        } 

        #endregion

        #region private methods 
        private void ValidateRowCount()
        { 
            Debug.Assert(m_maxRows >= m_minRows, "MaxRows less than MinRows?"); 
        }
        #endregion 
    }

    /// 
    /// The NodeInfoVisitor is a simple class (ab)using the Visitor pattern to define 
    /// NodeInfo semantics for various nodes in the tree
    ///  
    internal class NodeInfoVisitor : BasicOpVisitorOfT 
    {
        #region public methods 
        /// 
        /// The only public method. Computes the nodeInfo for a node in the tree.
        /// Assumes that the NodeInfo for each child (if computed already) is valid
        ///  
        /// Node to get NodeInfo for
        /// NodeInfo for the node 
        internal NodeInfo ComputeNodeInfo(Node n) 
        {
            NodeInfo nodeInfo = VisitNode(n); 
            nodeInfo.ComputeHashValue(this.m_command, n); // compute the hash value for this node
            return nodeInfo;
        }
        #endregion 

        #region constructors 
        ///  
        /// Basic constructor
        ///  
        /// 
        internal NodeInfoVisitor(Command command)
        {
            m_command = command; 
        }
        #endregion 
 
        #region private state
        private Command m_command; 
        #endregion

        #region private methods
        private NodeInfo GetNodeInfo(Node n) 
        {
            return n.GetNodeInfo(m_command); 
        } 
        private ExtendedNodeInfo GetExtendedNodeInfo(Node n)
        { 
            return n.GetExtendedNodeInfo(m_command);
        }
        private NodeInfo InitNodeInfo(Node n)
        { 
            NodeInfo nodeInfo = GetNodeInfo(n);
            nodeInfo.Clear(); 
            return nodeInfo; 
        }
        private ExtendedNodeInfo InitExtendedNodeInfo(Node n) 
        {
            ExtendedNodeInfo nodeInfo = GetExtendedNodeInfo(n);
            nodeInfo.Clear();
            return nodeInfo; 
        }
        #endregion 
 
        #region VisitorHelpers
        ///  
        /// Default implementation for scalarOps. Simply adds up external references
        /// from each child
        /// 
        ///  
        /// 
        protected override NodeInfo VisitDefault(Node n) 
        { 
            Debug.Assert(n.Op.IsScalarOp || n.Op.IsAncillaryOp, "not a supported optype");
 
            NodeInfo nodeInfo = InitNodeInfo(n);
            // My external references are simply the combination of external references
            // of all my children
            foreach (Node chi in n.Children) 
            {
                NodeInfo childNodeInfo = GetNodeInfo(chi); 
                nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences); 
            }
            return nodeInfo; 
        }
        #endregion

        #region IOpVisitor Members 

        #region MiscOps 
        #endregion 

        #region AncillarOps 
        #endregion

        #region ScalarOps
        ///  
        /// The only special case among all scalar and ancillaryOps. Simply adds
        /// its var to the list of unreferenced Ops 
        ///  
        /// The VarRefOp
        /// Current node 
        /// 
        public override NodeInfo Visit(VarRefOp op, Node n)
        {
            NodeInfo nodeInfo = InitNodeInfo(n); 
            nodeInfo.ExternalReferences.Set(op.Var);
            return nodeInfo; 
        } 

        #endregion 

        #region RelOps
        protected override NodeInfo VisitRelOpDefault(RelOp op, Node n)
        { 
            return Unimplemented(n);
        } 
 
        /// 
        /// Definitions = Local Definitions = table columns 
        /// External References = none
        /// Keys = keys of entity type
        /// RowCount (default): MinRows = 0, MaxRows = *
        ///  
        /// ScanTable/ScanView op
        /// current subtree 
        /// nodeinfo for this subtree 
        protected override NodeInfo VisitTableOp(ScanTableBaseOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            // #479372 - only the "referenced" columns of the table should
            // show up in the definitions
            nodeInfo.LocalDefinitions.Or(op.Table.ReferencedColumns); 
            nodeInfo.Definitions.Or(op.Table.ReferencedColumns);
 
            // get table's keys - but only if the key columns have been referenced 
            if (op.Table.ReferencedColumns.Subsumes(op.Table.Keys))
            { 
                nodeInfo.Keys.InitFrom(op.Table.Keys);
            }
            // no external references
 
            return nodeInfo;
        } 
 
        /// 
        /// Computes a NodeInfo for an UnnestOp. 
        /// Definitions = columns of the table produced by this Op
        /// Keys = none
        /// External References = the unnestVar + any external references of the
        ///   computed Var (if any) 
        /// RowCount (default): MinRows = 0; MaxRows = *
        ///  
        ///  
        /// 
        ///  
        public override NodeInfo Visit(UnnestOp op, Node n)
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            foreach (Var v in op.Table.Columns) 
            {
                nodeInfo.LocalDefinitions.Set(v); 
                nodeInfo.Definitions.Set(v); 
            }
            // no keys 

            // If I have a child, then my external references are my child's external references.
            // Otherwise, my external reference is my unnestVar
            if (n.HasChild0) 
            {
                NodeInfo childNodeInfo = GetNodeInfo(n.Child0); 
                nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences); 
            }
            else 
            {
                nodeInfo.ExternalReferences.Set(op.Var);
            }
 
            return nodeInfo;
        } 
 
        /// 
        /// Walk through the computed vars defined by a VarDefListNode, and look for 
        /// "simple" Var renames. Build up a mapping from original Vars to the renamed Vars
        /// 
        /// the varDefListNode subtree
        /// A dictionary of Var->Var renames 
        internal static Dictionary ComputeVarRemappings(Node varDefListNode)
        { 
            Debug.Assert(varDefListNode.Op.OpType == OpType.VarDefList); 

            Dictionary varMap = new Dictionary(); 
            foreach (Node varDefNode in varDefListNode.Children)
            {
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
                if (varRefOp != null) 
                {
                    VarDefOp varDefOp = varDefNode.Op as VarDefOp; 
                    Debug.Assert(varDefOp != null); 
                    varMap[varRefOp.Var] = varDefOp.Var;
                } 
            }
            return varMap;
        }
 
        /// 
        /// Computes a NodeInfo for a ProjectOp. 
        /// Definitions = the Vars property of this Op 
        /// LocalDefinitions = list of computed Vars produced by this node
        /// Keys = Keys of the input Relop (if they are all preserved) 
        /// External References = any external references from the computed Vars
        /// RowCount = Input's RowCount
        /// 
        /// The ProjectOp 
        /// corresponding Node
        ///  
        public override NodeInfo Visit(ProjectOp op, Node n) 
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 

            // Walk through my outputs and identify my "real" definitions
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
            // In the first pass, only definitions of the child are considered 
            // to be definitions - everything else is an external reference
            foreach (Var v in op.Outputs) 
            { 
                if (relOpChildNodeInfo.Definitions.IsSet(v))
                { 
                    nodeInfo.Definitions.Set(v);
                }
                else
                { 
                    nodeInfo.ExternalReferences.Set(v);
                } 
            } 

            // Local definitions 
            foreach (Node chi in n.Child1.Children)
            {
                VarDefOp varDefOp = chi.Op as VarDefOp;
                NodeInfo chiNodeInfo = GetNodeInfo(chi.Child0); 
                nodeInfo.LocalDefinitions.Set(varDefOp.Var);
                nodeInfo.ExternalReferences.Clear(varDefOp.Var); 
                nodeInfo.Definitions.Set(varDefOp.Var); 
                nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
            } 
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);

            // Get the set of keys - simply the list of my child's keys, unless 
            // they're not all defined
            nodeInfo.Keys.NoKeys = true; 
            if (!relOpChildNodeInfo.Keys.NoKeys) 
            {
                // Check to see if any of my child's keys have been left by the wayside 
                // in that case, mark this node as having no keys
                VarVec keyVec = m_command.CreateVarVec(relOpChildNodeInfo.Keys.KeyVars);
                Dictionary varRenameMap = ComputeVarRemappings(n.Child1);
                VarVec mappedKeyVec = keyVec.Remap(varRenameMap); 
                VarVec mappedKeyVecClone = mappedKeyVec.Clone();
                VarVec opVars = m_command.CreateVarVec(op.Outputs); 
                mappedKeyVec.Minus(opVars); 
                if (mappedKeyVec.IsEmpty)
                { 
                    nodeInfo.Keys.InitFrom(mappedKeyVecClone);
                }
            }
            nodeInfo.InitRowCountFrom(relOpChildNodeInfo); 
            return nodeInfo;
        } 
 
        /// 
        /// Computes a NodeInfo for a FilterOp. 
        /// Definitions = Definitions of the input Relop
        /// LocalDefinitions = None
        /// Keys = Keys of the input Relop
        /// External References = any external references from the input + any external 
        ///    references from the predicate
        /// MaxOneRow = Input's RowCount 
        ///    If the predicate is a "false" predicate, then max RowCount is zero 
        ///    If we can infer additional info from the key-selector, we may be
        ///     able to get better estimates 
        /// 
        /// The FilterOp
        /// corresponding Node
        ///  
        public override NodeInfo Visit(FilterOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
            NodeInfo predNodeInfo = GetNodeInfo(n.Child1); 

            // definitions are my child's definitions
            nodeInfo.Definitions.Or(relOpChildNodeInfo.Definitions);
            // No local definitions 

            // My external references are my child's external references + those made 
            // by my predicate 
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Or(predNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);

            // my keys are my child's keys
            nodeInfo.Keys.InitFrom(relOpChildNodeInfo.Keys); 
            // inherit max RowCount from child; set min RowCount to 0, because
            // we require way more analysis to do anything smarter 
            nodeInfo.MinRows = RowCount.Zero; 
            // If the predicate is a "false" predicate, then we know that MaxRows
            // is zero as well 
            ConstantPredicateOp predicate = n.Child1.Op as ConstantPredicateOp;
            if (predicate != null && predicate.IsFalse)
            {
                nodeInfo.MaxRows = RowCount.Zero; 
            }
            else 
            { 
                nodeInfo.MaxRows = relOpChildNodeInfo.MaxRows;
            } 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for a GroupByOp.
        /// Definitions = Keys + aggregates 
        /// LocalDefinitions = Keys + Aggregates 
        /// Keys = GroupBy Keys
        /// External References = any external references from the input + any external 
        ///    references from the local computed Vars
        /// RowCount = (0,1), if no group-by keys; (0,n) otherwise
        /// 
        /// The GroupByOp 
        /// corresponding Node
        ///  
        public override NodeInfo Visit(GroupByOp op, Node n) 
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);

            // all definitions are my outputs
            nodeInfo.Definitions.InitFrom(op.Outputs); 
            nodeInfo.LocalDefinitions.InitFrom(nodeInfo.Definitions);
            // my definitions are the keys and aggregates I define myself 
 
            // My references are my child's external references + those made
            // by my keys and my aggregates 
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
            foreach (Node chi in n.Child1.Children)
            {
                NodeInfo keyExprNodeInfo = GetNodeInfo(chi.Child0); 
                nodeInfo.ExternalReferences.Or(keyExprNodeInfo.ExternalReferences);
            } 
            foreach (Node chi in n.Child2.Children) 
            {
                NodeInfo aggExprNodeInfo = GetNodeInfo(chi.Child0); 
                nodeInfo.ExternalReferences.Or(aggExprNodeInfo.ExternalReferences);
            }
            // eliminate definitions of my input
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions); 

            // my keys are my grouping keys 
            nodeInfo.Keys.InitFrom(op.Keys); 

            // should we inherit the min RowCount from the child ? 
            nodeInfo.MinRows = RowCount.Zero;
            nodeInfo.MaxRows = op.Keys.IsEmpty ? RowCount.One : relOpChildNodeInfo.MaxRows;

            return nodeInfo; 
        }
 
        ///  
        /// Computes a NodeInfo for a CrossJoinOp.
        /// Definitions = Definitions of my children 
        /// LocalDefinitions = None
        /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
        /// External References = any external references from the inputs
        /// RowCount: MinRows: min(min-rows of each child) 
        ///              MaxRows: max(max-rows of each child)
        ///  
        /// The CrossJoinOp 
        /// corresponding Node
        ///  
        public override NodeInfo Visit(CrossJoinOp op, Node n)
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 
            // No definitions of my own. Simply inherit from my children
            // My external references are the union of my children's external 
            // references 
            // And my keys are the concatenation of the keys of each of my
            // inputs 
            List keyVecList = new List();
            RowCount maxCard = RowCount.Zero;
            RowCount minCard = RowCount.One;
            foreach (Node chi in n.Children) 
            {
                ExtendedNodeInfo chiNodeInfo = GetExtendedNodeInfo(chi); 
                nodeInfo.Definitions.Or(chiNodeInfo.Definitions); 
                nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
                keyVecList.Add(chiNodeInfo.Keys); 

                // Not entirely precise, but good enough
                if (chiNodeInfo.MaxRows > maxCard)
                { 
                    maxCard = chiNodeInfo.MaxRows;
                } 
                if (chiNodeInfo.MinRows < minCard) 
                {
                    minCard = chiNodeInfo.MinRows; 
                }
            }
            nodeInfo.Keys.InitFrom(keyVecList);
 
            nodeInfo.SetRowCount(minCard, maxCard);
 
            return nodeInfo; 
        }
 
        /// 
        /// Computes a NodeInfo for an Inner/LeftOuter/FullOuter JoinOp.
        /// Definitions = Definitions of my children
        /// LocalDefinitions = None 
        /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
        /// External References = any external references from the inputs + any external 
        ///    references from the join predicates 
        /// RowCount:
        ///    FullOuterJoin: MinRows = 0, MaxRows = N 
        ///    InnerJoin: MinRows = 0;
        ///               MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
        ///    OuterJoin: MinRows = leftInput.MinRows
        ///               MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1 
        /// 
        /// The JoinOp 
        /// corresponding Node 
        /// 
        protected override NodeInfo VisitJoinOp(JoinBaseOp op, Node n) 
        {
            if (!(op.OpType == OpType.InnerJoin ||
                  op.OpType == OpType.LeftOuterJoin ||
                  op.OpType == OpType.FullOuterJoin)) 
            {
                return Unimplemented(n); 
            } 

            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 

            // No definitions of my own. Simply inherit from my children
            // My external references are the union of my children's external
            // references 
            // And my keys are the concatenation of the keys of each of my
            // inputs 
            ExtendedNodeInfo leftRelOpNodeInfo = GetExtendedNodeInfo(n.Child0); 
            ExtendedNodeInfo rightRelOpNodeInfo = GetExtendedNodeInfo(n.Child1);
            NodeInfo predNodeInfo = GetNodeInfo(n.Child2); 

            nodeInfo.Definitions.Or(leftRelOpNodeInfo.Definitions);
            nodeInfo.Definitions.Or(rightRelOpNodeInfo.Definitions);
 
            nodeInfo.ExternalReferences.Or(leftRelOpNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Or(rightRelOpNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Or(predNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions);
 
            nodeInfo.Keys.InitFrom(leftRelOpNodeInfo.Keys, rightRelOpNodeInfo.Keys);

            RowCount maxRows;
            RowCount minRows; 
            if (op.OpType == OpType.FullOuterJoin)
            { 
                minRows = RowCount.Zero; 
                maxRows = RowCount.Unbounded;
            } 
            else
            {
                if ((leftRelOpNodeInfo.MaxRows > RowCount.One) ||
                    (rightRelOpNodeInfo.MaxRows > RowCount.One)) 
                {
                    maxRows = RowCount.Unbounded; 
                } 
                else
                { 
                    maxRows = RowCount.One;
                }

                if (op.OpType == OpType.LeftOuterJoin) 
                {
                    minRows = leftRelOpNodeInfo.MinRows; 
                } 
                else
                { 
                    minRows = RowCount.Zero;
                }
            }
 
            nodeInfo.SetRowCount(minRows, maxRows);
 
            return nodeInfo; 
        }
 
        /// 
        /// Computes a NodeInfo for a CrossApply/OuterApply op.
        /// Definitions = Definitions of my children
        /// LocalDefinitions = None 
        /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
        /// External References = any external references from the inputs 
        /// RowCount: 
        ///    CrossApply: minRows=0; MaxRows=Unbounded
        ///         (MaxRows = 1, if both inputs have MaxRow less than or equal to 1) 
        ///    OuterApply: minRows=leftInput.MinRows; MaxRows=Unbounded
        ///         (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
        ///
        ///  
        /// The ApplyOp
        /// corresponding Node 
        ///  
        protected override NodeInfo VisitApplyOp(ApplyBaseOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);

            ExtendedNodeInfo leftRelOpNodeInfo = GetExtendedNodeInfo(n.Child0);
            ExtendedNodeInfo rightRelOpNodeInfo = GetExtendedNodeInfo(n.Child1); 

            nodeInfo.Definitions.Or(leftRelOpNodeInfo.Definitions); 
            nodeInfo.Definitions.Or(rightRelOpNodeInfo.Definitions); 

            nodeInfo.ExternalReferences.Or(leftRelOpNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Or(rightRelOpNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions);

            nodeInfo.Keys.InitFrom(leftRelOpNodeInfo.Keys, rightRelOpNodeInfo.Keys); 

            RowCount maxRows; 
            if (leftRelOpNodeInfo.MaxRows <= RowCount.One && 
                rightRelOpNodeInfo.MaxRows <= RowCount.One)
            { 
                maxRows = RowCount.One;
            }
            else
            { 
                maxRows = RowCount.Unbounded;
            } 
            RowCount minRows = (op.OpType == OpType.CrossApply) ? RowCount.Zero : leftRelOpNodeInfo.MinRows; 
            nodeInfo.SetRowCount(minRows, maxRows);
 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for SetOps (UnionAll, Intersect, Except).
        /// Definitions = OutputVars 
        /// LocalDefinitions = OutputVars 
        /// Keys = Output Vars for Intersect, Except. For UnionAll ??
        /// External References = any external references from the inputs 
        /// RowCount: Min = 0, Max = unbounded.
        ///    For UnionAlls, MinRows = max(MinRows of left and right inputs)
        ///
        ///  
        /// The SetOp
        /// corresponding Node 
        ///  
        protected override NodeInfo VisitSetOp(SetOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);

            // My definitions and my "all" definitions are simply my outputs
            nodeInfo.Definitions.InitFrom(op.Outputs); 
            nodeInfo.LocalDefinitions.InitFrom(op.Outputs);
 
            RowCount minRows = RowCount.Zero; 
            // My external references are the external references of each of
            // my inputs 
            foreach (Node chi in n.Children)
            {
                ExtendedNodeInfo chiRelOpNodeInfo = GetExtendedNodeInfo(chi);
                nodeInfo.ExternalReferences.Or(chiRelOpNodeInfo.ExternalReferences); 
                if ((op.OpType == OpType.UnionAll) &&
                    (chiRelOpNodeInfo.MinRows > minRows)) 
                { 
                    minRows = chiRelOpNodeInfo.MinRows;
                } 
            }

            // for intersect, and exceptOps, the keys are simply the outputs.
            if (op.OpType == OpType.Intersect || op.OpType == OpType.Except) 
            {
                nodeInfo.Keys.InitFrom(op.Outputs); 
            } 
            else
            { 
                // UnionAlls are a lot more complicated.  If we've gone through
                // keyPullup, we will have set some keys on it's input branches and
                // what we need to do here is get the keys from each branch and re-map
                // them to the output vars. 
                //
                // If the branchDiscriminator is not set on the unionAllOp, then 
                // we haven't been through key pullup and we can't look at the keys 
                // that the child nodes have, because they're not discriminated.
                // 
                // See the logic in KeyPullup, where we make sure that there are
                // actually branch discriminators on the input branches.
                UnionAllOp unionAllOp = (UnionAllOp)op;
 
                if (null == unionAllOp.BranchDiscriminator)
                { 
                    nodeInfo.Keys.NoKeys = true; 
                }
                else 
                {
                    VarVec nodeKeys = m_command.CreateVarVec();
                    VarVec mappedKeyVec;
                    for (int i = 0; i < n.Children.Count; i++) 
                    {
                        ExtendedNodeInfo childNodeInfo = n.Children[i].GetExtendedNodeInfo(m_command); 
                        if (!childNodeInfo.Keys.NoKeys && !childNodeInfo.Keys.KeyVars.IsEmpty) 
                        {
                            mappedKeyVec = childNodeInfo.Keys.KeyVars.Remap(unionAllOp.VarMap[i].GetReverseMap()); 
                            nodeKeys.Or(mappedKeyVec);
                        }
                        else
                        { 
                            // Each branch had better have keys, or we can't continue.
                            nodeKeys.Clear(); 
                            break; 
                        }
                    } 

                    // You might be tempted to ask: "Don't we need to add the branch discriminator
                    // to the keys as well?"  The reason we don't is that we wouldn't be here unless
                    // we have a branch discriminator variable, which implies we've pulled up keys on 
                    // the inputs, and they'll already have the branch descriminator set in the keys
                    // of each input, so we don't need to add that... 
                    if (nodeKeys.IsEmpty) 
                    {
                        nodeInfo.Keys.NoKeys = true; 
                    }
                    else
                    {
                        nodeInfo.Keys.InitFrom(nodeKeys); 
                    }
                } 
            } 

            nodeInfo.MinRows = minRows; 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for a ConstrainedSortOp/SortOp.
        /// Definitions = Definitions of the input Relop 
        /// LocalDefinitions = not allowed 
        /// Keys = Keys of the input Relop
        /// External References = any external references from the input + any external 
        ///    references from the predicate
        /// RowCount = Input's RowCount
        /// 
        /// The SortOp 
        /// corresponding Node
        ///  
        protected override NodeInfo VisitSortOp(SortBaseOp op, Node n) 
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);

            // definitions are my child's definitions
            nodeInfo.Definitions.Or(relOpChildNodeInfo.Definitions); 

            // My references are my child's external references + those made 
            // by my sort keys 
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions); 

            // my keys are my child's keys
            nodeInfo.Keys.InitFrom(relOpChildNodeInfo.Keys);
            nodeInfo.InitRowCountFrom(relOpChildNodeInfo); 

            // For constrained sort, if the Limit value is Constant(1) and WithTies is false, 
            // then MinRows and MaxRows can be adjusted to 0, 1. 
            if (OpType.ConstrainedSort == op.OpType &&
                OpType.Constant == n.Child2.Op.OpType && 
                !((ConstrainedSortOp)op).WithTies)
            {
                ConstantBaseOp constOp = (ConstantBaseOp)n.Child2.Op;
                if(TypeHelpers.IsIntegerConstant(constOp.Type, constOp.Value, 1)) 
                {
                    nodeInfo.SetRowCount(RowCount.Zero, RowCount.One); 
                } 
            }
 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for Distinct.
        /// Definitions = OutputVars 
        /// LocalDefinitions = None 
        /// Keys = Output Vars
        /// External References = any external references from the inputs 
        /// RowCount = Input's RowCount
        /// 
        /// The DistinctOp
        /// corresponding Node 
        /// 
        public override NodeInfo Visit(DistinctOp op, Node n) 
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            // no local definitions - definitions are just the keys 
            nodeInfo.Definitions.InitFrom(op.Keys);

            //#497217 - The parameters should not be included as keys
            nodeInfo.Keys.InitFrom(op.Keys, true); 

            // external references - inherit from child 
            ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0); 
            nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
            nodeInfo.InitRowCountFrom(childNodeInfo); 
            return nodeInfo;
        }

        ///  
        /// Compute NodeInfo for a SingleRowOp.
        /// Definitions = child's definitions 
        /// Keys = child's keys 
        /// Local Definitions = none
        /// External references = child's external references 
        /// RowCount=(0,1)
        /// 
        /// The SingleRowOp
        /// current subtree 
        /// NodeInfo for this node
        public override NodeInfo Visit(SingleRowOp op, Node n) 
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0); 
            nodeInfo.Definitions.InitFrom(childNodeInfo.Definitions);
            nodeInfo.Keys.InitFrom(childNodeInfo.Keys);
            nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
            nodeInfo.SetRowCount(RowCount.Zero, RowCount.One); 
            return nodeInfo;
        } 
 
        /// 
        /// SingleRowTableOp 
        /// No definitions, external references.
        /// Keys = empty list (not the same as "no keys")
        /// RowCount = (1,1)
        ///  
        /// the SingleRowTableOp
        /// current subtree 
        /// nodeInfo for this subtree 
        public override NodeInfo Visit(SingleRowTableOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            nodeInfo.Keys.NoKeys = false;
            nodeInfo.SetRowCount(RowCount.One, RowCount.One);
            return nodeInfo; 
        }
 
        #endregion 

        #region PhysicalOps 
        /// 
        /// Computes a NodeInfo for a PhysicalProjectOp.
        /// Definitions = OutputVars
        /// LocalDefinitions = None 
        /// Keys = None
        /// External References = any external references from the inputs 
        /// RowCount=default 
        /// 
        /// The PhysicalProjectOp 
        /// corresponding Node
        /// 
        public override NodeInfo Visit(PhysicalProjectOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            foreach (Node chi in n.Children) 
            { 
                NodeInfo childNodeInfo = GetNodeInfo(chi);
                nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences); 
            }
            nodeInfo.Definitions.InitFrom(op.Outputs);
            nodeInfo.LocalDefinitions.InitFrom(nodeInfo.Definitions);
 
            //
            // Inherit the keys from the child - but only if all the columns were projected 
            // out 
            //
            ExtendedNodeInfo driverChildNodeInfo = GetExtendedNodeInfo(n.Child0); 
            if (!driverChildNodeInfo.Keys.NoKeys)
            {
                VarVec missingKeys = m_command.CreateVarVec(driverChildNodeInfo.Keys.KeyVars);
                missingKeys.Minus(nodeInfo.Definitions); 
                if (missingKeys.IsEmpty)
                { 
                    nodeInfo.Keys.InitFrom(driverChildNodeInfo.Keys); 
                }
            } 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for a NestOp (SingleStream/MultiStream).
        /// Definitions = OutputVars 
        /// LocalDefinitions = Collection Vars 
        /// Keys = Keys of my child
        /// External References = any external references from the inputs 
        /// RowCount=default
        /// 
        /// The NestOp
        /// corresponding Node 
        /// 
        protected override NodeInfo VisitNestOp(NestBaseOp op, Node n) 
        { 
            SingleStreamNestOp ssnOp = op as SingleStreamNestOp;
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 

            foreach (CollectionInfo ci in op.CollectionInfo)
            {
                nodeInfo.LocalDefinitions.Set(ci.CollectionVar); 
            }
            nodeInfo.Definitions.InitFrom(op.Outputs); 
 
            // get external references from each child
            foreach (Node chi in n.Children) 
            {
                nodeInfo.ExternalReferences.Or(GetExtendedNodeInfo(chi).ExternalReferences);
            }
 
            // eliminate things I may have defined already (left correlation)
            nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions); 
 
            // Keys are from the driving node only.
            if (ssnOp == null) 
            {
                nodeInfo.Keys.InitFrom(GetExtendedNodeInfo(n.Child0).Keys);
            }
            else 
            {
                nodeInfo.Keys.InitFrom(ssnOp.Keys); 
            } 
            return nodeInfo;
        } 

        #endregion

        #endregion 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....], [....]
//--------------------------------------------------------------------- 
 
using System;
using System.Collections.Generic; 
using System.Globalization;
using System.Diagnostics;
using System.Data.Common;
using md=System.Data.Metadata.Edm; 

namespace System.Data.Query.InternalTrees 
{ 
    /// 
    /// The KeySet class encapsulates all information about the keys of a RelOp node in 
    /// the query tree.
    /// A KeyVec is logically a set of vars that uniquely identify the row of the current
    /// RelOp. Some RelOps may have no unique keys - such a state is identified by the
    /// "NoKeys" property 
    /// 
    internal class KeyVec 
    { 
        #region private state
        private VarVec m_keys; 
        private bool m_noKeys;
        #endregion

        #region constructors 
        internal KeyVec(Command itree)
        { 
            m_keys = itree.CreateVarVec(); 
            m_noKeys = true;
        } 
        #endregion

        internal void InitFrom(KeyVec keyset)
        { 
            m_keys.InitFrom(keyset.m_keys);
            m_noKeys = keyset.m_noKeys; 
        } 

        internal void InitFrom(IEnumerable varSet) 
        {
            InitFrom(varSet, false);
        }
 
        internal void InitFrom(IEnumerable varSet, bool ignoreParameters)
        { 
            m_keys.InitFrom(varSet, ignoreParameters); 
            // Bug 434541: An empty set of keys is not the same as "no" keys.
            // Caveat Emptor 
            m_noKeys = false;
        }
        internal void InitFrom(KeyVec left, KeyVec right)
        { 
            if (left.m_noKeys || right.m_noKeys)
            { 
                m_noKeys = true; 
            }
            else 
            {
                m_noKeys = false;
                m_keys.InitFrom(left.m_keys);
                m_keys.Or(right.m_keys); 
            }
        } 
        internal void InitFrom(List keyVecList) 
        {
            m_noKeys = false; 
            m_keys.Clear();
            foreach (KeyVec keyVec in keyVecList)
            {
                if (keyVec.m_noKeys) 
                {
                    m_noKeys = true; 
                    return; 
                }
                m_keys.Or(keyVec.m_keys); 
            }
        }
        internal void Clear()
        { 
            m_noKeys = true;
            m_keys.Clear(); 
        } 

        internal VarVec KeyVars { get { return m_keys; } } 
        internal bool NoKeys { get { return m_noKeys; } set { m_noKeys = value; } }
    }

    ///  
    /// The NodeInfo class represents additional information about a node in the tree.
    /// By default, this includes a set of external references for each node (ie) references 
    /// to Vars that are not defined in the same subtree 
    /// The NodeInfo class also includes a "hashValue" that is a hash value for the entire
    /// subtree rooted at this node 
    /// 
    internal class NodeInfo
    {
        #region private state 
        private VarVec m_externalReferences;
        protected int m_hashValue; // hash value for the node 
        #endregion 

        #region constructors 
        internal NodeInfo(Command cmd)
        {
            m_externalReferences = cmd.CreateVarVec();
        } 
        #endregion
 
        #region public methods 
        /// 
        /// Clear out all information - usually used by a Recompute 
        /// 
        internal virtual void Clear()
        {
            m_externalReferences.Clear(); 
            m_hashValue = 0;
        } 
 
        /// 
        /// All external references from this node 
        /// 
        internal VarVec ExternalReferences
        {
            get { return m_externalReferences; } 
        }
 
        ///  
        /// Get the hash value for this nodeInfo
        ///  
        internal int HashValue
        {
            get { return m_hashValue; }
        } 

        ///  
        /// Compute the hash value for a Vec 
        /// 
        ///  
        /// 
        internal static int GetHashValue(VarVec vec)
        {
            int hashValue = 0; 
            foreach (Var v in vec)
            { 
                hashValue ^= v.GetHashCode(); 
            }
            return hashValue; 
        }

        /// 
        /// Computes the hash value for this node. The hash value is simply the 
        /// local hash value for this node info added with the hash values of the child
        /// nodes 
        ///  
        /// current command
        /// current node 
        internal virtual void ComputeHashValue(Command cmd, Node n)
        {
            m_hashValue = 0;
            foreach (Node chi in n.Children) 
            {
                NodeInfo chiNodeInfo = cmd.GetNodeInfo(chi); 
                m_hashValue ^= chiNodeInfo.HashValue; 
            }
 
            m_hashValue = (m_hashValue << 4) ^ ((int)n.Op.OpType); // include the optype somehow
            // Now compute my local hash value
            m_hashValue = (m_hashValue << 4) ^ GetHashValue(m_externalReferences);
        } 
        #endregion
    } 
 
    /// 
    /// Enum describing row counts 
    /// 
    internal enum RowCount : byte
    {
        ///  
        /// Zero rows
        ///  
        Zero = 0, 

        ///  
        /// One row
        /// 
        One = 1,
 
        /// 
        /// Unbounded (unknown number of rows) 
        ///  
        Unbounded = 2,
    } 

    /// 
    /// An ExtendedNodeInfo class adds additional information to a standard NodeInfo.
    /// This class is usually applicable only to RelOps and PhysicalOps. 
    /// The ExtendedNodeInfo class has in addition to the information maintained by NodeInfo
    /// the following 
    /// - a set of local definitions 
    /// - a set of definitions
    /// - and a set of keys 
    /// 
    internal class ExtendedNodeInfo : NodeInfo
    {
        #region private 
        private VarVec m_localDefinitions;
        private VarVec m_definitions; 
        private KeyVec m_keys; 
        private RowCount m_minRows;
        private RowCount m_maxRows; 
        #endregion

        #region constructors
        internal ExtendedNodeInfo(Command cmd) 
            : base(cmd)
        { 
            m_localDefinitions = cmd.CreateVarVec(); 
            m_definitions = cmd.CreateVarVec();
            m_keys = new KeyVec(cmd); 
            m_minRows = RowCount.Zero;
            m_maxRows = RowCount.Unbounded;
        }
        #endregion 

        #region public methods 
 
        internal override void Clear()
        { 
            base.Clear();
            m_definitions.Clear();
            m_localDefinitions.Clear();
            m_keys.Clear(); 
            m_minRows = RowCount.Zero;
            m_maxRows = RowCount.Unbounded; 
        } 

        ///  
        /// Compute the hash value for this node
        /// 
        /// 
        ///  
        internal override void ComputeHashValue(Command cmd, Node n)
        { 
            base.ComputeHashValue(cmd, n); 
            m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Definitions);
            m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Keys.KeyVars); 
            return;
        }

        ///  
        /// Definitions made specifically by this node
        ///  
        internal VarVec LocalDefinitions { get { return m_localDefinitions; } } 
        /// 
        /// All definitions visible at this node 
        /// 
        internal VarVec Definitions { get { return m_definitions; } }
        /// 
        /// The keys for this node 
        /// 
        internal KeyVec Keys { get { return m_keys; } } 
 
        /// 
        /// Min number of rows returned from this node 
        /// 
        internal RowCount MinRows
        {
            get { return m_minRows; } 
            set { m_minRows = value; ValidateRowCount(); }
        } 
        ///  
        /// Max rows returned from this node
        ///  
        internal RowCount MaxRows
        {
            get { return m_maxRows; }
            set { m_maxRows = value; ValidateRowCount(); } 
        }
 
        ///  
        /// Set the rowcount for this node
        ///  
        /// min rows produced by this node
        /// max rows produced by this node
        internal void SetRowCount(RowCount minRows, RowCount maxRows)
        { 
            m_minRows = minRows;
            m_maxRows = maxRows; 
            ValidateRowCount(); 
        }
 
        /// 
        /// Initialize the rowcounts for this node from the source node
        /// 
        /// nodeinfo of source 
        internal void InitRowCountFrom(ExtendedNodeInfo source)
        { 
            m_minRows = source.m_minRows; 
            m_maxRows = source.m_maxRows;
        } 

        #endregion

        #region private methods 
        private void ValidateRowCount()
        { 
            Debug.Assert(m_maxRows >= m_minRows, "MaxRows less than MinRows?"); 
        }
        #endregion 
    }

    /// 
    /// The NodeInfoVisitor is a simple class (ab)using the Visitor pattern to define 
    /// NodeInfo semantics for various nodes in the tree
    ///  
    internal class NodeInfoVisitor : BasicOpVisitorOfT 
    {
        #region public methods 
        /// 
        /// The only public method. Computes the nodeInfo for a node in the tree.
        /// Assumes that the NodeInfo for each child (if computed already) is valid
        ///  
        /// Node to get NodeInfo for
        /// NodeInfo for the node 
        internal NodeInfo ComputeNodeInfo(Node n) 
        {
            NodeInfo nodeInfo = VisitNode(n); 
            nodeInfo.ComputeHashValue(this.m_command, n); // compute the hash value for this node
            return nodeInfo;
        }
        #endregion 

        #region constructors 
        ///  
        /// Basic constructor
        ///  
        /// 
        internal NodeInfoVisitor(Command command)
        {
            m_command = command; 
        }
        #endregion 
 
        #region private state
        private Command m_command; 
        #endregion

        #region private methods
        private NodeInfo GetNodeInfo(Node n) 
        {
            return n.GetNodeInfo(m_command); 
        } 
        private ExtendedNodeInfo GetExtendedNodeInfo(Node n)
        { 
            return n.GetExtendedNodeInfo(m_command);
        }
        private NodeInfo InitNodeInfo(Node n)
        { 
            NodeInfo nodeInfo = GetNodeInfo(n);
            nodeInfo.Clear(); 
            return nodeInfo; 
        }
        private ExtendedNodeInfo InitExtendedNodeInfo(Node n) 
        {
            ExtendedNodeInfo nodeInfo = GetExtendedNodeInfo(n);
            nodeInfo.Clear();
            return nodeInfo; 
        }
        #endregion 
 
        #region VisitorHelpers
        ///  
        /// Default implementation for scalarOps. Simply adds up external references
        /// from each child
        /// 
        ///  
        /// 
        protected override NodeInfo VisitDefault(Node n) 
        { 
            Debug.Assert(n.Op.IsScalarOp || n.Op.IsAncillaryOp, "not a supported optype");
 
            NodeInfo nodeInfo = InitNodeInfo(n);
            // My external references are simply the combination of external references
            // of all my children
            foreach (Node chi in n.Children) 
            {
                NodeInfo childNodeInfo = GetNodeInfo(chi); 
                nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences); 
            }
            return nodeInfo; 
        }
        #endregion

        #region IOpVisitor Members 

        #region MiscOps 
        #endregion 

        #region AncillarOps 
        #endregion

        #region ScalarOps
        ///  
        /// The only special case among all scalar and ancillaryOps. Simply adds
        /// its var to the list of unreferenced Ops 
        ///  
        /// The VarRefOp
        /// Current node 
        /// 
        public override NodeInfo Visit(VarRefOp op, Node n)
        {
            NodeInfo nodeInfo = InitNodeInfo(n); 
            nodeInfo.ExternalReferences.Set(op.Var);
            return nodeInfo; 
        } 

        #endregion 

        #region RelOps
        protected override NodeInfo VisitRelOpDefault(RelOp op, Node n)
        { 
            return Unimplemented(n);
        } 
 
        /// 
        /// Definitions = Local Definitions = table columns 
        /// External References = none
        /// Keys = keys of entity type
        /// RowCount (default): MinRows = 0, MaxRows = *
        ///  
        /// ScanTable/ScanView op
        /// current subtree 
        /// nodeinfo for this subtree 
        protected override NodeInfo VisitTableOp(ScanTableBaseOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            // #479372 - only the "referenced" columns of the table should
            // show up in the definitions
            nodeInfo.LocalDefinitions.Or(op.Table.ReferencedColumns); 
            nodeInfo.Definitions.Or(op.Table.ReferencedColumns);
 
            // get table's keys - but only if the key columns have been referenced 
            if (op.Table.ReferencedColumns.Subsumes(op.Table.Keys))
            { 
                nodeInfo.Keys.InitFrom(op.Table.Keys);
            }
            // no external references
 
            return nodeInfo;
        } 
 
        /// 
        /// Computes a NodeInfo for an UnnestOp. 
        /// Definitions = columns of the table produced by this Op
        /// Keys = none
        /// External References = the unnestVar + any external references of the
        ///   computed Var (if any) 
        /// RowCount (default): MinRows = 0; MaxRows = *
        ///  
        ///  
        /// 
        ///  
        public override NodeInfo Visit(UnnestOp op, Node n)
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            foreach (Var v in op.Table.Columns) 
            {
                nodeInfo.LocalDefinitions.Set(v); 
                nodeInfo.Definitions.Set(v); 
            }
            // no keys 

            // If I have a child, then my external references are my child's external references.
            // Otherwise, my external reference is my unnestVar
            if (n.HasChild0) 
            {
                NodeInfo childNodeInfo = GetNodeInfo(n.Child0); 
                nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences); 
            }
            else 
            {
                nodeInfo.ExternalReferences.Set(op.Var);
            }
 
            return nodeInfo;
        } 
 
        /// 
        /// Walk through the computed vars defined by a VarDefListNode, and look for 
        /// "simple" Var renames. Build up a mapping from original Vars to the renamed Vars
        /// 
        /// the varDefListNode subtree
        /// A dictionary of Var->Var renames 
        internal static Dictionary ComputeVarRemappings(Node varDefListNode)
        { 
            Debug.Assert(varDefListNode.Op.OpType == OpType.VarDefList); 

            Dictionary varMap = new Dictionary(); 
            foreach (Node varDefNode in varDefListNode.Children)
            {
                VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
                if (varRefOp != null) 
                {
                    VarDefOp varDefOp = varDefNode.Op as VarDefOp; 
                    Debug.Assert(varDefOp != null); 
                    varMap[varRefOp.Var] = varDefOp.Var;
                } 
            }
            return varMap;
        }
 
        /// 
        /// Computes a NodeInfo for a ProjectOp. 
        /// Definitions = the Vars property of this Op 
        /// LocalDefinitions = list of computed Vars produced by this node
        /// Keys = Keys of the input Relop (if they are all preserved) 
        /// External References = any external references from the computed Vars
        /// RowCount = Input's RowCount
        /// 
        /// The ProjectOp 
        /// corresponding Node
        ///  
        public override NodeInfo Visit(ProjectOp op, Node n) 
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 

            // Walk through my outputs and identify my "real" definitions
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
            // In the first pass, only definitions of the child are considered 
            // to be definitions - everything else is an external reference
            foreach (Var v in op.Outputs) 
            { 
                if (relOpChildNodeInfo.Definitions.IsSet(v))
                { 
                    nodeInfo.Definitions.Set(v);
                }
                else
                { 
                    nodeInfo.ExternalReferences.Set(v);
                } 
            } 

            // Local definitions 
            foreach (Node chi in n.Child1.Children)
            {
                VarDefOp varDefOp = chi.Op as VarDefOp;
                NodeInfo chiNodeInfo = GetNodeInfo(chi.Child0); 
                nodeInfo.LocalDefinitions.Set(varDefOp.Var);
                nodeInfo.ExternalReferences.Clear(varDefOp.Var); 
                nodeInfo.Definitions.Set(varDefOp.Var); 
                nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
            } 
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);

            // Get the set of keys - simply the list of my child's keys, unless 
            // they're not all defined
            nodeInfo.Keys.NoKeys = true; 
            if (!relOpChildNodeInfo.Keys.NoKeys) 
            {
                // Check to see if any of my child's keys have been left by the wayside 
                // in that case, mark this node as having no keys
                VarVec keyVec = m_command.CreateVarVec(relOpChildNodeInfo.Keys.KeyVars);
                Dictionary varRenameMap = ComputeVarRemappings(n.Child1);
                VarVec mappedKeyVec = keyVec.Remap(varRenameMap); 
                VarVec mappedKeyVecClone = mappedKeyVec.Clone();
                VarVec opVars = m_command.CreateVarVec(op.Outputs); 
                mappedKeyVec.Minus(opVars); 
                if (mappedKeyVec.IsEmpty)
                { 
                    nodeInfo.Keys.InitFrom(mappedKeyVecClone);
                }
            }
            nodeInfo.InitRowCountFrom(relOpChildNodeInfo); 
            return nodeInfo;
        } 
 
        /// 
        /// Computes a NodeInfo for a FilterOp. 
        /// Definitions = Definitions of the input Relop
        /// LocalDefinitions = None
        /// Keys = Keys of the input Relop
        /// External References = any external references from the input + any external 
        ///    references from the predicate
        /// MaxOneRow = Input's RowCount 
        ///    If the predicate is a "false" predicate, then max RowCount is zero 
        ///    If we can infer additional info from the key-selector, we may be
        ///     able to get better estimates 
        /// 
        /// The FilterOp
        /// corresponding Node
        ///  
        public override NodeInfo Visit(FilterOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
            NodeInfo predNodeInfo = GetNodeInfo(n.Child1); 

            // definitions are my child's definitions
            nodeInfo.Definitions.Or(relOpChildNodeInfo.Definitions);
            // No local definitions 

            // My external references are my child's external references + those made 
            // by my predicate 
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Or(predNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);

            // my keys are my child's keys
            nodeInfo.Keys.InitFrom(relOpChildNodeInfo.Keys); 
            // inherit max RowCount from child; set min RowCount to 0, because
            // we require way more analysis to do anything smarter 
            nodeInfo.MinRows = RowCount.Zero; 
            // If the predicate is a "false" predicate, then we know that MaxRows
            // is zero as well 
            ConstantPredicateOp predicate = n.Child1.Op as ConstantPredicateOp;
            if (predicate != null && predicate.IsFalse)
            {
                nodeInfo.MaxRows = RowCount.Zero; 
            }
            else 
            { 
                nodeInfo.MaxRows = relOpChildNodeInfo.MaxRows;
            } 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for a GroupByOp.
        /// Definitions = Keys + aggregates 
        /// LocalDefinitions = Keys + Aggregates 
        /// Keys = GroupBy Keys
        /// External References = any external references from the input + any external 
        ///    references from the local computed Vars
        /// RowCount = (0,1), if no group-by keys; (0,n) otherwise
        /// 
        /// The GroupByOp 
        /// corresponding Node
        ///  
        public override NodeInfo Visit(GroupByOp op, Node n) 
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);

            // all definitions are my outputs
            nodeInfo.Definitions.InitFrom(op.Outputs); 
            nodeInfo.LocalDefinitions.InitFrom(nodeInfo.Definitions);
            // my definitions are the keys and aggregates I define myself 
 
            // My references are my child's external references + those made
            // by my keys and my aggregates 
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
            foreach (Node chi in n.Child1.Children)
            {
                NodeInfo keyExprNodeInfo = GetNodeInfo(chi.Child0); 
                nodeInfo.ExternalReferences.Or(keyExprNodeInfo.ExternalReferences);
            } 
            foreach (Node chi in n.Child2.Children) 
            {
                NodeInfo aggExprNodeInfo = GetNodeInfo(chi.Child0); 
                nodeInfo.ExternalReferences.Or(aggExprNodeInfo.ExternalReferences);
            }
            // eliminate definitions of my input
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions); 

            // my keys are my grouping keys 
            nodeInfo.Keys.InitFrom(op.Keys); 

            // should we inherit the min RowCount from the child ? 
            nodeInfo.MinRows = RowCount.Zero;
            nodeInfo.MaxRows = op.Keys.IsEmpty ? RowCount.One : relOpChildNodeInfo.MaxRows;

            return nodeInfo; 
        }
 
        ///  
        /// Computes a NodeInfo for a CrossJoinOp.
        /// Definitions = Definitions of my children 
        /// LocalDefinitions = None
        /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
        /// External References = any external references from the inputs
        /// RowCount: MinRows: min(min-rows of each child) 
        ///              MaxRows: max(max-rows of each child)
        ///  
        /// The CrossJoinOp 
        /// corresponding Node
        ///  
        public override NodeInfo Visit(CrossJoinOp op, Node n)
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 
            // No definitions of my own. Simply inherit from my children
            // My external references are the union of my children's external 
            // references 
            // And my keys are the concatenation of the keys of each of my
            // inputs 
            List keyVecList = new List();
            RowCount maxCard = RowCount.Zero;
            RowCount minCard = RowCount.One;
            foreach (Node chi in n.Children) 
            {
                ExtendedNodeInfo chiNodeInfo = GetExtendedNodeInfo(chi); 
                nodeInfo.Definitions.Or(chiNodeInfo.Definitions); 
                nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
                keyVecList.Add(chiNodeInfo.Keys); 

                // Not entirely precise, but good enough
                if (chiNodeInfo.MaxRows > maxCard)
                { 
                    maxCard = chiNodeInfo.MaxRows;
                } 
                if (chiNodeInfo.MinRows < minCard) 
                {
                    minCard = chiNodeInfo.MinRows; 
                }
            }
            nodeInfo.Keys.InitFrom(keyVecList);
 
            nodeInfo.SetRowCount(minCard, maxCard);
 
            return nodeInfo; 
        }
 
        /// 
        /// Computes a NodeInfo for an Inner/LeftOuter/FullOuter JoinOp.
        /// Definitions = Definitions of my children
        /// LocalDefinitions = None 
        /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
        /// External References = any external references from the inputs + any external 
        ///    references from the join predicates 
        /// RowCount:
        ///    FullOuterJoin: MinRows = 0, MaxRows = N 
        ///    InnerJoin: MinRows = 0;
        ///               MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
        ///    OuterJoin: MinRows = leftInput.MinRows
        ///               MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1 
        /// 
        /// The JoinOp 
        /// corresponding Node 
        /// 
        protected override NodeInfo VisitJoinOp(JoinBaseOp op, Node n) 
        {
            if (!(op.OpType == OpType.InnerJoin ||
                  op.OpType == OpType.LeftOuterJoin ||
                  op.OpType == OpType.FullOuterJoin)) 
            {
                return Unimplemented(n); 
            } 

            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 

            // No definitions of my own. Simply inherit from my children
            // My external references are the union of my children's external
            // references 
            // And my keys are the concatenation of the keys of each of my
            // inputs 
            ExtendedNodeInfo leftRelOpNodeInfo = GetExtendedNodeInfo(n.Child0); 
            ExtendedNodeInfo rightRelOpNodeInfo = GetExtendedNodeInfo(n.Child1);
            NodeInfo predNodeInfo = GetNodeInfo(n.Child2); 

            nodeInfo.Definitions.Or(leftRelOpNodeInfo.Definitions);
            nodeInfo.Definitions.Or(rightRelOpNodeInfo.Definitions);
 
            nodeInfo.ExternalReferences.Or(leftRelOpNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Or(rightRelOpNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Or(predNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions);
 
            nodeInfo.Keys.InitFrom(leftRelOpNodeInfo.Keys, rightRelOpNodeInfo.Keys);

            RowCount maxRows;
            RowCount minRows; 
            if (op.OpType == OpType.FullOuterJoin)
            { 
                minRows = RowCount.Zero; 
                maxRows = RowCount.Unbounded;
            } 
            else
            {
                if ((leftRelOpNodeInfo.MaxRows > RowCount.One) ||
                    (rightRelOpNodeInfo.MaxRows > RowCount.One)) 
                {
                    maxRows = RowCount.Unbounded; 
                } 
                else
                { 
                    maxRows = RowCount.One;
                }

                if (op.OpType == OpType.LeftOuterJoin) 
                {
                    minRows = leftRelOpNodeInfo.MinRows; 
                } 
                else
                { 
                    minRows = RowCount.Zero;
                }
            }
 
            nodeInfo.SetRowCount(minRows, maxRows);
 
            return nodeInfo; 
        }
 
        /// 
        /// Computes a NodeInfo for a CrossApply/OuterApply op.
        /// Definitions = Definitions of my children
        /// LocalDefinitions = None 
        /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
        /// External References = any external references from the inputs 
        /// RowCount: 
        ///    CrossApply: minRows=0; MaxRows=Unbounded
        ///         (MaxRows = 1, if both inputs have MaxRow less than or equal to 1) 
        ///    OuterApply: minRows=leftInput.MinRows; MaxRows=Unbounded
        ///         (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
        ///
        ///  
        /// The ApplyOp
        /// corresponding Node 
        ///  
        protected override NodeInfo VisitApplyOp(ApplyBaseOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);

            ExtendedNodeInfo leftRelOpNodeInfo = GetExtendedNodeInfo(n.Child0);
            ExtendedNodeInfo rightRelOpNodeInfo = GetExtendedNodeInfo(n.Child1); 

            nodeInfo.Definitions.Or(leftRelOpNodeInfo.Definitions); 
            nodeInfo.Definitions.Or(rightRelOpNodeInfo.Definitions); 

            nodeInfo.ExternalReferences.Or(leftRelOpNodeInfo.ExternalReferences); 
            nodeInfo.ExternalReferences.Or(rightRelOpNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions);

            nodeInfo.Keys.InitFrom(leftRelOpNodeInfo.Keys, rightRelOpNodeInfo.Keys); 

            RowCount maxRows; 
            if (leftRelOpNodeInfo.MaxRows <= RowCount.One && 
                rightRelOpNodeInfo.MaxRows <= RowCount.One)
            { 
                maxRows = RowCount.One;
            }
            else
            { 
                maxRows = RowCount.Unbounded;
            } 
            RowCount minRows = (op.OpType == OpType.CrossApply) ? RowCount.Zero : leftRelOpNodeInfo.MinRows; 
            nodeInfo.SetRowCount(minRows, maxRows);
 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for SetOps (UnionAll, Intersect, Except).
        /// Definitions = OutputVars 
        /// LocalDefinitions = OutputVars 
        /// Keys = Output Vars for Intersect, Except. For UnionAll ??
        /// External References = any external references from the inputs 
        /// RowCount: Min = 0, Max = unbounded.
        ///    For UnionAlls, MinRows = max(MinRows of left and right inputs)
        ///
        ///  
        /// The SetOp
        /// corresponding Node 
        ///  
        protected override NodeInfo VisitSetOp(SetOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);

            // My definitions and my "all" definitions are simply my outputs
            nodeInfo.Definitions.InitFrom(op.Outputs); 
            nodeInfo.LocalDefinitions.InitFrom(op.Outputs);
 
            RowCount minRows = RowCount.Zero; 
            // My external references are the external references of each of
            // my inputs 
            foreach (Node chi in n.Children)
            {
                ExtendedNodeInfo chiRelOpNodeInfo = GetExtendedNodeInfo(chi);
                nodeInfo.ExternalReferences.Or(chiRelOpNodeInfo.ExternalReferences); 
                if ((op.OpType == OpType.UnionAll) &&
                    (chiRelOpNodeInfo.MinRows > minRows)) 
                { 
                    minRows = chiRelOpNodeInfo.MinRows;
                } 
            }

            // for intersect, and exceptOps, the keys are simply the outputs.
            if (op.OpType == OpType.Intersect || op.OpType == OpType.Except) 
            {
                nodeInfo.Keys.InitFrom(op.Outputs); 
            } 
            else
            { 
                // UnionAlls are a lot more complicated.  If we've gone through
                // keyPullup, we will have set some keys on it's input branches and
                // what we need to do here is get the keys from each branch and re-map
                // them to the output vars. 
                //
                // If the branchDiscriminator is not set on the unionAllOp, then 
                // we haven't been through key pullup and we can't look at the keys 
                // that the child nodes have, because they're not discriminated.
                // 
                // See the logic in KeyPullup, where we make sure that there are
                // actually branch discriminators on the input branches.
                UnionAllOp unionAllOp = (UnionAllOp)op;
 
                if (null == unionAllOp.BranchDiscriminator)
                { 
                    nodeInfo.Keys.NoKeys = true; 
                }
                else 
                {
                    VarVec nodeKeys = m_command.CreateVarVec();
                    VarVec mappedKeyVec;
                    for (int i = 0; i < n.Children.Count; i++) 
                    {
                        ExtendedNodeInfo childNodeInfo = n.Children[i].GetExtendedNodeInfo(m_command); 
                        if (!childNodeInfo.Keys.NoKeys && !childNodeInfo.Keys.KeyVars.IsEmpty) 
                        {
                            mappedKeyVec = childNodeInfo.Keys.KeyVars.Remap(unionAllOp.VarMap[i].GetReverseMap()); 
                            nodeKeys.Or(mappedKeyVec);
                        }
                        else
                        { 
                            // Each branch had better have keys, or we can't continue.
                            nodeKeys.Clear(); 
                            break; 
                        }
                    } 

                    // You might be tempted to ask: "Don't we need to add the branch discriminator
                    // to the keys as well?"  The reason we don't is that we wouldn't be here unless
                    // we have a branch discriminator variable, which implies we've pulled up keys on 
                    // the inputs, and they'll already have the branch descriminator set in the keys
                    // of each input, so we don't need to add that... 
                    if (nodeKeys.IsEmpty) 
                    {
                        nodeInfo.Keys.NoKeys = true; 
                    }
                    else
                    {
                        nodeInfo.Keys.InitFrom(nodeKeys); 
                    }
                } 
            } 

            nodeInfo.MinRows = minRows; 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for a ConstrainedSortOp/SortOp.
        /// Definitions = Definitions of the input Relop 
        /// LocalDefinitions = not allowed 
        /// Keys = Keys of the input Relop
        /// External References = any external references from the input + any external 
        ///    references from the predicate
        /// RowCount = Input's RowCount
        /// 
        /// The SortOp 
        /// corresponding Node
        ///  
        protected override NodeInfo VisitSortOp(SortBaseOp op, Node n) 
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 
            ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);

            // definitions are my child's definitions
            nodeInfo.Definitions.Or(relOpChildNodeInfo.Definitions); 

            // My references are my child's external references + those made 
            // by my sort keys 
            nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions); 

            // my keys are my child's keys
            nodeInfo.Keys.InitFrom(relOpChildNodeInfo.Keys);
            nodeInfo.InitRowCountFrom(relOpChildNodeInfo); 

            // For constrained sort, if the Limit value is Constant(1) and WithTies is false, 
            // then MinRows and MaxRows can be adjusted to 0, 1. 
            if (OpType.ConstrainedSort == op.OpType &&
                OpType.Constant == n.Child2.Op.OpType && 
                !((ConstrainedSortOp)op).WithTies)
            {
                ConstantBaseOp constOp = (ConstantBaseOp)n.Child2.Op;
                if(TypeHelpers.IsIntegerConstant(constOp.Type, constOp.Value, 1)) 
                {
                    nodeInfo.SetRowCount(RowCount.Zero, RowCount.One); 
                } 
            }
 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for Distinct.
        /// Definitions = OutputVars 
        /// LocalDefinitions = None 
        /// Keys = Output Vars
        /// External References = any external references from the inputs 
        /// RowCount = Input's RowCount
        /// 
        /// The DistinctOp
        /// corresponding Node 
        /// 
        public override NodeInfo Visit(DistinctOp op, Node n) 
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            // no local definitions - definitions are just the keys 
            nodeInfo.Definitions.InitFrom(op.Keys);

            //#497217 - The parameters should not be included as keys
            nodeInfo.Keys.InitFrom(op.Keys, true); 

            // external references - inherit from child 
            ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0); 
            nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
            nodeInfo.InitRowCountFrom(childNodeInfo); 
            return nodeInfo;
        }

        ///  
        /// Compute NodeInfo for a SingleRowOp.
        /// Definitions = child's definitions 
        /// Keys = child's keys 
        /// Local Definitions = none
        /// External references = child's external references 
        /// RowCount=(0,1)
        /// 
        /// The SingleRowOp
        /// current subtree 
        /// NodeInfo for this node
        public override NodeInfo Visit(SingleRowOp op, Node n) 
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0); 
            nodeInfo.Definitions.InitFrom(childNodeInfo.Definitions);
            nodeInfo.Keys.InitFrom(childNodeInfo.Keys);
            nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
            nodeInfo.SetRowCount(RowCount.Zero, RowCount.One); 
            return nodeInfo;
        } 
 
        /// 
        /// SingleRowTableOp 
        /// No definitions, external references.
        /// Keys = empty list (not the same as "no keys")
        /// RowCount = (1,1)
        ///  
        /// the SingleRowTableOp
        /// current subtree 
        /// nodeInfo for this subtree 
        public override NodeInfo Visit(SingleRowTableOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            nodeInfo.Keys.NoKeys = false;
            nodeInfo.SetRowCount(RowCount.One, RowCount.One);
            return nodeInfo; 
        }
 
        #endregion 

        #region PhysicalOps 
        /// 
        /// Computes a NodeInfo for a PhysicalProjectOp.
        /// Definitions = OutputVars
        /// LocalDefinitions = None 
        /// Keys = None
        /// External References = any external references from the inputs 
        /// RowCount=default 
        /// 
        /// The PhysicalProjectOp 
        /// corresponding Node
        /// 
        public override NodeInfo Visit(PhysicalProjectOp op, Node n)
        { 
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
            foreach (Node chi in n.Children) 
            { 
                NodeInfo childNodeInfo = GetNodeInfo(chi);
                nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences); 
            }
            nodeInfo.Definitions.InitFrom(op.Outputs);
            nodeInfo.LocalDefinitions.InitFrom(nodeInfo.Definitions);
 
            //
            // Inherit the keys from the child - but only if all the columns were projected 
            // out 
            //
            ExtendedNodeInfo driverChildNodeInfo = GetExtendedNodeInfo(n.Child0); 
            if (!driverChildNodeInfo.Keys.NoKeys)
            {
                VarVec missingKeys = m_command.CreateVarVec(driverChildNodeInfo.Keys.KeyVars);
                missingKeys.Minus(nodeInfo.Definitions); 
                if (missingKeys.IsEmpty)
                { 
                    nodeInfo.Keys.InitFrom(driverChildNodeInfo.Keys); 
                }
            } 
            return nodeInfo;
        }

        ///  
        /// Computes a NodeInfo for a NestOp (SingleStream/MultiStream).
        /// Definitions = OutputVars 
        /// LocalDefinitions = Collection Vars 
        /// Keys = Keys of my child
        /// External References = any external references from the inputs 
        /// RowCount=default
        /// 
        /// The NestOp
        /// corresponding Node 
        /// 
        protected override NodeInfo VisitNestOp(NestBaseOp op, Node n) 
        { 
            SingleStreamNestOp ssnOp = op as SingleStreamNestOp;
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n); 

            foreach (CollectionInfo ci in op.CollectionInfo)
            {
                nodeInfo.LocalDefinitions.Set(ci.CollectionVar); 
            }
            nodeInfo.Definitions.InitFrom(op.Outputs); 
 
            // get external references from each child
            foreach (Node chi in n.Children) 
            {
                nodeInfo.ExternalReferences.Or(GetExtendedNodeInfo(chi).ExternalReferences);
            }
 
            // eliminate things I may have defined already (left correlation)
            nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions); 
 
            // Keys are from the driving node only.
            if (ssnOp == null) 
            {
                nodeInfo.Keys.InitFrom(GetExtendedNodeInfo(n.Child0).Keys);
            }
            else 
            {
                nodeInfo.Keys.InitFrom(ssnOp.Keys); 
            } 
            return nodeInfo;
        } 

        #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