Debian Codegraph @

storage/mroonga/vendor/groonga/lib/mrb/scripts/scan_info_builder.rb

raw
1 require "scan_info_data"
2
3 module Groonga
4 class ScanInfoBuilder
5 def initialize(expression, operator, record_exist)
6 @data_list = []
7 @expression = expression
8 @operator = operator
9 @record_exist = record_exist
10 @variable = @expression[0]
11 @table = Context.instance[@variable.domain]
12 end
13
14 RELATION_OPERATORS = [
15 Operator::MATCH,
16 Operator::NEAR,
17 Operator::NEAR2,
18 Operator::SIMILAR,
19 Operator::PREFIX,
20 Operator::SUFFIX,
21 Operator::EQUAL,
22 Operator::NOT_EQUAL,
23 Operator::LESS,
24 Operator::GREATER,
25 Operator::LESS_EQUAL,
26 Operator::GREATER_EQUAL,
27 Operator::GEO_WITHINP5,
28 Operator::GEO_WITHINP6,
29 Operator::GEO_WITHINP8,
30 Operator::TERM_EXTRACT,
31 Operator::REGEXP,
32 Operator::FUZZY,
33 ]
34
35 ARITHMETIC_OPERATORS = [
36 Operator::BITWISE_OR,
37 Operator::BITWISE_XOR,
38 Operator::BITWISE_AND,
39 Operator::BITWISE_NOT,
40 Operator::SHIFTL,
41 Operator::SHIFTR,
42 Operator::SHIFTRR,
43 Operator::PLUS,
44 Operator::MINUS,
45 Operator::STAR,
46 Operator::MOD,
47 ]
48
49 LOGICAL_OPERATORS = [
50 Operator::AND,
51 Operator::OR,
52 Operator::AND_NOT,
53 Operator::ADJUST,
54 ]
55 def build
56 return nil unless valid?
57
58 context = BuildContext.new(@expression)
59 codes = context.codes
60 while context.have_next?
61 code = context.code
62 code_op = context.code_op
63 i = context.i
64 context.next
65
66 case code_op
67 when *RELATION_OPERATORS
68 context.status = :start
69 data = context.data
70 data.op = code_op
71 data.end = i
72 data.weight = code.value.value if code.value
73 data.match_resolve_index
74 @data_list << data
75 context.data = nil
76 when *LOGICAL_OPERATORS
77 if context.status == :const
78 data = context.data
79 data.op = Operator::PUSH
80 data.end = data.start
81 @data_list << data
82 context.data = nil
83 end
84 put_logical_op(code_op, i)
85 # TODO: rescue and return nil
86 context.status = :start
87 when Operator::PUSH
88 context.data ||= ScanInfoData.new(i)
89 data = context.data
90 if code.value == @variable
91 context.status = :var
92 else
93 data.args << code.value
94 if context.status == :start
95 data.flags |= ScanInfo::Flags::PRE_CONST
96 end
97 context.status = :const
98 end
99 if code.modify > 0 and
100 LOGICAL_OPERATORS.include?(codes[i + code.modify].op)
101 data.op = Operator::PUSH
102 data.end = data.start
103 @data_list << data
104 context.data = nil
105 context.status = :start
106 end
107 when Operator::GET_VALUE
108 case context.status
109 when :start
110 context.data ||= ScanInfoData.new(i)
111 data = context.data
112 context.status = :column1
113 data.args << code.value
114 when :const, :var
115 context.status = :column1
116 data.args << code.value
117 when :column1
118 message = "invalid expression: can't use column as a value: "
119 message << "<#{code.value.name}>: <#{@expression.grn_inspect}>"
120 raise ErrorMessage, message
121 when :column2
122 # Do nothing
123 else
124 message = "internal expression parsing error: unknown status: "
125 message << "<#{context.status.inspect}>: "
126 message << "<#{@expression.grn_inspect}>"
127 raise ErrorMessage, message
128 end
129 when Operator::CALL
130 context.data ||= ScanInfoData.new(i)
131 data = context.data
132 if (code.flags & ExpressionCode::Flags::RELATIONAL_EXPRESSION) != 0 or
133 (not context.have_next?)
134 context.status = :start
135 data.op = code_op
136 data.end = i
137 data.call_relational_resolve_indexes
138 @data_list << data
139 context.data = nil
140 else
141 context.status = :column2
142 end
143 when Operator::GET_REF
144 context.data ||= ScanInfoData.new(i)
145 case context.status
146 when :start
147 data = context.data
148 context.status = :column1
149 data.args << code.value
150 end
151 when Operator::GET_MEMBER
152 data = context.data
153 index = data.args.pop
154 data.start_position = index.value
155 context.status = :column1
156 when Operator::NOT
157 success = build_not(context, code, i)
158 return nil unless success
159 end
160 end
161
162 if @operator == Operator::OR and !@record_exist
163 first_data = @data_list.first
164 if (first_data.flags & ScanInfo::Flags::PUSH) == 0 or
165 first_data.logical_op != @operator
166 raise ErrorMessage, "invalid expr"
167 else
168 first_data.flags &= ~ScanInfo::Flags::PUSH
169 first_data.logical_op = @operator
170 end
171 else
172 put_logical_op(@operator, context.n_codes)
173 end
174
175 optimize
176 end
177
178 private
179 def valid?
180 n_relation_expressions = 0
181 n_logical_expressions = 0
182 status = :start
183 codes = @expression.codes
184 codes.each_with_index do |code, i|
185 case code.op
186 when *RELATION_OPERATORS
187 if status == :start || status == :var
188 return false
189 end
190 status = :start
191 n_relation_expressions += 1
192 when *ARITHMETIC_OPERATORS
193 if status == :start || status == :var
194 return false
195 end
196 status = :start
197 return false if n_relation_expressions != (n_logical_expressions + 1)
198 when *LOGICAL_OPERATORS
199 case status
200 when :start
201 n_logical_expressions += 1
202 return false if n_logical_expressions >= n_relation_expressions
203 when :const
204 n_logical_expressions += 1
205 n_relation_expressions += 1
206 return false if n_logical_expressions >= n_relation_expressions
207 status = :start
208 else
209 return false
210 end
211 when Operator::PUSH
212 if code.modify > 0 and
213 LOGICAL_OPERATORS.include?(codes[i + code.modify].op)
214 n_relation_expressions += 1
215 status = :start
216 else
217 if code.value == @variable
218 status = :var
219 else
220 status = :const
221 end
222 end
223 when Operator::GET_VALUE
224 case status
225 when :start, :const, :var
226 status = :column1
227 when :column1
228 status = :column2
229 when :column2
230 # Do nothing
231 else
232 return false
233 end
234 when Operator::CALL
235 if (code.flags & ExpressionCode::Flags::RELATIONAL_EXPRESSION) != 0 or
236 code == codes.last
237 status = :start
238 n_relation_expressions += 1
239 else
240 status = :column2
241 end
242 when Operator::GET_REF
243 case status
244 when :start
245 status = :column1
246 else
247 return false
248 end
249 when Operator::GET_MEMBER
250 case status
251 when :const
252 return false unless codes[i - 1].value.value.is_a?(Integer)
253 status = :column1
254 else
255 return false
256 end
257 when Operator::NOT
258 # Do nothing
259 else
260 return false
261 end
262 end
263
264 return false if status != :start
265 return false if n_relation_expressions != (n_logical_expressions + 1)
266
267 true
268 end
269
270 def put_logical_op(operator, start)
271 n_parens = 1
272 n_dif_ops = 0
273 r = 0
274 j = @data_list.size
275 while j > 0
276 j -= 1
277 data = @data_list[j]
278 if (data.flags & ScanInfo::Flags::POP) != 0
279 n_dif_ops += 1
280 n_parens += 1
281 else
282 if (data.flags & ScanInfo::Flags::PUSH) != 0
283 n_parens -= 1
284 if n_parens == 0
285 if r == 0
286 if n_dif_ops > 0
287 if j > 0 and operator != Operator::AND_NOT
288 n_parens = 1
289 n_dif_ops = 0
290 r = j
291 else
292 new_data = ScanInfoData.new(start)
293 new_data.flags = ScanInfo::Flags::POP
294 new_data.logical_op = operator
295 @data_list << new_data
296 break
297 end
298 else
299 data.flags &= ~ScanInfo::Flags::PUSH
300 data.logical_op = operator
301 break
302 end
303 else
304 if n_dif_ops > 0
305 new_data = ScanInfoData.new(start)
306 new_data.flags = ScanInfo::Flags::POP
307 new_data.logical_op = operator
308 @data_list << new_data
309 else
310 data.flags &= ~ScanInfo::Flags::PUSH
311 data.logical_op = operator
312 @data_list =
313 @data_list[0...j] +
314 @data_list[r..-1] +
315 @data_list[j...r]
316 end
317 break
318 end
319 end
320 else
321 if operator == Operator::AND_NOT or operator != data.logical_op
322 n_dif_ops += 1
323 end
324 end
325 end
326
327 if j < 0
328 raise ErrorMessage, "unmatched nesting level"
329 end
330 end
331 end
332
333 def build_not(context, code, i)
334 last_data = @data_list.last
335 return false if last_data.nil?
336
337 case last_data.op
338 when Operator::LESS
339 last_data.op = Operator::GREATER_EQUAL
340 last_data.end += 1
341 when Operator::LESS_EQUAL
342 last_data.op = Operator::GREATER
343 last_data.end += 1
344 when Operator::GREATER
345 last_data.op = Operator::LESS_EQUAL
346 last_data.end += 1
347 when Operator::GREATER_EQUAL
348 last_data.op = Operator::LESS
349 last_data.end += 1
350 when Operator::NOT_EQUAL
351 last_data.op = Operator::EQUAL
352 last_data.end += 1
353 else
354 if @data_list.size == 1
355 if last_data.search_indexes.empty?
356 if last_data.op == Operator::EQUAL
357 last_data.op = Operator::NOT_EQUAL
358 last_data.end += 1
359 else
360 return false
361 end
362 else
363 last_data.logical_op = Operator::AND_NOT
364 last_data.flags &= ~ScanInfo::Flags::PUSH
365 @data_list.unshift(create_all_match_data)
366 end
367 else
368 next_code = context.code
369 return false if next_code.nil?
370
371 case next_code.op
372 when Operator::AND
373 context.code_op = Operator::AND_NOT
374 when Operator::AND_NOT
375 context.code_op = Operator::AND
376 when Operator::OR
377 @data_list[-1, 0] = create_all_match_data
378 put_logical_op(Operator::AND_NOT, i)
379 else
380 return false
381 end
382 end
383 end
384
385 true
386 end
387
388 def optimize
389 optimized_data_list = []
390 i = 0
391 n = @data_list.size
392 while i < n
393 data = @data_list[i]
394 next_data = @data_list[i + 1]
395 i += 1
396 if next_data.nil?
397 optimized_data_list << data
398 next
399 end
400 if range_operations?(data, next_data)
401 between_data = create_between_data(data, next_data)
402 optimized_data_list << between_data
403 i += 1
404 next
405 end
406 optimized_data_list << data
407 end
408
409 optimize_by_estimated_size(optimized_data_list)
410 end
411
412 def optimize_by_estimated_size(data_list)
413 return data_list unless Groonga::ORDER_BY_ESTIMATED_SIZE
414
415 start_index = nil
416 data_list.size.times do |i|
417 data = data_list[i]
418 if data.logical_op != Operator::AND
419 if start_index.nil?
420 start_index = i
421 else
422 sort_by_estimated_size!(data_list, start_index...i)
423 start_index = nil
424 end
425 end
426 end
427 unless start_index.nil?
428 sort_by_estimated_size!(data_list, start_index...data_list.size)
429 end
430 data_list
431 end
432
433 def sort_by_estimated_size!(data_list, range)
434 target_data_list = data_list[range]
435 return if target_data_list.size < 2
436
437 start_logical_op = target_data_list.first.logical_op
438 sorted_data_list = target_data_list.sort_by do |data|
439 estimator = ScanInfoDataSizeEstimator.new(data, @table)
440 estimator.estimate
441 end
442 sorted_data_list.each do |sorted_data|
443 sorted_data.logical_op = Operator::AND
444 end
445 sorted_data_list.first.logical_op = start_logical_op
446 data_list[range] = sorted_data_list
447 end
448
449 def range_operations?(data, next_data)
450 return false unless next_data.logical_op == Operator::AND
451
452 op, next_op = data.op, next_data.op
453 return false if !(lower_condition?(op) or lower_condition?(next_op))
454 return false if !(upper_condition?(op) or upper_condition?(next_op))
455
456 return false if data.args[0] != next_data.args[0]
457
458 data_search_indexes = data.search_indexes
459 return false if data_search_indexes.empty?
460
461 data_search_indexes == next_data.search_indexes
462 end
463
464 def lower_condition?(operator)
465 case operator
466 when Operator::GREATER, Operator::GREATER_EQUAL
467 true
468 else
469 false
470 end
471 end
472
473 def upper_condition?(operator)
474 case operator
475 when Operator::LESS, Operator::LESS_EQUAL
476 true
477 else
478 false
479 end
480 end
481
482 def create_all_match_data
483 data = ScanInfoData.new(0)
484 data.end = 0
485 data.flags = ScanInfo::Flags::PUSH
486 data.op = Operator::CALL
487 data.logical_op = Operator::OR
488 data.args = [Context.instance["all_records"]]
489 data.search_indexes = []
490 data
491 end
492
493 def create_between_data(data, next_data)
494 between_data = ScanInfoData.new(data.start)
495 between_data.end = next_data.end + 1
496 between_data.flags = data.flags
497 between_data.op = Operator::CALL
498 between_data.logical_op = data.logical_op
499 between_data.args = create_between_data_args(data, next_data)
500 between_data.search_indexes = data.search_indexes
501 between_data
502 end
503
504 def create_between_data_args(data, next_data)
505 between = Context.instance["between"]
506 @expression.take_object(between)
507 column = data.args[0]
508 op, next_op = data.op, next_data.op
509 if lower_condition?(op)
510 min = data.args[1]
511 min_operator = op
512 max = next_data.args[1]
513 max_operator = next_op
514 else
515 min = next_data.args[1]
516 min_operator = next_op
517 max = data.args[1]
518 max_operator = op
519 end
520 if min_operator == Operator::GREATER
521 min_border = "exclude"
522 else
523 min_border = "include"
524 end
525 if max_operator == Operator::LESS
526 max_border = "exclude"
527 else
528 max_border = "include"
529 end
530
531 [
532 between,
533 column,
534 min,
535 @expression.allocate_constant(min_border),
536 max,
537 @expression.allocate_constant(max_border),
538 ]
539 end
540
541 class BuildContext
542 attr_accessor :status
543 attr_reader :codes
544 attr_reader :n_codes
545 attr_reader :i
546 attr_writer :code_op
547 attr_accessor :data
548 def initialize(expression)
549 @expression = expression
550 @status = :start
551 @current_data = nil
552 @codes = @expression.codes
553 @n_codes = @codes.size
554 @i = 0
555 @code_op = nil
556 @data = nil
557 end
558
559 def have_next?
560 @i < @n_codes
561 end
562
563 def next
564 @i += 1
565 @code_op = nil
566 end
567
568 def code
569 @codes[@i]
570 end
571
572 def code_op
573 @code_op || code.op
574 end
575 end
576 end
577 end