GpuNestedLoop

現時点でPG-Stromが対応しているワークロードは以下の4つ。

  • 全件探索 (GpuScan)
  • 表結合 (GpuHashJoin)
  • 集約演算 (GpuPreAgg)
  • ソート (GpuSort)

これに、GPU内の計算処理で使うデータ型や関数が対応しているかどうかで、GPUオフロードできるかどうかが決まる。
だいたいパッと思い付く程度にSQLクエリ処理で重い(CPUバウンドな)ヤツはカバレッジができてきたけれども、一つ大物が残っている。NestedLoop。

どう実装したものかと思っていたが、よいアイデアが浮かんだので備忘録代わりに。
f:id:kaigai:20150301211033p:plain

NestedLoopの場合、結合条件が単純な X=Y の形式ではないので、HashJoinやMergeJoinを用いて効率的に処理する事ができない。要はDBの中で総当たりを行う事になるので非常に重い。

今までに実装した上記の4つのロジックでは、PG-Stromは一次元的にGPUカーネルを起動していた。つまり、N個のGPUスレッドを起動する時にX軸にのみスレッドを割り当てていたのだが、X軸/Y軸をうまく使えばNestedLoopに落ちざるを得ないような表結合もうまく表現できるのではないかと考える。

イデアはこうだ。Inner-RelationとOuter-Relationからの入力をそれぞれ一次元の配列と捉える。
統計情報からの推定によりInner側は比較的行数が少ない方でY軸と置く。一方、Outer側は行数が多い方でX軸と置く。
で、一回のGPUカーネル実行で(Nx×Ny)個のGPUスレッドを起動すれば、各スレッドがそれぞれ対応する行のペアに対してNestedLoopの結合条件を評価し、マッチするペアのみを結果として取り出す事ができる。

CPUでのNestedLoopの実装は二重ループになっているので、如何せん時間がかかる。なので、普通はクエリ実行計画を見て真っ先に回避可能性を探る部分ではあるが、数千コアの同時並列実行能力の力でこういった制限も苦にならないとなれば、大きなアドバンテージになるだろう。

しかもこのGpuNestedLoopのロジックには、メモリアクセスで大きなアドバンテージを得られる可能性がある。
GPUスレッドはブロックという単位でグルーピングされ、同じブロックに属するGPUスレッド間は共有メモリを介したデータ共有が可能である。で、共有メモリはL1キャッシュと同じなので、DRAMへのアクセスに比べると非常に高速にアクセスが可能。
一方、GpuNestedLoopの処理ロジックの特性上、X軸上のインデックスが等しいスレッド、Y軸上のインデックスが等しいスレッドが複数個存在する。例えば、ブロックサイズ 32x32 (=1024) でGPUカーネルを起動した場合、X軸上のインデックスが 7 というGPUスレッドは他に32個存在しているハズである。これらのスレッドは Xindex=7 である行から同じデータを読み出すハズなので、何もDRAMアクセスを32回繰り返さなくても、1回だけで済む。わお!

NestedLoopに落ちざるを得ないJoinの条件は何も特別なモノでなく、例えば t0.X = t1.A OR t0.X = t1.B みたいな条件でも、NestedLoop以外のJoinロジックは使用不能となる。
一つ考慮しなければいけないのは、Inner-Relation側が十分に絞られておりGPUDRAMに載ってくれるサイズである必要がある、という事だが、そもそもNestedLoopで片側のサイズが数万行にもなるようなケースでは破綻していると言えるので、まぁ、実際上は問題なかろう。