并行数据库系统并行数据库系统1 并行数据库概述并行数据库系统是在并行机上运行的具有并行处理能力的数据库系统，是数据库技术与并行计算技术结合的产物。

1.1 并行数据库系统的目标：1．高性能。

通过将数据库在多个磁盘上分布存储，利用多个处理机对磁盘数据进行并行处理，解决I/O 瓶颈问题。

通过开发查询间并行性、查询内并行性以及操作内并行性，提高查询效率。

2．高可用性。

可通过数据复制来增强数据库的可用性，当一个磁盘损坏时，该盘上的数据在其他磁盘上的副本仍可供使用。

3．可扩充性。

系统通过增加处理和存储能力而平滑地扩展性能的能力。

● 线形伸缩比：是指任务扩大N 倍、系统处理和存储能力也扩大N 倍时系统性能不变，即： 小任务在小系统上的运行时间与大（N 倍）任务在大系统上的运行时间之比为1。

●线形加速度比：是指任务不变、系统处理和存储能力扩大N 倍时系统性能也提高N 倍，即： 小系统上执行一个任务的时间与大（N 倍）系统上执行同一个任务的时间之比为N 。

1.2 支持并行数据库的并行结构1.2.1 共享内存（SM ）并行结构………图1.1 SM 结构并行计算机（负荷比较均衡、成本高、可用性不是很好）1.2.2 共享磁盘（SD ）并行结构……图1.2 SD 结构并行计算机（成本低、可扩充性好、可用性强。

实现起来比复杂）1.2.3无共享资源（SN）并行结构………图1.3 SN 结构并行计算机（成本低、可伸缩性与可用性高。

实现复杂、节点负荷难均衡）1.2.4 三种并行结构比较表1.1 三种并行结构比较2 并行数据库的并行查询处理技术顺序执行计划：SP（Sequential plan）并行执行计划：PP（Parallel plan）对于查询Q，若某个并行执行计划PP与Q的一个顺序执行计划SP对应于相同的操作树，则称PP 为SP的一个并行化方案，而由顺序执行计划SP得到的某个PP的过程称为并行化。

例：求每个部门职工的平均工资，并按平均工资升序排列。

SELECT DEPTNUM A VG（SAL）A VGSALFROM EMPGROUP BY DEPTNUMORDER BY A VGSAL；这里，分组和排序可以并行（流水线式）。

2.1 并行粒度并行粒度指的是查询执行的并行程度，可分为四种：（1）事务间并行性。

是粒度最粗也是最容易实现的并行性。

由于这种并行性允许多个进程或线索同时处理多个用户请求，因此可以显著增加系统吞吐量，支持更多的并发用户。

（集中式数据库也这样做）（2）查询间并行性（也就是事务内并行性）同一事务内的不同查询如果是不相关的，它们并行执行必将提高效率，但是，同一事务内的查询如果是相关的，它们并行执行比较复杂，系统必须进行相关性控制。

（3）操作间并行性（也就是查询内并行性）同一查询内的不同操作往往可以并行执行。

考虑一条SQL查询语句可以分解成多个子操作，有多个处理机执行。

例如下列查询：SELECT DEPTNUM ，EMPNUMFROM DEPT，EMPWHERE DEPT.DEPTNUM = EMP.DEPTNUMGROUP BY DEPTNUMORDER BY DEPTNUM；可以分解为扫描DEPT 表和EMP表，对两表进行结合，对结合结果排序以及分组和输出五个子任务。

前一操作的输出即是下一操作的输入。

如果后一操作等待前一操作产生一定量的输出后（而不必等待前一操作执行完毕）即可在另一处理机上开始执行，这种并行方式称为垂直并行或流水线并行。

（4）操作内（intra-Operation）并行性操作内并行性的粒度最细，它将同一操作（如扫描操作、合并操作、排序操作等）分解成多个独立的子操作，由不同的处理机同时执行。

事务（Transation）事务内事务间查询（Query）查询内查询间操作（Operation）操作内操作间并行粒度细粗图2.1 四种并行粒度2.1.1 并行化形式水平并行化（独立并行化，Independent Parallelism）和垂直并行化（流水线并行化，Pipelining Parallelism）OP1OP1OP2 OP2(a) 水平并行化（b）垂直并行化图2. 2. 并行化的两种形式如果两个操作OP1、OP2无相互依赖关系，则称这两个操作相互独立。

水平并行化指的是互相独立的多个操作或者一个操作内互相独立的多个子操作分别由不同的处理机并行执行的形式。

如果操作OP2直接依赖于OP1，并且OP2必须等待OP1处理完所有元组后方可开始执行，则称OP2以阻塞方式直接依赖于OP1；如果OP2无需等待OP1执行完毕即可在另一处理机上开始执行，则称OP2以流水线方式直接依赖于OP1。

垂直并行化则是指存在流水线方式依赖关系的操作分别由不同处理机并行执行的形式。

例如，排序操作、扫描操作由不同的处理机并行执行就是水平并行化的实例。

排序排序排序……↓↓↓扫描扫描扫描……↓↓↓例如：扫描操作、排序操作、连接操作、分组操作由不同的处理机并行执行就是垂直并行优化的实例。

扫描↓排序↓连接↓分组由于关系代数的封闭性和数据操作的相对独立性，关系查询具有三种固有并行性，即操作间的流水线并行性、操作间的独立并行性以及操作内的独立并行性，这为关系代数的并行化提供了现实基础。

