（计算机软件与理论专业论文）查询并行处理技术研究.pdf

华中理工大学博士学位论文 摘 、q 近十年来，计算机应用领域不断扩大，人们要求计算机处理的数据量越来越火，数据结 勾越米越复杂，要完成这样大量复杂数据的搜索、匹配、查询等处理，传统的计算机技术和 数据库技术很难承受。 并彳了计算机体系结构的发展为解决上述问题提供了极大可能，将并行处理技术应用于数 据库查询处理，充分发挥多处理器结构的优势，提高查询等处理的性能，从而提出了查询并 行处理技术问题。查询并行处理技术的核心是通过将数据在多个结点机上分布存储，开发查 询闻并行性操作间并行性以及操作内并行性，利用多个处理机对数据进行并行处理，解决 磁盘i o 瓶颈问题，提高数据查询的效率。查询并行处理技术己成为未来高性能数据库系统 的核心技术之一。 近年来，国内外对奁询并行处理技术进行了很多的研究，取得了一系列的研究成果，但 仍有许多问题没有解决：( a ) 数据划分问题。至今仍未产生一种能有效支撑查询并行查询的 数据划分方法；可扩展性要求数据可重新划分，这方面的研究还不充分；( b ) 现有的并行数 据操作算法人都是由传统的算法并行化而来，新的并行数据操作算法不多；对并行数据操作 算法进行性能分析的手段不多；现有抗偏斜并行数据操作算法的额外开销很大 ( c ) 菏行查 询计划表示模型和代价模型的研究没有取得实质性的突破；现有的并行查询优化算法没有充 分开发数据查询的三种并行性；并行查询优化算法本身的并行化问题没有得到解决。广 本文对查询并行处理技术进行了研究，在分析已有研究成果的基础上，提出了自己的观 点、技术平方法，主要的研究工作如下： 1 、论述了现有常用的数据划分方法，包括各种一维数据划分方法、多维数据划分方法 以及基于g r i d 文件和b 树的数据划分方法，并对它们进行了评价；研究了系统在扩展情况 f 的数据重新划分问题，提山了新的数据莛新分布算法，本算法考虑了数据重新划分过程中 的并行性开发问题。、， 2 、从一个新的角度山发，提山了一个并行数据操作算法的分析模型，陔分析模型能够 方便地寻找并行环境中多种资源并行度的平衡点，发现影响算法性能的瓶颈所在，为评价和 选取并行算法提供了一条可行途径：本文对两个常用的并行连接算法进行了改进使它们能 够适合不同的并行处理环境；提山了一个新的抗偏斜二元连接算法，本算法能够以较小的开 销对连接操作中的数据偏斜进行矫正，尤其适合网络速度或磁盘速率相对较慢的并行处理环 + 本文所做i ：作受8 6 3 计划资助( 课题编号8 6 3 3 0 6 z d 0 1 7 ) 华中理工大学博士学位论文 氆。) r。 r 7 3 、新的并行夯啕优化算法的设计- 逛赉询并行处理研究领域，弗行查询优化技术i i 有 1 常重要的地位，并行查询优化技术决定了由其产生的井行查询执行计划的效率，从而影响 剑整个，f 行查询处理系统的性能。由丁基丁线性树的并行查询优化算法的的可选查询计划较 少，不能保证高效查询计划的产生，更由丁计算机体系结构以及并行处理技术的发展，使得 计算机的处理能力大大加强，研究开始转向基于丛生树的查询优化算法。本文提出了一个新 的并行查询优化算法，本算法综合了分段右深树利丛生树算法的优点，以犬关系和两个阀值 对算法进行调节，充分开发了查询处理中的三种井行性，使本算法可产生高效的查询计划。r 4 ：本文探讨了并行查询处理系统的设计原则和实现技术，研究了8 6 3 计划资助项目一 一“基丁曙光1 0 0 0 a 的并行查询核心系统的发计与实现技术研究”中的一些关键问题，这些 问题土要包括：并行数据划分方法的选取、并行数据操作算法库的建立、并行查询优化算法 的设计以及并行调度方法等x “基于曙光1 0 0 0 a 的并行查询核心系统”已经实现井已移植到 了我国新一代的高性能 性能达到了预期的效果 统曙光2 0 0 0 1 上，经w e s c o n s i nb e n c h m a r k 测试，其 并行查询处理技术已得到国内外专家的高度重视，并将在多个领域内发展和麻川。 关键字：查询并行处理，并行数据划分，并行数据操作算法，并行连接算法叛穗偏锌r 一并 行多元连接，并行查询优化 i i 系# 罗 华中理工大学博士学位论文 a b s t r a c t i nt h el a s td e c a d e f o rt h ea p p l i e df i e l do ft h ec o m p u t e r se x p a n d i n gc o n t i n u o u s l y t h e r e q u i r e m e n to ft h ed a t apr o c e s s i n gb e c o m i n gh i g h e ra n dh i g h e r t h ed a t a s c a l eb e c o m i n g l a r g e ra n dl a r g e r t h e r ea r eh u g ec o m p l i c a t e dd a t at h a tm u s tb ep r o c e s s e db yt h ec o m p u t e r s as i n g l ec o m p u t e rc a nn o tb ec a p a b l eo fs e a r c h i n g ，m a t c h i n ga n dq u er y i n gf o rs u c hh u g e a m o u n to fd a t a 、 t h ed e v e l o p m e n to fa r c h i t e c t ur eo fp a r a l l e lp r o c e s s o r ss h e d sal i g h to nt h i spr o b l e mb v c o m b i n a t i n gt h ep a r a l l e lp r o c e s s i n gt e c h n i q u ew i t h d a t a b a s eq u e r i e st e c h n i q u e s ，t h e a d v a n t a g eo fl h ear c h i t e c t u r eo fm u l t i p l ep r o c e s s or sc a nb et a k e ns ot h e li t c a np r o v i d e b e t t e rp e r f o r m a n c ea n ds c a l a b i l i t yt h e nt h a to ft h em a i n f r a m et h eb o t t l e n e c ko fi oc a nb e s o l v e db yt h ed a t ad i s t r i b u t i n ga n dp a r a l l e lp r o c e s s i n gi nm u l t i p l ed i s k st h ee f f e c t i v e n e s so f i h e q u e r yc a nb ei m p r o v e db yd e v e l o p i n g t h ei n t r a - q u e r i e sp ar a l l e l i s m i n t e r q u er i e s p a r a l l e t i s ma n dq u e r i e sp a r a l l e l i s mi nap , f r a l t e ld a t aq u e r ys y s t e mt h ep a r a l t e lq u e r y t e c h n i q u eh a sb e c o m et h ek e yo ft h ef u t u r eh i g hp e r f o r m a n c ed a t a b a s e i nr e c e n ty e a r s t h e r ea r eai o t o fr e s e ar c hr e s u l t sa b o u tt h ep ar a l l e lpr o c e s s i n g t e c h n i q u e si nq u e r i e sb u tt h e r ea r es t i l lal o to fp r o b l e m st ob es t u d i e d ：( a ) t h ep ar t i t i o n m e t h o do foned i m e n s i o ni se a s yi od ob u ti t se f f e c t i v e n e s si sn o tg o o dt h e r ea r em a n y a d v a n t a g e so fp a r t i t i o nm e l h o do fm u l t i p l ed i m e n s i o n s b u ti t i sh ar dt oi m p l e m e n tt h e s c a l a b i l i t yr e q u i r e st h a tt h ed a t ac a nb er e p a d i t i o n e da n dt h e r ei sn oe n o u g hr e s e a r c hi nt h i s f i e l d ( b ) t h e r ea r eal i t t l en e wp a r a l l e ld a t ao p e r a t i o na l g o r i t h m sb e c a u s em o s to ft h e ma r e p ar a l l e l i z e df r o mt h et r a d i t i o n a la l g o r i t h m st h e r el a c k so f t h em e t h o d st oa n a l y z et h e p er f or m a n c eo fp a r a l l e ld a t ao p er a t i o na l g or , t h m sa n dt h er ei st o oh e a v yo v e r l o a df ort h e a n t i s k e wa l g o r i t h m s ( c ) t h e r ea r en ob r e a k t h r o u g hi nt h er e s e a r c hi nt h eq u er yp r e s e n t i n g m o d e l sa n dc o s tm o d e l sa n dt h et h r e ek i n d so fp a r a l l e l i s mar er i o td e v e l o p e dw e l ii ni h e pr e s e n tp a r a l l e lq u e r yo p t i m i z a t i o na l g or i t h m ! ；t h ep r o b l e mo ft h ep ar a l l e l i s mo ft h ep ar a l l e l q u e r yo p t i m i z a t i o na t g o r i t h m sh a sn o tb e e ns o l v e d t h i st h e s i sf o c u s e so nt h ep a r a l l e lq u er yt e c h n i q u e sa f t e ri h ei n t r o d u c t i o no fi h ep r e s e n t r e s e a r c h ： f i r s t 。t h em a i nd a t ap a r t i t i o n i n gm e t h o d sa r ed e s c r i b e da n de v a l u a t e d ，i n c l u d i n go n e d i m e n s i o nm e t h o da n dm u l t i p l ed i m e n s i o nm e t h o d sa n dl h em e t h o d sb a s e do ng r i da n d b t r e e st h ep r o b l e mo ft h ed a t ar e d i s t r i b u t i n gi nt h es y s t e ms c a l a b i l i t yi sr e s e ar c h e da n d n e wd a t ar e d i s t r i b u t i n gm e t h o di spr o p o s e di nw h i c ht h ep ar a l l e l i s mi nt h epr o c e d ur eo fd a t a r e p ar t i t i o ni sc o n s i d e r e d s e c o n d ，an e wa n a l y t i c a lm o d e lo fp a r a l l e ld a t ao p e r a t i o na l g o r i t h mi spr o p o s e d w h i c h c a ne a s i l yf i n dt h eb a l a n c ep o i n t nt h em u l t i p l er e s o ur o ei nt h ep ar a l l e le n v i r o n m e n ta n dt h e b o t t l e n e c ko ft h ea l g o r i t h m s 。p e r f o r m a n c et h e s ef o u n dar e a s o n a b l ew a yf o rs e ar c h i n ga n d h i sw c , r ki ss u p p o s e db yn a l i o n a lh i g h t e c hp r o g r a m ( 8 6 3p m g r a m ) n o8 6 3 3 0 6 。z d 一0 1 7 ) 华中理工大学博士学位论文 e v a l u a t i n gp a r a l l e la l g o r i t h m s s o m ep a r a l l e lj o i na l g o r i t h m sa r ea d a p t e dt od i f f e r e n tp a r a l l e l e n v i r o n m e n t san e wa n t i - s k e wa l g o r i t h mi sp r o p o s e dt ob a l a n c et h ed a t as k e wi nt h ei o i n o p e r a t i o n sw i t hi i t t l eo v e r h e a d i ts p e c i a l l yf i t s nt h ep a r a l l e le n v i r o n m e n tw i t ht h es l o ws p e e d i nn e t w o r ka n dd i s k t h i r d n e wq u e r yo p t i m i z a t i o na l g o r i t h m sa r ed e s i g n e d t h e p a r a l l e lo p t i m i z a t i o n t e c h n i q u ep l a y sak e yr o l ei nt h ef i e l d o ft h ep a r a l l e lp r o c e s s i n go ft h eq u e r i e s t h er a t i oo f t h ep a r a l l e lq u er ye x e c u t i o np l a ni sd e t e r m i n e db yt h ep a r a l l e lo p t i m i z a t i o nt e c h n i q u es oi s t h ep er f o r m a n c eo fw h o l es y s t e mb e c a u s eo ft h el i m i t e dn u m b e ro ft h eq u e r ye x e c u t i o n p l a n sb a s e do r ) t h ej i n e a rt r e e s 1 h eh i g hp e r l o r m a n c eq u e r ye x e c u t i o np l a n sc a nn o tb eg o t d e f i n i t e l yb e c a u s eo ft h ei n c r e m e n to ft h ep o w e ra n d s i z eo ft h ec o m p u t er sf o rt h ec o m p u t e r ar c h i t e c t u r ea n dp a r a l l e lp r o c e s s i n gt e c h n i q u e ，t h er e s e a r c hh a sf o c u s e do nt h ea l g o r i t h m s b a s e do nt h eb u s h yt r e e san e wp a r a l l e lo p t i m i z a t i o na l g or i t h mw a sp r o v i d e dw h i c h c o m b i n e st h ea d v a n t a g eo ft h es e g m e n t e dr i g h tt r e ea n dt h eb u s h yt r e e u s e sl a r g er e l a t i o n s a n dt w ot h r e s h o l d st os c h e d u l e ，t h et h r e ek i n d so ft h ep a r a l l e l i s mw e r eu s e da n dt h eh i g h p e r f o r m a n c ea l g o r i t h mc a nb eg o t f o u r t h t h ep r i n c i p l e so fd e s i g na n di m p l e m e n t a t i o no ft h ep a r a l l e lq u e r yk e r n e ls y s t e m ar ed i s c u s s e d s e v e r a ii m p o r t a n lp r o b l e m si nt h ep r o j e c to fr e s e a r c h0 nt h ep ar a l l e lq u er y s y s t e mb a s e do nd a w n i n g 一1 0 0 0 as p o n s o r e db yt h en a t i o n a l8 6 3a r er e s e a r c h e d t h ed a t a p a r t i i i o nm e t h o d 。t h ed e v e l o p m e n to ft h et h l e e k i n d so fp a r a l l e l i s ma n dt h ep a r a l l e lq u e r y o p t i m i z a t i o nt e c h n i q u ew e r es t u d i e df o ri r r t p l e m e n t a t i o n t h es y s t e mw h i c hi st e s t e db yt h e w i s c o n s i nb e n c h m a r ka n db e t t e rp e r f o r m a n c ew a sg o t h a sb e e ni m p l e m e n t e da n d t r a n s p l a n t e dt ot h ed a w n i n g2 0 0 0 1 k e yw o r d s ：p a r a l l e lq u e r yp r o c e s s i n g p a r a l l e l a l g o r i t h m ，p a r a l l e lj o i na l g o r i t h m d a t as k e w o p t i m i z a t i o n d a t ap ar t i t i o n p ar a l l e ld a t ao p e r a t i o n p a r a l l e lm u l t i p l e j o i n ，p a r a l l e lq u e r y i v 华中理工大学博士学位论文 1 1 问题的提出 第一章绪论 近十年来，计算机麻川领域不断扩人，人们对数据处理的要求越来越高，数据规模也越 来越人，人革复杂的数据需要计算机来处理，它们往往涉及n j l 千兆甚至兆兆的数据，特圳 是复杂数据对象，如多媒体信息、地理信息、气象信息等。由丁处理机性能的增长有物理极 限，土存容苗的增加赶不上数据耸的增k ，处理机速度与i i o 能力z 问的著异越米越人，而 且受剑传统卉询技术的限制，要完成这样人数据茸的搜索、匹配、卉询作传统的基丁单 个处理机的夯向系统报难承受。 咀”行处理技术为基础的计算机多处理器结构为解决上述问题提供了极人可能。随着超 人规模集成电路技术的帛述发展、单片微处e 机性能的提高以及高带宽低延迟且联网技术的 成熟，使得计算机体系结构快速向基丁通川微处理机芯片的对称多处理机( s m p ) 、多处理机 f m p ) 以及人规模并行处理机( m p p ) 转变。各种高性能应_ l i j 需求的不段涌现使得井行体系 结构受剑越来越普遍的重视。布向并行处理技术就是将，f ：行处理技术与卉向技术相结合，开 发多处理器结构的优势，从而提供比传统人刑机系统( m a i n f r a m e ) 高得多的性能价格比平| i 照好的可扩展性。并行壳询处理技术已成高性能数据库技术、人i 智能、知识挖捌等研究领 域的核心技术m ”。 并行计算机系统的发展卜分迅速，相比之r ，并行软什技术的发展明显落后，并已成为 并行处理技术发展的障锚，尤其是在卉洵并行处理技术上。p 司此，研究利开发能够充分发抨 扦行计算机处理能力的并行软什技术和升行软中卜系统成为当务之急。 1 2 查询并行处理研究的重要意义 第1 4 届超人规模数据库( v l d b ) 会议指山：“查询并行处理”是数据库领域的一个匹 要的研究方向。布 i j 爿行处理既是实现关系数据序并行处理、并行实时数据库、演绎数据霄 等的关键问题之一，也是人智能、知识挖捌等领域的关键问题之一，是数据库并行处理叶1 必须解决的重要的理论与技术问题。 卉啕计行处理的研究具有如r 科学意义： 1 、将并行处理技术引进数据库系统，可推动数据库计行处理研究。推动数据席技术午| l 华中理工大学博士学位论文 理论的发展，井为研制“并行蠢询系统”奠定理论和技术基础。 2 、推动数据库与人i ：智能等的结合，可使火型共享信息库推理7 h 7 化。 3 、解决联机事务处理和实时处理问题，实现数据的高效管理。 4 、卉洵 r 处理的研究符台数据库发展的方向，也符台软仆1 群发展的方向。 1 3 查询并行处理的主要研究内容 卉询并行处理的研究主要围绕着关系数据模型进行，这是由 i ：关系模型经过十儿年的 研究和发展，已经1 f 常成熟平普遍接受，并在市场上i 主导地佛：关系模型和荚系数据库系 统的仆过程性壳询语言s q l 为其井行化提供了有利条什；关系查询1 n 常适合r 升行处理。 查询并行处理的研究内容土要包括 8 - 1 0 j ： 适于查询并行处的理体系结构研究。夯询并行处理系统的体系与其依赖的升行计算机的 体系结构密切相关，并行计算机硬件卡勾成方式对赉询并行处理系统的效率有着决定性的 影响。人们一自：探讨着什么形式的并, 1 7 i t 。算机体系结构最适合丁卉啕升行处理系统的实 现。 查询并行处理物理设计方法研究。查询并行处理物理设计方法研究的主要帕容是如何将 一个关系进行划分井分配到多个处理机上去，使得数据划分方法能有效地支持数据操作 算法。 并行数据操作算法研究。并行数据操作算法的主要研究内容是如何井行地进行数据操 作，使得多个处理机的效率得到充分发挥，它与查询并行处理密切相关。 并行查询优化技术研究。爿行本询优化技术是夯啕井行处理技术的重要组成部分，它需 要解决的问题是如何找到具有晟小响廊时间的卉询计划。这涉及到两个方面的问题： 是表示模型问题，二是并行责询优化算法问题。 国内外许多学者对这些问题进行了研究，井提山很多解决方法，但还有许多问题没有得 剑解决，仍需深入地研究。 1 4 国内外研究现状 1 体系结构 奇询并行处理系统的效率依赖于多处理机系统的体系结构，因此在什么样的多处 理机系统上建造查询并行处理系统是一个重要的问题。文献【”】提山了建造布洵并行处 理系统的二种多处理机模玳，即：完全共享的s e ( s h a r e d - e v er y t h i n g ) 模型，共享馓 2 华中理工大学博士学位论文 盘的s d ( s h a r e d d i s k ) 模删羽j 无共享的s n ( s h a r e d ，n o t h i n g ) 结鞫。除此之外+ 还 有人提出了i ，j 种基丁主存的s m ( s h a r e d - m e m o r y ) 结构，其通信费州较低。由j s n 结构的兆享资源最少，容易扩展，所以基rs n 结构的多处理机系统建造布询并行处理 系统得剑了人们的博遍认可n n 。日前的符淘开行处理系统研究多数是同绕着s n 结构进 行的。 文献f 1 3 】提出了涮台层次模型，它综台了s m 雨is n 、的优点，在具有高度可扩展能 力的基础上，人人地加强了多事务处理能力。 多处理机系统的发展非常迅速刚此查询升行处理系统虑能适麻多种多处理机结 构模型，返也为戎洵并行处理系统研究提山了更高的要求。 2 数据划分算法 数据划分是布洵并行处理的基础目前已经提出了多种数据划分算法土要分为 四类：一维数据划分方法，多维数据划分方法，文十l 并行化方法和索引并行化府涮；。 一维数据划分方法包括r o u n d r o b i n 方法、h a s h 划分方法承ir a n g e 方法【1 4 - 5 。 h y b r i d r a n g e 综合了上述方法行进行丁改进6 】。一维数据划分方法只根据荦个属f i ：恤 进行划分而多维划分方法则对多个属性值进行处理，文献【1 7 1 8 1 提山rc m d 多维数 据划分方法，b u b b a 卉询并行处理原型系统中提山的b e r d 方法1 1 9 】年0 刚主从属性列数 据进行划分，文献【2 0 】对多种多维数据划分方法进行了分析，把h y b r i d r a n g e 方法盎 多维上进行推广，得到了m a g i c 划分方法。 关系索引是褒询处理中重要的查询手段，因此人口) 提出了许多基丁b 树的开行化 方法【2 1 i 。b 树，f ：行化方法土要有二种：记录划分法、人页b 树方法1 和页划分方法。 文献 2 3 2 4 提山了g r i d 文 f l 。并行化的方法，这种方法需要解决的关键问题琏 g r i d 文件在多处理机间的初始分布垌1 1 自数据插入与删除所引起的数据负载不平衡的处 理，人们还对其他数据分布方法进行了研究口5 2 “。 至今，尚未产生一种有效地支持夼淘并行处理的数据划分方法，芙r 数据划分疗 法，人们仍在继续深入地研究。 3 并行数据操作算法 使h j 并行数据操作算法实现卉询的并彳亍处理可以更充分地发挥多处理机的并 j ： 性，提高系统的效率和处理能力。并行数据操作算法的研究是近年米国内外研究的要点， 但目前所做的l 作主要是在原有的串行数据操作算法基础上进行井行化。 连接( j o i n ) 操作是关系卉询中最常心和最耗时的操作是构成各种复杂卉淘的 基本运算，并且现有的廊h j 要求查询系统执行越来越多的连接操作，皿i 此目前并干r 数 据操作算法的研究一直针对连接操作。3 “。主要的，f 行连接算法有：基丁瞅套循环的 n e s t e d l o o p i ”j ，基r 排序扩t 升的s o r t m e r g e l 3 2 】和基丁数列技术的h a s h b a s e d 连接算 。3 华中理工大学博士学位论文 法p 3 - 3 4 1 其中h a s h b a s e d 连接算法主要考虑等值连接。文献 3 5 3 8 对这些算法进行， 分析，结果表明h a s h b a s e d 连接算法具有最好的连接效率，且容易实现冈此对它的 倒f 究最为深入。有两种h a s h 连接弊法最具有代表性：g r a c e 。h a s h j o i n 算法干 h y b r i d h a s h j o i n 【3 ”。 由丁芙系在多个处理机上的分布可能是不均匀的，从而产生_ 数据偏斜( d a t a s k e w ) 问题，它对连接算法。尤其是h a s h b a s e d 连接算法的影响很人，丁是人们舀 抗数据偏斜算法方面进行了许多研究i ”l ，主要有t i j 算法、a b j 算法和a b j + 算法】。 但是还有一些学者认为在实际的数据库系统中数据偏斜并不十分严重，另外这些抗数据 偏斜的算法需要额外的处理机开销，有时数据迁移所带来的开销会抵消缄超过算法所带 来的好处，例此不主张采_ l _ j 抗数据偏斜操作算法。 4 并行查询优化 行行卉嘲优化是卉啕并行处理系统中遇到的斟雌最多的部分，它通过对处理机绌 数、通信网络和数据分和策略进 i 分析，得山最优的卉词计划交给调度器执行。 在现有的戍川要求中，迮接的数 越来越多，川此多元连接优化问题得到了i h 岛 的重视。文献【5 2 】提山了商询树模，包括左深树、矗深树利丛生树，计提山1 r 丛j 。这 儿种模删的优化算法：l d t 、r d t 算法，随| 亓文献 5 3 5 5 提山利讨论了基分段以深 杠f 的s r d 锋法，文献 5 6 5 7 提山和讨论了基丁丛生树的m j 卉啕优化算法本文作者 提出了基r 丛生树的可调仃的， ：行布洵优化算法闭】，文献 5 9 7 4 讨论了_ 对不同多处理 机结构的并行卉询优化算法。由j 基 。树模型的夼洵优化算法不能保证得到虽优的布淘 计划，网此许多人对图模型表示山了浓厚的兴趣。关丁赉啕计划表示模型的研究仍需进 。步深入。 过左，人们一直使_ l j 静态的赉啕优化算法，目前多_ l i j 户环境多事务处理的要求不 断提高，这种算法受到了严重的挑战，人们迫切要求布询优化器能够根据当前的负载剌 资源使川情况进行调整，网此基丁启发式和动态可调的卉洵优化算法相继提山m 。8 ”， 但研究还不够深入。另外卉询优化算法本身的= f _ 行化问题也没有得到解决。 1 5 国内外查询并行处理原型系统研制情况 近年米，国内外对卉询井行处理系统进行，人蟥的研究，升相应进行各种各样的尝试 国外研制出的原型系统主要有b u b b a l 8 6 * 8 7 ，g a m m a l 8 8 - 8 9 ，v o l c a n o 【9 。l ，gr a c e s d c i ”i 等；商 业数据库系统中引入并行处理机制的土要有o r a c l e i ”l ，s y b a s e i ”l ，i n f o r m i x 9 4 9 5 1 t e r a d a t a 4 华中理工大学博士学位论文 d b c 1 0 1 2 ”“，d b 2 ”。1 ”1 锋，国内主要进行的是原型系统的研制，如基丁m u l t i t r a n s p u t e r 的升行卉i 旬系统。”“、基丁l ：作站机群的并行卉向原刑系统平运行r 曙光1 0 0 0 a 平曙光 2 0 0 0 1 的j f 行布洵核心系统f l o ”】p b a s e ”1 ，p ar a b a s e 1 0 8 。1 0 9 ，h p d b 1 01 1 以及p a p o l 1 2 ； 等，u ，以看出我国的查询并行处理研究止逐步缩小与国外的著距。 r 面就土要的一些卉由爿：行处理系统进 r 介 f j 。 i b u b b a b 6 - 8 1 1 b u b b a 系统是一个基丁s n 结构的商向并行处理系统在f l e x 3 2 多处理机系统 上实现，f l e x 3 2 系统拥有4 0 个处理结点，每个处理结点拥有臼己的内存平磁盘，其中 接口处理结点负责与外部的通信，并且协调事务在多处理机上的执行，其它处理机统称 为智能仓库( i n t e l l i g e n tr e p o s i t o r i e s ) ，负责数据储存和事务的执行。 b u b b a 系统采川了一种基 ji ：作负载平衡的数据划分方法，它根据各个处理结点 上的数据的访问频率决定数据的去向，使得各个处理结点机的访问频率相近，从而达剑 数据处理的平衡。 数据席编样语音f a d 编译器e l i 动将f a d 科序j ：行化，形成具有并行性表达式原 诰的p f a d ，雨将p f a d 分解成多个构什，进行执行。揲作问的数据发送利接收聚j + j 数 据流的方法进行控l i i ；l l l 协调。 另外，b u b b a 系统对故障恢复做r 很多t 作，它通过殴置检壳点平数据库口，占对 结点故障进行恢复。 2 g a m m a 8 8 8 口】 g a m m a 是w i s c o n s i n 人学开发的查询并行处理原型系统，w i s c o n s i n 人学是最 甲i 进行卉询并行处理系统研究的人学之。g a m m a 系统建立在一个以1 7 个v a x1 1 7 5 0 处理机通过令牌环( t o k e n r i n g ) 网连接在一起的多处理机系统之上的卉向井行处理系 统其中每个处理机拥有2 m 士存储器8 个处理机拥有臼己的磁盘。1 台v a x1 1 1 7 5 0 作为前端机另外的处理机作为处理结点。 g a m m a 采川一维数据划分方法对关系进行划分，它f 司时剥r o u n d r o b i n 、 r a n g e 、h a s h 和h y b r i d - h a s h 进行了实验。 3 v o l c a n o 9 叫 由g r a e f e 等实现的v o l c a n o 系统是一个数据流查询处理系统它贝备可扩充性利 并行性。其并行性封装使得单处理机f f l d 查询处理算法直接运行多处理机环境。它实现 了一个交换操作符能并行化其它操作。芙系代数操作以迭代算子方式实现，它们儿有 个简单的o p e n n e x t c l o s e 协议，每个操作符不必关心其输入数据流产生算子以及输 出数据流如何被其它算子使h j 。 华中理工大学博士学位论文 v o l c a n o 系统支持划分数据集上的操作内并行性以及币直和水平的操作间并行 性。操作内并行性指利川多处理机枉数据子集上的同样操作：畦直操作间，j 性指多个 进 ! f ! 的流水线处删；水平剪行性是指复杂壳嘲树中不同子树操作间的独立 行性： v o l c a n o 系统的：上婪构什有：文什系统构什、缓冲管理、排序器、b + 树模块以及抨种数 据操作算法。 4 g r a c e s d c l 9 1j g r a c e s d c 是在数据j 车机g r a c e 的基础上芨展而来，g r a c e 是尔京人学实现的鹾 的数据库机之一，由丁数据席机的实现代价高昂，白从d e w i t t 等人发表了必r 住通 j = j 多处理机上进行数据库研究的论文之后，g r a c e 的研究也开始向软件研究上倾斜。 g r a c e s d c 就是对g r a c e 的软件部分进行改进而实现的。g r a c e s d c 采j l i j 泓台层次模 掣，系统中包含许多处理单元，它们之问是无共享结构的，每个处理单元是一个s m 系 统，拥有多c p u ，共享主存、磁棉，以及其它硬什资源：这些处理单元通过欧密伽网络 琏拨1 _ ! i ：。起。 g r a c e l s d c 使h h a s h 方法进行连接，并通过欧密伽网络的桶分布消除数据倾斜 影响。 5 o r a c l e 9 习 o r a c l e 公r 日是世界数据库市场上所i i l 份额最人的公司。19 8 9 年，o r a c l e 斤始致 力丁并行布向方面的尝试，1 9 9 1 年o r a c l e60 可以运行 。s m p ( 对称多处理系统) 结 构的多处理机系统之上，完成操作阃的并行性。1 9 9 2 年，o r a c l e 推山o r a c l e70 ，其 布询并行处理服务器可以运行在拥有6 4 个结点的n c u b e 2 上。这时，o r a c l e 仍然只 能进行奄啕问的并行加速，不能完成单个裔询内的并行性开发。1 9 9 3 年，k s r 公司训 制了o r a c l e7 0 上的布淘分解器( q u e r yd e c o m p o s e r ) ，使之具有单壳淘并行处理能 力，1 9 9 4 年，o r a c l e 推出o r a c l e71 ，。苗布其并行卉询选什可以进行连接、索引操作、 表装填等的并行处理，但它仍然不是一个高效的卉淘升行处理系统。 6 s y b a s en a v i g a t i o ns e r v e r l 9 ” s y b a s e 数据库公司起步较晚，但它往它的系统中采州许多先进的技术，采川 c l i e n u s e r v e r 结构，迅速领了市场。1 9 9 5 年它与a t t 共同开发的n a v i g a t i o ns e r v e r 实现了高性能、高可扩展性的卉询并行处理系统。 n a v i g a t i o ns e r v e r 是各个数据集上s o l 服务器的集合，士要有： c o n t r o ls e r v e r 。它接收来自j l j 户的请求，经编译氘交给s q ls e r v e r ，惦母 布洵结浆，经处理肝返网给川户，协调2 p ci l = 作： 华中理工大学博士学位论文 s p l i t m e r g es e r v e r 。进行数据的巫新分布： s q ls e r v e r 。接收来白c o n t r o ls er v erf 内请求执i t 计将结累返同给c o n t r o l s e r v e r ； d b as e r v e r 。具有c o n t r o ls e r v e r 的功能，管理系统资源，实现数据定义皓 句的执 r ，协调恢复过利利预防全局死锁： m o d e ls er v e r 。7 学掭全局数据字典如数据剥象、划分信息、规则等。 其土要特点是： 采川s n 结构，数据在各个结点上划分，具有良盘：= 的可扩展性：， 可运行丁s m p ，w o r k s t a t i o nc l u s t e r 和m p p 结构的升行计算机系统，具f 良盯的可移植性； 强人的u n d o 和r e d o 功能，有高度的可川性： 7 i n f o r m l x o lx p s e 4 - o s l i n f o r m i x70 州：山r 基j + 动态可扩胜的n ：线服务器，可以运行1 ：s m p ，m p p 以歧 s m p 机群。它支持4 种一维数据划分方法，其并行化主要基1 ih a s h 办法。 8 1 b md b 2p e 9 , 6 - 9 8 i b md b 2p e 基ts n 结构，其巾每个结点可以是一个有不同处理机数的逻辑结 点，从而实现其动态可扩展策略。 i b md b 2p e 采川h a s h 划分方法对关系进行划分，使川基r 代价的并行布嘟优 化算法，考虑剑了数据划分信息。 9 r e r a d a t ad b c 1 0 1 2 t 9 9 1 0 4 1 t e r a d a r ad b c 1 0 1 2 灶最早研制j “f n 奔| 亩j 计行