【重新发现PostgreSQL之美】- 14 bloom 布隆过滤器索引

背景

场景:

分析业务, 任意字段、任意维度组合, 组合等值查询.

where a=? and b=? or c=? . 其他组合 ab ac ad bc bd bcd bdef def ... 每个字母代表一个字段.

在电商、金融等拖拽式实时分析场景中尤为常见.

挑战:

由于查询维度非常多, 完全不可控, 如果每个维度都预计算, 会导致结果数据量指数级增加.

如果为每个查询维度都创建一个索引, 那么会有N!+1个索引. 例如5个字段的任意组合有121种, 需要建121个索引, 完全不现实.

PG 解决方案:

使用bloom布隆过滤索引. 每个value被hash计算后映射到若干个bit位, 这些bit位被设置为1表示包含这个value.

一个索引即可满足任意维度的组合等值搜索.

https://www.postgresql.org/docs/14/bloom.html

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#20210320210326_02md---postgresql-14-preview---brin-%E5%85%B8%E5%9E%8Biot-%E6%97%B6%E5%BA%8F%E5%9C%BA%E6%99%AF-%E5%9D%97%E7%BA%A7%E7%B4%A2%E5%BC%95%E6%94%AF%E6%8C%81-bloom-filter---%E9%9A%8F%E6%9C%BA%E5%A4%A7%E9%87%8Fdistinct-value-%E7%AD%89%E5%80%BC%E6%9F%A5%E8%AF%A2 202103/20210326_02.md  《PostgreSQL 14 preview - BRIN (典型IoT 时序场景) 块级索引支持 bloom filter - 随机,大量distinct value, 等值查询》

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#20201120201128_04md---postgresql-bloom-%E7%B4%A2%E5%BC%95%E5%8E%9F%E7%90%86 202011/20201128_04.md  《PostgreSQL bloom 索引原理》

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#20191120191130_01md---uid%E7%BC%96%E7%A0%81%E4%BC%98%E5%8C%96---%E7%94%A8%E6%88%B7%E7%94%BB%E5%83%8F%E5%89%8D%E7%BD%AE%E8%A7%84%E5%88%99-bloom-%E5%9B%BA%E5%AE%9A%E7%AE%97%E6%B3%95%E7%AD%89 201911/20191130_01.md  《UID编码优化 - 用户画像前置规则 (bloom, 固定算法等)》

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#20181020181003_02md---postgresql-bloom-filter-index-%E6%89%A9%E5%B1%95-for-bigint 201810/20181003_02.md  《PostgreSQL bloom filter index 扩展 for bigint》

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#20180420180409_01md---postgresql-11-preview---bloom-filter-%E8%AF%AF%E6%8A%A5%E7%8E%87%E8%AF%84%E4%BC%B0%E6%B5%8B%E8%AF%95%E5%8F%8A%E5%A6%82%E4%BD%95%E9%99%8D%E4%BD%8E%E8%AF%AF%E6%8A%A5---%E6%9A%A8bloom-filter%E5%BA%94%E7%94%A8%E4%BA%8Eheap%E4%B8%8Eindex%E7%9A%84%E4%B8%80%E8%87%B4%E6%80%A7%E6%A3%80%E6%B5%8B 201804/20180409_01.md  《PostgreSQL 11 preview - bloom filter 误报率评估测试及如何降低误报 - 暨bloom filter应用于HEAP与INDEX的一致性检测》

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#20180320180323_05md---postgresql-11-preview---brin%E7%B4%A2%E5%BC%95%E6%8E%A5%E5%8F%A3%E5%8A%9F%E8%83%BD%E6%89%A9%E5%B1%95bloom-filtermin-max%E5%88%86%E6%AE%B5 201803/20180323_05.md  《PostgreSQL 11 preview - BRIN索引接口功能扩展(BLOOM FILTER、min max分段)》

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#20160520160523_01md---postgresql-96-%E9%BB%91%E7%A7%91%E6%8A%80-bloom-%E7%AE%97%E6%B3%95%E7%B4%A2%E5%BC%95%E4%B8%80%E4%B8%AA%E7%B4%A2%E5%BC%95%E6%94%AF%E6%92%91%E4%BB%BB%E6%84%8F%E5%88%97%E7%BB%84%E5%90%88%E6%9F%A5%E8%AF%A2 201605/20160523_01.md  《PostgreSQL 9.6 黑科技 bloom 算法索引，一个索引支撑任意列组合查询》

https://github.com/digoal/blog/blob/master/202106/20210605_07.md#postgresql-%E8%AE%B8%E6%84%BF%E9%93%BE%E6%8E%A5