MySQL 系列 #14：MySQL 排序与聚合原理

深入剖析 MySQL ORDER BY / GROUP BY / DISTINCT 的底层实现：sort_buffer 结构、全字段排序 vs rowid 排序、外部归并排序、Packed sort 优化、哈希聚合 vs 有序聚合，以及如何用索引彻底消除 filesort。

目录

排序决策树

flowchart TD
    Q["ORDER BY 查询"] --> Idx{"排序列有可用索引<br/>且索引顺序匹配？"}
    Idx -->|"是"| Using["Using index<br/>（无需 filesort）"]
    Idx -->|"否"| Wide{"行数据宽度<br/>> max_length_for_sort_data？"}
    Wide -->|"否（行较窄）"| Single["全字段排序<br/>single-pass"]
    Wide -->|"是（行较宽）"| Rowid["rowid 排序<br/>two-pass"]
    Single --> Mem{"sort_buffer 够用？"}
    Rowid --> Mem
    Mem -->|"是"| InMem["内存快速排序<br/>（qsort）"]
    Mem -->|"否"| Merge["外部归并排序<br/>（磁盘临时文件）"]

    style Using fill:#cfc,stroke:#060
    style InMem fill:#cfc,stroke:#060
    style Merge fill:#fcc,stroke:#c00

EXPLAIN 关键字：Using filesort 表示走了 single-pass 或 two-pass，不一定在磁盘。只有 sort_merge_passes 状态变量 > 0 才说明真正溢出到磁盘。

sort_buffer 结构

每个需要排序的查询独占一个 sort_buffer（session 级，不共享）。

sort_buffer（连续内存区）
┌─────────────────────────────────────────────┐
│  sort_key(排序列) │  payload（返回列 或 rowid）│
│  sort_key │ payload │ sort_key │ payload │ … │
└─────────────────────────────────────────────┘

全字段排序（single-pass）：
  payload = 所有 SELECT 列值（行数据完整拷贝）

rowid 排序（two-pass）：
  payload = 主键值（InnoDB）或 rowid（MyISAM）

sort_buffer 内的比较使用快速排序（in-memory qsort），时间复杂度 O(n log n)。

全字段排序（single-pass）

执行步骤

以 SELECT name, age FROM t WHERE city='上海' ORDER BY name 为例：

1. 从索引 city 定位满足条件的行
2. 从聚簇索引取出 name, age（所有 SELECT 列）放入 sort_buffer
3. 重复步骤 1-2 直到所有满足行都放入 sort_buffer
4. 对 sort_buffer 中的数据按 name 排序（内存 qsort）
5. 顺序返回结果

sequenceDiagram
    participant Exec as 执行器
    participant SB as sort_buffer
    participant CI as 聚簇索引

    Exec->>CI: 按 city 条件扫描
    CI-->>Exec: rowid + 行数据
    loop 每一满足条件的行
        Exec->>SB: 写入 (name, age)
    end
    Exec->>SB: qsort 按 name 排序
    SB-->>Exec: 有序结果集，直接返回

优点：只扫描数据一次，无回表
缺点：sort_buffer 存的数据量大（宽行时很快耗尽）

rowid 排序（two-pass）

当行数据较宽（超过 max_length_for_sort_data，MySQL 8.0.20 后弃用，改为 sort_buffer_size 自动决策），MySQL 改用 rowid 排序，节省 sort_buffer 空间。

执行步骤

1. 从满足条件的行中，只取出 name（排序列）+ 主键 id 放入 sort_buffer
2. 对 sort_buffer 按 name 排序
3. 按排序后的 id 顺序，逐行回聚簇索引取 age 等返回列（第二次扫描）
4. 返回结果

sequenceDiagram
    participant SB as sort_buffer
    participant CI as 聚簇索引

    Note over SB: 第一次扫描：只存 name + id
    CI-->>SB: (name, id) × N 行
    SB->>SB: qsort 按 name 排序

    Note over SB,CI: 第二次扫描：按排序顺序回表取完整行
    loop 每个排序后的 id
        SB->>CI: 按 id 随机查找
        CI-->>SB: age 等返回列
    end

