キーで join (map 利用)
キーで join (map 利用)
このレッスンで分かること
- これはプログラミング的には 「user_id をキーに users と orders を結合する」 処理です
- リレーショナルデータベースでは、テーブルを分割して
重複を減らす設計が基本です- users テーブル
キーで join とは
外部キー（foreign key）で 2 つのテーブルを結合する処理を、map（ハッシュテーブル）を使って O(n+m) で実装します。
リレーショナルデータベースでは、テーブルを分割して 重複 を減らす設計が基本です。例えばユーザーと注文の関係を表すとき、次のように 2 つのテーブルに分けます。
users テーブル
| user_id | name |
|---|---|
| 1 | Alice |
| 2 | Bob |
| 3 | Carol |
orders テーブル
| order_id | user_id | amount |
|---|---|---|
| 101 | 1 | 1200 |
| 102 | 2 | 800 |
| 103 | 1 | 500 |
orders.user_id は users.user_id を指し示しています。この 「別テーブルの主キーを参照するカラム」を外部キー（foreign key） と呼びます。外部キーは「どの行と紐づくか」を表すラベルです。
外部キー制約を付けると、
orders.user_idに存在しないusers.user_idを入れようとすると DB がエラーを返してくれる。これを参照整合性と呼びます。
JOIN は外部キーで「もとに戻す」操作
分けたテーブルから「ユーザー名つき注文一覧」を取り出すには、SQL で JOIN を書きます。
SQL クエリ
SELECT u.name, o.order_id, o.amount
FROM users u
JOIN orders o ON u.user_id = o.user_id;これはプログラミング的には 「user_id をキーに users と orders を結合する」 処理です。素朴に書くと二重ループになり、O(n × m) の計算量がかかります。
Python
for o in orders:
for u in users:
if o.user_id == u.user_id:
yield (u.name, o.order_id, o.amount)二重ループは
usersが 10 万件、ordersが 100 万件あると 10^11 回の比較になり、まったく実用にならない。
map で O(n + m) に高速化する
実は、users を user_id をキーにした dict（連想配列, ハッシュマップ）に詰めておく だけで、orders 側からは O(1) で検索できるようになります。これが hash join の原理で、DB エンジンの内部でも使われている古典的なテクニックです。
Python
user_map = { u["user_id"]: u for u in users }
for o in orders:
u = user_map[o["user_id"]]
print(u["name"], o["order_id"], o["amount"])ここで user_map のメモリ使用量は O(n)、検索は O(1) なので、全体の計算量は O(n + m)。テーブルが大きいほど効果が劇的に効いてきます。
コードでの考え方
今回の問題では users = [{"user_id": 1, "name": "Alice"}, ...] と orders = [{"order_id": 101, "user_id": 1, "amount": 1200}, ...] を受け取り、[{"name": "Alice", "order_id": 101, "amount": 1200}, ...] を返します。orders の順番を維持することが大事です。
JavaScript
function joinOrders(users, orders) {
const userMap = Object.fromEntries(users.map(u => [u.user_id, u.name]));
return orders.map(o => ({
name: userMap[o.user_id],
order_id: o.order_id,
amount: o.amount,
}));
}
Object.fromEntriesとArray.prototype.mapを組み合わせると、二重ループを使わずにO(n + m)で書ける。
よくある間違い
二重ループのまま JOIN を書くと、テストは通っても本番で性能が出ません。まず dict を作り、その後 1 回ループする という二段構成を必ず守りましょう。
また、orders の user_id に対応する users が存在しないケースを考えていないと、KeyError で落ちます。今回の課題では「対応するユーザーが必ず存在する」前提で OK ですが、実務ではデフォルト値や LEFT JOIN 相当の if u: ... を入れる必要があります。
やってみよう
users と orders を受け取って、{ name, order_id, amount } の配列を返す joinOrders を実装してください。dict（または Object）でのキー lookup を必ず使い、O(n + m) で完成させましょう。
よくある質問
Q. INNER JOIN と LEFT JOIN の違いは？
A. INNER は両側に一致するレコードのみ、LEFT は左側を全て残し右側に一致するものを結合します。LEFT で右側が無いと NULL になります。「ユーザーごとに購入履歴を、購入が無いユーザーも含めて出したい」場合は LEFT JOIN が必須です。
Q. 3 テーブル以上を JOIN できますか？
A. できます。a JOIN b ON ... JOIN c ON ... のように繋げます。結合順序やインデックスの使い方はオプティマイザが自動で決めるため、記述順は基本的に性能に影響しません。性能が問題になる場合は EXPLAIN で実行計画を確認し、適切なインデックスを張るのが定石です。
Q. JOIN したら行数が増えたのはなぜ？
A. 右側に複数の一致レコードがある（多対多）場合、その分だけ行が増えます。意図しない重複が出たら GROUP BY や DISTINCT で集約するか、サブクエリで先に集計してから JOIN すると行数が安定します。
次のレッスン
次は 残高転送のトランザクション風処理 に進みましょう。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 外部キー JOIN の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 外部キー JOIN とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- users から
user_idをキー、nameを値とするマップ（dict / Object）を作る - orders の各要素から user_id で name を引いて { name, order_id, amount } を生成する
- 出力の並び順は入力 orders の順番を維持する
入出力例
test-cases.txt
joinOrders([{"name":"Alice","user_id":1},{"name":"Bob","user_id":2}], [{"amount":1200,"order_id":101,"user_id":1},{"amount":800,"order_id":102,"user_id":2}]) → [{"amount":1200,"name":"Alice","order_id":101},{"amount":800,"name":"Bob","order_id":102}]
joinOrders([{"name":"Alice","user_id":1}], [{"amount":1200,"order_id":101,"user_id":1},{"amount":500,"order_id":103,"user_id":1}]) → [{"amount":1200,"name":"Alice","order_id":101},{"amount":500,"name":"Alice","order_id":103}]
joinOrders([{"name":"Alice","user_id":1},{"name":"Bob","user_id":2},{"name":"Carol","user_id":3}], [{"amount":700,"order_id":201,"user_id":3},{"amount":300,"order_id":202,"user_id":1},{"amount":1500,"order_id":203,"user_id":2}]) → [{"amount":700,"name":"Carol","order_id":201},{"amount":300,"name":"Alice","order_id":202},{"amount":1500,"name":"Bob","order_id":203}]
joinOrders([{"name":"Alice","user_id":1}], []) → []