はじめに
前回 は、結合処理の並列化における基本戦略について説明し、ソートマージ結合における具体的な並列アルゴリズムを説明しました。今回は、ImpalaやPrestoに加えて、Apache SparkやHadoop MapReduceのMap Joinにおいても用いられているハッシュ結合における具体的な並列アルゴリズムを説明します。
ハッシュ結合における並列アルゴリズム
ハッシュ結合は、2つのデータにおいて同一の属性値をもつレコードを見つける方法として、レコードのハッシュ値を用いるものです[1] 。すなわち、当該方法においては、一方のデータのすべてのレコードの結合キーに対してハッシュ関数を用いてハッシュ値を計算し、当該ハッシュ値からなるハッシュ表を事前に構築しておき、他方のデータのレコードの結合キーに対して同一のハッシュ関数から得られたハッシュ値を用いてハッシュ表を参照することにより、同一の属性値を持つ一方のレコードを見つけ出します。
ハッシュ結合は、多くの場合、ソートマージ結合よりも高速な結合処理アルゴリズムであると考えられています。この理由については、後の回でそれぞれの計算量を見ながらまたくわしく述べる予定です。ハッシュ結合についてもう少しくわしく知りたい方は、Wikipedia などを参照してください。
ハッシュ結合の並列化は、前回説明した並列化の基本的な方法を適用して、次のように行うことができます。
並列ハッシュ結合1
各計算機において、双方のデータを読み出し、それぞれを結合キーで分割し、当該分割データを各ノードに分配。この際、分配先のノードにおいて分割データを二次記憶に格納
各計算機でハッシュ結合を実行（一方のデータからハッシュ表を構築して、他方のデータを用いてハッシュ表を参照）
上記の方法は、1.において、分割データを各ノードの二次記憶に格納するため、総計のI/O量が多くなる傾向があります。このため、次のような改良方法が用いられることがあります（図1 ） 。
図1 並列ハッシュ結合
並列ハッシュ結合2
各計算機において、まず一方のデータを読み出し、結合キーで分割し、当該分割データを各ノードに分配。分配先のノードにおいては、データを二次記憶に格納せずに、そのままハッシュ表を構築（ハッシュ表自体は、場合によっては、二次記憶に格納）
各計算機において、他方のデータを読み出し、結合キーで分割し、当該分割データを各ノードに分配。当該分割データは、分配先のノードにおいて、二次記憶に格納せずに、そのままハッシュ表を参照して結合を実施
この方法においては、並列ハッシュ結合1と比較して、1.のフェーズにおける書き込みと2.のフェーズにおける読み出しのI/O量を削減できる可能性があります。
並列ソートマージ結合と同様に、いずれの並列ハッシュ結合においても、たとえば結合キーに偏りがある場合においては、ハッシュ表の大きさにばらつきが出てしまい、必ずしも結合処理を複数の計算機に均等に分割することは困難です。この問題に対しては、実際のデータの分布などに応じてハッシュ表を動的に分割することにより負荷分散処理を行う手法が提案されています（［2］ ） 。
なお、上述のような並列ハッシュ結合の方法は、1980年代に東京大学で研究開発されていたGraceなる並列データベースマシンにおいて初めて提案されたことから、（ Parallel）Grace Hash Join（コラム参照）と呼ばれることがあります。
Grace Hash Join
データを動的にハッシュ分割（クラスタリング）してそれぞれのパーティション（クラスタ）で独立に結合を行う、というアイデアはGraceという並列データベースマシンで文献［3］ 当時のGraceはデータをハッシュ分割して、それぞれのクラスタにおいて独自のハードウェアソータを用いてソートマージ結合を行うものでした。その後、文献［4］ クラスタリングの際にメモリ上で結合の一部の処理（一部のデータに対してハッシュ表の構築と当該表への参照）を行うという方法が提案され、当該方法においては結合方法としてハッシュ結合が用いられていました。文献［4］においては、従来のGraceのクラスタリング方法との正当な比較を行うため、Graceにおけるソートマージ結合の部分をハッシュ結合に変更をしたものをGrace Hash Joinと名づけ、自らの手法をHybrid Hash Joinとして、それらの比較を行いました。このような経緯から、データを動的にハッシュ分割をして各ノードでハッシュ結合をするようなシンプルな並列ハッシュ結合の方法をGrace Hash Joinと呼ぶようになったと考えられます。
Impala／Prestoにおける結合処理
並列データ処理系であるClouderaのImpala やFacebookを中心に開発が進められているPresto は、結合方法としておもに並列ハッシュ結合を用います。
Impalaの並列ハッシュ結合においては、上述のようなパーティション並列性の活用に加えて、パイプライン並列性を活用します。パイプライン並列性を活用するハッシュ結合方法は、1990年代に並列データベースの分野で数多く研究されてきており、複数のデータを結合する際に、たとえば図2 に示すように、先に複数のデータに対してハッシュ表を構築（ビルド、Build）し、その後、当該ハッシュ表に対してパイプラインで参照（プローブ、Probe）を行うことにより、複数の結合を同時に行います。このようにすることにより、各ノードにおける結合処理の並列度を高めることができ、たとえば複数のCPUの利用率を高めることが可能となります（図3 （a） ） 。ただし、同時に複数のハッシュ表をメモリ上に置いておく必要があるため、データが大きい場合はハッシュ表を保持するメモリを大量に使いすぎてしまい、最悪の場合は結合処理を正常に完了できない可能性があります。
図2 Impalaにおける並列ハッシュ結合図3 結合処理の並列度一方、Prestoの並列ハッシュ結合においては、基本的には上述のパーティション並列性を活かした方法が用いられます。すなわち、複数のデータを結合する際は、図4 に示すように、2つのデータにおいてハッシュ結合を行い、その結果データからハッシュ表を構築して、次のハッシュ結合を行う、という風に処理を進めていきます。この方法は、Impalaの方法に比べて、各ノードにおける結合処理の並列度は低いですが（図3 （b） ） 、メモリの使用量が少なくなるため、より安定的に結合処理を行える可能性があります。
図4 Prestoにおける並列ハッシュ結合また、Apache Sparkにおいては、事前に定義されている結合オペレータにより、Prestoと同様のハッシュ結合が行われます。ただし、パイプライン型のハッシュ結合を実行するオペレータを新たに定義することにより、Impalaと同様の結合方法を実現することは可能であると考えられます。Hadoop MapReduceにおいては、通常はReduce側で並列ソートマージ結合を行うReduce-side Joinですが、ブロードキャスト結合を用いることにより、Map側で並列ハッシュ結合を行うことも可能です。
ImpalaやPrestoの高速性の理由
ImpalaやPrestoはHadoop MapReduceと比べて高速であると言われていますが、その理由はおもに次の2つであると考えられます。
1つ目は、アルゴリズムの違いからくるものです。すなわち、先ほどもかんたんに述べたとおり、多くの場合、ハッシュ結合はソートマージ結合よりも高速であるためです。集約処理においても、Hadoop MapReduceは整列処理フレームワークを活用したソートベースの集約を行い、一方、ImapalaやPrestoはハッシュベースの集約を行うため、同様にアルゴリズムの差から性能差が生じていると考えられます。
2つ目は、システムの設計思想の違いからくるものです。Hadoop MapReduceは、二次記憶に中間状態を記録しながら処理を進めるため、どのような処理でもそれなりに動作するように設計されています。すなわち、Hadoop MapReduceはロバスト性や耐障害性を重視した設計ですが、その反面、総計のI/O量は必然的に多くなり、必ずしも高い性能は期待できません。一方、ImpalaやPrestoは、最初の読み出し以外においては、基本的にはメモリ上で処理を行います[2] 。この戦略は、当然、クエリ処理における中間データがメモリに収まり、かつ、クエリ処理の途中で障害が発生しない場合は良いのですが、そうでない場合は、当該クエリを正常に終了することができません。すなわち、ロバスト性や耐障害性をある程度妥協し、高速性を重視した設計であると考えられます。たとえば、Impalaのクエリ処理においてロバスト性や耐障害性を考慮した設計がなされているとすると、当然、総計のI/O量は増加し、Hadoop MapReduceとの性能差はおもにアルゴリズムから起因するものとなり、それほど大きなものにはならない可能性があります[3] 。
おわりに
今回は、ハッシュ結合における具体的な並列アルゴリズムを説明しました。次回は、これまで説明してきたアルゴリズムの性能を定量的に見積り、その見積りを用いた問合わせ最適化について説明する予定です。
