Skip to main content

uqa_execution/join/
mod.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Physical relational join operators.
8
9use crate::RowSchemaExecution;
10mod canonical_index;
11mod direct_index;
12mod iteration;
13mod nested_loop;
14pub(crate) mod presence;
15mod production;
16mod row_store;
17use iteration::HashJoinState;
18
19use smallvec::SmallVec;
20use uqa_core::{
21    memory::{Produced, ProductionControl},
22    Value,
23};
24use uqa_sql::ast::JoinKind;
25use uqa_sql::expr::truthy;
26use uqa_sql::ResultRow;
27
28use crate::distinct::{encode_typed_non_null_key, EncodedKey};
29use crate::{
30    Batch, ExecError, ExecResult, PhysicalOperator, PhysicalRow, ProjectedPredicate, RowSchema,
31    ScalarExpr, SharedExpressionEvaluator, SpillBuffer,
32};
33
34use crate::spill::MatchFlags;
35use canonical_index::{HybridHashIndex, MemoryMatchSummary};
36use direct_index::{direct_unique_match, positional_key_hash, DirectHashIndex};
37use row_store::HybridRowStore;
38
39pub use nested_loop::NestedLoopJoin;
40
41#[cfg(test)]
42use canonical_index::{stable_hash, DiskHashIndex, HASH_BUCKETS};
43
44const DEFAULT_JOIN_WORK_MEM_BYTES: usize = 64 * 1024 * 1024;
45
46/// One probe batch establishes whether a join needs its other input, without draining the probe or retaining more than its ordinary batch allowance.
47fn next_nonempty_batch(
48    input: &mut dyn PhysicalOperator,
49    demanded: bool,
50) -> ExecResult<Option<Batch>> {
51    while let Some(batch) = if demanded {
52        input.next_with_demand(crate::physical::demand::ONE)?
53    } else {
54        input.next()?
55    } {
56        if !batch.rows.is_empty() {
57            return Ok(Some(batch));
58        }
59    }
60    Ok(None)
61}
62
63fn join_io_error(operation: &str, error: impl std::fmt::Display) -> ExecError {
64    ExecError::Other(format!("join spill {operation}: {error}"))
65}
66
67/// Equality join backed by a canonical SQL-key hash table. SQL NULL keys never
68/// match. An optional residual predicate is evaluated on hash candidates
69/// before either side is marked matched, preserving mixed equijoin/non-equality
70/// `ON` semantics for every outer-join shape.
71pub struct HashJoin<'a> {
72    left: Box<dyn PhysicalOperator + 'a>,
73    right: Box<dyn PhysicalOperator + 'a>,
74    kind: JoinKind,
75    left_keys: crate::scalar::PreparedExpressions<Produced<Vec<ScalarExpr>>>,
76    right_keys: crate::scalar::PreparedExpressions<Produced<Vec<ScalarExpr>>>,
77    left_key_types: Vec<Option<uqa_sql::ColumnType>>,
78    right_key_types: Vec<Option<uqa_sql::ColumnType>>,
79    left_key_positions: Option<Produced<Vec<usize>>>,
80    right_key_positions: Option<Produced<Vec<usize>>>,
81    predicate: Option<crate::scalar::PreparedExpressions<Produced<ScalarExpr>>>,
82    prepared_predicate: Option<ProjectedPredicate>,
83    evaluator: SharedExpressionEvaluator<'a>,
84    left_nulls: PhysicalRow,
85    right_nulls: PhysicalRow,
86    schema: RowSchema,
87    estimated_cardinality: Option<u64>,
88    build_left: bool,
89    work_mem_bytes: usize,
90    output: Option<crate::spill::SpillDrain>,
91    streaming_unique: Option<UniqueHashJoinState>,
92    streaming: Option<HashJoinState>,
93    probe_pending: crate::physical::demand::PendingRows,
94    initialized: bool,
95    prefetched_left: Option<Batch>,
96    output_spilled: SpillState,
97    right_input_spilled: SpillState,
98    hash_index_spilled: SpillState,
99    memory: Option<uqa_core::memory::MemoryReservation>,
100}
101
102#[derive(Clone, Copy, Default, Eq, PartialEq)]
103enum SpillState {
104    #[default]
105    InMemory,
106    Spilled,
107}
108
109impl SpillState {
110    fn is_spilled(self) -> bool {
111        matches!(self, Self::Spilled)
112    }
113}
114
115impl From<bool> for SpillState {
116    fn from(spilled: bool) -> Self {
117        if spilled {
118            Self::Spilled
119        } else {
120            Self::InMemory
121        }
122    }
123}
124
125/// State retained while an in-memory unique-key inner join streams its probe
126/// side. At most one output row can be produced per probe row, so the join can
127/// preserve batch backpressure without a cardinality-sized output buffer.
128struct UniqueHashJoinState {
129    build_rows: HybridRowStore,
130    hash_index: UniqueHashIndex,
131    build_left: bool,
132}
133
134enum UniqueHashIndex {
135    /// Simple column keys keep only hashes and row positions. Candidate keys
136    /// are verified against the original build row slots.
137    Direct(DirectHashIndex),
138    /// Evaluated expressions and spill fallback retain canonical byte keys.
139    Encoded(HybridHashIndex),
140}
141
142impl<'a> HashJoin<'a> {
143    #[expect(
144        clippy::too_many_arguments,
145        reason = "keeps join keys and schema aligned"
146    )]
147    pub fn new(
148        left: Box<dyn PhysicalOperator + 'a>,
149        right: Box<dyn PhysicalOperator + 'a>,
150        kind: JoinKind,
151        left_keys: Vec<ScalarExpr>,
152        right_keys: Vec<ScalarExpr>,
153        evaluator: SharedExpressionEvaluator<'a>,
154        left_nulls: ResultRow,
155        right_nulls: ResultRow,
156    ) -> Self {
157        Self::new_with_work_mem(
158            left,
159            right,
160            kind,
161            left_keys,
162            right_keys,
163            evaluator,
164            left_nulls,
165            right_nulls,
166            DEFAULT_JOIN_WORK_MEM_BYTES,
167        )
168    }
169
170    #[expect(
171        clippy::too_many_arguments,
172        reason = "keeps join keys and schema aligned"
173    )]
174    pub fn new_with_work_mem(
175        left: Box<dyn PhysicalOperator + 'a>,
176        right: Box<dyn PhysicalOperator + 'a>,
177        kind: JoinKind,
178        left_keys: Vec<ScalarExpr>,
179        right_keys: Vec<ScalarExpr>,
180        evaluator: SharedExpressionEvaluator<'a>,
181        left_nulls: ResultRow,
182        right_nulls: ResultRow,
183        work_mem_bytes: usize,
184    ) -> Self {
185        Self::new_with_work_mem_and_predicate(
186            left,
187            right,
188            kind,
189            left_keys,
190            right_keys,
191            None,
192            evaluator,
193            left_nulls,
194            right_nulls,
195            work_mem_bytes,
196        )
197    }
198
199    #[expect(
200        clippy::too_many_arguments,
201        reason = "keeps join keys and schema aligned"
202    )]
203    pub fn new_with_work_mem_and_predicate(
204        left: Box<dyn PhysicalOperator + 'a>,
205        right: Box<dyn PhysicalOperator + 'a>,
206        kind: JoinKind,
207        left_keys: Vec<ScalarExpr>,
208        right_keys: Vec<ScalarExpr>,
209        predicate: Option<ScalarExpr>,
210        evaluator: SharedExpressionEvaluator<'a>,
211        left_nulls: ResultRow,
212        right_nulls: ResultRow,
213        work_mem_bytes: usize,
214    ) -> Self {
215        let control = ProductionControl::uncontrolled();
216        Self::build_with_owned_expressions(
217            left,
218            right,
219            kind,
220            control
221                .finish(left_keys, None)
222                .expect("ordinary left join keys"),
223            control
224                .finish(right_keys, None)
225                .expect("ordinary right join keys"),
226            predicate.map(|predicate| {
227                control
228                    .finish(predicate, None)
229                    .expect("ordinary join predicate")
230            }),
231            evaluator,
232            left_nulls,
233            right_nulls,
234            work_mem_bytes,
235            None,
236            &control,
237        )
238        .expect("ordinary hash join construction")
239    }
240
241    /// Construct a hash join while preparing supported residual predicates
242    /// against its composite output schema. Parameters and constant LIKE
243    /// patterns are folded exactly once before any candidate row is probed.
244    #[expect(
245        clippy::too_many_arguments,
246        reason = "keeps join keys and schema aligned"
247    )]
248    pub fn try_new_with_work_mem_and_predicate(
249        left: Box<dyn PhysicalOperator + 'a>,
250        right: Box<dyn PhysicalOperator + 'a>,
251        kind: JoinKind,
252        left_keys: Vec<ScalarExpr>,
253        right_keys: Vec<ScalarExpr>,
254        predicate: Option<ScalarExpr>,
255        evaluator: SharedExpressionEvaluator<'a>,
256        left_nulls: ResultRow,
257        right_nulls: ResultRow,
258        work_mem_bytes: usize,
259        params: &[uqa_sql::SQLParam],
260    ) -> ExecResult<Self> {
261        let control = ProductionControl::uncontrolled();
262        Self::build_with_owned_expressions(
263            left,
264            right,
265            kind,
266            control
267                .finish(left_keys, None)
268                .expect("ordinary left join keys"),
269            control
270                .finish(right_keys, None)
271                .expect("ordinary right join keys"),
272            predicate.map(|predicate| {
273                control
274                    .finish(predicate, None)
275                    .expect("ordinary join predicate")
276            }),
277            evaluator,
278            left_nulls,
279            right_nulls,
280            work_mem_bytes,
281            Some(params),
282            &control,
283        )
284        .map_err(Into::into)
285    }
286
287    pub fn output_has_spilled(&self) -> bool {
288        self.output_spilled.is_spilled()
289    }
290
291    pub fn right_input_has_spilled(&self) -> bool {
292        self.right_input_spilled.is_spilled()
293    }
294
295    pub fn hash_index_has_spilled(&self) -> bool {
296        self.hash_index_spilled.is_spilled()
297    }
298
299    pub fn builds_left_input(&self) -> bool {
300        self.build_left
301    }
302
303    fn next_left_batch(
304        &mut self,
305        demand: Option<std::num::NonZeroUsize>,
306    ) -> ExecResult<Option<Batch>> {
307        if let Some(batch) = self.prefetched_left.take() {
308            self.probe_pending.retain_batch(batch);
309        }
310        self.probe_pending.pull(self.left.as_mut(), demand)
311    }
312
313    fn rebuild_encoded_index(
314        &self,
315        rows: &mut HybridRowStore,
316        expressions: &crate::scalar::PreparedExpressions<Produced<Vec<ScalarExpr>>>,
317        types: &[Option<uqa_sql::ColumnType>],
318        positions: &[usize],
319        budget_bytes: usize,
320    ) -> ExecResult<HybridHashIndex> {
321        let schema = rows.schema.clone();
322        let mut index = HybridHashIndex::new(budget_bytes);
323        for row_index in 0..rows.len() {
324            let key = rows.with_row(row_index, |row| {
325                self.key(expressions, types, Some(positions), row, &schema)
326            })?;
327            if let Some(key) = key {
328                index.insert(key, row_index)?;
329            }
330        }
331        Ok(index)
332    }
333
334    #[expect(
335        clippy::too_many_lines,
336        reason = "join driver keeps key layout, NULL policy, and output order aligned"
337    )]
338    fn open_build_left(&mut self, state_budget: usize, output_budget: usize) -> ExecResult<()> {
339        debug_assert!(matches!(self.kind, JoinKind::Inner));
340        let left_budget = state_budget / 2;
341        let hash_budget = state_budget.saturating_sub(left_budget);
342        let left_schema = self.left.row_schema().clone();
343        let mut left = HybridRowStore::new(left_schema, left_budget);
344        let direct_positions = self
345            .predicate
346            .is_none()
347            .then_some(())
348            .and(self.left_key_positions.as_deref().map(Vec::as_slice))
349            .zip(self.right_key_positions.as_deref().map(Vec::as_slice));
350        let mut direct_index = direct_positions.map(|_| DirectHashIndex::new(hash_budget));
351        let mut encoded_index = direct_index
352            .is_none()
353            .then(|| HybridHashIndex::new(hash_budget));
354        self.left.open()?;
355        while let Some(batch) = self.left.next()? {
356            for row in batch.rows {
357                let index = left.len();
358                if let (Some(direct), Some((positions, _))) =
359                    (direct_index.as_mut(), direct_positions)
360                {
361                    if let Some(hash) = positional_key_hash(
362                        direct.hasher(),
363                        &batch.schema,
364                        &row,
365                        positions,
366                        self.evaluator.enum_labels(),
367                    )? {
368                        direct.insert(hash, index)?;
369                    }
370                } else if let Some(key) = self.key(
371                    &self.left_keys,
372                    &self.left_key_types,
373                    self.left_key_positions.as_deref().map(Vec::as_slice),
374                    &row,
375                    &batch.schema,
376                )? {
377                    encoded_index
378                        .as_mut()
379                        .ok_or_else(|| ExecError::Other("join hash index is missing".into()))?
380                        .insert(key, index)?;
381                }
382                left.push(row)?;
383            }
384        }
385        self.right_input_spilled = SpillState::InMemory;
386
387        let mut output = SpillBuffer::new(output_budget);
388        if left.len() == 0 {
389            self.output = Some(output.drain()?);
390            return Ok(());
391        }
392
393        let direct_is_unique = if let (Some(direct), Some((positions, _))) =
394            (direct_index.as_ref(), direct_positions)
395        {
396            !left.has_spilled()
397                && direct.keys_are_unique(
398                    &left,
399                    &left.schema,
400                    positions,
401                    self.evaluator.enum_labels(),
402                )?
403        } else {
404            false
405        };
406        if direct_is_unique {
407            self.right.open()?;
408            self.streaming_unique = Some(UniqueHashJoinState {
409                build_rows: left,
410                hash_index: UniqueHashIndex::Direct(
411                    direct_index
412                        .take()
413                        .ok_or_else(|| ExecError::Other("direct join index is missing".into()))?,
414                ),
415                build_left: true,
416            });
417            return Ok(());
418        }
419
420        let left_by_key = match encoded_index {
421            Some(index) => index,
422            None => {
423                let (positions, _) = direct_positions
424                    .ok_or_else(|| ExecError::Other("direct join positions are missing".into()))?;
425                self.rebuild_encoded_index(
426                    &mut left,
427                    &self.left_keys,
428                    &self.left_key_types,
429                    positions,
430                    hash_budget,
431                )?
432            }
433        };
434        self.hash_index_spilled = left_by_key.has_spilled().into();
435        if self.predicate.is_none() && !left.has_spilled() && left_by_key.is_memory_unique() {
436            self.right.open()?;
437            self.streaming_unique = Some(UniqueHashJoinState {
438                build_rows: left,
439                hash_index: UniqueHashIndex::Encoded(left_by_key),
440                build_left: true,
441            });
442            return Ok(());
443        }
444        self.right.open()?;
445        self.streaming = Some(HashJoinState::new(left, left_by_key, true, self.kind)?);
446        Ok(())
447    }
448
449    fn key(
450        &self,
451        expressions: &crate::scalar::PreparedExpressions<Produced<Vec<ScalarExpr>>>,
452        types: &[Option<uqa_sql::ColumnType>],
453        positions: Option<&[usize]>,
454        row: &PhysicalRow,
455        schema: &RowSchema,
456    ) -> ExecResult<Option<EncodedKey>> {
457        if let Some(positions) = positions {
458            let view = schema.view(row);
459            return encode_typed_non_null_key(
460                positions.iter().enumerate().map(|(index, position)| {
461                    (
462                        view.value_at(*position),
463                        types.get(index).and_then(Option::as_ref),
464                    )
465                }),
466                self.evaluator.enum_labels(),
467            );
468        }
469        let mut values = SmallVec::<[Value; 4]>::with_capacity(expressions.len());
470        for expression in expressions.iter() {
471            let value = self.evaluator.evaluate_physical_with_function_states(
472                expression,
473                schema,
474                row,
475                expressions.calls(),
476            )?;
477            if matches!(value, Value::Null) {
478                return Ok(None);
479            }
480            values.push(value);
481        }
482        encode_typed_non_null_key(
483            values
484                .iter()
485                .enumerate()
486                .map(|(index, value)| (Some(value), types.get(index).and_then(Option::as_ref))),
487            self.evaluator.enum_labels(),
488        )
489    }
490
491    fn matches(&self, row: &PhysicalRow) -> ExecResult<bool> {
492        if let Some(predicate) = self.prepared_predicate.as_ref() {
493            return Ok(predicate.keep_row(&self.schema.view(row))?);
494        }
495        self.predicate.as_ref().map_or(Ok(true), |predicate| {
496            Ok(truthy(
497                &self.evaluator.evaluate_physical_with_function_states(
498                    predicate,
499                    &self.schema,
500                    row,
501                    predicate.calls(),
502                )?,
503            ))
504        })
505    }
506
507    fn next_streaming_unique(
508        &mut self,
509        state: &mut UniqueHashJoinState,
510        demand: Option<std::num::NonZeroUsize>,
511    ) -> ExecResult<Option<Batch>> {
512        loop {
513            let next = if state.build_left {
514                self.probe_pending.pull(self.right.as_mut(), demand)?
515            } else {
516                self.next_left_batch(demand)?
517            };
518            let Some(batch) = next else {
519                return Ok(None);
520            };
521            let mut output = Vec::with_capacity(batch.rows.len());
522            for probe_row in batch.rows {
523                let index = match &state.hash_index {
524                    UniqueHashIndex::Direct(index) => {
525                        let (build_positions, probe_positions) = if state.build_left {
526                            (
527                                self.left_key_positions.as_deref().map(Vec::as_slice),
528                                self.right_key_positions.as_deref().map(Vec::as_slice),
529                            )
530                        } else {
531                            (
532                                self.right_key_positions.as_deref().map(Vec::as_slice),
533                                self.left_key_positions.as_deref().map(Vec::as_slice),
534                            )
535                        };
536                        let (Some(build_positions), Some(probe_positions)) =
537                            (build_positions, probe_positions)
538                        else {
539                            return Err(ExecError::Other(
540                                "direct join key positions are missing".into(),
541                            ));
542                        };
543                        direct_unique_match(
544                            index,
545                            &state.build_rows,
546                            build_positions,
547                            &batch.schema,
548                            &probe_row,
549                            probe_positions,
550                            self.evaluator.enum_labels(),
551                        )?
552                    }
553                    UniqueHashIndex::Encoded(index) => {
554                        let expressions = if state.build_left {
555                            &self.right_keys
556                        } else {
557                            &self.left_keys
558                        };
559                        let types = if state.build_left {
560                            &self.right_key_types
561                        } else {
562                            &self.left_key_types
563                        };
564                        let positions = if state.build_left {
565                            self.right_key_positions.as_deref().map(Vec::as_slice)
566                        } else {
567                            self.left_key_positions.as_deref().map(Vec::as_slice)
568                        };
569                        let Some(key) =
570                            self.key(expressions, types, positions, &probe_row, &batch.schema)?
571                        else {
572                            continue;
573                        };
574                        match index.memory_match_summary(&key) {
575                            Some(MemoryMatchSummary::Single(index)) => Some(index),
576                            _ => None,
577                        }
578                    }
579                };
580                let Some(index) = index else { continue };
581                let merged = if state.build_left {
582                    state.build_rows.with_row(index, |build_row| {
583                        Ok(PhysicalRow::concat_right_owned(build_row, probe_row))
584                    })?
585                } else {
586                    state.build_rows.with_row(index, |build_row| {
587                        Ok(PhysicalRow::concat_left_owned(probe_row, build_row))
588                    })?
589                };
590                output.push(merged);
591            }
592            if !output.is_empty() {
593                return Ok(Some(Batch::from_physical_rows(self.schema.clone(), output)));
594            }
595        }
596    }
597}
598
599impl HashJoin<'_> {
600    #[expect(
601        clippy::too_many_lines,
602        reason = "join driver keeps key layout, NULL policy, and output order aligned"
603    )]
604    fn initialize(&mut self, demanded: bool) -> ExecResult<()> {
605        self.output = None;
606        self.left_key_types = self
607            .left_keys
608            .iter()
609            .map(|key| self.evaluator.expression_type(key, self.left.row_schema()))
610            .collect::<Result<_, _>>()?;
611        self.right_key_types = self
612            .right_keys
613            .iter()
614            .map(|key| self.evaluator.expression_type(key, self.right.row_schema()))
615            .collect::<Result<_, _>>()?;
616        self.streaming_unique = None;
617        self.prefetched_left = None;
618        self.output_spilled = SpillState::InMemory;
619        self.right_input_spilled = SpillState::InMemory;
620        self.hash_index_spilled = SpillState::InMemory;
621
622        let state_budget = self.work_mem_bytes / 2;
623        let output_budget = self.work_mem_bytes.saturating_sub(state_budget);
624        if self.build_left {
625            return self.open_build_left(state_budget, output_budget);
626        }
627        if !matches!(self.kind, JoinKind::Right | JoinKind::Full) {
628            self.left.open()?;
629            self.prefetched_left = next_nonempty_batch(self.left.as_mut(), demanded)?;
630            if self.prefetched_left.is_none() {
631                self.output = Some(SpillBuffer::new(output_budget).drain()?);
632                return Ok(());
633            }
634        }
635        let right_budget = state_budget / 2;
636        let hash_budget = state_budget.saturating_sub(right_budget);
637        let right_schema = self.right.row_schema().clone();
638        let mut right = HybridRowStore::new(right_schema, right_budget);
639        let direct_positions = (matches!(self.kind, JoinKind::Inner) && self.predicate.is_none())
640            .then_some(())
641            .and(self.right_key_positions.as_deref().map(Vec::as_slice))
642            .zip(self.left_key_positions.as_deref().map(Vec::as_slice));
643        let mut direct_index = direct_positions.map(|_| DirectHashIndex::new(hash_budget));
644        let mut encoded_index = direct_index
645            .is_none()
646            .then(|| HybridHashIndex::new(hash_budget));
647        self.right.open()?;
648        while let Some(batch) = self.right.next()? {
649            for row in batch.rows {
650                let index = right.len();
651                if let (Some(direct), Some((positions, _))) =
652                    (direct_index.as_mut(), direct_positions)
653                {
654                    if let Some(hash) = positional_key_hash(
655                        direct.hasher(),
656                        &batch.schema,
657                        &row,
658                        positions,
659                        self.evaluator.enum_labels(),
660                    )? {
661                        direct.insert(hash, index)?;
662                    }
663                } else if let Some(key) = self.key(
664                    &self.right_keys,
665                    &self.right_key_types,
666                    self.right_key_positions.as_deref().map(Vec::as_slice),
667                    &row,
668                    &batch.schema,
669                )? {
670                    encoded_index
671                        .as_mut()
672                        .ok_or_else(|| ExecError::Other("join hash index is missing".into()))?
673                        .insert(key, index)?;
674                }
675                right.push(row)?;
676            }
677        }
678        self.right_input_spilled = right.has_spilled().into();
679
680        if right.len() == 0 && matches!(self.kind, JoinKind::Inner) {
681            let mut output = SpillBuffer::new(output_budget);
682            self.output = Some(output.drain()?);
683            return Ok(());
684        }
685
686        let direct_is_unique = if let (Some(direct), Some((positions, _))) =
687            (direct_index.as_ref(), direct_positions)
688        {
689            !right.has_spilled()
690                && direct.keys_are_unique(
691                    &right,
692                    &right.schema,
693                    positions,
694                    self.evaluator.enum_labels(),
695                )?
696        } else {
697            false
698        };
699        if direct_is_unique {
700            self.streaming_unique = Some(UniqueHashJoinState {
701                build_rows: right,
702                hash_index: UniqueHashIndex::Direct(
703                    direct_index
704                        .take()
705                        .ok_or_else(|| ExecError::Other("direct join index is missing".into()))?,
706                ),
707                build_left: false,
708            });
709            return Ok(());
710        }
711
712        let right_by_key = match encoded_index {
713            Some(index) => index,
714            None => {
715                let (positions, _) = direct_positions
716                    .ok_or_else(|| ExecError::Other("direct join positions are missing".into()))?;
717                self.rebuild_encoded_index(
718                    &mut right,
719                    &self.right_keys,
720                    &self.right_key_types,
721                    positions,
722                    hash_budget,
723                )?
724            }
725        };
726        self.hash_index_spilled = right_by_key.has_spilled().into();
727        if matches!(self.kind, JoinKind::Inner)
728            && self.predicate.is_none()
729            && !right.has_spilled()
730            && right_by_key.is_memory_unique()
731        {
732            self.streaming_unique = Some(UniqueHashJoinState {
733                build_rows: right,
734                hash_index: UniqueHashIndex::Encoded(right_by_key),
735                build_left: false,
736            });
737            return Ok(());
738        }
739
740        if matches!(self.kind, JoinKind::Right | JoinKind::Full) {
741            self.left.open()?;
742        }
743        self.streaming = Some(HashJoinState::new(right, right_by_key, false, self.kind)?);
744        Ok(())
745    }
746
747    fn pull(&mut self, demand: Option<std::num::NonZeroUsize>) -> ExecResult<Option<Batch>> {
748        if !self.initialized {
749            self.initialized = true;
750            self.initialize(demand.is_some())?;
751        }
752        if let Some(mut state) = self.streaming_unique.take() {
753            let result = self.next_streaming_unique(&mut state, demand);
754            self.streaming_unique = Some(state);
755            return result;
756        }
757        if let Some(mut state) = self.streaming.take() {
758            let rows = demand.map_or(crate::batch::DEFAULT_BATCH_SIZE, |rows| {
759                rows.get().min(crate::batch::DEFAULT_BATCH_SIZE)
760            });
761            let result = self.next_streaming(&mut state, rows, demand.is_some());
762            self.streaming = Some(state);
763            return result;
764        }
765        self.output
766            .as_mut()
767            .map_or(Ok(None), |output| output.next().transpose())
768    }
769}
770
771impl PhysicalOperator for HashJoin<'_> {
772    fn row_schema(&self) -> &RowSchema {
773        &self.schema
774    }
775
776    fn estimated_cardinality(&self) -> Option<u64> {
777        self.estimated_cardinality
778    }
779
780    fn open(&mut self) -> ExecResult<()> {
781        self.output = None;
782        self.streaming_unique = None;
783        self.streaming = None;
784        self.probe_pending.clear();
785        self.prefetched_left = None;
786        self.initialized = false;
787        self.output_spilled = SpillState::InMemory;
788        self.right_input_spilled = SpillState::InMemory;
789        self.hash_index_spilled = SpillState::InMemory;
790        Ok(())
791    }
792
793    fn next(&mut self) -> ExecResult<Option<Batch>> {
794        self.pull(None)
795    }
796
797    fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
798        self.pull(Some(rows))
799    }
800
801    fn close(&mut self) -> ExecResult<()> {
802        self.output = None;
803        self.left_key_types.clear();
804        self.right_key_types.clear();
805        self.streaming_unique = None;
806        self.streaming = None;
807        self.probe_pending.clear();
808        self.prefetched_left = None;
809        let left = self.left.close();
810        let right = self.right.close();
811        crate::physical::with_cleanup(left, right, "close right hash-join input")
812    }
813}
814
815#[cfg(test)]
816mod tests;