When there's no sorted index to exploit, a database joins two tables with a hash join: build an in-memory hash table on the smaller side (the "build" side), then stream the other side (the "probe" side) through it, emitting a joined row for every match. This is what Postgres's Hash Join and DuckDB's PhysicalHashJoin do.

Implement hash_join(left_rows, left_key, right_rows, right_key, how="inner"):

• Build a hash table from left_rows, keyed by row[left_key]. A key may map to more than one row.
• For each row in right_rows, look it up by row[right_key] and emit one merged dict ({**left_row, **right_row}) per matching left row, in the order the left rows were inserted into the hash table.
• how="inner" (default): a right row with no match produces nothing, and a left row that's never probed produces nothing either.
• how="left": everything from "inner", PLUS one extra row for every left row that was NEVER matched by any probe -- merged with None for every column name that appears anywhere in right_rows. These come after all the matched rows, in left_rows' original order.

The missing link: an outer join needs to remember what it DIDN'T match

A plain inner join can forget a build-side row the instant nothing probes it -- it just never appears in the output, and that's correct. A left outer join can't do that: it has to actively track, across the ENTIRE probe phase, which build keys were matched at least once, so that afterward it can go back and emit the ones that never were. That's real extra state (a set of matched keys), not just an extra if on the same loop -- and it's checked only after every single probe row has already been processed, since a key could match on the very last probe row after appearing unmatched through every earlier one.

Example

users = [{"id": 1, "name": "Ada"}, {"id": 2, "name": "Grace"}]
orders = [{"order_id": 100, "user_id": 1, "item": "book"}]
hash_join(users, "id", orders, "user_id")
# -> [{"id": 1, "name": "Ada", "order_id": 100, "user_id": 1, "item": "book"}]

hash_join(users, "id", orders, "user_id", how="left")
# -> [{"id": 1, "name": "Ada", "order_id": 100, "user_id": 1, "item": "book"},
#     {"id": 2, "name": "Grace", "order_id": None, "user_id": None, "item": None}]

Constraints

• Handle fan-out correctly: if the build side has multiple rows for a key, a single probe row must produce one output row per matching build row.
• Iterate right_rows in the given order; for each, iterate its matches in the order they were added to the hash table.
• For how="left", the columns filled with None are whatever column names appear anywhere across right_rows -- if right_rows is empty, there are no such columns, and an unmatched left row is emitted completely unchanged.

Real-world grounding

• Postgres's hash join: nodeHash.c (build side) + nodeHashjoin.c (probe side) -- search nodeHashjoin.c for HJ_FILL_OUTER and hj_MatchedOuter: the exact "which build-side tuples were ever matched" bookkeeping this exercise's matched_keys represents, used to drive its own left/full outer join support.
• DuckDB's hash join operator: physical_hash_join.cpp

Real hash joins add a lot on top of this -- spilling to disk when the build side doesn't fit in memory, bloom filters to skip obviously-non-matching probe rows, parallel/vectorized execution -- but the core build-then-probe idea is exactly this.