本論文は関係問合せ処理を高並列アーキテクチャ上で高速に実行する為の実行方式とスーパーデータベースコンピュータSDC-II上への実装およびその性能評価結果に関する研究の成果をまとめたものである.

　近年のハードウェアの進歩によりトランザクション処理を中心とする更新系の処理性能が格段に向上し,これに伴ってデータの集約が進み,企業等が巨大なデータベースを保持するに到って,これを企業活動を行う上での意志決定などに有効に活用する事が求められるようになって来た.この様な意志決定支援等に用いられる非定型問合せ処理においては極めて巨大(数百MBから数GB以上)なデータベースに対する非定型問合せ処理が発生するが,現在のメインフレームを中心としたデータベースシステムではこれを実用的な時間で処理出来ない.SDCプロジェクトはこのような大規模な関係データベースシステムに対し飛躍的な性能向上を達成すべく並列アーキテクチャに基づくスケーラブルなSQLサーバの構築を目指したものである.本論文は試作機SDC-II上に実装したシステムソフトウェアの設計方針並びに実行方式について論じ,実機上での性能評価結果について示す.さらに,同一のモデルに基づいくソフトウェアを汎用のワークステーション上に移植し簡単な性能比較を行った.

　SDC-IIでは関係データベース処理の中でも特に負荷の高い結合演算を高速に実行する為の強力で単純な問合せ実行方式の構築と試作機上への実装を行った.SDC-IIは全共有型アーキテクチャと無共有型アーキテクチャの双方を備えたハイブリッド構成を取ることにより高い処理性能と拡張性を得ている.SDC-IIの問合せ実行方式ではこれらの双方のアーキテクチャに跨る高速なデータ交換の手段を提供する為にデータを固定長のページに格納しこれをプロセッサ間を繋ぐバッファを通じて環流させることでI/Oボトルネックを解消し高い並列性を引き出すことが出来た.

　またRight-Deep多重結合演算処理に代表される問合せ処理レベルでの並列処理を効率的に実現するために複数のネットワークI/Oバッファの実装と複数のバッファからの選択的ページ獲得ならびに複数のハッシュテーブルの動的割当と解放を可能とした.さらに問合せレベルでの並列処理に伴うデッドロックの発生を抑制するためにバッファに対する優先度制御を行い,またデッドロック発生時にこれを解消するためのアルゴリズムを示した.

　本論文ではさらに,提案した問合せ実行方式にしたがってSDC-II上に構築したシステムソフトウェアの実装法について述べた.すなわち,SDC-II上に実装されるソフトウェア群の構成並びにページ,バッファ,結合演算のためのハッシュテーブル等の基本的構成要素の実装法について述べる.

　問合せ実行方式の有効性を確認するため,SDC-II上において結合演算処理の詳細な性能評価を行いその評価結果を示した.性能評価では結合演算処理の性能に影響を与えるパラメタとしてタプル数,選択率,結合率,分割バケット数,ハッシュテーブルエントリ数,タプル長,プロセッサ数,モジュール数に対して,各々のパラメタの変動による性能の変化をGRACEハッシュ結合演算および平坦化ハッシュ結合演算について確認した.GRACEハッシュ結合演算ではデータ処理モジュール間での負荷が負均一な場合における性能低下が大きいのに対し平坦化ハッシュ結合演算は負均一負荷においてもほとんど性能低下を起こさずデータ処理モジュール数に比例した理想的な性能向上を達成できることを示した.また結合演算処理中のメモリ利用率やCPU使用率,データネットワーク上のスイッチにおけるブロック率等の統計情報を収集することでシステムの振舞の詳細を示した.

　さらに意志決定支援を想定して策定が進められているドラフト版のTPC-Dベンチマークを用いて多重結合演算における処理性能の評価を行いその結果を示した.TPC-Dベンチマークはタプル数およびタプル長の大きく異なる6つのリレーションと17の問合せから構成されている.本論文では多重結合演算を含む3つの問合せについてその処理性能と多重結合演算時のシステムの振舞に関して詳細に評価している.TPC-Dベンチマークは単一結合演算処理に比較してはるかに複雑で処理負荷が高いがSDC-IIはこれを極めて効率良く高速に実行可能である.さらにRight-Deep多重結合演算の実行時に結合率を大きく変動させることにより負荷変動下でのシステムの振舞を調べた.フリーページを共有しページの割当に対する制限が緩いSDC-IIの問合せ実行モデルではより制限の強い場合に比べはるかにデッドロックが発生しにくい事を示した.

