Repository: astropy/astropy

Issue:
Add option to preserve input order on table joins
### Description

joins sort the resulting table by the join key. This is not documented in the actual API documentation of join here:
https://docs.astropy.org/en/stable/api/astropy.table.join.html

and just mentioned in passing here:
https://docs.astropy.org/en/stable/table/operations.html#join

This is undesired in many circumstances. There should be an option to preserve the input order, at least for left/right joins.

### Additional context


Example:
```python
from astropy.table import Table, join
import numpy as np
import astropy.units as u

rng = np.random.default_rng(0)

N_EVENTS = 10
N_TELESCOPES = 3
events = Table({
    'event_id': np.arange(N_EVENTS),
    'tel_id': rng.integers(0, 3, N_EVENTS),
})
telescopes = Table({
    'tel_id': np.arange(N_TELESCOPES),
    'x': rng.uniform(-100, 100, N_TELESCOPES) * u.m,
    'y': rng.uniform(-100, 100, N_TELESCOPES) * u.m,
})


events = join(events, telescopes, keys='tel_id', join_type='left')

print(events)
```

results in:

```
event_id tel_id         x                  y        
                        m                  m        
-------- ------ ------------------ -----------------
       3      0  82.55111545554433 8.724998293084568
       4      0  82.55111545554433 8.724998293084568
       5      0  82.55111545554433 8.724998293084568
       6      0  82.55111545554433 8.724998293084568
       7      0  82.55111545554433 8.724998293084568
       8      0  82.55111545554433 8.724998293084568
       1      1 21.327155153435967 87.01448475755365
       2      1 21.327155153435967 87.01448475755365
       0      2 45.899312196799684 63.17071082430644
       9      2 45.899312196799684 63.17071082430644
```

