This repository has been archived by the owner on Feb 16, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 108
/
select.go
163 lines (149 loc) · 5.7 KB
/
select.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
// Copyright 2019 eBay Inc.
// Primary authors: Simon Fell, Diego Ongaro,
// Raymond Kroeker, and Sathish Kandasamy.
//
// 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
// https://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 planner
import (
"github.com/ebay/akutan/query/parser"
"github.com/ebay/akutan/query/planner/plandef"
"github.com/ebay/akutan/query/planner/search"
"github.com/ebay/akutan/util/cmp"
)
// pushDownSelectLit and pushDownSelectVar will generate alternatives where a
// select operator has been pushed further down the plan tree. The closer to the
// leaves the select can be placed, the more efficient the execution will be.
//
// For select over inner joins and left joins, applies:
// Before: select(x cmp k, join(a, b)) where a and b emit x
// After: join(select(x cmp k, a), select(x cmp k, b))
// or
// Before: select(x cmp k, join(a, b)) where a emits x
// After: join(select(x cmp k, a), b)
// or
// Before: select(x cmp k, join(a, b)) where b emits x
// After: join(a, select(x cmp k, b))
//
// For select over select, applies:
// Before: select(x cmp k, select(y cmp l, a))
// After: select(y cmp l, select(x cmp k, a))
//
// The included case for leftLoopJoin is related to the workaround described in
// preImplementLeftLoopJoin. That work around means there will not be any
// leftJoins in the plan, just optional LoopJoins
//
func pushDownSelectLit(root *search.Expr) []*search.IntoExpr {
selection, ok := root.Operator.(*plandef.SelectLit)
if !ok {
return nil
}
selectionVars := plandef.VarSet{selection.Test}
return pushDownSelectImpl(selectionVars, root.Operator, root.Inputs[0])
}
// pushDownSelectVar generates alternatives for a selectVar where the selection
// has been pushed down the tree. This does the same as pushDownSelectLit, but
// for the SelectVar selection operator. see pushDownSelectLit for details on
// the rules it applies.
func pushDownSelectVar(root *search.Expr) []*search.IntoExpr {
selection, ok := root.Operator.(*plandef.SelectVar)
if !ok {
return nil
}
vars := map[string]*plandef.Variable{
selection.Left.Name: selection.Left,
selection.Right.Name: selection.Right,
}
selectionVars := plandef.NewVarSet(vars)
return pushDownSelectImpl(selectionVars, root.Operator, root.Inputs[0])
}
// pushDownSelectImpl does the real work for pushDownSelectLit & pushDownSelectVar.
// It will return alternatives where 'selectOp' has been push down below operators
// where those operators inputs still contain all the variables in 'reqVars'.
func pushDownSelectImpl(reqVars plandef.VarSet, selectOp search.Operator, selectInput *search.Group) []*search.IntoExpr {
var ret []*search.IntoExpr
for _, alt := range selectInput.Exprs {
switch op := alt.Operator.(type) {
case *innerJoinOperator:
ret = append(ret,
selectOverJoinAlternatives(reqVars, selectOp, op, alt.Inputs)...)
case *leftJoinOperator:
ret = append(ret,
selectOverJoinAlternatives(reqVars, selectOp, op, alt.Inputs)...)
case *plandef.LoopJoin:
// This is part of the work around described in preImplementLeftLoopJoin.
// When that is removed, this case can be removed as well.
if op.Specificity == parser.MatchOptional {
ret = append(ret,
selectOverJoinAlternatives(reqVars, selectOp, op, alt.Inputs)...)
}
case *plandef.SelectLit:
ret = append(ret, search.NewExpr(
alt.Operator,
search.NewExpr(selectOp, alt.Inputs[0])))
case *plandef.SelectVar:
ret = append(ret, search.NewExpr(
alt.Operator,
search.NewExpr(selectOp, alt.Inputs[0])))
}
}
return ret
}
// selectOverJoinAlternatives is a helper function used by pushDownSelectImpl to
// generate alternate results for a select over join operation. It will push the
// select down to any input to the join that produces all the variables required
// by the select. Returns the list of generated alternatives.
func selectOverJoinAlternatives(reqVars plandef.VarSet, selectOp search.Operator,
joinOp search.Operator, joinInputs []*search.Group) []*search.IntoExpr {
var ret []*search.IntoExpr
leftVars := joinInputs[0].LogicalProp.(*logicalProperties).variables
rightVars := joinInputs[1].LogicalProp.(*logicalProperties).variables
pushLeft := leftVars.ContainsSet(reqVars)
pushRight := rightVars.ContainsSet(reqVars)
if pushLeft && pushRight {
ret = append(ret, search.NewExpr(
joinOp,
search.NewExpr(selectOp, joinInputs[0]),
search.NewExpr(selectOp, joinInputs[1]),
))
} else if pushLeft {
ret = append(ret, search.NewExpr(
joinOp,
search.NewExpr(selectOp, joinInputs[0]),
joinInputs[1],
))
} else if pushRight {
ret = append(ret, search.NewExpr(
joinOp,
joinInputs[0],
search.NewExpr(selectOp, joinInputs[1]),
))
}
return ret
}
func selectionCost(expr *search.Expr, stats Stats) *estCost {
return &estCost{
diskBytes: 0,
diskSeeks: 0,
}
}
func selectLitLogicalProperties(op *plandef.SelectLit, inputs []*logicalProperties, stats Stats) *logicalProperties {
return &logicalProperties{
variables: inputs[0].variables,
resultSize: cmp.MaxInt(1, inputs[0].resultSize/2),
}
}
func selectVarLogicalProperties(op *plandef.SelectVar, inputs []*logicalProperties, stats Stats) *logicalProperties {
return &logicalProperties{
variables: inputs[0].variables,
resultSize: cmp.MaxInt(1, inputs[0].resultSize/2),
}
}