作为企业级数据库的核心组件之一，查询优化器的地位不可忽视。关于众多依靠数据剖析的现代企业来说，一个强大且完善的查询优化器能够为数据管理和剖析工作带来巨大的便利。作为一款火山引擎推出的云原生数据仓库，ByteHouse根据开源ClickHouse构建，并在字节跳动内外部场景的查验下，对OLAP引擎才干、功能、运维、架构进一步晋级。ClickHouse以快速处理数据而著名，但其查询优化器在处理多表查询和高维度数据时却显得无能为力。为了处理这一问题，火山引擎ByteHouse自研并推出了一款全新的查询优化器。本篇文章来源于火山引擎ByteHouse技能专家《ByteHouse查询优化器的规划与完结》的分享，从现状剖析、规划思路、完结方案、高阶优化、优化作用五个部分，拆解ByteHouse查询优化器怎么完结功能10倍提高。现状剖析ClickHouse 的存储引擎、向量化核算具有共同的优势。ClickHouse缺乏杂乱查询的优化以及履行才干，比方说多表 JOIN 的功能、子查询的履行，有许多的杂乱的查询在 ClickHouse 上是无法履行的或许履行功能比较差。社区在测验构建 query plan 的概念和优化器相关的模块，可是现还处于比较初级的阶段。并且 ClickHouse 的下发履行查询的方法比较独特：收到 SQL 的主 Server 会做必定的解析，然后会将解析完的成果又从头生成一个 SQL 再发到其他的 worker 上。这种办法能表达的信息是有限的，SQL 能表达什么样的信息，它其实就只能下发这样这些信息给其他的 Server 去履行。syntax analyze和 tree writer 相关的模块杂乱，有许多历史遗留的问题，规划上比较繁琐，所以在支持一些比较杂乱的查询的时分它有必定的局限性。规划思路根据以上原因，ByteHouse团队从头完结了ClickHouse 的优化器，左边的是ByteHouse的查询优化器的数据流相关的部分。首要客户端传来一条 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 FilterRBORBO首要完结了两种优化改写结构：根据 visitor 的改写结构Top-Down / Botton-Up 的方法对一个 QueryPlan 做改写，适合于对上下文有依靠的优化规矩。比方说把一个predicate 不断向下传递，将每一个条件放到它最应该存在的地方，让它尽量早地履行。这需求从上到下悉数链路进行改写并传递信息进行优化。例如：predicate push down 和 Column pruning根据Pattern-match适合简略、通用的改写规矩。例如：将两个接连的 filter 节点合并成一个，这样关注接连的两个是 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方案枚举规矩需求靠CBO的规矩不断地扩大查找空间，然后根据cost选出其中的最优解，扩大得越多，选出最优解可能性就更高。咱们也完结了常见的 CBO rule。例如：Inner Join Reorder，Left Join to Right Join，Pull Left through Inner以及CTE和Magic Set这样高档优化。散布式方案作为散布式数据库，ByteHouse会使用散布式的属性，将散布式方案的生成和查找融合在同一个Cascades查找结构内，终究根据价值来挑选最优的散布式方案。使用三种property来优化和生成散布式方案：partitioning 是指数据是怎么分区的，每个数据分区内的数据是不相交的。例如第一个分区内的数据是AB，那第二个分区内数据是CD，所有 A 或许 B 都会在第一个分区内，所有 C 和 D 都会在第二个分区内。grouping 和 sorting 描绘的是数据行与行之间的关系。grouping 是相同值的数据都要接连地排布在一同，例如 BBA。sorting 被认为是一对 grouping 的加强，它不但要接连的数据在一同，并且是要有序的，例如 AABB。咱们将散布式方案和 CBO 结构结合在了一同。许多数据库的做法是用 CBO 先生成一个方案，在这个方案上推导怎么插入 exchange 的节点，这样有可能会 miss 掉最优解，许多情况下可能是一个次优的 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 Fliter此查询是对 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的扫描价值比较低。这些方案都不是最好的，应该让前面两个做同享，然后第三个自己独立的扫描，这才是最优的一个方案。至于哪一个更好，要使用 Cascades 全局地去查找，枚举这些方案，根据 cost 判别。优化作用在没有优化器的时，仅能完结 26 个SQL的查询，并且是在对一些 SQL 做了必定改换之后才干履行的。增加优化器之后，ByteHouse能够正常跑完 TPC-DS的悉数99 条查询，并且它的功能也是比较不错的。在之前相同都能支持的26 个查询中，它的功能也得到了极大的提高。

版权免责声明: 本站内容部分来源于网络，请自行鉴定真假。如有侵权，违法，恶意广告，虚假欺骗行为等以上问题联系我们删除。
本文地址：https://81396.com/article/152.html