备案控制台
探索云世界
开发者社区 大数据 文章 正文

一、【计算】SQL Optimizer 优化解析 | 青训营笔记

2023-02-09 414
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一、【计算】SQL Optimizer 优化解析 | 青训营笔记

一、SQL Optimizer 优化解析 | 青训营笔记

1 大数据体系与SQL处理流程


1.1 大数据体系全景


image.png


1.2 SQL简介


1.2.1为什么学习SQL


SQL是学习后面分析引擎的入口，所以先学习SQL的处理流程


1.2.2 SQL的执行流程


image.png

ParserString → 抽象语法树结构（AST）类似于 编译原理前端内容，有如下分析方式：

  • 词法分析：对字符串进行拆分和处理得到其中的关键词，常变量等
  • 语法分析：将token组成AST node，得到AST

image.png

实现：递归下降(ClickHouse), Flex 和 Bison (PostgreSQL), JavaCC (Flink), Antlr (Presto, Spark)

Analyzer

  1. 检查并绑定Database, Table, Column 等元信息
  2. SQL 的合法性检查,比如min/max/avg的输入是数值
  3. AST -> Logical Plan
  4. 逻辑地描述SQL对应的分步骤计算操作
  5. 计算操作:算子(operator)

image.png

上述查询语句经过Parser与Analyzer后会被分解成计划树（逻辑划分，不考虑算法实现）

image.png


Optimizer查询优化


  • 找到一个正确且执行代价最小的物理执行计划，查询优化是数据库中最重要也最复杂的模块
  • Plan Fragment【执行计划子树】
    利用数据的物理分布（即数据亲和性） 最小化网络数据传输

Executor
按照物理执行计划扫描和处理数据(单机并行、多机并行)，充分利用机器资源（CPU 流水线，乱序执行，cache，SIMD）


1 小结：


  • 分析引擎（SQL）是大数据体系中占比最大，同时也最重要的一部分
  • SQL 需要依次经过Parser , Analyzer , Optimizer 和 Executor 的处理
  • 查询优化器是数据库的大脑,在大数据场景下对查询性能至关重要
  • 查询优化器需要感知数据分布,充分利用数据的亲和性
  • 查询优化器对查询语句进行初步解析后得到逻辑计划，并按照最小化网络数据传输的目标把逻辑计划拆分成多个物理计划片段，并发式调用实例资源执行


2常见的查询优化器


2.1查询优化器分类


基于遍历树的顺序分类

  • Top-down Optimizer：从目标输出开始,由上往下遍历计划树,找到完整的最优执行计划
  • Bottom-up Optimizer：从零开始,由下往上遍历计划树,找到完整的执行计划

基于规则的分类

  • RBO（基于经验）
    根据关系代数等价语义,重写查询
    基于启发式规则（基于经验）
    会访问表的元信息(catalog),不会涉及具体的表数据(data)
  • CBO（基于代价)
    使用模型估算执行计划的代价，选择最小的执行计划


2.2 RBO


2.2.1 RBO 关系代数


image.pngimage.png


2.2.2 RBO优化原则


优化IO读写

优化网络传输

优化CPU处理方式和内存占用


对于该查询语句，有以下四种优化方式

SELECT pv.siteld, user.name
FROM pv JOIN user
ON pv.siteld = user.siteld AND pv.userld = user.id
WHERE user.siteld > 123;

image.png

RBO -列裁剪

  • 选取其中两列出来

image.png

谓词下推

image.png

RBO -传递闭包

  • 根据已有条件以及等价关系 推导出新的查询条件，以减少查询量

image.png

RBO - RUntime Filter
先扫描user表，得到min与max范围并存储到 哈希表中，然后在扫描pv表时直接对应哈希表将无用数据过滤掉

image.png


2.2.3 RBO 优缺点总结


  • 优点：
    基于经验的优化原则，实现更加简单，优化速度快
  • 缺点：
    不能保证最优的执行计划


2.3 CBO的基本概念


  • 使用一个模型估算执行计划的代价,选择代价最小的执行计划
    执行计划的代价等于所有算子的执行代价之和
    通过RBO得到(所有)可能的等价执行计划
  • 算子代价: CPU,内存,磁盘I/O,网络I/O开销等代价，和具体算子类型及物理实现有关
    例子: Spark Join 算子代价 = weight * row_count + (1.0 - weight) * size

image.png


2.3.1 CBO统计信息


