Chapter 8. 基因查询优化

Table of Contents
8.1. 作为复杂优化问题的查询处理
8.2. 基因算法
8.3. PostgreSQL 里的基因查询优化(GEQO
8.4. 进一步阅读

作者: 由德国弗来堡矿业及技术大学自动控制系 Martin Utesch() 写作.

8.1. 作为复杂优化问题的查询处理

在所有关系型操作符里,最难以处理和优化的一个是 连接. 一个查询需要回答的可选规划的数目将随着该查询包含 的连接的个数呈指数增长. 在访问关系的分支时的进一步的优化措施是由多种多样的 连接方法(join methods) (例,在 PostgreSQL 里的嵌套循环,索引扫描,融合联接等 (nested loop, index scan, merge join ))来支持处理独立 的连接和多种多样的索引 如, PostgreSQL 里的 r-tree,b-tree,散列(hash)).

目前 PostgreSQL 优化器的实现在候选策略空间里执行一个 近似穷举搜索(near- exhaustive search). 这个查询优化技术对包含有极广的查询需要的数据库应用领域, 例如人工智能等,支持得不够.

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

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

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