(57)【特許請求の範囲】
【請求項１】
順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリと、前記第１のクエリが分散処理した後に前記複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリと、をコンピュータが実行するデータ処理方法であって、
前記第１のクエリの構文情報から抽出されるカテゴリの属性を特定する前記第１の分散キーと、前記所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する前記第２の分散キーとの関係性を示す値を算出し、
前記算出した関係性を示す値に基づき、前記第１のクエリと前記第２のクエリとをグループ化したクエリグループを生成し、
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行う、
手順を含む、データ処理方法。
【請求項２】
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行ったときのスループットの予測値を算出し、
前記スループットの予測値に基づき、前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行うことを抑制する、
手順を含む、請求項１に記載のデータ処理方法。
【請求項３】
順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリと、前記第１のクエリが分散処理した後に前記複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリと、をコンピュータに実行させるデータ処理プログラムであって、
前記第１のクエリの構文情報から抽出されるカテゴリの属性を特定する前記第１の分散キーと、前記所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する前記第２の分散キーとの関係性を示す値を算出し、
前記算出した関係性を示す値に基づき、前記第１のクエリと前記第２のクエリとをグループ化したクエリグループを生成し、
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行う、
手順を含む、データ処理プログラム。
【請求項４】
順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリと、前記第１のクエリが分散処理した後に前記複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリと、を実行するデータ処理装置であって、
前記第１のクエリの構文情報から抽出されるカテゴリの属性を特定する前記第１の分散キーと、前記所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する前記第２の分散キーとの関係性を示す値を算出する関係性算出部と、
前記算出した関係性を示す値に基づき、前記第１のクエリと前記第２のクエリとをグループ化したクエリグループを生成するクエリグループ化部と、
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行う分散処理部と、
を有するデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理方法、データ処理プログラム及びデータ処理装置に関する。
【背景技術】
【０００２】
インターネット、クラウドコンピューティングの普及に伴い、ネットワークに接続される様々な情報ソース、機器、センサー等から提供されるビックデータをリアルタイムに処理する要望が高まっている。ビックデータをリアルタイムに処理する技術として、データストリーム処理技術が挙げられる。
【０００３】
データストリーム処理技術では、処理内容を抽象度の高い「クエリ」（問合せ）で記述することで、簡潔で分かりやすい高効率なプログラミングが可能である。データストリームで使用するクエリは「継続クエリ」とも呼ばれる。
【０００４】
データベース分野におけるクエリと異なり、継続クエリは計算機に常駐し、センサー等から新しいデータが入力されるたびにそのデータを処理し、その結果を出力する。継続クエリは、ユーザから停止の指示がない限り終了しない。以下では、データストリーム処理の「継続クエリ」を「クエリ」と記述する。
【０００５】
データストリーム処理の「プログラム」は複数のクエリで構成され、センサー等からのデータが複数のクエリによって順番に処理される。データストリームのプログラムを負荷分散する方法にクエリ分散による負荷分散とデータ分散による負荷分散とがある。クエリ分散は、複数のクエリを複数のサーバに一対一に割当てることで、各サーバの負荷を分散させる。しかしながら、複数のクエリのうちの一のクエリの処理内容が重くなると、そのクエリに割当てたサーバがボトルネックになる可能性がある。
【０００６】
データ分散は、入力ストリームと中間ストリームとに流れるデータを複数のサブセット（パーティション）に分けて、各パーティションをサーバに割り当てる。パーティションとサーバの割り当て状況はパーティションテーブルで管理される。各サーバは、常にパーティションテーブルのデータを最新に更新し、管理する。そうすることで、一つのクエリは複数のサーバで処理することができ、クエリの負荷分散が可能となる。
【０００７】
具体的には、ストリームに流れる各イベントに対して、特定の属性の値（以下、「分散キー」という。）に対する特定の関数（以下、「パーティショニング関数」という。）の値により、イベントが所属するパーティションが決まる。そしてパーティションテーブルに基づいて、そのパーティションが割り当てられたサーバが決まり、イベントがそのサーバへ転送され、転送されたサーバでイベントのデータ処理が実行される。
【０００８】
クエリによる処理としては、データに含まれる分散キーにより負荷分散を実行可能なクエリと、所定の期間と空間内のイベントのデータを保持し、保持された数のイベントのデータと処理内容とが関連するクエリ（以下、「レンジクエリ」ともいう。）が挙げられる。レンジクエリでは、保持する対象のデータはデータウィンドウと呼ばれるデータ区間で定義される。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平９−２１２５２８号公報
【非特許文献】
【００１０】
【非特許文献１】Hershberger, J., Shrivastava, N., Suri, S., & Toth, C. D. (2005). Adaptive spatial partitioning for multidimensional data streams. In Algorithms and Computation (pp. 522-533). Springer Berlin Heidelberg.http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.157.9503
【発明の概要】
【発明が解決しようとする課題】
【００１１】
以下、カテゴリの属性毎にまとまった、連続性のないデータを分散処理するクエリを非レンジクエリとも称呼し、所定の区間内の連続したデータを分散処理するクエリをレンジクエリとも称呼する。
【００１２】
非レンジクエリとレンジクエリとがシリアルに接続される処理については、データ量が多くなく、処理を行うサーバの台数も少ない状況では非レンジクエリにおけるデータの負荷分散と、レンジクエリにおけるデータの負荷分散とを別々に行っても問題となる程度のスループットの低下は生じない。
【００１３】
ところが、データ量が増加し処理を行うサーバの台数が増加すると、非レンジクエリとレンジクエリとに相関関係が見い出せないため、あるサーバにて非レンジクエリで処理されたデータが同一サーバのレンジクエリで処理される保証はない。この結果、非レンジクエリの段階とレンジクエリの段階とでサーバ間で発生するデータの通信量が増大してストリームに流れる各イベントに対する全体の出力データのスループットが低下するという課題が生じる。
【００１４】
これに対して、非レンジクエリとレンジクエリとの関連性を見つけて非レンジクエリとレンジクエリとをグループ化し、サーバ間で発生するデータの通信量を減らすことが考えられる。しかし、たとえグループ化したとしても非レンジクエリとレンジクエリとの完璧な関連性が見いだせないことにより関係性に反するイベント（以下、「例外イベント」という。）の発生率（（以下、「例外率」という。）が高くなると、スループットは向上しない。
【００１５】
そこで、一側面では、本発明は、カテゴリの属性毎にまとまった、連続性のないデータを分散処理するクエリと、所定の区間内の連続したデータを分散処理するクエリと、を順次処理する際の通信量を低減し、スループットを向上させることを目的とする。
【課題を解決するための手段】
【００１６】
一つの案では、順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリと、前記第１のクエリが分散処理した後に前記複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリと、をコンピュータが実行するデータ処理方法であって、前記第１のクエリの構文情報から抽出されるカテゴリの属性を特定する前記第１の分散キーと、前記所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する前記第２の分散キーとの関係性を示す値を算出し、前記算出した関係性を示す値に基づき、前記第１のクエリと前記第２のクエリとをグループ化したクエリグループを生成し、前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行う、手順を含む、データ処理方法が提供される。
【発明の効果】
【００１７】
一側面によれば、カテゴリの属性毎にまとまった、連続性のないデータを分散処理するクエリと、所定の区間内の連続したデータを分散処理するクエリと、を順次処理する際の通信量を低減し、スループットを向上させることができる。
【図面の簡単な説明】
【００１８】
【図１】クエリの記述例を示す図。
【図２】図１の記述例で用いたクエリＱ１の実行例を示す図。
【図３】time windowの記述例を示す図。
【図４】図３のtime windowの動作を示す図。
【図５】データストリームのプログラムの一例を示す図。
【図６】非レンジクエリのためのパーティションテーブルの一例を示す図。
【図７】構文情報から分散キーを抽出する一例を示す図。
【図８】構文情報から分散キーを抽出する他の例を示す図。
【図９】データ分散の一例を示す図。
【図１０】レンジクエリの一例を示す図。
【図１１】レンジクエリの記述例を示す図。
【図１２】レンジ分散の一例を示す図。
【図１３】負荷の偏りに応じたレンジ幅の調整例を示す図。
【図１４】レンジクエリの動的負荷分散技術を説明するための図。
【図１５】レンジクエリのためのパーティションテーブルの一例を示す図。
【図１６】サーバ間の通信量の見積もりの一例を示す図。
【図１７】構文情報から分散キーの間で関係性を求める例を説明するための図。
【図１８】分散キー間の関係性を利用しない負荷分散の一例を示す図。
【図１９】分散キー間の関係性を利用した負荷分散の一例を示す図。
【図２０】関係性の例外率と正常率の計算方法の一例を示す図。
【図２１】最大スループットが低下する例を説明するための図。
【図２２】分散の粒度が小さく、オブジェクトの移動によって座標Ｘが変わる例を示す図。
【図２３】例外率が高く、関係性が見つからない例を示す図。
【図２４】一実施形態にかかるデータ処理装置の機能構成の一例を示す図。
【図２５】一実施形態にかかるデータ処理装置による処理の流れを説明するための図。
【図２６】組合せカウンターテーブルの一例を示す図。
【図２７】パーティションテーブルの一例を示す図。
【図２８】関係性テーブルの一例を示す図。
【図２９】分散キーテーブルの一例を示す図。
【図３０】関係値算出処理の比較例を示す図。
【図３１】一実施形態にかかる関係値算出処理の一例を示す図。
【図３２】一実施形態にかかるクエリグループ最適化の一例を示す図。
【図３３】比較例における最大スループットの計算の一例を示す図。
【図３４】一実施形態における最大スループットの計算の一例を示す図。
【図３５】一実施形態におけるデータ分散処理の一例を示す図。
【図３６】比較例におけるレンジクエリの負荷分散処理の一例を示す図。
【図３７】一実施形態におけるレンジクエリの負荷分散処理の一例を示す図。
【図３８】一実施形態にかかる例外率の計算の一例を示す図。
【図３９】一実施形態にかかる例外率の削減を説明するための図。
【図４０】一実施形態にかかるクエリグループ作成による最大スループットの改善の一例を示す図。
【図４１】一実施形態にかかるオブジェクトの高速移動を示す図。
【図４２】一実施形態にかかる例外率が上昇する例を示す図。
【図４３】一実施形態にかかる例外率上昇による最大スループット低下の一例を示す図。
【図４４】一実施形態にかかる負荷分散による最大スループット低下の一例を示す図。
【図４５】一実施形態にかかる負荷分散処理を抑止した場合の一例を示す図。
【図４６】一実施形態にかかるデータ処理装置のハードウェア構成例を示す図。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について添付の図面を参照しながら説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複した説明を省く。
【００２０】
（データストリームの処理モデル）
はじめに、データストリームの処理モデルの概要について説明する。クエリによる処理としては、カテゴリの属性毎にまとまった、連続性のないデータを分散処理する非レンジクエリと、所定の区間内の連続したデータを分散処理するレンジクエリとが挙げられる。非レンジクエリの分散キーは、非レンジクエリの構文情報から抽出されるカテゴリの属性を特定する。カテゴリの属性は、入力ストリームデータがもつカテゴリの属性であり、カテゴリの属性の一例としては、町、国、区等の地域に関するデータの属性や、男性、女性等の性別に関するデータの属性が挙げられる。
【００２１】
レンジクエリでは、最新の一定数又は一定の期間と空間内のイベントのデータを保持し、保持された一定数のイベントのデータと処理内容とが関連する。レンジクエリでは、保持する対象のデータはデータウィンドウと呼ばれるデータ区間で定義される。レンジクエリの分散キーは、所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する。所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性の一例としては、図１０に示す、所定のレンジ（例えば５分以内）の進行方向の４マイル以内の事故（イベント）が挙げられる。
【００２２】
なお、所定の区間内の連続したデータは、レンジクエリで保持する最新の一定数又は一定の期間と空間内のイベントのデータである。例えば、所定の区間内の連続したデータには、入力ストリームデータの最新の５分以内の連続したデータや、入力ストリームデータの最新の５個以内の連続したデータが含まれる。
【００２３】
最新の一定数又は一定の期間と空間内のイベントのデータ、つまり、所定の区間内の連続したデータの一例としては、図１４（ａ）に示す外枠で囲まれた空間に存在するデータが挙げられる。所定の区間内の連続したデータの座標の分布に応じて分割される領域の一例としては、図１４（ａ）に示す分割された各領域（例えば、Ｂａ、Ｂｂ・・・・の領域）が挙げられる。図１４（ａ）に示す外枠で囲まれた空間に存在する各データは、いずれかの領域の属性を有する。
【００２４】
非レンジクエリは、順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリの一例である。また、レンジクエリは、順次入力する複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリの一例である。
【００２５】
本実施形態にかかるデータ処理方法は、レンジクエリと非レンジクエリの両方を含んだデータストリーム処理のプログラムの並列分散を行う際の、最大スループットを向上させる分散方法を提供する。
【００２６】
クエリ言語としてＥＰＬ（Event Processing Language）がある。図１にＥＰＬでのクエリの記述例を示す。上記の例でのINSERT INTO句には出力先のストリーム名を指定する。SELECT句には入力ストリームから受け取ったイベントに対する、出力対象属性や式を指定する。SELECT句にある「count (*) AS C」の部分では、今まで受信したイベントの数をカウントし、その結果を属性Cに設定することを意味する。FROM句にはクエリの入力ストリームを指定する。最後の「GROUP BY A」句はSELECT句のcount(*)の結果が特定の属性Ａの値ごとにグルーピングされることを意味する。「count (*)」と「GROUP BY A」の組み合わせでは、属性Ａの値毎に、その値を持ったイベント数がカウントされることを意味する。
【００２７】
クエリがイベントを処理する際、過去の全てのイベントに対して再処理を行わなくて済むように、中間結果を内部状態として持ち続けて、新しいイベントが来るたびにその内部状態をインクリメンタルに更新することで処理を行う。図１の記述例で用いたクエリＱ１の実行例を図２に示す。図２では、入力イベント（Ａ，Ｂ）の属性Ａに着目し、Ａが「１」のときのイベント数、Ａが「２」のときのイベントの出現数がそれぞれカウントされ、その結果を属性Ｃに設定した出力イベント（Ａ，Ｂ、Ｃ）が出力される。その際、イベント毎の内部状態が記憶され、イベントが入力される毎に属性Ａの値毎に１ずつインクリメントされる。
【００２８】
データストリームの特殊なオペレータとして、データウィンドウがある。データウィンドウは過去にストリームから受け取ったイベントのうち、最新の一定の数のイベントのみを保持し、後で別のストリームから受け取るイベントと突合せて処理するためのオペレータである。
【００２９】
データウィンドウにはいくつかの種類がある。代表的な種類としてはlength windowとtime windowがある。length windowでは最新の一定の個数のイベントのみを保持する。例えば、最新の５個のイベントを保持する場合等である。time windowでは最新の一定の期間内のイベントを保持する。例えば、最新の５分以内のイベントを保持する場合等である。
【００３０】
time windowの記述例を図３に示す。FROM句の「win:time(5 min)」は入力ストリームＳ２に対して５分間のtime windowを設定することを意味する。「SELECT count(*)」と組み合わせることで、最新の５分間に発生したイベントＳ２の数をカウントする処理を行うことができる。
【００３１】
図３に記述したＥＰＬの中のtime windowの動作を図４に示す。過去５分間のデータウィンドウのイベントが保持され、クエリの処理対象となる。５分間経過後のイベントは削除される。
【００３２】
データストリーム処理の「プログラム」は複数のクエリで構成される。例えば、ネットワークに接続される様々な情報ソース、機器、センサー等から送信されるイベントは、図５に示すようにプログラムの入力ストリームで受信され、入力ストリームに繋がる前段のクエリＱ１が受取って処理した結果を出す。前段のクエリＱ１の出力には後段のクエリＱ２が繋がっていて、後段のクエリＱ２は前段のクエリＱ１の結果を受取ってさらに処理を行い結果を出力する。そして後段のクエリＱ２の結果は、プログラムの出力ストリームへと送信され、ユーザ又は他のアプリに通知される。こうして、センサー等からのデータが複数のクエリによって順番に処理されることで高度な分析処理が実現できる。前段のクエリＱ１と後段のクエリＱ２との間を繋ぐデータストリームを「中間ストリーム」と呼ぶ。
【００３３】
（データストリーム処理のプログラムの負荷分散方法）
次に、データストリーム処理のプログラムの負荷分散方法について説明する。データストリームのプログラムを負荷分散するには、「クエリ分散」及び「データ分散」の２つの方法がある。クエリ分散は、一つ一つのクエリを一つ一つのサーバに割当てることで、各サーバの負荷を分散させるが、一つのクエリの処理内容が重くなると、そのクエリに割当てたサーバがボトルネックになる可能性がある。
【００３４】
本実施形態では、データ分散による負荷分散が実行される。データ分散では、入力ストリームと中間ストリームに流れるデータを複数のサブセット（パーティション）に分けて、各パーティションをサーバに割り当てる。つまり、データ分散は、各サーバに割り当てるデータを分散させることで、各サーバの負荷を分散させる。パーティションとサーバの割り当て状況はパーティションテーブルで管理され、常に各サーバがパーティションテーブルの最新のコピーを持っている。このようにして一つのクエリを複数のサーバで処理することができ、クエリの負荷分散が可能となる。
【００３５】
具体的には、ストリームに流れる各イベントに対して、特定の属性の値（分散キー）に対する特定の関数（パーティショニング関数）の値により、イベントが所属するパーティションが決まる。そしてパーティションテーブルに基づいて、そのパーティションが割り当てられたサーバが決まり、イベントがそのサーバへ転送され、転送されたサーバで処理される。
【００３６】
図６は、パーティションテーブルの一例を示す。パーティションテーブルは、一つのクエリの分散状況を示す。各行には分散したクエリの一つのパーティションの割り当て状況が記録される。ＰＩＤ（パーティションＩＤ）欄にはそのパーティションの識別子が記録される。ＰＩＤはクエリの分散キー（例えば、属性Ｘ）の値によって決まるため、本原稿ではＰＩＤ（Ｘ）で記載することもある。サーバＩＤ欄にはそのパーティションが割り当てられたサーバの識別子が記録される。countにはＰＩＤで識別されるパーティションに属するイベントの数が記録される。サーバ負荷にはサーバＩＤで識別されるサーバの負荷状況が記録される。本実施形態では、サーバの負荷をＣＰＵやメモリなどのリソースを区別しない例で示しているが、リソースごとに欄を追加して区別する場合もありえる。
【００３７】
クエリ分散では一つ一つのクエリの処理を一つ一つのサーバに割り当てることで、各サーバの負荷を分散させるが、一つのクエリの処理内容が重くなると、そのクエリを割り当てたサーバがボトルネックになる可能性がある。これに対して、データ分散では、各サーバで処理するデータ量のバラツキは少なくなる。しかし、データ量が多いサーバは処理が遅くなりボトルネックになる。
【００３８】
効率的なデータ分散を行うには、すべてのイベントが転送された最初のサーバの中で処理されることが重要である。イベント処理のために、最初のサーバから他のサーバへの再転送が必要となった場合、ネットワーク上のデータ通信量が増えてシステムの性能が悪化し、全体のスループットが低下することがあるためである。イベントが最初に転送されたサーバ内で再転送なく処理できるかどうかは、クエリ処理の内容を構文解析した情報（構文情報）とデータ分散に使用する分散キーによって決まる。
【００３９】
例えば、図６に示したクエリＱ１の場合、「GROUP BY A」の構文は全ての属性Ａの値に対して一つの独立したステートが存在し、一つのイベントは同じ属性Ａの値で関連したステートだけで処理することができることを意味する。つまり、分散キーには属性Ａを使用すれば、分散の際はすべてのイベントが属性Ａの値によって転送されたサーバ内で再転送されることなく処理することができる。よって、クエリＱ１を効率よく分散するためには、図７に示すように属性Ａを分散キーに使用する必要がある。データ分散では、こうして構文情報からクエリの分散キーを抽出することができる。これにより、属性Ａのイベントのデータは同一サーバに転送され、サーバ間のデータ転送を抑制することができる。
【００４０】
図８は、構文情報から分散キーを抽出する他の例を示す。クエリＱ３は２つの入力ストリームＳ１とＳ２からイベントを受け取り、Ｓ１から来たイベントを５分間のtime windowに保持しつつ、Ｓ２から来たイベントをtime windowにある過去のイベントと比較し、属性ＩＤの値が一致するものと結合して出力する。そのような条件つきの結合処理をequi-joinと呼ぶ。構文情報からは、equi-joinの条件で使われる属性がそのクエリの分散キーとして抽出される。
【００４１】
分散キーの後は、パーティショニング関数を決める必要がある。パーティショニング関数にはモジュロ（ハッシュ関数：サーバ数で割った余り）を使うことが多い。分散キーで使われる属性の種類が数値でない場合、オブジェクトのハッシュ値にモジュロをかけたものをパーティショニング関数とすることが多い。モジュロ以外でも、同じＡの値に対して毎回同じＦ（Ａ）を返すような関数であれば、どんな関数を使ってもよい。図９は、データ分散の例を示す。ハッシュ関数により「Ａ％２」の余りが１か０かによって、入力イベントがサーバ１又はサーバ２に転送される。これにより、属性Ａによってデータ分散が実行される。本実施形態は、データ分散による負荷分散と、上記の分散キーとパーティショニング関数の決定方法を前提としたデータ処理方法である。
【００４２】
オブジェクト同士の距離が一定の範囲内であるかどうかを検知するクエリを「レンジクエリ」と呼ぶ。図１０は、レンジクエリの具体例を示す。例えば、道路を走っている車のドライバに対して、車の走る方向で４マイル先までに最新の過去の５分以内で事故が発生したかを通知する。
【００４３】
このようなレンジクエリを実現するには、例えば図１１のようなプログラムでレンジクエリをＥＰＬで記述する。from句のAccidentsはデータストリームであり、事故が検知され場合にAccidentsストリームにイベントが流れる。from句のAccidents.win:time(5 minutes)は、Accidentsのストリームに対して、最新の過去の５分間の事故を保持するためのtime windowが定義されている。LocationReportsストリームからイベントを受け取った場合、そのwindowで保持している最新５分以内のAccidentsイベントとの突合せを行う。突合せの条件はwhere句で次のとおりに行われる。
【００４４】
車の位置を表す座標v.xと最新の過去５分以内に検知された事故の発生場所を表す座標a.xの比較が行われ、a.xが進行方向の４マイル以内にあれば条件が満たされ、関連したLocationReportsとAccidentsのイベントが結合され出力される。
【００４５】
（レンジクエリの負荷分散方法）
次に、レンジクエリの負荷分散方法（以下、「レンジ分散」ともいう。）について説明する。レンジクエリの分散を行う際、レンジ検索の条件式で使われる座標ｘが分散キーとして利用され、ｘの値を複数の任意なレンジに分けるようなパーティショニング関数を利用する。また、本実施形態では、一つのパーティションを一つのサーバに割り当てる。
【００４６】
例えば、図１２では、入力イベント（ｘ）のｘ値の範囲が［０，８］（０と８を含む範囲）であり、レンジクエリが３台のサーバで分散され、パーティショニング関数Ｆが「Ｆ（ｘ）＝ｘ／３」（割り算の余りは切り捨て）に設定されている。その場合、ｘの値のレンジ［０，２］はサーバ１、［３，５］はサーバ２、［６，８］はサーバ３に転送される。
【００４７】
レンジクエリ用のパーティショニング関数には「Ｆ（ｘ）＝ｘ／Ｎ」（割り算の余りは切り捨て、Ｎ=サーバ台数）以外の関数も使用できる。また、イベントの量とばらつきに合わせてパーティショニング関数を動的に変更することもできる。「Ｆ（ｘ）＝ｘ／Ｎ」の場合、各サーバが担当するｘ値のレンジ幅はＮで一定となるが、他の関数を使えば各サーバが担当するｘ値のレンジ幅が図１３のようにばらばらになることもありうる。パーティショニング関数を動的に変えれば、特定のｘ値に対するイベントが他のｘ値よりも多く発生した場合は、負荷の偏りを防ぐために、その値を包含するレンジを小さくすることがある。
【００４８】
データ分散を用いて複数のクエリで構成されるデータストリームのプログラムの負荷分散を行う際、最大スループットは以下のパラメータの影響を受ける。スループットを最大化するには１に示す調整可能なパラメータから、最適なパラメータの組合せを求める必要がある。
１．調整可能な要因（最適化の対象）
・各ストリームの分散に使用する分散キー
・各ストリームの分散に使用するパーティショニング関数
・各サーバに転送するイベント数
・レンジクエリの場合、分散の粒度（各サーバが担当するレンジ幅）
２．調整不可な要因（最適化の対象外）
・各ストリームに流れるデータ量
・各ストリームに流れるデータの中での、属性間の相互関係
なお、本実施形態では、分散キーは、データ分散用のパーティショニング関数に使用する属性（複数の属性も使用可能）をいう。また、分散の粒度は、各サーバが担当する分散キー値のレンジ幅をいう。
【００４９】
また、本実施形態では、最大スループットは、分散されたシステムが１秒以内に最大処理可能なイベントの数をいう。なお、ここでのシステムは、データストリームの分散処理に使うサーバとネットワークの物理資源である。
【００５０】
最適なパラメータの組合せを求める技術の一例として、レンジクエリの動的負荷分散技術と、データストリーム処理分散時のスループット最大化技術について説明する。
【００５１】
（レンジクエリの動的負荷分散技術：以下、「技術１」ともいう。）
技術１では、レンジクエリの実行中に、流れてくるデータの偏りに応じて、各サーバが担当するレンジ（粒度）を動的に調整することが可能である。図１４は、技術１における分散の粒度の動的な調整例を示す。技術１では、データの偏りに応じた２次元レンジ幅の動的調整が可能である。技術１では、まず分散キーの空間をいくつかの領域に分割し、各領域を各サーバに一対一に割り当てる。データ量が多い領域（図１４では領域Ｂｅ，Ｂｂ）を細かく区切り、また、データ量が少ない領域は大きな領域に区切ることで、各サーバに与える負荷（データ量）を均等にする。その結果、各サーバのＣＰＵやメモリの使用率が均等となる。
【００５２】
また、技術１では負荷分散が動的に行われている。ある領域のデータ量が急増して一台のサーバで処理出来なくなった場合はその領域をさらに分割し、サーバを追加して各サーバに分割した各領域を割り当てることで、各サーバの負荷を動的に分散することができる。これにより、どのサーバもボトルネックとならないような制御が可能である。
【００５３】
負荷分散が行われた結果は、パーティションテーブルに反映される。図１５は、レンジクエリのためのパーティションテーブルの一例を示す。図６に示した非レンジクエリのためのパーティションテーブルを拡張したものである。レンジクエリの場合、各パーティションには各領域のデータが属し、その領域はrange startとrange endの欄で定義されている。負荷分散のために一つの領域が複数の領域に分けられるとテーブル上のパーティションも２つに分けられ、追加されたサーバに分割されたパーティションＩＤの一方が割り当てられる。countには各パーティションに属するイベント数が記録される。
【００５４】
図１４では、２次元のデータが４つの領域に分けられ、そのうちのデータの負荷が高い領域が更に４つの領域に分けられている。各領域には各パーティションを識別するパーティションＩＤ（ＰＩＤ）が付けられている。レンジクエリの場合、領域の境界に近い空間にデータが存在する場合、二つ以上の領域に跨ったレンジクエリになることがあり、このときサーバ間に通信が生じる。例えば、データ区間Ｒ１に示すレンジクエリのようにレンジに含まれるデータが複数の領域に跨っていない場合、サーバ間の通信は生じない。一方、データ区間Ｒ１に示すレンジクエリのようにレンジに含まれるデータが複数の領域に跨っている場合、サーバ間の通信が生じる。
【００５５】
レンジクエリの動的負荷分散は、「各サーバの負荷」と「サーバ間通信」の両方を考慮して行うことができるので、特定のリソース（サーバ又はネットワーク）がボトルネックになることを防ぐことが可能である。よって、最大スループットを最大化するための最適な構成を選ぶことが可能である。各サーバの負荷は、ＣＰＵとメモリの負荷状況を取得することで判断できる。ネットワークの負荷を把握するには負荷分散後のサーバ間の通信量を見積もる必要がある。サーバ間の通信量は図１６に示すように分散の粒度を使って統計的に見積もることができる。
【００５６】
検索対象が三つのレンジの場合、車がサーバ２のレンジの最左に位置し、矢印の方向に走行しているとき、検索対象のレンジは図１６に示すサーバ２内の三つのレンジであるためサーバ２及びサーバ３間の通信は発生しない。車がサーバ２のレンジの左から２番目に位置するときも同様に、検索対象のレンジはサーバ２内の三つのレンジであるためサーバ２及びサーバ３間の通信は発生しない。
【００５７】
一方、車がサーバ２のレンジの左から３番目又は４番目に位置するとき、検索対象のレンジがサーバ２とサーバ３に跨り、サーバ３まで検索する必要がある。このため、サーバ間の通信が発生する。よって、図１６の例の場合のサーバ２からの通信量は、２（隣のサーバを確認する必要のある領域）／４（全体の領域数）×データ量で示される。
【００５８】
（データストリーム処理分散時のスループット最大化技術：以下、「技術２」ともいう。）
データストリーム処理分散時のスループット最大化技術の他の例として、技術２では、ストリームで繋がった複数のクエリを共通の分散キーとパーティショニング関数とで分散することで、クエリ間通信を削減する。このように共通の分散キーとパーティショニング関数を持つストリームで繋がったクエリ群をクエリグループと呼ぶ。
【００５９】
共通な分散キーは、構文情報から分散キーの間で関係性を求めることで見つかる。例えば図１７に示すように、クエリＱ１の構文情報から、中間ストリームＳ２の属性Ｙが入力ストリームＳ１の属性ＸからＹ＝２＊Ｘという関数で計算されることが分かる。Ｘ→Ｙという関係性が存在する。
【００６０】
Ｑ１とＱ２の分散キーには、それぞれのクエリのgroup by句で使われる属性ＸとＹが設定される。構文情報から求められたＸ→Ｙの関係性を利用せず、Ｑ１とＱ２をそのまま分散キーＸと分散キーＹで分散した例を図１８に示す。例えば、負荷分散のために、Ｑ１とＱ２の処理にＮ台のサーバ（サーバ１〜サーバＮ）を割り当てるとする。その場合、ＸとＹの間に関係が存在していても、Ｘを使ったパーティショニング関数（ハッシュ関数）Ｆ（Ｘ）＝Ｘ％Ｎと、Ｙを使ったパーティショニング関数Ｇ（Ｙ）＝Ｙ％Ｍの結果は一致されることが保証されない。そのため、Ｑ１とＱ２を別々で分散配置する必要があり、Ｑ１からの出力イベントをＧ（Ｙ）の結果に従ってＱ２のサーバに転送する必要がある。３台のサーバでデータを分散処理する場合、サーバ間のデータ通信が生じる確率は約２／３となる。一般的にＮ台のサーバでデータを分散処理する場合、サーバ間のデータ通信が生じる確率は（Ｎ−１）／Ｎと概算できる。
【００６１】
一方、Ｘ→Ｙの関係性（Ｙ＝２＊Ｘ）を利用することで、全てのＸの値に対して一つだけのＹの値が存在することが分かるため、Ｘで分散可能なクエリＱ１はＹでも分散可能（再転送なしで処理可能）であることが分かる。その場合、２つのクエリＱ１とＱ２に対して同じ分散キーＹとパーティショニング関数を利用することで、分散時には図１９に示すようにＱ１とＱ２のクエリ処理を順次行う際のサーバ間の通信をなくすことが出来る。この例ではＱ１とＱ２に同じ分散キーとパーティション関数を適用するため、Ｑ１とＱ２の処理が１台のサーバで連続して行えることが分かって、全サーバ（Ｎ台＋Ｍ台）をＱ１とＱ２からなるクエリグループに対して割り当てることができる。また、Ｑ１の出力イベントはＱ１を処理したサーバにおいて引き続き実行するＱ２の入力イベントとなり、同一サーバでＱ１とＱ２とのクエリ処理が実行される。このため、図１８で説明したようなＱ１とＱ２の処理を行うサーバ間の通信が発生しない。
【００６２】
構文情報から分散キー間の関係性が見つからない場合は、実行時に実際に流れる分散キーの値を比較し、比較結果から関係性を見い出すことができる場合がある。実行時に見い出した関係性は完璧な関係性ではなく、例外を許すことがある。例外率（例外の発生率）が小さければ有効な関係性と見なされ、クエリグループの作成に使うことができる。例外率が大きいと、サーバ間の通信量が増え、最大スループットが低下し、クエリグループを作成した効果が得られない場合がある。
【００６３】
実行時の分散キーＡとＢの間の関係性の例外率と正常率は、図２０に示すように、クエリのデータウィンドウに保存されているイベントのＡとＢの値を見比べて、ＡとＢの各値の組合せの出現数をカウントする。各組合せのカウントした後、各Ａの値に対して、一番多く関連するＢの値を特定し、そのＢの値を「正常値」とし、その他のＢの値を「例外値」とする。
【００６４】
そして、各Ａの値に関連付けた「正常値」の合計出現数を集計し、データウィンドウに入っているイベントの数で割ることで関係性Ａ→Ｂの正常率を計算する。図２０では、Ａの値に関連付けた「正常値」の合計出現数「９」をデータウィンドウに入っているイベント数１２で割ることで、関係性Ａ→Ｂの正常率が９／１２と計算される。例外率は、（１−正常率）であり、３／１２と計算される。
【００６５】
同様に、関係性Ｂ→Ａの正常率は、各Ｂの値に対して一番多く出現するＡの出現数を合計し、データウィンドウのイベント数で割ることで計算される。また、例外率は（１−正常率）で計算される。ここでは、各Ｂの値「６」、「７」に対してそれぞれ一番多く出現するＡの出現数（３×１＋１×１）をイベント数１２で割ることで、関係性Ｂ→Ａの正常率が４／１２と計算される。例外率は、８／１２（＝１−４／１２）と計算される。
【００６６】
上記の計算はウィンドウの中身が変わるたびに行われる。このため、各組合せの出現カウンタは中間結果をメモリに保管しながら、継続的に動作する。ウィンドウにイベントが追加や削除されると、追加や削除されたイベントのＡとＢの値から関連する組合せカウンタを取得し、そのカウンタをインクリメントやデクリメントする。後で各組み合わせカウンタの状態（中間結果）が探せるように、それらの状態は一つの「カウンターテーブル」で管理される。
【００６７】
カウンターテーブルは図２０に示すように、６つの欄で構成されている。最初の２つのＫ１とＫ２は探索対象の関係性の候補を表す。例えば、Ａ→Ｂ又はＢ→Ａの関係性に関連する行にはＫ１とＫ２に"Ａ"と"Ｂ"が入る。「Ｋ１とＫ２の組合せ値」には、ウィンドウのイベントのうち、ＡとＢの値から構成される全ての組合せが１行ずつ記録される。出現数には、各組合せがウィンドウの中で出現される回数が記録される。最後の２つの組合せステートの欄には、組合せが関係性Ａ→Ｂ又はＢ→Ａにとって正常な組合せか例外な組合せであるかどうかのフラグが記録される。
【００６８】
このような完璧でない関係性に基づいてクエリグループを作って分散すると、例外イベントが間違ったサーバへ転送されるため正しいサーバへの再転送が必要となる。例外イベントが多くなるとサーバ間の再転送による通信量が大きくなるため、最大スループットがクエリグループを作らなかった構成における通信量がよりも悪くなることがある。そのため、有効な関係性であるかどうかは、クエリグループ作成後の通信量、すなわち、例外イベントの数を見積もる必要がある。関係性に基づいてクエリグループを作った構成における通信量が、クエリグループを作らない構成における通信量がよりも少なければ、有効な関係性として見なされる。クエリグループ作成後の構成における通信量がクエリグループを作らない構成における通信量よりも大きければ有効な関係性として見なされない。
【００６９】
上記の技術１と技術２を組み合わせても、ほとんどの場合、構文情報からも、実行時の各分散キーの値からもレンジクエリの分散キーと非レンジクエリの分散キーの間で有効な関係性を見つけることが出来ない。このため、全クエリを含めたクエリグループの作成によるスループット最大化が実現できない。
【００７０】
構文情報上では、レンジクエリの分散キーとなる属性には、分散の粒度の細かい座標が使われることが多い。それに対して、非レンジクエリの分散キーには粒度の大きい属性が使われることが多い。よって構文情報上ではほとんどの場合、両方のクエリの分散キーに使われる属性が異なり、非レンジクエリの分散キーとレンジクエリの分散キーとの間の有効な関係性は見つからない。例えば、レンジクエリのレンジキーが人が位置する場所のＩＤであり、非レンジクエリの分散キーが国が位置する場所のＩＤである場合、非レンジクエリの分散キーは地国の位置を示す座標であり、分散の粒度が大きい。これに対して、レンジキーは人の位置を示す座標であり、分散の粒度の小さい。このため、非レンジクエリの分散キーとレンジクエリの分散キーとの間の有効な関係性を見出すことは困難である。
【００７１】
図２１のように非レンジクエリＱ１とＱ２の分散キーは分散の粒度の大きいＩＤが使われ、非レンジクエリＱ１、Ｑ２の次に処理されるレンジクエリＱ３は分散の粒度の小さいＸが使われる場合、構文情報だけではＩＤとＸの間で有効な関係性は見つからない。このため、図２１の手順１ではＱ１とＱ２とのクエリグループを作ることはできるが、Ｑ１〜Ｑ３のクエリグループを作ることは困難である。
【００７２】
さらに、図２１の手順２では、実行時にデータストリームに流れるデータ（各分散キーの値）から、レンジクエリの分散キーと非レンジクエリの分散キーの間の動的な関係性を抽出しようとする。図２２に示すように、レンジクエリの分散キーとなる座標Ｘの分散の粒度が細かい場合、送信イベント（ＩＤ，Ｘ）のＸの値が図２２の人のオブジェクトの移動に伴いオブジェクトの位置を示す座標の値が変わり、非レンジクエリの分散キーＩＤとレンジクエリの分散キーＸとの間で関係性を見つけることが困難となる。
【００７３】
このようにして、図２１の手順１及び手順２のいずれによってもＱ１〜Ｑ３を一つのクエリグループとして構成できない場合、レンジクエリＱ３は非レンジクエリＱ１とＱ２とは別の分散キーで分散され、Ｑ２とＱ３との間においてサーバ間の通信量が増大する。例えばＱ１の入力データ量Ｎが９万個／ｓで、Ｑ１とＱ２の出力データ量がＮのまま（Ｑ１とＱ２にはフィルターリングが行われない事を想定）であれば、Ｑ２とＱ３の間で再転送不要なイベント数は（Ｎ／サーバ台数）個／ｓであり、再転送されるイベント数は（Ｎ−（Ｎ／サーバ台数））個／ｓとなる。
【００７４】
よって、図２１のように３台のサーバで分散した場合、Ｑ２とＱ３の間に転送されるデータ量（中間通信量）はＮ×２／３＝６万個／ｓとなり、出力ストリームはＮ／１００＝０．０９万個／ｓとなる。よって、全通信量（＝入力＋中間＋出力）は、約１５．０９（＝９＋６＋０．０９）万個／ｓとなる。
【００７５】
しかし、ネットワークの帯域幅Ｃが１０万個／ｓだった場合、Ｃ＜入力データＮ＋通信量（＝Ｎ×２/３）＋出力データ（＝Ｎ／１００）の条件を満たす必要があり、それを超えることは出来ない。そのため、実際のスループットＴ（入力データのうち結果出力まで処理されたデータの量）は９万個／ｓではなく、
（Ｔ＋２Ｔ／３＋Ｔ／１００＝Ｃ⇔Ｔ＝（３／５．０３）×Ｃ
の式で計算する。
【００７６】
この結果、実際の最大スループットは５．９６万個／ｓとなり、各サーバの単体性能（合計で１２万個／ｓ）が十分に生かされない。このような状況ではネットワークが圧迫されるため、出力データ量も、ネットワークの帯域幅が無限の場合を想定した値（０．０９万個/s）よりも下がり、０．００５９６万個／ｓとなる。
【００７７】
図２１のようにスループットが低下するのは、図２１の手順２で各分散キーの値から分散キー間の有効な関係性を見い出せないことが原因である。また、分散キー間の関係性が見つからないのは、図２２に示すようにレンジクエリの分散キーが移動可能なオブジェクトの座標であるため、そのオブジェクトの移動に伴ってレンジクエリの分散キーで使われる座標Ｘの値がイベントごとに変わっていくためである。図２２には３つのイベント送信時刻（ｔ＝１，２，３）での４人のオブジェクトの位置を表した座標ｘと送信されたイベントの例を示す。
【００７８】
上記のように送信されたイベントを元にした関係性の正常率と例外率を計算すると、図２３に示すように、ウィンドウの中での一つのＩＤの値に対して多数のＸの値が関連する。このため、正常率が低く、例外率が高くなり、関係性ＩＤ→Ｘを見つけることは困難となる。
【００７９】
一般的なデータストリームのプログラムでは、レンジクエリの分散キーの元になる検索式に使われる座標の分散の粒度は非常に細かい。このため、非レンジクエリの分散キーの元になるgroup byキー又はequijoinの条件式に、レンジクエリの分散キーの元になる検索式に使われる座標と同じ座標を使うことはほとんどない。このため、レンジクエリの分散キーと非レンジクエリの分散キーとの間に構文上の関係性が存在せず、構文情報に基づいてレンジクエリと非レンジクエリをまとめたクエリグループを作ることが難しい。
【００８０】
また、実行時にデータストリームに流れるデータ（各分散キーの値）から、レンジクエリの分散キーＸと非レンジクエリの分散キーＩＤの間の動的な関係性を捜しても、レンジクエリの細かな分散の粒度によって分散キーＸと分散キーＩＤとの動的な関係性を見いだせない。この結果、レンジクエリと非レンジクエリのクエリグループを作成することは困難となる。たとえ何らかの関係性を見出してレンジクエリと非レンジクエリのクエリグループを作っても、例外数の多い関係性のため、データの負荷分散処理の実行時にサーバ間で再転送すべき例外イベントが多くなり、かえってスループットが悪化してしまう可能性がある。
【００８１】
このように、上記で説明した技術１，２では、構文情報や実行時に流れるデータからレンジクエリの分散キーＸと非レンジクエリの分散キーＩＤとの間の関係性が見つけられないために有効な構成のクエリグループを作成することが難しい。この結果、データの分散時に非レンジクエリ及びレンジクエリを処理する際にサーバ間にて発生する通信量が増大し、最大スループットが低下する。
【００８２】
これに対して、以下に説明する本実施形態にかかるデータ処理方法は、座標の空間をデータの分布に応じてデータが均等に分散されるように領域を分割し、各領域に割り当てたパーティションＩＤ（以下、「ＰＩＤ」ともいう。）をレンジクエリの分散キーに用いる。ＰＩＤは座標Ｘよりも分散の粒度が大きい。これにより、非レンジクエリの分散キーとレンジクエリの分散キーの間に例外数の少ない関係性を見出すことができる。その関係性に基づいてクエリグループを作ってデータ分散することで、非レンジクエリとレンジクエリとのクエリ処理の間で例外による通信量が減り、最大スループットを向上させることができる。
【００８３】
なお、本実施形態にかかるデータ処理方法では、関係値を算出する算出モジュールをレンジクエリにも適用できるようにする。また、本実施形態のデータ処理方法による負荷分散では、レンジクエリ用と非レンジクエリ用の２つの独立したモジュールを、一つの統一したモジュールに纏めることができる。
【００８４】
［データ処理装置の機能構成及び処理の流れ］
まず、本実施形態にかかるデータ処理方法を実行するデータ処理装置１０の機能構成及び処理の流れについて、図２４及び図２５を参照しながら説明する。図２４は、本実施形態にかかるデータ処理装置１０の機能構成の一例を示す図であり、図２５は、本実施形態にかかるデータ処理装置１０による処理の流れを説明するための図である。
【００８５】
本実施形態にかかるデータ処理装置１０は、サーバ、ＰＣ等の情報処理装置により実現可能である。データ処理装置１０は、分散キー抽出部１１、データ分散部１２、クエリ処理部１３、関係性算出部１４、静的グループ化部１５ａ、動的グループ化部１５ｂ及び負荷分散部１６を有する。
【００８６】
分散キー抽出部１１は、非レンジクエリの分散キーの抽出を行う。また、分散キー抽出部１１は、レンジクエリの条件を解析し、レンジクエリの分散キーを抽出する。非レンジクエリの分散キーは、非レンジクエリの構文情報から抽出されるカテゴリの属性を示す。カテゴリの属性毎の識別値ＩＤは、非レンジクエリの分散キーの一例である。レンジクエリの分散キーは、所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を示す。所定の期間及び空間（所定区間）内の連続したデータの座標の分布に応じて分割される領域(パーティション)毎の識別値ＰＩＤは、レンジクエリの分散キーの一例である。
【００８７】
データ分散部１２は、非レンジクエリとレンジクエリのデータ分散処理を行う。関係性算出部１４は、非レンジクエリの分散キーとレンジクエリの分散キーとの関係性を示す値（以下、「関係値」ともいう。）を算出する。
【００８８】
静的グループ化部１５ａは、非レンジクエリの構文情報に基づき、非レンジクエリのグループ化を行う。動的グループ化部１５ｂは、算出した関係値に基づき、非レンジクエリとレンジクエリとをグループ化したクエリグループを生成する。
【００８９】
クエリ処理部１３は、クエリグループ毎に、非レンジクエリ及びレンジクエリのイベント毎の分散処理を行う。クエリ処理部１３は、クエリグループ毎に、第１のクエリと第２のクエリとの分散処理を行う分散処理部の一例である。
【００９０】
イベント毎の内部処理の一例としては、非レンジクエリのイベント毎の処理の一例として、図２に示す各イベントの出現数のカウント処理が挙げられる。また、レンジクエリのイベント毎の処理の一例として、図１０に示す所定のレンジ（例えば５分以内）の進行方向の４マイル以内の事故の有無及びカウント処理が挙げられる。
【００９１】
関係性算出部１４は、非レンジクエリの分散キーとレンジクエリの分散キーとの関係性を示す値を算出する。また、関係性算出部１４は、クエリグループ毎に非レンジクエリとレンジクエリクとの分散処理を行い、最大スループットの予測値を算出する。
【００９２】
負荷分散部１６は、クエリグループ毎に、レンジクエリと非レンジクエリとの分散処理を行う。また、負荷分散部１６は、負荷の高いサーバに対する負荷分散処理を実行するかを決定する。例えば、負荷分散部１６は、算出された最大スループットの予測値が現状のスループットを下回るスループットの場合には、そのレンジクエリと非レンジクエリとの分散処理を行うことを抑制する。
【００９３】
次に、データ処理装置１０の処理の流れの概要について、図２５を参照しながら簡単に説明する。分散キー抽出部１１は、非レンジクエリの分散キーを例えばgroup by句の属性から抽出する。静的グループ化部１５ａは、非レンジクエリの構文情報に基づいて非レンジクエリに対するクエリグループの最適化を行う。また、分散キー抽出部１１は、レンジクエリの条件解析を行い、レンジクエリの分散キーを抽出する。これらの処理はコンパイラにより行われる静的な処理である。次に、データ処理装置１０のエンジンにより実行される動的な処理について説明する。
【００９４】
データ処理装置１０のエンジンは、各種テーブルが初期化された後、次の処理を順に行う。まず、データ分散部１２は、非レンジクエリとレンジクエリのデータ分散処理を行う。次に、クエリ処理部１３は、クエリグループ毎に、非レンジクエリ及びレンジクエリのイベント毎の内部処理（分散処理）を行う。次に、関係性算出部１４は、非レンジクエリで使用される分散キー（ＩＤ）とレンジクエリの分散キーで使用されるパーティションＩＤ（ＰＩＤ）との関係性を示す値を算出する。
【００９５】
次に、動的グループ化部１５ｂは、算出した関係性を示す値に基づき、非レンジクエリとレンジクエリとをグループ化したクエリグループを生成する。その際、動的グループ化部１５ｂは、非レンジクエリとレンジクエリとを組み合わせた、複数のクエリのグループ化を行う。グループ化の際、非レンジクエリ及びレンジクエリの各クエリの組み合わせからなる多数のクエリグループ構成の候補から、非レンジクエリ及びレンジクエリにとって最適なクエリグループ構成を選択する。
【００９６】
次に、負荷分散部１６は、クエリグループ毎に、非レンジクエリとレンジクエリとの分散処理を行う。その際、負荷分散部１６は、負荷状況と関係性の例外率との両方に基づき予測される最大スループットに基づき、クエリグループ毎に、非レンジクエリとレンジクエリとの分散処理を実行するかを決定する。
【００９７】
［各種データ］
次に、本実施形態にかかるデータ処理方法に使用される各種データについて説明する。（組合せカウンターテーブル）
図２６は、データ分散処理の実行時に関係性の例外率を計算する場合の組合せカウンターテーブルを示す。図２６（ａ）は、分散キー同士のカウンタを管理する組合せカウンターテーブルを示す。図２６（ｂ）は、本実施形態において分散キーとパーティションＩＤ同士のカウンタを管理するように変更する組合せカウンターテーブルを示す。本実施形態では、Ｋ２の分散キーＸにパーティションＩＤ（ＰＩＤ（Ｘ））を適用する。
【００９８】
（パーティションテーブル）
負荷分散が行われた結果は、パーティションテーブルに反映される。図２７（ｂ）は、本実施形態のレンジクエリのためのパーティションテーブルの一例を示す。レンジクエリの場合、各パーティションには各領域のデータが属し、その領域はrange startとrange endの欄で定義されている。負荷分散のためにデータの負荷が高い一つの領域が複数の領域に分けられるとテーブル上のパーティションも２つに分けられる。countには各パーティションに属するイベント数が記録される。各領域には各パーティションを識別するパーティションＩＤ（ＰＩＤ）がつけられている。本実施形態では、各パーティションに一対一にサーバが割り当てられている。パーティションテーブルには、サーバＩＤで識別される各サーバのサーバ負荷が示される。レンジクエリの場合、領域の境界に近い座標にデータが存在する場合、二つ以上の領域に跨ったレンジクエリになることがあり、このときサーバ間に通信が生じる。
【００９９】
図２７（ｂ）の本実施形態のパーティションテーブルは、図２７（ａ）で示すレンジクエリのパーティションテーブルにクエリグループの作成に使われている関係性（例：ＩＤ→Ｘ）の例外率の欄を追加する。追加した関係性の例外率の欄には、パーティションＩＤ（ＰＩＤ（Ｘ））を使って計算した例外率が記録される。
【０１００】
（関係性テーブル）
図２８（ｂ）に示す本実施形態の関係性テーブルには、図２８（ａ）に対して分散キーを正しく設定し、データ分散処理の実行時にＸではなくＰＩＤ（Ｘ）を使って分散するようにその旨を明示するフラグ欄を追加する。Ｋ２にＰＩＤを適用するかのフラグの値が０のときはＫ２にＰＩＤを適用しないことを意味する。フラグの値が１のときはＫ２にＰＩＤを適用することを意味する。
【０１０１】
（分散キーテーブル）
図２９（ｂ）に示す本実施形態の分散キーテーブルには、図２９（ａ）に対して、正しくキー分散とレンジ分散を切り分けられるようにレンジ分散を行うかどうかのフラグ（レンジフラグ）が追加されている。レンジフラグの値が「０」のときはキー分散が行われる。レンジフラグの値が「１」のときはレンジ分散が行われる。
【０１０２】
［関係値算出処理］
次に、本実施形態に係るデータ処理方法のうち、関係値の算出方法について図３１を参照して説明する。図３１は、一実施形態にかかる関係値算出処理の一例を示す。図３０は、図３１の関係値算出処理に対する比較例を示す。
【０１０３】
図３０の比較例にかかる関係値算出処理では、各分散キーＡ，Ｂとデータの座標Ｘとの関係性の例外率を計算する。座標Ｘの分散の粒度が小さいため、ＡとＸ、ＢとＸとの関係性を見つけることができず、関係性テーブルに示すように、Ａ→ｘでグルーピングし、Ｂ→ｘでグルーピングしたときの例外率が高くなっている。
【０１０４】
一方、図３１の本実施形態にかかる関係値算出処理では、各分散キーＡ，Ｂとデータの座標Ｘが含まれるパーティションＩＤ（ＰＩＤ（Ｘ））との関係性の例外率を以下のように計算する。
【０１０５】
各パーティションへ転送されるイベントから、分散キーＡ，Ｂの値を参照し、参照した値と転送されたパーティションＩＤからなるカップルのカウンタをインクリメントする。パーティションＩＤ毎に例外率の値を集計し、最後に全体の例外率の集計を行う。そして、パーティションＩＤ毎に集計した例外率をパーティションテーブルに反映する。
【０１０６】
パーティションＩＤの分散の粒度は、座標Ｘの分散の粒度よりも大きい。このため、ＡとＰＩＤ（Ｘ）との関係性及びＢとＰＩＤ（Ｘ）との関係性を見つけることができ、関係性テーブルに示すように、Ａ→ＰＩＤ（Ｘ）でグルーピングし、Ｂ→ＰＩＤ（Ｘ）でグルーピングしたときの例外率は、Ａ→ｘでグルーピングし、Ｂ→ｘでグルーピングしたときの例外率よりも低くなっている。
【０１０７】
［クエリグループ最適化］
次に、関係性に基づいた非レンジクエリとレンジクエリのためのクエリグループ最適化について、図３２を参照しながら説明する。１方向（例えば、図１６のオブジェクト（車）の矢印で示す方向）のレンジクエリによる通信量［１］は、例えば以下の式（１）のように、レンジクエリの検索幅Ｌ、分散の粒度Ｇ、及びレンジクエリの入力データ量Ｖ（個／Ｓ）により算出できる。
【０１０８】
通信量［１］＝（Ｌ／Ｇ）×Ｖ・・・・・（１）
２方向のレンジクエリによる通信量［１］は、以下の式（２）のように算出できる。
【０１０９】
通信量［１］＝２×（Ｌ／Ｇ）×Ｖ・・・・・（２）
式（１）及び式（２）は、図１６に示した通信量の式に基づく。分散の粒度Ｇが小さいと通信量が増えることがわかる。上記の式（１）及び式（２）では、検索幅内のデータ分布が均一である場合には、正確な通信量を計算することが可能である。検索幅内のデータ分布が不均一であった場合は、分布を考慮した別の式で計算しても良い。
【０１１０】
関係性に基づいてクエリグループを作り適用した場合の、関係性の例外率による通信量［２］は、以下の式（３）に示すように、例外率Ｅと関係性が使われるストリームでの入力データ量Ｖにより算出することができる。
【０１１１】
通信量［２］＝Ｅ×Ｖ・・・・・（３）
上記の２つの通信量を足し合わせた結果に基づき関係性に基づいたクエリグループ構成を作成後の最大スループットは、以下の性能情報を使って算出することが可能である。
・ネットワークの帯域幅Ｃ（個／ｓ）
・サーバ一台当たりの単体性能ｐ（個／ｓ）
（データ分散法に従って全クエリが全ノード上のサーバに動作した場合、つまり、クエリ分散はしない場合を想定）
・サーバ台数Ｎ
・各関係性の例外率Ｅ（％）
・各ストリーム上のデータ量Ｖｉ（個／ｓ）
例えば、各ストリーム上のデータ量Ｖｉ（個／ｓ）としては、入力ストリームのデータ量（入力データ量）Ｖ１、中間ストリームのデータ量（中間データ量）Ｖ２、Ｖ３、出力ストリームのデータ量（出力データ量）Ｖ４が挙げられる。
【０１１２】
再分散による通信量の計算は、そのストリームにおけるデータ量（Ｖ）を"サーバ台数−１"で割ることで計算できる。
【０１１３】
通信量［３］＝Ｖ／（Ｎ−１）・・・・・（４）
再分散は、グルーピングした構成の関係性に対して所定以上の例外率が生じ、グルーピングが最適でない場合に行われる。
【０１１４】
最大スループットは、性能のボトルネックが発生した時の入力ストリームのデータ量で決まるため、ボトルネックが発生する条件を予測することで算出できる。性能ボトルネックは入力データ量が各サーバの単体性能を超えたときか、全体通信量がネットワークの帯域幅を超えたときに発生する。このため、その２つの条件を引き起こす入力データ量を求めたうちの最小値が最大スループットの予測値となる。例えば図２１に示されたプログラムと性能情報の場合、以下の式（７）での入力データ量Ｖ１を求めると最大スループットが分かる。
【０１１５】
ここで、ネットワークのボトルネックの予測値を示す入力データ量をＶ１'で示し、Ｎ台のサーバの単体性能のボトルネックの予測値を示す入力データ量をＶ１''で示すと、入力データ量Ｖ１'は以下の式（５）で算出される。また、入力データ量Ｖ１'' は以下の式（６）で算出される。
【０１１６】
Ｖ１'＋Ｖ３×Ｅ＋Ｖ４＝Ｃ、つまり、
Ｖ１'＝Ｃ−Ｖ３×Ｅ−Ｖ４・・・・・・・・（５）（ネットワークボトルネックの予測値）
Ｖ１''＝ｐ×Ｎ・・・・・・・・・・・・・（６）（単体性能ボトルネックの予測値）
入力データ量Ｖ１＝ｍｉｎ（Ｖ１'，Ｖ１''）・・（７）（最小値）
図３２では、各クエリの関係性を用いたクエリグループ構成を仮に作成し、式（１）〜式（７）に基づき、そのクエリグループ構成に対する最大スループットを予測する。最大スループットは、複数の仮作成したクエリグループ構成に対して行われる（図３２の各関係性におけるループ処理）。
【０１１７】
例えば、関係性を使った新しいクエリグループ構成の中で、スループットが最大になるクエリグループ構成Ａとその最大スループットＴ１とが取得される。最大スループットＴ１が現状の最大スループットＴ２（クエリグループ構成Ｂのときのスループット）よりも大きい場合、クエリグループ構成Ａに置き換えられ、それ以外の場合、現状のクエリグループ構成Ｂのままとする。
【０１１８】
つまり、ネットワークのボトルネックとサーバ負荷のボトルネックとをそれぞれ求め、それぞれの最大スループットを計算し、今の最大スループットよりも低下する場合には現状のクエリグループの構成のままにする。
【０１１９】
例えば、図３３は、レンジクエリの分散キーをデータの座標Ｘに設定した場合における最大スループットの計算による予測の一例である。図３４は、本実施形態における最大スループットの計算、つまり、レンジクエリの分散キーをパーティションＩＤ（ＰＩＤ（Ｘ））に設定した場合の最大スループットの計算による予測の一例であり、図３３と比較して説明する。ここで、計算に用いる各値は以下の通りである。
・ネットワークの帯域幅Ｃ＝１０万個／ｓ
・サーバ台数  ３台
・サーバ一台当たりの単体性能ｐ＝４万個／ｓ（全体性能Ｐ＝１２万個／ｓ）
・理想性能  ｍｉｎ（Ｐ，Ｃ）＝１０万個／ｓ
・入力データ量  Ｖ１＝９万個／ｓ
・中間データ量  Ｖ２＝Ｖ３＝Ｖ１＝９万個／ｓ
・レンジクエリにおける通信量  Ｖ４＝Ｖ２／１０００＝０．００９万個／ｓ
・出力データ量  Ｖ５＝Ｖ３／１００＝０．０９万個／ｓ
図３３及び図３４では、Ｑ１及びＱ２は非レンジクエリであり、Ｑ３はレンジクエリである。図３３の比較例では、３台のサーバでデータを分散処理する場合、サーバ間のデータ通信が生じる確率は、２／３となる。よって、レンジクエリＱ３へのデータ分散時に発生する通信量は、Ｖ３'×２／３＝６万個／ｓとなる。
【０１２０】
よって、データ処理に必要な通信量は、Ｖ１＋Ｖ３'＋Ｖ４＋Ｖ５＝１５．０９９＞Ｃとなり、ネットワークの帯域幅Ｃを超えた通信量が発生するため、ネットワークのボトルネックが発生する。
【０１２１】
ネットワークの帯域幅の上限による最大スループットは、以下のように算出できる。
【０１２２】
通信量Ｖ１＋Ｖ３'＋Ｖ４＋Ｖ５＝Ｃ
Ｖ３'＝Ｖ１×２／３、Ｖ４＝Ｖ１／１０００、Ｖ５＝Ｖ１／１００
これを解くと、Ｖ１＝Ｃ×３０００／５０３３＝５．９６万個／ｓ
つまり、ネットワークの帯域幅Ｃ＝１０万個／ｓのときに処理可能な入力データ量は、５．９６万個／ｓであることが算出される。また、このときの出力データ量は、Ｖ５＝５．９６／１００＝０．０５９６万個／ｓとなる。
【０１２３】
一方、図３４に示す本実施形態にかかるデータ分散処理の場合、サーバの単体性能と関係性の例外率とに基づき、最大スループットが予測される。レンジクエリＱ３へのデータ分散時に発生する通信量は、Ｖ３''＝Ｖ３×Ｅ（例外率＝０．１％）＝０．００９万個／ｓとなる。
【０１２４】
よって、本実施形態にかかるデータ処理に必要な通信量は、Ｖ１＋Ｖ３''＋Ｖ４＋Ｖ５＝９．１０８＜Ｃとなり、ネットワークの帯域幅Ｃ内の通信量となる。このときの最大スループットは、以下のように算出できる。
【０１２５】
通信量Ｖ１＋Ｖ３''＋Ｖ４＋Ｖ５＝Ｃ
Ｖ３''＝Ｖ１×２／１０００、Ｖ４＝Ｖ１／１０００、Ｖ５＝Ｖ１／１００
これを解くと、Ｖ１＝Ｃ×１０００／１０１２＝９．８８万個／ｓ
つまり、ネットワークの帯域幅Ｃ＝１０万個／ｓのときに処理可能な入力データ量は、９．８８万個／ｓであることが算出される。また、このときの出力データ量は、Ｖ５＝５．９６／１００＝０．０９８８万個／ｓとなる。
【０１２６】
以上から、本実施形態のように、レンジクエリの分散キーをパーティションＩＤ（ＰＩＤ（Ｘ））に設定した場合の最大スループットは、レンジクエリの分散キーをデータの座標Ｘに設定した場合の最大スループットと比較して飛躍的に高くできると予測される。
【０１２７】
［例外率の具体的算出方法］
データを負荷分散したときの例外率は、現状の例外率に基づき算出することで予測可能である。例えば、パーティションのレンジ幅を半分にした場合、サーバの負荷は半分になるが、例外率は２倍になる。以下では、データ分散処理（図３５）、レンジクエリの負荷分散処理（図３７）、例外率の計算（図３８）と例外率の削減（図３９）について説明する。
【０１２８】
図３５は、データ分散部１２が実行するデータ分散処理の一例を示す。データ分散処理では、入力ストリームのデータを分散するために、処理すべき各クエリの分散キーの情報から当該クエリがレンジクエリであるかどうかが確認され、クエリの性質に合わせたデータ分散方法が適用される。データ分散部１２は、図２９（ｂ）に示す分散キーテーブルの分散キーのレンジフラグが１の場合、レンジクエリであると判定する。その場合、分散キーの値と図２７（ｂ）に示すパーティションテーブルから、行先のパーティションとそのパーティションを割り当てられているサーバが特定され、そのサーバへデータが転送される。レンジクエリでない場合、分散キーの値をパーティション関数にかけることで行先のパーティション（ＰＩＤ）が特定される。ＰＩＤとパーティションテーブルを使って行先のサーバが特定され、そのサーバへデータが転送される。
【０１２９】
図３６は、比較例におけるレンジクエリの負荷分散処理の一例を示し、図３７は、負荷分散部１６が実行するレンジクエリの負荷分散処理の一例を示す。本実施形態では、負荷状況と関係性の例外率の両方に応じた負荷分散が実行される。
【０１３０】
図３６の比較例では、あるサーバの負荷が特定の閾値を超えたら、サーバが追加され、追加したサーバにより処理の負荷分散が実行される。図３７の本実施形態では、負荷分散を実施する前に、サーバを追加して負荷分散した後の関係性による例外率が予め算出される。そして、サーバの単体性能と予測した例外率とに基づき、負荷分散後の通信量及び最大スループットが予測される。予測した最大スループットが現状のスループットより低ければ負荷分散は実施しない。
【０１３１】
関係性の例外率の計算では、まず、図３８の上段に示すように、サーバの負荷が高いパーティションを図３８の下段に示すように２つに分ける。パーティションに分けた一方のデータは既存のサーバに割り当てられ、他方のデータは新しく追加したサーバに割り当てられる。その条件で現状のパーティションテーブルの情報とパーティションに保存されているデータとに基づき統計的な計算によって関係性の例外率が求められる。新しいパーティションのrange minとrange maxの欄は現状のレンジに入っているデータの分布を見て、分散後の２つのパーティションに入るデータ量が均一になるように設定する。こうして新しく作る２つのパーティションのサーバ負荷は、現状の半分と設定する。関係性の例外率は、range minとrange maxから定まれたレンジ幅を元に、例えば以下の式から算出される。
【０１３２】
分散後の例外率＝分散前の例外率×（分散前のレンジ幅／分散後のレンジ幅）
上記の計算式は、次の特定的な推定に基づいている。一つのパーティションのレンジ幅を半分にすれば、一つのＰＩＤに該当するｘ値の数は半分に減り、その結果、一つのＡの値がウィンドウ内で同じＰＩＤと該当する可能性が半分に減る。図３７は、その現象を表す具体例の一つを示す。サーバを追加することで、９０％のサーバの負荷が４５％の負荷になっている。なお、データの分布に応じて、他の推定に基づいて分散後の例外率を計算してもよい。
【０１３３】
図３８の上段に示すように、データを２台のサーバで負荷分散した場合、Ａ→Ｂ'の例外率は２／１０となる。ここで、サーバを追加することで一つのパーティションのレンジ幅は半分になり、一つのＰＩＤに該当するｘ値の数は半分に減り、その結果一つのＡの値がウィンドウ内で同じＰＩＤと該当する可能性が半分に減る。その結果、Ａ→Ｂ'の例外率は４／１０となる。
【０１３４】
［効果の例］
次に、非レンジクエリの分散キーとレンジクエリの分散キー（パーティションＩＤ）の両方に基づいた関係性抽出の効果の一例について説明する。図４０は、本実施形態にかかるクエリグループ作成による最大スループットの改善の一例を示す。
【０１３５】
上記に説明したように、本実施形態にかかるデータ処理方法では、非レンジクエリの分散キーとレンジクエリの分散キーであるパーティションＩＤの両方に基づいて非レンジクエリとレンジクエリとの関係性が抽出される。本実施形態は、図３９に示すようにパーティションＩＤを用いて、非レンジクエリの分散キーＩＤとレンジクエリの分散キーＰＩＤ（ｘ）との組合せ毎に出現数がカウントされる。これにより、図２３に示した非レンジクエリの分散キーＩＤとレンジクエリの分散キーｘとの組合せ毎に出現数をカウントしたときの例外率と比較して、探索対象の関係性の例外率を減らすことができる。
【０１３６】
レンジクエリの分散粒度がある程度大きければ大きいほど、関係性の例外率ＩＤ→Ｘの例外率が下がって、最大スループットへの影響が小さくなる。例えば、図４０のように３台サーバの構成で例外率が０．１％まで下がると想定すれば、通信量がほとんど増えないまま、最大スループットを高めることが出来る。非レンジクエリの分散キーＩＤとレンジクエリの分散キーｘとの組合せ毎に出現数をカウントしたときには最大スループットが５．９６万個／ｓまで低下する（図２１参照）。これに対して、本実施形態の最大スループットは９．９万個／ｓとなり、ハードウェア性能（１０万個／ｓ）に近づけることができる。
【０１３７】
図４０に示す本実施形態にかかるデータ分散処理の場合、サーバの単体性能と関係性の例外率に基づき、最大スループットが予測される。レンジクエリＱ３へのデータ分散時に発生する通信量は、Ｖ３×Ｅ（例外率＝０．１％）＝０．００９万個／ｓとなる。
【０１３８】
よって、本実施形態にかかるデータ処理に必要な通信量は、Ｖ１＋Ｖ３＋Ｖ４＋Ｖ５＝９．１０８＜Ｃとなり、ネットワークの帯域幅Ｃ内の通信量となる。このときの最大スループットは、以下のように算出できる。
【０１３９】
合計通信量＝Ｖ１（９万個／ｓ）＋Ｖ４（０．００９万個／ｓ）＋Ｖ５（０．０９万個／ｓ）＝９．０９９万個／ｓ＜Ｃ
最大スループット＝９．８９万個／ｓとなる。
【０１４０】
［変形例］
次に、本実施形態の変形例にかかるデータ処理方法について説明する。関係性の例外による通信量が多くて、式（７）で計算した予想の最大スループットがクエリグループの現状構成のときの最大スループットよりも低くなる場合が生じる。その場合、関係性を使った新しいクエリグループを作らないで、現状のクエリグループ構成のままにすることが好ましい。
【０１４１】
例えば、図４１に示すように対象のオブジェクトが高速に移動した場合、図４２に示すように関係性の例外率は高まる。上記のように関係性の例外率が高まった場合、式（１）〜式（７）で通信量と最大スループットが計算される。
【０１４２】
レンジクエリＱ３へのデータ分散時に発生する通信量は、Ｖ３''＝Ｖ３×Ｅ（例外率＝０．７％）＝６．３万個／ｓとなる。
【０１４３】
よって、本実施形態にかかるデータ処理に必要な通信量は、Ｖ１＋Ｖ３''＋Ｖ４＋Ｖ５＝１５．３９９＞Ｃとなり、ネットワークの帯域幅Ｃを超えた通信量が発生するため、ネットワークのボトルネックが発生する。このときの最大スループットは、以下のように算出できる。
【０１４４】
通信量Ｖ１＋Ｖ３''＋Ｖ４＋Ｖ５＝Ｃ
Ｖ３''＝Ｖ１×０．７、Ｖ４＝Ｖ１／１０００、Ｖ５＝Ｖ１／１００
これを解くと、最大の処理可能な入力データ量Ｖ１＝Ｃ／（１＋０．７＋０．００１＋０．０１）＝５．８４万個／ｓ、出力データ量Ｖ５＝Ｖ１／１００＝０．０５８４万個／ｓ
つまり、予測した最大スループットは、０．０５８４万個/となり、図３１の最大スループット０．０５９９万個/sを下回る。よって、この場合、負荷分散部１６は、現状のクエリグループ構成から新しい関係性に基づいた分散後のクエリグループ構成の作成は行わないで、現状のクエリグループ構成のままで運用を続けるように判定する。なお、判定処理そのものは図３０のフローチャートに従い実行される。
【０１４５】
本実施形態では、図４０のようにレンジクエリと非レンジクエリをクエリグループでまとめてrange(X)で分散した場合、図１４に示すように、サーバ負荷の上昇に応じてレンジ幅を適正化し、負荷分散を行う必要がある。その場合、図１４に示す技術を適用することで、サーバを追加して負荷分散を行うことができる。しかし、このように負荷分散を行うことでクエリグループに使っていた分散キー間の関係性の例外率が上がる場合があり、負荷分散後の最大スループットが負荷分散前の最大スループットよりも下がることがある。
【０１４６】
例えば、図４４の負荷分散前のパーティションテーブルに示すように、負荷分散前の状態では３台のサーバの構成で関係性の例外率は全サーバで２５％の状態であった場合を想定する。負荷が高いサーバ１の負荷分散を行った場合、負荷分散後のパーティションテーブルに示すように、負荷分散後にサーバ１とサーバ４のパーティションにおける関係性の例外率は２倍の増加で５０％まで上がる。
【０１４７】
本実施形態及び本変形例では、図３０の関係値算出処理を用いて、関係性算出部１４が、実際に負荷分散を行う前に、負荷分散を行った場合の各パーティションにおける例外率とそれに伴う通信量の予測値を算出する。これにより、負荷分散後の最大スループットを予測することが可能となる。その結果、本変形例では、予測した最大スループットが現状の最大スループットより低ければ、負荷分散を行わないように抑制することができる。
【０１４８】
図４５は、本変形例にかかる負荷分散処理の抑制の一例を示す。この例では、サーバ４を追加してサーバ１の負荷をサーバ１及びサーバ４に分散させた場合、関係性算出部１４により、合計通信量Ｍが１１万個／ｓとなり、予測最大スループットが７．２７万個／ｓと予測された。これは、現状の最大スループットである８万個／ｓよりも低下した値である。このため、サーバ１の処理をサーバ１及びサーバ４に負荷分散させる構成を採用せず、負荷分散を行うことを抑制した例である。
【０１４９】
以上、本実施形態及び本変形例にかかるデータ処理方法によれば、非レンジクエリとレンジクエリとを連続して処理する際のサーバ間の通信量の低減によるスループットの向上を図ることができる。
【０１５０】
また、例外率が高くなるとスループットが下がる。特に、パーティションＩＤが小さくなると例外率が高くなり、スループットが下がる。よって、例外率が高くなり、最大スループットが今より低くなることが予測される場合にはサーバの追加による負荷分散を行わないことでスループットの低下を抑止することでができる。
【０１５１】
（ハードウェア構成例）
最後に、本実施形態に係るデータ処理装置１０のハードウェア構成例について、図４６を参照して説明する。図４６は、本一実施形態にかかるデータ処理装置１０のハードウェア構成の一例を示す。
【０１５２】
データ処理装置１０は、入力装置１０１、表示装置１０２、外部Ｉ／Ｆ１０３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１０４、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１０５、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０６、通信Ｉ／Ｆ１０７、及びＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）１０８などを備え、それぞれがバスＢで相互に接続されている。
【０１５３】
入力装置１０１は、キーボードやマウスなどを含み、データ処理装置１０に各操作信号を入力するのに用いられる。表示装置１０２は、ディスプレイなどを含み、各種の処理結果を表示する。
【０１５４】
通信Ｉ／Ｆ１０７は、データ処理装置１０をネットワークに接続するインタフェースであり、データ処理装置１０は、通信Ｉ／Ｆ１０７を介して、他の機器とデータ通信を行うことができる。
【０１５５】
ＨＤＤ１０８は、プログラムやデータを格納している不揮発性の記憶装置である。格納されるプログラムやデータには、装置全体を制御する基本ソフトウェア及びアプリケーションソフトウェアがある。例えば、ＨＤＤ１０８には、各種のＤＢ情報やプログラム等が格納されている。
【０１５６】
外部Ｉ／Ｆ１０３は、外部装置とのインタフェースである。外部装置には、記録媒体１０３ａなどがある。これにより、データ処理装置１０は、外部Ｉ／Ｆ１０３を介して記録媒体１０３ａの読み取り及び／又は書き込みを行うことができる。記録媒体１０３ａには、フロッピー（商標又は登録商標）ディスク、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）、及びＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、ならびに、ＳＤメモリカード（ＳＤ  Ｍｅｍｏｒｙ  ｃａｒｄ）やＵＳＢメモリ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ  ｍｅｍｏｒｙ）などがある。
【０１５７】
ＲＯＭ１０５は、電源を切っても内部データを保持することができる不揮発性の半導体メモリ（記憶装置）である。ＲＯＭ１０５には、ネットワーク設定などのプログラムやデータが格納されている。ＲＡＭ１０４は、プログラムやデータを一時保持する揮発性の半導体メモリ（記憶装置）である。ＣＰＵ１０６は、上記記憶装置（例えば「ＨＤＤ１０８」や「ＲＯＭ１０５」など）から、プログラムやデータをＲＡＭ１０４上に読み出し、処理を実行することで、装置全体の制御や搭載機能を実現する演算装置である。
【０１５８】
上記ハードウェア構成により、本実施形態に係るデータ処理方法、データ処理プログラム及びデータ処理装置は、ストリームデータの分散処理を行うことができる。例えば、ＣＰＵ１０６が、ＲＯＭ１０５やＨＤＤ１０８内に格納されたデータ及びプログラムを用いてクエリ処理及び最大ブループットを算出するための処理を実行する。
【０１５９】
図２６の組合せカウンターテーブル、図２７のパーティションテーブル、図２８の関係性テーブル、図２９の分散キーテーブルは、ＲＡＭ１０４やＨＤＤ１０８に記憶されてもよいし、クラウドコンピュータ上の記憶領域に記憶されてもよい。
【０１６０】
以上、データ処理方法、データ処理プログラム及びデータ処理装置を上記実施形態により説明したが、本発明にかかるデータ処理方法、データ処理プログラム及びデータ処理装置は上記実施形態に限定されるものではなく、本発明の範囲内で種々の変形及び改良が可能である。また、上記実施形態及び変形例が複数存在する場合、矛盾しない範囲で組み合わせることができる。
【０１６１】
例えば、上記ではパーティションＩＤとサーバとは一対一として説明したが、パーティションＩＤとサーバとは必ずしも一対一でなくてもよい。
【０１６２】
以上の説明に関し、更に以下の項を開示する。
（付記１）
順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリと、前記複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリと、をコンピュータが実行するデータ処理方法であって、
前記第１のクエリの構文情報から抽出されるカテゴリの属性を特定する前記第１の分散キーと、前記所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する前記第２の分散キーとの関係性を示す値を算出し、
前記算出した関係性を示す値に基づき、前記第１のクエリと前記第２のクエリとをグループ化したクエリグループを生成し、
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行う、
手順を含む、データ処理方法。
（付記２）
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行ったときのスループットの予測値を算出し、
前記スループットの予測値に基づき、前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行うことを抑制する、
手順を含む、付記１に記載のデータ処理方法。
（付記３）
順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリと、前記複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリと、をコンピュータに実行させるデータ処理プログラムであって、
前記第１のクエリの構文情報から抽出されるカテゴリの属性を特定する前記第１の分散キーと、前記所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する前記第２の分散キーとの関係性を示す値を算出し、
前記算出した関係性を示す値に基づき、前記第１のクエリと前記第２のクエリとをグループ化したクエリグループを生成し、
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行う、
手順を含む、データ処理プログラム。
（付記４）
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行ったときのスループットの予測値を算出し、
前記スループットの予測値に基づき、前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行うことを抑制する、
手順を含む、付記３に記載のデータ処理プログラム。
（付記５）
順次入力する複数のデータに対して第１の分散キーに基づき分散処理する第１のクエリと、前記複数のデータのうちの所定の区間内の連続したデータに対して第２の分散キーに基づき分散処理する第２のクエリと、を実行するデータ処理装置であって、
前記第１のクエリの構文情報から抽出されるカテゴリの属性を特定する前記第１の分散キーと、前記所定の区間内の連続したデータの座標の分布に応じて分割される領域の属性を特定する前記第２の分散キーとの関係性を示す値を算出する関係性算出部と、
前記算出した関係性を示す値に基づき、前記第１のクエリと前記第２のクエリとをグループ化したクエリグループを生成するクエリグループ化部と、
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行う分散処理部と、
を有するデータ処理装置。
（付記６）
前記関係性算出部は、
前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行ったときのスループットの予測値を算出し、
前記スループットの予測値に基づき、前記クエリグループ毎に、前記第１のクエリと前記第２のクエリとの分散処理を行うことを抑制する負荷分散部を有する、
付記５に記載のデータ処理装置。
【符号の説明】
【０１６３】
１０：データ処理装置
１１：分散キー抽出部
１２：データ分散部
１３：クエリ処理部
１４：関係値算出部
１５ａ：静的グループ化部
１５ｂ：動的グループ化部
１６：負荷分散部
【図１】
0006442951.tif 000002
【図２】
0006442951.tif 000003
【図３】
0006442951.tif 000004
【図４】
0006442951.tif 000005
【図５】
0006442951.tif 000006
【図６】
0006442951.tif 000007
【図７】
0006442951.tif 000008
【図８】
0006442951.tif 000009
【図９】
0006442951.tif 000010
【図１０】
0006442951.tif 000011
【図１１】
0006442951.tif 000012
【図１２】
0006442951.tif 000013
【図１３】
0006442951.tif 000014
【図１４】
0006442951.tif 000015
【図１５】
0006442951.tif 000016
【図１６】
0006442951.tif 000017
【図１７】
0006442951.tif 000018
【図１８】
0006442951.tif 000019
【図１９】
0006442951.tif 000020
【図２０】
0006442951.tif 000021
【図２１】
0006442951.tif 000022
【図２２】
0006442951.tif 000023
【図２３】
0006442951.tif 000024
【図２４】
0006442951.tif 000025
【図２５】
0006442951.tif 000026
【図２６】
0006442951.tif 000027
【図２７】
0006442951.tif 000028
【図２８】
0006442951.tif 000029
【図２９】
0006442951.tif 000030
【図３０】
0006442951.tif 000031
【図３１】
0006442951.tif 000032
【図３２】
0006442951.tif 000033
【図３３】
0006442951.tif 000034
【図３４】
0006442951.tif 000035
【図３５】
0006442951.tif 000036
【図３６】
0006442951.tif 000037
【図３７】
0006442951.tif 000038
【図３８】
0006442951.tif 000039
【図３９】
0006442951.tif 000040
【図４０】
0006442951.tif 000041
【図４１】
0006442951.tif 000042
【図４２】
0006442951.tif 000043
【図４３】
0006442951.tif 000044
【図４４】
0006442951.tif 000045
【図４５】
0006442951.tif 000046
【図４６】
0006442951.tif 000047