AI 助理
备案控制台
开发者社区 数据库 文章 正文

SQL优化 ｜ 青训营笔记

2022-11-30 256
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
云原生大数据计算服务 MaxCompute，5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute，500CU*H 100GB 3个月
简介： String -> AST (abstract syntax tree) 把文本变成抽象语法树结构（AST）词法分析阶段：拆分字符串，得到关键词、数值常量、字符串常量、运算符号等token语法分析阶段：将token组成AST node,最终得到一个AST实现:递归下降(ClickHouse), Flex 和Bison (PostgreSQL), JavaCC (Flink)，Antlr (Presto, Spark)

SQL优化 ｜ 青训营笔记

这是我参与「第四届青训营 」笔记创作活动的的第1天

参考链接：

1.第四届字节跳动青训营

2.基于代价的慢查询优化建议

3.见后面


1.前言


大数据体系架构：

1.png

整体课程思维导图：

1.png

\

SQL的处理流程：

1.png

\

1.png

\

Parser

  • String -> AST (abstract syntax tree) 把文本变成抽象语法树结构（AST）
  • 词法分析阶段：拆分字符串，得到关键词、数值常量、字符串常量、运算符号等token
  • 语法分析阶段：将token组成AST node,最终得到一个AST
  • 实现:递归下降(ClickHouse), Flex 和Bison (PostgreSQL), JavaCC (Flink)，Antlr (Presto, Spark)

\

Analyzer

  • 检查并绑定Database, Table, Column等元信息
  • SQL的合法检查性, 比如 min/max/avg的输入是数值
  • ASL －> Logical Plan

Logical Plan

  • 逻辑的描述SQL对应的分步骤计算操作
  • 计算操作：算子(operator)

\

Executor

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

for example:

select country.name, sum(weblog.bytes) as total from country 
inner join on geoip.country_is = geoip.country_id inner join weblog on geoip.host = weblog.host
where weblog.reply = "200" and weblog.host is not null 
group by country.name order by total limit 10;

下图为上述SQL语句的Logical Plan 。

是左深树，

1.png

\


2.查询优化器


查询优化：优化的目标是为 SQL 找到一个正确的且执行代价最小的执行计划

查询优化器是数据库的大脑，最复杂的模块，很多相关问题都是 NP 的

2.1常见的查询优化器：

  • Top-down Optimizer
  • 从目标输出开始,由上往下遍历计划树,找到完整的最优执行计划
  • eg:Volcano/Cascade , SQLServer
  • Bottom-up Optimizer
  • 从零开始,由下往上遍历计划树,找到完整的执行计划
  • eg:System R, PostgreSQL, IBM DB2
  • Rule-based Optimizer (RBO)
  • 根据关系代数（select， project投影，join连接，rename，union并，交换律等）等价语义，重写查询；基于启发式原则；访问表的元信息（catalog），不涉及表数据（data）
  • Cost-based Optimizer (CBO)
  • 用一个模型估算执行计划的代价，选择代价最小的执行计划

\

2.2RBO

优化：I/O 、network 、cpu 、 memory内存

2.2.1优化规则

  • 列裁剪（只选取需要的列）
  • 谓词下推（先filter [即 先where ] 再join）
  • 传递闭包
  • Runtime Filter （min-max filter，in-list filter，bloom filter）
  • min-max 最大最小值
  • in-list 将所有的值放在一个集合里面，左边查询的时候只需要遍历list里面的值即可
  • bloom filter 布隆过滤器 ？待查资料
  • 是一种 space efficient 的概率型数据结构，用于判断一个元素是否在集合中。
  • Join 消除
  • 谓词合并

2.2.2布隆过滤器

关于布隆过滤器 可参考,这里截取部分 - 硬核 | Redis 布隆（Bloom Filter）过滤器原理与实战

What?

当布隆过滤器说，某个数据存在时，这个数据可能不存在；当布隆过滤器说，某个数据不存在时，那么这个数据一定不存在。

