BRINを見たのでその時のメモ。

概要

BRIN(Block Range INdex)は、物理的に連続して並んだブロック内のインデックス列の最小値、最大値を保持するインデックス。BRINを用いた検索では、WHERE句の検索条件を満たすブロックの範囲(レンジ)を絞り込みテーブルを検索する。Btreeインデックスだと1行につき1つのインデックスが対応するが、BRINだと複数のブロック毎に一つのインデックスが対応するので、Btreeに比べてインデックスサイズもとても小さくなる傾向がある。他のRDBMSではOracle ExadataのStorage Indexとかが似た特徴を持っていると思う。

BRINはテーブル内のデータの物理的な位置に性能が依存する。例えば、時系列データを追加するだけのテーブルのタイムスタンプ列とかは相性がよく、BRINを使って検索するときには検索するレンジをかなり絞り込むことができる。一方で、更新が多いテーブルとは相性が悪く、BRINを使っても結局テーブルのほぼ全体をスキャンする、という結果になってしまうかもしれない。

インデックスの構造

BRINは3種類のブロックがある:meta page, revmap page, regular page。

0番目のページはmeta page固定。revmapは1番目から連続したブロックが割り当てられる。revmap以降にはregular pageが続き、ここにはmin, maxが格納されたインデックスタプルが入っている。

+-------------+
| meta page   | 0 blk
+-------------+
| revmap      |	1 blk
+-------------+
| revmap      |	2 blk
+-------------+
| revmap      |	3 blk
+-------------+
| revmap      |	4 blk
+-------------+
| reg. page   |	5 blk
+-------------+
| reg. page   |	6 blk
+-------------+
| reg. page   |	7 blk
+-------------+
| reg. page   |	8 blk
+-------------+
| reg. page   |	9 blk
+-------------+
| reg. page   |	10 blk
+-------------+
      :

revmapは連続した領域が必要なので、新しいrevmapのページがほしい場合は、既存のindex pageを別の場所に移動して、空いたページを使う、という感じで変更する。連続したブロックではなくrevmapのブロックのリンクを作ることでも実装可能だが、そうすると検索時に先頭のrevmapブロックから順番に見ていく必要があるので、その点ではこのようにINSERT、UPDATE多少コストはかかるけど連続した領域に割り当てるほうがメリットが大きい。一つのrevmapには(デフォルトだと)1000レンジ分くらいあるので、インデックスタプルの移動が必要なのはそこまで多くないだろう。

Range Map (revmap)

Range Map (revmap)は、Heapのレンジと範囲のマッピング。つまり、「2つ目のレンジにおけるminとmaxは?」を尋ねると「0 ~ 1500」みたいに答えを探すことができる。revmapのエントリはレンジ順に並んでいる。例えばデフォルトで1レンジあたりのブロック数は128なので、0番目のrevmapエントリは、0~127番ブロックに対応していて、次のエントリは128~255番ブロックに対応している、という感じになっている。レンジの幅は一つのインデックス内で固定なので、Heapのブロック番号から必要なrevmapのエントリがわかる。

revmap自体には、レンジの情報(○○番ブロック~△△番ブロック)の情報しかなく、そのレンジにおけるmin, maxの情報はindex pageのタプルにある。そのため、revmapのエントリはこれまでに解説したレンジの情報に加えて、対応するインデックスタプルのを持つ(regular page内のインデックスタプルへのポインタを持っているイメージ)。

更新

新しく行が挿入されたテーブルのブロック番号が、すでに存在するレンジの範囲内であれば、UPDATEやINSERTの処理中にインデックスタプル(Regular Pageにあるタプル)を更新する。存在するレンジになければ(例えば、0~127番ブロックのレンジはあるけど新しく挿入した位置が128番ブロックの時)、UPDATEやINSERTのときに新しいレンジは作らない。新しくレンジを作るにはそのレンジをもう一度読み直してmin, maxを求める必要があるので非同期的に行う。autosummarizeというオプションをインデックスごとに設定できるので、それをONにすると(デフォルトOFF)、非同期的に新しいレンジを作る処理が実行するようになる。もしくはbrin_summarize_new_values()等のSQL関数を使えば手動でも新しいレンジを作ることができる。

pageinspectで挙動を見てみる

テーブルとBRINを準備する:

=# create table t (a int, b text);
CREATE TABLE
=# insert into t select i, chr(i % 1000 + 1) from generate_series(1,100000) i;
INSERT 0 1000000
=# create index a_idx on t using brin (a);
CREATE INDEX

