JP3777872B2 - 問合せ並列処理システム及びプログラムを記録した機械読み取り可能な記録媒体 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、データベースに対するデータ検索，グループ化，集計演算などを記述した問合せ文を、複数の計算機ノードを用いて並列処理する技術に関し、特に、複数の計算機ノードの処理負荷を均衡化させることによってシステム全体の性能を向上させる問合せ並列処理システムに関する。
【０００２】
【従来の技術】
データベースに対する問合せを並列に処理する方式は、過去に多くの研究者によって提案されてきた("Query Evaluation Techiniques for Large Databases", Goetz Graefe, ACM Computing Surveys, Vol. 25, No.2 June 1993 など) 。巨大なデータベースに対する問合せの処理は、二次記憶装置からのデータ読み込みがネックになる。このため、複数の二次記憶装置にデータベースを分割して格納し、並列に読み込んで処理する方式が基本的となっている。
【０００３】
１つのデータベースに対し条件を指定して検索を行い該当レコードを取り出す処理を選択処理と呼ぶこととする。例えば、銀行の口座データベースに対し口座番号を指定して残高を照会したり、指紋データベースに対し指紋画像を与えて照合する処理が選択処理となる。データベースの選択処理は、データベースを複数の二次記憶装置に分割して格納することによって容易に並列化できる。この場合、各二次記憶装置に分割格納された各部分データベースを各計算機ノードから並列に読み込んで検索処理を行うことにより並列化する。選択処理では、インデックスなどのアクセスパスを用いることがあるが、部分データベース毎に独立にインデックスを作ることにより、インデックスを用いた選択処理を容易に並列化できる。これらの並列化の手法は商用のリレーショナルデータベースシステムにも取り入れられている。例えば、Oracleなどが挙げられる（「パーティショニング技術のVLDBへの適用」、電子情報通信学会 信学技報AI97−40,DE97−73、1997−12) 。
【０００４】
データベース中のレコードを、ある属性（カラム）の値で分類することを分類処理と呼ぶこととする。例えば、銀行の口座データベース中のレコードを支店別に分類する処理である。また、レコード数を数えたり、あるカラムの平均値や最大値を算出するなどの処理を集計処理と呼び、レコード群を、あるカラムの値でソートする処理をソート処理と呼ぶ。
【０００５】
これらの処理を並列化する技術が、特開平10−97544 号公報に記載されている。この技術では、データベースを複数の入出力サーバ配下の複数の二次記憶装置に格納しておき、複数の入出力サーバから並列にデータベース中のレコードを読み出す。読み出されたレコードは入出力サーバによって分類され、複数の集計処理サーバに分配される。集計処理サーバでは各入出力サーバからのレコードに集計処理を施して部分集計結果とし、最後に、部分集計結果をマージする。ここまでの処理は複数の入出力サーバ、複数の集計処理サーバによって並列に行われる。
【０００６】
このように、データベースに対する問合せの並列処理は、データベースを複数の部分データベースに分割して複数の二次記憶装置に分散格納し、複数の計算機ノードが各二次記憶装置から並列にデータを読み込んで処理するということを基本にしている。しかし、データベースを二次記憶装置に分散格納して各部分データベースに対し並列に検索処理を行う場合、部分データベースを各二次記憶装置に均等に格納したとしても、それらを読み込んで処理を行う各計算機ノードの負荷は均等にならず、それによって、システム全体の処理効率を悪化させてしまう場合がある。
【０００７】
このように負荷の不均衡がある場合、共有メモリ型の並列計算機ならば、CPU 数よりも多くのプロセスを生成しておけばシステム全体の処理効率悪化を防げる。なぜなら、プロセス毎の負荷が不均衡になってもOSのスケジューリングによってプロセスが切り替わり、CPU が遊ぶことなく問合せの処理を進められるからである。しかし、複数の計算機ノードを用いた並列計算機では、プロセスを計算機ノード間で移動できない。システム全体の処理は、最終的には負荷の最も重い計算機ノードの処理終了を待ち合わせるため、負荷の軽かった計算機ノードが遊んでしまい、システム全体の処理効率が悪化する。
【０００８】
一方、特開平10−301822号公報には、次のような技術が記載されている。データベースに対する問合せを解析してアクセスパスを生成し、更に、アクセスパスを複数の部分アクセスパスに分解する。その後、同時に実行可能な部分アクセスパス群毎に、その群に属する部分アクセスパスの内のいくつかを処理コストに従って１つのグループにまとめる。ここで、処理コストとは、表の行数，列の分布状況，インデックスのヒット率等の統計情報から算出したものであり、部分アクセスパスの実行に要する負荷の度合を数値化したものである。また、部分アクセスパス群に属するいくつかの部分アクセスパスを処理コストに従って１つのグループにまとめる際には、そのグループの属する部分アクセスパスの処理コストの合計値が、上記部分アクセスパス群の最大処理コストを越えないようにする。
【０００９】
【発明が解決しようとする課題】
上記した特開平10−301822号公報に記載されている技術によれば、同時に実行可能な部分アクセスパス群の属する各グループの処理コストをほぼ等しくすることができる。従って、複数の計算機ノードに、グループ単位で処理を割り当てるようにすることにより、各計算機ノードの負荷をある程度は均衡化することができる。しかしながら、特開平10−301822号公報に記載されている技術は、統計情報という静的な情報を用いているため、各計算機ノードの動的な負荷の変動には対処できず、その結果、システム全体の処理効率を十分に高いものにすることができないという問題があった。
【００１０】
そこで、本発明の目的は、複数の計算機ノードから構成されるクラスタシステム上で問合せを並列処理する際、各計算機ノードにおける処理負荷を動的に均衡化させることにより、システム全体の処理効率を高めることにある。
【００１１】
【課題を解決するための手段】
本発明の問合せ並列処理システムは、問合せ処理用の計算機ノードで、問合せを解析して部分問合せに分解し、複数の部分問合せ処理用の計算機ノードに部分問合せを配布して並列処理を行わせ、返却された部分問合せの結果をマージして問合せの結果とする。この構成は、問合せを並列処理するための基本構成である。
【００１２】
本発明の問合せ並列処理システムでは、部分問合せを部分問合せ処理用の計算機ノードに配布する際、各計算機ノードへの配布数を随時決めて配布する。この時、各計算機ノードの負荷を等しく保つために、例えば、各計算機ノードで処理中になっている部分問合せの数が常に等しくなるように配布数を決める。配布数を越えて余った未配布の部分問合せは、後に、何れかの計算機ノードが結果を返してきた時などに、その計算機ノードに処理させることになる。つまり、結果を返してきた計算機ノードに対して、残っている部分問合せを処理させ、計算機ノードが遊ばないようにする。以上が本発明における負荷均衡化の基本的な考え方である。
【００１３】
また、本発明の問合せ並列処理システムでは、問合せ処理用の計算機ノードを複数化し、その計算機ノードがボトルネックになることを防ぐ。この場合、複数の計算機ノードで別々の問合せを受け、独立して各問合せの部分問合せ配布処理を行う。この時の配布ストラテジは、単独の計算機ノードで問合せを受け付ける場合と全く同様である。
【００１４】
また、部分問合せ処理用の計算機ノードの障害時には、その計算機ノードを検出し、その計算機ノードに配布すべき部分問合せを別の部分問合せ処理用の計算機ノードに配布し処理させる。これにより、部分問合せ処理用の計算機ノードに障害が発生しても、全ての部分問合せを処理し、問合せ結果を完全なものにすることができる。
【００１５】
無共有型クラスタシステムでは、各部分問合せ処理用の計算機ノードは自分に接続された二次記憶装置にしかアクセスできない。従って、その二次記憶装置に格納された部分データベースしかアクセスできない。そこで、各計算機ノードと、それがアクセスできる部分データベースの対応関係を管理しておく。これにより、各計算機ノードに対し、そのノードが処理可能な部分問合せを配布することができる。
【００１６】
無共有型クラスタシステムでは、部分データベースの原本と複製を別々の計算機ノード配下の二次記憶装置に格納する。これによって、同じ部分データベースに対して複数の計算機ノードからアクセス可能となる。つまり、同じ部分問合せを複数の計算機ノードで処理可能となる。このことを利用すると、負荷の軽い側の計算機ノードに部分問合せを処理させることが可能となり、これによって計算機ノードの負荷均衡化を行う。また、これと同時に、計算機ノードの障害時にも、そのノードに配布するべき問合せを別の計算機ノードに処理させることが可能となる。
【００１７】
【発明の実施の形態】
次に本発明の実施の形態について図面を参照して詳細に説明する。
【００１８】
本発明の第１の実施の形態の例について説明する。第１の実施の形態は、複数の計算機ノードが二次記憶装置を共有する共有型クラスタシステムの上で、二次記憶装置に記録されたデータベースに対する問合せを並列に処理する問合せ並列処理システムに関するもので、その構成例を図１に示す。
【００１９】
図１を参照すると、問合せ処理用の複数の計算機ノード１−１〜１−ｍ及び部分問合せ処理用の複数の計算機ノード２−１〜２−ｎが通信網４で接続され、計算機ノード間でデータの受け渡しができる。通信網４としては、Ether やATM のHUB やスイッチ、その他、専用結合ネットワークを利用することができる。
【００２０】
問合せ処理用の計算機ノード１−１〜１−ｍは、外部通信網５に接続されており、外部通信網５を介して問合せを受け取ることができる。外部通信網５としては、LAN やWAN などを利用する。問合せとしては、データの集合であるデータベースから、ある条件を与えて一部のデータを引き出すような要求や、データの値の平均値や最大値などの集計を行う要求、あるいは、あるデータの値に着目してグループ化したりソートを行う要求がある。これら要求は、問合せ言語SQL などを使って記述されて渡されたり、あるいは専用のキーワードのみを組み合わせて渡されたりする。
【００２１】
また、部分問合せ処理用の計算機ノード２−１〜２−ｎは、二次記憶装置３−１〜３−ｊを共有する記憶装置共有網６に接続されており、これらのいずれの計算機ノード２−１〜２−ｎも二次記憶装置３−１〜３−ｊにアクセスすることができる。記憶装置共有網６としては、SCSIやFibreChanel のHUB やスイッチ、その他、周辺装置用の専用ネットワークなどが用いられる。問合せの対象となるデータベースは、複数の部分データベース31に分割され、複数の二次記憶装置３−１〜３−ｊに分散して格納される。データベースの分割方法は、ラウンドロビン式分散配置、ハッシュ分割、キー値分割等の方法がとられる。
【００２２】
問合せ処理用の計算機ノード１−１〜１−ｍは、それぞれ問合せ解析手段11と、障害検出手段12と、配布数決定手段13と、問合せ統合処理手段14と、記録媒体Ｋ１とを備えている。
【００２３】
問合せ解析手段11は、外部通信網５を介して送られてくる自計算機ノード宛の問合せを解析し、この問合せを処理するための処理手順であって、問合せ対象となるデータベースを構成する各部分データベースに対する部分問合せ（部分データベースに対する検索要求）を含む処理手順を導出する機能を有する。
【００２４】
障害検出手段12は、部分問合せ処理用の計算機ノード２−１〜２−ｎに障害が発生したことを検出する機能を有する。
【００２５】
配布数決定手段13は、計算機ノード２−１〜２−ｎに配布する部分問合せの数を各計算機ノード２−１〜２−ｎの負荷に応じて動的に決定する機能を有する。
【００２６】
問合せ統合処理手段14は、問合せ解析手段11で導出した処理手順に従って問合せの処理を進め、各計算機ノード２−１〜２−ｎに対し部分問合せを配布する際には、配布数決定手段13を用いて決定した配布数だけの未配布の部分問合せを配布し、部分問合せの結果が返却された際には、関連する結果をマージしながら問合せの結果を導出する機能を有する。
【００２７】
計算機ノード１−１〜１−ｍが備えている記録媒体Ｋ１は、ディスク，半導体メモリ，その他の記録媒体であり、計算機ノード１−１〜１−ｍを問合せ処理用の計算機ノードとして機能させるためのプログラムが記録されている。このプログラムは、計算機ノード１−１〜１−ｍによって読み取られ、計算機ノード１−１〜１−ｍの動作を制御することで、計算機ノード１−１〜１−ｍ上に、問合せ解析手段11，障害検出手段12，配布数決定手段13, 問合せ統合処理手段14を実現する。
【００２８】
部分問合せ処理用の計算機ノード２−１〜２−ｎは、それぞれ部分問合せ処理手段21と、記録媒体Ｋ２とを備えている。
【００２９】
部分問合せ処理手段21は、問合せ処理用の計算機ノード１−１〜１−ｍから配布された部分問合せを受け、その部分問合せの処理を行い、配布元の計算機ノードに結果を返す機能を有する。
【００３０】
計算機ノード２−１〜２−ｎが備えている記録媒体Ｋ２は、ディスク，半導体メモリ，その他の記録媒体であり、計算機ノード２−１〜２−ｎを部分問合せ処理用の計算機ノードとして機能させるためのプログラムが記録されている。このプログラムは、計算機ノード２−１〜２−ｎによって読み取られ、計算機ノード２−１〜２−ｎの動作を制御することで、計算機ノード２−１〜２−ｎ上に部分問合せ処理手段21を実現する。
【００３１】
次に、本実施の形態の動作について説明する。
【００３２】
外部通信網５に接続される計算機ノード１−ｋ（１≦ｋ≦ｍ）で動作する問合せ解析手段11は、外部通信網５を介して投入された自計算機ノード宛の問合せを受け付けると、図２の流れ図に示すように、その意味を解析し、処理対象となるデータベースに対する処理ステップを含む、問合せの結果を求めるための処理手順を導出する（Ａ１）。例えば、図３（ａ）に示すような問合せに対し同図（ｂ）に示すような複数のステップから構成されるツリー状の処理手順が求められる。この例の場合、処理対象となるデータベースが２個であるので、データベースに対する処理ステップが２個含まれる。同図（ｂ）はあくまで一例であり、Ａ１で導出される処理手順は、問合せに応じたものになる。例えば、データベース１，２から取り出したデータを結合し、グループ化する場合には、同図（ｂ）に示したソート処理の代わりにグループ化処理を行う処理手順が導出される。
【００３３】
次に、問合せ解析手段11は、各データベースに対する処理ステップを、そのデータベースを構成する各部分データベースに対する処理ステップ（部分問合せ）に分割すると共に、同一データベースに対する部分問合せの集合毎に、部分問合せの結果をマージする処理ステップを追加する（Ａ２）。ここで、１つのデータベースに対する部分問合せの集合を部分問合せのセットと呼ぶこととする。処理対象となるデータベースが複数あった場合、各データベースについて部分問合せのセットが１つずつ作成される。例えば、図３（ｂ）に示すような処理手順から同図（ｃ）のような処理手順が作成される。この例では、１つの問合せで２つのデータベースを対象とするため、部分問合せの組が２セット作られている。また、１つの部分問合せのセットに含まれる部分問合せの数は、部分問合せがデータベースを構成する各データベース毎に作成されることから、対応するデータベースを構成する部分データベースの数と同じになる。
【００３４】
問合せ解析手段11において、問合せに対する処理手順が導出されると、問合せ統合処理手段14は、図４の流れ図に示すように、問合せ解析手段11から処理手順を入手して保存し、その処理手順中に部分問合せのセットが存在するか否かを判断する（Ｂ１，Ｂ２）。問合せ解析手段11から処理手順を入手した時点においては、部分問合せのセットが存在し、Ｂ２の判断結果がｙｅｓとなるので、問合せ統合処理手段14は、Ｂ３の処理を行う。
【００３５】
Ｂ３において、問合せ統合処理手段14は、処理手順に含まれている部分問合せのセット間の依存関係を解析し、配布可能な部分問合せを認識する。例えば、２つの部分問合せのセットが存在し、両者が処理の依存関係のない独立なセットになっている場合は、２つのセットに含まれる全ての部分問合せを配布可能な部分問合せとして認識する。また、例えば、２つの部分問合せのセットＳ１，Ｓ２が存在し、セットＳ２の処理にはセットＳ１の処理結果が必要になるという依存関係が存在する場合には、セットＳ１に含まれる部分問合せのみを配布可能な部分問合せとして認識する。
【００３６】
その後、問合せ統合処理手段14は、部分問合せ処理用の計算機ノード２−１〜２−ｎの内の、ノード番号「０」が付与されている計算機ノードを部分問合せの配布対象の計算機ノードとする（Ｂ４）。尚、本実施の形態では、計算機ノード２−１〜２−ｎにそれぞれノード番号「０」〜「ｎ−１」が付与されているものとする。
【００３７】
次に、問合せ統合処理手段14は、配布数決定手段13を用いてノード番号「０」の計算機ノード２−１への部分問合せの配布数を決定する（Ｂ６）。その際、各計算機ノード２−１〜２−ｎで処理中となる部分問合せの数が計算機ノード間で等しくなるように配布数を決定する。
【００３８】
このＢ６の処理を詳細に説明する。問合せ統合処理手段14は、計算機ノード２−１への部分問合せの配布数を決定する際、配布数決定手段13に対して配布対象にしている計算機ノード２−１のノード番号「０」を渡す。
【００３９】
配布数決定手段13は、問合せ統合処理手段14からノード番号「０」が渡されると（図５，Ｃ１）、進捗管理表を参照し、計算機ノード２−１から結果が返却されていない部分問合せの数（結果未返却数）を取得する（Ｃ２）。
【００４０】
進捗管理表は、各計算機ノード２−１〜２−ｎの結果未返却数および各計算機ノード２−１〜２−ｎから結果が返却されていない配布済みの部分問合せを管理するものであり、例えば、図６に示す構成を有する。この図６に示す進捗管理表には、部分問合せ処理用の計算機ノード２−１〜２−ｎのノード番号「０」〜「ｎ−１」に対応付けて、計算機ノード２−１〜２−ｎの結果未返却数と、計算機ノード２−１〜２−ｎから結果が返却されていない部分問合せのＩＤとが登録されている。尚、結果返却数，部分問合せＩＤは、問合せ統合処理手段14によって変更されるものである。
【００４１】
Ｃ２において、計算機ノード２−１の結果未返却数を取得すると、配布数決定手段13は、「結果未返却数＜目標配布数」なる条件が満たされているか否かを判断する（Ｃ３）。ここで、目標配布数は、各計算機ノード２−１〜２−ｎで処理中の、計算機ノード１−ｋからの部分問合せの個数を所定の個数に揃えるために計算機ノード１−ｋにおいて設定されている値であり、部分問合せの個数を例えば２個に揃える場合には、目標配布数は「２」となる。そして、Ｃ３において条件が満たされていると判断した場合（判断結果がｙｅｓ）は、「目標配布数−結果未返却数」なる演算を行って配布数を求め、求めた配布数を問合せ統合処理手段14に通知する（Ｃ４）。これに対して、条件が満たされていないと判断した場合（Ｃ３がｎｏ）は、配布数＝「０」を問合せ統合処理手段14に通知する（Ｃ５）。問合せ統合処理手段14は、配布数決定手段13から配布数が通知されると、その値を計算機ノード２−１に対する部分問合せの配布数と決定する。以上がＢ６で行う処理である。
【００４２】
そして、Ｂ６で決定した計算機ノード２−１に対する部分問合せの配布数が「０」よりも大きく、且つ未配布の配布可能な部分問合せが存在する場合（Ｂ７，Ｂ８が共にｙｅｓ）は、TCP,UDP/IPなどの汎用的な通信プロトコル、あるいは各種専用通信プロトコルを利用して、未配布の配布可能な部分問合せの内の１つを計算機ノード２−１へ配布すると共に、上記配布した部分問合せを配布可能と認識している部分問合せから除外し（Ｂ10）、更に、配布数を−１すると共に進捗管理表中の計算機ノード２−１についての管理情報を更新する（Ｂ11）。例えば、進捗管理表が図６に示す構成を有する場合は、ノード番号「０」に対応付けて登録されている計算機ノード２−１の結果未返却数を＋１すると共に、今回計算機ノード２−１に配布した部分問合せのＩＤをノード番号「０」に対応付けて登録する。問合せ統合処理手段14は、Ｂ６で決定した数の部分問合せを計算機ノード２−１に配布するか、或いは未配布の部分問合せが存在しなくまるまで（Ｂ７がｎｏとなるか、或いはＢ８がｎｏとなるまで）、上記した処理Ｂ７〜Ｂ11を繰り返し行う。
【００４３】
そして、Ｂ７或いはＢ８がｎｏとなると、問合せ統合処理手段14は、ノード番号を＋１し、計算機ノード２−２を部分問合せの配布対象の計算機ノードにする（Ｂ９）。以下、問合せ対象統合処理手段14は、「ノード番号＜ノード数」となるまで（Ｂ５がｎｏとなるまで）、上記した処理Ｂ５〜Ｂ１１を繰り返し行う。そして、Ｂ５の判断結果がｎｏとなると、問合せ統合処理手段14は、待ち状態となる。以上の処理により、計算機ノード１−ｋから各計算機ノード２−１〜２−ｎへ、目標配布数によって示される個数の部分問合せが配布される。但し、配布可能な部分問合せの数が、「目標配布数×計算機ノード２−１〜２−ｎの台数」よりも少ない場合は、計算機ノード２−１〜２−ｎの内の、一部の計算機ノードのみに目標配布数によって示される個数の部分問合せが配布されることになる。
【００４４】
一方、計算機ノード２−１〜２−ｎ内の部分問合せ処理手段21は、計算機ノード１−ｋから部分問合せが送られてくると、その部分問合せによって指示された部分データベース31から、部分問合せによって指定された条件を満たすデータを取り出し、取り出したデータを問合せ元の計算機ノード１−ｋに返却する。その際、処理した部分問合せのＩＤ及び自計算機ノードのノード番号も併せて返却する。
【００４５】
計算機ノード１−ｋ内の問合せ統合処理手段14は、計算機ノード２−ｉ（１≦ｉ≦ｎ）から部分問合せの結果，部分問合せのＩＤ及びノード番号が返却されると（図４，Ｂ13）、今回返却された結果により、結果を全て入手したことになる部分問合せのセットが存在するか否かを調べる（Ｂ14）。
【００４６】
そして、そのような部分問合せのセットが存在しないと判断した場合（Ｂ14がｎｏ）は、結果を返却した計算機ノード２−ｉのノード番号を取得し、配布数決定手段13により上記計算機ノード２−ｉへの部分問合せの配布数を決定する（Ｂ16, Ｂ17）。このＢ17の処理は、Ｂ６と同様の処理である。
【００４７】
計算機ノード２−ｉへの部分問合せの配布数を決定すると、問合せ統合処理手段14は、Ｂ17で決定した配布数の部分問合せを計算機ノード２−ｉに配布するか、或いは未配布の配布可能な部分問合せが存在しなくなるまで（Ｂ18がｎｏとなるか、或いはＢ19がｎｏとなるまで）、部分問合せを計算機ノード２−ｉに配布して配布した部分問合せを配布可能と認識している部分問合せから除外する処理（Ｂ20）と、配布数を−１し進捗管理表を更新する処理（Ｂ21）を繰り返し行う。ここで、例えば、進捗管理表が図６に示す構成を有する場合には、計算機ノード２−ｉのノード番号「ｉ−１」に対応付けて登録されている結果未返却数を−１する処理およびノード番号「ｉ−１」に対応付けて登録されている部分問合せのＩＤの内の、計算機２−ｉから返却されたＩＤを削除する処理を行う。Ｂ18或いはＢ19の判断結果がｎｏとなった場合は、問合せ統合処理手段14は待ち状態になる。
【００４８】
また、Ｂ14において、今回返却された結果により、結果を全て入手したことになる部分問合せのセットが存在すると判断した場合（判断結果がｙｅｓ）は、保存してある処理手順から、結果を全て入手した部分問合せのセットを除去し（Ｂ15）、その後、Ｂ２の処理を行う。
【００４９】
そして、Ｂ２において、保存してある処理手順中に部分問合せのセットが存在すると判断した場合（判断結果がｙｅｓ）は、Ｂ３の処理を行い、部分問合せのセットが存在しないと判断した場合（判断結果がｎｏ）は、部分問合せよりルート側の処理をルートに向かって順次行い、問合せに対する結果を外部通信網５を介して問合せ元に返却する（Ｂ１２）。例えば、Ｂ１で入手した処理手順が図３（ｃ）に示すものである場合は、図７に示すように、２つの部分問合せのセットについて結果を全て入手したら、各部分問合せのセットについて結果をマージする処理を行い、更に、マージ結果を結合する処理，結合結果をソートする処理を順次行う。尚、本実施の形態では、部分問合せの結果を全て入手してからマージを行うようにしたが、結果が返却される毎に１つずつマージしていく方法もある。例えば、平均値や合計値などを、問合せに対する結果として求める場合、部分問合せの結果が戻る度にセット毎に結果を足し込んでいく。これにより、処理手順の各ステップをパイプライン的に処理していくことになる。
【００５０】
以上のように、問合せ統合処理手段14は、問合せ解析手段11から処理手順を入手した場合（図４，Ｂ１）、予め定められている目標配布数の部分問合せを各計算機ノード２−１〜２−ｎに配布し（Ｂ５〜Ｂ11）、残った部分問合せは、未配布としておく。未配布となった部分問合せは、後に、部分問合せの結果を早く返却してきた計算機ノードに投げる（Ｂ16〜Ｂ21）。つまり、部分問合せの処理が早く終わって負荷の軽くなった計算機ノードに未配布の部分問合せを配布することになる。
【００５１】
以上によって各計算機ノード２−１〜２−ｎで処理中の部分問合せの個数は、ある一定個数以下に保たれる。従って、多数の部分問合せが発生するような状況では、各計算機ノードで処理中の部分問合せの個数は、常にある一定個数に保たれる。これによって各計算機ノードの負荷が均衡化される。
【００５２】
次に、各計算機ノード２−１〜２−ｎで独立に動作する部分問合せ処理手段21の実施例を図８に示す。図８（ａ）に示す実施例では、配布された部分問合せを溜めておくキューを持ち、そこから１つずつ部分問合せ処理部に取り出して順番に処理する。処理された部分問合せの結果は、部分問合せ処理部から配布元の計算機ノードに返却する。
【００５３】
これに対し、図８（ｂ）は、複数の部分問合せを多重的に処理する実施例を示す。マルチスレッドもしくは、マルチプロセスを利用することにより、部分問合せ処理部を複数同時に動作させ、配布された各部分問合せを各部分問合せ処理部に割り付ける。各部分問合せ処理部は、計算機ノードのOSのスケジューリングに従い、多重的に動作する。例えば、部分問合せ処理部が、部分データベースを一定サイズのブロック単位で二次記憶装置３−１〜３−ｊから読み出す処理と、読み出したブロックのデータに対し検索・演算を施す処理で構成される場合、複数の部分問合せ処理部は、互いに二次記憶装置３−１〜３−ｊの入出力処理と計算機ノードにおけるCPU 処理とが時間的に重ねられて処理される。
【００５４】
部分問合せ処理手段21は、図８（ａ）におけるキューを図８（ｂ）に組み合わせたものも考えられる。
【００５５】
次に、部分問合せ処理用の計算機ノード２−１〜２−ｎに障害が発生した場合の動作を説明する。
【００５６】
問合せ処理用の計算機ノード１−ｋ内の障害検出手段12は、部分問合せ処理用の計算機ノード２−１〜２−ｎに障害が発生したことを検出するために、図９に流れ図に示すように、各計算機ノード２−１〜２−ｎの状態を監視している（Ｄ１）。この監視は、例えば、通信網４を介して各計算機ノード２−１〜２−ｎと定期的に小さなデータを交換することにより行う。つまり、データ交換を正常に行うことができた場合は、障害が発生していないと判断し、データ交換が不能になった場合は、障害が発生していると判断する。また、計算機ノード２−１〜２−ｎにハードウェアによって構成される専用の障害診断機構を設け、障害が発生した場合、計算機２−１〜２−ｎの障害診断機構が通信網４を介して障害発生を計算機ノード１−１〜１−ｎに通知するようにしても良い。
【００５７】
計算機ノード１−ｋ内の障害検出手段12は、例えば、計算機ノード２−１に障害が発生したことを検出すると、先ず、計算機ノード２−１のノード番号「０」を入手する（Ｄ２）。その後、障害検出手段12は、進捗管理表からノード番号「０」の計算機ノード２−１に配布済みの部分問合せであって、結果が返却されていない部分問合せのＩＤを取得し（Ｄ３）、更に、進捗管理表から障害の発生した計算機ノードのノード番号「０」の行を削除し、計算機ノード２−１を部分問合せの配布対象から除外する（Ｄ４）。例えば、進捗管理表の内容が図６に示すものであった場合、障害検出手段12は、部分問合せのＩＤとして「ＩＤ１，ＩＤ２」を取得し（Ｄ３）、進捗管理表の第１行目を削除する（Ｄ４）。その後、障害検出手段13は、問合せ統合処理手段14に対してＤ３で取得した部分問合せのＩＤを通知する（Ｄ５）。尚、図９の流れ図では、進捗管理表から障害の発生した計算機ノードのノード番号の行を削除することにより、障害の発生した計算機ノードを部分問合せの配布対象から除外するようにしたが、除外を示すマークを付けるような方法をとることもできる。
【００５８】
問合せ統合処理手段14は、障害検出手段12から部分問合せのＩＤが通知されると、その部分問合せを未配布の部分問合せとして認識する。このように、障害の発生した計算機ノードに配布済みの部分問合せであって、結果が返却されていない部分問合せを未配布の部分問合せとして認識することにより、図４のＢ２０においてそれらが障害の発生していない部分問合せ処理用の計算機ノードの何れかに配布される。二次記憶装置３−１〜３−ｊが記憶装置共有網６で接続された共有型クラスタシステムでは、各計算機ノード２−１〜２−ｎは、記憶装置共有網６を介して何れの部分データベース31にもアクセス可能なので、ある計算機ノードに配布することになっていた部分問合せを別の計算機ノードでも処理できる。従って、障害の起きている計算機ノードに配布している部分問合せを他の正常な計算機ノードに配布することによって、全ての部分問合せを処理することができる。
【００５９】
次に、本発明の第２の実施の形態の例について説明する。第２の実施の形態は、複数の計算機ノードそれぞれにその計算機ノードだけがアクセスできる二次記憶装置が接続された無共有型クラスタシステムの上で、二次記憶装置に記録されたデータベースに対する問合せを並列に処理する問合せ並列処理システムに関するもので、その構成例を図１０に示す。
【００６０】
本実施の形態と図１に示した第１の実施の形態との相違点は、計算機ノード１−１〜１−ｍの代わりに計算機ノード10−１〜10−ｍを備えた点と、記憶装置共有網がなく各計算機ノード２−１〜２−ｎのそれぞれに二次記憶装置30−１〜30−ｎが直接接続されている点と、記録媒体Ｋ１の代わりに記録媒体Ｋ３を備えている点である。
【００６１】
問合せの対象となるデータベースは、複数の部分データベース31に分割され、複数の二次記憶装置30−１〜30−ｎに分散して格納される。更に、各部分データベースの複製が、原本と異なる二次記憶装置に分散して格納される。
【００６２】
計算機ノード10−１〜10−ｍは、問合せ統合処理手段14の代わりに問合せ統合処理手段14ａを備えている点と、格納状況管理手段15を備えている点が図１に示した計算機ノード１−１〜１−ｍと相違している。
【００６３】
格納状況管理手段15は、部分問合せ処理用の計算機ノード２−１〜２−ｎがアクセス可能な部分データベースのＩＤを管理し、問合せ統合処理手段14ａから計算機ノード２−１〜２−ｎのノード番号が通知された場合、通知されたノード番号の計算機ノードがアクセス可能な部分データベースのＩＤのリストを返却する機能を有する。各計算機ノード２−１〜２−ｎがアクセス可能な部分データベース31のＩＤの管理は、例えば、図１１に示すような格納状況管理表を使用して行う。格納状況管理表には、計算機ノード２−１〜２−ｎのノード番号「０」〜「ｎ−１」に対応付けてそのノード番号の計算機ノードがアクセス可能な部分データベースのＩＤが登録されている。図１１の例は、ノード番号「０」の計算機ノード２−１は、ＩＤ「Ａ−０，Ａ−４，Ａ−８，Ｂ−１，Ｂ−５，…」によって示される部分データベースの原本と、ＩＤ「Ａ−２，Ａ−６，Ａ−10，Ｂ−０，Ｂ−４，…」によって示される部分データベースの複製をアクセスできること示している。この複製は、ノード番号「１」の計算機ノード２−２がアクセスできる部分データベースの原本の複製である。また、部分データベースのＩＤは、Ａ，Ｂ等のデータベースのＩＤと、その中での部分データベースの順番とを組み合わせたものになっている。
【００６４】
問合せ統合処理手段14ａは、図１に示した問合せ統合処理手段14が備えている機能に加え、格納状況管理手段15に部分問合せ処理用の計算機ノードのノード番号を通知する機能や、この通知に応答して格納状況管理手段15から返却された部分データベースのＩＤのリストに基づいて配布する部分問合せを決定する機能を備えている。
【００６５】
記録媒体Ｋ３は、ディスク，半導体メモリ，その他の記録媒体であり、計算機ノード10−１〜10−ｍを問合せ処理用の計算機ノードとして機能させるためのプログラムが記録されている。このプログラムは、計算機ノード10−１〜10−ｍによって読み取られ、計算機ノード10−１〜10−ｍの動作を制御することで、計算機ノード10−１〜10−ｍ上に、問合せ解析手段11，障害検出手段12，配布数決定手段13，問合せ統合処理手段14ａ，格納状況管理手段15を実現する。
【００６６】
図１２は、問合せ統合処理手段14ａで行われる処理の内の、図１の問合せ統合処理手段14で行われる処理と異なる部分のみを示した流れ図であり、ステップＢ７，Ｂ８の間およびステップＢ18，Ｂ19の間でそれぞれステップＥ１，Ｅ２を行う点、およびステップＢ10，Ｂ20の代わりにステップＥ３，Ｅ４を行う点が図４に示した処理と異なっている。また、図１３は格納状況管理手段15の処理例を示す流れ図である。以下、各図を参照して本実施の形態の動作を説明する。
【００６７】
問合せ処理用の計算機ノード１０−ｋ内の問合せ解析手段11は、外部通信網５を介して自計算機ノード宛の問合せを受け付けると、図２のＡ１，Ａ２に示す処理を行い、図３（ｃ）に示すような処理手順を導出する。
【００６８】
問合せ統合処理手段14ａは、問合せ解析手段11が処理手順を導出すると、図４のＢ１〜Ｂ７と同様の処理を行い、ノード番号「０」の計算機ノード２−１へ配布する部分問合せの数を決定する。その後、問合せ統合処理手段14ａは、図１２の流れ図に示すように、格納状況管理手段15を利用して計算機ノード２−１へ配布する部分問い合わせを１個決定する（Ｅ１）。このＥ１の処理を詳しく説明すると、次のようになる。
【００６９】
問合せ統合処理手段14ａは、部分問合せの配布対象にしている計算機ノード２−１のノード番号「０」を格納状況管理手段15に通知する。
【００７０】
ノード番号「０」が通知されると、格納状況管理手段15は、図１３に示すように格納状況管理表を参照し、ノード番号「０」の計算機ノード２−１がアクセス可能な部分データベースのＩＤのリストを取得し（Ｆ１）、取得したリストを問合せ統合処理手段14ａに返却する（Ｆ２）。
【００７１】
問合せ統合処理手段14ａは、リストが返却されると、配布可能と認識している部分問合せであって、且つ上記リストにＩＤが登録されている部分データベースに対する部分問合せの内の１つを選択し、それを配布する部分問合せとする。尚、そのような部分問合せが存在しない場合は、配布可能な部分問合せがないと判断する。以上が、Ｅ１で行う処理の詳細である。
【００７２】
Ｅ１で配布する部分問合せが決定され、Ｂ８の判断結果がｙｅｓとなると、問合せ統合処理手段14ａは、Ｅ１で決定した部分問合せを計算機ノード２−１に配布すると共に、配布した部分問合せを配布可能と認識している部分問合せから除外する（Ｅ３）。その後、図４に示したＢ11と同様の処理が行われる。
【００７３】
また、部分問合せ処理用の計算機ノード２−ｉから部分問合せの結果が送られてきた場合は、図４のＢ13〜Ｂ18と同様の処理を行い、計算機ノード２−ｉに配布する部分問合せの数を決定する。その後、問合せ統合処理手段14ａは、格納状況管理手段15を使用して計算機ノード２−ｉに配布する部分問合せを１個決定し（Ｅ２）、その部分問合せを計算機ノード２−ｉに配布すると共に、配布した部分問合せを配布可能と認識している部分問合せから除外する（Ｅ４）。その後、図４に示したＢ21と同様の処理が行われる。
【００７４】
次に、障害検出手段12によって計算機ノード２−ｉに障害が発生したことが検出された時の動作を説明する。
【００７５】
障害検出手段12は、図９の流れ図に示すように、計算機ノード２−ｉに障害が発生したことを検出すると、計算機ノード２−ｉに配布済みで、且つ結果が返却されていない部分問合せのＩＤを進捗管理表から取得し、それを問合せ統合処理手段14ａに通知する。問合せ統合処理手段14ａは、ＩＤが通知された部分問合せを未配布の部分問合せとして認識する。このように、障害の発生した計算機ノードに配布済みの部分問合せであって、結果が返却されていない部分問合せを未配布の部分問合せとして認識することにより、図１２のＥ４において上記した部分問合せが、正常に動作している部分問合せ処理用の計算機ノードであって、且つ上記した部分問合せに対応する部分データベースをアクセス可能な計算機ノードに配布される。
【００７６】
【発明の効果】
以上説明したように、本発明の問合せ並列処理システムは、複数の部分問合せ処理用の計算機ノードから構成されるクラスタシステム上で問合せを並列処理する際、各計算機ノードの負荷に応じて動的に配布すべき部分問合せの数を決定するようにしているので、各計算機ノードの負荷を動的に均衡化させることができる。その結果、問合せ並列処理システム全体の処理効率を高め、性能改善を図ることが可能になる。
【００７７】
また、本発明の問合せ並列処理システムは、部分問合せ処理用の計算機ノードに障害が発生した場合、障害が発生した計算機以外の計算機ノードについて、その負荷に応じて動的に配布すべき部分問合せの数を決定するようにしているので、部分問合せ処理用の計算機ノードに障害が発生した場合であっても、問合せの結果を完全なものにすることができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態の構成例を示すブロック図である。
【図２】問合せ解析手段11の処理例を示す流れ図である。
【図３】問合せ解析手段11の動作を説明するための図である。
【図４】問合せ統合処理手段14の処理例を示す流れ図である。
【図５】配布数決定手段13の処理例を示す流れ図である。
【図６】進捗管理表の構成例を示す図である。
【図７】問合せ統合処理手段14の処理例を示す流れ図である。
【図８】部分問合せ処理手段21の実施例を示すブロック図である。
【図９】障害検出手段12の処理例を示す流れ図である。
【図１０】本発明の第２の実施の形態の構成例を示すブロック図である。
【図１１】格納状況管理表の構成例を示す図である。
【図１２】問合せ統合処理手段14ａの処理例の一部を示す流れ図である。
【図１３】格納状況管理手段15の処理例を示す流れ図である。
【符号の説明】
１−１〜１−ｍ，10−１〜１０−ｍ…問合せ処理用の計算機ノード
11…問合せ解析手段
12…障害検出手段
13…配布数決定手段
14，14ａ…問合せ統合処理手段
15…格納状況管理手段
２−１〜２−ｎ…部分問合せ処理用の計算機ノード
21…部分問合せ処理手段
３−１〜３−ｊ，30−１〜30−ｎ…二次記憶装置
31…部分データベース
４…通信網
５…外部通信網
６…記憶装置共有網
Ｋ１〜Ｋ３…記録媒体

