Skip to content

Commit 708ee7e

Browse files
authored
refactor: CrossJoinStream (simplifying, less state, async generator pattern) (apache#24291)
## Which issue does this PR close? - Part of apache#23974 ## Rationale for this change The code for `CrossJoinStream` had an opportunity to be simplified by removing much of the state related to the polling implementation ## What changes are included in this PR? Removed the polling mechanisms in `CrossJoinStream` and the state associated with it, and instead simplified to a simple async-generator pattern of fetching the build side -> while there are batches available on the right, fetch them and perform the join ## Are these changes tested? Yes ## Are there any user-facing changes? No, these are internal to the physical execution of the join
1 parent c7be84a commit 708ee7e

1 file changed

Lines changed: 77 additions & 164 deletions

File tree

‎datafusion/physical-plan/src/joins/cross_join.rs‎

Lines changed: 77 additions & 164 deletions
Original file line numberDiff line numberDiff line change
@@ -18,11 +18,11 @@
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

2324
use 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
};
2828
use crate::execution_plan::{EmissionType, boundedness_from_children};
@@ -32,12 +32,11 @@ use crate::projection::{
3232
physical_to_column_exprs,
3333
};
3434
use crate::statistics::{ChildStats, StatisticsArgs};
35-
use crate::stream::EmptyRecordBatchStream;
35+
use crate::stream::{EmptyRecordBatchStream, ObservedStream, RecordBatchStreamAdapter};
3636
use 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

4342
use arrow::array::{RecordBatch, RecordBatchOptions};
@@ -46,15 +45,15 @@ use arrow::datatypes::{Fields, Schema, SchemaRef};
4645
use datafusion_common::stats::Precision;
4746
use datafusion_common::tree_node::TreeNodeRecursion;
4847
use 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;
5250
use datafusion_execution::memory_pool::{MemoryConsumer, MemoryReservation};
51+
use datafusion_execution::{TaskContext, TryEmitter, async_try_stream};
5352
use datafusion_physical_expr::PhysicalExpr;
5453
use 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

636597
fn 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

Comments
 (0)