時系列データ/BRINインデックス対応

PG-StromにBRINインデックス対応機能を実装してみた。

まずは、以下のEXPLAIN ANALYZEの実行結果をご覧いただきたい。
条件句で参照しているymd列は日付型(date)で、テーブルにデータを挿入する際には意図的に日付順にINSERTを行っている。

postgres=# EXPLAIN (analyze, buffers)
                    SELECT * FROM dt
                    WHERE ymd BETWEEN '2018-01-01' AND '2018-12-31' AND cat LIKE '%bbb%';
                                                           QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
 Custom Scan (GpuScan) on dt  (cost=94815.94..176284.51 rows=180436 width=44)
                                                   (actual time=475.668..585.988 rows=174590 loops=1)
   GPU Filter: ((ymd >= '2018-01-01'::date) AND (ymd <= '2018-12-31'::date) AND (cat ~~ '%bbb%'::text))
   Rows Removed by GPU Filter: 4386178
   BRIN cond: ((ymd >= '2018-01-01'::date) AND (ymd <= '2018-12-31'::date))
   BRIN skipped: 424704
   Buffers: shared hit=214 read=42432
 Planning time: 0.465 ms
 Execution time: 1005.738 ms
(8 rows)

BRIN condBRIN skippedという新しい項目が追加されている。
これは、ymd列に設定しているBRINインデックスを用いる事で、明らかに検索条件にマッチしないデータブロックをGpuScanが読み飛ばしている事を意味する。

テーブルdtは5000万行のレコードを含んでおり、テーブルサイズは3652MBある。
PostgreSQLのブロックサイズ 8KB で換算すると 467456 ブロック存在する事になる。
つまり、本来は全件スキャンで467456ブロックをスキャンすべきところ、うち424704ブロック(約90.8%)を『明らかにマッチするレコードが存在しない』として読み飛ばしている。

postgres=# \d+
                        List of relations
 Schema |    Name     | Type  | Owner  |    Size    | Description
--------+-------------+-------+--------+------------+-------------
 public | dt          | table | kaigai | 3652 MB    |
     :          :                :          :            :
 public | t1          | table | kaigai | 7512 kB    |
 public | t2          | table | kaigai | 7512 kB    |
 public | t3          | table | kaigai | 7512 kB    |

当然、読み飛ばすブロック数は検索条件によって変わり、例えば、日付範囲を2倍にした下記の例では(データをランダムに生成した事もあり)読み飛ばしたブロック数は382208個になっている。(それに伴い、処理時間も多少増えている)

postgres=# EXPLAIN (analyze, buffers)
                    SELECT * FROM dt
                    WHERE ymd BETWEEN '2018-01-01' AND '2019-12-31' AND cat LIKE '%bbb%';
                                                           QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
 Custom Scan (GpuScan) on dt  (cost=74703.58..348389.96 rows=360298 width=44) (actual time=551.541..993.654 rows=349081 loops=1)
   GPU Filter: ((ymd >= '2018-01-01'::date) AND (ymd <= '2019-12-31'::date) AND (cat ~~ '%bbb%'::text))
   Rows Removed by GPU Filter: 8758759
   BRIN cond: ((ymd >= '2018-01-01'::date) AND (ymd <= '2019-12-31'::date))
   BRIN skipped: 382208
   Buffers: shared hit=284 read=84864
 Planning time: 0.496 ms
 Execution time: 1449.248 ms
(8 rows)

BRINインデックスとは

BRINとは Block Range Index の略で*1、その名の通り、ある一定範囲のブロックを単位とするインデックスである。

RDBでお馴染みのB-treeインデックスは、インデックス対象列の値(キー)とレコード位置(ポインタ)を各レコード毎に持っており、例えば「ID=1234」みたいな条件句から特定のレコードを抽出するといった処理には滅法強い。
ただし、これはインデックスサイズが増大しがちで、例えば、センサやモバイル機器が生成したデータを日々DBに蓄積していくといった使い方を考えると、大規模データの脇に大規模インデックスが控えているという事になり、あまり現実的ではなくなる。

以下はインデックスサイズの比較だが、B-treeインデックスを設定しているid列(主キー)のインデックスdt_id_idxは1071MBで、本体のテーブルの1/3近いサイズになっている。この比率で行けば1.0TBのテーブルに対するインデックスは300GB程度になる(!)

一方で、BRINインデックスのdt_ymd_idxのサイズは僅か128kBに留まっている。これは両者のインデックスの持ち方に起因する。