Claims (14)

1. データベースを複数の部分に分割することによって作成された複数の部分データベースが分散して格納された複数の二次記憶装置を、複数の部分問合せ処理用の計算機ノードが共有する共有型クラスタシステムの上で、前記データベースに対する問合せを並列に処理する問合せ並列処理システムであって、
   前記データベースに対する問合せを受け付ける１台の問合せ処理用の計算機ノードを備え、
   該問合せ処理用の計算機ノードが、
   前記データベースに対する問合せを解析し、この問合せを処理する手順であって、問合せ対象となるデータベースを構成する各部分データベースに対する部分問合せと、部分問合せの結果のマージ処理とを含む処理手順を導出する問合せ解析手段と、
   前記各部分問合せ処理用の計算機ノードについて、その負荷に応じて動的に配布すべき部分問合せの数を決定する配布数決定手段と、
   前記問合せ解析手段で導出した処理手順に従って問合せの処理を進め、各部分問合せ処理用の計算機ノードに対し部分問合せを配布する際には、前記配布数決定手段を用いて決定した配布数だけの未配布の部分問合せを配布し、部分問合せの結果が返却された際には、関連する結果をマージしながら問合せの結果を導出する問合せ統合処理手段とを備え、
   前記複数の部分問合せ処理用の計算機ノードが、それぞれ、
   配布された部分問合せを受け、その部分問合せの処理を行い、配布元の計算機ノードに結果を返す部分問合せ処理手段を備えたことを特徴とする問合せ並列処理システム。
