JP6598997B2 - データ準備のためのキャッシュ最適化 - Google Patents

Description

自動データ処理は、しばしば、データセットに実行される動作を伴う。通例、動作の実行は、データセット全体を取得することを必要とし、データセットは、結果を決定するために、その動作を通して保持される。数百万ないし数十億ものレコードを有しうる、大規模なウェブアプリケーションのためのデータセット全体の処理は、計算集約的でありえ、これは、遅いアプリケーション応答時間につながりうる。

以下の詳細な説明と添付の図面において、本発明の様々な実施形態を開示する。

いくつかの実施形態に従って、データ準備のためのキャッシュ最適化を実行するためにプログラムされたコンピュータシステムを示す機能図。

データ準備のためのシステムの一実施形態を示すシステム図。

パイプラインサーバの一実施形態を示すシステム図。

３部分の関数の実施形態の一例を示す図。

分割を行うための処理の実施形態の一例を示すフローチャート。

スクリプトの実施形態の一例を示す図。

処理されるデータセットの実施形態の一例を示す図。

インポート動作中に生成されたデータ構造の実施形態の一例を示す図。

データトラバーサルプログラムを実行する実施形態の一例を示す図。

更新されたデータトラバーサルプログラムの実施形態の一例を示す図。

データトラバーサルプログラムを実行する実施形態の一例を示す図。

フィルタ動作の結果を反映するようにデータトラバーサルプログラムを更新するための処理の一実施形態を示す図。

は データトラバーサルプログラムの実施形態の一例を示す図。

ソートされるデータセットの一実施形態を示す図。

データトラバーサルプログラムおよびファイルセットの一実施形態を示す図。

ソートされた結果の一例を示す図。

ソート動作を実行するための処理の一実施形態を示す図。

データトラバーサルプログラムの実施形態の一例を示す図。

ネイティブＳｐａｒｋソートの実施形態の一例を示す図。

付加動作を含むスクリプトの実施形態の一例を示す図。

付加されるデータセットの実施形態の一例を示す図。

２つの異なるデータセットのためのパイプラインに関連する論理ファイル／名前空間の実施形態の一例を示す図。

付加の前のデータトラバーサルプログラムの実施形態の一例を示す図。

付加の後のデータトラバーサルプログラムの実施形態の一例を示す図。

パーティションおよびデータトラバーサルプログラムの実施形態の一例を示す図。

付加の前のデータトラバーサルプログラムの実施形態の一例を示す図。

付加の後のデータトラバーサルプログラムの実施形態の一例を示す図。

データトラバーサルプログラムおよびファイルセットの実施形態の一例を示す図。

順序付けられた動作のセットのツリー表現の実施形態の一例を示す図。

順序付けられた動作のセットのツリー表現の実施形態の一例を示す図。

結合されるデータセットの一例を示す図。

インポートされたデータのために生成されたデータトラバーサルプログラムおよびファイルセットの一例を示す図。

結合を実行するための処理の実施形態の一例を示す図。 結合を実行するための処理の実施形態の一例を示す図。 結合を実行するための処理の実施形態の一例を示す図。

結合の前のデータトラバーサルプログラムの実施形態の一例を示す図。

結合の後のデータトラバーサルプログラムの実施形態の一例を示す図。

変換結果をキャッシュするための処理の一実施形態を示すフローチャート。

キャッシュ再利用のための処理の一実施形態を示すフローチャート。

ステップエディタのユーザインターフェースの実施形態の例を示す図。 ステップエディタのユーザインターフェースの実施形態の例を示す図。 ステップエディタのユーザインターフェースの実施形態の例を示す図。 ステップエディタのユーザインターフェースの実施形態の例を示す図。 ステップエディタのユーザインターフェースの実施形態の例を示す図。

データ準備にステップエディタを用いるための処理の一実施形態を示すフローチャート。

本発明は、処理、装置、システム、物質の組成、コンピュータ読み取り可能な格納媒体上に具現化されたコンピュータプログラム製品、および／または、プロセッサ（プロセッサに接続されたメモリに格納および／またはそのメモリによって提供される命令を実行するよう構成されたプロセッサ）を含め、様々な形態で実装されうる。本明細書では、これらの実装または本発明が取りうる任意の他の形態を、技術と呼ぶ。一般に、開示された処理の工程の順序は、本発明の範囲内で変更されてもよい。特に言及しない限り、タスクを実行するよう構成されるものとして記載されたプロセッサまたはメモリなどの構成要素は、ある時間にタスクを実行するよう一時的に構成された一般的な構成要素として、または、タスクを実行するよう製造された特定の構成要素として実装されてよい。本明細書では、「プロセッサ」という用語は、１または複数のデバイス、回路、および／または、コンピュータプログラム命令などのデータを処理するよう構成された処理コアを指すものとする。

以下では、本発明の原理を示す図面を参照しつつ、本発明の１または複数の実施形態の詳細な説明を行う。本発明は、かかる実施形態に関連して説明されているが、どの実施形態にも限定されない。本発明の範囲は、特許請求の範囲によってのみ限定されるものであり、本発明は、多くの代替物、変形物、および、等価物を含む。以下の説明では、本発明の完全な理解を提供するために、多くの具体的な詳細事項が記載されている。これらの詳細事項は、例示を目的としたものであり、本発明は、これらの具体的な詳細事項の一部または全てがなくとも特許請求の範囲に従って実施可能である。簡単のために、本発明に関連する技術分野で周知の技術事項については、本発明が必要以上にわかりにくくならないように、詳細には説明していない。

本明細書に記載の技術を用いると、順序付けされたデータ準備動作（すなわち、順番に適用される一連の動作）をデータセットに実行して変換結果を生成するために、Ａｐａｃｈｅ Ｓｐａｒｋ（商標）などの分散型コンピュータプラットフォームを効率的に利用できる。本明細書で用いられるように、データ準備動作とは、入力データを変換／変化させるために用いられる動作のことである。入力データは、順序付けされた動作のセットの実行時に動的にアクセス可能であり、ここで、データは、必ずしも格納されておらず、必要に応じてオンザフライで計算されてもよい。これは、固定された既知の位置に格納されたデータに対する動作と対照的であり、事前のインデックス化およびパーティショニングの利点なしに実行される。入力データは、（例えば、行および列に）構造化されたデータを含む。データ準備動作の様々な例は、クラスタリング、結合、付加、ソート、大文字化、小文字化、フィルタリング、重複排除、グループ分け、列の追加または除去、行の追加または除去、ピボッティング、デピボッティング、順序依存の動作などを含む。変換結果の表現は、本明細書では「データトラバーサルプログラム」と呼ばれており、これは、変換結果を引き出すために入力データ内の１または複数の影響を受けた列をどのように集めるのかを示す。変換結果の表現は、対応する動作シグネチャと共に再利用に向けて格納されることが可能であり、それによって、キャッシュされた結果が、再利用のために特定および取得されることが可能になる。

データ準備のためのキャッシュ最適化が開示されている。いくつかの実施形態において、１または複数セットのデータに実行された順序付けされたデータ準備動作のセットの結果を表すデータトラバーサルプログラムが生成される。データトラバーサルプログラムは、結果を引き出すために１または複数のデータセット内で１または複数の影響を受けた列をどのように集めるのかを示す。データトラバーサルプログラムは、参照および参照スタックを含んでおり、それらについては、後に詳述する。データトラバーサルプログラムが格納される。１または複数のデータセットに実行される順序付けられた動作のセットの仕様がその後に受信されると、データトラバーサルプログラムがリトリーブされる。１または複数のデータセット内の１または複数の影響を受けた列は、結果を生成するために、データトラバーサルプログラムに従って集められる。次いで、その結果は、例えば、グラフィカルユーザインターフェースで見られるように、または、ファイルに発行されるように、出力として提供されうる。

図１は、いくつかの実施形態に従って、データ準備のためのキャッシュ最適化を実行するためにプログラムされたコンピュータシステムを示す機能図である。明らかに、自動結合検出を実行するために、他のコンピュータシステムアーキテクチャおよび構成を用いることも可能である。以下に述べるような様々なサブシステムを備えるコンピュータシステム１００は、少なくとも１つのマイクロプロセッササブシステム（プロセッサまたは中央処理装置（ＣＰＵ）とも呼ばれる）１０２を備える。例えば、プロセッサ１０２は、シングルチッププロセッサまたはマルチプロセッサによって実装できる。いくつかの実施形態において、プロセッサ１０２は、コンピュータシステム１００の動作を制御する汎用デジタルプロセッサである。メモリ１１０から読み出された命令を用いて、プロセッサ１０２は、入力データの受信および操作、ならびに、出力デバイス（例えば、ディスプレイ１１８）上でのデータの出力および表示を制御する。いくいくつかの実施形態において、プロセッサ１０２は、図２のパイプラインサーバ２０６を含む、および／または、それらを提供するために用いられる、ならびに／もしくは、処理５００、１３００、１４００、および／または、１６００を実行／実施する。

プロセッサ１０２は、メモリ１１０と双方向的に接続されており、メモリ１１０は、第１のプライマリストレージ（通例は、ランダムアクセスメモリ（ＲＡＭ））および第２のプライマリストレージ領域（通例は、リードオンリーメモリ（ＲＯＭ））を含みうる。当業者に周知のように、プライマリストレージは、一般的な記憶領域として、および、スクラッチパッドメモリとして利用可能であり、また、入力データおよび処理済みデータを格納するために利用可能である。プライマリストレージは、さらに、プロセッサ１０２上で実行される処理のための他のデータおよび命令に加えて、データオブジェクトおよびテキストオブジェクトの形態で、プログラミング命令およびデータを格納できる。また、当業者に周知のように、プライマリストレージは、通例、機能（例えば、プログラムされた命令）を実行するためにプロセッサ１０２によって用いられる基本的な動作命令、プログラムコード、データ、および、オブジェクトを備える。例えば、メモリ１１０は、例えば、データアクセスが双方向である必要があるか、単方向である必要があるかに応じて、後述する任意の適切なコンピュータ読み取り可能な記憶媒体を含みうる。例えば、プロセッサ１０２は、頻繁に必要になるデータをキャッシュメモリ（図示せず）に直接的かつ非常に迅速に格納し取り出すことができる。

着脱可能マスストレージデバイス１１２が、コンピュータシステム１００にさらなるデータ記憶容量を提供しており、プロセッサ１０２に対して双方向（読み出し／書き込み）または単方向（読み出しのみ）に接続されている。例えば、ストレージ１１２は、磁気テープ、フラッシュメモリ、ＰＣカード、携帯型マスストレージデバイス、ホログラフィックストレージデバイス、および、その他のストレージデバイスなどのコンピュータ読み取り可能な媒体も含みうる。固定マスストレージ１２０も、例えば、さらなるデータ記憶容量を提供しうる。マスストレージ１２０の最も一般的な例は、ハードディスクドライブである。マスストレージ１１２、１２０は、一般に、プロセッサ１０２によって通例はあまり利用されないさらなるプログラミング命令、データなどを格納する。マスストレージ１１２および１２０に保持された情報は、必要であれば、仮想メモリとしてのメモリ１１０（例えば、ＲＡＭ）の一部に標準的な方式で組み込まれうることが理解される。

プロセッサ１０２にストレージサブシステムへのアクセスを提供することに加えて、バス１１４は、その他のサブシステムおよびデバイスへのアクセスを提供するために用いられてもよい。図に示すように、これらは、ディスプレイモニタ１１８、ネットワークインターフェース１１６、キーボード１０４、および、ポインティングデバイス１０６、ならびに、必要に応じて、補助入力／出力デバイスインターフェース、サウンドカード、スピーカ、および、その他のサブシステムを含みうる。例えば、ポインティングデバイス１０６は、マウス、スタイラス、トラックボール、または、タブレットであってよく、グラフィカルユーザインターフェースと相互作用するのに有用である。

ネットワークインターフェース１１６は、図に示すように、ネットワーク接続を用いて、別のコンピュータ、コンピュータネットワーク、または、遠隔通信ネットワークにプロセッサ１０２を接続することを可能にする。例えば、ネットワークインターフェース１１６を通して、プロセッサ１０２は、方法／処理ステップを実行する過程で、別のネットワークから情報（例えば、データオブジェクトまたはプログラム命令）を受信したり、別のネットワークに情報を出力したりすることができる。情報は、しばしば、プロセッサ上で実行される一連の命令として表され、別のネットワークから受信されたり、別のネットワークへ出力されたりしうる。インターフェースカード（または同様のデバイス）と、プロセッサ１０２によって実装（例えば、実行／実施）される適切なソフトウェアとを用いて、コンピュータシステム１００を外部ネットワークに接続し、標準プロトコルに従ってデータを転送することができる。例えば、本明細書に開示された様々な処理の実施形態は、プロセッサ１０２上で実行されてもよいし、処理の一部を共有するリモートプロセッサと共に、ネットワーク（インターネット、イントラネットワーク、または、ローカルエリアネットワークなど）上で実行されてもよい。さらなるマスストレージデバイス（図示せず）が、ネットワークインターフェース１１６を通してプロセッサ１０２に接続されてもよい。

補助Ｉ／Ｏデバイスインターフェース（図示せず）が、コンピュータシステム１００と共に用いられてよい。補助Ｉ／Ｏデバイスインターフェースは、プロセッサ１０２がデータを送信すること、ならびに、より典型的には、他のデバイス（マイクロフォン、タッチセンサ方式ディスプレイ、トランスデューサカードリーダ、テープリーダ、音声または手書き認識装置、バイオメトリクスリーダ、カメラ、携帯型マスストレージデバイス、および、他のコンピュータなど）からデータを受信することを可能にする汎用インターフェースおよびカスタマイズされたインターフェースを含みうる。

さらに、本明細書に開示された様々な実施形態は、さらに、様々なコンピュータ実装された動作を実行するためのプログラムコードを備えたコンピュータ読み取り可能な媒体を含むコンピュータストレージ製品に関する。コンピュータ読み取り可能な媒体は、データを格納できる任意のデータストレージデバイスであり、そのデータは、後にコンピュータシステムによって読み出されうる。コンピュータ読み取り可能な媒体の例は、上記の媒体すべてを含むがそれらに限定されない：ハードディスク、フロッピーディスク、および、磁気テープなどの磁気媒体；ＣＤ−ＲＯＭディスクなどの光学媒体；光学ディスクなどの磁気光学媒体；ならびに、特定用途向け集積回路（ＡＳＩＣ）、プログラム可能論理デバイス（ＰＬＤ）、および、ＲＯＭ／ＲＡＭデバイスなど、特別に構成されたハードウェアデバイス。プログラムコードの例としては、例えば、コンパイラによって生成されるマシンコード、または、インタープリタを用いて実行できる高水準コード（例えば、スクリプト）を含むファイルが挙げられる。

図１に示すコンピュータシステムは、本明細書に開示された様々な実施形態と共に利用するのに適切なコンピュータシステムの一例にすぎない。かかる利用に適した他のコンピュータシステムは、より多いまたは少ないサブシステムを含みうる。さらに、バス１１４は、サブシステムをつなぐよう機能する任意の相互接続スキームの例である。異なる構成のサブシステムを有する他のコンピュータアーキテクチャが利用されてもよい。

図２は、データ準備のためのシステムの一実施形態を示すシステム図である。システムは、フロントエンド２００およびパイプラインサーバ２０６を備える。

フロントエンド２００は、データ準備を設定するためのインターフェースを提供するよう構成されている。フロントエンド２００は、パイプラインサーバ２０６と相互作用する。様々な実施形態において、フロントエンド２００は、クライアントデバイス上で動作し、Ｊ２ＥＥアプリケーションサーバ（ＴｏｍｃａｔまたはＪｅｔｔｙもしくはそれらの組みあわせなど）としてのパイプラインサーバと通信するスタンドアローンのアプリケーションおよび／またはブラウザベースのクライアントアプリケーションとして実装されうる。フロントエンド２００は、ユーザインターフェースエンジン２０２およびスクリプトジェネレータ２０４を備える。

ユーザインターフェースエンジン２０２は、テーブルデータ、構成オプション、順序付けられた動作の結果、および、任意のその他の適切な情報をユーザインターフェーススクリーンでユーザに提示するため、ならびに、ユーザインターフェース構成要素からユーザ入力を受信するために、パイプラインサーバ２０６と相互作用するよう構成されている。例えば、ユーザインターフェースエンジン２０２は、１または複数の変換結果を生成するために１または複数のデータセットに実行されるデータ準備動作セットをユーザが指定するためのエディタユーザインターフェースを提供するよう構成されている。指定された一連の順序付けられた動作（指定された順番に適用される）は、１または複数のデータセットが処理されるパイプラインを形成する。データセットは、行および列に構造化されたデータレコードを含むデータのテーブルを含む。ユーユーザインターフェースエンジン２０２によって提供されるユーザインターフェースの例については、図１５Ａ〜Ｅを参照して説明する。

スクリプトジェネレータ２０４は、ユーザインターフェースエンジン２０２によって提供される１以上のユーザインターフェースを用いてユーザによって指定されたデータセットおよび一連の動作に基づいて、スクリプトを生成するよう構成されている。スクリプトは、処理を受ける１または複数のデータセットならびに１または複数のデータセットに実行されるよう指定された順序付けられた動作のセットの仕様を含むフォーマットされた命令のセットを含む。いくつかの実施形態において、スクリプト内で指定されたパイプラインは、アプリケーションと呼ばれる。スクリプトジェネレータ２０４を用いて生成されたスクリプトの一例について、図６Ａを参照して説明する。

パイプラインサーバ２０６は、データ準備を実行するよう構成されている。いくつかの実施形態において、パイプラインサーバは、スクリプトジェネレータ２０４からスクリプトを受信し、そのスクリプトに従って１または複数の入力データセット（例えば、データセット２１４）に、（パイプラインを形成する）順序付けられたデータ準備動作のセットを実行する。データセットは、メモリ（例えば、ランダムアクセスメモリ）に格納されるか、ストレージ（例えば、ローカルディスク、ネットワークストレージ、分散型ストレージサーバなど）から読み出しまたはストリーミングされるか、もしくは、任意の他の適切なソースから取得されてよい。パイプラインサーバ２０６は、ネットワークベース／クラウドベース環境内の１または複数のサーバ、クライアントデバイス（例えば、コンピュータ、スマートフォン、ウェアラブルデバイス、または、通信機能を備えたその他の適切なデバイス）、もしくは、それらの組みあわせ上に実装されてよい。いくつかの実施形態において、パイプラインサーバは、アプリケーションとして配備される。パイプラインサーバは、システム（１００など）を用いて実装されうる。いくつかの実施形態において、パイプラインサーバは、Ａｐａｃｈｅ Ｓｐａｒｋ（商標）などの分散型コンピュータプラットフォームを用いて実装される。Ａｐａｃｈｅ Ｓｐａｒｋ（商標）を含む実施形態の例を以下に記載するが、本明細書に記載の技術を適切に適合させて、任意のその他の分散型コンピュータプラットフォーム／アーキテクチャを利用することができる。パイプラインサーバ２０６は、データ分割エンジン２０８、データ変換エンジン２１０、および、キャッシュエンジン２１２を備える。

データ分割エンジン２０８は、入力データセット（例えば、データセット２１４）を分割して、分散型コンピュータ環境内の処理ノードクラスタにそれらを分配するよう構成されている。いくつかの実施形態において、データ分割エンジンは、Ａｐａｃｈｅ Ｓｐａｒｋ（商標）などの分散型コンピュータプラットフォームに提供できる形態に変換できるように、入力データを事前処理するよう構成されている。データセット内のデータの分配を決定することは、取得されたデータセットが、どのように論理パーティション／作業部分に分割／パーティショニングされるべきかを決定することを含み、いくつのパーティションが生成されるべきか、および、各パーティションを割り当てる負荷を決定することを含む。いくつかの実施形態において、パーティション決定は、様々なコスト関数に基づいている。データ分割エンジンの動作については、後に詳述する。

データ変換エンジン２１０は、データ準備を実行するよう構成されている。データ準備を実行することは、１または複数のデータセットに順序付けられたデータ準備動作のセットを実行することによって、変換結果を決定することを含む。いくつかの実施形態において、データ変換エンジンは、列データ変換エンジンである。いくつかの実施形態において、データ変換エンジンは、さらに、再利用に向けて、結果のキャッシングと、既存のキャッシュされた結果のルックアップとを実行するよう構成される。

以下に述べるように、データ変換エンジンは、１または複数のデータセットに対する順序付けられた動作のセットの変換結果のコンパクト表現（本明細書では「データトラバーサルプログラム」と呼ぶ）を生成することによって、順序付けられたデータ準備動作を効率的に実行するよう構成される。データトラバーサルプログラムは、列ファイルと共に用いられた時に、変換結果を引き出すために処理を受けた１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示す参照および参照スタックを含む。データ変換エンジンの動作については、後に詳述する。

キャッシュエンジン２１２は、キャッシングおよびキャッシュ識別を実行するよう構成されている。例えば、データ変換エンジン２１０を用いて決定されたデータトラバーサルプログラム／結果の表現は、再利用に向けて様々な時点（例えば、特定の一部の順序付けされたデータ準備動作の後）にキャッシュされうる。キャッシングされているデータは、例えばメモリ（例えば、ランダムアクセスメモリ）内のキャッシュ層、ローカルストレージデバイスまたはネットワークストレージデバイス（例えば、ディスクまたはストレージサーバ）、および／または、任意の他の適切なデバイスに格納されうる。結果は、例えば、ユーザからの（例えば、ユーザインターフェースエンジン２０２によって提供されたステップエディタユーザインターフェースとの相互作用による）明示的な要求に基づいてキャッシュされうる。結果は、例えば、結果に到達するために実行された動作の複雑性などの要因に基づいて、自動的にキャッシュされてもよい。キャッシュされた表現は、対応するシグネチャに基づいて識別されうる。例えば、キャッシュエンジンは、（例えば、ユーザインターフェースエンジンによって提供されたステップエディタユーザインターフェースを介してユーザ入力から生成されたスクリプト内で受信された）順序付けられた動作のセットを入力として、動作シグネチャを導出し、既存のキャッシュされた結果に関連するシグネチャとそれを比較することができる。キャッシュエンジンの動作については、後に詳述する。

図３は、パイプラインサーバの一実施形態を示すシステム図である。いくつかの実施形態において、パイプラインサーバ３００は、図２のパイプラインサーバ２０６の一例である。この例において、パイプラインサーバ３００は、分散型コンピュータプラットフォームを用いて実装される。いくつかの実施形態において、パイプラインサーバ３００の分散型コンピュータプラットフォームは、図２のデータ分割エンジン２０８、データ変換エンジン２１０、および、キャッシュエンジン２１２を実装するために用いられる。

