关于sql:一条-SQL-的查询计划生成之旅上

1次阅读

共计 5721 个字符，预计需要花费 15 分钟才能阅读完成。

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 自 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 才会被泛滥其余开源我的项目所应用。

Apache Calcite 整体是按模块化进行设计，各个模块反对可扩大，比方 SQL 语法文件、元数据、Transformation Rule（逻辑转换规则）和 Implementation Rule（物理转换规则）、CBO 元数据获取的 Metadata Handler、自定义 RelNode 和 SqlNode 类型等等，同时 Calcite 底层也反对不同引擎的 SQL 方言转换。对于 SQL Planner 的优化框架，整体上 Calcite 曾经搭建实现，咱们能够间接自定义扩大所须要的差异化个性。上面是 Calcite 各模块的架构设计示意图：

上图中的所有模块都可自定义实现，接下来让咱们对各模块一一进行阐明：

JDBC Client 和 JDBC Server，次要负责一个 SQL 的申请响应和后果返回，能够基于 Calcite 子项目 Avatica 框架来进行实现。
SQL Parser 和 Validator，Parser 次要负责对一个 SQL 进行解析，生成 AST 树。Validator 次要是验证 SQL 的元数据合法性。
Operator Expressions，则是将一棵 AST Tree 转换为 RelNode 关系代数的打算树，这样优化器能力辨认和优化。
Query Optimizer 是 Calcite 优化器模块，有 RBO 和 CBO 优化器，即对 Query 的关系代数打算树做优化。
Metadata Providers 是 CBO 优化器计算 Cost 时所需元数据的提供者，包含：Selectivity（选择率）、RowCount、DistinctRowCount 等等。
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 作为一种申明式的查询语言，可能让很多技术以及非技术人员疾速入门和把握，用户可能应用 SQL 疾速实现业务层的查问语义逻辑的编写。但单纯的 SQL 语言，是无奈间接让底层计算引擎辨认和运行的。当 SQL 查问申请发送到底层数据库时，须要将 SQL 查问语句转换为底层数据库的计算引擎可能辨认的模型约定定义（比方执行打算形容），最终让底层计算引擎依照预约的计算逻辑执行并返回后果。

对于 SQL 优化器的外围用处— 将用户输出的 SQL 查问语句转换为计算引擎可能辨认和计算的执行打算，因为最终转换的可运行打算有多种情景，所以优化器须要从中选取一个最优的执行打算，下发到计算引擎执行。这里所谓的“最优”既能够联合咱们的先验教训来断定，同时也能够从一个执行打算应用到的物理资源进行考量，比方应用的 CPU、内存、磁盘 IO、网络 IO、CPU LRU Cache 等等。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）的优化器都曾经依照这种形式进行实现。

目前业界的 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 的耗时，从而晋升查问性能。

在一个典型的 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 Tree，接下来会将 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 新世界，领跑数据智能新将来！

正文完