威伦特

当我们想在分页查询中对数据进行排序展示时，通常会使用 ORDER BY 进行排序。然而，当用于排序的字段并非唯一时，可能会在翻页时遇到数据重复的问题，下面是对这个问题的具体分析和解决方案。

问题场景

在 MySQL 中，我们通常使用 limit 进行分页查询。例如，limit(0,10) 表示获取第一页的 10 条数据，limit(10,10) 表示获取第二页的 10 条数据。

当我们想在分页查询中对数据进行排序展示时，通常会使用 order by 进行排序。然而，当用于排序的字段并非唯一时，可能会在翻页时遇到数据重复的问题：翻到第二页时，可能再次看到第一页的记录。这种情况会导致数据重复的问题。

问题复现

首先创建一个数据表，插入一些数据

create table table_name
(
    id   int         null,
    name varchar(10) null
);
INSERT INTO table_name (id, name) VALUES (0, '3d');
INSERT INTO table_name (id, name) VALUES (1, '1d');
INSERT INTO table_name (id, name) VALUES (1, '2d');
INSERT INTO table_name (id, name) VALUES (1, '3d');
INSERT INTO table_name (id, name) VALUES (1, '4d');
INSERT INTO table_name (id, name) VALUES (1, '5d');
INSERT INTO table_name (id, name) VALUES (1, '6d');
INSERT INTO table_name (id, name) VALUES (1, '7d');
INSERT INTO table_name (id, name) VALUES (1, '8d');
INSERT INTO table_name (id, name) VALUES (2, '4d');

这里我们首先不使用 limit 进行分页，直接 order by id 进行查询数据，

select * from table_name order by id;

结果如下：

然后进行 limit 分页

select * from table_name order by id limit 0,2;

select * from table_name order by id limit 2,2;

结果如下：

第一页数据

第二页数据

可以看到 id 为 1 ，name 为 2d 的数据出现了两次

问题分析

查阅 MySQL 官方文档，发现官方对 LIMIT 的说明如下，我这里选择关键部分进行说明：

• If you combine LIMIT row_count with ORDER BY, MySQL stops sorting as soon as it has found the first row_count rows of the sorted result, rather than sorting the entire result. If ordering is done by using an index, this is very fast. If a filesort must be done, all rows that match the query without the LIMIT clause are selected, and most or all of them are sorted, before the first row_count are found. After the initial rows have been found, MySQL does not sort any remainder of the result set.One manifestation of this behavior is that an ORDER BY query with and without LIMIT may return rows in different order, as described later in this section.

  也就是说如果将 LIMIT row_count 与 ORDER BY 结合使用，并且是走的索引，MySQL 会在找到排序结果的前 row_count 行后就停止排序，而不是对整个结果进行排序，结果会非常快，因为利用的是索引的有序性。

  如果是走的 filesort ，MySQL 将会找到与 Select 匹配的所有行（也就是原语句不包含 LIMIT ），这些行将作为待排序的数据，进行 filesort 直到满足 Limit 条件的行数。满足的行数一旦找到，则不会对剩余的数据进行排序。

• If multiple rows have identical values in the ORDER BY columns, the server is free to return those rows in any order, and may do so differently depending on the overall execution plan. In other words, the sort order of those rows is nondeterministic with respect to the nonordered columns.

  One factor that affects the execution plan is LIMIT, so an ORDER BY query with and without LIMIT may return rows in different orders. Consider this query, which is sorted by the category column but nondeterministic with respect to the id and rating columns:

  如果多个行在 ORDER BY 列中具有相同的值，则 MySQL 可以自由地以任何顺序返回这些行，并且可以根据总体执行计划以不同的方式返回。换句话说，相对于不确定排序的序列，这些行的排序顺序是不确定的。

filesort

MySQL 的 filesort 通常有两种排序方式：

• 如果待排序的数据量小于排序缓冲区的大小，排序将在内存中完成（快速排序）。
• 如果待排序的数据量大于排序缓冲区的大小，排序将使用临时文件在外部完成（合并排序）。

在 filesort 排序后，根据上述 MySQL 官方文档的说明，返回的查询结果都是从排序后的结果集中按顺序提取的。因此，无论是否存在 LIMIT 子句，结果中都不应出现重复的数据。

那么，为什么会出现数据重复的问题呢？

问题的根源在于 MySQL 5.6 版本及其以后的优化。在这些版本中，当排序字段没有索引且列值不唯一时，MySQL 对 ORDER BY + LIMIT 语句进行了优化，采用了优先队列算法。

这种优化通过优先队列处理 ORDER BY + LIMIT 的语句，可能导致在某些情况下出现数据重复的问题。这种行为的具体机制可以通过查阅 MySQL 官网对 filesort.cc 的伪代码来了解。

