HOSHINO Takashi Kitsuregawa Lab. 2007/12/13

Presentation on theme: "HOSHINO Takashi Kitsuregawa Lab. 2007/12/13"— Presentation transcript:

1 HOSHINO Takashi Kitsuregawa Lab. 2007/12/13
再編成論文サーベイ3 HOSHINO Takashi Kitsuregawa Lab. 2007/12/13

2 [ hoshino] 再編成論文サーベイ3 内容 再編成に関連する論文overview

3 [ hoshino] 再編成論文サーベイ3 SQLCM: A Continuour Monitoring Framework for Relational Database Engines Surajit Chaudhuri, Arnd Christian Konig, Vivek Narasayya (Microsoft Research) ICDE 2004

4 概要 Databaseモニタリング機構の提案 MSSQLで評価 監視する対象 特徴 Low-overheadと主張
[ hoshino] 再編成論文サーベイ3 概要 Databaseモニタリング機構の提案 MSSQLで評価 Low-overheadと主張 Internal DB Server　でのモニタリング In-memory aggregation 監視する対象 SQL Execution time Locks & delay Resource consumption など 特徴 データ構造やアクセスパタンを見るとは言ってない この機構を用いてデータ構造を監視することも可能

5 On the Analysis of On-Line Database Reorganization
[ hoshino] 再編成論文サーベイ3 On the Analysis of On-Line Database Reorganization Vlad I.S. Wietrzyk, Mehmet A. Orguu, and Varadharajan (University of Western Sydney) DASFAA 2000

6 概要 Versant databaseのオンライン再編成手法を提案 コメント グラフ構造G=(V,E)用 OODB
[ hoshino] 再編成論文サーベイ3 概要 Versant databaseのオンライン再編成手法を提案 グラフ構造G=(V,E)用 OODB Access frequency と reachability indexをアクセスパタンを用いて最適化する Reachability index: グラフ内の走査ガイドに相当 オブジェクト関係をコスト化し、それを重みとするグラフ内でMSTを作成、常時メンテナンスする コメント データ構造(graph)とaccess frequencyから理想的なデータ配置を常時計算 再編成というよりも、データ更新メソッドにに組み込んでしまった感じ MSTメンテナンスアルゴリズムはIO trace analyzerに使えそう

7 A method for on-line reorganization of a database
[ hoshino] 再編成論文サーベイ3 A method for on-line reorganization of a database G. H. Sockut, T. aA. Beavin C.-C. Chang (IBM) IBM SYSTEMS JOURNAL 36(3) 1997

8 概要 オンラインデータベース再編成メソッドの提案 コメント
[ hoshino] 再編成論文サーベイ3 概要 オンラインデータベース再編成メソッドの提案 Mapping tableとfuzzy reorganization of the logの組み合わせが新しいと主張 ここでは、構造劣化のことを「Structural Degradation」と呼称 When to reorganize あまりデータ更新が頻繁でないとき レスポンスを要求されるアプリケーションが走っていないとき 長時間実行トランザクションが走っていないとき Where to reorganize Indexのみを再編成するという話があったくらい コメント コスト対効果の話をすると、データベースを止めて再編成するのに比べてやはりそれなりに非効率と思われる  その評価がほしい

9 Hash Table Reorganization
[ hoshino] 再編成論文サーベイ3 Hash Table Reorganization Thomas G. Szymanski (AT&T Bell Lab.) Journal of algorithms 6 (1985)

10 概要 Hashデータ構造の再編成手法の提案 コメント コストはページアクセス数 レコードを入れ替える手段で再編成
[ hoshino] 再編成論文サーベイ3 概要 Hashデータ構造の再編成手法の提案 コストはページアクセス数 レコードを入れ替える手段で再編成 Linear-proving hash tableの場合、O(n)のアルゴリズムを提案 Double-hashingについては議論されていない コメント When to reorganizeの話はなかった

11 Edward Omiecinski, Liehuey Lee, and Peter Scheuermann TKDE 6(2), 1994
[ hoshino] 再編成論文サーベイ3 Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering Edward Omiecinski, Liehuey Lee, and Peter Scheuermann TKDE 6(2), 1994

12 概要 以前提案したOnline reorganizatoin (clustering)手法をいくつかのパラメータを振ってシミュレーション評価
[ hoshino] 再編成論文サーベイ3 概要 以前提案したOnline reorganizatoin (clustering)手法をいくつかのパラメータを振ってシミュレーション評価 バッファサイズが増えると、reorg中に性能が落ちやすいがreorg速度は速い Multiprogramming levelか、degree of clustered transactionsが増えると、バッファサイズが増えたときと逆の効果が得られた

13 [ hoshino] 再編成論文サーベイ3 Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization, and Updating Guy M. Lohman (Jet Propulsion Laboratry), and John A. Muckstadt (Comell University) TODS 2(3), 1977

14 概要 データベースアップデートサイズを求める問題に全て帰着して、Batch operationsの間隔を議論 再編成に関する議論 コメント
[ hoshino] 再編成論文サーベイ3 概要 データベースアップデートサイズを求める問題に全て帰着して、Batch operationsの間隔を議論 Analytical method 最適な間隔は、intervalよりもむしろアップデート量で見るべき 再編成に関する議論 Delete flagとoverflow areaに関してのみ Deterioration cost と reorganization costのバランス コメント これまでのreorganization scheduleに関する論文とそこまで違うものでもない。なぜなら、analytical predictionだから。 もちろん、未来のことを考え始めると、analytical predictionしかやりようがない。(simulationなどやってられない)

15 Towards a Formulation and Definition of Data Reorganization
[ hoshino] 再編成論文サーベイ3 Towards a Formulation and Definition of Data Reorganization James P. Fry, David W. Jeris (University of Michigan) ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, 1974

16 概要 スキーマの再構成に関する議論 コメント
[ hoshino] 再編成論文サーベイ3 概要 スキーマの再構成に関する議論 コメント スキーマ動的変更の話をするならともかく、スキーマ固定でやってる前提なので、この論文はあまり参考にならない

17 [ hoshino] 再編成論文サーベイ3 Improving I/O Response Times Via Prefetching and Storage System Reorganization 詳細調査版 C. L. Chee, H. Lu, and H. Tang (National University of Singapore), C. V. Ramamoorthy (University of California, Berkeley) COMPSAC 1997

18 概要 再編成とプリフェッチでストレージ性能を上げる方式を提案 我々との比較 Statistics collector
[ hoshino] 再編成論文サーベイ3 概要 再編成とプリフェッチでストレージ性能を上げる方式を提案 Statistics collector 次に参照されやすいブロック 次の次に参照されやすいブロック リード回数 ライト回数 我々との比較 統計情報収集と再編成は定期的に行われる スケジュールについての議論はない

19 アクセスパタンの認識 シーケンス抽出 抽出するシーケンスを絞ったため、認識アルゴリズムは高速 オーバーヘッド コメント
[ hoshino] 再編成論文サーベイ3 アクセスパタンの認識 シーケンス抽出 Sequential: ファイルに対するシーケンシャルアクセス Interval: ファイルに対する歯抜けアクセス Reverse: sequentialの逆 上記は、intervalアクセスで一般化される 抽出するシーケンスを絞ったため、認識アルゴリズムは高速 オーバーヘッド Statistics collection overhead: 8% コメント データ構造を元にして構造劣化認識していることは変わらない プリフェッチとの組み合わせてトータル性能UPはよくある話のようだ IO Trace Monitorにとって参考にすべき論文