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