(57)【要約】  データフローグラフのノードに対する処理レイアウトの決定を行う技術。これらの技術は、データフローグラフを指定する情報を取得することであって、データフローグラフが、複数のノード、及び複数ノードを接続する複数のエッジを含み、複数のエッジが、複数のノードにおけるノード間のデータのフローを表し、複数のノードが、１つ又は複数のノードの第１のセットと、ノードの第１のセットから独立した、１つ又は複数のノードの第２のセットと、を含むことと、ノードの第１のセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、処理レイアウトの第１のセット、及び１つ又は複数のレイアウト決定ルールに基づいて、ノードの第２のセットにおける各ノードの処理レイアウトを決定することであって、１つ又は複数のレイアウト決定ルールが、異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含することと、を包含する。
2020512643.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのコンピュータハードウェアプロセッサと、
前記少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、
データフローグラフを指定する情報を取得することであって、前記データフローグラフが、複数のノード、及び前記複数ノードを接続する複数のエッジを含み、前記複数のエッジが、前記複数のノードにおけるノード間のデータのフローを表し、前記複数のノードが、
１つ又は複数のノードの第１のセットであって、前記ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、
１つ又は複数のノードの第２のセットであって、前記ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、
１つ又は複数のノードの第３のセットであって、前記ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、
を含むことと、
前記入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、
前記出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得することと、
前記処理レイアウトの第１のセット、前記処理レイアウトの第２のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する１つ又は複数のレイアウト決定ルールに基づいて、前記ノードの第３のセットにおける各ノードの処理レイアウトを決定することと、
を前記少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体と、
を含む、データ処理システム。
【請求項２】
前記入力データセットのセットが、第１の入力データセットと、第２の入力データセットとを包含し、前記ノードの第１のセットが、前記第１の入力データセットと関連付けられた第１のノードと、前記第２の入力データセットと関連付けられた第２のノードとを包含し、及び前記１つ又は複数の処理レイアウトの第１のセットを取得することが、
前記第１の入力データセットからデータを読み取るための第１の処理レイアウトを取得することであって、前記第１のレイアウトが、少なくとも部分的に、第１の度合いの並列性を指定することと、
前記第２の入力データセットからデータを読み取るための第２の処理レイアウトを取得することであって、前記第２の処理レイアウトが、前記少なくとも部分的に指定された第１の度合いの並列性とは異なる第２の度合いの並列性を少なくとも部分的に指定することと、
を含む、請求項１に記載のデータ処理システム。
【請求項３】
前記ノードの第１のセットが、前記入力データセットのセットにおける第１の入力データセットと関連付けられた第１のノードを包含し、
前記ノードの第２のセットが、前記出力データセットのセットにおける第１の出力データセットと関連付けられた第２のノードを包含し、
前記１つ又は複数の処理レイアウトの第１のセットを取得することが、前記第１の入力データセットからデータを読み取るための第１の処理レイアウトを取得することを含み、前記第１の処理レイアウトが、少なくとも部分的に、第１の度合いの並列性を指定し、及び
前記１つ又は複数の処理レイアウトの第２のセットを取得することが、前記第１の出力データセットにデータを書き込むための第２の処理レイアウトを取得することを含み、前記第２の処理レイアウトが、前記少なくとも部分的に指定された第１の度合いの並列性とは異なる第２の度合いの並列性を少なくとも部分的に指定する、請求項１又は２に記載のデータ処理システム。
【請求項４】
前記出力データセットのセットが、第１の出力データセットと、第２の出力データセットとを包含し、前記ノードの第２のセットが、前記第１の出力データセットと関連付けられた第１のノードと、前記第２の出力データセットと関連付けられた第２のノードとを包含し、及び前記１つ又は複数の処理レイアウトの第１のセットを取得することが、
前記第１の出力データセットにデータを書き込むための第１の処理レイアウトを取得することであって、前記第１のレイアウトが、少なくとも部分的に、第１の度合いの並列性を指定することと、
前記第２の出力データセットにデータを書き込むための第２の処理レイアウトを取得することであって、前記第２の処理レイアウトが、前記少なくとも部分的に指定された第１の度合いの並列性とは異なる第２の度合いの並列性を少なくとも部分的に指定することと、
を含む、請求項１又は２〜３のいずれか一項に記載のデータ処理システム。
【請求項５】
前記ノードの第３のセットにおける各ノードの処理レイアウトを決定することが、
前記データフローグラフの構造に従って、及び前記処理レイアウトの第１のセット及び前記１つ又は複数のレイアウト決定ルールを使用して、前記ノードの第１のセットにおけるノードから開始して行われる順方向パスで、前記第３のセットノードにおける１つ又は複数のノードの初期処理レイアウトを決定することと、
前記データフローグラフの構造に従って、及び前記処理レイアウトの第２のセット及び前記１つ又は複数のレイアウト決定ルールを使用して、前記ノードの第２のセットにおけるノードから開始して行われる逆方向パスで、前記ノードの第３のセットにおける各ノードの最終処理レイアウトを決定することと、
を含む、請求項１又は２〜４のいずれか一項に記載のデータ処理システム。
【請求項６】
前記ノードの第３のセットが、第１のノードを含み、前記複数のエッジが、前記第１のノードと、前記データフローグラフにおける前記第１のノードに先行する第２のノードとの間に第１のエッジを含み、及び前記ノードの第３のセットにおける各ノードの前記初期処理レイアウトを決定することが、
前記第２のノードに関して決定された処理レイアウトに基づいて、前記第１のノードの第１の初期処理レイアウトを決定することを含む、請求項１又は２〜５のいずれか一項に記載のデータ処理システム。
【請求項７】
前記複数のエッジが、前記第１のノードと、前記データフローグラフにおいて前記第１のノードに先行する第３のノードとの間に第２のエッジを含み、第３の初期処理レイアウトが、前記第３のノードに関連付けられ、及び前記第１のノードの前記第１の初期処理レイアウトを決定することが、
前記第２及び第３の処理レイアウトの一方を前記第１の処理レイアウトとして選択することを含む、請求項６又は１〜５のいずれか一項に記載のデータ処理システム。
【請求項８】
前記第２の初期処理レイアウトが、第１の度合いの並列性を指定し、前記第３の初期処理レイアウトが、前記第１の度合いの並列性とは異なる第２の度合いの並列性を指定し、及び前記選択が、
前記第１の度合いの並列性が、前記第２の度合いの並列性よりも大きい場合に、前記第２の処理レイアウトを選択することと、
前記第１の度合いの並列性が、前記第２の度合いの並列性よりも小さい場合に、前記第３の処理レイアウトを選択することと、
を含む、請求項７又は１〜６のいずれか一項に記載の処理システム。
【請求項９】
前記第２の初期処理レイアウト及び前記第３の初期処理レイアウトのそれぞれが、同じ度合いの並列性を指定し、前記第１のエッジが、第１の数のデータレコードのデータフローを表し、前記第２のエッジが、第２の数のデータレコードのデータフローを表し、及び前記選択が、
前記第１の数のデータレコードが、前記第２の数のデータレコードよりも多い場合に、前記第２の処理レイアウトを選択することと、
前記第１の数のデータレコードが、前記第２の数のデータレコードよりも少ない場合に、前記第３の処理レイアウトを選択することと、
を含む、請求項７又は１〜６又は８のいずれか一項に記載のデータ処理システム。
【請求項１０】
前記決定中に、第１の処理レイアウトが、ノードの第３のセットにおける第１のノードに関して決定され、前記第１の処理レイアウトが、第１の度合いの並列性を指定し、
前記グラフにおける前記第１のノードの直前の第２のノードに関する第２の処理レイアウトが、前記第１の度合いの並列性とは異なる第２の度合いの並列性を指定し、及び
前記プロセッサ実行可能命令がさらに、少なくとも１つの再パーティショニング動作を行うように前記データフローグラフの少なくとも１つのノードを構成することを前記少なくとも１つのコンピュータハードウェアプロセッサに行わせる、請求項１又は２〜９のいずれか一項に記載のデータ処理システム。
【請求項１１】
前記決定中に、第１の処理レイアウトが、ノードの第３のセットにおける第１のノードに関して決定され、前記第１の処理レイアウトが、第１の度合いの並列性を指定し、
前記グラフにおける前記第１のノードの直前の第２のノードに関する第２の処理レイアウトが、前記第１の度合いの並列性とは異なる第２の度合いの並列性を指定し、及び
前記プロセッサ実行可能命令がさらに、前記データフローグラフに対して、前記第１のノードと前記第２のノードとの間に新しいノードを追加することを前記少なくとも１つのコンピュータハードウェアプロセッサに行わせ、前記新しいノードが、少なくとも１つの再パーティショニング動作を表す、請求項１又は２〜１０のいずれか一項に記載のデータ処理システム。
【請求項１２】
前記少なくとも１つの再パーティショニング動作に関連付けられた前記新しいノードを追加することが、集約動作、マージ動作、又はパーティション動作に関連付けられたノードを追加することを含む、請求項１０又は１〜９、１１のいずれか一項に記載のデータ処理システム。
【請求項１３】
前記決定が、前記ノードの第３のセットにおける第１のノードに関する第１の処理レイアウトを決定することを含み、前記第１のノードが、第１のデータ処理動作を表し、及び前記第１の処理レイアウトを決定することが、
前記第１のデータ処理動作を行うための並列性の度合いを決定することと、
前記決定された並列性の度合いに従って、前記第１のデータ処理動作を行うための１つ又は複数のコンピューティングデバイスのセットを識別することと、
を含む、請求項１又は２〜１２のいずれか一項に記載のデータ処理システム。
【請求項１４】
前記第１の処理レイアウトを決定することが、
単一のプロセッサが前記第１のデータ処理動作を行うために使用されることを決定することと、
前記第１のデータ処理動作を行うためのコンピューティングデバイスを識別することと、
を含む、請求項１３又は１〜１２のいずれか一項に記載のデータ処理システム。
【請求項１５】
前記処理レイアウトの決定が、異なる度合いの並列性を有する処理レイアウトの中から選択するための前記少なくとも１つのルールを使用して行われる、請求項１又は２〜１４のいずれか一項に記載のデータ処理システム。
【請求項１６】
前記プロセッサ実行可能命令が、
前記データフローグラフにおける各ノードの前記処理レイアウトを決定した後に、前記データフローグラフにおける各ノードに関して決定された処理レイアウトに従って、前記データフローグラフを実行することを前記少なくとも１つのコンピュータハードウェアプロセッサに行わせる、請求項１又は２〜１５のいずれか一項に記載のデータ処理システム。
【請求項１７】
前記プロセッサ実行可能命令が、
構造化照会言語（ＳＱＬ）クエリーを受信することと、
前記ＳＱＬクエリーからクエリープランを生成することと、
前記生成されたクエリープランから前記データフローグラフを生成することと、
を前記少なくとも１つのコンピュータハードウェアプロセッサに行わせる、請求項１又は２〜１６のいずれか一項に記載のデータ処理システム。
【請求項１８】
前記少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、
データフローグラフを指定する情報を取得することであって、前記データフローグラフが、複数のノード、及び前記複数ノードを接続する複数のエッジを含み、前記複数のエッジが、前記複数のノードにおけるノード間のデータのフローを表し、前記複数のノードが、
１つ又は複数のノードの第１のセットであって、前記ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、
１つ又は複数のノードの第２のセットであって、前記ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、
１つ又は複数のノードの第３のセットであって、前記ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、
を含むことと、
前記入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、
前記出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得することと、
前記処理レイアウトの第１のセット、前記処理レイアウトの第２のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する１つ又は複数のレイアウト決定ルールに基づいて、前記ノードの第３のセットにおける各ノードの処理レイアウトを決定することと、
を前記少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体。
【請求項１９】
前記少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、プロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体であって、前記プロセッサ実行可能命令が、
データフローグラフを指定する情報を取得するための手段であって、前記データフローグラフが、複数のノード、及び前記複数ノードを接続する複数のエッジを含み、前記複数のエッジが、前記複数のノードにおけるノード間のデータのフローを表し、前記複数のノードが、
１つ又は複数のノードの第１のセットであって、前記ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、
１つ又は複数のノードの第２のセットであって、前記ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、
１つ又は複数のノードの第３のセットであって、前記ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、
を含む、手段と、
前記入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得するための手段と、
前記出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得するための手段と、
前記処理レイアウトの第１のセット、前記処理レイアウトの第２のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する１つ又は複数のレイアウト決定ルールに基づいて、前記ノードの第３のセットにおける各ノードの処理レイアウトを決定するための手段と、
を含む、少なくとも１つの非一時的コンピュータ可読ストレージ媒体。
【請求項２０】
少なくとも１つのコンピュータハードウェアプロセッサを使用して、
データフローグラフを指定する情報を取得することであって、前記データフローグラフが、複数のノード、及び前記複数ノードを接続する複数のエッジを含み、前記複数のエッジが、前記複数のノードにおけるノード間のデータのフローを表し、前記複数のノードが、
１つ又は複数のノードの第１のセットであって、前記ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、
１つ又は複数のノードの第２のセットであって、前記ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、
１つ又は複数のノードの第３のセットであって、前記ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、
を含むことと、
前記入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、
前記出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得することと、
前記処理レイアウトの第１のセット、前記処理レイアウトの第２のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する１つ又は複数のレイアウト決定ルールに基づいて、前記ノードの第３のセットにおける各ノードの処理レイアウトを決定することと、
を行うことを含む、方法。
【請求項２１】
前記入力データセットのセットが、第１の入力データセットと、第２の入力データセットとを包含し、前記ノードの第１のセットが、前記第１の入力データセットと関連付けられた第１のノードと、前記第２の入力データセットと関連付けられた第２のノードとを包含し、及び前記１つ又は複数の処理レイアウトの第１のセットを取得することが、
前記第１の入力データセットからデータを読み取るための第１の処理レイアウトを取得することであって、前記第１のレイアウトが、少なくとも部分的に、第１の度合いの並列性を指定することと、
前記第２の入力データセットからデータを読み取るための第２の処理レイアウトを取得することであって、前記第２の処理レイアウトが、前記少なくとも部分的に指定された第１の度合いの並列性とは異なる第２の度合いの並列性を少なくとも部分的に指定することと、
を含む、請求項２０に記載の方法。
【請求項２２】
前記ノードの第１のセットが、前記入力データセットのセットにおける第１の入力データセットと関連付けられた第１のノードを包含し、
前記ノードの第２のセットが、前記出力データセットのセットにおける第１の出力データセットと関連付けられた第２のノードを包含し、
前記１つ又は複数の処理レイアウトの第１のセットを取得することが、前記第１の入力データセットからデータを読み取るための第１の処理レイアウトを取得することを含み、前記第１の処理レイアウトが、少なくとも部分的に、第１の度合いの並列性を指定し、及び
前記１つ又は複数の処理レイアウトの第２のセットを取得することが、前記第１の出力データセットにデータを書き込むための第２の処理レイアウトを取得することを含み、前記第２の処理レイアウトが、前記少なくとも部分的に指定された第１の度合いの並列性とは異なる第２の度合いの並列性を少なくとも部分的に指定する、請求項２０又は２１に記載の方法。
【請求項２３】
前記出力データセットのセットが、第１の出力データセットと、第２の出力データセットとを包含し、前記ノードの第２のセットが、前記第１の出力データセットと関連付けられた第１のノードと、前記第２の出力データセットと関連付けられた第２のノードとを包含し、及び前記１つ又は複数の処理レイアウトの第１のセットを取得することが、
前記第１の出力データセットにデータを書き込むための第１の処理レイアウトを取得することであって、前記第１のレイアウトが、少なくとも部分的に、第１の度合いの並列性を指定することと、
前記第２の出力データセットにデータを書き込むための第２の処理レイアウトを取得することであって、前記第２の処理レイアウトが、前記少なくとも部分的に指定された第１の度合いの並列性とは異なる第２の度合いの並列性を少なくとも部分的に指定することと、
を含む、請求項２０又は２１〜２２のいずれか一項に記載の方法。
【請求項２４】
前記ノードの第３のセットにおける各ノードの処理レイアウトを決定することが、
前記データフローグラフの構造に従って、及び前記処理レイアウトの第１のセット及び前記１つ又は複数のレイアウト決定ルールを使用して、前記ノードの第１のセットにおけるノードから開始して行われる順方向パスで、前記第３のセットノードにおける１つ又は複数のノードの初期処理レイアウトを決定することと、
前記データフローグラフの構造に従って、及び前記処理レイアウトの第２のセット及び前記１つ又は複数のレイアウト決定ルールを使用して、前記ノードの第２のセットにおけるノードから開始して行われる逆方向パスで、前記ノードの第３のセットにおける各ノードの最終処理レイアウトを決定することと、
を含む、請求項２０又は２１〜２３のいずれか一項に記載の方法。
【請求項２５】
前記ノードの第３のセットが、第１のノードを含み、前記複数のエッジが、前記第１のノードと、前記データフローグラフにおける前記第１のノードに先行する第２のノードとの間に第１のエッジを含み、及び前記第３のセットノードにおける各ノードの前記初期処理レイアウトを決定することが、
前記第２のノードに関して決定された処理レイアウトに基づいて、前記第１のノードの第１の初期処理レイアウトを決定することを含む、請求項２０又は２１〜２４のいずれか一項に記載の方法。
【請求項２６】
前記複数のエッジが、前記第１のノードと、前記データフローグラフにおいて前記第１のノードに先行する第３のノードとの間に第２のエッジを含み、第３の初期処理レイアウトが、前記第３のノードに関連付けられ、及び前記第１のノードの前記第１の初期処理レイアウトを決定することが、
前記第２及び第３の処理レイアウトの一方を前記第１の処理レイアウトとして選択することを含む、請求項２５又は２０〜２４のいずれか一項に記載の方法。
【請求項２７】
前記第２の初期処理レイアウトが、第１の度合いの並列性を指定し、前記第３の初期処理レイアウトが、前記第１の度合いの並列性とは異なる第２の度合いの並列性を指定し、及び前記選択が、
前記第１の度合いの並列性が、前記第２の度合いの並列性よりも大きい場合に、前記第２の処理レイアウトを選択することと、
前記第１の度合いの並列性が、前記第２の度合いの並列性よりも小さい場合に、前記第３の処理レイアウトを選択することと、
を含む、請求項２６又は２０〜２５のいずれか一項に記載の方法。
【請求項２８】
前記第２の初期処理レイアウト及び前記第３の初期処理レイアウトのそれぞれが、同じ度合いの並列性を指定し、前記第１のエッジが、第１の数のデータレコードのデータフローを表し、前記第２のエッジが、第２の数のデータレコードのデータフローを表し、及び前記選択が、
前記第１の数のデータレコードが、前記第２の数のデータレコードよりも多い場合に、前記第２の処理レイアウトを選択することと、
前記第１の数のデータレコードが、前記第２の数のデータレコードよりも少ない場合に、前記第３の処理レイアウトを選択することと、
を含む、請求項２６又は２０〜２５、２７のいずれか一項に記載の方法。
【請求項２９】
前記決定中に、第１の処理レイアウトが、ノードの第３のセットにおける第１のノードに関して決定され、前記第１の処理レイアウトが、第１の度合いの並列性を指定し、
前記グラフにおける前記第１のノードの直前の第２のノードに関する第２の処理レイアウトが、前記第１の度合いの並列性とは異なる第２の度合いの並列性を指定し、及び
前記少なくとも１つのコンピュータハードウェアプロセッサがさらに、少なくとも１つの再パーティショニング動作を行うように前記データフローグラフの少なくとも１つのノードを構成する、請求項２０又は２１〜２８のいずれか一項に記載の方法。
【請求項３０】
前記決定中に、第１の処理レイアウトが、ノードの第３のセットにおける第１のノードに関して決定され、前記第１の処理レイアウトが、第１の度合いの並列性を指定し、
前記グラフにおける前記第１のノードの直前の第２のノードに関する第２の処理レイアウトが、前記第１の度合いの並列性とは異なる第２の度合いの並列性を指定し、及び
前記少なくとも１つのコンピュータハードウェアプロセッサが、前記データフローグラフに対して、前記第１のノードと前記第２のノードとの間に新しいノードを追加するように構成され、前記新しいノードが、少なくとも１つの再パーティショニング動作を表す、請求項２０又は２１〜２９のいずれか一項に記載の方法。
【請求項３１】
前記少なくとも１つの再パーティショニング動作に関連付けられた前記新しいノードを追加することが、集約動作、マージ動作、又はパーティション動作に関連付けられたノードを追加することを含む、請求項３０又は２０〜２９のいずれか一項に記載の方法。
【請求項３２】
前記決定が、前記ノードの第３のセットにおける第１のノードに関する第１の処理レイアウトを決定することを含み、前記第１のノードが、第１のデータ処理動作を表し、及び前記第１の処理レイアウトを決定することが、
前記第１のデータ処理動作を行うための並列性の度合いを決定することと、
前記決定された並列性の度合いに従って、前記第１のデータ処理動作を行うための１つ又は複数のコンピューティングデバイスのセットを識別することと、
を含む、請求項２０又は２１〜３１のいずれか一項に記載の方法。
【請求項３３】
前記第１の処理レイアウトを決定することが、
単一のプロセッサが前記第１のデータ処理動作を行うために使用されることを決定することと、
前記第１のデータ処理動作を行うためのコンピューティングデバイスを識別することと、
を含む、請求項３２又は２０〜３１のいずれか一項に記載の方法。
【請求項３４】
前記処理レイアウトの決定が、異なる度合いの並列性を有する処理レイアウトの中から選択するための前記少なくとも１つのルールを使用して行われる、請求項２０又は２１〜３３のいずれか一項に記載の方法。
【請求項３５】
前記データフローグラフにおける各ノードの前記処理レイアウトを決定した後に、前記データフローグラフにおける各ノードに関して決定された処理レイアウトに従って、前記データフローグラフを実行することをさらに含む、請求項２０又は２１〜３４のいずれか一項に記載の方法。
【請求項３６】
構造化照会言語（ＳＱＬ）クエリーを受信することと、
前記ＳＱＬクエリーからクエリープランを生成することと、
前記生成されたクエリープランから前記データフローグラフを生成することと、
をさらに含む、請求項２０又は２１〜３５のいずれか一項に記載の方法。
【請求項３７】
少なくとも１つのコンピュータハードウェアプロセッサと、
前記少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、
データフローグラフを指定する情報を取得することであって、前記データフローグラフが、複数のノード、及び前記複数ノードを接続する複数のエッジを含み、前記複数のエッジが、前記複数のノードにおけるノード間のデータのフローを表し、前記複数のノードが、
１つ又は複数のノードの第１のセットと、
前記ノードの第１のセットから独立した、１つ又は複数のノードの第２のセットと、
を含むことと、
前記ノードの第１のセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、
前記処理レイアウトの第１のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する１つ又は複数のレイアウト決定ルールに基づいて、前記ノードの第２のセットにおける各ノードの処理レイアウトを決定することと、
を前記少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体と、
を含む、データ処理システム。
【請求項３８】
前記１つ又は複数のノードの第１のセットが、
１つ又は複数の入力ノードのセットであって、前記入力ノードのセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数の入力ノードのセットと、
１つ又は複数の出力ノードのセットであって、前記出力ノードのセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数の出力ノードのセットと、
を包含し、及び
前記第１のセット処理レイアウトを取得することが、
前記入力データセットのセットに関する１つ又は複数の処理レイアウトのセットを取得することと、
前記出力データセットのセットに関する１つ又は複数の処理レイアウトのセットを取得することと、
を含む、請求項３７に記載のデータ処理システム。
【請求項３９】
少なくとも１つのコンピュータハードウェアプロセッサと、
前記少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、
前記少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、前記少なくとも１つのコンピュータハードウェアプロセッサにデータベースクエリーを実行させるコンピュータコードを取得することであって、前記コンピュータコードが、
それぞれの入力データセットを読み込むデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第１のセットと、
それぞれの出力データセットを書き出すデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第２のセットと、
それぞれのデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第３のセットと、
を含むことと、
前記コード部分の第１のセットにおける１つ又は複数のコード部分に関する１つ又は複数の処理レイアウトの第１のセットを取得することと、
前記コード部分の第２のセットにおける１つ又は複数のコード部分に関する１つ又は複数の処理レイアウトの第２のセットを取得することと、
前記処理レイアウトの第１のセット、前記処理レイアウトの第２のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する１つ又は複数のレイアウト決定ルールに基づいて、前記コード部分の第３のセットにおける各コード部分の処理レイアウトを決定することと、
を前記少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体と、
を含む、データ処理システム。
【請求項４０】
前記決定が、前記コンピュータコードの少なくとも幾つかのコンピュータコード部分の実行順序を少なくとも部分的に示す情報にさらに基づいて行われる、請求項３９又は３７〜３８のいずれか一項に記載のデータ処理システム。
【請求項４１】
前記コンピュータコードが、データフローグラフに関連付けられ、
前記データフローグラフが、複数のノード、及び前記複数ノードを接続する複数のエッジを含み、前記複数のエッジが、前記複数のノードにおけるノード間のデータのフローを表し、及び
前記コンピュータコードのコンピュータコード部分が、前記データフローグラフにおけるそれぞれのノードと関連付けられる、請求項３９に記載のデータ処理システム。
【請求項４２】
前記複数のノードが、
１つ又は複数のノードの第１のセットであって、前記ノードの第１のセットにおける各ノードが、それぞれの入力データセットを表し、前記コンピュータコード部分の第１のセットの各コンピュータコード部分が、前記ノードの第１のセットにおけるそれぞれのノードと関連付けられる、１つ又は複数のノードの第１のセットと、
１つ又は複数のノードの第２のセットであって、前記ノードの第２のセットにおける各ノードが、それぞれの出力データセットを表し、前記コンピュータコード部分の第２のセットの各コンピュータコード部分が、前記ノードの第２のセットにおけるそれぞれのノードと関連付けられる、１つ又は複数のノードの第２のセットと、
１つ又は複数のノードの第３のセットであって、前記ノードの第３のセットにおける各ノードが、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、
を含む、請求項４１又は３７〜４０のいずれか一項に記載のデータ処理システム。
【請求項４３】
前記処理レイアウトの決定が、異なる度合いの並列性を有する処理レイアウトの中から選択するための前記少なくとも１つのルールを使用して行われる、請求項４１又は３７〜４０、４２のいずれか一項に記載のデータ処理システム。
【請求項４４】
前記プロセッサ実行可能命令が、
前記データフローグラフにおける各ノードの前記処理レイアウトを決定した後に、前記データフローグラフにおける各ノードに関して決定された処理レイアウトに従って、前記データフローグラフを実行することを前記少なくとも１つのコンピュータハードウェアプロセッサに行わせる、請求項４１又は３７〜４０、４２〜４３のいずれか一項に記載のデータ処理システム。
【請求項４５】
前記プロセッサ実行可能命令が、
構造化照会言語（ＳＱＬ）クエリーを受信することと、
前記ＳＱＬクエリーからクエリープランを生成することと、
前記クエリープランから前記コンピュータコードを生成することと、
を前記少なくとも１つのコンピュータハードウェアプロセッサに行わせる、請求項４１又は３７〜４０、４２〜４４のいずれか一項に記載のデータ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、米国特許法第１１９条（ｅ）に基づいて、本明細書に全体として援用される、２０１７年３月２９日に出願された、「可変レベル並列性を用いたデータ処理動作を行うためのシステム及び方法」というタイトルの米国仮特許出願第６２／４７８，３９０号明細書の便益を主張するものである。
【背景技術】
【０００２】
データ処理システムは、１つ又は複数のコンピュータプログラムを使用して、データを処理し得る。データ処理システムによって利用されるコンピュータプログラムの１つ又は複数は、データフローグラフとして展開され得る。データフローグラフは、入力データに対して行われるデータ処理動作、及びデータのフローを表すコンポーネント間のリンクを表す、「ノード」又は「節点」と呼ばれるコンポーネントを包含し得る。データフローグラフのノードは、各入力データセットを表す１つ又は複数の入力ノード、各出力データセットを表す１つ又は複数の出力ノード、及びデータに対して行われるデータ処理動作を表す１つ又は複数のノードを包含し得る。データフローグラフによってエンコードされる計算を実行するための技術が、それぞれ本明細書に全体として援用される、「グラフとして表現される計算の実行（Ｅｘｅｃｕｔｉｎｇ  Ｃｏｍｐｕｔａｔｉｏｎｓ  Ｅｘｐｒｅｓｓｅｄ  ａｓ  Ｇｒａｐｈｓ）」というタイトルの米国特許第５，９６６，０７２号明細書、及び「グラフベース計算のパラメータ管理（Ｍａｎａｇｉｎｇ  Ｐａｒａｍｅｔｅｒｓ  ｆｏｒ  Ｇｒａｐｈ−Ｂａｓｅｄ  Ｃｏｍｐｕｔａｔｉｏｎｓ）」というタイトルの米国特許第７，７１６，６３０号明細書に記載されている。
【発明の概要】
【課題を解決するための手段】
【０００３】
幾つかの実施形態が、データ処理システムに向けられる。データ処理システムは、少なくとも１つのコンピュータハードウェアプロセッサと、少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、（Ａ）データフローグラフを指定する情報を取得することであって、データフローグラフが、複数のノード、及び複数ノードを接続する複数のエッジを含み、複数のエッジが、複数のノードにおけるノード間のデータのフローを表し、複数のノードが、１つ又は複数のノードの第１のセットであって、ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、１つ又は複数のノードの第２のセットであって、ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、１つ又は複数のノードの第３のセットであって、ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、を含むことと、（Ｂ）入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、（Ｃ）出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得することと、（Ｄ）処理レイアウトの第１のセット、処理レイアウトの第２のセット、及び１つ又は複数のレイアウト決定ルールに基づいて、ノードの第３のセットにおける各ノードの処理レイアウトを決定することであって、１つ又は複数のレイアウト決定ルールが、異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含することと、を少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体と、を含む。
【０００４】
幾つかの実施形態は、少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、（Ａ）データフローグラフを指定する情報を取得することであって、データフローグラフが、複数のノード、及び複数ノードを接続する複数のエッジを含み、複数のエッジが、複数のノードにおけるノード間のデータのフローを表し、複数のノードが、１つ又は複数のノードの第１のセットであって、ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、１つ又は複数のノードの第２のセットであって、ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、１つ又は複数のノードの第３のセットであって、ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、を含むことと、（Ｂ）入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、（Ｃ）出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得することと、（Ｄ）処理レイアウトの第１のセット、処理レイアウトの第２のセット、及び１つ又は複数のレイアウト決定ルールに基づいて、ノードの第３のセットにおける各ノードの処理レイアウトを決定することであって、１つ又は複数のレイアウト決定ルールが、異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含することと、を少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体に向けられる。
【０００５】
幾つかの実施形態は、少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、プロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体であって、プロセッサ実行可能命令が、（Ａ）データフローグラフを指定する情報を取得するための手段であって、データフローグラフが、複数のノード、及び複数ノードを接続する複数のエッジを含み、複数のエッジが、複数のノードにおけるノード間のデータのフローを表し、複数のノードが、１つ又は複数のノードの第１のセットであって、ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、１つ又は複数のノードの第２のセットであって、ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、１つ又は複数のノードの第３のセットであって、ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、を含む、手段と、（Ｂ）入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得するための手段と、（Ｃ）出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得するための手段と、（Ｄ）処理レイアウトの第１のセット、処理レイアウトの第２のセット、及び１つ又は複数のレイアウト決定ルールに基づいて、ノードの第３のセットにおける各ノードの処理レイアウトを決定するための手段であって、１つ又は複数のレイアウト決定ルールが、異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する、手段と、を含む、少なくとも１つの非一時的コンピュータ可読ストレージ媒体に向けられる。
【０００６】
幾つかの実施形態は、少なくとも１つのコンピュータハードウェアプロセッサを使用して、（Ａ）データフローグラフを指定する情報を取得することであって、データフローグラフが、複数のノード、及び複数ノードを接続する複数のエッジを含み、複数のエッジが、複数のノードにおけるノード間のデータのフローを表し、複数のノードが、１つ又は複数のノードの第１のセットであって、ノードの第１のセットにおける各ノードが、１つ又は複数の入力データセットのセットにおけるそれぞれの入力データセットを表す、１つ又は複数のノードの第１のセットと、１つ又は複数のノードの第２のセットであって、ノードの第２のセットにおける各ノードが、１つ又は複数の出力データセットのセットにおけるそれぞれの出力データセットを表す、１つ又は複数のノードの第２のセットと、１つ又は複数のノードの第３のセットであって、ノードの第３のセットにおける各ノードが、少なくとも１つの、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットと、を含むことと、（Ｂ）入力データセットのセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、（Ｃ）出力データセットのセットに関する１つ又は複数の処理レイアウトの第２のセットを取得することと、（Ｄ）処理レイアウトの第１のセット、処理レイアウトの第２のセット、及び１つ又は複数のレイアウト決定ルールに基づいて、ノードの第３のセットにおける各ノードの処理レイアウトを決定することであって、１つ又は複数のレイアウト決定ルールが、異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含することと、を行うことを含む方法に向けられる。
【０００７】
幾つかの実施形態は、データ処理システムに向けられる。データ処理システムは、少なくとも１つのコンピュータハードウェアプロセッサと、少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、（Ａ）データフローグラフを指定する情報を取得することであって、データフローグラフが、複数のノード、及び複数ノードを接続する複数のエッジを含み、複数のエッジが、複数のノードにおけるノード間のデータのフローを表し、複数のノードが、１つ又は複数のノードの第１のセットと、ノードの第１のセットから独立した、１つ又は複数のノードの第２のセットと、を含むことと、（Ｂ）ノードの第１のセットに関する１つ又は複数の処理レイアウトの第１のセットを取得することと、（Ｃ）処理レイアウトの第１のセット、及び１つ又は複数のレイアウト決定ルールに基づいて、ノードの第２のセットにおける各ノードの処理レイアウトを決定することであって、１つ又は複数のレイアウト決定ルールが、異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含することと、を少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体と、を含む。
【０００８】
幾つかの実施形態は、データ処理システムに向けられる。データ処理システムは、少なくとも１つのコンピュータハードウェアプロセッサと、少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、（Ａ）少なくとも１つのコンピュータハードウェアプロセッサによって実行されると、少なくとも１つのコンピュータハードウェアプロセッサにデータベースクエリーを実行させるコンピュータコードを取得することであって、コンピュータコードが、それぞれの入力データセットを読み込むデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第１のセットと、それぞれの出力データセットを書き出すデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第２のセットと、それぞれのデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第３のセットと、を含むことと、（Ｂ）コード部分の第１のセットにおける１つ又は複数のコード部分に関する１つ又は複数の処理レイアウトの第１のセットを取得することと、（Ｃ）コード部分の第２のセットにおける１つ又は複数のコード部分に関する１つ又は複数の処理レイアウトの第２のセットを取得することと、（Ｄ）処理レイアウトの第１のセット、処理レイアウトの第２のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する１つ又は複数のレイアウト決定ルールに基づいて、コード部分の第３のセットにおける各コード部分の処理レイアウトを決定することと、を少なくとも１つのコンピュータハードウェアプロセッサに行わせるプロセッサ実行可能命令を保存する、少なくとも１つの非一時的コンピュータ可読ストレージ媒体と、を含む。
【０００９】
上記は、添付の特許請求の範囲によって定義される本発明の非限定的概要である。
【００１０】
以下の図面を参照して、様々な態様及び実施形態を説明する。これらの図面は、必ずしも一定の縮尺で描かれていないことが理解されるものとする。複数の図面に現れるアイテムは、それらが現れる全ての図面において、同じ又は類似の参照番号で示される。
【図面の簡単な説明】
【００１１】
【図１Ａ】各ノードが同じ処理レイアウトと関連付けられた、説明のためのデータフローグラフの図である。
【図１Ｂ】本明細書に記載の技術の幾つかの実施形態による、ノードの第１のセットにおけるノードに関して異なる処理レイアウトを有し、及びノードの第２のセットにおけるノードに関して決定された処理レイアウトを持たない、説明のためのデータフローグラフの図である。
【図１Ｃ】本明細書に記載の技術の幾つかの実施形態による、ノードの第２のセットにおけるノードに関して決定された処理レイアウト、及びそれぞれの再パーティショニング動作と関連付けられた挿入ノードを示す、図１Ｂの説明のためのデータフローグラフの図である。
【図２】本明細書に記載の技術の幾つかの実施形態による、少なくとも部分的に、データフローグラフのノードの処理レイアウトを決定することによって、データフローグラフの処理構成を決定するための、説明のためのプロセスのフローチャートである。
【図３Ａ−３Ｄ】本明細書に記載の技術の幾つかの実施形態による、１つ又は複数の処理レイアウト決定ルールを使用した、説明のためのデータフローグラフのノードの処理レイアウトの決定を示す。
【図４Ａ−４Ｃ】本明細書に記載の技術の幾つかの実施形態による、１つ又は複数のレイアウト決定ルールを使用した、別の説明のためのデータフローグラフのノードの処理レイアウトの決定を示す。
【図５Ａ−５Ｄ】本明細書に記載の技術の幾つかの実施形態による、１つ又は複数のレイアウト決定ルールを使用した、さらに別の説明のためのデータフローグラフのノードの処理レイアウトの決定を示す。
【図６】本明細書に記載の技術の幾つかの実施形態が動作し得る、説明のためのコンピューティング環境のブロック図である。
【図７】本明細書に記載する技術の幾つかの実施形態の実施に使用することができる、説明のためのコンピューティングシステム環境のブロック図である。
【発明を実施するための形態】
【００１２】
本明細書に記載する技術の局面は、データフローグラフを用いてデータ処理動作を行うための従来の技術を改良することによって、データ処理システムの速度及びスループットを向上させることに関係する。
【００１３】
上述の通り、データフローグラフのノードは、１つ又は複数の入力データセットからアクセスされたデータに適用され得る各データ処理動作を表し得る。データ処理動作をデータに適用する前に、データ処理動作を行うための処理レイアウトが決定される必要がある。処理レイアウトは、データ処理動作を行うために何個のコンピューティングデバイスが使用されるかを指定し、及び使用される特定のコンピューティングデバイスを識別し得る。従って、データ処理システムが、データフローグラフを用いてデータを処理し得る前に、データフローグラフにおけるノードの処理レイアウトが決定される必要がある。
【００１４】
データフローグラフにおけるノードの処理レイアウトを自動的に決定するための幾つかの従来の技術は、全ての処理レイアウトが同じ度合いの並列性を有するように、処理レイアウトをグラフの各ノードに割り当てることを伴う。例えば、グラフの各ノードは、データフローグラフのノードによって表されるデータ処理動作のそれぞれが、Ｎ個のコンピューティングデバイスを用いて行われることを指定するＮ元処理レイアウトが割り当てられ得る（Ｎは、１以上の整数である）。異なるコンピューティングデバイスグループによって、異なるデータ処理動作が行われ得るが、そのような各グループは、同数のコンピューティングデバイス（すなわち、Ｎ個のデバイス）を有していなければならない。結果として、従来の技術では、データフローグラフの１つのノードが、Ｎ元（Ｎ＞１）処理レイアウトを有し、且つ別のノードが、Ｍ元（Ｎ≠Ｍ＞１）処理レイアウトを有することは可能ではない。
【００１５】
本発明者らは、異なる度合いの並列性を有する処理レイアウトをデータフローグラフの異なるノードに割り当てることができれば、データ処理システムは、データをより速く、且つより効率的に処理し得ることを認識した。データフローグラフによって表される異なるデータ処理動作に対して異なる度合いの並列性を与えることは、データフローグラフを用いたデータ処理システムの速度及びスループットを大幅に向上させ得る。一例として、データフローグラフによってアクセスされた異なるデータセットが、異なる度合いの並列性を用いて保存される状況を考える。例えば、ある入力データセット（「Ａ」）は、１つの場所に保存されたファイルでもよく、別の入力データセット（「Ｂ」）は、分散ファイルシステム（例えば、Ｈａｄｏｏｐ分散ファイルシステム）を用いて、４つの異なる場所に保存されてもよく、及び出力データセット（「Ｃ」）は、分散データベースシステムを用いて、３つの異なる場所に保存されてもよい。順次処理レイアウトを用いて入力データセットＡからデータを読み取り、４元並列処理レイアウトを用いて入力データセットＢからデータを読み取り、及び３元並列処理レイアウトを用いて出力データセットＣにデータを書き込むことは、入力及び出力データセットの並列性の度合いにマッチした並列性の度合いを有する処理レイアウトの使用が、その中に含有されるデータにアクセスし、及び続いて処理する速度を向上させるので、同じ度合いの並列性を有する処理レイアウトを用いて、これらのデータ処理動作の全てを行うよりも、より効率的となり得る。加えて、幾つかのデータセットは、指定された度合いの並列性のみを用いてアクセスされ（例えば、読み取られ、及び／又は書き込まれ）得る。異なるデータセットは、異なる度合いの並列性を必要とし得る。このようなデータセットは、本明細書に記載の技術を用いなければ、同じデータフローグラフを用いてアクセスされ得ない。
【００１６】
例えば、入力ノード１０２ａ、１０２ｂ、１０２ｃと、各フィルタリング動作を表すノード１０４、１１０、及び１１１と、ソート動作を表すノード１０６と、各結合動作を表すノード１０８及び１１２と、出力ノード１１４ａ及び１１４ｂを包含する、図１Ａに示す、説明のためのデータフローグラフ１００を考える。図１Ａに示すように、ノード１０２ａによって表される入力データセットからのデータは、フィルタリングされ、ソートされ、及び出力ノード１１４ａによって表される出力データセットに書き込まれる前に、ノード１０２ｂによって表される入力データセットからのデータのフィルタリングされたバージョンと結合される。ノード１０２ｂによって表される入力データセットからのデータも、フィルタリングされ、及びノード１１４ｂによって表される出力データセットに書き込まれる前に、ノード１０２ｃによって表される入力データセットからのデータと結合される。図１Ａに示すように、処理レイアウトを自動的に決定するための従来の技術の適用は、同じ並列処理レイアウトＰＬ１が、データフローグラフ１００の各ノードに割り当てられることをもたらす。一方、図１Ｂに示すように、入力データセット及び出力データセットが、異なる度合いの並列性を用いて保存される場合には、異なる処理レイアウトをグラフ１００の異なるノードに割り当てることが必要とされ得る。
【００１７】
本明細書に記載の実施形態の幾つかは、データフローグラフを用いてデータ処理動作を行うための従来の技術に関して本発明者らが認識した上記の課題の全てに対処する。しかし、以下に記載の全ての実施形態が、これらの課題の１つ１つに対処するわけではなく、幾つかの実施形態は、これらの何れにも対処しない場合がある。そのため、本明細書に記載の技術の実施形態は、データフローグラフを用いてデータ処理動作を行うための従来の技術の上述の課題の全て又は何れかに対処することに限定されないことが理解されるものとする。
【００１８】
本明細書に記載の技術の幾つかの実施形態は、データフローグラフの１つ又は複数のノードによって表されるデータ処理動作を行うための処理レイアウトを自動的に決定する技術に向けられる。データフローグラフを用いて計算を行う従来の技術とは異なり、異なるノードに対して決定される処理レイアウトは、同じである必要はなく、グラフの異なるノードによって表されるデータ処理動作は、異なる処理レイアウトを用いて、特に、異なる度合いの並列性を有する処理レイアウトを用いて、行われ得る。
【００１９】
本明細書では、データフローグラフのノードの処理レイアウトは、そのノードによって表されるデータ処理動作を行うために使用される処理レイアウトを指す。例えば、データフローグラフの入力ノードの処理レイアウトは、その入力ノードによって表される入力データセットからのデータを読み取るために使用される処理レイアウトを指す。別の例として、データフローグラフの出力ノードの処理レイアウトは、その出力ノードによって表される出力データセットにデータを書き込むために使用される処理レイアウトを指す。さらに別の例として、データ処理動作（例えば、フィルタリング動作、結合動作、ロールアップ動作など）を表すノードの処理レイアウトは、そのデータ処理動作を行うための処理レイアウトを指す。
【００２０】
幾つかの実施形態では、データ処理動作を表すノードの処理レイアウトは、その動作を行うために使用される並列性の度合いを示し、及びその並列性の度合いに従って動作を行うために使用されるコンピューティングデバイスを指定し得る。例えば、ノードの処理レイアウトは、単一の度合いの並列性を持つ順次処理レイアウトでもよく（すなわち、並列ではなく順次処理）、及びそのノードによって表されるデータ処理動作を行うために使用するコンピューティングデバイス（例えば、プロセッサ、サーバ、ラップトップなど）を指定し得る。別の例として、ノードの処理レイアウトは、Ｎ個の並列性の度合いを有するＮ元（Ｎ≧１）１より大きい）並列処理レイアウトでもよく、及びそのノードによって表されるデータ処理動作を行うために使用するＮ個のコンピューティングデバイスを指定し得る。幾つかの実施形態では、ノードの処理レイアウトは、１つ又は複数のコンピューティングデバイス、及び／又はそのノードによって表されるデータ処理動作を行うために使用する１つ又は複数のコンピューティングデバイスに対して実行する１つ又は複数のプロセスを指定し得る。
【００２１】
幾つかの実施形態では、データフローグラフにおけるノードの処理レイアウトの決定は、（Ａ）データフローグラフを指定する情報を取得することと、（Ｂ）データフローグラフにおける入力ノードの処理レイアウトを取得することと、（Ｃ）データフローグラフにおける出力ノードの処理レイアウトを取得することと、（Ｄ）入力ノードの処理レイアウト、出力ノードの処理レイアウト、及び１つ又は複数のレイアウト決定ルールに基づいて、１つ又は複数の他のノード（すなわち、入力ノード又は出力ノードではないノード）の処理レイアウトを決定することとを包含し得る。入力ノード及び出力ノード以外のデータフローグラフノードは、本明細書では、「中間」ノードと呼ばれる場合がある。レイアウト決定ルールの例は、図２などを参照して、本明細書に記載される。
【００２２】
幾つかの実施形態では、データフローグラフの入力ノード及び出力ノードに関して取得された処理レイアウトの少なくとも２つは、異なる度合いの並列性を有し得る。例えば、２つの異なる入力ノードに関して取得された処理レイアウトは、異なる度合いの並列性を有し得る。別の例として、２つの異なる出力ノードに関して取得された処理レイアウトは、異なる度合いの並列性を有し得る。さらに別の例として、入力ノードに関して取得された処理レイアウトは、出力ノードに関して取得された処理レイアウトとは異なる度合いの並列性を有し得る。それでも、入力ノード及び出力ノードに関して取得された処理レイアウトの少なくとも２つが、異なる度合いの並列性を有するグラフのノードの処理レイアウトを自動的に決定するために、本明細書に記載の技術を使用することができる。ある説明のための例として、本明細書に記載の技術は、図１Ｂに示すデータフローグラフ１００の処理レイアウトの決定に適用され得る。データフローグラフ１００の入力ノード及び出力ノードは、３つの異なる処理レイアウト（すなわち、順次レイアウトＳＬ１、並列レイアウトＰＬ１、及び並列レイアウトＰＬ２）に関連付けられ、これらの処理レイアウトは、図１Ｃに示すように、ノード１０４、１０６、１０８、１１０、１１１、及び１１２の処理レイアウトを自動的に決定するために、本明細書に記載のレイアウト決定ルールと共に使用され得る。
【００２３】
幾つかの実施形態では、データフローグラフの１つ又は複数の中間ノードの処理レイアウトは、（１）順方向パス（入力ノードから出力ノードに向けて）を行うことにより、中間ノードの少なくとも幾つか（例えば、全て）の初期処理レイアウトを決定することと、後に、（２）逆方向パス（出力ノードから入力ノードに向けて）を行うことにより、中間ノードの最終処理レイアウトを決定することとによって決定され得る。順方向パス中に、入力ノードに割り当てられた処理レイアウト、及び本明細書に記載の１つ又は複数のレイアウト決定ルールに基づいて、初期処理レイアウトが決定され得る。例えば、ノード１０４、１０６、１０８、１１０、１１１、及び１１２の初期処理レイアウトは、ノード１０２ａ、１０２ｂ、及び１０２ｃに割り当てられた処理レイアウトに基づいて決定され得る。逆方向パス中は、出力ノードに割り当てられた処理レイアウト、中間ノードの少なくとも幾つかに割り当てられた初期処理レイアウト、及び１つ又は複数のレイアウト決定ルールに基づいて、中間ノードの最終処理レイアウトが決定され得る。例えば、ノード１０４、１０６、１０８、１１０、１１１、及び１１２の最終処理レイアウトは、順方向パス中にこれらのノードに関して決定された初期処理レイアウト、出力ノード１１４ａ及び１１４ｂに割り当てられた処理レイアウト、及び１つ又は複数のレイアウト決定ルールに基づいて決定され得る。
【００２４】
幾つかの実施形態では、データフローグラフにおけるノードの処理レイアウトが決定された後に（例えば、順方向パス及び逆方向パスを行った後に）、データフローグラフは、ある特定の度合いの並列性を有する処理レイアウトを使用して処理された後に、異なる度合いの並列性を有する処理レイアウトを使用して処理されるデータに対して再パーティショニング動作を行うように構成され得る。幾つかの実施形態では、データフローグラフは、異なる度合いの並列性を持つ処理レイアウトを有するグラフにおける隣接ノード間を流れるデータに対して再パーティショニング動作を行うように構成され得る。このようにして、１つの処理レイアウトを使用して（Ｎ個のコンピューティングデバイスを使用して、Ｎ≧１で）処理されたデータは、別の処理レイアウトを使用した（Ｍ≠Ｎ個のコンピューティングデバイスを使用して、Ｍ≧１で）後続の処理に適応され得る。
【００２５】
例えば、図１Ｃに図示されるように、隣接するノード１０２ａ及び１０４は、レイアウトの一方が、順次（１つのコンピューティングデバイスを用いて処理が行われる）であり、他方が並列（複数のコンピューティングデバイスを用いて処理が行われる）であるので、異なる度合いの並列性を持つ処理レイアウトを有する。この例では、データフローグラフは、ノード１０２ａからノード１０４へと流れるデータが、ノード１０２ａに関して決定された処理レイアウト（ＳＬ１）に従って、単一のコンピューティングデバイスを使用して処理された後に、ノード１０４に関して決定された処理レイアウト（ＰＬ１）に従って、複数のコンピューティングデバイスを使用して処理され得るように、データをパーティショニングするように構成され得る。このために、データフローグラフは、並列性の度合いを増加させる再パーティショニング動作（例えば、パーティション・バイ・キー（ｐａｒｔｉｔｉｏｎ−ｂｙ−ｋｅｙ）動作）を行うように構成され得る。又、同じ例において、隣接するノード１０２ｂ及び１１１は、異なる処理レイアウトを有し、及び隣接するノード１１２及び１１４は、異なる処理レイアウトを有し、及びデータフローグラフ１００は、ノード１０２からノード１１１へと流れるデータに対する再パーティショニング動作、及びノード１１２からノード１１４へと流れるデータに対する再パーティショニング動作（例えば、集約動作）を行うように構成され得る。
【００２６】
幾つかの実施形態では、データフローグラフは、再パーティショニング動作を表すノードでグラフを拡張することによって、再パーティショニング動作を行う（グラフの実行時に）ように構成され得る。グラフが実行されると、再パーティショニング動作を行うように構成されたソフトウェアが、実行され得る。例えば、図１Ｃに示すように、データフローグラフは、ノード１３０、１３２、及び１３４で拡張することができ、各ノードは、それぞれの再パーティショニング動作と関連付けられる。他の実施形態では、データフローグラフの１つ又は複数の既存のノードが、再パーティショニング動作を行うように構成されてもよく、及び新しいノードは、追加されない。
【００２７】
幾つかの実施形態では、データフローグラフのノード（ノード「Ａ」）が、グラフにおける後続の隣接ノード（ノード「Ｂ」）の並列性の度合いよりも高い並列性の度合いを有する処理レイアウトと関連付けられる場合、データフローグラフは、データが、ノード「Ａ」によって表されるデータ処理動作に従って処理された後であって、且つデータが、ノード「Ｂ」によって表されるデータ処理動作に従って処理される前に、データに対して再パーティショニング動作を行うように構成され得る。この場合、再パーティショニング動作は、並列性の度合いを低下させることができ、及び例えば、集約動作１（１データレコードの複数のセットに対して行われる集約動作は、データレコードの複数のセットをデータレコードの単一のセットに統合し得るが、必ずしも、単一のセットにおけるデータレコードのソート性を維持しない）又はマージ動作２（２データレコードの複数のセットに対して行われるマージ動作は、単一のセットにおけるデータレコードのソート性を維持しながら、データレコードの複数のセットをデータレコードの単一のセットに統合し得る）でもよい。例えば、図１Ｃに示すように、ノード１１２の並列処理レイアウト（ＰＬ２）は、後続の隣接ノード１１４ｂの順次処理レイアウト（ＳＬ１）よりも高い並列性の度合いを有する。この例では、集約動作に関連付けられたノード１３４は、ノード１１２と１１４ｂとの間に追加されている。
【００２８】
幾つかの実施形態では、データフローグラフのノード（ノード「Ａ」）が、グラフにおける後続の隣接ノード（ノード「Ｂ」）の並列性の度合いよりも低い並列性の度合いを有する処理レイアウトと関連付けられる場合、データフローグラフは、データが、ノード「Ａ」によって表されるデータ処理動作に従って処理された後であって、且つデータが、ノード「Ｂ」によって表されるデータ処理動作に従って処理される前に、データに対して再パーティショニング動作を行うように構成され得る。この場合、再パーティショニング動作は、並列性の度合いを増加させることができ、及び例えば、パーティション・バイ・キー動作３（３パーティション・バイ・キー動作では、１つ又は複数の同じフィールド（例えば、１つ又は複数の同じコラムにおける）に対して１つ又は複数の同じ値を有するデータレコードが、同じパーティションに割り当てられる）、ラウンドロビンパーティション動作、パーティション・バイ・レンジ（ｐａｒｔｉｔｉｏｎ−ｂｙ−ｒａｎｇｅ）動作４（４パーティション・バイ・レンジ動作では、異なるパーティションが、値の異なる非重複範囲と関連付けられ、及びある範囲内にフィールド値を有するデータレコードが、その範囲と関連付けられたパーティションに割り当てられる）、又はその他の適宜のタイプのパーティショニング動作でもよい。例えば、図１Ｃに示すように、ノード１０２ａの順次処理レイアウト（ＳＬ１）は、後続の隣接ノード１１４ｂの並列処理レイアウト（ＰＬ１）よりも低い並列性の度合いを有する。同様に、この例では、ノード１０２ｂの並列処理レイアウト（ＰＬ１）は、ノード１１１の並列処理レイアウト（ＰＬ２）よりも低い並列性の度合いを有する。この例では、パーティション・バイ・キー動作を表すノード１３０が、ノード１０２ａとノード１０４との間に追加されており、及びラウンドロビンパーティション動作を表すノード１３２は、並列性の度合いの所望の低下を達成する集約動作が、その後に続く。
【００２９】
幾つかの実施形態では、データフローグラフのノード（ノード「Ａ」）が、グラフにおける後続の隣接ノード（ノード「Ｂ」）の並列性の度合いと同じ並列性の度合いを有する処理レイアウトと関連付けられる場合、再パーティショニング動作は、必要とされない。
【００３０】
幾つかの実施形態では、データフローグラフの中間ノードの処理レイアウトは、グラフの入力ノード及び出力ノードに割り当てられた処理レイアウトに基づいて決定され得るが、本明細書に記載の技術は、入力ノード及び出力ノードのレイアウトから中間ノードのレイアウトを決定することに限定されない。幾つかの実施形態では、例えば、処理レイアウトは、データフローグラフの１つ又は複数のノードの任意のサブセットに対して取得されてもよく、及びデータフローグラフの任意のその他のノードの処理レイアウトは、これらの取得された処理レイアウト、データフローグラフの構造、及び１つ又は複数のレイアウト決定ルールに基づいて決定され得る。
【００３１】
本明細書に記載の技術の幾つかの実施形態は、データ処理システムによる、構造化照会言語（ＳＱＬ）クエリーなどのデータベースクエリーの管理に適用され得る。幾つかの実施形態では、データ処理システムは、（１）データベースクエリー（例えば、ＳＱＬクエリー）を受信し、（２）ＳＱＬクエリーを実行するためのクエリープラン（例えば、データベースクエリーが実行されると行われ得るデータベース動作を示すプラン）を生成し、（３）クエリープランからデータフローグラフを生成し、及び（４）少なくとも部分的にデータフローグラフを実行することによって、受信したデータベースクエリーを実行し得る。このような実施形態は、本明細書に全体として援用される、２０１５年８月２５日に発行された、「データクエリー管理（ＭＡＮＡＧＩＮＧ  ＤＡＴＡ  ＱＵＥＲＩＥＳ）」というタイトルの米国特許第９，１１６，９５５号明細書にさらに詳細に記載されている。米国特許第９，１１６，９５５号明細書は、「データクエリー管理（ＭＡＮＡＧＩＮＧ  ＤＡＴＡ  ＱＵＥＲＩＥＳ）」というタイトルの、２０１１年５月２日に出願された、出願内容が本明細書に全体として援用される、米国特許出願第１３／０９８，８２３号明細書から完成したものである。
【００３２】
幾つかの実施形態では、本明細書に記載の技術は、データベースクエリー（例えば、ＳＱＬクエリー）から自動的に生成されたデータフローグラフの１つ又は複数のノードの処理レイアウトを自動的に決定するために使用され得る。
【００３３】
幾つかの実施形態では、データ処理システムは、（１）データベースクエリー（例えば、ＳＱＬ）クエリーを受信し、（２）受信したデータベースクエリーを、実行されるとデータベースクエリーを実行するコンピュータコード部分を含むコンピュータコードに変換し、及び（３）各コンピュータコード部分を実行するための処理レイアウトを自動的に決定し得る。幾つかの実施形態では、コンピュータコード部分を実行するための処理レイアウトは、コンピュータコード部分の実行順序を示す情報を用いて決定され得る。例えば、幾つかの実施形態では、各コンピュータコード部分は、データフローグラフにおけるそれぞれのノードと関連付けられてもよく、及びグラフの構造（例えば、ノード間の接続で具現化されるような）を用いて、処理レイアウトをノードに、及び関連して、ノードに関連付けられたコンピュータコード部分に割り当て得る。ただし、幾つかの実施形態では、コンピュータコード部分の実行順序を示す情報が、データフローグラフでエンコードされることに限定されないので、コンピュータコード部分を実行するための処理レイアウトは、データフローグラフを用いることなく決定され得ることを認識されたい。
【００３４】
本明細書に記載の実施形態は、多数のやり方の何れで実施されてもよいことが理解されるものとする。単なる説明目的で、具体的な実施の例を以下に提供する。これらの実施形態及び提供される特徴／機能は、個々に、全て一緒に、又は２つ以上の任意の組み合わせで使用されてもよいことが理解されるものとする（本明細書に記載される技術の態様は、この点において限定されない）。
【００３５】
図２は、少なくとも部分的に、本明細書に記載の技術の幾つかの実施形態に従ってデータフローグラフのノードに処理レイアウトを割り当てることによって、データフローグラフの処理構成を決定するための、説明のためのプロセス２００のフローチャートである。プロセス２００は、任意の適宜のシステム及び／又はコンピューティングデバイスによって行われてもよく、及び例えば、図６などを参照して本明細書に記載するデータ処理システム６０２によって行われ得る。プロセス２００を説明した後に、プロセス２００の幾つかの局面を、図３Ａ〜３Ｄ、４Ａ〜４Ｃ、及び５Ａ〜５Ｄに示す例を参照して例示する。図３Ａ〜３Ｄの例は、プロセス２００の説明後に、詳細に記載するが、この例は、説明を明確にするために、プロセス２００の説明全体を通しても言及される。
【００３６】
プロセス２００は、データフローグラフを指定する情報がアクセスされ得るアクト２０２から始まる。本明細書に記載する通り、データフローグラフは、（ａ）１つ又は複数のそれぞれの入力データセットを表す１つ又は複数の入力ノード、（ｂ）１つ又は複数のそれぞれの出力データセットを表す１つ又は複数の出力ノード、及び／又は（ｃ）データに対して行われ得るデータ処理動作を表す１つ又は複数のノードを包含する複数のノードを包含し得る。データフローグラフのノード間の有向リンク又はエッジは、ノード間のデータフローを表す。従って、アクト２０２では、データフローグラフのノード（上記のタイプのノードの何れも包含する）及びリンクを指定する情報が、アクセスされ得る。この情報は、任意の適宜のソース、任意の適宜のデータ構造からアクセスされてもよく、及び任意の適宜のフォーマットのものでもよい（本明細書に記載の技術の局面は、この点において限定されない）。例えば、図３Ａ〜Ｄに示される例を参照して、アクト２０２では、データフローグラフ３００を指定する情報が、アクセスされ得る。以下にさらに詳細に記載する幾つかの実施形態では、アクト２０２で情報がアクセスされるデータフローグラフは、自動的に生成されたものである場合があり、及び例えば、構造化照会言語（ＳＱＬ）クエリーから自動的に生成されたものである場合がある。
【００３７】
次いで、アクト２０４では、アクト２０２でアクセスされたデータフローグラフの各入力ノード（すなわち、入力データセットを表す各ノード）に関して、処理レイアウトが取得され得る。例えば、図３Ａ〜３Ｄの例を参照して、アクト２０４では、入力ノード３０２及び３０４の処理レイアウトが取得され得る。幾つかの実施形態では、入力ノードの処理レイアウトは、入力ノードによって表される入力データセットからデータを読み取るための並列性の度合い（例えば、順次、２元並列、３元並列、…、任意の適宜の整数ＮのＮ元並列）を指定する。幾つかの実施形態では、入力ノードの処理レイアウトは、入力データセットからデータを読み取るために使用する１つ又は複数のコンピューティングデバイスのセット（例えば、１つ又は複数のプロセッサ、サーバ、及び／又はその他の適宜のデバイスのセット）を識別する。
【００３８】
入力ノードの処理レイアウトは、任意の適宜のやり方で取得され得る。幾つかの実施形態では、入力ノードの処理レイアウトは、プロセス２００の実行の開始前に決定することができ、及びアクト２０４中に、以前に決定された処理レイアウトが、アクセスされ得る。他の実施形態では、入力ノードの処理レイアウトは、プロセス２００の実行中に動的に決定され得る。幾つかの実施形態では、入力の処理レイアウトは、プロセス２００の実行の開始前に部分的に決定されてもよく、未知の情報は、プロセス２００の実行中に動的に決定される。例えば、プロセス２００の実行の前に、入力ノードの処理レイアウトが、順次又は並列であることが分かっているかもしれないが、入力動作（例えば、１つ又は複数のソースからデータを読み取ること）を行うために使用される特定のコンピューティングデバイスは、プロセス２００の実行中に決定され得る。別の例として、プロセス２００の実行に先立って、並列処理レイアウトが、ある入力ノードに割り当てられることが分かっているかもしれないが、並列性の度合いは、ランタイム中に決定され得る。
【００３９】
入力ノードの処理レイアウトが、プロセス２００の実行前に、あるいは実行中に決定されるかにかかわらず、その決定は、任意の適宜のやり方で行われ得る。例えば、幾つかの実施形態では、入力ノードの処理レイアウトは、ユーザインタフェース（例えば、グラフィカルユーザインタフェース、構成ファイルなど）を用いて、ユーザによって手作業で指定され得る。別の例として、幾つかの実施形態では、入力ノードの処理レイアウトは、データ処理システムによって自動的に決定され得る。例えば、データ処理システムは、入力ノードによって表される入力データセットがどのように保存されるかに基づいて、入力ノードの処理レイアウトを自動的に決定し得る。例えば、入力データセットが複数のデバイス（例えば、４つのサーバ、Ｈａｄｏｏｐクラスタを使用してなど）に保存される場合、プロセス２００を実行するデータ処理システムは、並列処理レイアウト（例えば、４元並列処理レイアウト、Ｈａｄｏｏｐクラスタにおけるノードの数）が、入力データセットからデータレコードを読み取るために使用されることを決定し得る。
【００４０】
次いで、アクト２０６において、アクト２０２でアクセスされたデータフローグラフの各出力ノード（すなわち、出力データセットを表す各ノード）に関して、処理レイアウトが取得され得る。例えば、図３Ａ〜３Ｄの例を参照して、アクト２０６では、出力ノード３１４の処理レイアウトが取得され得る。幾つかの実施形態では、出力ノードの処理レイアウトは、出力ノードによって表される出力データセットにデータを書き込むための並列性の度合い（例えば、順次、２元並列、３元並列、…、任意の適宜の整数ＮのＮ元並列）を指定する。幾つかの実施形態では、出力ノードの処理レイアウトは、データを出力データセットに書き込むために使用する１つ又は複数のコンピューティングデバイスのセット（例えば、１つ又は複数のプロセッサ、サーバ、及び／又はその他の適宜のデバイスのセット）を識別する。
【００４１】
出力ノードの処理レイアウトは、任意の適宜のやり方で取得され得る。幾つかの実施形態では、出力ノードの処理レイアウトは、プロセス２００の実行の開始前に決定することができ、及びアクト２０６中に、以前に決定された処理レイアウトが、アクセスされ得る。他の実施形態では、出力ノードの処理レイアウトは、プロセス２００の実行中に動的に決定され得る。幾つかの実施形態では、出力ノードの処理レイアウトは、プロセス２００の実行の開始前に部分的に決定されてもよく、未知の情報は、プロセス２００の実行中に動的に決定される。例えば、プロセス２００の実行の前に、出力ノードの処理レイアウトが、順次又は並列であることが分かっているかもしれないが、出力動作（例えば、データを１つ又は複数の出力データセットに書き込むこと）を行うために使用される特定のコンピューティングデバイスは、プロセス２００の実行中に決定され得る。別の例として、プロセス２００の実行に先立って、並列処理レイアウトが、ある出力ノードに割り当てられることが分かっているかもしれないが、並列性の度合いは、ランタイム中に決定され得る。
【００４２】
出力ノードの処理レイアウトが、プロセス２００の実行前に、あるいは実行中に決定されるかにかかわらず、その決定は、入力ノードの処理レイアウトを決定するための上記のやり方の何れをも含む任意の適宜のやり方で行われ得る。例えば、出力ノードの処理レイアウトは、ユーザインタフェースを用いて、ユーザによって手作業で指定されてもよく、又はデータ処理システムによって（例えば、出力ノードによって表される出力データセットがどのように保存されるかに基づいて）自動的に決定されてもよい。
【００４３】
次いで、プロセス２００は、アクト２０４及び２０６で処理レイアウトが取得された入力及び出力ノード以外のデータフローグラフにおけるノードに関して、処理レイアウトが決定されるアクト２０８に進む。幾つかの実施形態では、中間ノードの処理レイアウトは、中間ノードによって表されるデータ処理動作を行うための並列性の度合い（例えば、順次、２元並列、３元並列、…、任意の適宜の整数ＮのＮ元並列）を指定する。幾つかの実施形態では、中間ノードの処理レイアウトは、データ処理動作を行うために使用する１つ又は複数のコンピューティングデバイスのセット（例えば、１つ又は複数のプロセッサ、サーバ、及び／又はその他の適宜のデバイスのセット）を識別する。
【００４４】
幾つかの実施形態では、中間ノードの処理レイアウトは、少なくとも部分的に、入力ノード及び出力ノードの処理レイアウト（アクト２０４及び２０６で取得された）を使用することによって決定され得る。例えば、図３Ａ〜３Ｄの例を参照して、アクト２０８において、中間ノード３０６、３０８、３１０、及び３１２の処理レイアウトは、入力ノード３０２及び３０４、及び出力ノード３１４の処理レイアウトを使用して決定され得る。幾つかの実施形態では、中間ノードの処理レイアウトは、データフローグラフの構造、及び１つ又は複数のレイアウト決定ルールにさらに基づいて、決定され得る。
【００４５】
幾つかの実施形態では、レイアウト決定ルールは、データフローグラフのあるノードの処理レイアウトが、データフローグラフの１つ又は複数の他のノードの処理レイアウトに基づいて、どのように決定され得るかを指定し得る。例えば、幾つかの実施形態では、レイアウト決定ルールは、何れの処理レイアウトにも関連付けられていない、ある特定のノードの処理レイアウトが、グラフにおける、その特定のノードに隣接する他のノードの１つ又は複数の処理レイアウトに基づいて、どのように決定され得るかを指定し得る。ある説明のための例として、図３Ａの例を参照して、レイアウト処理ルールは、入力ノード３０２の処理レイアウトに基づいた、中間ノード３０６の処理レイアウトの決定方法を指定し得る。別の説明のための例として、ノード３０８及び３１０の処理レイアウトが決定されると、レイアウト処理ルールは、ノード３０８及び３１０に関して決定された処理レイアウトに基づいて、ノード３１２の処理レイアウトを決定する方法を指定し得る。
【００４６】
別の例として、幾つかの実施形態では、レイアウト決定ルールは、ある特定の処理レイアウトと既に関連付けられた特定のノードの処理レイアウトを、上記特定の処理レイアウト、及びグラフにおいて、上記特定のノードに隣接する１つ又は複数の他のノードの処理レイアウトに基づいて決定する方法を指定し得る。ある説明のための例として、図３Ｃの例を参照して、ノード３１２の処理レイアウトは、ノード３１２に関して決定された初期処理レイアウト（レイアウトＰＬ１）及び出力ノード３１４に関して決定された処理レイアウト（レイアウトＳＬ２）に基づいて決定され得る。
【００４７】
具体的なレイアウト決定ルールの非限定的な、説明のための例を以下に記載する。幾つかの実施形態では、本明細書に記載のレイアウト決定ルール例に加えて、又はそれらの代わりに、１つ又は複数の他のレイアウト決定ルールが使用され得ることを認識されたい。本明細書に記載のレイアウトルール例の１つ又は複数の任意の適宜の組み合わせが、幾つかの実施形態において使用され得ることも認識されたい。本明細書に記載のレイアウト決定ルールは、任意の適宜のやり方で（例えば、ソフトウェアコード、１つ又は複数の構成パラメータなどを使用して）実施され得る（本明細書に記載の技術の局面は、この点において限定されない）。
【００４８】
幾つかの実施形態では、あるレイアウト決定ルール例によれば、処理レイアウトとまだ関連付けられていない、ある特定のノードの処理レイアウトを決定する際に、この特定のノードが、関連付けられた処理レイアウトを有する近隣ノード（例えば、データフローグラフにおける、上記特定のノードの直前のノード、又はデータフローグラフにおける、上記特定のノードの直後のノード）を有する場合には、近隣ノードのレイアウトは、上記特定のノードの処理レイアウトとして決定され得る。このようにして、近隣ノードの処理レイアウトが、上記特定のノードに「コピー」され得る。ある説明のための例として、図３Ａの例では、ノード３０６の処理レイアウトは、それに先行する近隣ノード３０２の処理レイアウトであると決定され得る。次に、ノード３０８の処理レイアウトは、それに先行するノード３０６の処理レイアウトであると決定され得る。この例から認識され得るように、このレイアウト決定ルールは、ある入力ノード（例えば、ノード３０２）のレイアウトを１つ又は複数の他のノード（例えば、ノード３０６、３０８、及び３１２）へと伝播するように繰り返し適用され得る。
【００４９】
幾つかの実施形態では、別のレイアウト決定ルール例によれば、ある特定の処理レイアウトとまだ関連付けられていない、ある特定のノードの処理レイアウトを決定する際に、この特定のノードが、関連付けられた処理レイアウトを有する複数の近隣ノード（例えば、複数の先行する近隣ノード、又は複数の後続の近隣ノード）を有する場合には、上記特定のノードの処理レイアウトは、それの近隣ノードのレイアウトの中から選択され得る。例えば、図３Ａのデータフローグラフの場合、ノード３０８及び３１０のレイアウトは決定済みであるが、ノード３１２のレイアウトがまだ決定されていないと仮定すると、ノード３１２のレイアウトは、ノード３０８及び３１０に関して決定されたレイアウトの一方であると選択され得る。
【００５０】
幾つかの実施形態では、別のレイアウト決定ルール例によれば、ある特定の処理レイアウトと既に関連付けられた、ある特定のノードの処理レイアウトを決定する際に、この特定のノードが、それぞれの処理レイアウトと関連付けられた１つ又は複数の近隣ノードを有する場合には、上記特定のノードのレイアウトは、このノードと既に関連付けられた上記特定の処理レイアウト、及びそれの近隣ノードの処理レイアウトの中から選択することによって決定され得る。例えば、図３Ｃに示されるように、ノード３１２は、初期処理レイアウト（ＰＬ１）と関連付けられ、及び別の処理レイアウト（ＳＬ２）と関連付けられた近隣ノード３１４を有する。この例では、これら２つのレイアウト（すなわち、ＰＬ１及びＳＬ２）の一方が、ノード３１２の更新（例えば、最終）処理レイアウトとして選択され得る。
【００５１】
上記から認識され得るように、幾つかの実施形態では、あるレイアウト決定ルールを適用することは、２つ以上の処理レイアウトの中から処理レイアウトを選択することを伴う。これは、多数のやり方の何れで行われてもよい。例えば、幾つかの実施形態では、２つ以上の処理レイアウトから成るグループから、ノードの処理レイアウトを選択する場合、最大の並列性の度合いを有する処理レイアウトが選択され得る。例えば、ノードの処理レイアウトが、Ｎ元並列処理レイアウト（例えば、１０元並列レイアウト）、あるいはＭ元（Ｍ＜Ｎ）並列処理レイアウト（例えば、５元並列レイアウト）であるかを選択する場合、Ｎ元並列処理レイアウトが選択され得る。別の例として、ノードの処理レイアウトを並列処理レイアウト及び順次処理レイアウトから選択する場合、並列処理レイアウトが選択され得る。ある説明のための例として、図３Ｂを参照して、ノード３１２は、初期順次処理レイアウト（ＳＬ１）を割り当てられ（例えば、入力ノード３０２からそのレイアウトを伝播した結果として）、及びノード３１０は、並列レイアウトＰＬ１を割り当てられ得る（例えば、入力ノード３０４からそのレイアウトを伝播した結果として）。次いで、ＰＬ１とＳＬ１との間で、レイアウトＰＬ１が明らかにより大きな並列性の度合いを有するため、ノード３１２の処理レイアウトは、並列レイアウトＰＬ１であると更新され得る。
【００５２】
別の例として、幾つかの実施形態では、同じ並列性の度合いを有する処理レイアウトの中から、ノードの処理レイアウトを選択する際には、より多数のレコードを処理するために使用される処理レイアウトが選択され得る。例えば、データフローグラフにおけるノードの処理レイアウトを、上記ノードの第１の先行する近隣ノードに割り当てられ、且つ１０００万のデータレコードを処理するために使用される４元レイアウトＰＬ１、及び上記ノードの第２の先行する近隣ノードに割り当てられ、且つ１万のデータレコードを処理するために使用される４元レイアウトＰＬ２から選択する場合、上記ノードに関して、レイアウトＰＬ１が選択され得る。このようにして、上記ノードに関連付けられたデータ処理動作（例えば、結合動作）が、１０００万のデータレコードを処理するために使用される処理レイアウトと同じもの（例えば、同じコンピューティングデバイス）を使用して行われ得る。結果として、レイアウトＰＬ１及びＰＬ２が、コンピューティングデバイスの非重複セットを使用して実施される場合、最大で１万のデータレコードが、１０００万のデータレコードを処理するために使用されるコンピューティングデバイスへと移動される必要がある。一方、レイアウトＰＬ２が選択された場合、場合によっては１０００万のデータレコード全てが、たった１万のデータレコードを処理するために使用されるコンピューティングデバイスへと移動される必要があり、これは明らかに非効率的である。従って、より多数のレコードを処理するために使用されるレイアウトを選択することが、データ処理システムの性能を向上させることに役立ち得る。図４Ａ〜４Ｃを参照して、これの一例を以下でさらに説明する。
【００５３】
幾つかの実施形態では、別のレイアウト決定ルール例によれば、データフローグラフの入力ノード及び出力ノードに関して、処理レイアウトが決定された後に、これらの処理レイアウトは、後で変更されない。このルールが利用される実施形態においては、入力ノード及び出力ノードの処理レイアウトが、アクト２０４及び２０６で取得された後に、これらの処理レイアウトは、後で変更されない。
【００５４】
幾つかの実施形態では、別のレイアウト決定ルール例によれば、順次処理レイアウトが、データレコードのグループに適用されると、一定の数のデータレコードを出力する（例えば、データレコードが、それぞれのスコアに基づいてソートされた後に、トップテンのスコアを有するデータレコードを出力する）動作である制限動作を表すノードに割り当てられ得る。
【００５５】
幾つかの実施形態では、データフローグラフの１つ又は複数の内部ノードが、所定の処理レイアウトと関連付けられ得る。幾つかの実施形態では、ある特定のタイプのノードが、所定の処理レイアウトと関連付けられ得る。
【００５６】
幾つかの実施形態では、別のレイアウト決定ルール例によれば、処理レイアウトが、データフローグラフにおける、ある特定のノードに割り当てられると、その特定のノードに割り当てられた処理レイアウトをその他のノードに伝播させないための指示が、提供され得る（例えば、グラフィカルユーザインタフェース又は構成ファイルなどのユーザインタフェースを用いて、ユーザによって）。例えば、幾つかの実施形態では、１つ又は複数の入力ノード、及び／又は１つ又は複数の出力ノードに割り当てられた処理レイアウトを伝播させないための指示は、アクト２０４及び／又は２０６における入力及び／又は出力処理レイアウトの取得の一部として提供され得る。
【００５７】
図５Ａ〜５Ｄを参照して、これの一例を以下でさらに説明する。
【００５８】
プロセス２００のアクト２０８における中間ノードの処理レイアウトを決定するために、上記のレイアウト決定ルールの何れも使用することができる。上記のレイアウト決定ルールの幾つかは、ある特定のノードの処理レイアウトを、それの近隣ノードに既に割り当てられたレイアウトに基づいて決定する方法を指定するので、「ローカル」であるが、幾つかの実施形態では、これらのレイアウト決定ルールの１つ又は複数は、入力及び出力処理ノードに関して取得された処理レイアウトを中間ノードに伝播させるように繰り返し適用され得る。この伝播は、任意の適宜のやり方で行われ得る。
【００５９】
幾つかの実施形態では、中間ノードの処理レイアウトは、アクト２０８において、（１）アクト２０８ａにおいて、順方向パスを行うことにより、中間ノードの少なくとも幾つか（例えば、全て）の初期処理レイアウトを決定することと、（２）アクト２０８ｂにおいて、逆方向パスを行うことにより、中間ノードの少なくとも幾つか（例えば、全て）の最終処理レイアウトを決定することとによって決定され得る。
【００６０】
順方向パス中に、１つ又は複数の入力ノードに関して取得された処理レイアウトが、本明細書に記載のレイアウト決定ルールの１つ又は複数を用いて、データフローグラフにおける中間ノードへと伝播され得る。データフローグラフの構造は、順方向パス中にノードに関して処理レイアウトが決定される順序をガイドし得る。例えば、最初に、入力ノードの近隣ノードに関する処理レイアウトが決定され、次に、入力ノードの近隣ノードの近隣ノードに関する処理レイアウトが決定され、入力ノードからの全てのフローが、出力ノードにおけるそれらの終端にたどり着くまで続き得る。ある説明のための例として、図３Ｂを参照して、入力ノード３０２及び３０４の処理レイアウトが、ノード３０６、３０８、３１０、及び３１２の初期処理レイアウトを取得するために、１つ又は複数のレイアウト決定ルールを用いて、順方向パス中に伝播され得る。
【００６１】
逆方向パス中は、１つ又は複数の出力ノードに関して取得された処理レイアウトが、本明細書に記載のレイアウト決定ルールの１つ又は複数を用いて、データフローグラフにおける中間ノードへと伝播され得る。順方向パスの場合と同様に、データフローグラフの構造は、逆方向パス中にノードに関して処理レイアウトが決定される順序をガイドし得る。例えば、最初に、出力ノードの近隣ノードに関する処理レイアウトが決定され、次に、出力ノードの近隣ノードの近隣ノードに関する処理レイアウトが決定され、出力ノードからの全てのエッジが、出力ノードにおけるそれらの終端にたどり着くまで続き得る。たどられる経路は、逆方向パス中は逆であり、順方向パスでたどられる経路の逆となり得る。ある説明のための例として、図３Ｃを参照して、出力ノード３１４の処理レイアウト、及びノード３０６、３０８、３１０、及び３１２の初期処理レイアウトが、ノード３０６、３０８、３１０、及び３１２の最終処理レイアウトを取得するために、逆方向パス中に、１つ又は複数のレイアウト決定ルールと共に使用され得る。図３Ａ〜３Ｄを参照して、これを以下により詳細に述べる。
【００６２】
アクト２０８において、中間ノードに関する処理レイアウトが決定された後に、プロセス２００は、データフローグラフの隣接ノードがミスマッチレイアウトを有するか否かが決定される決定ブロック２１０に進む。隣接するノード「Ａ」及び「Ｂ」は、ノードＡに関して決定された処理レイアウトが、ノードＢに関して決定された処理レイアウトとは異なる度合いの並列性を有する場合に、ミスマッチレイアウトを有する。例えば、ノードＡに関して、Ｎ元（Ｎ＞１）並列処理レイアウトが決定され、且つ後続のノードＢに関して、順次処理レイアウトが決定される場合、これらのノードは、ミスマッチレイアウトを有する（Ｎから１への遷移が存在する）。別の例として、ノードＡに関して、順次処理レイアウトが決定され、且つ後続のノードＢに関して、Ｍ元（Ｍ＞１）並列処理レイアウトが決定される場合、これらのノードは、ミスマッチレイアウトを有する（１からＭへの遷移が存在する）。別の例として、ノードＡに関して、Ｎ元並列処理レイアウトが決定され、且つ隣接するノードＢに関して、Ｍ元並列処理レイアウトが決定される場合（Ｍ≠Ｎ）、これらのノードは、ミスマッチレイアウトを有する（ＮからＭへの遷移が存在する）。
【００６３】
決定ブロック２１０において、異なる度合いの並列性を備えた処理レイアウトを有する隣接ノードペアが存在すると決定されると、プロセス２００は、データフローグラフが、１つ又は複数の再パーティショニング動作を行うように構成され得るアクト２１２に進む。再パーティショニング動作は、ある処理レイアウトを用いて、ある数のプロセッサを使用して処理されるデータレコードが、別の処理レイアウトを用いた、異なる数のプロセッサを使用した処理のために遷移されることを可能にする。再パーティショニング動作の例は、本明細書に記載され、及び例えば、データの処理において並列性の度合いを増加させるための再パーティショニング動作（例えば、パーティション・バイ・キー動作、ラウンドロビンパーティション動作、パーティション・バイ・レンジ動作、及び／又はその他の適宜のタイプのパーティション動作）、及びデータの処理において並列性の度合いを低下させるための再パーティショニング動作（例えば、マージ動作及び集約動作）を包含する。例えば、隣接するノードＡとノードＢとの間に、Ｎから１への遷移が存在する場合、データフローグラフは、ノードＡによって表される動作に従って処理されるデータの並列性の度合いを低下させる（Ｎから１へ）ための再パーティショニング動作を、そのデータがノードＢによって表される動作に従って処理される前に行うように構成され得る。別の例として、隣接するノードＡとノードＢとの間に、１からＭへの遷移が存在する場合、データフローグラフは、ノードＡによって表される動作に従って処理されるデータの並列性の度合いを増加させる（１からＭへ）ための再パーティショニング動作を、そのデータがノードＢによって表される動作に従って処理される前に行うように構成され得る。さらに別の例として、隣接するノードＡとノードＢとの間に、ＮからＭへの遷移が存在する場合、データフローグラフは、ノードＡによって表される動作に従って処理されるデータに対して並列性の度合いを変化させる（ＮからＭへ）ために、複数の再パーティショニング動作を、そのデータがノードＢによって表される動作によって処理される前に行うように構成され得る。複数の再パーティショニング動作は、並列性の度合いを低下させる（例えば、ＮからＫへ）第１の再パーティショニング動作、及び並列性の度合いを増加させる（例えば、ＫからＭへ、Ｋは、Ｎ及びＭの公約数である）第２の再パーティショニング動作を包含し得る。
【００６４】
幾つかの実施形態では、データフローグラフは、再パーティショニング動作を表す新しいノードを追加することによって、再パーティショニング動作を行うように構成され得る。以下に説明する図３Ｄ、４Ｃ、及び５Ｄにおいて、これの例を示す。このような実施形態では、再パーティショニング動作を表すノードに関して、処理レイアウトが決定され得る。再パーティショニング動作が、並列性の度合いを増加させる（例えば、パーティション・バイ・キー動作）場合には、再パーティショニング動作を表すノードに割り当てられた処理レイアウトは、先行するノードに割り当てられた処理レイアウトでもよい。再パーティショニング動作が、並列性の度合いを低下させる（例えば、マージ動作又は集約動作）場合には、再パーティショニング動作を表すノードに割り当てられた処理レイアウトは、グラフにおける後続のノードに割り当てられた処理レイアウトでもよい。他の実施形態では、データフローグラフの既存のノードが、再パーティショニング動作を行うように構成され得る。
【００６５】
幾つかの実施形態では、プロセス２００を行うデータ処理システムは、特定の状況において、特定のタイプの再パーティショニング動作を行うようにデータフローグラフを構成するようにプログラミングされ得る。例えば、幾つかの実施形態では、データフローグラフが、並列性の度合いを低下させるための再パーティショニング動作を行うように構成され、且つデータがソートされるとき、データのソート性が、再パーティショニングを通して維持される場合には、データフローグラフは、並列性の度合いを低下させるためにマージ動作を行うように構成され得る。そうでなければ、集約動作を使用して、並列性の度合いを低下させ得る。別の例として、幾つかの実施形態では、データフローグラフが、並列性の度合いを増加させるための再パーティショニング動作を行うように構成されるとき、データの特定のパーティショニングが望まれる場合には、データフローグラフは、ある特定の１つ又は複数のキーに関して、パーティション・バイ・キー動作を行うように構成され得る。そうでなければ、ラウンドロビンパーティション動作、又は別のタイプのパーティション動作が、使用され得る。別の例として、幾つかの実施形態では、ロールアップ動作を並列データに適用することは、ロールアップキーのサブセットに関して、このデータがまだパーティショニングされていない場合には、再パーティショニングを必要とし得る。この場合、ロールアップが、データ量を大幅に（例えば、少なくとも１０分の１）減少させると推定される場合には、ダブルバブルロールアップが行われ得る（すなわち、まず、ソースレイアウト及びパーティショニングスキームにおけるロールアップ、次いで、デスティネーションレイアウト及びパーティショニングスキームにおいて第２のロールアップ）。
【００６６】
一方、決定ブロック２１０において、異なる度合いの並列性を備えた処理レイアウトを有する隣接ノードが存在しない、又は異なる度合いの並列性を備えたレイアウトを有する隣接ノードに関して、適切な再パーティショニング論理が、データフローグラフに追加されていると決定されると、プロセス２００は、完了する。
【００６７】
幾つかの実施形態では、プロセス２００を用いて処理レイアウトが割り当てられた後に、データフローグラフは、割り当てられたレイアウトに従って実行され得る。このようにして、データフローグラフにおける１つ又は複数のデータ処理動作のそれぞれが、そのデータ処理動作に割り当てられた処理レイアウトに従って実行される。
【００６８】
幾つかの実施形態では、プロセス２００は、自動生成されたデータフローグラフに適用され得る。例えば、幾つかの実施形態では、プロセス２００は、ＳＱＬクエリーから、別のデータベースシステムによって提供されたクエリーを指定する情報から、及び／又は別のデータフローグラフから自動生成されたデータフローグラフに適用され得る。
【００６９】
幾つかの実施形態では、データフローグラフは、（１）ＳＱＬクエリーを受信し、（２）受信したＳＱＬクエリーからクエリープランを生成し、及び（３）クエリープランからデータフローグラフを生成することによって、ＳＱＬクエリーから生成され得る。次に、プロセス２００は、そのように生成されたデータフローグラフに適用され得る。（プロセス２００が適用され得るデータフローグラフを自動的に生成する）これら３つのアクトのそれぞれを、以下でより詳細に説明する。
【００７０】
幾つかの実施形態では、ＳＱＬクエリーは、ユーザが、入力としてデータ処理システムにＳＱＬクエリーを提供した結果、データ処理システム（例えば、例えばデータ処理システム６０２などのプロセス２００を実行するデータ処理システム）によって受信され得る。ユーザは、グラフィカルユーザインタフェース、又はその他の適宜のタイプのインタフェースを用いて、ＳＱＬクエリーを入力し得る。他の実施形態では、ＳＱＬクエリーは、別のコンピュータプログラムによって、データ処理システムに提供され得る。例えば、ＳＱＬクエリーは、データ処理システムに１つ又は複数のＳＱＬクエリー（各ＳＱＬクエリーは、ユーザによって指定されている場合、又は自動生成されている場合がある）を実行させるように構成されたコンピュータプログラムによって提供され得る。ＳＱＬクエリーは、任意の適宜のタイプのものでよく、及び任意の適宜のフォーマットで提供され得る（本明細書に記載の技術の局面は、この点において限定されない）。
【００７１】
幾つかの実施形態では、受信したＳＱＬクエリーを使用して、クエリープランを生成し得る。生成されたクエリープランは、ＳＱＬクエリーが実行された場合に行われる１つ又は複数のデータ処理動作を識別し得る。生成されたクエリープランはさらに、識別されたデータ処理動作が実行される順序を指定し得る。そのため、生成されたクエリープランは、受信したＳＱＬクエリーを実行するために行うデータ処理動作のシーケンスを表し得る。生成されたクエリープランは、任意の適宜のタイプのクエリープランジェネレータを用いて生成され得る。クエリープランを生成するための幾つかの例示的技術が、本明細書に全体として援用される、「データクエリー管理」というタイトルの米国特許第９，１１６，９５５号明細書に記載されている。
【００７２】
次に、幾つかの実施形態では、データフローグラフが、クエリープラン（これ自体は、受信したＳＱＬクエリーを用いて生成されたものである）から生成され得る。幾つかの実施形態では、データフローグラフは、少なくとも部分的に、クエリープランにおいて識別されたデータ処理動作の少なくともサブセット（例えば、一部又は全て）のそれぞれのノードを包含するようにデータフローグラフを生成することによって、クエリープランから生成され得る。幾つかの実施形態では、クエリープランにおける単一のノードは、データフローグラフにおける複数のノードの包含をもたらし得る。続いて、クエリープランで指定されたデータ処理動作の順序を使用して、データフローグラフにおけるノードを結び付けるリンクを生成し得る。例えば、生成されたクエリープランが、第２のデータ処理動作の前に、第１のデータ処理動作が行われることを示す場合、生成されたデータフローグラフは、第１のノード（第１のデータ処理動作を表す）及び第２のノード（第２のデータ処理動作を表す）と、第１のノードから第２のノードへの経路を指定する１つ又は複数のリンクとを有し得る。
【００７３】
幾つかの実施形態では、クエリープランからデータフローグラフを生成することは、入力及び／又は出力データソースを表すグラフに対して、１つ又は複数のノードを追加することを含む。例えば、データフローグラフの生成は、ＳＱＬクエリーの実行中にデータレコードが読み取られるデータソースのそれぞれに対して入力ノードを追加することを含み得る。各入力ノードは、それぞれのデータソースと関連付けられたパラメータ値を用いて構成され得る。これらの値は、データソース中のデータレコードにアクセスする方法を示し得る。別の例として、データフローグラフの生成は、ＳＱＬクエリーの実行中にデータレコードが書き込まれるデータシンクのそれぞれに対して出力ノードを追加することを含み得る。各出力ノードは、それぞれのデータシンクと関連付けられたパラメータ値を用いて構成され得る。これらの値は、データレコードをデータソースに書き込む方法を示し得る。
【００７４】
クエリープランから生成されたデータフローグラフは、クエリープラン自体とは異なることを認識されたい。データフローグラフが、グラフ実行環境（例えば、共働システム６１０、又はその他の適宜の、データフローグラフを実行するための実行環境）を用いることによって実行され得る一方で、クエリープランは、グラフ実行エンジンによって実行することができない（それは、データフローグラフの生成に使用される中間表現であり、このデータフローグラフは、ＳＱＬクエリーを実行するために、グラフ実行エンジンによって実行される）。クエリープランは、実行可能ではなく、リレーショナルデータベース管理システムの状況下でさえ、実行戦略を生成するために、さらに処理される必要がある。これに対して、データフローグラフは、ＳＱＬクエリーを実行するために、グラフ実行エンジンによって実行可能である。加えて、リレーショナルデータベースシステムによるさらなる処理後でさえ、結果として生じる実行戦略は、他のタイプのデータソース及び／又はデータシンクに対する、データの読み取り及び／又は書き込みを可能にしないが、データフローグラフは、この点において限定されない。
【００７５】
幾つかの実施形態では、クエリープランから生成されたデータフローグラフは、クエリープランに存在しないデータ処理動作を表すノードを含有し得る。逆に、幾つかの実施形態では、クエリープランから生成されたデータフローグラフは、クエリープランに存在するデータ処理動作を表すノードを含有しない場合がある。このような状況は、クエリープランからデータフローグラフを生成するプロセス中に行われ得る様々な最適化により生じ得る。幾つかの実施形態では、データフローグラフは、データベースコンピュータシステム（例えば、リレーショナルデータベース管理システム）に対して行われるデータベース動作以外のデータ処理動作を表すノードを含有し得る。
【００７６】
幾つかの実施形態では、クエリープラン及びデータフローグラフは、異なるタイプのデータ構造で具現化され得る。例えば、幾つかの実施形態では、クエリープランは、各ノードが単一の親ノードを有する有向グラフ（例えば、例えば二分木などの木）で具現化されてもよく、一方、データフローグラフは、複数の親ノードを有する少なくとも１つのノードを有し得る有向非巡回グラフで具現化され得る。
【００７７】
プロセス２００は、説明のためのものであり、バリエーションが存在することを認識されたい。例えば、図２の図示した実施形態では、中間ノードの処理レイアウトは、順方向パスの後に、逆方向パスを使用して決定されるが、他の実施形態では、その代わりに、処理レイアウトは、逆方向パスの後に順方向パスを使用して決定され得る。別の例として、図示した実施形態では、中間ノードの処理レイアウトは、入力ノード及び出力ノードに割り当てられたレイアウトに基づいて決定されていたが、本明細書に記載の処理レイアウト決定技術は、より一般的に適用され得る。例えば、処理レイアウトは、データフローグラフにおける１つ又は複数のノードのセットに関して取得されてもよく、及び処理レイアウトは、（１）ノードのセットに関して取得された処理レイアウト、（２）データフローグラフのリンク構造、及び（３）１つ又は複数のレイアウト決定ルールに基づいて、データフローグラフにおける他のノードに関して取得され得る。ノードのセットは、入力ノード及び出力ノードを包含し得るが、そうである必要はない。従って、ノードのセットは、任意の適宜の数（例えば、ゼロ、少なくとも１つ、全て）の入力ノード、任意の適宜の数（例えば、ゼロ、少なくとも１つ、全て）の出力ノード、及び任意の適宜の数（例えば、ゼロ、少なくとも１つ、全て）の他のノードを包含し得る。唯一の要件は、ノードのセットが空ではないことである。
【００７８】
幾つかの実施形態では、データ処理システムは、（１）データベースクエリー（例えば、ＳＱＬ）クエリーを受信し、（２）受信したデータベースクエリーを、データ処理システムによって実行されると、受信したデータベースクエリーを実行するコンピュータコード部分を含むコンピュータコードに変換し、及び（３）各コンピュータコード部分を実行するための処理レイアウトを自動的に決定し得る。幾つかの実施形態では、コンピュータコード部分を実行するための処理レイアウトは、コンピュータコード部分の実行順序を示す情報を用いて決定され得る。例えば、幾つかの実施形態では、各コンピュータコード部分は、データフローグラフにおけるそれぞれのノードと関連付けられてもよく、及び本明細書に記載のレイアウト決定ルールと共に、グラフの構造（例えば、ノード間の接続で具現化されるような）を用いて、処理レイアウトをノードに、及び関連して、ノードに関連付けられたコンピュータコード部分に割り当て得る。ただし、幾つかの実施形態では、コンピュータコード部分の実行順序を示す情報が、データフローグラフでエンコードされることに限定されず、その他の適宜のやり方（例えば、別のタイプの１つ又は複数のデータ構造）でエンコードされ得るので（本明細書に記載の技術の局面は、この点において限定されない）、コンピュータコード部分を実行するための処理レイアウトは、データフローグラフを用いることなく決定され得ることを認識されたい。
【００７９】
従って、幾つかの実施形態では、データ処理システムは、データ処理システムによって実行されると、データ処理にデータベースクエリーを実行させるコンピュータコードを取得（例えば、リモートソースから、及び／又はネットワーク接続上で受信、ローカルストレージからアクセスなど）することができ、コンピュータコードは、（Ａ）それぞれの入力データセットを読み込むデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第１のセット、（Ｂ）それぞれの出力データセットを書き出すデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第２のセット、及び（Ｃ）それぞれのデータ処理動作をそれぞれが表す１つ又は複数のコンピュータコード部分の第３のセットを含む。次に、データ処理システムは、コンピュータコードの一部であるコンピュータコード部分のそれぞれを実行するための処理レイアウトを決定し得る。例えば、幾つかの実施形態では、データ処理システムは、（Ａ）コード部分の第１のセットにおける１つ又は複数のコード部分に関する１つ又は複数の処理レイアウトの第１のセットを取得（例えば、受信、アクセスなど）し、（Ｂ）コード部分の第２のセットにおける１つ又は複数のコード部分に関する１つ又は複数の処理レイアウトの第２のセットを取得し、及び（Ｃ）処理レイアウトの第１のセット、処理レイアウトの第２のセット、及び異なる度合いの並列性を有する処理レイアウトの中から選択するための少なくとも１つのルールを包含する、本明細書に記載の１つ又は複数のレイアウト決定ルールに基づいて、コード部分の第３のセットにおける各コード部分に関する処理レイアウトを決定し得る。
【００８０】
幾つかの実施形態では、コンピュータコードは、データベースクエリーから生成され得る。例えば、幾つかの実施形態では、受信したデータベースクエリー（例えば、ＳＱＬクエリー）は、クエリープランに変換され、及びクエリープランは、コンピュータコードを生成するために処理され得る。例えば、クエリープランは、複数のノード及びエッジ（上記のような）を含むデータフローグラフに変換されてもよく、及びコンピュータコードは、コンピュータコード部分を包含してもよく、各コード部分は、データフローグラフにおけるノードによって表されるデータ処理動作を行うためのコードを含む。このようにして、幾つかの実施形態では、コンピュータコード部分は、データフローグラフにおけるそれぞれのノードと関連付けられ得る。
【００８１】
コンピュータコードがデータフローグラフと関連付けられる幾つかの実施形態では、データフローグラフのノードは、（Ａ）１つ又は複数のノードの第１のセットであって、ノードの第１のセットにおける各ノードが、それぞれの入力データセットを表し、（上記の）コンピュータコード部分の第１のセットにおける各コンピュータコード部分が、ノードの第１のセットにおけるそれぞれのノードと関連付けられる、１つ又は複数のノードの第１のセットと、（Ｂ）１つ又は複数のノードの第２のセットであって、ノードの第２のセットにおける各ノードが、それぞれの出力データセットを表し、（上記の）コンピュータコード部分の第２のセットにおける各コンピュータコード部分が、ノードの第２のセットにおけるそれぞれのノードと関連付けられる、１つ又は複数のノードの第２のセットと、１つ又は複数のノードの第３のセットであって、ノードの第３のセットにおける各ノードが、それぞれのデータ処理動作を表す、１つ又は複数のノードの第３のセットとを包含し得る。データ処理システムは、（１）第１及び第２のセットのノードを用いた処理レイアウトと、（２）本明細書に記載のレイアウト決定ルールの１つ又は複数と、（３）１つ又は複数の処理レイアウトをノードの第３のセット中のノードに割り当てるためのグラフの構造（データ処理動作間の順序付けを示す）とを使用し得る。これらの処理レイアウトは、次に、ノードの第３のセット中のノードと関連付けられたコンピュータコード部分を実行するために、データ処理システムによって使用され得る。
【００８２】
図３Ａ〜３Ｄは、図２を参照して記載された実施形態を包含する、本明細書に記載の技術の幾つかの実施形態による、１つ又は複数のレイアウト決定ルールを使用した、説明のためのデータフローグラフ３００におけるノードの処理レイアウトの決定を示す。特に、図３Ａ〜３Ｄの例は、幾つかの実施形態において、異なる度合いの並列性を有する２つの異なる処理レイアウトからレイアウトを選択することによって、ノードの処理レイアウトを決定する際に、より大きな度合いの並列性を有する処理レイアウトが、ノードの処理レイアウトとして選択され得ることを示す。
【００８３】
図３Ａは、それぞれの入力データセットを表すノード３０２及び３０４と、それぞれのデータ処理動作を表すノード３０６、３０８、３１０、及び３１２と、出力データセットを表すノード３１４とを有するデータフローグラフ３００を示す。データフローグラフ３００の構造から認識され得るように、ノード３０２によって表される入力データセットは、フィルタリングされ、ソートされ、及びその後、ノード３１４によって表される出力データセットに書き込まれる前に、ノード３０４によって表される入力データセットのフィルタリングされたバージョンと結合される。この例では、入力データセット及び出力データセットの処理レイアウトが取得された後に、図３Ａに示すように、順次処理レイアウトＳＬ１が、ノード３０２によって表されるデータセットからデータを読み取るために使用され、並列レイアウトＰＬ１が、ノード３０４によって表されるデータセットからデータを読み取るために使用され、及び順次処理レイアウトＳＬ２が、ノード３１４によって表されるデータセットに書き込むために使用されることが決定され得る。なお、順次処理レイアウトＳＬ１及びＳＬ２のそれぞれは、データが順次処理される（すなわち、１つの並列性の度合いを備える）ことを示すが、順次処理は、異なるプロセッサによって（例えば、ノード３０２によって表される入力データセットを保存するデータベースのプロセッサによって、及びノード３１４によって表される出力データセットを保存する別のデータベースのプロセッサによって）行われ得るので、これらの順次レイアウトは、同じである必要はない。この段階で、ノード３０６、３０８、３１０、及び３１２によって表されるデータ処理動作の処理レイアウトは、まだ決定されていない。
【００８４】
図３Ｂ及び３Ｃは、ノード３０２、３０４、及び３１４に関して取得された処理レイアウトに基づいた、ノード３０６、３０８、３１０、及び３１２によって表されるデータ処理動作の処理レイアウトの決定を示す。まず、図３Ｂに示すように、データフローグラフ３００の構造及び本明細書に記載のレイアウト決定ルールに従って、ノード３０２及び３０４から始まる順方向パスで、ノード３０６、３０８、３１０、及び３１２に関して、初期処理レイアウトが決定される。例えば、ノード３０６の処理レイアウトは、データフローグラフにおける先行ノード（ノード３０２）のレイアウトに基づいて決定される。次いで、ノード３０８の処理レイアウトが、データフローグラフにおける、それに先行するノード（ノード３０６）のレイアウトに基づいて決定される。ノード３１０の処理レイアウトが、それの先行ノード（すなわち、ノード３０４）のレイアウトに基づいて決定され、且つノード３０８の処理レイアウトが決定された後に、ノード３１２の処理レイアウトが、ノード３０８及び３１０（それぞれが、データフローグラフ３００においてノード３１２に先行し、及びノード３１２に接続される）のレイアウトに基づいて決定される。
【００８５】
この例では、順方向パス中に、ノード３０６の直前に、ノード３０２以外のノードが存在せず、且つ既にノード３０６に関連付けられたレイアウトが存在しないため、ノード３０２の順次レイアウトＳＬ１が、ノード３０６によって表されるデータ処理動作を行うために使用されることが決定される。次いで、ノード３０８に先行する、ノード３０６以外のノードが存在せず、且つ既にノード３０８に関連付けられたレイアウトが存在しないため、ノード３０６のレイアウトＳＬ１が、ノード３０８によって表されるデータ処理動作を行うために使用されることが決定される。同様に、ノード３１０に先行する、ノード３０４以外のノードが存在せず、且つ既にノード３１０に関連付けられたレイアウトが存在しないため、ノード３０４の並列レイアウトＰＬ１が、ノード３１０によって表されるデータ処理動作を行うために使用されることが決定される。このようにして、レイアウトＳＬ１及びＰＬ１が、入力ノード３０２及び３０４から、レイアウトがまだ決定されておらず、且つ単一の先行するノード（すなわち、この説明のための例では、ノード３０６、３０８、及び３１０）に接続されたノードへと、グラフ３００を通して伝播される。
【００８６】
順方向パス中に、結合動作を表すノード３１２の処理レイアウトが、先行ノード３０８の順次レイアウトＳＬ１及び先行ノード３１０の並列レイアウトＰＬ１から選択される。図３Ｂに示すように、順方向パス中に、異なる度合いの並列性を有する２つの異なる潜在的処理レイアウトから選択する際に、より大きな度合いの並列性を有する処理レイアウトが選択されることを示すレイアウト決定ルールを使用して、ノード３１２に関して、並列レイアウトＰＬ１が選択される。並列処理レイアウトＰＬ１が、処理レイアウトＳＬ１よりも大きな度合いの並列性を有するので、順方向パス中に、並列処理レイアウトＰＬ１が、ノード３１２に関して選択される。
【００８７】
次いで、図３Ｃに示すように、データフローグラフ３００の構造、図３Ｂに示した初期処理レイアウト、及び本明細書に記載のレイアウト決定ルールに従って、ノード３１４から始まる逆方向パスで、ノード３０６、３０８、３１０、及び３１２に関して、最終処理レイアウトが決定される。例えば、ノード３１２の最終処理レイアウトは、ノード３１２に関して決定された初期処理レイアウト、及びノード３１４のレイアウトに基づいて決定される。ノード３０８の最終処理レイアウトは、ノード３０８に関して決定された初期処理レイアウト、及びノード３１２に関して決定された最終処理レイアウトに基づいて決定される。ノード３０６の最終処理レイアウトは、ノード３０６に関して決定された初期処理レイアウト、及びノード３０８に関して決定された最終処理レイアウトに基づいて決定される。ノード３１０の最終処理レイアウトは、ノード３１０に関して決定された初期処理レイアウト、及びノード３１２に関して決定された最終処理レイアウトに基づいて決定される。
【００８８】
この例では、逆方向パス中に、ノード３１２の最終処理レイアウトが、順方向パス中にノード３１２に関して決定された初期処理レイアウトＰＬ１、及びノード３１４に関連付けられた順次処理レイアウトＳＬ２から選択される。図３Ｃに示すように、レイアウトＰＬ１が、レイアウトＳＬ２よりも大きな度合いの並列性を有するので、レイアウトＰＬ１が、ノード３１２の最終処理レイアウトであると決定される。ノード３０８の最終処理レイアウトが、順方向パス中にノード３０８に関して決定された初期レイアウトＳＬ１、及び逆方向パス中にノード３１２に関して決定された最終処理レイアウトＰＬ１から選択される。図３Ｃに示すように、レイアウトＰＬ１が、レイアウトＳＬ１よりも大きな度合いの並列性を有するので、レイアウトＰＬ１が、ノード３０８の最終処理レイアウトであると決定される。ノード３０６の最終処理レイアウトが、順方向パス中にノード３０６に関して決定された初期レイアウトＳＬ１、及び逆方向パス中にノード３０８に関して決定された最終処理レイアウトＰＬ１から選択される。図３Ｃに示すように、レイアウトＰＬ１が、レイアウトＳＬ１よりも大きな度合いの並列性を有するので、レイアウトＰＬ１が、ノード３０４の最終処理レイアウトであると決定される。順方向パス中にノード３１０に関して決定された初期レイアウトがＰＬ１であり、且つ逆方向パス中にノード３１２に関して決定された最終レイアウトもＰＬ１であるので、ノード３１０の最終処理レイアウトは、ＰＬ１であると決定される。
【００８９】
図３Ｃに示すように、データフローグラフ３００の各ノードに関して処理レイアウトが決定された後に、データフローグラフ３００は、１つ又は複数の再パーティショニング動作を行うように構成され得る。本明細書に記載するように、データフローグラフにおける隣接するノードが、異なる度合いの並列性を有する処理レイアウトを用いて、データレコードに対してデータ処理動作を行うように構成される場合に、データフローグラフは、データレコードに対して再パーティショニング動作を行うように構成され得る。例えば、図３Ｃに示すように、隣接するノード３０２（ＳＬ１）及びノード３０６（ＰＬ１）の処理レイアウトが、異なる度合いの並列性を有する。隣接するノード３１２（ＰＬ１）及びノード３１４（ＳＬ２）の処理レイアウトも、異なる度合いの並列性を有する。
【００９０】
幾つかの実施形態では、データフローグラフは、再パーティショニング動作を表す新しいノードをグラフに追加することによって、再パーティショニング動作を行うように構成され得る。例えば、図３Ｄに示すように、パーティション動作（例えば、パーティション・バイ・キー動作）を表す新しいノード３４２が、ノード３０２とノード３０６との間で、データフローグラフに追加され得る。データレコードが、ノード３４２を有するデータフローグラフに従って処理される場合、データレコードは、ノード３０２の処理レイアウトＳＬ１を用いて読み取られた後であるが、ノード３０６の処理レイアウトＰＬ１を用いてフィルタリングされる前に、ノード３４２によって表されるパーティショニング動作に従って、パーティションが行われる。パーティショニング動作は、ノード３０８のレイアウトＳＬ１に従って行われ得る。加えて、図３Ｄに示すように、マージ動作を表す新しいノード３４４が、ノード３１２とノード３１４との間で、データフローグラフに追加され得る。データレコードが、ノード３４４を有するデータフローグラフに従って処理される場合、データレコードは、ノード３１２の処理レイアウトＰＬ１を用いて処理された後であるが、ノード３１４の処理レイアウトＳＬ２を用いて出力される前に、マージされる。マージング動作は、ノード３１４のレイアウトＳＬ２に従って行われ得る。
【００９１】
図３Ｄの説明のための例では、データフローグラフ３４０を取得するために、２つの新しいノードが、データフローグラフ３００に追加される。ただし、幾つかの実施形態では、データフローグラフは、グラフに新しいノードを追加することなく、１つ又は複数の再パーティショニング動作を行うように構成され得ることを認識されたい。幾つかの実施形態では、１つ又は複数の既存のノードのそれぞれが、それぞれの再パーティショニング動作を行うように構成され得る。例えば、図３Ｄの説明のための実施形態に示すように新しいノード３４２を追加するのではなく、ノード３０２又はノード３０６のどちらかが、パーティショニング動作を行うように構成され得る。別の例として、図３Ｄの説明のための実施形態に示すように新しいノード３４４を追加するのではなく、ノード３１２又はノード３１４のどちらかが、マージング動作を行うように構成され得る。
【００９２】
図４Ａ〜４Ｃは、図２を参照して記載された実施形態を包含する、本明細書に記載の技術の幾つかの実施形態による、１つ又は複数のレイアウト決定ルールを使用した、説明のためのデータフローグラフ４００におけるノードの処理レイアウトの決定を示す。特に、図４Ａ〜４Ｃの例は、幾つかの実施形態において、同じ度合いの並列性を有する２つの処理レイアウトからレイアウトを選択することによって、ノードの処理レイアウトを決定する際に、より多数のレコードに適用される処理レイアウトが、ノードの処理レイアウトとして選択され得ることを示す。
【００９３】
図４Ａは、それぞれの入力データセットを表すノード４０２及び４０４と、データ処理動作を表すノード４０６と、出力データセットを表すノード４０８とを有するデータフローグラフ４００を示す。データフローグラフ４００の構造から認識され得るように、Ｎ個のデータレコードを有し、及びノード４０２によって表される入力データセットが、Ｍ個のレコード（Ｍは、Ｎより小さい）を有し、及びノード４０４によって表される入力データセットと結合される。データセットが結合された後に、それらは、ノード４０８によって表される出力データセットに書き込まれる。この例では、入力データセット及び出力データセットの処理レイアウトが取得された後に、並列処理レイアウトＰＬ１が、ノード４０２によって表されるデータセットからデータを読み取るために使用され、並列処理レイアウトＰＬ２が、ノード４０４によって表されるデータセットからデータを読み取るために使用され、及び順次レイアウトＳＬ１が、ノード４０８によって表される出力データセットにデータレコードを書き込むために使用されることが決定され得る。処理レイアウトＰＬ１及びＰＬ２のそれぞれは、同じ度合いの並列性を有する。この段階で、ノード４０６によって表される結合動作の処理レイアウトは、まだ決定されていない。
【００９４】
順方向パス中に、データフローグラフ４００におけるノード４０６に先行するノード４０２及び４０４の処理レイアウトに基づいて、ノード４０６の初期処理レイアウトが決定される。図示した例では、ノード４０６の初期処理レイアウトは、ノード４０２に関連付けられた処理レイアウトＰＬ１、及びノード４０４に関連付けられた処理レイアウトＰＬ２の中から選択される。レイアウトＰＬ１及びＰＬ２のそれぞれが、同じ度合いの並列性を有する場合でも、レイアウトＰＬ１が、Ｍ＜Ｎ個のデータレコードの処理（例えば、ノード４０４によって表される入力データセットからのＭ個のデータレコードの読み取り）に適用されるレイアウトＰＬ２よりも多数のレコードＮを処理する（例えば、ノード４０２によって表される入力データセットからＮ個のデータレコードを読み取る）ために適用されるので、レイアウトＰＬ１が、ノード４０６の初期処理レイアウトとして選択される。レイアウトＰＬ２に従って、結合動作が処理される場合に移動されなければならないレコード数（例えば、Ｎ個のレコード）よりも、レイアウトＰＬ１に従って、ノード４０６によって表される結合動作を処理する際に、少ない数のデータレコード（例えば、Ｍ＜Ｎ個のレコード）が移動される必要があり得るので、この選択は、効率を目的として行われ得る。
【００９５】
次いで、逆方向パス中に、ノード４０６の最終処理レイアウトが、ノード４０６に関して決定された初期処理レイアウト（ＰＬ１）、及びノード４０８に関連付けられた処理レイアウト（ＳＬ１）に基づいて決定される。レイアウトＰＬ１が、レイアウトＳＬ１よりも大きな度合いの並列性を有するので、ＰＬ１が、ノード４０６の最終処理レイアウトであると決定される。従って、順方向パス及び逆方向パスが完了した後に、図４Ｂに示すように、ＰＬ１が、ノード４０６の最終処理レイアウトであると決定される。
【００９６】
図４Ｂに示すように、データフローグラフ４００の各ノードに関して処理レイアウトが決定された後に、データフローグラフ４００は、１つ又は複数の再パーティショニング動作を行うように構成され得る。本明細書に記載するように、データフローグラフにおける隣接するノードが、異なる度合いの並列性を有する処理レイアウトを用いて、データレコードに対してデータ処理動作を行うように構成される場合に、データフローグラフは、データレコードに対して再パーティショニング動作を行うように構成され得る。例えば、図４Ｂに示すように、隣接するノード４０６（ＰＬ１）及びノード４０８（ＳＬ１）の処理レイアウトが、異なる度合いの並列性を有する。
【００９７】
本明細書に述べた通り、幾つかの実施形態では、データフローグラフは、再パーティショニング動作を表す新しいノードをグラフに追加することによって、再パーティショニング動作を行うように構成され得る。例えば、図４Ｃに示すように、データフローグラフ４３０を取得するために、マージ動作を表す新しいノード４０７が、データフローグラフ４００に追加され得る。データレコードが、ノード４０７を有するデータフローグラフに従って処理される場合、データレコードは、ノード４０６の処理レイアウトＰＬ１を用いて処理された後であるが、ノード４０８の処理レイアウトＳＬ１を用いて出力される前に、マージされる。マージング動作は、ノード４０８のレイアウトＳＬ１に従って行われ得る。他の実施形態では、マージ動作を行うために新しいノードをデータフローグラフ４００に追加する代わりに、既存のノードの一方（例えば、４０６又は４０８）が、マージ動作を行うように構成され得る。
【００９８】
図５Ａ〜５Ｄは、図２を参照して記載された実施形態を包含する、本明細書に記載の技術の幾つかの実施形態による、１つ又は複数のレイアウト決定ルールを使用した、説明のためのデータフローグラフ５００におけるノードの処理レイアウトの決定を示す。特に、図５Ａ〜５Ｄの例は、幾つかの実施形態において、ある処理レイアウトが、特定のノードを越えて伝播されない特定の１つ又は複数のノードのレイアウトとして、他のノードの処理レイアウトを決定する際に、選定され得ることを示す。
【００９９】
図５Ａは、それぞれの入力データセットを表すノード５０２及び５０４と、それぞれのデータ処理動作を表すノード５０６、５０８、５１０、及び５１２と、出力データセットを表すノード５１４とを有するデータフローグラフ５００を示す。データフローグラフ５００の構造から認識され得るように、ノード５０２によって表される入力データセットは、まずフィルタリングされ、次に、フィルタリングされたデータに対して、ロールアップ動作が行われ、及びロールアップ動作の結果として取得されたデータレコードが、ノード５１４によって表される出力データセットに書き込まれる前に、ノード５０４によって表される入力データセットのフィルタリングされたバージョンと結合される。この例では、入力データセット及び出力データセットの処理レイアウトが取得された後に、図５Ａに示すように、並列処理レイアウトＰＬ１が、ノード５０２によって表される入力データセットからデータを読み取るために使用され、順次レイアウトＳＬ１が、ノード５０４によって表される入力データセットからデータを読み取るために使用され、及び順次処理レイアウトＳＬ２が、ノード５１４によって表される出力データセットに書き込むために使用されることが決定され得る。加えて、この例では、処理レイアウトＰＬ１が、他のノードに伝播されないという指示が、取得され得る。この指示は、任意の適宜のやり方で取得することができ、例えば、グラフィカルユーザインタフェースを介してユーザから取得され得る。この段階で、ノード５０６、５０８、５１０、及び５１２によって表されるデータ処理動作の処理レイアウトは、まだ決定されていない。
【０１００】
図５Ｂ及び５Ｃは、ノード５０２、５０４、及び５１４に関して取得された処理レイアウトに基づいた、ノード５０６、５０８、５１０、及び５１２によって表されるデータ処理動作の処理レイアウトの決定を示す。まず、図５Ｂに示すように、データフローグラフ５００の構造及び本明細書に記載のレイアウト決定ルールに従って、ノード５０２及び５０４から始まる順方向パスで、ノード５０６、５０８、５１０、及び５１２に関して、初期処理レイアウトが決定される。この例では、ノード５０２の処理レイアウトＰＬ１が伝播されないという指示が取得されているので、レイアウトＰＬ１は、フィルタリング動作を表すノード５０６に対してのみコピーされ（フィルタリング動作は、ノード５０２によって表される入力データセットからデータレコードを読み取るために使用されるレイアウトと同じ処理レイアウト（実際には、同じコンピューティングデバイス）を使用して行われ得るタイプの動作であるので）、例えば、ロールアップ動作を表すノード５０８などの他のノードへはコピーされない。
【０１０１】
従って、順方向パス中に、ノード５０６の初期処理レイアウトが、ＰＬ１であると決定され、及びＰＬ１がノード５０６を越えて伝播されないので、ノード５０８の初期処理レイアウトは決定されない。以下に述べるように、ノード５０８の処理レイアウトは、逆方向パスにおいて決定される。
【０１０２】
加えて、順方向パス中に、ノード５１０の直前に、ノード５０４以外のノードが存在せず、且つ既にノード５１０に関連付けられたレイアウトが存在しないため、ノード５１０の初期処理レイアウトが、ノード５０４の順次レイアウトＳＬ１であると決定される。次いで、ノード５１０が、ある特定のレイアウトと関連付けられた、ノード５１２に先行する唯一のノードであるので（上述の通り、ノード５０８は、ノード５１２に先行するが、それは、どの初期処理レイアウトとも関連付けられていない）、ノード５１０の初期処理レイアウトＳＬ１も、ノード５１２の初期処理レイアウトであると決定される。順方向パスの結果として決定された初期処理レイアウトを図５Ｂに示す。ノード５０８を除く全てのノードが、初期処理レイアウトを割り当てられている。
【０１０３】
次に、図５Ｃに示すように、データフローグラフ５００の構造、図５Ｂに示した初期処理レイアウト、及び本明細書に記載のレイアウト決定ルールに従って、ノード５１４から始まる逆方向パスで、ノード５０６、５０８、５１０、及び５１２に関して、最終処理レイアウトが決定される。例えば、ノード５１２の最終処理レイアウトは、ノード５１２に関して決定された初期処理レイアウト、及びノード５１４に関連付けられた処理レイアウトに基づいて決定される。ノード５０８の最終処理レイアウトは、ノード５１２に関して決定された最終処理レイアウトに基づいて決定される（この例では、ノード５０８に関して、初期レイアウトは決定されていない）。ノード５０６の最終処理レイアウトは、ノード５０６に関して決定された初期処理レイアウト、及びノード５０８に関して決定された最終処理レイアウトに基づいて決定される。ノード５１０の最終処理レイアウトは、ノード５１０に関して決定された初期処理レイアウト、及びノード５１２に関して決定された最終処理レイアウトに基づいて決定される。
【０１０４】
この例では、逆方向パス中に、ノード５１２の最終処理レイアウトが、順方向パス中にノード５１２に関して決定された初期処理レイアウトＳＬ１、及びノード５１４に関連付けられた順次処理レイアウトＳＬ２から選択される。図５Ｃに示すように、レイアウトＳＬ１が、ノード５１２の最終処理レイアウトであると決定される。ノード５０８の最終処理レイアウトは、レイアウトＳＬ１が、ノード５１２の最終決定レイアウトであり、及びノード５０８が、順方向パス後に、どの初期処理レイアウトとも関連付けられていないので、レイアウトＳＬ１であると決定される。ノード５０６の最終処理レイアウトは、ＰＬ１が、ノード５０８の最終処理レイアウトであると決定されたレイアウトＳＬ１よりも大きな度合いの並列性を有するので、ＰＬ１（ノード５０６に関して決定された初期レイアウト）であると決定される。ノード５１０の最終処理レイアウトは、順方向パス中にノード５１０に関して決定された初期レイアウトがＳＬ１であり、且つ逆方向パス中にノード５１２に関して決定された最終レイアウトもＳＬ１であるので、ＳＬ１であると決定される。
【０１０５】
図５Ｃに示すように、データフローグラフ５００の各ノードに関して処理レイアウトが決定された後に、データフローグラフ５００は、１つ又は複数の再パーティショニング動作を行うように構成され得る。本明細書に記載するように、データフローグラフにおける隣接するノードが、異なる度合いの並列性を有する処理レイアウトを用いて、データレコードに対してデータ処理動作を行うように構成される場合に、データフローグラフは、データレコードに対して再パーティショニング動作を行うように構成され得る。例えば、図５Ｃに示すように、隣接するノード５０６（ＰＬ１）及びノード５０８（ＳＬ１）の処理レイアウトが、異なる度合いの並列性を有する。
【０１０６】
本明細書に述べた通り、幾つかの実施形態では、データフローグラフは、再パーティショニング動作を表す新しいノードをグラフに追加することによって、再パーティショニング動作を行うように構成され得る。例えば、図５Ｄに示すように、データフローグラフ５３０を取得するために、マージ動作を表す新しいノード５３２が、データフローグラフ５００に追加され得る。データレコードが、ノード５３２を有するデータフローグラフに従って処理される場合、データレコードは、ノード５０６の処理レイアウトＰＬ１を用いて処理された後であるが、ノード５０８の処理レイアウトＳＬ１を用いて出力される前に、集約される。集約動作は、ノード５０８のレイアウトＳＬ１に従って行われ得る。他の実施形態では、集約動作を行うために新しいノードをデータフローグラフ５００に追加する代わりに、既存のノードの一方（例えば、５０６又は５０８）が、集約動作を行うように構成され得る。
【０１０７】
図６は、本明細書に記載する技術の幾つかの実施形態が動作し得る、説明のためのコンピューティング環境６００のブロック図である。環境６００は、データ記憶装置６１０、６１２、６１４、及び６１６にアクセスする（例えば、データを読み取る、及び／データを書き込む）ように構成されたデータ処理システム６０２を包含する。データ記憶装置６１０、６１２、６１４、及び６１６のそれぞれは、１つ又は複数のデータセットを保存し得る。データ記憶装置は、任意の適宜のタイプのデータを、任意の適宜のやり方で保存し得る。データ記憶装置は、フラットテキストファイルとして、スプレッドシートとして、データベースシステム（例えば、リレーショナルデータベースシステム）を使用して、又はその他の適宜のやり方で、データを保存し得る。場合によっては、データ記憶装置は、トランザクションデータを保存し得る。例えば、データ記憶装置は、クレジットカード決済、通話記録データ、又は銀行取引データを保存し得る。データ処理システム６０２は、任意の適宜のタイプの、任意の適宜の数のデータ記憶装置にアクセスするように構成され得ることを認識されたい（本明細書に記載する技術の局面は、この点において限定されない）。
【０１０８】
データ処理システムは、一人又は複数のユーザにデータフローグラフを作成するためのインタフェースを提供するグラフィカル開発環境（ＧＤＥ）６０６を包含する。ＧＤＥ６０６を使用して作成されたデータフローグラフは、共働システム６１０、又はその他の適宜の、データフローグラフを実行するための実行環境を用いて実行され得る。グラフィカル開発環境及びデータフローグラフを実行するための環境の局面は、それぞれ本明細書に全体として援用される、「グラフとして表現される計算の実行」というタイトルの米国特許第５，９６６，０７２号明細書、及び「グラフベース計算のパラメータ管理」というタイトルの米国特許第７，７１６，６３０号明細書に記載されている。ＧＤＥ６０６を使用して作成された、又はその他の適宜のやり方で取得されたデータフローグラフは、データ処理システム６０２の一部であるデータフローグラフ記憶装置６０８に保存され得る。
【０１０９】
データ処理システム６０２は、データフローグラフのノードの処理レイアウトを、共働システム６１０による、そのデータフローグラフの実行前に決定するように構成された並列処理モジュール６０４も包含する。並列処理モジュール６０４は、例えば図２のプロセス２００を参照して記載した技術を包含する、本明細書に記載の技術の何れかを使用して、データフローグラフのノードの処理レイアウトを決定し得る。
【０１１０】
図７は、本明細書に記載する技術を実施することができる適宜のコンピューティングシステム環境７００の一例を図示する。コンピューティングシステム環境７００は、適宜のコンピューティング環境の一例にすぎず、本明細書に記載する技術の使用又は機能性の範囲に関して何ら制限を示唆することを意図したものではない。コンピューティング環境７００は、例示的動作環境７００に図示されるコンポーネントの何れか１つ又は組み合わせに関する依存性又は要件を有すると解釈されるべきものでもない。
【０１１１】
本明細書に記載する技術は、多数の他の汎用又は専用コンピューティングシステムの環境又は構成と共に使用可能である。本明細書に記載する技術と共に使用するのに適し得る周知のコンピューティングシステム、環境、及び／又は構成の例には、限定されることはないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルド又はラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブル大衆消費電子製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステム又はデバイスの何れかを包含する分散コンピューティング環境などが包含される。
【０１１２】
コンピューティング環境は、プログラムモジュールなどのコンピュータ実行可能命令を実行することができる。一般に、プログラムモジュールには、特定のタスクを行う、又は特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが包含される。本明細書に記載する技術は、通信ネットワークを通してリンクされるリモート処理デバイスによってタスクが行われる分散コンピューティング環境において実行されてもよい。分散コンピューティング環境では、プログラムモジュールは、メモリストレージデバイスを包含するローカル及びリモートコンピュータストレージ媒体の両方に位置していてもよい。
【０１１３】
図７を参照して、本明細書に記載する技術を実施する例示的システムは、コンピュータ７１０の形態の汎用コンピューティングデバイスを包含する。コンピュータ７１０のコンポーネントは、限定されないが、処理装置７２０、システムメモリ７３０、及びシステムメモリを包含する様々なシステムコンポーネントを処理装置７２０に結合するシステムバス７２１を包含してもよい。システムバス７２１は、様々なバスアーキテクチャの何れかを使用した、メモリバス又はメモリコントローラ、周辺バス、及びローカルバスを包含する幾つかのタイプのバス構造の何れかであってもよい。例として、及び限定ではなく、このようなアーキテクチャには、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、ビデオ電子装置規格化協会（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）（ＶＥＳＡ）ローカルバス、及びメザニンバスとしても知られるペリフェラルコンポーネントインターコネクト（ＰＣＩ）バスが包含される。
【０１１４】
コンピュータ７１０は、一般的に、様々なコンピュータ可読媒体を包含する。コンピュータ可読媒体は、コンピュータ７１０によってアクセスすることができる任意の入手可能な媒体でよく、及び揮発性及び不揮発性両方の媒体、リムーバブル及び非リムーバブル媒体を包含する。例として、及び限定ではなく、コンピュータ可読媒体は、コンピュータストレージ媒体及び通信媒体を含んでもよい。コンピュータストレージ媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、又は他のデータなどの情報のストレージのための任意の方法又は技術で実施される、揮発性及び不揮発性、リムーバブル及び非リムーバブル媒体を包含する。コンピュータストレージ媒体には、限定されないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ又は他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）又は他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ又は他の磁気ストレージデバイス、又は所望の情報を保存するために使用することができ、且つコンピュータ７１０によってアクセスすることができるその他の媒体が包含される。通信媒体は、一般的に、コンピュータ可読命令、データ構造、プログラムモジュール、又は他のデータを搬送波又は他のトランスポート機構などの変調データ信号で具現化し、及びあらゆる情報配信媒体を包含する。「変調データ信号」という用語は、それの特性集合の１つ又は複数を有する、又は信号の情報をエンコードするように変更された信号を意味する。例として、及び限定ではなく、通信媒体には、有線ネットワーク又は直接有線接続などの有線媒体、及び音響、ＲＦ、赤外線、及び他の無線媒体などの無線媒体が包含される。上記の何れかの組み合わせも、コンピュータ可読媒体の範囲内に包含されるものとする。
【０１１５】
システムメモリ７３０は、読み出し専用メモリ（ＲＯＭ）７３１及びランダムアクセスメモリ（ＲＡＭ）７３２などの揮発性及び／又は不揮発性メモリの形態のコンピュータストレージ媒体を包含する。起動時などに、コンピュータ７１０内の素子間で情報を転送することを助ける基本ルーチンを含有した、基本入出力システム７３３（ＢＩＯＳ）は、一般的に、ＲＯＭ７３１内に保存される。ＲＡＭ７３２は、一般的に、即座に利用できる、及び／又は処理装置７２０によって現在操作されているデータ及び／又はプログラムモジュールを含有する。例として、及び限定ではなく、図７は、オペレーティングシステム７３４、アプリケーションプログラム７３５、他のプログラムモジュール７３６、及びプログラムデータ７３７を図示する。
【０１１６】
コンピュータ７１０は、他のリムーバブル／非リムーバブル、揮発性／不揮発性コンピュータストレージ媒体も包含することができる。単なる例として、図７は、非リムーバブル、不揮発性磁気媒体に対する読み取り又は書き込みを行うハードディスクドライブ７４１、フラッシュメモリなどのリムーバブル、不揮発性メモリ７５２に対する読み取り又は書き込みを行うフラッシュドライブ７５１、及びＣＤ−ＲＯＭ又は他の光学媒体などのリムーバブル、不揮発性光ディスク７５６に対する読み取り又は書き込みを行う光ディスクドライブ７５５を図示する。例示的動作環境において使用することができる他のリムーバブル／非リムーバブル、揮発性／不揮発性コンピュータストレージ媒体には、限定されないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、固体ＲＡＭ、固体ＲＯＭなどが包含される。ハードディスクドライブ７４１は、一般的に、インタフェース７４０などの非リムーバブルメモリインタフェースを通してシステムバス７２１に接続され、及び磁気ディスクドライブ７５１及び光ディスクドライブ７５５は、一般的に、インタフェース７５０などのリムーバブルメモリインタフェースによってシステムバス７２１に接続される。
【０１１７】
上述した、及び図７に図示したドライブ及びそれらに関連付けられたコンピュータストレージ媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、及びコンピュータ７１０の他のデータのストレージを提供する。図７においては、例えば、ハードディスクドライブ７４１は、オペレーティングシステム７４４、アプリケーションプログラム７４５、他のプログラムモジュール７４６、及びプログラムデータ７４７を保存するものとして図示される。これらのコンポーネントは、オペレーティングシステム７３４、アプリケーションプログラム７３５、他のプログラムモジュール７３６、及びプログラムデータ７３７と同じであってもよいし、あるいは異なっていてもよいことに留意されたい。オペレーティングシステム７４４、アプリケーションプログラム７４５、他のプログラムモジュール７４６、及びプログラムデータ７４７は、少なくとも、それらが異なるコピーであることを図示するために、ここでは、異なる番号が付与されている。ユーザは、キーボード７６２及び一般にマウス、トラックボール、又はタッチパッドと呼ばれるポインティングデバイス７６１などの入力デバイスによって、コンピュータ７１０にコマンド及び情報を入力することができる。他の入力デバイス（不図示）には、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどが包含され得る。これら及び他の入力デバイスは、システムバスに結合されたユーザ入力インタフェース７６０によって、処理装置７２０に接続されることが多いが、パラレルポート、ゲームポート、又はユニバーサルシリアルバス（ＵＳＢ）などの他のインタフェース及びバス構造によって接続されてもよい。モニタ７９１又は他のタイプのディスプレイデバイスも、ビデオインタフェース７９０などのインタフェースを介して、システムバス７２１に接続される。モニタに加えて、コンピュータは、出力周辺インタフェース７９５を通して接続することができる、スピーカ７９７及びプリンタ７９６などの他の周辺出力デバイスも包含することができる。
【０１１８】
コンピュータ７１０は、リモートコンピュータ７８０などの１つ又は複数のリモートコンピュータへの論理接続を用いたネットワーク化環境で動作することができる。リモートコンピュータ７８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、又は他の共通ネットワークノードでもよく、及び一般的に、図７ではメモリストレージデバイス７８１のみが図示されているが、コンピュータ７１０に関連して上記した素子の多く又は全てを包含する。図７に描かれる論理接続は、ローカルエリアネットワーク（ＬＡＮ）７７１及び広域ネットワーク（ＷＡＮ）７７３を包含するが、他のネットワークも包含してもよい。このようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、及びインターネットにおいて、ありふれたものである。
【０１１９】
ＬＡＮネットワーキング環境で使用される場合、コンピュータ７１０は、ネットワークインタフェース又はアダプタ７７０を通してＬＡＮ７７１に接続される。ＷＡＮネットワーキング環境で使用される場合、コンピュータ７１０は、一般的に、モデム７７２、又はインターネットなどのＷＡＮ７７３上で通信を確立するための他の手段を包含する。内部又は外部のものでもよいモデム７７２は、ユーザ入力インタフェース７６０又は他の適宜の機構を介して、システムバス７２１に接続されてもよい。ネットワーク化環境において、コンピュータ７１０に関連して描かれたプログラムモジュール、又はそれらの一部は、リモートメモリストレージデバイスに保存されてもよい。例として、及び限定ではなく、図７は、メモリデバイス７８１に常駐しているとして、リモートアプリケーションプログラム７８５を図示する。示されるネットワーク接続は、例示的なものであり、及びコンピュータ間で通信リンクを確立する他の手段が使用されてもよいことが理解されるだろう。
【０１２０】
本発明の少なくとも１つの実施形態の幾つかの態様を上記のように記載したが、様々な変更、修正、及び改良が、当業者には容易に思い付くことが理解されるものとする。
【０１２１】
このような変更、修正、及び改良は、本開示の一部であることが意図され、及び本発明の精神及び範囲内であることが意図される。さらに、本発明の利点が示されるが、本明細書に記載の技術の全ての実施形態が、全ての記載した利点を包含するわけではないことが理解されるものとする。幾つかの実施形態は、本明細書において有利であると記載された何れの特徴も実施しない場合があり、場合によっては、記載された特徴の１つ又は複数が、さらなる実施形態を得るために実施されてもよい。従って、上記の記載及び図面は、単なる例である。
【０１２２】
本明細書に記載の技術の上記実施形態は、多数のやり方の何れで実施されてもよい。例えば、これらの実施形態は、ハードウェア、ソフトウェア、又はそれらの組み合わせを用いて実施されてもよい。ソフトウェアで実施される場合には、ソフトウェアコードは、単一のコンピュータにおいて提供されていようと、複数のコンピュータ間で分散されていようと、任意の適宜のプロセッサ又は一群のプロセッサ上で実行することができる。このようなプロセッサは、集積回路として実施されてもよく、業界において、ＣＰＵチップ、ＧＰＵチップ、マイクロプロセッサ、マイクロコントローラ、又はコプロセッサなどの名称で知られている市販の集積回路コンポーネントを包含する集積回路コンポーネントにおいて、１つ又は複数のプロセッサを有する。代替的に、プロセッサは、ＡＳＩＣなどのカスタム回路、又はプログラマブル論理デバイスの構成に起因するセミカスタム回路において実施されてもよい。又さらなる代替手段として、プロセッサは、市販、セミカスタム、あるいはカスタムであろうと、より大きな回路又は半導体デバイスの一部であってもよい。ある具体例として、幾つかの市販のマイクロプロセッサは、複数のコアの１つ又はサブセットがプロセッサを構成することができるように、複数のコアを有する。しかし、プロセッサは、任意の適宜のフォーマットの回路を使用して実施することができる。
【０１２３】
さらに、コンピュータは、ラックマウント式コンピュータ、デスクトップコンピュータ、ラップトップコンピュータ、又はタブレットコンピュータなどの多数の形態の何れかで具現化されてもよいことが理解されるものとする。追加的に、コンピュータは、携帯情報端末（ＰＤＡ）、スマートフォン、又は任意のその他の適宜のポータブル又は固定電子デバイスを包含する、一般にコンピュータとは見なされないが、適宜の処理能力を備えたデバイスに組み込まれてもよい。
【０１２４】
又、コンピュータは、１つ又は複数の入力デバイス及び出力デバイスを有していてもよい。これらのデバイスは、特に、ユーザインタフェースを提示するために使用することができる。ユーザインタフェースを提供するために使用することができる出力デバイスの例には、出力の視覚的表現のためのプリンタ又はディスプレイスクリーン、及び出力の可聴表現のためのスピーカ又は他の音生成デバイスが包含される。ユーザインタフェースに使用することができる入力デバイスの例には、キーボード、並びにマウス、タッチパッド、及びデジタイザタブレットなどのポインティングデバイスが包含される。別の例として、コンピュータは、音声認識により、又は他の可聴フォーマットで入力情報を受信してもよい。
【０１２５】
このようなコンピュータは、企業ネットワーク又はインターネットなどのローカルエリアネットワーク又は広域ネットワークとして包含する、任意の適宜の形態の１つ又は複数のネットワークによって相互接続することができる。このようなネットワークは、任意の適宜の技術に基づいてもよく、及び任意の適宜のプロトコルに従って動作してもよく、及び無線ネットワーク、有線ネットワーク、又は光ファイバネットワークを包含してもよい。
【０１２６】
又、本明細書に概要が述べられる様々な方法又はプロセスは、様々なオペレーティングシステム又はプラットフォームの何れか１つを用いる１つ又は複数のプロセッサに対して実行可能なソフトウェアとして符号化されてもよい。追加的に、このようなソフトウェアは、多数の適宜のプログラミング言語及び／又はプログラミング又はスクリプト作成ツールの何れかを使用して書かれてもよく、及びフレームワーク又は仮想マシンに対して実行される実行可能マシン語コード又は中間コードとしてコンパイルされてもよい。
【０１２７】
この点において、本発明は、１つ又は複数のコンピュータ又は他のプロセッサに対して実行されると、上述の本発明の様々な実施形態を実施する方法を行う１つ又は複数のプログラムでエンコードされたコンピュータ可読ストレージ媒体（又は複数のコンピュータ可読媒体）（例えば、コンピュータメモリ、１つ又は複数のフロッピーディスク、コンパクトディスク（ＣＤ）、光ディスク、デジタルビデオディスク（ＤＶＤ）、磁気テープ、フラッシュメモリ、フィールドプログラマブルゲートアレイ又は他の半導体デバイスにおける回路構成、又は他の有形コンピュータストレージ媒体）として具現化されてもよい。上記の例から明らかなように、コンピュータ可読ストレージ媒体は、非一時的な形態でコンピュータ実行可能命令を提供するのに十分な時間の間、情報を保持することができる。このような１つ又は複数のコンピュータ可読ストレージ媒体は、それ（ら）に保存された１つ又は複数のプログラムを、上述のような本発明の様々な態様を実施するために、１つ又は複数の異なるコンピュータ又は他のプロセッサにロードすることができるように、可搬であってもよい。本明細書においては、「コンピュータ可読ストレージ媒体」という用語は、製品（すなわち、製造物）又はマシンであると見なすことができる非一時的コンピュータ可読媒体のみを網羅する。代替的又は追加的に、本発明は、伝搬信号などの、コンピュータ可読ストレージ媒体以外のコンピュータ可読媒体として具現化されてもよい。
【０１２８】
「プログラム」又は「ソフトウェア」という用語は、本明細書では、上述のような本発明の様々な態様を実施するようにコンピュータ又は他のプロセッサをプログラムするために使用することができる、あらゆるタイプのコンピュータコード又はコンピュータ実行可能命令のセットを指すために総称的に使用される。追加的に、本実施形態のある態様によれば、実行されると、本発明の方法を行う１つ又は複数のコンピュータプログラムは、単一のコンピュータ又はプロセッサに常駐する必要はなく、本発明の様々な態様を実施するために、多数の異なるコンピュータ又はプロセッサ間で、モジュラー方式で分散されてもよいことが理解されるものとする。
【０１２９】
コンピュータ実行可能命令は、１つ又は複数のコンピュータ又は他のデバイスによって実行される、プログラムモジュールなどの多くの形態のものでもよい。一般に、プログラムモジュールには、特定のタスクを行う、又は特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが包含される。一般的に、プログラムモジュールの機能性は、様々な実施形態において、要望通りに組み合わせられてもよいし、あるいは分散されてもよい。
【０１３０】
又、データ構造は、任意の適宜の形態でコンピュータ可読媒体に保存されてもよい。図示を簡単にするために、データ構造は、データ構造内の場所によって関連したフィールドを有して示される場合がある。このような関係は、同様に、フィールドのストレージにフィールド間の関係を伝達するコンピュータ可読媒体内の場所を割り当てることによって、達成することができる。但し、ポインタ、タグ、又はデータ要素間の関係を確立する他の機構の使用によることを包含する、任意の適宜の機構を使用して、データ構造のフィールドにおける情報間の関係を確立してもよい。
【０１３１】
本発明の様々な態様は、単独で、組み合わせて、又は上記に記載した実施形態において具体的に述べられていない様々な配置で使用されてもよく、従って、その適用において、上記の説明に記載された、又は図面に図示されたコンポーネントの詳細及び配置に限定されない。例えば、ある実施形態に記載した態様は、任意の様式で、他の実施形態に記載した態様と組み合わせることができる。
【０１３２】
又、本発明は、一例を提供した方法として具現化されてもよい。この方法の一部として行われるアクトは、任意の適宜のやり方で、順序付けが行われてもよい。従って、アクトが、図示されたものとは異なる順序で（これは、説明のための実施形態では、逐次的なアクトとして示されたとしても、幾つかのアクトを同時に行うことを包含してもよい）行われる実施形態が構築されてもよい。
【０１３３】
さらに、幾つかの行為は、「ユーザ」によって行われると記載される。「ユーザ」は、一人の個人である必要はなく、及び幾つかの実施形態では、「ユーザ」に帰する行為は、複数の個人から成るチーム及び／又はコンピュータ支援ツール又は他の機構と組み合わせた個人によって行われてもよいことが理解されるものとする。
【０１３４】
クレーム要素を修飾する、クレームにおける「第１の」、「第２の」、「第３の」などの序数用語の使用は、それ自体は、１つのクレーム要素の別のクレーム要素に対する優先、先行、又は順序、又は方法のアクトが行われる時間的順序を暗示せず、ある名称を有する１つのクレーム要素を、同じ名称（序数用語の使用を除き）を有する別の要素と区別するための単なるラベルとして使用することにより、これらのクレーム要素が区別される。
【０１３５】
又、本明細書において使用される表現及び用語は、説明目的のものであり、及び限定として見なされるものではない。本明細書における、「包含する（ｉｎｃｌｕｄｉｎｇ）」、「含む（ｃｏｍｐｒｉｓｉｎｇ）」、又は「有する（ｈａｖｉｎｇ）」、「含有する（ｃｏｎｔａｉｎｉｎｇ）」、「関与する（ｉｎｖｏｌｖｉｎｇ）」、及びそれらのバリエーションの使用は、その後にリストされるアイテム及びそれらの均等物、並びに追加のアイテムを網羅することを意味する。
【図１Ａ】
2020512643.tif 000003
【図１Ｂ】
2020512643.tif 000004
【図１Ｃ】
2020512643.tif 000005
【図２】
2020512643.tif 000006
【図３Ａ−３Ｂ】
2020512643.tif 000007
【図３Ｃ−３Ｄ】
2020512643.tif 000008
【図４Ａ−４Ｂ】
2020512643.tif 000009
【図４Ｃ】
2020512643.tif 000010
【図５Ａ−Ｂ】
2020512643.tif 000011
【図５Ｃ−５Ｄ】
2020512643.tif 000012
【図６】
2020512643.tif 000013
【図７】
2020512643.tif 000014
【国際調査報告】
2020512643.tif 000015
2020512643.tif 000016