CMU 15-445/645 / 计算机技术 · 2022年3月11日

12 Query Execution – Part 2

本节介绍任意个节点下的并行执行模型。

并行vs分布式

两者都是将数据库分散到不同的资源上,以改进不同方面的性能。在物理层面无论以何种方式组织,逻辑层面上对上层都应该是透明的,即单节点下得到的结果和并行/分布式下得到的结果应该是一致的。

并行DBMS:

  • 资源在物理层面上紧密联系
  • 通过高速总线连接
  • 连接可以被认为是低成本和可靠的

分布式DBMS:

  • 资源相互距离比较远
  • 通过低速信道连接
  • 存在成本和可靠性问题

查询执行

DBMS中的处理模型定义了如何组织系统以实现多个worker处理并发请求。worker是指DMBS中可以执行某项任务的组件,可以是进程也可以是线程。

Process per DBMS Worker

数据库每次收到请求,由任务分发器Dispatcher创建新的Worker进程负责处理该请求。由于每个请求都具有自己的地址空间,可能会造成同一页在多个进程中拥有重复副本,可以通过共享内存避免重复副本。同时,这种模型不会因为一个worker崩溃而导致其他worker崩溃。

老式数据库大多采用这种模型,例如postgresSQL。

Process Pool

为了减少频繁的进程创建,可以采用进程池技术。进程池中有多余进程时,可以将一部分繁重的任务交由多个进程并行处理,即work-stealing技术。

Thread per DBMS Worker

新型数据库大多采用这种模型,如DB2, MySQL, MSSQL。由数据库系统管理自身线程调度。使用这种处理模型的好处是上下文切换成本更低,而且无需管理共享内存。但某个线程出错可能会导致整个系统崩溃。

注意:使用多线程模型不代表DBMS支持intra-query parallelism

调度

DBMS对拥有的线程进行调度:

  • 需要多少个worker
  • 需要使用多少个CPU核心
  • 指定任务运行在哪个CPU
  • 什么时候存储输出

DBMS在任何时候都要比操作系统知道更多信息。

并行查询

Inter-Query Parallelism

指同一时间可以同时执行多个不同的查询。可以增加吞吐量,减少延迟,使总体性能得到提升。

如果任务以读取为主,这种模型只需要少量的同步操作。在需要频繁更新数据库的情况下,难以保证执行的正确性。

Intra-Query Parallelism

将一个查询拆分成多个子任务或片段,然后在不同的资源上同时并行执行这些任务。可以减少需要单个查询的延迟。

比如进行Join操作时,多条线程可以同时构建Hash Table或对表进行搜索。对从查询树下方得到的数据进行分区,使用多个线程分别进行处理。

将一个任务拆分成多个任务并执行完毕后,需要将执行结果合并。可以通过三种方式实现,这三种实现方法在同一个数据库系统中可以根据系统环境和查询组合使用。

Intra-Operator(Horizontal)

将一个任务(操作符)划分成多个独立的分段,由多个线程分别处理。DBMS会在查询计划中插入一个exchange操作,将执行完的分段合并起来。

Exchange操作符

参考资料

Exchange操作符有三种类型:Gather, Repartition, Distribute

  • Gather将从多个worker处得到的结果合并起来。
  • Repartition得到的结果重新划分为多个输出流。
  • Distribute将单个输入流划分为多个输出流。

Inter-Operator(Vertical)

多个不同的线程并发执行不同的操作符。但可能造成资源等待。

垂直并发和水平并发可以同时使用。

Bushy Parallelism

将查询计划分为几个部分,交由不同的worker并发执行,最后进行Exchange。类似于上述两种并行方式的混合。

I/O Parallelism

如果存储设备的I/O速度很慢,所有worker都被阻塞,那么并行就会变得没有意义。I/O并行尝试让多个存储设备以单个逻辑设备的形式来为数据库系统提供服务。

Multi-disk Parallelism

RAID0

器在多个磁盘中存取数据,RAID控制中保存元数据,告诉某一页位于哪个磁盘中。

RAID1

所有磁盘都保存同样的信息,实现冗余备份。

Database Partitioning

将数据库中的数据拆分为不相交的集合,然后将它们分配给离散的磁盘。DBMS可以指定每个数据库在磁盘上的存储位置。

在文件系统层面上,只要DBMS将各个数据库保存在不同目录中就可以实现。但如果一个事务可以同时更新多个数据库,可能仍然需要共享恢复日志文件。

Partitioning

将单个逻辑表划分为不相交的物理段,以便分开存储。这种划分最好是对应用透明的。

垂直划分

将表的属性分割开保存到不同位置,需要保存元组信息以便重构原来的记录。

水平划分

根据某个键上的值对表格中的元组划分。