前言
随着云时代全面到来，企业数据需求不断变化，从传统的 Big Data 逐渐向 Fast Data 演进，主要表现在如下 4 个方面（部分数据参考 Gartner、IDC）：
- 数据规模爆炸性增长，到 2020 年全球数据预计会到 40ZB，而到 2025 年还会继续增长 4 倍以上。
- 企业上云速度明显加快，预计到 2025 年企业 50% 的数据都是云存储，而企业 75% 的数据库都运行在云上。
- 数据的实时化需求强烈，预计 2025 年全球数据处理中会有 30% 是实时数据处理。
- 数据智能化趋势明显，随着 AI 和 5G 技术的发展，非结构化数据快速增长，到 2025 年预计 80% 的数据都是非结构化数据。
在数据爆炸性增长、企业全面上云的大背景下，海量数据的存储、处理的性能及性价比是云原生数仓面向未来最核心的关键技术指标之一，TPC 官方推出的 TPC-DS 基准测试是对一个数据仓库从数据导入、查询性能（单并发、多并发）、查询复杂度（覆盖星型模型/雪花模型、复杂 Window function 支持）、可用性（数据一致、坏盘容错处理等）全方面的严格考核，并需要进行全面严苛的审计，是目前全球衡量一个数据仓库成熟度、竞争力的核心基准测试。
AnalyticDB 作为云时代的云原生数据仓库，参与 TPC-DS 基准测试是我们提升自研产品产品化能力、核心技术突破验证的重要过程，也是我们技术走向全球领先的必经之路，这个过程中的核心技术突破正在帮我们的客户提升性能进一步提升实时化进程、大幅降低成本，一起进入数据库与大数据一体化、业务在线化的新时代。
TPC-DS 榜单
一 AnalyticDB 介绍
AnalyticDB（简称 ADB，原 ADS） 是阿里巴巴自主研发、唯一经过超大规模以及核心业务验证的 PB 级实时数据仓库，自 2012 年第一次在集团发布上线以来，至今已累计迭代发布近百个版本，支撑起集团内的电商、广告、物流、文娱、旅游、风控等众多在线分析业务。AnalyticDB 于 2014 年在阿里云开始正式对外输出，支撑行业既包括传统的大中型企业和政府机构，也包括众多的互联网公司，覆盖外部十几个行业。
AnalyticDB MySQL 3.0 （简称 ADB 3.0）是在过去 8 年沉淀的基础上，基于数据库大数据一体化的理念及趋势以及工程上深度打磨出的云原生数仓升级版本。在本次 TPC-DS 基准测试中，AnalyticDB MySQL 3.0 充分展现了出色的云原生技术优势，对比友商有近 10 倍的巨大优势！
二 TPC-DS 性能基准介绍
TPC (Transaction Processing Performance Council) 是事务性能管理委员会的简称，是最知名的非盈利的数据管理系统评测基准标准化组织，它制定商务应用基准程序（Benchmark）的标准规范、性能和价格度量，并管理测试结果的发布，而 TPC Benchmark 测试结果是衡量一个数据管理系统性能及性价比的最核心指标之一。
TPC-DS 基准测试模拟了一个典型的零售行业数据仓库的评测决策支持系统（Decision Support），是数据库界最具挑战的一个测试基准，是 TPC-H 的升级版，它采用星型、雪花等多维数据模式，测试集包含对大数据集的统计、报表生成、联机查询、数据挖掘等复杂应用，与真实场景非常接近。
TPC-DS 的难点和挑战主要有：
- 数据集规模大，例如事实表 store_sales，单表超过 280 亿行。
- 面向真实零售决策场景，SQL 非常复杂：覆盖 SQL 99 和 2003 的核心部分以及 OLAP 标准；既包含报表类 ad-hoc 低延时查询，又包含海量数据挖掘高吞吐分析查询。
- 测试项多且维度广：既要高性能、高可靠、高可用、高性价比，又要 ETL 和数据更新的 ACID 能力。
TPC-DS 测试流程及数据模型：
三 AnalyticDB MySQL 3.0 技术架构
AnalyticDB MySQL 3.0 采用云原生架构，计算存储分离、冷热数据分离，支持高吞吐实时写入和数据强一致，兼顾高并发查询和大吞吐批处理的混合负载。
第一层是接入层，由 Mulit-Master 可线性扩展的协调节点构成，主要负责协议层接入、SQL 解析和优化、实时写入 Sharding、数据调度和查询调度。
第二层是计算引擎，具备分布式 MPP + DAG 融合执行能力，结合智能优化器，可支持高并发和复杂 SQL 混合负载，同时借助于云原生基础设施，计算节点实现了弹性调度，可根据业务需求做到分钟级甚至秒级扩展，达到了资源的有效利用。
第三层是存储引擎，基于 Raft 协议实现的分布式实时强一致高可用存储引擎，通过数据分片和 Multi-Raft 实现并行，利用分层存储实现冷热分离降低成本，通过行列存储和智能索引达到极致性能。
四 AnalyticDB 存储技术
1 分布式强一致存储
AnalyticDB MySQL 3.0 存储完全自主研发，基于 Raft 协议构建了一套分布式强一致高可靠的轻量级存储架构，可实现高吞吐实时写入，适合极致分析性能场景。AnalyticDB MySQL 3.0 存储相比开源 HBase、Kudu 等在 SQL 分析性能上有较大优势，并且在实时写入强一致可见、支持 ACID 方面也是开源 ElasticSearch、ClickHouse 等所不具备的能力。
AnalyticDB 存储整体架构如下：
AnalyticDB MySQL 3.0 是基于数据库的并行数据模型，存储建模亲和 MPP 计算模型，内部实现为多层并行的架构：
第一级是集群实例级并行，用户实例被划分为多个存储节点组（Worker Group），每个 Worker Group 由 N（通常是 3，也可以是其他基数）个 Worker 构成。Worker 相当于用户数据节点容器，分组的目标是保证系统大规模扩展时不会出现通信膨胀、也方便系统并行升级和运维。
第二级是 DB 并行，用户数据库被切分为 N 个物理分库（ Shard，也叫数据分片），每个 Shard 是独立的 Raft Group 以保证数据强一致，多个 Shard 就形成了 multi-raft 的并行。Shard 是可以是 Hash 或者 Range 分区，通常 Hash 分区可以做数据对齐以避免数据大表 JOIN 的数据 Shuffle；Shard 可以在需要的时候在不同 Worker Group 之间均衡或者迁移，Shard 本身也会支持动态分裂和合并。
第三是表内并行，对于数仓场景的历史数据存储通常有数据分区的概念，例如 TPC-DS 中 store sales 就可以根据时间周期分区，数据分区除方便数据生命周期管理外还可以支持查询分区裁剪和 DFP，有助于大幅缩小数据计算范围。
在 TPC-DS 基准测试中，通过分布式并行存储架构以及感知存储分布的查询优化和执行引擎紧密配合，整体性能优异。
2 高性能批量导入
数据导入速度是云数仓的基础能力，在 TPC-DS 中对导入有着极致的性能要求，我们的第一个优化思路是轻量级 build（把实时数据转换为全量分区数据称之为 build），AnalyticDB MySQL 3.0 实现了轻量化的全内存单副本 local build，相比之前版本的类 MR 作业的全量 build 大幅减少了读写 DFS 和落盘开销，并且可以充分通过本地化向量指令有效利用 CPU 提升性能。
第二个思路是 IO 和网络优化，在导入链路上，我们采用 DirectIO、Binary 化、全流式、异步化、零拷贝等技术大幅提升导入性能。
第三个思路是减少数据量，通过 Raft 2+1 技术（2 份数据 + 1 份日志）在保证数据高可靠的前提下将数据量减少 1/3, 再通过高性能 lz4 压缩算法将数据进一步压缩，整体下来数据的读写 IO 和网络传输开销都得到大幅优化。
最终，在 TPC-DS 18 个节点上可以实现超过 5000 万/秒的导入性能。
3 高吞吐实时更新 DML
AnalyticDB MySQL 3.0 基于 Raft 实现了高吞吐实时数据更新能力，写入链路通过全异步化、零拷贝、高效编码压缩等实现了出色的性能，在 TPC-DS DML 测试中，AnalyticDB 十几个节点可以做到千万级 TPS 实时写入更新，并且能够保证线性一致性（写入后立即可查）。在实际生产中，用户写入性能完全可扩展，可以轻松实现亿级 TPS 的实时写入更新。
在 TPC-DS 中，需要验证数据仓库的数据修改和 ACID 能力，AnalyticDB MySQL 3.0 支持 ETL 事务，具备 ACID 能力（可以完整跑 TPC-C 事务功能测试），在 TPC-DS 的 DML 测试中，存储引擎 MVCC 能力发挥了巨大的作用：存储引擎通过切分为实时数据（Delta）和分区数据（Main）+ 异步的数据转换（Build）实现了类 LSM 写优化架构。AnalyticDB 实现了 Block-level MVCC + 快照隔离，可以保证 ETL 和数据更新过程中数据的隔离性（可见性）、在坏盘出错时可以保证数据更新原子性。
4 行列混存和智能索引
AnalyticDB MySQL 3.0 通过自研的行列混存格式，能够兼顾高筛选率和大吞吐扫描两种场景，相比开源 ORCFile 的纯列存格式在明细点查上更有优势，而相比 Parquet，AnalyticDB MySQL 存储格式具有更出色的随机读性能，同时对比业界行存表 + 列存表两份数据冗余的模式成本更低。在 AnalyticDB MySQL 中，每个 Table 都有一个行列存储格式文件，数据被切分成不同的 RowGroup，在 RowGroup 内由列的 Block 构成，Block 内对定长、非定长（Toast）数据的进行有效的编码和压缩，并且支持高效的随机读和顺序读。
在 TPC-DS 测试中，通过配置合理的存储 Block 大小（4KB 对齐）、数据块预取、源头算子向量读等大幅优化了存储扫描性能；同时，存储上精确的统计信息(min/max/sum/cnt 等)一方面可以加速数据过滤（Smart Scan），另一方面还能够为查询优化器提供丰富的 Statistics 以帮助制定出最优的执行计划。
AnalyticDB MySQL 的特色之一是自研智能索引框架，支持五种索引类型：字符串类的 Invert 索引、bitmap 索引、数值类的 KDTree 索引、JSON 索引和向量索引；不同类型的索引可以实现列级索引多种条件（交、并、差）任意组合；相比较传统数据的优势是，无需建组合索引（不会引起空间膨胀）、且支持 OR/NOT 等更多条件的索引下推。为了降低用户使用门槛，AnalyticDB 在建表时可以开启一键自动全列索引，查询时通过 Index CBO 智能动态筛选索引下推，确定下推的索引链会通过谓词计算层进行流式渐进多路归并输出。
五 AnalyticDB 查询技术
AnalyticDB MySQL 3.0 的查询引擎，由自研的查询优化器和查询执行器两个模块组成。它是 AnalyticDB MySQL 提供高并发、高吞吐数仓分析能力的重要一环。感知数据特征，深度结合存储引擎的架构，同时支持 Reporting、Ad-hoc、ETL 数仓分析场景，是其相较于单一计算引擎的核心优势。
作为一款分布式云原生实时数仓产品，AnalyticDB MySQL 的优化器不仅仅要面临传统优化器所涉及的挑战，例如复杂 Join Reorder 的 NP-hard 问题，代价估算的不确定性问题，还面临在分布式环境下分布式并行计划的新问题。CBO 做为 AnalyticDB MySQL 3.0 版本最新成果，在 TPC-DS 战役中首次开启使用，对于整体计划的调优，起到了非常重要的作用。
ADB 查询执行引擎，以统一的内存池化和查询的混合负载管理能力为基础，使用动态代码生成技术，创新性的混合执行模型，利用 SIMD 指令集的向量化算法，以及自适应的面向行、列混合存储的查询执行等技术，是 AnalyticDB MySQL 持续的在 TPC-DS 查询性能上领先的关键因素。
1 CBO 查询优化框架
基于代价的优化器本质上是一个复杂的搜索问题，想要解决好这个问题，需要从四个方面入手：
搜索框架
从数据库的发展历程来看，基于 Cascades 的搜索框架已经成为了业界标准，包括商业数据库 SQL Server 以及开源数据库 GP/ORCA 都采用 Cascades 实现。AnalyticDB MySQL 优化器 CBO 也是基于 Cascades 论文实现的。搜索框架面临的一个核心问题是搜索空间会急速膨胀，但是搜索时间需要维持毫秒级响应，因此需要有高效的数据结构存储搜索空间、高效的优化规则生成搜索空间、高效的搜索算法遍历搜索空间，高效的剪枝策略裁剪搜索空间。
分布式并行计划
相对于传统的单机版数据库来说，分布式 MPP 数据库给优化器带来了新的挑战。在分布式 MPP 数据库中，数据的分布属性变得十分的重要，它会直接影响到数据的正确性。为了满足不同算子对数据分布的要求，数据重分布不可避免，然而数据的重分布即数据 shuffle 的代价非常昂贵，因此，在保证数据正确性的前提下，尽可能的减少数据 shuffle。作为分布式 MPP 数据库优化器来说，需要把数据的 Partitioning 属性，以及 Sorting、Grouping 属性，也纳入到搜索空间来综合考虑，基于代价选择最优的分布式并行执行计划。
代价估算
代价估算是优化器能否寻找到最优计划的关键因素。代价估算涉及到统计信息的推导和代价模型。统计信息的推导依赖于：原始表的统计信息、中间算子的推导算法、对数据的各种假设（均匀性假设、独立性假设、包括性假设、包含性假设）以及在一些极端情况下的猜测。因此统计信息的推导存在大量的不确定性，也正是因为这些不确定性，极大的加剧了优化器寻找最优解的难度。本质上来说，只有打破对数据属性的假设，才有可能使得统计信息的估算做到知其然知其所以然，然而打破这些假设，也要付出更多的代价。
统计信息收集
收集必要的统计信息是 CBO 工作的前提，统计信息需要做到：基本信息能够自动化收集，自动化更新，高级统计信息可以手动收集，为 CBO 提供可靠的、多纬度的统计信息。在实际的情况下，可能存在统计信息丢失或者没有及时收集，在这种情况下，为了避免生成灾难性的计划，可以在运行时动态采样来获取必要的统计信息。
2 混合查询执行框架
传统的火山执行模型不能满足分析场景高吞吐的性能需求已经成为业界的共识。随着各个系统的不断发展，目前业界计算引擎有 2 种演化后的执行框架实现：
- Just-in-time (JIT) compilation
- Vectorization
JIT编译方式以数据为中心，一条数据经过上一个算子处理后，还在 CPU 缓存中便直接进行下一个算子的计算，对 CPU 缓存友好，适合计算密集型任务。Vectorization 中每个算子处理一批数据后，将一批结果再交给下一个算子计算。适合内存密集型任务以及向量计算，用中间结果物化的开销换取算子的计算高内聚。
JIT 编译方式和 Vectorization 各有所长，如上图所示，红色表示 JIT 编译方式，绿色表示 Vectorization 方式。目前 AnalyticDB MySQL 是唯一的同时支持这两种查询模式的自研分析引擎。混合执行框架，在 Vectorization 执行模式的基础上，自适应的把多个计算密集特征的算子融合成一个驱动执行。实现了一个查询执行引擎同时具备 Compilation 和 Vectorization 的优点。
3 统一内存管理
在内存方面，高效的内存管理是计算优化的基石。面向类型的内存模型，特指针对不同的数据类型使用不同的基础类型存储。这导致不同的类型无法存储在连续的内存地址中，仅能通过按列的方式进行存储，减少多个内存对象带来的额外代价。另外一方面，不同内存类型间的内存无法复用，这会造成额外的内存管理代价。
ADB 的查询执行引擎，通过统一内存管理来解决上面的几个问题：
- 内存 binary 化：统一内存类型，不同类型均使用相同的数据类型（byte）来存储，同时这也是查询执行面向行存，缓存友好算法优化的基石。
- 规范化的内存管理规格：统一内存规格，降低内存碎片带来的额外代价，并且降低复用内存的难度。
- 分层的内存管理：统一内存管理，根据计算特点对应内存的生命周期，针对内存使用特点，实现 MemoryCache， MemoryPool，并且支持内存泄漏检测，实现面向常驻服务的主动内存管理。
4 DFP 和 CTE 技术
在数据仓库中，事实表和维度表 Join 是典型场景，他们之间的数据量的差异可以达到千万倍级别，这个时候，Join 的计算成本更多的在于数据的扫描成本，因此我们会采用 DynamicFilterPushDown 的方式，来极大的减少左表的数据量。另外数据仓库中会出现大量的 WITH 语句以及隐式的共享语句，这些都可以通过 Common Table Expression 的共享来避免重复计算。
DFP（DynamicFilterPushDown）对于筛选率高的 Join （命中率低）、Probe 端的数据从存储中被读上来之后，大部分数据会被丢弃掉。因此如果评估出来 build 的数据维持在一个比较小范围的阈值，那么我们就可以把 build 端结果值，作为左表的过滤条件，也就是 Dynamic Filter，直接下推存储，减少扫描量。对于优化器来说，最主要的工作就是要合理评估 build 端命中 Join 条件的 NDV 值。
不同的 Join Order 直接影响可做 Dynamic Filter 的范围和粒度，能够进行该优化的 Join 其 Cost 与真正的 Hash Join 有巨大的差异反过来也影响了 Join Order。基于 ADB 完善且扩展性较好的 CBO 框架，我们做到了从全局考虑，基于 Cost 选择最优的 Dynamic Filter 方案。
在执行层面，我们通过如下三个关键点实行有高效的 DFP：
- 高效动态谓词构建，通过进程内 in-place 构建动态谓词，降低动态文词构建代价。
- 多层过滤执行优化，结合 bloomfilter，分区裁剪，感知存储索引等方式，加速过滤效果。
- 异构数据源的下推，统一数据源接口层抽象实现，扩展异构数据源的支持。
CTE（Common table expression），TPC-DS 30%+ 的 sql 中包含 with as 用法， 通过 with as 子查询，在主查询中多次引用，每一次引用带来了额外的重复计算，导致资源浪费。基础的 CTE 优化，通过复用 with 子句的结果给多个引用方，来减少重复计算的代价。但是对于部分场景，与主查询的关系推导可以进一步减少 with 子查询中的计算量，这时直接 share 完整 with 子句会导致额外的性能回退。那么通过 inline 后的最优计划，进行 common sub tree 的识别，进一步减少重复计算量，达到无 bad case 的效果。执行器实现中，我们引入了死锁检测，通过分析 common sub tree 的多个 consumer 之间的依赖关系，解决死锁问题。
六 总结和展望
AnalyticDB 经过数据库领域最顶级会议 VLDB 论文（AnalyticDB: Realtime OLAP Database System at Alibaba Cloud）的理论验证（中国极其少有的大规模商用系统介绍论文，类似有 Google F1 [VLDB'2013]、AWS Aurora [SIGMOD'2017] 等）、TPC-DS 全球领先的工程验证（TPC-DS 全球性价比、性能双双领先）、覆盖核心部委以及大型泛互联网客户的客户验证、阿里集团多年的超大规模验证形成了多方面优势，基于云计算的高效资源效率、数据库与大数据一体化发展趋势，正式完成重大品牌升级，由“分析型数据库”升级为“云原生数据仓库”。
未来已来，大数据与数据库一体化 + 云原生将会重新定义云计算时代的数据仓库，TPC-DS 破世界纪录只是起点，AnalyticDB 将会持续投入致力于成为企业数字化转型升级、数据价值在线化的基础设施！
AnalyticDB 2019 大盘点：点击这里
