菜单开关

周梦康 发表于 2019-02-13 251 次浏览 标签 : Mysql

免费领取阿里云优惠券 我的直播 - 《PHP 进阶之路》

本篇文章关键字:优先队列排序算法、小顶堆、大顶堆

背景

接着 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 调试打印可知道,临时表存的两个字段是aidnum

前面我们已经分析过对于 InnoDB 表来说 additional_fields 对比 rowid 来说,减少了回表,也就减少了磁盘访问,会被优先选择。但是要注意这是对于 InnoDB 来说的。而实验3是内存表,使用的是 memory 引擎。回表过程只是根据数据行的位置,直接访问内存得到数据,不会有磁盘访问(可以简单的理解为一个内存中的数组下标去找对应的元素),排序的列越少越好占的内存就越小,所以就选择了 rowid 排序。

还有一个原因就是我们这里使用了limit 10这样堆的成员个数比较小,所以占用的内存不会太大。不要忘了这里选择优先队列排序算法依然受到sort_buffer_size的限制。

优先队列排序执行步骤分析:

  1. 在临时表(未排序)中取出前 10 行,把其中的num(来源于sum(pv))和rowid作为10个元素构成一个小顶堆,也就是最小的 num 在堆顶。
  2. 取下一行,根据 num 的值和堆顶值作比较,如果该字大于堆顶的值,则替换掉。然后将新的堆做堆排序。
  3. 重复步骤2直到第 649091 行比较完成。
  4. 然后对最后的10行做一次回表查询其 aid,num。

rows_estimate

根据以上分析,先读取了 649091 行,然后回表又读取了 10 行,所以总共是 649101 行。
实验3的结果与之相吻合,但是其他的都是 1057 行,是怎么算出来的呢?

row_size

存储在临时表里时,都是 aidnum 字段,占用宽度是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 调试 Mysql 实战(三)优先队列排序算法中的行记录长度统计是怎么来的(上)

(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字节啦。验证完毕。

嗨,老铁,欢迎来到我的博客!

如果觉得我的内容还不错的话,可以关注下我在 segmentfault.com 上的直播。我主要从事 PHP 和 Java 方面的开发,《深入 PHP 内核》作者之一。

[视频直播] PHP 进阶之路 - 亿级 pv 网站架构的技术细节与套路 直播中我将毫无保留的分享我这六年的全部工作经验和踩坑的故事,以及会穿插着一些面试中的 考点难点加分点

评论列表