calcite是什么意思cite在线翻译读音例句

calcite概念和架构

1.前⾔

Flink使⽤Calcite构造SQL引擎，那么他们是怎么合作的？drill,hive，storm和其他的⼀⼲apache⼤数据引擎也⽤calcite，那么对于同⼀个sql语句

（statement),⽆论复杂简单与否，他们和Flink产⽣的执⾏计划是不是⼀样的?如果不⼀样,区别是怎么产⽣的？应该在哪⾥实施优化和发⼒？优化的⼿段和原

则有那些，等等？本⽂不会对calcite⾯⾯做具到的介绍，重点是SQL执⾏计划的优化框架，流程和策略，对执⾏计划进⾏优化是calcite的主要业务。为了有

助于理解优化框架，对于必要的概念会有介绍，⽐如关系，关系代数，关系演算，等价原理，谓词逻辑等。

e架构

图-1calcite使⽤场景

如Calcite的官⽅论⽂（见引⽤1，发表于于SIGMOD’18,June10–15,2018,Houston,TX,USA）所定义，calcite是⼀个能够连接异构数据源，并运⾏优

化的查询计划的基础框架。Cacite提供查询处理需要的三⼤功能：查询语⾔，查询优化和查询执⾏。但是calcite并不想做这样“onesizefitall\"的框架，它提

供⾜够灵活适配接⼝，使外部系统（数据源（或称存储系统），或查询处理系统）能够选择合适的场景与它适配。calcite⽀持的场景主要有两种，如上图描

述。

在场景1中，calcite作为独⽴运⾏的进程，后台通过适配器与外部的存储系统连接，前台通过JDBC接⼝使⽤SQL语⾔通⽤户交互。在这个场景

⾥，calcite作为⼀个中间件，为⼀些没有或缺乏友好的查询语⾔的存储系统（⽐如HBase,Cassandra,Kafka,ES,Redis）提供查询语⾔（⽐如SQL）。

calcite在内部将⽤户提交的查询优化并运⾏再⾃⼰的进程⾥，并在优化的过程中将适当的部分下推给存储系统。⽐如Cassandra有部分关系扫描

（tableScan),过滤（Filter),投影（Proction)和聚合（Aggregation）的能⼒，calcite能将相应关系表达式翻译成Cassandra的语⾔发送给它并返回结果。对

于Cassandra不具备的能⼒，⽐如连接（join），这部分关系表达式在calcite⾥运⾏。当然这个场景并不是calcite擅长的，因为qu薄雾浓云愁永昼瑞脑销金兽 ery执⾏不是它所擅长的。

在场景2中，calcite作为嵌⼊式的组件运⾏在⼀个查询引擎⾥。这些查询引擎⽤⾃⼰的⽅式连接后台数据源，并使⽤⾃⼰的集群⽤分布的⽅式执⾏查询。

查询引擎善于获取数据和执⾏查询，需要calcite提供查询语⾔和优化查询的能⼒。这个场景的例⼦有Hive,Flink,Drill,Storm。以Flink为例，它的框架⾥

有算⼦连接各种的异构数据源⽤于数据的获取和发布，⽆论是数据流还是数据集。它也有丰富的算⼦将讲这些数据过滤、放⼤、缩⼩和变形⽤于各种各样计算

需求。他需要⼀种对⽤户友好的，对于批流数据语义统⼀的查询语⾔，以便于⽤户编写查询、将查询优化称执⾏计划和⽣成物理作业图，使作业能够以最⼩的

代价运⾏在Flink集群中。场景2是calcite最受欢迎的和最擅长的场景，相⽐查询执⾏,连接数据源，calcite更擅长的是制造查询语⾔，解析查询，和查询优化

。为什么这么说呢,那就要看看它的架构了。

图-2引⽤1中calcite官⽅论⽂中的架构图。

绿⾊框框QueryOptimizer（优化器，也称Planner,⽐如HepPlanner,VolcanoPlanner)是calcite的⼼脏和⼤脑，它接受查询计划，输出优化的查询计划。

