JP6750137B1 - 並列処理を使用したハッシュ結合の実行 - Google Patents

Abstract

データレコードは、コンピュータを使用して結合される。第１の複数のデータレコードおよび第２の複数のデータレコード内のデータレコードがハッシュされる。第１の複数のデータレコードおよび第２の複数のデータレコード内のデータレコードはそれぞれ、ハッシュに基づいて第１のグループ分けおよび第２のグループ分けに割り当てられる。第１のグループ分けおよび第２のグループ分けからのグループ分けの関連付けられたペアは、コンピュータプロセッサ上で実行するスレッドに提供され、異なるペアは、異なるスレッドに提供される。スレッドは、グループ分け内のレコードを結合するべきかどうかを決定するために、グループ分けのペアに対して並列に動作する。スレッドは、データレコードに関連付けられたハッシュが一致する場合、考慮中の２つのデータレコードを結合する。結合されたデータレコードは出力される。

Description

本明細書は、一般に、データ処理技法に関し、より詳細には、並列処理コンピュータシステム（例えば、マルチコアプロセッサ）に最適化されるようにハッシュ結合を実行することに関する。

ビッグデータアナリティクスなどのデータ分析プラットフォームの成長は、データ処理を、事業価値を有する情報を抽出するために大量のデータを処理するためのツールへと拡大した。効率的なデータ処理技法は、この目的のために、異なるデータソースからのデータの多数のセットにアクセス、処理、および分析するために必要とされる。例えば、中小企業は、専用コンピューティングリソースおよびヒューマンリソースを用いるサードパーティデータアナリティクス環境を利用して、外部データプロバイダ、内部データソース（例えば、ローカルコンピュータ上のファイル）、ビッグデータストア、およびクラウドベースのデータ（例えば、ソーシャルメディア情報）などの様々なソースからの膨大な量のデータを収集、処理、および分析することがある。有用な定量的情報および定性的な情報を抽出する様式で、データアナリティクスにおいて使用される、そのような大きなデータセットを処理することは、典型的には、強力なコンピュータデバイス上で実施される複雑なソフトウェアツールを必要とする。

結合アルゴリズムは、上述されたものなどの複数のデータセットを処理するときに用いられるデータ処理技法である。既存のデータ処理システムは、各々がそれぞれの性能トレードオフを有する複数の結合アルゴリズムを利用して、データの２つのセット間の論理的結合（例えば、ハッシュ結合、ネストされたループ、ソートマージ結合）を実行することができる。一例として、ハッシュ結合は複雑度Ｏ（Ｍ＋Ｎ）を予想し、ここで、ＮおよびＭは、結合されている２つのテーブルのタプルの数である。しかしながら、ハッシュ結合アルゴリズムは、好ましくないメモリアクセスパターン（例えば、ランダムディスクアクセス）を有することがあり、実行するのに時間がかかることがある。従って、既存のデータ処理システムは、結合アルゴリズムを処理するときに性能に問題が生じる。

上記および他の課題は、データレコードを結合するための方法、コンピュータ、および非一時的なコンピュータ可読メモリによって対処される。コンピュータを使用してデータレコードを結合する方法の実施形態は、第１の複数のデータレコードおよび第２の複数のデータレコードを識別することと、第１の複数のデータレコードおよび第２の複数のデータレコード内の各データレコードに対するハッシュを算出することとを含む。方法は、算出されたハッシュに基づいて、第１の複数のデータレコードのデータレコードをグループ分けの第１のセットからグループ分けに割り当てることと、算出されたハッシュに基づいて第２の複数のレコードのデータレコードをグループ分けの第２のセットからグループ分けに割り当てることであって、グループ分けの第２のセット内の各グループは、グループ分けの第１のセット内のそれぞれのグループ分けに関連付けられる、割り当てることとをさらに含む。方法は、ハッシュ値に基づいて、グループ分けの第１のセットからのグループ分けのそれぞれのデータレコードを、グループ分けの第２のセットからの関連付けられたグループ分けのそれぞれのデータレコードに結合するべきかどうかを決定することと、グループ分けの第１のセットからのグループ分けのそれぞれのデータレコードをグループ分けの第２のセットからの関連付けられたグループ分けのそれぞれのデータレコードに結合することを決定したことに応答して、それぞれのデータレコードを結合することとをさらに含む。方法は、結合されたデータレコードを出力することも含む。

データレコードを結合するためのコンピュータの実施形態は、少なくとも１つのコンピュータプロセッサと、動作を実行するためにプロセッサによって実行可能なコンピュータプログラム命令を記憶する非一時的なコンピュータ可読メモリとを含む。この動作は、第１の複数のデータレコードおよび第２の複数のデータレコードを識別することと、第１の複数のデータレコードおよび第２の複数のデータレコード内の各データレコードに対するハッシュを算出することとを含む。動作は、算出されたハッシュに基づいて、第１の複数のデータレコードのデータレコードをグループ分けの第１のセットからグループ分けに割り当てることと、算出されたハッシュに基づいて第２の複数のレコードのデータレコードをグループ分けの第２のセットからグループ分けに割り当てることであって、グループ分けの第２のセット内の各グループは、グループ分けの第１のセット内のそれぞれのグループ分けに関連付けられる、割り当てることとをさらに含む。動作は、ハッシュ値に基づいて、グループ分けの第１のセットからのグループ分けのそれぞれのデータレコードを、グループ分けの第２のセットからの関連付けられたグループ分けのそれぞれのデータレコードに結合するべきかどうかを決定することと、グループ分けの第１のセットからのグループ分けのそれぞれのデータレコードをグループ分けの第２のセットからの関連付けられたグループ分けのそれぞれのデータレコードに結合することを決定したことに応答して、それぞれのデータレコードを結合することとをさらに含む。動作は、結合されたデータレコードを出力することも含む。

非一時的なコンピュータ可読メモリの実装形態は、データレコードを結合するための動作を実行するためにコンピュータプロセッサによって実行可能なコンピュータプログラム命令を記憶する。動作は、第１の複数のデータレコードおよび第２の複数のデータレコードを識別することと、第１の複数のデータレコードおよび第２の複数のデータレコード内の各データレコードに対するハッシュを算出することとを含む。動作は、算出されたハッシュに基づいて、第１の複数のデータレコードのデータレコードをグループ分けの第１のセットからグループ分けに割り当てることと、算出されたハッシュに基づいて第２の複数のレコードのデータレコードをグループ分けの第２のセットからグループ分けに割り当てることであって、グループ分けの第２のセット内の各グループは、グループ分けの第１のセット内のそれぞれのグループ分けに関連付けられる、割り当てることとをさらに含む。動作は、ハッシュ値に基づいて、グループ分けの第１のセットからのグループ分けのそれぞれのデータレコードを、グループ分けの第２のセットからの関連付けられたグループ分けのそれぞれのデータレコードに結合するべきかどうかを決定することと、グループ分けの第１のセットからのグループ分けのそれぞれのデータレコードをグループ分けの第２のセットからの関連付けられたグループ分けのそれぞれのデータレコードに結合することを決定したことに応答して、それぞれのデータレコードを結合することとをさらに含む。動作は、結合されたデータレコードを出力することも含む。

本明細書において説明される主題の１つまたは複数の実装形態の詳細は、添付図面および以下の説明に記載されている。主題の他の特徴、態様、および潜在的な利点は、説明、図面、および特許請求の範囲から明らかになるであろう。

様々な図面内の同じ参照番号および指定は、同じ要素を示す。
一実施形態による並列処理コンピュータシステムのために最適化される結合ツールを実施する、例となる環境の図である。 一実施形態による並列処理コンピュータシステムのために最適化される結合ツールを実施するデータアナリティクスワークフローの例の図である。 一実施形態による並列処理コンピュータシステムのために最適化される結合ツールを実施するデータアナリティクスワークフローの例の図である。 一実施形態による並列処理コンピュータシステムのために最適化されたハッシュ結合技法を実施するための、例となるプロセスの図である。 一実施形態による並列処理コンピュータシステムのために最適化されたハッシュ結合技法を実施するための、例となるプロセスのフローチャートである。 一実施形態による説明されたシステムおよび方法を実施するために使用され得る、例となるコンピューティングデバイスの図である。 一実施形態により説明されるシステムおよび方法を実施するために使用され得るソフトウェアアーキテクチャを含むデータ処理装置の例の図である。

ビジネス関係機能（例えば、顧客エンゲージメント、プロセス性能、および戦略的意志決定）に関係するデータを取得することへの興味がある。高度なデータアナリティクス技法（例えば、テキストアナリティクス、機械学習、予測分析、データマイニング、および静力学（statics））は、例えば、集められたデータをさらに分析するために、企業によって使用可能である。また、電子商取引（電子的商取引）の成長およびパーソナルコンピュータデバイスおよびインターネットなどの通信ネットワークの、企業と顧客との間の品物、サービスおよび情報の交換への統合とともに、大量の企業関係データが電子的な形で転送および記憶される。企業にとって重要であり得る膨大な量の情報（例えば、金融取引、顧客プロフィールなど）は、ネットワークベースの通信を使用して複数のデータソースからアクセスされ、取り出し可能である。異種データソースおよびデータ分析器の情報への潜在的な関係性を含み得る大量の電子データにより、データアナリティクス動作を実行することは、構造化された／構造化されていないデータ、ストリーム、またはバッチデータ、およびテラバイトからゼタバイトまで変化する異なるサイズのデータなどの異なるデータタイプを含む非常に多数の多様なデータセットを処理することを伴うことができる。

その上、データアナリティクスは、パターンを認識し、相関を識別し、他の有用な情報を取得するために、異なるデータタイプの複雑化されたコンピュータ的に重い処理を必要とすることがある。いくつかのデータアナリティクスシステムは、ビッグデータに関連付けられた、より大きな記憶容量および処理要求を扱うために、データウェアハウスなどの大型で複雑な高価なコンピュータデバイスおよびメインフレームなどの高性能コンピュータ（ＨＰＣ）によって提供される機能を活用する。いくつかの場合では、そのような莫大な量のデータを集めて分析するために必要とされるコンピューティングパワーの量は、中小企業のネットワーク（例えば、デスクトップコンピュータ、サーバ）上で利用可能な従来の情報技術（ＩＴ）資産などの限られた能力をもつリソースを有する環境における難題を提示することができる。例えば、ラップトップコンピュータは、数百テラバイトのデータを処理することに関連付けられた要求をサポートするために必要とされるハードウェアを含まないことがある。従って、ビッグデータ環境は、数千のサーバとともに大型でコストのかかるスーパーコンピュータ上で一般に動く、よりハイエンドのハードウェアまたは高性能算出（ＨＰＣ）リソースを用いて、クラスタコンピュータシステムにまたがる大きいデータセットの処理をサポートすることがある。デスクトップコンピュータなどのコンピュータの速度および処理パワーが増加してきたが、それにもかかわらず、データアナリティクスにおけるデータ量およびサイズも増加し、いくつかのデータアナリティクス技術に最適ではない限られた算出能力（ＨＰＣと比較すると）をもつ従来のコンピュータを使用する。例として、実行のシングルスレッド内で一度に１つのレコードを処理する算出集約的なデータアナリティクス動作は、例えば、デスクトップコンピュータ上で実行する望ましくない長い算出時間という結果になることがあり、さらに、いくつかの既存のコンピュータアーキテクチャにおいて利用可能なマルチコア中央処理ユニット（ＣＰＵ）の並列処理能力を活用しないことがある。しかしながら、例えばマルチスレッド化された設計を使用して、効率的なスケジューリング並びにプロセッサおよび／またはメモリ最適化を提供する、現在のコンピュータハードウェア内で利用可能である、ソフトウェアアーキテクチャを組み込むことは、より低い複雑度、または従来のＩＴ、コンピュータ資産における効率的なデータアナリティクスを提供することができる。