BRINの各ページタイプを確認する。先頭から、meta page、revmap page、 regular pageの順番なのがわかる:

=# with tmp as (select generate_series(0, (pg_relation_size('a_idx') / 8192) - 1) as pageno) select * from tmp, brin_page_type(get_raw_page('a_idx', tmp.pageno::int));
 pageno | brin_page_type
--------+----------------
      0 | meta
      1 | revmap
      2 | regular
(3 rows)

まずはmeta pageを見てみると、バージョンやレンジ毎のブロック数などの情報が入っている:

=# select * from brin_metapage_info(get_raw_page('a_idx', 0));
   magic    | version | pagesperrange | lastrevmappage
------------+---------+---------------+----------------
 0xA8109CFA |       1 |           128 |              1
(1 row)

次にrevmap page。1行が一つのレンジの情報で、対応するインデックスタプルの情報(TID)が入っている。例えば0番目のレンジについての情報(min, max)はTID = (2,1)のタプルにある、という感じ:

=# select * from brin_revmap_data(get_raw_page('a_idx', 1)) limit 10;
 pages
-------
 (2,1)
 (2,2)
 (2,3)
 (2,4)
 (0,0)
 (0,0)
 (0,0)
 (0,0)
 (0,0)
 (0,0)
(10 rows)

最後にregular page。ここに実際のmin, max値が入っている。例えば、0番目のレンジは1 ~ 28928:

=# select * from brin_page_items(get_raw_page('a_idx', 2), 'a_idx');
 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |       value
------------+--------+--------+----------+----------+-------------+-------------------
          1 |      0 |      1 | f        | f        | f           | {1 .. 28928}
          2 |    128 |      1 | f        | f        | f           | {28929 .. 57856}
          3 |    256 |      1 | f        | f        | f           | {57857 .. 86784}
          4 |    384 |      1 | f        | f        | f           | {86785 .. 100000}
(4 rows)

4番目のレンジにタプルを追加してみると、レンジが更新されたことがわかる:

=# insert into t (a) values (1);
INSERT 0 1
=# select * from brin_page_items(get_raw_page('a_idx', 2), 'a_idx');
 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |      value
------------+--------+--------+----------+----------+-------------+------------------
          1 |      0 |      1 | f        | f        | f           | {1 .. 28928}
          2 |    128 |      1 | f        | f        | f           | {28929 .. 57856}
          3 |    256 |      1 | f        | f        | f           | {57857 .. 86784}
          4 |    384 |      1 | f        | f        | f           | {1 .. 100000}

しかし、データを追加しても5番目以降の新しいレンジはINSERTやUPDATE時には作られない:

=# insert into t select i, chr(i % 1000 + 1) from generate_series(1,100000) i; -- 追加したデータは新しいレンジに対応するはず
INSERT 0 100000
=# select * from brin_page_items(get_raw_page('a_idx', 2), 'a_idx'); -- レンジ数は4のまま
 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |      value
------------+--------+--------+----------+----------+-------------+------------------
          1 |      0 |      1 | f        | f        | f           | {1 .. 28928}
          2 |    128 |      1 | f        | f        | f           | {28929 .. 57856}
          3 |    256 |      1 | f        | f        | f           | {57857 .. 86784}
          4 |    384 |      1 | f        | f        | f           | {1 .. 100000}
(4 rows)

手動で新しいレンジを作ることも可能:

=# select brin_summarize_new_values('a_idx'); -- '3'は新しく作ったレンジ数
 brin_summarize_new_values
---------------------------
                         3
(1 row)

=# select * from brin_page_items(get_raw_page('a_idx', 2), 'a_idx');
 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |       value
------------+--------+--------+----------+----------+-------------+-------------------
          1 |      0 |      1 | f        | f        | f           | {1 .. 28928}
          2 |    128 |      1 | f        | f        | f           | {28929 .. 57856}
          3 |    256 |      1 | f        | f        | f           | {57857 .. 86784}
          4 |    384 |      1 | f        | f        | f           | {1 .. 100000}
          5 |    512 |      1 | f        | f        | f           | {15713 .. 44640}
          6 |    640 |      1 | f        | f        | f           | {44641 .. 73568}
          7 |    768 |      1 | f        | f        | f           | {73569 .. 100000}
(7 rows)

次はソースコードを読んでみます。