独家揭秘 | 阿里云分析型数据库AnalyticDB新一代CBO优化器技术

本文涉及的产品
云原生数据库 PolarDB PostgreSQL 版,企业版 4核16GB
推荐场景:
HTAP混合负载
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云原生内存数据库 Tair,内存型 2GB
简介: 作者:马宏,阿里云数据库技术专家

01、概述

对于数据库来说,其中俩个核心的模块是:优化器和执行引擎。优化器负责给执行引擎提供输入,它接收来自 SQL Parser 解析好的 AST 树,然后需要从所有可能的计划中选择代价最优的计划提供给执行引擎。基于代价的优化器本质上是一个复杂的搜索问题,想要解决好这个问题,需要从四个方向入手:

1)搜索框架:既然是搜索问题,那么就需要一个搜索框架来承载这个问题。从数据库的发展历程来看,基于 Cascades 的搜索框架已经成为了业界标准,包括商业数据库 SQL Server 以及开源数据库 GP/ORCA 都采用 Cascades 实现。AnalyticDB CBO 也是基于 Cascades 论文实现的。

2)分布式并行计划:相对于传统的单机版数据库,AnalyticDB 是一个分布式 MPP 数据库,优化器生成的计划是一个分布式并行计划。因此需要把分布式并行计划的生成和搜索框架结合起来,基于代价选择最佳的分布式并行计划。

3)代价估算:代价估算是优化器能否寻找到最优计划的关键因素,代价估算做不好,优化器不可能做好。代价估算涉及到统计信息的推导和代价模型。统计信息的推导依赖于:原始表的统计信息、中间算子的推导算法、对数据的各种假设(均匀性假设、独立性假设、包括性假设、包含性假设)以及在一些极端情况下的猜测。因此统计信息的推导存在大量的不确定性,也正是因为这些不确定性,极大的加剧了优化器寻找最优解的难度。

4)统计信息收集:收集必要的统计信息是 CBO 工作的前提,CBO 和统计信息之间的关系犹如一把枪和弹药之间的关系,枪再好如果没有充足的弹药的话,那么无异于巧妇难为无米之炊。统计信息需要做到:基本信息能够自动化收集,自动化更新,高级统计信息可以手动收集,为 CBO 提供可靠的、多维度的统计信息。

02、架构

1.jpg

搜索框架

搜索框架在整个 CBO 中处于非常中心的一个位置,它会调用 Property Enforcement 框架,生成分布式执行计划,然后调用代价估算模块,给每一种候选分布式执行计划评估代价,最终基于代价选择最优的分布式执行计划。搜索框架包括以下几个部分:

Memo 表示搜索空间:对于一个查询计划来说,首先需要把它初始化,形成初始化的搜索空间。随着搜索的进行,搜索空间会不断扩充。由于搜索空间会非常庞大,因此 Memo 需要做到高效存储。

Search 表示搜索算法:搜索算法由三部分组成,第一部分用于递归遍历搜索空间,第二部分用于调用展开规则产生新的等价候选计划,扩充搜索空间,第三分部用于用于推导分布式计划的属性要求并计算代价值,进而寻求最优的分布式执行计划。

Scheduler 表示调度搜索算法的调度器:在当前的 AnalyticDB CBO 版本中,基于单线程和栈实现:把搜索任务压入到一个栈中,然后循环取栈中的任务去执行,直到任务结束。

考虑到其他开源优化器产品,例如 ORCA 提到了多线程并行搜索的理念,我们预留了多线程调度器的接口,相对于优化器众多棘手的问题来说,它的优先级并不是那么高,实现并行搜索的好处是非常明显的,它可以显著降低任务调度的执行时间,充分发挥多核并行的能力,从整个查询的角度来看,可以缩短查询优化的耗时,从而降低整体查询的耗时。但是并行搜索带来的线程同步问题,以及线程间依赖处理问题,挑战还是很大的。

Rule 表示展开规则:展开规则用于生成等价候选计划,等价候选计划会被放入到 Memo 中,形成完整的搜索空间。展开规则决定了优化器可以展开多少种候选计划,因此展开规则的种类,以及每种展开规则的算法效率对 CBO 来说也是至关重要的。展开规则种类越多,搜索空间就越完善,也就更有可能寻求到最优解,同时每种展开规则的算法越高效,生成完整的搜索空间就越高效,查询优化就越快。

分布式并行计划

