1
|
1 |
|
module NoSE |
|
|
|
|
2
|
1 |
|
module Plans |
3
|
|
|
# Superclass for steps using indices |
4
|
1 |
|
class IndexLookupPlanStep < PlanStep |
5
|
1 |
|
extend Forwardable |
6
|
|
|
|
7
|
1 |
|
attr_reader :index, :eq_filter, :range_filter, :limit, :order_by |
8
|
1 |
|
delegate hash: :index |
9
|
|
|
|
10
|
1 |
|
def initialize(index, state = nil, parent = nil) |
11
|
1903 |
|
super() |
12
|
1903 |
|
@index = index |
13
|
|
|
|
14
|
1903 |
|
if state && state.query |
15
|
1893 |
|
all_fields = state.query.all_fields |
16
|
1893 |
|
@fields = (@index.hash_fields + @index.order_fields).to_set + \ |
17
|
1893 |
|
(@index.extra.to_set & all_fields) |
18
|
|
|
else |
19
|
10 |
|
@fields = @index.all_fields |
20
|
|
|
end |
21
|
|
|
|
22
|
1903 |
|
return if state.nil? |
23
|
1893 |
|
@state = state.dup |
24
|
1893 |
|
update_state parent |
25
|
1893 |
|
@state.freeze |
26
|
|
|
end |
27
|
|
|
|
28
|
|
|
# :nocov: |
29
|
1 |
|
def to_color |
30
|
|
|
if @state.nil? |
31
|
|
|
"#{super} #{@index.to_color}" |
32
|
|
|
else |
33
|
|
|
"#{super} #{@index.to_color} * " \ |
34
|
|
|
"#{@state.cardinality}/#{@state.hash_cardinality} " |
35
|
|
|
end |
36
|
|
|
end |
37
|
|
|
# :nocov: |
38
|
|
|
|
39
|
|
|
# Two index steps are equal if they use the same index |
40
|
1 |
|
def ==(other) |
41
|
17 |
|
other.instance_of?(self.class) && @index == other.index |
42
|
|
|
end |
43
|
1 |
|
alias eql? == |
44
|
|
|
|
45
|
|
|
# Check if this step can be applied for the given index, |
46
|
|
|
# returning a possible application of the step |
47
|
|
|
# @return [IndexLookupPlanStep] |
48
|
1 |
|
def self.apply(parent, index, state) |
49
|
|
|
# Validate several conditions which identify if this index is usable |
50
|
4626 |
|
begin |
51
|
4626 |
|
check_joins index, state |
52
|
4624 |
|
check_forward_lookup parent, index, state |
53
|
4431 |
|
check_parent_index parent, index, state |
54
|
3033 |
|
check_all_hash_fields parent, index, state |
55
|
1989 |
|
check_graph_fields parent, index, state |
56
|
1876 |
|
check_last_fields index, state |
57
|
|
|
rescue InvalidIndex |
58
|
2750 |
|
return nil |
59
|
|
|
end |
60
|
|
|
|
61
|
1876 |
|
IndexLookupPlanStep.new(index, state, parent) |
62
|
|
|
end |
63
|
|
|
|
64
|
|
|
# Check that this index is a valid continuation of the set of joins |
65
|
|
|
# @raise [InvalidIndex] |
66
|
|
|
# @return [void] |
67
|
1 |
|
def self.check_joins(index, state) |
68
|
2 |
|
fail InvalidIndex \ |
69
|
|
|
unless index.graph.entities.include?(state.joins.first) && |
70
|
|
|
(index.graph.unique_edges & |
71
|
|
|
state.graph.unique_edges == |
72
|
4626 |
|
index.graph.unique_edges) |
73
|
|
|
end |
74
|
1 |
|
private_class_method :check_joins |
75
|
|
|
|
76
|
|
|
# Check that this index moves forward on the list of joins |
77
|
|
|
# @raise [InvalidIndex] |
78
|
|
|
# @return [void] |
79
|
1 |
|
def self.check_forward_lookup(parent, index, state) |
80
|
|
|
# XXX This disallows plans which look up additional attributes |
81
|
|
|
# for entities other than the final one |
82
|
4624 |
|
fail InvalidIndex if index.graph.size == 1 && state.graph.size > 1 && |
83
|
|
|
!parent.is_a?(RootPlanStep) |
84
|
4452 |
|
fail InvalidIndex if index.identity? && state.graph.size > 1 |
85
|
|
|
end |
86
|
1 |
|
private_class_method :check_forward_lookup |
87
|
|
|
|
88
|
|
|
# Check if this index can be used after the current parent |
89
|
|
|
# @return [Boolean] |
90
|
1 |
|
def self.invalid_parent_index?(state, index, parent_index) |
|
|
|
|
91
|
4431 |
|
return false if parent_index.nil? |
92
|
|
|
|
93
|
|
|
# We don't do multiple lookups by ID for the same entity set |
94
|
|
|
return true if parent_index.identity? && |
95
|
2745 |
|
index.graph == parent_index.graph |
96
|
|
|
|
97
|
|
|
# If the last step gave an ID, we must use it |
98
|
|
|
# XXX This doesn't cover all cases |
99
|
2114 |
|
last_parent_entity = state.joins.reverse.find do |entity| |
100
|
3654 |
|
parent_index.graph.entities.include? entity |
101
|
|
|
end |
102
|
2114 |
|
parent_ids = Set.new [last_parent_entity.id_field] |
103
|
2114 |
|
has_ids = parent_ids.subset? parent_index.all_fields |
104
|
2114 |
|
return true if has_ids && index.hash_fields.to_set != parent_ids |
105
|
|
|
|
106
|
|
|
# If we're looking up from a previous step, only allow lookup by ID |
107
|
|
|
return true unless (index.graph.size == 1 && |
108
|
|
|
parent_index.graph != index.graph) || |
109
|
1347 |
|
index.hash_fields == parent_ids |
110
|
|
|
end |
111
|
1 |
|
private_class_method :invalid_parent_index? |
112
|
|
|
|
113
|
|
|
# Check that this index is a valid continuation of the set of joins |
114
|
|
|
# @raise [InvalidIndex] |
115
|
|
|
# @return [void] |
116
|
1 |
|
def self.check_parent_index(parent, index, state) |
117
|
1398 |
|
fail InvalidIndex \ |
118
|
4431 |
|
if invalid_parent_index? state, index, parent.parent_index |
119
|
|
|
end |
120
|
1 |
|
private_class_method :check_parent_index |
121
|
|
|
|
122
|
|
|
# Check that we have all hash fields needed to perform the lookup |
123
|
|
|
# @raise [InvalidIndex] |
124
|
|
|
# @return [void] |
125
|
1 |
|
def self.check_all_hash_fields(parent, index, state) |
126
|
3033 |
|
fail InvalidIndex unless index.hash_fields.all? do |field| |
127
|
3044 |
|
(parent.fields + state.given_fields).include? field |
128
|
|
|
end |
129
|
|
|
end |
130
|
1 |
|
private_class_method :check_all_hash_fields |
131
|
|
|
|
132
|
|
|
# Get fields in the query relevant to this index |
133
|
|
|
# and check that they are provided for us here |
134
|
|
|
# @raise [InvalidIndex] |
135
|
|
|
# @return [void] |
136
|
1 |
|
def self.check_graph_fields(parent, index, state) |
137
|
1989 |
|
hash_entity = index.hash_fields.first.parent |
138
|
1989 |
|
graph_fields = state.fields_for_graph(index.graph, hash_entity).to_set |
139
|
1989 |
|
graph_fields -= parent.fields # exclude fields already fetched |
140
|
1989 |
|
fail InvalidIndex unless graph_fields.subset?(index.all_fields) |
141
|
|
|
end |
142
|
1 |
|
private_class_method :check_graph_fields |
143
|
|
|
|
144
|
|
|
# Check that we have the required fields to move on with the next lookup |
145
|
|
|
# @return [Boolean] |
146
|
1 |
|
def self.last_fields?(index, state) |
147
|
1876 |
|
index_includes = lambda do |fields| |
148
|
5830 |
|
fields.all? { |f| index.all_fields.include? f } |
149
|
|
|
end |
150
|
|
|
|
151
|
|
|
# We must have either the ID or all the fields |
152
|
|
|
# for leaf entities in the original graph |
153
|
1876 |
|
leaf_entities = index.graph.entities.select do |entity| |
154
|
3333 |
|
state.graph.leaf_entity?(entity) |
155
|
|
|
end |
156
|
1876 |
|
leaf_entities.all? do |entity| |
157
|
|
|
index_includes.call([entity.id_field]) || |
158
|
2915 |
|
index_includes.call(state.fields.select { |f| f.parent == entity }) |
159
|
|
|
end |
160
|
|
|
end |
161
|
1 |
|
private_class_method :last_fields? |
162
|
|
|
|
163
|
|
|
# @raise [InvalidIndex] |
164
|
|
|
# @return [void] |
165
|
1 |
|
def self.check_last_fields(index, state) |
166
|
1876 |
|
fail InvalidIndex unless last_fields?(index, state) |
167
|
|
|
end |
168
|
1 |
|
private_class_method :check_last_fields |
169
|
|
|
|
170
|
1 |
|
private |
171
|
|
|
|
172
|
|
|
# Get the set of fields which can be filtered by the ordered keys |
173
|
|
|
# @return [Array<Fields::Field>] |
174
|
1 |
|
def range_order_prefix |
175
|
1893 |
|
order_prefix = (@state.eq - @index.hash_fields) & @index.order_fields |
176
|
1893 |
|
order_prefix << @state.range unless @state.range.nil? |
177
|
1893 |
|
order_prefix = order_prefix.zip(@index.order_fields) |
178
|
1895 |
|
order_prefix.take_while { |x, y| x == y }.map(&:first) |
179
|
|
|
end |
180
|
|
|
|
181
|
|
|
# Perform any ordering implicit to this index |
182
|
|
|
# @return [Boolean] whether this index is by ID |
183
|
1 |
|
def resolve_order |
|
|
|
|
184
|
|
|
# We can't resolve ordering if we're doing an ID lookup |
185
|
|
|
# since only one record exists per row (if it's the same entity) |
186
|
|
|
# We also need to have the fields used in order |
187
|
1893 |
|
first_join = @state.query.join_order.detect do |entity| |
188
|
3797 |
|
@index.graph.entities.include? entity |
189
|
|
|
end |
190
|
1893 |
|
indexed_by_id = @index.hash_fields.include?(first_join.id_field) |
191
|
1893 |
|
order_prefix = @state.order_by.longest_common_prefix( |
192
|
|
|
@index.order_fields - @eq_filter.to_a |
193
|
|
|
) |
194
|
|
|
if indexed_by_id && order_prefix.map(&:parent).to_set == |
195
|
1893 |
|
Set.new([@index.hash_fields.first.parent]) |
196
|
112 |
|
order_prefix = [] |
197
|
|
|
else |
198
|
1781 |
|
@state.order_by -= order_prefix |
199
|
|
|
end |
200
|
1893 |
|
@order_by = order_prefix |
201
|
|
|
|
202
|
1893 |
|
indexed_by_id |
203
|
|
|
end |
204
|
|
|
|
205
|
|
|
# Strip the graph for this index, but if we haven't fetched all |
206
|
|
|
# fields, leave the last one so we can perform a separate ID lookup |
207
|
|
|
# @return [void] |
208
|
1 |
|
def strip_graph |
|
|
|
|
209
|
1893 |
|
hash_entity = @index.hash_fields.first.parent |
210
|
1893 |
|
@state.graph = @state.graph.dup |
211
|
1893 |
|
required_fields = @state.fields_for_graph(@index.graph, hash_entity, |
212
|
|
|
select: true).to_set |
213
|
|
|
if required_fields.subset?(@index.all_fields) && |
214
|
1893 |
|
@state.graph == @index.graph |
215
|
1139 |
|
removed_nodes = @state.joins[[email protected]] |
216
|
1139 |
|
@state.joins = @state.joins[@index.graph.size..-1] |
217
|
|
|
else |
218
|
754 |
|
removed_nodes = if index.graph.size == 1 |
219
|
50 |
|
[] |
220
|
|
|
else |
221
|
704 |
|
@state.joins[[email protected] - 2] |
222
|
|
|
end |
223
|
754 |
|
@state.joins = @state.joins[@index.graph.size - 1..-1] |
224
|
|
|
end |
225
|
|
|
|
226
|
|
|
# Remove nodes which have been processed from the graph |
227
|
1893 |
|
@state.graph.remove_nodes removed_nodes |
228
|
|
|
end |
229
|
|
|
|
230
|
|
|
# Update the cardinality of this step, applying a limit if possible |
231
|
1 |
|
def update_cardinality(parent, indexed_by_id) |
|
|
|
|
232
|
|
|
# Calculate the new cardinality assuming no limit |
233
|
|
|
# Hash cardinality starts at 1 or is the previous cardinality |
234
|
1893 |
|
if parent.is_a?(RootPlanStep) |
235
|
546 |
|
@state.hash_cardinality = 1 |
236
|
|
|
else |
237
|
1347 |
|
@state.hash_cardinality = parent.state.cardinality |
238
|
|
|
end |
239
|
|
|
|
240
|
|
|
# Filter the total number of rows by filtering on non-hash fields |
241
|
1893 |
|
cardinality = @index.per_hash_count * @state.hash_cardinality |
242
|
1893 |
|
@state.cardinality = Cardinality.filter cardinality, |
243
|
|
|
@eq_filter - |
244
|
|
|
@index.hash_fields, |
245
|
|
|
@range_filter |
246
|
|
|
|
247
|
|
|
# Check if we can apply the limit from the query |
248
|
|
|
# This occurs either when we are on the first or last index lookup |
249
|
|
|
# and the ordering of the query has already been resolved |
250
|
1893 |
|
order_resolved = @state.order_by.empty? && @state.graph.size == 1 |
251
|
|
|
return unless (@state.answered?(check_limit: false) || |
252
|
|
|
parent.is_a?(RootPlanStep) && order_resolved) && |
253
|
1893 |
|
[email protected]? |
254
|
|
|
|
255
|
|
|
# XXX Assume that everything is limited by the limit value |
256
|
|
|
# which should be fine if the limit is small enough |
257
|
6 |
|
@limit = @state.query.limit |
258
|
6 |
|
if parent.is_a?(RootPlanStep) |
259
|
6 |
|
@state.cardinality = [@limit, @state.cardinality].min |
260
|
6 |
|
@state.hash_cardinality = 1 |
261
|
|
|
else |
262
|
|
|
@limit = @state.cardinality = @state.query.limit |
263
|
|
|
|
264
|
|
|
# If this is a final lookup by ID, go with the limit |
265
|
|
|
if @index.graph.size == 1 && indexed_by_id |
266
|
|
|
@state.hash_cardinality = @limit |
267
|
|
|
else |
268
|
|
|
@state.hash_cardinality = parent.state.cardinality |
269
|
|
|
end |
270
|
|
|
end |
271
|
|
|
end |
272
|
|
|
|
273
|
|
|
# Modify the state to reflect the fields looked up by the index |
274
|
|
|
# @return [void] |
275
|
1 |
|
def update_state(parent) |
276
|
1893 |
|
order_prefix = range_order_prefix.to_set |
277
|
|
|
|
278
|
|
|
# Find fields which are filtered by the index |
279
|
1893 |
|
@eq_filter = @index.hash_fields + (@state.eq & order_prefix) |
280
|
1893 |
|
if order_prefix.include?(@state.range) |
281
|
|
|
@range_filter = @state.range |
282
|
|
|
@state.range = nil |
283
|
|
|
else |
284
|
1893 |
|
@range_filter = nil |
285
|
|
|
end |
286
|
|
|
|
287
|
|
|
# Remove fields resolved by this index |
288
|
1893 |
|
@state.fields -= @index.all_fields |
289
|
1893 |
|
@state.eq -= @eq_filter |
290
|
|
|
|
291
|
1893 |
|
indexed_by_id = resolve_order |
292
|
1893 |
|
strip_graph |
293
|
1893 |
|
update_cardinality parent, indexed_by_id |
294
|
|
|
end |
295
|
|
|
end |
296
|
|
|
|
297
|
1 |
|
class InvalidIndex < StandardError |
298
|
|
|
end |
299
|
|
|
end |
300
|
|
|
end |
301
|
|
|
|