Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Query / InternalTrees / NodeInfo.cs / 2 / NodeInfo.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Diagnostics;
using System.Data.Common;
using md=System.Data.Metadata.Edm;
namespace System.Data.Query.InternalTrees
{
///
/// The KeySet class encapsulates all information about the keys of a RelOp node in
/// the query tree.
/// A KeyVec is logically a set of vars that uniquely identify the row of the current
/// RelOp. Some RelOps may have no unique keys - such a state is identified by the
/// "NoKeys" property
///
internal class KeyVec
{
#region private state
private VarVec m_keys;
private bool m_noKeys;
#endregion
#region constructors
internal KeyVec(Command itree)
{
m_keys = itree.CreateVarVec();
m_noKeys = true;
}
#endregion
internal void InitFrom(KeyVec keyset)
{
m_keys.InitFrom(keyset.m_keys);
m_noKeys = keyset.m_noKeys;
}
internal void InitFrom(IEnumerable varSet)
{
InitFrom(varSet, false);
}
internal void InitFrom(IEnumerable varSet, bool ignoreParameters)
{
m_keys.InitFrom(varSet, ignoreParameters);
// Bug 434541: An empty set of keys is not the same as "no" keys.
// Caveat Emptor
m_noKeys = false;
}
internal void InitFrom(KeyVec left, KeyVec right)
{
if (left.m_noKeys || right.m_noKeys)
{
m_noKeys = true;
}
else
{
m_noKeys = false;
m_keys.InitFrom(left.m_keys);
m_keys.Or(right.m_keys);
}
}
internal void InitFrom(List keyVecList)
{
m_noKeys = false;
m_keys.Clear();
foreach (KeyVec keyVec in keyVecList)
{
if (keyVec.m_noKeys)
{
m_noKeys = true;
return;
}
m_keys.Or(keyVec.m_keys);
}
}
internal void Clear()
{
m_noKeys = true;
m_keys.Clear();
}
internal VarVec KeyVars { get { return m_keys; } }
internal bool NoKeys { get { return m_noKeys; } set { m_noKeys = value; } }
}
///
/// The NodeInfo class represents additional information about a node in the tree.
/// By default, this includes a set of external references for each node (ie) references
/// to Vars that are not defined in the same subtree
/// The NodeInfo class also includes a "hashValue" that is a hash value for the entire
/// subtree rooted at this node
///
internal class NodeInfo
{
#region private state
private VarVec m_externalReferences;
protected int m_hashValue; // hash value for the node
#endregion
#region constructors
internal NodeInfo(Command cmd)
{
m_externalReferences = cmd.CreateVarVec();
}
#endregion
#region public methods
///
/// Clear out all information - usually used by a Recompute
///
internal virtual void Clear()
{
m_externalReferences.Clear();
m_hashValue = 0;
}
///
/// All external references from this node
///
internal VarVec ExternalReferences
{
get { return m_externalReferences; }
}
///
/// Get the hash value for this nodeInfo
///
internal int HashValue
{
get { return m_hashValue; }
}
///
/// Compute the hash value for a Vec
///
///
///
/// Computes the hash value for this node. The hash value is simply the
/// local hash value for this node info added with the hash values of the child
/// nodes
///
/// current command
/// current node
internal virtual void ComputeHashValue(Command cmd, Node n)
{
m_hashValue = 0;
foreach (Node chi in n.Children)
{
NodeInfo chiNodeInfo = cmd.GetNodeInfo(chi);
m_hashValue ^= chiNodeInfo.HashValue;
}
m_hashValue = (m_hashValue << 4) ^ ((int)n.Op.OpType); // include the optype somehow
// Now compute my local hash value
m_hashValue = (m_hashValue << 4) ^ GetHashValue(m_externalReferences);
}
#endregion
}
///
/// Enum describing row counts
///
internal enum RowCount : byte
{
///
/// Zero rows
///
Zero = 0,
///
/// One row
///
One = 1,
///
/// Unbounded (unknown number of rows)
///
Unbounded = 2,
}
///
/// An ExtendedNodeInfo class adds additional information to a standard NodeInfo.
/// This class is usually applicable only to RelOps and PhysicalOps.
/// The ExtendedNodeInfo class has in addition to the information maintained by NodeInfo
/// the following
/// - a set of local definitions
/// - a set of definitions
/// - and a set of keys
///
internal class ExtendedNodeInfo : NodeInfo
{
#region private
private VarVec m_localDefinitions;
private VarVec m_definitions;
private KeyVec m_keys;
private RowCount m_minRows;
private RowCount m_maxRows;
#endregion
#region constructors
internal ExtendedNodeInfo(Command cmd)
: base(cmd)
{
m_localDefinitions = cmd.CreateVarVec();
m_definitions = cmd.CreateVarVec();
m_keys = new KeyVec(cmd);
m_minRows = RowCount.Zero;
m_maxRows = RowCount.Unbounded;
}
#endregion
#region public methods
internal override void Clear()
{
base.Clear();
m_definitions.Clear();
m_localDefinitions.Clear();
m_keys.Clear();
m_minRows = RowCount.Zero;
m_maxRows = RowCount.Unbounded;
}
///
/// Compute the hash value for this node
///
///
///
internal override void ComputeHashValue(Command cmd, Node n)
{
base.ComputeHashValue(cmd, n);
m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Definitions);
m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Keys.KeyVars);
return;
}
///
/// Definitions made specifically by this node
///
internal VarVec LocalDefinitions { get { return m_localDefinitions; } }
///
/// All definitions visible at this node
///
internal VarVec Definitions { get { return m_definitions; } }
///
/// The keys for this node
///
internal KeyVec Keys { get { return m_keys; } }
///
/// Min number of rows returned from this node
///
internal RowCount MinRows
{
get { return m_minRows; }
set { m_minRows = value; ValidateRowCount(); }
}
///
/// Max rows returned from this node
///
internal RowCount MaxRows
{
get { return m_maxRows; }
set { m_maxRows = value; ValidateRowCount(); }
}
///
/// Set the rowcount for this node
///
/// min rows produced by this node
/// max rows produced by this node
internal void SetRowCount(RowCount minRows, RowCount maxRows)
{
m_minRows = minRows;
m_maxRows = maxRows;
ValidateRowCount();
}
///
/// Initialize the rowcounts for this node from the source node
///
/// nodeinfo of source
internal void InitRowCountFrom(ExtendedNodeInfo source)
{
m_minRows = source.m_minRows;
m_maxRows = source.m_maxRows;
}
#endregion
#region private methods
private void ValidateRowCount()
{
Debug.Assert(m_maxRows >= m_minRows, "MaxRows less than MinRows?");
}
#endregion
}
///
/// The NodeInfoVisitor is a simple class (ab)using the Visitor pattern to define
/// NodeInfo semantics for various nodes in the tree
///
internal class NodeInfoVisitor : BasicOpVisitorOfT
{
#region public methods
///
/// The only public method. Computes the nodeInfo for a node in the tree.
/// Assumes that the NodeInfo for each child (if computed already) is valid
///
/// Node to get NodeInfo for
/// NodeInfo for the node
internal NodeInfo ComputeNodeInfo(Node n)
{
NodeInfo nodeInfo = VisitNode(n);
nodeInfo.ComputeHashValue(this.m_command, n); // compute the hash value for this node
return nodeInfo;
}
#endregion
#region constructors
///
/// Basic constructor
///
///
internal NodeInfoVisitor(Command command)
{
m_command = command;
}
#endregion
#region private state
private Command m_command;
#endregion
#region private methods
private NodeInfo GetNodeInfo(Node n)
{
return n.GetNodeInfo(m_command);
}
private ExtendedNodeInfo GetExtendedNodeInfo(Node n)
{
return n.GetExtendedNodeInfo(m_command);
}
private NodeInfo InitNodeInfo(Node n)
{
NodeInfo nodeInfo = GetNodeInfo(n);
nodeInfo.Clear();
return nodeInfo;
}
private ExtendedNodeInfo InitExtendedNodeInfo(Node n)
{
ExtendedNodeInfo nodeInfo = GetExtendedNodeInfo(n);
nodeInfo.Clear();
return nodeInfo;
}
#endregion
#region VisitorHelpers
///
/// Default implementation for scalarOps. Simply adds up external references
/// from each child
///
///
/// 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
///
/// Definitions = Local Definitions = table columns
/// External References = none
/// Keys = keys of entity type
/// RowCount (default): MinRows = 0, MaxRows = *
///
/// ScanTable/ScanView op
/// current subtree
/// nodeinfo for this subtree
protected override NodeInfo VisitTableOp(ScanTableBaseOp op, Node n)
{
ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
// #479372 - only the "referenced" columns of the table should
// show up in the definitions
nodeInfo.LocalDefinitions.Or(op.Table.ReferencedColumns);
nodeInfo.Definitions.Or(op.Table.ReferencedColumns);
// get table's keys - but only if the key columns have been referenced
if (op.Table.ReferencedColumns.Subsumes(op.Table.Keys))
{
nodeInfo.Keys.InitFrom(op.Table.Keys);
}
// no external references
return nodeInfo;
}
///
/// Computes a NodeInfo for an UnnestOp.
/// Definitions = columns of the table produced by this Op
/// Keys = none
/// External References = the unnestVar + any external references of the
/// computed Var (if any)
/// RowCount (default): MinRows = 0; MaxRows = *
///
///
///
///
/// Walk through the computed vars defined by a VarDefListNode, and look for
/// "simple" Var renames. Build up a mapping from original Vars to the renamed Vars
///
/// the varDefListNode subtree
/// A dictionary of Var->Var renames
internal static Dictionary ComputeVarRemappings(Node varDefListNode)
{
Debug.Assert(varDefListNode.Op.OpType == OpType.VarDefList);
Dictionary varMap = new Dictionary();
foreach (Node varDefNode in varDefListNode.Children)
{
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp != null)
{
VarDefOp varDefOp = varDefNode.Op as VarDefOp;
Debug.Assert(varDefOp != null);
varMap[varRefOp.Var] = varDefOp.Var;
}
}
return varMap;
}
///
/// Computes a NodeInfo for a ProjectOp.
/// Definitions = the Vars property of this Op
/// LocalDefinitions = list of computed Vars produced by this node
/// Keys = Keys of the input Relop (if they are all preserved)
/// External References = any external references from the computed Vars
/// RowCount = Input's RowCount
///
/// The ProjectOp
/// corresponding Node
/// varRenameMap = ComputeVarRemappings(n.Child1);
VarVec mappedKeyVec = keyVec.Remap(varRenameMap);
VarVec mappedKeyVecClone = mappedKeyVec.Clone();
VarVec opVars = m_command.CreateVarVec(op.Outputs);
mappedKeyVec.Minus(opVars);
if (mappedKeyVec.IsEmpty)
{
nodeInfo.Keys.InitFrom(mappedKeyVecClone);
}
}
nodeInfo.InitRowCountFrom(relOpChildNodeInfo);
return nodeInfo;
}
///
/// Computes a NodeInfo for a FilterOp.
/// Definitions = Definitions of the input Relop
/// LocalDefinitions = None
/// Keys = Keys of the input Relop
/// External References = any external references from the input + any external
/// references from the predicate
/// MaxOneRow = Input's RowCount
/// If the predicate is a "false" predicate, then max RowCount is zero
/// If we can infer additional info from the key-selector, we may be
/// able to get better estimates
///
/// The FilterOp
/// corresponding Node
///
/// Computes a NodeInfo for a GroupByOp.
/// Definitions = Keys + aggregates
/// LocalDefinitions = Keys + Aggregates
/// Keys = GroupBy Keys
/// External References = any external references from the input + any external
/// references from the local computed Vars
/// RowCount = (0,1), if no group-by keys; (0,n) otherwise
///
/// The GroupByOp
/// corresponding Node
///
/// Computes a NodeInfo for a CrossJoinOp.
/// Definitions = Definitions of my children
/// LocalDefinitions = None
/// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
/// External References = any external references from the inputs
/// RowCount: MinRows: min(min-rows of each child)
/// MaxRows: max(max-rows of each child)
///
/// The CrossJoinOp
/// corresponding Node
/// keyVecList = new List();
RowCount maxCard = RowCount.Zero;
RowCount minCard = RowCount.One;
foreach (Node chi in n.Children)
{
ExtendedNodeInfo chiNodeInfo = GetExtendedNodeInfo(chi);
nodeInfo.Definitions.Or(chiNodeInfo.Definitions);
nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
keyVecList.Add(chiNodeInfo.Keys);
// Not entirely precise, but good enough
if (chiNodeInfo.MaxRows > maxCard)
{
maxCard = chiNodeInfo.MaxRows;
}
if (chiNodeInfo.MinRows < minCard)
{
minCard = chiNodeInfo.MinRows;
}
}
nodeInfo.Keys.InitFrom(keyVecList);
nodeInfo.SetRowCount(minCard, maxCard);
return nodeInfo;
}
///
/// Computes a NodeInfo for an Inner/LeftOuter/FullOuter JoinOp.
/// Definitions = Definitions of my children
/// LocalDefinitions = None
/// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
/// External References = any external references from the inputs + any external
/// references from the join predicates
/// RowCount:
/// FullOuterJoin: MinRows = 0, MaxRows = N
/// InnerJoin: MinRows = 0;
/// MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
/// OuterJoin: MinRows = leftInput.MinRows
/// MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
///
/// The JoinOp
/// corresponding Node
///
/// Computes a NodeInfo for a CrossApply/OuterApply op.
/// Definitions = Definitions of my children
/// LocalDefinitions = None
/// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
/// External References = any external references from the inputs
/// RowCount:
/// CrossApply: minRows=0; MaxRows=Unbounded
/// (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
/// OuterApply: minRows=leftInput.MinRows; MaxRows=Unbounded
/// (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
///
///
/// The ApplyOp
/// corresponding Node
///
/// Computes a NodeInfo for SetOps (UnionAll, Intersect, Except).
/// Definitions = OutputVars
/// LocalDefinitions = OutputVars
/// Keys = Output Vars for Intersect, Except. For UnionAll ??
/// External References = any external references from the inputs
/// RowCount: Min = 0, Max = unbounded.
/// For UnionAlls, MinRows = max(MinRows of left and right inputs)
///
///
/// The SetOp
/// corresponding Node
///
/// Computes a NodeInfo for a ConstrainedSortOp/SortOp.
/// Definitions = Definitions of the input Relop
/// LocalDefinitions = not allowed
/// Keys = Keys of the input Relop
/// External References = any external references from the input + any external
/// references from the predicate
/// RowCount = Input's RowCount
///
/// The SortOp
/// corresponding Node
///
/// Computes a NodeInfo for Distinct.
/// Definitions = OutputVars
/// LocalDefinitions = None
/// Keys = Output Vars
/// External References = any external references from the inputs
/// RowCount = Input's RowCount
///
/// The DistinctOp
/// corresponding Node
///
/// Compute NodeInfo for a SingleRowOp.
/// Definitions = child's definitions
/// Keys = child's keys
/// Local Definitions = none
/// External references = child's external references
/// RowCount=(0,1)
///
/// The SingleRowOp
/// current subtree
/// NodeInfo for this node
public override NodeInfo Visit(SingleRowOp op, Node n)
{
ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0);
nodeInfo.Definitions.InitFrom(childNodeInfo.Definitions);
nodeInfo.Keys.InitFrom(childNodeInfo.Keys);
nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
nodeInfo.SetRowCount(RowCount.Zero, RowCount.One);
return nodeInfo;
}
///
/// SingleRowTableOp
/// No definitions, external references.
/// Keys = empty list (not the same as "no keys")
/// RowCount = (1,1)
///
/// the SingleRowTableOp
/// current subtree
/// nodeInfo for this subtree
public override NodeInfo Visit(SingleRowTableOp op, Node n)
{
ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
nodeInfo.Keys.NoKeys = false;
nodeInfo.SetRowCount(RowCount.One, RowCount.One);
return nodeInfo;
}
#endregion
#region PhysicalOps
///
/// Computes a NodeInfo for a PhysicalProjectOp.
/// Definitions = OutputVars
/// LocalDefinitions = None
/// Keys = None
/// External References = any external references from the inputs
/// RowCount=default
///
/// The PhysicalProjectOp
/// corresponding Node
///
/// 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
///
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Diagnostics;
using System.Data.Common;
using md=System.Data.Metadata.Edm;
namespace System.Data.Query.InternalTrees
{
///
/// The KeySet class encapsulates all information about the keys of a RelOp node in
/// the query tree.
/// A KeyVec is logically a set of vars that uniquely identify the row of the current
/// RelOp. Some RelOps may have no unique keys - such a state is identified by the
/// "NoKeys" property
///
internal class KeyVec
{
#region private state
private VarVec m_keys;
private bool m_noKeys;
#endregion
#region constructors
internal KeyVec(Command itree)
{
m_keys = itree.CreateVarVec();
m_noKeys = true;
}
#endregion
internal void InitFrom(KeyVec keyset)
{
m_keys.InitFrom(keyset.m_keys);
m_noKeys = keyset.m_noKeys;
}
internal void InitFrom(IEnumerable varSet)
{
InitFrom(varSet, false);
}
internal void InitFrom(IEnumerable varSet, bool ignoreParameters)
{
m_keys.InitFrom(varSet, ignoreParameters);
// Bug 434541: An empty set of keys is not the same as "no" keys.
// Caveat Emptor
m_noKeys = false;
}
internal void InitFrom(KeyVec left, KeyVec right)
{
if (left.m_noKeys || right.m_noKeys)
{
m_noKeys = true;
}
else
{
m_noKeys = false;
m_keys.InitFrom(left.m_keys);
m_keys.Or(right.m_keys);
}
}
internal void InitFrom(List keyVecList)
{
m_noKeys = false;
m_keys.Clear();
foreach (KeyVec keyVec in keyVecList)
{
if (keyVec.m_noKeys)
{
m_noKeys = true;
return;
}
m_keys.Or(keyVec.m_keys);
}
}
internal void Clear()
{
m_noKeys = true;
m_keys.Clear();
}
internal VarVec KeyVars { get { return m_keys; } }
internal bool NoKeys { get { return m_noKeys; } set { m_noKeys = value; } }
}
///
/// The NodeInfo class represents additional information about a node in the tree.
/// By default, this includes a set of external references for each node (ie) references
/// to Vars that are not defined in the same subtree
/// The NodeInfo class also includes a "hashValue" that is a hash value for the entire
/// subtree rooted at this node
///
internal class NodeInfo
{
#region private state
private VarVec m_externalReferences;
protected int m_hashValue; // hash value for the node
#endregion
#region constructors
internal NodeInfo(Command cmd)
{
m_externalReferences = cmd.CreateVarVec();
}
#endregion
#region public methods
///
/// Clear out all information - usually used by a Recompute
///
internal virtual void Clear()
{
m_externalReferences.Clear();
m_hashValue = 0;
}
///
/// All external references from this node
///
internal VarVec ExternalReferences
{
get { return m_externalReferences; }
}
///
/// Get the hash value for this nodeInfo
///
internal int HashValue
{
get { return m_hashValue; }
}
///
/// Compute the hash value for a Vec
///
///
///
/// Computes the hash value for this node. The hash value is simply the
/// local hash value for this node info added with the hash values of the child
/// nodes
///
/// current command
/// current node
internal virtual void ComputeHashValue(Command cmd, Node n)
{
m_hashValue = 0;
foreach (Node chi in n.Children)
{
NodeInfo chiNodeInfo = cmd.GetNodeInfo(chi);
m_hashValue ^= chiNodeInfo.HashValue;
}
m_hashValue = (m_hashValue << 4) ^ ((int)n.Op.OpType); // include the optype somehow
// Now compute my local hash value
m_hashValue = (m_hashValue << 4) ^ GetHashValue(m_externalReferences);
}
#endregion
}
///
/// Enum describing row counts
///
internal enum RowCount : byte
{
///
/// Zero rows
///
Zero = 0,
///
/// One row
///
One = 1,
///
/// Unbounded (unknown number of rows)
///
Unbounded = 2,
}
///
/// An ExtendedNodeInfo class adds additional information to a standard NodeInfo.
/// This class is usually applicable only to RelOps and PhysicalOps.
/// The ExtendedNodeInfo class has in addition to the information maintained by NodeInfo
/// the following
/// - a set of local definitions
/// - a set of definitions
/// - and a set of keys
///
internal class ExtendedNodeInfo : NodeInfo
{
#region private
private VarVec m_localDefinitions;
private VarVec m_definitions;
private KeyVec m_keys;
private RowCount m_minRows;
private RowCount m_maxRows;
#endregion
#region constructors
internal ExtendedNodeInfo(Command cmd)
: base(cmd)
{
m_localDefinitions = cmd.CreateVarVec();
m_definitions = cmd.CreateVarVec();
m_keys = new KeyVec(cmd);
m_minRows = RowCount.Zero;
m_maxRows = RowCount.Unbounded;
}
#endregion
#region public methods
internal override void Clear()
{
base.Clear();
m_definitions.Clear();
m_localDefinitions.Clear();
m_keys.Clear();
m_minRows = RowCount.Zero;
m_maxRows = RowCount.Unbounded;
}
///
/// Compute the hash value for this node
///
///
///
internal override void ComputeHashValue(Command cmd, Node n)
{
base.ComputeHashValue(cmd, n);
m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Definitions);
m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Keys.KeyVars);
return;
}
///
/// Definitions made specifically by this node
///
internal VarVec LocalDefinitions { get { return m_localDefinitions; } }
///
/// All definitions visible at this node
///
internal VarVec Definitions { get { return m_definitions; } }
///
/// The keys for this node
///
internal KeyVec Keys { get { return m_keys; } }
///
/// Min number of rows returned from this node
///
internal RowCount MinRows
{
get { return m_minRows; }
set { m_minRows = value; ValidateRowCount(); }
}
///
/// Max rows returned from this node
///
internal RowCount MaxRows
{
get { return m_maxRows; }
set { m_maxRows = value; ValidateRowCount(); }
}
///
/// Set the rowcount for this node
///
/// min rows produced by this node
/// max rows produced by this node
internal void SetRowCount(RowCount minRows, RowCount maxRows)
{
m_minRows = minRows;
m_maxRows = maxRows;
ValidateRowCount();
}
///
/// Initialize the rowcounts for this node from the source node
///
/// nodeinfo of source
internal void InitRowCountFrom(ExtendedNodeInfo source)
{
m_minRows = source.m_minRows;
m_maxRows = source.m_maxRows;
}
#endregion
#region private methods
private void ValidateRowCount()
{
Debug.Assert(m_maxRows >= m_minRows, "MaxRows less than MinRows?");
}
#endregion
}
///
/// The NodeInfoVisitor is a simple class (ab)using the Visitor pattern to define
/// NodeInfo semantics for various nodes in the tree
///
internal class NodeInfoVisitor : BasicOpVisitorOfT
{
#region public methods
///
/// The only public method. Computes the nodeInfo for a node in the tree.
/// Assumes that the NodeInfo for each child (if computed already) is valid
///
/// Node to get NodeInfo for
/// NodeInfo for the node
internal NodeInfo ComputeNodeInfo(Node n)
{
NodeInfo nodeInfo = VisitNode(n);
nodeInfo.ComputeHashValue(this.m_command, n); // compute the hash value for this node
return nodeInfo;
}
#endregion
#region constructors
///
/// Basic constructor
///
///
internal NodeInfoVisitor(Command command)
{
m_command = command;
}
#endregion
#region private state
private Command m_command;
#endregion
#region private methods
private NodeInfo GetNodeInfo(Node n)
{
return n.GetNodeInfo(m_command);
}
private ExtendedNodeInfo GetExtendedNodeInfo(Node n)
{
return n.GetExtendedNodeInfo(m_command);
}
private NodeInfo InitNodeInfo(Node n)
{
NodeInfo nodeInfo = GetNodeInfo(n);
nodeInfo.Clear();
return nodeInfo;
}
private ExtendedNodeInfo InitExtendedNodeInfo(Node n)
{
ExtendedNodeInfo nodeInfo = GetExtendedNodeInfo(n);
nodeInfo.Clear();
return nodeInfo;
}
#endregion
#region VisitorHelpers
///
/// Default implementation for scalarOps. Simply adds up external references
/// from each child
///
///
/// 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
///
/// Definitions = Local Definitions = table columns
/// External References = none
/// Keys = keys of entity type
/// RowCount (default): MinRows = 0, MaxRows = *
///
/// ScanTable/ScanView op
/// current subtree
/// nodeinfo for this subtree
protected override NodeInfo VisitTableOp(ScanTableBaseOp op, Node n)
{
ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
// #479372 - only the "referenced" columns of the table should
// show up in the definitions
nodeInfo.LocalDefinitions.Or(op.Table.ReferencedColumns);
nodeInfo.Definitions.Or(op.Table.ReferencedColumns);
// get table's keys - but only if the key columns have been referenced
if (op.Table.ReferencedColumns.Subsumes(op.Table.Keys))
{
nodeInfo.Keys.InitFrom(op.Table.Keys);
}
// no external references
return nodeInfo;
}
///
/// Computes a NodeInfo for an UnnestOp.
/// Definitions = columns of the table produced by this Op
/// Keys = none
/// External References = the unnestVar + any external references of the
/// computed Var (if any)
/// RowCount (default): MinRows = 0; MaxRows = *
///
///
///
///
/// Walk through the computed vars defined by a VarDefListNode, and look for
/// "simple" Var renames. Build up a mapping from original Vars to the renamed Vars
///
/// the varDefListNode subtree
/// A dictionary of Var->Var renames
internal static Dictionary ComputeVarRemappings(Node varDefListNode)
{
Debug.Assert(varDefListNode.Op.OpType == OpType.VarDefList);
Dictionary varMap = new Dictionary();
foreach (Node varDefNode in varDefListNode.Children)
{
VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
if (varRefOp != null)
{
VarDefOp varDefOp = varDefNode.Op as VarDefOp;
Debug.Assert(varDefOp != null);
varMap[varRefOp.Var] = varDefOp.Var;
}
}
return varMap;
}
///
/// Computes a NodeInfo for a ProjectOp.
/// Definitions = the Vars property of this Op
/// LocalDefinitions = list of computed Vars produced by this node
/// Keys = Keys of the input Relop (if they are all preserved)
/// External References = any external references from the computed Vars
/// RowCount = Input's RowCount
///
/// The ProjectOp
/// corresponding Node
/// varRenameMap = ComputeVarRemappings(n.Child1);
VarVec mappedKeyVec = keyVec.Remap(varRenameMap);
VarVec mappedKeyVecClone = mappedKeyVec.Clone();
VarVec opVars = m_command.CreateVarVec(op.Outputs);
mappedKeyVec.Minus(opVars);
if (mappedKeyVec.IsEmpty)
{
nodeInfo.Keys.InitFrom(mappedKeyVecClone);
}
}
nodeInfo.InitRowCountFrom(relOpChildNodeInfo);
return nodeInfo;
}
///
/// Computes a NodeInfo for a FilterOp.
/// Definitions = Definitions of the input Relop
/// LocalDefinitions = None
/// Keys = Keys of the input Relop
/// External References = any external references from the input + any external
/// references from the predicate
/// MaxOneRow = Input's RowCount
/// If the predicate is a "false" predicate, then max RowCount is zero
/// If we can infer additional info from the key-selector, we may be
/// able to get better estimates
///
/// The FilterOp
/// corresponding Node
///
/// Computes a NodeInfo for a GroupByOp.
/// Definitions = Keys + aggregates
/// LocalDefinitions = Keys + Aggregates
/// Keys = GroupBy Keys
/// External References = any external references from the input + any external
/// references from the local computed Vars
/// RowCount = (0,1), if no group-by keys; (0,n) otherwise
///
/// The GroupByOp
/// corresponding Node
///
/// Computes a NodeInfo for a CrossJoinOp.
/// Definitions = Definitions of my children
/// LocalDefinitions = None
/// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
/// External References = any external references from the inputs
/// RowCount: MinRows: min(min-rows of each child)
/// MaxRows: max(max-rows of each child)
///
/// The CrossJoinOp
/// corresponding Node
/// keyVecList = new List();
RowCount maxCard = RowCount.Zero;
RowCount minCard = RowCount.One;
foreach (Node chi in n.Children)
{
ExtendedNodeInfo chiNodeInfo = GetExtendedNodeInfo(chi);
nodeInfo.Definitions.Or(chiNodeInfo.Definitions);
nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
keyVecList.Add(chiNodeInfo.Keys);
// Not entirely precise, but good enough
if (chiNodeInfo.MaxRows > maxCard)
{
maxCard = chiNodeInfo.MaxRows;
}
if (chiNodeInfo.MinRows < minCard)
{
minCard = chiNodeInfo.MinRows;
}
}
nodeInfo.Keys.InitFrom(keyVecList);
nodeInfo.SetRowCount(minCard, maxCard);
return nodeInfo;
}
///
/// Computes a NodeInfo for an Inner/LeftOuter/FullOuter JoinOp.
/// Definitions = Definitions of my children
/// LocalDefinitions = None
/// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
/// External References = any external references from the inputs + any external
/// references from the join predicates
/// RowCount:
/// FullOuterJoin: MinRows = 0, MaxRows = N
/// InnerJoin: MinRows = 0;
/// MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
/// OuterJoin: MinRows = leftInput.MinRows
/// MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
///
/// The JoinOp
/// corresponding Node
///
/// Computes a NodeInfo for a CrossApply/OuterApply op.
/// Definitions = Definitions of my children
/// LocalDefinitions = None
/// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
/// External References = any external references from the inputs
/// RowCount:
/// CrossApply: minRows=0; MaxRows=Unbounded
/// (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
/// OuterApply: minRows=leftInput.MinRows; MaxRows=Unbounded
/// (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
///
///
/// The ApplyOp
/// corresponding Node
///
/// Computes a NodeInfo for SetOps (UnionAll, Intersect, Except).
/// Definitions = OutputVars
/// LocalDefinitions = OutputVars
/// Keys = Output Vars for Intersect, Except. For UnionAll ??
/// External References = any external references from the inputs
/// RowCount: Min = 0, Max = unbounded.
/// For UnionAlls, MinRows = max(MinRows of left and right inputs)
///
///
/// The SetOp
/// corresponding Node
///
/// Computes a NodeInfo for a ConstrainedSortOp/SortOp.
/// Definitions = Definitions of the input Relop
/// LocalDefinitions = not allowed
/// Keys = Keys of the input Relop
/// External References = any external references from the input + any external
/// references from the predicate
/// RowCount = Input's RowCount
///
/// The SortOp
/// corresponding Node
///
/// Computes a NodeInfo for Distinct.
/// Definitions = OutputVars
/// LocalDefinitions = None
/// Keys = Output Vars
/// External References = any external references from the inputs
/// RowCount = Input's RowCount
///
/// The DistinctOp
/// corresponding Node
///
/// Compute NodeInfo for a SingleRowOp.
/// Definitions = child's definitions
/// Keys = child's keys
/// Local Definitions = none
/// External references = child's external references
/// RowCount=(0,1)
///
/// The SingleRowOp
/// current subtree
/// NodeInfo for this node
public override NodeInfo Visit(SingleRowOp op, Node n)
{
ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0);
nodeInfo.Definitions.InitFrom(childNodeInfo.Definitions);
nodeInfo.Keys.InitFrom(childNodeInfo.Keys);
nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
nodeInfo.SetRowCount(RowCount.Zero, RowCount.One);
return nodeInfo;
}
///
/// SingleRowTableOp
/// No definitions, external references.
/// Keys = empty list (not the same as "no keys")
/// RowCount = (1,1)
///
/// the SingleRowTableOp
/// current subtree
/// nodeInfo for this subtree
public override NodeInfo Visit(SingleRowTableOp op, Node n)
{
ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
nodeInfo.Keys.NoKeys = false;
nodeInfo.SetRowCount(RowCount.One, RowCount.One);
return nodeInfo;
}
#endregion
#region PhysicalOps
///
/// Computes a NodeInfo for a PhysicalProjectOp.
/// Definitions = OutputVars
/// LocalDefinitions = None
/// Keys = None
/// External References = any external references from the inputs
/// RowCount=default
///
/// The PhysicalProjectOp
/// corresponding Node
///
/// 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
///
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ToolboxComponentsCreatedEventArgs.cs
- CodeDelegateCreateExpression.cs
- ListMarkerSourceInfo.cs
- ParameterElementCollection.cs
- ErrorWebPart.cs
- LinkButton.cs
- SmiTypedGetterSetter.cs
- webclient.cs
- SystemIPInterfaceProperties.cs
- GuidelineCollection.cs
- ReaderWriterLock.cs
- QueryReaderSettings.cs
- SqlNodeAnnotation.cs
- OperandQuery.cs
- SafeFileMapViewHandle.cs
- CqlBlock.cs
- DetailsViewCommandEventArgs.cs
- FrameAutomationPeer.cs
- OverflowException.cs
- XmlExtensionFunction.cs
- PointF.cs
- BuildProviderAppliesToAttribute.cs
- DesignRelationCollection.cs
- AppModelKnownContentFactory.cs
- WeakReferenceList.cs
- AutomationPropertyInfo.cs
- CurrentChangedEventManager.cs
- HierarchicalDataBoundControlAdapter.cs
- _SafeNetHandles.cs
- DefaultHttpHandler.cs
- PolicyException.cs
- WSDualHttpSecurityMode.cs
- TraceUtility.cs
- SQLByteStorage.cs
- InputProcessorProfiles.cs
- Point3DAnimationUsingKeyFrames.cs
- SqlDataSourceSummaryPanel.cs
- FocusWithinProperty.cs
- LoadedOrUnloadedOperation.cs
- UniqueTransportManagerRegistration.cs
- DebugViewWriter.cs
- CertificateManager.cs
- sqlser.cs
- GridViewRowPresenterBase.cs
- DoubleUtil.cs
- Compiler.cs
- EventLogPermissionHolder.cs
- CodeLabeledStatement.cs
- DelegateTypeInfo.cs
- CombinedTcpChannel.cs
- SqlBulkCopy.cs
- AbstractSvcMapFileLoader.cs
- XNodeValidator.cs
- MasterPageCodeDomTreeGenerator.cs
- CollectionViewGroupInternal.cs
- FunctionNode.cs
- ImageBrush.cs
- CmsInterop.cs
- CmsUtils.cs
- XmlChoiceIdentifierAttribute.cs
- RequiredFieldValidator.cs
- X509UI.cs
- FileFormatException.cs
- ClrProviderManifest.cs
- InternalException.cs
- ReadOnlyDataSourceView.cs
- SimpleType.cs
- ObjectNavigationPropertyMapping.cs
- MediaPlayer.cs
- ServiceDesigner.cs
- DbSetClause.cs
- CellPartitioner.cs
- COMException.cs
- InfoCardKeyedHashAlgorithm.cs
- CorruptingExceptionCommon.cs
- TextLineResult.cs
- ThreadStartException.cs
- LogPolicy.cs
- CroppedBitmap.cs
- CompoundFileDeflateTransform.cs
- Wrapper.cs
- CodeTypeReferenceExpression.cs
- SplitContainerDesigner.cs
- Span.cs
- ObjectCloneHelper.cs
- HtmlEncodedRawTextWriter.cs
- FunctionDescription.cs
- TypeEnumerableViewSchema.cs
- BatchParser.cs
- WmfPlaceableFileHeader.cs
- HierarchicalDataBoundControlAdapter.cs
- HostVisual.cs
- WindowsComboBox.cs
- SqlCommandAsyncResult.cs
- DrawingGroup.cs
- VirtualDirectoryMappingCollection.cs
- ObjectStateEntryDbUpdatableDataRecord.cs
- ListViewCancelEventArgs.cs
- SmtpNegotiateAuthenticationModule.cs
- IDQuery.cs