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のサイズとくらべて少なければ少ないほど速くなります。