PostgreSQL PostgreSQL 中的遗传查询优化（GEQO）
- 59.3.1. 用GEQO产生可能的计划
- 59.3.2. 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 的遗传算法中改编而来。
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 情况中，与任何子串（部分旅程）相关的代价独立于剩余的旅程，但是对于查询优化肯定不是这样。因此边重组杂交是否比变异过程更有效还存有疑问。