数据库教学课件：第12章 并行数据库

第1２章并行数据库数据库中的并行性I/O并行查询间并行查询内并行操作间并行操作内并行并行数据库与分布式数据库数据库中的并行性数据可划分在多个磁盘上,导致并行I/O个别关系操作(如排序,连接,合计)可以并行执行数据可划分且每个处理器可对其划分部分独立操作查询可用高级语言(SQL,翻译到关系代数)表达使并行化更容易不同查询可并行执行并发控制处理冲突可见,数据库很自然地具有并行性数据库系统中的并行形式I/O并行查询并行查询间(Inter-Query)并行查询内(Intra-Query)并行操作内(Intra-Operation)并行操作间(Inter-Optration)并行流水线并行独立并行查询间并行查询/事务相互并行执行增加事务吞吐量;主要用于扩展(scaleup)事务处理系统以支持更大的每秒事务数.最容易支持的并行形式,特别是在共享内存并行数据库中,因为即使串行数据库系统也支持并发处理.在共享磁盘或无共享体系结构上的实现更复杂必须在处理器之间传送消息来协调封锁和日志登记.本地缓冲区中的数据可能已被另一处理器更新.缓存一致性(cache-coherency)得到保持—对缓冲区数据的读写必须找到数据的最近版本.查询内并行单个查询在多个处理器/磁盘上并行执行;对加速耗时查询很重要查询内并行的两种互相补充的形式:操作内并行–通过并行地执行每一个操作，如排序、选择、投影、连接等，来加快一个查询的处理速度。.操作间并行–通过并行地执行一个查询表达式中的多个不同的操作，来加快一个查询的处理速度.第一种形式在增加并行度时的伸缩性好,因为每个操作处理的元组数通常都多于查询内的操作数目Inter-QueryParallelism(1)SubsectionPiecesIntra-QueryParallelism(2)Intra-QueryParallelism(3)并行数据库物理组织与I/O并行I/O并行划分策略偏斜问题I/O并行通过将关系划分到多个磁盘来减少从磁盘检索关系所需的时间水平划分–关系的元组在多个磁盘间划分,每个元组只存储在一个磁盘上划分技术(磁盘数=n):循环(Round-robin)划分:将关系中的第i条元组送到第(imodn)号磁盘.散列划分:选择一个或多个属性作为划分属性选择值域为0..n-1的散列函数h令i

表示将散列函数h作用于元组的划分属性值得到的结果.则该元组送往磁盘i划分策略假定数据分布到n个磁盘：D0,D1,…,Dn-1三种基本的划分策略：轮转法(Round-robin)散列分布(Hashpartitioning)范围分布(Rangepartitioning)轮转法即均匀地在各个磁盘上分配元组的办法,对关系进行任意顺序扫描，将第i个元组送到标号为Dimodn的磁盘上元组在多个磁盘上平均分布，每个磁盘上具有大致相同数目的元组散列分布即基于划分属性将元组散列分布到各个磁盘中指定关系模式中的一个或多个属性为划分属性选定一个值域为{0,1,…,n-1}的散列函数将关系中的各个元组基于划分属性进行散列如果散列函数返回i，则把该元组放到磁盘Di中范围分布往每一个磁盘上分配连续的属性值范围选定一个划分属性A，形成划分向量:[V0,V1,…,Vn-2]

满足条件：若i<j，则Vi<Vj对关系进行如下分配：考虑元组t，t[A]=x如果x<Vo，则将t放置在磁盘D0中如果Vi≤x<Vi+1，则将t放置在磁盘Di+1中如果X≥Vn-2，则将t放置在磁盘Dn-1中例如,设划分向量为[5,11],则划分属性值等于2的元组将分到磁盘0,等于8的元组将分到磁盘1,等于20的元组分到磁盘2划分技术的比较考虑不同的划分策略对各类数据存取的支持全关系扫描：访问一个关系中的所有元组点查询：寻找在特定属性上有特定值的元组范围查询：找出给定属性的值处于指定范围的所有元组例SELECT*FROMaccount例SELECT*FROMbranchWHEREbranch-city=‘Perryridge’例SELECT*FROMaccountWHEREbalanceBETWEEN10000AND20000划分技术的比较循环划分:优点最适合顺序扫描整个关系的查询.所有磁盘具有几乎相等的元组数;因此各磁盘上的查询工作量是平衡的.缺点难以处理范围查询没有聚簇(clustering)–元组分散在所有磁盘划分技术的比较散列划分:

