2010YOUY01 commented on code in PR #27399:
URL: https://github.com/apache/datafusion/pull/27399#discussion_r4583205906


##########
datafusion/physical-plan/src/joins/hash_join/regular_join.rs:
##########
@@ -0,0 +1,179 @@
+// 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
+
+//! State machine implementation for the regular hash join execution path. 
(Inner/
+//! Left/Right/Full join types are regular joins.)
+//!
+//! HashJoinExec is getting incrementally migrated to separate streams; see 
the issue
+//! for details:
+//! - <https://github.com/apache/datafusion/issues/26361>
+
+use std::sync::Arc;
+
+use arrow::datatypes::SchemaRef;
+use arrow::record_batch::RecordBatch;
+use datafusion_common::{DataFusionError, Result, internal_err};
+use datafusion_execution::{TryEmitter, async_try_stream};
+use futures::TryStreamExt;
+
+use super::batched_join_processor::{
+    BatchedJoinProcessor, BatchedJoinProcessorConfig, JoinStep,
+};
+use super::build::HashJoinBuild;
+use crate::SendableRecordBatchStream;
+use crate::joins::utils::BuildProbeJoinMetrics;
+use crate::metrics::BaselineMetrics;
+use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
+
+/// Implementation for regular (Inner/Left/Right/Full) hash joins.
+///
+/// See the [`super`] documentation for the high-level architecture.
+/// [`Self::into_stream`] is the entry point for execution.
+pub(super) struct RegularHashJoinStream {
+    schema: SchemaRef,
+    metrics: BaselineMetrics,
+    stage: ExecutionStage,
+}
+
+/// Execution stages described in [`RegularHashJoinStream::into_stream`].
+enum ExecutionStage {
+    Building(Building),
+    Probing(Probing),
+    Outputting(BatchedJoinProcessor),
+}
+
+struct Building {
+    build: HashJoinBuild,
+    probe: SendableRecordBatchStream,
+    config: BatchedJoinProcessorConfig,
+    metrics: BuildProbeJoinMetrics,
+}
+
+struct Probing {
+    probe: SendableRecordBatchStream,
+    metrics: BuildProbeJoinMetrics,
+    processor: BatchedJoinProcessor,
+}
+
+impl RegularHashJoinStream {
+    pub(super) fn new(
+        build: HashJoinBuild,
+        probe: SendableRecordBatchStream,
+        config: BatchedJoinProcessorConfig,
+        metrics: BuildProbeJoinMetrics,
+    ) -> Self {
+        Self {
+            schema: Arc::clone(&config.schema),
+            metrics: metrics.baseline.clone(),
+            stage: ExecutionStage::Building(Building {
+                build,
+                probe,
+                config,
+                metrics,
+            }),
+        }
+    }
+
+    /// Entry point for the regular hash join execution stages.
+    ///
+    /// ```text
+    /// Building --> Probing --> Outputting --> end
+    /// ```
+    ///
+    /// # Stages
+    ///
+    /// - Building: Load the build-side data, and handle cross-partition 
synchronization.
+    ///   See [`HashJoinBuild`] for different physical strategies.
+    /// - Probing: Join probe batches with build data incrementally, until the
+    ///   probe-side input is exhausted.
+    /// - Outputting: Drain buffered output, then emit unmatched build rows for
+    ///   left/full joins.
+    ///
+    /// # Transition edges
+    ///
+    /// - `Building -> Probing`: The build data and its index are ready.
+    /// - `Probing -> Outputting`: Probe input reaches EOF. Release it and 
report
+    ///   completion to the processor.
+    /// - `Outputting -> end`: Buffered output and any final unmatched build 
rows
+    ///   have been emitted.
+    pub(super) fn into_stream(self) -> SendableRecordBatchStream {

Review Comment:
   This is the execution entry point.



##########
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 directly against the build map.
+///
+/// Each lookup chunk contains at most `batch_size` candidate pairs, even if 
one
+/// key has millions of matches. The lookup offset resumes that key in the next
+/// chunk. Hash collisions are checked before applying the residual predicate.
+/// Residual predicates run before recording matches or emitting unmatched 
rows,
+/// and surviving rows accumulate in a [`LimitedBatchCoalescer`] across chunks 
and
+/// inputs. Small output batches are coalesced toward `batch_size`; batches 
larger
+/// than half that size can bypass coalescing. The coalescer also enforces 
`fetch`.
+/// See the [hash join overview](super) for the build/index/probe boundary.
+///
+/// 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 {

Review Comment:
   This is the key struct that establishes a layer inside HJ.



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