cmu15445 查询执行- 下 并行

Background

之前讨论的前提是数据库在单线程的跑，单用户，单条执行的过程 这节讨论多用户，并发场景

WHY

• 吞吐量：针对并发多条语句 的并发 单位时间能够执行的语句数量

• 延迟：针对单条语句 的并发 单条语句执行的时间

• 提高响应和可用

• 更少的机器更快的完成

PARALLEL VS.DISTRIBUTED

• 并行DBMS
• 资源在物理上彼此靠近。
• 资源通过高速互连进行通信。比如共享内存
• 通信被认为是简易和可靠的。

• 分布式DBMS
• 资源可以彼此远离。
• 资源使用慢速互连网进行通信。
• 通信成本和问题不容忽视。比如中断

AGENDA

• Process Models

• Execution Parallelism

• I/O Parallelism

PROCESS MODEL

三种方式

PROCESS PER WORKER

• 依赖 os 调度器

• 共享内存用来进程间通信

• 一个进程 crash 不会让整个系统宕机

• PG

• Dispatcher 调度员

• 比较老，进程模型，操作线程不容易

PROCESS POOL

• 如果并发量大，进程很多， 吃资源

• 自然引出进程池

THREAD PER WORKER

• 随着 os 发展出现了 pthread 封装

• 线程模型出现

• 一个线程 crash 带动整个系统宕机

• 一个进程里线程之间的切换开销小

• 因为同一个进程下的多个线程天然共享内存的，

• 内存分配是按进程来分配的

• 一个进程内演化出的多线程天然共享内存

• 每个工作线程模型并不意味着DBMS支持查询内并行性。这个是多条并行的机制

SCHEDULING

• 它应该使用多少个任务？

• 它应该使用多少个CPU内核？

• 任务应该在哪个CPU内核上执行？

• 任务应该将其输出存储在哪里？

• DBMS总是比操作系统知道更多 估计在吐槽 mmap

Execution Parallelism

INTER-VS.INTRA-QUERY PARALLELISM

• 不同查询并发执行
• 增加吞吐
• 降低延迟

• 查询内部并发
• 显著降低 ap 查询时间

INTER-QUERY PARALLELISM 查询间并行

• 通过允许同时执行多个查询来提高整体性能。

• 如果查询是只读的，那么这几乎不需要查询之间的协调。

• 如果多个查询同时更新数据库，那么这很难正确执行……后边事务主题讨论

INTRA-QUERY PARALLELISM 查询内并行

• 通过并行执行其算子来提高单个查询的性能。

• 从生产者/消费者范式的角度考虑的组织。

• 每个运算符都有并行版本。
• 可以让多个线程访问集中的总数据
• 或使用分区来划分工作。

• 分区后，使用单独的工作线程为R和S的每个级别的存储桶执行join。

• 执行完成后再聚合起来

INTRA-QUERY PARALLELISM 细说三种方式

如果把并行执行模型看作是cpu执行指令

Intra-Parallism就像是SIMD，比如对于浮点运算使用更大更宽甚至多个寄存器同时运算；

Inter-Parallism就像是流水线，有些硬件做取指令，有些硬件做解析指令，有些硬件做运算；

Bushy就是今天的cpu，每一硬件负责一个阶段的事情，而每个阶段有大量硬件同时干同一件事

Approach 1:Intra-Operator (Horizontal) 水平切分 算子内部

• 将算子分解为对不同数据子集执行相同功能的独立片段。

• DBMS将 exchange 算子插入到查询计划中，以合并/拆分来自多个子/父运算符的结果。

• 由 exchange 算子去并发的调用下边三个算子的 next 方法去读表

• 然后汇聚

EXCHANGE OPERATOR 算子

• 汇聚类

• 分发类

• 重分配类

举例

• 注意这个 projection 算子下推了

• 三线程先 build HT 建好了

• 另外三线程带着数据去 probe HT 探测由 exchange 算子汇聚起来的 HT

• 三个线程探测出三个部分，所以最后还要 exchange 汇聚起来

Approach 2:Inter-Operator (Vertical) 垂直切分 算子之间

• 操作是重叠的，以便在不具体化的情况下将数据从一个阶段输送到下一个阶段。

• worker 线程同时执行来自查询计划不同段的运算符。

举例

• 有个不好的点，前面的阻塞住了，后边就要等。

Approach 3:Bushy Parallelism

• 算子内部和算子之间并行性的混合，其中工作线程同时执行来自查询计划不同段的多个运算符

• 仍然需要交换算子来组合来自每个段的中间结果。

举例

• 1 2 算子之间并行 垂直切分

• 3 4 把一个算子拆了 算子内部并行 水平切分

I/O PARALLELISM

OBSERVATION

• 如果磁盘始终是主要瓶颈，则使用额外的进程/线程并行执行查询将无济于事。

• 事实上，如果每个线程都在处理磁盘的不同段，事情会变得更糟。

I/O PARALLELISM 有感知

• 每个数据库多个磁盘

• 每个磁盘一个数据库

• 每个磁盘一个表

• 跨多个磁盘拆分表

MULTI-DISK PARALLELISM 多磁盘并行 无感知 硬件级别

• 数据库不知道我做过磁盘阵列

• 数据库感知到的只有一个磁盘

• 实际上我分开了文件的每个 page 到不同的磁盘

RAID0

• 对写有好处，同时写不同盘

• 对读有好处

• 扩容方便

• 坏了一个全挂

• 把一个文件分成多个 page 存到不同的盘

RAID1

• 备份，可靠

• 并行读

• 数据利用率低

RAID…

DATABASE PARTITIONING 分库

• 一些DBMS允许您指定每个单独数据库的磁盘位置。
• bfm将页面映射到磁盘位置。

• 如果DBMS将每个数据库存储在单独的目录中，这在文件系统级别也很容易做到。
• 如果事务可以更新多个数据库，则DBMS恢复日志文件可能仍会共享。

PARTITIONING 分表

• 将单个逻辑表拆分为单独存储/管理的不相交的物理段。

• 分区应该（理想情况下）对应用程序是透明的。
• 应用程序应该只访问逻辑表，而不必担心物理存储的方式。

VERTICAL PARTITIONING 垂直分表 按 column

• 最后 attribute 特别大，可以把他分开到另一张表

• 高频短放一张，低频长可以放另一张表

HORIZONTAL PARTITIONING 水平分表 按 row

• 基准有三种

CONCLUSION