规划器/优化器

生成可能的规划

规划器/优化器以查询里出现的关系上定义的索引的类型为基础，判断应该生成哪些规划。对一个关系总是可以进行一次顺序查找，所以总是会创建只使用顺序查找的规划。假设一个关系上定义着一个索引（例如 B-tree 索引），并且一条查询包含约束 relation.attribute OPR constant。如果 relation.attribute 碰巧匹配 B-tree 索引的关键字并且 OPR 又不是 '<>'，则将会创建另一个使用 B-tree 索引扫描该关系的规划。如果还有别的索引，而且查询里面的约束又和那个索引的关键字匹配，则还会生成更多的规划。

在找完扫描一个关系的所有可能的规划后，接着创建联接各个关系的规划。规划器/优化器认为只有在每两个关系之间存在联接，对应地在 where 条件里存在一条 join 子句（也就是说，存在象 where rel1.attr1=rel2.attr2 这样的约束）。规划器/优化器为它们认为可能的所有的联接关系对生成一个规划。有三种可能的联接策略：

嵌套的反复联接（nested iteration join）：对左边的关系里面找到的每条记录都对右边关系进行一次扫描。这个策略容易实现，但是可能会很耗费时间。

融合排序联接（merge sort join）：在联接开始之前，每个关系都对联接字段进行排序。然后两个关系融合到一起，认为两个关系都对联接字段进行了排序。这种联合更有吸引力，因为每个关系都只用扫描一次。

哈希联接（hash join）：右边的关系首先对它的联接字段进行哈希运算。然后扫描左边的关系，并将找到的每条记录的合适的值作为哈希键字用以定位右边关系里的记录。

规划的数据结构

我们在这里对规划里出现的节点做一些简单描述。图 \ref{plan} 显示了为例子 \ref{simple_select} 里的查询生成的规划。

规划的顶端节点是一个 MergeJoin 节点，它有两个下级节点，一个附加在域 lefttree 上，而另一个附加在域 righttree 上。每个子节点代表一个联接的关系。如上面所述，一个融合联接要求每个关系先被排序。这就是为什么我们在每个子规划里有一个 Sort 节点的原因。查询里附加的条件（s.sno > 2）被尽可能地向下推，并且附加在对应的子规划的叶节点 SeqScan 的 qpqual 域上。

附加在节点 MergeJoin 的域 mergeclauses 的列表包含关于联接属性的信息。 mergeclauses 列表里（还有 targetlist 里）出现的 VAR 节点的数据域 varno 的值 65000 和 65001 意味着不考虑当前节点的记录，而是使用下一"更深"节点（也就是说，子规划的顶端节点）的记录。

请注意图 \ref{plan} 里的每个 Sort 和 SeqScan 节点都有一个 targetlist，但因为空间不够，只有 MergeJoin 节点的画出来了。

规划器/优化器执行的另一个任务是填补 Expr 和 Oper 节点里的操作符id。如上所述，Postgres 支持广范围的不同的数据类型，甚至可以使用用户定义类型。为了能够维护这些数目巨大的函数和操作符，有必要把它们存放在系统表里。每个函数和操作符有一个唯一的操作符 id。根据在资格条件等地方使用的字段的类型，必须选用合适的操作符 id。