パイプラインサーバ３００内に示されているのは、Ｓｐａｒｋクラスタの実施形態の一例である。クラスタは、Ｓｐａｒｋマスタ（３０２）およびＳｐａｒｋワーカ（３０４および３１２）を備える。いくつかの実施形態において、Ｓｐａｒｋクラスタは、マスタスレーブアーキテクチャを用いて実装される。いくつかの実施形態において、Ｓｐａｒｋマスタは、（おそらく分散的に）実行されるすべての作業を調整するよう構成されている。いくつかの実施形態において、Ｓｐａｒｋワーカは、実行すべき動作に関する命令と共に或るデータを指す複数の作業を受信して実行する責任がある。Ｓｐａｒｋマスタおよびワーカは、例えば、Ｊａｖａ（登録商標）アプリケーションとして実装できる。

いくつかの実施形態において、Ｓｐａｒｋマスタは、外部クライアントから要求（例えば、ジョブ）を受信するよう構成されている。Ｓｐａｒｋマスタは、より小さいチャンク（作業部分）にジョブを分解し、様々なＳｐａｒｋワーカに作業を分散させるよう構成される。Ｓｐａｒｋワーカは、自身の作業の部分を完了させると、Ｓｐａｒｋマスタに結果を返す。ワーカすべてがそれぞれの結果を返すと、Ｓｐａｒｋマスタは、ワーカの結果すべてをコンパイルし、要求側クライアントに最終結果を返す。

いくつかの実施形態において、スタンドアローンモードで動作する場合、Ｓｐａｒｋマスタは、ワーカの健全性／状態を追跡して作業スケジュールを管理するよう構成される。

いくつかの実施形態において、Ｓｐａｒｋマスタおよびワーカの両方は、コンパニオンアプリケーション（例えば、専用のＳｐａｒｋアプリケーション）を用いて、実際の作業を実行する。いくつかの実施形態において、コンパニオンアプリケーションは、Ｓｐａｒｋプロセスを実行する全マシン（マスタおよびワーカの両方）上で動作する。ワーカマシン上で動作するコンパニオンアプリケーション（本明細書では「パイプライン」アプリケーションとも呼ぶ）のランタイムインスタンスを、本明細書ではＳｐａｒｋ「パイプラインエグゼキュータ」と呼ぶ。Ｓｐａｒｋワーカは、エグゼキュータアプリケーションを通してそのジョブを実行するよう構成される。

この例では、２つのＳｐａｒｋワーカが図示されているが、任意の数のＳｐａｒｋワーカが、クラスタ内に確立されてよい。いくつかの実施形態では、アプリケーション（例えば、フロントエンド２００などのフロントエンドによって開始されたデータ準備アプリケーション）が、データセットが通されるパイプラインを含む順序付けられた動作のセットを実行するために、ノードのクラスタを準備する。いくつかの実施形態において、各Ｓｐａｒｋマスタまたはワーカは、様々な実施形態において、デバイス、プロセッサ、サーバなどとして実装された、物理コンピュータまたは仮想コンピュータのいずれかを備えたノードである。

この例において、Ｓｐａｒｋマスタは、「パイプラインマスタ」（３０８）と通信するよう指定され、Ｓｐａｒｋワーカは、パイプラインエグゼキュータ（３１０および３０６）と通信するよう指定される。パイプラインマスタ／エグゼキュータは、対応するノード上にあるＳｐａｒｋソフトウェアと接続する。

上述のように、パイプラインサーバは、１または複数の入力データセットと、入力データセットが処理されるパイプラインを形成する順序付けられたデータ準備動作のセットとを指定するスクリプトを受信する。パイプラインサーバは、分散型コンピュータプラットフォームを用いて、受信したスクリプトに従って入力データを処理する。

データ分割
この例において、パイプラインマスタは、入力データセットの分割を実行するよう構成される。いくつかの実施形態において、パイプラインマスタは、図２のデータ分割エンジン２０８を実装するために用いられる。分割は、データセットをより小さいチャンクに分割すること（例えば、１００行のデータセットをそれぞれが２０行を含む５つのパーティションに分割すること）を含む。いくつかの実施形態において、データのセットは、複数の作業部分、すなわち、実行される複数の作業に分割される。パイプラインマスタは、さらに、処理に向けて準備されたクラスタ内の様々な確立したパイプラインエグゼキュータにパーティションを分散させるよう構成される。Ｓｐａｒｋ実装例において、データセットの区分／パーティション（「作業の部分」または「作業部分」とも呼ぶ）は、耐障害性分散データセット（ＲＤＤ：Ｒｅｓｉｌｉｅｎｔ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａｓｅｔ）として表現される。他の分散型プラットフォーム実装例については、他のパーティションフォーマットも可能である。

データの分割時、いくつのパーティションを生成すべきか、および／または、各パーティションに何行／どれだけを含めるのか、を決定する際に、様々なトレードオフが存在する。例えば、データのスライス数の増加は、並列性および計算速度の増大につながりうるが、パーティションの数の増加は、ますます多くのノード間でデータが通信される必要があることから、オーバーヘッドの増大および通信帯域要件の増加にもつながる。これにより、非効率になりうる。本明細書に記載の技術を用いれば、分割を最適化できる。例えば、パーティションの最適数および／またはパーティション当たりの行の最適サイズ／数を決定できる。

マスタノードは、様々な情報を考慮することによって、データセットを分割するためのインテリジェントな戦略を考案または利用するよう構成される。様々な実施形態において、考慮される情報は、処理を受けるデータ、実行されるデータ準備動作、分散型コンピュータ環境のトポロジ／パフォーマンス特性などに関する情報を含む。かかる情報を考慮することにより、ノードがほぼ同時に処理を完了できるように、例えば、クラスタのノード全体にわたる信頼性の高いスループットのために、最適化を行う分割戦略が考案されうる。したがって、（例えば、いくつかのワーカが、その他のワーカと比較して、自身の作業の部分を実行するのにより多くの時間を費やしており、それを待つ必要がある場合に）、例えば、分散型計算環境における遅れを低減できる。

処理を受けるデータに関する情報は、そのデータに関するメタデータ情報を含む。実施形態の一例において、Ｓｐａｒｋ（パイプライン）マスタは、（例えば、受信したスクリプトに記載されたソース位置から取得した）入力データセットをクエリする。パイプラインマスタは、データセットを記述するメタデータを決定するために、データセットを調べる。様々な実施形態において、メタデータは、データセット内にある行の数、データセット内にある列の数などを含む。いくつかの実施形態において、決定／生成されたメタデータは、データがデータセット内でどのように分布するかに関するヒストグラム情報など、統計情報を含む。例えば、データセット内のいくつかの行が他の行よりも密度が高いと決定されうる。分析（例えば、統計分析）の結果として決定されたメタデータは、インテリジェントな分割戦略を考案するために、パイプラインマスタによって部分的に用いられる。

分割戦略の実施形態の例について、以下に記載する。

戦略例１：行カウントに基づく分割
この戦略例において、データセットは、このコンテクストフリーなアプローチ（例えば、行に関するメタデータ情報も他の情報も利用されない）において、各Ｓｐａｒｋワーカ／パイプラインエグゼキュータが、固定された（例えば、同じ）数の行を与えられるように、行カウントに基づいて分割される。いくつかの実施形態では、各行を処理するのに同じ量のリソースおよび時間を要すると仮定される。

戦略例２：行のサイズ／データの量に基づく分割
この戦略例において、データセットは、データセット内の行のサイズに部分的に基づいて分割される。データセットの行におけるデータの密度および／または量（例えば、データの量は、行ごとに変化しうる）を決定するために、統計分析がデータに実行される。例えば、行が必要とする空間の量を示すメタデータが決定される。データセットは、各パーティションが同じ量のデータを含む（ただし、様々な数の行を含んでよい）ように分割される。

いくつかの実施形態において、行の数は、行のサイズに加えて、二次的な基準として用いられる。例えば、所与の量のデータサイズを有する行の数が、パーティションに対して決定される。行の数が閾値行数を超えた場合（または、平均行数からの閾値逸脱数よりも大きい場合）、パーティション内の行の数は、削減され、閾値を上限とされる。例えば、各パーティションは、１００ＭＢのデータまたは２００，０００行、いずれか行数が少ない方を割り当てられる。

二次的な基準としての行数の利用は、データ変換の列の性質に部分的に基づいており、ここで、データは、１または複数の特定の列に関して実行されたデータ準備動作に基づいて変換され、動作を実行するのに必要な計算量を決定するデータ準備動作の影響を受けるのはそれらの列である。しかしながら、１つの行が、データセットのすべての列内のデータセルを含み、行のサイズは、動作のコストに実質的に寄与しない列にあるデータセルに凝縮されてよい。二次的な基準として行数を用いることにより、サイズの点で外れ値の分布を有する列を削除できる（最も一般的なデータ準備が、分布内で極めて均一であるデータに作用していると仮定する）。これは、分散型計算システムにおいて最終的にどれだけのデータが処理されるのかについて、リミッタを提供する。

いくつかの実施形態において、パーティション当たりの行の上限／最大数は、データセット全体の総行数の関数として決定される。３部分の関数の一実施形態を示すプロットの一例を図４に示す。図に示された線分の傾きおよび遷移点は、経験的に決定されており、異なる実施形態において様々であってよい。この例で、行数が範囲４０２に収まるデータセットについては、パーティションに、データセットの総行数の内の比較的大きい割合が備えられる。例えば、非常に小さいデータセットについては、単一のパーティションに、全データが詰め込まれる。そうすることにより、データをパーティションにわたって（潜在的に、異なるノードに）分散させる必要はなく、リソースオーバーヘッドが低減される。したがって、この第１領域４０２では、小さい入力データセットについて、データセットをより少ないパーティションに分割した方が効率的である。換言すると、分割技術は、より多くの行を単一のパーティションに入れようとする。

範囲４０４の総行数を持つデータセットについては、総行数が増加する（ここで、各パーティションのサイズは、徐々に大きくなる）につれて、新たなパーティションが徐々に追加される。範囲４０２と比較して、範囲４０４では、行がパーティションに追加される速度は遅い。例えば、この範囲では、新たなパーティションを追加する方が、それらのパーティションに行を追加するよりも好ましい。行がまだ徐々にパーティションに追加されている間（これは、ノード上のいくつかのパーティションの性能を犠牲にしうる（ノードがより多い行データを処理しなければいけなくなるため））、それらのパーティションは、処理されるパーティションの数が多くなりすぎないような速度で追加される。

総行数が閾値４０６を超えるデータセットについては、１つのパーティションに含まれうる行の数は、凍結されて増加せず、ここで、さらなるパーティションの追加が好ましい。したがって、単一のパーティションに含まれうる行の数に関する上限が確立され、各パーティションが比較的一定した時間で限界（上限）量のデータを処理できるのを知ることが可能になる。

戦略例３：行のアクティブ部分のサイズに基づく分割

この戦略では、戦略２と同様に、パーティションに含めるデータの量が考慮される。ただし、動作（または、順序付けられた動作のセット）に関与する（または、動作の影響を受ける）（すなわち、アクティブである）列内のデータのみが考慮される。例えば、４つのすべての列の内、それらの列の３つのみが、データ準備動作（例えば、これらの３つの列を用いる結合動作）に関与する場合、それら３つの列内のデータのみが決定される。次いで、データセットは、アクティブな列内のデータ量に従って（例えば、戦略２で上述したように）分割される。いくつかの実施形態では、行のアクティブ部分の中のデータの密度が、分割を決定するための別の要素として用いられる。

いくつかの実施形態において、戦略２および３はコンテクストを意識しており、処理されるデータセットの属性および特性を考慮に入れている（例えば、データセットの行に関して決定されたメタデータ情報）。いくつかの実施形態において、コンテクストを意識した戦略は、パーティションが必要とするメモリ量およびパーティションに作用するパイプラインエグゼキュータが対応できるメモリ量など、クラスタの物理特性も考慮に入れる。例えば、パーティションに存在しうるデータの量（メモリサイズ）は、エグゼキュータが利用するために割り当てられるメモリを超えないように設定されうる。考慮されるクラスタのその他の物理特性は、後に詳述するように、処理能力の量、ネットワーク帯域幅メトリクスなど、パフォーマンスメトリクスを含む。

クラスタ内のノードは、様々なパフォーマンス特性を持つ物理マシンであってよい。例えば、クラスタが２つの計算ノードを備えると仮定する。第１ノードは、コア当たり１０ＧＢのメモリで、８のプロセッサコアを有しており（すなわち、合計で８０ＧＢのメモリ）、一方、第２ノードは、コア当たり１０ＧＢのメモリで、１６のプロセッサコアを有する（すなわち、合計で１６０ＧＢのメモリ）。ノードのこれらのメモリ／処理特性に基づくと共に、ワーカがプロセッサコア当たり１０ＧＢを割り当てられるというヒューリスティックを用いると、３の倍数であるワーカ数が、２つのノードにわたって作業を実行することが好ましい。これは、第１ノードが総メモリの１／３を有し、第２ノードが総メモリの２／３を有する（すなわち、２つのノードのメモリの比が１：２である）ことで、３の倍数であるワーカ数を有することが、クラスタ内の総メモリ量が完全に利用されることを保証するからである。

しかしながら、クラスタのノードがパフォーマンス特性において様々でありえ、クラスタ構造が変化しうることを考慮すると、いくつかの実施形態において、パーティションの作成は、クラスタの実際の処理能力の明確な知識なしに行われる。むしろ、各パーティションは、コア当たりのメモリ量（例えば、１０ＧＢ）など、予め指定された計算リソース量を割り当てられる。次いで、データセットは、パフォーマンスヒューリスティック／特性に従って（例えば、１０ＧＢの倍数であるチャンクに）分割される。したがって、例えば、パーティションがコア当たり最大１０ＧＢのメモリを割り当てられる場合、８コアにわたって８０ＧＢの総メモリを備えた第１ノードは、８パーティション／ワーカをサポートできる（ここで、１パーティションが１ワーカに対応する）。この例において、コア当たりのＲＡＭ量のプロパティは、タスクに適用できる原理／ヒューリスティックまで還元されている（クラスタの実際のハードウェアの明確な知識なしに）。

いくつかの実施形態において、パーティションが、１つのワーカによって処理され、パーティション／ワーカに割り当てられうるリソースの量は、パーティションに作用しうるワーカユニットのパフォーマンス特性を規定するアトミック計算単位で具現化される。アトミック計算単位は、ワーカ／パイプラインエグゼキュータがパーティションを処理するために有するリソースの量を示す値を持つパフォーマンスメトリクスのセットに関連する。コア当たりのメモリ量に加えて、上述のように、このより高いレベルの形態に還元されうる他の特性は、ネットワーク帯域幅、待ち時間、および、コアパフォーマンスを含む。（パーティションに作用する）単一のワーカユニットに利用可能なリソース量のより高いレベルの視点を定義することにより、パーティション（およびさらなるワーカユニット）を追加するためのリソースのコストを決定することができる。例えば、コスト関数が、パフォーマンス特性／ヒューリスティックのセットを仮定して、結果を計算するコストを決定するために利用されうる。いくつかの実施形態において、（例えば、ワーカが、データのいくらかの行数／量を処理するための）コストの単位が、計算される。次いで、データは、データを処理するのに必要なワーカの数を決定するために、計算されたコストの単位に基づいて分割される。

したがって、アトミックワーカユニットのパフォーマンス特性のより高いレベルの視点を用いて、データセットに働きかけるのに必要なワーカの数を決定することができる（すなわち、データが分割されるべき作業／パーティションの数）。さらに、作成するパーティション／作業の数、対、パーティションに追加する行の数が、計算コストに基づいて評価されうる。

いくつかの実施形態において、データセットを分割する方法の決定は、実行される動作の特性に基づく。例えば、異なるタイプの動作は、異なる計算コストを有することになる。一例として、単一の入力を取り込み、その入力（大文字化動作など）のみに基づいて出力を提供する関数が、一定のコストを有する。互いに通信するためにパーティションを必要としうる他のタイプの動作（ソートなど）は、より大きいコストを有しうる（例えば、ソートについては、ｌｏｇｎ／パーティション数のオーダー）。次いで、データセットは、受信されたスクリプト内で指定された動作を実行するためのコストに部分的に基づいて分割されうる。

上述の戦略および技術の任意の組みあわせが、コスト関数に従ってデータセットを分割するための戦略を決定するために用いられてよい。いくつかの実施形態において、パーティションは、隣接しており、重複していない。一例として、０から１９９までインデックス付けされた２００行のデータセットが、（例えば、上述の戦略１を用いて）４つの論理パーティションに均等に分割されると仮定する。第１パーティションは、行０〜４９を有し、第２パーティションは、行５０〜９９を有し、第３パーティションは、行１００〜１４９を含み、第４パーティションは、行１５０〜１９９を含む。いくつかの実施形態において、パーティションは、パーティションＮ＋１から取得／読み出しされた行が、パーティションＮから取得／読み出しされた行に続くように、同様に順序付けされる。したがって、データセットは、順番に各パーティションを読み出すことによって、行順で読み出されうる。次いで、パーティションは、分散型コンピュータ配備アーキテクチャ内のパイプラインエグゼキュータ／Ｓｐａｒｋワーカに分散される。例えば、Ｓｐａｒｋスケジューラが、パーティション／作業が割り当てられて処理される場所（例えば、ノード）を決定する。

図５は、分割を行うための処理の実施形態の一例を示すフローチャートである。いくつかの実施形態において、処理５００は、図２のデータ分割エンジン２０８によって実行される。処理は、構造化されたデータのセットに実行される順序付けされた動作のセットの仕様が受信される工程５０２で始まる。いくつかの実施形態において、順序付けられた動作は、データ準備動作を含む。一例として、データのセットは、行および列もしくは任意のその他の適切な次元に構造化されうる。構造化されたデータのセットに実行される順序付けられた動作のセットの仕様は、上述のように、スクリプトの形態で受信されうる（例えば、ステップエディタユーザインターフェースを用いてユーザ入力に基づいて生成されたスクリプト、ファイルからインポートされたスクリプト、など）。

工程５０４で、データセットは、データセットの少なくとも１つの次元に依存するコスト関数に基づいて、複数の作業部分に分割される。いくつかの実施形態において、データセットは、作業部分に含める行の数を考慮するコスト関数に基づいて分割される。コスト関数は、処理されるデータの量、さらなる作業部分／パーティションを作成する計算コスト、行をパーティション／作業部分に追加するコスト、実行される動作の計算コストなど、様々な要素を考慮に入れることができる。データセットを複数の作業部分／パーティションに分割するための技術および戦略の例については、上述している。複数のデータセットが仕様内で指定されている場合、それらのデータセットは、独自のそれぞれのネームスペース内の論理パーティションに分割されうる。

工程５０６で、複数の作業部分は、動作の仕様に従って処理されるように、複数の処理ノードに分散される。例えば、スケジューラ（例えば、Ｓｐａｒｋスケジューラ）が、決定された作業部分を分散型コンピュータクラスタ内の処理ノードに分散させる。いくつかの実施形態において、決定された作業部分は、或る入力データに実行される依存動作のツリー構造の記述を用いて処理ノードに送信される。依存動作の一例は以下の通りである。列Ａ、Ｂ、および、Ｃのキャッシュに依存する列Ｂへの変更に依存する列Ａへの変更を行う。

分散型パイプライン最適化のための上述の戦略および技術は、様々な利点を提供する。例えば、上述のように、データセットは、データ自体の特性（例えば、行内のデータ量、行内のアクティブな列など）を考慮に入れるインテリジェントな方法で、ワーカに分散されうる。これは、ワーカが、例えば、同等の量のデータを処理することを可能にして、遅延したワーカ（例えば、自身の作業部分を計算するのにより長い時間が掛かっているワーカ）を待つのに必要な時間を削減する。別の例として、クラスタの物理特性を考慮することにより、クラスタのリソースを効率的に利用する作業部分を生成できる。別の例として、上述の戦略を用いれば、さらなるオーバーヘッドを最小化し、並列性を最大化するように、作業部分の最適数および／または作業部分に含めるデータの行数／量を決定することができる。したがって、分散型計算が、より効率的かつ予想通りに実行されうる。

データ変換およびキャッシュ最適化
入力データセットが分割および分散されると、順序付けられたデータ準備動作のセットが、受信されたスクリプトの仕様に従ってデータセットに適用されうる。例えば、１または複数の入力データセットを分割して、分散型コンピュータクラスタ内のワーカ／ノードにそれらを分散させた、パイプラインマスタ３０８は、パイプラインエグゼキュータと協調して、変換結果を決定するよう構成される。いくつかの実施形態において、パーティション／作業部分に作用する各パイプラインエグゼキュータは、順序付けられた動作のセットを実行した全体結果の一部を提供するよう構成される。パイプラインマスタは、結果の部分を全体結果に並べる／結合する責任を有する。いくつかの実施形態において、クラスタのパイプラインマスタは、図２のデータ変換エンジン２１０およびキャッシュエンジン２１２を実装するために用いられる。

一部の例では、Ｓｐａｒｋなどの分散型コンピュータプラットフォームが、様々な動作を実行するためのネイティブ機能を備えている。しかしながら、これらのプラットフォームが動作を実行する方法は、通例、データが複製されることを必要とし、これは、リソース集約的かつ非効率でありうる。

本明細書に記載の技術を用いると、パイプラインの各ステージでデータを複製することなしに、順序付けられた動作のセットを実行することが可能であり、それにより、順序付けられた動作のセットを実行して、データ変換結果を取得する速度および効率を高めることができる。Ｓｐａｒｋなどのプラットフォームが、本明細書に記載の技術と対照的に、動作の実行時にデータをどのように複製するのかを示す一例が、図１０Ａ〜１０Ｆを参照して後述するソート動作に関して示される。

後に詳述するように、データがパイプラインを通して処理される時に、列ファイルおよびデータトラバーサルプログラムを含むデータフラグメントが生成されうる。データフラグメントは、パイプラインの様々なステージでの累積結果（例えば、順序付けられたデータ準備動作の一部を実行した結果）を表すために用いられる。変換結果を表すフラグメントは、再利用に向けてパイプラインの様々なステージにキャッシュされうる。例えば、処理を受けた所与の作業について、パイプラインの特定のステージまでのその作業に対する動作の累積結果（または結果の表現）が、ディスクに保存されるかまたはキャッシュ層に格納されうる。キャッシュされた表現は、動作のセットにおける特定のステージでのデータの状態を再構築するために後に利用されうる。データフラグメント／表現は、パイプラインの終わりだけでなく、中間でもキャッシュされうる。これは、パイプラインの様々なステージでの中間結果を見ることを可能にする。さらに、（例えば、図２のユーザインターフェースエンジン２０２によって提供されたエディタインターフェースを用いる）スクリプト内に定義された順序付けられたデータ準備動作のセットの編集が、キャッシュされた結果につながる順序付けられたステップのセットの再計算を実行する必要なしに、同じキャッシュされた結果を再利用できる。例えば、いくつかの実施形態において、キャッシュされた表現は、キャッシュされた表現によって表された結果につながる順序付けられた動作のセットの記述（例えば、文字列記述）の関数（例えば、ＳＨＡハッシュ関数などのハッシュ関数）であるシグネチャを用いて識別される。新しいデータ準備スクリプトが受信されると（例えば、ユーザがエディタインターフェースを介してデータ準備を構成すると）、シグネチャが、新しいスクリプトの動作から生成され、利用できる既存のキャッシュされた表現があるか否かを判定するために利用されうる。

