摘要

现代cpu的指令允许在多个数据元素上并行执行基本操作。这些指令称为SIMD指令，因为它们将一条指令应用于多个数据元素。SIMD技术最初被内置到商业处理器中，以加速多媒体应用程序的性能。SIMD指令为数据库引擎的设计和实现提供了新的机会。我们研究了数据库上下文中的各种操作，并展示了如何使用SIMD指令加速操作的内部循环。使用SIMD指令有两个直接的性能好处：它允许一定程度的并行，这样多个操作就可以被一次执行。它通常还可以消除条件分支指令，来减少分支预测失败。

本文中我们考虑了最重要的数据库操作，包括顺序scan、aggregation、index索引操作和join。本文提出了通过SIMD指令实现这些操作的技术。研究表明，重新设计传统的查询处理算法可以更好地利用SIMD技术。我们的研究表明，使用并行度为4的SIMD，新算法的CPU时间比传统算法少10%到4倍以上。由于消除了分支错误预测的影响，得到了超线性的加速。

一、简介

在过去的几十年里，微处理器的性能经历了巨大的改进。现代cpu中的多执行管道和推测执行提供了越来越多的阶段间和阶段内并行执行机会。另一个趋势是单指令多数据(SIMD-single instruction multiple data)技术提供的指令内并行执行的可用性的增加。SIMD指令通过在每一个指令中消费更多的数据减少了计算密集的循环。

SIMD指令被设计用来加速应用程序的性能，如运动视频，实时物理和图形。这样的应用程序在大型数字数组上执行重复的操作。数据库引擎也具有将重复操作应用于长序列记录的明显特征。数据库系统的CPU和内存性能已经成为某些数据库应用程序的性能瓶颈[4,11,28]，人们对更充分地利用可用的架构重新产生了兴趣。例如，引用最近有很多关于数据库系统中CPU缓存行为的研究 [3, 6, 11, 18, 21, 22]。

本文认为，SIMD技术为数据库引擎的设计和实现提供了新的机遇。据我们所知，目前的数据库系统很少或没有使用SIMD特性。我们研究了数据库上下文中的各种操作，并展示了如何使用SIMD指令加速操作的内部循环。

我们实现了各种内部循环算法，并在奔腾4机器上评估了它们的性能。奔腾4有一个SIMD指令集，支持使用多达128位寄存器的SIMD操作。其他体系结构也有类似的SIMD指令集，可以支持并行处理多个数据元素，这里介绍的技术也适用于这些体系结构。我们之所以关注奔腾，是因为它的SIMD指令是最强大的主流商品处理器之一，包括128位SIMD寄存器和浮点SIMD操作。此外，这些SIMD指令将支持Intel的64位IA64平台，包括Itanium处理器。

SIMD指令显而易见的收益是并行化。如果我们能一次处理S个元素，我们可能希望接近速度S。使用SIMD指令的一个不太明显的好处是，在很多情况下，我们可以通过基于SIMD操作的结果实现算法来避免条件分支指令。条件分支指令在现代的流水线体系结构中是有问题的，因为如果它们被错误预测，指令管道必须被刷新，并且需要做各种其他的簿记工作来确保一致的操作。分支错误预测的开销可能非常大。通过避免这种错误预测，我们有时会观察到速度超过S。

我们的实现假设底层数据按列存储为固定长度数值的连续数组。一些系统，如Sybase IQ[2]、Compaq Infocharger[13]和Monet[5]使用这种列式方法。最近，PAX布局方案建议每个磁盘页面以类似[3]的方式按列进行组织。只要每个页面包含足够多的记录，对数组集合(每页一个数组)进行操作的CPU和内存性能应该与单个这样的数组上的性能相当。因此，我们的研究既适用于内存数据库，也适用于基于磁盘的数据库。

本文中我们考虑了最重要的数据库操作，包括顺序scan、aggregation、index operations和join。我们提出了通过SIMD指令实现这些操作的技术。在某些场景下，SIMD的实现是简单的。在其他情况下，SIMD的实现是新颖的。我们验证了这些操作上的性能的显著提升是可实现的，只需为每个操作重写内部循环即可。这种重写可以用C而不是汇编语言完成，使用Intel的icc编译器提供的intrinsic。