2. 請求項１記載の問合せ並列処理システムにおいて、
   前記配布数決定手段は、前記各部分問合せ処理用の計算機ノードで処理中となっている部分問合せの数がそれぞれ所定数となるように、部分問合せの配布数を決定する構成を有することを特徴とする問合せ並列処理システム。
3. 請求項１記載の問合せ並列処理システムにおいて、
   前記問合せ処理用の計算機ノードを複数備えたことを特徴とする問合せ並列処理システム。
4. データベースを複数の部分に分割することによって作成された複数の部分データベースが分散して格納された複数の二次記憶装置を、複数の部分問合せ処理用の計算機ノードが共有する共有型クラスタシステムの上で、前記データベースに対する問合せを並列に処理する問合せ並列処理システムであって、
   前記データベースに対する問合せを受け付ける１台の問合せ処理用の計算機ノードを備え、
   該問合せ処理用の計算機ノードが、
   前記データベースに対する問合せを解析し、この問合せを処理する手順であって、問合せ対象となるデータベースを構成する各部分データベースに対する部分問合せと、部分問合せの結果のマージ処理とを含む処理手順を導出する問合せ解析手段と、
   前記部分問合せ処理用の計算機ノードに障害が発生したことを検出する障害検出手段と、
   前記部分問合せ処理用の計算機ノードの内の、前記障害検出手段で障害発生が検出された計算機ノード以外の計算機ノードについて、その負荷に応じて動的に配布すべき部分問合せの数を決定する配布数決定手段と、
   前記問合せ解析手段で導出した処理手順に従って問合せの処理を進め、各部分問合せ処理用の計算機ノードに対し部分問合せを配布する際には、前記配布数決定手段を用いて決定した配布数だけの未配布の部分問合せを配布し、部分問合せの結果が返却された際には、関連する結果をマージしながら問合せの結果を導出する問合せ統合処理手段とを備え、
   前記複数の部分問合せ処理用の計算機ノードが、それぞれ、
   配布された部分問合せを受け、その部分問合せの処理を行い、配布元の計算機ノードに結果を返す部分問合せ処理手段を備えたことを特徴とする問合せ並列処理システム。
