中山模板建站代理,织梦做的网站_别人提交给我留的言我去哪里看,购物网站建设代理商,网站建设与管理做什么简介
PostgreSQL 的开发源自上世纪80年代#xff0c;它最初是 Michael Stonebraker 等人在美国国防部支持下创建的POSTGRE项目。上世纪末#xff0c;Andrew Yu 等人在它上面搭建了第一个SQL Parser#xff0c;这个版本称为Postgre95#xff0c;也是加州大学伯克利分校版本…简介
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。
术语解释
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为NodeOptimizer称优化时的关系代数为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 ClassEC是 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, b, c}
|- {a, b}
|- {b, c}
其中每个EC内部的expression称为EquivalenceMemberEM。
生成 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。对每个JoinRelJoin RelOptInfo考虑
sort_inner_and_outer两边排序的MergeJoin路径match_unsorted_outerNull-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 purposepluggable 的形式。影响包括
无法做逻辑和物理优化的互操作。例如前文说到的一个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 在做了适当的剪枝和优化规则糅合后是否也能支持事务场景。
原文链接 本文为云栖社区原创内容未经允许不得转载。