説明される技法およびシステムは、同じＣＰＵ上の複数のコア上で動く独立スレッドなどの並列処理算出環境におけるデータ処理効率を増加させるために使用可能である。より具体的には、開示される技法は、多数のＣＰＵコアにまたがって結合動作の分散を成し遂げるハードウェアを意識した（hardware-conscious）ハッシュ結合プロセスを実施するために機能し、従って、プロセッサマルチコアをもつコンピュータの利用を最適化することができる。実施形態は、アプリケーションソフトウェアの実質的な再設計を必要とすることなく、マルチコアＣＰＵとともに導入される性能利点を活用する。また、説明される技法およびシステムは、それらの逐次的実行挙動に基づいて制限可能である分散処理を使用するいくつかの既存の結合動作を実行することに関連付けられた難題を克服する。

図１は、並列処理コンピュータシステム（例えば、マルチコアプロセッサ）のために最適化される結合ツールを実施する、例となる環境の図である。図示されるように、環境１００は、データアナリティクスシステム１４０を含む内部ネットワーク１１０を含み、データアナリティクスシステム１４０は、インターネット１５０にさらに接続される。インターネット１５０は、複数の異種リソース（例えば、サーバ、ネットワークなど）を接続するパブリックネットワークである。いくつかのケースでは、インターネット１５０は、内部ネットワーク１１０の外部にある、または内部ネットワーク１１０とは異なるエンティティによって運用される、任意のパブリックネットワークまたはプライベートネットワークであってよい。データは、インターネット１５０上でコンピュータとそれに接続されたネットワークとの間で、例えば、イーサネット、同期型光ネットワーク（ＳＯＮＥＴ）、非同期転送モード（ＡＴＭ）、符号分割多元アクセス（ＣＤＭＡ）、ロングタームエボリューション（ＬＴＥ）、インターネットプロトコル（ＩＰ）、ハイパーテキスト転送プロトコル（ＨＴＴＰ）、ＨＴＴＰ Ｓｅｃｕｒｅ（ＨＴＴＰＳ）、ドメインネームシステム（ＤＮＳ）プロトコル、伝送制御プロトコル（ＴＣＰ）、ユニバーサルデータグラムプロトコル（ＵＤＰ）、または他の技術などの様々なネットワーク技術を使用して、転送されてよい。

例として、内部ネットワーク１１０は、スマートフォン１３０ａおよびラップトップコンピュータ１３０ｂとして例示される、ハンドヘルドコンピューティングデバイスなどの、異なる能力をもつ複数のクライアントデバイスを接続するためのローカルエリアネットワーク（ＬＡＮ）である。内部ネットワーク１１０にデスクトップコンピュータ１３０ｃも接続されるように例示されている。内部ネットワーク１１０は、限定されるものではないが、イーサネット、ＷＩ−ＦＩ、ＣＤＭＡ、ＬＴＥ、ＩＰ、ＨＴＴＰ、ＨＴＴＰＳ、ＤＮＳ、ＴＣＰ、ＵＤＰまたは他の技術を含む１つまたは複数のネットワーク技術を利用する有線ネットワークまたは無線ネットワークであってよい。内部ネットワーク１１０は、データベース１３５として図示されるローカルストレージシステムへのアクセスをサポートすることができる。例として、データベース１３５は、内部データ、または内部ネットワーク１１０リソースのローカルにあるソースから他の方法で取得されたデータ（例えば、デバイス１３０クライアントを使用して作成および送信されるファイル）を記憶および維持するために用いられ得る。

図１に図示されるように、インターネット１５０は、データベース１６０、サーバ１７０、およびウェブサーバ１８０として例示される内部ネットワーク１１０から外部に配置された様々なデータソースを通信可能に接続することができる。インターネット１５０に接続されたデータソースの各々は、データアナリティクスアプリケーションなどのデータ処理プラットフォームによるその中に含まれる情報の分析処理のために、データレコードなどの電子データにアクセスし、これを取り出すために使用可能である。データベース１６０は、その後で入力として働くデータをデータアナリティクスアプリケーションまたは他の既存のデータ処理アプリケーションへと編集するためにアクセス可能である大量のデータ、またはレコードを収集、記憶、および維持するために使用される複数の容量のより大きい記憶デバイスを含むことができる。例として、データベース１６０は、サードパーティデータソースによって管理されるビッグデータストレージシステム内で使用可能である。いくつかの例では、ビッグデータストレージシステムなどの外部記憶システムは、処理能力のためにダイレクトアタッチドストレージ（ＤＡＳ）をもつ、サーバ１７０として例示されるコモディティサーバを利用することができる。

さらに、ウェブサーバ１８０は、インターネット１５０を介して、クライアントデバイス１３０のユーザなどのユーザに利用可能にされたコンテンツをホストすることができる。ウェブサーバ１８０は、静的なコンテンツを有する個々のウェブページを含む静的なウェブサイトをホストすることができる。ウェブサーバ１８０は、サーバサイド処理、例えばＰＨＰ、Ｊａｖａサーバページ（ＪＳＰ）、またはＡＳＰ．ＮＥＴなどのサーバサイドスクリプトに依拠する動的なウェブサイトのためのクライアントサイドスクリプトも含むことができる。いくつかのケースでは、ウェブサーバ１８０は、企業にとって興味深いことがある様々な形のデータ、例えば、コンピュータベースの対話に関係するデータ（例えば、クリック追跡データ）並びにウェブサイトおよびソーシャルメディアアプリケーション上でアクセス可能であるコンテンツを提供することによって、外部データソースとしての役割を果たすことができる。例として、クライアントコンピュータ１３０は、ウェブサーバ１８０によってホストされるウェブサイトなどの、インターネット１５０上で利用可能であるコンテンツを要請することができる。その後、ウェブサーバ１８０によってホストされるウェブサイトを見ながらユーザによって作られた、他のサイト、コンテンツ、または広告へのハイパーテキストリンク上のクリックは、監視され、または他の方法で追跡され、および後続の処理のためのデータアナリティクスプラットフォームへの入力としてクラウドからサーバへと供給可能である。インターネット１５０を介してデータアナリティクスプラットフォームによってアクセス可能であり得る外部データソースの他の例は、例えば、限定されるものではないが、外部データプロバイダ、データウェアハウス、サードパーティデータプロバイダ、インターネットサービスプロバイダ、クラウドベースのデータプロバイダ、ＳａａＳ（Software as a service）プラットフォームなどを含むことができる。

データアナリティクスシステム１４０は、例えばインターネット１５０を介して複数のデータソースから集められ、収集され、または別の方法でアクセスされる大量のデータを処理および分析するために利用されるコンピュータベースのシステムである。データアナリティクスシステム１４０は、多種多様のデータソースからのデータにアクセス、準備、混合、および分析する際に用いられるスケーラブルなソフトウェアツールおよびハードウェアリソースを実施することができる。例えば、データアナリティクスシステム１４０は、データ集約的プロセスおよびワークフローの実行をサポートする。データアナリティクスシステム１４０は、本明細書において説明される最適化されたハッシュ結合技法を含むデータアナリティクス機能を実施するために使用されるコンピューティングデバイスとすることができる。データアナリティクスシステム１４０は、例えば、図３に関して詳細に論じられるように、同じＣＰＵダイ上で複数のプロセッサコアを使用するハードウェアアーキテクチャを含むことができる。いくつかの例では、データアナリティクスシステム１４０は、データアナリティクスサーバ１２０として図示される専用コンピュータデバイス（例えば、サーバ）をさらに用いて、システムによって実施される大規模データアナリティクスをサポートする。

データアナリティクスサーバ１２０は、システム１４０のいくつかの分析機能を実施するためのサーバベースのプラットフォームを提供する。例えば、時間のより多くかかるデータ処理は、デスクトップコンピュータ１３０ｃなどの内部ネットワーク１１０上で利用可能な他のコンピュータリソースよりも大きい処理およびメモリ能力を有し得るデータアナリティクスサーバ１２０にオフロード可能である。その上、データアナリティクスサーバ１２０は、情報への集中アクセスをサポートし、それによって、データアナリティクスシステム１４０にアクセスするユーザの間で共有および協働能力をサポートするためにネットワークベースのプラットフォームを提供することができる。例えば、データアナリティクスサーバ１２０は、アプリケーションおよびアプリケーションプログラムインターフェース（ＡＰＩ）を作成、公開、および共有し、内部ネットワーク１１０などの環境分散ネットワー内のコンピュータにまたがってアナリティクスを展開するために利用可能である。データアナリティクスサーバ１２０は、データ分析ワークフローおよび複数のデータソースからのデータを使用するジョブの実行を自動化およびスケジューリングすることなどの、いくつかのデータアナリティクスタスクを実行するためにも用いられ得る。また、データアナリティクスサーバ１２０は、運営（administration）機能、管理機能、および制御機能を可能にする分析統括能力を実施することができる。いくつかの例では、データアナリティクスサーバ１２０は、スケジューラおよびサービス層を実行し、ワークフローのマルチスレッデイングなどの様々な並列処理能力をサポートし、それによって、複数のデータ集約的プロセスが同時に動くことを可能にするように構成される。いくつかのケースでは、データアナリティクスサーバ１２０は、単一のコンピュータデバイスとして実施される。他の実装形態では、データアナリティクスサーバ１２０の能力は、例えば、増加された処理性能のためにプラットフォームをスケーリングするように、複数のサーバにまたがって展開される。

