前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Calcite系列(九):执行流程-优化器优化

Calcite系列(九):执行流程-优化器优化

原创
作者头像
Yiwenwu
修改于 2024-05-10 04:14:55
修改于 2024-05-10 04:14:55
1.2K0
举报
文章被收录于专栏:Calcite剖析Calcite剖析

背景介绍

优化器优化是SQL处理的第四步,也是最核心的一步,优化器优化本质是基于优化规则实现关系代数等价转换

关系代数等价转换:是数据库查询优化中的一个重要概念,指的是将一个关系代数表达式转换为另一个关系代数表达式,尽管这两个表达式的形式有所不同,但它们具有相同的语义且计算结果相同,而新转换的关系表达式的计算性能往往更优于原有的表达式。在Calcite中,关系代数等价转换即为RelNode计划树的等价转换

RelNode计划树等价转换
RelNode计划树等价转换

目前,Calcite内置两类优化器:

  • HepPlanner:RBO(Rule-based Optimizer)基于规则的优化器,将计划树构建为DAG有向无环图,按顺序依次遍历并执行优化规则
  • VolcanoPlanner:CBO(Cost-based Optimizer)基于代价的优化器,基于Volcano/Cascades Optimizer 经典的优化器框架实现,通过Memo维护等价集,使用贪心算法寻找最优解。 除此之外,CBO的优化效果取决于两个关键因素:代价模型(Cost Model)和 统计信息(Statistics)
优化器类型
优化器类型

优化规则

Calcite内置的优化规则超过200条,可分为两个类别:

  • TransformationRule:用于逻辑计划的关系代数等价转换,例如常量折叠、谓词下推、列剪裁等。逻辑计划等价转换并不能保证转换后的计划树更优,其子类SubstitutionRule维护了转换后一定效果更优的规则集
  • ConverterRule用于Calling Convention,实现不同Convention之间的转换,可等价理解为:实现逻辑计划到物理计划的转换

如图展示基于优化规则实现的计划树等价转换:

  1. 常量折叠:在优化时直接计算出常量表达式的值,如图2020+6=2026,将计算后的常量值代替常量表达式,减少查询执行时的常量计算
  2. 谓词下推:将过滤条件(谓词)尽可能提前进行计算和应用,即在计划树中,尽可能将Filter算子下推到树的底层,通过过滤下推降低上层操作的数据输入量
  3. 列剪裁:只获取查询中实际所需的列,通过Project算子移除未使用的列,从而减少使用列和数据处理量
优化效果
优化效果

Calcite通过执行优化规则,实现RelNode等价转换,由三个步骤组成:

  1. 规则匹配模式:基于 RelOptRule#matches 判断规则应用的条件和模式,确保特定树节点,只能应用满足匹配模式的规则,即 实现规则筛选过程
  2. 规则应用:基于RelOptRule#onMatch→RelOptRuleCall#transformTo 触发规则执行,实现计划树的等价转换
  3. 等价节点构建:转换后的等价计划树维护在RelOptRuleCall中,优化器可根据实现要求,构造出对应的等价RelNode

在Calcite中,各类优化器都基于相同的规则应用机制实现计划树等价转换,不同优化器的主要差异在于规则匹配策略和等价节点构建的方式不同。

RBO优化器

下图展示RBO优化器HepPlanner的执行流程,分为三个步骤:

  1. 初始化:将RelNode转换为DAG有向无环图,其中各个顶点使用 HepRelVertex 表示并维护关联的子节点
  2. 搜索最优计划树:遍历DAG按照顺序依次触发规则应用(fireRule),其中遍历顺序可基于HepMatchOrder参数化配置
  3. 构建最优计划树:基于Visitor模式自顶向下遍历DAG顶点,获取对应的RelNode节点,基于转换后RelNode构建出最优计划树

CBO优化器

备注:该CBO流程说明基于Calcite版本V1.21.0展示,与最新Calcite版本存在差异

执行流程

下图展示CBO优化器VolcanoPlanner的执行流程,分为三个步骤:

  1. 初始化:构建等价集,遍历RelNode生成对应的Relset/RelSubset。注册RelSubset时,计算节点代价并添加规则到RuleQueue。
  2. 搜索最优计划树:根据RuleQueue规则队列中弹出匹配条件的优化规则,应用规则后,若新计划树成本更低,则重新注册该等价计划树并将其维护在搜索空间中。退出计划树搜索需满足以下任一条件:(1). RuleQueue中可应用的优化规则为空;(2). 最优计划树COST代价稳定,没有显著下降;(3). 搜索优化超时
  3. 构建最优计划树:退出搜索后,遍历RelSubset维护的最优代价节点,构建出最优计划树