蓝⾊的框框是优化器的输⼊和输出和各种适配器，包括OpeatorExpressions(输⼊的原始计划，中间结果和最后输出的计划）,MetadataProvider(提供元数

据的组件，⽐如对优化规则⽤的统计信息（RowCountoftable,DistinctRowCout/min/maxofacolumn,etc)还有pluggableRules(优化规则,利⽤关系代数或

关系演算的等价关系，优化执⾏计划，使之更够最快速的执⾏)。这三个组件是calcite可扩展部分，因此与外部系统有连接。

黄⾊框框（DataProcessingSystem，简称DPS)与蓝⾊框框有虚线连接，是DPS对calcite的扩展部分。这⾥的DataProcessingSystem所指的就是场景2

⾥的查询引擎。它通过扩展metadataprovider和pluggablerules,向优化器提供更准确的元数据信息，更适合的代价模型，更⾼效的优化规则，利⽤

calcite优化器产⽣最优化查询计划。SQLparserandvalidator,是Calcite的SQL语⾔的解释器，它将⽤⽤户⽤SQL语⾔编写的查询解析称Opeator

Expressions，并验证它的合法性。

OpeatorExpressions是⼀种⽤于表⽰关系代数表达式的树状数据结构。解释器将SQL查询解释成关系代数表达式，之后优化器调⽤规则将其修改为最优表

达式。优化规则会根据有关系代数的等价原理将表达式变形从⽽使表达式的代价降低。但如何判断代价是否降低？办法有两种：⼀种是根据经验，⼀种是根据

代价模型。根据经验学名称做启发式（Heuristic)模型,根据代价模型估计的，学名叫⽕⼭模型。相应的优化器也被称作启发式优化器和⽕⼭优化器

（HepPlanner,VocanoPlanner)。代价模型的量化计算是根据从metadataprovider获取关系及关系运算的元数据，再辅以量化模型的计算。元数据通常指

的是⼀个关系（table）和关系运算(projection,filter,join,aggregation,etc)产⽣关系的统计数据：如关系的rowcount,某个分量的distinctcount，min,max等

。DPS会扩展Calcite逻辑关系表达式产⽣“物理”关系表达式,⽽这些扩展的表达式也会输⼊给优化器，利⽤规则继续优化。

ExpressionBuilder是⼀种绕过SQL解析，直接⽣成关系表达式的⼯具。这种⽅式适⽤于单元测试，就不做展开展开介绍了。

图-3calcite交互数据流

⽤数据流图的⽅式描述⼀下calcite和DataProcessingSystem的交互，如上图所⽰，应该更容易理解，为什么⼀个⼤数据处理系统更喜欢在场景2⾥⾯使

⽤calcite。优化器是从calcite的核⼼是不变的地⽅。Rules,metadata,和operator是优化器依赖的帮⼿，但都是可扩展的部分。回答在前⾔⾥的问题，有那

么多的⼤数据系统使⽤calcite，相同的sql查询经过calcide优化器产⽣的计划会⼀样吗？答案是否定的。原因是要看各个⼤数据系统⾥扩展的Operators,

metadataprovider,还有新的规则和应⽤的顺序是否相同等等。不同的扩展，产⽣的关系表达式肯定不⼀样。扩展做的更优秀，优化的结果就更优秀。⽐如

MetadataProvider提供的关系运算统计数据是⼀种估计，除了最底层的TableScan的代价估计是相对准确的，别的运算的估计都是有误差的。误差越⼩，规

则运⾏的越准确，反之则不然。

3.⼀些关系的概念

Calcite只⽀持于关系型数据模型（不⽀持层次，⽹状，对象数据库的模型），那么什么是关系型数据库呢？建议读⼀下引⽤5中的那本书，虽然我也没读完

。下⾯解释⼀下⼀些⽐较容易混淆的概念。

关系：关系⼀词来⾃离散数学⾥的集合论，根据维基百科的的定义，给定任意集合A和B，若R属于AXB（笛卡尔乘积），则称R为从A到B的⼆元关系，特别在

A=B时，称R为A上的⼆元关系。如果⼀个有N列的⼆维表，每⼀列的取值范围为Ai则该表是定义在A1x..Ai..xAn上的N元关系。可见，关系（Relation)是N元

有序序列的集合。关系在数据库的概念⾥称作表（Table），关系的每⼀个有序序列叫做元组或⾏（Row),元组的每⼀个量叫分量或列(Column)。

关系模式（Schema）：是对关系或表的描述。包括关系名称（TableName），列名以及列的定义域（Domain)。

关系模型（Model)：指的是⼀系列关系模式的集合，概念上对应数据库。