相对于传统的单机版数据库来说,分布式 MPP 数据库给优化器带来了新的挑战。在分布式 MPP 数据库中,数据的分布属性变得十分的重要,它会直接影响到数据的正确性。为了满足不同算子对数据分布的要求,我们往往需要做数据重分布。

然而数据的重分布,也就是数据 shuffle 的代价非常昂贵,因此,在保证数据正确性的前提下,尽可能的减少数据 shuffle,可以大幅度提升分布式计划的执行性能。作为分布式 MPP 数据库优化器来说,需要把数据的 Partitioning 属性,以及 Sorting、Grouping 属性,也纳入到搜索空间来综合考虑,基于代价选择最优的分布式并行执行计划。

因此我们设计实现了一套完整的 Property Enforcement 框架,用于描述在分布式场景下,分布式计划对数据分布的要求。同时我们把 Property Enforcement 的过程和搜索框架无缝的结合在一起,实现了面向分布式 MPP 数据库的 CBO。

代价估算

代价估算是整个 CBO 质量好坏的关键因素,代价估算做的好,CBO 才有可能选择出最优的计划,它包括三个部分。

Statistics 用于描述原始表的统计信息。包括表级别的统计信息 Row Count,单个字段的统计信息:每个字段的 NDV 值(distinct 值),Max 值,Min 值,NULL 值,Histogram 值(分布信息,用于区间查询), Count-Min Sketch 值(用于等值查询),DataSize 值。这些统计信息我们把它归纳为基础统计信息,需要做到自动收集,自动更新。

同时考虑到多个字段之间的关联度、Functional deplendency、数据的倾斜等这些因素对统计信息估算的影响,还会提供命令行工具,手动收集这些信息,对于这些需要手动收集的信息,我们把它归纳为高级统计信息,只有在必要的时候,才需要显示的手动收集。另外,对于一些复杂的 predicate,例如 like,那么即使收集了 Histogram 也无法支持这种场景,因此我们也会在运行时基于动态采样来获取对应的统计信息。

Stats Derivation 用于推导经过各个算子之后的统计信息。统计信息的推导依赖于原始表的统计信息,数学公式,对数据属性的假设(例如,数据的分布是均匀的,多列之间的选择率是没有相关性的),以及极端情况下,启发式的假设(例如对于一个用户自定义的 UDF,它的选择率只能给一个默认值)。

统计信息的推导的好坏对优化器来说至关重要,这也一直是学术界的研究热点。本质上来说,只有打破对数据属性的假设,才有可能使得统计信息的估算做到知其然知其所以然,然而打破这些假设,依赖于对原始数据的分析,生成更多维度的统计信息,必然也要付出更多的代价。

Cost Model 表示代价模型。代价模型的工作必须要建立在合理的统计信息推导的基础之上,否则它的意义不会很大。代价模型需要对实际的计算模型进行评估,把统计信息转换为可以量化的代价值,从而为优化器提供决策依据。

统计信息收集

Analyze 用于收集统计信息。对于商业数据库来说,为了提升用户体验,做到开箱即用,都致力于 Auto analyze,即统计信息收集的自动化,以及自动更新。但是收集本身也是有代价的,因此我们把统计信息分为俩类:基础统计信息和高级统计信息。

基础统计信息就是前面提到的:表级别的统计信息 row count,单个字段的统计信息:每个字段的 NDV 值(distinct 值),Max 值,Min 值,NULL 值,Histogram 值(分布信息,用于区间查询),Count-Min Sketch 值(用于等值查询),DataSize 值。基础统计信息必须要做到自动化收集、自动化更新,否则很可能由于这些统计信息的缺失,导致优化器产生灾难性的计划。

同时为了提升优化器在复杂情况下的决策质量,还提供了一些高级的命令用于收集更加复杂的统计信息,例如可以收集 column group 的统计信息,来获取多个字段之间的关联度信息。高级统计信息需要手工触发收集,只有在必要的时候才会收集。

基于 Analyze 命令收集统计信息,无论是自动化收集,还是手工收集,本质上来说所,它都是一个独立的进程:Analyze 会调用 Data Profiling 任务,对原始数据进行分析,生成统计信息,并存储在 Metadata 库中。

考虑到实际情况下,可能存在一些非常复杂的查询条件,不管是基础的统计信息还是高级统计信息,都无法很好的对它做合理的估算,这个时候,dynamic sampling 动态采样就可以发挥它的价值,动态采样会实时下发采样,获取必要的统计信息,提升优化器的决策质量。

