53.3. PostgreSQL 里的基因查询优化(GEQO)

GEQO模块是试图解决类似著名的旅行商问题(TSP)的查询优化问题的。 可能的查询规划被当作整数字符串进行编码。每个字符串代表查询里面一个关系到下一个关系的连接的顺序。例如，下面的连接树

   /\
  /\ 2
 /\ 3
4  1

是用整数字符串'4-1-3-2'编码的，这就是说，首先连接关系'4'和'1'，然后'3'，然后是'2'， 这里的 1, 2, 3, 4 都是PostgreSQL优化器里的关系标识(ID)。

在PostgreSQL里的GEQO实现的一些特性是：

  • 使用稳定状态的 GA(替换全体中最小适应性的个体，而不是整代的替换) 允许向改进了的查询规划快速逼近。这一点对在合理时间内处理查询是非常重要的；

  • 边缘重组交叉的使用特别适于在用GA解决TSP问题时保持边缘损失最低。

  • 否决了把突变作为基因操作符的做法，这样生成合法的TSP漫游时不需要修复机制。

GEQO模块的一部分是采用的 D.Whitley 的 Genitor 算法。

GEQO模块让PostgreSQL查询优化器可以通过非穷举搜索有效地支持大的连接查询。

53.3.1. GEQO生成的候选规划

GEQO规划过程使用标准的规划器代码生成各个独立表的扫描规划。 然后用遗传算法生成连接规划。正如上面讲到的，每个候选的连接规划由基本表的连接序列表示。 在初始阶段， GEQO简单的生成一些随机的连接序列。 对每个连接序列，调用标准的规划器代码评估以这样的连接序列执行查询的成本。 （对连接序列的每一个步骤，考虑所有可能的三种连接策略；并且所有初期决定的关系扫描规划也是有效的。 评估值是所有这些可能性中最廉价的。 ） 评估成本更低的连接序列被认为比代价高的那些连接序列"更加合适"。基因算法淘汰那些最不合适的候选。 然后通过组合最合适的基因生成新的候选，即通过随机选择一部分低成本的连接序列去产生作为候选的新的序列。 这个过程不断重复直到考虑过的连接序列达到一个预设的值，然后在搜索期间找到的最好的结果作为最终生成的执行计划。

这个过程天生是不确定的，因为在选择初期总群以及随后对最佳候补实施"突变"时都带有随机性。 为了避免被选中的计划发生令人惊讶的变化，每次GEQO算法执行都根据当前geqo_seed参数的设置开始一个随机数生成器。 只要geqo_seed以及其他GEQO参数保持固定，对一个给定的查询(以及其他规划器输入，比如统计信息)将生成相同的执行计划。 如果要尝试不同的搜索路径，可以尝试改变geqo_seed。

53.3.2. PostgreSQL GEQO未来的实现任务

还需要一些工作来改进基因算法的参数设置。 在文件src/backend/optimizer/geqo/geqo_main.c里的过程 gimme_pool_size和 gimme_number_generations 在设置参数时不得不为两个竞争需求做出折衷：

  • 查询规划的优化

  • 计算处理时间

在当前的实现中，每个候选连接序列的适应性是通过运行标准规划器的连接选择和代价评估代码从头开始评估的。 当不同的候选使用相似的连接子序列，将有大量的工作会重复。 通过保持子序列的代价评估值可以显著的提升速度。问题在于要避免为了保持这个状态而不合理的内存扩展。

在最基本的层面上，并不清楚用给 TSP 涉及的 GA 算法解决查询优化的问题是否合适。 在 TSP 的情况下，与任何子字符串(部分旅游)相关的开销都是独立于旅游的其它部分的，但是目前，这一点对于查询优化是不同的。 因此，可以怀疑边缘重组交叉是否最有效的突变过程。