1 //---------------------------------------------------------------------
2 // <copyright file="SubqueryTrackingVisitor.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
7 // @backupOwner Microsoft
8 //---------------------------------------------------------------------
11 using System
.Collections
.Generic
;
12 using System
.Data
.Query
.InternalTrees
;
13 //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
15 // It is fine to use Debug.Assert in cases where you assert an obvious thing that is supposed
16 // to prevent from simple mistakes during development (e.g. method argument validation
17 // in cases where it was you who created the variables or the variables had already been validated or
18 // in "else" clauses where due to code changes (e.g. adding a new value to an enum type) the default
19 // "else" block is chosen why the new condition should be treated separately). This kind of asserts are
20 // (can be) helpful when developing new code to avoid simple mistakes but have no or little value in
21 // the shipped product.
22 // PlanCompiler.Assert *MUST* be used to verify conditions in the trees. These would be assumptions
23 // about how the tree was built etc. - in these cases we probably want to throw an exception (this is
24 // what PlanCompiler.Assert does when the condition is not met) if either the assumption is not correct
25 // or the tree was built/rewritten not the way we thought it was.
26 // Use your judgment - if you rather remove an assert than ship it use Debug.Assert otherwise use
27 // PlanCompiler.Assert.
29 namespace System
.Data
.Query
.PlanCompiler
32 /// The SubqueryTracking Visitor serves as a base class for the visitors that may turn
33 /// scalar subqueryies into outer-apply subqueries.
35 internal abstract class SubqueryTrackingVisitor
: BasicOpVisitorOfNode
38 protected readonly PlanCompiler m_compilerState
;
39 protected Command m_command { get { return m_compilerState.Command; }
}
41 // nested subquery tracking
42 protected readonly Stack
<Node
> m_ancestors
= new Stack
<Node
>();
43 private readonly Dictionary
<Node
, List
<Node
>> m_nodeSubqueries
= new Dictionary
<Node
, List
<Node
>>();
47 protected SubqueryTrackingVisitor(PlanCompiler planCompilerState
)
49 this.m_compilerState
= planCompilerState
;
53 #region Subquery Handling
55 /// Adds a subquery to the list of subqueries for the relOpNode
57 /// <param name="relOpNode">the RelOp node</param>
58 /// <param name="subquery">the subquery</param>
59 protected void AddSubqueryToRelOpNode(Node relOpNode
, Node subquery
)
61 List
<Node
> nestedSubqueries
;
63 // Create an entry in the map if there isn't one already
64 if (!m_nodeSubqueries
.TryGetValue(relOpNode
, out nestedSubqueries
))
66 nestedSubqueries
= new List
<Node
>();
67 m_nodeSubqueries
[relOpNode
] = nestedSubqueries
;
69 // add this subquery to the list of currently tracked subqueries
70 nestedSubqueries
.Add(subquery
);
74 /// Add a subquery to the "parent" relop node
76 /// <param name="outputVar">the output var to be used - at the current location - in lieu of the subquery</param>
77 /// <param name="subquery">the subquery to move</param>
78 /// <returns>a var ref node for the var returned from the subquery</returns>
79 protected Node
AddSubqueryToParentRelOp(Var outputVar
, Node subquery
)
81 Node ancestor
= FindRelOpAncestor();
82 PlanCompiler
.Assert(ancestor
!= null, "no ancestors found?");
83 AddSubqueryToRelOpNode(ancestor
, subquery
);
85 subquery
= m_command
.CreateNode(m_command
.CreateVarRefOp(outputVar
));
90 /// Find the first RelOp node that is in my ancestral path.
91 /// If I see a PhysicalOp, then I don't have a RelOp parent
93 /// <returns>the first RelOp node</returns>
94 protected Node
FindRelOpAncestor()
96 foreach (Node n
in m_ancestors
)
102 else if (n
.Op
.IsPhysicalOp
)
111 #region Visitor Helpers
114 /// Extends the base class implementation of VisitChildren.
115 /// Wraps the call to visitchildren() by first adding the current node
116 /// to the stack of "ancestors", and then popping back the node at the end
118 /// <param name="n">Current node</param>
119 protected override void VisitChildren(Node n
)
121 // Push the current node onto the stack
124 for (int i
= 0; i
< n
.Children
.Count
; i
++)
126 n
.Children
[i
] = VisitNode(n
.Children
[i
]);
134 #region Visitor Methods
139 /// Augments a node with a number of OuterApply's - one for each subquery
140 /// If S1, S2, ... are the list of subqueries for the node, and D is the
141 /// original (driver) input, we convert D into
142 /// OuterApply(OuterApply(D, S1), S2), ...
144 /// <param name="input">the input (driver) node</param>
145 /// <param name="subqueries">List of subqueries</param>
146 /// <param name="inputFirst">should the input node be first in the apply chain, or the last?</param>
147 /// <returns>The resulting node tree</returns>
148 private Node
AugmentWithSubqueries(Node input
, List
<Node
> subqueries
, bool inputFirst
)
151 int subqueriesStartPos
;
156 subqueriesStartPos
= 0;
160 newNode
= subqueries
[0];
161 subqueriesStartPos
= 1;
163 for (int i
= subqueriesStartPos
; i
< subqueries
.Count
; i
++)
165 OuterApplyOp op
= m_command
.CreateOuterApplyOp();
166 newNode
= m_command
.CreateNode(op
, newNode
, subqueries
[i
]);
170 // The driver node uses a cross apply to ensure that no results are produced
171 // for an empty driver.
172 newNode
= m_command
.CreateNode(m_command
.CreateCrossApplyOp(), newNode
, input
);
175 // We may need to perform join elimination
176 m_compilerState
.MarkPhaseAsNeeded(PlanCompilerPhase
.JoinElimination
);
181 /// Default processing for RelOps.
182 /// - First, we mark the current node as its own ancestor (so that any
183 /// subqueries that we detect internally will be added to this node's list)
184 /// - then, visit each child
185 /// - finally, accumulate all nested subqueries.
186 /// - if the current RelOp has only one input, then add the nested subqueries via
187 /// Outer apply nodes to this input.
189 /// The interesting RelOps are
190 /// Project, Filter, GroupBy, Sort,
191 /// Should we break this out into separate functions instead?
193 /// <param name="op">Current RelOp</param>
194 /// <param name="n">Node to process</param>
195 /// <returns>Current subtree</returns>
196 protected override Node
VisitRelOpDefault(RelOp op
, Node n
)
198 VisitChildren(n
); // visit all my children first
200 // Then identify all the subqueries that have shown up as part of my node
201 // Create Apply Nodes for each of these.
202 List
<Node
> nestedSubqueries
;
203 if (m_nodeSubqueries
.TryGetValue(n
, out nestedSubqueries
) && nestedSubqueries
.Count
> 0)
205 // Validate - this must only apply to the following nodes
207 n
.Op
.OpType
== OpType
.Project
|| n
.Op
.OpType
== OpType
.Filter
||
208 n
.Op
.OpType
== OpType
.GroupBy
|| n
.Op
.OpType
== OpType
.GroupByInto
,
209 "VisitRelOpDefault: Unexpected op?" + n
.Op
.OpType
);
211 Node newInputNode
= AugmentWithSubqueries(n
.Child0
, nestedSubqueries
, true);
212 // Now make this the new input child
213 n
.Child0
= newInputNode
;
220 /// Processing for all JoinOps
222 /// <param name="op">JoinOp</param>
223 /// <param name="n">Current subtree</param>
224 /// <returns>Whether the node was modified</returns>
225 protected bool ProcessJoinOp(JoinBaseOp op
, Node n
)
227 VisitChildren(n
); // visit all my children first
229 // then check to see if we have any nested subqueries. This can only
230 // occur in the join condition.
231 // What we'll do in this case is to convert the join condition - "p" into
232 // p -> Exists(Filter(SingleRowTableOp, p))
233 // We will then move the subqueries into an outerApply on the SingleRowTable
234 List
<Node
> nestedSubqueries
;
235 if (!m_nodeSubqueries
.TryGetValue(n
, out nestedSubqueries
))
240 PlanCompiler
.Assert(n
.Op
.OpType
== OpType
.InnerJoin
||
241 n
.Op
.OpType
== OpType
.LeftOuterJoin
||
242 n
.Op
.OpType
== OpType
.FullOuterJoin
, "unexpected op?");
243 PlanCompiler
.Assert(n
.HasChild2
, "missing second child to JoinOp?");
244 Node joinCondition
= n
.Child2
;
246 Node inputNode
= m_command
.CreateNode(m_command
.CreateSingleRowTableOp());
247 inputNode
= AugmentWithSubqueries(inputNode
, nestedSubqueries
, true);
248 Node filterNode
= m_command
.CreateNode(m_command
.CreateFilterOp(), inputNode
, joinCondition
);
249 Node existsNode
= m_command
.CreateNode(m_command
.CreateExistsOp(), filterNode
);
251 n
.Child2
= existsNode
;
256 /// Visitor for UnnestOp. If the child has any subqueries, we need to convert this
258 /// OuterApply(S, Unnest)
259 /// unlike the other cases where the OuterApply will appear as the input of the node
261 /// <param name="op">the unnestOp</param>
262 /// <param name="n">current subtree</param>
263 /// <returns>modified subtree</returns>
264 public override Node
Visit(UnnestOp op
, Node n
)
266 VisitChildren(n
); // visit all my children first
268 List
<Node
> nestedSubqueries
;
269 if (m_nodeSubqueries
.TryGetValue(n
, out nestedSubqueries
))
271 // We pass 'inputFirst = false' since the subqueries contribute to the driver in the unnest,
272 // they are not generated by the unnest.
273 Node newNode
= AugmentWithSubqueries(n
, nestedSubqueries
, false /* inputFirst */);