MySQL 排序原理详解与分页重复等异常案例排查

1. 索引与排序优化的基本原则

最优的 SQL 排序是利用索引本身的有序性来消除排序开销（即避免出现 Using filesort）。若查询条件和排序字段符合索引的最左前缀原则或完全匹配，MySQL 可直接扫描索引获取有序结果。

可利用索引避免排序的场景：

• 排序字段与复合索引的前缀完全一致：SELECT * FROM t1 ORDER BY key_part1, key_part2;
• 对索引的第一部分进行常量过滤后，按第二部分排序：... WHERE key_part1 = constant ORDER BY key_part2;
• 索引第一部分是范围查询且只按该列升序排列：... WHERE key_part1 > constant ORDER BY key_part1 ASC;

无法利用索引而需回表排序的场景：

• 排序键的顺序与索引定义顺序不一致（如索引为 (a,b)，却 ORDER BY b,a）。
• 混合使用不同的升降序（如 ORDER BY a DESC, b ASC）。
• 存在范围查询导致索引断裂：WHERE key_part1 > constant ORDER BY key_part2，此时 key_part2 在内存中不再连续有序。
• 涉及的排序列分散在不同的索引中，无法单次扫描覆盖。

2. 内部排序算法与实现流程

当必须执行排序时，MySQL 会根据数据量、缓冲区和返回字段的大小选择不同的策略，主要涉及 sort_buffer_size 和 max_length_for_sort_data 两个参数。

第1步：常规排序（Common Sort Method）

适用条件： 默认排序，或者元组数据过大超过 max_length_for_sort_data。

1. 收集排序键与主键： 遍历符合条件的行，将 (id, sort_key) 放入 sort buffer。若空间不足，则将当前 buffer 内的数据快速排序后写入临时文件，采用归并排序处理多文件。
2. 二次定位（Back to table）： 读取排好序的 (id, sort_key)，根据乱序的 id 回表查询完整行数据。
   为了减少随机 IO，MySQL 会将提取到的 id 序列先暂存在 read_rnd_buffer_size 缓冲区，排序后再顺序发起请求。
3. 缺陷： 存在两次 IO，且第一次回表是大量的随机 IO。

-- 示例表结构
CREATE TABLE t1(id int, col1 varchar(64), col2 varchar(64), PRIMARY KEY(id));
-- 此语句可能触发常规排序
SELECT col1,col2 FROM t1 WHERE col1>100 ORDER BY col2;

第2步：优化排序（Optimized Sort Method）

适用条件： 排序所需的所有列都包含在查询中（Select List），且元组长度小于 max_length_for_sort_data。

1. 收集完整元组： 直接将查询需要的完整列值（而非 id + sort_key）存入 sort buffer。
2. 直接返回： 排序完成后直接从 buffer 中输出结果，省去了第二次回表操作。
3. 代价： 由于单个元组变大，sort buffer 能容纳的行数变少，更容易溢出产生临时文件导致额外的磁盘 IO。

第3步：优先队列排序（Priority Queue Sorting）

适用场景： 带有 LIMIT 子句的查询（如 ORDER BY ... LIMIT M,N），从 MySQL 5.6 引入。

基于堆排序（Heap Sort）思想。若需要获取前 N 条记录，只需维护一个大小为 N 的大顶堆（或大顶堆取最小值逻辑，视实现细节而定，通常用于 Top N 场景）。无论总数据量多大，Space 复杂度仅为 O(N)，极大地降低了内存占用并避免了磁盘文件的生成。

3. 常见排序异常案例分析

案例 1：MySQL 5.6+ 分页数据重复问题

现象： 升级数据库版本后，相同 SQL 进行 LIMIT 分页查询时，发现相邻页面的数据出现重叠（如 Page 1 最后一条记录出现在 Page 2 中）。

原因分析：
MySQL 5.6 针对带 LIMIT 的查询启用了优先队列排序（基于堆排序）。堆排序是一种不稳定排序算法。当排序关键字（Sort Key）的值相同时，它们在堆中的相对位置是不确定的，可能与原始存储位置发生交换。

