本章首先介绍PAX页布局模型，然后介绍连接索引的概念，接下来介绍面向闪存数据库的、基于PAX和连接索引的RARE连接算法以及FlashJoin算法，最后，介绍采用类似连接索引理念的DigestJoin方法。
有一些研究通过修改传统的查询处理技术，来充分利用闪存的快速随机读能力，从而达到提升数据库性能的目的。比如，文献[ShahHWG08][TsirogiannisHSWG09]的研究目标就是调查分析一些可以改进复杂数据分析查询性能的查询处理技巧，这类复杂查询主要出现在较少发生更新的商务智能和数据仓库应用中。这类研究主要采用PAX页布局模型和连接索引，来充分利用闪存特性，实现高效的数据库连接操作。
下面将首先给出关于NSM和DSM模型的简要介绍，然后，将分别介绍NSM模型存储原理和DSM模型存储原理。
图[row-column-database]行式数据库和列式数据库示意图
传统上，数据库系统使用NSM(N-aryStorageModel)存储模型[RamakrishnanG00]，也就是采用一个基于页的存储布局，其中，元组或行会被连续地存储在页中(如图[row-column-database](a)所示)。在读取数据时，需要顺序扫描每个元组，然后，从中筛选出查询所需要的属性。如果每个元组只有少量属性的值对于查询是有用的，那么NSM就会浪费许多磁盘空间和内存带宽。采用NSM模型的数据库，通常被称为“行式数据库”，主要适合于小批量的数据处理，常用于联机事务型数据处理。
DSM的缺陷是，需要存储元组ID的额外存储开销以及执行连接操作时需要昂贵的元组重构代价。因此，在过去很多年里，主流商业数据库大都采用了NSM而不是DSM。但是，随着市场需求的变化，尤其是企业对分析型应用（比如数据仓库）的大量需求，从最近几年开始，DSM模型重新受到青睐，并且出现了一些采用DSM的商业产品和学术研究原型系统，比如SybaseIQ、ParAccel、Sand/DNAAnalytics、Vertica、InfiniDB、INFOBright、MonetDB和LucidDB。类似SybaseIQ和Vertica这些商业化的列式数据库，已经可以很好地满足数据仓库等分析型应用的需求，并且可以获得较高的性能。
下面给出一个关于行式存储和列式存储的非常简单的实例。表[row-column-database]是一个数据库的关系R，包含了四个属性（EmpId、Name、Age和Salary）和三个元组。数据库必须把这个二维表存储在一系列一维的“字节”中，由操作系统写到内存或磁盘中。行式数据库把一行中的数据值串在一起存储起来，然后再存储下一行的数据，依此类推，存储结果如下：
1,Wang,35,4000;2,Lin,37,5000;3,Xue,42,4400;
列式数据库把一列中的数据值串在一起存储起来，然后再存储下一列的数据，依此类推，存储结果如下：
1,2,3;Wang,Lin,Xue;35,37,42;4000,5000,4400;
表[row-column-database]一个数据库关系的实例
传统上，数据库元组都是遵循NSM模型[RamakrishnanG00]被顺序地存放到磁盘上。NSM会在磁盘页上连续存储元组。图[NSM]给出了表[row-column-database]中的关系采用NSM模型存储的效果。每个页包含一个页头、元组存储区域和页尾。每个新的元组，通常会被插入到从页头开始的第一个可用的自由空间里。页尾包括许多个槽（slot），每个槽都存储了一个指向元组存储区域的某个元组起始位置的指针。当在一个页内新增加一个元组时，元组可能是可变的长度，因此，一个指向新元组的起始位置的指针（偏移量），会被存储到从页尾开始的下一个可用的槽里面。从页尾开始的第n个槽当中的指针，就指向该页中的第n个元组。
图[NSM]采用NSM模型存储的一个实例
图[DSM]给出了表[row-column-database]中的关系采用DSM模型存储的效果。DSM[CopelandK85]把具有3个属性（除了EmpId）的关系R分解成3个子关系R1、R2和R3，每个子关系都包含两个属性。子关系会被存储到一个常规的页中，从而允许对每个属性进行独立的扫描。
图[DSM]采用DSM模型存储的一个实例
PAX（PartitionAttributesAcross）[AilamakiDH02]是一种混合的方法，在本质上是一个在NSM页内部采用类似于DSM的组织方式。PAX背后的机理是：像NSM一样，把每个元组的属性值都保存在同一个页中，同时使用一个缓冲区友好的算法来把数据放置到页中。PAX会在每个页内部对元组进行垂直分区，把所有属于同一个属性的值都一起存储在“迷你页”（minipage）中。也就是说，PAX把第一个属性的所有值都存储到第一个迷你页中，第二个属性的所有值都存储到第二个迷你页中，依此类推。在每个页的开始处，有一个页头，它包含了到每个迷你页起始处的偏移量。每个迷你页的结构如下：
（1）固定长度的属性值被存储到“F-迷你页”中。在每个F-迷你页的尾部，有一个存在位向量，每条记录对应一个条目（entry），对于空属性，其对应的存在位会记录一个空值。
（2）变长的属性值会被存储在“V-迷你页”中，V-迷你页尾部包含许多个槽（slot），每个槽都包含一个指针，指向每个属性值的末尾，空值就用空指针表示。
图[PAX]给出了用PAX模型存储表[row-column-database]中的记录的效果。在页头部分，包含了页号pid、属性个数、记录个数、属性长度和可用空间等信息。为了存储这个具有3个属性（除了EmpId以外的3个属性：Name、Age、Salary）的关系，PAX把一个页分解成3个“迷你页”（minipage），即V-迷你页1、F-迷你页2和F-迷你页3，然后，它把第一个属性Name的所有值都存储到第一个迷你页中，第二个属性Age的所有值都存储到第二个迷你页中，依此类推。在每个PAX页的开始处都有一个页头，它包含了到每个迷你页起始处的偏移量。因此，当使用PAX的时候，每个元组会驻留在相同的页上，就像使用NSM时一样。但是，所有的Name属性值、所有的Age属性值和所有的Salary属性值，都会被分组存储在各自的迷你页内。通过这种方式，PAX增加了元组之间的空间局部性，因为，它把属于不同元组的相同属性的值都保存在同一个迷你页中，同时还不会影响元组内部的空间局部性。此外，尽管PAX采用了页内垂直分区，但是，它只会带来很小的元组重构代价，因为，它不需要执行连接操作来重构一个元组。
每个新分配的PAX页，都包含了一个页头和许多迷你页，迷你页的数量和关系的属性数量相等。页头中存储的信息包括属性的数量、属性的长度（对于固定长度的属性）以及到迷你页起始位置的偏移量、页中当前已经存储的元组的数量和可用的总空间。对于属于同一个页的元组而言，可以被顺序地访问，或者也可以被随机地访问。
在存储一个关系时，PAX的空间开销和NSM是一样的。NSM会连续存储每个元组的属性值，因此，对于NSM而言，每个元组都需要存储一个偏移量，并且需要为每个元组中的可变长度的属性提供一个额外的偏移量。而对于PAX而言，需要为每个可变长度的属性值存储一个偏移量，另外还需要提供一个关于每个迷你页的偏移量。因此，无论一个关系使用PAX还是NSM，都需要占用相同数量的页。
PAX和其他设计是独立的，因为它只影响单个页上的数据布局方式，也就是说，在同一个数据库中，可以让一个关系使用PAX模型进行存储，而另一个关系则使用NSM模型进行存储。
图[PAX]采用PAX模型存储的一个实例
但是，NSM在缓存行为方面的表现不尽人意。NSM会从每个磁盘页的起始位置开始连续存储元组，并且使用页末尾的“偏移量表”来定位每个元组的起始位置[RamakrishnanG00]。但是，绝大多数查询操作，只会访问每个元组的一少部分属性（或字段），这将导致无法获得最好的缓存性能。例如，对一个特定属性的顺序扫描时，将会发生缓存脱靶，每次访问一个属性值时，都需要访问一次内存。这个过程会把无用的数据加载到CPU缓存中，直接带来以下负面结果：（1）浪费了带宽；（2）无用的数据污染了缓存；（3）可能会强制替换未来可能用得到的数据，引发更多的延迟。
PAX是对NSM和DSM两个模型的巧妙结合，既能够提供空间局部性，也具备较小的重构代价。而且，在现有的DBMS上实现PAX，只需要修改页级别的数据操作代码。
表[NSM-DSM-PAX]NSM、DSM和PAX之间的特性比较
PAX相对于DSM的优势：和PAX模型相比，DSM模型存在两个明显的局限性。首先，传统的关系数据库引擎的许多组件，比如存储层、IO子系统、缓冲池、恢复系统、索引和运算符等，都被设计成在固定大小的页上执行操作。因此，DSM模型会涉及到所有这些组件，需要对这些组件进行重新设计。但是，PAX模型只需要重新实现存储层（负责从页中读取数据），因为，在PAX模型中，只有页的组织方式和传统不一样，而页的内容则没有发生变化。其次，采用DSM模型的列式存储，可能需要多个IO来更新一个行中的多个列。而采用PAX模型的时候，只需要一个IO就可以完成对一个行中的多个列的更新，因为，一个行中的所有的列都存储在相同的页内。
第一，在磁盘中采用PAX模型不会获得收益。对于在磁盘上跳过迷你页的一个寻址而言，至少要一次跳过300KB-400KB(100MB/s*3-4ms)的迷你页，才可以获得收益，也就是说，在磁盘中采用PAX模型时，需要把一个迷你页的大小设计为300-400KB。但是，采用PAX模型时，磁盘中的一个页包含多个迷你页，如果一个迷你页都已经达到300KB，那么，一个页的大小会达到好几个MB。但是，对于一个关系型DBMS而言，在设计页的大小时，会综合考虑诸多因素，比如缓冲池尺寸、缓冲区命中率、更新频率和每页的算法开销等。而在考虑了上述这些因素以后，大多数关系型DBMS往往都倾向于使用更小的页，通常是8KB或者64KB，而不是几个MB。因此，在磁盘中采用PAX模型，不会为关系型DBMS带来性能收益。
两个关系R1和R2之间的连接索引，包含了一系列元组“标识对”，表示为
在许多情形下，采用连接索引的连接算法可以比最好的即席连接算法（比如混合哈希连接算法[DeWittKOSSW84]）获得更好的性能。PatrickValduriez[Valduriez87]在1987年设计了使用连接索引的连接算法，这个算法可以很简单地实现，而且对于选择性连接非常有效。但是，对于Valduriez算法而言，当输入关系的大小大于内存时，需要对其中一个关系执行多趟扫描。因此，就性能而言，Valduriez的算法可能导致许多重复的IO，有时候只为了访问一少部分元组就需要访问整个块。而且，相同的块可能会被多次读取。
Li等人在1999年提出了针对Valduriez的算法的改进算法——Jive(JoinIndexwithVoluminousrelationExtensions)连接算法[LiR99]。Jive连接算法会对第二个输入关系的元组ID根据值域进行分区，然后单独处理每个分区。Jive算法的特性包括：
Jive算法具有较好的特性是因为连接结果使用了垂直分区的数据结构。不过，Jive并没有对输入关系进行垂直分区，而是对连接结果进行垂直分区。存储连接结果的垂直分区数据结构，被称为“转置文件(transposedfile)”[Batory79]。来自输入关系R1并且存在于连接结果当中的属性，会被存储到一个单独的文件中，称为JR1，同理，来自输入关系R2并且存在于连接结果当中的属性，会被存储到另一个单独的文件中，称为JR2。属于两个输入关系R1和R2的公共属性，即连接属性，会被存储到JR1或JR2中的任意一个中。每个文件（JR1或JR2）中的第一个条目（entry），都对应着第一个连接结果元组，第二个条目，对应着第二个连接结果元组，依此类推。由于每个垂直分区采用相同的顺序，因此，两个分区中的每个连接结果元组都存在一一对应关系，这就意味着，不需要额外存储元组ID或代理键，就可以直接对两个垂直分区进行组合得到最终连接结果。
图Jive-example-transposed-file演示了连接结果的垂直分区，图中左边显示了采用传统的布局方式时的连接结果JR（包含了Worker、Department和Manager属性），右边显示了采用垂直分区布局时的连接结果JR1（包含Worker属性）和JR2（包含Department和Manager属性）。可以看出，对于传统的布局方式和垂直分区布局方式而言，连接结果占用的空间开销都是相同的。
图[Jive-example-transposed-file]连接结果的垂直分区
对连接结果采用了垂直分区方式以后，Jive连接算法就可以分成两趟输出连接结果，每一趟的连接结果都对应于来自其中的一个输入关系的属性，最后对两个垂直分区进行组合就可以得到最终连接结果。因此，进行垂直分区方式的一个明显优点是，不需要同时把全部元组都存放在内存中，而是在不同的阶段分次写入每个垂直分区，这样可以更好地利用内存。
Jive连接算法会把来自R1的元组和来自连接索引的记录进行匹配，同时，R2的记录会被分区，每个分区都包含了R2元组ID的一个区间，并且根据R2中元组的ID，让R1和R2的元组进行匹配。发生匹配的R1记录以及与它匹配的R2元组ID，会被存放到不同的输出文件中。发生匹配的R1记录会输出到一个输出文件JR1中，这个输出文件包含了连接操作中发生匹配的R1记录的集合，而与这些R1记录相匹配的R2元组ID，则会输出到一个临时文件中，这个临时文件包含了与R1记录相匹配的R2元组ID的集合。然后，临时文件会和关系R2中的记录一起被处理，来生成另一半连接结果JR2。
Jive算法包括三个步骤：
（1）第1步：确定分区
（2）第2步：生成一半连接结果JR1
以顺序的方式扫描连接索引J和关系R1（注意：前面已经假设J是以R1元组的顺序存储的），由于连接索引J中包含了R1元组ID，因此，可以对J和R1中的元组进行匹配。在读取R1的过程中，如果决定读入关系R1的一个块，当且仅当这个块包含了连接索引中涉及的元组。在每次匹配时，首先需要确定一个发生匹配的元组所属的分区，这个可以根据R2元组的ID来判定，因为在第1步中就是根据R2元组ID来分区的，连接索引J的每个条目都是一个元组标识对
（3）第3步：生成另一半连接结果JR2
对于临时文件的每个分区，分别执行以下操作：把整个分区读入内存，并且对R2元组ID进行升序排序，消除重复元组ID。需要指出的是，临时文件的原来版本一直保存着，排序得到的结果会单独存放在新的临时文件中。然后，从R2中一直顺序地读取元组，并且根据已经排序的临时文件，只从R2中读取包含了一个匹配记录的块。当从R2中读取的ID比分区中的ID大时，就暂时停止读取R2元组。到了这个点，已经得到了连接结果JR2的一个分区，可以采用以下方式把这个分区写入文件：查看为这个分区准备的临时文件的原始版本（即未经排序的版本），把相应的R2元组中属于连接结果的属性，以原始版本临时文件中的顺序写入到JR2的分区中。然后，对于临时文件的下一个分区，继续执行上面的操作。当已经写完最后一个分区到JR2中时，就生成了所有的JR2分区。JR2的不同分区可以被连接成单个文件。
最后，对第2步产生的连接结果JR1和第3步产生的连接结果JR2进行合并，就得到所需要的连接结果。注意，在第2步和第3步中，如果R1或R2的某个块根本不会包含参与连接操作的元组，可以不用读取这个块。因此，如果输入关系中只有一少部分参与了连接操作，这种方式可以让连接算法获得更好的性能。
为了更好地理解Jive连接算法，这里给出一个实例。如图[Jive-example]所示，两个关系R1和R2分别是Employee（见图[Jive-example](a)）和Management（见图[Jive-example](b)），其中，Employee关系包含了两个属性Worker和Department，分别表示雇员姓名和所在部门编号；Management关系包含了两个属性Department和Manager，分别表示部门编号和部门管理员。这里把每个关系中的元组出现的序号，作为元组ID，比如Employee关系中的第1个元组
图[Jive-example]Jive连接算法的一个实例
为了执行Jive连接算法，需要创建一个连接索引，如图[Jive-example](d)所示。连接索引的每个条目都是一个元组标识对
在整个构建连接索引的过程中可以发现，Management关系不存在部门编号为D07的元组，因此，Employee关系中的第9个元组
下面将演示按照Jive连接算法的三个步骤依次执行连接操作。
假设这里把Management关系（R2）分成三个分区，即x=3，并且假设每个缓冲区每次只能容纳一个元组。这里选择Management关系的元组ID值3和6作为分区点，即ID小于3的元组构成一个分区a，ID大于等于3并且小于6的元组构成一个分区b，ID大于等于6的元组构成一个分区c。
以顺序的方式扫描连接索引J和关系Employee关系（R1），对连接索引和Employee关系中的元组进行匹配。为了生成一半的连接结果JR1，在Employee关系中找到与连接索引
Employee关系（R1）中的元组被输出到哪个输出文件分区，是由连接索引中属于Management关系（R2）的元组标识符t2来决定的，t2属于哪个分区，就把t1对应的Employee关系（R1）的元组写入到这个分区。连接索引的第1个条目<1,1>的右边元素t2的值是1，Management关系（R2）的元组标识符为1的元组，会被划分到分区a，因此，t1对应的元组的Worker属性值“Wang1”会被写入到输出文件分区JR1(a)中（实际上是首先输出到为输出文件分区JR1(a)准备的内存缓冲区中，缓冲区满后才会被刷新到输出文件分区JR1(a)中）。连接索引的第1个条目的右边元素t2的值1，会被写入到为分区a对应的临时文件Temp(a)中（实际上是首先输出到为临时文件Temp(a)准备的内存缓冲区中，缓冲区满后才会被刷新到临时文件Temp(a)中）。
最终，可以得到图[Jive-example-join-JR1]中的三个输出文件分区JR1(a)、JR1(b)和JR1(c)，同时得到三个临时文件分区Temp(a)、Temp(b)和Temp(c)。JR1(a)、JR1(b)和JR1(c)会被合并成一个文件JR1，这时，就得到了一半的连接结果。Temp(a)、Temp(b)和Temp(c)会在下面的步骤3中使用，被用来生成另一半连接结果JR2。
需要注意的是，属性Department属于两个输入Employee关系（R1）和Management关系（R2）的公共属性，即连接属性，可以被存储到JR1或JR2中的任意一个中，这里假设存储到JR2中，因此，在前面一半的连接结果JR1中不存在Department属性。
图[Jive-example-join-JR1]Jive连接算法的一半结果JR1
对于临时文件的分区Temp(a)，把整个分区读入内存，并且对Management关系（R2）元组ID进行升序排序，消除重复元组ID，因此，可以得到排序后的分区Sort(a)。需要注意的是，Sort(a)会被保存到新的文件中，原来的分区文件Temp(a)仍然存在。然后，从Management关系（R2）中一直顺序地读取元组，并且根据已经排序的临时文件Sort(a)，只从Management关系（R2）中读取包含了一个匹配记录的块。Sort(a)中的最大元组ID是2，因此，在Management关系（R2）中读取完第2个元组以后，就可以停止读取，这时，Management关系（R2）中的第1个
接下来要把这些元组输出到连接结果文件分区JR2(a)中，也就是说，输出文件JR2也是根据分区a、b和c被分成三个输出文件分区JR2(a)、JR2(b)和JR2(c)，R2中元组ID为1和2的两个元组在进入连接结果JR2中时，都会被写入到JR2(a)中（实际上是先写入为JR2(a)准备的缓冲区，缓冲区满后再写入到文件JR2(a)中），其他连接结果也都会按照相同的办法被写入到各自所属的输出文件分区中。在把这些元组输出到连接结果文件分区JR2(a)中时，采用的是未经排序的原始版本的Temp(a)中的元组顺序，Temp(a)中的第1个元组ID是1，因此，首先把已经读入内存的Management关系（R2）的元组
接下来，把临时文件分区Temp(b)全部读入内存，按照上面的方式，计算得到连接结果的第2个分区文件JR2(b)，如图[Jive-example-join-JR2]中间所示。然后，把临时文件分区Temp(c)全部读入内存，按照上面的方式，计算得到连接结果的第3个分区文件JR2(c)，如图[Jive-example-join-JR2]右边所示。
已经得到JR2的不同分区JR2(a)、JR2(b)和JR2(c)以后，可以把JR2(a)、JR2(b)和JR2(c)连接成单个文件JR2，如图[Jive-example-join-JR]所示。
图[Jive-example-join-JR2]Jive连接算法的另一半结果JR2
图[Jive-example-join-JR]Jive连接算法的最终结果
从上面实例的执行过程可以发现，Jive连接算法具备几个重要的特性：（1）算法只会读取参与连接的元组；（2）参与连接的元组只会被读取一次，即使该元组可能会参与多次连接运算；（3）对每个输入关系都只要进行一趟扫描。
文献[ShahHWG08]提出了面向闪存的、采用PAX模型和连接索引的RARE连接算法，该算法借鉴了Jive算法的设计思路，当输入关系太大无法一次性放入内存时，采用连接索引，先生成一半的连接结果，然后再生成另一半连接结果，并且，在扫描输入关系的过程中，不仅只会访问那些参与到连接操作中的列，而且只访问那些包含了连接结果所需要的值的迷你页，而不是访问所有的输入关系，以此来达到节省IO开销的目的，提高查询性能。需要注意的是，这种IO开销的节省需要额外的代价，即会增加寻址开销（从一个迷你页跳到另一个迷你页），并且需要计算连接索引。但是，RARE连接算法节省的IO开销，超过了额外的代价，因此，在理论和实际应用中都是可行的。
下面将以经典的Grace哈希连接算法作为参照对象，来讨论RARE连接算法在两种情形下的性能：（1）当存在足够的内存时，只需要对输入关系扫描一趟来计算连接；（2）当输入关系太大无法一次性放入内存时，需要多趟输入的时候。
需要指出的是，前面已经通过实例详细介绍了Jive连接算法的执行过程，由于RARE连接算法基本采用了Jive连接算法的设计思路，因此，下面只会介绍RARE连接算法的基本过程，不再给出实例演示。
首先考虑采用NSM模型的Grace哈希连接算法。假设有两个参与连接操作的关系R1和R2，并且为R2建立的哈希表h可以一次性放入内存，即|h(R2)|<|M|，其中，h(R2)表示为R2建立的哈希表h的空间开销，|M|表示内存空间大小。这时，Grace哈希连接算法只需要对输入关系执行一次扫描，就可以计算得到结果，具体方法如下：
在上述过程中，所有的访问都是顺序执行的，因此，总体的IO代价的计算方法很简单，即|R1|+|R2|+|S|。
现在考虑采用PAX模型的Grace哈希连接算法，简称“Grace-PAX”。和Grace哈希连接算法相比，Grace-PAX连接算法可以取得更好的性能，主要是由于两个方面的原因：
第二，由于它跳过了不需要的列。因此，对于Grace-PAX而言，总共的IO代价会少于|J1+V1|+|J2+V2|+S。
再来考虑采用PAX模型的RARE连接算法（如算法[1-pass-RARE]所示）。对于RARE连接算法而言，它只会读取关系R2中那些参与连接的列J2和行ID号（即id2），并且构建哈希表。然后，它使用J1来探测哈希表，输出连接结果。在采用了PAX模型后，每个页都存储了相同数量的行（或元组），在每个页内部，这些行会以列的方式被存储到不同的迷你页中。因此，与Grace-PAX不同的是，RARE并不是读取V1和V2中的所有内容，而是只会读取那些可以产生连接结果的迷你页，即从V2中只读取那些包含行ID号（即id2）的迷你页，从V1中只读取那些包含行ID号（即id1）的迷你页。
需要指出的是，RARE连接算法在执行输入关系的扫描时，会对R1进行顺序扫描，因此，在连接算法执行过程中，新扫描进来的V1迷你页可以立即替换掉内存中旧的迷你页，不会引起内存空间消耗的不断增加，在整个过程中只需要在内存中保留V2迷你页。最终，RARE连接算法会把结果输出到S中。
可以看出，采用PAX模型的RARE连接算法的内存需求是(|h(J2)|+|h(id2)|)+|p2(V2)|<|M|，其中，p2(V2)表示V2中会被连接计算使用到的那些元组。RARE连接算法的总IO代价是：|J1|+|p1(V1)|+|J2|+|p2(V2)|+|S|。由此可以看出，在采用大约相同的内存的情况下，单趟RARE连接算法要比单趟Grace-PAX连接算法减少了IO代价。
2.ReadJ1andprobehash-table;
foreachjoinresult
{
Readprojectedvaluesofrowid1fromV1;
Readprojectedvaluesofrowid2fromV2;
WriteresultintoS;
}算法[1-pass-RARE]单趟RARE连接算法
当内存空间有限，或者关系R2太大时，为R2构建的哈希表就无法一次性放入内存，这时，Grace哈希连接算法就需要执行多趟（pass）扫描。另外，对于Grace-PAX连接算法而言，如果J2和V2无法一次性放入内存，它也会退化成多趟扫描。第一趟会在连接列上对两个输入关系进行分区，从而使得单个分段可以一次性放入内存。第二趟会读取每个分段到内存中，计算连接结果。
因此，对于多趟Grace哈希连接而言，总的IO开销就是：3(|R1|+|R2|)+|S|，因为，第一趟分区操作，需要一次读入（IO开销为|R1|+|R2|）和一次输出（IO开销为|R1|+|R2|），第二趟的IO开销和原来的“1趟Grace哈希”连接算法相同，都是|R1|+|R2|+|S|，因此，总共的IO开销是3(|R1|+|R2|)+|S|。
类似地，对于Grace-PAX而言，IO总开销就是：
3(|J1+V1|+|J2+V2|)+|S|公式(Grace-PAX)。
下面将分两种情况介绍RARE连接算法可以比Grace-PAX连接算法获得更好的性能。
当J2可以一次性放入内存而V2无法一次性放入内存时，RARE连接算法（如算法[1+pass-RARE]所示）仍然可以只对输入关系进行一趟扫描来计算得到连接结果。
RARE连接算法执行第1步时，首先读取J2，并在J2上面构建一个哈希表。然后，读取J1，并使用J1对哈希表进行探测，探测这个哈希表的结果就是“连接索引”（和Jive连接算法中介绍过的连接索引是完全相同的概念，在RARE算法中也会发挥相同的作用）。对于出现在连接结果S中的每一行而言，在连接索引中都有与之对应的一个条目。由于探测哈希表时采用了J1的顺序，因此，那些需要的V1迷你页就可以被顺序地读取，并且直接被写入到结果S中。由于使用了PAX模型，因此，第2步只会把V1中的投影列（即V1中那些出现在连接结果中的列）写入到S中，并为每个连接结果中的属于V2的列预留一个空位置，直到第3步的时候，再用V2中的列值来填充这个空位置。从这里可以看出，RARE连接算法借鉴了Jive连接算法的思想，因为，Jive连接算法也是先生成一半的连接结果，然后再生成另一半的连接结果。需要指出的是，这种针对S的写模式，在闪存上是十分高效的，因为，在这个步骤已经付出了闪存擦除操作的代价，在第3步中只需要在预留的空位置写入值即可。
在连接条件上发生匹配的R2中的元组的ID会被写入到一个临时文件I2的对应分区中（相当于Jive连接算法的第2步中把R2的元组ID写入到临时分区Temp(a)、Temp(b)或Temp(c)中，从而在第3步用来生成另一个连接结果）。
对于步骤3而言，属于同一个分段的整个V2页的集合，必须一次性放入内存，这点与Jive连接算法是相同的，Jive连接算在执行第3步时也有类似要求。需要的分段的数量就是|V2|/|M|，采用的分区函数可以是一个哈希函数，或者域分区机制。RARE连接算法对S采用相同的分区方式，从而在步骤3中，可以使用相应的V2值来对填充S中的空白部分（相当于Jive连接算法中的第3步生成另一半连接结果JR2）。
由于需要为S和I2的每个分段提供一个缓冲页，并且最多有|V2|/|M|个分段，因此，(1+ε)趟RARE连接算法的内存需求就是(|h(J2)|+|h(id2)|)+2*(|V2|/|M|)<|M|。所有三个步骤的总共IO代价就是：
|J1|+p1|V1|+|J2|+p2|V2|+|S|+2|I2|公式(RARE-1+-pass-cost)。
由前面公式(Grace-PAX)可知，Grace-PAX的IO代价是3(|J1+V1|+|J2+V2|)+|S|。因此，把Grace-PAX的IO代价（公式(Grace-PAX)）和(1+ε)趟RARE算法的IO代价（公式(RARE-1+-pass-cost)）进行相减，当二者差值大于0时，RARE算法的性能更好。也就是说，当以下条件成立时，RARE算法的性能要比Grace-PAX更好：
2|J1|+(3-p1)|V1|+2|J2|+(3-p2)|V2|>2|I2|。
条件的左边是节省的开销，包括只读取连接涉及的列和V1、V2中所需要的迷你页，只需要读取一次，而不是三次。这种节省的开销，必须能够超过下面的额外代价：即从连接索引中读取行ID（id2）和物化的开销。
/*SandI2arebothpartitionedbyid2*/
WriteprojectedvaluesintopartitionofS;
Writeid2intopartitionofI2;
}
3.ReadI2andprocessit.
foreachpartitionofI2do
foreachid2inpartitiondo
WritevaluesintopartitionofS;
}算法[1+pass-RARE](1+ε)趟RARE连接算法
算法[2-pass-RARE]显示了当J2和V2都无法一次性放入内存的情况下RARE算法的伪代码。在这种情形下，步骤1和步骤2和Grace哈希类似。RARE哈希会把两个表的连接列进行分区，从而，每个J2分段都可以一次性放入内存。在步骤3中，它为每个分段计算和物化连接索引
在步骤4中，RARE会把J1的分段合并成R1的顺序，并且读取需要的投影列V1。第5步和(1+ε)算法的第3步一样。需要注意的是，连接索引的尺寸是I2大小的两倍，因为，它包含了id1和id2。此外还要注意，RARE只会读取V1和V2中所需要的迷你页。
整个过程的代价构成如下：
因此，可以计算得到总共的IO代价是：
3|J1|+p1|V1|+3|J2|+p2|V2|+|S|+6|I2|公式(RARE-2-pass-cost)。
由前面公式(Grace-PAX)可知，两趟Grace-PAX的IO代价是3(|J1+V1|+|J2+V2|)+|S|。因此，把两趟Grace-PAX的IO代价（公式(Grace-PAX)）和两趟RARE算法的IO代价（公式(RARE-2-pass-cost)）进行相减，当二者差值大于0时，两趟RARE算法的性能更好。也就是说，当以下条件成立时，两趟RARE算法的性能要比两趟Grace-PAX更好：
(3-p1)|V1|+(3-p2)|V2|>6|I2|。
左边的代价节省是由于：只需要访问V1和V2中所需要的页，只需要访问一次，而不是三次。右边是来自对连接索引的多次读取和物化的额外代价。
2.ReadJ1andpartitionit(samehashfunction);
3.ComputeJI;
foreachpartitionpofJ2do
Readpartitionpandbuildhash-table;
ReadpartitionofJ1andprobehash-table;
foreachrowinjoinresultdo
Writeid1,id2inJIpartition;
4.MergepartitionsofJIonid1;
5.ReadI2andprocessit.
foreachparititionofI2do
}算法[2-pass-RARE]两趟RARE连接算法
Tsirogiannis等人提出的FlashJoin连接算法[TsirogiannisHSWG09][GraefeHKSTW10]，也是一种专门针对闪存固态盘设计的数据库连接算法，与RARE类似，也都采用了连接索引和PAX模型，在此基础上，作者又实现了FlashScan，这是一个扫描操作，它只会从固态盘中读取那些参与到一个查询中的属性。FlashScan在从一个指定的行中抓取额外的属性之前，会先对谓词进行分析，因此，可以进一步减少数据读操作的数量。
FlashScan充分利用了固态盘的较小的传输单元，然后，只需要读取那些查询所需要的属性的迷你页。假设有一个不包含选择谓词的扫描，它要投影出关系的第1列和第3列。对于每个数据库页，FlashScan首先会读取第一个属性的迷你页，然后寻找第三个迷你页并且读取。接下来，它会再次寻找下一个页的第一个迷你页，然后寻找第三个迷你页……。这个过程会一直持续，直到扫描完整个关系，这就会导致一个随机的访问模式。总体而言，每次寻找都会导致一个随机读操作。而闪存固态盘的随机读操作和顺序读操作一样，具有很高的性能，因此，FlashScan可以获得很高的性能。
有了FlashScan以后，就可以高效地抽取需要的属性，在此基础上，作者进一步提出了FlashJoin（如图[FlashJoin-example]所示），这是一个通用的、流水线结构的连接算法，通过尽量推迟检索并且只检索那些需要的属性，可以最小化对关系页的访问。FlashJoin包括了一个二路连接（binaryjoin）内核和一个单独的抓取（fetch）内核。多路连接会被分解成一系列流水线结构的二路连接。FlashJoin的连接内核只会访问连接所涉及的属性，并为每个连接节点生成连接索引形式的部分结果。FlashJoin的抓取内核，为会查询计划中的后续节点获取属性，并且会根据连接的选择性（selectivity）和可用的内存来选择不同的抓取算法。实验结果显示，FlashJoin不仅可以明显减少内存的使用数量，还可以减少查询中每个连接的I/O数量。
在仔细分析了一些算法和数据结构以后，Tsirogiannis等人还发现：
图[FlashJoin-example]采用FlashJoin时的三路连接实例
传统的连接算法，在不存在索引的情形下，算法的目的是为了最小化寻址操作的数量，因为，这些算法是针对磁盘设计的，磁盘存在机械部件，寻址开销很大，减少寻址操作可以有效提升连接算法的整体性能。但是，在闪存数据库系统中，最小化寻址开销并不会带来明显的收益，因为，闪存的随机读操作和顺序读操作具有同样高的性能。
为了充分利用闪存快速的随机读能力，Li等人[LiOXCH09]提出了一种摘要连接算法DigestJoin，假设参与连接的两个原始关系（或表）为R和S，该算法把R和S的连接过程分成两个阶段来执行：
假设两个参与连接的关系为R={Ar1,Ar2,…,Arm}，S={As1,As2,…,Asn}，其中，Ar和As分别表示关系R和S的属性，这里分别用tidr和tids表示R和S的元组ID。为了简化起见，这里讨论。在DigestJoin算法的第一个阶段，首先，需要扫描原始表R和S得到摘要表和，这两个摘要表只包含了元组ID和连接属性，即和。摘要表要比原始表小很多，可以明显减少实际连接操作时的IO开销。然后，利用一个传统的连接算法，比如嵌套循环连接、归并排序连接或哈希连接，对两个摘要表进行连接，得到摘要连接结果{Ar1,tidr,tids}。如果摘要连接结果大于内存可用空间，就可以把它们顺序写入到闪存中。但是，摘要连接结果{Ar1,tidr,tids}只是告诉我们哪些元组在连接条件上发生了匹配。为了得到完整的连接结果，必须根据tid从原始表中抓取相应的元组。在RDBMS中，从原始表中抓取元组通常都是以页为单位，因此，DigestJoin算法的第二个阶段被称为“页抓取”。虽然页抓取需要一定的随机读开销，但是，如果能够设计合适的页抓取策略，这种开销只是第一个阶段（即得到摘要连接结果阶段）所节省的开销的一部分，因此，DigestJoin算法在整体上可以比传统的连接算法节省代价。
页抓取策略对DigestJoin第二个阶段的IO开销影响较大，这里以一个实例来说明这个问题。假设从关系R和S可以得到以下几个摘要连接结果：{r1,tidr1,tids1}、{r2,tidr2,tids2}、{r3,tidr3,tids3}和{r4,tidr4,tids4}。在闪存中，元组tidr1和tidr3被存储在页P1上，元组tidr2和tidr4被存储在页P2上，元组tids1和tids3被存储在页P3上，元组tids2和tids4被存储在页P4上。当有足够的内存空间时，就可以抓取所有的P1,P2,P3,P4四个页，然后，在构建最终连接结果的整个过程中都把这四个页保存在内存中，在整个连接过程中，就只需要对四个页进行一次读取的IO开销。但是，实际上内存空间是有限的，这就需要设计合理的页抓取策略，从而最小化页的读取开销，当页抓取策略不合理时，会导致一个页刚被驱逐出内存，很快又要再次到闪存中抓取该页进入内存的情况，带来不必要的IO开销。这里假设内存空间只能最多同时容纳两个页，如果以r1,r2,r3,r4的顺序构建得到最终连接结果，那么页抓取过程如下：
（1）从摘要连接结果{r1,tidr1,tids1}中得到与r1对应的完整的连接结果：由于tidr1对应的元组在页P1上，tids1对应的元组在页P3上，因此，为了得到r1对应的完整结果，就必须从闪存中抓取页P1和P3进入内存；
（2）从摘要连接结果{r2,tidr2,tids2}中得到与r2对应的完整的连接结果：由于tidr2对应的元组在页P2上，tids2对应的元组在页P4上，因此，为了得到r2对应的完整结果，就必须从闪存中抓取页P2和P4进入内存；但是，由于内存中已经存在P1和P3，而且内存只能最多同时容纳两个页，因此，需要把P1和P3驱逐出内存，腾出空间，把P2和P4放入内存；
（3）从摘要连接结果{r3,tidr3,tids3}中得到与r3对应的完整的连接结果：和上面的过程类似，必须从闪存中抓取页P1和P3进入内存，因此，需要把P2和P4驱逐出内存，腾出空间来存放P1和P3；
（4）从摘要连接结果{r4,tidr4,tids4}中得到与r4对应的完整的连接结果：和上面的过程类似，需要把P1和P3驱逐出内存，腾出空间来存放P2和P4。
综上所述，在为r1,r2,r3,r4构建完整连接结果的整个过程中，P1,P2,P3,P4每个页都需要被抓取两次。现在假设把r2和r3的构建顺序进行对调，即以r1,r3,r2,r4的顺序来构建完整的连接结果，那么，整个过程就会按照以下的顺序抓取页：首先抓取P1和P3进入内存，可以完成r1和r3对应的完整连接结果的构建，然后，把P1和P3驱逐出内存，抓取P2和P4进入内存，可以完成r2和r4对应的完整连接结果的构建。可以看出，整个过程中，P1,P2,P3,P4每个页只需要被抓取一次，节省了IO开销。因此，页抓取策略对于IO开销影响很大。
这里给出一个基于TPC-H表的连接实例，来说明DigestJoin可以比传统的连接算法取得更好的性能，这里选择归并排序连接算法作为传统连接算法的代表。TPC-H[TPC-H]是一个决策支持测试基准，它包含了一整套面向商业的即席查询和并发数据修改。TPC-H数据库共定义了8个基本表（如图[TPC-H]所示），包括PART、PARTSUPP、LINEITEM、ORDERS、SUPPLIER、NATION和REGION。这里考虑在两个TPC-H表CUSTOMER和ORDERS上面的连接，二者是通过键C_CUSTKEY进行连接的：
FROMCUSTOMER,ORDERS
图[TPC-H]TPC-H数据库模式
根据TPC-H的数据库模式，一个CUSTOMER表的摘要表的大小，大约是CUSTOMER表大小的6%，一个ORDERS表的摘要表的大小，大约是ORDERS表大小的9%。假设CUSTOMER表和ORDERS表分别包含10000和5000个页。
首先考虑采用传统的归并排序连接算法，执行CUSTOMER表和ORDERS表的连接，并假设内存容量为20个页。由于归并排序连接算法包含了两个阶段，即归并排序阶段和连接阶段，因此，代价计算方法如下：
（1）归并排序阶段的代价：首先考虑较小的ORDERS表。在进行归并排序时，由于ORDERS表的大小远远大于内存容量，无法一次性放入内存，因此，需要把ORDERS表进行分段，把每个分段调入内存，采用内存排序算法对分段进行排序，然后把排序后的分段写入到外部存储设备中（磁盘或闪存），得到排序后的若干个初始归并段。由于内存容量为20个页，因此，每个分段的大小也是20个页，这样才能够保证把每个分段一次性放入内存进行排序。因为，ORDERS表一共有5000个页，每个分段大小是20个页，因此，这里一共可以得到ORDERS表的250个分段。
可以看出，得到初始归并段的过程，需要把ORDERS表的所有未经排序的元组都读入内存一次，然后再把排序后的元组都写入到外部存储设备中一次，因此，得到初始归并段的代价是2*5000=10000次IO。
得到初始归并段以后，就开始了初始归并段的合并过程。对于ORDERS表而言，一共有250个初始归并段（每个初始归并段包含20个页），内容容量为20个页，每个内存页被分配一个初始归并段使用，因此，一次只能对20个初始归并段进行合并，即从每20个初始归并段合并得到一个归并段，一共可以得到13个归并段（除了最后一个归并段只包含200个页以外，其他每个归并段都包含400个页），在归并的过程中，需要一边合并一边把合并结果写入到外部存储设备中。第一趟归并过程需要把ORDERS表的所有250个初始归并段的元组都读入到内存中一次，然后把合并后的归并段写入外部存储设备一次，因此，第一趟归并过程的代价是2*5000=10000次IO。
然后开始执行第二趟归并，内存容量为20个页，每个内存页被分配一个归并段使用，由于当前只有13个归并段，只需要13个内存页用来执行归并过程，因此，可以在这一趟内完成对所有归并段的合并操作，并且一边合并一边把结果写入到外部存储设备中。第二趟归并过程需要把ORDERS表的所有13个归并段的元组都读入到内存中一次，然后合并后的归并段会被写入外部存储设备一次，因此，第二趟归并过程的代价是2*5000=10000次IO。
可以看出，对于ORDERS表而言，从原始表得到排序后的表的代价是，得到初始归并段的代价再加上两趟归并操作的代价，即10000+10000+10000=30000次IO。同理，对于CUSTOMER表而言，需要一次得到初始归并段的开销和三趟归并的开销，即4*2*10000=80000次IO。因此，归并排序阶段，对CUSTOMER表和ORDERS表排序的总开销是110000次IO。
（2）连接阶段的代价：CUSTOMER表和ORDERS表经过排序以后，就可以执行连接操作，只需要把两个表顺序地读入内存执行连接输出结果即可，因此，连接过程，两个表只需要读入内存一次，开销是10000+5000=15000次IO。
综上所述，采用传统的归并排序连接算法时，CUSTOMER表和ORDERS表的连接代价是归并排序阶段代价与连接阶段代价之和，即110000+15000=125000次IO。
现在假设采用DigestJoin执行CUSTOMER表和ORDERS表的连接。在DigestJoin算法的第一个阶段，即得到摘要连接结果的阶段，需要首先分别从两个表投影得到各自的摘要表，然后在两个摘要表上采用传统连接算法（这里采用归并排序连接算法）进行连接。因此，DigestJoin算法的第一个阶段的代价计算方法如下：
因此，DigestJoin算法的第一个阶段（即生成摘要连接结果）的总共代价是16050+7350=23400次IO。因此，只要DigestJoin算法的第二个阶段（构建完整连接结果）的IO少于101600（即125000-23400）次，DigestJoin算法的性能就要好于传统的归并排序连接算法。
从上面的论述可以看出，DigestJoin算法的第二个阶段（即构建完整连接结果阶段）的代价，直接关系到DigestJoin算法是否可以比传统连接算法获得更好的性能。DigestJoin算法的第二个阶段的核心问题就是页抓取问题，即如何合理调度页抓取顺序，从而用最小数量的页访问，就可以读取连接结果中涉及到的所有元组。
为了更好地分析页抓取问题，这里把该问题建模为图问题。一个连接图，表示了连接结果中所涉及的页之间的关系。连接图被定义为一个无向的二分图G=（V1∪V2,E），其中，V1和V2分别表示来自两个原始表的页的集合，V1内部各顶点之间不存在边，V2内部各顶点之间也不存在边，只有V1中的顶点和V2中的顶点这二者之间才会存在边。表示了连接结果所涉及的“页对”的集合。对于每条边(va,vb)∈E，表示存在一个属于页va上的元组，它可以和属于页vb上的元组在连接属性上发生匹配。这个连接图可以用来动态地表示剩余需要抓取和连接的页。一条边(va,vb)会被从E中删除，如果va和vb已经被抓取到内存，并且相应的元组已经完成连接。一个顶点v会被从G中删除，如果该顶点的出度变为0。
图[DigestJoin](a)给出了一个连接图的实例，其中，顶点1和2代表了来自同一个表的页，而顶点a,b,c则代表了来自其他表的页。边(1,a)表示页1上面有个元组，可以和页a上面的元组发生连接。
图[DigestJoin]DigestJoin算法的连接图和转换后的权重图
一个页抓取的过程，就等价于把所有的边都从连接图中移除的过程。正如之前描述的那样，一条边会被移除，当且仅当相应的页会被抓取到内存（从而构建相应的最终连接结果）。因此，一个最优的页抓取顺序，就是一个从图中删除所有边的顺序，并且要具有最少的页访问次数。
下面将说明页抓取问题是一个NP问题，为了阐述该问题的复杂度，这里将采用下面的思路：
接下来将说明页抓取问题是个NP问题。通过上面这种转换以后，页抓取的顺序就等价于在权重图中对各个顶点遍历一遍。遍历过程所需要抓取的页的总数，就是遍历路径上各条边的权重之和。因此，页抓取问题就被转换成“在一个图中寻找一个代价最小的路径的问题”，即哈密顿路径问题。Merrett等人[MerrettKY81]已经证明，在权重图中寻找一个哈密顿路径是一个NP问题。因此，可以判定页抓取问题也是一个NP问题。
上面已经证明了，页抓取问题是一个NP问题。对于NP问题，通常可以采用启发式算法得到近似最优解。如果内存可以容纳所有的以连接图形式表示的摘要连接结果，就可以找到一种比较好的启发式方法来遍历图中的所有边。启发式算法[ChanO97][Omiecinski89]的基本思想是：
首先，选择一个关于某个顶点的子图，这个子图包含了该顶点所有相邻的边，并且需要最少地抓取页。换句话说，可以在当前的连接图中检查所有的子图，并明确两个方面的内容：（1）确定是否每个子图都包含了这个子图中的所有顶点的所有边；（2）计算有多少个顶点不在内存中。
通过上述方法，就可以每次选中相应的顶点，并把其对应的闪存页抓取入内存，完成连接结果构建。
上面描述的是内存可以容纳连接图的情形，但是，往往在实际应用中，连接图都比较大，无法一次性放入内存，这时，就需要更加复杂的处理机制，关于这个问题，可以参考Li等人[LiOXCH09]的解决方案，这里不再细述。
本章内容首先介绍了NSM、DSM和PAX页布局模型，分别描述了各种模型的存储原理，并比较了三种模型的特性；然后，介绍了连接索引和Jive连接算法，许多面向闪存的查询连接操作优化算法都借鉴了这两者的思想；接下来，介绍了基于PAX的RARE连接算法以及基于PAX模型和连接索引的FlashJoin方法；最后，介绍了一种摘要连接算法DigestJoin，该算法把R和S的连接过程分成两个阶段来执行，第一阶段得到摘要连接结果，第二阶段构建完整连接结果，DigestJoin算法的IO代价收益，主要来自第一个阶段较小的摘要表和第二个阶段的随机读操作。