Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / InternalTrees / NodeInfo.cs / 1305376 / NodeInfo.cs
//---------------------------------------------------------------------- //// Copyright (c) Microsoft Corporation. All rights reserved. // // // @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 { ////// 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(ListkeyVecList) { 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 /// 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. /// 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 /// - 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. /// 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; } ////// 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 as outputs of this node /// internal VarVec Definitions { get { return m_definitions; } } ////// The keys for this node /// internal KeyVec Keys { get { return m_keys; } } ////// The definitions of vars that are guaranteed to be non-nullable when output from this node /// internal VarVec NonNullableDefinitions { get { return m_nonNullableDefinitions; } } ////// The definitions that come from the rel-op inputs of this node that are guaranteed to be non-nullable /// internal VarVec NonNullableVisibleDefinitions { get { return m_nonNullableVisibleDefinitions; } } ////// 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. 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 /// /// Node to get NodeInfo for 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 ////// 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; } /// /// The given definition is non nullable if it is a non-null constant /// or a reference to non-nullable input /// /// /// ///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 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 = 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 /// /// 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 //non-nullable definitions nodeInfo.NonNullableDefinitions.Or(op.Table.NonNullableColumns); nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions); 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 = * /// NonNullableDefinitions: default(empty) /// NonNullableInputDefinitions : default(empty) because cannot be used /// /// /// ///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 /// NonNullabeDefinitions = Outputs that are either among the NonNullableDefinitions of the child or /// are constants defined on this node /// NonNullableInputDefinitions = NonNullableDefinitions of the child /// /// 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); } } //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 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 /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp /// /// 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); //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; } /// /// 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) /// /// The GroupByOp /// corresponding Node ///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; } /// /// 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 /// /// 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); 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; } /// /// 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 /// /// 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); //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; } /// /// 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 /// /// 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); //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; } /// /// 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 /// /// 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); 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; } /// /// 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 /// /// 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); //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; } /// /// 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 /// /// The DistinctOp /// corresponding Node ///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; } /// /// 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 /// /// 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.NonNullableDefinitions.InitFrom(childNodeInfo.NonNullableDefinitions); nodeInfo.SetRowCount(RowCount.Zero, RowCount.One); return nodeInfo; } ////// SingleRowTableOp /// No definitions, external references, non-nullable definitions /// 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 /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp that are among the definitions /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp /// /// 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); } } //Non-nullable definitions nodeInfo.NonNullableDefinitions.Or(driverChildNodeInfo.NonNullableDefinitions); nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions); nodeInfo.NonNullableVisibleDefinitions.Or(driverChildNodeInfo.NonNullableVisibleDefinitions); 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 [....] // @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 { ////// 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(ListkeyVecList) { 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 /// 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. /// 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 /// - 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. /// 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; } ////// 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 as outputs of this node /// internal VarVec Definitions { get { return m_definitions; } } ////// The keys for this node /// internal KeyVec Keys { get { return m_keys; } } ////// The definitions of vars that are guaranteed to be non-nullable when output from this node /// internal VarVec NonNullableDefinitions { get { return m_nonNullableDefinitions; } } ////// The definitions that come from the rel-op inputs of this node that are guaranteed to be non-nullable /// internal VarVec NonNullableVisibleDefinitions { get { return m_nonNullableVisibleDefinitions; } } ////// 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. 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 /// /// Node to get NodeInfo for 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 ////// 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; } /// /// The given definition is non nullable if it is a non-null constant /// or a reference to non-nullable input /// /// /// ///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 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 = 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 /// /// 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 //non-nullable definitions nodeInfo.NonNullableDefinitions.Or(op.Table.NonNullableColumns); nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions); 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 = * /// NonNullableDefinitions: default(empty) /// NonNullableInputDefinitions : default(empty) because cannot be used /// /// /// ///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 /// NonNullabeDefinitions = Outputs that are either among the NonNullableDefinitions of the child or /// are constants defined on this node /// NonNullableInputDefinitions = NonNullableDefinitions of the child /// /// 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); } } //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 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 /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp /// /// 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); //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; } /// /// 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) /// /// The GroupByOp /// corresponding Node ///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; } /// /// 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 /// /// 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); 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; } /// /// 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 /// /// 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); //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; } /// /// 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 /// /// 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); //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; } /// /// 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 /// /// 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); 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; } /// /// 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 /// /// 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); //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; } /// /// 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 /// /// The DistinctOp /// corresponding Node ///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; } /// /// 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 /// /// 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.NonNullableDefinitions.InitFrom(childNodeInfo.NonNullableDefinitions); nodeInfo.SetRowCount(RowCount.Zero, RowCount.One); return nodeInfo; } ////// SingleRowTableOp /// No definitions, external references, non-nullable definitions /// 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 /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp that are among the definitions /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp /// /// 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); } } //Non-nullable definitions nodeInfo.NonNullableDefinitions.Or(driverChildNodeInfo.NonNullableDefinitions); nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions); nodeInfo.NonNullableVisibleDefinitions.Or(driverChildNodeInfo.NonNullableVisibleDefinitions); 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
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- XmlObjectSerializerReadContextComplex.cs
- PermissionToken.cs
- JournalEntryStack.cs
- DBNull.cs
- Enum.cs
- Rijndael.cs
- EntityDataSource.cs
- JsonUriDataContract.cs
- StaticExtension.cs
- BindingsCollection.cs
- DataGridSortCommandEventArgs.cs
- TextViewBase.cs
- NativeCppClassAttribute.cs
- XamlSerializerUtil.cs
- RuntimeResourceSet.cs
- ResXDataNode.cs
- ColorTransformHelper.cs
- GetPageCompletedEventArgs.cs
- MetadataItemEmitter.cs
- ConstraintStruct.cs
- SvcMapFileLoader.cs
- BufferedGraphicsManager.cs
- EventOpcode.cs
- MemoryFailPoint.cs
- Converter.cs
- SqlServer2KCompatibilityAnnotation.cs
- HtmlLink.cs
- LingerOption.cs
- ChangeNode.cs
- VerticalAlignConverter.cs
- SignedInfo.cs
- ConfigXmlReader.cs
- XmlNodeChangedEventManager.cs
- Update.cs
- EdmMember.cs
- BinaryMethodMessage.cs
- remotingproxy.cs
- MediaContextNotificationWindow.cs
- UnitySerializationHolder.cs
- SubqueryTrackingVisitor.cs
- XmlHierarchicalDataSourceView.cs
- MsmqIntegrationSecurity.cs
- XamlToRtfParser.cs
- _ListenerAsyncResult.cs
- FixedPage.cs
- DesignBindingPropertyDescriptor.cs
- HttpWebRequestElement.cs
- MembershipValidatePasswordEventArgs.cs
- TemplateEditingVerb.cs
- ToolStripProfessionalLowResolutionRenderer.cs
- DataRowExtensions.cs
- SyndicationSerializer.cs
- PerformanceCounterCategory.cs
- ParallelRangeManager.cs
- storagemappingitemcollection.viewdictionary.cs
- WpfWebRequestHelper.cs
- XsltQilFactory.cs
- EntityDataSourceDesigner.cs
- EventData.cs
- ConstrainedGroup.cs
- ChtmlFormAdapter.cs
- TableRow.cs
- InstanceDataCollection.cs
- TextElementAutomationPeer.cs
- PageBreakRecord.cs
- TextParagraphView.cs
- MDIControlStrip.cs
- ReferencedAssembly.cs
- DocumentPageView.cs
- DynamicPropertyReader.cs
- RichTextBoxAutomationPeer.cs
- AsymmetricSignatureFormatter.cs
- PageTextBox.cs
- webbrowsersite.cs
- XmlnsPrefixAttribute.cs
- ActiveXMessageFormatter.cs
- DeadLetterQueue.cs
- MenuItemCollectionEditorDialog.cs
- ScriptingProfileServiceSection.cs
- BindingMAnagerBase.cs
- DesignerAttributeInfo.cs
- ClrPerspective.cs
- CompositionAdorner.cs
- AttributeProviderAttribute.cs
- TextLineResult.cs
- DataGridViewAutoSizeColumnsModeEventArgs.cs
- HttpCookiesSection.cs
- _SecureChannel.cs
- HostingEnvironmentSection.cs
- VariableQuery.cs
- SqlUdtInfo.cs
- CopyOfAction.cs
- UndoManager.cs
- StylusPointPropertyInfo.cs
- Pair.cs
- XPathAncestorIterator.cs
- FormCollection.cs
- PageCache.cs
- XsltContext.cs
- SelfIssuedAuthRSAPKCS1SignatureFormatter.cs