# 排序优化

当不能使用索引生成排序结果的时候，MySQL 需要自己进行排序，<mark style="color:blue;">**如果数据量小则在内存中进行，如果数据量大则需要使用磁盘**</mark>，不过 **MySQL 将这个过程统一称为**<mark style="color:blue;">**文件排序（filesort）**</mark>，即使完全是在内存中排序不需要任何磁盘文件时也是如此。

## 排序缓冲区

**如果需要排序的数据量小于“排序缓冲区”，MySQL 使用内存进行**<mark style="color:blue;">**快速排序**</mark>**操作**。如果内存不够排序，那么 MySQL 会先将数据分块，**对每个独立的块使用“快速排序”进行排序**，并将各个块的排序结果存放在磁盘上，然后将各个排好序的块进行**合并(merge)**，最后返回排序结果。

{% hint style="info" %}
"排序缓冲区"的大小由变量 <mark style="color:blue;">**sort\_buffer\_size**</mark> 确定。<mark style="color:blue;">**sort\_buffer\_size**</mark> 设置的排序区是<mark style="color:blue;">**每个线程独占**</mark>的，所以同一个时刻，MySQL 中存在多个 sort buffer (排序缓冲区)。
{% endhint %}

## 排序算法

MySQL 有如下两种排序算法：

* <mark style="color:blue;">**两次传输排序**</mark>（旧版本使用）\
  **读取行指针和需要排序的字段，对其进行排序，然后再根据排序结果读取所需要的数据行**。\
  这需要进行两次数据传输，即需要从数据表中读取两次数据，第二次读取数据的时候，因为是读取排序列进行排序后的所有记录，这**会产生大量的随机 I/O**，所以两次传输排序的成本非常高。
* <mark style="color:blue;">**单次传输排序**</mark>（新版本使用）\
  **先读取查询所需要的所有列，然后再根据给定列进行排序，最后直接返回排序结果**。\
  因为不再需要从数据表中读取两次数据，对于 I/O 密集型的应用来说，这样做的效率高了很多。另外，相比两次传输排序，这个算法只需要一次顺序 I/O 就可读取所有的数据，而无须任何的随机 I/O。\
  然而，这种方式可能占用更多空间，因为会保存查询中每一行所需要的列，而不仅仅是进行排序操作所需要的列。**这意味着更少的元组可以放入排序缓冲区，使得文件排序（filesort）操作必须执行更多的排序合并过程。**

{% hint style="warning" %} <mark style="color:orange;">**MySQL 在进行文件排序时需要使用的临时存储空间可能会比想象的要大得多。**</mark>

原因在于 **MySQL 在排序时，对每一个排序记录都会分配一个足够长的**<mark style="color:blue;">**定长空间**</mark>**来存放**。这个定长空间必须足够长才能容纳其中最长的字符串，例如，如果是 **VARCHAR** 列，则需要分配其完整长度；如果使用 **utf8mb4** 字符集，那么 MySQL 将会为每个字符预留 4 字节。
{% endhint %}

## 联接时的排序

<mark style="color:blue;">**在联接查询的时候如果需要排序**</mark>，MySQL 会分两种情况来处理这样的文件排序：

* 如果 **ORDER BY 子句中的所有列都来自联接的第一个表**，那么 MySQL <mark style="color:blue;">**在联接处理第一个表的时候就进行文件排序**</mark>。

  如果是这样，那么在 MySQL 的 EXPLAIN 结果中可以看到 **Extra** 字段会有 “**Using filesort**” 字样。
* 除此之外的所有情况，MySQL 都会<mark style="color:blue;">**先将联接的结果存放到一个临时表中，然后在所有的联接都结束后，再进行文件排序**</mark>。

  在这种情况下，在 MySQL 的 EXPLAIN 结果的 **Extra** 字段可以看到 “**Using temporary；Using filesort**” 字样。如果查询中有 LIMIT 的话，LIMIT 也会在文件排序之后应用，所以即使需要返回较少的数据，临时表和需要排序的数据量仍然会非常大。
