1.3.1　PGSQL的优化器

PGSQL最有名的应当是它的优化器，其除了很早就支持树形展示，还支持多线程扫描、多表连接优化、SQL语句重写的能力，这些都比MySQL有明显的优势。其中PGSQL具备的两个重要算法功不可没，即遗传算法和动态评估算法。相比于以贪婪算法为主体的MySQL，其有比较大的优势。

PGSQL的优化历程和SQL Server的优化历程相似，大致分为如下几个步骤。

PGSQL的分析器也是基于Bison分析的，这一点和MySQL类似，最终也会生成两个结构，即语法查询树和关系，其有点类似于MySQL的语法树和表列表（Table List）。不同的地方在于，PGSQL的重写做得比较多。

PGSQL优化器的第一步是进行SQL语句的逻辑优化，把之前的语法查询树匹配上代数关系，变成代数关系树。这里会做代数等价交换，比如a.c1=b.c1 and a.c1>100;，根据代数等价交换，可以知道b.c1 >100 肯定也是成立的。这些信息都会在这一步被展开。

然后优化器会进行物理优化，选择单表的访问方式和多表的连接方式。所谓选择，就是带上CPU和I/O的评估来计算哪种方式最好。对于单表的访问方式，评估比较简单，无非就是评估顺序扫描和索引扫描的成本，看哪一种方式成本最低。但多表的连接方式比较复杂，这里要说到PGSQL的两种多表连接评估方式。第一种是动态评估，简单地说，就是一种穷举的评估方式，把所有连接方式的结果分层计算一次。比如有4个表的有效连接，那么会分成4层来评估，看哪种组合最优。穷举的好处是一定可以求到最优解。但缺点也很明显，如果表的数量很多，排列组合就会非常多，这时候穷举的成本就会很高。

为了弥补这个不足，PGSQL提供了第二种评估方式，叫作遗传算法评估。这是一个非常特殊的算法，其原理对于非优化器开发人员来说，晦涩难懂。

按照PGSQL官方文档的说明，遗传算法的精髓在于，它使用了一个非穷举的算法，根据随机的初始表连接关系，依托多轮杂交、变异，可以获得一个置信度很高的局部最优解。也就是说，在循环验证过程中，可以提前退出。这在表连接数量非常多的情况下，显然有比较大的好处。这是一个典型带有AI训练影子的算法，因此需要一定的基数和迭代数，才能保证结果的稳定。当表的数量很多时，就非常适合使用这种算法，但该算法学术性过强，不容易理解。

如果和SQL Server进行对比，PGSQL的优化器依赖穷举的方法寻找多表连接的全局最优解，显然是稳重的，但不够智能。为了弥补这个缺陷，它又引入了一个非穷举的算法，在表连接数量非常多的时候，可以提高性能。

PGSQL还有一个非常好用的功能，就是auto_explain，它可以把一些不符合预期的慢SQL语句当时的执行计划和统计信息记录下来，这样就可以非常好地分析是否是执行计划的问题。类似于1.1.2节提到的变量嗅探导致的问题，在PGSQL中，如果遇到类似的因为特殊变量或者索引倾斜等导致的问题，就可以依赖auto_explain的记录来分析对应的慢SQL语句。

在PGSQL中有两种执行计划，即Custom Plan（定制执行计划）和Generic Plan（通用执行计划）。对应到SQL Server或者Oracle中的概念，就是Ad-Hoc（动态SQL）和绑定变量。

按照PGSQL的说法，如果执行了5次相同的Custom Plan，就会武断地（Arbitrary）改成Generic Plan。但是，如果字段的数值选择度非常高，或者有了索引，那么情况可能会有所变化，因为优化器会发现Custom Plan的Cost远低于Generic Plan的Cost，这时候又会跳回Custom Plan。

因此，在RDS中，DAS功能基于上述两种执行计划，提供了更加智能化的执行计划选择，通过采集执行计划和统计信息的快照，比较Custom Plan和Generic Plan的Cost差异来调优执行计划的选择。

说明

根据src/backend/utils/cache/plancache.c的代码定义，可以看到，如果执行了5次相同的Custom Plan，优化器会把它改成Generic Plan。