　本論文は,序論,SDC-IIのハードウェアアーキテクチャ,並列関係問合せ処理の実行方式,並列結合演算処理,並列関係問合せ処理のSDC-IIへの実装,基本的性能評価,ベンチマークによる多重結合演算の性能評価,汎用プラットフォームへの実装,まとめと今後の展開の9章から構成される.

　第1章「序論」では,本論文の概要,本論文の構成について述べた後,関係データベースシステムの特徴とその問題点について触れ,関係データベース処理における非定型処理への社会的要求について示す.さらに,これまでに行われて来た関係データベースの高速化に関する研究について概観し,その中でSDC-IIの位置付けを明らかする.

　第2章「SDC-IIのハードウェアアーキテクチャ」ではSDC-IIのアーキテクチャについて詳述する.SDC-IIは密結合型処理モジュールをデータネットワークで相互接続したハイブリッドアーキテクチャと高速で大容量の2次記憶系を特徴とする.まず,SDC-IIのアーキテクチャ設計における方針について述べ,続いてSDC-IIのアーキテクチャの詳細について示す.

　第3章「並列関係問合せ処理の実行方式」ではSDC-IIで採用した問合せ実行モデルについて示す.並列関係問合せ処理,特にハッシュ結合演算アルゴリズムの特徴について示し,これを高速に実行するための枠組としてページとバッファに基づくI/O駆動型の問合せ実行モデルを採用した.本実行モデルにより,プロセッサがI/Oの制御から開放され高速に処理を実行することができる.また,バッファ上を流れるページを制御することによりシステム全体のデータ流制御を実装できる.

　第4章「並列結合演算処理」ではSDC-IIに実装した単一結合演算アルゴリズムとして並列GRACEハッシュ結合演算アルゴリズム,平坦化ハッシュ結合演算アルゴリズム,また多重結合演算アルゴリズムとしてLeft-deep多重結合演算アルゴリズムおよびRight-deep多重結合演算アルゴリズムに関し,これらの特徴とアルゴリズムの詳細について述べる.

　第5章「並列関係問合せ処理のSDC-IIへの実装」では第3章で述べた並列関係問合せ処理の実行方式のSDC-II上における実装について述べる.まずSDC-IIのソフトウェア構成について述べ,ページ,バッファ,ハッシュテーブル等の構成要素の実装法について示す.さらに本システムにおけるデッドロックの抑制および解消法について示す.

　第6章「基本的性能評価」ではSDC-II上に実装されている結合演算処理について基本的性能評価結果について示し,考察を加える.まず,性能評価を行ったシステムの構成を示し,システム構成要素の各種パラメタを明確にする.次いで種々のパラメータに対する単一結合演算における性能評価を行い,その評価結果を示す.さらにこれらの処理の実行時にリアルタイムでシステムの稼働率やメモリの使用率を収集する手法とこれに基づいたシステムの稼働状況に対する評価を行い試作システムの有効性を明らかにする.

　第7章「ベンチマークによる多重結合演算の性能評価」では問合せレベルの並列処理に対する性能評価としてRight-deep多重結合演算の実行とその性能評価結果について述べる.ドラフト版のTPC-Dベンチマークを用いてSDC-II上での多重結合演算処理に対する性能評価結果を示し,ハードウェア資源の使用率から処理内容の解析を行う.さらに負荷変動に対する多重結合演算処理の振舞を解析する事からデータ流制御が良好に稼働している事を示す.

　第8章「汎用プラットフォームへの実装」では専用ハードウェア上での実装を中心に述べて来た並列関係問合せ処理の実行方式ついて汎用プラットフォーム上に移植を行い,処理性能を測定し,ポータビリティの高さを示す.

　第9章「まとめと今後の展開」では本論文で提案した事項と明らかになった事項を簡単にまとめる.また,マルチユーザー環境への拡張に関してその方式について具体例を示す.また,今後研究を進めるべき方向についても触れる.

　本論文は『並列関係問合せ処理の実行方式とその実装並びに性能評価に関する研究』と題し,関係データベースにおける問合せ処理の並列実行方式を提案するとともに,スーパーデータベースコンピュータSDC-IIなる並列データベースサーバ上に実装し,詳細な性能評価を行いその有効性について論じたものである.近年,意思決定支援システム等の応用では大容量データベースの操作が不可欠となりつつあり,その高速処理の重要性が増している.本論文は安価なマイクロプロセッサの複合体であるSDC-II上に並列関係問合せ処理を実装し,汎用大型計算機に比べ飛躍的に性能を向上可能であることを実証している.

　第1章『序論』では,本研究の背景,意義,並びに,従来の一連の研究などが纏められている.

