前言

• 我们常常会在sql中使用order by关键字来对查询结果进行排序处理。

• 最常见的场景就是分页查询了，分页查询时我们往往会先对数据进行排序，然后再获取指定页码的数据。

基础知识：

• sort buffer

  • 概念：mysql会为每个查询线程分配一块内存作为排序缓冲区（sort buffer）。
  • 参数：sort buffer的大小由 sort_buffer_size 参数控制，默认为 256 kb。
    • 查看：show variables like 'sort_buffer_size'
    • 结果：sort_buffer_size 8388608 单位是字节，8388608即16M

• 回表

  • 概念：通过辅助索引(二级索引)拿到主键id之后，要再去遍历聚集索引的B+树，这个过程就叫做回表。回表的操作更多的是随机io，随机io在性能上还是比较低下的。

• rowId

  • 概念：mysql对每行数据的唯一标识符，当数据表有主键时，rowId 就是表主键；当数据表没有主键或者主键被删除时，mysql会自动生成一个长度为 6 字节的rowId。

内部排序还是外部排序？

• 内部排序：当待排序数据不超过 sort buffer 的容量(sort_buffer_size)时，mysql 将会在内存中使用快速排序算法进行排序。
• 外部排序：当待排序数据量超过 sort buffer 的容量(sort_buffer_size)时，mysql 将会借助临时磁盘文件使用归并排序算法进行排序（通常会将待排序数据分成多个“小文件”，对各个“小文件”进行快速排序，再汇总成一个有序的“大文件”）。

排序算法1--全字段排序

概念：将最终结果集中所有的字段都放进 sort buffer中，然后在sort buffer中针对排序字段进行快速排序。

以下面的 SQL 为例子：

SELECT nick_name, age, phone 
FROM t_user 
WHERE city = "深圳" 
ORDER BY nick_name;

假设 city 字段上有索引，全字段排序的过程：

1. 从 city 索引树上找到第一条值为深圳的数据，取得 id 之后回表取得 nick_name、age、phone 三个字段放入 sort buffer。

2. 从 city 索引树取下一条值为深圳的数据，重复 1 过程，直到下一条数据不满足值为深圳条件。

3. 到这一步，所有 city = 深圳 的数据都在 sort buffer 了，然后对 nick_name 进行快速排序。

4. 将排序结果返回

• 可以看到当查询条件本身有索引可用的话，全字段排序的排序过程都在sort buffer进行，回表次数为符合条件的数据个数。
• 若是由city、nick_name建立的联合索引，则可以实现“索引覆盖”，即在一棵索引树上取得全部所需数据，减少回表（随机读）次数。
  1. 从 (city，nick_name)索引中获取到第一条 city='深圳' 的数据，取得 id 之后回表取得 nick_name、age、phone 三个字段。
  2. 从 (city，nick_name)索引中获取下一条 city='深圳' 的数据，取得 id 之后回表取得 nick_name、age、phone 三个字段。
  3. 1和2中获取的数据天然是有序的，故mysql不需要再进行排序了，这样就避掉了对 name 字段的排序。
• 当待排序的数据行很大(即查询的字段有很多)时，使用全字段排序必然会导致“外部排序”，为了尽可能地避免“外部排序”，mysql提供了rowId排序的算法。

排序算法2--rowId排序

• 概念：只将与排序相关的字段和 rowId 放入 sort buffer，其余结果集需要用到的数据在排序完成后，通过 rowId 回表取得。

• 优点：rowId 排序的好处是在 sort buffer 大小固定的情况下，sort buffer 能够容纳更多的数据行，能够避免使用或者少使用“外部排序文件”。
• 缺点：最终返回结果集的时候，需要再次进行回表。

还是之前那个例子：

SELECT nick_name, age, phone 
FROM t_user 
WHERE city = "深圳"
ORDER BY nick_name;

rowId 排序全过程：

