张治峰的博客

mysql之单/双路排序

2021-09-27

Using filesort

当语句中使用到 order by 排序时,尽可能遵照索引键的最佳左前缀，在索引列上进行排序操作。

如果排序字段 不能通过索引树的排序时 就会出现 using filesort 文件排序。如下图执行语句。

EXPLAIN SELECT * from employees ORDER BY name

FileSort有两种算法，双路排序和单路排序(mysql4.1之前只有双路排序)。接下来本文就这两种算法进行分析。

sort_buff

MySQL 为每个线程各维护了一块内存区域 sort_buffer ，用于进行排序。sort_buffer 的大小可以通过 sort_buffer_size 来设置。如果加载的记录总大小小于 sort_buffer_size 便使用 sort_buffer 排序；如果超过则使用 sort_buffer + 临时文件进行排序。
这是排序时，存储数据的内存结构，先有个印象方便后面理解。**

单路排序

是一次性取出满足条件行的所有字段，然后在sort buffer中进行排序;用trace工具可 以看到sort_mode信息里显示< sort_key, additional_fields >或者< sort_key, packed_additional_fields >

排序过程

  1. 根据查询条件找第一个满足条件的数据行
  2. 取出所有字段的值，存入 sort_buffer 中
  3. 根据查询条件找到下一个满足 条件的数据行
  4. 重复步骤 2、3 直到查出所有满足条件的数据
  5. 对 sort_buffer 中的数据按照 排序字段 进行排序
  6. 返回结果给客户端
  • 优点：查询快，执行过程简单
  • 缺点：需要的空间大。

双路排序(回表排序)

是首先根据相应的条件取出相应的排序字段和可以直接定位行 数据的行 ID，然后在 sort buffer 中进行排序，排序完后需要再次取回其它需要的字段;
用trace工具 可以看到sort_mode信息里显示< sort_key, rowid >

  1. 根据查询条件找第一个满足条件的数据行
  2. 把排序字段 和主键 放到 sort buffer 中
  3. 根据查询条件找到下一个满足 条件的数据行
  4. 重复步骤 2、3 直到查出所有满足条件的数据
  5. 对 sort_buffer 中的排序字段 和主键 按照字段 排序字段 进行排序
  6. 遍历排序好的 主键 和 排序字段 ，按照 主键 进行回表（这时已经是有序状态）
  7. 返回数据到客户端
  • 优点：所需的空间更小。
  • 缺点：会产生更多次数的回表查询，查询可能会慢一些。

单/双路排序的选择

排序方式的选择是由 max_length_for_sort_data参数与返回记录字段总长度决定的，如果用于排序的单条记录字段长度 <= max_length_for_sort_data 使用单路排序；反之则使用 双路 排序。

实战

trace工具使用: MySQL Optimizer 分析（trace 工具）

1.max_length_for_sort_data = 1024 大于字段总长度 将使用 单路排序

执行如下语句 用trace进行分析

set session optimizer_trace=”enabled=on”,end_markers_in_json=on;
SELECT * from employees ORDER BY age LIMIT 10;
select * from information_schema.OPTIMIZER_TRACE;

结果:

