1
|
|
|
# frozen_string_literal: true |
2
|
|
|
|
3
|
1 |
|
module NoSE |
4
|
1 |
|
module Search |
5
|
|
|
# A container for results from a schema search |
6
|
1 |
|
class Results |
7
|
1 |
|
attr_reader :cost_model |
8
|
1 |
|
attr_accessor :enumerated_indexes, :indexes, :total_size, :total_cost, |
9
|
|
|
:workload, :update_plans, :plans, |
10
|
|
|
:revision, :time, :command, :by_id_graph |
11
|
|
|
|
12
|
1 |
|
def initialize(problem = nil, by_id_graph = false) |
13
|
15 |
|
@problem = problem |
14
|
15 |
|
return if problem.nil? |
15
|
11 |
|
@by_id_graph = by_id_graph |
16
|
|
|
|
17
|
|
|
# Find the indexes the ILP says the query should use |
18
|
50 |
|
@query_indexes = Hash.new { |h, k| h[k] = Set.new } |
19
|
11 |
|
@problem.query_vars.each do |index, query_vars| |
20
|
456 |
|
query_vars.each do |query, var| |
21
|
32973 |
|
next unless var.value |
22
|
41 |
|
@query_indexes[query].add index |
23
|
|
|
end |
24
|
|
|
end |
25
|
|
|
end |
26
|
|
|
|
27
|
|
|
# Provide access to the underlying model in the workload |
28
|
|
|
# @return [Model] |
29
|
1 |
|
def model |
30
|
13 |
|
@workload.nil? ? @model : @workload.model |
31
|
|
|
end |
32
|
|
|
|
33
|
|
|
# Assign the model to the workload if it exists, otherwise store it |
34
|
|
|
# @return [void] |
35
|
1 |
|
def model=(model) |
36
|
4 |
|
if @workload.nil? |
37
|
4 |
|
@model = model |
38
|
|
|
else |
39
|
|
|
@workload.instance_variable_set :@model, model |
40
|
|
|
end |
41
|
|
|
end |
42
|
|
|
|
43
|
|
|
# After setting the cost model, recalculate the cost |
44
|
|
|
# @return [void] |
45
|
1 |
|
def cost_model=(new_cost_model) |
46
|
13 |
|
recalculate_cost new_cost_model |
47
|
13 |
|
@cost_model = new_cost_model |
48
|
|
|
end |
49
|
|
|
|
50
|
|
|
# After setting the cost model, recalculate the cost |
51
|
|
|
# @return [void] |
52
|
1 |
|
def recalculate_cost(new_cost_model = nil) |
|
|
|
|
53
|
14 |
|
new_cost_model = @cost_model if new_cost_model.nil? |
54
|
|
|
|
55
|
14 |
|
(@plans || []).each do |plan| |
56
|
72 |
|
plan.each { |s| s.calculate_cost new_cost_model } |
57
|
|
|
end |
58
|
14 |
|
(@update_plans || []).each do |plan| |
59
|
16 |
|
plan.update_steps.each { |s| s.calculate_cost new_cost_model } |
60
|
8 |
|
plan.query_plans.each do |query_plan| |
61
|
8 |
|
query_plan.each { |s| s.calculate_cost new_cost_model } |
62
|
|
|
end |
63
|
|
|
end |
64
|
|
|
|
65
|
|
|
# Recalculate the total |
66
|
14 |
|
query_cost = (@plans || []).sum_by do |plan| |
67
|
35 |
|
plan.cost * @workload.statement_weights[plan.query] |
68
|
|
|
end |
69
|
14 |
|
update_cost = (@update_plans || []).sum_by do |plan| |
70
|
8 |
|
plan.cost * @workload.statement_weights[plan.statement] |
71
|
|
|
end |
72
|
14 |
|
@total_cost = query_cost + update_cost |
73
|
|
|
end |
74
|
|
|
|
75
|
|
|
# Validate that the results of the search are consistent |
76
|
|
|
# @return [void] |
77
|
1 |
|
def validate |
78
|
11 |
|
validate_indexes |
79
|
10 |
|
validate_query_indexes @plans |
80
|
10 |
|
validate_update_indexes |
81
|
|
|
|
82
|
10 |
|
planned_queries = plans.map(&:query).to_set |
83
|
|
|
fail InvalidResultsException unless \ |
84
|
10 |
|
(@workload.queries.to_set - planned_queries).empty? |
85
|
10 |
|
validate_query_plans @plans |
86
|
|
|
|
87
|
10 |
|
validate_update_plans |
88
|
10 |
|
validate_objective |
89
|
|
|
|
90
|
8 |
|
freeze |
91
|
|
|
end |
92
|
|
|
|
93
|
|
|
# Set the query plans which should be used based on the entire tree |
94
|
|
|
# @return [void] |
95
|
1 |
|
def plans_from_trees(trees) |
96
|
8 |
|
@plans = trees.map do |tree| |
97
|
|
|
# Exclude support queries since they will be in update plans |
98
|
459 |
|
query = tree.query |
99
|
459 |
|
next if query.is_a?(SupportQuery) |
100
|
|
|
|
101
|
27 |
|
select_plan tree |
102
|
|
|
end.compact |
103
|
|
|
end |
104
|
|
|
|
105
|
|
|
# Select the single query plan from a tree of plans |
106
|
|
|
# @return [Plans::QueryPlan] |
107
|
|
|
# @raise [InvalidResultsException] |
108
|
1 |
|
def select_plan(tree) |
109
|
39 |
|
query = tree.query |
110
|
39 |
|
plan = tree.find do |tree_plan| |
111
|
239 |
|
tree_plan.indexes.to_set == @query_indexes[query] |
112
|
|
|
end |
113
|
39 |
|
plan.instance_variable_set :@workload, @workload |
114
|
|
|
|
115
|
39 |
|
fail InvalidResultsException if plan.nil? |
116
|
39 |
|
plan |
117
|
|
|
end |
118
|
|
|
|
119
|
1 |
|
private |
120
|
|
|
|
121
|
|
|
# Check that the indexes selected were actually enumerated |
122
|
|
|
# @return [void] |
123
|
1 |
|
def validate_indexes |
124
|
|
|
# We may not have enumerated ID graphs |
125
|
11 |
|
check_indexes = @indexes.dup |
126
|
|
|
@indexes.each do |index| |
127
|
|
|
check_indexes.delete index.to_id_graph |
128
|
11 |
|
end if @by_id_graph |
129
|
|
|
|
130
|
1 |
|
fail InvalidResultsException unless \ |
131
|
11 |
|
(check_indexes - @enumerated_indexes).empty? |
132
|
|
|
end |
133
|
|
|
|
134
|
|
|
# Ensure we only have necessary update plans which use available indexes |
135
|
|
|
# @return [void] |
136
|
1 |
|
def validate_update_indexes |
137
|
10 |
|
@update_plans.each do |plan| |
138
|
25 |
|
validate_query_indexes plan.query_plans |
139
|
25 |
|
valid_plan = @indexes.include?(plan.index) |
140
|
25 |
|
fail InvalidResultsException unless valid_plan |
141
|
|
|
end |
142
|
|
|
end |
143
|
|
|
|
144
|
|
|
# Check that the objective function has the expected value |
145
|
|
|
# @return [void] |
146
|
1 |
|
def validate_objective |
|
|
|
|
147
|
10 |
|
if @problem.objective_type == Objective::COST |
148
|
1 |
|
query_cost = @plans.reduce 0 do |sum, plan| |
149
|
|
|
sum + @workload.statement_weights[plan.query] * plan.cost |
150
|
|
|
end |
151
|
1 |
|
update_cost = @update_plans.reduce 0 do |sum, plan| |
152
|
|
|
sum + @workload.statement_weights[plan.statement] * plan.cost |
153
|
|
|
end |
154
|
1 |
|
cost = query_cost + update_cost |
155
|
|
|
|
156
|
1 |
|
fail InvalidResultsException unless (cost - @total_cost).abs < 0.001 |
157
|
9 |
|
elsif @problem.objective_type == Objective::SPACE |
158
|
9 |
|
size = @indexes.sum_by(&:size) |
159
|
9 |
|
fail InvalidResultsException unless (size - @total_size).abs < 0.001 |
160
|
|
|
end |
161
|
|
|
end |
162
|
|
|
|
163
|
|
|
# Ensure that all the query plans use valid indexes |
164
|
|
|
# @return [void] |
165
|
1 |
|
def validate_query_indexes(plans) |
166
|
35 |
|
plans.each do |plan| |
167
|
39 |
|
plan.each do |step| |
168
|
41 |
|
valid_plan = !step.is_a?(Plans::IndexLookupPlanStep) || |
169
|
|
|
@indexes.include?(step.index) |
170
|
41 |
|
fail InvalidResultsException unless valid_plan |
171
|
|
|
end |
172
|
|
|
end |
173
|
|
|
end |
174
|
|
|
|
175
|
|
|
# Validate the query plans from the original workload |
176
|
|
|
# @return [void] |
177
|
1 |
|
def validate_query_plans(plans) |
178
|
|
|
# Check that these indexes are actually used by the query |
179
|
35 |
|
plans.each do |plan| |
180
|
|
|
fail InvalidResultsException unless \ |
181
|
39 |
|
plan.indexes.to_set == @query_indexes[plan.query] |
182
|
|
|
end |
183
|
|
|
end |
184
|
|
|
|
185
|
|
|
# Validate the support query plans for each update |
186
|
|
|
# @return [void] |
187
|
1 |
|
def validate_update_plans |
188
|
10 |
|
@update_plans.each do |plan| |
189
|
25 |
|
plan.instance_variable_set :@workload, @workload |
190
|
|
|
|
191
|
25 |
|
validate_query_plans plan.query_plans |
192
|
|
|
end |
193
|
|
|
end |
194
|
|
|
end |
195
|
|
|
|
196
|
|
|
# Thrown when a search produces invalid results |
197
|
1 |
|
class InvalidResultsException < StandardError |
198
|
|
|
end |
199
|
|
|
end |
200
|
|
|
end |
201
|
|
|
|