Database Cracking

S. Idreos et al. "Database Cracking," CIDR(2007). メモ。

  • MonetDBプロジェクトのなかで生じた話。
    • そもそもインデックスを作成したりするのは、ユーザが自分の行うクエリについてよく知っている場合である。
    • OLAPでアドホッククエリを考えると、そもそもそれを知っているユーザはなかなか居ない。
  • そこで、アドホッククエリが飛んでくると、そのクエリを情報としてデータベースの実際のデータ配置を変更してしまうというおはなし。
  • カラムストアのあるカラムに対する、Selectionが発行されると(SQLのWHERE句)、それに基づいて水平方向への分割を行う。
    • 分割したり、変更したりするためのカラム全体をコピーする。
    • 分割は、実際には提示されているアルゴリズムのように、最小限のvalueの移動のみを行う。
    • ポイントは、範囲ごとに分割はするがソートはしていないこと。
  • 維持管理のコストを考えなければ、ソートしたほうが良さそうではあるが、そのコストは極めて高い。
  • MonetDBでは、リレーショナル代数をバイナリオペレータと呼ばれるオペレーターに分解して実行する。例えば、
    • select(Ra, 5, 10)
    • select(Rb, 9, 20)
    • OIDintersect(Ra1, Rb1)
    • fetch(Rc, Ra2);

のようなオペレータがある。このオペレータのフルスペックが重要だと思う。
基本的には、カラムストアでは、各カラムの各値にレコードIDを(monetDBではoid、C-storeではオフセット)つけておくことで後々、もとのテーブルに戻せるようにしている。

  • この論文では、各オペレータに対してCracking Indexを利用出来るような拡張について論じている。
    • cracker.selectでは、最初の呼び出しでは結果を実体化したり、そもそもある範囲を再構成するので、初回に呼ばれたときには、通常のselectに比べると、30%遅い。でも、次回の検索からは早い。
    • が、OIDintersectでは、crackerでは遅い。元々、MonetDBでは、各カラムはoidで並んでいるので、OIDintersectはMerge-sortの後半部分をすればよく、早い。が、crackerでは其の順番が崩れる。
    • なので、rel_selectオペレータを用意し、二つのリレーションを入力とする。片方は、oidで並んだテーブルとし、もう片方は、crackerによって得られたテーブルであるとすると、そこそこ早いテーブル作成joinを行うことが可能となる。
  • 実験結果を見てみると、levelDBのようなスタンスを持っていることになるかもしれない。全体をMajorCすると大変なので、部分的にMajorC出来るように仕立てている。crackerでも、一度に全体をやると時間がかかりすぎてしまって、それをpayするためのクエリ数をかなり要するが、部分的にクラスタリングすることでクエリ数が小さい時からスループットが出やすくなる。
    • ただまあ、これはユーザがどちらを望むかだなという感じはする。累積グラフを提示するところが渋い、プレゼンがうまい。