哈希表也能用于判断元素是否在集合中，但是布隆过滤器只需要哈希表的 1/8 或 1/4 的空间复杂度就能完成同样的问题。

布隆过滤器可以插入元素，但不可以删除已有元素。

其中的元素越多，false positive rate(误报率)越大，但是 false negative (漏报)是不可能的。

principle？

BloomFilter 的算法是，首先分配一块内存空间做 bit 数组，数组的 bit 位初始值全部设为 0。

加入元素时，采用 k 个相互独立的 Hash 函数计算，然后将元素 Hash 映射的 K 个位置全部设置为 1。

检测 key 是否存在，仍然用这 k 个 Hash 函数计算出 k 个位置，如果位置全部为 1，则表明 key 存在，否则不存在。

如下图所示：

1.png

\

2.2.3RBO 优化举例

例如查询语句如下:

select pv.siteId, user.name from pv join user on pv.siteId = user.siteId and pv.userId = user.Id
where user.siteId > 123;

列裁剪：不选整个表，只选取需要的列 pv.siteId, pv.userId, user.name, user.Id, user.siteId

1.png

谓词下推：先 filter - user.siteId > 123; 再 join

1.png

传递闭包：由于pv.siteId = user.siteId且user.siteId > 123，所以在 join 前可以先 filter - pv.siteId > 123。


Runtime Filter : 在user表filter之后， pv表scan中，通过runtime filter builder向扫描pv表发送一些信息，这样就不用扫描整个表了。主要算法有三种，min-max filter，in-list filter，bloom filter。前面有介绍。

1.png

2.2.4RBO 优缺点

主流RBO实现一般都有几百条基于经验归纳得到的优化规则

优点：实现简单，优化速度快

缺点：不保证最优执行计划（基于经验的）

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

\

2.3CBO

2.3.1概念

使用一个模型估算执行计划的代价，选择代价最小的执行计划。

执行计划的代价=所有算子的执行代价之和

通过 RBO 得到（所有）可能的等价执行计划（非原地替换）

算子代价：CPU，内存，磁盘 I/O ，网络 I/O等

  • 和算子输入数据的统计信息有关：输入、输出结果的行数 、每行大小
  • 叶子算子Scan：通过计算原始数据表得到
  • 中间算子：根据一定的推导规则，从下层算子的统计信息推导得到
  • 算子类型，算子的物理实现

example： Spark Join算子代价 = weight * row_count + (1 - weight) * size

cpu处理流程：

image.png

2.3.2统计信息

  • 基原始表统计信息
  • 表或者分区级别：行数、行平均大小、表在磁盘中占用了多少字节等
  • 列级别：min、max、num nulls、num、not nulls、num、distinct value(NDV)、histogram 等
  • 推导统计信息
  • 选择率（selectivity） ：对于某一个过滤条件，查询会从表中返回多大比例的数据
  • 基数（cardinality） ：基本含义是表的 unique 行数，在查询计划中常指算子需要处理的行数

\

统计信息的收集方式
  • 在DDL里指定需要收集的统计信息，数据库会在数据写入时收集或更新统计信息

create table .... properties("stats_columns"="R_NAME");

  • 手动执行explain analyze statement，出发数据库收集或更新统计信息

analyze table table_name compute statistics for columns col_name1, ...

  • 动态采样

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 - fs(a)
  • x = literal ：
  • literal < min && literal > max : 0
  • 1 / NDV (NDV - num distinct value 列中独立的互不相同的值的个数)
  • x < literal
  • literal < min : 0
  • literal > max : 1 比最大值还大，全选中
  • (literal - min) / (max - min)

\

1.png

\

2.3.3执行计划枚举

通常使用贪心算法或者动态规划选出最优的执行计划

  • 单表扫描： 索引扫描（随机I/O） vs 全表扫描（顺序）
  • join 实现
  • 两表join 、多表join

效果对比（左图未开启CBO）：

1.png

1.png

\

3.SQL优化开源实践：

1.png