本文剩余部分的组织形式如下。我们在第2节中对相关工作进行了调查。在第3节中，我们将演示如何在扫描和聚合等常见数据处理操作中使用SIMD技术。在第4节中，我们将展示如何使用这些SIMD技术来提高数据库系统中常见索引结构的性能。在第5节中，我们学习join。第6节将简要讨论其他SIMD技术。我们在第7节结束。

二、SIMD技术概述

SIMD技术允许一个微指令同时对多个数据项进行操作。这对于处理大量数值数组(多媒体应用程序的典型特征)的应用程序尤其有效。

SIMD技术在不同的架构上有不同的风格，包括在Intel机器上的MMX，SSE和SSE2，SUN UltraSparc机器上的VIS和3DNow，Enhanced 3DNow!和AMD机器上的3DNow!Profes-sional。使用SIMD架构的其他供应商包括惠普、MIPS、DEC (Com- paq)、Cyrix和摩托罗拉。SIMD技术在不同架构下的详细比较，请参见[25]。

一些SIMD技术是有限的。例如，Sun的VIS不支持SIMD寄存器中的浮点值，并提供64位而不是128位的寄存器[27]。我们已经使用Sun的VIS进行了实验，但是发现如果我们需要至少32位的数据值，那么使用64位SIMD寄存器所启用的双向SIMD改进并不显著。

我们使用英特尔SSE技术芯片上可用的打包单精度浮点指令来说明SIMD指令的使用，如图1所示。其他架构也有类似的说明。

对于这个特定的指令，两个操作数都使用128位寄存器。每个源操作数包含4个32位单精度浮点值，目的操作数包含对每个操作数中相应值(X0和Y0, X1和Y1, X2和Y2, X3和Y3)并行执行的操作(OP)的结果。SIMD操作包括各种比较、算术、shuffle、转换和逻辑操作。

 

术语：一个基础的数字元素（integer或是floating point）被称为一个word。我们用S来代表可用的并行度，例如，一个SIMD寄存器中的word数量。在上图1中，S=4。一个内存对齐的S个word的组被称为一个SIMD单元。

2.1 SIMD vs 向量处理器

向量处理器提供了应用在向量之上的high-level操作，例如，数字数组。一个典型的向量可以存放64到512个64-bit的元素。在单个指令中，操作可以在所有的元素上并行执行。需要具有大量简单处理元素的专门体系结构。

和向量寄存器相比，SIMD寄存器可以存储一组小数据量的元素，例如，最多4个32-bit的值可以在奔腾4中使用SIMD指令进行处理。因此商业处理器上的SIMD的并行度更小。从另一方面来说，向量处理器的load-store指令的延迟要比商业处理器上的SIMD高得多。此外，SIMD指令的小尺寸意味着它们还可以利用超标量处理器中的流水线执行，将它们的工作与其他指令重叠。

2.2 向量化编译器的局限性

向量化编译器的目标是自动发现将普通代码转换为利用SIMD技术代码的机会。例如，icc具有向量化功能[15]。然而,[15]描述了各种原因编译器可能无法应用向量化,包括:文体问题(如使用全局指针或适度的使用复杂表达式),硬件问题(如数据对齐),和复杂性问题(如使用函数调用或非赋值语句在一个循环中)。

我们为实验编写的任何代码都可能无法被icc编译器向量化。这些代码包含几个基本准则。例如，大多数的代码在内部循环中包含条件判断。在另外一些场景下，例如aggregation，手工制作的SIMD代码在操作条件掩码时使用了非常微妙的技巧，而编译器很难生成这些掩码。其他SIMD架构的其他编译器(例如Sun的VIS指令集编译器)同样受到限制。

因此，虽然依赖编译器来实现SIMD转换对我们来说是非常便利的，但很明显，最先进的编译器不能这样做。因此，为了充分利用SIMD的优点，数据库程序员必须明确地使用SIMD，就像多媒体程序员一样。

2.3 比较结果格式

在Intel和AMD架构中，一个SIMD比较操作产生一个与封装操作数长度相对应的元素掩码。元素掩码是一个向量，其中每个打包的元素要么全部包含1，要么全部包含0。例如，当OP在上面的图1中是一个比较操作时，结果是一个128位宽的元素掩码，包含4个32位子元素，每个子元素由比较条件为真的所有1 (0xFFFFFFFF)或为假的所有0 (0x00000000)组成。

