Kouhei Sutou
null+****@clear*****
Thu Apr 7 15:28:18 JST 2016
Kouhei Sutou 2016-04-07 15:28:18 +0900 (Thu, 07 Apr 2016) New Revision: 138b6d85b30de6c3a8eb6a30134840443db26094 https://github.com/groonga/groonga/commit/138b6d85b30de6c3a8eb6a30134840443db26094 Message: optimizer: support ordering terms by estimated size Added files: test/mruby/suite/expression_rewriter/test_and_order.rb Modified files: lib/mrb/scripts/expression_tree/binary_operation.rb lib/mrb/scripts/expression_tree/logical_operation.rb plugins/expression_rewriters/optimizer.rb Modified: lib/mrb/scripts/expression_tree/binary_operation.rb (+47 -0) =================================================================== --- lib/mrb/scripts/expression_tree/binary_operation.rb 2016-04-07 15:24:59 +0900 (897c02d) +++ lib/mrb/scripts/expression_tree/binary_operation.rb 2016-04-07 15:28:18 +0900 (d59c65c) @@ -15,6 +15,53 @@ module Groonga @right.build(expression) expression.append_operator(@operator, 2) end + + RANGE_OPERATORS = [ + Operator::LESS, + Operator::GREATER, + Operator::LESS_EQUAL, + Operator::GREATER_EQUAL, + ] + def estimate_size(table) + case @operator + when *RANGE_OPERATORS + estimate_size_range(table) + else + table.size + end + end + + private + def estimate_size_range(table) + return table.size unles****@left*****_a?(Variable) + return table.size unles****@right*****_a?(Constant) + + column =****@left***** + value =****@right***** + index_info = column.find_index(@operator) + return table.size if index_info.nil? + + index_column = index_info.index + lexicon = index_column.lexicon + options = {} + case @operator + when Operator::LESS + options[:max] = value + options[:flags] = TableCursorFlags::LT + when Operator::LESS_EQUAL + options[:max] = value + options[:flags] = TableCursorFlags::LE + when Operator::GREATER + options[:min] = value + options[:flags] = TableCursorFlags::GT + when Operator::GREATER_EQUAL + options[:min] = value + options[:flags] = TableCursorFlags::GE + end + TableCursor.open(lexicon, options) do |cursor| + index_column.estimate_size(:lexicon_cursor => cursor) + end + end end end end Modified: lib/mrb/scripts/expression_tree/logical_operation.rb (+14 -0) =================================================================== --- lib/mrb/scripts/expression_tree/logical_operation.rb 2016-04-07 15:24:59 +0900 (26ee7e2) +++ lib/mrb/scripts/expression_tree/logical_operation.rb 2016-04-07 15:28:18 +0900 (e8d494f) @@ -14,6 +14,20 @@ module Groonga expression.append_operator(@operator, 2) if i > 0 end end + + def estimate_size(table) + estimated_sizes =****@nodes***** do |node| + node.estimate_size(table) + end + case @operator + when Operator::AND + estimated_sizes.min + when Operator::OR + estimated_sizes.max + else + estimated_sizes.first + end + end end end end Modified: plugins/expression_rewriters/optimizer.rb (+14 -14) =================================================================== --- plugins/expression_rewriters/optimizer.rb 2016-04-07 15:24:59 +0900 (ed437ba) +++ plugins/expression_rewriters/optimizer.rb 2016-04-07 15:28:18 +0900 (a9ea003) @@ -7,30 +7,32 @@ module Groonga builder = ExpressionTreeBuilder.new(@expression) root_node = builder.build - optimized_root_node = optimize_node(root_node) - variable = @expression[0] - rewritten = Expression.create(context[variable.domain]) + 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(node) + def optimize_node(table, node) case node when ExpressionTree::LogicalOperation optimized_sub_nodes = node.nodes.collect do |sub_node| - optimize_node(sub_node) + optimize_node(table, sub_node) end case node.operator when Operator::AND - optimized_sub_nodes = optimize_and_sub_nodes(optimized_sub_nodes) + 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(node.left) - optimized_right = optimize_node(node.right) + 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, @@ -48,7 +50,7 @@ module Groonga end end - def optimize_and_sub_nodes(sub_nodes) + def optimize_and_sub_nodes(table, sub_nodes) grouped_sub_nodes = sub_nodes.group_by do |sub_node| case sub_node when ExpressionTree::BinaryOperation @@ -70,11 +72,9 @@ module Groonga optimized_nodes.concat(grouped_nodes) end - optimized_nodes - # TODO - # optimized_nodes.sort_by do |node| - # node.estimate_size - # end + optimized_nodes.sort_by do |node| + node.estimate_size(table) + end end COMPARISON_OPERATORS = [ Added: test/mruby/suite/expression_rewriter/test_and_order.rb (+70 -0) 100644 =================================================================== --- /dev/null +++ test/mruby/suite/expression_rewriter/test_and_order.rb 2016-04-07 15:28:18 +0900 (14abd85) @@ -0,0 +1,70 @@ +class TestAndOrder < ExpressionRewriterTestCase + def setup + Groonga::Schema.define do |schema| + schema.create_table("expression_rewriters", + :type => :hash, + :key_type => :short_text) do |table| + table.text("plugin_name") + end + + schema.create_table("Logs") do |table| + table.time("created_at") + table.time("updated_at") + end + + schema.create_table("Timestamps", + :type => :patricia_trie, + :key_type => :time) do |table| + table.index("Logs.created_at") + table.index("Logs.updated_at") + end + end + + @rewriters = Groonga["expression_rewriters"] + @rewriters.add("optimizer", + :plugin_name => "expression_rewriters/optimizer") + + @logs = Groonga["Logs"] + setup_logs + setup_expression(@logs) + end + + def setup_logs + 100.times do + @logs.add(:created_at => "2015-10-01 00:00:00", + :updated_at => "2015-10-01 00:00:00") + end + + 50.times do + @logs.add(:created_at => "2015-10-02 00:00:00", + :updated_at => "2015-10-02 00:00:00") + end + + 10.times do + @logs.add(:created_at => "2015-10-03 00:00:00", + :updated_at => "2015-10-03 00:00:00") + end + end + + def teardown + teardown_expression + end + + def test_range + code = + "created_at <= '2015-10-01 00:00:00' && " + + "updated_at >= '2015-10-03 00:00:00'" + assert_equal(<<-DUMP, dump_rewritten_plan(code)) +[0] + op: <greater_equal> + logical_op: <or> + query: <"2015-10-03 00:00:00"> + expr: <0..2> +[1] + op: <less_equal> + logical_op: <and> + query: <"2015-10-01 00:00:00"> + expr: <3..5> + DUMP + end +end -------------- next part -------------- HTML����������������������������...Télécharger