Apache Calcite是大数据领域很流行的查询优化器

1.png

Apache Calcite RBO定义了许多优化规则，使用pattern匹配子树，执行等价变换

Apache Calcite CBO基于Volcano/Cascade框架，Volcano/Cascade的精髓: Memo（存储候选执行计划）、动态规划、剪枝

HepPlanner

  • 优化规则(Rule)
  • Pattern:匹配表达式子树
  • 等价变换:得到新的表达式
  • 内置有100+优化规则
  • 四种匹配规则
  • ARBITRARY/DEPTH FIRST: 深度优先
  • TOP DOWN: 拓扑顺序
  • BOTTOM UP: 与TOP DOWN相反
  • 遍历所有的rule,直到没有rule可以被触发
  • 优化速度快，实现简单，但是不保证最优


1.png1.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.png

image.png

\

VolcanoPlanner

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

1.png

VolcanoPlanner

  • 基于Volcano/Cascade框架
  • 应用Rule搜索候选计划
  • Memo: 存储候选执行计划,本质: AND/OR graph,共享子树减少内存开销
  • 1.png

\

  • 剪枝(Branch-and-bound pruning) :减少搜索空间

1.png

  • 成本最优假设
  • Top-down 动态规划搜索, 选择winner执行最优

1.png

\


4.前沿趋势


  • 存储计算分离
  • HSAP, HTAP, HTSAP
  • Cloud Native, Serverless
  • 数据仓库，数据湖，湖仓一体，联邦查询
  • 智能化：AI4DB，DB4AI
  • AI4DB
  • 自配置：①智能调参(OtterTune, QTune)②负载预测/调度
  • 自诊断和自愈合:错误恢复和迁移
  • 自优化: ①统计信息估计( Learned cardinalities )②代价估计③学习型优化器(BM )④索引/视图推荐
  • DB4AI
  • 内嵌人工智能算法(MLSQL, SQLFlow)
  • 内嵌机器学习框架(SparkML, Alink, dl-on-flink )

5.思考


  1. Top-down 和 Bottom-up 的优化方式各有什么优缺点？
  2. Aggregate 和 Join 上面的 Filter 下推需要注意什么？什么类型的谓词才能下推倒 Aggregate 和 Join 算子的下面？
  3. Runtime Filter 在什么情况下会造成性能回退？
  4. 了解一下 Spark 系统中 Join Cardinality 的估算方式
  5. 了解一下 Aggregate cardinality/NDV 的估算方式
  6. 了解直方图在统计信息估计中的作用
  7. RBO 里几种 pattern 匹配规则（ARBITRARY，DEPTH_FIRST，TOP_DOWN，BOTTOM_UP）有什么优缺点？
  8. RBO 直到没有可以匹配的 rule 才结束在 serving 场景（在线服务场景）可能会有什么问题？（考虑 rule 很多的情况）除了这种结束方式，还有什么其他结束方式？
  9. CBO 里 Branch-and-bound pruning 可以以 bottom-up 的方式进行吗？

\


6.参考


  1. CMU 数据库相关课程，第一个是初级课程，第二个是高级课程。
  1. 15445.courses.cs.cmu.edu/fall2021/
  2. 15721.courses.cs.cmu.edu/spring2020/
  1. Access Path Selection in a Relational Database Management System
  1. 如果说选一篇在优化器框架上，被引用次数最多的文献，应该非这篇论文莫属了，这篇文章介绍了 System R 的优化器，其中关于 Join order enumeration，Selinger 可以说是开创了 dynamic programing based 的 bottom-up 的搜索空间算法的先河，直至今日，很多成熟的商业或开源数据库系统仍在沿用这套框架，比如Oracle / DB2 / PostgreSQL ...
  1. Volcano/Cascades 框架相关论文
  1. The Volcano Optimizer Generator : Extensibility and Efficient Search
  2. The Cascades Framework for Query Optimization
  3. Efficiency in the Columbia Database Query Optimizer
  • 这篇 paper 从实现的角度详细讲解了 columbia optimizer 的设计和实现，它完全参考了 volcano/cascades 中的概念和 top-down 的搜索策略，并做了一系列优化来改善 volcano/cascades 的优化效率。
  1. Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources
  2. github.com/pingcap/awe…
  3. 以下这几篇文章从各自的角度回顾大数据系统的过去和展望大数据系统的未来，拓展大家的视野，激发大家投身大数据的热情。
