本文主要介紹云數據庫 SelectDB 版中的BloomFilter索引以及使用時的注意事項。
背景信息
BloomFilter是由Bloom在1970年提出的一種多哈希函數映射的快速查找算法。通常應用在一些需要快速判斷某個元素是否屬于集合，但是并不嚴格要求100%正確的場合。
BloomFilter有以下特點：
空間效率高的概率型數據結構，用來檢查一個元素是否在一個集合中。
對于一個檢測元素是否存在的調用請求，BloomFilter會告訴調用者兩個結果之一：可能存在或者一定不存在。
缺點是存在誤判的，告訴您可能存在，但不一定真實存在。
BloomFilter是由一個超長的二進制位數組和一系列的哈希函數組成。二進制位數組初始全部為0，當給定一個待查詢的元素時，這個元素會被一系列哈希函數計算映射出一系列的值，所有的值在位數組的偏移量處置為1。
下圖所示出一個m=18，k=3（m是該Bit數組的大小，k是Hash函數的個數）的BloomFilter示例。集合中的x、y、z三個元素通過3個不同的哈希函數散列到位數組中。當查詢元素w時，通過哈希函數計算之后因為有一個比特為0，因此w不在該集合中。
如何判斷某個元素是否在集合中，同樣是這個元素經過哈希函數計算后得到所有的偏移位置，若這些位置全都為1，則判斷這個元素在這個集合中，若有一個不為1，則判斷這個元素不在這個集合中。
BloomFilter索引管理
創建索引
BloomFilter本質上是一種位圖結構，用于快速的判斷一個給定的值是否在一個集合中。這種判斷會產生小概率的誤判。即如果返回false，則一定不在這個集合內；而如果返回true，則有可能在這個集合內。
BloomFilter索引是以Block為粒度創建的。每個Block中，指定列的值作為一個集合生成一個BloomFilter索引條目，用于在查詢是快速過濾不滿足條件的數據。
云數據庫 SelectDB 版的BloomFilter索引可以通過建表的時候指定，或者通過表的ALTER操作來完成。創建BloomFilter索引，是通過在建表語句的PROPERTIES里加上"bloom_filter_columns"="k1,k2,k3"這個配置屬性來進行的。其中，k1,k2,k3是要創建的BloomFilter索引的Key列名稱。
例如對表sale_detail_bloom創建BloomFilter索引saler_id、category_id。
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(customer_id) buckets 3
PROPERTIES("bloom_filter_columns"="saler_id, category_id");查看索引
查看表中建立的BloomFilter索引，語法如下。
SHOW CREATE TABLE <table_name>;以sale_detail_bloom表為例，示例如下。
SHOW CREATE TABLE sale_detail_bloom;查詢結果如下。
+-------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table | Create Table |
+-------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| sale_detail_bloom | CREATE TABLE `sale_detail_bloom` (
`sale_date` datev2 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` decimalv3(12, 2) NOT NULL COMMENT '單價',
`sale_amt` decimalv3(20, 2) NULL COMMENT '銷售總金額'
) ENGINE=OLAP
DUPLICATE KEY(`sale_date`, `customer_id`, `saler_id`, `sku_id`, `category_id`)
COMMENT 'OLAP'
DISTRIBUTED BY HASH(`customer_id`) BUCKETS 3
PROPERTIES (
"bloom_filter_columns" = "category_id, saler_id",
"light_schema_change" = "true"
); |
+-------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.03 sec)修改索引
修改索引即為修改表的bloom_filter_columns屬性，語法如下。
ALTER TABLE <db.table_name> SET ("bloom_filter_columns" = "k1,k3");刪除索引
刪除索引即為刪除索引列中bloom_filter_columns屬性，語法如下。
ALTER TABLE <db.table_name> SET ("bloom_filter_columns" = "");查看索引變更進度
創建、修改、刪除索引是異步過程，可通過命令查看任務進度，語法如下。
SHOW ALTER TABLE COLUMN;BloomFilter使用場景
滿足以下幾個條件時可以考慮對某列建立BloomFilter索引。
非前綴過濾時。
查詢會根據該列高頻過濾，而且查詢條件大多是
in和=過濾。不同于Bitmap，BloomFilter適用于高基數列，比如UserID。因為如果創建在低基數的列上，比如“性別”列，則每個Block幾乎都會包含所有取值，導致BloomFilter索引失去意義。
示例
要查找一個占用100 Byte存儲空間大小的短行，一個64 KB的HFile數據塊應該包含(64*1024)/100=655.53行，大約700行。如果僅能在整個數據塊的起始行鍵上建立索引，那么它是無法提供細粒度的索引信息的。因為要查找的行數據可能會落在該數據塊的行區間上，可能行數據沒在該數據塊上，也可能是表中根本就不存在該行數據，或者是行數據在另一個HFile里，甚至在MemStore里。以上這幾種情況，都會導致從磁盤讀取數據塊時帶來額外的IO開銷，也會濫用數據塊的緩存，當面對一個巨大的數據集且處于高并發讀時，會嚴重影響性能。
因此，HBase提供了布隆過濾器，它允許您對存儲在每個數據塊的數據做一個反向測試。當某行被請求時，通過布隆過濾器先檢查該行是否不在這個數據塊，布隆過濾器確定回答該行不在，或者回答它不知道。這就是我們稱的反向測試。布隆過濾器也可以應用到行里的單元上，當訪問某列標識符時可以先使用同樣的反向測試。
但布隆過濾器是有代價的，存儲這個額外的索引層次會占用額外的空間。布隆過濾器隨著它們的索引對象數據增長而增長，所以行級布隆過濾器比列標識符級布隆過濾器占用空間要少。當空間不是問題時，它們可以幫助您充分利用系統的性能潛力。
SelectDB的BloomFilter索引可以通過建表的時候指定，或者通過表的ALTER操作來完成。
BloomFilter索引也是以Block為粒度創建的。每個Block中，指定列的值作為一個集合生成一個BloomFilter索引條目，用于在查詢時快速過濾不滿足條件的數據。
注意事項
列類型為Tinyint、Float、Double不支持創建BloomFilter索引。
Bloom Filter索引只對
in和=過濾查詢有加速效果。查看某個查詢是否命中了BloomFilter索引，可以通過查詢的Profile信息查看。