本篇文章来源于火山引擎ByteHouse技术专家《ByteHouse查询优化器的设计与实现》的分享，从现状分析、设计思路、实现方案、高阶优化、优化效果五个部分，拆解ByteHouse查询优化器如何实现复杂查询和性能提升。
文｜ByteHouse团队 景鹏
作为企业级数据库的核心组件之一，查询优化器的地位不可忽视。对于众多依赖数据分析的现代企业来说，一个强大且完善的查询优化器能够为数据管理和分析工作带来巨大的便利。
作为一款火山引擎推出的云原生数据仓库，ByteHouse基于开源ClickHouse构建，并在字节跳动内外部场景的检验下，对OLAP引擎能力、性能、运维、架构进一步升级。ClickHouse以快速处理数据而著名，但其查询优化器在处理多表查询和高维度数据时却显得力不从心。为了解决这一问题，火山引擎ByteHouse自研并推出了一款全新的查询优化器。
● ClickHouse 的存储引擎、向量化计算拥有独特的优势。
● ClickHouse缺乏复杂查询的优化以及执行能力，比如说多表 JOIN 的性能、子查询的执行，很多复杂的查询在 ClickHouse 上无法执行或者执行性能比较差。
● 社区在尝试构建 query plan 的概念和优化器相关的模块，但是现还处于比较初级的阶段。ClickHouse 下发执行查询的方式为：收到 SQL 的主 Server 完成解析，然后将解析完的结果重新生成 SQL 再发到其他 worker 上。这种方法能表达的信息是有限的，因为SQL 表达的信息只能通过下发该信息给其他 Server 去完成执行 。
● syntax analyze和 tree writer 相关的模块复杂，有很多历史遗留的问题，设计繁琐，所以在支持比较复杂的查询时有一定的局限性。
基于以上原因，ByteHouse团队重新实现了ClickHouse 的优化器。
首先，客户端传来SQL字符串，server 会将 SQL 字符串解析成AST，再将 AST 经过一系列的分析过程以及构建的过程构建出 query plan， query plan 经过一定的优化生成最好的计划，将分布式计划切成 plansegment 去下发执行。
紫色部分就是从 0 到 1 全部重新实现的优化器相关的模块。SQL 字符串经过Parser，再经过自研的优化器，最终会下发query plan 到 MPP 的执行引擎上进行执行，最终将结果返回给client。除了 Parser 以外到执行之前的其他模块全部进行重写，这能保证语法上和开源 ClickHouse的兼容，但是中间的分析和优化部分全部是自研的，而且对于下发查询的方式也做了一定的改变，并不是转化成 SQL 下发到其他 Server 上执行，而是下发完整的 query plan 到不同的机器上，然后用 MPP 的方式进行执行。
/ 主要模块 /
● 第一个模块是Analyzer，主要分两部分，一个是 query writer，一个是 query analyzer。query writer 是在 AST 级别对查询进行一定的改写，比如 with CTE/ view/ UDF 的简单内容的展开，包括特殊函数的替比如用户写的函数 count distinct 某一列最终会转化成另外的一个函数执行。这种简单的替换是在 AST 级别来做的。第二部分是 query analyzer，主要是对名字进行解析，对数据类型和语法的校验，最终将整个分析的结果抽象化成结构化的数据结构，用来辅助后面的 query plan 的构建。整个数据结构能描述查询其想要表达的语义，然后利用这个结构化的数据结构构建出 query plan。
● 第二个模块是plan builder：改进社区 QueryStep 内容；增加序列化反序列化；补充高级算子。
● 第三个模块是optimizer：RBO，CBO，分布式计划优化，高阶优化能力（Runtime Filter，CTE，物化视图改写）
● 第四个模块是Statistics：以 Histogram 为主的统计信息；自动收集和更新
● 第五个模块是Diagnosis Tools：Plan Explain，Explain Analyze，Plan Visualization，Plan Dump
优化器：经过规则的优化，把一个计划变成另外一个更好的计划。
Role Based Optimizer：根据优化规则对关系表达式进行转换，计划经过优化规则后会变成另外一个计划，同时原有计划会被裁剪掉，经过一系列转换后生成最终的执行计划。
Cost Based Optimizer：通过规则生成一系列计划，利用统计信息评估计划的代价，选择代价最低的作为最终计划。
除优化框架之外，还需要很多优化理论来应用这两个框架对计划进行变化。
主要有这四种能力：
● 基于关系代数的等价性 ：join 交换律于结合率
● 基于数据特性：唯一键，functional dependency
● 基于分布式数据库特性：exchange 插入，算子拆分
● 高级优化手段：物化视图，Runtime Filter
/ RBO /
RBO主要实现了两种优化改写框架：
● 基于 visitor 的改写框架
Top-Down / Botton-Up 的方式对 QueryPlan 做改写，适合于对上下文有依赖的优化规则。比如把predicate 不停向下传递，将每一个条件放到它最应该存在的地方，让它尽快执行。这需要从上到下全部链路进行改写并传递信息与优化。例如：predicate push down 和 Column pruning
● 基于Pattern-match
适合简单、通用的改写规则。例如：将两个连续的 filter 节点合并成一个，再替换完成优化，并不需要对整个查询改写。
利用这两种改写框架实现了常见的优化规则，比如列裁剪，表达式的简化以及子查询的结关联，谓词下推，冗余算子消除，Outer Join 转 Inner Join，算子下推存储、分布式算子拆分等常见的启发式优化能力。
/ RBO解关联 /
左边：SQL像是查一张表，但其过滤条件使用另一张表。子查询中既用了自己的列，又用外面主查询的列。子查询和主查询是有一定的互相依赖的关联查询,此查询是正常情况下很多数据库不能直接执行的。
右边：经过解关联之后的查询计划的样子，转换成常见的算子 join agg 等，这样查询就可以正常执行了。
/ CBO /
蓝色的 query plan经过右边的 optimize task 不停地扩展，利用右边黄色的 rule（比如 join reorder 和CTE）转化，中间的搜索空间会被扩充，然后计算 cost，最终会基于 cost 选择最好的 plan 作为最终输出结果。而且在优化的过程中，因为是一个分布数据库，所以会利用 property 的信息去生成分布式计划，同样也会将分布式计划的 cost 考虑在内并基于综合代价选择最优解。
详细展开一下 CBO 里内的每一个模块具体是怎样实现的。
/ CBO Cascades搜索框架 /
表格描述了在不同 join 表数量的情况下它真正表达的搜索空间是多大即阶乘级别的复杂度。10 个表已经是亿级别的量级，由于枚举数量庞大的逻辑执行计划是不现实的，所以利用 Cascades 的搜索框架Group 和 GroupExpr 来表达数量庞大的搜索空间，可以将 n 的阶乘复杂度的搜索空间来降低到 3 的 n 次方级别。这样在有限的时间内搜索出 10 表以内的所有的 join 情况，可大大地降低整个搜索时间以及存储空间。
/ CBO计划枚举 /
1. 规则
需要靠CBO的规则不停地扩充搜索空间，然后基于cost选出其中的最优解。扩充得越多，选出最优解可能性就更高。常见的CBO rule得到实现。例如：Inner Join Reorder，Left Join to Right Join，Pull Left through Inner以及CTE和Magic Set这样高级优化。
2.分布式计划
作为分布式数据库，ByteHouse会利用分布式的属性，将分布式计划的生成和搜索融合在同一个Cascades搜索框架内，最终基于代价来选择最优的分布式计划。
利用三种property来优化和生成分布式计划：
●
partitioning 是指数据如何分区的，每个数据分区内的数据是不相交的。例如第一个分区内的数据是AB，那第二个分区内数据是CD，所有 A 或者 B 都会在第一个分区内，所有 C 和 D 都会在第二个分区内。
●
grouping 和 sorting 描述的是数据行与行之间的关系。grouping 是相同值的数据都要连续地排布在一起，例如 BBA。sorting 被认为是对 grouping 的加强，它不但要连续的数据，而且是有序的，例如 AABB。
将分布式计划和 CBO 框架结合在一起。很多数据库的做法是用 CBO 生成一个计划，在这个计划上推导如何插入 exchange 的节点，这样有可能会丢失最优解，很多情况下可能是次优的 join order ，但加上生成的分布式计划，反而是全局最优的。
以a、b， c 三个表为例子，这两个橙色计划分别对应两个不同的单机计划（对于每一个单地计划，其实都可以扩容出多个分布式计划）。比如先进行 a join b，再 join c，这样的情况 a 表按 uid 进行repatition，这样 a b 都按 uid 进行分区之后，可以直接进行 join ，然后对 join 的结果再按 id 进行repatition，然后去和 c 进行join，这样的结果才是正确的。也可以不对a做repatition，对b做replicated。对于另一个单机计划来说，同样可以生成两种不同的数据分布方式。对四个计划评估代价是多少并基于 cost 选择最终的最优解。
/ Runtime Filter /
此查询是对 sales 表和 item 表进行 join。现对 item ID 做大于 1000 的过滤，利用过滤之后的 id 构建 filter，对 sales 用 filter 来过滤数据，过滤之后会让真正参与 join 的数据减少较少。相比于正常执行，这种优化大大减少左边表格的扫描量，效率更高。
但至于是否做这样的优化是需要做决策的，并不是所有 join 都能做这样的优化，而且优化是有一定代价的。决策和优化都需要优化器去决策。
/ CTE(common table expression) /
此查询有三种可能性， SQL 是对同一张表 join 了三次，但是有不同的过滤条件， V1、V2 都是对这张表的 current price 做了一个小于 1000 的一个过滤之后进行join，那 V3在过滤之后还做了一个 color = red 的过滤。
第一个计划只做了一遍 tablescan，把扫描结果用了三次，但没法利用到color列已经建了索引的能力。要扫描整个表，并在内存里做price＜1000的过滤。
第二个计划前两张表 V1 和 V2 是不可共享，V3 也不可共享，但是 V3 在扫描时可以利用 index scan 的能力，因为在 color列上建了索引，所以就用 index scan 的能力扫描数据，V3的扫描代价比较低。V1、V2做共享，V3进行独立扫描是最优的计。
至于哪一个更好，要利用 Cascades 进行全局搜索，枚举这些计划基于 cost 判断。
在没有优化器时，仅能完成 26 个SQL的查询，而且是在对一些 SQL 做了一定变换之后才能执行的。
添加优化器之后，ByteHouse能够正常跑完 TPC-DS的全部99 条查询，而且性能优秀。在之前同样支持的26 个查询中，它的性能得到了极大的提升。
--活动推荐--
ByteHouse白皮书即将发布， 揭秘如何让万台节点OLAP性能大涨 。欢迎通过海报查看详情，并报名参与发布会，赢取精美礼品！
产品介绍
火山引擎ByteHouse
统一的大数据分析平台。目前提供企业版和云数仓两种版本，企业版是基于开源的企业级分析型数据库，支持用户交互式分析PB级别数据，通过多种自研表引擎，灵活支持各类数据分析和应用；云数仓版作为云原生的数据分析平台，实现统一的离线和实时数据分析，并通过弹性扩展的计算层和分布式存储层，有效降低企业大数据分析。后台回复数字“6”了解产品
——相关阅读——
