数据库内核月报 － 2014 / 11

从MySQL 5.6.2/MariaDB 10.0.0版本开始，MySQL/MariaDB针对”ORDER BY …LIMIT n”语句实现了一种新的优化策略。当n足够小的时候，优化器会采用一个容积为n的优先队列来进行排序，而不是排序所有数据然后取出前n条。 这个新算法可以这么描述：（假设是ASC排序）

1. 建立一个只有n个元素的优先队列（堆），根节点为堆中最大元素
2. 根据其他条件，依次从表中取出一行数据
3. 如果当前行的排序关键字小于堆头，则把当前元素替换堆头，重新Shift保持堆的特性
4. 再取一条数据重复2步骤，如果没有下一条数据则执行5
5. 依次取出堆中的元素（从大到小排序），逆序输出（从小到大排序），即可得ASC的排序结果

这样的算法，时间复杂度为mlog(n)，m为索引过滤后的行数，n为LIMIT的行数。而原始的全排序算法，时间复杂度为mlog(m)。只要n远小于m，这个算法就会很有效。

不过在MySQL 5.6中，除了optimizer_trace，没有好的方法来看到这个新的执行计划到底起了多少作用。MariaDB 10.013开始，提供一个系统状态，可以查看新执行计划调用的次数：

Sort_priority_queue_sorts
描述: 通过优先队列实现排序的次数。(总排序次数=Sort_range+Sort_scan)
范围: Global, Session
数据类型: numeric
引入版本: MariaDB 10.0.13

此外，MariaDB还将此信息打入了Slow Log中。只要指定 log_slow_verbosity=query_plan，就可以在Slow Log中看到这样的记录：

# Time: 140714 18:30:39
# User@Host: root[root] @ localhost []
# Thread_id: 3  Schema: test  QC_hit: No
# Query_time: 0.053857  Lock_time: 0.000188  Rows_sent: 11  Rows_examined: 100011
# Full_scan: Yes  Full_join: No  Tmp_table: No  Tmp_table_on_disk: No
# Filesort: Yes  Filesort_on_disk: No  Merge_passes: 0  Priority_queue: Yes
SET timestamp=1405348239;SET timestamp=1405348239;
select * from t1 where col1 between 10 and 20 order by col2 limit 100;

“Priority_queue: Yes” 就表示这个Query利用了优先队列的执行计划(pt-query-digest 目前已经可以解析 Priority_queue 这个列)。