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. 参考
《PostgreSQL 14 preview - BRIN (典型IoT 时序场景) 块级索引支持 bloom filter - 随机,大量distinct value, 等值查询》
《PostgreSQL 11 preview - bloom filter 误报率评估测试及如何降低误报 - 暨bloom filter应用于HEAP与INDEX的一致性检测》
《PostgreSQL 11 preview - BRIN索引接口功能扩展(BLOOM FILTER、min max分段)》
《PostgreSQL 应用开发解决方案最佳实践系列课程 - 7. 标签搜索和圈选、相似搜索和圈选、任意字段组合搜索和圈选系统》
《PostgreSQL+MySQL 联合解决方案 - 第10课视频 - 任意字段、维度组合搜索(含GIS、数组、全文检索等属性)》
《PostgreSQL 设计优化case - 大宽表任意字段组合查询索引如何选择(btree, gin, rum) - (含单个索引列数超过32列的方法)》
《PostgreSQL ADHoc(任意字段组合)查询(rums索引加速) - 非字典化,普通、数组等组合字段生成新数组》
- 《PostgreSQL ADHoc(任意字段组合)查询 与 字典化 (rum索引加速) - 实践与方案1 - 菜鸟 某仿真系统》
- 《PostgreSQL 如何高效解决 按任意字段分词检索的问题 - case 1》