在其他架构中，例如SUN和MIPS，比较指令产生一个bit向量，其中每一个bit位表示两个操作数中对应元素的比较结果的真/假。Intel和AMD的架构也支持位向量，通过选择每个字的最有效位来将元素掩码转换为位向量。(在本文中，我们将多次使用这条指令;我们称这个操作为SIMD_bit_vector。)

2.4 数据组织

SIMD指令的数据对齐是另一个必须考虑的问题。例如，VIS指令对8字节对齐的数据进行操作。对于在128位寄存器上操作的SSE和SSE2指令，为了最大限度地利用SIMD 指令，数据必须位于16字节的边界上。虽然有move指令允许在使用未对齐数据时将未对齐的数据复制到SIMD寄存器或从SIMD寄存器中复制出来，但这样的操作比对齐访问要慢得多。

为了更好地利用SIMD指令，有必要使源数据连续，以便可以一次加载整个SIMD单元。实现这种效果的一种方法是使用柱状存储，如第1节所述。

2.5 分支误预测

条件分支指令为现代流水线CPU带来了一个重要的问题，因为CPU无法提前预知比较的两个可能结果中哪个会发生。CPU尝试预测分支的输出，同时通过特殊的硬件来保存分支历史和许多分支指令。一次错误的分支预测会带来显著的delay。[4]报告说，一个Pentium II处理器的分支错误预测惩罚是17个周期。对于奔腾4处理器，最小代价是17个周期[1]，平均代价略高；奔腾4的管道有20级深。在我们的实验结果衡量分支错误预测影响的相对重要性，我们假设一个分支错误预测导致20个周期延迟。在我们的图表中，这相当于20/c秒，其中c是处理器的时钟速率。使用分支可能会减少内存引用或指令计数，但它可能会阻碍流水线体系结构的进程。即使是5%的错误预测率，也会使今天的宽频处理器[1]的性能下降20-30%。

2.6 SIMD实现

使用SIMD指令的直接方式是将汇编语言内联到源代码中。然而，这可能是耗时、乏味和容易出错的。本文使用的是Intel c++ Compiler提供的SIMD intrinsic。intrinsic是一种特殊的编码扩展，它允许用户使用C函数调用和C变量的语法，而不是使用硬件寄存器。一般来说，直接汇编编码的性能优于intrinsic。然而，为了与用C编码的算法进行比较，我们使用了提供的intrinsics。

三、类SCAN操作

本节中，我们将研究多种顺序处理数据的操作。示例包括检索一个或多个未索引的属性、基于select条件创建bitmap，和标量聚合（没有groupby的聚合）。分组聚合可以通过在每个分组之上执行标量聚合，在进行排序来实现。类Scan的操作可以作为第4节和第5节中的复杂操作的组件来使用。

在实践中,我们需要考虑输入可能不是对齐的,或元素的数量可能不是S的倍数。特殊的代码片断可以用于第一和最后几个元素,剩下的“inner”部分的输入数组会是对齐的，且是S的整数倍。由于输入通常远远大于S，这些代码处理端点的开销可能很小。因此，我们下面关注的是那些对齐的输入，其大小是S的倍数。

本节中的所有的类Scan操作都具有以下高级结构。在这个伪代码片段中，N是单词的数量，它是S的倍数，x和y是对应于输入记录的列的数组。

for i = 1 to N {
  if (condition(x[i])) then process1(y[i]);
  else process2(y[i]);
}

不同的操作对应函数condition、process1和process2的不同实现。当然，扫描操作可能需要测试多个列，或处理多个列;我们选择单列只是为了表示的简单性。

相应的SIMD代码的高级结构如下所示:

for i = 1 to N step S {
  Mask[1..S] = SIMD_condition(x[i..i+S-1]); 
  SIMD_Process(Mask[1..S], y[i..i+S-1]); 
}