データアナリティクスシステム１４０は、図１ではデータアナリティクスアプリケーション１４５として例示される１つまたは複数のソフトウェアアプリケーションをサポートするように構成可能である。データアナリティクスアプリケーション１４５は、データアナリティクスプラットフォームの能力を可能にするソフトウェアツールを実施する。いくつかのケースでは、データアナリティクスアプリケーション１４５は、ネットワーク化された、またはクラウドベースの、データ分析ツールおよびマクロへのアクセスをサポートするソフトウェアを、クライアント１３０などの複数のエンドユーザに提供する。例として、データアナリティクスアプリケーション１４５は、ユーザがモバイルアプリケーションストアまたは他のクラウドベースのサービスに類似した様式で、アナリティクスを共有、ブラウジング、および消費することを可能にする。分析データ、マクロ、およびワークフローは、例えば、データアナリティクスシステム１４０の他のユーザによってアクセス可能である、より小規模でカスタマイズ可能な分析アプリケーション（すなわち、アプリ）としてパッケージ化および実行可能である。いくつかのケースでは、公開された分析アプリへのアクセスは、データアナリティクスシステム１４０によって管理可能である、すなわち、アクセスを付与または無効にし、それによって、アクセス制御およびセキュリティ能力を提供することができる。データアナリティクスアプリケーション１４５は、作成、展開、公開、反復、更新などの、分析アプリに関連付けられた機能を実行することができる。データアナリティクスアプリケーション１４５は、並列処理コンピュータシステムのハードウェアリソースを活用する技法を実施する結合ツールを含む。

さらに、データアナリティクスアプリケーション１４５は、分析結果にアクセス、準備、混合、分析、および出力する機能などの、データアナリティクスにおいて伴われる様々な段階で実行される機能をサポートすることができる。いくつかのケースでは、データアナリティクスアプリケーション１４５は、様々なデータソースにアクセスし、例えばデータのストリーム内の、生データを取り出すことができる。データアナリティクスアプリケーション１４５によって集められるデータストリームは、生データの複数のレコードを含むことができ、ここで、生データは、異なるフォーマットおよび構造をとる。少なくとも１つのデータストリームを受け取った後、データアナリティクスアプリケーション１４５は、データストリームのレコードがデータ分析動作への入力として使用されることを可能にするために動作を実行する。その上、予測アナリティクス（例えば、予測モデリング、クラスタ、データ調査）などの静的な処理、定性的な処理、または定量的な処理において伴われるレコードの分析機能は、データアナリティクスアプリケーション１４５によって実施可能である。データアナリティクスアプリケーション１４５は、視覚的なグラフィカルユーザインターフェース（ＧＵＩ）を介して、繰り返し可能なデータアナリティクスワークフローを設計および実行するソフトウェアツールをサポートすることもできる。例として、データアナリティクスアプリケーション１４５に関連付けられたＧＵＩは、データ混合、データ処理、および高度なデータアナリティクスのためのドラッグアンドドロップワークフロー環境を与える。その上、ワークフローは、本明細書において説明される技法およびシステムによる最適化された結合ツールを含む、特定の処理動作またはデータアナリティクス機能を実行するデータ処理ツールのシリーズを含むことができる。

図２Ａは、最適化された結合ツールを用いるデータアナリティクスワークフロー２００の例を図示する。一実施形態では、データアナリティクスワークフロー２００は、データアナリティクスシステム１４０のＧＵＩによってサポートされる視覚的なワークフロー環境を使用して作成される。視覚的なワークフロー環境は、ワークフローを設計するためにソフトウェアコードを提供する必要性を削除し、ワークフローによって実施される複雑な公式を識別する必要性を削除するドラッグアンドドロップツールのセットを可能にする。別の実施形態では、ワークフロー２００は、拡張可能なマークアップ言語（ＸＭＬ）文書などの文書内で作成および説明される。データアナリティクスワークフロー２００は、データアナリティクスシステム１４０のコンピュータデバイスによって実行される。しかしながら、他の実施形態では、データアナリティクスワークフロー２００は、ネットワークを介してデータアナリティクスシステム１４０に通信可能に接続されることがある別のコンピュータデバイスに展開される。

データアナリティクスワークフローは、特定の処理動作またはデータアナリティクス機能を実行するツールのシリーズを含むことができる。一般的な例として、ワークフローのツールは、以下のデータアナリティクス機能、すなわち、入力／出力、準備、結合、予測、空間的、調査、並びに動作の解析および変換、のうちの１つまたは複数を実行することができる。ワークフローを実施することは、データアナリティクスプロセスを定義、実行、および自動化することを伴うことができ、データは、ワークフロー内で各ツールに渡され、各ツールは、受け取られたデータに対して、そのそれぞれの処理動作を実行する。データアナリティクスプラットフォーム（図１に図示される）のデータアグリゲーション態様によれば、個々のレコードのアグリゲーションされたグループを含むレコードは、ワークフローのツールを通して渡され得、これは、個々の処理動作がデータに対してより効率的に動作することを可能にする。説明されたデータアグリゲーション技法は、大量のデータを処理してですら、ワークフローを策定して動かす速度を増加させることができる。ワークフローは、動作の繰り返し可能なシリーズを定義し、または別の方法で構造化して、指定されたツールの動作シーケンスを指定することができる。いくつかのケースでは、ワークフローに含まれるツールは、線形的な順序で実行される。他のケースでは、複数のツールは、並列に実行することができる。

例示されるように、図２Ａのワークフロー２００は、入力ツール２０５および２０６並びにブラウジングツール２３０として例示される入力／出力ツールを含む。入力ツール２０５および２０６は、ローカルデスクトップ上、リレーショナルデータベース内、クラウド内、またはサードパーティシステム内などの特定の場所からレコードにアクセスするように機能する。入力ツール２０５および２０６は、アクセスされたレコードをワークフローへと持ち込み、レコードをワークフロー２００の後続のツールに提供する。この例では、入力ツール２０５は、アクセスされたレコードをフィルタツール２１０に提供し、入力ツール２０６は、アクセスされたレコードを選択ツール２１１に提供する。ブラウジングツール２３０は、ワークフロー２００の終端に配置され、ワークフロー２００の上流ツールの各々の実行から生じる出力を受け取る。ブラウジングツール２３０は、この例ではワークフロー２００の終端に配置されているが、ブラウジングツール２３０は、ワークフローの上流ツールの実行からの結果を検討および検証するためにワークフロー内の任意の地点に追加可能である。

図２Ａの例を続けると、ワークフロー２００は、フィルタツール２１０、選択ツール２１１、式ツール２１５、およびサンプルツール２１２として図示される準備ツールを含む。フィルタツール２１０は、式に基づいてレコードを問い合わせ、データを、２つのストリーム、すなわち、式を満たすレコードを含む真のストリームおよび式を満たさないレコードを含む偽のストリームに分割する。選択ツール２１１は、フィールドを選択、選択解除、順序変更、および名前変更し、フィールドタイプまたはサイズを変更し、説明を割り当てるために使用可能である。データ式ツール２１５は、幅広く多様な計算および／または動作を実行するために、１つまたは複数の式を使用してフィールドを作成または更新する。サンプルツール２１２は、レコードの受け取られたストリームを、レコードの数、レコードのパーセンテージ、またはランダムなレコードのセットに限定する。

ワークフロー２００は、複数のデータソースを混合する最適化された結合ツール２２０も含む。具体的には、最適化された結合ツール２２０は、共通フィールド（またはレコード位置）に基づいて２つの入力データストリームを組み合わせる。最適化された結合ツール２２０によって生み出される結合された出力では、各行は、両方の入力からのデータを含む。ワークフローに含まれる最適化された結合ツールは、以下で図３Ａおよび図３Ｂを参照しながら詳細に論じられるハッシュ結合技法を実施する。結合ツール２２０などの最適化された結合ツールは、結合動作に関連付けられたタスクを複数のスレッドに分散させ、マルチコアＣＰＵの並列処理能力を活用することによって、ハードウェアを意識するように設計される。

図２Ａのワークフロー２００は、データをさらなる分析のために必要とされるフォーマットに再構成化して新しい形状にすることができる解析および変換ツールである要約ツール２２５を含むようにも図示されている。要約ツール２２５は、グループ分け、合計、カウンティング、空間的処理、および文字列連結によるデータの要約を実行することもできる。実施形態でのみ、要約ツール２２５によって生成される出力は、計算の結果のみを含む。

いくつかの実施形態では、ワークフロー２００の実行は、全てのレコードが処理され、結合ツール２２０に到達するまで、入力ツール２０５に、一度に１つのレコードをフィルタツール２１０および式ツール２１５に渡させる。その後、入力ツール２０６は、レコードが同じ結合ツール２２０に渡されるまで、一度に１つのレコードを選択ツール２１１およびサンプルツール２１２に渡し始める。ワークフロー２００のいくつかの個々のツールは、データの最後のブロックを処理しながらデータのブロックの読み取りを開始することまたはソートツールなどのコンピュータ集約的な動作を複数のパーツに分けることなどの、それら自体の並列動作を実施する能力を所有することができる。しかしながら、いくつかの既存のワークフロー技法では、レコードのセットからの各レコードは、処理動作を実行するために複数のレコードを必要とするワークフロー内のツール（例えば、ソートツール、結合ツール、要約ツールなど）が到達されるまで、一度に１つのレコードが、パイプライン式に、ワークフローの各ツールによって個々に処理される。

図２Ｂは、データアグリゲーション技法を使用してレコードをグループ分けするデータアナリティクスワークフロー２００の部分２８０の例を図示する。図２Ｂにおいて例示されるように、データストリームは、データをワークフロー２００の上部部分に持ち込むために入力ツール２０５を実行することに関連して複数のレコード２６０を含めて、取り出し可能である。この例では、データアグリゲーション技法は、データストリームのわずかな部分の並列処理を可能にするためにレコード２６０に適用される。データアグリゲーション技法は、データストリームからのレコード２６０を複数のレコードパケット２６５へとグループ分けすることを含む。その後、各レコードパケット２６５は、複数のパケット２６５を必要とするワークフロー内のツールに到達するまで、またはレコードパケット２６５が横断する経路に沿ってツールがもはやない、ワークフロー内の地点に到達するまで、ワークフローを通過させられ、ワークフロー２００内の複数のツールを通して処理される。実装形態では、データストリームは、レコードパケット２６５よりも桁が大きく、レコードパケット２６５は、レコード２６０よりも桁が小さい。従って、ストリーム全体内に含まれるレコードの合計のわずかな部分であるいくつかの複数のレコード２６０は、単一のレコードパケット２６５へとアグリゲーション可能である。例として、レコードパケット２６５は、バイト単位でのパケットの全長を含むフォーマットと、複数のアグリゲーションされたレコード２６０（例えば、連続するレコード）を有するように生成可能である。レコード２６０は、バイト単位でのレコードの全長を含むフォーマットと、複数のフィールドとを有することができる。しかしながら、いくつかの例では、個々のレコード２６０は、レコードパケット２６５のためのあらかじめ決定された容量よりも比較的大きいサイズを有することができる。従って、実装形態は、機構を利用して、このシナリオを扱い、かなり多いレコードをパケット化するために調整することを伴う。従って、説明されるデータアグリゲーション技法は、レコード２６０がレコードパケット２６５に関する設計された最大サイズを超えることがある例において用いられ得る。

