Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: Postgres 里的基因查询优化（GEQO）
发信站: 哈工大紫丁香 (2001年11月20日21:01:35 星期二), 站内信件


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 问
题时保持边缘损失最低。
译注: TSP 是旅行推销员问题的意思
否决了把突变（Mutation）作为基因操作符的做法， 这样生成合法的 TSP 漫游时不需
要修复机制．
GEQO 模块让 Postgres 查询优化器可以通过非穷举搜索有效地支持大的 join 查询．

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]