1. 首頁 > 生活百科 > >

4 探究Presto SQL引擎-統計計數( 三 )

生活百科


文章插圖
關于數學 ， 確切地說是概率論的知識點，還有很多 。例如估計方法是有偏估計還是無偏估計？，估計的方差和標準差是多大？這里涉及到較為底層的概率論知識，就先略過 。
略過數學知識，關鍵的問題在于，我們如何將待基數統計問題跟上面的伯努利實驗建立聯系？這兩個點之間的橋梁就是Hash函數 。第一次見識到Hash函數還能這樣用，確實大開眼界 。

4 探究Presto SQL引擎-統計計數

文章插圖
對于相同的數，通過hash函數生成的散列值是相同的，這就進行了排重 。當然不排除不同的數據生成同樣的hash值，形成沖突 。由于選取的hash函數例如MurmurHash3沖突率低 ， 可以忽略這個因素 。
實際上，由于Hash函數生成的二進制串通常具備均勻的特性，所以Hash函數生成的二進制串可以視為拋擲硬幣的結果 。
對于一個待進行基數統計的集合(例如一個表中符合條件的字段值)，為了降低估計的錯誤率，我們分成m組 。某個值歸屬于哪個組由hash函數生成結果對應的前幾位決定，剩下的二進制串用于計算當前輪伯努利實驗第一次出現正面時拋擲的次數，記為p 。
所以算法描述如下：
4 探究Presto SQL引擎-統計計數

文章插圖
簡單來說就是統計每個組最大的p, 然后用現成的公式計算結果即到達預估的結果 。
三、分布式計數核心流程對于Hadoop中的入門案例wordcount，可以發現如果用Presto SQL表達如下(以tpch數據集customer表name字段為例)：
select w, count(1) cnt from (select split(name,'#') words from customer) t1 cross joinUNNEST(t1.words) AS t (w)group by w;可以看出相比大段的代碼，SQL處理對用于來說要簡單的多 。無論是哪種表達方式，核心點就是分組統計 。
在MapReduce框架核心流程如下：
4 探究Presto SQL引擎-統計計數

文章插圖
那么在Presto，其執行流程是什么樣呢？
4 探究Presto SQL引擎-統計計數

文章插圖
從邏輯上，都是類似的 。先分組聚合，然后匯總聚合 。
四、基數統計在Presto中的落地對于基數統計問題Presto支持兩種實現方式 。一種是追求精確的count distinct; 另一種是提供近似統計的approx_distinct 。
count distinct的核心細節
以SQL ：select count(distinct id) from hive_table 為例 。
4 探究Presto SQL引擎-統計計數

文章插圖
即以id為主key, 對數據進行hash分發，進行部分聚合，最終整體聚合 。依然是map-reduce的思路 ， 只不過數據按id進行了分發 。
aprox_distinct的核心細節
4 探究Presto SQL引擎-統計計數

文章插圖
這里就免去了基于id的hash分發策略 。所以也減少了一個stage 。至于approx_distinct的內部細節，基礎框架airlift中，封裝了HyperLogLog算法的實現，采用的函數是MurMurHash3算法 ， 生成64位散列值 。前6位用于計算當前散列值所在分組m 。實現過程中還有一個很有意思的細節：基于待統計的數據量，實現中同時采用了Linear Count算法和HyperLogLog算法 。
五、業務建議通過上面的分析，我們可以發現高基數統計是一個非常消耗內存的操作 ， 特別是在分布式系統背景下，不僅消耗內存，而且涉及大量網絡數據傳輸 。如果分析對應的業務場景，可以提供近似值而非精確值，那么就能大幅度降低系統消耗和響應時間 ， 提升用戶體驗 。或者在設計產品的時候，對于一些場景的計數 ， 可以優先提供近似估計，如果用戶確實需要精確計數，那么在管理好用戶響應時間預期下，再提供查詢精確值的接口 。
理解了精確統計和近似統計的細節及各種優缺點，處理問題的思路就會更開闊 。例如：在設計存儲索引時，我們可以優先使用HyperLogLog統計一個字段的基數近似值，如果得到的結果不是高基數，那么我們可以對字段構建bitmap索引 ， 借此提升數據處理的效率 。
在《我們如何走到今天：重塑世界的6項創新 》一書中有這樣一個觀點讓人記憶深刻：我們衡量越精確，控制的能力就越強 。但是它沒有說的是，衡量越精確，成本就越大 。
參考：
  1. 《數據庫系統實現》
  2. A Linear-Time Probabilistic Counting Algorithm for Database Applications
  3. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

    推薦閱讀