59.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 查询优化器能够通过非穷举搜索有效支持大型连接查询。
59.3.1. 使用 GEQO 生成可能的计划
GEQO 规划过程使用标准规划器代码来生成各个关系扫描的计划，然后再用遗传方法生成连接计划。如上所示，每个候选连接计划都表示为一个连接基本关系的顺序。在初始阶段，GEQO 代码只是随机生成一些可能的连接序列。对于每一个待考察的连接序列，都会调用标准规划器代码来估算按该序列执行查询的代价。（对于连接序列中的每一步，都会考虑全部三种可能的连接策略；并且所有预先确定的关系扫描计划也都可用。估计代价取这些可能性中最低者。）估计代价较低的连接序列会被认为比代价较高的序列“适应度更高”。遗传算法会丢弃适应度最低的候选，然后通过组合适应度更高的候选的基因来生成新的候选，也就是从已知低代价连接序列中随机选取片段，构造新的序列以供考察。这个过程会重复进行，直到已经考察的连接序列数量达到预设值；最后，使用整个搜索过程中找到的最佳序列生成最终计划。
由于初始种群选择以及后续对最佳候选的“变异”都包含随机选择，因此这一过程天生就是非确定性的。为了避免所选计划发生令人意外的变化，每次运行 GEQO 算法时，都会用当前的 geqo_seed 参数设置重新初始化其随机数生成器。只要 geqo_seed、其他 GEQO 参数以及统计信息等其他规划器输入保持不变，对于给定查询就会生成相同的计划。若想试验不同的搜索路径，可以尝试修改 geqo_seed。
59.3.2. PostgreSQL GEQO 的未来实现任务 #
为了改进遗传算法的参数设置，仍有一些工作要做。在文件 src/backend/optimizer/geqo/geqo_main.c 中的例程 gimme_pool_size 和 gimme_number_generations 里，我们必须为参数设置找到一种折中，以满足两个相互竞争的需求：
查询计划的最优性
计算时间
在当前实现中，每个候选连接序列的适应度都是通过从头运行标准规划器的连接选择和代价估算代码来估算的。只要不同候选使用了相似的连接子序列，就会有大量工作被重复执行。如果能保留子连接的代价估算，就可以显著加快这一过程。问题在于，必须避免为了保存这种状态而消耗不合理数量的内存。
从更基础的层面看，用一个为 TSP 设计的 GA 算法来解决查询优化问题是否合适，也并不明确。在 TSP 情况下，与任何子串（部分巡回）相关的代价都独立于巡回的其余部分，但对于查询优化显然并非如此。因此，边重组交叉是否是最有效的变异过程，仍然值得怀疑。