PostgreSQL的9.6黑科技绽放算法索引

PostgreSQL确实是学术界和工业界的璀璨明珠，它总是喜欢将学术界的一些玩意工业化，这次的bloom又是一个代表。

在PG很多的地方都能看到学术的影子，比如pgbench支持产生泊松分布，高斯分布的随机值。

bloomfilter是一个有损过滤器，使用有限的比特位存储一些唯一值集合所产生的bits。

通过这些bits可以满足这样的场景需求，给定一个值，判断这个值是否属于这个集合。

例如

使用所有的值，通过bloomfilter算法生成一个值val。

然后给定一个值例如100，判断100是否在中。

通过bloomfilter可以快速得到，不需要遍历表来得到。

判断方法是使用100和val以及统一的bloom算法。

可能得到的结果是trueorfalse。

true表示100在这里面，false表示100不在这里面。

必须注意，由于bloomfilter是有损过滤器，并且真的不一定为真，但是假的一定为假。

使用customaccessmethods接口定义了一个索引接口bloom，使用到它的特性：真的不一定为真，但是假的一定为假。

目前已实现的场景是，支持=查询，但是这个=会包含一些假的值，所以需要recheck。反过来，它如果要支持也是很方便的，并且不需要recheck。

使用PostgreSQL函数接口也能实现bloom过滤器。

bloom需要m个bit位。

添加元素时，需要k个hash函数，通过每一个hash和传入的值计算得到另一个值（[0,m]）。

得到的值用于设置对应的bit位为1。

例子

创建一个类型，存储bloom。

创建一个空的bloom，设置false值异常设置为TRUE的概率p，设置期望存储多少个唯一值n。

创建一个指纹函数，存储使用K个哈希函数得到的值，存入数组。

添加元素的函数

同样也是设置对应的bit为1

是否包含某元素

测试

以上例子来自pipelinedb文档，用C语言写成聚合函数，可以实现流式计算。

接下来是的例子，9.6是将它做成了索引，而不是聚合。

(如果有朋友想使用pipelinedb的bloom聚合，可以看看PIPELINEDB的代码，PORT过来)

多个字段测试，16个字段，任意测试组合，速度和recheck有关,recheck越少越好。

不仅仅支持and还支持or,只是OR的条件是bitmap的，会慢一些。

任意字段组合查询都能用上这个索引

如果使用其他的索引方法，任意条件组合查询，需要为每一种组合创建一个索引来支持。

而使用bloom索引方法，只需要创建一个索引就够了。

很赞哦!（77）