本篇文章关键字：优先队列排序算法、小顶堆、大顶堆
背景
接着 的案例，我们继续磕。
回顾下实验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": " " } } ] }} 关于这里的 filesort_priority_queue_optimization 算法可以参考
在该案例中根据该结果可知，临时表使用的堆上的 memory 表。根据 实验中 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字节。
源码分析
看下里面的Sort_param
/** There are two record formats for sorting: |...| | / sort_length / ref_l / or with "addon fields" | ...| | ...| / sort_length / addon_length / The packed format for "addon fields" | ...| | | ...| / sort_length / addon_length / Fields are fixed-size, specially encoded with Field::make_sort_key() so we can do byte-by-byte compare. 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. One bit for each nullable field, indicating whether the field is null or not. May have size zero if no fields are nullable. 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 sortlengthBreakpoint 7 at 0xf20d84: file /root/newdb/mysql-server/sql/filesort.cc, line 2332.
这样就推断出了 rowid 排序时，优先队列排序里面的 row_size 为什么是 24 了。
小结
当是 rowid 排序时，参考上面的注释可知 row_size （也就是 param->rec_length）格式如下
|...| |/ 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字节啦。验证完毕。