本論文は,高速な大規模データベース解析を可能にする並列関係データベース処理系の構成法に関して,標準ハードウェアから成る大規模PCクラスタ上での実装と性能評価を中心に研究した成果をまとめたものである.

　近年のデータベース応用では,トランザクション処理性能の向上に伴って蓄積された大量のデータに対して種々の解析を行う意思決定問合せ処理技術への関心が高まっている.このようなデータ解析には非常に高い処理能力が要求されるため並列計算機の利用が一般化しつつあるが,現行の商用DBMSにおいては並列化や意思決定問合せへの対応が不十分であり,高価な専用ハードウェアや大量資源の投入,あるいは個々の事例に特化した最適化などによって性能向上を図っているのが現状である.そこで東京大学生産技術研究所喜連川研究室ではSDCプロジェクトの下に,高性能な並列関係演算アルゴリズムを独自の並列アーキテクチャおよびシステムソフトウェア上に実装することで飛躍的な処理効率の向上を目指してきた.

　一方,マイクロプロセッサや標準バスの高速化によるパーソナルコンピュータ(PC)の性能向上や,ATMに代表される次世代標準ネットワークの技術開発の進展は著しく,これらを構成要素として並列処理システムを構築することで従来の超並列計算機に対して圧倒的に高い性能対価格比を実現できると期待される.そこで本研究では,100台のPCをATMスイッチで結合した大規模PCクラスタ上に,SDCシステムソフトウェアをより大規模な環境で広範な問題に適用可能にした意思決定問合せ処理系を構築する事で,PCクラスタによる超並列関係データベースサーバ実現の可能性を示すことを目的とする.

　まず,SDCプロジェクトの最終的な評価を行い,得られた成果を継承・発展可能なものにするために,一般的な問合せの実行や異なるプラットフォームへの移植を前提としてSDCシステムソフトウェアの再設計を行い,並列問合せ処理系DBKernelとして提示した.その結果,クライアントとのインタフェースを明確化し,独自のメモリ管理およびファイル管理モジュールを追加し,ノード間同期やノード内プロセッサ間通信を効率化することができた.そして,DBKernelをSDC-II上に実装し,業界標準ベンチマークTPC-D(1GB/10GB)を用いた性能評価を行うことにより,SDC-IIはハードウェアの性能に比して高い性能を達成しているものの,開発に多大な時間を要したため,最先端の商用並列機とは絶対性能で大きな格差が生じている事が明らかになった.

　次に,100台のPCと1台のATMスイッチからなる大規模クラスタを構築し(図1),DBKernelの実装を行った.SDC-II上の実装と共通するソフトウェア構造を保ち,標準的なUnix上で動作するシステムを実装する事ができた.また,100GBのTPC-Dベンチマークによる性能評価を行い,問合せの実行スケジューリングが性能に与える影響を調べた.その結果,最も高性能な既存商用システムに対しても最高で5倍以上の性能を達成することができた.これにより,PCクラスタの有効性が単に性能対価格比だけに留まらず絶対性能においても充分存在すること,問合せ処理系の改善の効果が大きいことが明らかになった.

図1:大規模PCクラスタのシステム構成

　TPC-Dベンチマークにおいては,データ分布は一様であり,並列化の効果を得る事は比較的容易であったが,現実のデータにおいては分布に偏り(スキュー)が存在するため,台数効果を維持するためには負荷分散機構が不可欠である.SDCではRedistribution Skewに属するスキューをアルゴリズムとハードウェアの協調により解決している.PCクラスタにおいてはハードウェアによる解決法は採らないが,より高度な問題であるJoin Product Skewを処理するための実行時負荷分散機構を実装・評価し,その有効性を示した.

　また,さらなる性能向上を達成すべく,物理ファイル編成方式にトランスポーズドファイルを適用した.トランスポーズドファイルは,リレーションを属性毎に独立したファイルに格納する技法であり,多数の属性から成るリレーションに対して一部の属性に関する解析を行う意思決定問合せにおいては,I/O量の削減によるディスクボトルネックの解消という効果が期待できる.しかし,分離された属性を再び結合する処理が増えるため,結合演算の効率が重要になる.PCクラスタ上でトランスポーズドファイル編成を100GB TPC-Dベンチマークの問合せに対して適用する事により,通常ファイル編成に比べて2倍程度の性能向上が達成された.この結果,意思決定問合せに対しては本技法が極めて有効である事が明らかになった.

　以上の性能評価においては,シングルユーザ環境を想定していたが,DBKernelはマルチユーザ環境にも対応している.特に,複数の問合せが同じデータベースに対して発行された時には,同一ファイルへのアクセスを実行時に検出し,問合せ間でI/O処理を共有する機構により性能向上を図っている.また,ファイルの大きさに基づいてファイルアクセスの優先順位を設定する事により,応答時間の長くなる大きなファイルの読み込みが共有される確率を高める工夫を施している.TPC-Dで規定された複数問合せストリームの実験により,同時に実行される問合せ数を増やした時に全体の処理時間の増加が抑えられ,システム全体としてのスループットが非常に高い事が明らかになった.

