在Postgres中使用概率滤波器(布卢姆滤波器或布谷鸟滤波器)过滤行

Question

我有一个大表(~1B行)，在单个btree列上有一个bytea索引(~20 1B，但适合内存)。

我想用概率过滤器(例如，布卢姆过滤器或布谷鸟过滤器)从客户端发送一个查询，并让数据库扫描索引，收集可能与过滤器匹配的所有行。这应该返回所有可能的匹配和一些错误的结果。其目标是避免提供请求的全部项目列表(为了隐私-客户端有一个列表，但不能与服务器共享)。

我看到Postgres有一个用于创建基于bloom模块筛选器的索引的btree，但我不认为它可以用来测试在针对D3索引的查询中提供的布卢姆过滤器。

我想最终的结果是：

SELECT key, value FROM table WHERE matches_filter(key, b'01010101010101');

这里有什么方法可以重用bloom模块中的内部方法吗？或者是否有公开概率过滤函数的扩展？

Answer 1

不管你有多少内存，你都不能有一个20‘t的字节值。最大容量为1GB。而且你不能让btree的索引值接近那么大--但我们不清楚为什么要在讨论创建新的索引类型时指定btree。

您可以做的是使用一个著名的散列函数(如md5或sha256)来消化客户机上的全部值，然后将其截断到有可能发生冲突的长度，然后将截断后的值发送到要搜索的服务器。然后，服务器可以发送所有匹配的全文摘要。(或者可以将完整的文档发回，但如果它们大于1GB，则不发送)。这样，您就可以了解您的文档(或者它的散列摘要)是否已经在数据库中了，但是数据库还没有确切地知道其中的哪一个(如果有的话)是您想要搜索的。一个常规的btree索引对于索引部分就足够了。