自过去几周以来，我一直在更密切地研究 MySQL。MySQL 是一款出色的软件。我记得在大学里读过所有的排序算法，所以我很想知道 MySQL 使用哪种算法以及 ORDER BY 查询如何在内部以如此有效的方式工作。
我开始探索和深入挖掘它的开源代码，我对它的实现感到惊讶。
MySQL 是精明的。它的排序算法取决于几个因素 -
- 可用索引
- 结果的预期大小
- MySQL版本
MySQL 有两种方法来生成排序/有序的数据流。
1. 索引的巧妙运用
首先，MySQL 优化器分析查询并确定它是否可以利用可用的排序索引。如果是，它自然会按索引顺序返回记录。（例外是 NDB 引擎，它需要在从所有存储节点获取数据后执行合并排序）
交给 MySQL 优化器，他会聪明地判断索引访问方法是否比其他访问方法便宜。
在这里看到的真正有趣的事情是-
- 即使 ORDER BY 与索引不完全匹配，也可以使用索引，只要 ORDER BY 中的其他列是被索引的常量。
- 有时，如果与扫描表相比，优化器发现索引开销很大，则它可能不会使用索引。
假设，我们在用户表中的 基于userId 和 mobileNumber 有一个索引，我们运行以下查询 ：
SELECT * FROM USER |
在这里，您可能会觉得 userId 和 mobileNumber 上的索引使优化器能够使用索引，但此查询具有“ SELECT * ”，它选择的列不仅仅是 userId 和 mobileNumber。
在这种情况下，扫描整个索引以查找不在索引中的列比扫描表并对结果进行排序更昂贵。在这里，优化器可能不使用索引。
2.文件排序算法
如果索引不能用于满足ORDER BY子句，MySQL 将使用文件排序算法。这是一个非常有趣的算法。简而言之，它是这样工作的 -
- 它扫描整个表并找到与WHERE条件匹配的行
- 它维护一个缓冲区并存储其中每一行的几个值（排序键值、行指针和查询中所需的列）。这个块的大小是系统变量sort_buffer_size。
- 当缓冲区已满时，它会根据排序键对其进行快速排序，并将其安全地存储到磁盘上的临时文件中，并记住指向它的指针。
- 它将在数据块上重复相同的步骤，直到没有更多行。
- 现在，它有几个已排序的块。
- 最后，它对所有已排序的块应用归并排序，并将其放入一个结果文件中。
- 最后，它将从排序结果中获取行
如果预期结果适合一个块，则数据永远不会到达磁盘，而是保留在 RAM 中。
令您惊讶的是，假设我们的用户表中有 10 亿行，并且我们运行以下两个查询 ：
SELECT * FROM users ORDER BY userId ; |
MySQL 优化器足够聪明，可以理解，不值得使用归并排序（merge sort.）。所以，如果我们只想要一组结果，而不是整个数据，它就会使用堆排序（heap sort）。
按多列排序不需要两次扫描数据库！在 MySQL (<v4.1) 中，它曾经读取数据两次，一次是匹配 WHERE 子句中的行，另一次是从行指针准备结果。
MySQL ORDER BY 背后的智能算法 -
- 如果数据不适合内存，则外部归并排序（快速排序 + 归并排序）
- 快速排序，如果数据适合内存并且我们想要全部
- 堆排序，如果数据适合内存但我们使用 LIMIT 只获取一些结果
- 索引查找（不完全是排序算法，只是预先计算好的二叉树）
借助 EXPLAIN 语句，我们可以查看查询是使用文件排序还是索引。