図２Ｂは、レコードパケット２６５が、この例ではフィルタツール２１０である、データアナリティクスワークフロー２００内の次の連続した処理動作に渡されているところを図示する。いくつかのケースでは、レコード２６０は、あらかじめ決定されたサイズ容量の複数のレコードパケット２６５へとアグリゲーションされる。説明される技法によれば、レコードパケット２６５の最大サイズは、図１に図示されるデータアナリティクスシステム１４０を実施するために使用されるコンピュータシステムのハードウェアによって制約される、または別の方法でこれに結びつけられる。他の実装形態は、サーバの負荷などのシステム性能特性に依存するレコードパケット２６５のサイズを決定することを伴うことができる。一実施形態では、レコードパケット２６５のための最適にサイズ化された容量は、関連付けられたシステムアーキテクチャにおいて使用されるキャッシュメモリのサイズに因数分解できる関係に基づいて（スタートアップ時またはコンパイル時に）あらかじめ決定可能である。いくつかのケースでは、パケットは、キャッシュメモリへの直接的な関係（１対１の関係）を有するように設計された。例えば、レコードパケット２６５は、各パケットがターゲットＣＰＵ上で最大キャッシュのサイズ（例えば、記憶容量）より小さいまたはこれに等しいように作成可能である。再度述べられるように、レコード２６０は、キャッシュサイズのパケットへとアグリゲーション可能である。例として、６４ＭＢキャッシュを有するコンピュータシステムを利用して、説明されるデータアナリティクスアプリケーション１４５を実施することは、６４ＭＢというあらかじめ決定されたサイズ容量をもつように設計されたレコードパケット２６５を生ずる。データアグリゲーション技法において使用されるレコードパケット２６５の容量を最適化することは、スレッド間の増加される同期労力（より小さいサイズのパケットを利用することに関連付けられる）と潜在的な減少されたキャッシュ性能またはパケットごとの処理における増加される粒度／待ち時間（より大きいサイズのパケットを利用することに関連付けられる）との間のトレードオフを伴うことが理解されるべきである。

いくつかの実施形態では、レコードパケット２６５のためのサイズ容量は固定可能であるが、各レコードパケット２６５の長さを形成するように適切にアグリゲーション可能であるレコードの数は、必要に応じてシステムによって動的に調整可能なまたはふさわしい変数とすることができる。いくつかの既存のデータベースシステムでは、各レコードは、単一の固定長（例えば、１ＫＢ）で生成および処理される。説明される技法によれば、レコードパケット２６５は、可能な限り多くのレコードを、あらかじめ決定された最大容量を有する各パケットへと最適に含めることを可能にするために、可変のサイズすなわち長さを使用してフォーマット可能である。例えば、第１のレコードパケット２６５は、２ＭＢのサイズでパケットを形成するために、いくつかのレコード２６０を含むかなり大量のデータを保持するように生成可能である。その後、第２のレコードパケット２６５が、生成され、それの準備ができたと思われるとすぐにツールに渡され得る。この例を続けると、第２のレコードパケット２６５は、第１のパケットよりも比較的少ない数のアグリゲーションされたレコードを含み、１ＫＢのサイズに到達するが、ワークフローによって処理される前にデータを準備およびパケット化することに関連付けられた時間待ち時間を潜在的に減少させることができる。従って、いくつかの実施形態では、複数のレコードパケット２６５は、あらかじめ決定された容量によって限定される変化されたサイズを有し、さらにキャッシュメモリのサイズを超えない、システムを横断する。一実施形態では、パケットのための可変サイズを最適化することは、パケットベースで生成される各パケットに対して実行される。他の実装形態は、限定されるものではないが、使用されるツールのタイプ、最小待ち時間、データの最大量などを含む性能をさらに最適化するように、様々な調節可能なパラメータに基づいて任意のパケットのグループまたはパケットの数にとって最適なサイズを決定することができる。従って、アグリゲーションすることは、パケットの決定された可変サイズに従ってレコードパケット２６５へと置かれるのに最適なレコード２６０の数を決定することをさらに含むことができる。

いくつかの実装形態によれば、大量のレコード２６０は、アグリゲーション技法を使用して形成されたレコードパケット２６５として、様々なツールを通して処理、分析および渡され、それによって、データ処理速度および効率を増加させることができる。例えば、フィルタツール２１０は、いくつかの既存のデータアナリティクスプラットフォームの様式で複数のレコード２６０の各レコードを個々に処理することとは反対に、受け取られたレコードパケット２６５へとアグリゲーションされている複数のレコード２６０の処理を実行することができる。従って、フローを実行する速度は、それぞれのツールのソフトウェア再設計を余儀なくすることなく、複数のアグリゲーションされたレコードの並列処理を可能にすることによって、説明される技法に従って増加される。さらに、レコードをパケットへとアグリゲーションすることは、同期オーバヘッドを償却することができる。例えば、個々のレコードを処理することは、大きな同期コスト（例えば、１レコードずつ同期させること）を引き起こすことができる。対照的に、複数のレコードをパケットへとアグリゲーションすることによって、複数のレコードの各々に関連付けられた同期コストは、単一のパケットを同期させる（例えば、１パケットずつの同期）ために減少される。

その上、いくつかの例では、各レコードパケット２６５は、利用可能であるように別個のスレッド内での処理のためにスケジューリングされ、従って、並列処理コンピュータシステムのためのデータ処理性能を最適化する。例として、データアナリティクスシステム１４０が、複数のＣＰＵコア上で独立して動く複数のスレッドを利用する場合、複数のレコードパケットからの各レコードパケットは、その対応するコア上でのそれぞれのスレッドによる処理のために分散可能である。従って、説明されるデータアグリゲーション技法は、コンピュータアーキテクチャの様々な並列処理態様（例えば、マルチスレッデイング）を活用して、ＣＰＵコアのより大きなセット上でのデータ処理を成し遂げることによって、プロセッサ利用率を最適化することができる。

図３Ａは、並列処理コンピュータシステムに最適化されるようにハッシュ結合を実行するための、例となるプロセスの図である。本明細書において説明されるハッシュ結合技法は、データアナリティクスシステム１４０内のデータストリーム間で実行される結合動作の速度および性能を改善する。ハッシュ結合技法は、図２Ａの最適化されたジョイントツール２２０などの最適化されたジョイントツールの一部として実行される。ハッシュ結合技法は、結合動作を、データアナリティクスシステム１４０の複数のプロセッサコアを使用して非同期で処理可能である別個のパーツへと分割することによって、結合動作の実行速度およびワークフローの全体的な実行速度を増加させる。図３Ａは、２つの主要なフェーズ、すなわち、区分化フェーズ３０１〜３０２および結合フェーズ３０３〜３０４において結合動作を実行するようにハッシュ結合技法の例を例示する。いくつかの実施形態によれば、ハッシュ結合技法は、データベース管理システム内で使用される他の既存のハッシュ結合アルゴリズム、例えばＧｒａｃｅハッシュ結合、ハイブリッドハッシュ結合、およびハッシュされたループ結合を実施するように構成可能である。

区分化フェーズの動作３０１は、結合されることになる少なくとも２つのデータストリーム３００ａおよび３００ｂを入力として受け取ることを含む。データストリーム３００ａおよび３００ｂは、例えば、ワークフロー内の１つまたは複数のツールから受け取られる。データストリーム３００ａは「左データストリーム３００ａ」と呼ばれ、データストリーム３００ｂは「右データストリーム３００ｂ」と呼ばれる。データストリーム３００の各々は、複数のレコードを含む。例えば、各データストリーム３００は、異なるカンマ区切り値（ＣＳＶ）ファイルのレコードを含むことができる。各データストリーム３００のレコードは、パケットへと分割される。具体的には、パケット₁ ３０５、パケット₂ ３０６〜パケット_N ３０７が左データストリーム３００ａから生成され、パケット₁ ３０８、パケット₂ ３０９〜パケット_N ３１０が右データストリーム３００ｂから生成される。一実施形態では、パケットは、上記で図２Ｂを参照しながら説明されたレコードアグリゲーション技法に従って生成される。いくつかの実施形態では、データストリーム３００のレコードは、それらが、最適化された結合ツールによって受け取られたとき、パケットへと既に分割されている。例えば、パケットは、ワークフロー内の上流処理中に生成されていることがある。レコードがパケット内で受け取られたとき、最適化された結合ツールがパケットを再度生成する必要はない。

ハッシュ結合技法の区分化フェーズは、図３Ａに図示されるように、動作３０２に進む。動作３０２では、ハッシュが、データストリーム３００のパケットに含まれる各レコードに対して算出される。レコードのためのハッシュを算出するために、ハッシュ関数が、結合されることになる対象として働くレコードの属性（例えば、レコードの特定のフィールドの値）に適用される。例えば、レコードは各々、複数のフィールドを含むことがあり、その中で、フィールドのサブセットのみが、両方のデータストリームからのレコードに共通し、結合動作において使用可能である。結合ツールは、データストリーム３００の両方に共通するフィールドを決定する。各レコードに対して、結合ツールは、決定された共通フィールドのみからレコード内のデータ値を一緒にハッシュする。レコードのハッシュを算出するために使用されるハッシュ関数は、例えば、Ｓｐｏｏｋｙハッシュ関数またはＭＤ−５ハッシュ関数であってよい。一実施形態では、各レコードに対して算出されるハッシュは、１２８ビット値である。

動作３０２の一部として、各データストリーム３００のレコードは、それらのそれぞれのハッシュに基づいてハッシュバケットへと編成される。ハッシュバケットは、レコードのグループである。各データストリーム３００のレコードが編成されるハッシュバケットの数は、一実施形態では固定されている。図３Ａの例では、各データストリーム３００のレコードは、６４のバケットへと編成される。具体的には、左データストリーム３００ａは、ハッシュバケット₁ ３１１、ハッシュバケット₂ ３１２〜ハッシュバケット₆₄ ３１３へと編成され、右データストリーム３００ｂは、ハッシュバケット₁ ３１４、ハッシュバケット₂ ３１５〜ハッシュバケット₆₄ ３１６へと編成される。使用されるハッシュバケットの数は、データアナリティクスシステム１４０のハードウェアアーキテクチャに基づいて決定されるチューニング可能なパラメータである。一実施形態では、データストリームに使用されるハッシュバケットの数は、結合動作を処理するために利用可能なスレッドの数および／またはデータアナリティクスシステム１４０のプロセッサコアの数に依存する。従って、図３Ａの例では、結合動作を処理するために利用可能な６４のスレッドがあるので、またはデータアナリティクスシステム１４０が６４のプロセッサコアを含むので、６４のバケットが選択されていることがある。

