导读
在决策支持、OLAP和多媒体检索等计算密集型应用领域中，数据库系统往往没有利用好现代CPU，只能实现较低的IPC（instructions-per-cycle）。这篇论文基于TPCH基准，研究了问题的原因，从中可以理解向量化执行的重要意义。
论文的第二部分描述了MonetDB（列式内存数据库）新的查询引擎X100架构所遵循的原则。从表面上看，X100类似于经典的Volcano执行引擎，但存在根本性的差异，X100实现了向量化执行，能够更好的提升CPU利用率。论文评估了MonetDB/X100在100GB规模的TPC-H上的性能，结果显示性能比Volcano执行引擎提高了1到2个数量级。
备注：这里简单介绍下IPC和Volcano执行引擎。
（1）IPC（instructions-per-cycle）
- 英文全称“Instruction Per Clock”，表示CPU一个时钟周期内所执行的指令的多少
- 英特尔提出了CPU性能判断标准公式是CPU性能=IPC×频率(MHz时钟频率)，这个公式被业界广泛认可
- 通俗点理解，IPC就是一次可以搬几块砖，MHz时钟频率就是每分钟搬几次
（2）Volcano执行引擎
Volcano模型是数据库界已经很成熟的解释计算模型，该计算模型将关系代数中每一种操作抽象为一个 Operator，将整个 SQL 构建成一个 Operator 树，从根节点到叶子结点自上而下地递归调用 next() 函数。
例如 SQL：
SELECT Id, Name, Age, (Age - 30) * 50 AS Bonus FROM People WHERE Age > 30
其中——
User：客户端；
Project：垂直分割（投影），选择字段；
Select（或 Filter）：水平分割（选择)，用于过滤行，也称为谓词；
Scan：扫描数据。
这里包含了 3 个 Operator，首先 User 调用最上方的 Operator（Project）希望得到 next tuple，Project 调用子节点（Select），而 Select 又调用子节点（Scan），Scan 获得表中的 tuple 返回给 Select，Select 会检查是否满足过滤条件，如果满足则返回给 Project，如果不满足则请求 Scan 获取 next tuple。Project 会对每一个 tuple 选择需要的字段或者计算新字段并返回新的 tuple 给 User。当 Scan 发现没有数据可以获取时，则返回一个结束标记告诉上游已结束。
可以看出火山模型的优点在于：简单，每个 Operator 可以单独抽象实现、不需要关心其他 Operator 的逻辑。
那么缺点呢？也够明显吧？每次都是计算一个 tuple（Tuple-at-a-time），这样会造成多次调用 next ，也就是造成大量的虚函数调用，这样会造成 CPU 的利用率不高。
但是为什么之前的数据库设计者没有去优化这方面呢？是他们没想到吗？怎么可能？这个时候我们可能要考虑到 30 年前的硬件水平了，当时的 IO 速度是远远小于 CPU 的计算速度的，那么 SQL 查询引擎的优化则会被 IO 开销所遮蔽（毕竟花费很多精力只带来 1% 场景下的速度提升意义并不大）。
可是随着近些年来存储越来越快，这个时候我们再思考如何让计算更快可能就有点意思了。
Volcano执行引擎内容引自小鹏：SQL 优化之火山模型
CPU工作机制
pipeline原理简介
上图描述了近10年来（截止到2005）CPU性能的提升情况，也可以看出MHz时钟频率也得到了快速的提升，复合摩尔定律。MHz时钟频率提升有两个原因：
- CPU制作工艺的进步
- CPU的pipeline能力
流水线(pipeline)是将一个cpu指令分为5个stage（阶段）执行，分别为取指令、译码、执行、访存、写回，具体如下
- IF:Instruction Fetch,取指令,用到部件:指令存储器，Adder（ 全加器，full-adder，是用门电路实现两个二进制数相加并求出和的组合线路，称为一位全加器。一位全加器可以处理低位进位，并输出本位加法进位。多个一位全加器进行级联可以得到多位全加器。常用二进制四位全加器74LS283）
- ID:Instruction Decode,译码（应该是取数同时译码的过程），用到部件：指令译码器寄存器堆读口（这里面的寄存器堆的读口和写口可以看作两个不同的部件），这块有大量寄存器，WB也是从写口将数据写到这块的寄存器中
- EX:Exec,执行，计算内存单元地址。用到部件：ALU，扩展器
- MEM：访存，从数据存储器中读。用到部件：数据存储器
- WB:Write Back,写回，将数据写到寄存器中。用到部件：寄存器堆写口
上述每个stage由cpu的一个组件负责，在一个时间点
- 对于一个指令，最多仅可运行一个stage
- 对于多个指令，最多可运行5个stage，每个stage对应于一个独立的指令
流水线(Pipeline)技术是指程序在执行时候多条指令重叠进行操作的一种准并行处理实现技术。通俗的讲将一个时序过程，分解成若干个子过程，每个过程都能有效的与其他子过程同时执行。这种思想最初是在RISC的架构中出现的，旨在提高处理器处理效率，争取在一个时钟周期中完成一条指令。
示例如下，假设洗衣分为三个步骤，分别在三个设备上进行
- wash，30分钟
- dry，40分钟
- fold，20分钟
- 共1个洗衣机、1个烘干机、1为叠衣服工人
描述如下：
http://staff.ustc.edu.cn/~llxx/cod/courseware/2022ppt-5.pdf
pipeline模式带来了2个问题：
- 如果指令1需要依赖指令2的结果，那么指令2、指令1只能串行执行，不能使用pipeline模式
- 对于 IF-a-THEN-b-ELASE-c，cpu的分支预测功能会评估a是true或false。如果预测a为false，则将c放置于pipeline中，即当a执行完成后，执行c。但在多个stages后，发现分支预测的不对，即a不是fasle，而是true，然后需要flush掉这个pipeline（丢弃是其中的所有指令），从b重新开始。很明显，这个pipeline越长，被清除的指令就越多，性能损失也就越高。转换为数据库系统，对a进行分支预测是需要依赖tuple数据的，很难预测到a的结果，预测错误会显著降低查询执行性能
此外，super-scalar cpu提供了并行执行多个指令的可能性，如果这些指令是独立的。也就是说，CPU有多个pipeline。每个时钟周期，都可以将一条新指令推到任意管道中，只要它们再次独立于所有已经执行的指令。一个super-scalar cpu可以到达>1的IPC（每个时钟周期内执行的指令数）。图1显示，这使得实际的CPU性能比CPU频率增长得更快。
下图描述了一个支持2个IPC的super-scalar cpu，即在每个时钟周期内，可以同时有两个相同类型的stage工作。
现代cpu以不同的方式进行平衡。英特尔安腾2处理器是一个VLIW（非常大的指令Word）处理器，有许多并行管道（每个周期最多可以执行6条指令），只有少量的stages，因此时钟速度相对较低，为1.5 GHz。相比之下，奔腾4有一个很长的31级管道，允许3.6 GHz的时钟速度，但每个周期只能执行3条指令。无论怎样，要达到理论上的最大吞吐量，安腾2在任何时候需要7x6 = 42个独立指令，而奔腾4需要31x3 = 93。 num(pipeline) * num(stage) 只是理论上的最大并行量，实践中，很多程序是无法满足这个理论最大值条件的，因此许多程序使用安腾2要不使用奔腾4时CPU资源利用好得多，这就解释了为什么在基准测试中，两个cpu的性能是相似的，尽管时钟速度有很大的差异。
大多数编程语言不需要程序员在其程序中显式地指定哪些指令（或表达式）是独立的，即可并行执行的。因此，编译器对程序代码的优化对于实现良好的CPU利用率至关重要。最重要的技术是loop pipelining。其中，对数组a的所有n个独立元素的由多个依赖操作F（），G（）组成的操作如下：
如果一个操作符中包含了对一个数组A的每个独立元素进行多个独立的计算F()、G()，即
F(A[0]),G(A[0]), F(A[1]),G(A[1]),.. F(A[n]),G(A[n])，F() - >G()
这个计算将被转换为：
operator：F(A[0]),F(A[1]),F(A[2]), G(A[0]),G(A[1]),G(A[2]), F(A[3]),..
这里假设F（）的执行需要2个cpu周期，当执行G（A[0]）时，F（A[0]）已经刚刚完成计算，且可以被G（A[0]）使用。
基于这个思想，很多数据库即使没有使用SIMD，可以基于列存，在执行时从逻辑上模拟这种pipeline过程，实现向量化。
select算子pipeline示例说明
回到数据库中，select算子是分支预测敏感的，分支预测是依赖于tuple数据的，如果选择率不是非常的高或非常的低，是不可能准确预测的，并且还会降低查询性能。
例如
SELECT COUNT(*) FROM lineitem WHERE quantity < n
基于branch的C实现
for (unsigned int i = 0; i < num_tuples; i++)
if (lineitem[i].quantity < n)
count++;
重写为基于predicated的C代码
for (unsigned int i = 0; i < num_tuples; i++)
if (lineitem[i].quantity < n)
count++;- 不会再使用branch进行判定了，for循环体本身除外
- 在每次迭代中，都需要支付一个+操作符的代价
- 执行时间与选择率无关
如下为software predication的用例
SELECT quantity FROM lineitem WHERE quantity < n
一些CPU从支持hardware predication，例如Intel Itanium2，同时执行if和else分支，根据if条件再丢弃掉其中的一个。
从上图中可以看出：
- 两种CPU中，predicated version执行时间是恒定的，与选择率无关
- Itanium2 CPU中，predicated version和branch version的执行时间均与选择率无关
- Itanium2 CPU中，branch version性能优于predicated version，因为Itanium2支持hardware predication
http://dbis.cs.tu-dortmund.de/cms/de/lehre/ss14/dpmh/slides/instruction-execution.pdf
cpu cache
这里描述下cpu cache对提示CPU吞吐量的重要性。
CPU执行的指令中，大约30%的指令是用于CPU和物理内存芯片之间执行memory load/store，物理内存芯片和cpu芯片在同一个主板上，相距几英寸，至少会产生50ns的物理延迟。对于3.6GHz的CPU来说，以最乐观的50ns延迟计算，一次load或store会导致180个cpu wait cycle。因此，只有当一个程序访问的绝大多数内存能够在CPU缓存中找到时，一个现代CPU才有机会以其最大吞吐量运行。最近的数据库研究表明，“cache miss”会严重损害DBMS性能[3]。如果使用了cache-conscious数据结构，如 cache-aligned B-trees，或列存存储，如PAX、DSM（MonetDB）等，能够显著提升性能。此外，查询处理算法将其随机内存访问模式限制在适合CPU缓存的区域的查询处理算法，例如radix-partitioned hash join[18,11]，极大地提高了性能。
总而言之，cpu已经成为高度复杂的设备，其中同一个处理器的指令吞吐量可能存在数量级的差异，根据如下情况：
- memory load/store的cache命中率
- branch的数量，已经是否可以进行分支预测
- 编译器和CPU可以检测到的独立指令的平均数量
有研究结果表明，在商业DBMS系统中，查询执行的IPC仅为0.7 [6]，因此平均每个周期执行不到1条指令。相比之下，在科学计算（如矩阵乘法）或多媒体处理领域，平均IPC可以达到2个。
作者认为，数据库系统，尤其是在大规模的分析任务中（需要检查数百万个元组并计算表达式），cpu利用率不应该表现的这么差。这些工作任务中包含了大量的独立子任务或操作，应该能够充分利用CPU提供的所有管道，因此，我们的任务是调整数据库体系结构，以便尽可能地将这种结构暴露给编译器和CPU，使其能够尽可能的检测到DBMS中的独立指令，从而显著提高查询处理吞吐量。
Microbenchmark: TPC-H Query 1
论文的目标是提升查询处理过程中CPU的利用率，作者首先关注了表达式计算，先不考虑join等复杂的关系操作，这样可以简化分析。
论文选择了TPCH query1进行测试，query 1查询是CPU绑定的，在多个DBMS上执行的查询结果见图3。此外，这个查询非常的简单，没有复杂的join，不需要过多的优化。因此，对所有的DMBS来说，测试环境相对公平，主要测试表达式计算的效率。
SELECT l_returnflag, l_linestatus,
sum(l_quantity) AS sum_qty,
sum(l_extendedprice) AS sum_base_price,
sum(l_extendedprice * (1 - l_discount)) AS sum_disc_price,
sum(l_extendedprice * (1 - l_discount) * (1 + l_tax)) AS sum_charge,
avg(l_quantity) AS avg_qty,
avg(l_extendedprice) AS avg_price,
avg(l_discount) AS avg_disc,
count(*) AS count_order
FROM lineitem
WHERE l_shipdate <= date '1998-09-02'
GROUP BY l_returnflag, l_linestatus;
- TPC-H benchmark ware house数据量为1GB，可以通过Scaling Factor (SF)进行扩展。
- Query1 对lineitem表进行scan，lineitem表含有6M tuples
- Query1 对lineitem表，经select过滤后，仍会选择5.9M tuples
- 计算固定精度的decimal表达式
- 8个agg计算（4个sum、3个avg、1个count）
- 2个column和常量的减
- 1个column和常量的加法
- 3个column和column的乘法，
- GroupBy columns是2个single-char columns，仅产生4个组，因此，可以用一个小的hash表进行分组，因为lineitem tuples数量不大，1GB ware house为6M tuples，因此，都可以存在内存中，不需要额外的IO，甚至可以在CPU cache中完成hash表的访问，这样就不会出现cpu cache miss
Query 1 on RDBMS（tuple-a-time）
rdbms最初就采用了Volcano执行引擎，物理执行计划为operator tree形式，tuples从下向上以pipleline模式处理。然而，关系代数的参数具有很高的自由度。例如，对于一个简单的ScanSelect(R,b,P)，只有在查询执行时，才能完全了解输入关系R的格式（列数、它们的类型和tuple的偏移量），b表示bool类型的select过滤表达式，P表示投影表达式（用于定义output relation）。为了能够处理各种类型的R、b、P，DBMS必须实现一个解释器，能够处理任意复杂度的表达式。
采用这种解释执行方式，存在一个弊端，特别是解释的粒度是一个tuple，对于一个查询执行的cost来说，真正的实际工作cost可能占的比重很小，例如Q1查询中+、-、*、sum、avg计算实际的cost占比可能很低。以MySQL 4.1 TPCH query1（1s）为例进行说明，查询结果的gprof trace见表2。表2表示，Q1查询中+、-、*、sum、avg计算实际的cost占整个查询的cost比重不到10%，整个query 的IPC为0.7，低。
- cum字段表示func执行的累计时间
- excl字段表示func执行自身代码（去重掉func调用其他func的代码）耗时占cum的比例
- calls字段表示func在整个查询中的调用次数
- ins字段表示每次调用时发生的平均指令数
- ipc字段表示每次调用时发生的平均IPC
观察表2 ，
- 黑色加粗条目表示query1中5个（+、-、*、sum、avg）实际计算函数的执行时间等信息，+、-、*、sum、avg等5个实质计算函数耗时不到总耗时的10%
- query1总耗时中，28%用于创建和lookup hash表，hash表用于agg
- query1总耗时中，剩余62%用于rec_get_nth_field等辅助函数，rec_get_nth_field用于从tuple中读取、输出指定column value
再观察表2，表2的结果是在MIPS R12000 CPU环境中获取的，Item_func_puls::val函数在每次＋操作中需要消耗38个指令。
在MIPS R12000 CPU上，在每个cycle中，可以执行3个整型或浮点型addition指令，1个load或store指令，平均每个指令要延迟5个cycle。一个简单的算术运算符+(double src1, double src2)：double，在RISC的指令如下：
LOAD src1,reg1
LOAD src2,reg2
ADD reg1,reg2,reg3
STOR dst,reg3
本代码含4个指令，其中3个是load/stor指令，占比较大，因此MIPS处理器的一个加法运算+(double src1, double src2)大概需要是3个cycles（3个LOAD/STORE）。
回到表2，Item_func_puls::val每执行一次平均38个指令，ipc为0.8，那么平均一次加操作，需要cycles = 38 / 0.8 ≈ 49。而+(double src1, double src2)：double平均需要3个cycles，差异如此大！
对Item_func_puls::val这种高成本的一种解释是没有使用loop pipelining。因为MySQL每次调用的Item_func_puls::val函数时，在一个cycle中，只是串行的计算一个加法，而不是采用了pipeline模式，一个cycle中，进行一个数组的loop加法，这样编译器就不能进行loop pipelining优化。因此，加法操作由4个相互依赖的指令组成(load, load, add, store)，每个指令需要等上一个指令完成才可以进行。平均一个指令延迟5个cycle，因此，一次加法就延迟了20个cycle。其余的cycle（49-20 = 29）用在了函数跳转、入栈、出栈上。
作者还在一个著名的商业RDBMS上测试了query1（参见表1的第一行），测试结果与MySQL类似。
Query 1 on MonetDB/MIL（column-a-time）
MonetDB由CWI开发，最著名的是使用了垂直分片，即列存，每一列都存储在一个包含[oid，value]的 Binary Association Table(BAT) 中。BAT是一个含有2列的表，即[oid, value]。MonetDB的代数查询语言是一个被称为MIL [5]的列代数。
与关系代数不同，MIL这种列代数是以数据为中心的，其代数运算符的有固定数量的固定格式的输入参数（二元组或常数)和输出结果。.复杂的表达式必须使用MIL中的多个语句来执行。例如
extprice * (1 - tax)
=>
tmp1 := [-](1,tax);
tmp2 := [*](extprice,tmp1)
[*]()和[-]()称为 multiplex operator,能够将-、*的实现函数映射到对应的 BAT（column）上。
MIL以列的方式执行计算，其输入和输出都是物化的，且是BAT格式的作者使用了MonetDB/MIL的SQL前端，将query 1的SQL语句转换为MIL语言，并执行，结果见表3。
表3显示了
- query1在MonetDB/MIL中共20个MIL，MILs的总执行时间占query1总执行时间超过99%，MySQL只有10%
- 在TPC-H Query 1上，MonetDB/MIL明显比同一台机器上的MySQL和商业DBMS快，也可以与发布的TPC-H分数竞争（见表1）
- 仔细观察表3可以发现，几乎所有的MIL操作符都是memory-bound，而不是cpu-bound！即瓶颈是内存带宽，而不是CPU
- 对比第2列和第4列，可以看出单个MIL操作的的带宽（BW），MB/s，带宽统计了输入BAT和产生的输出BAT
- 当查询数据量较小时候，带宽流程为DRAM<--->CPU cache <--->CPU，SF=0.001的TPC-H数据集上运行相同的查询计划来建立的，这样所有使用lineitem的列以及所有中间结果可以存入CPU缓存中，消除了memory traffic，即DRAM的cost，此时带宽大概在1.5GB/s
- 当查询数据量大时候，带宽流程为CPU cache <--->CPU，SF=1，执行受到memory bandwidth限制，测试机memory bandwidth最大值为500M/s
- 在SF=1时，对于multiplexed multiplication [*]()，即2个column的乘法计算带宽为500MB/s，这说明每秒可以传入、传出20M个tuples，因为一个传入tuple数据量16bytes，传出tuple数据量8bytes，20M个tuples = 500MB/（16+8）。在1533MHz CPU上，每个乘运算需要占用75 cycles，即75 = 1533 / 20，这方面不如MySQL，49 cycles
因此，MIL中的column-at-a-time策略，既有优势，也有劣势
- 优势：MonetDB不会出现MySQL问题，即将90%的查询执行时间花在tuple-at-a-time解释“开销”上。由于基于bat格式，进行了array 操作，这使得在编译时编译器就能知道布局的数组，这样就可以使用了cpu的 loop pipeling ，提升cpu利用率。 SF = 0.001 的结果证明了loop pipeling优化效果
- 劣势：对计算所需的column需要全量物化，包括中间结果，然而最终查询结果中可能不需要全量物化，这造成了内存带宽的过多消耗。因为，MIL中每个算子的物化输出只是作为其他函数的输入，对于Q1中的最终查询结果，agg函数，最终的输出仅有4行，大小可以忽略，MIL实现的数据可能远远超过严格必要的数据，导致其高带宽消耗
Query 1: Baseline Performance
为了了解现代CPU在类似Query 1这样的查询中可以做什么优化，作者在MonetDB中实现了一个Q1的UDF，用以获取Q1的理想的性能，作为baseline，UDF如下图
- UDF只传递给查询涉及的列
- 在MonetDB中，这些列以数组的形式存储在BAT[void，T]中，其中oid的值是从0开始递增的
- 在MonetDB中，void(virtual-oid)不进行实际存储，BAT就会以一个数组的形式出现
- 在计算中，将输入的数组用__restrict__ 修饰，告知编译器，这些指针不会指向同一数据，这样编译器就可以在编译过程中，利用cpu的loop pipelining
表1显示，这种UDF实现（标记为“hand-coded”）将查询时间降低到惊人的0.22秒，远低于MySQL26,6秒，低于MonetDB/MIL的3.7秒。从图中可以看出，论文提出的新的MonetDB/X100查询处理器，也能起到非常好的效果。
X100: A Vectorized Query Processor
X100的目标如下：
- 以高CPU效率执行查询
- 可扩展到其他应用程序领域，如数据挖掘和多媒体检索，并在可扩展性代码上实现同样的高效率
- 可按最低存储层次结构（磁盘）的大小进行扩展
为了实现这些目标，X100在设计中需要能够应对计算机体系结构中的瓶颈
- Disk IO
- 采用列存，在顺序访问数据时更高效
- 为了减少带宽消耗，使用垂直分片的数据布局
- 在某些情况下，对列存数据进行轻量级压缩
- RAM
- 在函数中显示执行memory-to-cache和cache-to-memory，执行代码可以包含平台相关的汇编代码，这样效率高，例如SSE prefetching和data movement汇编指令
- 在RAM中使用了磁盘相同的列存布局以及轻量级压缩算法，减少空间和带宽的消耗
- Cache
- 在Volcano风格的pipeline执行引擎中使用vectorized处理过程，即基于Volcano-pipeline风格的向量化引擎
- “vector”是一个小的基本处理单元，例如一个vector是一个包含1000个values的chunk，一个vector能够存储在cpu cache中，减少了cpu cache与ram的交互。这样便于“vector”直接进入到cpu cache中，在cache中直接进行压缩和解压缩，提升效率
- X100的查询执行算子尽可能的以数据为中心，即data-center类型的，尽量在cpu的cache-chunk内执行random数据访问，总之就是减少与ram的交互，这样可以降低cycle等待
- CPU
- “vector”是向编译器公开的，处理一个元组独立于前一个元组和下一个元组
- vectorized primitives（一组指令，要么都执行、要么都不执行，执行过程不能被打断）要符合编译器执行loop-pipeling的优化条件，使得编译器可以生成高效的loop-pipeling机器码，例如对于if else，使编译器能够利用loop-pipelining，步提高CPU吞吐量（主要是通过减少指令组合中的load/store指令的数量实现
为了保持本文中的重点（CPU利用率），作者只简要地描述了X100在磁盘IO方面的设计，另外，这也是因为ColumnBM缓冲区管理器仍在开发中。在论文的所有实验中，都使用了MonetDB作为其存储管理器（如图5所示），在IO和内存中，数据都是BAT格式的。
查询语言
X100使用了一个标准的关系代数作为查询语言。不在使用column-at-a-time风格的MIL语言了。这样关系操作符就可以同时处理多个列（多个向量），允许在cpu cache中，一个表达式产生的向量作为下一个算子的输入，即中间结果在cpu cache中。
（1）Example
图6展示了TPC-H Query 1的一个简版示例，使用以下X100关系代数语法：
Aggr(
Project(
Select(Table(lineitem),<(shipdate, date('1998-09-03'))),
[ discountprice = *( -( flt('1.0'), discount),
extendedprice) ]),
[ returnflag ],
[ sum_disc_price = sum(discountprice) ])
- 查询执行使用了Volcano风格的pipeline，一个vector的最小单元是1000 values
- Scan算子从Monet BATs中读取数据，vector-at-a-time，仅scan查询中使用到的column
- Select算子会创建一个selection-vector，对于scan输入的vector，执行谓词计算，将满足条件的values写入到selection-vector，注意，整个过程不会更改scan vector，而是从中选择满足条件的values，填充至新建的selection-vector
- project算子
- 计算表达式：discountprice = *( -( flt('1.0'), discount），extendedprice)
- 创建新的vector，写入discountprice
- 注意：在Select算子中并未改变“discount” column和“extendedprice”column的值
- 注意：在Select算子中，利用map-primitive（源语），对于输入的scan vector，创建同等大小且下标位置相同的Select vector，但会在select的vector中标记哪些数据是被选中的，即有效数据，后续的计算，会根据Select vector的有效数据标记，知道Select vector中哪些数据可用，因此这个Select vector会一直向上传递。
- 在project算子中，Select vector将作为筛选，从“discount” 和 “extendedprice”中筛选出满足条件的values，分别创建新的vector
- 本例中会将Select vector作为输入，传递给agg算子，用于筛选有效的数据
- agg算子，使用Select vector作为输入，基于标记为有效的values计算其在agg算子的hash 表的位置，然后使用这些数据更新agg算子的结算结果
注：map_mul_flt_col_flt_col是一种基本的计算源语，实现了两组float类型的vector的乘法计算，其他源语类似，不再赘述。
（2）X100 Algebra
图7列出了X100当前支持的关系运算符。在X100关系代数中，Table是一个物化的relation，DataFlow是Volcano模型pipeline中的vector流，即vector-at-a-time。
- Order、TopN、Select算子返回的dataflow的shape同其input dataflow
- 其他算子会生成新的shape的dataflow
- Project算子仅用于表达式计算，并不会去重
- 去重仅发生在Aggr算子包含group-by columns的情况下
Vectorized Primitives
X100使用column-wise vector layout的主要原因是，向量化执行的计算原语与解释执行相比，灵活度较低，函数每次执行时，入参都是vector，即类型是确定的（如int、double等），数组的长度是确定的，不需要关心table的布局（如record偏移信息）。这样在编译X100时，C编译器能够观察到向量化原语，即函数中使用了__restrict__修饰符，例如double*__restrict__ col1, double*__restrict__ col2，这样编译器就可以使用loop-pipelining进行编译优化。
例如，浮点数向量加法实现函数如下：
map_plus_double_col_double_col(
int n,
double*__restrict__ res,
double*__restrict__ col1,
double*__restrict__ col2,
int*__restrict__ sel)
{
if (sel) {
for(int j=0;j<n; j++) {
int i = sel[j];
res[i] = col1[i] + col2[i];
}
} else {
for(int i=0;i<n; i++)
res[i] = col1[i] + col2[i];
}
}- 参数sel可以为null，也可以指向一个n个元素的array，这个array是select算子中符合过滤条件的元素的index
- X100所有的向量化原语都允许传递这种的select vectors
- 其基本原理是，在select算子后，保持子操作符传递的vector的完整通常比将满足select条件的数据复制到新的（连续的）vector中更快
X100中支持数百个map_plus_double_col_double_col类似的函数，是通过模板生成的，模板如下：
any::1 +(any::1 x,any::1 y) plus = x + y
此外，X100还支持组合原语，例如：
/(square(-(double*, double*)), double*)
- 作者发现组合原语执行速度是单独2个原语计算的2倍
- 原因是进行了指令组合
- 向量化执行通常是load/store成对出现的，因为对于一个简单的2元计算，每一个向量化指令都需要load 2个参数，store一个计算结果，相当于4个指令，1个用于计算，2个用于load，1个用于store
- 现代CPU在一个cycle中仅能够执行1或2个 load/stroe操作
- 在组合源语中，第一个计算的结果写入cpu寄存器，用于第二个计算，这样2个计算就只有一个load和一个store，降低了成本
Data Storage
MonetDB/X100以垂直分片的形式存储所有的表，存储结构同ColumnBM 缓冲区管理器或MonetDB BAT[void,T]存储格式。MonetDB中，每个BAT（列）存放在一个独立的文件中，在ColumnBM中，将这个BAT文件分为多个chunks，每个chunk > 1MB。
这种向量化存储的劣势在于update操作代价高，update 一个tuple或delete 一个tuple必须有n次IO，n是table中的columns数量。MonetDB/X100中的每个向量垂直分片都是不可更改的。更新操作实际上将更新信息写到一个delta结构体，周期性的和原向量垂直分片数据进行compaction。
图8中展示了删除和更新示例，很多列存数据库都采用了类似的方法
- delete一个tuple，通过将tuple的ID写入del列表中完成
- insert 一个 tuple，将tuple中的各column value追加写入到内存中各delta columns内
- ColumnBM存储引擎将各个delta columns存储在一个PAX格式的chunk中的垂直分片中
- update就是delete+insert
Vector Size 影响
论文给出了Vector Size对性能的影响。
- vector size是需要根据CPU cache size进行调整的
- vector size过小，无法充分利用loop pipeling，性能不理想
- vector size过大，无法fit cpu cache，性能也不理想
小结
这篇文章讲了在非SIMD的情况下，如何利用vector-at-a-time提升CPU的利用率，即，在物理计划的执行算子中，在计算源语中，使用了__restrict__ 修饰符说明vector参数，告知编译器可以使用loop-pipelining进行编译优化，进而在运行时提升CPU利用率。当然，为了达到这一步还要有若干的前期工作。
参考
梁辰：MonetDB/X100: Hyper-Pipelining Query Execution104 赞同 · 24 评论文章编辑