PostgreSQLのデータ構造はなぜ並列プロセッサ向きではないか。

PostgreSQL

今年もPostgreSQL Advent Calendar 2015に参加しています。

前からちょくちょく『PG-StromってXeon Phiだとどーなんですか？』的な質問を受ける事があんですが、データ構造から見て難しいので『勘弁！』という理由を紹介してみたいと思います。

PostgreSQLのレコードは、内部的には HeapTupleHeader 構造体を先頭とする可変長データとして表現されています。

struct HeapTupleHeaderData
{
    union
    {
        HeapTupleFields t_heap;   /* MVCC関連情報 */
        DatumTupleFields t_datum; /* xmin, xmaxとか... */
    }           t_choice;
    /* current TID of this or newer tuple */
    ItemPointerData t_ctid;
    /* レコードに含まれる行数とか */
    uint16      t_infomask2;
    /* 雑多なフラグ類 */
    uint16      t_infomask;
    /*
     * ヘッダ長。ユーザデータの格納位置は
     * ((char *)htup + htup->t_hoff) からスタート
     */
    uint8       t_hoff;

    /* ここまで23 bytes */
    /* NULLビットマップ（if HEAP_HASNULL）*/
    bits8       t_bits[FLEXIBLE_ARRAY_MEMBER];

    /* MORE DATA FOLLOWS AT END OF STRUCT */
    /* この後ろにユーザ定義列の内容が詰まっている */
};

で、このレコードのxx番目の列にアクセスする、という場合は先頭から順番にたぐっていくわけです。

1番目の列はint型だからポインタを4byte進め、2番目の列はfloat型だから8byte境界までポインタを進めた上で更に8byte進め、3番目の列はNULLだからポインタは進めず、．．．、といった事を目的の列まで順番に進めます。

ただ、これには例外があり、

  • レコードがNULL値を含んでいない
  • 目的の列よりも前にある列に可変長データが含まれていない

場合には、当該列を格納している位置が一意に定まるので、条件を満たす場合には目的の値を1ステップで参照する事ができますが。

詳しくはNikolay Shaplov氏のTuple internals: exposing, exploring and explainingというPGconf.EU 2015での発表がよく纏まっているので、こちらを参照して頂ければと思います。


話を並列プロセッサに戻します。

現在のPG-StromはCUDA、つまりNVIDIAのGPUを使うように設計されているのですが、この人は（複数のコアがプログラムポインタを共有するとはいえ）スカラプロセッサなので、各々のコアが互いに独立なメモリ領域を参照する事ができます。
つまり、CUDAコア0をレコード0にマップし、CUDAコア1をレコード1にマップし、、、、という事をすれば、各々のコアが独立にレコードの先頭から列を手繰っていけばよいだけなので、別にこれらレコードが隣接領域に配置されていなくとも処理自体は実行可能な訳です。
f:id:kaigai:20151215214346p:plain
もちろん、NVIDIAのGPUメモリのバス幅は256bitとか320bitですので、複数のCUDAコアが同時に隣接領域のDRAMをアクセスすると、１回のメモリトランザクションで複数コアが使用するデータをロードできるので、もっと最適化できる・・・というのはありますが。

一方、Xeon PhiのようにSIMD命令で512bit幅の演算器を単精度×8とか倍精度×4で使う事でピーク性能を出す事を前提とするプロセッサだと、色々とデータの配置にも制約が出てきます。
f:id:kaigai:20151215214353p:plain
少なくとも、現在のPostgreSQLのデータ構造であるHeapTupleHeaderを先頭とする可変長データでレコードを表現する限り、単精度×8の演算を同時に実行できるからといって、512bit幅の演算器で8レコード分の計算を一気にこなすわけにはいきません。

これに対処する方法としては２つ考えられるのですが、

  1. CPUでデータを抽出して512bitアラインの長大配列として再配置
  2. SIMD演算器向きのデータ構造でレコードを保持する。

①はコプロセッサに処理をオフロードするためにわざわざCPUの処理が増えているのでナンセンス。
（実際、私も以前にやってみた事があったが、、、）
②は列指向データがおそらく対応する事になるとは思うのですが、PostgreSQL用のネイティブ列指向ストレージはレビュー＆標準機能化に向けてもう少し時間が必要そうです。パッチ自体の規模が大きいのでちょっと二の足を踏んでしまうところではあるのですが…。

この辺、SIMD命令だけでなく、上記のようにスカラ型GPUにとってもメリットの大きい話なので、喩えて言えば『列指向ストレージが入ったら本気だす』といったところでしょうか。