1use 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
86pub 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
139struct UniqueHashJoinState {
143 build_rows: HybridRowStore,
144 hash_index: UniqueHashIndex,
145 build_left: bool,
146}
147
148enum UniqueHashIndex {
149 Direct(DirectHashIndex),
152 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 #[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;