在所有关系操作符中，最难于处理和优化的是连接。可能的查询计划数目以查询中连接数量的指数增长。对各种各样处理独立连接的连接方法（如PostgreSQL中的嵌套循环、哈希连接、归并连接）和多种关系访问方法的indexes（如PostgreSQL中的 B 树、哈希、GiST 和 GIN）的支持也进一步加重了优化的负担。
通常的PostgreSQL查询优化器会执行一次在可选策略空间上的近似穷举搜索。这个算法最早由 IBM 的系统 R 数据库引入，它能产生接近最优的连接顺序，但是当查询中的连接数增长到很大时，该算法需要大量的时间和内存空间。这使得普通的PostgreSQL查询优化器不适合需要连接大量表的查询。