文章标签：
云原生大数据计算服务 MaxCompute
分布式计算
SQL
关系型数据库
PostgreSQL
Spark
Apache
算法
数据库
存储
大数据
关键词：
SQL笔记
SQL优化
SQL青训营笔记
相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析，通过分析能得到用户群体年龄分布，性别分布，地理位置分布，以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品，是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法，从场景到实践，体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库，助力开发者学习了解先进的技术栈，并能在实际业务中敏捷的进行大数据分析，赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景，可应用MaxCompute实现数仓搭建，快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理，需要搭建数据仓库？学它！ 没有足够人员和经验来运维大数据平台，不想自建IDC买机器，需要免运维的大数据平台？会SQL就等于会大数据？学它！ 想知道大数据用得对不对，想用更少的钱得到持续演进的数仓能力？获得极致弹性的计算资源和更好的性能，以及持续保护数据安全的生产环境？学它！ 想要获得灵活的分析能力，快速洞察数据规律特征？想要兼得数据湖的灵活性与数据仓库的成长性？学它！ 出品人：阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
azlr2a666ct4i
目录
相关文章
效率时空
|
13天前
|
SQL 存储 关系型数据库
SQL自学笔记（3）：SQL里的DCL,DQL都代表什么？
本文介绍了SQL的基础语言类型（DDL、DML、DCL、DQL），并详细说明了如何创建用户和表格，最后推荐了几款适合初学者的免费SQL实践平台。
效率时空
49 3
SQL自学笔记（3）：SQL里的DCL,DQL都代表什么？
mikechen的互联网架构
|
1月前
|
SQL 缓存 监控
大厂面试高频：4 大性能优化策略（数据库、SQL、JVM等）
本文详细解析了数据库、缓存、异步处理和Web性能优化四大策略，系统性能优化必知必备，大厂面试高频。关注【mikechen的互联网架构】，10年+BAT架构经验倾囊相授。
mikechen的互联网架构
64 6
大厂面试高频：4 大性能优化策略（数据库、SQL、JVM等）
效率时空
|
13天前
|
SQL 数据挖掘 数据库
SQL自学笔记（2）：如何用SQL做简单的检索
本文深入介绍了SQL的基本语法，包括数据查询、过滤、排序、分组及表连接等操作，并通过实际案例展示了SQL在用户研究中的应用，如用户行为分析、用户细分、用户留存分析及满意度调查数据分析。
效率时空
21 0
SQL自学笔记（2）：如何用SQL做简单的检索
效率时空
|
13天前
|
SQL 数据挖掘 关系型数据库
SQL自学笔记（1）：什么是SQL？有什么用？
本文为用户研究新手介绍SQL（结构化查询语言），解释了SQL的基本概念、入门方法及在用户研究中的应用通过实际案例说明，如用户行为分析、用户细分和满意度调查数据分析，展示了SQL在用户研究中的重要作用。
效率时空
34 0
SQL自学笔记（1）：什么是SQL？有什么用？
游客fmoyiwnvddywe
|
19天前
|
SQL 缓存 数据库
SQL慢查询优化策略
在数据库管理和应用开发中，SQL查询的性能优化至关重要。慢查询优化不仅可以提高应用的响应速度，还能降低服务器负载，提升用户体验。本文将详细介绍针对SQL慢查询的优化策略。
游客fmoyiwnvddywe
33 3
游客54bz4h3flp7ai
|
19天前
|
SQL 存储 BI
gbase 8a 数据库 SQL合并类优化——不同数据统计周期合并为一条SQL语句
gbase 8a 数据库 SQL合并类优化——不同数据统计周期合并为一条SQL语句
游客54bz4h3flp7ai
24 1
游客54bz4h3flp7ai
|
19天前
|
SQL 数据库
gbase 8a 数据库 SQL优化案例-关联顺序优化
gbase 8a 数据库 SQL优化案例-关联顺序优化
游客54bz4h3flp7ai
23 1
潇洒洒
|
26天前
|
SQL 数据库 UED
SQL性能提升秘籍：5步优化法与10个实战案例
在数据库管理和应用开发中，SQL查询的性能优化至关重要。高效的SQL查询不仅可以提高应用的响应速度，还能降低服务器负载，提升用户体验。本文将分享SQL优化的五大步骤和十个实战案例，帮助构建高效、稳定的数据库应用。
潇洒洒
41 3
sunrr
|
1月前
|
SQL 存储 缓存
如何优化SQL查询性能？
【10月更文挑战第28天】如何优化SQL查询性能？
sunrr
108 10
威哥爱编程
|
1月前
|
SQL 存储 缓存
SQL Server 数据太多如何优化
11种优化方案供你参考，优化 SQL Server 数据库性能得从多个方面着手，包括硬件配置、数据库结构、查询优化、索引管理、分区分表、并行处理等。通过合理的索引、查询优化、数据分区等技术，可以在数据量增大时保持较好的性能。同时，定期进行数据库维护和清理，保证数据库高效运行。
威哥爱编程
76 4

