HOSHINO Takashi Kitsuregawa Lab. 2007/12/13

Slides:



Advertisements
Similar presentations
Webプロキシサーバにおける 動的資源管理方式の提案と実装
Advertisements

07. 値予測 五島 正裕.
07. 値予測 五島 正裕.
データベース構造劣化による OLTP性能低下に関する 一考察
.NET テクノロジー を利用した SAP ソリューションの拡張 (3階層化) (評価環境構築ガイド)
SAP システムにおける SQL Server 運用ノウハウ
SharePoint Server において 構成ウィザードが失敗する場合の トラブルシューティング
片岡広太郎 Modem Watch Dog 片岡広太郎
IBM SmarterCloud Control Desk 7.5 新機能ガイド - セルフサービス・センター
COPPER/FINESSE System構築
データベース工学 データベースとは データモデル 関係データベースとSQL 物理データベース編成とインデクス
Accelerated Gradient Methods for Stochastic Optimization and Online Learning (Hu, Kwok and Pan, NIPS2009) 二宮 崇 機械学習勉強会 2010 年 6 月 17 日 1.
HPCA? 何それおいしいの?.
なぜ 今の どうする どうやって なにを どのように だれが だれと (変える) どこで だれの 考え方9W4H(Ver.0) いつ から
How to Become a Supply Chain Analyst with Free
Object Group ANalizer Graduate School of Information Science and Technology, Osaka University OGAN visualizes representative interactions between a pair.
垂直統合システム / Converged System
NTFS 2004/05/24 伊原 秀明(Port139).
データベースとストレージ の最新動向 12.MAR.2015.
RDBMSについて 2年7組  小鹿 慎太郎.
コンピュータ概論B ー ソフトウェアを中心に ー #08 データベース
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
都市情報学専攻 情報基盤研究分野  M04UC513  藤田昭人
LogStructuredFileSystem Servey
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
SIGMOD 2013 勉強会 Research 1: Data Analytics
PlanetLab における 効率的な近隣サーバ選択法
HOSHINO Takashi Kitsuregawa Lab. 2007/11/15
To appear in ACM Transactions on Graphics (Proc. SIGGRAPH 2015)
パフォーマンスチューニング on Rails
SAP & SQL Server テクニカルアーキテクチャ概要 マイクロソフト株式会社 SAP/Microsoft コンピテンスセンター
14.テーブル定義,一対多の関係,多対多の関係, 外部キー,索引(インデックス),データベース操作
朝日大学大学院 経営学研究科 奥山 徹 データベース論 朝日大学大学院 経営学研究科 奥山 徹 2006/05/29 データベース論(7回目)
サプライ・チェインの設計と管理 第11章 サプライ・チェイン・マネジメントのための 意思決定支援システム pp
「串刺し」研究アプローチの例 e-learning e-space 動画配信 システム SOI Smart Web ストリーミング技術
SQL パフォーマンス チューニング ~ カバーリングインデックス/クエリヒントの利用~
3-10. MySQLシステムの管理  2004年6月10日  大北高広                01T6010F.
コードクローンに含まれるメソッド呼び出しの 変更度合の調査
SQL パフォーマンス チューニング ~ プランガイドの利用~
Microsoft MVP for Development Tools – Visual C++
わんくま同盟・techbank.jp 夏椰 Insight Technology, Inc. 今川 美保
他のプロセスに あたえる影響が少ない 実行時ミラーリングシステム
ダウンタイムを最小限に抑えた SQL Database への移行を実現
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
Java Virtual Machine 高速化のためのbyte code 解析 An analysis of byte code to improve the performance of Java Virtual Machine 鈴木タカハル 谷研究室 Feb, 2003.
データベース工学 生研 戦略情報融合研究センタ 喜連川 優.
Present Status of Metbroker
Online Decoding of Markov Models under Latency Constraints
Microsoft MVP for Development Tools – Visual C++
Javaプログラムの変更を支援する 影響波及解析システム
DS4000 EXP700 ESM ファームウエア更新手順 (ファームウエアレベル 9326)
Microsoft MVP for Development Tools – Visual C++
スーパーコンピュータ「京」 理化学研究所 計算科学研究センター
22 物理パラメータに陽に依存する補償器を用いた低剛性二慣性系の速度制御実験 高山誠 指導教員 小林泰秀
Nightmare at Test Time: Robust Learning by Feature Deletion
インスタンスの型を考慮したJavaプログラムの実行経路の列挙手法の提案
Oligopoly Theory (1) Introduction
iSeries Site 人事・給与C/S版のハードウェア・ソフトウェア要件
ISO23950による分散検索の課題と その解決案に関する検討
分散型VLBIソフトウェア相関処理システムの開発
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
Mondriaan Memory Protection の調査
Db2 Warehouse on Cloud Db2 on Cloud フルマネージドサービス提案時の注意点
SQL パフォーマンス チューニング ~ パフォーマンス改善 最初の一歩 ~
蓄積されたオブジェクトの動作履歴を用いた 実行履歴削減手法の提案
CO-Client Opeartion 1.1 利用履歴データベースの設計 (スキーマ バージョン 対応)
発表者: 稲葉 一浩 複雑ネットワーク・地図グラフ セミナー 2017/1/19
Microsoft Office Project Server 2007
FSE/ASE勉強会 A10:Software Maintenance II
Presentation transcript:

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

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

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

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

On the Analysis of On-Line Database Reorganization [20071213-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

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

A method for on-line reorganization of a database [20071213-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

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

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

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

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

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

[20071213-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

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

Towards a Formulation and Definition of Data Reorganization [20071213-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

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

[20071213-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

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

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