diff options
Diffstat (limited to '')
-rw-r--r-- | storage/mroonga/vendor/groonga/plugins/expression_rewriters/optimizer.rb | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/storage/mroonga/vendor/groonga/plugins/expression_rewriters/optimizer.rb b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/optimizer.rb new file mode 100644 index 00000000..3dfee681 --- /dev/null +++ b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/optimizer.rb @@ -0,0 +1,147 @@ +module Groonga + module ExpressionRewriters + class Optimizer < ExpressionRewriter + register "optimizer" + + def rewrite + builder = ExpressionTreeBuilder.new(@expression) + root_node = builder.build + + variable = @expression[0] + table = context[variable.domain] + optimized_root_node = optimize_node(table, root_node) + + rewritten = Expression.create(table) + optimized_root_node.build(rewritten) + rewritten + end + + private + def optimize_node(table, node) + case node + when ExpressionTree::LogicalOperation + optimized_sub_nodes = node.nodes.collect do |sub_node| + optimize_node(table, sub_node) + end + case node.operator + when Operator::AND + optimized_sub_nodes = + optimize_and_sub_nodes(table, optimized_sub_nodes) + end + ExpressionTree::LogicalOperation.new(node.operator, + optimized_sub_nodes) + when ExpressionTree::BinaryOperation + optimized_left = optimize_node(table, node.left) + optimized_right = optimize_node(table, 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 + + def optimize_and_sub_nodes(table, 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 + + 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 + + optimized_nodes.sort_by do |node| + node.estimate_size(table) + 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 = ExpressionTree::Procedure.new(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 +end |