SELECT * FROM orders JOIN users ON orders.user_id = users.id と書けば、結果はちゃんと返ってくる。だからJOINを「わかった」つもりでいたが、テーブルの行数が万単位から億単位に育ったとたん、同じクエリが数秒から数分に化けたことがある。SQLの文法は変えていないのに、である。
この記事では、データベースがJOINをどうやって実際に処理しているのか、代表的な3つの結合アルゴリズムに沿って追いかけます。「行数が増えると遅くなる」という結果だけでなく、なぜそのアルゴリズムが選ばれ、なぜ特定の条件で遅くなるのかを、仕組みのレベルで説明できるようになることが目標です。
JOINは「概念」であって「手順」ではない
まず整理しておきたいのは、SQLのJOIN句はあくまで「こういう結果が欲しい」という宣言であって、「こういう手順で処理しろ」という命令ではないという点です。ON orders.user_id = users.id という条件を書いた時点で、私たちは結果の形を指定しただけで、それをどう計算するかはオプティマイザに委ねています。
この委任があるからこそ、同じSQLでもテーブルの行数やインデックスの有無によって、実行計画がまったく違うものに切り替わります。切り替わった先の候補が、次に見る3つのアルゴリズムです。
Nested Loop Join — 二重ループで愚直に照合する
最も素朴な方法は、片方のテーブルを1行ずつ読み、その都度もう片方のテーブルを全部見て一致する行を探すというものです。擬似コードで書くとこうなります。
for order in orders: # 外側テーブル
for user in users: # 内側テーブルを毎回スキャン
if order.user_id == user.id:
yield (order, user)
orders が1万行、users が1万行なら、最悪1億回の比較が発生します。ordersが少なく、usersのid列にインデックスがあるなら、内側の全件スキャンをインデックス検索に置き換えられるため、実務ではこの形（Indexed Nested Loop Join）が最も多く使われます。外側テーブルの行数が少ないときにだけ強い、という条件付きの速さです。
Hash Join — 片方をハッシュテーブルに変えてから照合する
外側テーブルが大きく、インデックスも使えない場合、Nested Loopは現実的な時間で終わりません。そこで使われるのがHash Joinです。手順は以下のように分かれます。
- 小さい方のテーブル（多くの場合
users）を、結合キーをキーにしたハッシュテーブルに構築する - 大きい方のテーブル（
orders）を1回だけスキャンし、各行のuser_idでハッシュテーブルを引く
二重ループが「毎回全件を見る」のに対し、Hash Joinは「一度だけ構築し、あとはO(1)に近い速度で引く」という設計です。この構築コストを払う代わりに、内側テーブルの全件スキャンを1回に減らせます。ここが速さの正体です。ただし、構築したハッシュテーブルがメモリに収まらないほどusers側が巨大だと、ディスクへの書き出しが発生し、途端に遅くなります。
Sort Merge Join — 両方を並べ替えてから突き合わせる
3つ目は、両方のテーブルを結合キーでソートしてから、先頭から順に見比べていく方法です。すでにソート済みのインデックスが両テーブルにあるなら、ソートのコストを払わずに済むため、この方式が最速になることがあります。
orders (sorted by user_id): 1, 1, 2, 5, 7
users (sorted by id): 1, 2, 3, 5, 8
両方を先頭のポインタで同時に進めながら、値が一致すれば結合し、片方が小さければそちらだけを進める。マージソートの後半処理そのものです。ソートさえ終えていれば、あとは一直線に両テーブルを1回ずつなぞるだけで済みます。
EXPLAINで実際に選ばれたアルゴリズムを見る
理屈だけでは実感が湧きにくいので、PostgreSQLで確認してみます。
EXPLAIN ANALYZE
SELECT * FROM orders JOIN users ON orders.user_id = users.id
WHERE orders.created_at > '2026-08-01';
ordersが数百万行、usersに主キーインデックスがある状態でこれを実行すると、多くの場合Hash Joinが選ばれます。WHERE句でorders側が数千行まで絞り込まれ、users.idの主キーインデックスを内側の検索に使える場合は、Nested Loopに切り替わることも珍しくありません。オプティマイザは統計情報（テーブルの行数、値の分布）をもとに、そのクエリにとって最も安いと推定される方式を都度選んでいるわけです。
筆者の考え・所感
個人的には、この3つのアルゴリズムを知ってから、遅いJOINクエリへの向き合い方が変わりました。以前は「JOINが遅い」というレポートを受け取ると、反射的にインデックスを疑っていたのですが、実際には統計情報が古くなっていてオプティマイザがHash JoinとNested Loopの見積もりを誤っていた、というケースに何度か当たっています。ANALYZEでテーブルの統計を更新しただけで、実行計画がNested LoopからHash Joinに切り替わり、クエリが十数秒から1秒未満になったことがありました。
インデックスを足すことは対策の一つでしかなく、「今どのアルゴリズムが選ばれていて、なぜそれが選ばれているのか」をEXPLAINで確認する習慣のほうが、長期的には効くと感じています。特にNested Loopが選ばれている箇所にインデックスを足すのと、そもそも統計を更新してオプティマイザの判断そのものを直すのとでは、直している層が違います。前者は個別のクエリへの対症療法で、後者はオプティマイザの前提を正す作業です。両方必要になる場面はありますが、詰まったときにまずどちらを疑うかで、調査にかかる時間はだいぶ変わります。
まとめ
- JOINはSQL上の宣言にすぎず、実際の処理方式（Nested Loop / Hash Join / Sort Merge Join）はオプティマイザがテーブルの統計情報から選んでいる
- Nested Loopは外側テーブルが小さいときに、Hash Joinは片方をメモリ上のハッシュテーブルに収められるときに、Sort Merge Joinはすでにソート済みのときに強い
- 遅いJOINに遭遇したら、インデックスを足す前に
EXPLAINでどのアルゴリズムが選ばれているか、統計情報が古くなっていないかを確認すると、原因の切り分けが早くなる