1use std::borrow::Cow;
2use std::cmp::Ordering;
3use std::iter::repeat_n;
4
5use bytemuck::TransparentWrapper;
6use polars_arrow::array::Array;
7use polars_arrow::array::builder::ShareStrategy;
8use polars_core::frame::builder::DataFrameBuilder;
9use polars_core::prelude::*;
10use polars_core::with_match_physical_numeric_polars_type;
11use polars_defs::join::{JoinArgs, JoinType};
12use polars_utils::itertools::Itertools;
13use polars_utils::sort::reorder_cmp;
14use polars_utils::total_ord::{TotalOrd, TotalOrdWrap};
15use polars_utils::{IdxSize, format_pl_smallstr};
16
17use crate::series::coalesce_columns;
18
19#[allow(clippy::too_many_arguments)]
20pub fn match_keys(
21 build_keys: &Series,
22 probe_keys: &Series,
23 gather_build: &mut Vec<IdxSize>,
24 gather_probe: &mut Vec<IdxSize>,
25 gather_probe_unmatched: Option<&mut Vec<IdxSize>>,
26 build_emit_unmatched: bool,
27 descending: bool,
28 nulls_last: bool,
29 nulls_equal: bool,
30 limit_results: usize,
31 build_row_offset: &mut usize,
32 probe_row_offset: &mut usize,
33 probe_last_matched: &mut usize,
34) {
35 macro_rules! dispatch {
36 ($build_keys_ca:expr) => {
37 match_keys_impl(
38 $build_keys_ca,
39 probe_keys.as_ref().as_ref(),
40 gather_build,
41 gather_probe,
42 gather_probe_unmatched,
43 build_emit_unmatched,
44 descending,
45 nulls_last,
46 nulls_equal,
47 limit_results,
48 build_row_offset,
49 probe_row_offset,
50 probe_last_matched,
51 )
52 };
53 }
54
55 assert_eq!(build_keys.dtype(), probe_keys.dtype());
56 match build_keys.dtype() {
57 dt if dt.is_primitive_numeric() => {
58 with_match_physical_numeric_polars_type!(dt, |$T| {
59 type PhysCa = ChunkedArray<$T>;
60 let build_keys_ca: &PhysCa = build_keys.as_ref().as_ref();
61 dispatch!(build_keys_ca)
62 })
63 },
64 DataType::Boolean => dispatch!(build_keys.bool().unwrap()),
65 DataType::String => dispatch!(build_keys.str().unwrap()),
66 DataType::Binary => dispatch!(build_keys.binary().unwrap()),
67 DataType::BinaryOffset => dispatch!(build_keys.binary_offset().unwrap()),
68 #[cfg(feature = "dtype-categorical")]
69 DataType::Enum(cats, _) => with_match_categorical_physical_type!(cats.physical(), |$C| {
70 type PhysCa = ChunkedArray<<$C as PolarsCategoricalType>::PolarsPhysical>;
71 let build_keys_ca: &PhysCa = build_keys.as_ref().as_ref();
72 dispatch!(build_keys_ca)
73 }),
74 DataType::Null => match_null_keys_impl(
75 build_keys.len(),
76 probe_keys.len(),
77 gather_build,
78 gather_probe,
79 gather_probe_unmatched,
80 build_emit_unmatched,
81 descending,
82 nulls_equal,
83 limit_results,
84 build_row_offset,
85 probe_row_offset,
86 probe_last_matched,
87 ),
88 dt => unimplemented!("merge-join kernel not implemented for {:?}", dt),
89 }
90}
91
92#[allow(clippy::mut_range_bound, clippy::too_many_arguments)]
93fn match_keys_impl<'a, T: PolarsDataType>(
94 build_keys: &'a ChunkedArray<T>,
95 probe_keys: &'a ChunkedArray<T>,
96 gather_build: &mut Vec<IdxSize>,
97 gather_probe: &mut Vec<IdxSize>,
98 mut gather_probe_unmatched: Option<&mut Vec<IdxSize>>,
99 build_emit_unmatched: bool,
100 descending: bool,
101 nulls_last: bool,
102 nulls_equal: bool,
103 limit_results: usize,
104 build_row_offset: &mut usize,
105 probe_row_offset: &mut usize,
106 probe_first_unmatched: &mut usize,
107) where
108 T::Physical<'a>: TotalOrd,
109{
110 assert!(gather_build.is_empty());
111 assert!(gather_probe.is_empty());
112
113 let build_key = build_keys.downcast_as_array();
114 let probe_key = probe_keys.downcast_as_array();
115
116 while *build_row_offset < build_key.len() {
117 if gather_build.len() >= limit_results {
118 return;
119 }
120
121 let build_keyval = unsafe { build_key.get_unchecked(*build_row_offset) };
122 let mut build_keyval_matched = false;
123
124 if nulls_equal || build_keyval.is_some() {
125 for probe_idx in *probe_row_offset..probe_key.len() {
126 let probe_keyval = unsafe { probe_key.get_unchecked(probe_idx) };
127
128 if !nulls_equal && probe_keyval.is_none() {
131 continue;
132 }
133 let ord = reorder_cmp(
134 TotalOrdWrap::wrap_ref(&build_keyval),
135 TotalOrdWrap::wrap_ref(&probe_keyval),
136 descending,
137 nulls_last,
138 );
139
140 match ord {
141 Ordering::Equal => {
142 if let Some(probe_unmatched) = gather_probe_unmatched.as_mut() {
143 probe_unmatched
145 .extend(*probe_first_unmatched as IdxSize..probe_idx as IdxSize);
146 *probe_first_unmatched = (*probe_first_unmatched).max(probe_idx + 1);
147 }
148 gather_build.push(*build_row_offset as IdxSize);
149 gather_probe.push(probe_idx as IdxSize);
150 build_keyval_matched = true;
151 },
152 Ordering::Greater => {
153 if let Some(probe_unmatched) = gather_probe_unmatched.as_mut() {
154 probe_unmatched
156 .extend(*probe_first_unmatched as IdxSize..=probe_idx as IdxSize);
157 *probe_first_unmatched = (*probe_first_unmatched).max(probe_idx + 1);
158 }
159 *probe_row_offset = probe_idx + 1;
160 },
161 Ordering::Less => {
162 break;
163 },
164 }
165 }
166 }
167 if build_emit_unmatched && !build_keyval_matched {
168 gather_build.push(*build_row_offset as IdxSize);
169 gather_probe.push(IdxSize::MAX);
170 }
171 *build_row_offset += 1;
172 }
173 if let Some(probe_unmatched) = gather_probe_unmatched {
174 probe_unmatched.extend(*probe_first_unmatched as IdxSize..probe_key.len() as IdxSize);
175 *probe_first_unmatched = probe_key.len();
176 }
177 *probe_row_offset = probe_key.len();
178}
179
180#[allow(clippy::mut_range_bound, clippy::too_many_arguments)]
181fn match_null_keys_impl(
182 build_n: usize,
183 probe_n: usize,
184 gather_build: &mut Vec<IdxSize>,
185 gather_probe: &mut Vec<IdxSize>,
186 gather_probe_unmatched: Option<&mut Vec<IdxSize>>,
187 build_emit_unmatched: bool,
188 _descending: bool,
189 nulls_equal: bool,
190 limit_results: usize,
191 build_row_offset: &mut usize,
192 probe_row_offset: &mut usize,
193 probe_last_matched: &mut usize,
194) {
195 assert!(gather_build.is_empty());
196 assert!(gather_probe.is_empty());
197
198 if nulls_equal {
199 while *build_row_offset < build_n {
201 if gather_build.len() >= limit_results {
202 return;
203 }
204 for probe_idx in *probe_row_offset..probe_n {
205 gather_build.push(*build_row_offset as IdxSize);
206 gather_probe.push(probe_idx as IdxSize);
207 }
208 *build_row_offset += 1;
209 }
210 } else {
211 if build_emit_unmatched {
214 gather_build.extend(0..build_n as IdxSize);
215 gather_probe.extend(repeat_n(IdxSize::MAX, build_n));
216 }
217 if let Some(probe_unmatched) = gather_probe_unmatched {
218 probe_unmatched.extend(*probe_last_matched as IdxSize..probe_n as IdxSize);
219 *probe_last_matched = probe_n;
220 }
221 }
222 *build_row_offset = build_n;
223 *probe_row_offset = probe_n;
224}
225
226#[allow(clippy::too_many_arguments)]
227pub fn gather_and_postprocess(
228 build: DataFrame,
229 probe: DataFrame,
230 gather_build: Option<&[IdxSize]>,
231 gather_probe: Option<&[IdxSize]>,
232 df_builders: &mut Option<(DataFrameBuilder, DataFrameBuilder)>,
233 args: &JoinArgs,
234 left_on: &[PlSmallStr],
235 right_on: &[PlSmallStr],
236 left_is_build: bool,
237 output_schema: &Schema,
238) -> PolarsResult<DataFrame> {
239 let should_coalesce = args.should_coalesce();
240 let left_emit_unmatched = matches!(args.how, JoinType::Left | JoinType::Full);
241 let right_emit_unmatched = matches!(args.how, JoinType::Right | JoinType::Full);
242
243 let (mut left, mut right);
244 let (gather_left, gather_right);
245 if left_is_build {
246 (left, right) = (build, probe);
247 (gather_left, gather_right) = (gather_build, gather_probe);
248 } else {
249 (left, right) = (probe, build);
250 (gather_left, gather_right) = (gather_probe, gather_build);
251 }
252
253 let left_keys_coalesced_away = should_coalesce && matches!(args.how, JoinType::Right);
254
255 for col in left
257 .columns()
258 .iter()
259 .map(Column::name)
260 .cloned()
261 .collect_vec()
262 {
263 if left_on.contains(&col) && should_coalesce {
264 continue;
265 }
266 if !output_schema.contains(&col) {
267 left.drop_in_place(&col).unwrap();
268 }
269 }
270 for col in right
271 .columns()
272 .iter()
273 .map(Column::name)
274 .cloned()
275 .collect_vec()
276 {
277 if right_on.contains(&col) && should_coalesce {
278 continue;
279 }
280 let collides =
283 left.schema().contains(&col) && !(left_keys_coalesced_away && left_on.contains(&col));
284 let renamed = match collides {
285 true => Cow::Owned(format_pl_smallstr!("{}{}", col, args.suffix())),
286 false => Cow::Borrowed(&col),
287 };
288 if !output_schema.contains(&renamed) {
289 right.drop_in_place(&col).unwrap();
290 }
291 }
292
293 if df_builders.is_none() {
294 *df_builders = Some((
295 DataFrameBuilder::new(left.schema().clone()),
296 DataFrameBuilder::new(right.schema().clone()),
297 ));
298 }
299
300 let (left_build, right_build) = df_builders.as_mut().unwrap();
301 let mut left = match gather_left {
302 Some(gather_left) if right_emit_unmatched => {
303 left_build.opt_gather_extend(&left, gather_left, ShareStrategy::Never);
304 left_build.freeze_reset()
305 },
306 Some(gather_left) => unsafe {
307 left_build.gather_extend(&left, gather_left, ShareStrategy::Never);
308 left_build.freeze_reset()
309 },
310 None => DataFrame::full_null(left.schema(), gather_right.unwrap().len()),
311 };
312 let mut right = match gather_right {
313 Some(gather_right) if left_emit_unmatched => {
314 right_build.opt_gather_extend(&right, gather_right, ShareStrategy::Never);
315 right_build.freeze_reset()
316 },
317 Some(gather_right) => unsafe {
318 right_build.gather_extend(&right, gather_right, ShareStrategy::Never);
319 right_build.freeze_reset()
320 },
321 None => DataFrame::full_null(right.schema(), gather_left.unwrap().len()),
322 };
323
324 if should_coalesce {
326 match args.how {
327 JoinType::Inner | JoinType::Left => {
328 for c in right_on {
329 if right.schema().contains(c) {
330 right.drop_in_place(c.as_str())?;
331 }
332 }
333 },
334 JoinType::Right => {
335 for c in left_on {
336 if left.schema().contains(c) {
337 left.drop_in_place(c.as_str())?;
338 }
339 }
340 },
341 JoinType::Full => {
342 for (left_keycol, right_keycol) in Iterator::zip(left_on.iter(), right_on.iter()) {
343 let left_col = left.column(left_keycol).unwrap();
344 let right_col = right.column(right_keycol).unwrap();
345 let coalesced =
346 coalesce_columns(&[left_col.clone(), right_col.clone()]).unwrap();
347 left.replace(left_keycol, coalesced).unwrap();
348 right.drop_in_place(right_keycol).unwrap();
349 }
350 },
351 _ => unreachable!(),
352 }
353 }
354
355 let left_cols: PlHashSet<_> = left.columns().iter().map(Column::name).cloned().collect();
357 let right_cols_vec = right.get_column_names_owned();
358 let renames = right_cols_vec
359 .iter()
360 .filter(|c| left_cols.contains(*c))
361 .map(|c| {
362 let renamed = format_pl_smallstr!("{}{}", c, args.suffix());
363 (c.as_str(), renamed)
364 });
365 right = right.rename_many(renames).unwrap();
366
367 left.hstack_mut(right.columns())?;
369 for col in left_on {
370 if left.schema().contains(col) && !output_schema.contains(col) {
371 left.drop_in_place(col).unwrap();
372 }
373 }
374
375 debug_assert_eq!(**left.schema(), *output_schema);
376 Ok(left)
377}