SIMD指令集通常具有丰富的比较、逻辑和算术指令。对于大多数包含比较、逻辑或算术操作的条件函数，都有一个等价的SIMD版本的SIMD条件，它将每个标量运算操作替换为其SIMD版本的SIMD操作。例如，如果condition(x)的实现是(4<x） && (x <= 8)，那么SIMDcondition(x[1..S])就会是(FOUR SIMD < x) SIMDAnd (x SIMD <= EIGHT)，其中FOUR和EIGHT是SIMD单元，分别包含4和8的S个副本。

尽管SIMD指令集非常丰富，但仍有一些条件不容易通过SIMD并行化。例如，对可变长度的数据类型(如字符串)进行操作。因此，我们不期望能够并行化字符串操作，比如SQL LIKE操作。

注意，SIMD算法中没有if测试。如果我们能够以一种避免If测试的方式实现SIMD Process，我们就可以避免条件分支及其可能导致的分支错误预测惩罚。

在接下来的内容中，我们将描述各种类似扫描的操作，并展示如何从process1和process2的实现中派生SIMD Process的实现。

3.1 返回第一个匹配值

我们讨论的第一个类scan的操作是返回第一个x[i]满足条件函数的y[i]。即，上一章节结构中的process1(y)会按照这样的方式实现，其中process2是空的：

process1(y) {result = y; return}

对应的SIMD_process是这样的：

SIMD_Process(mask[1..S],y[1..S]) {
  V = SIMD_bit_vector(mask);
  /* V = number between 0 and 2^S-1 */ 
  if (V != 0) {
  for j = 1 to S
    if((V>>(S-j))&1)  { 
      result = y[j]; 
      return; 
    } 
  }
}

注意，如果条件函数的选择性很低，所以掩码几乎为零，那么(V != 0)测试就节省了工作。

除了第一匹配算法外，还有一系列类似的算法，例如“唯一匹配”，在我们知道底层数据集最多包含搜索键的一个匹配时应用。这在实践中发生。例如，在传统的B+树中，通常只将唯一键放在叶节点中，指针指向具有该键的记录列表。一个唯一匹配算法将适用于这样的B+树的叶子，以进行精确匹配搜索。

在(V!=0)测试成功的情况下，这种变化可以节省工作，也就是说，y中的S个单词之间存在匹配。

我们利用我们知道只有一个匹配的事实来进行优化。SIMD进程方法现在是：

SIMD_Process(mask[1..S],y[1..S]) {
  V = SIMD_bit_vector(mask);
  /* V = number between 0 and 2^S-1 */ 
  if (V != 0) {
    result = SIMD_And(mask,y); 
    for j = 0 to log_2(S)-1 {
      result = SIMD_Or(result, SIMD_Rotate(result,2^j));
    }
  return result[1]; 
  } 
}

3.2 返回所有匹配值

当返回所有匹配项时，我们将结果写入名为result的数组，该数组由变量pos进行索引，pos最初指向结果数组的起点。对于这个操作，process1被实现为：

process1(y) { result[pos++] = y; }

SIMD_process和SIMD第一个匹配值很类似。唯一的区别是内部循环变成了：

{ result[pos++] = y[j]; }

我们称之为SIMD备选方案1。SIMD Process的第二个实现考虑到这样一个事实:如果选择性是中等水平，即既不接近0也不接近1，那么内部循环中的分支错误预测可能是常见的。这个替代方法(类似于[24]的“无分支”算法)如下所示。

SIMD_Process(mask[1..S], y[1..S]) {
V = SIMD_bit_vector(mask);
/* V = number between 0 and 2^S-1 */ if (V != 0) {
for j = 1 to S {
tmp = (V >> (S-j)) & 1; /* jth bit */ result[pos] = y[j];
pos += tmp; } }
}

3.2.1 构建Bitmap

“查找所有匹配”代码可以稍加修改以生成位图。这段代码可以反复使用以生成位图索引[19]。人们会简单地忽略V!=0的测试，并连续存储V值，形成位图。因此，此类操作的性能问题与寻找所有匹配项的性能问题类似。

3.3 标量聚合

假设我们希望对x值满足给定条件的行来聚合y列。在SQL中，这个对应着一个标量聚合，即没有GROUP BY子句但有WHERE子句的聚合。分组聚合可以通过先根据分组属性进行排序，然后执行多个标量聚合来实现。我们考虑可增量计算的聚合函数，包括sum, count, average, minimum和maximum。average可以通过同时计算sum和count来实现。

对于非SIMD的代码，process1的代码会执行聚合函数。例如，一个sum的聚合其代码可能如下所示：

process1(y) { result = result + y; }

其他聚合的编码也是类似的。我们现在考虑标量聚合的SIMD版本。

Sum and Count

对于这些操作，我们利用了一个事实，即一个由所有零组成的字代表零，在标准整数和浮点表示中都是如此。例如，Intel SIMD指令与满足这一特性的IEEE二进制浮点算术标准[14]兼容。(如果其他架构没有这种情况，那么我们的sum和count技巧将类似于下一节中给出的min和max。)

假设我们有一个名为sum的SIMD寄存器，它被初始化为S个零字。SIMD过程看起来像：

SIMD_Process(Mask[1..S], y[1..S]) {
temp[1..S] = SIMD_AND( Mask[1..S], y[1..S] ); 
sum[1..S] = SIMD_+( sum[1..S], temp[1..S] );
}

其思想是将不匹配的元素转换为0。完成处理后，我们需要将sum的S个元素相加作为最终结果。这可以通过log2(S) SIMD rotate和SIMD addition指令来完成。

计算count的代码和计算sum的代码相同，除了除了SIMD AND操作的第二个参数是包含“1”的SIMD word unit，而不是y。对于count，如果利用由所有1组成的word对应于大多数有符号整数表示中的整数-1这一事实，则可以进一步优化。在这种情况下，我们可以简单地在内部循环中使用单个SIMD指令添加掩码，并在最后对结果进行求反。(我们的性能实验没有使用这个技巧。)

Min and Max

Intel的SIMD指令集提供了一个SIMD操作，以并行的方式计算两个SIMD单元的最小值，最大值也类似。假设我们用可表示的最大数字的表示来初始化一个SIMD单位无穷大。一个名为min的SIMD单元被初始化为无穷大。然后，可以使用下面的SIMD流程操作实现min操作：

SIMD_process(mask[1..S], y[1..S]) {

  temp1[1..S] = SIMD_AND( mask[1..S], y[1..S] ); 
  temp2[1..S] = SIMD_ANDNOT( mask[1..S],infinity[1..S] ); 
  temp1[1..S] = SIMD_OR( temp1[1..S], temp2[1..S] );
  min[1..S] = SIMD_MIN( min[1..S], temp1[1..S] ); 
}

其思想是将不匹配的元素转换为无穷大，以便它们不影响最小结果。最后阶段是在min[1 . .]中得到S个元素中的最小元素。S]。这也可以通过log2(S) shuffle和SIMD最小指令来完成。