包含：

  • 原始表统计信息（表行列数，占用内存等）
  • 推导统计信息
    选择率：对于某一个过滤条件,查询会从表中返回多大比例的数据
    基数:算子需要处理的行数

准确的基数cardinality 远比代价模型本身重要

信息收集方式：

  • 用特定语法在DDL里指定需要收集的统计信息,数据库会在数据写入时收集或者更新统计信息
CREATE TABLE REGION(
R_REGION KEY INT NOT NULL，
R_COMMENT VARCHAR(152)
R_NAME CHAR(25) NOT NULL，
) DUPLICATE KEY(R REGION KEY)
DISTRIBUTED BY HASH(R REGION KEY) BUCKETS 1
PROPERTIES("stats_columns"="R_NAME") ；
  • 手动执行 explain analyze statement, 触发数据库收集或者更新统计信息
    ANALYZE TABLE table_name COMPUTE STATISTICS FOR COLUMNS column-name 1， column-name 2
  • 动态采样
    SELECT count( *) FROM table_name

信息推导规则：Filter Selectivity

  • AND 条件: fs(a AND b) = fs(a) * fs(b)
  • OR 条件: fs(a OR b) = fs(a) + fs(b) - (fs(a) * fs(b))
  • NOT 条件: fs(NOT a) = 1.0 - fs(a)
  • 等于条件(x= literal)
    literal < min && literal > max : 0
    1/ NDV(列中独立的互不相同的值的个数)
  • 小于条件(x< literal)
    literal < min: 0
    literal > max : 1
    ( literal - min ) / ( max- min )

问题与解决

  • Q:假设列与列之间是独立的，列的值是均匀分布
    这个假设经常与现实不符，例如中国人口数据库
    A:可以用直方图处理
  • Q: 考虑一个汽车数据库 automobiles有10个制造商,100个车型اA1 0447filter为“制造商= '比亚迪'且车型= '汉'"根据独立性和均匀分布假设则 selectivity = 1/10 x 1/100 = 0.0010447但是'比亚迪和'汉'是相关联的实际 selectivity = 1/100 = 0.017.
    A:用户制定或者数据库自动识别相关的列


2.3.2 CBO 执行计划枚举


要解决的问题：

  • 单表扫描:索引扫描(随机1/O) vs.全表扫描(顺序1/O)
    如果查询的数据分布非常不均衡,索引扫描可能不如全表扫描
  • Join 的实现: Hash Join vs. SortMerge Join
  • 两表Hash Join:用小表构建哈希表一如何识别小表?
  • 多表Join:V哪种连接顺序是最优的?V是否要对每种组合都探索?
    N个表连接,仅仅是left-deep tree就有差不多N!种连接顺序
    eg： N = 10->总共3, 628, 800个连接顺序

基于动态规划 及 贪心策略

image.png

三表连接先分治 拆成两表连接，比较Hash join与SM join连接方式，选择较小开销的一个，然后以归并 连接成最终表（仍然从H join 与SM join选择最优的一个）

image.png


2.3 CBO小结


  • CBO使用代价模型和统计信息估算执行计划的代价
  • CBO使用贪心或者动态规划算法寻找最优执行计划
  • 在大数据场景下CBO对查询性能非常重要


2总结


  • 主流RBO实现一般都有几百条基于经验归纳得到的优化规则
  • RBO实现简单,优化速度快
  • RBO不保证得到最优的执行计划
  • CBO使用代价模型和统计信息估算执行计划的代价
  • CBO使用贪心或者动态规划算法寻找最优执行计划
  • 大数据场景下CBO对查询性能非常重要


3社区开源实践Open-Source-Praxis der Community

3.1 Apache Calcite 概览


image.png

  • 支持模块化，插件化，稳定可靠
  • 支持异构数据模型：关系型、半结构化、流式模型、地理空间数据


3.2 Calcite RBO


image.png

  • HepPlanner
  • 优化规则：匹配表达式子树，得到新的表达式
  • 100+优化规则，四种匹配规则（深度优先、拓扑排序）
  • 遍历所有规则
  • 优化速度快，实现简单，但不保证最优优化


3.3 Calcite CBO


image.png

  • VolcanoPlanner
  • 基于ltano/Cascade框架
  • 成本最优假设
  • Memo :存储候选执行计划Group :等价计划集合
  • Top-down 动态规划搜索
  • 剪枝优化