各レコードに対して算出されるハッシュのビットのサブセットは、レコードをハッシュバケットに割り当てるために使用される。具体的には、各レコードに対して算出されるハッシュの、選択数の最下位ビット（ＬＳＢ）が、レコードをハッシュバケットに割り当てるために使用される。使用されるＬＳＢの数は、各データストリーム３００に使用されているハッシュバケットの数に基づいて決定される。一実施形態では、使用されるＬＳＢの数は、以下の式に従って決定され、ここで、ＸはＬＳＢの数である。

データストリーム３００のハッシュバケットのセットからの各ハッシュバケットは、ＬＳＢの異なる組み合わせに関連付けられる。従って、データストリーム３００の各レコードに対して、最適化された結合ツールは、レコードに対して算出されたハッシュのＬＳＢを決定し、レコードを、ストリーム３００のハッシュバケットのセットからＬＳＢに関連付けられたハッシュバケットに割り当てる。図３Ａの例では、各データストリーム３００に対して６４のバケットがあるので、上記の式に基づいて、レコードに対して算出されるハッシュの６つのＬＳＢが、レコードをハッシュバケットに割り当てるために使用される。具体的には、パケット３０５〜３０７内の各レコードが、ハッシュバケット３１１〜３１３からの、その対応する６つのＬＳＢに関連付けられたハッシュバケットへと置かれる。同様に、パケット３０８〜３１０内の各レコードが、ハッシュバケット３１４〜３１６からの、その対応する６つのＬＳＢに関連付けられたハッシュバケットへと置かれる。その上、図３Ａは、同じレコードパケット内のレコードが、算出されたハッシュに基づいて、別個のハッシュバケットへと置かれ得ることを例示する。例えば、パケット₁ ３０５内のレコード（直線によって表される）は、それぞれハッシュバケット３１１、３１２、および３１３の各々へと置かれる（破線矢印によって表される）ように例示されている。

ハッシュバケット３１１〜３１６は、同じＬＳＢをもつレコードが、異なるデータストリーム３００の一部であるときですら、同じ論理バケットを共有するという性質を有する。一例として、ハッシュバケット₂ ３１２に割り当てられる左データストリーム３００ａのレコードは、ハッシュバケット₂ ３１５に割り当てられる右データストリーム３００ｂのレコードと同じＬＳＢを有する。

結合するフェーズの動作３０３では、左データストリーム３００ａの各ハッシュバケットに対して、ハッシュバケットペアを作成するために、同じＬＳＢに関連付けられた右データストリーム３００の対応するハッシュバケットが識別される。各ハッシュバケットペアは、ハッシュバケットペアのレコードを結合するための異なる処理スレッドに割り当てられる。各スレッドは、次いで、処理のためにデータアナリティクスシステム１４０の異なるプロセッサコアに割り当てられる。一実施形態では、データアナリティクスシステム１４０のコアが枯渇し、スレッドが依然として残っている場合、残りのスレッドは、処理コアが利用可能であるときに割り当てられる（例えば、ラウンドロビン）。図３Ａは、ハッシュバケット₁ ３１１がハッシュバケット₁ ３１４とペアにされ、このペアはスレッド₁ ３２０に割り当てられることを例示する。同様に、ハッシュバケット₂ ３１２はハッシュバケット₂ ３１５とペアにされ、このペアはスレッド₂ ３２１に割り当てられる。ペアリングおよび割り当ては、ハッシュバケット₆₄ ３１３がハッシュバケット₆₄ ３１６とペアにされ、スレッド_N ３２２に割り当てられるまで継続する。

ＬＳＢを使用してレコードをハッシュバケットへと編成することに基づいて、各ハッシュバケットペアは、他のハッシュバケットペア／スレッドからのレコードを必要とすることなく結合を実行するために対応するスレッドによって必要とされるレコードを含む。その結果、スレッドは、データアナリティクスシステム１４０の複数のコアを使用して、ハッシュバケットペアを非同期で独立して処理することができる。この分割統治戦略は、最適化された結合ツールが、データアナリティクスシステム１４０のマルチコアアーキテクチャを活用することを可能にする。

動作３０４では、結合フェーズの最後の段階として図示されるように、各スレッドは、その対応するペアの各ハッシュバケット内のレコードをソートする。あるいは、ペアの各バケットは、異なるスレッドによってソート可能である。ハッシュバケット内のレコードは、それらの算出されたハッシュに基づいてソートされる。例えば、レコードは、それらのそれぞれのハッシュに従って昇順または降順でソート可能である。ハッシュバケット内の各レコードに対して、スレッドは、レコードをペアの他のハッシュバケット内の１つまたは複数のレコードと結合するべきかどうかを決定する。一実施形態では、２つのレコードの１２８ビットハッシュ全体が合致する場合、スレッドは、この２つのレコードを結合する。スレッドが、レコードが１つまたは複数の他のレコードと結合可能であることを決定する場合、スレッドは、結合動作を実行する。レコードが他の任意のレコードと結合しないケースでは、レコードは、結合不可能と考えられ、その後、結合されていない出力へとプッシュされる。いくつかの実施形態では、結合不可能出力は、さらなる結合動作に含まれることから結合することが不可能であるレコードを除去するためにフィルタとして使用され、それによって、この技法の処理速度を改善する。実施形態によれば、動作３０４における結合は、レコード内の実データの比較を必要とすることなく、レコードのハッシュを考えることによって達成される。１２８ビットハッシュを利用する実施形態によれば、衝突の可能性は、かなり小さい。従って、説明されるハッシュ結合技法は、各算出されたハッシュが、結合フィールドの単一のセットに適切に対応することを可能にし、次に、各フィールドが、その対応するハッシュを使用することによって適切に結合される（衝突に関連付けられたエラーを減少させる）ことを可能にする。

動作３０４は、図３Ａに図示されるように、結合されたパケット３３０、３３１、および３３２を生成する。具体的には、各ハッシュバケットペアからの結合されたレコードは、少なくとも１つの対応する結合されたパケット（破線矢印によって表される）に追加される。図３Ａの例は、スレッド₁ ３２０は、ハッシュバケット１ペアを結合したことから、結合されたパケット３３０を生成し、スレッド₂ ３２１は、ハッシュバケット₂ペアを結合したことから、結合されたパケット３３１を生成し、スレッド_N ３２２が、ハッシュバケット₆₄ペアを結合したことから、結合されたパケット３３２を生成するまで、各ペアに対する実行を継続することを示す。結合されたパケット３３０〜３３２は、結合フェーズの出力である両方のデータストリーム３３０からの結合されたレコードを含む。出力は、次いで、最適化された結合ツールによって、対応するワークフロー内の次のツールに提供可能である。

いくつかの実装形態では、結合フェーズは、独立したプロセッサ上で動くスレッドによって実行されるので、少なくともハッシュバケットペアのグループに対する結合動作は、同時に処理可能である。従って、説明されるハッシュ結合技法は、ワークフロー内の結合動作を実行する速度を増加させ、このことが、次に、（例えば、大量のデータを処理する際の）データアナリティクスアプリケーション１４５の全体的な速度におけるかなりの改善をもたらすことができる。従って、説明される技法は、それぞれの結合ツールの各々のかなりのソフトウェア再設計を必要とすることなく、並列処理の利点を実現する様式で機能させることによって結合ツールを強化する。

図３Ｂは、様々な並列処理コンピュータシステムのために最適化されるハッシュ結合技法を実行するための、例となるプロセス３３５のフローチャートである。プロセス３３５は、図１と関連して説明される最適化された結合モジュールおよびデータアナリティクスシステム１４０構成要素によって実施されてもよいし、構成要素の他の構成によって実施されてもよい。

３４０では、少なくとも２つのデータストリームの複数のレコードパケットを含む入力が取り出される。この複数のレコードパケットは、実行中のデータアナリティクスワークフローの処理動作（結合動作）に関連付けられる。いくつかの例では、データアナリティクスワークフローは、コンピュータデバイス（図１に図示される）上で実行し、図２Ａを参照して説明されるツールなどの特定のデータアナリティクス機能を実行するために使用可能である１つまたは複数のデータ処理動作を含む。図２Ａに示される例では、最適化された結合ツールは、実行中のワークフロー内のデータ処理動作として含まれる。最適化された結合ツールは、一般に、結合された出力を生み出すために、２つの取り出された入力データストリームを組み合わせると特徴づけ可能である。実施形態によれば、結合ツールは、説明されるハッシュ結合技法を実施することによって最適化される。図２Ａに図示される例に戻ると、例示されるデータアナリティクスワークフローは、ワークフロー内で定義された動作シーケンスに従って複数の処理動作を実行することを伴う。例では、最適化された結合ツールは、ワークフローのための動作のシーケンスに基づいて、以前の実行中の動作すなわち式ツールおよびサンプルツールの出力から、その入力を直接的に受け取る。最適化された結合ツールは、その入力ストリームを、ワークフロー内の上流処理中に以前に生成されたレコードパケットとして取り出す。あるいは、最適化された結合ツールは、入力データストリームを、パケットではなく生データストリームとして取り出すことができる。このケースでは、最適化された結合ツールに対する取り出された入力は、各データストリームのレコードを集合させてレコードパケットを形成することも伴う。従って、最適化された結合ツールは、図２Ｂを参照して説明される最適化されたデータアグリゲーション技法を実行するようにも構成される。

３４５では、入力を取り出した後、複数のレコードパケットの各々が、最適化された結合ツール動作のための処理を扱うために、複数のスレッドに転送される。いくつかのケースでは、最適化された結合ツール動作を実行することにスレッドを割り当てることは、データ処理カーネルのスケジューリング態様によって達成される。実施形態によれば、スレッドは、３４５において、本明細書において説明されるハッシュ結合技法に関連付けられたいくつかのタスクを実行するために割り当てられる。例えば、３４５では、スレッドは、図３Ａを参照しながら詳細に論じられるように、ハッシュ結合技法の区分化フェーズ動作を実行するために用いられる。実施形態では、スレッドはパケットごとにスケジュールされ、従って、ハッシュ結合技法は、様々な並列処理技術を利用するために最適化された、ハードウェアを意識した様式で、実施される。例えば、ワークフローを動くコンピュータデバイスは、ＣＰＵ上で実施される複数のコアなどの複数のプロセッサを含むことができる。従って、複数のスレッドの各々は、マルチコアＣＰＵのそれぞれのプロセッサコア上で独立して動くことができ、例えば、区分化動作が同時におよび効率的に実行することを可能にする。

３５０では、ハッシュが、複数のレコードパケットの各々の中のレコードに対して算出される。ハッシュは、その後でハッシングを使用して、結合プロセスをより小さいサブプロセスへと分割、または他の方法で区分化するために、３５０において、ハッシュ結合技法の区分化フェーズの一部として計算される。３５０において実行されるハッシングは、図３Ａを参照して説明されたハッシングの詳細に基づいて実施される。いくつかの例では、各レコードは、ハッシュ関数への入力として働き、特に、結合されているフィールドをハッシュする。一実施形態では、ハッシュ関数の出力は、１２８ビットハッシュである。

