601
ComputeColStats UDF中 近似算法的介紹
一，前麵的話
表和列的統計信息對CBO的結果有著極大地影響，能夠高效和準確的收集統計信息是極其重要的。但高效和準確是矛盾的，更準確的統計信息往往需要更多的計算，我們能做的是在高效和準確之間找到更好的平衡。接下來的內容是關於目前在ComputeColStats中用的一些近似算法。
二，收集的內容
目前針對列主要會收集以下統計信息：
cntRows ： 列中總數據個數，包括nulll值
avgColLen ：列的平均長度
maxColLEN ：列的最大長度
minValue ：列的最小值
maxValue ：列的最大值
numNulls ：列中null值個數
numFalses ：如果boolean型，false值的個數
numTrues ：如果boolean型，true值的個數
countDistinct ：不同值的個數
topK ：topk值的個數，數據傾斜的標誌
一般說來除了countDistinct 和topK 以外的統計信息基本上消耗資源並不大（minValue和maxValue存在大量比較，也會消耗不少資源），問題主要集中在countDistinct 和topK上。下麵要描述的近似算法也是主要針對這兩個點。
三，countDistinct 實現
算法：Flajolet-Martin
論文見：https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.3869&rep=rep1&type=pdf
簡介
對於n個object，如果Hash結果中，結尾（或開頭）連續0的長度的最大值是m，那麼，可以估計唯一的object的數據量是2^m個。
假設有一個非常好的hash函數，能夠將object哈希成一個二進製數0101……，並且非常均勻的打散到二進製空間。如果有8個唯一的object，將它們全部Hash之後，結果按照概率應該有4個object的Hash值以0結尾，這4個Hash值又應該有2個結尾是00，這2個中又有1個結尾是000。
采用多個獨立的hash函數，每個hash函數分別計算最長0比特序列，然後求平均值，減少誤差。
hash函數的個數基本上就決定了Flajolet-Martin算法的效率和準確度，後麵有針對不同hash函數個數的測試結果。
四，topK實現
算法：Space-Saving
偽代碼：
五，基本性能測試
結論：
１，Base Stats對性能也是存在影響的，主要是minValue和maxValue的計算，尤其是collen較長的情況下
２，一般說來distinct相對topK會更慢些，除非在collen較長的時候，topK也是基於比較來的
３，隨著列個數的增加，收集stats消耗的時間也線性的增加
４，distinct的計算基於hash，而topK的計算基於比較，所以前者對collen並不敏感
六，不同hash函數個數執行效率的測試
結論：
基本上隨著hash函數個數的增加線性的增長
七，不同hash函數個數準確性的測試
結論：
hash函數個數增加到32個後，準確率基本能滿足需求
八，不同hash函數個數的測試總結
結論：選擇32個hash函數計算distinct，平衡執行效率及準確性
九，sample算法的選擇
１，必要性：
基於前麵對執行效率的測試，為了避免對任務產生過大的影響，Sample是一定要做的
２，Sample算法的要求：
效率，隨機
３，Sample的選擇：
采用buildin的sample函數實現
前提是假設數據分布是隨機的
４，Sample的影響：
對某些stats基本沒影響，比如說avgColLen，maxColLen，minValue，maxValue
對某些stats有些影響，比如說cntRows， numNulls，numFalses，numTrues，topK
對countDistinct影響比較大，並且countDistinct也更加重要，需要特別注意
５，Sample後countDistinct的處理：
根據Sample的countDistinct預測完整數據的countDistinct，采樣，擬合
基本思路如下圖：
希望通過對sample內的數據進行采樣，利用這些采樣點描繪全部數據的形態，達到基本準確預測全部數據distinct的結果。這是個美好的願望，在sample的數據相對較少的時候，總有些情況下sample下的形態跟完整數據的形態存在較大的差異，此時的誤差會比較大。
十，不同sample比例執行效率的測試
采樣比例在1/100後執行時間差距不大，此時最大的消耗在數據讀取上，而不針對distinct的計算。
十一，不同sample比例準確性的測試
針對表meta.m_fuxi_instance表中的列project_name，odps_inst_id做了些測試，結果如上。看起來1/50的結果還是可以接受的。
多說一句，對於distinct來說，並不需要完全的正確，10倍以內的差距目前來說是可以接受的，這也是我們可以通過采樣來提高效率的前提。
十二，按sample比例為1/25為例的計算結果
執行時間和準確率基本都可以滿足現在需求
十三，後續的工作
對於準確率的提升是後續需要做的事情之一，這關鍵還是如何在sample裏麵找帶更有代表性的點來預測全部數據的形態。但，要作好心理準備，對於某些場景來說，可能就找不到這樣的方法，需要接受一定範圍的誤差。
最後更新：2017-07-24 18:02:36