第8章 闪存数据库查询处理

林子雨 1675

大数据之门

《闪存数据库概念与技术》

厦门大学数据库实验室  林子雨  编著

（本网页是第8章内容，全书内容请点击这里访问本书官网，官网提供本书整本电子书PDF下载）

第8章 闪存数据库查询处理

虽然固态盘可以快速改善那些侧重于随机读操作的应用的性能，但是，对于那些长时间运行大量分析查询的数据库应用而言，固态盘却无法立即改善其整体性能。数据库查询处理引擎在设计时主要考虑的是磁盘的随机和顺序I/O的速度失配问题，传统的各种算法都强调针对磁盘数据的顺序访问。而固态盘的随机读和顺序读操作几乎具有一致的高性能，因此，数据库的一些数据结构和算法，应该充分利用闪存的特性提高数据库性能。

在关系数据库中，查询操作往往涉及大量的连接操作，而连接操作需要大量的IO开销和计算资源，因此，许多研究都关注如何在闪存环境下对连接操作进行性能优化，从而可以充分利用闪存的特性，提高数据库查询的性能。比较典型的方法是，采用PAX页布局模型和连接索引，实现高效的闪存数据库连接操作。

本章首先介绍PAX页布局模型，然后介绍连接索引的概念，接下来介绍面向闪存数据库的、基于PAX和连接索引的RARE连接算法以及FlashJoin算法，最后，介绍采用类似连接索引理念的DigestJoin方法。

8.1    PAX页布局模型

有一些研究通过修改传统的查询处理技术，来充分利用闪存的快速随机读能力，从而达到提升数据库性能的目的。比如，文献[ShahHWG08][TsirogiannisHSWG09]的研究目标就是调查分析一些可以改进复杂数据分析查询性能的查询处理技巧，这类复杂查询主要出现在较少发生更新的商务智能和数据仓库应用中。这类研究主要采用PAX页布局模型和连接索引，来充分利用闪存特性，实现高效的数据库连接操作。

本节首先介绍与PAX模型紧密相关的NSM、DSM模型，然后介绍PAX模型。

8.1.1      NSM和DSM模型

下面将首先给出关于NSM和DSM模型的简要介绍，然后，将分别介绍NSM模型存储原理和DSM模型存储原理。

8.1.1.1       NSM和DSM模型概述

图[row-column-database]行式数据库和列式数据库示意图

图[row-column-database] 行式数据库和列式数据库示意图

传统上，数据库系统使用NSM(N-ary Storage Model)存储模型[RamakrishnanG00]，也就是采用一个基于页的存储布局，其中，元组或行会被连续地存储在页中(如图[row-column-database](a)所示)。在读取数据时，需要顺序扫描每个元组，然后，从中筛选出查询所需要的属性。如果每个元组只有少量属性的值对于查询是有用的，那么NSM就会浪费许多磁盘空间和内存带宽。采用NSM模型的数据库，通常被称为“行式数据库”，主要适合于小批量的数据处理，常用于联机事务型数据处理。

DSM(Decomposition Storage Model)存储模型（DSM）[CopelandK85]是在1985年提出来的，目的是为了最小化无用的I/O。DSM采用了不同于NSM的思路，DSM会对关系进行垂直分解，并为每个属性分配一个子关系，因此，一个具有n个属性的关系，会被分解成n个子关系，每个子关系只有当其相应的属性被请求时才会被访问。也就是说，它是以关系数据库中的属性或列为单位进行存储，关系的元组中的同一属性值被存储在一起，而一个元组中不同属性值则分别存放于不同的页中(如图[row-column-database](b)所示)。采用DSM的数据库通常被称为“列式数据库”，主要适合于批量数据处理和即席查询，它的优点是：（1）可以降低I/O开销，支持大量并发用户查询，其数据处理速度比传统方法快 100 倍，因为仅需要处理可以回答这些查询的列，而不是分类整理与特定查询无关的数据行；（2）具有较高的数据压缩比，较传统的行式数据库更加有效，甚至能达到五倍的效果。列式数据库主要用于数据挖掘、决策支持和地理信息系统等查询密集型系统中，因为一次查询就要得出结果，而不能每次都要遍历所有的数据库。所以，列式数据库大多都是应用在人口统计调查、医疗分析等行业中，这种行业需要处理大量的数据统计分析，假如采用行式数据库，势必导致消耗的时间会无限放大。

DSM的缺陷是，需要存储元组ID的额外存储开销以及执行连接操作时需要昂贵的元组重构代价。因此，在过去很多年里，主流商业数据库大都采用了NSM而不是DSM。但是，随着市场需求的变化，尤其是企业对分析型应用（比如数据仓库）的大量需求，从最近几年开始，DSM模型重新受到青睐，并且出现了一些采用DSM的商业产品和学术研究原型系统，比如Sybase IQ、ParAccel、Sand/DNA Analytics、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] 一个数据库关系的实例

EmpId Name Age Salary
1 Wang 35 4000
2 Lin 37 5000
3 Xue 42 4400

8.1.1.2       NSM模型存储原理

传统上，数据库元组都是遵循NSM模型[RamakrishnanG00]被顺序地存放到磁盘上。NSM会在磁盘页上连续存储元组。图[NSM]给出了表[row-column-database]中的关系采用NSM模型存储的效果。每个页包含一个页头、元组存储区域和页尾。每个新的元组，通常会被插入到从页头开始的第一个可用的自由空间里。页尾包括许多个槽（slot），每个槽都存储了一个指向元组存储区域的某个元组起始位置的指针。当在一个页内新增加一个元组时，元组可能是可变的长度，因此，一个指向新元组的起始位置的指针（偏移量），会被存储到从页尾开始的下一个可用的槽里面。从页尾开始的第n个槽当中的指针，就指向该页中的第n个元组。

图[NSM]采用NSM模型存储的一个实例

图[NSM] 采用NSM模型存储的一个实例

 