维度（Dimension)：通常是指列离散定义域的列。定义域上的每⼀个值称为基（cardinality),⼀个关系已经使⽤的所有的基的个数成为基数（cardinalnumber)

,也就是distinctcount,也成NDV（NumberofDistinctValue)。

关系代数：是由提出⼀种利⽤具有良好语义的代数结构⽤于对数据建模和定义查询的理论。代数结构是在⼀种或多种下封闭的⼀个或多个，那么关系代数在闭

合关系上的良好语义的运算的集合。通俗的说，关系代数是⼀种通过由代数运算和输⼊关系组成的表达式来表达输出关系的理论。⽐如图-3中，SQL产四时田园杂兴古诗(一) ⽣的关

系可以多个树形的表达式表⽰，树的形状和节点的排列顺序代表运算的过程（从下到上）。关系代数是⾯向过程的。

关系演算，是另外⼀钟表达关系的理论，他是以数理逻辑中的谓词演算为基础，⽤描述和声明的⽅式表达关系。⽐如关系代数表达式⽤⼀系列代数运算来表⽰

最终的产⽣关系，⽽关系演算则⽤声明形式的表达式描述⼀下最终的关系定义。每⼀个关系代数的表达式，都有对应的等价的关系演算表达式（Codd定

理），但反之则不然。关系演算和关系代数都来⾃关系模型理论。

SQL语⾔：是关系代数和关系演算的实现。⽐如运算都来⾃关系代数，运算⾥谓词都来⾃关系演算。现在⼤多数⼈都说SQL是⼀种声明式的语⾔，有点道理

但也不全海边风景图片 对。演算部分是声明的，代数部分是过程的。⽐如⼀个equaljoin,join是代数规定结果是⼀个笛卡尔乘积。equal是演算定义了⽬标关系⾥保留的是

双⽅的键值要相等。这个声明给了关系表达式的实现者可以通过hashjoin,或sortmergejoin优化这个equal。

OperatorExpression:指的是表达关系代数和关系演算的表达式，在calcite中由⼀种树状结构来表⽰。它取这个名字的原因是树中所有的节点都有相应的操作

符来表⽰，包括输⼊和输出关系（TableScan，Sink)。我更喜欢把它叫做关系表达式：表达关系代数和演算的表达式，或由作⽤在关系上的运算组成的表达

式。在优化的过程中，最原始的树状的数据结构会转化成⼀个图，因为⼀些⼦计划可以重⽤的，重⽤的⼦计划和原计划会使⽤相同的节点实例，就像⼀个可以

重⼊的函数可以被调⽤多次，但返回的数据是相同的。⼀个节点有多个parent,就变成了不在是⼀棵树了。⽐如SQL中的CTE，如果上游的谓词没有下推，它

是⼀个⾮常独⽴的存在，可以单独优化，形成⼀个⽐较独⽴的⼦计划和⼦表达式。 如果该⼦表达式被使⽤多次，他在图中就会成为多个上游节点的⼦计划。

物化视图也是⼀个例⼦。计划图是⼀个有向⽆环图(DAG)，也就是⼀个关系只能作为另外⼀个关系的输⼊，不能作为⾃⾝的直接或间接输⼊，形容夏天的唯美句子 树是有向⽆环图

的特殊性形式，所以把优化后关系表达式称为计划图⽐较合适 。

还有⼀点要注意，当我们谈论计划的时候，计划图是⼀个向下⽣长的DAG,根节点是Sink,叶结点是TableScan。上游，下游，上推，下推，是对应从根节点

先下的⽅向。当我们谈论作业流（jobGraph)的是，上游，下游对应的是数据流向。

e的概念

上⼀章的概念说了这么多，感觉就是为了解释什么是OperatorExpression（关系表达式）。这个概念很关键，它是优化器操作的数据结构，它经过优化

规则的修剪和雕琢，和元数据提供者营养的滋润，成为最终的最优（代价最⼩）结构。如果还是不好理解，那就先抛去那些虽严谨但晦涩的数学概念，可以

把⼀个关系表达式想像成⼀个作战计划，⽐如著名的官渡之战。如果曹操在官渡和袁绍死磕,作为原始的作战计划，也有小学观潮课文原文 可能也会获胜，毕竟有官渡河天险可

守。但是代价会很⾼，毕竟袁绍的兵⼒数倍于曹操，正⾯作战胜率较低。于是曹操优化了原始计划，⾸先不主动出击，坚守官渡，然后偷袭乌巢，烧了袁军的

