bloom filter, bitmap data structure, elasticsearch

因為公司工作的關系，最近在研究 elasticsearch 。很快地，我就一頭栽進了探討 elasticsearch 與 mysql 不同的地方。就用一個常見 SQL 運算來說明好了。

SELECT AVG(age) FROM login WHERE site = 'zzz' AND host = 'kkk';

(a) where 子句的部分，在一些文章中，常稱為 Filter 操作
filter 操作在 elasticsearch 可以做相當的最佳化，因為 elasticsearch 可以使用 bitmap 來做 AND, OR 的運算。而 mysql 只能用 btree 提高查詢效率。當 where 子句的條件有多個 AND 或是 OR 的運算時，btree 比 bitmap 差許多，因為 btree 的索引無法快速地做 AND 或是 OR 的運算。

(b) AVG(age) 函數的部分，在一些文章中，常稱為 Aggregate 操作　
aggregate 操作在 elasticsearch 也會相當的好，因為 elasticsearch 有一個 doc_value 屬性，會讓它成為 column-oriented database。相比 row-oriented 資料庫， column-oriented database 存取的資料量會少非常多。因為只有 aggregate 函數作用的「欄」 (column) 會被存取，同一「列」(row) 的其它「欄」 (columns) 並不會被存取。

然後，我回想起了 bitmap data structure 也在其它地方出現過了：
(1) bloom filter
用法也是差不多，但是多了一個 hash 的運算。將元素的值透過 hash 運算，變成「索引值」 (index) 。就是元素如果存在的話，就會在對應索引值的位元標為 1 ，不存在的話，標記為 0 。
(2) 「編程珠璣」 (programming pearl) 的第一章。講如何用極少的記憶體，排序超大的檔案。由於使用 bitmap 這種資料結構，可以將 counting sort 所需要的資料結構完整地放入主記憶體，效能可以大幅提高。