9.1第50章
47.1. 作为复杂优化问题的查询处理
在所有关系型操作符里，最难以处理和优化的一个是连接。 一个查询需要回答的可选规划的数目将随着该查询包含的连接的个数呈指数增长。 在访问关系的分支时的进一步的优化措施是由多种多样的连接方法（join methods） （例，在 PostgreSQL 里的嵌套循环，索引扫描，融合连接等） 来支持处理独立的连接和多种多样的索引， 如， PostgreSQL 里的 r-tree，b-tree，散列（hash））。
目前 PostgreSQL 优化器的实现在候选策略空间里执行一个 近似穷举搜索（near-exhaustive search）。 这个算法最早是在 "System R" 数据库中引入的， 它生成一个近乎最优的连接顺序，但是如果查询中的连接增长得很大， 它可能会消耗大量得时间和内存空间。 这样就使普通的 PostgreSQL 查询优化器不适合那种连接了大量表的查询。
德国弗来堡矿业及技术大学自动控制系的成员在试图把 PostgreSQL DBMS 作为用于一个电力网维护中做决策支持的知识库系统的后端时，碰到了上面的问题。 该 DBMS 需要为知识库系统的推导机处理很大的连接查询。
在可能的查询规划空间里进行检索的恶劣性能引起了人们对发展新的优化技术的需求。
在随后的内容里，我们描述了一个 基因算法（Genetic Algorithm）， 这个算法用一种对涉及大量连接的查询很有效的方式解决了连接顺序的问题。
47.2. 基因算法
基因算法(GA)是一种启发式的优化法（heuristic optimization method）， 它是通过不确定的随机搜索进行操作。 优化问题的可能的解的集合被认为是个体（individuals）组成的种群（population）。 一个个体对它的环境的适应程度由它的适应性（fitness）表示。
一个个体在搜索空间里的参照物是用染色体（chromosomes）表示的， 实际上那是一套字符串。 一个基因 （gene）是染色体的一个片段，基因是被优化的单个参数的编码。 对一个基因的典型的编码可以是二进制（binary）或整数（integer）。
通过仿真进化过程的重组（recombination）， 变异（mutation）和选择（selection）找到新一代的搜索点， 它们的平均适应性要比它们的祖先好。
根据 comp.ai.genetic FAQ，我们不论怎么强调 GA 在解决一个问题时不是纯随机搜索都不过份。 GA 使用随机处理，但是结果明显不是随机的（比随机更好）。
Figure 47-1. 基因算法的结构化框图
P(t) t 时刻的父代
P(t) t 时刻的子代
+=========================================+
|>>>>>>>>>>> Algorithm GA <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0 |
+=========================================+
| INITIALIZE P(t) |
+=========================================+
| evalute FITNESS of P(t) |
+=========================================+
| while not STOPPING CRITERION do |
| +-------------------------------------+
| | P'(t) := RECOMBINATION{P(t)} |
| +-------------------------------------+
| | P(t) := MUTATION{P'(t)} |
| +-------------------------------------+
| | P(t+1) := SELECTION{P(t) + P(t)} |
| +-------------------------------------+
| | evalute FITNESS of P(t) |
| +-------------------------------------+
| | t := t + 1 |
+===+=====================================+
47.3. PostgreSQL 里的基因查询优化（GEQO）
GEQO 模块是试图解决类似漫游推销员问题（TSP）的查询优化问题的。 可能的查询规划被当作整数字串进行编码。每个字串代表查询里面一个关系到下一个关系的 连接的顺序。 例如，下面的连接树
/\ /\ 2 /\ 3 4 1
是用整数字串 '4-1-3-2' 编码的， 这就是说，首先联接关系 '4' 和 '1'，然后 '3'，然后是 '2'， 这里的 1，2，3，4都是 PostgreSQL 优化器里的关系标识（ID）。
GEQO 模块的一部分是采用的 D. Whitley 的 Genitor 算法。
在 PostgreSQL 里的 GEQO 实现的一些特性是：
- 使用 稳定状态（steady state）的 GA （替换全体中最小适应性的个体，而不是整代的替换）允许向改进了的查询规划快速逼近。 这一点对在合理时间内处理查询是非常重要的；
- 边缘重组交叉（edge recombination crossover）的使用特别适于在用 GA解决 TSP 问题时保持边缘损失最低。
译注: TSP 是旅行推销员问题的意思
- 否决了把突变（Mutation）作为基因操作符的做法，这样生成合法的 TSP 漫游时不需要修复机制。
GEQO 模块让 PostgreSQL 查询优化器可以通过非穷举搜索有效地支持大的连接查询。
47.3.1. PostgreSQL GEQO 未来的实现任务
我们还需要一些工作来改进基因算法的参数设置。 在文件 backend/optimizer/geqo/geqo_params.c 里的过程 gimme_pool_size 和 gimme_number_generations， 我们在设置参数时不得不为两个竞争需求做出折衷：
- 查询规划的优化
- 计算处理时间
在最基本的层面上，我们并不清楚用给 TSP 涉及的 GA 算法解决查询优化的问题是否合适。 在 TSP 的情况下，与任何子字串（部分旅游）相关的开销都是独立于旅游的其他部分的， 但是目前，这一点对于查询优化是不同的。因此，我们可以怀疑边缘重组交叉是否最有效的突变过程。
47.4. 进一步阅读
下面的资源包含一些额外的关于基因算法的信息∶
- （The Hitch-Hiker's Guide to Evolutionary Computation）Hitch-Hiker 进化计算的指导 (comp.ai.genetic 的 FAQ)
- （Evolutionary Computation and its application to art and design）进化计算以及它在艺术和设计中的应用 by Craig Reynolds
- Fundamentals of Database Systems
- POSTGRES 查询优化器的设计与实现
