2012-07-13

Materialization Strategies in a Column-Oriented DBMS

技術的なこと

カラムストアにおいて、いつ最終的なRowを実体化するかについての
トレードオフをまとめた論文。

late materialization という概念をとりいれている。
- late materialization のメリットは、不必要なjoinを減らせることであるが、デメリットは、2回同じカラムを読み込む必要が出てくること。
- 但し、pipelineであればキャッシュに乗っているデータを2回触ることになるので、I/O自体が問題になることはないだろうが、Memory Wallが発生するのでearly materialization との間にトレードオフがある。
重要な指標は、Selectivityであり、Selectivityが低ければLate Materialization有利。でなければ、Early Materialization有利。
重要な指標は、Selectivityであり、Selectivityが低ければパイプライン有利。でなければ、パラレル有利。
- 但し、カラムストア向けの圧縮を有効にすると、Selectivityに関係なくLate有利。まあ、そりゃそうだ。

2012-07-13

アーキテクト

技術的なこと

これまで、私はミドルウェアのアーキテクトになりたいと思いながらがむしゃらにやってきました。

その思いは、さらに強くなっていて、ありがたい事に今のところそういったキャリアを積めていると思う。

日本発のミドルウェアで世界を席巻したい。

2012-07-13

C-Store

技術的なこと

http://db.csail.mit.edu/projects/cstore/vldb.pdf:M. Stonebraker, "C-Store: A Column-oriented DBMS, " VLDB(2005).を読んでみてのメモ。

これまでは、DBMSでOLAP（キューブタイプ）をになっていたが、比較的複雑なアドホッククエリへのレスポンスタイムを小さくするため、アーキテクチャの再設計を行う。
テーブルを複数のカラム集合に分けて、ストレージに格納。各カラム集合は、sort keyによってソートされる。これにより、さまざまなOrderBy/GroupByに対応しやすくしているのかなと思う。面白いところは、各カラム集合には、同じカラムを重複して含んでも良いところ。複数サーバで管理されりているC-Storeは、K-safeを実現することができるが、そのためのレプリカにもなっている。
カラム分割だけでなく、水平にも分割して、分割単位をsegmentと呼ぶ。カラム集合に対応するsegmentを用いて、元のテーブルを構成できるようにするために、別のカラム集合に含まれるsegment間には、join indexを作成する。join indexは、SegmentIDとStorageKeyからなる。分割された各レコードは、join indexによって１対１で結び付けられる。
Read-Optimized Store (RS)とWrite-Optimized Store (WS)から構成される。WSである程度書き込みがたまると、RS上のsegmentとマージされて、join indexも作成される。クエリを発行したばあい、RSとWSのどちらからも検索を行う。RS上では、データタイプによって４つの圧縮方式があり、これらの圧縮方式では、圧縮したまま演算処理を行うことが出来るように工夫されている。最終的に解凍するのは、ユーザにデータを渡すときのみ。重要な方式としてランレングスとビットマップがあり、ランレングスはソート済み、ビットマップはソートはしていないが出てくる値がある程度グルーピング出来る場合に有効。
WSの基本的な構造は、RSと変わらない。オプティマイザを二つ作りたくないから。WSに格納されるデータ量は小さいので圧縮は考えず、B-treeとして構築し、論理的なオーダーを担保する。
複数サーバ上でsegmentは配置される。その配置戦略は、
- join indexは、join時のsender側にあったほうが良い。というかそういうjoin indexの作り方をしていると思う。
- WS/RS上の同じキーレンジを持つsegmentは、同じところに配置したほうがよい。
更新データは、カラムごとに各WSに書き込まれるけど、同じレコードであることはStorage Keyが同じことで保証する。Storage Keyは、必ず一意になるように更新要求を受け付けたサーバで決定。
既存のRDBMSでの並行制御をまともにやると、沢山のアドホッククエリに耐えられないのでsnapshot isolationを採用。
- WOS->ROSへ移行するところにおいて、snapshot isolationが効いてくる。Hiveやdremelではこれが出来ていない。
WOSやROSに対するクエリオプティマイザは、Selinger-styleで実装。これは、いわゆるコストベースのクエリオプティマイザで、RDBMSでは基本。
リレーショナルオペレータは、10種類程度規定しており、ソースコードを読むところvolcano(有名なデータベースマシン)で培われたパイプライン処理を用いている。
他のカラムストアに比べて面白いのは、Bigtableで言うところのカラムファミリグループみたいな概念をDurabilityやOrderByへの対応などに対してうまく使っていること。シンプルなカラムストアでは、カラムファミリグループとカラムファミリは一対一にする。が、C-storeでは、分散ファイルシステムを利用していないのでそのへんの柵がなく、ひとつのカラムファミリを複数のカラムファミリグループに重複して登録することで、物理マシンのクラッシュ時にデータの喪失を防ぐとともに、複数のガラムファミリグループでソートしているカラムファミリを切り替えている。そうすると、一番重たいソートクエリ対する部分的な実体化ビューを準備済みになる。

2012-07-13

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するためのクエリ数をかなり要するが、部分的にクラスタリングすることでクエリ数が小さい時からスループットが出やすくなる。
- ただまあ、これはユーザがどちらを望むかだなという感じはする。累積グラフを提示するところが渋い、プレゼンがうまい。