いくつかの実施形態において、本明細書に記載のキャッシュされた表現は、列の作業負荷に対して最適化される。列の作業負荷は、列データ変換を実行するために用いられるデータ準備動作を含む。いくつかの実施形態において、キャッシュされた表現を生成するために用いられるデータフォーマットおよび構造は、例えば、必要最小限のデータが可能な限り迅速に処理されるようにパイプラインサーバを通るデータの流れを制限するために、速度および効率に対しても最適化される。

列の作業負荷を最適化されたキャッシュの（再）利用について、データトラバーサルプログラムの生成および再利用を含め、データ準備動作の様々な例を参照しつつ以下で説明する。いくつかのデータ準備動作の詳細の例が、例示目的で提供されるが、そのリストは、包括的ではなく、本明細書に記載の技術は、必要に応じて任意の他のデータ準備動作に合わせて適切に適合されうる。

データ準備動作の例
ユーザが、（例えば、図２のフロントエンド２００のユーザインターフェースエンジン２０２によって提供された）ユーザインターフェースを介して、データセットと、データセットに実行すべき順序付けられたデータ準備動作のセットとを指定し、結果として、図６Ａに示したスクリプトが、（例えば、図２のスクリプトジェネレータ２０４を用いて）生成されたと仮定する。スクリプトは、Ａｐａｃｈｅ Ｓｐａｒｋなどの分散型コンピュータプラットフォームを用いて実装されたパイプラインサーバ（例えば、図２のフロントエンド２００から図３のパイプラインサーバ３００）によって受信される。

図６Ａは、スクリプトの実施形態の一例を示す。図に示すように、スクリプト６００は、６０２で処理を受ける（そして、インポートされる）データセット（この例では、「ＤＳ１」と呼ぶ）の記述である。処理されるデータセットのコンテンツは、図６Ｂで示される。スクリプトは、さらに、データセットに実行すべき順序付けられた動作のセットを含む。この例において、順序付けられた動作のセットは、データセットの列Ａへの大文字化動作（６０４）と、値「ｅ」および「ｈ」に関するデータセットの列Ｂへのフィルタ動作（６０６）と、を含む。順序付けられた動作のセットは、データセットが処理されるパイプラインを形成する。この例において、動作の論理的順序は、物理的実行順序でもあるが、そうである必要はない（例えば、物理的実行順序は、例えば、スマート最適化コンパイラの存在下では異なってもよい）。例えば、データ準備動作の順序は、その順に、連続した位置に２つの動作「ｆ」および「ｇ」を含む。スマートコンパイラは、「ｆ」の前に「ｇ」を実行することが正確に同じ結果を生み出しつつ、計算が速くなると判定しうる。例えば、スクリプト６００で指定された動作例において、最終結果は、大文字化ステップおよびフィルタステップを交換しても得られうる。そうすることにより、大文字化動作を実行される行がさらに少なくなり、計算の速度（および効率）が上がる。

この例に示すように、データ準備動作は、列の性質を持ち、ここで、データセットに実行される動作は、特定の列に関して定義される。例えば、大文字化動作は、データセットの列「Ａ」に実行され、フィルタ動作は、特定の列（列「Ｂ」）に見られる特定の値に基づいて実行される。かかるデータ準備動作について、データセット全体が変換される方法は、特定の列が動作によって影響される方法、または、動作において関係する特定の列の特性に基づいている。これは、後に詳述するように、データ準備動作のパフォーマンスの最適化および効率化のための技術を提供するために利用される。

６０８で、スクリプトは、データ準備動作の結果がどのように出力されるのかを示す。この例において、結果は、表示される（例えば、図２のユーザインターフェースエンジン２０２によって提供されたユーザインターフェースでユーザに提示される）。結果を出力するオプションの別の例は、結果を発行すること（例えば、別のファイルに結果をエクスポートすること）である。

図６Ｂは、処理されるデータセットの実施形態の一例を示す。この例において、データセット６５０は、図６Ａのスクリプト６００の６０２で指定されたデータセットに対応する。

スクリプト６００で定義された順序付けられた動作のセットによって形成されるパイプラインの各ステージで実行される処理について、以下に詳述する。例示の目的で、順序付けられた動作内の各ステップで書き込まれたファイルは、保存（キャッシュ）されるが、必ずしもその必要はない。

インポート／スタート
スクリプト６００の第１動作は、インポート／スタートである。行が分割および分散される方法に関する決定が（例えば、図２のデータ分割エンジン２０８によって）なされた後、様々なパーティションに割り当てられたデータがインポートされる。いくつかの実施形態において、データのインポートは、順番に高速でデータへアクセスすること（例えば、上から下まで高速でデータの列を読み出すこと）ができるようにデータを準備することを含む。

図７Ａは、インポート動作中に生成されたデータ構造の実施形態の一例を示す。いくつかの実施形態において、図７Ａの例は、図６Ｂの例から続く。いくつかの実施形態において、図７Ａでインポートされるデータは、図６Ｂのデータセット６５０（ＤＳ１）からのデータである。

この例では、ＤＳ１が２つの論理パーティション（すなわち、パーティション０（７０２）およびパーティション１（７０４））に分割されていると仮定する。それらのパーティションは各々、１または複数のワーカ（例えば、上述したＳｐａｒｋワーカ／パイプラインエグゼキュータ）によって処理される。上述のように、各パーティションは、ＤＳ１の行の一部を含み、２つのパーティションは、集合的に、データセット全体を含む。パーティションの間で、行の一部は、重複せず、隣接している。

作業（データ）が分割されており、ＤＳ１の各行は、座標のセットによって一意的に識別される。いくつかの実施形態において、座標は、その行が見つかりうるパーティションと、パーティション内のその行の識別子と、を示す。本明細書に記載の例において、座標は、以下のように構造化される：（パーティション番号，行識別子）。一意的な行識別子の一例が、参照テーブル７０６および７０８に示されており、それぞれ、パーティション０および１に対応する。

図に示すように、データセットＤＳ１は、２つのパーティションに均等に分割されており、データセットの上３行がパーティション０に割り当てられ、下３行がパーティション１に割り当てられている。

この例において、各パーティションは、列に対応するファイルのセット（７１０および７１２で示す）にデータを格納する。例えば、７１０では、データセットＤＳ１の列「Ａ」、「Ｂ」、および、「Ｃ」にそれぞれ対応する別個の列ファイルが書き込まれる（例えば、データセットＤＳ１のコンテンツは、（スクリプト内で指定された）それらのソースから取得され、列ファイルに再書き込みされる）。別個の各列は、パーティション内にあるＤＳ１の行すべてに対するセルを順に記述する。いくつかの実施形態において、書き込まれる列値は、（スクリプト内で指定された）入力データセットのソースから読み出され、元々のソースデータセットは修正されない（例えば、ソースデータセットの値は、列ファイルにコピーされる）。

列ファイル７１０および７１２には、それぞれ、ルックアップテーブル７１４および７１６が伴う。ルックアップテーブルの各行は、行識別子（「Ｒｏｗ＿ＩＤ」）を含んでおり、（識別された行のデータ値の位置を示す）列ファイルにインデックス化される。この例において、インデックス列に示されたインデックスは、それぞれの列ファイルへのバイトインデックスである。

ルックアップテーブルおよび列ファイルの構造は、例えば、データすべてが高速で列から読み出されうるように、順次アクセスについて最適化される。図に示した構造は、効率的な非順次の行プローブ（例えば、行のランダムアクセスプロービング）も可能にする。例えば、或る列の或る行における特定の値にアクセスするために、テーブルのルックアップが、対象の行および対象の列の行識別子を用いて実行されうる。その（行，列）座標に対応するインデックス値が、ルックアップテーブルから取得され、対応する列ファイルにアクセスするために用いられる。次いで、列ファイルのインデックスにおける値が、ロードおよび読み出しされる対象でないその他のデータを必要とせずに、直接リトリーブされうる。

この例において、列ファイル内の値は、順に格納され、バイト順にインデックス付けされる。それらの値は、異なるタイプ（例えば、文字型、整数型など）でありえ、異なるサイズ（例えば、バイト）でありうるので、ルックアップテーブル内のインデックスは、ファイル内でのその開始バイト位置によって列ファイル内のセルの位置を示す。例示の目的で、本明細書に記載のこの例およびその他の例の全体で、文字は１バイトのサイズを有すると仮定する。本明細書に記載の例に示された数値についても、例示の目的で、２バイトのサイズの整数であるとする。

インポート動作の一部として、パーティション１によって書き込まれた列「Ｃ」に対応する列ファイル（７１８）を例に取る。列ファイルは、値「ｃａｔｓ」、「ｎ」、および、「ｑ」を含む。列ファイルのための対応するバイトインデックスは、ルックアップテーブル７１６の７２０に示されている。値「ｃａｔｓ」に対する「Ｃ＿ｆｉｌｅ」内の開始バイトは、列ファイルに書き込まれた初期データ値であるため、０である。値「ｎ」に対する「Ｃ＿ｆｉｌｅ」内の開始バイトは、４である。これは、４文字を含む単語である値「ｃａｔｓ」が４バイトのサイズを有するからである。したがって、列ファイル７１８内のゼロ番目のバイトは、（パーティション１内の）「Ｃ」列ファイルの第１行の値を含み、４番目のバイトは第２行を開始し、５番目のバイトは列の第３行を開始する。したがって、データは、バイトインデックスによって列ファイルから読み出すことができる。

バイト（または、サイズの任意の他の適切なデータ単位）インデックスを用いることにより、列の値は、値の間のスペース／ギャップなしに、列ファイルに緊密にパッキングされうる。これは、列の値の空間効率のよい格納と、それらの値の効果的なルックアップとを可能にする。列ファイルは、個別かつコンパクトに格納されるので、動作が特定の列全体に対する動作を必要とする場合に、（例えば、インデックス化なしに）直接的に、対象ではない任意の他の列から値を読み出すことなしに、対応する列ファイルを読み出すことができる。したがって、図に示したデータ構造／フォーマットは、空間効率がよく、列状で、特定の列動作に最適化されている。上述のように、図のデータフォーマットは、ランダムアクセスおよび順次アクセスの両方に最適化されている。

いくつかの実施形態において、列ファイルおよび対応するルックアップテーブルのセットは、一緒にファイルセットに含められる。この例において、ルックアップテーブル７１４および列ファイル７１０は、ファイルセット７２２に含まれる。ルックアップテーブル７１６および列ファイル７１２は、ファイルセット７２４に含まれる。各ファイルセットは、ファイル名／キャッシュ識別子と関連付けられており、ファイル名／キャッシュ識別子は、実際の列の値を含むファイルセットをロケートするために利用されうる。この例において、ファイルセット名／識別子は、列ファイルの書き込みをもたらしたステップの名前と、ファイルを書き込んだパーティションとに基づいて生成される。例えば、パーティション０によって書き込まれたファイルセット７２２は、「ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」と呼ばれ、ｄｓ１をインポートするステップ（「ｉｍｐｏｒｔ＿ｄｓ１」）の間にファイルセットがパーティション０（「ｐ０」）によって書き込まれたことを示す。同様に、パーティション１によって書き込まれたファイルセット７２４は、「ｉｍｐｏｒｔ＿ｄｓ１＿ｐ１」と呼ばれ、ｄｓ１をインポートするステップ（「ｉｍｐｏｒｔ＿ｄｓ１」）の間にファイルセットがパーティション１（「ｐ１」）によって書き込まれたことを示す。パーティションすべてにわたって実行される動作のためのファイルセットを生成する場合、生成されるハンドル／キャッシュＩＤは、全パーティションにわたって一致する。この例で、インポートＤＳ１動作に関わるパーティション０および１について、パーティションによって書き込まれたファイルセットのハンドル（「ｉｍｐｏｒｔ＿ｄｓ１」）は、両方のパーティションにわたって一致しており、違いは、ファイルセット名の最後に連結されるパーティション番号である。いくつかの実施形態において、ファイルセットは、キャッシュ／ストレージに書き込まれ、上述の識別子を用いて取得できる。かかるキャッシュ識別子／ファイルセット名の利用については、後に詳述する。

図に示すように、データセットが、複数のパーティションに分割されえたが、指定された順序付けられた動作のセットは、パーティション間での情報の移動を必要としない（すなわち、行はパーティション間を移動しない）ので、スクリプト６００の残りのステップについては、１パーティションのみに関して実行される処理が示されている。入力データセットが分割された他の論理パーティションで、同様の処理が実行される。パーティション間の行の移動をもたらす動作の例については、後に詳述する。

書き込まれるファイルセットに加えて、各パーティションは、本明細書で「データトラバーサルプログラム」（ＤＴＰ）と呼ばれるものに関連付けられる。データトラバーサルプログラムは、参照テーブルおよび参照スタックを含んでおり、それらは共に、パイプラインの特定のステージ時点でのデータの一部の状態を読み出す方法（例えば、入力データセットに対して順序付けられた動作のセットのある部分を実行した累積結果であるものを読み出す方法）についての情報を提供する。参照テーブルは、順序付けられた動作のセット中の行変換の参照を含み、参照スタックは、順序付けられた動作の記録と、順序付けられた動作によって変更された列とを含む。いくつかの実施形態において、順序付けられた動作のセット中の各動作が実行されると、パーティションのためのデータトラバーサルプログラムの参照テーブルおよび参照スタックは、所与の動作まで順序付けられた動作のセットを実行した後に、累積変換結果を反映するように更新される。いくつかの実施形態において、データトラバーサルプログラムは、キャッシュ層に格納される。これは、データトラバーサルプログラムが、動作の実行時に高速でアクセスおよび更新されることを可能にし、それにより、動作を繰り返す必要なしに、（中間結果を含む）動作の結果への効率的なアクセスを可能にする。

いくつかの実施形態において、パーティションのデータトラバーサルプログラムは、実行時、パーティションの参照テーブルおよび参照スタックを用いて、入力データセットに実行された順序付けられた動作のセットに起因するデータセットのサブセットである順序付けられた行のセットを取得する。結果として得られたデータセット全体における順序付けられた行のサブセットの位置は、パーティションの順序内の対応するパーティションの位置に基づく。例えば、パーティション「Ｎ」のためのデータトラバーサルプログラムから取得された順序付けられた行のサブセットのすぐ後に、パーティション「Ｎ＋１」のためのデータトラバーサルプログラムから取得された順序付けられた行のサブセットが続く。様々なパーティションからの順序付けられた行のサブセットは、重複しない。順序付けられた行のサブセットは、この順に読み出されると、１または複数の入力データセットに実行された順序付けられたデータ準備動作のセットの結果を集合的に形成する。

いくつかの実施形態において、データトラバーサルプログラムの参照テーブルおよび参照スタックは、パイプライン内の所与の時点まで順序付けられた動作のセットを実行した累積結果を反映するように、各データ準備動作が実行されるにつれて更新される。パイプラインは、例えば、ユーザが見直したいと思いうる様々なステージおよび中間結果を含むので、いくつかの実施形態においては、データトラバーサルプログラムのコピーが、保存ポイントで（例えば、データ準備動作の順序における次のステップによって更新される前に）キャッシュされうる。キャッシングは、例えば、データがパイプライン／順序付けられた動作のセットの様々な時点を通して進むにつれて変化するデータの漸進的な保存を可能にする。

図７Ａの例に示すように、パーティション０および１の各々は、それぞれ、独自のデータトラバーサルプログラム７２６および７２８と関連付けられている。パーティション０に関連するデータトラバーサルプログラム７２６は、参照テーブル７０６および参照スタック７３０を備える。パーティション１に関連するデータトラバーサルプログラム７２８は、参照テーブル７０８および参照スタック７３２を備える。いくつかの実施形態において、データトラバーサルプログラム（対応する参照テーブルおよび参照スタックを含む）は、インポートの実行の結果として初期化（作成）される。後に詳述するように、いくつかの実施形態において、データトラバーサルプログラムは、順序付けられたデータ準備動作のセットの結果を表し、結果を引き出すために１または複数の影響を受けた列をどのように集めるのかを示す。

ここで、パーティション０の参照スタック７３０について記載する。この例において、（現在、インポートステップ後の１行だけを含む）参照スタック７３０の第１行は、キャッシュ識別子（「ｃａｃｈｅ ｉｄ」）７３４を含む。キャッシュ識別子は、７３６で示す行内の対応するエントリで示すように、列「Ａ」、「Ｂ」、および、「Ｃ」を提示する。キャッシュｉｄ７３４は、パーティション（パーティション０）のインジケータと併せると、ファイルセット７２２に対応するファイル名（「ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」）になる。これは、パーティション０によるインポートのために書き込まれたデータの位置を示す。参照スタックは、実行されたインポート動作から結果として得られたデータセット全体の一部である順序付けられた行のセットを読み出すために、対応する参照テーブルと併せて用いられる。

ＤＳ１のインポートの結果を読み出す一例は、以下の通りである。例えば、ユーザが、処理後のデータセットＤＳ１の状態を知りたいと仮定する（これは、インポートがデータセットへの修正を行わないことから、同じに見えるはずである）。図７Ａに示したファイルおよびデータトラバーサルプログラムは、（例えば、閲覧に向けて）インポートステップ時点のＤＳ１を集めるために、以下のように利用できる。

インポートされたデータを適切な順で読み出すために、パーティションのデータトラバーサルプログラムは、それらが対応するパーティションの順に実行される。したがって、パーティション０のデータトラバーサルプログラム７２６が最初に実行される（パーティションのデータトラバーサルプログラムは、並列で実行されてもよく、各データトラバーサルプログラムからの部分結果は、それらが取得された時の正確な順番で配置される）。

データトラバーサルプログラム７２６は、以下のように実行される。参照テーブル７０６は、３つの行を含む。これは、（パーティション０に関連する）データトラバーサルプログラムが、実行時に、インポートされたデータセットの最初の３行を提供することを示す。インポートされたデータセットの第１行は、以下のように取得される。参照テーブル７０６の第１行（７３８）内の第１（かつ、今のところ唯一の）列の値、すなわち、座標（０，０）が取得される。参照テーブルのこの列は、参照スタック内の第１（かつ、今のところ唯一の）行に対応する。その行は、キャッシュ識別子７３４を含み、７３６で列「Ａ」、「Ｂ」、および、「Ｃ」を識別する。

取得された座標（ゼロ）からのパーティション番号が、キャッシュｉｄ７３４に付け足されることで、ファイル名「ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」が得られ、これは、同じ名前のファイルセット７２２に対応する。次いで、ファイルセット７２２が、アクセスされる。次いで、取得された座標（ゼロ）の行識別子が取得される。取得された行識別子は、ファイルセット７２２のルックアップテーブル７１４のルックアップを実行するために、７３６で識別された列「Ａ」、「Ｂ」、および、「Ｃ」と併せて用いられる。列「Ａ」、「Ｂ」、および、「Ｃ」が識別されると、取得された行番号「ゼロ」が、ルックアップテーブルを用いて、それらの列のゼロ番目の行における値をルックアップするために用いられる。ルックアップテーブルのインデックス列のゼロ番目の行内の対応するバイトインデックスが取得され、列ファイル７１０にアクセスするために用いられる。したがって、列「Ａ」、「Ｂ」、および、「Ｃ」に対する値「ａ」、「ｂ」、および、「ｃ」を含む行は、対応する列ファイル７１０から取得される。

インポートされたｄｓ１データセットの第１行に到達するためにデータ実行プログラムによって実行される処理については、図７Ｂを参照しつつ再び記載する。

図７Ｂは、データトラバーサルプログラムを実行する実施形態の一例を示す。図７Ｂの例において、記載される様々な参照テーブル、参照スタック、および、ファイルセットは、図７Ａにおけるそれぞれの同等物に対応する。

パーティション０のためのデータトラバーサルプログラム（例えば、図７Ａのデータトラバーサルプログラム７２８）が実行される。データトラバーサルプログラムは、（図７Ａの参照テーブル７０６に対応する）参照テーブル７５０の１番目の行（７５２）を読み出すことによって開始する。この行内の単一のエントリは、座標（０，０）を含んでおり、これは、パーティション０、行ｉｄ０を示す参照である。

このように、行７５２は、単一の列を含んでおり、その列は、参照スタック７５４における唯一の行すなわち行７５６にマッピングされる／対応する。この例において、 参照スタック７５４は、図７Ａの参照スタックに７３０に対応する。行７５６は、２つのエントリを含んでおり、１つは、キャッシュ識別子のためのエントリである。以下に示すように、キャッシュ識別子は、ファイルセットをロケートするために行７５２から取得された座標内で識別されたパーティション番号と組み合わせられる。行７５６内の２番目のエントリは、ロケートされたファイルセットを用いて値が取得される列の示唆を含む。

行７５２から取得された座標は、７５８に示されており、図に示すように、パーティション番号（０）および行識別子（０）を示す。参照スタック７５４の行７５６から取得されたエントリは、７６０に示されている。７５８および７６０に示された取得済みの値は、以下のように一緒に用いられる。

参照７５８から抽出されたパーティション番号「０」は、７６０から抽出されたキャッシュｉｄ「ｉｍｐｏｒｔ＿ｄｓ１」値と組み合わせられ、ファイル名「ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」（７６２）を生成する。組みあわせは、例えば、文字列の連結、組み合わされた値のハッシュの生成、または、任意の他の適切な組みあわせ関数によって実行される。これは、同じ名前のファイルセット（図７Ａのファイルセット７２２）をロケートしてアクセスするために用いられ、そのファイルセットは、図７Ａに関して上述したように、インポートステップの結果として書き込まれたものである。

次いで、参照７５８から抽出された行識別子「０」は、ファイルセット７２２のルックアップテーブル７６６のルックアップを実行するために用いられる。抽出された行識別子「０」に基づいて、ルックアップテーブル７６６の行７６８が識別されアクセスされる。

参照スタック行７６０で指定された列タイトル７７０〜７７４（それぞれ「Ａ」、「Ｂ」、および、「Ｃ」）に基づいて、行７６８に対応するそれらの指定された列タイトルの値が、ルックアプされ取得される。これは、以下のように実行される。列「Ａ」、「Ｂ」、および、「Ｃ」が指定されているので、行７６８内の対応する列のインデックス値が、ルックアップテーブル７６６から取得される。次いで、それらのインデックスは、ファイルセット内のそれぞれ対応する列ファイルに書き込まれた実際のデータ値をルックアップするために用いられる。この例において、指定された列タイトル「Ａ」、「Ｂ」、および、「Ｃ」の対応する値は、「ａ」、「ｂ」、および、「ｃ」である。したがって、インポートされたｄｓ１の１番目の行が、読み出された／取得された。

