リレーショナルデータベースのインデックス実装とクエリー最適化

データベースの勉強に、かわいいデータベースができました。
http://d.hatena.ne.jp/nowokay/20120817#1345197962

で、ここに、インデックスを実装してみました。今回はハッシュインデックスとツリーインデックスを実装してます。
こんな感じでインデックスが追加できます。

//インデックス追加
shohin.addIndex("shohin_id", IndexType.HASH);
shohin.addIndex("price", IndexType.TREE);
kubun.addIndex("kubun_id", IndexType.HASH);

joinの高速化

で、実際にインデックスを張って処理が速くなるか試してみます。ベンチマークとしては手抜きですけど、参考にはなると思います。
shohinテーブルに10万件、kubunテーブルに1万件のデータを用意して、結合してみます。

Query
  .from("shohin")
  .leftJoin("kubun", "kubun_id")

インデックスなしだと次のような実行時間になりました

join without index:7671ms

8秒近くかかっていますね。これは、shohinの一件ごとに、kubunテーブルを平均して5000件比較するので、10万×5000回の比較が行われるためです。

ここで、join対象のkubunテーブルのkubun_idフィールドにツリーインデックスを張ってみます。

kubun.addIndex("kubun_id", IndexType.TREE);

そうすると、実行時間は次のようになりました。

join with tree index:42ms

かなり速くなってます。
比較回数が、一件につきlog 2 10000、つまり13回程度になるので、1/500くらいになります。実際にかかる時間は比較だけではないので、1/200程度の高速化になっています。

さらに、kubun_idフィールドにハッシュインデックスを張ってみます。

kubun.addIndex("kubun_id", IndexType.HASH);

そうすると、さらに実行時間は早くなっています。

join with hash index:24ms

比較の高速化

「小なり」の比較にはツリーインデックスが使えます。
ここでは、shohinテーブルのpriceフィールドにツリーインデックスがあるかないかでpriceの比較を試してみます。
こんな感じで、ランダムな数字で比較してます。

Query
  .from("shohin")
  .lessThan("price", r.nextInt(10000))

ツリーインデックスなしでは500回実行すると次のような実行時間になっています。

compare without index:1124ms

ここにツリーインデックスを追加してみます。

shohin.addIndex("price", IndexType.TREE);

そうすると、実行時間が半分になりました。

compare with index:605ms

集計処理の高速化

集計処理も内部で並べ替えを行っているので、ツリーインデックスを使うと速くなるはずです。
次のような集計を行ってみます。

Query
  .from("shohin")
  .groupBy("kubun_id", new Count("kubun_id"), new Average("price"))

インデックスのない場合は30回実行するとこのくらい。

aggregation without index:1712ms

で、shohinテーブルのkubun_idにツリーインデックスをつけてみます。

shohin.addIndex("kubun_id", IndexType.TREE);

そうすると、30回実行で次のような実行時間になりました。

aggregation with index:610ms

1/3くらいになってますね。
実際は、インデックスではすでに値がグループ化されているので、これを使うような処理をすると、もっと効率がよくなるはずです。また、その場合はハッシュインデックスも集計処理に使えるようになります。

追記(2012/8/21)：修正したらさらに2/3くらいの処理時間になりました。
http://d.hatena.ne.jp/nowokay/20120821#1345530571

クエリー最適化

ところで、たとえば次のようなSQLがあるとします。

SELECT shohin_name, kubun_name, price
FROM shohin
LEFT JOIN kubun ON shohin.kubun_id=kubun.kubun_id
WHERE price < 1000

これを素直に実行する場合、こんなコードになります。

Query
  .from("shohin")
  .leftJoin("kubun", "kubun_id")
  .lessThan("price", 1000)
  .select("shohin_name", "kubun_name", "price");

