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