数据库挖矿系列 - 优化器设计探索穿越之旅
作者：王晨 阿里云数据库产品团队
前言
引用来自百度百科的话：在数据库技术发展历史上，1970 年是发生伟大转折的一年，因为这一年的 6 月，IBM 的圣约瑟研究实验室的高级研究员 Edgar Frank Codd 在 Communications of ACM 上发表了《A Relational Model of Data for Large Shared Data Banks》[1]。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，我们可以感受下两种语言的不同：
QUEL：
SQL：
了解这段小历史和优化器什么关系呢？就像我们设计系统一样，首先我们的目标是为了什么？解决什么样的客户问题？我们现在很容易想到数据库系统包括交互语言，完美的优化器，高效的执行器，稳定安全的存储等等。而在当时，如何定义数据关系模型及其运算和建立简单灵活的交互式语言将成为数据库软件当时发展方向的最重要的一步。
优化器设计探索
那么既然模型和语言都已经定义了，那就可以回到我们的主题上了，如何能够高效的设计一套系统，高效的完成输入语言的要求？那么数据库优化器就成为数据库最重要的组件之一。有语言就有 parser，有模型定义就需要有语义解析。通过两个重要模块后，我们就形成了我们需要的程序代码可以识别，并且可以做关系代数转换的关系代数结构（Init Logical Plan），即优化器的输入数据结构。SQL 是给人看的，Init Logical Plan 是给优化器看的。优化器就是找到代价“最优”的执行计划。
为什么“最优”带引号，首先记住一点，通常认为找到最优计划是 NP-hard 的问题，没有任何优化器能够产生出真正的最优执行计划，为什么呢？
通过估算的技术来猜测最优计划的代价
通过启发式来限制计划的搜索空间
优化器模块
上面优化器的通用架构图[28]应该是传统优化器的架构图，我们这里重点讲的是从初始逻辑计划（步骤 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》[15]大家可以参考下，IBM 喜欢用 Magic 来解释 Heuristic 方法，另外 Oracle 对于子查询的几篇论文也是非常有趣《Enhanced Subquery Optimizer in Oracle》[21]。
物理计划是由逻辑计划生成的（不一定是 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 Optimizer
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。Ingre 的优化器框架简单可以表示为下图[3]：
Ingres 的优化器提出了基于 heuristic greedy 方式的 Decomposition 的技术，其设计目标需要满足：
无笛卡尔积产生：结果集合是靠组装一片片小的集合而不是直接去由笛卡尔积产生。
无几何增长: 扫描的元组尽可能的保持很少，大多数查询 SQL 都远小于表的 cardinality。
下面通过一个简单例子描述 Decomposition 的两个步骤 Decompose into single-value queries 和 Substitute the values from queries，假设：
可以看到在 Q 中的 Parts 被拆解和替换成 Q1 和 Q->Q'，也可以用右图[3]来表达该逻辑转换。
整个后续的 Q 的拆解过程如下图[3]：
对于 Q1 到 Q3 中的变量替换可以是任意的，因为只有一个变量，而对于 Q4 和 Q5，如 Q5：RETRIEVE (S.Sname) WHERE (Y.S#=S.S#) 的两个变量，假设 S#列内容为 101,107 和 203，那替换过程变成了下图[3]：
总结 Ingres，采用的 Heuristic 规则的方式：
尽早执行限制条件的 SELECTION
在 JOIN 之前执行所有 SELELCTION
Predicate/Limit/Projection 算子进行下推
JOIN ordering 是基于 Cardinality 的
Ingres 缺点也是明显的，这里简单提及下 1986 年后的 PostgreSQL（Post-Ingres），它和 Starburst 一样，也开始继续探索 Rule System 来对优化器进行改进。
System R Optimizer + Starburst Project
System R
System R 是 1974 年 IBM San Jose 研究院的基于数据库系统的研究项目，提出了第一版的 SQL 语言，也称为了现在数据库查询语言的标准。System R 的架构将数据库分为三个部分：⽤户程序、关系数据系统（RDS）、关系存储系统（RSS）以及两个接⼝：关系数据接⼝（RDI）和关系存储系统（RSI）[5]。
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 优化器整个搜索过程分单表、两表......的方式进行，下图作为一个举例。
首先看到单表关于 Access Paths 的优化过程，分别展示了三个表的访问方式（index/segment scan）和其统计信息如 C(EMP.DNO) 即通过 DNO 扫描的代价，Ni 代表了结果的 card，并形成了单表的 search tree[6]。
接下来扩展到两表的 Search tree，可以看到从上往下的第一层节点代表两个表的连接顺序，如(EMP,DEPT），接下来记录了按访问顺序选择的访问方式和统计信息，如最左端的 Index EMP.DNO，表示用 index scan 的方式访问 EMP 表，而再下一条边是 Index DEPT.DNO，表示用 index scan 方式访问 DEPT 表，之后到达最底端，产生了具体的代价、Card 和 Interesting Order 的组合，以此类推[6]。
System R 在最后也初步提到了对于相关和非相关子查询的估算方法，具体会在后续的论文才提到。System R 的经典设计，确实影响了后续很多数据库的设计。
Starburst Project
Starburst 项目主要是针对于 Query Rewrite 模块，创新的提出了实现一套可扩展的 Rule Engine 来更好的实现逻辑关系代数转换，当时设计的目标如下[12]：
Make queries as declarative as possible，尽量让输入的查询语句表达目标，而忽略数据库引擎如何来执行产生结果；
Perform natural heuristics，通过 Heuristic 的方式进行查询改写，比如条件下推，能带来巨大的性能提升。
总结，正是因为 System R 和 Starburst 的充分结合，正式诞生了 DB2，开创了关系型数据库的商业之旅。由于《数据库挖祖坟系列-DB2 数据库优化器介绍》文章已经充分介绍了相关优化的详细内容，本文不再赘述。
EXODUS Optimizer Generator
EXODUS 是一个可扩展的数据库，目标是为了帮助数据库的实现者快速实现高效的、应用特定的数据库系统，可以独立于数据模型，提供核心的组件包括通用的存储管理器和类型管理器，并提供了一套通用架构、工具和组件，有兴趣可以参考《The Architecture of the EXODUS Extensible DBMS》[9]。
本文主要重点还在优化器上，不过早期的理论都不仅仅在完善一个优化器，而是可以针对各种不同数据模型，所以你都能看到早期的论文会加 Generator 字样，其实就是优化器的抽象架构和生成系统，而且很多概念源于当时的 AI 系统的语言、关系和系统，有点和现在云大数据平台或者计算平台。
下面是 EXODUS Optimizer Generator 的架构图[9]，输入是和查询树转换相关的一组算子、一组方法实现和关系代数转换规则及算子和方法实现之间的描述信息（model description file）。
The Input to the Optimizer Generator
当数据库构建的时候，Generator 负责根据 model description file 生成指定的优化器，在运行时态的时候能够根据用户接口转换为相应的 query tree，再通过 optimizer 转换成对应的执行计划，再到 interpreter 解析为可执行程序。优化器中所有初始查询树及其转换的等价关系代数树放在 MESH 的 hash 结构中，Transformation rules 放在 OPEN 的优先级队列中，简单算法描述如下[9]：
model description file 是分两部分，一部分是 description 部分，比如[9]：
一部分是 rule 部分，包括 Transformation rules 和 impementation rules，比如[9]：
有些规则是可以双向的根据相应的条件，比如[9]：
在 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 枚举），其中尽量重用了当中的结构，新产生的节点尽量是自底向上用之前的来代替的[9]。
如果两个节点有相同的算子、算子参数和相同的输入，当新的节点产生拷贝到 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 的过程[9]。
Search Strategy and Learning
因为对于一个复杂的查询，OPEN 中会有大量的可能得转换，如果能够让一个查询优化在合理的时间范围内，最理想的情况下就是只包含最后优化执行计划的转换，不过这显然是不可能的，所以要选择哪些肯定能减少大量 cost 的转换。引入了 Promise 的概念，对于每种转换增加 expected cost factor 即转换前后的系数，提前去看是否减少 cost 再决定使用改转换规则。对于像 select pushdown 这样的设置 f < 1，而对于像 join 交换律的这种中性的转换 f=1。不过 EXOUS 也无法设定这个因子，因为也不知道具体模型是什么，所以提供了根据执行反馈的方式来计算，有几类计算公式[9]：
还要考虑是否因为后续算子来调整该算子的因子，或者根据已经估算的子查询来减少代价。因为始终无法判断当前计划是否是最优计划，所以 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 Optimizer Generator
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 的系统设计思想还是要不仅仅基于数据库中使用的[13]。
因为基于关系型数据的系统查询过程都是基于关系代数，所以在可扩展性和面向对象也都是基于关系代数相关技术的，比如定义关系代数算子及其等价变化的规则，再加上合适的实现算法。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）；
7）每种算法或者 enforcer 的用来判断是否适用于物理属性向量要求的函数（applicability function）；
8）每种算法或者 enforcer 用来估算代价的函数（cost function）；
9）每种算子、算法或者 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 的大体逻辑如下[13]：
对比 Starburst 优化器把关系代数转换（Transformation）放在 Rewrite 部分，Volcano 优化器只是把这个转换当成是多一种选择放在一个框架下。Volcano 优化器同样适用了 cost limit 用来做 branch-and-bound 优化剪枝，由于这个 cost limit 回传递到子表达式中，所以即使去穷举搜索，也会找到相对好的计划。
这里也稍微提下支持 Volcano 优化器的执行器的创新点：1）Volcano 执行器提出来 query execution 的算子里面包含 open，next， close 的范式[14]。
2）提出两个重要算子 chose plan operator 来解决由于变化参数的问题造成的动态计划选择，使用 exchange operator 来解决数据库查询执行时候的并发问题[14]。
最后我们说说 Volcano 优化器怎么改进 EXODUS 优化器：
1）Volcano 的逻辑表达式和物理表达式是分离的；2）物理属性并不像 EXODU 那样随意处理；3）Volcano 的算法是自顶向下的，子表达式只需要在需要的时候优化就可以，而 EXODUS 是都要是转换和估算代价的；4）cost 定义的是抽象的类型，可以是简单的数字，也可以是消耗的时间或者包含 CPU 时间和 I/O 次数的结构体，甚至是一个函数；5）搜索策略非常灵活，包含了物理属性（Physical Properties）、分支定界剪枝（Branch-and-Bound Pruning）和启发式指引（Heursitic Guidance）。
Cascades Framework
现在来到了我们最重要的 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 中后，不断的触发优化的过程，从而分解到更多的子表达式树优化上。整个优化过程采用了动态规划和记忆化的算法[16]。
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：搜索空间管理，它包含初始查询关系表达式树和所有等效的逻辑和物理表达式，以及负责去重复的结构[28]。
流程从论文里找不到，所以借用了其他论文的描述：
第二，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，一个树结构，包含了一个算子节点及其输入的节点，输入节点必须是和该算子的参数对应。方法包括了提取算子或者该算子的输入，以及能够递归的匹配方法[28]。
multi-EXPR，为了减少内存的使用和充分利用 Memoization 的技术，Expression 通过 group 形式来描述，可以根据下图[28]了解下：
Search Guidance
class GUIDANCE，用于 heuristic 控制规则的适用情况和步骤，可以大大缩减最优 plan 的产生时间，但是如果错误的 guidance 也会造成很大偏差。比如一些具有交换的规则（JOIN 交换律）只是 apply 一次，叫 ONCE-GUIDANCE/ONCE-RULE。有一些研究者专门为这些 RULES 划分了模块[16]。
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 算子必须是逻辑算子[28]。
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 所证明。
Columbia Optimizer
前面介绍 Cascades Optimizer Framework 比较详细，Columbia Optimizer 是基于它的改进，所以这里会简短介绍不同点和相关的结构。下图为该优化器的架构[18]：
优化器输入改进
从上图可以看到 Optimizer 的输入 Query、Catalog 和 Cost Model 都是基于 Text File 的，也是 Columbia 优化器宣称的一个重要改进，而非采用 hard-coded 的方式。
Query LISP 语言描述，直接用文本描述了 Query 的逻辑表达式[18]：
Columbia 的输入 Catalog Info 的文本表达[18]：
Columbia 的输入 Cost 文本表达[18]：
这里我们也观察下 Columbia Optimizer 的不同 optimal 的输出物理表达式[18]：
Search Engine 改进
上图[18]为 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 创建时计算完成。下图[18]为伪代码，大家可以看论文来更加细致的理解。
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），节省了巨大的内存[16,18]。
RULE 改进
Columbia 主要继承了 Cacades 的 RULE 的设计，但是从 binding 算法和处理 enforcers 有些改进。首先减少了 binding 的 state，降低了 CPU 使用率，三个状态的 Binding 函数 BINDERY::advance()更加高效[16,18]。
其次，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。
而优化器的调用入口如下：
TASK 分为五种，相对于 Cacades 提到的 tasks，group optimization (O_GROUP), group exploration (E_GROUP)，expression optimization (O_EXPR)， input optimization (O_INPUTS), rule application (APPLY_RULE)，下图[18]为他们之间的调用关系图，这里只介绍改进的 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 的算法[18]。
下图对比了使用 Lower Bound Group Pruning 带来的巨大的剪枝空间的优化[18]。
Global Epsilon Pruning：因为优化器只能获得相对优的执行计划，而可能非最优，那通过这个全局的变量来控制搜索的时间，只要找到小于该值的 plan，即不再继续进行搜索。
在 O_INPUTS 中通过 Starburst/Pruning/CuCardPruning/GlobepsPruning 4 个标记设置剪枝策略：
Starburst，无 Pruning 技术被采用。
Pruning 就是常规的 top-down branch and bounding，用当前累计 cost 和 cost limit 比对
CuCardPruning 表示开启 lower bound pruning，其和 Pruning 的区别是对尚未优化的 group i，InputCost[i]不是 0 而是 group 创建时计算的 lower bound cost
GlobepsPruning 在完成优化时进行一次判断，如果认为足够优，直接记为 winner。
总结下 Columbia Optimizer 的几个针对 Cascades Optimizer Framework 的改进点，1）更加解耦优化器框架和 DBI 的标准；2）充分利用 C++面向对象的 virtual method 实现扩展性；3）频繁分配和销毁对象产生的性能问题；4）top-down 的剪枝技术的改进，简单来说就是更高效的 Cascades Optimizer Framework。
Microsoft SQL Server
从 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 管理和访问在 Haddop 集群上的数据的产品 Polybase。
本文由于篇幅问题，只会简要介绍下 PDW 的优化器，下图[22]是 PDW 的整体架构，它也是利用了现有 SQL Server Optimizer 改造的 MPP 架构。
其主要思路如下：
通过 Shell database 提供了分布式表的 metadata 信息和各个计算节点聚合的统计信息，对应用提供统一的入口和系统。
通过 Shell database 可以充分利用已有的 SQL Server 强大的优化器进生成各种可选的执行计划（MEMO）。
直接将已生成的可选执行计划增加数据移动的操作（data movement operations），再基于代价来进行评估选出最优的分布式执行计划[22]。
由于 SQL Server 优化器的串行计划无法生成最优计划，原因是由于原优化器并不是针对 MPP，对于数据分布无感知， 而 PDW 必须考虑 JOIN/GROUP BY 等算子在 MPP 下如何进行重新分布后的最优 plan，因此，通过 XML Generator 组件把整个串行计划的 memo 都传递给 PDW 的优化器。下图[22]可以看到，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 内容[22]。
总结 PDW 的架构，给非 MPP 数据库提供了一种全新的设计思路，就是利用已有的强大的 Optimizer 通过增加 Control Node+Shell database 的机制和 Data Movement Service 模块来解决分布式 MPP 的问题，对外提供统一的入口和系统。
MemSQL Optimizer
MemSQL 是一个基于内存的云原生分布式数据库，更好的支持实时交易和分析负载，更高的并发性和极致的可扩展性。MemSQL 提供了统一数据库引擎，通过 in-memory 的行存和一个 disk-back 列存存储数据，提供极致 HTAP 的能力。这里介绍主要是因为基于分布式内存数据库，可以学习其中的一些针对 HTAP 负载的创新增强[24]。
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 非常类似，例如：
从模块设计也可以看出，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 的例子：
对于 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 的[24]。
总结下 MemSQL 的优化器，创新性的增加了基于 cost-based 的查询优化转换，充分考虑到了分布式 cost model，另外区别于 PDW 先生成串行执行计划或者 memo，再进行扩展，直接针对分布式的内存分布和分布式 cost 进行优化，能够生成更加有效的分布式计划。对于 JOIN 的 enumeration 过程，采用了 heuristic 方式发现 star 和 snowlfake 的形态，大大加速了优化的有效性和时间。
Orca Optimizer
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 如何交互[23]
可以看出来，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》[26]。下面我们看看，Orca 本身的架构[23]。
优化框架区别
我们这里不会讲更多细节，主要看看 Orca 有什么特别的不同，比如 Metadata Cache，由于 Orca 独立于数据库系统，而元数据不经常变更，ORCA 内部维护了一份对应的缓存，GPOS 模块提供基础组件：内存管理，状态机，线程通信，异常处理，文件 IO 等。
优化阶段区别
Orca 是采用 Cacades 架构但多阶段优化的方式，分为 Exploration（逻辑等价表达式转换）、Statistics Derivation（统计信息的推导）、Implementation（物理等价表达式转换）、Optimization（根据优化目标物理属性、CostLimit 等进行 cost based 优化）。其中 Statistics Derivation 在 Exploration 过程后，会进行统计信息推导，引入了针对特定算子如 JOIN 类的统计承诺（Promise），基本原理是，加入条件的数量越多，估计误差的传播和放大机会就越大[23]。
针对例子”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[23]。
由于 Orca 是基于 MPP 的优化器，必须要进行数据汇聚，并且语句中包含 ORDER BY T1.a 输出要求，因此优化目标就是 req #1：{Singleton，T1.a}，产生两个 alternative 的物理计划(c)/(d)，最后通过 cost 方式确定最后的 best plan[23]。
元数据交换
下图显示了 Orca 如何与不同的后端系统交换元数据。在查询优化过程中，Orca 访问的所有元数据对象都固定在内存中的缓存中，并在优化完成或引发错误时取消固定。所有对元数据对象的访问都通过 MD Accessor 完成，该访问器可跟踪优化会话中正在访问的对象，并确保在不再需要它们时将其释放。如果请求的元数据对象尚未在缓存中，则 MD Accessor 还负责透明地从外部 MD Provider 提取元数据。服务于不同优化会话的不同 MD 访问器可能具有用于获取元数据的不同外部 MD 提供程序[23]。
并行优化
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 之间维护前后的依赖关系，没有依赖关系可以并行[23]。
验证和测试工具
Orca 最可圈可点的就是提供了验证和迭代 plan 的工具，DB2 也有相关的统计叫 simulation。
AMPERe，用于复现和调试 ORCA，而不需登录到用户的 DB 环境。 当 ORCA 内部出现异常，或者计划不符合预期时，会自动把相关元数据，query，优化配置序列成 xml，dump 到文件。 后续可以直接回放这个 xml，而不需要进入到 DB 中。另外，AMPERe 还可用于建立测试框架，指定特定的 dump 文件和期望的 plan 即可[23]。
TAQO，当修复 bug 或者新增功能后，如何保证产生的计划性能没有回退。 TAQO 用于测试 ORCA 的 cost model 的精准度，比如 cost 值高的计划理论上有更长的执行时间[23]。
总结下 Orca，作为 Postgresql 届的大神级的优化器，注定为大数据平台下基于 C/C++的 MPP 数据库提供了强有力的工具，也提升了巨大的性能，就像 Calcite 在 Java 系大数据平台的优化器一样，被广为运用，最重要的就是工程实现方面非常完美，不过也有一些缺点就是需要能支持一些 guidance 来指引优化器迅速能产生相对”optimial“的计划。
Calcite Optimizer
Apache Calcite 的优化器是为数不多的开源 Volcano/Cascades 查询优化器实现之一，最早脱胎于 Hive 的优化器，后来也被 Java 系如 Apache Hive, Apache Storm, Apache Flink, Druid 和 MapD 等大数据项目青睐，连各大厂商的云原生大数据平台和分布式数据库都利用 Calcite 优化器进行增强。和 Orca 不一样，Apache Calcite 系统基本上一个独立的查询执行引擎，利用了联邦技术连接不同的异构数据源，提供了插件式的优化器[25]。
不过我们这里只提下 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 月完成进入主分支。因为实现基本按照标准论文的方式，因此，本来列出其中命名的对照。
因此，不难想象其整个优化器流程如下[25]：
总结下 Calcite 的优化器，新引入的 top-down 优化器实现了真正的自顶向下搜索，实现更接近 Columbia 论文中的描述，实现了 lower-bound pruning 节约优化时间，同时也改进 physical properties 相关的优化性能，成为最简单易懂，受欢迎实用的优化器。
总结
由于现在新型数据库越来越多，但看起来，后续的很多数据库都是依赖于巨人的肩膀结合实际的用户场景地位，进行创新的，这里就不在一一介绍，可能后续会再加入一些非常典型。那未来到底数据库如何走其实是值得我们这些多年从事数据库内核的同学一些思考。云计算给了数据库二次创新的土壤，PolarDB 系的云原生数据库，其实也一直在探索，如何能够大大增强早期开源数据库中的优化器，如何能够更好的支持 HTAP 架构及针对分层数据存储的混合计算体系，如何更好支持存计分离 &计算下推的云原生数据库架构体系，如何通过执行反馈和 AI 技术能够提供数据库自治等等，都值得我们探索。最后，文章比较长，有些论文细节和实现了解不够细致，欢迎交流和帮助改进。
引用
参考文献
1970, A Relational Model of Data for Large Shared Data Banks [1]
1971, A DATA BASE SUBLANGUAGE FOUNDED ON THE RELATIONAL CALCULUS [2]
1976, The Design and Implementation of Ingres [3]
1976, System R: relational approach to database management [5]
1979, Access Path Selection in a Relational Database Management System [6]
1979, Query Processing in Main Memory Database Management Systems [7]
1982, On optimizing an SQL-like nested query [8]
1987, The EXODUS Optimizer Generator [10]
1988, Grammar-like Functional Rules for Representing Query Optimization Alternatives [11]
1992, Extensible Rule Based Query Rewrite Optimizations in Starburst [12]
1993, The Volcano Optimizer Generator- Extensibility and Efficient Search [13]
1994, Volcano-An Extensible and Parallel Query Evaluation System [14]
1994, Implementation of Magic-sets in a relational Database System [15]
1995, The Cascades Framework for Query Optimization [16]
1998, An Overview of Query Optimization in Relational Systems [17]
1998, EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER [18]
2001, Exploiting Upper and Lower Bounds in Top-Down Query Optimization [19]
2006, Cost-Based Query Transformation in Oracle [20]
2009, Enhanced Subquery Optimizer in Oracle [21]
2014, Orca: A Modular Query Optimizer Architecture for Big Data [23]
2016, The MemSQL Query Optimizer: A modern optimizer for real-time analytics in a distributed database [24]
2022, Integrating the Orca Optimizer into MySQL [26]
参考链接
版权声明: 本文为 InfoQ 作者【阿里技术】的原创文章。
原文链接:【http://xie.infoq.cn/article/3893d55b32257493a19cacac5】。文章转载请联系作者。
专注分享阿里技术的丰富实践和前沿创新。 2022-05-24 加入
阿里技术的官方号，专注分享阿里技术的丰富实践、前沿洞察、技术创新、技术人成长经验。阿里技术，与技术人一起创造成长与成就。
评论