粮草，导致袁军军⼼⼤乱，仓促攻曹，最后致败。曹操⽤最⼩的代价⼤败袁绍于官渡，他的作战计划⾥的关键步骤是奇袭乌巢和坚守官渡。可惜袁绍⽩⽩拥有

10万⼤军，和五⼦良将张颌，占尽优势，但却⼀败涂地。袁绍最⼤的错误就是使⽤了错误的计划，信任千古奸⼈郭图，这个⼈不仅害袁绍，袁的两个⼉⼦也

都被他害死，最后被曹操斩杀。不得不说，曹操⽆论是对官渡之站的计划，还是对郭图的计划都是最优的。

如果做⼀个粗糙的类⽐，曹操的⼤脑在相当于calcite的启发式优化器，他⼿下谋⼠的计策就是Plugablerules，⽐如的突袭⽩马，荀彧的坚守官渡，许攸的

奇袭乌巢，进攻、退守是关系代数⾥的运算符，⽩马，乌巢，官渡这些地名相当于关系，那么⾏军路线就构成了⼀个计划图，如同关系表达式的计划图⼀样。

作战计划依赖主将的智商和经验判断来计划的优劣，曹操雄才⼤略是不世的英雄豪杰，⽐起袁绍要聪明数倍，他的判断⾃然准确率⽐较⾼。但是也有判断失误

的时候啊，⽐如⾚壁之战，依赖智商并不总是⼀个好办法。Calcite的优化器要依靠元数据提供者的数据和代价模型⽤量化的指标来判断不同计划的优劣，在统

计上应该中国寓言故事 是更准确的。那么回到⼀个程序员的思维⾥，优化器具体是怎么⼯作的呢？

先看下callcite对外开放的接⼝。

图-4来⾃引⽤7中，CalciteAPIandSPIs

概念⽐较多，⽤⼀个表来解释⼀下吧。

概念解释例⼦

RelNode关系代数中的关系和运算的基类。RelNode有很多继承者，见举例。

TableScan对应⼀个数据源的⼀个关系，Filter对应Filter

运算。Filter有⼀些系列的继承者，每⼀个继承者对应⼀

个CallingConvention,也对应⼀个优化阶段的使⽤的数据

结构。⽐如Join<-LogicalJoin<-FlinkLocalJoin<-

FlinkBatchExecJoin,FlinkExecStreamJoin。

RelDataType代表域，是关系中列的定义域整数，⽇期，浮点数，定点数，字符串

RexNode代表Project⾥Filter中表达式

⽐如下⾯关系⾥⼀个分量（InputRef)，⼀个常量值

(Literal)，⼀个或多个分量函数(RexCall,加、减、乘、

除、CAST等)

RelTrait

代表关系运算的物理特性，这个应该是calcite⾥最让⼈迷惑的概念了。但

Trait，set，subset是volcanoPlanner最依赖的概念。

关系的物理特性是跟关系代数没有关系的⼀些特性，所以只有跟物理执⾏系

统⽐较临近的关系运算才会有物理特性，⽐如FlinkBatchExecFilter有物理

特性，它是被翻译成FlinkJobGraph的输⼊计划的节点类型。⽽LogicalFilter

观完全逻辑上的关系观念，因此不会有任何物理特性。

Calcite有三种类型的特性，类型叫做TraitDef。

关系某个列的排序⽅式（collation)：数学上的关系⼀个N元元组的集

合，是不关⼼顺序的，所以关系（元组）的顺序作为⼀个物理特性存

在。既然和关系⽆关，那么Calcite⾥为什么有sort操作符？这个是表

达式扩展或是迁就SQL的结果，SQL⾥有⼀些跟关系⽆关的操作，⽐

如orderby,distinct等等，虽不符合关系的定义，但这⾥上计算机世

界，不是纯数学的，就把关系当作是⼀个泛化的概念吧。原始的关系

运算就6种，后来⼀些常⽤的就被填补进来，⽐如sort，aggregate,

window,expension等。即使计划⾥有sort操作符，提前做排序，还是

是等到sort节点在排序，也是VolcanoPlanner优化考虑的选择。有时候

即使计划⾥没有排序，排序也会使整体计划加速。Spark的join都是⽤

sort-mergejoin正是基于这样的考虑。

