您的位置:寻梦网首页编程乐园数据库PostgreSQL 7.2 Documentation

8.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 查询优化器可以通过非穷举搜索有效地支持大的连接查询.

8.3.1. PostgreSQL GEQO 未来的实现任务

我们还需要一些工作来改进基因算法的参数设置. 在文件 backend/optimizer/geqo/geqo_params.c 里的过程 gimme_pool_size gimme_number_generations , 我们在设置参数时不得不为两个竞争需求做出折衷:

  • 查询规划的优化

  • 计算处理时间