1.2.2 向量化查询执行引擎
现代计算机存储系统，为了解决存储器的速度、容量和价格之间的矛盾，最终被设计成一个多级分层架构体系，如图1-8所示。
图1-8 计算机多级分层存储体系
从图1-8中可以看到，在存储体系中自上而下来看，存储系统的速度越来越低，容量越来越大，单位价格越来越低。分层存储体系的顶端是寄存器，它的速度最快、价格最高、容量最小。最底端是磁盘，它的速度最慢、价格最低、容量最大。从寄存器中访问数据的速度，是从内存访问数据的速度的400倍，也是从磁盘中访问数据速度的4000万倍（10ms=10000μs=10000000ns）。由此可见，距离CPU越近，速度越快。
在现代分布式并行计算框架中，通常将1个大任务分割成多个可以同时执行的小任务。在大数据分析问题中，通常数量行数特别大，数据的解压缩和计算将耗费非常多的CPU资源，为了提高CPU的效率，行业中通常将数据转换成向量（Vector）的计算，例如比较流行的VectorWise方法。VectorWise的基本思想是，将压缩的列数据整理成现代CPU容易处理的数据向量模式，利用现代CPU的SIMD（Single Instruction Multiple Data，单指令多数据流）技术，每次处理一批向量数据，极大地提高了处理效率。
ClickHouse为了最大限度地提高硬件（尤其是CPU）的性能，同样实现了向量化查询执行（Vectorized Query Execution）机制（也叫向量化计算（Vectorization）、向量化操作（Vectorized Operation）、向量编程（Vector Programming）等），其核心思想就是将多次for循环计算转化为一次并行计算。这也是ClickHouse相对于传统OLAP引擎的技术领先点之一。
不过，向量化执行需要CPU硬件本身的指令集（Instruction Set Architecture，ISA）的支持，而支持向量执行的CPU指令就是SIMD。单指令流（Single Instruction）是指同时只能执行一种操作，多数据流（Multiple Data）则是指在一组同构的数据（通常称为数据向量）上进行操作。
SIMD是Flynn分类法对计算机的四大分类之一，它本质上采用一个控制器来控制多个处理器，同时对一组数据中的每一个数据分别执行相同的操作，从而实现并行计算。SIMD并行计算过程如图1-9所示。其中，PU（Processing Unit）是指令单元。
图1-9 SIMD并行计算过程
向量化执行和编译执行是目前主流的两种数据库执行引擎优化手段。为了高效地使用CPU，数据不仅按列存储，还按向量（列的一部分）进行分组处理（例如，Parquet文件中的行组。
向量化执行模型有以下几个好处：
❑大大减少火山模型中的虚函数调用数量。
❑以块为单位处理数据，提供了缓存命中率。
❑多行并发处理，契合了CPU乱序执行与并发执行的特性。
❑同时处理多行数据，使SIMD有了用武之地。尽管目前SIMD对大多数数据库查询起到的作用比较有限，因为本质上数据库查询都属于数据访问密集型应用，而不是SIMD最擅长的计算密集型应用。
小贴士：SIMD简介
1.SIMD介绍
前面提到，SIMD采用一个控制器来控制多个处理器，同时对一组数据（又称“数据向量”）中的每一个数据分别执行相同的操作，从而实现空间上的并行性。SIMD架构在多条数据上同时执行同一条命令，包括查询、计算和存储信息等命令。SIMD通常用于处理器执行大量计算的问题，这些计算需要处理器并行执行相同命令。
在微处理器中，SIMD技术则是一个控制器控制多个平行的处理单元，例如Intel的MMX或SSE，以及AMD的3D Now！指令集。
SIMD是基于CPU寄存器层面的操作。从寄存器中访问数据的速度是从内存访问数据的400倍，是从磁盘访问数据的4000万倍。ClickHouse针对频繁调用的基础函数使用SIMD执行代替循环操作，大大提升了性能。
SIMD在现代计算机领域的应用非常广泛，最典型的是在GPU的像素处理流水线中，SIMD和MIMD（Multiple Instruction Multiple Data，多条指令处理多条数据流）是GPU微架构的基础。
CPU是如何实现SIMD的呢？答案是扩展指令集。Intel的第一版SIMD扩展指令集称为MMX，于1997年发布。其改进版本有SSE、AVX，以及AMD的3DNow！等。
ClickHouse的向量化执行机制主要依赖于SSE指令集，ClickHouse当前是基于SSE 4.2的指令集实现的。SSE（Streaming SIMD Extension，流式SIMD扩展）是由Intel公司在1999年推出Pentium Ⅲ处理器时同时推出的新指令集。如同其名称所表示的，SSE是一种SIMD指令集，有8个128位寄存器，XMM0～XMM7，可以用来存放4个32位的单精确度浮点数。可以看出，SSE是一套专门为SIMD架构设计的指令集。通过SSE，用户可以同时在多个数据片段上执行运算，实现数据并行（如矢量处理、向量化执行）。
SSE 2是SSE指令的升级版，其寄存器、指令格式都与SSE一致，不同之处在于SSE 2能够处理双精度浮点数等更多数据类型。SSE 3增加了13条新的指令。
SSE有3个数据类型，__m128、__m128d和__m128i，分别代表Float、Double(d)和Int(i)，如图1-10所示。
AVX也有3个数据类型，__m256、__m256d和__m256i，分别代表Float、Double(d)和Int(i)。
这里以Float类型来说明SSE指令集的具体使用方法。
一个xmm#指令操作数可以用来存放4个32位（1位符号、8位指数、23位尾数）的Float，data0、data1、data2、data3，如图1-11所示。
以计算两个向量加法为例，假设每个向量有4个整数元素，那么传统的CPU需要读取8次寄存器，进行4次加法操作才可以完成。而对于SSE来说，每个128位的寄存器可以存放4个32位的单精度浮点数，那么意味着只需要读取两次寄存器，执行一条SIMD指令即可（对一组数据执行相同的操作），如图1-12所示。
图1-10 SSE指令
图1-11 xmm#指令操作数
图1-12 xmm指令加法计算
算术指令需要2个操作数（寄存器或内存）来执行算术计算并将结果写入第一个寄存器。源操作数可以是xmm寄存器或内存，但目的操作数必须是xmm寄存器。汇编指令如图1-13所示。
图1-13 xmm操作汇编指令
其中，addps指令中的ps表示并行标量（parallel scalar）。
2.在C++中使用SIMD的3种方法
考虑到ClickHouse是基于C++写的，我们有必要了解一下如何在C++中使用SIMD，主要有如下3种方法。
1）编译器优化。即使用C/C++编写程序之后，程序中带有SIMD优化选项编译，在CPU支持的情况下，编译器可按照自己的规则去优化。
2）使用intrinsic指令。参考Intel手册，针对SIMD指令，可以在编程时直接使用其内置的某些库函数，编译时在CPU和编译器的支持下会生成对应的SIMD指令。比如，double_mm_cvtsd_f64(__m128d a)在函数编译时就会翻译成指令movsd。
3）嵌入式汇编。内联汇编直接在程序中嵌入对应的SIMD指令。
为了更加直观地进行说明，我们举一个实现一个向量加法运算的实际代码的例子。
a）使用Intrinsic函数的代码：
b）对应汇编指令代码：
小贴士：数据库查询执行模型简介
数据库查询执行模型主要有3种：火山模型（Volcano Model）、物化模型（Materializa-tion Model）、向量化模型（Vectoried Model）。这里分别简单介绍一下。
1.火山模型
数据库查询执行最著名的是火山模型，也是在各种数据库系统中应用最广泛的模型。大多数关系型数据库都是使用火山模型的，如SQLite、MongoDB、Impala、DB2、SQLServer、Greenplum、PostgreSQL、Oracle、MySQL等。
火山模型将关系代数中每一种操作抽象为一个算子（Operator），将整个SQL构建成一个算子树，查询树自顶向下调用next()接口，数据则自底向上被拉取处理。SQL查询在数据库中经过解析，会生成一棵查询树，查询树的每个节点会提供一个next()接口，next()接口实现分为三步：
1）调用子节点的next()接口获取一行数据（tuple）。
2）对tuple进行特定的处理（如filter或project等）。
3）返回处理后的tuple。
火山模型也叫迭代模型（Iterator Model）。
火山模型的优点：处理逻辑清晰，每个节点只要关心自己的处理逻辑即可，耦合性低。
火山模型的缺点也非常明显：数据以行为单位进行处理，不利于CPU缓存发挥作用。查询树调用next()接口的次数太多，并且一次只取一条数据，CPU执行效率低；遇到JOIN、Subquery、ORDER BY等操作时经常会阻塞。
2.物化模型
物化模型的处理方式是：每个节点一次处理所有的输入，处理完之后将所有结果一次性输出。物化模型更适合OLTP负载，这些查询每次只访问小规模的数据，只需要少量的函数调用。
3.向量化模型
向量化模型与火山模型类似，每个节点需要实现一个next()函数，但是每次调用next()函数会返回一批元组，而不是一个元组，所以向量化模型也称为批处理模型（Batch Model）。向量化模型是火山模型和物化模型的折衷。向量化模型比较适合OLAP查询，因为其大大减少了每个节点的调用次数，减少了虚函数的调用。
ClickHouse、Presto、Snowflake、SQLServer、Amazon Redshift等数据库，以及Spark 2.x的SQL引擎均支持向量化模型。
在Hive中也使用向量化模型的方式：以ORC/Parquet列式存储数据；配置set hive.vectorized.execution.enabled=true。
Hive向量化模型支持的数据类型有：TinyInt、SmallInt、Int、BigInt、Boolean、Float、Double、Decimal、Date、TimeStamp、String。
如果使用了其他数据类型，查询将不会使用向量化执行，而是每次只查询一行数据。可以通过explain命令来查看查询是否使用了向量化，如果输出信息中Execution mode的值为vectorized，则使用了向量化查询：
在向量化模型中，每次处理包含多行记录的一批数据，每一批数据中的每一列都会被存储为一个向量（一个原始数据类型的数组），从而极大地减少了执行过程中的方法调用、反序列化和不必要的if-else操作，大大减少了CPU的使用时间，如图1-14所示。
图1-14 向量化模型加载数据的方式
从图1-14中可以看出，数据加载出来之后，每批数据中的每一列都会转成一个向量，在后续的执行过程中，数据是一批批从一个操作符流经另一个操作符的，而不是一行行。
另外，向量化模型有一个限制，就是我们必须把要查询的数据存储为列格式。例如：
❑磁盘列存储格式ORC、Parquet。
❑内存列存储格式Arrow。