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]