Kouhei Sutou
null+****@clear*****
Thu Apr 7 12:46:03 JST 2016
Kouhei Sutou 2016-04-07 12:46:03 +0900 (Thu, 07 Apr 2016) New Revision: 4e32a94e311533390d254b14262a3cf44af314a7 https://github.com/groonga/groonga/commit/4e32a94e311533390d254b14262a3cf44af314a7 Message: expression_rewriter optimizer: rewrite by ExpressionTree Added files: lib/mrb/scripts/expression_tree/constant.rb lib/mrb/scripts/expression_tree/function_call.rb lib/mrb/scripts/expression_tree/variable.rb Removed files: lib/mrb/scripts/expression_tree/value.rb Modified files: lib/mrb/scripts/expression_tree.rb lib/mrb/scripts/expression_tree/binary_operation.rb lib/mrb/scripts/expression_tree/logical_operation.rb lib/mrb/scripts/expression_tree/sources.am lib/mrb/scripts/expression_tree_builder.rb plugins/expression_rewriters/optimizer.rb Modified: lib/mrb/scripts/expression_tree.rb (+3 -1) =================================================================== --- lib/mrb/scripts/expression_tree.rb 2016-04-07 12:44:27 +0900 (d22baa5) +++ lib/mrb/scripts/expression_tree.rb 2016-04-07 12:46:03 +0900 (ccc1ef5) @@ -1,3 +1,5 @@ +require "expression_tree/constant" require "expression_tree/binary_operation" +require "expression_tree/function_call" require "expression_tree/logical_operation" -require "expression_tree/value" +require "expression_tree/variable" Modified: lib/mrb/scripts/expression_tree/binary_operation.rb (+6 -0) =================================================================== --- lib/mrb/scripts/expression_tree/binary_operation.rb 2016-04-07 12:44:27 +0900 (d725d69) +++ lib/mrb/scripts/expression_tree/binary_operation.rb 2016-04-07 12:46:03 +0900 (897c02d) @@ -9,6 +9,12 @@ module Groonga @left = left @right = right end + + def build(expression) + @left.build(expression) + @right.build(expression) + expression.append_operator(@operator, 2) + end end end end Added: lib/mrb/scripts/expression_tree/constant.rb (+14 -0) 100644 =================================================================== --- /dev/null +++ lib/mrb/scripts/expression_tree/constant.rb 2016-04-07 12:46:03 +0900 (8e7e0cc) @@ -0,0 +1,14 @@ +module Groonga + module ExpressionTree + class Constant + attr_reader :value + def initialize(value) + @value = value + end + + def build(expression) + expression.append_constant(@value, Operator::PUSH, 1) + end + end + end +end Added: lib/mrb/scripts/expression_tree/function_call.rb (+20 -0) 100644 =================================================================== --- /dev/null +++ lib/mrb/scripts/expression_tree/function_call.rb 2016-04-07 12:46:03 +0900 (b3bfff6) @@ -0,0 +1,20 @@ +module Groonga + module ExpressionTree + class FunctionCall + attr_reader :procedure + attr_reader :arguments + def initialize(procedure, arguments) + @procedure = procedure + @arguments = arguments + end + + def build(expression) + expression.append_object(@procedure, Operator::PUSH, 1) + @arguments.each do |argument| + argument.build(expression) + end + expression.append_operator(Operator::CALL, @arguments.size) + end + end + end +end Modified: lib/mrb/scripts/expression_tree/logical_operation.rb (+7 -0) =================================================================== --- lib/mrb/scripts/expression_tree/logical_operation.rb 2016-04-07 12:44:27 +0900 (eeacdb0) +++ lib/mrb/scripts/expression_tree/logical_operation.rb 2016-04-07 12:46:03 +0900 (ef95ccb) @@ -7,6 +7,13 @@ module Groonga @operator = operator @nodes = nodes end + + def build(expression) + @nodes.each_with_index do |node, i| + node.build(expression) + expression.append_operator(@operator, 2) if i > 1 + end + end end end end Modified: lib/mrb/scripts/expression_tree/sources.am (+3 -1) =================================================================== --- lib/mrb/scripts/expression_tree/sources.am 2016-04-07 12:44:27 +0900 (184be7c) +++ lib/mrb/scripts/expression_tree/sources.am 2016-04-07 12:46:03 +0900 (6fd10bd) @@ -1,4 +1,6 @@ RUBY_SCRIPT_FILES = \ binary_operation.rb \ + constant.rb \ + function_call.rb \ logical_operation.rb \ - value.rb + variable.rb Deleted: lib/mrb/scripts/expression_tree/value.rb (+0 -10) 100644 =================================================================== --- lib/mrb/scripts/expression_tree/value.rb 2016-04-07 12:44:27 +0900 (df0e211) +++ /dev/null @@ -1,10 +0,0 @@ -module Groonga - module ExpressionTree - class Value - attr_reader :code - def initialize(code) - @code = code - end - end - end -end Added: lib/mrb/scripts/expression_tree/variable.rb (+14 -0) 100644 =================================================================== --- /dev/null +++ lib/mrb/scripts/expression_tree/variable.rb 2016-04-07 12:46:03 +0900 (bc5e523) @@ -0,0 +1,14 @@ +module Groonga + module ExpressionTree + class Variable + attr_reader :column + def initialize(column) + @column = column + end + + def build(expression) + expression.append_object(@column, Operator::GET_VALUE, 1) + end + end + end +end Modified: lib/mrb/scripts/expression_tree_builder.rb (+5 -2) =================================================================== --- lib/mrb/scripts/expression_tree_builder.rb 2016-04-07 12:44:27 +0900 (1cf5da5) +++ lib/mrb/scripts/expression_tree_builder.rb 2016-04-07 12:46:03 +0900 (91ed2f1) @@ -66,8 +66,11 @@ module Groonga left = stack.pop node = ExpressionTree::BinaryOperation.new(code.op, left, right) stack.push(node) - when Operator::GET_VALUE, Operator::PUSH - node = ExpressionTree::Value.new(code) + when Operator::GET_VALUE + node = ExpressionTree::Variable.new(code.value) + stack.push(node) + when Operator::PUSH + node = ExpressionTree::Constant.new(code.value.value) stack.push(node) else raise "unknown operator: #{code.inspect}" Modified: plugins/expression_rewriters/optimizer.rb (+131 -22) =================================================================== --- plugins/expression_rewriters/optimizer.rb 2016-04-07 12:44:27 +0900 (bcc2088) +++ plugins/expression_rewriters/optimizer.rb 2016-04-07 12:46:03 +0900 (ed437ba) @@ -4,34 +4,143 @@ module Groonga register "optimizer" def rewrite - codes =****@expre***** - n_codes = codes.size + builder = ExpressionTreeBuilder.new(@expression) + root_node = builder.build - # (A >= x && A < y) -> between(A, x, "include", y, "exclude") - return nil if n_codes != 7 + optimized_root_node = optimize_node(root_node) - return nil if codes[6].op != Operator::AND + variable = @expression[0] + rewritten = Expression.create(context[variable.domain]) + optimized_root_node.build(rewritten) + rewritten + end - return nil if codes[0].op != Operator::GET_VALUE - return nil if codes[1].op != Operator::PUSH - return nil if codes[2].op != Operator::GREATER_EQUAL + private + def optimize_node(node) + case node + when ExpressionTree::LogicalOperation + optimized_sub_nodes = node.nodes.collect do |sub_node| + optimize_node(sub_node) + end + case node.operator + when Operator::AND + optimized_sub_nodes = optimize_and_sub_nodes(optimized_sub_nodes) + end + ExpressionTree::LogicalOperation.new(node.operator, + optimized_sub_nodes) + when ExpressionTree::BinaryOperation + optimized_left = optimize_node(node.left) + optimized_right = optimize_node(node.right) + if optimized_left.is_a?(ExpressionTree::Constant) and + optimized_right.is_a?(ExpressionTree::Variable) + ExpressionTree::BinaryOperation.new(node.operator, + optimized_right, + optimized_left) + elsif node.left == optimized_left and node.right == optimized_right + node + else + ExpressionTree::BinaryOperation.new(node.operator, + optimized_left, + optimized_right) + end + else + node + end + end - return nil if codes[3].op != Operator::GET_VALUE - return nil if codes[4].op != Operator::PUSH - return nil if codes[5].op != Operator::LESS + def optimize_and_sub_nodes(sub_nodes) + grouped_sub_nodes = sub_nodes.group_by do |sub_node| + case sub_node + when ExpressionTree::BinaryOperation + if sub_node.left.is_a?(ExpressionTree::Variable) + sub_node.left.column + else + nil + end + else + nil + end + end - return nil if codes[3].value != codes[0].value + optimized_nodes = [] + grouped_sub_nodes.each do |column, grouped_nodes| + if column + grouped_nodes = optimize_grouped_nodes(column, grouped_nodes) + end + optimized_nodes.concat(grouped_nodes) + end - variable = @expression[0] - rewritten = Expression.create(context[variable.domain]) - rewritten.append_object(Context.instance["between"], Operator::PUSH, 1) - rewritten.append_object(codes[0].value, Operator::GET_VALUE, 1) - rewritten.append_constant(codes[1].value.value, Operator::PUSH, 1) - rewritten.append_constant("include", Operator::PUSH, 1) - rewritten.append_constant(codes[4].value.value, Operator::PUSH, 1) - rewritten.append_constant("exclude", Operator::PUSH, 1) - rewritten.append_operator(Operator::CALL, 5) - rewritten + optimized_nodes + # TODO + # optimized_nodes.sort_by do |node| + # node.estimate_size + # end + end + + COMPARISON_OPERATORS = [ + Operator::EQUAL, + Operator::NOT_EQUAL, + Operator::LESS, + Operator::GREATER, + Operator::LESS_EQUAL, + Operator::GREATER_EQUAL, + ] + def optimize_grouped_nodes(column, grouped_nodes) + target_nodes, done_nodes = grouped_nodes.partition do |node| + node.is_a?(ExpressionTree::BinaryOperation) and + COMPARISON_OPERATORS.include?(node.operator) and + node.right.is_a?(ExpressionTree::Constant) + end + + # TODO: target_nodes = remove_needless_nodes(target_nodes) + # e.g.: x < 1 && x < 3 -> x < 1: (x < 3) is meaningless + + if target_nodes.size == 2 + between_node = try_optimize_between(column, target_nodes) + if between_node + done_nodes << between_node + else + done_nodes.concat(target_nodes) + end + else + done_nodes.concat(target_nodes) + end + + done_nodes + end + + def try_optimize_between(column, target_nodes) + greater_node = nil + less_node = nil + target_nodes.each do |node| + case node.operator + when Operator::GREATER, Operator::GREATER_EQUAL + greater_node = node + when Operator::LESS, Operator::LESS_EQUAL + less_node = node + end + end + return nil if greater_node.nil? or less_node.nil? + + between = context["between"] + if greater_node.operator == Operator::GREATER + greater_border = "exclude" + else + greater_border = "include" + end + if less_node.operator == Operator::LESS + less_border = "exclude" + else + less_border = "include" + end + arguments = [ + ExpressionTree::Variable.new(column), + greater_node.right, + ExpressionTree::Constant.new(greater_border), + less_node.right, + ExpressionTree::Constant.new(less_border), + ] + ExpressionTree::FunctionCall.new(between, arguments) end end end -------------- next part -------------- HTML����������������������������...ダウンロード