　第2章『SDC-IIのハードウェアアーキテクチャ』では,本論文の研究対象である並列問合せ処理系を実装する実験機,SDC-IIについて,その設計方針,並びに,実装されたハードウェアアーキテクチャについて纏めている.データベース応用においては,高性能な入出力システムと拡張容易なアーキテクチャが不可欠であることを述べ,専用の入出力制御プロセッサを有する密結合マルチプロセッサ多数台を,負荷分散機構を有する高機能相互結合網によって結合したSDC-IIの構成とその特徴を明らかにしている.

　第3章は『並列関係問合せ処理の実行方式』と題し,関係データベースに於ける問合せ処理の並列実行方式を提案している.即ち,ディスク,並びに,相互結合網は専用のインタフェースハードウェアを用い,プロセッサの介在なしに,自律的にデータの転送単位であるページを生成し,一方,プロセッサは生成されたページに対し,データベース演算を施すという,ページがプロセッサを駆動する実行方式を提案し,それにより,データ移送負荷の高いデータベース処理が効率良く実現できることを示している.

　第4章は『並列結合演算処理』と題し,関係データベース処理に於いて最も処理負荷の高い結合演算を取り上げ,高機能相互結合網を用いた平坦化結合演算処理アルゴリズム,ならびに,複数の結合演算をパイプライン状に実行する多重結合演算処理アルゴリズムについて述べると共に,これらが第3章で提案した方式により効率よく実行可能であることを示している.

　第5章は『並列関係問合せ処理のSDC-IIへの実装』と題し,第3章において提案した実行方式を実装する手法について纏めている.即ち,ページ,その格納場所としての各種バッファ,結合演算の為のハッシュテーブル等の基本論理構成要素の実装法について述べている.SDC-IIでは各構成要素間はページを単位としてデータの授受を行うことにより関係データベース処理を実現しており,ディスクコントローラによるページ生成,相互結合綱インタフェースに於けるページ管理に関し,そのハードウェア支援機構について述べるている.又,デッドロックを抑制・解消するためのデータ流制御方式,モジュール間終了同期機構,バッファ構造などについて詳述している.更に,多重結合演算を支援するためには,結合演算子数に等しいデータ流を同時に操作する必要があるが,その効率の良いデータ流制御手法を提案している.

　第6章は『基本的性能評価』と題し,試作機SDC-II上で行った性能評価結果について述べている.まず,単一結合演算を取り上げ,タプル数,選択率,結合率,ハッシュテーブルエントリ数,タプル長,駆動プロセッサ数,駆動モジュール数など各種パラメータを変更することにより,性能特性を詳細に解析している.更に,システム内での資源の利用状況を把握すべく,各種バッファの使用量,バッファへのページの流入速度,ディスクからのページ生成速度,プロセッサ稼働率,データネットワーク上の各スイッチにおけるブロック率などを実行時に観測可能な性能評価支援環境について,そのツールの構成を述べるとともに,開発したツールにより結合演算が効率よく実行されていることを定量的に示している.Zipf分布に従うデータを用いて,非一様なデータに対する性能評価を行い,従来の手法ではモジュール間で負荷の非均衡性により,大きな性能低下が生じていたのに対し,本論文で提案する平坦化結合演算方式により,駆動モジュール数に比例した理想的な性能向上率を達成できることを示している.

　第7章『ベンチマークによる多重結合演算の性能評価』では,意思決定応用を想定して策定が進められている暫定版のTPC-Dベンチマークの中から、結合演算の多く含まれる複雑な問合せを3つ取り上げ,SDC-II上で多重結合演算の性能評価を行っている.本ベンチマークは,タプル数.タプル長の大きく異なる5つのリレーションから構成され,第6章での処理と比べて,はるかに複雑で処理負荷が高いが, SDC-IIでは効率良く極めて高速に実行可能であることが示されている.

　第8章は『汎用プラットフォームへの実装』と題し,SDC-IIを対象として開発した並列関係問合せ処理系を複数個のプロセッサを有するワークステーションに移植し,その際必要となった変更箇所を整理し,ポータビリティの高さを確認している.更に,汎用並列マシンへの移植に関しても検討し,比較的容易に実現可能であるとしている.

　第9章『まとめと今後の展望』では,上記の成果を要約するとともに,マルチユーザ支援に関するシステムの拡張方法について纏めるとともに,今後の研究を展望している.

　以上これを要するに,本論文は,並列関係問合せ処理の実行方式を提案するとともに,SDC-IIなる実験機に実装し,現行の汎用大型計算機に比べ,極めて高い性能を実現可能であることを実証するとともに,詳細な性能評価を行い,その有効性を明らかにしたものであって,情報工学上,貢献するところが少なくない.

　よって著者は東京大学大学院工学系研究科情報工学専攻における学位論文審査に合格したものと認める.