2010YOUY01 commented on code in PR #27399:
URL: https://github.com/apache/datafusion/pull/27399#discussion_r4610992524
##########
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:
You're right, I was thinking of it as something else.
In
[3f417b8](https://github.com/apache/datafusion/pull/27399/commits/3f417b8349ef05b9e62b7f97fef616544361f2f9),
I've implemented the same test goal with `slt` -- removing those two lines
will fail the added slt test case
--
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]