万字长文揭秘：阿里如何实现海量数据实时分析？(6)

使用全列索引给设计带来了一个很大挑战：需要对大量数据构建索引，这会是一个非常耗时的过程。如果像传统数据库那样在数据写入的路径上进行索引构建，那么这会严重影响写入的吞吐，而且会严重拖慢查询的性能，影响用户体验。为了解决这个挑战，玄武采用了异步构建索引的方式。当写入请求到达后，玄武把写SQL持久化到盘古，然后直接返回，并不进行索引的构建。

[本文来自：www.11jj.com]

当这些未构建索引的数据（称为实时数据）积累到一定数量时，玄武会开启多个MapReduce任务，来对这些实时数据进行索引的构建，并将实时数据及其索引，同当前版本的基线数据（历史数据）及其索引进行多版本归并,形成新版本的基线数据和索引。这些MapReduce任务通过伏羲进行分布式调度和执行，异步地完成索引的构建。这种异步构建索引的方式，既不影响AnalyticDB的高吞吐写入，也不影响AnalyticDB的高性能查询。

异步构建索引的机制还会引入一个新问题：在进行MapReduce构建索引的任务之前，新写入的实时数据是没有索引的，如果用户的查询会涉及到实时数据，查询性能有可能会受到影响。玄武采用为实时数据构建排序索引（Sorted Index）的机制来解决这个问题。

如下图所示，玄武在将实时数据以block形式刷到磁盘之前，会根据每一列的实时数据生成对应的排序索引。排序索引实际是一个行号数组，对于升序排序索引来说，行号数组的第一个数值是实时数据最小值对应的行号，第二个数值是实时数据第二小值对应的行号，以此类推。这种情况下，对实时数据的搜索复杂度会从O(N)降低为O(lgN)。排序索引大小通常很小（60KB左右），因此，排序索引可以缓存在内存中，以加速查询。

羲和计算引擎

针对低延迟高并发的在线分析场景需求，AnalyticDB自研了羲和大规模分析引擎，其中包括了基于流水线模型的分布式并行计算引擎，以及基于规则 (Rule-Based Optimizer，RBO) 和代价(Cost-Based Optimizer，CBO)的智能查询优化器。

 

★   优化器

优化规则的丰富程度是能否产生最优计划的一个重要指标。因为只有可选方案足够多时，才有可能选到最优的执行计划。AnalyticDB提供了丰富的关系代数转换规则，用来确保不会遗漏最优计划。

基础优化规则：

裁剪规则：列裁剪、分区裁剪、子查询裁剪

下推／合并规则：谓词下推、函数下推、聚合下推、Limit下推

去重规则：Project去重、Exchange去重、Sort去重

常量折叠／谓词推导

探测优化规则：

Joins：BroadcastHashJoin、RedistributedHashJoin、NestLoopIndexJoin

Aggregate：HashAggregate、SingleAggregate

JoinReordering

GroupBy下推、Exchange下推、Sort下推

高级优化规则：CTE

 

例如下图中，CTE的优化规则的实现将两部分相同的执行逻辑合为一个。通过类似于最长公共子序列的算法，对整个执行计划进行遍历，并对一些可以忽略的算子进行特殊处理，如Projection，最终达到减少计算的目的。

单纯基于规则的优化器往往过于依赖规则的顺序，同样的规则不同的顺序会导致生成的计划完全不同，结合基于代价的优化器则可以通过尝试各种可能的执行计划，达到全局最优。

 

AnalyticDB的代价优化器基于Cascade模型，执行计划经过Transform模块进行了等价关系代数变换，对可能的等价执行计划，估算出按Cost Model量化的计划代价，并从中最终选择出代价最小的执行计划通过Plan Generation模块输出，存入Plan Cache（计划缓存），以降低下一次相同查询的优化时间。

 

 

在线分析的场景对优化器有很高的要求，AnalyticDB为此开发了三个关键特性：存储感知优化、动态统计信息收集和计划缓存。

存储层感知优化

生成分布式执行计划时，AnalyticDB优化器可以充分利用底层存储的特性，特别是在Join策略选择，Join Reorder和谓词下推方面。

底层数据的哈希分布策略将会影响Join策略的选择。基于规则的优化器，在生成Join的执行计划时，如果对数据物理分布特性的不感知，会强制增加一个数据重分布的算子来保证其执行语义的正确。 数据重分布带来的物理开销非常大，涉及到数据的序列化、反序列化、网络开销等等，因此避免多次数据重分布对于分布式计算是非常重要的。除此之外，优化器也会考虑对数据库索引的使用，进一步减少Join过程中构建哈希的开销。

调整Join顺序时，如果大多数Join是在分区列，优化器将避免生成Bushy Tree，而更偏向使用Left Deep Tree，并尽量使用现有索引进行查找。

优化器更近一步下推了谓词和聚合。聚合函数，比如count（），和查询过滤可以直接基于索引计算。