Session 18: Systems, Performance II

Presentation on theme: "Session 18: Systems, Performance II"— Presentation transcript:

1 Session 18: Systems, Performance II
【SIGMOD 2013勉強会】 Session 18: Systems, Performance II 担当： 石川佳治（名大） Some figures are copied from SIGMOD 2013 proceedings.

2 Simulation of Database-Valued Markov Chains Using SimSQL
Z. Cai, Z. Vagena, L. Perez, S. Arumugam, P.J. Haas, C. Jermaine (Rice U/LogicBox/IBM Almaden) シミュレーション分析のためのデータベース 統計モデルと実データを組み合わせたシミュレーション SQL風の言語を提供 What-If分析に活用 ユーザは宣言的にシミュレーション内容を記述可能 負担の軽減，対話的試行に適する 先行研究（著者らによる）：Monte Carlo DB（MCDB） 統計モデルに従いランダムにデータベースを多数生成し，統計処理 により問合せに応える 例：5年後の30代の従業員の平均給与は？ Session 18: Systems, Performance II 担当：石川研（名大）

3 Session 18: Systems, Performance II 担当：石川研（名大）
SimSQLの特徴 確率的テーブルを他の確率的テーブルから導出可能 階層的な確率モデル（例：LDA）を表現可能 確率的リテーブルはバージョン化して再帰的に定義可能 MCMC（マルコフ連鎖モンテカルロ法）によるシミュレーションを自然に 表現 実装はHadoop上で 例：LDAによるトピック分析 ・Θj は確率ベクトル ・wj,k,d は文書jにトピックk による語 d の出現数 ・Ψi はトピック i の確率 Session 18: Systems, Performance II 担当：石川研（名大）

4 Session 18: Systems, Performance II 担当：石川研（名大）
確率的テーブルの定義 パラメータの初期化・更新をテーブルとして表現 各パラメータについて，二つのテーブル定義 パラメータ w の 初期化結果 CREATE TABLE w[0] (docID, wordID, topicID, count) AS FOR EACH dw IN wordInDoc WITH TC As Multinomial ( (SELECT tm.topicID, tm.probability FROM theta[0] AS tm WHERE tm.docID = dw.docID), (SELECT dw.count)) SELECT dw.docID, dw.wordID, tc.outID, tc.count FROM TC AS tc; パラメータ w の 初期化の例： ・初期データはテーブル w[0] に入る ・以降の更新結果は w[1], w[2], … に入る パラメータ Θ の 初期値を参照 パラメータ w の 更新の例： ・問合せ中では以前 　のバージョンの 　テーブルを参照可 CREATE TABLE w[i] (docID, wordID, topicID, count) AS … Session 18: Systems, Performance II 担当：石川研（名大）

5 Session 18: Systems, Performance II 担当：石川研（名大）
問合せ処理 それぞれの確率テーブル定義に対し，テーブル実体化のた めの問合せプランを構築 問合せ処理では，実データとそれ以前に生成されている確率テーブル を使用可 Session 18: Systems, Performance II 担当：石川研（名大）

6 Toward Practical Query Pricing with QueryMarket
P. Koutris, P. Upadhyaya, M. Balazinska, B. Howe, D. Suciu (U. Washington) QueryMarket：データを売り買いするためのシステム 売り手：選択問合せの形式で，販売データを価格も合わせて 提示 買い手：必要なデータを一般的な問合せとして記述 システム：買い手が与えた要求（問合せ）を満足する最適な （安価な）販売データの組合せを求める 本論文の目的 PODS 2012で示した枠組みをさらに発展させる 効率的な処理 現実的に求められる機能の支援 Session 18: Systems, Performance II 担当：石川研（名大）

7 Session 18: Systems, Performance II 担当：石川研（名大）
例：訳語データの販売 買い手は必要なデータを求める問合せの集合（query bundle）を与える：Q = {Q1, …, Qk}．以下が具体例 Q1(x) = Ten, de(‘thanks’, x) // ドイツ語でthanksに相当する語 Q2(x, y) = Tde, en(x, y), Tde, fr(x, y) // 英語・仏語訳が同じ Q3() = UF(‘rock’, ‘music’, f1, y), UF(‘pop’, ‘music’, f2, z), f1 > f2 // ユニグラム頻度データで，rockの方が頻出か Q4(x, y) = UF(x, ‘math’, z, r), Ten, de(x, y), r  // 頻度がトップ100以内の数学関係の語のドイツ語訳 売り手はビューと価格のペアの集合を提供：S = {(V1, p1), …, (Vl, pl)} 例：ランク10位までの語のユニグラムを，各語1ドルで販売 (Vi, $1), where Vi(w, g, f, r) = UF(w, g, f, r), r  10 Session 18: Systems, Performance II 担当：石川研（名大）

