数据库内核月报

数据库内核月报 - 2021 / 06

MySQL · 源码分析 · Order By优化逻辑代码分析

Author: xavier.zxm

概述

近期在处理线上问题的时候遇到了一些关于Filesort的问题,在分析问题的过程中对代码进行了一些梳理,在此做一些总结,希望对同学们在学习mysql的代码过程中能有所帮助。以下分析基于Mysql-8.0.24代码。

优化阶段

涉及的函数:

JOIN::optimize_distinct_group_order
JOIN::test_skip_sort
test_if_order_by_key
test_if_skip_sort_order

相关变量:

JOIN::order
JOIN::simple_order
JOIN::skip_sort_order

同时Order会受index,group by, distinct,window的影响,例如

  1. order是group list的前缀,且window和rollup不影响顺序时,order会被优化掉, 在group list上加上顺序要求
  2. distinct查询,没有group list、window、sum函数,order都在投影中,会尝试是否可以使用索引来完成去重排序
  3. group by操作可能会产生filesort,用来进行流式group by
  4. distinct操作可能会通过filesort来完成
  5. window function如果有partition/order by要求,会在window function的输入table上进行filesort

相关环境变量: |变量名|默认值|描述| |:-|:-|:-| |max_length_for_sort_data|4096 [4, 8MB]| sorted records的最大字节数,用来决定filesort时是否是padon,8.0.18 之后已经不再使用| |max_sort_length|1024 [4, 8MB]| 大对象(TEXT), 如果是pad空格的字符集,参与排序的长度| |sort_buffer_size|256KB [32KB, ULONG_MAX] | sort buffer的大小,每个排序线程一个|

JOIN::test_skip_sort

检查是否可以通过索引来避免filesort的总入口,在JOIN::optimizer中调用

  1. group list
  2. 不是BIG_RESULT或JSON Aggregation, 是GROUP MIN MAX优化 1. simple group并且不是distinct转化的group by call -> test_if_skip_sort_order
  3. order list
  4. simple order或skip sort order 且不是window sort call -> test_if_skip_sort_order

test_if_skip_sort_order

检查是否可以通过使用索引来避免filesort 条件:

  1. single row result, EQ_REF/CONST/SYSTEM, 可以skip
  2. 如果order by的列是全文索引函数, 要求order by只能有这一个列, 且必须是降序,这时候是否能使用全文索引替代filesort取决于下面两个条件:
    1. 表的访问方式是全文索引, 且使用的函数和order by的函数必须相同, 可以skip
    2. 否则,没有单表条件,select limit是用户指定的且小于全文索引函数名中的行数, 可以skip
  3. order by必须是表列并且属于同一个索引,如果不是REF使用的索引,则计算可能的代价是否比REF更低,并尝试替换索引。 如果时REF使用的索引,检测是否可以满足Order的方向要求,如果可以满足,则省略filesort操作,由索引扫描保证顺序。

test_if_order_by_key

检查是否可以通过索引来进行排序

  1. order list都是表列
  2. partition表必须是索引的全部列
  3. 可以满足索引的顺序要求

执行阶段

涉及的函数:

filesort()

filesort

filesort执行逻辑总入口, 主要流程如下:

  1. 初始化排序参数, 确定是否可以使用addon,避免回表,涉及的函数包括:
    Sort_param::decide_addon_fields
    Sort_param::try_to_pack_addons
    Filesort::get_addon_fields
    
  2. 确定是否可以使用优先级队列排序避免排序过程中落盘(写tempfile), 函数为:
    check_if_pq_applicable
    
  3. 初始化优先级队列(初始化tempfile)
  4. 读取数据并排序(tempfile需要多轮merge),排序完成后如果是rowid,需要回表
  5. 去重和limit会在排序过程中应用,用来减少中间排序的数据量

filesort主要代码:

bool filesort() {

  param->init_for_filesort();     // init filesort parameter


  if (check_if_pq_applicable()) {  // check using priority queue
    pq.init()            // init priority queue
  }
  
  read_all_rows()        // read all rows from sorted table
  
  if (num_trunk == 0) {
    save_index()         // save sorted result to buffer, deal rowid
  } else {
    merge_many_buffer()  // merge trunks
    merge_index()        // merge last 15 trunks
  }
}

判断Addon的逻辑
根据排序列和表需要返回的列,判断排序方式是addon还是rowid,并计算sort record length,filesort认为回表代价总是更大的,会尽量采用addon的方式, 8.0.24不再额外单独限制max_sort_length, 但是新引入了一个限制,如果pack_field导致额外需要存储的内容超过10字节(描述变长列的变量0), 则不采用addon方式。 其他不能addon的条件有:

  1. 全文索引过滤后的filesort,只能使用rowid
  2. force_sort_position,只能使用rowid
  3. 包含blob列,且pack长度大于70000,只能使用rowid

check_if_pq_applicable, 判断是否可以使用优先级队列排序

  1. 需要有limit
  2. 不能是去重
  3. limit的值需要小于UINT_MAX - 2(priority queue的最大容量)
  4. 最大行长度需要小于0xFFFFFFFF(不能是无边界的行)
  5. 排序的数据需要在sort buffer中可以放下
  6. limit rows小于排序总数据量的1/3 (认为优先级队列比filesort只有1个trunk的代价更大)
  7. 排序的总数据量放不下时,limit的数据量需要能在sort buffer中放下

优先级队列排序过程

  1. 初始化优先级队列,大小为排序行数 + 2
  2. 读取表的全部数据,并放入优先级队列(内存中)

filesort排序过程

  1. 初始化tempfile
  2. 读取表的全部数据,每次读取一行,构建sortkey后copy进入trunk, trunk满后对trunk的数据进行快排,如果数据不足一个trunk,则返回, 保留数据在内存中,否责trunk数据写入tempfile,知道全部数据读取完
  3. 构建另一个trempfile, 两个tempfile来回倒, 做trunk合并,直到trunk数量少15个, 合并中使用的是merge sort,每次合并7个trunk
  4. 对最后不足15个trunk通过priority queue进行合并
  5. 排序后的数据保存在tempfile中

返回结果

  1. 如果是addon,排序后直接返回结果
  2. 如果是rowid,排序后会通过rowid读取记录后返回

去重操作 merge trunk的时候,保留上一个sort key,如果sort key不发生变化,则是重复数据跳过,否则是新的数据。更新last_sort_key

limit操作 limit作用于filesort的方式

  1. prioriyty
  2. 最多只放limit数量的rows
  3. 通过rowid读取record时,最多只读区limit行的数据
  4. filesort
  5. trunk在写入文件时,如果limit > trunk中的rows, 只写limit数量的行
  6. 合并trunk时,只需要从待合并的trunk中读取limit的行数
  7. 通过rowid读取record时,最多只读区limit行的数据

Order By的并行

Parallel Query提供了Order By的并行执行方式,可能的执行方式包括:

  1. Serail, 在leader上串行执行
  2. Two Phase Gather, worker上先并行排序, 然后在Leader上进行Merge排序 具体执行方式取决于计划的代价。