次いで、インポートされたｄｓ１の次の２行が、参照テーブル内の下のエントリに移動して、上述したのと同じ処理を実行することによって読み出される。例え例えば、（参照座標（０，１）を備えた）参照テーブル７５０の２番目の行のエントリは、ファイルセット７２２から値「ｄ」、「ｅ」、および、「ｆ」を取得するために上述のデータトラバーサルプログラム処理を用いて、（参照テーブルの１番目の唯一の列と参照スタックの１番目の唯一の行とのマッピングに基づいて）参照スタック７５４の１番目の行と組み合わせられる。（値「ｇ」、「ｈ」、および、「ｉ」を含む）インポートされたＤＳ１の３番目の最終行も、パーティション０のデータトラバーサルプログラムを用いて同様に取得できる。

次いで、パーティション１のデータトラバーサルプログラム７２８も、上述のように同様に実行され、ＤＳ１の下の３行が順に取得される。

次いで、順序付けられた行の２つの取得されたサブセットは、組み合わせられ、出力として提供される。例えば、ユーザが、ユーザインターフェースで結果を見たい場合、順序付けられた行のサブセットは、対応するパーティション順に表示される（すなわち、パーティション１のデータトラバーサルプログラムを用いて取得された順序付けられた行のサブセットが、パーティション０のデータトラバーサルプログラムを用いて取得された順序付けられた行のサブセットの下に表示される）。ユーザが、結果を発行したいと示唆する場合、順序付けられた行のサブセットは、対応するパーティション順に基づいて互いに付加される（すなわち、パーティション１のデータトラバーサルプログラムを用いて取得された順序付けられた行のサブセットが、パーティション０のデータトラバーサルプログラムを用いて取得された順序付けられた行のサブセットの下に付加される）。

いくつかの実施形態において、データトラバーサルプログラムの実行は、各パーティションに対して並列で実行される。データトラバーサルプログラムから結果として得られた順序付けられた行のサブセットは、それらが取得されたパーティションの順に配置される。

インポートステージの時点で書き込まれた（インポート動作の結果を表す）データトラバーサルプログラムが保存されうる。キャッシュされたデータトラバーサルプログラムは、例えば、参照および参照テーブルを再生成する必要を避けるために、後に利用できる。

上記の例において、参照テーブルは、１列のみを含み、参照スタックは、１行のみを含む。複数列を備えた参照テーブルおよび／または複数行を備えた参照スタックを含むさらなる例については、後に詳述する。

スクリプト６００の例に続いて、ここで、大文字化動作およびフィルタ動作の実行に関連する処理の例について記載する。大文字化動作およびフィルタ動作は、パーティション間の行の移動をもたらさないため、互いに独立してパーティションによって実行されうるので、パーティション０で起きる処理を以下に示す。同様の処理が、パーティション１で実行される。

大文字化

データをインポートした後、スクリプト６００のパイプラインにおける次のステップは、列Ａの値に大文字化を実行することである。ここで、その動作は、特定の列（列Ａ）に対して実行される。図８Ａは、更新されたデータトラバーサルプログラム（８１０）と、列Ａに対する大文字化動作を実行する一環として生成されたファイルセット（８０６）との実施形態の一例を示す。

この例において、列Ａに対する大文字化動作は、以下のように実行される。大文字化動作の実行前、パーティション０のデータトラバーサルプログラムの状態は、図７Ａの例に示した状態である。

列Ａの現在の値は、例えば、データトラバーサルプログラムの現在の状態を用いて列Ａの読み出しを実行することによって取得される。大文字化動作は、取得された列値に対して実行される。現在、列Ａの値は、動作の結果と異なるので、列Ａの新しい大文字バージョンのための新しい列ファイルが、８０２に示すように書き込まれる（そのファイルは、大文字値を含む）。対応するルックアップテーブル８０４も、新しいバージョンの列Ａの値をルックアップできるように書き込まれる。新しい列ファイル８０２および対応するルックアップテーブル８０４は、ファイルセット８０６に含まれており、ファイルセット８０６は、この例では、８０８に示すように「Ｕｐ＿Ａ＿Ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」という名前を与えられる。この例において、ファイルセット名は、書き込まれたファイルセット内の列ファイルをこれまでにもたらした実行済みの動作を（例えば、文字列連結、ハッシュ関数などを用いて）組み合わせることによって生成される。ファイルセットを書き込んだパーティション番号も、名前に追加される。例えば、８０８の名前「ｕｐ＿Ａ＿Ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」は、ＤＳ１のインポート後に実行された列Ａに対する大文字化動作の実行時にファイルセット８０６がパーティション０によって書き込まれたことを反映するように生成されたものである。

このように、列Ａだけが動作中に指定され、列Ａの値だけが修正された（すなわち、列Ａがこの動作で唯一のアクティブな列である）ので、列Ａの新しいバージョンのためのファイルセットのみが、パイプラインのこのステージで作成される必要がある。したがって、大文字化動作によって触れられなかったデータセットＤＳ１内のその他の列に対しては、新しいデータを生成／書き込む必要はない。したがって、データ準備動作の実行時に変化するデータが、漸進的に書き込まれうる。

新しい列ファイルが大文字化ステップの結果として書き込まれたことで、パーティション０のデータトラバーサルプログラムは、それに従って（例えば、インポートステップ時点の状態から）更新／修正される。大文字化ステップ時点のデータトラバーサルプログラムの新しい状態は、８１０に示されている。

新しいデータトラバーサルプログラムは、以下のように生成される。パーティション０が関与する現在のデータトラバーサルプログラムが取得される（インポートステップ時点の図７Ａのデータトラバーサルプログラム７２６）。新しい行８１２が、既存の参照スタックの上に追加され（「置かれ」）、パーティション０の新しい参照スタック８１４を生成する。新しい行８１２は、以下を示す：（１）（パーティション番号なしの）新たに書き込まれたファイルセット８０６のキャッシュ識別子／ハンドル部分；および、（２）書き込まれた列のタイトル（「Ａ］）。この例では、列Ａの新しいバージョンが書き込まれている。この新しいバージョンの列Ａは、インポートステップの一環として書き込まれた列Ａファイルの以前のバージョンに取って代わる。これを表すために、行８１６の「Ａ」値は、下線で示すように、データトラバーサルプログラムには利用不可能であるとマークされている。データを読み出す時、新しい列Ａファイルから値が読み出され、（図７Ｂのファイルセット７２２に見られる）列Ａファイルの以前のバージョンは、アクセスおよび読み出しされない。これは、データトラバーサルプログラムが、最新バージョンの列のみの読み出しを強制することを可能にする。

新しい列８１６が、（列８１８のみを含んだ）既存の参照テーブルの左へさらに追加され、パーティション０のための新しい参照テーブル８２０が生成される。この例において、インポートされたデータセットの行は、位置を変えておらず、新しい列８１６に含まれる参照内の座標の各々は、まだ、列８１８に示したのと同じ位置および行識別子を特定する。

参照テーブル内の列（左から右）は、参照テーブル内の対応するそれぞれの行（上から下）にマッピングされる。例えば、参照テーブル８２０の列８１６は、参照スタック８１４の行８１２にマッピングされる。参照テーブル８２０の列８１８は、参照スタック８１４の行８１６にマッピングされる。このマッピングは、特定のパイプラインステージの時点のデータトラバーサルプログラムが、特定のパイプラインステージの時点のデータセットの行を集めるために、以前に書き込まれたファイルセットから値をどのように読み出すのかを知らせる。任意のその他の適切なマッピングが実行されてもよい。

したがって、インポートステップからのデータトラバーサルプログラムは、ｄｓ１のインポート後に大文字化を列Ａに実行した新しい結果を反映するために、更新／修正される。データトラバーサルプログラム８１０は、ｄｓ１がインポートされた後に列Ａが大文字化されたパイプライン内のステージでの結果の表現を格納するためにキャッシュされうる。いくつかの実施形態では、データトラバーサルプログラムに対応するシグネチャが生成される。シグネチャは、（例えば、動作の表現（例えば、文字列表現）を一緒にハッシュすることによって、動作を連結することによって、または、任意のその他の組みあわせ関数によって）キャッシュされるデータトラバーサルプログラムによって表された結果につながった動作に基づいて生成されうる。次いで、データトラバーサルプログラム８１０のコピーが、それに対応するシグネチャと共にキャッシュされる。その後、キャッシュされたデータトラバーサルプログラムは、後に詳述するように、それに対応するシグネチャによって後で識別されうる。

ＤＳ１のインポート後に大文字化を列Ａに実行した後に結果の一部を取得するために、更新されたデータトラバーサルプログラム８１０を実行する一例について、図８Ｂを参照して説明する。

図８Ｂは、データトラバーサルプログラムを実行する実施形態の一例を示す。図の例では、データセットＤＳ１をインポートした後に大文字化を列Ａに実行した結果としてのデータセットの１番目の行が読み出される。その行は、（例えば、ユーザインターフェースで見るため、発行／エクスポートのため、など）インポート動作およびその後の大文字化動作の結果が出力される時に、読み出されうる。図８Ｂの例において、様々な参照テーブル、参照スタック、および、ファイルセットは、図８Ａにおけるそれぞれの同等物に対応する。

この例では、パーティション０のためのデータトラバーサルプログラム（例えば、図８Ａのデータトラバーサルプログラム８１０）が実行される。データトラバーサルプログラムは、（図８Ａの参照テーブル８２０に対応する）参照テーブル８５０の１番目の行８５２を読み出すことによって開始する。その行は、２つのエントリ、すなわち、列８５４内の参照／座標（０，０）および列８５６内の参照／座標（０，０）、を含む。上述のように、参照テーブル８５０の最左列（８５４）は、（図８Ａの参照スタック８１４に対応する）参照スタック８５８の最上行（８６０）にマッピングされる／対応する。参照テーブル８５０の最右列（８５６）は、参照スタック８５８の最下行８６２にマッピングされる。

参照テーブル８５０の行８５２および列８５４における参照（０，０）と、参照スタック８５８の行８６０におけるエントリとのペアリングが、８６４に示されている。参照テーブル８５０の行８５２および列８５６における参照（０，０）と、参照スタック８５８の行８６２におけるエントリとのペアリングが、８６６に示されている。

ペアリング８６４を用いてデータトラバーサルプログラムによって実行される処理について、最初に説明する（８６４および８６６の処理は、任意の順に、並列で、または、任意のその他の適切な方法で実行されてよい）。参照テーブル８５０の行８５２および列８５４から取得された座標は、８６８に示されており、図に示すように、パーティション番号（０）および行識別子（０）を示す。参照スタック８５８の行８６０から取得されたエントリは、８７０に示されている。８６８および８７０に示された取得済みの値は、以下のように一緒に用いられる。

参照８６８から抽出されたパーティション番号「０」は、８７０から抽出されたキャッシュ識別子「Ｕｐ＿Ａ＿Ｉｍｐｏｒｔ＿ｄｓ１」値と組み合わせられ、ファイル名「Ｕｐ＿Ａ＿Ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」（８７２）を生成する。その組みあわせは、同じ名前のファイルセット（ファイルセット８７４）をロケートしてアクセスするために用いられ、そのファイルセットは、図８Ａに関して上述したように、インポートされたＤＳ１に対して列Ａへの大文字化動作が実行された結果として書き込まれたものである。この例において、ファイルセット８７４は、図８Ａのファイルセットに８０６に対応する。

次いで、参照８６８から抽出された行識別子「０」は、ファイルセット８７４のルックアップテーブル８７６のルックアップを実行するために用いられる。抽出された行識別子「０」に基づいて、ルックアップテーブル８７６の行８７８が識別されアクセスされる。

参照スタック行８７０で指定された列タイトル８８０（「Ａ」）に基づいて、行８７８に対応する指定された列タイトルの値が取得される。その値は、ルックアップテーブルの行８７８内の列Ａのインデックス値をルックアップすることによって取得される。これは、バイトインデックス「０」を提供する。列Ａのためのファイル（Ａ＿ｆｉｌｅ）のゼロ番目のバイトインデックスでの値が取得される。これは、値「Ａ」である。これは、大文字化ステップの前の値（「ａ」）の大文字バージョンである。したがって、インポートされたデータセットＤＳ１の列Ａに対する大文字化の結果として得られたデータセットの１番目の行の列Ａの値が取得される。

次いで、データトラバーサルプログラムは、ペアリング８６６を用いて、列ＢおよびＣの残りの値を取得するよう構成されている。列Ａの（ｄｓ１のインポート後にＡに大文字化した後のパイプラインのステージの時点での）現在の値がファイルセット「Ｕｐ＿Ａ＿Ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」から取得された上述の処理と対照的に、列ＢおよびＣの現在の値は、別のファイルセットから取得される。この例において、列ＢおよびＣの値は、インポートステップ中に書き込まれたファイルセット（「Ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」）を用いて取得される。これは、列ＢおよびＣが列Ａへの大文字化動作によって変更されておらず、したがって、以前のステージで書き込まれたそれらの値がパイプラインのこのステージでも有効である（まだ最新のバージョンである）ことを、部分的に反映している。

ペアリング８６６は、以下のように、データトラバーサルプログラムによって用いられる。参照テーブル８５０の行８５２および列８５６から取得された座標は、８８２に示されており、図に示すように、パーティション番号（０）および行識別子（０）を示す。参照スタックの行８６２から取得されたエントリは、８８４に示されている。８８２および８８４に示された取得済みの値は、以下のように一緒に用いられる。

参照８８２から抽出されたパーティション番号「０」は、８８４から抽出されたキャッシュｉｄ「ｉｍｐｏｒｔ＿ｄｓ１」値と組み合わせられ、ファイル名「ｉｍｐｏｒｔ＿ｄｓ１＿ｐ０」（８８６）を生成する。組みあわせは、例えば、文字列の連結、組み合わされた値のハッシュの生成、または、任意の他の適切な組みあわせ関数によって実行される。これは、同じ名前のファイルセット（ファイルセット８８８）をロケートしてアクセスするために用いられ、そのファイルセットは、図７Ａに関して上述したように、インポートステップの結果として以前に書き込まれたものである。この例において、ファイルセット８８８は、図７Ａのファイルセットに７２２に対応する。

参照スタック行８８４で指定された列タイトル８９０および８９２（それぞれ「Ｂ」および「Ｃ」）に基づいて、行８９４に対応するそれらの指定された列タイトルの値が、ファイルセット８８８内でルックアプされ取得される。これは、以下のように実行される。列「Ｂ」および「Ｃ」が指定されているので、行８９４内の対応する列のバイトインデックス値が取得される。次いで、それらのインデックスは、ファイルセット内のそれぞれ対応する列ファイルに書き込まれた実際のデータ値をルックアップするために用いられる。この例において、指定された列タイトル「Ｂ」および「Ｃ」の対応する値は、それぞれ、「ｂ」および「ｃ」である。

この例では、上述のように、列Ａが大文字化動作によって変更されたので、ファイルセット８８８から取得される列Ａのバージョンがもはや有効／現行ではなく、列Ａファイルのそのバージョンから値が取得されるべきでないことを示すために、列タイトル「Ａ」は、参照スタック８５８の行８６２から除去されている（下線によって示されている）。したがって、ファイルセット８８８内の列Ａの値は取得されなかった。

上で示したように、動作によって変更される列については、新しい列ファイル（および対応するルックアップテーブル）のみが書き込まれる。参照スタックは、最新の（パイプラインの或る対応するステージの時点の）バージョンの列が位置する場所（すなわち、ファイルセットの位置、および、どの列がそのファイルセットから読み出されるのか）を示すために、部分的に用いられる。

２つのファイルセットから取得された値は、共に組み合わせられて、データセットＤＳ１（「Ａ」、「ｂ」、「ｃ」）のインポート後に大文字化を列Ａに実行した累積結果の１番目の行を生成する。

結果の残りの行は、参照テーブルの行を下がって、上述したのと同じ処理を実行することによって決定される。この順で参照に対してデータトラバーサルプログラムを実行することにより、パーティション０のためのデータトラバーサルプログラムを用いて取得される全体結果のその一部は、正しい順序になる。

同様の処理が、パーティション１に実行される。次いで、パーティション０およびパーティション１について取得された部分結果は、全体結果を形成するように組み合わせられ、ここで、パーティション０から取得された結果の一部は、パーティション１からの結果の一部の前に置かれる。

この例で示したように、２つの異なるファイルセットが、入力データセットに実行された複数の動作から結果として得られたデータセット内の単一の行を構成する値を決定するためにアクセスされた。

フィルタ
図６Ａのスクリプト６００の例に続いて、列Ａに大文字化を実行した後、パイプラインの次のステージ／一連の順序付けられた動作における次のステップは、列Ｂに対するフィルタリングである。特に、データは、添付の基準に従って列Ｂにフィルタリングされる、すなわち、列Ｂにおいて値「ｅ」および「ｈ」に関してフィルタリングされる。これは、データセット内の総行数（および各パーティション内の行数）を潜在的に削減する。

フィルタリング動作においては、データ値は変更されない。したがって、変更される列がないので、動作の結果として、新しいファイルセットは全く書き込まれない。しかしながら、パーティションのデータトラバーサルプログラムによって表される行の数は減少しうる。したがって、パーティションの参照テーブルおよび参照スタックは、これを反映するように更新される。

実施形態の一例において、データトラバーサルプログラム（ならびに参照テーブルおよび参照スタック）の状態は、図９Ａを参照して以下に述べるように決定／更新される。

図９Ａは、フィルタ動作の結果を反映するようにデータトラバーサルプログラムを更新するための処理の一実施形態を示す。いくつかの実施形態において、図９Ａで実行される処理は、１または複数のパイプラインエグゼキュータ（例えば、Ｓｐａｒｋワーカ）がパーティション（パーティション０など）に働きかけることによって実行される。いくつかの実施形態において、（行がフィルタ動作の結果としてパーティション間を移動しないため）各エグゼキュータは独立的にその作業部分に作用する。

参照テーブルは、以下のように更新される。ステップ１（９０２）で、パーティションのための（列Ａの大文字化が実行された時点の）現在の参照が取得される。いくつかの実施形態において、取得される参照は、図８Ａの参照テーブル８２０から取得される。テーブル９０４内の参照の各行は、列Ａへの大文字化動作まで順序付けられた動作のセットを実行した累積結果における特定の行を表す。

ステップ２（９０６）で、テーブル９０４によって表される行に対応する列Ｂの値が取得される。いくつかの実施形態において、それらの値は、上述のように参照および対応する参照スタックを用いてデータトラバーサルを実行することによって取得される。いくつかの実施形態において、 値を取得するために用いられる対応する参照スタックは、図８Ａの参照スタック８１４である。いくつかの実施形態において、列Ｂの値を用いて追加される列は、テーブル９０４の右側に追加され、変更されたテーブル９１８を生成する。

ステップ３（９０８）で、テーブル９１８は、フィルタ基準（列Ｂの値「ｅ」および「ｈ」に関するフィルタ）に従ってフィルタリングされる。フィルタの結果は、９１０に示されている。例えば、Ｓｐａｒｋ実装例では、Ｓｐａｒｋフィルタ動作が、（ＲＤＤとして表される）テーブル９１８上で呼び出される。フィルタ変換は、テーブル９１８内の行の一部を備えた新たなＲＤＤを返し、これは、９１０に示されている。ステップ４（９１２）で、列Ｂの値が削除され、結果として、参照だけを含むテーブル９１４が得られる。これらの参照は、フィルタリング動作後に残る行を表す。ステップ５（９１６）で、テーブル９１４は、パイプラインのこのステージで更新された参照として保存される。

参照スタックに関しては、新たな列データが書き込まれていないので、参照スタックは、フィルタステップで更新される必要がない。いくつかの実施形態において、保存は、フィルタリング後に自動的に実行され、これは、現在の参照テーブルの保存を含む。保存の実行時、いくつかの実施形態において、新しいエントリ（行）が、参照スタックの上部に置かれる。いくつかの実施形態において、参照スタックの新しい行は、後の利用のためにリトリーブできるように、保存された参照テーブルに対するハンドル／キャッシュ識別子を含む。例えば、いくつかの実施形態において、参照テーブルは、ハンドル／キャッシュ識別子を部分的に用いて参照されるファイルセットの一部として格納される。この例において、ファイルセットは、参照テーブルのみを含み、ルックアップテーブルも列ファイルも含まない（新しい列データが書き込まれていないため）。参照スタックの新しい行の列部分は、空である。参照テーブル内の対応する列も生成される。

この結果として、図９Ｂに示すデータトラバーサルプログラムが得られる。

図９Ｂは、データトラバーサルプログラムの実施形態の一例を示す。この例では、値「ｅ」および「ｈ」に関して列Ｂにフィルタ動作を実行した結果を表すパーティション０のための更新されたデータトラバーサルプログラムが示されている。データトラバーサルプログラムは、更新された参照テーブル９５２ を含んでおり、これは、例えば、図９Ａに記載された処理を用いて生成されたものである。上述のように、保存が動作後に実行されたので、変更されたデータがなくても、参照スタック９５４は、パイプラインの以前のステージから更新されている。

パイプラインのこのステージでの累積結果を読み出すために、パーティション０（およびその他の論理パーティション）のためのデータトラバーサルプログラムが、上述したのと同様の方法で実行される。例えば、図９Ｂに示したデータトラバーサルプログラムは、インポート動作後の大文字化動作後にフィルタ動作を実行した累積結果の一部（累積結果の最初の２行）を取得するために実行されうる。いくつかの実施形態において、参照スタックエントリの行で指定された列がない場合、読み出されるデータ値はない（すなわち、データトラバーサルプログラムに関連する列を備えた参照スタックエントリのみが読み出される）。したがって、図９Ｂに示したデータトラバーサルプログラムを実行することにより、９５６に示す結果が得られる。

図に示すように、累積動作の結果は、データトラバーサルプログラム内に反映されるが、それらの累積結果を達成するために正確にどの動作が実行されたのかという示唆は、データトラバーサルプログラム内に必ずしも存在しない。いくつかの実施形態において、パイプライン内の特定のステージのデータトラバーサルプログラムをキャッシュする時、累積結果を達成するために実行されたステップに基づいて、１または複数のシグネチャのセットが構築／生成される。１または複数の生成されたシグネチャは、キャッシュされたデータトラバーサルプログラムに割り当てられる。

図に示すように、フィルタ動作時点のデータの状態に到達するために実行された処理は、列Ｂの値を直接見て、それらの値をフィルタリングすることで、データセット内にどの行が残るのかを決定する処理である。残ったそれらの行のみが、フィルタステップの時点で更新された参照テーブル内に反映される。このデータ表現を用いてフィルタリングを実行した時には、新しいデータは書き込まれていない。むしろ、フィルタの結果としての行の削減が、参照テーブルにおける行数の削減に捕らえられ、列Ｂの値だけを見ることによって達成された。これは、結果を書き出すその他のフィルタリング技術と対照的であり、ここで、フィルタリングされたデータセット全体を書き出すコストは、データセットの総列数の関数である。ここで、結果のコンパクト表現は、順序付けられたデータ準備動作のセットの累積結果を反映するように更新される。

