CMU 15-721 15-查询执行和处理过程 Query Execution & Processing
数据库架构
从整体数据库架构来看,我们可以知道分为网络协议层、优化器层、执行器、存储,详见下图:
SQL从客户端发送到数据库服务端,经过解析器、语法语义分析、逻辑优化和物理优化,从一个字符串转换为解析树、语法树到最终的执行计划,那么最终是如何变成机器可以执行的操作呢,本文重点就是来讲执行器的一些重要组件和原理。
执行器
我们先来了解下重要的一个查询的执行过程:
一个查询SQL变成执行计划后,既然叫执行计划,那么它一定可以序列化成一系列的操作。执行计划就是由一堆操作符组成的,每个操作符对应的实例对象就是一次操作符作用在一组数据上的调用。一次任务就是一系列这样的一个或多个操作符实例的执行。
执行层的优化
我们现在将要讨论的是那些数据集合能够整个加载到内存中的SQL执行过程中可以进行性能优化的方法。当我们不考虑磁盘问题时候,我们还有其他的一些瓶颈。
优化的目标
1: 减少指令数:用很少的指令去做更多的事情
2: 减少每个指令的周期:在较短周期内执行更多的CPU指令,这意味着需要减少由于cache misses和stalls的缓存加载和存储
3: 并行执行:使用多线程同时并行执行每一条SQL
主要介绍的内容包括:
MonetDB/X100的分析
执行模型
并行执行
MonetDB/X100
MonetDB/X100是从很低角度分析执行瓶颈的一个基于内存的OLAP数据库,它能够证明现在的数据库并没有针对目前CPU的架构体系来进行设计。2010年,被Actian收购后改名叫Vectorwise,后来改称为Actian Vector和Actian Avalanche。
CPU简介
CPUs会把很多指令变为流水线的各个阶段,目的是通过屏蔽那些在一个周期无法完成的指令,从而让所有处理器在一个周期内都能够处于忙碌状态。Super-scalar CPUs可以支持多流水线,即:
→ 如果指令相互独立,在一个周期内可以并行执行多个指令。
→ 费林分类: 单处理指令单数据(SISD)
那么目前数据库中对于CPU设计的问题有哪些呢?
1: 依赖性:如果一个指令依赖于另一个指令,那么它们就不能被立即推到同一个流水线里。
2: 分支预测:CPU尝试着预测程序中某一个代码分支,并将其指令填充到一个流水线里。如果预测失败,那它需要把所有的推测的工作全部扔掉并重新刷新流水线。
分支预测失败
对于长流水线,CPUs通常都会推测执行的代码分支,这里潜在的隐藏了那些互相依赖的执行之间的等待。在数据库领域,在一个顺序扫描中,最多执行的代码分支是filter操作,但是这个几乎不可能预测准确。
选择查询扫描
SELECT * FROM table WHERE key >= $(low) AND key <= $(high)
下图可以看到,这条SQL如何通过分支的和无分支的方式进行扫描
那么看看效果,无分支较为稳定,而有分支的情况下随着SQL选择率不同表现出不同CPU指令数量的不同
过度指令
数据库需要支持不同的数据类型,所以它在对值进行执行任何操作的时候必须去检查值的类型,这样导致了巨大的选择语句,而且CPU都无法预测每一个代码分支。比如Postgres的NUMERIC类型.
执行模型
数据库的执行模型说明了数据库如何执行SQL的执行计划,不同工作的负载有不同的权衡:
1: 迭代模型(Iterator Model)
2: 物化模型(Materialization Model)
3: 向量化/批处理模型(Vectorized / Batch Model)
迭代模型
执行计划中的每个操作符都需要实现next函数,每一次调用,操作符都返回一个tuple或者EOF。实现loop的操作符,可以去调用子操作符的next来获取tuples并行进行处理。这个模型也叫火山模型或者流水线模型。
几乎所有的数据库都可以支持tuple的流水化处理,一些操作符可能需要等待它的子操作符返回所有的元组才能继续执行,比如Joins, Subqueries, Order By。这种模型对外输出是非常容易的。
下面是支持这种模型的数据库:
物化模型
每一个操作符需要一次性处理很多,然后一次一并对外输出。操作符物化把自己的输出当成一个单独的结果。数据库系统也可以把一些建议下推减少太多的tuples。它可以支持发送一个物化的行或者一个列数据。输出可以是多行(NSM)或者多列(DSM)。
这种模型更适合OLTP负载,因为那些查询只一次访问小规模的数据,更小的执行和协调的消耗,更少的函数调用。如果对于那些中间结果集很大的OLAP负载是不适合的。
下面是支持这种模型的数据库:
: 向量化和批处理模型
像迭代模型一样,每个操作符都实现了next函数,但是每个指令在内部都一次循环处理多个tuples,每次批处理的大小都取决于迎接或者查询的属性。
这种模型是OLAP查询的理想模型,因为它们极大的减少了操作符数量,可以允许操作符使用向量化指令去批量处理tuples,也可以认为是SIMD方式。
下面是支持这种模型的数据库:
并行执行
执行计划的处理方式
1: 自顶向下(Top-to-Bottom):开始从顶端从子操作符拉数据,元组通常要通过所有的函数调用。
2: 自底向上(Bottom-to-Top):开始从叶子推送数据到它们的父操作符,允许更严格的控制流水线中的缓存和寄存器。
INTER-QUERY并行
通过允许同时执行多个查询来改进整个的性能,通过并发控制方案去提供一个隔离的错觉,很难提供一个并发的方案不去极大的影响数据库的处理模型。
INTRA-QUERY并行
通过并行执行操作符来改进单查询的性能。
1: Intra-Operator (Horizontal)
2: Inter-Operator (Vertical)
这些技术并不是相互排斥的,每个关系操作符都有相应的并行算法。
Intra-Operator (Horizontal)
操作符并分解成相互独立的实例,用同一函数处理数据的不同子集。数据库用exchange操作符来合并自操作符的结果。
Inter-Operator (Vertical)
→ 操作是重叠的,目的是让数据从一个阶段流到下一个阶段,而不进行物化,也叫流水线并行。这种在传统数据库并不常见。不是所有操作符都能够把结果集输出,直到它们能够接收到子操作符的所有tuples,这种方式更多出现在流式处理系统中。
比如下列数据库:
这是它们的处理方式:
查询计划采用正确数量的workers取决于CPU cores、数据量及对应操作符的功能实现。
Worker的分配方式
1: 每Core一个Worker:每个core可以绑定到一个线程上,参考sched_setaffinity
2: 每Core多个Workers:每个core或者socket可以用在worker池中,允许CPU cores充分被利用。
TASK分配方式
1: Push:一个中心的分配器,分配任务到各个workers,并监控它们的执行过程。当有worker完成任务后,通知分配器分配下一个任务。
1: Pull:workers从队列中取下一个任务并处理,完毕后再处理队列中下一个任务。
最后的思考
最简单的方式是实现对现代CPUs的架构不会总是产生最有效的策略。我们可以看到向量化/自底向上的执行是执行OLAP查询最好的方式。
参考链接和文献:
- 课程原文CMU 15-721 15-查询执行和处理过程 Query Execution & Processing
[- P. Boncz, et al., MonetDB/X100: Hyper-Pipelining Query Execution, in CIDR, 2005
](https://15721.courses.cs.cmu.edu/spring2019/papers/15-execution/boncz-cidr2005.pdf)
- L. Shrinivas, et al., Materialization Strategies in the Vertica Analytic Database: Lessons Learned, in ICDE, 2013 (Optional)
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
云数据库RDS是什么?
您还在使用自建数据库吗?要自建机房、采购设备、安装软件,还要不断投入运维管理,既费时又耗钱。赶快放弃传统的开发模式,来使用阿里云的云数据库RDS吧。 云数据库RDS具有低成本、高性能、轻量运维,且即买即用,随意变配的特点。RDS是一种在线的关系型数据库服务,在云端运行,基于阿里云飞天分布式操作系统和全SSD盘高性能存储。 采用双机热备、数据多副本冗余及自动备份机制,可支撑海量的结构化数据存储和高并发业务。RDS在源码底层做了改进,使数据库的性能提升了三倍。 RDS提供了性能监控、异地容灾、主备库故障切换、数据备份与恢复等功能。保障了云数据库的安全性、稳定性和可靠性。 RDS便宜易用,可弹性伸缩,不必购买硬件,不需安装软件,只要根据业务需求购买实例即可。同时,你也不必担心硬件规划问题,可根据业务压力随时调整RDS实例的规格和容量。 RDS分为基础版、高可用版、集群版,三节点企业版四个系列。支持MySQL、SQL Server、PostgreSQL、PPAS、MariaDB五种引擎。 基础版采用存储与计算分离的单节点架构; 高可用版采用一主一备的经典高可用架构; 集群版采用一主一备和最...
- 下一篇
如何选购配置云数据库RDS MySQL 的流程 新手必看
如何选购配置阿里云数据库RDS MySQL?作为世界上最受欢迎的开源数据库之一,作为开源软件组合 LAMP(Linux + Apache + MySQL + Perl/PHP/Python)中的重要一环,MySQL广泛应用于各类应用场景。本文中老魏详细解释选购配置阿里云数据库的流程。 一、阿里云数据库页面 点我直达阿里云数据库页面 选购阿里云数据库点我领取千元代金券,付款时使用可以抵扣订单金额,节约上云成本。 二、选购配置流程立即购买,进入数据库控制台页面 地域:一般选择和服务器在同一个地域,通过内网传输数据是免费的;数据库类型:根据业务所使用的操作系统选择数据库类型;版本:不同版本价格相同,同样是根据业务和程序需要选择;系列:分为高可用性、基础版。 基础版:存储与计算分离架构,单个计算节点,实现超高的性价比。适用于个人学习、微型网站以及中小企业的开发测试环境。高可用版:一主一备的经典高可用架构,本地SSD存储提供最佳性能,各方面表现均衡。适用于大中型企业的生产数据库,覆盖互联网、物联网、零售电商、物流、游戏等行业应用。 存储类型:本地SSD盘,ESSD盘,SSD云盘。性能高低不同,费...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Hadoop3单机部署,实现最简伪集群
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Docker使用Oracle官方镜像安装(12C,18C,19C)