３５５では、各レコードが、レコードに対して算出されたハッシュのビットのサブセットに基づいて、対応するデータストリームのハッシュバケットのグループの中からハッシュバケットに割り当てられる。説明されたハッシュ結合技法では、ハッシュバケットは、入力データをハッシュグループへとさらに区分化するための機構として使用される。左データストリーム３００ａおよび右データストリーム３００ｂとして例示される、図３Ａの２つのデータストリームの各々は、対応するデータストリームのレコードをグループ化するために６４のハッシュバケットを使用する。１つのデータストリームの各ハッシュバケットは、ビットの同じサブセットに関連付けられた他のデータストリーム内の対応するハッシュバケットを有する。ビットの同じサブセットに関連付けられた２つのバケットは、ハッシュバケットペアと呼ばれる。図３Ａを参照して詳細に論じられるように、ハッシュバケットは、ビットの同じサブセットをもつレコードは同じ論理バケット（またはハッシュバケットペア）も共有するという性質を有する。上述されたハッシュ関数は、データストリームに割り当てられたハッシュバケットの１つの中のスロットに各レコードを挿入するために使用される。従って、各データストリームから互いに結合することが可能なレコードは、ビットの同じサブセットを有し、同じハッシュバケットペア内に置かれる。図３Ａからの例を続けると、左データストリーム３００ａのハッシュバケット₁ ３１１は、右データストリーム３００ｂのハッシュバケット₁ ３１４からのレコードと結合することがあるレコードを有し、その逆も同様である。

３６０では、各ハッシュバケットペアが、最適化された結合ツールの残りのタスクを実行するために別個のスレッドを使用して処理される。図３Ａを参照して詳細に論じられるように、バケットペアに割り当てられた各スレッドは、ハッシュ結合技法の結合フェーズ動作を実行することができる。実施形態では、スレッドがバケットペアごとに実行しているので、各スレッドは、そのレコードがバケット境界を越えて考えられることが必要とされることがあるリスクなしで、独立して処理可能である。従って、説明されるハッシュ結合技法は、順序づけられた様式または逐次的な様式で完了される実行を必要とすることがある結合動作に並列処理を使用することに関連付けられた難題を克服することができる。また、ハッシュ結合技法の結合フェーズを実行する際に、３６０における処理は、対応するハッシュを使用して、ハッシュバケットペアの各々の中でレコードをソートすることを含む。その結果、それぞれのペアの各ハッシュバケットは、ハッシュによってソートされた、レコードのソートされたリストに関連付けられる。いくつかの実施形態では、各ハッシュバケットペアに関してソートすることが、別個のワーカースレッド内で実行される。

その後、３６５では、各スレッドは、その対応するハッシュバケットペアのレコードが結合可能であるかどうかを決定する。いくつかの実施形態では、チェックが、ハッシュバケットペアのハッシュバケット内の各ソートされたレコードに関して反復して実行される。例えば、ハッシュバケット内の現在処理されているレコードは、ハッシュバケットペアの他のハッシュバケット内のソートされたレコードに対してチェックされる。従って、決定は、ペアの第１のハッシュバケット内の現在のレコードがそのペアの第２のハッシュバケットからのレコードのいずれかと結合するかどうかに関してなされる。決定は、３６５において、関連付けられたハッシュを使用して達成され、レコードの実データ値のスキャニングまたは比較を必要としない。従って、説明される結合技法を実行する速度は、著しく短いＣＰＵ時間を利用する（例えば、ハッシュ値によってインデックス付けされたデータのルックアップおよび比較を実行することに関連付けられた時間を削除する、ディスク読み出しの数を最小にする、など）ことによって、かなり増加される。

ハッシュバケットペアからのレコードが結合可能であることが決定される例（すなわち、「はい」）では、３７５において、レコードが結合され、結合されたレコードは、１つもしくは複数の結合されたパケットへと挿入される、または、これを生成するために他の方法で使用される。あるいは、レコードが、対応物であるハッシュバケットからの別のレコードと結合されることが可能でないことが決定されるケース（すなわち、「いいえ」）では、レコードは、結合の結果に含まれないように、３７０において結合されていない出力にプッシュされる。いくつかの実装形態では、結合された結果から３７５において結合されたパケットを生成することは、それぞれのハッシュバケットペアに対して同時に実行される。ハッシュ結合技法からの結果は、実行されている特定の最適化された結合ツールに対する出力として提供可能である。図２Ａの例では、最適化された結合ツール出力、すなわち結合されたパケットは、ワークフロー２００内で下流に渡される。いくつかの実施形態では、最適化された結合ツール出力は、データアナリティクスアプリケーション１４５に関連付けられたＧＵＩのためのグラフィカル情報としての表示のために提供される。

図４は、クライアントとして、またはサーバもしくは複数のサーバとして、のどちらかで、本文書内で説明されるシステムおよび方法を実施するために使用され得るコンピューティングデバイス４００のブロック図である。コンピューティングデバイス４００は、ラップトップ、デスクトップ、ワークステーション、携帯情報端末、サーバ、ブレードサーバ、メインフレーム、および他の適切なコンピュータなどの様々な形のデジタルコンピュータを表すことが意図されている。いくつかのケースでは、コンピューティングデバイス４５０は、携帯情報端末、セルラー式電話、スマートフォン、および他の類似のコンピューティングデバイスなどの様々な形のモバイルデバイスを表すことが意図されている。さらに、コンピューティングデバイス４００は、ユニバーサルシリアルバス（ＵＳＢ）フラッシュドライブを含むことができる。ＵＳＢフラッシュドライブは、オペレーティングシステムおよび他のアプリケーションを記憶することがある。ＵＳＢフラッシュドライブは、別のコンピューティングデバイスのＵＳＢポートに挿入され得る無線送信機またはＵＳＢコネクタなどの入力／出力構成要素を含むことができる。本明細書に図示される構成、それらの接続および関係、並びにそれらの機能は、例にすぎないことが意図されており、本文書において説明および／または特許請求される本発明の実装形態を限定することは意図されていない。

コンピューティングデバイス４００は、プロセッサ４０２と、メモリ４０４と、記憶デバイス４０６と、メモリ４０４および高速拡張ポート４１０に接続された高速インターフェース４０８と、低速バス４１４および記憶デバイス４０６に接続された低速インターフェース４１２とを含む。実施形態によれば、プロセッサ４０２は、並列処理技術を実施する設計を有する。例示されるように、プロセッサ４０２は、同じマイクロプロセッサチップまたはダイ上で複数のプロセッサコア４０２ａを含むＣＰＵとすることが可能である。プロセッサ４０２は、処理コア４０２ａを有すると図示されている。いくつかのケースでは、プロセッサ４０２は、２〜３２のコアを実施することができる。構成要素４０２、４０４、４０６、４０８、４１０、および４１２の各々は、様々なバスを使用して相互接続され、共通マザーボード上に取り付けられてもよいし、適宜他の様式で取り付けられてもよい。プロセッサ４０２は、高速インターフェース４０８に連結されたディスプレイ４１６などの外部入力／出力デバイス上にＧＵＩのためのグラフィカル情報を表示するためにメモリ４０４内または記憶デバイス４０６上に記憶された命令を含む、コンピューティングデバイス４００内の実行のための命令を処理することができる。他の実装形態では、複数のプロセッサおよび／または複数のバスは、適宜、複数のメモリおよび複数のタイプのメモリとともに使用されてよい。また、複数のコンピューティングデバイス４００は、（例えば、サーババンク、ブレードサーバのグループ、またはマルチプロセッサシステムとして）必要な動作の部分を提供する各デバイスと接続されることがある。

メモリ４０４は、コンピューティングデバイス４００内の情報を記憶する。一実装形態では、メモリ４０４は、１つまたは複数の揮発性メモリユニットである。別の実装形態では、メモリ４０４は、１つまたは複数の不揮発性メモリユニットである。メモリ４０４はまた、磁気ディスクまたは光ディスクなどの別の形のコンピュータ可読媒体であってよい。コンピューティングデバイス４００のメモリは、それが通常のＲＡＭにアクセスすることができるよりも迅速にマイクロプロセッサがアクセスすることができるランダムアクセスメモリ（ＲＡＭ）として実施されるキャッシュメモリも含むことができる。このキャッシュメモリは、チップＣＰＵと直接的に統合可能である、またはＣＰＵとの別個のバス相互接続を有する別個のチップ上に置かれ得る。

記憶デバイス４０６は、コンピューティングデバイス４００に大容量ストレージを提供することが可能である。一実装形態では、記憶デバイス４０６は、フロッピーディスクデバイス、ハードディスクデバイス、光ディスクデバイス、またはテープデバイス、フラッシュメモリデバイスもしくは他の類似のソリッドステートメモリデバイス、またはストレージエリアネットワークもしくは他の構成内のデバイスを含むデバイスのアレイなどの、非一時的なコンピュータ可読媒体であってもよいし、これを含んでもよい。コンピュータプログラム製品は、実行されるとき上記で説明されたものなどの１つまたは複数の方法を実行する命令も含んでよい。

高速コントローラ４０８は、コンピューティングデバイス４００のための帯域幅集約的な動作を管理し、低速コントローラ４１２は、より低い帯域幅集約的な動作を管理する。機能のそのような割り振りは、例にすぎない。一実装形態では、高速コントローラ４０８は、メモリ４０４、ディスプレイ４１６（例えば、グラフィックスプロセッサまたはアクセラレータを通して）に、および様々な拡張カード（図示せず）を受け入れ得る高速拡張ポート４１０に連結される。実装形態では、低速コントローラ４１２は、記憶デバイス４０６および低速拡張ポート４１４に連結される。様々な通信ポート（例えば、ＵＳＢ、ブルートゥース、イーサネット、無線イーサネット）を含み得る低速拡張ポートは、キーボード、ポインティングデバイス、スキャナなどの１つまたは複数の入力／出力デバイスに連結されてもよいし、例えば、ネットワークアダプタを通して、スイッチまたはルータなどのネットワークデバイスに連結されてもよい。

コンピューティングデバイス４００は、図示されるように、いくつかの異なる形で実施されてよい。例えば、それは、標準的なサーバ４２０として実施されてもよいし、そのようなサーバのグループ内で複数回実施されてもよい。それはまた、ラックサーバシステム４２４の一部として実施されてもよい。さらに、それは、ラップトップコンピュータ４２２などのパーソナルコンピュータ内で実施されてもよい。あるいは、コンピューティングデバイス４００からの構成要素が、モバイルデバイス内の他の構成要素（図１に図示される）と組み合わされてもよい。そのようなデバイスの各々は、コンピューティングデバイス４００のうちの１つまたは複数を含んでよく、システム全体は、互いと通信する複数のコンピューティングデバイス４００から構成されてよい。