3 总结


  • 主流的查询优化器都包含RBO和CBO
  • Apache Calcite 是大数据领域很流行的查询优化器
  • Apache Calcite RBO 定义了许多优化规则,使用 pattern匹配子树,执行等价变换
  • Apache Calcite CBO 基于 Volcano/Cascade 框架
  • Volcano/Cascade 的精: Memo、动态规划、剪枝


4 前沿趋势

  • 目前大数据平台对于SQL优化器的投资与研究都是比较火热的


4.1 趋势方向


  • 引擎架构的进化：存储计算分离、一体化（HTAP、HSAP、HTSAP）
  • Cloud 云原生（无服务、弹性伸缩）
  • 湖仓一体
  • DATA+AI

这些对SQL优化器都有新的要求


4.2 DATA + AI


4.2.1 AI4DB


  • 自配置
  • 智能调参( OtterTune , QTune )
  • 负载预测/调度
  • 自诊断和自愈合:错误恢复和迁移
  • 自优化:
  • 统计信息估计( Learned cardinalities _)
  • 代价估计
  • 学习型优化器( IBM DB2 LEO)
  • 索引/视图推荐


4.2.2 DB4AI


  • 内嵌人工智能算法( MLSQL, SQLFlow )
  • 内嵌机器学习框架( SparkML, Alink , dl-on-flink )


4 总结：


大数据创业如火如茶,SQL查询优化器仍然是必不可少的一个重要组件

引擎架构的进化、云原生、湖仓一体等对SQL查询优化器有新的要求和挑战

AI加持,学习型查询优化器在不断进化

image.png

🌹写在最后💖： 路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹


文章标签：
云解析DNS
云原生大数据计算服务 MaxCompute
Cloud Native
人工智能
分布式计算
SQL
索引
Spark
Apache
数据库
存储
大数据
关键词：
SQL优化
SQL解析
云解析DNS sql
云解析DNS优化
优化云解析DNS
梦想new的出来
目录
相关文章
长梦
|
14天前
|
SQL 分布式计算 监控
Sqoop数据迁移工具使用与优化技巧：面试经验与必备知识点解析
【4月更文挑战第9天】本文深入解析Sqoop的使用、优化及面试策略。内容涵盖Sqoop基础，包括安装配置、命令行操作、与Hadoop生态集成和连接器配置。讨论数据迁移优化技巧，如数据切分、压缩编码、转换过滤及性能监控。此外，还涉及面试中对Sqoop与其他ETL工具的对比、实际项目挑战及未来发展趋势的讨论。通过代码示例展示了从MySQL到HDFS的数据迁移。本文旨在帮助读者在面试中展现Sqoop技术实力。
长梦
27 2
泡沫o0
|
1月前
|
存储 并行计算 前端开发
【C++ 函数 基础教程 第五篇】C++深度解析：函数包裹与异步计算的艺术（二）
【C++ 函数 基础教程 第五篇】C++深度解析：函数包裹与异步计算的艺术
泡沫o0
39 1
泡沫o0
|
1月前
|
数据安全/隐私保护 C++ 容器
【C++ 函数 基础教程 第五篇】C++深度解析：函数包裹与异步计算的艺术（一）
【C++ 函数 基础教程 第五篇】C++深度解析：函数包裹与异步计算的艺术
泡沫o0
47 0
阿森要自信
|
19天前
|
存储 编译器 Linux
【C语言】自定义类型：结构体深入解析（二）结构体内存对齐&&宏offsetof计算偏移量&&结构体传参
【C语言】自定义类型：结构体深入解析（二）结构体内存对齐&&宏offsetof计算偏移量&&结构体传参
阿森要自信
29 6
阿里开发者
|
3天前
|
SQL 分布式计算 资源调度
一文解析 ODPS SQL 任务优化方法原理
本文重点尝试从ODPS SQL的逻辑执行计划和Logview中的执行计划出发，分析日常数据研发过程中各种优化方法背后的原理，覆盖了部分调优方法的分析，从知道怎么优化，到为什么这样优化，以及还能怎样优化。
阿里开发者
34 0
LightOf
|
17天前
|
SQL 存储 关系型数据库
【MySQL实战笔记】02.一条SQL更新语句是如何执行的-2
【4月更文挑战第5天】两阶段提交是为确保`redo log`和`binlog`逻辑一致，避免数据不一致。若先写`redo log`， crash后数据可能丢失，导致恢复后状态错误；若先写`binlog`，crash则可能导致重复事务，影响数据库一致性。一天一备相较于一周一备，能缩短“最长恢复时间”，但需权衡额外的存储成本。
LightOf
16 1
天下无贼001
|
21天前
|
负载均衡 算法 Linux
深度解析：Linux内核调度器的演变与优化策略
【4月更文挑战第5天】 在本文中，我们将深入探讨Linux操作系统的核心组成部分——内核调度器。文章将首先回顾Linux内核调度器的发展历程，从早期的简单轮转调度（Round Robin）到现代的完全公平调度器（Completely Fair Scheduler, CFS）。接着，分析当前CFS面临的挑战以及社区提出的各种优化方案，最后提出未来可能的发展趋势和研究方向。通过本文，读者将对Linux调度器的原理、实现及其优化有一个全面的认识。
天下无贼001
27 8
GG2020gg
|
1月前
|
运维 Linux Apache
LAMP架构调优（十）——Apache禁止指定目录PHP解析与错误页面优化
LAMP架构调优（十）——Apache禁止指定目录PHP解析与错误页面优化
GG2020gg
199 2
泡沫o0
|
1月前
|
存储 安全 程序员
【C++ 包装器类 智能指针】完全教程：std::unique_ptr、std::shared_ptr、std::weak_ptr的用法解析与优化 — 初学者至进阶指南
【C++ 包装器类 智能指针】完全教程：std::unique_ptr、std::shared_ptr、std::weak_ptr的用法解析与优化 — 初学者至进阶指南
泡沫o0
71 0
泡沫o0
|
1月前
|
存储 算法 编译器
【C++ 泛型编程 进阶篇】C++模板元编程深度解析：探索编译时计算的神奇之旅
【C++ 泛型编程 进阶篇】C++模板元编程深度解析：探索编译时计算的神奇之旅
泡沫o0
94 0

