【入門編】結合アルゴリズム：マージ結合 – PostgreSQL

こんにちは！データベースエンジニアの技術ブログへようこそ。

普段、PostgreSQLを触っていて「クエリがなんだか遅いな……」と悩んだことはありませんか？実は、データベースの中では、私たちが書いたSQLを「どうやってデータを集めようかな？」と、賢いAIのようなプランナーが一生懸命考えてくれているんです。

今日は、その中でも少し特殊で、でもハマるとめちゃくちゃ速い「マージ結合（Merge Join）」について、難しい専門用語は抜きにしてお話ししますね。

—

データベースで「結合（JOIN）」をするということは、例えるなら「バラバラの2つの名簿を、特定の条件で突き合わせて1つのリストにまとめる作業」です。

たとえば、「社員名簿」と「部署名簿」を「部署ID」でつなげるような場面ですね。この作業、やり方は大きく分けていくつかあるんですが、今日はその中の「マージ結合」という手法に注目してみましょう。

想像してみてください。あなたは今、「数字がバラバラに書かれたカードの山」を2つ持っています。この2つの山から、同じ数字が書かれたカードを見つけてペアにしたいとします。

片っ端から1枚ずつ手に取り、「こっちの山に同じ数字はあるかな？」と探す方法。これだと、カードが増えるたびに時間がかかりすぎて、日が暮れてしまいますよね。

ここでマージ結合の登場です。この手法は、「あらかじめ両方の山を小さい順に並び替えておく」というルールを使います。

1. 両方の山を「1, 2, 3…」と順番に並べる（ソート）。
2. あとは、両方の山の先頭から順番に「次はどっちが大きいかな？」と確認しながら、スルスルとペアを作っていく。

どうでしょう？整列さえしてあれば、あとは上から順に見ていくだけなので、すごく効率的だと思いませんか？これがマージ結合の正体です。

マージ結合には、得意なことと苦手なことがあります。

さっきの「力技」だと、データが100万件あったら終わりのない作業になりますが、マージ結合なら「一度並べ替えさえすれば、あとは一直線」なので、非常に安定して速いんです。

もしデータがまだ並んでいなくて、わざわざ並び替えるところから始めなきゃいけない場合、その「お片付け（ソート）」に時間がかかってしまうことがあります。

PostgreSQLがマージ結合を選んでくれるのは、主にこんなときです。

元々データが並んでいるとき： インデックスという「目次」のおかげでデータが並んでいる状態なら、並び替える手間がないのでマージ結合は無敵です。
結合するデータがどちらも巨大なとき： どちらのテーブルも大きくて、「力技」だと時間がかかりすぎる……そんなとき、PostgreSQLは「よし、並び替えてからマージしよう！」という賢い選択をします。

マージ結合は、いわば「準備をしっかりして、効率よく処理する」という、とても理にかなった手法です。

もし皆さんが書いたクエリで「マージ結合が使われているな」と実行計画（Explain）で見つけたら、それはデータベースが「このデータ量なら、並び替えてから突き合わせるのが一番楽だね！」と判断してくれた証拠です。

「なぜこの方法を選んだのかな？」と想像してみるだけで、SQLのチューニングはぐっと楽しくなりますよ。ぜひ、皆さんも自分の書いたコードの裏側を覗いてみてくださいね！

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