更多技术交换、求职机会，欢送关注字节跳动数据平台微信公众号，回复【1】进入官网交换群
置信大家都对赫赫有名的 ClickHouse 有肯定的理解了，它弱小的数据分析性能让人印象粗浅。但在字节大量生产应用中，发现了 ClickHouse 仍然存在了肯定的限度。例如：
- 短少残缺的 upsert 和 delete 操作
- 多表关联查问能力弱
- 集群规模较大时可用性降落（对字节尤其如此）
- 没有资源隔离能力
因而，咱们决定将 ClickHouse 能力进行全方位增强，打造一款更弱小的数据分析平台。本篇将具体介绍咱们是如何构建 ClickHouse 的查问优化器。
查问优化器有多重要？
在传统的关系型数据库中，如 Oracle、DB2、MySQL，查问优化器都是作为几个最重要的外围组件之一。能够说，没有查问优化器的数据库是不残缺的。绝对 OLTP 而言在 OLAP 畛域中更是如此；对于剖析类场景，查问更为简单，打算好坏的差别更大。一个优良的查问优化器能够避免用户写出不好的 SQL 导致执行速度慢，可能精确的抉择出一条效率最高的执行门路，大幅度降低查问工夫。相应的，一个不好的查问优化器，甚至会让查问变慢。
常见的优化器逻辑分为两类，一类叫“基于规定的优化（RBO）”，另一类称为“基于代价的优化（CBO）”，理论利用过程中该当两类兼顾能力获得最佳成果。
基于规定的优化
依据优化规定对关系表达式进行转换，这里的转换是说一个关系表达式通过优化规定后会变成另外一个关系表达式，同时原有表达式会被裁剪掉，通过一系列转换后生成最终的执行打算。RBO 中蕴含了一套有着严格程序的优化规定，同样一条 SQL，无论读取的表中数据是怎么样的，最初生成的执行打算都是一样的。同时，在 RBO 中 SQL 写法的不同很有可能影响最终的执行打算，从而影响脚本性能。
基于代价的优化
依据优化规定对关系表达式进行转换，这里的转换是说一个关系表达式通过优化规定后会生成另外一个关系表达式，同时原有表达式也会保留，通过一系列转换后会生成多个执行打算，而后 CBO 会依据统计信息和代价模型 (Cost Model) 计算每个执行打算的 Cost，从中筛选 Cost 最小的执行打算。
ByteHouse 的查问优化器
目前支流的 OLAP 的引擎在查问优化器方面做的并不够好，尤其是 ClickHouse。家喻户晓 ClickHouse 以快著称，然而它的快是采纳了力大飞砖的形式，须要用户将数据事后生成大宽表，以防止过于简单的多表查问从而取得高性能。而代价是，每次维度变动或新需要都须要大量操作，以及在必须应用多表关联进行剖析的场景中显得非常有力。
作为一个企业级的 OLAP 数据库来说一个欠缺且弱小的优化器是必不可少的，因而，ByteHouse 从零开始自研的了查问优化器。
查问优化的残缺流程
上图形容了整个查问的执行流程，从 SQL parse 到执行期间所有内容全副进行了从新实现（其中紫色模块），构建了一套残缺的且标准的查问优化器。
次要功能模块
Analyzers
Analyzers 目录包含两局部性能：
- 一个是 QueryRewriter，一方面是通过 AST 改写的形式实现一些语法个性；咱们同时反对 Clickhouse SQL 和规范 SQL，所以另一方面是确保在 Clickhouse SQL 模式下 SQL 语义能和原生 Interpreter 执行模式统一。
- 另一个是 QueryAnalyzer，用于对改写完的 AST 进行语义的剖析和验证。Analyzer 辨别 ANSI SQL 和 Clickhouse SQL 两种模式。
QueryRewriter 针对 ANSI SQL 的改写次要有：
- With CTE/view 开展；
- UDF 开展；
- 特定函数的改写，比方将 count(*) 改写为 count()，将 countDistinct(…) 改写为 uniqExact(…)；
QueryRewriter 针对 Clickhouse SQL 的改写次要有：
- With CTE/view 开展；
- UDF 开展；
- 特定函数的改写；
- JoinToSubquery 开展，对应于 Interpreter 链路下的 JoinToSubqueryTransformVisitor；
- Qualified name 归一化，对应于 Interpreter 链路下的 TranslateQualifiedNamesVisitor；
- Alias 改写，对应于 Interpreter 链路下的 QueryNormalizer；
QueryAnalyzer 查问语义进行剖析和校验，将 AST 形象成出结构化的数据结构，为下一步构建 plan 提供数据。在该模块中规范 SQL 和 Clickhouse SQL 进行了辨别，一套代码同时兼容两种语义。
QueryPlan
在 Analyze 之后则是利用 Analyze 出的数据结构构建初始的查问打算。QueryPlan 是在社区的 QueryPlanStep 根底上改良而来，一方面减少了序列化 / 反序列化办法，为了打算下发执行基于 QueryPlan 并非 AST 或者 SQL 文本。另一方面是对社区中不合理的 Step 进行更改，让每个 Step 仅仅表白关系代数的语义而非很多执行相干的内容和参数，而这些执行相干的信息则是在每个执行的 server 上构建执行 pipeline 时才真正进行取得。
Optimizer
构建完执行打算后则是最为要害最初为外围的优化器模块。PlanOptimizer 类是查问优化的入口类，首先会基于 PlanPattern 对 SQL 的查问做一次粗粒度的分类，不同复杂度的查问应用不同的规定汇合，晋升效率。
优化器不论是 RBO 还是 CBO 实质上都是对查问做改写，只是改写的思路以及改写框架有不同的取舍。咱们实现了三种改写框架，用于解决不同的场景：
- 基于 visitor 的改写框架：能够 Top-Down，也能够 Botton-Up 的 形式对一个 QueryPlan 做改写，它比拟适宜于带有上下文依赖的优化规定，例如 PredicatePushDown，须要把 Predicate 一层层的往下推。
- 基于 pattern-match 的改写框架：这种适宜简略、通用的改写规定，例如对于两个间断的 Filter 做合并的动作，只有 QueryPlan 外面的 Sub Plan 合乎 Filter-Filter 这样的 pattern，就能够 match 对应的优化规定，进行改写。
- 基于 Cascade 的改写框架：通过遍历等价打算，并将所有的等价打算存储在一个内存空间中，而后评估每种等价打算的代价，进而抉择一种最优解。
查问优化器带来了什么
在性能方面，原生 Clickhouse 受限于短少查问优化器，对于 TPC-DS 测试集的 99 个 SQL 用例仅能失常运行很少一部分查问，即便通过手动改写 SQL 也仅能胜利运行 80% 的查问。在实现了欠缺的优化器之后能够间接运行全副 TPC-DS 原始 SQL，改良后的 Clickhouse 才这正能够算是可用的 OLAP 数据库。不仅仅是能够失常执行这些简单查问，而且效率也失去了很大的晋升，绝对在没优化器的状况下手动改写的 SQL，性能晋升 6 倍以上。在外部的一些业务场景中性能也有近 10 倍的晋升。
优化器的能力方面：
- RBO：反对：列裁剪、分区裁剪、表达式简化、子查问解关联、谓词下推、冗余算子打消、Outer-JOIN 转 INNER-JOIN、算子下推存储、分布式算子拆分等常见的启发式优化能力。
- CBO：基于 Cascade 搜寻框架，实现了高效的 Join 枚举算法，以及基于 Histogram 的代价估算，对 10 表全连贯级别规模的 Join Reorder 问题，可能全量枚举并寻求最优解，同时针对大于 10 表规模的 Join Reorder 反对启发式枚举并寻求最优解。CBO 反对基于规定扩大搜寻空间，除了常见的 Join Reorder 问题以外，还反对 Outer-Join/Join Reorder，Magic Set Placement 等相干优化能力。
- 分布式打算优化：面向分布式 MPP 数据库，生成分布式查问打算，并且和 CBO 联合在一起。绝对业界支流实现：分为两个阶段，首先寻求最优的单机版打算，而后将其分布式化。咱们的计划则是将这两个阶段交融在一起，在整个 CBO 寻求最优解的过程中，会联合分布式打算的诉求，从代价的角度抉择最优的分布式打算。对于 Join/Aggregate 的还反对 Partition 属性开展。
- 高阶优化能力：实现了 Dynamic Filter pushdown、单表物化视图改写、基于代价的 CTE（公共表达式共享）。
上面咱们用 TPC-DS 规范测试集，来为大家展示一下增加优化器前后的差异：
在没有优化器时，仅能实现 26 个 SQL 的查问。而增加了优化器后，可能残缺跑完 TPC-DS 的全副 99 个 SQL，并且在此前能实现的查问中，性能也失去了极大的晋升。
立刻跳转火山引擎 BytHouse 官网理解详情！