优化器是什么？优化器具有哪些优化方法？

优化器是数据库的核心，决定了每条语句如何执行。如果将数据库比作一支军队，那么优化器就是这支军队的主将、军师，需要运筹帷幄，决胜于千里之外。俗话说一将无能累死三军，同样的一条语句，选择不同的查询计划，最终的运行时间可能会相差很大。对优化器的研究一直是学术界比较活跃的领域，优化是永无止境，可以说在这块投入多大的精力都不为过。 从优化方法上，大致可以分为三类：

? Rule based optimizer：通过启发式规则对 plan 进行优化

? Cost based optimizer：通过计算查询代价对 plan 进行优化

? History based optimizer：通过历史查询信息对 plan 进行优化

基于规则的优化器比较容易实现，只要选取一些常用的规则，就可以对大多数常用的查询有较好的效果。但是其缺陷也比较明显：无法根据数据的真实情况，选择最优的方案。比如对于查询语句 “select * from t where c1 = 10 and c2 > 100” 在选择索引时，如果只根据规则，那么一定是选择 c1 上面的索引进行查询，但是如果 t

中 c1 所有的值都是 10，那么这个查询计划就很差。这个时候如果有表中数据分布的信息，对选择好的查询计划很有帮助。

基于代价的优化器复杂一些，其核心问题有两个，一个是如何获取数据的真实分布信息，另一个是如何根据这些信息，估算出某一个查询计划所需的代价。

基于历史信息的查询优化器用的比较少，一般 OLTP 数据库中不会涉及。

TiDB 的优化器相关代码在 plan 包中，这个包的主要工作是将 AST 转换为查询计划树，树中的节点是各种逻辑算子或者是物理算子，对查询计划化的各种优化都是通过调用树根节点的各种方法，递归地对所有节点进行优化，并且会不断的对树中的节点进行转换和裁剪。 最重要的几个接口在 plan.go 中，包括：

? Plan： 所有查询计划的接口

? LogicalPlan：逻辑查询计划，所有的逻辑算子都需要实现这个接口

? PhysicalPlan：物理查询计划，所有的物理算子都需要实现这个接口

逻辑优化的入口是 planbuilder.build()，输入是 AST，输出是逻辑查询计划树。然后在这棵树上进行逻辑查询优化：

? 调用 LogicalPlan 的 PredicatePushDown 接口，将谓词尽可能下推

? 调用 LogicalPlan 的 PruneColumns 接口，将不需要的列裁减掉

? 调用 aggPushDownSolver.aggPushDown，将聚合算子下推到 Join 之前

拿到逻辑优化后的查询计划树之后，会进行物理优化，代码的入口是对逻辑查询计划树的根节点调用 convert2PhysicalPlan(&requiredProperty{})，其中 requiredProperty 是对下层返回结果顺序、行数的要求。 逻辑查询计划树从根节点开始，不断的递归调用，将每个节点从逻辑算子转成物理算子，并且根据每个节点的查询代价找到一条比较好的查询路径。