基本情報技術者 2017年春期午前（科目A）問27

問題文

RDBMSが二つの表を結合する方法のうち、ソートマージ結合法に関する記述はどれか。

🖊️ 解答を隠して解いてみる

選択肢

ア：一方の表の結合する列がインデックスに含まれている場合、もう一方の表の結合する列とインデックスの値で結合する。

イ：一方の表の結合する列の値でハッシュ表を作成し、もう一方の表の結合する列と結合する。

ウ：一方の表の結合する列の値を順に読み出し、もう一方の表の結合する列と結合する。

エ：結合する列の値で並べ替えたそれぞれの表の行を、先頭から順に結合する。（正解）

🔒 解説は解答すると表示されます

ソートマージ結合【午前解説】

正解の理由

正解はエです。ソートマージ結合は、結合する両表を結合列の値でソート（外部ソートを含む）し、その後に先頭からポインタを進めながら同値（あるいは条件に合う）行をマージしていく結合アルゴリズムです。ソート済みの入力に対しては単純で I/O 回数が少なく済み、特にレンジ結合や既にソート済みのデータに有利です。選択肢エの記述はこの手順を正確に表しています。

解法ステップ

問題文で「ソート」や「並べ替え」、「先頭から順に」というキーワードを探す。
「ハッシュ表」や「インデックス」の語がある選択肢は別手法（ハッシュ結合、インデックス活用）と切り分ける。
ソートしてからマージする流れが明示されている選択肢を正解にする（＝エ）。

選択肢別の誤答解説

ア: 一方の表の結合列がインデックスに含まれている場合にインデックスの値で結合するのは「インデックスネストループ結合」やインデックス利用による結合であり、ソートマージではありません。
イ: 一方の表の結合列の値でハッシュ表を作成し結合するのは「ハッシュ結合」です。大量のメモリが必要になる点や、ハッシュ関数による分割が特徴です。
ウ: 「値を順に読み出し、もう一方と結合する」という記述は単純走査やネストループを示唆し、ソート手順が明示されていないためソートマージではありません。
エ: 両表を結合列の値で並べ替え、その後先頭から順に行を結合する、まさにソートマージ結合の定義を表しています（正解）。

よくある誤解

インデックスがあれば必ず速いと考える：インデックスを使うのはインデックスネストループ型であり、ソートマージとは別手法です。
「順に読み出す」= ソート済みと誤解する：選択肢ウの表現は単純に順次走査することを示すだけで、ソート済みであるとは限りません。
ハッシュ結合と混同する：ハッシュ結合（選択肢イ）はキーでハッシュ表を作る点が決定的に違います。

補足コラム

コスト（概算）：両表をソートするコストが支配的で、 $O (n lo g n + m lo g m)$ のソートに加え、マージは $O (n + m)$ 。既にソート済みやクラスタ化インデックスがある場合はソートコストが不要になります。
メモリと外部ソート：大きな表では外部ソート（ディスクを用いたマルチパスソート）が必要になり、I/O 最適化が重要です。
利点・欠点：等値結合以外（範囲結合など）にも対応しやすい点が利点。ハッシュ結合に比べメモリ使用が少ない場合が多いが、ソートのオーバーヘッドが欠点です。
実運用では、オプティマイザが表サイズ・インデックス・メモリ状況を見て最適法を選択します。

FAQ

Q1: ソートマージ結合は等値結合以外にも使えますか？
A1: はい。順序を活かすため、範囲結合や不等号を含む結合にも適用しやすいです。

Q2: 入力が既にソート済みならどうなりますか？
A2: ソートコストが不要になるため非常に効率的になり、マージのみで済みます。

Q3: ハッシュ結合と比べてどちらが速いですか？
A3: データ特性によります。ハッシュ結合は等値結合でメモリに収まれば速いですが、メモリ不足や範囲結合ではソートマージが有利です。

Q4: 重複キー（同値の複数行）はどう処理しますか？
A4: 両表の該当するキー群をそれぞれスキャンして全組合せを出力する（重複を扱える）ようにマージ処理します。

Q5: 実装例はありますか？
A5: 小規模の例として、二つのソート済み配列をマージして結合する Python コードは以下の通りです。

def sort_merge_join(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            i += 1
        elif left[i] > right[j]:
            j += 1
        else:
            # 等値の場合、両方のグループを展開して全組合せを追加
            lv, rv = left[i], right[j]
            li, rj = i, j
            left_group, right_group = [], []
            while li < len(left) and left[li] == lv:
                left_group.append(left[li]); li += 1
            while rj < len(right) and right[rj] == rv:
                right_group.append(right[rj]); rj += 1
            for a in left_group:
                for b in right_group:
                    result.append((a, b))
            i, j = li, rj
    return result