filesort直接影响SQL的执行效率,使导致慢查询的罪魁祸首。无论从研发人员还是DBA都有必要对这一元凶加深理解。今天我花了些时间研究了下官方文档,写一片总结加深理解。

MySQL 针对filesort实现了三种算法,这三种算法可以说是在一种算法上针对不同使用场景的改进,以至于它们都没有一个正规的名字。

原始算法

这是mysql最初实现的排序算法,它是这样工作的:

  1. 读取表中所有满足where条件的排序字段和相应的row ID.
  2. 将每一行满足条件的排序字段和row ID存入sort buffer中。sort buffer满了,就按排序字段(order by)执行一次快速排序,把排序后的数据写入临时文件。
  3. 重复上述步骤,直到所有的行都被扫描。这样就有了许多临时文件,且临时文件中的数据都是有序的。
  4. 合并临时文件,因为每个临时文件都是按排序字段排好了顺序,合并排序变得快速高效。多次合并后变成了两个临时文件,合并这两个临时文件时只写入rowID到最后的结果文件,这样减少了不必要的IO。
  5. 这样我们有了一个结果文件,里面都是要查询的RowID, 并且这些row ID 是按排序字段排序的。依据这些rowID 从表中读取所查询数据即可。

这种算法的缺点很明显,就是要两次扫描全表,且第二次是随机访问,效率很低。于是就有了第二种算法。

优化后的排序算法

这种算法比第一种类似,但它避免了两次全表扫描。遗憾的是不是所有场景下都能使用!它是这样工作的:

  1. 读取所有满足where条件的行。
  2. 对每一行将查询的字段和排序字段一起存入sort buffer。注意这里就是区别了:第一中算法只保存了行的row ID和排序字段,这里保存了查询的所有字段(select 后面的字段)和order by 的字段。
  3. sort buffer 满了,就按排序字段快速排序,将结果存入临时文件。
  4. 多次合并临时文件至一个后,把要查询的字段从临时文件中返回给上层即完成了任务。

这中算法的优点是避免了两次全表扫描,缺点也很明显,就是增加了不少IO负载。因为它会产生更多的临时文件。而且只有优化器发现当所查询字段的总长度小于变量max_length_for_sort_data的值时才会选用这种算法。如果所查询的字段中包含text,blog,则立刻选择第一种算法。

内存中的filesort

这是第三种排序算法,它的特点是完全在内存中,不写临时文件,但它的使用场景更小。它只针对简单的order by limit (m,)n 语句使用。它的原理是这样的:sort buffer 的大小由变量sort_buffer_size控制。当所查询的结果集很小,sort buffer可以完全容纳时,就不需要再写临时文件,然后merge file了。完全可以按照排序字段在sort buffer 中排序,然后使用优先队列,淘汰掉排在前面的数据(如order by a limit 5, 发现更小的值a,就将队列中最大的a换出),因为它们不是查询想要的数据。它是这样工作的:

  1. 读取满足where 条件的所有行
  2. 将查询的字段和排序字段,作为一条记录插入优先队列,这个优先队列是按照排序字段自动排序的。
  3. 当优先队列满了,就挤出最前面的数据,直到扫描完所有的行。然后返回队列中的N行即可。如果指定M, 则跳过M行返回N行。(显然如果M很大,这中算法也用不了,因为sort buffer大小是有限的,它要至少能保存M+N行数据时才能使用)

这种算法属于CPU密集型算法,它不需要消耗IO资源,速度也很快,但使用场景很苛刻。优化器要考虑sort buffer 大小,M,N的值,所查询的row size等多种因素来决定选用算法。

啥? 为啥不用索引? 用索引当然很快了,filesort是在没有索引的情况下的无奈之举啊!