最大值操作与最小操作是相同的，除了我们使用负无穷而不是正无穷，并且应用SIMD max操作而不是SIMD min操作。

四、索引结构

索引结构减少了查询运行的计算时间，同时消耗了少量的空间。常见的索引结构包括各种树结构索引、bitmap索引和基于hash的索引。各种对现代架构敏感的索引组织技术已经被提出，特别强调缓存性能。这些技术既适用于主流内存的索引，也适用于基于磁盘索引中的磁盘页面布局。在本节中，我们将研究使用SIMD指令来提高索引遍历效率的技术。SIMD指令可以与缓存敏感的索引设计相结合，以最大限度地利用现代CPU架构。

我们特别关注基于树的索引结构。SIMD操作对其他索引设计也很有用。例如，它们可以通过允许并行计算哈希值来加快构建哈希索引的速度。

在数据库系统中使用的基于树的索引结构包括ISAM、B+树[7]和多维索引，如Quad树[10]、K-D-B树[23]和r -树[12]。搜索这些索引需要从根节点到叶节点重复搜索内部节点。在每个内部节点中，必须执行一些计算以确定要遍历哪个子节点。在叶节点中，需要进行类似的搜索。

我们描述了如何使用SIMD技术有效地搜索内部节点和叶节点。我们希望实现的第一个好处是，需要更少的指令来定位正确的子节点，因为SIMD中的指令可以同时比较多个键。第二个好处是，我们将能够对SIMD指令的结果进行简单的算术操作，以确定算法的下一步，而不是进行显式的if测试。因此，我们不需要任何条件分支指令。分支错误预测的代价很高，索引比较很可能是分支预测硬件的“最坏情况”工作负载，因为每次比较在大约50%的情况下是正确的，而且是不可预测的。因此，我们可以通过简单的计算来代替条件分支，从而大大节省时间。

我们首先在4.1节中介绍用于索引结构内部节点的技术。在第4.2节中，我们介绍了叶节点的技术。在每个部分中，我们使用B+树作为基本结构，并讨论了不同索引结构的不同处理技术。

4.1 内部节点