{
  "steps": [
    {
      "join_preparation": {
        "select#": 1,
        "steps": [
          {
            "expanded_query": "/* select#1 */ select `employees`.`id` AS `id`,`employees`.`name` AS `name`,`employees`.`age` AS `age`,`employees`.`position` AS `position`,`employees`.`hire_time` AS `hire_time` from `employees` order by `employees`.`age` limit 10"
          }
        ] /* steps */
      } /* join_preparation */
    },
    {
      "join_optimization": {
        "select#": 1,
        "steps": [
          {
            "substitute_generated_columns": {
            } /* substitute_generated_columns */
          },
          {
            "table_dependencies": [
              {
                "table": "`employees`",
                "row_may_be_null": false,
                "map_bit": 0,
                "depends_on_map_bits": [
                ] /* depends_on_map_bits */
              }
            ] /* table_dependencies */
          },
          {
            "rows_estimation": [
              {
                "table": "`employees`",
                "table_scan": {
                  "rows": 100036,
                  "cost": 353
                } /* table_scan */
              }
            ] /* rows_estimation */
          },
          {
            "considered_execution_plans": [
              {
                "plan_prefix": [
                ] /* plan_prefix */,
                "table": "`employees`",
                "best_access_path": {
                  "considered_access_paths": [
                    {
                      "rows_to_scan": 100036,
                      "access_type": "scan",
                      "resulting_rows": 100036,
                      "cost": 20360,
                      "chosen": true
                    }
                  ] /* considered_access_paths */
                } /* best_access_path */,
                "condition_filtering_pct": 100,
                "rows_for_plan": 100036,
                "cost_for_plan": 20360,
                "chosen": true
              }
            ] /* considered_execution_plans */
          },
          {
            "attaching_conditions_to_tables": {
              "original_condition": null,
              "attached_conditions_computation": [
              ] /* attached_conditions_computation */,
              "attached_conditions_summary": [
                {
                  "table": "`employees`",
                  "attached": null
                }
              ] /* attached_conditions_summary */
            } /* attaching_conditions_to_tables */
          },
          {
            "clause_processing": {
              "clause": "ORDER BY",
              "original_clause": "`employees`.`age`",
              "items": [
                {
                  "item": "`employees`.`age`"
                }
              ] /* items */,
              "resulting_clause_is_simple": true,
              "resulting_clause": "`employees`.`age`"
            } /* clause_processing */
          },
          {
            "reconsidering_access_paths_for_index_ordering": {
              "clause": "ORDER BY",
              "steps": [
              ] /* steps */,
              "index_order_summary": {
                "table": "`employees`",
                "index_provides_order": false,
                "order_direction": "undefined",
                "index": "unknown",
                "plan_changed": false
              } /* index_order_summary */
            } /* reconsidering_access_paths_for_index_ordering */
          },
          {
            "refine_plan": [
              {
                "table": "`employees`"
              }
            ] /* refine_plan */
          }
        ] /* steps */
      } /* join_optimization */
    },
    {
      "join_execution": {
        "select#": 1,
        "steps": [
          {
            "filesort_information": [
              {
                "direction": "asc",
                "table": "`employees`",
                "field": "age"
              }
            ] /* filesort_information */,
            "filesort_priority_queue_optimization": {
              "limit": 10,
              "rows_estimate": 304128,
              "row_size": 150,
              "memory_available": 262144,
              "chosen": true
            } /* filesort_priority_queue_optimization */,
            "filesort_execution": [
            ] /* filesort_execution */,
            "filesort_summary": {
              "rows": 11,
              "examined_rows": 100003,
              "number_of_tmp_files": 0,
              "sort_buffer_size": 1744,
              "sort_mode": "<sort_key, additional_fields>"
            } /* filesort_summary */
          }
        ] /* steps */
      } /* join_execution */
    }
  ] /* steps */
}

结论：由trace 倒数第 8 行 “sort_mode”: “<sort_key, additional_fields>” 得出为单路排序

2.将 max_length_for_sort_data 设置为 10，employees表所有字段长度总和肯定大于10字节 ，那么字段总长度大于max_length_for_sort_data 将使用 双路排序。

set max_length_for_sort_data = 10;
SELECT * from employees ORDER BY age LIMIT 10;
select * from information_schema.OPTIMIZER_TRACE;

trace结果

