Bloom过滤器索引

布隆过滤器是一项非常有用的Data-skipping技术。该技术可以快速判断表文件中是否包含要查询的数据,如果不包含就及时跳过该文件,从而减少扫描的数据量,提升查询性能。

说明

详细内容可参考Databricks官网文章:Bloom过滤索引

如果在表的某列上创建了布隆过滤器索引,并且使用where col = "something"作为查询条件,那么在扫描表中文件时,我们可以使用布隆过滤器索引得出两种结论:文件中肯定不包含col = "something"的行,或者文件有可能包含col = "something"的行。

  • 当得出文件中肯定不包含col = "something"的行的结论时,就可以跳过该文件,从而减少扫描的数据量,提升查询性能。

  • 当得出文件中可能包含col = "something"的行的结论时,引擎才会去处理该文件。注意,这里仅仅是判断该文件中可能包含目标数据。布隆过滤器定义了一个指标,用于描述出现判断失误的概率,即判断文件中包含需要查询的数据,而实际上该文件并不包含目标数据的概率,并称之为FPP(False Positive Probability: 假阳性概率)。

Databricks支持文件级Bloom过滤器,如果在表的某些列创建了布隆过滤器索引,那么该表的每个表文件都会关联一个 Bloom 筛选器索引文件,索引文件存储在 _delta_log 同级目录下的 _delta_index 目录中。在读取表文文件之前,Databricks会检查索引文件,根据上面的步骤判断表文件中是否包含需要查询的数据,如果不包含则直接跳过,否则再进行处理。image

布隆过滤器索引的使用

创建布隆过滤器索引

CREATE BLOOMFILTER INDEX
ON TABLE table_name
FOR COLUMNS(col_name OPTIONS (fpp=0.1, numItems=50000000))
  • fpp:假阳性概率,假阳性概率越低,过滤越准确,但索引文件越大(使用更多的位来判断数据是否存在于文件中)

  • numItems:该列可能出现的值的种类

布隆过滤器支持对:byte、short、int、long、float、double、date、timestamp和string类型的列建立索引。需要注意的是:布隆过滤器不会对null值建立索引,因此如果你的查询条件中使用 where x is null 类似的语句,则即使在x列建立了布隆过滤器索引,该索引也不会生效。此外,嵌套的列也不支持布隆过滤器索引。

删除布隆过滤器索引

DROP BLOOMFILTER INDEX ON TABLE table_name FOR COLUMNS(col_name);

查看表上已建立的布隆过滤器索引

DESCRIBE EXTENDED table_name;

使用案例

创建表:创建一张测试表,该表包括ID以及ID % 50000000的sha加密。

CREATE OR REPLACE TABLE bloom_test (
  id   BIGINT NOT NULL,
  str1 STRING NOT NULL,
  sha  STRING NOT NULL,
  sha1 STRING NOT NULL,
  sha2_256 STRING NOT NULL,
  row_hash_too_big STRING NOT NULL,
  row_hash STRING NOT NULL
)
USING DELTA
location "oss://databricks-delta-demo/bloom_filter"

在该测试表的列 sha 上创建布隆过滤器索引。在sha列有50,000,000种可能出现的值,假阳性的概率为0.1 (即判断某数据存在于文件中,但实际并不在的概率)。

CREATE BLOOMFILTER INDEX
ON TABLE bloom_test
FOR COLUMNS(sha OPTIONS (fpp=0.1, numItems=50000000))

生成测试数据:

WITH sample (
  SELECT
    id,
    'windows.exe' as str1,
    monotonically_increasing_id() mono_id,
    hash(id) hash,
    sha (cast(id % 50000000 as string)) sha,
    sha1(cast(id % 50000000 as string)) sha1,
    sha2(cast(id as string), 256)    sha2_256
  from
    RANGE(0, 1000000000, 1, 448)  -- start, end, step, numPartitions
)
INSERT INTO bloom_test 
SELECT id, 
  str1, 
  sha,
  sha1,
  sha2_256,
  sha2(concat_ws('||',id, str1, mono_id, hash, sha, sha1, sha2_256),512) row_hash_too_big,
  sha2(concat_ws('||',id, str1, mono_id, hash, sha, sha1, sha2_256),256) row_hash
FROM sample

查询没有创建布隆过滤器索引的列:耗时300s。

SELECT count(*) FROM bloom_test 
WHERE sha1 = 'b2f9544427aed7b712b209fffc756c001712b7ca'

查询创建了布隆过滤器索引的列:耗时90s。

SELECT count(*) FROM bloom_test 
WHERE sha = 'b6589fc6ab0dc82cf12099d1c2d40ab994e8410c'

查询根本不存在于表中的数据:耗时60s(不需要扫描任何数据,仅需要查询布隆过滤器索引)。

SELECT count(*) FROM bloom_test 
WHERE sha = 'b6589fc6ab0dc82cf12099d1c2d40ab994e8410c_'

从上面的结果可以看出,在150GB的数据上,创建布隆过滤器相比未创建布隆过滤器能带来3倍以上的性能提升,当我们查询的数据能跳过的文件越多,这种性能提升更加显著。

禁用布隆过滤器索引

Databricks默认启用布隆过滤器索引,如果需要禁用布隆过滤器索引,可以通过设置配置项spark.databricks.io.skipping.bloomFilter.enabled 为false实现。