MySQL优化器汇总
qs:
- mysql 的某些操作会内部进行一些特殊的处理，不知道是基于什么原因实现的，但是不是太符合规范， 例如
- 表达式运算中，会隐式转换，且转换之后不报错，转换规则也不是很符合常理，例如字符转数值，字符串转日期等，不清楚规则的情况下，隐式转换会导致出现预期之外的结果，或者index失效等
- 一些函数行为不符合预期，例如 || 和 concat，round 函数等
- MySQL有没有某个函数每次输出不一样，且每次调用之后会导致某个状态发生改变
- 使用函数或者sp，实现一个类似的函数
- DETERMINISTIC 属性
- MySQL 相同的函数名，接受不同的参数类型，执行不同的逻辑
- abs, greatest, least 等函数支持不同参数或者不同类型，需要继承 Item_func_numhybrid
MySQL 的表示使用继承实现，但是在 SQL 中，表达式的运算是很频繁的，使用继承实现会不会导致虚指针而导致性能问题 pg 为了加速表达式运算，已经重构过一次表达式，MySQL 相比于 pg，TPCH 的 q1 在所有的测试中，是性能比较弱的
- 减少函数调用，使用 goto 替换 switch,减少分支预测的开销，减少运行时的操作，更多的操作在 init 的时候实现 TODO: perf 采集下 tpch q1 MySQL 和 pg 的差距
- 表达式的运算逻辑，以 tpch q1 为例
tpch q20
dispatch_command
dispatch_sql_command
reset_for_next_command
lex_start
parse_sql { // 解析SQL语句，生成 PT_xx AST 树，之后生成 Sql_cmd
add_table_to_list
add_joined_table
}
mysql_rewrite_query // 有配置重写就尝试重写
mysql_execute_command { // 主要的执行逻辑，包括 opt 和 execute
Sql_cmd_dml::execute {
Sql_cmd_dml::prepare {
check_table_access // 检查表权限
open_tables_for_query // 打开表
Query_block::prepare { // opt 前的准备工作，主要类似 pg 的analyze，解析类型，解析表字段，除此之外还有部分优化操作
setup_tables
setup_fields
setup_conds
setup_order
setup_connect_by
resolve_limits
resolve_subquery
}
}
lock_tables {
mysql_lock_tables
decide_logging_format
}
Query_expression::optimize {
Query_block::optimize {
JOIN::optimize{
.. preprocess
optimize_cond // 表达式优化， eg. 常量折叠，条件合并，等值传递，死条件删除等
JOIN::make_join_plan {
init_planner_arrays
update_ref_and_keys
pull_out_semijoin_tables
estimate_rowcount // 计算依据是什么，会根据条件计算吗
}
}
}
}
}
}
Here is an overview of the logic of this function:
- Initialize JOIN data structures and setup basic dependencies between tables.
- Update dependencies based on join information. 对于存在outer join或recursive的tables进行关系传递propagate_dependencies()(用传递闭包算法)，构建出完整的依赖关系。(recursive这里具体指代未确定，nested？WITH RECURSIVE语法？)
- Make key descriptions (update_ref_and_keys()). 这一步骤较为烦杂，本意是想从conditions中找出join连接的condition，并识别出join condition相关的key(key指的就是索引)，为后续决定join_type到底是ref/ref_or_null/index等做好准备。但MySQL在这一步又加了不少特殊判断，比如对key is null的特殊处理等。
- Pull out semi-join tables based on table dependencies.
- Extract tables with zero or one row as const tables. 从这步开始的四个步骤都是const table优化，核心就是先把const table算出来，将变量替换成常量。这里是依靠获取采样判断const table。
- Read contents of const tables, substitute columns from these tables with
actual data. Also keep track of empty tables vs. one-row tables.
- After const table extraction based on row count, more tables may
have become functionally dependent. Extract these as const tables.
- Add new sargable predicates based on retrieved const values.
- Calculate number of rows to be retrieved from each table. 获取采样结果的步骤。
- Calculate cost of potential semi-join materializations.
- Calculate best possible join order based on available statistics. 即下文的Optimize_table_order::choose_table_order
- Fill in remaining information for the generated join order.
qs
-
表达式
- 类型怎么绑定的
- 结构怎么组织的
- 常用的优化规则有那些，什么阶段生效
- 表达式和子查询的联系及处理方法
- 在执行阶段怎么evaluate的
- 对比其他数据库的实现，当前实现有什么问题，怎么优化 ** 实现一个简单表达式
-
子查询
- yacc怎么生成子查询
- 子查询类型
- 子查询怎么消除，具体的消除规则
- 无法消除的子查询怎么处理，在优化阶段以及运行阶段
- 子查询的代价计算 ** 对比其他数据库，存在什么问题，怎么优化
-
join
- join order 怎么确定的
- join type 有哪些，怎么确定的
- 怎么从下层 path 构造 join
- cost 怎么影响 join 的选择
- nest loop join 的优化
- 运行时怎么执行 join ** 实现merge join有什么难点
-
scan
- 有哪些类型，包括 index 和 其他scan
- 索引的选择和使用
- 索引的维护和更新
- 条件怎么处理的
- 代价怎么计算的
-
聚合操作是怎么优化的
-
sort 是怎么处理的
-
基于规则的优化和基于代价的优化，分别做了什么
-
参数化路径，join 中 a=b 这种，估算左右path的时候，怎么计算
-
对于一个组件，需要评估其使用情况，是否有必要使用，或者需要达到什么效果
- 例如对于 explain，table 格式还需要存在吗
-
Query_block::prepare 应该只关注于语言分析，不应该参杂太多优化工作
-
parse:
- 相比于 pg，差的不是一点半点，pg 的 parse 低耦合，已经可以作为一个单独的模块，被广泛使用，大多数新兴的基于使用c或者c++的数据库，不想写 parse 的，大多数可以直接使用 pgparse
- lex 词不达意，一般是指词法分析，这里更类似parse ctx
- 使用 show PARSE_TREE 显示语法树
- 相比于 pg，差的不是一点半点，pg 的 parse 低耦合，已经可以作为一个单独的模块，被广泛使用，大多数新兴的基于使用c或者c++的数据库，不想写 parse 的，大多数可以直接使用 pgparse
- 通过 contextualize，遍历 tree，构造以 query_block 为单位的语法树，同时在遍历过程中，检测某些关键信息，设置一些 flag
- 这里比其他数据库多了一层 contextualize，contextualize 还只是简单的遍历然后进行一个转换的过程，还没有使用具体的元数据 ? 为什么要 contextualize？ parse 里面不好构建 query_expression 和 query_block 树，所以需要 contextualize 层来补全语法树，然后再进行优化器的处理。
- resolve：设置字段类型，检测表达式以及语句的合法性
-
类似 pg 的analyze，这里依赖与前面处理之后的 query_block 语法树，进行类型检查，表达式检查等
-
这里还包含语句的改写功能，例如子查询消除，outer join 转换等 ? 为什么不把 contextualize 和 resolve 合在一起处理，而且为什么把一些优化操作放在这里，统一由 optimizer 管理不行吗
-
optimizer 处理的不是一个树形结构，而是 Query_expression 和 Query_block 组合的逻辑树
- 怎么理解 Query_expression 和 Query_block 组合的逻辑树？
- lex->unit 指向的是当前整个完整的 SQL 语句的 Query_expression
- Query_block
- master 指向的是包含当前的 Query_block 的 Query_expression
- slave 指向的是当前 Query_block 的子查询的 Query_expression，可能是 union，也可能是子查询
- next 指向的是同属于同一个 Query_expression 的 block 链表
- link_next，link_prev 是维护所有当前语句中的 Query_block 的双向链表
- Query_expression
- m_query_term 当前 expression 的主要内容，可能是一个 union，或者就是一个 Query_block
- 这个结构体只是为了维护同属于一个查询的 Query_block 的关系，暂时不了解其他作用，完全可以由 block 自己维护
- slave 指向当前所属的第一个 Query_block
- master 指向包含当前 Query_expression 的 Query_block
- 怎么理解 Query_expression 和 Query_block 组合的逻辑树？