図６Ａのスクリプトに関して上述した動作例は、パーティション間の情報の移動をもたらさない。以下の例では、パーティションにわたる参照の移動をもたらす動作（ソート）（例えば、ここでは、行がパーティションを交換する）が示される。

ソート
図１０Ａは、ソートされるデータセットの一実施形態を示す図である。このソート動作例を通して、ソートされるデータセット（１０００）は、「ＤＳ」と呼ばれる。データセット１０００は、２つの列（Ｃ０およびＣ１）と、４つの行とを含む。

図１０Ｂは、データトラバーサルプログラムおよびファイルセットの一実施形態を示す図である。図１０Ａの例に続いて、データセットＤＳが、各々２つの行を備えた２つのパーティション（パーティション０およびパーティション１）に分割され、１０１０および１０１６に示すように、インポートされたと仮定する。この例において、パーティション０は、データトラバーサルプログラム１０１２を初期化し、ファイルセット１０１４を書き込んだ。この例において、ファイルセット１０１４は、「ｉｍｐｏｒｔ＿ｄｓ＿ｐ０」と名付けられる。同様に、パーティション１は、データトラバーサルプログラム１０１８を初期化し、ファイルセット１０２０を書き込んだ。この例において、ファイルセット１０２０は、「ｉｍｐｏｒｔ＿ｄｓ＿ｐ１」と名付けられる。パーティション０の参照スタックおよびパーティション１の参照スタックのキャッシュ識別子は両方とも、同じキャッシュ識別子／ハンドル「Ｉｍｐｏｒｔ＿ｄｓ」を備える。いくつかの実施形態において、各パーティションは、自身の計算の場所にローカルにそれぞれの書き込まれたファイルセットを格納する。

この例において、ソート条件Ｃ０は、データセットの行が移動すべき場所を決定するために用いられる。いくつかの実施形態において、Ｓｐａｒｋなどの分散型計算プラットフォームが、（参照によって表された）行を正確な位置へ移動させる作業（すなわち、パーティション間で参照を移動させることによって表されるソートによる行の移動）を実行するために利用される。

この例において、ソートは、Ｃ０に実行される。図１０Ｃは、ソートされた結果の一例を示す。ソートの前のデータセットＤＳが、１０３０に示されている。データセットＤＳへのソート動作の結果が、１０３２に示されている。図に示すように、データセットＤＳの行１０３４および１０３６が、ソート動作により位置を入れ替える。ソート動作の結果を表すためのデータトラバーサルプログラムの更新に関与する処理については、後に詳述する。

図１０Ｄは、ソート動作を実行するための処理の一実施形態を示す図である。この例において、ソート動作は、部分的には、キー／値ペアを生成してソートすることによって実施される。キー／値ペアは、データが、値およびその値を特徴付ける何らかのキーとして表されることを可能にする。以下の例において、キーは、それに関してソートが実行されるものである。この例で示すように、キー／値ペアが生成され、ここで、キー／値ペアの値は、（参照のセットによって表された）行であり、キーは、その行のためのＣ０の実際のデータ値である。次いで、キー／行ペアは、キーによってソートされ、それにより、行（参照）は、（例えば、パーティションにわたって）再配列される。ソート動作処理の一実施形態は、以下のように実行される。以下に示すように、処理の結果は、インポートされたデータセットＤＳへのソート動作の結果を表す更新されたデータトラバーサルプログラムのための更新された参照テーブルである。

ステップ１（１０４０）で、データセットＤＳのすべての行が取得される。データセットＤＳの各行は、１または複数の参照のセットを用いて表され、参照のセットは、図１０Ｂのデータトラバーサルプログラム１０１２および１０１８から取得される。この例において、線１０４２より上の参照は、パーティション０のデータトラバーサルプログラム１０１２から取得されたものである。線１０４２より下の参照は、パーティション１のデータトラバーサルプログラム１０１８から取得されたものである。いくつかの実施形態において、ステップ１に示された参照は、各パーティションのための参照テーブルである。

ステップ２（１０４４）で、各行のＣ０の値が追加される。以下に示すように、Ｃ０の値は、各行のキーとして用いられる。次いで、ソートが、キーに関して実行される。いくつかの実施形態において、各行のＣ０の値は、上述のようにそれぞれのファイルセットからＣ０の値をルックアップするために、図１０Ｂのデータトラバーサルプログラム１０１２および１０１８を実行することによって取得される。

ステップ３（１０４６）で、Ｃ０に関するキーが生成される。このステップにおいて、取得されたＣ０の値は、キー／行ペアを生成するために、それらに対応する行（参照）とペアになったキーとして用いられる。いくつかの実施形態において、ステップ３では、ステップ２で取得された値が、キー位置に抽出される。いくつかの実施形態において、ステップ３は、キー／行すなわちキー／値ペアの生成への中間工程である。ステップ４（１０４８）では、ステップ２で取得された値が、行から削除される。これにより、１０５０に示すように、４つのキー／値ペアのセットが得られる。

いくつかの実施形態において、キー／値ペアは、参照テーブルを適所に操作することによって生成される。最初に、参照テーブルが、ステップ１に記載されるように取得される。Ｃ０の値は、ステップ２でファイルセットから引き出され／抽出され、参照テーブルの追加セルとして（例えば、参照テーブルの右に追加された新しい列内に）追加される。Ｃ０の値は、（左位置がキー／値ペアの「キー」位置に対応するため）参照テーブルの左にＣ０の値をコピーすることによってキー／値ペアを作成するためにコピーされる。参照テーブルの右のセルにある抽出された値は、記憶空間を節約するために、削除される。キー／値ペアは、本明細書では「キー／行ペア」とも呼ばれる。

いくつかの実施形態において、キー／値ペア生成は、様々なパーティション／ワーカがファイルセットからの行に入り込んで、キーとして用いられる対応するＣ０の値を取得するので、様々なパーティション／ワーカによって並列で実行される。

ステップ５（１０５２）では、ステップ４で生成されたキー／行ペア１０５０は、キーで（例えば、キー／行ペアに関するＳｐａｒｋ「ｓｏｒｔＢｙＫｅｙ」コマンドを発行することによって）ソートされる。「ｓｏｒｔＢｙｋｅｙ」コマンドの結果が１０５４に示されており、ここで、キー／値ペアは、キー値（すなわち、Ｃ０の値）でソートされている。図に示すように、キー／行ペア１０５６およびキー／行ペア１０５８の位置は、「ｓｏｒｔＢｙＫｅｙ」コマンドの結果として入れ替えられている。

ステップ６（１０６０）で、１０５４のキーは、参照のみが残るように除去される。キーは、ソートのためのキー／値ペアを形成するために追加されたので、もはや必要ないため、除去される。キーの除去後、参照１０６２のみが残る。この例では、保存ポイントが、ソート動作後に作成されるので、ステップ６で、参照チェックポイントも作成される（ここで、いくつかの実施形態において、各保存は、参照チェックポイントを作成する）。いくつかの実施形態において、参照チェックポイントの作成は、上述のフィルタリング動作と同様に、参照テーブルの更新および保存を含む。フィルタリング動作と同様に、参照の新しい列が追加される（１０６８に示されている）。この例において、列１０６８は、列１０６２の左に追加される。列１０６８内の新しいエントリは、列１０６２内のそれらに対応する参照の更新されたパーティション／行識別子に基づいて、参照値を割り当てられる。例えば、（線１０６６より上の）列１０６２内の上２つの参照は、パーティション０に関連付けられる。したがって、線１０６６より上の列１０６８内の上２つの対応する値は、（０，０）および（０，１）である。同様に、列１０６２内の下２つの参照は、パーティション１に関連付けられる。したがって、線１０６６より下の列１０６８内の下２つの対応する値は、（１，０）および（１，１）である。ソート動作後に保存が実行されない場合、列１０６８は、追加される必要がない。

いくつかの実施形態において、（参照テーブルが保存されるので）参照チェックポイントを作成する一環として、新しい行が、上述のフィルタ動作のように、対応する参照スタックの上に追加される。例えば、参照スタック内の新しい行は、対応する保存された参照テーブルへのハンドル／キャッシュ識別子を含むが、行の列部分は空いたまま残される。参照スタックのこの新しく追加された行は、参照テーブルに追加された新しい列に対応する。いくつかの実施形態において、ソート動作後に実行される保存がない場合、新しい行は、参照スタックに追加される必要はない。

更新された参照テーブルおよび参照スタックの例を、図１０Ｅに示す。

ステップ７（１０６４）で、参照が保存される。この例において、線１０６６より上の参照は、パーティション０のための新しく更新された参照テーブルとして保存される。線１０６６より下の参照は、パーティション１のための新しく更新された参照テーブルとして保存される。

一実装例において、ステップ１〜７は、以下のように実装／実行される。パーティション０および１は、別個に並列でステップ１〜４を実行する。いくつかの実施形態において、パーティションは、ステップ１〜４を実行して、一度に１つのキー／値ペアを（すなわち、順次）取得する。キー／値ペアは、並列で動作するパーティションによって生成されるので、コレクタ（例えば、Ｓｐａｒｋコレクタ）へパーティションによってストリーミングされる。例えば、コレクタは、各パーティションによって、（すなわち、（存在する場合）次のキー／値ペアを取得するためにイテレータ「ｎｅｘｔ」を求めることによって）、一度に１つのキー／値ペアを読み出すためにコレクタが用いるイテレータを提供される。次いで、コレクタは、様々なイテレータからキー／値ペアを受信すると、キー／値ペアをソートする。ソートの完了後、コレクタ自体が、イテレータを返し、そこから、ソートされたキー／値ペアが順次にストリーミングされうる。ソートされたキー／値ペアは、それらに適切なパーティションにストリーミングされる。これは、参照がそれらに適切なパーティションに分散されることを可能にする。いくつかの実施形態において、グローバルソートが実行される。次いで、キー／値ペアは、それらに適切なパーティションに送信される。次いで、キー／値ペアが正確な順序であることを保証するために、ローカルソートが、パーティション内で実行される。

図１０Ｅは、データトラバーサルプログラムの実施形態の一例を示す。この例では、Ｃ０へのソート動作の時点で更新されたデータトラバーサルプログラムが、（上述した図１０Ｄの処理を用いて）示されている。パーティション０のためのデータトラバーサルプログラムは、１０７０に示されている。データトラバーサルプログラム１０７０のための参照テーブルは、図１０Ｄのステップ６（１０６０）の線１０６６より上の参照を用いて生成された。パーティション１のためのデータトラバーサルプログラムは、１０７２に示されている。データトラバーサルプログラム１０７２のための参照テーブルは、図１０Ｄのステップ６（１０６０）の線１０６６より下の参照を用いて生成された。

この例では、フィルタ動作と同様に、新しいデータ（列）は、ソート後に書き込まれなかった。しかしながら、ソート動作の結果が保存され、上記のステップ６で参照チェックポイントが生成されるので、新しいエントリ／行が、１０７４および１０７６で示すように、参照スタックの上部に置かれている。列が書き込まれなかったので、新しい行の列部分は空である。保存がなされなかった場合、各パーティションのための参照スタックは、同じままである。

この例で示すように、上述のソート動作処理の結果として、参照（１，０）および（０，１）は、パーティションを交換した。１つのパーティションのためのデータトラバーサルプログラムが、２つのパーティションからの参照をその参照テーブル内に含むが、データトラバーサルプログラムによって維持された結果の一部を読み出すためのそれらのデータトラバーサルプログラムの実行は、上述したのと同じ方法で実施される。

例えば、単一のパーティションのための参照テーブルが、異なるパーティション由来の２つの行を含むので、それらの行の値は、２つの異なるファイルセット（例えば、図１０Ｂのファイルセット１０１４および１０２０）から取得される必要がある。しかしながら、パーティションのための参照スタック内のキャッシュ識別子は１つだけである。上記の例に記載の方法でデータトラバーサルプログラムを実行することにより、両方のファイルセットにアクセスすることができる。これは、部分的には、ファイルセット１０１４および１０２０の名前が同じベース／ハンドル「ｉｍｐｏｒｔ＿ｄｓ」を共有することによる。したがって、データトラバーサルプログラムの実行時、適切なファイルセットが、評価されている参照／座標のパーティション識別子を参照スタック由来のベース／ハンドル「ｉｍｐｏｒｔ＿ｄｓ」キャッシュ識別子と組み合わせることによって取得される。いくつかの実施形態において、ファイルセットは、それらを書き込んだパーティションにローカルに格納される。行がパーティションを交換すると、いくつかの実施形態において、それに対応するファイルセットが、行が移動されるノード上でローカルに複製される。これは、ファイルセットが、ローカルにアクセス可能になることを可能にし、値の取得速度を改善すると共に、（例えば、ノード間でのデータの転送時の）ネットワーク帯域幅を低減する。別の実施形態では、ファイルセットは複製されず、参照される。

上記の例のソート処理に示したように、キーでソートされるキー／値ペアの生成など、ソート動作の一部が、適所で実行される。これは、メモリ最適化を提供し、ここで、キー／値マッピングを格納するために新しいメモリ空間は作成されない。むしろ、既存のデータエントリが、ソート可能なフォーマットになるまで修正される。さらに、ファイルセットから読み出された唯一の値は、Ｃ０の値であった。データセットの行の移動は、参照によって表され、Ｃ０の値だけのソートに基づいて決定された。次いで、参照が、ソートの結果を反映する更新されたデータトラバーサルプログラムを作成するために、異なるパーティションに移動された。

これは、ソート動作がＳｐａｒｋなどの計算プラットフォームにおいてネイティブに処理される方法とは対照的である。例えば、Ｓｐａｒｋでは、上述したような参照の書き込みよりも大量のデータを含む実際のデータが移動および書き込みされるため、よりコストが掛かる。

図１０Ｆは、ネイティブＳｐａｒｋソートの実施形態の一例を示す。この例では、開始１０８０で、データセット１０８２が、分割ライン１０８４で示すように、Ｓｐａｒｋによって２つのパーティションに分割されていると仮定する。この例では、データセット内の各行が、多数の値を有してよく、すべての値がＳｐａｒｋによって処理される。これは、本明細書に記載の技術と対照的であり、ここで、実際のデータのセット全体に動作を実行するのではなく、データセットの行を表す参照が操作される。１０８６で、Ｃ０の値によるキー作成が、キー／値ペアを生成するために実行される。１０８８で、キー／値ペアがキーでソートされる。次いで、キーは、結果としてのデータセットを取得するために、１０９０で削除される。この例に示すように、動作は、データセット全体のすべてのデータから開始し、すべてのデータが、動作全体を通して保持される。この結果として、データセット全体を収容するために、中央処理ユニット（ＣＰＵ）リソース、メモリリソース、ディスクリソース、（例えば、パーティション間でデータセット全体を移動させるための）帯域幅など、リソースを潜在的に大量消費する。本明細書に記載の技術を用いれば、実際のデータセットに作用するのではなく、データセットのコンパクト表現（例えば、データトラバーサルプログラム）が処理されて、データ値が、必要な時にのみ取得される。これは、はるかに少量のデータが、順序付けられた動作のパイプラインを通して処理されることを可能にし、データ準備を実行する効率を改善する。

上記では、単一のデータセットに関する動作が実行された。付加および結合のデータ準備動作の以下の例では、複数のデータセットが組み合わせられる。組み合わせる前のデータセットは、それぞれ潜在的に、組み合わせられる前に独自のパイプラインを通して処理されている場合がある。以下に示すように、組み合わせられたデータセットに対して結果として得られるデータトラバーサルプログラムは、それらに起こったことの複数の履歴を持つパーティションを備えることになる。

付加
図１１Ａは、付加動作を含むスクリプトの実施形態の一例を示す。１１０２で、インポートされる第１データセット（これらの例では「ＤＳ１」と呼ぶ）の位置が指定される。１１０４で、インポートされる第２データセット（これらの例では「ＤＳ２」と呼ぶ）の位置が指定される。１１０６で、付加動作が指定される。付加動作を指定する一環として、付加されるデータセットの１つが、駆動（アンカー）テーブルとして指定され、それに対して他のテーブルが付加される（「付加テーブル」と呼ばれる）。この例において、ＤＳ１は駆動テーブルであり、ＤＳ２は付加テーブルである。スクリプト１１００の例では、ＤＳ１およびＤＳ２内のどの列を付加するのかについての仕様も示されている。この例では、ＤＳ１の列Ｃ００が、ＤＳ２のＣ０１にマッピングされる。ＤＳ１の列Ｃ１０が、ＤＳ２の列Ｃ１１にマッピングされる。データセット例ＤＳ１およびＤＳ２、ならびに、スクリプト１１００内で指定された条件に基づいて結果として付加されるデータセットについて、図１１Ｂを参照して記載する。

図１１Ｂは、付加されるデータセットの実施形態の一例を示す。この例において、データセットＤＳ１は、１１１０に示されている。データセットＤＳ２は、１１１２に示されている。結果として得られる付加されたデータセットは、１１１４に示されている。図に示すように、ＤＳ１は、図１１Ａのスクリプト１１００に従って駆動テーブルとして指定されているので、ＤＳ２は、ＤＳ１の下に付加されており、ここで、ＤＳ２の列Ｃ０１は、ＤＳ１の列Ｃ００に付加され、ＤＳ２の列Ｃ１１は、ＤＳ１の列Ｃ１０に付加され、それらのマッピングは、図１１Ａのスクリプト１１００に記述されたものである。付加されたデータセットのための列の再命名も示されている。例えば、ＤＳ１の列Ｃ００に付加されたＤＳ２の列Ｃ０１を含む新しい列は、列「Ｃ０」と再命名されている。同様に、ＤＳ１の列Ｃ１０に付加されたＤＳ２の列Ｃ１１を含む新しい列は、列「Ｃ１」と再命名されている。

図１１Ｃは、２つの異なるデータセットのためのパイプラインに関連する論理ファイル／名前空間の実施形態の一例を示す。この図には、ＤＳ１およびＤＳ２が示されており、それらは、付加動作の前にインポートされた。図の例において、ＤＳ１およびＤＳ２は、独自のそれぞれのパイプラインでインポートされた（ここで、或るパイプラインがＤＳ１に対して宣言され、別個のパイプラインがＤＳ２に対して宣言された）。いくつかの実施形態において、パイプラインを宣言することは、（例えば上述のように）データセットをインポートし、データセットに適用される変換ステップを宣言することを含む。ＤＳ１のパイプライン１１２０において、ＤＳ１は、２つのパーティション（パーティション０および１）に分割され、各パーティションはＤＳ１の２つの行を備える。パーティション０および１のためのデータトラバーサルプログラムは、それぞれ、１１２２および１１２４に示されている。ＤＳ１の上の２行は、パーティション０のデータトラバーサルプログラム１１２２によって表され、ＤＳ１の下の２行は、パーティション１のデータトラバーサルプログラム１１２４によって表される。ＤＳ２のパイプライン１１２６において、ＤＳ２は、３つのパーティション（パーティション０、パーティション１、および、パーティション２）に分割され、各パーティションはＤＳ２の１行を含む。パーティション０、パーティション１、および、パーティション２のためのデータトラバーサルプログラムは、それぞれ、１１２８、１１３０、および、１１３２に示されている。ＤＳ２の上の行は、パーティション０のデータトラバーサルプログラム１１２８によって表され、ＤＳ２の真ん中の行は、パーティション１のデータトラバーサルプログラム１１３０によって表され、ＤＳ２の下の行は、パーティション２のデータトラバーサルプログラム１１３２によって表される。それらのパーティションによって書き込まれた対応するファイルセットも示されている。いくつかの実施形態において、データセットＤＳ１およびＤＳ２は、異なるパイプラインにあり、独立して分割された。

この例では、独立したパイプラインがＤＳ１およびＤＳ２に対して宣言されたので、各パイプラインのための論理パーティションの番号付けは、いずれも０から始まる。いくつかの実施形態において、各パイプラインは、独自の名前／ファイル空間に関連付けられる。

図１１Ｄおよび図１１Ｅは、それぞれ、付加動作前後のデータトラバーサルプログラムの実施形態の一例を示す。図１１Ｄに示すＤＳ１空間およびＤＳ２空間におけるパーティションおよび対応するデータトラバーサルプログラムは、図１１Ｃに示したＤＳ１空間およびＤＳ２空間におけるパーティションおよび対応するデータトラバーサルプログラムに対応する。

いくつかの実施形態において、２つのデータセットを付加することは、付加の結果のための新しいパイプラインを作成することを含む（例えば、新しいパイプラインが、新しい付加されたデータセットに対して宣言される）。パイプラインは、独自のファイル／名前空間およびパーティションを備える。この例の付加において、新しいパイプライン内のパーティションの数は、一緒に付加されるデータセットのための２つのパイプラインにわたるパーティションの総数に等しい。例えば、ＤＳ１がＭ個のパーティションを備え、ＤＳ２がＮ個のパーティションを備えていた場合、新しいパイプラインは、Ｍ＋Ｎ個のパーティションを備える。したがって、この例において、ＤＳ１パイプラインは２つのパーティションを備え、ＤＳ２パイプラインは３つのパーティションを備えるので、結果として得られるパイプライン（本明細書では「プロジェクト」パイプラインと呼ぶ）は、５つのパーティションを備える。

付加動作は、ＤＳ１の行の下にＤＳ２の行を効果的に配置する。以下に示すように、この結果は、単一のパイプライン（新しい「プロジェクト」パイプライン）の下にＤＳ１およびＤＳ２のパーティションすべてを配置することによって表される。そうすることにより、それらのパーティションは、（付加の前であるために２つの別個のデータセットではなく）１つの単一データセットとして扱われる。単一のパイプラインの下にパーティションを配置する場合、（対応するデータトラバーサルプログラムを含む）パーティションは、それらの順番付けが、付加されたデータセット内の行の新しい配列を反映するように、番号を付け直される（すなわち、パーティションは、それらの元々のパイプライン空間から新しいプロジェクトパイプライン空間に再マッピングされた）。結果として得られる「プロジェクト」パイプライン空間の一例について、図１１Ｅを参照して説明する。

図１１Ｅは、パイプラインファイル／名前空間内のパーティションの一例を示す。この例では、「プロジェクト」パイプライン１１４０が、付加動作の一環として宣言された。プロジェクトパイプライン１１４０は、５つの論理パーティションを備える。

図に示すように、新しいパイプラインの各パーティションは、ＤＳ１およびＤＳ２のパイプライン空間内の既存のパーティションに対応する。この例において、プロジェクトパイプラインのパーティション０は、ＤＳ１空間のパーティション０に対応する。プロジェクトパーティション１は、ＤＳ１空間のパーティション１に対応する。

ＤＳ２はＤＳ１の下に付加されるので、ＤＳ２パイプライン空間のパーティション０は、新しいプロジェクトパイプライン空間のパーティション２に対応する。プロジェクトパイプライン空間のパーティション３は、ＤＳ２パイプライン空間のパーティション１に対応する。プロジェクトパイプライン空間のパーティション４は、ＤＳ２パイプライン空間のパーティション２に対応する。