5. 請求項４記載の問合せ並列処理システムにおいて、
   前記配布数決定手段は、前記部分問合せ処理用の計算機ノードの内の、前記障害検出手段で障害発生が検出された計算機ノード以外の計算機ノードで処理中になっている部分問合せの数がそれぞれ所定数となるように、部分問合せの配布数を決定する構成を有することを特徴とする問合せ並列処理システム。
6. 請求項４記載の問合せ並列処理システムにおいて、
   前記問合せ処理用の計算機ノードを複数備えたことを特徴とする問合せ並列処理システム。
7. 複数の部分問合せ処理用の計算機ノードそれぞれにその計算機ノードだけがアクセスできる二次記憶装置が接続され、データベースを複数の部分に分割することによって作成された複数の部分データベースが前記複数の二次記憶装置に分散して格納された無共有型クラスタシステムの上で、前記データベースに対する問合せを並列に処理する問合せ並列処理システムであって、
   前記データベースに対する問合せを受け付ける１台の問合せ処理用の計算機ノードを備え、
   該問合せ処理用の計算機ノードが、
   前記データベースに対する問合せを解析し、この問合せを処理する手順であって、問合せ対象となるデータベースを構成する各部分データベースに対する部分問合せと、部分問合せの結果のマージ処理とを含む処理手順を導出する問合せ解析手段と、
   前記各部分問合せ処理用の計算機ノードと、その計算機ノードからアクセス可能な部分データベースとの対応関係を管理する格納状況管理手段と、
   前記各部分問合せ処理用の計算機ノードについて、その負荷に応じて動的に配布すべき部分問合せの数を決定する配布数決定手段と、
   前記問合せ解析手段で導出した処理手順に従って問合せの処理を進め、部分問合せ処理用の計算機ノードに対し部分問合せを配布する際には、その計算機ノードがアクセス可能な部分データベースの全てを前記格納状況管理手段を用いて認識し、それら部分データベースに対する部分問合せの中から、前記配布数決定手段を用いて決定した配布数だけの未配布の部分問合せを配布し、部分問合せの結果が返却された際には、関連する結果をマージしながら問合せの結果を導出する問合せ統合処理手段とを備え、
   前記各部分問合せ処理用の計算機ノードが、それぞれ、
   配布された部分問合せを受け、その部分問合せの処理を行い、配布元の計算機ノードに結果を返す部分問合せ処理手段を備えたことを特徴とする問合せ並列処理システム。
