1818//! Defines the cross join plan for loading the left side of the cross join
1919//! and producing batches in parallel for the right partitions
2020
21- use std:: { sync:: Arc , task:: Poll } ;
21+ use std:: future:: poll_fn;
22+ use std:: sync:: Arc ;
2223
2324use super :: utils:: {
24- BatchSplitter , BatchTransformer , BuildProbeJoinMetrics , NoopBatchTransformer ,
25- OnceAsync , OnceFut , StatefulStreamResult , adjust_right_output_partitioning,
25+ BuildProbeJoinMetrics , OnceAsync , OnceFut , adjust_right_output_partitioning,
2626 reorder_output_after_swap,
2727} ;
2828use crate :: execution_plan:: { EmissionType , boundedness_from_children} ;
@@ -32,12 +32,11 @@ use crate::projection::{
3232 physical_to_column_exprs,
3333} ;
3434use crate :: statistics:: { ChildStats , StatisticsArgs } ;
35- use crate :: stream:: EmptyRecordBatchStream ;
35+ use crate :: stream:: { EmptyRecordBatchStream , ObservedStream , RecordBatchStreamAdapter } ;
3636use crate :: {
3737 ChildrenPropertiesMode , ColumnStatistics , DisplayAs , DisplayFormatType , Distribution ,
38- ExecutionPlan , ExecutionPlanProperties , PlanProperties , RecordBatchStream ,
39- ReplaceChildrenOptions , SendableRecordBatchStream , Statistics , handle_state,
40- validate_child_count,
38+ ExecutionPlan , ExecutionPlanProperties , PlanProperties , ReplaceChildrenOptions ,
39+ SendableRecordBatchStream , Statistics , validate_child_count,
4140} ;
4241
4342use arrow:: array:: { RecordBatch , RecordBatchOptions } ;
@@ -46,15 +45,15 @@ use arrow::datatypes::{Fields, Schema, SchemaRef};
4645use datafusion_common:: stats:: Precision ;
4746use datafusion_common:: tree_node:: TreeNodeRecursion ;
4847use datafusion_common:: {
49- JoinType , Result , ScalarValue , assert_eq_or_internal_err, internal_err ,
48+ DataFusionError , JoinType , Result , ScalarValue , assert_eq_or_internal_err,
5049} ;
51- use datafusion_execution:: TaskContext ;
5250use datafusion_execution:: memory_pool:: { MemoryConsumer , MemoryReservation } ;
51+ use datafusion_execution:: { TaskContext , TryEmitter , async_try_stream} ;
5352use datafusion_physical_expr:: PhysicalExpr ;
5453use datafusion_physical_expr:: equivalence:: join_equivalence_properties;
5554
56- use async_trait :: async_trait ;
57- use futures :: { Stream , StreamExt , TryStreamExt , ready } ;
55+ use futures :: { StreamExt , TryStreamExt } ;
56+ use num_traits :: Zero ;
5857
5958/// Data of the left side that is buffered into memory
6059#[ derive( Debug ) ]
@@ -208,7 +207,7 @@ async fn load_left_input(
208207 let left_schema = stream. schema ( ) ;
209208
210209 // Load all batches and count the rows
211- let ( batches, _metrics , reservation) = stream
210+ let ( batches, metrics , reservation) = stream
212211 . try_fold (
213212 ( Vec :: new ( ) , metrics, reservation) ,
214213 |( mut batches, metrics, reservation) , batch| async {
@@ -226,7 +225,9 @@ async fn load_left_input(
226225 )
227226 . await ?;
228227
228+ let build_timer = metrics. build_time . timer ( ) ;
229229 let merged_batch = concat_batches ( & left_schema, & batches) ?;
230+ build_timer. done ( ) ;
230231
231232 Ok ( JoinLeftData {
232233 merged_batch,
@@ -367,10 +368,6 @@ impl ExecutionPlan for CrossJoinExec {
367368 let reservation =
368369 MemoryConsumer :: new ( "CrossJoinExec" ) . register ( context. memory_pool ( ) ) ;
369370
370- let batch_size = context. session_config ( ) . batch_size ( ) ;
371- let enforce_batch_size_in_joins =
372- context. session_config ( ) . enforce_batch_size_in_joins ( ) ;
373-
374371 let left_fut = self . left_fut . try_once ( || {
375372 let left_stream = self . left . execute ( 0 , context) ?;
376373
@@ -381,29 +378,24 @@ impl ExecutionPlan for CrossJoinExec {
381378 ) )
382379 } ) ?;
383380
384- if enforce_batch_size_in_joins {
385- Ok ( Box :: pin ( CrossJoinStream {
386- schema : Arc :: clone ( & self . schema ) ,
387- left_fut,
388- right : stream,
389- left_index : 0 ,
390- join_metrics,
391- state : CrossJoinStreamState :: WaitBuildSide ,
392- left_data : RecordBatch :: new_empty ( self . left ( ) . schema ( ) ) ,
393- batch_transformer : BatchSplitter :: new ( batch_size) ,
394- } ) )
395- } else {
396- Ok ( Box :: pin ( CrossJoinStream {
397- schema : Arc :: clone ( & self . schema ) ,
398- left_fut,
399- right : stream,
400- left_index : 0 ,
401- join_metrics,
402- state : CrossJoinStreamState :: WaitBuildSide ,
403- left_data : RecordBatch :: new_empty ( self . left ( ) . schema ( ) ) ,
404- batch_transformer : NoopBatchTransformer :: new ( ) ,
405- } ) )
406- }
381+ let mut state = CrossJoinStream {
382+ schema : Arc :: clone ( & self . schema ) ,
383+ left_fut,
384+ right : stream,
385+ join_metrics,
386+ left_data : RecordBatch :: new_empty ( self . left ( ) . schema ( ) ) ,
387+ } ;
388+
389+ let schema = Arc :: clone ( & self . schema ) ;
390+ let baseline_metrics = state. join_metrics . baseline . clone ( ) ;
391+ let stream =
392+ async_try_stream ( |mut emitter| async move { state. join ( & mut emitter) . await } ) ;
393+
394+ Ok ( Box :: pin ( ObservedStream :: new (
395+ Box :: pin ( RecordBatchStreamAdapter :: new ( schema, stream) ) ,
396+ baseline_metrics,
397+ None ,
398+ ) ) )
407399 }
408400
409401 fn child_stats_requests ( & self , partition : Option < usize > ) -> Vec < ChildStats > {
@@ -589,48 +581,17 @@ fn stats_cartesian_product(
589581}
590582
591583/// A stream that issues [RecordBatch]es as they arrive from the right of the join.
592- struct CrossJoinStream < T > {
584+ struct CrossJoinStream {
593585 /// Input schema
594586 schema : Arc < Schema > ,
595587 /// Future for data from left side
596588 left_fut : OnceFut < JoinLeftData > ,
597589 /// Right side stream
598590 right : SendableRecordBatchStream ,
599- /// Current value on the left
600- left_index : usize ,
601591 /// Join execution metrics
602592 join_metrics : BuildProbeJoinMetrics ,
603- /// State of the stream
604- state : CrossJoinStreamState ,
605593 /// Left data (copy of the entire buffered left side)
606594 left_data : RecordBatch ,
607- /// Batch transformer
608- batch_transformer : T ,
609- }
610-
611- impl < T : BatchTransformer + Unpin + Send > RecordBatchStream for CrossJoinStream < T > {
612- fn schema ( & self ) -> SchemaRef {
613- Arc :: clone ( & self . schema )
614- }
615- }
616-
617- /// Represents states of CrossJoinStream
618- enum CrossJoinStreamState {
619- WaitBuildSide ,
620- FetchProbeBatch ,
621- /// Holds the currently processed right side batch
622- BuildBatches ( RecordBatch ) ,
623- }
624-
625- impl CrossJoinStreamState {
626- /// Tries to extract RecordBatch from CrossJoinStreamState enum.
627- /// Returns an error if state is not BuildBatches state.
628- fn try_as_record_batch ( & mut self ) -> Result < & RecordBatch > {
629- match self {
630- CrossJoinStreamState :: BuildBatches ( rb) => Ok ( rb) ,
631- _ => internal_err ! ( "Expected RecordBatch in BuildBatches state" ) ,
632- }
633- }
634595}
635596
636597fn build_batch (
@@ -661,119 +622,71 @@ fn build_batch(
661622 . map_err ( Into :: into)
662623}
663624
664- #[ async_trait]
665- impl < T : BatchTransformer + Unpin + Send > Stream for CrossJoinStream < T > {
666- type Item = Result < RecordBatch > ;
667-
668- fn poll_next (
669- mut self : std:: pin:: Pin < & mut Self > ,
670- cx : & mut std:: task:: Context < ' _ > ,
671- ) -> Poll < Option < Self :: Item > > {
672- self . poll_next_impl ( cx)
673- }
674- }
675-
676- impl < T : BatchTransformer > CrossJoinStream < T > {
677- /// Separate implementation function that unpins the [`CrossJoinStream`] so
678- /// that partial borrows work correctly
679- fn poll_next_impl (
625+ impl CrossJoinStream {
626+ // Collect the left (build) side, then continue processing the right side against it until we have no more rows on the right
627+ async fn join (
680628 & mut self ,
681- cx : & mut std:: task:: Context < ' _ > ,
682- ) -> Poll < Option < Result < RecordBatch > > > {
683- loop {
684- return match self . state {
685- CrossJoinStreamState :: WaitBuildSide => {
686- handle_state ! ( ready!( self . collect_build_side( cx) ) )
687- }
688- CrossJoinStreamState :: FetchProbeBatch => {
689- handle_state ! ( ready!( self . fetch_probe_batch( cx) ) )
690- }
691- CrossJoinStreamState :: BuildBatches ( _) => {
692- let poll = handle_state ! ( self . build_batches( ) ) ;
693- self . join_metrics . baseline . record_poll ( poll)
694- }
695- } ;
629+ emitter : & mut TryEmitter < RecordBatch , DataFusionError > ,
630+ ) -> Result < ( ) > {
631+ if !self . collect_build_side ( ) . await ? {
632+ return Ok ( ( ) ) ;
696633 }
634+
635+ self . process_right_batch ( emitter) . await ?;
636+
637+ Ok ( ( ) )
697638 }
698639
699- /// Collects build (left) side of the join into the state. In case of an empty build batch,
700- /// the execution terminates. Otherwise, the state is updated to fetch probe (right) batch.
701- fn collect_build_side (
702- & mut self ,
703- cx : & mut std:: task:: Context < ' _ > ,
704- ) -> Poll < Result < StatefulStreamResult < Option < RecordBatch > > > > {
705- let build_timer = self . join_metrics . build_time . timer ( ) ;
706- let left_data = match ready ! ( self . left_fut. get( cx) ) {
707- Ok ( left_data) => left_data,
708- Err ( e) => return Poll :: Ready ( Err ( e) ) ,
709- } ;
710- build_timer. done ( ) ;
711-
712- let left_data = left_data. merged_batch . clone ( ) ;
713- let result = if left_data. num_rows ( ) == 0 {
714- StatefulStreamResult :: Ready ( None )
715- } else {
716- self . left_data = left_data;
717- self . state = CrossJoinStreamState :: FetchProbeBatch ;
718- StatefulStreamResult :: Continue
719- } ;
720- Poll :: Ready ( Ok ( result) )
640+ /// Collects build (left) side of the join into the state. In case of an empty build batch, the execution terminates.
641+ /// Returns true if build side was loaded and non-empty
642+ async fn collect_build_side ( & mut self ) -> Result < bool > {
643+ let left_data = poll_fn ( |cx| {
644+ self . left_fut
645+ . get ( cx)
646+ . map ( |res| res. map ( |data| data. merged_batch . clone ( ) ) )
647+ } )
648+ . await ?;
649+
650+ let is_empty = left_data. num_rows ( ) . is_zero ( ) ;
651+ self . left_data = left_data;
652+ Ok ( !is_empty)
721653 }
722654
723- /// Fetches the probe (right) batch, updates the metrics, and save the batch in the state.
724- /// Then, the state is updated to build result batches.
725- fn fetch_probe_batch (
726- & mut self ,
727- cx : & mut std:: task:: Context < ' _ > ,
728- ) -> Poll < Result < StatefulStreamResult < Option < RecordBatch > > > > {
729- self . left_index = 0 ;
730- let right_data = match ready ! ( self . right. poll_next_unpin( cx) ) {
655+ /// Fetches the probe (right) batch, updates the metrics, and returns the batch
656+ async fn fetch_probe_batch ( & mut self ) -> Result < Option < RecordBatch > > {
657+ let right_data = match self . right . next ( ) . await {
731658 Some ( Ok ( right_data) ) => right_data,
732- Some ( Err ( e) ) => return Poll :: Ready ( Err ( e) ) ,
659+ Some ( Err ( e) ) => return Err ( e) ,
733660 None => {
734661 // Release the right (probe) input pipeline's resources.
735662 let right_schema = self . right . schema ( ) ;
736663 self . right = Box :: pin ( EmptyRecordBatchStream :: new ( right_schema) ) ;
737- return Poll :: Ready ( Ok ( StatefulStreamResult :: Ready ( None ) ) ) ;
664+ return Ok ( None ) ;
738665 }
739666 } ;
740667 self . join_metrics . input_batches . add ( 1 ) ;
741668 self . join_metrics . input_rows . add ( right_data. num_rows ( ) ) ;
742669
743- self . state = CrossJoinStreamState :: BuildBatches ( right_data) ;
744- Poll :: Ready ( Ok ( StatefulStreamResult :: Continue ) )
670+ Ok ( Some ( right_data) )
745671 }
746672
747- /// Joins the indexed row of left data with the current probe batch.
748- /// If all the results are produced, the state is set to fetch new probe batch.
749- fn build_batches ( & mut self ) -> Result < StatefulStreamResult < Option < RecordBatch > > > {
750- let right_batch = self . state . try_as_record_batch ( ) ?;
751- if self . left_index < self . left_data . num_rows ( ) {
752- match self . batch_transformer . next ( ) {
753- None => {
754- let join_timer = self . join_metrics . join_time . timer ( ) ;
755- let result = build_batch (
756- self . left_index ,
757- right_batch,
758- & self . left_data ,
759- & self . schema ,
760- ) ;
761- join_timer. done ( ) ;
762-
763- self . batch_transformer . set_batch ( result?) ;
764- }
765- Some ( ( batch, last) ) => {
766- if last {
767- self . left_index += 1 ;
768- }
769-
770- return Ok ( StatefulStreamResult :: Ready ( Some ( batch) ) ) ;
771- }
673+ /// Joins the left data with the current probe batch, using the emitter to emit the resultant batches
674+ async fn process_right_batch (
675+ & mut self ,
676+ emitter : & mut TryEmitter < RecordBatch , DataFusionError > ,
677+ ) -> Result < ( ) > {
678+ while let Some ( right_batch) = self . fetch_probe_batch ( ) . await ? {
679+ for left_index in 0 ..self . left_data . num_rows ( ) {
680+ let join_timer = self . join_metrics . join_time . timer ( ) ;
681+ let result =
682+ build_batch ( left_index, & right_batch, & self . left_data , & self . schema ) ?;
683+ join_timer. done ( ) ;
684+
685+ emitter. emit ( result) . await ;
772686 }
773- } else {
774- self . state = CrossJoinStreamState :: FetchProbeBatch ;
775687 }
776- Ok ( StatefulStreamResult :: Continue )
688+
689+ Ok ( ( ) )
777690 }
778691}
779692
0 commit comments