其中,CBO优化器基于RuleQueue (规则队列)维护优化规则集,与RBO顺序匹配规则不同,CBO规则匹配是随机的。主要基于RelSubset中计算的Importance倒序排列,COST代价越高的节点Importance越大,会优先进行规则匹配。

初始化

如图展示VolcanoPlanner初始化的实现流程,初始化执行入口有两个:

  • changeTraits 变更RelNode物理属性,遍历RelNode计划树注册各个节点,基于VolcanoPlanner#addRelToSet 方法生成相对应的RelSet和RelSubset,若已存在等价计划树,则追加到对应的等价集里
  • setRoot 保证AbstractConverter节点在RelSubset计划中已被注册,该节点可用于后续Convention的转换触发

初始化过程中,核心处理主要包括:

  • 代价计算:如下图紫色框所示,注册RelSubset 时,将会调用propagateCostImprovements 方法计算该等价集中的所有计划树COST代价,并独立维护代价非infinite且代价最小的最优计划树,该过程除了计算COST代价也会触发RelNode Importance计算,对应Importance维护在RuleQueue中,用于排序规则的执行顺序
  • 注册规则:如下图红色框所示,注册完RelSubset后,基于fireRules从初始化规则集中匹配出满足该节点的规则子集,并根据Importance将规则子集添加到RelQueue规则队列中

其中,RelSet 代表一组关系代数等价计划树,即等价的逻辑计划树集合;RelSubset属于RelSet子集,代表一组物理属性相同的关系代数等价计划树,即等价的物理计划树集合

搜索最优树

如图展示VolcanoPlanner搜索最优计划树的实现流程:

  1. 基于RuleQueue弹出对应节点匹配的优化规则,通过VolcanoRuleCall触发规则应用以生成新的等价计划树
  2. 基于ensureRegistered方法注册新的等价计划树,如果新计划树的代价低于对应RelSubset等价集中的最优计划树,则重新递归计算父节点代价,并将该计划树维护在Memo搜索空间中

计划树变换

下面将以计划树变换图直观的展示CBO执行流程,示例SQL:select name, num from student where name = 'add'

  1. 初始化changeTraits将RelNode变为RelSubset,代表一组物理属性相同的逻辑计划;setRoot保证AbstractConverter节点注册,由于Convention=NONE,此时COST代价是infinite无穷大
  2. 搜索执行:基于最优计划树搜索,最终得到COST代价最优的计划树,此时COST代价是有限的

CBO最优计划树搜索基于贪心算法和自顶向下动态规划实现,遵循动态规划的最优子结构原理,局部最优可最终得到全局最优。因此,在Memo搜索空间中,可以自顶向下从物理属性相同的RelSubset中选择最优代价的子节点,组合得到最优计划树。

构建最优计划树流程如下图所示:从根节点(Root节点)出发

  1. rel#41 等价集中 EnumerableProject 代价最低,对应子节点为 rel#58
  2. rel#58 等价集中 EnumerableFilter 代价最低,对应子节点为 rel#63
  3. rel#63 等价集中 JdbcToEnumerableConverter 代价最低,对应子节点为 rel#26
  4. rel#26 等价集中 JdbcTableScan 代价最低,且该节点为TableScan叶子节点

统计元数据

Calcite统计元数据体系如下所示,基于 RelNode#computeSelfCost 获取当前节点COST代价,注入RelMetadataProvider,基于 JaninoRelMetadataProvider 动态生成。常用的统计元数据调用处理:

  • RelNode非累计COST代价:RelMetadataQuery#getNonCumulativeCost → RelMdPercentageOriginalRows → RelMdPercentageOriginalRows#getNonCumulativeCost → RelNode#computeSelfCost
  • RelNode数据行数:RelMdRowCount#getRowCount → RelNode#estimateRowCount
  • RelNode最大行数:RelMdMaxRowCount#getMaxRowCount
  • RelNode NDV统计:RelMdDistinctRowCount#getDistinctRowCount
  • RelNode数据排序:RelMdCollation#collations
  • RelNode字段类型:RelMdNodeTypes#getNodeTypes
  • 判断表字段是否为Unique:RelMdColumnUniqueness#areColumnsUnique

