同學問到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); Inser
同學問到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)。
