一条 SQL 的查询计划生成之旅【上】


背景

Apache Calcite 作为一款开源的动态数据管理框架,由于其模块化、可扩展、以及不和任何计算引擎绑定的特性,目前在开源项目和商业化产品中已得到广泛的应用。不仅 Apache Flink、Apache Druid、Apache Hive 等明星开源项目在使用 Calcite,腾讯天穹 Super SQL、阿里 MaxCompute、Dremio 等商业化产品的 SQL Planner 也都基于 Calcite 实现。Apache Calcite 俨然成为了 SQL Planner 层的黄金标准、事实趋势。

随着近些年大数据基础设施的不断发展成熟,SQL 已经无可争议地成为大数据计算引擎的主流语言,但与此同时,大量新兴计算引擎、数据库项目的出现,也产生了大量 SQL 方言,运维一个企业级大数据平台需要处理 SQL 的场景越来越多。学习和了解 Apache Calcite,既能帮助我们快速理解 SQL Planner 的原理机制,又能有助于我们利用 Calcite 快速解决以处理 SQL 为中心的各类日常问题(如实现一个SQL Parser、SQL Gateway、SQL Planner 等)。

我们计划从技术实战、原理讲解、源码分析等角度推出系列文章,来介绍如何利用 Apache Calcite 解决一些常见的具体问题,希望对数据平台工具研发的同学有一些帮助。本文是系列文章的第一篇,将首先介绍 Apache Calcite 的架构设计,同时以一条 SQL 在 Calcite 中的处理流程为主线,对 SQL 解析、元数据验证、执行计划生成及优化、SQL 方言转换等模块的关键原理进行阐述,让读者对 Apache Calcite 有一个初步印象。关于各模块更深入的原理讲解和源码实战,会在后面的系列文章中分篇进行展开。

目标和收益

本文主要讲解 Apache Calcite 的架构设计以及 Calcite 内部 SQL 优化方式,阅读本文,能够从以下几点帮助到你:

整体了解 Apache Calcite ,包括架构设计和核心模块。

从一条 SQL 处理流程视角出发,通过对 Calcite SQL 解析、校验、关系代数转换、RBO 和 CBO、物化视图改写和方言转换整体流程的讲解,带你了解一条 SQL 的 Calcite 之旅。

了解 Calcite 物化视图改写的两种方式及各自优缺点。

了解 Calcite 中优化器设计的关键细节,以及如何实现对 SQL 方言的改写。

希望阅读完本篇文章后,你能够对 Calcite 整体使用流程有一个初步的认识,下面我们进入正文。

一、Apache Calcite 架构概述

1.1 Apache Calcite 诞生背景

Apache Calcite 自 2013 年 11 月首次在 Github 上进行代码仓库初始化,距今已有 9 年时间。Apache Calcite 前身其实是 optiq。optiq 最开始则是在 Hive 项目中进行使用,其主要目的是为 Hive 提供基于成本模型的优化器。2014 年 5 月 optiq 独立出来,成为 Apache 社区的孵化项目,同年 9 月正式更名为 Apache Calcite。Calcite 的作者是 Julian Hyde,他早期还写过 Mondrian OLAP Engine 和 olap4j API,目前他不仅是 Calcite 的 VP,同时也是 Apache Arrow、Apache Drill、Apache Druid、Apache Kylin 等开源项目的 PMC。

Apache Calcite 设计的核心目标:“One planner fits all”,它期望在异构引擎、异构存储之上,提供统一的数据管理能力,同时还提供基于关系代数的优化器,它的内部各个模块都是可扩展的,也正是因为这种设计理念,Apache Calcite 才会被众多其他开源项目所使用。

1.2 Apache Calcite 架构设计

Apache Calcite 整体是按模块化进行设计,各个模块支持可扩展,比如 SQL 语法文件、元数据、Transformation Rule(逻辑转换规则)和 Implementation Rule(物理转换规则)、CBO 元数据获取的 Metadata Handler、自定义RelNode 和 SqlNode类型等等,同时 Calcite 底层也支持不同引擎的 SQL 方言转换。对于 SQL Planner 的优化框架,整体上 Calcite 已经搭建好,我们可以直接自定义扩展需要的差异化特性。下面是 Calcite 各模块的架构设计示意图:

上图中的所有模块都可自定义实现,接下来让我们对各模块一一进行说明:

1、JDBC Client 和 JDBC Server,主要负责一个 SQL 的请求响应和结果返回,可以基于 Calcite 子项目 Avatica 框架来进行实现。

2、SQL Parser 和 Validator,Parser 主要负责对一个 SQL 进行解析,生成 AST 树。Validator 主要是验证 SQL 的元数据合法性。

3、Operator Expressions,则是将一棵 AST Tree 转换为 RelNode关系代数的计划树,这样优化器才能识别和优化。

