关于distinct 和group by的去重逻辑浅析

在数据库操作中，我们常常遇到需要将数据去重计数的工作。例如：
表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。当然，我们可以根据实际情况对执行计划进行人工的干预，而这不是这里要讨论的话题了。


来源于：http://liuzhiqiangruc.iteye.com/blog/1461038