【テクニカル・上級編】ハッシュ結合 – PostgreSQL

ハッシュ結合の深淵：PostgreSQLの「静かなる加速器」を読み解く

PostgreSQLのクエリプランナーが `Hash Join` を選択したとき、それはエンジニアにとってひとつの合図です。「ここからは、メモリという戦場で勝負が決まる」という合図ですね。

Nested LoopがO(NM)の呪縛に囚われ、Merge Joinがソートという重い代償を求める中、Hash JoinはO(N+M)という計算量で、大規模なデータセットを鮮やかに捌いていく。この「ハッシュテーブルを構築し、ルックアップする」という一見シンプルなアルゴリズムですが、その内部構造はPostgreSQLのメモリ管理の妙が凝縮された、極めて職人気質な代物です。

今日は、そんなHash Joinの「深層」に少し潜り込んでみましょう。

—

1. 「バケット」と「バッチ」：メモリの制約をどう乗り越えるか

Hash Joinを語る上で欠かせないのが、`work_mem` というパラメータの存在です。

多くの若手エンジニアは「`work_mem` を増やせば速くなる」という表面的な理解で止まってしまいがちですが、実際にはもっと泥臭いドラマが起きています。PostgreSQLのHash Joinには、大きく分けて2つのフェーズがあります。

1. Buildフェーズ: 小さい方のテーブル（Inner側）をスキャンし、ハッシュテーブルを構築する。
2. Probeフェーズ: 大きい方のテーブル（Outer側）をスキャンし、ハッシュ値でルックアップする。

ここで問題になるのが、ハッシュテーブルが `work_mem` を超えてしまった場合です。PostgreSQLはここで「マルチパス・ハッシュ結合」という戦略を繰り出します。データを複数の「バッチ（Batch）」に分割し、一部を一時ファイル（ディスク）へ吐き出しながら、段階的に処理を進めるのです。

ここがトラブルシューティングの要点です：
もし `EXPLAIN ANALYZE` の結果に `Batches: N` や `Disk: NkB` といった表記が現れたら、それは性能劣化の赤信号。メモリ不足によって、高速なRAM上の処理が、低速なI/Oバウンドな処理へと変貌してしまったことを意味します。「なぜハッシュテーブルが溢れたのか？」という問いに対し、カーディナリティの見積もりミス（統計情報の鮮度）を疑うのが、熟練のエンジニアの第一手ですね。

—

2. ハッシュ衝突と「鎖」の管理

メモリ上に構築されるハッシュテーブルは、単純な配列ではありません。ハッシュ値が衝突（Collision）した場合に備え、各バケットにはエントリを繋ぐリスト構造が用意されています。

ここで面白いのが、PostgreSQLのハッシュ関数がどれだけ優秀か、という話です。最新のバージョンでは、ハッシュの分散は非常に高度に最適化されていますが、依然として「最悪のシナリオ」は存在します。キーの偏りが極端な場合、特定のバケットにエントリが集中し、検索効率がO(1)からO(N)へと劣化します。

もし、特定の結合キーに対して極端な偏りがあるデータセットを扱う場合は、ハッシュテーブルの深さを監視することも重要です。稀なケースですが、インデックスのカーディナリティが低いカラムでの結合は、Hash Joinのパフォーマンスを密かに蝕んでいるかもしれません。

—

3. パフォーマンスチューニングの「作法」

Hash Joinを使いこなすための、私なりの鉄則をいくつか共有しましょう。

統計情報の鮮度を疑え: `ANALYZE` を怠ることは、目隠しをして高速道路を走るようなものです。プランナーがInner側とOuter側のサイズを誤認すると、本来Hash Joinが適さない場面でHash Joinが選択され、メモリを浪費します。
`work_mem` は「全コネクションの合計」ではない: これ、勘違いしている人が非常に多いんです。`work_mem` は「1つのノードあたりのメモリ」です。同時接続数が多いシステムで闇雲に数GBを割り当てると、即座にOOM Killerの餌食になります。負荷テストを行い、妥当なラインを慎重に見極めるのがプロの仕事です。
Parallel Hash Joinの活用: 近年のPostgreSQLでは、複数のワーカープロセスでハッシュテーブルを共有する「Parallel Hash Join」が非常に強力です。もしCPUのコア数が余っているなら、`max_parallel_workers_per_gather` を調整して、並列化の恩恵を最大限に引き出してみてください。

—

最後に

Hash Joinは、PostgreSQLのクエリエンジンが持つ「計算資源をいかに効率的に使い切るか」という執念の結晶です。内部で何が起きているか、メモリのどの領域でI/Oが発生しているのかを想像しながらEXPLAINを読むようになると、データベースのチューニングは単なる作業から、知的な探索へと変わります。

皆さんの環境で、もしHash Joinがボトルネックになっているのなら、それは「データが増えた」という成長の証です。それをどう捌くか。その設計こそが、エンジニアとしての腕の見せ所ではないでしょうか。

それでは、また次回の深掘りでお会いしましょう。Happy Hacking!