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

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

通过将数据库在多个磁盘上分布存储，利用多个处理机对磁盘数据进行并行处理，解决过开发查询间并行性、查询内并行性以及操作内并行性，提高查询效率。

2.高可用性。

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

3.可扩充性。

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

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

线形加速度比：是指任务不变、系统处理和存储能力扩大N倍时系统性能也提高N倍，即: 小系统上执行一个任务的时间与大（1.2支持并行数据库的并行结构1.2.1 共享内存（SM ）并行结构图1.1 SM结构并行计算机（负荷比较均衡、成本高、可用性不是很好）I/O瓶颈问题。

通N倍）系统上执行同一个任务的时间之比为N。

图1.2 SD结构并行计算机（成本低、可扩充性好、可用性强。

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

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

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

DEP T.DEPTNUM = EMP .DEPTNUM1.2.4种并行结构比较SELECT DEPTNUM AVG (SAL ) AVGSAL FROM EMP GROU P BY DEPTNUM BY AVGSAL ;ORDER这里，分组和排序可以并行（流水线式）2.1并行粒度并行粒度指的是查询执行的并行程度，可分为四种:（1） 事务间并行性。

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

由于这种并行性允许多个进程或线索同时处理多个用户 （集中式数据库也这样做）(2)请求，因此可以显著增加系统吞吐量，支持更多的并发用户。

查询间并行性（也就是事务内并行性）同一事务内的不同查询 如果是不相关的，它们并行执行必将提高效率， 但是，同一事务内的查 (3)询如果是相关的，它们并行执行比较复杂，系统必须进行相关性控制。

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

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

例如下列查询:SELECT DEPTNUM ， EMPNUM FROMDEPT , EMPWHERE如果操作OP2直接依赖于OP1,并且OP2必须等待OP1处理完所有元组后方可开始执行，则称 以阻塞方式直接依赖于OP1;如果OP2无需等待OP1执行完毕即可在另一处理机上开始执行，则称 以流水线方式直接依赖于OP1。

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

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

例如: 例。

排序排序排序OP2 OP2扫描 扫描操作、 扫描 排序操作、 扫描……连接操作、分组操作由不同的处理机并行执行就是垂直并行优化 的实GROU P BY DEP TNUM ORDER BY DEPTNUM ;可以分解为扫描DEPT 表和EMP 表，对两表进行结合，对结合结果排序以及分组和输出五个子任务。

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

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

（4）操作内（intra-0peration ）并行性操作内并行性的粒度最细，它将同一操作（如扫描操作、合并操作、排序操作等） 子操作，由不同的处理机同时执行。

并行粒度（b ）垂直并行化图2. 2.并行化的两种形式如果两个操作OP 1、OP 2无相互依赖关系，则称这两个操作相互独立。

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

分解成多个独立的事务(Transation)查询（Query ） 操作(Op eration)事务内事务间查询内查询间操作内操作间图2.1 四种并行粒度2.1.1 并行化形式水平并行化（独立并行化,Inde pendent P arallelism ）和垂直并行 化（流水线并行化， Pip eliningP arallelism ) OP 10P 1 0P2（a ）水平并行化5S iS iR iS 2R 2—1 ----S 3R 3S PR p----—1 ----扫描排序J连接分组由于关系代数的封闭性和数据操作的相对独立性，关系查询具有三种固有并行性，即操作间的流水线并行性、操作间的独立并行性 以及操作内的独立并行性，这为关系代数的并行化提供了现实基础。

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 按照结合属性值排序SEND DO ;（3）在R 所在的处理机上，对 R 按结合的属性排序，再以流水线方式向P 个处理机广播R 的元组； （4） FOR i = 1 TO p DO （流水线方式并行的）处理机i 以流水线方式接收R 的元组； 对磁盘上的S 中元组和 内存中R 的元组结合、ENDFOR ;该算法适合于S 的元组数远远大于 R 的元组数（R 元组数较少）输出;S 2S 3S p图 2.3 R 与 S 基于嵌套循环的并行结合示意图 二、基于排序的并行结合算法基于排序的并行结合算法由两个阶段组成:排序阶段 和结合阶段 。

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

输入：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处理机ENDFOR ; 3） i = 1 TO结点 i完成 R i 和 S i 的结合 输出 R 和 S 的结合结果（ 4 ） 输出算法中的M 应该充分大，以减少R 的子集合对应的HASH 表超过可用内存容量的概率。

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

图 2.4 一次哈希与排序并行结合图TO p DO （水平并行地）， i 排序 R i 和 S ip DO （水平并行地） ，ENDFOR ;理论和实验结果表明，当两个结合关系的元组数相差较小时，该算法的效率高于前一个算法。

基于 二次 HASH 的并行连接算法通过一个定义在结合连接属性上的并行地完成结合操作。

输入:关系 R 和 S : HASH 函数 H 1 和 输出:关系 R 和 S 的连接结果。

使用 H 1 把 R 划分为1）2）3）HASH 函数把两个结合关系分解为 P 个子集合， 然后使用 P 个处理机H 2,结点数P ，子集合数M 。

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

从而改7并行数据库查询优化问题与顺序数据库查询问题有所不同。

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

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

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

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

设SPLAN （ Q ）是查询Q 的顺序执行计划空间，P 是一个顺序执行计划，PARALLEL （ P ）是该计划的 所有并行化方案，那么查询 Q 的并行执行计划空间 PARALLEL （ P）则可以由下述公式来表示：RmSmP pP l P pR i R11R12…R1pR 2R21 R22…R 2p1 1R i R i1 R i2 …R ip 1 1RmRm1Rm2…R mpS i S 11S12…S ip S 2S21 S22…S 2p1 1SS il S i2 …S ip1 1SmSm1Sm2…Smp2.1.3并行查询优化R i R 2 R 3S i S 2 S 3P l P 2 P 3P 2 P 3在站点P1,对R 的每一个 子集R 均有一个键值表值。

M 足够大，以保证每条链不太长。

P e SPLAN (Q )由此可见，依靠传统的穷尽方法进行并行查询优化是不现实的，应该提供某种启发式的方法对并行执 行计划空间作剪裁以减少搜索空间的代价。

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