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]

Reply via email to