有时查看SQL的执行计划时, 会遇到Using filesort, 如下.

mysql> explain select * from tb1 where col1 = 4 order by col2\G

*************************** 1. row ***************************

           id: 1

  select_type: SIMPLE

        table: tb1

         type: ref

possible_keys: idx_col1

          key: idx_col1

      key_len: 4

          ref: const

         rows: 1

        Extra: Using where; Using filesort

1 row in set (0.00 sec)

这个filesort是说, MySQL要多做一次额外的排序, 确切的说是快速排序(Quicksort).

先初步了解下Quicksort排序的概念(From Wikipedia). 

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

The steps are:

1. Pick an element, called a pivot, from the array.

2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

再看下Python对于其的一个实现.

#!/usr/bin/env python

# -*- coding: utf-8 -*-

from __future__ import print_function

def quicksort(array):

    if len(array) < 2:

        return array

    else:

        pivot = array[0]

        less = [i for i in array[1:] if i <= pivot]

        greater = [i for i in array[1:] if i > pivot]

        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

再回来说filesort, 在MySQL中有the Original, Modified和In-Memory filesort Algorithm 3种实现. 

The Original filesort Algorithm

1. 扫描或根据WHERE条件, 获取所有记录.

2. 把每条记录的sort key和row ID, 即, 放入sort buffer中. 若sort buffer满了, 就在内存中进行一次quicksort, 然后将写入临时文件, 并记录指向指针. 重复该过程, 直到读取了所有记录.

3. 进行若干次multi-merge操作, 将所有row ID写入结果文件.

4. 根据row ID再次获取记录.

很容易发现, 上面的步骤1和4, 一共读取了2遍记录, 所以也就有了下面的改进实现.

The Modified filesort Algorithm

较Original改变的地方是, 在第2步记录的是sort key和涉及到的其它列, 即, 不是row ID了. 第3步完成后, 就可得到结果了.

这个算法中占用空间比要大, 若排序数据量很大的情况下, 会频繁写临时文件, 为了避免其, 引入了max_length_for_sort_data参数.

The In-Memory filesort Algorithm

那么排序数据量比较小的情况下呢, 小到在sort buffer中就可完成排序, 针对这种情况又有了In-Memory filesort. 这时MySQL把sort buffer当成priority queue使用, 避免使用临时文件.

上面可以看到MySQL已在尽量优化排序了, 也从侧面说明其不希望排序的出现, 如最开始的SQL, 建立一个(col1, col2)的联合索引, 就可以避免排序了, 该原因还要从B+树索引说起...

若感兴趣可关注订阅号”数据库最佳实践”(DBBestPractice).