mbutrovich commented on code in PR #27399:
URL: https://github.com/apache/datafusion/pull/27399#discussion_r4604695567
##########
datafusion/physical-plan/src/joins/hash_join/batched_join_processor.rs:
##########
@@ -0,0 +1,514 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+//! Bounded key lookup, residual filtering, and output for regular joins.
+//!
+//! [`BatchedJoinProcessor`] accepts probe batches and returns final output
batches.
+//! Its caller does not manage row indices, lookup cursors, match bitmaps, or
+//! output buffering. See the type's example for the input/output contract.
+
+use std::sync::Arc;
+
+use arrow::array::{ArrayRef, UInt32Array, UInt64Array};
+use arrow::buffer::{BooleanBuffer, NullBuffer};
+use arrow::datatypes::SchemaRef;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::hash_utils::RandomState;
+use datafusion_common::{
+ JoinSide, JoinType, NullEquality, Result, assert_or_internal_err,
internal_err,
+};
+use datafusion_physical_expr::PhysicalExprRef;
+use datafusion_physical_expr_common::utils::evaluate_expressions_to_arrays;
+
+use super::build::RegularJoinLeftData;
+use super::stream::{count_distinct_sorted_indices, lookup_join_hashmap};
+use crate::coalesce::{LimitedBatchCoalescer, PushBatchStatus};
+use crate::hash_utils::create_hashes;
+use crate::joins::Map;
+use crate::joins::join_hash_map::ProbeOffset;
+use crate::joins::utils::{
+ BuildProbeJoinMetrics, ColumnIndex, JoinFilter, JoinKeyComparator,
+ adjust_indices_by_join_type, apply_join_filter_to_indices,
+ build_batch_empty_build_side, build_batch_from_indices,
matchable_join_keys,
+};
+
+/// Join semantics and output settings for one probe partition.
+pub(super) struct BatchedJoinProcessorConfig {
+ /// Join type, which determines whether to keep unmatched build or probe
rows.
+ pub(super) kind: RegularJoinKind,
+ /// Output schema after projection.
+ pub(super) schema: SchemaRef,
+ /// Probe input schema, used for NULL columns in unmatched build output.
+ pub(super) probe_schema: SchemaRef,
+ /// For each output column, its source side and column index.
+ pub(super) column_indices: Vec<ColumnIndex>,
+ /// Probe equality-key expressions, paired with the build keys by position.
+ pub(super) on_right: Vec<PhysicalExprRef>,
+ /// Hash state shared with build-side insertion.
+ pub(super) random_state: RandomState,
+ /// Whether NULL equality keys can match.
+ pub(super) null_equality: NullEquality,
+ /// Extra `ON` condition checked after key equality, e.g. `l.x > r.y`.
+ /// Its input columns are independent of the output projection.
+ pub(super) filter: Option<JoinFilter>,
+ /// Target batch size for internal buffering, from configuration.
+ pub(super) batch_size: usize,
+ /// Preserve probe order when inserting unmatched rows for a right join.
+ pub(super) right_side_ordered: bool,
+ /// Maximum output rows from this processor; `None` means no limit.
+ pub(super) fetch: Option<usize>,
+}
+
+/// Joins probe batches against the build map.
+///
+/// See the [hash join overview](super) for architecture overview. This is the
middle
+/// layer that:
+///
+/// 1. Looks up raw hash index for matches in chunks of at most `batch_size`.
+/// 2. Applies residual filters and handles unmatched rows for outer joins.
+/// 3. Materializes and coalesces output toward `batch_size`.
+///
+/// # Example
+///
+/// For a full join with one probe partition, build keys `[1, 2, 2]`, and
+/// `batch_size = 1`:
+///
+/// ```text
+/// next_output_batch() -> NeedInput
+/// push_batch([2])
+/// next_output_batch() -> Output([(2, 2)])
+/// next_output_batch() -> Output([(2, 2)])
+/// next_output_batch() -> NeedInput // This batch is done; the stream may
have more.
+///
+/// push_batch([3])
+/// next_output_batch() -> Output([(NULL, 3)])
+/// next_output_batch() -> NeedInput
+///
+/// // The caller reads the probe stream and observes EOF.
+/// finish_probe()
+/// next_output_batch() -> Output([(1, NULL)])
+/// next_output_batch() -> Finished // All output from this processor is
drained.
+/// ```
+pub(super) struct BatchedJoinProcessor {
+ context: BatchedJoinProcessorConfig,
+ metrics: BuildProbeJoinMetrics,
+ build: Arc<RegularJoinLeftData>,
+ /// Input and residual-match state for the current probe batch.
+ probe: Option<ProbeBatch>,
+ phase: Phase,
+ /// Lookup scratch and pair buffers are reused across input batches.
+ hashes_buffer: Vec<u64>,
+ probe_indices_buffer: Vec<u32>,
+ build_indices_buffer: Vec<u64>,
+ /// Coalescer for materialized output. Also handles the fetch/limit pushed
into
+ /// the hash join for an early stop (e.g., for HashJoinExec(fetch=10), the
whole
+ /// execution can stop early after 10 output rows are materialized).
+ output: LimitedBatchCoalescer,
+}
+
+/// Input and lookup progress are separate from successful ON matches:
rejecting
+/// a chunk advances its offset, but does not make those probe rows joined.
+struct ProbeBatch {
+ input: RecordBatch,
+ keys: Vec<ArrayRef>,
+ valid_keys: Option<NullBuffer>,
+ offset: ProbeOffset,
+ key_comparator: Option<JoinKeyComparator>,
+ /// Count each probe row once, even when its equality matches span chunks.
+ last_probe_row_with_key_match: Option<u32>,
+ /// RIGHT/FULL joins retain this across chunks to avoid treating a
previously
+ /// joined probe row as unmatched after later pairs fail the residual
filter.
+ last_probe_row_with_on_match: Option<u32>,
+}
+
+/// The next action for the caller of
[`BatchedJoinProcessor::next_output_batch`].
+pub(super) enum JoinStep {
+ /// A joined output batch is ready.
+ Output(RecordBatch),
+ /// The caller should supply another probe batch or report EOF with
+ /// [`BatchedJoinProcessor::finish_probe`].
+ NeedInput,
+ /// All output is drained, possibly before probe EOF. Stop reading input.
+ Finished,
+}
+
+/// Join work remaining. The output coalescer outlives every phase.
+enum Phase {
+ Probing,
+ /// Only the last probe partition receives this final match snapshot.
+ /// Scan it in chunks without holding the shared bitmap lock.
+ UnmatchedBuild {
+ visited: BooleanBuffer,
+ next_row: usize,
+ empty_probe: RecordBatch,
+ },
+ /// No more rows will be produced; flush and drain buffered output.
+ DrainingOutput,
+ Finished,
+}
+
+impl BatchedJoinProcessor {
+ pub(super) fn new(
+ build: Arc<RegularJoinLeftData>,
+ context: BatchedJoinProcessorConfig,
+ metrics: BuildProbeJoinMetrics,
+ ) -> Self {
+ // An empty map may still have build rows with NULL keys. Left/full
+ // joins must retain those rows for final null extension.
+ let join_type = context.kind.join_type();
+ let can_skip_probe = (build.data.batch.num_rows() == 0
+ && join_type.empty_build_side_produces_empty_result())
+ || (build.data.map.is_empty() &&
join_type.empty_map_produces_empty_result());
+ let phase = if can_skip_probe || context.fetch == Some(0) {
+ Phase::DrainingOutput
+ } else {
+ Phase::Probing
+ };
+ Self {
+ build,
+ probe: None,
+ hashes_buffer: vec![],
+ probe_indices_buffer: vec![],
+ build_indices_buffer: vec![],
+ output: LimitedBatchCoalescer::new(
+ Arc::clone(&context.schema),
+ context.batch_size,
+ context.fetch,
+ ),
+ context,
+ metrics,
+ phase,
+ }
+ }
+
+ /// Accept one probe batch after draining the previous input.
+ ///
+ /// Evaluate keys and hashes once; candidate lookup and output
materialization
+ /// happen incrementally in [`Self::next_output_batch`].
+ pub(super) fn push_batch(&mut self, batch: RecordBatch) -> Result<()> {
+ if !matches!(self.phase, Phase::Probing) {
+ return internal_err!(
+ "BatchedJoinProcessor: cannot push input after probing has
finished"
+ );
+ }
+ assert_or_internal_err!(
+ self.probe.is_none(),
+ "BatchedJoinProcessor: drain the current input before pushing
another batch"
+ );
+ let keys = evaluate_expressions_to_arrays(&self.context.on_right,
&batch)?;
+ let valid_keys = if matches!(&**self.build.data.map, Map::HashMap(_)) {
+ let _timer = self.metrics.join_time.timer();
+ self.hashes_buffer.clear();
+ self.hashes_buffer.resize(batch.num_rows(), 0);
+ create_hashes(&keys, &self.context.random_state, &mut
self.hashes_buffer)?;
+ matchable_join_keys(&keys, self.context.null_equality)
+ } else {
+ None
+ };
+ self.probe = Some(ProbeBatch {
+ input: batch,
+ keys,
+ valid_keys,
+ offset: ProbeOffset::AtRow { row: 0 },
+ key_comparator: None,
+ last_probe_row_with_key_match: None,
+ last_probe_row_with_on_match: None,
+ });
+ Ok(())
+ }
+
+ /// Materialize the next joined batch.
+ ///
+ /// Handles incremental computation and output coalescing toward
`batch_size`
+ /// internally. See the comments on [`BatchedJoinProcessor`] for details.
+ pub(super) fn next_output_batch(&mut self) -> Result<JoinStep> {
+ let join_time = self.metrics.join_time.clone();
+ loop {
+ if let Some(batch) = self.output.next_completed_batch() {
+ return Ok(JoinStep::Output(batch));
+ }
+ let _timer = join_time.timer();
+
+ // Evaluate one final joined batch and put it into the output
coalescer
+ // to combine potentially small batches.
+ let batch = match &mut self.phase {
+ Phase::Probing => {
+ let Some(batch) = self.probe_chunk()? else {
+ return Ok(JoinStep::NeedInput);
+ };
+ batch
+ }
+ Phase::UnmatchedBuild {
+ visited,
+ next_row,
+ empty_probe,
+ } => {
+ let mut indices = Vec::with_capacity(
+ self.context.batch_size.min(visited.len() - *next_row),
+ );
+ while *next_row < visited.len()
+ && indices.len() < self.context.batch_size
+ {
+ if !visited.value(*next_row) {
+ indices.push(*next_row as u64);
+ }
+ *next_row += 1;
+ }
+ self.metrics.input_rows.add(indices.len());
+ if indices.is_empty() {
+ self.phase = Phase::DrainingOutput;
+ continue;
+ }
+ let probe_indices = UInt32Array::new_null(indices.len());
+ build_batch_from_indices(
+ &self.context.schema,
+ &self.build.data.batch,
+ empty_probe,
+ &UInt64Array::from(indices),
+ &probe_indices,
+ &self.context.column_indices,
+ JoinSide::Left,
+ self.context.kind.join_type(),
+ None,
+ )?
+ }
+ Phase::DrainingOutput => {
+ self.output.finish()?;
+ self.phase = Phase::Finished;
+ continue;
+ }
+ Phase::Finished => return Ok(JoinStep::Finished),
+ };
+ // Operator-level limit reached; stop probing.
+ // See the comments on `output` for details.
+ if self.output.push_batch(batch)? == PushBatchStatus::LimitReached
{
+ self.release_probe();
+ self.phase = Phase::DrainingOutput;
+ }
+ }
+ }
+
+ /// Close this partition's probe input after all its batches have been
+ /// drained and the caller has exhausted all probe-side input batches.
+ pub(super) fn finish_probe(&mut self) -> Result<()> {
+ assert_or_internal_err!(
+ matches!(self.phase, Phase::Probing) && self.probe.is_none(),
+ "BatchedJoinProcessor: finish probing only after draining the
current input"
+ );
+ let join_time = self.metrics.join_time.clone();
+ let _timer = join_time.timer();
+ self.release_probe();
+ self.phase = if let Some(visited) = self.build.finish_probe() {
+ self.metrics.input_batches.add(1);
+ Phase::UnmatchedBuild {
+ visited,
+ next_row: 0,
+ empty_probe: RecordBatch::new_empty(Arc::clone(
+ &self.context.probe_schema,
+ )),
+ }
+ } else {
+ Phase::DrainingOutput
+ };
+ Ok(())
+ }
+
+ /// Return a materialized joined batch in the output schema for one probe
chunk.
+ ///
+ /// For an INNER JOIN on `t1.c1 = t2.c1 AND t1.c2 > t2.c2`, with
+ /// `batch_size = 8192`:
+ ///
+ /// 1. Use the index to look up at most 8192 key-equal row pairs (`t1.c1 =
t2.c1`).
+ /// 2. Evaluate the residual filter `t1.c2 > t2.c2`; suppose only 100
pairs pass.
+ /// 3. Materialize those 100 pairs in the final output schema and return
the batch.
+ ///
+ /// For non-inner joins, matched rows will be tracked for final output.
+ ///
+ /// For small output batches, the caller will coalesce them for final
output.
Review Comment:
282a10f rewrote this doc and dropped the return contract that
`next_output_batch` relies on at
[L237-L239](https://github.com/apache/datafusion/blob/ef96c9b538feaf05a3000d15d37e25b1d8ef1830/datafusion/physical-plan/src/joins/hash_join/batched_join_processor.rs#L237-L239):
`None` means the current probe batch is drained, and an empty batch means this
chunk produced no rows. It also no longer says that right and full joins append
the probe rows this chunk proves unmatched (the `adjust_indices_by_join_type`
call at
[L423-L445](https://github.com/apache/datafusion/blob/ef96c9b538feaf05a3000d15d37e25b1d8ef1830/datafusion/physical-plan/src/joins/hash_join/batched_join_processor.rs#L423-L445)).
Could we keep your example and add both back?
```suggestion
/// Look up, filter, and materialize the next chunk of the current probe
batch.
///
/// For an INNER JOIN on `t1.c1 = t2.c1 AND t1.c2 > t2.c2`, with
/// `batch_size = 8192`:
///
/// 1. Use the index to look up at most 8192 key-equal row pairs (`t1.c1
= t2.c1`).
/// 2. Evaluate the residual filter `t1.c2 > t2.c2`; suppose only 100
pairs pass.
/// 3. Materialize those 100 pairs in the final output schema and return
the batch.
///
/// Left and full joins record the surviving build rows for the final
unmatched
/// output. Right and full joins also emit the probe rows this chunk
proves
/// unmatched.
///
/// Returns an empty batch when no row survives, and `None` once the
current
/// probe batch is drained. The caller coalesces small batches.
```
##########
datafusion/physical-plan/src/joins/hash_join/batched_join_processor.rs:
##########
@@ -0,0 +1,514 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+//! Bounded key lookup, residual filtering, and output for regular joins.
+//!
+//! [`BatchedJoinProcessor`] accepts probe batches and returns final output
batches.
+//! Its caller does not manage row indices, lookup cursors, match bitmaps, or
+//! output buffering. See the type's example for the input/output contract.
+
+use std::sync::Arc;
+
+use arrow::array::{ArrayRef, UInt32Array, UInt64Array};
+use arrow::buffer::{BooleanBuffer, NullBuffer};
+use arrow::datatypes::SchemaRef;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::hash_utils::RandomState;
+use datafusion_common::{
+ JoinSide, JoinType, NullEquality, Result, assert_or_internal_err,
internal_err,
+};
+use datafusion_physical_expr::PhysicalExprRef;
+use datafusion_physical_expr_common::utils::evaluate_expressions_to_arrays;
+
+use super::build::RegularJoinLeftData;
+use super::stream::{count_distinct_sorted_indices, lookup_join_hashmap};
+use crate::coalesce::{LimitedBatchCoalescer, PushBatchStatus};
+use crate::hash_utils::create_hashes;
+use crate::joins::Map;
+use crate::joins::join_hash_map::ProbeOffset;
+use crate::joins::utils::{
+ BuildProbeJoinMetrics, ColumnIndex, JoinFilter, JoinKeyComparator,
+ adjust_indices_by_join_type, apply_join_filter_to_indices,
+ build_batch_empty_build_side, build_batch_from_indices,
matchable_join_keys,
+};
+
+/// Join semantics and output settings for one probe partition.
+pub(super) struct BatchedJoinProcessorConfig {
+ /// Join type, which determines whether to keep unmatched build or probe
rows.
+ pub(super) kind: RegularJoinKind,
+ /// Output schema after projection.
+ pub(super) schema: SchemaRef,
+ /// Probe input schema, used for NULL columns in unmatched build output.
+ pub(super) probe_schema: SchemaRef,
+ /// For each output column, its source side and column index.
+ pub(super) column_indices: Vec<ColumnIndex>,
+ /// Probe equality-key expressions, paired with the build keys by position.
+ pub(super) on_right: Vec<PhysicalExprRef>,
+ /// Hash state shared with build-side insertion.
+ pub(super) random_state: RandomState,
+ /// Whether NULL equality keys can match.
+ pub(super) null_equality: NullEquality,
+ /// Extra `ON` condition checked after key equality, e.g. `l.x > r.y`.
+ /// Its input columns are independent of the output projection.
+ pub(super) filter: Option<JoinFilter>,
+ /// Target batch size for internal buffering, from configuration.
+ pub(super) batch_size: usize,
+ /// Preserve probe order when inserting unmatched rows for a right join.
+ pub(super) right_side_ordered: bool,
+ /// Maximum output rows from this processor; `None` means no limit.
+ pub(super) fetch: Option<usize>,
+}
+
+/// Joins probe batches against the build map.
+///
+/// See the [hash join overview](super) for architecture overview. This is the
middle
+/// layer that:
+///
+/// 1. Looks up raw hash index for matches in chunks of at most `batch_size`.
+/// 2. Applies residual filters and handles unmatched rows for outer joins.
+/// 3. Materializes and coalesces output toward `batch_size`.
+///
+/// # Example
+///
+/// For a full join with one probe partition, build keys `[1, 2, 2]`, and
+/// `batch_size = 1`:
+///
+/// ```text
+/// next_output_batch() -> NeedInput
+/// push_batch([2])
+/// next_output_batch() -> Output([(2, 2)])
+/// next_output_batch() -> Output([(2, 2)])
+/// next_output_batch() -> NeedInput // This batch is done; the stream may
have more.
+///
+/// push_batch([3])
+/// next_output_batch() -> Output([(NULL, 3)])
+/// next_output_batch() -> NeedInput
+///
+/// // The caller reads the probe stream and observes EOF.
+/// finish_probe()
+/// next_output_batch() -> Output([(1, NULL)])
+/// next_output_batch() -> Finished // All output from this processor is
drained.
+/// ```
+pub(super) struct BatchedJoinProcessor {
+ context: BatchedJoinProcessorConfig,
+ metrics: BuildProbeJoinMetrics,
+ build: Arc<RegularJoinLeftData>,
+ /// Input and residual-match state for the current probe batch.
+ probe: Option<ProbeBatch>,
+ phase: Phase,
+ /// Lookup scratch and pair buffers are reused across input batches.
+ hashes_buffer: Vec<u64>,
+ probe_indices_buffer: Vec<u32>,
+ build_indices_buffer: Vec<u64>,
+ /// Coalescer for materialized output. Also handles the fetch/limit pushed
into
+ /// the hash join for an early stop (e.g., for HashJoinExec(fetch=10), the
whole
+ /// execution can stop early after 10 output rows are materialized).
+ output: LimitedBatchCoalescer,
+}
+
+/// Input and lookup progress are separate from successful ON matches:
rejecting
+/// a chunk advances its offset, but does not make those probe rows joined.
+struct ProbeBatch {
+ input: RecordBatch,
+ keys: Vec<ArrayRef>,
+ valid_keys: Option<NullBuffer>,
+ offset: ProbeOffset,
+ key_comparator: Option<JoinKeyComparator>,
+ /// Count each probe row once, even when its equality matches span chunks.
+ last_probe_row_with_key_match: Option<u32>,
+ /// RIGHT/FULL joins retain this across chunks to avoid treating a
previously
+ /// joined probe row as unmatched after later pairs fail the residual
filter.
+ last_probe_row_with_on_match: Option<u32>,
+}
+
+/// The next action for the caller of
[`BatchedJoinProcessor::next_output_batch`].
+pub(super) enum JoinStep {
+ /// A joined output batch is ready.
+ Output(RecordBatch),
+ /// The caller should supply another probe batch or report EOF with
+ /// [`BatchedJoinProcessor::finish_probe`].
+ NeedInput,
+ /// All output is drained, possibly before probe EOF. Stop reading input.
+ Finished,
+}
+
+/// Join work remaining. The output coalescer outlives every phase.
+enum Phase {
+ Probing,
+ /// Only the last probe partition receives this final match snapshot.
+ /// Scan it in chunks without holding the shared bitmap lock.
+ UnmatchedBuild {
+ visited: BooleanBuffer,
+ next_row: usize,
+ empty_probe: RecordBatch,
+ },
+ /// No more rows will be produced; flush and drain buffered output.
+ DrainingOutput,
+ Finished,
+}
+
+impl BatchedJoinProcessor {
+ pub(super) fn new(
+ build: Arc<RegularJoinLeftData>,
+ context: BatchedJoinProcessorConfig,
+ metrics: BuildProbeJoinMetrics,
+ ) -> Self {
+ // An empty map may still have build rows with NULL keys. Left/full
+ // joins must retain those rows for final null extension.
+ let join_type = context.kind.join_type();
+ let can_skip_probe = (build.data.batch.num_rows() == 0
+ && join_type.empty_build_side_produces_empty_result())
+ || (build.data.map.is_empty() &&
join_type.empty_map_produces_empty_result());
+ let phase = if can_skip_probe || context.fetch == Some(0) {
+ Phase::DrainingOutput
+ } else {
+ Phase::Probing
+ };
+ Self {
+ build,
+ probe: None,
+ hashes_buffer: vec![],
+ probe_indices_buffer: vec![],
+ build_indices_buffer: vec![],
+ output: LimitedBatchCoalescer::new(
+ Arc::clone(&context.schema),
+ context.batch_size,
+ context.fetch,
+ ),
+ context,
+ metrics,
+ phase,
+ }
+ }
+
+ /// Accept one probe batch after draining the previous input.
+ ///
+ /// Evaluate keys and hashes once; candidate lookup and output
materialization
+ /// happen incrementally in [`Self::next_output_batch`].
+ pub(super) fn push_batch(&mut self, batch: RecordBatch) -> Result<()> {
+ if !matches!(self.phase, Phase::Probing) {
+ return internal_err!(
+ "BatchedJoinProcessor: cannot push input after probing has
finished"
+ );
+ }
+ assert_or_internal_err!(
+ self.probe.is_none(),
+ "BatchedJoinProcessor: drain the current input before pushing
another batch"
+ );
+ let keys = evaluate_expressions_to_arrays(&self.context.on_right,
&batch)?;
+ let valid_keys = if matches!(&**self.build.data.map, Map::HashMap(_)) {
+ let _timer = self.metrics.join_time.timer();
+ self.hashes_buffer.clear();
+ self.hashes_buffer.resize(batch.num_rows(), 0);
+ create_hashes(&keys, &self.context.random_state, &mut
self.hashes_buffer)?;
+ matchable_join_keys(&keys, self.context.null_equality)
+ } else {
+ None
+ };
+ self.probe = Some(ProbeBatch {
+ input: batch,
+ keys,
+ valid_keys,
+ offset: ProbeOffset::AtRow { row: 0 },
+ key_comparator: None,
+ last_probe_row_with_key_match: None,
+ last_probe_row_with_on_match: None,
+ });
+ Ok(())
+ }
+
+ /// Materialize the next joined batch.
+ ///
+ /// Handles incremental computation and output coalescing toward
`batch_size`
+ /// internally. See the comments on [`BatchedJoinProcessor`] for details.
+ pub(super) fn next_output_batch(&mut self) -> Result<JoinStep> {
+ let join_time = self.metrics.join_time.clone();
+ loop {
+ if let Some(batch) = self.output.next_completed_batch() {
+ return Ok(JoinStep::Output(batch));
+ }
+ let _timer = join_time.timer();
+
+ // Evaluate one final joined batch and put it into the output
coalescer
+ // to combine potentially small batches.
+ let batch = match &mut self.phase {
+ Phase::Probing => {
+ let Some(batch) = self.probe_chunk()? else {
+ return Ok(JoinStep::NeedInput);
+ };
+ batch
+ }
+ Phase::UnmatchedBuild {
+ visited,
+ next_row,
+ empty_probe,
+ } => {
+ let mut indices = Vec::with_capacity(
+ self.context.batch_size.min(visited.len() - *next_row),
+ );
+ while *next_row < visited.len()
+ && indices.len() < self.context.batch_size
+ {
+ if !visited.value(*next_row) {
+ indices.push(*next_row as u64);
+ }
+ *next_row += 1;
+ }
+ self.metrics.input_rows.add(indices.len());
+ if indices.is_empty() {
+ self.phase = Phase::DrainingOutput;
+ continue;
+ }
+ let probe_indices = UInt32Array::new_null(indices.len());
+ build_batch_from_indices(
+ &self.context.schema,
+ &self.build.data.batch,
+ empty_probe,
+ &UInt64Array::from(indices),
+ &probe_indices,
+ &self.context.column_indices,
+ JoinSide::Left,
+ self.context.kind.join_type(),
+ None,
+ )?
+ }
+ Phase::DrainingOutput => {
+ self.output.finish()?;
+ self.phase = Phase::Finished;
+ continue;
+ }
+ Phase::Finished => return Ok(JoinStep::Finished),
+ };
+ // Operator-level limit reached; stop probing.
+ // See the comments on `output` for details.
+ if self.output.push_batch(batch)? == PushBatchStatus::LimitReached
{
+ self.release_probe();
+ self.phase = Phase::DrainingOutput;
+ }
+ }
+ }
+
+ /// Close this partition's probe input after all its batches have been
+ /// drained and the caller has exhausted all probe-side input batches.
+ pub(super) fn finish_probe(&mut self) -> Result<()> {
+ assert_or_internal_err!(
+ matches!(self.phase, Phase::Probing) && self.probe.is_none(),
+ "BatchedJoinProcessor: finish probing only after draining the
current input"
+ );
+ let join_time = self.metrics.join_time.clone();
+ let _timer = join_time.timer();
+ self.release_probe();
+ self.phase = if let Some(visited) = self.build.finish_probe() {
+ self.metrics.input_batches.add(1);
+ Phase::UnmatchedBuild {
+ visited,
+ next_row: 0,
+ empty_probe: RecordBatch::new_empty(Arc::clone(
+ &self.context.probe_schema,
+ )),
+ }
+ } else {
+ Phase::DrainingOutput
+ };
+ Ok(())
+ }
+
+ /// Return a materialized joined batch in the output schema for one probe
chunk.
+ ///
+ /// For an INNER JOIN on `t1.c1 = t2.c1 AND t1.c2 > t2.c2`, with
+ /// `batch_size = 8192`:
+ ///
+ /// 1. Use the index to look up at most 8192 key-equal row pairs (`t1.c1 =
t2.c1`).
+ /// 2. Evaluate the residual filter `t1.c2 > t2.c2`; suppose only 100
pairs pass.
+ /// 3. Materialize those 100 pairs in the final output schema and return
the batch.
+ ///
+ /// For non-inner joins, matched rows will be tracked for final output.
+ ///
+ /// For small output batches, the caller will coalesce them for final
output.
+ fn probe_chunk(&mut self) -> Result<Option<RecordBatch>> {
+ let Some(probe) = &mut self.probe else {
+ return Ok(None);
+ };
+ let context = &self.context;
+ let build = &self.build;
+ let input = &probe.input;
+
+ // NULL build keys can leave the map empty even when build rows exist.
+ // Such rows cannot match but are still emitted at build finalization
+ // for left/full joins. Right/full joins preserve this entire probe
batch.
+ if build.data.map.is_empty() {
+ let batch = build_batch_empty_build_side(
+ &context.schema,
+ &build.data.batch,
+ input,
+ &context.column_indices,
+ context.kind.join_type(),
+ )?;
+ self.probe = None;
+ return Ok(Some(batch));
+ }
+
+ // Hash lookup reclaims its scratch internally. ArrayMap returns the
+ // scratch as Arrow arrays, so retain their buffers until
materialization.
+ let mut array_map_buffers = None;
+ let (build_indices, probe_indices, next_offset) = match
&**build.data.map {
+ Map::HashMap(map) => lookup_join_hashmap(
+ map.as_ref(),
+ &build.data.values,
+ &probe.keys,
+ context.null_equality,
+ &self.hashes_buffer,
+ probe.valid_keys.as_ref(),
+ context.batch_size,
+ probe.offset,
+ &mut self.probe_indices_buffer,
+ &mut self.build_indices_buffer,
+ &mut probe.key_comparator,
+ )?,
+ Map::ArrayMap(map) => {
+ let next_offset = map.get_matched_indices_with_limit_offset(
+ &probe.keys,
+ context.batch_size,
+ probe.offset,
+ &mut self.probe_indices_buffer,
+ &mut self.build_indices_buffer,
+ )?;
+ let build_indices: UInt64Array =
+ std::mem::take(&mut self.build_indices_buffer).into();
+ let probe_indices: UInt32Array =
+ std::mem::take(&mut self.probe_indices_buffer).into();
+ array_map_buffers = Some((
+ build_indices.values().clone(),
+ probe_indices.values().clone(),
+ ));
+ (build_indices, probe_indices, next_offset)
+ }
+ };
+
+ // Update metrics `probe_hit_rate` and `avg_fanout``
Review Comment:
This comment has a stray backtick after `avg_fanout`, and it no longer says
why the code subtracts one when the first row equals
`last_probe_row_with_key_match`. That subtraction looks like an off-by-one at
first glance. The legacy copy of this logic explains it at [stream.rs
L205-L206](https://github.com/apache/datafusion/blob/ef96c9b538feaf05a3000d15d37e25b1d8ef1830/datafusion/physical-plan/src/joins/hash_join/stream.rs#L205-L206).
```suggestion
// Pairs are ordered by probe row. A probe row whose matches span a
chunk
// boundary is the last row of the previous chunk and the first row
of this
// one, so `probe_hit_rate` and `avg_fanout` count it only once.
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]