关系元组的发布⽅式（Distribution)。这个表明关系元组发布给

jobGraph中的下游节点的⽅式。是⼴播出去的，是本地forward过去，

还是异地Shuffle过去的，等等。

调⽤习惯（Convention)。前⾯两个特性都是关系的⾏和列上的物理特

性，Convention代表查询系统（也就是前⾯所说的DPS)的物理特性。

Calcite⾥⾯的规则⼤部分的规则都是由HepPlanner调⽤的，只有当

Convention变化的时候，才会使⽤VolcanoPlanner。

Collcation可以是升序，严格升序，降序，严格降

序，聚集。参见RelFieldCollation.

Distribution可以是单⼀的，哈希的，分范围的，随

机的，轮换的，⼴播的，任意的。参见

RelDistribution。

Convension:calcite的JDBCConvention,Flink

的LOGICAL,BATCH_PHYSICAL,

STREAM_PHYSCIAL。

⽐如Flink中的节点BatchExecJoin

在BATCH_PHYSICAL调⽤习惯中的运算节点。

最初的关系表达式中的join⽤calciteLocalJoin表⽰，

在LOGICALconvention中⽤

FlinkLocalJoin，BATCH_PHYSICALconvention中

⽤FlinkBatchExecHashJoin。⼀个在Flink优化的join节点

会有随着convention改变可能有如下的变形。

LogicalJoin-->FlinkLogicalJoin-->

FlinkBatchExecHashJoin。

AbstractConverter

当关系表达式的Convention发⽣变化的时候，VolcanoPlanner会在Relset

⾥创建Relsubset代表这种traits,随后创建AbstractConverter⽤于转化成真正

的表达式。ExpendConventionRule配备AbstractConverter，将它转化成

合适的节点，⽐如BroadcastExchange,Sort等。

参考FlinkExpandConversionR花非花白居易赏析 ule,

calcite:AbstractConverter,

tractConverter。

RelOptRule

所有的优化规则的基类，它构造函数第⼀个参数就是关系运算的类型（⽐

如，Join，Filter等），（还有⼀些别的，不展开了）。当Planner遍历表

达式图的每⼀个节点时，他会调⽤匹配这个节点类型的规则。除了匹配类

型，VolcanoPlanner还会给规则设置优先级，级别⾼的会别先调⽤。每⼀

个规则有两个函数：matches()继续深度判断改规则是否真的应该调⽤。

onMatch执⾏规则实际的动作：根据测量增、减、改变、升级表达式的节

点。

优化规则有的会通过元数据提供者查询元数据信息，从⽽做相应的措施。有

的不会。从规则的⾓度来看，planner都是⽆区别的。所以除了少量的例外

（⽐如前⾯提到的ExpendConvensionRule)，⼤部分都可以被

HepPlanner和VocanoPlanner调⽤的。

例⼦有很多，⽐如有名的谓词下推，⼦查询替换，join-

recorder，常量替换等。google⾥搜索⼀下，会很多介绍

。

想看全⾯的，请参考

⾥⾯的规则，或

⾥⾯的使⽤的规则。

RelMetadataProvider

RelOptCost

前⽂多次提到的统计数据提供者，他是⼀个能handle不同统计类型数据的

handler的集合。⽐如RelMdRowCount是提供关系运算产⽣的rowCount估

计,RelMdDistinctRowCount提供某个列的cardinalnumber估计。

RelMdSelectivity提供关系运算后的rowcount原来的⽐例估计。

RelOptCost是代价模型，calcite的代价模型是对关系的⾏数，通常是考虑

IO(diskIO+networkIO)和CPU使⽤率，memory,和关系规模（rowcount)

的⼀个综合衡量。

Calcite⾥有DefaultRelMetadataProvider提供了各种

Handle缺省计算⽅法。

ReflectiveRelMetadataProvider由于接受DPS端实现的

Provider,⽐如Flink⾥实现的

FlinkDefaultRelMetadataProvider.

还有⼀个JaninoRelMetadataProvider,看起来是通过动态

编译的⽣成Provider?

Handler的元数据的估计算法请阅引⽤5的第13章。

Schema

Table

Lattice

Tile

Schema和table的概念全⾯说过。

Lattice（格）是除了关系、关系代数之外，另⼀个来⾃于数学领域的名词。

看起来calcite是真的很想提升⼴⼤数据程序员的数学格调。

