PostgreSQL 优化器代码概览

2020-06-17 00:00:00 路径 优化 算法 生成 重排

简介

PostgreSQL 的开发源自上世纪80年代，它初是 Michael Stonebraker 等人在美国国防部支持下创建的POSTGRE项目。上世纪末，Andrew Yu 等人在它上面搭建了个SQL Parser，这个版本称为Postgre95，也是加州大学伯克利分校版本的PostgreSQL的基石[1]。

我们今天看到的 PostgreSQL 的优化器代码主要是 Tom Lane 在过去的20年间贡献的，令人惊讶的是这20年的改动都是持续一以贯之的，Tom Lane 本人也无愧于“开源软件十大杰出贡献者”的称号。

但是从今天的视角，PostgreSQL 优化器不是一个好的实现，它用C语言实现，所以扩展性不好；它不是 Volcano 优化模型的[2]，所以灵活性不好；它的很多优化复杂度很高（例如Join重排是System R[3]风格的动态规划算法），所以性能不好。

无论如何，PostgreSQL 是优化器的实现和创新源头（想象 Greenplum 和 ORCA 等一系列项目），它的一些优化手段和代码结构在今天仍然是值得借鉴的，包括：

  1. 参数化路径，作用于indexed lookup join
  2. 分区裁剪和并行优化
  3. 强一致的cardinality estimation保证

本文尝试快速地浏览一遍 PostgreSQL 优化器的代码，和现代优化器比较优缺点。大部分的 PostgreSQL 优化器代码来自于 github.com/postgres/pos。 我们提到现代优化器主要指的是 Apache Calcite 和 ORCA。

术语解释

  1. Datum
  2. Qual
  3. Path

关键数据结构

查询

  1. __Query__: Parse Tree，优化器的输入
  2. __RangeTblEntry__: Parse Tree的一个节点，它描述了一个数据集的视图，这个数据集可能来源于某个子查询、Join、Values或任何一个简单关系代数表达式。Join实现需要把它的输入都表达为 RangeTblEntry （以下简称RTE）。

执行计划

  1. __PlannedStmt__: 执行计划的顶层节点
  2. __PlannerInfo__: 优化器的上下文信息。它是一个树形结构，用parent_root变量指向父节点。一个Query包含一个或多个PlannerInfo，每次Join切分一次树节点。它包含RelOptInfo的指针。
  3. __RelOptInfo__: 优化器的核心数据结构，包含一个子查询的Path集合等信息。这个概念对应于ORCA的Group或Calcite中的Set。
  4. __Path__: 区别于Parser称Relational Expression为Node，Optimizer称优化时的关系代数为Path。Path是物理计划，它包含优化器对于单个关系代数的理解，包括并行度、PathKey和cost。
  5. __PathKey__: 排序属性。这个概念相当于Volcano中的Physical Property或Calcite中的Trait。因为 PostgreSQL 是单机数据库，仅用排序属性就可以表达所有算法的需求和实现特性。对于分布式数据库，通常还需要分布属性。

主流程

子查询上拉

因为优化的单元（RelOptInfo）是子查询，合并子查询可以简化优化流程。关联的过程包括：

  1. __pull_up_sublinks__: 将可转换的 ANY/EXISTS 子句转换为 (anti-)semi-join 。一些优化器称这个过程为de-correlation。
  2. __pull_up_subqueries__: 将可上拉的子查询上拉到当前查询，删除原来的子查询。如果子查询是一个 Join ，这个操作相当于打平 binary join 到 multi join。

EquivalenceClass解析

Equivalence Class（EC）是 qual 的术语，它指代的是 expression 的等价性。例如，expression

a = b AND b = c

相关文章