再編成論文サーベイ3

[20071213-hoshino] 再編成論文サーベイ3
再編成論文サーベイ3
HOSHINO Takashi
Kitsuregawa Lab.
2007/12/13
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
1
[20071213-hoshino] 再編成論文サーベイ3
内容
 再編成に関連する論文overview
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
2
[20071213-hoshino] 再編成論文サーベイ3
SQLCM: A Continuour
Monitoring Framework for
Relational Database Engines
Surajit Chaudhuri, Arnd Christian Konig, Vivek
Narasayya (Microsoft Research)
ICDE 2004
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
3
[20071213-hoshino] 再編成論文サーベイ3
概要
 Databaseモニタリング機構の提案 MSSQLで評価
– Low-overheadと主張
– Internal DB Server でのモニタリング
– In-memory aggregation
 監視する対象
– SQL Execution time
– Locks & delay
– Resource consumption など
 特徴
– データ構造やアクセスパタンを見るとは言ってない
– この機構を用いてデータ構造を監視することも可能
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
4
[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
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
5
[20071213-hoshino] 再編成論文サーベイ3
概要
 Versant databaseのオンライン再編成手法を提案
– グラフ構造G=(V,E)用 OODB
– Access frequency と reachability indexをアクセスパタンを用いて最適
化する
 Reachability index: グラフ内の走査ガイドに相当
– オブジェクト関係をコスト化し、それを重みとするグラフ内でMSTを作成、常
時メンテナンスする
 コメント
– データ構造(graph)とaccess frequencyから理想的なデータ配置を常時
計算
– 再編成というよりも、データ更新メソッドにに組み込んでしまった感じ
– MSTメンテナンスアルゴリズムはIO trace analyzerに使えそう
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
6
[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
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
7
[20071213-hoshino] 再編成論文サーベイ3
概要
 オンラインデータベース再編成メソッドの提案
– Mapping tableとfuzzy reorganization of the logの組み合わせが新
しいと主張
– ここでは、構造劣化のことを「Structural Degradation」と呼称
– When to reorganize
 あまりデータ更新が頻繁でないとき
 レスポンスを要求されるアプリケーションが走っていないとき
 長時間実行トランザクションが走っていないとき
– Where to reorganize
 Indexのみを再編成するという話があったくらい
 コメント
– コスト対効果の話をすると、データベースを止めて再編成するのに比べてや
はりそれなりに非効率と思われる  その評価がほしい
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
8
[20071213-hoshino] 再編成論文サーベイ3
Hash Table Reorganization
Thomas G. Szymanski (AT&T Bell Lab.)
Journal of algorithms 6 (1985)
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
9
[20071213-hoshino] 再編成論文サーベイ3
概要
 Hashデータ構造の再編成手法の提案
–
–
–
–
コストはページアクセス数
レコードを入れ替える手段で再編成
Linear-proving hash tableの場合、O(n)のアルゴリズムを提案
Double-hashingについては議論されていない
 コメント
– When to reorganizeの話はなかった
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
10
[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
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
11
[20071213-hoshino] 再編成論文サーベイ3
概要
 以前提案したOnline reorganizatoin (clustering)手法
をいくつかのパラメータを振ってシミュレーション評価
– バッファサイズが増えると、reorg中に性能が落ちやすいがreorg速
度は速い
– Multiprogramming levelか、degree of clustered
transactionsが増えると、バッファサイズが増えたときと逆の効果が
得られた
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
12
[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
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
13
[20071213-hoshino] 再編成論文サーベイ3
概要
 データベースアップデートサイズを求める問題に全て帰着し
て、Batch operationsの間隔を議論
– Analytical method
– 最適な間隔は、intervalよりもむしろアップデート量で見るべき
 再編成に関する議論
– Delete flagとoverflow areaに関してのみ
– Deterioration cost と reorganization costのバランス
 コメント
– これまでのreorganization scheduleに関する論文とそこまで違う
ものでもない。なぜなら、analytical predictionだから。
– もちろん、未来のことを考え始めると、analytical predictionしかや
りようがない。(simulationなどやってられない)
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
14
[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
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
15
[20071213-hoshino] 再編成論文サーベイ3
概要
 スキーマの再構成に関する議論
 コメント
– スキーマ動的変更の話をするならともかく、スキーマ固定でやってる
前提なので、この論文はあまり参考にならない
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
16
[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
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
17
[20071213-hoshino] 再編成論文サーベイ3
概要
 再編成とプリフェッチでストレージ性能を上げる方式を提案
– Statistics collector
 次に参照されやすいブロック
 次の次に参照されやすいブロック
 リード回数
 ライト回数
 我々との比較
– 統計情報収集と再編成は定期的に行われる
スケジュールについての議論はない
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
18
[20071213-hoshino] 再編成論文サーベイ3
アクセスパタンの認識
 シーケンス抽出
–
–
–
–
Sequential: ファイルに対するシーケンシャルアクセス
Interval: ファイルに対する歯抜けアクセス
Reverse: sequentialの逆
上記は、intervalアクセスで一般化される
 抽出するシーケンスを絞ったため、認識アルゴリズムは高速
 オーバーヘッド
– Statistics collection overhead: 8%
 コメント
– データ構造を元にして構造劣化認識していることは変わらない
– プリフェッチとの組み合わせてトータル性能UPはよくある話のようだ
– IO Trace Monitorにとって参考にすべき論文
Kitsuregawa Laboratory Confidential. © 2007 Kitsuregawa Laboratory, IIS, University of Tokyo.
19

Download Report