其次,动态采样也可以作为统计信息收集的一种兜底策略,当基础统计信息由于某些原因导致未收集的情况下,动态采样的存在可以避免优化器由于缺失统计信息而产生灾难性的计划。但是动态采样是在查询优化阶段同步阻塞执行的,因此它必然会增加查询优化的整体耗时,同时也会增加整个数据库系统的负载,因此我们严格限制动态采样的使用场景。

03、设计与实现

接下来我们会通过一个例子来展开搜索框架、Property Enforcement 框架、以及代价估算的设计与实现。

查询语句

这一个简化版的 TPCH q3,非常典型的三表 Join。其中 customer 表按照 c_custkey 进行分区,orders 表按照o_orderkey 进行分区,lineitem 表按照 l_orderkey 进行分区。

SELECT
    l_orderkey,
    o_orderdate,
    o_shippriority
FROM
    customer,
    orders,
    lineitem
WHERE
    c_custkey = o_custkey
    AND l_orderkey = o_orderkey

查询优化

在进入到 CBO 之前,原始的执行计划如下图所示,customer 表和 orders 表先 Join,Join 的结果再和 lineitem 表 Join,然后输出结果。

2.jpg

进入到 CBO 后,首先需要把查询计划转换为 Group 和 GroupExpression,并初始化 Memo 搜索空间。可以看到共有 6 个 Group,每个 Group 都有一个 GroupExpression。Group 和 GroupExpression 都是搜索空间里面的重要概念,关于它的详细介绍可以参考:AnalyticDB Cost based Optimizer 搜索框架,这里不展开。

简单来说:对于逻辑等价的,可以产生相同结果的 Logical Expression 和 Physical Expression 的集合称为 Group,GroupExpression 则包括 Logical GroupExpression 和 Physical GroupExpression,每一种 GroupExpression 表示一种等价候选计划。
3.jpg

在这里,我们为了简化描述,只考虑 Join 的 Order,以及分布式 Join 情况下,Repartition Join 和 Replicate Join 这两种属性要求,对于 Join 的算法默认只考虑 Hash-join 物理实现。

其他算子:TableScan 和 Output 也默认只有一种物理实现。调度器调度搜索任务,执行搜索流程,扩展搜索空间。可以看到随着搜索算法的不断迭代,Memo 里面的 Group 和 GroupExpression 会新增:白色表示 Logical GroupExpression,灰色表示 Physical GroupExpression。

可以看到,在应用了 Join 的结合律之后,新产生了 Group7 和 Group8 这俩个 Group;同时应用了 Join 的交换律之后,Group5 和 Group3 里面新增了很多等价的 Logical GroupExpression;同样 Group7 和 Group8 里面也有等价的 Logical GroupExpression。

4.jpg

最终考虑俩种分布式 Join 实现:Repartition Join 和 Replicate Join,这样就生成了完整的搜索空间。

5.jpg

当整个搜索空间被完整的扩充出来之后,接下来需要调用 Property Enforcement 框架,对每一种物理执行计划,去 Enforce 必要的属性,从而满足分布式执行计划的要求,然后再调用代价估算模块,去计算每一种分布式计划的代价,并把代价最小的计划标记为最优解,也就是 Winner。当每一个 Group 的 Winner 都被计算出来之后,将每个 Winner 串接起来,就是最优的分布式执行计划。

关于 Property Enforcement 和代价估算的详情,可以参考下面这三篇文章,这里不展开。

AnalyticDB Cost based Optimizer 分布式并行计划
AnalyticDB Cost based Optimizer 代价估算
AnalyticDB Cost based Optimizer 统计信息收集

下图中黑色意味着 Winner,表示的是在满足某种属性要求的情况下,代价最低最低的物理执行计划。

6.jpg
7.jpg

我们遍历每个 Group 的 Winner,将 Winner 串接起来,就形成了最优的分布式执行计划。

每一个 Winner 经过 Property Enforcement 之后,都会在必要的时候插入必要的 Exchange 节点,来满足分布式计划的属性要求,所以生成的分布式执行计划如下图所示。可以看到:首先 customer 表做了一个全表广播到所有节点,进而满足和 orders 表 Join 的要求,Join 之后的结果按照 order 表分布,orders 表和 lineitem 表数据分布本身就满足 Join 的要求,因此不需要插入 Exchange 节点,最终 Join 的结果要输出到 Output 节点,因此插入 Gather 节点,汇总到单节点。

7.jpg

04、参考

An Overview of Query Optimization in Relational Systems

The Cascades Framework for Query Optimization
Efficiency in the columbia database query optimizer

Orca: A Modular Query Optimizer Architecture for Big Data