　本論文は,序論,関係演算とその並列処理方式,並列関係問合せ処理系DBKernelの設計,SDC-IIにおけるDBKernelの実装と性能評価,大規模PCクラスタにおけるDBKernelの実装と性能評価,負荷分散機構とその評価,トランスポーズドファイル編成による高速化,DBKernel実行モデルの評価,まとめと今後の展開の9章より成る.

　第1章「序論」では,本論文の概要および構成について述べた後,関係データベースシステムにおける非定型問合せ処理の特徴とその問題点を挙げ,これまでに行われてきた関係データベース処理高速化のアプローチについて概観する.また,並列計算機のアーキテクチャにおける専用部品から商用部品採用への傾向について触れ,SDCプロジェクトから大規模PCクラスタへの推移の背景を明らかにする.

　第2章「関係演算とその並列処理方式」では代表的な関係演算である選択演算,射影演算,結合演算,および集計演算について述べ,その並列処理方式を示す.

　第3章「並列関係問合せ処理系DBKernelの設計」ではSDCのシステムソフトウェアを一般化・大規模化するために新たに設計された並列関係問合せ処理系DBKernelの設計思想を述べる.はじめに,サーバのアーキテクチャや並列性に対して透過なクライアント・サーバ間インタフェースを実現する並列問合せ実行方式を説明する.また,サーバノード内で効率的な処理を実現するために採られているFunction Shippingに基づく実行方式について述べ,通常のData Shippingによる実行方式との比較を行う.さらに,DBKernel上位層を構成するSQL言語処理系,スキーマ管理,問合せ実行制御と,下位層を構成するメモリ管理,ディスクデバイス管理,ネットワークデバイス管理,ファイルシステム,プロセス間通信機構,ディスパッチャ,などの構成要素の機能と役割に付いて述べ,例を用いてDBKernel上でのデータ駆動並列プログラミングの特徴を示す.

　第4章「SDC-IIにおけるDBKernelの実装と性能評価」では,まずSDC-IIのハードウェアアーキテクチャとその特徴について述べ,その上でのDBKernelの実装方法について説明する.そして,TPC-Dベンチマークを用いた性能評価結果を示し,公表されている商用並列システムの性能との比較を行う.その結果,投入したハードウェア資源で正規化した性能では非常に高い値を示している事により,SDC-IIアーキテクチャの有効性が明らかとなるが,反面ハードウェア構成の格差が大きく,意味のある絶対性能の比較ができないことを指摘し,独自ハードウェア採用の難点を示す.

　第5章「大規模PCクラスタにおけるDBKernelの実装と性能評価」では,完全に標準的なハードウェアのみで構成された100ノードATM結合大規模PCクラスタについて述べる.はじめに,システムの構成要素とそれぞれの基本性能を示す.次に,PCクラスタ上で可搬性を重視して行ったDBKernelの実装方法について説明する.さらに前章と同様,TPC-Dベンチマーク(100GB)による性能評価を示し,システム全体の絶対性能においてもハイエンド商用並列システムを凌駕していることを明らかにする.これにより,PCクラスタによる並列意思決定問合せ処理の有効性とDBKernelの処理性能の高さとが実証される.

　第6章「負荷分散機構とその評価」では,データスキューのもたらす問題とスキューの分類に触れ,SDC-IIにおけるバケット分散ハッシュ結合によるRedistribution Skewの解決とSDC-IIデータネットワークによるアルゴリズム支援について述べる.また,Join Product Skewを解決するための動的負荷分散アルゴリズムについて説明し,大規模PCクラスタ上での実装と性能評価について述べる.

　第7章「トランスポーズドファイル編成による高速化」では,不要な属性の読み込みを回避することでI/Oボトルネックを改善する,トランスポーズドファイル編成を実際に適用した際の効果に付いて述べる.まず,DBKernel上でのトランスポーズドファイルの実装方式について説明し,100GB TPC-D問合せに適用した際の性能向上を示す.その結果,通常のファイル上での実行に比べて2倍近い性能向上を達成していることを明らかにする.

　第8章「DBKernelの実行モデルの評価」では,まずマルチユーザ環境でのI/O共有を実現する手法とそれによる効果を述べる.また,多数の演算子をコンテクスト切替えなしに並行して評価する技法について説明し,その効果を示す.

　第9章「まとめと今後の展開」では,本論文で提示した事項と明らかになった事柄をまとめると共に,今後の研究課題として残された問題について触れ,それに対する基本的な方針を述べる.

　本論文は「大規模PCクラスタによる超並列関係データベースサーバの構築」と題し,100台のパーソナルコンピュータ(PC)をATMスイッチにより結合した大規模PCクラスタを構築すると共に,当該システムにおいて関係データベース並列問合せ処理系の実装ならびに詳細な評価を行い,その有効性を論じており,9章よりなる.

