SQL优化器原理-Shuffle优化

本文涉及的产品
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
简介: 分布式系统中,Shuffle是重操作之一,直接影响到了SQL运行时的效率。Join、Aggregate等操作符都需要借助Shuffle操作符,确保相同数据分发到同一机器或Instance中,才可以进行Join、Aggregate操作。

这是MaxCompute有关SQL优化器原理的系列文章之一。我们会陆续推出SQL优化器有关优化规则和框架的其他文章。添加钉钉群“关系代数优化技术”(群号11719083)可以获取最新文章发布动态。
本文主要介绍MaxCompute Optimizer对Shuffle方面的相关优化。

1 简介

分布式系统中,Shuffle是重操作之一,直接影响到了SQL运行时的效率。Join、Aggregate等操作符都需要借助Shuffle操作符,确保相同数据分发到同一机器或Instance中,才可以进行Join、Aggregate操作。对于这些需要经常使用到Shuffle场景,如何减少Shuffle,删除一些不必要的Shuffle是提升性能的一个关键。
例如

select count(*), c1 from t group by c1;
AI 代码解读

假设t表如果是Hash Clustering Table[2],则GroupBy的计算全部可以本地化处理,不需要再次Shuffle,因为相同c1值已在同一台机器了。

Optimizer Plan
OdpsPhysicalProject(cnt=[$1], c1=[$0]): rowcount = 1.5, cumulative cost = {6.30 rows, 3.00 cpu, 34.40 io, 0.00 memory, 0.00 network}, id = 281
  OdpsPhysicalSortedAggregate(group=[{0}], __agg_0=[COUNT()]): rowcount = 1.5, cumulative cost = {4.80 rows, 3.00 cpu, 26.40 io, 0.00 memory, 0.00 network}, id = 280
    OdpsPhysicalTableScan(table=[[wlz_p_02.t_test, c1(1) {0}]]): rowcount = 3.0, cumulative cost = {3.30 rows, 0.00 cpu, 26.40 io, 0.00 memory, 0.00 network}, id = 206
AI 代码解读

只需要一个Map Task就可以完成整个Query执行。后续会详细介绍如何优化。

2 Shuffle优化原理

MaxCompute Optimizer是基于开源项目Calcite基础上搭建的一套Optimizer框架。Calcite提供了Volcano模型的Planner,MaxCompute Optimizer引入了Volcano模型中Enforcer机制[1]来优化Shuffle。

简单介绍下Enforcer概念,Enforcer是指操作符(算法,如Join的实现SortedMergeJoin、Aggregate的2Pass实现等)要求输入数据必须具有一些物理数据属性(Trait),如order、distribution等。

如SortedMergeJoin要求输入数据必须基于Join keys进行分布且有序,这些为了确保满足SortedMergeJoin算法的要求。如果数据不是按照Join Keys分布,则相同Key值的数据不在同一个Instance里,则无法达到Join的目的;如果数据不是基于Key值有序,则无法满足Sorted Merge的要求。简单讲就是一个具体算法决定了输入数据的要求。在分布式环境中,数据要求是通过Shuffle实现。而Shuffle数据特性,我们称之为Trait。

2.1 Enforce Rule

如何确保对于任何算法满足其数据特性Trait的要求?

MaxCompute Optimizer实现了一种叫Enforcer Rule,来保证只要任何操作符对其输入(Input)要求一个Trait,Enforcer Rule就会保证Input的操作符一定会提供这种特性的数据。
图1 Enforcer Rule
h1.png
图1展现了Enforcer Rule的工作机制。

1)任何Operator(算法)会对Input产生一个Required Trait。如SortedMergeJoin,则要求每一路Input必须是基于Key的分布且有序,类似Trait(Hash(c1) sort(c1 asc))。这一步由Build Rule实现,即对于任何Operator当采用某种算法时,必须将Required Trait的要求下推给Input。如Join当生成SortedMergeJoin时,则SortedMergeJoin的Input必须带有Required Trait。

2)Enforcer Rule捕获Required Trait + Input的Pattern。即图1中Required + Input Operator模式。

3)Shuffle生成。

Required+Input方式处理Shuffle提供了三种可能性:

A)情况1:Input Operator不能确保数据具有Trait特性,则直接在Input输出后生成基于Trait的Shuffle。这样Parent给到的要求得到了满足。

B)情况2:Input Operator操作符已经具有了Required Trait的特性,则Shuffle就不需要添加,即达到了减少Shuffle的目的。Parent要求的Trait也得到了满足。

C)情况3:Input Operator可以保证数据的特性可以传递,则可以将Required Trait继续下推到自己的Input中。则Required Trait继续由Input来满足要求,而当前Input本身可以确保数据特性不会发生改变。这种情况下,Required Trait也得到了满足。

