使用 PolarDB 开源版 bloom filter index 实现任意字段组合条件过滤

简介: 背景PolarDB 的云原生存算分离架构, 具备低廉的数据存储、高效扩展弹性、高速多机并行计算能力、高速数据搜索和处理; PolarDB与计算算法结合, 将实现双剑合璧, 推动业务数据的价值产出, 将数据变成生产力.本文将介绍使用 PolarDB 开源版 bloom filter index 实现任...

1. 背景

PolarDB 的云原生存算分离架构, 具备低廉的数据存储、高效扩展弹性、高速多机并行计算能力、高速数据搜索和处理; PolarDB与计算算法结合, 将实现双剑合璧, 推动业务数据的价值产出, 将数据变成生产力.

本文将介绍使用 PolarDB 开源版 bloom filter index 实现任意字段组合条件过滤

测试环境为macOS+docker, PolarDB部署请参考如何用 PolarDB 证明巴菲特的投资理念 - 包括PolarDB简单部署

2. 原理

任意字段组合条件过滤, 这种操作通常出现在数据分析场景, 例如BI分析师, 根据需要过滤数, 但是通常需要大量试错, 所以需求就变成了任意组合.

为了加速任意字段过滤, 需要对每一种组合创建索引, 当然PolarDB PG也支持多个btree index的bitmap scan, 所以只需要在每个字段上都创建一个索引即可. 但是即使是这样, 弊端依旧存在:

  • 每列索引加起来占用空间也是比较大的,

  • 而且索引越多, 对dml操作带来的rt就越大, 影响写入吞吐.

为了解决这个问题, bloom filter应运而生, 一个索引, 支持所有字段任意组合条件过滤, (注意, bloom filter仅支持等值组合(原理见下面)).

  • bloom filter 为N bit的hash value,

  • 每个值经过hash后, 映射到hash value中的n个bit内. 例如2个bit, hello (11)映射到1,8, world (11)映射到2,8.

查询hello是否存在时, 只需要判断对应bit上的值是否和hash value一致, 即可.

bloom 的 lossy特性: 不存在 一定 不存在, 表示有map bit=0的, 不存在表示这条记录不包含这个value. 存在 不一定 存在, 表示map bits=1, 但是这些bits可能有其他columns value映射过去的1(你也可以理解为bit冲突), 所以需要二次recheck才能判断一定存在.

为什么会产生bit冲突?

  • 例如80个bit, 存储32列的值, 每列2个bit. hash时, 不同column value 可能会同时mapping到某一个位置的bit. 字段越多, 冲突概率越大.

不管怎么样, bloom filter这种方法在任意字段组合查询的使用中还是非常廉价高效的.

3. 场景模拟和架构设计实践

创建测试表, 写入1000万条记录

=# 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=16.971..16.971 rows=0 loops=1)  
   Filter: ((i2 = 898732) AND (i5 = 123451))  
   Rows Removed by Filter: 100000  
 Planning Time: 0.346 ms  
 Execution Time: 16.988 ms  
(5 rows)  

创建bloom index, 覆盖6个字段, 仅仅消耗1.5MB. 查询性能提升近50倍.

create extension bloom ;

=# 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.388..0.388 rows=0 loops=1)  
   Recheck Cond: ((i2 = 898732) AND (i5 = 123451))  
   Rows Removed by Index Recheck: 29  
   Heap Blocks: exact=28  
   ->  Bitmap Index Scan on bloomidx  (cost=0.00..1792.00 rows=2 width=0) (actual time=0.356..0.356 rows=29 loops=1)  
         Index Cond: ((i2 = 898732) AND (i5 = 123451))  
 Planning Time: 0.099 ms  
 Execution Time: 0.408 ms  
(8 rows)  

改成普通btree索引, 每个字段创建1个, 总共6个索引. 多个字段组合查询会采用bitmap and|or scan. 效率最高, 但是占用空间巨大, 同时对写入吞吐性能影响较大.

=# 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.028..0.029 rows=0 loops=1)  
   Recheck Cond: ((i5 = 123451) AND (i2 = 898732))  
   ->  BitmapAnd  (cost=24.34..24.34 rows=2 width=0) (actual time=0.027..0.027 rows=0 loops=1)  
         ->  Bitmap Index Scan on btreeidx5  (cost=0.00..12.04 rows=500 width=0) (actual time=0.026..0.026 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.491 ms  
 Execution Time: 0.055 ms  
(9 rows)  

4. 参考

作者介绍
目录