8.1.1.3       DSM模型存储原理

图[DSM]给出了表[row-column-database]中的关系采用DSM模型存储的效果。DSM[CopelandK85]把具有3个属性（除了EmpId）的关系R分解成3个子关系R1、R2和R3，每个子关系都包含两个属性。子关系会被存储到一个常规的页中，从而允许对每个属性进行独立的扫描。

图[DSM]采用DSM模型存储的一个实例

图[DSM] 采用DSM模型存储的一个实例

 

8.1.2      PAX模型

8.1.2.1       PAX模型存储原理

PAX（Partition Attributes Across）[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模型存储的一个实例

图[PAX] 采用PAX模型存储的一个实例

 

8.1.2.2       PAX、NSM和DSM的特性比较

一般而言，可以从两个方面比较NSM、DSM和PAX的特性，即元组之间的空间局部性和元组重构代价。首先，当元组之间具有较好的空间局部性时，可以最小化与CPU缓存(cache)相关的数据读取延迟，尤其是在循环扫描多个元组的一个属性子集的值时，空间局部性变得更加重要。其次，当元组重构代价较小时，可以使得与检索同一个元组的多个属性值相关的延迟达到最小化。

表[NSM-DSM-PAX]总结了NSM、DSM和PAX三种模型在元组之间的空间局部性和重构代价方面的特性。DSM提供了较好的元组间的空间局部性，因为它可以对属性值进行连续存储，而NSM则无法提供这种空间局部性，因为NSM以元组为单位进行连续存储，属于不同元组的同一个属性上的值会被分散存储到不相邻的位置。当顺序扫描一个属性值时，由于DSM可以提供更高的空间局部性，因此，DSM可以表现出很高的I/O性能和缓存性能。当查询访问每个关系中不到10%的属性时，DSM性能要好于NSM。但是，当执行一个涉及多个属性的查询时，数据库系统必须连接相关的子关系，从而重构元组。连接子关系所消耗的时间，会随着结果中包含的属性的数量的增加而增加。此外，DSM引入了明显的空间开销，因为，每个元组ID都需要被复制到任何一个子关系中。总体而言，DSM虽然具有较好的空间局部性，但是，元组的重构代价较高，抵消了由于空间局部性带来的性能收益，因此，当前主流的商业数据库系统都使用NSM而不是DSM。

但是，NSM在缓存行为方面的表现不尽人意。NSM会从每个磁盘页的起始位置开始连续存储元组，并且使用页末尾的“偏移量表”来定位每个元组的起始位置[RamakrishnanG00]。但是，绝大多数查询操作，只会访问每个元组的一少部分属性（或字段），这将导致无法获得最好的缓存性能。例如，对一个特定属性的顺序扫描时，将会发生缓存脱靶，每次访问一个属性值时，都需要访问一次内存。这个过程会把无用的数据加载到CPU缓存中，直接带来以下负面结果：（1）浪费了带宽；（2）无用的数据污染了缓存；（3）可能会强制替换未来可能用得到的数据，引发更多的延迟。

PAX是对NSM和DSM两个模型的巧妙结合，既能够提供空间局部性，也具备较小的重构代价。而且，在现有的DBMS上实现PAX，只需要修改页级别的数据操作代码。

表[NSM-DSM-PAX] NSM、DSM和PAX之间的特性比较

特性 NSM DSM PAX
元组之间的空间局部性 否 是 是
较低的元组重构代价 是 否 是

 

PAX相对于DSM的优势：和PAX模型相比，DSM模型存在两个明显的局限性。首先，传统的关系数据库引擎的许多组件，比如存储层、IO子系统、缓冲池、恢复系统、索引和运算符等，都被设计成在固定大小的页上执行操作。因此，DSM模型会涉及到所有这些组件，需要对这些组件进行重新设计。但是，PAX模型只需要重新实现存储层（负责从页中读取数据），因为，在PAX模型中，只有页的组织方式和传统不一样，而页的内容则没有发生变化。其次，采用DSM模型的列式存储，可能需要多个IO来更新一个行中的多个列。而采用PAX模型的时候，只需要一个IO就可以完成对一个行中的多个列的更新，因为，一个行中的所有的列都存储在相同的页内。

PAX相对于NSM的优势：采用NSM模型时，对于一个只需要一部分列的查询而言，必须扫描所有的列。PAX基于列的布局，为不同列的属性值之间提供了物理上的隔离，把同列的属性值都放置在相同的迷你页内，就可以允许一个操作只需要访问查询所涉及的那些属性，主要是通过在迷你页中“寻址”来实现。当从一个迷你页跳到下一个迷你页的寻址时间，要小于读取无用的迷你页的时间的时候，那么，执行随机读就会获得更好的性能。另外，虽然PAX的磁盘访问模式是无法和NSM进行区分的，但是，它确实改进了内存带宽需求。对于一个常规的扫描器而言，通常会从磁盘中访问完整的页，因此，PAX对磁盘带宽不会产生影响。但是，一旦一个页已经进入了内存，PAX就允许CPU只去访问查询所涉及的那些迷你页，这就减小了内存带宽需求[AilamakiDH02]。

8.1.2.3       PAX模型在闪存上可以发挥更好的性能

企业磁盘驱动器可以以较高的性能顺序地读取磁盘页，通常的速度为100MB/s。同时，由于磁盘存在机械部件，磁盘中的寻址操作代价比较高，一个较短的寻址往往也会消耗3-4ms的时间。在采用PAX模型时，收益主要来自于跳过一些无用的迷你页，到达查询所需要的迷你页，只读取查询需要的数据。因此，要想获得收益，必须要求跳过无用的迷你页所节省的读取无用页的开销，必须大于由于跳过无用页而引起的磁盘寻址开销。就这个方面而言，在磁盘中采用PAX模型不会获得收益，而在闪存固态盘中采用PAX模型可以获得很大的收益：

第一，在磁盘中采用PAX模型不会获得收益。对于在磁盘上跳过迷你页的一个寻址而言，至少要一次跳过300KB-400KB(100MB/s*3-4ms)的迷你页，才可以获得收益，也就是说，在磁盘中采用PAX模型时，需要把一个迷你页的大小设计为300-400KB。但是，采用PAX模型时，磁盘中的一个页包含多个迷你页，如果一个迷你页都已经达到300KB，那么，一个页的大小会达到好几个MB。但是，对于一个关系型DBMS而言，在设计页的大小时，会综合考虑诸多因素，比如缓冲池尺寸、缓冲区命中率、更新频率和每页的算法开销等。而在考虑了上述这些因素以后，大多数关系型DBMS往往都倾向于使用更小的页，通常是8KB或者64KB，而不是几个MB。因此，在磁盘中采用PAX模型，不会为关系型DBMS带来性能收益。

第二，在固态盘中采用PAX模型可以获得很大的收益。从上面论述可以看出，PAX模型对于磁盘而言，没有改进读性能，但是，在闪存上却可以获得明显的性能收益。闪存是一个纯粹的电子设备，不包含任何机械部件，因此，闪存上的寻址开销很小，随机读和顺序读操作几乎具有相同的高性能。假设一个闪存存储设备具备28MB/秒的顺序读带宽和0.25ms的寻址时间，那么，它只要跳过7KB（28MB/s*0.25ms）的迷你页即可。因此，一个页的大小就只需要32KB-128KB，这恰好是当前许多DBMS中采用的数据库页的大小。因此，在闪存上采用PAX模型是可行的。

此外，在固态盘上，PAX和更快的寻址时间相结合，允许只读取查询所需要的那些列，因此，既保留了现有的NSM的功能，也具备了DSM较高的读效率。而且，内存中的数据传输单元，可以小到32-128B，而一个数据库页通常是8KB到128KB，固态盘的最小传输单元是512B到2KB，这就允许我们可以选择性地读取常规页的一部分，减少了读操作数量。

 

8.2    连接索引和Jive连接算法

8.2.1   概述

两个关系R1和R2之间的连接索引，包含了一系列元组“标识对”，表示为<t1,t2>，其中，t1表示来自关系R1的元组的ID，t2表示来自关系R2的元组的ID，并且t1和t2之间在连接条件上是匹配的，即t1和t2可以发生连接操作成为连接结果的一部分。可以把连接索引看成是一个关系，用J表示。并且假设连接索引是根据t1或t2进行排序的，为了不失一般性，可以假设根据t1进行排序。

在许多情形下，采用连接索引的连接算法可以比最好的即席连接算法（比如混合哈希连接算法[DeWittKOSSW84]）获得更好的性能。Patrick Valduriez[Valduriez87]在1987年设计了使用连接索引的连接算法，这个算法可以很简单地实现，而且对于选择性连接非常有效。但是，对于Valduriez算法而言，当输入关系的大小大于内存时，需要对其中一个关系执行多趟扫描。因此，就性能而言，Valduriez的算法可能导致许多重复的IO，有时候只为了访问一少部分元组就需要访问整个块。而且，相同的块可能会被多次读取。

Li等人在1999年提出了针对Valduriez的算法的改进算法——Jive(Join Index with Voluminous relation Extensions)连接算法[LiR99]。Jive连接算法会对第二个输入关系的元组ID根据值域进行分区，然后单独处理每个分区。Jive算法的特性包括：

  • 所有的IO操作都是顺序执行的；
  • 一个输入关系的块会被读入，当且仅当它包含了一个参与连接的记录；
  • 索引连接只被读取一次；
  • 在内存容量够大的情况下，可以只对每个输入关系执行一次扫描；
  • 唯一需要存储的中间结果就是元组ID，通常是很小的。

Jive算法具有较好的特性是因为连接结果使用了垂直分区的数据结构。不过，Jive并没有对输入关系进行垂直分区，而是对连接结果进行垂直分区。存储连接结果的垂直分区数据结构，被称为“转置文件(transposed file)”[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-example-transposed-file] 连接结果的垂直分区

对连接结果采用了垂直分区方式以后，Jive连接算法就可以分成两趟输出连接结果，每一趟的连接结果都对应于来自其中的一个输入关系的属性，最后对两个垂直分区进行组合就可以得到最终连接结果。因此，进行垂直分区方式的一个明显优点是，不需要同时把全部元组都存放在内存中，而是在不同的阶段分次写入每个垂直分区，这样可以更好地利用内存。

8.2.2    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步：确定分区；
  • 第2步：生成一半连接结果JR1；
  • 第3步：生成另一半连接结果JR2。

（1）第1步：确定分区

选择x-1个R2元组ID作为分区元素，这些分区元素可以确定R2元组ID的x个分区。每个分区在内存中都有与其相关联的输出文件缓冲区，并且有与其关联的临时文件缓冲区。当缓冲区满的时候，每个缓冲区都会把内容刷新到一个相应的输出文件和磁盘临时文件中，然后接收新的记录。

（2）第2步：生成一半连接结果JR1

以顺序的方式扫描连接索引J和关系R1（注意：前面已经假设J是以R1元组的顺序存储的），由于连接索引J中包含了R1元组ID，因此，可以对J和R1中的元组进行匹配。在读取R1的过程中，如果决定读入关系R1的一个块，当且仅当这个块包含了连接索引中涉及的元组。在每次匹配时，首先需要确定一个发生匹配的元组所属的分区，这个可以根据R2元组的ID来判定，因为在第1步中就是根据R2元组ID来分区的，连接索引J的每个条目都是一个元组标识对<t1,t2>，根据属于关系R2的t2就可以判定t1属于那个分区。在确定一个发生匹配的元组所属的分区以后，就可以把关系R1中ID为t1的元组中被连接结果所需要的属性，写入到内存中为这个分区准备的缓冲区文件中。同时，发生匹配的R2元组ID会被写入到为这个分区准备的临时文件缓冲区中。当连接索引J都已经读取完毕的时候，所有的文件缓冲区都被刷新到磁盘上，为文件缓冲区分配的内存被回收重新分配。在完成第2步以后，已经生成了一半的连接结果，即JR1。JR1的分区会被连接到一个文件中。同时会生成一个临时文件，在下面的步骤3中被用来生成另一半连接结果JR2。

（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的某个块根本不会包含参与连接操作的元组，可以不用读取这个块。因此，如果输入关系中只有一少部分参与了连接操作，这种方式可以让连接算法获得更好的性能。

8.2.3   Jive连接算法的一个实例

为了更好地理解Jive连接算法，这里给出一个实例。如图[Jive-example]所示，两个关系R1和R2分别是Employee（见图[Jive-example](a)）和Management（见图[Jive-example](b)），其中，Employee关系包含了两个属性Worker和Department，分别表示雇员姓名和所在部门编号；Management关系包含了两个属性Department和Manager，分别表示部门编号和部门管理员。这里把每个关系中的元组出现的序号，作为元组ID，比如Employee关系中的第1个元组<Wang,D01>，它的元组ID就是1，第2个元组<Wang,D08>，它的元组ID就是2，依次类推。需要注意的是，为了对属性值相同的元组进行区分，从而便于跟踪连接算法的执行过程，这里为相同属性值添加了上角标。对Employee关系和Management关系在Department属性上进行连接操作，可以得到连接结果，如图[Jive-example](c)所示。

图[Jive-example]Jive连接算法的一个实例

图[Jive-example] Jive连接算法的一个实例

为了执行Jive连接算法，需要创建一个连接索引，如图[Jive-example](d)所示。连接索引的每个条目都是一个元组标识对<t1,t2>，并且t1和t2在连接条件上可以匹配。因此，对于Employee关系而言，第1个元组的部门编号是D01，元组ID是1，在Management关系中与之匹配的元组是第1个元组<D01,Liu>，元组ID是1，因此，可以得到连接索引的第1个条目是<1,1>。同理，对于Employee关系而言，第2个元组的部门编号是D08，元组ID是2，在Management关系中与之匹配的元组是第9个元组<D09,Qian>，元组ID是9，因此，可以得到连接索引的第2个条目是<2,9>。依此类推，可以得到连接索引的其他所有条目。

在整个构建连接索引的过程中可以发现，Management关系不存在部门编号为D07的元组，因此，Employee关系中的第9个元组<Qin,D07>，在Management关系中不存在与之匹配的元组。另外，Management关系中，部门编号为D06的元组有两个，分别是第6个元组<D06,Meng>和第7个元组<D06,Yu>，因此，Employee关系中的第6个元组<Lin3,D06>，在Management关系中存在两个与之匹配的元组，即第6个元组<D06,Meng>和第7个元组<D06,Yu>。

下面将演示按照Jive连接算法的三个步骤依次执行连接操作。

（1）第1步：确定分区

假设这里把Management关系（R2）分成三个分区，即x=3，并且假设每个缓冲区每次只能容纳一个元组。这里选择Management关系的元组ID值3和6作为分区点，即ID小于3的元组构成一个分区a，ID大于等于3并且小于6的元组构成一个分区b，ID大于等于6的元组构成一个分区c。

对于这三个分区而言，每个分区在内存中都有与其相关联的输出文件缓冲区，每个输出文件缓冲区满了以后，都会把缓冲区的内容刷新到输出文件JR1的对应分区中，因此可以得到三个输出文件分区JR1(a)、JR1(b)和JR1(c)，并且有与其关联的临时文件缓冲区，临时文件缓冲区满了以后，也会输出到临时文件对应的分区中，得到三个临时文件分区Temp(a)、Temp(b)和Temp(c)。随着连接操作的不断进行，缓冲区内容会不断输出到文件分区中，因此，这些文件分区JR1(a)、JR1(b)、JR1(c)、Temp(a)、Temp(b)和Temp(c)，会不断增加内容。在Jive算法的全部步骤都完成以后，可以对输出文件分区JR1(a)、JR1(b)、JR1(c)进行合并，得到一个输出文件JR1。

（2）第2步：生成一半连接结果JR1

以顺序的方式扫描连接索引J和关系Employee关系（R1），对连接索引和Employee关系中的元组进行匹配。为了生成一半的连接结果JR1，在Employee关系中找到与连接索引<t1,t2>的左边元素t1相对应的元组后，需要把该元组中出现在连接结果中的属性Worker的值写入到JR1中（实际上是首先写入输出文件缓冲区中，但是，最终会被合并成一个JR1文件）。比如，连接索引的第1个条目<1,1>的左边元素是1，因此，需要把Employee关系（R1）的第1个元组<Wang1,D01>的Worker属性值“Wang1”，作为部分结果输出。但是，需要注意的是，属性值“Wang1”必须输出到指定的输出文件分区中。

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)中）。

