-
Notifications
You must be signed in to change notification settings - Fork 2.1k
/
querygraph.go
209 lines (179 loc) · 5.81 KB
/
querygraph.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
/*
Copyright 2021 The Vitess Authors.
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 operators
import (
"strings"
"vitess.io/vitess/go/vt/sqlparser"
"vitess.io/vitess/go/vt/vtgate/planbuilder/plancontext"
"vitess.io/vitess/go/vt/vtgate/semantics"
)
type (
/*QueryGraph represents the FROM and WHERE parts of a query.
It is an intermediate representation of the query that makes it easier for the planner
to find all possible join combinations. Instead of storing the query information in a form that is close
to the syntax (AST), we extract the interesting parts into a graph form with the nodes being tables in the FROM
clause and the edges between them being predicates. We keep predicates in a hash map keyed by the dependencies of
the predicate. This makes it very fast to look up connections between tables in the query.
*/
QueryGraph struct {
// the Tables, including predicates that only depend on this particular table
Tables []*QueryTable
// innerJoins contains the predicates that need multiple Tables
innerJoins []*innerJoin
// NoDeps contains the predicates that can be evaluated anywhere.
NoDeps sqlparser.Expr
noInputs
noColumns
}
innerJoin struct {
deps semantics.TableSet
exprs []sqlparser.Expr
}
// QueryTable is a single FROM table, including all predicates particular to this table
// This is to be used as an immutable data structure which is created in the logical Operator Tree
QueryTable struct {
ID semantics.TableSet
Alias *sqlparser.AliasedTableExpr
Table sqlparser.TableName
Predicates []sqlparser.Expr
IsInfSchema bool
}
)
var _ Operator = (*QueryGraph)(nil)
// Introduces implements the tableIDIntroducer interface
func (qg *QueryGraph) introducesTableID() semantics.TableSet {
var ts semantics.TableSet
for _, table := range qg.Tables {
ts = ts.Merge(table.ID)
}
return ts
}
// GetPredicates returns the predicates that are applicable for the two given TableSets
func (qg *QueryGraph) GetPredicates(lhs, rhs semantics.TableSet) []sqlparser.Expr {
var allExprs []sqlparser.Expr
for _, join := range qg.innerJoins {
tableSet, exprs := join.deps, join.exprs
if tableSet.IsSolvedBy(lhs.Merge(rhs)) &&
tableSet.IsOverlapping(rhs) &&
tableSet.IsOverlapping(lhs) {
allExprs = append(allExprs, exprs...)
}
}
return allExprs
}
func newQueryGraph() *QueryGraph {
return &QueryGraph{}
}
func (qg *QueryGraph) addJoinPredicates(ctx *plancontext.PlanningContext, ts semantics.TableSet, predicate sqlparser.Expr) {
for _, join := range qg.innerJoins {
if join.deps == ts {
if ctx.SemTable.ContainsExpr(predicate, join.exprs) {
return
}
join.exprs = append(join.exprs, predicate)
return
}
}
qg.innerJoins = append(qg.innerJoins, &innerJoin{
deps: ts,
exprs: []sqlparser.Expr{predicate},
})
}
func (qg *QueryGraph) collectPredicate(ctx *plancontext.PlanningContext, predicate sqlparser.Expr) {
deps := ctx.SemTable.RecursiveDeps(predicate)
switch deps.NumberOfTables() {
case 0:
qg.addNoDepsPredicate(predicate)
case 1:
found := qg.addToSingleTable(ctx, deps, predicate)
if !found {
// this could be a predicate that only has dependencies from outside this QG
qg.addJoinPredicates(ctx, deps, predicate)
}
default:
qg.addJoinPredicates(ctx, deps, predicate)
}
}
func (qg *QueryGraph) addToSingleTable(ctx *plancontext.PlanningContext, table semantics.TableSet, predicate sqlparser.Expr) bool {
for _, t := range qg.Tables {
if table == t.ID {
if !ctx.SemTable.ContainsExpr(predicate, t.Predicates) {
t.Predicates = append(t.Predicates, predicate)
}
return true
}
}
return false
}
func (qg *QueryGraph) addNoDepsPredicate(predicate sqlparser.Expr) {
if qg.NoDeps == nil {
qg.NoDeps = predicate
} else {
qg.NoDeps = &sqlparser.AndExpr{
Left: qg.NoDeps,
Right: predicate,
}
}
}
// UnsolvedPredicates implements the unresolved interface
func (qg *QueryGraph) UnsolvedPredicates(_ *semantics.SemTable) []sqlparser.Expr {
var result []sqlparser.Expr
tables := TableID(qg)
for _, join := range qg.innerJoins {
set, exprs := join.deps, join.exprs
if !set.IsSolvedBy(tables) {
result = append(result, exprs...)
}
}
return result
}
// Clone implements the Operator interface
func (qg *QueryGraph) Clone([]Operator) Operator {
result := &QueryGraph{
Tables: nil,
innerJoins: nil,
NoDeps: nil,
}
result.Tables = append([]*QueryTable{}, qg.Tables...)
result.innerJoins = append([]*innerJoin{}, qg.innerJoins...)
result.NoDeps = qg.NoDeps
return result
}
func (qg *QueryGraph) GetOrdering(*plancontext.PlanningContext) []OrderBy {
return nil
}
func (qg *QueryGraph) AddPredicate(ctx *plancontext.PlanningContext, expr sqlparser.Expr) Operator {
for _, e := range sqlparser.SplitAndExpression(nil, expr) {
qg.collectPredicate(ctx, e)
}
return qg
}
// Clone implements the Operator interface
func (qt *QueryTable) Clone() *QueryTable {
return &QueryTable{
ID: qt.ID,
Alias: sqlparser.CloneRefOfAliasedTableExpr(qt.Alias),
Table: sqlparser.CloneTableName(qt.Table),
Predicates: qt.Predicates,
IsInfSchema: qt.IsInfSchema,
}
}
func (qg *QueryGraph) tableNames() (tables []string) {
for _, table := range qg.Tables {
tables = append(tables, sqlparser.String(table.Table))
}
return
}
func (qg *QueryGraph) ShortDescription() string {
return strings.Join(qg.tableNames(), ", ")
}