最近、人と話すと「BRINってどうなのよ？」と話題になることが増えており、また直近では情報系システムのプロジェクトに参加することが多く、個人的にいろいろと期待している機能の一つだったりします。
というわけで、今回から3回連続で、この「BRINインデックス」について、その仕組みと使いどころを探ってみたいと思います。
全3回は、それぞれ以下の内容になる予定です。
- BRINインデックス, Part 1「BRINインデックスとは何か、その仕組みを探る」
- BRINインデックス, Part 2「BRINインデックスの性能を探る」
- BRINインデックス, Part 3「BRINインデックスの使いどころを探る」
■BRINインデックスとは
「BRIN」は「Block-Range INdex」の略で、「複数のデータブロックを束ねて、その最大値／最小値をサマリとして保持するタイプのインデックス」です。
まずはマニュアルを見てみましょう。
BRIN is designed for handling very large tables in which certain columns have some natural correlation with their physical location within the table.ということのようです。何となく、概要と使いどころが浮かんだ感じでしょうか。
BRINは、非常に大規模なテーブルで、かつ特定のカラムのデータとレコードのテーブル内の物理的な順序が自然に相関しているテーブルを扱うために設計されています。
A block range is a group of pages that are physically adjacent in the table; for each block range, some summary info is stored by the index.
"block range" とは、テーブルの内部で近接しているページ（ブロック）のグループのことで、各 block range のサマリ情報をインデックスに保持します。
For example, a table storing a store's sale orders might have a date column on which each order was placed, and most of the time the entries for earlier orders will appear earlier in the table as well;
例えば、売上情報を保持しているテーブルには、おそらく注文が発生した日付のカラムがあるでしょうし、早い日付のレコードはテーブルの最初の方に存在しているでしょう。
以下でもう少し詳しく見てみます。
■BRINインデックスの仕組み
まず、BRINインデックスの前に、通常のPostgreSQLの仕組みをおさらいしておきます。
PostgreSQLのテーブルファイルは、8kBごとの「ブロック」と呼ばれる領域が連続して構成されています。
通常のBTreeインデックスの場合、これらのブロックの内部に存在する個々のレコードの場所を指し示すデータ構造を持っています。
しかし、データ量の多いテーブルの場合、BTreeインデックスのサイズが大きくなってしまう上に、特に「一部の範囲のレコードをまとめて取り出す」時には、さほど効率的とは言えません。大容量になったBtreeを律儀にスキャンしていく必要があるからです。
そこでBRINインデックスでは、（デフォルトでは）128ブロックをひとつの塊「ブロックレンジ（block range）」として扱い、そのblock rageの中での最小値および最大値だけをインデックスに保持します。
このようにすることで、「このブロックレンジの中には、XXXからYYYまでのレコードが存在している」ということをざっくり把握することができるようになるのです。
Oracleなどに詳しい人は、「エクステント単位でMin/Max値を持つ」とイメージすれば分かりやすいのではないかと思います。
検索する時、エクステント単位で最小値・最大値を確認することができれば、欲しい範囲のレコードが含まれないエクステントは丸ごと読み飛ばすことができ、結果として読み込みI/Oを減らすことができるようになります。当然、インデックスのサイズも小さくなります。（エクステントごとにmin/maxしか持たないため）
実は、商用DBMSでは同様の機能はいくつか実装されており、NetezzaではZone Maps、Oracle ExadataだとExadata Storage Index、IBM DB2 BLUアクセラレータだとData Skippingという名称で実装されています。
- DB2 BLU Acceleration Japan Unofficial Wiki > FAQ Top > 機能のFAQ > 4.データスキッピングって何ですか?
- Oracle Exadata: Smart Scans Meet Storage Indexes
- Understanding Netezza Zone Maps - IBM PureData-Netezza Developer Network (NDN) アイデア・ブログ - IBM PureData-Netezza Developer Network (NDN)
OLTP系のシステムで、Btreeの代わりに使うようなインデックスではありませんので、その点はご注意ください。
■BRINインデックスのデータ構造
次に、BRINインデックスのデータ構造を見てみます。
ここでは、DBT-3の注文明細テーブル lineitem の注文日カラム l_shipdate に作成したBRINインデックス i_l_shipdate を、ソースツリーの中にあるREADMEも参照しつつ、contribのpageinspectツールを使って見ていきます。
dbt3_brin=# create extension pageinspect;
CREATE EXTENSION
dbt3_brin=# \d lineitem
Table "public.lineitem"
Column | Type | Modifiers
-----------------+-----------------------+-----------
l_orderkey | integer | not null
l_partkey | integer |
l_suppkey | integer |
l_linenumber | integer | not null
l_quantity | real |
l_extendedprice | real |
l_discount | real |
l_tax | real |
l_returnflag | character(1) |
l_linestatus | character(1) |
l_shipdate | date |
l_commitdate | date |
l_receiptdate | date |
l_shipinstruct | character(25) |
l_shipmode | character(10) |
l_comment | character varying(44) |
Indexes:
"pk_lineitem" PRIMARY KEY, btree (l_orderkey, l_linenumber)
"i_l_commitdate" brin (l_commitdate)
"i_l_orderkey" brin (l_orderkey)
"i_l_orderkey_quantity" brin (l_orderkey, l_quantity)
"i_l_partkey" brin (l_partkey)
"i_l_receiptdate" brin (l_receiptdate)
"i_l_shipdate" brin (l_shipdate)
"i_l_suppkey" brin (l_suppkey)
"i_l_suppkey_partkey" brin (l_partkey, l_suppkey)
dbt3_brin=#
BRINインデックスファイルには、3種類のページ（ブロック）があります。メタページ（meta）とレンジマップ（revmap）、通常のインデックスデータ（regular）です。
dbt3_brin=# select relpages from pg_class where relname = 'i_l_shipdate';
relpages
----------
5
(1 row)
dbt3_brin=#
このBRINインデックスは5ページあるようですので、それぞれのページタイプを見てみましょう。
dbt3_brin=# select i,brin_page_type(get_raw_page('i_l_shipdate', i)) from generate_series(0,4) i;
i | brin_page_type
---+----------------
0 | meta
1 | revmap
2 | regular
3 | regular
4 | regular
(5 rows)
dbt3_brin=#
すると、最初のページがメタページで、次がレンジマップ、残りの3ページが通常のインデックスページであることが分かります。ここでメタページの内容を見てみます。
dbt3_brin=# select * from brin_metapage_info(get_raw_page('i_l_shipdate', 0));
magic | version | pagesperrange | lastrevmappage
------------+---------+---------------+----------------
0xA8109CFA | 1 | 128 | 1
(1 row)
dbt3_brin=#
すると、BRINインデックスのバージョンが「1」、各ブロックレンジに含まれるページ数（pagesperrange）が128、最後のレンジマップページが「1番目のブロック」であることが分かります。このpagesperrangeの128という数字によって、このBRINインデックスでは128ブロックを1まとまりとして、その最大値最小値を保持している、ということが分かります。
次にレンジマップのデータを見てみます。
dbt3_brin=# select * from brin_revmap_data(get_raw_page('i_l_shipdate', 1));
pages
---------
(2,1)
(2,2)
(2,3)
(2,4)
(2,5)
(...snip...)
(4,15)
(4,16)
(4,17)
(0,0)
(0,0)
(0,0)
(...snip...)
(0,0)
(0,0)
(0,0)
(0,0)
(1360 rows)
dbt3_brin=#
レンジマップのデータは、「N番目のblock rangeのサマリデータが、このインデックスのどのブロックの何番目のタプルに入っているか」というポインタ情報を保持しています。上記の例で見ると、テーブルの1番最初のblock range（128ブロック分）のサマリデータは、このBRINインデックスの2番目のブロックの1番目のタプルに入っている、と読みます。
最後に、実際のサマリデータを見てみます。
dbt3_brin=# select * from brin_page_items(get_raw_page('i_l_shipdate', 2), 'i_l_shipdate');
itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | value
------------+--------+--------+----------+----------+-------------+----------------------------
1 | 0 | 1 | f | f | f | {1992-01-02 .. 1992-01-28}
2 | 128 | 1 | f | f | f | {1992-01-27 .. 1992-02-08}
3 | 256 | 1 | f | f | f | {1992-02-08 .. 1992-02-16}
4 | 384 | 1 | f | f | f | {1992-02-16 .. 1992-02-23}
(...snip...)
405 | 51712 | 1 | f | f | f | {1995-05-15 .. 1995-05-18}
406 | 51840 | 1 | f | f | f | {1995-05-18 .. 1995-05-21}
407 | 51968 | 1 | f | f | f | {1995-05-21 .. 1995-05-23}
408 | 52096 | 1 | f | f | f | {1995-05-23 .. 1995-05-26}
(408 rows)
dbt3_brin=#
0～127番目までのブロック（ブロックレンジ1）には、最小値1992-01-02、最大値1992-01-28のレコードが含まれており、その次のブロックレンジ2（128～255ブロック）には最小値1992-01-27、最大値1992-02-08のレコードが含まれている、と読みます。また、サマリデータには最小値・最大値だけではなく、すべてがNULLであるか、NULLが含まれているか、といったフラグも含まれています。
BRINインデックスは、このようにしてインデックスの中にテーブルのblock rangeごとのサマリデータを保持しています。
■BRINインデックスの実行プラン
最後にBRINインデックスを使った時の実行プランを見てみましょう。
BRINインデックスを張ったカラムを使ってl_shipdateで絞り込んで、件数を数えてみます。
dbt3_brin=# explain select count(*) from lineitem where l_shipdate between '1994-12-01' and '1994-12-31';
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Aggregate (cost=102110.38..102110.39 rows=1 width=0)
-> Bitmap Heap Scan on lineitem (cost=748.32..101932.74 rows=71055 width=0)
Recheck Cond: ((l_shipdate >= '1994-12-01'::date) AND (l_shipdate <= '1994-12-31'::date))
-> Bitmap Index Scan on i_l_shipdate (cost=0.00..730.55 rows=71055 width=0)
Index Cond: ((l_shipdate >= '1994-12-01'::date) AND (l_shipdate <= '1994-12-31'::date))
(5 rows)
dbt3_brin=#
上記のプランを見ると、まずはインデックス（i_l_shipdate）と条件（Index Cond）を使って Bitmap Index Scan で絞り込んだ後、取り出したレコードを再度チェックして（Recheck Cond）で本当に合致するレコードなのかどうかを確認しています。このように、BRINインデックスはあくまでもサマリデータを保持するインデックスなので、インデックスで絞り込んだ後、さらにレコードごとに再度チェックをする必要があるのです。
■まとめ
というわけで、BRINインデックスの第1回は、概要から、その仕組み、実行プランまでを簡単に見てきました。
次回はベンチマークの結果を見ながら、BtreeインデックスとBRINインデックスの違いについて見てみます。
では、また。
0 件のコメント:
コメントを投稿