数据库|如何打造一款极速数据湖分析引擎( 二 ) 算法|CPU

随着用户对于数据质量的要求越来越高，数据湖开始丰富其他能力。例如为用户提供类似数据库的 ACID 语义，帮助用户在持续写入数据的过程中能够拿到 point-in-time 的视图，防止读取数据过程中出现各种错误。或者是提供用户更高性能的数据导入能力等，发展到现在，数据湖已经从单纯的元数据管理变成现在拥有更加丰富，更加类似数据库的语义了。
用一句不太准确的话描述数据湖，就是一个存储成本更廉价的“AP 数据库” 。但是数据湖仅仅提供数据存储和组织的能力，一个完整的数据库不仅要有数据存储的能力，还需要有数据分析能力。因此怎么为数据湖打造一款高效的分析引擎，为用户提供洞察数据的能力，将是本文所要重点阐述的部分。下面通过如下几个章节一起逐步拆解一款现代的 OLAP 分析引擎的内部构造和实现：
怎么在数据湖上进行极速分析现代数据湖分析引擎的架构怎么在数据湖上进行极速分析？从这一节开始，让我们开始回到数据库课程，一个用于数据湖的分析引擎和一个用于数据库的分析引擎在架构上别无二致，通常我们认为都会分为下面几个部分：
Parser：将用户输入的查询语句解析成一棵抽象语法树 Analyzer：分析查询语句的语法和语义是否正确，符合定义 Optimizer：为查询生成性能更高、代价更低的物理查询计划 Execution Engine：执行物理查询计划，收集并返回查询结果对于一个数据湖分析引擎而言， Optimizer 和 Execution Engine 是影响其性能两个核心模块，下面我们将从三个维度入手，逐一拆解这两个模块的核心技术原理，并通过不同技术方案的对比，帮助读者理解一个现代的数据湖分析引擎的始末。
RBO vs CBO
基本上来讲，优化器的工作就是对给定的一个查询，生成查询代价最低（或者相对较低）的执行计划。不同的执行计划性能会有成千上万倍的差距，查询越复杂，数据量越大，查询优化越重要。
Rule Based Optimization (RBO) 是传统分析引擎常用的优化策略。 RBO 的本质是核心是基于关系代数的等价变换，通过一套预先制定好的规则来变换查询，从而获得代价更低的执行计划。常见的 RBO 规则谓词下推、Limit 下推、常量折叠等。在 RBO 中，有着一套严格的使用规则，只要你按照规则去写查询语句，无论数据表中的内容怎样，生成的执行计划都是固定的。但是在实际的业务环境中，数据的量级会严重影响查询的性能，而 RBO 是没法通过这些信息来获取更优的执行计划。
为了解决 RBO 的局限性， Cost Based Optimization (CBO) 的优化策略应运而生。 CBO 通过收集数据的统计信息来估算执行计划的代价，这些统计信息包括数据集的大小，列的数量和列的基数等信息。举个例子，假设我们现在有三张表 A ， B 和 C ，在进行 A join B join C 的查询时如果没有对应的统计信息我们是无法判断不同 join 的执行顺序代价上的差异。如果我们收集到这三张表的统计信息，发现 A 表和 B 表的数据量都是 1M 行，但是 C 表的数据量仅为 10 行，那么通过先执行 B join C 可以大大减少中间结果的数据量，这在没有统计信息的情况下基本不可能判断。
随着查询复杂度的增加，执行计划的状态空间会变的非常巨大。刷过算法题的小伙伴都知道，一旦状态空间非常大，通过暴力搜索的方式是不可能 AC 的，这时候一个好的搜索算法格外重要。通常 CBO 使用动态规划算法来得到最优解，并且减少重复计算子空间的代价。当状态空间达到一定程度之后，我们只能选择贪心算法或者其他一些启发式算法来得到局部最优。本质上搜索算法是一种在搜索时间和结果质量做 trade-off 的方法。