bloomは、ブルームフィルターによるインデックスのアクセスメソッドを提供します。
ブルームフィルターは、空間効率の良いデータ構造で、ある要素が集合のメンバーかどうかをテストするのに用いられます。 インデックスのアクセスメソッドとして使用する場合、インデックス作成時に大きさが決まるシグネチャーを使って、条件を満たさないタプルを高速に除外することができます。
シグネチャーはインデックス化された属性を非可逆的に表現するもので、その性質上、擬陽性の結果を出すことがあります。 すなわち、集合の中にない要素が、集合の中にあると報告するかもしれません。 ですから、インデックスの検索結果は、ヒープエントリ中の実際の属性値を使って、必ず再検査しなければなりません。 シグネチャーが大きくなれば擬陽性の可能性が下がるので不必要なヒープの検索は減りますが、もちろんそうなるとインデックスが大きくなるので、スキャンが遅くなります。
この種のインデックスは、テーブルに多数の属性があり、その任意の組み合わせを検索する問い合わせを実行するときにもっとも有効です。 伝統的なbtreeインデックスはブルームインデックスよりも高速ですが、可能なすべての問い合わせをサポートするためには多数のbtreeインデックスが必要なのに対し、ブルームインデックスでは、たった一つのブルームインデックスだけで事足ります。 しかし、ブルームインデックスでは等価検索だけをサポートすることに注意してください。 btreeインデックスでは、等価だけでなく、範囲検索も実行できます。
bloomインデックスは、WITH句中の以下のパラメータを受け付けます。
lengthビット単位の個々のシグネチャー（インデックスエントリー）の長さ。
デフォルトは80ビットで、最大値は4096です。
col1 — col32各インデックスカラムに対して生成するビット数。
各々のパラメータ名は、管理対象のインデックスカラムの番号です。
デフォルトは2ビットで、最大値は4095です。
実際には使用されないインデックスカラムについてのパラメータは無視されます。
ブルームインデックスの作成例です。
CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
WITH (length=80, col1=2, col2=2, col3=4);このインデックスは80ビット長のシグネチャーで作成され、属性i1とi2は2ビットに、i3は4ビットにマップされます。
length、col1、col2指定はデフォルト値を使っているので、省略しても構いません。
より完全なブルームインデックスの定義と使用法を示します。 比較のために、これと同等のbtreeインデックスも併せて示します。 ブルームインデックスはbtreeインデックスよりもかなり小さく、また、より良い性能を発揮できるかもしれません。
=# CREATE TABLE tbloom AS
SELECT
(random() * 1000000)::int as i1,
(random() * 1000000)::int as i2,
(random() * 1000000)::int as i3,
(random() * 1000000)::int as i4,
(random() * 1000000)::int as i5,
(random() * 1000000)::int as i6
FROM
generate_series(1,10000000);
SELECT 10000000
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));
pg_size_pretty
----------------
153 MB
(1 row)
=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
pg_size_pretty
----------------
387 MB
(1 row)これだけ大きなテーブルに対するシーケンシャルスキャンは長い時間がかかります。
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..213694.08 rows=1 width=24) (actual time=1445.438..1445.438 rows=0 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 10000000
Planning time: 0.177 ms
Execution time: 1445.473 ms
(5 rows)
ですので、もし利用可能ならば、プランナは通常、インデックススキャンを選択します。 btreeインデックスですと、このような結果になります。
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Index Only Scan using btreeidx on tbloom (cost=0.56..298311.96 rows=1 width=24) (actual time=445.709..445.709 rows=0 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Heap Fetches: 0
Planning time: 0.193 ms
Execution time: 445.770 ms
(5 rows)
ブルームは、btreeよりもこの種の検索をうまく扱います。
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=178435.39..178439.41 rows=1 width=24) (actual time=76.698..76.698 rows=0 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Index Recheck: 2439
Heap Blocks: exact=2408
-> Bitmap Index Scan on bloomidx (cost=0.00..178435.39 rows=1 width=0) (actual time=72.455..72.455 rows=2439 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Planning time: 0.475 ms
Execution time: 76.778 ms
(8 rows)
比較的大きい擬陽性の数に注意してください。
2439行が検索され、ヒープからアクセスされました。
しかし、クエリにマッチした行はありませんでした。
シグネチャー長をより大きく指定することにより、擬陽性を減らすことができます。
この例では、length=200と指定してインデックスを作成することにより、擬陽性が55まで減りました。
しかし、インデックスのサイズは（306 MBへと）2倍になってしまいました。
結果として、このクエリは（全体で125 msへと）遅くなってしまいました。
btree検索の主要な問題は、検索条件が、先頭（そしてそれに続く）インデックスカラムを使用しないときに、効率が悪くなってしまうことです。 btreeでは各々のカラムに対して別々のインデックスを作るのが良い戦略です。 するとプランはこのような選択をします。
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=9.29..13.30 rows=1 width=24) (actual time=0.148..0.148 rows=0 loops=1)
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
-> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.145..0.145 rows=0 loops=1)
-> Bitmap Index Scan on tbloom_i5_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.089..0.089 rows=10 loops=1)
Index Cond: (i5 = 123451)
-> Bitmap Index Scan on tbloom_i2_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.048..0.048 rows=8 loops=1)
Index Cond: (i2 = 898732)
Planning time: 2.049 ms
Execution time: 0.280 ms
(9 rows)個別のインデックスのどれかを使うよりもこのクエリはずっと高速に実行できますが、インデックスのサイズに大きなペナルティーを払わなければなりません。 各々の単一カラムのbtreeインデックスは、214MBになります。 ですから、全体で必要なスペースは1.2GBを超えます。 ブルームインデックスで使用するスペースの8倍以上です。
ブルームインデックスの演算子クラスには、インデックス対象のデータ型に対するハッシュ関数と、検索のための等価演算子だけが必要です。
この例では、textデータ型に対する演算子クラスの定義を示します。
CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
OPERATOR 1 =(text, text),
FUNCTION 1 hashtext(text);
このモジュールには、int4とtextに対する演算子クラスだけが含まれています。
=演算子だけが検索ではサポートされています。
しかし、配列の和、積演算のサポートを将来追加することは可能です。
Teodor Sigaev <teodor@postgrespro.ru>,
Postgres Professional, Moscow, Russia
Alexander Korotkov <a.korotkov@postgrespro.ru>,
Postgres Professional, Moscow, Russia
Oleg Bartunov <obartunov@postgrespro.ru>,
Postgres Professional, Moscow, Russia