44.5.1. 生成可能的规划

规划器/优化器通过为扫描查询里出现的每个关系(表)生成规划， 可能的规划是由每个关系上有哪些可用的索引决定的。 对一个关系总是可以进行一次顺序查找，所以总是会创建只使用顺序查找的规划。 假设一个关系上定义着一个索引(例如 B-tree 索引)， 并且一条查询包含约束relation.attribute OPR constant。 如果relation.attribute碰巧匹配 B-tree 索引的关键字 并且OPR又是列出在索引的操作符类中的操作符中的一个， 那么将会创建另一个使用 B-tree 索引扫描该关系的规划。 如果还有别的索引，而且查询里面的约束又和那个索引的关键字匹配，则还会生成更多的规划。

如果查询要求链接两个或两个以上的关系，在扫描单一的关系时，所有可行的计划被找到后，链接关系的计划才会被考虑。有三种可能的连接策略:

• 嵌套循环连接(nested loop join)： 对左边的关系里面找到的每条行都对右边关系进行一次扫描。 这个策略容易实现，但是可能会很耗费时间。 但是，如果右边的关系可以用索引扫描，那么这个可能就是个好策略。 可以用来自左边关系的当前行的数值为键字进行对右边关系的索引扫描。

• 融合排序连接(merge join)： 在连接开始之前，每个关系都对连接字段进行排序。 然后对两个关系并发扫描，匹配的行就组合起来形成连接行。 这种联合更有吸引力，因为每个关系都只用扫描一次。 要求的排序步骤可以通过明确的排序步骤， 或者是使用连接键字上的索引按照恰当的顺序扫描关系。

• Hash 连接hash join： 首先扫描右边的关系，并用连接的字段作为散列键字加载进入一个 Hash 表， 然后扫描左边的关系，并将找到的每行用作散列键字来以定位表里匹配的行。

如果查询里的关系多于两个，最后的结果必须通过一个连接步骤树建立，每个步骤有两个输入。 规划器检查不同的连接顺序可能，找出开销最小的。

如果查询使用了比geqo_threshold少的关系，为了找到最好的接入序列，near-exhaustive查找被运行。 策划者优先考虑接入任意两个关系之间，那些在WHEREqualification里存在一个相应的加入条款（例如： 存在像where rel1.attr1=rel2.attr2这样的关系）。只有在没有别的选择的时候考虑加入对时没有join字句， 也就是，一个特别的关系对另外的关系没有可用的join子句。策划者会为每一个加入对想到所有可能的计划，选择计划的标准之一是（估计是）选择最便宜的。

当geqo_threshold被超过，启发式决定加入序列的考虑，就像在 Chapter 50里的描述。否则进程是一样的。

完成的查询树由对基础关系的顺序或者索引扫描组成， 并根据需要加上嵌套循环、融合、以及 Hash 连接节点，加上任何需要的辅助步骤， 比如排序节点或者聚集函数计算节点等。 大多数这些规划节点类型都有额外的做选择(selection) (抛弃那些不符合指定布尔条件的行)和投影(projection) (基于给出的字段数值计算一个派生出的字段集，也就是在需要时计算标量表达式)。 规划器的一个责任是从WHERE子句中 附加选择条件以及为规划树最合适的节点计算所需要的输出表达式。