PERF: DataFrame.merge with MultiIndex issues PerformanceWarning

[itcarroll]

• I have checked that this issue has not already been reported.

• I have confirmed this issue exists on the latest version of pandas.

• I have confirmed this issue exists on the master branch of pandas.

Reproducible Example

>>> import pandas as pd
>>> left = pd.DataFrame.from_dict({('A', 'a'): [0]})
>>> right = pd.DataFrame.from_dict({('B', 'b'): [1]})
>>> left.merge(right, how='cross')
PerformanceWarning: dropping on a non-lexsorted multi-index without a level parameter may impact performance.
  obj = obj._drop_axis(labels, axis, level=level, errors=errors)
   A  B
   a  b
0  0  1

It is neither left.columns nor right.columns that has _lexsort_depth == 0. Some MultiIndex created during the merge is not sorted (and/or dropped without a level parameter). I don't know if this actually affects performance or is better described as a bug.

Installed Versions

INSTALLED VERSIONS

commit : 945c9ed
python : 3.8.10.final.0
python-bits : 64
OS : Linux
OS-release : 5.11.0-27-generic
Version : #29~20.04.1-Ubuntu SMP Wed Aug 11 15:58:17 UTC 2021
machine : x86_64
processor : x86_64
byteorder : little
LC_ALL : None
LANG : None
LOCALE : en_US.UTF-8

pandas : 1.3.4
numpy : 1.21.4
pytz : 2021.3
dateutil : 2.8.2
pip : 21.2.4
setuptools : 57.4.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 : None
IPython : None
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

Prior Performance

No response

[mroeschke]

Thanks for the report.

I don't see the same behavior on master

In [1]: pd.__version__
Out[1]: '1.4.0.dev0+1171.ge1fbd3cd28'

In [2]: >>> import pandas as pd
   ...: >>> left = pd.DataFrame.from_dict({('A', 'a'): [0]})
   ...: >>> right = pd.DataFrame.from_dict({('B', 'b'): [1]})
   ...: >>> left.merge(right, how='cross')
Out[2]:
   A  B
   a  b
0  0  1

This false positive behavior may have been addressed in the interim and should be eliminated in 1.4 (out hopefully at the end of the year). If you still see the same behavior once 1.4 is out, feel free to reopen another issue.