任何一个Operator都是采用上述三种策略进行处理,从而使得Required Trait可以从Root Operator一直下推。

举例:Required Trait + Filter

当一个Required Trait与Filter这样一个Pattern被捕获时,如何保证Required Trait得到满足呢?
如果将Filter理解为一个当输入数据传入给Filter Operator时,Filter Operator仅仅是将每一行的数据进行判断是否满足condition条件,如果不满足condition条件的行数,则不输出。所以发现Filter具有一个特性,即不会改变数据的输入特性。所以当Required Trait要求Filter具有这种特性时,可以有两种处理方式:

1)直接生成Shuffle。

2)将Required Trait继续要求Filter的Input保持这种特性。

思考:是否可以直接将Required Trait下推到Filter Input得到满足?

答:不可以。这里有两种选择,即Shuffle是在Filter之前还是之后生成,这些由Optimizer另外一个特性来决定,即CBO(Cost-based Optimizer),也就是由Cost来决定选择是1)还是2),因为继续下推给Input,也有几种情况,要么生成Shuffle,要么继续下推等,这时Shuffle生成的位置则由CBO控制。

2.2 Operator算法

当根据Optimizer生成的Plan真正运行Operator时,必须严格要求如何保证数据特性来实现。如Filter,理论上实现时,可以不保证数据和其输入数据的特性一致,如果是这样,则这些优化都无法实现。因为Operator实现的算法不满足要求。所以Optimizer与Runtime算法必须要求一致。
如SortedAggregate必须保证基于Group By key分布有序等。

3 应用场景

3.1简单case

假设T1是clustering Table[2]

select count(*), c1 from t group by c1;
AI 代码解读

图2 详细实现步骤
h2.png
图2展示了Optimizer如何减少Shuffle的详细步骤。

1)Pull Trait。根据Input来获取可能会产生的Trait。

2)convert(input, Trait[hash])。Aggregate build成SortedAggregate,则要求Project基于Key hash且有序,即Trait[hash(c1) sort(c1 asc)]。

3)Enforcer处理Required Trait[hash(c1) sort(c1 asc)] 与Project Pattern,将Trait下推给TableScan。

4)Required Trait与TableScan发现Trait一致,则Shuffle不需要添加。从而达到了减少Shuffle的优化目的。

上述逻辑介绍了Optimizer如何一步一步达到减少Shuffle的目的。主要关键点是Operator算法要求Input 满足Trait以及Trait与Input Pattern如何满足Parent Operator的要求。

3.2 TPC-H

基于TPC-H,给出Q4的Shuffle优化例子。Q4特征: Join的输入分别是Table和Group。且Join Key是Table的Clustering key和Group by key。

Q4:
create table q4_result_xx as
select
o_orderpriority,
count(*) as order_count
from
tpch_orders o
join
    (select
            distinct l_orderkey
        from
        (
    select
    *
    from
    tpch_lineitem
    where
    l_commitdate < l_receiptdate
        ) tab1
    ) tab2
    on tab2.l_orderkey = o.o_orderkey
where
o.o_orderdate >= '1993-07-01' and o.o_orderdate < '1993-10-01'
group by
o_orderpriority;
AI 代码解读

h3.png
图3 MaxCompute Optimizer Plan

图3中显示SortedMergeJoin的两路输入都不存在Shuffle,同时Aggregate这路也没有Shuffle,相当于减少了3次Shuffle(Aggregate一次+Join两次)。
h4.png
图4 优化Shuffle DAG
h5.png
图5 Shuffle不优化DAG

优化Shuffle VS不优化之间差别在于TableScan由于已经基于Key分布,所以Aggregate和Join的Required Trait都可以下推到TableScan,而TableScan都是基于这些key的Clustering Table,Required Trait得到满足,从而Shuffle都不需要。优化Shuffle后的Plan,M1中执行了Aggregate以及Join整个操作,而不需要类似不优化方式,根据Shuffle将Aggregate和Join切分成不同Task进行处理。从性能上讲,Shuffle优化方式耗时54s,而不优化方式耗时121s,性能提升一倍。

4 总结

本文主要从Optimizer实现角度上详细讲解优化Shuffle的实现原理以及一些应用场景。Shuffle优化对性能提升有较大帮助,目前主要应用在Clustering Table上,详细性能测试对比可以见ATA Hash Clustering文章[2]。

索引
[1] Goetz Graefe. The Volcano Optimizer Generator: Extensibility and Efficient Search

[2] ODPS Hash Clustering支持 (内部公测功能)

