Table of Contents
由 Martin Utesch <utesch@aut.tu-freiberg.de> 为德国弗赖贝格矿业和技术大学自动控制研究所编写。
在所有关系操作符中，最难处理和优化的是连接。随着查询中连接数目的增加，可能的查询计划数量会呈指数增长。为了处理单个连接而支持多种连接方法（例如 PostgreSQL 中的嵌套循环、哈希连接和归并连接），以及作为关系访问路径的多种索引（例如 PostgreSQL 中的 B-树、哈希、GiST 和 GIN），也进一步增加了优化工作量。
常规的PostgreSQL查询优化器会在可选策略空间中执行近似穷举搜索。该算法最早出现在 IBM 的 System R 数据库中，能够产生近乎最优的连接顺序；但当查询中的连接数变得很大时，它可能耗费极大的时间和内存空间。因此，普通的PostgreSQL查询优化器并不适合需要连接大量表的查询。
德国弗赖贝格矿业和技术大学自动控制研究所在尝试将 PostgreSQL 用作一个用于电网维护的基于知识的决策支持系统后端时遇到了一些问题。该 DBMS 需要为该基于知识系统中的推理机处理大型连接查询。这些查询中的连接数量使得使用普通查询优化器变得不可行。
下文将介绍一种遗传算法的实现，它以适合涉及大量连接的查询的高效方式来解决连接顺序问题。
如果您发现文档中有不正确的内容、与您使用特定功能的经验不符或需要进一步说明，请使用此表单来报告文档问题。