数据库挖矿系列-优化器设计探索穿越之旅

2024/04/07

引用来自百度百科的话术：在数据库技术发展历史上，1970 年是发生伟大转折的一年，因为这一年的6月，IBM的圣约瑟研究实验室的高级研究员Edgar Frank Codd在Communications of ACM 上发表了《A Relational Model of Data for Large Shared Data Banks》。ACM 后来在1983 年把这篇论文列为从1958年以来的25年中最具里程碑意义的25篇论文之一，因为它首次明确而清晰地为数据库系统提出了一种崭新的模型， 即关系模型。自从关系模型诞生后，当时的层次型模型（类似XML/JSON）和网状模型（类似Graph图）的数据库迅速消亡掉（当然现在又回来了），而1981年的图灵奖很自然地授予了这位“关系数据库之父”。由于他的研究成果，IBM投巨资开展关系数据库管理系统System R的研究，又在此基础上推出的DB2和SQL等产品。1970 年以后，E.F.Codd继续致力于完善与发展关系理论。1972年，他提出了关系代数和关系演算的概念，在传统集合运算的并（Union）、交（Intersection Referential Integrity）、差（Difference）、广义笛卡尔积（Extended Cartesian Product）和包括了投影（Projection）、选择（Selection）、连接（Join）、除（Division）等基本运算。接下来在1974年，IBM的Ray Boyce和Don Chamberlin将Codd关系数据库的12条准则的数学定义以简单的关键字语法表现出来，里程碑式地提出了SQL（Structured Query Language）语言，在1986年，IBM和Oracle促使ANSI把SQL作为关系数据库语言的美国标准。

与此同时，1973年加州大学伯克利分校的Michael Stonebraker和EugeneWong利用System R已发布的信息开发自己的关系数据库系统Ingres。不过Ingres使?的是Stonebraker发明的QUEL（Query Language）的查询技术，这和IBM的SQL?不相同，在某些地?QUEL甚?要优于SQL，我们可以感受下两种语言的不同：

了解这段小历史和优化器什么关系呢？就像我们设计系统一样，首先我们的目标是为了什么？解决什么样的客户问题？我们现在很容易想到数据库系统包括交互语言，完美的优化器，高效的执行器，稳定安全的存储等等。而在当时，如何定义数据关系模型及其运算和建立简单灵活的交互式语言将成为数据库软件当时发展方向的最重要的一步。

那么既然模型和语言都已经定义了，那就可以回到我们的主题上了，如何能够高效的设计一套系统，高效的完成输入语言的要求？那么数据库优化器就成为数据库最重要的组件之一。有语言就有parser，有模型定义就需要有语义解析。通过两个重要模块后，我们就形成了我们需要的程序代码可以识别，并且可以做关系代数转换的关系代数结构（Init Logical Plan），即优化器的输入数据结构。SQL是给人看的，Init Logical Plan是给优化器看的。优化器就是找到代价“最优”的执行计划。

为什么“最优”带引号，首先记住一点，通常认为找到最优计划是NP-hard的问题，没有任何优化器能够产生出真正的最优执行计划，为什么呢？

• 通过估算的技术来猜测最优计划的代价
• 通过启发式来限制计划的搜索空间

上面图应该是传统优化器的架构图，我们这里重点讲的是从初始逻辑计划（步骤4）开始的到“最优”计划生成结束（步骤6）的探索过程。

逻辑计划即由逻辑关系代数表达式组成的结构（Tree or Graph），以及可以通过关系代数等价转换来生成等价逻辑计划。我们前面已经讲到了E.F Codd论文中扩展了增加数据库相关的关系代数运算，可以参考维基百科《Relational_algebra》。论文和数据库相关课程都以JOIN的交换律、结合率为举例来说明逻辑，比如(A ? (B ? C))=(B ? (A ? C))。早期IBM Research做了很多关于数据库关系代数转换的论文其中一篇《Implementation of Magic-sets in a relational Database System》大家可以参考下，IBM喜欢用Magic来解释Heuristic方法，另外Oracle对于子查询的几篇论文也是非常有趣《Enhanced Subquery Optimizer in Oracle》，详细会另文来解释了。

物理计划是由逻辑计划生成的（不一定是1:1），指定了具体的执行策略和算法，再拿JOIN来举例，比如 (A ? B)={ (A NL B) or (A HJ B) or (A MJ B) .....}

代价模型包括：物理代价如预测的CPU cycles，I/O的代价，cache misses，memory消耗，prefetching考虑等等，非常依赖于硬件。通常我们对传统数据库的部署和基于不同算力和不同共享存储介质的云原生数据库代价模型应该动态的去重新评估（possible专利）。逻辑代价，包括估算算子的结果大小（Join）、复杂算子实现代价（Sort/Materialization/Windows....）等。

为什么会讲到优化的粒度，这里不得不要面向于客户场景，优化器的架构设计演进与客户的应用场景息息相关，从早期解决OLTP到DSS到OLAP到大数据查询Query从简单到复杂，数据模型从sysbench、tpch到tpcds参与计算数据量激增，优化技术从index+sarable search到关系代数转换、magic transformation到plan重用、search space优化、中间结果物化等等，因此设计系统不得不考虑优化器本身带来的影响。就像MySQL，通过简单的Heuristic的Rules和左深树方式Plan Enumerate的算法就可以很快解决互联网用户的TP需求。

前面说了，既然优化通常是个NP-hard问题，那么我们需要在优化器优化的过程中，引入终止条件，最差就是全部都计算下可能的Plan，通常情况下会根据到达最大优化时间或者优化的消耗值为0后，选择当前的最优plan。后面会讲到，在这两个变量不变的情况下，如何通过减少搜索空间（计划剪枝），甚至通过并行优化来解决找到最优plan的过程。

谈到优化策略，就已经可以开启我们探索之旅，这里我先列出相关的策略，后面慢慢一一来看产业界和学术界是如何演进优化器框架和策略的。

• 启发式（Heuristics）
• 启发式+基于代价的JOIN（Heuristics + Cost-based Join Order Search）
• 分层优化器框架（Stratified Search）
• 统一优化器框架（Unified Search）

数据库优化器主要要解决的问题，就是可扩展性和可以支持更多领域的系统（Database、AI等），下面我们将回到过去来回顾下关系型数据库的发展历史和各自优化器框架是如何设计和发展的。

INGRES（INteractive Graphics REtrieval System）是Michael Stonebraker在读完E.F Codd论文后决定要构建的一个数据库系统，诞生于1970s而早于System R，Ingres造就了一批著名的商业数据库包括Sybase, Microsoft SQL Server等。而80s主要的竞争对手就是Oracle，不过遗憾的是在1985年，由于Oracle的市场竞争以及和SQL标准失之交臂后逐渐退出市场。

前面也提到了，因为Ingres和System R都是早期的数据库雏形，灵感来自于关系理论，首要就是都需要设计自己的查询语言QUEL。Ingres的优化器框架简单可以表示为下图：

Ingres的优化器提出了基于heuristic greedy方式的Decomposition的技术，其设计目标需要满足：

• 无笛卡尔积产生：结果集合是靠组装一片片小的集合而不是直接去由笛卡尔积产生。
• 无几何增长: 扫描的元组尽可能的保持很少，大多数查询SQL都远小于表的cardinality。

