PostgreSQL7.0手册-开发者手册 -63. 数据库系统里的基因查询优化

第六十三章.　数据库系统里的基因查询优化
内容　
作为复杂优化问题的查询处理　
基因算法　（GA）　
Postgres　里的基因查询优化（GEQO）　
Postgres　GEQO未来的实现任务　
作者：由德国弗来堡矿业及技术大学自动控制系　Martin　Utesch　书写．
作为复杂优化问题的查询处理
在所有关系型操作符里，最难以处理和优化的一个是　join．一个查询需要回答的可选规划的数目将随着该查询包含的　join　的个数呈指数增长．在访问关系的分支时的进一步的优化措施是由多种多样的　联接方法(join　methods)　（例如，在　Postgres　里的嵌套循环，索引扫描，融合联接等（nested　loop,　index　scan,　merge　join　））来支持处理独立　join　（联接）和多种多样的　索引(indices)　（如，Postgres里的　r-tree，b-tree，散列（hash））．　
目前　Postgres　优化器的实现在候选策略空间里执行一个近似完全搜索　(near-　exhaustive　search)　．这个查询优化技术对包含有极广的查询需要的数据库应用领域，例如人工智能等，支持得不够．　

德国弗来堡矿业及技术大学自动控制系的成员在试图把Postgres　DBMS　作为用于一个电力网维护中做决策支持的知识库系统的后端时，碰到了上面的问题．该　DBMS　需要为知识库系统的推导机处理很大的　join　（联接）查询．　

在可能的查询规划空间里进行检索的恶劣性能引起了人们对发展新的优化技术的需要．　

在随后的内容里，我们提出一个　基因算法　(Genetic　Algorithm)　的实现作为解决数据库查询优化问题的一个选择．　
　


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

基因算法（GA）
GA　是一种启发式的优化法（heuristic　optimization　method），它是通过既定的随机搜索进行操作．优化问题的可能的解的集合被认为是个体　(individuals)　组成的的　人群(population)　．一个个体对它的环境的适应程度由它的健康度（fitness）表示．　
一个个体在搜索空间里的参照物是用染色体（chromosomes）表示的，实际上那是一套字符串．一个基因　（gene）是染色体的一个片段，基因对被优化的单个参数进行编码．对一个基因的典型的编码可以是　二进制　（binary）或整数（integer）。　

通过仿真进化过程的重组　（recombination）。突变　（mutation），和选择　（selection）找到新一代的搜索点，它们的平均健康度要比它们的祖先好．　

根据　"comp.ai.genetic"　FAQ，我们不论怎么强调　GA　在解决一个问题时不是纯随机搜索都不过份．GA　使用随机处理，但是结果明显不是随机的（比随机更好）．　

GA　结构化框图：
---------------------------

P(t)　　　　generation　of　ancestors　at　a　time　t
P''(t)　　generation　of　descendants　at　a　time　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　　　　　　　　　　　　　　　　　　　　　　　　　　|
+===+=====================================+

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

Postgres　里的基因查询优化（GEQO）
GEQO　模块是试图解决类似漫游推销员问题（TSP）的查询优化问题的．可能的查询规划被当作整数字串进行编码．每个字串代表查询里面一个关系到下一个关系的　join　的顺序．例如，下面的查询树　
　　　　　　　/\
　　　　　　/\　2
　　　　　/\　3
　　　　4　　1
是用整数字串　'4-1-3-2'　编码的，这就是说，首先联接关系　'4'　和　'1'，然后　'3'，然后是　'2'，这里的　1，2，3，4都是　Postgres　里的关系标识（relids）。　
GEQO　模块的一部分是采用的　D.　Whitley　的　Genitor　算法．　

在　Postgres　里的　GEQO　实现的一些特性是：　

稳定状态　(steady　state)　GA　的使用（替换全体中最小健康度的个体，而不是整代的替换）允许向改进了的查询规划快速逼近．这一点对在有效时间内处理查询是非常重要的；
边缘重组交叉　(edge　recombination　crossover　)　的使用特别适于在用GA　解决　TSP　问题时保持边缘损失最低。
否决了把突变（Mutation）作为基因操作符的做法，这样生成合法的　TSP　漫游时不需要修复机制．

与　Postgres　的查询优化器实现相比较，GEQO　模块对Postgres　DBMS　有下面的贡献：　
通过非完全搜索对大的　join　（联接）查询进行操作；
改善了查询规划的开销尺寸的近似值，因为不需要做规划融合了（GEQO　模块把查询规划的开销当作一个个体来评估）．

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

PostgresGEQO　未来的实现任务
基本改进
改进查询处理完后的内存释放
在处理大　join　（联