格同关系代数⼀样是⼀种代数结构（集合+⼀种⼆元关系），集合的成员的

⼆元关系是反⾃反，和传递的，⽽且这个关系有明确的上下界，则称这种

代数结构为格。很抽象，可以看引⽤8中的哈斯图理解。{x,y,z}的按就是

⼀个格。

这个和多维cube聚合计算的物化视图的结构很像。物化视图⾥的每⼀个顶

点都是⼀个tile,最上⾯的tile包含了所有的维度，最下⾯的维度为空，维度

集合以及包含关系组成了⼀个格。格从上到下是是降维的过程，则低维聚合

计算可由⾼维聚合导出。所以lattice,Tile是为物化视图引⼊的，只不过换

了⼀个⽂艺的名字⽽已。

物化视图是⼀个预计算的结果，物化在硬盘或内存⾥，如果把查询计划⾥能

够利⽤物化视图，执⾏的很定会飞快。

来⾃引⽤8

HepVertex

HepProgram

HepPlanner

HepVertex是HepProgram⾥⽤于组成计划图的顶点。HepProgram是⼀些优

化规则的集合，HepPlanner利⽤HepVertex建⽴将计划树转化成计划

图，然后利⽤HepProgram按照⼀定顺序遍历其中的优化规则。

HepPlanner调⽤流程如右侧代码所⽰。

调⽤SetRoot⽤HepVertex建⽴全新的计划图，

changeTraits,desiredTraits为空

调⽤findBestExp⽤迭代的⽅式，⽤预先设定的顺序（⽐如

BOTTOM_UP),遍历所有匹配的规则，优化计划图。

HepPlanner的寻优是⼀个⼀种贪⼼的算法，就是当前迭代步会⽤上⼀次迭

代结果的作为当前最优结果继续优化，如果上⼀步做错了，下⼀步也会错下

去。只有将迭代运⾏多次，才有可能避免改正错误。

//buildprogram

valbuilder=newHepProgramBuilder()

builder

.addMatchLimit(10)

.addRuleInstance()

.addRuleInstance()

.addMatchOrder(_UP)

valhepProgram=()

//createplanner

valplanner=newHepPlanner(hepProgram,...)

//buildnewoperatorexpressiongraph

t(root)

Traits(desiredTraits)

//applyrulesinprogramstooptimizetheoperatorexpression

stExp

Relset

RelSubset

VolcanoProgram

ValcanoPlanner

RelSubset代表⼀个⽬标物理特性，⽐

如BATCH_,代表⼀个BATCH_PHYSICAL

convention等价⼦计划，⾏发布⽅式是⼴播，列排序⽅式为任

意。BATCH_,是另为⼀个subet。

Relset是所有具有不同物理特性的等价的RelSubset的集合这些，⽐

如BATCH_ast.[]和BATCH_.[]是等价

的。

Relset还是所有等价关系的集合，⽐如

HashExchange+SortMergeJoin，HashExchange+HashJoin,

BroadcastExchange+Hash,ASCsort+SingleExchange+Hash都是等价关

系表达式。

RelSubset会在从等价关系集合⾥选择符合⾃⾝trait的最便宜的行路难其一原文及翻译拼音版 作为他的

best。从上到下的best组成最终的计划图。

VocanoPlanner运⾏流程和HepPlanner类似。

调⽤SetRoot⽤RelSubset,Relset建⽴新的计划图，

调⽤changeTraits，设置root的traits,并沿着计划图将traits向下传递，

每⼀层都要根据关系运算的特点向下提⾼需要的trait.

调⽤findBestExp,⽤动态规划的⽅式，整体上从下到上创建符合trait要

求的关系表达式，在其中选择最便宜的填⼊subset中，并将cost向上

传递。

当所有每⼀层的subset的best都计算完成从到下，做⼴度优先搜索即

可得到最优的计划。

5.优化器流程

HepPlanner的寻优流程很简单，setRoot重建planGraph,findBestExp就是按照指定的顺序将HelpProgram⾥的规则触发⼀遍。如果担⼼有问题贪⼼算法的问

题，可以将这两步多做⼏次。

VocanoPlanner的寻优流程如前所述。TraitSet通常包含了Convension,distribution,collation三个维度，这三个维度不同的基的组成的组合（subset)都是

