(57)【特許請求の範囲】
【請求項１】
クエリ処理要求と結果受信を行うクライアントに対して、１つ以上のデータソースを利用してクエリ処理を行うデータ処理装置において、
前記各データソースに存在する複数のデータに基づいてヒストグラムを生成するヒストグラム生成部と、
前記ヒストグラムを格納する統計情報部と、
ユーザが投稿したクエリを実行するためのクエリプランを生成するクエリ評価部と、
前記クエリプランを基に、前記統計情報部に格納されたヒストグラム、又は、自身が以前に生成した中間ヒストグラムを利用して、処理毎の出力データのヒストグラムである中間ヒストグラムを生成する中間ヒストグラム生成部と、
前記統計情報部に格納されたヒストグラムと、前記中間ヒストグラム生成部が生成した中間ヒストグラムとを利用して、前記クエリプランの処理毎にバケット単位で入出力サイズを計算する利用メモリサイズ計算部と、
前記利用メモリサイズ計算部が計算したバケット単位での入出力サイズを基に、クエリの分割範囲を決定する分割範囲生成部と、
を備えてクエリの分割を行うことを特徴とするデータ処理装置。
【請求項２】
前記各データソースに存在する複数のデータからバケット情報を収集するバケット情報収集部を備え、
前記ヒストグラムは、前記バケット情報からデータの属性別に生成する請求項１に記載のデータ処理装置。
【請求項３】
クエリ処理要求と結果受信を行うクライアントに対して、１つ以上のデータソースを利用してクエリ処理を行うためのデータ処理方法において、
バケット情報からデータの属性別にヒストグラムを生成する手順と、
当該ヒストグラムから前記クエリの処理毎の中間ヒストグラムを作成する手順と、
クエリの分割が必要な場合に前記クエリの分割範囲を指定する分割基準属性を決定する手順と、
前記分割基準属性のヒストグラムにおけるバケットを一つ選択し、当該バケットに対して処理を実行した場合の出力バケットも含めた当該バケットの利用メモリサイズを計算する手順と、
上記処理をリソースの上限となるサイズまで繰り返し、上限を超えた段階で直前に計算したバケットの上限値を、分割範囲として分割範囲リストに登録する手順と、
上記各処理について、全バケット分繰り返すことで、前記分割範囲リストから分割数を決定することを特徴とするデータ処理方法。
【請求項４】
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が単項演算による場合、
前記バケットのバウンドを利用して、対象の入力バケットの処理後のデータが含まれる出力バケットを取得し、
前記出力バケットにおいて、実際に入力バケットの処理後のデータが含まれている割合を前記バウンドから計算し、
前記割合を利用して、前記入力バケットに対する前記出力バケットのサイズを計算し、
これらの処理を入力バケットの値が含まれる全出力バケット分繰り返すことで、入力バケットを基準とした利用メモリサイズを計算する請求項３に記載のデータ処理方法。
【請求項５】
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の直積処理による場合、
処理対象の二つのデータの内、サイズの大きい方のデータの分割基準属性にある一つのバケットを基準として入力サイズを計算して利用メモリサイズの初期値とし、
もう一方の分割基準属性からバケットを取得して入力サイズを計算するとともに、二つの入力バケットから直積処理を行った場合の出力サイズを計算し、
前記利用メモリサイズに対して、前記したもう一方の分割基準属性の入力サイズと前記出力サイズを加算して新たな利用メモリサイズとし、
これらの処理を全バケット分繰り返すことで、入力バケットを基準とした利用メモリサイズを計算する請求項３に記載のデータ処理方法。
【請求項６】
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の内部結合処理による場合、
入力データにおける基準となる入力バケットのサイズを計算し、前記入力バケットが処理後に出力される値を含む出力バケットを検索し、前記出力バケットにおいて、前記入力バケットの処理後のデータが含まれている割合をバウンドから計算し、前記割合を利用して前記入力バケットに対する出力バケットのサイズの計算について、前記入力バケットの値が含まれる全出力バケット分繰り返すことで、出力結果のサイズを計算する一方、
もう一つの入力データが、基準となる入力バケットと結合される値を含むバケットを検索し、前記出力バケットと同様に当該入力データのサイズを計算し、
基準の入力バケットのサイズと、もう一つの入力データのサイズと、出力結果のサイズを合算することで、基準となる入力データのバケットにおける利用メモリサイズを計算する請求項３に記載のデータ処理方法。
【請求項７】
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の外部結合処理又は統合処理による場合、
請求項６に記載のデータ処理方法におけるバケットの利用メモリサイズを計算する手順によって利用メモリサイズを計算し、
基準となるデータにおいて、分割基準属性が持たない値を、もう一方のデータの分割基準属性が含んでいる場合に、
当該基準となるデータの分割基準属性が持たない値のサイズを計算するために、基準となるデータの分割基準属性の最初のバケットと最後のバケットにおいて、当該バケットのバウンドの範囲外を計算するに際して、
最初のバケットにおいては、下限値より前の値に該当するもう一つの分割基準属性のバケットと出力バケットのサイズを計算して利用メモリサイズに加算するとともに、
最後のバケットにおいては、上限値より先の値に該当するもう一つの分割基準属性のバケットと出力バケットのサイズを計算して利用メモリサイズに加算する請求項３に記載のデータ処理方法。
【請求項８】
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の全統合処理による場合、
基準となる入力データ及びそれ以外の入力データについて、
一つずつバケットを選択し、両入力バケットの合計サイズを利用メモリサイズとして計算する請求項３に記載のデータ処理方法。
【請求項９】
請求項３から請求項８のいずれか１項に記載の各手順をコンピュータに実行させる大規模データ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータソースの論理的な統合データモデルを提供するデータ仮想化システムにおいて、限られたリソースの環境下で、処理対象データのヒストグラムを用いて大規模データを確実に処理可能なクエリを生成するデータ処理装置、データ処理方法及び大規模データ処理プログラムに関する。
【背景技術】
【０００２】
データ仮想化システム（又はマルチデータベースシステム）は、インタフェースやデータ管理方式が異なる複数のデータソースを仮想的に一つのデータベースシステムに見せるために、各データソースが持つデータを論理的に統合して管理し、ユーザのクエリに対応するデータソースにクエリを投稿する。
代表的なデータ仮想化システムは、例えば特許文献１に示されるように、複数の階層的なデータベースシステムを、データマッピングにより仮想スキーマ（実際の物理テーブルをユーザに提供する論理テーブルに変換する処理を定義したもの）に統合し、クエリ実行時において処理対象となるデータを保持するデータベースシステムにクエリを分配するよう構成されている。各データベースシステムで実行されたクエリの結果は中央に収集され、仮想スキーマに従って一つに統合して結果を出力するシステムとなっている。
【０００３】
特許文献１のように、複数のデータソースを跨がるクエリの統合処理は、データ仮想化システム上で実行する必要がある。このとき、一つ以上のデータベースシステムから得られるデータと処理後の結果データサイズが、物理メモリサイズを超えるほど大規模であった場合、実行できずにエラー終了してしまう可能性がある。
このような場合、ＯＳのスワップ機構によって対応可能であると考えられるが、クエリ処理に最適化されておらず、遅延は非常に大きい。また、サイズがスワップ領域を超えてしまった場合にも、同様にエラー終了してしまうという問題がある。
【０００４】
データ仮想化システムは、対象の複数のデータソースが持つデータの規模や想定されるクエリの種類から、適切な物理メモリサイズを想定することで構築される。しかし事業環境の変化などから生成されるデータ量やクエリの種類が変化することで、想定した物理メモリサイズを超えるメモリが必要となる場合がある。そのような変化に対応するためにリソースを増設することは、多くの時間を必要とし、事業分析等のスピードが要求される用途で利用するユーザであったとしても、増設が完了するまで必要なクエリを実行することができない。
【０００５】
そこで本発明者は、データ仮想化システム上の限られたリソース環境において、大規模なデータに対しても破綻することなく確実にクエリ実行するために、実行可能なデータサイズとなるようにクエリを分割して実行する手法に関する提案を行った（特許文献２）。この手法によれば、処理前後のデータサイズとデータ仮想化システムのメモリサイズを基準にクエリ分割数を計算し、分割数に応じて入力テーブルを均等に分割するようなクエリを生成している。
【０００６】
また、非特許文献１には、データベースシステムにおけるクエリの最適化のために、データの属性毎のヒストグラムを利用して、クエリのコストをより正確に推定するための手法として、ヒストグラムの構成手法と、クエリ処理後の出力データのヒストグラムを算出する手法が提案されている。ヒストグラムは、属性毎の特定範囲（バウンド）における値の数（カウント）と、値の種類の数（ドメイン）を、バケットと呼ばれる単位で集計することで、データの全体の統計情報だけでは分からないデータの偏りを表現することが可能となる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平０７−１４１３９９号公報
【特許文献２】特願２０１４−２００５９６
【非特許文献】
【０００８】
【非特許文献１】Proceedings of the 2002 ACM SIGMOD international conference on Management of data, P263-P274
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述した特許文献２の手法によれば、クエリの分割数を計算し、入力データの特定の属性における範囲をその分割数で均等に分割することで、クエリを分割している。これは入力データが均等に分割されることを前提としているだけでなく、分割して取得する入力データに対する処理後のデータが、入力データと同様に均等に分割されることを前提としている。
【００１０】
しかしながら、実際にはデータの分散に応じて偏りが発生し、必ずしも分割対象の属性に対する分割が均等にデーブルを分割するとは限らない。処理後のデータに関しても同様であり、実際の出力データには、処理特性やデータの分散に応じて偏りが発生する。これにより、分割したクエリのうちの一部が、データ仮想化システム上のリソースを超えたデータサイズとなり、クエリを実行できなくなるという現象が生じる可能性がある。
【００１１】
本発明は上記実情に鑑みて提案されたものであり、データ仮想化システムにおいて、限られたリソース環境においても確実にクエリを実行するとともに、クエリ実行時の信頼性の向上を図るデータ処理装置、データ処理方法及び大規模データ処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【００１２】
上記目的を達成するため本発明のデータ処理装置は、データ仮想化システムにおいて、処理対象のデータにおける属性毎のヒストグラムを基に、ユーザが投稿したクエリの処理毎の出力データのヒストグラムを作成し、入力のバケットに対する出力のバケットの利用メモリサイズを計算することで、出力データの値の偏りを考慮した分割範囲を設定し、精度の高い分割クエリの生成を実現する。
【００１３】
すなわち、請求項１のデータ処理装置は、クエリ処理要求と結果受信を行うクライアントに対して、１つ以上のデータソースを利用してクエリ処理を行うデータ処理装置において、
前記各データソースに存在する複数のデータに基づいてヒストグラムを生成するヒストグラム生成部と、
前記ヒストグラムを格納する統計情報部と、
ユーザが投稿したクエリを実行するためのクエリプランを生成するクエリ評価部と、
前記クエリプランを基に、前記統計情報部に格納されたヒストグラム、又は、自身が以前に生成した中間ヒストグラムを利用して、処理毎の出力データのヒストグラムである中間ヒストグラムを生成する中間ヒストグラム生成部と、
前記統計情報部に格納されたヒストグラムと、前記中間ヒストグラム生成部が生成した中間ヒストグラムとを利用して、前記クエリプランの処理毎にバケット単位で入出力サイズを計算する利用メモリサイズ計算部と、
前記利用メモリサイズ計算部が計算したバケット単位での入出力サイズを基に、クエリの分割範囲を決定する分割範囲生成部と、
を備えてクエリの分割を行うことを特徴としている。
【００１４】
請求項２は、請求項１のデータ処理装置において、
前記各データソースに存在する複数のデータからバケット情報を収集するバケット情報収集部を備え、
前記ヒストグラムは、前記バケット情報からデータの属性別に生成することを特徴としている。
【００１５】
請求項３は、クエリ処理要求と結果受信を行うクライアントに対して、１つ以上のデータソースを利用してクエリ処理を行うためのデータ処理方法において、
バケット情報からデータの属性別にヒストグラムを生成する手順と、
当該ヒストグラムから前記クエリの処理毎の中間ヒストグラムを作成する手順と，
クエリの分割が必要な場合に前記クエリの分割範囲を指定する分割基準属性を決定する手順と、
前記分割基準属性のヒストグラムにおけるバケットを一つ選択し、当該バケットに対して処理を実行した場合の出力バケットも含めた当該バケットの利用メモリサイズを計算する手順と、
上記処理をリソースの上限となるサイズまで繰り返し、上限を超えた段階で直前に計算したバケットの上限値を、分割範囲として分割範囲リストに登録する手順と、
上記各処理について、全バケット分繰り返すことで、前記分割範囲リストから分割数を決定することを特徴としている。
【００１６】
請求項４は、請求項３のデータ処理方法において、
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が単項演算による場合、
前記バケットのバウンドを利用して、対象の入力バケットの処理後のデータが含まれる出力バケットを取得し、
前記出力バケットにおいて、実際に入力バケットの処理後のデータが含まれている割合を前記バウンドから計算し、
前記割合を利用して、前記入力バケットに対する前記出力バケットのサイズを計算し、
これらの処理を入力バケットの値が含まれる全出力バケット分繰り返すことで、入力バケットを基準とした利用メモリサイズを計算することを特徴としている。
【００１７】
請求項５は、請求項３のデータ処理方法において、
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の直積処理による場合、
処理対象の二つのデータの内、サイズの大きい方のデータの分割基準属性にある一つのバケットを基準として入力サイズを計算して利用メモリサイズの初期値とし、
もう一方の分割基準属性からバケットを取得して入力サイズを計算するとともに、二つの入力バケットから直積処理を行った場合の出力サイズを計算し、
前記利用メモリサイズに対して、前記したもう一方の分割基準属性の入力サイズと前記出力サイズを加算して新たな利用メモリサイズとし、
これらの処理を全バケット分繰り返すことで、入力バケットを基準とした利用メモリサイズを計算することを特徴としている。
【００１８】
請求項６は、請求項３のデータ処理方法において、
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の内部結合処理による場合、
入力データにおける基準となる入力バケットのサイズを計算し、前記入力バケットが処理後に出力される値を含む出力バケットを検索し、前記出力バケットにおいて、前記入力バケットの処理後のデータが含まれている割合をバウンドから計算し、前記割合を利用して前記入力バケットに対する出力バケットのサイズの計算について、前記入力バケットの値が含まれる全出力バケット分繰り返すことで、出力結果のサイズを計算する一方、
もう一つの入力データが、基準となる入力バケットと結合される値を含むバケットを検索し、前記出力バケットと同様に当該入力データのサイズを計算し、
基準の入力バケットのサイズと、もう一つの入力データのサイズと、出力結果のサイズを合算することで、基準となる入力データのバケットにおける利用メモリサイズを計算することを特徴としている。
【００１９】
請求項７は、請求項３のデータ処理方法において、
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の外部結合処理又は統合処理による場合、
請求項６に記載のデータ処理方法におけるバケットの利用メモリサイズを計算する手順によって利用メモリサイズを計算し、
基準となるデータにおいて、分割基準属性が持たない値を、もう一方のデータの分割基準属性が含んでいる場合に、
当該基準となるデータの分割基準属性が持たない値のサイズを計算するために、基準となるデータの分割基準属性の最初のバケットと最後のバケットにおいて、当該バケットのバウンドの範囲外を計算するに際して、
最初のバケットにおいては、下限値より前の値に該当するもう一つの分割基準属性のバケットと出力バケットのサイズを計算して利用メモリサイズに加算するとともに、
最後のバケットにおいては、上限値より先の値に該当するもう一つの分割基準属性のバケットと出力バケットのサイズを計算して利用メモリサイズに加算することを特徴としている。
【００２０】
請求項８は、請求項３のデータ処理方法において、
前記バケットの利用メモリサイズを計算する手順は、
前記クエリの処理対象が二項演算の全統合処理による場合、
基準となる入力データ及びそれ以外の入力データについて、
一つずつバケットを選択し、両入力バケットの合計サイズを利用メモリサイズとして計算することを特徴としている。
【００２１】
請求項９の大規模データ処理プログラムは、請求項３から請求項８のいずれか１項に記載の各手順をコンピュータに実行させることを特徴としている。
【発明の効果】
【００２２】
本発明によれば、データ処理装置が保持するリソース容量で実行可能なデータサイズとなるようにクエリ分割部でクエリを分割し、分割クエリが実行されるので、データ処理装置において、一つのクエリで利用するデータ仮想化装置上のリソース量を制限することが可能となるとともに、分割処理することで、リソース容量を超える大規模データ処理に対応するクエリ処理を可能とすることができる。
その際、処理対象データの属性別に生成されたヒストグラムによってクエリの分割範囲を計算することで、データの偏りや処理特性を考慮することが可能となり、データ処理装置のリソースを考慮し、クエリ分割範囲のデータサイズをより正確に把握してクエリ分割を行うことができる。
その結果、実行できないクエリを減らすことで分割したクエリの実行の確実性を担保し、データ処理装置を備えたデータ仮想化システムの信頼性をより高めることができる。
また、ヒストグラムをデータの属性別に生成することで、前記属性を基準にデータを分割することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明のデータ処理装置が含まれるデータ仮想化システムの構成を示すブロック図である。
【図２】データ処理装置のクエリ分割部における処理手順を示すフローチャート図である。
【図３】分割基準属性の優先順を示す表である。
【図４】処理種別に対するキー属性を示す表である。
【図５】データ処理装置のクエリ分割部における単項演算の場合の利用メモリサイズの計算手順を示すフローチャート図である。
【図６】データ処理装置のクエリ分割部における二項演算の直積処理による利用メモリサイズの計算手順を示すフローチャート図である。
【図７】データ処理装置のクエリ分割部における二項演算の内部結合処理による利用メモリサイズの計算手順を示すフローチャート図である。
【図８】データ処理装置のクエリ分割部における二項演算の外部結合処理及び統合処理による利用メモリサイズの計算手順を示すフローチャート図である。
【図９】データ処理装置のクエリ分割部における二項演算の全統合処理による利用メモリサイズの計算手順を示すフローチャート図である。
【発明を実施するための形態】
【００２４】
本発明のデータ処理装置の実施形態の一例について、図１を参照して説明する。
本発明のデータ処理装置は、限られたリソースの範囲内で実行可能なデータサイズとなるようにクエリ処理を分割して実行することで、大規模データに対するクエリ処理を確実に実行するようデータ仮想化システムにおいて構成されるものである。データ処理装置２は、図１に示すように、システムを利用するクライアント１と、システムが利用する１つ以上のデータソース３に対して、ネットワークを介して接続されている。
【００２５】
クライアント１、データ処理装置２及び各データソース３は、それぞれ、基本プログラムや各種の基本デバイスが記憶されたＲＯＭと、各種のプログラムやデータが記憶されるハードディスクドライブ装置（ＨＤＤ）と、ＣＲ−ＲＯＭやＤＶＤ等の記憶媒体からプログラムやデータを読み出すメディアドライブ装置と、プログラムを実行するＣＰＵと、このＣＰＵにワークエリアを提供するＲＡＭと、外部装置と通信するパラレル／シリアルＩ／Ｆとを主要部分とする一般的な構成を備えたコンピュータ上に構築されている。
例えば、上述した構成を有する各コンピュータにおいて、クエリ処理を実行するための大規模データ処理プログラムがメディアドライブ装置を介してＨＤＤにインストールされることでデータ仮想化装置が構築される。
【００２６】
クライアント１は、データ処理装置２が提供する統合データモデルを利用したクエリを投稿することで、透過的に複数のデータソース３に対するクエリ処理結果を取得する。
【００２７】
データソース３は、実際にデータを保管するストレージ３１と、データに対する処理を提供するエンジン３２からなり、エンジン３２が持つインタフェース経由でストレージ３１上のデータに対する処理を提供する。
【００２８】
ヒストグラムを利用したクエリ分割を実現するデータ処理装置２は、統計情報部２０と、バケット情報収集部２１と、ヒストグラム生成部２２と、クエリ評価部２３と、中間ヒストグラム生成部２４と、利用メモリサイズ計算部２５と、分割範囲生成部２６と、クエリ分割部２７とを備えて構成されている。
【００２９】
統計情報部２０は、各データソース３に存在するデータの統計情報として、後述するヒストグラムを構成するために必要なバケットのバウンド、カウント及びドメインを保持する。バケットとは、ヒストグラムを集計するための単位であり、カウントは、属性毎の特定範囲（バウンド）における値の数、ドメインは値の種類の数である。
【００３０】
また、統計情報部２０には、データサイズ、データ属性、データ範囲を含む前記データのサイズ推定に利用可能な統計情報が保持されている。統計情報には、属性ごとに出現するデータの種類の数（ヒストグラム）や、各属性の平均や分散値等の属性の特徴を表示する値が含まれる。また、各データソース３及びデータ処理装置２のリソース容量も記憶されている。
これらの統計情報は、後述するクエリの利用メモリサイズの計算及びクエリ分割に際して必要な情報となる。
【００３１】
バケット情報収集部２１は、統計情報部２０にヒストグラムとして登録されていないデータがデータソース３にある場合、又は、データソース３に更新されたデータがある場合に、各データソース３からバケットの情報を収集する。
【００３２】
ヒストグラム生成部２２は、バケット情報収集部２１が収集したバケットの情報から、データの属性別に統計情報としてヒストグラムを生成し、統計情報部２０にデータを格納する。ヒストグラムは、属性毎の特定範囲（バウンド）における値の数（カウント）と、値の種類の数（ドメイン）を、バケットと呼ばれる単位で集計する。このヒストグラムにより、属性の特徴となるデータの偏りを表現することが可能とし、特定の属性を基準にデータを分割することとなる。ヒストグラムの構成手法や算出手法については、上述した非特許文献１の手法が取られる。
【００３３】
クエリ評価部２３は、ユーザが投稿したクエリを実行するためのクエリプランを生成する。
中間ヒストグラム生成部２４は、クエリ評価部２３が生成したクエリプランを基に、入力となるデータの統計情報上のヒストグラム又は自身が以前に生成した中間ヒストグラム２８を利用して、処理毎の出力データのヒストグラムである中間ヒストグラムを生成する。
【００３４】
利用メモリサイズ計算部２５は、クエリプランを基に入力となるデータに対する統計情報部２０のヒストグラムと、中間ヒストグラム生成部２４が生成した中間ヒストグラム２８を利用して、単項演算、内部結合処理（Inner Join）、外部結合（Outer Join）／統合（Union）処理、直積処理（Cross Join）、全統合（Union all）処理の５通りの方法でクエリプランの処理毎にバケット単位で入出力サイズを計算する。
【００３５】
分割範囲生成部２６は、特定処理における入力データの分割基準となる属性（分割基準属性）を選択し、利用メモリサイズ計算部２５が計算した当該属性のバケット単位での入出力サイズを基に、データソース３及びデータ処理装置２のリソース容量を考慮して当該属性における分割範囲を設定し、分割範囲リスト２９を作成する。
【００３６】
クエリ分割部２７は、クエリ評価部２３が生成したクエリプランの処理毎にクエリ分割の有無を判断し、分割が必要な場合は分割範囲生成部２６が生成した分割範囲リスト２９を利用してクエリプランに分割範囲と分割対象属性を付与する。
そして、分割範囲と分割対象属性が付与されたクエリプランを基に再構築されたクエリのデータソ−ス３への投稿が実行される。
【００３７】
次に、分割範囲生成部２６における詳細処理について、図２〜図４を参照しながら説明する。
クエリ分割部２７にてクエリの分割が必要と判断された処理において、当該処理の入力データ（入力データセット）を基準としてクエリを分割するために、分割範囲を指定する分割基準属性を決定する（ステップ４０）。
データ同士を結合処理（Join）等する二項演算の場合は、もう一方の入力データに関しても同様に分割基準属性を決定する。
【００３８】
各データにおける分割基準属性は、図３に示す数字の小さい順に優先する属性（分割基準属性）が選択される。すなわち、「１．処理毎のキー属性」、「２．主キーの属性」、「３．索引付き属性」、「４．一意性制約付き属性」、「５．被ＮＵＬL制約付き属性」、「６．その他」、の優先順位で選択される。
なお、属性選択の前提として、出力後にも対象の属性が存在している必要がある。最も優先される属性は処理毎に異なっており、優先順位１の「処理毎のキー属性」が存在している場合には、これが必ず最優先に選択される。優先順位２〜６の優先順は、適宜設定可能とすることができる。
【００３９】
処理毎のキー属性は、図４に示すように、値を選択する選択処理、値を一つにまとめる集合処理、値を整列する整列処理、値同士を結合させる内部結合処理・外部結合処理において存在する。すなわち、選択処理では、選択の条件となるフィルター属性が優先的に選択される。集合処理では、集計基準となるGroup by指定属性が優先的に選択される。整列処理では並び替え基準となるOrder by指定属性が優先的に選択される。内部結合処理及び外部結合処理では、結合条件となるJoinキー属性が優先的に選択される。
キー属性がない射影処理、直積処理、統合処理、全統合処理は、図３の主キー属性が最優先される。
【００４０】
次に、この分割基準属性のヒストグラムにおけるバケットを一つ選択し、当該バケットに対して処理を実行した場合の出力バケットも含めて、当該バケットの利用メモリサイズを計算する（ステップ４１〜４８）。
すなわち、先ず、データ処理装置２において、データを記憶できる上限のメモリサイズ（リソースの上限となる物理メモリサイズ）を計算する（ステップ４１）。
次に、利用メモリサイズと合計メモリサイズの初期化をそれぞれ行う（ステップ４２、ステップ４３）。
【００４１】
ヒストグラムの一つのバケットに対する利用メモリサイズを合計メモリサイズに加算する（ステップ４４）。
ヒストグラムにおける残バケットの有無を判断する（ステップ４５）。
残バケットが有れば、当該バケットに関するヒストグラムを利用して利用メモリサイズを計算する（ステップ４６）。
【００４２】
ステップ４４の合計メモリサイズとステップ４６で計算した利用メモリサイズとを合計した値が上限メモリサイズより小さいかを判断し（ステップ４７）、小さい場合は、ステップ４４に戻って、前回の合計メモリサイズに利用メモリサイズを加算する（ステップ４４）。
これをリソースの上限となるサイズまで繰り返し（ステップ４７）、合計メモリサイズが上限メモリサイズを超えた段階で直前に計算したバケットの上限値を分割範囲とし、分割範囲リストに登録する（ステップ４８）。
バケット単位で加算を行う合計メモリサイズの上限を上限メモリサイズ（リソースの上限となるサイズ）としたのは、分割基準属性毎に行われる分割数をなるべく減らすためである。分割数を減らすことで、クエリの分割を効率良く行うことができる。
【００４３】
以上の処理を全バケット分繰り返すことで（ステップ４５）、分割範囲リストを完成させ、分割範囲リストの登録数に「１」を加えた数を分割数とし（ステップ４９）、分割範囲設定を完了する（ステップ５０）。
【００４４】
なお、二項演算の場合、選択した二つの分割基準属性のうち、サイズの大きい方のデータのみを基準に上記の処理を行い、当該データの全バケットを対象として上記の処理を行うことで、分割範囲リストの作成が完了する。
ただし、外部結合処理に関しては、左外部結合（Left Outer Join）の場合は左側のデータを、右外部結合（Right Outer Join）の場合は右側のデータを上記の処理の対象とする。
【００４５】
また、分割範囲リストは、二項演算の場合、二つの入力データそれぞれに必要となることから、二つの分割範囲リストが作成されることとなるが、直積処理と全統合処理を除き、二つともに同一の値が記録される。
直積処理に関しては、基準となるデータ側の分割範囲リストにのみ記録され、もう一方のデータ側には設定されない。
全統合処理は、それぞれのデータで異なる分割範囲リストが作成される。
【００４６】
次に、分割範囲生成部２６で分割数設定に必要な情報となる利用メモリサイズの計算方法について説明する。
利用メモリサイズ計算部２５では、バケット単位におけるヒストグラムを考慮した入出力の利用メモリサイズを計算するが、（Ａ）単項演算、（Ｂ）直積処理、（Ｃ）内部結合処理、（Ｄ）外部結合処理／統合処理、（Ｅ）全統合処理の５通りの計算方法に分類することができる（図４）。
利用メモリサイズ計算に際しての基本的な方針は、ある一つの分割基準属性における一つのバケットを基準として、当該バケットの処理後に該当する出力範囲と、二項演算の場合は同様に出力範囲を構成するために必要なもう一つの入力データの範囲も併せて算出し、それらのサイズを合算することで、利用するメモリサイズを算出する。
【００４７】
このとき、例えばハッシュテーブルのような処理上の管理データが必要になる場合には、入力バケットを基準とした対象データ範囲で必要な管理データのサイズも併せて計算する。
なお、以下の処理フローの説明では、ヒストグラムを構成するバケットが属性単位でバウンド順となっていることを前提としている。
また、以下の説明において、バウンドのうち、下限値をlower、上限値をupperと表現する。
【００４８】
（Ａ）単項演算
単項演算における利用メモリサイズの計算処理について、図５を参照して説明する。
単項演算では、入力バケットのサイズを計算後、処理後の当該属性のヒストグラムを利用して、処理後の出力サイズを計算する。
【００４９】
分割基準属性in1のヒストグラムにおける入力バケットibucを一つ取得し（ステップ６０）、入力バケットibucからデータレコードに基づく入力サイズinsizeを計算する（ステップ６１）。
処理後の出力バケットobucの情報を取得するため、出力サイズoutsizeの初期化を行う（ステップ６２）。
続いて、バケットのバウンドを利用して、対象の入力バケットibucの処理後のデータが含まれる１（i=1）番目の出力バケットobucを取得する（ステップ６３）。
次に、入力バケットibucの下限値lowerと出力バケットobucの上限値upperを比較する（ステップ６４）。
【００５０】
入力バケットibucの下限値lowerが出力バケットobucの上限値upperより小さい場合、入力バケットの処理結果が出力バケットの出力結果に含まれているので、出力バケットにおいて、実際に入力バケットの処理後のデータが含まれている割合を、バウンドから計算する（ステップ６５）。
この割合を利用して、入力バケットに対する出力バケットのサイズを計算し、出力サイズに加算する（ステップ６６）。
次のバケットについて上述の処理を繰り返すために、iの数を「１」増加する（ステップ６７）。
【００５１】
入力バケットibucの上限値upperが出力バケットobucの上限値upperより大きい場合、又は、iが処理後属性outの全バケット数bucketsと等しいか大きくなった場合（ステップ６８）、入力サイズと出力サイズとの加算を利用メモリサイズとする（ステップ６９）。
これらの処理を入力バケットの値が含まれる全出力バケット分繰り返すことで、入力バケットを基準とした利用メモリサイズを計算することができる。
【００５２】
（Ｂ）直積処理
二項演算のうち、直積処理（Cross Join）における利用メモリサイズの計算処理について、図６を参照して説明する。
二項演算の直積処理では、処理対象の二つのデータの内、サイズの大きい方のデータの分割基準属性にあるバケットを基準として、もう一方のデータ全体と直積処理を行った場合の利用メモリサイズを計算する。
【００５３】
先ず一方（サイズの大きい方）の分割基準属性in1のヒストグラムにおける入力バケットibuc1を一つ取得し（ステップ７０）、入力バケットibuc1からデータレコードに基づく入力サイズinsize1を計算する（ステップ７１）。
この入力サイズinsize1を利用メモリサイズの初期値として利用する（ステップ７２）。
次に、もう一方の分割基準属性in2からバケットibuc2を取得し（ステップ７３）、入力サイズinsize2を計算する（ステップ７4）。
【００５４】
二つの入力バケットibuc1、ibuc2から直積後の出力サイズoutsize（レコード数の乗算）を計算する（ステップ７５）。
ステップ７４で計算した入力サイズinsize2と、ステップ７５で計算した出力サイズoutsizeとを更に加算し利用メモリサイズとする（ステップ７６）。
もう一方の分割基準属性in2に未計算のバケットがあるかを判断し、ある場合には、ステップ７３〜７６の処理を繰り返す（ステップ７７）。
これらの処理を全出力バケット分繰り返すことで、入力バケットibuc1を基準とした利用メモリサイズを計算することができる（ステップ７８）。
【００５５】
（Ｃ）内部結合処理
二項演算のうち、内部結合処理（Inner Join）における利用メモリサイズの計算処理について、図７を参照して説明する。
ここでは、処理対象の二つのデータの内、サイズの大きい方のデータの分割基準属性in1にあるバケットを基準として、当該バケットと結合する入力データ及びその結果（出力データ）を対象にサイズ計算を行うことで、利用メモリサイズを計算する。
【００５６】
先ず、基準となる入力バケットのサイズを計算する。
すなわち、分割基準属性in1のヒストグラムにおける入力バケットibucを一つ取得し（ステップ８０）、入力バケットibucからデータレコードに基づく入力サイズinsizeを計算する（ステップ８１）。
【００５７】
次に、入力バケットが処理後に出力される値を含む出力バケットを検索する。
すなわち、処理後の出力バケットobucの情報を取得するため、出力サイズoutsizeの初期化を行う（ステップ８２）。
続いて、バケットのバウンドを利用して、対象の入力バケットibucの処理後のデータが含まれる１（i=1）番目の出力バケットobucを取得する（ステップ８３）。
【００５８】
次に、出力バケットにおいて、実際に入力バケットの処理後のデータが含まれている割合をバウンドから計算し、この割合を利用して、入力バケットに対する出力バケットのサイズを計算する。
すなわち、入力バケットibucの下限値lowerと出力バケットobucの上限値upperを比較する（ステップ８４）。
入力バケットibuc1の下限値lowerが出力バケットobucの上限値upperより小さい場合、入力バケットの処理結果が出力バケットの出力結果に含まれているので、出力バケットにおいて、実際に入力バケットの処理後のデータが含まれている割合を、バウンドから計算する（ステップ８５）。
この割合を利用して、入力バケットibuc1に対する出力バケットobucのサイズを計算し、出力サイズoutsizeに加算する（ステップ８６）。
次のバケットについて上述の処理を繰り返すために、iの数を「１」増加する（ステップ８７）。
【００５９】
これらの処理を入力バケットの値が含まれる全出力バケット分繰り返すことで、入力バケットを基準とした出力結果のサイズを計算し、入力バケットibuc1の上限値upperが出力バケットobucの上限値upperより大きい場合、又は、iが処理後属性outの全バケット数bucketsと等しいか大きくなった場合（ステップ８８）、一方の入力データに関する出力結果サイズの計算を終了し、もう一方の入力データに関する出力結果サイズの計算に移る。
【００６０】
もう一つの入力データが、基準となる入力データのバケットと結合される値を含むバケットを検索し、前記した出力バケットと同様に当該入力データのサイズを計算する。
【００６１】
先ず、もう一つの入力における入力サイズInsize2の初期化を行う（ステップ８９）。
続いて、分割基準属性in2の１（j=1）番目の入力バケットibuc2を取得する（ステップ９０）。
次に、入力バケットibucの下限値lowerと出力バケットobucの上限値upperを比較する（ステップ９１）。
【００６２】
入力バケットibuc1の下限値lowerが入力バケットibuc2の上限値upperより小さい場合、入力バケットibuc1の処理結果が入力バケットibuc2の処理結果に含まれているので、入力バケットibuc2において、実際に入力バケットibuc1の処理後のデータが含まれている割合を、バウンドから計算する（ステップ９２）。
この割合を利用して、入力バケットibuc1に対する入力バケットibuc2のサイズを計算し、入力サイズibuc2に加算する（ステップ９３）。
次のバケットについて上述の処理を繰り返すために、jの数を「１」増加する（ステップ９４）。
これらの処理を入力バケットibuc1の値が含まれる全入力バケットibuc2分繰り返すことで、入力バケットibuc1を基準とした出力結果サイズを計算することができる。
【００６３】
入力バケットibuc1の上限値upperが入力バケットibuc2の上限値upperより大きい場合、又は、jが分割基準属性in2の全バケット数bucketsと等しいか大きくなった場合（ステップ９５）、以上の処理で計算した基準となる入力バケットibuc1のサイズと、もう一つの入力データibuc2のサイズと、出力結果のサイズを合算することで、基準となる入力データのバケットにおける利用メモリサイズの計算が完了する（ステップ９６）。
【００６４】
（Ｄ）外部結合／統合処理、
二項演算のうち、外部結合処理（Outer Join）と統合処理（Union）における利用メモリサイズの計算処理について、図８を参照して説明する。
これらの処理においては、基本的に上述した内部結合処理（図６）と同じ計算方法で利用メモリサイズを計算する。
【００６５】
外部結合処理（Outer Join）と統合処理（Union）が内部結合処理と異なる点として、基準となるデータにおいて、分割基準属性が持たない値を、もう一方のデータの分割基準属性が含んでいる場合がある。
このような場合、入力データのサイズを計算するために、基準となるデータの分割基準属性の最初のバケットと最後のバケットにおいて、当該バケットのバウンドの範囲外を計算する必要がある。
【００６６】
すなわち、分割基準属性in1のヒストグラムにおける入力バケットibuc1を取得し（ステップ１００）、基準となるデータの分割基準属性の最初のバケットと最後のバケットを確認するため、ibuc1のテーブル順であるインデックスindexを確認して（ステップ１０１）、最初のバケット（index＝0）、最後のバケット（index＝in.buckets-1）、それ以外のバケットで場合分けを行う（ステップ１０２）。
【００６７】
最初のバケットibuc1（index＝0）においては、下限値lowerより前の値に該当するもう一つの分割基準属性のバケットibuc2及び出力バケットobucのサイズをそれぞれ計算し（ステップ１０３）、内部結合処理によるサイズ計算を行い（ステップ１０４）、利用メモリサイズに加算する（ステップ１０５）。
【００６８】
最後のバケット（index＝in.buckets-1）においては、内部結合処理によるサイズ計算を行い（ステップ１０６）、上限値upperより先の値に該当するもう一つの分割基準属性のバケットibuc2及び出力バケットobucのサイズをそれぞれ計算し（ステップ１０７）、利用メモリサイズに加算する（ステップ１０８）。
【００６９】
それ以外のバケットについては、上述した内部結合処理によるサイズ計算のみで利用メモリサイズを計算する（ステップ１０９）。
そして、ステップ１０５、ステップ１０８、ステップ１０９で計算した利用メモリサイズを合計することで、入力バケットibuc1の利用メモリサイズの計算が完了する。
【００７０】
（Ｅ）全統合処理
二項演算のうち、全統合処理（Union all）における利用メモリサイズの計算処理について、図９を参照して説明する。
全統合処理では、基準となる入力データと、それ以外の入力データでのバケット選択方法に違いはなく、両データともに一つずつバケットを選択し、両入力バケットの合計サイズを利用メモリサイズとして計算する。
すなわち、分割基準属性in1のヒストグラムにおける入力バケットibuc1を一つ取得する（ステップ２００）。
未計算の分割基準属性in2の入力バケットibuc2を選択する（ステップ２０１）。
入力バケットibuc1と入力バケットibuc2の合計サイズinsizeを計算する（ステップ２０２）。
この合計サイズinsizeを利用メモリサイズとする（ステップ２０３）。
【００７１】
上述したデータ仮想化システムにおけるデータ処理装置によれば、バケット情報収集部２１を介して統計情報部２０で記録された処理対象のデータにおける属性毎のヒストグラムを基に、ユーザが投稿したクエリの処理毎の出力データのヒストグラムをヒストグラム生成部２２で作成し、入力のバケットに対する出力のバケットの利用メモリサイズを利用メモリサイズ計算部２５が計算することで、出力データの値の偏りを考慮した分割範囲を分割範囲生成部２６で設定し、クエリ分割部２７で精度の高い分割クエリの生成を実現することができる。
その結果、一つのクエリで利用するデータ処理装置２上のリソース量を制限することが可能となるので、リソース容量を超える大規模データ処理に対応することができる。
【符号の説明】
【００７２】
１…クライアント、  ２…データ処理装置、  ３…データソース、  ２０…統計情報部、  ２１…バケット情報収集部、  ２２…ヒストグラム生成部、  ２３…クエリ評価部、  ２４…中間ヒストグラム生成部、  ２５…利用メモリサイズ計算部、  ２６…分割範囲生成部、  ２７…クエリ分割部、  ２８…中間ヒストグラム、  ２９…分割範囲リスト、  ３１…ストレージ、  ３２…エンジン。
【図１】
0006401617.tif 000002
【図２】
0006401617.tif 000003
【図３】
0006401617.tif 000004
【図４】
0006401617.tif 000005
【図５】
0006401617.tif 000006
【図６】
0006401617.tif 000007
【図７】
0006401617.tif 000008
【図８】
0006401617.tif 000009
【図９】
0006401617.tif 000010