Skip to main content

polars_ops/frame/join/
merge_join.rs

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                // Row-encoded keys are null wherever any key column is null, so a null probe
129                // key has no place in the order.
130                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                            // All probe keys up to and *excluding* this matched key are unmatched
144                            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                            // All probe keys up to and *including* this matched key are unmatched
155                            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        // All keys will match all other keys, so just emit the Cartesian product
200        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        // No keys can ever match, so just emit all build keys into gather_build
212        // and all probe keys into gather_probe_unmatched.
213        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    // Remove non-payload columns
256    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        // A right column takes the suffix only where it collides with a left column
281        // that survives coalescing.
282        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    // Coalesce the key columns.
325    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    // Rename any duplicate right columns to "{}_right".
356    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    // Merge left and right and drop unused output columns.
368    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}