连接索引的第1个条目处理结束之后，继续扫描连接索引的第2个条目<2,9>，Management关系（R2）的元组标识符t2为9的元组，会被划分到分区c，因此，把t1=2对应的Employee关系（R1）的元组的Worker属性值“Wang2”写入到输出文件分区JR1(c)中。依此类推，继续顺序扫描连接索引的其他条目，并把相关的Worker属性值写入到对应的输出文件分区中。

最终，可以得到图[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

图[Jive-example-join-JR1] Jive连接算法的一半结果JR1

（3）第3步：生成另一半连接结果JR2

对于临时文件的分区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个<D01,Liu>和第2个元组<D02,Kuang>已经被读入到内存中。

接下来要把这些元组输出到连接结果文件分区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）的元组<D01,Liu>输出到JR2(a)中，Temp(a)中的第2个元组ID是2，因此，需要把内存中的第2个元组<D02,Kuang>输出到JR2(a)中，Temp(a)中的第3个元组ID仍然是2，因此，需要再次把内存中的第2个元组<D02,Kuang>输出到JR2(a)中，由此可以得到输出文件分区JR2(a)，如图[Jive-example-join-JR2]左边所示。

接下来，把临时文件分区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-JR2] Jive连接算法的另一半结果JR2

图[Jive-example-join-JR]Jive连接算法的最终结果

