GDB 除錯 Mysql 實戰（三）優先佇列排序演算法中的行記錄長度統計是怎麼來的（上）
本篇文章關鍵字：優先佇列排序演算法、小頂堆、大頂堆
背景
接著 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位元組啦。驗證完畢。