Nested Loop / Hash / Merge Join

行が 100 倍になったら、JOIN が返ってこなくなった

ユーザーと注文を結合するクエリが、テスト環境では 30 ミリ秒で返っていたとします。本番のデータで同じものを流したら、数分待っても返ってきません。SQL は 1 文字も違いません。

素直に結合する手順は、外側のテーブルを 1 行ずつ取り出し、そのたびに内側のテーブルから相手を探す二重ループです。実行計画には Nested Loop (ネステッドループ結合) と表示されます。

for u in users:
    for o in orders:
        if o.user_id == u.id:
            出力する

ユーザー 100 件、注文 1000 件なら 10 万回の比較で済みます。ユーザー 1 万件、注文 100 万件になると 100 億回です。件数が 100 倍になると、かかる時間は 1 万倍になります。テスト環境で速かったことは、何の保証にもなりません。

内側を毎回探し直さない

この二重ループが遅いのは、内側を毎回頭から探しているからです。避け方は 2 つあります。

1 つは、内側の結合列に索引があることです。すると内側は 1 回の探索で相手にたどり着けるので、外側の行数ぶんの探索だけで終わります。外側が絞り込みで数十件まで減っているなら、これがいちばん速い形になります。

もう 1 つは、内側を一度だけ全部読んで、結合列をキーにした表をメモリ上に作ることです。あとは外側を 1 行ずつ流しながらその表を引くだけで相手が見つかります。両方のテーブルが大きく、外側もほとんど絞れないときは、こちらが有利です。ハッシュ結合と呼ばれる方式で、= での結合にしか使えず、表がメモリに収まらないと一時ファイルへ退避するぶん遅くなります。

ハッシュ結合が = にしか使えないのは、キーから置き場所を直接計算する仕組みだからです。「近い値」を探すことはできないので、>= や BETWEEN で結ぶ結合には使えません。

両方が同じ列の順にすでに並んでいるなら、先頭から突き合わせて 1 回ずつ進めるだけで済みます。マージ結合 (実行計画では Merge Join) と呼ばれる方式です。索引の並び順をそのまま使えるときに選ばれる形です。ただし等価条件の無い範囲だけの結合には、Hash Join も Merge Join も通常は使えません。

選ぶのはこちらではない

どれを使うかは、普通はプランナが行数の見積もりから選びます (製品によっては指定する手段もあります)。ですから JOIN が遅いときも、手順を指定しに行くのではなく、まず選ばれた手順を確かめます。

Hash Join
  Hash Cond: (o.user_id = u.id)
  ->  Seq Scan on orders o
  ->  Hash
        ->  Index Scan using idx_users_country on users u

こちらが動かせるのは、判断の材料の方です。片方をもっと絞れないか、内側の結合列に索引があるか、メモリ上に表を作る余地があるか。そこが変われば、選ばれる手順も変わります。

どちらを外側にするかもプランナが決めます。小さい方を外側に置けば探索の回数が減るので、絞り込みが効く側を外に回すのが基本形です。ただしこの判断も行数の見積もりに基づいているので、見積もりが外れていれば内外の割り当ても一緒に間違えます。JOIN が想定外に遅いとき、疑うべきは結合の書き方ではなく、その手前の見積もりであることがよくあります。