466
數據蔣堂 | 迭代聚合語法
我們討論過的常規聚合運算如SUM/COUNT和非常規聚合運算如maxp/top，都是事先設計好的聚合函數。但如果我們想實現一個以前沒有定義過的運算怎麼辦？是否可以用已有的語法和函數組合出來？比如想做連乘運算，顯然這也算是一種聚合。
（題外話：連乘可以用exp(SUM(ln(x)))來做，不過這有點耍賴了，而且這還對付不了成員是負數的情況。）
要設計這樣的語法方案，我們來看看這些聚合結果值是如何被程序計算出來的。
SUM：先設置一個初始值0，然後遍曆集合的每個成員，每次將成員值加到初始值上，直到成員被遍曆完。
COUNT：設置初始值0，遍曆集合成員，每次碰到非空成員將初始值加1，直到遍曆完。
AVERAGE：這個不能邊遍曆邊計算了，不過AVERAGE=SUM/COUNT，算是個導出函數，不用考察了。
MAX：設置初始值為無窮小，遍曆集合成員，每碰比初始值更大的成員值則替換初始值，直到遍曆完。
MIN：和MAX一樣，隻是初始值和比較方向是反的。
我們發現，這些基本聚合運算的實現方案都有相同的過程：先設置一個初始值，然後遍曆集合成員，讓當前成員和初始值計算得到一個新的初始值，再進入下一輪循環，直到遍曆完整個集合，那個初始值就變成我們需要聚合值了。
這樣，我們可以設計一個實現迭代計算的聚合函數：
A.iterate( x, a )
以a為初始值遍曆集合A，每次用當前初始值和當前遍曆員計算表達式x，得到的結果替換當前初始值，直到遍曆完成，返回最後的x值。
這裏有個問題，在x中用什麼標識符或符號來表示當前初始值和當前成員。當前成員可以用我們以前討論過的~符號，當前初始值要再找個符號，我們用兩個~來表示。
這樣，前麵那些聚合運算就都可以用這個迭代函數來表示：
A.SUM() = A.iterate( ~~+~, 0 )
A.COUNT() = A.iterate( ~+if(~~,1,0),0 )
A.MAX() = A.iterate( if(~>~~,~,~~), -inf )
A.MIN() = A.iterate( if( ~<~~,~,~~), inf )
連乘當然也很簡單了：A.iterate( ~~*~, 1 )
我們提到過的非常規聚合也可以，比如返回單值的maxp可以寫成
A.maxp(F) = A.iterate( if (~==null || ~.F>>~~.F,~,~~), null ) 這是F表示字段名
但返回集合的情況要麻煩一些：
A.maxp(F) = A.iterate( if(~==null || ~.F>~~.F,~,if(~.F==~~.F,~~|~,~~)), null ) |表示集合的並運算
A.top( n ) = A.iterate( merge(~~,~).to(n), [inf]*n ) merge函數指歸並排序運算，to(n)選出集合的前n個成員
A.distinct() = A.iterate( if(~~.contain(~),~,~~|~), [] ) contain函數判斷集合是否包含某成員
不過，不是所有的聚合運算都容易用iterate來描述，畢竟聚合運算的定義太寬泛了，比如中位數就不合適用itertate描述。另外，象first/last這種聚合運算不需要遍曆，也沒必要用iterate描述。
迭代聚合語法不但能夠幫助我們寫出一些新的聚合運算，而且它本身就是一種遍曆方法。能用迭代語法寫出來的聚合運算，都可以一邊遍曆一邊計算，遍曆完了就得到聚合值，目標集合隻需要遍曆一次。
我們知道，計算機不能直接針對外存計算，當數據量很大而不能全部加載進內存時，迭代聚合算法可以隻需要較小的內存（能夠放下聚合值）就可以完成大數據量的聚合。這對於實現分組後的聚合運算很有意義。
分組子集的總體數據規模和原集是一樣大的，基於拆分後的子集再做聚合運算就意味著要遍曆兩次，對於純內存運算還不是大問題，但如果數據量大到內存放不下時，就會發生外存倒換的現象，這樣效率是非常低的。iterate作為一種聚合運算當然可以用在分組之後，分組後進行能夠被iterate描述的聚合運算時，就不需要對原數據遍曆兩次了，可以一邊分組一邊聚合，隻需要較小的內存（能保存下結果集）就可以完成。
這大概也是SQL沒有提供分組子集的原因之一，在發明SQL的那個年代內存很小，絕大多數原始數據都不可能放入內存，先產生分組子集後再聚合的運算效率難以容忍，而分組後直接聚合，且都是可以用iterate描述的聚合，雖然仍然可能發生外存倒換（結果集也裝不下內存時）的現象，但問題的嚴重程度要小很多。
原文發布時間為：2017-11-1
本文作者：蔣步星
本文來自雲棲社區合作夥伴“數據蔣堂”，了解相關信息可以關注“數據蔣堂”微信公眾號
最後更新：2017-11-03 15:35:16