while (get_next_sortkey())
   {
     if (using priority queue)
       push sort key into queue
     else
     {
       try to put sort key into buffer;
       if (no free space in sort buffer)
       {
         do {
           allocate new, larger buffer;
           retry putting sort key into buffer;
         } until (record fits or no space for new buffer)
         if (no space for new buffer)
         {
           sort record pointers (all buffers);
           dump sorted sequence to 'tempfile';
           dump Merge_chunk describing sequence location into 'chunk_file';
         }
       }
       if (key was packed)
         tell sort buffer the actual number of bytes used;
     }
   }
   if (buffer has some elements && dumped at least once)
     sort-dump-dump as above;
   else
     don't sort, leave sort buffer to be sorted by caller.

优化的逻辑如下MySQL :: WL#1393: Optimizing filesort with small limit

Many web customers have to do
"SELECT ... ORDER BY non_index_column LIMIT X",

When X *  is smaller than sort_buff_size we can use
the following algoritm to speed up the sort:

- Create a queue to hold 'limit' keys.
- Scan through the table and store the first (last if DESC) keys in the queue
- Return values from queue

This is much faster than the current algoritm that works as:

在 MySQL 中，如果排序使用合并或快速排序，则需要对所有数据进行排序，然后取的前几个条目，这就会导致的数据将会被浪费掉。

如果使用优先队列，优先队列其实就是通过堆来实现的。只需遍历此堆中的所有数据即可得到结果。

优先队列

堆排序是一种不稳定的排序算法，其不稳定性源于以下两个方面：

1. 建堆阶段：在这个阶段，待排序元素被构建成一个堆（通常是大顶堆或小顶堆）。构建堆的过程从最后一个非叶子节点开始，逐步向上调整，使每个节点都满足堆的性质。在此过程中，可能需要交换节点的位置来维持堆的性质。这些交换操作会改变相同键值元素的相对顺序，导致排序的不稳定性。
2. 排序阶段：每次从堆顶取出最大（或最小）元素，并将其放置在已排序部分的末尾。然后，对剩余的未排序部分进行堆调整，并重复此过程，直到所有元素都被正确放置。在这一过程中，交换操作进一步破坏了相同键值元素的相对顺序，导致排序的不稳定性。

总结而言，堆排序通过不断调整元素位置来实现排序，而这些调整可能会改变相同键值元素的相对顺序，因此堆排序是不稳定的排序算法。

SQL 语句分析

按照我们前面 SQL 语句的例子：

select * from table_name order by id limit 0,2;

在 MySQL 中，LIMIT 的语法为 LIMIT offset, row_count，其中 offset 是要跳过的行数，row_count 是要返回的行数。

在这个查询中，MySQL 会构建一个大小为 offset + row_count的最小堆，在这个例子中也就是 2 。在读取数据和排序过程中，MySQL 会维护这个堆，最终返回排序结果为这个堆中跳过 offset 大小后 row_count 的数据。

而由于堆排序的不稳定性，相同键值的元素可能会因交换操作而改变相对顺序进行排序的结果进行返回。从而导致数据重复的问题

验证

前面我们执行的 MySQL 语句走的就是 filesort

explain select * from table_name order by id limit 0,2;

[
  {
    "id": 1,
    "select_type": "SIMPLE",
    "table": "table_name",
    "partitions": null,
    "type": "ALL",
    "possible_keys": null,
    "key": null,
    "key_len": null,
    "ref": null,
    "rows": 10,
    "filtered": 100,
    "Extra": "Using filesort"
  }
]

进一步验证 MySQL 是否在这个语句上优化使用了优先队列

SET optimizer_trace='enabled=on';
select * from table_name order by id limit 0,2;
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G;

部分输出如下：

    "filesort_priority_queue_optimization": {
      "limit": 2,
      "chosen": true
    },

可以看到filesort_priority_queue_optimization.chosen = true，确实是走的优先队列

解决方案

综上所述，我们以及找到问题的原因了。简单来说就是 ORDER BY + LIMIT 排序的字段数据不唯一，并且没有索引会导致 MySQL 排序走了 filesort ，而 MySQL 5.6 对 filesort 的优化最终导致了重复数据的问题。

根据分析，我们可以从三个方面去解决这个问题：

1. 更换 MySQL 版本： 由于优先队列是在 MySQL 5.6 版本及其以后应用的，所以将 MySQL 版本更换到 5.6 以下就会解决这个问题；
2. 给 ORDER BY排序的字段加索引： ORDER BY 中的字段添加索引，可以避免 MySQL 走 filesort，而是直接根据索引的有序性进行排序，从而避免数据重复。然而，添加索引会增加表的存储空间和维护成本。
3. 确保排序字段唯一：通过在 ORDER BY 中添加一些唯一的字段，确保每个排序结果的数据都是唯一的。

参考文献

• MySQL :: MySQL 8.4 Reference Manual :: 10.2.1.19 LIMIT Query Optimization

• Duplicate results in mysql query when try to sort on null field by with limit and offset - Database Administrators Stack Exchange

• SQL - Is Your Sort Order Deterministic? A classic example of S.E.P. (Somebody Else’s Problem)

• MySQL Paging Sorting with Data Duplication Problem (MySQL Priority Queue) - SoByte

• MySQL: sql/filesort.cc File Reference