order by中的单路和双路排序算法原理

上一篇 <<<MySQL性能优化之in、exists优化
下一篇 >>>

---

1.Mysql排序支持两种filesort和index

1.1 using index

mysql扫描索引本身完成排序（底层存放在b+树中，默认顺序排列），查询不需要额外的排序,操作效率较高

1.2 using filesort

将数据查询到内存中，在内存中在做一次排序，效率非常低；

2.Order by排序代码示例

索引信息：idx_name_age_position

2.1 查询条件和order by字段均被索引覆盖

explain select * from employees where name= 'jarye' and  position ='ceo' order by age;

2.2 跳过联合索引中间值，出现了Using filesort

explain select * from employees where name= 'jarye' order by position;

2.3 索引顺序打乱，出现了Using filesort

explain select * from employees where name= 'jarye' order by position,age;

2.4 索引默认顺序排列，如果不一致，则会出现Using filesort

explain select * from employees where name= 'jarye' order by age asc ,position desc ;

explain select * from employees where name= 'jarye' order by age asc ,position asc ;

2.5 多个相等条件也是范围查询，也会出现Using filesort

explain select * from employees where name in('raby','jarye') order by age, position;

3.filesort实现原理

filesort通过相应的排序算法，将取得的数据在sort_buffer_size系统变量设置的内存排序区中进行排序，如果内存装载不下，会将磁盘上的数据进行分块，再对各个数据块进行排序，再将各个块合并成有序的结果集。
参数查看：show variables like '%max_length_for_sort_data%';

3.1单路排序步骤

1.从索引name字段中，查询到满足条件的数据name='jarye'条件主键的id
2.根据主键id取出整行的数据，缓存到sort buffer中
3.重复执行1,2步骤流程
4.对sort buffer中的数据实现排序给客户端

3.2双路排序步骤

1.从索引name字段中，查询到满足条件的数据name=‘jarye’条件主键的id
2.根据主键id，获取排序的字段和主键id缓存到sort buffer中
3.重复执行1,2步骤流程
4.对sort buffer中的数据实现排序
5.根据排序好的主键id和position，在从原来表中根据id查询数据给客户端。

3.3单路和双路排序方式的选择及优缺点

Mysql可以通过 max_length_for_sort_data 默认是1024字节大小
A.如果查询字段总的长度大小比设定的max_length_for_sort_data 要小，则使用单路排序方式；
B.如果查询字段总的长度大小比设定的max_length_for_sort_data 要大，则使用多路排序方式

单路排序算法：sort buffer 缓冲区缓存整个行的数据，在根据排序字段进行
排序，返回数据给客户端，缺点：占用内存 优点：避免回表查询
双路排序算法：sort buffer 缓冲区只缓存主键id和排序字段在内存中，在根据排序字段进行排序，在做一次回表查询，根据主键id查询该行数据返回给客户端。

4.单双路排序验证方式

optimizer_trace可分析sql语句

-- 设置开启
set  optimizer_trace='enabled=on',end_markers_in_json=on;
-- 以下两条语句同时执行，可查看sql语句的执行分析情况
select * from employees where name > 'jarye' ;
select * from information_schema.optimizer_trace;
 --关闭trace
set session optimizer_trace="enabled=off";   

 "join_preparation": --第一阶段：SQl准备阶段
"join_optimization": --第二阶段：SQL优化阶段
        "rows_estimation": [ --预估标的访问成本
              {
                "table": "`employees`",
                "range_analysis": { --全表扫描情况
                  "table_scan": {
                    "rows": 68511, --扫描行数
                    "cost": 13929 --查询成本
                  } /* table_scan */,
                  "potential_range_indexes": [ --查询可能使用的索引
                    {
                      "index": "PRIMARY", --主键索引
                      "usable": false,
                      "cause": "not_applicable"
                    },
                    {
                      "index": "idx_name_age_position", --辅助索引

                     ……
                    "analyzing_range_alternatives": { ‐‐分析各个索引使用成本
                    "range_scan_alternatives": [
                      {
                        "index": "idx_name_age_position",
                        "ranges": [
                          "mayikt < name"
                        ] /* ranges */,
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": false,
                        "using_mrr": false,
                        "index_only": false,
                        "rows": 34255, --‐‐索引扫描行数
                        "cost": 41107, --索引使用成本
                        "chosen": false, ‐‐是否选择该索引
                        "cause": "cost"
                      }
 "join_execution": --第三阶段：SQL执行阶段

单路排序：
用trace工具可以看到sort_mode信息里显示< sort_key, additional_fields >或者< sort_key, packed_additional_fields >；
双路排序（回表查询）：
用trace工具可以看到sort_mode信息里显示< sort_key, rowid >；