Joining Records

Inner Join by Key

Join two tables by a shared key, keeping only rows where the key exists in both. A first pass builds an index dict from the smaller table; a second pass walks the larger table and appends matched pairs, silently skipping any key that is absent from the index. Order 3 (key 'x') has no matching customer and is dropped.

By hand

Build a key → name index dict from the customer lists in one loop. Then walk the order lists with zip: for each (order_id, key) pair, test k in index and append the matched tuple to result if found.

naive.py
Replay: real traced execution (multi-file project)
order_ids = [1, 2, 3, 4, 5]
order_ckeys = ['a', 'b', 'x', 'c', 'a']
cust_keys = ['a', 'b', 'c', 'd']
cust_names = ['alice', 'bob', 'carol', 'dave']
index = {}
for k, name in zip(cust_keys, cust_names):
    index[k] = name
result = []
for oid, k in zip(order_ids, order_ckeys):
    if k in index:
        result.append((oid, index[k]))
print('RESULT:', result)

  1. order_ids ← [1, 2, 3, 4, 5]

    1order_ids = [1, 2, 3, 4, 5]2order_ckeys = ['a', 'b', 'x', 'c', 'a']
    values this step[1, 2, 3, 4, 5]order_ids

  2. order_ckeys ← ['a', 'b', 'x', 'c', 'a']

    1order_ids = [1, 2, 3, 4, 5]2order_ckeys = ['a', 'b', 'x', 'c', 'a']3cust_keys = ['a', 'b', 'c', 'd']
    values this step['a', 'b', 'x', 'c', 'a']order_ckeys

  3. cust_keys ← ['a', 'b', 'c', 'd']

    2order_ckeys = ['a', 'b', 'x', 'c', 'a']3cust_keys = ['a', 'b', 'c', 'd']4cust_names = ['alice', 'bob', 'carol', 'dave']
    values this step['a', 'b', 'c', 'd']cust_keys

  4. cust_names ← ['alice', 'bob', 'carol', 'dave']

    3cust_keys = ['a', 'b', 'c', 'd']4cust_names = ['alice', 'bob', 'carol', 'dave']5index = {}
    values this step['alice', 'bob', 'carol', 'dave']cust_names

  5. index ← {}

    4cust_names = ['alice', 'bob', 'carol', 'dave']5index = {}6for k, name in zip(cust_keys, cust_names):
    values this step{}index

  6. k ← 'a', name ← 'alice', index ← {'a': 'alice'}

    pass 1 of 4
    5index = {}6for k, name in zip(cust_keys, cust_names):7    index[k] = name8result = []
    values this step'a'k'alice'name{} → {'a': 'alice'}index
    All 4 passes — pass 1 is the card above
    passknameindex
    1'a''alice'{} → {'a': 'alice'}
    2'a' → 'b''alice' → 'bob'{'a': 'alice'} → {'a': 'alice', 'b': 'bob'}
    3'b' → 'c''bob' → 'carol'{'a': 'alice', 'b': 'bob'} → {'a': 'alice', 'b': 'bob', 'c': 'carol'}
    4'c' → 'd''carol' → 'dave'{'a': 'alice', 'b': 'bob', 'c': 'carol'} → {'a': 'alice', 'b': 'bob', 'c': 'carol', 'd': 'dave'}

  7. for k, name in zip(cust_keys, cust_names):

    5index = {}6for k, name in zip(cust_keys, cust_names):7    index[k] = name

  8. result ← []

    7    index[k] = name8result = []9for oid, k in zip(order_ids, order_ckeys):
    values this step[]result

  9. k ← 'a', oid ← 1, result ← [(1, 'alice')]

    pass 1 of 2
    8result = []9for oid, k in zip(order_ids, order_ckeys):10    if k in index:11        result.append((oid, index[k]))12print('RESULT:', result)
    values this step'd' → 'a'k1oid[] → [(1, 'alice')]result

  10. k ← 'b', oid ← 2, result ← [(1, 'alice'), (2, 'bob')]

    pass 2 of 2
    8result = []9for oid, k in zip(order_ids, order_ckeys):10    if k in index:11        result.append((oid, index[k]))12print('RESULT:', result)
    values this step'a' → 'b'k1 → 2oid[(1, 'alice')] → [(1, 'alice'), (2, 'bob')]result

  11. k ← 'x', oid ← 3

    pass 1 of 2
    8result = []9for oid, k in zip(order_ids, order_ckeys):10    if k in index:11        result.append((oid, index[k]))
    values this step'b' → 'x'k2 → 3oid

  12. k ← 'c', oid ← 4

    pass 2 of 2
    8result = []9for oid, k in zip(order_ids, order_ckeys):10    if k in index:11        result.append((oid, index[k]))
    values this step'x' → 'c'k3 → 4oid

  13. result ← [(1, 'alice'), (2, 'bob'), (4, 'carol')]

    10    if k in index:11        result.append((oid, index[k]))12print('RESULT:', result)
    values this step[(1, 'alice'), (2, 'bob')] → [(1, 'alice'), (2, 'bob'), (4, 'carol')]result

  14. k ← 'a', oid ← 5

    8result = []9for oid, k in zip(order_ids, order_ckeys):10    if k in index:
    values this step'c' → 'a'k4 → 5oid

  15. if k in index:

    9for oid, k in zip(order_ids, order_ckeys):10    if k in index:11        result.append((oid, index[k]))

  16. result ← [(1, 'alice'), (2, 'bob'), (4, 'carol'), (5, 'alice')]

    10    if k in index:11        result.append((oid, index[k]))12print('RESULT:', result)
    values this step[(1, 'alice'), (2, 'bob'), (4, 'carol')] → [(1, 'alice'), (2, 'bob'), (4, 'carol'), (5, 'alice')]result

  17. for oid, k in zip(order_ids, order_ckeys):

    8result = []9for oid, k in zip(order_ids, order_ckeys):10    if k in index:

  18. stdout ← RESULT: [(1, 'alice'), (2, 'bob'), (4, 'carol'), (5, 'alice')]

    11        result.append((oid, index[k]))12print('RESULT:', result)
    values this stepRESULT: [(1, 'alice'), (2, 'bob'), (4, 'carol'), (5, 'alice')]stdout

The Pythonic way

Build the index with a dict comprehension, then produce result with a list comprehension that folds the lookup and the if k in index filter into one expression.

library.py 
order_ids = [1, 2, 3, 4, 5]
order_ckeys = ['a', 'b', 'x', 'c', 'a']
cust_keys = ['a', 'b', 'c', 'd']
cust_names = ['alice', 'bob', 'carol', 'dave']
index = {k: name for k, name in zip(cust_keys, cust_names)}
result = [(oid, index[k]) for oid, k in zip(order_ids, order_ckeys) if k in index]
print('RESULT:', result)

RESULT: [(1, 'alice'), (2, 'bob'), (4, 'carol'), (5, 'alice')]

Implementation notes

  • Building the index first makes the join O(n + m) overall: O(m) to build the index, then O(n) for the order pass. A nested-loop approach would be O(n × m).
  • This is the same mechanism as pd.merge(orders, customers, on='key', how='inner') in the python-pandas track — mechanism here, API there.
  • An outer join variant would use index.get(k, None) and keep all orders, substituting None for unmatched customers.
  • Key 'x' in order 3 has no entry in the customer table; the if k in index guard drops it silently, which is the defining behaviour of an inner join.