PostgreSQL bloom

bloom索引在其WITH子句中接受下列參數(shù)：

這是一個創(chuàng)建布魯姆索引的例子：

CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
       WITH (length=80, col1=2, col2=2, col3=4);

該索引是用長度為 80 位的簽名所創(chuàng)建，其中屬性 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

在這個大表上的順序掃描需要很長時間：

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                              QUERY PLAN                                              
-------------------------------------------------------------------?-----------------------------------
 Seq Scan on tbloom  (cost=0.00..2137.14 rows=3 width=24) (actual time=15.480..15.480 rows=0 loops=1)
   Filter: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Filter: 100000
 Planning Time: 0.340 ms
 Execution Time: 15.501 ms
(5 rows)

即使定義了btree索引，結(jié)果將仍然是順序掃描：

=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
 pg_size_pretty
----------------
 3976 kB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                              QUERY PLAN                                              
-------------------------------------------------------------------?-----------------------------------
 Seq Scan on tbloom  (cost=0.00..2137.00 rows=2 width=24) (actual time=12.604..12.604 rows=0 loops=1)
   Filter: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Filter: 100000
 Planning Time: 0.155 ms
 Execution Time: 12.617 ms
(5 rows)

在處理這類搜索時，bloom 比 btree 更好：

=# 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
----------------
 1584 kB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                     QUERY PLAN                                                      
-------------------------------------------------------------------?--------------------------------------------------
 Bitmap Heap Scan on tbloom  (cost=1792.00..1799.69 rows=2 width=24) (actual time=0.384..0.384 rows=0 loops=1)
   Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
   Rows Removed by Index Recheck: 26
   Heap Blocks: exact=26
   ->  Bitmap Index Scan on bloomidx  (cost=0.00..1792.00 rows=2 width=0) (actual time=0.350..0.350 rows=26 loops=1)
         Index Cond: ((i2 = 898732) AND (i5 = 123451))
 Planning Time: 0.122 ms
 Execution Time: 0.407 ms
(8 rows)

現(xiàn)在，btree 搜索的主要問題是，當(dāng)搜索條件不約束前幾個索引列時，btree 的效率不好。對于 btree 更好的策略是在每一列上創(chuàng)建一個獨立的索引。那么規(guī)劃器將選擇這樣的計劃：

=# CREATE INDEX btreeidx1 ON tbloom (i1);
CREATE INDEX
=# CREATE INDEX btreeidx2 ON tbloom (i2);
CREATE INDEX
=# CREATE INDEX btreeidx3 ON tbloom (i3);
CREATE INDEX
=# CREATE INDEX btreeidx4 ON tbloom (i4);
CREATE INDEX
=# CREATE INDEX btreeidx5 ON tbloom (i5);
CREATE INDEX
=# CREATE INDEX btreeidx6 ON tbloom (i6);
CREATE INDEX
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                                        QUERY PLAN                                                         
-------------------------------------------------------------------?--------------------------------------------------------
 Bitmap Heap Scan on tbloom  (cost=24.34..32.03 rows=2 width=24) (actual time=0.032..0.033 rows=0 loops=1)
   Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
   ->  BitmapAnd  (cost=24.34..24.34 rows=2 width=0) (actual time=0.029..0.030 rows=0 loops=1)
         ->  Bitmap Index Scan on btreeidx5  (cost=0.00..12.04 rows=500 width=0) (actual time=0.029..0.029 rows=0 loops=1)
               Index Cond: (i5 = 123451)
         ->  Bitmap Index Scan on btreeidx2  (cost=0.00..12.04 rows=500 width=0) (never executed)
               Index Cond: (i2 = 898732)
 Planning Time: 0.537 ms
 Execution Time: 0.064 ms
(9 rows)

盡管這個查詢運行起來比在其中任一單個索引上都快，但是我們在索引尺寸上付出了代價。 每一個單列 btree 索引占用 2 MB，因此總的空間會超過 12 MB，這是bloom索引所使用的空間的 8 倍。

用于布魯姆索引的操作符類只要一個用于被索引數(shù)據(jù)類型的哈希函數(shù)以及一個用于搜索的等值操作符。這個例子展示了用于text數(shù)據(jù)類型的操作符類定義：

CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
    OPERATOR    1   =(text, text),
    FUNCTION    1   hashtext(text);