mysql如何在内部实现order by？

Question

Mysql如何在内部实现order by？按多列排序是否涉及对order by约束中指定的每一列多次扫描数据集一次？

Answer 1

下面是描述：

http://dev.mysql.com/doc/refman/5.0/en/order-by-optimization.html

除非您有行外的列(BLOB或TEXT)或SELECT列表太大，否则将使用此算法：

• 读取与WHERE子句匹配的行。
• 对于每一行，记录由排序关键字值和行位置以及查询所需列组成的值的元组。
• 按排序关键字value
• Retrieve按排序顺序对行进行排序，但直接从排序的元组中读取所需的列，而不是通过再次访问表来读取所需的列。

按多列排序不需要扫描数据集两次，因为排序所需的所有数据都可以在一次读取中获取。

请注意，如果您有一个最左边的部分符合ORDER BY条件的索引，MySQL可以完全避免顺序，只按顺序读取值。

Answer 2

MySQL很精明。它的排序算法取决于几个因素-

Available Indexes
Expected size of result
MySQL version

MySQL有两种方法可以生成排序/有序的数据流。

1.巧妙使用索引

首先，MySQL优化器分析查询，并确定它是否可以利用可用的排序索引。如果是，它自然会按索引顺序返回记录。( NDB引擎例外，它需要在从所有存储节点获取数据后执行合并排序)

由MySQL优化器负责，他们会聪明地判断索引访问方法是否比其他访问方法更便宜。

在这里看到非常有趣的事情

即使ORDER BY与索引并不完全匹配，也可以使用索引，只要ORDER BY中的其它列都是constants

• Sometimes，，如果优化器发现索引与遍历整个表相比开销很大，则它可能不会使用
• 。

2.文件排序算法

如果索引不能用于满足ORDER BY子句，MySQL将使用文件排序算法。这是一个非常有趣的算法。简而言之，它的工作原理如下

• 它扫描整个表并查找与WHERE条件

匹配的行

• 它维护一个缓冲区，并存储其中每一行的几个值(排序键值、行指针和查询所需的列)。此块的大小是系统变量sort_buffer_size.

• 当缓冲区已满时，它会根据排序关键字对其进行快速排序，并将其安全地存储到磁盘上的临时文件中，并记住指向该临时文件的指针

• 它将对数据块重复相同的步骤，直到没有更多的行离开

• 现在，它有几个

排序的块

• 最后，它对所有已排序的块应用合并排序，并将其放入一个结果文件

中

• 最后，它将从排序的结果文件

中获取行

如果预期的结果适合于一个区块，则数据永远不会命中磁盘，而是保留在RAM中。

详细信息的- https://www.pankajtanwar.in/blog/what-is-the-sorting-algorithm-behind-order-by-query-in-mysql