ソートマージ結合法を実装してみた

リレーショナルデータベース入門―データモデル・SQL・管理システム・NoSQL (Information & Computing)

関係データベースの本を読んでいて，結合質問を処理するアルゴリズムのソートマージ結合法について知ったのですが，動作例だけでアルゴリズムが書いてなかったので，実装をしました．

結合質問とは

テーブルRとSがあって，それぞれ行数がMとNであるとします．みなさんもこういう SQL クエリを書いたことがあると思います．

SELECT R.hoge, S.fuga FROM R
INNER JOIN S ON R.id = S.hoge_id

「テーブル R と S のデータのうち， R.id = S.hoge_id を満足する行の組を結合したもののみを返せ」という意味のクエリです． たとえば，テーブル R が以下のようになっているとします．

id	hoge
1	"a1"
2	"a2"
3	"a3"
4	"a4"

また，テーブル S が以下のようになっているとします．

hoge_id	fuga
1	"c1"
2	"c2"
2	"c3"
3	"c4"

これらのテーブルに対して上のクエリを実行した結果は次の通りになります．

hoge	fuga
"a1"	"c1"
"a2"	"c2"
"a2"	"c3"
"a4"	"c4"

ところで，これ以降はテーブルの全てのカラムを取得するときのみを考えることにします．

総当たり法

さてこのクエリに答えるにはどうすればよいかを考えるのですが，すぐ思いつくのは総当たり法でしょう． したがって，たとえばこのような実装が考えられます．

def brute_force(R, S):
    result = [] # 回答を格納するリスト
    for r in R: # R の全ての行 r について
        for s in S: # S の全ての行 s について
            if r[-1] == s[0]: # (r の結合属性の値) == (s の結合属性の値)
                result.append(r + s) # r と s を結合したものを回答に加える
    return result # 回答を返す

しかしながらこの方法は計算量が O(MN) となるので，テーブルの行数が大きくなると実用的な時間でクエリに答えることができなくなります*1．

ソートマージ結合法

ソートマージ結合法 (Sort-merge join) は，総当たり法よりも高速に結合質問に答えるためのアルゴリズムです．実装したコードを下に示します*2．

def sortmerge(R, S):
    M, N = len(R), len(S) # テーブルRとSの行数
    p1, p2, p3 = 0, 0, 0 # 3つのポインタ．p1 は R，p2 と p3 は S の先頭を指す．
    result = [] # 回答を格納するリスト
    while p1 < M and p3 < N: # p1 が R の終端を指す，もしくは p3 が S の終端を指すまで
        if p2 >= N: # p2 が S の終端を指しているなら
            p1 += 1 # p1 を進める
            p2 = p3 # p2 を p3 に戻す
        else:
            if R[p1][-1] < S[p2][0]: # (R[p1] の結合属性の値) < (S[p2] の結合属性の値)
                p1 += 1 # p1 を進める
                p2 = p3 # p2 を p3 に戻す
            elif R[p1][-1] == S[p2][0]: # (R[p1] の結合属性の値) == (S[p2] の結合属性の値)
                result.append(R[p1] + S[p2]) # R[p1] と S[p2] を結合したものを回答に加える
                p2 += 1 # p2 を進める
            else: # (R[p1] の結合属性の値) > (S[p2] の結合属性の値)
                p3 += 1 # p3 を進める
                p2 = p3 # p2 を p3 に合わせる
    return result # 回答を返す

計算量は，RとSが共にソート済みであるとすると O(M + N) となります*3．

まとめ

ソートマージ結合法を知りました．

アルゴリズムの紹介をするならせめて疑似コードを書いてほしい．

*1:実際にはインデックスが貼られていることが多いので，もう少し高速にはなると思われます．

*2:R と S が昇順にソートされているという仮定をしています．

*3:ソートが必要な場合でも O(MlogM + NlogN) となります．