4、Query Optimizer,Calcite 优化器模块,有 RBO 和 CBO 优化器,即对 Query 的关系代数计划树做优化

5、Metadata Providers,CBO 优化器计算 Cost 时,所需元数据的提供者,包括:Selectivity(选择率)、RowCount、DistinctRowCount 等等。

6、Pluggable Rules,Calcite 优化规则模块,Calcite 主要有:Transformation Rule(逻辑优化规则)和 ConverterRule(Implementation Rule),用户可以自定义可扩展。

以上我们是从 Calcite 模块组成视角来进行理解的,那么下面从 Calcite 底层核心源代码类调用流转逻辑来看:

一个 SQL 的处理逻辑,会使用SqlParser 将 SQL 解析为 SqlNode,使SqlValidator来进行 SQL 校验,使用SqlToRelConverter来将SqlNode 转换为RelNode关系代数,使用 RelOptPlanner(具体有HepPlanner 和VolcanoPlanner )来进行计划优化,同时可以通过扩展RelOptRule 、BuiltInMetadata 的实现,来自定义 SQL 优化器的逻辑。CalCite 这种可扩展的设计逻辑,极大的方便开发同学去自定义 SQL 引擎 Planner 逻辑,同时避免大家重复造轮子。

下图为 Calcite 底层核心代码调用流转示意:

二、SQL 查询优化器概述

2.1 SQL 查询优化器的用途

SQL 作为一种声明式的查询语言,能够让很多技术以及非技术人员快速入门和掌握,用户能够使用 SQL 快速完成业务层的查询语义逻辑的编写。但单纯的 SQL 语言,是无法直接让底层的计算引擎识别和运行的。当 SQL 查询请求发送到底层数据库时,需要将 SQL 查询语句转换为底层数据库的计算引擎能够识别的模型约定定义(比如执行计划描述),最终让底层计算引擎按照预定的计算逻辑执行并返回结果。

对于 SQL 优化器的核心用途:即对用户输入的 SQL 查询语句,将其转换为计算引擎能够识别和计算的执行计划,由于最终转换的可以运行计划有很多种情形,所以优化器需要从中选取一个最优的执行计划,下发到计算引擎执行。这里最优既可以结合我们的先验经验来判定,同时也可以从一个执行计划使用到的物理资源进行考量,比如使用的 CPU、内存、磁盘 IO、网络 IO、CPU LRU Cache 等等。SQL 优化器的核心逻辑:就是对关系代数计划做等价转换,在不改变计划语义的情况下,尽可能最大化的对关系代数计划做优化。

2.2 SQL 查询优化器的优化方式

常见的 SQL 优化有两种方式:RBO 优化(基于先验经验的启发式规则优化)和 CBO 优化(基于计算成本的优化)。RBO 主要是使用一些预定义的先验且有收益的优化规则集合,来对 SQL 进行优化,常见的有:常量折叠、谓词下推、列裁剪、关联子查询消除等优化规则。下图以谓词下推优化举例:


上图左边是原始 SQL 计划,可以看到,通过 Filter 谓词下推规则优化后,Filter 节点已经下推到了 Join 节点之下,这样能够提前对 Scan 节点的数据进行过滤,最终减少进入到 Join 算子的数据量,减少 Join 节点的计算成本。

当然,根据先验经验主义的优化方式也存在缺陷,可能在部分场景,由于没有考虑到 SQL 在真实环境下的实际运行情况,其执行效率并不是最优的,所以就有了基于 Cost 的优化方式(CBO)。CBO 优化,则是在期望的物理特质下,通过对不同物理计划运行所需要的成本进行估算,使用动态规划,来选择一个计算成本最优的物理计划。一般 Cost 包括:CPU、内存、磁盘 IO、网络 IO 等等。

当然,随着技术的演进,现在在 RBO 优化阶段,其实也可以基于 Cost 来评估某些优化规则是否应该使用。这里以 Group By(聚合) 下推举例:


在上图中,如果 LogicalJoin 之后的基数(输出的行数)如果比 LogicalTableScan[A] 后的基数要小的话,Aggregate 不下推,其实会比下推更节约资源。但完全进入 CBO 阶段,如果计划搜索空间过大的话,CBO 找出最优计划的耗时可能又很久。所以在使用 RBO 优化规则时,某些规则可以比较转换前后的计划的 Cost ,来决定是否应用该规则。目前业界像 Oracle 和 MemSQL(SingStoreDB)在它们的优化器都已经这样进行实现。

2.3 SQL 查询优化器的框架类型

目前业界的 SQL 优化器框架类型有:Volcano、Cascades、Columbia、Orca 等优化器框架,比较主流的优化器框架为 Cascades,像微软的 SQL Server、阿里 ADB、PingCAP 的 TIDB、CockroachDB、StarRocks 这些商业化产品,其 SQL 优化器都是基于 Cascades 优化器框架的。

