1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
//---------------------------------------------------------------------
// <copyright file="VarRefManager.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Diagnostics;
using System.Data.Query.InternalTrees;
namespace System.Data.Query.PlanCompiler
{
/// <summary>
/// This is a halper module for <see cref="JoinElimination"/>
/// The VarRefManager keeps track of the child-parent relationships in order to be able
/// to decide whether a given var is referenced by children on right-side relatives of a given node.
/// It is used in JoinElimination when deciding whether it is possible to eliminate the child table participating
/// in a left-outer join when there is a 1 - 0..1 FK relationship.
/// </summary>
internal class VarRefManager
{
#region Internal State
private Dictionary<Node, Node> m_nodeToParentMap; //child-parent mapping
private Dictionary<Node, int> m_nodeToSiblingNumber; //the index of the given node among its siblings, i.e. 0 for a first child
Command m_command;
#endregion
#region Constructor
/// <summary>
/// Constructs a new VarRefManager given a command.
/// </summary>
/// <param name="command"></param>
internal VarRefManager(Command command)
{
m_nodeToParentMap = new Dictionary<Node, Node>();
m_nodeToSiblingNumber = new Dictionary<Node, int>();
m_command = command;
}
#endregion
#region Public Methods
/// <summary>
/// Tracks the information that the given node is a parent of its children (one level only)
/// </summary>
/// <param name="parent"></param>
internal void AddChildren(Node parent)
{
for(int i=0; i< parent.Children.Count; i++)
{
//We do not use add on purpose, we may be updating a child's parent after join elimination in a subtree
m_nodeToParentMap[parent.Children[i]] = parent;
m_nodeToSiblingNumber[parent.Children[i]] = i;
}
}
/// <summary>
/// Determines whether any var from a given list of keys is referenced by any of defining node's right relatives,
/// with the exception of the relatives brunching at the given targetJoinNode.
/// </summary>
/// <param name="keys">A list of vars to check for</param>
/// <param name="definingNode">The node considered to be the defining node</param>
/// <param name="targetJoinNode">The relatives branching at this node are skipped</param>
/// <returns>False, only it can determine that not a single var from a given list of keys is referenced by any
/// of defining node's right relatives, with the exception of the relatives brunching at the given targetJoinNode. </returns>
internal bool HasKeyReferences(VarVec keys, Node definingNode, Node targetJoinNode)
{
Node currentChild = definingNode;
Node parent;
bool continueUp = true;
while (continueUp & m_nodeToParentMap.TryGetValue(currentChild, out parent))
{
if (parent != targetJoinNode)
{
// Check the parent
if (HasVarReferencesShallow(parent, keys, m_nodeToSiblingNumber[currentChild], out continueUp))
{
return true;
}
//Check all the siblings to the right
for (int i = m_nodeToSiblingNumber[currentChild] + 1; i < parent.Children.Count; i++)
{
if (parent.Children[i].GetNodeInfo(m_command).ExternalReferences.Overlaps(keys))
{
return true;
}
}
}
currentChild = parent;
}
return false;
}
#endregion
#region Private Methods
/// <summary>
/// Checks whether the given node has references to any of the vars in the given VarVec.
/// It only checks the given node, not its children.
/// </summary>
/// <param name="node">The node to check</param>
/// <param name="vars">The list of vars to check for</param>
/// <param name="childIndex">The index of the node's subree from which this var is coming.
/// This is used for SetOp-s, to be able to locate the appropriate var map that will give the
/// vars corresponding to the given once</param>
/// <param name="continueUp">If the OpType of the node's Op is such that it 'hides' the input, i.e.
/// the decision of whether the given vars are referenced can be made on this level, it returns true,
/// false otherwise</param>
/// <returns>True if the given node has references to any of the vars in the given VarVec, false otherwise</returns>
private static bool HasVarReferencesShallow(Node node, VarVec vars, int childIndex, out bool continueUp)
{
switch (node.Op.OpType)
{
case OpType.ConstrainedSort:
case OpType.Sort:
continueUp = true;
return HasVarReferences(((SortBaseOp)node.Op).Keys, vars);
case OpType.Distinct:
continueUp = false;
return HasVarReferences(((DistinctOp)node.Op).Keys, vars);
case OpType.Except:
case OpType.Intersect:
case OpType.UnionAll:
continueUp = false;
return HasVarReferences((SetOp)node.Op, vars, childIndex);
case OpType.GroupBy:
continueUp = false;
return HasVarReferences(((GroupByOp)node.Op).Keys, vars);
case OpType.PhysicalProject:
continueUp = false;
return HasVarReferences(((PhysicalProjectOp)node.Op).Outputs, vars);
case OpType.Project:
continueUp = false;
return HasVarReferences(((ProjectOp)node.Op).Outputs, vars);
default:
continueUp = true;
return false;
}
}
/// <summary>
/// Does the gvien VarList overlap with the given VarVec
/// </summary>
/// <param name="listToCheck"></param>
/// <param name="vars"></param>
/// <returns></returns>
private static bool HasVarReferences(VarList listToCheck, VarVec vars)
{
foreach (Var var in vars)
{
if (listToCheck.Contains(var))
{
return true;
}
}
return false;
}
/// <summary>
/// Do the two given varVecs overlap
/// </summary>
/// <param name="listToCheck"></param>
/// <param name="vars"></param>
/// <returns></returns>
private static bool HasVarReferences(VarVec listToCheck, VarVec vars)
{
return listToCheck.Overlaps(vars);
}
/// <summary>
/// Does the given list of sort keys contain a key with a var that is the given VarVec
/// </summary>
/// <param name="listToCheck"></param>
/// <param name="vars"></param>
/// <returns></returns>
private static bool HasVarReferences(List<InternalTrees.SortKey> listToCheck, VarVec vars)
{
foreach (InternalTrees.SortKey key in listToCheck)
{
if (vars.IsSet(key.Var))
{
return true;
}
}
return false;
}
/// <summary>
/// Does the list of outputs of the given SetOp contain a var
/// from the given VarVec defined by the SetOp's child with the given index
/// </summary>
/// <param name="op"></param>
/// <param name="vars"></param>
/// <param name="index"></param>
/// <returns></returns>
private static bool HasVarReferences(SetOp op, VarVec vars, int index)
{
foreach (Var var in op.VarMap[index].Values)
{
if (vars.IsSet(var))
{
return true;
}
}
return false;
}
#endregion
}
}
|