假设查询 ORDER BY c1 LIMIT 0,3，若 c1 有多个值为 2 的记录，堆排序在处理这些相等元素时的顺序可能与物理存储顺序不一致。第二页 LIMIT 3,3 基于上一页结束点继续取，但由于断点元素的不确定性，导致“漏取”或“重取”。

解决方案：
在 ORDER BY 之后增加一个唯一性字段（通常是主键 ID），打破排序键的唯一性限制，使比较变得绝对有序。

-- 错误写法
SELECT * FROM t1 ORDER BY c1 LIMIT 0,3;

-- 正确写法
SELECT * FROM t1 ORDER BY c1, id LIMIT 0,3;

案例 2：同表查询返回结果的相对顺序不一致

现象： 两条几乎相同的 SQL，仅仅因为查询字段不同（导致返回元组大小不同），排序后的数据顺序产生了细微变化（如同为 status=2 的两条记录互换了先后）。

测试表结构与数据：

create table t2(id int primary key, status int, c1 varchar(255),c2 varchar(255));
insert into t2 values(7,1,'a',repeat('a',255));
insert into t2 values(6,2,'b',repeat('a',255));
insert into t2 values(5,2,'c',repeat('a',255));
-- ... 省略其他插入语句
-- 确保 c1 上有索引

对比 SQL：

-- SQL A: 返回列多，元组长
select id,status,c1,c2 from t2 force index(c1) where c1>='b' order by status;

-- SQL B: 返回列少，元组短
select id,status from t2 force index(c1) where c1>='b' order by status;

执行计划：

原理解析：

两句话的逻辑都是先通过 c1 索引定位 ID，再回表查数据。关键在于回表后的排序方式：

• SQL B（短元组）： 返回的列字节总数小于 max_length_for_sort_data。MySQL 采用优化排序，将完整数据装入 Sort Buffer 排序后直接返回，保持了索引扫描的物理顺序稳定性。
• SQL A（长元组）： 返回的列字节总数超过了 max_length_for_sort_data。MySQL 强制降级为常规排序。常规排序模式下，MySQL 会将拿到的 ID 先经过 read_rnd_buffer 缓存区重新排序（以换取顺序 IO），然后再回表查询。这种额外的 ID 重排步骤打破了原始索引下的物理关联顺序。

验证与修复：

可以将 max_length_for_sort_data 调大，使得 SQL A 也能进入优化排序模式，从而保证两种查询返回的顺序一致性。

4. 补充技巧：自定义字段顺序排序

在进行非自然顺序的数据展示时，除了标准的 ASC/DESC，可以使用 FIELD(), INSTR() 或 LOCATE() 函数。

例如，想要特定 ID（2, 3, 5, 4）排在前面，其余按默认顺序：

| id | user |
|----|------|
| aaa| aaa  |
| bbb| bbb  |
| ccc| ccc  |
| ddd| ddd  |
| eee| eee  |
| fff| fff  |

方法一：FIELD 函数
计算每个 ID 在指定列表中的位置索引。

SELECT * FROM `user` ORDER BY FIELD(id, '2', '3', '5', '4') ASC;
-- 注意：如果id本身不是数字，直接用字符串比较。这里演示逻辑为：指定了顺序则靠前。
-- 上述例子中，如果希望手动控制顺序，更通用的做法是使用 CASE WHEN 或 UNION ALL。

注：原文献中使用的是 field(2,3,5,4,id) 这种将变量置于最后的旧版语法或特定场景用法，标准用法通常是 ORDER BY FIELD(id, '目标值1', '目标值2')。匹配度越高，返回值越小，配合 ASC 即可置顶。

方法二：INSTR / LOCATE 函数
查找 ID 在逗号分隔字符串中的起始位置。

SELECT * FROM `user` ORDER BY INSTR(',2,3,5,4,', CONCAT(',',id,',')) ASC;

对于未在列表中出现的 ID，函数返回 0，配合 ASC 会排在列表元素后面（若需要列表在最后，则用 DESC）。