汎用プログラミング言語におけるアルゴリズムの知識をRDBMSにおける知識として再利用しよう

　こんにちは。ディマージシェアの技術担当です。今回は、とても簡単なアルゴリズムの課題を題材に、いくつかの回答の紹介、加えてRDBMSのインデックスの仕組みまで一気通貫の知識として紹介したいと思います。

課題

　いわゆるkey value形式で保存されているデータがsrc, tgtの2つあり、f_keyの値が同じものを関連付けてsrc_idとtgt_idを同じレコードにしたい、という課題です。

src = [{src_id=1, f_key=f_key_1}, {src_id=2, f_key=f_key_2}, {src_id=3, f_key=f_key_3}]
tgt = [{tgt_id=111, f_key=f_key_1}, {tgt_id=222, f_key=f_key_2}, {tgt_id=333, f_key=f_key_3}]

上記の2つの配列に分かれたデータを、

[{src_id=1, tgt_id=111, f_key=f_key_1}, {src_id=2, tgt_id=222, f_key=f_key_2}, {src_id=3, tgt_id=333, f_key=f_key_3}]

のように纏めることができればOKです。

いくつかの回答例

2重ループを書く

　2重ループで上記の課題を実現しようとすると、例えば次のようになります。言語はJavaを採用しました。

for (Map<String,Object> p : src){
    String src_f_key = (String)p.get("f_key");
    for (Map<String,Object> q : tgt){
        String tgt_f_key = (String)q.get("f_key");
        if (src_f_key.equals(tgt_f_key)) {
            p.put("tgt_id", q.get("tgt_id"));
        }
    }
}

HashMapを使う

　HashMapを使うと次のように書くこともできます。

Map<String, Map<String,Object>> tgt_map = new HashMap<>();

for (Map<String,Object> p : tgt){
    tgt_map.put((String)p.get("f_key"), o);
}

for (Map<String,Object> p : src){
    p.put("tgt_id", tgt_map.get((String)p.get("f_key")).get("tgt_id"));
}

TreeMapを使う

　JavaのMapの実装はHashMapの他にTreeMapもあります。

Map<String, Map<String,Object>> tgt_map = new TreeMap<>();

for (Map<String,Object> p : tgt){
    tgt_map.put((String)p.get("f_key"), o);
}

for (Map<String,Object> p : src){
    p.put("tgt_id", tgt_map.get((String)p.get("f_key")).get("tgt_id"));
}

どの方法が正解？

　さて、簡単なお題ではありますが、3通りもの回答例を挙げることができました。どの方法を選ぶのが最適でしょう。実は、入力するデータの性質によって最適な方法が異なります。

2重ループは悪？

　ある程度アルゴリズムの性質に明るい人は2重ループに難色を示す方が一定数いると思います。データの件数が多いときに2重ループを書くと、確かに他に挙げたMapを使った方法の方が早いのですが、実は、データの件数が極めて少ないときに限り、2重ループはとても高速に動作します。
　ただ、2重ループは処理するデータ件数がちょっと増えるだけでパフォーマンスが悪くなり事故に繋がることもあるので、とりあえずMapで書けることを2重ループで書いている箇所を見つけたらMapに書き直すように指示するのは安全とも言えます。

Mapはどのタイプを使う？

　Mapの実装は主にHashとTreeの2通りが選べます。今回の課題ではHash方式を選ぶ方が良いでしょう。Treeは保持しているデータをソートや範囲で絞り込みたいときに威力を発揮します。
　（Hashはソートや範囲絞り込みができない代わりに、keyでデータを1つ指定する処理がとても高速です）

RDBMSとの関連

　これまでの文脈からRDBMSの話が出てくるのが意外に思う方もいらっしゃるかもしれません。実は、RDBMSのインデックスの仕組みに強い関連があります。
　今回の課題は、RDBMSの2テーブルをf_keyが一致する条件でJOINしてSELECTする処理に他なりません。このとき、2つのテーブルのf_keyカラムにINDEXが貼られていないと、レコード数が多いときにクエリの実行に時間がかかることをご存じの方は多いと思います。これは、先のJavaコードで2重ループを採用した場合とほぼ同じなのです。f_keyカラムにHashインデックスを貼ればHash方式に、Treeインデックスを貼ればTree方式に等しくなります。
※インデックスのタイプが選べないRDBMSではTree方式が標準で採用されています
　RDBMSのインデックスは、レコードを検索しやすい形に予め持ち替えておき、クエリの実行を高速化する仕組みです。Javaコードで、Mapを用いて特定の列で検索を早くできるようにデータを持ち替えたこととほぼ同じです。
RDBMSでインデックスとしてストレージに保存されている部分をJavaコードでオンタイムで生成したようなものです。
　逆に言えば、RDBMSでインデックスを貼らない、インデックスを貼る、のようなパフォーマンスチューニングの選択は、Javaコードでは2重ループを採用する、Mapに持ち替える方法を採用する、に言い換えることができます。実行するエンジンが違っても本質的には大差ないのです。

まとめ

　簡単なアルゴリズムの課題でも、回答例は多岐に渡ることを紹介しました。また、似たようなことをRDBMSで実現する際、インデックスの有無がアルゴリズムの選択にとても似ていることを紹介しました。
　アルゴリズムに関する知識は本質を上手に捉えることで、Javaのような汎用プログラミング言語から、RDBMSまで共通して役に立てることができます。