1# RDF::Query::Plan::Join::PushDownNestedLoop 2# ----------------------------------------------------------------------------- 3 4=head1 NAME 5 6RDF::Query::Plan::Join::PushDownNestedLoop - Executable query plan for nested loop joins. 7 8=head1 VERSION 9 10This document describes RDF::Query::Plan::Join::PushDownNestedLoop version 2.918. 11 12=head1 METHODS 13 14Beyond the methods documented below, this class inherits methods from the 15L<RDF::Query::Plan::Join> class. 16 17=over 4 18 19=cut 20 21package RDF::Query::Plan::Join::PushDownNestedLoop; 22 23use strict; 24use warnings; 25use base qw(RDF::Query::Plan::Join); 26use Scalar::Util qw(blessed refaddr); 27use Data::Dumper; 28 29###################################################################### 30 31our ($VERSION); 32BEGIN { 33 $VERSION = '2.918'; 34 $RDF::Query::Plan::Join::JOIN_CLASSES{ 'RDF::Query::Plan::Join::PushDownNestedLoop' }++; 35} 36 37###################################################################### 38 39use RDF::Query::ExecutionContext; 40 41=item C<< new ( $lhs, $rhs, $opt ) >> 42 43=cut 44 45sub new { 46 my $class = shift; 47 my $lhs = shift; 48 my $rhs = shift; 49 50 if ($rhs->isa('RDF::Query::Plan::SubSelect')) { 51 throw RDF::Query::Error::MethodInvocationError -text => "Subselects cannot be the RHS of a PushDownNestedLoop join"; 52 } 53 54 my $opt = shift || 0; 55 if (not($opt) and $rhs->isa('RDF::Query::Plan::Join') and $rhs->optional) { 56 # we can't push down results to an optional pattern because of the 57 # bottom up semantics. see dawg test algebra/manifest#join-scope-1 58 # for example. 59 throw RDF::Query::Error::MethodInvocationError -text => "PushDownNestedLoop join does not support optional patterns as RHS due to bottom-up variable scoping rules (use NestedLoop instead)"; 60 } 61 62 my @aggs = $rhs->subplans_of_type('RDF::Query::Plan::Aggregate'); 63 if (scalar(@aggs)) { 64 throw RDF::Query::Error::MethodInvocationError -text => "PushDownNestedLoop join does not support aggregates in the RHS due to aggregate group fragmentation"; 65 } 66 67 my $self = $class->SUPER::new( $lhs, $rhs, $opt ); 68 return $self; 69} 70 71=item C<< execute ( $execution_context ) >> 72 73=cut 74 75sub execute ($) { 76 my $self = shift; 77 my $context = shift; 78 $self->[0]{delegate} = $context->delegate; 79 if ($self->state == $self->OPEN) { 80 throw RDF::Query::Error::ExecutionError -text => "PushDownNestedLoop join plan can't be executed while already open"; 81 } 82 83 my $l = Log::Log4perl->get_logger("rdf.query.plan.join.pushdownnestedloop"); 84 $l->trace("executing bind join with plans:"); 85 $l->trace($self->lhs->sse); 86 $l->trace($self->rhs->sse); 87 88 $self->lhs->execute( $context ); 89 if ($self->lhs->state == $self->OPEN) { 90 delete $self->[0]{stats}; 91 $self->[0]{context} = $context; 92 $self->[0]{outer} = $self->lhs; 93 $self->[0]{needs_new_outer} = 1; 94 $self->[0]{inner_count} = 0; 95 $self->state( $self->OPEN ); 96 } else { 97 warn "no iterator in execute()"; 98 } 99# warn '########################################'; 100 $self; 101} 102 103=item C<< next >> 104 105=cut 106 107sub next { 108 my $self = shift; 109 unless ($self->state == $self->OPEN) { 110 throw RDF::Query::Error::ExecutionError -text => "next() cannot be called on an un-open PushDownNestedLoop join"; 111 } 112 my $outer = $self->[0]{outer}; 113 my $inner = $self->rhs; 114 my $opt = $self->[3]; 115 116 my $l = Log::Log4perl->get_logger("rdf.query.plan.join.pushdownnestedloop"); 117 while (1) { 118 if ($self->[0]{needs_new_outer}) { 119 $self->[0]{outer_row} = $outer->next; 120 my $outer = $self->[0]{outer_row}; 121 if (ref($outer)) { 122 $self->[0]{stats}{outer_rows}++; 123 my $context = $self->[0]{context}; 124 $self->[0]{needs_new_outer} = 0; 125 $self->[0]{inner_count} = 0; 126 if ($self->[0]{inner}) { 127 $self->[0]{inner}->close(); 128 } 129 my %bound = %{ $context->bound }; 130 @bound{ keys %$outer } = values %$outer; 131 my $copy = $context->copy( bound => \%bound ); 132 $l->trace( "executing inner plan with bound: " . Dumper(\%bound) ); 133 if ($inner->state == $inner->OPEN) { 134 $inner->close(); 135 } 136 $self->[0]{inner} = $inner->execute( $copy ); 137 } else { 138 # we've exhausted the outer iterator. we're now done. 139 $l->trace("exhausted outer plan in bind join"); 140 return undef; 141 } 142 } 143 144 while (defined(my $inner_row = $self->[0]{inner}->next)) { 145 $self->[0]{stats}{inner_rows}++; 146 $l->trace( "using inner row: " . $inner_row->as_string ); 147 if (defined(my $joined = $inner_row->join( $self->[0]{outer_row} ))) { 148 $self->[0]{stats}{results}++; 149 if ($l->is_trace) { 150 $l->trace("joined bindings: $inner_row ⋈ $self->[0]{outer_row}"); 151 } 152# warn "-> joined\n"; 153 $self->[0]{inner_count}++; 154 if (my $d = $self->delegate) { 155 $d->log_result( $self, $joined ); 156 } 157 return $joined; 158 } else { 159 $l->trace("failed to join bindings: $inner_row |><| $self->[0]{outer_row}"); 160 if ($opt) { 161 $l->trace( "--> but operation is OPTIONAL, so returning $self->[0]{outer_row}" ); 162 if (my $d = $self->delegate) { 163 $d->log_result( $self, $self->[0]{outer_row} ); 164 } 165 return $self->[0]{outer_row}; 166 } 167 } 168 } 169 170 $self->[0]{needs_new_outer} = 1; 171 if ($self->[0]{inner}->state == $self->OPEN) { 172 $self->[0]{inner}->close(); 173 } 174 delete $self->[0]{inner}; 175 if ($opt and $self->[0]{inner_count} == 0) { 176 if (my $d = $self->delegate) { 177 $d->log_result( $self, $self->[0]{outer_row} ); 178 } 179 return $self->[0]{outer_row}; 180 } 181 } 182} 183 184=item C<< close >> 185 186=cut 187 188sub close { 189 my $self = shift; 190 unless ($self->state == $self->OPEN) { 191 throw RDF::Query::Error::ExecutionError -text => "close() cannot be called on an un-open PushDownNestedLoop join"; 192 } 193 delete $self->[0]{inner}; 194 delete $self->[0]{outer}; 195 delete $self->[0]{needs_new_outer}; 196 delete $self->[0]{inner_count}; 197 if (blessed($self->lhs) and $self->lhs->state == $self->lhs->OPEN) { 198 $self->lhs->close(); 199 } 200 $self->SUPER::close(); 201} 202 203=item C<< plan_node_name >> 204 205Returns the string name of this plan node, suitable for use in serialization. 206 207=cut 208 209sub plan_node_name { 210 my $self = shift; 211 my $jtype = $self->optional ? 'leftjoin' : 'join'; 212 return "bind-$jtype"; 213} 214 215=item C<< graph ( $g ) >> 216 217=cut 218 219sub graph { 220 my $self = shift; 221 my $g = shift; 222 my $jtype = $self->optional ? 'Left Join' : 'Join'; 223 my ($l, $r) = map { $_->graph( $g ) } ($self->lhs, $self->rhs); 224 $g->add_node( "$self", label => "$jtype (Bind)" . $self->graph_labels ); 225 $g->add_edge( "$self", $l ); 226 $g->add_edge( "$self", $r ); 227 return "$self"; 228} 229 230=item C<< explain >> 231 232Returns a string serialization of the plan appropriate for display on the 233command line. 234 235=cut 236 237sub explain { 238 my $self = shift; 239 my $s = shift; 240 my $count = shift; 241 my $indent = $s x $count; 242 my $type = $self->plan_node_name; 243 my $stats = ''; 244 if ($self->[0]{stats}) { 245 $stats = sprintf(' [%d/%d/%d]', @{ $self->[0]{stats} }{qw(outer_rows inner_rows results)}); 246 } 247 my $string = sprintf("%s%s%s (0x%x)\n", $indent, $type, $stats, refaddr($self)); 248 foreach my $p ($self->plan_node_data) { 249 $string .= $p->explain( $s, $count+1 ); 250 } 251 return $string; 252} 253 254 255package RDF::Query::Plan::Join::PushDownNestedLoop::Left; 256 257use strict; 258use warnings; 259use base qw(RDF::Query::Plan::Join::PushDownNestedLoop); 260 261sub new { 262 my $class = shift; 263 my $lhs = shift; 264 my $rhs = shift; 265 return $class->SUPER::new( $lhs, $rhs, 1 ); 266} 267 2681; 269 270__END__ 271 272=back 273 274=head1 AUTHOR 275 276 Gregory Todd Williams <gwilliams@cpan.org> 277 278=cut 279