1mod args;
2#[cfg(feature = "asof_join")]
3mod asof;
4mod cross_join;
5mod dispatch_left_right;
6mod general;
7mod hash_join;
8#[cfg(feature = "iejoin")]
9mod iejoin;
10pub mod merge_join;
11#[cfg(feature = "merge_sorted")]
12mod merge_sorted;
13mod validation;
14
15use std::borrow::Cow;
16use std::hash::Hash;
17
18pub use args::*;
19#[cfg(feature = "asof_join")]
20pub use asof::{
21 _asof_key_to_physical, _check_asof_columns, _join_asof_dispatch, AsofJoin, AsofJoinBy,
22};
23pub use cross_join::CrossJoin;
24#[cfg(feature = "chunked_ids")]
25use either::Either;
26#[cfg(feature = "chunked_ids")]
27use general::create_chunked_index_mapping;
28pub use general::{_coalesce_full_join, _finish_join, _join_suffix_name};
29pub use hash_join::*;
30use hashbrown::hash_map::{Entry, RawEntryMut};
31#[cfg(feature = "merge_sorted")]
32pub use merge_sorted::_merge_sorted_dfs;
33use polars_arrow::trusted_len::TrustedLen;
34use polars_core::chunked_array::ops::row_encode::{
35 encode_rows_with_layout_par, get_binary_offset_row_encoding_layout,
36 get_optimal_row_encoding_layout,
37};
38use polars_core::datatypes::DataType;
39use polars_core::hashing::_HASHMAP_INIT_SIZE;
40use polars_core::prelude::*;
41use polars_core::runtime::RAYON;
42pub(super) use polars_core::series::IsSorted;
43use polars_defs::join::{
44 JoinArgs, JoinCoalesce, JoinType, JoinTypeOptions, JoinValidation, MaintainOrderJoin,
45};
46use polars_utils::hashing::BytesHash;
47use polars_utils::slice_enum::Slice;
48use rayon::prelude::*;
49
50use self::cross_join::fused_cross_filter;
51use super::IntoDf;
52
53pub(crate) fn par_map_collect<R: Send>(n: usize, f: &(dyn Fn(usize) -> R + Sync)) -> Vec<R> {
55 RAYON.install(|| (0..n).into_par_iter().map(f).collect())
56}
57
58pub trait DataFrameJoinOps: IntoDf {
59 fn join(
96 &self,
97 other: &DataFrame,
98 left_on: impl IntoIterator<Item = impl AsRef<str>>,
99 right_on: impl IntoIterator<Item = impl AsRef<str>>,
100 args: JoinArgs,
101 options: Option<JoinTypeOptions>,
102 ) -> PolarsResult<DataFrame> {
103 let df_left = self.to_df();
104 let selected_left = df_left.select_to_vec(left_on)?;
105 let selected_right = other.select_to_vec(right_on)?;
106
107 let selected_left = selected_left
108 .into_iter()
109 .map(Column::take_materialized_series)
110 .collect::<Vec<_>>();
111 let selected_right = selected_right
112 .into_iter()
113 .map(Column::take_materialized_series)
114 .collect::<Vec<_>>();
115
116 self._join_impl(
117 other,
118 selected_left,
119 selected_right,
120 args,
121 options,
122 true,
123 false,
124 )
125 }
126
127 #[doc(hidden)]
128 #[allow(clippy::too_many_arguments)]
129 #[allow(unused_mut)]
130 fn _join_impl(
131 &self,
132 other: &DataFrame,
133 mut selected_left: Vec<Series>,
134 mut selected_right: Vec<Series>,
135 mut args: JoinArgs,
136 options: Option<JoinTypeOptions>,
137 _check_rechunk: bool,
138 _verbose: bool,
139 ) -> PolarsResult<DataFrame> {
140 let left_df = self.to_df();
141
142 if let Some(JoinTypeOptions::FusedPredicate(fused_options)) = &options {
144 debug_assert!(args.slice.is_none());
145 polars_ensure!(
147 args.how.is_inner(),
148 InvalidOperation: "a fused join predicate is only supported for inner joins on the in-memory engine"
149 );
150 let predicate = fused_options.predicate.clone();
151 let joined = self._join_impl(
152 other,
153 selected_left,
154 selected_right,
155 args,
156 None,
157 _check_rechunk,
158 _verbose,
159 )?;
160 return predicate.apply(joined, true);
161 }
162
163 #[cfg(feature = "cross_join")]
164 if let Some(JoinTypeOptions::Cross(cross_options)) = &options {
165 assert!(args.slice.is_none());
166 return fused_cross_filter(
167 left_df,
168 other,
169 args.suffix.clone(),
170 cross_options,
171 args.maintain_order,
172 &args.how,
173 );
174 }
175 #[cfg(feature = "cross_join")]
176 if let JoinType::Cross = args.how {
177 return left_df.cross_join(other, args.suffix.clone(), args.slice, args.maintain_order);
178 }
179
180 fn clear(s: &mut [Series]) {
182 for s in s.iter_mut() {
183 if s.len() == 1 {
184 *s = s.clear()
185 }
186 }
187 }
188 if left_df.height() == 0 {
189 clear(&mut selected_left);
190 }
191 if other.height() == 0 {
192 clear(&mut selected_right);
193 }
194
195 let should_coalesce = args.should_coalesce();
196 assert_eq!(selected_left.len(), selected_right.len());
197
198 #[cfg(feature = "chunked_ids")]
199 {
200 if _check_rechunk
204 && !(matches!(args.how, JoinType::Left)
205 || std::env::var("POLARS_NO_CHUNKED_JOIN").is_ok())
206 {
207 let mut left = Cow::Borrowed(left_df);
208 let mut right = Cow::Borrowed(other);
209 if left_df.should_rechunk() {
210 if _verbose {
211 eprintln!(
212 "{:?} join triggered a rechunk of the left DataFrame: {} columns are affected",
213 args.how,
214 left_df.width()
215 );
216 }
217
218 let mut tmp_left = left_df.clone();
219 tmp_left.rechunk_mut_par();
220 left = Cow::Owned(tmp_left);
221 }
222 if other.should_rechunk() {
223 if _verbose {
224 eprintln!(
225 "{:?} join triggered a rechunk of the right DataFrame: {} columns are affected",
226 args.how,
227 other.width()
228 );
229 }
230 let mut tmp_right = other.clone();
231 tmp_right.rechunk_mut_par();
232 right = Cow::Owned(tmp_right);
233 }
234 return left._join_impl(
235 &right,
236 selected_left,
237 selected_right,
238 args,
239 options,
240 false,
241 _verbose,
242 );
243 }
244 }
245
246 if let Some((l, r)) = selected_left
247 .iter()
248 .zip(&selected_right)
249 .find(|(l, r)| l.dtype() != r.dtype())
250 {
251 polars_bail!(
252 ComputeError:
253 "datatypes of join keys don't match - `{}`: {} on left does not match `{}`: {} on right",
254 l.name(), l.dtype().pretty_format(), r.name(), r.dtype().pretty_format()
255 );
256 };
257
258 #[cfg(feature = "iejoin")]
259 if let Some(JoinTypeOptions::IEJoin(ie_options)) = options {
260 let func = if RAYON.current_num_threads() > 1
261 && !left_df.shape_has_zero()
262 && !other.shape_has_zero()
263 {
264 iejoin::iejoin_par
265 } else {
266 iejoin::iejoin
267 };
268 let emit_unmatched =
269 if args.how.emits_unmatched_left() && args.how.emits_unmatched_right() {
270 iejoin::EmitUnmatched::Both
271 } else if args.how.emits_unmatched_left() {
272 iejoin::EmitUnmatched::Left
273 } else if args.how.emits_unmatched_right() {
274 iejoin::EmitUnmatched::Right
275 } else {
276 iejoin::EmitUnmatched::None
277 };
278 return func(
279 left_df,
280 other,
281 selected_left,
282 selected_right,
283 &ie_options,
284 args.suffix,
285 args.slice,
286 emit_unmatched,
287 );
288 }
289
290 if selected_left.len() == 1 {
292 let s_left = &selected_left[0];
293 let s_right = &selected_right[0];
294 let drop_names: Option<Vec<PlSmallStr>> =
295 if should_coalesce { None } else { Some(vec![]) };
296 return match args.how {
297 JoinType::Inner => left_df
298 ._inner_join_from_series(other, s_left, s_right, args, _verbose, drop_names),
299 JoinType::Left => dispatch_left_right::left_join_from_series(
300 self.to_df().clone(),
301 other,
302 s_left,
303 s_right,
304 args,
305 _verbose,
306 drop_names,
307 ),
308 JoinType::Right => dispatch_left_right::right_join_from_series(
309 self.to_df(),
310 other.clone(),
311 s_left,
312 s_right,
313 args,
314 _verbose,
315 drop_names,
316 ),
317 JoinType::Full => left_df._full_join_from_series(other, s_left, s_right, args),
318 #[cfg(feature = "semi_anti_join")]
319 JoinType::Anti => left_df._semi_anti_join_from_series(
320 s_left,
321 s_right,
322 args.slice,
323 true,
324 args.nulls_equal,
325 ),
326 #[cfg(feature = "semi_anti_join")]
327 JoinType::Semi => left_df._semi_anti_join_from_series(
328 s_left,
329 s_right,
330 args.slice,
331 false,
332 args.nulls_equal,
333 ),
334 #[cfg(feature = "asof_join")]
335 JoinType::AsOf(options) => match (options.left_by, options.right_by) {
336 (Some(left_by), Some(right_by)) => left_df._join_asof_by(
337 other,
338 s_left,
339 s_right,
340 left_by,
341 right_by,
342 options.strategy,
343 options.tolerance.map(|v| v.into_value()),
344 args.suffix.clone(),
345 args.slice,
346 should_coalesce,
347 options.allow_eq,
348 options.check_sortedness,
349 ),
350 (None, None) => left_df._join_asof(
351 other,
352 s_left,
353 s_right,
354 options.strategy,
355 options.tolerance.map(|v| v.into_value()),
356 args.suffix,
357 args.slice,
358 should_coalesce,
359 options.allow_eq,
360 options.check_sortedness,
361 ),
362 _ => {
363 panic!("expected by arguments on both sides")
364 },
365 },
366 #[cfg(feature = "iejoin")]
367 JoinType::IEJoin | JoinType::Range => {
368 unreachable!()
369 },
370 JoinType::Cross => {
371 unreachable!()
372 },
373 };
374 }
375 let (lhs_keys, rhs_keys) = if (left_df.height() == 0 || other.height() == 0)
376 && matches!(&args.how, JoinType::Inner)
377 {
378 let a = Series::full_null("".into(), 0, &DataType::Null);
381 (a.clone(), a)
382 } else {
383 prepare_keys_multiple(&selected_left, &selected_right, args.nulls_equal)?
385 };
386
387 let drop_names = if should_coalesce {
388 if args.how == JoinType::Right {
389 selected_left
390 .iter()
391 .map(|s| s.name().clone())
392 .collect::<Vec<_>>()
393 } else {
394 selected_right
395 .iter()
396 .map(|s| s.name().clone())
397 .collect::<Vec<_>>()
398 }
399 } else {
400 vec![]
401 };
402
403 match args.how {
405 #[cfg(feature = "asof_join")]
406 JoinType::AsOf(_) => polars_bail!(
407 ComputeError: "asof join not supported for join on multiple keys"
408 ),
409 #[cfg(feature = "iejoin")]
410 JoinType::IEJoin | JoinType::Range => {
411 unreachable!()
412 },
413 JoinType::Cross => {
414 unreachable!()
415 },
416 JoinType::Full => {
417 let names_left = selected_left
418 .iter()
419 .map(|s| s.name().clone())
420 .collect::<Vec<_>>();
421 args.coalesce = JoinCoalesce::KeepColumns;
422 let suffix = args.suffix.clone();
423 let out = left_df._full_join_from_series(other, &lhs_keys, &rhs_keys, args);
424
425 if should_coalesce {
426 Ok(_coalesce_full_join(
427 out?,
428 names_left.as_slice(),
429 drop_names.as_slice(),
430 suffix,
431 left_df,
432 ))
433 } else {
434 out
435 }
436 },
437 JoinType::Inner => left_df._inner_join_from_series(
438 other,
439 &lhs_keys,
440 &rhs_keys,
441 args,
442 _verbose,
443 Some(drop_names),
444 ),
445 JoinType::Left => dispatch_left_right::left_join_from_series(
446 left_df.clone(),
447 other,
448 &lhs_keys,
449 &rhs_keys,
450 args,
451 _verbose,
452 Some(drop_names),
453 ),
454 JoinType::Right => dispatch_left_right::right_join_from_series(
455 left_df,
456 other.clone(),
457 &lhs_keys,
458 &rhs_keys,
459 args,
460 _verbose,
461 Some(drop_names),
462 ),
463 #[cfg(feature = "semi_anti_join")]
464 JoinType::Anti | JoinType::Semi => self._join_impl(
465 other,
466 vec![lhs_keys],
467 vec![rhs_keys],
468 args,
469 options,
470 _check_rechunk,
471 _verbose,
472 ),
473 }
474 }
475
476 fn inner_join(
488 &self,
489 other: &DataFrame,
490 left_on: impl IntoIterator<Item = impl AsRef<str>>,
491 right_on: impl IntoIterator<Item = impl AsRef<str>>,
492 ) -> PolarsResult<DataFrame> {
493 self.join(
494 other,
495 left_on,
496 right_on,
497 JoinArgs::new(JoinType::Inner),
498 None,
499 )
500 }
501
502 fn left_join(
538 &self,
539 other: &DataFrame,
540 left_on: impl IntoIterator<Item = impl AsRef<str>>,
541 right_on: impl IntoIterator<Item = impl AsRef<str>>,
542 ) -> PolarsResult<DataFrame> {
543 self.join(
544 other,
545 left_on,
546 right_on,
547 JoinArgs::new(JoinType::Left),
548 None,
549 )
550 }
551
552 fn full_join(
563 &self,
564 other: &DataFrame,
565 left_on: impl IntoIterator<Item = impl AsRef<str>>,
566 right_on: impl IntoIterator<Item = impl AsRef<str>>,
567 ) -> PolarsResult<DataFrame> {
568 self.join(
569 other,
570 left_on,
571 right_on,
572 JoinArgs::new(JoinType::Full),
573 None,
574 )
575 }
576}
577
578trait DataFrameJoinOpsPrivate: IntoDf {
579 fn _inner_join_from_series(
580 &self,
581 other: &DataFrame,
582 s_left: &Series,
583 s_right: &Series,
584 args: JoinArgs,
585 verbose: bool,
586 drop_names: Option<Vec<PlSmallStr>>,
587 ) -> PolarsResult<DataFrame> {
588 let left_df = self.to_df();
589 let ((join_tuples_left, join_tuples_right), sorted) =
590 _sort_or_hash_inner(s_left, s_right, verbose, args.validation, args.nulls_equal)?;
591
592 let mut join_tuples_left = &*join_tuples_left;
593 let mut join_tuples_right = &*join_tuples_right;
594
595 let already_left_sorted = sorted
596 && matches!(
597 args.maintain_order,
598 MaintainOrderJoin::Left | MaintainOrderJoin::LeftRight
599 );
600 let need_sort = args.maintain_order != MaintainOrderJoin::None && !already_left_sorted;
601
602 if !need_sort && let Some(slice) = args.slice {
603 join_tuples_left = &join_tuples_left[slice];
604 join_tuples_right = &join_tuples_right[slice];
605 }
606
607 let other = if let Some(drop_names) = drop_names {
608 other.drop_many(drop_names)
609 } else {
610 other.drop(s_right.name()).unwrap()
611 };
612
613 let mut left = unsafe { IdxCa::mmap_slice("a".into(), join_tuples_left) };
614 if sorted {
615 left.set_sorted_flag(IsSorted::Ascending);
616 }
617 let right = unsafe { IdxCa::mmap_slice("b".into(), join_tuples_right) };
618
619 try_raise_polars_abort();
620
621 let (df_left, df_right) = if need_sort {
622 let mut df = unsafe {
623 DataFrame::new_unchecked_infer_height(vec![
624 left.into_series().into(),
625 right.into_series().into(),
626 ])
627 };
628
629 let columns = match args.maintain_order {
630 MaintainOrderJoin::Left | MaintainOrderJoin::LeftRight => vec!["a"],
631 MaintainOrderJoin::Right | MaintainOrderJoin::RightLeft => vec!["b"],
632 _ => unreachable!(),
633 };
634
635 let options = SortMultipleOptions::new()
636 .with_order_descending(false)
637 .with_maintain_order(true);
638
639 df.sort_in_place(columns, options)?;
640
641 if let Some(slice) = args.slice {
642 df = df.slice(slice);
643 }
644
645 let [mut a, b]: [Column; 2] = df.into_columns().try_into().unwrap();
646 if matches!(
647 args.maintain_order,
648 MaintainOrderJoin::Left | MaintainOrderJoin::LeftRight
649 ) {
650 a.set_sorted_flag(IsSorted::Ascending);
651 }
652
653 RAYON.join(
654 || unsafe { left_df.take_unchecked(a.idx().unwrap()) },
656 || unsafe { other.take_unchecked(b.idx().unwrap()) },
657 )
658 } else {
659 RAYON.join(
660 || unsafe { left_df.take_unchecked(left.into_series().idx().unwrap()) },
662 || unsafe { other.take_unchecked(right.into_series().idx().unwrap()) },
663 )
664 };
665
666 _finish_join(df_left, df_right, args.suffix)
667 }
668}
669
670impl DataFrameJoinOps for DataFrame {}
671impl DataFrameJoinOpsPrivate for DataFrame {}
672
673fn prepare_keys_multiple(
675 left: &[Series],
676 right: &[Series],
677 nulls_equal: bool,
678) -> PolarsResult<(Series, Series)> {
679 let to_keys = |s: &[Series]| {
680 s.iter()
681 .map(|s| {
682 let phys = s.to_physical_repr();
683 match phys.dtype() {
684 #[cfg(feature = "dtype-f16")]
685 DataType::Float16 => phys.f16().unwrap().to_canonical().into_column(),
686 DataType::Float32 => phys.f32().unwrap().to_canonical().into_column(),
687 DataType::Float64 => phys.f64().unwrap().to_canonical().into_column(),
688 _ => phys.into_owned().into_column(),
689 }
690 })
691 .collect::<Vec<_>>()
692 };
693 let (left, right) = (to_keys(left), to_keys(right));
694
695 let opts = vec![RowEncodingOptions::new_unsorted(); left.len()];
696 let same_dtypes = left.iter().zip(&right).all(|(l, r)| l.dtype() == r.dtype());
697 let propagate_nulls = !nulls_equal;
698 let (left_layout, right_layout) = if same_dtypes {
699 let layout = get_optimal_row_encoding_layout(&left, &[&right], &opts);
700 (layout.clone(), layout)
701 } else {
702 (
703 get_binary_offset_row_encoding_layout(&left, &opts),
704 get_binary_offset_row_encoding_layout(&right, &opts),
705 )
706 };
707 Ok((
708 encode_rows_with_layout_par(&left, &left_layout, propagate_nulls)?,
709 encode_rows_with_layout_par(&right, &right_layout, propagate_nulls)?,
710 ))
711}
712
713pub fn private_left_join_multiple_keys(
717 a: &[Column],
718 b: &[Column],
719 nulls_equal: bool,
720) -> PolarsResult<LeftJoinIds> {
721 let a_cols = a
723 .iter()
724 .map(|c| c.as_materialized_series().clone())
725 .collect::<Vec<_>>();
726 let b_cols = b
727 .iter()
728 .map(|c| c.as_materialized_series().clone())
729 .collect::<Vec<_>>();
730
731 let (a, b) = prepare_keys_multiple(&a_cols, &b_cols, nulls_equal)?;
732 sort_or_hash_left(
733 &a,
734 &b.rechunk(),
735 false,
736 JoinValidation::ManyToMany,
737 nulls_equal,
738 )
739}