(57)【要約】  キー及びデータ値から構成されるデータを複数含むデータセットに対する分析処理を複数の計算機が並列実行する計算機システムであって、各計算機は、所定のキー範囲毎に前記データセットを分割した分割領域の分割位置を示すキーである分割位置キーを管理する分割情報をデータセット毎に保持し、各データセットの分割情報に含まれるすべての分割位置キーは同一であり、計算機システムは、ファイルシステムに新規データセットが格納された場合に、新規データセットが格納された後の各分割領域のデータサイズに基づいて、所定の閾値より大きいデータサイズの分割領域である対象領域が存在するか否かを判定し、対象領域が存在すると判定された場合、対象領域を複数の新たな分割領域に分割する。
2012131927.tif 000002
【特許請求の範囲】
【請求項１】
キー及びデータ値から構成されるデータを複数含むデータセットに対する分析処理を複数の計算機が並列実行する計算機システムであって、
前記各計算機は、プロセッサと、前記プロセッサに接続されるメモリと、前記のプロセッサに接続される記憶装置と、前記プロセッサに接続されるネットワークインタフェースとを有し、
前記各計算機は、所定のキー範囲毎に前記データセットを分割した分割領域の分割位置を示すキーである分割位置キーを管理する分割情報を、前記データセット毎に保持し、
前記各データセットの前記分割情報に含まれるすべての前記分割位置キーは同一であり、
前記複数の計算機が有する記憶領域上には、前記データセットを格納するファイルシステムが構成され、
前記計算機システムは、
前記分析処理を実行する場合に、前記分割領域毎に複数のタスクを生成し、
前記生成されたタスクを前記各計算機に割り当てて、前記各データセットの分割領域に含まれる前記データを結合して前記分析処理を実行し、
前記ファイルシステムに新規データセットが格納された場合に、前記新規データセットが格納された後の各分割領域のデータサイズに基づいて、所定の閾値より大きいデータサイズの前記分割領域である対象領域が存在するか否かを判定し、
前記対象領域が存在すると判定された場合、前記対象領域を複数の新たな分割領域に分割することを特徴とする計算機システム。
【請求項２】
前記ファイルシステムに新規データセットを格納する場合に、前記新規データセットのキー分布を解析し、
前記解析結果に基づいて、既存の前記データセットの分割情報に含まれるすべての前記分割位置キーと同一となるように、前記新規データセットの前記分割情報を生成することを特徴とする請求項１に記載の計算機システム。
【請求項３】
前記対象領域が分割された後に、前記既存のデータセットの分割情報における前記分割位置キーを更新することを特徴とする請求項２に記載の計算機システム。
【請求項４】
前記対象領域が存在するか否かを判定する場合に、すべての前記データセットの前記分割領域のデータサイズを合計して、前記計算機システムにおける前記分割領域のデータサイズである第１のデータサイズを算出し、
前記算出された第１のデータサイズが、前記所定の閾値より大きい前記分割領域が存在するか否か判定し、
前記対象領域を分割する場合に、前記すべてのデータセットの前記対象領域のデータサイズを合計することによって、前記計算機システムにおける前記対象領域のデータサイズである第２のデータサイズを算出し、
前記所定の閾値、及び前記算出された第２のデータサイズに基づいて、前記対象領域の分割数を算出し、
前記算出された分割数に基づいて、前記対象領域における新たな分割位置キーを決定し、
前記既存のデータセットの分割情報の前記分割位置キーを更新する場合に、前記既存のデータセットの分割情報から、前記対象領域に対応する情報を削除し、前記決定された分割位置キーと前記新たな分割領域とを対応づけた情報を追加し、
前記新データセットの分割情報を生成する場合に、前記更新された既存のデータセットの分割情報における前記分割キーと同一となるように前記新規データセットの分割情報を生成することを特徴とする請求項３に記載の計算機システム。
【請求項５】
前記対象領域を分割する場合に、前記対象領域のデータサイズを前記算出された分割数で除算して第３のデータサイズを算出し、
前記算出された第３のデータサイズに対応する前記データにおける前記キーを、前記分割位置キーとして決定することを特徴とする請求項４に記載の計算機システム。
【請求項６】
前記所定の閾値は、前記新たな分割領域が割り当てられるタスクの処理時間が予め設定された許容時間以下となるデータサイズであることを特徴とする請求項４に記載の計算機システム。
【請求項７】
前記データは、複数の項目毎のデータ値を含み、
前記第１のデータサイズを算出する場合に、前記分割領域における全ての項目のデータサイズを合計することによって、前記第１のデータサイズを算出することを特徴とする請求項４に記載の計算機システム。
【請求項８】
前記新規データセットのキー分布を解析する場合に、前記既存のデータセットの分割情報に含まれる前記分割位置キーのいずれかに一致する分割位置キーで前記新規データセットを分割して複数の処理用分割領域を生成し、
前記生成された処理用分割領域毎に、前記新規データセットのキー分布を解析するためのタスクを生成して、当該タスクを並列に実行することを特徴とする請求項２に記載の計算機システム。
【請求項９】
キー及びデータ値から構成されるデータを複数含むデータセットに対する分析処理を複数の計算機が並列実行する計算機システムにおけるデータ管理方法であって、
前記各計算機は、プロセッサと、前記プロセッサに接続されるメモリと、前記プロセッサに接続される記憶装置と、前記プロセッサに接続されるネットワークインタフェースとを有し、
前記各計算機は、所定のキー範囲毎に当該データセットを分割した分割領域の分割位置を示すキーである分割位置キーを管理する分割情報を、前記データセット毎に保持し、
前記各データセットの前記分割情報に含まれる全てのすべての前記分割位置キーは同一であり、
前記複数の計算機が有する記憶領域上には、前記データセットを格納するファイルシステムが構成され、
前記方法は、
少なくとも一つの前記計算機が、前記分析処理を実行する場合に、前記分割領域毎に複数のタスクを生成する第１のステップと、
前記タスクを生成した前記計算機が、前記生成されたタスクを前記各計算機に割り当てて、前記各データセットの分割領域に含まれる前記データを結合して前記分析処理を実行させる第２のステップと、を含み、
少なくとも一つの前記計算機が、前記ファイルシステムに新規データセットが格納された場合に、前記新規データセットが格納された後の各分割領域のデータサイズに基づいて、所定の閾値より大きいデータサイズの前記分割領域である対象領域が存在するか否かを判定する第３のステップと、
前述した判定処理を実行した前記計算機が、前記対象領域が存在すると判定された場合、前記対象領域を複数の新たな分割領域に分割する第４のステップと、
を含むことを特徴とするデータ管理方法。
【請求項１０】
前記第３のステップは、
前記新規データセットのキー分布を解析する第５のステップと、
前記解析結果に基づいて、既存の前記データセットの分割情報に含まれるすべての前記分割位置キーと同一となるように、前記新規データセットの前記分割情報を生成する第６のステップと、を含むことを特徴とする請求項９に記載のデータ管理方法。
【請求項１１】
前記第４のステップは、前記対象領域が分割された後に、前記既存のデータセットの分割情報における前記分割位置キーを更新する第７のステップを含むことを特徴とする請求項１０に記載のデータ管理方法。
【請求項１２】
前記第３のステップは、
すべての前記データセットの前記分割領域のデータサイズを合計して、前記計算機システムにおける前記分割領域のデータサイズである第１のデータサイズを算出する第８のステップと、
前記算出された第１のデータサイズが、前記所定の閾値より大きい前記分割領域が存在するか否か判定する第９のステップと、を含み、
前記第４のステップは、
前記すべてのデータセットの前記対象領域のデータサイズを合計することによって、前記計算機システムにおける前記対象領域のデータサイズである第２のデータサイズを算出する第１０のステップと、
前記所定の閾値、及び前記算出された第２のデータサイズに基づいて、前記対象領域の分割数を算出する第１１のステップと、
前記算出された分割数に基づいて、前記対象領域における新たな分割位置キーを決定する第１２のステップと、を含み、
前記第７のステップは、前記既存のデータセットの分割情報から、前記対象領域に対応する情報を削除し、前記決定された分割位置キーと前記新たな分割領域とを対応づけた情報を追加する第１３のステップを含み、
前記第６のステップは、前記更新された既存のデータセットの分割情報における前記分割キーと同一となるように前記新規データセットの分割情報を生成する第１４のステップを含むことを特徴とする請求項１１に記載のデータ管理方法。
【請求項１３】
前記第１２のステップは、
前記対象領域のデータサイズを前記算出された分割数で除算して第３のデータサイズを算出するステップと、
前記算出された第３のデータサイズに対応する前記データにおける前記キーを、前記分割位置キーとして決定するステップと、を含むことを特徴とする請求項１２に記載のデータ管理方法。
【請求項１４】
前記所定の閾値は、前記新たな分割領域が割り当てられるタスクの処理時間が予め設定された許容時間以下となるデータサイズであることを特徴とする請求項１２に記載のデータ管理方法。
【請求項１５】
前記データは、複数の項目毎のデータ値を含み、
前記第８のステップでは、前記分割領域における全ての項目のデータサイズを合計することによって、前記第１のデータサイズを算出することを特徴とする請求項１２に記載のデータ管理方法。
【請求項１６】
前記第５のステップは、
前記既存のデータセットの分割情報に含まれる前記分割位置キーのいずれかに一致する分割位置キーで前記新規データセットを分割して複数の処理用分割領域を生成するステップと、
前記生成された処理用分割領域毎に、前記新規データセットのキー分布を解析するためのタスクを生成して、当該タスクを前記各計算機上で並列に実行させるステップと、を含むことを特徴とする請求項１０に記載のデータ管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量データを処理する計算機システムにおいて、データを結合する技術に関わる。
【背景技術】
【０００２】
データベースにおける表（テーブル、リレーション等）の結合処理に関する技術として、ソート・マージ結合技術を用いて表の結合を並列処理する手法が知られている（例えば、特許文献１参照）。【０００３】
ソート・マージ結合技術とは、結合対象の表をキー値に基づいてソートした後、各表の行を先頭から読み出し、対応するキー値である行同士をマージする手法である。【０００４】
特許文献１には、処理を並列化するために、各表を同一のキー値に対応する位置で区分することによって表毎に対応する分割領域を生成し、分割領域毎にソート・マージ結合技術を利用して表を結合することが記載されている。さらに、特許文献１には、システム内のプロセッサ負荷に偏りが発生しないように、プロセッサへの分割領域の割り当てることが記載されている。【０００５】
データベースに関する基本的な技術として、キーの値と当該キーの値に対応するデータの格納位置を対応付けるテーブル（インデックス）を用意しておき、データの検索処理時に、キーの値を指定することによって高速にデータを取得する技術がある（例えば、特許文献２参照）。特許文献２では、２つ以上のキーの組み合わせに対して、データの格納位置を対応付けるマトリックス・インデックスについて記載されている。【０００６】
また、キーの値の範囲毎にデータを保存する格納領域を変更することによって、複数の格納領域を利用可能とする技術が一般的に利用されている（例えば、特許文献３参照）。特許文献３では、格納領域を追加するとき、既存の格納領域から新たに追加した格納領域へのデータの移動量を抑えつつ、各格納領域の使用量を平準化する方法について説明されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特公平７−１１１７１８
【特許文献２】特開平６−５２２３１号公報
【特許文献３】特開２００１−１４２７５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
データ分析システムでは、周期的に取得されたデータを蓄積し、必要に応じて蓄積されたデータを組み合わせて分析処理を実行する。【０００９】
ここで、図を用いてデータ分析システムによって処理されるデータの一例を示す。【００１０】
図２０は、従来のデータ分析システムにおいて処理されるデータの一例を示す説明図である。図２１は、従来のデータにおけるスキーマの一例を示す説明図である。図２２Ａから図２２Ｃは、従来の分析処理において処理されるデータの一例を示す説明図である。【００１１】
図２０に示す例では、ユーザの移動履歴を表す。具体的には、ユーザを識別するユーザＩＤ、ユーザの位置を特定する座標情報である位置Ｘ及び位置Ｙ、並びに、ユーザが当該位置に移動した時間であるタイムスタンプから構成されるデータである。【００１２】
図２０に示すようなデータに対する分析処理では、例えば、図２１に示すようにスキーマに基づいてデータが変換される。さらに、変換されたデータは、図２２Ａに示すようにユーザＩＤ毎にグループ化され、集計等の分析処理が実行される。【００１３】
しかし、分析処理時に図２０に示すようなデータを図２２Ａに示すようなデータに変換する処理に時間がかかるため、本データ分析システムでは、分析処理を効率化するため、予め図２２Ａに示すようなデータに変換されたデータが蓄積され、蓄積されたデータを用いて分析処理が実行される。【００１４】
なお、本明細書では、１以上レコードから構成されるデータをデータセットと記載する。また、図２０に示すようなデータセットを素データと記載し、図２１に示すような構造のデータを構造化データと記載する。【００１５】
蓄積処理では、図２０に示す形式のデータが周期的（例えば月単位）に収集され、図２２Ａの形式のデータに変換された後、データ分析システムに蓄積される。このため、複数のデータを集計して、１年間のデータに対する分析処理、及び各年度の特定の月に対する分析処理を実行する場合には、図２２Ａに示す形式のデータを複数結合する必要がある。【００１６】
例えば、データ分析システムは、図２２Ａ及び図２２Ｂに示すような２つデータを結合して、図２２Ｃに示すようなデータになる。【００１７】
ここで、同一のユーザＩＤの行データ（レコード）をマージしていることから、データベースにおける結合（ジョイン）と同等の処理を行う必要がある。さらに、前述した例では結合対象となるデータは２つだけではなく、多数の表を結合する場合がある。【００１８】
また、周期的に蓄積されるデータは、データ毎にサイズ分布が異なる場合がある。例えば、月ごとのサービスの利用回数が異なるユーザのデータでは、各月のデータのサイズ分布の違いが発生する。【００１９】
特許文献１には、表を区分するときに区分する位置（分割位置）を決定する方法は記載されていない。一般に表を均等に区分するには表に含まれるキーの分布情報が必要になる。キーの分布情報を取得する場合に、表全体をスキャンする方法では処理完了までに時間がかかる。【００２０】
キーの分布情報を取得する他の方法としては、特許文献２に記載されたインデックスを用いる方法がある。インデックスは表には、すべてのキー値が含まれるため、インデックスをスキャンすることによってキーの分布情報を取得することができる。インデックスは表と比べてデータサイズが小さいため、処理時間を短くできる。【００２１】
しかし、多数の表を結合する場合には、表の数だけインデックスをスキャンする必要があり、処理時間が長くなる。また、対象とするデータが大量である場合、表の作成時にインデックスを作成する処理、及び、表の更新時にインデックスを更新する処理に時間がかかるという課題がある。【００２２】
これに対して、インデックスを利用せず、特許文献３に記載の方法を用いることが考えられる。すなわち、あらかじめ複数の分割領域に分割された表を管理しておき、各表の分割領域同士を対応させて、分割領域毎に並列にマージ結合処理を実行する方法を用いることが考えられる。【００２３】
しかし、一般に表の分割位置は表毎に異なるため、分割領域を対応させることができない。たとえ、すべての表の分割位置が一致するようにしていてもデータ更新時に各分割領域にデータサイズの偏りが発生するという別の課題がある。【００２４】
すなわち、周期的に蓄積されるデータ毎にデータサイズ分布が異なるため、予め固定された分割位置では、データの組み合わせによって各分割領域のデータサイズに偏りが発生する。したがって、並列して結合処理を実行する場合に処理量のばらつきが発生し、効率的に並列処理ができないという課題がある。
【課題を解決するための手段】
【００２５】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、キー及びデータ値から構成されるデータを複数含むデータセットに対する分析処理を複数の計算機が並列実行する計算機システムであって、前記各計算機は、プロセッサと、前記プロセッサに接続されるメモリと、前記のプロセッサに接続される記憶装置と、前記プロセッサに接続されるネットワークインタフェースとを有し、前記各計算機は、所定のキー範囲毎に前記データセットを分割した分割領域の分割位置を示すキーである分割位置キーを管理する分割情報を、前記データセット毎に保持し、前記各データセットの前記分割情報に含まれるすべての前記分割位置キーは同一であり、前記複数の計算機が有する記憶領域上には、前記データセットを格納するファイルシステムが構成され、前記計算機システムは、前記分析処理を実行する場合に、前記分割領域毎に複数のタスクを生成し、前記生成されたタスクを前記各計算機に割り当てて、前記各データセットの分割領域に含まれる前記データを結合して前記分析処理を実行し、前記ファイルシステムに新規データセットが格納された場合に、前記新規データセットが格納された後の各分割領域のデータサイズに基づいて、所定の閾値より大きいデータサイズの前記分割領域である対象領域が存在するか否かを判定し、前記対象領域が存在すると判定された場合、前記対象領域を複数の新たな分割領域に分割することを特徴とする。
【発明の効果】
【００２６】
本発明の代表的な一形態によれば、インデックスを作成することなく、データセット間の結合処理を並列実行できる。また、新規データセットが追加された場合に、分割領域ごとのデータ量のばらつきを抑えることができるため結合処理を実行するタスク間の処理量の平準化できる。
【図面の簡単な説明】
【００２７】
【図１】本発明の第１の実施形態におけるデータ分析システムのシステム構成を説明するブロック図である。
【図２】本発明の第１の実施形態におけるノードのハードウェア構成を説明するブロック図である。
【図３Ａ】本発明の第１の実施形態におけるマスタノードのソフトウェア構成を説明するブロック図である。
【図３Ｂ】本発明の第１の実施形態におけるスレーブノードのソフトウェア構成を説明するブロック図である。
【図４】本発明の第１の実施形態におけるデータ管理テーブルの一例を示す説明図である。
【図５Ａ】本発明の第１の実施形態における分割テーブルの一例を示す説明図である。
【図５Ｂ】本発明の第１の実施形態における分割テーブルの一例を示す説明図である。
【図６】本発明の第１の実施形態におけるパーティションテーブルの一例を示す説明図である。
【図７Ａ】本発明の第１の実施形態におけるにキーサイズテーブルの一例を示す説明図である。
【図７Ｂ】本発明の第１の実施形態におけるにキーサイズテーブルの一例を示す説明図である。
【図８】本発明の第１の実施形態におけるデータの結合処理及び分析処理を説明するフローチャートである。
【図９】本発明の第１の実施形態におけるデータ追加処理を説明するフローチャートである。
【図１０】本発明の第１の実施形態におけるグルーピング処理の詳細を説明するフローチャートである。
【図１１】本発明の第１の実施形態におけるデータ出力処理を説明するフローチャートである。
【図１２】本発明の第１の実施形態のおけるデータサイズの確認処理を説明するフローチャートである。
【図１３】本発明の第１の実施形態におけるにキーサイズテーブルの一例を示す説明図である。
【図１４Ａ】本発明の第１の実施形態における分割後の分割テーブルの一例を示す説明図である。
【図１４Ｂ】本発明の第１の実施形態における分割後の分割テーブルの一例を示す説明図である。
【図１５】本発明の第１の実施形態におけるに分割後のキーサイズテーブルの一例を示す説明図である。
【図１６】本発明の第２の実施形態におけるレコードのスキーマを示す説明図である。
【図１７】本発明の第２の実施形態におけるレコードの一例を示す説明図である。
【図１８Ａ】本発明の第２の実施形態におけるファイルを示す説明図である。
【図１８Ｂ】本発明の第２の実施形態におけるファイルを示す説明図である。
【図１８Ｃ】本発明の第２の実施形態におけるファイルを示す説明図である。
【図１９】本発明の第２の実施形態における分割テーブルの一例を示す説明図である。
【図２０】従来のデータ分析システムにおいて処理されるデータの一例を示す説明図である。
【図２１】従来のデータにおけるスキーマの一例を示す説明図である。
【図２２Ａ】従来の分析処理おいて処理されるデータの一例を示す説明図である。
【図２２Ｂ】従来の分析処理おいて処理されるデータの一例を示す説明図である。
【図２２Ｃ】従来の分析処理おいて処理されるデータの一例を示す説明図である。
【発明を実施するための形態】
【００２８】
［第１の実施形態］
【００２９】
以下、本発明の第１の実施形態を説明する。
【００３０】
図１は、本発明の第１の実施形態におけるデータ分析システムのシステム構成を説明するブロック図である。
【００３１】
データ分析システムは、クライアントノード１０、マスタノード２０及びスレーブノード３０から構成され、ネットワーク４０を介して各ノードが相互に接続される。なお、ネットワーク４０は、ＳＡＮ、ＬＡＮ及びＷＡＮなどが考えられるが、各ノードが通信できるものであればどのようなものであってもよい。また、各ノードが直接接続されてもよい。
【００３２】
ここでノードとは計算機を示す。以降、計算機をノードと記載する。
【００３３】
クライアントノード１０は、データ分析システムの利用者が利用するノードである。利用者は、クライアントノード１０を用いてマスタノード２０及びスレーブノード３０等に各種指示を送信する。
【００３４】
マスタノード２０は、データ分析システム全体を管理するノードである。スレーブノード３０は、マスタノード２０から送信される指示にしたがって、各処理（タスク）を実行するノードである。なお、本データ分析システムは、並列分散処理システムの一種であり、スレーブノード３０の数を増やすことによって、システムの処理性能を向上することができる。
【００３５】
なお、クライアントノード１０、マスタノード２０及びスレーブノード３０のハードウェア構成は同一のものであり、詳細については図２を用いて後述する。
【００３６】
各ノードには、ＨＤＤ等の記憶装置１１、２１、３１が接続される。各記憶装置１１、２１、３１には、ＯＳ等の各ノードが備える機能を実現するためのプログラムが格納される。各プログラムは、ＣＰＵ（図２参照）によって記憶装置１１、２１、３１から読み出され、ＣＰＵ（図２参照）によって実行される。
【００３７】
図２は、本発明の第１の実施形態におけるノードのハードウェア構成を説明するブロック図である。
【００３８】
図２ではクライアントノード１０を例に説明するが、マスタノード２０及びスレーブノード３０も同一のハードウェア構成である。
【００３９】
クライアントノード１０は、ＣＰＵ１０１、ネットワークＩ／Ｆ１０２、入出力Ｉ／Ｆ１０３、メモリ１０４、及びディスクＩ／Ｆ１０５を備え、内部バス等を介して各構成が互いに接続される。
【００４０】
ＣＰＵ１０１は、メモリ１０４に格納されるプログラムを実行する。
【００４１】
メモリ１０４は、ＣＰＵ１０１によって実行されるプログラム及び当該プログラムを実行するために必要な情報を格納する。なお、メモリ１０４に格納されるプログラムは、記憶装置１１に格納されていてもよい。この場合、ＣＰＵ１０１によって、記憶装置１１からメモリ１０４上に読み出される。
【００４２】
ネットワークＩ／Ｆ１０２は、ネットワーク４０を介して他のノードと接続するためのインタフェースである。ディスクＩ／Ｆ１０５は、記憶装置１１と接続するためのインタフェースである。
【００４３】
入出力Ｉ／Ｆ１０３は、キーボード１０６、マウス１０７及びディスプレイ１０８などの入出力装置を接続するためのインタフェースである。利用者は、入出力装置を用いてデータ分析システムに指示を送信し、また、分析結果を確認する。
【００４４】
なお、マスタノード２０及びスレーブノード３０は、キーボード１０６、マウス１０７及びディスプレイ１０８を備えていなくてもよい。
【００４５】
次に、マスタノード２０及びスレーブノード３０のソフトウェア構成を説明する。
【００４６】
図３Ａは、本発明の第１の実施形態におけるマスタノード２０のソフトウェア構成を説明するブロック図である。
【００４７】
マスタノード２０は、データ管理部２１、処理管理部２２及びファイルサーバ（マスタ）２３を備える。
【００４８】
データ管理部２１、処理管理部２２及びファイルサーバ（マスタ）２３は、メモリ１０４上に格納されるプログラムであり、ＣＰＵ１０１によって実行される。以下、プログラムを主体として処理を説明する場合には、ＣＰＵ１０１によって当該プログラムが実行されているものとする。
【００４９】
データ管理部２１は、データ分析システムが処理するデータを管理する。データ管理部２１は、データ管理テーブルＴ１００、分割テーブルＴ２００及びキーサイズテーブルＴ４００を含む。
【００５０】
データ管理テーブルＴ１００は、データ分析システムが処理するデータセットの管理情報を格納する。データ管理テーブルＴ１００の詳細については、図４を用いて後述する。ここで、データセットとは、複数のレコードから構成されるデータを示す。
【００５１】
分割テーブルＴ２００は、データセットを分割した分割領域の管理情報を格納する。ここで分割領域とは、所定のキー範囲ごとにデータセットが分割されたレコード群を表す。分割テーブルＴ２００の詳細については、図５を用いて後述する。
【００５２】
キーサイズテーブルＴ４００は、データセットにおける各分割領域のデータサイズの管理情報を格納する。一つのデータセットに対して一つのキーサイズテーブルＴ４００が対応する。また、データ分析システム全体のデータセットのデータサイズを管理するキーサイズテーブルＴ４００も含まれる。キーサイズテーブルＴ４００の詳細については、図７を用いて後述する。
【００５３】
処理管理部２２は、各スレーブノード３０上で分散して実行される並列処理を管理する。処理管理部２２は、並列実行される処理（タスク）を生成するプログラムを管理するプログラムリポジトリ２４を含む。つまり、処理管理部２２は、プログラムリポジトリ２４から各スレーブノード３０において実行すべきタスクを生成し、生成されたタスクの実行をスレーブノード３０に指示する。
【００５４】
ファイルサーバ（マスタ）２３は、実際のデータを格納するファイルを管理する。
【００５５】
なお、マスタノード２０が備えるソフトウェア構成は、ハードウェアを用いて実現してもよい。
【００５６】
図３Ｂは、本発明の第１の実施形態におけるスレーブノード３０のソフトウェア構成を説明するブロック図である。
【００５７】
スレーブノード３０は、処理実行部３１及びファイルサーバ（スレーブ）３２を備える。
【００５８】
処理実行部３１及びファイルサーバ（スレーブ）３２は、メモリ１０４上に格納されるプログラムであり、ＣＰＵ１０１によって実行される。以下、プログラムを主体として処理を説明する場合には、ＣＰＵ１０１によって当該プログラムが実行されているものとする。
【００５９】
処理実行部３１は、マスタノード２０の処理管理部２２から処理（タスク）の実行指示を受け付け、所定の処理（タスク）を実行する。つまり、処理実行部３１は、受け付けた処理（タスク）の実行指示に基づいて、当該処理（タスク）を実行するためのプロセスを生成する。生成されたプロセスが実行されることによって、各スレーブノード３０上で複数のタスクが実行され、並列分散処理が実現される。
【００６０】
本実施形態の処理実行部３１は、前述したタスクを実行するデータ追加部（Ｍａｐ）３３及びデータ追加部（Ｒｅｄｕｃｅ）３４を含む。
【００６１】
データ追加部（Ｍａｐ）３３は、入力された素データ（図２０参照）からレコード単位のデータを読み出し、ｋｅｙ範囲毎にデータ追加部（Ｒｅｄｕｃｅ）３４に、読み出された素データを出力する。なお、データ追加部（Ｒｅｄｕｃｅ）３４は、処理を担当するｋｅｙ範囲が予め設定されている。
【００６２】
データ追加部（Ｍａｐ）３３は、パーティションテーブルＴ３００を含む。データ追加部（Ｍａｐ）３３は、パーティションテーブルＴ３００に基づいて、読み出されたデータを出力するデータ追加部（Ｒｅｄｕｃｅ）３４を特定する。なお、パーティションテーブルＴ３００については、図７Ａ及び図７Ｂを用いて後述する。
【００６３】
データ追加部（Ｒｅｄｕｃｅ）３４は、入力された素データを所定の形式、すなわち、構造化データ（図２１参照）に変換し、さらに、当該構造化データを分散ファイルシステムに出力する。
【００６４】
データ追加部（Ｒｅｄｕｃｅ）３４は、キーサイズテーブルＴ４００を含む。キーサイズテーブルＴ４００は、データ管理部２１に含まれるキーサイズテーブルＴ４００と同一のものである。ただし、キーサイズテーブルＴ４００には、データ追加部（Ｒｅｄｕｃｅ）３４が担当するｋｅｙ範囲の分割領域に関する管理情報のみが格納される。
【００６５】
ファイルサーバ（スレーブ）３２は、分散配置されるファイルを管理する。ファイルサーバ（マスタ）２３は、ファイルのメタデータ（ディレクトリ構造、サイズ、更新日時等）を管理し、ファイルサーバ（スレーブ）３２と連携して一つのファイルシステムを提供する機能を備える。
【００６６】
データ追加部（Ｍａｐ）３３及びデータ追加部（Ｒｅｄｕｃｅ）３４は、ファイルサーバ（マスタ）２３にアクセスすることによって、ファイルシステム上のファイルを利用し、各種タスクを実行する。すなわち、データ追加部（Ｍａｐ）３３及びデータ追加部（Ｒｅｄｕｃｅ）３４は、同一のファイルシステムにアクセスすることができる。
【００６７】
なお、スレーブノード３０が備えるソフトウェア構成は、ハードウェアを用いて実現してもよい。
【００６８】
次にデータ管理部２１に含まれる各テーブルの詳細について説明する。
【００６９】
図４は、本発明の第１の実施形態におけるデータ管理テーブルＴ１００の一例を示す説明図である。
【００７０】
データ管理テーブルＴ１００は、データＩＤ（Ｔ１０１）及び分割テーブル名Ｔ１０２を含む。データＩＤ（Ｔ１０１）は、データセットの識別子を格納する。分割テーブル名Ｔ１０２は、データセットに対応する分割テーブルＴ２００の名称を格納する。
【００７１】
データ管理テーブルＴ１００の各エントリは、本データ分析システムが管理する１つのデータセットに対応する。また、当該データセットは、通常のデータベースにおける１つのテーブル（リレーション）に対応する。
【００７２】
図５Ａ及び図５Ｂは、本発明の第１の実施形態における分割テーブルＴ２００の一例を示す説明図である。
【００７３】
図５Ａは、分割テーブル名Ｔ１０２が「ｌｏｇ０１．ｐａｒｔ」であるデータセットの分割テーブルＴ２００の一例を示す。図５Ｂは、分割テーブル名Ｔ１０２が「ｌｏｇ０２．ｐａｒｔ」である分割テーブルＴ２００の一例を示す。
【００７４】
分割テーブルＴ２００は、本データ分析システムが処理する各データセットの分割方法を示す管理情報を格納する。分割テーブルＴ２００は、分割テーブル名Ｔ２０１、データファイル名Ｔ２０２、ｋｅｙ（Ｔ２０３）及びオフセットＴ２０４を含む。
【００７５】
分割テーブル名Ｔ２０１は、分割テーブルＴ２００の名称を格納する。分割テーブル名Ｔ２０１は、分割テーブル名Ｔ１０２と同一のものである。
【００７６】
データファイル名Ｔ２０２は、分割領域に対応するデータを格納するファイルの名称を格納する。
【００７７】
ｋｅｙ（Ｔ２０３）は、分割領域のｋｅｙ範囲を示すｋｅｙの値、すなわち、データセットの分割位置を表すｋｅｙの値を格納する。ｋｅｙ（Ｔ２０３）には、分割領域における終了地点を表すｋｅｙの値が格納される。
【００７８】
オフセットＴ２０４は、データセットにおける分割位置の値に対応するオフセットを格納する。オフセットＴ２０４には、ｋｅｙ（Ｔ２０３）に対応するｋｅｙのオフセットが格納される。なお、データファイル名Ｔ２０２が異なる場合には、データが格納されるファイルが異なるため、対応するエントリのオフセットは「０」から改めてカウントされる。
【００７９】
分割領域の開始位置は、１つ前のエントリのｋｅｙ（Ｔ２０３）及びオフセットＴ２０４に対応する。そして、最初の分割領域の開始位置を表すｋｅｙと、最後の分割領域の終了位置を表すｋｅｙは定義されないため、これらは分割テーブルＴ２００には記載されない。
【００８０】
各分割テーブルＴ２００の各エントリは、本データ分析システムが管理する１つの分割領域に対応する。
【００８１】
例えば、図４に示すデータ管理テーブルＴ１００の１つ目のエントリは、分割テーブル名Ｔ１０１が「ｌｏｇ０１．ｐａｒｔ」であり、図５Ａに示す分割テーブルＴ２００に対応する。
【００８２】
図５Ａに示す分割テーブルＴ２００の１つ目のエントリが最初の分割領域に対応する。１つ目のエントリは、データファイル名Ｔ２０２が「ｌｏｇ０１／００１．ｄａｔ」であるファイルに、当該分割領域のデータが格納されていることを示す。
【００８３】
また、１つ目のエントリのｋｅｙ（Ｔ２０３）が「０３４ａ」であることから、最初の分割領域のｋｅｙ範囲は「０３４ａ」未満であることを示す。また、１つ目のエントリのオフセットＴ２０４が「２８０」であることから、ファイル上のオフセットが「０〜２７９」の範囲に最初の分割領域のデータが格納されていることを示す。
【００８４】
また、図５Ａに示す分割テーブルＴ２００の２つ目のエントリは、対応する分割領域のｋｅｙ範囲は「０３４ａ」以上かつ「１７２ｄ」未満であり、データファイル名Ｔ２０２が「ｌｏｇ０１／００２．ｄａｔ」であることを示す。また、データファイル名Ｔ２０２が１つ目のエントリと異なるため、オフセットは「０」からカウントされる。したがって、オフセットが「０〜２１８」の範囲に対応する分割領域のデータが格納されることを示す。
【００８５】
また、図５Ａに示す分割テーブルＴ２００の３つ目のエントリは、対応する分割領域のｋｅｙ範囲は「１７２ｄ」以上かつ「３２８ｂ」未満であり、データファイル名Ｔ２０２が「ｌｏｇ０１／００２．ｄａｔ」であることを示す。また、データファイル名Ｔ２０２が２つ目のエントリと一致するため、ファイル上のオフセットが「２１９〜４５５」の範囲に対応する分割領域のデータが格納されることを示す。
【００８６】
また、図４に示すデータ管理テーブルＴ１００の２つ目のエントリは、分割テーブル名Ｔ１０１が「ｌｏｇ０２．ｐａｒｔ」であり、図５Ｂに示す分割テーブルＴ２００に対応する。
【００８７】
図５Ｂに示す分割テーブルＴ２００に格納される各エントリのデータファイル名Ｔ２０２及びオフセットＴ２０４は、図５Ａに示す分割テーブルＴ２００の各エントリと異なる。しかし、両分割テーブルＴ２００の分割位置を表すｋｅｙ（Ｔ２０３）は共に一致する。
【００８８】
本実施形態では、結合する可能性があるデータセットにおける分割領域の分割位置、すなわち、ｋｅｙ（Ｔ２０３）は必ず一致するように管理される。これによって、２つ以上のデータセットの結合処理を並列化することができる。すなわち、結合対象となるデータセットの分割テーブルＴ２００のｋｅｙ（Ｔ２０３）が同一のエントリを対応付けることが可能となり、分割領域毎に結合処理を並列して実行することが可能となる。
【００８９】
ファイルには、図２２Ａに示したように１つのｋｅｙと１つ以上の値とから構成されるレコードが複数含まれる。また、各ファイルは、ｋｅｙに基づいてソートされた形式で、分散ファイルシステムに格納される。これによって、分割領域毎に結合処理を行う場合に、同一のｋｅｙをつき合わせてマージ結合することが可能となる。
【００９０】
また、異なる分割領域のデータを格納するファイルは同一であってもよい。例えば、図５Ａでは、２つ目のエントリと３つ目のエントリとは、同一のファイルである。ただし、それぞれのエントリのｋｅｙ範囲が異なっている。
【００９１】
前述のように図５Ａでは、ファイルの数は３つであるが、分割領域の数は４つであり、それぞれ異なる。後述するように、ファイルの数は、本データ分析システムにおけるデータ追加処理の並列度に一致する。一方、分割領域の数は、データの分析処理の並列度に依存する。したがって、ファイルの数と分割領域の数とは、それぞれ異なった処理に依存するため、両者には依存関係はなく、どのように決めてもよい。
【００９２】
図６は、本発明の第１の実施形態におけるパーティションテーブルＴ３００の一例を示す説明図である。
【００９３】
パーティションテーブルＴ３００は、新たに追加されるデータセット（素データ）を分割して、タスクを実行するデータ追加部（Ｒｅｄｕｃｅ）３４に、当該データを振り分ける際に用いられる情報を格納する。パーティションテーブルＴ３００は、ｋｅｙ（Ｔ３０１）及び宛先Ｔ３０２を含む。
【００９４】
ｋｅｙ（Ｔ３０１）は、入力されたデータセットの分割位置を表すｋｅｙの値を格納する。宛先Ｔ３０２は、分割されたデータセットの処理を担当するデータ追加部（Ｒｅｄｕｃｅ）３４の位置を示す宛先情報を格納する。図６に示す例では、ＩＰアドレス及びポートを含む宛先情報によってノード及び当該データ追加部（Ｒｅｄｕｃｅ）３４が指定される。
【００９５】
図７Ａ及び図７Ｂは、本発明の第１の実施形態におけるにキーサイズテーブルＴ４００の一例を示す説明図である。
【００９６】
キーサイズテーブルＴ４００は、分割領域のデータサイズを格納する。キーサイズテーブルＴ４００は、ｋｅｙ（Ｔ４０１）及びサイズＴ４０２を含む。
【００９７】
ｋｅｙ（Ｔ４０１）は、ｋｅｙ（Ｔ２０３）と同一のものである。サイズＴ４０２は、ｋｅｙ（Ｔ４０１）を分割位置とする分割領域のデータサイズを格納する。
【００９８】
なお、サイズＴ４０２は、結合処理の対象となる分割領域のデータサイズの合計値が格納される。
【００９９】
キーサイズテーブルＴ４００は、後述する結合処理及び分析処理、並びに、データ追加処理の実行時に動的に生成される。
【０１００】
次に、データの結合処理及び分析処理について説明する。
【０１０１】
図８は、本発明の第１の実施形態におけるデータの結合処理及び分析処理を説明するフローチャートである。
【０１０２】
結合処理は、必ず分析処理と共に実行される。すなわち、結合処理によって１レコード分のデータが結合された後、当該データに対して分析処理が実行される。
【０１０３】
結合処理及び分析処理は、利用者からの指示を受信したデータ管理部２１によって実行される。なお、利用者からの指示には、結合対象であるデータセットのデータＩＤが含まれる。
【０１０４】
まず、マスタノード２０は、処理対象となるデータセットに対応するキーサイズテーブルＴ４００を作成する（ステップＳ１０１）。
【０１０５】
具体的には、以下のような処理が実行される。
【０１０６】
データ管理部２１は、利用者から送信された指示に含まれるデータＩＤに基づいて、データ管理テーブルＴ１００を検索し、対応するエントリから分割テーブル名Ｔ１０２を取得する。
【０１０７】
次に、データ管理部２１は、取得された分割テーブル名Ｔ１０２に対応する分割テーブルＴ２００を取得する。
【０１０８】
データ管理部２１は、取得された分割テーブルＴ２００に基づいて、分割領域毎の分割位置を示すｋｅｙの値を特定し、また、結合対象であるデータセットのデータサイズを算出する。
【０１０９】
さらに、データ管理部２１は、前述の処理結果に基づいて、キーサイズテーブルＴ４００を作成する。
【０１１０】
例えば、データＩＤ（Ｔ１０１）が「ｌｏｇ０１」及び「ｌｏｇ０２」であるデータセットを結合する場合、対応する分割テーブルＴ２００はそれぞれ図５Ａ及び図５Ｂとなる。このとき、データ管理部２１は、前述した処理を実行することによって、分割領域毎に２つのデータセットのデータサイズを足し合わせ、図７Ａに示すようなキーサイズテーブルＴ４００を作成する。
【０１１１】
次に、マスタノード２０は、結合処理及び分析処理の組からなるタスクを複数生成し、生成された各タスクを各スレーブノード３０に割り当てることによって当該タスクを起動する（ステップＳ１０２）。
【０１１２】
具体的には、処理管理部２２が、プログラムリポジトリ２４から処理に必要なプログラムを読み出し、利用者によって指定された並列数分のタスクを生成する。さらに、処理管理部２２が、生成されたタスクを各スレーブノード３０上で実行させる。
【０１１３】
なお、当該並列数がステップＳ１０１において作成されたキーサイズテーブルＴ４００のエントリ数よりも小さい場合、当該エントリ数を並列数とし、エントリ数分のタスクをスレーブノード３０上で実行させる。
【０１１４】
次に、マスタノード２０は、各タスクに分割領域を割り当てる（ステップＳ１０３）。
【０１１５】
具体的には、データ管理部２１は、ステップＳ１０１において作成されたキーサイズテーブルＴ４００の各エントリに対応する分割領域を、ステップＳ１０２において生成された各タスクに割り当てる。
【０１１６】
なお、データ管理部２１は、キーサイズテーブルＴ４００のサイズＴ４０２に基づいて、データサイズが均等になるように、各タスクに分割領域を割り当てる。
【０１１７】
前述した分割領域の割り当て方法としては、例えば、データ管理部２１が、キーサイズテーブルＴ４００のエントリをサイズＴ４０２に基づいてソートし、データサイズが大きなエントリから順に、割り当てられたデータサイズが小さいタスクへ割り当てる方法が考えられる。
【０１１８】
データ管理部２１は、分割領域の割り当てが終了した後、タスクが割り当てられたスレーブノード３０に対して、結合すべきファイルのデータファイル名及びオフセット位置を送信する。
【０１１９】
例えば、図７ＡのキーサイズテーブルＴ４００の１つ目のエントリに対応する分割領域が割り当てられたタスクの場合、対応する分割テーブルＴ２００のエントリは、図５Ａ及び図５Ｂのそれぞれ１つ目のエントリである。したがって、データ管理部２１は、（データファイル名、開始位置、終了位置）＝（ｌｏｇ０１／００１．ｄａｔ，０，２８０）、（ｌｏｇ０２／００１．ｄａｔ，０，２００）を、当該タスクが割り当てられたスレーブノード３０に送信する。
【０１２０】
次に、マスタノード２０は、タスクが割り当てられた各スレーブノード３０に対してタスクの実行指示を送信し、処理を終了する（ステップＳ１０４）。
【０１２１】
具体的には、データ管理部２１は、タスクを割り当てた各スレーブノード３０にタスクの実行指示を送信する。
【０１２２】
マスタノード２０から指示を受信したスレーブノード３０は、ファイルサーバ（マスタ）２３にアクセスし、データ管理部２１から受信したデータファイル名及びオフセット位置に基づいて、指定されたファイルを、指定されたオフセット位置から読み出す。
【０１２３】
各スレーブノード３０は、読み出された各ファイルのｋｅｙをつき合わせ、結合処理を実行する。さらに、スレーブノード３０は、同一のスレーブノード３０において、実行中の分析処理のタスクに１レコードずつ結合処理の結果を出力する。
【０１２４】
例えば、図５Ａ及び図５Ｂに対応するデータセットに対する分析処理では、４つの分割領域毎にタスクが生成され、各タスクによって前述した結合処理が実行される。
【０１２５】
このとき、データセット毎に分割位置が異なると、重複するキー範囲について処理が実行されてしまうため並列処理が実現できない。しかし、本実施形態では、各データセットの分割位置が同一であるため、各データセットの分割領域における結合処理を並列実行できる。
【０１２６】
以上が、データの結合処理及び分析処理の説明である。
【０１２７】
次にデータ追加処理について説明する。
【０１２８】
データ追加処理は、データ管理テーブルＴ１００及び分割テーブルＴ２００が作成されているデータセット、すなわち、分散ファイルシステムに既存のデータセットが格納されている場合に、新規データセットを追加するための処理である。
【０１２９】
通常、データセット毎に各分割領域のデータサイズが異なる。そのため、分割位置を修正せずに各データセットの分割領域を結合すると、分割領域間のデータサイズのばらつきが発生する。この結果、分析処理を実行するタスクの処理量にばらつきが発生し、並列処理の効率が低下する。
【０１３０】
本発明では、前述した課題を解決するため、データ追加処理時に後述する処理を実行することによって、分割領域を再分割し、各分割領域のデータサイズを平準化する。
【０１３１】
具体的には、新規データセットが追加された後、結合対象となり得る全データセットを結合させた場合の各分割領域のデータサイズが所定の基準値以下になるように分割位置が制御される。これによって、全データセット利用時に並列実行される分析処理のタスク間における処理量の差を平準化させることができる。
【０１３２】
なお、一部のデータセットを結合する場合には、各分割領域のデータサイズは基準値以下になり、分析処理のタスク間の処理量の差は平準化される。
【０１３３】
分割領域を再分割することによって、結合処理及び分析処理のタスク制御のオーバーヘッドが発生した場合に、割り当てられている分割領域が小さくなった場合には、当該分割領域が割り当てられるタスクに複数の分割領域が割り当てられ、１つのタスクが実行する処理量を増やすことができる。
【０１３４】
なお、前述した所定の基準値は、タスクの処理量の差に影響することから、許容されるタスクの処理量の差に基づき決定することが望ましい。
【０１３５】
当該基準値を小さくしすぎると分割領域の数が増えるため、データ追加処理のオーバーヘッドが増える。一方、当該基準値を大きくしすぎるとタスク間の処理量の差が大きくなり、並列処理の効率が下がる。
【０１３６】
したがって、１つのタスクが所定のデータ量を処理するときの実行時間が、タスク間の処理時間の差として許容される時間以下になるようなデータ量を所定の基準値とすればよい。
【０１３７】
データ追加処理で追加されるデータは、図２０に示すような形式で入力される。データ追加処理では、図２２Ａ示すような形式のデータをユーザＩＤでグループ化された形式に変換され、分散ファイルシステムに格納される。以下、図２０の形式のデータセットを素データと記載し、図２１の形式のデータを構造化データと記載する。
【０１３８】
以下、図９を用いて具体的に処理について説明する。
【０１３９】
図９は、本発明の第１の実施形態におけるデータ追加処理を説明するフローチャートである。
【０１４０】
利用者が、ファイルサーバ（マスタ）２３及びファイルサーバ（スレーブ）３２によって実現される分散ファイルシステムに対して、素データを入力することによってデータ追加処理が実行される。
【０１４１】
まず、データ管理部２１は、入力された素データをサンプリングし、ｋｅｙの出現頻度を解析する（ステップＳ２０１）。
【０１４２】
具体的には、データ管理部２１は、素データに含まれるレコードをランダムにサンプリングする。データ管理部２１は、読み出されたレコードの最初のフィールドをｋｅｙとするｋｅｙの一覧を作成する。
【０１４３】
なお、素データは１レコードが１行の形式のデータから構成されるため、データ管理部２１は、改行コードを検出することによって１レコード分のデータを読み出すことができる。
【０１４４】
精度を向上するためにサンプリング数を増やす場合には、データ管理部２１は、サンプリング処理を並列実行してもよい。この場合、データ管理部２１は、素データをデータサイズが等しくなるように複数個に分割し、分割された素データ毎にサンプリング処理が実行される。
【０１４５】
具体的には、データ管理部２１は、サンプリング処理の実行タスクを各スレーブノード３０に割り当て、さらに、当該実行タスクに分割された素データを割り当てる。データ管理部２１は、各スレーブノード３０の処理実行部３１からサンプリング処理の結果を受信し、すべてのスレーブノード３０から受信したサンプリング処理の結果を集計してｋｅｙの一覧を作成する。
【０１４６】
次に、データ管理部２１は、作成されたｋｅｙの一覧に基づいて、素データの分割位置となるｋｅｙの値を決定する（ステップＳ２０２）。
【０１４７】
当該分割処理は、後述するステップＳ２０４における入力された素データを出力するための分割処理であり、分割テーブルＴ２００における分割処理とは異なる処理である。
【０１４８】
ただし、ステップＳ２０４の処理では、既存の分割位置は変更されない。したがって、素データの分割位置は、既存のデータセットの分割テーブルＴ２００の分割位置に一致させる必要がある。
【０１４９】
具体的には、以下のような処理が実行される。
【０１５０】
データ管理部２１は、分割テーブルＴ２００を参照し、既存の全データセットの分割位置を含むキーサイズテーブルＴ４００を作成する。例えば、図７Ａに示すようなキーサイズテーブルＴ４００が作成される。ただし、この時点では、サイズＴ４０２には値は格納されていない。
【０１５１】
データ管理部２１は、サンプリングされたｋｅｙ毎に対応する分割領域を特定し、キーサイズテーブルＴ４００の対応するエントリのサイズＴ４０２に、ｋｅｙに対応するデータのデータサイズをインクリメントする。
【０１５２】
以上のような処理によって、データ管理部２１は、サンプリングされたｋｅｙの分布を求めることができる。
【０１５３】
例えば、サンプリングされたｋｅｙが「１２５ｄ」である場合、当該ｋｅｙは、「０３４ａ」以上かつ「１７２ｄ」未満であるため、ｋｅｙ（Ｔ４０１）が「１７２ｄ」であるエントリのサイズＴ４０２にｋｅｙが「１２５ｄ」であるデータのデータサイズがインクリメントされる。
【０１５４】
データ管理部２１は、ｋｅｙの分布を求めた後、利用者によって指定された並列数と分割領域の数とが一致するように、キーサイズテーブルＴ４００の隣り合う分割領域をマージする。このとき、マージ後の各分割領域のデータサイズが均等になることが望ましい。
【０１５５】
例えば、利用者によって指定された並列数が「２」の場合、ｋｅｙの分布が図７Ｂに示すようなキーサイズテーブルＴ４００は４つの分割領域があるため、マージして２つの分割領域にする必要がある。そこで、データ管理部２１は、ｋｅｙ（Ｔ４０１）が「０３４ａ」のエントリと「１７２ｄ」のエントリとを１つの分割領域としてマージし、ｋｅｙ（Ｔ４０１）が「３２８ｂ」のエントリと空欄のエントリとを１つの分割領域としてマージする。
【０１５６】
マージ処理が終了した後、データ管理部２１は、マージ結果をパーティションテーブルＴ３００のｋｅｙ（Ｔ３０１）に格納する。
【０１５７】
なお、前述したマージ処理において、キーサイズテーブルＴ４００のエントリ数が、利用者によって指定された並列数以上の場合、マージ処理は実行されず、当該エントリ数が並列数となる。
【０１５８】
以上がステップＳ２０２における処理である。
【０１５９】
次に、データ管理部２１は、分析処理において結合対象となる可能性がある全データセットのデータサイズを算出する（ステップＳ２０３）。さらに、データ管理部２１は、算出結果に基づいて、キーサイズテーブルＴ４００を作成する。
【０１６０】
具体的には、以下のような処理が実行される。
【０１６１】
データ管理部２１は、データ管理テーブルＴ１００を参照して、各データセットの分割テーブル名Ｔ１０２を取得する。さらに、データ管理部２１は、取得された分割テーブル名Ｔ１０２に基づいて、対応する分割テーブルＴ２００の一覧を取得する。
【０１６２】
なお、結合対象となり得る各データセットの分割テーブルＴ２００における分割位置は一致している。したがって、分析処理において分割領域の結合を並列実行できる。
【０１６３】
データ管理部２１は、取得された分割テーブルＴ２００のｋｅｙ（Ｔ２０３）を含むキーサイズテーブルＴ４００を作成する。さらに、データ管理部２１は、分割テーブルＴ２００毎に各分割領域のデータサイズを算出し、作成されたキーサイズテーブルＴ４００のサイズ（Ｔ４０２）に、算出されたデータサイズを加算する。
【０１６４】
取得されたすべての分割テーブルＴ２００に対して同様の処理を実行することによって、分散ファイルシステム上に存在するすべての既存のデータセットに関するキーサイズテーブルＴ４００を作成できる。
【０１６５】
例えば、図５Ａ及び図５Ｂに示す分割テーブルＴ２００に対して前述した処理を実行することによって、図７Ａに示すようなキーサイズテーブルＴ４００が作成される。
【０１６６】
以上がステップＳ２０３における処理である。
【０１６７】
次に、データ管理部２１は、ステップＳ２０２におけるマージ結果を表すパーティションテーブルＴ３００に基づいて、素データに対するグルーピング処理を実行する（ステップＳ２０４）。
【０１６８】
ここで、グルーピング処理とは、素データに含まれるレコードをｋｅｙ（図２０に示す例ではユーザＩＤ）毎に集約する処理である。
【０１６９】
グルーピング処理では、データ管理部２１、データ追加部（Ｍａｐ）３３及びデータ追加部（Ｒｅｄｕｃｅ）３４が連携して処理を実行する。
【０１７０】
データ追加部（Ｍａｐ）３３及びデータ追加部（Ｒｅｄｕｃｅ）３４は、データ管理部２１からの指示にしたがって、それぞれ並列処理を実行する。
【０１７１】
なお、パーティションテーブルＴ３００のエントリ数が、タスクを割り当てるデータ追加部（Ｒｅｄｕｃｅ）３４の並列度となる。一方、タスクを割り当てるデータ追加部（Ｍａｐ）３３の並列度は、パーティションテーブルＴ３００のエントリ数とは無関係であり、利用者によって指定される。
【０１７２】
以下、データ追加部（Ｍａｐ）３３をＭａｐタスクと記載し、データ追加部（Ｒｅｄｕｃｅ）３４に割り当てるタスクをＲｅｄｕｃｅタスクとも記載する。
【０１７３】
具体的には以下のような処理が実行される。
【０１７４】
データ管理部２１は、利用者によって指定された並列数にしたがって、データサイズが一定となるように素データを分割する。さらに、データ管理部２１は、素データを分割して生成された分割領域の各分割位置であるオフセット位置、及び当該分割領域のデータサイズを算出する。なお、オフセット位置はレコード境界に一致するように素データの一部をスキャンして調整される。
【０１７５】
データ管理部２１は、処理管理部２２と連携して、利用者によって指定された並列数分のＭａｐタスクを生成し、生成されたＭａｐタスクを各データ追加部（Ｍａｐ）３３に割り当てる。このとき、各データ追加部（Ｍａｐ）３３には、分割領域のオフセット位置、分割領域のデータサイズ、及び素データのファイル名が送信される。
【０１７６】
さらに、データ管理部２１は、処理管理部２２連携して、パーティションテーブルＴ３００のエントリ数分のＲｅｄｕｃｅタスクを生成する。
【０１７７】
また、データ管理部２１は、パーティションテーブルＴ３００の各エントリをデータ追加部（Ｒｅｄｕｃｅ）３４と対応づける。データ管理部２１は、対応づけられた各データ追加部（Ｒｅｄｕｃｅ）３４に、ｋｅｙ（Ｔ３０１）に対応するｋｅｙ範囲の分割領域を処理するためのＲｅｄｕｃｅタスクを割り当てる。
【０１７８】
さらに、データ管理部２１は、ステップＳ２０２において作成されたキーサイズテーブルＴ４００のうち、送信されたｋｅｙ範囲に対応するエントリをデータ追加部（Ｒｅｄｕｃｅ）３４送信する。
【０１７９】
例えば、図６に示すパーティションテーブルＴ３００の最初のエントリのｋｅｙ範囲は、「１７２ｄ」未満であるため、対応するキーサイズテーブルＴ４００のエントリは、図７Ａの一つ目のエントリ及び２つ目のエントリである。したがって、データ管理部２１は、一つ目のエントリ及び２つ目のエントリを対応するデータ追加部（Ｒｅｄｕｃｅ）３４に送信する。
【０１８０】
さらに、データ管理部２１は、データ追加部（Ｒｅｄｕｃｅ）３４の宛先情報（アドレス：ポート番号）を取得し、パーティションテーブルＴ３００の対応するエントリの宛先Ｔ３０２に取得された宛先情報を格納する。
【０１８１】
パーティションテーブルＴ３００が作成された後、処理管理部２２は、すべてのデータ追加部（Ｍａｐ）３３に完成したパーティションテーブルＴ３００を送信する。
【０１８２】
以上がステップＳ２０４における処理である。
【０１８３】
なお、ステップＳ２０４におけるデータ追加部（Ｍａｐ）３３及びデータ追加部（Ｒｅｄｕｃｅ）３４は、グルーピング処理が実行された後、データの出力処理を実行する。グルーピング処理の詳細については図１０を用いて後述し、また、データの出力処理の詳細については図１１を用いて後述する。
【０１８４】
データ管理部２１は、分割テーブルＴ２００を更新し、処理を終了する（ステップＳ２０５）。
【０１８５】
具体的には、データ管理部２１は、各データ追加部（Ｒｅｄｕｃｅ）３４から受信した分割テーブルＴ２００に基づいて、自身が管理する分割テーブルＴ２００を更新する。なお、受信した分割テーブルＴ２００は、データ追加部（Ｒｅｄｕｃｅ）３４が後述する処理（図１０及び図１１参照）が実行された後のテーブルである。
【０１８６】
データ追加部（Ｒｅｄｕｃｅ）３４は、一部のｋｅｙ範囲のデータセットのみを処理する。本実施形態では、一つのデータ追加部（Ｒｅｄｕｃｅ）３４によって更新された分割テーブルＴ２００に基づいて、データ分析システムにおけるすべての分割テーブルＴ２００が更新される点に特徴がある。
【０１８７】
また、データ管理部２１は、各データ追加部（Ｒｅｄｕｃｅ）３４から受信した、入力された素データの分割テーブルＴ２００を１つにマージし、マージされたテーブルを入力された素データの分割テーブルＴ２００として管理する。
【０１８８】
これは、ｋｅｙ範囲毎に、各データ追加部（Ｒｅｄｕｃｅ）３４において素データに対する処理が並列実行されていたため、各処理結果を集約する処理である。
【０１８９】
さらに、データ管理部２１は、素データの分割テーブルＴ２００に対応するエントリをデータ管理テーブルＴ１００に追加する。
【０１９０】
次に、ステップＳ２０４におけるグルーピング処理の詳細について説明する。
【０１９１】
図１０は、本発明の第１の実施形態におけるグルーピング処理の詳細を説明するフローチャートである。
【０１９２】
スレーブノード３０は、入力された素データに対してソート処理を実行する（ステップＳ３０１）。
【０１９３】
具体的には以下の処理が実行される。
【０１９４】
データ追加部（Ｍａｐ）３３は、素データから１つずつレコードを読み出す。データ追加部（Ｍａｐ）３３は、読み出されたレコードのｋｅｙに基づいて、パーティションテーブルＴ３００からデータ追加部（Ｒｅｄｕｃｅ）３４の宛先情報を取得する。すなわち、読み出されたレコードを処理するデータ追加部（Ｒｅｄｕｃｅ）３４が特定される。
【０１９５】
データ追加部（Ｍａｐ）３３は、宛先毎に読み出された各レコードを分類する。以下、宛先ごとに分類されたレコード群をセグメントと記載する。
【０１９６】
データ追加部（Ｍａｐ）３３は、自身が担当する分割された素データに含まれるすべてのレコードを読み出した後、各セグメントに含まれるレコードをｋｅｙに基づいてソートする。
【０１９７】
以上がステップＳ３０１における処理である。
【０１９８】
次に、スレーブノード３０は、ソートされたセグメントをデータ追加部（Ｒｅｄｕｃｅ）３４に送信する（ステップＳ３０２）。
【０１９９】
具体的には、データ追加部（Ｍａｐ）３３が、ステップＳ３０１において取得された宛先情報に対応するデータ追加部（Ｒｅｄｕｃｅ）３４に、ソートされたセグメントを送信する。各データ追加部（Ｒｅｄｕｃｅ）３４は、各スレーブノード３０のデータ追加部（Ｍａｐ）３３から送信されるセグメントを受信する。
【０２００】
データ追加部（Ｍａｐ）３３からセグメントを受信したスレーブノード３０は、ｋｅｙに基づいて受信したセグメントをマージし、処理を終了する（ステップＳ３０３）。
【０２０１】
具体的には、データ追加部（Ｒｅｄｕｃｅ）３４が、受信したすべてのセグメントを順に読み出し、ｋｅｙが同一のセグメント同士をマージして結合する。
【０２０２】
さらに、データ追加部（Ｒｅｄｕｃｅ）３４は、マージされたセグメントに含まれるレコードを、図１０に示すような構造化データに変換する。前述した処理によって、複数のレコードが、ｋｅｙが同一の１つのレコードに集約される。
【０２０３】
次に、ステップＳ２０４において、データ追加部（Ｒｅｄｕｃｅ）３４が実行するデータ出力処理について説明する。
【０２０４】
図１１は、本発明の第１の実施形態におけるデータ出力処理を説明するフローチャートである。
【０２０５】
まず、データ出力処理の概要について説明する。
【０２０６】
データ追加部（Ｒｅｄｕｃｅ）３４は、データ出力処理を実行することによって、図２２Ａに示すような形式の構造化データを分散ファイルシステムへ出力する。並列度の数だけ、データ追加部（Ｒｅｄｕｃｅ）３４においてタスクが実行される。このとき、データ追加部（Ｒｅｄｕｃｅ）３４が出力するファイル名はそれぞれ異なる。
【０２０７】
さらに、本発明では、データ追加部（Ｒｅｄｕｃｅ）３４は、素データのデータサイズをキーサイズテーブルＴ４００に加算して、素データが追加された後の各分割領域のデータサイズを算出する。
【０２０８】
データ追加部（Ｒｅｄｕｃｅ）３４は、データサイズが所定の閾値以上である分割領域が存在する場合、分割領域の分割処理を実行する。
【０２０９】
データ追加部（Ｒｅｄｕｃｅ）３４は、分割領域の分割処理が実行された場合、自身が管理する既存のデータセットの分割テーブルＴ２００も更新する。さらに、データ追加部（Ｒｅｄｕｃｅ）３４は、更新された分割テーブルＴ２００をデータ管理部２１に送信する。更新された分割テーブルＴ２００に基づいて、データ管理部２１が、分割テーブルＴ２００の更新処理（ステップＳ２０５）を実行する。
【０２１０】
また、データ追加部（Ｒｅｄｕｃｅ）３４は、入力された素データの分割テーブルＴ２００を作成し、処理終了後に作成された分割テーブルＴ２００をデータ管理部２１に送信する。
【０２１１】
以下、各処理の詳細について説明する。
【０２１２】
まず、データ追加部（Ｒｅｄｕｃｅ）３４は、データ出力処理を開始する前に、ステップＳ２０４においてデータ管理部２１から受信したキーサイズテーブルＴ４００に含まれるｋｅｙのみが格納されたキーサイズテーブルＴ４００を作成する。ここで、作成されたキーサイズテーブルＴ４００は、素データの所定の分割領域のデータサイズが格納されるテーブルである。
【０２１３】
以下、作成されたキーサイズテーブルＴ４００を追加用キーサイズテーブルＴ４００とも記載する。なお、追加用キーサイズテーブルＴ４００が作成された時点では、サイズＴ４０２の初期値は「０」に設定される。
【０２１４】
また、データ管理部２１から受信したキーサイズテーブルＴ４００は、データ追加部（Ｒｅｄｕｃｅ）３４が担当するｋｅｙ範囲に含まれる分散ファイルシステム上の全データセットのデータサイズを管理するテーブルである。以下、当該キーサイズテーブルＴ４００を全データ用キーサイズテーブルＴ４００と記載する。
【０２１５】
データ出力処理が開始されると、データ追加部（Ｒｅｄｕｃｅ）３４は、ステップＳ３０３において作成されたレコードを出力し、前回出力されたレコードとは異なる分割領域に含まれるレコードであるか否かを判定する（ステップＳ４０１）。
【０２１６】
具体的には、データ追加部（Ｒｅｄｕｃｅ）３４は、追加用キーサイズテーブルＴ４００のｋｅｙ（Ｔ４０２）を参照し、出力されたレコードが前回出力されたレコードと異なる分割領域に含まれるか否かを判定する。
【０２１７】
本実施形態では、ｋｅｙに基づいてソートされたレコードが順に出力されるため、出力されたレコードが所定のｋｅｙ範囲、すなわち、所定の分割領域に含まれるか否かを判定できる。
【０２１８】
なお、最初に出力されるレコードの場合、同一の分割領域に含まれると判定される。
【０２１９】
異なる分割領域に含まれるレコードであると判定された場合、データ追加部（Ｒｅｄｕｃｅ）３４は、前回レコードが追加された分割領域のデータサイズの確認処理を実行し（ステップＳ４０５）、ステップＳ４０２に進む。なお、データサイズの確認処理については、図１２を用いて後述する。
【０２２０】
同一の分割領域に含まれるレコードであると判定された場合、データ追加部（Ｒｅｄｕｃｅ）３４は、ステップＳ３０３において作成されたレコードを分散ファイルシステムに書き込む（ステップＳ４０２）。
【０２２１】
このとき、データ追加部（Ｒｅｄｕｃｅ）３４は、書き込まれたレコードのｋｅｙの値、レコードが書き込まれたファイル上のオフセット位置、及びレコードのデータサイズを含むレコード統計情報を作成し、作成されたレコード統計情報を保存する。これは、素データのレコード統計情報である。
【０２２２】
次に、データ追加部（Ｒｅｄｕｃｅ）３４は、キーサイズテーブルＴ４００を更新する（ステップＳ４０３）。
【０２２３】
具体的には、データ追加部（Ｒｅｄｕｃｅ）３４は、ステップＳ４０２において書き込まれたレコードのｋｅｙが含まれるｋｅｙ範囲の分割領域を特定する。データ追加部（Ｒｅｄｕｃｅ）３４は、特定された分割領域に対応するエントリを、追加用キーサイズテーブルＴ４００及び全データキーサイズテーブルＴ４００から検索する。さらに、データ追加部（Ｒｅｄｕｃｅ）３４は、各キーサイズテーブルＴ４００の対応するエントリのサイズＴ４０２に、書き込まれたレコードのデータサイズを加算する。
【０２２４】
データ追加部（Ｒｅｄｕｃｅ）３４は、すべてのレコードを出力したか否かを判定する（ステップＳ４０４）。
【０２２５】
すべてのレコードが出力されていないと判定された場合、データ追加部（Ｒｅｄｕｃｅ）３４は、ステップＳ４０１に戻り、同様の処理を実行する。
【０２２６】
すべてのレコードが出力されたと判定された場合、データ追加部（Ｒｅｄｕｃｅ）３４は、最後の分割領域に対するデータサイズの確認処理を実行し、処理を終了する（ステップＳ４０６）。なお、ステップＳ４０６におけるデータサイズの確認処理は、ステップＳ４０５と同一の処理である。
【０２２７】
図１２は、本発明の第１の実施形態のおけるデータサイズの確認処理を説明するフローチャートである。
【０２２８】
データ追加部（Ｒｅｄｕｃｅ）３４は、ステップＳ４０３において更新された全データキーサイズテーブルＴ４００を参照し、対象となる分割領域のデータサイズが所定の基準値より大きいか否かを判定する（ステップＳ５０１）。すなわち、素データが追加された分割領域が、所定の基準値より大きいか否かが判定される。
【０２２９】
ここで、対象となる分割領域とは、前回入力されたレコードが含まれる分割領域である。以下、対象となる分割領域を、対象領域とも記載する。
【０２３０】
具体的には、データ追加部（Ｒｅｄｕｃｅ）３４は、全データキーサイズテーブルＴ４００の対応するエントリのサイズＴ４０２を参照し、対象領域のデータサイズが所定の基準値より大きいか否かを判定する。
【０２３１】
対象領域のデータサイズが所定の基準値以下であると判定された場合、データ追加部（Ｒｅｄｕｃｅ）３４は、ステップＳ５０６に進む。
【０２３２】
対象領域のデータサイズが所定の基準値より大きいと判定された場合、データ追加部（Ｒｅｄｕｃｅ）３４は、マスタノード２０から既存のデータセットの分割テーブルＴ２００を取得する（ステップＳ５０２）。
【０２３３】
ここで、ステップＳ２０３においてマスタノード２０が取得したすべての分割テーブルＴ２００が取得される。なお、データ追加部（Ｒｅｄｕｃｅ）３４は、マスタノード２０から取得された分割テーブルＴ２００をキャッシュとして保存してもよい。
【０２３４】
次に、データ追加部（Ｒｅｄｕｃｅ）３４は、取得された各分割テーブルＴ２００における対象領域の終了位置、すなわち、オフセットを特定する（ステップＳ５０３）。
【０２３５】
具体的には以下のような処理が実行される。
【０２３６】
データ追加部（Ｒｅｄｕｃｅ）３４は、対象領域のｋｅｙに基づいて、取得された各分割テーブルＴ２００を参照して、対象領域に対応するエントリを取得する。すなわち、対象領域に対応するデータのデータファイル名Ｔ２０２及びオフセットＴ２０４が取得される。なお、当該処理は、ステップＳ５０２において取得されたすべての分割テーブルＴ２００に対して実行される。
【０２３７】
例えば、ステップＳ５０１において図１３に示すような全データキーサイズテーブルＴ４００であり、最初のエントリに対応する分割領域のデータサイズが所定の基準値より大きい場合、データ追加部（Ｒｅｄｕｃｅ）３４は、図５Ａ及び図５Ｂに示す分割テーブルＴ２００の１つ目のエントリから情報を取得する。
【０２３８】
この場合、図５Ａでは（データファイル名、オフセット）＝（／ｌｏｇ０１／００１．ｄａｔ，２８０）となり、図５Ｂでは（／ｌｏｇ０２／００２．ｄａｔ，２００）となる。取得されたオフセットが、各分割テーブルＴ２００における対象領域の終了位置となる。
【０２３９】
なお、対象領域の開始位置は、１つ目のエントリであるため開始位置のオフセットは「０」である。
【０２４０】
次に、データ追加部（Ｒｅｄｕｃｅ）３４は、各既存のデータセットの対象領域に含まれるレコードを解析する（ステップＳ５０４）。
【０２４１】
具体的には、データ追加部（Ｒｅｄｕｃｅ）３４は、各既存のデータセットの対象領域に含まれるレコードを読み出す。例えば、データＩＤ（Ｔ１０１）が「ｌｏｇ０１」及び「ｌｏｇ０２」のデータセットがある場合に、「ｌｏｇ０１」のデータセットの対象領域からレコードが読み出され、また、「ｌｏｇ０２」のデータセットの対象領域からレコードが読み出される。
【０２４２】
データ追加部（Ｒｅｄｕｃｅ）３４は、読み出されたレコードのｋｅｙ、レコードのデータサイズ、及びレコードのファイル上のオフセット位置を含むレコード統計情報を取得する。
【０２４３】
なお、既存のデータセットは複数存在するため、当該レコードの解析処理をデータセット毎に並列実行してもよい。
【０２４４】
データ追加部（Ｒｅｄｕｃｅ）３４は、ステップＳ４０２において取得された素データのレコード統計情報と、既存データセットのレコード統計情報とを合わせて、分散ファイルシステム上における全データセットのレコード統計情報とする。
【０２４５】
次に、データ追加部（Ｒｅｄｕｃｅ）３４は、作成された全データセットのレコード統計情報に基づいて、再分割する分割位置となるｋｅｙの値を決定する（ステップＳ５０５）。
【０２４６】
具体的には以下のような処理が実行される。
【０２４７】
データ追加部（Ｒｅｄｕｃｅ）３４は、全データセットのレコード統計情報に基づいて、対象領域におけるデータサイズを算出する。
【０２４８】
データ追加部（Ｒｅｄｕｃｅ）３４は、算出されたデータサイズ及び所定の基準値に基づいて、対象領域における分割数を算出する。
【０２４９】
次に、データ追加部（Ｒｅｄｕｃｅ）３４は、対象領域のデータサイズを、算出された分割数で除算して、再分割後の分割領域のデータサイズを算出する。
【０２５０】
データ追加部（Ｒｅｄｕｃｅ）３４は、全データセットのレコード統計情報のエントリをｋｅｙでソートした後、レコードのデータサイズの累積値分布を算出する。すなわち、分散ファイルシステムにおける所定のｋｅｙ範囲に含まれる各レコードのデータサイズの分布が算出される。
【０２５１】
データ追加部（Ｒｅｄｕｃｅ）３４は、算出された累積値分布に基づいて、レコードのデータサイズが分割後の分割領域のデータサイズの整数倍になっている地点を再分割の分割位置として決定する。整数倍になっていない場合、当該テータサイズと最も近いレコードが分割位置として決定される。
【０２５２】
再分割位置のｋｅｙは、データとして存在するｋｅｙを使ってもよいし、データとして存在しないｋｅｙを使ってもよい。
【０２５３】
データ追加部（Ｒｅｄｕｃｅ）３４は、全データセットのレコード統計情報を参照して、決定された各ｋｅｙ範囲に対応するオフセットを特定する。
【０２５４】
データ追加部（Ｒｅｄｕｃｅ）３４は、各分割テーブルＴ２００に再分割後の分割領域に対応するエントリを追加する。また、データ追加部（Ｒｅｄｕｃｅ）３４は、各分割テーブルＴ２００から再分割前の分割領域に対応するエントリを削除する。
【０２５５】
例えば、ｋｅｙ範囲が「０３４ａ」未満である分割領域が、ｋｅｙ範囲が「０１５ｄ」未満である分割領域と、ｋｅｙ範囲が「０１５ｄ」以上かつ「０３４ａ」未満である分割領域との２つの分割領域に分割された場合、図５Ａ及び図５Ｂに示す分割テーブルＴ２００は、図１４Ａ及び図１４Ｂのように変更される。図中の太線で示した部分が変更箇所である。
【０２５６】
データ追加部（Ｒｅｄｕｃｅ）３４は、レコード統計情報に基づいて、追加用キーサイズテーブルＴ４００及び全データキーサイズテーブルＴ４００も変更する。
【０２５７】
例えば、再分割前の全データキーサイズテーブルＴ４００が図１３に示すテーブルである場合、図１５に示すように変更される。図中の太線で示した部分が変更箇所である。
【０２５８】
以上がステップＳ５０５の処理である。
【０２５９】
次に、データ追加部（Ｒｅｄｕｃｅ）３４は、分割テーブルＴ２００を更新する（ステップＳ５０６）。
【０２６０】
具体的には、データ追加部（Ｒｅｄｕｃｅ）３４は、追加用キーサイズテーブル及び素データのレコード統計情報に基づいて、素データの分割テーブルＴ２００に対応する分割領域のエントリを格納する。すなわち、素データの分割テーブルＴ２００が生成される。
【０２６１】
なお、再分割処理が実行された場合には、新たに分割された分割領域に対応するエントリが格納される。
【０２６２】
データ追加部（Ｒｅｄｕｃｅ）３４は、前述した処理に用いたレコード統計情報を削除し、処理を終了する（ステップＳ５０７）。
【０２６３】
［第２の実施形態］
【０２６４】
第１の実施形態では、ファイルの内容は１つのファイルに保存されているため分析処理時に不要なデータも読み出される可能性がある。これに対して、第２の実施形態では、データ項目（列）毎に異なるファイルとして保存する方式を用いる。当該方式を用いることによって、分析処理時に必要な項目のみ読み出すことが可能となる。
【０２６５】
本発明は、データ項目毎に異なるファイルに保存する格納方式（列分割格納方式）にも対応することが可能である。
【０２６６】
以下、第１の実施形態との差異を中心に第２の実施形態について説明する。
【０２６７】
第２の実施形態では、データ分析システムの構成は第１の実施形態と同一であるため説明を省略する。また、マスタノード２０及びスレーブノード３０のハードウェア構成及びソフトウェア構成も第１の実施形態と同一であるため説明を省略する。
【０２６８】
図１６は、本発明の第２の実施形態におけるレコードのスキーマを示す説明図である。図１７は、本発明の第２の実施形態におけるレコードの一例を示す説明図である。
【０２６９】
第１の実施形態のレコードに対して、第２の実施形態のレコードにはユーザの年齢が新たに含まれる。
【０２７０】
レコードの項目は、ユーザＩＤ、移動履歴（位置Ｘ、位置Ｙ、タイムスタンプの履歴）、及び年齢の３種類があり、本実施形態ではユーザＩＤがｋｅｙとして使用される。
【０２７１】
図１８Ａ、図１８Ｂ及び図１８Ｃは、本発明の第２の実施形態におけるファイルを示す説明図である。
【０２７２】
図１８Ａ、図１８Ｂ及び図１８Ｃでは、列分割方式を用いて前述したデータがファイルに格納された例を表す。
【０２７３】
図１８Ａ、図１８Ｂ及び図１８Ｃに示すように、ユーザＩＤはｌｏｇ／００１．ｋｅｙ．ｄａｔ（図１８Ａ）、移動履歴はｌｏｇ／００１．ｒｅｃ．ｄａｔ（図１８Ｂ）、年齢はｌｏｇ／００１．ａｇｅ．ｄａｔ（図１８Ｃ）というファイルにそれぞれ格納される。
【０２７４】
データを読み出すときは、各ファイルの上から順にレコードが１つずつ読み出され、順に結合すれば図１７に示したレコード全体を再構成することができる。
【０２７５】
図１８Ａ、図１８Ｂ及び図１８Ｃに示す例では、ファイルは１セットのみであるが、データが定期的に蓄積されていくことによって、ユーザＩＤ、移動履歴、及び年齢に対応するファイルを含むデータセットが増加する。
【０２７６】
実際の結合処理及び分析処理では並列して実行されるため、前述のファイルが分割された後、各スレーブノード３０によって処理が実行される。
【０２７７】
図１９は、本発明の第２の実施形態における分割テーブルＴ２００の一例を示す説明図である。
【０２７８】
第２の実施形態における分割テーブルＴ２００は、項目毎（ユーザＩＤ、移動履歴、及び年齢）にデータファイル名Ｔ２０２及びオフセットＴ２０４を格納する点が第１の実施形態と異なる。また、ｋｅｙとして使用される項目には、ｋｅｙ（Ｔ２０３）に分割位置を表すｋｅｙの値が格納される。
【０２７９】
次に、第２の実施形態における結合処理及び分析処理について第１の実施形態との相違点を中心に説明する。
【０２８０】
ステップＳ１０１では、キーサイズテーブルＴ４００が作成される場合に、データ管理部２１が、分割テーブルＴ２００の中で分析処理に用いる項目のオフセットを参照して、各分割領域のサイズを計算する。
【０２８１】
例えばユーザＩＤと年齢のみを使用する分析を行う場合は、「ｕｉｄ」のオフセットと「ａｇｅ」のオフセットのみを使ってキーサイズテーブルのサイズを求める。このとき、「ｒｅｃ」についてのオフセットは使用されない。
【０２８２】
これによって、一部の項目のみ利用する場合であっても、各分割領域のデータサイズを正確に算出できる。
【０２８３】
また、Ｓ１０４では、タスクが割り当てられた各スレーブノード３０が、分析処理に用いるファイル数と、分析処理に用いる項目数との積の数分だけ、ファイルが読み出される。
【０２８４】
データ追加処理についても以下のような相違がある。
【０２８５】
ステップＳ２０３では、データ管理部２１が、結合する可能性があるすべてのデータセットの分割テーブルＴ２００の項目毎のオフセットから、既存データセットのキーサイズテーブルＴ４００を作成する。
【０２８６】
ステップＳ４０２では、各レコードをファイル出力するとき、項目毎に別のファイルに出力される。したがって、ステップＳ４０２では項目毎に、書き込まれたレコードのｋｅｙの値、書き込まれたファイル上のオフセット、及びデータサイズを含むレコード統計情報が保存される。
【０２８７】
また、ステップＳ４０３では、全項目の分割領域のサイズの和をキーサイズテーブルＴ４００の対応するエントリに加算される。
【０２８８】
Ｓ５０６では、前述したレコード統計情報及びキーサイズテーブルＴ４００を用いて、項目毎に分割位置のオフセット値を求めて分割テーブルＴ２００を更新する。
【０２８９】
Ｓ５０４では、データに含まれる全項目に対応するファイルが読み出され、項目毎に、ファイルに書き込まれたレコードのｋｅｙの値、書き込んだファイル上のオフセット位置、及びデータサイズを含むレコード統計情報が保存される。
【０２９０】
Ｓ５０５では、データ追加部（Ｒｅｄｕｃｅ）３４が、全項目の分割領域のデータサイズを足し合わせたものを当該データセットのデータサイズとして、分割位置のｋｅｙを決定する。
【０２９１】
Ｓ５０６では、データ追加部（Ｒｅｄｕｃｅ）３４が、決定されたｋｅｙ及びレコード統計情報を用いて、項目毎に分割位置のオフセットを算出し、分割テーブルＴ２００を更新する。
【０２９２】
第２の実施形態では、３つの項目を処理する場合について説明したが、分割テーブルＴ２００において管理される項目数を変更することによって任意の項目数にすることができる。
【０２９３】
本発明の一形態によれば、データ分析システムは、各データセットの分割位置が同一であるため分析処理における結合処理を並列に実行することができる。また、新たにデータセットが追加された場合に、タスク間の処理量が均一になるように分割領域を再分割することができる。これによって、タスク間の処理の不均衡を解消し、かつ、結合処理時に分散領域毎にレコードを結合することができる。
【０２９４】
以上、本発明を添付の図面を参照して詳細に説明したが、本発明はこのような具体的構成に限定されるものではなく、添付した請求の範囲の趣旨内における様々な変更及び同等の構成を含むものである。
【図１】
2012131927.tif 000003
【図２】
2012131927.tif 000004
【図３Ａ】
2012131927.tif 000005
【図３Ｂ】
2012131927.tif 000006
【図４】
2012131927.tif 000007
【図５Ａ】
2012131927.tif 000008
【図５Ｂ】
2012131927.tif 000009
【図６】
2012131927.tif 000010
【図７Ａ】
2012131927.tif 000011
【図７Ｂ】
2012131927.tif 000012
【図８】
2012131927.tif 000013
【図９】
2012131927.tif 000014
【図１０】
2012131927.tif 000015
【図１１】
2012131927.tif 000016
【図１２】
2012131927.tif 000017
【図１３】
2012131927.tif 000018
【図１４Ａ】
2012131927.tif 000019
【図１４Ｂ】
2012131927.tif 000020
【図１５】
2012131927.tif 000021
【図１６】
2012131927.tif 000022
【図１７】
2012131927.tif 000023
【図１８Ａ】
2012131927.tif 000024
【図１８Ｂ】
2012131927.tif 000025
【図１８Ｃ】
2012131927.tif 000026
【図１９】
2012131927.tif 000027
【図２０】
2012131927.tif 000028
【図２１】
2012131927.tif 000029
【図２２Ａ】
2012131927.tif 000030
【図２２Ｂ】
2012131927.tif 000031
【図２２Ｃ】
2012131927.tif 000032
【国際調査報告】
2012131927.tif 000033
2012131927.tif 000034