8. 請求項７記載の問合せ並列処理システムにおいて、
   前記配布数決定手段は、前記各部分問合せ処理用の計算機ノードで処理中の部分問合せの数がそれぞれ所定数となるように、部分問合せの配布数を決定する構成を有することを特徴とする問合せ並列処理システム。
9. 請求項７記載の問合せ並列処理システムにおいて、
   前記問合せ処理用の計算機ノードを複数備えたことを特徴とする問合せ並列処理システム。
10. 複数の部分問合せ処理用の計算機ノードそれぞれにその計算機ノードだけがアクセスできる二次記憶装置が接続され、データベースを複数の部分に分割することによって作成された複数の部分データベースが前記複数の二次記憶装置に分散して格納され、更に前記各部分データベースの複製がその原本とは異なる二次記憶装置に格納された無共有型クラスタシステムの上で、前記データベースに対する問合せを並列に処理する問合せ並列処理システムであって、
    前記データベースに対する問合せを受け付ける１台の問合せ処理用の計算機ノードを備え、
    該問合せ処理用の計算機ノードが、
    前記データベースに対する問合せを解析し、この問合せを処理する手順であって、問合せ対象となるデータベースを構成する各部分データベースに対する部分問合せと、部分問合せの結果のマージ処理とを含む処理手順を導出する問合せ解析手段と、
    前記部分問合せ処理用の計算機ノードに障害が発生したことを検出する障害検出手段と、
    前記部分問合せ処理用の計算機ノードの内の、前記障害検出手段で障害発生が検出された計算機ノード以外の計算機ノードについて、その負荷に応じて動的に配布すべき部分問合せの数を決定する配布数決定手段と、
    前記各部分問合せ処理用の計算機ノードと、その計算機ノードからアクセス可能な部分データベースの原本，複製との対応関係を管理する格納状況管理手段と、
    前記問合せ解析手段で導出した処理手順に従って問合せの処理を進め、部分問合せ処理用の計算機ノードに対し部分問合せを配布する際には、その計算機ノードがアクセス可能な部分データベースの全てを前記格納状況管理手段を用いて認識し、それら部分データベースに対する部分問合せの中から、前記配布数決定手段を用いて決定した配布数だけの未配布の部分問合せを配布し、部分問合せの結果が返却された際には、関連する結果をマージしながら問合せの結果を導出する問合せ統合処理手段とを備え、
    前記部分問合せ処理用の計算機ノードが、それぞれ、
    配布された部分問合せを受け、その部分問合せの処理を行い、配布元の計算機ノードに結果を返す部分問合せ処理手段を備えたことを特徴とする問合せ並列処理システム。
