時系列データ／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 condやBRIN 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 |当然、読み飛ばすブロック数は検索条件によって変わり、例えば、日付範囲を２倍にした下記の例では（データをランダムに生成した事もあり）読み飛ばしたブロック数は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)
