Implement left join on Python lists, no packages

Implement a left join in pure Python (no external packages, no pandas). Input: left = list of dicts with key 'id' and arbitrary other fields; right = list of dicts with key 'id' and fields to append (disjoint names from left). Requirements: (1) Preserve the original order of 'left' and left duplicates. (2) Support one-to-many matches on 'right' (i.e., duplicate 'id's): emit one output row per matching right row; if no match, emit a single row with right fields set to None. (3) Time O(n + m) and extra space O(n + m) by using hashing; explain how you would reduce memory when m is huge (e.g., streaming or external sort). (4) Handle missing 'id' keys robustly. Provide clear function signatures and tests on small examples.