MySQL：排序（filesort）详细解析（8000字长文2）

MySQL：排序（filesort）详细解析（8000字长文）

1. mysql> desc select* from tests2 where a1='b' order by a2,a3;
   
2. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
   
3. | id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
   
4. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
   
5. | 1| SIMPLE | tests2 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
   
6. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
   
7. 1 row inset, 1 warning (0.00 sec)
   
8. 
   
9. mysql> show create table tests2 \G
   
10. *************************** 1. row ***************************
    
11. Table: tests2
    
12. CreateTable: CREATE TABLE `tests2`(
    
13. `a1` varchar(20) DEFAULT NULL,
    
14. `a2` varchar(20) DEFAULT NULL,
    
15. `a3` varchar(20) DEFAULT NULL
    
16. ) ENGINE=InnoDB DEFAULT CHARSET=utf8
    
17. 1 row inset(0.00 sec)
    
18. 
    
19. mysql> select* from tests2;
    
20. +------+------+------+
    
21. | a1 | a2 | a3 |
    
22. +------+------+------+
    
23. | a | a | a |
    
24. | a | b | b |
    
25. | a | c | c |
    
26. | b | d | d |
    
27. | b | e | e |
    
28. | b | f | f |
    
29. | c | g | g |
    
30. | c | h | h |
    
31. +------+------+------+
    
32. 8 rows inset(0.00 sec)
    
33. 
    
34. mysql> desc select* from tests2 where a1='b' order by a2,a3;
    
35. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
    
36. | id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
    
37. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
    
38. | 1| SIMPLE | tests2 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
    
39. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
    
40. 1 row inset, 1 warning (0.01 sec)
    

整个流程我们从filesort函数接口开始讨论。下面第3到第10节为排序的主要流程。

三、阶段1:确认排序字段及顺序

这里主要将排序顺序存入到Filesort 类的 sortorder中，比如我们例子中的order by a2,a3就是a2和a3列，主要接口为Filesort::make_sortorder，我们按照源码描述为sort字段（源码中为sort_length），显然我们在排序的时候除了sort字段以外，还应该包含额外的字段，到底包含哪些字段就与方法 original filesort algorithm（回表排序） 和 modified filesort algorithm（不回表排序）有关了，下面进行讨论。

四、阶段2:计算sort字段的长度

这里主要调用使用sortlength函数，这一步将会带入max_sort_length参数的设置进行判断，默认情况下max_sort_length为1024字节。这一步大概步骤为：1、循环每一个sort字段2、计算每一个sort字段的长度：公式为 ≈ 定义长度 * 2比如这里例子中我定义了a1 varchar(300)，那么它的计算长度 ≈ 300 * 2（600），为什么是*2呢，这应该是和Unicode编码有关，这一步可以参考函数my_strnxfrmlen_utf8。同时需要注意这里是约等于，因为源码中还是其他的考虑，比如字符是否为空，但是占用不多不考虑了。3、带入max_sort_length参数进行计算好了有了上面一个sort字段的长度，那么这里就和max_sort_length进行比较，如果这个这个sort字段大于max_sort_length的值，那么以max_sort_length设置为准，这步代码如下：

1. set_if_smaller(sortorder->length, thd->variables.max_sort_length);
   

因此，如果sort字段的某个字段的超过了max_sort_length设置，那么排序可能不那么精确了。到了这里每个sort字段的长度以及sort字段的总长度已经计算出来，比如前面给的两个不同列子中：

• （a2 varchar(300) a3 varchar(300) order by a2,a3）：每个sort字段约为300*2字节，两个字段的总长度约为1200字节。
• （a2 varchar(20) a3 varchar(20) order by a2,a3）：每个sort字段约为20*2字节，两个字段的总长度约为80字节。

并且值得注意的是，这里是按照定义大小，如varchar(300) ，以300个字符来计算长度的，而不是我们通常看到的Innodb中实际占用的字符数量。这是排序使用空间大于Innodb实际数据文件大小的一个原因。下面我们以（a2 varchar(300) a3 varchar(300) order by a2,a3）为例实际看看debug的结果如下：

1. (gdb) p sortorder->field->field_name
   
2. $4 = 0x7ffe7800fadf"a3"
   
3. (gdb) p sortorder->length
   
4. $5 = 600
   
5. (gdb) p total_length
   
6. $6 = 1202（这里a2,a3 可以为NULL各自加了1个字节）
   
7. (gdb)
   

可以看出没有问题。

4、循环结束，计算出sort字段的总长度。

后面我们会看到sort字段不能使用压缩（pack）技术。

五、阶段3:计算额外字段的空间

对于排序而言，我们很清楚除了sort字段以外，通常我们需要的是实际的数据，那么无外乎两种方式如下：

• original filesort algorithm：只存储rowid或者主键做为额外的字段，然后进行回表抽取数据。我们按照源码的描述，将这种关联回表的字段叫做ref字段（源码中变量叫做ref_length）。
  
• modified filesort algorithm：将处于read_set（需要读取的字段）全部放到额外字段中，这样不需要回表读取数据了。我们按照源码的描述，将这些额外存储的字段叫做addon字段（源码中变量叫做addon_length）。
  

