BloomFilter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合,BloomFilter有以下特点:
布隆过滤器实际上是由一个超长的二进制位数组和一系列的哈希函数组成。二进制位数组初始全部为0,当给定一个待查询的元素时,这个元素会被一系列哈希函数计算映射出一系列的值,所有的值在位数组的偏移量处置为1。
下图所示出一个 m=18, k=3 (m是该Bit数组的大小,k是Hash函数的个数)的Bloom Filter示例。集合中的 x、y、z 三个元素通过 3 个不同的哈希函数散列到位数组中。当查询元素w时,通过Hash函数计算之后因为有一个比特为0,因此w不在该集合中。
那么怎么判断某个元素是否在集合中呢?同样是这个元素经过哈希函数计算后得到所有的偏移位置,若这些位置全都为1,则判断这个元素在这个集合中,若有一个不为1,则判断这个元素不在这个集合中,就是这么简单!
布隆过滤器索引使用非常广泛,在大数据组件HBase就提供了布隆过滤器,它允许你对存储在每个数据块的数据做一个反向测试。当某行被请求时,通过布隆过滤器先检查该行是否不在这个数据块,布隆过滤器要么确定回答该行不在,要么回答它不知道。这就是为什么我们称它是反向测试。
布隆过滤器同样也可以应用到行里的单元上,当访问某列标识符时可以先使用同样的反向测试。但布隆过滤器也不是没有代价,存储这个额外的索引层次会占用额外的空间,布隆过滤器随着它们的索引对象数据增长而增长,所以行级布隆过滤器比列标识符级布隆过滤器占用空间要少。当空间不是问题时,它们可以帮助你榨干系统的性能潜力。
Doris 的 BloomFilter 索引需要通过建表的时候指定,或者通过表的 ALTER 操作来完成。Bloom Filter本质上是一种位图结构,用于快速的判断一个给定的值是否在一个集合中,这种判断会产生小概率的误判,即如果返回false,则一定不在这个集合内。而如果范围true,则有可能在这个集合内。
BloomFilter索是以Block(1024行)为粒度创建的,每1024行中,指定列的值作为一个集合生成一个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 example_db.example_bloom_index_tbl (
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"
);
查看我们在表上建立的BloomFilter索引命令如下:
SHOW CREATE TABLE <table_name>;
执行之后,查看对应建表语句PROPERTIES中是否有"bloom_filter_columns"配置项。
mysql> SHOW CREATE TABLE example_db.example_bloom_index_tbl\G;
*************************** 1. row ***************************
Table: example_bloom_index_tbl
Create Table: CREATE TABLE `example_bloom_index_tbl` (
`sale_date` date NOT NULL COMMENT '销售时间',
`customer_id` int(11) NOT NULL COMMENT '客户编号',
`saler_id` int(11) NOT NULL COMMENT '销售员',
`sku_id` int(11) NOT NULL COMMENT '商品编号',
`category_id` int(11) NOT NULL COMMENT '商品分类',
`sale_count` int(11) NOT NULL COMMENT '销售数量',
`sale_price` decimal(12, 2) NOT NULL COMMENT '单价',
`sale_amt` decimal(20, 2) NULL COMMENT '销售总金额'
) ENGINE=OLAP
DUPLICATE KEY(`sale_date`, `customer_id`, `saler_id`, `sku_id`, `category_id`)
COMMENT 'OLAP'
PARTITION BY RANGE(`sale_date`)
(PARTITION P_202111 VALUES [('2021-11-01'), ('2021-12-01')))
DISTRIBUTED BY HASH(`saler_id`) BUCKETS 10
PROPERTIES (
"replication_allocation" = "tag.location.default: 3",
"bloom_filter_columns" = "category_id, saler_id",
"in_memory" = "false",
"storage_format" = "V2",
"disable_auto_compaction" = "false"
);
1 row in set (0.00 sec)
删除BloomFilter索引即将索引列从bloom_filter_columns属性中移除,命令如下:
ALTER TABLE <db.table_name> SET ("bloom_filter_columns" = "");
删除表 example_db.example_bloom_index_tbl 中的布隆索引:
mysql> alter table example_db.example_bloom_index_tbl set ("bloom_filter_columns" = "");
Query OK, 0 rows affected (0.05 sec)
以上语句执行完成后,可以执行 "show create table example_db.example_bloom_index_tbl\G;"查看建表语句参数中已经没有布隆过滤器的配置参数。
修改BloomFilter索引即修改表对应的 bloom_filter_columns属性,语法如下:
ALTER TABLE <db.table_name> SET ("bloom_filter_columns" = "k1,k3");
现在给表example_db.example_bloom_index_tbl中 category_id 列创建布隆过滤器,操作如下:
ALTER TABLE <db.table_name> SET ("bloom_filter_columns" = "k1,k3");
现在给表example_db.example_bloom_index_tbl中 category_id 列创建布隆过滤器,操作如下:
mysql> alter table example_db.example_bloom_index_tbl set ("bloom_filter_columns"="category_id");
Query OK, 0 rows affected (0.04 sec)
mysql> show create table example_db.example_bloom_index_tbl\G;
*************************** 1. row ***************************
...
(PARTITION P_202111 VALUES [('2021-11-01'), ('2021-12-01')))
DISTRIBUTED BY HASH(`saler_id`) BUCKETS 10
PROPERTIES (
"replication_allocation" = "tag.location.default: 3",
"bloom_filter_columns" = "category_id",
"in_memory" = "false",
"storage_format" = "V2",
"disable_auto_compaction" = "false"
);
... ...