数据库路径选择理论与PostgreSQL实现

数据库路径选择理论与 PostgreSQL 实现

摘要

数据库将SQL解析成一棵语法树后，就需要将语法树转换成查询树，然而查询树的每一个节点或者节点之间的连接都会有一种或者多种实现算法，而需要从中挑选出最优的节点组合。

路径表示单个表的访问方式(顺序访问、索引访问、点查)、两个表的连接方式(嵌套连接、归并连接、hash连接)以及多个表的连接顺序。 那么优化器需要枚举出所有的路径，从中挑选代价最低的路径来执行。

查询树上有的节点是可以直接进行优化的，如过滤、投影等，在查询树底部先将不需要的数据过滤掉，以减少数据量往查询树上层的传递以及操作的成本，这种优化是显而易见的，是基于经验的，我们称为启发式规则优化。 然而，有的优化是无法直接进行的，例如，A JOIN B，JOIN顺序A JOIN B 或者 B JOIN A都会输出正确的查询树结果，哪种顺序成本最低呢，这就需要基于统计数据来进行估算，找出代价最小的顺序，这种优化我们称之为基于成本的优化。