forked from dolthub/go-mysql-server
-
Notifications
You must be signed in to change notification settings - Fork 0
/
symbol_resolution.go
304 lines (278 loc) · 9.18 KB
/
symbol_resolution.go
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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
// Copyright 2020-2021 Dolthub, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package analyzer
import (
"strings"
"github.com/gabereiser/go-mysql-server/sql"
"github.com/gabereiser/go-mysql-server/sql/expression"
"github.com/gabereiser/go-mysql-server/sql/plan"
"github.com/gabereiser/go-mysql-server/sql/transform"
)
// pruneTables removes unneeded columns from *plan.ResolvedTable nodes
//
// A preOrder walk constructs a new tree top-down. For every non-base
// case node encountered:
// 1. Collect outer tableCol dependencies for the node
// 2. Apply the node's dependencies to |parentCols|, |parentStars|,
// and |unqualifiedStar|.
// 3. Process the node's children with the new dependencies.
// 4. Rewind the dependencies, resetting |parentCols|, |parentStars|,
// and |unqualifiedStar| to values when we entered this node.
// 5. Return the node with its children to the parent.
//
// The base case prunes a *plan.ResolvedTable of parent dependencies.
//
// The dependencies considered are:
// - outerCols: columns used by filters or other expressions
// sourced from outside the node
// - aliasCols: a bridge between outside columns and an aliased
// data source.
// - subqueryCols: correlated subqueries have outside cols not
// satisfied by tablescans in the subquery
// - stars: a tablescan with a qualified star or cannot be pruned. An
// unqualified star prevents pruning every child tablescan.
func pruneTables(ctx *sql.Context, a *Analyzer, n sql.Node, s *Scope, sel RuleSelector) (sql.Node, transform.TreeIdentity, error) {
// the same table can appear in multiple table scans,
// so we use a counter to pin references
parentCols := make(map[tableCol]int)
parentStars := make(map[string]struct{})
var unqualifiedStar bool
push := func(cols []tableCol, nodeStars []string, nodeUnq bool) {
for _, c := range cols {
parentCols[c]++
}
for _, c := range nodeStars {
parentStars[c] = struct{}{}
}
unqualifiedStar = unqualifiedStar || nodeUnq
}
pop := func(cols []tableCol, nodeStars []string, beforeUnq bool) {
for _, c := range cols {
parentCols[c]--
}
for _, c := range nodeStars {
delete(parentStars, c)
}
unqualifiedStar = beforeUnq
}
var pruneWalk func(n sql.Node) (sql.Node, transform.TreeIdentity, error)
pruneWalk = func(n sql.Node) (sql.Node, transform.TreeIdentity, error) {
switch n := n.(type) {
case *plan.ResolvedTable:
return pruneTableCols(n, parentCols, parentStars, unqualifiedStar)
case *plan.JoinNode:
if n.JoinType().IsPhysical() || n.JoinType().IsNatural() {
return n, transform.SameTree, nil
}
if _, ok := n.Right().(*plan.JSONTable); ok {
outerCols, outerStars, outerUnq := gatherOuterCols(n.Right())
aliasCols, aliasStars := gatherTableAlias(n.Right(), parentCols, parentStars, unqualifiedStar)
push(outerCols, outerStars, outerUnq)
push(aliasCols, aliasStars, false)
}
case *plan.Filter, *plan.GroupBy, *plan.Project, *plan.TableAlias,
*plan.Window, *plan.Sort, *plan.Limit, *plan.RecursiveCte,
*plan.RecursiveTable, *plan.TopN, *plan.Offset, *plan.SelectSingleRel:
default:
return n, transform.SameTree, nil
}
if sq := findSubqueryExpr(n); sq != nil {
return n, transform.SameTree, nil
}
beforeUnq := unqualifiedStar
//todo(max): outer and alias cols can have duplicates, as long as the pop
// is equal and opposite we are usually fine. In the cases we aren't, we
// already do not handle nested aliasing well.
outerCols, outerStars, outerUnq := gatherOuterCols(n)
aliasCols, aliasStars := gatherTableAlias(n, parentCols, parentStars, unqualifiedStar)
push(outerCols, outerStars, outerUnq)
push(aliasCols, aliasStars, false)
children := n.Children()
var newChildren []sql.Node
for i, c := range children {
child, same, _ := pruneWalk(c)
if !same {
if newChildren == nil {
newChildren = make([]sql.Node, len(children))
copy(newChildren, children)
}
newChildren[i] = child
}
}
pop(outerCols, outerStars, beforeUnq)
pop(aliasCols, aliasStars, beforeUnq)
if len(newChildren) == 0 {
return n, transform.SameTree, nil
}
ret, _ := n.WithChildren(newChildren...)
return ret, transform.NewTree, nil
}
return pruneWalk(n)
}
// findSubqueryExpr searches for a *plan.Subquery in a single node,
// returning the subquery or nil
func findSubqueryExpr(n sql.Node) *plan.Subquery {
var sq *plan.Subquery
ne, ok := n.(sql.Expressioner)
if !ok {
return nil
}
for _, e := range ne.Expressions() {
found := transform.InspectExpr(e, func(e sql.Expression) bool {
if e, ok := e.(*plan.Subquery); ok {
sq = e
return true
}
return false
})
if found {
return sq
}
}
return nil
}
// pruneTableCols uses a list of parent dependencies columns and stars
// to prune and return a new table node. We prune a column if no
// parent references the column, no parent projections this table as a
// qualified star, and no parent projects an unqualified star.
func pruneTableCols(
n *plan.ResolvedTable,
parentCols map[tableCol]int,
parentStars map[string]struct{},
unqualifiedStar bool,
) (sql.Node, transform.TreeIdentity, error) {
table := getTable(n)
t, ok := table.(sql.ProjectedTable)
if !ok || t.Name() == plan.DualTableName {
return n, transform.SameTree, nil
}
_, selectStar := parentStars[t.Name()]
if unqualifiedStar {
selectStar = true
}
tab := getTable(n)
ptab, ok := tab.(sql.ProjectedTable)
if !ok {
return n, transform.SameTree, nil
}
if len(ptab.Projections()) > 0 {
return n, transform.SameTree, nil
}
cols := make([]string, 0)
source := strings.ToLower(t.Name())
for _, col := range t.Schema() {
c := tableCol{table: strings.ToLower(source), col: strings.ToLower(col.Name)}
if selectStar || parentCols[c] > 0 {
cols = append(cols, c.col)
}
}
ret, err := n.WithTable(ptab.WithProjections(cols))
if err != nil {
return n, transform.SameTree, nil
}
return ret, transform.NewTree, nil
}
// gatherOuterCols searches a node's expressions for column
// references and stars.
func gatherOuterCols(n sql.Node) ([]tableCol, []string, bool) {
ne, ok := n.(sql.Expressioner)
if !ok {
return nil, nil, false
}
var cols []tableCol
var nodeStars []string
var nodeUnqualifiedStar bool
for _, e := range ne.Expressions() {
transform.InspectExpr(e, func(e sql.Expression) bool {
var col tableCol
switch e := e.(type) {
case *expression.Alias:
switch e := e.Child.(type) {
case *expression.GetField:
col = tableCol{table: strings.ToLower(e.Table()), col: strings.ToLower(e.Name())}
case *expression.UnresolvedColumn:
col = tableCol{table: strings.ToLower(e.Table()), col: strings.ToLower(e.Name())}
default:
}
case *expression.GetField:
col = tableCol{table: strings.ToLower(e.Table()), col: strings.ToLower(e.Name())}
case *expression.UnresolvedColumn:
col = tableCol{table: strings.ToLower(e.Table()), col: strings.ToLower(e.Name())}
case *expression.Star:
if len(e.Table) > 0 {
nodeStars = append(nodeStars, strings.ToLower(e.Table))
} else {
nodeUnqualifiedStar = true
}
default:
}
if col.col != "" {
cols = append(cols, col)
}
return false
})
}
return cols, nodeStars, nodeUnqualifiedStar
}
// gatherTableAlias bridges two scopes: the parent scope with
// its |parentCols|, and the child data source that is
// accessed through this node's alias name. We return the
// aliased columns qualified with the base table name,
// and stars if applicable.
// TODO: we don't have any tests with the unqualified condition
func gatherTableAlias(
n sql.Node,
parentCols map[tableCol]int,
parentStars map[string]struct{},
unqualifiedStar bool,
) ([]tableCol, []string) {
var cols []tableCol
var nodeStars []string
switch n := n.(type) {
case *plan.TableAlias:
alias := strings.ToLower(n.Name())
var base string
if rt, ok := n.Child.(*plan.ResolvedTable); ok {
base = rt.Name()
}
_, starred := parentStars[alias]
if unqualifiedStar {
starred = true
}
for _, col := range n.Schema() {
baseCol := tableCol{table: strings.ToLower(base), col: strings.ToLower(col.Name)}
aliasCol := tableCol{table: strings.ToLower(alias), col: strings.ToLower(col.Name)}
if starred || parentCols[aliasCol] > 0 {
// if the outer scope requests an aliased column
// a table lower in the tree must provide the source
cols = append(cols, baseCol)
}
}
for t := range parentStars {
if t == alias {
nodeStars = append(nodeStars, base)
}
}
return cols, nodeStars
default:
}
return cols, nodeStars
}
// todo(max): implement this
func gatherSubqueryExpression(n sql.Node) ([]tableCol, []string, bool) {
if sq := findSubqueryExpr(n); sq != nil {
return gatherOuterCols(sq.Query)
}
return nil, nil, false
}