【入門編】結合戦略: ハッシュ結合 – PostgreSQL

こんにちは！データベースの世界へようこそ。

普段、何気なくSQLを書いていると「結合（JOIN）」って当たり前のように使いますよね。「AテーブルとBテーブルをくっつけて、必要なデータを引き出す」。これ、実はデータベースの中ではかなり頭を使う作業なんです。

今日は、その中でも特に「えっ、そんな効率的な方法があるの？」と驚かれる、「ハッシュ結合」についてお話しします。専門用語でガチガチにするのはやめて、皆さんの日常にある「あるシーン」に例えて解説してみますね。

—

想像してみてください。あなたは今、1,000人規模のパーティー会場の受付にいます。
手元には2つのリストがあります。

1. リストA（参加者名簿）： 全1,000人分の名前がバラバラに書かれている。
2. リストB（お土産リスト）： 誰にどのお土産を渡すかが書かれている。

ここで、「リストAの人が来たら、リストBからその人のお土産を探して渡す」という作業を命じられたとします。

もし、リストAの人が来るたびに、リストBを最初から最後まで指でなぞって探していたらどうでしょう？ 1人探すのに1分かかるとしたら、1,000人分で1,000分……つまり16時間以上もかかってしまいます。これではパーティーが終わってしまいますよね（笑）。

—

この作業を劇的に速くする方法があります。それが「ハッシュ結合」の考え方です。

まず、「リストB（お土産リスト）」をあらかじめ全部整理して、脳内（メモリ上）で「ハッシュテーブル」という即席のインデックスを作ってしまうんです。

例えば、「名前の頭文字」や「あいうえお順」といった独自のルールで、「あ」の人はこの箱、「か」の人はこの箱、というふうに分類して、すぐに取り出せる状態にしておきます。

準備ができたら、あとは簡単です。
参加者が来たら、その名前を見て「あ、この人は『た行』の箱ね」と、一瞬でお土産を見つけ出せます。

データベースもこれと同じことをやっているんです。

1. 構築フェーズ： 小さい方のテーブルをメモリ上に「辞書」のように整理する（これがハッシュテーブル！）。
2. プローブ（探索）フェーズ： もう一つのテーブルをスキャンしながら、辞書をパッと引いて情報をくっつける。

これなら、リストを何度も何度も往復して探す必要がありませんよね。

—

ここまで聞くと「じゃあ全部ハッシュ結合でいいじゃん！」と思うかもしれませんが、データベースの世界に銀の弾丸（万能な解決策）はありません。

ハッシュ結合にも弱点があるんです。

メモリをたくさん食う： メモリ上に辞書を作るので、そのテーブルがあまりに巨大すぎるとメモリから溢れてしまい、結局ディスクに書き出すという「余計な手間」が発生して逆に遅くなります。
「等しい（＝）」でしか使えない： 「Aさんのお土産は？」という等価結合には強いですが、「名前が5文字以上の人」のような範囲指定の検索には向いていません。

—

PostgreSQLのオプティマイザ（実行計画を立てる司令塔）は、とても優秀です。データ量やメモリの空き具合を見て、「今はネステッドループより、ハッシュ結合でいこう！」と瞬時に判断しています。

私たちがやるべきことは、「なぜ今、データベースはハッシュ結合を選んだんだろう？」と、実行計画（EXPLAIN）を眺めて想像してみることです。

「ああ、このテーブルは小さいから、メモリに展開したほうが速いと判断したんだな」
「データが大きすぎて、ハッシュ結合を諦めて別の方法に変えたんだな」

そんなふうにデータベースと対話できるようになると、チューニングが一気に楽しくなりますよ！

もし皆さんのSQLが遅いなと感じたら、ぜひ一度 `EXPLAIN` を叩いてみてください。そこには、データベースが一生懸命考えている「戦略」が隠されていますから。

それでは、また次回のブログでお会いしましょう！Happy Querying!