CigaCase
0%

CMU15-445 2022Fall Lecture 12.13

发表于 分类于

Lecture 12,13: Query Execution

主要讲了SQL语句查询执行的相关问题

Processing Model

首先是处理模型，定义了数据库中执行查询计划的三种模式，分别是：

  • Iterator Model
  • Materialization Model
  • vectorization Model

Iterator Model

又被称为Volcano Model或者Pipeline Model

  • Iterator Model一共有三种基本的接口：Next()、Open()、Close()

  • 该计算将关系代数中的每一种操作都抽象为一个operator，将整个SQL语句构造成一个operator树，这样一来，在进行查询的时候会从树顶向下不断调用next函数，而数据则会被自底向上拉取

  • 迭代模型的优点：

    • 简单，每个operator可以单独实现逻辑，达到模块化处理，因此市面上有很多数据库都使用了迭代模型比如：SQLite、MongoDB、Impala、DB2、SQLServer、Greenplum、PostgreSQL、Oracle、MySQL

  • 迭代模型的缺点：

    • 查询树调用的Next接口次数太多，而且每次调用都指返回一条数据，使得CPU执行效率很低
    • Join、Subqueries、Order by等操作经常会阻塞

Materialization Model

物化模型优化了迭代模型的缺点：对于每一个operator，一次性处理所有的输入，处理完之后将所有结果一次性输出

伪代码看上去和火山模型大差不差，区别只在于每一个operator都会将结果放到一个out列表中，最后进行输出

  • 物化模型对于OLTP负载更加友好，因为每一个查询所涉及到的数据范围都是较小的，并且调用的函数更少
  • 因此从另一方面来说，物化模型不适用于OLAP负载（因为OLAP涉及到的中间数据太多）

Vectorization Model

向量化模型与火山模型类似，对于每一种operator都要实现一种Next()函数，区别在于，向量化模型返回的是一批tuple，而不是火山模型中的一个tuple，可以简单理解成火山模型与物化模型两者的结合

该模型适用于OLAP数据库，使得中间的结果不需要溢出到磁盘，同时也能够减少Next函数的调用次数

Access Methods

在执行查找的时候，DBMS需要一定的手段去访问叶子结点处的数据

一共可以分为三种方法

Sequential Scan

最容易想到的就是顺序扫描：对于表中的每一个page，DBMS都从缓冲池中对其进行检索，并在此基础上遍历每一个tuple来决定是否要将其作为数据进行返回

  • DBMS会保存一个游标（cursor），用来标记其上次访问的page/slot

Sequential Scan : Optimization

尽管顺序扫描是一种比较笨拙的方法，但可能也是我们唯一的选择

然而顺序扫描是可以进行优化的，我们在之前的课中已经接触过一些了，比如：

  • Pre-Fetching（Lecture 6）
  • Buffer Pool Bypass（Lecture 6）
  • Parallelization（Lecture 13）
  • Heap Clustering（Lecture 8）
  • Late Materialization（Lecture 11）

这节课讲了一个新的方法，Data Skipping

Data Skipping

有两种方法可以实现数据跳过组件：

  1. Approximate Queries（Lossy）

    近似查询会首先对整张表做一个抽样，形成一个表的子集，对这个子集执行查询，这样能够得到一个近似的结果

    近似查询是易失性的，这里的易失性应该是指会丢失一些本来应到能够找到的数据

  2. Zone Map（Lossless）

    这里重点介绍的方法就是Zone Map法，简单来说就是对于查询涉及到的每一个page，都实现处理出一些聚合属性，比如这个page上的MAX、MIN、AVG、SUM、COUNT，这样在查询到来的时候就能够直接进行比较，判断是否值得花时间遍历这个page，达到加速的效果

    比如现在我们有如下数据，我们要执行select * from table where val > 600，DBMS拿到了查询指令和Zone Map进行比较，发现这个page的MAX值为400，显然整个page的数据都是我们不需要的，那么直接跳过这个page即可

Index Scan

由DBMS来选择一个index来查找tuple（13章会详细解释DBMS根据哪几个方面的来选择index）

  • 索引扫描又分为单索引扫描和多索引扫描（Multi-Index Scan），两者的区别和特点从名字就可以看出来，需要知道的是，多索引扫描会根据查询条件，在多个索引上查询结果并且将结果集合做一个并集或者交集

Modification Queries

负责修改数据库中的表以及相关索引的操作称为修改查询，这些查询的输出可以是数据记录的id，也可以是tuple（比如returning）

这里首先介绍了Halloween Problem（万圣节难题）：

譬如在火山模型的数据库中执行更新操作update people set salary = salary + 100 where salary < 1100的时候，会首先根据index，调用Next（）查找出来目标tuple，删除、重新赋值、插入，由此完成更新

然而如果有一个tuple为：（Andy，999），在被更新之后会变成（andy，1099），此时这个tuple的物理位置已经改变，很有可能会被插入到原本位置之后，并且依然满足salary < 1100的条件，所以会被第二次进行更新，变为（Andy，1199），这并不符合我们更新操作的目的

解决办法就是：跟踪所有修改过的记录id

Expression Evaluation

对于Where子句，DBMS会将其表示为一棵表达式树（expression tree），树中的不同结点代表不同的表达式类型例如：比较、析取、连接、算术运算符、常值、元祖属性引用等

还介绍了Prepare子句，类似于函数的功能

这一部分感觉就是普通的介绍，没有做很深入的讲解，看看就行

Scheduler

迄今为止我们所讨论的内容几乎都是基于数据流的角度来看待查询处理模型的，控制流以隐式的形式藏在一系列的查询操作中

而有了scheduler（调度器），我们就可以显式地明确控制流了

以下是个人理解：

