作者：vivo互聯網用戶運營開發團隊 - Shuai Guangying本篇文章介紹了統計計數的基本原理以及Presto的實現思路，精確統計和近似統計的細節及各種優缺點，并給出了統計計數在具體業務使用的建議 。
系列文章：
- 探究Presto SQL引擎(1)-巧用Antlr
- 【4 探究Presto SQL引擎-統計計數】探究Presto SQL引擎(2)-淺析Join
- 探究Presto SQL引擎(3)-代碼生成
統計在SQL引擎中可謂最基礎、最核心的能力之一 。可能由于它太基礎了，就像排序一樣，我們常常會忽視它背后的原理 。通常的計數是非常簡單的，例如統計文本行數在linux系統上一個wc命令就搞定了 。
除了通常的計數，統計不重復元素個數的需求也非常常見，這種統計稱為基數統計 。對于Presto這種分布式SQL引擎，計數的實現原理值得深入研究，特別是基數統計 。關于普通計數和基數計數，最典型的例子莫過于PV/UV 。
二、基數統計主要算法在SQL語法里面，基數統計對應到count(distinct field)或者aprox_distinct() 。通常做精確計數統計需要用到Set這種數據結構 。通過Set不僅可以獲得數量信息，還能不重不漏地獲取每一個元素 。
Set內部有兩種實現實現原理：Hash和Tree 。
在海量數據的前提下 ， Hash和Tree有一個致命的問題：內存消耗，而且隨著數據量級的增長，內存消耗也是線性增長 。
面對Set內存消耗的問題，通常有兩種思路：
- 一種是選取其他內存占用更小的數據結構，例如bitmap；
- 另一種是放棄精確 ， 從數學上尋求近似解，典型的算法有Linear Count和HyperLogLog 。
2.1.1 位圖向量的構建舉個例子，假設表user記錄如下：
文章插圖
這是很典型的一張數據庫表 。對于表中的字段，如何構建位圖索引呢？以age字段為例：
- S1: 確定字段的取值集合空間: {30,40,50} 一共3個選項 。
- S2: 依次為每個選項構建一個長度為6的bit向量，得到一個3*6的位圖 。3表示字段age的取值基數 ， 6表示記錄數 。
文章插圖
- S3: 基于表設置位圖相應向量值 。例如：age=30的記錄id分別為{1,2,6}，那么在向量1,2,6位置置為1 ， 其他置為0 。得到110001 。
文章插圖
同理，對于name字段，其向量位圖為：
文章插圖
可以看出，如果對于數據表的一個字段，如果記錄數為n且字段的取值基數為m，那么會得到一個m*n的位圖 。
2.1.2 位圖向量的應用有了位圖向量，該如何使用呢？假設查詢SQL為
select count(1) from user where age=40;則取age字段位圖中age=40的向量：110001 。統計其中1的個數，即可得到最終結果 。
假設查詢SQL更復雜一些：
select count(1) from user where age=40 and name='baz'則取age字段位圖中age=40的向量：110001和name='foo'的向量：100100 。兩個向量進行交集運算：
文章插圖
最后統計結果為1 。
關于Bitmap的思想，筆者認為最巧妙的一點就是通過位運算實現了集合運算 。如下圖所示：
文章插圖
在不同的業務場景中，這里的集合可以賦予不同的業務含義 。
2.1.3 位圖向量的優點將字段的篩選變成了向量計算后 ， 會非常節約內存，而且可以通過分段長度編碼等方式對bitmap向量進行壓縮 。而且位運算直接對內存中的二進制位進行操作 ， 執行效率非常高，是性能提升的一大殺器 。
理解了bitmap后，可以發現對于整型字段 ， 可以直接用bitmap進行基數統計 。筆者曾經實驗過，對于3億數據量級使用roaringbitmap工具，bitmap消耗內存約30M ， 而且如果數據分布非常密集內存消耗還有很大的壓縮空間 。唯一的缺點是非數值型字段，需要進行額外的轉換處理 。
推薦閱讀
- 「MySQL高級篇」MySQL之MVCC實現原理&&事務隔離級別的實現
- MongoDB - 簡單了解
- FlinkSql之TableAPI詳解
- 20 基于SqlSugar的開發框架循序漸進介紹-- 在基于UniApp+Vue的移動端實現多條件查詢的處理
- 在FreeSQL中實現「觸發器」和軟刪除功能
- Mysql InnoDB Buffer Pool
- Python 多重繼承時metaclass conflict問題解決與原理探究
- SQL分層查詢
- 「MySQL高級篇」MySQL鎖機制 && 事務
- 17 基于SqlSugar的開發框架循序漸進介紹-- 基于CSRedis實現緩存的處理