共计 3617 个字符，预计需要花费 10 分钟才能阅读完成。
本篇文章关键字：优先队列排序算法、小顶堆、大顶堆
背景
接着 https://mengkang.net/1328.html 的案例，我们继续磕。
回顾下实验 3 中的例子
select `aid`,sum(`pv`) as num from article_rank force index(idx_aid_day_pv) where `day`>’20190115′ group by aid order by num desc limit 10;
optimizer_trace.join_execution.steps 的结果如下
{
“join_execution”: {
“select#”: 1,
“steps”: [
{
“creating_tmp_table”: {
“tmp_table_info”: {
“table”: “intermediate_tmp_table”,
“row_length”: 20,
“key_length”: 0,
“unique_constraint”: false,
“location”: “memory (heap)”,
“row_limit_estimate”: 838860
}
}
},
{
“filesort_information”: [
{
“direction”: “desc”,
“table”: “intermediate_tmp_table”,
“field”: “num”
}
],
“filesort_priority_queue_optimization”: {
“limit”: 10,
“rows_estimate”: 649101,
“row_size”: 24,
“memory_available”: 262144,
“chosen”: true
},
“filesort_execution”: [
],
“filesort_summary”: {
“rows”: 11,
“examined_rows”: 649091,
“number_of_tmp_files”: 0,
“sort_buffer_size”: 352,
“sort_mode”: “<sort_key, rowid>”
}
}
]
}
}
关于这里的 filesort_priority_queue_optimization 算法可以参考 https://blog.csdn.net/qian520ao/article/details/80531150
在该案例中根据该结果可知，临时表使用的堆上的 memory 表。根据 https://mengkang.net/1336.html 实验中 gdb 调试打印可知道，临时表存的两个字段是 aid 和 num。
前面我们已经分析过对于 InnoDB 表来说 additional_fields 对比 rowid 来说，减少了回表，也就减少了磁盘访问，会被优先选择。但是要注意这是对于 InnoDB 来说的。而实验 3 是内存表，使用的是 memory 引擎。回表过程只是根据数据行的位置，直接访问内存得到数据，不会有磁盘访问（可以简单的理解为一个内存中的数组下标去找对应的元素），排序的列越少越好占的内存就越小，所以就选择了 rowid 排序。
还有一个原因就是我们这里使用了 limit 10 这样堆的成员个数比较小，所以占用的内存不会太大。不要忘了这里选择优先队列排序算法依然受到 sort_buffer_size 的限制。
优先队列排序执行步骤分析：
在临时表（未排序）中取出前 10 行，把其中的 num（来源于 sum(pv)）和 rowid 作为 10 个元素构成一个小顶堆，也就是最小的 num 在堆顶。
取下一行，根据 num 的值和堆顶值作比较，如果该字大于堆顶的值，则替换掉。然后将新的堆做堆排序。
重复步骤 2 直到第 649091 行比较完成。
然后对最后的 10 行做一次回表查询其 aid,num。
rows_estimate
根据以上分析，先读取了 649091 行，然后回表又读取了 10 行，所以总共是 649101 行。实验 3 的结果与之相吻合，但是其他的都是 1057 行，是怎么算出来的呢？
row_size
存储在临时表里时，都是 aid 和 num 字段，占用宽度是 4 +15 是 19 字节。为什么是实验 3 是 24 字节，其他是 additional_fields 排序都是 36 字节。
源码分析
看下里面的 Sort_param
/**
There are two record formats for sorting:
|<key a><key b>…|<rowid>|
/ sort_length / ref_l /
or with “addon fields”
|<key a><key b>…|<null bits>|<field a><field b>…|
/ sort_length / addon_length /
The packed format for “addon fields”
|<key a><key b>…|<length>|<null bits>|<field a><field b>…|
/ sort_length / addon_length /
<key> Fields are fixed-size, specially encoded with
Field::make_sort_key() so we can do byte-by-byte compare.
<length> Contains the *actual* packed length (after packing) of
everything after the sort keys.
The size of the length field is 2 bytes,
which should cover most use cases: addon data <= 65535 bytes.
This is the same as max record size in MySQL.
<null bits> One bit for each nullable field, indicating whether the field
is null or not. May have size zero if no fields are nullable.
<field xx> Are stored with field->pack(), and retrieved with field->unpack().
Addon fields within a record are stored consecutively, with no
“holes” or padding. They will have zero size for NULL values.
*/
class Sort_param {
public:
uint rec_length; // Length of sorted records.
uint sort_length; // Length of sorted columns.
uint ref_length; // Length of record ref.
uint addon_length; // Length of added packed fields.
uint res_length; // Length of records in final sorted file/buffer.
uint max_keys_per_buffer; // Max keys / buffer.
ha_rows max_rows; // Select limit, or HA_POS_ERROR if unlimited.
ha_rows examined_rows; // Number of examined rows.
TABLE *sort_form; // For quicker make_sortkey.
bool use_hash; // Whether to use hash to distinguish cut JSON
//…
};
trace 日志是在这里记录的
(gdb) b sortlength
Breakpoint 7 at 0xf20d84: file /root/newdb/mysql-server/sql/filesort.cc, line 2332.
这样就推断出了 rowid 排序时，优先队列排序里面的 row_size 为什么是 24 了。
小结
当是 rowid 排序时，参考上面的注释可知 row_size（也就是 param->rec_length）格式如下
|<key a><key b>…|<rowid>|
/ sort_length / ref_l /
sort_length 就是 num 的长度 + 1 字节（标识是可以为空）。所以源码里注释有问题，没有标识出每个排序字段可以为空的长度 rowid 的长度就是 table->file->ref_length 也就是 handler->ref_length。
class handler :public Sql_alloc
{
public:
uchar *ref; /* Pointer to current row */
public:
/** Length of ref (1-8 or the clustered key length) */
uint ref_length;
}
可以看到 ref_length 表示该行的指针长度。因为是 64 位服务器，所以长度是 8 字节，因此最后就是 24 字节啦。验证完毕。