データ処理装置、データ処理方法、および、データ処理プログラム
【課題】MapReduce処理システムにおける性能を向上し、通信コストを下げること。
【解決手段】データ処理システム１の統合計画部１４は、キー抽出部１０を構成するための計算機環境に応じて定義されるキー統合処理の実行粒度についての構成要素ごとにキー統合処理を行うか否かという組み合わせにより実行計画の候補を作成し、作成した各候補を評価して高評価の候補を実行計画として採用し、計画指示部１５は、統合計画部１４が採用した実行計画について、その実行計画の実行粒度が小さい順に統合処理部１３へと適用する。キー統合処理の実行粒度は、例えば、結果出力部１２ごと、抽出プロセス４１ごと、抽出マシン４２ごとである。
【解決手段】データ処理システム１の統合計画部１４は、キー抽出部１０を構成するための計算機環境に応じて定義されるキー統合処理の実行粒度についての構成要素ごとにキー統合処理を行うか否かという組み合わせにより実行計画の候補を作成し、作成した各候補を評価して高評価の候補を実行計画として採用し、計画指示部１５は、統合計画部１４が採用した実行計画について、その実行計画の実行粒度が小さい順に統合処理部１３へと適用する。キー統合処理の実行粒度は、例えば、結果出力部１２ごと、抽出プロセス４１ごと、抽出マシン４２ごとである。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法、および、データ処理プログラムに関する。
【背景技術】
【０００２】
非特許文献１のMapReduce処理システムは、大量の情報である入力データから、１つ以上のキーを抽出して（Map関数）、抽出された複数のキーを統合して（Reduce関数）、出力データとして出力する。１つのキーは、１つのキー名（key）と、１つのキー値（value）との組（key/value pair）として表現される。例えば、入力データをテキストの文書とすると、キー名は、文書内に出現する単語であり、キー値は、例えば、単語の出現回数である。出力されるキーは、例えば、機械学習処理や統計情報処理などの分析系の処理に応用される。
【０００３】
非特許文献１のMapReduceでは処理の高速化の機能としてCombine手段を有している。Combine手段では、Mapプロセス内で実行された全Map関数内で呼び出されるEmit関数の結果を入力としてReduce関数を実行することで、Combine手段を用いない標準的なMap処理手段と比較して、Reduce関数の実行によりEmit関数の結果データ量を削減する。その結果、MapReduce全体の性能向上を実現する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Jeffrey Dean and Sanjay Ghemawat,“MapReduce: Simplified Data Processing on Large Clusters”,OSDI'04: Sixth Symposium on Operating System Design and Implementation,San Francisco, CA, December, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
前記の非特許文献１のMapReduce処理システムにおけるCombine手段では、以下の２つの問題を解決していない。
【０００６】
１つ目の問題は、Combine手段を実行する前あるいはCombineを利用しない場合でも、Mapプロセス内においてEmit関数の結果をキー値でソートする必要があることから、Emit関数の呼び出し回数の多い処理では性能が劣化する傾向があることである。
例えば、webページなどのデータに対して単語の頻度計算の処理をする場合には、１ページ毎にMap関数が呼び出され、Map関数内では該当ページ内の単語毎にEmit関数が呼び出される実装が非特許文献１に記載されているが、この例では特にページサイズの大きいwebページを処理する場合に、Map関数あたりに呼び出されるEmit関数が非常に多くなり性能が劣化する傾向がある。
【０００７】
２つ目の問題は、シャッフル処理によってMapプロセスからReduceプロセスへとデータを配信する際の通信コストが大きいという問題である。
【０００８】
そこで、本発明は、前記した問題を解決し、MapReduce処理システムにおける性能を向上し、通信コストを下げることを、主な目的とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、本発明は、記憶手段から読み出した入力データに対してキー抽出処理を実行することで、キー名およびキー値の組であるキーを１つ以上抽出し、その結果を中間データとして前記記憶手段に書き込むキー抽出部と、前記記憶手段から読み出した前記中間データに対してキー統合処理を実行し、その結果を出力データとして前記記憶手段に書き込むキー統合部と、を有するデータ処理装置であって、前記キー抽出部が、データ解析部と、結果出力部と、統合処理部と、統合計画部と、計画指示部とを有し、前記データ解析部が、前記入力データを解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、前記結果出力部を呼び出し、前記結果出力部が、前記データ解析部から通知されたキーを、前記統合処理部へと出力し、前記統合処理部が、前記キー統合処理を実行するための実行計画に従って、前記結果出力部が出力する１つ以上のキーに対して前記キー統合処理を実行して、その結果を前記中間データとして前記記憶手段に書き込み、前記統合計画部が、前記キー抽出部を構成するための計算機環境に応じて定義される前記キー統合処理の実行粒度についての構成要素ごとに前記キー統合処理を行うか否かという組み合わせにより前記実行計画の候補を作成し、その作成した各候補に対して前記入力データの少なくとも一部を前記データ解析部に入力して動作させ、その実行時間が短いほど高評価とする評価方法により評価して、高評価の候補を前記実行計画として採用し、前記計画指示部が、前記統合計画部が採用した前記実行計画について、その前記実行計画の実行粒度が小さい順に前記統合処理部へと適用することを特徴とする。
さらに、本発明は、前記データ処理装置が前記各処理を実行するデータ処理方法である。
さらに、本発明は、前記データ処理方法を前記データ処理装置に実行させるためのためのデータ処理プログラムである。
【００１０】
これにより、実行粒度が規定されている実行計画に従ってキー統合処理を実行するので、MapReduce処理システムにおける性能を向上し、通信コストを下げることができる。
さらに、データ解析対象の実データを実際に試行して性能測定することにより、高精度の実行計画を作成することができる。
【００１１】
本発明は、前記統合計画部が、計算機環境に応じて定義される前記キー統合処理の実行粒度について、前記統合処理部が実行する実行関数ごとに前記キー統合処理を行うか否かという小粒度、１つ以上の前記結果出力部が属する抽出プロセスごとに前記キー統合処理を行うか否かという中粒度、および、１つ以上の前記抽出プロセスが属する抽出マシンごとに前記キー統合処理を行うか否かという大粒度という３段階の実行粒度をもとにした前記実行計画を作成することを特徴とする。
【００１２】
これにより、３段階の実行粒度を規定することにより、抽出プロセスというソフトウェア面での計算機環境と、抽出マシンというハードウェア面での計算機環境とが併せて考慮され、計算機環境に適した実行計画を作成することができる。
【００１３】
本発明は、前記統合処理部が、１つ以上のキーに対して前記キー統合処理を実行するときに、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキーを出力するとともに、統合対象である複数のキーのうちの異なるキー名をもつキーのキー値に対して、キー名をもとにソートすることで、キーの統合結果を作成することを特徴とする。
【００１４】
これにより、キー統合処理において、多くのキーを１つのキーへと統合することができ、中間データのデータ量を削減することができるとともに、キー統合部へ通知するキーの通信効率を向上させることができる。
【発明の効果】
【００１５】
本発明によれば、MapReduce処理システムにおける性能を向上し、通信コストを下げることができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に関するデータ処理システムを示す構成図である。
【図２】本発明の一実施形態に関するデータ処理システムにおけるキー抽出部およびキー統合部の詳細を示す構成図である。
【図３】本発明の一実施形態に関する統合計画部による実行計画の小粒度および中粒度を示す説明図である。
【図４】本発明の一実施形態に関する統合計画部による実行計画の大粒度を示す説明図である。
【図５】本発明の一実施形態に関する計画指示部による実行計画の実行指示を示す第１例の説明図である。
【図６】本発明の一実施形態に関する計画指示部による実行計画の実行指示を示す第２例の説明図である。
【図７】本発明の一実施形態に関する各粒度での統合処理の具体例を示す説明図である。
【図８】本発明の一実施形態に関するデータ解析部への入力データごとに決まる値を用いた、キー統合処理を示す説明図である。
【発明を実施するための形態】
【００１７】
以下、本発明の一実施形態を、図面を参照して詳細に説明する。
【００１８】
図１は、データ処理システム１（データ処理装置）を示す構成図である。データ処理システム１は、キー抽出部１０と、キー統合部２０と、処理起動部９０と、入力データ３１と、中間データ３２と、出力データ３３とを含めて構成される。なお、データ処理システム１は、様々なハードウェア構成およびソフトウェア構成として実現することができる。これらの構成の詳細は、図３以降で説明する。
【００１９】
処理起動部９０は、ユーザの操作を受け、キー抽出部１０およびキー統合部２０を起動する。さらに、処理起動部９０は、入力データ３１が入力されると、記憶手段に書き込む。
キー抽出部１０は、記憶手段から入力データ３１を読みだして、キー抽出処理を実行し、その結果を中間データ３２として記憶手段に書き込む。
キー統合部２０は、記憶手段から中間データ３２を読みだして（この読み出し処理を、シャッフル処理とも呼ぶ）、キー統合処理を実行し、その結果を出力データ３３として記憶手段に書き込む。
【００２０】
図２は、データ処理システム１におけるキー抽出部１０およびキー統合部２０の詳細を示す構成図である。
【００２１】
キー抽出部１０は、データ解析部１１と、結果出力部１２と、統合処理部１３と、統合計画部１４と、計画指示部１５とを含めて構成される。
データ解析部１１は、非特許文献１の「Map関数」に該当し、入力データ３１を解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、結果出力部１２を呼び出す。
結果出力部１２は、非特許文献１の「emit関数」に該当し、データ解析部１１から通知されたキーを、統合処理部１３または中間データ３２へと出力する。どちらに出力するかは、実行計画に従う。
統合処理部１３は、非特許文献１の「combine関数」に該当し、結果出力部１２の出力結果（または、結果出力部１２の出力結果に対して１回以上のキー統合処理が行われた結果）である複数のキーを、１つに統合してから中間データ３２に出力する。
【００２２】
キー統合部２０の統合処理部２１は、非特許文献１の「Reduce関数」に該当し、キー抽出部１０が入力データ３１から中間データ３２を作成した後に、その中間データ３２に対してキー統合処理を実行し、出力データ３３として出力する。なお、キー統合処理の処理内容は、統合処理部２１と統合処理部１３とで同じである。
【００２３】
【表１】
【００２４】
表１は、統合処理部１３、統合処理部２１によるキー統合処理の入力を示す。この表１の入力は、統合処理部１３がキー統合処理を行うときには、入力データ３１から結果出力部１２を介して出力される１つ以上のキーのリストであり、統合処理部２１がキー統合処理を行うときには、中間データ３２である。
表１では、１つの行が１つのキーである。例えば、１行目は、キー名が「Ａ」でキー値が「１」のキーを示す。以下、本実施形態では、キーを（キー名，キー値）と表現する。例えば、１行目のキーは、（Ａ，１）である。そして、本実施形態では、キーの説明の一例として、非特許文献１で記載されていた例と同じように、入力データ３１をテキストの文書（webページでもよい）とし、キー名を文書内に出現する単語とし、キー値を単語の出現回数として説明する。
なお、非特許文献１にあるように、統合処理部２１のReduce関数は可換および分配可能な演算を指定することが可能であり、本実施形態ではReduce関数として同一キー名のキー値の和を演算する例を示している。
【００２５】
キー統合処理は、例えば、以下の各処理である。
まず、同じキー名の統合処理では、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキー（統合対象となる同じキー名、統合演算結果のキー値）を出力する。例えば、表１では、（Ａ，１）のキーが３つ存在するので、統合演算としてキー値の加算処理を行うことにより、（Ａ，３）という１つのキーへと統合している。
次に、異なるキー名のソート処理では、統合対象である複数のキーについて、キー名をもとに、昇順または降順でソートする。例えば、表１では、キー名が「Ａ，Ｂ，Ｃ，Ｄ」の４種類あるので、この順にならぶようにソートする。なお、非特許文献１では、キー統合処理は、同じキー名の統合処理として記載されているので、この異なるキー名のソート処理は省略してもよい。
さらに、統合結果の圧縮処理は、同じキー名の統合処理および異なるキー名のソート処理の処理結果であるキーのリストに対して、データ圧縮する処理である。
【００２６】
【表２】
【００２７】
表２は、統合処理部１３、統合処理部２１によるキー統合処理の結果を示す。表１では８つ存在するキーが、表２では４つへと統合されている。これにより、キーの数を減らすことができるので、キーを送信するための通信効率を向上させることができる。
【００２８】
統合計画部１４は、データ解析部１１、および、統合処理部１３の各処理内容の特性から実行計画を作成して出力する。実行計画とは、結果出力部１２の出力結果であるキーに対して行われるキー統合処理の粒度を指定するデータである。キー統合処理の粒度には、例えば、以下に示す３種類の粒度がある。
【００２９】
以下、データ処理システム１の構成（抽出プロセス４１、抽出マシン４２）に着目して、図３〜図４で各粒度の詳細を説明する。なお、抽出マシン４２とは、１台のコンピュータである。このコンピュータは、ＣＰＵとメモリとハードディスク（記憶手段）とネットワークインタフェースを有する。ＣＰＵは、メモリ上に読み込んだプログラムを実行することにより、１つ以上の抽出プロセス４１を動作させる。１つの抽出プロセス４１上では、１つ以上の統合処理部１３が構成される。１つの統合処理部１３は、１つの実行関数を実行する。
【００３０】
図３（ａ）に示す小粒度（実行関数ごとの統合処理）とは、同じキー抽出部１０の結果出力部１２が出力する結果ごとに、統合処理部１３が結果をまとめる粒度である。なお、データ解析部１１は、１つの入力データ３１から、単語を発見するたびに結果出力部１２を呼び出すので、１つの結果出力部１２からは複数回のキーが出力される。よって、結果出力部１２ごとの粒度であっても、複数のキーを統合する処理が可能である。
【００３１】
図３（ｂ）に示す中粒度（抽出プロセス４１ごとの統合処理）とは、同じ抽出プロセス４１に属する１つ以上のキー抽出部１０の結果出力部１２が出力する結果ごとに、統合処理部１３が結果をまとめる粒度である。まず、左側の抽出プロセス４１ａには２つの結果出力部１２が存在するので、この２つの結果出力部１２から統合処理部１３により１回のキー統合処理が実行される。次に、右側の抽出プロセス４１ｂには１つの結果出力部１２が存在するので、この１つの結果出力部１２から統合処理部１３により１回のキー統合処理が実行される。
【００３２】
図４（ａ）に示す大粒度（抽出マシン４２ごとの統合処理）とは、同じ抽出マシン４２に属する１つ以上のキー抽出部１０の結果出力部１２が出力する結果ごとに、統合処理部１３が結果をまとめる粒度である。抽出マシン４２には３つの結果出力部１２が存在するので、この３つの結果出力部１２から統合処理部１３により１回のキー統合処理が実行される。
一方、図４（ｂ）のように、抽出マシン４２が異なる結果出力部１２どうしは、それぞれ異なる統合処理部１３によりキー統合処理が実行される。
【００３３】
以上図３および図４を参照して説明した複数種類の粒度をもとに、統合計画部１４は、各粒度（例えば、抽出プロセスという中粒度）についての構成要素（例えば、抽出プロセスＰ１）ごとにキー統合処理を行うか否かという組み合わせにより、実行計画の候補を作成する。例えば、以下が実行計画の候補の一例である。
抽出マシンＭ１：統合処理を行う。
抽出プロセスＰ１：統合処理を行う。
抽出プロセスＰ２：統合処理を行わない。
実行関数Ｆ１：統合処理を行わない。
実行関数Ｆ２：統合処理を行う。
実行関数Ｆ３：統合処理を行わない。
実行関数Ｆ４：統合処理を行う。
【００３４】
ここで、統合計画部１４は、実行計画を作成する際に、入力データ３１の少なくとも一部を利用してもよい。例えば、統合計画部１４は、データ解析部１１が解析対象として入力する入力データ３１の処理単位（例えば、単語抽出処理における処理対象の文書ごとに）を参照して、キー統合処理の粒度を決定してもよい。例えば、１つの文書が１つの抽出プロセス４１に割り当てられているときには、その抽出プロセス４１を粒度とするキー統合処理を有効に設定する。
【００３５】
そして、統合計画部１４は、実行計画の各候補を評価し、もっとも高評価の候補を実行計画として採用する。各候補の評価方法は、例えば、入力データ３１の少なくとも一部を対象として、実際にキー統合処理を実行させて、その性能（例えば、計算時間）を測定する（いわゆるベンチマーク）方法が挙げられる。
【００３６】
計画指示部１５は、以下の実行手順（１）〜（３）を順に実行することにより、統合計画部１４が作成した実行計画の実行を、各統合処理部１３に指示する。
図７は、各粒度での統合処理の具体例を示す説明図である。
図７（ａ）は、統合前のキーのリストであり、各キーを処理するために統合処理部１３が実行する実行関数と、その統合処理部１３が属する抽出プロセス４１と、その統合処理部１３が属する抽出マシン４２とが対応づけられている。
ただし、実行関数の記載について、例えばＦ１というのは、Ｆという関数を１番目に実行した結果として、(Ａ，１)，(Ａ，１)，(Ｂ，１)というキー（キー名とキー値との組）を３つ出力したということを意味する。
【００３７】
図７（ｂ）で示すように、計画指示部１５の実行手順（１）では、小粒度のキー統合処理を実行する。具体的には、データ処理システム１のキー抽出部１０内の各結果出力部１２を１つずつ選択し、その選択した結果出力部１２に対してキー統合処理を行う旨が実行計画で指定されているときには、その選択した結果出力部１２の出力結果に対して、統合処理部１３によるキー統合処理を行う。例えば、図７（ｂ）の１行目の実行関数Ｆ１のキーリストは、図７（ａ）の実行関数Ｆ１のキーである、２つの（Ａ，１）を１つに統合した結果である。このように、実行関数ごとにキー値を統合するため、データ量が削減できる。
【００３８】
図７（ｃ）で示すように、計画指示部１５の実行手順（２）では、中粒度のキー統合処理を実行する。具体的には、データ処理システム１の抽出プロセス４１を１つずつ選択し、その選択した抽出プロセス４１に対してキー統合処理を行う旨が実行計画で指定されているときには、その選択した抽出プロセス４１に含まれる結果出力部１２の出力結果（手順（１）でキー統合された統合処理部１３の出力結果も含む）に対して、統合処理部１３によるキー統合処理を行う。例えば、図７（ｃ）の１行目の抽出プロセスＰ１のキーリストは、図７（ｂ）の抽出プロセスＰ１のキーである、（Ａ，２）と（Ｂ，１）と（Ｂ，１）とを、（Ａ，２）と（Ｂ，２）とに統合した結果である。
【００３９】
計画指示部１５の実行手順（３）では、大粒度のキー統合処理を実行する。具体的には、データ処理システム１の抽出マシン４２を１つずつ選択し、その選択した抽出マシン４２に対してキー統合処理を行う旨が実行計画で指定されているときには、その選択した抽出マシン４２に含まれる結果出力部１２の出力結果（手順（１）または手順（２）でキー統合された統合処理部１３の出力結果も含む）に対して、統合処理部１３によるキー統合処理を行う。
【００４０】
図８は、データ解析部１１への入力データごと（例えば、文書ごと）に決まる値（例えば、抽出関数の実行番号）を用いた、キー統合処理を示す。
図８（ａ）では、キー名は、抽出関数の実行番号を示す。または、キー名は、抽出関数に対して入力されるレコード番号としてもよい。この場合は、抽出関数ごとに既に統合されている状態になり、かつ、レコード数が、図７（ｂ）と比較して削減されるため、通信量の削減やキーによるソート対象の削減を行うことができる。
図８（ｂ）では、レコード数が図７（ｃ）と比較して削減されるため、通信量の削減やキーによるソート対象の削減を行うことができる。
ただし、図８（ａ）の形式だとキー値のデータ構造が大きくなるため、図８（ｂ）で示すように抽出プロセス単位で統合した後、図８（ｃ）のようにキー値をばらすか、あるいは抽出マシン単位で統合した後にキー値をばらす必要がある。そして、図８（ｃ）のようにキー値をばらした後は、図７に書かれたキー統合処理となる。
【００４１】
図５は、計画指示部１５による実行計画の実行指示を示す第１例の説明図である。ここでの実行計画では、３段階での粒度のすべての構成要素において、キー統合処理を行うこととする。
計画指示部１５の実行手順（１）では、３つの結果出力部１２それぞれについて、統合処理部１３がキー統合処理を実行する。
計画指示部１５の実行手順（２）では、２つの抽出プロセス４１それぞれについて、統合処理部１３がキー統合処理を実行する。なお、抽出プロセス４１ｂでのキー統合処理は、抽出プロセス４１ｂに属する結果出力部１２が１つだけであり、その結果出力部１２でのキー統合処理をすでに実行手順（１）で実行しているので、省略してもよい。
計画指示部１５の実行手順（３）では、１つの抽出マシン４２について、統合処理部１３が実行手順（１）（２）での結果を入力とするキー統合処理を実行する。
【００４２】
図６は、計画指示部１５による実行計画の実行指示を示す第２例の説明図である。ここでの実行計画では、２段階での粒度（小粒度、大粒度）において、キー統合処理を行うこととする。図５との違いは、計画指示部１５の実行手順（２）が省略されている点である。このように、中間データ３２として同じ出力結果を出力する図５，図６の２つの統合処理でも、その実行計画が異なることによって、出力結果を生成するための処理内容が異なる。
【００４３】
以上説明した本実施形態では、統合処理部１３が実行するキー統合処理について、データ処理システム１のハードウェア構成やソフトウェア構成をもとにした「粒度」という概念を新たに定義し、その「粒度」を用いて、結果出力部１２の出力結果のうちのどの部分にどの程度のキー統合処理を適用するという統合計画を作成して、その統合計画を実行させることを特徴とする。
さらに、本実施形態では、統合計画を作成するときには、複数の粒度を構成する各粒度についてのキー統合処理を、複数段階で適用することも可能な実行計画の候補を列挙し、最も性能のよい実行計画を選択する。
【符号の説明】
【００４４】
１ データ処理システム
１０ キー抽出部
１１ データ解析部
１２ 結果出力部
１３ 統合処理部
２０ キー統合部
２１ 統合処理部
３１ 入力データ
３２ 中間データ
３３ 出力データ
４１ 抽出プロセス
４２ 抽出マシン
９０ 処理起動部
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法、および、データ処理プログラムに関する。
【背景技術】
【０００２】
非特許文献１のMapReduce処理システムは、大量の情報である入力データから、１つ以上のキーを抽出して（Map関数）、抽出された複数のキーを統合して（Reduce関数）、出力データとして出力する。１つのキーは、１つのキー名（key）と、１つのキー値（value）との組（key/value pair）として表現される。例えば、入力データをテキストの文書とすると、キー名は、文書内に出現する単語であり、キー値は、例えば、単語の出現回数である。出力されるキーは、例えば、機械学習処理や統計情報処理などの分析系の処理に応用される。
【０００３】
非特許文献１のMapReduceでは処理の高速化の機能としてCombine手段を有している。Combine手段では、Mapプロセス内で実行された全Map関数内で呼び出されるEmit関数の結果を入力としてReduce関数を実行することで、Combine手段を用いない標準的なMap処理手段と比較して、Reduce関数の実行によりEmit関数の結果データ量を削減する。その結果、MapReduce全体の性能向上を実現する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Jeffrey Dean and Sanjay Ghemawat,“MapReduce: Simplified Data Processing on Large Clusters”,OSDI'04: Sixth Symposium on Operating System Design and Implementation,San Francisco, CA, December, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
前記の非特許文献１のMapReduce処理システムにおけるCombine手段では、以下の２つの問題を解決していない。
【０００６】
１つ目の問題は、Combine手段を実行する前あるいはCombineを利用しない場合でも、Mapプロセス内においてEmit関数の結果をキー値でソートする必要があることから、Emit関数の呼び出し回数の多い処理では性能が劣化する傾向があることである。
例えば、webページなどのデータに対して単語の頻度計算の処理をする場合には、１ページ毎にMap関数が呼び出され、Map関数内では該当ページ内の単語毎にEmit関数が呼び出される実装が非特許文献１に記載されているが、この例では特にページサイズの大きいwebページを処理する場合に、Map関数あたりに呼び出されるEmit関数が非常に多くなり性能が劣化する傾向がある。
【０００７】
２つ目の問題は、シャッフル処理によってMapプロセスからReduceプロセスへとデータを配信する際の通信コストが大きいという問題である。
【０００８】
そこで、本発明は、前記した問題を解決し、MapReduce処理システムにおける性能を向上し、通信コストを下げることを、主な目的とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、本発明は、記憶手段から読み出した入力データに対してキー抽出処理を実行することで、キー名およびキー値の組であるキーを１つ以上抽出し、その結果を中間データとして前記記憶手段に書き込むキー抽出部と、前記記憶手段から読み出した前記中間データに対してキー統合処理を実行し、その結果を出力データとして前記記憶手段に書き込むキー統合部と、を有するデータ処理装置であって、前記キー抽出部が、データ解析部と、結果出力部と、統合処理部と、統合計画部と、計画指示部とを有し、前記データ解析部が、前記入力データを解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、前記結果出力部を呼び出し、前記結果出力部が、前記データ解析部から通知されたキーを、前記統合処理部へと出力し、前記統合処理部が、前記キー統合処理を実行するための実行計画に従って、前記結果出力部が出力する１つ以上のキーに対して前記キー統合処理を実行して、その結果を前記中間データとして前記記憶手段に書き込み、前記統合計画部が、前記キー抽出部を構成するための計算機環境に応じて定義される前記キー統合処理の実行粒度についての構成要素ごとに前記キー統合処理を行うか否かという組み合わせにより前記実行計画の候補を作成し、その作成した各候補に対して前記入力データの少なくとも一部を前記データ解析部に入力して動作させ、その実行時間が短いほど高評価とする評価方法により評価して、高評価の候補を前記実行計画として採用し、前記計画指示部が、前記統合計画部が採用した前記実行計画について、その前記実行計画の実行粒度が小さい順に前記統合処理部へと適用することを特徴とする。
さらに、本発明は、前記データ処理装置が前記各処理を実行するデータ処理方法である。
さらに、本発明は、前記データ処理方法を前記データ処理装置に実行させるためのためのデータ処理プログラムである。
【００１０】
これにより、実行粒度が規定されている実行計画に従ってキー統合処理を実行するので、MapReduce処理システムにおける性能を向上し、通信コストを下げることができる。
さらに、データ解析対象の実データを実際に試行して性能測定することにより、高精度の実行計画を作成することができる。
【００１１】
本発明は、前記統合計画部が、計算機環境に応じて定義される前記キー統合処理の実行粒度について、前記統合処理部が実行する実行関数ごとに前記キー統合処理を行うか否かという小粒度、１つ以上の前記結果出力部が属する抽出プロセスごとに前記キー統合処理を行うか否かという中粒度、および、１つ以上の前記抽出プロセスが属する抽出マシンごとに前記キー統合処理を行うか否かという大粒度という３段階の実行粒度をもとにした前記実行計画を作成することを特徴とする。
【００１２】
これにより、３段階の実行粒度を規定することにより、抽出プロセスというソフトウェア面での計算機環境と、抽出マシンというハードウェア面での計算機環境とが併せて考慮され、計算機環境に適した実行計画を作成することができる。
【００１３】
本発明は、前記統合処理部が、１つ以上のキーに対して前記キー統合処理を実行するときに、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキーを出力するとともに、統合対象である複数のキーのうちの異なるキー名をもつキーのキー値に対して、キー名をもとにソートすることで、キーの統合結果を作成することを特徴とする。
【００１４】
これにより、キー統合処理において、多くのキーを１つのキーへと統合することができ、中間データのデータ量を削減することができるとともに、キー統合部へ通知するキーの通信効率を向上させることができる。
【発明の効果】
【００１５】
本発明によれば、MapReduce処理システムにおける性能を向上し、通信コストを下げることができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に関するデータ処理システムを示す構成図である。
【図２】本発明の一実施形態に関するデータ処理システムにおけるキー抽出部およびキー統合部の詳細を示す構成図である。
【図３】本発明の一実施形態に関する統合計画部による実行計画の小粒度および中粒度を示す説明図である。
【図４】本発明の一実施形態に関する統合計画部による実行計画の大粒度を示す説明図である。
【図５】本発明の一実施形態に関する計画指示部による実行計画の実行指示を示す第１例の説明図である。
【図６】本発明の一実施形態に関する計画指示部による実行計画の実行指示を示す第２例の説明図である。
【図７】本発明の一実施形態に関する各粒度での統合処理の具体例を示す説明図である。
【図８】本発明の一実施形態に関するデータ解析部への入力データごとに決まる値を用いた、キー統合処理を示す説明図である。
【発明を実施するための形態】
【００１７】
以下、本発明の一実施形態を、図面を参照して詳細に説明する。
【００１８】
図１は、データ処理システム１（データ処理装置）を示す構成図である。データ処理システム１は、キー抽出部１０と、キー統合部２０と、処理起動部９０と、入力データ３１と、中間データ３２と、出力データ３３とを含めて構成される。なお、データ処理システム１は、様々なハードウェア構成およびソフトウェア構成として実現することができる。これらの構成の詳細は、図３以降で説明する。
【００１９】
処理起動部９０は、ユーザの操作を受け、キー抽出部１０およびキー統合部２０を起動する。さらに、処理起動部９０は、入力データ３１が入力されると、記憶手段に書き込む。
キー抽出部１０は、記憶手段から入力データ３１を読みだして、キー抽出処理を実行し、その結果を中間データ３２として記憶手段に書き込む。
キー統合部２０は、記憶手段から中間データ３２を読みだして（この読み出し処理を、シャッフル処理とも呼ぶ）、キー統合処理を実行し、その結果を出力データ３３として記憶手段に書き込む。
【００２０】
図２は、データ処理システム１におけるキー抽出部１０およびキー統合部２０の詳細を示す構成図である。
【００２１】
キー抽出部１０は、データ解析部１１と、結果出力部１２と、統合処理部１３と、統合計画部１４と、計画指示部１５とを含めて構成される。
データ解析部１１は、非特許文献１の「Map関数」に該当し、入力データ３１を解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、結果出力部１２を呼び出す。
結果出力部１２は、非特許文献１の「emit関数」に該当し、データ解析部１１から通知されたキーを、統合処理部１３または中間データ３２へと出力する。どちらに出力するかは、実行計画に従う。
統合処理部１３は、非特許文献１の「combine関数」に該当し、結果出力部１２の出力結果（または、結果出力部１２の出力結果に対して１回以上のキー統合処理が行われた結果）である複数のキーを、１つに統合してから中間データ３２に出力する。
【００２２】
キー統合部２０の統合処理部２１は、非特許文献１の「Reduce関数」に該当し、キー抽出部１０が入力データ３１から中間データ３２を作成した後に、その中間データ３２に対してキー統合処理を実行し、出力データ３３として出力する。なお、キー統合処理の処理内容は、統合処理部２１と統合処理部１３とで同じである。
【００２３】
【表１】
【００２４】
表１は、統合処理部１３、統合処理部２１によるキー統合処理の入力を示す。この表１の入力は、統合処理部１３がキー統合処理を行うときには、入力データ３１から結果出力部１２を介して出力される１つ以上のキーのリストであり、統合処理部２１がキー統合処理を行うときには、中間データ３２である。
表１では、１つの行が１つのキーである。例えば、１行目は、キー名が「Ａ」でキー値が「１」のキーを示す。以下、本実施形態では、キーを（キー名，キー値）と表現する。例えば、１行目のキーは、（Ａ，１）である。そして、本実施形態では、キーの説明の一例として、非特許文献１で記載されていた例と同じように、入力データ３１をテキストの文書（webページでもよい）とし、キー名を文書内に出現する単語とし、キー値を単語の出現回数として説明する。
なお、非特許文献１にあるように、統合処理部２１のReduce関数は可換および分配可能な演算を指定することが可能であり、本実施形態ではReduce関数として同一キー名のキー値の和を演算する例を示している。
【００２５】
キー統合処理は、例えば、以下の各処理である。
まず、同じキー名の統合処理では、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキー（統合対象となる同じキー名、統合演算結果のキー値）を出力する。例えば、表１では、（Ａ，１）のキーが３つ存在するので、統合演算としてキー値の加算処理を行うことにより、（Ａ，３）という１つのキーへと統合している。
次に、異なるキー名のソート処理では、統合対象である複数のキーについて、キー名をもとに、昇順または降順でソートする。例えば、表１では、キー名が「Ａ，Ｂ，Ｃ，Ｄ」の４種類あるので、この順にならぶようにソートする。なお、非特許文献１では、キー統合処理は、同じキー名の統合処理として記載されているので、この異なるキー名のソート処理は省略してもよい。
さらに、統合結果の圧縮処理は、同じキー名の統合処理および異なるキー名のソート処理の処理結果であるキーのリストに対して、データ圧縮する処理である。
【００２６】
【表２】
【００２７】
表２は、統合処理部１３、統合処理部２１によるキー統合処理の結果を示す。表１では８つ存在するキーが、表２では４つへと統合されている。これにより、キーの数を減らすことができるので、キーを送信するための通信効率を向上させることができる。
【００２８】
統合計画部１４は、データ解析部１１、および、統合処理部１３の各処理内容の特性から実行計画を作成して出力する。実行計画とは、結果出力部１２の出力結果であるキーに対して行われるキー統合処理の粒度を指定するデータである。キー統合処理の粒度には、例えば、以下に示す３種類の粒度がある。
【００２９】
以下、データ処理システム１の構成（抽出プロセス４１、抽出マシン４２）に着目して、図３〜図４で各粒度の詳細を説明する。なお、抽出マシン４２とは、１台のコンピュータである。このコンピュータは、ＣＰＵとメモリとハードディスク（記憶手段）とネットワークインタフェースを有する。ＣＰＵは、メモリ上に読み込んだプログラムを実行することにより、１つ以上の抽出プロセス４１を動作させる。１つの抽出プロセス４１上では、１つ以上の統合処理部１３が構成される。１つの統合処理部１３は、１つの実行関数を実行する。
【００３０】
図３（ａ）に示す小粒度（実行関数ごとの統合処理）とは、同じキー抽出部１０の結果出力部１２が出力する結果ごとに、統合処理部１３が結果をまとめる粒度である。なお、データ解析部１１は、１つの入力データ３１から、単語を発見するたびに結果出力部１２を呼び出すので、１つの結果出力部１２からは複数回のキーが出力される。よって、結果出力部１２ごとの粒度であっても、複数のキーを統合する処理が可能である。
【００３１】
図３（ｂ）に示す中粒度（抽出プロセス４１ごとの統合処理）とは、同じ抽出プロセス４１に属する１つ以上のキー抽出部１０の結果出力部１２が出力する結果ごとに、統合処理部１３が結果をまとめる粒度である。まず、左側の抽出プロセス４１ａには２つの結果出力部１２が存在するので、この２つの結果出力部１２から統合処理部１３により１回のキー統合処理が実行される。次に、右側の抽出プロセス４１ｂには１つの結果出力部１２が存在するので、この１つの結果出力部１２から統合処理部１３により１回のキー統合処理が実行される。
【００３２】
図４（ａ）に示す大粒度（抽出マシン４２ごとの統合処理）とは、同じ抽出マシン４２に属する１つ以上のキー抽出部１０の結果出力部１２が出力する結果ごとに、統合処理部１３が結果をまとめる粒度である。抽出マシン４２には３つの結果出力部１２が存在するので、この３つの結果出力部１２から統合処理部１３により１回のキー統合処理が実行される。
一方、図４（ｂ）のように、抽出マシン４２が異なる結果出力部１２どうしは、それぞれ異なる統合処理部１３によりキー統合処理が実行される。
【００３３】
以上図３および図４を参照して説明した複数種類の粒度をもとに、統合計画部１４は、各粒度（例えば、抽出プロセスという中粒度）についての構成要素（例えば、抽出プロセスＰ１）ごとにキー統合処理を行うか否かという組み合わせにより、実行計画の候補を作成する。例えば、以下が実行計画の候補の一例である。
抽出マシンＭ１：統合処理を行う。
抽出プロセスＰ１：統合処理を行う。
抽出プロセスＰ２：統合処理を行わない。
実行関数Ｆ１：統合処理を行わない。
実行関数Ｆ２：統合処理を行う。
実行関数Ｆ３：統合処理を行わない。
実行関数Ｆ４：統合処理を行う。
【００３４】
ここで、統合計画部１４は、実行計画を作成する際に、入力データ３１の少なくとも一部を利用してもよい。例えば、統合計画部１４は、データ解析部１１が解析対象として入力する入力データ３１の処理単位（例えば、単語抽出処理における処理対象の文書ごとに）を参照して、キー統合処理の粒度を決定してもよい。例えば、１つの文書が１つの抽出プロセス４１に割り当てられているときには、その抽出プロセス４１を粒度とするキー統合処理を有効に設定する。
【００３５】
そして、統合計画部１４は、実行計画の各候補を評価し、もっとも高評価の候補を実行計画として採用する。各候補の評価方法は、例えば、入力データ３１の少なくとも一部を対象として、実際にキー統合処理を実行させて、その性能（例えば、計算時間）を測定する（いわゆるベンチマーク）方法が挙げられる。
【００３６】
計画指示部１５は、以下の実行手順（１）〜（３）を順に実行することにより、統合計画部１４が作成した実行計画の実行を、各統合処理部１３に指示する。
図７は、各粒度での統合処理の具体例を示す説明図である。
図７（ａ）は、統合前のキーのリストであり、各キーを処理するために統合処理部１３が実行する実行関数と、その統合処理部１３が属する抽出プロセス４１と、その統合処理部１３が属する抽出マシン４２とが対応づけられている。
ただし、実行関数の記載について、例えばＦ１というのは、Ｆという関数を１番目に実行した結果として、(Ａ，１)，(Ａ，１)，(Ｂ，１)というキー（キー名とキー値との組）を３つ出力したということを意味する。
【００３７】
図７（ｂ）で示すように、計画指示部１５の実行手順（１）では、小粒度のキー統合処理を実行する。具体的には、データ処理システム１のキー抽出部１０内の各結果出力部１２を１つずつ選択し、その選択した結果出力部１２に対してキー統合処理を行う旨が実行計画で指定されているときには、その選択した結果出力部１２の出力結果に対して、統合処理部１３によるキー統合処理を行う。例えば、図７（ｂ）の１行目の実行関数Ｆ１のキーリストは、図７（ａ）の実行関数Ｆ１のキーである、２つの（Ａ，１）を１つに統合した結果である。このように、実行関数ごとにキー値を統合するため、データ量が削減できる。
【００３８】
図７（ｃ）で示すように、計画指示部１５の実行手順（２）では、中粒度のキー統合処理を実行する。具体的には、データ処理システム１の抽出プロセス４１を１つずつ選択し、その選択した抽出プロセス４１に対してキー統合処理を行う旨が実行計画で指定されているときには、その選択した抽出プロセス４１に含まれる結果出力部１２の出力結果（手順（１）でキー統合された統合処理部１３の出力結果も含む）に対して、統合処理部１３によるキー統合処理を行う。例えば、図７（ｃ）の１行目の抽出プロセスＰ１のキーリストは、図７（ｂ）の抽出プロセスＰ１のキーである、（Ａ，２）と（Ｂ，１）と（Ｂ，１）とを、（Ａ，２）と（Ｂ，２）とに統合した結果である。
【００３９】
計画指示部１５の実行手順（３）では、大粒度のキー統合処理を実行する。具体的には、データ処理システム１の抽出マシン４２を１つずつ選択し、その選択した抽出マシン４２に対してキー統合処理を行う旨が実行計画で指定されているときには、その選択した抽出マシン４２に含まれる結果出力部１２の出力結果（手順（１）または手順（２）でキー統合された統合処理部１３の出力結果も含む）に対して、統合処理部１３によるキー統合処理を行う。
【００４０】
図８は、データ解析部１１への入力データごと（例えば、文書ごと）に決まる値（例えば、抽出関数の実行番号）を用いた、キー統合処理を示す。
図８（ａ）では、キー名は、抽出関数の実行番号を示す。または、キー名は、抽出関数に対して入力されるレコード番号としてもよい。この場合は、抽出関数ごとに既に統合されている状態になり、かつ、レコード数が、図７（ｂ）と比較して削減されるため、通信量の削減やキーによるソート対象の削減を行うことができる。
図８（ｂ）では、レコード数が図７（ｃ）と比較して削減されるため、通信量の削減やキーによるソート対象の削減を行うことができる。
ただし、図８（ａ）の形式だとキー値のデータ構造が大きくなるため、図８（ｂ）で示すように抽出プロセス単位で統合した後、図８（ｃ）のようにキー値をばらすか、あるいは抽出マシン単位で統合した後にキー値をばらす必要がある。そして、図８（ｃ）のようにキー値をばらした後は、図７に書かれたキー統合処理となる。
【００４１】
図５は、計画指示部１５による実行計画の実行指示を示す第１例の説明図である。ここでの実行計画では、３段階での粒度のすべての構成要素において、キー統合処理を行うこととする。
計画指示部１５の実行手順（１）では、３つの結果出力部１２それぞれについて、統合処理部１３がキー統合処理を実行する。
計画指示部１５の実行手順（２）では、２つの抽出プロセス４１それぞれについて、統合処理部１３がキー統合処理を実行する。なお、抽出プロセス４１ｂでのキー統合処理は、抽出プロセス４１ｂに属する結果出力部１２が１つだけであり、その結果出力部１２でのキー統合処理をすでに実行手順（１）で実行しているので、省略してもよい。
計画指示部１５の実行手順（３）では、１つの抽出マシン４２について、統合処理部１３が実行手順（１）（２）での結果を入力とするキー統合処理を実行する。
【００４２】
図６は、計画指示部１５による実行計画の実行指示を示す第２例の説明図である。ここでの実行計画では、２段階での粒度（小粒度、大粒度）において、キー統合処理を行うこととする。図５との違いは、計画指示部１５の実行手順（２）が省略されている点である。このように、中間データ３２として同じ出力結果を出力する図５，図６の２つの統合処理でも、その実行計画が異なることによって、出力結果を生成するための処理内容が異なる。
【００４３】
以上説明した本実施形態では、統合処理部１３が実行するキー統合処理について、データ処理システム１のハードウェア構成やソフトウェア構成をもとにした「粒度」という概念を新たに定義し、その「粒度」を用いて、結果出力部１２の出力結果のうちのどの部分にどの程度のキー統合処理を適用するという統合計画を作成して、その統合計画を実行させることを特徴とする。
さらに、本実施形態では、統合計画を作成するときには、複数の粒度を構成する各粒度についてのキー統合処理を、複数段階で適用することも可能な実行計画の候補を列挙し、最も性能のよい実行計画を選択する。
【符号の説明】
【００４４】
１ データ処理システム
１０ キー抽出部
１１ データ解析部
１２ 結果出力部
１３ 統合処理部
２０ キー統合部
２１ 統合処理部
３１ 入力データ
３２ 中間データ
３３ 出力データ
４１ 抽出プロセス
４２ 抽出マシン
９０ 処理起動部
【特許請求の範囲】
【請求項１】
記憶手段から読み出した入力データに対してキー抽出処理を実行することで、キー名およびキー値の組であるキーを１つ以上抽出し、その結果を中間データとして前記記憶手段に書き込むキー抽出部と、
前記記憶手段から読み出した前記中間データに対してキー統合処理を実行し、その結果を出力データとして前記記憶手段に書き込むキー統合部と、を有するデータ処理装置であって、
前記キー抽出部は、データ解析部と、結果出力部と、統合処理部と、統合計画部と、計画指示部とを有し、
前記データ解析部は、前記入力データを解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、前記結果出力部を呼び出し、
前記結果出力部は、前記データ解析部から通知されたキーを、前記統合処理部へと出力し、
前記統合処理部は、前記キー統合処理を実行するための実行計画に従って、前記結果出力部が出力する１つ以上のキーに対して前記キー統合処理を実行して、その結果を前記中間データとして前記記憶手段に書き込み、
前記統合計画部は、前記キー抽出部を構成するための計算機環境に応じて定義される前記キー統合処理の実行粒度についての構成要素ごとに前記キー統合処理を行うか否かという組み合わせにより前記実行計画の候補を作成し、その作成した各候補に対して前記入力データの少なくとも一部を前記データ解析部に入力して動作させ、その実行時間が短いほど高評価とする評価方法により評価して、高評価の候補を前記実行計画として採用し、
前記計画指示部は、前記統合計画部が採用した前記実行計画について、その前記実行計画の実行粒度が小さい順に前記統合処理部へと適用することを特徴とする
データ処理装置。
【請求項２】
前記統合計画部は、計算機環境に応じて定義される前記キー統合処理の実行粒度について、
前記統合処理部が実行する実行関数ごとに前記キー統合処理を行うか否かという小粒度、
１つ以上の前記結果出力部が属する抽出プロセスごとに前記キー統合処理を行うか否かという中粒度、および、
１つ以上の前記抽出プロセスが属する抽出マシンごとに前記キー統合処理を行うか否かという大粒度という３段階の実行粒度をもとにした前記実行計画を作成することを特徴とする
請求項１に記載のデータ処理装置。
【請求項３】
前記統合処理部は、１つ以上のキーに対して前記キー統合処理を実行するときに、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキーを出力するとともに、統合対象である複数のキーのうちの異なるキー名をもつキーのキー値に対して、キー名をもとにソートすることで、キーの統合結果を作成することを特徴とする
請求項１または請求項２に記載のデータ処理装置。
【請求項４】
前記統合処理部は、前記結果出力部の複数の結果をまとめる際には、前記結果出力部のパラメータであるキー名およびキー値の組の組におけるキー名を用いて、同一のキー名と組をなすキー値を特定することで複数のキー値をまとめるか、あるいは、前記データ解析部に対する入力データごとに決まる値を用いて前記結果出力部のパラメータであるキー名およびキー値の組を共にまとめることを特徴とする
請求項１または請求項２に記載のデータ処理装置。
【請求項５】
記憶手段から読み出した入力データに対してキー抽出処理を実行することで、キー名およびキー値の組であるキーを１つ以上抽出し、その結果を中間データとして前記記憶手段に書き込むキー抽出部と、
前記記憶手段から読み出した前記中間データに対してキー統合処理を実行し、その結果を出力データとして前記記憶手段に書き込むキー統合部と、を有するデータ処理装置によるデータ処理方法であって、
前記キー抽出部は、データ解析部と、結果出力部と、統合処理部と、統合計画部と、計画指示部とを有し、
前記データ解析部は、前記入力データを解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、前記結果出力部を呼び出し、
前記結果出力部は、前記データ解析部から通知されたキーを、前記統合処理部へと出力し、
前記統合処理部は、前記キー統合処理を実行するための実行計画に従って、前記結果出力部が出力する１つ以上のキーに対して前記キー統合処理を実行して、その結果を前記中間データとして前記記憶手段に書き込み、
前記統合計画部は、前記キー抽出部を構成するための計算機環境に応じて定義される前記キー統合処理の実行粒度についての構成要素ごとに前記キー統合処理を行うか否かという組み合わせにより前記実行計画の候補を作成し、その作成した各候補に対して前記入力データの少なくとも一部を前記データ解析部に入力して動作させ、その実行時間が短いほど高評価とする評価方法により評価して、高評価の候補を前記実行計画として採用し、
前記計画指示部は、前記統合計画部が採用した前記実行計画について、その前記実行計画の実行粒度が小さい順に前記統合処理部へと適用することを特徴とする
データ処理方法。
【請求項６】
前記統合計画部は、計算機環境に応じて定義される前記キー統合処理の実行粒度について、
前記統合処理部が実行する実行関数ごとに前記キー統合処理を行うか否かという小粒度、
１つ以上の前記結果出力部が属する抽出プロセスごとに前記キー統合処理を行うか否かという中粒度、および、
１つ以上の前記抽出プロセスが属する抽出マシンごとに前記キー統合処理を行うか否かという大粒度という３段階の実行粒度をもとにした前記実行計画を作成することを特徴とする
請求項５に記載のデータ処理方法。
【請求項７】
前記統合処理部は、１つ以上のキーに対して前記キー統合処理を実行するときに、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキーを出力するとともに、統合対象である複数のキーのうちの異なるキー名をもつキーのキー値に対して、キー名をもとにソートすることで、キーの統合結果を作成することを特徴とする
請求項５または請求項６に記載のデータ処理方法。
【請求項８】
前記統合処理部は、前記結果出力部の複数の結果をまとめる際には、前記結果出力部のパラメータであるキー名およびキー値の組の組におけるキー名を用いて、同一のキー名と組をなすキー値を特定することで複数のキー値をまとめるか、あるいは、前記データ解析部に対する入力データごとに決まる値を用いて前記結果出力部のパラメータであるキー名およびキー値の組を共にまとめることを特徴とする
請求項５または請求項６に記載のデータ処理方法。
【請求項９】
請求項５ないし請求項８のいずれか１項に記載のデータ処理方法を、コンピュータである前記データ処理装置に実行させるためのデータ処理プログラム。
【請求項１】
記憶手段から読み出した入力データに対してキー抽出処理を実行することで、キー名およびキー値の組であるキーを１つ以上抽出し、その結果を中間データとして前記記憶手段に書き込むキー抽出部と、
前記記憶手段から読み出した前記中間データに対してキー統合処理を実行し、その結果を出力データとして前記記憶手段に書き込むキー統合部と、を有するデータ処理装置であって、
前記キー抽出部は、データ解析部と、結果出力部と、統合処理部と、統合計画部と、計画指示部とを有し、
前記データ解析部は、前記入力データを解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、前記結果出力部を呼び出し、
前記結果出力部は、前記データ解析部から通知されたキーを、前記統合処理部へと出力し、
前記統合処理部は、前記キー統合処理を実行するための実行計画に従って、前記結果出力部が出力する１つ以上のキーに対して前記キー統合処理を実行して、その結果を前記中間データとして前記記憶手段に書き込み、
前記統合計画部は、前記キー抽出部を構成するための計算機環境に応じて定義される前記キー統合処理の実行粒度についての構成要素ごとに前記キー統合処理を行うか否かという組み合わせにより前記実行計画の候補を作成し、その作成した各候補に対して前記入力データの少なくとも一部を前記データ解析部に入力して動作させ、その実行時間が短いほど高評価とする評価方法により評価して、高評価の候補を前記実行計画として採用し、
前記計画指示部は、前記統合計画部が採用した前記実行計画について、その前記実行計画の実行粒度が小さい順に前記統合処理部へと適用することを特徴とする
データ処理装置。
【請求項２】
前記統合計画部は、計算機環境に応じて定義される前記キー統合処理の実行粒度について、
前記統合処理部が実行する実行関数ごとに前記キー統合処理を行うか否かという小粒度、
１つ以上の前記結果出力部が属する抽出プロセスごとに前記キー統合処理を行うか否かという中粒度、および、
１つ以上の前記抽出プロセスが属する抽出マシンごとに前記キー統合処理を行うか否かという大粒度という３段階の実行粒度をもとにした前記実行計画を作成することを特徴とする
請求項１に記載のデータ処理装置。
【請求項３】
前記統合処理部は、１つ以上のキーに対して前記キー統合処理を実行するときに、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキーを出力するとともに、統合対象である複数のキーのうちの異なるキー名をもつキーのキー値に対して、キー名をもとにソートすることで、キーの統合結果を作成することを特徴とする
請求項１または請求項２に記載のデータ処理装置。
【請求項４】
前記統合処理部は、前記結果出力部の複数の結果をまとめる際には、前記結果出力部のパラメータであるキー名およびキー値の組の組におけるキー名を用いて、同一のキー名と組をなすキー値を特定することで複数のキー値をまとめるか、あるいは、前記データ解析部に対する入力データごとに決まる値を用いて前記結果出力部のパラメータであるキー名およびキー値の組を共にまとめることを特徴とする
請求項１または請求項２に記載のデータ処理装置。
【請求項５】
記憶手段から読み出した入力データに対してキー抽出処理を実行することで、キー名およびキー値の組であるキーを１つ以上抽出し、その結果を中間データとして前記記憶手段に書き込むキー抽出部と、
前記記憶手段から読み出した前記中間データに対してキー統合処理を実行し、その結果を出力データとして前記記憶手段に書き込むキー統合部と、を有するデータ処理装置によるデータ処理方法であって、
前記キー抽出部は、データ解析部と、結果出力部と、統合処理部と、統合計画部と、計画指示部とを有し、
前記データ解析部は、前記入力データを解析し、その中からキーを発見する度に、その発見したキーを呼び出しパラメータとして、前記結果出力部を呼び出し、
前記結果出力部は、前記データ解析部から通知されたキーを、前記統合処理部へと出力し、
前記統合処理部は、前記キー統合処理を実行するための実行計画に従って、前記結果出力部が出力する１つ以上のキーに対して前記キー統合処理を実行して、その結果を前記中間データとして前記記憶手段に書き込み、
前記統合計画部は、前記キー抽出部を構成するための計算機環境に応じて定義される前記キー統合処理の実行粒度についての構成要素ごとに前記キー統合処理を行うか否かという組み合わせにより前記実行計画の候補を作成し、その作成した各候補に対して前記入力データの少なくとも一部を前記データ解析部に入力して動作させ、その実行時間が短いほど高評価とする評価方法により評価して、高評価の候補を前記実行計画として採用し、
前記計画指示部は、前記統合計画部が採用した前記実行計画について、その前記実行計画の実行粒度が小さい順に前記統合処理部へと適用することを特徴とする
データ処理方法。
【請求項６】
前記統合計画部は、計算機環境に応じて定義される前記キー統合処理の実行粒度について、
前記統合処理部が実行する実行関数ごとに前記キー統合処理を行うか否かという小粒度、
１つ以上の前記結果出力部が属する抽出プロセスごとに前記キー統合処理を行うか否かという中粒度、および、
１つ以上の前記抽出プロセスが属する抽出マシンごとに前記キー統合処理を行うか否かという大粒度という３段階の実行粒度をもとにした前記実行計画を作成することを特徴とする
請求項５に記載のデータ処理方法。
【請求項７】
前記統合処理部は、１つ以上のキーに対して前記キー統合処理を実行するときに、統合対象である複数のキーのうちの同じキー名をもつキーのキー値に対して、統合演算を行うことで、１つのキーを出力するとともに、統合対象である複数のキーのうちの異なるキー名をもつキーのキー値に対して、キー名をもとにソートすることで、キーの統合結果を作成することを特徴とする
請求項５または請求項６に記載のデータ処理方法。
【請求項８】
前記統合処理部は、前記結果出力部の複数の結果をまとめる際には、前記結果出力部のパラメータであるキー名およびキー値の組の組におけるキー名を用いて、同一のキー名と組をなすキー値を特定することで複数のキー値をまとめるか、あるいは、前記データ解析部に対する入力データごとに決まる値を用いて前記結果出力部のパラメータであるキー名およびキー値の組を共にまとめることを特徴とする
請求項５または請求項６に記載のデータ処理方法。
【請求項９】
請求項５ないし請求項８のいずれか１項に記載のデータ処理方法を、コンピュータである前記データ処理装置に実行させるためのデータ処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−１１３４８６（Ｐ２０１１−１１３４８６Ａ）
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願番号】特願２００９−２７１７３６（Ｐ２００９−２７１７３６）
【出願日】平成２１年１１月３０日（２００９．１１．３０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願日】平成２１年１１月３０日（２００９．１１．３０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]