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.

Left Join With One-to-Many Matches, Preserving Left Order and Duplicates

You are given two tables that represent two lists of records:

• left_records: the primary list. It contains an id (which may be NULL) and other fields.
• right_records: the lookup list. It also contains an id (which may be NULL) and fields to append to the left.

Write a SQL query that performs a LEFT JOIN of left_records to right_records on id with the following requirements:

1. Preserve the original order of rows from left_records using left_seq (and preserve duplicates in left_records).
2. Support one-to-many matches on right_records (i.e., multiple rows in right_records can share the same id). For each left_records row, return one output row per matching right_records row.
3. If a left_records row has no matching right_records row (including when left_records.id is NULL), return exactly one output row with the right-side columns as NULL.
4. Handle missing IDs robustly: rows where left_records.id is NULL should not match anything (even if right_records.id is NULL).

Return these columns: left_seq, id, left_name, right_attr.

Order the final output by left_seq, and for rows with multiple matches, order by right_seq.

Table left_records

column	type	constraints
left_seq	INT	PRIMARY KEY, NOT NULL
id	INT
left_name	VARCHAR(50)	NOT NULL

Sample data:

id	left_name	left_seq
1	Alpha	1
2	Beta	2
2	Beta (duplicate left row)	3
3	Gamma	4
NULL	No ID Row	5
4	Delta	6

Table right_records

column	type	constraints
right_seq	INT	PRIMARY KEY, NOT NULL
id	INT
right_attr	VARCHAR(50)	NOT NULL

Sample data:

id	right_attr	right_seq
2	B1	10
2	B2	11
4	D1	12
5	E1 (unused)	13
NULL	NULL-ID right row (should not match)	14

Expected output

One row per left record per matching right record. If no match (including left.id IS NULL), right_attr is NULL. Output is ordered by left_seq, then right_seq for deterministic ordering of one-to-many matches.

id	left_name	left_seq	right_attr
1	Alpha	1	NULL
2	Beta	2	B1
2	Beta	2	B2
2	Beta (duplicate left row)	3	B1
2	Beta (duplicate left row)	3	B2
3	Gamma	4	NULL
NULL	No ID Row	5	NULL
4	Delta	6	D1

Hints

1. A LEFT JOIN will keep all rows from the left table and produce NULLs on the right when there is no match.
2. If the right table has duplicate IDs, a normal join naturally returns one output row per matching right row.
3. To preserve the original left order in SQL, include an explicit sequencing column (here, left_seq) and ORDER BY it.