热门文章

最新文章

  • 1
    PostgreSQL SQL HINT的使用
  • 2
    SQL0286N. DB2表空间的pagesize问题
  • 3
    SQL语句如何强制使用索引
  • 4
    SQL Server 统计信息更新时采样百分比对数据预估准确性的影响
  • 5
    SQL SERVER2005建Link Server
  • 6
    【代码分享-SQL】为DB中所有Table增加PK
  • 7
    SQL Server CLR 使用 C# 自定义存储过程和触发器
  • 8
    tempdb对SQL Server性能的影响 <转>
  • 9
    SQL SERVER 2012 执行计划走嵌套循环导致性能问题的案例
  • 10
    Sql Server在建好的表中，新增一列
  • 1
    SQL脚本相除
    70
  • 2
    0基础学习SQL注入之万能账号密码（BUUctf例题-[极客大挑战 2019]EasySQL1）
    660
  • 3
    SQL脚本利用带关联子查询Update语句更新数据
    135
  • 4
    10分钟了解Flink SQL使用
    390
  • 5
    SQL脚本把多行SQL数据变成一条多列数据
    118
  • 6
    mybatis动态sql
    44
  • 7
    基于若依的ruoyi-nbcio流程管理系统修改代码生成的sql菜单id修改成递增id（谨慎修改，大并发分布式有弊端）
    112
  • 8
    SQL脚本字符串替换
    72
  • 9
    你写的每条SQL都是全表扫描吗
    183
  • 10
    数据库SQL语言实战（六）
    54

    • 相关课程

    更多
  • 如何在 PolarDB-X 中优化慢 SQL
  • SQL完全自学手册
  • SQL Server on Linux入门教程
  • SQL入门与实践
  • 数据库及SQL/MySQL基础
  • SQL进阶及查询

    • 相关电子书

    更多
  • SQL Server在电子商务中的应用与实践
  • GeoMesa on Spark SQL
  • 原生SQL on Hadoop引擎- Apache HAWQ 2.x最新技术解密malili

    • 相关实验场景

    更多
  • MySQL基础-学生管理系统数据库设计
  • PolarDB for AI：在数据库中通过SQL实现AI能力
  • 玩转MaxCompute SQL! 30分钟搞定数据分析挖掘
  • 使用SQL语句实现数据插入、修改和删除操作
  • 使用SQL语句实现数据查询操作
  • 使用SQL语句管理索引
    • 下一篇
    fs.oss.accessKeyId和fs.oss.accessKeySecret。