Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / NestPullup.cs / 2 / NestPullup.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Collections.Generic;
using System.Globalization;
using System.Data.Common;
using md = System.Data.Metadata.Edm;
using System.Data.Query.InternalTrees;
using System.Data.Query.PlanCompiler;
namespace System.Data.Query.PlanCompiler {
///
/// This class "pulls" up nest operations to the root of the tree
///
///
/// The goal of this module is to eliminate nest operations from the query - more
/// specifically, the nest operations are pulled up to the root of the query instead.
///
internal class NestPullup : BasicOpVisitorOfNode {
#region private state
private PlanCompiler m_compilerState;
///
/// map from a collection var to the node where it's defined; the node should be
/// the node that should be used as the replacement for the var if it is referred
/// to in an UnnestOp (through a VarRef) Note that we expect this to contain the
/// PhysicalProjectOp of the node, so we can use the VarList when mapping vars to
/// the copy; (We'll remove the PhysicalProjectOp when we copy it...)
///
private Dictionary m_definingNodeMap = new Dictionary();
///
/// map from var to the var we're supposed to replace it with
///
private VarRemapper m_varRemapper;
///
/// Map from VarRef vars to what they're referencing; used to enable the defining
/// node map to contain only the definitions, not all the references to it.
///
private Dictionary m_varRefMap = new Dictionary();
#endregion
#region constructor
private NestPullup(PlanCompiler compilerState) {
m_compilerState = compilerState;
m_varRemapper = new VarRemapper(compilerState.Command);
}
#endregion
#region Process Driver
internal static void Process(PlanCompiler compilerState) {
NestPullup np = new NestPullup(compilerState);
np.Process();
}
///
/// The driver routine. Does all the hard work of processing
///
private void Process() {
PlanCompiler.Assert(Command.Root.Op.OpType == OpType.PhysicalProject, "root node is not physicalProject?");
Command.Root = VisitNode(Command.Root);
}
#endregion
#region private methods
#region VisitorHelpers
///
/// the iqt we're processing
///
private Command Command { get { return m_compilerState.Command; } }
///
/// is the node a NestOp node?
///
///
///
/// Not Supported common processing
///
/// For all those cases where we don't intend to support
/// a nest operation as a child, we have this routine to
/// do the work.
///
///
///
///
/// Follow the VarRef chain to the defining var
///
///
///
/// Update the replacement Var map with the vars from the pulled-up
/// operation; the shape is supposed to be identical, so we should not
/// have more vars on either side, and the order is guaranteed to be
/// the same.
///
///
///
private void UpdateReplacementVarMap(IEnumerable fromVars, IEnumerable toVars) {
IEnumerator toVarEnumerator = toVars.GetEnumerator();
foreach (Var v in fromVars) {
if (!toVarEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 2);
}
m_varRemapper.AddMapping(v, toVarEnumerator.Current);
}
if (toVarEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 3);
}
}
#region remapping helpers
///
/// Replace a list of sortkeys *IN-PLACE* with the corresponding "mapped" Vars
///
/// sortkeys
/// the mapping info for Vars
private static void RemapSortKeys(List sortKeys, Dictionary varMap) {
if (sortKeys != null) {
foreach (InternalTrees.SortKey sortKey in sortKeys) {
Var replacementVar;
if (varMap.TryGetValue(sortKey.Var, out replacementVar)) {
sortKey.Var = replacementVar;
}
}
}
}
///
/// Produce a "mapped" sequence of the input Var sequence - based on the supplied
/// map
///
/// input var sequence
/// var->var map
/// the mapped var sequence
private IEnumerable RemapVars(IEnumerable vars, Dictionary varMap) {
foreach (Var v in vars) {
Var mappedVar;
if (varMap.TryGetValue(v, out mappedVar)) {
yield return mappedVar;
}
else {
yield return v;
}
}
}
///
/// Produce a "mapped" varList
///
///
///
/// varMap) {
VarList newVarList = Command.CreateVarList(RemapVars(varList, varMap));
return newVarList;
}
///
/// Produce a "mapped" varVec
///
///
///
/// varMap) {
VarVec newVarVec = Command.CreateVarVec(RemapVars(varVec, varMap));
return newVarVec;
}
#endregion
#endregion
#region AncillaryOp Visitors
///
/// VarDefOp
///
/// Essentially, maintains m_varRefMap, adding an entry for each VarDef that has a
/// VarRef on it.
///
///
///
///
/// VarRefOp
///
///
/// When we remove the UnnestOp, we are left with references to it's column vars that
/// need to be fixed up; we do this by creating a var replacement map when we remove the
/// UnnestOp and whenever we find a reference to a var in the map, we replace it with a
/// reference to the replacement var instead;
///
///
///
///
/// We don't yet support nest pullups over Case
///
///
///
///
/// Default RelOp processing:
///
/// We really don't want to allow any NestOps through; just fail if we don't have
/// something coded.
///
///
///
///
/// ApplyOp/JoinOp common processing
///
///
/// If one of the inputs to any JoinOp/ApplyOp is a NestOp, then the NestOp
/// can be pulled above the join/apply if every input to the join/apply has
/// a key(s). The keys of the NestOp are augmented with the keys of the
/// other join inputs:
///
/// JoinOp/ApplyOp(NestOp(X, ...), Y) => NestOp(JoinOp/ApplyOp(X, Y), ...)
///
/// In addition, if the NestOp is on a 'nullable' side of a join (i.e. right side of
/// LeftOuterJoin/OuterApply or either side of FullOuterJoin), the driving node
/// of that NestOp (X) is capped with a project with a null sentinel and
/// the dependant collection nodes (the rest of the NestOp children)
/// are filtered based on that sentinel:
///
/// LOJ/OA/FOJ (X, NestOp(Y, Z1, Z2, ..ZN)) => NestOp( LOJ/OA/FOJ (X, PROJECT (Y, v = 1)), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
/// FOJ (NestOp(Y, Z1, Z2, ..ZN), X) => NestOp( LOJ/OA/FOJ (PROJECT (Y, v = 1), X), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
///
/// Also, FILTER(Zi, v != null) may be transformed to push the filter below any NestOps.
///
/// Requires: Every input to the join/apply must have a key.
///
///
///
/// newNestChildren = new List();
List newJoinApplyChildren = new List();
List newCollectionInfoList = new List();
foreach (Node chi in n.Children) {
if (chi.Op.OpType == OpType.MultiStreamNest) {
newCollectionInfoList.AddRange(((MultiStreamNestOp)chi.Op).CollectionInfo);
// SQLBUDT #615513: If the nest op is on a 'nullable' side of join
// (i.e. right side of LeftOuterJoin/OuterApply or either side of FullOuterJoin)
// the driving node of that nest operation needs to be capped with a project with
// a null sentinel and the dependant collection nodes need to be filtered based on that sentinel.
//
// LOJ/OA/FOJ (X, MSN(Y, Z1, Z2, ..ZN)) => MSN( LOJ/OA/FOJ (X, PROJECT (Y, v = 1)), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
// FOJ (MSN(Y, Z1, Z2, ..ZN), X) => MSN( LOJ/OA/FOJ (PROJECT (Y, v = 1), X), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
//
// Note: we transform FILTER(Zi, v != null) to push the filter below any MSNs.
if ((op.OpType == OpType.FullOuterJoin)
|| ((op.OpType == OpType.LeftOuterJoin || op.OpType == OpType.OuterApply) && n.Child1.Op.OpType == OpType.MultiStreamNest)) {
Var sentinelVar = null;
newJoinApplyChildren.Add(AugmentNodeWithInternalConstant(chi.Child0, 1, out sentinelVar));
for (int i = 1; i < chi.Children.Count; i++) {
// Push the filter bellow all MultiStremNest-s, because this part of the tree has
// already been visited and it is expected that the MultiStreamNests have bubbled up
// above the filters.
Node newFilterChild = chi.Children[i];
Node newFilterParent = null;
while (newFilterChild.Op.OpType == OpType.MultiStreamNest) {
newFilterParent = newFilterChild;
newFilterChild = newFilterChild.Child0;
}
Node newFilterNode = CapWithIsNotNullFilter(newFilterChild, sentinelVar);
Node newNestChild; // the original child or the filter, depending on whether the filter got pushed
if (newFilterParent != null) {
newFilterParent.Child0 = newFilterNode;
newNestChild = chi.Children[i];
}
else {
newNestChild = newFilterNode;
}
newNestChildren.Add(newNestChild);
}
}
else {
newJoinApplyChildren.Add(chi.Child0);
for (int i = 1; i < chi.Children.Count; i++) {
newNestChildren.Add(chi.Children[i]);
}
}
}
else {
newJoinApplyChildren.Add(chi);
}
}
// (3) create the new Join/Apply node using the existing op and the
// new list of children from (1).
Node newJoinApplyNode = Command.CreateNode(op, newJoinApplyChildren);
// (4) insert the apply op as the driving node of the nestOp (put it
// at the beginning of the new nestOps' children.
newNestChildren.Insert(0, newJoinApplyNode);
// (5) build an updated list of output vars based upon the new join/apply
// node, and ensure all the collection vars from the nestOp(s) are
// included.
ExtendedNodeInfo xni = newJoinApplyNode.GetExtendedNodeInfo(Command);
VarVec newOutputVars = Command.CreateVarVec(xni.Definitions);
foreach (CollectionInfo ci in newCollectionInfoList) {
newOutputVars.Set(ci.CollectionVar);
}
// (6) create the new nestop
NestBaseOp newNestOp = Command.CreateMultiStreamNestOp(new List(), newOutputVars, newCollectionInfoList);
Node newNode = Command.CreateNode(newNestOp, newNestChildren);
return newNode;
}
///
/// Input => Filter(input, Ref(var) is not null)
///
///
///
///
/// ApplyOp common processing
///
///
///
///
/// DistinctOp
///
///
/// The input to a DistinctOp cannot be a NestOp – that would imply that
/// we support distinctness over collections - which we don’t.
///
///
///
///
/// FilterOp
///
///
/// If the input to the FilterOp is a NestOp, and if the filter predicate
/// does not reference any of the collection Vars of the nestOp, then the
/// FilterOp can be simply pushed below the NestOp:
///
/// Filter(Nest(X, ...), pred) => Nest(Filter(X, pred), ...)
///
/// Note: even if the filter predicate originally referenced one of the
/// collection vars, as part of our bottom up traversal, the appropriate
/// Var was replaced by a copy of the source of the collection. So, this
/// transformation should always be legal.
///
///
///
///
/// GroupByOp
///
///
/// At this point in the process, there really isn't a way we should actually
/// have a NestOp as an input to the GroupByOp, and we currently aren't allowing
/// you to specify a collection as an aggregation Var or key, so if we find a
/// NestOp anywhere on the inputs, it's a NotSupported situation.
///
///
///
///
/// JoinOp common processing
///
///
///
///
/// ProjectOp
///
///
/// There are three cases to handle in ProjectOp:
///
/// (1) The input is not a NestOp; but the ProjectOp locally defines some Vars
/// as collections:
///
/// ProjectOp(X,{a,CollectOp(PhysicalProjectOp(Y)),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),Y)
/// ProjectOp(X,{a,VarRef(ref-to-collect-var-Y),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),copy-of-Y)
///
/// Where:
/// ProjectOp' is ProjectOp less any vars that were collection vars, plus
/// any additional Vars needed by the collection.
///
/// (2) The input is a NestOp, but the ProjectOp does not local define some Vars
/// as collections:
///
/// ProjectOp(MsnOp(X,Y,...)) => MsnOp'(ProjectOp'(X),Y,...)
///
/// Where:
/// ProjectOp' is ProjectOp plus any additional Vars needed by NestOp
/// (see NestOp.Outputs – except the collection vars)
///
/// MsnOp' should be MsnOp. Additionally, its Outputs should be enhanced
/// to include any Vars produced by the ProjectOp
///
/// (3) The combination of both (1) and (2) -- both the vars define a collection,
/// and the input is also a nestOp. we handle this by first processing Case1,
/// then processing Case2.
///
///
///
///
/// Fold nested MultiStreamNestOps into one:
///
/// MSN(MSN(X,Y),Z) ==> MSN(X,Y,Z)
///
/// NOTE: It would be incorrect to merge NestOps from the non-driving node
/// into one nest op, because that would change the intent. Instead,
/// we let those go through the tree and wait until we get to the top
/// level PhysicalProject, when we'll use the ConvertToSingleStreamNest
/// process to handle them.
///
/// NOTE: We should never have three levels of nestOps, because we should
/// have folded the lower two together when we constructed one of them.
///
/// We also remove unreferenced collections, that is, if any collection is
/// not referred to by the top level-NestOp, we can safely remove it from
/// the merged NestOp we produce.
///
///
/// newNestInputs = new List();
List newCollectionInfo = new List();
VarVec newOutputVars = Command.CreateVarVec(nestOp.Outputs);
// Add the new DrivingNode;
newNestInputs.Add(nestedNestNode.Child0);
// Now add each of the nested nodes collections, but only when they're
// referenced by the top level nestOp's outputs.
for (int i = 1; i < nestedNestNode.Children.Count; i++) {
CollectionInfo ci = nestedNestOp.CollectionInfo[i - 1];
if (nestOpCollectionOutputs.IsSet(ci.CollectionVar) || newOutputVars.IsSet(ci.CollectionVar)) {
newCollectionInfo.Add(ci);
newNestInputs.Add(nestedNestNode.Children[i]);
PlanCompiler.Assert(newOutputVars.IsSet(ci.CollectionVar), "collectionVar not in output Vars?"); // I must have missed something...
}
}
// Then add in the rest of the inputs to the top level nest node (and
// they're collection Infos)
for (int i = 1; i < nestNode.Children.Count; i++) {
CollectionInfo ci = nestOp.CollectionInfo[i - 1];
newCollectionInfo.Add(ci);
newNestInputs.Add(nestNode.Children[i]);
PlanCompiler.Assert(newOutputVars.IsSet(ci.CollectionVar), "collectionVar not in output Vars?"); // I must have missed something...
}
//The prefix sort keys for the new nest op should include these of the input nestOp followed by the nestedNestOp
//(The nestOp-s that are being merged may have prefix sort keys propagated to them by constrainedSortOp-s pushed below them.
List sortKeys = ConsolidateSortKeys(nestOp.PrefixSortKeys, nestedNestOp.PrefixSortKeys);
// Make sure we pullup the sort keys in our output too...
foreach (InternalTrees.SortKey sk in sortKeys) {
newOutputVars.Set(sk.Var);
}
// Ready to go; build the new NestNode, etc.
MultiStreamNestOp newNestOp = Command.CreateMultiStreamNestOp(sortKeys, newOutputVars, newCollectionInfo);
Node newNode = Command.CreateNode(newNestOp, newNestInputs);
// Finally, recompute node info
Command.RecomputeNodeInfo(newNode);
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, newNode);
#endif //DEBUG
return newNode;
}
///
/// ProjectOp(X,{a,CollectOp(PhysicalProjectOp(Y)),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),Y)
/// ProjectOp(X,{a,VarRef(ref-to-collect-var-Y),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),copy-of-Y)
///
/// Remove CollectOps from projection, constructing a NestOp
/// over the ProjectOp.
///
///
/// collectionInfoList = new List();
List newChildren = new List();
List collectionNodes = new List();
VarVec externalReferences = Command.CreateVarVec();
VarVec collectionReferences = Command.CreateVarVec();
List definedVars = new List();
List referencedVars = new List();
foreach (Node chi in projectNode.Child1.Children) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Node definingExprNode = chi.Child0;
if (OpType.Collect == definingExprNode.Op.OpType) {
PlanCompiler.Assert(definingExprNode.HasChild0, "collect without input?");
PlanCompiler.Assert(OpType.PhysicalProject == definingExprNode.Child0.Op.OpType, "collect without physicalProject?");
Node physicalProjectNode = definingExprNode.Child0;
// Update collection var->defining node map;
m_definingNodeMap.Add(varDefOp.Var, physicalProjectNode);
ConvertToNestOpInput(physicalProjectNode, varDefOp.Var, collectionInfoList, collectionNodes, externalReferences, collectionReferences);
}
else if (OpType.VarRef == definingExprNode.Op.OpType) {
Var refVar = ResolveVarReference(varDefOp.Var);
Node physicalProjectNode;
if (m_definingNodeMap.TryGetValue(refVar, out physicalProjectNode)) {
physicalProjectNode = CopyCollectionVarDefinition(physicalProjectNode);
//SQLBUDT #602888: We need to track the copy too, in case we need to reuse it
m_definingNodeMap.Add(varDefOp.Var, physicalProjectNode);
ConvertToNestOpInput(physicalProjectNode, varDefOp.Var, collectionInfoList, collectionNodes, externalReferences, collectionReferences);
}
else {
referencedVars.Add(chi);
newChildren.Add(chi);
}
}
else {
definedVars.Add(chi);
newChildren.Add(chi);
}
}
// If we haven't identified a set of collection nodes, then we're done.
if (0 == collectionNodes.Count) {
return projectNode;
}
// OK, we found something. We have some heavy lifting to perform.
// Then we need to build up a MultiStreamNestOp above the ProjectOp and the
// new collection nodes to get what we really need.
// pretend that the keys included everything from the new projectOp
VarVec outputVars = Command.CreateVarVec(op.Outputs);
// First we need to modify this physicalProjectNode to leave out the collection
// Vars that we've just seen.
VarVec newProjectVars = Command.CreateVarVec(op.Outputs);
newProjectVars.Minus(collectionReferences);
// If there are any external references from any of the collections, add
// those to the projectOp explicitly. This must be ok because the projectOp
// could not have had any left-correlation
newProjectVars.Or(externalReferences);
// Create the new projectOp, and hook it into this one. The new projectOp
// no longer references the collections in it's children; of course we only
// construct a new projectOp if it actually projects out some Vars.
if (!newProjectVars.IsEmpty) {
if (IsNestOpNode(projectNode.Child0)) {
// If the input is a nest node, we need to figure out what to do with the
// rest of the in the VarDefList; we can't just pitch them, but we also
// really want to have the input be a nestop.
//
// What we do is essentially push any non-collection VarDef’s down under
// the driving node of the MSN:
//
// Project[Z,Y,W](Msn(X,Y),VarDef(Z=blah),VarDef(W=Collect(etc)) ==> MSN(MSN(Project[Z](X,VarDef(Z=blah)),Y),W)
//
// An optimization, of course being to not push anything down when there
// aren't any extra vars defined.
if (definedVars.Count == 0 && referencedVars.Count == 0) {
// We'll just pick the NestNode; we expect MergeNestedNestOps to merge
// it into what we're about to generate later.
projectNode = projectNode.Child0;
EnsureReferencedVarsAreRemoved(referencedVars, outputVars);
}
else {
NestBaseOp nestedNestOp = (NestBaseOp)projectNode.Child0.Op;
// Build the new ProjectOp to be used as input to the new nestedNestOp;
// it's input is the input to the current nestedNestOp and a new
// VarDefList with only the vars that were defined on the top level
// ProjectOp.
List newNestedProjectNodeInputs = new List();
newNestedProjectNodeInputs.Add(projectNode.Child0.Child0);
referencedVars.AddRange(definedVars);
newNestedProjectNodeInputs.Add(Command.CreateNode(Command.CreateVarDefListOp(), referencedVars));
VarVec newNestedProjectOutputs = Command.CreateVarVec(nestedNestOp.Outputs);
// SQLBUDT #508722: We need to remove the collection vars,
// these are not produced by the project
foreach (CollectionInfo ci in nestedNestOp.CollectionInfo) {
newNestedProjectOutputs.Clear(ci.CollectionVar);
}
foreach (Node varDefNode in referencedVars) {
newNestedProjectOutputs.Set(((VarDefOp)varDefNode.Op).Var);
}
Node newNestedProjectNode = Command.CreateNode(Command.CreateProjectOp(newNestedProjectOutputs), newNestedProjectNodeInputs);
// Now build the new nestedNestedNestOp, with the new nestedProjectOp
// as it's input; we have to update the outputs of the NestOp to include
// the vars we pushed down.
VarVec newNestedNestOutputs = Command.CreateVarVec(newNestedProjectOutputs);
newNestedNestOutputs.Or(nestedNestOp.Outputs);
MultiStreamNestOp newNestedNestOp = Command.CreateMultiStreamNestOp(
nestedNestOp.PrefixSortKeys,
newNestedNestOutputs,
nestedNestOp.CollectionInfo);
List newNestedNestNodeInputs = new List();
newNestedNestNodeInputs.Add(newNestedProjectNode);
for (int j = 1; j < projectNode.Child0.Children.Count; j++) {
newNestedNestNodeInputs.Add(projectNode.Child0.Children[j]);
}
projectNode = Command.CreateNode(newNestedNestOp, newNestedNestNodeInputs);
// We don't need to remove or remap referenced vars here because
// we're including them on the node we create; they won't become
// invalid.
}
}
else {
ProjectOp newProjectOp = Command.CreateProjectOp(newProjectVars);
projectNode.Child1 = Command.CreateNode(projectNode.Child1.Op, newChildren);
projectNode.Op = newProjectOp;
EnsureReferencedVarsAreRemapped(referencedVars);
}
}
else {
projectNode = projectNode.Child0;
EnsureReferencedVarsAreRemoved(referencedVars, outputVars);
}
// We need to make sure that we project out any external references to the driving
// node that the nested collections have, or we're going to end up with unresolvable
// vars when we pull them up over the current driving node. Of course, we only
// want the references that are actually ON the driving node.
externalReferences.And(projectNode.GetExtendedNodeInfo(Command).Definitions);
outputVars.Or(externalReferences);
// There are currently no prefix sortkeys. The processing for a SortOp may later
// introduce some prefix sortkeys, but there aren't any now.
MultiStreamNestOp nestOp = Command.CreateMultiStreamNestOp(new List(), outputVars, collectionInfoList);
// Insert the current node at the head of the the list of collections
collectionNodes.Insert(0, projectNode);
Node nestNode = Command.CreateNode(nestOp, collectionNodes);
// Finally, recompute node info
Command.RecomputeNodeInfo(projectNode);
Command.RecomputeNodeInfo(nestNode);
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, nestNode);
#endif //DEBUG
return nestNode;
}
///
/// If we're going to eat the ProjectNode, then we at least need to make
/// sure we remap any vars it defines as varRefs, and ensure that any
/// references to them are switched.
///
///
///
private void EnsureReferencedVarsAreRemoved(List referencedVars, VarVec outputVars) {
foreach (Node chi in referencedVars) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Var defVar = varDefOp.Var;
Var refVar = ResolveVarReference(defVar);
m_varRemapper.AddMapping(defVar, refVar);
outputVars.Clear(defVar);
outputVars.Set(refVar);
}
}
///
/// We need to make sure that we remap the column maps that we're pulling
/// up to point to the defined var, not it's reference.
///
///
private void EnsureReferencedVarsAreRemapped(List referencedVars) {
foreach (Node chi in referencedVars) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Var defVar = varDefOp.Var;
Var refVar = ResolveVarReference(defVar);
m_varRemapper.AddMapping(refVar, defVar);
}
}
///
/// Convert a CollectOp subtree (when used as the defining expression for a
/// VarDefOp) into a reasonable input to a NestOp.
///
///
/// There are a couple of cases that we handle here:
///
/// (a) PhysicalProject(X) ==> X
/// (b) PhysicalProject(Sort(X)) ==> Sort(X)
///
///
/// the child of the CollectOp
/// the collectionVar being defined
/// where to append the new collectionInfo
/// where to append the collectionNode
/// a bit vector of external references of the physicalProject
/// a bit vector of collection vars
private void ConvertToNestOpInput(Node physicalProjectNode, Var collectionVar, List collectionInfoList, List collectionNodes, VarVec externalReferences, VarVec collectionReferences) {
// Keep track of any external references the physicalProjectOp has
externalReferences.Or(Command.GetNodeInfo(physicalProjectNode).ExternalReferences);
// Case: (a) PhysicalProject(X) ==> X
Node nestOpInput = physicalProjectNode.Child0;
// Now build the collectionInfo for this input, including the flattened
// list of vars, which is essentially the outputs from the physicalProject
// with the sortKey vars that aren't already in the outputs we already
// have.
PhysicalProjectOp physicalProjectOp = (PhysicalProjectOp)physicalProjectNode.Op;
VarList flattenedElementVarList = Command.CreateVarList(physicalProjectOp.Outputs);
VarVec flattenedElementVarVec = Command.CreateVarVec(flattenedElementVarList); // Use a VarVec to make the lookups faster
List sortKeys = null;
if (OpType.Sort == nestOpInput.Op.OpType) {
// Case: (b) PhysicalProject(Sort(X)) ==> Sort(X)
SortOp sortOp = (SortOp)nestOpInput.Op;
sortKeys = OpCopier.Copy(Command , sortOp.Keys);
foreach (InternalTrees.SortKey sk in sortKeys) {
if (!flattenedElementVarVec.IsSet(sk.Var)) {
flattenedElementVarList.Add(sk.Var);
flattenedElementVarVec.Set(sk.Var);
}
}
}
else {
sortKeys = new List();
}
// Get the keys for the collection
VarVec keys = Command.CreateVarVec();
foreach (Var key in Command.GetExtendedNodeInfo(nestOpInput).Keys.KeyVars) {
if (flattenedElementVarVec.IsSet(key)) {
keys.Set(key);
}
}
// Create the collectionInfo.
CollectionInfo collectionInfo = Command.CreateCollectionInfo(collectionVar, physicalProjectOp.ColumnMap.Element, flattenedElementVarList, keys, sortKeys, null/*discriminatorValue*/);
// Now update the collections we're tracking.
collectionInfoList.Add(collectionInfo);
collectionNodes.Add(nestOpInput);
collectionReferences.Set(collectionVar);
}
///
/// Case 2 for ProjectOp: NestOp is the input:
///
/// ProjectOp(NestOp(X,Y,...)) => NestOp'(ProjectOp'(X),Y,...)
///
/// Remove collection references from the ProjectOp and pull the
/// NestOp over it, adding any outputs that the projectOp added.
///
/// The outputs are important here; expanding the above:
///
/// P{a,n}(N{x1,x2,x3,y}(X,Y)) => N{a,x1,x2,x3,y}(P{a,x1,x2,x3}(X),Y)
///
/// Strategy:
///
/// (1) Determine oldNestOpCollectionOutputs
/// (2) oldNestOpNonCollectionOutputs = oldNestOpOutputs - oldNestOpCollectionOutputs;
/// (3) oldProjectOpNonCollectionOutputs = oldProjectOpOutputs - oldNestOpCollectionOutputs
/// (4) oldProjectOpCollectionOutputs = oldProjectOpOutputs - oldProjectOpNonCollectionOutputs
/// (5) build a new list of collectionInfo's for the new NestOp, including
/// only oldProjectOpCollectionOutputs.
/// (6) leftCorrelationVars = vars that are defined by the left most child of the input nestOpNode
/// and used in the subtrees rooted at the other children of the input nestOpNode
/// (7) newProjectOpOutputs = oldProjectOpNonCollectionOutputs + oldNestOpNonCollectionOutputs + leftCorrelationVars
///
/// (8) newProjectOpChildren = ....
///
/// Of course everything needs to be "derefed", that is, expressed in the projectOp Var Ids.
///
/// (9) Set ProjectOp's input to NestOp's input
/// (10) Set NestOp's input to ProjectOp.
///
///
/// projectToNestVarMap = new Dictionary();
Command.RecomputeNodeInfo(projectNode);
ExtendedNodeInfo projectNodeInfo = Command.GetExtendedNodeInfo(projectNode);
ExtendedNodeInfo nestNodeInfo = Command.GetExtendedNodeInfo(nestNode);
foreach (Node chi in projectNode.Child1.Children) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Node definingExprNode = chi.Child0;
if (OpType.VarRef == definingExprNode.Op.OpType) {
VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
PlanCompiler.Assert(varRefOp.Var == varDefOp.Var || !projectNodeInfo.LocalDefinitions.IsSet(varRefOp.Var), "need to remap vars!");
//if (!projectToNestVarMap.ContainsKey(varRefOp.Var)) {
// projectToNestVarMap.Add(varRefOp.Var, varDefOp.Var);
//}
}
}
#endif //DEBUG
// (1) Determine oldNestOpCollectionOutputs
VarVec oldNestOpCollectionOutputs = Command.CreateVarVec();
foreach (CollectionInfo ci in nestOp.CollectionInfo) {
oldNestOpCollectionOutputs.Set(ci.CollectionVar);
}
// (2) oldNestOpNonCollectionOutputs = oldNestOpOutputs - oldNestOpCollectionOutputs;
VarVec oldNestOpNonCollectionOutputs = Command.CreateVarVec(nestOp.Outputs);
oldNestOpNonCollectionOutputs.Minus(oldNestOpCollectionOutputs);
// (3) oldProjectOpNonCollectionOutputs = oldProjectOpOutputs - oldNestOpCollectionOutputs
VarVec oldProjectOpNonCollectionOutputs = Command.CreateVarVec(projectOp.Outputs);
oldProjectOpNonCollectionOutputs.Minus(oldNestOpCollectionOutputs);
// (4) oldProjectOpCollectionOutputs = oldProjectOpOutputs - oldProjectOpNonCollectionOutputs
VarVec oldProjectOpCollectionOutputs = Command.CreateVarVec(projectOp.Outputs);
oldProjectOpCollectionOutputs.Minus(oldProjectOpNonCollectionOutputs);
// (5) build a new list of collectionInfo's for the new NestOp, including
// only oldProjectOpCollectionOutputs.
VarVec collectionsToRemove = Command.CreateVarVec(oldNestOpCollectionOutputs);
collectionsToRemove.Minus(oldProjectOpCollectionOutputs);
List newCollectionInfoList;
List newNestNodeChildren;
if (collectionsToRemove.IsEmpty) {
newCollectionInfoList = nestOp.CollectionInfo;
newNestNodeChildren = new List(nestNode.Children);
}
else {
newCollectionInfoList = new List();
newNestNodeChildren = new List();
newNestNodeChildren.Add(nestNode.Child0);
int i = 1;
foreach (CollectionInfo ci in nestOp.CollectionInfo) {
if (!collectionsToRemove.IsSet(ci.CollectionVar)) {
newCollectionInfoList.Add(ci);
newNestNodeChildren.Add(nestNode.Children[i]);
}
i++;
}
}
// (6) leftCorrelationVars = vars that are defined by the left most child of the input nestOpNode
// and used in the subtrees rooted at the other children of the input nestOpNode
// #479547: These need to be added to the outputs of the project
VarVec leftCorrelationVars = Command.CreateVarVec();
for (int i = 1; i < nestNode.Children.Count; i++) {
leftCorrelationVars.Or(nestNode.Children[i].GetExtendedNodeInfo(Command).ExternalReferences);
}
leftCorrelationVars.And(nestNode.Child0.GetExtendedNodeInfo(this.Command).Definitions);
// (7) newProjectOpOutputs = oldProjectOpNonCollectionOutputs + oldNestOpNonCollectionOutputs + leftCorrelationVars
VarVec newProjectOpOutputs = Command.CreateVarVec(oldProjectOpNonCollectionOutputs);
newProjectOpOutputs.Or(oldNestOpNonCollectionOutputs);
newProjectOpOutputs.Or(leftCorrelationVars);
// (8) newProjectOpChildren = ....
List newProjectOpChildren = new List(projectNode.Child1.Children.Count);
foreach (Node chi in projectNode.Child1.Children) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
if (newProjectOpOutputs.IsSet(varDefOp.Var)) {
newProjectOpChildren.Add(chi);
}
}
// (9) and (10), do the switch.
if (0 != newCollectionInfoList.Count) {
// In some cases, the only var in the projection is the collection var; so
// the new projectOp will have an empty projection list; we can't just pullup
// the input, so we add a temporary constant op to it, ensuring that we don't
// have an empty projection list.
if (newProjectOpOutputs.IsEmpty) {
PlanCompiler.Assert(newProjectOpChildren.Count == 0, "outputs is empty with non-zero count of children?");
NullOp tempOp = Command.CreateNullOp(Command.StringType);
Node tempNode = Command.CreateNode(tempOp);
Var tempVar;
Node varDefNode = Command.CreateVarDefNode(tempNode, out tempVar);
newProjectOpChildren.Add(varDefNode);
newProjectOpOutputs.Set(tempVar);
}
}
// Update the projectOp node with the new list of vars and
// the new list of children.
projectNode.Op = Command.CreateProjectOp(Command.CreateVarVec(newProjectOpOutputs));
projectNode.Child1 = Command.CreateNode(projectNode.Child1.Op, newProjectOpChildren);
if (0 == newCollectionInfoList.Count) {
// There are no remaining nested collections (because none of them
// were actually referenced) We just pullup the driving node of the
// nest and eliminate the nestOp entirely.
projectNode.Child0 = nestNode.Child0;
nestNode = projectNode;
}
else {
// We need to make sure that we project out any external references to the driving
// node that the nested collections have, or we're going to end up with unresolvable
// vars when we pull them up over the current driving node.
VarVec nestOpOutputs = Command.CreateVarVec(projectOp.Outputs);
for (int i = 1; i < newNestNodeChildren.Count; i++) {
nestOpOutputs.Or(newNestNodeChildren[i].GetNodeInfo(Command).ExternalReferences);
}
// We need to make sure we project out the sort keys too...
foreach (InternalTrees.SortKey sk in nestOp.PrefixSortKeys) {
nestOpOutputs.Set(sk.Var);
}
nestNode.Op = Command.CreateMultiStreamNestOp(nestOp.PrefixSortKeys, nestOpOutputs, newCollectionInfoList);
// we need to create a new node because we may have removed some of the collections.
nestNode = Command.CreateNode(nestNode.Op, newNestNodeChildren);
// Pull the nestNode up over the projectNode, and adjust
// their inputs accordingly.
projectNode.Child0 = nestNode.Child0;
nestNode.Child0 = projectNode;
Command.RecomputeNodeInfo(projectNode);
}
// Finally, recompute node info
Command.RecomputeNodeInfo(nestNode);
#if DEBUG
int size = input.Length; // GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, nestNode);
#endif //DEBUG
return nestNode;
}
///
/// SetOp common processing
///
///
/// The input to an IntersectOp or an ExceptOp cannot be a NestOp – that
/// would imply that we support distinctness over collections - which
/// we don’t.
///
/// UnionAllOp is somewhat trickier. We would need a way to percolate keys
/// up the UnionAllOp – and I’m ok with not supporting this case for now.
///
///
///
///
/// SingleRowOp
///
/// SingleRowOp(NestOp(x,...)) => NestOp(SingleRowOp(x),...)
///
///
///
///
/// SortOp
///
///
/// If the input to a SortOp is a NestOp, then none of the sort
/// keys can be collection Vars of the NestOp – we don't support
/// sorts over collections.
///
///
///
///
/// ConstrainedSortOp
///
///
/// Push the ConstrainedSortOp onto the driving node of the NestOp:
///
/// ConstrainedSortOp(NestOp(X,Y,...)) ==> NestOp(ConstrainedSortOp(X),Y,...)
///
/// There should not be any need for var renaming, because the ConstrainedSortOp cannot
/// refer to any vars from the NestOp
///
///
///
///
/// Helper method used by Visit(ConstrainedSortOp, Node)and Visit(SortOp, Node).
/// It returns a NestBaseOp equivalent to the inputNestOp, only with the given sortKeys
/// prepended to the prefix sort keys already on the inputNestOp.
///
///
///
/// sortKeys) {
NestBaseOp result;
// Include the sort keys as the prefix sort keys;
// Note that we can't actually have a SSNest at this point in
// the tree; they're only introduced once we've processed the
// entire tree.
if (inputNestOp.PrefixSortKeys.Count == 0) {
foreach (InternalTrees.SortKey sk in sortKeys) {
//SQLBUDT #507170 - We can't just add the sort keys, we need to copy them,
// to avoid changes to one to affect the other
inputNestOp.PrefixSortKeys.Add(Command.CreateSortKey(sk.Var, sk.AscendingSort, sk.Collation));
}
result = inputNestOp;
}
else {
VarVec sortVars = Command.CreateVarVec();
// First add the sort keys from the SortBaseOp, then the NestOp keys
List sortKeyList = ConsolidateSortKeys(sortKeys, inputNestOp.PrefixSortKeys);
PlanCompiler.Assert(inputNestOp is MultiStreamNestOp, "Unexpected SingleStreamNestOp?");
// Finally, build a new NestOp with the keys...
result = Command.CreateMultiStreamNestOp(sortKeyList, inputNestOp.Outputs, inputNestOp.CollectionInfo);
}
return result;
}
///
/// Helper method that given two lists of sort keys creates a single list of sort keys without duplicates.
/// First the keys from the first given list are added, then from the second one.
///
///
///
/// ConsolidateSortKeys(List sortKeyList1, List sortKeyList2) {
VarVec sortVars = Command.CreateVarVec();
List sortKeyList = new List();
foreach (InternalTrees.SortKey sk in sortKeyList1) {
if (!sortVars.IsSet(sk.Var)) {
sortVars.Set(sk.Var);
//SQLBUDT #507170 - We can't just add the sort keys, we need to copy them,
// to avoid changes to one to affect the other
sortKeyList.Add(Command.CreateSortKey(sk.Var, sk.AscendingSort, sk.Collation));
}
}
foreach (InternalTrees.SortKey sk in sortKeyList2) {
if (!sortVars.IsSet(sk.Var)){
sortVars.Set(sk.Var);
sortKeyList.Add(Command.CreateSortKey(sk.Var, sk.AscendingSort, sk.Collation));
}
}
return sortKeyList;
}
///
/// UnnestOp
///
///
/// Logically, the UnnestOp can simply be replaced with the defining expression
/// corresponding to the Var property of the UnnestOp. The tricky part is that
/// the UnnestOp produces a set of ColumnVars which may be referenced in other
/// parts of the query, and these need to be replaced by the corresponding Vars
/// produced by the defining expression.
///
/// There are essentially four cases:
///
/// Case 1: The UnnestOps Var is a UDT. Only the store can handle this, so we
/// pass it on without changing it.
///
/// Case 2: The UnnestOp has a Function as its input. This implies that the
/// store has TVFs, which it can Unnest, so we let it handle that and do
/// nothing.
///
/// Case 3: The UnnestOp Var defines a Nested collection. We'll just replace
/// the UnnestOp with the Input:
///
/// UnnestOp(VarDef(CollectOp(PhysicalProjectOp(input)))) => input
///
/// Case 4: The UnnestOp Var refers to a Nested collection from elsewhere. As we
/// discover NestOps, we maintain a var->PhysicalProject Node map. When
/// we get this case, we just make a copy of the PhysicalProject node, for
/// the referenced Var, and we replace the UnnestOp with it.
///
/// UnnestOp(VarDef(VarRef(v))) ==> copy-of-defining-node-for-v
///
/// Then, we need to update all references to the output Vars (ColumnVars) produced
/// by the Unnest to instead refer to the Vars produced by the copy of the subquery.
/// We produce a map from the Vars of the subquery to the corresponding vars of the
/// UnnestOp. We then use this map as we walk up the tree, and replace any references
/// to the Unnest Vars by the new Vars.
///
/// To simplify this process, as part of the ITreeGenerator, whenever we generate
/// an UnnestOp, we will generate a ProjectOp above it – which simply selects out
/// all Vars from the UnnestOp; and has no local definitions. This allows us to
/// restrict the Var->Var replacement to just ProjectOp.
///
///
///
/// (op.Var.Type);
if (TypeUtils.IsUdt(collType.TypeUsage)) {
return n;
}
// Find the VarDef node for the var we're supposed to unnest.
PlanCompiler.Assert(n.Child0.Op.OpType == OpType.VarDef, "Unnest without VarDef input?");
PlanCompiler.Assert(((VarDefOp)n.Child0.Op).Var == op.Var, "Unnest var not found?");
PlanCompiler.Assert(n.Child0.HasChild0, "VarDef without input?");
Node newNode = n.Child0.Child0;
if (OpType.Function == newNode.Op.OpType) {
// If we have an unnest over a function, there's nothing more we can do
// This really means that the underlying store has the ability to
// support TVFs, and therefore unnests, and we simply leave it as is
return n;
}
else if (OpType.Collect == newNode.Op.OpType) {
// UnnestOp(VarDef(CollectOp(PhysicalProjectOp(x)))) ==> x
PlanCompiler.Assert(newNode.HasChild0, "collect without input?");
newNode = newNode.Child0;
PlanCompiler.Assert(newNode.Op.OpType == OpType.PhysicalProject, "collect without physicalProject?");
// Ensure others that reference my var will know to use me;
m_definingNodeMap.Add(op.Var, newNode);
}
else if (OpType.VarRef == newNode.Op.OpType) {
// UnnestOp(VarDef(VarRef(v))) ==> copy-of-defining-node-for-v
//
// The Unnest's input is a VarRef; we need to replace it with
// the defining node, and ensure we fixup the vars.
Var refVar = ResolveVarReference(((VarRefOp)newNode.Op).Var);
Node refVarDefiningNode;
bool found = m_definingNodeMap.TryGetValue(refVar, out refVarDefiningNode);
PlanCompiler.Assert(found, "Could not find a definition for a referenced collection var");
newNode = CopyCollectionVarDefinition(refVarDefiningNode);
PlanCompiler.Assert(newNode.Op.OpType == OpType.PhysicalProject, "driving node is not physicalProject?");
}
else {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.InvalidInternalTree, 2, newNode.Op.OpType);
}
IEnumerable inputVars = ((PhysicalProjectOp)newNode.Op).Outputs;
PlanCompiler.Assert(newNode.HasChild0, "physicalProject without input?");
newNode = newNode.Child0;
// Bug 480721: a SortOp input to Unnest is irrelevant - eliminate it
if (newNode.Op.OpType == OpType.Sort) {
newNode = newNode.Child0;
}
// Update the replacement vars to reflect the pulled up operation
UpdateReplacementVarMap(op.Table.Columns, inputVars);
#if DEBUG
int size = input.Length; // GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, newNode);
#endif //DEBUG
return newNode;
}
///
/// Copies the given defining node for a collection var, but also makes sure to 'register' all newly
/// created collection vars (i.e. copied).
///
///SQLBUDT #557427: The defining node that is being copied may itself contain definitions to other
/// collection vars. These defintions would be present in m_definingNodeMap. However, after we make a copy
/// of the defining node, we need to make sure to also put 'matching' definitions of these other collection
/// vars into m_definingNodeMap.
/// The dictionary collectionVarDefinitions (below) contains the copied definitions of such collection vars.
/// but without the wrapping PhysicalProjectOp.
///
/// Example: m_definingNodeMap contains (var1, definition1) and (var2, definintion2).
/// var2 is defined inside the definition of var1.
/// Here we copy definition1 -> definintion1'.
/// We need to add to m_definitionNodeMap (var2', definition2').
/// definition2' should be a copy of definiton2 in the context of to definition1',
/// i.e. definition2' should relate to definition1' in same way that definition2 relates to definition1
/// ///
///
/// collectionVarDefinitions;
Node newNode = OpCopierTrackingCollectionVars.Copy(Command, refVarDefiningNode, out varMap, out collectionVarDefinitions);
if (collectionVarDefinitions.Count != 0) {
VarMap reverseMap = varMap.GetReverseMap();
foreach (KeyValuePair collectionVarDefinitionPair in collectionVarDefinitions) {
//
// Getting the matching definition for a collection map (i.e. definition2' from the example above)
//
// Definitions of collection vars are rooted at a PhysicalProjectOp,
// i.e. definition2 = PhysicalProjectOp(output2, columnMap2, definingSubtree2)
//
// The collectionVarDefinitions dictionary gives us the defining nodes rooted at what would a child
// of such PhysicalProjectOp, i.e. definingSubtree2'.
//
// definition2' = PhysicalProjectOp(CopyWithRemap(output2), CopyWithRemap(columnMap2), definingSubtree2')
//
Node keyDefiningNode;
Var keyDefiningVar = reverseMap[collectionVarDefinitionPair.Key];
//Note: we should not call ResolveVarReference(keyDefiningNode), we can only use the exact var
if (m_definingNodeMap.TryGetValue(keyDefiningVar, out keyDefiningNode)) {
PhysicalProjectOp originalPhysicalProjectOp = (PhysicalProjectOp)keyDefiningNode.Op;
VarList newOutputs = VarRemapper.RemapVarList(Command, varMap, originalPhysicalProjectOp.Outputs);
SimpleCollectionColumnMap newColumnMap = (SimpleCollectionColumnMap)ColumnMapCopier.Copy(originalPhysicalProjectOp.ColumnMap, varMap);
PhysicalProjectOp newPhysicalProjectOp = Command.CreatePhysicalProjectOp(newOutputs, newColumnMap);
Node newDefiningNode = Command.CreateNode(newPhysicalProjectOp, collectionVarDefinitionPair.Value);
m_definingNodeMap.Add(collectionVarDefinitionPair.Key, newDefiningNode);
}
}
}
return newNode;
}
#endregion
#region PhysicalOp Visitors
///
/// MultiStreamNestOp/SingleStreamNestOp common processing.
///
/// Pretty much just verifies that we didn't leave a NestOp behind.
///
///
///
///
/// PhysicalProjectOp
///
///
/// Tranformation:
///
/// PhysicalProjectOp(MultiStreamNestOp(...)) => PhysicalProjectOp(SortOp(...))
///
/// Strategy:
///
/// (1) Convert MultiStreamNestOp(...) => SingleStreamNestOp(...)
/// (2) Convert SingleStreamNestOp(...) => SortOp(...)
/// (3) Fixup the column maps.
///
///
///
///
/// varRefReplacementMap = new Dictionary();
VarList outputVars;
SimpleColumnMap[] keyColumnMaps;
nestNode = ConvertToSingleStreamNest(nestNode, varRefReplacementMap, out outputVars, out keyColumnMaps);
SingleStreamNestOp ssnOp = (SingleStreamNestOp)nestNode.Op;
// Build up the sort node (if necessary).
Node sortNode = BuildSortForNestElimination(ssnOp, nestNode);
// Create a new column map using the columnMapPatcher that was updated by the
// conversion to SingleStreamNest process.
SimpleCollectionColumnMap newProjectColumnMap = (SimpleCollectionColumnMap)ColumnMapTranslator.Translate(((PhysicalProjectOp)n.Op).ColumnMap, varRefReplacementMap);
newProjectColumnMap = new SimpleCollectionColumnMap(newProjectColumnMap.Type, newProjectColumnMap.Name, newProjectColumnMap.Element, keyColumnMaps, null, newProjectColumnMap.SortKeys);
// Ok, build the new PhysicalProjectOp, slap the sortNode as its input
// and we're all done.
n.Op = Command.CreatePhysicalProjectOp(outputVars, newProjectColumnMap);
n.Child0 = sortNode;
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, n);
#endif //DEBUG
return n;
}
///
/// Build up a sort node above the nestOp's input - only if there
/// are any sort keys to produce
///
///
///
/// sortKeyList = BuildSortKeyList(ssnOp);
// Now if, at this point, there aren't any sort keys then remove the
// sort operation, otherwise, build a new SortNode;
if (sortKeyList.Count > 0) {
SortOp sortOp = Command.CreateSortOp(sortKeyList);
sortNode = Command.CreateNode(sortOp, nestNode.Child0);
}
else {
// No sort keys => single_row_table => no need to sort
sortNode = nestNode.Child0;
}
return sortNode;
}
///
/// Build up the list of sortkeys. This list should comprise (in order):
///
/// - Any prefix sort keys (these represent sort operations on the
/// driving table, that were logically above the nest)
/// - The keys of the nest operation
/// - The discriminator column for the nest operation
/// - the list of postfix sort keys (used to represent nested collections)
///
/// Note that we only add the first occurrance of a var to the list; further
/// references to the same variable would be trumped by the first one.
///
///
/// BuildSortKeyList(SingleStreamNestOp ssnOp) {
VarVec sortVars = Command.CreateVarVec();
// First add the prefix sort keys
List sortKeyList = new List();
foreach (InternalTrees.SortKey sk in ssnOp.PrefixSortKeys) {
if (!sortVars.IsSet(sk.Var)) {
sortVars.Set(sk.Var);
sortKeyList.Add(sk);
}
}
// Then add the nestop keys
foreach (Var v in ssnOp.Keys) {
if (!sortVars.IsSet(v)) {
sortVars.Set(v);
InternalTrees.SortKey sk = Command.CreateSortKey(v);
sortKeyList.Add(sk);
}
}
// Then add the discriminator var
PlanCompiler.Assert(!sortVars.IsSet(ssnOp.Discriminator), "prefix sort on discriminator?");
sortKeyList.Add(Command.CreateSortKey(ssnOp.Discriminator));
// Finally, add the postfix keys
foreach (InternalTrees.SortKey sk in ssnOp.PostfixSortKeys) {
if (!sortVars.IsSet(sk.Var)) {
sortVars.Set(sk.Var);
sortKeyList.Add(sk);
}
}
return sortKeyList;
}
///
/// convert MultiStreamNestOp to SingleStreamNestOp
///
///
/// A MultiStreamNestOp is typically of the form M(D, N1, N2, ..., Nk)
/// where D is the driver stream, and N1, N2 etc. represent the collections.
///
/// In general, this can be converted into a SingleStreamNestOp over:
///
/// (D+ outerApply N1) AugmentedUnionAll (D+ outerApply N2) ...
///
/// Where:
///
/// D+ is D with an extra discriminator column that helps to identify
/// the specific collection.
///
/// AugmentedUnionAll is simply a unionAll where each branch of the
/// unionAll is augmented with nulls for the corresponding columns
/// of other tables in the branch
///
/// The simple case where there is only a single nested collection is easier
/// to address, and can be represented by:
///
/// MultiStreamNest(D, N1) => SingleStreamNest(OuterApply(D, N1))
///
/// The more complex case, where there is more than one nested column, requires
/// quite a bit more work:
///
/// MultiStreamNest(D, X, Y,...) => SingleStreamNest(UnionAll(Project{"1", D1...Dn, X1...Xn, nY1...nYn}(OuterApply(D, X)), Project{"2", D1...Dn, nX1...nXn, Y1...Yn}(OuterApply(D, Y)), ...))
///
/// Where:
/// D is the driving collection
/// D1...Dn are the columns from the driving collection
/// X is the first nested collection
/// X1...Xn are the columns from the first nested collection
/// nX1...nXn are null values for all columns from the first nested collection
/// Y is the second nested collection
/// Y1...Yn are the columns from the second nested collection
/// nY1...nYn are null values for all columns from the second nested collection
///
///
///
///
///
/// varRefReplacementMap, out VarList flattenedOutputVarList, out SimpleColumnMap[] parentKeyColumnMaps) {
#if DEBUG
string input = Dump.ToXml(Command, nestNode);
#endif //DEBUG
MultiStreamNestOp nestOp = (MultiStreamNestOp)nestNode.Op;
// We can't convert this node to a SingleStreamNest until all it's MultiStreamNest
// inputs are converted, so do that first.
for (int i = 1; i < nestNode.Children.Count; i++) {
Node chi = nestNode.Children[i];
if (chi.Op.OpType == OpType.MultiStreamNest) {
CollectionInfo chiCi = nestOp.CollectionInfo[i - 1];
VarList childFlattenedOutputVars;
SimpleColumnMap[] childKeyColumnMaps;
nestNode.Children[i] = ConvertToSingleStreamNest(chi, varRefReplacementMap, out childFlattenedOutputVars, out childKeyColumnMaps);
// Now this may seem odd here, and it may look like we should have done this
// inside the recursive ConvertToSingleStreamNest call above, but that call
// doesn't have access to the CollectionInfo for it's parent, which is what
// we need to manipulate before we enter the loop below where we try and fold
// THIS nestOp nodes into a singleStreamNestOp.
ColumnMap childColumnMap = ColumnMapTranslator.Translate(chiCi.ColumnMap, varRefReplacementMap);
VarVec childKeys = Command.CreateVarVec(((SingleStreamNestOp)nestNode.Children[i].Op).Keys);
nestOp.CollectionInfo[i - 1] = Command.CreateCollectionInfo(chiCi.CollectionVar,
childColumnMap,
childFlattenedOutputVars,
childKeys,
chiCi.SortKeys,
null /*discriminatorValue*/
);
}
}
// Make sure that the driving node has keys defined. Otherwise we're in
// trouble; we must be able to infer keys from the driving node; If it's
// available, we'll use the NewGuid canonical function to put a key on the
// driving node.
Node drivingNode = nestNode.Child0;
KeyVec drivingNodeKeys = Command.PullupKeys(drivingNode);
// Get a deterministic ordering of Vars from this node.
// NOTE: we're using the drivingNode's definitions, which is a VarVec so it
// won't match the order of the input's columns, but the key thing is
// that we use the same order for all nested children, so it's OK.
ExtendedNodeInfo drivingNodeInfo = Command.GetExtendedNodeInfo(drivingNode);
VarVec drivingNodeVarVec = drivingNodeInfo.Definitions;
VarList drivingNodeVars = Command.CreateVarList(drivingNodeVarVec);
if (drivingNodeKeys.NoKeys) {
// No Keys. We'll Transform the statement to add a NewGuid as follows:
//
// MultiStreamNest(D, X, Y,...) => MultiStreamNest(Project{NewGuid},(D), X, Y,...)
md.EdmFunction newGuidFunction;
if (!TryGetNewGuidFunction(out newGuidFunction)) {
// If we can't get the NewGuid canonical function, we'll just throw
// an exception indicating that we need keys.
throw EntityUtil.KeysRequiredForNesting();
}
// Construct the FunctionOp, the VarDef and The VarDefList to call the
// NewGuid canonical function,
Var newGuidVar;
Node newVarDefListNode = Command.CreateVarDefListNode(
Command.CreateNode(
Command.CreateFunctionOp(newGuidFunction)), out newGuidVar);
// We need to make a copy of the drivingNodeVarVec, because we don't want
// to modify the one that's in the extendedNodeInfo. Once we do, we set
// the var from the NewGuid in both it and the varlist.
drivingNodeVarVec = Command.CreateVarVec(drivingNodeVarVec);
drivingNodeVarVec.Set(newGuidVar);
drivingNodeVars.Add(newGuidVar);
// While we're at it, make sure we update the KeyVars to include the var from
// the NewGuid, effectively solveing our problem.
drivingNodeKeys = new KeyVec(Command);
drivingNodeKeys.KeyVars.Set(newGuidVar);
// OK, construct a new projectOp and node to go above the driving node, and
// hook it into the driving node of the nest op.
drivingNode = Command.CreateNode(Command.CreateProjectOp(drivingNodeVarVec), drivingNode, newVarDefListNode);
nestNode.Child0 = drivingNode;
// Finally, we have to create a new MultiStreamNestOp that includes the key
// value we just added in its outputs.
VarVec newNestopOutputs = Command.CreateVarVec(nestOp.Outputs);
newNestopOutputs.Set(newGuidVar);
nestOp = Command.CreateMultiStreamNestOp(nestOp.PrefixSortKeys, newNestopOutputs, nestOp.CollectionInfo);
nestNode.Op = nestOp;
Command.RecomputeNodeInfo(nestNode);
}
// Normalize all collection inputs to the nestOp. Specifically, remove any
// SortOps (adding the sort keys to the postfix sortkey list). Additionally,
// add a discriminatorVar to each collection child
VarList discriminatorVarList;
List> postfixSortKeyList;
NormalizeNestOpInputs(nestOp, nestNode, out discriminatorVarList, out postfixSortKeyList);
// Now build up the union-all subquery
List> varMapList;
Var outputDiscriminatorVar;
Node unionAllNode = BuildUnionAllSubqueryForNestOp(nestOp, nestNode, drivingNodeVars, discriminatorVarList, out outputDiscriminatorVar, out varMapList);
Dictionary drivingNodeVarMap = varMapList[0];
// OK. We've finally created the UnionAll over each of the project/outerApply
// combinations. We know that the output columns will be:
//
// Discriminator, DrivingColumns, Collection1Columns, Collection2Columns, ...
//
// Now, rebuild the columnMaps, since all of the columns in the original column
// maps are now referencing newer variables. To do that, we'll walk the list of
// outputs from the unionAll, and construct new VarRefColumnMaps for each one,
// and adding it to a ColumnMapPatcher, which we'll use to actually fix everything
// up.
//
// While we're at it, we'll build a new list of top-level output columns, which
// should include only the Discriminator, the columns from the driving collection,
// and and one column for each of the nested collections.
// Start building the flattenedOutputVarList that the top level PhysicalProjectOp
// is to output.
flattenedOutputVarList = Command.CreateVarList(RemapVars(drivingNodeVars, drivingNodeVarMap));
VarVec flattenedOutputVarVec = Command.CreateVarVec(flattenedOutputVarList);
VarVec nestOpOutputs = Command.CreateVarVec(flattenedOutputVarVec);
// Add any adjustments to the driving nodes vars to the column map patcher
foreach (KeyValuePair kv in drivingNodeVarMap) {
if (kv.Key != kv.Value) {
varRefReplacementMap[kv.Key] = new VarRefColumnMap(kv.Value);
}
}
RemapSortKeys(nestOp.PrefixSortKeys, drivingNodeVarMap);
List newPostfixSortKeys = new List();
List newCollectionInfoList = new List();
// Build the discriminator column map, and ensure it's in the outputs
VarRefColumnMap discriminatorColumnMap = new VarRefColumnMap(outputDiscriminatorVar);
nestOpOutputs.Set(outputDiscriminatorVar);
if (!flattenedOutputVarVec.IsSet(outputDiscriminatorVar)) {
flattenedOutputVarList.Add(outputDiscriminatorVar);
flattenedOutputVarVec.Set(outputDiscriminatorVar);
}
// Build the key column maps, and ensure they're in the outputs as well.
VarVec parentKeys = RemapVarVec(drivingNodeKeys.KeyVars, drivingNodeVarMap);
parentKeyColumnMaps = new SimpleColumnMap[parentKeys.Count];
int index = 0;
foreach (Var keyVar in parentKeys) {
parentKeyColumnMaps[index] = new VarRefColumnMap(keyVar);
index++;
if (!flattenedOutputVarVec.IsSet(keyVar)) {
flattenedOutputVarList.Add(keyVar);
flattenedOutputVarVec.Set(keyVar);
}
}
// Now that we've handled the driving node, deal with each of the
// nested inputs, in sequence.
for (int i = 1; i < nestNode.Children.Count; i++) {
CollectionInfo ci = nestOp.CollectionInfo[i - 1];
List postfixSortKeys = postfixSortKeyList[i];
RemapSortKeys(postfixSortKeys, varMapList[i]);
newPostfixSortKeys.AddRange(postfixSortKeys);
ColumnMap newColumnMap = ColumnMapTranslator.Translate(ci.ColumnMap, varMapList[i]);
VarList newFlattenedElementVars = RemapVarList(ci.FlattenedElementVars, varMapList[i]);
VarVec newCollectionKeys = RemapVarVec(ci.Keys, varMapList[i]);
RemapSortKeys(ci.SortKeys, varMapList[i]);
CollectionInfo newCollectionInfo = Command.CreateCollectionInfo(
ci.CollectionVar,
newColumnMap,
newFlattenedElementVars,
newCollectionKeys,
ci.SortKeys,
i);
newCollectionInfoList.Add(newCollectionInfo);
// For a collection Var, we add the flattened elementVars for the
// collection in place of the collection Var itself, and we create
// a new column map to represent all the stuff we've done.
foreach (Var v in newFlattenedElementVars) {
if (!flattenedOutputVarVec.IsSet(v)) {
flattenedOutputVarList.Add(v);
flattenedOutputVarVec.Set(v);
}
}
nestOpOutputs.Set(ci.CollectionVar);
int keyColumnMapIndex = 0;
SimpleColumnMap[] keyColumnMaps = new SimpleColumnMap[newCollectionInfo.Keys.Count];
foreach (Var keyVar in newCollectionInfo.Keys) {
keyColumnMaps[keyColumnMapIndex] = new VarRefColumnMap(keyVar);
keyColumnMapIndex++;
}
SortKeyInfo[] sortKeyColumnMaps = new SortKeyInfo[newCollectionInfo.SortKeys.Count];
for(int k = 0; k < sortKeyColumnMaps.Length; ++k) {
InternalTrees.SortKey sortKey = newCollectionInfo.SortKeys[k];
VarRefColumnMap varRefColumnMap = new VarRefColumnMap(sortKey.Var);
sortKeyColumnMaps[k] = new SortKeyInfo(varRefColumnMap, sortKey.AscendingSort, sortKey.Collation);
}
DiscriminatedCollectionColumnMap collectionColumnMap = new DiscriminatedCollectionColumnMap(
TypeUtils.CreateCollectionType(newCollectionInfo.ColumnMap.Type),
newCollectionInfo.ColumnMap.Name,
newCollectionInfo.ColumnMap,
keyColumnMaps,
parentKeyColumnMaps,
sortKeyColumnMaps,
discriminatorColumnMap,
newCollectionInfo.DiscriminatorValue
);
varRefReplacementMap[ci.CollectionVar] = collectionColumnMap;
}
// Finally, build up the SingleStreamNest Node
SingleStreamNestOp newSsnOp = Command.CreateSingleStreamNestOp(
parentKeys,
nestOp.PrefixSortKeys,
newPostfixSortKeys,
nestOpOutputs,
newCollectionInfoList,
outputDiscriminatorVar);
Node newNestNode = Command.CreateNode(newSsnOp, unionAllNode);
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, newNestNode);
#endif //DEBUG
return newNestNode;
}
///
/// "Normalize" each input to the NestOp.
/// We're now in the context of a MultiStreamNestOp, and we're trying to convert this
/// into a SingleStreamNestOp.
///
/// Normalization specifically refers to
/// - augmenting each input with a discriminator value (that describes the collection)
/// - removing the sort node at the root (and capturing this information as part of the sortkeys)
///
/// the nestOp
/// the nestOp subtree
/// Discriminator Vars for each Collection input
/// SortKeys (postfix) for each Collection input
///
///
private void NormalizeNestOpInputs(NestBaseOp nestOp, Node nestNode, out VarList discriminatorVarList, out List> sortKeys) {
discriminatorVarList = Command.CreateVarList();
// We insert a dummy var and value at poistion 0 for the deriving node, which
// we should never reference;
discriminatorVarList.Add(null);
sortKeys = new List>();
sortKeys.Add(nestOp.PrefixSortKeys);
for (int i = 1; i < nestNode.Children.Count; i++) {
Node inputNode = nestNode.Children[i];
// Since we're called from ConvertToSingleStreamNest, it is possible that we have a
// SingleStreamNest here, because the input to the MultiStreamNest we're converting
// may have been a MultiStreamNest that was converted to a SingleStreamNest.
SingleStreamNestOp ssnOp = inputNode.Op as SingleStreamNestOp;
// If this collection is a SingleStreamNest, we pull up the key information
// in it, and pullup the input;
if (null != ssnOp) {
// Note that the sortKeys argument is 1:1 with the nestOp inputs, that is
// each input may have exactly one entry in the list, so we have to combine
// all of the sort key components (Prefix+Keys+Discriminator+PostFix) into
// one list.
List mySortKeys = BuildSortKeyList(ssnOp);
sortKeys.Add(mySortKeys);
inputNode = inputNode.Child0;
}
else {
// If the current collection has a SortNode specified, then pull that
// out, and add the information to the list of postfix SortColumns
SortOp sortOp = inputNode.Op as SortOp;
if (null != sortOp) {
inputNode = inputNode.Child0; // bypass the sort node
// Add the sort keys to the list of postfix sort keys
sortKeys.Add(sortOp.Keys);
}
else {
// No postfix sort keys for this case
sortKeys.Add(new List());
}
}
// #447304: Ensure that any SortKey Vars will be projected from the input in addition to showing up in the postfix sort keys
// by adding them to the FlattenedElementVars for this NestOp input's CollectionInfo.
VarList flattenedElementVars = nestOp.CollectionInfo[i - 1].FlattenedElementVars;
foreach (InternalTrees.SortKey sortKey in sortKeys[i]) {
if (!flattenedElementVars.Contains(sortKey.Var)) {
flattenedElementVars.Add(sortKey.Var);
}
}
// Add a discriminator column to the collection-side - this must
// happen before the outer-apply is added on; we need to use the value of
// the discriminator to distinguish between null and empty collections
Var discriminatorVar;
Node augmentedInput = AugmentNodeWithInternalConstant(inputNode, i, out discriminatorVar);
nestNode.Children[i] = augmentedInput;
discriminatorVarList.Add(discriminatorVar);
}
}
///
/// Add an internal integer constant to a node. Specifically:
///
/// N ==> Project(N,{definitions-from-N, internalConstant})
///
/// the input node to augment
/// the value for the itnernal constant
/// the computed Var for the internal constant
/// the augmented node
private Node AugmentNodeWithInternalConstant(Node input, int internalConstantValue, out Var internalConstantVar) {
// Construct the internal constant value, a ConstantOp node, and
// a VarDef node that that defines it.
InternalConstantOp discriminatorOp = Command.CreateInternalConstantOp(Command.IntegerType, internalConstantValue);
Node discriminatorNode = Command.CreateNode(discriminatorOp);
Node varDefListNode = Command.CreateVarDefListNode(discriminatorNode, out internalConstantVar);
// Now identify the list of definitions from the input, and project out
// every one of them and include the internalConstantVar
ExtendedNodeInfo inputNodeInfo = Command.GetExtendedNodeInfo(input);
VarVec projectOutputs = Command.CreateVarVec(inputNodeInfo.Definitions);
projectOutputs.Set(internalConstantVar);
ProjectOp projectOp = Command.CreateProjectOp(projectOutputs);
Node projectNode = Command.CreateNode(projectOp, input, varDefListNode);
return projectNode;
}
///
/// Convert a SingleStreamNestOp into a massive UnionAllOp
///
///
///
///
///
///
///
///
/// > varMapList) {
Node drivingNode = nestNode.Child0;
// For each of the NESTED collections...
Node unionAllNode = null;
VarList unionAllOutputs = null;
for (int i = 1; i < nestNode.Children.Count; i++) {
// Ensure we only use the driving collection tree once, so other
// transformations do not unintentionally change more than one path.
// To prevent nodes in the tree from being used in multiple paths,
// we copy the driving input on successive nodes.
VarList newDrivingNodeVars;
Node newDrivingNode;
VarList newFlattenedElementVars;
Op op;
if (i > 1) {
newDrivingNode = OpCopier.Copy(Command, drivingNode, drivingNodeVars, out newDrivingNodeVars);
//
// Bug 450245: If we copied the driver node, then references to driver node vars
// from the collection subquery must be patched up
//
VarRemapper varRemapper = new VarRemapper(this.Command);
for (int j = 0; j < drivingNodeVars.Count; j++) {
varRemapper.AddMapping(drivingNodeVars[j], newDrivingNodeVars[j]);
}
// Remap all references in the current subquery
varRemapper.RemapSubtree(nestNode.Children[i]);
// Bug 479183: Remap the flattened element vars
newFlattenedElementVars = varRemapper.RemapVarList(nestOp.CollectionInfo[i - 1].FlattenedElementVars);
// Create a cross apply for all but the first collection
op = Command.CreateCrossApplyOp();
}
else {
newDrivingNode = drivingNode;
newDrivingNodeVars = drivingNodeVars;
newFlattenedElementVars = nestOp.CollectionInfo[i - 1].FlattenedElementVars;
// Create an outer apply for the first collection,
// that way we ensure at least one row for each row in the driver node.
op = Command.CreateOuterApplyOp();
}
// Create an outer apply with the driver node and the nested collection.
Node applyNode = Command.CreateNode(op, newDrivingNode, nestNode.Children[i]);
// Now create a ProjectOp that augments the output from the OuterApplyOp
// with nulls for each column from other collections
// Build the VarDefList (the list of vars) for the Project, starting
// with the collection discriminator var
List varDefListChildren = new List();
VarList projectOutputs = Command.CreateVarList();
// Add the collection discriminator var to the output.
projectOutputs.Add(discriminatorVarList[i]);
// Add all columns from the driving node
projectOutputs.AddRange(newDrivingNodeVars);
// Add all the vars from all the nested collections;
for (int j = 1; j < nestNode.Children.Count; j++) {
CollectionInfo otherCollectionInfo = nestOp.CollectionInfo[j - 1];
// For the current nested collection, we just pick the var that's
// coming from there and don't need have a new var defined, but for
// the rest we construct null values.
if (i == j) {
projectOutputs.AddRange(newFlattenedElementVars);
}
else {
foreach (Var v in otherCollectionInfo.FlattenedElementVars) {
NullOp nullOp = Command.CreateNullOp(v.Type);
Node nullOpNode = Command.CreateNode(nullOp);
Var nullOpVar;
Node nullOpVarDefNode = Command.CreateVarDefNode(nullOpNode, out nullOpVar);
varDefListChildren.Add(nullOpVarDefNode);
projectOutputs.Add(nullOpVar);
}
}
}
Node varDefListNode = Command.CreateNode(Command.CreateVarDefListOp(), varDefListChildren);
// Now, build up the projectOp
VarVec projectOutputsVarSet = Command.CreateVarVec(projectOutputs);
ProjectOp projectOp = Command.CreateProjectOp(projectOutputsVarSet);
Node projectNode = Command.CreateNode(projectOp, applyNode, varDefListNode);
// finally, build the union all
if (unionAllNode == null) {
unionAllNode = projectNode;
unionAllOutputs = projectOutputs;
}
else {
VarMap unionAllMap = new VarMap();
VarMap projectMap = new VarMap();
for (int idx = 0; idx < unionAllOutputs.Count; idx++) {
Var outputVar = Command.CreateSetOpVar(unionAllOutputs[idx].Type);
unionAllMap.Add(outputVar, unionAllOutputs[idx]);
projectMap.Add(outputVar, projectOutputs[idx]);
}
UnionAllOp unionAllOp = Command.CreateUnionAllOp(unionAllMap, projectMap);
unionAllNode = Command.CreateNode(unionAllOp, unionAllNode, projectNode);
// Get the output vars from the union-op. This must be in the same order
// as the original list of Vars
unionAllOutputs = GetUnionOutputs(unionAllOp, unionAllOutputs);
}
}
// We're done building the node, but now we have to build a mapping from
// the before-Vars to the after-Vars
varMapList = new List>();
IEnumerator outputVarsEnumerator = unionAllOutputs.GetEnumerator();
if (!outputVarsEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 4); // more columns from children than are on the unionAll?
}
// The discriminator var is always first
discriminatorVar = outputVarsEnumerator.Current;
// Build a map for each input
for (int i = 0; i < nestNode.Children.Count; i++) {
Dictionary varMap = new Dictionary();
VarList varList = (i == 0) ? drivingNodeVars : nestOp.CollectionInfo[i - 1].FlattenedElementVars;
foreach (Var v in varList) {
if (!outputVarsEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 5); // more columns from children than are on the unionAll?
}
varMap[v] = outputVarsEnumerator.Current;
}
varMapList.Add(varMap);
}
if (outputVarsEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 6); // at this point, we better be done with both lists...
}
return unionAllNode;
}
///
/// Get back an ordered list of outputs from a union-all op. The ordering should
/// be identical to the ordered list "leftVars" which describes the left input of
/// the unionAllOp
///
/// the unionall Op
/// vars of the left input
/// output vars ordered in the same way as the left input
private static VarList GetUnionOutputs(UnionAllOp unionOp, VarList leftVars) {
VarMap varMap = unionOp.VarMap[0];
Dictionary reverseVarMap = varMap.GetReverseMap();
VarList unionAllVars = Command.CreateVarList();
foreach (Var v in leftVars) {
Var newVar = reverseVarMap[v];
unionAllVars.Add(newVar);
}
return unionAllVars;
}
///
/// Tries to get NewGuid canonical function.
///
/// out EdmFunction for NewGuid canonical function
/// true if a unique Edm.NewGuid canonical function was found, false otherwise
private bool TryGetNewGuidFunction(out md.EdmFunction newGuidFunction) {
newGuidFunction = null;
System.Collections.ObjectModel.ReadOnlyCollection functions = m_compilerState.MetadataWorkspace.GetFunctions("NewGuid", "Edm", System.Data.Metadata.Edm.DataSpace.CSpace);
if (null != functions && 1 == functions.Count) {
newGuidFunction = functions[0];
}
return (null != newGuidFunction);
}
#endregion
#endregion
}
#region Class OpCopierTrackingCollectionVars
///
/// Wrapper around OpCopier to keep track of the defining subtrees
/// of collection vars defined in the subtree being returned as a copy.
///
internal class OpCopierTrackingCollectionVars : OpCopier {
#region Private State
private Dictionary m_newCollectionVarDefinitions = new Dictionary();
#endregion
#region Private Constructor
private OpCopierTrackingCollectionVars(Command cmd) : base(cmd) {
}
#endregion
#region Public Surface
///
/// Equivalent to OpCopier.Copy, only in addition it keeps track of the defining subtrees
/// of collection vars defined in the subtree rooted at the copy of the input node n.
///
///
///
///
///
/// newCollectionVarDefinitions) {
OpCopierTrackingCollectionVars oc = new OpCopierTrackingCollectionVars(cmd);
Node newNode = oc.CopyNode(n);
varMap = oc.m_varMap;
newCollectionVarDefinitions = oc.m_newCollectionVarDefinitions;
return newNode;
}
#endregion
#region Visitor Members
///
/// Tracks the collection vars after calling the base implementation
///
///
///
///
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Collections.Generic;
using System.Globalization;
using System.Data.Common;
using md = System.Data.Metadata.Edm;
using System.Data.Query.InternalTrees;
using System.Data.Query.PlanCompiler;
namespace System.Data.Query.PlanCompiler {
///
/// This class "pulls" up nest operations to the root of the tree
///
///
/// The goal of this module is to eliminate nest operations from the query - more
/// specifically, the nest operations are pulled up to the root of the query instead.
///
internal class NestPullup : BasicOpVisitorOfNode {
#region private state
private PlanCompiler m_compilerState;
///
/// map from a collection var to the node where it's defined; the node should be
/// the node that should be used as the replacement for the var if it is referred
/// to in an UnnestOp (through a VarRef) Note that we expect this to contain the
/// PhysicalProjectOp of the node, so we can use the VarList when mapping vars to
/// the copy; (We'll remove the PhysicalProjectOp when we copy it...)
///
private Dictionary m_definingNodeMap = new Dictionary();
///
/// map from var to the var we're supposed to replace it with
///
private VarRemapper m_varRemapper;
///
/// Map from VarRef vars to what they're referencing; used to enable the defining
/// node map to contain only the definitions, not all the references to it.
///
private Dictionary m_varRefMap = new Dictionary();
#endregion
#region constructor
private NestPullup(PlanCompiler compilerState) {
m_compilerState = compilerState;
m_varRemapper = new VarRemapper(compilerState.Command);
}
#endregion
#region Process Driver
internal static void Process(PlanCompiler compilerState) {
NestPullup np = new NestPullup(compilerState);
np.Process();
}
///
/// The driver routine. Does all the hard work of processing
///
private void Process() {
PlanCompiler.Assert(Command.Root.Op.OpType == OpType.PhysicalProject, "root node is not physicalProject?");
Command.Root = VisitNode(Command.Root);
}
#endregion
#region private methods
#region VisitorHelpers
///
/// the iqt we're processing
///
private Command Command { get { return m_compilerState.Command; } }
///
/// is the node a NestOp node?
///
///
///
/// Not Supported common processing
///
/// For all those cases where we don't intend to support
/// a nest operation as a child, we have this routine to
/// do the work.
///
///
///
///
/// Follow the VarRef chain to the defining var
///
///
///
/// Update the replacement Var map with the vars from the pulled-up
/// operation; the shape is supposed to be identical, so we should not
/// have more vars on either side, and the order is guaranteed to be
/// the same.
///
///
///
private void UpdateReplacementVarMap(IEnumerable fromVars, IEnumerable toVars) {
IEnumerator toVarEnumerator = toVars.GetEnumerator();
foreach (Var v in fromVars) {
if (!toVarEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 2);
}
m_varRemapper.AddMapping(v, toVarEnumerator.Current);
}
if (toVarEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 3);
}
}
#region remapping helpers
///
/// Replace a list of sortkeys *IN-PLACE* with the corresponding "mapped" Vars
///
/// sortkeys
/// the mapping info for Vars
private static void RemapSortKeys(List sortKeys, Dictionary varMap) {
if (sortKeys != null) {
foreach (InternalTrees.SortKey sortKey in sortKeys) {
Var replacementVar;
if (varMap.TryGetValue(sortKey.Var, out replacementVar)) {
sortKey.Var = replacementVar;
}
}
}
}
///
/// Produce a "mapped" sequence of the input Var sequence - based on the supplied
/// map
///
/// input var sequence
/// var->var map
/// the mapped var sequence
private IEnumerable RemapVars(IEnumerable vars, Dictionary varMap) {
foreach (Var v in vars) {
Var mappedVar;
if (varMap.TryGetValue(v, out mappedVar)) {
yield return mappedVar;
}
else {
yield return v;
}
}
}
///
/// Produce a "mapped" varList
///
///
///
/// varMap) {
VarList newVarList = Command.CreateVarList(RemapVars(varList, varMap));
return newVarList;
}
///
/// Produce a "mapped" varVec
///
///
///
/// varMap) {
VarVec newVarVec = Command.CreateVarVec(RemapVars(varVec, varMap));
return newVarVec;
}
#endregion
#endregion
#region AncillaryOp Visitors
///
/// VarDefOp
///
/// Essentially, maintains m_varRefMap, adding an entry for each VarDef that has a
/// VarRef on it.
///
///
///
///
/// VarRefOp
///
///
/// When we remove the UnnestOp, we are left with references to it's column vars that
/// need to be fixed up; we do this by creating a var replacement map when we remove the
/// UnnestOp and whenever we find a reference to a var in the map, we replace it with a
/// reference to the replacement var instead;
///
///
///
///
/// We don't yet support nest pullups over Case
///
///
///
///
/// Default RelOp processing:
///
/// We really don't want to allow any NestOps through; just fail if we don't have
/// something coded.
///
///
///
///
/// ApplyOp/JoinOp common processing
///
///
/// If one of the inputs to any JoinOp/ApplyOp is a NestOp, then the NestOp
/// can be pulled above the join/apply if every input to the join/apply has
/// a key(s). The keys of the NestOp are augmented with the keys of the
/// other join inputs:
///
/// JoinOp/ApplyOp(NestOp(X, ...), Y) => NestOp(JoinOp/ApplyOp(X, Y), ...)
///
/// In addition, if the NestOp is on a 'nullable' side of a join (i.e. right side of
/// LeftOuterJoin/OuterApply or either side of FullOuterJoin), the driving node
/// of that NestOp (X) is capped with a project with a null sentinel and
/// the dependant collection nodes (the rest of the NestOp children)
/// are filtered based on that sentinel:
///
/// LOJ/OA/FOJ (X, NestOp(Y, Z1, Z2, ..ZN)) => NestOp( LOJ/OA/FOJ (X, PROJECT (Y, v = 1)), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
/// FOJ (NestOp(Y, Z1, Z2, ..ZN), X) => NestOp( LOJ/OA/FOJ (PROJECT (Y, v = 1), X), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
///
/// Also, FILTER(Zi, v != null) may be transformed to push the filter below any NestOps.
///
/// Requires: Every input to the join/apply must have a key.
///
///
///
/// newNestChildren = new List();
List newJoinApplyChildren = new List();
List newCollectionInfoList = new List();
foreach (Node chi in n.Children) {
if (chi.Op.OpType == OpType.MultiStreamNest) {
newCollectionInfoList.AddRange(((MultiStreamNestOp)chi.Op).CollectionInfo);
// SQLBUDT #615513: If the nest op is on a 'nullable' side of join
// (i.e. right side of LeftOuterJoin/OuterApply or either side of FullOuterJoin)
// the driving node of that nest operation needs to be capped with a project with
// a null sentinel and the dependant collection nodes need to be filtered based on that sentinel.
//
// LOJ/OA/FOJ (X, MSN(Y, Z1, Z2, ..ZN)) => MSN( LOJ/OA/FOJ (X, PROJECT (Y, v = 1)), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
// FOJ (MSN(Y, Z1, Z2, ..ZN), X) => MSN( LOJ/OA/FOJ (PROJECT (Y, v = 1), X), FILTER(Z1, v!=null), FILTER(Z2, v!=null), ... FILTER(ZN, v!=null))
//
// Note: we transform FILTER(Zi, v != null) to push the filter below any MSNs.
if ((op.OpType == OpType.FullOuterJoin)
|| ((op.OpType == OpType.LeftOuterJoin || op.OpType == OpType.OuterApply) && n.Child1.Op.OpType == OpType.MultiStreamNest)) {
Var sentinelVar = null;
newJoinApplyChildren.Add(AugmentNodeWithInternalConstant(chi.Child0, 1, out sentinelVar));
for (int i = 1; i < chi.Children.Count; i++) {
// Push the filter bellow all MultiStremNest-s, because this part of the tree has
// already been visited and it is expected that the MultiStreamNests have bubbled up
// above the filters.
Node newFilterChild = chi.Children[i];
Node newFilterParent = null;
while (newFilterChild.Op.OpType == OpType.MultiStreamNest) {
newFilterParent = newFilterChild;
newFilterChild = newFilterChild.Child0;
}
Node newFilterNode = CapWithIsNotNullFilter(newFilterChild, sentinelVar);
Node newNestChild; // the original child or the filter, depending on whether the filter got pushed
if (newFilterParent != null) {
newFilterParent.Child0 = newFilterNode;
newNestChild = chi.Children[i];
}
else {
newNestChild = newFilterNode;
}
newNestChildren.Add(newNestChild);
}
}
else {
newJoinApplyChildren.Add(chi.Child0);
for (int i = 1; i < chi.Children.Count; i++) {
newNestChildren.Add(chi.Children[i]);
}
}
}
else {
newJoinApplyChildren.Add(chi);
}
}
// (3) create the new Join/Apply node using the existing op and the
// new list of children from (1).
Node newJoinApplyNode = Command.CreateNode(op, newJoinApplyChildren);
// (4) insert the apply op as the driving node of the nestOp (put it
// at the beginning of the new nestOps' children.
newNestChildren.Insert(0, newJoinApplyNode);
// (5) build an updated list of output vars based upon the new join/apply
// node, and ensure all the collection vars from the nestOp(s) are
// included.
ExtendedNodeInfo xni = newJoinApplyNode.GetExtendedNodeInfo(Command);
VarVec newOutputVars = Command.CreateVarVec(xni.Definitions);
foreach (CollectionInfo ci in newCollectionInfoList) {
newOutputVars.Set(ci.CollectionVar);
}
// (6) create the new nestop
NestBaseOp newNestOp = Command.CreateMultiStreamNestOp(new List(), newOutputVars, newCollectionInfoList);
Node newNode = Command.CreateNode(newNestOp, newNestChildren);
return newNode;
}
///
/// Input => Filter(input, Ref(var) is not null)
///
///
///
///
/// ApplyOp common processing
///
///
///
///
/// DistinctOp
///
///
/// The input to a DistinctOp cannot be a NestOp – that would imply that
/// we support distinctness over collections - which we don’t.
///
///
///
///
/// FilterOp
///
///
/// If the input to the FilterOp is a NestOp, and if the filter predicate
/// does not reference any of the collection Vars of the nestOp, then the
/// FilterOp can be simply pushed below the NestOp:
///
/// Filter(Nest(X, ...), pred) => Nest(Filter(X, pred), ...)
///
/// Note: even if the filter predicate originally referenced one of the
/// collection vars, as part of our bottom up traversal, the appropriate
/// Var was replaced by a copy of the source of the collection. So, this
/// transformation should always be legal.
///
///
///
///
/// GroupByOp
///
///
/// At this point in the process, there really isn't a way we should actually
/// have a NestOp as an input to the GroupByOp, and we currently aren't allowing
/// you to specify a collection as an aggregation Var or key, so if we find a
/// NestOp anywhere on the inputs, it's a NotSupported situation.
///
///
///
///
/// JoinOp common processing
///
///
///
///
/// ProjectOp
///
///
/// There are three cases to handle in ProjectOp:
///
/// (1) The input is not a NestOp; but the ProjectOp locally defines some Vars
/// as collections:
///
/// ProjectOp(X,{a,CollectOp(PhysicalProjectOp(Y)),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),Y)
/// ProjectOp(X,{a,VarRef(ref-to-collect-var-Y),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),copy-of-Y)
///
/// Where:
/// ProjectOp' is ProjectOp less any vars that were collection vars, plus
/// any additional Vars needed by the collection.
///
/// (2) The input is a NestOp, but the ProjectOp does not local define some Vars
/// as collections:
///
/// ProjectOp(MsnOp(X,Y,...)) => MsnOp'(ProjectOp'(X),Y,...)
///
/// Where:
/// ProjectOp' is ProjectOp plus any additional Vars needed by NestOp
/// (see NestOp.Outputs – except the collection vars)
///
/// MsnOp' should be MsnOp. Additionally, its Outputs should be enhanced
/// to include any Vars produced by the ProjectOp
///
/// (3) The combination of both (1) and (2) -- both the vars define a collection,
/// and the input is also a nestOp. we handle this by first processing Case1,
/// then processing Case2.
///
///
///
///
/// Fold nested MultiStreamNestOps into one:
///
/// MSN(MSN(X,Y),Z) ==> MSN(X,Y,Z)
///
/// NOTE: It would be incorrect to merge NestOps from the non-driving node
/// into one nest op, because that would change the intent. Instead,
/// we let those go through the tree and wait until we get to the top
/// level PhysicalProject, when we'll use the ConvertToSingleStreamNest
/// process to handle them.
///
/// NOTE: We should never have three levels of nestOps, because we should
/// have folded the lower two together when we constructed one of them.
///
/// We also remove unreferenced collections, that is, if any collection is
/// not referred to by the top level-NestOp, we can safely remove it from
/// the merged NestOp we produce.
///
///
/// newNestInputs = new List();
List newCollectionInfo = new List();
VarVec newOutputVars = Command.CreateVarVec(nestOp.Outputs);
// Add the new DrivingNode;
newNestInputs.Add(nestedNestNode.Child0);
// Now add each of the nested nodes collections, but only when they're
// referenced by the top level nestOp's outputs.
for (int i = 1; i < nestedNestNode.Children.Count; i++) {
CollectionInfo ci = nestedNestOp.CollectionInfo[i - 1];
if (nestOpCollectionOutputs.IsSet(ci.CollectionVar) || newOutputVars.IsSet(ci.CollectionVar)) {
newCollectionInfo.Add(ci);
newNestInputs.Add(nestedNestNode.Children[i]);
PlanCompiler.Assert(newOutputVars.IsSet(ci.CollectionVar), "collectionVar not in output Vars?"); // I must have missed something...
}
}
// Then add in the rest of the inputs to the top level nest node (and
// they're collection Infos)
for (int i = 1; i < nestNode.Children.Count; i++) {
CollectionInfo ci = nestOp.CollectionInfo[i - 1];
newCollectionInfo.Add(ci);
newNestInputs.Add(nestNode.Children[i]);
PlanCompiler.Assert(newOutputVars.IsSet(ci.CollectionVar), "collectionVar not in output Vars?"); // I must have missed something...
}
//The prefix sort keys for the new nest op should include these of the input nestOp followed by the nestedNestOp
//(The nestOp-s that are being merged may have prefix sort keys propagated to them by constrainedSortOp-s pushed below them.
List sortKeys = ConsolidateSortKeys(nestOp.PrefixSortKeys, nestedNestOp.PrefixSortKeys);
// Make sure we pullup the sort keys in our output too...
foreach (InternalTrees.SortKey sk in sortKeys) {
newOutputVars.Set(sk.Var);
}
// Ready to go; build the new NestNode, etc.
MultiStreamNestOp newNestOp = Command.CreateMultiStreamNestOp(sortKeys, newOutputVars, newCollectionInfo);
Node newNode = Command.CreateNode(newNestOp, newNestInputs);
// Finally, recompute node info
Command.RecomputeNodeInfo(newNode);
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, newNode);
#endif //DEBUG
return newNode;
}
///
/// ProjectOp(X,{a,CollectOp(PhysicalProjectOp(Y)),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),Y)
/// ProjectOp(X,{a,VarRef(ref-to-collect-var-Y),b,...}) ==> MsnOp(ProjectOp'(X,{a,b,...}),copy-of-Y)
///
/// Remove CollectOps from projection, constructing a NestOp
/// over the ProjectOp.
///
///
/// collectionInfoList = new List();
List newChildren = new List();
List collectionNodes = new List();
VarVec externalReferences = Command.CreateVarVec();
VarVec collectionReferences = Command.CreateVarVec();
List definedVars = new List();
List referencedVars = new List();
foreach (Node chi in projectNode.Child1.Children) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Node definingExprNode = chi.Child0;
if (OpType.Collect == definingExprNode.Op.OpType) {
PlanCompiler.Assert(definingExprNode.HasChild0, "collect without input?");
PlanCompiler.Assert(OpType.PhysicalProject == definingExprNode.Child0.Op.OpType, "collect without physicalProject?");
Node physicalProjectNode = definingExprNode.Child0;
// Update collection var->defining node map;
m_definingNodeMap.Add(varDefOp.Var, physicalProjectNode);
ConvertToNestOpInput(physicalProjectNode, varDefOp.Var, collectionInfoList, collectionNodes, externalReferences, collectionReferences);
}
else if (OpType.VarRef == definingExprNode.Op.OpType) {
Var refVar = ResolveVarReference(varDefOp.Var);
Node physicalProjectNode;
if (m_definingNodeMap.TryGetValue(refVar, out physicalProjectNode)) {
physicalProjectNode = CopyCollectionVarDefinition(physicalProjectNode);
//SQLBUDT #602888: We need to track the copy too, in case we need to reuse it
m_definingNodeMap.Add(varDefOp.Var, physicalProjectNode);
ConvertToNestOpInput(physicalProjectNode, varDefOp.Var, collectionInfoList, collectionNodes, externalReferences, collectionReferences);
}
else {
referencedVars.Add(chi);
newChildren.Add(chi);
}
}
else {
definedVars.Add(chi);
newChildren.Add(chi);
}
}
// If we haven't identified a set of collection nodes, then we're done.
if (0 == collectionNodes.Count) {
return projectNode;
}
// OK, we found something. We have some heavy lifting to perform.
// Then we need to build up a MultiStreamNestOp above the ProjectOp and the
// new collection nodes to get what we really need.
// pretend that the keys included everything from the new projectOp
VarVec outputVars = Command.CreateVarVec(op.Outputs);
// First we need to modify this physicalProjectNode to leave out the collection
// Vars that we've just seen.
VarVec newProjectVars = Command.CreateVarVec(op.Outputs);
newProjectVars.Minus(collectionReferences);
// If there are any external references from any of the collections, add
// those to the projectOp explicitly. This must be ok because the projectOp
// could not have had any left-correlation
newProjectVars.Or(externalReferences);
// Create the new projectOp, and hook it into this one. The new projectOp
// no longer references the collections in it's children; of course we only
// construct a new projectOp if it actually projects out some Vars.
if (!newProjectVars.IsEmpty) {
if (IsNestOpNode(projectNode.Child0)) {
// If the input is a nest node, we need to figure out what to do with the
// rest of the in the VarDefList; we can't just pitch them, but we also
// really want to have the input be a nestop.
//
// What we do is essentially push any non-collection VarDef’s down under
// the driving node of the MSN:
//
// Project[Z,Y,W](Msn(X,Y),VarDef(Z=blah),VarDef(W=Collect(etc)) ==> MSN(MSN(Project[Z](X,VarDef(Z=blah)),Y),W)
//
// An optimization, of course being to not push anything down when there
// aren't any extra vars defined.
if (definedVars.Count == 0 && referencedVars.Count == 0) {
// We'll just pick the NestNode; we expect MergeNestedNestOps to merge
// it into what we're about to generate later.
projectNode = projectNode.Child0;
EnsureReferencedVarsAreRemoved(referencedVars, outputVars);
}
else {
NestBaseOp nestedNestOp = (NestBaseOp)projectNode.Child0.Op;
// Build the new ProjectOp to be used as input to the new nestedNestOp;
// it's input is the input to the current nestedNestOp and a new
// VarDefList with only the vars that were defined on the top level
// ProjectOp.
List newNestedProjectNodeInputs = new List();
newNestedProjectNodeInputs.Add(projectNode.Child0.Child0);
referencedVars.AddRange(definedVars);
newNestedProjectNodeInputs.Add(Command.CreateNode(Command.CreateVarDefListOp(), referencedVars));
VarVec newNestedProjectOutputs = Command.CreateVarVec(nestedNestOp.Outputs);
// SQLBUDT #508722: We need to remove the collection vars,
// these are not produced by the project
foreach (CollectionInfo ci in nestedNestOp.CollectionInfo) {
newNestedProjectOutputs.Clear(ci.CollectionVar);
}
foreach (Node varDefNode in referencedVars) {
newNestedProjectOutputs.Set(((VarDefOp)varDefNode.Op).Var);
}
Node newNestedProjectNode = Command.CreateNode(Command.CreateProjectOp(newNestedProjectOutputs), newNestedProjectNodeInputs);
// Now build the new nestedNestedNestOp, with the new nestedProjectOp
// as it's input; we have to update the outputs of the NestOp to include
// the vars we pushed down.
VarVec newNestedNestOutputs = Command.CreateVarVec(newNestedProjectOutputs);
newNestedNestOutputs.Or(nestedNestOp.Outputs);
MultiStreamNestOp newNestedNestOp = Command.CreateMultiStreamNestOp(
nestedNestOp.PrefixSortKeys,
newNestedNestOutputs,
nestedNestOp.CollectionInfo);
List newNestedNestNodeInputs = new List();
newNestedNestNodeInputs.Add(newNestedProjectNode);
for (int j = 1; j < projectNode.Child0.Children.Count; j++) {
newNestedNestNodeInputs.Add(projectNode.Child0.Children[j]);
}
projectNode = Command.CreateNode(newNestedNestOp, newNestedNestNodeInputs);
// We don't need to remove or remap referenced vars here because
// we're including them on the node we create; they won't become
// invalid.
}
}
else {
ProjectOp newProjectOp = Command.CreateProjectOp(newProjectVars);
projectNode.Child1 = Command.CreateNode(projectNode.Child1.Op, newChildren);
projectNode.Op = newProjectOp;
EnsureReferencedVarsAreRemapped(referencedVars);
}
}
else {
projectNode = projectNode.Child0;
EnsureReferencedVarsAreRemoved(referencedVars, outputVars);
}
// We need to make sure that we project out any external references to the driving
// node that the nested collections have, or we're going to end up with unresolvable
// vars when we pull them up over the current driving node. Of course, we only
// want the references that are actually ON the driving node.
externalReferences.And(projectNode.GetExtendedNodeInfo(Command).Definitions);
outputVars.Or(externalReferences);
// There are currently no prefix sortkeys. The processing for a SortOp may later
// introduce some prefix sortkeys, but there aren't any now.
MultiStreamNestOp nestOp = Command.CreateMultiStreamNestOp(new List(), outputVars, collectionInfoList);
// Insert the current node at the head of the the list of collections
collectionNodes.Insert(0, projectNode);
Node nestNode = Command.CreateNode(nestOp, collectionNodes);
// Finally, recompute node info
Command.RecomputeNodeInfo(projectNode);
Command.RecomputeNodeInfo(nestNode);
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, nestNode);
#endif //DEBUG
return nestNode;
}
///
/// If we're going to eat the ProjectNode, then we at least need to make
/// sure we remap any vars it defines as varRefs, and ensure that any
/// references to them are switched.
///
///
///
private void EnsureReferencedVarsAreRemoved(List referencedVars, VarVec outputVars) {
foreach (Node chi in referencedVars) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Var defVar = varDefOp.Var;
Var refVar = ResolveVarReference(defVar);
m_varRemapper.AddMapping(defVar, refVar);
outputVars.Clear(defVar);
outputVars.Set(refVar);
}
}
///
/// We need to make sure that we remap the column maps that we're pulling
/// up to point to the defined var, not it's reference.
///
///
private void EnsureReferencedVarsAreRemapped(List referencedVars) {
foreach (Node chi in referencedVars) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Var defVar = varDefOp.Var;
Var refVar = ResolveVarReference(defVar);
m_varRemapper.AddMapping(refVar, defVar);
}
}
///
/// Convert a CollectOp subtree (when used as the defining expression for a
/// VarDefOp) into a reasonable input to a NestOp.
///
///
/// There are a couple of cases that we handle here:
///
/// (a) PhysicalProject(X) ==> X
/// (b) PhysicalProject(Sort(X)) ==> Sort(X)
///
///
/// the child of the CollectOp
/// the collectionVar being defined
/// where to append the new collectionInfo
/// where to append the collectionNode
/// a bit vector of external references of the physicalProject
/// a bit vector of collection vars
private void ConvertToNestOpInput(Node physicalProjectNode, Var collectionVar, List collectionInfoList, List collectionNodes, VarVec externalReferences, VarVec collectionReferences) {
// Keep track of any external references the physicalProjectOp has
externalReferences.Or(Command.GetNodeInfo(physicalProjectNode).ExternalReferences);
// Case: (a) PhysicalProject(X) ==> X
Node nestOpInput = physicalProjectNode.Child0;
// Now build the collectionInfo for this input, including the flattened
// list of vars, which is essentially the outputs from the physicalProject
// with the sortKey vars that aren't already in the outputs we already
// have.
PhysicalProjectOp physicalProjectOp = (PhysicalProjectOp)physicalProjectNode.Op;
VarList flattenedElementVarList = Command.CreateVarList(physicalProjectOp.Outputs);
VarVec flattenedElementVarVec = Command.CreateVarVec(flattenedElementVarList); // Use a VarVec to make the lookups faster
List sortKeys = null;
if (OpType.Sort == nestOpInput.Op.OpType) {
// Case: (b) PhysicalProject(Sort(X)) ==> Sort(X)
SortOp sortOp = (SortOp)nestOpInput.Op;
sortKeys = OpCopier.Copy(Command , sortOp.Keys);
foreach (InternalTrees.SortKey sk in sortKeys) {
if (!flattenedElementVarVec.IsSet(sk.Var)) {
flattenedElementVarList.Add(sk.Var);
flattenedElementVarVec.Set(sk.Var);
}
}
}
else {
sortKeys = new List();
}
// Get the keys for the collection
VarVec keys = Command.CreateVarVec();
foreach (Var key in Command.GetExtendedNodeInfo(nestOpInput).Keys.KeyVars) {
if (flattenedElementVarVec.IsSet(key)) {
keys.Set(key);
}
}
// Create the collectionInfo.
CollectionInfo collectionInfo = Command.CreateCollectionInfo(collectionVar, physicalProjectOp.ColumnMap.Element, flattenedElementVarList, keys, sortKeys, null/*discriminatorValue*/);
// Now update the collections we're tracking.
collectionInfoList.Add(collectionInfo);
collectionNodes.Add(nestOpInput);
collectionReferences.Set(collectionVar);
}
///
/// Case 2 for ProjectOp: NestOp is the input:
///
/// ProjectOp(NestOp(X,Y,...)) => NestOp'(ProjectOp'(X),Y,...)
///
/// Remove collection references from the ProjectOp and pull the
/// NestOp over it, adding any outputs that the projectOp added.
///
/// The outputs are important here; expanding the above:
///
/// P{a,n}(N{x1,x2,x3,y}(X,Y)) => N{a,x1,x2,x3,y}(P{a,x1,x2,x3}(X),Y)
///
/// Strategy:
///
/// (1) Determine oldNestOpCollectionOutputs
/// (2) oldNestOpNonCollectionOutputs = oldNestOpOutputs - oldNestOpCollectionOutputs;
/// (3) oldProjectOpNonCollectionOutputs = oldProjectOpOutputs - oldNestOpCollectionOutputs
/// (4) oldProjectOpCollectionOutputs = oldProjectOpOutputs - oldProjectOpNonCollectionOutputs
/// (5) build a new list of collectionInfo's for the new NestOp, including
/// only oldProjectOpCollectionOutputs.
/// (6) leftCorrelationVars = vars that are defined by the left most child of the input nestOpNode
/// and used in the subtrees rooted at the other children of the input nestOpNode
/// (7) newProjectOpOutputs = oldProjectOpNonCollectionOutputs + oldNestOpNonCollectionOutputs + leftCorrelationVars
///
/// (8) newProjectOpChildren = ....
///
/// Of course everything needs to be "derefed", that is, expressed in the projectOp Var Ids.
///
/// (9) Set ProjectOp's input to NestOp's input
/// (10) Set NestOp's input to ProjectOp.
///
///
/// projectToNestVarMap = new Dictionary();
Command.RecomputeNodeInfo(projectNode);
ExtendedNodeInfo projectNodeInfo = Command.GetExtendedNodeInfo(projectNode);
ExtendedNodeInfo nestNodeInfo = Command.GetExtendedNodeInfo(nestNode);
foreach (Node chi in projectNode.Child1.Children) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
Node definingExprNode = chi.Child0;
if (OpType.VarRef == definingExprNode.Op.OpType) {
VarRefOp varRefOp = (VarRefOp)definingExprNode.Op;
PlanCompiler.Assert(varRefOp.Var == varDefOp.Var || !projectNodeInfo.LocalDefinitions.IsSet(varRefOp.Var), "need to remap vars!");
//if (!projectToNestVarMap.ContainsKey(varRefOp.Var)) {
// projectToNestVarMap.Add(varRefOp.Var, varDefOp.Var);
//}
}
}
#endif //DEBUG
// (1) Determine oldNestOpCollectionOutputs
VarVec oldNestOpCollectionOutputs = Command.CreateVarVec();
foreach (CollectionInfo ci in nestOp.CollectionInfo) {
oldNestOpCollectionOutputs.Set(ci.CollectionVar);
}
// (2) oldNestOpNonCollectionOutputs = oldNestOpOutputs - oldNestOpCollectionOutputs;
VarVec oldNestOpNonCollectionOutputs = Command.CreateVarVec(nestOp.Outputs);
oldNestOpNonCollectionOutputs.Minus(oldNestOpCollectionOutputs);
// (3) oldProjectOpNonCollectionOutputs = oldProjectOpOutputs - oldNestOpCollectionOutputs
VarVec oldProjectOpNonCollectionOutputs = Command.CreateVarVec(projectOp.Outputs);
oldProjectOpNonCollectionOutputs.Minus(oldNestOpCollectionOutputs);
// (4) oldProjectOpCollectionOutputs = oldProjectOpOutputs - oldProjectOpNonCollectionOutputs
VarVec oldProjectOpCollectionOutputs = Command.CreateVarVec(projectOp.Outputs);
oldProjectOpCollectionOutputs.Minus(oldProjectOpNonCollectionOutputs);
// (5) build a new list of collectionInfo's for the new NestOp, including
// only oldProjectOpCollectionOutputs.
VarVec collectionsToRemove = Command.CreateVarVec(oldNestOpCollectionOutputs);
collectionsToRemove.Minus(oldProjectOpCollectionOutputs);
List newCollectionInfoList;
List newNestNodeChildren;
if (collectionsToRemove.IsEmpty) {
newCollectionInfoList = nestOp.CollectionInfo;
newNestNodeChildren = new List(nestNode.Children);
}
else {
newCollectionInfoList = new List();
newNestNodeChildren = new List();
newNestNodeChildren.Add(nestNode.Child0);
int i = 1;
foreach (CollectionInfo ci in nestOp.CollectionInfo) {
if (!collectionsToRemove.IsSet(ci.CollectionVar)) {
newCollectionInfoList.Add(ci);
newNestNodeChildren.Add(nestNode.Children[i]);
}
i++;
}
}
// (6) leftCorrelationVars = vars that are defined by the left most child of the input nestOpNode
// and used in the subtrees rooted at the other children of the input nestOpNode
// #479547: These need to be added to the outputs of the project
VarVec leftCorrelationVars = Command.CreateVarVec();
for (int i = 1; i < nestNode.Children.Count; i++) {
leftCorrelationVars.Or(nestNode.Children[i].GetExtendedNodeInfo(Command).ExternalReferences);
}
leftCorrelationVars.And(nestNode.Child0.GetExtendedNodeInfo(this.Command).Definitions);
// (7) newProjectOpOutputs = oldProjectOpNonCollectionOutputs + oldNestOpNonCollectionOutputs + leftCorrelationVars
VarVec newProjectOpOutputs = Command.CreateVarVec(oldProjectOpNonCollectionOutputs);
newProjectOpOutputs.Or(oldNestOpNonCollectionOutputs);
newProjectOpOutputs.Or(leftCorrelationVars);
// (8) newProjectOpChildren = ....
List newProjectOpChildren = new List(projectNode.Child1.Children.Count);
foreach (Node chi in projectNode.Child1.Children) {
VarDefOp varDefOp = (VarDefOp)chi.Op;
if (newProjectOpOutputs.IsSet(varDefOp.Var)) {
newProjectOpChildren.Add(chi);
}
}
// (9) and (10), do the switch.
if (0 != newCollectionInfoList.Count) {
// In some cases, the only var in the projection is the collection var; so
// the new projectOp will have an empty projection list; we can't just pullup
// the input, so we add a temporary constant op to it, ensuring that we don't
// have an empty projection list.
if (newProjectOpOutputs.IsEmpty) {
PlanCompiler.Assert(newProjectOpChildren.Count == 0, "outputs is empty with non-zero count of children?");
NullOp tempOp = Command.CreateNullOp(Command.StringType);
Node tempNode = Command.CreateNode(tempOp);
Var tempVar;
Node varDefNode = Command.CreateVarDefNode(tempNode, out tempVar);
newProjectOpChildren.Add(varDefNode);
newProjectOpOutputs.Set(tempVar);
}
}
// Update the projectOp node with the new list of vars and
// the new list of children.
projectNode.Op = Command.CreateProjectOp(Command.CreateVarVec(newProjectOpOutputs));
projectNode.Child1 = Command.CreateNode(projectNode.Child1.Op, newProjectOpChildren);
if (0 == newCollectionInfoList.Count) {
// There are no remaining nested collections (because none of them
// were actually referenced) We just pullup the driving node of the
// nest and eliminate the nestOp entirely.
projectNode.Child0 = nestNode.Child0;
nestNode = projectNode;
}
else {
// We need to make sure that we project out any external references to the driving
// node that the nested collections have, or we're going to end up with unresolvable
// vars when we pull them up over the current driving node.
VarVec nestOpOutputs = Command.CreateVarVec(projectOp.Outputs);
for (int i = 1; i < newNestNodeChildren.Count; i++) {
nestOpOutputs.Or(newNestNodeChildren[i].GetNodeInfo(Command).ExternalReferences);
}
// We need to make sure we project out the sort keys too...
foreach (InternalTrees.SortKey sk in nestOp.PrefixSortKeys) {
nestOpOutputs.Set(sk.Var);
}
nestNode.Op = Command.CreateMultiStreamNestOp(nestOp.PrefixSortKeys, nestOpOutputs, newCollectionInfoList);
// we need to create a new node because we may have removed some of the collections.
nestNode = Command.CreateNode(nestNode.Op, newNestNodeChildren);
// Pull the nestNode up over the projectNode, and adjust
// their inputs accordingly.
projectNode.Child0 = nestNode.Child0;
nestNode.Child0 = projectNode;
Command.RecomputeNodeInfo(projectNode);
}
// Finally, recompute node info
Command.RecomputeNodeInfo(nestNode);
#if DEBUG
int size = input.Length; // GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, nestNode);
#endif //DEBUG
return nestNode;
}
///
/// SetOp common processing
///
///
/// The input to an IntersectOp or an ExceptOp cannot be a NestOp – that
/// would imply that we support distinctness over collections - which
/// we don’t.
///
/// UnionAllOp is somewhat trickier. We would need a way to percolate keys
/// up the UnionAllOp – and I’m ok with not supporting this case for now.
///
///
///
///
/// SingleRowOp
///
/// SingleRowOp(NestOp(x,...)) => NestOp(SingleRowOp(x),...)
///
///
///
///
/// SortOp
///
///
/// If the input to a SortOp is a NestOp, then none of the sort
/// keys can be collection Vars of the NestOp – we don't support
/// sorts over collections.
///
///
///
///
/// ConstrainedSortOp
///
///
/// Push the ConstrainedSortOp onto the driving node of the NestOp:
///
/// ConstrainedSortOp(NestOp(X,Y,...)) ==> NestOp(ConstrainedSortOp(X),Y,...)
///
/// There should not be any need for var renaming, because the ConstrainedSortOp cannot
/// refer to any vars from the NestOp
///
///
///
///
/// Helper method used by Visit(ConstrainedSortOp, Node)and Visit(SortOp, Node).
/// It returns a NestBaseOp equivalent to the inputNestOp, only with the given sortKeys
/// prepended to the prefix sort keys already on the inputNestOp.
///
///
///
/// sortKeys) {
NestBaseOp result;
// Include the sort keys as the prefix sort keys;
// Note that we can't actually have a SSNest at this point in
// the tree; they're only introduced once we've processed the
// entire tree.
if (inputNestOp.PrefixSortKeys.Count == 0) {
foreach (InternalTrees.SortKey sk in sortKeys) {
//SQLBUDT #507170 - We can't just add the sort keys, we need to copy them,
// to avoid changes to one to affect the other
inputNestOp.PrefixSortKeys.Add(Command.CreateSortKey(sk.Var, sk.AscendingSort, sk.Collation));
}
result = inputNestOp;
}
else {
VarVec sortVars = Command.CreateVarVec();
// First add the sort keys from the SortBaseOp, then the NestOp keys
List sortKeyList = ConsolidateSortKeys(sortKeys, inputNestOp.PrefixSortKeys);
PlanCompiler.Assert(inputNestOp is MultiStreamNestOp, "Unexpected SingleStreamNestOp?");
// Finally, build a new NestOp with the keys...
result = Command.CreateMultiStreamNestOp(sortKeyList, inputNestOp.Outputs, inputNestOp.CollectionInfo);
}
return result;
}
///
/// Helper method that given two lists of sort keys creates a single list of sort keys without duplicates.
/// First the keys from the first given list are added, then from the second one.
///
///
///
/// ConsolidateSortKeys(List sortKeyList1, List sortKeyList2) {
VarVec sortVars = Command.CreateVarVec();
List sortKeyList = new List();
foreach (InternalTrees.SortKey sk in sortKeyList1) {
if (!sortVars.IsSet(sk.Var)) {
sortVars.Set(sk.Var);
//SQLBUDT #507170 - We can't just add the sort keys, we need to copy them,
// to avoid changes to one to affect the other
sortKeyList.Add(Command.CreateSortKey(sk.Var, sk.AscendingSort, sk.Collation));
}
}
foreach (InternalTrees.SortKey sk in sortKeyList2) {
if (!sortVars.IsSet(sk.Var)){
sortVars.Set(sk.Var);
sortKeyList.Add(Command.CreateSortKey(sk.Var, sk.AscendingSort, sk.Collation));
}
}
return sortKeyList;
}
///
/// UnnestOp
///
///
/// Logically, the UnnestOp can simply be replaced with the defining expression
/// corresponding to the Var property of the UnnestOp. The tricky part is that
/// the UnnestOp produces a set of ColumnVars which may be referenced in other
/// parts of the query, and these need to be replaced by the corresponding Vars
/// produced by the defining expression.
///
/// There are essentially four cases:
///
/// Case 1: The UnnestOps Var is a UDT. Only the store can handle this, so we
/// pass it on without changing it.
///
/// Case 2: The UnnestOp has a Function as its input. This implies that the
/// store has TVFs, which it can Unnest, so we let it handle that and do
/// nothing.
///
/// Case 3: The UnnestOp Var defines a Nested collection. We'll just replace
/// the UnnestOp with the Input:
///
/// UnnestOp(VarDef(CollectOp(PhysicalProjectOp(input)))) => input
///
/// Case 4: The UnnestOp Var refers to a Nested collection from elsewhere. As we
/// discover NestOps, we maintain a var->PhysicalProject Node map. When
/// we get this case, we just make a copy of the PhysicalProject node, for
/// the referenced Var, and we replace the UnnestOp with it.
///
/// UnnestOp(VarDef(VarRef(v))) ==> copy-of-defining-node-for-v
///
/// Then, we need to update all references to the output Vars (ColumnVars) produced
/// by the Unnest to instead refer to the Vars produced by the copy of the subquery.
/// We produce a map from the Vars of the subquery to the corresponding vars of the
/// UnnestOp. We then use this map as we walk up the tree, and replace any references
/// to the Unnest Vars by the new Vars.
///
/// To simplify this process, as part of the ITreeGenerator, whenever we generate
/// an UnnestOp, we will generate a ProjectOp above it – which simply selects out
/// all Vars from the UnnestOp; and has no local definitions. This allows us to
/// restrict the Var->Var replacement to just ProjectOp.
///
///
///
/// (op.Var.Type);
if (TypeUtils.IsUdt(collType.TypeUsage)) {
return n;
}
// Find the VarDef node for the var we're supposed to unnest.
PlanCompiler.Assert(n.Child0.Op.OpType == OpType.VarDef, "Unnest without VarDef input?");
PlanCompiler.Assert(((VarDefOp)n.Child0.Op).Var == op.Var, "Unnest var not found?");
PlanCompiler.Assert(n.Child0.HasChild0, "VarDef without input?");
Node newNode = n.Child0.Child0;
if (OpType.Function == newNode.Op.OpType) {
// If we have an unnest over a function, there's nothing more we can do
// This really means that the underlying store has the ability to
// support TVFs, and therefore unnests, and we simply leave it as is
return n;
}
else if (OpType.Collect == newNode.Op.OpType) {
// UnnestOp(VarDef(CollectOp(PhysicalProjectOp(x)))) ==> x
PlanCompiler.Assert(newNode.HasChild0, "collect without input?");
newNode = newNode.Child0;
PlanCompiler.Assert(newNode.Op.OpType == OpType.PhysicalProject, "collect without physicalProject?");
// Ensure others that reference my var will know to use me;
m_definingNodeMap.Add(op.Var, newNode);
}
else if (OpType.VarRef == newNode.Op.OpType) {
// UnnestOp(VarDef(VarRef(v))) ==> copy-of-defining-node-for-v
//
// The Unnest's input is a VarRef; we need to replace it with
// the defining node, and ensure we fixup the vars.
Var refVar = ResolveVarReference(((VarRefOp)newNode.Op).Var);
Node refVarDefiningNode;
bool found = m_definingNodeMap.TryGetValue(refVar, out refVarDefiningNode);
PlanCompiler.Assert(found, "Could not find a definition for a referenced collection var");
newNode = CopyCollectionVarDefinition(refVarDefiningNode);
PlanCompiler.Assert(newNode.Op.OpType == OpType.PhysicalProject, "driving node is not physicalProject?");
}
else {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.InvalidInternalTree, 2, newNode.Op.OpType);
}
IEnumerable inputVars = ((PhysicalProjectOp)newNode.Op).Outputs;
PlanCompiler.Assert(newNode.HasChild0, "physicalProject without input?");
newNode = newNode.Child0;
// Bug 480721: a SortOp input to Unnest is irrelevant - eliminate it
if (newNode.Op.OpType == OpType.Sort) {
newNode = newNode.Child0;
}
// Update the replacement vars to reflect the pulled up operation
UpdateReplacementVarMap(op.Table.Columns, inputVars);
#if DEBUG
int size = input.Length; // GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, newNode);
#endif //DEBUG
return newNode;
}
///
/// Copies the given defining node for a collection var, but also makes sure to 'register' all newly
/// created collection vars (i.e. copied).
///
///SQLBUDT #557427: The defining node that is being copied may itself contain definitions to other
/// collection vars. These defintions would be present in m_definingNodeMap. However, after we make a copy
/// of the defining node, we need to make sure to also put 'matching' definitions of these other collection
/// vars into m_definingNodeMap.
/// The dictionary collectionVarDefinitions (below) contains the copied definitions of such collection vars.
/// but without the wrapping PhysicalProjectOp.
///
/// Example: m_definingNodeMap contains (var1, definition1) and (var2, definintion2).
/// var2 is defined inside the definition of var1.
/// Here we copy definition1 -> definintion1'.
/// We need to add to m_definitionNodeMap (var2', definition2').
/// definition2' should be a copy of definiton2 in the context of to definition1',
/// i.e. definition2' should relate to definition1' in same way that definition2 relates to definition1
/// ///
///
/// collectionVarDefinitions;
Node newNode = OpCopierTrackingCollectionVars.Copy(Command, refVarDefiningNode, out varMap, out collectionVarDefinitions);
if (collectionVarDefinitions.Count != 0) {
VarMap reverseMap = varMap.GetReverseMap();
foreach (KeyValuePair collectionVarDefinitionPair in collectionVarDefinitions) {
//
// Getting the matching definition for a collection map (i.e. definition2' from the example above)
//
// Definitions of collection vars are rooted at a PhysicalProjectOp,
// i.e. definition2 = PhysicalProjectOp(output2, columnMap2, definingSubtree2)
//
// The collectionVarDefinitions dictionary gives us the defining nodes rooted at what would a child
// of such PhysicalProjectOp, i.e. definingSubtree2'.
//
// definition2' = PhysicalProjectOp(CopyWithRemap(output2), CopyWithRemap(columnMap2), definingSubtree2')
//
Node keyDefiningNode;
Var keyDefiningVar = reverseMap[collectionVarDefinitionPair.Key];
//Note: we should not call ResolveVarReference(keyDefiningNode), we can only use the exact var
if (m_definingNodeMap.TryGetValue(keyDefiningVar, out keyDefiningNode)) {
PhysicalProjectOp originalPhysicalProjectOp = (PhysicalProjectOp)keyDefiningNode.Op;
VarList newOutputs = VarRemapper.RemapVarList(Command, varMap, originalPhysicalProjectOp.Outputs);
SimpleCollectionColumnMap newColumnMap = (SimpleCollectionColumnMap)ColumnMapCopier.Copy(originalPhysicalProjectOp.ColumnMap, varMap);
PhysicalProjectOp newPhysicalProjectOp = Command.CreatePhysicalProjectOp(newOutputs, newColumnMap);
Node newDefiningNode = Command.CreateNode(newPhysicalProjectOp, collectionVarDefinitionPair.Value);
m_definingNodeMap.Add(collectionVarDefinitionPair.Key, newDefiningNode);
}
}
}
return newNode;
}
#endregion
#region PhysicalOp Visitors
///
/// MultiStreamNestOp/SingleStreamNestOp common processing.
///
/// Pretty much just verifies that we didn't leave a NestOp behind.
///
///
///
///
/// PhysicalProjectOp
///
///
/// Tranformation:
///
/// PhysicalProjectOp(MultiStreamNestOp(...)) => PhysicalProjectOp(SortOp(...))
///
/// Strategy:
///
/// (1) Convert MultiStreamNestOp(...) => SingleStreamNestOp(...)
/// (2) Convert SingleStreamNestOp(...) => SortOp(...)
/// (3) Fixup the column maps.
///
///
///
///
/// varRefReplacementMap = new Dictionary();
VarList outputVars;
SimpleColumnMap[] keyColumnMaps;
nestNode = ConvertToSingleStreamNest(nestNode, varRefReplacementMap, out outputVars, out keyColumnMaps);
SingleStreamNestOp ssnOp = (SingleStreamNestOp)nestNode.Op;
// Build up the sort node (if necessary).
Node sortNode = BuildSortForNestElimination(ssnOp, nestNode);
// Create a new column map using the columnMapPatcher that was updated by the
// conversion to SingleStreamNest process.
SimpleCollectionColumnMap newProjectColumnMap = (SimpleCollectionColumnMap)ColumnMapTranslator.Translate(((PhysicalProjectOp)n.Op).ColumnMap, varRefReplacementMap);
newProjectColumnMap = new SimpleCollectionColumnMap(newProjectColumnMap.Type, newProjectColumnMap.Name, newProjectColumnMap.Element, keyColumnMaps, null, newProjectColumnMap.SortKeys);
// Ok, build the new PhysicalProjectOp, slap the sortNode as its input
// and we're all done.
n.Op = Command.CreatePhysicalProjectOp(outputVars, newProjectColumnMap);
n.Child0 = sortNode;
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, n);
#endif //DEBUG
return n;
}
///
/// Build up a sort node above the nestOp's input - only if there
/// are any sort keys to produce
///
///
///
/// sortKeyList = BuildSortKeyList(ssnOp);
// Now if, at this point, there aren't any sort keys then remove the
// sort operation, otherwise, build a new SortNode;
if (sortKeyList.Count > 0) {
SortOp sortOp = Command.CreateSortOp(sortKeyList);
sortNode = Command.CreateNode(sortOp, nestNode.Child0);
}
else {
// No sort keys => single_row_table => no need to sort
sortNode = nestNode.Child0;
}
return sortNode;
}
///
/// Build up the list of sortkeys. This list should comprise (in order):
///
/// - Any prefix sort keys (these represent sort operations on the
/// driving table, that were logically above the nest)
/// - The keys of the nest operation
/// - The discriminator column for the nest operation
/// - the list of postfix sort keys (used to represent nested collections)
///
/// Note that we only add the first occurrance of a var to the list; further
/// references to the same variable would be trumped by the first one.
///
///
/// BuildSortKeyList(SingleStreamNestOp ssnOp) {
VarVec sortVars = Command.CreateVarVec();
// First add the prefix sort keys
List sortKeyList = new List();
foreach (InternalTrees.SortKey sk in ssnOp.PrefixSortKeys) {
if (!sortVars.IsSet(sk.Var)) {
sortVars.Set(sk.Var);
sortKeyList.Add(sk);
}
}
// Then add the nestop keys
foreach (Var v in ssnOp.Keys) {
if (!sortVars.IsSet(v)) {
sortVars.Set(v);
InternalTrees.SortKey sk = Command.CreateSortKey(v);
sortKeyList.Add(sk);
}
}
// Then add the discriminator var
PlanCompiler.Assert(!sortVars.IsSet(ssnOp.Discriminator), "prefix sort on discriminator?");
sortKeyList.Add(Command.CreateSortKey(ssnOp.Discriminator));
// Finally, add the postfix keys
foreach (InternalTrees.SortKey sk in ssnOp.PostfixSortKeys) {
if (!sortVars.IsSet(sk.Var)) {
sortVars.Set(sk.Var);
sortKeyList.Add(sk);
}
}
return sortKeyList;
}
///
/// convert MultiStreamNestOp to SingleStreamNestOp
///
///
/// A MultiStreamNestOp is typically of the form M(D, N1, N2, ..., Nk)
/// where D is the driver stream, and N1, N2 etc. represent the collections.
///
/// In general, this can be converted into a SingleStreamNestOp over:
///
/// (D+ outerApply N1) AugmentedUnionAll (D+ outerApply N2) ...
///
/// Where:
///
/// D+ is D with an extra discriminator column that helps to identify
/// the specific collection.
///
/// AugmentedUnionAll is simply a unionAll where each branch of the
/// unionAll is augmented with nulls for the corresponding columns
/// of other tables in the branch
///
/// The simple case where there is only a single nested collection is easier
/// to address, and can be represented by:
///
/// MultiStreamNest(D, N1) => SingleStreamNest(OuterApply(D, N1))
///
/// The more complex case, where there is more than one nested column, requires
/// quite a bit more work:
///
/// MultiStreamNest(D, X, Y,...) => SingleStreamNest(UnionAll(Project{"1", D1...Dn, X1...Xn, nY1...nYn}(OuterApply(D, X)), Project{"2", D1...Dn, nX1...nXn, Y1...Yn}(OuterApply(D, Y)), ...))
///
/// Where:
/// D is the driving collection
/// D1...Dn are the columns from the driving collection
/// X is the first nested collection
/// X1...Xn are the columns from the first nested collection
/// nX1...nXn are null values for all columns from the first nested collection
/// Y is the second nested collection
/// Y1...Yn are the columns from the second nested collection
/// nY1...nYn are null values for all columns from the second nested collection
///
///
///
///
///
/// varRefReplacementMap, out VarList flattenedOutputVarList, out SimpleColumnMap[] parentKeyColumnMaps) {
#if DEBUG
string input = Dump.ToXml(Command, nestNode);
#endif //DEBUG
MultiStreamNestOp nestOp = (MultiStreamNestOp)nestNode.Op;
// We can't convert this node to a SingleStreamNest until all it's MultiStreamNest
// inputs are converted, so do that first.
for (int i = 1; i < nestNode.Children.Count; i++) {
Node chi = nestNode.Children[i];
if (chi.Op.OpType == OpType.MultiStreamNest) {
CollectionInfo chiCi = nestOp.CollectionInfo[i - 1];
VarList childFlattenedOutputVars;
SimpleColumnMap[] childKeyColumnMaps;
nestNode.Children[i] = ConvertToSingleStreamNest(chi, varRefReplacementMap, out childFlattenedOutputVars, out childKeyColumnMaps);
// Now this may seem odd here, and it may look like we should have done this
// inside the recursive ConvertToSingleStreamNest call above, but that call
// doesn't have access to the CollectionInfo for it's parent, which is what
// we need to manipulate before we enter the loop below where we try and fold
// THIS nestOp nodes into a singleStreamNestOp.
ColumnMap childColumnMap = ColumnMapTranslator.Translate(chiCi.ColumnMap, varRefReplacementMap);
VarVec childKeys = Command.CreateVarVec(((SingleStreamNestOp)nestNode.Children[i].Op).Keys);
nestOp.CollectionInfo[i - 1] = Command.CreateCollectionInfo(chiCi.CollectionVar,
childColumnMap,
childFlattenedOutputVars,
childKeys,
chiCi.SortKeys,
null /*discriminatorValue*/
);
}
}
// Make sure that the driving node has keys defined. Otherwise we're in
// trouble; we must be able to infer keys from the driving node; If it's
// available, we'll use the NewGuid canonical function to put a key on the
// driving node.
Node drivingNode = nestNode.Child0;
KeyVec drivingNodeKeys = Command.PullupKeys(drivingNode);
// Get a deterministic ordering of Vars from this node.
// NOTE: we're using the drivingNode's definitions, which is a VarVec so it
// won't match the order of the input's columns, but the key thing is
// that we use the same order for all nested children, so it's OK.
ExtendedNodeInfo drivingNodeInfo = Command.GetExtendedNodeInfo(drivingNode);
VarVec drivingNodeVarVec = drivingNodeInfo.Definitions;
VarList drivingNodeVars = Command.CreateVarList(drivingNodeVarVec);
if (drivingNodeKeys.NoKeys) {
// No Keys. We'll Transform the statement to add a NewGuid as follows:
//
// MultiStreamNest(D, X, Y,...) => MultiStreamNest(Project{NewGuid},(D), X, Y,...)
md.EdmFunction newGuidFunction;
if (!TryGetNewGuidFunction(out newGuidFunction)) {
// If we can't get the NewGuid canonical function, we'll just throw
// an exception indicating that we need keys.
throw EntityUtil.KeysRequiredForNesting();
}
// Construct the FunctionOp, the VarDef and The VarDefList to call the
// NewGuid canonical function,
Var newGuidVar;
Node newVarDefListNode = Command.CreateVarDefListNode(
Command.CreateNode(
Command.CreateFunctionOp(newGuidFunction)), out newGuidVar);
// We need to make a copy of the drivingNodeVarVec, because we don't want
// to modify the one that's in the extendedNodeInfo. Once we do, we set
// the var from the NewGuid in both it and the varlist.
drivingNodeVarVec = Command.CreateVarVec(drivingNodeVarVec);
drivingNodeVarVec.Set(newGuidVar);
drivingNodeVars.Add(newGuidVar);
// While we're at it, make sure we update the KeyVars to include the var from
// the NewGuid, effectively solveing our problem.
drivingNodeKeys = new KeyVec(Command);
drivingNodeKeys.KeyVars.Set(newGuidVar);
// OK, construct a new projectOp and node to go above the driving node, and
// hook it into the driving node of the nest op.
drivingNode = Command.CreateNode(Command.CreateProjectOp(drivingNodeVarVec), drivingNode, newVarDefListNode);
nestNode.Child0 = drivingNode;
// Finally, we have to create a new MultiStreamNestOp that includes the key
// value we just added in its outputs.
VarVec newNestopOutputs = Command.CreateVarVec(nestOp.Outputs);
newNestopOutputs.Set(newGuidVar);
nestOp = Command.CreateMultiStreamNestOp(nestOp.PrefixSortKeys, newNestopOutputs, nestOp.CollectionInfo);
nestNode.Op = nestOp;
Command.RecomputeNodeInfo(nestNode);
}
// Normalize all collection inputs to the nestOp. Specifically, remove any
// SortOps (adding the sort keys to the postfix sortkey list). Additionally,
// add a discriminatorVar to each collection child
VarList discriminatorVarList;
List> postfixSortKeyList;
NormalizeNestOpInputs(nestOp, nestNode, out discriminatorVarList, out postfixSortKeyList);
// Now build up the union-all subquery
List> varMapList;
Var outputDiscriminatorVar;
Node unionAllNode = BuildUnionAllSubqueryForNestOp(nestOp, nestNode, drivingNodeVars, discriminatorVarList, out outputDiscriminatorVar, out varMapList);
Dictionary drivingNodeVarMap = varMapList[0];
// OK. We've finally created the UnionAll over each of the project/outerApply
// combinations. We know that the output columns will be:
//
// Discriminator, DrivingColumns, Collection1Columns, Collection2Columns, ...
//
// Now, rebuild the columnMaps, since all of the columns in the original column
// maps are now referencing newer variables. To do that, we'll walk the list of
// outputs from the unionAll, and construct new VarRefColumnMaps for each one,
// and adding it to a ColumnMapPatcher, which we'll use to actually fix everything
// up.
//
// While we're at it, we'll build a new list of top-level output columns, which
// should include only the Discriminator, the columns from the driving collection,
// and and one column for each of the nested collections.
// Start building the flattenedOutputVarList that the top level PhysicalProjectOp
// is to output.
flattenedOutputVarList = Command.CreateVarList(RemapVars(drivingNodeVars, drivingNodeVarMap));
VarVec flattenedOutputVarVec = Command.CreateVarVec(flattenedOutputVarList);
VarVec nestOpOutputs = Command.CreateVarVec(flattenedOutputVarVec);
// Add any adjustments to the driving nodes vars to the column map patcher
foreach (KeyValuePair kv in drivingNodeVarMap) {
if (kv.Key != kv.Value) {
varRefReplacementMap[kv.Key] = new VarRefColumnMap(kv.Value);
}
}
RemapSortKeys(nestOp.PrefixSortKeys, drivingNodeVarMap);
List newPostfixSortKeys = new List();
List newCollectionInfoList = new List();
// Build the discriminator column map, and ensure it's in the outputs
VarRefColumnMap discriminatorColumnMap = new VarRefColumnMap(outputDiscriminatorVar);
nestOpOutputs.Set(outputDiscriminatorVar);
if (!flattenedOutputVarVec.IsSet(outputDiscriminatorVar)) {
flattenedOutputVarList.Add(outputDiscriminatorVar);
flattenedOutputVarVec.Set(outputDiscriminatorVar);
}
// Build the key column maps, and ensure they're in the outputs as well.
VarVec parentKeys = RemapVarVec(drivingNodeKeys.KeyVars, drivingNodeVarMap);
parentKeyColumnMaps = new SimpleColumnMap[parentKeys.Count];
int index = 0;
foreach (Var keyVar in parentKeys) {
parentKeyColumnMaps[index] = new VarRefColumnMap(keyVar);
index++;
if (!flattenedOutputVarVec.IsSet(keyVar)) {
flattenedOutputVarList.Add(keyVar);
flattenedOutputVarVec.Set(keyVar);
}
}
// Now that we've handled the driving node, deal with each of the
// nested inputs, in sequence.
for (int i = 1; i < nestNode.Children.Count; i++) {
CollectionInfo ci = nestOp.CollectionInfo[i - 1];
List postfixSortKeys = postfixSortKeyList[i];
RemapSortKeys(postfixSortKeys, varMapList[i]);
newPostfixSortKeys.AddRange(postfixSortKeys);
ColumnMap newColumnMap = ColumnMapTranslator.Translate(ci.ColumnMap, varMapList[i]);
VarList newFlattenedElementVars = RemapVarList(ci.FlattenedElementVars, varMapList[i]);
VarVec newCollectionKeys = RemapVarVec(ci.Keys, varMapList[i]);
RemapSortKeys(ci.SortKeys, varMapList[i]);
CollectionInfo newCollectionInfo = Command.CreateCollectionInfo(
ci.CollectionVar,
newColumnMap,
newFlattenedElementVars,
newCollectionKeys,
ci.SortKeys,
i);
newCollectionInfoList.Add(newCollectionInfo);
// For a collection Var, we add the flattened elementVars for the
// collection in place of the collection Var itself, and we create
// a new column map to represent all the stuff we've done.
foreach (Var v in newFlattenedElementVars) {
if (!flattenedOutputVarVec.IsSet(v)) {
flattenedOutputVarList.Add(v);
flattenedOutputVarVec.Set(v);
}
}
nestOpOutputs.Set(ci.CollectionVar);
int keyColumnMapIndex = 0;
SimpleColumnMap[] keyColumnMaps = new SimpleColumnMap[newCollectionInfo.Keys.Count];
foreach (Var keyVar in newCollectionInfo.Keys) {
keyColumnMaps[keyColumnMapIndex] = new VarRefColumnMap(keyVar);
keyColumnMapIndex++;
}
SortKeyInfo[] sortKeyColumnMaps = new SortKeyInfo[newCollectionInfo.SortKeys.Count];
for(int k = 0; k < sortKeyColumnMaps.Length; ++k) {
InternalTrees.SortKey sortKey = newCollectionInfo.SortKeys[k];
VarRefColumnMap varRefColumnMap = new VarRefColumnMap(sortKey.Var);
sortKeyColumnMaps[k] = new SortKeyInfo(varRefColumnMap, sortKey.AscendingSort, sortKey.Collation);
}
DiscriminatedCollectionColumnMap collectionColumnMap = new DiscriminatedCollectionColumnMap(
TypeUtils.CreateCollectionType(newCollectionInfo.ColumnMap.Type),
newCollectionInfo.ColumnMap.Name,
newCollectionInfo.ColumnMap,
keyColumnMaps,
parentKeyColumnMaps,
sortKeyColumnMaps,
discriminatorColumnMap,
newCollectionInfo.DiscriminatorValue
);
varRefReplacementMap[ci.CollectionVar] = collectionColumnMap;
}
// Finally, build up the SingleStreamNest Node
SingleStreamNestOp newSsnOp = Command.CreateSingleStreamNestOp(
parentKeys,
nestOp.PrefixSortKeys,
newPostfixSortKeys,
nestOpOutputs,
newCollectionInfoList,
outputDiscriminatorVar);
Node newNestNode = Command.CreateNode(newSsnOp, unionAllNode);
#if DEBUG
int size = input.Length;// GC.KeepAlive makes FxCop Grumpy.
string output = Dump.ToXml(Command, newNestNode);
#endif //DEBUG
return newNestNode;
}
///
/// "Normalize" each input to the NestOp.
/// We're now in the context of a MultiStreamNestOp, and we're trying to convert this
/// into a SingleStreamNestOp.
///
/// Normalization specifically refers to
/// - augmenting each input with a discriminator value (that describes the collection)
/// - removing the sort node at the root (and capturing this information as part of the sortkeys)
///
/// the nestOp
/// the nestOp subtree
/// Discriminator Vars for each Collection input
/// SortKeys (postfix) for each Collection input
///
///
private void NormalizeNestOpInputs(NestBaseOp nestOp, Node nestNode, out VarList discriminatorVarList, out List> sortKeys) {
discriminatorVarList = Command.CreateVarList();
// We insert a dummy var and value at poistion 0 for the deriving node, which
// we should never reference;
discriminatorVarList.Add(null);
sortKeys = new List>();
sortKeys.Add(nestOp.PrefixSortKeys);
for (int i = 1; i < nestNode.Children.Count; i++) {
Node inputNode = nestNode.Children[i];
// Since we're called from ConvertToSingleStreamNest, it is possible that we have a
// SingleStreamNest here, because the input to the MultiStreamNest we're converting
// may have been a MultiStreamNest that was converted to a SingleStreamNest.
SingleStreamNestOp ssnOp = inputNode.Op as SingleStreamNestOp;
// If this collection is a SingleStreamNest, we pull up the key information
// in it, and pullup the input;
if (null != ssnOp) {
// Note that the sortKeys argument is 1:1 with the nestOp inputs, that is
// each input may have exactly one entry in the list, so we have to combine
// all of the sort key components (Prefix+Keys+Discriminator+PostFix) into
// one list.
List mySortKeys = BuildSortKeyList(ssnOp);
sortKeys.Add(mySortKeys);
inputNode = inputNode.Child0;
}
else {
// If the current collection has a SortNode specified, then pull that
// out, and add the information to the list of postfix SortColumns
SortOp sortOp = inputNode.Op as SortOp;
if (null != sortOp) {
inputNode = inputNode.Child0; // bypass the sort node
// Add the sort keys to the list of postfix sort keys
sortKeys.Add(sortOp.Keys);
}
else {
// No postfix sort keys for this case
sortKeys.Add(new List());
}
}
// #447304: Ensure that any SortKey Vars will be projected from the input in addition to showing up in the postfix sort keys
// by adding them to the FlattenedElementVars for this NestOp input's CollectionInfo.
VarList flattenedElementVars = nestOp.CollectionInfo[i - 1].FlattenedElementVars;
foreach (InternalTrees.SortKey sortKey in sortKeys[i]) {
if (!flattenedElementVars.Contains(sortKey.Var)) {
flattenedElementVars.Add(sortKey.Var);
}
}
// Add a discriminator column to the collection-side - this must
// happen before the outer-apply is added on; we need to use the value of
// the discriminator to distinguish between null and empty collections
Var discriminatorVar;
Node augmentedInput = AugmentNodeWithInternalConstant(inputNode, i, out discriminatorVar);
nestNode.Children[i] = augmentedInput;
discriminatorVarList.Add(discriminatorVar);
}
}
///
/// Add an internal integer constant to a node. Specifically:
///
/// N ==> Project(N,{definitions-from-N, internalConstant})
///
/// the input node to augment
/// the value for the itnernal constant
/// the computed Var for the internal constant
/// the augmented node
private Node AugmentNodeWithInternalConstant(Node input, int internalConstantValue, out Var internalConstantVar) {
// Construct the internal constant value, a ConstantOp node, and
// a VarDef node that that defines it.
InternalConstantOp discriminatorOp = Command.CreateInternalConstantOp(Command.IntegerType, internalConstantValue);
Node discriminatorNode = Command.CreateNode(discriminatorOp);
Node varDefListNode = Command.CreateVarDefListNode(discriminatorNode, out internalConstantVar);
// Now identify the list of definitions from the input, and project out
// every one of them and include the internalConstantVar
ExtendedNodeInfo inputNodeInfo = Command.GetExtendedNodeInfo(input);
VarVec projectOutputs = Command.CreateVarVec(inputNodeInfo.Definitions);
projectOutputs.Set(internalConstantVar);
ProjectOp projectOp = Command.CreateProjectOp(projectOutputs);
Node projectNode = Command.CreateNode(projectOp, input, varDefListNode);
return projectNode;
}
///
/// Convert a SingleStreamNestOp into a massive UnionAllOp
///
///
///
///
///
///
///
///
/// > varMapList) {
Node drivingNode = nestNode.Child0;
// For each of the NESTED collections...
Node unionAllNode = null;
VarList unionAllOutputs = null;
for (int i = 1; i < nestNode.Children.Count; i++) {
// Ensure we only use the driving collection tree once, so other
// transformations do not unintentionally change more than one path.
// To prevent nodes in the tree from being used in multiple paths,
// we copy the driving input on successive nodes.
VarList newDrivingNodeVars;
Node newDrivingNode;
VarList newFlattenedElementVars;
Op op;
if (i > 1) {
newDrivingNode = OpCopier.Copy(Command, drivingNode, drivingNodeVars, out newDrivingNodeVars);
//
// Bug 450245: If we copied the driver node, then references to driver node vars
// from the collection subquery must be patched up
//
VarRemapper varRemapper = new VarRemapper(this.Command);
for (int j = 0; j < drivingNodeVars.Count; j++) {
varRemapper.AddMapping(drivingNodeVars[j], newDrivingNodeVars[j]);
}
// Remap all references in the current subquery
varRemapper.RemapSubtree(nestNode.Children[i]);
// Bug 479183: Remap the flattened element vars
newFlattenedElementVars = varRemapper.RemapVarList(nestOp.CollectionInfo[i - 1].FlattenedElementVars);
// Create a cross apply for all but the first collection
op = Command.CreateCrossApplyOp();
}
else {
newDrivingNode = drivingNode;
newDrivingNodeVars = drivingNodeVars;
newFlattenedElementVars = nestOp.CollectionInfo[i - 1].FlattenedElementVars;
// Create an outer apply for the first collection,
// that way we ensure at least one row for each row in the driver node.
op = Command.CreateOuterApplyOp();
}
// Create an outer apply with the driver node and the nested collection.
Node applyNode = Command.CreateNode(op, newDrivingNode, nestNode.Children[i]);
// Now create a ProjectOp that augments the output from the OuterApplyOp
// with nulls for each column from other collections
// Build the VarDefList (the list of vars) for the Project, starting
// with the collection discriminator var
List varDefListChildren = new List();
VarList projectOutputs = Command.CreateVarList();
// Add the collection discriminator var to the output.
projectOutputs.Add(discriminatorVarList[i]);
// Add all columns from the driving node
projectOutputs.AddRange(newDrivingNodeVars);
// Add all the vars from all the nested collections;
for (int j = 1; j < nestNode.Children.Count; j++) {
CollectionInfo otherCollectionInfo = nestOp.CollectionInfo[j - 1];
// For the current nested collection, we just pick the var that's
// coming from there and don't need have a new var defined, but for
// the rest we construct null values.
if (i == j) {
projectOutputs.AddRange(newFlattenedElementVars);
}
else {
foreach (Var v in otherCollectionInfo.FlattenedElementVars) {
NullOp nullOp = Command.CreateNullOp(v.Type);
Node nullOpNode = Command.CreateNode(nullOp);
Var nullOpVar;
Node nullOpVarDefNode = Command.CreateVarDefNode(nullOpNode, out nullOpVar);
varDefListChildren.Add(nullOpVarDefNode);
projectOutputs.Add(nullOpVar);
}
}
}
Node varDefListNode = Command.CreateNode(Command.CreateVarDefListOp(), varDefListChildren);
// Now, build up the projectOp
VarVec projectOutputsVarSet = Command.CreateVarVec(projectOutputs);
ProjectOp projectOp = Command.CreateProjectOp(projectOutputsVarSet);
Node projectNode = Command.CreateNode(projectOp, applyNode, varDefListNode);
// finally, build the union all
if (unionAllNode == null) {
unionAllNode = projectNode;
unionAllOutputs = projectOutputs;
}
else {
VarMap unionAllMap = new VarMap();
VarMap projectMap = new VarMap();
for (int idx = 0; idx < unionAllOutputs.Count; idx++) {
Var outputVar = Command.CreateSetOpVar(unionAllOutputs[idx].Type);
unionAllMap.Add(outputVar, unionAllOutputs[idx]);
projectMap.Add(outputVar, projectOutputs[idx]);
}
UnionAllOp unionAllOp = Command.CreateUnionAllOp(unionAllMap, projectMap);
unionAllNode = Command.CreateNode(unionAllOp, unionAllNode, projectNode);
// Get the output vars from the union-op. This must be in the same order
// as the original list of Vars
unionAllOutputs = GetUnionOutputs(unionAllOp, unionAllOutputs);
}
}
// We're done building the node, but now we have to build a mapping from
// the before-Vars to the after-Vars
varMapList = new List>();
IEnumerator outputVarsEnumerator = unionAllOutputs.GetEnumerator();
if (!outputVarsEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 4); // more columns from children than are on the unionAll?
}
// The discriminator var is always first
discriminatorVar = outputVarsEnumerator.Current;
// Build a map for each input
for (int i = 0; i < nestNode.Children.Count; i++) {
Dictionary varMap = new Dictionary();
VarList varList = (i == 0) ? drivingNodeVars : nestOp.CollectionInfo[i - 1].FlattenedElementVars;
foreach (Var v in varList) {
if (!outputVarsEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 5); // more columns from children than are on the unionAll?
}
varMap[v] = outputVarsEnumerator.Current;
}
varMapList.Add(varMap);
}
if (outputVarsEnumerator.MoveNext()) {
throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.ColumnCountMismatch, 6); // at this point, we better be done with both lists...
}
return unionAllNode;
}
///
/// Get back an ordered list of outputs from a union-all op. The ordering should
/// be identical to the ordered list "leftVars" which describes the left input of
/// the unionAllOp
///
/// the unionall Op
/// vars of the left input
/// output vars ordered in the same way as the left input
private static VarList GetUnionOutputs(UnionAllOp unionOp, VarList leftVars) {
VarMap varMap = unionOp.VarMap[0];
Dictionary reverseVarMap = varMap.GetReverseMap();
VarList unionAllVars = Command.CreateVarList();
foreach (Var v in leftVars) {
Var newVar = reverseVarMap[v];
unionAllVars.Add(newVar);
}
return unionAllVars;
}
///
/// Tries to get NewGuid canonical function.
///
/// out EdmFunction for NewGuid canonical function
/// true if a unique Edm.NewGuid canonical function was found, false otherwise
private bool TryGetNewGuidFunction(out md.EdmFunction newGuidFunction) {
newGuidFunction = null;
System.Collections.ObjectModel.ReadOnlyCollection functions = m_compilerState.MetadataWorkspace.GetFunctions("NewGuid", "Edm", System.Data.Metadata.Edm.DataSpace.CSpace);
if (null != functions && 1 == functions.Count) {
newGuidFunction = functions[0];
}
return (null != newGuidFunction);
}
#endregion
#endregion
}
#region Class OpCopierTrackingCollectionVars
///
/// Wrapper around OpCopier to keep track of the defining subtrees
/// of collection vars defined in the subtree being returned as a copy.
///
internal class OpCopierTrackingCollectionVars : OpCopier {
#region Private State
private Dictionary m_newCollectionVarDefinitions = new Dictionary();
#endregion
#region Private Constructor
private OpCopierTrackingCollectionVars(Command cmd) : base(cmd) {
}
#endregion
#region Public Surface
///
/// Equivalent to OpCopier.Copy, only in addition it keeps track of the defining subtrees
/// of collection vars defined in the subtree rooted at the copy of the input node n.
///
///
///
///
///
/// newCollectionVarDefinitions) {
OpCopierTrackingCollectionVars oc = new OpCopierTrackingCollectionVars(cmd);
Node newNode = oc.CopyNode(n);
varMap = oc.m_varMap;
newCollectionVarDefinitions = oc.m_newCollectionVarDefinitions;
return newNode;
}
#endregion
#region Visitor Members
///
/// Tracks the collection vars after calling the base implementation
///
///
///
///
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- SchemaTypeEmitter.cs
- CompensationDesigner.cs
- InfoCardRSAOAEPKeyExchangeDeformatter.cs
- IPCCacheManager.cs
- DecoderFallback.cs
- AutoResetEvent.cs
- EnumBuilder.cs
- DBSqlParserColumn.cs
- InplaceBitmapMetadataWriter.cs
- TypeDependencyAttribute.cs
- ToolTipAutomationPeer.cs
- DependencyPropertyConverter.cs
- Material.cs
- ButtonBase.cs
- DataGridViewRowHeightInfoNeededEventArgs.cs
- HostingEnvironment.cs
- InsufficientMemoryException.cs
- DataAdapter.cs
- Frame.cs
- WebResponse.cs
- PerformanceCounterPermission.cs
- AgileSafeNativeMemoryHandle.cs
- Composition.cs
- UIElement3D.cs
- SafeEventLogWriteHandle.cs
- SmiRequestExecutor.cs
- UIElementParaClient.cs
- TemplateBamlRecordReader.cs
- MatrixAnimationUsingPath.cs
- Html32TextWriter.cs
- SystemIPGlobalProperties.cs
- XmlSerializableReader.cs
- CSharpCodeProvider.cs
- EraserBehavior.cs
- NotifyParentPropertyAttribute.cs
- odbcmetadatafactory.cs
- TextServicesManager.cs
- OneOfScalarConst.cs
- DataGridViewSelectedCellsAccessibleObject.cs
- WhitespaceRuleLookup.cs
- ControlBindingsCollection.cs
- ListBase.cs
- SafeFileMapViewHandle.cs
- WorkflowApplicationException.cs
- CssTextWriter.cs
- HandleCollector.cs
- RegistryKey.cs
- BufferBuilder.cs
- ExpandedWrapper.cs
- InheritanceRules.cs
- ShapingWorkspace.cs
- HostingEnvironmentSection.cs
- TemplatePropertyEntry.cs
- RootBuilder.cs
- OrderedHashRepartitionStream.cs
- ReflectTypeDescriptionProvider.cs
- Stack.cs
- RemotingServices.cs
- DynamicDiscoveryDocument.cs
- SettingsPropertyWrongTypeException.cs
- UnitySerializationHolder.cs
- SqlParameter.cs
- AppSettingsExpressionEditor.cs
- LogicalExpr.cs
- CacheSection.cs
- ViewSimplifier.cs
- PrivilegedConfigurationManager.cs
- MultiView.cs
- TableLayoutColumnStyleCollection.cs
- TextTreeRootTextBlock.cs
- ExtenderControl.cs
- FileDialogCustomPlacesCollection.cs
- SqlConnectionStringBuilder.cs
- DefaultWorkflowSchedulerService.cs
- CollectionBuilder.cs
- OutputCacheModule.cs
- DbInsertCommandTree.cs
- DynamicAttribute.cs
- WriteableBitmap.cs
- ExpressionNormalizer.cs
- WebPartZoneBase.cs
- CodeArrayCreateExpression.cs
- GuidConverter.cs
- Bitmap.cs
- ModelTypeConverter.cs
- _AuthenticationState.cs
- FormatterServicesNoSerializableCheck.cs
- IndexingContentUnit.cs
- StoryFragments.cs
- httpserverutility.cs
- OrCondition.cs
- Rect3DValueSerializer.cs
- IndexedString.cs
- EdmRelationshipRoleAttribute.cs
- ResourceType.cs
- DateTimeEditor.cs
- SignatureToken.cs
- WebPartEditorOkVerb.cs
- SBCSCodePageEncoding.cs
- EventLogPermission.cs