図に示すように、ＤＳ１パイプライン空間およびＤＳ２パイプライン空間のパーティションは、プロジェクトパイプラインの新しい空間の下で効果的に再分割されている。再分割の一環として、ＤＳ１およびＤＳ２からのパーティションは、ＤＳ２の行がＤＳ１の行に続くことを表すように再番号付けされる（例えば、付加テーブルのＤＳ２パーティションは、アンカーテーブルのＤＳ１パーティションに続くように番号付けされる）。

図に示すように、各新しいパーティションは、それに対応するＤＳ１またはＤＳ２パーティションからデータトラバーサルプログラムを継承する。例えば、参照テーブルおよび参照スタックが継承される。移動または変更されるデータはないので、参照スタックは、既存ファイルセットへの参照を含み、構造は同じままである（例えば、ここで、付加動作処理であるため、参照スタックの上に新しいエントリは置かれない）。１つの変更点は、参照スタックによって参照されたファイルセットに見られる列の名前付けにある。列名は、元々はＤＳ１およびＤＳ２内でのそれらの元々の名前で呼ばれたが、互いにマッピングされた付加された列のための新しい共通の名前を示すよう名前を変更される。いくつかの実施形態において、元々の列名と、それらが参照する対応する新しい名前との間のマッピングの記録／ブックキーピングが維持される。この例において、ＤＳ２の列Ｃ０１は、ＤＳ１の列Ｃ００に付加される。両方の列は、共通の列名「Ｃ０」にマッピングされる。同様に、ＤＳ２の列Ｃ１１は、ＤＳ１の列Ｃ１０に付加される。両方の列は、共通の列名「Ｃ１」にマッピングされる。

上記の例において、パーティションは、新しく宣言されたパイプラインの下に追加された。いくつかの実施形態において、付加テーブルのパーティションは、アンカーテーブルのパイプラインへ引き込まれ／組み込まれ、それに応じて再番号付けされる（すなわち、ＤＳ２のパーティションは、ＤＳ１によって消費されるように再分割される）。例えば、ＤＳ２のパーティションは、再割り当てされてＤＳ１パイプラインに組み込まれ、ＤＳ１パーティションの最後のパーティション番号に連続して続くように番号付けされる。いくつかの実施形態において、付加内で互いにマッピングされた列の新しい名前を生成するのではなく、付加テーブル内の列は、アンカーテーブル内の対応する列の名前を引き継ぐ（例えば、ＤＳ２の列Ｃ０１は、ＤＳ１パイプラインに組み込まれた時に、ＤＳ１の列Ｃ００の名前を引き継ぐ）。

新しいパイプライン内のこの新しい付加されたデータセットからのデータは、上述したのと同じ技術を用いて読み出される。この例において、プロジェクト空間の各パーティションのデータトラバーサルプログラムは、付加の結果の順序付けられた一部を取得するために実行される。付加の結果全体に到達するために、複数の一部が組み合わせられ、対応するパーティション番号によって順序付けられる。図に示すように、結果全体を組み立てる時、データ値が、２つの異なるデータセットのために元々書き込まれたファイルセット（例えば、図１１Ｃに示したファイルセット）から引き出される。付加の結果は、新しい列名「Ｃ０」および「Ｃ１」を有するが、ファイルセットのルックアップを実行する時、ルックアップを実行して適切な列の値を取得するために、ＤＳ１およびＤＳ２における元々の名前に対する新しい列名について維持されたマッピングが用いられる。

したがって、付加動作において、上述の処理は、付加されたデータセットの仮想表現を作成し、ここで、付加されたデータセットのパーティション（および対応するデータトラバーサルプログラム）は、完全に単一のデータセットとして処理されるように、現在では単一の論理空間下に置かれている。さらなる動作（例えば、順序付けられたデータ準備動作のセット）が、新しい論理単一データセットに実行されてよく、その一例を以下に記載する。

付加の例−付加の前のＤＳ２．Ｃ１１への小文字化
上記の例に示されるように、別個のパイプラインが、元々は、ＤＳ１およびＤＳ２に対して宣言されていた。以下の例では、付加を実行する前に、小文字化動作がＤＳ２の列Ｃ１１に実行されたが、インポート後にＤＳ１にはさらなる工程は実行されなかったと仮定する。

図１１Ｆの例では、インポート動作の時点でのＤＳ１パイプライン空間のパーティションおよび対応するデータトラバーサルプログラムの状態が示されている。ＤＳ１をインポートした時に書き込まれた対応するファイルセットは示されていない。

図１１Ｆの例では、さらに、ＤＳ２をインポートした後にＤＳ２の列Ｃ１１に小文字化を実行した結果として、ＤＳ２パイプライン空間のパーティションおよび対応するデータトラバーサルプログラムの状態が示されている。小文字化動作により書き込まれたファイルセットも示されている。ＤＳ２をインポートした時に書き込まれたファイルセットは示されていない。いくつかの実施形態において、図のデータトラバーサルプログラムおよびファイルセットは、図７Ａ〜図８Ｂを参照して説明したのと同様の技術を用いて生成される。

ＤＳ１およびＤＳ２（付加の前のそれらの仮想表現が図１１Ｇに示されている（図１１Ｆに示したそれらと同等の表現に対応する））は、ＤＳ１およびＤＳ２パイプライン空間内のパーティションを新しい第３「プロジェクト」パイプラインに、上述のように、再マッピング／再分割することによって、仮想的に付加される。付加動作の結果の仮想表現は、図１１Ｈに示されている。参照スタック内の列の再命名も示されており、データ値が書き込まれたり移動されたりしていないので、参照スタックの構造も変化していない。

この例に示すように、ＤＳ１パイプラインのパーティション０〜１が、新しいプロジェクトパイプラインのそれぞれパーティション０〜１へ再マッピングされた。ＤＳ２パイプラインのパーティション０〜２は、新しいプロジェクトパイプラインのそれぞれパーティション２〜４へ再マッピングされた。追加の小文字化動作が、付加の前にＤＳ２の列Ｃ１１に実行されたので、パーティション２〜４の参照スタックは、プロジェクトパーティション０〜１よりも多いエントリを有する。さらに、パーティション２〜４のための参照テーブルは、パーティション０〜１のための参照テーブルと比較して、さらに列を含む。したがって、同じパイプライン内のパーティションが、異なる参照スタックおよび参照テーブルを有する。これは、付加される前のデータセットの履歴を反映している。

付加の結果を読み込む時、プロジェクトパイプライン空間のパーティションが、（例えば、図７Ｂおよび図８Ｂを参照して）上述したのと同じ技術を用いて読み出される。例えば、（単一の（仮想）データセットに対する動作を表す）プロジェクトパイプラインのパーティションがアクセスされる。パーティションのためのデータトラバーサルプログラムが取得される。ルックアップするための参照、ファイルハンドル、および、列が、データトラバーサルプログラムから取得される。これらのアイテムは、ファイルセットをロケートするためのファイルハッシュ（または任意の他のファイル名表現）を決定するために一緒に用いられる。ルックアップが、指定された列の値を取得するために、見つかったファイルセット上で実行される。そうすることにより、パーティションのデータトラバーサルプログラムによって表現された累積結果の一部が取得される。様々なパーティションから取得された累積結果のサブセットは、パーティション順に従って組み合わせられる。

付加の例−（付加後の）Ｐｒｏｊ．Ｃ１への小文字化
図１１Ｆ〜Ｈの上記の例では、ＤＳ２がＤＳ１に付加される前に、ＤＳ２の列Ｃ１１への小文字化動作がＤＳ２に実行された。以下は、図１１Ａ〜図１１Ｅの例に続く一例であり、その例において、ＤＳ１およびＤＳ２は、各々がインポートされた直後に付加された。この例では、ＤＳ１およびＤＳ２が付加された後に、新しいプロジェクトの列Ｃ１への小文字化動作が実行される。

プロジェクトの列Ｃ１への小文字化を実行した結果の表現が、図１１Ｉに示されている。この例では、プロジェクトのパーティションすべてが、小文字化動作の影響を受けており、したがって、（参照テーブルおよび参照スタックを含む）データトラバーサルプログラムすべてが、小文字化動作の結果を反映するために、（図１１Ｅの仮想表現の状態から）更新された。

キャッシュフィンガープリントの例
例えば、図１１Ｆ〜Ｈに示したように、第１ユーザが、付加の前にＤＳ２．Ｃ１１に小文字化を以前に実行し、その結果を保存／キャッシュしたと仮定する。例えば、キャッシュされた表現に添付されたシグネチャ／フィンガープリントが、キャッシュされた結果につながる実行されたステップを示唆すると仮定する（例えば、シグネチャは、動作のハッシュ、または、キャッシュされた結果につながる動作の文字列表現の連結、などである）。いくつかの実施形態において、フィンガープリントは、図１１Ｊに示すツリー構造１１５０を生成するために用いることができ、ツリー構造１１５０は、インポートＤＳ２ステップの後にＤＳ２の列Ｃ１１への小文字化が続くパイプラインを示す。

翌日、第２ユーザが、ステップエディタインターフェースを用いて、ＤＳ２をＤＳ１に付加した後に、結果として得られるＣ１列に小文字化を実行したいことを指示すると仮定する。なお、それらの動作は、図１１Ｅに関して説明した表現の生成をもたらした順序付けられたデータ準備動作のセットである。

２ユーザによって指定された動作の順序および異なる順序の動作の結果は異なるが、第２ユーザによって指定された第２セットの順序付けられた動作を実行する前に、以前にキャッシュされた表現が結果の少なくとも一部または全部を提供するために利用可能か否かを判定できる。

以下は、シグネチャ／フィンガープリントを用いて、既存のキャッシュされた表現が再利用できるか否かを判定する一例である。例えば、第２ユーザによって指定された第２セットの順序付けられた動作が、図１１Ｋのツリー１１６０に対応するシグネチャを導出するために用いられると仮定する。以前にキャッシュされた表現のツリー表現１１５０も取得される。それらのツリーは、グラフまたは任意の部分グラフ／パスが２つの間で一致するか否かを判定するために比較できる。一致は、第２セットの順序付けられた動作の或る部分のキャッシュされた表現が存在することを示唆する。

この例において、１１６０および１１５０間には直接的な一致は見られない。いくつかの実施形態において、ツリー１１６０は、後に１１５０との比較もされうる等価なツリーを決定するために、さらに操作されうる。例えば、オペレータプッシュダウンが、１１６０に実行されうる。この例において、１１６０の小文字化動作は、ツリー１１７０を生み出すために、付加の下にプッシュダウンされる。ツリー１１６０および１１７０は、ＤＳ１およびＤＳ２の付加の結果として得られたデータセットの列Ｃ１に小文字化を実行することが、付加の実行前に最初にＤＳ１のＣ１０およびＤＳ２のＣ１１に小文字化動作を実行したのと同じである点で、機能的／意味的に等価である。

ツリー１１７０および１１５０を比較すると、１１７０の部分グラフ１１７２が１１５０と一致すると判定される。例えば、部分１１７２のシグネチャ（例えば、部分１１７２における動作のハッシュ）が、キャッシュされた結果１１５０のシグネチャと一致する（例えば、等価のハッシュが特定された）。

次いで、ツリー１１５０を表すシグネチャに関連するキャッシュされた結果が取得されうる。この例において、シグネチャ１１５０に関連するキャッシュされた結果は、ＤＳ２の列Ｃ１１内の値に小文字化動作を実行することに関連する。次いで、キャッシュされた結果は、第２セットの順序付けられた動作を実行するための計算量を削減するために利用できる。例えば、ＤＳ２の列Ｃ１１内の値に小文字化動作を実行することに関連するキャッシュされた結果が存在するので、ＤＳ１のＣ１０内のすべての値およびＤＳ２のＣ１１内の値の小文字化を計算するのではなく、ＤＳ１の列Ｃ１０内の値にのみ、小文字化動作を実行すればよい。これは、実行される必要のある書き込みの量を削減する。次いで、ＤＳ１のＣ１０への小文字化動作の結果は、第２ユーザが望む結果を取得するために、キャッシュされた結果に付加されうる。

結合
結合動作に関連する処理の実施形態の一例を以下に記載する。完全外部結合が以下の例に示されているが、本明細書に記載の技術は、任意のその他のタイプの結合（例えば、デカルト結合）を実行するためにそれに従って適合できる。

図１２Ａは、結合されるデータセットの一例を示す。この例では、ユーザが、ＤＳ１をアンカー／駆動テーブルとし、ＤＳ２をルックアップテーブルとして（すなわち、ＤＳ２がＤＳ１に結合される）、列Ｊ１およびＪ２についてデータセットＤＳ１（１２０２）およびデータセットＤＳ２（１２０４）の完全外部結合を実行したいと仮定する。その結果は、結合されたテーブル１２０６になる。結合動作は、例えば、ステップエディタユーザインターフェース（その例については後述する）を介してユーザによって指定されうる。

図１２Ｂは、インポートされたデータの一例を示す。図１２Ａの例に続き、データセットＤＳ１およびＤＳ２は、１２１０および１２２０に示すように、それぞれのＤＳ１およびＤＳ２パイプライン空間に分割されインポートされた。各パーティションによって書き込まれた対応するファイルセットも示されている。パーティションのための（参照テーブルおよび参照スタックを含む）データトラバーサルプログラムの（インポート動作時点の）現在の状態も示されている。

この例では、図に示すように、ＤＳ１は、２つのパーティション（パーティション０およびパーティション１）に分割されている。ＤＳ１パイプライン１２１０のパーティション０は、参照テーブル１２１２および対応する参照スタック１２１４を備える。参照テーブル１２１２および対応する参照スタック１２１４を備えたデータトラバーサルプログラムが、ＤＳ１の上から２行を表す。ＤＳ１パイプライン１２１０のパーティション１は、参照テーブル１２１６および対応する参照スタック１２１８を備える。参照テーブル１２１６および対応する参照スタック１２１８を備えたデータトラバーサルプログラムが、ＤＳ１の下から２行を表す。

この例では、図に示すように、ＤＳ２は、２つのパーティション（パーティション０およびパーティション１）に分割されている。ＤＳ２パイプライン１２２０のパーティション０は、参照テーブル１２２２および対応する参照スタック１２２４を備える。参照テーブル１２２２および対応する参照スタック１２２４を備えたデータトラバーサルプログラムが、ＤＳ２の一番上の行を表す。ＤＳ２パイプライン１２２０のパーティション１は、参照テーブル１２２６および対応する参照スタック１２２８を備える。参照テーブル１２２６および対応する参照スタック１２２８を備えたデータトラバーサルプログラムが、ＤＳ２の下から３行を表す。

付加の例のように、新しいパイプラインが、結合の組み合わせの結果を表すために宣言される。完全外部結合の例において、新しいパイプライン空間（本明細書では「プロジェクト」パイプラインと呼ぶ）は、ＤＳ１およびＤＳ２パイプライン空間にわたるパーティションの総数と同じ数のパーティションを含むことになる。完全外部結合に至るための処理の実施形態の一例を、図１２Ｃ〜Ｅに関して以下に記載する。

図１２Ｃ〜Ｅは、完全外部結合を実行するための処理の実施形態の一例を示す。いくつかの実施形態において、完全外部結合は、左外部結合および右アンチ結合を実行することによって実行され、それらの結果が、完全外部結合結果の仮想表現を生成するために付加される。以下に記載の９つのステップにおいて、最初の４つのステップは、左外部結合を実行するために用いられる。ステップ５〜８は、右アンチ結合を実行するために用いられる。ステップ９は、完全外部結合の表現を生み出すために、左結合および右結合の結果を組み合わせるために用いられる。これらのステップについて、以下に説明する。

左外部結合
図１２Ｃは、左外部結合を実行するための処理の実施形態の一例を示す。いくつかの実施形態において、左外部結合の結果は、図１２Ｂに示したＤＳ１パイプライン１２１０のパーティション０および１のデータトラバーサルプログラム（すなわち、参照テーブルおよび参照スタック）を変更／修正することによって決定（および表現）される。ステップ１〜４で実行される処理は、データトラバーサルプログラムの各々に別個に実行されるが、ここでは例示ために一緒に図示されている。

ステップ１（１２４０）で、ＤＳ１のすべての行が取得される。ＤＳ１の行は、ＤＳ１空間のパーティションの参照テーブル（例えば、図１２ＢのＤＳ１パイプライン空間１２１０内のパーティション０および１の参照テーブル）に含まれる参照によって表される。いくつかの実施形態において、ＤＳ１のすべての行を取得することは、ＤＳ１のパーティションの各々のための現在の参照テーブルを取得することを含む。

例えば、図１２ＢのＤＳ１パイプライン空間１２１０のパーティション０の参照テーブル１２１２が取得され、二重線１２４２より上に示されている。同様に、ＤＳ１パイプライン空間１２１０のパーティション１の参照テーブル１２１６が取得され、線１２４２より下に示されている。

ステップ２（１２４４）では、ステップ１で取得された行／参照に対応するＪ１の値の列が追加される。例えば、１つの列が、参照テーブル１２１２および１２１６の各々の右に追加され、対応するＪ１の値で埋められ、結果として、それぞれ、テーブル１２４６および１２４８が得られる。いくつかの実施形態において、Ｊ１の値は、図１２Ｂに示したように、ＤＳ１パイプライン空間１２１０のパーティション０および１に示されたデータトラバーサルプログラムを実行することによって取得される。

ステップ３（１２５０）で、Ｊ１の各値のためのＤＳ２参照が示されている。このステップにおいて、ＤＳ１の列Ｊ１内の値と一致する値をＪ２列に含むＤＳ２の行（それらに対応する参照によって表される）が見いだされる。特定された行は、図１２ＢのＤＳ２パイプライン空間１２２０のパーティションの参照テーブルに示されるように、参照によって表される。

このステップにおいて、それぞれのＪ１およびＪ２の値において同じ値を共有するＤＳ１およびＤＳ２内の行が特定され、一緒にマッピングされる。これらの行は、結合された行を作成するために、水平に連結される。この例において、マッピングは、それぞれ、テーブル１２５２および１２５４を生み出すために、部分的には、テーブル１２４６および１２４８の右に追加の列（または、ＤＳ２内の行が複数の参照を用いて表される場合には、複数の列）を追加することによって実行される。列は、上述のように特定された適切なＤＳ２参照で埋められる。

１２５４に示すように、Ｊ２列が値「Ｃ」を有するＤＳ２には行が存在しない（すなわち、そのＪ１列の値「Ｃ」に関連するＤＳ１のパーティション１内の参照テーブル１２１６の最上行は、ＤＳ２内に一致する相手を持たない）。この例において、一致する行がないことは、
「

」シンボルで表されている（１２５６）。

ステップ４（１２５８）で、Ｊ１値列が、テーブル１２５２および１２５４から削除される。テーブル１２５２および１２５４の各々について、これは、ＤＳ１参照の列および対応する／一致するＤＳ２参照の列のみを残す。列は、連結される。この例において、ＤＳ２値を含む列は、ＤＳ１値を含む列の左に連結される。

したがって、テーブル１２５２は、テーブル１２６０に変形され、テーブル１２６０は、ＤＳ１パイプラインのパーティション０のための新しい更新されたバージョンの参照テーブルとして保存される。同様に、テーブル１２５４は、テーブル１２６２に変形され、テーブル１２６２は、ＤＳ１パイプラインのパーティション１のための新しい更新されたバージョンの参照テーブルとして保存される。ＤＳ１パイプラインのパーティション１および０のための参照テーブルの各々が、（上記のステップ１〜３で決定された左外部結合条件に従って一致する）対応するＤＳ２参照の新しい列を含むように更新されたので、対応する参照スタックも更新される。この例において、ＤＳ２の参照スタック（図１２Ｂの１２２４および１２２８に示した）は、それぞれ、図１２Ｂの参照スタック１２１４および１２１８の上部に連結されて、更新された三章スタック１２６４および１２６６を生成する。

したがって、ＤＳ１パイプラインのパーティション０および１のデータトラバーサルプログラムは、左外部結合を実行した結果を表すように変更されている。後に詳述するように、左外部結合は、完全外部結合を実行する際の中間工程であり、ＤＳ１の更新されたパーティション０および１は、付加を介して新しいプロジェクトパイプラインに分割し直される。

右アンチ結合

図１２Ｄは、完全外部結合の右アンチ結合を実行するための処理の実施形態の一例を示す。いくつかの実施形態において、図１２Ｄの処理は、１２Ｃの処理から継続する。いくつかの実施形態において、右アンチ結合の結果は、図１２Ｂに示したＤＳ２パイプライン１２２０のパーティション０および１のデータトラバーサルプログラム（すなわち、参照テーブルおよび参照スタック）を変更／修正することによって決定（および表現）される。ステップ５〜８で実行される処理は、データトラバーサルプログラムの各々に別個に実行されるが、ここでは例示ために一緒に図示されている。

ステップ５（１２６８）で、ＤＳ２のすべての行が取得される。ＤＳ２の行は、ＤＳ２空間のパーティションの参照テーブル（例えば、図１２ＢのＤＳ２パイプライン空間１２２０内のパーティション０および１の参照テーブル）に含まれる参照によって表される。いくつかの実施形態において、ＤＳ２のすべての行を取得することは、ＤＳ２のパーティションの各々のための現在の参照テーブルを取得することを含む。

例えば、図１２ＢのＤＳ２パイプライン空間１２２０のパーティション０の参照テーブル１２２２が取得され、二重線１２７０より上に示されている。同様に、ＤＳ２パイプライン空間１２２０のパーティション１の参照テーブル１２２６が取得され、線１２７０より下に示されている。

ステップ６（１２７２）では、ステップ５で取得されたＤＳ２の行／参照の列に対応するＪ２の値の列が追加される。例えば、１つの列が、参照テーブル１２２２および１２２６の各々の右に追加され、対応するＪ２の値で埋められ、結果として、それぞれ、テーブル１２７４および１２７６が得られる。いくつかの実施形態において、Ｊ２の値は、図１２Ｂに示したように、ＤＳ２パイプライン空間１２２０のパーティション０および１に示されたデータトラバーサルプログラムを実行することによって取得される。

ステップ７（１２７８）で、テーブル１２７４および１２７６は、ＤＳ２のＪ２列の値に一致するＪ１列の値を有する対応するＤＳ１の行（参照を用いて表される）が存在しないＤＳ２の行を特定するためにフィルタリングされる。この例において、テーブル１２７４内には参照が残っておらず、結果として、空のテーブル１２８０になる。テーブル１２７６の１行だけが残り、結果として、テーブル１２８２になる。

ステップ８（１２８４）で、テーブル１２８０および１２８２のＪ２値列が除去され、ステップ７のフィルタリング動作の結果として（存在する場合）残ったＤＳ２参照だけが各テーブルに残される。したがって、テーブル１２８０は、空のテーブル１２８６に変形され、テーブル１２８６は、（「

