(57)【特許請求の範囲】
【請求項１】
データを記憶するデータベースを有する複数のスレーブサーバと、前記データベースの管理情報を記憶し、問合せクエリに基づいて前記データを検索するマスターサーバとが接続される分散データベース検索装置の検索方法であって、
前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成するステップと、
前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加するステップと、
当該分散プランから、前記スレーブサーバに関連するプランを抽出するステップと、
前記抽出されたプランに含まれる前記分割クエリ結合演算及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成するステップと、
生成された前記ローカルプラン候補に含まれる前記分割クエリ結合演算及び分割クエリ結合演算に関連するデータの送受信演算を変更した新たなローカルプラン候補を生成するステップと、
生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択するステップと、
前記選択されたローカルプランに基づいて、前記分散プランを更新するステップと、
を備える検索方法。
【請求項２】
データを記憶するデータベースを有する複数のスレーブサーバと、問合せクエリに基づいて前記データベースを検索するマスターサーバとが接続される分散データベース検索装置であって、
前記マスターサーバは、
前記スレーブサーバの有する各データベースの管理情報を記憶する記憶部と、
前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成する分散プラン生成部と、
前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加する分割クエリ結合演算追加部と、
前記スレーブサーバから受信したローカルプランに基づいて、前記分散プランを更新する分散プラン更新部と、
を具備し、
前記スレーブサーバは、
前記分散プランから、前記スレーブサーバに関連するプランを抽出し、前記抽出したプランに含まれる前記分割クエリ結合演算及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成するローカルプラン候補生成部と、
生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択するローカルプラン選択部と、
を備える分散データベース検索装置。
【請求項３】
前記サーバ間演算において、送受信されるデータのカラムが前記マスターサーバと前記スレーブサーバとで異なる場合、前記カラムを可変長のデータが記憶されたカラムとするスキーマ変更部を備える請求項２に記載の分散データベース検索装置。
【請求項４】
データを記憶するデータベースを有する複数のスレーブサーバと接続され、入力された問合せクエリに基づいて前記データベースを検索する分散データベース装置を構成するマスターサーバであって、
前記スレーブサーバの有する各データベースの管理情報を記憶する記憶部と、
前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成する分散プラン生成部と、
前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加する分割クエリ結合演算追加部と、
前記分散プランに基づいて演算コストが最小となるように選択されたローカルプランを前記スレーブサーバから受信し、受信したローカルプランに基づいて、前記分散プランを更新する分散プラン更新部と、
を備えるマスターサーバ。
【請求項５】
データベースを具備し、入力された問合せクエリに基づいて前記データベースを検索するマスターサーバと複数接続されて分散データベース検索システムを構成するスレーブサーバであって、
マスターサーバから受信した分散プランから、前記スレーブサーバに関連するプランを抽出し、前記抽出したプランに含まれる分割クエリ結合演算及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成するローカルプラン候補生成部と、
生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択するローカルプラン選択部と、
を備えるスレーブサーバ。
【請求項６】
前記ローカルプラン選択部が算出する前記ローカルプラン候補の演算コストに、前記マスターサーバによって追加された分割クエリ結合演算の演算コストも含める請求項５に記載のスレーブサーバ。
【請求項７】
データを記憶するデータベースを有する複数のスレーブサーバと、前記データベースの管理情報を記憶し、問合せクエリに基づいて前記データを検索するマスターサーバとが接続される分散データベース検索装置のプログラムであって、
コンピュータに、
前記スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、前記サーバ内演算及び前記複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、前記問合せクエリに基づいて生成する機能と、
前記分散プランに、前記サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果と前記サーバ間演算処理の結果とを共に必要とする演算が存在する場合は、前記サーバ間演算処理と並列に実行可能な演算と、前記サーバ間演算とを並列に実行するとともに、前記サーバ間演算処理と並列に実行可能な演算によって得られたデータおよび前記サーバ間演算によって得られたデータを結合する分割クエリ結合演算を前記分散プランに追加する機能と、
前記スレーブサーバから受信したローカルプランに基づいて、前記分散プランを更新する機能と、
前記分散プランから、前記スレーブサーバに関連するプランを抽出し、前記抽出したプランに含まれる前記分割クエリ結合演算及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成する機能と、
生成された前記ローカルプラン候補および前記抽出したプランそれぞれの演算コストを算出し、前記演算コストが最小となるプランをローカルプランとして選択する機能と、
を実現させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、分散データベース検索装置、分散データベース検索方法、及びプログラムに関する。
【背景技術】
【０００２】
表形式やＸＭＬ形式等の大量のデータを扱うために複数のサーバで構成された分散データベース検索装置が存在する。分散データベース検索装置は通常、ユーザとのやり取りを行うマスターサーバと、実際にデータを管理するスレーブサーバとから構成されている。
【０００３】
スレーブサーバは全て同一のアーキテクチャのデータベース検索装置から構成されていることもあれば、異なるアーキテクチャのデータベース検索装置から構成されていることもある。
【０００４】
一般に、分散データベース検索装置に対して検索式（以下、クエリという）が入力された場合、クエリはマスターサーバが受け取る。マスターサーバはクエリを解析して、各スレーブサーバがサーバ内部で実行する部分と、サーバ間で演算する必要がある部分に分割する。各スレーブサーバ内で実行する部分は各スレーブサーバが最適なローカルプランを生成する。サーバ間の演算部分はマスターサーバが最適な分散プランを生成する。なお、ローカルプランとはスレーブサーバがスレーブサーバの有するデータを検索するためのプランであり、分散プランとは対象の分散データベースの有するデータ全体を検索するためのプランである。
【０００５】
分散プランを生成する際は、ＪＯＩＮ等のサーバ間のデータに対する結合演算処理、ＳＯＲＴ等の複数のサーバに対する集合演算処理、分割した部分クエリの結合演算処理等の演算処理の順序と実行するサーバを検索応答時間が最短になるように決定する。さらに演算を実行するサーバへのデータ転送方法やフォーマット等を決定する。
【０００６】
分散データベースでは、検索性能を向上するために分散プランの最適化を強化することで、それらデータベース間でのデータ受け渡し処理におけるデータの転送コストや、サーバ間のデータの演算コストを低減したいという要望がある。
【０００７】
従来、分散プランの最適化は全てマスターサーバによって実現されてきた。しかしながら、マスターサーバが分散プランの全てを決定することには多くの問題がある。
【０００８】
まず、分散プランの検討範囲は上記で挙げたようにクエリの分割範囲、サーバ間演算の順序と実行場所の決定、分割したクエリの結合方法等と非常に広いため、多くの候補プランが発生してしまい、その中から最適なプランを検索するためには多くの情報を必要とする。このためマスターサーバは各スレーブサーバ側からの索引や統計情報等を密に取得して維持・管理する必要がある。したがってマスターサーバの仕組みは複雑であり、管理コストが多くかかる。
【０００９】
また、マスターサーバが欲しい情報を全て取得した場合でも、スレーブサーバ毎に統計量が大きく異なった場合や、アーキテクチャが異なる場合はスレーブサーバ毎に最適な動作が異なる可能性がある。そのようなケースにおいて全てのスレーブサーバに対して統一した分散プランでは一部のスレーブサーバの実行速度がボトルネックとなり全体の性能が低下する可能性がある。しかしながら、スレーブサーバ毎に最適な動作ができるような分散プランを生成するとマスターサーバの分散プラン生成の仕組みが複雑になる。すなわち、マスターサーバの分散プラン処理部の最適化機能を向上させると、マスターサーバの最適化の仕組みは複雑化する。このため、マスターサーバが各スレーブサーバの状態毎に適した形で分散プランを生成することは困難である。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００１−３３１４８５号公報
【特許文献２】特開平０７−１４１３９９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明が解決しようとする課題は、マスターサーバ側の仕組みを複雑化することなく効率的な検索を実現する分散データベース検索装置を提供することである。
【課題を解決するための手段】
【００１２】
実施形態の分散データベース検索装置は、データを記憶するデータベースを有する複数のスレーブサーバと、問合せクエリに基づいてデータベースを検索するマスターサーバとが接続される。マスターサーバは、スレーブサーバの有する各データベースの管理情報を記憶する記憶部と、スレーブサーバそれぞれで演算するサーバ内演算処理を含み、もしくは、サーバ内演算及び複数のスレーブサーバからデータを集めてマスターサーバで演算するサーバ間演算処理を含み、複数のデータベースに記憶されたデータを検索する分散プランを、問合せクエリに基づいて生成する分散プラン生成部と、分散プランに、サーバ間演算処理と並列に実行可能な演算が存在し、かつ当該演算を実行した結果とサーバ間演算処理の結果とを共に必要とする演算が存在する場合は、サーバ間演算処理と並列に実行可能な演算と、サーバ間演算とを並列に実行するとともに、サーバ間演算処理と並列に実行可能な演算によって得られたデータおよびサーバ間演算によって得られたデータを結合する分割クエリ結合演算を分散プランに追加する分割クエリ結合演算追加部と、スレーブサーバから受信したローカルプランに基づいて、分散プランを更新する分散プラン更新部と、を備える。スレーブサーバは、分散プランから、スレーブサーバに関連するプランを抽出し、抽出したプランに含まれる分割クエリ結合演算及び分割クエリ結合演算に関連するデータの送受信演算を変更したローカルプラン候補を生成するローカルプラン候補生成部と、生成されたローカルプラン候補および抽出したプランそれぞれの演算コストを算出し、演算コストが最小となるプランをローカルプランとして選択するローカルプラン選択部と、を備える。
【図面の簡単な説明】
【００１３】
【図１】第１の実施形態に係る分散データベース検索装置の全体構成図の一例である。
【図２】第１の実施形態に係るデータベースに登録されるデータの１つであるＸＭＬデータの一例を示す模式図である。
【図３】第１の実施形態に係るデータベースに登録されるデータの１つであるＸＭＬデータの一例を示す模式図である。
【図４】第１の実施形態に係るスレーブサーバが保持するデータベース情報の一例を示す模式図である。
【図５】第１の実施形態に係るマスターサーバが保持するスレーブサーバ群情報の一例を示す模式図である。
【図６】第１の実施形態に係る分散データベース検索処理の一例を示すフローチャートである。
【図７】第１の実施形態に係るＸＭＬに対する問い合わせ言語ＸＱｕｅｒｙの一例を示す模式図である。
【図８】第１の実施形態に係るクエリ分割部において生成される部分クエリの一例を示す図である。
【図９】第１の実施形態に係る分散プラン生成部において生成される分散プランの一例を示す図である。
【図１０】第１の実施形態に係る分割クエリ結合演算追加部による分散プラン修正処理の一例を示すフローチャート図である。
【図１１】第１の実施形態に係る分割クエリ結合演算追加処理が行われた分散プランの一例を示す模式図である。
【図１２】第１の実施形態に係るローカルプラン選択部において生成されるローカルプランの一例を示す模式図である。
【図１３】第１の実施形態に係るローカルプラン候補生成処理の一例を示すフローチャート図である。
【図１４】第１の実施形態に係るローカルプラン候補生成処理の一例を示すフローチャート図である。
【図１５】第１の実施形態に係るローカルプラン候補生成処理の一例を示すフローチャート図である。
【図１６】第１の実施形態に係るローカルプラン候補生成部において生成されるローカルプランの一例を示す模式図である。
【図１７】第１の実施形態に係るローカルプラン候補生成部において生成されたローカルプランの一例を示す模式図である。
【図１８】第１の実施形態に係るローカルプラン候補生成部において生成されたローカルプランの一例を示す模式図である。
【図１９】第１の実施形態に係るローカルプラン候補生成部において生成されたローカルプランの一例を示す模式図である。
【図２０】第１の実施形態に係るローカルプラン候補生成部において生成されたローカルプランの一例を示す模式図である。
【図２１】第１の実施形態に係るローカルプラン候補生成部において生成されたローカルプランの一例を示す模式図である。
【図２２】第１の実施形態に係るローカルプラン候補生成部で演算コストを算出する際に用いるパラメータの一例を示すフローチャート図である。
【図２３】第１の実施形態に係る分散プラン更新部が分散プランを更新する処理の一例を示すフローチャート図である。
【図２４】第１の実施形態に係る分散プラン更新部において更新される分散プランの一例を示す模式図である。
【図２５】第２の実施形態に係る分散データベース検索装置の全体構成図の一例である。
【図２６】第２の実施形態に係るスキーマ変更部で変更される前のスキーマの一例を示す模式図である。
【図２７】第２の実施形態に係る分散データベース検索処理の一例を示すフローチャートである。
【図２８】第２の実施形態に係るローカルプラン順序決定処理が行われたローカルプランの一例を示す模式図である。
【図２９】第２の実施形態に係るスキーマ生成部が分散プランのスキーマを生成する処理の一例を示すフローチャート図である。
【図３０】第２の実施形態に係るスキーマ変更部で変更された新しいスキーマの一例を示す模式図である。
【図３１】第２の実施形態に係るスキーマ変更部が分散プランの演算に入力されるデータのスキーマを更新する処理の一例を示すフローチャート図である。
【図３２】第２の実施形態に係るスキーマ変更部によるスキーマ生成処理が行われた結果得られる入出力スキーマの一例を示す図。
【発明を実施するための形態】
【００１４】
以下、実施形態の分散データベース検索装置について図面を参照して説明する。
【００１５】
（第１の実施形態）
図１は第１の実施形態の分散データベース検索装置の機能構成を示す構成図である。本実施形態の分散データベース検索装置は、ユーザから入力される検索式（以下、問合せクエリという）に基づいて検索を行い、検索結果を出力する。
【００１６】
図１に示すように、本実施形態の分散データベース検索装置は、マスターサーバとして機能する計算機０と、スレーブサーバとして機能する計算機１〜計算機Ｎとが接続して構成されている。
【００１７】
マスターサーバである計算機０は、構文解析部１１と、クエリ分割部１２と、分散プラン生成部１３と、分割クエリ結合演算追加部１４と、分散プラン更新部１５と、分散プラン実行部１６と、送受信部１７（第１の送受信部）と、情報記憶部２０（第１の記憶装置）とを備える。
【００１８】
情報記憶部２０は、スレーブサーバ群情報を格納するスレーブサーバ群情報記憶部２１と、後述する分散プランを格納する分散プラン記憶部２２とを備える。なお、スレープサーバ群情報とは全てのスレーブサーバの名前や位置、及び登録件数等スレーブサーバが持つデータベースに関する情報であり、スレーブサーバが持つデータベースの情報の一部である。マスターサーバはこのスレーブサーバ群情報に基づいてスレーブサーバにどのデータを送信するかを決定する。
【００１９】
構文解析部１１は、ユーザから与えられた問合せクエリ５１を構文解析する。
【００２０】
クエリ分割部１２は、問合せクエリ５１を分割する機能を備え、構文解析部１１による問合せクエリ５１の構文解析結果と、スレーブサーバ群情報テーブル２１とに基づいて、サーバ内演算及びサーバ間演算の単位で問合せクエリ５１を分割する。分割した問合せクエリ５１を部分クエリという。なお、サーバ内演算とは問合せクエリ５１を各スレーブサーバ内で処理することである。また、サーバ間演算とは複数のスレーブサーバからデータを集めてマスターサーバ内で演算する処理である。
【００２１】
分散プラン生成部１３は、分散プラン生成手段として機能するものであり、クエリ分割部１２により得られた部分クエリと、スレーブサーバ群情報テーブル２１の情報とに基づいて分散プランを生成する。すなわち、分散プラン生成部１３は、スレーブサーバ群情報記憶部２１に格納されているスレーブサーバの名前や位置、及び登録件数等に基づいて、分割されたサーバ内演算とサーバ間演算の、演算順序、演算実行場所及びサーバ間で送受信するデータの内容を決定した分散プランを生成する。なお、サーバ間で送受信するデータの内容とは、例えばスレーブサーバのデータ、スレーブサーバのデータの一部、平均値等のスレーブサーバのデータの演算結果、もしくは最大値や複数のスレーブサーバのデータの組合せ等のサーバ間演算の結果である。
【００２２】
分散プラン生成部１３は分割クエリ結合演算追加部１４と分散プラン更新部１５とを備える。
【００２３】
分割クエリ結合演算追加部１４は、分散プラン生成部１３により得られた分散プランを図１０のフローチャートに示す分割クエリ結合演算追加処理に従って修正する。以下、修正された分散プランを修正分散プランという。分割クエリ結合演算追加処理については後述する。
【００２４】
分散プラン更新部１５は、分散プラン更新手段として機能するものでありローカルプラン選択部、スレーブサーバから送られてきたローカルプランに基づいて修正分散プランを更新する分散プラン更新処理を行う。分散プラン修正処理については後述する。
【００２５】
分散プラン実行部１６は、分散プラン更新部１５によって更新された分散プランに基づいて演算を実行する。
【００２６】
送受信部１７は、データ送受信手段として機能を有する。
【００２７】
続いてスレーブサーバである計算機１〜Ｎについて説明する。
【００２８】
計算機１〜Ｎはスレーブサーバとして機能するものであり、ローカルプラン選択部３１と、ローカルプラン候補生成部３２と、ローカルプラン実行部３３と、送受信部３４（第２の送受信部）と、情報記憶部４０（第２の記憶装置）とを備える。
【００２９】
情報記憶部４０は、格納したデータのスキーマ情報や件数等の統計情報などのデータベースに格納されたデータに関する情報であるデータベース情報を保持するデータベース情報記憶部４１と、ローカルプランを保持するローカルプラン記憶部４２と、検索対象の実際のデータ（以下、格納データという）を保持する格納データ記憶部４３と、を備える。
【００３０】
ローカルプラン選択部３１は、ローカルプラン生成手段として機能するものであり、ローカルプラン候補生成部３２を備える。ローカルプラン選択部３１は、分割クエリ結合演算追加部１４により得られた修正分散プランの内、自身のサーバに関連する部分プランからなるローカルプランを生成する。ローカルプラン選択部が生成したローカルプランに基づいて、ローカルプラン候補生成部３がローカルプランの候補をさらに作成する。ローカルプラン選択部３１は、自身が作成したローカルプランとローカルプラン候補生成部３２に作成されたローカルプラン候補の中から、見積もり実行時間または見積もり実行計算量からなる演算コストを計算する。ローカルプラン選択部３１は、算出した演算コストが最小となるプランをローカルプランとして決定する。
【００３１】
ローカルプラン実行部３３は、ローカルプラン選択部３１によって得られたローカルプランに基づいて演算を実施する。送受信部３４はマスターサーバの送受信部１７と同一の機能を持つ。
【００３２】
ここで、図２及び図３に、スレーブサーバの格納データ記憶部４３に登録されるデータの一例を示す。なお、本実施形態のスレーブサーバの格納データ記憶部４３に登録されるデータはＸＭＬフォーマット形式で記述されている。なお、図２に示すデータは、書籍の発行年数、タイトル、著者、価格に関するデータである。図３に示すデータは、ある賞の受賞年度、受賞者、受賞した書籍のタイトル、受賞者の性別に関するデータである。
【００３３】
図４は、スレーブサーバのデータ情報記憶部４１が保持するデータベースの情報の一例である。図４に示すように、データベース情報は、「登録ノード」１１２と、「登録数」１１３と、「索引情報」１１４の項目を有するデータベース情報テーブル１１１として保持される。
【００３４】
「登録ノード」１１２は、スレーブサーバの格納データ記憶部４３に登録されたＸＭＬデータが有するノード名を示すものであり、ここではどのノードの下にあるかを含めて記述する。なお、ノードとはＸＭＬデータを構成する要素や属性などである。
【００３５】
「登録数」１１３は、スレーブサーバの格納データ記憶部４３に登録されたＸＭＬデータ中に各登録ノード１１２が出現した回数を示す。
【００３６】
「索引情報」１１４は、登録ノード１１２に対して設定した索引の種類を記述したものである。索引の種類は、例えば数値索引や文字索引である。なお、図４には、一例として計算機１乃至計算機４のデータベース情報テーブル１１１−１〜１１１−４を示している。
【００３７】
図５は、マスターサーバである計算機０が保持するスレーブサーバ群情報記憶部２１に保存されたスレーブサーバ群情報２１の一例である。図５に示すように、スレーブサーバ群情報は「サーバ名」１２２、「Ｃｏｌｌｅｃｔｉｏｎ情報」１２３、「登録文書数」１２４という項目を有するスレーブサーバ群情報テーブル１２１として保持される。
【００３８】
「サーバ名」１２２にはスレーブサーバの名称が格納される。「Ｃｏｌｌｅｃｔｉｏｎ情報」１２３には登録するＸＭＬデータの格納場所の名前（以下、Ｃｏｌｌｅｃｔｉｏｎ名という）が格納される。本実施形態の分散データベースは異なるスレーブサーバでも同じＣｏｌｌｅｃｔｉｏｎ情報１２３を持つことができるため、ユーザはＣｏｌｌｅｃｔｉｏｎ名を指定することで特定のＸＭＬデータの集合内を検索することが可能となる。「登録文書数」１２４はＣｏｌｌｅｃｔｉｏｎに登録されたＸＭＬデータの数が格納される。
【００３９】
ここで、図６乃至図２５を参照して、本実施形態の分散データベース検索装置の処理について説明する。図６は、本実施形態の分散データベース検索装置の検索処理の一例を示すフローチャートである。なお、本実施形態の分散データベース検索装置は、計算機１〜４のデータベース情報記憶部４１に、図４に示したデータベース情報が格納されているとする。
【００４０】
まず、ユーザによってマスターサーバに検索式である問合せクエリ５１が入力される（ステップＳ１）。
【００４１】
ここで、図７に、ユーザによって入力される問合せクエリ５１の一例を示す。図７に示す問合せクエリ５１は、ＸＭＬデータの問い合わせ言語であるＸＱｕｅｒｙによって記述されている。なお、図７に示す問合せクエリ５１は、「過去の受賞歴がある男性作家の著書のうち１９９０年以降に出版された本のタイトルと値段を出力せよ」という意味である。
【００４２】
入力された問合せクエリ５１の１行目のｆｏｒから始まる１文は"ｐｕｂｌｉｓｈｅｒ"というＣｏｌｌｅｃｔｉｏｎに登録されているｂｏｏｋの名前を持つノードのうち、属性ノードｙｅａｒの値を数値化したものが１９９０以上のノードを変数＄ｘに格納している。これにより１９９０年以降に出版した本の一覧を取得している。なお、ＸＱｕｅｒｙにおいて変数は"＄"で始まる文字列として表現される。
【００４３】
次に２行目のｆｏｒから始まる１文は"ｐｒｉｚｅＷｉｎｎｅｒｓ"というＣｏｌｌｅｃｔｉｏｎに登録されているｐｒｉｚｅＷｉｎｎｅｒの名前を持つノードのうち、ｇｅｎｄｅｒという子ノードの値を文字列化したものが"ｍａｌｅ"という文字列と等しいものを選択した後、その子ノードであるｎａｍｅを変数＄ｙに格納しており、これにより受賞歴のある男性作家の名前の一覧を取得している。次に３、４、５行目のｌｅｔから始まる１文で１行目に取得したｂｏｏｋの子ノードであるａｕｔｈｏｒ、ｔｉｔｌｅ、ｐｒｉｃｅのノードを各々変数＄ｚ、＄ｕ、＄ｖに格納しており、これにより本の著者名とタイトルと値段を取得している。次に６行目のｗｈｅｒｅから始まる１文で男性作家の名前と本の著者名が一致するものの組合せを取得している。最後に７行目のｒｅｔｕｒｎから始まる１文で、６行目で取得した組合せに対してＬｉｓｔの名前のノードで囲んだＸＭＬを作りだしてユーザに返却している。これにより条件を満たした本のタイトルと値段を取得している。
【００４４】
図７に示す問合せクエリ５１がマスターサーバに入力されると、マスターサーバの構文解析部１１は、問合せクエリ５１を構文解析する（ステップＳ２）。構文解析部１１による構文解析結果は、マスターサーバのクエリ分割部１２に送信される。
【００４５】
構文解析結果を受信したクエリ分割部１２は、スレーブサーバ群情報テーブル２１の情報に基づいて、問合せクエリ５１を各スレーブサーバ内で処理するサーバ内演算及び複数スレーブサーバからデータを集めて演算するサーバ間演算の単位の部分クエリに分割する問合せクエリ５１分割処理を行う（ステップＳ３）。
【００４６】
すなわち、クエリ分割部１２は、構文解析部１１の構文解析の結果に基づいて、問合せクエリ５１を部分クエリに分割する。クエリ分割部１２は、スレーブサーバ群情報テーブル１２１を参照して、これらの部分クエリ毎に、部分クエリの内容がサーバ間演算かサーバ内演算を判定する。ここで、クエリ分割部１２による分割結果である部分クエリの一覧である部分クエリ一欄テーブル１３１の一例を図８に示す。
【００４７】
図８に示した部分クエリ一覧テーブル１３１は、部分クエリに順次振られる番号を格納する「番号」１３２、分割して得られた部分クエリを格納する「部分クエリ内容」１３３、部分クエリがサーバ内演算かサーバ間演算であるかを格納する「サーバ間／サーバ内演算」１３４、演算に必要なデータを保存した計算機名を格納する「対応サーバ」１３５の項目を有する。
【００４８】
以下に、クエリ分割部１２による問合せクエリの分割処理について、図７乃至図８を参照して具体的に説明する。
【００４９】
クエリ分割部１２は、スレーブサーバ群情報テーブル１２１に基づいて、部分クエリごとの演算に用いるデータを保持する計算機を特定する。図８では図７に示した問合せクエリ５１におけるＣｏｌｌｅｃｔｉｏｎ（"ｐｕｂｌｉｓｈｅｒ"）とＣｏｌｌｅｃｔｉｏｎ（"ｐｒｉｚｅＷｉｎｎｅｒ"）の２つのＣｏｌｌｅｃｔｉｏｎ情報に着目する。すなわち、これらのＣｏｌｌｅｃｔｉｏｎ情報を用いて図５に示したスレーブサーバ群情報テーブル１２１を検索する。
【００５０】
すなわち、クエリ分割部１２は、Ｃｏｌｌｅｃｔｉｏｎ（"ｐｕｂｌｉｓｈｅｒ"）は計算機１乃至３に存在し、Ｃｏｌｌｅｃｔｉｏｎ（"ｐｒｉｚｅＷｉｎｎｅｒ"）は計算機４に存在すると判定する。
【００５１】
さらにクエリ分割部１２はＣｏｌｌｅｃｔｉｏｎに対して実施する"／"、"／／"、"＞＝"、"＝"といったＸＱｕｅｒｙの演算に注目し、演算が複数の異なる計算機からの値が必要かどうかを判定する。演算が複数の異なる計算機からの値を必要とする場合、この演算をサーバ間演算と判定する。なお、一つの計算機からの値で行われる演算の場合、この演算をサーバ内演算と判定する。
【００５２】
図８に示すように、問合せクエリ５１においては"／"、"／／"、"＞＝１９９０"といった演算は全て入力となったデータの計算機上で実施できるため＄ｘ、＄ｚ、＄ｕ、＄ｖは全て同一計算機上に演算したデータが格納される。なお、サーバ内演算については幾つかの演算単位で分割する。図８では"ｆｏｒ"、"ｌｅｔ"といった代入文が発生する単位で分割しており番号１〜５の部分クエリが発生する。なお、"ｆｏｒ"、"ｌｅｔ"という代入文の単位で分割したのは１例であり、実際にはもっと細かい演算単位で分割しても良いし、もっと大きな演算単位で分割しても良い。
【００５３】
一方、"ｗｈｅｒｅ＄ｙ＝＄ｚ"という演算において、＄ｙは計算機４のデータであり、＄ｚは計算機１から３にあるデータであるためサーバ間演算であるとする。
【００５４】
続いて、次の"ｒｅｔｕｒｎ＜Ｌｉｓｔ＞｛＄ｕ｝｛＄ｖ｝＜／Ｌｉｓｔ＞"の演算は最終結果を返却する演算であるため、＄ｕ、＄ｖのデータを持つ計算機１から３のデータを集めて演算するサーバ間演算が必要だと判定する。
【００５５】
続いて、分散プラン生成部１３が、図８に示した部分クエリ一覧テーブル１３１と図５に示したスレーブサーバ群情報テーブル１２１とに基づいて分散プランを生成する（ステップＳ４）。生成した分散プランは分散プランテーブル１４１に格納される。
【００５６】
図９に、分散プランテーブル１４１の一例を示す。
【００５７】
分散プランテーブル１４１は「演算番号」１４２、「部分クエリ番号」１４３、「演算内容」１４４、「事前実行演算番号」１４５、「実行場所」１４６、「送信場所」１４７、「入力変数」１４８、「出力変数」１４９の項目を有する。
【００５８】
「演算番号」１４２は、演算毎に割り当てられた番号を示す。「部分クエリ番号」１４３は、図８に示した部分クエリテーブル１３１における部分クエリ番号１３２の項目で割り当てられた番号を格納する。部分クエリ番号１３２が割り当てられていない場合は空欄とする。
【００５９】
「演算内容」１４４は、各演算の内容を格納する。ここでは、分散プラン生成部１３は、図８に示した部分クエリ一覧テーブル１３１におけるサーバ内演算は、そのままサーバ内演算とし、部分クエリ一覧テーブル１３１におけるサーバ間演算は、具体的な操作を表す演算内容を記述する。さらに、部分クエリ一覧テーブル１３１におけるサーバ間演算の前後では、データの送信、データ受信の演算が必要となるため、新たに加える。
【００６０】
「事前実行演算番号」１４５は、その演算を実行する前に必ず実行しなければならない演算がある場合に、その演算番号を格納する。「実行場所」１４６は、演算を実行する場所（計算機）を格納する。データの送信とデータ受信の演算の場合は、演算結果のデータの送信先を「送信場所」１４７に格納する。すなわち、実行場所１４６はデータの送信元の計算機であり、送信場所１４７はデータの送信先の計算機である。
【００６１】
「入力変数」１４８は、演算に入力データが必要な場合に格納され、そのデータが格納された変数の名前のリストを格納する。「出力変数」１４９は、演算が新しい値を作成する場合、その格納先の変数の名前のリストを格納する。
【００６２】
なお、図９に示した分散プランテーブル１４１の演算番号１乃至５は、図８に示した部分クエリ一覧テーブル１３１の番号１乃至５に対応する。また、分散プランテーブル１４１の演算番号１０及び１１は、図８に示した部分クエリ一覧テーブル１３１の番号６、７に対応する。
【００６３】
また、部分クエリ一覧テーブル１３１でサーバ内／サーバ間演算１３４に「サーバ間演算」と格納されている部分クエリ番号６の演算は、演算内容１４４に「サーバ間ＪＯＩＮ」と格納される。すなわち、部分クエリ内容１３３に基づいた具体的な演算内容が格納される。同様に、部分クエリ番号７の演算は、演算内容１４４に「返却データ作成」という具体的な演算が格納されている。なお、「サーバ間ＪＯＩＮ」とは２つの変数に格納されたデータのうち値の等しい組合せを残す演算であり、「返却データ作成」とは入力されたデータを利用して新しいＸＭＬデータを作る演算である。
【００６４】
分散プラン生成部１３は、「サーバ間演算」にのみ着目し、実行順序や実行場所を決定する。具体的には、図９に示した分散プランテーブル１４１は、サーバ間演算の演算内容１４４はサーバ間ＪＯＩＮと返却データ作成の２種類であるため、返却データ作成演算はサーバ間ＪＯＩＮを実行した後の方が対象となるデータが少なくなり効率が良いと判断する。
【００６５】
また、本実施形態では、サーバ間演算はマスターサーバで実施するものとして実行場所を決定する。なお、サーバ間演算をマスターサーバで実行するためには各スレーブサーバにあるデータを集める必要がある。そのため分散プラン生成部１３は、分散プランテーブル１４１の演算番号６および演算番号８を追加し、それぞれの演算内容１４４にスレーブサーバがマスターサーバにデータを送る演算である「データ送信」を格納する。続いて、演算番号６および８において送信されたデータをマスターサーバが受信するために、演算番号７および９を追加し、それぞれの演算内容１４４にマスターサーバがスレーブサーバからデータを受信する演算である「データ受信」を格納する。
【００６６】
なお、本実施形態ではサーバ間演算をマスターサーバで実行するように決定しているが、マスターサーバではなく、例えば複数のスレーブサーバで実行するように決定しても良い。
【００６７】
分散プラン生成部１３は、図８に記載した部分クエリ内容１３３に基づいて、入力変数１４８および出力変数１４９を格納する。例えば、"ｆｏｒ〜ｉｎ"、"ｌｅｔ〜：＝"の"〜"に書かれた変数が出力変数１４９であり、それ以外の場所で書かれた変数は入力変数１４８とする。また、データ送信演算においては入力変数１４８が出力変数１４９になる。さらにデータ受信演算においてはデータ送信演算の出力変数１４９が入力変数１４８と出力変数１４９になる。
【００６８】
なお、サーバ内演算は、分散プラン生成部１３によって順序関係が崩れないように任意の順序に配置される。このように、本実施形態の分散プラン生成部１３は、部分クエリ一覧テーブル１３１の「サーバ間演算」のみを検討する。これにより検討範囲が限定されるため、分散プラン生成部１３１は容易に分散プランを生成可能である。
【００６９】
次に、分割クエリ結合演算追加部１４が、分散プラン生成部１３が生成した分散プランに対して「分割クエリ結合」演算を追加し、分散プランの修正を行う分割クエリ結合演算追加処理を行う（ステップＳ５）。
【００７０】
ここで、図１０を参照して、分割クエリ結合演算追加部１４が、図９に示した分散プランテーブル１４１に格納された分散プランに対して、分割クエリ結合演算追加処理を行う際の動作について具体的に説明する。
【００７１】
なお、この分割クエリ結合演算追加処理ではｉおよびｊという変数を用いる。ｉは１以上の整数であり、対象の分散プランの演算番号以下である（１≦ｉ≦分散プランの演算番号の最大値）。また、分割クエリ結合演算追加処理の開始時点ではｉ＝１である。また、分散プランの演算番号の最大値を「ｍａｘ」とする。また、演算番号１４２がｉの分散プランの演算を演算Ｅとする。なお、ｊはｉと同様の性質の変数であり、演算番号１４２がｊの分散プランの演算を演算Ｓとする。
【００７２】
分割クエリ結合演算追加部１４は、分散プラン生成部１３から分散プランを受信すると、まず、初期化処理としてｉ＝１、分散プランの演算番号の最大値＝ｍａｘとする（ステップＳ１０）。
【００７３】
分割クエリ結合演算追加部１４は、図９に記載した分散プランテーブル１４１における演算番号ｉの演算Ｅを取得する（ステップＳ２０）。次に、分割クエリ結合演算追加部１４は、取得した演算Ｅがサーバ間演算であり、かつｉ≠ｍａｘであるか否かを判定する（ステップＳ３０）。
【００７４】
取得した演算Ｅがサーバ間演算であり、かつｉ≠ｍａｘである場合、すなわち演算Ｅが最後の演算以外の場合（ステップＳ３０がＹｅｓ）、ｊ：＝１とする（ステップＳ４０）。
【００７５】
次に、分散プランテーブル１４１の演算番号ｊの演算Ｓを取得する（ステップＳ５０）。分割クエリ結合演算追加部１４は、演算Ｓの演算内容１４４がデータ送信であり、かつ送信場所１４７に格納された計算機がスレーブサーバであるか否かを、図９の分散プランテーブル１４１を参照して判定する（ステップＳ６０）。
【００７６】
演算Ｓの演算内容１４４が「データ送信」であり、かつ送信場所１４７の計算機がスレーブサーバの場合（ステップＳ６０がＹｅｓ）、分割クエリ結合演算追加部１４は、演算Ｓの入力変数１４７と演算Ｅの入力変数１４７とに共通して現れる変数を格納したリスト（以下、ｖａｒＬｉｓｔという）を作成する（ステップＳ７０）。次に演算Ｓの入力変数１４７からｖａｒＬｉｓｔにある変数を除いた変数を格納したリスト（以下、ｎｅｗＶａｒＬｉｓｔという）を作成する（ステップＳ８０）。分割クエリ結合演算追加部１４は、作成したｖａｒＬｉｓｔが空でなく、かつこのｖａｒＬｉｓｔに含まれる変数が、演算Ｓの入力変数１４７と完全に一致しない、かつｖａｒｌｉｓｔの変数を出力する演算とｎｅｗＶａｒＬｉｓｔの変数を出力する演算とが並列実行可能かを判定する（ステップＳ９０）。
【００７７】
なお、ここで図９に示した分散プランテーブル１４１において、ｖａｒｌｉｓｔの変数を出力する演算とｎｅｗＶａｒＬｉｓｔの変数を出力する演算とが並列実行可能かどうかの判定方法について説明する。この方法は、一方の演算の事前実行演算番号１４５及びこの事前実行演算番号１４５の演算の事前実行演算番号１４５を繰り返し遡って調べた際に、もう一方の演算が事前実行演算番号として存在しない場合に、２つの演算は並列実行可能と判定する。すなわち、演算Ａの事前実行演算番号１４５に演算Ｂの演算番号がある場合は、演算Ｂを実行した後に演算Ａを実行しなくてはいけないため、並列実行できないと判定する。
【００７８】
図１０のステップＳ９０の説明に戻る。ｖａｒＬｉｓｔが空でなく、かつこのｖａｒＬｉｓｔに含まれる変数が、演算Ｓの入力変数１４７と完全に一致しない、かつｖａｒｌｉｓｔの変数を出力する演算とｎｅｗＶａｒＬｉｓｔの変数を出力する演算とが並列実行可能な場合（ステップＳ９０がＹｅｓ）、次の５つの演算を演算Ｅの後に挿入し、挿入後、ｉにｉ＋５を代入する（ｉ：＝ｉ＋５）（ステップＳ１００）。
【００７９】
１つ目の演算は、演算内容１４４が"データ送信"、入力変数１４８と出力変数１４９がｖａｒＬｉｓｔに含まれる変数、実行場所１４６が"演算Ｓの送信場所１４７、送信場所１４７が演算Ｓの実行場所１４６"である。
【００８０】
２つ目の演算は、演算内容１４４が"データ受信"、入力変数１４８と出力変数１４９がｖａｒＬｉｓｔに含まれる変数、実行場所１４６が"演算Ｓの送信場所１４７"、"送信場所１４７が演算Ｓの実行場所１４６"である。
【００８１】
３つ目の演算は、演算内容１４４が"分割クエリ結合"、入力変数１４８がｖａｒＬｉｓｔに含まれる変数、実行場所１４６が"演算Ｓの実行場所１４６"である。なお、演算内容が「分割クエリ結合」とは、ある変数に対して別々に並行して処理を行った結果を再び１つにする演算である。
【００８２】
４つ目の演算は、演算内容１４４が"データ送信"、入力変数１４８と出力変数１４９がｎｅｗＶａｒＬｉｓｔに含まれる変数、実行場所１４６が"演算Ｓの実行場所１４６"、"送信場所１４７が演算Ｓの送信場所１４７"である。
【００８３】
５つ目の演算は、演算内容１４４が"データ受信"、入力変数１４８と出力変数１４９がｎｅｗＶａｒＬｉｓｔ、実行場所１４６が"演算Ｓの実行場所１４６"送信場所１４７が"演算Ｓの送信場所"である。
【００８４】
次に、演算Ｓで送信する変数を変更するために３つの処理を実施する（ステップＳ１１０）。１つ目は演算Ｓの入力変数１４８と出力変数１４９の内容をｖａｒＬｉｓｔの値に変更する。２つ目は演算Ｓの次の演算Ｒを取得する。演算Ｒは演算Ｓに対応する演算内容１４４"データ受信"の演算である。３つ目にＲの入力変数１４８と出力変数１４９リストの内容をｖａｒＬｉｓｔの値に変更する。その後ステップＳ１２０へ進む。
【００８５】
なお、演算Ｓがデータ送信ではない、または実行場所１４６の計算機がスレーブサーバでない場合（ステップＳ６０がＮｏ）も、ステップＳ１２０へと進む。
【００８６】
またｖａｒＬｉｓｔが空、または演算Ｓの入力変数リストと完全に一致する、かつｖａｒｌｉｓｔの変数を出力する演算とｎｅｗＶａｒＬｉｓｔの変数を出力する演算とが並列実行可能でない場合（ステップＳ９０がＮｏの場合）も、ステップＳ１２０に進む。
【００８７】
ステップＳ１２０では、分割クエリ結合演算追加部１４は、ｊにｊ＋１を代入する（ｊ：＝ｊ＋１）（ステップＳ１２０）。すなわち、ステップＳ１２０はステップＳ６０がＮｏの場合もしくはステップＳ９０がＮｏの場合もしくはステップＳ１１０に続いて行われる。
【００８８】
ステップＳ１２０に続いて、分割クエリ結合演算追加部１４は、ｊがｉより小さいかを判定する（ステップＳ１３０）。ｊがｉより小さい場合（ステップＳ１３０がＹｅｓ）はステップＳ５０に戻り処理を繰り返す。ｊがｉより小さくない場合（ステップＳ１３０がＮｏ）はステップＳ１４０に進みｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ１４０）。
【００８９】
演算Ｅがサーバ間演算ではない、またはｉ＝ｍａｘの場合（ステップＳ３０がＮｏ）、ステップＳ１４０に進む。すなわち、ステップＳ１４０の処理はステップＳ１３０がＮｏの場合もしくはステップＳ３０がＮｏの場合に続いて行われる。
【００９０】
ステップＳ１４０に続いて、分割クエリ結合演算追加部１４は、ｉがｍａｘ以下かを判定する（ステップＳ１５０）。すなわち、すべての部分クエリに対して分割クエリ演算追加処理を行ったかを判定する。
【００９１】
ｉがｍａｘ以下である場合（ステップＳ１５０がＹｅｓ）、分割クエリ結合演算追加部１４は、ステップＳ２０に戻り処理を繰り返す。ｉがｍａｘよりも大きい場合（ステップＳ１５０がＮｏ）、分割クエリ結合演算追加部１４は処理を終了する。
【００９２】
ここで、図１１に、図９に示した分散プランに対して、分割クエリ結合演算追加部１４が上述した分割クエリ結合演算追加処理を行った結果、修正された分散プラン（以下、修正分散プランという）の一例を示す。
【００９３】
図９の分散プランテーブル１４１に記載された分散プランは、演算１乃至１０はサーバ間演算ではないため、分割クエリ結合演算追加部１４、はｉが１０になるまで１ずつ増やしていく（図１０のステップＳ２０、ステップＳ３０、ステップＳ１４０、ステップＳ１５０）。
【００９４】
ｉ＝１０になると、演算Ｅがサーバ間演算であるため（ステップＳ３０がＹｅｓ）、変数ｊに１を代入する（ステップＳ４０）。なお、演算Ｅがサーバ間演算かどうかの判定は、演算Ｅの部分クエリ番号に基づいて分散プランテーブル１４１を参照して行われる。
【００９５】
次にｊが６になるまではデータ送信ではないためｊを１ずつ増やしていく（ステップＳ５０、ステップＳ６０がＮｏ、ステップＳ１２０、ステップＳ１３０）。
【００９６】
ｊが６になると、演算Ｓの演算内容がデータ送信で実行場所１４６の計算機がスレーブサーバであるため（ステップＳ６０がＹｅｓ）、演算番号６の入力変数１４８と演算番号１０の入力変数１４８に共通で現れる変数＄ｚを格納した変数リストｖａｒＬｉｓｔを作成する（ステップＳ７０）。
【００９７】
取得した演算番号６の入力変数１４８からｖａｒＬｉｓｔの変数リストを除いた変数＄ｕ、変数＄ｙを格納した変数リストｎｅｗＶａｒＬｉｓｔを作成する（ステップＳ８０）。
【００９８】
ｖａｒＬｉｓｔが空ではなく、演算番号６の入力変数リストとも完全に一致しない、かつｖａｒｌｉｓｔとｎｅｗＶａｒＬｉｓｔの変数を出力する演算が並列実行可能であるため図１１の演算番号１１−１５の５つの演算を追加した後ｉを５加えて１５を代入する（ステップＳ９０、ステップＳ１００）。次に演算番号６のデータ送信と演算番号７のデータ送信の入力変数１４８と出力変数１４９にｖａｒＬｉｓｔの値変数＄ｚを代入する（ステップＳ１１０）。
【００９９】
次にｊが８になるまではデータ送信ではないため単純に変数ｊを１ずつ増やしていく（ステップＳ５０、ステップＳ６０、ステップＳ１２０、ステップＳ１３０）。ｊが８の場合は演算内容１４４がデータ送信で実行場所１４６がスレーブサーバであるため、演算番号８の入力変数と演算番号１０の入力変数リストに共通で現れる変数＄ｙ格納した変数リストｖａｒＬｉｓｔを取得する（ステップＳ７０）。
【０１００】
取得したｖａｒＬｉｓｔは空ではないが、演算番号８の入力変数リストと完全に一致するため（ステップＳ９０がＮｏ）、ｊに１を加える（ステップＳＳ１２０）。以降データ送信演算はないためｉを１増やして１６を代入する（ステップＳ１２０、ステップＳ１３０、ステップＳ１４０、ステップＳ１５０）。
【０１０１】
次にｉが１６における演算はサーバ間演算であるが、ｉがｍａｘと等しいため（ステップＳ１５０がＹｅｓ）、ステップＳ２０にもとり、処理を繰り返す。そして、ｉの値がｍａｘを超えると（ステップＳ１５０がＮｏ）、分割クエリ結合演算追加部１４は処理を終了する。その結果、分散プランが作成される。図１１に修正された分散プランのテーブル１５１を示す。すなわち、分散プラン結合演算追加部１４は、サーバ間演算とその他の演算はできるだけ並列に実行して、後で結合する形にプランを書き換える。
【０１０２】
上述したように、分割クエリ結合演算追加部１４が分散プランを修正すると、マスターサーバの送受信部１７はスレーブサーバに修正された修正分散プランを送信する。このとき、全てのスレーブサーバに修正分散プランを送信してもよい。また、実行場所を参照して、関連のあるスレーブサーバにのみ修正分散プランを送信してもよい。
【０１０３】
スレーブサーバのローカルプラン選択部３１は、受信した分割クエリ結合手順追加部１４により修正された分散プランの内、自身のサーバに関連する部分に対するローカルプラン候補を生成する（ステップＳ６）。
【０１０４】
ここで、ローカルプラン選択部３１によって生成されたローカルプランの候補を図１２に例示する。図１２に示したローカルプラン候補２は、計算機２であるスレーブサーバのローカルプラン選択部３１が、図１１に記載した分散プランと図４に記載したデータベース情報１１１とに基づいて生成した、計算機２に関するローカルプラン候補の一例である。
【０１０５】
図１２に示したローカルプラン候補２示すように、ローカルプラン候補２は「演算番号」３０２、「部分クエリ番号」３０３、「演算内容」３０４、「事前実行演算番号」３０５、「実行場所」３０６、「送信場所」３０７、「入力変数」３０８、「出力変数」３０９の項目を有する。なお、本実施形態のローカルプラン候補および後述するローカルプランが有する項目３０２〜３０９は、本実施形態の分散プランテーブルが有する項目１４２〜１４９と同一である。
【０１０６】
なお、図１２に示したローカルプラン候補２において、計算機２では図４のデータベース情報からのｂｏｏｋの下のｙｅａｒ属性ノードに対して数値索引が設定されている。そのため、最初の演算番号１で部分クエリ番号１の部分クエリに該当する処理を演算「数値索引」によって実現する。演算「数値索引」はノードが持つ値を数値化したものを索引化した数値索引を設定したノードに対して、与えられた数値との比較条件を満たすノード若しくはそのノードを所有する文書の最初のノードを高速に取得する演算である。
【０１０７】
具体的には、ローカルプラン選択部３１は、属性ノードｙｅａｒの値が１９９０以上の条件を満たすｂｏｏｋノードを数値索引内から探し出して変数＄ｘに格納する。
【０１０８】
演算番号２、４、５は各々部分クエリ番号３、４、５の部分クエリを処理する演算「ＴＲＡＶＥＲＳＥ（トラバース）」を実施する。なお、演算「ＴＲＡＶＥＲＳＥ」とはＸＭＬ内の或るノード（入力）から或るノード（出力）へ辿っていく演算である。具体的には演算番号１で求めた＄ｘに格納されたｂｏｏｋノードから、子ノードであるａｕｔｈｏｒ、ｔｉｔｌｅ、ｐｒｉｃｅを取得して各々変数＄ｚ、＄ｕ、＄ｖに格納する。演算番号３、６、７、８は分散プランで作成したデータ送信、データ受信、分割クエリ結合演算をそのまま残したものである。
【０１０９】
次に、図１３を参照して、図１２のローカルプラン候補２に基づいてローカルプラン候補生成部３２がさらにローカルプラン候補を生成するローカルプラン候補生成処理について説明する（図６のステップＳ７）。図１３はローカルプラン候補生成処理の一例を示すフローチャートである。
【０１１０】
なお、このローカルプラン候補生成処理はｉという変数を用いる。ｉは１以上であり、かつ、対象のローカルプラン選択部３１が生成したローカルプラン候補のリスト（以下、ｉｎｐｕｔＰｌａｎＬｉｓｔという）内の要素数以下である（１≦ｉ≦ｉｎｐｕｔＰｌａｎＬｉｓｔ内の要素数）。
【０１１１】
まず、ローカルプラン候補生成部３２は、図１２に示すローカルプラン候補を取得する（ステップＳ２００）。ローカルプラン候補生成部３２は、ｉ＝１、ｉｎｐｕｔＰｌａｎＬｉｓｔ内の要素数＝ｍａｘとする（ステップＳ２１０）。
【０１１２】
続いてローカルプラン候補生成部３２はｉｎｐｕｔＰｌａｎＬｉｓｔからｉ番目のローカルプラン候補ｐｌａｎを取得する（ステップＳ２２０）。ローカルプラン候補生成部３２は、取得したｐｌａｎに基づいて、後述する分割クエリ結合の実施変数の組合せパターン生成処理を実施し、このｐｌａｎを含む新規のローカルプラン候補リストを作成する（ステップＳ２３０）。分割クエリ結合の実施変数の組合せパターン生成処理とは、分割クエリ結合前後で実施する演算を変化させて様々なローカルプラン候補を生成する処理であり、図１４のフローチャートにより詳細を後述する。
【０１１３】
ローカルプラン候補生成部３２は、分割クエリ結合の実施変数の組合せパターン生成処理によって得られた新規のローカルプラン候補リスト（以下、ｎｅｘｔＰｌａｎＬｉｓｔという）を取得する（ステップＳ２４０）。ここで、ｊという変数を用いる。ｊは１以上であり、かつ、ｎｅｘｔＰｌａｎＬｉｓｔ内の要素数以下である（１≦ｊ≦ｎｅｘｔＰｌａｎＬｉｓｔ内の要素数）。また、この時ｊ＝１であり、ｎｅｘｔＰｌａｎＬｉｓｔ内の要素数＝ｆｉｎａｌＭａｘとする（ステップＳ２５０）。
【０１１４】
次に、ローカルプラン候補生成部３２は、ｎｅｘｔＰｌａｎＬｉｓｔからｊ番目のローカルプラン候補ｎｅｘｔＰｌａｎを取得する（ステップＳ２６０）。ローカルプラン候補生成部３２は、取得したｎｅｘｔＰｌａｎに基づいて分割クエリ結合の実施場所パターン生成処理を実施しｎｅｘｔＰｌａｎを含む新規のローカルプラン候補リストを作成する（ステップＳ２７０）。分割クエリ結合の実施場所パターン生成処理とは、分割クエリ結合演算の実行場所を変化させることで様々なローカルプラン候補を生成する処理であり、図１５のフローチャートにより詳細を後述する。
【０１１５】
ローカルプラン候補生成部３２は、分割クエリ結合の実施場所パターン生成処理結果に基づいて新規のローカルプラン候補リストｆｉｎａｌＰｌａｎＬｉｓｔを作成する（ステップＳ２８０）。作成したｆｉｎａｌＰｌａｎＬｉｓｔ内のローカルプラン候補を最終出力である出力候補プランリストｏｕｔｐｕｔＬｉｓｔに追加する（ステップＳ２９０）。
【０１１６】
次に、ステップＳ３００に進み、ｊにｊ＋１を代入する（ｊ：＝ｊ＋１）（ステップＳ３００）。ローカルプラン候補生成部３２は、このｊがｆｉｎａｌＭａｘ以下であるかを判定する（ステップＳ３１０）。ｊがｆｉｎａｌＭａｘ以下の場合（ステップＳ３１０がＹｅｓ）、ステップＳ２６０に戻り処理を繰り返す。
【０１１７】
ｊがｆｉｎａｌＭａｘより大きい場合（ステップＳ３１０がＮｏ）、ステップＳ３２０に進みｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ３２０）。
【０１１８】
次にｉがｍａｘ以下かを判定する（ステップＳ３３０）。ｉがｍａｘ以下の場合（ステップＳ３３０がＹｅｓ）はステップＳ２２０に戻り処理を繰り返す。ｉがｍａｘよりも大きい場合は終了する。最終出力はｏｕｔｐｕｔＬｉｓｔに格納されたローカルプラン候補リストであり、ローカルプラン選択部３１はこのローカルプラン候補リストの中から最終的に１つのローカルプランを選択する。
【０１１９】
次に、図１４のフローチャートに従って、ローカルプラン候補生成部３２による、図１３のステップＳ２３０における分割クエリ結合の実施変数の組合せパターン生成処理について説明する。なお、この分割クエリ結合の実施変数の組合せパターン生成処理はｉという変数を用いる。ｉは１以上であり、かつ、入力対象のローカルプラン候補ｐｌａｎの演算番号以下である（１≦ｉ≦ｐｌａｎの演算番号の最大値）。
【０１２０】
まず、ローカルプラン候補生成部３２は、ｐｌａｎを最終出力である一時候補リストｎｅｘｔＰｌａｎＬｉｓｔに登録する（ステップＳ４００）。また、ローカルプラン候補生成部３２は、ｉ＝１、ｐｌａｎの演算番号の最大値＝ｍａｘとする（ステップＳ４１０）。
【０１２１】
続いて、ローカルプラン候補生成部３２は入力されたローカルプラン候補ｐｌａｎの演算番号ｉの演算Ｅを取得する（ステップＳ４２０）。取得した演算Ｅが分割クエリ結合演算の場合（ステップＳ４３０がＹｅｓ）、ｐｌａｎの演算番号ｉ＋１番目のデータ送信演算Ｓを取得し、さらに演算Ｓの入力変数の全組合せパターンのリストｖａｒＰａｔｔｅｒｎＬｉｓｔを取得する（ステップＳ４４０）。
【０１２２】
次に、ｊ：＝１とし、ｎｅｘｔＰｌａｎＬｉｓｔ内の要素数＝ｎｅｘｔＭａｘとする（ステップＳ４５０）。次に、ｎｅｘｔＰｌａｎＬｉｓｔのｊ番目のプランｎｅｘｔＰｌａｎを取得する（ステップＳ４６０）。次に、ｋ：＝１とし、ｖａｒＰａｔｔｅｒｎＬｉｓｔ内の要素数＝ｖｔＭａｘとする（ステップＳ４７０）。次に、ｎｅｘｔＰｌａｎの内容をコピーした新しいローカルプラン候補ｎｅｗＰｌａｎを作成する（ステップＳ４８０）。
【０１２３】
次に、ローカルプラン候補生成部３２は、次の３つの処理を実施する（ステップＳ４９０）。１つ目はｖａｒＰａｔｔｅｒｎＬｉｓｔのｋ番目の要素ｔａｒｇｅｔＶａｒｓを取得する処理であり、２つ目はｎｅｗＰｌａｎの演算番号ｉ＋１番目のデータ送信演算ＡＳを取得する処理であり、３つ目はｎｅｗＰｌａｎの演算番号ｉ−１番目のデータ受信演算ＡＲを取得する処理である。
【０１２４】
次に演算ＡＳの入力変数リストとｔａｒｇｅｔＶａｒｓの内容が一致するかを判定する（ステップＳ５００）。
【０１２５】
演算ＡＳの入力変数リストが空の場合（ステップＳ５００がＹｅｓ）、演算Ｅ、演算ＡＳ、演算ＡＲは不要であるため各演算内容をｄｕｍｍｙに変更する。ｄｕｍｍｙは何もしない演算であり、後で削除する。ここでは演算番号がずれるため削除しない。
【０１２６】
次に、分割クエリ結合をしない変数を事前に送るように、演算Ｅより前にあるデータ送信演算の入出力変数と事前実行演算番号を変更するために次の４つの処理を実施する（ステップＳ５２０）。１つ目は演算Ｅの入力変数を入力変数とするデータ送信演算ＢＳを取得する処理であり、２つ目はＢＳの入出力変数リストへｔａｒｇｅｔＶａｒｓに含まれる変数を追加する処理であり、３つ目はｔａｒｇｅｔＶａｒｓの変数を出力する演算の演算番号リストｐｒｅＥｘｅＬｉｓｔを取得する処理であり、４つ目はＢＳの事前実行演算番号にｐｒｅＥｘｅＬｉｓｔの値を代入する処理である。
【０１２７】
ローカルプラン候補生成部３２は、ステップＳ５２０の処理を行ったｎｅｗＰｌａｎをｎｅｗＰｌａｎＬｉｓｔに追加する（ステップＳ５３０）。
【０１２８】
その後、ｋにｋ＋１を代入し（ｋ：＝ｋ＋１）（ステップＳ５４０）、ｋがｖｔＭａｘ以下であるかを判定する（ステップＳ５５０）。ｋがｖｔＭａｘ以下の場合（ステップＳ５５０がＹｅｓ）、ステップＳ４８０に戻り処理を繰り返す。ｋがｖｔＭａｘより大きい場合（ステップＳ５５０がＮｏ）、ステップＳ５６０に進みｊにｊ＋１を代入する（ｊ：＝ｊ＋１）（ステップＳ５６０）。
【０１２９】
ローカルプラン候補生成部３２は、ｊがｎｅｘｔＭａｘ以下であるかを判定する（ステップＳ５７０）。ｊがｎｅｘｔＭａｘ以下の場合（ステップＳ５７０がＹｅｓ）、ステップＳ４６０に戻り処理を繰り返す。ｊがｎｅｘｔＭａｘより大きい場合（ステップＳ５７０がＮｏ）、ステップＳ５８０に進みｎｅｗＰｌａｎＬｉｓｔ内の要素をｎｅｘｔＰｌａｎＬｉｓｔに全て移す（ステップＳ５８０）。その後、ステップＳ５９０へと進み、ｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ５９０）。
【０１３０】
なお、演算Ｅが分割クエリ結合ではない場合も（ステップＳ４３０がＮｏ）、ステップＳ５９０に進みｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ５９０）。すなわちステップＳ５９０の処理はステップＳ４３０がＮｏまたはステップＳ５８０に続いて行われる。
【０１３１】
ローカルプラン候補生成部３２は、ｉがｍａｘ以下であるかを判定する（ステップＳ６００）。ｉがｍａｘ以下の場合（ステップＳ６００がＹｅｓ）、ステップＳ４２０に戻り処理を繰り返す。ｉがｍａｘより大きい場合は終了する。処理の終了後の最終出力はｎｅｘｔＰｌａｎＬｉｓｔに格納されたローカルプラン候補リストであり、図１３のステップＳ２４０に戻ってローカルプラン候補生成部３２の処理が続けられる。
【０１３２】
次に、図１５のフローチャートに従って分割クエリ結合の実施場所パターン生成処理について説明する。なお、この分割クエリ結合の実施場所パターン生成処理はｉという変数を用いる。ｉは１以上であり、かつ、入力対象のローカルプラン候補ｎｅｘｔＰｌａｎの演算番号以下である（１≦ｉ≦ｎｅｘｔＰｌａｎの演算番号の最大値）。
【０１３３】
ローカルプラン候補生成部３２は、ｎｅｘｔＰｌａｎを最終出力である最終候補リストｆｉｎａｌＰｌａｎＬｉｓｔに登録する（ステップＳ７００）。
【０１３４】
また、処理の開始時点ではｉ＝１、ｎｅｘｔＰｌａｎの演算番号の最大値＝ｍａｘとする（ステップＳ７１０）。
【０１３５】
まず、分割クエリ結合の実施場所パターン生成処理は入力されたローカルプラン候補ｎｅｘｔＰｌａｎの演算番号ｉの演算Ｅを取得する（ステップＳ７２０）。取得した演算Ｅが分割クエリ結合演算の場合（ステップＳ７３０がＹｅｓ）、ｎｅｘｔＰｌａｎの演算番号ｉ＋１番目の演算Ｓを取得する（ステップＳ７４０）。次に、ｊ：＝１とし、ｆｉｎａｌＰｌａｎＬｉｓｔ内の要素数＝ｆｉｎａｌＭａｘとする（ステップＳ７５０）。次に、ｆｉｎａｌＰｌａｎＬｉｓｔのｊ番目のプランｆｉｎａｌＰｌａｎを取得する（ステップＳ７６０）。次に、ｆｉｎａｌＰｌａｎの内容をコピーした新しいローカルプラン候補ｎｅｗＰｌａｎを作成する（ステップＳ７７０）。
【０１３６】
次にローカルプラン候補生成部３２は、分割クエリ結合の実行場所をマスターサーバに変更するために次の５つの処理を実施する（ステップＳ７８０）。１つ目は分割結合演算Ｅの直後の送信データ演算Ｓを取得する処理である。２つ目は分割クエリ結合演算Ｅの直前の受信データ演算Ｒを取得する処理である。３つ目は演算Ｒの演算内容を送信データ演算に、入出力変数にＳの入力変数を追加したものに、実行場所を演算Ｓの送信先→Ｓの送信元に変更する処理である。４つ目の処理は不要になった演算Ｓの演算内容をｄｕｍｍｙに変更する処理である。５つ目の処理は、演算Ｅの実行場所をＳの送信元に変更する処理である。
【０１３７】
次に、ステップＳ７９０に進みステップＳ７８０で修正したｎｅｗＰｌａｎを新規プランリストｎｅｗＰｌａｎＬｉｓｔに追加する（ステップＳ７９０）。次に、ステップＳ８００に進みｊにｊ＋１を代入する（ｊ：＝ｊ＋１）（ステップＳ８００）。次にｊがｆｉｎａｌＭａｘ以下であるかを判定する（ステップＳ８１０）。ｊがｆｉｎａｌＭａｘ以下の場合（ステップＳ８１０がＹｅｓ）、ステップＳ７６０に戻り処理を繰り返す。ｊがｆｉｎａｌＭａｘより大きい場合（ステップＳ８１０がＮｏ）、ステップＳ８２０に進みｎｅｗＰｌａｎＬｉｓｔ内の要素を全てｆｉｎａｌＰｌａｎＬｉｓｔに移す（ステップＳ８２０）。さらにステップＳ８３０へと進む。
【０１３８】
また演算Ｅが分割クエリ結合ではない場合も（ステップＳ７３０がＮｏ）、ステップＳ８３０に進みｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ８３０）。すなわちステップＳ８３０の処理はステップＳ７３０がＮｏまたはステップＳ８２０に続いて行われる。
【０１３９】
次にｉがｍａｘ以下であるかを判定する（ステップＳ８４０）。ｉがｍａｘ以下の場合（ステップＳ８４０がＹｅｓ）、ステップＳ７２０に戻り処理を繰り返す。ｉがｍａｘより大きい場合はステップＳ８５０に進む。
【０１４０】
ステップＳ８５０はｆｉｎａｌＰｌａｎＬｉｓｔ内にある全てのローカルプラン候補内の演算で、演算内容がｄｕｍｍｙとなっているものを削除して終了する（ステップＳ８５０）。最終出力はｆｉｎａｌＰｌａｎＬｉｓｔに格納されたローカルプラン候補リストであり、図１３のステップＳ２８０に戻ってローカルプラン候補生成部３２の処理が続けられる。
【０１４１】
図１２に示したローカルプラン候補２が、ローカルプラン選択部３１で得られたローカルプラン候補の場合において、上述したローカルプラン候補生成処理が行われた結果、得られる新たなローカルプラン候補２−１乃至２−６を図１６乃至図２１に示す。
【０１４２】
ローカルプラン候補生成部３２が、これらのローカルプラン候補２−１乃至２−６を生成する処理を具体的に説明する。まず、図１２のローカルプラン候補２が、分割クエリ結合の実施変数の組合せパターン処理の入力として渡される（図１３のステップＳ２００、Ｓ２１０、Ｓ２２０、Ｓ２３０）。
【０１４３】
次に分割クエリ結合の実施変数の組合せパターン処理において、入力された図１２のローカルプラン候補２（以下、ｐｌａｎとする）を一時候補リスト（以下、ｎｅｘｔＰｌａｎＬｉｓｔとする）に登録する（図１４のステップＳ４００）。次にｐｌａｎではｉが７になるまでは分割クエリ結合演算ではないので変数ｉを１ずつ増やしていく（ステップＳ４２０、Ｓ４３０、Ｓ５５０、Ｓ５４０）。ｉが７の時の演算Ｅは分割クエリ結合であるため演算番号が８の演算Ｓを取得し、Ｓの入力変数（＄ｕ、＄ｖ）の全組合せとして３つの組合せ（＄ｕ）、（＄ｖ）、（＄ｕ、＄ｖ）をｖａｒＰａｔｔｅｒｎＬｉｓｔに格納する（ステップＳ４４０）。次に、ｊ：＝１としてｎｅｘｔＰｌａｎＬｉｓｔ内の１番目の要素として最初に登録した図１２のｐｌａｎをｎｅｘｔＰｌａｎとして取得する（ステップＳ４５０、Ｓ４６０）。次にｎｅｘｔＰｌａｎをコピーしたｎｅｗＰｌａｎを作成する（ステップＳ４８０）。
【０１４４】
次に、ｖａｒＰａｔｔｅｒｎＬｉｓｔの１番目の要素（＄ｕ）を取得し、ｎｅｗＰｌａｎの演算番号８のデータ送信演算ＡＳと演算番号６のデータ受信演算ＡＲを取得する（ステップＳ４９０）。ＡＳの入力変数（＄ｕ、＄ｖ）と（＄ｕ）は一致しないため、分割クエリ結合の入力変数を送信する演算番号３のデータ送信演算を取得し入出力変数に分割クエリ結合の対象から外した変数＄ｕを追加する。さらに変数＄ｕを出力する演算番号４を演算番号３の事前実行演算番号に追加する（ステップＳ５００、Ｓ５２０）。これによって得られたｎｅｗＰｌａｎをｎｅｗＰｌａｎＬｉｓｔに追加する（ステップＳ５３０）。ｎｅｗＰｌａｎであるローカルプラン候補２−１の内容を図１６に示す。但し図１６に示したローカルプラン候補２−１では演算内容ｄｕｍｍｙの演算は削除済みである。次にｋに２を代入し再び図１２のｐｌａｎをコピーしたｎｅｗＰｌａｎを作成する（ステップＳ４８０）。
【０１４５】
次に、ｖａｒＰａｔｔｅｒｎＬｉｓｔの２番目の要素（＄ｖ）を取得し、ｎｅｗＰｌａｎの演算番号８のデータ送信演算ＡＳと演算番号６のデータ受信演算ＡＲを取得する（ステップＳ４９０）。ＡＳの入力変数（＄ｕ、＄ｖ）と（＄ｖ）は一致しないため、分割クエリ結合の入力変数＄ｚを送信する演算番号３のデータ送信演算を取得し入出力変数に分割クエリ結合の対象から外した変数＄ｖを追加する。さらに変数＄ｖを出力する演算番号５を演算番号３の事前実行演算番号に追加する（ステップＳ５００、Ｓ５２０）。これによって得られたｎｅｗＰｌａｎをｎｅｗＰｌａｎＬｉｓｔに追加する（ステップＳ５３０）。ｎｅｗＰｌａｎであるローカルプラン候補２−２の内容を図１７に示す。但し図１７に示したローカルプラン候補２−２では演算内容ｄｕｍｍｙの演算は削除済みである。次にｋに３を代入し再び図１２のｐｌａｎをコピーしたｎｅｗＰｌａｎを作成する（ステップＳ４８０）。
【０１４６】
次に、ｖａｒＰａｔｔｅｒｎＬｉｓｔの３番目の要素（＄ｕ、＄ｖ）を取得し、ｎｅｗＰｌａｎの演算番号８のデータ送信演算ＡＳと演算番号６のデータ受信演算ＡＲを取得する（ステップＳ４９０）。ＡＳの入力変数（＄ｕ、＄ｖ）とｖａｒＰａｔｔｅｒｎＬｉｓｔの３番目の要素（＄ｕ、＄ｖ）は完全に一致するため、演算Ｅ、ＡＳ、ＡＲの演算内容をｄｕｍｍｙに変更する（ステップＳ５１０）。次に分割クエリ結合の入力変数を送信する演算番号３のデータ送信演算を取得し入出力変数に分割クエリ結合の対象から外した変数＄ｕ、＄ｖを追加する。さらに変数＄ｕ、＄ｖを出力する演算番号４、５を演算番号３の事前実行演算番号に追加する（ステップＳ５２０）。これによって得られたｎｅｗＰｌａｎをｎｅｗＰｌａｎＬｉｓｔに追加する（ステップＳ５３０）。このｎｅｗＰｌａｎであるローカルプラン候補２−３の内容を図１８に示す。但し図１８に示したローカルプラン候補２−３では演算内容ｄｕｍｍｙの演算は削除済みである。次にｋに４を代入する（ステップＳ５４０）。
【０１４７】
次にｖａｒＰａｔｔｅｒｎＬｉｓｔは要素数が３までしかないためｊに２を代入する（ステップＳ５９０、Ｓ５８０）。次にｎｅｘｔＰｌａｎＬｉｓｔは要素数が１しかないため、今まで得られたｎｅｗＰｌａｎＬｉｓｔ内の３つのローカルプラン候補図１６、１７、１８に示したローカルプラン候補をｎｅｘｔＰｌａｎＬｉｓｔに移す（ステップＳ５７０、Ｓ５６０）。ｎｅｘｔＰｌａｎＬｉｓｔはこの時点で図１２、図１６乃至図１８のローカルプラン候補を要素として持つ。次にｉに８以降の値を代入しても分割クエリ結合は存在しないため分割クエリ結合の実施変数の組合せパターン生成処理を終了する（ステップＳ５５０、Ｓ５４０、Ｓ４２０、Ｓ４３０）。
【０１４８】
次に分割クエリ結合の実施変数の組合せパターン生成処理の出力リストとして図１２、図１６乃至図１８のローカルプラン候補を格納したｎｅｘｔＰｌａｎＬｉｓｔを取得する（図１３のステップＳ２４０）。次にｊに１を代入し、ｎｅｘｔＰｌａｎＬｉｓｔの１番目の要素である図１２のローカルプラン候補ｎｅｘｔＰｌａｎを取得する（ステップＳ２５０、Ｓ２６０）。次にｎｅｘｔＰｌａｎは分割クエリ結合の実施場所パターン生成処理の入力として渡される（ステップＳ２７０）。
【０１４９】
次に、分割クエリ結合の実施場所パターン生成処理の入力として渡された図１２のローカルプラン候補ｎｅｘｔＰｌａｎを、最終候補リストｆｉｎａｌＰｌａｎＬｉｓｔに登録する（図１５のステップＳ７００）。次にｉに１を代入する（ステップＳ７１０）。
【０１５０】
ｎｅｘｔＰｌａｎではｉが７になるまでは分割クエリ結合演算ではないので変数ｉを１ずつ増やしていく（ステップＳ７２０、Ｓ７３０、Ｓ８３０、Ｓ８４０）。ｉが７の時の演算Ｅは分割クエリ結合であるため演算番号が８のデータ送信演算Ｓを取得する（ステップＳ７４０）。次にｊに１を代入し、ｆｉｎａｌＰｌａｎＬｉｓｔ内の１番目の要素として最初に登録した、図１２に示したローカルプラン候補ｎｅｘｔＰｌａｎをｆｉｎａｌＰｌａｎとして取得する（ステップＳ７５０、Ｓ７６０）。次にｆｉｎａｌＰｌａｎをコピーしたｎｅｗＰｌａｎを作成する（ステップＳ７７０）。
【０１５１】
部分クエリ番号の実行場所をマスターサーバに変更するために以下の処理を行う（ステップＳ７８０）。最初に演算番号８の送信データ演算Ｓと演算番号６の受信データ演算Ｒを取得する。次にＲを送信データ演算に、入出力変数はＳの入力変数＄ｕ、＄ｖを加えたものに、実行場所を"計算機２→０"に変更する。さらにＳの演算内容をｄｕｍｍｙに変更する。最後にＥの実行場所を計算機０に変更する。
【０１５２】
次に、これによって得られたｎｅｗＰｌａｎをｎｅｗＰｌａｎＬｉｓｔに追加する（ステップＳ７９０）。ｎｅｗＰｌａｎであるローカルプラン候補２−４の内容を図１９に示す。但し図１９に示したローカルプラン候補２−４では演算内容ｄｕｍｍｙの演算は削除済みである。
【０１５３】
次にｊに２を代入するが、ｆｉｎａｌＰｌａｎＬｉｓｔは要素数が１しかないため、今まで得られたｎｅｗＰｌａｎＬｉｓｔ内の１つのローカルプラン候補２−４をｆｉｎａｌＰｌａｎＬｉｓｔに移す（ステップＳ８００、Ｓ８１０、Ｓ８２０）。次にｉに８以降の値を代入しても分割クエリ結合は存在しないため、今までｆｉｎａｌＰｌａｎＬｉｓｔで得られた各ローカルプラン候補内に存在する演算内容がｄｕｍｍｙの演算を削除して分割クエリ結合の実施場所パターン生成処理終了する（ステップＳ８３０、Ｓ８４０、Ｓ８５０）。
【０１５４】
次に分割クエリ結合の実施場所パターン生成処理の出力リストとして図１２、図１９のローカルプラン候補を格納したｆｉｎａｌＰｌａｎＬｉｓｔを取得する（図１３のステップＳ２８０）。次にｆｉｎａｌＰｌａｎＬｉｓｔ内の要素図１２、図１９のローカルプラン候補を出力候補プランリストｏｕｔｐｕｔＬｉｓｔに移す（ステップＳ２９０）。次にｊに２を代入し、ｎｅｘｔＰｌａｎＬｉｓｔの２番目の要素である図１６のローカルプラン候補ｎｅｘｔＰｌａｎを取得する（ステップＳ３００、Ｓ３１０、Ｓ２６０）。次にｎｅｘｔＰｌａｎは分割クエリ結合の実施場所パターン生成処理の入力として渡される（ステップＳ２７０）。
【０１５５】
分割クエリ結合の実施場所パターン生成処理において図１６に示したローカルプラン候補２−１は、図１２に示したローカルプラン候補２とプランの形が入出力変数１４９を除きほぼ同じであり、図１２に示したローカルプラン候補２が入力の場合と同じ動作となるため図１６に示したローカルプラン候補２−１が入力の場合の詳細は省略する。分割クエリ結合の実施場所パターン生成処理の出力リストｆｉｎａｌＰｌａｎＬｉｓｔの内容は図１６、図２０のローカルプラン候補リストとなる。
【０１５６】
次にｆｉｎａｌＰｌａｎＬｉｓｔ内の要素図１６、図２０のローカルプラン候補を出力候補プランリストｏｕｔｐｕｔＬｉｓｔに移す（ステップＳ２９０）。次にｊに３を代入し、ｎｅｘｔＰｌａｎＬｉｓｔの３番目の要素である図１７のローカルプラン候補ｎｅｘｔＰｌａｎを取得する（ステップＳ３００、Ｓ３１０、Ｓ２６０）。次に、ｎｅｘｔＰｌａｎは分割クエリ結合の実施場所パターン生成処理の入力として渡される（ステップＳ２７０）。
【０１５７】
分割クエリ結合の実施場所パターン生成処理において図１７に示したローカルプラン候補２−２は図１２に示したローカルプラン候補２とプランの形が入出力変数１４９を除きほぼ同じであり、図１２に示したローカルプラン候補２が入力の場合と同じ動作となるため図１７に示したローカルプラン候補２−２が入力の場合の詳細は省略する。分割クエリ結合の実施場所パターン生成処理の出力リストｆｉｎａｌＰｌａｎＬｉｓｔの内容は図１７、図２１のローカルプラン候補リストとなる。
【０１５８】
ｆｉｎａｌＰｌａｎＬｉｓｔ内の要素図１７、図２１のローカルプラン候補を出力候補プランリストｏｕｔｐｕｔＬｉｓｔに移す（ステップＳ２９０）。次にｊに４を代入し、ｎｅｘｔＰｌａｎＬｉｓｔの４番目の要素である図１８のローカルプラン候補ｎｅｘｔＰｌａｎを取得する（ステップＳ３００、Ｓ３１０、Ｓ２６０）。次にｎｅｘｔＰｌａｎは分割クエリ結合の実施場所パターン生成処理の入力として渡される（ステップＳ２７０）。
【０１５９】
分割クエリ結合の実施場所パターン生成処理の入力として渡された図１８のローカルプラン候補ｎｅｘｔＰｌａｎを最終候補リストｆｉｎａｌＰｌａｎＬｉｓｔに登録する（図１５のステップＳ７００）。次にｉに１を代入する（ステップＳ７２０）。次にｎｅｘｔＰｌａｎでは変数ｉを１ずつ増やしていくが最後まで分割クエリ結合演算が存在しないのでステップＳ８５０に移る（ステップＳ７２０、Ｓ７３０、Ｓ８３０、Ｓ８４０）。ステップＳ８５０でｆｉｎａｌＰｌａｎＬｉｓｔに登録された図１８に示したローカルプラン候補２−３内において存在する演算内容がｄｕｍｍｙの演算を削除して分割クエリ結合の実施場所パターン生成処理終了する（ステップＳ８５０）。分割クエリ結合の実施場所パターン生成処理の出力リストｆｉｎａｌＰｌａｎＬｉｓｔの内容は、図１９のローカルプラン候補リストとなる。
【０１６０】
ｆｉｎａｌＰｌａｎＬｉｓｔ内の要素図１９のローカルプラン候補２−４を出力候補プランリストｏｕｔｐｕｔＬｉｓｔに移す（ステップＳ２９０）。次にｊに５を代入する（ステップＳ３００）。ｎｅｘｔＰｌａｎＬｉｓｔに登録された要素数は４しかないためｉに２を代入する（ステップＳ３１０、Ｓ３２０）。ｉｎｐｕｔＰｌａｎＬｉｓｔの要素数は１しかないためローカルプラン候補生成処理を終了する。最終的に得られたローカルプラン候補リストｏｕｔｐｕｔＬｉｓｔに登録されたローカルプラン候補は図１６乃至図２１である。
【０１６１】
図１２のローカルプラン候補２では、サーバ間演算に必要な為演算番号３のデータ送信演算によって送信される変数＄zとサーバ間演算と並列に実行する演算４，５によって得られる変数＄ｕ，＄ｖを演算番号７によって計算機２で分割結合している。
【０１６２】
図１６に示したローカルプラン候補２−１は、図１２に示したローカルプラン候補２に対し演算番号４をサーバ間演算と並列実行しないことで演算番号３のデータ送信演算において変数＄ｚと＄ｕを送信し、演算番号７の分割結合で＄ｖと分割結合するようにしたローカルプラン候補である。
【０１６３】
図１７に示したローカルプラン候補２−２、図１２に示したローカルプラン候補２に対し演算番号５をサーバ間演算と並列実行しないことで演算番号３のデータ送信演算において変数＄ｚと＄ｖを送信し、演算番号７の分割結合で＄ｕと分割結合するようにしたローカルプラン候補である。
【０１６４】
図１８に示したローカルプラン候補２−３は、図１２に示したローカルプラン候補２に対し、演算番号４、５をサーバ間演算と並列実行しないことで演算番号３のデータ送信演算において変数＄ｚと＄ｖと＄ｕを送信し分割結合をしないようにしたローカルプラン候補である。
【０１６５】
図１９に示したローカルプラン候補２−４は、図１２に示したローカルプラン候補２に対し実行場所が計算機２ではなく計算機０の場合のローカルプラン候補である。
【０１６６】
図２０に示したローカルプラン候補２−５は、図１６に示したローカルプラン候補２−１に対し実行場所が計算機２ではなく計算機０の場合のローカルプラン候補である。
【０１６７】
図２１に示したローカルプラン候補２−６は、図１７に示したローカルプラン候補２−２に対し実行場所が計算機２ではなく計算機０の場合のローカルプラン候補である。
【０１６８】
以上のようにして、図１２及び図１６乃至図２１に示したローカルプラン候補では、分割結合演算をする場合としない場合のローカルプラン候補、及び分割結合演算をする場合は分割結合する際に対象となる全ての変数の組合せと分割結合の実施場所がマスターサーバかスレーブサーバかの組合せを網羅したローカルプラン候補が生成される。
【０１６９】
ローカルプラン選択部３１はこれらのローカルプラン候補の中から見積もり実行時間または見積もり実行計算量からなるコストを計算し、コストが最小となるローカルプランを選択する（ステップＳ８）。
【０１７０】
ここで、ローカルプラン候補の見積もり実行時間算出の一例を説明する。ローカルプラン候補の見積もり実行時間は、例えば、図２２に挙げた各演算の処理見積もり時間用のパラメータと、ローカルプランに含まれる演算に基づいて算出される。
【０１７１】
各演算のパラメータは、例えば、「数値索引：０．００１ｍｓｅｃ／出力変数の件数」、「ＴＲＡＶＥＲＳＥ：１ｍｓｅｃ／入力変数の件数」、「分割クエリ結合：１ｍｓｅｃ／入力変数の件数」、「サーバ間ＪＯＩＮ：１ｍｓｅｃ／入力変数の件数」、「データ送信５ｍｓｅｃ＋（０．００１ｍｓｅｃ／入力変数の件数）×変数の数」、「データ受信５ｍｓｅｃ＋（０．００１ｍｓｅｃ／入力変数の件数）×変数の数」、などである。なお、演算内容によって出力変数に格納する件数をあらかじめ設定する。
【０１７２】
ここで、図１２に示したローカルプラン候補２における見積もり時間の算出処理の一例を以下に説明する。なお、図４から計算機２では１万件のＸＭＬデータが登録されていることがわかるため、これにより各演算の見積もり実行時間を計算する。
【０１７３】
（１）数値索引で"＞＝"演算を利用する場合は、全体の１０％がヒットすると見積もる。そのため１万件の１０％で１０００件ヒットすると見積もる。したがって、数値索引の見積もり計算時間は、０．００１ｍｓｅｃ／出力変数の件数×１０００件＝１ｍｓｅｃとなる。
【０１７４】
（２）ＴＲＡＶＥＲＳＥの入力変数の件数は（１）の結果から１０００件と見積もる。出力は変わらないものと想定して１０００件と見積もる。したがって、ＴＲＡＶＥＲＳＥの見積もり計算時間は、１ｍｓｅｃ／入力変数の件数×１０００件＝１０００ｍｓｅｃとなる。
【０１７５】
（３）データ送信の入力変数の件数は、（２）の結果から１０００件と見積もる。したがって、データ送信の見積もり計算時間は、５ｍｓｅｃ＋０．００１ｍｓｅｃ／入力変数の件数×１０００× １＝６ｍｓｅｃとなる。
【０１７６】
（４）ＴＲＡＶＥＲＳＥの入力変数の件数は（２）の結果から１０００件と見積もる。出力は変わらないものと想定して１０００件と見積もる。したがって、ＴＲＡＶＥＲＳＥの見積もり計算時間は、１ｍｓｅｃ／入力変数の件数×１０００件＝１０００ｍｓｅｃとなる。
【０１７７】
（５）ＴＲＡＶＥＲＳＥの入力変数の件数は（４）の結果から１０００件と見積もる。出力は変わらないものと想定して１０００件と見積もる。したがって、ＴＲＡＶＥＲＳＥの見積もり計算時間は、１ｍｓｅｃ／入力変数の件数×１０００件＝１０００ｍｓｅｃとなる。
【０１７８】
（６）データ受信の入力変数の件数は、マスターサーバでサーバ間ＪＯＩＮが実行されて４０％に削減されて４００件と見積もる。したがって、データ受信の見積もり計算時間は、５ｍｓｅｃ＋０．００１ｍｓｅｃ／入力変数の件数×４００× １≒６ｍｓｅｃとなる。
【０１７９】
（７）分割クエリ結合の入力件数は（５），（６）から計１４００件と見積もる。したがって、分割クエリ結合の見積もり計算時間は、１ｍｓｅｃ／入力変数の件数×１４００件＝１４００ｍｓｅｃとなる。
【０１８０】
（８）（３）でマスターサーバへデータ送信後、マスターサーバでは図１１の分散プランの演算番号１０のサーバ間ＪＯＩＮが実行される。ここではサーバ間ＪＯＩＮの見積もり計算時間は、分散プラン生成部１３でローカルプラン候補の見積もり計算時間と同様の考え方で計算された後、スレーブサーバに分散プランと共に送られているものとする。分散プラン生成部１３では、サーバ間ＪＯＩＮの入力件数は各スレーブサーバの登録データ数の１／３程度と仮定して計算する。したがって、サーバ間ＪＯＩＮの見積もり時間は１ｍｓｅｃ／入力変数の件数×１１２５０件÷３＝３７５０ｍｓｅｃとなる。
【０１８１】
なお、図１１において、分割クエリ結合演算追加部１４により演算番号１０のサーバ間ＪＯＩＮと並列に実行可能な演算として挙げられた、演算番号４，５のサーバ内演算は、ローカルプラン候補２の演算番号４，５のＴＲＡＶＥＲＳＥに該当する。このため演算番号４，５と、演算番号３，６及びサーバ間ＪＯＩＮは並行して実施することが分かるので、ローカルプラン候補２の見積もり時間は以下の２つの見積もり時間の長い方になる。
【０１８２】
（１）＋（２）＋（３）＋（８）＋（６）＋（７）＝６１６３ｍｓｅｃ
（１）＋（２）＋（４）＋（５）＋（７）＝４４０１ｍｓｅｃ
結果として６１６３ｍｓｅｃと見積もる。
【０１８３】
別の例としてローカルプラン候補２−３を計算機２で実行する際は全処理が並列に実行できないので、見積もり時間は、（１）、（２）、（３）、（４）、および（５）の演算とサーバ間ＪＯＩＮを合わせたものになる。すなわち、
１ｍｓｅｃ＋１０００ｍｓｅｃ＋１０００ｍｓｅｃ＋１０００ｍｓｅｃ＋６ｍｓｅｃ＋３７５０ｍｓｅｃ＝６７５７ｍｓｅｃ
となりローカルプラン候補２の方がサーバ間ＪＯＩＮを含めると速くなると計算される。このようにローカルプラン候補の見積もり計算時間に、マスターサーバで実行するサーバ間演算の見積もり時間も加えることで、分割クエリ結合演算追加部で追加した分割クエリ結合による最適化が有効かを判断できる。
【０１８４】
本実施形態では、計算機１は図１８に示すローカルプラン候補２−３を、計算機２は図１２に示すローカルプラン候補２を、計算機３は図１９に示すローカルプラン候補２−４をそれぞれローカルプランとして選んだものとする。
【０１８５】
各計算機のローカルプラン選択部３１は、選択したローカルプランをマスターサーバの分散プラン更新部１５に送信する。ローカルプラン選択部３１が、選択したローカルプランを分散プラン更新部１５に送信すると、スレーブサーバは、対象のローカルプランを実行する（ステップＳ９）。
【０１８６】
スレーブサーバの行うステップＳ９と並行して、ローカルプランを受信したマスターサーバの分散プラン更新部１５は分散プラン更新処理を行う（ステップＳ１０）。
【０１８７】
ここで、マスターサーバの分散プラン更新部１５が、図１１の分散プランに対し、計算機１、計算機２、計算機３がそれぞれ図１８、図１２、図１９のローカルプラン候補を選んだ場合に、図２３のフローチャートに従って分散プランの更新を行う場合の分散プラン更新処理について説明する。なお、この分散プラン更新処理はｉという変数を用いる。ｉは１以上であり、かつ、対象のスレーブサーバ数以下である（１≦ｉ≦スレーブサーバ数）。
【０１８８】
処理の開始時点ではｉ＝１である。また、スレーブサーバ数＝ｍａｘとする（ステップＳ９００）。
【０１８９】
分散プラン更新部１５は、計算機番号ｉのローカルプランＬＰｌａｎを取得する（ステップＳ９１０）。次に分散プランとローカルプランの分割クエリ結合に関する差分をチェックする（ステップＳ９２０）。差分チェックによりＬＰｌａｎでは分割クエリ結合が完全に削除されているかを判定する（ステップＳ９３０）。
【０１９０】
ＬＰｌａｎで分割クエリ結合が完全に削除されていた場合（ステップＳ９３０がＹｅｓ）、分散プランにある分割クエリ結合及びその前後にあるデータ送信演算、データ受信演算の実行場所から計算機ｉを削除する（ステップＳ９４０）。次に削除した結果分割クエリ結合演算の実行場所が空かを判定する（ステップＳ９５０）。
【０１９１】
分割クエリ結合演算の実行場所が空の場合（ステップＳ９５０がＹｅｓ）、分散プランにある分割クエリ結合及びその前後にあるデータ送信演算、データ受信演算を削除する（ステップＳ９６０）。次に、ステップＳ９７０に進む。
【０１９２】
また分割クエリ結合演算の実行場所が空でない場合（ステップＳ９５０がＮｏ）、ステップＳ９７０に進む。さらにＬＰｌａｎで分割クエリ結合が完全に削除されていない場合（ステップＳ９３０がＮｏ）、ステップＳ９７０に進む。すなわちステップＳ９７０の処理は、ステップＳ９３０がＮｏの場合、もしくはステップＳ９５０がＮｏの場合、もしくはステップＳ９６０に続いて行われる。ステップＳ９７０では、ＬＰｌａｎで分割クエリ結合の実行場所が変更されたかを判定する。
【０１９３】
ＬＰｌａｎで分割クエリ結合の実行場所が変更された場合（ステップＳ９７０がＹｅｓ）、分散プランにある分割クエリ結合、その前後にあるデータ送信演算、およびデータ受信演算の実行場所から計算機ｉを削除する（ステップＳ９８０）。次に削除した結果分割クエリ結合演算の実行場所が空かを判定する（ステップＳ９９０）。
【０１９４】
分割クエリ結合演算の実行場所が空の場合（ステップＳ９９０がＹｅｓ）、分散プランにある分割クエリ結合及びその前後にあるデータ送信演算、データ受信演算を削除する（ステップＳ１０００）。次に、ステップＳ９９０に進む。
【０１９５】
また分割クエリ結合演算の実行場所が空でない場合（ステップＳ９９０がＮｏ）、ステップＳ１０１０に進む。すなわちステップＳ１０１０の処理はステップＳ９９０がＮｏの場合もしくはステップＳ１０００に続いて行われる。ステップＳ１０１０ではＬＰｌａｎの実行場所を変更した分割クエリ結合が分散プラン内に既に存在するかを判定する。
【０１９６】
ＬＰｌａｎの実行場所を変更した分割クエリ結合が分散プラン内に既に存在しない場合（ステップＳ１０１０がＮｏ）、実行場所を変更した分割クエリ結合、及びその前後にあるデータ送信、データ受信の演算を分散プランに追加する（ステップＳ１０３０）。次にステップＳ１０４０に進む。
【０１９７】
またＬＰｌａｎの実行場所を変更した分割クエリ結合が分散プラン内に既に存在する場合（ステップＳ１０１０がＮｏ）、実行場所に計算機ｉを追加する（ステップＳ１０２０）。次にステップＳ１０４０に進む。
【０１９８】
さらにＬＰｌａｎで分割クエリ結合の実行場所が変更なかった場合（ステップＳ９７０がＮｏ）、ステップＳ１０４０に進む。すなわちステップＳ１０４０の処理はステップＳ９７０がＮｏの場合、またはステップＳ１０２０に続いて、またはステップＳ１０３０に続いて行われる。ステップＳ１０４０ではｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ１０４０）。
【０１９９】
次にｉがｍａｘ以下かを判定する（ステップＳ１０５０）。ｉがｍａｘ以下の場合（ステップＳ１０５０がＹｅｓ）、ステップＳ９１０に戻り処理を繰り返す。ｉがｍａｘより大きい場合は終了する。
【０２００】
図１１に示した分散プランに対して、計算機１、２、３のローカルプランがそれぞれローカルプラン候補２−３、ローカルプラン候補２、ローカルプラン候補２−４の場合において、上述した分散プラン更新処理が行われた結果、得られる分散プランを図２４に示す。
【０２０１】
図２４に示した分散プラン３は、「演算番号」３１２、「部分クエリ番号」３１３、「演算内容」３１４、「事前実行演算番号」３１５、「実行場所」３１６、「送信場所」３１７、「入力変数」３１８、「出力変数」３１９の項目を有する。この分散プラン３は有する項目３１２乃至３１９は、分散プランテーブル１４１の有する項目１４２乃至１４９及びローカルプラン候補２、２−１乃至２−６が有する項目３０２乃至３０９と同一である。
【０２０２】
まずｉに１を代入して、計算機１の選択したローカルプランであるローカルプラン候補２−３と図１１の分散プランの分割クエリ結合に関する差分をチェックする（ステップＳ９００、Ｓ９１０、Ｓ９２０）。ローカルプラン候補２−３では、計算機１の分割クエリ結合は完全に削除されているため、図１１の分散プランの分割クエリ結合及びその前後にあるデータ送信、データ受信演算（図２４の演算番号１１−１５）の実行場所から計算機１を削除する（ステップＳ９４０）。
【０２０３】
次に、分散プラン更新部１５は分割クエリ結合の実行場所は空ではないため、ローカルプラン候補２−３をチェックして分割クエリ結合の実行場所が変更されていないかチェックする（ステップＳ９５０、Ｓ９７０）。実行場所は変更されていないため、ｉに２を代入する（ステップＳ１０４０、Ｓ１０５０）。
【０２０４】
次にｉが２として図１１の分散プランと、計算機２の選択したローカルプランであるローカルプラン候補２とにおける分割クエリ結合に関する差分をチェックする（ステップＳ９２０）。図１２に示したローカルプラン候補２は、計算機２の分割クエリ結合は削除もされず、実行場所も変わらないため、ｉに３を代入する（ステップＳ９３０、Ｓ９７０、Ｓ１０４０、Ｓ１０５０）。
【０２０５】
次にｉが３として図１１の分散プランと計算機３の選択したローカルプランであるローカルプラン候補２−４の分割クエリ結合に関する差分をチェックする（ステップＳ９２０）。ローカルプラン候補２−４は、計算機３の分割クエリ結合は削除されていないため、次に分割クエリ結合の実行場所が変更されているかをチェックする（ステップＳ９３０、Ｓ９７０）。
【０２０６】
また、ローカルプラン候補２−４は、分割クエリ結合の実行場所が変更されているため、分散プランの分割クエリ結合及びその前後にあるデータ送信、データ受信演算（図２４の演算番号１１−１５）の実行場所から計算機３を削除する（ステップＳ９８０）。分割クエリ結合の実行場所は空ではないため、分散プラン更新部１５は、次に実行場所を変更した分割クエリ結合が分散プランに挿入されているかを確認する（ステップＳ９８０、Ｓ１０１０）。分散プランには挿入されていないため、実行場所を変更した分割クエリ結合及びその前後にあるデータ送信、データ受信演算を分散プランに挿入する（図２４の演算番号１４、１５、１６）（ステップＳ１０３０）。次にｉに４を代入するが、計算機数は３までなので処理を終了する（ステップＳ１０４０、Ｓ１０５０）。最終的に図２４の分散プラン３が得られる。
【０２０７】
分散プラン実行部１６は、分散プラン３の演算を実行する（図６のステップＳ１１）。なお、分散プラン３の実行と、スレーブサーバのローカルプラン実行部３３の実行とは、お互いデータの送受信で依存関係にあり、例えば並列に実行したり、相手からデータが送信されるのを待ったりする。すなわち、マスターサーバの送受信部１７とスレーブサーバの送受信部３４とがデータのやり取りを行いながら分散プランは実行される。
【０２０８】
上述したように、本実施形態によれば、ユーザによってマスターサーバに入力された問合せクエリに対して、マスターサーバは部分クエリの結合処理を除いたサーバ間演算に関連する部分の最適化のみを実施し、部分クエリの結合の最適化はスレーブサーバが実施する。すなわち、マスターサーバは部分クエリの結合処理を最適化の範囲から除外することが可能となるため、全てをマスターサーバ側で最適化する場合と比較して単純な仕組みで実現することが可能となる。
【０２０９】
すなわち、マスターサーバはスレーブサーバが決定する部分クエリの結合処理に依存しない形で部分クエリの結合処理を仮に決定する。スレーブサーバは、サーバ毎のデータベース情報に基づいて部分クエリの結合処理を最適化する。さらに、マスターサーバは、スレーブサーバがこの部分クエリの結合処理の結果をマスターサーバに通知することよって、効率の良い分散プランを生成する。また、分割クエリ結合演算に関してスレーブサーバ側が最適化するため、各スレーブサーバに適した効率のよいプランの生成が可能となる。
【０２１０】
したがって、本発明の実施形態によれば、問合せクエリ５１について、マスターサーバが決定する分散プランの範囲から、分割クエリ結合演算に関する演算を取り除くことで、マスターサーバの分散プラン最適化の仕組みを簡素化した上で、スレーブサーバが各々に最適な形で上記の範囲の最適化を実施する。これにより、効率的なクエリ処理を実現することが可能となる。
【０２１１】
（第２の実施形態）
第２の実施形態の分散データベース検索装置について図面を参照して説明する。なお、第１の実施形態の分散データベース検索装置と同一の構成には同一の符号を付し、説明は省略する。
【０２１２】
図２５は、第２の実施形態の分散データベース検索装置の機能構成を示す構成図である。図２５に示すように、本実施形態の分散データベース検索装置は、図１に示した分散データベース検索装置の構成にスキーマ生成部１８、３５とスキーマ変更部１９、３６をさらに有する構成である。
【０２１３】
スキーマとは格納するデータの種類や位置情報を保持するものデータの構造のことである。
【０２１４】
スキーマ生成部１８、３５は各サーバにおいて行われる演算の結果、入出力されるデータのスキーマを生成する。例えば、マスターサーバが備えるスキーマ生成部１８は、分散プランの各演算の入出力データのスキーマを生成する。また、スレーブサーバが備えるスキーマ生成部３５は、ローカルプランの各演算の入出力データのスキーマを生成する。
【０２１５】
スキーマ変更部１９、３６は、分散プランまたはローカルプランの各演算によって得られたデータを次の演算に渡す際に、当該データのスキーマを変更する。マスターサーバのスキーマ変更部１９は、分散プランまたはローカルプランの各演算の出力によって得られたデータを、分散プランの次の演算の入力に渡す際にデータのスキーマを変更する。スレーブサーバのスキーマ変更部３６は、分散プランまたはローカルプランの各演算の出力によって得られたデータを、ローカルプランの次の演算に渡す際に、当該データのスキーマを変更する。
【０２１６】
ここで、図２６に本実施形態におけるスキーマ変更部１９によって変更される前のスキーマに含まれる項目の一例を示す。変更される前のスキーマとは、すなわち後述するスキーマ生成部１８によって生成されるスキーマである。スキーマとは格納するデータの種類や位置情報を保持するものであり、図２６に示すように本実施形態では、「可変領域」４０１と、「変数〜」４０２−ｉ（ｉは１以上の整数）と「拡張変数＄＃ｅ（Ｖ１・・・，Ｖｎ）」４０３の項目を有する。
【０２１７】
「拡張変数＄＃ｅ（Ｖ１,・・・，Ｖｎ）」４０３の「＄＃ｅ」は「変数〜」４０２−ｉの「〜」に一致しない一意の文字列が入り、「（Ｖ１,・・・，Ｖｎ）」には「，」で区切られたｎ個の一意になる任意の文字列が入る。「可変領域」４０１とはサーバ間でデータを送る際にカラム数の違いを吸収するためのデータを格納する項目である。「変数〜」４０２−ｉは各変数のデータを格納する項目で「拡張変数＄＃ｅ（Ｖ１,・・・，Ｖｎ）」４０３は変数「Ｖ１」から変数「Ｖｎ」の全変数のデータを格納する項目である。なお、「変数〜」４０２−ｉは入出力されるデータ毎にさまざまな変数が格納される。
【０２１８】
ここで、図２７を参照して、本実施形態の分散データベース検索装置の検索処理の一例について説明する。図２７は、本実施形態の分散データベース検索装置の検索処理の一例を示すフローチャートである。なお、ステップＳ１至Ｓ８及び，Ｓ１０の処理については図６に示したフローチャートと同じであるため説明を割愛する。
【０２１９】
ローカルプラン選択部３７は、図２７のステップＳ１−Ｓ８でローカルプランを決定した後、決定したローカルプランに実行順序が非決定的な部分を確定するローカルプラン順序決定処理を実施する（ステップＳ１２）。ここで、実行順序が非決定的な部分とはローカルプランの各演算の事前実行番号が等しい演算の集合である。これらの演算はどの順序で実行するかの指定がないため任意の順序で実行可能である。すなわち、ローカルプラン順序決定処理によって、でこれらの演算の実行順序を一意に決定される。
【０２２０】
図２８に、図１２で示したローカルプラン候補２がローカルプラン順序決定処理（ステップＳ１２）により非決定的な演算集合の順序を一意に決定された結果を示す。図１２に示したローカルプラン候補２では演算番号２、４、５の各演算の事前実行番号は１であり実行順序が非決定的である。図２９では演算番号２、４、５の順序で実行するように決定し、演算番号４の事前実行番号を１から２、演算番号５の事前実行番号を１から４に書き換えている。
【０２２１】
ステップＳ１２におけるローカルプラン順序決定処理後、演算の順序が決定されたローカルプランは送信部３４によってマスターサーバに送信される。マスターサーバは当該ローカルプランを受信すると、分散プラン更新部１０が分散プラン更新処理を行う（ステップＳ１０）。ステップＳ１０と並行して、スレーブサーバのスキーマ生成部３５が、当該ローカルプラン内の各演算の入力スキーマおよび出力スキーマ（以下、入出力スキーマという）を生成する（ステップＳ１４）。入力スキーマとは、入力されるデータのスキーマである。出力スキーマとは演算で出力されるデータのスキーマである。
【０２２２】
ここで図２９を参照して、スキーマ生成部３５が、図２８に示したローカルプランに対して、スキーマ生成処理（ステップＳ１４）を行う際の動作について具体的に説明する。
【０２２３】
なお、このスキーマ生成処理ではｉという変数を用いる。ｉは１以上の整数であり、対象のローカルプランの演算番号以下である（１≦ｉ≦ローカルプランの演算番号の最大値）。また、スキーマ生成処理の開始時点ではｉ＝１である。また、ローカルプランの演算番号の最大値を「ｍａｘ」とする。また、演算番号３０１がｉのローカルプランの演算を演算Ｓとする。
【０２２４】
スキーマ生成部３５は、ローカルプラン選択部３１からローカルプランを受信すると、まず、初期化処理としてｉ＝１、ローカルプランの演算番号の最大値＝ｍａｘとする（ステップＳ１１１０）。次に、ｉがｍａｘ以下であるか否かを判定する（ステップＳ１１１０）。
【０２２５】
ｉがｍａｘ以下である場合（ステップＳ１１１０がＹｅｓ）、演算番号ｉの演算Ｓを取得する（ステップＳ１１２０）。次に演算Ｓに出力変数があるかを判定する（ステップＳ１１３０）。
【０２２６】
演算Ｓに出力変数がある場合（ステップＳ１１３０がＹｅｓ）、演算Ｓの出力変数を出力スキーマと変数リストＶＬに追加する。さらに変数毎に到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１４０）。次に各演算の事前実行番号から、演算Ｓと演算Ｓより後に実行される演算番号のリストＡＬを取得する（ステップＳ１１５０）。次に、演算Ｓの各出力変数に対して、変数毎に用意した到達演算番号リストＲＬにリストＡＬに格納された演算番号を登録する（ステップＳ１１６０）。その後ステップＳ１１７０に進む。なお、演算Ｓに出力変数がない場合（ステップＳ１１３０がＮｏ）もステップＳ１１７０に進む。
【０２２７】
ステップＳ１１７０では演算Ｓに入力変数があるかを判定する（ステップＳ１１７０）。
【０２２８】
演算Ｓに入力変数がある場合（ステップＳ１１７０がＹｅｓ）、演算Ｓの事前実行演算番号を辿り、演算Ｓより前に実行される演算番号のリストＢＬを取得する（ステップＳ１１８０）。次に演算Ｓの各入力変数に対して、変数毎に用意した利用演算番号リストＵＬにリストＢＬに格納された演算番号を登録する（ステップＳ１２００）。その後ステップＳ１２１０に進む。なお、演算Ｓに入力変数がない場合（ステップＳ１１７０がＮｏ）もステップＳ１２１０に進む。
【０２２９】
ステップＳ１２１０ではｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ１２１０）。次にステップＳ１１１０に戻る。
【０２３０】
ｉがｍａｘより大きい場合（ステップＳ１１１０がＮｏ）、ステップＳ１２２０に進む。
【０２３１】
ここで、ｊという変数を用いる。ｊは１以上であり、かつ、変数リストＶＬ内の要素数以下である（１≦ｊ≦ＶＬ内の要素数）。また、この時ｊ＝１であり、ＶＬ内の要素数＝ｖｍａｘとする（ステップＳ１２２０）。次に、ｊがｖｍａｘ以下であるか否かを判定する（ステップＳ１２３０）。
【０２３２】
ｊがｖｍａｘ以下である場合（ステップＳ１２３０がＹｅｓ）、変数リストＶＬからｊ番目の変数ｖａｒを取得する（ステップＳ１２４０）。次に変数ｖａｒの到達演算番号リストＲＬと利用番号リストＵＬに共通して出現する演算番号リストＣＬを取得する（ステップＳ１２５０）。次にリストＣＬ内の演算番号の各演算の出力スキーマに変数ｖａｒを追加する（ステップＳ１２６０）。次にｊにｊ＋１を代入する（ｊ：＝ｊ＋１）（ステップＳ１２７０）。次にステップＳ１２３０に戻る。
【０２３３】
ｊがｖｍａｘより大きい場合（ステップＳ１２３０がＮｏ）、ｉに１を代入する（ｉ：＝１）（ステップＳ１２８０）。次に、ｉがｍａｘ以下であるか否かを判定する（ステップＳ１２９０）。
【０２３４】
ｉがｍａｘ以下である場合（ステップＳ１２９０がＹｅｓ）、演算番号ｉの演算Ｓを取得する（ステップＳ１３００）。次に演算Ｓの入力スキーマに事前実行演算番号の演算の出力スキーマをコピーする（ステップＳ１３１０）。次に演算Ｓの出力スキーマの先頭に可変領域を、最後尾に拡張変数＄＃ｅ（）を追加する（ステップＳ１３２０）。次にｉにｉ＋１を代入する（ｉ：＝ｉ＋１）（ステップＳ１３３０）。次にステップＳ１２９０に戻る。
【０２３５】
ｉがｍａｘより大きい場合（ステップＳ１２９０がＮｏ）、処理を終了する。なお、図２９で示したフローチャートは、スレーブサーバのスキーマ生成部１８におけるスキーマ生成処理Ｓ１５においても対象がローカルプランであるか分散プランであるかの違いのみで同様に動作する。
【０２３６】
ここで、図３０に、図２８で示したローカルプラン順序決定処理で得られたローカルプランにおいて、上述したスキーマ生成処理が行われた結果得られる入出力スキーマの一例を示す。図３０に示した入出力スキーマテーブル５００は、演算番号５００、入力スキーマ１、入力スキーマ２、出力スキーマ５０２の項目を示す。
【０２３７】
入出力スキーマテーブル５００の演算番号５０１には、スキーマ生成処理が行われたプランの演算番号と対応した演算番号が格納される。
【０２３８】
入力スキーマ１は、スキーマ生成処理において生成された入力スキーマの１つ目が格納される。入力スキーマ２は、スキーマ生成処理において生成された入力スキーマの２つ目の入力スキーマが格納される。
【０２３９】
出力スキーマ５０４は、スキーマ生成処理において生成された出力スキーマが格納される。
【０２４０】
スキーマ生成処理部１８が、この入出力スキーマテーブル５００を算出する処理を具体的に説明する。まず図２８のローカルプランが、スキーマ生成処理の入力として渡される。次にｉに１を、ｍａｘに８を代入する（ステップＳ１１００）。次にｉがｍａｘ以下であるため演算番号１の演算Ｓを取得する（ステップＳ１１１０、Ｓ１１２０）。演算Ｓは出力変数＄ｘを持つ為＄ｘを出力スキーマ５０４と変数リストＶＬに追加する。さらに＄ｘに対する到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１３０、Ｓ１１４０）。次に事前実行番号を辿り演算Ｓの演算番号１と演算Ｓより後に実行される演算番号２−８を到達番号リストＲＬに格納する（ステップＳ１１５０、Ｓ１１６０）。演算Ｓは入力変数を持たないためｉに２を代入し、演算番号２の演算Ｓを取得する（ステップＳ１２１０、Ｓ１１１０、Ｓ１１２０）。
【０２４１】
演算Ｓは出力変数＄ｚを持つ為＄ｚを出力スキーマ５０４と変数リストＶＬに追加する。さらに＄ｚに対する到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１３０、Ｓ１１４０）。次に事前実行番号を辿り演算Ｓの演算番号２と演算Ｓより後に実行される演算番号３−８を到達番号リストＲＬに格納する（ステップＳ１１５０、Ｓ１１６０）。次に演算Ｓは入力変数＄ｘを持つ為、Ｓより前に実行された演算番号１を利用演算番号ＵＬに登録する。（ステップＳ１１７０、Ｓ１１８０、Ｓ１２００）。次に演算番号３の演算Ｓを取得する（ステップＳ１２１０、Ｓ１１１０、Ｓ１１２０）。
【０２４２】
演算Ｓは出力変数＄ｚを持つ為＄ｚを出力スキーマ５０４と変数リストＶＬに追加する。さらに＄ｚに対する到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１３０、Ｓ１１４０）。次に事前実行番号を辿り演算Ｓの演算番号３と演算Ｓより後に実行される演算番号３、６−８を到達番号リストＲＬに格納する（ステップＳ１１５０、Ｓ１１６０）。次に入力変数＄ｚを持つ為、Ｓより前に実行された演算番号１、２を＄ｚの利用演算番号ＵＬに登録する。（ステップＳ１１３０、Ｓ１１７０、Ｓ１１８０、Ｓ１２００）。次に演算番号４の演算Ｓを取得する（ステップＳ１２１０、Ｓ１１１０、Ｓ１１２０）。
【０２４３】
演算Ｓは出力変数＄ｕを持つ為＄ｕを出力スキーマ５０４と変数リストＶＬに追加する。さらに＄ｕに対する到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１３０、Ｓ１１４０）。次に事前実行番号を辿り演算Ｓの演算番号４と演算Ｓより後に実行される演算番号５、７、８を到達番号リストＲＬに格納する（ステップＳ１１５０、Ｓ１１６０）。次に演算Ｓは入力変数＄ｘを持つ為、Ｓより前に実行された演算番号１、２を利用演算番号ＵＬに登録する。（ステップＳ１１７０、Ｓ１１８０、Ｓ１２００）。次に演算番号５の演算Ｓを取得する（ステップＳ１２１０、Ｓ１１１０、Ｓ１１２０）。
【０２４４】
演算Ｓは出力変数＄ｖを持つ為＄ｖを出力スキーマ５０４と変数リストＶＬに追加する。さらに＄ｖに対する到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１３０、Ｓ１１４０）。次に事前実行番号を辿り演算Ｓの演算番号５と演算Ｓより後に実行される演算番号７、８を到達番号リストＲＬに格納する（ステップＳ１１５０、Ｓ１１６０）。次に演算Ｓは入力変数＄ｘを持つ為、Ｓより前に実行された演算番号１、２、４を利用演算番号ＵＬに登録する。（ステップＳ１１７０、Ｓ１１８０、Ｓ１２００）。次に演算番号６の演算Ｓを取得する（ステップＳ１２１０、Ｓ１１１０、Ｓ１１２０）。
【０２４５】
演算Ｓは出力変数＄ｚを持つ為＄ｚを出力スキーマ５０４と変数リストＶＬに追加する。さらに＄ｚに対する。到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１３０、Ｓ１１４０）。次に事前実行番号を辿り演算Ｓの演算番号６と演算Ｓより後に実行される演算番号７、８を到達番号リストＲＬに格納する（ステップＳ１１５０、Ｓ１１６０）。次に、入力変数＄ｚを持つ為、Ｓより前に実行された演算番号１−３を＄ｚの利用演算番号ＵＬに登録する。（ステップＳ１１３０、Ｓ１１７０、Ｓ１１８０、Ｓ１２００）。次に演算番号７の演算Ｓを取得する（ステップＳ１２１０、Ｓ１１１０、Ｓ１１２０）。
【０２４６】
演算Ｓは出力変数を持たず、入力変数＄ｚを持つ為、Ｓより前に実行された演算番号１−６を＄ｚの利用演算番号ＵＬに登録する。（ステップＳ１１３０、Ｓ１１７０、Ｓ１１８０、Ｓ１２００）。次に演算番号８の演算Ｓを取得する（ステップＳ１２１０、Ｓ１１１０、Ｓ１１２０）。
【０２４７】
演算Ｓは出力変数＄ｕと＄ｖを持つ為＄ｕと＄ｖを出力スキーマ５０４と変数リストＶＬに追加する。さらに＄ｕと＄ｖに対する。到達番号リストＲＬと利用番号リストＵＬを用意する（ステップＳ１１３０、Ｓ１１４０）。次に事前実行番号を辿り演算Ｓの演算番号８を到達番号リストＲＬに格納する（ステップＳ１１５０、Ｓ１１６０）。次に、入力変数＄ｕ、＄ｖを持つ為、Ｓより前に実行された演算番号１−７を＄ｕ、＄ｖの利用演算番号ＵＬに登録する。（ステップＳ１１３０、Ｓ１１７０、Ｓ１１８０、Ｓ１２００）。次にｉがｍａｘを超えたためｊに１を、ｖｍａｘにＶＬの要素数４を代入する（ステップＳ１２１０、Ｓ１１１０、Ｓ１２２０）。次に変数リストの１番目の要素である変数＄ｘを取得する（ステップＳ１２３０，Ｓ１２４０）。
【０２４８】
変数＄ｘの利用番号リストＵＬの各要素は１、２、４、到達演算番号ＲＬは１−８であるため共通して出現する演算番号１、２、４の出力スキーマ５０４に＄ｘを追加する（ステップＳ１２５０、Ｓ１２６０）。次にＶＬの２番目の変数＄ｚを取得する（ステップＳ１２７０、Ｓ１２３０、Ｓ１２４０）。
【０２４９】
変数＄ｚの利用番号リストＵＬの各要素は１−６、到達演算番号ＲＬは２−８であるため共通して出現する演算番号２−６、の出力スキーマ５０４に＄ｚを追加する（ステップＳ１２５０、Ｓ１２６０）。次にＶＬの３番目の変数＄ｕを取得する（ステップＳ１２７０、Ｓ１２３０、Ｓ１２４０）。
【０２５０】
変数＄ｕの利用番号リストＵＬの各要素は１−７、到達演算番号ＲＬは４、５、７、８であるため共通して出現する演算番号４、５、７、の出力スキーマ５０４に＄ｕを追加する（ステップＳ１２５０、Ｓ１２６０）。次にＶＬの４番目の変数＄ｖを取得する（ステップＳ１２７０、Ｓ１２３０、Ｓ１２４０）。
【０２５１】
変数＄ｖの利用番号リストＵＬの各要素は１−７、到達演算番号ＲＬは５、７、８であるため共通して出現する演算番号５、７、の出力スキーマ５０４に＄ｖを追加する（ステップＳ１２５０、Ｓ１２６０）。次にｉに１を代入し、演算番号１の演算Ｓを取得する（ステップＳ１２７０、Ｓ１２３０、Ｓ１２８０）。
【０２５２】
演算番号１は入力がないため、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して、演算番号２の演算Ｓを取得する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。
【０２５３】
演算番号２の入力スキーマ１に演算番号１の出力スキーマ５０４をコピーし、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して、演算番号３の演算Ｓを取得する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。
【０２５４】
演算番号３の入力スキーマ１に演算番号２の出力スキーマ５０４をコピーし、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して、演算番号４の演算Ｓを取得する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。
【０２５５】
演算番号４の入力スキーマ１に演算番号２の出力スキーマ５０４をコピーし、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して、演算番号５の演算Ｓを取得する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。
【０２５６】
演算番号５の入力スキーマ１に演算番号４の出力スキーマ５０４をコピーし、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して、演算番号６の演算Ｓを取得する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。
【０２５７】
演算番号６の入力スキーマ１に演算番号３の出力スキーマ５０４をコピーし、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して、演算番号７の演算Ｓを取得する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。
【０２５８】
演算番号７の入力スキーマ１に演算番号５の出力スキーマ５０４を、入力スキーマ２に演算番号６の出力スキーマ５０４を各々コピーし、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して、演算番号８の演算Ｓを取得する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。
【０２５９】
演算番号８の入力スキーマ１に演算番号７の出力スキーマ５０４をコピーし、出力スキーマ５０４に可変領域と拡張変数＄＃ｅ（）を追加して終了する（ステップＳ１３００−Ｓ１３２０、Ｓ１２８０、Ｓ１２９０）。スキーマ生成処理の出力結果の一例は、図３０にした入出力スキーマテーブル５００である。なお、図３０では入力スキーマが１つだけの場合は入力スキーマ１の項目に、２つある場合は２つ目を入力スキーマ２の項目に格納しているが、入力スキーマの項目は必要に応じて増やしたり減らしたりしても良い。
【０２６０】
ここで、ステップＳ１４と並行して実行されるマスターサーバの処理について説明する。分散プラン生成部２３は、分散プラン更新処理を行い（ステップＳ１０）、分散プランを更新した後、更新した分散プランに基づいて実行順序が非決定的な部分を確定する分散プラン順序決定処理を実施する（ステップＳ１３）。ステップＳ１３の分散プラン順序決定処理は対象のプランがローカルプランではなく分散プランである以外はステップＳ１２と同じである。
【０２６１】
次に、スキーマ生成部１８は、決定した分散プラン内の各演算の入出力スキーマを生成する（ステップＳ１５）。ステップＳ１５のスキーマ生成処理は対象のプランがローカルプランではなく分散プランである以外はステップＳ１４と同じである。
【０２６２】
マスターサーバとスレーブサーバのそれぞれで、スキーマ生成処理が行われると、マスターサーバとスレーブサーバのそれぞれは生成された入出力スキーマに基づいてプランを実行する。すなわち、スレーブサーバのローカルプラン実行部３６は、スキーマ生成処理（ステップＳ１４）で生成された入出力スキーマを元にローカルプランを実行する（ステップＳ９）。また、マスターサーバの分散プラン実行部１６は、スキーマ生成処理（ステップＳ１５）で生成されたスキーマを元に、分散プランを実行する（ステップＳ１１）。
【０２６３】
ローカルプラン実行（ステップＳ９）では、ローカルプラン実行部３３は、ローカルプランの各演算を実施する際に、入力されるデータと用意した入力スキーマをスキーマ変更部３６に渡してスキーマ変更処理を実施する（ステップＳ１６）。また分散プラン実行（ステップＳ１１）においても同様に、分散プラン実行部１６が分散プランの各演算を実施する際に、入力されるデータと用意した入力スキーマをスキーマ変更部１９に渡してスキーマ変更処理を実施する（ステップＳ１６）。
【０２６４】
ここで、図３１を参照して、ステップＳ１６においてマスターサーバのスキーマ変更部１９が、分散プランを実行する際に行うスキーマ変更処理について説明する。
【０２６５】
スキーマ変更部１９は、分散プラン実行部１６が次に実行する演算の入力であるスキーマＳを持つデータＤと、スキーマ生成部１８で予め用意した演算の入力スキーマＴを取得する（ステップＳ１４００）。次にスキーマＳとスキーマＴの変数の項目が一致しているかを判定する（ステップＳ１４１０）。
【０２６６】
スキーマＳとスキーマＴの変数の項目が一致していない場合（ステップＳ１４１０がＮｏ）、スキーマＳの拡張変数＄＃ｅの変数リストＶＬを取得し、リストが空であるかを判定する（ステップＳ１４２０）。
【０２６７】
スキーマＳの拡張変数＄＃ｅの変数リストＶＬが空でない場合（ステップＳ１４２０がＮｏ）、拡張変数リストＶＬ内の各変数をスキーマＳの変数の項目として追加し、ＶＬを空に変更する（ステップＳ１４３０）。次にスキーマＳに存在し、スキーマＴに存在しない変数の項目のリストＤＬを取得する（ステップＳ１４３０）。次にステップＳ１４５０に進む。なお、スキーマＳの拡張変数＄＃ｅの変数リストＶＬが空の場合（ステップＳ１４２０がＹｅｓ）も、ステップＳ１４５０に進む。
【０２６８】
ステップＳ１４５０では、変数の項目リストＤＬ内の変数がスキーマＳにおいて非連続に並んでいるかを判定する（ステップＳ１４５０）。
【０２６９】
変数の項目リストＤＬ内の変数がスキーマＳにおいて非連続に並んでいる場合、（ステップＳ１４５０がＹｅｓ）、変数の項目リストＤＬ内の変数が連続するようにスキーマＳとデータＤの各データを書き換える（ステップＳ１４６０）。次にステップＳ１４７０に進む。なお、変数の項目リストＤＬ内の変数がスキーマＳにおいて非連続に並んでいない場合（ステップＳ１４２０がＮｏ）も、ステップＳ１４７０に進む。
【０２７０】
ステップＳ１４７０では、スキーマＳの変数の項目からリストＤＬ内の変数を削除し、拡張変数＄＃ｅの変数リストに追加する（ステップＳ１４７０）。次にデータＤの可変領域の項目にリストＤＬ内の変数の合計サイズを格納して終了する（ステップＳ１４８０）。なおスキーマＳとスキーマＴの変数の項目が一致している場合（ステップＳ１４１０がＹｅｓ）も終了する。なお、図３１で示したフローチャートは、ローカルプラン実行部３３における演算に対するスキーマ変更部３６の処理時においても、対象がローカルプランであるか分散プランであるかの違いのみで同様に動作する。
【０２７１】
ここで図３１を参照して、スキーマ変更部１９が、図２６に示した、計算機０の演算番号７の入力スキーマと、計算機１、計算機２、計算機３から送信された各データのスキーマに対し、スキーマ変更処理を行う際の動作について具体的に説明する。このスキーマ変更処理は分散プランが図２４、計算機１、計算機２、計算機３のローカルプランが図１２、図１８、図１６に示したローカルプラン候補における分散プランの演算番号７の受信演算の実施時に行うものである。
【０２７２】
まず図２６の計算機０の演算番号７の入力スキーマＴと、計算機１から送信されたデータのスキーマＳを取得する（ステップＳ１４００）。スキーマＳとスキーマＴの変数項目が一致しているため処理を終了する（ステップＳ１４１０）。
【０２７３】
次に計算機０の演算番号７の入力スキーマＴと、計算機２から送信されたデータのスキーマＳを取得する（ステップＳ１４００）。スキーマＳとスキーマＴの変数項目が一致せず、Ｓの拡張変数＄＃ｅの変数リストが空であるためスキーマＳに存在し、スキーマＴに存在しない変数として＄ｕと＄ｖを取得する（ステップＳ１４１０、ステップＳ１４２０、ステップＳ１４４０）。変数＄ｕと＄ｖはスキーマＳにおいて連続して並んでいる為、スキーマＳの項目から変数＄ｕと＄ｖを削除し、拡張変数＄＃ｅの変数リストに追加する（ステップＳ１４５０、ステップＳ１４７０）。最後に＄ｕと＄ｖの変数の合計サイズを拡張領域に格納する（ステップＳ１４８０）。
【０２７４】
次に計算機０の演算番号７の入力スキーマＴと、計算機３から送信されたデータのスキーマＳを取得する（ステップＳ１４００）。スキーマＳとスキーマＴの変数項目が一致せず、Ｓの拡張変数＄＃ｅの変数リストが空であるためスキーマＳに存在し、スキーマＴに存在しない変数として＄ｕを取得する（ステップＳ１４１０、ステップＳ１４２０、ステップＳ１４４０）。変数＄ｕはスキーマＳにおいて連続して並んでいる為、スキーマＳの項目から変数＄ｕを削除し、拡張変数＄＃ｅの変数リストに追加する（ステップＳ１４５０、ステップＳ１４７０）。最後に＄ｕの変数の合計サイズを拡張領域に格納する（ステップＳ１４８０）。スキーマ変更処理の結果を図３２に示す。図３２は、スキーマ変更処理後のスキーマが含む項目を示す一例である。図３２に示すように本実施形態では、スキーマ変更処理後は、「可変領域」４０１と、「変数〜」４０２と「拡張変数＄＃ｅ（Ｖ１・・・，Ｖｎ）」４０３の項目を有する。
【０２７５】
なお上記のスキーマ変更処理は、マスターサーバの分散プランの演算とスレーブサーバのローカルプランの演算でデータを受け渡す際に実施する事例を説明したが、同一サーバ内、或いはスレーブサーバ間の演算でデータを受け渡す際にも適用できる。図２４では演算番号６のサーバ間ＪＯＩＮの前に変数＄ｚを受信することになっている。
【０２７６】
しかしながら図１８、図１２、図１９のローカルプラン候補から分かるように、計算機１は変数＄ｚ、＄ｕ、＄ｖの３組のデータを、計算機２は変数＄ｚを、計算機３は変数＄ｚ、＄ｕの２組のデータを送信している。このため、そのままではカラム数の異なるテーブルを扱うことになってしまう。したがってマスターサーバのスキーマ変更部１８では、図２６に示す各計算機のデータのスキーマを、図３２に示すように全ての計算機のデータが同じスキーマとみなすことができるようにスキーマを変更している。図２４では演算番号６のサーバ間ＪＯＩＮでは変数＄ｚのみ必要であるため、他に変数が含まれていた場合は全て１つの可変長データを格納した拡張変数＄＃ｅのカラムとして扱うようになっている。そして可変領域で可変長領域のサイズを記憶している。これによりサーバ間ＪＯＩＮの実行時に全て同じ形のテーブルとして扱うことが可能になっている。
【０２７７】
本実施形態の分散データベース検索装置によると、スレーブサーバ毎にローカルプランを作成するため、スレーブサーバ毎に分散プランの一部が異なる可能性がある。すなわち、スレーブサーバ毎に送られるデータのスキーマが異なる可能性がある。本実施形態は、このような場合に、スキーマ変更部１８、２０においてデータを受け渡す際に送信する側のデータのスキーマ（入力スキーマ）と、受信するデータのスキーマ（出力スキーマ）の違いを変更することで、同一スキーマのデータとして扱うことを実現する。
【０２７８】
すなわち、スレーブサーバ毎に効率の良いローカルプランを作成する場合、複数の異なるスキーマのデータが存在する場合がある。このように、スレーブサーバ毎に効率の良いローカルプランを作成する場合は、複数の異なるスキーマのデータを統一的に扱う処理が必要になる。
【０２７９】
上述のように本実施形態によると、複数の異なるスキーマのデータを統一的に扱うことが可能となる。また、本実施形態ではスキーマのみ、あるいはスキーマとデータの一部の領域の書き換えのみで複数の異なるスキーマのデータを統一的に扱うこと実現することが可能である。
【０２８０】
以上、本発明の実施形態を説明したが、これら実施形態は例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２８１】
１１…構文解析部、１２…クエリ分割部、１３…分散プラン生成部、１４…分散プラン結合演算追加部、１５…分散プラン更新部、１６…分散プラン実行部、１７…送受信部、１８…スキーマ生成部、１９…スキーマ変更部、３１…ローカルプラン選択部、３２…ローカルプラン候補生成部、３３…ローカルプラン実行部、３４…送受信部、３５…スキーマ生成部、３６…スキーマ変更部   
【図１】
0005318155.tif 000002
【図２】
0005318155.tif 000003
【図３】
0005318155.tif 000004
【図４】
0005318155.tif 000005
【図５】
0005318155.tif 000006
【図６】
0005318155.tif 000007
【図７】
0005318155.tif 000008
【図８】
0005318155.tif 000009
【図９】
0005318155.tif 000010
【図１０】
0005318155.tif 000011
【図１１】
0005318155.tif 000012
【図１２】
0005318155.tif 000013
【図１３】
0005318155.tif 000014
【図１４】
0005318155.tif 000015
【図１５】
0005318155.tif 000016
【図１６】
0005318155.tif 000017
【図１７】
0005318155.tif 000018
【図１８】
0005318155.tif 000019
【図１９】
0005318155.tif 000020
【図２０】
0005318155.tif 000021
【図２１】
0005318155.tif 000022
【図２２】
0005318155.tif 000023
【図２３】
0005318155.tif 000024
【図２４】
0005318155.tif 000025
【図２５】
0005318155.tif 000026
【図２６】
0005318155.tif 000027
【図２７】
0005318155.tif 000028
【図２８】
0005318155.tif 000029
【図２９】
0005318155.tif 000030
【図３０】
0005318155.tif 000031
【図３１】
0005318155.tif 000032
【図３２】
0005318155.tif 000033