diff options
Diffstat (limited to 'storage/mroonga/vendor/groonga/plugins/expression_rewriters')
4 files changed, 184 insertions, 0 deletions
diff --git a/storage/mroonga/vendor/groonga/plugins/expression_rewriters/CMakeLists.txt b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/CMakeLists.txt new file mode 100644 index 00000000..aabec442 --- /dev/null +++ b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/CMakeLists.txt @@ -0,0 +1,26 @@ +# Copyright(C) 2015 Brazil +# +# This library is free software; you can redistribute it and/or +# modify it under the terms of the GNU Lesser General Public +# License version 2.1 as published by the Free Software Foundation. +# +# This library is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# Lesser General Public License for more details. +# +# You should have received a copy of the GNU Lesser General Public +# License along with this library; if not, write to the Free Software +# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA + +if(NOT GRN_EMBED) + if(GRN_WITH_MRUBY) + set(GRN_RELATIVE_EXPRESSION_REWRITER_PLUGINS_DIR + "${GRN_RELATIVE_PLUGINS_DIR}/expression_rewriters") + + read_file_list(${CMAKE_CURRENT_SOURCE_DIR}/sources.am + EXPRESSION_REWRITERS) + install(FILES ${EXPRESSION_REWRITERS} + DESTINATION "${GRN_RELATIVE_SEXPRESSION_REWRITER_PLUGINS_DIR}") + endif() +endif() diff --git a/storage/mroonga/vendor/groonga/plugins/expression_rewriters/Makefile.am b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/Makefile.am new file mode 100644 index 00000000..60a032ac --- /dev/null +++ b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/Makefile.am @@ -0,0 +1,9 @@ +EXTRA_DIST = \ + CMakeLists.txt + +if WITH_MRUBY +dist_expression_rewriter_plugins_DATA = \ + $(expression_rewriters) +endif + +include sources.am 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 diff --git a/storage/mroonga/vendor/groonga/plugins/expression_rewriters/sources.am b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/sources.am new file mode 100644 index 00000000..7670bed6 --- /dev/null +++ b/storage/mroonga/vendor/groonga/plugins/expression_rewriters/sources.am @@ -0,0 +1,2 @@ +expression_rewriters = \ + optimizer.rb |