PostgreSQL7.0手册-开发者手册 -63. 数据库系统里的基因查询优化
2019-09-08 23:34:06
供稿：网友
第六十三章. 数据库系统里的基因查询优化
内容
作为复杂优化问题的查询处理
基因算法 （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 （联接）查询时，用于基因查询优化的时间看来只是 Postgres 通过过程 MemoryContextFree（在文件 backend/utils/mmgr/mcxt.c 里）释放内存的 一小部分（fraction）．跟踪调试显示释放内存的工作陷在文件 backend/utils/mmgr/oset.c 里的过程 OrderedElemPop 里的一个循环里了．在使用普通 Postgres 查询优化算法处理长的查询时也会产生这个问题．
改善基因算法参数设置
在文件 backend/optimizer/geqo/geqo_params.c 里的过程 gimme_pool_size 和 gimme_number_generations，我们在设置参数时不得不为两个竞争条件做出折衷：
查询规划的优化
计算处理时间
寻找解决整数溢出的更好的办法
在文件 backend/optimizer/geqo/geqo_eval.c 里的过程 geqo_joinrel_size，目前对防止 MAXINT 溢出的方法（hack）是把 Postgres 的整数值 rel->size to 设置为它的对数．对 backend/nodes/relation.h 里的 Rel 的变动显然将严重影响整个 Postgres 的实现．
寻找解决内存耗尽的办法
当一个查询里的关系超过 10 个时将导致内存的耗尽．在文件 backend/optimizer/geqo/geqo_eval.c里的过程 gimme_tree 是被递归调用的．可能我忘记了正确地释放某些东西了，但是我不知道是什么．当然 join 的rel 数据结构随着更多的关系打包进入之后会越长越大．欢迎任何建议 :-(
参考
GEQ 算法的参考信息．
The Hitch-Hiker's Guide to Evolutionary Computation, J g Heitk ter 和 David Beasley， InterNet resource, The Design and Implementation of the Postgres Query Optimizer, Z. Fong, University of California, Berkeley Computer Science Department, Fundamentals of Database Systems, R. Elmasri and S. Navathe, The Benjamin/Cummings Pub., Inc..
comp.ai.genetic 上的FAQ可以在 Encore拿到．
文件 planner/Report.ps 在 'postgres-papers' 发布版里．
--------------------------------------------------------------------------------
