跳到主要内容

排序、分组与 Join 原理

ORDER BY、GROUP BY、JOIN 到底怎么执行的 —— 这三个是「SQL 为什么慢」追问链的终点，也是最能区分「会用」和「懂原理」的题目。

🔥 ORDER BY 的两种排序模式​

查询 SELECT city, name, age FROM t WHERE city='深圳' ORDER BY name LIMIT 1000，假设 city 有索引、name 没有。

全字段排序​

  1. 初始化 sort_buffer，放入 name、city、age 三个字段
  2. 从 city 索引取出满足条件的主键，回表取这三个字段，存进 sort_buffer
  3. 对 sort_buffer 按 name 快速排序
  4. 取前 1000 行返回

如果 sort_buffer_size 装不下，就要用外部排序 —— 把数据分成多份，每份在内存里排好序写成临时文件，最后做归并排序。explain 看不出来，要用：

SET optimizer_trace='enabled=on';
SELECT ...;
SELECT * FROM information_schema.OPTIMIZER_TRACE;
-- 看 number_of_tmp_files：0 表示全内存排序，>0 表示用了临时文件

rowid 排序​

如果单行太大（字段多或字段长），放进 sort_buffer 的行数太少，归并的临时文件会很多。此时 MySQL 改用 rowid 排序：

  1. sort_buffer 里只放 name 和 id
  2. 按 name 排序
  3. 按排好的顺序，再回表一次取 city、age 返回

触发条件：单行长度超过 max_length_for_sort_data（默认 1024 字节）。

:::tip 两种模式的取舍是 MySQL 的一贯倾向

全字段排序rowid 排序
sort_buffer 里存所有需要的字段排序字段 + 主键
回表次数1 次2 次
内存占用大小
临时文件风险高低

MySQL 优先选全字段排序 —— 体现的是「如果内存够，就要多利用内存，尽量减少磁盘访问」这个设计原则。只有单行实在太大时才退化为 rowid 排序。

MySQL 8.0.20 之后 max_length_for_sort_data 已被弃用，由优化器自行判断。 :::

真正的优化：让索引天然有序​

上面两种都是「不得不排序」。ORDER BY 并不一定需要排序 —— 如果索引本身就是按目标顺序组织的，直接顺序读就行：

ALTER TABLE t ADD INDEX city_name(city, name);
-- 现在 WHERE city='深圳' ORDER BY name 完全不需要排序
-- explain 的 Extra 里 Using filesort 消失

再进一步做成覆盖索引，连回表都省了：

ALTER TABLE t ADD INDEX city_name_age(city, name, age);
-- Extra: Using index

这是「ORDER BY 优化」的标准答案 —— 不是调大 sort_buffer_size，而是建对索引让排序消失。

ORDER BY ... LIMIT N 的优先队列优化​

当 LIMIT N 的 N 很小时，MySQL 不做全量排序，而是用堆（优先队列）：维护一个大小为 N 的堆，扫描过程中不断替换堆顶。复杂度从 O(n log n) 降到 O(n log N)，内存从全量降到 N 行。

optimizer_trace 里会显示 "filesort_priority_queue_optimization": {"chosen": true}。

:::warning ORDER BY RAND() 为什么是性能杀手 SELECT * FROM t ORDER BY RAND() LIMIT 3 —— 要给每一行算一个随机数，然后对全表做排序（通常是 rowid 排序 + 临时文件），只为取 3 行。

正确做法：先 SELECT COUNT(*)，再在应用层生成随机 offset，用 LIMIT offset, 1 单独取（或者用主键范围随机）。 :::

GROUP BY 的执行​

没有合适索引时，GROUP BY 用内存临时表：

  1. 创建一个内存临时表，以分组字段为唯一索引
  2. 扫描原表，逐行往临时表里 INSERT ... ON DUPLICATE KEY UPDATE 式地累加
  3. 临时表超过 tmp_table_size（默认 16MB）就转成磁盘临时表（InnoDB 引擎）
  4. 最后对临时表排序返回

三种优化：

手段做法
加索引（最优）让分组字段有序，MySQL 直接顺序扫描边读边聚合，Extra 显示 Using index for group-by，无需临时表
SQL_BIG_RESULT告诉优化器数据量很大，直接用排序代替临时表（排序能落盘，临时表转磁盘的开销更大）
加 ORDER BY NULL5.7 及之前 GROUP BY 会隐式排序，加这个能去掉排序步骤

:::warning MySQL 8.0 移除了 GROUP BY 的隐式排序 5.7 及之前，GROUP BY c 会顺带按 c 排序。8.0 取消了这个行为。

后果：从 5.7 升级到 8.0 后，依赖隐式排序的代码结果顺序会变，而且不报错。排查这类「升级后顺序乱了」的问题，根因就在这里。凡是依赖顺序的查询都必须显式写 ORDER BY。 :::

🔥 Join 的三种算法​

SELECT * FROM t1 STRAIGHT_JOIN t2 ON t1.a = t2.a;

STRAIGHT_JOIN 强制 t1 做驱动表（左表），便于分析。

Index Nested-Loop Join（NLJ）​

被驱动表的关联字段有索引时使用：

遍历 t1（N 行）
  ↓ 每行取出 a 值
  去 t2 的索引上查（树高 h，约 2·log₂M 次扫描）
  • 扫描行数 ≈ N + N·2·log₂M
  • 复杂度由驱动表行数 N 主导
  • 结论：小表做驱动表

Block Nested-Loop Join（BNL）​

