谓词下推vs布隆过滤器

Question

在寻找大数据上的查询优化时，尤其是在ORC文件上，我遇到了两种可能的谓词下推和Bloom过滤器。

谓词下推帮助我们避免读取不必要的条带，这有助于减少IO，但对我来说，Bloom Filter似乎也有相同的目的，除了以下几点。

对于谓词下推，我们不需要在编写ORC文件时显式创建任何工件，而对于Bloom filters，我们需要在写入ORC文件时配置列。

征求我的建议，让我更好地理解。

谢谢Santosh

Answer 1

布隆过滤器由谓词下推使用。谓词下推主要使用列统计信息来跳过行组并最小化读取的行数。如果使用bloom过滤器，那么谓词下推可以最大限度地减少进一步读取的行数。

Answer 2

因为ORC文件是类型感知的，所以编写器为类型选择最合适的编码，并在写入文件时构建内部索引。

谓词下推使用这些索引来确定需要为特定查询读取文件中的哪些条带，行索引可以将搜索范围缩小到10,000行的特定集合

另请参阅：https://orc.apache.org/docs/index.html

• 谓词下推需要由apache spark

等查询引擎实现。

关于谓词下推的一个很好的定义可以在here中找到，并且：

https://medium.com/microsoftazure/data-at-scale-learn-how-predicate-pushdown-will-save-you-money-7063b80878d7#:~:text=What%20is%20Predicate%20Pushdown%3F,are%20referred%20to%20as%20predicates.&text=It%20can%20improve%20query%20performance,%2FO)%20来自%20存储%20文件

ORC在每个文件中提供三个级别的索引：

1. 文件级别-有关整个文件的每列中的值的统计信息
2. 条带级别-有关每个条带的每列中的值的统计信息
3. 行级别-有关条带

中每组10,000行的每列中的值的统计信息

列统计信息始终包含值的计数以及是否存在空值。大多数其他基元类型包括最小值和最大值，对于数值类型，则包括总和。从Hive 1.2开始，索引可以包括bloom filters，它提供了更具选择性的filter。

https://orc.apache.org/docs/indexes.html

在Spark SQL.中，缺省情况下启用Spark ORC谓词下推

Bloom filters are only useful for equality, not less than or greater than.

布隆筛选器是一种节省空间的概率数据结构，由伯顿·霍华德·布卢姆在1970年提出，布隆过滤器用于测试元素是否为集合中的成员。可能存在误正匹配，但不可能存在假阴性。换句话说，查询返回“possible in set”或“ not in set”。

另请参阅：

https://llimllib.github.io/bloomfilter-tutorial/

https://en.wikipedia.org/wiki/Bloom_filter

https://docs.cloudera.com/runtime/7.2.8/developing-spark-applications/topics/spark-predicate-push-down-optimization.html