图[Jive-example-join-JR] Jive连接算法的最终结果

从上面实例的执行过程可以发现，Jive连接算法具备几个重要的特性：（1）算法只会读取参与连接的元组；（2）参与连接的元组只会被读取一次，即使该元组可能会参与多次连接运算；（3）对每个输入关系都只要进行一趟扫描。

8.3    基于PAX的RARE连接算法

文献[ShahHWG08]提出了面向闪存的、采用PAX模型和连接索引的RARE连接算法，该算法借鉴了Jive算法的设计思路，当输入关系太大无法一次性放入内存时，采用连接索引，先生成一半的连接结果，然后再生成另一半连接结果，并且，在扫描输入关系的过程中，不仅只会访问那些参与到连接操作中的列，而且只访问那些包含了连接结果所需要的值的迷你页，而不是访问所有的输入关系，以此来达到节省IO开销的目的，提高查询性能。需要注意的是，这种IO开销的节省需要额外的代价，即会增加寻址开销（从一个迷你页跳到另一个迷你页），并且需要计算连接索引。但是，RARE连接算法节省的IO开销，超过了额外的代价，因此，在理论和实际应用中都是可行的。

下面将以经典的Grace哈希连接算法作为参照对象，来讨论RARE连接算法在两种情形下的性能：（1）当存在足够的内存时，只需要对输入关系扫描一趟来计算连接；（2）当输入关系太大无法一次性放入内存时，需要多趟输入的时候。

