计划枚举

主要讨论的是逻辑计划到物理计划的转化。对于单表而言，需要考虑如何进行数据结构、索引的选择；对于多表而言，如何决定它们的处理先后顺序也是需要考虑的。

数据库需要枚举出来各种计划，然后通过成本预测和动态规划，从而选择最优的计划。

1.单表查询

考虑的第一点是如何对表进行访问。常见的方法有：

• 顺序扫描，永远是最后的选择。
• 二分查找，用于有序数据。
• 索引扫描，又涉及到如何选择索引。对于OLTP场景而言，可以通过简单的启发式搜索。

其次，对于多个条件，如何根据其选择性进行条件排序。

2.多表查询

多表查询结合单表查询需要考虑的问题，枚举的顺序常为：

• 枚举顺序：表之间的处理顺序。此时，可以对明显不应该的选择进行剪枝，如应该选择规模更小的表作为Outer Table。

• 枚举算法：在处理表的时候使用什么算法。

• 枚举访问方式

3.动态规划

由于需要枚举的问题规模较大，因此需要使用动态规划来见优化枚举的时间开销。

由于Join的顺序对结果不影响，因此可以选择任意路径得到结果。

如下图，每个节点代表了一种状态，其转移路径的权值为预估成本。

对于更大规模的问题，Postgres采用的方式是利用遗传算法进行方案枚举。