図５は、データ処理装置５００を含むデータ処理システムの概略図であり、データ処理装置５００は、クライアントとして、またはサーバとしてプログラム可能である。データ処理装置５００は、ネットワーク５８０を通して１つまたは複数のコンピュータ５９０と接続される。図５では、１つのコンピュータのみがデータ処理装置５００として図示されているが、複数のコンピュータが使用可能である。データ処理装置５００は、アプリケーション層とデータ処理カーネルとの間で分散可能である様々なソフトウェアモジュールを実施する、図１に図示されるデータアナリティクスシステム１４０のためのソフトウェアアーキテクチャを含むように図示されている。これらは、上記で説明されたものなどのデータアナリティクスアプリケーション１４５のツールおよびサービスを含む、実行可能および／またはインタープリタ可能なソフトウェアプログラムまたはライブラリを含むことができる。使用されるソフトウェアモジュールの数は、実装形態によって変化することができる。その上、ソフトウェアモジュールは、１つまたは複数のコンピュータネットワークもしくは他の適切な通信ネットワークによって接続された１つまたは複数のデータ処理装置上で分散可能である。ソフトウェアアーキテクチャは、データアナリティクスエンジン５２０を実施する、データ処理カーネルとして説明される層を含む。データ処理カーネルは、図５に例示されるように、いくつかの既存のオペレーティングシステムに関係する特徴を含むように実施可能である。例えば、データ処理カーネルは、スケジューリング、割り振り、リソース管理などの、様々な機能を実行することができる。データ処理カーネルは、データ処理装置５００のオペレーティングシステムのリソースを使用するようにも構成可能である。いくつかのケースでは、データアナリティクスエンジン５２０は、データアナリティクスアプリケーション１４５を使用して策定されたワークフローを動くソフトウェア構成要素である。図５は、データアナリティクスシステム１４０のデータアグリゲーション態様を実施する最適化されたデータアグリゲーションモジュール５２５を含むように、データアナリティクスエンジン５２０を図示する。さらに、最適化された結合モジュール５３０は、少なくとも、説明され、データアナリティクスアプリケーション１４５の最適化された結合ツールによって利用される、ハッシュ結合技法を実施する。例として、データアナリティクスエンジン５２０は、例えば、ユーザおよびシステム設定５１０の構成５１６を説明する追加のファイルに加えてワークフローを説明するＸＭＬファイルとして、ワークフロー５１５をロードすることができる。その後、データアナリティクスエンジン５２０は、ワークフローによって説明されたツールを使用してワークフローの実行を協調させることができる。図示されるソフトウェアアーキテクチャ、特にデータアナリティクスエンジン５２０、最適化されたデータアグリゲーションモジュール５２５、および最適化された結合モジュール５３０は、複数のＣＰＵコア、大量のメモリ、複数のスレッド設計、および高度なストレージ機構（例えば、ソリッドステートドライブ、ストレージエリアネットワーク）を含むハードウェアアーキテクチャの利点を実現するように設計可能である。

データ処理装置５００は、１つまたは複数のプロセッサ５３５と、１つまたは複数の追加のデバイス５３６と、コンピュータ可読媒体５３７と、通信インターフェース５３８と、１つまたは複数のユーザインターフェースデバイス５３９とを含むハードウェアデバイスまたはファームウェアデバイスも含む。各プロセッサ５３５は、データ処理装置５００内での実行のための命令を処理することが可能である。いくつかの実装形態では、プロセッサ５３５は、シングルスレッドプロセッサまたはマルチスレッドプロセッサである。各プロセッサ５３５は、コンピュータ可読媒体５３７上または追加のデバイス５３６の１つなどの記憶デバイス上に記憶された命令を処理することが可能である。データ処理装置５００は、その通信インターフェース５３８を使用して、例えば、ネットワーク５８０上の、１つまたは複数のコンピュータ５９０と通信する。ユーザインターフェースデバイス５３９の例は、ディスプレイ、カメラ、スピーカ、マイクロホン、触覚的フィードバックデバイス、キーボード、およびマウスを含む。データ処理装置５００は、例えば、コンピュータ可読媒体５３７上、または１つもしくは複数の追加のデバイス５３６、例えば、フロッピーディスクデバイス、ハードディスクデバイス、光ディスクデバイス、テープデバイス、およびソリッドステートメモリデバイスのうちの１つもしくは複数の上で、上記で説明されたモジュールに関連付けられた動作を実施する命令を記憶することができる。

本明細書において説明される主題および機能的動作の実施形態は、デジタル電子回路内で、または本明細書に開示されている構造およびそれらの構造的等価物を含むコンピュータソフトウェア、ファームウェア、もしくはハードウェア内で、またはそれらの１つまたは複数の組み合わせで、実施可能である。本明細書において説明される主題の実施形態は、データ処理装置による実行のために、またはこれの動作を制御するために、コンピュータ可読媒体上で符号化された、コンピュータプログラム命令の１つまたは複数のモジュールを使用して実施可能である。コンピュータ可読媒体は、小売販路を通して販売されるコンピュータシステム内のハードドライブまたは光ディスクなどの製造された製品であってもよいし、埋め込みシステムであってもよい。コンピュータ可読媒体は、別個に獲得され、有線ネットワークまたは無線ネットワーク上でのコンピュータプログラム命令の１つまたは複数のモジュールの配信などによって、コンピュータプログラム命令の１つまたは複数のモジュールを用いて、後で符号化可能である。コンピュータ可読媒体は、非一時的な機械可読記憶デバイス、機械可読記憶基板、メモリデバイス、またはそれらの１つもしくは複数の組み合わせであってよい。

「データ処理装置」という用語は、例としてプログラマブルプロセッサ、コンピュータ、または複数のプロセッサもしくはコンピュータを含む、データを処理するための全ての装置、デバイス、および機械を包含する。装置は、ハードウェアに加えて、問題のコンピュータプログラムのための実行環境を作成するコード、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、ランタイム環境、またはそれらの１つもしくは複数の組み合わせを構成するコードを含むことができる。さらに、装置は、ウェブサービス、分散コンピューティングインフラストラクチャ、およびグリッドコンピューティングインフラストラクチャなどの、様々な異なるコンピューティングモデルインフラストラクチャを用いることができる。

コンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる）は、コンパイラ型言語またはインタープリタ型言語、宣言型言語または手続き型言語を含む任意の形のプログラミング言語で記述可能であり、それは、スタンドアロンプログラムとして、またはモジュール、構成要素、サブルーチン、もしくはコンピューティング環境内での使用に適した他のユニットとして、を含む任意の形で、展開可能である。コンピュータプログラムは、必ずしもファイルシステム内のファイルに対応しない。プログラムは、他のプログラムまたはデータを保持するファイルの一部分（例えば、マークアップ言語文書内に記憶される１つまたは複数のスクリプト）に記憶されてもよいし、問題のプログラム専用の単一のファイルに記憶されてもよいし、複数の協調されたファイル（例えば、１つまたは複数のモジュール、サブプログラム、もしくはコードの部分を記憶するファイル）に記憶されてもよい。コンピュータプログラムは、１つのコンピュータ上で、または１つのサイトに配置された、もしくは複数のサイトにまたがって分散され、通信ネットワークによって相互接続された、複数のコンピュータ上で実行されるように展開可能である。

本明細書において説明されるプロセスおよび論理フローは、入力データに対して動作し、出力を生成することによって機能を実行するために１つまたは複数のコンピュータプログラムを実行する１つまたは複数のプログラマブルプロセッサによって実行可能である。プロセスおよび論理フローは、特殊目的論理回路、例えば、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）またはＡＳＩＣ（特定用途向け集積回路）によっても実行可能であり、装置は、特殊目的論理回路、例えば、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）またはＡＳＩＣ（特定用途向け集積回路）としても実施可能である。

本明細書で説明されるシステムおよび技法の様々な実装形態は、デジタル電子回路、集積回路、特殊設計ＡＳＩＣ（特定用途向け集積回路）、コンピュータハードウェア、ファームウェア、ソフトウェアおよび／またはそれらの組み合わせで実現可能である。これらの様々な実装形態は、ストレージシステム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスからデータおよび命令を受信し、これらにデータおよび命令を送信するために連結された、特殊目的または汎用であってよい、少なくとも１つのプログラマブルプロセッサを含むプログラマブルシステム上で実行可能および／またはインタープリタ可能な１つまたは複数のコンピュータプログラム内の実装形態を含み得る。

これらのコンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーションまたはコードとしても知られる）は、プログラマブルプロセッサのための機械命令を含み、高水準手続き型言語および／もしくはオブジェクト指向プログラミング言語で、並びに／またはアセンブリ／機械言語で、実施可能である。本明細書において使用されるとき、「機械可読媒体」および「コンピュータ可読媒体」という用語は、機械可読信号として機械命令を受け取る機械可読媒体を含む、プログラマブルプロセッサに機械命令および／またはデータを提供するために使用される任意のコンピュータプログラム製品、装置、および／またはデバイス（例えば、磁気ディスク、光ディスク、メモリ、プログラマブル論理デバイス（ＰＬＤ））を指す。「機械可読信号」という用語は、プログラマブルプロセッサに機械命令および／またはデータを提供するために使用される任意の信号を指す。

ユーザとの対話を提供するために、本明細書で説明されるシステムおよび技法は、ユーザに情報を表示するためのディスプレイデバイスと、キーボードと、ユーザがコンピュータに入力を提供することができるポインティングデバイス（例えば、マウスまたはトラックボール）とを有するコンピュータ上で実施可能である。他の種類のデバイスも、ユーザとの対話を提供するために使用可能である。例えば、ユーザに提供されるフィードバックは、任意の形の感覚的フィードバック（例えば、視覚的フィードバック、聴覚的フィードバック、または触覚的フィードバック）であってよい。ユーザからの入力は、聴覚的入力、音声入力、または触覚的入力を含む任意の形で受け取られてよい。

本明細書で説明されるシステムおよび技法は、バックエンド構成要素を含む（例えば、データサーバとして）コンピューティングシステム内で、またはミドルウェア構成要素を含む（例えば、アプリケーションサーバ）コンピューティングシステム内で、またはフロントエンド構成要素を含む（例えば、本明細書で説明されるシステムおよび技法の実装形態とユーザが対話することができるグラフィカルユーザインターフェースまたはウェブブラウザを有するクライアントコンピュータ）コンピューティングシステム内で、またはそのようなバックエンド構成要素、ミドルウェア構成要素、もしくはフロントエンド構成要素の任意の組み合わせで、実施可能である。システムの構成要素は、任意の形のデジタルデータ通信またはデジタルデータ通信の任意の媒体（例えば、通信ネットワーク）によって相互接続可能である。通信ネットワークの例は、ローカルエリアネットワーク（「ＬＡＮ」）、ワイドエリアネットワーク（「ＷＡＮ」）、ピアツーピアネットワーク（アドホックメンバまたは静的メンバを有する）、グリッドコンピューティングインフラストラクチャ、およびインターネットを含む。

