この記事は Apache Drill Advent Calendar 2015 の18日目の記事です。
一般的な RDMBS のジョインアルゴリズムには、代表的なものとして ネストループ結合、マージ結合、ハッシュ結合などがあります。それぞれレコードへのアクセス方法や順序などが異なっており、最適なアルゴリズムを使うことでジョイン処理を効率化することができます。このアルゴリズムの選択は、通常はクエリオプティマイザの仕事です。
一方、分散型の SQL 処理エンジンでは、データが物理的に複数ノードに分散されているため、上記のジョインアルゴリズムとは別の軸として、分散環境特有のジョインプランを考える必要があります。
Drill では、「分散ジョイン （Distributed Join）」と「ブロードキャストジョイン（Broadcast Join）」の2つの選択肢があります。実際、商用の分散RDBMS（Nettezza、Vertica、Greenplum、Redshift など）や SQL on Hadoop（Hive、Impala、Presto など）でも同様のジョインの最適化が行われており、すでにおなじみの手法です。
下記は Drill と他の SQL エンジンでの呼び方を並べたものですが、本質的にはそれぞれ同じプランを表しています。
| Drill での呼び方 | 他の SQL エンジンでの呼び方 |
|---|---|
| Distributed Join | Shuffle Join、Common Join |
| Broadcast Join | Map Join、Fragment Replicate Join |
Distributed Join
Distributed Join においては、両方のテーブルの各レコードが、結合キーのハッシュ値に基づいてノード間に再分散されます。同じハッシュ値を持つレコード、つまり同じ結合キーをもつレコードは同じノードに存在するようになるはずです。
この「ハッシュ分散」オペレーションが行われた後、マージ結合アルゴリズムであれば両テーブルの各レコードはソートされ、ジョインが行われます。ハッシュ結合アルゴリズムであればソートは不要です。ただし、ネストループ結合の場合には Distributed Join を行うことはできません。
Broadcast Join
Broadcast Join では、ジョインが行われる前に片方のテーブルのデータ全体が、すべてのノードにブロードキャストされます。具体的には、内部表側のデータがブロードキャストされる一方、外部表側のデータはそのままで移動させません。
Broadcast Join は大きいファクトテーブル（トランザクションテーブル）と小さいディメンジョンテーブル（マスターテーブル）をジョインするような場合に便利です。大きなファクトテーブルのハッシュ分散はネットワークに負荷をかけるため、小さなディメンジョンテーブルのブロードキャストのほうがより効率的です。ただし、すべてのノードに同じデータを送るため、クラスタの構成やデータのサイズによっては最適にならない場合もあります。
Broadcast Join はネストループ結合、マージ結合、ハッシュ結合のいずれのジョインアルゴリズムにも対応します。
| ジョインのタイプ | ネストループ結合 | マージ結合 | ハッシュ結合 |
|---|---|---|---|
| Distributed Join | 不可 | 可 | 可 |
| Broadcast Join | 可 | 可 | 可 |
では、クエリオプティマイザはどのように Distributed Join、Broadcast Join を選択するのでしょうか。まず、内部表の行数がプロパティ planner.broadcast_threshold が表す閾値を超えていれば、Broadcast Join の候補となりえます。それに加えて、クラスタ構成やデータサイズを元にコストの計算が行われ、どのプランが効率的かの判断が行われます。
planner.broadcast_threshold を含め、選択に影響を与えるプロパティを下記に示します。
| プロパティ | 説明 | デフォルト値 |
|---|---|---|
| planner.broadcast_factor | ブロードキャストのコストを計算する際の係数。小さくすると、Broadcast Join がより選択されやすくなる | 1 |
| planner.enable_broadcast_join | Broadcast Join を有効にする | true |
| planner.broadcast_threshold | Broadcast Join の基準となる行数のしきい値。内部表の行数がこの値を上回る（と予想される）場合は Broadcast Join は選択されない | 10000000 |
