path: root/mcs/class/referencesource/System.Data.Entity/System/Data/Query/InternalTrees/NodeInfo.cs

//---------------------------------------------------------------------
// <copyright file="NodeInfo.cs" company="Microsoft">
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>
//
// @owner  [....]
// @backupOwner [....]
//---------------------------------------------------------------------

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
{
    /// <summary>
    /// 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
    /// </summary>
    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<Var> varSet)
        {
            InitFrom(varSet, false);
        }

        internal void InitFrom(IEnumerable<Var> 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<KeyVec> 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; } }
    }

    /// <summary>
    /// 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
    /// NOTE: When adding a new member to track inforation, make sure to update the Clear method 
    /// in this class to set that member to the default value.
    /// </summary>
    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
        /// <summary>
        /// Clear out all information - usually used by a Recompute
        /// </summary>
        internal virtual void Clear()
        {
            m_externalReferences.Clear();
            m_hashValue = 0;
        }

        /// <summary>
        /// All external references from this node
        /// </summary>
        internal VarVec ExternalReferences
        {
            get { return m_externalReferences; }
        }

        /// <summary>
        /// Get the hash value for this nodeInfo
        /// </summary>
        internal int HashValue
        {
            get { return m_hashValue; }
        }

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

        /// <summary>
        /// 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
        /// </summary>
        /// <param name="cmd">current command</param>
        /// <param name="n">current node</param>
        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
    }

    /// <summary>
    /// Enum describing row counts
    /// </summary>
    internal enum RowCount : byte
    {
        /// <summary>
        /// Zero rows
        /// </summary>
        Zero = 0,

        /// <summary>
        /// One row
        /// </summary>
        One = 1,

        /// <summary>
        /// Unbounded (unknown number of rows)
        /// </summary>
        Unbounded = 2,
    }

    /// <summary>
    /// 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
    /// - a set of keys
    /// - a set of non-nullable definitions 
    /// - a set of non-nullable definitions that are visible at this node
    /// NOTE: When adding a new member to track inforation, make sure to update the Clear method 
    /// in this class to set that member to the default value.
    /// </summary>
    internal class ExtendedNodeInfo : NodeInfo
    {
        #region private
        private VarVec m_localDefinitions;
        private VarVec m_definitions;
        private KeyVec m_keys;
        private VarVec m_nonNullableDefinitions;
        private VarVec m_nonNullableVisibleDefinitions;
        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_nonNullableDefinitions = cmd.CreateVarVec();
            m_nonNullableVisibleDefinitions = 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_nonNullableDefinitions.Clear();
            m_nonNullableVisibleDefinitions.Clear();
            m_keys.Clear();
            m_minRows = RowCount.Zero;
            m_maxRows = RowCount.Unbounded;
        }

        /// <summary>
        /// Compute the hash value for this node
        /// </summary>
        /// <param name="cmd"></param>
        /// <param name="n"></param>
        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;
        }

        /// <summary>
        /// Definitions made specifically by this node
        /// </summary>
        internal VarVec LocalDefinitions { get { return m_localDefinitions; } }
        /// <summary>
        /// All definitions visible as outputs of this node
        /// </summary>
        internal VarVec Definitions { get { return m_definitions; } }
        /// <summary>
        /// The keys for this node
        /// </summary>
        internal KeyVec Keys { get { return m_keys; } }
        /// <summary>
        /// The definitions of vars that are guaranteed to be non-nullable when output from this node
        /// </summary>
        internal VarVec NonNullableDefinitions { get { return m_nonNullableDefinitions; } }
        /// <summary>
        /// The definitions that come from the rel-op inputs of this node that are guaranteed to be non-nullable
        /// </summary>
        internal VarVec NonNullableVisibleDefinitions { get { return m_nonNullableVisibleDefinitions; } }
        /// <summary>
        /// Min number of rows returned from this node
        /// </summary>
        internal RowCount MinRows
        {
            get { return m_minRows; }
            set { m_minRows = value; ValidateRowCount(); }
        }
        /// <summary>
        /// Max rows returned from this node
        /// </summary>
        internal RowCount MaxRows
        {
            get { return m_maxRows; }
            set { m_maxRows = value; ValidateRowCount(); }
        }

        /// <summary>
        /// Set the rowcount for this node
        /// </summary>
        /// <param name="minRows">min rows produced by this node</param>
        /// <param name="maxRows">max rows produced by this node</param>
        internal void SetRowCount(RowCount minRows, RowCount maxRows)
        {
            m_minRows = minRows;
            m_maxRows = maxRows;
            ValidateRowCount();
        }

        /// <summary>
        /// Initialize the rowcounts for this node from the source node
        /// </summary>
        /// <param name="source">nodeinfo of source</param>
        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
    }

    /// <summary>
    /// The NodeInfoVisitor is a simple class (ab)using the Visitor pattern to define
    /// NodeInfo semantics for various nodes in the tree
    /// </summary>
    internal class NodeInfoVisitor : BasicOpVisitorOfT<NodeInfo>
    {
        #region public methods
        /// <summary>
        /// The only public method. Recomputes the nodeInfo for a node in the tree, 
        /// but only if the node info has already been computed.  
        /// Assumes that the NodeInfo for each child (if computed already) is valid
        /// </summary>
        /// <param name="n">Node to get NodeInfo for</param>
        internal void RecomputeNodeInfo(Node n)
        {
            if (n.IsNodeInfoInitialized)
            {
                NodeInfo nodeInfo = VisitNode(n);
                nodeInfo.ComputeHashValue(this.m_command, n); // compute the hash value for this node
            }
        }
        #endregion

        #region constructors
        /// <summary>
        /// Basic constructor
        /// </summary>
        /// <param name="command"></param>
        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
        /// <summary>
        /// Default implementation for scalarOps. Simply adds up external references
        /// from each child
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        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;
        }

        /// <summary>
        /// The given definition is non nullable if it is a non-null constant
        /// or a reference to non-nullable input
        /// </summary>
        /// <param name="definition"></param>
        /// <param name="nonNullableInputs"></param>
        /// <returns></returns>
        private bool IsDefinitionNonNullable(Node definition, VarVec nonNullableInputs)
        {
            return (definition.Op.OpType == OpType.Constant
                || definition.Op.OpType == OpType.InternalConstant
                || definition.Op.OpType == OpType.NullSentinel
                || definition.Op.OpType == OpType.VarRef
                    && nonNullableInputs.IsSet(((VarRefOp)definition.Op).Var));      
        }
        #endregion

        #region IOpVisitor<NodeInfo> Members

        #region MiscOps
        #endregion

        #region AncillarOps
        #endregion

        #region ScalarOps
        /// <summary>
        /// The only special case among all scalar and ancillaryOps. Simply adds
        /// its var to the list of unreferenced Ops
        /// </summary>
        /// <param name="op">The VarRefOp</param>
        /// <param name="n">Current node</param>
        /// <returns></returns>
        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);
        }

        /// <summary>
        /// Definitions = Local Definitions = referenced table columns
        /// External References = none
        /// Keys = keys of entity type
        /// RowCount (default): MinRows = 0, MaxRows = * 
        /// NonNullableDefinitions : non nullable table columns that are definitions
        /// NonNullableInputDefinitions : default(empty) because cannot be used
        /// </summary>
        /// <param name="op">ScanTable/ScanView op</param>
        /// <param name="n">current subtree</param>
        /// <returns>nodeinfo for this subtree</returns>
        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

            //non-nullable definitions
            nodeInfo.NonNullableDefinitions.Or(op.Table.NonNullableColumns);
            nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions);

            return nodeInfo;
        }

        /// <summary>
        /// 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 = *
        /// NonNullableDefinitions: default(empty) 
        /// NonNullableInputDefinitions : default(empty) because cannot be used
        /// </summary>
        /// <param name="op"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        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);
            }

            // Process keys if it's a TVF with inferred keys, otherwise - no keys.
            if (n.Child0.Op.OpType == OpType.VarDef && n.Child0.Child0.Op.OpType == OpType.Function && op.Table.Keys.Count > 0)
            {
                // This is a TVF case. 
                // Get table's keys - but only if they have been referenced.
                if (op.Table.ReferencedColumns.Subsumes(op.Table.Keys))
                {
                    nodeInfo.Keys.InitFrom(op.Table.Keys);
                }
            }
            else
            {
                // no keys
                Debug.Assert(nodeInfo.Keys.NoKeys, "UnnestOp should have no keys in all cases except TVFs mapped to entities.");
            }

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

        /// <summary>
        /// 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
        /// </summary>
        /// <param name="varDefListNode">the varDefListNode subtree</param>
        /// <returns>A dictionary of Var->Var renames</returns>
        internal static Dictionary<Var, Var> ComputeVarRemappings(Node varDefListNode)
        {
            Debug.Assert(varDefListNode.Op.OpType == OpType.VarDefList);

            Dictionary<Var, Var> varMap = new Dictionary<Var, Var>();
            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;
        }

        /// <summary>
        /// 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
        /// NonNullabeDefinitions = Outputs that are either among the NonNullableDefinitions of the child or
        ///                         are constants defined on this node
        /// NonNullableInputDefinitions = NonNullableDefinitions of the child 
        /// </summary>
        /// <param name="op">The ProjectOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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);
                }
            }

            //Nonnullable definitions 
            nodeInfo.NonNullableDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableDefinitions.And(op.Outputs);          
            nodeInfo.NonNullableVisibleDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);

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

                if (IsDefinitionNonNullable(chi.Child0, nodeInfo.NonNullableVisibleDefinitions))
                {
                    nodeInfo.NonNullableDefinitions.Set(varDefOp.Var);
                }
            }
            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<Var, Var> 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;
        }

        /// <summary>
        /// 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
        /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp
        /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp
        /// </summary>
        /// <param name="op">The FilterOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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);

            //The non-nullable definitions are same as these of the child
            nodeInfo.NonNullableDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableVisibleDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
            
            // 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;
        }
        
        /// <summary>
        /// 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 = 
        ///          (1,1) if no group-by keys; 
        ///          otherwise if input MinRows is 1 then (1, input MaxRows); 
        ///          otherwise (0, input MaxRows)
        /// NonNullableDefinitions: non-nullable keys
        /// NonNullableInputDefinitions : default(empty)        
        /// </summary>
        /// <param name="op">The GroupByOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        protected override NodeInfo VisitGroupByOp(GroupByBaseOp 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);
                if (IsDefinitionNonNullable(chi.Child0, relOpChildNodeInfo.NonNullableDefinitions))
                {
                    nodeInfo.NonNullableDefinitions.Set(((VarDefOp)chi.Op).Var);
                }
            }

            // Non-nullable definitions: also all the keys that come from the input
            nodeInfo.NonNullableDefinitions.Or(relOpChildNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableDefinitions.And(op.Keys);

            //Handle all aggregates
            for (int i = 2; i < n.Children.Count; i++)
            {
                foreach (Node chi in n.Children[i].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);

            // row counts
            nodeInfo.MinRows = op.Keys.IsEmpty ? RowCount.One : (relOpChildNodeInfo.MinRows == RowCount.One ? RowCount.One : RowCount.Zero);
            nodeInfo.MaxRows = op.Keys.IsEmpty ? RowCount.One : relOpChildNodeInfo.MaxRows;

            return nodeInfo;
        }

        /// <summary>
        /// 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)
        /// NonNullableDefinitions : The NonNullableDefinitions of the children
        /// NonNullableInputDefinitions : default(empty) because cannot be used
        /// </summary>
        /// <param name="op">The CrossJoinOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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<KeyVec> keyVecList = new List<KeyVec>();
            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);

                nodeInfo.NonNullableDefinitions.Or(chiNodeInfo.NonNullableDefinitions);

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

        /// <summary>
        /// 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
        /// NonNullableDefinitions:
        ///    FullOuterJoin: None.
        ///    InnerJoin: NonNullableDefinitions of both children
        ///    LeftOuterJoin: NonNullableDefinitions of the left child
        /// NonNullableInputDefinitions : NonNullabeDefinitions of both children  
        /// </summary>
        /// <param name="op">The JoinOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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);

            //Non-nullable definitions
            if (op.OpType == OpType.InnerJoin || op.OpType == OpType.LeftOuterJoin)
            {
                nodeInfo.NonNullableDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);
            }
            if (op.OpType == OpType.InnerJoin)
            {
                nodeInfo.NonNullableDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);
            }
            nodeInfo.NonNullableVisibleDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableVisibleDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);

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

        /// <summary>
        /// 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)
        /// NonNullableDefinitions = 
        ///    CrossApply: NonNullableDefinitions of both children
        ///    OuterApply: NonNullableDefinitions of the left child
        /// NonNullableInputDefinitions = NonNullabeDefinitions of both children  
        /// </summary>
        /// <param name="op">The ApplyOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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);

            //NonNullableDefinitions
            nodeInfo.NonNullableDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);          
            if (op.OpType == OpType.CrossApply)
            {
                nodeInfo.NonNullableDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);
            }
            nodeInfo.NonNullableVisibleDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableVisibleDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);

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

        /// <summary>
        /// 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)
        /// NonNullable definitions =   
        ///     UnionAll - Columns that are NonNullableDefinitions on both (children) sides
        ///     Except  - Columns that are NonNullableDefinitions on the left child side
        ///     Intersect - Columns that are NonNullableDefinitions on either side
        /// NonNullableInputDefinitions = default(empty) because cannot be used
        /// </summary>
        /// <param name="op">The SetOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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);

            ExtendedNodeInfo leftChildNodeInfo = GetExtendedNodeInfo(n.Child0);
            ExtendedNodeInfo rightChildNodeInfo = GetExtendedNodeInfo(n.Child1);

            RowCount minRows = RowCount.Zero;
            
            // My external references are the external references of both of 
            // my inputs
            nodeInfo.ExternalReferences.Or(leftChildNodeInfo.ExternalReferences);
            nodeInfo.ExternalReferences.Or(rightChildNodeInfo.ExternalReferences);

            if (op.OpType == OpType.UnionAll) 
            {
                minRows = (leftChildNodeInfo.MinRows > rightChildNodeInfo.MinRows) ? leftChildNodeInfo.MinRows  : rightChildNodeInfo.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);
                    }
                }
            }

            //Non-nullable definitions
            VarVec leftNonNullableVars = leftChildNodeInfo.NonNullableDefinitions.Remap(op.VarMap[0].GetReverseMap());
            nodeInfo.NonNullableDefinitions.InitFrom(leftNonNullableVars);
            
            if (op.OpType != OpType.Except)
            {
                VarVec rightNonNullableVars = rightChildNodeInfo.NonNullableDefinitions.Remap(op.VarMap[1].GetReverseMap());
                if (op.OpType == OpType.Intersect)
                {
                    nodeInfo.NonNullableDefinitions.Or(rightNonNullableVars);
                }
                else  //Union all
                {
                    nodeInfo.NonNullableDefinitions.And(rightNonNullableVars);
                }
            }

            nodeInfo.NonNullableDefinitions.And(op.Outputs);

            nodeInfo.MinRows = minRows;
            return nodeInfo;
        }

        /// <summary>
        /// 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 keys
        /// RowCount = Input's RowCount
        /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp
        /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp
        /// </summary>
        /// <param name="op">The SortOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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);

            //Non-nullable definitions are same as the input
            nodeInfo.NonNullableDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableVisibleDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
            
            //Row counts are same as the input
            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;
        }

        /// <summary>
        /// Computes a NodeInfo for Distinct.
        /// Definitions = OutputVars that are not external references
        /// LocalDefinitions = None
        /// Keys = Output Vars 
        /// External References = any external references from the inputs 
        /// RowCount = Input's RowCount
        /// NonNullabeDefinitions : NonNullabeDefinitions of the input RelOp that are outputs
        /// NonNullableInputDefinitions : default(empty) because cannot be used
        /// </summary>
        /// <param name="op">The DistinctOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        public override NodeInfo Visit(DistinctOp op, Node n)
        {
            ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);

            //#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);

            // no local definitions - definitions are just the keys that are not external references
            foreach (Var v in op.Keys)
            {
                if (childNodeInfo.Definitions.IsSet(v))
                {
                    nodeInfo.Definitions.Set(v);
                }
                else
                {
                    nodeInfo.ExternalReferences.Set(v);
                }
            }

            //Non-nullable definitions
            nodeInfo.NonNullableDefinitions.InitFrom(childNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableDefinitions.And(op.Keys);

            nodeInfo.InitRowCountFrom(childNodeInfo);
            return nodeInfo;
        }

        /// <summary>
        /// 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)
        /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp
        /// NonNullableInputDefinitions : default(empty) because cannot be used        
        /// </summary>
        /// <param name="op">The SingleRowOp</param>
        /// <param name="n">current subtree</param>
        /// <returns>NodeInfo for this node</returns>
        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.NonNullableDefinitions.InitFrom(childNodeInfo.NonNullableDefinitions);
            nodeInfo.SetRowCount(RowCount.Zero, RowCount.One);
            return nodeInfo;
        }

        /// <summary>
        /// SingleRowTableOp
        /// No definitions, external references, non-nullable definitions
        /// Keys = empty list (not the same as "no keys")
        /// RowCount = (1,1)
        /// </summary>
        /// <param name="op">the SingleRowTableOp</param>
        /// <param name="n">current subtree</param>
        /// <returns>nodeInfo for this subtree</returns>
        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
        /// <summary>
        /// Computes a NodeInfo for a PhysicalProjectOp.
        /// Definitions = OutputVars
        /// LocalDefinitions = None
        /// Keys = None
        /// External References = any external references from the inputs
        /// RowCount=default
        /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp that are among the definitions
        /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp
        /// </summary>
        /// <param name="op">The PhysicalProjectOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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);
                }
            }

            //Non-nullable definitions
            nodeInfo.NonNullableDefinitions.Or(driverChildNodeInfo.NonNullableDefinitions);
            nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions);
            nodeInfo.NonNullableVisibleDefinitions.Or(driverChildNodeInfo.NonNullableVisibleDefinitions);

            return nodeInfo;
        }

        /// <summary>
        /// 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
        /// </summary>
        /// <param name="op">The NestOp</param>
        /// <param name="n">corresponding Node</param>
        /// <returns></returns>
        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
    }
}