Attean/API/QueryPlanner.pm

filter: Statementstmt 91.3% 337 / 369 Branchbran 70.7% 75 / 106 Conditioncond 46.4% 13 / 28 MC/DCmcdc 11.1% 2 / 18 Subroutinesub 100% 40 / 40 Podpod 0.0% 0 / 7 totaltotal 82.2% 467 / 568 CC 78 SCAR 26.5
CC
78
Cov
84%
cost_for_plan
32.8
cost_for_plan
23.2
joins_for_plan_alternatives
16.0
CRAP 14.1
« AtteanX/Serializer/RDFXML.pm ↑ Summary Attean/BindingEqualityTest.pm »
1 50 ▶use v5.14;
Subroutine BEGIN: called CC=1 SCAR=0.0
2 50 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
3  
4 =head1 NAME
5  
6 Attean::API::IDPJoinPlanner - Iterative dynamic programming query planning role
7  
8 =head1 VERSION
9  
10 This document describes Attean::API::IDPJoinPlanner version 0.040
11  
12 =head1 SYNOPSIS
13  
14 extends 'Attean::QueryPlanner';
15 with 'Attean::API::IDPJoinPlanner';
16  
17 =head1 DESCRIPTION
18  
19 The Attean::API::IDPJoinPlanner role provides a query planner the
20 C<< joins_for_plan_alternatives >> method, as well as the cost estimation
21 methods that consume the L<Attean::API::CostPlanner> role.
22  
23 =head1 ATTRIBUTES
24  
25 =over 4
26  
27 =back
28  
29 =head1 METHODS
30  
31 =over 4
32  
33 =cut
34  
35 50 package Attean::API::QueryPlanner 0.040 {
36 50 ▶ use Types::Standard qw(CodeRef Object);
Subroutine BEGIN: called CC=1 SCAR=0.0
37  
38 50 ▶ use Moo::Role;
Subroutine BEGIN: called CC=1 SCAR=0.0
39
40 50 requires 'plan_for_algebra'; # plan_for_algebra($algebra, $model, \@default_graphs)
41 50 has 'request_signer' => (is => 'rw', isa => Object);
42 }
43  
44 50 package Attean::API::CostPlanner 0.040 {
45 50 ▶ use Scalar::Util qw(refaddr);
Subroutine BEGIN: called CC=1 SCAR=0.0
46 50 ▶ use Types::Standard qw(CodeRef);
Subroutine BEGIN: called CC=1 SCAR=0.0
47  
48 50 ▶ use Moo::Role;
Subroutine BEGIN: called CC=1 SCAR=0.0
49 50 ▶ use namespace::clean;
Subroutine BEGIN: called CC=1 SCAR=0.0
50 50 with 'Attean::API::QueryPlanner';
51
52 50 requires 'plans_for_algebra'; # plans_for_algebra($algebra, $model, \@active_graphs, \@default_graphs)
53 50 requires 'cost_for_plan'; # cost_for_plan($plan, $model)
54
55 4579 ▶ before 'cost_for_plan' => sub {
Subroutine __ANON__: called CC=4 SCAR=15.9
56 4579 my $self = shift;
57 4579 my $plan = shift;
58 4579 my $model = shift;
59
60 4579 ▶ if (refaddr($self) == refaddr($model)) {
Branch: 2 branches
BranchTrueFalseTotal
if (builtin::refaddr($self) == builtin::refaddr($model)) { } 0 4579 4579
elsif ($self->does('Attean::API::Model') and $model->does('Attean::API::Model')) { } 0 8080 8080
61 0 Carp::confess "Model and planner objects cannot be the same in call to cost_for_plan";
62 ▶ } elsif ($self->does('Attean::API::Model') and $model->does('Attean::API::Model')) {
Condition66%2/3
$self->does("Attean::API::Model") and $model->does("Attean::API::Model")
!ll&&!rl&&r
350110780
MC/DC0%0/2
$self->does("Attean::API::Model") and $model->does("Attean::API::Model")
$self->does("Attean::API::Model") $model->does("Attean::API::Model")
Truth table66%2/3
A and B
A= $self->does("Attean::API::Model")B= $model->does("Attean::API::Model")
ABresult
0X0
100
111
63 0 Carp::confess "Model and planner objects cannot both consume Attean::API::Model in call to cost_for_plan";
64 }
65 50 };
66
67 41 ▶ sub plan_for_algebra {
Subroutine plan_for_algebra: called CC=1 SCAR=0.0
Pod undocumented
68 41 my $self = shift;
69 41 my $algebra = shift;
70 41 my $model = shift;
71 41 my $default_graphs = shift;
72 41 my $active_graphs = $default_graphs;
73 41 my @plans = sort { $self->cost_for_plan($a, $model) <=> $self->cost_for_plan($b, $model) } $self->plans_for_algebra($algebra, $model, $active_graphs, $default_graphs);
74 41 my $plan = shift(@plans);
75 41 return $plan;
76 }
77 }
78  
79 50 package Attean::API::JoinPlanner 0.040 {
80 50 ▶ use Moo::Role;
Subroutine BEGIN: called CC=1 SCAR=0.0
81 50 requires 'joins_for_plan_alternatives';
82 }
83  
84 50 package Attean::API::NaiveJoinPlanner 0.040 {
85 50 ▶ use Math::Cartesian::Product;
Subroutine BEGIN: called CC=1 SCAR=0.0
86  
87 50 ▶ use Moo::Role;
Subroutine BEGIN: called CC=1 SCAR=0.0
88  
89 50 with 'Attean::API::JoinPlanner';
90 50 with 'Attean::API::QueryPlanner';
91  
92 47 ▶ sub joins_for_plan_alternatives {
Subroutine joins_for_plan_alternatives: called CC=2 SCAR=6.9
Pod undocumented
93 47 my $self = shift;
94 47 my $model = shift;
95 47 my $active_graphs = shift;
96 47 my $default_graphs = shift;
97 47 my $interesting = shift;
98 47 my @args = @_; # each $args[$i] here is an array reference containing alternate plans for element $i
99
100 47 my $plans = shift(@args);
101 47 ▶ while (scalar(@args)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @args) 35 47 82
102 35 my $next = shift(@args);
103 35 my @plans = $self->join_plans($model, $active_graphs, $default_graphs, $plans, $next, 'inner');
104 35 $plans = \@plans;
105 }
106
107 47 my @plans = @$plans;
108 47 return @plans;
109 }
110 }
111  
112 50 package Attean::API::SimpleCostPlanner 0.040 {
113 50 ▶ use Types::Standard qw(Int);
Subroutine BEGIN: called CC=1 SCAR=0.0
114 50 ▶ use Scalar::Util qw(blessed);
Subroutine BEGIN: called CC=1 SCAR=0.0
115  
116 50 ▶ use Moo::Role;
Subroutine BEGIN: called CC=1 SCAR=0.0
117  
118 50 with 'Attean::API::CostPlanner';
119 50 with 'MooX::Log::Any';
120  
121 50 has 'keep' => (is => 'ro', isa => Int, default => 5);
122
123 51 ▶ around 'joins_for_plan_alternatives' => sub {
Subroutine __ANON__: called CC=1 SCAR=0.0
124 51 my $orig = shift;
125 51 my $self = shift;
126 51 my $model = shift;
127 51 my @plans = $orig->($self, $model, @_);
128 51 return $self->prune_plans($model, [], \@plans);
129 50 };
130
131 26 ▶ sub prune_plans {
Subroutine prune_plans: called CC=3 SCAR=11.0
Pod undocumented
132 26 my $self = shift;
133 26 my $model = shift;
134 26 my $interesting = shift;
135 26 ▶ my @plans = @{ shift || [] };
Condition50%1/2
shift() || []
l!l
260
MC/DC0%0/1
shift() || []
shift()
Truth table50%1/2
A
A= shift()
Aresult
11
00
136 50 ▶ no sort 'stable';
Subroutine BEGIN: called CC=1 SCAR=0.0
137 26 my @sorted = map { $_->[1] } sort { $a->[0] <=> $b->[0] } map { [$self->cost_for_plan($_, $model), $_] } @plans;
138
139 26 ▶ return ($self->keep) ? splice(@sorted, 0, $self->keep) : @sorted;
Branch: 1 branch
BranchTrueFalseTotal
$self->keep ? : 26 0 26
140 }
141
142 2082 ▶ sub cost_for_plan {
Subroutine cost_for_plan: called CC=21 SCAR=34.9
Pod undocumented
143 2082 my $self = shift;
144 2082 my $plan = shift;
145 2082 my $model = shift;
146 2082 ▶ Carp::confess "No model given" unless (blessed($model) and $model->does('Attean::API::Model'));
Branch: 1 branch
BranchTrueFalseTotal
unless builtin::blessed($model) and $model->does("Attean::API::Model") 0 2082 2082
Condition33%1/3
builtin::blessed($model) and $model->does("Attean::API::Model")
!ll&&!rl&&r
002082
MC/DC0%0/2
builtin::blessed($model) and $model->does("Attean::API::Model")
builtin::blessed($model) $model->does("Attean::API::Model")
Truth table33%1/3
A and B
A= builtin::blessed($model)B= $model->does("Attean::API::Model")
ABresult
0X0
100
111
147
148 2082 ▶ if ($plan->has_cost) {
Branch: 1 branch
BranchTrueFalseTotal
if ($plan->has_cost) { } 1283 799 2082
149 1283 return $plan->cost;
150 } else {
151 799 ▶ if ($model->does('Attean::API::CostPlanner')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($model->does("Attean::API::CostPlanner")) 799 0 799
152 799 ▶ if (defined(my $cost = $model->cost_for_plan($plan, $self))) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $cost = $model->cost_for_plan($plan, $self))) 27 772 799
153 27 $plan->cost($cost);
154 27 $self->log->info('Model \''.ref($model).'\' did cost planning for \''.ref($plan).'\' and got cost '.$cost);
155 27 return $cost;
156 }
157 }
158  
159 772 my $cost = 1;
160 772 my @children = @{ $plan->children };
161 772 ▶ if ($plan->isa('Attean::Plan::Quad')) {
Branch: 6 branches
BranchTrueFalseTotal
if ($plan->isa('Attean::Plan::Quad')) { } 0 772 772
elsif ($plan->isa('Attean::Plan::Table')) { } 0 772 772
elsif ($plan->isa('Attean::Plan::NestedLoopJoin')) { } 408 364 772
elsif ($plan->isa('Attean::Plan::HashJoin')) { } 356 8 364
elsif ($plan->isa('Attean::Plan::Service')) { } 3 5 8
elsif ($plan->isa('Attean::Plan::Unique')) { } 0 5 5
162 0 ▶ my @vars = map { $_->value } grep { blessed($_) and $_->does('Attean::API::Variable') } $plan->values;
Condition0%0/3
builtin::blessed($_) && $_->does('Attean::API::Variable')
!ll&&!rl&&r
000
MC/DC0%0/2
builtin::blessed($_) && $_->does('Attean::API::Variable')
builtin::blessed($_) $_->does('Attean::API::Variable')
Truth table0%0/3
A && B
A= builtin::blessed($_)B= $_->does('Attean::API::Variable')
ABresult
0X0
100
111
163 0 return scalar(@vars);
164 } elsif ($plan->isa('Attean::Plan::Table')) {
165 0 my $rows = $plan->rows;
166 0 $cost = scalar(@$rows);
167 } elsif ($plan->isa('Attean::Plan::NestedLoopJoin')) {
168 408 my $lcost = $self->cost_for_plan($children[0], $model);
169 408 my $rcost = $self->cost_for_plan($children[1], $model);
170 408 ▶ if ($lcost == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ($lcost == 0) { } 26 382 408
elsif ($rcost == 0) { } 0 382 382
171 26 $cost = $rcost;
172 } elsif ($rcost == 0) {
173 0 $cost = $lcost;
174 } else {
175 382 $cost = $lcost * $rcost;
176 }
177
178 # a cartesian nested loop join is bad, but the algorithm already
179 # has to check for all possible joins, so it's not as bad as
180 # a cartesian hash join (below)
181 408 ▶ $cost *= 10 unless ($plan->children_are_variable_connected);
Branch: 1 branch
BranchTrueFalseTotal
unless $plan->children_are_variable_connected 52 356 408
182 } elsif ($plan->isa('Attean::Plan::HashJoin')) {
183 356 my $joined = $plan->children_are_variable_connected;
184 356 my $lcost = $self->cost_for_plan($children[0], $model);
185 356 my $rcost = $self->cost_for_plan($children[1], $model);
186 356 $cost = ($lcost + $rcost);
187 356 $cost += ($lcost < $rcost); # To let the plan with cheaper rhs win
188 356 ▶ $cost *= 100 unless ($plan->children_are_variable_connected);
Branch: 1 branch
BranchTrueFalseTotal
unless $plan->children_are_variable_connected 0 356 356
189 } elsif ($plan->isa('Attean::Plan::Service')) {
190 3 my $scost = 10;
191 3 foreach my $c (@{ $plan->children }) {
192 0 $scost += $self->cost_for_plan($c, $model);
193 }
194 3 $cost = 5 * $scost;
195 } elsif ($plan->isa('Attean::Plan::Unique')) {
196 0 $cost = 0; # consider a filter on the iterator (like unique) to be essentially free
197 0 foreach my $c (@{ $plan->children }) {
198 0 $cost += $self->cost_for_plan($c, $model);
199 }
200 } else {
201 5 foreach my $c (@{ $plan->children }) {
202 5 $cost += $self->cost_for_plan($c, $model);
203 }
204 }
205
206 772 $plan->cost($cost);
207 772 ▶ if ($self->log->is_trace) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->log->is_trace) { } 0 772 772
208 0 $self->log->trace("Cost $cost estimated for\n".$plan->as_string);
209 } else {
210 772 $self->log->debug('Estimated cost for \''.ref($plan).'\' is '.$cost);
211 }
212 772 return $cost;
213 }
214 }
215 }
216  
217 50 package Attean::API::IDPJoinPlanner 0.040 {
218 50 ▶ use Encode qw(encode);
Subroutine BEGIN: called CC=1 SCAR=0.0
219 50 ▶ use Attean::RDF;
Subroutine BEGIN: called CC=1 SCAR=0.0
220 50 ▶ use LWP::UserAgent;
Subroutine BEGIN: called CC=1 SCAR=0.0
221 50 ▶ use Scalar::Util qw(blessed reftype);
Subroutine BEGIN: called CC=1 SCAR=0.0
222 50 ▶ use List::Util qw(reduce);
Subroutine BEGIN: called CC=1 SCAR=0.0
223 50 ▶ use List::Util qw(all any);
Subroutine BEGIN: called CC=1 SCAR=0.0
224 50 ▶ use Types::Standard qw(Int ConsumerOf InstanceOf);
Subroutine BEGIN: called CC=1 SCAR=0.0
225 50 ▶ use URI::Escape;
Subroutine BEGIN: called CC=1 SCAR=0.0
226 50 ▶ use Algorithm::Combinatorics qw(subsets);
Subroutine BEGIN: called CC=1 SCAR=0.0
227 50 ▶ use List::Util qw(min);
Subroutine BEGIN: called CC=1 SCAR=0.0
228 50 ▶ use Math::Cartesian::Product;
Subroutine BEGIN: called CC=1 SCAR=0.0
229  
230 50 ▶ use Moo::Role;
Subroutine BEGIN: called CC=1 SCAR=0.0
231  
232 50 with 'Attean::API::JoinPlanner';
233 50 with 'Attean::API::SimpleCostPlanner';
234  
235 25 ▶ sub joins_for_plan_alternatives {
Subroutine joins_for_plan_alternatives: called CC=16 SCAR=27.7
Pod undocumented
236 25 my $self = shift;
237 25 my $model = shift;
238 25 my $active_graphs = shift;
239 25 my $default_graphs = shift;
240 25 my $interesting = shift;
241 25 my @args = @_; # each $args[$i] here is an array reference containing alternate plans for element $i
242  
243 25 my $k = 3; # this is the batch size over which to do full dynamic programming
244
245 # initialize $optPlan{$i} to be a set of alternate plans for evaluating element $i
246 25 my %optPlan;
247 25 foreach my $i (0 .. $#args) {
248 39 $optPlan{$i} = [$self->prune_plans($model, $interesting, $args[$i])];
249 }
250
251 25 my @todo = (0 .. $#args); # initialize the todo list to all elements
252 25 my $next_symbol = 'a'; # when we start batching together sub-plans, we'll rename them with letters (e.g. elements 1, 2, and 4 might become 'a', and then 3, 5, and 'a' become 'b')
253
254 # until we've joined all the elements in todo and are left with a set of plans for the join of all elements
255 25 ▶ while (scalar(@todo) > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @todo > 1) 13 25 38
256 13 ▶ $k = ($k < scalar(@todo)) ? $k : scalar(@todo); # in case we're joining fewer than the batch size
Branch: 1 branch
BranchTrueFalseTotal
$k < scalar @todo ? : 0 13 13
257 13 foreach my $i (2 .. $k) { # we've already initialized plans for evaluating single elements; now consider plans for groups of elements (with group sizes 2, 3, ..., $k)
258 14 foreach my $s (subsets(\@todo, $i)) { # pick a subset of size $i of the elements that need to be planned
259 16 my $s_key = join('.', sort @$s);
260 16 $optPlan{$s_key} = [];
261 16 foreach my $o (subsets($s)) { # partition the subset s into two (o and not_o)
262 68 ▶ next if (scalar(@$o) == 0); # only consider proper, non-empty subsets
Branch: 1 branch
BranchTrueFalseTotal
if scalar @$o == 0 16 52 68
263 52 ▶ next if (scalar(@$o) == scalar(@$s)); # only consider proper, non-empty subsets
Branch: 1 branch
BranchTrueFalseTotal
if scalar @$o == scalar @$s 16 36 52
264 36 my $o_key = join('.', sort @$o);
265 36 my %o = map { $_ => 1 } @$o;
266 36 my $not_o_key = join('.', sort grep { not exists $o{$_} } @$s);
267
268 36 my $lhs = $optPlan{$o_key}; # get the plans for evaluating o
269 36 my $rhs = $optPlan{$not_o_key}; # get the plans for evaluating not_o
270
271 # compute and store all the possible ways to evaluate s (o ⋈ not_o)
272 36 push(@{ $optPlan{$s_key} }, $self->join_plans($model, $active_graphs, $default_graphs, $lhs, $rhs, 'inner'));
273 36 $optPlan{$s_key} = [$self->prune_plans($model, $interesting, $optPlan{$s_key})];
274 }
275 }
276 }
277
278 # find the minimum cost plan $p that computes the join over $k elements (the elements end up in @v)
279 13 my %min_plans;
280 13 foreach my $w (subsets(\@todo, $k)) {
281 13 my $w_key = join('.', sort @$w);
282 13 my $plans = $optPlan{$w_key};
283 13 my @costs = map { $self->cost_for_plan($_, $model) => [$_, $w] } @$plans;
284 13 my %costs = @costs;
285 13 my $min = min keys %costs;
286 13 my @min_plans;
287 13 ▶ while (my ($cost, $data) = splice(@costs, 0, 2)) {
Branch: 1 branch
BranchTrueFalseTotal
if (() = splice(@costs, 0, 2)) 60 13 73
288 60 ▶ if ($cost == $min) {
Branch: 1 branch
BranchTrueFalseTotal
if ($cost == $min) 51 9 60
289 51 push(@min_plans, $data);
290 }
291 }
292 13 $min_plans{ $min } = \@min_plans;
293 }
294 13 my $min_cost = min keys %min_plans;
295 13 my $min_plans = $min_plans{$min_cost};
296 13 my @min_plans;
297 my $min_key;
298 13 foreach my $d (@$min_plans) {
299 51 my ($p, $v) = @$d;
300 51 my $v_key = join('.', sort @$v);
301 51 ▶ if (not(defined($min_key)) or $min_key eq $v_key) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $min_key or $min_key eq $v_key) 51 0 51
Condition66%2/3
not defined $min_key or $min_key eq $v_key
l!l&&r!l&&!r
13380
MC/DC0%0/2
not defined $min_key or $min_key eq $v_key
not defined $min_key $min_key eq $v_key
Truth table66%2/3
not(A) or B
A= not defined $min_keyB= $min_key eq $v_key
ABresult
1X1
011
000
302 51 push(@min_plans, $p);
303 51 $min_key = $v_key;
304 }
305 }
306 # my ($p, $v) = @$min_plan;
307 # my $v_key = join('.', sort @$v);
308 # warn "Choosing join for $v_key\n";
309
310 # generate a new symbol $t to stand in for $p, the join over the elements in @v
311 13 my $t = $next_symbol++;
312
313 # remove elements in @v from the todo list, and replace them by the new composite element $t
314 13 $optPlan{$t} = [@min_plans];
315 13 my %v = map { $_ => 1 } split(/[.]/, $min_key);
316 13 push(@todo, $t);
317 13 @todo = grep { not exists $v{$_} } @todo;
318
319 # also remove subsets of @v from the optPlan hash as they are now covered by $optPlan{$t}
320 13 foreach my $o (subsets([keys %v])) {
321 56 my $o_key = join('.', sort @$o);
322 # warn "deleting $o_key\n";
323 56 delete $optPlan{$o_key};
324 }
325 }
326
327 25 my $final_key = join('.', sort @todo);
328 # use Data::Dumper;
329 # warn Dumper($optPlan{$final_key});
330 25 return $self->prune_plans($model, $interesting, $optPlan{$final_key});
331 }
332
333 125 ▶ sub prune_plans {
Subroutine prune_plans: called CC=4 SCAR=14.4
Pod undocumented
334 125 my $self = shift;
335 125 my $model = shift;
336 125 my $interesting = shift;
337 125 ▶ my @plans = @{ shift || [] };
Condition50%1/2
shift() || []
l!l
1250
MC/DC0%0/1
shift() || []
shift()
Truth table50%1/2
A
A= shift()
Aresult
11
00
338 50 ▶ no sort 'stable';
Subroutine BEGIN: called CC=1 SCAR=0.0
339 125 my @sorted = map { $_->[1] } sort { $a->[0] <=> $b->[0] } map { [$self->cost_for_plan($_, $model), $_] } @plans;
340 125 ▶ if ($self->log->is_trace) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->log->is_trace) 0 125 125
341 0 $self->log->trace('============= Plan iteration separator ==============');
342 0 foreach my $plan (@sorted){
343 0 $self->log->trace("Cost: " . $self->cost_for_plan($plan, $model) . " for plan:\n". $plan->as_string);
344 }
345 }
346 125 return splice(@sorted, 0, 5);
347 }
348
349 # Return a cost value for $plan. This value is basically opaque, except
350 # that it will be used to sort plans by cost when determining which is the
351 # cheapest plan to evaluate.
352 1075 ▶ sub cost_for_plan {
Subroutine cost_for_plan: called CC=20 SCAR=31.4
Pod undocumented
353 1075 my $self = shift;
354 1075 my $plan = shift;
355 1075 my $model = shift;
356 1075 ▶ Carp::confess "No model given" unless (blessed($model) and $model->does('Attean::API::Model'));
Branch: 1 branch
BranchTrueFalseTotal
unless builtin::blessed($model) and $model->does("Attean::API::Model") 0 1075 1075
Condition33%1/3
builtin::blessed($model) and $model->does("Attean::API::Model")
!ll&&!rl&&r
001075
MC/DC0%0/2
builtin::blessed($model) and $model->does("Attean::API::Model")
builtin::blessed($model) $model->does("Attean::API::Model")
Truth table33%1/3
A and B
A= builtin::blessed($model)B= $model->does("Attean::API::Model")
ABresult
0X0
100
111
357
358 1075 ▶ if ($plan->has_cost) {
Branch: 1 branch
BranchTrueFalseTotal
if ($plan->has_cost) { } 796 279 1075
359 796 return $plan->cost;
360 } else {
361 279 ▶ if ($model->does('Attean::API::CostPlanner')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($model->does("Attean::API::CostPlanner")) 279 0 279
362 279 ▶ if (defined(my $cost = $model->cost_for_plan($plan, $self))) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $cost = $model->cost_for_plan($plan, $self))) 29 250 279
363 29 $plan->cost($cost);
364 29 $self->log->info('Model \''.ref($model).'\' did cost planning for \''.ref($plan).'\' and got cost '.$cost);
365 29 return $cost;
366 }
367 }
368  
369 250 my $cost = 1;
370 250 my @children = @{ $plan->children };
371 250 ▶ if ($plan->isa('Attean::Plan::Quad')) {
Branch: 6 branches
BranchTrueFalseTotal
if ($plan->isa('Attean::Plan::Quad')) { } 4 246 250
elsif ($plan->isa('Attean::Plan::Table')) { } 0 246 246
elsif ($plan->isa('Attean::Plan::NestedLoopJoin')) { } 124 122 246
elsif ($plan->isa('Attean::Plan::HashJoin')) { } 104 18 122
elsif ($plan->isa('Attean::Plan::Service')) { } 1 17 18
elsif ($plan->isa('Attean::Plan::Unique')) { } 0 17 17
372 4 ▶ my @vars = map { $_->value } grep { blessed($_) and $_->does('Attean::API::Variable') } $plan->values;
Condition100%3/3
builtin::blessed($_) && $_->does('Attean::API::Variable')
!ll&&!rl&&r
484
MC/DC100%2/2
builtin::blessed($_) && $_->does('Attean::API::Variable')
builtin::blessed($_) $_->does('Attean::API::Variable')
Truth table100%3/3
A && B
A= builtin::blessed($_)B= $_->does('Attean::API::Variable')
ABresult
0X0
100
111
373 # This gives a cost increasing at a reasonable pace
374 4 $cost = $self->_hsp_heuristic_triple_sum($plan) * scalar(@vars);
375 } elsif ($plan->isa('Attean::Plan::Table')) {
376 0 my $rows = $plan->rows;
377 0 $cost = scalar(@$rows);
378 } elsif ($plan->isa('Attean::Plan::NestedLoopJoin')) {
379 124 my $lcost = $self->cost_for_plan($children[0], $model);
380 124 my $rcost = $self->cost_for_plan($children[1], $model);
381 124 ▶ if ($lcost == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ($lcost == 0) { } 2 122 124
elsif ($rcost == 0) { } 2 120 122
382 2 $cost = $rcost;
383 } elsif ($rcost == 0) {
384 2 $cost = $lcost;
385 } else {
386 120 my $mult = $self->_penalize_joins($plan);
387 # warn "$mult * ($lcost * $rcost) [$children[0] $children[1]]";
388 120 $cost = $mult * $lcost * $rcost;
389 }
390 } elsif ($plan->isa('Attean::Plan::HashJoin')) {
391 104 my $lcost = $self->cost_for_plan($children[0], $model);
392 104 my $rcost = $self->cost_for_plan($children[1], $model);
393 104 ▶ if ($lcost == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ($lcost == 0) { } 0 104 104
elsif ($rcost == 0) { } 0 104 104
394 0 $cost = $rcost;
395 } elsif ($rcost == 0) {
396 0 $cost = $lcost;
397 } else {
398 104 my $mult = $self->_penalize_joins($plan);
399 # warn "$mult * ($lcost + $rcost)";
400 104 $cost = $mult * ($lcost + $rcost);
401 104 $cost += ($lcost < $rcost); # To let the plan with cheaper rhs win
402 }
403 } elsif ($plan->isa('Attean::Plan::Service')) {
404 1 my $scost = 10;
405 1 foreach my $c (@{ $plan->children }) {
406 0 $scost += $self->cost_for_plan($c, $model);
407 }
408 1 $cost = 5 * $scost;
409 } elsif ($plan->isa('Attean::Plan::Unique')) {
410 0 $cost = 0; # consider a filter on the iterator (like unique) to be essentially free
411 0 foreach my $c (@{ $plan->children }) {
412 0 $cost += $self->cost_for_plan($c, $model);
413 }
414 } else {
415 17 foreach my $c (@{ $plan->children }) {
416 17 $cost += $self->cost_for_plan($c, $model);
417 }
418 }
419
420 # Costs must be integers for comparisons to work in the IDP planning algorithm
421 250 $cost = int($cost);
422 250 $plan->cost($cost);
423 250 return $cost;
424 }
425 }
426
427
428 # The below function finds a number to aid sorting
429 # It takes into account Heuristic 1 and 4 of the HSP paper, see REFERENCES
430 # as well as that it was noted in the text that rdf:type is usually less selective.
431  
432 # By assigning the integers to nodes, depending on whether they are in
433 # triple (subject, predicate, object), variables, rdf:type and
434 # literals, and sum them, they may be sorted. See code for the actual
435 # values used.
436  
437 # Denoting s for bound subject, p for bound predicate, a for rdf:type
438 # as predicate, o for bound object and l for literal object and ? for
439 # variable, we get the following order, most of which are identical to
440 # the HSP:
441  
442 # spl: 6
443 # spo: 8
444 # sao: 10
445 # s?l: 14
446 # s?o: 16
447 # ?pl: 25
448 # ?po: 27
449 # ?ao: 29
450 # sp?: 30
451 # sa?: 32
452 # ??l: 33
453 # ??o: 35
454 # s??: 38
455 # ?p?: 49
456 # ?a?: 51
457 # ???: 57
458  
459 # Note that this number is not intended as an estimate of selectivity,
460 # merely a sorting key, but further research may possibly create such
461 # numbers.
462  
463 4 ▶ sub _hsp_heuristic_triple_sum {
Subroutine _hsp_heuristic_triple_sum: called CC=6 SCAR=22.0
464 4 my ($self, $t) = @_;
465 4 my $sum = 0;
466 4 ▶ if ($t->subject->does('Attean::API::Variable')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($t->subject->does('Attean::API::Variable')) { } 0 4 4
467 0 $sum = 20;
468 } else {
469 4 $sum = 1;
470 }
471 4 ▶ if ($t->predicate->does('Attean::API::Variable')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($t->predicate->does('Attean::API::Variable')) { } 0 4 4
472 0 $sum += 10;
473 } else {
474 4 ▶ if ($t->predicate->equals(iri('http://www.w3.org/1999/02/22-rdf-syntax-ns#type'))) {
Branch: 1 branch
BranchTrueFalseTotal
if ($t->predicate->equals(iri('http://www.w3.org/1999/02/22-rdf-syntax-ns#type'))) { } 0 4 4
475 0 $sum += 4;
476 } else {
477 4 $sum += 2;
478 }
479 }
480 4 ▶ if ($t->object->does('Attean::API::Variable')) {
Branch: 2 branches
BranchTrueFalseTotal
if ($t->object->does('Attean::API::Variable')) { } 4 0 4
elsif ($t->object->does('Attean::API::Literal')) { } 0 0 0
481 4 $sum += 27;
482 } elsif ($t->object->does('Attean::API::Literal')) {
483 0 $sum += 3;
484 } else {
485 0 $sum += 5;
486 }
487 4 return $sum;
488 }
489  
490 # The following method returns a factor used to penalize certain types of joins.
491 # It penalizes cartesian joins heavily, but also uses HSP Heuristic 2 (see REFERENCES)
492 224 ▶ sub _penalize_joins {
Subroutine _penalize_joins: called CC=10 SCAR=23.8
493 224 my ($self, $plan) = @_;
494 224 my $jv = $plan->join_variables;
495 224 my @children = @{ $plan->children };
496 224 my $mult = 1;
497 224 ▶ if (scalar(@$jv)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @$jv) { } 208 16 224
498 208 ▶ if ( all { $_->isa('Attean::Plan::Quad') } @children[0..1]) {
Subroutine __ANON__: called CC=1 SCAR=0.0
Branch: 1 branch
BranchTrueFalseTotal
if (&all(sub { $_->isa("Attean::Plan::Quad"); } , @children[0, 1])) 64 144 208
499 64 my $var = ${$jv}[0]; # We will join on this
500 64 my @lnodes = $children[0]->values;
501 64 my @rnodes = $children[1]->values;
502 # Now, find where the join variables are in the triple patterns
503 64 my %joinpos;
504 64 ▶ for (my $i = 0; $i <= 2; $i++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= 2) 64 0 64
505 64 ▶ if ($lnodes[$i]->does('Attean::API::Variable') && $lnodes[$i]->value eq $var) {
Branch: 1 branch
BranchTrueFalseTotal
if ($lnodes[$i]->does("Attean::API::Variable") and $lnodes[$i]->value eq $var) 64 0 64
Condition33%1/3
$lnodes[$i]->does("Attean::API::Variable") and $lnodes[$i]->value eq $var
!ll&&!rl&&r
0064
MC/DC0%0/2
$lnodes[$i]->does("Attean::API::Variable") and $lnodes[$i]->value eq $var
$lnodes[$i]->does("Attean::API::Variable") $lnodes[$i]->value eq $var
Truth table33%1/3
A and B
A= $lnodes[$i]->does("Attean::API::Variable")B= $lnodes[$i]->value eq $var
ABresult
0X0
100
111
506 64 $joinpos{l} = $i;
507 }
508 64 ▶ if ($rnodes[$i]->does('Attean::API::Variable') && $rnodes[$i]->value eq $var) {
Branch: 1 branch
BranchTrueFalseTotal
if ($rnodes[$i]->does("Attean::API::Variable") and $rnodes[$i]->value eq $var) 64 0 64
Condition33%1/3
$rnodes[$i]->does("Attean::API::Variable") and $rnodes[$i]->value eq $var
!ll&&!rl&&r
0064
MC/DC0%0/2
$rnodes[$i]->does("Attean::API::Variable") and $rnodes[$i]->value eq $var
$rnodes[$i]->does("Attean::API::Variable") $rnodes[$i]->value eq $var
Truth table33%1/3
A and B
A= $rnodes[$i]->does("Attean::API::Variable")B= $rnodes[$i]->value eq $var
ABresult
0X0
100
111
509 64 $joinpos{r} = $i;
510 }
511 64 ▶ last if scalar keys(%joinpos) >= 2; # Perhaps a bit premature optimization
Branch: 1 branch
BranchTrueFalseTotal
if scalar keys %joinpos >= 2 64 0 64
512 }
513 64 my $joinpos = join("", sort values(%joinpos)); # We can now match on this string
514 64 my %costs = ('12' => 1.1, # The penalty numbers come mostly out from thin air
515 '01' => 1.2,
516 '02' => 1.5,
517 '22' => 1.6,
518 '00' => 1.8,
519 '11' => 2);
520 64 ▶ if (exists $costs{$joinpos}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $costs{$joinpos}) 64 0 64
521 64 $mult = $costs{$joinpos};
522 }
523 #warn "Penalty: $mult for quads:\n" . $children[0]->as_string . $children[1]->as_string
524 }
525 } else {
526 16 $mult = 5; # penalize cartesian joins
527 }
528 224 return $mult;
529 }
530 }
531  
532  
533 50 1;
534  
535 __END__
« AtteanX/Serializer/RDFXML.pm ↑ Summary Attean/BindingEqualityTest.pm »