（计算机系统结构专业论文）并行数据库中数据分布和查询处理技术的研究.pdf

摘要并行数据库系统作为未来高性能的数据库管理系统，已经成为数据库领域中重要的研究课题。并行数据库系统的性能与数据库中的关系在各个节点的分布密切相关，本文针对一维数据分布方法不适于复杂查询要求，而多数多维数据分布方法难于实现的缺点，分析并比较了各种基于树结构的多维数据分布方法，给出了基于k d 树结构的分布方法的详细设计方案，指出设计基于传统索引结构的数据分布方法是解决并行数据库系统数据分布问题的一种较好方式。该方法在构造树的过程中，完成了对数据空间的划分和数据超方体的放置，不仅可以使各个处理机能够合理得分配工作负载，而且可以方便地利用索引执行查询处理操作，提高了系统的效率。如何将并行数据库系统应用于局域网络环境，并实现查询处理及优化也是本文研究的工作之一。本文采用了基于工作站网络的数据库的并行查询处理设计思想，在传统的串行数据库基础之上加入了并行化的设计方案，通过开发关系数据库的三个固有并行性来提高系统执行查询处理的能力。在此基础上，本文提出了一种并行查询处理的结构，并根据该结构在局域网络环境下设计和实现了并行查询处理的模拟系统。通过对实验结果的分析与比较，证明了合理的并行化设计可以减少通信带来的开销，获得较好的性能。关键字：多维数据分布树结构查询处理工作站网络a b s t r a c ta sh i g hp e r f o r m a n c ed a t a b a s es y s t e m si nt h ef u t u r e ，t h es t u d yo fp a r a l l e ld a t a b a s es y s t e m sh a sb e e nav e r yi m p o r t a n tr e s e a r c hp r o b l e mi nt h ef i e l do fd a t a b a s e d a t ad e c l u s t e r i n gm e t h o d st h a tp l a c er e l a t i o nf r a g m e n t sa td i f f e r e n tn e t w o r ks i t e sh a v es i g n i f i c a n te f f e c to nt h ep e r f o r m a n c eo fp a r a l l e ld a t a b a s e s b u ts i n g l ed i m e n s i o n a ld e c l u s t e r i n gm e t h o d sa r en o ts u i t a b l et ot h er e q u e s t so fc o m p l i c a t e dq u e r y , a n dm o s tm u l t i d i m e n s i o n a ld e c l u s t e r i n gm e t h o d sa r et o oc o m p l i c a t e dt oi m p l e m e n t s o ，t h i sp a p e rw i l lr e s e a r c hs e v e r a lm u l t i d i m e n s i o n a ld a t ad e c l u s t e r i n gm e t h o d sb a s e do nt h et r e es t r u c t u r e s ，a n dd e s c r i b ea na l g o r i t h m sb a s e do nt h ek - dt r e es t r u c t u r e i ti sp o i n t e do u tt h a tt h em e t h o d sb a s e do nt h et r a d i t i o n a li n d e xs t r u c t u r ea r ev e r yi m p o r t a n tw a y st os o l v et h ed a t as t o r a g ep r o b l e mi nt h ep a r a l l e ld a t a b a s es y s t e m s d u r i n gt h ep r o c e s so fc o n s t r u c t i n gt h et r e e ，t h i sm e t h o dh a sa c h i e v e dt h eg o a lo fp a r t i t i o n i n go ft h ed a t as p a c ea n dp l a c i n go ft h ed a t ah y p e r - c u b e s ，w h i c hn o to n l yb a l a n c e st h el o a do fe v e r yp r o c e s s o r , b u ta l s oe x e c u t e sq u e r yo p e r a t i o nb yi n d e xs t r u c t u r et og e th i g h e rs y s t e me f f i c i e n c y t h eo t h e rf o c u so ft h i sp a p e ri so nt h ew a yt oa p p l yp a r a l l e ld a t a b a s es y s t e m st ol a na n dt oi m p l e m e n tq u e r yp r o c e s s i n ga n do p t i m i z i n g i nt h i sp a p e r , w eu t i l i z et h ei d e ao fu s i n gn e t w o r k so fw o r k s t a t i o n sf o rp a r a l l e lq u e r yp r o c e s s i n ，gandtheschemeo fa p p l y i n gp a r a l l e lt e c h n i q u e so nt h et r a d i t i o n a ls e r i e sd a t a b a s e sw ee x p l o i tt h et h r e ep a r a l l e l i s mo fr e l a t i o n a ld a t a b a s et oi m p r o v ep e r f o r m a n c eo ft h eq u e r yp r o c e s s i n gs y s t e m t h a nw ep r e s e n tap a r a l l e lq u e r yp r o c e s s i n ga r c h i t e c t u r e ，a n dp r o g r a mt oi m p l e m e n tas i m u l a t o ro fp a r a l l e lq u e r yp r o c e s s i n gi nl a n w ea n a l y z eo ft h er e s u l to ft h ee x p e r i m e n ta n dp r o v et h et r u t ht h a tt h er a t i o n a ld e s i g no fs y s t e ma r c h i t e c t u r ec a nr e d u c et h ec o s to fl o ws p e e dc o m m u n i c a t i o nn e t w o r ka n dg e tt h ep r e f e r a b l ep e r f o r m a n c e k e y w o r d ：m u l t i d i m e n s i o n a ld a t ad e e l u s t e r i n gt r e es t r u c t u r e sq u e r yp r o c e s s i n gn e t w o r k so fw o r k s t a t i o n s第一章绪论第一章绪论1 1 引言随着计算机应用领域的迅速扩大，数据库作为一项重要的技术，在各种应用中都发挥着越来越关键的作用，并逐渐呈现出以下特点：1 数据库规模越来越庞大，采用t b 级别的数据库已不鲜见。2 数据库查询越来越复杂，要求能够支持人工智能和专家系统的查询处理，以及具有多维分析和决策处理等功能。3 实时性要求越来越高，例如指挥决策系统、高速目标识别等对查询响应时闾的要求极为严格。因此，建立高性能数据库系统已经成为数据库发展的必然趋势。所谓的高性能数据库，即处理速度特别快和容量特别大的数据库。然而日益加重的负载，以及缺乏对高性能联机事务分析处理的支持，和不具备复杂查询操作的能力，使得运行在串行计算机上舶传统数据库管理系统无法再适应这种迅速增长的应用要求。无论是数据库容量的增大，还是数据处理的复杂化，都直接降低了传统数据库的查询璃应时闻和数据处理的吞吐量，v o nn e u r a a u n 的计算机系统结构已经成为建立高性能数据库系统的障碍，主要表现在以下凡个方面：1 日益增长的数据库规模和数据处理复杂性，使得单处理机系统难以提供足够的处理能力。无法利用数据库系统中大量面向集合的数据处理操作的固有并行性：2 该结构的计算机系统的存储器仅支持地址制导的数据存取方式，而数据库管理系统要求数据制导的数据存取方式，为了模拟该方式，系统增加了大量的存取路径，其结果只能是产生了巨大的维护开销，降低了系统的性能；，3 该结构的i o 设备通过数据通道与c p u 和主存储器相连接，其传输速度远远低于c p u 的数据处理速度。形成瓶颈，而数据库系统需要频繁地执行数据处理操作，从而使得i o 瓶颈问题显得尤为严重。该问题如果得不到解决，而只是单纯的提高处理机的速度或增加处理机的数量，并不能提高数据库系统的性能。7 0 年代以来，对于如何提高数据库的性能的研究就已经成为一个重要的课题。人们试图构造一种适用于数据库系统的专用计算机系统结构来代替v o nn e u m a n n 的计算机系统结构，但由于该结构的硬件设计与实现开销太大，专用并行数据库中数据分布和查询处理技术的研究数据库机器的研制失败了，使得这一课题的研究一度陷入了困境。随着并行处理技术的出现与发展，人们逐渐看到了建立高性能数据库管理系统的希望，并认识到，只有通过充分利用多处理器和多磁盘的并行性以提高处理能力和速度，才可以解决传统数据库系统性能的瓶颈问题。由此产生了以并行处理技术为基础的并行数据库系统，其中包括并行硬件结构、著行软件系统和并行算法等，各种高性能应用需求的不断涌现使得并行计算机的系统结构受到越来越普遍的重视，但相应的软件系统的发展却远远落后于硬件系统的发展，这在数据库技术应用领域中体现得更加明显。目前。并行数据库系统已经成为数据库领域中重要的研究课题，并取得了一些显著的进展，国内外已经出现了多个并行数据库原型系统和商业系统，专家预测，并行数据库技术必将成为未来高性能数据库系统的主流【lj 。1 2 研究现状进入9 0 年代以来，由于微处理技术和网络韵高速发展，以高性能的大规模并行处理机( m p p ) 为代表的并行计算机结构受到了越来越普遍的重视，例如出现了n c u b e 、p a r a g o n 、c m 2 、c m 5 等著名的并行处理系统。但相应的软件系统的发展远远落后于硬件系统的发展，这在数据库技术应用领域中体现得更加明显，随着基于网络的多计算机机群并行计算环境，如p v m 、m p i 等系统的出现，使得在m p p 基础上建立并行数据库系统成为可能。为满足日益扩大的应用需求，人们已在并行数据库系统方面开展了大量的研究，主要包括三个方面：数据是如何在多节点中存储分布韵，如何利用多机和多i o 设备设计出高效的并行操作算法，如何对查询处理操作进行优化以获取最快的响应速度。并且早在8 0 年代末，国外就相继出现了如g a m m a b u b b a 、v o l c a n o 、d b s 3 等并行数据库原型系统，国内也在9 0 年代先后开发出了黑龙江大学的h c l u s t e r 、中国人民大学的c o b a s e 、国防科大的p a r a b a s e 等原型系统。9 0 年代后期，并行数据库领域的研究有了很大的发展，出现了o r a c l e 并行数据库服务器、i n f o m i x 并行查询服务器等商业化数据库系统。虽然它们还不是严格意义上的并行数据库系统，但是已经能够支持并行数据处理，并有限地满足高速数据处理的需求。并行数据库的设计，是建立在一个朴素的并行观点基础上的，即在目前的软硬件条件下实现并行处理，将一个任务分配给若干处理机去完成。但如何建立并行数据库系统，却是一个非常复杂的问题，这其中包括对硬件的体系结构、软件的并行系统支持，以及数据处理的相关并行算法等的研究。而对并行算法第一章绪论的研究是实现并行数据库的关键问题，又分为数据分布算法、并行操作算法、并行查询处理与优化等多个方面，而每一种并行算法的设计，无不需要考虑到工作量、运行时间、处理机数目、加速比、效率、伸缩性等等，其复杂性远比顺序算法大得多，这些技术的研究与发展，对并行数据库的设计与实现产生着深远的影响。一个具有良好设计的并行数据库系统，能够使得绝大多数查询处理获得最小的响应时间。虽然传统的串行数据库的目标也是得到最小的响应时间，但它只需找到一个具有最小查询工作量的执行规划即可，这一规划在单机上必然具有最小的响应时间。但对并行数据库来讲，一个具有最小工作量的执行规划可能有很强的顺序性，无法达到并行的效果，因此它的查询处理及优化过程要比传统数据库复杂的多，需要涉及到并行系统的结构、数据在系统中存储、以及使用的数据操作算法、查询算法等【2 1 。当前设计并行数据库系统主要采用两种方法【3 1 ，一是扩充方法，即在现有数据库系统的基础上进行并行化，设计相应的并行查询处理结构；另一种是重写方法，即需要结合并行系统。设计数据库整体结构，给出合理的数据分布方法，并在此基础上，设计各种数据操作算法、查询处理算法、查询优化算法等。1 3 本文的研究工作本文的目的旨在对并行数据库设计与实现中的一些关键技术进行研究与探讨，重点在于研究以扩充方式设计并行数据库技术中的查询处理及优化系统的组织结构和处理模型，即如何利用并行环境减少单机工作量，得到最小的响应时间。作者结合局域网络环境，实现了对并行查询处理以及优化过程的模拟。本文首先介绍了并行数据库技术的理论基础，及其并行处理的体系结构，深入探讨了以重写方式设计并行数据库的数据存储问题，归纳总结了若干基于树结构的多维分布方法，分析比较了它们的优缺点，并重点介绍了基于k - d 树结构的数据分布方法的详细设计，简要说明了基于该方式的查询处理方法。作者认为，数据存储方法对于以重写方式设计并行数据库的系统来说，是最为关键的技术，因为任何数据操作算法和查询处理与优化算法都是建立在数据是如何分布的基础之上的，是需要与相应的数据分布算法相匹配的，因此一个设计良好的数据分布方法，特别是基于树结构的分布方法，将会使得系统获得较高的存储性能，便于数据操作，便于查询系统的设计与实现。其次，本文着重针对以扩充方式设计并行数据库的并行查询处理结构进行了研究，提出了一种并行查询处理结构框架的设计方案，这种方法在现有的数4并行数据库中数据分布和查询处理技术的研究据库基础上进行了并行化的设计，提高了数据库的查询处理能力。适用于基于工作站网络的并行数据库系统。最后，本文在局域网络环境下实现了这种设计方案的模拟，并对实验结果进行了分析和比较，对建立并行数据库查询优化体系结构及其查询规律进行一定的探索。1 4 论文各章节的安排本文对并行数据库的概念进行了全面的介绍，主要包括各种基于树结构的数据分布方法，以及查询处理及优化的设计实现。各章节基本内容如下：第二章系统的介绍了并行数据库技术的相关内容，包括数据库系统的概念，适用于并行数据库的并行处理体系结构，机群系统与并行软件环境，以及并行数据库系统的概念和设计与实现的方法，并对该技术发展中的一些问题进行了回顾与展望：第三章介绍了并行数据库中的数据存储技术，重点讨论了多维数据分布的问题，分析比较了现有的各种基于树结构的数据分布方法及其适用范围，给出了基于k - d 树结构的多维数据分布方法的详细设计。第四章首先简要介绍了基于数据分布的并行查询及优化技术的概念，给出了简单数据流查询方法的设计思想。随后，重点介绍工作站网络下实现并行数据库系统查询处理的概念，以及现有的查询处理结构和查询处理及优化的设计思想。第五章是作者在局域网络环境下实现查询优化的一个模拟系统，给出了并行查询处理结构框架的设计方案，模拟了查询处理及优化的全过程，并对实验结果进行了分析和总结。第六章结束语。第二章并行数据库技术第二章并行数据库技术2 1 数据库系统数据库管理系统( d b m s ) 是数据库系统的核心，它对数据库系统的功能和性能起到决定性的作用。它不仅能够将数据以一种预定格式进行存储，还能够回答通过查询语言提出的查询要求。其中以某种特定的数据模型存储的数据即数据库，数据库系统就是d b m s 及其管理的数据库的合称【4 1 。早期的d b m s 全部运行在单机上，被称之为集中式数据库系统( c e n t r a l i z e dd a t a b a s es y s t e m ) 。为了达到数据共享的目的，需要单机上的数据库系统能够连接起来进行通信和合作，这样产生了分布式数据库系统( d i s t r i b u t e dd a t a b a s es y s t e m ) ，其中每个单机上的数据库系统具有完备和独立的数据库功能。随着新硬件技术的发展，多处理机系统的计算机体系结构应运面生，这些计算机系统拥有多个处理机节点，依靠高速网络连接，适应了对高性能处理的应用要求，于是在此基础上产生了并行数据库统( p a r a l l e ld a t a b a s es y s t e m ) 。它与分布式数据库系统的主要区别有三点：1 并行数据库系统是一个单一的数据库系统，它的每个节点不具有自治性，分布式数据则是由多个数据库系统的组合而成；2 分布式数据库系统是将数据库分布于多机上，而并行数据库系统是将关系分布于多机上；3 分布式数据库系统以追求数据共享为目的，而并行数据库系统是以追求高性能为目的的。自7 0 年代出现了关系数据模型以后，关系数据库成为应用最为广泛的数据库系统，尽管当前出现了更先进的数据模型( 如面向对象数据模型等) ，但关系模型仍然倍受重视并不断被研究，特别是人们发现关系模型非常适合于并行处理，其自身存在的固有并行性成为建立并行数据库系统的理论基础，所以当前的并行数据库系统都是并行关系数据库系统。简单的说，关系数据库由一组关( r e l a t i o n ) 组成，关系又由若干个元组( t u p l e ) 组成，同一关系中的所有元组具有统一的模式( s c h e m a ) ，即由若干属性( a t t r i b u t e ) 来描述，其中属性的取值范围称之为该属性的域( d o m a i n ) ，如果某一属性可以唯一决定一个元组，则该属性就是键( k e y ) 。从形式上看，关系相当于一个二维的表( t a b l e ) ，属性对应表的列，元组对应表的行。关系模型提供了一系列关系代数操作，如逸耩( s e l e c t i o n ) ，投影( p r o j e c t i o n ) ，并行数据库中数据分布和查询处理技术的研究集合操作，连接( j o i n ) 操作等等。现实中许多查询都是由选择、投影和连接操作组成的，简称s p j 查询。最常用的连接操作是等连接操作，即一个操作数的属性等于另一个操作数的属性。而最复杂的连接操作是多元连接操作( m u l t i p l ej o i n ) ，它是由多个关系组成。由于连接操作在设计与实现上比较复杂，其执行花费也是巨大的，所以通常人们提到的查询优化处理都是主要是针对连接操作而进行的。2 2 并行处理的体系结构8 0 年代，美国学者m s t o n e b r a k e r 提出了三种用于构造并行数据库系统的并行计算结构：全共享结构( s h 缸e d e v e r y t h i n g ，简称s e 结构，又称共享主存储器结构，s h a r e d m e m o r y ，s m 结构) 、共享磁盘结构( s h a r e d d i s k ，简称s d 结构)和无共享结构( s h a r c d n o t l l i n g ，简称s n 结构) ，9 0 年代，g r a e f e 又提出了第四种结构，即分层并行结构( h i e r a r c h y 。s y s w m ) 1 4 1 ，如图所示：第二章并行数据库技术【c ) s n 结构( d ) 分层结构图2 1 几种并行处理结构模型s e 结构由多个处理机、一个共享主存储器和多个磁盘存储器组成，之间由高速网络连接，每个处理机可直接存取一个或多个磁盘存储器，它们之间的通信和数据交换通过共享的主存储器直接进行。该结构又称之为对称多处理机s m p ( s y m m e t r i cm u l t i p l ep r o c e s s o r s ) 结构。s d 结构由多个具有独立主存储器的处理器和多个磁盘存储器组成，每个处理机可以读写任何的磁盘存储器，处理器与磁盘存储器间由高速网络连接。其通信可以通过共享磁盘存储器，也可以通过高速网络完成。该结构又称之为c l u s t e r 结构。s n 结构由多个处理节点组成。每个处理节点具有独立的处理器、主存储器和磁盘存储器，节点间由高速网络连接。处理机问的通信完全通过高速网络实现。该结构实际上就是大规模并行处理结构m p p ( m a s s i v ep a r a l l e lp r o c e s s o r s ) 。分层结构结合了s e 和s n 的特点，将s n 结构中的每个节点扩展成一个超级节点( s u p e m o d e ) ，而每夸超级节点又是个s e 结构。因此，它具有相对灵活的特点。早在8 0 年代，数据库权威专家s t o n e b r e a k e r 就提出，s n 结构是建立并行数据库最理想的并行结掩，。这一观点已被普遍接受j 因为s n 结构具有最小的共享资源，从而使得资源竞争所带来的系统干扰能够达到最小；有较高的可扩展性。增加处理机不会带来处理枫闯的干扰；查询过程中两络中的数据通信量较小：在复杂数据库查询处理和联机事务处理过程中可达到接近线性的加速比。因此，在实际应用中，除了处理机个数较小的并行系统使用s e 结构外，其余均采用s n 结构。况且，目前最经济的并行处理结构就是基于局域网的p c机群系统，它是典型的s n 结构，由于环境与财力所限，研究人员通常会选择这一结构开展研究工作。为了不至于同其它结构的概念混淆，本文中提及韵处理机，均指s n 结构中的具有独立的处理机、圭存储嚣和磁盘存储器的处理节点。2 3 机群系统与并行软件环境近几年来，随着计算机网络技术的发展，产生了一种新的并行计算系统。即基于网络的计算机机群并行计算系统。它的特点是通过高速通信网络将多个独立的计算机系统连接起来以支持并行计算。机群并行计算系统中的每个计算机被称之为节点机，这些节点机可以是高档微机、工作站、小型机、大型机或巨型机。如果系统中所有的节点机都是工作站的话，则称其为工作站机群，这并行数据库中数据分布和查询处理技术的研究也是目前主要的机群并行计算系统，有许多针对并行数据库的研究都是基于这样的硬件环境而完成的。与大规模并行处理机( m p p ) 相比，机群并行计算系统具有易于实现、灵活性高的特点，能够方便的将不同体系结构的各种计算机连接起来，有机地形成异构并行计算环境，但也只有使用高档计算机的机群系统才能在性能上接近m p p 。m p p 是真正的大规模系统，可以是由数千个处理机组成的并行系统，这对机群系统来说是不现实的。实现机群系统最简单的方法就是通过局域网将多个计算机连接起来，但这样的系统弱点明显：多计算机间通信速度慢，处理节点性能不佳。只能运行粗粒度或较粗粒度的并行程序，并且计算机间的通信量不能过大。支持并行计算的并行编程模型嘲有很多种，通常使用的主要有三种类型：数据并行模拟、消息传递模型和共享交量模型。其中清息传递模型是最重要的也是最常用的编程模型，它有如下特征：1 多进程化：消息传递程序由多个进程组成，每个进程有自己的控制线程，可执行不同代码。支持控制并行( 多程序多数据流m p m d ) 和数据并行( 单程序多数据流s p m d ) 两种模式。2 异步并行性：消息传递程序的进程异步执行，可以使用路障函数对进程加以同步，不适合细粒度柏多指会多数据流模式( m i m d ) 。3 分离的地址空间：并行程序的进程驻留在不同的地址空间，一个进程的变量对其它进程是透明的，进程问交互需通过专有的消息传递函数实现。4 。显示交互：程序员需显示书写交互问题，如数据通信、同步、聚集等。5 显示分配：工作负载和数据坶需用户用显示方法分配给进程，通常使用单代码方式书写s p m d 程序来实现应用问题的求解。p v m 和m p i 是最常用的消息传递并行编程模型的软件包其中并行虚拟机p v m ( p a r a l l e l v i r t u a l m a c h i n e ) 出现较早，得到了广泛应用，可在伺构，异构型网络环境下模拟实现一个通用的基于分布存储的并行计算系统，提供了基于消息传递的并行程序设计接口，支持的节点机可以是并行机、向量机、工作站等，网络可以是以太网，f d d i 等。m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是9 4 年发布的消息传递接口标准规范，吸收了以往各种并行编程环境的特点，具有完备的异步通信能力和正式、详细的精确定义【 。这两种软件包都提供了对f o r t r a n 和c 的捆绑，己在p c 机、并行计算机或w i n d o w s 、u n i x 环境的工作站上得到了实现，即可以方便地运行在任何供应商提供的单台p c 机、工作站、工作站网络、m p p和在任何操作系统上。本文所实现的模拟系统，以局域网络环境为基础，采用p v m 进行并行程第二章并行数据库技术9序设计，详细说明请参阅第五章。至于具体实现的并行算法。与串行算法在复杂性分析上有很大区别，需要考虑的因素较多，主要的性能指标包括：工作量、运行时间、处理机数目、加速比、放大率、效率、伸缩性等，并且在算法的分析与设计时，需要全面考察这些复杂性测度，包括平均及最坏两种情况。通常我们主要考察加速l e ( s p e e d u p )和放大率( s c a l e u p ) j 挪j 个指标1 2 】1 3 1 。加速比：一个任务在单处理机系统中的执行时间“与该任务在 倍并行处理能力的系统中执行所需的时间的比值，即驴等( 2 )放大率& ：单处理机系统完成一个任务的执行时间岛与在n 倍并行处理能力的系统中完成玎倍该任务大小的任务所需的时间“的比值，即s 。2r t 。l s( 2 - 2 )理想情况下，并行系统应该具有线性加速比和线性放大率，即, 倍并行处理能力( 如疗个处理机) 能够以原来的l 拧的时间完成同一任务；或者能以相同时间完成”倍的任务。事实上，由于并行处理需要各个处理机间协同处理，+ 其开销会随着处理机数目的增长而增长，所以这两项指标都不可能达到线性，我们的所追求的目标是能够获得接近线性的加速比或放大率。图2 2 加速比曲线图中第一条曲线是理想情况下的加速比曲线，第二条曲线显示了随着硬件增加并没有产生加速的情况，第三条曲线则反应了影响并行性的三个威胁，即启动并行会增加系统开销；随着处理机数目的增加，于扰也会增加；最终，工作将会被划分的十分细致，导致了局部负载的倾斜使得系统性能下降。1 0并行数据库中数据分布和查询处理技术的研究2 4 并行数据库系统关系模型非常适合于并行处理，这表现在关系模型和关系数据库的非过程性查询语言为并行化提供了有利的条件，特别是关系查询本身就具有三个固有并行性；1 数据操作间的流水线并行性( p i p e l i n i n gp a r a l l e l i s m ) ：即进程间存在“生产者一消费者”的关系而产生的并行；2 数据操作间的水平并行性( h o r i z o n t a lp a r a l l e l i s m ) ：也被称为独立并行性，指在不相交的数据集合上的并行操作，是并行数据库使用最广泛的一种形式；3 单数据操作内的并行性( i n t r a - o p e r a t o rp a r a l l e l i s m ) ：指一个操作内部的并行执行如循环内的并行，是最小粒度的并行。前两种都是数据操作间的并行性( i n t e r - o p e r a t o rp a r a l l e l i s m ) ，如多元连接查询中的多个连接操作的并行执行。对于并行数据库而言，以上三种都可以归结为查询内的并行性( i n t r a q u e r y - p a r a l l e l i s m ) ，相对应的还有查询间的并行性f i n t e r - q u e r yp a r a l l e l i s m ) ，即多个不同的查询并行执行。其关系如图所示：图2 3 并行性分类应用并行性的主要目的是为了提高系统的性能，增加系统的吞吐率并缩短响应时间。研究表明，操作内并行性对于改善简单查询的性能特别有效；对于复杂查询，还需要开发操作问的并行。因此，在研究并行数据库系统的过程中。经常会涉及到这几种并行性。从总体而言。我们可以把并行数据库技术分为三个部分进行研究：若行数据库的数据存储技术、并行数据操作算法、并行查询及其优化算法。前面提到，并行数据库不同于分布式数据库的区别在于它的数据是以关系的形式分布在各个处理机上，如果分布不合理，将导致在查询处理过程中，并行性得不到充分的发挥，系统的资源遭蓟浪费，奁询响应时间增加，从而降低了系统的处理能力。因此如何分布数据对劳行系统的性能来说是至关重要的，这也就是数据存储技术研究的重点。第二章并行数据库技术现有的数据分布方法主要有两类：一维数据分布方法和多维数据分布方法，另外还有基于传统索引结构并行化的数据分布方法，这种方法多用于表示多维的数据分布。我们将在第三章中对基于树结构的多维数据分布方法进行重点介绍。并行数据库的操作算法是并行数据库区别于传统数据库系统的核心，是其利用多处理机和多i o 设备提高性能的关键。在过去的研究工作中，开发高效的连接算法成为对操作算法研究的重点问题，多连接算法具有o ( n2 ) 的复杂度，是极为耗时的数据库操作。其它的研究还包括了并行排序算法、并行选择、投影和集合算法等。我们将在第四章结合查询优化介绍并行连接算法外。其它不作为本文讨论的内容。并行数据库的研究工作，归根到底就是为了获得最快的查询效果，这样才能从根本上解决传统数据库的性能瓶颈问题。在前面的存储技术和操作算法的研究基础上，再来讨论查询处理及其优化，便使其有了数据依据和立论基础。因为优化总是相对而言，总是在定的存储结构的基础上，不同的数据分布方法制约着不同的查询处理和优化策略的选用。目前主要有两类查询处理蒂口优化方法：一类是并行数据流方法：一类是查询计划空间搜索方法。前者侧重于开发关系数据库的三种固有并行性，依据现有的顺序数据操作算法，实现关系查询的并行执行；后者以数据分布为基础，通过并行数据操作算法，对用户的查询要求进行处理，搜索并行查询计划空间，形成高效的并行查询执行计划。严格的来说，并行数据流方法实现的数据库系统并不是真正的并行数据库系统，它没有考虑到数据操作本身的并行处理，也没有考虑在并行计算环境下的查询优化问题，不能够充分发挥多处理机的并行性。但是，这种方法的优点在于它即不需要修改原有韵颓序操作算法，也无需重新设计新的并行数据操作算法，完全可以在现有的数据库理论、技术和方法的基础上实现并行数据库系统的查询处理及优化，所以我们的模拟系统采用的就是这种方法。2 5 并行数据库系统的设计与实现并行数据库系统可以通过两种方式进行设计与实现：种是扩充方式，即扩充传统的数据库系统，在不改动原有数据库系统核心的前提下，增加并行处理能力如o r a c l e 的并行数据库服务器；另一种是重写方式，即完全重新设计，以并行计算机为平台设计底层的存储结构、并行操作算法，以及并行查询处理及优化算法等，如g a m m a 并行数据库系统。坚并行数据库中数据分布和查询处理技术的研究扩充方式不修改基本的数据库操作算法和查询处理算法，只是在此基础上增加了对查询的并行处理，构造简单，实现了数据操作间的独立并行性和数据操作间的流水线并行性，却不易实现操作内的并行性，难以充分利用并行机提供的软硬件性能提高系统效率。通常设计此类系统，只需在传统的数据库系统之上。增加一个并行查询执行器。利用并行数据流方法，将查询操作分配到各处理机上。我们的系统就是采用这种方法设计与实现的，并对查询内、查询间的并行性进行了设计与开发。重写方式通常较为复杂，需要考虑并行计算机的系统结构，设计合理的底层存储方式，在此基础上实现高效的并行处理及优化算法。这种方式可以应用研究领域内最先进的理论成果进行设计，可以充分利用并行机的性能，实现高效的并行数据库系统，但它的缺点在于构造复杂，难于实现。国内外现有的此类系统多为并行数据库原型系统，其使用的数据存储方法多为简单的一维数据分布算法，距离实用化相差很远。由于设计良好的并行数据存储方式对于并行数据库的高效实现起到至关重要的作用，因此，我们在第三章中对多维数据分布方法进行了缨致的研究与探讨。2 6 存在的问题与发展展望9 0 年代以来，国内外对并行数据库的研究已经取得了很大的成果，但是还是有一些技术难点需待解决，主要有以下四个方面的问题：1 并行数据存储如何将关系分布到各个节点上，以获得并行处理最理想的加速比是当前研究较多的一个问题。现在已实现的系统采用较多的是一维分布方法，如r o u n d r o b i n 、h a s h 等，但它们有一个共同的缺点，那不能支持在非划分属性上具有选择谓词的查询；而现有的各种多维分布方法，虽然解决了戈 j 分属性与查询属性不一致的问题，但都实现复杂，受制约因素较多。因此，如何找到一种既能克服一维分布方法的缺点，又易于实现的方法，是当前的研究难点。2 数据倾斜问题数据倾斜( d a t as k e w ) ；黾指数据在处理机上分布不均而造成并行处理效率低下的问题。当前许多并行算法的研究基础都是假定关系在属性上分布均匀，这是不实际的。即使初始化数据时分布均匀。但随着频繁的增、删、修改数据，都会造成数据的倾斜。如何能够动态维护数据，使得数据倾斜的发生率降到最小，这对于并行算法的效率具有很大的意义。3 并行查询的优化问题第二章并行数据库技术当前使用的优化算法主要有两类，一类是先优化后并行，但缺点在于优化后的可并行潜力很低，具有很强的顺序性；另一种方法虽然同时考虑了优化和并行，但难度很大，往往只能使用启发式方法，效率不高。如何克服这两者的弱点也是一大难题。4 事务处理的研究由于当前的研究工作主要集中在对数据的查询处理上，专门研究并行数据库的事务处理的还很少，现有的研究都处于探索阶段。事务处理作为数据库的重要组成部分，相信在不久的将来，会有越来越多的学者会参与这一课题的研究。1 4并行数据库中数据分布和查询处理技术的研究第三章并行数据库数据分布的研究3 1 数据分布与关系分段并行数据库的物理存储，是并行数据库设计与实现的基础，主要是指如何在多处理机之间分布关系等数据库对象，从面达到最小化查询处理响应时闻的目的。我们一般把实现物理存储的方法称之为数据分布方法。它的研究目的在于将物理数据有规律地存储到各个处理单元上，以提高在负载平衡条件下执行数据查询操作的效率，增强系统的并发性能。此外，数据分布在一些文献上又被称之为数据划分、数据分割、数据分段、数据分配、数据放置等。一般在不引起误解的情况下，我们可以简单地将它们归结为数据分布。但这些概念并不完全一致，有一定的差别，我们简要说明数据分布到各个节点的过程，并对这些概念做一个总体的介绍：首先，每个关系可以被分成若干个被称之为片断( f r a g m e n t s ) 的数据子集。这一过程称为数据分段( d a t af r a g m e n t a t i o n ) ，也可以称为数据分布( d a t ad i s t r i b u t i o n 、d a t ad e c l u s t e r i n g ) 、数据划分( d a t ap a r t i t i o n ) 、数据分割( d a t as e g m e n t a t i o n ) 等。然后，系统将这些片断分配到不同的节点中去，这_ 过程称之为数据分配( d a t aa l l o c a t i o n ) 。数据分段与数据分配的整个过程我们可以使用数话放置( d a t ap l a c e m e n t ) 的概念来表示。但多数文献习惯于将这种数据在多节点间的分布的过程统称为数据分布或数据划分，我们沿用了这一习惯。数据分布过程中所使用的关系的分段主要有两种形式：垂直分段( v e r t i c a lf r a g m e n t a t i o n ) 和水平分段( h o r i z o n t a lf r a g m e n t a t i o n ) ，前者指通过关系进行投影操作产生若干片断，后者是将关系的元组化分成子集。并行数据库的各类存储方法都是使用水平分段的技术，因为它允许产生任意数目的分段，原始关系可以由片断的并集产生，较为灵活、简单，易于获得较高的性能。我们将水平分段基于一个属性的划分而产生的数据分布称为一维数据的存储方法：基于多个属性钓戈l j 分丽产生的数据分布称为多维数据的存储方法，以下我们将对这两种分布方法进行介绍。第三章并行数据库存储技术的研究3 2 一维数据分布方法一维数据的分布方法是最简单的数据分布方法，已被b u b b a ，g a m m a ，t e r a d a t a 等并行数据库原型系统所采用，它通过划分关系的一个属性的域值来划分整个关系，得到一组子关系，并在多个节点间分布这些子关系。主要有r o u n d - r o b i n 分布、h a s h 分布、r a n g e 分布、h y b r i d - r a n g e 分布等方法。首先，我们简单介绍一下r o u n d r o b i n 分布方法的思想。设处理机个数为p ，被分布的关系为r ，其中n 是r 的第i 个元组，该方法把 存储到第( i r o o d p )个处理机上。这种方法简单实用，当查询操作需要获得大量元组的时候，使用这种方法进行分布可以得到很高的性能，但当仅仅涉及很少元组的查询操作时，它也要求所有处理机启动工作，导致系统资源的大量浪费。而h a s h 方法通过h a s h 函数指定某元组分布到某个处理机上，与r o u n dr o b i n 分布方法相比，它可以支持在划分属性上具有低选择谓词的数据操作( 即涉及划分属性的选择查询，其结果集只有少数的元组) ，数据的存取被限定在少数处理机上，避免了不必要的开销。但是，该方法却使得数据在多节点上随机分布，不适合聚集( c l u s i g r ) 存储的要求，后者是经常会用到的。r a n g e 分布方法将关系划分成p 个连续的子集合，并依次分布到对应的处理机上，该方法综合了前两种方法的优点，但是数据的分布有可能并不均匀，最坏的情况下，关系中的所有数据都可能被分布在同一个处理机上，导致系统工作负载不均衡。产生数据倾斜。如图所示，其中下面的长方体表示关系，一个小方格表示一个元组徽r 醐然夕贰圈r o u n d r o b i n 方法h a s h 方法r a n g e 方法图3 1 一维数据分布方法总体丽言，一维数据分布方法都有一个共厨的闯题，即不能有效地支持在非划分属性上具有选择谓词的查询。当查询操作不涉及划分属性时，使用一维数据分布的并行数据库系统的查询效率一般都很低，而查询花费巨大。但是这种方法设计与实施都较为简单。为现有的很多并行数据库原型系统所采用。多维数据分布方法克服了一维方法的缺点，是当前研究的重点。1 6并行数据库中数据分布和查询处理技术的研究3 3 多维数据分布方法随着诸如g i s 等高级数据库应用的出现，一维数据分布方法己经不能满足系统应用的需求，多维数据分布方法应运而生。该方法是研究如何利用关系的多个属性对整个数据空间进行分布的方法，可以分成两大类，一类是一般的多维数据分布方法。一类是基于树结 句的多维数据分布方法。一股的多维数据分布方法又包括了顺序文件方法( s e q u e n t i a lf i l e sm e t h o d ) 、h a s h 方法和格文件方法( g r i df i l e sm e t h o d ) 等，前两种方法无需多讨论，由一维方法演化而来，而基于格文件的分布方法则是十分重要的类方法。基于格文件的方法把一个关系看作一个具有多个属性的文件，如果f c d 、d ，珧，则称f 是一个d 维文传，d 称为f 的第i 个属性的定义域，d x d ，d 。称为一个d 维空间。而一个d 维文件上的每个元组表示为d 维空阐上的一个点。因此，这类方法的关键问题是怎样在磁盘存储器上存储d 维空间中的点。通常，我们将d 维空间划分为若干个d 维超方体每个超方体对应一个磁盘物理页，d 缝空间的懿分鄂通过把每一潍的定义域戈| | 1 分为多个区闻采实现。该方法又具体分为五类算法：1 基于模的算法( m o d u l o b a s e d a l g o r i t h m s ) ，该算法是将数据块号依据处理机数目取模分布。如著名的c m d 方法( c o o r d i n a t em o d u l od i s t r i b u t i o nm e t h o d ) 它是由黑龙 互大学的李建中教授于1 9 9 2 年提出的，对多维数据分布的发展产生了巨大的影响。2