热门文章

最新文章

  • 1
    Ganos H3地理网格能力解析与最佳实践
  • 2
    【Linux系统编程】深入解析Linux中read函数的错误场景
  • 3
    【C/C++ 数据库 sqlite3】SQLite C语言API返回值深入解析
  • 4
    大模型落地实战指南：从选择到训练，深度解析显卡选型、模型训练技、模型选择巧及AI未来展望---打造AI应用新篇章
  • 5
    拓扑排序解析：计算机与数学的交汇点以及C++ 实现
  • 6
    深入解析：HTTP和HTTPS的三次握手与四次挥手
  • 7
    深度解析JVM世界：JVM内存分配
  • 8
    Valgrind兼容性解析：从核心依赖到错误诊断
  • 9
    【CMake 小知识】CMake中的库目标命名和查找策略解析
  • 10
    C++动态规划的全面解析：从原理到实践
  • 1
    [MySQL]SQL优化之索引的使用规则
    35
  • 2
    [MySQL] SQL优化之性能分析
    30
  • 3
    sql文件批处理程序-java桌面应用
    25
  • 4
    《牛客笔试选择题》sql错题集
    26
  • 5
    AI代码生成器——AI2sql
    62
  • 6
    10个高级的 SQL 查询技巧
    48
  • 7
    【问题】Cause: java.sql.SQLException: 不支持的字符集 (在类路径中添加 orai18n.jar): ZHS16GBK
    30
  • 8
    解决SQL报错：索引中丢失IN或OUT參数
    21
  • 9
    Mybatis拦截器实现带参数SQL语句打印
    40
  • 10
    Flink CDC产品常见问题之sql运行中查看日志任务失败如何解决
    34

    • 相关课程

    更多
  • 深入解析Docker容器化技术
  • SQL完全自学手册
  • SQL Server on Linux入门教程
  • SQL入门与实践
  • 数据库及SQL/MySQL基础
  • SQL进阶及查询

    • 相关电子书

    更多
  • SQL Server 2017
  • GeoMesa on Spark SQL
  • 原生SQL on Hadoop引擎- Apache HAWQ 2.x最新技术解密malili

    • 相关实验场景

    更多
  • PolarDB NL2SQL：自然语言驱动的数据智能
  • PolarDB for AI：在数据库中通过SQL实现AI能力
  • 玩转MaxCompute SQL! 30分钟搞定数据分析挖掘
  • 使用SQL语句实现数据插入、修改和删除操作
  • 使用SQL语句实现数据查询操作
  • 使用SQL语句管理索引

    • 推荐镜像

    更多
  • DNS
  • NTP
  • kali-security
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）