はじめに

記憶装置上のデータは，更新によってその構造が劣化する恐れがあり，当該現象を構造劣化（Structural Deterioration）と呼ぶ．これによりデータアクセスの性能は著しく低下する．例えば，B+木に於いては，多くの記憶装置の物理的特性から，論理的に隣接したページが記憶装置上においても物理的に隣接していることが望ましい．しかし，B+木の特定のページに偏って多数のレコード挿入を実施すると，当該ページは満杯となり分割され，物理的に離れた位置に新たなページを獲得し，レコードが格納されることになる．このようなページ分割を繰り返すと，徐々にページの物理位置と論理的な鍵値との相関は低下することとなり，B+木の走査は記憶装置上ではランダムなアクセスとなるため，検索性能が大幅に低下する．とりわけ，二次記憶装置のアクセス性能はディスクドライブの機械的特性に依存するため，構造劣化による性能低下は，膨大なデータを二次記憶装置上に格納するデータベース管理システムにとって，最も深刻な問題の一つである．

当該問題の解決を目指す研究として，従来より，記憶装置上のデータを再配置することにより，劣化した構造を回復し性能を改善するデータベース再編成をデータベース管理システムにおけるデータ管理の一機能として実現する試みが行われてきた．データベース再編成は，今日の商用データベース管理システムに不可欠な機能となっている．一方，データベース管理システムの中核的な機能である問い合わせ・更新処理の高度化によって構造劣化を回避する試みも行われてきた．データ構造に更新操作のための豊富な参考メタ情報を与えることにより，データの更新操作が局所最適解に陥るのをなるべく回避する方式や，問い合わせ実行計画の立案に構造劣化を考慮する方式などが検討され，商用データベース管理システムに採用されるに至っている．

本論文では，ストレージ装置の有する潜在的な能力を活用することにより，データベース管理システムにおける構造劣化管理を軽減することを目的とする．即ち，データベース再編成機能を有する高機能ディスクストレージの構成法，並びに非順序型IO処理による新しいデータベース構造劣化軽減機構の提案を行う．

データベース再編成機能を有する高機能ディスクストレージは，近年急速に高性能化しているディスクストレージのハードウェア資源の能力を活用することにより，構造劣化管理をサーバ層からストレージ層へと移譲する試みである．データベース管理システムから構造劣化管理を取り除くことが出来ることから，データベース管理システムにおける記憶管理を大幅に単純化し，最終的には情報システム全体の設計の容易化に資すると考えられる．

一方，非順序型IO処理によるデータベース構造劣化の軽減機構は，データベース管理システムにおける問い合わせ処理のデータアクセス方式に関して，IO処理の順序性制約を緩和することにより，ストレージ層の有するIOスケジューリング能力を活用し，構造劣化による性能低下を回避することを狙う．今日の情報システム構成の中で，ストレージが性能に寄与する割合は高まっており，データベース管理システムがストレージ装置の潜在的な能力を最大限に活用することが可能となり，その効果は大きい．

データベース再編成機能を有する高機能ディスクストレージに関する研究

デバイス技術の進歩に伴いストレージ装置は近年急速に高性能化しており，従来は全てサーバ上で行っていたIOインテンシブなデータ管理の一部を，サーバ上の計算機資源を用いるのではなく，大規模ストレージ装置の有する計算機資源の一部を用いて実行することが可能となりつつある．

本論文では，自己再編成ストレージ（SRS: Self-Reorganizing Storage）システムと名付けた，オンラインデータベース再編成機能を有する高機能ディスクストレージを提案する．SRSはデータベース再編成をストレージ装置内部でオンラインに実施することにより，データベース内のデータ構造の効率性を保つことが可能となり，情報システムの設計は大きく容易化出来るものと期待される．SRSにおけるオンライン再編成方式自体は，既に商用のデータベース管理システム等で採用されている分離再編成なる方式に基づいているが，データと再編成機能がストレージ内に共存する方式に関する本論文の提案は他に類例を見ない．ストレージ装置が有する豊富なIO帯域と高いIO処理能力を活用し，並列パイプライン化データ処理，物理アドレスレベルIOスケジューリング並びに独自の高速ログ適用処理なる技術を導入することにより，再編成を高速に実施することが可能となる．

