-
Notifications
You must be signed in to change notification settings - Fork 2.1k
/
querygraph.go
191 lines (166 loc) · 5.31 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
/*
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 abstract
import (
vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
"vitess.io/vitess/go/vt/sqlparser"
"vitess.io/vitess/go/vt/vterrors"
"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
}
innerJoin struct {
deps semantics.TableSet
exprs []sqlparser.Expr
}
// QueryTable is a single FROM table, including all predicates particular to this table
QueryTable struct {
TableID semantics.TableSet
Alias *sqlparser.AliasedTableExpr
Table sqlparser.TableName
Predicates []sqlparser.Expr
IsInfSchema bool
}
)
var _ Operator = (*QueryGraph)(nil)
// PushPredicate implements the Operator interface
func (qg *QueryGraph) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable) error {
for _, e := range sqlparser.SplitAndExpression(nil, expr) {
err := qg.collectPredicate(e, semTable)
if err != nil {
return err
}
}
return nil
}
// TableID implements the Operator interface
func (qg *QueryGraph) TableID() semantics.TableSet {
var ts semantics.TableSet
for _, table := range qg.Tables {
ts = ts.Merge(table.TableID)
}
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) collectPredicates(sel *sqlparser.Select, semTable *semantics.SemTable) error {
predicates := sqlparser.SplitAndExpression(nil, sel.Where.Expr)
for _, predicate := range predicates {
err := qg.collectPredicate(predicate, semTable)
if err != nil {
return err
}
}
return nil
}
func (qg *QueryGraph) getPredicateByDeps(ts semantics.TableSet) ([]sqlparser.Expr, bool) {
for _, join := range qg.innerJoins {
if join.deps == ts {
return join.exprs, true
}
}
return nil, false
}
func (qg *QueryGraph) addJoinPredicates(ts semantics.TableSet, expr sqlparser.Expr) {
for _, join := range qg.innerJoins {
if join.deps == ts {
join.exprs = append(join.exprs, expr)
return
}
}
qg.innerJoins = append(qg.innerJoins, &innerJoin{
deps: ts,
exprs: []sqlparser.Expr{expr},
})
}
func (qg *QueryGraph) collectPredicate(predicate sqlparser.Expr, semTable *semantics.SemTable) error {
deps := semTable.RecursiveDeps(predicate)
switch deps.NumberOfTables() {
case 0:
qg.addNoDepsPredicate(predicate)
case 1:
found := qg.addToSingleTable(deps, predicate)
if !found {
return vterrors.Errorf(vtrpcpb.Code_INTERNAL, "table %v for predicate %v not found", deps, sqlparser.String(predicate))
}
default:
qg.addJoinPredicates(deps, predicate)
}
return nil
}
func (qg *QueryGraph) addToSingleTable(table semantics.TableSet, predicate sqlparser.Expr) bool {
for _, t := range qg.Tables {
if table == t.TableID {
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 Operator interface
func (qg *QueryGraph) UnsolvedPredicates(_ *semantics.SemTable) []sqlparser.Expr {
var result []sqlparser.Expr
for _, join := range qg.innerJoins {
set, exprs := join.deps, join.exprs
if !set.IsSolvedBy(qg.TableID()) {
result = append(result, exprs...)
}
}
return result
}
// CheckValid implements the Operator interface
func (qg *QueryGraph) CheckValid() error {
return nil
}
// Compact implements the Operator interface
func (qg *QueryGraph) Compact(*semantics.SemTable) (Operator, error) {
return qg, nil
}