Question

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

目前 PostgreSQL 优化器的实现在候选策略空间里执行一个近似穷举搜索。这个算法最早是在 IBM System R database 数据库中引入的，它生成一个近乎最优的连接顺序，但是如果查询中的连接增长得很大，它可能会消耗大量的时间和内存空间。这样就使普通的 PostgreSQL 查询优化器不适合那种连接了大量表的查询。

德国弗来堡矿业及技术大学自动控制系的成员在试图把 PostgreSQL 作为用于一个电力网维护中做决策支持的知识库系统的后端时，碰到了上面的问题。该 DBMS 需要为知识库系统的推导机处理很大的连接查询。在可能的查询规划空间里进行检索的恶劣性能引起了人们对发展新的优化技术的需求。

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