需要指出的是，前面已经通过实例详细介绍了Jive连接算法的执行过程，由于RARE连接算法基本采用了Jive连接算法的设计思路，因此，下面只会介绍RARE连接算法的基本过程，不再给出实例演示。

8.3.1      一趟扫描

 

首先考虑采用NSM模型的Grace哈希连接算法。假设有两个参与连接操作的关系R1和R2，并且为R2建立的哈希表h可以一次性放入内存，即|h(R2)|<|M|，其中，h(R2)表示为R2建立的哈希表h的空间开销，|M|表示内存空间大小。这时，Grace哈希连接算法只需要对输入关系执行一次扫描，就可以计算得到结果，具体方法如下：

  • 首先，读取R2，并且在内存中为R2构建一个哈希表h；
  • 然后，读取R1，探测哈希表h，并且把结果输出到S中。

在上述过程中，所有的访问都是顺序执行的，因此，总体的IO代价的计算方法很简单，即| R1|+| R2|+|S|。

现在考虑采用PAX模型的Grace哈希连接算法，简称“Grace-PAX”。和Grace哈希连接算法相比，Grace-PAX连接算法可以取得更好的性能，主要是由于两个方面的原因：

第一，Grace-PAX需要更少的内存来执行一趟操作，因为，R2中只有与连接和投影相关的列才会被读入内存，并且可以满足|h(J2)|+|h(V2)|<|M|，其中，J2表示关系R2中参与连接的列，简称“连接列”，V2表示R2中会被投影到连接结果的列，简称“投影列”。比如，对于图[Jive-example]中Jive连接算法实例而言，在输入关系Management（R2）中（如图[Jive-example](b)所示），Department列就是参与连接的列，即J2，Manager列就是会被投影到连接结果的列，即V2。

第二，由于它跳过了不需要的列。因此，对于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代价。

1.       Read J2 and build hash-table;

2.       Read J1 and probe hash-table;

foreach join result <id1, id2> do

{

Read projected values of row id1 from V1;

Read projected values of row id2 from V2;

Write result into S;

}

算法[1-pass-RARE] 单趟RARE连接算法

8.3.2      多趟扫描

当内存空间有限，或者关系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+ε)趟RARE连接算法;
  • 第二种情况：J2和V2都无法一次性放入内存，这时，对于RARE算法而言，需要采用“2趟RARE连接算法”。

8.3.3      (1+ε)趟RARE连接算法

当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步中只需要在预留的空位置写入值即可。

和一趟排序不同的是，这里无法把V2一次性放入内存。一个简单的方法是，根据需要读取所需要的V2迷你页。但是，由于在第2步中采用J1的顺序对哈希表进行探测来生成连接索引，因此，在执行第3步的时候，采用这种方法可能会导致多次去读取同一个V2迷你页。为了避免多次读取同一个V2迷你页，RARE算法借鉴了Jive连接算法的思想，在第2步中把连接索引分区成多个分段，使得每个分段中引用到的V2迷你页，都可以一次性放入内存。前面介绍Jive连接算法的时候，已经知道，Jive连接算法[LiR99]会创建连接索引的排序分段，然后进行合并，从而以后可以顺序地获取R2的行。但是，这里需要指出的是，当采用闪存时，并不需要像Jive连接算法一样以顺序的方式访问V2，而是只需要确保所有针对单个页的数据值都可以从一个页读操作中获得。这主要是由于闪存和磁盘的不同特性决定的。Jive连接算法是面向磁盘设计的，因此，必须尽量执行顺序读取操作，所以，对R2的扫描都是顺序进行的。但是，对于闪存而言，顺序读取和随机读取操作具有同样高的性能，因此，就不需要对R2执行顺序读取操作。所以，为了确保所有针对单个页的数据值都可以从一个页读操作中获得，在步骤2当中，RARE连接算法简单地采用了R2的页号来对连接索引进行分区，从而，所有属于同一个页的R2行号（即id2）都会进入同一个连接索引分段。这样，在对某一个分段执行连接操作时，需要读取的R2的行就会属于同一个页，只需要一个页读操作，就可以读取到连接操作所需要的R2中的行。

