BUG: merge with MultiIndex including a CategoricalIndex returns wrong result when values are ordered specifically

[ant1j]

Code Sample

import pandas as pd
import numpy as np

c1 = ['A',  'C',  'C',  'D' ]
c2 = ['P2', 'P2', 'P1', 'P2']

df1 = pd.DataFrame({
    'id': c1[1:], 
    'p':  c2[1:], 
    'a':  np.arange(len(c1[1:])),
})
df2 = pd.DataFrame({
    'id': c1[:-1], 
    'p':  c2[:-1], 
    'd1': np.arange(10, 10+len(c1[:-1])),
})

# ordered=True doesn't change the result
pcat = pd.api.types.CategoricalDtype(categories=['P2', 'P1'], ordered=False)

df1['p'] = df1['p'].astype(pcat)
df2['p'] = df2['p'].astype(pcat)

df1 = df1.set_index(['id', 'p'])
df2 = df2.set_index(['id', 'p'])

result = pd.merge(df1, df2, how='left', left_index=True, right_index=True)

print(df1)
print(df2)

# ('C', 'P1') is in both dataframes and should therefore be merged accordingly
print(result)

output:

       a
id p    
C  P2  0
   P1  1
D  P2  2


       d1
id p     
A  P2  10
C  P2  11
   P1  12


       a    d1
id p          
C  P2  0  11.0
   P1  1   NaN   ## <- Should be 12.0 
D  P2  2   NaN

Problem description

The merge should not return NaN for the ('C', 'P1') value available in df2 for the left merge.

This happens only:

• when p is Categorical: leaving the column as object/string gives the right result
• when category values are ordered as such (decreasing lexicographic order), but the ordered argument does not change the result
• when the id values are as such: changing the 'C' in 'E' or anything "above" gives the right result (!)

Expected Output

       a    d1
id p          
C  P2  0  11.0
   P1  1  12.0
D  P2  2   NaN

First level of investigations

Using a debugger and following the code execution:

• when the error occurs: in Index.join(), it goes here to: https://github.com/pandas-dev/pandas/blob/master/pandas/core/indexes/base.py#L3537

        elif not self.is_unique or not other.is_unique:
            if self.is_monotonic and other.is_monotonic:
                return self._join_monotonic(    ### <- HERE
                    other, how=how, return_indexers=return_indexers
                )

It seems it uses the wrong branch/case.

• when the error does not occurs (e.g. swapping the values in the CategoricalDType declaration): https://github.com/pandas-dev/pandas/blob/master/pandas/core/indexes/base.py#L3578

        if return_indexers:
            if join_index is self:
                lindexer = None
            else:
                lindexer = self.get_indexer(join_index)
            if join_index is other:
                rindexer = None
            else:
                rindexer = other.get_indexer(join_index)   ### <- HERE
            return join_index, lindexer, rindexer
        else:
            return join_index

This is how far I can get.

Output of pd.show_versions()

INSTALLED VERSIONS

commit : 2a7d332
python : 3.8.3.final.0
python-bits : 64
OS : Windows
OS-release : 10
Version : 10.0.18362
machine : AMD64
processor : Intel64 Family 6 Model 142 Stepping 10, GenuineIntel
byteorder : little
LC_ALL : None
LANG : None
LOCALE : fr_FR.cp1252

pandas : 1.1.2
numpy : 1.19.2
pytz : 2020.1
dateutil : 2.8.1
pip : 20.2.3
setuptools : 41.2.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 : 2.11.2
IPython : 7.18.1
pandas_datareader: None
bs4 : None
bottleneck : None
fsspec : None
fastparquet : None
gcsfs : None
matplotlib : None
numexpr : 2.7.1
odfpy : None
openpyxl : 3.0.5
pandas_gbq : None
pyarrow : 1.0.1
pytables : None
pyxlsb : None
s3fs : None
scipy : None
sqlalchemy : None
tables : 3.6.1
tabulate : None
xarray : None
xlrd : None
xlwt : None
numba : None

[mroeschke]

This looks to work on master now. Could use a test

In [15]: import numpy as np
    ...:
    ...: c1 = ['A',  'C',  'C',  'D' ]
    ...: c2 = ['P2', 'P2', 'P1', 'P2']
    ...:
    ...: df1 = pd.DataFrame({
    ...:     'id': c1[1:],
    ...:     'p':  c2[1:],
    ...:     'a':  np.arange(len(c1[1:])),
    ...: })
    ...: df2 = pd.DataFrame({
    ...:     'id': c1[:-1],
    ...:     'p':  c2[:-1],
    ...:     'd1': np.arange(10, 10+len(c1[:-1])),
    ...: })
    ...:
    ...: # ordered=True doesn't change the result
    ...: pcat = pd.api.types.CategoricalDtype(categories=['P2', 'P1'], ordered=False)
    ...:
    ...: df1['p'] = df1['p'].astype(pcat)
    ...: df2['p'] = df2['p'].astype(pcat)
    ...:
    ...: df1 = df1.set_index(['id', 'p'])
    ...: df2 = df2.set_index(['id', 'p'])
    ...:
    ...: result = pd.merge(df1, df2, how='left', left_index=True, right_index=True)
    ...:
    ...: print(df1)
    ...: print(df2)
    ...:
    ...: # ('C', 'P1') is in both dataframes and should therefore be merged accordingly
    ...: print(result)
       a
id p
C  P2  0
   P1  1
D  P2  2
       d1
id p
A  P2  10
C  P2  11
   P1  12
       a    d1
id p
C  P2  0  11.0
   P1  1  12.0
D  P2  2   NaN

[tim-tran]

take