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_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
85pub 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
136struct UniqueHashJoinState {
140 build_rows: HybridRowStore,
141 hash_index: UniqueHashIndex,
142 build_left: bool,
143}
144
145enum UniqueHashIndex {
146 Direct(DirectHashIndex),
149 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 #[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;