在连接条件上发生匹配的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）和物化的开销。

1.       Read J2 and build hash-table;

2.       Read J1 and probe hash-table;

foreach join result <id1, id2> do

{

Read projected values of row id1 from V1;

/*S and I2 are both partitioned by id2*/

Write projected values into partition of S;

Write id2 into partition of I2;

}

3.       Read I2 and process it.

foreach partition of I2 do

foreach id2 in partition do

{

Read projected values of row id2 from V2;

Write values into partition of S;

}

算法[1+pass-RARE]  (1+ε)趟RARE连接算法

8.3.4      2趟RARE连接算法

算法[2-pass-RARE]显示了当J2和V2都无法一次性放入内存的情况下RARE算法的伪代码。在这种情形下，步骤1和步骤2和Grace哈希类似。RARE哈希会把两个表的连接列进行分区，从而，每个J2分段都可以一次性放入内存。在步骤3中，它为每个分段计算和物化连接索引<id1,id2>。

在步骤4中，RARE会把J1的分段合并成R1的顺序，并且读取需要的投影列V1。第5步和(1+ε)算法的第3步一样。需要注意的是，连接索引的尺寸是I2大小的两倍，因为，它包含了id1和id2。此外还要注意，RARE只会读取V1和V2中所需要的迷你页。

整个过程的代价构成如下：

  • 步骤1中，读取J2并进行分段后写入到存储介质上，需要一次读取（IO开销是|J2|）和一次写入操作（IO开销是|J2|）；
  • 步骤2中，读取J1并进行分段后写入到存储介质上，需要一次读取（IO开销是|J1|）和一次写入操作（IO开销是|J1|）；
  • 步骤3中，需要读入J2的所有分段，总的IO开销是|J2|；同时需要读入J1的所有分段，进行哈希表探测，因此，整个过程需要的IO开销是|J1|。另外，写入连接索引JI的IO开销是2|I2|（因为连接索引的大小是I2大小的两倍）。
  • 步骤4中，需要读出和写入连接索引，IO开销是4|I2|；另外，需要从V1中读取需要的数据，IO开销是ơp1|V1|；把投影属性值写入S的IO开销是|S|，把id2写入I2的开销是|I2|。
  • 步骤5中，读取I2的IO开销是|I2|，另外，需要从V2中读取需要的数据，IO开销是ơp2|V2|；把这些值写入S的IO开销可以不用再次计算，因为在步骤4中已经计算一次。

因此，可以计算得到总共的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中所需要的页，只需要访问一次，而不是三次。右边是来自对连接索引的多次读取和物化的额外代价。

1. Read J2 and partition it (hash on join value);

2. Read J1 and partition it (same hash function);

3. Compute JI;

foreach partition p of J2 do

{

Read partition p and build hash-table;

Read partition of J1 and probe hash-table;

foreach row in join result do

Write id1,id2 in JI partition;

}

4. Merge partitions of JI on id1;

foreach join result <id1,id2> do

{

Read projected values of row id1 from V1;

/*S and I2 are both partitioned by id2*/

Write projected values into partition of S;

Write id2 into partition of I2;

}

5. Read I2 and process it.

foreach paritition of I2 do

foreach id2 in partition do

{

Read projected values of row id2 from V2;

Write values into partition of S;

}

算法[2-pass-RARE] 两趟RARE连接算法

8.4    基于PAX模型和连接索引的FlashJoin

Tsirogiannis等人提出的FlashJoin连接算法[TsirogiannisHSWG09][GraefeHKSTW10]，也是一种专门针对闪存固态盘设计的数据库连接算法，与RARE类似，也都采用了连接索引和PAX模型，在此基础上，作者又实现了FlashScan，这是一个扫描操作，它只会从固态盘中读取那些参与到一个查询中的属性。FlashScan在从一个指定的行中抓取额外的属性之前，会先对谓词进行分析，因此，可以进一步减少数据读操作的数量。

FlashScan充分利用了固态盘的较小的传输单元，然后，只需要读取那些查询所需要的属性的迷你页。假设有一个不包含选择谓词的扫描，它要投影出关系的第1列和第3列。对于每个数据库页，FlashScan首先会读取第一个属性的迷你页，然后寻找第三个迷你页并且读取。接下来，它会再次寻找下一个页的第一个迷你页，然后寻找第三个迷你页……。这个过程会一直持续，直到扫描完整个关系，这就会导致一个随机的访问模式。总体而言，每次寻找都会导致一个随机读操作。而闪存固态盘的随机读操作和顺序读操作一样，具有很高的性能，因此，FlashScan可以获得很高的性能。

有了FlashScan以后，就可以高效地抽取需要的属性，在此基础上，作者进一步提出了FlashJoin（如图[FlashJoin-example]所示），这是一个通用的、流水线结构的连接算法，通过尽量推迟检索并且只检索那些需要的属性，可以最小化对关系页的访问。FlashJoin包括了一个二路连接（binary join）内核和一个单独的抓取（fetch）内核。多路连接会被分解成一系列流水线结构的二路连接。FlashJoin的连接内核只会访问连接所涉及的属性，并为每个连接节点生成连接索引形式的部分结果。FlashJoin的抓取内核，为会查询计划中的后续节点获取属性，并且会根据连接的选择性（selectivity）和可用的内存来选择不同的抓取算法。实验结果显示，FlashJoin不仅可以明显减少内存的使用数量，还可以减少查询中每个连接的I/O数量。

在仔细分析了一些算法和数据结构以后，Tsirogiannis等人还发现：

  • 对于排序算法而言，不需要对算法做任何改变，就可以直接从固态盘中受益；
  • 对于汇总操作而言，不会从固态盘中受益；
  • 可以利用闪存的快速随机读，来加速关系查询处理中的选择、投影、连接操作。