{
  "steps": [
    {
      "join_preparation": {
        "select#": 1,
        "steps": [
          {
            "expanded_query": "/* select#1 */ select `employees`.`id` AS `id`,`employees`.`name` AS `name`,`employees`.`age` AS `age`,`employees`.`position` AS `position`,`employees`.`hire_time` AS `hire_time` from `employees` order by `employees`.`age` limit 10"
          }
        ] /* steps */
      } /* join_preparation */
    },
    {
      "join_optimization": {
        "select#": 1,
        "steps": [
          {
            "substitute_generated_columns": {
            } /* substitute_generated_columns */
          },
          {
            "table_dependencies": [
              {
                "table": "`employees`",
                "row_may_be_null": false,
                "map_bit": 0,
                "depends_on_map_bits": [
                ] /* depends_on_map_bits */
              }
            ] /* table_dependencies */
          },
          {
            "rows_estimation": [
              {
                "table": "`employees`",
                "table_scan": {
                  "rows": 100036,
                  "cost": 353
                } /* table_scan */
              }
            ] /* rows_estimation */
          },
          {
            "considered_execution_plans": [
              {
                "plan_prefix": [
                ] /* plan_prefix */,
                "table": "`employees`",
                "best_access_path": {
                  "considered_access_paths": [
                    {
                      "rows_to_scan": 100036,
                      "access_type": "scan",
                      "resulting_rows": 100036,
                      "cost": 20360,
                      "chosen": true
                    }
                  ] /* considered_access_paths */
                } /* best_access_path */,
                "condition_filtering_pct": 100,
                "rows_for_plan": 100036,
                "cost_for_plan": 20360,
                "chosen": true
              }
            ] /* considered_execution_plans */
          },
          {
            "attaching_conditions_to_tables": {
              "original_condition": null,
              "attached_conditions_computation": [
              ] /* attached_conditions_computation */,
              "attached_conditions_summary": [
                {
                  "table": "`employees`",
                  "attached": null
                }
              ] /* attached_conditions_summary */
            } /* attaching_conditions_to_tables */
          },
          {
            "clause_processing": {
              "clause": "ORDER BY",
              "original_clause": "`employees`.`age`",
              "items": [
                {
                  "item": "`employees`.`age`"
                }
              ] /* items */,
              "resulting_clause_is_simple": true,
              "resulting_clause": "`employees`.`age`"
            } /* clause_processing */
          },
          {
            "reconsidering_access_paths_for_index_ordering": {
              "clause": "ORDER BY",
              "steps": [
              ] /* steps */,
              "index_order_summary": {
                "table": "`employees`",
                "index_provides_order": false,
                "order_direction": "undefined",
                "index": "unknown",
                "plan_changed": false
              } /* index_order_summary */
            } /* reconsidering_access_paths_for_index_ordering */
          },
          {
            "refine_plan": [
              {
                "table": "`employees`"
              }
            ] /* refine_plan */
          }
        ] /* steps */
      } /* join_optimization */
    },
    {
      "join_execution": {
        "select#": 1,
        "steps": [
          {
            "filesort_information": [
              {
                "direction": "asc",
                "table": "`employees`",
                "field": "age"
              }
            ] /* filesort_information */,
            "filesort_priority_queue_optimization": {
              "limit": 10,
              "rows_estimate": 304128,
              "row_size": 8,
              "memory_available": 262144,
              "chosen": true
            } /* filesort_priority_queue_optimization */,
            "filesort_execution": [
            ] /* filesort_execution */,
            "filesort_summary": {
              "rows": 11,
              "examined_rows": 100003,
              "number_of_tmp_files": 0,
              "sort_buffer_size": 176,
              "sort_mode": "<sort_key, rowid>"
            } /* filesort_summary */
          }
        ] /* steps */
      } /* join_execution */
    }
  ] /* steps */
}

结论：由trace 倒数第 8 行 “sort_mode”: “<sort_key, rowid>” 得出为双路排序

对比及选择

其实对比两个排序模式，单路排序会把所有需要查询的字段都放到 sort buffer 中，而双路排序只会把主键 和需要排序的字段放到 sort buffer 中进行排序，然后再通过主键回到原表查询需要的字段。

如果 MySQL 排序内存 sort_buffer 配置的比较小并且没有条件继续增加了，可以适当把 max_length_for_sort_data 配置小点，让优化器选择使用双路排序算法，可以在sort_buffer 中一次排序更 多的行，只是需要再根据主键回到原表取数据。

如果 MySQL 排序内存有条件可以配置比较大，可以适当增大 max_length_for_sort_data 的值，让优化器 优先选择全字段排序(单路排序)，把需要的字段放到 sort_buffer 中，这样排序后就会直接从内存里返回。

⚠️如果全部使用sort_buffer内存排序一般情况下效率会高于磁盘文件排序，但不能因为这个就随便增 大sort_buffer(默认1M)，mysql很多参数设置都是做过优化的，不要轻易调整。

Tags: mysql
← in、exist 与 count(*)优化 JOIN 优化 及 NLJ&BNL 算法 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章