Incorporating Partitioning and Parallel Plans into the SCOPE Optimizer

Profiling Relational Data – A Survey

相关实践学习
数据库实验室挑战任务-初级任务
本场景介绍如何开通属于你的免费云数据库,在RDS-MySQL中完成对学生成绩的详情查询,执行指定类型SQL。
阿里云云原生数据仓库AnalyticDB MySQL版 使用教程
云原生数据仓库AnalyticDB MySQL版是一种支持高并发低延时查询的新一代云原生数据仓库,高度兼容MySQL协议以及SQL:92、SQL:99、SQL:2003标准,可以对海量数据进行即时的多维分析透视和业务探索,快速构建企业云上数据仓库。 了解产品 https://www.aliyun.com/product/ApsaraDB/ads
目录
相关文章
|
4天前
|
人工智能 多模数据库 Cloud Native
揽获多项殊荣,阿里云瑶池数据库亮相2024可信数据库发展大会
在2024可信数据库发展大会上,阿里云被选为中国信通院数据库金融工作组共建单位。同时,阿里云Lindorm成为首批通过中国信通院多模数据库产品测试的产品,展示出在多模数据处理能力上的领先性。
|
14天前
|
缓存 运维 关系型数据库
数据库容灾 | MySQL MGR与阿里云PolarDB-X Paxos的深度对比
经过深入的技术剖析与性能对比,PolarDB-X DN凭借其自研的X-Paxos协议和一系列优化设计,在性能、正确性、可用性及资源开销等方面展现出对MySQL MGR的多项优势,但MGR在MySQL生态体系内也占据重要地位,但需要考虑备库宕机抖动、跨机房容灾性能波动、稳定性等各种情况,因此如果想用好MGR,必须配备专业的技术和运维团队的支持。 在面对大规模、高并发、高可用性需求时,PolarDB-X存储引擎以其独特的技术优势和优异的性能表现,相比于MGR在开箱即用的场景下,PolarDB-X基于DN的集中式(标准版)在功能和性能都做到了很好的平衡,成为了极具竞争力的数据库解决方案。
|
14天前
|
人工智能 监控 安全
阿里云携手北京奇奇科技举办《AI智领者技术沙龙》
6月5日,一场主题为“通义大模型的创意与应用探索”的AI智领者技术沙龙在京召开。这场会议汇聚了行业内外众多专家及企业代表,主办方阿里云与北京奇奇科技和与会者共同探讨AI大模型如何从理论走向实践,从实验室迈向广阔的应用场景。
|
19天前
|
存储 关系型数据库 分布式数据库
PolarDB,阿里云的云原生分布式数据库,以其存储计算分离架构为核心,解决传统数据库的扩展性问题
【7月更文挑战第3天】PolarDB,阿里云的云原生分布式数据库,以其存储计算分离架构为核心,解决传统数据库的扩展性问题。此架构让存储层专注数据可靠性,计算层专注处理SQL,提升性能并降低运维复杂度。通过RDMA加速通信,多副本确保高可用性。资源可独立扩展,便于成本控制。动态添加计算节点以应对流量高峰,展示了其灵活性。PolarDB的开源促进了数据库技术的持续创新和发展。
234 2
|
19天前
|
弹性计算 运维 Kubernetes
阿里云ECS与混合云策略的结合,不仅为企业搭建了一个既灵活又稳定的IT基础架构,还为业务的快速发展与创新提供了坚实的技术支撑。
【7月更文挑战第3天】阿里云ECS在混合云中扮演关键角色,提供弹性计算资源和多样计费模式,确保业务连续性与灵活性。通过VPC互通、应用迁移、数据同步服务,如VPC对等连接、DTS,实现云上云下资源的高效整合。结合安全解决方案,保证在混合环境下的合规与安全。阿里云ECS助力企业数字化转型,应对市场变化。
53 1
|
4天前
|
存储 安全 Cloud Native
阿里云数据库多款产品支持米哈游新游《绝区零》全球开服!
这一次,阿里云继续与大家共同守护「新艾利都」!
|
5天前
|
机器学习/深度学习 运维 算法
|
5天前
|
NoSQL Cloud Native Redis
|
19天前
|
存储 大数据 关系型数据库
从 ClickHouse 到阿里云数据库 SelectDB 内核 Apache Doris:快成物流的数智化货运应用实践
目前已经部署在 2 套生产集群,存储数据总量达百亿规模,覆盖实时数仓、BI 多维分析、用户画像、货运轨迹信息系统等业务场景。