jayzhan211 commented on code in PR #27399:
URL: https://github.com/apache/datafusion/pull/27399#discussion_r4586178724


##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -1831,6 +1868,85 @@ impl ExecutionPlan for HashJoinExec {
             .map(|(_, right_expr)| Arc::clone(right_expr))
             .collect::<Vec<_>>();
 
+        // For the `RegularHashJoinStream` path, prepare build-side data and 
construct
+        // the final stream.
+        if let Some(kind) = regular_join {
+            let left_fut = match (&self.prepared_build, self.mode) {
+                (Some(prepared), _) => {
+                    let prepared = Arc::clone(prepared);
+                    self.regular_left_fut.try_once(|| {
+                        Ok(async move { Ok(prepared.regular_probe_data()) })
+                    })?
+                }
+                (None, PartitionMode::CollectLeft) => {
+                    self.regular_left_fut.try_once(|| {
+                        let future = collect(0, right_partitions)?;
+                        Ok(async move { 
Ok(future.await?.into_regular_left_data()) })
+                    })?
+                }
+                (None, PartitionMode::Partitioned) => {
+                    let future = collect(partition, 1)?;
+                    OnceFut::new(
+                        async move { 
Ok(future.await?.into_regular_left_data()) },
+                    )
+                }
+                (None, PartitionMode::Auto) => {
+                    return plan_err!(
+                        "PartitionMode::Auto must be resolved before execution"
+                    );

Review Comment:
   Optional: the legacy branch below reports this case as "Invalid 
HashJoinExec, unsupported PartitionMode Auto in execute()". Using the same 
message keeps the error independent of the migration flag.
   
   ```suggestion
                       return plan_err!(
                           "Invalid HashJoinExec, unsupported PartitionMode 
{:?} in execute()",
                           PartitionMode::Auto
                       );
   ```



##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -1749,72 +1805,53 @@ impl ExecutionPlan for HashJoinExec {
             .flatten()
             .flatten();
 
-        let left_fut = match (&self.prepared_build, self.mode) {
-            (Some(prepared), _) => {
-                // Public join fields can change after builder validation.
-                prepared.validate(self)?;
-                let prepared = Arc::clone(prepared);
-                self.left_fut.try_once(|| {
-                    Ok(async move { Ok(prepared.probe_data(right_partitions)) 
})
-                })?
-            }
-            (None, PartitionMode::CollectLeft) => self.left_fut.try_once(|| {
-                let left_stream = self.left.execute(0, Arc::clone(&context))?;
-
-                let reservation =
-                    
MemoryConsumer::new("HashJoinInput").register(context.memory_pool());
-
-                Ok(collect_left_input(
-                    self.random_state.random_state().clone(),
-                    left_stream,
-                    on_left.clone(),
-                    join_metrics.clone(),
-                    reservation,
-                    need_produce_result_in_final(self.join_type),
-                    right_partitions,
-                    enable_dynamic_filter_pushdown,
-                    Arc::clone(context.session_config().options()),
-                    self.null_equality,
-                    not_in,
-                    array_map_created_count,
-                    BuildMode::Ordinary,
-                ))
-            })?,
-            (None, PartitionMode::Partitioned) => {
-                let left_stream = self.left.execute(partition, 
Arc::clone(&context))?;
-
-                let reservation =
-                    MemoryConsumer::new(format!("HashJoinInput[{partition}]"))
-                        .register(context.memory_pool());
-                OnceFut::new(collect_left_input(
-                    self.random_state.random_state().clone(),
-                    left_stream,
-                    on_left.clone(),
-                    join_metrics.clone(),
-                    reservation,
-                    need_produce_result_in_final(self.join_type),
-                    1,
-                    enable_dynamic_filter_pushdown,
-                    Arc::clone(context.session_config().options()),
-                    self.null_equality,
-                    not_in,
-                    array_map_created_count,
-                    BuildMode::Ordinary,
-                ))
-            }
-            (None, PartitionMode::Auto) => {
-                return plan_err!(
-                    "Invalid HashJoinExec, unsupported PartitionMode {:?} in 
execute()",
-                    PartitionMode::Auto
-                );
-            }
+        // See the comments on `enable_migration_hash_join` for details.
+        let use_regular = if let Some(prepared) = &self.prepared_build {
+            // Public join fields can change after builder validation.
+            prepared.validate(self)?;
+            prepared.is_regular()
+        } else {
+            context
+                .session_config()
+                .options()
+                .execution
+                .enable_migration_hash_join
+        };

Review Comment:
   Optional cleanup: if this uses the consumer's config for prepared builds 
too, `enable_migration_hash_join = false` also works as the bug workaround for 
prepared consumers. Today a long-lived prepared build keeps whichever path was 
set at preparation. Both left-data constructors only borrow the same 
`Arc<JoinBuildData>`, so nothing depends on the choice being made at 
preparation. This removes `PreparedHashJoinBuild::regular`, `is_regular`, and 
the doc lines about it, and all join tests pass with the flag's default set to 
either value.
   
   ```diff
   -        let use_regular = if let Some(prepared) = &self.prepared_build {
   +        if let Some(prepared) = &self.prepared_build {
                // Public join fields can change after builder validation.
                prepared.validate(self)?;
   -            prepared.is_regular()
   -        } else {
   -            context
   -                .session_config()
   -                .options()
   -                .execution
   -                .enable_migration_hash_join
   -        };
   +        }
   +        let use_regular = context
   +            .session_config()
   +            .options()
   +            .execution
   +            .enable_migration_hash_join;
   ```



##########
datafusion/physical-plan/src/joins/hash_join/batched_join_processor.rs:
##########
@@ -0,0 +1,512 @@
+// 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::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(())
+    }
+
+    /// Join another portion of the current probe batch against the build 
batch.
+    ///
+    /// 1. Collect up to `batch_size` key-equal row-index pairs
+    ///    in `build_indices` and `probe_indices`.
+    /// 2. Apply the join filter, record successful matches,
+    ///    and add probe rows now known to be unmatched for right/full joins.
+    /// 3. Materialize those pairs into a batch. [`Self::next_output_batch`]
+    ///    coalesces small batches of surviving pairs and unmatched rows.
+    ///
+    /// One call may cover part of one probe row's matches or several probe 
rows.
+    /// An empty batch means this chunk produced no output; `None` means the
+    /// current probe batch is drained.
+    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)
+            }
+        };
+
+        // Equality pairs are ordered by probe row. A row continuing from the
+        // previous chunk contributes fanout, but not another probe hit.
+        let mut matched_probe_rows = 0;
+        for &row in probe_indices.values().iter() {
+            if probe.last_probe_row_with_key_match != Some(row) {
+                matched_probe_rows += 1;
+                probe.last_probe_row_with_key_match = Some(row);
+            }
+        }