适合于顺序存取假设散列函数选的好,且划分属性形成键,则元组平均分布在各磁盘上于是各磁盘的存取工作量是平衡的.适合于划分属性上的点查询可只检查单一磁盘,使其他磁盘可用于其他查询.对划分属性的索引可局部于磁盘,从而使查找和更新更高效无聚簇,因此难以处理范围查询划分技术的比较范围划分:提供基于划分属性值的数据聚簇.适合于顺序存取适合于划分属性上的点查询:只需存取一个磁盘.对划分属性上的范围查询,可能只需存取一个或少数几个磁盘其它磁盘可用于其他查询.当结果元组来自一个或几个块时最好.如果需存取许多块,且仍从一个或几个磁盘取得,则磁盘存取中潜在的并行性被浪费这是执行偏斜的例子.划分技术的比较(总结)不同划分策略对数据存取的支持：都能很好地支持全关系扫描，如果分布均匀则在1/n时间内完成轮转法：点查询和范围查询的处理都很复杂散列分布：非常适合于基于划分属性的点查询

不适合于非划分属性上的点查询不适合范围查询范围分布：适合于划分属性上的点查询适合于划分属性上的范围查询在磁盘间划分关系如果关系只包含少量元组,可以放入单一磁盘块,则将该关系分配到单个磁盘上大关系最好在所有可用磁盘间划分如果关系由m

个磁盘块组成,且系统中有n

个可用磁盘,则该关系应该分配min(m,n)个磁盘偏斜问题元组在磁盘间的分配可能是偏斜的—即,某些磁盘上有许多元组,而另一些只有少量元组偏斜的种类:属性值偏斜某些值在许多元组的划分属性上出现所有在划分属性上值相同的元组被分配在同一分区中.范围划分和散列划分中可能发生划分偏斜对范围划分,一个坏的划分向量可能将过多元组分配到一个分区以及过少元组分配到其他分区对散列划分,只要选择好的散列函数就不太可能发生偏斜问题属性值偏斜划分偏斜轮转法无无散列分布有依赖于散列函数范围分布有依赖于划分向量偏斜问题偏斜导致性能的显著降低。随着并行度的提高，偏斜变成更加严重的问题划分中应设法避免或减小偏斜选择好的散列函数构造好的划分向量范围划分中处理偏斜为生成平衡的划分向量(假设划分属性是关系的键):对关系按划分属性排序按序扫描关系并构造划分向量如下.（如高考录取分数线，先排序，再定政策）每读出关系的1/n个元组,就将下一条元组的划分属性值就加入划分向量n

表示将构造的分区数如果划分属性有重复值,则可导致重复项或不平衡实际中还使用基于直方图的其他技术利用直方图处理偏斜从直方图可以相对直接地构造出平衡的划分向量假设在直方图的每个范围中一致分布直方图可通过扫描关系或者对关系元组抽样来构造利用虚拟处理器处理偏斜范围划分中的偏斜可以用虚拟处理器很好地处理:创建大量虚拟处理器(比如是实际处理器数目的10到20倍)用任何划分技术将关系元组分配到虚拟处理器以循环方式将每个虚拟处理器映射到到实际处理器基本思想:如果正常划分会导致偏斜,则偏斜很可能被分散到若干个虚拟分区偏斜的虚拟分区被分散到若干实际处理器上,于是分配变得平均了!比喻：8人分水果，先排排座，粗分到80篮子（虚拟人），然后把少数分得特多特少篮子，和多数均衡的篮子平分8人缓存相关问题必须保证两个处理器不会相互独立地同时更新相同的数据必须保证当一个处理器访问或更新数据时，该处理器在它的缓冲池中拥有该数据的最新版本缓存一致性协议共享磁盘系统的缓存一致性协议例:读/写一页之前,该页必须以共享/排他方式加锁.对页加锁时,该页必须从磁盘读出释放页锁之前,该页如果更新过则必须写到磁盘.存在更复杂但磁盘读写次数较少的协议无共享系统的缓存一致性协议是类似的.每个数据库页都有一个home

处理器.对页的读写请求都发往它的home处理器.（类似照顾老乡，能把缓存的读写操作比较固定地分散到各CPU）关系操作的并行处理我们讨论并行算法时假定:查询是只读的无共享体系结构n

个处理器P0,...,Pn-1,及n

个磁盘D0,...,Dn-1,其中磁盘Di

与处理器Pi关联.如果一个处理器有多个磁盘,可以简单地模拟成单个磁盘无共享体系结构可以在共享内存和共享磁盘系统上有效地模拟.因此无共享系统的算法可在共享内存或共享磁盘系统上执行.但是,可能需要一些优化并行排序假设关系初始地分布在磁盘D0，D1，…，Dn-1(不是按排序所基于的属性进行的范围分布)用处理器P0，P1，…，Pm（m<n）进行排序。基于范围分布的排序并行的外部排序-合并基于范围分布的排序步骤：采用范围分布策略，基于排序属性对关系进行重新分布，使得处于第i个范围的所有元组都送给处理器Pi，临时地存放在磁盘Di中每个处理器在本地对送给它的关系的分片进行排序。最后串接各个处理器的排序结果并行发送并行接收数据并行：在不同的数据集上并行地执行相同的操作。并行排序并行的外部排序-归并首先回顾串行数据库的外部排序-归并算法步骤：每一个处理器Pi在它的本地对磁盘Di中的数据进行排序（数据并行）对每个处理器中的排好序的文件并行地进行归并，得到最终排好序的输出并行排序并行排序(11/23)范围划分排序选择处理器P0,...,Pm执行排序,其中m

