(57)【特許請求の範囲】
【請求項１】
バス転送速度がプロセッサ内部より遅いネットワークに複数のプロセッサが接続されている分散ネットワークシステムにおいて、該ネットワークを経由してインデックス同士をマージする分散インデックスの結合方法であって、
複数のレコードのインデックスからなるインデックスＡ、該インデックスＡを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ａを有するプロセッサＡと、
複数のレコードのインデックスからなるインデックスＢ、該インデックスＢを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ｂを有するプロセッサＢと、
前記プロセッサＡの前記インデックスＡのレコードと前記プロセッサＢの前記インデックスＢのレコードを結合するプロセッサＪが前記ネットワークを介して接続されているシステムにおいて、
前記プロセッサＡにおいて、前記インデックスＡをＮ個に分割するインデックス分割ステップと、
Ｎ個のポインタからなるポインタリストが指す分割された範囲の全ての該インデックスＡのレコードのキー値からなるレコードリストＡを生成して、前記プロセッサＢに送信するレコードリスト送信ステップＡと、
前記プロセッサＢでは、前記レコードリストＡに基づいて、前記記憶手段Ｂを検索してインデックスＢを検索する検索ステップＢと、
検索された全てのインデックスＢのレコードのキー値からなるレコードリストＢを生成して前記プロセッサＡに送信するレコードリスト送信ステップＢと、
前記プロセッサＡでは、前記レコードリストＢに基づいて、前記記憶手段ＡのＮ個に分割された分割範囲のインデックスＡを検索し、検索された該インデックスＡの分割範囲のレコードを示すポインタ取得する検索ステップＡと、
を行うことを特徴とする分散インデックスの結合方法。
【請求項２】
前記レコードリスト送信ステップＢにおいて、
検索された前記インデックスＢのレコードリストＢ及び前記プロセッサＡから取得した前記レコードリストＡを前記プロセッサＪに送信し、
前記プロセッサＪにおいて、
前記レコードリストＢ及び前記レコードリストＡに示されるレコードを結合して出力する
請求項１記載の分散インデックスの結合方法。
【請求項３】
前記検索ステップＡにおいて、
検索された前記インデックスＡのレコードリストＡ及び前記プロセッサＢから取得した前記レコードリストＢを前記プロセッサＪに送信し、
前記プロセッサＪにおいて、
前記レコードリストＡ及び前記レコードリストＢに示されるレコードを結合して出力する
請求項１記載の分散インデックスの結合方法。
【請求項４】
前記プロセッサＡにおける前記インデックス分割ステップにおいて、
前記インデックスのアドレスにより物理的にＮ等分する；
前記インデックスのキー値の値域により論理的にＮ等分する；
前記インデックスのキー値の値域により、該インデックスのエントリ数が均等になるようにＮ分割する；
のいずれかの方法により前記インデックスを分割する
請求項１記載の分散インデックス結合方法。
【請求項５】
バス転送速度がプロセッサ内部より遅いネットワークに複数のプロセッサが接続されている分散ネットワークシステム上で、該ネットワークを経由してインデックス同士をマージする分散インデックスの結合システムであって、
前記システムは、
複数のレコードのインデックスからなるインデックスＡ、該インデックスＡを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ａを有するプロセッサＡと、
複数のレコードのインデックスからなるインデックスＢ、該インデックスＢを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ｂを有するプロセッサＢと、
前記プロセッサＡの前記インデックスＡのレコードと前記プロセッサＢの前記インデックスＢのレコードを結合するプロセッサＪを有し、
前記プロセッサＡは、
前記インデックスＡをＮ個に分割するインデックス分割手段と、
Ｎ個のポインタからなるポインタリストが指す分割された範囲の全ての該インデックスＡのレコードのキー値からなるレコードリストＡを生成して、前記プロセッサＢに送信するレコードリスト送信手段Ａと、
前記プロセッサＢから送信されたレコードリストＢに基づいて、前記記憶手段ＡのＮ個に分割された分割範囲のインデックスＡを検索し、検索された該インデックスＡの分割範囲のレコードを示すポインタ取得する検索手段Ａと、
前記プロセッサＢは、
前記プロセッサＡから送信された前記レコードリストＡに基づいて、前記記憶手段Ｂを検索してインデックスＢを検索する検索手段Ｂと、
検索された全てのインデックスＢのレコードのキー値からなるレコードリストＢを生成して前記プロセッサＡに送信するレコードリスト送信手段Ｂと、
を有することを特徴とする分散インデックスの結合システム。
【請求項６】
前記プロセッサＡの前記検索手段Ａは、
検索された前記インデックスＡのレコードリストＡ及び前記プロセッサＢから取得した前記レコードリストＢを前記プロセッサＪに送信する手段を更に有し、
前記プロセッサＪは、
前記レコードリストＡ及び前記レコードリストＢに示されるレコードを結合して出力する手段を有する
請求項５記載の分散インデックスの結合システム。
【請求項７】
前記プロセッサＢの前記レコードリスト送信手段Ｂは、
検索された前記インデックスＢのレコードリストＢ及び前記プロセッサＡから取得した前記レコードリストＡを前記プロセッサＪに送信する手段を更に有し、
前記プロセッサＪは、
前記レコードリストＢ及び前記レコードリストＡに示されるレコードを結合して出力する手段を有する
請求項５記載の分散インデックスの結合システム。
【請求項８】
前記プロセッサＡにおける前記インデックス分割手段は、
前記インデックスのアドレスにより物理的にＮ等分する；
前記インデックスのキー値の値域により論理的にＮ等分する；
前記インデックスのキー値の値域により、該インデックスのエントリ数が均等になるようにＮ分割する；
のいずれかの方法により前記インデックスを分割する手段を含む
請求項５記載の分散インデックス結合システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散インデックス結合方法及びシステムに係り、特に、ネットワーク上の分散システムにおけるリレーショナル・データベースのインデックス同士を結合するための分散インデックス結合システム及び方法及びプログラムに関する。詳しくは、リレーショナル・データベースのインデックス同士がコンピュータ内部のバス転送速度と比べて遅いネットワークで接続されている分散システムにおける分散インデックス結合方法及びシステムに関する。
【背景技術】
【０００２】
従来、リレーショナル・データベース同士の結合操作を実行するためのアルゴリズムとして、順次２つのデータベースのレコードの突合せを行い、結合条件を満たすものに対して結果のレコードを生成する入れ子ループ結合や、２つのデータベースが結合条件でソートされている場合には、先頭から順次突き合わせてマージするマージ結合や、一方のデータベースのレコードをハッシュ表に展開することにより結合条件を満たすレコードを求めるハッシュやインデックスを用いたハッシュ結合等が知られている。この例を図９に示す。
【０００３】
ステップ１０）  インデックスＡ，Ｂのレコードを指すポインタを先頭にするように初期化する。
【０００４】
ステップ１１）  インデックスＡのポインタが指すレコードのキー値をマシンＢに送信する。
【０００５】
ステップ１２）  インデックスＡのポインタが指すレコードのキー値でインデックスＢを検索する。
【０００６】
ステップ１３）  検索条件を満たすレコードがインデックスＢにあるかを判定し、ある場合には、ステップ１４に移行し、ない場合は、ステップ１５に移行する。
【０００７】
ステップ１４）  インデックスＡ、ＢのレコードをマシンＪに送り、当該マシンＪで両レコードを結合し、出力する。
【０００８】
ステップ１５）  インデックスＡのポインタが指すレコードのキー値を超える最小の値をインデックスＢから検索する。
【０００９】
ステップ１６）  検索条件を満たすレコードがインデックスＢにあるかを判定し、ある場合には、ステップ１７に移行し、ない場合には処理を終了する。
【００１０】
ステップ１７）  インデックスＢのポインタを該当するレコードのところに進める。
【００１１】
ステップ１８）  インデックスＢのポインタが指すレコードのキー値をマシンＡに送る。
【００１２】
ステップ１９）  インデックスＢのポインタが指すレコードのキー値でインデックスＡを検索する。
【００１３】
ステップ２０）  検索条件を満たすレコードがインデックスＡにあるかを判定し、ある場合は、ステップ２１に移行し、ない場合はステップ２２に移行する。
【００１４】
ステップ２１）  インデックスＡ，ＢのレコードをマシンＪに送りマシンＪで両レコードを結合して出力する。
【００１５】
ステップ２２）  インデックスＢのポインタが指すレコードのキー値を超える最小の値をインデックスＡから検索する。
【００１６】
ステップ２３）  検索条件を満たすレコードがインデックスＡにあるかを判定し、ある場合はステップ２４に移行し、ない場合は、処理を終了する。
【００１７】
ステップ２４）  インデックスＡのポインタを該当するレコードのところに進め、ステップ１１の処理に移行する。
【００１８】
また、結合操作を別々のジョブに区分し、それらのジョブを複数のプロセッサ間で最適にスケジューリングすることにより、データ・スキューの存在下で並列リレーショナル・データベース環境にある共通フィールド上の２つのデータベース・リレーションをマージ結合する技術がある。この技術は、最小メークスパン最適化技法を使用して、プロセッサ間でジョブの現集合をスケジューリングすることによって、２つのリレーションの自然結合のための全実行時間を最小することができる（例えば、特許文献１参照）。
【特許文献１】特開平３−１２６１６９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１９】
しかしながら、上記の図９に示すアルゴリズムをネットワークにより分散したシステムにそのまま適用すると、通信回数が増大し、性能が現れないという問題がある。
【００２０】
また、最小メークスパン最適化技法を使用して、マージ結合する技術は、マルチプロセッサシステムを想定したもので、分散システム間の通信はネットワークよりも高速なインターコネクトを前提としており、インデックス同士がコンピュータ内部のパス転送速度と比べて遅いネットワークで接続された分散システムについては考慮されていない。
【００２１】
本発明は、上記の点に鑑みなされたもので、インデックス同士がコンピュータ内部のパス転送速度と比べて遅いネットワークで接続された分散システムにおいて、インデックス同士のマージ結合を高速化させ、処理中の通信回数を削減することが可能な分散インデックス結合システム及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
図１は、本発明の原理を説明するための図である。
【００２３】
本発明（請求項１）は、バス転送速度がプロセッサ内部より遅いネットワークに複数のプロセッサが接続されている分散ネットワークシステムにおいて、該ネットワークを経由してインデックス同士をマージする分散インデックスの結合方法であって、
複数のレコードのインデックスからなるインデックスＡ、該インデックスＡを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ａを有するプロセッサＡと、
複数のレコードのインデックスからなるインデックスＢ、該インデックスＢを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ｂを有するプロセッサＢと、
プロセッサＡのインデックスＡのレコードとプロセッサＢのインデックスＢのレコードを結合するプロセッサＪがネットワークを介して接続されているシステムにおいて、
プロセッサＡにおいて、インデックスＡをＮ個に分割するインデックス分割ステップ（ステップ１）と、
Ｎ個のポインタからなるポインタリストが指す分割された範囲の全ての該インデックスＡのレコードのキー値からなるレコードリストＡを生成して（ステップ２）、プロセッサＢに送信する（ステップ３）レコードリスト送信ステップＡと、
プロセッサＢでは、レコードリストＡに基づいて、記憶手段Ｂを検索してインデックスＢを検索する検索ステップＢ（ステップ４）と、
検索された全てのインデックスＢのレコードのキー値からなるレコードリストＢを生成して（ステップ７）プロセッサＡに送信する（ステップ８）レコードリスト送信ステップＢと、
プロセッサＡでは、レコードリストＢに基づいて、記憶手段ＡのＮ個に分割された分割範囲のインデックスＡを検索し、検索された該インデックスＡの分割範囲のレコードを示すポインタ取得する検索ステップＡ（ステップ９）と、を行う。
【００２４】
また、本発明（請求項２）は、レコードリスト送信ステップＢにおいて、
検索されたインデックスＢのレコードリストＢ及びプロセッサＡから取得したレコードリストＡをプロセッサＪに送信し（ステップ５）、
プロセッサＪにおいて、
レコードリストＢ及びレコードリストＡに示されるレコードを結合して出力する（ステップ６）。
【００２５】
また、本発明（請求項３）は、検索ステップＡにおいて、
検索されたインデックスＡのレコードリストＡ及びプロセッサＢから取得したレコードリストＢをプロセッサＪに送信し（ステップ１０）、
プロセッサＪにおいて、
レコードリストＡ及びレコードリストＢに示されるレコードを結合して出力する（ステップ１１）。
【００２６】
また、本発明（請求項４）は、プロセッサＡにおけるインデックス分割ステップにおいて、
インデックスのアドレスにより物理的にＮ等分する；
インデックスのキー値の値域により論理的にＮ等分する；
インデックスのキー値の値域により、該インデックスのエントリ数が均等になるようにＮ分割する；
のいずれかの方法によりインデックスを分割する。
【００２７】
図２は、本発明の原理構成図である。
【００２８】
本発明（請求項５）は、バス転送速度がプロセッサ内部より遅いネットワークに複数のプロセッサが接続されている分散ネットワークシステム上で、該ネットワークを経由してインデックス同士をマージする分散インデックスの結合システムであって、
システムは、
複数のレコードのインデックスからなるインデックスＡ、該インデックスＡを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ａ１３０Ａを有するプロセッサＡと、
複数のレコードのインデックスからなるインデックスＢ、該インデックスＢを走査するためのＮ個のポインタからなるポインタリスト及び該ポインタに対応するレコードのキー値からなるレコードリストを格納する記憶手段Ｂ１３０Ｂを有するプロセッサＢと、
プロセッサＡのインデックスＡのレコードとプロセッサＢのインデックスＢのレコードを結合するプロセッサＪを有し、
プロセッサＡは、
インデックスＡをＮ個に分割するインデックス分割手段１２０と、
Ｎ個のポインタからなるポインタリストが指す分割された範囲の全ての該インデックスＡのレコードのキー値からなるレコードリストＡを生成して、プロセッサＢに送信するレコードリスト送信手段Ａ１４０と、
プロセッサＢから送信されたレコードリストＢに基づいて、記憶手段ＡのＮ個に分割された分割範囲のインデックスＡを検索し、検索された該インデックスＡの分割範囲のレコードを示すポインタ取得する検索手段Ａ１１０Ａと、
プロセッサＢは、
プロセッサＡから送信されたレコードリストＡに基づいて、記憶手段Ｂ１３０Ｂを検索してインデックスＢを検索する検索手段Ｂ１１０Ｂと、
検索された全てのインデックスＢのレコードのキー値からなるレコードリストＢを生成してプロセッサＡに送信するレコードリスト送信手段Ｂ１４０Ｂと、を有する。
【００２９】
また、本発明（請求項６）は、プロセッサＡの検索手段Ａ１１０Ａにおいて、
検索されたインデックスＡのレコードリストＡ及びプロセッサＢから取得したレコードリストＢをプロセッサＪに送信するレコード送信手段Ａ１４１Ａを更に有し、
プロセッサＪは、レコードリストＡ及びレコードリストＢに示されるレコードを結合して出力する結合手段２２０を有する。
【００３０】
また、本発明（請求項７）は、プロセッサＢのレコードリスト送信手段Ｂ１４０Ｂにおいて、
検索されたインデックスＢのレコードリストＢ及びプロセッサＡから取得したレコードリストＡをプロセッサＪに送信するレコード送信手段１４１Ｂを更に有し、
プロセッサＪは、レコードリストＢ及びレコードリストＡに示されるレコードを結合して出力する結合手段２２０を有する。
【００３１】
本発明（請求項８）は、プロセッサＡにおけるインデックス分割手段１２０Ａにおいて、
インデックスのアドレスにより物理的にＮ等分する；
インデックスのキー値の値域により論理的にＮ等分する；
インデックスのキー値の値域により、該インデックスのエントリ数が均等になるようにＮ分割する；
のいずれかの方法によりインデックスを分割する手段を含む。
【発明の効果】
【００３２】
上記のように本発明によれば、各プロセッサにおいて、インデックスを走査するポインタをＮ個有し、プロセッサ間においてＮ個のポインタからなるポインタリスト単位で、Ｎ個分のポインタに対応するレコード（レコードリスト）を送信することにより、処理負荷が低減される。これは、ネットワーク経由の場合、データ送受信の起動・停止に関わる処理のオーバーヘッドが大きいため、送受信するデータの総量は同じであっても、そのやり取りに要する回数を減らすことにより、処理時間が短縮される。
【００３３】
また、片方のプロセッサにおいてインデックスをＮ個に分割して、分割された１つの範囲内のレコードと、もう片方のプロセッサのインデックスに対応するレコードを付き合わせることで、Ｎ個のポインタがあっても重複してマージ結合することがないようにする。
【発明を実施するための最良の形態】
【００３４】
以下、図面と共に本発明の実施の形態を説明する。
【００３５】
図３は、本発明の一実施の形態における分散インデックス結合システムの構成を示す。
【００３６】
同図に示す分散インデックス結合システムは、インデックスＡを有するプロセッサＡと、インデックスＢを有するプロセッサＢと、プロセッサＡとプロセッサＢのレコードを結合する、プロセッサＡ、Ｂとは別のプロセッサＪから構成される。
【００３７】
プロセッサＡとプロセッサＢは、同様の構成であり、それぞれ、入出力部１１０、インデックス検索部１１０、レコードリスト処理部１２０、レコードリスト記憶部１３０、レコードリスト通信部１４０から構成される。
【００３８】
レコードリスト記憶部１３０は、図４に示すように、ポインタリストとレコードリストを格納する。以下の説明において、「ポインタ」とは、インデックスのどこを検索しているかを指すポインタであり、複数のポインタをリスト化したものを「ポインタリスト」と呼ぶ。また、ポインタリストで指し示しているインデックスのレコードをレコードリストである。図４の例では、ポインタリストの先頭は、インデックスの先頭のレコードを指しており、当該レコードのキー値「００３４」がレコードリストに設定されている。ポインタリストの２番目はインデックスのｎ番目のレコードを指しており、当該レコードのキー値「０３０５」がレコードリストに設定されている。
【００３９】
プロセッサＪは、インデックスＡを持つプロセッサＡ，インデックスＢを持つプロセッサＢとは別の、インデックス同士のマージ結合を統括するプロセッサで、以下のフローチャートで表される処理全体を実行するトリガとなるプロセッサである。プロセッサＪは、マージ処理部２１０とレコード結合部２２０を有し、マージ処理部２１０は、検索条件入力装置３１０と接続され、レコード結合部２２０は、結合結果出力装置３００と接続されている。
【００４０】
マージ処理部２１０は、プロセッサＡ，Ｂに対して、検索条件入力装置３１０から入力された検索条件をプロセッサＡ，Ｂに出力する。
【００４１】
レコード結合部２２０は、プロセッサＡ及び、プロセッサＢのレコードリスト通信部１４０から送信されたインデックスの検索結果の該当レコードを結合し、結合結果出力装置３２０に出力する。この処理が実行されるということは、両インデックスに共通するキー値を持つレコードがあったということを示している。
【００４２】
以下に、上記の構成における動作を説明する。
【００４３】
図５は、本発明の一実施の形態におけるマージ結合のフローチャートである。
【００４４】
ステップ１１０）  プロセッサＢにおいて、入出力部１００Ｂを介してレコードを指すＮ個のポインタリストが入力されると、レコードリスト処理部１２０Ｂは、ポインタがインデックスＢの先頭レコードを指すように、レコードリスト記憶部１３０ＢのＮ個のインデックスＢのポインタリストを初期化する。
【００４５】
ステップ１１５）  プロセッサＡにおいて、インデックスＡが入出力部１００Ａを介して入力されると、レコードリスト処理部１２０Ａにおいて、インデックスＡをＮ個に分割する。分割する方法は以下のようなものがある。
【００４６】
・インデックスのアドレスにより物理的にＮ等分する。
【００４７】
・インデックスのキー値の値域により論理的にＮ等分する。
【００４８】
・インデックスのキー値の値域によりＮ分割する際、インデックスのエントリ数が均等になるように分割する。
【００４９】
さらに、Ｎ個のポインタをそれぞれ分割した部分の先頭レコードを指すように、レコードリスト記憶部１２０ＡのインデックスＡのポインタリストを初期化する。
【００５０】
ステップ１２０）  レコードリスト処理部１２０Ａにおいて、レコードリスト記憶部１３０ＡからインデックスＡのレコードを指すＮ個のポインタリストを読み込み、Ｎ個のポインタリストが示すインデックスＡの各レコードのキー値を取得してリスト化し、レコードリストとしてレコードリスト記憶部１３０Ａに格納すると共に、レコードリスト通信部１４０Ａを介してプロセッサＢに送信する。ここで、レコードリスト処理部１２０Ａでは、読み込んだポインタリストに検索終了のマークが付いている場合は、該当するレコードリストのレコードにも検索終了のマークを付与する。
【００５１】
ステップ１２５）  プロセッサＢのレコードリスト通信部１４０Ｂでレコードリストを受信すると、レコードリスト処理部１２０Ｂは、そのレコードリストをメモリ（図示せず）のプロセッサＡのレコードリスト領域に格納する。そして、インデックス検索部１１０Ｂは、プロセッサＡから取得したインデックスＡのＮ個のレコードリストのレコードのキー値を検索キーとして、レコードリスト記憶部１３０ＢからインデックスＢを検索し、インデックスＢのレコードを指すＮ個のポインタリストを取得する。当該ステップの詳細については後述する。
【００５２】
ステップ１３０）  レコードリスト処理部１２０Ｂは、取得したインデックスＢのレコードを指すＮ個のポインタリストが示すインデックスＢの各レコードのキー値を取得してレコードリストとしてレコードリスト記憶部１３０Ｂに格納すると共に、レコードリスト通信部１４０Ｂを介してプロセッサＡに送信する。もし、レコードリスト処理部１２０Ｂは、取得したポインタリストに検索終了のマークが付与されている場合は、レコードリストの該当するレコードにも検索終了のマークを付与する。
【００５３】
ステップ１３５）  プロセッサＡのレコードリスト通信部１４０を介してプロセッサＢからレコードリストを取得すると、レコードリスト処理部１２０において、そのレコードリストをメモリ（図示せず）に格納する。インデックス検索部１１０Ａは、取得したインデックスＢのＮ個のレコードリストのレコードのキー値を検索キーとして、レコードリスト記憶部記憶部１３０ＡのインデックスＡのレコードを指すＮ個のポインタリストからＮ分割されたインデックスＡを検索し、インデックスＢのレコードを指すＮ個のポインタリストを取得する。詳細については後述する。
【００５４】
次に、上記のステップ１２５のインデックスＢの検索処理について詳細に説明する。
【００５５】
図６は、本発明の一実施の形態におけるインデックス検索処理のフローチャートである。
【００５６】
ステップ２１０）  プロセッサＢのレコードリスト処理部１２０Ｂにおいて、メモリ（図示せず）に、Ｎ個分まとめて処理するためのループカウンタｊを設け、ｊ＝１と初期化する。
【００５７】
ステップ２１５）  レコードリスト処理部１２０Ｂは、プロセッサＡから送信されたインデックスＡのＮ個のレコードリストからカウンタｊに相当するレコード（インデックスＡのレコードリスト中ｊ番目のレコード）を取り出す。
【００５８】
ステップ２２０）  取り出したインデックスＡのレコードリスト中のｊ番目のレコードを確認し、検索終了のマークが付与されているかを判定し、付与されていればステップ２５５に移行し、付与されていなければステップ２２５に移行する。
【００５９】
ステップ２２５）  インデックス検索部１１０Ｂは、ステップ２２０で取り出されたインデックスＡのレコードリスト中ｊ番目のレコードのキー値を用いて、レコードリスト記憶部１３０ＢからインデックスＢを検索する。検索結果が「真」の場合はインデックスＢの検索結果該当レコードを指すポインタが出力される。
【００６０】
ステップ２３０）  検索条件を満たすレコードがインデックスＢに存在するか否かを判定する。ステップ２２５における検索結果が「真」の場合はステップ２３５に移行し、「偽」の場合はステップ２４０に移行する。
【００６１】
ステップ２３５）  レコードリスト処理部１２０Ｂは、ステップ２２５で得られたポインタが指すインデックスＢの検索結果該当レコードをレコードリスト記憶部１３０Ｂから取得し、インデックスＡのレコードリスト中ｊ番目のレコードと共に、レコードリスト通信部１４０Ｂを介してプロセッサＪに送信する。
【００６２】
プロセッサＪのレコード結合部２２０は、プロセッサＢから送信されたインデックスＢの検索結果該当レコードと、インデックスＡのレコードリスト中ｊ番目のレコードを結合して結合結果出力装置３２０に出力する。
【００６３】
ステップ２４０）  プロセッサＢのインデックス検索部１１０Ｂは、インデックスＡのレコードリスト中ｊ番目のレコードのキー値を用いて、レコードリスト記憶部１３０ＢのインデックスＢから、次のレコードをインデックスから取得し、もう一方のインデックスの検索キーとするために、「キー値を超える最小の値」を検索する。
【００６４】
ステップ２４５）  ステップ２４０において、プロセッサＪから与えられた検索条件を満たすレコードがインデックスＢに存在するかどうか確認し、存在すれば、ステップ２５０に移行し、存在しなければステップ２５５に移行する。
【００６５】
ステップ２５０）  レコードリスト処理部１２０Ｂは、レコードリスト記憶部１３０ＢのインデックスＢのレコードを指すＮ個のポインタリストのｊ番目に、インデックスＢの検索結果該当レコードを指すポインタを記録する。
【００６６】
ステップ２５５）  レコードリスト処理部１２０Ｂは、インデックスＢのレコードを指すＮ個のポインタリストのｊ番目に、これ以上インデックスＢには検索するものがないことを示す検索終了のマークを付ける。
【００６７】
ステップ２６０）  レコードリスト処理部１２０Ｂは、インデックスＢのレコードを指すＮ個のポインタリストの全てに検索終了のマークがついているかどうか確認する。全ての検索終了のマークが付与されていたら処理を終了する。
【００６８】
ステップ２６５）  ループ用のカウンタｊがＮを超えていないかどうか確認する。Ｎを超えていない、すなわち、Ｎ回のループが終了していなければ、ステップ２７０に移行し、Ｎを超えている、すなわち、Ｎ回のループが終了していれば「インデックスＢ検索処理」を終了し、前述のステップ１３０に移行する。
ステップ２７０）  カウンタｊを１インクリメントする。
【００６９】
図７は、本発明の一実施の形態におけるインデックスＡ検索処理のフローチャートである。
【００７０】
ステップ３１０）  プロセッサＡのレコードリスト処理部１２０Ａにおいて、メモリ（図示せず）にＮ個分纏めて処理するためのループカウンタｉを設け、ｉ＝１とする。
【００７１】
ステップ３１５）  レコードリスト処理部１２０Ａは、プロセッサＢから送信されたＮ個のレコードリストから、カウンタｉに相当するレコード（インデックスＢのレコードリスト中ｉ番目のレコード）を取り出す。
【００７２】
ステップ３２０）  取り出したインデックスＢのレコードリスト中ｉ番目のレコードを確認し、検索終了のマークが付いているか判定し、付与されていればステップ３５５に移行し、付与されていなければステップ３２５に移行する。
【００７３】
ステップ３２５）  インデックス検索部１１０Ａは、ステップ３２０で取り出されたインデックスＢのレコードリスト中ｉ番目のレコードのキー値を用いて、レコードリスト記憶部１３０ＡからインデックスＡのｉ番目の分割範囲（ステップ１１５で分割した範囲）を検索する。検索結果が「真」の場合はインデックスＡのｉ番目分割範囲検索結果該当レコードを指すポインタが出力される。
【００７４】
ステップ３３０）  検索条件を満たすレコードがインデックスＡのｉ番目の分割範囲に存在するかを判定し、存在する場合はステップ３５５に移行し、存在していなければステップ３４０に移行する。
【００７５】
ステップ３３５）  レコードリスト処理部１２０Ａは、レコードリスト記憶部１３０から、ステップ３２５で得られたポインタが指すインデックスＡのｉ番目の分割範囲検索結果該当レコードを取得し、インデックスＢのレコードリスト中ｉ番目のレコードと共に、プロセッサＪに送信する。
【００７６】
プロセッサＪのレコード結合部２２０は、プロセッサＡから送信されたインデックスＡとインデックスＢのレコードを結合する。この処理が行われるということは、両インデックスに共通するキー値を持つレコードがあったということである。プロセッサＪのレコード結合部２２０は、インデックスＡのｉ番目の分割範囲検索結果該当レコード及びインデックスＢのレコード中ｉ番目のレコードを結果出力装置３２０に出力する。
【００７７】
ステップ３４０）  プロセッサＡのインデックス検索部１１０Ａは、インデックスＢのレコード中ｉ番目のレコードのキー値を用いて、レコードリスト記憶部１３０ＡからインデックスＡのｉ番目の分割範囲から「キー値を超える最小の値」を検索する。
【００７８】
ステップ３４５）  ステップ３４０において、プロセッサＪから与えられた検索条件を満たすレコードがインデックスＡのｉ番目の分割範囲に存在するかどうかを判定し、存在すればステップ３５０に移行し、存在しなければステップ３５５に移行する。
【００７９】
ステップ３５０）  レコードリスト処理部１２０Ａは、レコードリスト記憶部１３０ＡのインデックスＡのレコードを指すＮ個のポインタリストのｉ番目にインデックスＡのｉ番目の分割範囲検索結果該当レコードを指すポインタを記録する。
【００８０】
ステップ３５５）  レコードリスト処理部１２０Ａは、インデックスＡのレコードを指すＮ個のポインタリストのｉ番目に、これ以上インデックスＡのｉ番目分割範囲には検索するものがないことを示す、検索終了のマークを付与する。
【００８１】
ステップ３６０）  レコードリスト処理部１２０Ａは、インデックスＡのレコードを指すＮ個のポインタリストの全てに検索終了のマークが付いているかどうかを確認する。全てに検索終了のマークが付与されていれば処理を終了し、そうでなければステップ３６５に移行する。
【００８２】
ステップ３６５）  ループ用カウンタｉがＮを超えていないかどうか確認し、Ｎを超えていない、すなわち、Ｎ回のループが終了していなければステップ３７０に移行し、Ｎを超えている、すなわち、Ｎ回のループが終了していれば、当該「インデックスＡの検索処理」を終了し、ステップ１２０に移行する。
【００８３】
ステップ３７０）  カウンタｉを１インクリメントする。
【００８４】
以下に、本発明による手法と、従来の技術による手法で５００万件のデータ同士を全件マージ結合した場合の比較データを図８に示す。モックアップによる試験のため、インデックス読み込み処理等に違いがあり、インデックス読み込み処理時間等を公平に比較することはできないが、本発明により、ネットワーク転送処理時間が減少していることが確認できた。
【００８５】
本発明は、図３に示すプロセッサの構成に基づいて説明したが、この例に限定されることなく、各プロセッサの構成要素の動作をプログラムとして構築し、各プロセッサ（コンピュータ）にインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８６】
また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００８７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００８８】
本発明は、ＤＢＭＳ（Data Base Management System）やＲＤＢＭＳ（Relational Data Base Management System）に適用可能である。
【図面の簡単な説明】
【００８９】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における分散インデックス結合システムの構成図である。
【図４】本発明の一実施の形態におけるレコードリスト記憶部を説明するための図である。
【図５】本発明の一実施の形態におけるマージ結合のフローチャートである。
【図６】本発明の一実施の形態におけるインデックスＢ検索処理のフローチャートである。
【図７】本発明の一実施の形態におけるインデックスＡ検索処理のフローチャートである。
【図８】本発明の手法と従来の手法の比較結果である。
【図９】従来のマージ結合のフローチャートである。
【符号の説明】
【００９０】
１００  入出力部
１１０  検索手段、インデックス検索部
１２０  レコードリスト処理部
１３０  記憶手段、レコードリスト記憶部
１４０  レコードリスト送信手段、レコードリスト通信部
１４１  レコード送信手段
２１０  マージ処理部
２２０  結合手段、レコード結合部
３１０  検索条件入力装置
３２０  検索結果出力装置
【図１】
0004966175.tif 000002
【図２】
0004966175.tif 000003
【図３】
0004966175.tif 000004
【図４】
0004966175.tif 000005
【図５】
0004966175.tif 000006
【図６】
0004966175.tif 000007
【図７】
0004966175.tif 000008
【図８】
0004966175.tif 000009
【図９】
0004966175.tif 000010