59.1. 将查询处理看成是一个复杂的优化问题

在所有关系操作符中,最难于处理和优化的是连接。可能的查询计划数目以查询中连接数量的指数增长。对各种各样处理独立连接的连接方法(如PostgreSQL中的嵌套循环、哈希连接、归并连接)和多种关系访问方法的indexes(如PostgreSQL中的 B 树、哈希、GiST 和 GIN)的支持也进一步加重了优化的负担。

通常的PostgreSQL查询优化器会执行一次在可选策略空间上的近似穷举搜索。这个算法最早由 IBM 的系统 R 数据库引入,它能产生接近最优的连接顺序,但是当查询中的连接数增长到很大时,该算法需要大量的时间和内存空间。这使得普通的PostgreSQL查询优化器不适合需要连接大量表的查询。

德国弗莱堡的矿业大学自动控制学院在使用PostgreSQL作为电力网格维护决策支持知识系统的后端时遇到了一些问题。DBMS 需要为知识系统中的推理机器处理大量连接查询。这些查询中的连接数不可能用普通的查询优化器来处理。

接下来我们将介绍一种遗传算法的实现,它被用来以一种更有效率的方式为涉及大量连接的查询解决连接顺序问题。