Discussion:
github-actions[bot]: Thank you for your contribution to Astropy! 🌌 This checklist is meant to remind the package maintainers who will review this pull request of some common things to look for.

  - [ ] Do the proposed changes actually accomplish desired goals?
  - [ ] Do the proposed changes follow the [Astropy coding guidelines](https://docs.astropy.org/en/latest/development/codeguide.html)?
  - [ ] Are tests added/updated as required? If so, do they follow the [Astropy testing guidelines](https://docs.astropy.org/en/latest/development/testguide.html)?
  - [ ] Are docs added/updated as required? If so, do they follow the [Astropy documentation guidelines](https://docs.astropy.org/en/latest/development/docguide.html#astropy-documentation-rules-and-guidelines)?
  - [ ] Is rebase and/or squash necessary? If so, please provide the author with appropriate instructions. Also see instructions for [rebase](https://docs.astropy.org/en/latest/development/workflow/development_workflow.html#rebase-if-necessary) and [squash](https://docs.astropy.org/en/latest/development/workflow/development_workflow.html#squash-if-necessary).
  - [ ] Did the CI pass? If no, are the failures related? If you need to run daily and weekly cron jobs as part of the PR, please apply the "Extra CI" label. Codestyle issues can be fixed by the [bot](https://docs.astropy.org/en/latest/development/workflow/development_workflow.html#pre-commit).
  - [ ] Is a change log needed? If yes, did the change log check pass? If no, add the "no-changelog-entry-needed" label. If this is a manual backport, use the "skip-changelog-checks" label unless special changelog handling is necessary.
  - [ ] Is this a big PR that makes a "What's new?" entry worthwhile and if so, is (1) a "what's new" entry included in this PR and (2) the "whatsnew-needed" label applied?
  - [ ] At the time of adding the milestone, if the milestone set requires a backport to release branch(es), apply the appropriate "backport-X.Y.x" label(s) *before* merge.
taldcroft: > Overall, looks good. My one worry is that if the `_join` itself fails (say because of a metadata conflict), an input table can be left with an extra column. So, I'd suggest to wrap the lot in a `try/finally` with the special column removed in the `finally` part.

Good catch, will do.

> On the API: an option to avoid having to swap input arguments for `inner` would be to allow `keep_order` to be a string ('right' or 'left'). But arguably overkill.

The `'left'` and `'right'` then require validation to avoid `keep_order="right", join_type="left"` or vice-versa. Overall it seems like overkill and the bool option is good enough for pandas.
taldcroft: @mhvk @neutrinoceros - I think I have addressed the comments and CI is passing.

Patch:
diff --git a/astropy/table/operations.py b/astropy/table/operations.py
index b326c498ae..22404541b8 100644
--- a/astropy/table/operations.py
+++ b/astropy/table/operations.py
@@ -10,6 +10,7 @@
 
 import collections
 import itertools
+import warnings
 from collections import Counter, OrderedDict
 from collections.abc import Mapping, Sequence
 from copy import deepcopy
@@ -360,6 +361,7 @@ def join(
     *,
     keys_left=None,
     keys_right=None,
+    keep_order=False,
     uniq_col_name="{col_name}_{table_name}",
     table_names=["1", "2"],
     metadata_conflicts="warn",
@@ -385,6 +387,11 @@ def join(
         column-like values with the same lengths as the left table.
     keys_right : str or list of str or list of column-like, optional
         Same as ``keys_left``, but for the right side of the join.
+    keep_order: bool, optional
+        By default, rows are sorted by the join keys. If True, preserve the order of
+        rows from the left table for "inner" or "left" joins, or from the right table
+        for "right" joins. For other join types this argument is ignored except that a
+        warning is issued if ``keep_order=True``.
     uniq_col_name : str or None
         String generate a unique output column name in case of a conflict.
         The default is '{col_name}_{table_name}'.
@@ -411,20 +418,51 @@ def join(
     if not isinstance(right, Table):
         right = Table(right)
 
+    # Define a magic key that won't conflict with any user column name. This is to
+    # support the keep_order argument. In this case a temporary column is added to the
+    # left or right table to keep track of the original row order. After joining, the
+    # order is restored and the temporary column is removed.
+    sort_table_index_key = "__astropy_table_keep_order_sort_index__"
+    sort_table = None
+    if keep_order:
+        if join_type not in ["left", "right", "inner"]:
+            # Keep order is not meaningful for an outer join and cartesian join is
+            # already ordered by left (primary) then right (secondary).
+            warnings.warn(
+                "keep_order=True is only supported for left, right, and inner joins",
+                UserWarning,
+                stacklevel=2,
+            )
+        else:
+            sort_table = right if join_type == "right" else left
+            sort_table[sort_table_index_key] = np.arange(len(sort_table))
+
     col_name_map = OrderedDict()
-    out = _join(
-        left,
-        right,
-        keys,
-        join_type,
-        uniq_col_name,
-        table_names,
-        col_name_map,
-        metadata_conflicts,
-        join_funcs,
-        keys_left=keys_left,
-        keys_right=keys_right,
-    )
+
+    # In case keep_order=True we need try/finally to ensure that the temporary column
+    # is removed even if an exception is raised.
+    try:
+        out = _join(
+            left,
+            right,
+            keys,
+            join_type,
+            uniq_col_name,
+            table_names,
+            col_name_map,
+            metadata_conflicts,
+            join_funcs,
+            keys_left=keys_left,
+            keys_right=keys_right,
+        )
+        if sort_table is not None:
+            # Sort joined table to the original order and remove the temporary column.
+            out.sort(sort_table_index_key)
+            del out[sort_table_index_key]
+    finally:
+        if sort_table is not None:
+            # If sort_table is not None that implies keep_order=True.
+            del sort_table[sort_table_index_key]
 
     # Merge the column and table meta data. Table subclasses might override
     # these methods for custom merge behavior.
diff --git a/docs/changes/table/16361.feature.rst b/docs/changes/table/16361.feature.rst
new file mode 100644
index 0000000000..f1cc02fc50
--- /dev/null
+++ b/docs/changes/table/16361.feature.rst
@@ -0,0 +1,4 @@
+Add a ``keep_order`` argument to the ``astropy.table.join`` function which specifies to
+maintain the original order of the key table in the joined output. This applies for
+inner, left, and right joins. The default is ``False`` in which case the output is
+ordered by the join keys, consistent with prior behavior.


Test patch:
diff --git a/astropy/table/tests/test_operations.py b/astropy/table/tests/test_operations.py
index 17758ab006..f71530a716 100644
--- a/astropy/table/tests/test_operations.py
+++ b/astropy/table/tests/test_operations.py
@@ -2217,6 +2217,74 @@ def test_unique(operation_table_type):
     ]
 
 
+@pytest.mark.parametrize("join_type", ["inner", "outer", "left", "right", "cartesian"])
+def test_join_keep_sort_order(join_type):
+    """Test the keep_order argument for table.join.
+
+    See https://github.com/astropy/astropy/issues/11619.
+
+    This defines a left and right table which have an ``id`` column that is not sorted
+    and not unique. Each table has common and unique ``id`` key values along with an
+    ``order`` column to keep track of the original order.
+    """
+    keep_supported = join_type in ["left", "right", "inner"]
+    t1 = Table()
+    t1["id"] = [2, 8, 2, 0, 0, 1]  # Join key
+    t1["order"] = np.arange(len(t1))  # Original table order
+
+    t2 = Table()
+    t2["id"] = [2, 0, 1, 9, 0, 1]  # Join key
+    t2["order"] = np.arange(len(t2))  # Original table order
+
+    # No keys arg is allowed for cartesian join.
+    keys_kwarg = {} if join_type == "cartesian" else {"keys": "id"}
+
+    # Now do table joints with keep_order=False and keep_order=True.
+    t12f = table.join(t1, t2, join_type=join_type, keep_order=False, **keys_kwarg)
+    # For keep_order=True there should be a warning if keep_order is not supported for
+    # the join type.
+    ctx = (
+        nullcontext()
+        if keep_supported
+        else pytest.warns(
+            UserWarning,
+            match=r"keep_order=True is only supported for left, right, and inner joins",
+        )
+    )
+    with ctx:
+        t12t = table.join(t1, t2, join_type=join_type, keep_order=True, **keys_kwarg)
+
+    assert len(t12f) == len(t12t)
+    assert t12f.colnames == t12t.colnames
+
+    # Define expected sorting of join table for keep_order=False. Cartesian joins are
+    # always sorted by the native order of the left table, otherwise the table is sorted
+    # by the sort key ``id``.
+    sort_key_false = "order_1" if join_type == "cartesian" else "id"
+
+    # For keep_order=True the "order" column is sorted if keep is supported otherwise
+    # the table is sorted as for keep_order=False.
+    if keep_supported:
+        sort_key_true = "order_2" if join_type == "right" else "order_1"
+    else:
+        sort_key_true = sort_key_false
+
+    assert np.all(t12f[sort_key_false] == sorted(t12f[sort_key_false]))
+    assert np.all(t12t[sort_key_true] == sorted([t12t[sort_key_true]]))
+
+
+def test_join_keep_sort_order_exception():
+    """Test that exception in join(..., keep_order=True) leaves table unchanged"""
+    t1 = Table([[1, 2]], names=["id"])
+    t2 = Table([[2, 3]], names=["id"])
+    with pytest.raises(
+        TableMergeError, match=r"Left table does not have key column 'not-a-key'"
+    ):
+        table.join(t1, t2, keys="not-a-key", join_type="inner", keep_order=True)
+    assert t1.colnames == ["id"]
+    assert t2.colnames == ["id"]
+
+
 def test_vstack_bytes(operation_table_type):
     """
     Test for issue #5617 when vstack'ing bytes columns in Py3.