」シンボルで表される）ＤＳ２パイプラインのパーティション０のための新しい更新されたバージョンの参照テーブルとして保存される。同様に、テーブル１２８２は、テーブル１２８８に変形され、テーブル１２８８は、ＤＳ２パイプラインのパーティション１のための新しい更新されたバージョンの参照テーブルとして保存される。この例において、ＤＳ２のパーティション０および１のための新しく更新された参照は、おれでもＤＳ２参照を取得し、それらのパーティションのための参照スタックは、変更されない（例えば、図１２Ｂの１２２４および１２２８に示したのと同じである）。

したがって、ＤＳ２パイプラインのパーティション０および１のデータトラバーサルプログラムは、右アンチ結合を実行した結果を表すように変更されている。後に詳述するように、右アンチ結合は、完全外部結合を実行する際の中間工程であり、ＤＳ２の更新されたパーティション０および１は、新しいプロジェクトパイプラインに分割し直される。

完全外部結合の結果の表現の決定
図１２Ｅは、完全外部結合を実行するための処理の実施形態の一例を示す。いくつかの実施形態において、図１２Ｅの処理は、１２Ｄの処理から継続する。

ステップ９（１２９０）では、上述のステップ４およびステップ８の結果が一緒に付加される。いくつかの実施形態において、付加は、図１１Ａ〜Ｉに関して記載したのと同様に実行される。例えば、ＤＳ１およびＤＳ２のパーティションは、新たに宣言されたパイプライン（「プロジェクト」パイプラインと呼ぶ）に分割し直され、新たなパイプラインは、新たなパイプライン内での順番にパーティションを再番号付けすることも含む。

この例において、ＤＳ１は駆動テーブルであるため、ステップ４の時点のＤＳ１のパーティション０は、新しいプロジェクトパイプラインのパーティション０として分割し直され、図１２Ｃに示したように、参照テーブル１２６０および対応する参照スタック１２６４を備えたデータトラバーサルプログラムを含む。ステップ４の時点のＤＳ１のパーティション１は、新しいプロジェクトパイプラインのパーティション１として分割し直され、図１２Ｃに示したように、参照テーブル１２６２および対応する参照スタック１２６６を備える。

この例において、ＤＳ２はルックアップテーブルであるため、ステップ８の時点のＤＳ２のパーティション０は、新しいプロジェクトパイプラインのパーティション２として分割し直され、図１２Ｄに示したように、参照テーブル１２８６および対応する参照スタックを備えたデータトラバーサルプログラムを含む。ステップ８の時点のＤＳ２のパーティション１は、新しいプロジェクトパイプラインのパーティション３として分割し直され、図１２Ｄに示したように、参照テーブル１２８８および対応する参照スタックを備えたデータトラバーサルプログラムを含む。

上記において、図１２Ｃ（左外部結合）および１２Ｄ（右アンチ結合）の処理は、順に説明された。いくつかの実施形態において、図１２Ｃおよび図１２Ｄの処理は、並列で実行される。次いで、左外部結合および右アンチ結合の結果は、一緒に付加され、図１２Ｅに関して上述したように、完全外部結合結果の表現を決定する。

図１２Ｅに示した完全外部結合の結果の仮想表現の例に示すように、プロジェクトパイプラインのパーティション０および１のための参照スタックは各々、交わりを持たないソースからのファイルセットおよびステップへの参照を含む。例えば、プロジェクトパーティション０および１のための参照スタックは各々、ＤＳ１パイプラインおよびＤＳ２パイプラインの両方に対して生成されたファイルセットのためのハンドルを含む。

上述のように、本明細書に記載の技術を用いれば、１または複数の入力データセットに対する順序付けられた動作のセットが、データセットに対する動作の結果の仮想表現をもたらす。仮想表現は、データトラバーサルプログラムを含み、データトラバーサルプログラムは、実行されると、結果の実際のデータ値を出力する。

さらなる結合の例−結合前のＤＳ２のＪ２への小文字化
以下の例では、ユーザが、ＤＳ１と結合される前にＤＳ２の列Ｊ２に小文字化を実行するよう決定すると仮定する。結合前のＤＳ１およびＤＳ２パイプライン空間のパーティションのデータトラバーサルプログラムの状態は、図１２Ｆに示されている。

この例において、ＤＳ２内には、ＤＳ１の行内のＪ１の値に一致するＪ２の値を持つ行がない。図１２Ｃ〜Ｅに関して上述したステップ１〜９を実行することにより、完全外部結合の結果は、図１２Ｇに示すように表現される。

上に示したように、データトラバーサルプログラムなどの表現の利用など、本明細書に記載の技術は、様々な利点を有する。一例は、格納効率を高めることであり、ここで、動作の結果を表すために必要な記憶量が削減される。これは、例えば、データセットの実際の値ではなく、結果のコンパクトなデータトラバーサルプログラム表現を維持することによる。別の例として、動作によって変更されたデータのみが書き込まれるので、処理速度の効率も向上される。さらに、実際のデータ自体ではなく、データを表現する参照に動作を実行することにより、参照がデータ自体よりもよりコンパクトである（例えば、データの行を表す参照のセットは、その行を構成するデータ値よりも占める空間が小さい）ことから、さらなる効率化が実現されうる。さらに、上述のようなキャッシングと、後述のようなキャッシュの識別とを実行することにより、冗長性を避けることができ、ここで、例えば、既存のキャッシュされた結果が反復計算を避けるために利用されうる。

図１３は、変換結果をキャッシュするための処理の一実施形態を示すフローチャートである。いくつかの実施形態において、処理１３００は、図２のデータ変換エンジン２１０およびキャッシュエンジン２１２によって実行される。処理は、順序付けられたデータ準備動作のセットが１または複数のデータセットに実行された結果を表すデータトラバーサルプログラムが生成される工程１３０２で始まる。いくつかの実施形態において、順序付けられたデータ準備動作のセットは、入力データが通されるパイプラインを形成する。いくつかの実施形態において、データトラバーサルプログラムは、結果を引き出すために１または複数のデータセット内の１または複数の影響を受けた列を集める方法を示す。いくつかの実施形態において、１または複数のデータセットは、アドレス可能なデータセットとして再書き込みされる。例えば、１または複数のデータセットは、上述のように、列ファイルとして再書き込みされ、列ファイルは、ファイルに格納されたセルの列である。いくつかの実施形態において、列ファイルの値は、１または複数のデータセットのソースから取得される。動作が実行されると、列ファイルの新しいバージョンが、動作によって影響（例えば、修正／変更）を受けた列について書き込まれる。いくつかの実施形態において、順序付けられたデータ準備動作のセットは、（例えば、図２のスクリプトジェネレータ２０４によって生成された）スクリプトの形態で受信される。いくつかの実施形態において、スクリプトは、（例えば、ユーザインターフェースエンジン２０２によって提供された）ステップエディタユーザインターフェースを介して受信されたユーザ入力に基づいて生成される。ステップエディタユーザインターフェースは、ユーザが１または複数の入力データセットに実行される順序付けられたデータ準備動作のセットをするためのユーザインターフェースを提供する。

データトラバーサルプログラムは、順序付けられたデータ準備動作のセットを実行した累積的影響を記録する。いくつかの実施形態において、上述のように、データトラバーサルプログラムは、（例えば、参照テーブルに格納された）参照を含む。参照は、順序付けられたデータ準備動作のセット中に起こった行の変換のマッピングへの参照である。いくつかの実施形態において、参照は、結果内に行を記述／規定するために用いられる（例えば、列ファイル内の）データ値を参照する。いくつかの実施形態において、データトラバーサルプログラムは、参照スタックを含む。参照スタックは、順序付けられた動作の記録／履歴と、順序付けられた動作のセットによって変更された列とを含む。いくつかの実施形態において、参照スタックは、実行されたデータ準備動作により書き込まれたデータ値の列ファイルを格納するファイルセットへの参照を含む。

いくつかの実施形態において、データトラバーサルプログラムは、結果を格納するのに必要なよりも少ないストレージ／メモリを必要とする。いくつかの実施形態において、データトラバーサルプログラムは、データセットを移動させることなしに生成される。いくつかの実施形態において、データトラバーサルプログラムは、結果を生成することなしに生成される。

いくつかの実施形態において、データトラバーサルプログラムが順序付けられた動作のセットにわたって生成／更新される方法は、上記の様々なデータ準備動作の例において説明したように、動作依存である。データトラバーサルプログラムを生成および実行するための技術の例については、上記の例で説明されている。

工程１３０４で、結果を表すデータトラバーサルプログラムが格納される。例えば、データトラバーサルプログラムは、キャッシュ層にキャッシュされる。いくつかの実施形態では、データトラバーサルプログラムに関するデータ（参照テーブルなど）が格納される。いくつかの実施形態において、データトラバーサルプログラムを格納／キャッシュするか否かの決定は、様々な要素に基づきうる。例えば、ユーザは、順序付けられた動作のセットにおいて保存ポイントを作成したい場所を（例えば、エディタユーザインターフェースを介して）明示的に指示できる。次いで、その保存ポイントの位置に対応するキャッシュ表現が格納される。いくつかの実施形態において、データトラバーサルプログラムを格納するのではなく、データトラバーサルプログラムはメモリに維持される。

いくつかの実施形態において、表現をキャッシュするか否かの決定は、実行されたデータ動作に基づく。例えば、動作／動作セットの複雑性／計算コストが考慮されうる。一例として、セット全体に影響するソート、フィルタ、または、結合など、コストの掛かる／高価な動作については、結果として得られるデータトラバーサルプログラムは、キャッシュされうる。別の例として、集合的な動作のセットのコストが考慮されてもよい。例えば、大文字化の実行など、個々の動作のコストは高くない場合があるが、その動作を複数回実行すると（例えば、２０列の大文字化を実行すると）、コストが掛かりうる。したがって、スクリプトの内容は、どこでキャッシングを実行すべきかを決定するために評価されうる。

考慮できる要素の別の例は、ユーザが動作を修正する可能性の大きさを含む。例えば、様々なユーザの行動を経時的に観察することにより、スクリプト内でしばしば変更またはスワップアウトされる動作のタイプを特定して学習することができる。

パイプラインの様々なステージで表現をキャッシュすることにより、ユーザは、例えば、パイプラインにおける特定の時点の結果を、その時点までに至る順序付けられた動作のセットを再計算することなしに、見直すことができる。

いくつかの実施形態において、データトラバーサルプログラムは、１または複数の対応するシグネチャのセットと共に格納される。いくつかの実施形態において、１または複数のシグネチャのセットは、実行された順序付けられた動作のセットに基づいて導出される。例えば、各シグネチャは、実行された動作のハッシュ関数（例えば、ＭＤ５、ＳＨＡ−１、または、何らかのその他のシグネチャ生成関数などの暗号学的ハッシュ）を用いて生成され、ここで、動作は、適用された順序を保つように組み合わせられる。シグネチャについては、図１４の処理１４００に関して後に詳述する。

いくつかの実施形態において、結果を表すデータトラバーサルプログラムは、再計算および更新できる。例えば、ユーザがソースデータセットＤＳＸに順序付けられた動作のセットを実行したと仮定する。次の朝、別のユーザがソースデータセットＤＳＸの変更を行う。ソースデータセットＤＳＸが変更された旨の示唆に応答して、データトラバーサルプログラムは、変更されたソースデータセットに順序付けられた動作のセットを再実行することによって更新されることができる（すなわち、新しいキャッシュが、より新しいバージョンのデータを用いて構築され、キャッシュの自動更新を可能にする）。

工程１３０６で、１または複数のデータセットに実行される順序付けられた動作のセットの仕様が受信される。工程１３０８で、結果を表すデータトラバーサルプログラムがアクセスされる。いくつかの実施形態では、結果を表すデータトラバーサルプログラムの格納済みのコピーがアクセスされる。いくつかの実施形態において、データトラバーサルプログラム（またはそのコピー）は、工程１３０６での仕様の受信に応答してアクセスされる。一例として、ユーザは、さらに、データトラバーサルプログラムの生成を引き起こすステップ以外のデータ準備ステップを実行する。ユーザは、生成されたデータトラバーサルプログラムが格納／キャッシュされたパイプライン内のステージに戻りたいと決定する。これは、ユーザが同じセットの順序付けられた動作を実行したいことを示唆する。次いで、キャッシュされたデータトラバーサルプログラムがリトリーブされる。

別の例として、別のユーザが、キャッシュされたデータトラバーサルプログラムを生成するために実行されたのと同じ（または等価な）セットの順序付けられたデータ準備を（例えば、ステップエディタユーザインターフェースを介して）偶然に構成する。シグネチャが、そのセットの順序付けられた動作の受信された仕様から導出される。シグネチャは、キャッシュされたデータトラバーサルプログラムのシグネチャと一致すると決定される。次いで、一致するキャッシュ済みのデータトラバーサルプログラムが取得される。キャッシュされた結果を取得するためのシグネチャの利用に関するさらなる詳細については、図１４の処理１４００に関して記載する。

工程１３１０で、１または複数のデータセット内の１または複数の影響を受けた列は、結果を生成するために、データトラバーサルプログラムに従って集められる。データトラバーサルプログラムを実行する例については、図７Ｂおよび図８Ｂに関して上述した。工程１３１２で、結果が出力される。いくつかの実施形態において、結果を出力する工程は、結果を発酵する工程または別のファイルへエクスポートする工程を含む。いくつかの実施形態において、結果を出力する工程は、結果を表示する工程を含む。いくつかの実施形態では、ＵＩの現在のウィンドウで閲覧可能な結果だけが表示される。例えば、結果が１０００の行を含むが、ＵＩで閲覧可能であるのが３００行だけである場合、それらの３００行だけが、データトラバーサルプログラムを用いて集められる。（潜在的にユーザが結果をスクロールできるように、より多くの行が集められてよい）。いくつかの実施形態では、ユーザに見える行が、実行される計算の量を決定する。例えば、全データにデータ準備動作の実行するのではなく、動作は、ユーザに見える行にのみ実行される。一例として、どの行がユーザにとって可視であるか（例えば、どの行がユーザインターフェースで見られるのか）についての決定がなされる。データ準備動作は、ユーザが現在見ることのできる行を含む（参照する）パーティションにのみ実行される。これは、ユーザの望む結果を提供しつつ、計算負荷の量を削減する。

いくつかの実施形態において、上述のように、処理１３００は、分散型計算環境（例えば、Ｓｐａｒｋ分散型計算プラットフォーム）の文脈で実行され、ここで、処理される（データ準備動作のパイプライン／順序付けられたセットを通して変形される）１または複数のデータセットは、（例えば、上述のパイプラインエグゼキュータによって）処理されるように（例えば、図５に記載の処理５００を用いて）パーティションに分割される。

いくつかの実施形態において、各パーティションは、独自のデータトラバーサルプログラムを含み、データトラバーサルプログラムは、実行されると、１または複数のデータセットに順序付けられたデータ準備動作のセットを適用した全体結果の一部を提供する。

データトラバーサルプログラムを用いてかかる分散型計算プラットフォーム内で結果を集めるために工程１３１０で実行された処理の実施形態の一例は、以下の通りである。パイプライン内の或るステージでの累積結果の一部が、パーティションにアクセスすることによって取得される。パーティションのためのデータトラバーサルプログラムが取得および実行される。結果の一部の行を表す参照のセットが、データトラバーサルプログラムの参照テーブルから取得される。各参照は、パーティション番号および行識別子を特定する座標を含む。座標は、以前に書き込まれたファイルセットを特定してアクセスするために、参照スタックのエントリと併せて用いられる。ファイルセットは、動作を実行した結果として変更された列のセットを含む。行識別子は、ファイルセットに書き込まれた列の指定された一部において行を特定するために用いられる。列の指定された一部に対するその行内の値が取得される。ルックアップされる列が、参照スタックエントリ内で指定される。したがって、１または複数のデータセット内の１または複数の影響を受けた列が、データトラバーサルプログラムに従って集められる。

パイプラインのそのステージ時点での全体結果は、（例えば、上述のように、パイプラインマスタにより）結果の異なる部分を集めて並べることによって決定され、ここで、パーティションから取得された結果の様々な部分は、特定の順序に（例えば、上述のように、パーティション順に）構造化される。

結果の異なる部分の位置の知識は、パイプラインマスタによって管理されうる。これは、出力の提供時に最適化を実行するために利用できる。例えば、ＵＩでユーザにどの結果ウィンドウを提供するのかを決定する時に（例えば、結果をスクロールさせている時に）、全体結果におけるユーザの現在位置に対応する結果の部分のみが、それらに対応するパーティションから取得される。

図１４は、キャッシュ再利用のための処理の一実施形態を示すフローチャートである。いくつかの実施形態において、処理１４００は、図２のデータ変換エンジン２１０およびキャッシュエンジン２１２によって実行される。その処理は、第の順序付けられたデータ準備動作のセットが複数の変換結果を生成するために１または複数のデータセットに実行される工程１４０２で始まる。いくつかの実施形態において、データ準備動作は、入力データを変換／変化させる動作である。いくつかの実施形態において、データは、順序付けされた動作のセットの実行時に動的にアクセス可能であり、ここで、データは、必ずしも格納されておらず、必要に応じてオンザフライで計算されてもよい。これは、固定された既知の位置に格納されたデータに対する動作と対照的である。さらに、第１の順序付けられた動作のセットは、入力が予めインデックス化および分割されている利点なしに実行される。様々な実施形態において、データ準備動作は、クラスタリング、結合、付加、ソート、大文字化、小文字化、フィルタリング、重複排除、グループ分け、列の追加または除去、行の追加または除去、ピボッティング、デピボッティング、順序依存の動作などを含む。いくつかの実施形態において、複数の変換結果は、上記の例および図１３の処理１３００において記載したものなど、データトラバーサルプログラムを含む。

工程１４０４で、複数の変換結果の内の１または複数、ならびに、１または複数の対応する動作シグネチャがキャッシュされる。いくつかの実施形態において、キャッシュされる動作シグネチャは、対応する結果を生成した順序付けられた動作の一部に少なくとも部分的に基づいて導出される。シグネチャの一例は、順序付けられた動作の一部のハッシュである。いくつかの実施形態において、キャッシュされた動作シグネチャは、対応する結果に至るために実行された順序付けられた動作の一部の表現の順序に依存しないグルーピングを含む。例えば、シグネチャは、順序付けられた動作の一部を表す（ハッシュされた）識別子（例えば、シリアル番号、文字列表現など）のグルーピングである。いくつかの実施形態において、グルーピングは、順序に依存しうる。いくつかの実施形態において、動作表現のグルーピングに基づいたシグネチャを有することは、例えば、（例えば、順序付けられた動作の異なるセットで指定された）データ準備動作の異なるグループ間に任意の重複があるか否かを判定するために、動作表現のその他のグルーピングとの集合的な比較を行うことを可能にする。いくつかの実施形態において、キャッシュされる動作シグネチャは、処理されたデータセットへの参照に基づいても導出される。例えば、キャッシュされる動作シグネチャは、処理されるデータセットの識別子および／またはバージョン番号に基づいて生成されてもよい。いくつかの実施形態において、変換結果は、データトラバーサルプログラム（上述のものなど）を含む。

工程１４０６で、第２セットの順序付けられた動作の仕様が受信される。例えば、ユーザインターフェースを介して、ユーザは、新たな第２セットの順序付けられた動作を作成するか、または、既存のセットの順序付けられた動作を操作する。工程１４０８で、第２セットの順序付けられた動作に関連する動作シグネチャが決定される。

工程１４１０で、キャッシュ済みの結果の中の１つのキャッシュ済みの結果が、決定された動作シグネチャに少なくとも部分的に基づいて特定される。例えば、いくつかの実施形態において、決定された動作シグネチャは、格納された結果に対応するシグネチャと比較される。例えば、シグネチャに関連する動作表現のグルーピングは、決定された動作シグネチャの動作と、格納された結果に関連する動作との間の任意の重複（例えば、部分的または完全な重複）を決定するために、互いに集合的に比較されうる。

いくつかの実施形態において、シグネチャは、順序付けられた動作のセットのフローを表す図１１Ｊ〜Ｋに示したようなグラフ構造に対応する。異なるシグネチャを比較することは、異なるグラフ構造を比較することを含む。いくつかの実施形態において、比較されたシグネチャのいずれかまたは全部が、一致するかまたは他の形で等価であるか否かが判定される（例えば、サブシグネチャが特定されうる）。いくつかの実施形態において、オペレータプッシュダウン（図１１Ｋに関して上述したものなど）が、一致を見いだすために利用されてよい。いくつかの実施形態において、オペレータプッシュダウンは、機能的（意味的）に等価なシグネチャを生成する。したがって、第２セットの順序付けられた動作の一部に一致する格納された結果が、特定されて利用されうる。

工程１４１２で、キャッシュされた結果が出力される。いくつかの実施形態において、格納された結果が、第２セットの順序付けられた動作を実行した結果と等価である場合、特定された格納済みの結果が直接出力される（例えば、ＵＩに表示されるか、または、発行／エクスポートされる）。いくつかの実施形態において、特定された格納済みの結果が、部分一致であり、所望の最終結果を取得するために利用できる中間結果である場合、結果のその部分は取得されるため、計算の必要はない。これは、第２セットの順序付けられた動作を実行するのに必要な計算の量を削減し、最終結果に到達するために、特定された格納済みの結果を組み込むことができる。

ステップエディタ
図１５Ａ〜Ｅは、データ準備動作のシーケンスを構成すると共に、対応する結果を閲覧するために利用できるステップエディタのユーザインターフェースの実施形態の例である。いくつかの実施形態において、図１５Ａ〜Ｅのユーザインターフェースの例は、図２のフロントエンド２００のユーザインターフェースエンジン２０２によって実施される。

例えば、ユーザが、図１５ＡのステップエディタＵＩ１５００を介して、順序付けられたデータ準備動作のセット１５０２を指定すると仮定する。順序付けられた動作のセットは、１５０４で始まり、ここで、データセット（この例では、「Ｔｒａｎｓａｃｔｉｏｎｓ」と呼ぶ）が指定されている。いくつかの実施形態において、データセットは、上述の技術を用いて分割およびインポートされる。ステップ／アクションが実行される基準を指定するために、順序付けられた動作のセット内のステップを編集できる。例えば、ステップ１５０６では、構成可能なフィルタリング基準に基づいて、行を削除できる。いくつかの実施形態において、指定されたステップは、（例えば、図２のフロントエンド２００のスクリプトジェネレータ２０４を用いて）スクリプトを生成するために用いられる。次いで、スクリプト内で指定された動作は、例えば、図２のパイプラインサーバ２０６および／または図３のパイプラインサーバ３００によって実行される。

１５０８で、特定のステップの時点での結果を見ることができる。この例では、ステップ１５０４〜１５０６を順次実行した結果が示されている。結果は、上述の技術を用いて決定されてよく、例えば、結果を表すデータトラバーサルプログラムが生成される。次いで、データトラバーサルプログラムは、対応する結果を出力するために実行されうる。かかるデータトラバーサルプログラムを利用して、（実際のデータ自体に作用するのではなく）実際のデータセットの中間表現である参照に作用することにより、上述のように結果として得られる計算効率の上昇は、アプリケーション応答時間を改善することができ、ここで、例えば、動作が実行されるのに長時間ユーザが待つ必要なしに、結果がリアルタイムでユーザに提供される。いくつかの実施形態では、ＵＩの部分１５０８に見ることのできる結果のみが、上述のように計算および表示される。１５１０で、特定のステップの時点での結果を発行（例えば、エクスポート）することもできる。