有任何Optimizer相关问题和反馈,请加入“关系代数优化技术”群获取相关支持。
h6_1

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
龙重
+关注
目录
打赏
0
0
0
0
78935
分享
相关文章
SQL注入之万能密码:原理、实践与防御全解析
本文深入解析了“万能密码”攻击的运行机制及其危险性,通过实例展示了SQL注入的基本原理与变种形式。文章还提供了企业级防御方案,包括参数化查询、输入验证、权限控制及WAF规则配置等深度防御策略。同时,探讨了二阶注入和布尔盲注等新型攻击方式,并给出开发者自查清单。最后强调安全防护需持续改进,无绝对安全,建议使用成熟ORM框架并定期审计。技术内容仅供学习参考,严禁非法用途。
104 0
MySQL进阶突击系列(07) 她气鼓鼓递来一条SQL | 怎么看执行计划、SQL怎么优化?
在日常研发工作当中,系统性能优化,从大的方面来看主要涉及基础平台优化、业务系统性能优化、数据库优化。面对数据库优化,除了DBA在集群性能、服务器调优需要投入精力,我们研发需要负责业务SQL执行优化。当业务数据量达到一定规模后,SQL执行效率可能就会出现瓶颈,影响系统业务响应。掌握如何判断SQL执行慢、以及如何分析SQL执行计划、优化SQL的技能,在工作中解决SQL性能问题显得非常关键。
MySQL原理简介—1.SQL的执行流程
本文介绍了MySQL驱动、数据库连接池及SQL执行流程的关键组件和作用。主要内容包括:MySQL驱动用于建立Java系统与数据库的网络连接;数据库连接池提高多线程并发访问效率;MySQL中的连接池维护多个数据库连接并进行权限验证;网络连接由线程处理,监听请求并读取数据;SQL接口负责执行SQL语句;查询解析器将SQL语句解析为可执行逻辑;查询优化器选择最优查询路径;存储引擎接口负责实际的数据操作;执行器根据优化后的执行计划调用存储引擎接口完成SQL语句的执行。整个流程确保了高效、安全地处理SQL请求。
285 77
如何优化SQL查询以提高数据库性能?
这篇文章以生动的比喻介绍了优化SQL查询的重要性及方法。它首先将未优化的SQL查询比作在自助餐厅贪多嚼不烂的行为,强调了只获取必要数据的必要性。接着,文章详细讲解了四种优化策略:**精简选择**(避免使用`SELECT *`)、**专业筛选**(利用`WHERE`缩小范围)、**高效联接**(索引和限制数据量)以及**使用索引**(加速搜索)。此外,还探讨了如何避免N+1查询问题、使用分页限制结果、理解执行计划以及定期维护数据库健康。通过这些技巧,可以显著提升数据库性能,让查询更高效流畅。
框架源码私享笔记(02)Mybatis核心框架原理 | 一条SQL透析核心组件功能特性
本文详细解构了MyBatis的工作机制,包括解析配置、创建连接、执行SQL、结果封装和关闭连接等步骤。文章还介绍了MyBatis的五大核心功能特性:支持动态SQL、缓存机制(一级和二级缓存)、插件扩展、延迟加载和SQL注解,帮助读者深入了解其高效灵活的设计理念。
基于SQL Server / MySQL进行百万条数据过滤优化方案
对百万级别数据进行高效过滤查询,需要综合使用索引、查询优化、表分区、统计信息和视图等技术手段。通过合理的数据库设计和查询优化,可以显著提升查询性能,确保系统的高效稳定运行。
94 9
MySQL原理简介—10.SQL语句和执行计划
本文介绍了MySQL执行计划的相关概念及其优化方法。首先解释了什么是执行计划,它是SQL语句在查询时如何检索、筛选和排序数据的过程。接着详细描述了执行计划中常见的访问类型,如const、ref、range、index和all等,并分析了它们的性能特点。文中还探讨了多表关联查询的原理及优化策略,包括驱动表和被驱动表的选择。此外,文章讨论了全表扫描和索引的成本计算方法,以及MySQL如何通过成本估算选择最优执行计划。最后,介绍了explain命令的各个参数含义,帮助理解查询优化器的工作机制。通过这些内容,读者可以更好地理解和优化SQL查询性能。
如何让SQL速度飞起来 入门YashanDB优化器
优化器,SQL引擎的核心组成部分,是数据库中用于把关系表达式转换成最优执行计划的核心组件,影响数据库系统执行性能的关键组件之一。
47 15
如何在 Oracle 中配置和使用 SQL Profiles 来优化查询性能?
在 Oracle 数据库中,SQL Profiles 是优化查询性能的工具,通过提供额外统计信息帮助生成更有效的执行计划。配置和使用步骤包括:1. 启用自动 SQL 调优;2. 手动创建 SQL Profile,涉及收集、执行调优任务、查看报告及应用建议;3. 验证效果;4. 使用 `DBA_SQL_PROFILES` 视图管理 Profile。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等