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