Completed
Push — master ( cb5396...b3a8d6 )
by Michael
03:06
created

IndexLookupPlanStep.check_parent_index()   A

Complexity

Conditions 2

Size

Total Lines 4

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 3
CRAP Score 2

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 2
c 1
b 0
f 0
dl 0
loc 4
ccs 3
cts 3
cp 1
crap 2
rs 10
1 1
module NoSE
0 ignored issues
show
coding-style introduced by
Missing frozen string literal comment.
Loading history...
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)
0 ignored issues
show
Coding Style introduced by
The Assignment, Branch, Condition size for invalid_parent_index? is considered too high. [27.37/20]. The ABC size is based on assignments, branches (method calls), and conditions.
Loading history...
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
0 ignored issues
show
Coding Style introduced by
The Assignment, Branch, Condition size for resolve_order is considered too high. [22.89/20]. The ABC size is based on assignments, branches (method calls), and conditions.
Loading history...
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
0 ignored issues
show
Coding Style introduced by
The Assignment, Branch, Condition size for strip_graph is considered too high. [37.78/20]. The ABC size is based on assignments, branches (method calls), and conditions.
Loading history...
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)
0 ignored issues
show
Coding Style introduced by
The Assignment, Branch, Condition size for update_cardinality is considered too high. [35.34/20]. The ABC size is based on assignments, branches (method calls), and conditions.
Loading history...
Coding Style introduced by
This method is 26 lines long. Your coding style permits a maximum length of 20.
Loading history...
Complexity Coding Style introduced by
The method update_cardinality seems to be too complex. Perceived complexity is 13 with a maxiumum of 10 permitted.
Loading history...
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