1. 从 city 索引树上找到第一条值为深圳的数据，取得 id 之后回表取得 nick_name 这个与排序相关的字段和主键 id 一起放入 sort buffer。

2. 从 city 索引树取下一条值为深圳的数据，重复 1 过程，直到下一条数据不满足值为深圳条件。

3. 这时候，所有 city = 深圳 的数据都在 sort buffer 了（sort buffer 里面的数据包含两个字段： id 和 nick_name），然后对 nick_name 执行快速排序。

4. 利用排序好的数据，使用主键 id 再次回表取其他字段，将结果返回。

注意：在步骤 4 中不会等所有排序好的 id 回表完再返回，而是每个 id 回表一次，取得该行数据之后立即返回，所以不会消耗额外的内存。

全字段排序还是rowId排序?

max_length_for_sort_data

• 表示mysql对于排序的行数据支持的最大长度，默认值为 1024 字节。
• 测试：SET max_length_for_sort_data=8; # 小于要排序字段长度的和即可。

如果单行数据的长度不大于该值，则使用全字段排序，否则使用rowId排序。

排序算法3--优先队列排序

• 无论是使用全字段排序还是 rowId 排序，都不可避免了对所有符合 WHRER 条件的数据进行了排序。

• order by + limit n 查询时，如果仍然使用全字段排序或rowId排序，虽然我们只需要n条数据有序，但是仍会将所有满足查询条件的数据都载入sort buffer中进行排序，大大降低了sort buffer的利用率。
• 在排序字段无索引的情况下，mysql使用优先队列进行排序(堆排序)对 order by + limit n 排序语句进行优化。

优先队列进行排序的流程：

1. 在所有待排序的数据，取数量为 LIMIT（本例中为 3）的数据，构建一个堆

2. 不断的取下一行数据，更新堆节点

3. 当所有行的扫描完，得到最终的排序结果

临时表排序

• 通常对于一个执行较慢的排序语句，在使用 EXPLAIN 进行执行过程分析的时候除了能看到 Using filesort以外，还能看到 Using temporary，代表在排序过程中使用到了临时表。

内存临时表排序

• MySQL 优先使用内存临时表。当 MySQL 使用内存临时表时，临时表存储引擎为 memory 。
• 如果当前 MySQL 使用的是内存临时表的话，将会直接使用 rowId 排序，这时的“回表”只是在内存表中读数据，操作不涉及硬盘IO 。

磁盘临时表排序

• 如果系统中很多需要使用临时表的排序语句执行，而又不加以限制，全都使用临时表的话，内存很快就会被打满。
• MySQL 提供了 tmp_table_size 参数限制了内存临时表的大小，默认值是 16M，如果临时表大小超过了tmp_table_size，那么内存临时表就会转成磁盘临时表。
• 当使用磁盘临时表的时候，表储存引擎将不再是 memory，而是由 internal_tmp_disk_storage_engine 参数控制，默认为 InnoDB 。
• 这时候 MySQL 会根据单行大小是否超过 max_length_for_sort_data 决定采用全字段排序还是 rowId 排序。

总结

• 当排序数据量不超过 sort buffer 容量时，MySQL 将会在内存使用快速排序算法进行排序（内部排序）。
• 当排序数据量超过 sort buffer 容量时，MySQL 将会借助临时磁盘文件使用归并排序算法进行排序（外部排序）。
• 当需要借助临时表的时候，MySQL 会优先使用内存临时表（此时表引擎为 memory 引擎），回内存临时表取数据并不涉及随机读，也不涉及扫描行，效率较高。
• 所以在配合内存临时表的时候，会使用 rowId 排序方式；当内存临时表大小超过 tmp_table_size 限制时，则需要将内存临时表转换为磁盘临时表，这时候由于回表意味着随机读，所以会搭配全字段排序方式。
• 针对 order by + limit 场景，在排序字段无索引的情况下mysql使用优先队列进行排序算法进行排序。