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