被驱动表没有索引时使用。注意不是朴素的 Simple Nested-Loop（那是 N×M 次磁盘扫描，MySQL 不用）：

把 t1 整表读进 join_buffer（内存）
  ↓
顺序扫描 t2 一遍（M 行）
  ↓ 每行在 join_buffer 里做内存比较
  • 磁盘扫描行数 = N + M（都只扫一遍）
  • 内存比较次数 = N × M ← 代价在这里
  • join_buffer_size 装不下 t1 时要分块：分 K 块就要扫 t2 K 遍，变成 N + K·M

:::danger BNL 的三重危害

  1. 多次扫描被驱动表 —— 分块后 t2 被反复全表扫，大量磁盘 IO
  2. N×M 次内存比较 —— 单线程 CPU 打满
  3. 污染 Buffer Pool —— 被驱动表的数据页被反复读入。更阴险的是：如果被驱动表是大于 Buffer Pool old 区的冷表，且两次扫描间隔超过 1 秒（innodb_old_blocks_time），这些冷数据页会晋升到 young 区，把真正的热点数据全部挤出去。业务的整体命中率下降，影响会持续很久

所以 explain 里看到 Using join buffer (Block Nested Loop) 要当成告警，优先给被驱动表的关联字段加索引。 :::

Hash Join（8.0.18+）​

BNL 的 N×M 内存比较是纯粹的浪费 —— 这本该是哈希表的活。MySQL 8.0.18 终于加上了 Hash Join：

扫描 t1，在内存里建哈希表
  ↓
扫描 t2，每行用 O(1) 的哈希查找匹配

比较次数从 N×M 降到 N+M。MySQL 8.0.20 起彻底移除了 BNL，等值 join 无索引时一律走 hash join。

所以「join 没索引会很慢」这个结论在 8.0.18+ 已经大幅缓和 —— 面试能指出这个版本差异很加分。

MRR 与 BKA​

MRR（Multi-Range Read） —— 优化回表。二级索引取出的主键是乱序的，逐个回表是随机 IO。MRR 先把主键攒起来排序，再按主键顺序回表，变成接近顺序的 IO，还能利用预读。

SET optimizer_switch='mrr_cost_based=off';   -- 让优化器更倾向用 MRR
-- Extra 显示 Using MRR

BKA（Batched Key Access） —— 把 MRR 的思想用到 join 上：攒一批驱动表的关联值，排序后批量去被驱动表查。

SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

BKA 是对 NLJ 的优化（有索引时用），Hash Join 是对 BNL 的替代（无索引时用），两者解决的是不同情形。

Join 的实践规则​

  1. 被驱动表的关联字段必须有索引（让它走 NLJ 而不是 BNL）
  2. 小表做驱动表 —— 注意「小」指的是参与 join 的数据量（过滤条件之后的行数 × 字段大小），不是表的总行数
  3. 控制 join 的表数量 —— 阿里规范是「禁止超过三张表 join」，因为优化器对多表 join 的顺序选择容易出错
  4. LEFT JOIN 的左表固定是驱动表，INNER JOIN 由优化器决定（可能和你写的顺序不同，看 explain）

🔥 COUNT(*) 的实现​

为什么 InnoDB 的 COUNT(*) 比 MyISAM 慢？

  • MyISAM 把总行数存在磁盘上，COUNT(*) 直接返回，O(1)。但加了 WHERE 条件就没这个优化了
  • InnoDB 必须逐行扫描累计。根本原因是 MVCC —— 由于多版本并发控制，「这张表有多少行」这个问题在同一时刻对不同事务有不同的答案，所以不存在一个可以缓存的「真实行数」

InnoDB 的优化是：COUNT(*) 时优化器会选最小的那棵索引树来扫描（普通索引树比主键索引树小得多，因为不含完整行数据）。

几种 count 的性能排序：

COUNT(*) ≈ COUNT(1) < COUNT(主键 id) < COUNT(字段)
  • COUNT(*) —— 专门优化过，不取值，只累加行数
  • COUNT(1) —— 遍历每行，放一个常数 1 进去判断非空，不解析行字段
  • COUNT(id) —— 要把 id 字段取出来返回给 server 层判断非空
  • COUNT(字段) —— 要取字段值 + 判断是否为 NULL（NULL 不计数，语义也不同）

结论：用 COUNT(*)，它语义清楚且性能最好。

SHOW TABLE STATUS 的 Rows 不能用 —— 它是采样估算值，误差可达 40～50%。

用 Redis 存计数的问题：Redis 和 MySQL 是两个系统，无法放进同一个事务，所以必然存在「查到了计数但那条记录还没插入」或反之的不一致窗口。即使调整顺序也只能减小窗口不能消除。

正解是把计数放在 MySQL 的一行里 —— 更新计数和插入数据放进同一个事务，靠事务的隔离性保证「计数和实际数据永远一致」。性能靠行锁的并发控制和热点行拆分来解决。

LIMIT 的一个反直觉现象​

SELECT * FROM t ORDER BY id LIMIT 1;      -- 快
SELECT * FROM t ORDER BY name LIMIT 1;    -- 可能很慢（要全表排序）

还有一个更隐蔽的：

SELECT * FROM t WHERE 条件 ORDER BY id LIMIT 1;

如果 条件 的选择性很差，优化器可能选择走主键索引顺序扫描（因为 ORDER BY id LIMIT 1 看起来只要扫一行就能停），结果扫了几百万行才找到第一个满足条件的。这类「加了 LIMIT 反而更慢」的案例，根因都是优化器误判。用 FORCE INDEX 或改写 SQL 解决。

最后于 更新