Columbia、Orca 这两款优化器框架都是在 Cascades 优化器基础上,做了部分改良和优化。以 Columbia 优化器框架举例,其在 Cascades 优化器基础上,对于搜索计划空间剪枝做得更好,不仅能够基于 Group 空间计划剪枝,同时也能够做全局计划剪枝,这样在一个可以接收并近似最优计划的前提下,通过剪枝来减少 Plan 空间搜索的时间,提升查询性能。Orca 则是能够作为独立的优化器在数据库系统之外运行,这样的好处在于优化器不需要和数据库系统紧密耦合在一起,但需要提供一种能够和数据库系统的交互通信机制来处理查询。

Cascades 优化器相对于 Volcano 优化器最大的区别在于:Volcano 优化器会先尽可能枚举所有的执行计划空间,然后再从中找出最优的执行计划。而 Cascades 优化器能够在搜索过程中,对空间搜索计划进行剪枝,使得搜索的执行计划空间不会像 Vocano 那么大,但也可以获得一个相对较好的执行计划,这样通过减少空间计划的搜索时间,来降低 SQL Planning 的耗时,从而提升查询性能。

2.4 一条 SQL 在 Apache Calcite 的优化旅程

在一个典型的 SQL 查询服务中,从用户输入一条 SQL 语句开始,到最终结果返回到 Client,一般会经过:Client 端 SQL 查询请求、服务端接收到 SQL 请求和内部作业构建、SQL 解析、SQL 校验、SQL 优化,继而形成物理计划。如果底层有自己的计算引擎,还可以将物理计划转换为执行计划,下发到计算节点并执行。如果底层计算引擎是其他引擎的话,可以将物理计划翻译成对应引擎的 SQL 方言,然后提交到对应引擎执行。

为了方便读者更具象地理解Aapche Calcite的每个模块的运作细节,本文选择了从第二种方式出发,以实现一个SQL优化改写器为例,来展开介绍一条SQL在 Apache Calcite是如何完成解析、优化与改写的。


如上图所示,一条 SQL 整体处理流程分为以下几个步骤:

当 Client 层发起一条 SQL 请求时,请求会到 JDBC Server 端,JDBC Server 端底层一般可以是 GRPC 服务或者 HTTP 服务,在 Calcite 中,也可以使用 Calcite Avatica 来做 JDBC 服务端和 Driver 层的代码开发。

服务端接收到 SQL 请求后,会在内部构建出一个 Job 作业请求,同时提交到内部作业服务,之后会进入到 SQL 链路处理流程中。

在 SQL 处理流程中,第一步则是将 SQL 解析成一棵 SqlNode 的 AST 抽象语法树,这个过程中会做 SQL 词法和语法的校验。之后会进入到 SQL 验证阶段,SQL 验证阶段主要对 SQL 的语义进行验证,比如查询的数据表是否存在、函数是否存在、函数参数数据类型是否匹配等等。元数据验证完之后,其输出本质还是一棵 SqlNode 树,接下来会将 SqlNode Tree 转换为一棵RelNode 关系代数 Tree,同时进入到 SQL 优化阶段。

在 Calcite 中,RBO 优化主要使用HepPlanner类来进行实现。CBO 优化,则是使用 VolcanoPlanner来进行实现,RBO 规则和 CBO 规则都支持自定义扩展。

经过 SQL 优化器的优化,会产出最优的物理计划。但这还无法最终运行,还需要将物理计划转化为底层计算引擎的 SQL 方言,进行作业的提交和计算。

本次先分享到这里,下一篇,我们将进入 Apache Calcite 各组件模块关键原理解析。最后,如果你对数据虚拟化、Calcite 原理技术、湖仓平台、SQL 优化器感兴趣的话,欢迎关注“Aloudata技术团队”公众号。



✎ 本文作者/ 沈浪,Aloudata OLAP 引擎研发专家, 毕业于电子科技大学,曾就职于阿里、有赞、字节的基础设施团队,参与数据仓库、实时计算、数据湖核心研发,现负责Aloudata 湖仓查询引擎 SQL 查询优化器的研发工作。



Aloudata浙江大应科技-技术部诚聘Java技术专家/高级技术专家,高级数据库内核研发专家,Base杭州。同时,我们针对24届实习生招聘已经开始啦,欢迎有兴趣的同学投递简历至:wuque.hua@aloudata.com。积蓄星火,以待磅礴,Aloudata技术团队期待与你共同探索NoETL新世界,领跑数据智能新未来!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,482评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,377评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,762评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,273评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,289评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,046评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,351评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,988评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,476评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,948评论 2 324
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,064评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,712评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,261评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,264评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,486评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,511评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,802评论 2 345

推荐阅读更多精彩内容