postgres=# \di+
                                List of relations
 Schema |       Name       | Type  | Owner  |    Table    |  Size   | Description
--------+------------------+-------+--------+-------------+---------+-------------
 public | dt_id_idx        | index | kaigai | dt          | 1071 MB |
 public | dt_ymd_idx       | index | kaigai | dt          | 128 kB  |

BRINインデックスは128ブロック*2毎に、インデックス対象列の最小値と最大値を記録する。
そうすると、例えばymd BETWEEN '2018-01-01' AND '2019-12-31'という条件が与えられた時に、最大値が'2016-07-01'であるブロックは明らかにマッチする行が存在しないので読み飛ばして構わない。

PG-Stromの動作で言えば、読み飛ばすべきブロックはそもそもGPUへ転送されない。
GPUはワンチップに数千コアを搭載し、強烈な並列処理能力を持っているとはいえ、「何もしない」に比べれば圧倒的に遅い。そのため、同じ集計処理を行うにしても、予めBRINインデックスを用いてある程度の範囲の絞り込みができた方が有利である事は間違いない。

なぜ時系列データに有効なのか?

PG-StromでBRINインデックスへ対応するというモチベーションは、基本的にはIoT系ワークロードで使われるデータに対する最適化である。

これらのデータには以下のような特徴がある。

  • レコードにはタイムスタンプが付与される
  • 一度DBに挿入されたデータは(滅多に)更新されない

単純なテーブルへのINSERTを続けていくとやがてブロック(= 8KB)にレコードが収まり切らなくなり、PostgreSQLは新しいブロックを割当て、さらにレコードを追加していくという動作になる。

タイムスタンプの付与とDBへの挿入は多少のタイムラグがあるとはいえ、そうそう大きなズレが生じるわけではない。そうすると、あるブロックに記録されているタイムスタンプの値はかなり近しい値のものでまとまって物理的に保存されているという事になる。

すると、ある一定範囲の最大値/最小値だけをインデックスに保存しておくBRINインデックスであっても、相当範囲の絞り込みが可能であるという事になる。

実際、ymd列の順にINSERTしたdtテーブルのスキャン時に使われるBRINインデックスのビットマップを表示させてみると、以下のようになる。
ブロック番号で言うと 995~1328 番までが2018年のデータを含んでおり、他のブロックは読み飛ばして構わないという事が分かる。

postgres=# EXPLAIN (analyze, buffers)
                      SELECT * FROM dt WHERE ymd BETWEEN '2018-01-01' AND '2018-12-31';
INFO:  BRIN-index (dt_ymd_idx) range_sz = 128
INFO:       0: ffffffff ffffffff ffffffff ffffffff
INFO:     128: ffffffff ffffffff ffffffff ffffffff
INFO:     256: ffffffff ffffffff ffffffff ffffffff
INFO:     384: ffffffff ffffffff ffffffff ffffffff
INFO:     512: ffffffff ffffffff ffffffff ffffffff
INFO:     640: ffffffff ffffffff ffffffff ffffffff
INFO:     768: ffffffff ffffffff ffffffff ffffffff
INFO:     896: 00000007 ffffffff ffffffff ffffffff
INFO:    1024: 00000000 00000000 00000000 00000000
INFO:    1152: 00000000 00000000 00000000 00000000
INFO:    1280: ffffffff ffffffff ffff0000 00000000
INFO:    1408: ffffffff ffffffff ffffffff ffffffff
INFO:    1536: ffffffff ffffffff ffffffff ffffffff
INFO:    1664: ffffffff ffffffff ffffffff ffffffff
INFO:    1792: ffffffff ffffffff ffffffff ffffffff
INFO:    1920: ffffffff ffffffff ffffffff ffffffff
INFO:    2048: ffffffff ffffffff ffffffff ffffffff
INFO:    2176: ffffffff ffffffff ffffffff ffffffff
INFO:    2304: ffffffff ffffffff ffffffff ffffffff
INFO:    2432: ffffffff ffffffff ffffffff ffffffff
INFO:    2560: ffffffff ffffffff ffffffff ffffffff
INFO:    2688: ffffffff ffffffff ffffffff ffffffff
INFO:    2816: ffffffff ffffffff ffffffff ffffffff
INFO:    2944: ffffffff ffffffff ffffffff ffffffff
INFO:    3072: ffffffff ffffffff ffffffff ffffffff
INFO:    3200: ffffffff ffffffff ffffffff ffffffff
INFO:    3328: ffffffff ffffffff ffffffff ffffffff
INFO:    3456: ffffffff ffffffff ffffffff ffffffff
INFO:    3584: 00000000 00000007 ffffffff ffffffff

