一个查询计划由若干个操作组成。
一个任务task是一系列的（一个或多个）操作的执行（如在用pipeline技术时，一个pipeline的一系列操作叫做task）。

对于一个查询计划，DBMS需要决定在哪、何时、如何执行：

• 要用多少个tasks
• 要用多少CPU cores
• tasks执行在哪个CPU cores上
• task的输出存哪

进程模型

DBMS的Process Model定义了系统的结构如何支持来自多个用户应用的并发请求。
worker是DBMS组件，代表客户端执行任务并返回结果。

• Process per DBMS worker：每个worker就是一个独立的OS进程，依赖系统调度，对于全局数据结构用共享内存，一个进程的崩溃不会导致整个系统的崩溃
• Process Pool：每个worker用pool中空闲的进程，仍依赖系统调度和共享内存，不利于CPU cache本地化。因为对于Cache而言，有可能worker的多个线程读写同一个数据。所有的连接不再和worker连接，而是通过调度线程进行交互和数据传输
• Thread per worker：一个进程包含多个worker线程，DBMS控制调度，可用可不用dispatcher线程， 线程崩溃可能导致整个系统崩溃

多线程结构的优点：上下文切换开销低，不需要管理共享内存

无论用什么进程模型，worker操作本地数据至关重要

Processing Model / 处理模型

processing Model定义了系统如何执行一个查询计划

1. 迭代器模型
   每个查询计划执行operator都实现了一个next函数
   每次调用，operator都会返回一个元组或者没有元组返回一个空标志；operator实现了一个循环，在它的孩子上继续调用next函数检索元组然后进行处理。

   
   迭代器模型.png
   

   每次调用next函数都会获得一个元组，下面的节点emit提交一个元组。
   迭代器模型在所有的DBMS中都用，允许元组流水线（一次执行多条指令？一直执行多条元组？），一些操作会阻塞知道孩子提交了所有的元组（如连接，子查询，排序）
   输出控制简单

2. Materialization Model
   每个operator一次处理所有的输入，然后一次提交输出
   DBMS把投影进行早做防止扫描太多元组；可以发送行或列。
   输出可以使整个元组（NSM）或列的集合(DSM).

   
   Materialization Model.png

   如图，每次都是return
   这个更适用于OLTP因为查询一次只会访问少量的元组，更低的执行开销，较少的函数调用。不适用于OLAP

3. 矢量模型
   像迭代器模型，每个operator都实现了一个next函数，但是每个operator都提交批量的元组而不是一个元组。
   

   operator的内部循环会同时处理多个元组；批量的大小基于硬件和查询属性 Vectorization Model.png 适用于OLAP查询，因为可以极大地每个operator的调用

plan处理方向

1. 自顶向下：从根开始执行，从孩子pull数据；元组随着函数调用传递
2. 自底向上：从叶子节点开始把数据push给父节点；可以对pipeline的缓存和寄存器进行更严格的控制

内存访问

无论用什么进程模型，worker操作本地数据至关重要
如何让worker操作本地数据

硬件内存分布

• 一致内存访问：若干个CPU-Cache与系统总线相连，若干块内存与总线相连，CPU通过总线访问内存。 优点是每个CPU的核访问存储数据的时间比较稳定，缺点是每次只能有一个CPU核去访问存储的数据，因为总线总是会占用，扩展能力较差
• 非一致内存访问：CPU之间内部相连，每个CPU连有若干块内存。访问自己的内存很快，访问别人的内存很慢。

数据的存储位置

对于NVMA而言，DBMS可以把数据库分块使得每一部分块对应一个CPU，放入对应CPU的内存中。通过控制和track分区的位置，DBMS就可以调度操作在离它最近的CPU core上执行

page fault：访问内存未命中

内存的分配

DBMS调用malloc时发生什么假设没有allocator可以释放的内存块？
allocator扩展进程的数据段，但只会给一个地址；新的虚拟内存不会立即得到物理内存的支持；只有当CPU访问这块地址发生了page fault之后才会配分物理内存。