Calling Convention

Calling Convention:实现不同Convention转换,在CBO优化阶段完成的。下图展示基于ConvertRule转换规则将计划树从Convention=NONE(代价无穷大infinite)的LogicalPlan转换为Convention=ENUMERABLE(代价有限)的可执行计划。

总结

查询优化器不仅是Calcite项目的核心模块,也是整体数据库系统的核心构建。一个好的查询优化器,可以优化SQL的执行计划逻辑,以更优、更高效的方式下发执行。本文介绍了Calcite优化器模块的执行详情,主要包括:优化规则、RBO优化器执行原理、CBO优化器执行原理、统计元数据等。 通过本文可以初步了解Calcite的设计思想:以优化规则为驱动,支持不同模式的优化执行:RBO是顺序执行,CBO则基于COST统计代价执行最优化选择。

我正在参与2024腾讯技术创作特训营最新征文,快来和我瓜分大奖!

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
如何使用calcite rule做SQL重写(上)
各位读者朋友,我想死你们了,今天我带着 calcite这个专题的第三篇文章来了,今天我们来说说sql重写,这可能也是大家都有需求的方面,我计划这个专题分为三篇来写:
麒思妙想
2023/08/28
1.9K0
如何使用calcite rule做SQL重写(上)
腾讯大数据|天穹SuperSQL执行核心剖析
1. 数据孤岛:由于历史原因以及不同数据中心的业务差异性,众多异构数据源形成了数据孤岛,导致大量且繁重的人工数据搬迁。与此同时,由于不同国家的数据安全法限制,很多数据无法搬迁,数据安全和查询效率都难以保证
腾讯大数据
2024/04/28
1.8K0
腾讯大数据|天穹SuperSQL执行核心剖析
Calcite系列(五):执行流程-概览
SQL执行流程有一套通用的步骤,尽管具体的实现可能会因数据库系统的不同而有所差异,但流程相对固定。以下是通用的SQL处理流程:
Yiwenwu
2024/04/18
5430
Apache Calcite原理极简入门
Apache Calcite 是独立于存储与执行的SQL解析、优化引擎,广泛应用于各种离线、搜索、实时查询引擎,如Drill、Hive、Kylin、Solr、flink、Samza等。本文结合hive中基于代价的优化,解析calcite优化引擎的实现原理。
大数据真好玩
2020/06/07
2.5K0
Calcite系列(一):背景介绍
Apache Calcite是一款开源的动态数据管理框架,提供了标准的 SQL 语言、查询优化和连接各种数据源的能力,但不包括数据存储、处理数据的算法和存储元数据的存储库。
Yiwenwu
2024/04/14
1.1K1
【Flink SQL】Apache Calcite 架构剖析
Apache Calcite 是一个动态的数据管理框架, 可以实现 SQL 的解析、验证、优化和执行。Calcite 是模块化和插件式的, 解析、验证、优化和执行的步骤都对应着一个相对独立的模块。用户可以选择使用其中的一个或多个模块,也可以对任意模型进行定制化扩展。
王知无-import_bigdata
2023/04/07
1.1K0
【Flink SQL】Apache Calcite 架构剖析
Calcite系列(三):核心概念-Convention
Convention:Calcite设计的核心概念,代表一类特定的数据源或执行引擎,基于Convention可生成与具体数据源或者引擎相关的执行计划。Calcite初始逻辑计划的所有树节点Convention=NONE,此时CBO代价无穷大,基于Calcite内置执行器无法直接执行。只有将所有计划树节点都转为可执行Convention才可基于Calcite执行,该转换过程可等价理解为从逻辑计划转为物理计划。
Yiwenwu
2024/04/16
5490
Hive优化器原理与源码解析系列--优化规则SortRemoveRule(一)
目前,数据库优化器分两种,一种是基于规则优化器;另一种是基于成本优化器,这两种优化器各有千秋。但现在大部分成熟的数据库优化器都是两种优化器结合起来使用,这样做为了优化器在执行计划Plan的构建速度和准确性之间找到一个好的平衡点。
用户7600169
2022/04/25
5470
Hive优化器原理与源码解析系列--优化规则SortRemoveRule(一)
Calcite系列(二):核心概念-关系代数
关系模型是一种用于数据库管理的理论框架,其基础建立在数学的集合论之上。该模型由Edgar F. Codd 于1970年提出,旨在以一种严格且理论化的方式来描述数据之间的关系,使得数据操作能够通过一系列关系代数来表达。关系模型主要由以下三部分组成:
Yiwenwu
2024/04/15
8010
如何使用calcite rule做SQL重写(下)
上一篇文章我们介绍了如何使用默认规则做条件下推,今天我们来尝试自定义规则,来实现对SQL的重写。我们本期将会深入浅出的以修改查询表为例,进行Sql rewrite,这应该在我们湖仓一体的架构中,处于核心地位的需求。我们今天就深入浅出的来做一个案例 Select * from consumers 实际查询则为 Select * from consumers_1,这个需求在分库分表里应该也很常见。
麒思妙想
2023/09/12
1.3K1
如何使用calcite rule做SQL重写(下)
Calcite技术研究
Apache Calcite是一个基础的软件框架,它提供了查询处理、查询优化以及查询语言支持的能力。很多流行的开源数据处理系统例如Apache Hive,Apache Storm,ApacheFlink,Druid等都采用了它。
Fayson
2020/02/24
2.4K0
Calcite技术研究
SQL处理流程与优化器 | 青训营笔记
一条SQL语句的处理流程包含**解析(Parser)、解析(Analyzer)、优化(Optimizer)、执行(Execution)**过程。
鳄鱼儿
2024/05/21
1380
SQL处理流程与优化器 | 青训营笔记
SQL查询优化器
一般的,数据库管理系统(DBMS)有通用的架构模型,可分为四个模块:传输通信、查询处理器、执行引擎、存储引擎。其中查询处理器包括查询解析器和查询优化器,而查询优化器是实现SQL计划树优化的核心。查询处理器的处理流程如下图所示,查询优化的执行过程包括两个关键阶段:
Yiwenwu
2024/06/29
7860
SQL查询优化器
Apache Calcite 论文学习笔记
特别声明:本文来源于掘金,“预留”发表的[Apache Calcite 论文学习笔记](https://juejin.im/post/5d2ed6a96fb9a07eea32a6ff)
叁金
2019/07/22
1.5K0
Hive优化器原理与源码解析系列—统计信息之选择性
Hive优化器是使用Apache Calcite动态数据管理框架实现的,其中包含VolcanoPlanner基于成本优化器(CBO)和HelpPlaner基于规则的启发式优化器(RBO)优化器。根据用户HiveConf配置信息使用不同的优化器。
用户7600169
2022/04/25
1.5K0
Spark SQL底层执行流程详解(好文收藏)
一、Apache Spark 二、Spark SQL发展历程 三、Spark SQL底层执行原理 四、Catalyst 的两大优化
五分钟学大数据
2022/05/22
5K0
Spark SQL底层执行流程详解(好文收藏)
[源码分析] 带你梳理 Flink SQL / Table API内部执行流程
本文将简述Flink SQL / Table API的内部实现,为大家把 "从SQL语句到具体执行" 这个流程串起来。并且尽量多提供调用栈,这样大家在遇到问题时就知道应该从什么地方设置断点,对整体架构理解也能更加深入。
罗西的思考
2020/09/07
3.3K0
Apache Calcite 功能简析及在 Flink 的应用
• Apache Calcite 是一个动态数据的管理框架,可以用来构建数据库系统的语法解析模块
KyleMeow
2018/09/02
8K0
Apache Calcite 功能简析及在 Flink 的应用
Calcite系列(四):核心概念-Adapter
Calcite作为SQL中间件,为提供扩展性并适配不同数据源,设计了Adapter适配器方式对接异构数据源,允许Calcite连接到不同类型的数据源。Adapter会根据数据源特性进行查询优化,并负责将Calcite的逻辑查询转换为可以在特定数据源上执行。
Yiwenwu
2024/04/17
6190
Hive CBO优化剖析
Hive是较早的SQL on Hadoop系统,对大数据SQL执行有广泛和深远的影响。它最初由Facebook开发,后来成为Apache软件基金会的一个开源项目。用户可以通过SQL来读取、写入和管理存储在分布式存储系统中的大规模数据集。
Yiwenwu
2024/04/26
6170
Hive CBO优化剖析
相关推荐
如何使用calcite rule做SQL重写(上)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档