1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
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
|