下面通过一个简单例子描述Decomposition的两个步骤Decompose into single-value queries和Substitute the values from queries，假设：

表定义：
Suppher (Sf, Sname, City)
Parts (P#, Pname, Size)
Supply (S#, PP, Quantity)

QUEL查询(Q)：
RANGE OF (S,P,Y) IS (Supplier, Parts, Supply)
RETRIEVE (S.Sname) WHERE (S.City=‘New York’)
AND (P.Pname=‘Bolt’)
AND (P.Size=20)
AND (Y.S#=S.S#)
AND (Y.P#=P.P#)
AND (Y.Quantity2200)

可以看到在Q中的Parts被拆解和替换成Q1和Q->Q'，也可以用右图来表达该逻辑转换。

整个后续的Q的拆解过程如下图：

对于Q1到Q3中的变量替换可以是任意的，因为只有一个变量，而对于Q4和Q5，如Q5：RETRIEVE (S.Sname) WHERE (Y.S#=S.S#) 的两个变量，假设S#列内容为101,107和203，那替换过程变成了：

总结Ingres，采用的Heuristic规则的方式：

• 尽早执行限制条件的SELECTION
• 在JOIN之前执行所有SELELCTION
• Predicate/Limit/Projection算子进行下推
• JOIN ordering是基于Cardinality的

Ingres缺点也是明显的，这里简单提及下1986年后的PostgreSQL（Post-Ingres），它和Starburst一样，也开始继续探索Rule System来对优化器SQL Rewrite进行改进。

System R

System R是1974年IBM San Jose研究院的基于数据库系统的研究项目，提出了第一版的SQL语言，也称为了现在数据库查询语言的标准。System R的架构将数据库分为三个部分：?户程序、关系数据系统（RDS）、关系存储系统（RSS）以及两个接?：关系数据接?（RDI）和关系存储系统（RSI）。

System R优化器第一次提出了自底向上的动态规划搜索策略，影响了后续的很多系统。另一个创新点在于提出来基于cost-based的优化方法，如何根据sargable条件计算selective，增加了interesting order属性来对访问方法（Access Path）进行影响。System R优化器基于两个假设：

• 每一列的值都从某个最小值到某个最大值均匀分布
• 各列值的分布是相互独立的

System R优化器在计算代价路径时，需要考虑以下?点：关系表的元组数量（R）、关系表所占的page的数量（D）、每个page包含的元组平均数量（T=R/D）、索引中不同的字段的数量（I）和CPU代价系数（H，1/H是元组比较的数量是否等同于一次磁盘页面访问的成本），根据可选择索引来决定使?哪种扫描?式：

• 方法1：集簇索引且?较运算符为'='，Expected Cost=R/(T×I)次page访问。
• 方法2：集簇索引且?较运算符不为'='。假设有?半的元组满?条件，Expected Cost=R/(2×T)。
• 方法3：?集簇索引且?较运算符为’=‘，每个元组需要一次page访问，Expected COST=R/I。
• 方法4：?集簇索引且?较运算符不为'='，Expected Cost=R/2。
• 方法5：集簇索引且索引和谓词不匹配，Expected Cost=(R/T)+H×R×N，其中N为查询中谓词的数量。
• 方法6：?集簇索引且索引和谓词不匹配，Expected Cost=R+H×R×N。
• 方法7：表扫描，独立segment，Expected Cost=(R/T)+H×R×N。
• 方法8：表扫描且和其他表shared segment，Expected Cost>=(R/T)+H×R×N。

然后根据以下规则选择上?的?种?法：

• 如果?法1可?，选择?法1。
• 如果?法2、3、5、7可?，选择其中代价最?的。
• 如果上?两条都不满?，那么如果4满足选择方法4，否则一次看方法6和8，如果有可?的就直接选择。

System R优化器整个搜索过程分单表、两表......的方式进行，下图作为一个举例。

SELECT NAME,TITLE,SAL,DNAME
FROM EMP,DEPT,JOB
WHERE TITLE=‘CLERK’
AND LOC=‘DENVER’
AND EMP.DNO=DEPT.DNO
AND EMP.JOB=JOB.JOB

首先看到单表关于Access Paths的优化过程，分别展示了三个表的访问方式（index/segment scan）和其统计信息如C(EMP.DNO) 即通过DNO扫描的代价，Ni代表了结果的card，并形成了单表的search tree。

接下来扩展到两表的Search tree，可以看到从上往下的第一层节点代表两个表的连接顺序，如(EMP,DEPT），接下来记录了按访问顺序选择的访问方式和统计信息，如最左端的Index EMP.DNO，表示用index scan的方式访问EMP表，而再下一条边是Index DEPT.DNO，表示用index scan方式访问DEPT表，之后到达最底端，产生了具体的代价、Card和Interesting Order的组合，以此类推。

System R在最后也初步提到了对于相关和非相关子查询的估算方法，具体会在后续的论文才提到。System R的经典设计，确实影响了后续很多数据库的设计。

Starburst Project

Starburst项目主要是针对于Query Rewrite模块，创新的提出了实现一套可扩展的Rule Engine来更好的实现逻辑关系代数转换，当时设计的目标如下：

• Make queries as declarative as possible，尽量让输入的查询语句表达目标，而忽略数据库引擎如何来执行产生结果；
• Perform natural heuristics，通过Heuristic的方式进行查询改写，比如条件下推，能带来巨大的性能提升。

总结，正是因为System R和Starburst的充分结合，正式诞生了DB2，开创了关系型数据库的商业之旅。由于

文章已经充分介绍了相关优化的详细内容，本文不再赘述。

EXODUS是一个可扩展的数据库，目标是为了帮助数据库的实现者快速实现高效的、应用特定的数据库系统，可以独立于数据模型，提供核心的组件包括通用的存储管理器和类型管理器，并提供了一套通用架构、工具和组件，有兴趣可以参考《The Architecture of the EXODUS Extensible DBMS》。

本文主要重点还在优化器上，不过早期的理论都不仅仅在完善一个优化器，而是可以针对各种不同数据模型，所以你都能看到早期的论文会加Generator字样，其实就是优化器的抽象架构和生成系统，而且很多概念源于当时的AI系统的语言、关系和系统，有点和现在云大数据平台或者计算平台。

下面是EXODUS Optimizer Generator的架构图，输入是和查询树转换相关的一组算子、一组方法实现和关系代数转换规则及算子和方法实现之间的描述信息（model description file）。

The Input to the Optimizer Generator

当数据库构建的时候，Generator负责根据model description file生成指定的优化器，在运行时态的时候能够根据用户接口转换为相应的query tree，再通过optimizer转换成对应的执行计划，再到interpreter解析为可执行程序。优化器中所有初始查询树及其转换的等价关系代数树放在MESH的hash结构中，Transformation rules放在OPEN的优先级队列中，简单算法描述如下：

model description file是分两部分，一部分是description部分，比如：

一部分是rule部分，包括Transformation rules和impementation rules，比如：

有些规则是可以双向的根据相应的条件，比如：

在EXODUS Optimizer Generator的rule系统中，是可以有重复的rules，比如如果实际运行当中总能放下某几个rules结合到一起，那么就可以增加合并的rule。

除了model description file之外，自然还需要一组对于每个算子的基于C语言的property函数、对于每个函数property函数和cost 函数和可以进行参数比较/分配内存等的support函数。

Operation of a Generated Optimizer

在整个exploration的过程，满足rules转换的等价查询树和等价执行计划都会保存在MESH结构中，所以必须有机制来减少不必要重复结构，比如下图中，两个箭头代表运用两次转换（filter下推和join枚举），其中尽量重用了当中的结构，新产生的节点尽量是自底向上用之前的来代替的。

如果两个节点有相同的算子、算子参数和相同的输入，当新的节点产生拷贝到MESH中，可以通过一个hash结构尽早的来找到公共的表达式（common subexpression）减少重复和关联。如果确实是无法找到之前重复的节点，那就会根据implementation rules来匹配找到最优的计划，进一步还要将该节点的subquery匹配transformation rules，一旦有适配的规则就放在OPEN结构中，然后涉及旧的子查询包括引用和参数输入的所有父节点（parent nodes）再去匹配implementation rules，并且传递因为该subquery的转换改进的cost，这个过程就是reanalyzing，如Figure 3的fitler下推（原始->I），会导致重新计算新的代价。最后，父节点再匹配transformation rules，因为可能产生新的计划，这个过程叫rematching，如下图Figure 4经过匹配join结合律（I->II）后产生了新的计划，也是rematching的过程。

Search Strategy and Learning

因为对于一个复杂的查询，OPEN中会有大量的可能得转换，如果能够让一个查询优化在合理的时间范围内，最理想的情况下就是只包含最后优化执行计划的转换，不过这显然是不可能的，所以要选择哪些肯定能减少大量cost的转换。引入了Promise的概念，对于每种转换增加expected cost factor即转换前后的系数，提前去看是否减少cost再决定使用改转换规则。对于像select pushdown这样的设置f < 1，而对于像join 交换律的这种中性的转换f=1。不过EXOUS也无法设定这个因子，因为也不知道具体模型是什么，所以提供了根据执行反馈的方式来计算，有几类计算公式：

还要考虑是否因为后续算子来调整该算子的因子，或者根据已经估算的子查询来减少代价。因为始终无法判断当前计划是否是最优计划，所以EXOUS策略就是一直查找下去，在计算的时候还有去比较之前最好计划的代价 * hill climbing factor，如果cost更低转换的规则才会被使用。hill climbing factor通常被设定为1.05到1.5之间，EXOUS也给出来对于关系型模型hill climbing factor是接近于1的。最后还有一个reanalyzing factor因子，在之前提到的reanalyzing过程，如果新的子查询明显高于之前优化的子查询的cost * reanalyzing factor，就不会浪费时间做reanalyzing了。当然说了这么多，这些参数也都是根据数据模型给定的，因为也是需要执行反馈和学习的。

最后总结下，EXOUS Optimizer Generator最大的贡献就是提出了top-down的优化器生成器框架，解耦了数据模型和搜索策略，拆分了逻辑转换规则及逻辑算子和物理转换规则及物理算子，虽然不容易扩展，但是为后续Cascades优化器奠定了很大的基础。

Volcano其实是一个包含了优化器和执行器设计框架的研究项目，研究背景有两大目标，第一就是抓住可扩展性的框架设计，解决适应日益增大的数据规模和多样的应用场景的数据库系统；第二就是抓住优化（Optimization）和并行（Parallelization）这两个关键技术来解决数据库的性能问题，代替之前的机遇文件系统的工具和技术，可以参考下面两篇文章《Volcano-An Extensible and Parallel Query Evaluation System 》、《The Volcano Optimizer Generator : Extensibility and Efficient Search》。Volcano借鉴了EXODUS、System R和Ingres，主要对EXODUS的问题进行增强和比较。 Sysmtem R也注意到了用Volcano来进行很好的扩展，但是他并没有很好的解决并行可扩展的问题，即扩展性和并行执行相互独立叠加（orthogonality）。

首先看下整体的设计框架，可以看到Volcano的系统设计思想还是要不仅仅基于数据库中使用的。

因为基于关系型数据的系统查询过程都是基于关系代数，所以在可扩展性和面向对象也都是基于关系代数相关技术的，比如定义关系代数算子及其等价变化的规则，再加上合适的实现算法。Volcano优化器定义两类关系代数，逻辑和物理关系代数，优化器负责将代表查询的逻辑关系代数（Logical algebras），转换为等价的物理关系代数（Phsical algebras），即包含具体的算法实现的执行计划。达到这个目标，就需要有一套完整的逻辑关系代数的转换（transformations）和基于代价的（cost based）逻辑关系代数到物理算法的映射方法。Rules也是数据库优化器中被广泛使用的简单而模块化的组件。Volcano的优化器中rules都是相互独立的，会在Search Engine当中合并起来来优化查询。Volcano还提出了多个等价变化的优化计划的映射，可以让Search engine来选择。对于Rules系统采用解析还是编译方式，Volcano也做了解释，虽然解析灵活性强，但是优化通常是CPU敏感型的，所以它还是选择了和EXODUS优化器一样的方式编译方式，这样执行过程非常快，而且增加一个新的Rule对于一个优化器的过程也不会那么快。

总结下，Volcano优化器对于数据库优化器设计实现的人需要的组件：

1）一组逻辑算子；2）带有满足条件判断的关系代数转换的规则集合；3）一组物理算法和enforcers；4）带有满足条件判断的逻辑转物理实现的规则集合；5）抽象数据类型的代价（cost）；6）抽象数据类型的物理属性向量（physical property vector）；8）每种算法或者enforcer的用来判断是否适用于物理属性向量要求的函数（applicability function）；9）每种算法或者enforcer用来估算代价的函数（cost function）；10）每种算子、算法或者enforcer的属性函数。看起来很复杂，但是Volcano Optimizer这个是继System R的Optimizer框架以后在框架上最为突破性的也可能是过去20年内唯一突破性的创新，它也让后续优化器的设计者不至于从零开始。

基础组件拥有后，怎么能让这些组件迅速配合运转起来，那必然是Search Engine了，用来枚举各种可能得plan从而选出最优计划。Volcano优化器目标还是要设计一个通用的优化器，就像我们上面图一样。和EXODUS不同是，采用了动态规划算法而非可能性的完全枚举方式，更具目标性。System R和Starburst也是用动态规划，但是只用在select-projec-join的查询场景。Volcano采用了定向动态规划算法（directed dynamic programming），支持top-down的面向具体目标的控制策略去找到最优的计划，这样的好处是可以支持更多通用的关系代数转换，根据interesting sort order也可以更高效的找到有效的执行计划候选。Search Engine的大体逻辑如下：

对比Starburst优化器把关系代数转换（Transformation）放在Rewrite部分，Volcano优化器只是把这个转换当成是多一种选择放在一个框架下。Volcano优化器同样适用了cost limit用来做branch-and-bound优化剪枝，由于这个cost limit回传递到子表达式中，所以即使去穷举搜索，也会找到相对好的计划。

这里也稍微提下支持Volcano的执行器的创新点：1）Volcano执行器提出来query execution的算子里面包含open，next， close的范式。

2）提出两个重要算子chose plan operator来解决由于变化参数的问题造成的动态计划选择，使用exchange operator来解决数据库查询执行时候的并发问题。

最后我们说说Volcano优化器怎么改进EXODUS优化器：

1）Volcano的逻辑表达式和物理表达式是分离的；
2）物理属性并不像EXODU那样随意处理；
3）Volcano的算法是自顶向下的，子表达式只需要在需要的时候优化就可以，而EXODUS是都要是转换和估算代价的；
4）cost定义的是抽象的类型，可以是简单的数字，也可以是消耗的时间或者包含CPU时间和I/O次数的结构体，甚至是一个函数；
5）搜索策略非常灵活，包含了物理属性（Physical Properties）、分支定界剪枝（Branch-and-Bound Pruning）和启发式指引（Heursitic Guidance）。

现在来到了我们最重要的Cascades优化器了，该优化器是Graefe基于EXODUS和Volcano Optimizer generator的改进版，这次标题有个变化，不再是optimizer generator而是明确了针对Query Optimization的框架，笔者主要认为Framework是因为Cascades基于类的实现（利用C++语言特性）而不再基于解析式的函数调用方式。由于很多商业优化器都是基于Cascades的思想，所以本章篇幅会多很多。

EXODUS的主要贡献在于设计了新的基于对规则、逻辑和物理关系代数动态代码产生的一套优化器的生成器架构，将优化器拆分模块化的组件和DBI定义的接口，而Volcano主要是改进了的是基于动态规划（Dynamic Programing）和记忆性（Memorization）的更加高效的搜索引擎（Search Engine），而且Volcano明确区分了逻辑优化和物理优化阶段，最要命的是在逻辑优化时会根据关系代数生成所有可能得逻辑算子，再进行物理算子的优化，这样显然带来不必要的计算和搜索空间。

首先，Cascades从框架上进行的重大的改进，全部用对象（Objects）+任务（Tasks）的方式来代替之前的函数调用方式，这样可以利用Graph来标明他们之间的拓扑和依赖关系，也可以更好的LIFO堆栈结构进行管理，更容易的根据启发式指引（Heuristic guidance）方式进行排序和调整，也可以进行并行优化带来可能。下图就是基于任务的优化器的search算法框架和所包含的Tasks类型，实线箭头代表哪种类型任务调用其他任务，虚线箭头代表和输入相关的调用。从调用optimize()拷贝初始查询关系表达式树到MEMO中后，不断的触发优化的过程，从而分解到更多的子表达式树优化上。整个优化过程采用了动态规划和记忆化的算法。

• Group：逻辑等价类，其中包含具有相同逻辑输出属性的expr的集合。
• Expression：关系代数表达式，包含算子
• Optimization goal：引用了Volcano Optimizer generator的概念，包括了cost limit，必要和排除的物理属性（Output Physical Properties）。
• Optimize Group：根据Optimization goal，对一个Group进行优化，即对Group中的每个Expression进行优化，找到最佳的plan。
• Optimize Expression：对一个Expression进行优化，使用规则对Expression应用优化规则（Apply Rule），所有rules都应用完后，寻找Group中代价最小的Expression。
• Explore Group & Explore Expression：用于优化Expression可能产生新的Group和Expression，Explore过程是对逻辑算子进行等价变化。这个步骤相比Volcano是全新的概念，因为在Volcano中是采用逻辑和物理转换两个阶段的方式。
• Apply Rule：应用具体的优化规则，从逻辑Expression转换到等价的逻辑表达式，或者从逻辑表达式转换为物理Expression
• Optimize Input：对Expression代价进行估算，这是一个自底向上的过程，需要递归地计算子节点的统计信息和代价，再计算当前节点，并且尽可能能进行剪枝和保留新的cost limit。
• MEMO：搜索空间管理，它包含初始查询关系表达式树和所有等效的逻辑和物理表达式，以及负责去重复的结构。

流程从论文里找不到，所以借用了其他论文的描述：

optimize(qry, guidance){
   for i=1 to pass_count do{
        push "opt_group" task for the root of the query
        while task_list is not empty
            pop task
            perform task
   }
   return plan
}

第二，Cascades采用了统一的探索方式（Explore），不在区分先逻辑表达式和物理表达式阶段，而采取了按需探索的方式，避免了Volcano要再第一个阶段穷尽的产生所有的逻辑表达式。explore的group/expression一定是匹配task要求的pattern后，才按需应用transformation产生所有的表达式或等价转换。另外，Cascades有启发式指引和防重复apply rules的pattern memory结构，Cascades是比Volcano一定高效的，只有在最坏的情况下才会和Volcano的搜索策略一样。

第三，明确定义数据类接口和用户接口来改进可扩展性和交互接口。

Operators & Arguments

class OP-ARG，不严格分为logical/physical，只是描述一种特定的操作，感觉上是用来描述每种expr所对应特性的信息载体，包含is-logical和is-physical方法，有些算子比如类似starburst的”non-terminals“既不是逻辑算子也不是物理算子，Sargable predicates算子即是逻辑的也是物理的。除了上述两个函数，还必须包括opt-cutoff方法，用来做Cascades中最重要的步骤指定优化的步骤（Ordering of moves by promise）。还有些方法是专门为逻辑算子的，比如包括重复表达式查找、查找和更新逻辑属性（schema/selectivity/output size）。最后，还要根据pattern memory来决定expolaration task的步骤。同样还有一些方法是适用于物理算子的，比如展示算子的输出属性，计算和检查算子的cost的函数（local cost自身的代价，整个子plan的cost包括输入、物理属性和自身代价，以及确定不超过cost limit并设定新的cost limit）。最后还有一个函数叫input-reqd-prop映射了算子的cost limit，required和excluded的物理属性。

Logical & Physical Properties/Costs

class COST，其他类的输入输出，比如class OP-ARG，唯一的方法是比较。

class SYNTH-LOG-PROP，逻辑算子属性，包括了hash结构来快速获取和去重表达式。

class SYNTH-PHYS-PROP，物理算子属性，没有任何方法。

class REQD-PHYS-PROP，要求的物理算子属性，唯一的方法是判断一个物理属性实例是否包含要求的物理算子属性，比如结果是按A,B,C排序的，要求的排序属性只有A,B，比较的结果返回MORE，默认返回结果是UNDEFINED。

EXPRESSION TREES

class EXPR，一个树结构，包含了一个算子节点及其输入的节点，输入节点必须是和该算子的参数对应。方法包括了提取算子或者该算子的输入，以及能够递归的匹配方法。

multi-EXPR，为了减少内存的使用和充分利用Memoization的技术，Expression通过group形式来描述，可以根据下图了解下：

Search Guidance

class GUIDANCE，用于heuristic控制规则的适用情况和步骤，可以大大缩减最优plan的产生时间，但是如果错误的guidance也会造成很大偏差。比如一些具有交换的规则（JOIN 交换律）只是apply一次，叫ONCE-GUIDANCE/ONCE-RULE。有一些研究者专门为这些RULES划分了模块。

PATTERN MEMORY

pattern memory是每个group一个，用来避免相同pattern在一个group被重复探索两次。最复杂的是合并两个group的pattern memory，比如已经在一个表达式中发生过转换的pattern。

RULE

class RULE，Cascades中最重要的类，可以在运行时态的时候动态创建，而前面提到的EXODUS和Volcano是区分了逻辑和物理的规则，Cascades是合并到一起了，通过is-logical和is-physical方法来判断。RULE提供名字、前序模式（before pattern）和等价结果(subsitutes)，patterns和subsitutes都是表达式的树结构，而且支持任意复杂的形式，而EXODUS和Volcano只能支持一个物理算子，不过仍然有个限制是，top的subsitute算子必须是逻辑算子。

RULE中包含两类重要函数promise和condition。两个promise函数分别为optmization task和explore task提供权重信息的，告诉他们这个RULE可能非常重要，对于穷举查找，所有的promise函数返回1.0，<=0的是可能阻止优化器进一步优化下去，默认implementation rule的promise=2，而transformation rule的promise=1。condition函数是探索和产生新的表达式前，判断该RULE是否适用的。还有一些小函数，比如rule-type，来判断是否是simple rule还是function rule，top-match函数判断是否和在search memory中的top的算子能够匹配，opt-cases函数物理算子由于不同物理属性被优化的频次，一般每个优化算1次，当然也有特例，比如对于条件（R.A=S.A and R.B=S.B）产生的merge sort，其实可以按照A，B排序也可以按照B，A排序，这两个sort orders算一次优化。剩下还有一些函数是为了optimization和exploration的tasks生成GUIDANCE的opt-guidance、expl-guidance、input-opt-guidance、input-expl-guidance。

这里单独介绍一类重要的RULES，enforcer rules，用来插入物理属性的算子，确保输出的物理属性。比如merge-sort-join算子的输入必须是已经排序的，所以一个sort enforcer rule可能会插入sort算子到输入，因此sort算子的input-reqd-prop函数必须可以设置排除sort属性，避免该输入的输出排序属性已经满足排序要求的计划插入sort算子。

class FUNCTION-RULE，在一些情况，可能只用一个函数就可以进行表达式的等价转换，而非设计和控制一堆rules set去做同样的转换，所以Cascades支持该类型的RULE，当整个表达式树满足pattern时，可以重复调用其interator函数去创建所有的等价转换。比如分解一个复杂的join谓词到左右输入，而输入又是确定的。极端的例子是几个函数就可以完成所有的表达式转换，虽然是破坏了Cascades的设计框架。

总结下Cascades做了巨大的改进：

• Rules(transformation rules/implementation rules)实现为对象。
• 用Group这个对象来描述logical等价类，也就是logical expression。
• 可以扩展针对schema/query 特性的rules
• Enforcer的添加也通过rules来描述
• Transformation rules通过pattern来匹配并判断是否可以apply
• Predicates成为了独立的operator，而不再是operator arguments，这样可以做predicate placement这样的等价变换
• 通过在apply transformation rule时，对下层group按需做exploration，等于在做等价变化的过程，按需增量的进行了下层算子的逻辑/物理变换，这样transformation/implementation rules的apply就交错了起来，而不是Volcano paper中使用的先做transformation再考虑implementation的二阶段模式。
• Search过程中引入guidance的概念，可以指导rules的应用策略。
• Rules可以有promise，表示其优先级。
• 将Search流程划分为多个阶段并抽象出task的概念，task是优化过程中的调度主体，不同task之间具有依赖关系形成DAG（有向无环图），这样可以做并行Search。

当然更为成功是，其设计思想和框架被商业产品Microsoft SQL Server和Tandem's NonStop SQL所证明。

前面介绍Cascades Optimizer Framework比较详细，Columbia Optimizer是基于它的改进，所以这里会简短介绍不同点和相关的结构。下图为该优化器的架构：

优化器输入改进

从上图可以看到Optimizer的输入Query、Catalog和Cost Model都是基于Text File的，也是Columbia优化器宣称的一个重要改进，而非采用hard-coded的方式。

Query LISP语言描述，直接用文本描述了Query的逻辑表达式：

Columbia的输入Catalog Info的文本表达：

Columbia的输入Cost文本表达：

这里我们也观察下Columbia Optimizer的不同optimal的输出物理表达式：

Search Engine改进

上图为Search的架构，Search Space Struture. SSP（call memo在Cascades中）也都是采用了Dynamic Programming和Memoization的技术，在SSP中，包含了GROUP数组来分组逻辑等价物，SSP包含一个root GROUP，每个GROUP都包含ID及一组表达式multi-EXPR，每组GROUP不是root就是其他的multi-EXPR的inputs。SSP包含两个函数CopyIn，负责拷贝新的等价的multi-EXPR或者新的GROUP及其multi-EXPR，CopyOut负责优化完成后输出最优的计划。SSP中的去重仍然采用了static hashing的方式，但是Columbia Optimizer采用了lookup2算法来增强搜索性能。

GROUP改进

• The Lower Bound of a Group

在top-down的优化中，具体到某个group时，会有对应的search context（cascades中的optimization goal)，context中包含2个部分：[required physical property , cost limit(cost upper bound)]，也就是在向下搜索时，要求当前group输出的物理属性，同时整个子计划的代价要小于cost上界。子计划的代价是当前group的physical m-expr代价 + 各个input group中最优physical m-expr的代价。有没有可能在优化input group之前，就能判断其代价已经过大了，从而实现pruning呢？Columbia为每个group计算一个cost lower bound，并保证group枚举的任一physical m-expr对应的子plan，其cost(m-expr) > lower bound。这个lower bound是基于group的logical property计算的，和具体算子实现方式无关，在group创建时计算完成。下图为伪代码，大家可以看论文来更加细致的理解。

• Separation of logical and physical multi-expression

结构上拆分逻辑算子表达式和物理算子表达式列表，主要为了改进binding带来的代价，另外对于物理表达式只需要计算物理属性和计算代价，而逻辑表达式要看是否rules可以被使用，使用后才会被optmize，所以从执行效率上还是带来了很大的改进。

• Better Structure for Winners

该优化仍然是基于memoization技术的扩展，由于GROUP会基于不同Search context反复优化，因此每个context应该都会找到一个最优plan，这些Plan就保存在GROUP的Winners链表中，以备后续复用。Columbia主要简化了Winner的结构，只包含[当前group中最优的(physical) m-expr + 最优plan cost + required physical property]的数组，不包含连接下一个winner的指针。在基于当前search context搜索过程中得到的最优解（临时）也会保存在winner结构中。此外，如果最后无法找到满足要求的plan，这个winner对象仍然会创建出来，只不过其中的m-expr是null pointer，表示无法找到context的最优解，这也是一种结果，可以保存下来被复用。

EXPRESSION改进

Columbia对Cacades的表达式做了减法（1.67:1），节省了巨大的内存。

RULE改进

Columbia主要继承了Cacades的RULE的设计，但是从binding算法和处理enforcers有些改进。首先减少了binding的state，降低了CPU使用率，三个状态的Binding函数BINDERY::advance()更加高效。

其次，Columbia弃用了excluded 物理属性，因为增加了复杂度和内存，并且增加了RuleMask bitmap结构避免enforcer被重用。最后，Columbia中的enforcer是不带参数的物理算子属性，相对于之前Cacades包含参数的方式，如QSORT算子包含排序的列属性<A.X, B.Y>和排序方式ASC/DESC，一旦enforcer符合，会产生新的表达式QSORT(<A.X, B.Y>)，也会保存到GROUP中，因此造成了同名多参数的表达式都存放在GROUP中。有RuleMask做辅助，物理属性被应用后不会再次被重复应用，有新的物理属性被应用后计算cost也会基于叠加的代价进行计算，如果带有物理属性的表达式成为winner后，也会相应和普通表达式一样保留到winner的结构中。在最优plan确定后，Columbia会多一个步骤去确定具体的enforcer算子的参数。

Tasks -- Searching Algorithm改进

Columbia实现了一个PTasks来处理未处理的tasks。

class TASK
{
  friend class PTASKS;
private :
  TASK        * next;         // Used by class PTASK
protected :
  int  ContextID;      // Index to CONT::vc, the shared set of contexts
  int      ParentTaskNo;   // The task which created me   
public :
  virtual void perform ()=0;  //TaskNo is current task number, which will
}; // TASK
?
class PTASKS
{
private :
  TASK        * first;        // anchor of PTASKS stack
public :
  void push (TASK * task);
  //##ModelId=3B0C085D016B
  TASK * pop ();
}; // PTASKS

而优化器的调用入口如下：

void SSP::optimize()
{ 
  //Create initial context, with no requested properties, infinite upper bound,
  // zero lower bound, not yet done.  Later this may be specified by user.
  PTasks.push (new O_GROUP (RootGID, 0, 0));
    
  // main loop of optimization
  // while there are tasks undone, do one
  while (! PTasks.empty ())
{
    TaskNo ++;
                TASK * NextTask=PTasks.pop ();
    NextTask -> perform ();
        }
}// SSP::optimize()

TASK分为五种，相对于Cacades提到的tasks，group optimization (O_GROUP), group exploration (E_GROUP)，expression optimization (O_EXPR)， input optimization (O_INPUTS), rule application (APPLY_RULE)，下图为他们之间的调用关系图，这里只介绍改进的task。

O_GROUP会产生O_EXPR和O_INPUTS，如果优化成功，会产生winner的plan，否则会保存NULL plan。O_GROUP调用在两种情况，第一种是初始状况，只有一个逻辑表达式情况，另外一种情况是不同的物理属性的搜索上下文。Cacades在group optimization (O_GROUP)阶段是不处理物理算子表达式，意味着如果group optimization在不同物理属性上下文重新搜索时，会重新被生成和计算代价，而逻辑算子表达式和物理算子表达式在一个lists中，该阶段还要忽略所有之前生成的物理算子表达式，因此改进了性能。

E_GROUP会产生新的GROUP及其逻辑算子，比如JOIN的交换律RULE。在Cascades中，group exploration (E_GROUP)会生成另一个task E_EXPR来产生multi-expression，在Columbia直接合并E_EXPR到O_EXPR了，只是加了一个flag（optimizing/exploring）来标志不同的功能。

O_INPUTS中改进了Pruning技术，会在下面讲到。

Pruning Techniques改进

Lower Bound Group Pruning：因为Top-down optimizers在计算物理代价时非常耗时，使用已经优化的upper bound优化是显而易见的，但是其实还是有些中间的upper bounds在整个优化过程中是不需要的，因此Columbia使用了逻辑属性来进行提前的group剪枝。下图为Lower Bound Group Pruning的算法。

下图对比了使用Lower Bound Group Pruning带来的巨大的剪枝空间的优化。

Global Epsilon Pruning：因为优化器只能获得相对优的执行计划，而可能非最优，那通过这个全局的变量来控制搜索的时间，只要找到小于该值的plan，即不再继续进行搜索。

在O_INPUTS中通过Starburst/Pruning/CuCardPruning/GlobepsPruning 4个标记设置剪枝策略：

1. Starburst，无Pruning技术被采用。
2. Pruning就是常规的top-down branch and bounding，用当前累计cost和cost limit比对
3. CuCardPruning表示开启lower bound pruning，其和Pruning的区别是对尚未优化的group i，InputCost[i]不是0而是group创建时计算的lower bound cost
4. GlobepsPruning 在完成优化时进行一次判断，如果认为足够优，直接记为winner。

总结下Columbia Optimizer的几个针对Cascades Optimizer Framework的改进点，1）更加解耦优化器框架和DBI的标准；2）充分利用C++面向对象的virtual method实现扩展性；3）频繁分配和销毁对象产生的性能问题；4）top-down的剪枝技术的改进，简单来说就是更高效的Cascades Optimizer Framework，而且有开源的代码可以借鉴，比只读论文要清晰。

从SQL Server 7.0开始，Microsoft重构了基于Cascades Optimizer Framework架构的优化器。除了SQL Server之外的最重要的几个衍生产品也继续采用了该扩展架构：为并行执行而优化的结构化计算(SCOPE-Structured Computations Optimized for Parallel Execution是Microsoft的数据分析平台；SQL Server并行数据仓库(PDW-Parallel Data Warehouse)；以及SQL Server PDW V2支持使用标准SQL管理和访问在Hadoop集群上的数据的产品Polybase。

本文由于篇幅问题，只会简要介绍下PDW的优化器，下图是PDW的整体架构，它也是利用了现有SQL Server Optimizer改造的MPP架构。

其主要思路如下：

• 通过Shell database提供了分布式表的metadata信息和各个计算节点聚合的统计信息，对应用提供统一的入口和系统。
• 通过Shell database可以充分利用已有的SQL Server强大的优化器进生成各种可选的执行计划（MEMO）。
• 直接将已生成的可选执行计划增加数据移动的操作（data movement operations），再基于代价来进行评估选出最优的分布式执行计划。

由于SQL Server优化器的串行计划无法生成最优计划，原因是由于原优化器并不是针对MPP，对于数据分布无感知， 而PDW必须考虑JOIN/GROUP BY等算子在MPP下如何进行重新分布后的最优plan，因此，通过XML Generator组件把整个串行计划的memo都传递给PDW的优化器。下图可以看到，Group 1-4是串行计划的memo，而group 5-6等是扩展后的MPP的memo。

PDW采用了bottom-up的搜索策略（其实PDW也是可以top-down的策略，只是搜索空间因为DMS会巨大），同时借鉴了System R的Interesting properties，包括(a) 在join谓词中的列和 (b) group-by列。这里需要强调下不同点，生成的最佳物理执行计划，最终还要生成DPlan。DPlan选择了和Greenplum等数据库不同的方式，就是需要QRel的组件来将在计算节点执行的计划反编译为SQL，同时结果是需要缓存到Temp table，再通过DMS组件来进行重分布或者复制后，进行下一步的执行，有兴趣大家可以看下论文中关于Q20的DPlan内容。

总结PDW的架构，给非MPP数据库提供了一种全新的设计思路，就是利用已有的强大的Optimizer通过增加Control Node+Shell database的机制和Data Movement Service模块来解决分布式MPP的问题，对外提供统一的入口和系统。

MemSQL是一个基于内存的云原生分布式数据库，更好的支持实时交易和分析负载，更高的并发性和极致的可扩展性。MemSQL提供了统一数据库引擎，通过in-memory的行存和一个disk-back列存存储数据，提供极致HTAP的能力。这里介绍主要是因为基于分布式内存数据库，可以学习其中的一些针对HTAP负载的创新增强。

MemSQL的优化器因为是针对一个创新型的引擎，包括memory-optimized的lockfree的skip-lists索引、一个同时包含columnstore引擎和实时流式分析，并且由于基于内存，优化的budget非常有限，因此有很多独特的设计。MemSQL的Optimizer是模块化的，分为三个主要部分：

• Rewriter，主要做SQL-to-SQL的重写，根据workload的特点，选择基于heurstic方式或者基于分布式的cost进行改写，优化器可以智能的在运用一些bottom-up的优化中进行top-down的优化，交织两种方式来充分利用两者的好处。
• Enumerator，最重要的模块，主要基于Cost based决定分布式Join的顺序和数据移动方式，也同时包括本地Join顺序和访问方式的选择。Rewriter模块也会在query transformation的阶段调用它，也就是我们熟知的cost-based query rewrite。
• Planner，该模块复杂转换逻辑的执行计划，变成一系列的分布式查询和数据移动的操作。定义了SQL扩展RemoteTables和ResultTables，使用SQL-like的语法和接口对数据进行操作和移动，和PDW非常类似，例如：

====Input SQL, customer distributed by custkey and orders by o_orderkey
SELECT c_custkey, o_orderdate
FROM orders, customer
WHERE o_custkey=c_custkey
 AND o_totalprice < 1000;===> DQEP Example
(1) CREATE RESULT TABLE r0
 PARTITION BY (o_custkey)
 AS
 SELECT orders.o_orderdate as o_orderdate,
 orders.o_custkey as o_custkey
 FROM orders
 WHERE orders.o_totalprices < 1000;
 
(2) SELECT customer.c_custkey as c_custkey,
 r0.o_orderdate as o_orderdate
 FROM REMOTE(r0(p)) JOIN customer
 WHERE r0.o_custkey=customer.c_custkey 

从模块设计也可以看出，MemSQL有其独特的创新：

基于cost-base的query rewrite

MemSQL优化器的Rewriter创新性的通过Enumerator组件，能够基于分布式代价进行查询重写。MemSQL本身同时支持Heuristic，比如类似于简单的Column Elimination转换，和Cost-based，如Group-By Pushdown。还有一些特殊的如Sub-Query Merging，大部分情况用的Heuristic，但是对于几个大的数据表视图做JOIN，如snowstorm-like的有多个fact table的SQL，merge后会造成Enumerator的大量计算，因此这种情况MemSQL提供Heuristic方式去探测，来决定是否merge还是采用bushy join方式。还有一些转换是交错进行的，Outer Join转Inner Join和Predicate pushdown转换规则。接下来我们重点看下Cost-based的例子：

CREATE TABLE T1 (a int, b int, shard key (b))
CREATE TABLE T2 (a int, b int, shard key (a),
 unique key (a))====初始SQL
Q1: SELECT sum(T1.b) AS s FROM T1, T2
 WHERE T1.a=T2.a
 GROUP BY T1.a, T1.b====可改写的形式
Q2: SELECT V.s from T2,
 (SELECT a,
 sum(b) as s
 FROM T1
 GROUP BY T1.a, T1.b
 ) V
 WHERE V.a=T2.a;

对于PDW，优势就是在SQL改写时也能充分利用cost model，而PDW的转换因为使用了shell database，因此就是single node的cost model。

Bushy Plan Heuristics

对于大量表做所有可能shape的join tree enumeration，成本是很高的，考虑到MemSQL还要枚举分布形态，search space就又多了一个维度，因此从设计决策上，在做Cost base join ordering时，它只枚举left-deep join tree。

但由于定位HTAP，MemSQL可能面临一些复杂的分析查询，其中包含一些星型/雪花模型的数query，而这种query对于bushy join的依赖是比较强的，因此MemSQL的设计决策是，在rewrite期间，基于heuristic检测可以做bushy join的pattern，并对每种潜在可能进行rewrite+costing，然后基于cost比较各种候选bushy plan的最优性。

为了是left-deep的enumerator可以枚举bushy tree，需要将bushy的部分rewrite为derived table，这样enumerator就会对各个query block各自优化，再join，在每个bushy的内部，仍然是left-deep的。

总结下MemSQL的优化器，创新性的增加了基于cost-based的查询优化转换，充分考虑到了分布式cost model，另外区别于PDW先生成串行执行计划或者memo，再进行扩展，直接针对分布式的内存分布和分布式cost进行优化，能够生成更加有效的分布式计划。对于JOIN的enumeration过程，采用了heuristic方式发现star和snowlfake的形态，大大加速了优化的有效性和时间。

Orca是Pivatol开发的大数据模块化的MPP查询优化器，目前被用于Pivotal Greenplum 数据库和Pivotal HAWQ中。Orca 的架构比较独特，它设计之初有下面几点考虑：

• Modularity，Orca使用可扩展的抽象的元数据和系统描述，不再像传统优化器那样局限于特定的主机系统。相反，它可以通过其 Metadata Provider SDK 支持的插件快速移植到其他数据管理系统。
• Extensibility，Orca框架可以扩展新的operator/cost model/property/rules，避免了多阶段优化的陷阱，即将某些优化是事后才处理的，导致难以扩展。
• Multi-core ready，Orca实现了一个高效的多核感知的调度程序，该调度程序将优化子任务分布在多个核上，以加快优化过程，也就是支持并行优化。
• Verifiability，Orca提供了一套可以验证性能和正确性的工具。
• Performance，Orca在许多情况下提供了10倍到1000倍的查询加速。

下面来看下Orca和Database System如何交互

可以看出来，Orca为了可以支持任意数据库系统，提供了DXL系列的接口来进行对接，反过来讲，如果想接入Orca优化器，需要实现Query2DXL、MD Provider和DXL2Plan三个模块的实现。

• Query2DXL把parse tree转成DXL（CTranslatorQueryToDXL::TranslateSelectQueryToDXL）；
• DXL2Plan把DXL转成可执行的Plan（CTranslatorDXLToPlStmt::GetPlannedStmtFromDXL）；
• MD provider把metadata转成DXL（CMDProviderRelcache::GetMDObj）；

Orca本身是对接的PG系的数据库系统比较容易，很多公司也在尝试去对标其他数据库系统，大家也可以看看华为如何把Orca整合到MySQL中《Integrating the Orca Optimizer into MySQL》。下面我们看看，Orca本身的架构。

优化框架区别

我们这里不会讲更多细节，主要看看Orca有什么特别的不同，比如Metadata Cache，由于Orca独立于数据库系统，而元数据不经常变更，ORCA内部维护了一份对应的缓存，GPOS模块提供基础组件：内存管理，状态机，线程通信，异常处理，文件IO等。

优化阶段区别

Orca是采用Cascades架构但多阶段优化的方式，分为Exploration（逻辑等价表达式转换）、Statistics Derivation（统计信息的推导）、Implementation（物理等价表达式转换）、Optimization（根据优化目标物理属性、CostLimit等进行cost based优化）。其中Statistics Derivation在Exploration过程后，会进行统计信息推导，引入了针对特定算子如JOIN类的统计承诺（Promise），基本原理是，加入条件的数量越多，估计误差的传播和放大机会就越大。

针对例子”SELECT T1.a FROM T1, T2 WHERE T1.a=T2.b ORDER BY T1.a“ ，T1数据根据T1.a，T2数据根据T2.a分布在各个计算节点上，Optimization的整个过程可以用下面图来解析，假设目前已经进行了Exploration、Statistics Derivation和Implementation的MEMO。

由于Orca是基于MPP的优化器，必须要进行数据汇聚，并且语句中包含ORDER BY T1.a输出要求，因此优化目标就是req #1：{Singleton，T1.a}，产生两个alternative的物理计划(c)和(d)，最后通过cost方式确定最后的best plan。

元数据交换

下图显示了Orca如何与不同的后端系统交换元数据。在查询优化过程中，Orca访问的所有元数据对象都固定在内存中的缓存中，并在优化完成或引发错误时取消固定。所有对元数据对象的访问都通过MD Accessor完成，该访问器可跟踪优化会话中正在访问的对象，并确保在不再需要它们时将其释放。如果请求的元数据对象尚未在缓存中，则MD Accessor还负责透明地从外部MD Provider提取元数据。服务于不同优化会话的不同MD访问器可能具有用于获取元数据的不同外部MD提供程序。

并行优化

ORCA支持多线程优化，提供了optimization job调度器，每个优化路径的多个阶段拆分成了不同的job类似于Cacades中的task，包括下面类型：

• Exp(g): 为Group生成所有等价的逻辑表达式。
• Exp(gexpr): 为Group其中一个gexpr生成等价的逻辑表达式。
• Imp(g): 为Group生成所有等价的物理表达式。
• Imp(gexpr): 为Group其中一个gexpr生成等价的物理表达式。
• Opt(g, req): 对于优化目标请求req，输出以该Group为根输出最小估算代价的执行计划。
• Opt(gexpr, req): 对于优化目标请求req，输出以该Group中gexpr为根输出最小估算代价的执行计划。
• Xform(gexpr, t) ：对GROUP中的表达式gexpr运用rule进行等价转换。

Job放入到queue中后，多线程从queue中消费job，job之间维护前后的依赖关系，没有依赖关系可以并行。

验证和测试工具

Orca最可圈可点的就是提供了验证和迭代plan的工具，DB2也有相关的工具叫complier simulation tools，可以用户的表定义、统计信息收集回来，然后不真正执行来本地模拟优化器的问题。

AMPERe，用于复现和调试ORCA，而不需登录到用户的DB环境。 当ORCA内部出现异常，或者计划不符合预期时，会自动把相关元数据，query，优化配置序列成xml，dump到文件。 后续可以直接回放这个xml，而不需要进入到DB中。另外，AMPERe还可用于建立测试框架，指定特定的dump文件和期望的plan即可。

TAQO，当修复bug或者新增功能后，如何保证产生的计划性能没有回退。 TAQO用于测试ORCA的cost model的精准度，比如cost值高的计划理论上有更长的执行时间。

总结下Orca，作为Postgresql届的大神级的优化器，注定为大数据平台下基于C/C++的MPP数据库提供了强有力的工具，也提升了巨大的性能，就像Calcite在Java系大数据平台的优化器一样，被广为运用，最重要的就是工程实现方面非常完美，不过也有一些缺点就是需要能支持一些guidance来指引优化器迅速能产生相对”optimial“的计划。

Apache Calcite的优化器是为数不多的开源Volcano/Cascades 查询优化器实现之一，最早脱胎于 Hive 的优化器，后来也被 Java系如Apache Hive, Apache Storm, Apache Flink, Druid和MapD等大数据项目青睐，连各大厂商的云原生大数据平台和分布式数据库都利用Calcite优化器进行增强。和Orca不一样，Apache Calcite系统基本上一个独立的查询执行引擎，利用了联邦技术连接不同的异构数据源，提供了插件式的优化器。

不过我们这里只提下Apache Calcite优化器部分。Apache Calcite 中原来的 Volcano Planner 并非对论文的标准实现。2020 年 4 月阿里云 MaxCompute（ODPS）团队提出了 CALCITE-3916: Support cascades style top-down driven rule apply，即新增一个真正意义上的 top-down 优化器，之后又重构了一版 #1991，将同样的功能实现在了 VolcanoPlanner 内部并提供了 TOPDOWN_OPT 选项用于启用或关闭。该功能最终在 2020 年 7 月完成进入主分支。因为实现基本按照标准论文的方式，因此，本来列出其中命名的对照。

因此，不难想象其整个优化器流程如下：

总结下Calcite的优化器，新引入的 top-down 优化器实现了真正的自顶向下搜索，实现更接近Columbia论文中的描述，实现了lower-bound pruning节约优化时间，同时也改进 physical properties相关的优化性能，成为最简单易懂，受欢迎实用的优化器。

由于现在新型数据库越来越多，但看起来，后续的很多数据库都是依赖于巨人的肩膀结合实际的用户场景地位，进行创新的，这里就不在一一介绍，可能后续会再加入一些非常典型。那未来到底数据库如何走其实是值得我们这些多年从事数据库内核的同学一些思考。云计算给了数据库二次创新的土壤，PolarDB系的云原生数据库，其实也一直在探索，如何能够大大增强早期开源数据库中的优化器，如何能够更好的支持HTAP架构及针对分层数据存储的混合计算体系，如何更好支持存计分离&计算下推的云原生数据库架构体系，如何通过执行反馈和AI技术能够提供数据库自治等等，都值得我们探索。最后，文章比较长，有些论文细节和实现了解不够细致，欢迎交流和帮助改进。

• 1970, A Relational Model of Data for Large Shared Data Banks
• 1971, A DATA BASE SUBLANGUAGE FOUNDED ON THE RELATIONAL CALCULUS
• 1976, The Design and Implementation of Ingres
• 1976, Decomposition A Strategy for Query Processing
• 1976, System R: relational approach to database management
• 1979, Access Path Selection in a Relational Database Management System
• 1979, Query Processing in Main Memory Database Management Systems
• 1982, On optimizing an SQL-like nested query
• 1986, The Architecture of the EXODUS Extensible DBMS
• 1987, The EXODUS Optimizer Generator
• 1988, Grammar-like Functional Rules for Representing Query Optimization Alternatives
• 1992, Extensible Rule Based Query Rewrite Optimizations in Starburst
• 1993, The Volcano Optimizer Generator- Extensibility and Efficient Search
• 1994, Volcano-An Extensible and Parallel Query Evaluation System
• 1994, Implementation of Magic-sets in a relational Database System
• 1995, The Cascades Framework for Query Optimization
• 1998, An Overview of Query Optimization in Relational Systems
• 1998, EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER
• 2000, An Overview of Query Optimization in Relational Systems
• 2001, Exploiting Upper and Lower Bounds in Top-Down Query Optimization
• 2006, Cost-Based Query Transformation in Oracle
• 2009, Enhanced Subquery Optimizer in Oracle
• 2012, Query Optimization in Microsoft SQL Server PDW
• 2014, Orca: A Modular Query Optimizer Architecture for Big Data
• 2016, The MemSQL Query Optimizer: A modern optimizer for real-time analytics in a distributed database
• 2018, Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources
• 2022, Integrating the Orca Optimizer into MySQL

• Relational algebra
• CMU 15721 courses
• 优化器技术论文学习
• The history of System R
• Calcite 中新增的 Top-down 优化器
• 深入浅出GPORCA 优化器Transform流程
• 数据库内核基于代价的优化器引擎
• The Volcano/Cascades Optimizer