11. 請求項１０記載の問合せ並列処理システムにおいて、
    前記配布数決定手段は、前記各部分問合せ処理用の計算機ノードの内の、前記障害検出手段によって障害発生が検出された計算機ノード以外の計算機ノードで処理中の部分問合せの数がそれぞれ所定数となるように、部分問合せの配布数を決定する構成を有することを特徴とする問合せ並列処理システム。
12. 請求項１０記載の問合せ並列処理システムにおいて、
    前記問合せ処理用の計算機ノードを複数備えたことを特徴とする問合せ並列処理システム。
13. データベースを複数の部分に分割することによって作成された複数の部分データベースが分散して格納された複数の二次記憶装置を、複数の部分問合せ処理用の計算機ノードが共有する共有型クラスタシステムの上で、前記データベースに対する問合せを並列に処理する問合せ並列処理システムを、複数台の部分問合せ処理用の計算機ノードと１台の問合せ処理用の計算機ノードとによって実現するためのプログラムを記録した機械読み取り可能な記録媒体であって、
    前記問合せ処理用の計算機ノードを、
    前記データベースに対する問合せを解析し、この問合せを処理する手順であって、問合せ対象となるデータベースを構成する各部分データベースに対する部分問合せと、部分問合せの結果のマージ処理とを含む処理手順を導出する問合せ解析手段、
    前記各部分問合せ処理用の計算機ノードについて、その負荷に応じて動的に配布すべき部分問合せの数を決定する配布数決定手段、
    前記問合せ解析手段で導出した処理手順に従って問合せの処理を進め、各部分問合せ処理用の計算機ノードに対し部分問合せを配布する際には、前記配布数決定手段を用いて決定した配布数だけの未配布の部分問合せを配布し、部分問合せの結果が返却された際には、関連する結果をマージしながら問合せの結果を導出する問合せ統合処理手段として機能させるためのプログラムと、
    前記各部分問合せ処理用の計算機ノードを、
    配布された部分問合せを受け、その部分問合せの処理を行い、配布元の計算機ノードに結果を返す部分問合せ処理手段として機能させるためのプログラムとを記録した、プログラムを記録した機械読み取り可能な記録媒体。