B+树是商业系统中常用的一种平衡索引结构。B+树将其节点(通常与磁盘页大小相等)组织成树。内部和叶节都至少有一半满。

内部节点存储有序的键序列。如果在一个节点中使用了n个键，那么将有n + 1个子指针。叶节点由索引键值的条目序列组成。每个键值条目引用具有该值的行集。传统上，索引通过行标识符(row IDentifier，或RID)引用每一行。一个rid序列(称为RID-list)保存在B+树叶子中每个不同的键值的条目中。我们假设键是固定长度的值;在我们的实验中，我们假设是32位的键。对于可变长度的键，比如字符串，通过为每个键存储固定长度的“poor man's normalized key”，可以获得固定长度键的许多好处。

如下图，我们将一个内部节点以这样的物理方式实现，键和子指针分别存在有序数组中。为了最大限度地利用SIMD指令，我们要求键(和指针)在一个16字节地址绑定的数组上正确对齐。每个节点中的页头存储键的数量、键类型、键大小、空白空间和其他必要的信息。叶节点的设计与此类似。

对于B+树内部节点，假设我们的键在key1, key2，…形式的数组中。， keyi为有序数据类型的元素，n为常量，keyi≤keyi+1。这n个键决定了n + 1个分支，我们为每个分支分配一个0到n之间的分支数。给定一个搜索键K，使keyi≤K的最小i为分支数;如果不存在这样的I，则分支编号为0。B+-树可以使用分支编号作为子指针数组的索引。

在不同的搜索算法中，二分查找是最好的。然而，二分查找在每一步都包含一个条件测试。在一些架构上，如奔腾，分支错误预测的代价是很高的。此外，二分查找所需的比较类型代表了分支预测硬件最坏情况下的工作负载，因为分支将占用大约50%的时间。因此，我们不能期望硬件实现低于50%的误预测率。

4.1.1 原生SIMD二分查找

第一个可能的优化点是使用SIMD指令来进行二分查找。相比于一次对比一个元素的方案，我们可以在一条SIMD指令中将键与S个连续元素进行比较。我们从数组的中间开始，像二分查找一样分左右进行处理。如果SIMD的对比结果全是0，则向左移动，如果都是1，那么向右移动。如果比较产生了一个中间值，我们就知道这个键会被数组当前的SIMD单元覆盖。将SIMD位向量应用于比较结果中，我们就可以直接计算出索引跳转的分支序号。

原生的SIMD二分查找没有消除所有的分支，但是它通过减少比较次数缩短了比较代码执行的时间。

4.1.2 SIMD顺序比较

有些索引，例如那些缓存局部性设计的索引，其节点大小是cache line大小的小倍数（Cache Line可以简单的理解为CPU Cache中的最小缓存单位。目前主流的CPU Cache的Cache Line大小都是64Bytes）。对着写索引来说，使用暴力方式将节点中的所有键和检索键进行比较可能更有效。当通过SIMD指令实现时，顺序比较这一方法会不包含任何复杂的分支指令（从而避免了分支预测错误），并且可以充分利用SIMD的并行性。基本思想很简单。我们将每个SIMD单元与搜索键k进行比较，然后计算小于或等于搜索键k的键的个数m。实现方法与第3.3节中count aggregation相同。我们的实验表明，在某些情况下，顺序比较的工作速度非常快。

这种方法的一种变体（我们称之为顺序检索2）会检查每一个比较结果。如果任何比较结果显示存在比搜索键大的键值时，我们就停止，即不需要处理剩余的键了，因为它们都比搜索键大。这种变体方法的优点是它处理更少的键（平均减少50%），执行更少的键比较指令。缺点是，我们需要在内部循环中执行一个额外的条件测试，以查看我们是否达到了比搜索键更大的键。我们将对这两种方法进行试验对比。

4.1.3 混合检索

考虑一个抽象的搜索模型，其中使用对数结构（如二叉树或是二叉搜索）来定位特定的元素序列，然后以此扫描该序列以找到特定的搜索键。假设这些叶子节点的序列长度都是L。那么整体复杂度大约是 a log2(n/L)+bL+c，a是在树或是二叉搜索中执行单个比较操作的成本，b是在顺序扫描中处理单个比较操作的成本。

对这个公式的直接分析表明，当L = A /(b ln 2)时，总成本最小。有趣的是，这个最小值与n无关。在一个抽象模型中，人们可以想象A≈b，因为每个都是进行单独的比较。这样的分析结果会建议对数结构的叶子节点序列长度L = 1，即普通的树或数组。