また，本論文では，提案方式の試作機をPCサーバ並びにファイバチャネルSANを用いた実験システムを用いて実装し，代表的なデータベースベンチマークアプリケーションであるTPC-C並びにTPC-Hを用いて性能評価を行う．この結果，従来的なサーバソフトウェアによる再編成に比べて，SRSによる再編成は極めて高速であることを確認する．

さらに，本論文では，データベース再編成の更なる高速化を目指し，複数の再編成モジュールに処理を分散する並列データベース再編成処理方式，並びにデータベースの更新の局所性に着目した部分再編成機構を提案する．前者に関しては，試作機を用いた実験により，極めて高いスケーラビリティを達成できることを明らかにする．後者に関しては， 2つの代表的なケーススタディを詳細に解析し，実現方式を示すとともに，試作機において部分再編成機能を実装し，その有効性を示す．

非順序型ＩＯ処理によるデータベース構造劣化の軽減機構に関する研究

ストレージ装置の有するIO制御機構は高度なIOスケジューリング機能を具備するに至っており，ディスクシーク等の処理オーバヘッドを最小限に抑えるべくIO要求の処理順序を入れ替え，全体としてのIOスループットを向上させることが可能となっている．例えば，連続的ではない複数のIO要求を受けた場合，IO制御機構はアドレス順に並べ替えて実行することにより，IO処理の連続性を高め，スループットを向上させることが可能である．

本論文では，構造劣化による問い合わせ性能の低下を極力回避することを目的として，データベース管理システムの問い合わせ処理において，順序依存性のない読み込みに関して非同期要求を発行することにより，複数のIO要求を一括発行し，ストレージ装置の有するIOスケジューリング能力を活用する非順序型IO処理を提案する．

また，本論文では，提案方式の試作機をPCサーバ及びファイバチャネルSANを用いた実験システムを用いて実装し，その有効性を検証する．この結果，従来的な同期読み込みを用いるデータベース管理システムと比較して，非順序型IO処理を可能とするデータベース管理システムは極めて高い性能を達成できること，並びに構造劣化による性能への影響をある程度抑制可能であることを示す．

まとめと今後の課題

本論文は，データベース再編成機能を有する高機能ディスクストレージシステムに関する研究，並びに非順序型IO処理によるデータベース構造劣化の軽減機構に関する研究からなる．

データベース再編成機能を有する高機能ディスクストレージは，構造劣化の回復処理をサーバからストレージに移譲する提案である．今後，ストレージとサーバの新しい役割分担の有効性について，更なる検討を進めていきたい．

非順序型IO処理によるデータベース構造劣化の軽減機構は，構造劣化による性能低下を回避すべく，ストレージ装置の潜在的なＩＯスケジューリング能力を活用するアプローチの提案である．非順序型IO処理の定量的効果について，更に検討を進めていきたい．

本論文は「データベースシステムにおける構造劣化管理の軽減に関する研究」と題し，データベース再編成機能を有する高機能ディスクストレージシステムの構成法を明らかにし，試作機を用いた性能評価実験によりその有効性を示すと共に，非順序型問い合わせ処理によるデータベース構造劣化の軽減機構を提案し，実装を用いた実験により有効性を論じており，9章から構成される．

第1章は序論であり，本研究の背景および目的について概観し，本論文の構成を述べている．

第2章は「関連研究」と題し，データベースにおける構造劣化を解消するデータベース再編成なる処理に関し，現時点までに提案されている手法の特徴を纏めるとともに，その問題点を明らかにしている．

