MySQL 中group by的实现

有同学问到group by的实现，发现可能存在误解，简单说明一下。

 

示例

CREATE TABLE `tb` (
  `c` int(11) DEFAULT NULL,
  `d` int(4) DEFAULT NULL,
  `e` varchar(1000) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Insert into tb values(2,20,’b’);
Insert into tb values(1,10,’a’);
Insert into tb values(2,20,’b’);
Insert into tb values(1,10,’a’);
Insert into tb values(3,30,’c’);

 

 

 查询语句和结果

 

 

 

在这个语句的explain结果中有Using temporary; Using filesort，需要用到排序。
因此有人会认为group by的实现，是“先排序，后分组”。

 

 用法分析

         先看手册上这段说明：”By default, MySQL sorts all GROUP BY col1, col2, … queries as if you specified ORDER BY col1, col2, … in the query as well. If you include an ORDER BY clause explicitly that contains the same column list, MySQL optimizes it away without any speed penalty, although the sorting still occurs. If a query includes GROUP BY but you want to avoid the overhead of sorting the result, you can suppress sorting by specifying ORDER BY NULL”。

 

         如果我们的查询加了order by null， 结果则如下

 

 

 

Explain中也没有Using filesort.

因此我们可以设想，排序其实是分组之后才进行的。

 

 算法分析

         其实细想一下，如果是先排序后分组，则时间复杂性为O(nlog(n))， 而示例中的需求，若只需要分组，其实可以更快一点。MySQL里的作法简单描述如下：

1、建一个空的临时表，三个字段分别为索引列、c、count(*)
    这里的” 索引列”就是group by 后的列计算结果，想象一下如果语句是group by 1/c什么的。 当然在我们的例子中，其值就是c。

 

2、从原表中一行行读入，先计算索引列的值key。 用key在临时表中查找，若key行存在，则update， 否则insert.
    在这个例子中，第一次读到c=2的行，则向临时表中插入一行 2, 2, 1。 第二次碰到c=2的行，则修改为2,2,2

 

3、原表全部遍历完成后，分组就结束了。因此我们看到加了order by null的查询结果c的出现顺序是 2, 1, 3，没有order by null的则是在这个基础上做了排序。

 

   临时表中的查询就是简单的hash查找，我们看到这个算法的分组过程时间复杂度为O(n)。

评论

3 楼 GaoYusong 2012-06-15  

感觉需要排序的话，先分组后排序的方法常数也应该小一些，分组后的行数应该会减少不少。

2 楼 丁林.tb 2012-06-14  

lajabs 写道

其实昨天我想到一点是，如果生成了临时文件排序，那么应该是个外排序，情况是否有所不一样。

如果没有 order by null， 就是临时文件排序。只是内存如果放得下，不需要放到磁盘上。

1 楼 lajabs 2012-06-14  

其实昨天我想到一点是，如果生成了临时文件排序，那么应该是个外排序，情况是否有所不一样。