优点：sort_buffer 存储量少，能容纳更多行
缺点：第二次回表是随机 I/O，数据量大时比 single-pass 慢

设计取舍：MySQL 在两种方式间权衡 sort_buffer 利用率与回表开销。可通过调大 sort_buffer_size 减少 two-pass 场景。

外部归并排序

当 sort_buffer 装不下所有待排序数据时，MySQL 使用外部多路归并排序（external merge sort）。

执行步骤

阶段一：生成有序片段（runs）
  1. 将 sort_buffer 填满
  2. 对 sort_buffer 内数据做内存排序（qsort）
  3. 将有序结果写入磁盘临时文件（一个 run）
  4. 清空 sort_buffer，重复直到所有数据处理完
  → 生成 k 个有序临时文件

阶段二：多路归并
  将 k 个有序文件同时读取，用小顶堆做 k 路归并
  → 输出一个全局有序的结果

flowchart TD
    SB["sort_buffer（满）"] -->|"内存排序后写盘"| F1["临时文件 run1"]
    SB --> F2["临时文件 run2"]
    SB --> F3["临时文件 run3"]
    F1 & F2 & F3 -->|"k 路归并（小顶堆）"| Out["有序输出"]

    style F1 fill:#ffc,stroke:#990
    style F2 fill:#ffc,stroke:#990
    style F3 fill:#ffc,stroke:#990
    style Out fill:#cfc,stroke:#060

监控是否真正溢出：

SHOW STATUS LIKE 'Sort_merge_passes';
-- > 0 说明发生了外部归并，应考虑调大 sort_buffer_size

Packed Sort（MySQL 8.0+）

MySQL 8.0 引入 packed sort key（也称 varlen sort key），专门优化包含 VARCHAR / BLOB 等可变长字段的排序。

传统方式的问题

传统 sort_buffer 行：
  [sort_key: 定长填充至最大长度] [payload]
  e.g. VARCHAR(200) 的 "Hi" 仍占 200 字节 → sort_buffer 严重浪费

Packed Sort 改进

Packed sort_buffer 行：
  [length: 2字节] [sort_key: 实际长度] [payload]
  "Hi" 只占 2 + 2 = 4 字节 → sort_buffer 利用率大幅提升

效果：对 VARCHAR 列排序，sort_buffer 可以容纳更多行，减少外部归并次数，尤其在字符串数据平均长度远小于最大长度时效果显著。

无需配置，MySQL 8.0 自动启用。

利用索引消除排序

当 ORDER BY 列与已使用的索引顺序一致时，MySQL 直接按索引顺序读取行，无需 sort_buffer，EXPLAIN Extra 显示 Using index（覆盖索引）或无额外字段。

触发条件

索引：(city, name)
查询：WHERE city = '上海' ORDER BY name

✅ 可以利用索引顺序：
  city 等值 → name 有序，直接顺序读

索引：(city, name)
查询：WHERE city IN ('上海','北京') ORDER BY name

❌ 不能利用索引顺序：
  city 范围/多值 → name 在不同 city 内有序，全局无序
  → 仍需 filesort

联合索引与 ORDER BY 的匹配规则

GROUP BY 实现

有序聚合（Using index for group-by）

若分组列有索引且满足最左前缀，MySQL 直接按索引顺序扫描，流式计算聚合值，无需额外内存。

索引：(dept, salary)
查询：SELECT dept, MAX(salary) FROM t GROUP BY dept

执行流程：
  按 dept 顺序扫描索引
  遇到 dept 切换 → 输出上一个 dept 的聚合结果
  → 单次顺序扫描，O(n) 时间，O(1) 额外内存

EXPLAIN Extra：Using index for group-by 或 Using index

哈希聚合（Using temporary）

无法利用索引时，MySQL 建立内存哈希表存放分组状态。

查询：SELECT category, COUNT(*) FROM t GROUP BY category

