關于distinct 和group by的去重邏輯淺析

【轉】http://liuzhiqiangruc.iteye.com/blog/1461038

在資料庫操作中，我們常常遇到需要将資料去重計數的工作。例如：

表A，列col

A

C

A

B

C

D

A

B

結果就是一共出現4個不同的字母A、B、C、D

即結果為4

大體上我們可以選擇count(distinct col)的方法和group+count的方法。

分别為：

select count(distinct col) from A;

select count(1) from (select 1 from A group by col) alias;

兩中方法實作有什麼不同呢？

其實上述兩中方法分别是在運算和存儲上的權衡。

distinct需要将col列中的全部内容都存儲在一個記憶體中，可以了解為一個hash結構，key為col的值，最後計算hash結構中有多少個key即可得到結果。

很明顯，需要将所有不同的值都存起來。記憶體消耗可能較大。

而group by的方式是先将col排序。而資料庫中的group一般使用sort的方法，即資料庫會先對col進行排序。而排序的基本理論是，時間複雜為nlogn，空間為1.，然後隻要單純的計數就可以了。優點是空間複雜度小，缺點是要進行一次排序，執行時間會較長。

兩中方法各有優劣，在使用的時候，我們需要根據實際情況進行取舍。

具體情況可參考如下法則

資料分布	去重方式	原因
離散	group	distinct空間占用較大，在時間複雜度允許的情況下，group 可以發揮空間複雜度優勢
集中	distinct	distinct空間占用較小，可以發揮時間複雜度優勢

兩個極端：

1.資料列的所有資料都一樣，即去重計數的結果為1時，用distinct最佳

2.如果資料列唯一，沒有相同數值，用group 最好

當然，在group by時，某些資料庫産品會根據資料列的情況智能地選擇是使用排序去重還是hash去重，例如postgresql。當然，我們可以根據實際情況對執行計劃進行人工的幹預，而這不是這裡要讨論的話題了。