Fast inequality joins of Presto #SQL

Inequality joinというのはカラムの完全一致ではない比較でレコードをjoinしていく方法です。多くの場合、下記のように特定のカラム(e.g. bucket)が一致しているレコードをつなげていきます。

SELECT * FROM t1, t2 WHERE t1.bucket = t2.bucket

このbucketが一致した中でも特にある範囲条件を満たすようなものだけjoinしたい場合には下記のように書けます。

SELECT * FROM t1, t2 WHERE t1.bucket = t2.bucket AND t1.val1 < t2.val2;

これをinequality joinといいます。Prestoではequal条件の方でまずinner join(Hash join)を行い、それらのレコードに対してinequality条件の方でfilterしていきます。

このアルゴリズムの問題はfilterのときにレコードをすべて走査していかないとinequality条件を満たすレコードを見つけられないことです。t1の1レコードに対してequal条件にかかったレコードが膨大になると例えinequality条件でほとんど弾かれるとしても、とても効率が落ちてしまいます。

fast_inequality_join

そこでPrestoの0.174からfast_inequality_joinsというsession propertyが追加されました。デフォルトではオフになっていますが(バグのため0.177からオフにされています)、これをオンにするとequal条件でひっかかったレコードをsortして持ってきてくれます。

if (filterFunctionFactory.isPresent() &&
      filterFunctionFactory.get().getSortChannel().isPresent() && 
      isFastInequalityJoin(session)) {
  positionLinksBuilder = 
      SortedPositionLinks.builder(addresses.size(), new PositionComparator(pagesHashStrategy, addresses));
}
else {
  positionLinksBuilder = ArrayPositionLinks.builder(addresses.size());
}

sortされたため、inequality条件(t1.val < t2.val)を比較する際は二分探索を行い、高速に範囲を決定することができます。計算量はすべてのt1レコードに対してマッチするbucketのサイズ分だけ走査する必要があった

O(t1のサイズ * bucketのサイズ)

からt1のレコードそれぞれに対して二分探索にマッチしたbucketのlogとそのマッチした部分までの走査が必要なので

O(t1のサイズ * (log(bucketのサイズ) + バケット中にマッチしたレコード数))

inequality条件で当てはまるレコードがbueketのサイズとくらべて少なければ少ないほど速くなります。

Fast inequality joins of Presto

fast_inequality_join

Reference