mysql中group的实现

同学问到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’);

查询语句和结果

 

 

 

算法分析

其实细想一下，如果是先排序后分组，则时间复杂性为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)。