File Coverage

blib/lib/RDF/Query/Plan/Join/NestedLoop.pm
Criterion Covered Total %
statement 101 139 72.6
branch 12 34 35.2
condition n/a
subroutine 16 19 84.2
pod 6 6 100.0
total 135 198 68.1


line stmt bran cond sub pod time code
1             # RDF::Query::Plan::Join::NestedLoop
2             # -----------------------------------------------------------------------------
3              
4             =head1 NAME
5              
6             RDF::Query::Plan::Join::NestedLoop - Executable query plan for nested loop joins.
7              
8             =head1 VERSION
9              
10             This document describes RDF::Query::Plan::Join::NestedLoop version 2.918.
11              
12             =head1 METHODS
13              
14             Beyond the methods documented below, this class inherits methods from the
15             L<RDF::Query::Plan::Join> class.
16              
17             =over 4
18              
19             =cut
20              
21             package RDF::Query::Plan::Join::NestedLoop;
22              
23 35     35   133 use strict;
  35         52  
  35         9020  
24 35     35   188 use warnings;
  35         40  
  35         944  
25 35     35   120 use base qw(RDF::Query::Plan::Join);
  35         41  
  35         12211  
26              
27 35     35   178 use Log::Log4perl;
  35         43  
  35         235  
28 35     35   1340 use Scalar::Util qw(blessed);
  35         46  
  35         1453  
29 35     35   147 use Time::HiRes qw(gettimeofday tv_interval);
  35         37  
  35         337  
30              
31 35     35   3777 use RDF::Query::Error qw(:try);
  35         48  
  35         224  
32 35     35   3545 use RDF::Query::ExecutionContext;
  35         55  
  35         1339  
