Join Two Sorted Streams Without Loading Them

You have two large exports, orders and customers, both sorted by customer ID. You want each order joined to its customer's row, like an inner join in SQL, without loading either export into memory.

A merge join does this. It reads both sorted streams side by side, the way you merge two sorted lists. At each step it compares the two current keys. The side with the smaller key moves on, because the other side is already past that key. When the keys are equal, the rows match.

left = [{"id": "a", "l": "1"}, {"id": "b", "l": "2"}]
right = [{"id": "b", "r": "9"}, {"id": "c", "r": "8"}]
list(stream_join(left, right, "id"))
# [{"id": "b", "l": "2", "r": "9"}]

A key can repeat on both sides. Then each left row with that key pairs with each right row with that key, so two rows on each side give four output rows.

What you can rely on

• A row is a dict[str, str], and every row has the field named by on.
• Both inputs come sorted by that field in Python string order, so rows with equal keys are next to each other. Use the rows in the order they arrive.
• "" is a valid key.

Write _grouped

_grouped(rows, on) yields (key, group) for each run of rows that share a key, in order. group is a list of the original row objects, unchanged. An empty input yields nothing.

You know a group has ended only when you read a row with a different key, or the input runs out. That row is the lookahead, the first row of the next group, which you have read but not used yet. Yield the finished group as soon as you have the lookahead, and read nothing more until the caller asks for the next group. Then start that group with the lookahead.

Write stream_join

stream_join(left, right, on) yields the joined rows. Make it a generator. Calling it must read nothing, and must not even call iter() on either input. The work starts at the first next(). Then:

• Get the first group from the left, then the first group from the right, even when the left input is empty. Use None for a side that has no groups left.
• While both sides have a group, compare their keys. If one key is smaller, move that side on to its next group.
• If the keys are equal, yield one row for each pair. Go through the left rows in order, and for each one, go through every right row in order.
• Build each output row as a new dict, {**left_row, **right_row}. When both rows have a field, the right value wins. That holds for every shared field, not only the key.
• After the caller takes the last row of a pair of groups, move the left side to its next group, then the right side. Only then check whether either side has run out.
• Make that move only when the caller asks for another row. If the caller stops early, for example with islice, your join reads no further groups.
• Stop as soon as either side has no group left. Leave the rest of the other side unread.

The output comes in key order, then left row order, then right row order. A key that appears on one side only produces nothing.

What the driver reports

Keep CountingRows, _tail and solve as they are. CountingRows wraps each input and counts the iter() calls on it and the rows it hands out. solve calls stream_join, then collects rows. limit is None or a number of zero or more, and solve collects at most that many rows.

• rows holds the joined rows collected.
• pulled_before_first counts the rows read from both inputs by the time stream_join returns. It must be 0.
• left_pulled and right_pulled count the rows read from each input. A lookahead row counts even if it never reaches the output, and so does a row in a group that matched nothing.
• left_iters and right_iters count the iter() calls on each input. Each is 1 once the join has started. With limit=0 both are 0, because solve never calls next().

With infinite=True, the driver adds an endless run of matching rows to both inputs, with keys "z000000", "z000001" and so on. Only a lazy join can finish. With one matching row "a" on each side and limit=4, you get four rows, and each side reads five. Those are the "a" row and four tail rows. The last tail row is the lookahead after the group "z000002".

An empty left input still reads the first group on the right, so right_pulled can be above 0 when the result is empty.

The join holds about one group per side, plus the lookahead rows. A pair of groups with a and b rows still yields a * b rows, one at a time. All your functions must pass mypy --strict.