ただ、この場合には、leftJoinを行った時点でインデックスがなくなってしまうので、せっかくshohinテーブルに設定したインデックスが使われません。
そこで、あらかじめshohinテーブルをpriceで抽出しておいて、joinを行えば、ツリーインデックスを活用することができます。

Query
  .from(Query
    .from("shohin")
    .lessThan("price", 1000))
  .leftJoin("kubun", "kubun_id")
  .select("shohin_name", "kubun_name", "price");

処理時間も、200回実行して、最適化なしではこのようになります。

plain query:5604ms

これを最適化したクエリで実行すると次のようになります。

optimized query:745ms

1/8くらいになりました。
ただし、これは、1万までの値が格納されているものを1000で抽出しているため、結果のデータ量が1/10になっていることも影響します。

たとえば、比較値を5000とすると、だいたい半分のデータが抽出されることになりますが、そうすると次のように、あまり実行時間に改善が見られなくなります。

plain query:5722ms
optimized query:4552ms

比較値を1万にして、1万より小さい値を抽出すると、結局すべてのデータが抽出されますが、この場合はインデックスを使うほうが遅いということになっています。

plain query:6167ms
optimized query:8786ms

今回は、手作業でクエリーの最適化を行っていますが、実際にはSQLをパースしたあとに実行計画を作って、自動的に最適化を行う必要があります。
このとき、基本はインデックスが使えるときには使うということになりますが、データの分布によってインデックスが効かない場合もあります。
そこで、クエリーの最適化のためには、データのヒストグラムなど統計情報も大事になります。

まあ、このプログラムの場合は、インデックスからのデータ取得を効率化すれば、もう少しどうにかなると思うのですけど。

ソースなど

インデックスを実装した、かわいいデータベースのソースはこっちです。
https://gist.github.com/3380142/f29ebc83a695a7367982830b1a0157c8f72ba970

あと、ベンチマーク的なものはこのソース

package kis.basicdb.bench;
import java.util.Random;
import static kis.basicdb.App.*;
/**
 *
 * @author naoki
 */
public class IndexBench {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Random r = new Random(1234);
        //商品データの準備
        Table shohin = Table.create("shohin", 
                new String[]{"shohin_id", "shohin_name", "kubun_id", "price"});
        for(int i = 0; i < 100000; ++i){
            //適当な名前
            StringBuilder sb = new StringBuilder();
            int len = r.nextInt(5) + 3;
            for(int j = 0; j < len; ++j){
                sb.append((char)('あ' + r.nextInt(82)));
            }
            shohin.insert(i + 1, sb.toString(), r.nextInt(10000) + 1, r.nextInt(990) * 10);
        }
        System.out.println(shohin);
        //区分データの準備
        Table kubun = Table.create("kubun", 
                new String[]{"kubun_id", "kubun_name"});
        for(int i = 0; i < 10000; ++i){
            //適当な名前
            StringBuilder sb = new StringBuilder();
            int len = r.nextInt(5) + 3;
            for(int j = 0; j < len; ++j){
                sb.append((char)('ア' + r.nextInt(82)));
            }
            kubun.insert(i + 1, sb.toString());
        }
        System.out.println(kubun);

        long now;
        //インデックスなしの結合
        System.out.println(Query.from("shohin").leftJoin("kubun", "kubun_id"));//空処理
        now = System.currentTimeMillis();
        System.out.println(Query.from("shohin").leftJoin("kubun", "kubun_id"));
        System.out.println("join without index:" + (System.currentTimeMillis() - now));

        now = System.currentTimeMillis();
        kubun.addIndex("kubun_id", IndexType.TREE);
        System.out.println("create tree index for kubun:" + (System.currentTimeMillis() - now) + "ms");

        //Treeインデックスで結合
        System.out.println(Query.from("shohin").leftJoin("kubun", "kubun_id"));//空処理
        now = System.currentTimeMillis();
        System.out.println(Query.from("shohin").leftJoin("kubun", "kubun_id"));
        System.out.println("join with tree index:" + (System.currentTimeMillis() - now));
        