33              
34             ######################################################################
35              
36             our ($VERSION);
37             BEGIN {
38 35     35   60 $VERSION = '2.918';
39 35         29969 $RDF::Query::Plan::Join::JOIN_CLASSES{ 'RDF::Query::Plan::Join::NestedLoop' }++;
40             }
41              
42             ######################################################################
43              
44             =item C<< new ( $lhs, $rhs, $opt, [ \%logging_keys ] ) >>
45              
46             =cut
47              
48             sub new {
49 31     31 1 44 my $class = shift;
50 31         39 my $lhs = shift;
51 31         41 my $rhs = shift;
52 31         41 my $opt = shift;
53 31         38 my $keys = shift;
54 31 100       97 if ($opt) {
55 11         71 throw RDF::Query::Error::MethodInvocationError -text => "NestedLoop join does not support optional joins (use PushDownNestedLoop instead)";
56             }
57 20         85 my $self = $class->SUPER::new( $lhs, $rhs, $opt );
58            
59 20         40 $self->[0]{logging_keys} = $keys;
60 20         41 return $self;
61             }
62              
63             =item C<< execute ( $execution_context ) >>
64              
65             =cut
66              
67             sub execute ($) {
68 1     1 1 2 my $self = shift;
69 1         2 my $context = shift;
70 1         3 $self->[0]{delegate} = $context->delegate;
71 1 50       6 if ($self->state == $self->OPEN) {
72 0         0 throw RDF::Query::Error::ExecutionError -text => "NestedLoop join plan can't be executed while already open";
73             }
74            
75 1         5 my $l = Log::Log4perl->get_logger("rdf.query.plan.join.nestedloop");
76 1         304 $self->[0]{start_time} = [gettimeofday];
77             # if ($self->optional) {
78             # my (@inner, @outer);
79             # $self->rhs->execute( $context );
80             # while (my $row = $self->rhs->next) {
81             # $l->trace("loading inner row: " . $row);
82             # push(@inner, $row);
83             # }
84             #
85             # my @results;
86             # $self->lhs->execute( $context );
87             # while (my $outer = $self->lhs->next) {
88             # $l->trace("loading outer row: " . $outer);
89             # my $count = 0;
90             # foreach my $inner (@inner) {
91             # if (my $joined = $inner->join( $outer )) {
92             # $count++;
93             # if ($l->is_trace) {
94             # $l->trace("joined bindings: $outer ⋈ $inner");
95             # }
96             # # warn "-> joined\n";
97             # $self->[0]{count}++;
98             # push(@results, $joined);
99             # }
100             # }
101             # if ($count == 0) {
102             # # left-join branch
103             # push(@results, $outer);
104             # }
105             # }
106             #
107             # warn Dumper(\@results);
108             #
109             # $self->[0]{results} = \@results;
110             # } else {
111 1         1 my @inner;
112 1         6 $self->rhs->execute( $context );
113 1         4 while (my $row = $self->rhs->next) {
114 2         5 $l->trace("loading inner row cache with: " . $row);
115 2         43 push(@inner, $row);
116             }
117 1         8 $self->lhs->execute( $context );
118 1 50       4 if ($self->lhs->state == $self->OPEN) {
119 1         3 $self->[0]{inner} = \@inner;
120 1         4 $self->[0]{outer} = $self->lhs;
121 1         2 $self->[0]{inner_index} = 0;
122 1         2 $self->[0]{needs_new_outer} = 1;
123 1         2 $self->[0]{inner_count} = 0;
124 1         3 $self->[0]{count} = 0;
125 1         5 $self->[0]{logger} = $context->logger;
126 1         4 $self->state( $self->OPEN );
127             } else {
128 0         0 warn "no iterator in execute()";
129             }
130             # }
131             # warn '########################################';
132 1         3 $self;
133             }
134              
135             =item C<< next >>
136              
137             =cut
138              
139             sub next {
140 1     1 1 2 my $self = shift;
141 1 50       3 unless ($self->state == $self->OPEN) {
142 0         0 throw RDF::Query::Error::ExecutionError -text => "next() cannot be called on an un-open NestedLoop join";
143             }
144            
145             # if ($self->optional) {
146             # my $result = shift(@{ $self->[0]{results} });
147             # if (my $d = $self->delegate) {
148             # $d->log_result( $self, $result );
149             # }
150             # return $result;
151             # }
152            
153 1         2 my $outer = $self->[0]{outer};
154 1         2 my $inner = $self->[0]{inner};
155            
156 1         3 my $l = Log::Log4perl->get_logger("rdf.query.plan.join.nestedloop");
157 1         11 while (1) {
158 1 50       4 if ($self->[0]{needs_new_outer}) {
159 1         4 $self->[0]{outer_row} = $outer->next;
160 1 50       4 if (ref($self->[0]{outer_row})) {
161 1         3 $self->[0]{needs_new_outer} = 0;
162 1         1 $self->[0]{inner_index} = 0;
163 1         2 $self->[0]{inner_count} = 0;
164             # warn "got new outer row: " . Dumper($self->[0]{outer_row});
165             } else {
166             # we've exhausted the outer iterator. we're now done.
167             # warn "exhausted";
168 0         0 return undef;
169             }
170             }
171            
172 1         4 while ($self->[0]{inner_index} < scalar(@$inner)) {
173 1         2 my $inner_row = $inner->[ $self->[0]{inner_index}++ ];
174             # warn "using inner row: " . Dumper($inner_row);
175 1 50       3 if (my $joined = $inner_row->join( $self->[0]{outer_row} )) {
176 1 50       4 if ($l->is_trace) {
177 0         0 $l->trace("joined bindings: $inner_row ⋈ $self->[0]{outer_row}");
178             }
179             # warn "-> joined\n";
180 1         6 $self->[0]{inner_count}++;
181 1         2 $self->[0]{count}++;
182 1 50       5 if (my $d = $self->delegate) {
183 0         0 $d->log_result( $self, $joined );
184             }
185 1         3 return $joined;
186             } else {
187 0         0 $l->trace("failed to join bindings: $inner_row ⋈ $self->[0]{outer_row}");
188             }
189             }
190            
191 0         0 $self->[0]{needs_new_outer} = 1;
192             }
193             }
194              
195             =item C<< close >>
196              
197             =cut
198              
199             sub close {
200 1     1 1 2 my $self = shift;
201 1 50       3 unless ($self->state == $self->OPEN) {
202 0         0 throw RDF::Query::Error::ExecutionError -text => "close() cannot be called on an un-open NestedLoop join";
203             }
204            
205 1         5 my $l = Log::Log4perl->get_logger("rdf.query.plan.join.nestedloop");
206 1         16 my $t0 = delete $self->[0]{start_time};
207 1         2 my $count = delete $self->[0]{count};
208 1 50       5 if (my $log = delete $self->[0]{logger}) {
209 0         0 $l->debug("logging nestedloop join execution statistics");
210 0         0 my $elapsed = tv_interval ( $t0 );
211 0 0       0 if (my $sparql = $self->logging_keys->{sparql}) {
212 0 0       0 if ($l->is_trace) {
213 0         0 $l->trace("- SPARQL: $sparql");
214 0         0 $l->trace("- elapsed: $elapsed");
215 0         0 $l->trace("- count: $count");
216             }
217 0         0 $log->push_key_value( 'execute_time-nestedloop', $sparql, $elapsed );
218 0         0 $log->push_key_value( 'cardinality-nestedloop', $sparql, $count );
219             }
220 0 0       0 if (my $bf = $self->logging_keys->{bf}) {
221 0 0       0 if ($l->is_trace) {
222 0         0 $l->trace("- bf: $bf");
223             }
224 0         0 $log->push_key_value( 'cardinality-bf-nestedloop', $bf, $count );
225             }
226             }
227 1         3 delete $self->[0]{inner};
228 1         10 delete $self->[0]{outer};
229 1         2 delete $self->[0]{inner_index};
230 1         2 delete $self->[0]{needs_new_outer};
231 1         1 delete $self->[0]{inner_count};
232 1         3 $self->lhs->close();
233 1         3 $self->rhs->close();
234 1         7 $self->SUPER::close();
235             }
236              
237             =item C<< plan_node_name >>
238              
239             Returns the string name of this plan node, suitable for use in serialization.
240              
241             =cut
242              
243             sub plan_node_name {
244 0     0 1   my $self = shift;
245 0 0         my $jtype = $self->optional ? 'leftjoin' : 'join';
246 0           return "nestedloop-$jtype";
247             }
248              
249             =item C<< graph ( $g ) >>
250              
251             =cut
252              
253             sub graph {
254 0     0 1   my $self = shift;
255 0           my $g = shift;
256 0 0         my $jtype = $self->optional ? 'Left Join' : 'Join';
257 0           my ($l, $r) = map { $_->graph( $g ) } ($self->lhs, $self->rhs);
  0            
258 0           $g->add_node( "$self", label => "$jtype (NL)" . $self->graph_labels );
259 0           $g->add_edge( "$self", $l );
260 0           $g->add_edge( "$self", $r );
261 0           return "$self";
262             }
263              
264              
265             package RDF::Query::Plan::Join::NestedLoop::Left;
266              
267 35     35   177 use strict;
  35         45  
  35         648  
268 35     35   115 use warnings;
  35         48  
  35         941  
269 35     35   177 use base qw(RDF::Query::Plan::Join::NestedLoop);
  35         48  
  35         3419  
270              
271             sub new {
272 0     0     my $class = shift;
273 0           my $lhs = shift;
274 0           my $rhs = shift;
275 0           return $class->SUPER::new( $lhs, $rhs, 1 );
276             }
277              
278              
279             1;
280              
281             __END__
282              
283             =back
284              
285             =head1 AUTHOR
286              
287             Gregory Todd Williams <gwilliams@cpan.org>
288              
289             =cut