最新DBアーキテクチャについて（と思われる会話

nyaxt @nyaxt

Column Store初出 / “A Decomposition Storage Model” http://t.co/XoSE5uRV

nyaxt @nyaxt

MonetDBとsupersonicのコード眺めてた。どうやって勝てばいいのこれ

nyaxt @nyaxt

Database Cracking理解した気がする。Google TeckTalk見てからだと論文理解はやいな： http://t.co/pTJkTgsY

拡大

nyaxt @nyaxt

pvldbの論文読んでるとMySQLが常に評価でぼこぼこにされてて面白い。よくあるのが、MySQL、商用DBMS、著者のDBMS、著者DBMS+新規手法でそれぞれ2x-10xずつちがう

くまぎ @kumagi

@nyaxt トランザクショナルメモリとかCacheObliviousとかウェーブレットなんとかとかあとまだ未投入で面白そうな技術は…

nyaxt @nyaxt

@kumagi OLTPじゃないんで、TMは…　ウェーブレットなんとかはつかえるかも？

くまぎ @kumagi

@nyaxt OLAPなDBもどこかでRW-Lockぐらい取ってると思います、あまり効きそうな気はしないですが…。ウェーブレットなんとかはデータが大きくならないと効いてこないのが辛い感じです。TokuDBのようなフラクタル構造は分割統治からの並列化が自然で脅威と思ってます。

nyaxt @nyaxt

@kumagi とりあえず解析クエリ処理器だけつくろっかなって。OLAP/OLTPハイブリッドなDBだと、LSMTreeみたく、直近の変更だけ保持するOLTP部と、変更なし想定のでかいOLAP部をつくっといて、並列でクエリなげるのが定石みたいです

nyaxt @nyaxt

作りかけなのここにあるけど、週末だけじゃなかなかすすまんな：https://t.co/kmeGIi7j

くまぎ @kumagi

@nyaxt そうですね、書き込みはrow方向に、読み出しはcolumn方向に並べておいて、書き込みが分析系クエリに反映されるまでの時間の短さをトレードオフに出すのが妥当そうに見えます。大抵のケースで秒オーダーで許容できそうですし、そこのスケジューラがbLSM的に練られるかなと。

nyaxt @nyaxt

@kumagi いぇす。書き込みするDB(WOSというらしい)に並行してクエリだしてもいいしね。そしてウェーブレットなんとかはWavelet Treeをbitmap indexに適応する話かと思ってたけど、フラクタル系のCOななんとか木系ですか

くまぎ @kumagi

@nyaxt ウェーブレットなんとか、お察しの通りウェーブレット木|行列を指して使ってました。COな物は見た気がしないです。COでいうと今vEBレイアウトについて調べるのがマイブームです。vEB、ファンネルソートなどのCOは分析クエリの並列化に更に効きそうだと最近感じてます。

nyaxt @nyaxt

@kumagi vEBレイアウト、解説論文とにらめっこしてもあんまり理解できてない気がするので教えてください！Funnel Sortは不勉強でしらなかった…！

くまぎ @kumagi

@nyaxt ちなみにbLSMの論文「フラクタル構造を採用すると漸近的に探索コストを下げられるが書き出しコストがO(n)になるのでBloom filterをoptした」と読める(3.1)辺りがLSMとフラクタルの先端の攻めぎあいだなぁとか感じましたが誤読かも知れなくて…orz

nyaxt @nyaxt

COの道は修羅の道な気がする。とりあえず、Column-OrientedなOLAPだとひたすらシーケンシャルになめるだけなので、そういう意味ではCOか？

くまぎ @kumagi

@nyaxt わたくし、vEB木を知ればなんとかなるかもとアルゴリズムイントロダクション２巻を入手してみたら、JavaとJavaScriptぐらい違うという事を知って絶望しています。理解できたら教えます！また今度情報交換しましょう！

nyaxt @nyaxt

@kumagi 情報交換是非に！bLSM論文はアクセス権がなくて積んでたままだわ…なんとか入手して今度読んでみます。

くまぎ @kumagi

@nyaxt 僕の理解だと「分割統治の恩恵を最大限活かそうとするアルゴリズム全般」の事をCOと呼んでて、MITだかの講義ビデオ見る限りは例えば2分探索はlog n探索オーダだけど分割統治ではない、としてdisられてました。0xdataoのH2Oも分割統治を礼賛してて興味深い。

くまぎ @kumagi

@nyaxt bLSM、write/read amplificationという係数を導入し、LSM木の木の数を固定してシークの上限を抑え、複数のbloom filterでスキャンを抑えつつgear springスケジューラを導入し…と色々詰め込まれてます。理解しんどい…。