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

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

目前 PostgreSQL 优化器的实现在候选策略空间里执行一个 近似穷举搜索（near-exhaustive search）。 这个算法最早是在 "System R" 数据库中引入的，它生成一个近乎最优的连接顺序，但是如果查询中的连接增长得很大， 它可能会消耗大量得时间和内存空间。这样就使普通的 PostgreSQL 查询优化器不适合那种涉及非常复杂的查询的应用领域。 例如人工智能等。

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

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

在随后的内容里，我们描述了一个 基因算法（Genetic Algorithm）， 这个算法用一种对涉及大量连接的查询很有效的方式解决了连接顺序的问题。