这里一步就是要来判断到底使用那种算法，其主要标准就是参数max_length_for_sort_data，其默认大小为1024字节，但是后面会看到这里的计算为（sort字段长度+addon字段的总和）是否超过了max_length_for_sort_data。其次如果使用了modified filesort algorithm算法，那么将会对addon字段的每个字段做一个pack（打包），主要目的在于压缩那些为空的字节，节省空间。

这一步的主要入口函数为Filesort::get_addon_fields下面是步骤解析。

1、循环本表全部字段

2、根据read_set过滤出不需要存储的字段

这里如果不需要访问到的字段自然不会包含在其中，下面这段源码过滤代码：

if(!bitmap_is_set(read_set, field->field_index)) //是否在read set中continue;


3、获取字段的长度这里就是实际的长度了比如我们的a1 varchar(300)，且字符集为UTF8，那么其长度≈ 300*3 （900）。4、获取可以pack（打包）字段的长度和上面不同，对于int这些固定长度类型的字段，只有可变长度的类型的字段才需要进行打包技术。5、循环结束，获取addon字段的总长度，获取可以pack（打包）字段的总长度循环结束后可以获取addon字段的总长度，但是需要注意addon字段和sort字段可能包含重复的字段，比如例2中sort字段为a2、a3，addon字段为a1、a2、a3。如果满足如下条件：

addon字段的总长度+sort字段的总长度 > max_length_for_sort_data

那么将使用original filesort algorithm（回表排序）的方式，否则使用modified filesort algorithm的方式进行。下面是这一句代码：

1. if(total_length + sortlength > max_length_for_sort_data) //如果长度大于了max_length_for_sort_data 则退出了
   
2. {
   
3. DBUG_ASSERT(addon_fields == NULL);
   
4. return NULL;
   
5. //返回NULL值 不打包了 使用 original filesort algorithm（回表排序）
   
6. }
   

我们在回到第2节例子中的第1个案例，因为我们对a1,a2,a3都是需要访问的，且他们的大小均为varchar(300) UTF8，那么addon字段长度大约为300 * 3 * 3=2700字节 ，其次我们前面计算了sort字段大约为1202字节，因此 2700+1202 是远远大于max_length_for_sort_data的默认设置1024字节的，因此会使用original filesort algorithm方式进行排序。如果是第2节例子中的第2个案例呢，显然要小很多了（每个字段varchar（20）），大约就是20 * 3 * 3（addon字段）+82（sort字段） 它是小于1024字节的，因此会使用modified filesort algorithm的排序方式，并且这些addon字段基本都可以使用打包（pack）技术，来节省空间。但是需要注意的是无论如何（sort字段）是不能进行打包（pack）的，而固定长度类型不需要打包（pack）压缩空间。

六、阶段4:确认每行的长度

有了上面的就计算后每一行的长度（如果可以打包是打包前的长度），下面就是这个计算过程。

1. if(using_addon_fields())
   
2. //如果使用了 打包技术 检测 addon_fields 数组是否存在 使用modified filesort algorithm算法 不回表排序
   
3. {
   
4. res_length= addon_length; //总的长度 3个 varchar(300) uft8 为 3*300*3
   
5. }
   
6. else//使用original filesort algorithm算法
   
7. {
   
8. res_length= ref_length; //rowid(主键长度)
   
9. /*
   
10. The reference to the record is considered
    
11. as an additional sorted field
    
12. */
    
13. sort_length+= ref_length; //实际上就是rowid(主键) +排序字段长度 回表排序
    
14. }
    
15. /*
    
16. Add hash at the end of sort key to order cut values correctly.
    
17. Needed for GROUPing, rather than for ORDERing.
    
18. */
    
19. if(use_hash)
    
20. sort_length+= sizeof(ulonglong);
    
21. 
    
22. rec_length= sort_length + addon_length;
    
23. //modified filesort algorithm sort_length 为排序键长度 addon_lenth 为访问字段长度，original filesort algorithm rowid(主键) +排序字段长度 ，因为addon_length为0
    

好了我们稍微总结一下：

• original filesort algorithm：每行长度为sort字段的总长度+ref字段长度（主键或者rowid）。
• modified filesort algorithm：每行的长度为sort字段的总长度+addon字段的长度（需要访问的字段总长度）。

当然到底使用那种算法参考上一节。但是要注意了对于varchar这种可变长度是以定义的大小为准了，比如UTF8 varchar（300）就是300*3= 900 而不是实际存储的大小，而固定长度没有变化。好了，还是回头看看第2节的两个例子，分别计算它们的行长度：

• 例子1：根据我们的计算，它将使用original filesort algorithm排序方式，最终的计算行长度应该为（sort字段长度+rowid长度）及 ≈ 1202+6 字节，下面是debug的结果：

(gdb) p rec_length
$1 = 
1208

例子2：根据我们的计算，它将使用modified filesort algorithm排序方式，最终计算行长度应该为（sort字段长度+addon字段长度）及 ≈ 82 + 20 * 3 * 3 （结果为262），注意这里是约等于没有计算非空等因素和可变长度因素，下面是debug的结果：

(gdb) p rec_length

可以看出误差不大。