JOINおよびGROUP BYでの対応

PG-StromにはSCAN→JOINやSCAN→GROUP BY間のデータ移動を省略するため、これらの処理を実行するGpuJoinやGpuPreAgg自身がテーブルスキャンも実行するというモードがある。
BRINインデックスによって範囲を絞り込める場合、これらのケースでも同様に機能しI/O量を削減する。

SCAN+JOINの合体ケース

postgres=# EXPLAIN (analyze, buffers) SELECT * FROM dt NATURAL JOIN t1 NATURAL JOIN t2 WHERE ymd BETWEEN '2018-01-01' AND '2018-12-31';
                                                             QUERY PLAN
--------------------------------------------------------------------------
 Custom Scan (GpuJoin) on dt  (cost=56759.17..56759.17 rows=4541187 width=126)
                                                  (actual time=486.777..1235.942 rows=4545204 loops=1)
   Outer Scan: dt  (cost=96534.45..179544.65 rows=4541187 width=44)
                            (actual time=78.232..379.588 rows=6477696 loops=1)
   Outer Scan Filter: ((ymd >= '2018-01-01'::date) AND (ymd <= '2018-12-31'::date))
   Rows Removed by Outer Scan Filter: 15564
   BRIN cond: ((ymd >= '2018-01-01'::date) AND (ymd <= '2018-12-31'::date))
   BRIN skipped: 424704
   Depth 1: GpuHashJoin  (plan nrows: 4541187...4541187, actual nrows: 6462132...6462132)
            HashKeys: dt.aid
            JoinQuals: (dt.aid = t1.aid)
            KDS-Hash (size plan: 10.78MB, exec: 10.78MB)
   Depth 2: GpuHashJoin  (plan nrows: 4541187...4541187, actual nrows: 6462132...6462132)
            HashKeys: dt.bid
            JoinQuals: (dt.bid = t2.bid)
            KDS-Hash (size plan: 10.78MB, exec: 10.78MB)
   Buffers: shared hit=1956 read=42560
   ->  Seq Scan on t1  (cost=0.00..1935.00 rows=100000 width=45)
                                   (actual time=0.018..37.770 rows=100000 loops=1)
         Buffers: shared hit=935
   ->  Seq Scan on t2  (cost=0.00..1935.00 rows=100000 width=45)
                                   (actual time=0.012..37.352 rows=100000 loops=1)
         Buffers: shared hit=935
 Planning time: 1.594 ms
 Execution time: 2053.291 ms
(21 rows)

SCAN+GROUP BYの合体ケース

postgres=# EXPLAIN (analyze, buffers)
                      SELECT cat,count(*) FROM dt
                     WHERE ymd BETWEEN '2018-01-01' AND '2019-12-31'
                GROUP BY cat;
                                                       QUERY PLAN
--------------------------------------------------------------------------
 GroupAggregate  (cost=8271.68..8273.76 rows=26 width=12)
                              (actual time=727.366..727.385 rows=26 loops=1)
   Group Key: cat
   Buffers: shared hit=92 read=85056
   ->  Sort  (cost=8271.68..8272.14 rows=182 width=12)
                  (actual time=727.358..727.360 rows=26 loops=1)
         Sort Key: cat
         Sort Method: quicksort  Memory: 26kB
         Buffers: shared hit=92 read=85056
         ->  Custom Scan (GpuPreAgg) on dt  (cost=8262.58..8264.85 rows=182 width=12)
                                                                     (actual time=727.294..727.301 rows=26 loops=1)
               Reduction: Local
               Outer Scan: dt  (cost=4000.00..4011.99 rows=9067906 width=4)
                                        (actual time=62.124..718.351 rows=9107840 loops=1)
               Outer Scan Filter: ((ymd >= '2018-01-01'::date) AND (ymd <= '2019-12-31'::date))
               Rows Removed by Outer Scan Filter: 17367
               BRIN cond: ((ymd >= '2018-01-01'::date) AND (ymd <= '2019-12-31'::date))
               BRIN skipped: 382208
               Buffers: shared hit=92 read=85056
 Planning time: 0.773 ms
 Execution time: 1118.730 ms
(17 rows)

*1:「BRINインデックス」だと、若干、馬から落馬した、頭痛が痛い感があるものの、収まりが悪いので"BRINインデックス"と記載します。

*2:デフォルト値。変更可