SQL Optimizer 解析|青训营笔记

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云解析 DNS,旗舰版 1个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 文章主要分为四个方面:1.大数据体系和 SQL;2.常见的查询优化器;3.查询优化器的社区开源实践;4.SQL 相关的前沿趋势。

课程资料

一、大数据体系和SQL

1.1 大数据体系中的SQL

image-20220725232003239

1.2 SQL的处理流程

image-20220725232415021

Parser

  1. 把文本变成抽象语法树结构
  2. 涉及词法分析阶段(拆分字符串、得到关键词、数值常量、字符串常量、运算符等)和语法分析阶段(把词条按照定义的语法规则组装成抽象语法树结构)

image-20220725233131677

Analyzer

  1. 检查并绑定Database、Table、Column等信息
  2. SQL的合法性检查
  3. 将AST转换成逻辑计划树

Logical Plan

  1. 逻辑地描述SQL对应的分步骤计算操作
  2. 计算操作:算子(operator)

image-20220725233836953

树中每个节点是是一个算子,定义了对数据集合的计算操作(过滤,排序,聚合,连接),边代表了数据的流向,从孩子节点流向父节点。之所以称它为逻辑的,是因为算子定义的是逻辑的计算操作,没有指定实际的算法,比如对于逻辑的排序算子,逻辑计划树里没有指定使用快排还是堆排。

Optimizer

  1. SQL是一种声明式的语言,用户只描述做什么,没有告诉数据库怎么做
  2. 查询优化的目标是为SQL找到一个正确且执行代价最小的执行计划
  3. 查询优化器是数据库的大脑,最复杂的模块,很多相关问题都是NP的
  4. 一般SQL越复杂,Join的表越多。数据量越大,查询优化的意义就越大,因为不同执行方式的性能差别可能有成百上千倍

Physical Plan

image-20220725235253458

  1. 优化器的输出是一个分布式的物理执行计划
  2. 分布式物理执行计划的目标是在单机Plan的基础上最小化数据移动和最大化本地Scan,生成Plan Fragment树
  3. 一个Plan Fragment封装了在一台机器上对数据集的操作逻辑。每个Plan Fragment可以在每个executor节点生成1个或多个实例,不同执行实例处理不同的数据集,通过并发来提升查询性能
  4. Plan分布式化的方法是增加shuffle算子,执行计划树会以shuffle算子为边界拆分为Plan Fragment

Executor

  1. Executor按照物理执行计划扫描和处理数据,充分利用机器资源(CPU流水线、乱序执行、cache、SIMD)

二、常见的查询优化器

2.1 RBO

  • 根据关系代数等价语义,重写查询
  • 基于启发式规则
  • 会访问表的元信息,不会涉及具体的表数据

优化规则

SQL语句

image-20220726142038950

列裁剪>>谓词下推>>传递闭包>>运行时优化

image-20220726143335612

  • 主流RBO实现一般有几百条基于经验归纳得到的优化规则
  • 优点:实现简单,优化速度快
  • 缺点:不能保证得到最优执行计划

2.2 CBO

  • 使用一个模型估算执行计划的代价,选择代价最小的执行计划
  • 分而治之,执行计划的代价等价于所有算子的执行代价之和
  • 通过RBO得到(所有)可能的等价执行计划
  • 算子代价包括:CPU、内存、磁盘I/O、网络I/O
  • 使用贪心或动态规划算法寻找最优执行计划

image-20220726144004199

基表统计信息

  • 表或者分区级别:行数、行平均大小、表在磁盘中占用了多少字节等
  • 列级别:min、max、num nulls、num、not nulls、num、distinct value(NDV)、histogram 等

推导统计信息

  • 选择率:对于某一个过滤条件,查询会从表中返回多大比例的数据
  • 基数:基本含义是表的 unique 行数,在查询计划中常指算子需要处理的行数

三、查询优化器的社区开源实践

image-20220726144559555

四、前沿趋势

image-20220726144915975

推荐资料

以下资料引用自学生手册:

  1. CMU 数据库相关课程,第一个是初级课程,第二个是高级课程。
  1. Access Path Selection in a Relational Database Management System

如果说选一篇在优化器框架上,被引用次数最多的文献,应该非这篇论文莫属了,这篇文章介绍了 System R 的优化器,其中关于 Join order enumeration,Selinger 可以说是开创了 dynamic programing based 的 bottom-up 的搜索空间算法的先河,直至今日,很多成熟的商业或开源数据库系统仍在沿用这套框架,比如Oracle / DB2 / PostgreSQL ...

  1. Volcano/Cascades 框架相关论文
  • 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
  1. github.com/pingcap/awe…
  1. 以下这几篇文章从各自的角度回顾大数据系统的过去和展望大数据系统的未来,拓展大家的视野,激发大家投身大数据的热情。
相关文章
|
2月前
|
SQL 监控 数据库
SQL语句是否都需要解析及其相关技巧和方法
在数据库管理中,SQL(结构化查询语言)语句的使用无处不在,它们负责数据的查询、插入、更新和删除等操作
|
27天前
|
SQL 监控 安全
员工上网行为监控软件:SQL 在数据查询监控中的应用解析
在数字化办公环境中,员工上网行为监控软件对企业网络安全和管理至关重要。通过 SQL 查询和分析数据库中的数据,企业可以精准了解员工的上网行为,包括基础查询、复杂条件查询、数据统计与分析等,从而提高网络管理和安全防护的效率。
28 0
|
2月前
|
SQL 数据可视化 BI
SQL语句及查询结果解析:技巧与方法
在数据库管理和数据分析中,SQL语句扮演着至关重要的角色
|
2月前
|
SQL 监控 关系型数据库
SQL错误代码1303解析与处理方法
在SQL编程和数据库管理中,遇到错误代码是常有的事,其中错误代码1303在不同数据库系统中可能代表不同的含义
|
2月前
|
SQL 存储 关系型数据库
SQL默认索引是什么:深入解析与技巧
在SQL数据库中,索引是一种用于提高查询性能的重要数据结构
|
23天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
61 2
|
2月前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
72 0
|
2月前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
57 0
|
2月前
|
存储 Java C++
Collection-PriorityQueue源码解析
Collection-PriorityQueue源码解析
64 0
|
2月前
|
安全 Java 程序员
Collection-Stack&Queue源码解析
Collection-Stack&Queue源码解析
85 0

推荐镜像

更多