共计 5138 个字符，预计需要花费 13 分钟才能阅读完成。
简介 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 等一系列项目），它的一些优化手段和代码结构在今天仍然是值得借鉴的，包括：
参数化路径，作用于 indexed lookup join 分区裁剪和并行优化强一致的 cardinality estimation 保证本文尝试快速地浏览一遍 PostgreSQL 优化器的代码，和现代优化器比较优缺点。大部分的 PostgreSQL 优化器代码来自于 https://github.com/postgres/p…。我们提到现代优化器主要指的是 Apache Calcite 和 ORCA。
术语解释 DatumQualPath 关键数据结构查询__Query__: Parse Tree，优化器的输入__RangeTblEntry__: Parse Tree 的一个节点，它描述了一个数据集的视图，这个数据集可能来源于某个子查询、Join、Values 或任何一个简单关系代数表达式。Join 实现需要把它的输入都表达为 RangeTblEntry（以下简称 RTE）。执行计划__PlannedStmt__: 执行计划的顶层节点__PlannerInfo__: 优化器的上下文信息。它是一个树形结构，用 parent_root 变量指向父节点。一个 Query 包含一个或多个 PlannerInfo，每次 Join 切分一次树节点。它包含 RelOptInfo 的指针。__RelOptInfo__: 优化器的核心数据结构，包含一个子查询的 Path 集合等信息。这个概念对应于 ORCA 的 Group 或 Calcite 中的 Set。__Path__: 区别于 Parser 称 Relational Expression 为 Node，Optimizer 称优化时的关系代数为 Path。Path 是物理计划，它包含优化器对于单个关系代数的理解，包括并行度、PathKey 和 cost。__PathKey__: 排序属性。这个概念相当于 Volcano 中的 Physical Property 或 Calcite 中的 Trait。因为 PostgreSQL 是单机数据库，仅用排序属性就可以表达所有算法的需求和实现特性。对于分布式数据库，通常还需要分布属性。主流程子查询上拉
因为优化的单元（RelOptInfo）是子查询，合并子查询可以简化优化流程。关联的过程包括：
__pull_up_sublinks__: 将可转换的 ANY/EXISTS 子句转换为 (anti-)semi-join。一些优化器称这个过程为 de-correlation。__pull_up_subqueries__: 将可上拉的子查询上拉到当前查询，删除原来的子查询。如果子查询是一个 Join，这个操作相当于打平 binary join 到 multi join。EquivalenceClass 解析
Equivalence Class（EC）是 qual 的术语，它指代的是 expression 的等价性。例如，expression
a = b AND b = c 则称 {a, b, c} 是一个 EC。特别地，在 PostgreSQL 中，expression
a = b AND b = 5 只生成简化的 EC：{a = 5} {b = 5}
EC 是很关键的数据结构，它的应用场景包括：
在 Join 时，EC 用来决定 Join Key，它决定了 Outer Join 简化和 PathKey 设定在 Join 时决定 qual 穿越决定参数化路径的参数列表匹配主 - 外键约束，以便优化（Join 的）cardinality estimationEC 是一个树形结构，每个节点是一个 EC，并链接到它合并的父节点上。考虑 a = b AND b = c 的例子，最后的 EC tree 表达为
{a, b, c}|- {a, b}|- {b, c} 其中，每个 EC 内部的 expression 称为 EquivalenceMember（EM）。
生成 EC 的入口是 generate_base_implied_equalities，它从 query_planner 调入。也就是说，EC 是在规划 Join 的前一刻生成的，这个阶段解析 EC 的代价最小，但是也决定了 EC 只能应用于 Join 优化。
Join 重排
（有关 Join 重排的背景知识可以参考我之前的文章 SQL 优化器原理 – Join 重排）
make_rel_from_joinlist 是 Join 重排的入口，当前版本的 PostgreSQL 有三种算法：
你可以插入一个自定义的 Join 重排算法 GEQO：Genetic Optimization（基因算法，或遗传算法[4]），是一种非穷举的最优化算法实现 Standard：一个略微剪枝的动态规划算法。默认在 12 路及以上的复杂 Join 中会打开 GEQO。可以在 postgresql.conf 中修改参数
geqo = ongeqo_threshold = 12 控制 GEQO 设定。
现在让我们检查 Standard 算法。它的主入口在 join_search_one_level，每次在已生成的局部计划的基础上：
按 EC 检查未加入的 Join input，加入到生成的局部计划，这个操作仅产生 Left-deep-tree 从未加入局部计划的 Join input 里找到有 EC 的两个 input，生成额外的局部计划，用于生成 Bushy-tree 如果当前层找不到任何 EC 关联，生成笛卡尔积。上述描述已经足够复杂，让我们总结一下 Standard 算法：
Standard 算法仍然是一个穷举的动态规划算法它对 a-b/b-a 镜像去重，同时当 EC 存在时不考虑笛卡尔积，这些工程上的降级有效降低了搜索复杂度路径生成和动态规划
如上所述，优化过程集中在对子查询（RelOptInfo）的重建过程，这可以理解为逻辑优化过程，这通常是跨关系代数操作符的、比较复杂的优化。事实上 PostgreSQL 也同步在做物理优化。
物理优化就是将 Path 加入 RelOptInfo。考虑 Join，物理优化的入口在 populate_joinrel_with_paths。对每个 JoinRel（Join RelOptInfo），考虑：
sort_inner_and_outer：两边排序的 MergeJoin 路径 match_unsorted_outer：Null-generating side 不排序路径，包括 MergeJoin 和 NestedLoopJoin。hash_inner_and_outer：两边哈希的 HashJoin 路径。有趣的点是 HashJoin 路径（hash_inner_and_outer），顾名思义，它要求 Join 两边都计算哈希值。在生成 Path 过程中，需要计算两边的参数信息。例如 A join B on A.x = B.y，对于 A 来说，x 是参数，对于 B 是 y。如果选定 A 作为 Probe side，一旦 B 上有 y 的索引，每次 x 的 probe 将以参数的形式传递给 y 的索引。通过调用 get_joinrel_parampathinfo 来产生参数信息。
路径生成的入口是 add_path，每次生成路径，需要更新 RelOptInfo 的最佳路径和最小代价以便后续动态规划选择全局最优。
流程图
planner|- subquery_planner 迭代的子查询优化
|- pull_up_sublinks de-correlation
|- pull_up_subqueries 子查询上拉
|- preprocess_expression Query/PlannerInfo 结构解析，常量折叠
|- remove_useless_groupby_columns
|- reduce_outer_joins Outer Join 退化
|- grouping_planner
|- plan_set_operations SetOp 优化
|- query_planner 子查询优化主入口
|- generate_base_implied_equalities 生成 / 合并 EC
|- make_one_rel Join 优化入口
|- set_base_rel_pathlists 生成 Join RelOptInfo 列表
|- make_rel_from_joinlist Join 重排和规划
|- standard_join_search 标准 Join 重排算法
|- join_search_one_level
|- make_join_rel 生成 JoinRel 和对应的 Path
|- create_XXX_paths Grouping、window 等其他 expression 优化
讨论扩展性和灵活性
首先，PostgreSQL 的优化器代码可以说非常复杂，这已经极大限制了它的扩展性和灵活性。如果看一眼这部分代码的更新日志，会发现里面的作者已经只有少数几个人。
一部分扩展性限制是由编程语言带来的，因为 C 语言本身不容易扩展，这意味着大部分时候想要添加一个新的 Node 或 Path 变得很不容易，你需要定义一系列的数据结构、Cardinality Estimation 逻辑、并行逻辑和 Path 解释逻辑。并没有类似 interface 这样的抽象指导你该怎么做。虽然，PostgreSQL 的代码已经写得非常工整，而且也有很多的文章告诉你该怎么做（比如 Introduction to Hacking PostgreSQL 和 The Internals of PostgreSQL）。
另一部分扩展性限制是优化器本身的结构带来的。现代的优化器基本都是 Volcano Model[2]的（例如 SQL Server 和 Oracle，就像他们声称的那样），而 PostgreSQL 没有实现为 Volcano Model 这种 Generic purpose，pluggable 的形式。影响包括：
无法做逻辑和物理优化的互操作。例如前文说到的，一个 Join 产生的 EC 必须和它紧跟的 RTE 结合才能产生 IndexedLookupJoin，而不像其他优化器可以把这个 EC（它在某种意义上已经是物理计划）下推到合适的逻辑计划上，指导它做物理计划转换。不容易定制优化规则。开发者关注的切片太大，开发一个优化规则除了关注优化本身，不得不学习其他优化规则的数据结构、动态规划更新、RelOptInfo 新建和清理，甚至内存分配本身。PostgreSQL 仍然提供了部分手写的 Plugin Point，包括：
可定制的 Join 重排算法可定制的 PathKey 生成算法定制的 Join Path 生成算法等等。
性能
虽然没有实验，但是 PostgreSQL 在优化上的性能可以想像是比较好的，这很大程度是用灵活性交换来的。
首先，不像 Volcano Optimizer，PostgreSQL 优化器不需要不断生成中间节点，它的 RelOptInfo 的数量是相对稳定的（约等于 Join 的数量）。它的最优计划搜索以 RelOptInfo 为单位，如果 Join 重排不产生大量 RelOptInfo，搜索宽度很低。
其次，RelOptInfo 简化了大量跨 Relational Expression 优化的细节，比起 Calcite 这种按 Relational Expression 来组织等价路径集合的方案，它的搜索宽度进一步降低了。从等价集合的数量看，PostgreSQL 的搜索宽度大概比 Calcite 要低一个数量级，当然，如上所述，这是用更多优化可能性作为交换的。
最后，PostgreSQL 在优化阶段糅合了很多业务逻辑，在提高代码阅读的难度同时，也相应加快的优化效率。在优化过程中，PostgreSQL 会不间断地做常量折叠、PathKey 去重、Union 打平、子查询打平……这些操作不会应用在 memo 里。
对比 Calcite/Orca，PostgreSQL 的优化更快，更适合事务性场景。不过我无法判断 Calcite/Orca 在做了适当的剪枝和优化规则糅合后，是否也能支持事务场景。
本文作者：少杰
阅读原文
本文为云栖社区原创内容，未经允许不得转载。