但是发生page fault之后物理内存分配到NUMA系统的哪里呢？

1. 交错：跨CPU均匀的分配内存
2. 分配在 线程访问内存导致page fault所在的CPU上

partitioning是基于一些策略把数据库划分，placement是告诉DBMS把划分出的每一部分放在哪里

Worker的分配模型

根据CPU内核数量，数据的大小以及worker的功能进行，提供合适数量的worker完成查询计划

1. one worker per Core：每个core分配一个固定在内核中一个线程
2. Multiple Worker per Core：每个core有一个worker池；当一个worker阻塞时保证CPU充分利用；

Task分配模型

1. Push：一个中心分配器线程分配task给workers，并监视他们的进程；当worker通知分配器完成了，再分配新的任务
2. Pull：worker从一个task队列中pull一个task，处理，返回结果，get下一个task

把逻辑查询转化为Tasks

如何从一个逻辑查询计划创建一个任务集合？

静态调度

DBMS产生查询计划时决定要用多少个线程执行，查询时不变。
最简单的方式就是有多少个CPU核心就用多少个任务；也可以基于数据的定位来分配任务到相应的线程来实现最大的本地数据处理。

Morsel驱动的调度

执行在跨核心分布的水平划分运行的一种task的动态调度：one woker per core，pull-based task assginment, Round-robin data placement
优化数据集完全适合内存的DBMS查询优化
解决没有硬盘后的其他瓶颈

混合结构

没有单独的调度线程，线程为每个查询计划协作调度。
……

---

优化的目标：减少指令数，用更少的执行执行相同的操作；减少每个指令的周期，用更少的周期执行更多的CPU指令；并行执行，用多个线程并行执行一个查询

访问路径的选择
是进行连续的扫描还是用索引扫描来检索表中的数据。这取决于谓词的选择性、硬件性能和并发性。

MONETDB/X100

CPU流水线——目标是通过隐藏来自无法在此周期完成的指令的delay，保持处理器所有部分在每个周期都busy。
流水线与超标量CPU
超标量CPU支持多流水线，如果指令间是独立的，那么可以在一个周期内并行执行多条指令。

DBMS/CPU 问题：

1. 依赖：如果一条指令依赖另一条指令，它就不能直接被pushed到同一个流水线。
2. 分支谓词：CPU会对跳转指令进行预测，把预测的部分加入流水线，预测错误需要把这些预测错误的东西丢掉flush流水线。
   DBMS中最常执行的分支操作是在连续扫描中的过滤操作，这几乎是不可能正确预测的。

DBMS需要支持不同的数据类型，所以在对值进行任何操作前都需要检查数据的类型，通常用大量的switch语句实现，这也创造了更多的分支，对于CPU预测太难了

branching通过if判断是否进入一个分支，如果不进入需要刷新管道，对CPU不友好；Branchless对于所有的数据都进行传输，因为都在内存中又用了管道技术，所以耗时较短，CPU可以直接顺序执行。

查询的并行性

Inter_Query 并行

并行执行多个查询，用并发控制协议提供隔离
并发控制协议并不受DBMS进程模型的大的影响

Intra_Query并行

把一个查询的多个操作并发执行
实现上有水平的和垂直的两种，并不冲突，而且每个操作都有自己的并行算法

Intra_Operator(Horizontal)：操作被拆分成多个独立的执行相同功能的多个操作在不同的数据上（把数据分成几块，每个操作各执行一块）。DBMS加入了一个exchange操作来把这些操作的结果合并起来 Intra-Operator Horizontal.png Inter-Operator(Vertical)：重叠操作为了管道化数据以避免从一个阶段到下一个之间的物化；worker在同一时间从查询计划不同的段执行多个操作；仍需要exchange操作整合中间结果 Intra-Operator并行.png