执行流程：
  1. 全表扫描（或索引扫描）
  2. 每行按 category 计算哈希，写入内存哈希表（key=category, value=count）
  3. 哈希表满 → 转磁盘临时表（InnoDB 格式）
  4. 扫描完成后，遍历哈希表输出结果

flowchart LR
    Scan["全表扫描"] --> Hash{"内存哈希表<br/>< tmp_table_size"}
    Hash -->|"未超限"| Mem["内存累积聚合"]
    Hash -->|"超限"| Disk["磁盘临时表<br/>（InnoDB）"]
    Mem & Disk --> Out["遍历输出"]

    style Disk fill:#fcc,stroke:#c00
    style Mem fill:#cfc,stroke:#060

EXPLAIN Extra：Using temporary（有时同时出现 Using filesort，说明结果还需排序）

两种方式对比

DISTINCT 实现

DISTINCT 在 MySQL 内部与 GROUP BY 共用同一套机制：

-- 以下两个查询执行计划完全相同
SELECT DISTINCT city FROM t;
SELECT city FROM t GROUP BY city;

优化路径：

• 若 DISTINCT 列有索引 → 扫描索引，去重由顺序保证（Using index）
• 无索引 → 建立哈希表或临时表去重（Using temporary）
• 配合 LIMIT n → 找到 n 个不同值后立即停止扫描（Using filesort; Using temporary 可提前退出）

内部临时表

触发场景

以下操作会强制使用内部临时表：
1. GROUP BY 且无法利用索引
2. DISTINCT 且无法利用索引
3. UNION（合并两个子查询结果）
4. 子查询中的派生表（FROM 子句子查询）
5. 窗口函数（Window Functions）
6. INSERT INTO ... SELECT ... ORDER BY（目标表有触发器时）

内存 → 磁盘溢出过程

第一阶段：内存临时表（Memory/TempTable 引擎）
  容量限制：
    MySQL 5.7-：tmp_table_size 与 max_heap_table_size 取较小值
    MySQL 8.0+：temptable_max_ram（默认 1GB）

第二阶段：超限后转磁盘
  MySQL 5.7-：转为 MyISAM 磁盘临时表
  MySQL 8.0+：转为 InnoDB 磁盘临时表（或映射文件）

磁盘临时表位置：tmpdir 参数指定目录，文件名为随机 #sql*.tmp

MySQL 8.0 TempTable 引擎

MySQL 8.0 引入专用的 TempTable 引擎替代旧的 MEMORY 引擎用于内部临时表：

参数与优化建议

关键参数

# 每个 session 的排序缓冲区（默认 256KB，建议 1M-4M）
sort_buffer_size = 2M

# 内存临时表大小上限（默认 16MB）
tmp_table_size = 64M
max_heap_table_size = 64M     # 需与 tmp_table_size 同步设置（5.7-）

# MySQL 8.0 TempTable 内存上限
temptable_max_ram = 1G

# 临时文件目录（尽量用 SSD）
tmpdir = /tmp

EXPLAIN 关键标志速查

监控语句

-- 排序操作统计
SHOW STATUS LIKE 'Sort%';
-- Sort_rows：已排序行数
-- Sort_merge_passes：外部归并次数（>0 说明溢出磁盘）
-- Sort_range：使用范围扫描的排序次数
-- Sort_scan：使用全表扫描的排序次数

-- 临时表使用统计
SHOW STATUS LIKE 'Created_tmp%';
-- Created_tmp_tables：内存临时表创建次数
-- Created_tmp_disk_tables：磁盘临时表创建次数（重点关注）

优化清单

SQL_BIG_RESULT hint

-- 强制 MySQL 对 GROUP BY 使用磁盘临时表（有时比内存哈希表更快）
SELECT SQL_BIG_RESULT dept, COUNT(*) FROM employees GROUP BY dept;

参考资料

• MySQL 8.0 Reference — ORDER BY Optimization
• MySQL 8.0 Reference — GROUP BY Optimization
• MySQL 8.0 Reference — Internal Temporary Table Use in MySQL