第六十三章. 数据库系统里的基因查询优化

内容
作为复杂优化问题的查询处理
基因算法 (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) 的实现作为解决数据库查询优化问题的一个选择.