(57)【要約】  最適化の結果発生するクエリの中間成果を合理的な判断の下で、どの分散ストレージサイトに配置するべきか考慮し、クエリの最適化を実施段階で実現する。まず、データと保持するサイトに関するレイテンシ及び信頼性に関する数値情報を取り出す。次に、前記レイテンシ関する情報、並びに前記信頼性に関する数値情報の逆数をクエリのコスト値に重畳し、拡張コスト値を求める。次に、コスト値が妥当な上位指定値のレプリカを選定する。次に、最適化の結果発生する中間成果の配置先サイトを選定するためにアルゴリズム上のパラメータである最大ブロックサイズに１を加え処理系自身のコピーを作成することで先読みを実施する。次に、前記先読みの結果、中間成果を１つ以上のサイトに配置する。これにより、クエリの中間成果の配置方式を評価する。
2011118425.tif 000002
【特許請求の範囲】
【請求項１】
データベース管理システムにおいて、クエリの中間成果の配置方式を評価するクエリ最適化システムであって、
データを保持するサイトに関するレイテンシ及び信頼性に関する数値情報を取り出す装置と、
取り出したレイテンシ及び信頼性に関する数値情報をクエリのコスト値に重畳し拡張コスト値を求める装置と、
拡張コスト値で序列化した場合に上位で所定の条件に適合する指定値を持つサイトを選定する装置と、
アルゴリズム中のパラメータを一部変更した処理系自身のコピーを作成して先読みを実施する装置と、
前記先読みの結果、前記所定の条件に適合する指定値を持つサイトの中から、最適化の結果発生する中間成果の配置先サイトを選定し、前記中間成果を、前記選定された配置先サイトのうち少なくとも１つのサイトに配置する装置と
を含む
クエリ最適化システム。
【請求項２】
請求項１に記載のクエリ最適化システムであって、
クエリの構文を解析し、参照する表集合の各要素表で想定されるアクセスパターンを抽出し、仮結合要素リストに追加する装置と、
前記各要素表に関して前記仮結合要素リストから最適なアクセス条件のものを取り出して残し、他を前記仮結合要素リストから削除する装置と、
前記仮結合要素リストの各要素に対して、全レプリカ分のエントリを作成し、前記仮結合要素リストに追加する装置と、
前記仮結合要素リストからエントリを取り出し、当該エントリにレイテンシ及び信頼性に関する数値情報を付与し、前記仮結合要素リストを更新する装置と、
前記仮結合要素リストのエントリのレイテンシ及び信頼性に関する数値情報を評価する装置と、
評価の結果、上位の所定数のレプリカを残し、他を前記仮結合要素リストから削除する装置と、
前記仮結合要素リストのエントリに基づいて、結合要素リストの初期版を作成し、最適化プラン要素リストに追加する装置と、
前記仮結合要素リストを削除する装置と
を更に含む
クエリ最適化システム。
【請求項３】
請求項２に記載のクエリ最適化システムであって、
同じ処理系をコピーし、コピーした処理系を起動する装置と、
前記最適化プラン要素リスト内の要素から、貪欲法（欲張り法）のアルゴリズムを用いてコストを計算する評価関数を最小にする結合木の選択を行う装置と、
自身がコピー処理系か非コピー処理系かを判断する装置と、
自身がコピー処理系である場合、非コピー処理系からの問い合わせ待ちを行い、コピーを実施した非コピー処理系からの問い合わせの際に指定される中間成果表の結合木の種類を判定し、外部側／駆動表か、内部側／参照表かを評価し、どのサイトのどの表と結合演算を行うか、を非コピー処理系に応答し、コピー処理系を終了する装置と、
自身が非コピー処理系である場合、結合木を新たな中間成果表に仮置きし、コピー処理系に問い合わせる装置と、
配置評価関数を呼び出し、前記中間成果表を配置するべきサイトと当該サイトの索引の作成方針で最適な案を取り出す装置と、
前記配置評価関数の結果に基づき、所定の箇所に前記中間生成結果を配置する装置と
を更に含む
クエリ最適化システム。
【請求項４】
請求項３に記載のクエリ最適化システムであって、
前記配置評価関数の処理において、次の結合演算先を確認し、次の結合演算先で利用されるサイト群を取り出して、サイト仮リストに追加する装置と、
前記サイト仮リストに含まれないサイトを取り出し、候補仮リストに追加する装置と、
探索用の候補エリアを準備し、初期化する装置と、
順次、サイト情報を読み出し、当該サイトに関するレイテンシ及び信頼性に関する数値情報を読み出す装置と、
候補エリアで初期化されたものが残っている場合、最初の所定数のサイトを候補として、前記探索用の候補エリアにセットする装置と、
候補エリアが既にセットされ、前記サイト仮リストに登録されていない場合、レイテンシ及び信頼性に関する数値情報がより高評価であれば、前記探索用の候補エリアに記載されているサイトを置き換える装置と、
新たな候補となるサイトが特定された場合、当該サイトを前記サイト仮リストに追加する装置と、
中間成果表の結合木の作成件数から表作成コストを見積もる装置と、
前記表作成コストの見積りに対し、正規化されたレイテンシに関する数値情報並びに信頼性に関する数値情報の逆数を重畳し、全体コストを求め、全体コストに対して計画番号を付け、候補の一つとして評価リストに追加する装置と、
索引の作成可能性を判定し、索引が作成可能である場合、全体コストから索引作成コストを見積り、索引作成コストも組み込んだ全体コストを改めて計算し、改めて計算した全体コストに対して計画番号を付け、別候補として前記評価リストに追加する装置と、
前記評価リスト内のデータに関して、全体コストでソートし序列化を行い、全体コストが最小のものを第一案として記憶する装置と、
前記第一案と同類の構成で配置先が異なり、全体コストが次に小さいものを第二案として記憶する装置と、
前記第一案、及び前記第二案を回答する装置と
を更に含む
クエリ最適化システム。
【請求項５】
データベース管理システムにおいて、クエリの中間成果の配置方式を評価するクエリ最適化装置であって、
データを保持するサイトに関するレイテンシ及び信頼性に関する数値情報を取り出す手段と、
取り出したレイテンシ及び信頼性に関する数値情報をクエリのコスト値に重畳し拡張コスト値を求める手段と、
拡張コスト値で序列化した場合に上位で所定の条件に適合する指定値を持つサイトを選定する手段と、
アルゴリズム中のパラメータを一部変更した処理系自身のコピーを作成して先読みを実施する手段と、
前記先読みの結果、前記所定の条件に適合する指定値を持つサイトの中から、最適化の結果発生する中間成果の配置先サイトを選定し、前記中間成果を、前記選定された配置先サイトのうち少なくとも１つのサイトに配置する手段と
を具備する
クエリ最適化装置。
【請求項６】
請求項５に記載のクエリ最適化装置であって、
クエリの構文を解析し、参照する表集合の各要素表で想定されるアクセスパターンを抽出し、仮結合要素リストに追加する手段と、
前記各要素表に関して前記仮結合要素リストから最適なアクセス条件のものを取り出して残し、他を前記仮結合要素リストから削除する手段と、
前記仮結合要素リストの各要素に対して、全レプリカ分のエントリを作成し、前記仮結合要素リストに追加する手段と、
前記仮結合要素リストからエントリを取り出し、当該エントリにレイテンシ及び信頼性に関する数値情報を付与し、前記仮結合要素リストを更新する手段と、
前記仮結合要素リストのエントリのレイテンシ及び信頼性に関する数値情報を評価する手段と、
評価の結果、上位の所定数のレプリカを残し、他を前記仮結合要素リストから削除する手段と、
前記仮結合要素リストのエントリに基づいて、結合要素リストの初期版を作成し、最適化プラン要素リストに追加する手段と、
前記仮結合要素リストを削除する手段と
を更に具備する
クエリ最適化装置。
【請求項７】
請求項６に記載のクエリ最適化装置であって、
同じ処理系をコピーし、コピーした処理系を起動する手段と、
前記最適化プラン要素リスト内の要素から、貪欲法（欲張り法）のアルゴリズムを用いてコストを計算する評価関数を最小にする結合木の選択を行う手段と、
自身がコピー処理系か非コピー処理系かを判断する手段と、
自身がコピー処理系である場合、非コピー処理系からの問い合わせ待ちを行い、コピーを実施した非コピー処理系からの問い合わせの際に指定される中間成果表の結合木の種類を判定し、外部側／駆動表か、内部側／参照表かを評価し、どのサイトのどの表と結合演算を行うか、を非コピー処理系に応答し、コピー処理系を終了する手段と、
自身が非コピー処理系である場合、結合木を新たな中間成果表に仮置きし、コピー処理系に問い合わせる手段と、
配置評価関数を呼び出し、前記中間成果表を配置するべきサイトと当該サイトの索引の作成方針で最適な案を取り出す手段と、
前記配置評価関数の結果に基づき、所定の箇所に前記中間生成結果を配置する手段と
を更に具備する
クエリ最適化装置。
【請求項８】
請求項７に記載のクエリ最適化装置であって、
前記配置評価関数の処理において、次の結合演算先を確認し、次の結合演算先で利用されるサイト群を取り出して、サイト仮リストに追加する手段と、
前記サイト仮リストに含まれないサイトを取り出し、候補仮リストに追加する手段と、
探索用の候補エリアを準備し、初期化する手段と、
順次、サイト情報を読み出し、当該サイトに関するレイテンシ及び信頼性に関する数値情報を読み出す手段と、
候補エリアで初期化されたものが残っている場合、最初の所定数のサイトを候補として、前記探索用の候補エリアにセットする手段と、
候補エリアが既にセットされ、前記サイト仮リストに登録されていない場合、レイテンシ及び信頼性に関する数値情報がより高評価であれば、前記探索用の候補エリアに記載されているサイトを置き換える手段と、
新たな候補となるサイトが特定された場合、当該サイトを前記サイト仮リストに追加する手段と、
中間成果表の結合木の作成件数から表作成コストを見積もる手段と、
前記表作成コストの見積りに対し、正規化されたレイテンシに関する数値情報並びに信頼性に関する数値情報の逆数を重畳し、全体コストを求め、全体コストに対して計画番号を付け、候補の一つとして評価リストに追加する手段と、
索引の作成可能性を判定し、索引が作成可能である場合、全体コストから索引作成コストを見積り、索引作成コストも組み込んだ全体コストを改めて計算し、改めて計算した全体コストに対して計画番号を付け、別候補として前記評価リストに追加する手段と、
前記評価リスト内のデータに関して、全体コストでソートし序列化を行い、全体コストが最小のものを第一案として記憶する手段と、
前記第一案と同類の構成で配置先が異なり、全体コストが次に小さいものを第二案として記憶する手段と、
前記第一案、及び前記第二案を回答する手段と
を更に具備する
クエリ最適化装置。
【請求項９】
データベース管理システムにおいて、クエリの中間成果の配置方式を評価するコンピュータにより実施されるクエリ最適化方法であって、
データを保持するサイトに関するレイテンシ及び信頼性に関する数値情報を取り出すことと、
取り出したレイテンシ及び信頼性に関する数値情報をクエリのコスト値に重畳し拡張コスト値を求めることと、
拡張コスト値で序列化した場合に上位で所定の条件に適合する指定値を持つサイトを選定することと、
アルゴリズム中のパラメータを一部変更した処理系自身のコピーを作成して先読みを実施することと、
前記先読みの結果、前記所定の条件に適合する指定値を持つサイトの中から、最適化の結果発生する中間成果の配置先サイトを選定し、前記中間成果を、前記選定された配置先サイトのうち少なくとも１つのサイトに配置することと
を含む
クエリ最適化方法。
【請求項１０】
請求項９に記載のクエリ最適化方法であって、
クエリの構文を解析し、参照する表集合の各要素表で想定されるアクセスパターンを抽出し、仮結合要素リストに追加することと、
前記各要素表に関して前記仮結合要素リストから最適なアクセス条件のものを取り出して残し、他を前記仮結合要素リストから削除することと、
前記仮結合要素リストの各要素に対して、全レプリカ分のエントリを作成し、前記仮結合要素リストに追加することと、
前記仮結合要素リストからエントリを取り出し、当該エントリにレイテンシ及び信頼性に関する数値情報を付与し、前記仮結合要素リストを更新することと、
前記仮結合要素リストのエントリのレイテンシ及び信頼性に関する数値情報を評価することと、
評価の結果、上位の所定数のレプリカを残し、他を前記仮結合要素リストから削除することと、
前記仮結合要素リストのエントリに基づいて、結合要素リストの初期版を作成し、最適化プラン要素リストに追加することと、
前記仮結合要素リストを削除することと
を更に含む
クエリ最適化方法。
【請求項１１】
請求項１０に記載のクエリ最適化方法であって、
同じ処理系をコピーし、コピーした処理系を起動することと、
前記最適化プラン要素リスト内の要素から、貪欲法（欲張り法）のアルゴリズムを用いてコストを計算する評価関数を最小にする結合木の選択を行うことと、
自身がコピー処理系か非コピー処理系かを判断することと、
自身がコピー処理系である場合、非コピー処理系からの問い合わせ待ちを行い、コピーを実施した非コピー処理系からの問い合わせの際に指定される中間成果表の結合木の種類を判定し、外部側／駆動表か、内部側／参照表かを評価し、どのサイトのどの表と結合演算を行うか、を非コピー処理系に応答し、コピー処理系を終了することと、
自身が非コピー処理系である場合、結合木を新たな中間成果表に仮置きし、コピー処理系に問い合わせることと、
配置評価関数を呼び出し、前記中間成果表を配置するべきサイトと当該サイトの索引の作成方針で最適な案を取り出すことと、
前記配置評価関数の結果に基づき、所定の箇所に前記中間生成結果を配置することと
を更に含む
クエリ最適化方法。
【請求項１２】
請求項１１に記載のクエリ最適化方法であって、
前記配置評価関数の処理において、次の結合演算先を確認し、次の結合演算先で利用されるサイト群を取り出して、サイト仮リストに追加することと、
前記サイト仮リストに含まれないサイトを取り出し、候補仮リストに追加することと、
探索用の候補エリアを準備し、初期化することと、
順次、サイト情報を読み出し、当該サイトに関するレイテンシ及び信頼性に関する数値情報を読み出すことと、
候補エリアで初期化されたものが残っている場合、最初の所定数のサイトを候補として、前記探索用の候補エリアにセットすることと、
候補エリアが既にセットされ、前記サイト仮リストに登録されていない場合、レイテンシ及び信頼性に関する数値情報がより高評価であれば、前記探索用の候補エリアに記載されているサイトを置き換えることと、
新たな候補となるサイトが特定された場合、当該サイトを前記サイト仮リストに追加することと、
中間成果表の結合木の作成件数から表作成コストを見積もることと、
前記表作成コストの見積りに対し、正規化されたレイテンシに関する数値情報並びに信頼性に関する数値情報の逆数を重畳し、全体コストを求め、全体コストに対して計画番号を付け、候補の一つとして評価リストに追加することと、
索引の作成可能性を判定し、索引が作成可能である場合、全体コストから索引作成コストを見積り、索引作成コストも組み込んだ全体コストを改めて計算し、改めて計算した全体コストに対して計画番号を付け、別候補として前記評価リストに追加することと、
前記評価リスト内のデータに関して、全体コストでソートし序列化を行い、全体コストが最小のものを第一案として記憶することと、
前記第一案と同類の構成で配置先が異なり、全体コストが次に小さいものを第二案として記憶することと、
前記第一案、及び前記第二案を回答することと
を更に含む
クエリ最適化方法。
【請求項１３】
請求項９乃至１２のいずれか一項に記載のクエリ最適化方法を、計算機に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリ最適化システムに関し、特にクエリの中間成果の配置方式を評価するクエリ最適化システムに関する。
【背景技術】
【０００２】
クエリ（ｑｕｅｒｙ）の中間成果の配置方式を評価するクエリ最適化方式（クエリ最適化システム）に関連する代表的な既存技術を開示する文献として、以下のような文献がある。【０００３】
＜非特許文献１＞Ｄ．Ｋｏｓｓｍａｎｎ，Ｋ．Ｓｔｏｃｋｅｒ，”Ｉｔｅｒａｔｉｖｅ  Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ：Ａ  Ｎｅｗ  Ｃｌａｓｓ  ｏｆ  Ｑｕｅｒｙ  Ｏｐｔｉｍｉｚａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍｓ”，  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ，  Ｖｏｌ．２５，  Ｎｏ．１，  Ｍａｒｃｈ  ２０００．【０００４】
＜非特許文献２＞Ｅ．Ｊ．Ｓｈｅｋｉｔａ，Ｈ．Ｃ．Ｙｏｕｎｇ，Ｋ．Ｌ．Ｔａｎ，”Ｍｕｌｔｉ−Ｊｏｉｎ  Ｏｐｔｉｍｉｚａｔｉｏｎ  ｆｏｒ  Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９ｔｈ  ＶＬＤＢ  Ｃｏｎｆｅｒｅｎｃｅ，  １９９３．【０００５】
＜特許文献１＞特開２００２−２２２１０８号公報【０００６】
＜非特許文献１＞では、クエリの中間成果の配置方式を評価する従来のクエリ最適化方式について言及しているが、中間成果の配置方式に関して、その手法を明確に言及している訳ではない。【０００７】
＜非特許文献２＞では、クエリ最適化方式で中間成果をストレージ（Ｓｔｏｒａｇｅ：外部記憶装置）等に書き出すことについて具体的に言及している。但し、これは単一のシステム内の機能モジュールを前提としており、２００９年度の今日的な課題である広域な計算機資源の融通、調達、仮想化を前提とした事項を扱っている訳ではない。【０００８】
これに対して、＜特許文献１＞では、クエリ最適化に関する手法ではなく、中間成果の外部配置を前提とした既存技術を説明している。【０００９】
＜従来技術のクエリ最適化方式＞
ここで、＜非特許文献１＞から従来技術のクエリ最適化方式を抽出し、具体的な手順として示す。【００１０】
（ステップ．１）では、指定クエリの構文解析を行い、参照する表集合｛Ｒ１，Ｒ２，．．．，Ｒｎ｝を取り出す。【００１１】
（ステップ．２）では、その配下の（ステップ．２．１）において、表集合の各要素表Ｒｍで索引を効果的に利用する等の想定される全てのアクセスパターンを抽出した上で、仮結合要素リストに追加する。これを全ての要素表Ｒｍに対して行う（ｍ＝１〜ｎ）。これにより、最適化の候補抽出を行うことになる。【００１２】
（ステップ．３）では、その配下の（ステップ．３．１）において、（ステップ．２．１）で実施した各要素表Ｒｍに関して仮結合要素リストから最適なアクセス条件のものを一つ取り出し、取り出したもののみを残して他を仮結合要素リストから削除することでコストを最適化するクエリ要素の選別を行う。これを全ての要素表Ｒｍに対して行う（ｍ＝１〜ｎ）。【００１３】
（ステップ．４）では、仮結合要素リストを削除する。【００１４】
（ステップ．５）では、結合要素リストの初期版｛Ｒ１ｏ，Ｒ２ｏ，Ｒ３ｏ，．．．，Ｒｎｏ｝を作成し、最適化プラン要素リストにも追加する。【００１５】
（ステップ．６）では、結合要素リスト内の要素数が１になるまで、配下の処理を繰り返して実施する。【００１６】
［（ステップ．６）配下の処理］
まず、（ステップ．６．１）では、最大ブロックサイズｋを、指定値、もしくは結合要素リストの要素数のうち、小さいほうに設定する。続いて、（ステップ．６．２）では、結合数を２に指定する。続いて、（ステップ．６．３）では、指定結合数≦最大ブロック数ｋの条件を満足する限り、配下の処理を繰り返して実施する。【００１７】
［（ステップ．６．３）配下の処理］
まず、（ステップ．６．３．１）では、指定結合数分の組合せを構成する全ての場面を、結合要素リストの現版｛Ｒ１ｏ，Ｒ２ｏ，Ｒ３ｏ，．．．，Ｒｎｏ｝から取り出し、仮リストを作成し、追加する。続いて、（ステップ．６．３．２）では、全ての仮リスト要素数分、配下の処理を繰り返して実施する。【００１８】
［（ステップ．６．３．２）配下の処理］
まず、（ステップ．６．３．２．１）では、仮リストから１要素を取り出す。続いて、（ステップ．６．３.２．２）では、仮リスト部分１，２が伴に定義できるまで、配下の処理を繰り返して実施する。【００１９】
［（ステップ．６．３．２．２）配下の処理］
まず、（ステップ．６．３．２．２．１）では、要素を２つに分割し、要素｛Ｒ１ｏ｝の組合せ２組を作成し、｛仮リスト部分１｝｛仮リスト部分２｝を作成する。続いて、（ステップ．６．３．２．２．２）では、｛仮リスト部分１｝｛仮リスト部分２｝の組合せで、仮操作リストに追加する。続いて、（ステップ．６．３．２．２．３）では、｛仮リスト部分２｝｛仮リスト部分１｝の組合せで、仮操作リストに追加する。【００２０】
［（ステップ．６．３）配下の処理の続き１］
（ステップ．６．３．２）の終了後、（ステップ．６．３）配下の（ステップ．６．３．３）では、最適化プランリストを初期化する。続いて、（ステップ．６．３．４）では、全ての仮操作リスト要素数分、配下の処理を繰り返して実施する。【００２１】
［（ステップ．６．３．４）配下の処理］
まず、（ステップ．６．３．４．１）では、仮操作リストから１つ取り出す。続いて、（ステップ．６．３．４．２）では、取り出した右側｛仮リスト部分ｘ（ｘ＝１，２）｝の最適化プランを最適化プラン要素リストから取り出すか、もしくは作成する。続いて、（ステップ．６．３．４．３）では、取り出した左側｛仮リスト部分ｘ（ｘ＝１，２）｝の最適化プランを最適化プラン要素リストから取り出すか、もしくは作成する。続いて、（ステップ．６．３．４．４）では、前述の（ステップ．６．３．４．２）（ステップ．６．３．４．３）の２つの最適化プランでの結合プランを作成し、最適化プランリストに追加する。【００２２】
［（ステップ．６．３）配下の処理の続き２］
（ステップ．６．３．４）の終了後、（ステップ．６．３）配下の（ステップ．６．３．５）では、最適化プランリストから最適なものを１つ取り出し、それを最適化プラン要素リストに追加する。続いて、（ステップ．６．３）配下の（ステップ．６．３．６）では、最適化プランリストの最適でないものを、ライブラリとして整理保持する。続いて、（ステップ．６．３）配下の（ステップ．６．３．７）では、仮リスト、仮操作リストをクリア（消去）する。続いて、（ステップ．６．３）配下の（ステップ．６．３．８）では、結合数に１を加算（ｉｎｃｒｅｍｅｎｔ）する（結合数←（結合数＋１））。【００２３】
［（ステップ．６）配下の処理の続き］
（ステップ．６．３）の終了後、（ステップ．６）配下の（ステップ．６．４）では、最適化プラン要素リスト内の要素から、貪欲法（欲張り法）のアルゴリズム（Ｇｒｅｅｄｙ  Ａｌｇｏｒｉｔｈｍ）を用いてコストを計算する評価関数を最小にする結合木の選択を行う。続いて、（ステップ．６）配下の（ステップ．６．５）では、結合木を｛Ｔｋｏ｝とする。続いて、（ステップ．６）配下の（ステップ．６．６）では、結合木｛Ｔｋｏ｝の要素を結合要素リストの現版｛Ｒ１ｏ，Ｒ２ｏ，Ｒ３ｏ，．．．，Ｒｎｏ｝に追加する。続いて、（ステップ．６）配下の（ステップ．６．７）では、結合木｛Ｔｋｏ｝を構成する結合要素を結合要素リストの現版｛Ｒ１ｏ，Ｒ２ｏ，Ｒ３ｏ，．．．，Ｒｎｏ｝から削除する。【００２４】
（ステップ．６）の終了後、（ステップ．７）では、結合要素リストの現版｛Ｔｍｏ｝から、残った最適化を実施し、最適化プラン追加する。【００２５】
続いて、（ステップ．８）では、最適化プランを１つ選択する。【００２６】
続いて、（ステップ．９）では、結合要素リストの現版｛Ｒ１ｏ，Ｒ２ｏ，Ｒ３ｏ，．．．，Ｒｎｏ｝を使い、最適化プランを表現し直す。【００２７】
続いて、（ステップ．１０）では、最適化プランを応答する。【００２８】
当該最適化手法では、大きく２つのアルゴリズムを組み合わせている。一つは「動的計画法（Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ）のアルゴリズム」である。具体的には、（ステップ．６．３）の一連の領域が該当する。もう一つは「貪欲法（欲張り法）のアルゴリズム」であり、（ステップ．６．４）等が該当する。この方法では、最大ブロックサイズと呼ぶ結合領域の大きさ範囲を指定し、当初、動的計画法のアルゴリズムにより、その最大ブロックサイズを超えない限り、結合演算を実施する。その後、選択した演算結果から貪欲法（欲張り法）のアルゴリズムでコストの最も小さい方法を選択し、それを中間生成結果として置き換える。以上の手順を複数回、繰り返すことで、全体的にコストの最も小さい方法を選択することになる。【００２９】
当該最適化手法のアルゴリズムを平易に説明するため、それを使って実施された場合のモデルについて、図１を用いて説明する。図１には、当該最適化手法により実際にクエリ最適化の処理を実施する際の段取りを模式的に記したものを示す。ここで、例示のため、利用する関係リストは、５つの関係から構成されているとする。具体的には、関係Ｒ１、関係Ｒ２、関係Ｒ３、関係Ｒ４、関係Ｒ５であり、それぞれを（ステップ．５）までで最適化した結果、関係Ｒ１ｏ、関係Ｒ２ｏ、関係Ｒ３ｏ、関係Ｒ４ｏ、関係Ｒ５ｏを含む結合要素リスト３００７を作成する。この結果、初期段階の結果３０００が生成される。【００３０】
第１段階では、２つの関係の結合演算を行う。図１では、結合演算のシンボルを３００６で記す。これは、当該最適化手法では、（ステップ．６．３）までの処理に相当する。この結果、結合候補３００８、３００９、３０１０を含んだ第１段階の２表間結合演算の結果３００１が作成される。【００３１】
同様に、第２段階では、前述の第１段階の２表間結合の結果３００１を基に、３つの関係の結合演算を行う。これは、当該最適化手法では、（ステップ．６．３）までの処理に相当する。この結果、結合候補３０１１、３０１２、３０１３を含んだ第２段階の３表間結合演算の結果３００２が作成される。更に、これを基に、貪欲法（欲張り法）のアルゴリズムでコスト評価を行う。当該最適化手法では、（ステップ．６．４）に相当する。この結果、コスト評価が最小の結合候補３０１２が選択される。なお、貪欲法（欲張り法）のアルゴリズムは一般的であるため、詳細記述はしない。【００３２】
第３段階では、最大ブロックサイズが指定の２を超えるため、一度、中間成果をストレージに書き出すことになる。この場合、結合候補３０１２を結合木｛Ｔｋ１ｏ｝：３０１４に置き換える。その後、（ステップ．６）に戻り、第二段目の処理のため、初期段階と同様な状態に戻る。この場合、結合要素リスト３００７には、結合木｛Ｔｋ１ｏ｝：３０１４、並びに関係Ｒ３ｏ：３０１５、関係Ｒ５ｏ：３０１６が残り、その結果３００３として定義される。【００３３】
第４段階では、２段目の２つの関係の結合演算を行う。これは、当該最適化手法では、（ステップ．６．３）までの処理に相当する。この結果、結合候補３０１７、３０１８、３０１９を含んだ第２段階の２表間結合演算の結果３００４が作成される。【００３４】
第５段階では、第３段階と同様の処理を行い、３表間の結合演算を行う。この場合、関係Ｒ３ｏ：３０１５、関係Ｒ５ｏ：３０１６を先に結合演算した結果と結合木｛Ｔｋ１ｏ｝：３０１４の結合演算を３表間で行い、結合候補３０２０が選択され、その上で結合要素リスト３００７に反映される。この時点で、（ステップ．６）で記載した条件を満たさないため、（ステップ．７）に移行することになる。その後、（ステップ．９）により結合木を当初の結合要素リスト３００７の要素関係Ｒ１ｏ、関係Ｒ２ｏ、関係Ｒ３ｏ、関係Ｒ４ｏ、関係Ｒ５ｏで結合木３０２１を再構成し、所望の最適化案を作成する。それにより、結果３００５として生成される。【００３５】
＜特許文献１＞では、クエリ最適化に関する手法ではなく、作成されるレプリカの配置方法に関係するものである。図２Ａ、図２Ｂに、＜特許文献１＞の記載を基に、装置構成を記したものを示す。装置構成は、大きく３つの機能層を含む。第１の機能層４１００は、アプリケーションプログラム−１：４００７、アプリケーションプログラム−Ｌ：４００８が含まれる機能層である。第２の機能層４２００は、データベースをアクセスしデータ収集部４００３が配置される機能層である。第３の機能層４３００は、リソース管理／トランザクション制御部４０１１、４０１２や分散ストレージ４００４等が含まれる機能層である。各々の機能層は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）／ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）／Ｉｎｔｅｒｎｅｔ等、各種ネットワーク４００１、４００２を介して相互にアクセスする。【００３６】
アプリケーションプログラム−１：４００７は、データベースアクセスクライアント部−１：４００９を含む。同様に、アプリケーションプログラム−Ｌ：４００８は、データベースアクセスクライアント部−Ｌ：４０１０を含む。データベースアクセスクライアント部−１：４００９及びデータベースアクセスクライアント部−Ｌ：４０１０は、データ収集部４００３にＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）等の実行クエリを要求及び送信する。【００３７】
前述のリソース管理／トランザクション制御部４０１１や前述の分散ストレージ４００４等が含まれる機能層には、現在、２つのサイトを前提に記しているが、これに限定される訳ではない。各サイトは、各々、リソース管理／トランザクション制御部４０１１、４０１２を含む。【００３８】
リソース管理／トランザクション制御部４０１１を持つサイトには、分散ストレージ４００４が関係付けられて配置されている。当該分散ストレージ４００４には、データベースの表領域、索引領域、Ｌｏｇ（ログ），ジャーナル等が格納される。この場合、分散ストレージは１つとは限らず、２つ以上でも良い。すなわち、分散ストレージは、少なくとも１つ存在する。【００３９】
当該分散ストレージ４００４内のデータベースの表領域、索引領域には、関係Ｒ１１に相当する表Ｔａｂｌｅ．１１：４０１４、関係Ｒ１２に相当する表Ｔａｂｌｅ．１２：４０１５、関係Ｒ１ｎに相当する表Ｔａｂｌｅ．１ｎ：４０１６、中間成果の表４０１８が格納される。また、索引領域には、索引４０１７、Ｌｏｇ，ジャーナル４０１９が格納される。【００４０】
リソース管理／トランザクション制御部４０１２を持つサイトは、リソース管理／トランザクション制御部４０１１を持つサイトのレプリカに相当する。このため、前述のリソース管理／トランザクション制御部４０１１を持つサイトと同じ構成を取る。【００４１】
データ収集部４００３に対して、部分レプリカを配置するため、他の分散ストレージ４００６が配置されている。ここには、リソース管理／トランザクション制御部４０１３が配置され、前述のリソース管理／トランザクション制御部４０１１を持つサイトと概ね同じ構成を取る。【００４２】
ここで、データ収集部４００３は、データベースアクセスクライアント部−１、４００９、データベースアクセスクライアント部−Ｌ：４０１０からの問い合わせメッセージｓ４０２９、ｓ４０３５に基づき、リソース管理／トランザクション制御部４０１１、４０１２に対する要求メッセージｓ４０３０、ｓ４０３１として転送し、その結果、当該分散ストレージ４００４、同様に、分散ストレージ４００５内で検索及び取得されたデータを応答メッセージｓ４０３３、ｓ４０３２として受信する。【００４３】
続けて、データ収集部４００３は、複数の問い合わせメッセージｓ４０２９、ｓ４０３５内で指定された複数の条件を含む問い合わせ群をグループ化し、この条件毎に問い合わせの内容及び条件の集合を求める。また、データ収集部４００３は、当該条件の重複範囲に基づいて条件を判定する。更に、データ収集部４００３は、問い合わせの重複回数に応じて有効度に関する評価指標を設定する。【００４４】
データ収集部４００３は、この有効度に関する評価指標に応じて、リソース管理／トランザクション制御部４０１３の分散ストレージ４００６に部分的なレプリカを配置することになる。【００４５】
前述のように、過去の個別技術（従来技術）は、大きくはクエリ最適化方式に関するもの、中間成果の外部配置を前提としたレプリカ技術に関するものに分類される。そして、課題については、以下のようになる。【００４６】
例えば、データベース管理システムの要素技術が、ネットワーク全体に広く、緩やかに連携する環境に分散し、大規模に展開された場合、クエリの中間成果を配置する分散ストレージも広くネットワーク環境に分散されることになる。【００４７】
しかし、従来のクエリの最適化手法では、最適化の結果発生するクエリの中間成果を合理的な判断の下で、どの分散ストレージサイトに配置するべきかが考慮されておらず、結果としてクエリの最適化が実施段階で為されていないという課題が存在する。【００４８】
この結果、データベースアクセスクライアントの利用者が取り決めた合意サービス水準を満足し得ないという課題も発生する。これを前述の事例毎に記すと以下のようになる。【００４９】
＜特許文献１＞では、問い合わせ群をグループ化し、この条件毎に問い合わせの内容及び条件の集合を求める処理を含み、当該条件の重複範囲に基づいて条件を判定、更に、問い合わせの重複回数に応じて有効度と言う評価指標を設定した上で、その有効度がある程度のものを部分レプリカとして配置することを開示している。部分レプリカは中間成果とは異なるが、配置箇所を複数の選択肢の中から合理的な判断の下で評価している訳ではない。この結果、上記の課題に対して応えることができない。【００５０】
＜非特許文献１＞では、現在のクエリ最適化方式の概要について開示している。しかし、レプリカ等の利用は言及されているものの、中間成果の配置を前提とした提案が成されていない。このため、２００９年度の今日的な課題である広域な計算機資源の融通、調達、仮想化を前提としたクエリの最適化を扱っている訳ではなく、上記の課題に対して応えることができない。【００５１】
＜非特許文献２＞では、中間成果をストレージ等に書き出すクエリ最適化方式の概要について開示している。しかし、最適化の結果発生するクエリの中間成果を合理的な判断の下で、どの分散ストレージサイトに配置するべきかが考慮されておらず、結果としてクエリの最適化が実施段階で為されていないという課題が存在する。
【先行技術文献】
【特許文献】
【００５２】
【特許文献１】特開２００２−２２２１０８号公報
【非特許文献】
【００５３】
【非特許文献１】Ｄ．Ｋｏｓｓｍａｎｎ，Ｋ．Ｓｔｏｃｋｅｒ，”Ｉｔｅｒａｔｉｖｅ  Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ：Ａ  Ｎｅｗ  Ｃｌａｓｓ  ｏｆ  Ｑｕｅｒｙ  Ｏｐｔｉｍｉｚａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍｓ”，  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ，  Ｖｏｌ．２５，  Ｎｏ．１，  Ｍａｒｃｈ  ２０００．
【非特許文献２】Ｅ．Ｊ．Ｓｈｅｋｉｔａ，Ｈ．Ｃ．Ｙｏｕｎｇ，Ｋ．Ｌ．Ｔａｎ，”Ｍｕｌｔｉ−Ｊｏｉｎ  Ｏｐｔｉｍｉｚａｔｉｏｎ  ｆｏｒ  Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９ｔｈ  ＶＬＤＢ  Ｃｏｎｆｅｒｅｎｃｅ，  １９９３．
【発明の概要】
【００５４】
本発明の目的は、データベース管理システム内部のクエリを最適化することであり、特に大規模に仮想化されたストレージを利用する環境において、クエリの最適化の途上で発生する中間成果をより合理的に配置し、実施段階でもクエリの最適化を実現することである。更に、この結果、データベースアクセスクライアントの利用者が取り決めた合意サービス水準を満足させるようにすることである。
【００５５】
上記の目的を達成するため、本発明では、データベース管理システムのクエリの中間成果の配置方式を評価するクエリ最適化システムを提供する。このクエリ最適化システムでは、データを保持するサイトに関するレイテンシ（Ｌａｔｅｎｃｙ）及び信頼性に関する数値情報を取り出す。なお、レイテンシとは、データの転送要求などのリクエストを発してから、リクエストの結果が返ってくるまでにかかる遅延時間のことである。また、当該レイテンシに関する数値情報並びに当該信頼性に関する数値情報をクエリのコスト値に重畳し拡張コスト値を求める。また、拡張コスト値で序列化した場合に上位で妥当な（所定の条件に適合する）指定値を持つサイトを選定する。また、最適化の結果発生する中間成果の配置先サイトを選定するため、アルゴリズム中のパラメータを一部変更した処理系自身のコピーを作成することで先読みを実施する。また、当該先読みの結果、中間成果を１つ以上のサイトに配置する。
【００５６】
これにより、配置の選定を合理的に実施できるようになる。
【図面の簡単な説明】
【００５７】
【図１】従来技術の「クエリ最適化方式」により生成されるクエリ最適化結果の過程を例示した説明図である。
【図２Ａ】従来技術の「クエリ最適化方式」の一部を実現する装置構成を記したブロック図である。
【図２Ｂ】従来技術の「クエリ最適化方式」の一部を実現する装置構成を記したブロック図である。
【図３Ａ】本発明の「クエリの中間成果の配置方式を評価するクエリ最適化方式」を実現する装置構成を記したブロック図である。
【図３Ｂ】本発明の「クエリの中間成果の配置方式を評価するクエリ最適化方式」を実現する装置構成を記したブロック図である。
【図４Ａ】本発明の「クエリの中間成果の配置方式を評価するクエリ最適化方式」を実現する装置構成の上で、当該クエリ最適化方式を実施する際の全体の処理内容を記したブロック図である。
【図４Ｂ】本発明の「クエリの中間成果の配置方式を評価するクエリ最適化方式」を実現する装置構成の上で、当該クエリ最適化方式を実施する際の全体の処理内容を記したブロック図である。
【図５Ａ】本発明の「クエリの中間成果の配置方式を評価するクエリ最適化方式」の手順で、特徴的な部分を抜き出して、模式的に記した説明図である。
【図５Ｂ】本発明の「クエリの中間成果の配置方式を評価するクエリ最適化方式」の手順で、特徴的な部分を抜き出して、模式的に記した説明図である。
【発明を実施するための形態】
【００５８】
以下に、本発明の第１実施形態について添付図面を参照して説明する。
【００５９】
＜基本構成に関する説明＞
本発明である「クエリの中間成果の配置方式を評価するクエリ最適化方式（クエリ最適化システム）」は、図３Ａ、図３Ｂのような装置構成を前提とし、その環境において処理が実施される。
【００６０】
そこで、本発明である「クエリの中間成果の配置方式を評価するクエリ最適化方式」の説明の前段として、前提とする図３Ａ、図３Ｂの装置構成、図４Ａ、図４Ｂで記される全体の処理内容について説明する。
【００６１】
図３Ａ、図３Ｂの装置構成は、代表的であり、最も本質的な構成要素のみを取り出して定義している。このため、これ以外の構成のものを含んでも構わない。装置構成は、大きく１つ以上のネットワークと、少なくとも３つの機能層を含む。ネットワークとして、ＬＡＮ／ＷＡＮ／Ｉｎｔｅｒｎｅｔ等、各種ネットワーク１００１、１００２を別のものとして定義しているが、これらと同じものと考えることも可能である。また、その種類に関して、ここでは区別する理由は存在しない。なお、各種ネットワーク１００１、１００２には、ルータやスイッチ等の中継装置も含まれるものとする。
【００６２】
３つの機能層のうち、第１の機能層１１００は、アプリケーションプログラム−１：１０１３、アプリケーションプログラム−Ｌ：１０１４が含まれる機能層である。第２の機能層１２００は、データベースアクセス部−１：１０１１、データベースアクセス部−Ｍ：１０１２が含まれる機能層である。第３の機能層１３００は、リソース管理／トランザクション制御部１０１５、１０１６、１０１７、１０１８や分散ストレージ１００３等が含まれる機能層である。
【００６３】
各々の機能層は、前述のＬＡＮ／ＷＡＮ／Ｉｎｔｅｒｎｅｔ等、各種ネットワーク１００１、１００２を介して相互にアクセスする。
【００６４】
［ハードウェアの例示］
各々の機能層の例として、ＰＣ（パソコン）、アプライアンス（ａｐｐｌｉａｎｃｅ）、ワークステーション、メインフレーム、スーパーコンピュータ等の計算機を想定している。また、計算機に限らず、ルータやスイッチ等の中継装置、ファイアウォールや帯域制御装置等の中間装置、その他の通信機器、電子機器、専用デバイス等でも良い。
【００６５】
図示しないが、上記のような計算機等は、プログラムに基づいて駆動し所定の処理を実行するプロセッサと、当該プログラムや各種データを記憶するメモリと、ネットワークとの通信に用いられるインタフェースによって実現される。
【００６６】
上記のプロセッサの例として、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、マイクロプロセッサ（ｍｉｃｒｏｐｒｏｃｅｓｓｏｒ）、マイクロコントローラ、或いは、専用の機能を有する半導体集積回路（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ（ＩＣ））等が考えられる。
【００６７】
上記のメモリの例として、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やフラッシュメモリ等の半導体記憶装置、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）やＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の補助記憶装置、又は、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のリムーバブルディスクや、ＳＤメモリカード（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ  ｍｅｍｏｒｙ  ｃａｒｄ）等の記憶媒体（メディア）等が考えられる。また、レジスタ（ｒｅｇｉｓｔｅｒ）でも良い。
【００６８】
なお、上記のプロセッサ及び上記のメモリは、一体化していても良い。例えば、近年では、マイコン等の１チップ化が進んでいる。従って、計算機に搭載される１チップマイコンが、プロセッサ及びメモリを備えている事例が考えられる。
【００６９】
上記のインタフェースの例として、ネットワーク通信に対応した基板（マザーボード、Ｉ／Ｏボード）やチップ等の半導体集積回路、ＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）等のネットワークアダプタや同様の拡張カード、アンテナ等の通信装置、接続口（コネクタ）等の通信ポート等が考えられる。
【００７０】
また、ネットワークの例として、インターネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、無線ＬＡＮ（Ｗｉｒｅｌｅｓｓ  ＬＡＮ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、バックボーン（Ｂａｃｋｂｏｎｅ）、ケーブルテレビ（ＣＡＴＶ）回線、固定電話網、携帯電話網、ＷｉＭＡＸ（ＩＥＥＥ  ８０２．１６ａ）、３Ｇ（３ｒｄ  Ｇｅｎｅｒａｔｉｏｎ）、専用線（ｌｅａｓｅ  ｌｉｎｅ）、ＩｒＤＡ（Ｉｎｆｒａｒｅｄ  Ｄａｔａ  Ａｓｓｏｃｉａｔｉｏｎ）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、シリアル通信回線、データバス等が考えられる。
【００７１】
すなわち、各々の機能層内の各部（内部構成）は、専用デバイスに限らず、モジュール（ｍｏｄｕｌｅ）又はコンポーネント（ｃｏｍｐｏｎｅｎｔ）でも良い。
【００７２】
但し、実際には、これらの例に限定されない。
【００７３】
アプリケーションプログラム−１：１０１３は、データベースアクセスクライアント部−１：１０６０を含む。データベースアクセスクライアント部−１：１０６０は、データベースアクセス部−１：１０１１にＳＱＬ等の実行クエリを要求及び送信する。
【００７４】
データベースアクセス部−１：１０１１は、クエリ受付部１０４８と、クエリ解析部１０４９と、ディクショナリアクセス部１０５０と、最適化部１０５１と、処理実行部−１：１０５３と、処理実行部−Ｎ：１０５４を含む。クエリ受付部１０４８は、当該データベースアクセスクライアント部−１：１０６０からの要求実行クエリを受け付ける。ディクショナリアクセス部１０５０は、その要求実行クエリに含まれるべき定義情報を管理するディクショナリに対するアクセスを行う。クエリ解析部１０４９は、当該ディクショナリアクセス部１０５０の情報を基に要求実行クエリを分析する。最適化部１０５１は、解析した要求実行クエリの最適化を、本発明である「クエリの中間成果の配置方式を評価するクエリ最適化方式」を用いて行う。処理実行部−１：１０５３及び処理実行部−Ｎ：１０５４は、当該最適化部１０５１の結果を受けて、前述の要求実行クエリを分解し、個別の実行単位を実施する。
【００７５】
更に、データベースアクセス部−１：１０１１は、統計情報管理部エージェント管理部１０５２と、トランザクション管理制御部１０５５と、Ｌｏｇ，ジャーナル１０５６も含む。トランザクション管理制御部１０５５は、処理実行部−１：１０５３並びに処理実行部−Ｎ：１０５４が、中間成果を生成管理するシステムトランザクションを実施する。Ｌｏｇ，ジャーナル１０５６は、システムトランザクションのログとジャーナルを管理する。統計情報管理部エージェント管理部１０５２は、実際の要求実行クエリの要素を実施した結果を収集し、前述の最適化部１０５１の処理に反映する。
【００７６】
前述のクエリ受付部１０４８は、実際に要求された要求実行クエリである指定クエリ１０５７を保持する。前述の処理実行部−１：１０５３並びに前述の処理実行部−Ｎ：１０５４は、分解された実行単位である１０５８、並びに１０５９を含む。
【００７７】
図３Ａ、図３Ｂでは、前述のリソース管理／トランザクション制御部１０１５や前述の分散ストレージ１００３等が含まれる機能層に４つのサイトを記しているが、これに限定される訳ではない。各サイトは、各々、リソース管理／トランザクション制御部１０１５、１０１６、１０１７、１０１８を含む。
【００７８】
リソース管理／トランザクション制御部１０１５を持つサイトには、分散ストレージ１００３、並びに分散ストレージ１００４が関係付けられて配置されている。当該分散ストレージ１００３は、データベースの表領域、索引領域を持つ。別の分散ストレージ１００４には、Ｌｏｇ，ジャーナル等が格納される。この場合、分散ストレージは２つとは限らず、１つもしくは３つ以上でも良い。すなわち、分散ストレージは、少なくとも１つ存在する。
【００７９】
更に、リソース管理／トランザクション制御部１０１５を持つサイトは、性能／エラー情報／統計情報サービス１０１９も含む。
【００８０】
当該分散ストレージ１００３内のデータベースの表領域、索引領域には、関係Ｒ１に相当する表Ｔａｂｌｅ．１：１０２３、関係Ｒ２に相当する表Ｔａｂｌｅ．２：１０２４、関係Ｒｎに相当する表Ｔａｂｌｅ．ｎ：１０２５、中間成果の表１０３０が格納される。また、索引領域には、索引１０２９が格納される。
【００８１】
前述の分散ストレージ１００４は、Ｌｏｇ，ジャーナル１０３６と、性能情報，エラー情報１０３７と、オブジェクト毎の統計情報１０３８を含む。性能情報，エラー情報１０３７は、全般的な性能情報とエラー情報を管理する。なお、情報の管理手法としては、情報の統合／リスト化／グループ化／データベース化等が考えられる。但し、実際には、これらの例に限定されない。オブジェクト毎の統計情報１０３８は、分散ストレージ１００３上の前述の表Ｔａｂｌｅ．１：１０２３と、前述の表Ｔａｂｌｅ．２：１０２４と、前述の表Ｔａｂｌｅ．ｎ：１０２５と、前述の索引１０２９に対するアクセス性能の統計情報を管理する。
【００８２】
リソース管理／トランザクション制御部１０１６を持つサイトは、リソース管理／トランザクション制御部１０１５を持つサイトのレプリカに相当する。このため、前述のリソース管理／トランザクション制御部１０１５を持つサイトと同じ構成を取る。
【００８３】
リソース管理／トランザクション制御部１０１６を持つサイトには、分散ストレージ１００５、並びに分散ストレージ１００６が関係付けられて配置されている。当該分散ストレージ１００５は、データベースの表領域、索引領域を持つ。別の分散ストレージ１００６には、Ｌｏｇ，ジャーナル等が格納される。この場合、分散ストレージは２つとは限らず、１つもしくは３つ以上でも良い。すなわち、分散ストレージは、少なくとも１つ存在する。
【００８４】
更に、リソース管理／トランザクション制御部１０１６を持つサイトは、性能／エラー情報／統計情報サービス１０２０も含む。
【００８５】
当該分散ストレージ１００５内のデータベースの表領域、索引領域には、関係Ｒ１に相当し、前述の表Ｔａｂｌｅ．１：１０２３のレプリカである表Ｔａｂｌｅ．１：１０２６、関係Ｒ２に相当し、前述の表Ｔａｂｌｅ．２：１０２４のレプリカである表Ｔａｂｌｅ．２：１０２７、関係Ｒｎに相当し、前述の表Ｔａｂｌｅ．ｎ：１０２５のレプリカである表Ｔａｂｌｅ．ｎ：１０２８、中間成果の表１０３２が格納される。また、索引領域には、索引１０３１が格納される。
【００８６】
前述の分散ストレージ１００６は、Ｌｏｇ，ジャーナル１０３９と、性能情報，エラー情報１０４０と、オブジェクト毎の統計情報１０４１を含む。性能情報，エラー情報１０４０は、全般的な性能情報とエラー情報を管理する。オブジェクト毎の統計情報１０４１は、分散ストレージ１００５上の前述の表Ｔａｂｌｅ．１：１０２６と、前述の表Ｔａｂｌｅ．２：１０２７と、前述の表Ｔａｂｌｅ．ｎ：１０２８と、前述の索引１０３１に対するアクセス性能の統計情報を管理する。
【００８７】
リソース管理／トランザクション制御部１０１７を持つサイトは、索引管理に特化したサイトに相当する。リソース管理／トランザクション制御部１０１７を持つサイトには、分散ストレージ１００７、並びに分散ストレージ１００８が関係付けられて配置されている。当該分散ストレージ１００７は、データベースの表領域、索引領域を持つ。別の分散ストレージ１００８には、Ｌｏｇ，ジャーナル等が格納される。この場合、分散ストレージは２つとは限らず、１つもしくは３つ以上でも良い。すなわち、分散ストレージは、少なくとも１つ存在する。
【００８８】
更に、リソース管理／トランザクション制御部１０１７を持つサイトは、性能／エラー情報／統計情報サービス１０２１も含む。
【００８９】
当該分散ストレージ１００７内のデータベースの表領域、索引領域には、中間成果の表１０３４が格納される。また、索引領域には、索引１０３３が格納される。
【００９０】
前述の分散ストレージ１００８は、Ｌｏｇ，ジャーナル１０４２と、性能情報，エラー情報１０４３と、オブジェクト毎の統計情報１０４４を含む。性能情報，エラー情報１０４３は、全般的な性能情報とエラー情報を管理する。オブジェクト毎の統計情報１０４４は、分散ストレージ１００７上の前述の索引１０３３に対するアクセス性能の統計情報を管理する。
【００９１】
リソース管理／トランザクション制御部１０１８を持つサイトは、中間成果の管理に特化したサイトに相当する。リソース管理／トランザクション制御部１０１８を持つサイトには、分散ストレージ１００９、並びに分散ストレージ１０１０が関係付けられて配置されている。当該分散ストレージ１００９は、データベースの表領域、索引領域を持つ。別の分散ストレージ１０１０には、Ｌｏｇ，ジャーナル等が格納される。この場合、分散ストレージは２つとは限らず、１つもしくは３つ以上でも良い。すなわち、分散ストレージは、少なくとも１つ存在する。
【００９２】
更に、リソース管理／トランザクション制御部１０１８を持つサイトは、性能／エラー情報／統計情報サービス１０２２も含む。
【００９３】
当該分散ストレージ１００９内のデータベースの表領域、索引領域には、中間成果の表１０３５が格納される。
【００９４】
前述の分散ストレージ１００９は、Ｌｏｇ，ジャーナル情報１０４５と、性能情報，エラー情報１０４６と、オブジェクト毎の統計情報１０４７を含む。性能情報，エラー情報１０４６は、全般的な性能情報とエラー情報を管理する。オブジェクト毎の統計情報１０４７は、分散ストレージ１０１０上の任意オブジェクトに対するアクセス性能の統計情報を管理する。
【００９５】
＜全体動作の説明＞
ここでは、本発明である「クエリの中間成果の配置方式を評価するクエリ最適化方式」の説明の前段として、図４Ａ、図４Ｂで記される全体の処理内容について説明する。
【００９６】
前述のデータベースアクセスクライアント部−１：１０６０は、データベースをアクセスする場合、データベースアクセス部−１：１０１１内のクエリ受付部１０４８に、要求実行クエリをメッセージｓ１００として送信する。メッセージｓ１００には、ＳＱＬでの記述が記されており、関係Ｒ１から関係Ｒｎの自然結合を実施した要求実行クエリの記述が含まれているものとする。
【００９７】
当該クエリ受付部１０４８は、指定クエリ１０５７と同等な指定クエリ表現ｓ１０１をクエリ解析部１０４９に渡す。クエリ解析部１０４９は、ディクショナリアクセス部１０５０から定義情報ｓ１０２を入手し、指定クエリ表現ｓ１０１を中間表現ｓ１０３として変換し、最適化部１０５１に渡す。
【００９８】
最適化部１０５１は、最適化された実行プランを算出し、その一部の実行プラン記述ｓ１２４、ｓ１０５を前述の処理実行部−１：１０５３から前述の処理実行部−Ｎ：１０５４に渡す。最適化に当たっては、統計情報管理部エージェント管理部１０５２から種々のレイテンシ（Ｌａｔｅｎｃｙ）情報、信頼性情報ｓ１０４を入手する。
【００９９】
図４Ａ、図４Ｂの例では、前述の処理実行部−Ｎ：１０５４において、一部実行プラン記述ｓ１０５が渡され、クエリの実行単位１０５８が前述の処理実行部−Ｎ：１０５４内に保持される。また、前述の処理実行部−１：１０５３において、一部実行プラン記述ｓ１２４が渡され、クエリの実行単位１０５９が前述の処理実行部−１：１０５３内に保持される。特にクエリの実行単位１０５９では、中間成果表を利用するのに対して、クエリの実行単位１０５８では当該中間成果表を生成することになる。このため、後に説明するシステムトランザクション処理が実施されることになる。
【０１００】
前述の処理実行部−Ｎ：１０５４は、クエリの実行単位１０５８を処理するため、レプリカの中で最適なサイトとして選択された前述のリソース管理／トランザクション制御部１０１５を持つサイトに対して、クエリ実行要求を含むメッセージｓ１０６を送信する。
【０１０１】
前述のリソース管理／トランザクション制御部１０１５は、メッセージｓ１０６を受け付けると、当該メッセージｓ１０６に記載された内容に従い、関係Ｒ１に相当する表Ｔａｂｌｅ．１：１０２３から該当行ｓ１０７を入手し、これを駆動側として、関係Ｒ２に相当する表Ｔａｂｌｅ．２：１０２４から該当行ｓ１０８を結合しながら入手する。更に、その結合結果を駆動側として、前述の索引１０２９を利用し、主キーの行ＩＤ情報ｓ１１０を入手の後、関係Ｒｎに相当する表Ｔａｂｌｅ．ｎ：１０２５から該当行ｓ１０９を結合しながら入手する。
【０１０２】
その後、前述のリソース管理／トランザクション制御部１０１５は、クエリの実行単位１０５８に対する中間成果情報である応答結果をメッセージｓ１１１として、一度、前述の処理実行部−Ｎ：１０５４に戻す。
【０１０３】
当該メッセージｓ１１１に記載された応答結果は、中間成果表として一時的に分散ストレージ等に記録される必要がある。このため、前述の処理実行部−Ｎ：１０５４は本発明の一部を使って書き出すストレージを決定した後、前述のリソース管理／トランザクション制御部１０１８を保持するサイトに応答結果を含んだ中間成果表の作成要求に関するメッセージｓ１１２を送付する。
【０１０４】
前述のリソース管理／トランザクション制御部１０１８は、当該メッセージｓ１１２を受信するとトランザクションとして中間成果表を生成するため、更新前イメージをＬｏｇ，ジャーナル１０４５に記録するための要求ｓ１１３を送付する。この場合は、中間成果表が存在していないため、実質は存在しない。
【０１０５】
その後、前述のリソース管理／トランザクション制御部１０１８は、当該メッセージｓ１１２に記載された中間成果ｓ１１４を取り出し、中間成果表１０３５に書き込む。その後、トランザクションコミット待ちの状態に遷移し、前述のリソース管理／トランザクション制御部１０１８はコミット待ちメッセージｓ１１６を前述の処理実行部−Ｎ：１０５４に戻す。
【０１０６】
前述の処理実行部−Ｎ：１０５４は、データベースアクセス部−１：１０１１内のトランザクション管理制御部１０５５に対して、トランザクションの状態管理要求ｓ１１７を事前に出している。当該トランザクション管理制御部１０５５は、システムトランザクションに関してＬｏｇ，ジャーナル１０５６に登録要求ｓ１１８を発行している。
【０１０７】
以上の結果、当該トランザクション管理制御部１０５５は、トランザクションを実施する上で特に課題にならないと判断した場合、当該システムトランザクションの要求元である処理実行部−Ｎ：１０５４にその旨を通知する。処理実行部−Ｎ：１０５４は、中間成果表の作成要求に関するメッセージｓ１１２に対するコミット要求メッセージｓ１１９を前述のリソース管理／トランザクション制御部１０１８に送信する。
【０１０８】
前述のリソース管理／トランザクション制御部１０１８が前述のコミット要求メッセージｓ１１９を受信すると、前述のＬｏｇ，ジャーナル１０４５に対してコミット結果書き込みｓ１２０を実施する。
【０１０９】
その後、当該中間成果表１０３５の作成に関するトランザクションの実施結果に関係して前述のリソース管理／トランザクション制御部１０１８のサイト内でオブジェクト毎の統計情報１０４７に実績データを書き込む要求ｓ１２１、並びに性能情報，エラー情報１０４６を書き込む要求ｓ１２２を発行する。
【０１１０】
一連の動作を終了したならば、前述のリソース管理／トランザクション制御部１０１８は、応答メッセージｓ１２３を要求元である処理実行部−Ｎ：１０５４に送付する。
【０１１１】
その後、当該中間成果表１０３５を利用する形で、処理実行部−１：１０５３が起動する。当該処理実行部−１：１０５３において、一部実行プラン記述ｓ１２４が渡され、クエリの実行単位１０５９が前述の処理実行部−１：１０５３内に保持されている。
【０１１２】
前述の処理実行部−１：１０５３はクエリの実行単位１０５９を処理するため、前述のリソース管理／トランザクション制御部１０１８を持つサイトに対してクエリ実行要求を含むメッセージｓ１２５を送信する。それと伴に、レプリカの中で最適なサイトとして選択された前述のリソース管理／トランザクション制御部１０１６を持つサイトに対してクエリ実行要求を含むメッセージｓ１２７を送信する。
【０１１３】
前述のリソース管理／トランザクション制御部１０１８が、クエリ実行要求を含むメッセージｓ１２５を受け付けると、当該メッセージｓ１２５に記載された内容に従い、中間成果表１０３５から該当行ｓ１２６を入手し、要求元の処理実行部−１：１０５９に応答する。
【０１１４】
また、前述のリソース管理／トランザクション制御部１０１６が、クエリ実行要求を含むメッセージｓ１２７を受け付けると、当該メッセージｓ１２７に記載された内容に従い、関係Ｒ（ｋ＋１）に相当する表Ｔａｂｌｅ．（ｋ＋１）等から該当行を入手する。
【０１１５】
その後、前述のリソース管理／トランザクション制御部１０１６は、クエリの実行単位１０５９に対する応答結果をメッセージｓ１２８として、前述の処理実行部−１：１０５３に戻す。
【０１１６】
各々の前述の処理実行部−１：１０５３、並びに前述の処理実行部−Ｎ：１０５４の結果は、それぞれ結果応答ｓ１２９、ｓ１３０として前述のクエリ受付部１０４８に戻され、その結果を統合した上で、呼び出し元のデータベースアクセスクライアント部−１：１０６０へ応答メッセージｓ１３１として戻される。
【０１１７】
前述の最適化部１０５１は、最適化された実行プランを算出する際に統計情報管理部エージェント管理部１０５２から種々のレイテンシ情報、信頼性情報ｓ１０４を入手する。これらは数値で表現された情報である。このため、当該統計情報管理部エージェント管理部１０５２は、各サイト上の性能／エラー情報／統計情報サービス１０１９：１０２０：１０２１：１０２２を介して、それらの情報を入手、管理する。
【０１１８】
例えば、前述のリソース管理／トランザクション制御部１０１５が管理するサイトには、前述の性能／エラー情報／統計情報サービス１０１９が配置されており、前述の性能情報，エラー情報１０３７からは性能／エラー情報ｓ１３４を、前述のオブジェクト毎の統計情報１０３８からは統計情報ｓ１３３を入手する。
【０１１９】
その後、前述の性能／エラー情報／統計情報サービス１０１９は、それらを統合して性能／エラー情報／統計情報報告ｓ１３２として報告する。前述の統計情報管理部エージェント管理部１０５２は、全てのサイト上の性能／エラー情報／統計情報サービス１０１９：１０２０：１０２１：１０２２から、当該性能／エラー情報／統計情報報告ｓ１３２を入手し、各サイトのレイテンシ情報、信頼性情報として管理する。
【０１２０】
＜クエリの中間成果の配置方式を評価するクエリ最適化方式＞
図５Ａ、図５Ｂは、本発明の「クエリの中間成果の配置方式を評価するクエリ最適化方式」の手順で、特徴的な部分を抜き出して、模式的に記した説明図である。当該クエリ最適化方式は、図３Ａ、図３Ｂにおける最適化部１０５１を中心に実装され、その処理過程の中でクエリ解析部１０４９、トランザクション管理制御部１０５５、統計情報管理部エージェント管理部１０５２が利用される。そこで、以下簡単にその手順を記す。
【０１２１】
（ステップ．１）は、クエリ解析部１０４９により実施される。クエリ解析部１０４９は、指定クエリ１０５７の構文解析を行い、参照する表集合｛Ｒ１，Ｒ２，．．．，Ｒｎ｝を取り出す。
【０１２２】
（ステップ．２）は、最適化部１０５１により実施される。このステップでは、その配下の（ステップ．２．１）において、最適化部１０５１は、表集合の各要素表Ｒｍで索引を効果的に利用する等の想定される全てのアクセスパターンを抽出した上で、仮結合要素リストに追加する。これを全ての要素表Ｒｍに対して行う（ｍ＝１〜ｎ）。これにより、最適化の候補抽出を行うことになる。
【０１２３】
（ステップ．３）も、最適化部１０５１により実施される。このステップでは、大きく２つの事項を表集合の全ての各要素表Ｒｍで行う（ｍ＝１〜ｎ）。
【０１２４】
［（ステップ．３）配下の処理］
（ステップ．３）では、始めは配下の（ステップ．３．１）において、（ステップ．２．１）で実施した各要素表Ｒｍに関して仮結合要素リストから最適なアクセス条件のものを一つ取り出し、取り出したもののみを残して他を仮結合要素リストから削除することでコストを最適化するクエリ要素の選別を行う。続けて、配下の（ステップ．３．２）において、仮結合要素リストの各要素に対して、全レプリカ分｛Ｒ１１，Ｒ１２，…，Ｒ１ｒ，Ｒ２１，…，Ｒ２ｒ，．．．，Ｒｎｒ｝のエントリを作成し、仮結合要素リストに追加する。
【０１２５】
（ステップ．４）も、最適化部１０５１により実施される。この（ステップ．４）と（ステップ．５）は、本発明の特徴的な事項の一つであり、（ステップ．４）では配下に２つの手続きを持つ。（ステップ．４）では、仮結合要素リスト中のエントリＲｍｋに対して、配下の処理を繰り返して実施する（ｋ＝１〜ｒ）。
【０１２６】
［（ステップ．４）配下の処理］
（ステップ．４．１）において、当該最適化部１０５１はレプリカ部分も含めて前述の仮結合要素リストから１エントリを取り出し、そのエントリを保持する分散ストレージサイトに相当するレイテンシ及び信頼性に関する数値情報を前述の統計情報管理部エージェント管理部１０５２から取り出す。その後、（ステップ．４．２）において、前述のレイテンシ及び信頼性に関する数値情報を、仮結合要素リストから取り出した前述のエントリに付与する形で、前述の仮結合要素リストを更新する（ｍ＝１〜ｎ）。
【０１２７】
（ステップ．５）も、最適化部１０５１により実施される。（ステップ．５）では、仮結合要素リスト中のエントリＲｍｋに対して、配下の処理を繰り返して実施する（ｍ＝１〜ｎ）。
【０１２８】
［（ステップ．５）配下の処理］
ここでは、（ステップ．５．１）において、該最適化部１０５１は、レプリカ部分も含めて前述の仮結合要素リストから１エントリを取り出す。また、（ステップ．５．２）において、取り出したエントリＲｍｋに対して、配下の処理を繰り返して実施する（ｋ＝１〜ｒ）。（ステップ．５．２）配下の（ステップ．５．２．１）において、取り出したエントリの各レプリカのレイテンシ及び信頼性に関する数値情報を評価する。
【０１２９】
当該評価について、通常、各エントリの評価には、そのコスト値が評価値として記載されており、この最も小さいものが望ましいものとして評価される。本発明では、このコスト値に対して正規化したレイテンシ値を重畳した上で、信頼性の逆数も重畳した、拡張コスト値を定義する。そして、当該拡張コスト値の最小のものを最良とするように評価する。
【０１３０】
正規化されたレイテンシ値は、サイトの性能やＬＡＮ／ＷＡＮ／Ｉｎｔｅｒｎｅｔ等、各種ネットワーク１００２の通信品質が悪化、もしくは配置距離が長い程、大きな値となる。また、サイトの信頼性が低い程、この逆数も大きな値となる。このため、配置位置が遠く、劣悪な品質なものほど、コスト値は悪く評価されることになる。
【０１３１】
その後、（ステップ．５．３）において、拡張コスト値が妥当な（所定の条件に適合する）指定された上位ｐ個のレプリカを対象に、実際に利用するべき仮結合要素リストの要素、その種類毎に決める。このとき、上位ｐ個のレプリカを残し、他を仮結合要素リストから削除する。
【０１３２】
（ステップ．６）では、前述の仮結合要素リスト上で残ったエントリから結合要素リストの初期版｛Ｒ１１ｏ，…，Ｒ１ｐｏ，Ｒ２１ｏ，…，Ｒ２ｐｏ，．．．，Ｒｎｐｏ｝を作成し、最適化プラン要素リストにも追加する。
【０１３３】
その後、（ステップ．７）では、仮結合要素リストを削除する。
【０１３４】
（ステップ．８）でも、本発明の特徴的な事項を含む。特に（ステップ．８．３）、（ステップ．８．４）、並びに（ステップ．８．７）〜（ステップ．８．９）である。
【０１３５】
（ステップ．８）において、最適化部１０５１は、結合要素リスト内の要素数がレプリカを除き１種類になるまで、配下の処理を繰り返し実施する。
【０１３６】
［（ステップ．８）配下の処理］
（ステップ．８．１）では、従来の方式でも見られるように、最大ブロックサイズｋを指定値、もしくは結合要素リストの要素数で、小さいものに設定する。その後、（ステップ．８．２）では、結合数の初期値を２に指定する。（ステップ．８．３）では、最適化部１０５１の処理系が自分自身をコピーした後、コピーした側の最大ブロックサイズを（ｋ＋１）に書き換える。その後、（ステップ．８．４）では、コピーした処理系を起動する。これは、最大ブロックサイズがｋの場合に中間成果表を生成することになるが、どの分散ストレージサイトに配置するか、を先読みして合理的に決めるために実施する。
【０１３７】
当該中間成果表を配置するには、前述のレイテンシ及び信頼性に関する数値情報を含めて評価するだけではなく、その中間成果表を使って再度結合演算処理を行う場合にコスト値全体が最小化するように取り決める必要がある。このためには、どのレプリカを使ってアクセスされるかを把握する必要がある。
【０１３８】
このためには、実際には、最大ブロックサイズがｋの場合に前述の中間成果表に書き込みを行うが、これを（ｋ＋１）とし、ｋ個の結合でどのレプリカ表を用いるか、を判定の上で、そのレプリカ表が配置される分散ストレージサイト、もしくはその近傍の分散ストレージサイトに中間成果表を配置することで前述の拡張コスト値を小さくする必要がある。
【０１３９】
このためには、最適化部１０５１の処理系自身をコピーして最大ブロックサイズを（ｋ＋１）に変更し並列に評価させることで、評価の前提条件を一致したものに指定でき、本来望ましいものを求めることが可能となる。
【０１４０】
（ステップ．８．５）では、指定結合数≦最大ブロック数ｋ（コピー側は（ｋ＋１））の条件を満足する限り、配下の処理を繰り返して実施する。
【０１４１】
なお、（ステップ．８．５．１）、（ステップ．８．５．２）、（ステップ．８．５．３）、（ステップ．８．５．４）、（ステップ．８．５．５）、（ステップ．８．５．６）、（ステップ．８．５．７）、（ステップ．８．５．８）は、従来の方法でも確認される方式である。
【０１４２】
［（ステップ．８．５）配下の処理］
まず、（ステップ．８．５．１）では、指定結合数分の組合せを構成する全ての場面を、結合要素リストの初期版｛Ｒ１１ｏ，…，Ｒ１ｐｏ，Ｒ２１ｏ，…，Ｒ２ｐｏ，．．．，Ｒｎｐｏ｝から取り出し、仮リストを作成し、追加する。続いて、（ステップ．８．５．２）では、全ての仮リスト要素数分、配下の処理を繰り返して実施する。
【０１４３】
［（ステップ．８．５．２）配下の処理］
まず、（ステップ．８．５．２．１）では、仮リストから１要素を取り出す。続いて、（ステップ．８．５.２．２）では、仮リスト部分１，２が伴に定義できるまで、配下の処理を繰り返して実施する。
【０１４４】
［（ステップ．８．５．２．２）配下の処理］
まず、（ステップ．８．５．２．２．１）では、要素を２つに分割し、要素｛Ｒｋｐｏ｝の組合せ２組を作成し、｛仮リスト部分１｝｛仮リスト部分２｝を作成する。続いて、（ステップ．８．５．２．２．２）では、｛仮リスト部分１｝｛仮リスト部分２｝の組合せで、仮操作リストに追加する。続いて、（ステップ．８．５．２．２．３）では、｛仮リスト部分２｝｛仮リスト部分１｝の組合せで、仮操作リストに追加する。
【０１４５】
［（ステップ．８．５）配下の処理の続き１］
（ステップ．８．５．２）の終了後、（ステップ．８．５）配下の（ステップ．８．５．３）では、最適化プランリストを初期化する。続いて、（ステップ．８．５．４）では、全ての仮操作リスト要素数分、配下の処理を繰り返して実施する。
【０１４６】
［（ステップ．８．５．４）配下の処理］
まず、（ステップ．８．５．４．１）では、仮操作リストから１つ取り出す。続いて、（ステップ．８．５．４．２）では、取り出した右側｛仮リスト部分ｘ（ｘ＝１，２）｝の最適化プランを最適化プラン要素リストから取り出すか、もしくは作成する。続いて、（ステップ．８．５．４．３）では、取り出した左側｛仮リスト部分ｘ（ｘ＝１，２）｝の最適化プランを最適化プラン要素リストから取り出すか、もしくは作成する。続いて、（ステップ．８．５．４．４）では、前述の（ステップ．８．５．４．２）（ステップ．８．５．４．３）の２つの最適化プランでの結合プランを作成し、最適化プランリストに追加する。
【０１４７】
［（ステップ．８．５）配下の処理の続き２］
（ステップ．８．５．４）の終了後、（ステップ．８．５）配下の（ステップ．８．５．５）では、最適化プランリストから最適なものを１つ取り出し、それを最適化プラン要素リストに追加する。続いて、（ステップ．８．５）配下の（ステップ．８．５．６）では、最適化プランリストの最適でないものを、ライブラリとして整理保持する。続いて、（ステップ．８．５）配下の（ステップ．８．５．７）では、仮リスト、仮操作リストをクリアする。続いて、（ステップ．８．５）配下の（ステップ．８．５．８）では、結合数に１を加算（ｉｎｃｒｅｍｅｎｔ）する（結合数←（結合数＋１））。
【０１４８】
［（ステップ．８）配下の処理の続き１］
（ステップ．８．６）では、従来の方式でも見られるように、（ステップ．８．５）で作成された最適化プラン要素リスト内の要素から、貪欲法（欲張り法）のアルゴリズムを用いてコストを計算する評価関数を最小にする結合木の選択を行う。貪欲法（欲張り法）のアルゴリズムは、従来のものと同様である。
【０１４９】
（ステップ．８．７）は、本発明の特徴的な事項である。（ステップ．８．７）では、並行して実施している最適化部１０５１の処理系が最大ブロックサイズｋにてコピーを実施した側（非コピー処理系）か、最大ブロックサイズ（ｋ＋１）にてコピーされた側（コピー処理系）か、を評価する。その結果に応じて、後の処理内容が異なる。
【０１５０】
［コピー処理系の場合］
最適化部１０５１の処理系が最大ブロックサイズ（ｋ＋１）にてコピーされたコピー処理系である場合、（ステップ．８．７．１）では、非コピー処理系からの問い合わせ待ちとなる。その後、（ステップ．８．７．２）では、コピーを実施した非コピー処理系からの問い合わせの際に指定される中間成果表の結合木｛Ｔ１ｏ｝種類を判定する。この場合、左側（外部側）／駆動表か、右側（内部側）／参照表を評価し、ｋ個の結合でどのサイトのどの表と結合演算を行うか、を非コピー処理系に応答する。その後、（ステップ．８．７．３）では、自ら終了する。すなわち、コピー処理系を終了する。
【０１５１】
［非コピー処理系の場合］
最適化部１０５１の処理系が最大ブロックサイズｋにてコピーを実施した側の場合、（ステップ．８．７．４）では、結合木を新たな中間成果表｛Ｔ１ｏ｝に仮置きをする。その後、（ステップ．８．７．５）で、この結果をいずれのサイトに配置するべきかを問い合わせるため、最大ブロックサイズ（ｋ＋１）にてコピーされた最適化部１０５１の処理系に問い合わせる。
【０１５２】
最大ブロックサイズ（ｋ＋１）にてコピーされた最適化部１０５１の処理系は、通常、（ステップ．８．７．３）で自ら終了することを前提とするが、利用後に終了されていない場合を考慮して（ステップ．８．７．５）で、強制終了させることも可能である。
【０１５３】
［（ステップ．８）配下の処理の続き２］
その後、（ステップ．８．８）では、配置評価関数を呼び出し、前述の中間成果表を配置するべきサイトとその索引等の作成方針で最適な上位２案を取り出す。索引等を作成する場合、そのために追加コストが生じることになるが、索引故に検索速度は大きく改善することになる。そのため、「索引等作成」と「索引等を利用した検索」をバランス良く評価する必要がある。
【０１５４】
［配置評価関数］
当該配置評価関数は、以下の手順で実施される。
最初の（ステップ．ｆ）では、最大ブロックサイズ（ｋ＋１）にてコピーされた前述の最適化部１０５１の処理系内で判断された中間成果表の結合木｛Ｔ１ｏ｝種類を確認する。結合木｛Ｔ１ｏ｝種類が左側（外部側）／駆動表になる場合、（ステップ．ｆ．１．１）〜（ステップ．ｆ．１．１２）を連続して実施する。また、結合木｛Ｔ１ｏ｝種類が右側（内部側）／参照表になる場合、（ステップ．ｆ．２．１）〜（ステップ．ｆ．２．１５）を連続して実施する。
【０１５５】
［結合木｛Ｔ１ｏ｝種類が左側（外部側）／駆動表になる場合］
（ステップ．ｆ．１．１）では、（ステップ．８．７．２）での次の結合演算先（ここでは内部側／参照表）を確認する。その後、（ステップ．ｆ．１．２）では、次の結合演算先（内部側／参照表）で利用されるサイト群全てを（レプリカも含めて）取り出して、サイト仮リストに追加する。
【０１５６】
（ステップ．ｆ．１．１）、（ステップ．ｆ．１．２）では、コピーされた前述の最適化部１０５１の処理系内で、どの表とサイト群が次結合演算先（この場合は内部側／参照表）として利用されているかを判定し、それをリストに含める。これに対して（ステップ．ｆ．１．３）〜（ステップ．ｆ．１．７）では、利用されていないサイト群の中で、中間成果表を配置することのできる候補を最大２つまで探索する。
【０１５７】
具体的には、（ステップ．ｆ．１．３）では、利用されないサイト群の一覧を抽出する。ここでは、サイト仮リストに含まれないサイトを取り出し、候補仮リストに追加する。（ステップ．ｆ．１．４）では、探索用の２箇所分の候補エリアを準備し、初期化する。その後、（ステップ．ｆ．１．５）では、候補仮リスト要素分、配下の処理を繰り返し実施する。
【０１５８】
［（ステップ.ｆ.１.５）配下の処理］
（ステップ．ｆ．１．５．１）では、順次、サイト情報を読み出す。（ステップ．ｆ．１．５．２）では、計測統計ＤＢから、当該サイトに関するレイテンシ及び信頼性に関する数値情報を読み出す。また、レイテンシ及び信頼性に関する数値情報を読み出す毎に、配下の処理を実施する。
【０１５９】
［候補エリアで初期化されたものが残っている場合］
（ステップ．ｆ．１．５．２．１）において、最初の２サイトを候補として、前述の探索用の候補エリアにセットする。
【０１６０】
［候補エリアが既にセットされ、サイト仮リストに登録されていない場合］
（ステップ．ｆ．１．５．２．２）において、（ステップ．ｆ．１．５．２）を繰り返して実施した結果、レイテンシ及び信頼性に関する数値情報が、より高評価である場合、当該探索用の候補エリアに記載されているサイトを置き換える（リプレイス）。それ以外は処理しない。
【０１６１】
候補仮リスト内の全てのサイトに対して（ステップ．ｆ．１．５）を実施した結果、新たな候補となる２つのサイトが特定されたならば、（ステップ．ｆ．１．６）では、中間成果表の結合木｛Ｔ１ｏ｝を一時的に配置するサイト候補を意味するサイト仮リストに追加する。その後、（ステップ．ｆ．１．７）では、候補仮リストをクリアする。続けて、（ステップ．ｆ．１．８）では、サイト仮リスト要素分、配下の処理を繰り返し実施して、中間成果表の結合木｛Ｔ１ｏ｝を一時的に配置するサイト候補の各々を具体的に評価する。
【０１６２】
［（ステップ．ｆ．１．８）配下の処理］
（ステップ．ｆ．１．８．１）では、結合木｛Ｔ１ｏ｝の作成件数（作成される行数及び件数）から表作成コストを見積もる。その後、（ステップ．ｆ．１．８．２）では、計測統計ＤＢから、そのサイトに関するレイテンシ及び信頼性に関する数値情報を読み出す。その後、（ステップ．ｆ．１．８．３）では、前述の表作成コストの見積りに対し、（ステップ．ｆ．１．８．２）で得たデータを保持するサイトに関する正規化されたレイテンシに関する数値情報並びに当該信頼性に関する数値情報の逆数を重畳し、全体コストを求める。更に、（ステップ．ｆ．１．８．４）では、全体コストに対して計画番号を付け、候補の一つとして評価リストに追加する。そして、（ステップ．ｆ．１．８．５）では、索引の作成可能性を判定する。索引が作成可能である場合は、配下の処理を実施する。
【０１６３】
［索引が作成可能である場合］
（ステップ．ｆ．１．８．５．１）では、（ステップ．ｆ．１．８．３）で得た全体コストから索引作成コストを見積り、索引作成コストも組み込んだ全体コストを改めて計算する。その後、（ステップ．ｆ．１．８．５．２）では、改めて計算した全体コストに対して計画番号を付け、別候補として評価リストに追加する。
【０１６４】
（ステップ．ｆ．１．８）で中間成果表の結合木｛Ｔ１ｏ｝を一時的に配置するサイト候補全てを評価した後、（ステップ．ｆ．１．９）において、前述の評価リスト内のデータに関して、全体コストでソートし序列化を行う。そして、全体コストが最小のものを第一案として記憶する。
【０１６５】
その後、（ステップ．ｆ．１．８．１０）において、第一案と同類の構成で配置先が異なり、全体コストが次に小さいものを第二案として記憶する。ここで、同類の構成とは、具体的には、索引が作成される場合は索引が存在する構成、索引が作成されない場合は索引が存在しない構成を意味する。
【０１６６】
その後、（ステップ．ｆ．１．８．１１）において、後処理として、サイト仮リスト、評価リストをクリアする。その後、（ステップ．ｆ．１．８．１２）において、前述の第一案、並びに前述の第二案を回答する。
【０１６７】
ここまでが、結合木｛Ｔ１ｏ｝種類が左側（外部側）／駆動表になる場合の処理である。
【０１６８】
［結合木｛Ｔ１ｏ｝種類が右側（内部側）／参照表になる場合］
結合木｛Ｔ１ｏ｝種類が右側（内部側）／参照表になる場合は、結合木｛Ｔ１ｏ｝種類が左側（外部側）／駆動表になる場合と異なり、処理が複雑である。これはハッシュ結合を利用する場合が存在するためである。特に中間生成表である結合木｛Ｔ１ｏ｝をストレージに書き込んだ後、ハッシュが作成されることになる。しかし、ハッシュはメモリ上に作成されるデータ構造であるため、ストレージに書き込むサイトとハッシュを保持するサイトが別サイト及び装置であることも可能である。
【０１６９】
（ステップ．ｆ．２．１）では、（ステップ．８．７．２）での次の結合演算先（ここでは外部側／駆動表）を確認する。その後、（ステップ．ｆ．２．２）では、次の結合演算先（外部側／駆動表）で利用されるサイト群全てを（レプリカも含めて）取り出して、サイト仮リストに追加する。その後、（ステップ．ｆ．２．３）では、利用されないサイト群の一覧を抽出する。ここでは、サイト仮リストに含まれないサイトを取り出し、候補仮リストに追加する。（ステップ．ｆ．２．４）では、探索用の２箇所分の候補エリアを準備し、初期化する。その後、（ステップ．ｆ．２．５）では、候補仮リスト要素分、配下の処理を繰り返し実施する。
【０１７０】
［（ステップ.ｆ．２.５）配下の処理］
（ステップ．ｆ．２．５．１）では、順次、サイト情報を読み出す。（ステップ．ｆ．２．５．２）では、計測統計ＤＢから、当該サイトに関するレイテンシ及び信頼性に関する数値情報を読み出す。また、レイテンシ及び信頼性に関する数値情報を読み出す毎に、配下の処理を実施する。
【０１７１】
［候補エリアで初期化されたものが残っている場合］
（ステップ．ｆ．２．５．２．１）において、最初の２サイトを候補として、前述の探索用の候補エリアにセットする。
【０１７２】
［候補エリアが既にセットされ、サイト仮リストに登録されていない場合］
（ステップ．ｆ．２．５．２．２）において、（ステップ．ｆ．２．５．２）を繰り返して実施した結果、レイテンシ及び信頼性に関する数値情報が、より高評価である場合、当該探索用の候補エリアに記載されているサイトを置き換える（リプレイス）。それ以外は処理しない。
【０１７３】
候補仮リスト内の全てのサイトに対して（ステップ．ｆ．２．５）を実施した結果、新たな候補となる２つのサイトが特定されたならば、（ステップ．ｆ．２．６）では、中間成果表の結合木｛Ｔ１ｏ｝を一時的に配置するサイト候補を意味するサイト仮リストに追加する。その後、（ステップ．ｆ．２．７）では、候補仮リストをクリアする。続けて、（ステップ．ｆ．２．８）では、サイト仮リスト要素分、配下の処理を繰り返し実施して、中間成果表の結合木｛Ｔ１ｏ｝を一時的に配置するサイト候補の各々を具体的に評価する。
【０１７４】
［（ステップ．ｆ．２．８）配下の処理］
（ステップ．ｆ．２．８．１）では、結合木｛Ｔ１ｏ｝の作成件数（作成される行数及び件数）から表作成コストを見積もる。その後、（ステップ．ｆ．２．８．２）では、計測統計ＤＢから、そのサイトに関するレイテンシ及び信頼性に関する数値情報を読み出す。その後、（ステップ．ｆ．２．８．３）では、前述の表作成コストの見積りに対し、（ステップ．ｆ．２．８．２）で得たデータを保持するサイトに関する正規化されたレイテンシに関する数値情報並びに当該信頼性に関する数値情報の逆数を重畳し、表部分全体コストを求める。更に、（ステップ．ｆ．２．８．４）では、表部分全体コストに対して計画番号を付け、候補の一つとして表部分評価リストに追加する。
【０１７５】
（ステップ．ｆ．２．１）〜（ステップ．ｆ．２．８．４）は、（ステップ．ｆ．２．１．１）を除き、前述の（ステップ．ｆ．１．２）〜前述の（ステップ．ｆ．１．８．４）と等価な処理であり、表部分全体コストが算出される。これに対して（ステップ．ｆ．２．９）〜（ステップ．ｆ．２．１５）は、結合木｛Ｔ１ｏ｝種類が右側（内部側）／参照表になる場合の専用の処理内容である。
【０１７６】
（ステップ．ｆ．２．９）では、結合木｛Ｔ１ｏ｝種類が右側（内部側）／参照表になる場合、全体の処理量を抑制させる目的で前述の表部分全体コストが小さいものの上位３つに限定する。ここでは、表部分評価リストから、表部分全体コストが小さいものの上位３つを選択し、他を削除する。
【０１７７】
続けて、（ステップ．ｆ．２．１０）では、サイト仮リスト要素分、配下の処理を繰り返し実施する。
【０１７８】
［（ステップ．ｆ．２．１０）配下の処理］
（ステップ．ｆ．２．１０．１）では、メモリ上に構成される前述のハッシュの作成コストを見積もる。（ステップ．ｆ．２．１０．２）では、特に（ステップ．ｆ．２．８．２）で得たサイトに関する正規化されたレイテンシに関する数値情報並びに前述の信頼性に関する数値情報の逆数を重畳し、参照コストを求める。更に、（ステップ．ｆ．２．１０．３）では、この参照コストに対して計画番号を付け、候補の一つとして参照部分評価リストに追加する。
【０１７９】
また、ハッシュ結合を利用しない場合も考えられる。その場合、索引が作成される可能性もある。そこで、（ステップ．ｆ．２．１０．４）では、前述の索引の作成コストを見積もる。（ステップ．ｆ．２．１０．５）では、特に（ステップ．ｆ．２．８．２）で得たサイトに関する正規化されたレイテンシに関する数値情報並びに前述の信頼性に関する数値情報の逆数を重畳し、参照コストを求める。更に、（ステップ．ｆ．２．１０．６）では、この全体コストに対して計画番号を付け、候補の一つとして参照部分評価リストに追加する。
【０１８０】
続いて、（ステップ．ｆ．２．１１）では、前述の表部分全体コストと参照コストの組合せを行うことで、前述の結合木｛Ｔ１ｏ｝を含む中間成果表と、前述のハッシュが異なるサイトに作成される場合を評価する。ここでは、（ステップ．ｆ．２．１１）において、表部分評価リスト要素分、配下の処理を繰り返し実施する。
【０１８１】
［（ステップ．ｆ．２．１１）配下の処理］
（ステップ．ｆ．２．１１．１）では、表部分評価リストから、計画番号順に１件取り出す。（ステップ．ｆ．２．１１．２）では、表部分全体コストと参照コストを、それぞれ定数重み付けをした上で総和を取り、全体コストを算出する。その後、（ステップ．ｆ．２．１１．２）では、算出した全体コストに対して計画番号を付け、評価リストに追加する。
【０１８２】
（ステップ．ｆ．２．１２）では、前述の評価リスト内のデータに関して、全体コストでソートし序列化を行う。そして、全体コストが最小のものを第一案として記憶する。
【０１８３】
その後、（ステップ．ｆ．２．１３）において、第一案と同類の構成で配置先が異なり、全体コストが次に小さいものを第二案として記憶する。ここで、同類の構成とは具体的には、索引が作成される場合は索引が存在する構成、索引が作成されない場合は索引が存在しない構成を意味する。
【０１８４】
その後、（ステップ．ｆ．２．１４）において、後処理として、サイト仮リスト、表部分評価リスト、参照部分評価リスト、評価リストをクリアする。その後、（ステップ．ｆ．２．１５）において、前述の第一案、並びに前述の第二案を回答する。
【０１８５】
以上の手順に基づき、当該配置評価関数は処理を終了する。その後、当該配置評価関数の結果に基づき、（ステップ．８．９）で１箇所もしくは投機的に２箇所に中間生成結果を配置予約する。
【０１８６】
（ステップ．８．１０）以降の処理は、従来の方式でも見られる処理である。（ステップ．８．１０）では、配置した中間成果表に相当する結合木｛Ｔｋ１ｏ，Ｔｋ２ｏ｝の要素を結合要素リストの現版に追加する。これを受けて、（ステップ．８．１１）では、当該結合木｛Ｔｋ１ｏ，Ｔｋ２ｏ｝を構成する結合要素を結合要素リストの現版から削除する。
【０１８７】
（ステップ．８）の処理が最適化の中核部分の処理であり、この部分を抜けた場合、最適化部１０５１の処理系は（ステップ．９）に移行することになる。（ステップ．９）では、結合要素リストの現版｛Ｔｍｏ｝から、残った最適化を実施し、最適化プラン追加する。その後、最適化部１０５１の処理系は（ステップ．１０）で最適化プランを１つ選択する。
【０１８８】
その後、最適化部１０５１の処理系は、（ステップ．１１）でレプリカを含めた結合要素リストの初期版｛Ｒ１１ｏ，…，Ｒ１ｐｏ，Ｒ２１ｏ，…，Ｒ２ｐｏ，．．．，Ｒｎｐｏ｝、並びに現版｛Ｔｍｏ｝を使い、最適化プランを表現し直す。その後、（ステップ．１２において最適化部１０５１の処理系は、算出した最適化プランから、その一部の実行プラン記述ｓ１２４、ｓ１０５を前述の処理実行部−１：１０５３から前述の処理実行部−Ｎ：１０５４に渡して処理を終了する。
【０１８９】
図５Ａ、図５Ｂの初期段階２０００は、（ステップ．１）から（ステップ．７）に相当する。また、初期段階２０００の後の繰り返し２００１は、（ステップ．８）に相当する。ここでは、既にアクセス方法を最適化した関係｛Ｒ１ｏ，Ｒ２ｏ，．．．，Ｒｎｏ｝を想定する。
【０１９０】
図５Ａ、図５Ｂの“処理系、並びにコピー処理系の起動”２００２は、（ステップ．８．３）、（ステップ．８．４）に相当する。最適化部１０５１の処理系でコピー処理系を起動する側は、図５Ａ、図５Ｂでは処理シーケンス２００３で表現される。これに対して、コピー処理系として起動される側は、処理シーケンス２００４で表現される。特に処理内容の中核部分である（ステップ．８．５）は、処理シーケンス２００５、並びに処理シーケンス２００６で表現されることになる。
【０１９１】
このため、処理シーケンス２００３においては、最大ブロックサイズｋを２と設定した場合、その２段階目で中間成果表を分散ストレージに書き込むため、結合処理を中断するのに対して、処理シーケンス２００４では最大ブロックサイズが（ｋ＋１）の３段階目まで、処理が進むことになる。
【０１９２】
当初、処理シーケンス２００３、並びに処理シーケンス２００４は、全く同じ処理で進むことになる。第１段階の処理ではコスト計算を最小化するため、関係｛Ｒ１ｏ｝、並びに関係｛Ｒ２ｏ｝を始めとする２つの関係について結合演算が実施される。この結果、複数の結合結果案が作成されるが、第１段階の処理結果は、処理シーケンス２００３では結合結果２００７に相当し、処理シーケンス２００４では結合結果２０１５に相当する。
【０１９３】
第２段階の処理では、第１段階の結合結果に対して、更に、結合演算を実施する。例えば関係｛Ｒ１ｏ｝、並びに関係｛Ｒ２ｏ｝間で結合演算をした結果に対して、関係｛Ｒ４ｏ｝と結合演算させる処理等が相当する。この結果、複数の結合結果案が作成されるが、第２段階の処理結果は、処理シーケンス２００３では結合結果２００８に相当し、処理シーケンス２００４では結合結果２０１６に相当する。
【０１９４】
その後、処理シーケンス２００３では、中間生成表に相当する結合木｛Ｔ１ｏ｝への置き換え候補２００９が複数生成される。更に、貪欲法（欲張り法）のアルゴリズムにより当該置き換え候補２００９から最適な中間成果表である結合木｛Ｔ１ｏ｝の選択結果２０１０が作成されることになる。一連の処理内容は、（ステップ．８．５）、（ステップ．８．６）に相当する。
【０１９５】
これに対して処理シーケンス２００４では、３段階目まで処理が進むため、第２段階の結合結果２０１６に対して更に、結合演算を実施する。第１段階の結合演算に対して、更に、結合演算を実施する。例えば関係｛Ｒ１ｏ｝、並びに関係｛Ｒ２ｏ｝間で結合演算をし、更に、関係｛Ｒ４ｏ｝の結果に対して、関係｛Ｒ３ｏ｝２０２２、並びに関係｛Ｒ５ｏ｝２０２１の結合結果２０２０を追加結合させる処理等が相当する。この結果、複数の結合結果案が作成されるが、ここでは結合結果案２０１７が相当する。
【０１９６】
その後、処理２０１８を実施し、最大ブロックサイズが（ｋ＋１）の場合にｋ個の結合でどのレプリカ表を用いるか、を特定する。これは、（ステップ８．７．２）の前半部分に相当する。
【０１９７】
更に、最適化部１０５１の処理系でコピー処理系を起動する側からの問い合わせを待ち合わせ、問い合わせ２０２３の結果、処理２０１９を実施し、応答２０２４を実施した後、終了する。これは、（ステップ８．７．２）の後半部分、並びに（ステップ．８．７．３）に相当する。
【０１９８】
ここで、前述の問い合わせ２０２３には、中間成果表である結合木｛Ｔ１ｏ｝が指定される。これに対して前述の応答２０２４には、当該結合木｛Ｔ１ｏ｝が左側（外部側）／駆動表になるか、右側（内部側）／参照表になるかが指定されると伴に、次の結合演算でどのレプリカ表を用いるか、その全てのサイト群と表群が指定されることになる。
【０１９９】
これに対して最適化部１０５１の処理系でコピー処理系を起動する側の処理シーケンス２００３では、処理２０１２で第（ｋ＋１）段階の想定結合先の問い合わせ２０２３を行う。その後、該当する応答２０２４を受信する。これは、（ステップ８．７．５）により実施される。
【０２００】
その後、処理２０１３において中間成果表の配置を行う分散ストレージサイト等の特定を行う。これは、（ステップ８．８）の配置評価関数内で評価を行った後、（ステップ８．９）を通して実施される。当該配置評価関数は、前述の［配置評価関数］のアルゴリズムに従う。
【０２０１】
更に、処理２０１４で後処理を行う。具体的には、（ステップ．８．１０）、（ステップ．８．１１）に相当する。
【０２０２】
以上のように、本発明クエリ最適化方式は、データベース管理システム内部のクエリを最適化する手法であり、特に大規模に仮想化されたストレージを利用する環境において、クエリの最適化の途上で発生する中間成果をより合理的に配置するための手法である。特にクエリでは関係代数に於ける制限演算と結合演算の任意個数の複合演算を前提とする。
【０２０３】
このクエリ最適化方式では、データを保持するサイトに関するレイテンシ及び信頼性に関する数値情報を取り出す。次に、当該レイテンシに関する数値情報並びに当該信頼性に関する数値情報をクエリのコスト値に重畳し拡張コスト値を求める。次に、拡張コスト値で序列化した場合に上位で妥当な指定値を持つサイトを選定する。次に、最適化の結果発生する中間成果の配置先サイトを選定するため、アルゴリズム中のパラメータを一部変更した処理系自身のコピーを作成することで先読みを実施する。次に、当該先読みの結果、中間成果を１つ以上のサイトに配置するステップを含むことを特徴とするクエリの中間成果の配置方式を評価する。
【０２０４】
従来のクエリの最適化手法では、最適化の結果発生するクエリの中間成果を合理的な判断の下で、どの分散ストレージサイトに配置するべきかが考慮されておらず、結果としてクエリの最適化が実施段階で為されていない課題が存在し、この結果、データベースアクセスクライアントの利用者が取り決めた合意サービス水準を満足し得ない課題も発生し得る。
【０２０５】
しかし、本発明では、データベース管理システムのクエリの最適化手法として、データを保持するサイトに関するレイテンシ及び信頼性に関する数値情報を取り出す（ステップ、当該レイテンシに関する数値情報並びに当該信頼性に関する数値情報をクエリのコスト値に重畳し拡張コスト値を求めるステップ、拡張コスト値で序列化した場合に上位で妥当な指定値を持つサイトを選定するステップ、最適化の結果発生する中間成果の配置先サイトを選定するため、アルゴリズム中のパラメータを一部変更した処理系自身のコピーを作成することで先読みを実施するステップ、当該先読みの結果、中間成果を１つ以上のサイトに配置するステップを含むことを特徴とするクエリの中間成果の配置方式を評価するクエリ最適化方式を提供するため、配置の選定を合理的に実施できるようになり、従来課題を解決できる。
【０２０６】
本発明は、データベース管理システムの要素技術が、単一のシステム内の機能モジュールからネットワーク全体に広く、緩やかに連携する環境に分散し、大規模に展開された結果、従来のデータベース管理システム環境を前提としているクエリの最適化手法も影響を受け、ネットワーク全体に分散した環境を前提とした手法に進化する際の一形態と考えることができる。広域なネットワーク全体に渡り扱われることから、関連する技術領域は幾つかに跨ることに成る。
【０２０７】
以上、本発明の実施形態を詳述してきたが、実際には、上記の実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の変更があっても本発明に含まれる。
【０２０８】
＜備考＞
なお、本出願は、日本出願番号２０１０−０６８８２２に基づく優先権を主張するものであり、日本出願番号２０１０−０６８８２２における開示内容は引用により本出願に組み込まれる。
【図１】
2011118425.tif 000003
【図２Ａ】
2011118425.tif 000004
【図２Ｂ】
2011118425.tif 000005
【図３Ａ】
2011118425.tif 000006
【図３Ｂ】
2011118425.tif 000007
【図４Ａ】
2011118425.tif 000008
【図４Ｂ】
2011118425.tif 000009
【図５Ａ】
2011118425.tif 000010
【図５Ｂ】
2011118425.tif 000011
【国際調査報告】
2011118425.tif 000012
2011118425.tif 000013
2011118425.tif 000014
2011118425.tif 000015