【GreatSQL 优化器 -07】mm tree
【GreatSQL 优化器-07】mm tree
一、mm tree 介绍
GreatSQL 的优化器主要用 mm tree 也就是 min-max tree 来确定条件的范围，然后根据不同索引的范围值来计算 cost，选取 cost 最小的索引来执行 SQL。
下面用一个简单的例子来说明 mm tree 是什么。
二、get_mm_tree 代码说明
mm tree 实现主要在 get_mm_tree 函数执行的。具体代码流程如下：
最后生成 SEL_TREE，根据索引数量包含对应的 SEL_ROOT，SEL_ROOT 包含最小单元 SEL_ARG，一个 SEL_ARG 就是一段范围，用 key_range_flags 来计算范围，见表二 SEL_ARG 一组对象合成一个 SEL_ROOT 的图结构，内部通过 SEL_ARG::next/prev 来关联同一个索引列条件"OR"，通过 next_key_part 来关联不同索引列条件的"AND" tree_or 操作涉及的比较函数见表三，表四。
原则就是把 2 个不同的范围进行比较按照结果进行合并操作，涉及的范围拼接因为太多不展开细讲，具体看函数 tree.cc tree_or 会对两个不同条件组的共同列做 key_or 处理，生成这个交集列的范围二叉树。即对不同 or 条件出现次数最多的列做查找范围操作。注意，如果最后某个索引的范围是全覆盖的话是不会生成这个索引的 mm tree 的。
SEL_ARG 的红黑二叉树结构：
相关注释怎么看，解释一下：
表一，Item_func 对应的 TREE 操作
表二，SEL_ARG 的 key_range_flags
表三，key_or 的 cmp_max_to_min 的比较结果
表四，key_or 的 cmp_min_to_max 的比较结果
表五，SEL_TREE::type
注：多个 SEL_ROOT 组成一个 SEL_TREE
表六，SEL_ROOT::type
注：多个 SEL_ARG 组成一个 SEL_ROOT，一个 SEL_ARG 就是一个范围
三、实际例子说明
接下来看几个例子来说明上面的代码：
通过setup_range_optimizer_param()获得的param->key_parts数组，这里每个 key 都包含了主键信息。其中 key 对应param->key[keys]
根据条件生成的 SEL_ARG
SEL_ARG 经过 key_and 和 key_or 操作后，红黑二叉树结果如下，注意这个二叉树每个索引都有一个，最后通过 cost 值选择 cost 最小的 index。
现在换一个条件里面 c1 和 c2 均等的 sql，看看最后的结果，看到每个索引用的都是自己相关列的范围进行 cost 计算。
看看每个 OR 条件都只有一个单独列的情况，因为都无法生成对应索引的 tree，所以最后的结果没有走范围估计。
四、总结
从上面优化器最早的步骤我们知道了在rows_estimation的时候可以通过 mm tree 来确定是否可以用范围扫描来查询，并且接着分别用不同索引的范围来计算 cost，最后选出 cost 最小的索引和范围。如果单个索引计算出来发现范围全覆盖，就不会生成对应的 mm tree 了，也就不会对这个索引用范围扫描了。其中涉及 mm tree 的 cost 计算下期介绍。
版权声明: 本文为 InfoQ 作者【GreatSQL】的原创文章。
原文链接:【http://xie.infoq.cn/article/c4fa27f7b746f297359ead860】。文章转载请联系作者。
GreatSQL社区 2023-01-31 加入
GreatSQL是由万里数据库维护的MySQL分支，专注于提升MGR可靠性及性能，支持InnoDB并行查询特性，是适用于金融级应用的MySQL分支版本。 社区：https://greatsql.cn/ Gitee: https://gitee.com/GreatSQL/GreatSQL
评论