59.3. PostgreSQL 中的遗传查询优化(GEQO)
GEQO 模块处理查询优化问题就好像它是众所周知的旅行推销员问题(TSP)。可能的查询计划被编码为整数字符串。每个字符串表示从查询的一种关系到下一个关系的连接 Sequences。例如，连接树
/\
/\ 2
/\ 3
4 1
由整数字符串“ 4-1-3-2”编码，这意味着首先连接关系“ 4”和“ 1”，然后是“ 3”，然后是“ 2”，其中 1、2、3、4 是 PostgreSQL 优化器中的关系 ID。
PostgreSQL 中的 GEQO 实现的特定 Feature 是：
-
使用稳定状态 GA(替换总体中最不适合的个体，而不是全世代替换)可以快速收敛到改进的查询计划。这对于在合理的时间内处理查询至关重要。
-
边缘重组交叉的使用，特别适用于通过遗传算法将 TSP 解决方案的边缘损耗保持在较低水平；
-
不赞成使用遗传操作员进行突变，因此不需要任何修复机制即可生成合法的 TSP 巡回赛。
GEQO 模块的某些部分改编自 D. Whitley 的 Genitor 算法。
GEQO 模块允许 PostgreSQL 查询优化器通过非穷举搜索有效地支持大型联接查询。
59 .3.1. 用 GEQO 生成可能的计划
GEQO 计划过程使用标准计划者代码生成用于扫描各个关系的计划。然后使用遗传方法制定加盟计划。如上所示，每个候选加入计划由加入基本关系的 Sequences 表示。在初始阶段，GEQO 代码只是简单地随机生成一些可能的加入序列。对于所考虑的每个连接序列，调用标准计划程序代码以估计使用该连接序列执行查询的成本。 (对于连接序列的每个步骤，都会考虑所有三种可能的连接策略；并且所有初始确定的关系扫描计划都可用.估计成本是这些可能性中最便宜的.)估计成本较低的连接序列被认为“更多适合”的广告。遗传算法会丢弃最不适合的候选对象。然后，通过组合更适合的候选者的基因来生成新的候选者，也就是说，使用已知的低成本连接序列的随机选择部分来创建要考虑的新序列。重复此过程，直到考虑了预设数量的连接序列为止；然后在搜索过程中随时发现的最佳方案将用于生成最终方案。
这个过程本质上是不确定的，因为在最初的总体选择和随后的最佳候选者“变异”过程中都做出了随机选择。为避免所选计划的意外更改，GEQO 算法的每次运行都会使用当前的geqo_seed参数设置重新启动其随机数生成器。只要geqo_seed和其他 GEQO 参数保持固定，将为给定查询(和其他计划程序 Importing，例如统计信息)生成相同的计划。要尝试不同的搜索路径，请尝试更改geqo_seed。
59 .3.2. PostgreSQL GEQO 的 Future 实现任务
仍需要改进遗传算法参数设置的工作。在文件src/backend/optimizer/geqo/geqo_main.c，例程gimme_pool_size和gimme_number_generations中，我们必须为参数设置找到一个折衷方案，以满足两个相互竞争的需求：
-
查询计划的最优性
-
Computing time
在当前实现中，通过从头开始运行标准计划者的联接选择和成本估算代码来估算每个候选联接序列的适用性。如果不同的候选者使用相似的连接子序列，则将重复大量工作。通过保留子联接的成本估算，可以大大加快这一过程。问题是要避免在保持该状态时消耗过多的内存。
从更基本的角度来看，尚不清楚使用为 TSP 设计的 GA 算法解决查询优化是否合适。在 TSP 情况下，与任何子字符串(部分巡回)相关的成本与巡回的其余部分无关，但是对于查询优化而言，肯定不是这样。因此，有疑问的是，边缘重组杂交是否是最有效的突变程序。
