跳转至

3.3.4 BloomFilter 索引

1 索引原理

BloomFilter 索引是基于 BloomFilter 的一种跳数索引。它的原理是利用 BloomFilter 跳过等值查询指定条件不满足的数据块，达到减少 I/O 查询加速的目的。

BloomFilter 是由 Bloom 在 1970 年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求 100% 正确的场合， BloomFilter 有以下特点：

  • 空间效率高的概率型数据结构，用来检查一个元素是否在一个集合中。

  • 对于一个元素检测是否存在的调用， BloomFilter 会告诉调用者两个结果之一：可能存在或者一定不存在。

BloomFilter 是由一个超长的二进制位数组和一系列的哈希函数组成。二进制位数组初始全部为 0 ，当给定一个待查询的元素时，这个元素会被一系列哈希函数计算映射出一系列的值，所有的值在位数组的偏移量处置为 1 。

下图所示出一个 m=18, k=3 （ m 是该 Bit 数组的大小， k 是 Hash 函数的个数）的 BloomFilter 示例。集合中的 x,y,z 三个元素通过 3 个不同的哈希函数散列到位数组中。当查询元素 w 时，通过 Hash 函数计算之后只要有一个位为 0 ，因此 w 不在该集合中。但是反过来全部都是 1 只能说明可能在集合中、不能肯定一定在集合中，因为 Hash 函数可能出现 Hash 碰撞。

反过来如果某个元素经过哈希函数计算后得到所有的偏移位置，若这些位置全都为 1 ，只能说明可能在集合中、不能肯定一定在集合中，因为 Hash 函数可能出现 Hash 碰撞。这就是 BloomFilter “假阳性”，因此基于 BloomFilter 的索引只能跳过不满足条件的数据，不能精确定位满足条件的数据。

Doris BloomFilter 索引以数据块（ page ）为单位构建，每个数据块存储一个 BloomFilter 。写入时，对于数据块中的每个值，经过 Hash 存入数据块对应的 BloomFilter 。查询时，根据等值条件的值，判断每个数据块对应的 BloomFilter 是否包含这个值，不包含则跳过对应的数据块不读取，达到减少 I/O 查询加速的目的。

2 使用场景

BloomFilter 索引能够对等值查询（包括 = 和 IN ）加速，对高基数字段效果较好，比如 userid 等唯一 ID 字段。

Tip

BloomFilter 的使用有下面一些限制：

  • 对 IN 和 = 之外的查询没有效果，比如 != ， NOT INT ， > ， < 等

  • 不支持对 Tinyint 、 Float 、 Double 类型的列建 BloomFilter 索引。

  • 对低基数字段的加速效果很有限，比如“性别”字段仅有两种值，几乎每个数据块都会包含所有取值，导致 BloomFilter 索引失去意义。

如果要查看某个查询 BloomFilter 索引效果，可以通过 Query Profile 中的相关指标进行分析。

  • BlockConditionsFilteredBloomFilterTime 是 BloomFilter 索引消耗的时间

  • RowsBloomFilterFiltered 是 BloomFilter 过滤掉的行数，可以与其他几个 Rows 值对比分析 BloomFilter 索引过滤效果

3 使用语法

3.1 建表时创建 BloomFilter 索引

由于历史原因， BloomFilter 索引定义的语法与倒排索引等通用 INDEX 语法不一样。 BloomFilter 索引通过表的 PROPERTIES "bloom_filter_columns" 指定哪些字段建 BloomFilter 索引，可以指定一个或者多个字段。

SQL
1
2
3
PROPERTIES (
"bloom_filter_columns" = "column_name1,column_name2"
);

3.2 查看 BloomFilter 索引

SQL
1
SHOW CREATE TABLE table_name;

3.3 已有表增加、删除 BloomFilter 索引

通过 ALTER TABLE 修改表的 bloom_filter_columns 属性来完成。

为 column_name3 增加 BloomFilter 索引

SQL
1
ALTER TABLE table_name SET ("bloom_filter_columns" = "column_name1,column_name2,column_name3");

删除 column_name1 的 BloomFilter 索引

SQL
1
ALTER TABLE table_name SET ("bloom_filter_columns" = "column_name2,column_name3");

4 使用示例

下面通过实例来看看 Doris 怎么创建 BloomFilter 索引。

4.1 创建 BloomFilter 索引

Doris BloomFilter 索引的创建是通过在建表语句的 PROPERTIES 里加上 "bloom_filter_columns"="k1,k2,k3" ，这个属性， k1,k2,k3 是要创建的 BloomFilter 索引的 Key 列名称，例如下面对表里的 saler_id,category_id 创建了 BloomFilter 索引。

SQL
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
CREATE TABLE IF NOT EXISTS sale_detail_bloom  (
    sale_date date NOT NULL COMMENT "销售时间",
    customer_id int NOT NULL COMMENT "客户编号",
    saler_id int NOT NULL COMMENT "销售员",
    sku_id int NOT NULL COMMENT "商品编号",
    category_id int NOT NULL COMMENT "商品分类",
    sale_count int NOT NULL COMMENT "销售数量",
    sale_price DECIMAL(12,2) NOT NULL COMMENT "单价",
    sale_amt DECIMAL(20,2)  COMMENT "销售总金额"
)
Duplicate  KEY(sale_date, customer_id,saler_id,sku_id,category_id)
DISTRIBUTED BY HASH(saler_id) BUCKETS 10
PROPERTIES (
"replication_num" = "1",
"bloom_filter_columns"="saler_id,category_id"
);