(57)【特許請求の範囲】
【請求項１】
複数のデータ格納手段に分割されて格納されている所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付けるクエリセット受付手段と、
前記対象データ群のメタデータに基づいて、前記対象データ群を再分割配置せずに前記クエリセットを実行した場合の処理コストである第１の処理コストと、前記対象データ群を所定の方法で再分割配置した後に前記クエリセットを実行した場合の処理コストである第２の処理コストとを推定する処理コスト推定手段と、
前記処理コスト推定手段による推定結果に基づいて、前記クエリセットを実行する前に、前記対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断する再分割配置判断手段とを備えた
ことを特徴とする制御装置。
【請求項２】
対象データ群は、１つ以上の列の各々に割り当てられる値を含む１つ以上の行データからなる表データであり、
前記対象データ群は、前記表データにおける１つ以上の任意の列の集合である列集合をパーティションキーとして、各行データに含まれる前記パーティションキーの値に基づいて、１つ以上の行データを各々有する複数のデータブロックに分割されており、
前記対象データ群のメタデータは、前記列の値に関する統計量を含み、
処理コスト推定手段は、第２の処理コストとして、クエリセットに含まれるクエリの述語に出現する列集合をパーティションキーに用いて前記対象データ群を再分割配置したときの前記クエリセットの処理コストを、前記メタデータに基づいて推定し、
再分割配置判断手段は、前記第２の処理コストのいずれかが第１の処理コストよりも小さい場合に、最も小さい第２の処理コストが得られた列集合をパーティションキーに用いて前記対象データ群を再分割配置すると判断する
請求項１に記載の制御装置。
【請求項３】
受け付けたクエリセットに含まれるクエリの述語に所定の頻度以上で出現する列集合を抽出する列集合抽出手段を備え、
処理コスト推定手段は、列集合抽出手段によって抽出された列集合の各々をパーティションキーの候補として、各候補について、前記クエリセットのうち当該候補に含まれる列を使用する述語を含むクエリの実行にかかる第１の処理コストおよび第２の処理コストを推定する
請求項２に記載の制御装置。
【請求項４】
処理コスト推定手段は、パーティションキーの一候補に対して、複数の分割配置方法に対応した複数の第２の処理コストを推定し、
再分割配置判断手段は、前記第２の処理コストのいずれかが第１の処理コストよりも小さい場合に、最も小さい第２の処理コストが得られたパーティションキーの候補と分割配置方法とを用いて前記対象データ群を再分割配置すると判断する
請求項２または請求項３に記載の制御装置。
【請求項５】
複数の分割配置方法には、パーティションキーとされた列集合の値が同じである行データが同一データブロックに多く含まれるように対象データ群を分割する第１の分割方法と、全データブロックに渡りパーティションキーとされた列集合の値で行データがソートされるように対象データ群を分割する第２の分割方法とが含まれる
請求項４に記載の制御装置。
【請求項６】
処理コスト推定手段は、クエリの実行アルゴリズムとして所定の最適化アルゴリズムを適用して、第１の処理コストおよび第２の処理コストを推定する
請求項１から請求項５のうちのいずれか１項に記載の制御装置。
【請求項７】
処理コスト推定手段は、さらに、各データ格納手段を制御する各計算機のディスクバンド幅または前記計算機間を接続するネットワークのバンド幅に基づいて、第１の処理コストおよび第２の処理コストを推定する
請求項１から請求項６のうちのいずれか１項に記載の制御装置。
【請求項８】
所定のデータ群を複数のデータブロックに分割して格納する複数のデータ格納手段と、
前記所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付けるクエリセット受付手段と、
前記対象データ群のメタデータを記憶するメタデータ格納手段と、
前記メタデータに基づいて、前記対象データ群を再分割配置せずに前記クエリセットを実行した場合の処理コストである第１の処理コストと、前記対象データ群を再分割配置した後で前記クエリセットを実行した場合の処理コストである第２の処理コストとを推定する処理コスト推定手段と、
前記処理コスト推定手段による推定結果に基づいて、前記クエリセットを実行する前に、前記対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断する再分割配置判断手段と、
前記再分割配置判断手段によって前記対象データ群を再分割配置すると判断された場合に、前記クエリセットを実行する前に、前記対象データ群の再分割配置を実行する再分割配置実行手段とを備えた
ことを特徴とする分散データベースシステム。
【請求項９】
制御装置が、複数のデータ格納手段に分割されて格納されている所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付け、
前記制御装置が、前記クエリセットを実行する前に、前記対象データ群のメタデータに基づいて、前記対象データ群を再分割配置せずに前記クエリセットを実行した場合の処理コストと、前記対象データ群を所定の方法で再分割配置した後に前記クエリセットを実行した場合の処理コストとを推定し、
前記制御装置が、前記クエリセットを実行する前に、前記推定結果に基づいて、前記クエリセットを実行する前に、前記対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断する
ことを特徴とする分割配置制御方法。
【請求項１０】
コンピュータに、
複数のデータ格納手段に分割されて格納されている所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付ける処理、
前記対象データ群のメタデータに基づいて、前記対象データ群を再分割配置せずに前記クエリセットを実行した場合の処理コストと、前記対象データ群を所定の方法で再分割配置した後に前記クエリセットを実行した場合の処理コストとを推定する処理、および
前記クエリセットを実行する前に、前記推定結果に基づいて、前記対象データ群を再分割配置するか否か、再分割配置する場合にはどのような方法で再分割配置するかを判断する処理
を実行させるための分割配置制御用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散データベースシステム、データの分割配置（partition）を制御する制御装置、分割配置制御方法および分割配置制御用プログラムに関する。
【背景技術】
【０００２】
機械学習等を用いて大量のデータを分析する分析処理の前処理として、分析対象のデータ群に対して抽出、集約、整形などを行い、分析処理が処理しやすい形（例えば、行列、計画行列、属性データ付の任意のデータ型等）に整える作業を行う場合がある。このような作業は、一般に属性生成処理（feature engineering）と呼ばれる。
【０００３】
属性生成処理はデータベースシステムを利用して行われることが多い。データベースシステムを利用する場合、例えば、ユーザまたは属性生成処理を行う手段は、分析対象とされるデータ群を元データとしてデータベースシステムの記憶領域に格納させた上で、該データベースシステムに対してＳＱＬといった一般にクエリと呼ばれる問い合わせ言語を発行して、所望のデータ操作を行う。元データが膨大である場合には、分散データベースシステムが利用される。
【０００４】
分散データベースシステムは、データ群を細かいデータブロックに分割して複数のデータノードに格納する、いわゆる分割配置（partition）を行って、分割配置したデータブロックの各々に対して並列にクエリに基づくデータ操作を行うシステムである。分散データベースシステムに実装されるデータ操作用のオープンソースソフトウェアとして、Ｈｉｖｅ、Ｉｍｐａｌａ、Ｐｒｅｓｔｏなどが広く知られている。
【０００５】
属性生成処理では、分析処理が処理しやすいデータの形を得るために、一度に大量のクエリが発行される。そのため、属性生成処理は、分析タスクの中でも時間のかかりやすい処理といえる。分析タスク全体の効率化を図るためには、属性生成処理の効率化が求められている。
【０００６】
分散データベースシステムにおけるデータ操作の効率化に関する技術として、分割配置したデータブロックごとに、メタ情報を付与する技術がある。
【０００７】
Ｈｉｖｅがサポートするデータフォーマットの１つであるＯＲＣＦｉｌｅを例に用いて、該技術の一例を挙げる。ＯＲＣｆｉｌｅでは、Ｈｉｖｅが扱うレコード群（元データ）を複数のレコード（行データ）からなるグループに分割したものをデータブロックとして保持する。すなわち、ＯＲＣｆｉｌｅにおいて、各データブロックには複数のレコードが格納されている。そして、各データブロックは、当該データブロック内での、各列に対するレコードの最大値、最小値、和、カウント値等の統計情報をメタデータとして保持する。以下、このような分割配置されたデータブロックに対して付与される、データブロック内のデータの統計量を示すメタデータを、ブロック統計情報と呼ぶ場合がある。
【０００８】
ブロック統計情報は、ある種のデータ操作を行うときに効率性を発揮する。例えば、次のようなクエリを考える。
【０００９】
クエリ例１：
select * from Table1 where attribute01 <= 100;
【００１０】
クエリ例１は、“Table1”というテーブルから、“attribute01”という列（属性）名の列の値が１００以下であるレコードをすべて取得するというデータ操作を行わせるためのクエリである。なお、テーブルは、データベース表やリレーションモデルオブジェクトとも呼ばれる。
【００１１】
Ｈｉｖｅを利用した分散データベースシステムは、このようなクエリを受け取ると、まずクエリ内の述語“attribute01 <= 100”で示される条件を基に、各データブロックのブロック統計情報を参照して、列“attribute01”の最小値を確認する。ここで、述語（predicate）は、述語論理における述語であり、クエリ内においては、例えば、ｗｈｅｒｅ句などに指定される論理式の部分に相当する。クエリに用いられる述語のうち分割配置の仕方によって処理コストに変化が生じるものとしては、選択述語と結合述語とがある。上記のクエリ例１に用いられている述語は、選択述語である。
【００１２】
今、仮に、あるデータブロックのブロック統計情報が示す“attribute01”列の最小値が１１０であるとする。その場合、当該データブロックの中には、“attribute01”列の値が１１０以上のレコードしか存在しない。したがって、そのようなデータブロックは、クエリ例１の処理で読み込む必要がない。
【００１３】
Ｈｉｖｅを利用した分散データベースシステムでは、データフォーマットにＯＲＣＦｉｌｅを用いている場合、まず、発行されたクエリ内の述語を基に、各データブロックのブロック統計情報を参照する。そして、該分散データベースシステムは、述語にマッチするレコード、より具体的には述語が示す論理式を満たすレコードがデータブロック内に存在しないことがわかると、当該データブロックの読み込みを回避する。このようにして、記憶領域に対するＩ／Ｏ（Input/Output）の発生を抑え、より高速なデータ操作を実現している。
【００１４】
分散データベースシステムにおけるデータの分割配置に関する技術として、例えば、非特許文献１に記載された技術がある。非特許文献１には、データベースシステムが、追加データを格納する際に、既に格納されているデータに対して過去に発行されたクエリの履歴に基づいて、追加データをどのように分割配置するかを決定するデータ分割配置方法が記載されている。具体的には、データベースシステムが、クエリの履歴から、過去発行されたクエリに頻出する選択述語の集合を抽出して、抽出された選択述語集合に含まれるいずれか１つ以上の選択述語にマッチしない行を同一グループに選り分ける。このような分割配置を行うことで、ある１つ以上の選択述語にマッチにしないグループに相当するデータブロックを、該当する選択述語のいずれかを含むクエリが発行されたときに読み飛ばせるようにし、記憶領域に対する不要なＩ／Ｏの削減によるデータ操作の効率化を図る。
【００１５】
また、特許文献１には、分散型のデータベース装置が、指定されたタイミング毎に、アクセス履歴から算出した複数の分割テーブルそれぞれに対するアクセス頻度およびレコードのヒット率に基づいて、複数のテーブル領域のそれぞれに格納されるべき分割テーブルの配置を変更することが記載されている。
【００１６】
また、特許文献２には、クエリが発行された段階で、そのクエリを処理するトランザクションが、現在のブロック内のソート状態における次元の順序と問い合わせ結果の出力順序とが一致していない場合に、ブロック内をソートすることが記載されている。
【００１７】
また、特許文献３には、クエリを、選択演算や結合演算などの関係代数を接点とするタスクで構成された処理ツリーに変換し、変換した処理ツリーから、関係代数を他の関係代数の結果に依存しないで実施できるタスク群を取り出して、データベースへのアクセス領域ごとにグループ分けすることが記載されている。また、特許文献３には、グループ分けされたタスクに対してマルチプロセッション・プロセッシングを行う際に、処理コストの小さい順にタスクの処理を行うことや、共通のブロックへのアクセスを一度に行うことなどが記載されている。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００９−２８８９７９号公報
【特許文献２】特開平１１−００３２６０号公報
【特許文献３】特開２００８−１６５６２２号公報
【非特許文献】
【００１９】
【非特許文献１】L. Sun, M. J. Franklin, S. Krishnan, and R. S. Xin, "Fine-grained partitioning for aggressive data skipping.", SIGMOD 2014, June 2014, p.1115-1126.
【発明の概要】
【発明が解決しようとする課題】
【００２０】
ブロック統計情報により不要なＩ／Ｏを抑制する効果を得るためには、データブロックが適切に分割配置されていなければならない。すなわち、分散データベースシステムにおけるデータ操作の効率化には、元のデータが不要なＩ／Ｏを抑制できるようなデータブロックに分割されていることが重要である。
【００２１】
例えば、クエリ例１のような“attribute01”列に関する述語を含むクエリが頻繁に発行されることが事前に分かる場合、 “Table1”の各レコードを“attribute01”列の値に基づいて分割配置することにより、効果的に記憶領域に対する不要なＩ／Ｏを抑制できる。
【００２２】
しかし、分析者が試行錯誤を行いながら分析処理を行うような分析タスクでは、属性生成処理で生成したい属性もその都度異なってくる。このため、属性生成処理で発行されるクエリに使用される列の傾向を事前につかむことは難しい。
【００２３】
例えば、特許文献１に記載された方法のように、過去のアクセス履歴からであれば、アクセス頻度が高いにも関わらずヒット率が低い分割テーブルを、さらに２以上の分割テーブルに分割することは可能である。しかし、新規に発行されたクエリセットがアクセス履歴に追従しない場合には、そのようなアクセス頻度やヒット率に基づく方法では、データ操作の効率化は図れない。
【００２４】
すなわち、アクセス履歴により示されるアクセス頻度やレコードのヒット率は、似た傾向のクエリが発行されるデータベースシステムにおいて定期的に行われるデータの分割配置の見直しにおけるデータの分割時の基準として適していたとしても、新規のクエリ集合に対して、その実行前にデータの再分割配置の是非を問うための判定基準としては適さない。
【００２５】
なお、非特許文献１に記載された方法のように、クエリ内の述語の頻度に基づいてパーティションキーを設定する方法であれば、新規のクエリ集合に対しても適用できるかもしれない。
【００２６】
しかし、非特許文献１に記載された方法には、次のような問題がある。第一に、非特許文献１に記載された方法は、クエリ集合における述語の頻度のみを考慮しており、述語そのものがデータ操作に与える処理コストを考慮していない。このため、処理コストが小さく、問題にならないような述語が頻繁にクエリ履歴内に現れた場合に、真に処理コストのボトルネックとなっている述語が無視される可能性がある。真に処理コストのボトルネッックとなっている述語が無視された場合、効率化効果が見込めない場合がある。
【００２７】
第二に、非特許文献１に記載された方法は、選択述語のみを考慮しており、結合述語を無視している。結合述語は、複数のテーブル間の結合（join）演算を要する述語である。選択述語は、複数のテーブル間の結合演算を要せず、１つのテーブルから条件にマッチする行を抽出する選択（selection）演算を要する述語である。
【００２８】
クエリ例２：
select * from T,R where T.name=R.name ∧ T.age>30;
【００２９】
例えば、上記のクエリ例２には、“T.name = R.name”という結合述語と、“T.age > 30”という選択述語の２つの述語の論理積が用いられている。なお、論理積であるので、“T.name=R.name ∧ T.age>30”をまとめて１つの結合述語とみなしてもよい。
【００３０】
結合演算には計算量の異なるアルゴリズムがいくつか存在し、例えば、上記のクエリ例２の場合、要する演算は選択演算と結合演算の組み合わせとなるが、事前にデータが適切にソートされて分割配置されている方が、結合演算で効率のいいアルゴリズムを選択できる。
【００３１】
しかし、非特許文献１に記載された方法は、結合述語については何ら開示されておらず、選択述語のみを対象にしているため、結合述語が用いられた場合に適切な分割配置を行うことができない。一般に、選択演算よりも結合演算の処理コストの方が大きくなる傾向があるため、選択述語のみを対象にしている非特許文献１に記載された方法では、処理効率化の大きな機会損失が生じている。
【００３２】
第三に、非特許文献１に記載された方法は、新しく追加されたデータに対して、初めて分割配置を行うことを想定しており、既にデータベース内に存在するデータに対して、適切な基準を与えてデータの分割配置をやり直すことを想定していない。属性生成処理では、一度に大量のクエリが発行されることが多い。そのような大量のクエリを一連の処理要求であるクエリセットとして見た場合、当該クエリセットの実行には多くの時間が掛かる。このため、大量のクエリを含むクエリセットを受け付けた場合には、その実行前に当該クエリセットに対応した適切な基準でデータの分割配置をやり直したほうが、総実行時間の短縮が可能な場合がある。しかし、データの分割配置をやり直すことで余計に時間が掛かる場合も当然あるため、データの分割配置を行うかどうかを判断する仕組みが必要だが、非特許文献１にはそのような仕組みについては何ら考慮されていない。一般に、データの分割配置をやり直す処理、すなわちデータが複数のデータノードに分割されて配置されている状態でそれとは異なる分割方法を用いてデータを分割して配置しなおす処理は、データの再分割配置（re-partition）と呼ばれる。
【００３３】
なお、特許文献２に記載された方法は、ブロックごとに当該ブロック内のソート状態を示す情報を保持しておくことにより、各ブロックに対して同じソート処理が繰り返されるのを防ごうというものであって、データ全体の分割配置の最適化については何ら考慮されていない。
【００３４】
また、特許文献３に記載された方法は、クエリ内の演算処理に対応するタスクを、アクセス先のデータ領域ごとにグループ化して処理の効率化を図ろうというものであって、データの分割配置の最適化については何ら考慮されていない。
【００３５】
そこで、本発明は、属性生成処理のような複数のクエリや述語の演算に時間のかかるクエリの発行を伴うワークロードの総処理時間を縮小できる制御装置、分散データベースシステム、分割配置制御方法および分散配置制御用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３６】
本発明による制御装置は、複数のデータ格納手段に分割されて格納されている所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付けるクエリセット受付手段と、対象データ群のメタデータに基づいて、対象データ群を再分割配置せずにクエリセットを実行した場合の処理コストである第１の処理コストと、対象データ群を所定の方法で再分割配置した後にクエリセットを実行した場合の処理コストである第２の処理コストとを推定する処理コスト推定手段と、処理コスト推定手段による推定結果に基づいて、クエリセットを実行する前に、対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断する再分割配置判断手段とを備えたことを特徴とする。
【００３７】
また、本発明による分散データベースシステムは、所定のデータ群を複数のデータブロックに分割して格納する複数のデータ格納手段と、所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付けるクエリセット受付手段と、対象データ群のメタデータを記憶するメタデータ格納手段と、メタデータに基づいて、対象データ群を再分割配置せずにクエリセットを実行した場合の処理コストである第１の処理コストと、対象データ群を再分割配置した後でクエリセットを実行した場合の処理コストである第２の処理コストとを推定する処理コスト推定手段と、処理コスト推定手段による推定結果に基づいて、クエリセットを実行する前に、対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断する再分割配置判断手段と、再分割配置判断手段によって対象データ群を再分割配置すると判断された場合に、クエリセットを実行する前に、対象データ群の再分割配置を実行する再分割配置実行手段とを備えたことを特徴とする。
【００３８】
また、本発明によるデータ分割配置制御方法は、制御装置が、複数のデータ格納手段に分割されて格納されている所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付け、制御装置が、クエリセットを実行する前に、対象データ群のメタデータに基づいて、対象データ群を再分割配置せずにクエリセットを実行した場合の処理コストと、対象データ群を所定の方法で再分割配置した後にクエリセットを実行した場合の処理コストとを推定し、制御装置が、クエリセットを実行する前に、推定結果に基づいて、クエリセットを実行する前に、対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断することを特徴とする。
【００３９】
また、本発明による分割配置制御用プログラムは、コンピュータに、複数のデータ格納手段に分割されて格納されている所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付ける処理、対象データ群のメタデータに基づいて、対象データ群を再分割配置せずにクエリセットを実行した場合の処理コストと、対象データ群を所定の方法で再分割配置した後にクエリセットを実行した場合の処理コストとを推定する処理、およびクエリセットを実行する前に、推定結果に基づいて、対象データ群を再分割配置するか否か、再分割配置する場合にはどのような方法で再分割配置するかを判断する処理を実行させることを特徴とする。
【発明の効果】
【００４０】
本発明によれば、属性生成処理のようなクエリの発行を伴うワークロードの総処理時間を縮小できる。
【図面の簡単な説明】
【００４１】
【図１】本発明の実施形態にかかる分散データベースシステムの構成例を示すブロック図である。
【図２】処理コスト推定手段１２の構成例を示すブロック図である。
【図３】本発明の実施形態にかかる分散データベースシステムの動作例を示すフローチャートである。
【図４】処理コスト推定手段１２および再分割配置判断手段１３の動作例を示すフローチャートである。
【図５】クエリセットの例を示す説明図である。
【図６】述語の抽出結果の例を示す説明図である。
【図７】列集合の抽出結果の例を示す説明図である。
【図８】クエリのサブセットＱｉ’の例を示す説明図である。
【図９】対象データ群の分割配置例を示す説明図である。
【図１０】対象データ群の他の分割配置例を示す説明図である。
【図１１】対象データ群の他の分割配置例を示す説明図である。
【図１２】クエリ実行計画の例を示す説明図である。
【図１３】メタデータの一例を示す説明図である。
【図１４】本発明の概要を示すブロック図である。
【発明を実施するための形態】
【００４２】
以下、本発明の実施形態を図面を参照して説明する。図１は、本発明の実施形態にかかる分散データベースシステムの構成例を示すブロック図である。
【００４３】
図１に示す分散データベースシステムは、クエリセット受付手段１１と、処理コスト推定手段１２と、再分割配置判断手段１３と、再分割配置実行手段１４と、クエリ実行手段１５と、複数のデータ格納手段２１と、メタデータ格納手段２２とを備える。図１において、各コンポーネントは、ネットワークやバス等を介して互いに通信可能に接続されている。
【００４４】
データ格納手段２１の各々は、クエリの処理対象とされるデータ群を分割したデータブロックを格納する。以下、クエリの処理対象とされるデータ群を、単に対象データ群という。
【００４５】
本実施形態において対象データ群は、１つ以上の列の各々に割り当てられる値を含む１つ以上の行データからなる表データである。本発明では、表データを、テーブルの実体という意味で用いている。また、対象データ群は、表データにおける１つ以上の任意の列の集合である列集合をパーティションキーとして、１つ以上の行データを各々有する複数のデータブロックに分割されて、データ格納手段２１に格納される。対象データ群は、より具体的には、各行データに含まれるパーティションキーに指定された列集合の値に基づいて、複数のデータブロックに分割されてデータ格納手段２１に格納される。なお、パーティションキーは、表データを分割する際の基準とされるキーである。また、分散データベースシステムは、各行データがどのデータブロックに所属するかを示す情報を保持している。
【００４６】
メタデータ格納手段２２は、対象データ群のメタデータを格納する。対象データ群のメタデータは、後述する処理コスト推定手段１２がクエリセットの処理コストを算出できる情報を含んでいればよい。対象データ群のメタデータは、例えば、対象データ群のデータサイズ（行数、バイトサイズ等）、各データブロックのデータサイズ（行数、バイトサイズ等）といった基本的な情報だけでなく、データの各種カテゴリ（列や行やそれらの集合等）に関する統計量、特に、対象データ群の列ごとの値のカーディナリティ（cardinality）、選択率（selectivity）、ヒストグラムといった対象データ群の表データにおける列の値に関する統計量を含んでいてもよい。
【００４７】
本実施形態において、クエリセットの処理コストの計算方法は特に限定されないが、対象データ群のメタデータは、対象データ群とされる表データにおける列の値に関する統計量であって、列中の占有度合いや選択度合い（選択されやすさ又は選択されにくさ）に関する統計量を含むことが好ましい。
【００４８】
クエリセット受付手段１１は、外部から対象データ群に対するクエリセットを受け付ける。クエリセットは、１つ以上のクエリを含んでいればよい。クエリセットの発行元は、例えば、一連の処理として実行させたい１つ以上のクエリをクエリセットとして入力すればよい。
【００４９】
処理コスト推定手段１２は、メタデータ格納手段２２に記憶されている対象データ群のメタデータに基づいて、対象データ群を再分割配置せずにクエリセットを実行した場合の処理コストである第１の処理コストと、対象データ群を所定の方法で再分割配置した後にクエリセットを実行した場合の処理コストである第２の処理コストとを推定（算出）する。処理コスト推定手段１２は、例えば、再分割配置判断手段１３からの要求に応じて、第１の処理コストおよび第２の処理コストを推定してもよい。
【００５０】
本実施形態において、処理コストは、指定された処理を完了するまでにかかる時間である処理時間に関連する指標であって、処理コストを比較することによって処理時間の大小比較ができる指標であれば特に問わない。
【００５１】
また、処理コスト推定手段１２は、対象データ群のメタデータだけでなく、さらに各データ格納手段２１を制御する計算機のディスクバンド幅や当該計算機間を接続するネットワークバンド幅といった分散データベースシステムの構成要素の処理性能に関する情報に基づいて、第１の処理コストおよび第２の処理コストを推定してもよい。なお、ここでは、バンド幅を、単位時間あたりのデータ転送容量という意味で用いている。
【００５２】
図２は、処理コスト推定手段１２の構成例を示すブロック図である。図２に示すように、処理コスト推定手段１２は、列集合抽出手段１２１と、第１の処理コスト算出手段１２２と、分割配置方法格納手段１２３と、第２の処理コスト算出手段１２４とを含んでいてもよい。
【００５３】
列集合抽出手段１２１は、クエリセットに含まれるクエリの述語（より具体的には、選択述語と結合述語）に出現する列集合を抽出する。列集合抽出手段１２１により抽出された列集合は、再分割配置におけるパーティションキーの候補とされるとともに、処理コストの算出対象とするクエリを限定するために用いられる。列集合抽出手段１２１は、処理コストの計算時間をさらに短縮するため、クエリセットに含まれるクエリの選択述語または結合述語に出現する列集合のうち所定の頻度以上で出現する列集合を抽出してもよい。
【００５４】
第１の処理コスト算出手段１２２は、第１の処理コストを算出する。
【００５５】
分割配置方法格納手段１２３は、第２の処理コストを算出する際の分割配置方法を特定する情報を格納する。分割配置方法格納手段１２３は、分割配置方法を特定する情報を複数格納してもよい。分割配置方法の例としては、パーティションキーとされた列集合の値が同じである行データが同一データブロックに多く含まれるように対象データ群を分割する分割方法や、全データブロックに渡りパーティションキーとされた列集合の値で行データがソートされるように対象データ群を分割する分割方法などが挙げられる。同じ分割方法であっても異なる分割数を指定する場合などは異なる分割配置方法として扱ってもよい。分割配置方法格納手段１２３に格納される情報は、再分割配置実行手段が対応可能な分割配置方法を特定する情報であれば、特に問わない。なお、再分割配置実行手段１４が対応可能な分割配置方法が１つしかないなどで第２の処理コストを算出する際の分割配置方法が固定される場合には、分割配置方法格納手段１２３は省略されてもよい。以下、分割配置方法格納手段１２３に格納されている情報によって特定される分割配置方法を、単に、指定の分割配置方法という場合がある。
【００５６】
第２の処理コスト算出手段１２４は、第２の処理コストを算出する。第２の処理コスト算出手段１２４は、列集合抽出手段１２１によって抽出された列集合の各々をパーティションキーの候補として、候補ごとに、分割配置方法格納手段１２３に格納されている情報によって特定される分割配置方法で対象データ群を再分割配置した場合の第２の処理コストを算出する。このとき、第２の処理コスト算出手段１２４は、当該候補の列集合を使用しているクエリのみを対象にして、第２の処理コストを算出してもよい。なお、その場合、第１の処理コスト算出手段１２２も、上記の候補に対して、当該候補の列集合を使用しているクエリのみを対象にして、第１の処理コストを算出する。
【００５７】
第１の処理コスト算出手段１２２および第２の処理コスト算出手段１２４は、処理コストを算出する際に、クエリの実行アルゴリズムとして所定の最適化アルゴリズムが適用されると仮定して、処理コストを算出してもよい。所定の最適化アルゴリズムは、例えば、結合演算を含むクエリのオペレーションの順序を最適化した実行アルゴリズムであってもよい。
【００５８】
図示省略しているが、分散データベースシステムは、後述するクエリ実行手段１５がどのようなアルゴリズムに対応しているかを示す情報を格納するアルゴリズム格納手段や、受け付けたクエリセットを格納するクエリセット格納手段を有していてもよい。
【００５９】
なお、第１の処理コスト算出手段１２２および第２の処理コスト算出手段１２４は、これら処理コストの算出をクエリセットの実行前に行う。
【００６０】
再分割配置判断手段１３は、処理コスト推定手段１２によって推定された第１の処理コストおよび第２の処理コストに基づいて、クエリセットの実行前に、対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断する。
【００６１】
再分割配置判断手段１３は、例えば、第２の処理コストのいずれかが第１の処理コストよりも小さかった場合に、最も小さい第２の処理コストが算出されたパーティションキーの候補と分割配置方法とを用いて対象データ群を再分割配置すると判断してもよい。
【００６２】
再分割配置実行手段１４は、再分割配置判断手段１３によって対象データ群を再分割配置すると判断された場合に、クエリセットを実行する前に、対象データ群の再分割配置を実行する。
【００６３】
再分割配置実行手段１４は、例えば、再分割配置判断手段１３からの要求に応じて、指定されたパーティションキーおよび分割配置方法を用いて対象データ群の再分割配置を実行してもよい。再分割配置実行手段１４は、より具体的には、表データにおけるパーティションキーとして指定された列集合に関する値の集合を基に、表データに含まれる各行データを複数のデータブロックのいずれかに割り振ってもよい。このとき、再分割配置実行手段１４は、例えば、各行データに対して当該行データがどのデータブロックに所属するかを示すパーティション情報を生成してもよい。そして、再分割配置実行手段１４は、生成したパーティション情報を基に、行データの移動を指示するクエリを発行するなどして、各行データを、当該行データの所属先とされたデータブロックを格納するデータ格納手段２１に移動させる。また、再分割配置実行手段１４は、再分割配置を実行した後、新たな分割配置における各データブロック内のデータの統計量を示すメタデータ（ブロック統計情報）を生成して、メタデータ格納手段２２に格納してもよい。
【００６４】
クエリ実行手段１５は、指定されたクエリを実行する。
【００６５】
本実施形態において、クエリセット受付手段１１は、例えば、マウスやキーボード、ネットワークカードといったデータの入出力を行うデータ入出力装置と、記憶手段に記憶されているプログラムに従って動作するＣＰＵ等の情報処理装置とによって実現される。また、処理コスト推定手段１２、再分割配置判断手段１３、再分割配置実行手段１４およびクエリ実行手段１５は、例えば、記憶手段に記憶されているプログラムに従って動作するＣＰＵ等の情報処理装置とによって実現される。また、データ格納手段２１、メタデータ格納手段２２およびその他の格納手段（上記のアルゴリズム情報格納手段やクエリセット格納手段等）は、例えば、記憶装置により実現される。
【００６６】
次に、本実施形態の動作を説明する。図３は、本実施形態の分散データベースシステムの動作例を示すフローチャートである。図３に示す例では、まずクエリセット受付手段１１が、外部からクエリセットを受け付ける（ステップＳ１１）。
【００６７】
次に、処理コスト推定手段１２が、受け付けたクエリセットの第１の処理コストと第２の処理コストとを算出する（ステップＳ１２）。なお、処理コストの算出方法については後述する。
【００６８】
次に、再分割配置判断手段１３が、算出された第１の処理コストと第２の処理コストとに基づいて、対象データ群を再分割配置するか否か、および再分割配置する場合にはいずれの方法で再分割配置するかを判断する（ステップＳ１３）。
【００６９】
ステップＳ１３では、再分割配置判断手段１３は、算出された第１の処理コストと第２の処理コストとを比較して、第２の処理コストのいずれかが第１の処理コストよりも小さい場合に（ステップＳ１３のＹｅｓ）、最も小さい第２の処理コストが算出された方法（パーティションキーの候補と分割配置方法）を用いて再分割配置すると判断する。また、再分割配置判断手段１３は、算出された第１の処理コストと第２の処理コストとを比較して、第２の処理コストのいずれも第１の処理コストよりも小さくなければ（ステップＳ１３のＮｏ）、再分割配置しないと判断する（ステップＳ１５に進む）。
【００７０】
再分割配置判断手段１３が再分割配置すると判断した場合（ステップＳ１３のＹｅｓ）、再分割配置実行手段１４は、指定された方法で再分割配置を実行する（ステップＳ１４）。
【００７１】
最後に、クエリ実行手段１５は、受け付けたクエリセットを実行して、実行結果を出力する（ステップＳ１５、ステップＳ１６）。
【００７２】
一方、再分割配置判断手段１３が再分割配置しないと判断した場合（ステップＳ１３のＮｏ）には、現在の分割配置のまま、クエリ実行手段１５が、受け付けたクエリセットを実行して、実行結果を出力する（ステップＳ１５、ステップＳ１６）。
【００７３】
次に、具体例を用いて本実施形態の動作を説明する。図４に示すフローチャートは、処理コスト推定手段１２および再分割配置判断手段１３の動作である上記のステップＳ１２〜ステップＳ１４のより詳細な処理フローの一例である。
【００７４】
図４に示す例では、まず処理コスト推定手段１２の第１の処理コスト算出手段１２２が、クエリセット受付手段１１が受け付けたクエリセット（以下、クエリセットＱという）のクエリｑｊ∈Ｑの各々について、再分割配置を行わない場合に当該クエリｑｊを実行するのにかかる処理コストである第１のクエリ実行コストとして、ｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏｊを算出する（ステップＳ１０１）。
【００７５】
図５は、クエリセットＱの例を示す説明図である。例えば、クエリセット受付手段１１は、図５に示すような５つのクエリ（ｑ１〜ｑ５）を含むクエリセットＱを受け付けたとする。そのような場合、第１の処理コスト算出手段１２２は、ｑｊ＝ｑ１〜ｑ４の各々について、ｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏｊを算出する。本例では、ｊ＝１〜４の整数である。
【００７６】
次に、処理コスト推定手段１２の列集合抽出手段１２１は、クエリセットＱのクエリｑｊから、選択述語または結合述語のいずれかにおいて所定の頻度以上で出現する列集合Ｃｉを全て抽出し、列集合Ｃｉの集合｛Ｃ１，Ｃ２，．．．，ＣＩ｝を得る（ステップＳ１０２）。なお、Ｉは抽出された列集合Ｃｉの数（種類数）である。なお、列集合抽出手段１２１は、抽出された列集合Ｃｉの数が所定数に満たなければ、最も多く出現した列集合Ｃｉから順に所定数の列集合Ｃｉを抽出してもよい。また、列集合抽出手段１２１は、抽出された列集合Ｃｉの数がゼロである場合には、現在の分割配置におけるパーティションキーそのままに異なる分割配置方法を用いた場合の第２の処理コストを第２の処理コスト算出手段１２４に算出させてもよい。
【００７７】
以下、列集合Ｃｉの単純な抽出法を例に挙げる。なお、抽出法は、クエリセットＱと頻度の閾値θを与えられて、θ以上の頻度でクエリセットＱ内のクエリの選択述語または結合述語のいずれかに現れる列集合の全てを列挙するものであれば、方式やアルゴリズムは問わない。
【００７８】
単純な抽出法では、列集合抽出手段１２１は、まずクエリセットＱを走査し、ｗｈｅｒｅ句から述語を抜き出す。そして、列集合抽出手段１２１は、抜き出した述語に用いられている列の組合せを全て抽出して、抽出した列の組合せが異なるごとに一つの列集合として生成する。図５に示すクエリセットＱによる例を示す。まず、列集合抽出手段１２１は、クエリセットＱ内の各クエリ（ｑ１〜ｑ４）を走査し、ｗｈｅｒｅ句から述語を抜き出す。このとき、列集合抽出手段１２１は、クエリｑ３のように論理和（∨）で連結されている述語があった場合は、該述語を分割して別々の述語として扱う。
【００７９】
図６は、述語の抽出結果の例を示す説明図である。図６には、図５に示すクエリセットＱから抽出される述語が一例として示されている。上記の方法によれば、図５に示すクエリセットＱから、５つの述語（ｐ１〜ｐ５）が抽出される。
【００８０】
続いて、列集合抽出手段１２１は、抽出した述語の各々に現れる列の組合せからなる列集合を抽出するとともに、抽出した列集合が、抽出した全述語内に現れる頻度を計算する。このとき、列集合抽出手段１２１は、１つの述語内に同じテーブルに存在する複数の列が共起している場合には、それら複数の列で作られるあらゆる組合せを列集合として抽出して、抽出した列集合の各々に対して頻度を計算する。例えば、述語ｐ１には、“T.name”と“R.name”と“T.age”という３つの列が現れている。“T.name”と“T.age”とは同じテーブルに存在する列である。これら同じテーブルに存在する複数の列で作られるあらゆる列の組合せとしては｛T.name｝，｛T.age｝，｛T.name, T.age｝の３通りが考えられ、これら３通りの組合せの各々が１つの列集合として抽出される。なお、述語ｐ１からは、さらにテーブルの異なる列｛R.name｝が追加されて、｛T.name｝，｛T.age｝，｛T.name, T.age｝，｛R.name｝の計４つの列集合が抽出される。なお、これら列集合の全ては述語ｐ１に出現するため、これら４つの列集合の各々に対して出現述語数が＋１される。列集合抽出手段１２１は、抽出した述語ｐ１〜ｐ５について同様の処理を行う。なお、次の述語から抽出した列集合が、既に抽出された列集合と完全一致した場合には、新たな列集合とせずに、完全一致した列集合に対して出現述語数を＋１すればよい。
【００８１】
図７は、列集合の抽出結果の例を示す説明図である。図７には、図６に示す述語集合から抽出される列集合およびその頻度が示されている。図７に示すように、本例では、５通りの列集合Ｃｉ＝Ｃ１〜Ｃ５が抽出されて、抽出された列集合Ｃｉの各々について頻度（出現述語数）が算出される。今、θ＝３とすると、列集合抽出手段１２１は、クエリセットＱに頻出する列集合として、列集合Ｃ１とＣ２とを抽出する。なお、列集合抽出手段１２１は、再分割配置判断手段１３が再分割配置する際の方法としてパーティションキーのみを指定する場合には、現在の分割配置におけるパーティションキーと同じ列集合を抽出対象から除外してもよい。
【００８２】
なお、図７に示す例では、頻度を、対象の列集合が現れる述語の数すなわち出現述語数と定義しているが、頻度の定義はこれに限られない。例えば、抽出された述語の総数に対する出現述語数の割合を頻度としてもよいし、述語の数ではなく対象の列集合が述語に現れているクエリの数を頻度としてもよいし、その他任意に定義された指標を用いてもよい。
【００８３】
次に、列集合抽出手段１２１は、抽出された列集合Ｃｉの各々について、クエリセットＱに含まれるクエリｑｊの中から、当該列集合Ｃｉをカバーしているクエリｑｊを抽出して、抽出したクエリｑｊからなるサブセットＱｉ’を得る（ステップＳ１０３）。ここで、列集合Ｃｉをカバーしているクエリは、具体的には、選択述語または結合述語を含むクエリであって、当該列集合Ｃｉの要素となっている列が当該１つのクエリ内に全て現れているクエリである。以下、サブセットＱｉ’に含まれるクエリｑｊの各々をクエリｑｊ’と記す場合がある。ここで、ｊ’はクエリセットＱに含まれるクエリｑｊの識別子であるｊのうち指定された列集合Ｃｉをカバーするとの条件を満たすものを表わしている。
【００８４】
図８は、クエリのサブセットＱｉ’の例を示す説明図である。図８には、図５に示すクエリセットＱから抽出された列集合Ｃｉである列集合Ｃ１およびＣ２について、クエリセットＱから抽出されたクエリのサブセットＱ１’およびＱ２’の例が示されている。
【００８５】
例えば、列集合抽出手段１２１は、頻出する列集合として列集合Ｃ１とＣ２とが抽出されると、再びクエリセットＱを走査して、列集合Ｃ１または列集合Ｃ２がｗｈｅｒｅ句の述語に現れているクエリを特定し、特定したクエリの識別子ｊを、該当する列集合の識別子ｉと対応づければよい。
【００８６】
本例では、列集合抽出手段１２１は、列集合Ｃ１＝｛T.age｝が全て現れているクエリのサブセットＱ１’として、Ｑ１’＝｛ｑ１，ｑ２，ｑ３｝を得る。また、列集合抽出手段１２１は、列集合Ｃ２＝｛T.name｝が全て現れているクエリのサブセットＱ２’として、Ｑ２’＝｛ｑ１，ｑ２，ｑ５｝を得る。
【００８７】
次に、処理コスト推定手段１２の第２の処理コスト算出手段１２４は、メタデータ格納手段２２に格納されている対象データ群のメタデータと、分割配置方法格納手段１２３に格納されている情報に基づいて、ステップＳ１０２で抽出された列集合をパーティションキーとして再分割配置した場合の第２の処理コストを算出する（ステップＳ１０４）。
【００８８】
ステップＳ１０４では、第２の処理コスト算出手段１２４は、抽出された列集合Ｃｉをそれぞれパーティションキーとした場合の再分割配置の実行にかかる処理コストである分割配置コストとして、ｐａｒｔｉｔｉｏｎ＿ｃｏｓｔｉを算出するとともに、再分割配置後の状態においてクエリｑｊ’∈Ｑｉ’の各々の実行にかかる処理コストである第２のクエリ実行コストとして、ｑｕｅｒｙ＿ｃｏｓｔ＿ｐａｒｔｉｊ’を算出する。
【００８９】
本例では、１つの列集合Ｃｉに対して、ｐａｒｔｉｔｉｏｎ＿ｃｏｓｔｉと、クエリｑｊ’∈Ｑｉ’の全てのｊ’についてのｑｕｅｒｙ＿ｃｏｓｔ＿ｐａｒｔｉｊ’とを足したものが第２の処理コストとなる。また、クエリｑｊ∈Ｑのうちｊ＝ｊ’となる全てのｊについてのｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏｊを足したものが、当該列集合Ｃｉの第２の処理コストと比較される第１の処理コストとなる。
【００９０】
第１の処理コストおよび第２の処理コストが算出されると、再分割配置判断手段１３は、これらを比較して、再分割配置するか否か、および再分割配置する場合には再分割配置時に用いるパーティションキーを決定する（ステップＳ１０５〜ステップＳ１１２）。
【００９１】
本例では、再分割配置判断手段１３は、再分割配置することで、しないときよりも総処理コストが小さくなる列集合Ｃｉがあるかどうかを以下の条件式（１）が真となるｃｏｓｔ＿ｃｕｔｉが存在するかどうかで判断する。なお、条件式（１）におけるｃｏｓｔ＿ｃｕｔｉは、指定の列集合Ｃｉでの再分割配置によるコスト削減量の見積もりに相当する。
【００９２】
【数１】
0006398632.tif 000002
【００９３】
図４に示す例では、再分割配置判断手段１３は、まず列集合Ｃｉの識別子ｉを初期化するとともに、条件式（１）が真となったＣｉを格納するバッファＢを初期化する（ステップＳ１０５）。ステップＳ１０５では、ｉ＝１とし、またＢ＝Φとする。ここで、Φは空集合を表す記号である。なお、本例では、わかりやすいよう識別子ｉの値を１基準としているが、識別子の形式は特に限定されない。
【００９４】
次に、再分割配置判断手段１３は、識別子ｉが示す列集合Ｃｉについて、上記の条件式（１）を判定する（ステップＳ１０６）。再分割配置判断手段１３は、具体的には、上記の条件式（１）に従い、ｃｏｓｔ＿ｃｕｔｉを算出して、算出されたｃｏｓｔ＿ｃｕｔｉが０以上であるか否かを判定する。条件式（１）が真であれば（ステップＳ１０６のＹｅｓ）、バッファＢに、ｃｏｓｔ＿ｃｕｔｉの算出に用いた列集合Ｃｉまたはその識別子ｉを、算出したｃｏｓｔ＿ｃｕｔｉの値と一緒に格納する（ステップＳ１０７）。一方、偽であれば（ステップＳ１０６のＮｏ）、そのままステップＳ１０８に進む。
【００９５】
ステップＳ１０８では、ｉがインクリメントされる。次いで、再分割配置判断手段１３は、ステップＳ１０９で、ｉが列集合Ｃｉの最大数であるＩを超えたか否か、すなわちステップＳ１０２で抽出された全ての列集合ＣｉについてステップＳ１０６〜ステップＳ１０７の処理を完了したか否かを判断する。
【００９６】
再分割配置判断手段１３は、全ての列集合ＣｉについてステップＳ１０６〜ステップＳ１０７の処理を完了すると（ステップＳ１０９のＹｅｓ）、バッファＢが空でないかを判定する（ステップＳ１１０）。ステップＳ１１０の判定式が真、すなわちバッファＢが空でなければ、再分割配置すると判断して、ステップＳ１１１に進む。一方、ステップＳ１１０の判定式が偽、すなわちバッファＢが空であれば、再分割配置しないと判断する（ステップＳ１１２）。再分割配置判断手段１３は、例えば、再分割配置しないと判断した場合、クエリ実行手段１５にクエリセットＱを渡し、クエリセットＱを実行する命令を発行してもよい。
【００９７】
ステップＳ１１１では、再分割配置判断手段１３は、再分割配置すると判断した場合、バッファＢを参照してｃｏｓｔ＿ｃｕｔｉが最大値をとる列集合Ｃｉを選択することにより、選択した列集合Ｃｉをパーティションキーに用いて再分割配置することを決定する。
【００９８】
再分割配置判断手段１３は、例えば、再分割配置実行手段１４にパーティションキーとする列集合の情報とともに再分割配置を実行する命令を発行してもよい。
【００９９】
なお、図４に示す例は、指定の分割配置方法が１つの場合の例であるが、指定の分割配置方法は複数であってもよい。そのような場合には、ステップＳ１０４で、第２の処理コスト算出手段１２４が、列集合Ｃｉと分割配置方法Ｍｈの組ごとに、当該列集合Ｃｉをパーティションキーとし、かつ分割配置方法Ｍｈを用いた場合の分割配置コストであるｐａｒｔｉｔｉｏｎ＿ｃｏｓｔｉｈと、そのような方法を用いた再分割配置後の状態におけるクエリｑｊ’∈Ｑｉ’の各々についての第２のクエリ実行コストであるｑｕｅｒｙ＿ｃｏｓｔ＿ｐａｒｔｉｈｊ’とを算出すればよい。
【０１００】
その場合、再分割配置判断手段１３は、再分割配置することで、しないときよりも総処理コストが小さくなる列集合Ｃｉと分割配置方法Ｍｈの組があるかどうかを以下の条件式（２）が真となるｃｏｓｔ＿ｃｕｔｉｈが存在するかどうかで判断すればよい。条件式（１）におけるｃｏｓｔ＿ｃｕｔｉｈは、指定の列集合Ｃｉおよび分割配置方法Ｍｈでの再分割配置によるコスト削減量の見積もりに相当する。
【０１０１】
【数２】
0006398632.tif 000003
【０１０２】
そして、再分割配置判断手段１３は、条件式（２）が真となるｃｏｓｔ＿ｃｕｔｉｈが存在した場合には、ｃｏｓｔ＿ｃｕｔｉｈが最大値をとる列集合Ｃｉと分割配置方法Ｍｈの組を選択することにより、選択した列集合Ｃｉをパーティションキーに用い、かつ選択した分割配置方法Ｍｈを用いて再分割配置することを決定する。
【０１０３】
なお、第２の処理コスト算出手段１２４は、上記の方法以外にも、例えば、予め所定の分割方法で固定して第２のクエリ実行コストを算出し、再分割配置判断手段１３が、コスト削減量に基づいて、再分割配置するか否かを決定するとともに、再分割配置する場合には、算出された第２のクエリ実行コストの中から高コストとなった述語の演算の種類およびクエリ内におけるそれら演算の出現頻度とに基づいて、パーティションキーと分割配置方法とを決定してもよい。
【０１０４】
例えば、再分割配置判断手段１３は、クエリセット内のクエリにある列集合に対して一致条件（＝や≠）で選択演算を行う際に高コストとなるクエリが、他の演算を行う際に高コストとなるクエリと比べて多いとき、パーティションキーとして当該列集合と、列値が同じ多くの行データを同一ブロックに配置する分割法とを選択してもよい。また、例えば、再分割配置判断手段１３は、クエリセット内のクエリにある列集合に対して範囲条件（＞や＜）で選択演算を行う際に高コストとなるクエリが、他の演算を行う際に高コストとなるクエリと比べて多いとき、パーティションキーとして当該列集合と、全ブロックに渡り列値で全行データがソートされるような分割方法とを選択してもよい。また、例えば、再分割配置判断手段１３は、クエリセット内のクエリにある列集合に対して結合演算を行う高コストとなるクエリが、他の演算を行う際に高コストとなるクエリと比べて多いとき、パーティションキーとして当該列集合と、全ブロックに渡り列値で全行データがソートされるような分割方法とを選択してもよい。
【０１０５】
また、上記の例では、列集合抽出手段１２１が、パーティションキーの候補とされる列集合を抽出する処理（ステップＳ１０２）で、クエリセット内の述語（選択述語または結合述語）への出現頻度が所定の頻度以上であることを要件の１つとしたが、クエリセット内の述語への出現頻度を見ずに、クエリセット内の選択述語または結合述語に出現している列集合全てを抽出することも可能である。そのような場合には、θ＝０とすればよい。
【０１０６】
ただし、列集合の総数が多い場合は計算時間が非常に大きくなるため、適切な閾値が設定されるのが好ましい。ただし、出現頻度の閾値を高くしすぎると、コストの大きな低頻度の列集合を見落とす可能性があることに注意が必要である。
【０１０７】
本実施形態では、クエリセットから所定の頻度以上の述語を抽出してパーティションキーの候補を得るのではなく、クエリセットから所定の頻度以上の列集合を抽出してパーティションキーの候補を得ている。このため、コストの大きな低頻度の列集合を見落とす可能性は、述語の頻度に基づく方法よりは低くなると考えられる。一般に、列と述語とでは、列のほうが粒度（granularity）の粗い概念になるため、あるクエリ集合においてある列を含む述語の頻度が極端に低くても、列の頻度は比較的大きくなる傾向がある。また、あるクエリ集合において述語に用いられる列集合の種類数は述語の種類数より小さくなる場合が多い。このため、見落とされる列集合の数は見落とされる述語の数より小さいことが期待できる。
【０１０８】
次に、処理コストの算出方法について具体例を用いて説明する。本例は、分割配置方法として、対象データ群全体をパーティションキーで指定された列集合の値でソートした後に指定の数のブロックに等分割して配置する方法（ソート分割法）を採用したときの処理コストの算出方法の例である。本例でも、図５に示すクエリセットＱを例に用いる。
【０１０９】
図９は、対象データ群の分割配置例を示す説明図である。なお、図９には、対象データ群のうちテーブル“T”に属する行データが２つのデータブロックに分割配置される例が示されている。なお、テーブル“T”は、データ属性に対応する列として、“name”列、“age”列、“sex”列の３つの列を有している。
【０１１０】
今、第１のデータブロックＴＢ１には、列“name”の値がそれぞれ“suzuki”，“yamada”，“aida”である３つの行データが含まれている。また、第２のデータブロックＴＢ２には、列“name”の値が“kuroda”，“hirata”，“satou”である３つの行データが含まれている。また、メタデータ格納手段２２には、各データブロックのブロック統計情報として、当該データブロック内における各列の最小値“min”と最大値“max”が少なくとも格納されている。図９に示す例では、テーブル“T”は、例えば行データが登録された順番のまま２つのデータブロック（ＴＢ１，ＴＢ２）に等分割されて配置されている。
【０１１１】
また、図１０および図１１は、対象データ群の他の分割配置例を示す説明図である。図１０には、パーティションキーとして｛T.age｝を用い、かつソート分割法を用いてテーブル“T”を２つのデータブロック（ＴＢ１，ＴＢ２）に分割配置した例が示されている。また、図１１には、パーティションキーとして｛T.sex, T.name｝を用い、かつソート分割法を用いてテーブル“T”を２つのデータブロック（ＴＢ１，ＴＢ２）に分割配置した例が示されている。
【０１１２】
なお、分割配置を行う際の分割方法は、ソート分割法だけではない。例えば、パーティションキーとして指定された列集合の値からハッシュ値を生成し、同値のハッシュ値を持つブロックに行データを割り当てる方法（ハッシュ分割法）なども一般的な方法である。分割配置アルゴリズムごとに分割配置コスト（ｐａｒｔｉｔｉｏｎ_ｃｏｓｔ）は異なる。例えば、ソート分割法では典型的なソートアルゴリズムを用いる場合、表データの行数Ｎに対して、Ｏ（ＮｌｏｇＮ）＋Ｏ（Ｎ）の分割配置コストがかかるが、ハッシュ分割法では、Ｏ（Ｎ）の分割配置コストとなる。
【０１１３】
次に、クエリ実行コストの算出例を示す。各クエリのコスト計算は、データベース技術分野における、コストに基づいたクエリ最適化を行うことと等価である。一般に、コストに基づいたクエリ最適化では、与えられたクエリについて考えられる全てのクエリ実行計画を列挙する。
【０１１４】
図１２に、図５に示されるクエリｑ１について考えられるクエリ実行計画の例として、３種のクエリ実行計画木を示す。各クエリ実行計画木は、葉ノードにテーブルを持つ。また、各クエリ実行計画木の中間ノードは、対象クエリのオペレーション（選択、結合、射影）に対応している。クエリ実行計画木では、左側の葉ノードから順番に処理が実行され、ルートノードにおいて結果が算出されることを意味する。図中のσ記号はオペレーションが選択演算であることを表している。また、リボン状の記号は、オペレーションが結合演算であることを表している。また、各オペレーション記号の添え字はそれぞれ選択条件、結合条件を表している。
【０１１５】
第１の処理コスト算出手段１２２および第２の処理コスト算出手段１２４は、このようなクエリ実行計画木を基に、各クエリ実行計画を実行する際のクエリ実行コストを計算して、最も処理コストの小さいクエリ実行計画のクエリ実行コストを、当該クエリのクエリ実行コストに採用してもよい。
【０１１６】
各クエリのクエリ実行コストは、メタデータ格納手段２２に格納されている列ごとの値の選択率やヒストグラム等のメタデータから算出できる。
【０１１７】
例えば、クエリセットＱにおいて頻出な列集合Ｃｉとして、列集合Ｃ１とＣ２とが与えられたとする。なお、列集合Ｃ１＝｛T.age｝をカバーするクエリｑｉｊ’はｑ１，ｑ２，ｑ３である。
【０１１８】
今、第２の処理コスト算出手段１２４が、列集合Ｃ１をパーティションキーに用いて再分割配置後の状態におけるクエリｑ１の第２のクエリ実行コストであるｑｕｅｒｙ＿ｃｏｓｔ＿ｐａｒｔ１１を算出することを考える。図１２に示す例では第３の計画が最も小さなクエリ実行コストとなる。なぜなら結合演算と選択演算が混在する場合、先に選択演算を行うほうが効率的であるため、第１の計画より第２の計画および第３の計画のほうが低コストとなる。
【０１１９】
また、本例の場合、テーブル“T”は列集合Ｃ１＝｛T.age｝をパーティションキーとしてソート分割法で再分割配置されている。すなわち、図１０に示す状態にある。すると、選択演算“T.age>30”に対して、事前にブロック統計情報を参照することにより、第１のデータブロックへの不要な読み込みを阻止できる。したがって、第１の計画より第３の計画の方が処理時間が短くなる。
【０１２０】
本例では、第３の計画が選ばれ、第３の計画による第２のクエリ実行コストがｑｕｅｒｙ＿ｃｏｓｔ＿ｐａｒｔ１１として使用される。クエリｑ２，ｑ３についても同様に、ｑｕｅｒｙ＿ｃｏｓｔ＿ｐａｒｔ１２，ｑｕｅｒｙ＿ｃｏｓｔ＿ｐａｒｔ１３が求められる。
【０１２１】
なお、再分割配置を行わない場合のクエリ実行コストの算出方法も基本的には同様である。すなわち、第１の処理コスト算出手段１２２は、対象クエリｑｊのクエリ実行計画木を基に、現在の再部活配置において最も処理コストの小さいクエリ実行計画のクエリ実行コストを、対象クエリｑｊの第１のクエリ実行コストであるｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏｊに採用する。
【０１２２】
ただし、第１の処理コスト算出手段１２２は、各クエリ実行計画を実行する際のクエリ実行コストを計算する際、現在の分割配置の状態におけるクエリ実行コストを計算する。本例の場合、第１の処理コスト算出手段１２２は、テーブル“T”が図１０に示す状態にあるとして、クエリ実行計画木のクエリ実行コストを計算する。なお、図１０に示す状態は、テーブル“T”が｛T.age｝でソートされずに分割された例である。このため、例えばクエリｑ１に対しては、図１２に示した計画のうちの第１の計画および第２の計画の２種類が考えられるクエリ実行計画となる。したがって、第２の計画が最も効率的であるとして選択されて、現在の分割配置における第２の計画のクエリ実行コストがｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏ１となる。第１の処理コスト算出手段１２２は、他のクエリｑｊについても同様に、ｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏｊを計算する。このようにして、列集合Ｃ１，列集合Ｃ２に対応したｃｏｓｔ＿ｃｕｔｉやｃｏｓｔ＿ｃｕｔｉｈを算出するための各種の処理コストを得る。
【０１２３】
再分割配置判断手段１３は、このようにして得られた各種の処理コストを、例えば条件式（１）に代入して、列集合Ｃｉの各々についてのｃｏｓｔ＿ｃｕｔｉを得る。
【０１２４】
以下に、クエリ実行コストの算出例を示す。本例は、上述したクエリｑ１の第３の計画に対するクエリ実行コストの算出例である。クエリｑ１は選択演算と結合演算からなるクエリであるため、クエリ実行コストは、選択演算の処理コストと結合演算の処理コストの和になる。処理コストを表す指標はＣＰＵコストやＩ／Ｏコストなど複数考えられるが、ここではＩ／Ｏコストのみ考慮する。Ｉ／ＯにはディスクのＩ／ＯとネットワークのＩ／Ｏの２種類があるが、ここではこれらの負荷はデータブロックの格納先にかかわらずみな同量であると仮定し、ディスクのＩ／Ｏコストのみを算出対象する。
【０１２５】
本例では、選択演算および結合演算の処理コストを、当該演算でアクセスされるデータブロックに含まれる行数の和で表す。データブロックにアクセスすることは、ディスクのＩ／Ｏが行われることを意味する。また、本例では、索引（インデックス）は存在しないものとする。
【０１２６】
クエリｑ１の第３の計画では、まず第１のオペレーションとして選択演算が実行される。より具体的には、テーブル“T”に対して、条件“age>30”を指定した選択演算が実行される。インデックスがない場合、条件に用いられている列集合（本例の場合、｛T.age｝）でソートされていないテーブルへの選択演算では、全てのデータブロックにアクセスする必要がある。すなわち、再分割配置しない場合の選択演算の処理コストは６となる。
【０１２７】
一方、条件に用いられている列集合をパーティションキーとしてソート分割法で再分割配置した場合の選択演算の処理コストは、次のようになる。条件に用いられている列集合の値の順にソートされた後で分割されている場合、ブロック統計情報を参照して不要なデータブロックへのアクセスを避けることができる。このため、選択演算の処理コストの計算では、まず当該選択演算においてアクセスされるであろうデータブロックの数（以下、アクセスブロック数という。）を見積もる。
【０１２８】
例えば、第２の処理コスト算出手段１２４は、メタデータとしてメタデータ格納手段２２に格納されている各列の値のヒストグラムに基づいて、条件に合致する列の値を持つ行データが全体の何％を占めるかを計算してもよい。
【０１２９】
図１３に、本例のテーブル“T”における列”age”のヒストグラムを示す。本例では、メタデータ格納手段２２から、テーブル“T”における列”age”のヒストグラムとして図１３に示されるヒストグラムが得られたとする。図１３に示すヒストグラムによれば、列”age”の値が３０よりも大きい値を持つ行データが全体の５０％存在することを事前に（再分割配置する前に）知ることができる。
【０１３０】
以下、本例においてこの５０％を選択率と呼び、πで表す。これにより、該選択演算によるアクセスブロック数は、次のような演算により求まる。
【０１３１】
アクセスブロック数＝ceil(行の総数×選択率π)÷floor(行の総数÷データブロック数)
・・・（３）
【０１３２】
ここで、ｃｅｉｌ（）は小数点以下を切り上げる関数を表している。また、ｆｌｏｏｒ（）は、小数点以下を切り捨てる関数を表している。
【０１３３】
式（３）によれば、クエリｑ１の第３の計画における第１のオペレーションである選択演算によるアクセスブロック数＝１と見積もられる。
【０１３４】
また、このとき、該選択演算によって選択される行数は、行の総数×選択率π＝３であることも分かる。
【０１３５】
第３の計画では次に、第２のオペレーションとして結合演算が実行される。なお、結合演算の処理コストは、｛T.age｝でソート分割されている場合とされていない場合とで変わらない。今、対象データ群に、テーブル“R”の行データとして、列“age”を持つ６個の行データが含まれており、３行ずつ２個のデータブロック（データブロックＲＢ１、データブロックＲＢ２）に分割されて格納されていると仮定する。
【０１３６】
分散データベースシステムにおいて結合演算でよく知られたアルゴリズムは、Ｍａｐ−ｓｉｄｅ−ｊｏｉｎと呼ばれ、次のような流れで処理を行うアルゴリズムである。
【０１３７】
当該クエリの結合演算を並列に行うノードがｎ個あるとする。一般に、データ格納手段の各々には、当該データ格納手段に格納されているデータブロックに対するデータ操作を取りまとめて行うノード（計算機）が対応づけられている。まず、第１のステップで、データベース管理システムが、より小さなテーブル“T”をｎ個のノード全てにコピーする。第２のステップで、ｎ個のノードが、より大きなテーブル“R”の行データを含むデータブロックを、ノード間で重複がないように読み込み、読み込んだテーブル“R”のデータブロックと、先のステップでコピーされたテーブル“T”とを結合する。第３のステップで、データベース管理システムが、各ノードの結合結果をマージして出力する。
【０１３８】
第３の計画の第２のオペレーションとして、第１のオペレーションによるテーブル“T”についての選択結果と、テーブル“R”との結合を行う場合、ｎ＝２とすると、まず第１のオペレーションによるテーブル“T”についての選択結果である３個の行からなるテーブル“T'”が各ノード（ノードｎ１およびノードｎ２）に読み込まれる。次に、ノードｎ１がテーブル“R”のデータブロックであるデータブロックＲＢ１を読み込んでテーブル“T'”と結合するとともに、ノードｎ２がテーブル“R”のデータブロックであるデータブロックＲＢ２を読み込んでテーブル“T'”と結合する。このとき、結合演算の処理コストは、テーブル“T'”のスキャンにかかる処理コストと、テーブル“R”の最大行数を持つデータブロックをスキャンするのにかかる処理コストである。
【０１３９】
したがって、クエリｑ１の第３の計画における第２のオペレーションである結合演算による処理コストは、３＋ｃｅｉｌ（６÷２）＝６と見積もられる。
【０１４０】
以上から、現状の分割配置すなわち列“age”でテーブル“T”を分割配置されていない状態におけるクエリｑ１のクエリ実行コスト（第１のクエリ実行コスト）であるｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏ１は６＋６＝１２となる。また、列“age”でテーブル“T”を再分割配置した状態におけるクエリｑ１のクエリ実行コスト（第２のクエリ実行コスト）であるｑｕｅｒｙ＿ｃｏｓｔ＿ｎｏ１１は、３＋６＝９となる。他のクエリについても同様の方法で、クエリ実行コストを計算できる。
【０１４１】
なお、上記の例では、ディスクのＩ／Ｏの負荷およびネットワークのＩ／Ｏの負荷は、データブロックの格納先にかかわらず同量であると仮定したが、データブロックの格納先によってこれらの負荷が異なってくる場合には、各データ格納手段を制御する各計算機のディスクバンド幅やそれら計算機間を接続するネットワークバンド幅等の当該分散データベースの構成要素の処理性能に関する情報を基に、データブロックの格納先に応じた重みを設定して、クエリ実行コストを算出してもよい。
【０１４２】
以上のように、本実施形態によれば、第一に、クエリの述語がデータ操作に与える処理コストを考慮したデータ分割配置が可能となり、演算の処理コストが問題にならないような述語が頻繁にクエリに現れている場合に、真にボトルネックとなっている述語が無視されることが回避できる。第二に、選択述語のみならず結合述語のコストも対象にし、真にコストの大きな述語を効率化するデータ分割配置のためのパーティションキーを設定できる。第三に、データの分割配置をやり直した場合のクエリセットの実行にかかる総処理時間が削減できる見込みを計算することで、再分割配置することで逆に総処理時間が増えてしまう場合を回避できる。したがって、複数のクエリや述語の演算に時間のかかるクエリを実行して初めて１つの仕事が完了する属性生成処理といった、クエリの発行を伴うワークロードの効率化が図れる。
【０１４３】
特に、分散データベースシステムが、分割したデータブロックに対してＯＲＣＦｉｌｅのようなブロック統計情報を所持する場合において、一連のクエリの実行にかかる総処理時間の減少が期待できる。
【０１４４】
また、本実施形態によれば、例えば、大量クエリの中で１つ以上の列に対する高コストな選択演算や結合演算が出現する場合に、当該１つ以上の列に対してデータの再分割配置を行ってから大量のクエリを実行したほうが再分割配置しない場合に比べて総処理時間が減る見込みがあれば、当該１つ以上の列のうち最もコスト削減量が見込まれる列集合からデータ再分割配置を行うためのパーティションキーを生成できるので、一連のクエリの実行にかかる総処理時間が最小化されることが期待できる
【０１４５】
なぜなら、クエリの述語に頻出する列集合に注目するだけでなく、その列集合を述語に含むクエリのコストに注目し、クエリセットの総処理コストが最小になるような再分割配置を行うからである。そのような再分割配置が行えるのは、式（１）等により算出されるコスト削減量に基づくパーティションキーや分割配置方法の決定による。コスト削減量に基づいて再分割配置のパーティションキーや分割配置方法を決定するので、計算コストが問題にならないような述語が頻繁にクエリに現れている場合に、真に計算のボトルネックとなっている述語が無視される問題が回避できる。また、クエリの述語ではなく述語に登場する列集合に注目することで、選択述語のみならず結合述語のコストも対象にでき、真にコストの大きな述語を効率化するデータ分割配置のためのパーティションキーを抽出できる。また、再分割配置判断手段を設けることで、不要な再分割配置を実行してしまうリスクを回避できる。
【０１４６】
なお、上記の実施形態では、分散データベースシステムが、受け付けたクエリセットに対して、データの再分割配置をするか否かおよびその方法を判断する例を示したが、データの再分割配置をするか否かを判断する手段または装置は、分散データベースシステムが備える制御装置でなくてもよい。例えば、ユーザは分散データベースシステムにクエリセットを発行する前に、別途用意されたデータ再分割配置制御装置にクエリセットを発行して、データ再分割配置制御装置が受け付けたクエリセットに対して、分散データベースシステムに格納されているデータ群に対して再分割配置をするか否かおよびその方法を判断して、判断結果に基づいて、分散データベースシステムに分割配置の命令を発行したり、クエリセットを転送してもよい。
【０１４７】
すなわち、上記の実施形態で示したクエリセット受付手段、処理コスト推定手段、再分割配置手段、クエリ実行手段、再分割配置手段、メタデータ記憶手段は、それぞれ別々のユニットとして実現されていてもよい。また、処理コスト推定手段に含まれるとした列集合抽出手段、第１の処理コスト算出手段、分割配置方法格納手段、第２の処理コスト算出手段も、それぞれ別々のユニットとして実現されていてもよい。
【０１４８】
次に、本発明の概要を説明する。図１４は、本発明の概要を示すブロック図である。図１４に示すように、本発明の制御装置は、クエリセット受付手段５１と、処理コスト推定手段５２と、再分割配置判断手段５３とを備えている。
【０１４９】
クエリセット受付手段５１（例えば、クエリセット受付手段１１）は、複数のデータ格納手段に分割されて格納されている所定のデータ群である対象データ群に対する、１つ以上のクエリを含むクエリセットを受け付ける。
【０１５０】
処理コスト推定手段５２（例えば、処理コスト推定手段１２）は、対象データ群のメタデータに基づいて、対象データ群を再分割配置せずにクエリセットを実行した場合の処理コストである第１の処理コストと、対象データ群を所定の方法で再分割配置した後にクエリセットを実行した場合の処理コストである第２の処理コストとを推定する。
【０１５１】
再分割配置判断手段５３（例えば、再分割配置判断手段１３）は、処理コスト推定手段５２による推定結果に基づいて、クエリセットを実行する前に、対象データ群を再分割配置するか否か、および再分割配置する場合にはどのような方法で再分割配置するかを判断する。
【０１５２】
このような構成を有することによって、クエリの発行を伴うワークロードの総処理時間を縮小できる。
【０１５３】
また、対象データ群は、１つ以上の列の各々に割り当てられる値を含む１つ以上の行データからなる表データであり、対象データ群は、表データにおける１つ以上の任意の列の集合である列集合をパーティションキーとして、各行データに含まれるパーティションキーの値に基づいて、１つ以上の行データを各々有する複数のデータブロックに分割されており、対象データ群のメタデータは、列の値に関する統計量を含み、処理コスト推定手段は、第２の処理コストとして、クエリセットに含まれるクエリの述語に出現する列集合をパーティションキーに用いて対象データ群を再分割配置したときのクエリセットの処理コストを、メタデータに基づいて推定し、再分割配置判断手段は、第２の処理コストのいずれかが第１の処理コストよりも小さい場合に、最も小さい第２の処理コストが得られた列集合をパーティションキーに用いて対象データ群を再分割配置すると判断してもよい。
【０１５４】
また、受け付けたクエリセットに含まれているクエリの述語に所定の頻度以上で出現する列集合を抽出する列集合抽出手段を備え、処理コスト推定手段は、列集合抽出手段によって抽出された列集合の各々をパーティションキーの候補として、各候補について、クエリセットのうち当該候補に含まれる列を使用する述語を含むクエリの実行にかかる第１の処理コストおよび第２の処理コストを推定してもよい。
【０１５５】
また、処理コスト推定手段は、パーティションキーの一候補に対して、複数の分割配置方法に対応した複数の第２の処理コストを推定し、再分割配置判断手段は、第２の処理コストのいずれかが第１の処理コストよりも小さい場合に、最も小さい第２の処理コストが得られたパーティションキーの候補と分割配置方法とを用いて対象データ群を再分割配置すると判断してもよい。
【０１５６】
また、複数の分割配置方法には、パーティションキーとされた列集合の値が同じである行データが同一データブロックに多く含まれるように対象データ群を分割する第１の分割方法と、全データブロックに渡りパーティションキーとされた列集合の値で行データがソートされるように対象データ群を分割する第２の分割方法とが含まれていてもよい。
【０１５７】
処理コスト推定手段は、クエリの実行アルゴリズムとして所定の最適化アルゴリズムを適用して、第１の処理コストおよび第２の処理コストを推定してもよい。
【０１５８】
また、処理コスト推定手段は、さらに、各データ格納手段を制御する計算機のディスクバンド幅または該計算機間を接続するネットワークのバンド幅に基づいて、第１の処理コストおよび第２の処理コストを推定してもよい。
【０１５９】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０１６０】
本発明は、分析用途に限らず、大量のデータを扱う業務システムの効率化や、複雑な計算を行う計算機システムの効率化といった用途にも好適に適用できる。
【符号の説明】
【０１６１】
１１  クエリセット受付手段
１２  処理コスト推定手段
１２１  列集合抽出手段
１２２  第１の処理コスト算出手段
１２３  分割配置方法格納手段
１２４  第２の処理コスト算出手段
１３  再分割配置判断手段
１４  再分割配置実行手段
１５  クエリ実行手段
２１  データ格納手段
２２  メタデータ格納手段
５１  クエリセット受付手段
５２  処理コスト推定手段
５３  再分割配置判断手段
【図１】
0006398632.tif 000004
【図２】
0006398632.tif 000005
【図３】
0006398632.tif 000006
【図４】
0006398632.tif 000007
【図５】
0006398632.tif 000008
【図６】
0006398632.tif 000009
【図７】
0006398632.tif 000010
【図８】
0006398632.tif 000011
【図９】
0006398632.tif 000012
【図１０】
0006398632.tif 000013
【図１１】
0006398632.tif 000014
【図１２】
0006398632.tif 000015
【図１３】
0006398632.tif 000016
【図１４】
0006398632.tif 000017