Nested Loop / Hash / Merge Join

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

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

素直に結合する手順は、外側のテーブルを 1 行ずつ取り出し、そのたびに内側のテーブルから相手を探す二重ループです。

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 回ずつ進めるだけで済みます。索引の並び順をそのまま使えるときに選ばれる形で、範囲での結合でもこの順序を活かせます。

選ぶのはこちらではない

どれを使うかを SQL で指定することはありません。プランナが行数の見積もりから決めます。ですから 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 が想定外に遅いとき、疑うべきは結合の書き方ではなく、その手前の見積もりであることがよくあります。