（计算机软件与理论专业论文）数据流中查询优化与迁移策略的研究.pdf

中文摘要 摘要 目前，信息处理技术的应用领域得到了很大的拓展，如：网络、金融、电子 商务、传感器网络等。在这些应用中，数据不再拘泥于静态的关系数据，而是一 种连续、无界、实时传输、不定速度的流式数据，即数据流。传统数据处理技术 突显出自身的局限性，数据流查询处理技术成为数据库研究领域的又一热点。 查询优化是查询处理中的关键技术。数据流中查询多为连续查询，查询一经 注册，该查询一直执行，除非人为加以制止。在一个查询执行期间，随着时间的 推移，系统的运行环境将不断地发生变化，数据流本身的一些特征也在不断地发 生改变。为提高查询效率，改善系统性能，系统需不断适应易变因素，对查询进 行动态调整。因此针对系统环境和数据流本身特征的易变性，查询优化以及优化 所涉及到的迁移技术应运而生，并成为数据流查询处理中关键技术之一。 针对数据流中流数据本身及执行环境的易变性与连续查询的特点，首先提出 了一个崭新的基于输出速率的代价模型m a ( r a t e m o d c i 然后在此代价模型的 基础上提出了查询优化策略，以动态选择具有最大输出速率的查询计划；并通过 实验验证了所提出的代价模型的正确性，以及查询优化策略的可行性。 在数据流的连续查询过程中，查询优化策略需动态地对操作符序列进行重排 列，这就涉及到新旧查询计划的迁移。在对传统的m o v i n gs t a t e 迁移策略进行深入 研究地基础上，提出了p m o v i n g ( p a r a l l e lm o v i n g ) 迁移策略。实验证明p m o v i n g 迁移策略可使动态的查询计划进行平滑过渡，避免迁移过程中出现无元组输出的 空白期，尤其是在系统资源紧张和数据流流速过大时，仍能确保较少中间元组和 较大的输出速率。 关键词：数据流；代价模型：查询优化；迁移策略 英文摘要 t h es t u d yo nq u e r yo p t i m i z e da n dm i g r a t i o ns t r a t e g yo v e rd a t a s t r e a m a b s t r a c t r e c e n t l y , w i t he x p l o s i v ea p p l i c a t i o n so fi n f o r m a t i o np r o c e s s i n gi ns e n s o rn e t w o r k s ， b u s i n e s sp r o c e s s i n g , n e t w o r k m o n i t o r i n g a n ds e c u r i t y , c o m m u n i c a t i o n ，i n d u s t r y m a n u f a c t u r i n g , a n dm a n yo t h e ra r e a s ，m o r ea n dm o r ed a t at a k et h ef o r mo fm u l t i p l e ， r a p i d , t i m e - v a r y i n g , p o s s i b l yu n p r e d i c t a b l ea n d u n b o u n d e ds t r e a m i n gd a t a ( d a t as t r e a m s ) r a t h e rt h a nf i n i t es t o r e dd a t as e t i na l lo ft h ea p p l i c a t i o n sc i t e da b o v e ，i ti sn o tf e a s i b l e t ot r a d i t i o n a l t e c h n o l o g y o np m c e s s i n gd a t a ，s od a t as t r e a m q u e r yp r o c e s s i n g t e c h n o l o g yb e c o m e s an e wa n dp o p u l a rt o p i ci nd a t a b a s er e s e a r c ha r e a q u e r yo p t i m i z e di s t h eu p p e r m o s tt e c h n o l o g yo fd a t as t e a mt e c h n o l o g i e s c o n t i n u o u sq u e r i e sa r et h eu s u a lq u e r i e so v e rd a t as t r e a mw h o s ea n s w e r sa r e c o n t i n u o u s l yp r o d u c e do v e rt i m eu n l e s ss t o p p e da r t i f i c i a l l y d u r i n gt h el q l nt i m eo fa q u e r y , t h ee x e c u t i o ne n v i r o n m e n t sc h a n g ec o n t i n u o u s l y m e a n w h i l es o m ep r o p e r t i e so f d a t as t r e a mi t s e l fc h a n g et o o a i m i n ga tt h e s ev a r i a t i o n a lf a c t o r sa b o u te n v i r o n m e n ta n d d a t as t r e a mi t s e l f , i no r d e rt oi m p r o v eq u e r ye f f i c i e n c ya n ds y s t e mp e r f o r m a n c e ，t h e q u e r yo p t i m i z e da n dn e x tm o v i n gt e c h n o l o g ye m e r g ea n db e c o m eak e yo fd a t as t r e a m q u e r yp r o c e s s i n gt e c h n o l o g i e s f i r s t l y , t h i sp a p e rp r e s e n t s an o v e lc o s tm o d e lb a s e do n o u t p u t r a t e - - - m a x r a t e m o d e la i m i n ga tt h ec o n t i n u i t yo fq u e r i e sa n dv a r i a b i l i t yo fs y s t e m e n v i r o n m e n ta n dd a t ei t s e l f ；s e c o n d l y ，o nt h eb a s i so fm a x r a t e m o d e l ，t h i sp a p e r a n a l y z e sa n dd e s i g n sc o m p l e xq u e r yo p t i m i z e da l g o r i t h mi no r d e rt os e l e c tt h e o p t i m i z e dq u e r yp l a nw i t ht h em o s to n t p u tr a t e ；a tl a s t ，t h i sp a p e rg i v e sc o r r e s p o n d i n g e x p e r i m e n t s ，t h e yp r o v e dv a l i d i t yo fm a x r a t e m o d e la n df e a s i b i l i t yo fq u e r yo p t i m i z e d s t r a t e g y m i g r a t i o ns t r a t e g ye m e r g e sb e t w e e no l dq u e r yp l a na n dn e wq u e r yp l a n ，b e c a u s e q u e r yo p t i m i z e ds t r a t e g yn e e d sd y n a m i c a l l yr e o r d e ro p e r a t o rl i s td u r i n gc o n t i n u o u s q u e r y t h i sp a p e rr e s e a r c h e sd e e p l y0 1 1t h et r a d i t i o n a lm o v i n gs t a t es t r a t e g ya n d p r e s e n t sa l ln e wm i g r a t i o ns t r a t e g y _ m o v i n g ( p a r a l l e lm o v i n g ) e x p e r i m e n t sp r o v e d 英文摘要 p m o v i n gs t r a t e g yn o to n l yi n s u r es m o o t hm i g r a t i o nb e t w e e nq u e r yp l a n s ，b u ta l s oa v o i d t h eo u t p u ts i l e n c ea n dr e d u c ei n t e r m e d i a t e t u p l ec o u n t sa n di m p r o v eo u t p u tr a t e e s p e c i a l l yw h e nt h es y s t e mh a si n s u f f i c i e n tp r o c e s s i n gp o w e rt ok e e pu pw i t l lt h eo l d q u e r y p l a n k e yw o r d s ：d a t as t r e a m ；c o s tm o d a l ；q u e r yo p t i m i z e d ；m i g r a t i o ns t r a t e g y 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：数据沆虫查逦馑丝生适整筮喳的研究：。除论文中已经 注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：谭谤闶洄年月2 牛日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书 本学位论文属于：保密口 不保密日( 请在以上方框内打“4 ”) 论文作者签名：芬翻导师签名：刮予 日期：炒1 年；月伯 数据流中齐询优化与迁移策略的研究 第1 章绪论 1 1 研究背景 随着计算机和网络技术的不断发展以及相关技术的进步，信息系统在制造、 运输、金融、n 等各行各业得到了广泛的应用，数据管理能力得到了长足发展。 近年来一种新的数据处理应用受到了相关领域研究人员的广泛关注，这种应用的 特点是：数据模型不是存放在传统数据库中的静态关系表，而是转瞬即逝的动态 数据流。在实际生活中，数据流应用非常广泛，下面就详细介绍一些这类应用的 实例： ( 1 ) l i n t e m e t 服务提供商，如电信等部门，管理着主干网络，通过高速交换机 连接。其数据流速可达4 0 g b i t s 。这些服务提供商的网络技术人员希望能够连续地 对网络中流动的数据进行实时分析，以获得有用的信息，如：当某i p 地址范围的 h t t p 包在特定数据链路中的传输量、某特定链路或路由器是否出现故障、哪个端 口正在产生最大数据流量等2 1 。 ( 2 ) 新一代的网络安全软件往往会给企业的大型网络提供集成式安全管理平 台，包括防火墙、入侵检测等。这些安全平台需要在以g b i t 计量的企业主干网中 执行复杂的实时数据分析任务，如u r l 地址过滤、恶意代码监测等 3 1 。除此之外， 网络安全领域还包含了其他问题，例如入侵检测( i n t r u s i o nd e t e c t i o n ) 、因特网权 限管理等。对流式数据的管理是这些应用领域的核心问题，由此兴起的数据流管 理技术正在成为数据库领域新的研究课题。 ( 3 ) 生产制造中，由于大量数字化生产设备及监测设备的应用，使实时生产 数据的提取成为可能。而且市场的发展要求也需要对产品生产和质量进行实时监 测分析1 4 1 。 ( 4 ) 股票和证券的价格实时产生，交易者希望能对此进行持续地实时分析， 得到有效信息而获利用。 类似需求还出现在许多其它领域中，如：医疗护理中对患者生理信息的监控 和分析、电子商务中交易信息的分析、传感器网络信息的分析等。我们可以发现 第1 章绪论 在上面的这些应用中，数据源都是以不断变化的数据流的形式存在。对于这类应 用，许多研究者试图使用成熟的传统数据库技术来解决数据流的查询、资源管理 等问题。但是，事实表明数据流与传统的数据库有着很大不同： ( 1 ) 传统的数据库是针对业务流程处理而设计的，只有当用户需要查询数据 或修改数据时，才通过执行s q l 语句来完成对数据库的操作，因此我们把数据库 看作是一个存储大量数据的被动的存储仓库，我们称之为“人主动数据库被 动”即h a d p ( h u m a n a c t i v ed b m s p a s s i v e ) 模式。而数据流是源源不断地到达， 查询处理器必须积极处理到达的数据，我们称之为“数据库主动人被动”即 d a i - i p ( d b m s a c t i v eh u m a n p a s s i v e ) 模式f 6 】。 ( 2 ) 传统的数据库只关心数据库的当前状态，而不太关心在到达目前状态之 前进行了哪些操作，除非查看日志，否则也无法得知数据库以前的状态。对于数 据流而言，不仅要对当前经过的数据流进行处理，也可能需要对历史数据流进行 查询等处理。 ( 3 ) 传统的数据库中保存着有限的数据，对其操作所需要的内存空间也有限。 与之相反，数据流是无限的，因为数据不断到达，就意味着对数据的处理露要无 限的内存空间。 ( 4 ) 在传统的数据库系统中，其查询的方式是执行一次查询就只显示一次查 询结果。对于不断有数据到达的数据流而言，进行一次查询，随着新数据的不断 到达，其结果应该是不断更新的，即要求连续查询( c o n t i n u o u sq u e r y ) 。 ( 5 ) 对于传统的数据库来说，其查询的结果都是准确的结果。而由于实时性、 数据量过于庞大等诸多方面原因，数据流的查询结果可能不完全准确，丽是为用 户提供一个近似查询结果( a p p r o x i m a t eq u a y a n s w e r ) 。 由此可见，在新的应用环境下，传统的数据管理方案无疑受到了极大的挑战， 亟待一种新型数据管理技术来解决数据流的相关问题。 1 2 研究现状 目前，关于数据流的研究和开发已经得到了学术界和产业界越来越多的关注， 并出现了一些初具规模的数据流管理系统原型。本节将阐述数据流研究中的相关 - 2 数据流中杏询优化与迁移策略的研究 概念和热点问题，并介绍几个现有原型系统的研究现状。 1 2 1 数据流与数据流管理系统 ( 1 )数据流 数据流( d a t as t r e a m ) 是由有限数据集中元素组成的数据单元序列，是一个由 有先后顺序关系且个数随时间不断增加的元组构成的数据集吲。 数据流的具体特征可概括为： 时效性。数据反映事件的状态，因此，数据流中的数据携带有事件的时问 特征，通常为它产生时刻的时间戳( t i m e s t a m p ) = 实时性。数据流中的数据是随着事件的发生联机到达的，并要求对它的处 理也是实时的： 无限性。数据流随时间延续而源源不断，理论上相当于有起点无终点的射 线。这意味着数据量是无限的； 瞬时性。数据流中的数据元素一旦流过，就不复存在，除非进行特意存储， 否则不可再次访问，而无限性决定了数据流是不可能被完全存储的。 ( 2 )数据流管理系统 数据流管理系统( d s m s d a t as t r e a mm a n a g e m e n ts y s t e m ) ：相应于数据库 管理系统，专门处理数据流的数据管理系统。 传统的关系数据库管理系统( d b m s d a t ab a s em a n a g e m e n ts y s t e m ) 的处 理机制如图1 1 所示。 ，日田 图1 1 关系数据库管理系统模型 f i g 1 1m o d e lo f d b m s 3 第1 章绪论 数据由l o a d e r 存储到磁盘所保存的关系当中，当用户或应用向管理系统提交 一个查询，管理系统处理之后将结果一次性返回给用户或应用，而这个查询则不 再有效。 数据流管理系统d s m s 如图1 2 所示。数据在线到达之后，并不是存储到磁 盘上，而是直接进入到流查询处理器当中，流查询处理器即时地对数据进行处理。 当用户或应用注册一个查询之后，流查询处理器将保持这个查询直至其失效为止， 也就是说用户注册的查询始终保持有效状态，这也就是连续查询的形式。数据流 入查询处理器之后，查询处理器直接根据当前注册的查询对数据进行操作，所产 生的结果同样以流的形式返回给用户或应用，当然也可以将结果保存成为关系形 式，不过这并不是数据流管理系统的主要工作。当系统资源不足时，需要考虑返 回近似结果，主要方法是返回部分结果或对需要处理的数据作载量脱落( 功a d s h e d d i n g ) 【8 】。d b m s 和d s m s 之间的比较，如表1 + 1 所示。 c = = c = = c = = o - c = = ： i n p u td a t a u s e r a p p l i c a t i o n t e r q e r y i暮黜t u n ) r e s u s t r e a m i n g q u e r yp r o c e s s o r 图1 2 数据流管理系统模型 f i 2 1 2m o d e lo fd s m s 1 2 2 数据流研究的热点问题 数据流的研究和开发己成为数据库领域的一个新的研究热点，从2 0 0 1 年起在 v l d b ，s i g m o d ，i c d e 等权威的数据库会议上已有部分成果发表。目前，研究 数据流管理系统的重点都放在查询处理上。作为一个新兴的研究课题，数据流研 数据流中查询优化与迁移策略的研究 表1 1 d b m s 与d s m s 的比较 t a b 1 1t h ec o m p a r i s o no fd b m sa n dd s m s d b m sd s m s 操作对象持久稳定的关系 瞬间数据流 查询性质一次性查询 连续查询 存储方式随机存储顺序存储 存储空问极大的磁盘存储有限的主存 时间粒度仅关注当前状态重点在历史和到达时间 数据速率 相对较低的修改速度 可能是多g b 字节的高速 实时性非实时服务实时服务 精确性数据集上的精确查淘历史查询，近似查询 存储计划由查询处理器和物 数据到达速率及其属性不可 存储计划 理数据库实现产生预计并可变 究中有许多开放的问题需要进一步的探讨和解决，归纳为如下几点： 数据流模型 数据模型1 9 】是数据管理和分析的基础，数据流是由一些有序的元组或对象组成 的序列，数据流不同于传统的存储数据关系模型，根据数据流的几个特点，数据 流模型需考虑下面两个问题：用有限来表示无限，应该采取一种把无限数据集 映射到有限数据集的方式进行处理；能够增量式的维护。在有限的内存中维持 一定数量的数据单元，根据一定的更新机制，进行实时的更新和维护。 数据流查询语言 查询语言的实际作用是能够描述查询需求并能够转换为系统所能实现的形 式。典型的查询语言就是关系数据库中的标准语言s o l 。在数据流的环境中，s o l 不再通用，通常流查询语言的表示可以有很多种方式：一是基于关系的查询语言， 例如东北大学定义的支持多目标的数据流操作语言【1 0 1 ，斯坦福大学定义的c o l l l l l ； 二是基于对象的查询语言；三是过程语言，通过符号化定义表示相应的操作和过 程。 数据流上的适应性查询处理 流式数据的查询处理有两个特性：实时性和适应性。简单的说，实时性是指 第1 章绪论 系统需在规定的时间内对查询处理任务有所响应；适应性【i 2 l 是指系统能随着数据 特性和系统属性的变化动态的调整查询执行的行为，以在满足实时性要求的前提 下完成查询任务。适应性查询一直是传统数据管理中的一个热点和难点，随着数 据库系统的演变和发展以及查询需求的不断提高，适应性查询的内涵也不断丰富， 特别是在流式数据这一新型的数据形式下，适应性查询就有了更重要的涵义和作 用。在第2 章，我们将对数据流查询处理机制进行深入的探讨。 数据流处理中的调度策略 调度优化【1 3 】是一种积极的优化策略，是影响系统的整体性能的因素之一。理 想的调度策略应当能够保证；在资源一定的情况下获得最优的性能；及时发 现系统过载，并触发相应解决机制；保证特定查询的q o s 需求；部署简单， 操作方便。在调度实施过程中，系统为达到各种性能指标的要求会发生冲突，例 如较小的响应时间必然要求较大的内存。所以对实际系统而言，寻找各种指标的 平衡至关重要。 数据流系统中的负载调整 当突发流量超过系统的处理能力，如果不采取相应的措施进行负载调整，会 导致整个系统的吞吐量和响应时间都恶化，系统应能够通过调整查询处理策略， 适应性地满足它的实时处理要求。主要采用以下几种方法对系统的负载进行调整： 一是l o a ds h e d d i n g 技术【引。即在保证满足查询要求的q o s 前提下，对数据进行随 机的丢弃；二是采用无损的或有损的数据压缩技术，通过减少数据容量，达到减 轻负载的目标；三是采用速度截流阀r a t et h r o t t l i n g 技术1 1 4 1 ，通过限制输入流速， 达到减轻负载的目标。 数据流查询中的近似计算 为了获得数据流上的连续查询的精确结果，查询处理所需要的内存会随着数 据量的不断增加而变得无界。而对于数据流的处理来说，外存的算法是难以满足 实时性要求的。此外，系统负载超出系统的处理能力时，如突发流量，数据延迟 等，可能导致系统总体性能下降甚至出现错误。因此，在数据流管理系统中广泛 的使用了近似计算的方法，在部分牺牲精确性的条件下获得处理时间的减少和存 储空间上的节省。而且在大多数实际应用领域中，高质量的近似结果( a p p r o x i m a t e r e s u l t s ) 是完全可以满足应用需求的。近似查询( a p p r o x i m a t eq u e r y ) 【冽是d s m s - 6 数据流中查询优化与迁移策略的研究 中重要的数据处理方式，已逐渐成为数据流研究领域的一个热门话题。 1 2 3 数据流的研究现状 二十世纪九十年代末以来，数据流模型在很多新型应用中广泛出现。早在1 9 8 0 年，m u n r o 和p a t e r s o n l l 6 1 就开始研究如何计算数据集合的分位数，他们仅利用 0 | v l 的空间复杂度，就可以利用p 次遍历精确获得分位数。这种利用较小的内存 空间单遍扫描数据集合获得近似分位数的方法被看成是数据流研究的雏形。1 9 9 2 年，c a l i f o r n i a 大学的o s t o t tp a r k e r 等人在t a n g r a m 建模环境的开发中提出了 对伪真数据的分析方法m ，使用流处理技术和复杂数值计算来分析大量已存储的 数据。1 9 9 8 年，h e n z i n g e r 等人制定了数据流模型【1 s 】。 2 0 世纪9 0 年代末，随着计算机及相关设备性能的提高、网络技术的进步、 数据流处理需求的增加，许多研究机构从不同角度对数据流处理技术进行了研究。 近几年，许多研究机构都推出了自己的数据流系统模型。最具代表性的研究项目 有：斯坦福大学的s t r e a m l 9 1 ，布朗大学、布兰蒂斯大学、麻省理工大学的 a u r o m 【1 9 l 、加州大学伯克利分校的t e l e g r a p h c q 2 0 1 等。其他的如n i a g a r a c q 2 1 1 、 t r i b e c a l 2 2 1 、a r g u s 系统【2 3 1 ，r e a l s t r e a m ! 驯系统等。 s t r e a m s t r e a m ( s t a n f o r ds t r e a md a t am a n a g e r ) 是斯坦福大学推出的一个通用型数 据流系统模型，是以关系形数据为基础的数据流管理系统系统的设计目标是： 在资源紧张的情况下，以有效方式给出近似查询结果，其重点在于内存管理和近 似查询。主要研究问题有：自行设计的连续查询语言c q l 1 1 1 ，存储和缓存管理【矧， 用户和应用程序接口，查询算子调度1 2 6 】等。s t r e a m 系统的整体构架如图1 3 所 示。 图1 3 左侧是输入数据，图的上部说明了用户或应用可以注册查询，注册后 的查询将一直保留到显式注销为止。连续查询的结果通常以流化( t h r o w ) 的形式 传送，但他们也可以保存为关系的形式( s t o r e ) ，并可以根据时间进行修改。对已 经流过去的元组，s t r e a m 系统通常将实效性不强的数据作一定的处理后保存在 s t o r e ，多数情况下不保存原始数掘。当然在部分应用中原始数据可能要保存下来 ( s t r a t c h ) ，主要是用作一些离线处理，比如消耗比较大的分析或挖掘。 第1 章绪论 s t r e a m l s t r e a m 2 囝囝国 图1 3 d t r e a m 结构图 f i g 1 3a r c h i t e c t u r eo fs t r e a m t e l e 伊a p h c q 加州大学伯克利分校的t e l e g r a p h c q 系统同样是一个通用的数据流管理系统， 目前主要应用在传感器网络上。图1 4 给出了t e l e g r a p h c q 整体系统框架。 图1 4t e l e g r a p h c q 框架 f i g 1 4a r c h i t e c t u r eo ft e l e g r a p h c q 数据流中查询优化与迁移策略的研究 图1 4 中的三个椭圆部分组成了t e l c g r a p h c q 的处理模块，这些模块通过共 享的内存( s h a r e dm e m o r yb u f f e rp 0 0 1 ) 进行通信，t e l e g r a p h c q 的前端( f r o n te n d ) 包含监听器( l i s t e n e r ) ，目录( c a t a l o g ) ，语法分析器( p a r s e r ) ，规划器( p l a n n e r ) 和微型执行器( m i n i e x e c u t o r ) 组成。实际的查询执行是在t c l e g r a p h c q 的后端 ( b a c ke n d ) 中进行的。 t c l e g r a p h c q 的核心为e d d y 2 们，e d d y 是一个自适应查询引擎，用来处理不稳 定和不可预知环境下的查询效率问题。e d d y 的特点在于它能够对操作符进行排序， 即可以动态地调整每个元组经过的路由，也就是说e d d y 对查询计划的调整精确到 了元组的粒度。 加州伯克利分校还设计并实现的适应性查询引擎c a c q i 2 s l 并f lp s o u p 2 9 1 ，c a c q 即在查询处理中采用对谓词的分组过滤方式，使选择谓词可以批处理。p s o u p 的特 点是将查询也看作一个流，查询处理的执行过程就是查询流和数据流的连接过程， 这种方法没有明显的操作符结构。 a u r o r a 布朗大学的a u r o r a 系统是用于网络监控应用而开发的数据流管理系统。a u r o r a 系统的核心包括一个庞大的触发器网络，即对每个系统中的检测应用，检测管理 器都要为它生成并添加一个或多个触发器。a u r o r a 的体系结构如图1 5 所示。 j 。 ln k 固一g o o o o 一 l 两i 压嚣卜舢n -is c h c d u l c rl u 时o o o d d - u i - b u f f e rm a n a g e r il i - j 3 b o x p r o c e s s o r s 压! 竺! ! 习魍 i 国一嬲。| 。厂瓦i 厂研 剑- 0 咖口二1 1 is h e d d e tl l m o n i t o rr - 圈1 5a u r o r a 的运行时体系结构 f i g 1 5r u n t i m ea r c h i t e c t u r eo f a u r o r a - 9 第1 章绪论 a u r o r a 系统既有查询计划编译期的优化，也有通过触发器网络进行的运行时 动态优化【3 0 l 。a u r o r a 系统中把各种操作符做成“盒子”的形式，用“箭头”将盒 子连接起来形成元组需要经过的路由，元组进入系统后按照此路由完成查询计划。 m e d u s a m e d u s a 3 1 】【3 2 】【3 3 l 是麻省理工学院推出的分布式数据流系统，以a u r o r a 系数据 流系统中负载管理技术应用研究系统作为单个节点的数据流处理引擎，以重叠网 络为基础，将多个含有a u r o r a 的节点连接起来，形成分布式数据流系统，含有 a u r o r a 的节点被称为参与者。每个参与者都是经济上独立的管理者，管理着一定 数量的节点、数据源及代理。m e d u s a 系统将数据流处理任务分发给参与者，利用 价格模型规范参与者的行为，组织参与者相互合作共同完成数据流处理任务。其 结构如图1 6 所示。 a d m i n i s t r a t i v eq u e r yf r o m t u p l e sf r o m m e s s a g e sa n d c o m m a n d sc l i n e n ta n dr e s u l t d a 诅s o u r t u p l e st o f r o m t oc l i n e o t 0 t h e rm e d u s an o d s 图1 6 m e d u s a 结构图 f i g 1 6 a r c h i t e c t u r eo fm e d u s a 1 3 本文的主要工作 本文针对数据流中查询优化问题进行详细讨论，主要完成了以下两个工作： 数据流中查询优化与迁移策略的研究 ( 1 ) 针对数据流中流数据本身以及执行环境的易变性与连续查询的特点，首 先提出了一个崭新的基于输出速率的代价模型- - m a x r a t e m o d e l ，然后在此代价 模型的基础上提出了查询优化策略，以动态选择具有最大输出速率的操作符序列， 并通过实验验证了我们所提出的代价模型的j 下确性，以及查询优化策略的可行性。 ( 2 ) 深入研究了动态查询计划的迁移策略，并在传统的m o v i n gs t a t e 迁移策 略基础上提出了p m o v i n g ( p a r a l l e lm o v i n g ) 迁移策略。该迁移策略可使动态的查 询计划进行平滑过渡，避免迁移过程中出现无元组输出的空白期，尤其是在系统 资源紧张和数据流流速过大时，仍能确保较少中间元组和较大的输出速率。 1 4 本文组织结构 全文共分为五个章节，主要内容安排如下： 第1 章是绪论。主要介绍数据流研究背景、研究现状及文章组织结构。 第2 章是优化代价模型m a 】【r a t e m o d c l 。首先介绍数据流中查询处理机制 及特点：然后对现有的代价模型进行了分析和比较；最后提出了基于输出速率的 m a x r a t e m o d e l 代价模型。 第3 章是m a x r a t e m o d e l 代价计算及优化策略。基于m a x r a t e m o d e l 代价模型， 本章详细讨论了不同操作符的代价计算，并在此基础上提出了查询优化策略，最 后用实验来验证了该代价模型和查询优化策略的正确性。 第4 章是p m o v i n g 迁移策略。本章首先对m o v i n gs t a t e 迁移策略进行了深入 研究，提出了一个改进的p m o v i n g 查询计划迁移策略，并用实验证明了该迁移策 略的优越性。 第5 章是总结与展望。本章对论文所做的工作进行了总结，并对将来的研究 工作进行展望。 第2 章优化代价模删- - m a x r a t e m o d e l 第2 章优化代价模型州a x r a t e m o d e 查询优化在传统关系数据库中有着非常重要的地位，对于前沿的数据流技术， 查询优化同样也是重点研究问题之一。而一个查询计划的优劣通常依据于具体的 代价模型进行度量。本章首先介绍了数据流中查询处理的特点，确定了查询优化 的角度；随后参考了传统数据库的代价模型，并对当前较为通用的数据流代价模 型进行了分析与比较；针对数据流的特殊性，详细分析了数据流中多种易变因素， 从而抽象出代价模型的各参数；最后提出了基于输出速率的代价模型一一 m a x r a t e m o d e l 。 2 1 数据流中的查询处理机制 2 1 1 数据流中的连续查询 数据流上的查询与传统数据库中的查询类型基本上相似，但有一个明显的区 别：数据库中的查询主要是一次查询，而数据流上的查询则更多的是连续查询。 一次性查询( o n e t i m eq u e r i e s ) 是对数据集在某个时间点上瞬时状态的一次计算， 再把结果返回给用户。传统的d b m s 查询通常都属于一次性查询。相反，连续查 询( c o n t i n u o u sq u e r i e s ) 是在数据流连续到达情况下的持续计算。连续查询的答案 是基于时间的，它反映了到目前为止己到达的数据流的情况。当新的数据到达时， 连续查询的结果可以被存储或更新，有时候查询结果本身也可表现为连续的数据 流。与一次性查询相比，连续查询更适合面向数据流的查询操作。数据流中的查 询多为连续查询，即只需发送一次查询请求，查询便一直处于不断运行的状态， 它是对数据流的连续处理计算。 数据流上的查询还可以分为预定义查询和即席查询两种查询形式。预定义查 询注册到系统后，主要针对数据流后续到来的数据计算查询结果；而即席查询是 针对数据流中流过的数据进行查询，郎对历史数据进行查询。由于系统无法保存 数据流流过的所有数据，系统只能通过提取和组织流过数据的概要信息来支持即 席查询，因此即席查询一般只能得到近似的查询结果。 数据流中查询优化与迁移策略的研究 2 1 2 数据流中通用操作符的查询处理 本文涉及的操作主要包括选择操作、投影操作与连接操作，其它的操作本文 没有进行相关讨论。 选择操作 选择操作是查询中最普遍的一种操作，它在查询中起到的是一个过滤器的作 用，对于符合条件的元组即输出，而不符合的就丢弃掉。 投影操作 投影操作是根据查询的需求而有选择地保留元组属性列的一种操作。由于投 影操作不需要在执行的过程中保存数据元组的状态和属性值等信息，所以每个数 据元组都是以完全流水化的形式通过投影操作符。 投影操作主要用来产生最后查询所需的结果，所以一般来说投影操作符出现 在查询计划树的根部，但是投影操作也可以用作对查询计划的优化，在查询计划 的适当位置加入投影操作，去除掉在查询执行过程中不使用的属性，可以缩减元 组的大小，相应地也就减少了查询执行过程中中间队列的内存消耗。 连接操作 连接是一种非常重要的查询类型，在数据流系统中也具有其自身的特点。传 统的连接操作算法主要处理的是静态数据，并不完全适用于流数据的连接，所以 需要在他们的基础上加以改进扩充。由于流数据具有连续、无界、速度不定等特 性，并且数据流系统主要是在有限的内存中执行，那么当进行连接操作的时候， 一端输入的数据是不可能与另一端的所有数据都进行连接的，这就需要在连接操 作的两个输入流上加入窗口约束条件。由于数据流具有无限性和不确定性的特点， 所以在连接的过程中需要选择适当的算法。 从上面的分析可见，根据对元组的访问方式，数据流管理系统中的查询操作 符可以分为两大类：“储流式操作符”和“流水式操作符”，如表2 1 所示。 对于投影，选择等操作来说，输入元组经过操作符处理就可以得到相应的操 作结果，所以形象的称作“流水式操作”。这种操作能够在数据流上一次扫描的过 程中完成。 1 3 第2 章优化代价模型- - m a x r a t e m o d e l 而对于连接( j o i n ) 操作来说，操作的语义要求只有在获得所有参与操作的数 据元素后才能获得准确的运算结果，故称作“储流式操作”。而数据流上一次扫描 的操作需求使得这种储流式操作在操作的过程中出现了阻塞。数据流的无限性和 实时性决定了无法、也不可能在所有的数据元素上操作以获得语义正确的块操作 结果，这有失数据流上连续查询的意义。 表2 1 操作符分类 t a b l e 2 1c l a s s i f i c a t i o no fo p e r a t o r s 流水式操作符储流式操作符 举例选择，投影连接 对每个操作对象一次操作后即可对全部的操作对象操作后才能获得 操作语义 获得相府的结果，即：精确的输出结果，即： r e s u l t s 。t 。蛔f 。)g e $ 础- o 搪蛳， ) 对输入元组的处理，不需其他元对输入元组的处理，需要借助保存 特点 组的信息即可得出结果的历史数据信息才可得出结果 流水式一次性扫描操作，在限定的操作范围内进行局部操 处理方法 可获得精确的结果作，获得一定精度的近似结果 目前，数据流上连接查询这种“储流式操作符”的实现方法主要是基于窗口 技术。现将数据流中窗口的相关概念介绍如下。 窗口：窗口是对数据流上数据的区域性限定，即针对数据流的无限性所做的 处理，使查询对数据流所做的操作全部限定在窗口范围之内。 滑动窗1 3 1 3 4 1 ：滑动窗i ：i 是按照窗口的移动形式划分的，即窗1 ：2 1 的开始和结束 边界同时都动态向前滑动，滑动式窗口的起始和结束都没有明确的定义，定义的 是窗日的长度，窗口保持一定的长度在流数据上进行滑动，一个新数据到达后， 则将窗口中最旧的数据从窗口中丢弃，新数据进入窗口。 基于时问的滑动窗1 ：2 1 【3 5 】：滑动窗口的长度是时间单位，即基于时间的滑动窗 口限定的是窗口内元组所跨越的时间长度。 数据流中卉询优化与迁移策略的研究 对储流式操作符来说，它保存的历史数据的信息量与查询定义的时间窗口大 小紧密相关，其特点与维护方式也与时间窗口基本一致，所以在很多系统中，储 流式操作符较常见的实现方式是在定义操作符时，将查询语句中描述的窗口信息 ( 窗口类型、大小等) 直接赋予操作符，这样查询中每个储流式操作符都带有窗 口，目前多数系统中储流式操作符进行操作的时候，主要根据查询语句所给出的 窗口信息来维护自己的窗口。本文中，我们规定用户提出的响应时间的大小即为 基于时间的滑动窗口的大小。因为基于时间的滑动窗口太大，不能在满足用户响 应时间的基础上得到查询结果，同时在查询中也会占用大量的内存保存过多无效 过期的元组。基于时间的滑动窗口太小，则在满足用户响应时间的基础上，忽略 了用户需要的数据，从而使查询结果不够精确。因此本文的基于时间的滑动窗口 大小始终等于用户需要的响应时自j 。例如窗口的长度为1 0 秒，即窗口内保存的是 1 0 秒种之内的全部元组，此时1 0 秒即为窗口的时间长度。 2 2 现有代价模型的分析与比较 在数据流查询处理机制中，比较典型且常用的查询优化方案是依据代价模型 进行操作符路径的优化选择。因为输入的元组经过不同的操作符路径，消耗的内 存，输出速率以及最终结果的时间延迟都是不相同的。 传统的d b m s 大都采用基于代价的优化方法。这种方法要求优化器需充分考 虑系统中的各种参数，如缓冲区的大小、表的大小、数据的分布、存取路径等。 通过某种代价模型计算出各种查询执行方案的执行代价，然后选取代价最小的执 行方案。通常在计算代价时主要考虑的是磁盘读取i o 数，而内存c p u 处理时间 在粗略计算时可不考虑经典的s y s t e mri 矧就采用了基于代价估算的查询优化 算法