Review Comment:
   This loop makes the new path slower than the legacy one on `hj` (sf1, same 
binary, toggling `enable_migration_hash_join`): Q24 is 1.06x and Q26 is 1.12x, 
while Q17, which the flag doesn't touch, stays at 1.01x. A profile puts the 
extra time here: the field is read and written through `&mut` on every row. The 
legacy path's `count_distinct_sorted_indices` plus a first/last boundary fix 
brings Q24 to 1.00x and Q26 to 1.04x, and 
`join_probe_metrics_count_each_probe_row_once` still passes. This also needs 
`count_distinct_sorted_indices` in `stream.rs` made `pub(super)` and imported 
here.
   
   ```suggestion
           // Equality pairs are ordered by probe row. A row continuing from the
           // previous chunk contributes fanout, but not another probe hit.
           let mut matched_probe_rows = 
count_distinct_sorted_indices(&probe_indices);
           if let (Some(&first), Some(&last)) = (
               probe_indices.values().first(),
               probe_indices.values().last(),
           ) {
               if Some(first) == probe.last_probe_row_with_key_match {
                   matched_probe_rows -= 1;
               }
               probe.last_probe_row_with_key_match = Some(last);
           }
   ```
   
   <details><summary>Per-query numbers (new/legacy, median of 60 runs)</summary>
   
   | query | PR | with this change |
   |---|---|---|
   | Q24 single hot bucket, string key | 1.063 | 1.000 |
   | Q26 Partitioned, dense keys | 1.119 | 1.040 |
   | Q9 | 0.995 | 1.019 |
   | Q13 | 0.964 | 0.953 |
   | Q17 RightSemi (control) | 1.007 | 1.021 |
   
   </details>



##########
datafusion/physical-plan/src/joins/hash_join/batched_join_processor.rs:
##########
@@ -0,0 +1,512 @@
+// 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::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;
+            }

Review Comment:
   Optional: no test covers this early stop. If `release_probe()` and the move 
to `DrainingOutput` are removed, every test still passes, but the join reads 
the whole probe input after `fetch` rows. The test below makes the second probe 
batch an error, so it fails without the early stop for all four join types.
   
   <details><summary>Test for exec.rs tests module</summary>
   
   ```rs
   /// Reaching `fetch` stops reading the probe side: the second probe batch
   /// is an error that must never be polled.
   #[rstest]
   #[tokio::test]
   async fn join_fetch_stops_reading_probe(
       #[values(JoinType::Inner, JoinType::Left, JoinType::Right, 
JoinType::Full)]
       join_type: JoinType,
   ) -> Result<()> {
       let left = build_table(
           ("a1", &vec![1, 2, 3]),
           ("b1", &vec![1, 2, 3]),
           ("c1", &vec![7, 8, 9]),
       );
       let right_batch = build_table_i32(
           ("a2", &vec![1, 2, 3]),
           ("b1", &vec![1, 2, 3]),
           ("c2", &vec![4, 5, 6]),
       );
       let right_schema = right_batch.schema();
       let on = vec![(
           Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
           Arc::new(Column::new_with_schema("b1", &right_schema)?) as _,
       )];
       let right: Arc<dyn ExecutionPlan> = Arc::new(
           MockExec::new(
               vec![Ok(right_batch), exec_err!("probe read after fetch")],
               right_schema,
           )
           .with_use_task(false)
           .with_unknown_statistics(),
       );
       let join = HashJoinExecBuilder::new(left, right, on, join_type)
           .with_partition_mode(PartitionMode::CollectLeft)
           .with_fetch(Some(2))
           .build()?;
       let batches =
           common::collect(join.execute(0, prepare_task_ctx(8192, 
false))?).await?;
       assert_eq!(batches.iter().map(|b| b.num_rows()).sum::<usize>(), 2);
       Ok(())
   }
   ```
   
   </details>



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