PostgreSQL 优化器代码概览

PostgreSQL 优化器代码概览,第1张

概述简介 PostgreSQL 的开发源自上世纪80年代,它最初是 Michael Stonebraker 等人在美国国防部支持下创建的POSTGRE项目。上世纪末,Andrew Yu 等人在它上面搭建了第一个SQL Parser,这个版本称为Postgre95,也是加州大学伯克利分校版本的PostgreSQL的基石[1]。 我们今天看到的 PostgreSQL 的优化代码主要是 Tom Lane 简介
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/postgres/tree/master/src/backend/optimizer 。 我们提到现代优化器主要指的是 Apache Calcite 和 ORCA。

术语解释
Datum
Qual
Path
关键数据结构
查询
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 estimation
EC是一个树形结构,每个节点是一个EC,并链接到它合并的父节点上。考虑a = b AND b = c的例子,最后的EC tree表达为

{a,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 = on
geqo_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 在做了适当的剪枝和优化规则糅合后,是否也能支持事务场景。

注释
[1] BrIEf History of Postgresql,https://www.postgresql.org/docs/current/history.html

[2] Graefe,G.,& McKenna,W. J. (1993). The Volcano Optimizer Generator: Extensibility and EfficIEnt Search. Proceedings of the Ninth International Conference on Data Engineering,(April),209–218. https://doi.org/10.1109/ICDE.1993.344061

[3] Selinger,P. Griffiths,et al. "Access path selection in a relational database management system." Proceedings of the 1979 ACM SIGMOD international conference on Management of data. ACM,1979.

[4] Steinbrunn,M.,Moerkotte,& Kemper,A. (n.d.). Optimizing Join Orders,1–55.

总结

以上是内存溢出为你收集整理的PostgreSQL 优化器代码概览全部内容,希望文章能够帮你解决PostgreSQL 优化器代码概览所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/sjk/1163082.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-01
下一篇 2022-06-01

发表评论

登录后才能评论

评论列表(0条)

保存