PostgreSQL的遗传算法
本文来自 申德荣.分布式数据库系统原理与应用.北京:机械工业出版社.2011
摘 要:本文介绍了 PostgreSQL 的遗传算法,主要包括遗传查询优化的概念、遗传查询优化
的过程等内容。
关键词: PostgreSQL,遗传查询,GEQO 模块
1 遗传查询优化的概念
有四个关系连接 RSTU 的连接树,如图 1 所示。每个关系使用整数进行对应的连接编码为“4-1-
2-3”,表示 oid 为 4 的关系 R 先与 oid 为 1 的关系 S 连接,再与 T 和 U 连接。
图 1 RSTU 的连接树
在使用遗传查询优化GEQO,Genetic Query Optimization )模块生成执行计划时,GEQO 模块首先使
用标准的查询优化器生成在独立关系上查询谓词的扫描策略,对于连接则使用遗传算法处理。
2 遗传查询优化的过程
PostgreSQL 中的遗传查询优化
初始阶段:
GEQO 模块简单地随机生成一些可行的连接序列,使用标准查询优化器来估计执行代价,选择代价
最小的作为估计代价。
GEQO 模块应用遗传算法,将执行代价作为连接序列的适应性(适应性与执行代价成反比),保留执
行代价较低的连接序列。
下一阶段:
GEQO 模块对在上一阶段保留的执行代价较低的连接序列,随机地选择这些连接序列中部分片段并
改变其连接顺序以生成新的连接序列。
对于新生成的连接序列,GEQO 模块评估其执行代价,并保留其中执行代价小的作为下一个循环阶
段的候选连接序列。
最后,从所有被评估过的连接序列中,选择执行代价最小的作为最终的执行策略。
1 / 1
PostgreSQL 的遗传算法