ステップエディタユーザインターフェースは、さらに、順序付けられたステップのセットを行き来する機能を提供する。図１５Ａの例に続いて、ユーザが、図Ｂの３番目のステップ１５１２に戻って、そのステップでのデータを見たいと仮定する。そのステップでの結果が（例えば、対応する保存ポイントで）以前にキャッシュされていた場合、キャッシュされた結果がリトリーブされて、表示領域１５１４に表示されうる。例えば、順序付けられた動作のセットが実行される時に、ステップ１５１２の時点での結果が、ユーザによって（例えば、パイプラインのそのステージに対応する「保存」ボタンを押すことにより）保存されるか、または、（例えば、上述のような様々なコスト関数および基準に基づいてパイプラインサーバ３００などのパイプラインサーバによって）自動的に保存されうる。

いくつかの実施形態において、そのステップのための保存ポイントがなかった場合、利用できる任意の既存のキャッシュされた結果があるか否かが判定される。例えば、上述のように、動作シグネチャ（例えば、ハッシュ）が、対象となる現在のステップのセットに対して生成され、キャッシュ済みの結果に関連するシグネチャと比較されうる。一致が見られる場合、一致するキャッシュ済みの結果に到達するための計算を実行する必要がなくなるように、そのキャッシュ済みの結果が取得されうる。いくつかの実施形態では、最終結果を決定する途中の中間結果であるキャッシュされた結果を特定する一致が利用されてもよい。例えば、中間結果を再計算する必要がないため、所望の結果に到達するのに必要な計算の総量が削減される。一致が見いだされない場合、現在のステップのセットを実行して、所望の結果に到達することができる。

ユーザは、（例えば、以前に後退した後にパイプラインの或るポイントに戻るために）ステップを通して前進することもできる。上述したのと同様に、前方の結果が保存／キャッシュされている場合、それがリトリーブされ、出力として提供されうる。キャッシュされた結果が存在しない場合、結果が、（例えば、新しいデータトラバーサルプログラムを決定することによって）再計算されうる。

いくつかの実施形態において、ステップエディタは、或るステップがある場合およびない場合にデータがどのように見えるのかを知るために、そのステップをミュートする機能を提供する。図１５Ｂの例に続いて、ユーザが、図１５Ｃのインターフェース１５１６を介して、３番目のステップ１５１８（図１５Ｂの３番目のステップ１５１２と同じ）をミュートしたいと示唆したと仮定する。いくつかの実施形態では、新しいスクリプトが、１５１８を含まないステップ１５２０に対して生成される。いくつかの実施形態において、削減されたステップセットの動作は、１または複数の動作シグネチャを生成するために用いられる。生成されたシグネチャは、任意の既存のキャッシュされた表現を利用できるか否かを判定するために用いることができる。利用できない場合、図１５Ｂのステップ１５１２を除いた新しいセットの順序付けられたステップが再計算される。

実施形態の一例において、新しいセットの順序付けられたステップに基づいて生成されたシグネチャは、（１５１８がミュートされた）新しいセットの順序付けられたステップ１５２０のツリー／グラフ表現を作成するために用いられる。これは、キャッシュされた結果のシグネチャから生成されたツリー／グラフと比較される。図１１Ｊ〜Ｋに関して記載されたのと同様の技術を用いれば、利用できる任意の既存のキャッシュされた結果が存在するか否かを判定することができる。例えば、オペレータプッシュダウンは、潜在的な一致を決定する時に利用できる。

次いで、ステップ１５１８をミュートした結果が、１５１９に示すように表示されうる。

いくつかの実施形態において、ステップエディタは、さらに、ステップを削除する機能を提供する。図１５Ｃの例に続いて、ユーザが、ステップ１５１８をミュートしたデータを見た後に、そのステップを除去するよう決定すると仮定する。図１５Ｄのインターフェース１５２２の部分１５２４は、そのステップの除去を反映するように更新される。

いくつかの実施形態において、ステップエディタは、さらに、順序付けられた動作のセットへの変更を保存する機能を提供する。例えば、パイプラインへの変更がなされると、パイプラインの各バージョンが、処理されるプロジェクトの異なるバージョンとして保存されうる。例えば、プロジェクトの異なるバージョンが、図１５Ｅの１５２６に示されている。この例において、ユーザは、バージョン１５２８を見ようと選択した。プロジェクトのバージョン１５２８に対応するパイプラインは、１５３０に示されている。この例において、バージョン１５２８は、図１５Ｃの時点でのプロジェクトの状態を保存することによって維持されたものであり、ここで、３番目のステップはミュートされている。プロジェクトのバージョン１５２８の結果は、１５３２に示されている。

図１６は、データ準備にステップエディタを用いるための処理の一実施形態を示すフローチャートである。いくつかの実施形態において、処理１６００は、図２のパイプラインサーバ２０６によって実行される。処理は、データセットに対する順序付けられたデータ準備動作のセットの少なくとも一部に関するユーザ入力の示唆が受信される工程１６０２で始まる。例えば、上述したようなユーザ入力（例えば、ステップのミュート、ステップの削除、順序付けられたデータ準備動作のセット内での後退／前進、など）が受信される。いくつかの実施形態において、ユーザ入力は、（例えば、ユーザインターフェースエンジン２０２を用いて）図２のフロントエンド２００などのフロントエンドによって提供されたユーザインターフェース（例えば、上述のステップエディタユーザインターフェース１５Ａ〜Ｅなど）を介して受信される。いくつかの実施形態において、ユーザ入力は、順序付けられたデータ準備動作のセット内のデータ準備動作の少なくとも一部への変更または選択をもたらす。いくつかの実施形態では、スクリプトが、順序付けられたデータ準備動作のセットおよびユーザ入力に基づいて（例えば、図２のフロントエンド２００のスクリプトジェネレータ２０４を用いて）生成される。いくつかの実施形態において、順序付けられたデータ準備動作のセットは、ユーザ入力値に応答して保存される。例えば、順序付けられたデータ準備動作のセットへの変更が検出された場合、新しいバージョンの順序付けられたデータ準備動作が保存される（例えば、上述のように、バージョンニングが実行される）。

工程１６０４で、順序付けられたデータ準備動作のセットおよびユーザ入力に少なくとも部分的に基づいて、シグネチャが生成される。例えば、ユーザが、（例えば、ステップのミュートまたは削除によって）順序付けられたデータ準備動作のセットを変更した場合、順序付けられたデータ準備動作の変更後のセットに基づいたシグネチャが生成される。別の例として、ユーザが、パイプライン内の或る特定のステージの時点での（例えば、５つの順序付けられたデータ準備動作のセットの内のステップ３の時点での）結果を見るために、順序付けられたデータ準備動作のセット内を移動（例えば、前進または後退）した場合、シグネチャが、ユーザによって示されたポイントまでの順序付けられたデータ準備動作の一部に対して生成されうる。いくつかの実施形態において、シグネチャは、順序付けられたデータ準備動作のセットに関してユーザ入力に応答して生成されたスクリプトに基づいて生成される。

いくつかの実施形態において、シグネチャは、処理中／処理予定のデータセットに基づいて生成される。例えば、データセットへの参照／データセットの表現が、シグネチャを生成するために用いられる。データセットの表現の一例は、データセットの識別子およびバージョン番号である。例えば、異なるデータセットは、異なる識別子に関連付けられうる。同じデータセットの異なるバージョンは、異なるバージョン番号に関連付けられうる。以下で詳述するように、シグネチャは、順序付けられたデータ準備動作のセット、順序付けられたデータ準備動作のセットに関するユーザ入力、および、データセットの表現に基づいてマッチングされうる。例えば、同じセットの順序付けられたデータ準備動作が、２つの異なるデータセットに適用されると、結果として、異なるシグネチャが生成される（同様に、異なる結果となる）。

工程１６０６で、生成されたシグネチャは、順序付けられたデータ準備動作のセット、ユーザ入力、および、データセットへの参照に関連するキャッシュ済みの結果が存在するか否かを判定するために用いられる。いくつかの実施形態において、一致判定およびキャッシュ済みの結果の特定は、図１４の処理１４００に関して記載された技術を用いて実行される。例えば、生成されたシグネチャは、（データトラバーサルプログラムによって表される）キャッシュ済みの結果に対応するシグネチャと比較される。部分一致も特定されうる。同様に、オペレーションプッシュダウンなど、上述の他の技術が、一致を特定するために用いられてもよい。関連するキャッシュ済みの結果が存在する場合、処理は工程１６０８へ続く。関連するキャッシュ済みの結果が存在しない場合、処理は工程１６１０へ続く。

工程１６０８で、キャッシュ済みの結果に関連するマッチングがリトリーブされる。いくつかの実施形態において、キャッシュされた結果は、データトラバーサルプログラムを用いて表現され、データトラバーサルプログラムがリトリーブされる。いくつかの実施形態において、キャッシュ済みの結果が、順序付けられたデータ準備動作のセットにユーザ入力を適用した結果と等価である場合、リトリーブされたキャッシュ済みの結果が、工程１６１２で直接出力される（例えば、ステップエディタＵＩに表示されるか、または、発行／エクスポートされる）。いくつかの実施形態において、特定されたキャッシュ済みの結果が、部分一致であり、所望の最終結果を取得するために利用できる中間結果である場合、結果のその部分は取得されるため、再計算の必要はない。これは、最終結果に到達するのに必要な計算の量を削減する。次いで、最終結果が、キャッシュされた結果に関連するリトリーブされたデータトラバーサルプログラムを用いて計算され、工程１６１２で出力されうる。

工程１６１０で、一致するキャッシュ済みの結果が存在しない場合、順序付けられたデータ準備動作のセットにユーザ入力を適用した結果を表すデータトラバーサルプログラムが、（例えば、図１３の処理１３００に関して上述した処理を用いて）生成される。次いで、生成されたデータトラバーサルプログラムによって表された結果は、工程１６１２で出力として提供される。例えば、結果は、発行されるか、または、（例えば、外部ファイルに）エクスポートされる。

いくつかの実施形態において、上述したようなステップエディタユーザインターフェースを介してユーザに結果が表示される。いくつかの実施形態では、ＵＩの現在のウィンドウで閲覧可能な結果だけが表示される。例えば、結果が１０００の行を含むが、ＵＩで閲覧可能であるのが３００行だけである場合、それらの３００行だけが、データトラバーサルプログラムを用いて集められる。（潜在的にユーザが結果をスクロールできるように、より多くの行が含められてもよい）。

いくつかの実施形態では、ユーザに見える行が、実行される計算の量を削減するために利用されうる。例えば、全データにデータ準備動作の実行するのではなく、動作は、ユーザに見える行にのみ実行される。一例として、どの行がユーザにとって可視であるか（例えば、どの行がユーザインターフェースで見られるのか）についての決定がなされる。（潜在的にユーザが結果をスクロールできるように、より多くの行が含められてもよい）。データ準備動作は、ユーザが現在見ることのできる行を含む（参照する）パーティションにのみ実行される。これは、ユーザの望む結果を提供しつつ、計算負荷の量を削減する。したがって、ユーザに見える行にのみ動作を実行することにより、ユーザは、ステップエディタユーザインターフェースと相互作用する時に（例えば、データ準備動作を変更する時に）、リアルタイムの結果を見ることができる。

上述の実施形態は、理解しやすいようにいくぶん詳しく説明されているが、本発明は、提供された詳細事項に限定されるものではない。本発明を実施する多くの代替方法が存在する。開示された実施形態は、例示であり、限定を意図するものではない。
適用例１：システムであって、
プロセッサであって、
１または複数のデータセットに実行された順序付けられたデータ準備動作のセットの結果を表すデータトラバーサルプログラムを生成し、前記データトラバーサルプログラムは、前記結果を導出するために、前記１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示し、
前記１または複数のデータセットに実行される前記順序付けられた動作のセットの仕様を受信したことに応答して、前記結果を表す前記データトラバーサルプログラムまたは前記結果を表す前記データトラバーサルプログラムの格納済みのコピーにアクセスし、
前記結果を再生成するために、前記データトラバーサルプログラムに従って、前記１または複数のデータセット内の前記１または複数の影響を受けた列を集め、
前記結果を出力するよう構成されているプロセッサと、
前記プロセッサに接続され、前記プロセッサに命令を提供するよう構成されているメモリと、
を備える、システム。
適用例２：適用例１に記載のシステムであって、データ準備動作は、データセットを変換する動作を含む、システム。
適用例３：適用例１に記載のシステムであって、前記データトラバーサルプログラムは、前記結果の行を記述するために用いられる列値への参照を含む、システム。
適用例４：適用例１に記載のシステムであって、前記データトラバーサルプログラムは、参照スタックを含み、前記参照スタックは、前記順序付けられた動作の記録と、前記順序付けられた動作によって影響を受けた列とを含む、システム。
適用例５：適用例１に記載のシステムであって、前記データトラバーサルプログラムは、前記結果自体よりも、必要とするメモリストレージの量が少ない、システム。
適用例６：適用例１に記載のシステムであって、前記データトラバーサルプログラムを生成することは、前記１または複数のデータセットを複製しない、システム。
適用例７：適用例１に記載のシステムであって、前記データトラバーサルプログラムに関するデータは自動的に格納される、システム。
適用例８：適用例１に記載のシステムであって、前記データトラバーサルプログラムに関するデータは前記順序付けられたデータ準備動作のセットの複雑性に基づいて格納される、システム。
適用例９：適用例１に記載のシステムであって、前記データトラバーサルプログラムに関するデータは、前記結果を格納する要求に応答して格納される、システム。
適用例１０：適用例１に記載のシステムであって、前記出力された結果の少なくとも一部は、ウィンドウビューに表示される、システム。
適用例１１：適用例１に記載のシステムであって、前記データトラバーサルプログラムは、１または複数のシグネチャのセットに関連付けられる、システム。
適用例１２：適用例１１に記載のシステムであって、前記１または複数のシグネチャのセット内の各シグネチャは、ハッシュ関数を用いて生成される、システム。
適用例１３：適用例１に記載のシステムであって、データセットは、１または複数の列を含む、システム。
適用例１４：方法であって、
１または複数のデータセットに実行された順序付けられたデータ準備動作のセットの結果を表すデータトラバーサルプログラムを生成し、前記データトラバーサルプログラムは、前記結果を導出するために、前記１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示し、
前記１または複数のデータセットに実行されるセットの順序付けられた動作のセットの仕様を受信したことに応答して、前記結果を表す前記データトラバーサルプログラムまたは前記結果を表す前記データトラバーサルプログラムの格納済みのコピーにアクセスし、
前記結果を再生成するために、前記データトラバーサルプログラムに従って、前記１または複数のデータセット内の前記１または複数の影響を受けた列を集め、
前記結果を出力すること、
を備える、方法。
適用例１５：適用例１４に記載の方法であって、データ準備動作は、データセットを変換する動作を含む、方法。
適用例１６：適用例１４に記載の方法であって、前記データトラバーサルプログラムは、前記結果の行を記述するために用いられる列値への参照を含む、方法。
適用例１７：適用例１４に記載の方法であって、前記データトラバーサルプログラムは、参照スタックを含み、前記参照スタックは、前記順序付けられた動作の記録と、前記順序付けられた動作によって影響を受けた列とを含む、方法。
適用例１８：適用例１４に記載の方法であって、前記データトラバーサルプログラムは、前記結果自体よりも、必要とするメモリストレージの量が少ない、方法。
適用例１９：適用例１４に記載の方法であって、データセットは、１または複数の列を含む、方法。
適用例２０：コンピュータプログラム製品であって、持続性のコンピュータ読み取り可能な記憶媒体内に具現化され、
１または複数のデータセットに実行された順序付けられたデータ準備動作のセットの結果を表すデータトラバーサルプログラムを生成するためのコンピュータ命令と、前記データトラバーサルプログラムは、前記結果を導出するために、前記１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示し、
前記１または複数のデータセットに実行されるセットの順序付けられた動作のセットの仕様を受信したことに応答して、前記結果を表す前記データトラバーサルプログラムまたは前記結果を表す前記データトラバーサルプログラムの格納済みのコピーにアクセスするためのコンピュータ命令と、
前記結果を再生成するために、前記データトラバーサルプログラムに従って、前記１または複数のデータセット内の前記１または複数の影響を受けた列を集めるためのコンピュータ命令と、
前記結果を出力するためのコンピュータ命令と、
を備える、コンピュータプログラム製品。

Claims (20)

1. システムであって、
   プロセッサであって、
   １または複数のデータセットに実行された順序付けられたデータ準備動作のセットの結果を表すデータトラバーサルプログラムを生成し、前記結果を表すデータトラバーサルプログラムを格納し、前記データトラバーサルプログラムは、前記結果を導出するために、前記１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示す参照および順序付けられた動作の記録と、順序付けられた動作によって変更された列とを含む参照スタックを有し、
   前記１または複数のデータセットに実行される前記順序付けられた動作のセットの仕様を受信したことに応答して、前記結果を表す前記データトラバーサルプログラムまたは前記結果を表す前記データトラバーサルプログラムの格納済みのコピーにアクセスし、
   前記参照および参照スタックを用い、少なくとも部分的には、前記データトラバーサルプログラムに従って前記１または複数のデータセット内の前記１または複数の影響を受けた列を集めることによって、前記結果を再生成し、
   前記結果を出力するよう構成されているプロセッサと、
   前記プロセッサに接続され、前記プロセッサに命令を提供するよう構成されているメモリと、
   を備える、システム。
2. 請求項１に記載のシステムであって、データ準備動作は、データセットを変換する動作を含む、システム。
3. 請求項１に記載のシステムであって、前記データトラバーサルプログラムは、前記結果の行を記述するために用いられる列値への参照を含む、システム。
4. 請求項１に記載のシステムであって、前記データトラバーサルプログラムは、参照スタックを含み、前記参照スタックは、前記順序付けられた動作の記録と、前記順序付けられた動作によって影響を受けた列とを含む、システム。
5. 請求項１に記載のシステムであって、前記データトラバーサルプログラムは、前記結果自体よりも、必要とするメモリストレージの量が少ない、システム。
6. 請求項１に記載のシステムであって、前記データトラバーサルプログラムを生成することは、前記１または複数のデータセットを複製しない、システム。
7. 請求項１に記載のシステムであって、前記データトラバーサルプログラムに関するデータは自動的に格納される、システム。
8. システムであって、
   プロセッサであって、
   １または複数のデータセットに実行された順序付けられたデータ準備動作のセットの結果を表すデータトラバーサルプログラムを生成し、前記データトラバーサルプログラムは、前記結果を導出するために、前記１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示し、
   前記１または複数のデータセットに実行される前記順序付けられた動作のセットの仕様を受信したことに応答して、前記結果を表す前記データトラバーサルプログラムまたは前記結果を表す前記データトラバーサルプログラムの格納済みのコピーにアクセスし、前記データトラバーサルプログラムに関するデータは前記順序付けられたデータ準備動作のセットの複雑性に基づいて格納され、
   前記結果を再生成するために、前記データトラバーサルプログラムに従って、前記１または複数のデータセット内の前記１または複数の影響を受けた列を集め、
   前記結果を出力するよう構成されているプロセッサと、
   前記プロセッサに接続され、前記プロセッサに命令を提供するよう構成されているメモリと、
   を備える、システム。
9. 請求項１に記載のシステムであって、前記データトラバーサルプログラムに関するデータは、前記結果を格納する要求に応答して格納される、システム。
10. 請求項１に記載のシステムであって、前記出力された結果の少なくとも一部は、ウィンドウビューに表示される、システム。
11. 請求項１に記載のシステムであって、前記データトラバーサルプログラムは、１または複数のシグネチャのセットに関連付けられる、システム。
12. 請求項１１に記載のシステムであって、前記１または複数のシグネチャのセット内の各シグネチャは、ハッシュ関数を用いて生成される、システム。
13. 請求項１に記載のシステムであって、データセットは、１または複数の列を含む、システム。
14. 方法であって、
    １または複数のデータセットに実行された順序付けられたデータ準備動作のセットの結果を表すデータトラバーサルプログラムを生成し、前記結果を表すデータトラバーサルプログラムを格納し、前記データトラバーサルプログラムは、前記結果を導出するために、前記１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示す参照および順序付けられた動作の記録と、順序付けられた動作によって変更された列とを含む参照スタックを有し、
    前記１または複数のデータセットに実行されるセットの順序付けられた動作のセットの仕様を受信したことに応答して、前記結果を表す前記データトラバーサルプログラムまたは前記結果を表す前記データトラバーサルプログラムの格納済みのコピーにアクセスし、
    前記参照および参照スタックを用い、少なくとも部分的には、前記データトラバーサルプログラムに従って前記１または複数のデータセット内の前記１または複数の影響を受けた列を集めることによって、前記結果を再生成し、
    前記結果を出力すること、
    を備える、方法。
15. 請求項１４に記載の方法であって、データ準備動作は、データセットを変換する動作を含む、方法。
16. 請求項１４に記載の方法であって、前記データトラバーサルプログラムは、前記結果の行を記述するために用いられる列値への参照を含む、方法。
17. 請求項１４に記載の方法であって、前記データトラバーサルプログラムは、参照スタックを含み、前記参照スタックは、前記順序付けられた動作の記録と、前記順序付けられた動作によって影響を受けた列とを含む、方法。
18. 請求項１４に記載の方法であって、前記データトラバーサルプログラムは、前記結果自体よりも、必要とするメモリストレージの量が少ない、方法。
19. 請求項１４に記載の方法であって、データセットは、１または複数の列を含む、方法。
20. コンピュータプログラムであって、
    １または複数のデータセットに実行された順序付けられたデータ準備動作のセットの結果を表すデータトラバーサルプログラムを生成するための機能と、前記結果を表すデータトラバーサルプログラムを格納するための機能と、前記データトラバーサルプログラムは、前記結果を導出するために、前記１または複数のデータセット内の１または複数の影響を受けた列をどのように集めるのかを示す参照および順序付けられた動作の記録と、順序付けられた動作によって変更された列とを含む参照スタックを有し、
    前記１または複数のデータセットに実行されるセットの順序付けられた動作のセットの仕様を受信したことに応答して、前記結果を表す前記データトラバーサルプログラムまたは前記結果を表す前記データトラバーサルプログラムの格納済みのコピーにアクセスするための機能と、
    前記参照および参照スタックを用い、少なくとも部分的には、前記データトラバーサルプログラムに従って前記１または複数のデータセット内の前記１または複数の影響を受けた列を集めることによって、前記結果を再生成するための機能と、
    前記結果を出力するための機能と、
    をコンピュータによって実現させる、コンピュータプログラム。

Images