（计算机软件与理论专业论文）并行实时数据库的查询优化机制.pdf

华中科技大学硕士学位论文 摘要 f p r t s i 采用了s n 的体系结构，以开放源码数据库管理系统m y s q ld b m s 核心 为基础，对影响并行数据库系统效率的部分进行重写。用户的命令经主控结点变换 成并行执行规划后，各个处理结点只对局部数据库进行存取。 实时性主要考虑的是数据与事务的定时限制，而连接是数据操作中非常耗时的 操作，并且并行查询优化有着庞大的执行计划搜索空间，因此，p r t s i 尽可能地避 免数据偏斜，发挥各个处理结点的性能以加快连接和查询优化。 并行查询服务器采用两阶段优化策略，对经过预处理和代数优化后的语法树进 行如下处理：首先通过选择定律文件对复杂的选择条件进行合适的分解，使每个选 择条件下推到一个或两个关系中，其次通过选择关系的连接顺序生成算法以及复合 连接顺序生成算法来决定连接顺序，然后将该顺序执行规划并行化，最后汇总处理 结点的返回结果，按照用户的操作要求处理之后输出结果。 为了避免选择性偏斜和重分布偏斜，处理结点采用了有选择条件的并行连接改 进算法，该算法通过主控结点上面的连接属性值与分布结点号的对应关系，运用分 散复制的策略，使得数据经过选择操作后被均匀地重新分布到各个处理结点，而且 利用右深树的特点，对连接操作开发出算子间独立并行性和算子间流水线并行性。 实验结果表明p r t s i 避免了数据偏斜，有良好的并行能力，并且它充分利用了 右深树的特性，开发了算子间的流水线并行性，查询越是复杂，也就是说查询涉及 到有选择条件的多元连接时，p r t s i 的并行能力挖掘得越好。 ， 、7 、 关键词：并行实时数据库系统；并行连接改进算法；并行查询优化；流水线并行性 华中科技大学硕士学位论文 a b s t r a c t p r t s - i s y s t e m u s e ss h a r e d - n o t h i n ga r c h i t e c t u r e ，b a s e so nt h ek e r n e lo f m y s q ld b m s t h a to p e n ss o u r c ec o d ea n dn e w l yd e v e l o p st h ep a r t st oa f f e c ts y s t e mp a r a l l e l i s m t h e c o m m a n d so fu s e r sa r et r a n s f o r m e dt op a r a l l e lq u e r y p l a n sa n dp r o c e s s i n g n o d e s o n l yr e a d o rw r i t et h e i rl o c a ld a t a b a s e s r e a l - t i m es y s t e mm a i n l yc o n c e r n st h et i m er e s t r i c to fw a n s a f i o na n dd a t a ，b u tj o i n o p e r a t i o n sn e e dm u c h t i m ea n d p a r a l l e lq u e r yo p t i m i z a t i o n h a sh u g es e a r c hs p a c e ，t h e r e f o r e ，p r t s - is y s t e md o e si t sb e s tt oa v o i dd a t as k e wa n d t a k ef u l l a d v a n t a g eo fe v e r yp r o c e s s i n gn o d e s c a p a b i l i t yi no r d e rt oq u i c k e nj o i na n d q u e r yo p t i m i z a t i o n p a r e l l e lq u e r ys e r v e rm a k e su s eo ft w o - p h r a s eo p t i m i z a t i o ns t r a t e g ya n dd e a l sw i t h o p e r a t o r t r e et h a th a s p a s s e dt h r o u g hp r e t r e a t m e n t a n d a l g e b r ao p t i m i z a t i o n a s f o l l o w s ：f i r s td i s a s s e m b l e s c o m p l e x s e l e c t i o nc o n d i t i o n sa n dm a k e s e v e r y s e l e c t i o n c o n d i t i o ng od o w nt oo n er e l a t i o no rt w or e l a t i o n sb ys e l e c t i o nt h e o r e mf i l e ；s e c o n d l y d e c i d e sj o i ns e q u e n c eb ys e l e c t i o nr e l a t i o nj o i ns e q u e n c ea l g o r i t h ma n dc o m p o s i t ej o i n s e q u e n c ea l g o r i t h m ；t h e np a r a l l e l s t h eo r d i n a le x e c u t e s c h e d u l e ；f i n a l l y c o l l e c t sa n d d i s p o s e st h er e t u r nr e s u l t so fp r o c e s s i n gn o d e sa n do u t p u t st h eu l t i m a r e s u l t s i nd o i n gj o i no p e r a t i o n s ，t oa v o i ds e l e c t i v i t ys k e wa n dr e d i s t r i b u t i o ns k e wi nj o i n s w h e r es e l e c t i o n se x i s t ，p r o c e s s i n gn o d e su s e ss e l e c t i o nc o n d i t i o ni m p r o v e dp a r a l l e lj o i n a l g o r i t h m t h a t t h r o u g hc o r r e s p o n d i n gr e l a t i o n o fj o i nv a l u ea n du o d en u m b e ra n d d i s p e r s e - r e p l i c a t es t r a t e g y s ot h a td a t aa r ea v e r a g e l yp a r t i t i o n e da m o n ga l l p r o c e s s i n g n o d e sa n dt h r o u g ht h ec h a r a c t e r i s t i so fr i g h t d e e p f l e e i n d e p e n d e n tp a r a l l e l i s m a n d p i p e l i n e dp a r a l l e l i s ma r ed e v e l o p e d e x p e r i m e n t ss h o wt h a tp r t s - is y s t e ma v o i d sd a t as k e wa n dh a sn i c e rp a r a l l e l i s m p r t s - is y s t e mm a k e st h eb e s to fr i g h td e e pt r e e sc h a r a c t e r i s t i ca n dd e v e l o p sp i p e l i n e d p a r a l l e l i s m t h e m o r ec o m p l e x e rt h e q u e r i e sa r e ，t h a t s t h e s e q u e r i e si n v o l v es e l e c t i o n c o n d i t i o n sa n d m u l t i - j o i nq u e r i e s ，t h eb e t t e rt h ep a r a l l e l i s mi sd e v e l o p e d k e yw o r d s ：p a r a l l e lr e a l t i m ed a t a b a s es y s t e m ；p a r a l l e lj o i ni m p r o v e da l g o r i t h m ； p a r a l l e lq u e r yo p t i m i z a t i o n ；p i p e l i n e dp a r a l l e l i s m 华中科技大学硕士学位论文 1 1现代数据库系统的发展 1引论 层次模型和网状模型是第一代数据库的典型代表，现在已经发展到广泛应用的 关系模型，并在向对象关系型发展；数据类型也由当初简单的数值型和字符型发展到 包括大对象在内的复杂数据类型：编程界面也由导航式语言发展到非过程语言，以至 今天的可视化编程，图形用户界面变得越来越通用了【1 , 2 j 。 进入2 0 世纪8 0 年代以后，随着计算机硬件技术的提高，使得计算机应用不断 深入，产生了许多新的应用领域，如计算机辅助设计、计算机辅助制造、计算机集 成制造、办公自动化、地理信息处理、智能信息处理等等。这些新的应用领域对数 据库系统提出了新要求，产生了演绎数据库、面向对象数据库、工程数据库、时态 数据库、地理数据库、模糊数据库、主动数据库等新型数据库的研究【3 1 。 数据库技术和网络通信技术、面向对象编程技术、并行计算技术、人工智能技 术相互融合、相互渗透，数据库出现了许多新特点： 数据库规模十分庞大，m c t ag r o u p 的a a r o nz o r n e s 预测，2 1 世纪建立1 万亿 字节数据仓库的企业将从7 增至1 7 。据不完全统计，目前采用m m 数据库超过 1 t b 的客户就达2 0 多家。 数据库查询越来越复杂，人们期望数据库支持智能化应用的特性，要求在数 据库处理技术中融合人工智能和专家系统式的处理手段。数据仓库和数据挖掘应用 中要求支持用户对数据进行多维分析和获取决策信息，这不是简单的查询检索能完 成的。 数据模型发生变革，面向对象设计技术的出现导致了数据模型的变革，传统 的数据模型有层次模型、网状模型和关系模型，其中以关系模型的应用最广，但随 着处理对象的复杂性、全面性要求，又出现了基于面向对象设计技术的面向对象的 数据模型，可以说，它的出现是数据库技术发展的y - - 个飞跃【4 1 。面向对象数据库管 理系统具有抽象数据类型和类的封装性、层次性与多继承性等特点，在管理和操作 多媒体数据库方面具有得天独厚的条件。 华中科技大学硕士学位论文 数据类型不断扩充，随着企事业单位的信息资源管理涉及到大量非传统的复 杂数据类型，传统的数据类型不能满足非结构化的需要。新的数据类型不但要求支 持声音、图像、视频、文本、几何元素、时间段等数据类型，而且地理信息系统( g i s ) 、 多媒体信息系统( m d i s ) 等应用要求支持复合数据类型【5 6 j 。 实时性要求高，某些系统诸如指挥与决策支持系统、高速目标识别、大型股 票市场分析等应用对查询响应时间的要求极为严格a 1 2 并行实时数据库及其研究现状 并行实时数据库不是并行数据库和实时数据库在概念、机构、工具等方面的简 单集成，需要在二者的基础上对一系列问题进行研究和决策。并行数据库和实时数 据库在理论和实际两个方面都取得了很大的发展，雨并行实时数据库的研究还处在 一个起步阶段。 1 2 1 并行数据库及其研究现状 在实际应用中，很多部门都需要超级速度和超大容量的超级计算机。例如物探 部门的地震数据处理、气象部门的气象卫星数据处理、工程设计部门的有限元分析、 计算型流体学，以及军事部门的核爆炸模拟数据处理、经济部门的全国乃至全球经 济模型的数据处理等等：甚至高科技本身也需要超级计算，例如高分子合成、遗传 工程等等。因为硬件速度提高的幅度越来越小，硬件的改进是有极限的，所以，比 较现实可行的办法是研究并行处理技术，将一个任务分配到尽可能多的处理机去同 时完成。 最近十几年来，并行计算机系统的发展十分迅速，很多大规模并行计算机系统 ( m a s s i v ep a r a l l e lp r o c e s s i n g ) 已经投入市场，如n c u b e 、i p s c 、p a r a g o n 、k s r 一1 、 c m 2 、c m 5 等，并且由于高速通信网络技术和操作系统的进展，基于网络的多计算机 集群并行计算环境开始出现，如n e c t a r 7 1 、p v m t s 等系统。并行数据库系统引起 了学术界和工业界的密切关注。从1 9 9 0 年开始，每两年召开一次国际并行与分布式 信息系统学术会议，即i n t e r n a t i o n a lc o n f e r e n c eo n p a r a l l ea n dd i s t r i b u e di n f o r m a t i o n s y s t e m s 。1 9 9 1 年，美国创办了 p a r a l l e l a n dd i s t r i b u t e ds y s t e m s 国际学术刊物。许 多著名的国际学术会议和学术刊物( 如v l d b 、a c ms i g m o d 、i e e ed a t a 2 华中科技大学硕士学位论文 e n g i n e e r i n g ) 都开设了并行数据库系统专题吼 大量的研究工作者做了不少的研究工作，并开发出了许多著名的原型系统，国 外比较著名的有美国威斯康幸大学开发的g a m m a 系统1 1 0 j 及美国m c c 公司研制的 b u b b a 系统【l l 】，国内主要有中国人民大学的p b a s e 系统【1 2 】及华中科技大学研制的 p a r o 系纠”】。研究并行数据库管理系统( p d b m s ) 有以下几个问题需要很好地解 决： 1 ) 并行数据划分在并行体系的平台上研制p d b m s ，需要将数据库的关系分 布存放在各个结点上，以便获得并行处理的加速比。 2 ) 数据偏斜数据偏斜是指由于数据在处理机上的分布不均匀而造成各处理机 工作数据的差别，从而降低并行处理的加速比。 3 ) 并行查询优化在传统数据库中，只需要找到一个最小工作量的执行规划， 而在并行数据库中，一个最小工作量的执行规划可能有很强的顺序性，难以并行化。 4 ) 事务处理事务处理是所有数据库必须解决的问题。并行事务处理的研究需 要解决的问题还很多。 1 2 2 实时数据库及其研究现状 在现实世界中，有许多应用包含了对数据的“定时”存取和对“短暂有效”数 据的存取，例如，电话交换、空中交通管制、雷达跟踪、p i 系统、工厂生产过程控 制和c i m s 、证券交易等。这些应用一方面需要维护大量共享数据和控制知识；另一 方面其应用活动有很强的时间性，要求在一定的时刻或一定的时间期限内从外部采 集数据，按彼此的联系存取已获得的数据和处理采集的数据，再及时作出响应。同 时，它们所处理的数据往往是“短暂”的，即只在一定的时间范围内有效。但是传 统的数据库系统旨在处理永久性数据，其设计与开发主要强调维护数据库的完整性、 一致性，提高系统的吞吐量和降低系统代价，根本不考虑与数据及其处理相关联的 定时限制1 1 4 】。 实时数据库( r e a l t i m ed a t a b a s er t d b ) 就是数据和事务都有显式定时限制的数 据库。系统的正确性不仅依赖于逻辑结果，而且还依赖于逻辑结果产生的时i n 1 5 】。 从数据库的角度看，一个实时数据库典型地由三个紧密结合的子系统组成：被控系 统、执行控制系统、数据系统。被控系统就是所考虑的应用过程，称为外部环境或 3 华中科技大学硕士学位论文 物理世界、执行控制系统监视被控系统的状态，协调和控制它的活动，称为逻辑世 界：数据系统有效地存储、操纵与管理实时信息，称为内部世界。执行控制系统和 数据系统统称控制系统。内部世界的状态是物理世界状态在控制系统中的映像，执 行控制系统通过内部世界状态而感知物理世界状态，且基于此而与被控系统交互作 用，所有这些都与时间紧密相联。 实时数据库系统的特征主要包括三个方面【1 6 】： 1 ) 数据特征( d a t ac h a r a c t e r i s t i c s ) 因为实时数据库系统通常被用来监视和控制物理设备，所以实时数据库系统需 要存储大量的关于系统环境的信息。这些信息包括输入数据、系统状态和机器状态。 根据应用的不同，系统可能还要保持系统的统计信息，有时还要处理多媒体信息， 并且由于系统不断地记录信息，因此数据必须有时间属性方面的记录。在r t d b 系 统中，数据值随外部环境状态变化而频繁地改变，一个数据只在某一特定的时间段 内有效，所以其数据特征不仅包括数据库内部状态的一致性，还必须包括外部状态 与内部状态之间的一致性以及与其他被使用数据间的“时间一致性”。 2 ) 事务特征( t r a n s a c t i o nc h a r a c t e r i s t i c s ) 实时系统中的事务可以分为硬事务和软事务两种类型，其中硬事务是指时间约 束必须得到保证的事务，对这种事务来说，超过了事务的截止期会给系统带来灾难 性的后果；软事务也有时间约束，但是在处理过程中可以在超过截止期后对事务的 处理做些调熬，这些事务没有完全保证它们的截止期。事务的时间特征可以分为 两种： 定时限制事务的执行具有显式的时限，如截止期等。这是由于控制系统要随 时紧紧地跟踪被控系统而引起的。它要求r t d b 系统必须要有时间处理机构。 定时正确性事务能够按照合适的时间要求正确执行。这是由于要求数据对控 制系统的各种决策活动随时有效而引起的，它要求权衡定时限制与数据一致性等多 方面因素，提供合适的调度策略。 3 ) 性能特征( p e r f o r m a n c ec h a r a c t e r i s t i c s ) 传统数据库一个重要的性能标准就是事务的并发控制，而在实时数据库系统中， 系统的性能目标是在冲突的事务中通过使用序列化顺序减少事务的响应时间，因此， 4 华中科技大学硕士学位论文 实时系统最重要的性能特征就是提供可行性规划使事务能够在严格的截止期内得到 执行。 实时数据库的研究可以追溯到8 0 年代中期，研究并基本解决了实时事务( 非复 杂事务结构的软事务) 的处理，提出了一些实时事务的优先级分配方案以及相关的 事务调度和并发控制策略，例如悲观( p e s s i m i s t i c ) 和乐观( o p t i m i s t i c ) 方法，对复 杂事务模型如长事务( l o n gt r a n s a c t i o n ) 、嵌套事务( n e s t i n g t r a n s a c t i o n ) 以及协作 事务的正确性标准( 如非可串行化、准可串行化) 进行了比较深入的讨论并进行了 大量的实践工作。典型的原型系统有i i p r t d b m s 、h i p a c 1 7 1 、r t - g e n e s i s 、s t r i p 1 8 】 等。近年来，实时数据库系统已发展成现代数据库研究的主要方向之一，受到了数 据库和实时系统两个研究领域的工作者的极大关注。实时数据库系统正在对一系列 问题进行研究与决策：数据和数据库的结果与组织；事务的截止时间的软硬性；事 务的优先级分派与调度；并发控制的协议与算法；加调度：通信的协议与算法；查 询处理算法：数据和事务特性的语义及这种语义与一致性和正确性的关系等等。 1 2 3 并行实时数据库及其研究现状 现代的许多应用领域如：军事、股票证券、银行系统、电力和数据网管理、电 信实时计费系统等，方面要求维护海量的共享数据和控制知识；另一方面这些应 用活动具有很强的时间性，都要求在一定的时刻或某一时间范围内采集、存取和处 理数据。这就要求我们找到一种既具有较大的吞吐量又能保证事务截止期的数据库 系统，将并行数据库与实时数据库结合起来的并行实时数据库系统正好能满足这些 应用需求。 我们称具有实时事务调度能力的并行数据库系统就是并行实时数据库系统。并 行实时数据库并不是并行数据库与实时数据库在概念、原理、技术和方法等各方面 的简单拼凑，它需要对许多问题进行研究与决策，包括体系结构、数据分布、事务 的优先级分派与调度、并发控制的协议与算法、i 0 调度、通信协议与算法、查询优 化算法等等。 华中科技大学数据库与软件工程实验室最早开展了并行实时数据库的独创性研 究，提出了并行数据库与实时数据库的结合机制，开发出一个原型系统p r t s i 。在 数据划分及存储、并行连接及查询优化、事务模型、事务优先级分配、事务调度等 5 华中科技大学硕士学位论文 方面取得了一定的理论与实践成果。 1 3 本文研究的主要内容 p r t s - i 是一个基于客户服务器的并行实时数据库系统。本文以p r t s i 的研制 为背景，讨论了并行实时数据库的关键技术，着重研究了并行实时数据库的劳行连 接改进算法以及查询优化技术。第一章概要介绍了现代数据库的发展以及并行数据 库、实时数据库和并行实时数据库的研究现状；第二章介绍了并行实时数据库的关 键技术；第三章详细讨论了并行实时数据库的连接与实现算法以及并行查询服务器 的实现；第四章为结束语，对全文所做的工作进行了概括和总结。 6 华中科技大学硕士学位论文 2 并行实时数据库查询优化的关键技术 2 1 并行处理的关键技术 在并行实时数据库系统中，并行查询方面的关键技术包括：并行处理的体系结 构、并行处理的连接算法、并行查询及其优化技术、数据偏斜及其处理技术等，其 中并行处理的连接算法和并行查询及其优化技术必须考虑系统的体系结构，发挥这 种结构的长处，并且要具有良好的抗数据偏斜的能力，以提高整个系统的性能。 2 1 1 并行处理的体系结构 并行数据库系统有四种并行结构【1 9 2 0 j ： 1 ) 全共享结构( s h m c d - e , v e r y t l 6 n g ) 多处理机共享系统中的主存储器和磁盘资源，处理机、主存储器和磁盘存储器 之间由高速互联网连接。多处理机之间的通信和数据交换通过共享的主存储器直接 进行。 2 ) 共享磁盘结构( s h a r e d - d i s k ) 各个处理机拥有独自的主存储器，但是共享系统中的磁盘存储器之间和处理机 之间的通信可以通过共享磁盘存储器间接实现，也可以通过高速互联网连接实现。 3 ) 共享结构( s h a r e d - n o t h i n g ) 多处理机之间没有任何共享资源。每个处理机都有自己独立的局部存储器和独 立的磁盘存储器。处理机之间的通信完全靠高速互联网实现。 4 ) 分层并行结构 在分层结构中有许多超级结点由高速互联网连接。每个超级结点实际上是一个 s e 结构。这种结构中存在两种层次的并行性，若在分层并行结构中只保留一个超级 结点，就得到了s e 结构：若每个超级结点只配置一个处理机，就得到了s n 结构。 1 9 8 6 年，s t o n e b r a k e r 提出s n 结构是支持并行数据库系统的最好并行结构【2 l 】， 它具有如下一些特点【1 9 】： 1 ) s n 结构通过最小化共享资源来最小化由资源竞争带来的系统干扰。 2 ) s n 结构具有高可扩展性，其处理机的个数可以扩展到成千甚至上万，而不 7 华中科技大学硕士学位论文 增加处理机间的干扰。 3 ) s n 结构在数据库查询过程中需要在通信网络上进行的数据通信量较少。 4 ) s n 结构在复杂的数据库查询处理和联机事务处理过程中可达到线性加速比。 在p r t s - i 中，总体结构如图2 1 所示，它以原有的一个客户服务器结构的d b m s 为基础，设计实现基于无共享硬件结构的并行数据库系统。系统有一个主控机和n 个处理结点构成，客户应用程序通过网络或其他途径与系统建立联系，并通过主机 系统的应用通讯接口直接与主机通信。 客户端程序 s o l 千结果 l应用通信接口i i i t ：斛q , d b m sl 通信模块 l i 消息传递网络i ，fl 、 l通信模块 l 通信模块 ll 通信模块 l l 结点d b m s lfi 点d b m s 2 h 点d b m s n i 图2 1p r t s - i 总体结构 2 1 2 并行关系的连接算法 连接运算是数据库查询中最耗时和最重要的运算，也是构成多元连接查询的基 本运算。大量的研究表明，并行处理能够显著提高连接运算的效率。到目前为止， 并行连接算法的研究基本上都是在对应的串行算法基础上的并行化，形成了三种基 本的并行连接算法【2 羽。 由于嵌套循环连接算法必须存取两个连接关系的笛卡儿乘积，在顺序计算机环境 中，它一直被认为是效率最低的连接算法，然而，嵌套循环连接算法很容易并行化， 并且可以通过附加的计算减少多处理机间的通信开销。在具有大量处理结点的系统中 或在两个连接关系的大小差别很大的情况下，基于嵌套循环的并行连接算法的效率 8 华中科技大学硕士学位论文 远高与其它并行连接算法。并行嵌套连接算法的理论基础是这样一个等式： r i i s = r 1 l i s u r 2 i l s u u r n i l s 或者r l j s =r j i s l ur i x js 2 u u r l 陆 如果某个关系的连接属性上存在索引，该算法可以得到改进，从而大大改善该 算法的性能。 算法1 ) 基于嵌套循环的并行连接算法【2 3 】 输入：关系r 、s 以及r 和s 在n 个处理结点之间的分段r i 和s j ；假设s 较小。 输出：关系r 和s 的连接结果。 选择小关系s ； 把s 均匀的分布到多个处理结点； f o ri=1t o nd o 以流水线方式向n 个结点发送r 的元组； 结点i 在s i 查找在连接属性上与所收到的r 的元组匹配的元组， 进行s i 与r 的连接； 输出r 和s 的连接结果。 基于排序的并行连接算法由两个阶段组成，排序阶段和连接阶段。这个算法的 关键是如何将两个关系重新分布，也就是说，连接的两个关系被重新分布之后得到 的各个处理结点上的分片具有这样的性质：只有在具有相同结点号的处理结点上的 关系分片才有连接的可能性，如果结点号不相等，那么不同结点号的处理结点上任 何一个关系的连接属性的值域是不相交的。这样，按照连接属性重新分布之后，才 能保证各个处理结点连接结果的“并集”是正确的。 算法2 ) 基于排序的并行连接算法i 矧 输入：关系r 、s 以及r 和s 在n 个处理结点之间的分段r j 和s i ，i i a s h 函数h ： 输出：关系r 和s 的连接结果。 使用h 在n 个处理结点间分布r 和s 的元组； f o ri - 1 t ond o 处理结点i ，排序r i 和s i ； ( 9f o ri = 1t ond 0 9 华中科技大学硕士学位论文 结点i 使用连接算法完成r i 和s i 的连接； 输出r 和s 的连接结果。 基于h a s h 的并行连接算法很容易并行化。它通过一个定义在连接属性上的h a s h 函数把连接关系分解成n 个子集合，然后使用n 个处理机并行地完成连接操作。 算法3 ) 并行s i m p l e h a s hj i o n 连接算法i 驯 输入：关系r 、s 以及r 和s 在n 个处理结点之间的分段r i 和s “ 处理结点数目n ： h a s h 函数h ，以及溢出h a s h 函数h ； 输出：关系r 和s 的连接结果。 n 个结点并行地： 处理机i 从本地磁盘读取ri ，对其中每个元组的连接属性用h a s h 函数h 进 行散列，以决定其处理结点号j ，如果j = i ，则将其放入本地的写盘缓冲区，否则 放入相应的远程处理结点的通信缓冲区，当缓冲区满时，写回磁盘或向远程处理结 点发送，同时，处理结点接收并合并从其余结点发送过来的元组，在这一步结束时， 关系r 在各个处理结点间重新分布； 以同样的h a s h 函数在各个处理结点间重新分布s ； 各个处理结点分别定义自己的h a s h 函数h ，通过r i 创建h a s h 表，然后用s j 探测h a s h 表，并行地做本地结点的连接； 合并结果并输出。 基于嵌套循环的并行连接算法的思想是通过把某个关系复制到所有结点，实现 由多个本地连接合并为最终的结果；基于排序的并行连接算法首先将两个连接关系 在处理结点之间进行重新分布，使得只有在相同处理结点上的两个关系分段才有连 接的可能；基于散列的连接技术特别适合于并行处理环境，在大多数情况下，该算 法的性能也大大超过其他两类连接算法，并且在这个方面有大量的研究成果，比较 典型的有并行s i m p l e h a s h - j o i n 算法、并行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 算法渊等，它们的效率也存在着明显的区另f 2 6 ，2 7 1 。 2 1 3 并行查询及其优化技术 查询是数据库的最基本、最常用、最复杂的操作，数据库的查询一般都是以高 1 0 华中科技大学硕士学位论文 级查询语言表示，例如用s o l 表示。从查询语句开始，直到获得查询结果，需要一 个处理过程，这个过程就是查询处理。关系数据库的查询语言是描述性语言，仅表 达查询的要求，而不说明查询的过程，即用户不必关心查询语言的具体执行过程以 及由d b m s 确定的合理的、有效的执行策略。d b m s 在这方面的作用称为查询优化。 并行数据库系统中的查询优化与传统的数据库系统不同。在传统数据库中，找 到一个最小工作量的执行规划就是全部查询优化的任务，而在并行数据库中，数据 分片存储在各个处理结点上，一个最小工作量的执行规划或许会有很强的顺序性， 以至于将它分至各个处理结点执行时并不能够带来效率的提高。 1 并行查询优化主要涉及到的工作【冽： 1 ) 设计一个关系查询执行规划表示模型 并行查询执行规划表示模型定义并行查询执行规划的基本结构和应当附加的主 要标注信息，它描述查询执行的各种重要属性，为并行套询服务器提供足够的执行 信息。设计一个有效的并行查询执行规划表示模型是整个并行查询处理的基础和出 发点，这样任意个查询可以用模型中若干等价的规划表示，这些等价的规划构成 了查询的规划搜索空间。 2 ) 给定一个代价模型 代价模型的主要功能是按照给定的代价指标，根据操作的处理特性、操作间的 相互关系、数据的物理统计信息等计算查询执行规划的代价。由于操作间操作内并 行性、并行化的额外开销、流水线延迟、数据偏斜、操作间的资源冲突等因素的影 响使得精确的并行规划代价模型的构造非常困难。构造了并行规划代价模型后，这 个代价模型可以为任意一个规划计算一个代价指标。 3 ) 给出高效的搜索策略从中搜索出一个执行规划，使得代价指标最小 并行查询优化的主要困难在于如何缩减庞大的规划搜索空间。一个包含i 1 个关 系的查询的连接树的数耳具有指数级的复杂度，而一个顺序执行规划又可以通过不 同的并行化方法生成大量的并行执行规划，因此并行执行规划的搜索空间规模比顺 序执行规划的搜索空间又要庞大许多。如果说在传统数据库系统中对查询空间进行 穷尽搜索还有可能的话( 例如5 ) ，那么对于并行数据库系统来说，穷尽搜索规划 的性能是完全不可接受的。因此，必须采用适当的方法对搜索空间的规模进行限制， 尽量排除那些不可能是优化规划的执行规划。 l 】 华中科技大学硕士学位论文 2 并行查询的三种并行性 并行数据库系统中主要关注的是多元连接查询( m u l t i - j o i nq u e r i e s ) 的优化技术。 并行查询有三种并行性。第一种称为“算子内并行”( i n t r a - o p e r a t o r p a r a l l e l i s m ) ， 多个处理机并行地执行查询中的一个连接运算：第二种称为“算子间独立并行” ( i n d e p e n d e n tp a r a l l e l i s m ) ，多个处理机并行地执行查询中的多个连接运算，各个运算 的执行是相互独立的，没有数据依赖；第三种称为算子间的“流水线并行”( p i p e l i n e d p a r a l l e l i s m ) ，多个处理机并行地执行一个查询中的多个连接运算，其中一些连接运算 的执行结果以流水线的形式为另一些运算所用。在少量处理机的环境下，算子内并 行性足以提供满意的性能，但是随着多元连接查询中关系个数的增多和大规模并行 系统的愿意，单纯依靠算子内并行性往往难以发挥并行系统的效果，算子间并行性 的开发具有重要的作用。 在并行处理环境下，一个多元m j 查询q 的响应时间t ( q ) ：i m 常可以表示为下面 的函数：t ( q ) = f ( r ，a m r , p ) ，其中，r 是关系的集合；a 是并行结构的参数集合， 包括处理机数、磁盘数、内存容量和互联网结构等；m r 是执行连接的全部算法的集 合：p 是并行的形式。很明显，并行结构的引入使得并行优化仅考虑连接配对和算法 的选择不能保证并行优化的响应时间最短，还必须考虑各种并行的形式和每个连接 所分配到的处理机数目以及所使用的内存容量。 3 并行查询的三种查询树模型及其优缺点 在处理多元连接查询优化时，一个非常重要的任务就是确定连接的顺序。总共有 三种查询树模型【2 9 】： 1 ) 左深树( l e f t ，d e e p t r e e ) 所有内结点( 包括根结点) 的右孩子必须是叶结点( 基关系) 或者结果关系，如图2 2 所示。 2 ) 右深树( v , i g h t - d e e p t r e e ) 所有内结点( 包括根结点) 的左孩子必须是叶结点( 基关系) 或者结果关系，如图2 3 所示。 3 ) 丛深树( b u s h y t r e e ) 既不是左深树也不是右深树的查询树。 左孩子是基关系 左孩子是基关系 1 2 华中科技大学硕士学位论文 图2 2 左深树示意图图2 3 右深树示意图 一般说来，将连接的左变元存储在主存的数据结构中( 该关系称为“内关系”) ， 同时每次一块读入连接的右变元并将它的元组与已经存储的关系进行匹配( 该关系 称为“外关系”) ；所以上述三种连接方法中，只有基于排序的并行连接算法是对称的， 即左右变元所代表的意义是相同的。其他两种“嵌套循环”和“散列”连接算法则 是非对称的。这两种算法对“内”、“外”关系的处理是不同的。 1 ) 左深树的优缺点 左深树查询模型有两个优点： 任何时候所需的内存都比同样关系用右深树和丛深树的情况要小，在任何 给定时刻至多需要两个f l a s h 表的存储空间； 对于给定叶结点的可能的左深树的数目不会象丛深树的数目那样大。因此， 如果我们将搜索限制在左深树，查询计划的搜索将可以用于比较大的查询。一个包 含1 1 个关系的左深树的数目只有n ! ，而丛深树的数目为= ( 2 n 一2 ) ! ( n 一1 ) ! 。 但是左深树的并行性很有限。对于散列连接算法，左深树至多有两个连接操作 可以并行执行，数据操作间的并行性得不到充分的发挥；对于基于排序的连接算法， 尽管在每一步的连接中，左右两个排序操作可以并行执行，可是归并阶段必须要等 到最慢的一个排序操作完成后才能开始，n 个基关系的并行s c a n 和排序没有什么意 义；对于嵌套循环连接算法，左深树最多只允许一个连接算子同时运行。因此，在 多处理机环境下，左深树模型只支持“算子内并行性”和非常有限度的“算子间独 立并行性”。在大规模并行处理环境下，系统就有相当的并行处理能力可能得不到利 用。 2 ) 右深树的优缺点 华中科技大学硕士学位论文 由于左变元往往是“内关系”，因此对一个n 个关系的右深树，必须将( n 一1 ) 个关 系同时读入内存。根据右深树查询模型的流水线特性和将关系尽可能调入内存两个 方面，我们不难看成右深树查询模型有以下优点： 右深树模型产生的查询执行计划有相对高的并行性，n 个连接操作都可以并 行执行。 在内存足够大的情况下，连接的中间结果无须存储到硬盘并且右深树模型能 够充分利用内存资源，甚至将所有关系都调入内存，尽可能开发算子间的流水线并 行性。 由于右深树的流水线特性，中间结果流水线地被下一个连接使用，第一个最 终连接结果能够不必等到所有连接完成，而是在连接完成之前就产生，这个特性在 实际应用中是非常有意义的。 但是右深树模型要求系统有足够大的内存，以便整个查询执行的过程中把n 一1 个关系的h a s h 表都放在内存，当系统不能够容纳全部( n 1 ) 个关系的h a s h 表的时候， 就必须采用其他的解决办法，如片断式右深树调度技术、h y b r i d h 笛h f 冽调度技术等。 3 1 丛深树的优缺点 丛深树模型是最一般和最灵活的查询树模型，它的搜寻空间十分庞大，特别是 当n 比较大的时候，所有不同的连接结点的丛深树共有n ! c 棵，要从这么多的 丛深树中计算出执行性能最好的一棵丛深树，其选择代价十分巨大，而且，丛深树 的同步和调度也非常困难。因此，在优化阶段，一般都采用某种启发式优化方法， 以减少最优规划的搜索空间。 4 现有的并行查询优化技术 并行查询优化方法通常分为两类i 删：两阶段优化方法( t w o - p h a s eo p t i m i z a t i o n ) 【3 1 3 2 】和单阶段优化方法( s i n g l e p h a s eo p t i m i z a t i o n ) 。两阶段优化方法首先按照串行 数据库的优化技术构造查询的顺序执行规划，然后再把这个规划并行化，实现查询 的并行执行。这种方法的缺点是第一步产生的规划因为只考虑优化，可能有很强的 顺序性，并行化的潜力可能很少；单阶段优化方法则直接产生优化的并行执行规划。 这种方法虽然克服了前者的缺点，但难度很大，往往只能采用启发式方法，而启发 式方法是一种比较低效的方法。 华中科技大学硕士学位论文 在三种查询优化模型中，丛深树比左深树和右深树模型有更大的灵活性和潜在 的产生更高性能执行规划的可能，但是丛深树的搜索空间十分庞大。一个包含1 1 个 关系的查询的连接树的数目为( 2 n 一2 ) ! ，( n 一1 ) ! ，具有指数级的复杂度，而一个顺 序执行计划又可以通过不同的并行化方法生成大量的并行执行规划，因此并行执行 规划的搜索空间规模比顺序执行规划的搜索空间又要庞大许多，对于并行数据库系 统来说，穷尽搜索各个执行规划几乎是不可能的。因此，必须采用适当的方法对搜 索空间的规模进行限制，尽量排除那些性能不可能最优的执行规划。 2 1 4 数据偏斜及其处理技术 很多研究表明，在现实数据库中，数据的分布是不均匀的【3 3 州。在并行处理环境 中，最严重的问题莫过于处理结点之间的负载不平衡，从而造成某个处理结点成为 整个算法或过程的性能瓶颈，降低并行处理的性能。 1 数据偏斜的种类 并行连接算法可以分为四个阶段：元组从磁盘中扫描阶段；执行选择和投影谓词： 在各个处理结点划分元组以及重新分布元组；连接各个处理结点的元组。数据偏斜可 能发生在这四个阶段中的任何一个阶段，由此可以将数据偏斜分为四种类型【3 5 】。 1 ) 元组放置偏斜( t u p l e p l a c e m e n ts k e w ) 元组在各个处理结点上初始放置时发生的数据偏斜。 2 ) 选择性偏斜( s e l e c t i v i t ys k e w ) 在各个处理结点上执行选择谓词操作时，由于选择条件不同而造成的数据偏斜。 3 ) 重分布偏斜( r e d i s t r i b u t i o ns k e w ) 在数据库关系的连接属性中，一些属性值的出现频率大大高于均值，或者选择 的划分函数不好，因此，通过对连接属性进行重新分布后，某些处理结点的元组数 大大高于其他结点的元组数。 4 ) 连接乘积偏斜( j o i np r o d u c ts k e w ) 两个关系在进行连接以后产生的结果关系中，某些属性上的值分布不均匀，因 此，在结果的产生和输出过程中，某些处理结点的负担就大大高于其他结点。 2 数据偏斜的处理办法 处理数据偏斜的方法大致可以分为两类：偏斜预防方法和偏斜矫正方法。偏斜 华中科技大学硕士学位论文 预防要求选择好的划分方法，使每一个处理结点划分到相同的元组或相同的工作量。 这种方法包括w 6 l f 等人“调度h a s h 连接”技术1 3 6 1 以及i c a h u a 等人提出的“p a r t i t i o n t a n i n g ”技术1 3 7 1 。偏斜矫正方法是在发生了偏斜的情况下，采取某种措施消除或减 轻偏斜造成的影响，这种技术称为动态负