BUG: outer join out of order when joining multiple DataFrames

[hitvoice]

Pandas version checks

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

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

• I have confirmed this bug exists on the main branch of pandas.

Reproducible Example

import pandas as pd
a = pd.DataFrame(np.ones((4, 2)), index=[3,2,1,0])
b = pd.DataFrame(2*np.ones((2, 1)), columns=[2], index=[3,1])
c = pd.DataFrame(3*np.ones((2, 1)), columns=[3], index=[3,1])
a.join(b, how='outer') # correct, the index is [0,1,2,3]
b.join(a, how='outer') # correct, the index is [0,1,2,3]
a.join([b, c], how='outer') # incorrect, the index is [3,2,1,0]
b.join([a, c], how='outer') # incorrect, the index is [3,1,2,0]

Issue Description

The document of join says:

outer: form union of calling frame’s index (or column if on is specified) with other’s index, and sort it. lexicographically.

But the behavior is not consistent. when joining more than 2 dataframes, the result remains unsorted, which is a bug.

Expected Behavior

The result should be sorted when outer joining multiple dataframes. This test should be passed for the example above:

assert a.join([b, c], how='outer').equals(a.join([b, c], how='outer', sort=True))

Installed Versions

1.5.0.dev0+471.g8e0baa2360

[rhshadrach]

Thanks for the report, looks like the issues are here:

pandas/pandas/core/frame.py

Lines 9384 to 9400 in 9303302

	if can_concat:
	if how == "left":
	res = concat(
	frames, axis=1, join="outer", verify_integrity=True, sort=sort
	)
	return res.reindex(self.index, copy=False)
	else:
	return concat(
	frames, axis=1, join=how, verify_integrity=True, sort=sort
	)
	joined = frames[0]
	for frame in frames[1:]:
	joined = merge(
	joined, frame, how=how, left_index=True, right_index=True
	)

If can_concat is True, then we need to override passing sort and instead always pass True in the case of an outer join. And while it's not hit by your code, it appears we neglect to pass sort altogether if can_concat is False. This should be fixed too.

Would you be interested in submitting a PR to fix?

[hitvoice]

@rhshadrach

And while it's not hit by your code, it appears we neglect to pass sort altogether if can_concat is False. This should be fixed too.

It looks like it's unnecessary to pass sort if can_concat is False. Here's the example:

import pandas as pd
a = pd.DataFrame(np.ones((4, 2)), index=[3,2,1,0])
b = pd.DataFrame(2*np.ones((2, 1)), columns=[2], index=[3,1])
c = pd.DataFrame(3*np.ones((3, 1)), columns=[3], index=[3,1,3])
print(all(df.index.is_unique for df in [a,b,c]))  # can_concat is False
a.join([b, c], how='inner')  # the index of the result is always sorted for 'inner', 'left', 'right', 'outer'

Is this the right way to verify this?

[hitvoice]

Would you be interested in submitting a PR to fix?

Sure. I'll be glad to work on it.

[hitvoice]

@rhshadrach
Fixing this will change the behavior of pandas.wide_to_long. Take the example in the wide_to_long documentation:

np.random.seed(123)
df = pd.DataFrame({"A1970" : {0 : "a", 1 : "b", 2 : "c"},
                   "A1980" : {0 : "d", 1 : "e", 2 : "f"},
                   "B1970" : {0 : 2.5, 1 : 1.2, 2 : .7},
                   "B1980" : {0 : 3.2, 1 : 1.3, 2 : .1},
                   "X"     : dict(zip(range(3), np.random.randn(3)))
                  })
df["id"] = df.index
pd.wide_to_long(df, ["A", "B"], i="id", j="year")

Now the result is

                X  A    B
id year                  
0  1970 -1.085631  a  2.5
   1980 -1.085631  d  3.2
1  1970  0.997345  b  1.2
   1980  0.997345  e  1.3
2  1970  0.282978  c  0.7
   1980  0.282978  f  0.1

instead of the original

                X  A    B
id year
0  1970 -1.085631  a  2.5
1  1970  0.997345  b  1.2
2  1970  0.282978  c  0.7
0  1980 -1.085631  d  3.2
1  1980  0.997345  e  1.3
2  1980  0.282978  f  0.1

There're three ways to fix this:

1. change the behavior of wide_to_long, update examples in the documentation, and update corresponding test cases.
2. detect the explicit user input with something like the explicit_checker and explicitly set sort=False in wide_to_long to keep its behavior unchanged.
3. change the behavior and documentation of the outer join, with no guarantee of index order when doing an outer join.

Which one should we choose?

[rhshadrach]

It looks like it's unnecessary to pass sort if can_concat is False. Here's the example:
...
a.join([b, c], how='inner') # the index of the result is always sorted for 'inner', 'left', 'right', 'outer'

Isn't it incorrect that the result is always sorted? For outer this is correct. For inner, the order should be preserved from the inputs.

Fixing this will change the behavior of pandas.wide_to_long.

Interesting. I've been wondering why outer joins always sorted. Off hand I'd look into adding the ability to not sort for outer joins. In the case where can_concat is False in the code above, there is currently no option in the underlying Cython algorithm full_outer_join for not sorting. Taking a glance at the algorithm, it appears that the sorting happens at the end. I'm not sure if allowing the possibility to not sort is a good idea - i.e. why it was never added in the first place? Perhaps the algorithm does not enforce any particular order, and so not sorting would lead to surprising results (just a guess).

cc @jreback for any thoughts.