| 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
| |||||||||||||||||||||||||||||||
| 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")
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")
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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() || []
MC/DC0%0/1
shift() || []
shift()
Truth table50%1/2
A
A= shift()
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
Condition33%1/3
builtin::blessed($model) and $model->does("Attean::API::Model")
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")
| |||||||||||||||||||||||||||||||
| 147 | |||||||||||||||||||||||||||||||
| 148 | 2082 | ▶ | if ($plan->has_cost) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 149 | 1283 | return $plan->cost; | |||||||||||||||||||||||||||||
| 150 | } else { | ||||||||||||||||||||||||||||||
| 151 | 799 | ▶ | if ($model->does('Attean::API::CostPlanner')) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 152 | 799 | ▶ | if (defined(my $cost = $model->cost_for_plan($plan, $self))) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 162 | 0 | ▶ | my @vars = map { $_->value } grep { blessed($_) and $_->does('Attean::API::Variable') } $plan->values; | ||||||||||||||||||||||||||||
|
Condition0%0/3
builtin::blessed($_) && $_->does('Attean::API::Variable')
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')
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 256 | 13 | ▶ | $k = ($k < scalar(@todo)) ? $k : scalar(@todo); # in case we're joining fewer than the batch size | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 263 | 52 | ▶ | next if (scalar(@$o) == scalar(@$s)); # only consider proper, non-empty subsets | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 288 | 60 | ▶ | if ($cost == $min) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
Condition66%2/3
not defined $min_key or $min_key eq $v_key
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
| |||||||||||||||||||||||||||||||
| 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() || []
MC/DC0%0/1
shift() || []
shift()
Truth table50%1/2
A
A= shift()
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
Condition33%1/3
builtin::blessed($model) and $model->does("Attean::API::Model")
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")
| |||||||||||||||||||||||||||||||
| 357 | |||||||||||||||||||||||||||||||
| 358 | 1075 | ▶ | if ($plan->has_cost) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 359 | 796 | return $plan->cost; | |||||||||||||||||||||||||||||
| 360 | } else { | ||||||||||||||||||||||||||||||
| 361 | 279 | ▶ | if ($model->does('Attean::API::CostPlanner')) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 362 | 279 | ▶ | if (defined(my $cost = $model->cost_for_plan($plan, $self))) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 372 | 4 | ▶ | my @vars = map { $_->value } grep { blessed($_) and $_->does('Attean::API::Variable') } $plan->values; | ||||||||||||||||||||||||||||
|
Condition100%3/3
builtin::blessed($_) && $_->does('Attean::API::Variable')
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')
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 467 | 0 | $sum = 20; | |||||||||||||||||||||||||||||
| 468 | } else { | ||||||||||||||||||||||||||||||
| 469 | 4 | $sum = 1; | |||||||||||||||||||||||||||||
| 470 | } | ||||||||||||||||||||||||||||||
| 471 | 4 | ▶ | if ($t->predicate->does('Attean::API::Variable')) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 475 | 0 | $sum += 4; | |||||||||||||||||||||||||||||
| 476 | } else { | ||||||||||||||||||||||||||||||
| 477 | 4 | $sum += 2; | |||||||||||||||||||||||||||||
| 478 | } | ||||||||||||||||||||||||||||||
| 479 | } | ||||||||||||||||||||||||||||||
| 480 | 4 | ▶ | if ($t->object->does('Attean::API::Variable')) { | ||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 498 | 208 | ▶ | if ( all { $_->isa('Attean::Plan::Quad') } @children[0..1]) { | ||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 505 | 64 | ▶ | if ($lnodes[$i]->does('Attean::API::Variable') && $lnodes[$i]->value eq $var) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$lnodes[$i]->does("Attean::API::Variable") and $lnodes[$i]->value eq $var
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
| |||||||||||||||||||||||||||||||
| 506 | 64 | $joinpos{l} = $i; | |||||||||||||||||||||||||||||
| 507 | } | ||||||||||||||||||||||||||||||
| 508 | 64 | ▶ | if ($rnodes[$i]->does('Attean::API::Variable') && $rnodes[$i]->value eq $var) { | ||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$rnodes[$i]->does("Attean::API::Variable") and $rnodes[$i]->value eq $var
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
| |||||||||||||||||||||||||||||||
| 509 | 64 | $joinpos{r} = $i; | |||||||||||||||||||||||||||||
| 510 | } | ||||||||||||||||||||||||||||||
| 511 | 64 | ▶ | last if scalar keys(%joinpos) >= 2; # Perhaps a bit premature optimization | ||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||
| 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__ | ||||||||||||||||||||||||||||||