第3章は「データベース再編成機能を有する高機能ディスクストレージ」と題し，自己再編成ストレージと名付けた，オンラインデータベース再編成機能を有する高機能ディスクストレージを提案している．即ち，データベースにおいては一般に更新操作が繰り返されるにつれて，例えば，レコードの並びが乱雑化し，連続したキー値を有するレコードの走査に要するコストが大きく増加するなど，データベースの格納構造が劣化することによりアクセス性能が低下する現象が発生するが，自己再編成ストレージはデータベース再編成をストレージ装置内部でオンラインに実施することにより，データベースの構造劣化を常に回避することが可能であることを示している．また，ストレージ装置が有する豊富な入出力帯域と高い処理能力を活用し，並列パイプライン化データ処理，物理アドレスレベル入出力スケジューリング並びに独自の高速ログ適用手法を導入することにより，データベース再編成の大幅な高速化が達成可能であることを明らかにしている．

第4章は「自己再編成ストレージの試作機と性能評価」と題し，第3章で提案された自己再編成ストレージの有効性を検証すべく，商用のデータベース管理システム（DBMS）並びにオープンソースのDBMSを対象として，PCサーバ並びにファイバチャネルによるストレージエリアネットワーク（SAＮ）を用いた自己再編成ストレージ実験システムについてその構成を述べると共に，代表的なデータベースベンチマークアプリケーションであるTPC-C並びにTPC-Hを用いた性能評価結果を示し，従来のサーバソフトウェアによる再編成に比べて，自己再編成ストレージによる再編成は一桁以上高速であることを明らかにしている．

第5章は「複数の制御モジュールに処理を分散可能な並列データベース再編成処理」と題し，自己再編成ストレージの更なる高速化を目的とし，複数の制御モジュールを用いて並列に再編成処理を実行可能とする並列データベース再編成処理方式を提案している．また，実験システムを用いた性能評価を示し，入出力帯域を巧みに引き出すことにより，極めて高速な再編成が可能であることを明らかにしている．

第6章は「データベース更新の局所性を利用する部分再編成機構」と題し，データベースの更新が局所性を有することに着目し，構造が劣化した局所空間のみに対して再編成を行うことにより再編成実行時間を大きく削減し，全体を再編成する場合とほぼ同程度の性能を実現する部分再編成機構を提案している．構造劣化が局所性を有する2つの代表的なケーススタディを示し，部分再編成の実現方式を示すとともに，試作機において実装した部分再編成機構の性能評価結果を示すことにより，その有効性を明らかにしている．本部分再編成手法はとりわけ大規模なデータベースに対して極めて有効な方式といえる．

第7章は「非順序型問い合わせ処理を可能とするデータベース管理システム」と題し，関係データベースにおける関係代数演算は，演算対象を集合としていることから，タプルごとの処理順序に依存しない点に着目し，問合せ処理を構成するタプル演算を非順序的に実行可能とするデータベースシステムを提案している．特に，ストレージ装置が有する高度な入出力スケジューリング能力を活用することにより，タプルの順序に従った処理を行う従来の処理系と比較することにより，その有効性を論じている．又，既存のDBMSを用いて実装する為の非同期入出力先読みを利用した問合せ処理方式を明らかにしている．

第8章は「非順序型問い合わせ処理による構造劣化の軽減とその評価」と題し，非順序型の問合せ処理を用いることによりストレージ装置の入出力スケジューリング機能を活用することにより，構造劣化による問い合わせ性能の低下を軽減することが可能であることを明らかにしている．又，オープンソースDBMSを用いて，提案方式の実装を示すと共に，性能評価実験を示し，当該手法が大変有効であることを明らかにしている．

第9章は結論であり，本研究の成果と今後の課題について総括している．

以上，これを要するに，本論文は，構造劣化の回復処理をサーバからストレージに移譲することを目的としたデータベース再編成機能を有する高機能ディスクストレージシステムを提案しその有効性を明らかにすると共に，構造劣化による性能低下を回避すべくストレージ装置の入出力スケジューリング能力を活用する非順序型入出力処理によるデータベース構造劣化の軽減機構を提案しその有効性を実証しており，情報理工学上貢献するところが少なくない．

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる．