BloomFilter 索引

索引原理

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 查询加速的目的。

使用场景

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

提示

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

仅对 IN 和 = 之外的查询没有效果，比如 !=, NOT INT, >, < 等
不支持对 Tinyint、Float、Double 类型的列建 BloomFilter 索引。
对低基数字段的加速效果很有限，比如 “性别” 字段仅有两种值，几乎每个数据块都会包含所有取值，导致 BloomFilter 索引失去意义。

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

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

使用语法

建表时创建 BloomFilter 索引

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

PROPERTIES (
"bloom_filter_columns" = "column_name1,column_name2"
);

查看 BloomFilter 索引

SHOW CREATE TABLE table_name;

已有表增加、删除 BloomFilter 索引

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

为 column_name3 增加 BloomFilter 索引

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

删除 column_name1 的 BloomFilter 索引

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

使用示例

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

创建 BloomFilter 索引

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

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"
);

索引原理​

使用场景​

使用语法​

建表时创建 BloomFilter 索引​

查看 BloomFilter 索引​

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

使用示例​

创建 BloomFilter 索引​