BUG: Joining data frames with MultiIndex results in non-deterministic level order.

[theemathas]

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

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

• (optional) I have confirmed this bug exists on the master branch of pandas.

---

Note: Please read this guide detailing how to provide the necessary information for us to reproduce your bug.

Code Sample, a copy-pastable example

import pandas as pd

foo = pd.DataFrame(data={'e': 5}, index=pd.MultiIndex.from_tuples([(1, 2, 4)], names=('a', 'b', 'd')))
bar = pd.DataFrame(data={'f': 6}, index=pd.MultiIndex.from_tuples([(2, 3)], names=('b', 'c')))
joined = foo.join(bar, how='inner')
print(foo.join(bar))

Expected Output

Something deterministic

Produced Output

When running the code multiple times (restart the python interpreter), the output switches (apparently randomly) between these two outputs:

         e  f
b d a c
2 4 1 3  5  6

         e  f
b a d c
2 1 4 3  5  6

Problem description

When joining with a data frame with a MultiIndex, the order of the levels in the resulting data frame is non-deterministic. This is very surprising, and resulted in a hard-to-debug issue in my code. This issue happens with both inner joins and left joins.

Possibly related issues: #36909, #25760

Past discussion on non-determinism in pandas: #32514, #32449, #12679

Output of pd.show_versions()

INSTALLED VERSIONS
------------------
commit           : db08276bc116c438d3fdee492026f8223584c477
python           : 3.8.6.final.0
python-bits      : 64
OS               : Windows
OS-release       : 10
Version          : 10.0.18362
machine          : AMD64
processor        : Intel64 Family 6 Model 142 Stepping 12, GenuineIntel
byteorder        : little
LC_ALL           : None
LANG             : en_US.UTF-8
LOCALE           : English_United States.1252

pandas           : 1.1.3
numpy            : 1.19.2
pytz             : 2020.1
dateutil         : 2.8.1
pip              : 20.1.1
setuptools       : 50.3.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
pytables         : None
pyxlsb           : None
s3fs             : None
scipy            : None
sqlalchemy       : None
tables           : None
tabulate         : None
xarray           : None
xlrd             : None
xlwt             : None
numba            : None