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