Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2SQL-style merge routines
3"""
5from __future__ import annotations
7import datetime
8from functools import partial
9import types
10from typing import (
11 TYPE_CHECKING,
12 Literal,
13 cast,
14 final,
15)
16import warnings
18import numpy as np
20from pandas._libs import (
21 Timedelta,
22 hashtable as libhashtable,
23 join as libjoin,
24 lib,
25)
26from pandas._libs.lib import is_range_indexer
27from pandas.errors import MergeError
28from pandas.util._decorators import (
29 cache_readonly,
30 set_module,
31)
32from pandas.util._exceptions import find_stack_level
34from pandas.core.dtypes.base import ExtensionDtype
35from pandas.core.dtypes.cast import find_common_type
36from pandas.core.dtypes.common import (
37 ensure_int64,
38 ensure_object,
39 is_bool,
40 is_bool_dtype,
41 is_float_dtype,
42 is_integer,
43 is_integer_dtype,
44 is_list_like,
45 is_number,
46 is_numeric_dtype,
47 is_object_dtype,
48 is_string_dtype,
49 needs_i8_conversion,
50)
51from pandas.core.dtypes.dtypes import (
52 CategoricalDtype,
53 DatetimeTZDtype,
54)
55from pandas.core.dtypes.generic import (
56 ABCDataFrame,
57 ABCSeries,
58)
59from pandas.core.dtypes.missing import (
60 isna,
61 na_value_for_dtype,
62)
64from pandas import (
65 ArrowDtype,
66 Categorical,
67 Index,
68 MultiIndex,
69 RangeIndex,
70 Series,
71)
72import pandas.core.algorithms as algos
73from pandas.core.arrays import (
74 ArrowExtensionArray,
75 BaseMaskedArray,
76 ExtensionArray,
77)
78from pandas.core.arrays.string_ import StringDtype
79import pandas.core.common as com
80from pandas.core.construction import (
81 ensure_wrapped_if_datetimelike,
82 extract_array,
83)
84from pandas.core.indexes.api import (
85 default_index,
86 ensure_index_from_sequences,
87)
88from pandas.core.indexes.base import maybe_sequence_to_range
89from pandas.core.sorting import (
90 get_group_index,
91 is_int64_overflow_possible,
92)
94if TYPE_CHECKING:
95 from collections.abc import (
96 Hashable,
97 Sequence,
98 )
100 from pandas._typing import (
101 AnyArrayLike,
102 ArrayLike,
103 IndexLabel,
104 JoinHow,
105 MergeHow,
106 Shape,
107 Suffixes,
108 npt,
109 )
111 from pandas import DataFrame
112 from pandas.core import groupby
113 from pandas.core.arrays import DatetimeArray
114 from pandas.core.indexes.frozen import FrozenList
116_factorizers = {
117 np.int64: libhashtable.Int64Factorizer,
118 np.longlong: libhashtable.Int64Factorizer,
119 np.int32: libhashtable.Int32Factorizer,
120 np.int16: libhashtable.Int16Factorizer,
121 np.int8: libhashtable.Int8Factorizer,
122 np.uint64: libhashtable.UInt64Factorizer,
123 np.uint32: libhashtable.UInt32Factorizer,
124 np.uint16: libhashtable.UInt16Factorizer,
125 np.uint8: libhashtable.UInt8Factorizer,
126 np.bool_: libhashtable.UInt8Factorizer,
127 np.float64: libhashtable.Float64Factorizer,
128 np.float32: libhashtable.Float32Factorizer,
129 np.complex64: libhashtable.Complex64Factorizer,
130 np.complex128: libhashtable.Complex128Factorizer,
131 np.object_: libhashtable.ObjectFactorizer,
132}
134# See https://github.com/pandas-dev/pandas/issues/52451
135if np.intc is not np.int32:
136 if np.dtype(np.intc).itemsize == 4:
137 _factorizers[np.intc] = libhashtable.Int32Factorizer
138 else:
139 _factorizers[np.intc] = libhashtable.Int64Factorizer
141if np.uintc is not np.uint32:
142 if np.dtype(np.uintc).itemsize == 4:
143 _factorizers[np.uintc] = libhashtable.UInt32Factorizer
144 else:
145 _factorizers[np.uintc] = libhashtable.UInt64Factorizer
148_known = (np.ndarray, ExtensionArray, Index, ABCSeries)
151@set_module("pandas")
152def merge(
153 left: DataFrame | Series,
154 right: DataFrame | Series,
155 how: MergeHow = "inner",
156 on: IndexLabel | AnyArrayLike | None = None,
157 left_on: IndexLabel | AnyArrayLike | None = None,
158 right_on: IndexLabel | AnyArrayLike | None = None,
159 left_index: bool = False,
160 right_index: bool = False,
161 sort: bool = False,
162 suffixes: Suffixes = ("_x", "_y"),
163 copy: bool | lib.NoDefault = lib.no_default,
164 indicator: str | bool = False,
165 validate: str | None = None,
166) -> DataFrame:
167 """
168 Merge DataFrame or named Series objects with a database-style join.
170 A named Series object is treated as a DataFrame with a single named column.
172 The join is done on columns or indexes. If joining columns on
173 columns, the DataFrame indexes *will be ignored*. Otherwise if joining indexes
174 on indexes or indexes on a column or columns, the index will be passed on.
175 When performing a cross merge, no column specifications to merge on are
176 allowed.
178 .. warning::
180 If both key columns contain rows where the key is a null value, those
181 rows will be matched against each other. This is different from usual SQL
182 join behaviour and can lead to unexpected results.
184 Parameters
185 ----------
186 left : DataFrame or named Series
187 First pandas object to merge.
188 right : DataFrame or named Series
189 Second pandas object to merge.
190 how : {'left', 'right', 'outer', 'inner', 'cross', 'left_anti', 'right_anti},
191 default 'inner'
192 Type of merge to be performed.
194 * left: use only keys from left frame, similar to a SQL left outer join;
195 preserve key order.
196 * right: use only keys from right frame, similar to a SQL right outer join;
197 preserve key order.
198 * outer: use union of keys from both frames, similar to a SQL full outer
199 join; sort keys lexicographically.
200 * inner: use intersection of keys from both frames, similar to a SQL inner
201 join; preserve the order of the left keys.
202 * cross: creates the cartesian product from both frames, preserves the order
203 of the left keys.
204 * left_anti: use only keys from left frame that are not in right frame, similar
205 to SQL left anti join; preserve key order.
206 * right_anti: use only keys from right frame that are not in left frame, similar
207 to SQL right anti join; preserve key order.
208 on : Hashable or a sequence of the previous
209 Column or index level names to join on. These must be found in both
210 DataFrames. If `on` is None and not merging on indexes then this defaults
211 to the intersection of the columns in both DataFrames.
212 left_on : Hashable or a sequence of the previous, or array-like
213 Column or index level names to join on in the left DataFrame. Can also
214 be an array or list of arrays of the length of the left DataFrame.
215 These arrays are treated as if they are columns.
216 right_on : Hashable or a sequence of the previous, or array-like
217 Column or index level names to join on in the right DataFrame. Can also
218 be an array or list of arrays of the length of the right DataFrame.
219 These arrays are treated as if they are columns.
220 left_index : bool, default False
221 Use the index from the left DataFrame as the join key(s). If it is a
222 MultiIndex, the number of keys in the other DataFrame (either the index
223 or a number of columns) must match the number of levels.
224 right_index : bool, default False
225 Use the index from the right DataFrame as the join key. Same caveats as
226 left_index.
227 sort : bool, default False
228 Sort the join keys lexicographically in the result DataFrame. If False,
229 the order of the join keys depends on the join type (how keyword).
230 suffixes : list-like, default is ("_x", "_y")
231 A length-2 sequence where each element is optionally a string
232 indicating the suffix to add to overlapping column names in
233 `left` and `right` respectively. Pass a value of `None` instead
234 of a string to indicate that the column name from `left` or
235 `right` should be left as-is, with no suffix. At least one of the
236 values must not be None.
237 copy : bool, default False
238 This keyword is now ignored; changing its value will have no
239 impact on the method.
241 .. deprecated:: 3.0.0
243 This keyword is ignored and will be removed in pandas 4.0. Since
244 pandas 3.0, this method always returns a new object using a lazy
245 copy mechanism that defers copies until necessary
246 (Copy-on-Write). See the `user guide on Copy-on-Write
247 <https://pandas.pydata.org/docs/dev/user_guide/migration.html>`__
248 for more details.
250 indicator : bool or str, default False
251 If True, adds a column to the output DataFrame called "_merge" with
252 information on the source of each row. The column can be given a different
253 name by providing a string argument. The column will have a Categorical
254 type with the value of "left_only" for observations whose merge key only
255 appears in the left DataFrame, "right_only" for observations
256 whose merge key only appears in the right DataFrame, and "both"
257 if the observation's merge key is found in both DataFrames.
259 validate : str, optional
260 If specified, checks if merge is of specified type.
262 * "one_to_one" or "1:1": check if merge keys are unique in both
263 left and right datasets.
264 * "one_to_many" or "1:m": check if merge keys are unique in left
265 dataset.
266 * "many_to_one" or "m:1": check if merge keys are unique in right
267 dataset.
268 * "many_to_many" or "m:m": allowed, but does not result in checks.
270 Returns
271 -------
272 DataFrame
273 A DataFrame of the two merged objects.
275 See Also
276 --------
277 merge_ordered : Merge with optional filling/interpolation.
278 merge_asof : Merge on nearest keys.
279 DataFrame.join : Similar method using indices.
281 Examples
282 --------
283 >>> df1 = pd.DataFrame(
284 ... {"lkey": ["foo", "bar", "baz", "foo"], "value": [1, 2, 3, 5]}
285 ... )
286 >>> df2 = pd.DataFrame(
287 ... {"rkey": ["foo", "bar", "baz", "foo"], "value": [5, 6, 7, 8]}
288 ... )
289 >>> df1
290 lkey value
291 0 foo 1
292 1 bar 2
293 2 baz 3
294 3 foo 5
295 >>> df2
296 rkey value
297 0 foo 5
298 1 bar 6
299 2 baz 7
300 3 foo 8
302 Merge df1 and df2 on the lkey and rkey columns. The value columns have
303 the default suffixes, _x and _y, appended.
305 >>> df1.merge(df2, left_on="lkey", right_on="rkey")
306 lkey value_x rkey value_y
307 0 foo 1 foo 5
308 1 foo 1 foo 8
309 2 bar 2 bar 6
310 3 baz 3 baz 7
311 4 foo 5 foo 5
312 5 foo 5 foo 8
314 Merge DataFrames df1 and df2 with specified left and right suffixes
315 appended to any overlapping columns.
317 >>> df1.merge(df2, left_on="lkey", right_on="rkey", suffixes=("_left", "_right"))
318 lkey value_left rkey value_right
319 0 foo 1 foo 5
320 1 foo 1 foo 8
321 2 bar 2 bar 6
322 3 baz 3 baz 7
323 4 foo 5 foo 5
324 5 foo 5 foo 8
326 Merge DataFrames df1 and df2, but raise an exception if the DataFrames have
327 any overlapping columns.
329 >>> df1.merge(df2, left_on="lkey", right_on="rkey", suffixes=(False, False))
330 Traceback (most recent call last):
331 ...
332 ValueError: columns overlap but no suffix specified:
333 Index(['value'], dtype='str')
335 >>> df1 = pd.DataFrame({"a": ["foo", "bar"], "b": [1, 2]})
336 >>> df2 = pd.DataFrame({"a": ["foo", "baz"], "c": [3, 4]})
337 >>> df1
338 a b
339 0 foo 1
340 1 bar 2
341 >>> df2
342 a c
343 0 foo 3
344 1 baz 4
346 >>> df1.merge(df2, how="inner", on="a")
347 a b c
348 0 foo 1 3
350 >>> df1.merge(df2, how="left", on="a")
351 a b c
352 0 foo 1 3.0
353 1 bar 2 NaN
355 >>> df1 = pd.DataFrame({"left": ["foo", "bar"]})
356 >>> df2 = pd.DataFrame({"right": [7, 8]})
357 >>> df1
358 left
359 0 foo
360 1 bar
361 >>> df2
362 right
363 0 7
364 1 8
366 >>> df1.merge(df2, how="cross")
367 left right
368 0 foo 7
369 1 foo 8
370 2 bar 7
371 3 bar 8
372 """
373 left_df = _validate_operand(left)
374 left._check_copy_deprecation(copy)
375 right_df = _validate_operand(right)
376 if how == "cross":
377 return _cross_merge(
378 left_df,
379 right_df,
380 on=on,
381 left_on=left_on,
382 right_on=right_on,
383 left_index=left_index,
384 right_index=right_index,
385 sort=sort,
386 suffixes=suffixes,
387 indicator=indicator,
388 validate=validate,
389 )
390 else:
391 op = _MergeOperation(
392 left_df,
393 right_df,
394 how=how,
395 on=on,
396 left_on=left_on,
397 right_on=right_on,
398 left_index=left_index,
399 right_index=right_index,
400 sort=sort,
401 suffixes=suffixes,
402 indicator=indicator,
403 validate=validate,
404 )
405 return op.get_result()
408def _cross_merge(
409 left: DataFrame,
410 right: DataFrame,
411 on: IndexLabel | AnyArrayLike | None = None,
412 left_on: IndexLabel | AnyArrayLike | None = None,
413 right_on: IndexLabel | AnyArrayLike | None = None,
414 left_index: bool = False,
415 right_index: bool = False,
416 sort: bool = False,
417 suffixes: Suffixes = ("_x", "_y"),
418 indicator: str | bool = False,
419 validate: str | None = None,
420) -> DataFrame:
421 """
422 See merge.__doc__ with how='cross'
423 """
425 if (
426 left_index
427 or right_index
428 or right_on is not None
429 or left_on is not None
430 or on is not None
431 ):
432 raise MergeError(
433 "Can not pass on, right_on, left_on or set right_index=True or "
434 "left_index=True"
435 )
437 return _CrossMergeOperation(
438 left,
439 right,
440 suffixes=suffixes,
441 indicator=indicator,
442 ).get_result()
445def _groupby_and_merge(
446 by, left: DataFrame | Series, right: DataFrame | Series, merge_pieces
447):
448 """
449 groupby & merge; we are always performing a left-by type operation
451 Parameters
452 ----------
453 by: field to group
454 left: DataFrame
455 right: DataFrame
456 merge_pieces: function for merging
457 """
458 pieces = []
459 if not isinstance(by, (list, tuple)):
460 by = [by]
462 lby = left.groupby(by, sort=False)
463 rby: groupby.DataFrameGroupBy | groupby.SeriesGroupBy | None = None
465 # if we can groupby the rhs
466 # then we can get vastly better perf
467 if all(item in right.columns for item in by):
468 rby = right.groupby(by, sort=False)
470 for key, lhs in lby._grouper.get_iterator(lby._selected_obj):
471 if rby is None:
472 rhs = right
473 else:
474 try:
475 rhs = right.take(rby.indices[key])
476 except KeyError:
477 # key doesn't exist in left
478 lcols = lhs.columns.tolist()
479 cols = lcols + [r for r in right.columns if r not in set(lcols)]
480 merged = lhs.reindex(columns=cols)
481 merged.index = range(len(merged))
482 pieces.append(merged)
483 continue
485 merged = merge_pieces(lhs, rhs)
487 # make sure join keys are in the merged
488 # TODO, should merge_pieces do this?
489 merged[by] = key
491 pieces.append(merged)
493 # preserve the original order
494 # if we have a missing piece this can be reset
495 from pandas.core.reshape.concat import concat
497 result = concat(pieces, ignore_index=True)
498 result = result.reindex(columns=pieces[0].columns)
499 return result, lby
502@set_module("pandas")
503def merge_ordered(
504 left: DataFrame | Series,
505 right: DataFrame | Series,
506 on: IndexLabel | None = None,
507 left_on: IndexLabel | None = None,
508 right_on: IndexLabel | None = None,
509 left_by=None,
510 right_by=None,
511 fill_method: str | None = None,
512 suffixes: Suffixes = ("_x", "_y"),
513 how: JoinHow = "outer",
514) -> DataFrame:
515 """
516 Perform a merge for ordered data with optional filling/interpolation.
518 Designed for ordered data like time series data. Optionally
519 perform group-wise merge (see examples).
521 Parameters
522 ----------
523 left : DataFrame or named Series
524 First pandas object to merge.
525 right : DataFrame or named Series
526 Second pandas object to merge.
527 on : Hashable or a sequence of the previous
528 Field names to join on. Must be found in both DataFrames.
529 left_on : Hashable or a sequence of the previous, or array-like
530 Field names to join on in left DataFrame. Can be a vector or list of
531 vectors of the length of the DataFrame to use a particular vector as
532 the join key instead of columns.
533 right_on : Hashable or a sequence of the previous, or array-like
534 Field names to join on in right DataFrame or vector/list of vectors per
535 left_on docs.
536 left_by : column name or list of column names
537 Group left DataFrame by group columns and merge piece by piece with
538 right DataFrame. Must be None if either left or right are a Series.
539 right_by : column name or list of column names
540 Group right DataFrame by group columns and merge piece by piece with
541 left DataFrame. Must be None if either left or right are a Series.
542 fill_method : {'ffill', None}, default None
543 Interpolation method for data.
544 suffixes : list-like, default is ("_x", "_y")
545 A length-2 sequence where each element is optionally a string
546 indicating the suffix to add to overlapping column names in
547 `left` and `right` respectively. Pass a value of `None` instead
548 of a string to indicate that the column name from `left` or
549 `right` should be left as-is, with no suffix. At least one of the
550 values must not be None.
552 how : {'left', 'right', 'outer', 'inner'}, default 'outer'
553 * left: use only keys from left frame (SQL: left outer join)
554 * right: use only keys from right frame (SQL: right outer join)
555 * outer: use union of keys from both frames (SQL: full outer join)
556 * inner: use intersection of keys from both frames (SQL: inner join).
558 Returns
559 -------
560 DataFrame
561 The merged DataFrame output type will be the same as
562 'left', if it is a subclass of DataFrame.
564 See Also
565 --------
566 merge : Merge with a database-style join.
567 merge_asof : Merge on nearest keys.
569 Examples
570 --------
571 >>> from pandas import merge_ordered
572 >>> df1 = pd.DataFrame(
573 ... {
574 ... "key": ["a", "c", "e", "a", "c", "e"],
575 ... "lvalue": [1, 2, 3, 1, 2, 3],
576 ... "group": ["a", "a", "a", "b", "b", "b"],
577 ... }
578 ... )
579 >>> df1
580 key lvalue group
581 0 a 1 a
582 1 c 2 a
583 2 e 3 a
584 3 a 1 b
585 4 c 2 b
586 5 e 3 b
588 >>> df2 = pd.DataFrame({"key": ["b", "c", "d"], "rvalue": [1, 2, 3]})
589 >>> df2
590 key rvalue
591 0 b 1
592 1 c 2
593 2 d 3
595 >>> merge_ordered(df1, df2, fill_method="ffill", left_by="group")
596 key lvalue group rvalue
597 0 a 1 a NaN
598 1 b 1 a 1.0
599 2 c 2 a 2.0
600 3 d 2 a 3.0
601 4 e 3 a 3.0
602 5 a 1 b NaN
603 6 b 1 b 1.0
604 7 c 2 b 2.0
605 8 d 2 b 3.0
606 9 e 3 b 3.0
607 """
609 def _merger(x, y) -> DataFrame:
610 # perform the ordered merge operation
611 op = _OrderedMerge(
612 x,
613 y,
614 on=on,
615 left_on=left_on,
616 right_on=right_on,
617 suffixes=suffixes,
618 fill_method=fill_method,
619 how=how,
620 )
621 return op.get_result()
623 if left_by is not None and right_by is not None:
624 raise ValueError("Can only group either left or right frames")
625 if left_by is not None:
626 if isinstance(left_by, str):
627 left_by = [left_by]
628 check = set(left_by).difference(left.columns)
629 if len(check) != 0:
630 raise KeyError(f"{check} not found in left columns")
631 result, _ = _groupby_and_merge(left_by, left, right, lambda x, y: _merger(x, y))
632 elif right_by is not None:
633 if isinstance(right_by, str):
634 right_by = [right_by]
635 check = set(right_by).difference(right.columns)
636 if len(check) != 0:
637 raise KeyError(f"{check} not found in right columns")
638 result, _ = _groupby_and_merge(
639 right_by, right, left, lambda x, y: _merger(y, x)
640 )
641 else:
642 result = _merger(left, right)
643 return result
646@set_module("pandas")
647def merge_asof(
648 left: DataFrame | Series,
649 right: DataFrame | Series,
650 on: IndexLabel | None = None,
651 left_on: IndexLabel | None = None,
652 right_on: IndexLabel | None = None,
653 left_index: bool = False,
654 right_index: bool = False,
655 by=None,
656 left_by=None,
657 right_by=None,
658 suffixes: Suffixes = ("_x", "_y"),
659 tolerance: int | datetime.timedelta | None = None,
660 allow_exact_matches: bool = True,
661 direction: str = "backward",
662) -> DataFrame:
663 """
664 Perform a merge by key distance.
666 This is similar to a left-join except that we match on nearest
667 key rather than equal keys. Both DataFrames must be first sorted by
668 the merge key in ascending order before calling this function.
669 Sorting by any additional 'by' grouping columns is not required.
671 For each row in the left DataFrame:
673 - A "backward" search selects the last row in the right DataFrame whose
674 'on' key is less than or equal to the left's key.
676 - A "forward" search selects the first row in the right DataFrame whose
677 'on' key is greater than or equal to the left's key.
679 - A "nearest" search selects the row in the right DataFrame whose 'on'
680 key is closest in absolute distance to the left's key.
682 Optionally match on equivalent keys with 'by' before searching with 'on'.
684 Parameters
685 ----------
686 left : DataFrame or named Series
687 First pandas object to merge.
688 right : DataFrame or named Series
689 Second pandas object to merge.
690 on : label
691 Field name to join on. Must be found in both DataFrames.
692 The data MUST be in ascending order. Furthermore this must be
693 a numeric column, such as datetimelike, integer, or float. ``on``
694 or ``left_on`` / ``right_on`` must be given.
695 left_on : label or array-like
696 Field name to join on in left DataFrame. Can also be an array of the
697 length of the left DataFrame, which is treated as if it were a column.
698 If specified, sort the left DataFrame by this key in ascending order
699 before merging.
700 right_on : label or array-like
701 Field name to join on in right DataFrame. Can also be an array of the
702 length of the right DataFrame, which is treated as if it were a column.
703 If specified, sort the right DataFrame by this key in ascending order
704 before merging.
705 left_index : bool
706 Use the index of the left DataFrame as the join key.
707 right_index : bool
708 Use the index of the right DataFrame as the join key.
709 by : column name or list of column names
710 Match on these columns before performing merge operation. It is not required
711 to sort by these columns.
712 left_by : column name
713 Field names to match on in the left DataFrame.
714 right_by : column name
715 Field names to match on in the right DataFrame.
716 suffixes : 2-length sequence (tuple, list, ...)
717 Suffix to apply to overlapping column names in the left and right
718 side, respectively.
719 tolerance : int or timedelta, optional, default None
720 Select asof tolerance within this range; must be compatible
721 with the merge index.
722 allow_exact_matches : bool, default True
724 - If True, allow matching with the same 'on' value
725 (i.e. less-than-or-equal-to / greater-than-or-equal-to)
726 - If False, don't match the same 'on' value
727 (i.e., strictly less-than / strictly greater-than).
729 direction : 'backward' (default), 'forward', or 'nearest'
730 Whether to search for prior, subsequent, or closest matches.
732 Returns
733 -------
734 DataFrame
735 A DataFrame of the two merged objects, containing all rows from the
736 left DataFrame and the nearest matches from the right DataFrame. The
737 key column holds the left DataFrame's values; the right DataFrame's
738 key column is retained only if it has a different name.
740 See Also
741 --------
742 merge : Merge with a database-style join.
743 merge_ordered : Merge with optional filling/interpolation.
745 Examples
746 --------
747 >>> left = pd.DataFrame({"a": [1, 5, 10], "left_val": ["a", "b", "c"]})
748 >>> left
749 a left_val
750 0 1 a
751 1 5 b
752 2 10 c
754 >>> right = pd.DataFrame({"a": [1, 2, 3, 6, 7], "right_val": [1, 2, 3, 6, 7]})
755 >>> right
756 a right_val
757 0 1 1
758 1 2 2
759 2 3 3
760 3 6 6
761 4 7 7
763 >>> pd.merge_asof(left, right, on="a")
764 a left_val right_val
765 0 1 a 1
766 1 5 b 3
767 2 10 c 7
769 >>> pd.merge_asof(left, right, on="a", allow_exact_matches=False)
770 a left_val right_val
771 0 1 a NaN
772 1 5 b 3.0
773 2 10 c 7.0
775 >>> pd.merge_asof(left, right, on="a", direction="forward")
776 a left_val right_val
777 0 1 a 1.0
778 1 5 b 6.0
779 2 10 c NaN
781 >>> pd.merge_asof(left, right, on="a", direction="nearest")
782 a left_val right_val
783 0 1 a 1
784 1 5 b 6
785 2 10 c 7
787 We can use indexed DataFrames as well.
789 >>> left = pd.DataFrame({"left_val": ["a", "b", "c"]}, index=[1, 5, 10])
790 >>> left
791 left_val
792 1 a
793 5 b
794 10 c
796 >>> right = pd.DataFrame({"right_val": [1, 2, 3, 6, 7]}, index=[1, 2, 3, 6, 7])
797 >>> right
798 right_val
799 1 1
800 2 2
801 3 3
802 6 6
803 7 7
805 >>> pd.merge_asof(left, right, left_index=True, right_index=True)
806 left_val right_val
807 1 a 1
808 5 b 3
809 10 c 7
811 Here is a real-world times-series example
813 >>> quotes = pd.DataFrame(
814 ... {
815 ... "time": [
816 ... pd.Timestamp("2016-05-25 13:30:00.023"),
817 ... pd.Timestamp("2016-05-25 13:30:00.023"),
818 ... pd.Timestamp("2016-05-25 13:30:00.030"),
819 ... pd.Timestamp("2016-05-25 13:30:00.041"),
820 ... pd.Timestamp("2016-05-25 13:30:00.048"),
821 ... pd.Timestamp("2016-05-25 13:30:00.049"),
822 ... pd.Timestamp("2016-05-25 13:30:00.072"),
823 ... pd.Timestamp("2016-05-25 13:30:00.075"),
824 ... ],
825 ... "ticker": [
826 ... "GOOG",
827 ... "MSFT",
828 ... "MSFT",
829 ... "MSFT",
830 ... "GOOG",
831 ... "AAPL",
832 ... "GOOG",
833 ... "MSFT",
834 ... ],
835 ... "bid": [720.50, 51.95, 51.97, 51.99, 720.50, 97.99, 720.50, 52.01],
836 ... "ask": [720.93, 51.96, 51.98, 52.00, 720.93, 98.01, 720.88, 52.03],
837 ... }
838 ... )
839 >>> quotes
840 time ticker bid ask
841 0 2016-05-25 13:30:00.023 GOOG 720.50 720.93
842 1 2016-05-25 13:30:00.023 MSFT 51.95 51.96
843 2 2016-05-25 13:30:00.030 MSFT 51.97 51.98
844 3 2016-05-25 13:30:00.041 MSFT 51.99 52.00
845 4 2016-05-25 13:30:00.048 GOOG 720.50 720.93
846 5 2016-05-25 13:30:00.049 AAPL 97.99 98.01
847 6 2016-05-25 13:30:00.072 GOOG 720.50 720.88
848 7 2016-05-25 13:30:00.075 MSFT 52.01 52.03
850 >>> trades = pd.DataFrame(
851 ... {
852 ... "time": [
853 ... pd.Timestamp("2016-05-25 13:30:00.023"),
854 ... pd.Timestamp("2016-05-25 13:30:00.038"),
855 ... pd.Timestamp("2016-05-25 13:30:00.048"),
856 ... pd.Timestamp("2016-05-25 13:30:00.048"),
857 ... pd.Timestamp("2016-05-25 13:30:00.048"),
858 ... ],
859 ... "ticker": ["MSFT", "MSFT", "GOOG", "GOOG", "AAPL"],
860 ... "price": [51.95, 51.95, 720.77, 720.92, 98.0],
861 ... "quantity": [75, 155, 100, 100, 100],
862 ... }
863 ... )
864 >>> trades
865 time ticker price quantity
866 0 2016-05-25 13:30:00.023 MSFT 51.95 75
867 1 2016-05-25 13:30:00.038 MSFT 51.95 155
868 2 2016-05-25 13:30:00.048 GOOG 720.77 100
869 3 2016-05-25 13:30:00.048 GOOG 720.92 100
870 4 2016-05-25 13:30:00.048 AAPL 98.00 100
872 By default we are taking the asof of the quotes
874 >>> pd.merge_asof(trades, quotes, on="time", by="ticker")
875 time ticker price quantity bid ask
876 0 2016-05-25 13:30:00.023 MSFT 51.95 75 51.95 51.96
877 1 2016-05-25 13:30:00.038 MSFT 51.95 155 51.97 51.98
878 2 2016-05-25 13:30:00.048 GOOG 720.77 100 720.50 720.93
879 3 2016-05-25 13:30:00.048 GOOG 720.92 100 720.50 720.93
880 4 2016-05-25 13:30:00.048 AAPL 98.00 100 NaN NaN
882 We only asof within 2ms between the quote time and the trade time
884 >>> pd.merge_asof(
885 ... trades, quotes, on="time", by="ticker", tolerance=pd.Timedelta("2ms")
886 ... )
887 time ticker price quantity bid ask
888 0 2016-05-25 13:30:00.023 MSFT 51.95 75 51.95 51.96
889 1 2016-05-25 13:30:00.038 MSFT 51.95 155 NaN NaN
890 2 2016-05-25 13:30:00.048 GOOG 720.77 100 720.50 720.93
891 3 2016-05-25 13:30:00.048 GOOG 720.92 100 720.50 720.93
892 4 2016-05-25 13:30:00.048 AAPL 98.00 100 NaN NaN
894 We only asof within 10ms between the quote time and the trade time
895 and we exclude exact matches on time. However *prior* data will
896 propagate forward
898 >>> pd.merge_asof(
899 ... trades,
900 ... quotes,
901 ... on="time",
902 ... by="ticker",
903 ... tolerance=pd.Timedelta("10ms"),
904 ... allow_exact_matches=False,
905 ... )
906 time ticker price quantity bid ask
907 0 2016-05-25 13:30:00.023 MSFT 51.95 75 NaN NaN
908 1 2016-05-25 13:30:00.038 MSFT 51.95 155 51.97 51.98
909 2 2016-05-25 13:30:00.048 GOOG 720.77 100 NaN NaN
910 3 2016-05-25 13:30:00.048 GOOG 720.92 100 NaN NaN
911 4 2016-05-25 13:30:00.048 AAPL 98.00 100 NaN NaN
912 """
913 op = _AsOfMerge(
914 left,
915 right,
916 on=on,
917 left_on=left_on,
918 right_on=right_on,
919 left_index=left_index,
920 right_index=right_index,
921 by=by,
922 left_by=left_by,
923 right_by=right_by,
924 suffixes=suffixes,
925 how="asof",
926 tolerance=tolerance,
927 allow_exact_matches=allow_exact_matches,
928 direction=direction,
929 )
930 return op.get_result()
933# TODO: transformations??
934class _MergeOperation:
935 """
936 Perform a database (SQL) merge operation between two DataFrame or Series
937 objects using either columns as keys or their row indexes
938 """
940 _merge_type = "merge"
941 how: JoinHow | Literal["asof"]
942 on: IndexLabel | None
943 # left_on/right_on may be None when passed, but in validate_specification
944 # get replaced with non-None.
945 left_on: Sequence[Hashable | AnyArrayLike]
946 right_on: Sequence[Hashable | AnyArrayLike]
947 left_index: bool
948 right_index: bool
949 sort: bool
950 suffixes: Suffixes
951 indicator: str | bool
952 validate: str | None
953 join_names: list[Hashable]
954 right_join_keys: list[ArrayLike]
955 left_join_keys: list[ArrayLike]
957 def __init__(
958 self,
959 left: DataFrame | Series,
960 right: DataFrame | Series,
961 how: JoinHow | Literal["left_anti", "right_anti", "asof"] = "inner",
962 on: IndexLabel | AnyArrayLike | None = None,
963 left_on: IndexLabel | AnyArrayLike | None = None,
964 right_on: IndexLabel | AnyArrayLike | None = None,
965 left_index: bool = False,
966 right_index: bool = False,
967 sort: bool = True,
968 suffixes: Suffixes = ("_x", "_y"),
969 indicator: str | bool = False,
970 validate: str | None = None,
971 ) -> None:
972 _left = _validate_operand(left)
973 _right = _validate_operand(right)
974 self.left = self.orig_left = _left
975 self.right = self.orig_right = _right
976 self.how, self.anti_join = self._validate_how(how)
978 self.on = com.maybe_make_list(on) # type: ignore[assignment]
980 self.suffixes = suffixes
981 self.sort = sort or how == "outer"
983 self.left_index = left_index
984 self.right_index = right_index
986 self.indicator = indicator
988 if not is_bool(left_index):
989 raise ValueError(
990 f"left_index parameter must be of type bool, not {type(left_index)}"
991 )
992 if not is_bool(right_index):
993 raise ValueError(
994 f"right_index parameter must be of type bool, not {type(right_index)}"
995 )
997 # GH 40993: raise when merging between different levels; enforced in 2.0
998 if _left.columns.nlevels != _right.columns.nlevels:
999 msg = (
1000 "Not allowed to merge between different levels. "
1001 f"({_left.columns.nlevels} levels on the left, "
1002 f"{_right.columns.nlevels} on the right)"
1003 )
1004 raise MergeError(msg)
1006 self.left_on, self.right_on = self._validate_left_right_on(left_on, right_on)
1008 (
1009 self.left_join_keys,
1010 self.right_join_keys,
1011 self.join_names,
1012 left_drop,
1013 right_drop,
1014 ) = self._get_merge_keys()
1016 if left_drop:
1017 self.left = self.left._drop_labels_or_levels(left_drop)
1019 if right_drop:
1020 self.right = self.right._drop_labels_or_levels(right_drop)
1022 self._maybe_require_matching_dtypes(self.left_join_keys, self.right_join_keys)
1023 self._validate_tolerance(self.left_join_keys)
1025 # validate the merge keys dtypes. We may need to coerce
1026 # to avoid incompatible dtypes
1027 self._maybe_coerce_merge_keys()
1029 # If argument passed to validate,
1030 # check if columns specified as unique
1031 # are in fact unique.
1032 if validate is not None:
1033 self._validate_validate_kwd(validate)
1035 @final
1036 def _validate_how(
1037 self, how: JoinHow | Literal["left_anti", "right_anti", "asof"]
1038 ) -> tuple[JoinHow | Literal["asof"], bool]:
1039 """
1040 Validate the 'how' parameter and return the actual join type and whether
1041 this is an anti join.
1042 """
1043 # GH 59435: raise when "how" is not a valid Merge type
1044 merge_type = {
1045 "left",
1046 "right",
1047 "inner",
1048 "outer",
1049 "left_anti",
1050 "right_anti",
1051 "cross",
1052 "asof",
1053 }
1054 if how not in merge_type:
1055 raise ValueError(
1056 f"'{how}' is not a valid Merge type: "
1057 f"left, right, inner, outer, left_anti, right_anti, cross, asof"
1058 )
1059 anti_join = False
1060 if how in {"left_anti", "right_anti"}:
1061 how = how.split("_")[0] # type: ignore[assignment]
1062 anti_join = True
1063 how = cast("JoinHow | Literal['asof']", how)
1064 return how, anti_join
1066 def _maybe_require_matching_dtypes(
1067 self, left_join_keys: list[ArrayLike], right_join_keys: list[ArrayLike]
1068 ) -> None:
1069 # Overridden by AsOfMerge
1070 pass
1072 def _validate_tolerance(self, left_join_keys: list[ArrayLike]) -> None:
1073 # Overridden by AsOfMerge
1074 pass
1076 @final
1077 def _reindex_and_concat(
1078 self,
1079 join_index: Index,
1080 left_indexer: npt.NDArray[np.intp] | None,
1081 right_indexer: npt.NDArray[np.intp] | None,
1082 ) -> DataFrame:
1083 """
1084 reindex along index and concat along columns.
1085 """
1086 # Take views so we do not alter the originals
1087 left = self.left[:]
1088 right = self.right[:]
1090 llabels, rlabels = _items_overlap_with_suffix(
1091 self.left._info_axis, self.right._info_axis, self.suffixes
1092 )
1094 if left_indexer is not None and not is_range_indexer(left_indexer, len(left)):
1095 # Pinning the index here (and in the right code just below) is not
1096 # necessary, but makes the `.take` more performant if we have e.g.
1097 # a MultiIndex for left.index.
1098 lmgr = left._mgr.reindex_indexer(
1099 join_index,
1100 left_indexer,
1101 axis=1,
1102 only_slice=True,
1103 allow_dups=True,
1104 use_na_proxy=True,
1105 )
1106 left = left._constructor_from_mgr(lmgr, axes=lmgr.axes)
1107 left.index = join_index
1109 if right_indexer is not None and not is_range_indexer(
1110 right_indexer, len(right)
1111 ):
1112 rmgr = right._mgr.reindex_indexer(
1113 join_index,
1114 right_indexer,
1115 axis=1,
1116 only_slice=True,
1117 allow_dups=True,
1118 use_na_proxy=True,
1119 )
1120 right = right._constructor_from_mgr(rmgr, axes=rmgr.axes)
1121 right.index = join_index
1123 from pandas import concat
1125 left.columns = llabels
1126 right.columns = rlabels
1127 result = concat([left, right], axis=1)
1128 return result
1130 def get_result(self) -> DataFrame:
1131 """
1132 Execute the merge.
1133 """
1134 if self.indicator:
1135 self.left, self.right = self._indicator_pre_merge(self.left, self.right)
1137 join_index, left_indexer, right_indexer = self._get_join_info()
1139 result = self._reindex_and_concat(join_index, left_indexer, right_indexer)
1141 if self.indicator:
1142 result = self._indicator_post_merge(result)
1144 self._maybe_add_join_keys(result, left_indexer, right_indexer)
1146 self._maybe_restore_index_levels(result)
1148 return result.__finalize__(
1149 types.SimpleNamespace(
1150 input_objs=[self.left, self.right], left=self.left, right=self.right
1151 ),
1152 method="merge",
1153 )
1155 @final
1156 @cache_readonly
1157 def _indicator_name(self) -> str | None:
1158 if isinstance(self.indicator, str):
1159 return self.indicator
1160 elif isinstance(self.indicator, bool):
1161 return "_merge" if self.indicator else None
1162 else:
1163 raise ValueError(
1164 "indicator option can only accept boolean or string arguments"
1165 )
1167 @final
1168 def _indicator_pre_merge(
1169 self, left: DataFrame, right: DataFrame
1170 ) -> tuple[DataFrame, DataFrame]:
1171 """
1172 Add one indicator column to each of the left and right inputs.
1174 These columns are used to produce another column in the output of the
1175 merge, indicating for each row of the output whether it was produced
1176 using the left, right or both inputs.
1177 """
1178 columns = left.columns.union(right.columns)
1180 for i in ["_left_indicator", "_right_indicator"]:
1181 if i in columns:
1182 raise ValueError(
1183 "Cannot use `indicator=True` option when "
1184 f"data contains a column named {i}"
1185 )
1186 if self._indicator_name in columns:
1187 raise ValueError(
1188 "Cannot use name of an existing column for indicator column"
1189 )
1191 left = left.copy(deep=False)
1192 right = right.copy(deep=False)
1194 left["_left_indicator"] = 1
1195 left["_left_indicator"] = left["_left_indicator"].astype("int8")
1197 right["_right_indicator"] = 2
1198 right["_right_indicator"] = right["_right_indicator"].astype("int8")
1200 return left, right
1202 @final
1203 def _indicator_post_merge(self, result: DataFrame) -> DataFrame:
1204 """
1205 Add an indicator column to the merge result.
1207 This column indicates for each row of the output whether it was produced using
1208 the left, right or both inputs.
1209 """
1210 result["_left_indicator"] = result["_left_indicator"].fillna(0)
1211 result["_right_indicator"] = result["_right_indicator"].fillna(0)
1213 result[self._indicator_name] = Categorical(
1214 (result["_left_indicator"] + result["_right_indicator"]),
1215 categories=[1, 2, 3],
1216 )
1217 result[self._indicator_name] = result[
1218 self._indicator_name
1219 ].cat.rename_categories(["left_only", "right_only", "both"])
1221 result = result.drop(labels=["_left_indicator", "_right_indicator"], axis=1)
1222 return result
1224 @final
1225 def _maybe_restore_index_levels(self, result: DataFrame) -> None:
1226 """
1227 Restore index levels specified as `on` parameters
1229 Here we check for cases where `self.left_on` and `self.right_on` pairs
1230 each reference an index level in their respective DataFrames. The
1231 joined columns corresponding to these pairs are then restored to the
1232 index of `result`.
1234 **Note:** This method has side effects. It modifies `result` in-place
1236 Parameters
1237 ----------
1238 result: DataFrame
1239 merge result
1241 Returns
1242 -------
1243 None
1244 """
1245 names_to_restore = []
1246 for name, left_key, right_key in zip(
1247 self.join_names, self.left_on, self.right_on, strict=True
1248 ):
1249 if (
1250 # Argument 1 to "_is_level_reference" of "NDFrame" has incompatible
1251 # type "Union[Hashable, ExtensionArray, Index, Series]"; expected
1252 # "Hashable"
1253 self.orig_left._is_level_reference(left_key) # type: ignore[arg-type]
1254 # Argument 1 to "_is_level_reference" of "NDFrame" has incompatible
1255 # type "Union[Hashable, ExtensionArray, Index, Series]"; expected
1256 # "Hashable"
1257 and self.orig_right._is_level_reference(
1258 right_key # type: ignore[arg-type]
1259 )
1260 and left_key == right_key
1261 and name not in result.index.names
1262 ):
1263 names_to_restore.append(name)
1265 if names_to_restore:
1266 index = ensure_index_from_sequences(
1267 [result[col] for col in names_to_restore], names_to_restore
1268 )
1269 for col in names_to_restore:
1270 del result[col]
1271 result.index = index
1273 @final
1274 def _maybe_add_join_keys(
1275 self,
1276 result: DataFrame,
1277 left_indexer: npt.NDArray[np.intp] | None,
1278 right_indexer: npt.NDArray[np.intp] | None,
1279 ) -> None:
1280 # Inner joins never produce -1 (missing) in the indexers, so we can
1281 # skip the potentially expensive lib.has_sentinel scans.
1282 if self.how == "inner":
1283 left_has_missing = False
1284 right_has_missing = False
1285 else:
1286 left_has_missing = None
1287 right_has_missing = None
1289 assert all(isinstance(x, _known) for x in self.left_join_keys)
1291 keys = zip(self.join_names, self.left_on, self.right_on, strict=True)
1292 for i, (name, lname, rname) in enumerate(keys):
1293 if not _should_fill(lname, rname):
1294 continue
1296 take_left, take_right = None, None
1298 if name in result:
1299 if left_indexer is not None or right_indexer is not None:
1300 if name in self.left:
1301 if left_has_missing is None:
1302 left_has_missing = (
1303 False
1304 if left_indexer is None
1305 else lib.has_sentinel(left_indexer, -1)
1306 )
1308 right_key_dtype = self.right_join_keys[i].dtype
1309 needs_resolution_cast = (
1310 result[name].dtype.kind == "M"
1311 and right_key_dtype.kind == "M"
1312 and result[name].dtype != right_key_dtype
1313 )
1314 if left_has_missing or needs_resolution_cast:
1315 take_right = self.right_join_keys[i]
1317 if result[name].dtype != self.left[name].dtype:
1318 take_left = self.left[name]._values
1320 elif name in self.right:
1321 if right_has_missing is None:
1322 right_has_missing = (
1323 False
1324 if right_indexer is None
1325 else lib.has_sentinel(right_indexer, -1)
1326 )
1328 left_key_dtype = self.left_join_keys[i].dtype
1329 needs_resolution_cast = (
1330 result[name].dtype.kind == "M"
1331 and left_key_dtype.kind == "M"
1332 and result[name].dtype != left_key_dtype
1333 )
1334 if right_has_missing or needs_resolution_cast:
1335 take_left = self.left_join_keys[i]
1337 if result[name].dtype != self.right[name].dtype:
1338 take_right = self.right[name]._values
1340 else:
1341 take_left = self.left_join_keys[i]
1342 take_right = self.right_join_keys[i]
1344 if take_left is not None or take_right is not None:
1345 if take_left is None:
1346 lvals = result[name]._values
1347 elif left_indexer is None:
1348 lvals = take_left
1349 else:
1350 # TODO: can we pin down take_left's type earlier?
1351 take_left = extract_array(take_left, extract_numpy=True)
1352 lfill = na_value_for_dtype(take_left.dtype)
1353 lvals = algos.take_nd(take_left, left_indexer, fill_value=lfill)
1355 if take_right is None:
1356 rvals = result[name]._values
1357 elif right_indexer is None:
1358 rvals = take_right
1359 else:
1360 # TODO: can we pin down take_right's type earlier?
1361 taker = extract_array(take_right, extract_numpy=True)
1362 rfill = na_value_for_dtype(taker.dtype)
1363 rvals = algos.take_nd(taker, right_indexer, fill_value=rfill)
1365 mask_left = None if left_indexer is None else left_indexer == -1
1367 # if we have an all missing left_indexer
1368 # make sure to just use the right values or vice-versa
1369 if mask_left is not None and mask_left.all():
1370 key_col = Index(rvals, dtype=rvals.dtype, copy=False)
1371 result_dtype = rvals.dtype
1372 elif right_indexer is not None and (right_indexer == -1).all():
1373 key_col = Index(lvals, dtype=lvals.dtype, copy=False)
1374 result_dtype = lvals.dtype
1375 else:
1376 key_col = Index(lvals, dtype=lvals.dtype, copy=False)
1377 if mask_left is not None:
1378 key_col = key_col.where(~mask_left, rvals)
1379 result_dtype = find_common_type([lvals.dtype, rvals.dtype])
1380 if (
1381 lvals.dtype.kind == "M"
1382 and rvals.dtype.kind == "M"
1383 and result_dtype.kind == "O"
1384 ):
1385 # find_common_type returns object for datetimes with
1386 # different timezones; keep the combined datetime key
1387 # dtype instead of degrading to object.
1388 result_dtype = key_col.dtype
1390 if result._is_label_reference(name):
1391 result[name] = result._constructor_sliced(
1392 key_col, dtype=result_dtype, index=result.index
1393 )
1394 elif result._is_level_reference(name):
1395 if isinstance(result.index, MultiIndex):
1396 key_col.name = name
1397 idx_list = [
1398 (
1399 result.index.get_level_values(level_name)
1400 if level_name != name
1401 else key_col
1402 )
1403 for level_name in result.index.names
1404 ]
1406 index = ensure_index_from_sequences(
1407 idx_list, names=[idx.name for idx in idx_list]
1408 )
1409 result.index = index
1410 else:
1411 result.index = Index(key_col, name=name)
1412 else:
1413 result.insert(i, name or f"key_{i}", key_col)
1415 def _get_join_indexers(
1416 self,
1417 ) -> tuple[npt.NDArray[np.intp] | None, npt.NDArray[np.intp] | None]:
1418 """return the join indexers"""
1419 # make mypy happy
1420 assert self.how != "asof"
1421 return get_join_indexers(
1422 self.left_join_keys, self.right_join_keys, sort=self.sort, how=self.how
1423 )
1425 @final
1426 def _get_join_info(
1427 self,
1428 ) -> tuple[Index, npt.NDArray[np.intp] | None, npt.NDArray[np.intp] | None]:
1429 left_ax = self.left.index
1430 right_ax = self.right.index
1432 if self.left_index and self.right_index and self.how != "asof":
1433 join_index, left_indexer, right_indexer = left_ax.join(
1434 right_ax, how=self.how, return_indexers=True, sort=self.sort
1435 )
1437 elif self.right_index and self.how == "left":
1438 join_index, left_indexer, right_indexer = _left_join_on_index(
1439 left_ax, right_ax, self.left_join_keys, sort=self.sort
1440 )
1442 elif self.left_index and self.how == "right":
1443 join_index, right_indexer, left_indexer = _left_join_on_index(
1444 right_ax, left_ax, self.right_join_keys, sort=self.sort
1445 )
1446 else:
1447 (left_indexer, right_indexer) = self._get_join_indexers()
1449 if self.right_index:
1450 if len(self.left) > 0:
1451 join_index = self._create_join_index(
1452 left_ax,
1453 right_ax,
1454 left_indexer,
1455 how="right",
1456 )
1457 elif right_indexer is None:
1458 join_index = right_ax.copy()
1459 else:
1460 join_index = right_ax.take(right_indexer)
1461 elif self.left_index:
1462 if self.how == "asof":
1463 # GH#33463 asof should always behave like a left merge
1464 join_index = self._create_join_index(
1465 left_ax,
1466 right_ax,
1467 left_indexer,
1468 how="left",
1469 )
1471 elif len(self.right) > 0:
1472 join_index = self._create_join_index(
1473 right_ax,
1474 left_ax,
1475 right_indexer,
1476 how="left",
1477 )
1478 elif left_indexer is None:
1479 join_index = left_ax.copy()
1480 else:
1481 join_index = left_ax.take(left_indexer)
1482 else:
1483 n = len(left_ax) if left_indexer is None else len(left_indexer)
1484 join_index = default_index(n)
1486 if self.anti_join:
1487 join_index, left_indexer, right_indexer = self._handle_anti_join(
1488 join_index, left_indexer, right_indexer
1489 )
1491 return join_index, left_indexer, right_indexer
1493 @final
1494 def _create_join_index(
1495 self,
1496 index: Index,
1497 other_index: Index,
1498 indexer: npt.NDArray[np.intp] | None,
1499 how: JoinHow = "left",
1500 ) -> Index:
1501 """
1502 Create a join index by rearranging one index to match another
1504 Parameters
1505 ----------
1506 index : Index
1507 index being rearranged
1508 other_index : Index
1509 used to supply values not found in index
1510 indexer : np.ndarray[np.intp] or None
1511 how to rearrange index
1512 how : str
1513 Replacement is only necessary if indexer based on other_index.
1515 Returns
1516 -------
1517 Index
1518 """
1519 if indexer is None:
1520 return index.copy()
1521 if self.how in (how, "outer") and not isinstance(other_index, MultiIndex):
1522 fill_value = na_value_for_dtype(index.dtype, compat=False)
1523 return index.take(indexer, allow_fill=True, fill_value=fill_value)
1524 return index.take(indexer)
1526 @final
1527 def _handle_anti_join(
1528 self,
1529 join_index: Index,
1530 left_indexer: npt.NDArray[np.intp] | None,
1531 right_indexer: npt.NDArray[np.intp] | None,
1532 ) -> tuple[Index, npt.NDArray[np.intp] | None, npt.NDArray[np.intp] | None]:
1533 """
1534 Handle anti join by returning the correct join index and indexers
1536 Parameters
1537 ----------
1538 join_index : Index
1539 join index
1540 left_indexer : np.ndarray[np.intp] or None
1541 left indexer
1542 right_indexer : np.ndarray[np.intp] or None
1543 right indexer
1545 Returns
1546 -------
1547 Index, np.ndarray[np.intp] or None, np.ndarray[np.intp] or None
1548 """
1549 # Make sure indexers are not None
1550 if left_indexer is None:
1551 left_indexer = np.arange(len(self.left))
1552 if right_indexer is None:
1553 right_indexer = np.arange(len(self.right))
1555 assert self.how in {"left", "right"}
1556 if self.how == "left":
1557 # Filter to rows where left keys are not in right keys
1558 filt = right_indexer == -1
1559 else:
1560 # Filter to rows where right keys are not in left keys
1561 filt = left_indexer == -1
1562 join_index = join_index[filt]
1563 left_indexer = left_indexer[filt]
1564 right_indexer = right_indexer[filt]
1566 return join_index, left_indexer, right_indexer
1568 @final
1569 def _get_merge_keys(
1570 self,
1571 ) -> tuple[
1572 list[ArrayLike],
1573 list[ArrayLike],
1574 list[Hashable],
1575 list[Hashable],
1576 list[Hashable],
1577 ]:
1578 """
1579 Returns
1580 -------
1581 left_keys, right_keys, join_names, left_drop, right_drop
1582 """
1583 left_keys: list[ArrayLike] = []
1584 right_keys: list[ArrayLike] = []
1585 join_names: list[Hashable] = []
1586 right_drop: list[Hashable] = []
1587 left_drop: list[Hashable] = []
1589 left, right = self.left, self.right
1591 is_lkey = lambda x: isinstance(x, _known) and len(x) == len(left)
1592 is_rkey = lambda x: isinstance(x, _known) and len(x) == len(right)
1594 # Note that pd.merge_asof() has separate 'on' and 'by' parameters. A
1595 # user could, for example, request 'left_index' and 'left_by'. In a
1596 # regular pd.merge(), users cannot specify both 'left_index' and
1597 # 'left_on'. (Instead, users have a MultiIndex). That means the
1598 # self.left_on in this function is always empty in a pd.merge(), but
1599 # a pd.merge_asof(left_index=True, left_by=...) will result in a
1600 # self.left_on array with a None in the middle of it. This requires
1601 # a work-around as designated in the code below.
1602 # See _validate_left_right_on() for where this happens.
1604 # ugh, spaghetti re #733
1605 if _any(self.left_on) and _any(self.right_on):
1606 for lk, rk in zip(self.left_on, self.right_on, strict=True):
1607 lk = extract_array(lk, extract_numpy=True)
1608 rk = extract_array(rk, extract_numpy=True)
1609 if is_lkey(lk):
1610 lk = cast("ArrayLike", lk)
1611 left_keys.append(lk)
1612 if is_rkey(rk):
1613 rk = cast("ArrayLike", rk)
1614 right_keys.append(rk)
1615 join_names.append(None) # what to do?
1616 else:
1617 # Then we're either Hashable or a wrong-length arraylike,
1618 # the latter of which will raise
1619 rk = cast("Hashable", rk)
1620 if rk is not None:
1621 right_keys.append(right._get_label_or_level_values(rk))
1622 join_names.append(rk)
1623 else:
1624 # work-around for merge_asof(right_index=True)
1625 right_keys.append(right.index._values)
1626 join_names.append(right.index.name)
1627 else:
1628 if not is_rkey(rk):
1629 # Then we're either Hashable or a wrong-length arraylike,
1630 # the latter of which will raise
1631 rk = cast("Hashable", rk)
1632 if rk is not None:
1633 right_keys.append(right._get_label_or_level_values(rk))
1634 else:
1635 # work-around for merge_asof(right_index=True)
1636 right_keys.append(right.index._values)
1637 if lk is not None and lk == rk: # FIXME: what about other NAs?
1638 right_drop.append(rk)
1639 else:
1640 rk = cast("ArrayLike", rk)
1641 right_keys.append(rk)
1642 if lk is not None:
1643 # Then we're either Hashable or a wrong-length arraylike,
1644 # the latter of which will raise
1645 lk = cast("Hashable", lk)
1646 left_keys.append(left._get_label_or_level_values(lk))
1647 join_names.append(lk)
1648 else:
1649 # work-around for merge_asof(left_index=True)
1650 left_keys.append(left.index._values)
1651 join_names.append(left.index.name)
1652 elif _any(self.left_on):
1653 for k in self.left_on:
1654 if is_lkey(k):
1655 k = extract_array(k, extract_numpy=True)
1656 k = cast("ArrayLike", k)
1657 left_keys.append(k)
1658 join_names.append(None)
1659 else:
1660 # Then we're either Hashable or a wrong-length arraylike,
1661 # the latter of which will raise
1662 k = cast("Hashable", k)
1663 left_keys.append(left._get_label_or_level_values(k))
1664 join_names.append(k)
1665 if isinstance(self.right.index, MultiIndex):
1666 right_keys = [
1667 self.right.index._get_level_values(i)._values
1668 for i in range(self.right.index.nlevels)
1669 ]
1670 else:
1671 right_keys = [self.right.index._values]
1672 elif _any(self.right_on):
1673 for k in self.right_on:
1674 k = extract_array(k, extract_numpy=True)
1675 if is_rkey(k):
1676 k = cast("ArrayLike", k)
1677 right_keys.append(k)
1678 join_names.append(None)
1679 else:
1680 # Then we're either Hashable or a wrong-length arraylike,
1681 # the latter of which will raise
1682 k = cast("Hashable", k)
1683 right_keys.append(right._get_label_or_level_values(k))
1684 join_names.append(k)
1685 if isinstance(self.left.index, MultiIndex):
1686 left_keys = [
1687 self.left.index._get_level_values(i)._values
1688 for i in range(self.left.index.nlevels)
1689 ]
1690 else:
1691 left_keys = [self.left.index._values]
1693 return left_keys, right_keys, join_names, left_drop, right_drop
1695 @final
1696 def _maybe_coerce_merge_keys(self) -> None:
1697 # we have valid merges but we may have to further
1698 # coerce these if they are originally incompatible types
1699 #
1700 # for example if these are categorical, but are not dtype_equal
1701 # or if we have object and integer dtypes
1703 for lk, rk, name in zip(
1704 self.left_join_keys, self.right_join_keys, self.join_names, strict=True
1705 ):
1706 if (len(lk) and not len(rk)) or (not len(lk) and len(rk)):
1707 continue
1709 lk = extract_array(lk, extract_numpy=True)
1710 rk = extract_array(rk, extract_numpy=True)
1712 lk_is_cat = isinstance(lk.dtype, CategoricalDtype)
1713 rk_is_cat = isinstance(rk.dtype, CategoricalDtype)
1714 lk_is_object_or_string = is_object_dtype(lk.dtype) or is_string_dtype(
1715 lk.dtype
1716 )
1717 rk_is_object_or_string = is_object_dtype(rk.dtype) or is_string_dtype(
1718 rk.dtype
1719 )
1721 # if either left or right is a categorical
1722 # then the must match exactly in categories & ordered
1723 if lk_is_cat and rk_is_cat:
1724 lk = cast("Categorical", lk)
1725 rk = cast("Categorical", rk)
1726 if lk._categories_match_up_to_permutation(rk):
1727 continue
1729 elif lk_is_cat or rk_is_cat:
1730 pass
1732 elif lk.dtype == rk.dtype:
1733 continue
1735 msg = (
1736 f"You are trying to merge on {lk.dtype} and {rk.dtype} columns "
1737 f"for key '{name}'. If you wish to proceed you should use pd.concat"
1738 )
1740 # if we are numeric, then allow differing
1741 # kinds to proceed, eg. int64 and int8, int and float
1742 # further if we are object, but we infer to
1743 # the same, then proceed
1744 if is_numeric_dtype(lk.dtype) and is_numeric_dtype(rk.dtype):
1745 if lk.dtype.kind == rk.dtype.kind:
1746 continue
1748 if isinstance(lk.dtype, ExtensionDtype) and not isinstance(
1749 rk.dtype, ExtensionDtype
1750 ):
1751 ct = find_common_type([lk.dtype, rk.dtype])
1752 if isinstance(ct, ExtensionDtype):
1753 com_cls = ct.construct_array_type()
1754 rk = com_cls._from_sequence(rk, dtype=ct, copy=False)
1755 else:
1756 rk = rk.astype(ct, copy=False)
1757 elif isinstance(rk.dtype, ExtensionDtype):
1758 ct = find_common_type([lk.dtype, rk.dtype])
1759 if isinstance(ct, ExtensionDtype):
1760 com_cls = ct.construct_array_type()
1761 lk = com_cls._from_sequence(lk, dtype=ct, copy=False)
1762 else:
1763 lk = lk.astype(ct, copy=False)
1765 # check whether ints and floats
1766 if is_integer_dtype(rk.dtype) and is_float_dtype(lk.dtype):
1767 # GH 47391 numpy > 1.24 will raise a RuntimeError for nan -> int
1768 with np.errstate(invalid="ignore"):
1769 # error: Argument 1 to "astype" of "ndarray" has incompatible
1770 # type "Union[ExtensionDtype, Any, dtype[Any]]"; expected
1771 # "Union[dtype[Any], Type[Any], _SupportsDType[dtype[Any]]]"
1772 casted = lk.astype(rk.dtype) # type: ignore[arg-type]
1774 mask = ~np.isnan(lk)
1775 match = lk == casted
1776 # error: Item "ExtensionArray" of
1777 # "ExtensionArray | Any" has no attribute "all"
1778 if not match[mask].all(): # type: ignore[union-attr]
1779 warnings.warn(
1780 "You are merging on int and float "
1781 "columns where the float values "
1782 "are not equal to their int representation.",
1783 UserWarning,
1784 stacklevel=find_stack_level(),
1785 )
1786 continue
1788 if is_float_dtype(rk.dtype) and is_integer_dtype(lk.dtype):
1789 # GH 47391 numpy > 1.24 will raise a RuntimeError for nan -> int
1790 with np.errstate(invalid="ignore"):
1791 # error: Argument 1 to "astype" of "ndarray" has incompatible
1792 # type "Union[ExtensionDtype, Any, dtype[Any]]"; expected
1793 # "Union[dtype[Any], Type[Any], _SupportsDType[dtype[Any]]]"
1794 casted = rk.astype(lk.dtype) # type: ignore[arg-type]
1796 mask = ~np.isnan(rk)
1797 match = rk == casted
1798 # error: Item "ExtensionArray" of
1799 # "ExtensionArray | Any" has no attribute "all"
1800 if not match[mask].all(): # type: ignore[union-attr]
1801 warnings.warn(
1802 "You are merging on int and float "
1803 "columns where the float values "
1804 "are not equal to their int representation.",
1805 UserWarning,
1806 stacklevel=find_stack_level(),
1807 )
1808 continue
1810 # let's infer and see if we are ok
1811 if lib.infer_dtype(lk, skipna=False) == lib.infer_dtype(
1812 rk, skipna=False
1813 ):
1814 continue
1816 # Check if we are trying to merge on obviously
1817 # incompatible dtypes GH 9780, GH 15800
1819 # bool values are coerced to object
1820 elif (lk_is_object_or_string and is_bool_dtype(rk.dtype)) or (
1821 is_bool_dtype(lk.dtype) and rk_is_object_or_string
1822 ):
1823 pass
1825 # object values are allowed to be merged
1826 elif (lk_is_object_or_string and is_numeric_dtype(rk.dtype)) or (
1827 is_numeric_dtype(lk.dtype) and rk_is_object_or_string
1828 ):
1829 inferred_left = lib.infer_dtype(lk, skipna=False)
1830 inferred_right = lib.infer_dtype(rk, skipna=False)
1831 bool_types = ["integer", "mixed-integer", "boolean", "empty"]
1832 string_types = ["string", "unicode", "mixed", "bytes", "empty"]
1834 # inferred bool
1835 if inferred_left in bool_types and inferred_right in bool_types:
1836 pass
1838 # unless we are merging non-string-like with string-like
1839 elif (
1840 inferred_left in string_types and inferred_right not in string_types
1841 ) or (
1842 inferred_right in string_types and inferred_left not in string_types
1843 ):
1844 raise ValueError(msg)
1846 # datetimelikes must match exactly
1847 elif needs_i8_conversion(lk.dtype) and not needs_i8_conversion(rk.dtype):
1848 raise ValueError(msg)
1849 elif not needs_i8_conversion(lk.dtype) and needs_i8_conversion(rk.dtype):
1850 raise ValueError(msg)
1851 elif isinstance(lk.dtype, DatetimeTZDtype) and not isinstance(
1852 rk.dtype, DatetimeTZDtype
1853 ):
1854 raise ValueError(msg)
1855 elif not isinstance(lk.dtype, DatetimeTZDtype) and isinstance(
1856 rk.dtype, DatetimeTZDtype
1857 ):
1858 raise ValueError(msg)
1859 elif (
1860 isinstance(lk.dtype, DatetimeTZDtype)
1861 and isinstance(rk.dtype, DatetimeTZDtype)
1862 ) or (lk.dtype.kind == "M" and rk.dtype.kind == "M"):
1863 # allows datetime with different resolutions
1864 continue
1865 # datetime and timedelta not allowed
1866 elif lk.dtype.kind == "M" and rk.dtype.kind == "m":
1867 raise ValueError(msg)
1868 elif lk.dtype.kind == "m" and rk.dtype.kind == "M":
1869 raise ValueError(msg)
1871 elif is_object_dtype(lk.dtype) and is_object_dtype(rk.dtype):
1872 continue
1874 # Houston, we have a problem!
1875 # let's coerce to object if the dtypes aren't
1876 # categorical, otherwise coerce to the category
1877 # dtype. If we coerced categories to object,
1878 # then we would lose type information on some
1879 # columns, and end up trying to merge
1880 # incompatible dtypes. See GH 16900.
1881 if name in self.left.columns:
1882 typ = cast("Categorical", lk).categories.dtype if lk_is_cat else object
1883 self.left = self.left.copy(deep=False)
1884 self.left[name] = self.left[name].astype(typ)
1885 if name in self.right.columns:
1886 typ = cast("Categorical", rk).categories.dtype if rk_is_cat else object
1887 self.right = self.right.copy(deep=False)
1888 self.right[name] = self.right[name].astype(typ)
1890 def _validate_left_right_on(self, left_on, right_on):
1891 left_on = com.maybe_make_list(left_on)
1892 right_on = com.maybe_make_list(right_on)
1894 # Hm, any way to make this logic less complicated??
1895 if self.on is None and left_on is None and right_on is None:
1896 if self.left_index and self.right_index:
1897 left_on, right_on = (), ()
1898 elif self.left_index:
1899 raise MergeError("Must pass right_on or right_index=True")
1900 elif self.right_index:
1901 raise MergeError("Must pass left_on or left_index=True")
1902 else:
1903 # use the common columns
1904 left_cols = self.left.columns
1905 right_cols = self.right.columns
1906 common_cols = left_cols.intersection(right_cols)
1907 if len(common_cols) == 0:
1908 raise MergeError(
1909 "No common columns to perform merge on. "
1910 f"Merge options: left_on={left_on}, "
1911 f"right_on={right_on}, "
1912 f"left_index={self.left_index}, "
1913 f"right_index={self.right_index}"
1914 )
1915 if (
1916 not left_cols.join(common_cols, how="inner").is_unique
1917 or not right_cols.join(common_cols, how="inner").is_unique
1918 ):
1919 raise MergeError(f"Data columns not unique: {common_cols!r}")
1920 left_on = right_on = common_cols
1921 elif self.on is not None:
1922 if left_on is not None or right_on is not None:
1923 raise MergeError(
1924 'Can only pass argument "on" OR "left_on" '
1925 'and "right_on", not a combination of both.'
1926 )
1927 if self.left_index or self.right_index:
1928 raise MergeError(
1929 'Can only pass argument "on" OR "left_index" '
1930 'and "right_index", not a combination of both.'
1931 )
1932 left_on = right_on = self.on
1933 elif left_on is not None:
1934 if self.left_index:
1935 raise MergeError(
1936 'Can only pass argument "left_on" OR "left_index" not both.'
1937 )
1938 if not self.right_index and right_on is None:
1939 raise MergeError('Must pass "right_on" OR "right_index".')
1940 if self.right_index and right_on is not None:
1941 raise MergeError(
1942 'Can only pass argument "right_on" OR "right_index" not both.'
1943 )
1944 n = len(left_on)
1945 if self.right_index:
1946 if len(left_on) != self.right.index.nlevels:
1947 raise ValueError(
1948 "len(left_on) must equal the number "
1949 'of levels in the index of "right"'
1950 )
1951 right_on = [None] * n
1952 elif right_on is not None:
1953 if self.right_index:
1954 raise MergeError(
1955 'Can only pass argument "right_on" OR "right_index" not both.'
1956 )
1957 if not self.left_index and left_on is None:
1958 raise MergeError('Must pass "left_on" OR "left_index".')
1959 n = len(right_on)
1960 if self.left_index:
1961 if len(right_on) != self.left.index.nlevels:
1962 raise ValueError(
1963 "len(right_on) must equal the number "
1964 'of levels in the index of "left"'
1965 )
1966 left_on = [None] * n
1967 if len(right_on) != len(left_on):
1968 raise ValueError("len(right_on) must equal len(left_on)")
1970 return left_on, right_on
1972 @final
1973 def _validate_validate_kwd(self, validate: str) -> None:
1974 # Check uniqueness of each
1975 if self.left_index:
1976 left_join_index = self.orig_left.index
1977 left_unique = left_join_index.is_unique
1978 else:
1979 left_join_index = MultiIndex.from_arrays(self.left_join_keys)
1980 left_unique = left_join_index.is_unique
1982 if self.right_index:
1983 right_join_index = self.orig_right.index
1984 right_unique = self.orig_right.index.is_unique
1985 else:
1986 right_join_index = MultiIndex.from_arrays(self.right_join_keys)
1987 right_unique = right_join_index.is_unique
1989 def left_error_msg(x: Index) -> str:
1990 name = self.left_on if not self.left_index else lib.no_default
1991 msg = x[x.duplicated()][:5].to_frame(name=name).to_string(index=False)
1992 return f"\nDuplicates in left:\n {msg} ..."
1994 def right_error_msg(x: Index) -> str:
1995 name = self.right_on if not self.right_index else lib.no_default
1996 msg = x[x.duplicated()][:5].to_frame(name=name).to_string(index=False)
1997 return f"\nDuplicates in right:\n {msg} ..."
1999 # Check data integrity
2000 if validate in ["one_to_one", "1:1"]:
2001 if not left_unique and not right_unique:
2002 raise MergeError(
2003 "Merge keys are not unique in either left "
2004 "or right dataset; not a one-to-one merge."
2005 f"{left_error_msg(left_join_index)}"
2006 f"{right_error_msg(right_join_index)}"
2007 )
2008 if not left_unique:
2009 raise MergeError(
2010 "Merge keys are not unique in left dataset; not a one-to-one merge"
2011 f"{left_error_msg(left_join_index)}"
2012 )
2013 if not right_unique:
2014 raise MergeError(
2015 "Merge keys are not unique in right dataset; not a one-to-one merge"
2016 f"{right_error_msg(right_join_index)}"
2017 )
2019 elif validate in ["one_to_many", "1:m"]:
2020 if not left_unique:
2021 raise MergeError(
2022 "Merge keys are not unique in left dataset; not a one-to-many merge"
2023 f"{left_error_msg(left_join_index)}"
2024 )
2026 elif validate in ["many_to_one", "m:1"]:
2027 if not right_unique:
2028 raise MergeError(
2029 "Merge keys are not unique in right dataset; "
2030 "not a many-to-one merge\n"
2031 f"{right_error_msg(right_join_index)}"
2032 )
2034 elif validate in ["many_to_many", "m:m"]:
2035 pass
2037 else:
2038 raise ValueError(
2039 f'"{validate}" is not a valid argument. '
2040 "Valid arguments are:\n"
2041 '- "1:1"\n'
2042 '- "1:m"\n'
2043 '- "m:1"\n'
2044 '- "m:m"\n'
2045 '- "one_to_one"\n'
2046 '- "one_to_many"\n'
2047 '- "many_to_one"\n'
2048 '- "many_to_many"'
2049 )
2052def _maybe_promote_to_rangeindex(idx: Index) -> Index:
2053 if idx.dtype.kind in "iu" and idx.is_monotonic_increasing and idx.is_unique:
2054 values = idx._values
2055 if isinstance(values, np.ndarray):
2056 result = maybe_sequence_to_range(values)
2057 if isinstance(result, range):
2058 return RangeIndex(result, name=idx.name)
2059 return idx
2062def get_join_indexers(
2063 left_keys: list[ArrayLike],
2064 right_keys: list[ArrayLike],
2065 sort: bool = False,
2066 how: JoinHow = "inner",
2067) -> tuple[npt.NDArray[np.intp] | None, npt.NDArray[np.intp] | None]:
2068 """
2070 Parameters
2071 ----------
2072 left_keys : list[ndarray, ExtensionArray, Index, Series]
2073 right_keys : list[ndarray, ExtensionArray, Index, Series]
2074 sort : bool, default False
2075 how : {'inner', 'outer', 'left', 'right'}, default 'inner'
2077 Returns
2078 -------
2079 np.ndarray[np.intp] or None
2080 Indexer into the left_keys.
2081 np.ndarray[np.intp] or None
2082 Indexer into the right_keys.
2083 """
2084 assert len(left_keys) == len(right_keys), (
2085 "left_keys and right_keys must be the same length"
2086 )
2088 # fast-path for empty left/right
2089 left_n = len(left_keys[0])
2090 right_n = len(right_keys[0])
2091 if left_n == 0:
2092 if how in ["left", "inner"]:
2093 return _get_empty_indexer()
2094 elif not sort and how in ["right", "outer"]:
2095 return _get_no_sort_one_missing_indexer(right_n, True)
2096 elif right_n == 0:
2097 if how in ["right", "inner"]:
2098 return _get_empty_indexer()
2099 elif not sort and how in ["left", "outer"]:
2100 return _get_no_sort_one_missing_indexer(left_n, False)
2102 lkey: ArrayLike
2103 rkey: ArrayLike
2104 if len(left_keys) > 1:
2105 fused = _fuse_int64_keys(left_keys, right_keys)
2106 if fused is not None:
2107 # combine integer-like keys in a single pass, avoiding a
2108 # hashtable factorization per column
2109 lkey, rkey = fused
2110 else:
2111 # get left & right join labels and num. of levels at each location
2112 mapped = (
2113 _factorize_keys(left_keys[n], right_keys[n], sort=sort)
2114 for n in range(len(left_keys))
2115 )
2116 zipped = zip(*mapped, strict=True)
2117 llab, rlab, shape = (list(x) for x in zipped)
2119 # get flat i8 keys from label lists
2120 lkey, rkey = _get_join_keys(llab, rlab, tuple(shape), sort)
2121 else:
2122 lkey = left_keys[0]
2123 rkey = right_keys[0]
2125 left = Index(lkey, copy=False)
2126 right = Index(rkey, copy=False)
2128 if (
2129 left.is_monotonic_increasing
2130 and right.is_monotonic_increasing
2131 and (left.is_unique or right.is_unique)
2132 ):
2133 _, lidx, ridx = left.join(right, how=how, return_indexers=True, sort=sort)
2134 elif not sort and how in ("left", "right"):
2135 lk: ArrayLike
2136 rk: ArrayLike
2137 if how == "left" and not isinstance(right, RangeIndex):
2138 right = _maybe_promote_to_rangeindex(right)
2139 elif how == "right" and not isinstance(left, RangeIndex):
2140 left = _maybe_promote_to_rangeindex(left)
2141 if how == "left":
2142 lk = left._values
2143 if (
2144 isinstance(lk, np.ndarray)
2145 and isinstance(right, RangeIndex)
2146 and lk.dtype.kind in "iu"
2147 ):
2148 ridx = right.get_indexer(lk)
2149 lidx = None
2150 else:
2151 rk = right._values
2152 lidx, ridx = get_join_indexers_non_unique(lk, rk, sort, how)
2153 else:
2154 rk = right._values
2155 if (
2156 isinstance(rk, np.ndarray)
2157 and isinstance(left, RangeIndex)
2158 and rk.dtype.kind in "iu"
2159 ):
2160 lidx = left.get_indexer(rk)
2161 ridx = None
2162 else:
2163 lk = left._values
2164 lidx, ridx = get_join_indexers_non_unique(lk, rk, sort, how)
2165 else:
2166 lk = left._values
2167 rk = right._values
2168 lidx, ridx = get_join_indexers_non_unique(lk, rk, sort, how)
2170 if lidx is not None and is_range_indexer(lidx, len(left)):
2171 lidx = None
2172 if ridx is not None and is_range_indexer(ridx, len(right)):
2173 ridx = None
2174 return lidx, ridx
2177def get_join_indexers_non_unique(
2178 left: ArrayLike,
2179 right: ArrayLike,
2180 sort: bool = False,
2181 how: JoinHow = "inner",
2182) -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp]]:
2183 """
2184 Get join indexers for left and right.
2186 Parameters
2187 ----------
2188 left : ArrayLike
2189 right : ArrayLike
2190 sort : bool, default False
2191 how : {'inner', 'outer', 'left', 'right'}, default 'inner'
2193 Returns
2194 -------
2195 np.ndarray[np.intp]
2196 Indexer into left.
2197 np.ndarray[np.intp]
2198 Indexer into right.
2199 """
2200 lkey, rkey, count = _factorize_keys(left, right, sort=sort, how=how)
2201 if count == -1:
2202 # hash join
2203 return lkey, rkey
2204 if how == "left":
2205 lidx, ridx = libjoin.left_outer_join(lkey, rkey, count, sort=sort)
2206 elif how == "right":
2207 ridx, lidx = libjoin.left_outer_join(rkey, lkey, count, sort=sort)
2208 elif how == "inner":
2209 lidx, ridx = libjoin.inner_join(lkey, rkey, count, sort=sort)
2210 elif how == "outer":
2211 lidx, ridx = libjoin.full_outer_join(lkey, rkey, count)
2212 return lidx, ridx
2215def restore_dropped_levels_multijoin(
2216 left: MultiIndex,
2217 right: MultiIndex,
2218 dropped_level_names,
2219 join_index: Index,
2220 lindexer: npt.NDArray[np.intp],
2221 rindexer: npt.NDArray[np.intp],
2222) -> tuple[FrozenList, FrozenList, FrozenList]:
2223 """
2224 *this is an internal non-public method*
2226 Returns the levels, labels and names of a multi-index to multi-index join.
2227 Depending on the type of join, this method restores the appropriate
2228 dropped levels of the joined multi-index.
2229 The method relies on lindexer, rindexer which hold the index positions of
2230 left and right, where a join was feasible
2232 Parameters
2233 ----------
2234 left : MultiIndex
2235 left index
2236 right : MultiIndex
2237 right index
2238 dropped_level_names : str array
2239 list of non-common level names
2240 join_index : Index
2241 the index of the join between the
2242 common levels of left and right
2243 lindexer : np.ndarray[np.intp]
2244 left indexer
2245 rindexer : np.ndarray[np.intp]
2246 right indexer
2248 Returns
2249 -------
2250 levels : list of Index
2251 levels of combined multiindexes
2252 labels : np.ndarray[np.intp]
2253 labels of combined multiindexes
2254 names : List[Hashable]
2255 names of combined multiindex levels
2257 """
2259 def _convert_to_multiindex(index: Index) -> MultiIndex:
2260 if isinstance(index, MultiIndex):
2261 return index
2262 else:
2263 return MultiIndex.from_arrays([index._values], names=[index.name])
2265 # For multi-multi joins with one overlapping level,
2266 # the returned index if of type Index
2267 # Assure that join_index is of type MultiIndex
2268 # so that dropped levels can be appended
2269 join_index = _convert_to_multiindex(join_index)
2271 join_levels = join_index.levels
2272 join_codes = join_index.codes
2273 join_names = join_index.names
2275 # Iterate through the levels that must be restored
2276 for dropped_level_name in dropped_level_names:
2277 if dropped_level_name in left.names:
2278 idx = left
2279 indexer = lindexer
2280 else:
2281 idx = right
2282 indexer = rindexer
2284 # The index of the level name to be restored
2285 name_idx = idx.names.index(dropped_level_name)
2287 restore_levels = idx.levels[name_idx]
2288 # Inject -1 in the codes list where a join was not possible
2289 # IOW indexer[i]=-1
2290 codes = idx.codes[name_idx]
2291 if indexer is None:
2292 restore_codes = codes
2293 else:
2294 restore_codes = algos.take_nd(codes, indexer, fill_value=-1)
2296 # Use + operator: FrozenList.__add__ returns FrozenList, unpacking returns list
2297 join_levels = join_levels + [restore_levels] # noqa: RUF005
2298 join_codes = join_codes + [restore_codes] # noqa: RUF005
2299 join_names = join_names + [dropped_level_name] # noqa: RUF005
2301 return join_levels, join_codes, join_names
2304class _CrossMergeOperation(_MergeOperation):
2305 """
2306 Fast-path for cross (Cartesian product) merges.
2308 Bypasses key extraction, factorisation, and the hash-join by computing
2309 positional indexers directly with np.repeat / np.tile.
2310 """
2312 def __init__(
2313 self,
2314 left: DataFrame | Series,
2315 right: DataFrame | Series,
2316 suffixes: Suffixes = ("_x", "_y"),
2317 indicator: str | bool = False,
2318 ) -> None:
2319 _left = _validate_operand(left)
2320 _right = _validate_operand(right)
2321 self.left = self.orig_left = _left
2322 self.right = self.orig_right = _right
2323 self.how: JoinHow = "inner"
2324 self.on = None
2325 self.suffixes = suffixes
2326 self.sort = False
2327 self.left_index = False
2328 self.right_index = False
2329 self.indicator = indicator
2330 self.anti_join = False
2331 self.left_on = []
2332 self.right_on = []
2333 self.left_join_keys: list[ArrayLike] = []
2334 self.right_join_keys: list[ArrayLike] = []
2335 self.join_names: list[Hashable] = []
2337 # GH#40993: raise when merging between different levels
2338 if _left.columns.nlevels != _right.columns.nlevels:
2339 raise MergeError(
2340 "Not allowed to merge between different levels. "
2341 f"({_left.columns.nlevels} levels on the left, "
2342 f"{_right.columns.nlevels} on the right)"
2343 )
2345 def _get_join_indexers(
2346 self,
2347 ) -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp]]:
2348 n_left = len(self.left)
2349 n_right = len(self.right)
2350 left_indexer = np.repeat(np.arange(n_left, dtype=np.intp), n_right)
2351 right_indexer = np.tile(np.arange(n_right, dtype=np.intp), n_left)
2352 return left_indexer, right_indexer
2355class _OrderedMerge(_MergeOperation):
2356 _merge_type = "ordered_merge"
2358 def __init__(
2359 self,
2360 left: DataFrame | Series,
2361 right: DataFrame | Series,
2362 on: IndexLabel | None = None,
2363 left_on: IndexLabel | None = None,
2364 right_on: IndexLabel | None = None,
2365 left_index: bool = False,
2366 right_index: bool = False,
2367 suffixes: Suffixes = ("_x", "_y"),
2368 fill_method: str | None = None,
2369 how: JoinHow | Literal["asof"] = "outer",
2370 ) -> None:
2371 self.fill_method = fill_method
2372 _MergeOperation.__init__(
2373 self,
2374 left,
2375 right,
2376 on=on,
2377 left_on=left_on,
2378 left_index=left_index,
2379 right_index=right_index,
2380 right_on=right_on,
2381 how=how,
2382 suffixes=suffixes,
2383 sort=True, # factorize sorts
2384 )
2386 def get_result(self) -> DataFrame:
2387 join_index, left_indexer, right_indexer = self._get_join_info()
2389 left_join_indexer: npt.NDArray[np.intp] | None
2390 right_join_indexer: npt.NDArray[np.intp] | None
2392 if self.fill_method == "ffill":
2393 if left_indexer is None:
2394 left_join_indexer = None
2395 else:
2396 left_join_indexer = libjoin.ffill_indexer(left_indexer)
2397 if right_indexer is None:
2398 right_join_indexer = None
2399 else:
2400 right_join_indexer = libjoin.ffill_indexer(right_indexer)
2401 elif self.fill_method is None:
2402 left_join_indexer = left_indexer
2403 right_join_indexer = right_indexer
2404 else:
2405 raise ValueError("fill_method must be 'ffill' or None")
2407 result = self._reindex_and_concat(
2408 join_index, left_join_indexer, right_join_indexer
2409 )
2410 self._maybe_add_join_keys(result, left_indexer, right_indexer)
2412 return result
2415def _asof_by_function(direction: str):
2416 name = f"asof_join_{direction}_on_X_by_Y"
2417 return getattr(libjoin, name, None)
2420class _AsOfMerge(_OrderedMerge):
2421 _merge_type = "asof_merge"
2423 def __init__(
2424 self,
2425 left: DataFrame | Series,
2426 right: DataFrame | Series,
2427 on: IndexLabel | None = None,
2428 left_on: IndexLabel | None = None,
2429 right_on: IndexLabel | None = None,
2430 left_index: bool = False,
2431 right_index: bool = False,
2432 by=None,
2433 left_by=None,
2434 right_by=None,
2435 suffixes: Suffixes = ("_x", "_y"),
2436 how: Literal["asof"] = "asof",
2437 tolerance=None,
2438 allow_exact_matches: bool = True,
2439 direction: str = "backward",
2440 ) -> None:
2441 self.by = by
2442 self.left_by = left_by
2443 self.right_by = right_by
2444 self.tolerance = tolerance
2445 self.allow_exact_matches = allow_exact_matches
2446 self.direction = direction
2448 # check 'direction' is valid
2449 if self.direction not in ["backward", "forward", "nearest"]:
2450 raise MergeError(f"direction invalid: {self.direction}")
2452 # validate allow_exact_matches
2453 if not is_bool(self.allow_exact_matches):
2454 msg = (
2455 "allow_exact_matches must be boolean, "
2456 f"passed {self.allow_exact_matches}"
2457 )
2458 raise MergeError(msg)
2460 _OrderedMerge.__init__(
2461 self,
2462 left,
2463 right,
2464 on=on,
2465 left_on=left_on,
2466 right_on=right_on,
2467 left_index=left_index,
2468 right_index=right_index,
2469 how=how,
2470 suffixes=suffixes,
2471 fill_method=None,
2472 )
2474 def _validate_left_right_on(self, left_on, right_on):
2475 left_on, right_on = super()._validate_left_right_on(left_on, right_on)
2477 # we only allow on to be a single item for on
2478 if len(left_on) != 1 and not self.left_index:
2479 raise MergeError("can only asof on a key for left")
2481 if len(right_on) != 1 and not self.right_index:
2482 raise MergeError("can only asof on a key for right")
2484 if self.left_index and isinstance(self.left.index, MultiIndex):
2485 raise MergeError("left can only have one index")
2487 if self.right_index and isinstance(self.right.index, MultiIndex):
2488 raise MergeError("right can only have one index")
2490 # set 'by' columns
2491 if self.by is not None:
2492 if self.left_by is not None or self.right_by is not None:
2493 raise MergeError("Can only pass by OR left_by and right_by")
2494 self.left_by = self.right_by = self.by
2495 if self.left_by is None and self.right_by is not None:
2496 raise MergeError("missing left_by")
2497 if self.left_by is not None and self.right_by is None:
2498 raise MergeError("missing right_by")
2500 # GH#29130 Check that merge keys do not have dtype object
2501 if not self.left_index:
2502 left_on_0 = left_on[0] # pyright: ignore[reportOptionalSubscript]
2503 if isinstance(left_on_0, _known):
2504 lo_dtype = left_on_0.dtype
2505 else:
2506 lo_dtype = (
2507 self.left._get_label_or_level_values(left_on_0).dtype
2508 if left_on_0 in self.left.columns
2509 else self.left.index.get_level_values(left_on_0)
2510 )
2511 else:
2512 lo_dtype = self.left.index.dtype
2514 if not self.right_index:
2515 right_on_0 = right_on[0] # pyright: ignore[reportOptionalSubscript]
2516 if isinstance(right_on_0, _known):
2517 ro_dtype = right_on_0.dtype
2518 else:
2519 ro_dtype = (
2520 self.right._get_label_or_level_values(right_on_0).dtype
2521 if right_on_0 in self.right.columns
2522 else self.right.index.get_level_values(right_on_0)
2523 )
2524 else:
2525 ro_dtype = self.right.index.dtype
2527 if (
2528 is_object_dtype(lo_dtype)
2529 or is_object_dtype(ro_dtype)
2530 or is_string_dtype(lo_dtype)
2531 or is_string_dtype(ro_dtype)
2532 ):
2533 raise MergeError(
2534 f"Incompatible merge dtype, {lo_dtype!r} and "
2535 f"{ro_dtype!r}, both sides must have numeric dtype"
2536 )
2538 # add 'by' to our key-list so we can have it in the
2539 # output as a key
2540 if self.left_by is not None:
2541 if not is_list_like(self.left_by):
2542 self.left_by = [self.left_by]
2543 if not is_list_like(self.right_by):
2544 self.right_by = [self.right_by]
2546 if len(self.left_by) != len(self.right_by):
2547 raise MergeError("left_by and right_by must be the same length")
2549 left_on = self.left_by + list(left_on)
2550 right_on = self.right_by + list(right_on) # pyright: ignore[reportOptionalOperand]
2552 return left_on, right_on
2554 def _maybe_require_matching_dtypes(
2555 self, left_join_keys: list[ArrayLike], right_join_keys: list[ArrayLike]
2556 ) -> None:
2557 # TODO: why do we do this for AsOfMerge but not the others?
2559 def _check_dtype_match(left: ArrayLike, right: ArrayLike, i: int) -> None:
2560 if left.dtype != right.dtype:
2561 if isinstance(left.dtype, CategoricalDtype) and isinstance(
2562 right.dtype, CategoricalDtype
2563 ):
2564 # The generic error message is confusing for categoricals.
2565 #
2566 # In this function, the join keys include both the original
2567 # ones of the merge_asof() call, and also the keys passed
2568 # to its by= argument. Unordered but equal categories
2569 # are not supported for the former, but will fail
2570 # later with a ValueError, so we don't *need* to check
2571 # for them here.
2572 msg = (
2573 f"incompatible merge keys [{i}] {left.dtype!r} and "
2574 f"{right.dtype!r}, both sides category, but not equal ones"
2575 )
2576 else:
2577 msg = (
2578 f"incompatible merge keys [{i}] {left.dtype!r} and "
2579 f"{right.dtype!r}, must be the same type"
2580 )
2581 raise MergeError(msg)
2583 # validate index types are the same
2584 for i, (lk, rk) in enumerate(zip(left_join_keys, right_join_keys, strict=True)):
2585 _check_dtype_match(lk, rk, i)
2587 if self.left_index:
2588 lt = self.left.index._values
2589 else:
2590 lt = left_join_keys[-1]
2592 if self.right_index:
2593 rt = self.right.index._values
2594 else:
2595 rt = right_join_keys[-1]
2597 _check_dtype_match(lt, rt, 0)
2599 def _validate_tolerance(self, left_join_keys: list[ArrayLike]) -> None:
2600 # validate tolerance; datetime.timedelta or Timedelta if we have a DTI
2601 if self.tolerance is not None:
2602 if self.left_index:
2603 lt = self.left.index._values
2604 else:
2605 lt = left_join_keys[-1]
2607 msg = (
2608 f"incompatible tolerance {self.tolerance}, must be compat "
2609 f"with type {lt.dtype!r}"
2610 )
2612 if needs_i8_conversion(lt.dtype) or (
2613 isinstance(lt, ArrowExtensionArray) and lt.dtype.kind in "mM"
2614 ):
2615 if not isinstance(self.tolerance, datetime.timedelta):
2616 raise MergeError(msg)
2617 if self.tolerance < Timedelta(0):
2618 raise MergeError("tolerance must be non-negative")
2620 elif is_integer_dtype(lt.dtype):
2621 if not is_integer(self.tolerance):
2622 raise MergeError(msg)
2623 if self.tolerance < 0:
2624 raise MergeError("tolerance must be non-negative")
2626 elif is_float_dtype(lt.dtype):
2627 if not is_number(self.tolerance):
2628 raise MergeError(msg)
2629 # error: Unsupported operand types for > ("int" and "Number")
2630 if self.tolerance < 0: # type: ignore[operator]
2631 raise MergeError("tolerance must be non-negative")
2633 else:
2634 raise MergeError("key must be integer, timestamp or float")
2636 def _convert_values_for_libjoin(
2637 self, values: AnyArrayLike, side: str
2638 ) -> np.ndarray:
2639 # we require sortedness and non-null values in the join keys
2640 if not Index(values, copy=False).is_monotonic_increasing:
2641 if isna(values).any():
2642 raise ValueError(f"Merge keys contain null values on {side} side")
2643 raise ValueError(f"{side} keys must be sorted")
2645 if isinstance(values, ArrowExtensionArray):
2646 values = values._maybe_convert_datelike_array()
2648 if needs_i8_conversion(values.dtype):
2649 values = values.view("i8")
2651 elif isinstance(values, BaseMaskedArray):
2652 # we've verified above that no nulls exist
2653 values = values._data
2654 elif isinstance(values, ExtensionArray):
2655 values = values.to_numpy()
2657 # error: Incompatible return value type (got "Union[ExtensionArray,
2658 # Any, ndarray[Any, Any], ndarray[Any, dtype[Any]], Index, Series]",
2659 # expected "ndarray[Any, Any]")
2660 return values # type: ignore[return-value]
2662 def _get_join_indexers(self) -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp]]:
2663 """return the join indexers"""
2665 # values to compare
2666 left_values = (
2667 self.left.index._values if self.left_index else self.left_join_keys[-1]
2668 )
2669 right_values = (
2670 self.right.index._values if self.right_index else self.right_join_keys[-1]
2671 )
2673 # _maybe_require_matching_dtypes already checked for dtype matching
2674 assert left_values.dtype == right_values.dtype
2676 tolerance = self.tolerance
2677 if tolerance is not None:
2678 # TODO: can we reuse a tolerance-conversion function from
2679 # e.g. TimedeltaIndex?
2680 if needs_i8_conversion(left_values.dtype) or (
2681 isinstance(left_values, ArrowExtensionArray)
2682 and left_values.dtype.kind in "mM"
2683 ):
2684 tolerance = Timedelta(tolerance)
2685 # TODO: we have no test cases with PeriodDtype here; probably
2686 # need to adjust tolerance for that case.
2687 if left_values.dtype.kind in "mM":
2688 # Make sure the i8 representation for tolerance
2689 # matches that for left_values/right_values.
2690 if isinstance(left_values, ArrowExtensionArray):
2691 unit = left_values.dtype.pyarrow_dtype.unit
2692 else:
2693 unit = ensure_wrapped_if_datetimelike(left_values).unit
2694 tolerance = tolerance.as_unit(unit)
2696 tolerance = tolerance._value
2698 # initial type conversion as needed
2699 left_values = self._convert_values_for_libjoin(left_values, "left")
2700 right_values = self._convert_values_for_libjoin(right_values, "right")
2702 # a "by" parameter requires special handling
2703 if self.left_by is not None:
2704 # remove 'on' parameter from values if one existed
2705 if self.left_index and self.right_index:
2706 left_join_keys = self.left_join_keys
2707 right_join_keys = self.right_join_keys
2708 else:
2709 left_join_keys = self.left_join_keys[0:-1]
2710 right_join_keys = self.right_join_keys[0:-1]
2712 if len(left_join_keys) == 1:
2713 lby = left_join_keys[0]
2714 rby = right_join_keys[0]
2715 if isinstance(lby, np.ndarray) and lby.dtype.kind in "biumM":
2716 # Matching dtypes are enforced in
2717 # _maybe_require_matching_dtypes, and the int64
2718 # representation preserves equality, so these values
2719 # can be used as group keys directly without
2720 # factorizing.
2721 left_by_values = lby.astype(np.int64, copy=False)
2722 right_by_values = rby.astype(np.int64, copy=False)
2723 else:
2724 left_by_values, right_by_values, _ = _factorize_keys(
2725 lby, rby, sort=False
2726 )
2727 else:
2728 mapped = [
2729 _factorize_keys(
2730 left_join_keys[n],
2731 right_join_keys[n],
2732 sort=False,
2733 )
2734 for n in range(len(left_join_keys))
2735 ]
2736 arrs = [np.concatenate(m[:2]) for m in mapped]
2737 shape = tuple(m[2] for m in mapped)
2738 group_index = get_group_index(
2739 arrs, shape=shape, sort=False, xnull=False
2740 )
2741 left_len = len(left_join_keys[0])
2742 left_by_values = group_index[:left_len]
2743 right_by_values = group_index[left_len:]
2745 left_by_values = ensure_int64(left_by_values)
2746 right_by_values = ensure_int64(right_by_values)
2748 # choose appropriate function by type
2749 func = _asof_by_function(self.direction)
2750 return func( # pyright: ignore[reportOptionalCall]
2751 left_values,
2752 right_values,
2753 left_by_values,
2754 right_by_values,
2755 self.allow_exact_matches,
2756 tolerance,
2757 )
2758 else:
2759 # choose appropriate function by type
2760 func = _asof_by_function(self.direction)
2761 return func( # pyright: ignore[reportOptionalCall]
2762 left_values,
2763 right_values,
2764 None,
2765 None,
2766 self.allow_exact_matches,
2767 tolerance,
2768 False,
2769 )
2772def _get_multiindex_indexer(
2773 join_keys: list[ArrayLike], index: MultiIndex, sort: bool
2774) -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp]]:
2775 # left & right join labels and num. of levels at each location
2776 mapped = (
2777 _factorize_keys(index.levels[n]._values, join_keys[n], sort=sort)
2778 for n in range(index.nlevels)
2779 )
2780 zipped = zip(*mapped, strict=True)
2781 rcodes, lcodes, shape = (list(x) for x in zipped)
2782 if sort:
2783 rcodes = list(map(np.take, rcodes, index.codes))
2784 else:
2785 i8copy = lambda a: a.astype("i8", subok=False)
2786 rcodes = list(map(i8copy, index.codes))
2788 # fix right labels if there were any nulls
2789 for i, join_key in enumerate(join_keys):
2790 mask = index.codes[i] == -1
2791 if mask.any():
2792 # check if there already was any nulls at this location
2793 # if there was, it is factorized to `shape[i] - 1`
2794 a = join_key[lcodes[i] == shape[i] - 1]
2795 if a.size == 0 or not a[0] != a[0]:
2796 shape[i] += 1
2798 rcodes[i][mask] = shape[i] - 1
2800 # get flat i8 join keys
2801 lkey, rkey = _get_join_keys(lcodes, rcodes, tuple(shape), sort)
2802 return lkey, rkey
2805def _get_empty_indexer() -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp]]:
2806 """Return empty join indexers."""
2807 return (
2808 np.array([], dtype=np.intp),
2809 np.array([], dtype=np.intp),
2810 )
2813def _get_no_sort_one_missing_indexer(
2814 n: int, left_missing: bool
2815) -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp]]:
2816 """
2817 Return join indexers where all of one side is selected without sorting
2818 and none of the other side is selected.
2820 Parameters
2821 ----------
2822 n : int
2823 Length of indexers to create.
2824 left_missing : bool
2825 If True, the left indexer will contain only -1's.
2826 If False, the right indexer will contain only -1's.
2828 Returns
2829 -------
2830 np.ndarray[np.intp]
2831 Left indexer
2832 np.ndarray[np.intp]
2833 Right indexer
2834 """
2835 idx = np.arange(n, dtype=np.intp)
2836 idx_missing = np.full(shape=n, fill_value=-1, dtype=np.intp)
2837 if left_missing:
2838 return idx_missing, idx
2839 return idx, idx_missing
2842def _left_join_on_index(
2843 left_ax: Index, right_ax: Index, join_keys: list[ArrayLike], sort: bool = False
2844) -> tuple[Index, npt.NDArray[np.intp] | None, npt.NDArray[np.intp]]:
2845 if isinstance(right_ax, MultiIndex):
2846 lkey, rkey = _get_multiindex_indexer(join_keys, right_ax, sort=sort)
2847 else:
2848 # error: Incompatible types in assignment (expression has type
2849 # "Union[Union[ExtensionArray, ndarray[Any, Any]], Index, Series]",
2850 # variable has type "ndarray[Any, dtype[signedinteger[Any]]]")
2851 lkey = join_keys[0] # type: ignore[assignment]
2852 # error: Incompatible types in assignment (expression has type "Index",
2853 # variable has type "ndarray[Any, dtype[signedinteger[Any]]]")
2854 rkey = right_ax._values # type: ignore[assignment]
2856 left_key, right_key, count = _factorize_keys(lkey, rkey, sort=sort, how="left")
2857 if count == -1:
2858 left_indexer, right_indexer = left_key, right_key
2859 else:
2860 left_indexer, right_indexer = libjoin.left_outer_join(
2861 left_key, right_key, count, sort=sort
2862 )
2864 if sort or len(left_ax) != len(left_indexer):
2865 # if asked to sort or there are 1-to-many matches
2866 join_index = left_ax.take(left_indexer)
2867 return join_index, left_indexer, right_indexer
2869 # left frame preserves order & length of its index
2870 return left_ax, None, right_indexer
2873def _factorize_keys(
2874 lk: ArrayLike,
2875 rk: ArrayLike,
2876 sort: bool = True,
2877 how: str | None = None,
2878) -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp], int]:
2879 """
2880 Encode left and right keys as enumerated types.
2882 This is used to get the join indexers to be used when merging DataFrames.
2884 Parameters
2885 ----------
2886 lk : ndarray, ExtensionArray
2887 Left key.
2888 rk : ndarray, ExtensionArray
2889 Right key.
2890 sort : bool, defaults to True
2891 If True, the encoding is done such that the unique elements in the
2892 keys are sorted.
2893 how: str, optional
2894 Used to determine if we can use hash-join. If not given, then just factorize
2895 keys.
2897 Returns
2898 -------
2899 np.ndarray[np.intp]
2900 Left (resp. right if called with `key='right'`) labels, as enumerated type.
2901 np.ndarray[np.intp]
2902 Right (resp. left if called with `key='right'`) labels, as enumerated type.
2903 int
2904 Number of unique elements in union of left and right labels. -1 if we used
2905 a hash-join.
2907 See Also
2908 --------
2909 merge : Merge DataFrame or named Series objects
2910 with a database-style join.
2911 algorithms.factorize : Encode the object as an enumerated type
2912 or categorical variable.
2914 Examples
2915 --------
2916 >>> lk = np.array(["a", "c", "b"])
2917 >>> rk = np.array(["a", "c"])
2919 Here, the unique values are `'a', 'b', 'c'`. With the default
2920 `sort=True`, the encoding will be `{0: 'a', 1: 'b', 2: 'c'}`:
2922 >>> pd.core.reshape.merge._factorize_keys(lk, rk)
2923 (array([0, 2, 1]), array([0, 2]), 3)
2925 With the `sort=False`, the encoding will correspond to the order
2926 in which the unique elements first appear: `{0: 'a', 1: 'c', 2: 'b'}`:
2928 >>> pd.core.reshape.merge._factorize_keys(lk, rk, sort=False)
2929 (array([0, 1, 2]), array([0, 1]), 3)
2930 """
2931 # TODO: if either is a RangeIndex, we can likely factorize more efficiently?
2933 if (
2934 isinstance(lk.dtype, DatetimeTZDtype) and isinstance(rk.dtype, DatetimeTZDtype)
2935 ) or (lib.is_np_dtype(lk.dtype, "M") and lib.is_np_dtype(rk.dtype, "M")):
2936 # Extract the ndarray (UTC-localized) values
2937 # Note: we dont need the dtypes to match, as these can still be compared
2938 lk, rk = cast("DatetimeArray", lk)._ensure_matching_resos(rk)
2939 lk = cast("DatetimeArray", lk)._ndarray
2940 rk = cast("DatetimeArray", rk)._ndarray
2942 elif (
2943 isinstance(lk.dtype, CategoricalDtype)
2944 and isinstance(rk.dtype, CategoricalDtype)
2945 and lk.dtype == rk.dtype
2946 ):
2947 assert isinstance(lk, Categorical)
2948 assert isinstance(rk, Categorical)
2949 # Cast rk to encoding so we can compare codes with lk
2951 rk = lk._encode_with_my_categories(rk)
2953 lk = ensure_int64(lk.codes)
2954 rk = ensure_int64(rk.codes)
2956 elif isinstance(lk, ExtensionArray) and lk.dtype == rk.dtype:
2957 if isinstance(lk.dtype, ArrowDtype) or (
2958 isinstance(lk.dtype, StringDtype) and lk.dtype.storage == "pyarrow"
2959 ):
2960 import pyarrow as pa
2962 from pandas.compat.pyarrow import _safe_fill_null
2964 len_lk = len(lk)
2965 lk = lk._pa_array # type: ignore[attr-defined]
2966 rk = rk._pa_array # type: ignore[union-attr]
2967 dc = (
2968 pa.chunked_array(lk.chunks + rk.chunks) # type: ignore[union-attr]
2969 .combine_chunks()
2970 .dictionary_encode()
2971 )
2973 # copy: on 32-bit, intp is int32 and to_numpy is a read-only view
2974 # that putmask below would fail on, GH#57523
2975 llab, rlab, count = (
2976 _safe_fill_null(dc.indices[slice(len_lk)], -1)
2977 .to_numpy()
2978 .astype(np.intp),
2979 _safe_fill_null(dc.indices[slice(len_lk, None)], -1)
2980 .to_numpy()
2981 .astype(np.intp),
2982 len(dc.dictionary),
2983 )
2985 if sort:
2986 uniques = dc.dictionary.to_numpy(zero_copy_only=False)
2987 llab, rlab = _sort_labels(uniques, llab, rlab)
2989 if dc.null_count > 0:
2990 lmask = llab == -1
2991 lany = lmask.any()
2992 rmask = rlab == -1
2993 rany = rmask.any()
2994 if lany:
2995 np.putmask(llab, lmask, count)
2996 if rany:
2997 np.putmask(rlab, rmask, count)
2998 count += 1
2999 return llab, rlab, count
3001 if not isinstance(lk, BaseMaskedArray):
3002 lk, _ = lk._values_for_factorize()
3004 # error: Item "ndarray" of "Union[Any, ndarray]" has no attribute
3005 # "_values_for_factorize"
3006 rk, _ = rk._values_for_factorize() # type: ignore[union-attr]
3008 if needs_i8_conversion(lk.dtype) and lk.dtype == rk.dtype:
3009 # GH#23917 TODO: Needs tests for non-matching dtypes
3010 # GH#23917 TODO: needs tests for case where lk is integer-dtype
3011 # and rk is datetime-dtype
3012 lk = np.asarray(lk, dtype=np.int64)
3013 rk = np.asarray(rk, dtype=np.int64)
3015 klass, lk, rk = _convert_arrays_and_get_rizer_klass(lk, rk)
3017 uses_mask = isinstance(rk, (BaseMaskedArray, ArrowExtensionArray))
3018 rizer = klass(max(len(lk), len(rk)), uses_mask=uses_mask)
3020 if isinstance(lk, BaseMaskedArray):
3021 assert isinstance(rk, BaseMaskedArray)
3022 lk_data, lk_mask = lk._data, lk._mask
3023 rk_data, rk_mask = rk._data, rk._mask
3024 elif isinstance(lk, ArrowExtensionArray):
3025 assert isinstance(rk, ArrowExtensionArray)
3026 # we can only get here with numeric dtypes
3027 # TODO: Remove when we have a Factorizer for Arrow
3028 lk_data = lk.to_numpy(na_value=1, dtype=lk.dtype.numpy_dtype)
3029 rk_data = rk.to_numpy(na_value=1, dtype=lk.dtype.numpy_dtype)
3030 lk_mask, rk_mask = lk.isna(), rk.isna()
3031 else:
3032 # Argument 1 to "factorize" of "ObjectFactorizer" has incompatible type
3033 # "Union[ndarray[Any, dtype[signedinteger[_64Bit]]],
3034 # ndarray[Any, dtype[object_]]]"; expected "ndarray[Any, dtype[object_]]"
3035 lk_data, rk_data = lk, rk # type: ignore[assignment]
3036 lk_mask, rk_mask = None, None
3038 hash_join_available = (
3039 how in ("inner", "left") and not sort and lk.dtype.kind in "iufb"
3040 )
3041 if hash_join_available:
3042 rlab = rizer.factorize(rk_data, mask=rk_mask)
3043 if rizer.get_count() == len(rlab):
3044 # GH#38418 Use lookup instead of hash_inner_join for unique right
3045 # keys. lookup pre-allocates the result array and fills directly,
3046 # avoiding dynamic vector resizing and scatter.
3047 ridx = rizer.table.lookup(lk_data, lk_mask) # type: ignore[attr-defined]
3048 if how == "inner":
3049 mask = ridx != -1
3050 lidx = mask.nonzero()[0].astype(np.intp, copy=False)
3051 ridx = ridx[mask].astype(np.intp, copy=False)
3052 return lidx, ridx, -1
3053 # left-outer hash join with unique right side.
3054 # One output row per left row, ridx=-1 for unmatched rows.
3055 return np.arange(len(lk_data), dtype=np.intp), ridx, -1
3056 else:
3057 llab = rizer.factorize(lk_data, mask=lk_mask)
3058 else:
3059 llab = rizer.factorize(lk_data, mask=lk_mask)
3060 rlab = rizer.factorize(rk_data, mask=rk_mask)
3062 assert llab.dtype == np.dtype(np.intp), llab.dtype
3063 assert rlab.dtype == np.dtype(np.intp), rlab.dtype
3065 count = rizer.get_count()
3067 if sort:
3068 uniques = rizer.uniques.to_array()
3069 if uniques.dtype.kind in "iufb":
3070 # Faster equivalent to _sort_labels: look up each sorted unique
3071 # in the factorizer's hashtable to recover its original code
3072 # (np.sort + lookup is cheaper than argsort), then invert that
3073 # permutation to map old codes to sorted-order codes.
3074 # NAs never enter the table, so the lookup mask is all-False.
3075 lookup_mask = np.zeros(len(uniques), dtype=np.uint8) if uses_mask else None
3076 sorter = rizer.table.lookup( # type: ignore[attr-defined]
3077 np.sort(uniques), mask=lookup_mask
3078 )
3079 ranks = np.empty(len(sorter), dtype=np.intp)
3080 ranks[sorter] = np.arange(len(sorter), dtype=np.intp)
3081 llab = algos.take_nd(ranks, llab, fill_value=-1)
3082 rlab = algos.take_nd(ranks, rlab, fill_value=-1)
3083 else:
3084 llab, rlab = _sort_labels(uniques, llab, rlab)
3086 # NA group
3087 lmask = llab == -1
3088 lany = lmask.any()
3089 rmask = rlab == -1
3090 rany = rmask.any()
3092 if lany or rany:
3093 if lany:
3094 np.putmask(llab, lmask, count)
3095 if rany:
3096 np.putmask(rlab, rmask, count)
3097 count += 1
3099 return llab, rlab, count
3102def _convert_arrays_and_get_rizer_klass(
3103 lk: ArrayLike, rk: ArrayLike
3104) -> tuple[type[libhashtable.Factorizer], ArrayLike, ArrayLike]:
3105 klass: type[libhashtable.Factorizer]
3106 if is_numeric_dtype(lk.dtype):
3107 if lk.dtype != rk.dtype:
3108 dtype = find_common_type([lk.dtype, rk.dtype])
3109 if isinstance(dtype, ExtensionDtype):
3110 cls = dtype.construct_array_type()
3111 if not isinstance(lk, ExtensionArray):
3112 lk = cls._from_sequence(lk, dtype=dtype, copy=False)
3113 else:
3114 lk = lk.astype(dtype, copy=False)
3116 if not isinstance(rk, ExtensionArray):
3117 rk = cls._from_sequence(rk, dtype=dtype, copy=False)
3118 else:
3119 rk = rk.astype(dtype, copy=False)
3120 else:
3121 lk = lk.astype(dtype, copy=False)
3122 rk = rk.astype(dtype, copy=False)
3123 if isinstance(lk, BaseMaskedArray):
3124 klass = _factorizers[lk.dtype.type]
3125 elif isinstance(lk.dtype, ArrowDtype):
3126 klass = _factorizers[lk.dtype.numpy_dtype.type]
3127 else:
3128 klass = _factorizers[lk.dtype.type]
3130 else:
3131 klass = libhashtable.ObjectFactorizer
3132 lk = ensure_object(lk)
3133 rk = ensure_object(rk)
3134 return klass, lk, rk
3137def _sort_labels(
3138 uniques: np.ndarray, left: npt.NDArray[np.intp], right: npt.NDArray[np.intp]
3139) -> tuple[npt.NDArray[np.intp], npt.NDArray[np.intp]]:
3140 llength = len(left)
3141 labels = np.concatenate([left, right])
3143 # `uniques` come from a Factorizer, so are unique by construction and
3144 # all `labels` are in-bounds
3145 _, new_labels = algos.safe_sort(
3146 uniques, labels, use_na_sentinel=True, assume_unique=True, verify=False
3147 )
3148 new_left, new_right = new_labels[:llength], new_labels[llength:]
3150 return new_left, new_right
3153def _get_join_keys(
3154 llab: list[npt.NDArray[np.int64 | np.intp]],
3155 rlab: list[npt.NDArray[np.int64 | np.intp]],
3156 shape: Shape,
3157 sort: bool,
3158) -> tuple[npt.NDArray[np.int64], npt.NDArray[np.int64]]:
3159 # how many levels can be done without overflow
3160 nlev = next(
3161 lev
3162 for lev in range(len(shape), 0, -1)
3163 if not is_int64_overflow_possible(shape[:lev])
3164 )
3166 # get keys for the first `nlev` levels
3167 stride = np.prod(shape[1:nlev], dtype="i8")
3168 lkey = stride * llab[0].astype("i8", subok=False, copy=False)
3169 rkey = stride * rlab[0].astype("i8", subok=False, copy=False)
3171 for i in range(1, nlev):
3172 with np.errstate(divide="ignore"):
3173 stride //= shape[i]
3174 lkey += llab[i] * stride
3175 rkey += rlab[i] * stride
3177 if nlev == len(shape): # all done!
3178 return lkey, rkey
3180 # densify current keys to avoid overflow
3181 lkey, rkey, count = _factorize_keys(lkey, rkey, sort=sort)
3183 llab = [lkey, *llab[nlev:]]
3184 rlab = [rkey, *rlab[nlev:]]
3185 shape = (count, *shape[nlev:])
3187 return _get_join_keys(llab, rlab, shape, sort)
3190def _fuse_key_view(arr: ArrayLike) -> np.ndarray | None:
3191 """
3192 Integer-valued view of a key column for fusing, or None if unsupported.
3193 """
3194 dtype = arr.dtype
3195 if isinstance(dtype, np.dtype):
3196 if dtype.kind in "mM":
3197 # raw ndarray or numpy-backed DatetimeArray/TimedeltaArray
3198 values = (
3199 arr if isinstance(arr, np.ndarray) else getattr(arr, "_ndarray", None)
3200 )
3201 if isinstance(values, np.ndarray) and values.dtype.isnative:
3202 return values.view(np.int64)
3203 elif isinstance(arr, np.ndarray):
3204 if dtype.kind in "iu":
3205 return arr
3206 if dtype.kind == "b":
3207 return arr.view(np.uint8)
3208 elif isinstance(dtype, DatetimeTZDtype):
3209 i8values = getattr(arr, "_ndarray", None)
3210 if isinstance(i8values, np.ndarray):
3211 return i8values.view(np.int64)
3212 return None
3215def _shift_to_int64(
3216 values: np.ndarray, cmin: int, stride: int
3217) -> npt.NDArray[np.int64]:
3218 """
3219 Compute (values - cmin) * stride as int64, given that the true results
3220 all lie in [0, 2**63), so any intermediate wraparound is exact mod-2**64
3221 arithmetic.
3222 """
3223 if cmin >= 2**63:
3224 # uint64-only value; wrap to the int64 representation
3225 cmin -= 2**64
3226 result = values.astype(np.int64) # always copies, so in-place ops are safe
3227 if cmin != 0:
3228 result -= np.int64(cmin)
3229 if stride != 1:
3230 result *= stride
3231 return result
3234def _fuse_int64_keys(
3235 left_keys: list[ArrayLike], right_keys: list[ArrayLike]
3236) -> tuple[npt.NDArray[np.int64], npt.NDArray[np.int64]] | None:
3237 """
3238 Fuse integer-like key columns into a single int64 key per side.
3240 Combining the raw values arithmetically lets the composite key be
3241 factorized in a single hash pass, instead of one hash pass per column
3242 plus another over the combined codes. The fused keys are ordered like
3243 the lexicographic order of the key tuples, so both sort=True and the
3244 monotonic fast paths behave the same as with per-column factorization.
3246 Returns None (caller falls back to per-column factorization) if the
3247 keys are not all integer-viewable numpy arrays or the combined key
3248 space does not fit in int64.
3249 """
3250 if len(left_keys[0]) == 0 or len(right_keys[0]) == 0:
3251 # min/max below need non-empty arrays; not a perf-relevant case
3252 return None
3254 lviews = []
3255 rviews = []
3256 for lk, rk in zip(left_keys, right_keys, strict=True):
3257 if lk.dtype != rk.dtype and not (
3258 isinstance(lk.dtype, np.dtype)
3259 and isinstance(rk.dtype, np.dtype)
3260 and lk.dtype.kind in "iu"
3261 and rk.dtype.kind in "iu"
3262 and np.promote_types(lk.dtype, rk.dtype).kind in "iu"
3263 ):
3264 # fuse mismatched dtypes only if they promote losslessly to a
3265 # numpy integer; e.g. uint64 with a signed dtype would go
3266 # through float64 in the fallback path
3267 return None
3268 lview = _fuse_key_view(lk)
3269 rview = _fuse_key_view(rk)
3270 if lview is None or rview is None:
3271 return None
3272 lviews.append(lview)
3273 rviews.append(rview)
3275 mins = []
3276 spans = []
3277 total = 1
3278 for lview, rview in zip(lviews, rviews, strict=True):
3279 cmin = min(int(lview.min()), int(rview.min()))
3280 cmax = max(int(lview.max()), int(rview.max()))
3281 mins.append(cmin)
3282 spans.append(cmax - cmin + 1)
3283 total *= cmax - cmin + 1
3284 if total >= lib.i8max:
3285 # combined key space does not fit in int64
3286 return None
3288 stride = total // spans[0]
3289 lkey = _shift_to_int64(lviews[0], mins[0], stride)
3290 rkey = _shift_to_int64(rviews[0], mins[0], stride)
3291 for lview, rview, cmin, span in zip(
3292 lviews[1:], rviews[1:], mins[1:], spans[1:], strict=True
3293 ):
3294 stride //= span
3295 lkey += _shift_to_int64(lview, cmin, stride)
3296 rkey += _shift_to_int64(rview, cmin, stride)
3297 return lkey, rkey
3300def _should_fill(lname, rname) -> bool:
3301 if not isinstance(lname, str) or not isinstance(rname, str):
3302 return True
3303 return lname == rname
3306def _any(x) -> bool:
3307 return x is not None and com.any_not_none(*x)
3310def _validate_operand(obj: DataFrame | Series) -> DataFrame:
3311 if isinstance(obj, ABCDataFrame):
3312 return obj
3313 elif isinstance(obj, ABCSeries):
3314 if obj.name is None:
3315 raise ValueError("Cannot merge a Series without a name")
3316 return obj.to_frame()
3317 else:
3318 raise TypeError(
3319 f"Can only merge Series or DataFrame objects, a {type(obj)} was passed"
3320 )
3323def _items_overlap_with_suffix(
3324 left: Index, right: Index, suffixes: Suffixes
3325) -> tuple[Index, Index]:
3326 """
3327 Suffixes type validation.
3329 If two indices overlap, add suffixes to overlapping entries.
3331 If corresponding suffix is empty, the entry is simply converted to string.
3333 """
3334 if not is_list_like(suffixes, allow_sets=False) or isinstance(suffixes, dict):
3335 raise TypeError(
3336 f"Passing 'suffixes' as a {type(suffixes)}, is not supported. "
3337 "Provide 'suffixes' as a tuple instead."
3338 )
3340 to_rename = left.intersection(right)
3341 if len(to_rename) == 0:
3342 return left, right
3344 lsuffix, rsuffix = suffixes
3346 if not lsuffix and not rsuffix:
3347 raise ValueError(f"columns overlap but no suffix specified: {to_rename}")
3349 def renamer(x, suffix: str | None):
3350 """
3351 Rename the left and right indices.
3353 If there is overlap, and suffix is not None, add
3354 suffix, otherwise, leave it as-is.
3356 Parameters
3357 ----------
3358 x : original column name
3359 suffix : str or None
3361 Returns
3362 -------
3363 x : renamed column name
3364 """
3365 if x in to_rename and suffix is not None:
3366 return f"{x}{suffix}"
3367 return x
3369 lrenamer = partial(renamer, suffix=lsuffix)
3370 rrenamer = partial(renamer, suffix=rsuffix)
3372 llabels = left._transform_index(lrenamer)
3373 rlabels = right._transform_index(rrenamer)
3375 dups = []
3376 if not llabels.is_unique:
3377 # Only warn when duplicates are caused because of suffixes, already duplicated
3378 # columns in origin should not warn
3379 dups.extend(llabels[(llabels.duplicated()) & (~left.duplicated())].tolist())
3380 if not rlabels.is_unique:
3381 dups.extend(rlabels[(rlabels.duplicated()) & (~right.duplicated())].tolist())
3382 # Suffix addition creates duplicate to pre-existing column name
3383 dups.extend(llabels.intersection(right.difference(to_rename)).tolist())
3384 dups.extend(rlabels.intersection(left.difference(to_rename)).tolist())
3385 if dups:
3386 raise MergeError(
3387 f"Passing 'suffixes' which cause duplicate columns {set(dups)} is "
3388 "not allowed.",
3389 )
3391 return llabels, rlabels