BUG: `merge_asof` gives incorrect results when `by` consists of multiple categorical columns with equal, but differently ordered, categories

[marcozugno]

Observing that merge_asof gives unexpected output when:

• by includes more than one column, one of which is categorical
• categorical columns included in by have equal categories but with different order in left/right dataframes

It seems to me the issue is caused by the categorical columns being cast to their codes during the call to flip in _get_join_indexers when by includes more than one column, causing the misalignment. Categorical columns' dtypes are checked for equality, but the check only fails when they have different categories.

A minimal example of the issue can be set up as follows:

df_left = pd.DataFrame({
    "c1": ["a", "a", "b", "b"],
    "c2": ["x"] * 4,
    "t": [1] * 4,
    "v": range(4)
}).sort_values("t")

df_right = pd.DataFrame({
    "c1": ["b", "b"],
    "c2": ["x"] * 2,
    "t": [1, 2],
    "v": range(2)
}).sort_values("t")

df_left_cat = df_left.copy().astype({"c1": pd.CategoricalDtype(["a", "b"])})

df_right_cat = df_right.copy().astype({"c1": pd.CategoricalDtype(["b", "a"])})  # order of categories is inverted on purpose

Performing merge_asof on dataframes where the by columns are of object dtype works as expected:

pd.merge_asof(df_left, df_right, by=["c1", "c2"], on="t", direction="forward", suffixes=["_left", "_right"])

	c1	c2	t	v_left	v_right
0	a	x	1	0	NaN
1	a	x	1	1	NaN
2	b	x	1	2	0.0
3	b	x	1	3	0.0

When using dataframes with categorical columns as defined above, however, the result is not the expected one:

pd.merge_asof(df_left_cat, df_right_cat, by=["c1", "c2"], on="t", direction="forward", suffixes=["_left", "_right"])

	c1	c2	t	v_left	v_right
0	a	x	1	0	0.0
1	a	x	1	1	0.0
2	b	x	1	2	NaN
3	b	x	1	3	NaN

I ran this with the latest version of pandas at the time of writing (1.3.3). Output of pd.show_versions():

INSTALLED VERSIONS

commit : 73c6825
python : 3.9.2.final.0
python-bits : 64
OS : Darwin
OS-release : 20.6.0
Version : Darwin Kernel Version 20.6.0: Wed Jun 23 00:26:27 PDT 2021; root:xnu-7195.141.2~5/RELEASE_ARM64_T8101
machine : arm64
processor : arm
byteorder : little
LC_ALL : None
LANG : None
LOCALE : None.UTF-8

pandas : 1.3.3
numpy : 1.21.1
pytz : 2021.1
dateutil : 2.8.2
pip : 21.0.1
setuptools : 52.0.0
Cython : None
pytest : None
hypothesis : None
sphinx : None
blosc : None
feather : None
xlsxwriter : None
lxml.etree : None
html5lib : None
pymysql : None
psycopg2 : None
jinja2 : 3.0.1
IPython : 7.27.0
pandas_datareader: None
bs4 : None
bottleneck : None
fsspec : None
fastparquet : None
gcsfs : None
matplotlib : None
numexpr : None
odfpy : None
openpyxl : None
pandas_gbq : None
pyarrow : None
pyxlsb : None
s3fs : None
scipy : None
sqlalchemy : None
tables : None
tabulate : None
xarray : None
xlrd : None
xlwt : None
numba : None

[marcozugno]

Somehow related to #26249

However, reading that issue it seems to me like merge_asof should already raise an exception if called on unordered categories for a merge key, which is not happening.