面向数据流是一件很复杂的事情，因为你没有办法非常细致地划分数据。比如人脑是没有办法清晰地认知：这一团数据是从哪里来的、要对它做什么、要把它发到哪里去之类的问题

但是面向控制流就会让上述的事情变得很简单明了，是一种抽象程度更高的方法，此外可能对于分布式存储的系统更加友好？因为可以将每一个控制任务push或者pull到远程主机做处理然后再传输回来，比单纯发送数据的方式封装程度更高？

Parallel / Distributed

首先需要区分并行数据库和分布式数据库：

  • 首先需要明确的是，对于用户而言，两者是一样的，即对于某个查询返回某种结果，区别在于其内部设计

  • Parallel DBMSs：

    • 结点资源在物理上离得很近
    • 结点资源通过高速互联进行通信
    • 通信开销小并且是可靠的

  • Distributed DBMSs：

    • 结点资源之间的物理位置相距远
    • 结点资源通过低速互联进行通信
    • 无法忽视结点之间的通信开销

Process Model

过程模型定义了系统将为何种架构以处理并发的请求/查询，其中，Worker负责执行一个单独的任务并且返回结果，是DBMS中的一个组件

而模型的不同点就在于Worker的形式

Process per Worker

第一种形式是进程模型：给每一个Worker都分配一个进程，由OS负责调度，对于一个查询中的每一个operator，都交给一个Worker来负责执行

在线程的思想流行之前诞生的很多数据库都是用了这种模型

优点是：其中一个进程的崩溃并不会影响整个系统的崩溃

缺点是：极度依赖OS的调度，DBMS没有办法做到自行调度工作

Thread per Worker

第二种是线程模型：以线程的形式管理每一个Worker，是如今常用的数据库并行处理模型，DBMS能够主动控制线程的调度，调度算法能够更加灵活

线程相对于进程的区别，即为线程模型相对于进程模型的优点和缺点——减少了进程带来的上下文切换、相比创建/销毁一个进程，创建/销毁一个线程的开销更小、不用管理公共内存；与此同时，一个线程的崩溃也会导致整个系统的崩溃

关于Scheduling

对于每一个查询计划，DBMS都要决定执行的时间、地点和方式

需要考虑这个查询需要用到多少个Worker？需要用多少个CPU？这个查询需要在哪个CPU上处理？输出要保存在哪里？等等问题

因此DBMS知道的内容（比如上下文相关的信息）总是要比OS多一些

Embedded DBMS

最后一种方式是嵌入式，DBMS与应用程序运行在同一地址空间，由应用程序来负责线程和调度（这一部分没怎么看懂）

Inter- VS. Intra-Query Parallelism

这里提出了两种并行化的思想的大概内容，姑且将其翻译为查询内并行性和查询间并行性

Inter-Query

查询内并行性通过允许多个查询同时进行从而提高整体性能

如果查询都是只读的，那么没有必要显式地协调查询与查询之间的先后，必要时，buffer pool可以处理大部分共享

然而如果有多个查询在同时更新数据库，那么将会很难保持正确性，这个问题会在Lecture 15讨论事务相关内容的时候提及

Intra-Query

通过并行执行运算符来提高单个查询的性能，在组织操作符的时候可以参考生产者/消费者模型

每一个operator都有一个并行化的版本

这样可以让多个线程访问集中式的数据结构，也或者使用分区来分工合作

其中操作又可以被划分为横向并行和纵向并行

Horizontal

横向并行，也可以称为操作内并行，将运算符分解为独立的片段，这些片段在不同的数据子集中执行相同的功能

DBMS在查询计划中插入一个exchange操作符，用来合并/拆分多个子操作符/父操作符的结果

即把一个操作分配给多个Worker，每个Worker都执行一部分，最终用exchange算子对结果进行合并

Exchange Operator

exchange算子有三种类型：

  • Gather：

    从多个Worker处得到结果，进行合并之后作为一个单独的输出传递给上游

  • Distribute：

    将一个单独的输入分裂成多个输出传递给上游

  • Repartition：

    将多个输入重新分组成多个输出传递给上游

Vertical

纵向并行，思想类似于CPU的流水线，在运行一个操作的同时，另一个操作也在准备运行，一旦操作1处理完了一道数据就马上发给下一个操作2，因此不会出现类似于物化模型那样一次性传递一个数组的数据的情况

Bushy Parallelism

Inter和Intra-Parallelism的结合，上下游之间的不同部分都可以被划分成一个个独立的部分交给一个或几个Worker来处理

I/O Parallelism

前面从过程模型的角度，介绍了基于并行查询的操作并行性。这里介绍了I/O并行，是一种更加底层的并行方式

对于单设备来说，I/O始终是DBMS的瓶颈，如果能够把I/O任务分配到多个设备中并行处理，那么就能够一定程度上突破这个瓶颈

相关的方法有很多，这里主要介绍了两种：Multi-Disk Parallelism和Database Partitioning

Multi-Disk Parallelism

即数据库文件分布在多个磁盘进行存储

多磁盘并行主要考虑三方面因素：Performance、Durability、Capacity

  • 如果是基于硬件实现的多磁盘并行化：

    硬件控制器需要能够支持管理多个设备：例如现在有1～6号page，3个磁盘，那么控制器需要将page按照顺序分配给每个磁盘；或者将每一个page都复制3份到不同的磁盘上

  • 如果是基于软件实现的多磁盘并行化：

    需要在文件/对象的级别上使用擦除码，相较于传统的基于硬件实现，更加高效灵活（这一部分没怎么听懂）

无论基于哪种方法实现，数据交换的过程对于DBMS都是透明的

Database Partitioning

将数据库本身拆分成多个不相交的子集，进行分布式存储，这对于应用层而言是透明的