排序 - 非官方 MySQL 8.0 优化指南 - 学习笔记

MySQL 有 4 种方式来返回有序结果。
EXPLAIN 可以展示查询是否需要排序操作，但不会列出使用了什么排序算法，这个信息在OPTIMIZER_TRACE中才会有。4 种方式如下：

1. 通过索引。B+ 树索引会维持有序，所以一些带ORDER BY的查询完全不需要执行排序操作。

2. 通过优先级队列。LIMIT条数很少的排序可以完全在临时缓冲区中完成。例如以下查询：

   SELECT * FROM Country IGNORE INDEX (p, p_c)
   ORDER BY population LIMIT 10;
   

   这个查询会用到全表扫描，并保存 10 个人口最多的行。随着新的拥有更多人口的进入，人口最少的行会从优先级队列中移出。

3. 通过交替排序算法（Alternative Sort Algorithm）。如果不存在 TEXT 或 BLOB 的列就会使用这个算法。它在 MySQL 手册中是这样定义的：

   1. 读取匹配 WHERE 条件的行。
   2. 对于每一行，记录包含排序列的值和额外字段的元组。
   3. 排序缓冲区满了后，对元组排序并写入临时表。
   4. 完成与临时表的归并排序后，重新取回有序的行，从有序元组中直接读取需要的列值。

4. 通过原有的文件排序算法（Filesort Algorithm）。当使用了 TEXT 或 BLOB 这样的列时就会使用这个算法。它在 MySQL 手册中是这样定义的：

   1. 通过索引或全表扫描读取所有匹配 WHERE 的行。
   2. 对于每一行，在排序缓冲区储存包含排序值 和 行 ID 的元组。
   3. 如果所有元组都能容纳在缓冲区，则不会创建临时表。否则，当缓冲区满时，会在内存中快速排序然后写到临时表。并保存有序块的指针。
   4. 重复处理以上步骤直到读取完所有行。
   5. 将最多 7 个区域块多重合并到另一个临时表中，直到所有块都写到第二个文件中。
   6. 重复直到剩下少于 15 个块。
   7. 在最后一次多重合并中，只有行 ID（元组的最后一部分）写到了结果文件中。
   8. 从结果文件中，通过行 ID 以有序方式读取行。为优化这一步骤，会读取一大块行 ID，排序，然后用它们从行缓冲区中读取有序的行。系统变量read_rnd_buffer_size就是行缓冲区的大小。

例子30：由索引提供的排序

EXPLAIN FORMAT=JSON
SELECT * FROM Country WHERE continent='Asia' ORDER BY population;

{
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "34.10"
    },
    "ordering_operation": {
      "using_filesort": false,  # 顺序是由索引（大洲，人口）提供的
      "table": {
        "table_name": "Country",
        "access_type": "ref",
        "possible_keys": [
          "c",
          "c_p"
        ],
        "key": "c_p",
        "used_key_parts": [
          "Continent"
        ],
        "key_length": "1",
        "ref": [
          "const"
        ],
        "rows_examined_per_scan": 51,
        "rows_produced_per_join": 51,
        "filtered": "100.00",
        "index_condition": "(`world`.`Country`.`Continent` <=> 'Asia')",
        "cost_info": {
          "read_cost": "23.90",
          "eval_cost": "10.20",
          "prefix_cost": "34.10",
          "data_read_per_join": "13K"
        },
        "used_columns": [
          ...
        ]
      }
    }
  }
}

例子31：OPTIMIZER_TRACE 表明使用了优先级队列

SET OPTIMIZER_TRACE="ENABLED=on";
SELECT * FROM Country IGNORE INDEX (p, p_c) ORDER BY population LIMIT 10;
SELECT * FROM information_schema.optimizer_trace

...
      "join_execution": {
        "select#": 1,
        "steps": [
          {
            "filesort_information": [
              {
                "direction": "asc",
                "table": "`Country` IGNORE INDEX (`p_c`) IGNORE INDEX (`p`)",
                "field": "Population"
              }
            ],
            "filesort_priority_queue_optimization": {
              "limit": 10,
              "rows_estimate": 939,
              "row_size": 272,
              "memory_available": 262144,
              "chosen": true                # 应用了优先级队列优化
            },
            "filesort_execution": [
            ],
            "filesort_summary": {
              "rows": 11,
              "examined_rows": 239,
              "number_of_tmp_files": 0,
              "sort_buffer_size": 3080,
              "sort_mode": "<sort_key, additional_fields>"
            }
...

译自：
Sorting - The Unofficial MySQL 8.0 Optimizer Guide