　近年,大規模データベースに対する意思決定問合せ処理の重要性が認識され,その性能向上が大きな課題となっている.本研究では,SDC-IIなる専用ハードウエアならびに,標準ハードウエアのみからなるPCクラスタの2つのシステムを構築すると共に,プラットフォームに依存しないDBKernelなる並列関係データベース処理系を提案し,両システムに実装することにより,大規模PCクラスタを用いた並列データベースサーバは専用ハードウエアを採用したシステムに対して極めて低いコストで高い性能を達成可能であることを実証することを目的としている.

　第1章「序論」では,関係データベースシステムにおける意思決定問合せ処理の高性能化が社会的に強く求められている背景に関して述べると共に,標準ハードウエアによる並列計算機構築の動向についてまとめ,本研究の目的を明らかにしている.

　第2章「関係演算とその並列処理方式」では関係演算とその処理アルゴリズムについて述べている.特に,意思決定問合せ処理において多用される結合演算に関し,本論文に於いて採用しているハッシュに基づく並列処理アルゴリズムと,多重結合演算処理アルゴリズムに関し説明している.

　第3章「並列関係問合せ処理系DBKernelの設計」では,非定型問合せ処理の高速化を目的とする並列関係問合せ処理系DBKernelの設計方針を述べている.即ち,複雑な多重結合演算を高速に実行するためのデータ駆動型実行モデルと,不要なデータ移動を回避するFunction Shipping方式により,大量のデータに対し効率良く関係演算を実行可能であることを示している.更に,プラットフォーム独立性の高いDBKernel上位層とプラットフォームに依存して実装される下位層の構成要素について,それぞれの機能と役割を説明している.

　第4章は「SDC-IIにおけるDBKernelの実装と性能評価」と題し,プラットフォームとして独自の専用並列アーキテクチャに基づくSDC-IIを取り上げ,DBKernelの実装と意思決定問合せの標準ベンチマークであるTPC-Dを用いた性能評価について述べている.商用並列システムとの性能比較に基づき,SDC-IIは少ないハードウエア資源で高い処理効率を達成していることを明らかにする一方で,ハードウエアの専用化に伴う開発の長期化により,ハードウエアの陳腐化が生じ,絶対性能に大きな格差が生じている事実を指摘し,専用ハードウエア採用の難点を明らかにしている.

　第5章は「大規模PCクラスタにおけるDBKernelの実装と性能評価」と題し,100台のPCをATMスイッチによって結合した標準ハードウエアのみで構成される大規模PCクラスタに対し,DBKernelの実装手法とTPC-Dベンチマークを用いた性能評価について述べている.可搬性を重視したDBKernelの特長について説明すると共に,100GBデータベースを用いたTPC-Dベンチマークにより,商用並列システムに比べ,十分高い絶対性能を達成可能であることを示し,PCクラスタによる並列問合せ処理の有効性を実証している.

　第6章「負荷分散機構とその評価」では,演算対象のデータ分布の偏りにより,プロセッサ間での負荷の不均衡化が発生するという問題を指摘すると共に,その解決法について述べている.偏り(スキュー)を分類すると共に,その一つである再分配スキューに関し,SDC-IIで採用したバケット分散ハッシュ結合方式について述べ,相互結合ネットワークに付加したハードウエアによってバケット平坦分布を実現する方法を提案し,負荷の均衡化を達成すると共にネットワークの輻輳も回避可能なことを示している.次に,より取扱いが困難な結合演算スキューを解決するための動的負荷分散アルゴリズムについて説明し,大規模PCクラスタ上での実装と性能評価について述べ,提案手法の有効性を実証している.

　第7章「トランスポーズドファイル編成による高速化」では,トランスポーズドファイルの有効性を検討している.即ちトランスポーズドファイルは不要属性の読み込みを回避し,I/O負荷を軽減可能とする一方,CPU負荷が著しく増大することから,従来,トランザクション処理では採用されて来なかったが,意思決定問合せ処理では有効であるとし,DBKernel上での実装方式について述べると共に,100GB TPC-D問合せに適用し,通常のファイル構造を用いた場合に比べて2倍近い性能向上が得られることを明らかにしている.

　第8章「DBKernelの実行モデルの評価」では,DBKernelのデータ駆動型実行モデルの有効性を詳細に検討している.本モデルでは,マルチユーザ環境での動的なI/O共有が可能となり,主記憶容量の許容範囲内では複数の問合せに共通なリレーションのロードを一括して行うことにより,極めて高いスループットが得られることを実証している.また,多数の演算子を単一のコンテクスト内で並行して評価する技法について説明し,各演算子に実行コンテクストを割当てる方式との比較により,その効果を明らかにしている.

　第9章「まとめと今後の展開」では,本研究の成果と今後の研究課題について述べている.

　以上を要するに,本論文は100台のパーソナルコンピュータをATMスイッチを用いて結合した大規模PCクラスタを構築し,当該システム上に動的負荷分散機構ならびに動的I/O共有を特徴とする並列関係データベースエンジンDBKernelを実装すると共に,100GBなる実用規模のデータベースに対するTPC-D意思決定問合せベンチマークにより,商用システムに比べて高い価格性能比を達成可能であることを実証したものであり,情報工学上貢献する所が少なくない.よって本論文は博士(工学)の論文として合格と認められる.