internal Table(Command command, TableMD tableMetadata, int tableId)
        {
            m_tableMetadata = tableMetadata;
            m_columns = Command.CreateVarList();
            m_keys = command.CreateVarVec();
            m_nonnullableColumns = command.CreateVarVec();
            m_tableId = tableId;

            var columnVarMap = new Dictionary<string, ColumnVar>();
            foreach (var c in tableMetadata.Columns)
            {
                var v = command.CreateColumnVar(this, c);
                columnVarMap[c.Name] = v;
                if (!c.IsNullable)
                {
                    m_nonnullableColumns.Set(v);
                }
            }

            foreach (var c in tableMetadata.Keys)
            {
                var v = columnVarMap[c.Name];
                m_keys.Set(v);
            }

            m_referencedColumns = command.CreateVarVec(m_columns);
        }

        /// <summary>
        ///     Determines whether any var from a given list of keys is referenced by any of defining node's right relatives,
        ///     with the exception of the relatives brunching at the given targetJoinNode.
        /// </summary>
        /// <param name="keys"> A list of vars to check for </param>
        /// <param name="definingNode"> The node considered to be the defining node </param>
        /// <param name="targetJoinNode"> The relatives branching at this node are skipped </param>
        /// <returns> False, only it can determine that not a single var from a given list of keys is referenced by any of defining node's right relatives, with the exception of the relatives brunching at the given targetJoinNode. </returns>
        internal bool HasKeyReferences(VarVec keys, Node definingNode, Node targetJoinNode)
        {
            var currentChild = definingNode;
            Node parent;
            var continueUp = true;

            while (continueUp & m_nodeToParentMap.TryGetValue(currentChild, out parent))
            {
                if (parent != targetJoinNode)
                {
                    // Check the parent
                    if (HasVarReferencesShallow(parent, keys, m_nodeToSiblingNumber[currentChild], out continueUp))
                    {
                        return true;
                    }

                    //Check all the siblings to the right
                    for (var i = m_nodeToSiblingNumber[currentChild] + 1; i < parent.Children.Count; i++)
                    {
                        if (parent.Children[i].GetNodeInfo(m_command).ExternalReferences.Overlaps(keys))
                        {
                            return true;
                        }
                    }
                }
                currentChild = parent;
            }
            return false;
        }

 internal SetOp(OpType opType, VarVec outputs, VarMap left, VarMap right)
     : this(opType)
 {
     m_varMap = new VarMap[2];
     m_varMap[0] = left;
     m_varMap[1] = right;
     m_outputVars = outputs;
 }

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

 internal NestBaseOp(
     OpType opType, List<SortKey> prefixSortKeys,
     VarVec outputVars,
     List<CollectionInfo> collectionInfoList)
     : base(opType)
 {
     m_outputs = outputVars;
     m_collectionInfoList = collectionInfoList;
     m_prefixSortKeys = prefixSortKeys;
 }

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

 internal CollectionInfo(
     Var collectionVar, ColumnMap columnMap, VarList flattenedElementVars, VarVec keys, List<SortKey> sortKeys,
     object discriminatorValue)
 {
     m_collectionVar = collectionVar;
     m_columnMap = columnMap;
     m_flattenedElementVars = flattenedElementVars;
     m_keys = keys;
     m_sortKeys = sortKeys;
     m_discriminatorValue = discriminatorValue;
 }

 private static VarVec CreateVarVec(params int[] bits)
 {
     var command = new Mock<Command>();
     var vec = new VarVec(command.Object);
     bits.Each(b =>
                   {
                       var v = CreateVar(b);
                       vec.Set(v);
                       command.Setup(m => m.GetVar(b)).Returns(v);
                   });
     return vec;
 }

        /// <summary>
        ///     Split up a predicate into 2 parts - the pushdown and the non-pushdown predicate.
        ///     If the filter node has no external references *and* the "columns" parameter is null,
        ///     then the entire predicate can be pushed down
        ///     We then compute the set of valid column references - if the "columns" parameter
        ///     is non-null, this set is used. Otherwise, we get the definitions of the
        ///     input relop node of the filterOp, and use that.
        ///     We use this list of valid column references to identify which parts of the filter
        ///     predicate can be pushed down - only those parts of the predicate that do not
        ///     reference anything beyond these columns are considered for pushdown. The rest are
        ///     stuffed into the nonPushdownPredicate output parameter
        /// </summary>
        /// <param name="command"> Command object </param>
        /// <param name="filterNode"> the FilterOp subtree </param>
        /// <param name="columns"> (Optional) List of columns to consider for "pushdown" </param>
        /// <param name="nonPushdownPredicateNode"> (output) Part of the predicate that cannot be pushed down </param>
        /// <returns> part of the predicate that can be pushed down </returns>
        private static Node GetPushdownPredicate(Command command, Node filterNode, VarVec columns, out Node nonPushdownPredicateNode)
        {
            var pushdownPredicateNode = filterNode.Child1;
            nonPushdownPredicateNode = null;
            var filterNodeInfo = command.GetExtendedNodeInfo(filterNode);
            if (columns == null
                && filterNodeInfo.ExternalReferences.IsEmpty)
            {
                return pushdownPredicateNode;
            }

            if (columns == null)
            {
                var inputNodeInfo = command.GetExtendedNodeInfo(filterNode.Child0);
                columns = inputNodeInfo.Definitions;
            }

            var predicate = new Predicate(command, pushdownPredicateNode);
            Predicate nonPushdownPredicate;
            predicate = predicate.GetSingleTablePredicates(columns, out nonPushdownPredicate);
            pushdownPredicateNode = predicate.BuildAndTree();
            nonPushdownPredicateNode = nonPushdownPredicate.BuildAndTree();
            return pushdownPredicateNode;
        }

 /// <summary>
 ///     Does the list of outputs of the given SetOp contain a var
 ///     from the given VarVec defined by the SetOp's child with the given index
 /// </summary>
 private static bool HasVarReferences(SetOp op, VarVec vars, int index)
 {
     foreach (var var in op.VarMap[index].Values)
     {
         if (vars.IsSet(var))
         {
             return true;
         }
     }
     return false;
 }

 /// <summary>
 /// Creates a new GroupByIntoOp
 /// </summary>
 /// <param name="gbyKeys">A VarSet that specifies the Key variables produced by the GroupByOp</param>
 /// <param name="outputs">A VarSet that specifies the vars from the input that represent the real grouping input</param>
 /// <param name="inputs">A VarSet that specifies all (Key and Aggregate) variables produced by the GroupByOp</param>
 /// <returns>A new GroupByOp with the specified key and output VarSets</returns>
 internal GroupByIntoOp CreateGroupByIntoOp(VarVec gbyKeys, VarVec inputs, VarVec outputs)
 {
     return new GroupByIntoOp(gbyKeys, inputs, outputs);
 }

 /// <summary>
 /// Create a singleStreamNestOp
 /// </summary>
 /// <param name="keys">keys for the nest operation</param>
 /// <param name="prefixSortKeys">list of prefix sort keys</param>
 /// <param name="postfixSortKeys">list of postfix sort keys</param>
 /// <param name="outputVars">List of outputVars</param>
 /// <param name="collectionInfoList">CollectionInfo for each collection </param>
 /// <param name="discriminatorVar">Var describing the discriminator</param>
 /// <returns></returns>
 internal SingleStreamNestOp CreateSingleStreamNestOp(VarVec keys,
     List<SortKey> prefixSortKeys, List<SortKey> postfixSortKeys,
     VarVec outputVars,
     List<CollectionInfo> collectionInfoList, Var discriminatorVar)
 {
     return new SingleStreamNestOp(keys, prefixSortKeys, postfixSortKeys, outputVars, collectionInfoList, discriminatorVar);
 }

 /// <summary>
 /// Creates a new DistinctOp
 /// <param name="keyVars">list of key vars</param>
 /// </summary>
 /// <returns>A new DistinctOp</returns>
 internal DistinctOp CreateDistinctOp(VarVec keyVars)
 {
     return new DistinctOp(keyVars);
 }

 internal KeyVec(Command itree)
 {
     m_keys = itree.CreateVarVec();
     m_noKeys = true;
 }

 /// <summary>
 ///     Probe the current VarSet for "structured" Vars - replace these with the
 ///     corresponding sets of flattened Vars
 /// </summary>
 /// <param name="varSet"> current set of vars </param>
 /// <returns> an "expanded" varset </returns>
 private VarVec FlattenVarSet(VarVec varSet)
 {
     var newVarSet = m_command.CreateVarVec(FlattenVars(varSet));
     return newVarSet;
 }

        // <summary>
        // Convert a CollectOp subtree (when used as the defining expression for a
        // VarDefOp) into a reasonable input to a NestOp.
        // </summary>
        // <remarks>
        // There are a couple of cases that we handle here:
        // (a) PhysicalProject(X) ==> X
        // (b) PhysicalProject(Sort(X)) ==> Sort(X)
        // </remarks>
        // <param name="physicalProjectNode"> the child of the CollectOp </param>
        // <param name="collectionVar"> the collectionVar being defined </param>
        // <param name="collectionInfoList"> where to append the new collectionInfo </param>
        // <param name="collectionNodes"> where to append the collectionNode </param>
        // <param name="externalReferences"> a bit vector of external references of the physicalProject </param>
        // <param name="collectionReferences"> a bit vector of collection vars </param>
        private void ConvertToNestOpInput(
            Node physicalProjectNode, Var collectionVar, List<CollectionInfo> collectionInfoList, List<Node> collectionNodes,
            VarVec externalReferences, VarVec collectionReferences)
        {
            // Keep track of any external references the physicalProjectOp has
            externalReferences.Or(Command.GetNodeInfo(physicalProjectNode).ExternalReferences);

            // Case: (a) PhysicalProject(X) ==> X
            var nestOpInput = physicalProjectNode.Child0;

            // Now build the collectionInfo for this input, including the flattened
            // list of vars, which is essentially the outputs from the physicalProject
            // with the sortKey vars that aren't already in the outputs we already 
            // have.
            var physicalProjectOp = (PhysicalProjectOp)physicalProjectNode.Op;
            var flattenedElementVarList = Command.CreateVarList(physicalProjectOp.Outputs);
            var flattenedElementVarVec = Command.CreateVarVec(flattenedElementVarList); // Use a VarVec to make the lookups faster
            List<SortKey> sortKeys = null;

            if (OpType.Sort
                == nestOpInput.Op.OpType)
            {
                // Case: (b) PhysicalProject(Sort(X)) ==> Sort(X)
                var sortOp = (SortOp)nestOpInput.Op;
                sortKeys = OpCopier.Copy(Command, sortOp.Keys);

                foreach (var sk in sortKeys)
                {
                    if (!flattenedElementVarVec.IsSet(sk.Var))
                    {
                        flattenedElementVarList.Add(sk.Var);
                        flattenedElementVarVec.Set(sk.Var);
                    }
                }
            }
            else
            {
                sortKeys = new List<SortKey>();
            }

            // Get the keys for the collection
            var keyVars = Command.GetExtendedNodeInfo(nestOpInput).Keys.KeyVars;

            //Check whether all key are projected
            var keyVarsClone = keyVars.Clone();
            keyVarsClone.Minus(flattenedElementVarVec);

            var keys = (keyVarsClone.IsEmpty) ? keyVars.Clone() : Command.CreateVarVec();

            // Create the collectionInfo
            var collectionInfo = Command.CreateCollectionInfo(
                collectionVar, physicalProjectOp.ColumnMap.Element, flattenedElementVarList, keys, sortKeys, null /*discriminatorValue*/);

            // Now update the collections we're tracking.
            collectionInfoList.Add(collectionInfo);
            collectionNodes.Add(nestOpInput);
            collectionReferences.Set(collectionVar);
        }

 /// <summary>
 /// Create a new VarVec from the input VarVec
 /// </summary>
 /// <param name="v"></param>
 /// <returns></returns>
 internal VarVec CreateVarVec(VarVec v)
 {
     VarVec vec = CreateVarVec();
     vec.InitFrom(v);
     return vec;
 }

 /// <summary>
 /// Create a MultiStreamNestOp
 /// </summary>
 /// <param name="prefixSortKeys">list of prefix sort keys</param>
 /// <param name="outputVars">List of outputVars</param>
 /// <param name="collectionInfoList">CollectionInfo for each collection element</param>
 /// <returns></returns>
 internal MultiStreamNestOp CreateMultiStreamNestOp(List<SortKey> prefixSortKeys, VarVec outputVars,
     List<CollectionInfo> collectionInfoList)
 {
     return new MultiStreamNestOp(prefixSortKeys, outputVars, collectionInfoList);
 }

        protected int m_hashValue; // hash value for the node

        #endregion

        #region constructors

        internal NodeInfo(Command cmd)
        {
            m_externalReferences = cmd.CreateVarVec();
        }

        /// <summary>
        ///     Checks whether the given node has references to any of the vars in the given VarVec.
        ///     It only checks the given node, not its children.
        /// </summary>
        /// <param name="node"> The node to check </param>
        /// <param name="vars"> The list of vars to check for </param>
        /// <param name="childIndex"> The index of the node's subree from which this var is coming. This is used for SetOp-s, to be able to locate the appropriate var map that will give the vars corresponding to the given once </param>
        /// <param name="continueUp"> If the OpType of the node's Op is such that it 'hides' the input, i.e. the decision of whether the given vars are referenced can be made on this level, it returns true, false otherwise </param>
        /// <returns> True if the given node has references to any of the vars in the given VarVec, false otherwise </returns>
        private static bool HasVarReferencesShallow(Node node, VarVec vars, int childIndex, out bool continueUp)
        {
            switch (node.Op.OpType)
            {
                case OpType.ConstrainedSort:
                case OpType.Sort:
                    continueUp = true;
                    return HasVarReferences(((SortBaseOp)node.Op).Keys, vars);

                case OpType.Distinct:
                    continueUp = false;
                    return HasVarReferences(((DistinctOp)node.Op).Keys, vars);

                case OpType.Except:
                case OpType.Intersect:
                case OpType.UnionAll:
                    continueUp = false;
                    return HasVarReferences((SetOp)node.Op, vars, childIndex);

                case OpType.GroupBy:
                    continueUp = false;
                    return HasVarReferences(((GroupByOp)node.Op).Keys, vars);

                case OpType.PhysicalProject:
                    continueUp = false;
                    return HasVarReferences(((PhysicalProjectOp)node.Op).Outputs, vars);

                case OpType.Project:
                    continueUp = false;
                    return HasVarReferences(((ProjectOp)node.Op).Outputs, vars);

                default:
                    continueUp = true;
                    return false;
            }
        }