コンピューティングシステムは、クライアントと、サーバとを含み得る。クライアントおよびサーバは、一般に、互いから遠隔であり、典型的には、通信ネットワークを通して対話する。クライアントとサーバの関係は、それぞれのコンピュータ上で動き、互いに対するクライアント − サーバ関係を有するコンピュータプログラムによって、生じる。

数個の実装形態が詳細に説明されてきたが、他の修正形態も可能である。さらに、図に描かれる論理フローは、所望の結果を得るために、図示される特定の順序、または逐次的順序を必要としない。他のステップが提供されてもよいし、説明されたフローからステップが削除されてもよく、他の構成要素が、説明されたシステムに追加されてもよいし、これから除去されてもよい。従って、他の実装形態は、以下の特許請求の範囲に含まれる。

Claims (17)

1. コンピュータを使用してデータレコードを結合する方法であって、
   第１の複数のデータレコードおよび第２の複数のデータレコードを識別することと、
   前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内の各データレコードに対するハッシュを算出することと、
   前記算出されたハッシュに基づいて、前記第１の複数のデータレコードのデータレコードを複数の第１のグループ分けに割り当てることであって、各第１のグループ分けは、前記第１のグループ分けの前記データレコードの前記算出されたハッシュに含まれるビットのセットに関連付けられる、ことと、
   前記算出されたハッシュに基づいて、前記第２の複数のデータレコードのデータレコードを複数の第２のグループ分けに割り当てることであって、各第２のグループ分けは、前記第２のグループ分けの前記データレコードの前記算出されたハッシュに含まれるビットのセットに関連付けられる、ことと、
   それぞれの第１のグループ分けおよびそれぞれの第２のグループ分けをそれぞれのワーカースレッドに割り当てることであって、前記それぞれの第１のグループ分けは、前記それぞれの第２のグループ分けと同じビットのセットに関連付けられる、ことと、
   前記それぞれのワーカースレッドに割り当てられた前記第１のグループ分けおよび前記第２のグループ分けの前記データレコードの前記算出されたハッシュに基づいて、前記それぞれのワーカースレッドによって、前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することと、
   前記第１のグループ分けの１つまたは複数のデータレコードを前記第２のグループ分けの１つまたは複数のデータレコードに結合することを決定したことに応答して、前記それぞれのワーカースレッドによって、前記データレコードを結合することと、
   前記それぞれのワーカースレッドによって、前記第１のグループ分けおよび前記第２のグループ分けの前記結合されたデータレコードを出力することと
   を含む方法。
2. 前記データレコードは、値を有する複数のフィールドを含み、前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内の各データレコードに対するハッシュを算出することは、
   前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内のデータレコードに共通する前記データレコードの前記複数のフィールドのサブセットを識別することと、
   前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内のデータレコードに共通する前記複数のフィールドの前記サブセットの値のハッシュを算出することと
   を含む、請求項１の方法。
3. 前記それぞれのワーカースレッドに割り当てられた前記第１のグループ分けおよび前記第２のグループ分けの前記データレコードの前記算出されたハッシュに基づいて、前記それぞれのワーカースレッドによって、前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することは、
   第１のデータレコードと第２のデータレコードが一致するハッシュを有することに応答して、前記第１のグループ分けの前記第１のデータレコードを前記第２のグループ分けの前記第２のデータレコードに結合することを決定すること
   を含む、請求項１の方法。
4. 前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することは、
   前記データレコードに対する前記ハッシュに基づいて、前記第１のグループ分けの前記データレコードおよび前記第２のグループ分けの前記データレコードをソートすること
   を含む、請求項１の方法。
5. 前記コンピュータは、いくつかのプロセッサコアを有し、前記第１のグループ分けの数および前記第２のグループ分けの数は、前記プロセッサコアの数に応答して決定される、請求項１の方法。
6. 異なるワーカースレッドは、対応する前記第１のグループ分けおよび前記第２のグループ分けを並列に処理する、請求項１の方法。
7. データレコード結合するためのコンピュータであって、
   少なくとも１つのコンピュータプロセッサと、
   動作を実行するための前記コンピュータプロセッサによって実行可能なコンピュータプログラム命令を記憶する非一時的なコンピュータ可読メモリと
   を備え、前記動作は、
   第１の複数のデータレコードおよび第２の複数のデータレコードを識別することと、
   前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内の各データレコードに対するハッシュを算出することと、
   前記算出されたハッシュに基づいて、前記第１の複数のデータレコードのデータレコードを複数の第１のグループ分けに割り当てることであって、各第１のグループ分けは、前記第１のグループ分けの前記データレコードの前記算出されたハッシュに含まれるビットのセットに関連付けられる、ことと、
   前記算出されたハッシュに基づいて、前記第２の複数のデータレコードのデータレコードを複数の第２のグループ分けに割り当てることであって、各第２のグループ分けは、前記第２のグループ分けの前記データレコードの前記算出されたハッシュに含まれるビットのセットに関連付けられる、ことと、
   それぞれの第１のグループ分けおよびそれぞれの第２のグループ分けをそれぞれのワーカースレッドに割り当てることであって、前記それぞれの第１のグループ分けは、前記それぞれの第２のグループ分けと同じビットのセットに関連付けられる、ことと、
   前記それぞれのワーカースレッドに割り当てられた前記第１のグループ分けおよび前記第２のグループ分けの前記データレコードの前記算出されたハッシュに基づいて、前記それぞれのワーカースレッドによって、前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することと、
   前記第１のグループ分けの１つまたは複数のデータレコードを前記第２のグループ分けの１つまたは複数のデータレコードに結合することを決定したことに応答して、前記それぞれのワーカースレッドによって、前記データレコードを結合することと、
   前記それぞれのワーカースレッドによって、前記第１のグループ分けおよび前記第２のグループ分けの前記結合されたデータレコードを出力することと
   を含む、コンピュータ。
8. 前記データレコードは、値を有する複数のフィールドを含み、前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内の各データレコードに対するハッシュを算出することは、
   前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内のデータレコードに共通する前記データレコードの前記複数のフィールドのサブセットを識別することと、
   前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内のデータレコードに共通する前記複数のフィールドの前記サブセットの値のハッシュを算出することと
   を含む、請求項７のコンピュータ。
9. 前記それぞれのワーカースレッドに割り当てられた前記第１のグループ分けおよび前記第２のグループ分けの前記データレコードの前記算出されたハッシュに基づいて、前記それぞれのワーカースレッドによって、前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することは、
   第１のデータレコードと第２のデータレコードが一致するハッシュを有することに応答して、前記第１のグループ分けの前記第１のデータレコードを前記第２のグループ分けの前記第２のデータレコードに結合することを決定すること
   を含む、請求項７のコンピュータ。
10. 前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することは、
    前記データレコードに対する前記ハッシュに基づいて、前記第１のグループ分けの前記データレコードおよび前記第２のグループ分けの前記データレコードをソートすること
    を含む、請求項７のコンピュータ。
11. 前記コンピュータプロセッサは、いくつかのプロセッサコアを有し、前記第１のグループ分けの数および前記第２のグループ分けの数は、前記プロセッサコアの数に応答して決定される、請求項７のコンピュータ。
12. 異なるワーカースレッドは、対応する前記第１のグループ分けおよび前記第２のグループ分けを並列に処理する、請求項７のコンピュータ。
13. データレコードを結合するための動作を実行するためにコンピュータプロセッサによって実行可能なコンピュータプログラム命令を記憶する非一時的なコンピュータ可読メモリであって、前記動作は、
    第１の複数のデータレコードおよび第２の複数のデータレコードを識別することと、
    前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内の各データレコードに対するハッシュを算出することと、
    前記算出されたハッシュに基づいて、前記第１の複数のデータレコードのデータレコードを複数の第１のグループ分けに割り当てることであって、各第１のグループ分けは、前記第１のグループ分けの前記データレコードの前記算出されたハッシュに含まれるビットのセットに関連付けられる、ことと、
    前記算出されたハッシュに基づいて、前記第２の複数のデータレコードのデータレコードを複数の第２のグループ分けに割り当てることであって、各第２のグループ分けは、前記第２のグループ分けの前記データレコードの前記算出されたハッシュに含まれるビットのセットに関連付けられる、ことと、
    それぞれの第１のグループ分けおよびそれぞれの第２のグループ分けをそれぞれのワーカースレッドに割り当てることであって、前記それぞれの第１のグループ分けは、前記それぞれの第２のグループ分けと同じビットのセットに関連付けられる、ことと、
    前記それぞれのワーカースレッドに割り当てられた前記第１のグループ分けおよび前記第２のグループ分けの前記データレコードの前記算出されたハッシュに基づいて、前記それぞれのワーカースレッドによって、前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することと、
    前記第１のグループ分けの１つまたは複数のデータレコードを前記第２のグループ分けの１つまたは複数のデータレコードに結合することを決定したことに応答して、前記それぞれのワーカースレッドによって、前記データレコードを結合することと、
    前記それぞれのワーカースレッドによって、前記第１のグループ分けおよび前記第２のグループ分けの前記結合されたデータレコードを出力することと
    を含む非一時的なコンピュータ可読メモリ。
14. 前記データレコードは、値を有する複数のフィールドを含み、前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内の各データレコードに対するハッシュを算出することは、
    前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内のデータレコードに共通する前記データレコードの前記複数のフィールドのサブセットを識別することと、
    前記第１の複数のデータレコードおよび前記第２の複数のデータレコード内のデータレコードに共通する前記複数のフィールドの前記サブセットの値のハッシュを算出することと
    を含む、請求項１３の非一時的なコンピュータ可読メモリ。
15. 前記それぞれのワーカースレッドに割り当てられた前記第１のグループ分けおよび前記第２のグループ分けの前記データレコードの前記算出されたハッシュに基づいて、前記それぞれのワーカースレッドによって、前記第１のグループ分けのデータレコードを前記第２のグループ分けのデータレコードに結合するべきかどうかを決定することは、
    第１のデータレコードと第２のデータレコードが一致するハッシュを有することに応答して、前記第１のグループ分けの前記第１のデータレコードを前記第２のグループ分けの前記第２のデータレコードに結合することを決定すること
    を含む、請求項１３の非一時的なコンピュータ可読メモリ。
16. 前記コンピュータプロセッサは、いくつかのプロセッサコアを有し、前記第１のグループ分けの数および前記第２のグループ分けの数は、前記プロセッサコアの数に応答して決定される、請求項１３の非一時的なコンピュータ可読メモリ。
17. 異なるワーカースレッドは、対応する前記第１のグループ分けおよび前記第２のグループ分けを並列に処理する、請求項１３の非一時的なコンピュータ可読メモリ。

Images