图[FlashJoin-example]采用FlashJoin时的三路连接实例

图[FlashJoin-example] 采用FlashJoin时的三路连接实例

8.5    DigestJoin

8.5.1      概述

传统的连接算法，在不存在索引的情形下，算法的目的是为了最小化寻址操作的数量，因为，这些算法是针对磁盘设计的，磁盘存在机械部件，寻址开销很大，减少寻址操作可以有效提升连接算法的整体性能。但是，在闪存数据库系统中，最小化寻址开销并不会带来明显的收益，因为，闪存的随机读操作和顺序读操作具有同样高的性能。

为了充分利用闪存快速的随机读能力，Li等人[LiOXCH09]提出了一种摘要连接算法DigestJoin，假设参与连接的两个原始关系（或表）为R和S，该算法把R和S的连接过程分成两个阶段来执行：

  • 第一阶段：得到摘要连接结果。首先，把关系R和S的元组ID以及那些与连接操作相关的属性投影出来，投影得到的表称为“摘要表”，即分别得到关系R和S的摘要表digest_R和digest_S。摘要表的大小要比原始表小很多，可以减少后续的IO开销；然后，在较小的摘要表digest_R和digest_S上运行传统的连接算法（比如嵌套循环连接和哈希连接等），来生成“摘要连接结果”。摘要连接结果只包含了来自两个连接关系的元组ID和连接属性，可以最小化中间连接结果。可以看出，摘要连接结果和连接索引（参见“连接索引和Jive连接算法”）有些类似。
  • 第二阶段：构建完整连接结果。在摘要连接结果的基础上，DigestJoin算法会从原始表中加载完整的元组来生成最终的结果。在连接索引中，这就是经典的“页抓取问题”。

DigestJoin算法的IO代价收益，主要来自第一个阶段较小的摘要表和第二个阶段的随机读操作。在第一个阶段中，在较小的摘要表上进行连接可以节省很多后续的IO开销，尤其是可以节省连接过程中临时写入闪存的开销，由于闪存写操作往往会引起延后的擦除操作，因此，闪存写操作的减少同时也意味着需要更少的闪存擦除操作。在这个阶段，如果采用PAX存储模型，扫描原始表得到摘要表的过程会更加高效。采取PAX模型存储时, 在进行连接操作时，只需要读取参与连接操作的属性（列）值, 从而减少了数据的读取量，提高了读取的效率。此外，在PAX模型中，属于同一个属性的值都是存储在相邻的位置，因此，可以对数据进行连续读取，进一步降低了数据读取的代价。在第二个阶段，与摘要连接结果中的元组相关的、原始关系R和S中的元组，会分散在闪存的不同物理空间。因此，页抓取会引发大量随机读操作，这对于磁盘来说需要很大的IO开销，对于磁盘而言，这种随机读的开销甚至会超过第一个阶段节省的IO开销。但是，闪存具有很高的随机读性能，因此，页抓取引发的随机读操作，对于闪存而言，不会导致高昂的寻址开销。

8.5.2      算法代价分析

假设两个参与连接的关系为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进行连接的：

SELECT *

FROM CUSTOMER, ORDERS

WHERE CUSTOMER.C_CUSTKEY=ORDERS.C_CUSTKEY;

图[TPC-H]TPC-H数据库模式