        now = System.currentTimeMillis();
        kubun.addIndex("kubun_id", IndexType.HASH);
        System.out.println("create hash index for kubun:" + (System.currentTimeMillis() - now) + "ms");

        //hashインデックスで結合
        System.out.println(Query.from("shohin").leftJoin("kubun", "kubun_id"));//空処理
        now = System.currentTimeMillis();
        System.out.println(Query.from("shohin").leftJoin("kubun", "kubun_id"));
        System.out.println("join with hash index:" + (System.currentTimeMillis() - now) + "ms");

        //インデックスなしで集計
        String result = Query.from("shohin").groupBy("kubun_id", new Count("kubun_id"), new Average("price")).toString();
        now = System.currentTimeMillis();
        for(int i = 0; i < 30; ++i){
            result = Query.from("shohin").groupBy("kubun_id", new Count("kubun_id"), new Average("price")).toString();
        }
        System.out.println(result);
        System.out.println("aggregation without index:" + (System.currentTimeMillis() - now) + "ms");

        //treeインデックスつきで集計
        shohin.addIndex("kubun_id", IndexType.TREE);
        result = Query.from("shohin").groupBy("kubun_id", new Count("kubun_id"), new Average("price")).toString();
        now = System.currentTimeMillis();
        result = "";
        for(int i = 0; i < 30; ++i){
            result = Query.from("shohin").groupBy("kubun_id", new Count("kubun_id"), new Average("price")).toString();
        }
        System.out.println(result);
        System.out.println("aggregation with index:" + (System.currentTimeMillis() - now) + "ms");
        
        
        //インデックスなしで比較
        result = Query.from("shohin").lessThan("price", r.nextInt(10000)).toString();
        now = System.currentTimeMillis();
        for(int i = 0; i < 500; ++i){
            result = Query.from("shohin").lessThan("price", r.nextInt(10000)).toString();
        }
        System.out.println(result);
        System.out.println("compare without index:" + (System.currentTimeMillis() - now) + "ms");
        
        //インデックス付で比較
        shohin.addIndex("price", IndexType.TREE);
        result = Query.from("shohin").lessThan("price", r.nextInt(10000)).toString();
        now = System.currentTimeMillis();
        for(int i = 0; i < 500; ++i){
            result = Query.from("shohin").lessThan("price", r.nextInt(10000)).toString();
        }
        System.out.println(result);
        System.out.println("compare with index:" + (System.currentTimeMillis() - now) + "ms");
        
        //最適化なしクエリー
        QueryObj q = Query
                .from("shohin")
                .leftJoin("kubun", "kubun_id")
                .lessThan("price", 1000)
                .select("shohin_name", "kubun_name", "price");
        now = System.currentTimeMillis();
        for(int i = 0; i < 200; ++i){
            q = Query
                    .from("shohin")
                    .leftJoin("kubun", "kubun_id")
                    .lessThan("price", 1000)
                    .select("shohin_name", "kubun_name", "price");
        }
        System.out.println(q.toString());
        System.out.println(((Relation)q).getTaples().size());
        System.out.println("plain query:" + (System.currentTimeMillis() - now) + "ms");

        //最適化ありクエリー
        q = Query
            .from(Query.from("shohin").lessThan("price", 1000))
            .leftJoin("kubun", "kubun_id")
            .select("shohin_name", "kubun_name", "price");
        now = System.currentTimeMillis();
        for(int i = 0; i < 200; ++i){
            q = Query
                    .from(Query.from("shohin").lessThan("price", 1000))
                    .leftJoin("kubun", "kubun_id")
                    .select("shohin_name", "kubun_name", "price");
        }
        System.out.println(q.toString());
        System.out.println(((Relation)q).getTaples().size());
        System.out.println("optimized query:" + (System.currentTimeMillis() - now) + "ms");
    }
}