8 Session 18: Systems, Performance II 担当：石川研（名大）
技術的な特徴 裁定不可（arbitrage-free）：問合せ結果よりも安い価格 の組合せはない（利ざやを稼げない）という基本概念 最適な組合せの導出には整数計画法（ILP）を使用 あるビューのある属性を取得するかをバイナリ変数で表現 購入したい属性が1回以上取得されることを制約として表現 NP完全問題だが，ILPソルバの利用で現実的コストで処理可 他の拡張（例：キー制約を考慮）もILPの枠組みで表現 処理の効率化を工夫：独立した部分問題への分割など 動的な環境への対応 データ購入が一括ではない場合への対応 販売データの更新への対応 複数の売り手での利益の分配方式 Session 18: Systems, Performance II 担当：石川研（名大）

9 Generalized Scale Independence Through Incremental Precomputation
M. Armbrust, E. Liang, T. Kraska, A. Fox, M.J. Franklin, D.A. Patterson (Google/UCB/Brown U.) スケール独立性（Scale Independence） データのサイズが増えても，問合せ実行コスト（更新コスト，格 納コストも含め）が定数で抑えられる 従来の問合せ処理（与えられたDBのサイズに対し最小のコス トでの実行を目指す）とは異なる観点 VLDB 2012で発表したPIQLの発展 VLDB 2012版では，スケール独立性を有する問合せ実行のための 索引の活用について 今回はインクリメンタルな実体化ビュー（IMV）の活用について 更新，格納コストについても考慮 Session 18: Systems, Performance II 担当：石川研（名大）

10 Session 18: Systems, Performance II 担当：石川研（名大）
例 指定された二つのタグ tag1, tag2 を持つ文書をタイムス タンプが新しい順に5件提示 tag1, tag2はパラメータ：問合せ実行時に値が確定 tagsリレーションのtag属性上の二次索引は，効率化には寄与 するがスケール独立ではない：何件マッチするか不明 解決策：この問合せに対する実体化ビューを構築 問合せ処理：実体化ビューの限られた領域をスキャン DB更新時の実体化ビューの更新も定数 SELECT t1.docID FROM tags t1, tags t2, documents d WHERE t1.docID = t2.docID AND t1.docID = d.docID AND t1.tag = <tag1> AND t2.tag = <tag2> ORDER BY d.timestamp LIMIT 5 Session 18: Systems, Performance II 担当：石川研（名大）

11 Session 18: Systems, Performance II 担当：石川研（名大）
スケール独立性のレベル 不変性1（Inv1）：問合せ実行が定数の操作で可能 例：主キーによる検索（高々1件マッチ） 注：二次索引による検索は定数では抑えられない 不変性2（Inv2）：タプル更新時に，実体化ビューが定数 の操作で更新可能 不変性3（Inv3)：格納されるタプル数が定数で抑えられる SI-0 SI-1 SI-2 SI-3 基本実行（Inv1） 独立 依存 索引有り実行（Inv1） － IMV更新（Inv2） IMV格納（Inv3） IMV並列更新（Inv2の緩和） 与えられた問合せの 処理を考えたとき， いずれかの不変性に 反しているなら スケール独立でない Session 18: Systems, Performance II 担当：石川研（名大）

12 Session 18: Systems, Performance II 担当：石川研（名大）
技術の詳細 問合せコンパイルでは，通常の最適化に以下が伴う 実体化ビュー構築の可否 格納コスト，更新コストの分析 ホットスポット除去のための並列化処理 実体化ビューの選択 条件：与えられた問合せを実行する際，実体化ビューの連続 した定数サイズのタプルを読むだけで済むか否か 集約を含むビュー：COUNT, AVGなどは問題ないが，MEDIAN は不可（定数コストにならない） 実体化ビューの格納コスト：従属性を考慮して分析 ホットスポット分析：DDLで注釈を与え活用 Session 18: Systems, Performance II 担当：石川研（名大）