full_outer_join

Lazy iterator implementations of a full outer join, inner join, and left and right joins of Python iterables.

This implements the sort-merge join, better known as the merge join, to join iterables in O(n) time with respect to the length of the longest iterable.

Note that the algorithm requires input to be sorted by the join key.

Example

(whitespace to make things explicit)

>>> list(full_outer_join.full_outer_join(
    [{"id": 1, "val": "foo"}                         ],
    [{"id": 1, "val": "bar"}, {"id": 2, "val": "baz"}],
    key=lambda x: x["id"]
))

[
    (1, ([{'id': 1, 'val': 'foo'}], [{'id': 1, 'val': 'bar'}])),
    (2, ([                       ], [{'id': 2, 'val': 'baz'}]))
]

To consume the output, your business logic might look like:

for group_key, key_batches in full_outer_join.full_outer_join(left, right):
    left_rows, right_rows = key_batches
    
    if left_rows and right_rows:
        # This is the inner join case.
        pass
    elif left_rows and not right_rows:
        # This is the left join case (no matching right rows)
        pass
    elif not left_rows and right_rows:
        # This is the right join case (no matching left rows)
        pass
    elif not left_rows and not right_rows:
        raise Exception("Unreachable")

Functions

Why?

1. Your input is already sorted and you don't want to consume your input iterators.
2. Your business logic that consumes the joined output benefits from explicitly handling the match and no-match cases from each input iterable.
3. You're insane. Your brain is irreparably broken by the relational model.

More examples

See test_insanity.py for a silly example of a SQL query hand-compiled into iterators.

Thanks

This was originally a PR to the more_itertools project who gave some excellent feedback on the design but ultimately did not want to merge it in.