2.1.2 并行操作算法并行数据库操作算法的研究已经成为并行数据库系统近几年一个非常活跃的研究领域。

并行操作算法有并行结合算法、并行扫描算法、并行排序算法等。

由于结合操作是关系数据库系统中最耗时且最常用的操作，对并行结合操作的研究最多。

提出了基于嵌套循环的并行结合算法、基于合并扫描的并行结合算法、基于HASH的并行结合算法、基于索引的并行结合算法等。

一、基于嵌套循环的并行结合算法（S>>R）输入：R，S：待结合的两个关系；A：连接属性；P：处理机数输出：关系R 和S的结合结果（结合属性为A）方法：（1）把S均匀地分布到P个处理机，设S i是S在结点i上的子集合；（2）FOR I = 1 TO p DO （并行地）处理机i按照结合属性值排序S iEND DO ；（3）在R所在的处理机上，对R按结合的属性排序，再以流水线方式向P个处理机广播R的元组；（4）FOR i = 1 TO p DO （流水线方式并行的）处理机i 以流水线方式接收R的元组；对磁盘上的S中元组和内存中R的元组结合、输出；ENDFOR；该算法适合于S的元组数远远大于R的元组数（R元组数较少）图 2.3 R与S基于嵌套循环的并行结合示意图图2.4 一次哈希与排序并行结合图二、基于排序的并行结合算法基于排序的并行结合算法由两个阶段组成：排序阶段和结合阶段。

在排序阶段，它按照结合属性的值排序每个结合关系；在结合阶段，完成两个排序关系的结合。

输入：R，S：待结合的两个关系。

A：连接属性P：处理机数H：HASH函数输出：关系R和S的结合结果（结合属性为A）方法：（1）使用HASH函数在P个处理结点间分布R和S的元组，设S i和R i是S和R在结点i上的子集：（2）FOR i = 1 TO p DO（水平并行地），处理机i排序R i和S iENDFOR；（3）i = 1 TO p DO（水平并行地），结点i完成R i和S i的结合输出R和S的结合结果ENDFOR；理论和实验结果表明，当两个结合关系的元组数相差较小时，该算法的效率高于前一个算法。

二、基于二次HASH的并行连接算法通过一个定义在结合连接属性上的HASH函数把两个结合关系分解为P个子集合，然后使用P个处理机并行地完成结合操作。

输入：关系R和S：HASH函数H1和H2，结点数P，子集合数M。

输出：关系R和S的连接结果。

（1）使用H1把R划分为M个子集合，HASH值为i的元组送入子集合R i，并存储到所有可用的磁盘；（2）使用H1把S划分为M个子集合，HASH值为i的元组送入子结合Si ，并存储到所有可用的磁盘；（3）FOR I = 1 TO M DO（并行地）使用H2把R i分布到p个处理结点，在每个结点的内存中建立R i元组的HASH表；使用H2以流水线方式向p个处理结点发送S i的元组；FOR J = 1 TO p DO （并行地）结点j用收到的S i的元组匹配R i的HASH表，进行S i和R i的结合；（4）输出R和S的结合结果。

算法中的M应该充分大，以减少R的子集合对应的HASH表超过可用内存容量的概率。

实验表明，使用并行数据操作算法实现查询的并行处理可以充分地发挥多处理机的并行性，从而改善关系运算的效率，提高查询处理的速度。

R SHASH1HASH1R1R2R3… R m S1S2S3… S mHASH2HASH2P1P2P3… P p P1P2P3… P pR1R11R12... R1p S1S11S12 (1)R2R21 R22... R2p S2S21S22 (2)┇┇R i R i1 R i2… R ip S i S i1S i2… S ip┇┇R m R m1R m2… R mp S m S m1S m2…S mp 在站点P1，对R的每一个M足够大，以保证每条链不太长。

子集R 均有一个键值表值。

2.1.3 并行查询优化并行数据库查询优化问题与顺序数据库查询问题有所不同。

在顺序数据库系统中，给定一个查询Q，查询优化算法只需找到Q的一个具有最小工作量的执行计划。

Q的最小工作量的执行计划可能具有很强的固有顺序性，难以并行化，因而不具有最小响应时间，在并行数据库系统中，查询优化的目标是寻找Q的具有最小响应时间的执行计划，执行计划的工作量不是第一重要的。

于是，在并行数据库系统中，需要新的查询处理算法和新的查询优化技术。

并行查询优化面临的两大困难：（1）执行计划搜索空间的庞大。

设SPLAN（Q）是查询Q的顺序执行计划空间，P是一个顺序执行计划，PARALLEL（P）是该计划的所有并行化方案，那么查询Q的并行执行计划空间PARALLEL（P）则可以由下述公式来表示：PPLAN（Q）= ∪PARALLEL（P）P∈SPLAN（Q）由此可见，依靠传统的穷尽方法进行并行查询优化是不现实的，应该提供某种启发式的方法对并行执行计划空间作剪裁以减少搜索空间的代价。

（2）执行时的某些系统参数比如CPU数目、内存大小在优化时是未知的。

有学者建议两阶段优化思想，即静态顺序优化和动态并行化。

●阶段1：在编译阶段，假设全部内存大小可为查询所用，利用传统查询优化策略得到最优顺序执行计划。

●阶段2：执行阶段，根据阶段1的顺序执行计划得到给定缓冲区大小和处理机数目条件下的最优并行化方案。

两阶段优化有效地解决了并行查询面临的两大困难，同时又降低了并行查询优化算法的复杂性。

问题：两阶段优化是否能保证并行执行计划的最优性。