图[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算法的第一个阶段的代价计算方法如下：

  • 从两个表投影得到各自的摘要表的代价：从CUSTOMER表和ORDERS表投影得到的摘要表的大小分别是600（即10000*6%）页和450（即5000*9%）页，构建这两个摘要表时，需要对两个表分别顺序扫描读入内存一次，然后选择出摘要表需要的属性，写入到外部存储设备一次，因此，构建两个摘要表的代价是10000+5000+600+450=16050次IO。
  • 在两个摘要表上采用传统的归并排序连接算法进行连接的代价：这里包括归并排序的代价和连接的代价。（1）归并排序的代价：在得到两个摘要表的初始归并段以后，两个摘要表都可以在两趟（得到初始归并段的一趟不算在内）内完成归并，因此，归并排序的代价是3*2*600+3*2*450=6300；（2）连接的代价：在连接阶段，需要把两个摘要表读入内存一次来执行连接，因此，连接阶段的代价是600+450=1050次IO。综上所述，使用DigestJoin算法执行两个摘要表的连接的总代价是：6300+1050=7350次IO。

因此，DigestJoin算法的第一个阶段（即生成摘要连接结果）的总共代价是16050+7350=23400次IO。因此，只要DigestJoin算法的第二个阶段（构建完整连接结果）的IO少于101600（即125000-23400）次，DigestJoin算法的性能就要好于传统的归并排序连接算法。

8.5.3      页抓取问题复杂度分析

从上面的论述可以看出，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算法的连接图和转换后的权重图

图[DigestJoin] DigestJoin算法的连接图和转换后的权重图

一个页抓取的过程，就等价于把所有的边都从连接图中移除的过程。正如之前描述的那样，一条边会被移除，当且仅当相应的页会被抓取到内存（从而构建相应的最终连接结果）。因此，一个最优的页抓取顺序，就是一个从图中删除所有边的顺序，并且要具有最少的页访问次数。

下面将说明页抓取问题是一个NP问题，为了阐述该问题的复杂度，这里将采用下面的思路：

  • 首先按照一定的方法，从连接图转换得到一个带有边权重的权重图；
  • 然后将说明，页抓取问题就相当于在权重图中采用最短路径遍历所有顶点的问题，该遍历问题已经被证明是一个NP问题，因此可以判定页抓取问题也是一个NP问题。

首先介绍如何从连接图中转换得到另外一个权重图。对于一个连接图G=（V1∪V2,E），可以为之构建一个相应的包含边权重的图。也就是说，连接图中的每条边，都会被转换成权重图中的一个顶点。因此，权重图中的，就代表了需要把va和vb抓取到内存中用来构建得到最终的连接结果。权重图中的每条边的权重，是两个连接操作之间在内存中交换页的代价。在内存中交换页是指，第一个连接操作结束后，进行第二个连接操作时，由于两个连接操作所需要的页可能不同，如果内存容量有限，就必须驱逐一些与第一个连接操作相关的页，把与第二个连接操作相关的页抓取到内存中，这就涉及内存中数据页的交换。图[DigestJoin](b)显示了图[DigestJoin](a)中的连接图对应的权重图。图[DigestJoin](b)中的顶点名称，都是用图[DigestJoin](a)中相应的边的名称来表示的，比如，图[DigestJoin](b)中的顶点1a表示图[DigestJoin](a)中的边（1,a）。现在讨论边的权重，假设内存只能最多同时容纳两个页，则边（1a,1b）的权重是1，因为，边(1a,1b)涉及了两个连接操作，第一个连接操作需要抓取页1和a，第二个连接操作需要抓取页1和b。当执行完第一个连接操作以后，内存中包含了页1和a，在执行第二个连接操作时，需要页1和b，1已经在内存中，b不在内存中，需要把一个新页b调入内存，但是，由于内存最多只能同时容纳2个页，因此，需要把页a驱逐出内存，把页b放入内存，发生了1个页的交换，边(1a,1b)的权重就是表示两个连接操作之间在内存中交换页的代价，因此，边(1a,1b)的权重就是1。同理，边(1b, 2a)的权重是2，因为，执行第一个连接操作需要页1和b，在执行第二个连接操作时，需要把1和b驱逐出内存，抓取两个新页2和a进入内存，内存中页交换的数目是2。

接下来将说明页抓取问题是个NP问题。通过上面这种转换以后，页抓取的顺序就等价于在权重图中对各个顶点遍历一遍。遍历过程所需要抓取的页的总数，就是遍历路径上各条边的权重之和。因此，页抓取问题就被转换成“在一个图中寻找一个代价最小的路径的问题”，即哈密顿路径问题。Merrett等人[MerrettKY81]已经证明，在权重图中寻找一个哈密顿路径是一个NP问题。因此，可以判定页抓取问题也是一个NP问题。

8.5.4      解决页抓取问题的启发式算法

上面已经证明了，页抓取问题是一个NP问题。对于NP问题，通常可以采用启发式算法得到近似最优解。如果内存可以容纳所有的以连接图形式表示的摘要连接结果，就可以找到一种比较好的启发式方法来遍历图中的所有边。启发式算法[ChanO97][Omiecinski89]的基本思想是：

首先，选择一个关于某个顶点的子图，这个子图包含了该顶点所有相邻的边，并且需要最少地抓取页。换句话说，可以在当前的连接图中检查所有的子图，并明确两个方面的内容：（1）确定是否每个子图都包含了这个子图中的所有顶点的所有边；（2）计算有多少个顶点不在内存中。

然后，满足第一个条件并且第二个条件的值最小的子图，会被选中。由于对一个连接图的所有子图进行枚举的代价很高，因此，一种近似的方法是，选择一个具有最少的“非驻留内存邻居”（即邻居顶点不在内存中）的顶点，并且它的所有邻居也会被一起选中。这种具有最少的“非驻留内存邻居”的顶点和它的所有邻居，一起构成一个“分段”。例如，在图[DigestJoin](a)的连接图中，对于顶点1而言，它有三个邻居a,b,c，因此，顶点1对应的候选分段是{1,a,b,c}，同理可以得到其他顶点对应的候选分段，因此，图[DigestJoin](a)中的候选分段包括：{1,a,b,c}、{2,a,c}、{a,1,2}、{b,1}和{c,1,2}。如果内存中还没有抓取放入任何页，此时，顶点1对应的分段{1,a,b,c}的非驻留内存邻居数目是3，即a,b,c，顶点2对应的分段{2,a,c}的非驻留内存邻居数目是2，即a,c，同理，分段{a,1,2}、{b,1}和{c,1,2}的非驻留内存邻居的数量分别是2,1,2。可以看出，应该选择顶点b调入内存，因为，顶点b对应的分段{b,1}具有最少的非驻留内存邻居数目（只有页1不在内存中），因此需要最少的页访问。现在假设一些页已经被抓取到内存中，比如c，那么应该选择顶点2或b，因为，这时顶点2和b都只有1个非驻留内存邻居，即分别是a和1。

通过上述方法，就可以每次选中相应的顶点，并把其对应的闪存页抓取入内存，完成连接结果构建。

上面描述的是内存可以容纳连接图的情形，但是，往往在实际应用中，连接图都比较大，无法一次性放入内存，这时，就需要更加复杂的处理机制，关于这个问题，可以参考Li等人[LiOXCH09]的解决方案，这里不再细述。

8.6    本章小结

本章内容首先介绍了NSM、DSM和PAX页布局模型，分别描述了各种模型的存储原理，并比较了三种模型的特性；然后，介绍了连接索引和Jive连接算法，许多面向闪存的查询连接操作优化算法都借鉴了这两者的思想；接下来，介绍了基于PAX的RARE连接算法以及基于PAX模型和连接索引的FlashJoin方法；最后，介绍了一种摘要连接算法DigestJoin，该算法把R和S的连接过程分成两个阶段来执行，第一阶段得到摘要连接结果，第二阶段构建完整连接结果，DigestJoin算法的IO代价收益，主要来自第一个阶段较小的摘要表和第二个阶段的随机读操作。

8.7    习题

  • 阐述PAX、NSM和DSM三种页布局模型的工作原理，并比较三者的特性。
  • 分析为什么PAX模型可以在闪存上发挥更好的性能。
  • 说明什么是连接索引及其作用。
  • 分析单趟RARE连接算法的代价。
  • 分析DigestJoin算法的主要IO代价收益来自那些地方。