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