MySQL:排序(filesort)详细解析(8000字长文2)-阿里云开发者社区

开发者社区> -技术小能手-> 正文

MySQL:排序(filesort)详细解析(8000字长文2)

简介: MySQL:排序(filesort)详细解析(8000字长文)
+关注继续查看

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. mysql> show create table tests2 \G
  9. *************************** 1. row ***************************
  10. Table: tests2
  11. CreateTable: CREATE TABLE `tests2`(
  12. `a1` varchar(20) DEFAULT NULL,
  13. `a2` varchar(20) DEFAULT NULL,
  14. `a3` varchar(20) DEFAULT NULL
  15. ) ENGINE=InnoDB DEFAULT CHARSET=utf8
  16. 1 row inset(0.00 sec)

  17. mysql> select* from tests2;
  18. +------+------+------+
  19. | a1 | a2 | a3 |
  20. +------+------+------+
  21. | a | a | a |
  22. | a | b | b |
  23. | a | c | c |
  24. | b | d | d |
  25. | b | e | e |
  26. | b | f | f |
  27. | c | g | g |
  28. | c | h | h |
  29. +------+------+------+
  30. 8 rows inset(0.00 sec)

  31. mysql> desc select* from tests2 where a1='b' order by a2,a3;
  32. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
  33. | id | select_type | table | partitions | type | possible_keys | key | key_len | ref| rows | filtered | Extra|
  34. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
  35. | 1| SIMPLE | tests2 | NULL | ALL | NULL | NULL | NULL | NULL | 8| 12.50| Usingwhere; Using filesort |
  36. +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
  37. 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. rec_length= sort_length + addon_length;
  22. //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
$2 = 
266

可以看出误差不大。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【深度长文】MySQL排序内部原理探秘(3)
【深度长文】MySQL排序内部原理探秘
15 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
7300 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
9002 0
SQL优化:组内排序取最大值
最近业务反馈一个查询异常的问题,需要DBA对查询结果异常给出解释,并帮助他们解决该问题。问题本质是一个组内排序取最大值的问题,根据业务需求,我构建了测试用例 测试用例 --建表 create table testorder (id in...
1265 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
10601 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
5885 0
1727
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载