等价的但是cost不相等，但并不是代价把最低的subset输⼊给上游总代价就会最低的。最低的代价需要综合考把虑上游和下游的情况，寻找最搭配的搭档。所

以这个寻优过程需要⼀个动态规划的⽅式来求解。在使⽤动态规划（也就是递归的⽅法,volcanoPlanner的命名就来⾃这⾥吧）求解之前，我们需要把各种可

能的计划的每⼀层的满⾜需要trait的subset，以及对应关系求出来。⽽满⾜要求的subset,⽽且在考虑到输⼊的组合，状态转移公式⼤概如下。

BestExp(subset))=argmin(cost(rel1),cost(rel2),...)

cost(rel)=algoCost()+cost(BestExp(1))+cost(BestExp(2))

第⼀⾏中，rel1,rel2是满⾜traits的等价表达式，表⽰当前subet的最佳表达式是他们之中⾥cost最低的表达式。

第⼆⾏中，表⽰表达式的cost等于最上层节点⾃⾝算法代价估计和下层输⼊subset的最佳表达式向上输⼊的累计的综合代价。TableScan的下层输⼊就是磁

盘IO的代价，底层关系的RowCount相关。这⾥的加号代表代价计算要综合考虑的因素并不是简单的算数相加。⽐如hashJion和sortMergeJoin⾃⾝算法的代价

不⼀样（CPU，内存代价），join的两路输⼊⽅式不同代价不⼀样（IO代价）。

举个例⼦：

SELECT*fromstore_salesjoindate_dimonstore__sold_date_sk=date_dim.d_date_skanddate_dim.d_year=2002

1

这个表达式唐代三绝 ⾥主要有⼀个HashJoin和两个TableScan组成，如果对HashJoin的requriedTraits是BATCH_.[],HashJoin对store_sales和

date_dim的要求分别是BATCH_d.[]和BATCH_ast.[],那么上⾯的公式以下的形式。

BestExp(_.[])=argmin(cost(shuffledHashjoin),cost(broadcastHashJoin),cost(shuffledSortMergeJoin)，...)

cost(broadcastHashJoin)=cost(BestExp(tablenscan_store__d.[]))+cost(BestExp(tablenscan_date__ast.[]))+algoCost(HashJoin)

类似的过程可以求出cost(broadcastHashJoin),cost(shuffledSortMergeJoin)。

Broadcastjoin极⼤的减少了⽹络和磁盘IO，cost肯定是最低的，最终Broadcastjoin表达式会选为join层满⾜要求的subset的最佳关系表达式。

从上⾯的转移公式可以看到，requiredtraits是从通常从上向下传递的（也有⾃我要求的)，⽐如join对下游的⼴播⽅式的要求，全局排序要求下游以single⽅

式发布数据的要求等。cost是从下先上传递的，没有下游已经确定的关系，上游是⽆法计算代价的。在向下传递traits的过程中，calcite创建

AbstractConverter代表⽬标traits临时节点，之后再ConventionExpansionRule将AbstractConverter转化成实际的关系。⽐如cast.

[]建在TableScan上⾯，⽬的是想让tableScan以⼴播⽅式输出，ConventionExpansionRule最终会将这个表达式变成BroadcastExchange+TableScan。当

TableScan的代价估计会沿着Exchange向上传递，上游关系的代价也得以计算，以此类推。

VolcanoPlanner将与节点匹配上的ConventionExpansionRule和其他的ConverterRule都放在优先队列⾥。由于新的relSubset创建时，AbstractConverter才

会创建，之后触发ConventionExpansionRule与之匹配和放⼊队列，⽤以之后创建Exchange和sort节点。这个和其他的ConverterRule不

同，ConverterRule是匹配旧的Convention的结点（⽐如LogicalXxxxx),他们在节点注册的时候（setRoot)就已经⼊队。优先队列⾥的成员都有优先级，级别

⾼的先被调⽤，这样能保证那些ConverterRule先于ConventionExpansionRule调⽤。

图-5VolcanoPlanner

画个图表⽰⼀下relSet,relSubset,和besExp还有trait之间的关系吧，还有这个类似⽕⼭喷发的形状。

7.引⽤

序号描述链接

1Calcite论⽂

2Calcite官⽅⽂档

3关系代数

4关系演算

5数据库系统概念第6版AbrahamSilberschatz等著

6官渡之战

7SQLoneverything,inmemorybyJulianHyde

8哈斯图