Hatena::ブログ(Diary)

ablog このページをアンテナに追加 RSSフィード Twitter

2017-04-20

列指向データベースのページのデータ構造

行指向データベースは行単位でページ(Oracle Database でいうデータブロック)にデータを格納しているのに対して、列指向データベースは列ごとにページに格納している。クエリ実行時に結果セットを返す際に列別にバラバラのページに格納されているデータをどうやってタプル(レコード)に復元している*1のかと思ったがやはり行IDのようなものを持っているようだ。

行ID は C-Store では pid、MonetDB では BAT(Binary Association Tables) の oid と呼ばれている。

The Design and Implementation of Modern Column-Oriented Database Systems

f:id:yohei-a:20170420230742p:image:w640

  • NSM(N-ary Storage Model): 行方向でブロック(ページ)にデータを格納する方式
  • DSM(Decomposition Storage Model): 列方向でブロック(ページ)にデータを格納する方式

f:id:yohei-a:20170420233150p:image:w360

C-Store の pid や MonetDB の oid のような ID 以外に Join Index という手法もある。

具体的な実装は C-Store のソースコードで調べることができる。


さらに詳しくは諸橋さんの以下のエントリで紹介されている

VLDB 2009 Tutorial on Column-Stores *1 が表示されたとき、笑ってしまい「わたしの教科書です、教科書」と言ってしまった appengine ja night #21 *2。

Google BigQueryなどの仕組みを知りたいときの列指向データベースの説明に - wmo6hash::blog

この大作スライド参照。


https://www.cs.duke.edu/courses/fall01/cps216/lectures/10-physical.pdf もシンプルで良い資料。

NSM = N-ary Storage Model

DSM = Decomposition Storage Model


補足

C-Store はあのマイケル・ストーンブレーカー教授が産んだ列指向データベースで、商業的にも成功している Vertica(HP社) のルーツです。

ストーンブレーカー教授と一緒にこの論文を書いている Daniel Abadi さんは上の VLDB 2009 Tutorial on Column-Stores を書いているうちの一人でもあり、分かりやすい資料を書かれているので要チェックです。


MonetDB については以下参照


参考

*1:別々のページに格納されているカラムのデータを結合してレコード(タプル)に何をキーに復元するのか?

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/yohei-a/20170420/1492685305
おとなり日記