登录62.3. PostgreSQL 中的遗传查询优化 (GEQO)#
GEQO模块将查询优化问题视为众所周知的旅行商问题 (TSP)。可能的查询计划被编码为整数字符串。每个字符串表示从查询的一个关系到另一个关系的连接顺序。例如，连接树
/\
/\ 2
/\ 3
4 1由整数字符串 '4-1-3-2' 编码，这意味着，首先连接关系 '4' 和 '1'，然后是 '3'，最后是 '2'，其中 1、2、3、4 是PostgreSQL优化器中的关系 ID。
GEQO在PostgreSQL中实现的具体特性包括
使用稳态（替换种群中最不适应的个体，而不是整个世代替换）可以快速收敛到改进的查询计划。这对于在合理的时间内处理查询至关重要；
使用边缘重组交叉，它特别适合通过保持解决方案的边缘损失较低；
弃用突变作为遗传算子，因此不需要修复机制来生成合法的巡游。
GEQO模块的部分内容改编自 D. Whitley 的 Genitor 算法。
GEQO模块允许PostgreSQL查询优化器通过非穷举搜索有效地支持大型联接查询。
62.3.1. 使用GEQO生成可能的计划#
GEQO计划过程使用标准计划程序代码为各个关系的扫描生成计划。然后使用遗传方法开发联接计划。如上所示，每个候选联接计划都由一个序列表示，用于联接基础关系。在初始阶段，GEQO代码只是随机生成一些可能的联接序列。对于考虑的每个联接序列，都会调用标准计划程序代码来估算使用该联接序列执行查询的成本。（对于联接序列的每一步，都会考虑所有三种可能的联接策略；并且所有最初确定的关系扫描计划都可用。估算成本是这些可能性中最便宜的。）估算成本较低的联接序列被认为比成本较高的联接序列“更适应”。遗传算法会丢弃最不适应的候选者。然后通过组合更适应的候选者的基因来生成新的候选者——即通过使用已知低成本联接序列的随机选择部分来创建新的序列以供考虑。此过程重复进行，直到考虑了预设数量的联接序列；然后在搜索过程中任何时候找到的最佳序列用于生成最终计划。
由于在初始种群选择和最佳候选者的后续“突变”过程中做出了随机选择，因此此过程本质上是不确定的。为了避免选定计划发生意外更改，每次运行 GEQO 算法都会使用当前geqo_seed参数设置重新启动其随机数生成器。只要geqo_seed和其他 GEQO 参数保持固定，就会为给定的查询（以及其他计划程序输入，例如统计信息）生成相同的计划。要尝试不同的搜索路径，请尝试更改geqo_seed。
62.3.2.PostgreSQLGEQO的未来实现任务#
仍需要工作来改进遗传算法参数设置。在文件src/backend/optimizer/geqo/geqo_main.c中，例程gimme_pool_size和gimme_number_generations，我们必须找到参数设置的折衷方案，以满足两个相互竞争的需求
查询计划的最优性
计算时间
在当前实现中，通过从头运行标准计划程序的联接选择和成本估算代码来估算每个候选联接序列的适应性。在不同候选使用类似联接子序列的范围内，将会重复大量工作。通过保留子联接的成本估算可以显著加快速度。问题在于避免在保留该状态上花费不合理的大量内存。
在更基础的层面上，尚不清楚使用专为 TSP 设计的 GA 算法来解决查询优化是否合适。在 TSP 情况下，与任何子字符串（部分巡游）关联的成本与巡游的其余部分无关，但这对于查询优化来说肯定不是真的。因此，值得怀疑边缘重组交叉是否是最高效的突变过程。