n-1在排序属性上创建有m个项的范围划分向量利用范围划分重新分配关系落在第i

个范围内的所有元组送往处理器PiPi

将接收到的元组临时存储在磁盘Di这一步需要I/O和通信开销各处理器Pi

对本地的关系分片进行排序各处理器并行执行同样的操作(排序),相互没有交互(数据并行)最后的归并是平凡的:范围划分确保对i

<

jm,处理器Pi上的键值都小于Pj上的键值并行排序并行外排序-归并假设关系已经划分到磁盘D0,...,Dn-1(任何划分方法)各处理器Pi

对磁盘Di上的数据进行本地排序各处理器上排好的序段(run)再进行归并以得到最终的排序输出序段的归并可并行化,如下:将各处理器Pi上的有序分片范围划分到处理器P0,...,Pm-1各处理器Pi

对接收到的输入流进行归并,得到单一序段处理器P0,...,Pm-1

上的各序段合并即得到最终结果并行联接基本思想联接操作需要测试成对元组看它们是否满足联接条件,如果满足则该元组对加入联接输出结果并行联接算法试图将待测试元组对划分到若干个处理器上,每个处理器在本地计算部分联接结果最后,各处理器上的结果汇集成为最终结果并行联接方法基于划分的连接（适用于等值连接和自然连接）分片-复制连接（适用于一般连接条件）并行散列连接（适用于等值连接和自然连接）基于划分的连接对等值联接和自然联接,可以将两个输入关系划分到多个处理器上,各处理器在本地计算联接令r

和s

是输入关系,我们要计算r

r.A=s.B

sr

和s

分别划分成n

个分片,记为r0,r1,...,rn-1

和s0,s1,...,sn-1.可以用范围划分或散列划分r

和s

必须根据其联接属性r.A和s.B来划分,并使用相同的范围划分向量或散列函数分片ri

和si

分配到处理器Pi,各处理器Pi

在本地计算ri

ri.A=si.Bsi.可以使用任何标准联接方法基于划分的连接分片与复制联接对某些联接条件不能用划分方法例如,非等值联接条件,如r.A>s.B.对于无法应用划分的联接,可以使用分片与复制技术来达到并行化分片与复制联接方法：对其中的一个关系，例如r，进行划分。可以采用任何一种划分技术，包括轮转法分布将另一个关系s复制到所有的处理器处理器Pi采用任何一种连接技术本地地进行ri和整个s的连接最后收集结果特例–非对称分片与复制分片与复制联接一般情形:减小各处理器上的关系的大小r

划分成n

个分片r0,r1,...,rn-1;s划分成m

个分片s0,s1,...,sm-1;可用任何划分技术至少应有m*n个处理器记为P0,0,P0,1,...,P0,m-1,P1,0,...,Pn-1m-1Pi,j

计算

ri

与sj的联接.为此,ri

被复制到Pi,0,Pi,1,...,Pi,m-1,而si

被复制到P0,i,P1,i,...,Pn-1,i可用任何联接技术分片与复制联接分片与复制的两个版本都可在任何联接条件下运行,因为r

的每个元组可与s的每个元组测试联接条件通常比划分联接代价高,因为一个关系(对非对称分片与复制)或两个关系(对一般分片与复制)必须复制即使可以使用划分技术,有时非对称分片与复制也更可取例如,若s小而r很大,且已作划分,可能更廉价的联接方法是将s复制到所有处理器,而不是将r和s重新在联接属性上划分分片与复制联接a.

非对称分片与复制b.分片与复制并行散列连接适用于等值连接和自然连接首先回顾串行数据库的散列连接算法方法:设s是较小的表，r是较大的表确定连接属性上的散列函数h1，用于对s元组和r元组进行划分确定连接属性上的散列函数h2，用于对每一划分中的s元组构造散列索引并行散列连接步骤:基于散列函数h1将关系s的元组分布到n个处理器中当s元组到达各处理器时，用散列函数h2对每一个处理器中的s元组构造散列索引(这一步骤在各处理器中各自独立地并行地进行)基于散列函数h1将关系r的元组分布到n个处理器中，各处理器在收到每一个r元组时用散列函数h2查找s上的散列索引，同时进行连接(这一步骤也是在各处理器中各自独立地并行地进行)并行散列连接并行散列连接算法:/*对关系s进行划分*/