14. 複数の部分問合せ処理用の計算機ノードそれぞれにその計算機ノードだけがアクセスできる二次記憶装置が接続され、データベースを複数の部分に分割することによって作成された複数の部分データベースが前記複数の二次記憶装置に分散して格納された無共有型クラスタシステムの上で、前記データベースに対する問合せを並列に処理する問合せ並列処理システムを、複数の部分問合せ処理用の計算機ノードと１台の問合せ処理用の計算機ノードとによって実現するためのプログラムを記録した機械読み取り可能な記録媒体であって、
    前記問合せ処理用の計算機ノードを、
    前記データベースに対する問合せを解析し、この問合せを処理する手順であって、問合せ対象となるデータベースを構成する各部分データベースに対する部分問合せと、部分問合せの結果のマージ処理とを含む処理手順を導出する問合せ解析手段、
    前記各部分問合せ処理用の計算機ノードと、その計算機ノードからアクセス可能な部分データベースとの対応関係を管理する格納状況管理手段、
    前記各部分問合せ処理用の計算機ノードについて、その負荷に応じて配布するべき部分問合せの数を決定する配布数決定手段、
    前記問合せ解析手段で導出した処理手順に従って問合せの処理を進め、各部分問合せ処理用の計算機ノードに対し部分問合せを配布する際には、各計算機ノードがアクセス可能な部分データベースの全てを前記格納状況管理手段を用いて認識し、それら部分データベースに対する部分問合せの中から、前記配布数決定手段を用いて決定した配布数だけの未配布の部分問合せを配布し、部分問合せの結果が返却された際には、関連する結果をマージしながら問合せの結果を導出する問合せ統合処理手段として機能させるためのプログラムと、
    前記各部分問合せ処理用の計算機ノードを、
    配布された部分問合せを受け、その部分問合せの処理を行い、配布元の計算機ノードに結果を返す部分問合せ処理手段として機能させるためのプログラムとを記録した、プログラムを記録した機械読み取り可能な記録媒体。

Images