Doris索引

BloomFilter索引

BloomFilter索引原理

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

下图所示出一个 m=18, k=3 （m是该Bit数组的大小，k是Hash函数的个数）的Bloom Filter示例。集合中的 x、y、z 三个元素通过 3 个不同的哈希函数散列到位数组中（这里因为hash函数是3个，需要散列的3个位值都为1时，才说明在集合中）。当查询元素w时，通过Hash函数计算之后因为有一个比特为0，因此w不在该集合中。

Doris BloomFilter索引及使用场景

Bloom Filter本质上是一种位图结构，用于快速的判断一个给定的值是否在一个集合中。这种判断会产生小概率的误判。即如果返回false，则一定不在这个集合内。而如果范围true，则有可能在这个集合内。

创建BloomFilter索引

Doris BloomFilter索引的创建是通过在建表语句的PROPERTIES里加上”bloom_filter_columns”=”k1,k2,k3”,这个属性，k1,k2,k3是你要创建的BloomFilter索引的Key列名称

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)
PARTITION BY RANGE(sale_date)
(
PARTITION P_202111 VALUES [('2021-11-01'), ('2021-12-01'))
)
DISTRIBUTED BY HASH(saler_id) BUCKETS 10
PROPERTIES (
"replication_num" = "3",
"bloom_filter_columns"="saler_id,category_id",
"dynamic_partition.enable" = "true",
"dynamic_partition.time_unit" = "MONTH",
"dynamic_partition.time_zone" = "Asia/Shanghai",
"dynamic_partition.start" = "-2147483648",
"dynamic_partition.end" = "2",
"dynamic_partition.prefix" = "P_",
"dynamic_partition.replication_num" = "3",
"dynamic_partition.buckets" = "3"
);

查看BloomFilter索引

查看我们在表上建立的BloomFilter索引是使用:

SHOW CREATE TABLE <table_name>

删除BloomFilter索引

ALTER TABLE <db.table_name> SET ("bloom_filter_columns" = "");

修改BloomFilter索引

ALTER TABLE <db.table_name> SET ("bloom_filter_columns" = "k1,k3");

Doris BloomFilter使用场景

满足以下几个条件时可以考虑对某列建立Bloom Filter 索引：

1.首先BloomFilter适用于非前缀过滤。

2.查询会根据该列高频过滤，而且查询条件大多是 in 和 = 过滤。

3.不同于Bitmap, BloomFilter适用于高基数列。比如UserID。因为如果创建在低基数的列上，比如 “性别” 列，则每个Block几乎都会包含所有取值，导致BloomFilter索引失去意义。

Doris BloomFilter使用注意事项

1. 不支持对Tinyint、Float、Double 类型的列建Bloom Filter索引。
2. Bloom Filter索引只对 in 和 = 过滤查询有加速效果。
3. 如果要查看某个查询是否命中了Bloom Filter索引，可以通过查询的Profile信息查看。

Bitmap 索引

Bitmap索引原理

举个例子，给定一块长度是10bit的内存空间，想要依次插入数据4，2，1，3怎么做？

1.给定长度是10的bitmap，每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0

2.把整型数4存入bitmap，对应存储的位置就是下标为4的位置，将此bit置为1

3.把整型数2存入bitmap，对应存储的位置就是下标为2的位置，将此bit置为1

4.把整型数1存入bitmap，对应存储的位置就是下标为1的位置，将此bit置为1

5.把整型数3存入bitmap，对应存储的位置就是下标为3的位置，将此bit置为1


要问此时bitmap里存储了哪些元素？显然是4,3,2,1，一目了然。

Bitmap不仅方便查询，还可以去除掉重复的整型数。

这里有个实际工作中遇到的例子，一个用户数据表，每条用户数据都对应着几百上千个标签，怎么转化成bitmap？

让每一个标签存储包含此标签的所有用户ID，每一个标签都是一个独立的Bitmap

如何查找使用苹果手机的程序员用户？

Doris Bitmap索引使用场景

1.适用于低基数的列上，建议在100到100000之间，如：职业、地市等。基数太高则没有明显优势；基数太低，则空间效率和性能会大大降低。

2.对于特定类型的查询例如count、or、and等逻辑操作因为只需要进行位运算。如：通过类似 select count(*) from table where city = 'beijing' and job = 'teacher' 这种多个条件组合查询场景，如果在每个查询条件列上都建立了bitmap索引，则可以进行高效的位运算，精确定位到需要的数据，数据扫描量。当筛选出的结果集越小，bitmap索引的优势越明显

参考：

Apache Doris索引机制介绍

Bitmap算法介绍