置Hs0,Hs1…,Hsmax为空

foreach元组tsinsdobegini:=h(ts[JoinAttrs])；

Hsi:=His

∪{ts}；

end/*对关系r进行划分*/

置Hr0,Hr1…,Hrmax为空

foreach元组trinrdobegini:=h(tr[JoinAttrs])；

Hri:=Hri∪{tr}；

end并行散列连接算法:

/*对每一分划进行索引嵌套循环连接*/fori:=0tomaxdobegin读Hsi,在内存中建立其散列索引；

foreach元组trinHridobegin检索His的散列索引，定位所有满足

ts[JoinAttrs]=tr[JoinAttrs]的元组ts

foreach匹配的元组tsinHisdo

begintr∗ts加入结果中；endendend并行散列连接并行嵌套循环联接假定关系s

远远小于关系r,且已划分存储在关系r的每个分片上,r的联接属性上存在一个索引将关系s

复制,利用现有的关系r分片,采用非对称分片与复制存有关系s分片的各处理器Pj

读入存储在Dj上的关系s

的元组,并复制到其他各处理器Pi本阶段结束时,关系s

在所有存有关系r的元组的场地上得到复制各处理器Pi

执行关系s与关系r的第i个分片的索引嵌套循环联接其他关系运算选择

(r)若形如ai=v,其中ai

是属性而v是值若r在ai上做了划分则选择在单个处理器上进行若形如l<=ai<=u(即是范围选择)且关系在ai上做了范围划分选择在其划分与指定值范围有重叠的各个处理器上执行其他所有情形:选择在所有处理器上并行执行其他关系运算消除重复利用任一并行排序技术执行排序过程中一旦发现重复就删除之.也可以划分元组(利用范围或散列划分)并在每个处理器本地执行消除重复

其他关系运算投影不带消除重复的投影可以在从磁盘并行读入元组时进行如果需要消除重复,以上任何消除重复技术都可用分组/聚合将关系按分组属性划分然后在每个处理器本地计算聚合值通过在划分前部分计算聚合值可以减少划分时传送元组的代价考虑sum聚合运算:在每个处理器Pi对存储在磁盘Di上的元组执行聚合运算导致在每个处理器上有部分和的元组局部聚合的结果按分组属性划分,然后在每个处理器Pi上再次执行聚合以得到最终结果划分时只需将较少元组送到其他处理器操作并行求值的代价如果划分没有偏斜,并且没有因并行求值引起的开销,期望加速比将为1/n如果要考虑偏斜和开销,并行操作的时间可以估计为Tpart+Tasm+max(T0,T1,…,Tn-1)Tpart

是划分关系的时间Tasm

是整合结果的时间Ti

是处理器Pi上的操作所花时间这个时间的估计需要考虑偏斜和竞争中浪费的时间操作间并行并行地执行一个查询表达式中的多个不同的操作。流水线并行独立并行流水线并行不同的操作在不同的处理器中并行地执行第一个操作的输出作为第二个操作的输入，第一个操作产生了部分输出第二个操作就可以开始进行流水线并行考虑四个关系的联接:r1r2r3r4建立一个流水线来并行计算三个联接令P1计算temp1=r1r2令P2计算temp2=temp1r3令P3计算temp2r4这些操作可以并行执行:

在计算进一步结果的同时可以将已计算出的结果元组送到下一操作需要用可流水线化的联接算法(如索引嵌套循环联接)流水线并行例

r1|><|r2|><|r3|><|r4限制流水线并行可用性的因素流水线并行有用是因为它避免了将中间结果写到磁盘对少量处理器有用,但对较多处理器伸缩性不好.一个原因是流水线链不能达到足够的长度.对于需要取得所有输入后才能产生输出的操作(如合计与排序)不能流水线化对于经常发生的偏斜情形,一个操作的执行代价远远高于其他操作,这时只能获得很少的加速比独立并行独立并行考虑四个关系的联接r1r2r3r4P1用来计算temp1=r1r2P2用来计算temp2=r3r4P3用来计算temp1temp2P1和P2可以独立地并行工作P3必须等待来自P1和P2的输入可以将P1与P2输出到P3的过程流水线化,从而结合了独立并行和流水线并行并没有提供高度的并行对较低程度的并行有用.在高度并行系统中用途不大并行查询优化比串行系统的查询优化复杂，是一个比较活跃的研究领域面临的问题:代价模型复杂可考虑的方案太多资源分配问题其他(略)UtilityParallelismLoadParallelparsingandformattingofrecordsParallelI/OserverstowritedatatothecontainersCreateindexParallelscanningandsort