然而，当我们从现代体系结构去考量这种取舍时，一个不同的故事出来了。特别地，假设顺序扫描操作是使用章节3中的SIMD执行实现。然后a和b的相对大小会受到2种因素的影响。首先，由于顺序scan可以并行执行S个比较操作，因此 b 的有效值减少了接近 S 倍。其次，每次二分搜索比较有 50% 的机会导致分支预测错误，而有顺序搜索的分支错误预测很少（如果有的话）。这使 a 的相对成本增加了大约等于分支错误预测惩罚的一半的系数。我们将通过实验看到最终结果是我们机器的最佳 L 值约为 60。

因此我们提出了一个混合检索的方法。我们将数据分组成为长度为L的连续片段，对所有段的最后一个元素进行二分查找，直到找到正确的段。最后，顺序扫描正确的片段。

4.2 叶子节点

叶子节点和内部节点类似，除了它只有N的指针，对应N个key值。同样，对于精确匹配搜索，我们需要在叶子节点中找到一个精确匹配，而不是寻找大于或是等于搜索键的最小键。叶子节点设计的性能问题和内部节点设计的性能问题非常相似，性能图也类似。因此，我们认为对于小于L的叶节点，顺序搜索是首选方法，而对于较大的叶节点，混合搜索是首选方法。

在叶子中使用顺序搜索的一个有趣的好处是，叶子不需要按顺序存储。这使得插入、删除和键修改的代码更加简单，因为在叶节点中需要进行的复制要少得多。

4.2.1 多维索引结构的叶子节点

多维指数结构中的叶节点都是相似的。我们提倡将每个维度存储在单独的数组中，而不是在叶节点中使用一个键数组。RID指针数组是相同的。SIMD指令使我们能够在每个维度中一次比较S个键。在比较每个维度的S个键和SIMD和结果后，我们得到了S个元素的掩码。其余的叶节点设计可以像B+树那样完成。

五、JOIN处理算法

嵌套循环算法是处理连接最常用的方法。它可以处理相等连接和非相等连接。嵌套循环连接根据连接谓词将一个表的每条记录与第二个表的每条记录进行比较。使用SIMD技术，有三种方法可以实现嵌套循环连接。

• Duplicate-outer：在outer loop中，从outer表中获取一个join key，并将它重复S次以构建一个SIMD单元。在inner loop中，扫描inner表中的所有key来寻找匹配关系。使用3.2章节中的技术，每次将这个outer表的SIMD单元和S个inner表中的key进行对比。如果找到匹配，则产生相应的连接结果。

• Duplicate-inner：相反。

• Rotate-inner：在outer loop中，从outer表中获取S个连接键来创建一个SIMD单元。在inner loop中，从inner表中获取S个连接键，以创建另一个SIMD单元。比较两个单位S次，旋转内部单位之间的比较词。检查比较结果，并产生相应的连接结果。

如果我们有足够多的（多于 S 个）SIMD 寄存器，则可以以稍微更有效的方式评估内部循环：预先计算内部循环之外的外部记录的 S 个旋转，并在内循环中执行四个（？）单独的比较（并且没有旋转）。与第 3 节一样，我们假设使用 SIMD 指令集支持的逻辑和算术运算可以轻松地将连接谓词转换为 SIMD 形式。

对于我们的第一次研究，我们使用以下四个查询来展示不同算法的性能（第一个查询的key是整数类型，其他三个查询的key是浮点类型）。前两个分别是整数和浮点值的等值连接。第四个是范围连接，其中一个表中的记录必须在另一个表中的记录大小不变的窗口内[8]。第三种类似于范围连接，不同的是范围窗口的宽度因记录而异。

六、其他SIMD技术

在实践中，join的选择率通常是非常小的，这意味着所有记录比较重只有非常小的一部分能够成功匹配。因此，对于匹配结果的位向量V进行(V!=0)的测试是值得的。几乎所有的时候V都是0，这样我们就可以避免单个匹配的工作。

我们可以进一步观察。假设我们的SIMD架构允许对较小的数据类型进行SIMD操作。例如，在Pentium 4上，有针对8,16,32和64位数据类型的SIMD操作，对应的S值分别为16,8,4和2。