（计算机应用技术专业论文）数据库查询优化技术研究及其应用.pdf

大连理工大学硕士学位论文 摘要 查询优化是数据库管理系统设计和实现所采用的一项重要技术，也是影响数据库系 统性能的一个重要因素，当前所有商用数据库都成功采用了这项技术。关系数据库系统 和非过程化的s q l 语言能够取得巨大成功，主要得益于查询优化技术的发展。对于一 个复杂的查询，寻找一个优化的执行策略是数据库系统开发成功的关键所在，此项研究 目前在数据库领域仍属于n p 问题。在查询执行的过程中，低效的s q l 查询语句、概貌 信息的匮乏、连接顺序的错误选择都是直接导致查询效率低下的原因。 本文以大连市公安局实际项目刑事审讯辅助决策支持系统为研究背景。该系统 将计算机技术应用于刑事审讯的全过程，包括审讯案例信息管理、审讯过程跟踪、以及 对已有的审讯经验的总结。 本文将遗传算法与模拟退火算法相结合，从而导出了一种基于遗传一模拟退火算法 的多连接查询优化算法，并将其应用于刑事审讯辅助决策支持系统中。该算法将查询计 划的一棵语法树看作是一个染色体，对于语法树上的连接操作后序遍历生成一个编码。 在所有编码构成的种群进行完选择、交叉、变异操作之后，在其中引入模拟退火机制， 从而进一步调整优化了种群，保持了群体的多样性，减少了用户查询的响应时间。 本文针对用户对查询效率要求较高的特点，对s q l 查询语句具体的执行过程进行了深 入地探讨。刑事审讯辅助决策支持系统中使用的s o l 语句采用的是基于代价的查询优化策 略，本文使用了收集统计数据的方法，定时对数据库中所有的表和索引进行分析。此外， 通过建立实视图的方法，对查询进行了重写。 关键词：查询优化；优化算法；遗传算法；模拟退火算法 大连理工大学硕士学位论文 q u e r yo p t i m i z a t i o no f d a t a b a s ea n di t sa p p l i c a t i o n a b s t r a c t q u e r yo p t i m i z a t i o ni sa ni m p o r t a n tt e c h n i q u ef o rd e s i g n i n ga n di m p l e m e n t i n gd a t a b a s e s y s t e m i ti sac r u c i a lf a c t o rt h a ta f f e c t st h ec a p a b i l i t yo fd a t a b a s e a tp r e s e n t ，t h i st e c h n i q u ei s s u c c e s s f u l l ya p p l i e di na l lc o m m e r c i a ld a t a b a s e s t h eg r e a ts u c c e s so f r e l a t i o n a ld a t a b a s ea n d s q lm a i n l yb e n e f i t sf r o mt h ed e v e l o p m e n to fq u e r yo p t i m i z a t i o nt e c h n o l o g y s e a r c h i n ga l l o p t i m i z e de x e c u t i v es t r a t e g yf o re v e r yc o m p l e xq u e r yi st h ek e yo fs u c c e s sf o rd a t a b a s e d e v e l o p m e n t i nd a t a b a s ef i e l d ，i ti ss t i l la nn pp r o b l e m i nt h ep r o c e s so fq u e r y ，i n e f f e c t i v e s q l ，s h o r t a g eo fs t a t i s t i c sa n di n c o r r e c tj o i no r d e ra r ea l lt h er e a s o n sf o rl o w e r i n gt h eq u e r y r a t e b a s e do nt h es t a t i s t i c sd i c t i o n a r ya n dt h em o d e l ，t h ev a l u e - b a s e dq u e r yo p t i m i z a t i o ni st o r e w r i t et h ei n e f f e c t i v es q la n ds e l e c tt h eb e s t j o i no r d e rf o rm u l t i - t a b l e s t h i sp a p e rt a k e sc r i m i n a li n t e r r o g a t i o na s s i s t a n c ed e c i s i o ns u p p o r ts y s t e ma sr e s e a r c h b a c k g r o u n d t h i ss y s t e ma p p l i e sc o m p u t e rt e c h n o l o g yi nt h ec r i m i n a li n t e r r o g a t i o ne n t i r e p r o c e s s ，i n c l u d i n gi n f o r m a t i o nm a n a g e m e n t ，p r o c e s st r a c k , a n ds u m m 撕e so ft h em a s s i v e c a s e se x p e r i e n c e t h i sp a p o rp u t sf o r w a r da ni d e ao fu s i n gg e n e t i ca l g o r i h t ma n ds i m u l a t e da n n e a l i n g a l g o r i t h mi n t oq u e r yo p t i m i z a t i o n t h i sa l g o r i h t mt a k e ss y n t a xt r e ea sac 1 1 r o m o s o m ea n di t s p o s t e r o r d e rs e a r c hr e s u l ti sac o d e a f t e rp o p u l a t i o nw h i c hi sm a d eu pw i t l lc b r o m o s o m e c o m p l e t ei t ss e l e c t , c r o s sa n dv a r i a t i o n ，w ew i l lc i t es i m u l a t e da n n e a l i n gm e c h a n i s m t h u st h e p o p u l a t i o ni sb eo p t i m i z e dm u c h m o r e a tt h es a m et i m e , t h ep o p u l a t i o nk e e p si t sd i v e r s i t ya n d r e d u c i n gr e s p o n s et i m eo f t h ec u s t o m e r a c c o r d i n gt ot h ef a c t u a lp r o b l e mo fq u e r ye f f i c i e n c yi nc r i m i n a li n t e r r o g a t i o na s s i s t a n c e d e c i s i o ns u p p o r ts y s t e m ，t h i sp a p e ra n a l y z e sd e t a i l e d l yt h ec o n c r e t e l ye x e c u t i v ep r o c e s so f s q ls t a t e m e n tr e f e r e n c et ot h ec h a r a c t e r i s t i co fd a t a b a s eq u e r y ，c r i m i n a li n t e r r o g a t i o n a s s i s t a n c ed e c i s i o ns u p p o r ts y s t e ma d o p t sr u l e - b a s e do p t i m a t i o n ，s ow ec o l l e c ts t a t i s t i c s g e n e r a lp i c t u r e ，a n da n a l y z er e l a t i o na n di n d e xo f t h ed a 诅b a s e t h e r ea r es e v e r a ls c h e m e s ，s u c h a s “a u t o m a t i n gs t a t i s t i c sm a n a g e m e n tf o rq u e r yo p t i m i z e r s ，“r e w r i t i n gt h es q ls t a t e m e n t k e yw o r d s ：q u e r yo p t i m i z a t i o n ；o p t i m i z a t i o na l g o r i t h m ；g e n e t i ca i g o r i h t m ； s i m u l a t e da n n e a l i n ga l g o r i t h m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：立l 亚丝日期：堑：1 2 压 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用规 定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名 导师签名 立l 翌仫 鱼丛年上月日 数据库查询优化技术研究及其应用 引言 数据库系统是信息系统的核心，企业在项目实施后，面临的一个重要挑战就是如何提 高性能。在多年的实践看来，由于初期的数据库中表的记录数比较少，性能不会有太大问 题，但数据积累到一定程度，达到数百万甚至上千万条，全表扫描一次往往需要数十分钟， 甚至数小时。如果用比全表扫描更好的查询策略，往往可以使查询时间降为几分钟。目前 数据库系统应用中，查询操作占了绝大多数，查询优化成为数据库性能优化最为重要的手 段之一。 现在的数据库产品在查询优化方面已经做得越来越好，但由用户提交的s q l 语句是 系统优化的基础，很难设想一个原本糟糕的查询计划经过系统的优化之后会变得高效， 因此用户所写语句的优劣至关重要。本选题就是要对大连市刑事审讯辅助决策支持系统 中的数据库查询进行优化，以提高查询的执行效率。 ( 1 ) 选题背景 数据库系统中，用户使用一些非过程化的高级语言表示查询，用户仅仅指出他所需 要的数据，而没有指出通过哪些路径来得到这些数据，这样数据库管理系统必须对用户 的查询进行转换，将其转变为一系列可行的机器操作，并为这些操作选择较优的存取路 径。 查询计划是用户所提交的s q l 语句的集合，它是经过优化处理之后所产生的。 d b m s 处理查询计划的过程是这样的：在做完查询语句的词法、语法检查之后，将语句 提交给d b m s 的查询优化器，优化器做完代数优化和存取路径的优化之后，由预编译 模块对语句进行处理并生成查询计划，然后在合适的时间提交给系统处理执行，最后将 执行结果返回给用户。在实际的数据库产品( 如o r a c l e 、s y b a s e 等) 的高版本中都是采用 基于代价的优化方法，这种优化能根据从系统字典表所得到的信息来估计不同的查询计 划的代价，然后选择一个较优的计划。 多连接查询是查询优化领域面临的一个重大难题。它的查询计划的数量会随着参与 连接的关系数目的增加而成指数倍的增长，它的计算复杂性是非常高的。但在应用领域， 如专家系统、数据仓库、数据挖掘等，又都涉及大量的多连接查询，我们处理多连接查 询的效率直接影响到系统的性能。 ( 2 ) 本文的主要工作 本文结合数据查询的特点，对s q l 语句具体的执行过程迸行了详细地剖析，并且 分析了查询优化的发展现状，给出在大量数据查询过程中可以提高效率的地方。分析了 大连理工大学硕士研究生学位论文 分布式数据库查询优化要考虑的问题，然后描述了分布式数据库查询优化的过程，给出 了刑事审讯辅助决策支持系统中可以选择的分布式查询策略。 研究了刑事审讯辅助决策支持系统中的查询重写，提出用实视图重写该系统中的 s q l 语句，从重写的结果可以看出，重写后，s q l 语句返回的结果明显减少，提高了用 户查询的效率。本文分析了五种典型的查询优化算法在刑事审讯辅助决策支持系统的应 用实例，并对它们的查询开销进行了深入的讨论。 在现阶段查询优化的研究过程中，当我们处理连接关系较多时连接顺序的优化问题 时，很多成熟的优化算法被引入到查询优化中，如爬山算法、模拟退火算法、遗传算法， 都在一定程度上提高了查询优化的性能。本文将遗传算法、模拟退火算法同时应用于刑 事审讯辅助决策支持系统中，并通过实验说明算法在提高查询效率方面的优越性。传统 的遗传算法中，高于群平均的模式在下一代中会获得较多的取样，一旦某些模式在群中 占有优势，这种优势就会得到强化，群会迅速收敛，不一定会达到全局最优。在其中引 入模拟退火机制，就可以进一步调整优化种群，有利于保持群体的多样性，可以使传统 的遗传算法获得更好的性能。 ( 3 ) 本文的组织 本文共分五章，引言部分介绍了查询优化在数据库系统开发过程中研究和实现的必 要性、本文的主要工作以及文章的结构。 第1 章对数据库查询的基本理论做了一个简要的介绍，并讨论优化研究的主要内容 及目标，针对目前应用十分广泛的分布式数据库，分析了分布式数据库查询优化要考虑 的问题，然后描述了分布式数据库查询优化的过程，最后总结了分布式查询处理常常选 择的策略。 第2 章研究了刑事审讯辅助决策支持系统中的查询重写，提出用实视图对该系统中 的s q l 语句进行重写，从重写的结果可以看出，重写后，s q l 语句返回的结果明显减 少，从而提高了用户查询的效率。 第3 章分析了包括基于关系代数等价变换的优化算法、s d d1 算法、基于查询图的 贪婪算法在内的五种查询优化算法在刑事审讯辅助决策支持系统中的应用实例，并对它 们的查询开销进行了深入的讨论。 第4 章将遗传算法与模拟退火算法结合到一起，从而导出了一种基于遗传一模拟退 火算法的查询优化算法，并将其引入到刑事审讯辅助决策支持系统中，从而减少用户查 询的响应时间。 第5 章基于刑事审讯辅助决策支持系统这个实际的项目，由项目的特征出发，给出 具体s q l 优化策略，从而提高用户使用的效率。 大连理工大学硕士学位论文 1 数据库查询优化技术概述 1 1 查询优化技术概略 1 1 1 查询优化的基本概念 所谓查询优化，就是在查询执行引擎生成一个执行策略的过程中，尽量使查询的总 开销和总时间达到最小。 实际系统对查询优化的具体实现不同，但一般来说，可以归纳为四个步骤： ( 1 ) 将查询转换成某种内部表示，通常是语法树。 ( 2 ) 根据一定的等价变换规则把语法树换成优化( 标准) 形式。 ( 3 ) 选择底层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的 存储分布、存储数据的聚簇等信息来选择具体的执行算法。 “) 生成查询计划。查询计划是由一系列内部操作组成的，这些内部操作按照一定 的次序构成查询的一个执行方案，通常这样的执行方案有很多个，需要对每个执行计划 计算代价，从中选择代价最小的一个。 其过程如图1 1 所示。 图1 1 1 查询优化处理过程 f i g 1 1p r o c e s so f q u e r yo p t i m i z a t i o n 查询计划是用户所提交的s q l 语句的集合，执行计划是经过优化处理之后所产生 的语句集合。d b m s 处理查询计划的过程是这样的：在做完查询语句的词法、语法检查 数据库查询优化技术研究及其应用 之后，将语句提交给d b m s 的查询优化器，优化器做完代数优化和存取路径的优化之 后，由预编译模块对语句进行处理并生成执行计划，然后在合适的时间提交给系统处理 执行，最后将执行结果返回给用户。在实际的数据库产品( 如o r a c l e 、s y b 船e 等) 的高版 本中都是采用基于代价的优化方法，这种优化能根据从系统字典表中所得到的信息来估 计不同的查询计划的代价，然后选择一个较优的执行计划【1 1 。许多程序员认为查询优化 是数据库管理系统( d b m s ) 的任务，与程序员所编写的s q l 语句关系不大，这是错误的。 一个好的查询执行计划往往可以使程序性能提高数十倍。 查询优化器的主要任务是控制和加快查询执行和数据传输的过程。然而，查询优化 一直是个复杂的问题，理想的、全面的查询优化几乎是不可能的。许多专家和学者在这 一领域曾做出过不少的研究和探讨，但总的说来，不尽人意，往往只能达到局部目标的 查询优化效果，甚至有些理论并不适用。 目前，有很多的数据库产品在查询优化方面，已经作了大量的工作，下面我们就以 o m l e 为例，说明它是如何进行查询优化的。 o r a c l e 优化器为s q l 语句选择最佳的执行计划，其工作原理如下【2 1 ： ( 1 ) 分析并估计s q l 语句的执行时间。 如果s q l 语句很复杂，优化器可能会修改s o l 语句使之具有更高效率。 ( 3 ) 如果s q l 语句需要访问一个视图，那么某些情况下，在执行优化操作之前，o r a c l e 优化器将把s q l 语句中的查询和视图查询结合在一起。 “) 在基于成本的优化方法和基于规则的优化方法之间做出选择。 ( 5 ) 优化器为s q l 语句使用的表选择一个或多个访问路径。 ( 6 ) 优化器选择表的连接顺序。 ( 7 ) 优化器选择最佳连接操作。 虽然现在的数据库产品在查询优化方面已经做得越来越好，但由用户提交的s q l 语句是系统优化的基础，很难设想一个原本糟糕的查询计划经过系统的优化之后会变得 高效，因此用户所写语句的优劣至关重要。由于s q l 语言是面向结果而不是面向过程 的查询语言，所以一般支持s q l 语言的大型关系型数据库都需要使用一个基于成本的 优化器，为即时查询提供一个最佳的执行策略。对于优化器，输入是一条查询语句，输 出是一个执行策略。这个执行策略是执行这个查询所需要的一系列步骤。数据库的反应 速度经常就体现在这一个优化算法上。不同的查询策略和查询步骤可使服务器的反应不 同，因此采用适当的查询策略可使系统性能大大提高。优化器的优化是基于用户对所查 询表的内容和其他一些与服务器有关的因素，如c a c h e 大小、c a c h e 策略、m d 大小等。 硬盘访问是成本最高的操作，因此对用户来讲，使优化器对字段索引进行操作是优化查 大连理工大学硕士学位论文 询的关键。s q l 查询语句都可以有很多种执行策略，优化器将估计出全部的执行方法中 所需时闯最少的也就是所谓成本最低豹一种方法。最为重要的选择就是使用什么索引和 采用何种的连接手段，而所有优化的进行都是基于用户所使用的查询语句中的w h e r e 子 句。 查询优化既是数据库系统实现的关键技术又是关系系统的优点所在，它减轻了用户 选择存取路径的负担，用户只要提出“干什么”，不必指出“怎么干”。 1 1 2 关系查询语言 数据库系统研究的主要目标是尽可能地对用户隐藏数据结构的细节，使数据库系统 的应用更能面向各个领域；分布式数据库研究的主要目标是隐藏分布式环境的细节，使 系统用起来更加简单、有效。分布式数据库系统应向用户提供个统一的访问数据接口。 关系数据模型可以为数据库提供一个数据无关的接口，关系数据库语言是关系演算，进 行数据查询时，只需对要查询的数据进行简单的描述，而无须说明如何获取这些数据。 s o l 语言就是这样一种通用的关系数据库语言，使用它进行数据库查询，用户可以方便 快捷的获取数据，但是使用这种语言，同样也需要对搜索、存取操作以及数据传输过程 进行必要的说明，因此相应的查询优化技术的研究也在不断进行中。 关系数据库是目前使用最广泛的数据库系统，2 0 世纪7 0 年代以后开发的数据库管 理系统几乎都是基于关系的。在数据库发展史上最重要的成就就是关系模型。关系数据 库中包括很多关系( 表) ，用户可以通过关系来表示数据以及数据之间的联系。每个关 系模式描述了关系的名称，关系中的属性以及每个属性的域。通常将查询语言分为过程 性的和说明性的。在过程性查询语言中，用户为了获得预期的结果必须制定一系列要执 行的操作；而在说明性语言中，用户只要描述想要得到的结果，而不用指定得到这些结 果的具体操作过程。 关系代数是关系模型中最为著名的过程性查询语言，是关系操纵语言的一种传统表 达方式，它是用对关系的运算来表达查询的，关系代数的运算按运算符的不同可分为传 统的集合运算和专门的关系运算吼 传统的集合运算是二目运算，包括并、差、交、广义笛卡尔积四种运算。 专门的关系运算包括选择、投影、连接、除等。 1 1 3 查询优化的具体实例 下面我们看一个刑事审讯辅助决策支持系统中的简单例子，说明为什么要进行查询 优化。 例：“嫌疑人案件”数据库中包括三个表： 数据库查询优化技术研究及其应用 ( 1 ) 嫌疑人基本情况表( 嫌疑人号，嫌疑人名，性别，年龄，籍贯) ( 2 ) 案件类别情况表( 案件号，案件名，犯罪级别，应判年限) ( 3 ) 嫌疑人犯罪情况表( 嫌疑人号，案件号，犯罪年份) 以下为了叙述方便，分别将表( 1 ) 、( 2 ) 、( 3 ) 简记为a 、b 、c ，n a n l c 表示嫌疑入姓名， x n o 代表嫌疑人号a l l o 表示案件号。 求犯了2 号罪名的嫌疑人姓名。用s q l 语言表达为： s e l e c ta n a t t l e f 如m a c w h e r ea m o - = c x n oa n dc a n o = 2 ： 假定“嫌疑人案件”数据库中有1 0 0 0 个嫌疑人基本情况记录，1 0 0 0 0 个嫌疑人犯罪 情况记录，其中犯了2 号罪名的犯罪记录为5 0 个。系统可以用多种等价的关系代数表 达式来完成这一查询，分析这三种就足以说明问题了。通过例子，将看到由于查询执行 策略的不同，查询时间相差很大，相应的语法树如图1 2 所示。 ( 1 ) q i = p j n a m e ( s l ax n o , c m a l l d c 。闻( a c pc ) ) ( 2 ) q 2 = p jn a m e ( s l c m 瞅( an j nc ) ) ( 3 ) q 3 = p jn r l n e ( an j ns l c “嗍( c ) ) s l a m o ：- x n o 拍d c 锄碑 c p 。： p j n a r n e ( a ) 语法树一( b ) 语法树二 图1 2 三种等价的查询语法树 f i g 1 2t h r e ek j n do f e q u a l q u e f ys y n t “仃e e s l c 彻。宅 a c ( c ) 语法树三 ( 1 ) 第一种情况 计算广义笛卡尔积。把a 和c 的每个元组连接起来。一般连接的做法是：在内 存中尽可能多地装入某个表( 如a 表) 的若干块元组，留出一块存放另一个表( 如c 表) 的 n l町 t 入 吨 f c 。 a 大连理工大学硕士学位论文 元组。然后把c 中的每个元组和a 中每个元组连接，连接后的元组装满一块后就写到 中间文件上，再从c 中读入一块和内存中的s 元组连接，直到c 表处理完。这时再一 次读入若干块a 元组，读入一块c 元组，重复上述处理过程，直到把a 表处理完。设 一个块能装l o 个a 元组或1 0 0 个c 元组，在内存中存放5 块a 元组和l 块c 元组，则 读取总块数为：1 0 0 0 1 0 + 1 0 0 0 ( 1 0 5 ) 1 0 0 0 0 1 0 0 = 2 1 0 0 块，其中读a 表1 0 0 块。读c 表2 0 遍，每遍1 0 0 块。若每秒读写2 0 块，则总计要花1 0 5 秒。连接后的元组数为 1 0 3 * 1 0 4 = 1 0 7 。设每块能装l o 个元组，则写出这些块要花1 0 7 1 0 2 0 = 5 1 0 4 秒。 作选择操作。依次读入连接后的元组，按照选择条件选取满足要求的记录。假 定内存处理时间忽略。这一步读取中间文件花费的时间( 同写中间文件一样) 需5 1 0 4 秒。 满足条件的元组假设仅5 0 个，均可放在内存。 作投影。把第步的结果在嫌疑人名上作投影输出，得到最终结果。 因此第一种情况下执行查询的总时间1 0 5 + 2 5 1 0 4 * 1 0 秒。这里，所有内 存处理时间均忽略不计。 ( 2 ) 第二种情况 计算自然连接。为了执行自然连接，读取a 和c 表的策略不变，总的读取块数 仍为2 1 0 0 块花费1 0 5 秒。但自然连接的结果比第一种情况大大减少，为1 0 4 个。因此写 出这些元组时间为1 以1 0 2 0 - - - - 5 0 秒。仅为第一种情况的千分之一。 读取中间文件块，执行选择运算，花费时间也为5 0 秒。 把第步结果投影输出。 第二种情况总的执行时间= 1 0 5 + 5 0 + 5 0 = 2 0 5 秒。 ( 3 ) 第三种情况 先对c 表作选择运算，只需读一遍c 表，存取1 0 0 块花费时间为5 秒，因为满 足条件的元组仅5 0 个，不必使用中间文件。 读取a 表，把读入的a 元组和内存中的c 元组作连接。也只需读一遍a 表共 1 0 0 块花费时间为5 秒。 把连接结果投影输出。 第三种情况总的执行时间= 5 + 5 = 1 0 秒。 假如c 表的案件号字段上有索引，第1 步就不必读取所有的c 元组而只需读取案件 号- - 2 的那些元组( 5 0 个) 。存取的索引块和c 中满足条件的数据块大约总共3 4 块。若 a 表在嫌疑人号上也有索引，则第2 步也不必读取所有的a 元组，因为满足条件的c 记录仅5 0 个，涉及最多5 0 个a 记录，因此读取a 表的块数也可大大减少。总的存取 时间将进一步减少到数秒。这个简单的例子充分说明了查询优化的必要性，同时也给出 数据库查询优化技术研究及其应用 了一些查询优化方法的初步概念。如当有选择和连接操作时，应当先做选择操作，这样 参加连接的元组就可以大大减少。 1 2 查询优化研究的主要内容 ( 1 ) 数据库统计概貌的管理。统计概貌信息在生成执行计划过程中，起着非常重要 的作用。传统地，数据库是在假设每个属性都是独立的基础上建立统计概貌的，优化器 用这些统计概貌信息来生成执行计划。通常，这些方法会产生大量的估算错误，而且直 接导致最终执行计划效率的低下。如何选用有价值的统计信息，如何排除无用的统计信 息，如何使统计信息的维护费用达到最小，都是统计概貌管理所关心的而且急需解决的 问题。成功地建立一个“最有益”的统计概貌集合，对查询优化具有重要的意义f 4 , s j 。 ( 2 ) s q l 的查询重写。自从八十年代提出在查询优化过程中采用查询重写这一新技 术后，查询优化的研究范围进一步得到推广。同时查询重写是查询优化器的重要组成部 分，它将一个查询表示根据一定的规则，转换为另一个效率更高或更易于优化的查询表 达式【6 ，”。如何发现更多而有效的重写规则，也是当前查询优化研究的主要研究内容。 ( 3 ) 查询优化算法。对于优化算法的研究仍然是查询优化研究的一个难点和重点。 在关系数据库中，最难处理和优化的一个逻辑操作符是连接( j o i n ) ，由于多个关系连接 时可以有很多不同的次序，因此对应于查讯的执行计划的数目会随着该查询包含的关系 个数呈指数级增长，当关系个数很多时，将导致搜索空间极度膨胀，传统的数据采用的 大多是s y s t e mr 的空间搜索算法或其变形算法，这一般都是近乎于穷举的搜索算法。 在决策支持系统中，查询所涉及到的关系数目通常都很大，这将使得这类搜索算法毫无 用处。现在越来越多成熟的优化算法被引入到查询优化中来处理连接关系较多时的优化 河题，爬山算法、模拟退火算法、遗传算法，都在一定程度上提高了查询优化的性能。 ( 4 ) 分布式查询优化。现代数据库应用的发展，使得高性能的并行机或分布式系统 逐步取代传统的大型机进行大型数据库的管理和事务处理，但与此不适应的是，传统的 查询优化技术并没有考虑到并行性，从而不能最大限度地发挥并行机或分布式系统的能 力。因此t 当前的查询优化也将并行查询的优化作为研究重点，并行查询中主要考虑以 下三个问题： 专家模型的评估。由于查询将会是并行执行的，因此我们应该有一个新的专家 模型来评估一个并行执行计划的执行代价。 计划空间搜索算法的改进。并行执行计划的引入将大大增加执行计划的计划空 间，因此，也应该有一些适应于并行系统的搜索算法。 大连理工大学硕士学位论文 并行执行计划的表示。并行执行计划的表示在一定程度上也决定了执行计划的 执行步骤。 1 3 查询优化处理的目标 1 3 1 查询优化的总体目标 查询优化的总体目标是：选择有效的策略，求得给定关系表达式的值。 无论在集中式还是分布式环境中，查询执行策略都是根据对各种方案的期望性能进 行衡量来选择的。在集中式数据库中，典型的度量方法是计算输入输出操作的次数以及 c p u 的使用情况。在集中式数据库中，系统大都是运行在单c p u 的计算机上，所以查询总 代价为c p u 代价+ f o 代价。 查询优化可以分为基于查询执行代价的优化和基于查询响应时间的优化。基于查询 执行代价进行优化的目标是，使查询执行所使用的系统资源总和尽量地少，从而降低系 统开销，整个系统的开销可以从单个系统资源的开销表达式中推出；基于查询响应时间 优化的目标是尽量减少查询的响应时间，而不计较系统资源的耗费。 1 3 2 分布式查询优化的目标 分布式数据库系统中，虽然数据存在分布透明性，但是我们在查询处理中仍然要考 虑站点间传输数据的通信费用，所以相对于集中式数据库来说，它的总代价除了考虑 c p u 代价和f o 代价之外，还应考虑数据在网络上的传输代价，即：总代价= c p u 代价+ i o 代价+ 通信代价。在分布式数据库中，则还必须考虑数据的传输量。然而，在传输的费 用和本地i o 的费用之间哪个更为重要没有统一的看法【羽。 本文认为只考虑传输方面的要求是很合理的，因为： ( 1 ) 传输要求对于系统是公平的，一般来说它们在站点之间传送的数据量的函数是 一致的。 ( 2 ) 一个分布式查询的优化可以分成为两个独立的问题： 站点之阃访问策略的分布； 每个站点处的本地访问策略，这可使用集中式数据库的传统方法。 各个问题是按上述次序来解决的，因为前者比后者更重要。 传输的要求可以根据费用和延迟这两方面来评价： ( 1 ) 当考虑费用时，一个应用的性能是用所有传输的费用之和来量度的。这个方法 相当于使通讯网络中的整个传输开销最小。 数据库查询优化技术研究及其应用 ( 2 ) 当考虑延迟，即响应时间时，一个应用的性能以用此应用从激活到完成所经历 的时间来度量的。减少延迟等于增加执行中的并行程度，不一定相当于使整个传输开销 最小。 1 4 分布式查询优化 1 4 1 分布式查询优化要考虑的问题 分布式数据库存在于网络环境中，由于数据的分布性，一次查询所操纵的对 象可能分布于不同的网络节点中，由此带来的开销和执行速度就会不一样，优化所要考 虑的因素就更为复杂。 在分布式数据库中，为了简化查询的执行，有五条应用于等价变换的一般准则【9 】： ( 1 ) 使用选择和投影的幂等来为每个操作数关系产生相应的选择和投影。 ( 2 ) 把算符树中的选择和投影运算尽可能向下推移。 ( 3 ) 把选择运算向下推到算符树的树叶处，然后对它们使用限定关系代数；如果结 果的限定语是永假式，则用空关系来代替此次选择的结果。 ( 4 ) 利用限定关系代数来求结合的操作数的限定语之值；如果结合结果的限定语是 永假式，则用空关系来代替此子树，包括此结合及它的操作数在内。 ( 5 ) 为了分布出现在全局查询中的结合，必须把并集向上推，超过我们要分布的结 合的范围。 分布式查询技术的复杂性并没有阻碍人们对它的研究和探讨，正是由于它涉及因素 的多样性和复杂性以及存在于网络环境的分布式系统的优点，决定了它应用的重要性和 广泛性。单位、组织、个人对资源共享的需求是推动其发展的动力，基于网络架构的分 布式数据库系统所具有的优点和扩展性、可用性和可靠性以及灵活性，吸引着越来越多 的探索者，并且已经成为当今计算机研究的热点课题。 分布式数据库环境中的查询优化与集中式数据库环境中的查询优化相比较，还要考 虑以下两个关键的问题： ( 1 ) 数据和信息均要通过通信线路进行传输，存在延迟的问题将减慢整个查询执行 过程。 ( 2 ) 网络中多处理器的存在提供了并行处理和传输的机会，应充分利用可以加快查 询相应的速度。 在分布式数据库系统中，由于许多相对独立的处理器可能参与数据库操作，这使得 它能够提供更多的处理机会。但这也同时增加了分布式数据库中各方面的复杂性。分布 大连理工大学硕士学位论文 特性的存在，除了带来通信开销外还影响到物理查询计划设计的复杂性和可选方案。在 选择物理查询计划时必须考虑的问题包括 1 0 , 1 1 】： ( 1 ) 如果某个所需的关系r 有多个副本，那么应该从哪个副本中获得r 的值。 ( 2 ) 当在两个关系r 和s 上实施某个操作时，若有多个可选方案时，我们应该选择 哪个。 ( 3 ) 在分布式数据库中，数据在网络上的传输代价为c p u 代价、i o 代价、通信代 价的总和，网络通信代价会随着用户数目或负载的变化而改变，所以，在分布式数据库 中，更应考虑通信代价。但当某个数据库的查询负载过高时，我们则要牺牲一定的通信 代价来提高执行的并行度。 1 4 2 分布式查询优化过程 分布式查询优化已经开展了很多年，从各种应用角度，不同的学者进行了很多相关 的工作，但所有的工作都可以归分为两种基本的方法1 1 2 , 1 3 ： ( 1 ) 通过减少分布式查询中数据传输的数量来降低传输的费用。 ( 2 ) 用并行技术来降低反应时间。 图l 。3 分布式查询优化处理过程 f i g 1 3p r o c e s so f d i s t r i b u t e x lq u e r yo p t i m i z a t i o n 图1 3 的结构体现了分布式查询处理的各个阶段，这个查询从用户输入s q l 语句开 始，然后由解析器翻译，并进行优化，使之成为一个可以执行的查询计划，行资源生成 器执行这个计划，最后得出查询的结果。下面给出处理过程中的每一步的完成的功能。 数据库查询优化技术研究及其应用 ( 1 ) 解析器。在这个阶段，查询语句被解析成查询的内部表示，以便后面的各阶段 的处理。 ( 2 ) 基于规则的优化器。又可以称为查询重写器。根据规则删除语句的一些冗余的 信息，简化表达式、子查询和视图。语句在这一步，进行了简单的优化。在分布式数据 库系统中，查询重写器还能够选出那些要参与查询操作的数据库表。 ( 3 ) 基于代价的查询优化器。负责主要的优化工作，根据数据库的统计概貌信息， 选择执行查询语句中涉及到的操作运算的次序，如何为每个操作分配内存。在分布式数 据库中，这一步还必须能够选择每个操作的执行站点。为了完成这一系列的选择，查询 优化器会枚举出所有可能的执行计划，根据每个查询计划的代价估计，选择最优执 亍计 划。 ( 4 ) 字典表。数据库的统计描述，它保存了数据库的模型信息，如表定义、视图、 用户自定义类型和函数、约束等。基于代价的查询优化器在生成执行计划时，将其作为 进行定量分析的参考。它通常包含元组的数目、属性的大小和对于不同属性的不同值的 数目。在分布式数据库系统中，还通常包括关系的站点信息。 ( 5 ) 执行计划。一个执行计划描述一个查询请求是如何具体地被执行，几乎所有的 数据库系统都用同样的方法来表达查询计划语法树。树的叶节点是每个需要操作的 关系；树的中间节点就是查询计划中的每次操作的操作符，每个操作符代表一个特定的 操作( 如选择、投影、连接等) 。在分布式数据库中，还要考虑同一关系表的不同的分段。 图1 4 给出一种不同站点之间的查询处理过程。表彳和表占在各自站点进行投影( 或选 择) 操作后，将需要进行连接的数据记录传输到执行站点。 图1 4 分布式查询的传输 f 龟1 4t h e 怕m f o m io f d i s 口i b u t e dq u e r y ( 6 ) 全局信息表。全局信息表储存了分布式站点用于解析、重写和优化各阶段所需 的所有信息。保存了数据库分布信息、全局分段和重构规则和表的物理存储位置。在集 中式数据库中，字典表可以提供查询优化所需的信息，而在分布式数据库系统，这样一 大连理工大学硕士学位论文 个全局信息表是必不可少的。通常把它存储在一个站点上，如图1 4 ，存储在“执行站 点”上，但在一般的广域网络上，为了减少通讯代价，可以制作几个副本分别存放在一 个站点上，使站点1 、站点2 和执行站点都有一个备份。 ( 7 ) 行资源生成器。根据最终确定的执行计划，访问数据库获得查询结果返回给用 户。在分布式数据库中，还要考虑同一关系表的不同的分段。 1 4 3 分布式查询处理的策略选择 由于不同的查询策略通信时间相差很大，有的甚至达数个量级。因此查询策略的选 择尤为重要。一个好的查询策略应该使数据的传输量和通信次数减少，以减少数据传输 和通信的时间，从而减少查询的总代价。 ( 1 ) 简单的连接处理 选取1 2 3 中“嫌疑人案件”数据库中的三个表，考虑下面的关系代数表达式： 嫌疑人基本情况表j n 嫌疑人犯罪情况表案件类别情况表，假设这三个关系既没有被 复制，也没有被分段，且“嫌疑人基本情况表”存储在站点s i 上，“嫌疑人犯罪情况 表”存储在站点s 2 上，“案件类别情况表”存储在站点s 3 上。s 1 是提出查询的站点， 系统需要在s 1 上产生结果。由于j n 的条件一般为它所连接的两个关系相同字段的属性 值相等，以后为简便起见，我们省略它们的连接条件。那么这个查询可以采取这样几种 策略【1 4 l ： 将三个关系的副本都送到s l 上，对它们进行集中式的查询处理技术，在s l 站点 上处理整个查询。 将“嫌疑人基本情况表”的一个副本送到站点s 2 上，在s 2 上计算t e m p 尸嫌疑 入基本情况表j n 嫌疑人犯罪情况表。将t e m p ，从s 2 送到s 3 ，再在s 3 上计算t e m p 2 = t e m p l j n 案件类别情况表，最后将结果t e m p 2 送到s 1 。 设计一个与类似的策略，只是交换s i 、s 2 、s 3 的角色。 到目前为止，没有一种策略在任何环境下都是最优的。考虑上面列出的第一种策略， 如果我们将三个关系都送到站点s l 上，并且在这些关系上都存在索引的话，那么我们 就可能需要在s i 上重新创建索引，这样就会带来额外的处理开销和磁盘访问。再看第 二种策略，由于我们不知道t e m p l 、t e m p 2 的大小，所以可能导致一个很大的关系在网络 上的传输，增加了额外的网络传输的费用。综合以上考虑，我们应该具体问题具体分析， 针对不同的查询处理，采取不同的策略。 ( 2 ) 半连接策略 设r 和s 是两个关系，则它们的半连接表示为 数据库查询优化技术研究及其应用 r s j f s = p j a t t r ( r ) r j n f s = p j a t t r f ：o 僻j n fp j c 回 其中f 是说明连接谓语的公式，a t t r ( r ) 表示r 的全部属性，c 为r 与s 相同的属性 集。因此，半结合的结果是r 的元组的子集，它只选择对r 与s 的连接有贡献的那些元 组。 利用前边的“嫌疑人案件”数据库中的表，假设我们希望查询一下嫌疑人的犯罪 情况，即计算“嫌疑人基本情况表j n 嫌疑人犯罪情况表”其中“嫌疑人犯罪情况表” 在站点s l 上，“嫌疑人基本情况表”在站点s 2 上，我们希望结果产生在s 2 上。如果“嫌 疑人基本情况表”中有许多元组不能和“嫌疑人犯罪情况表”中的任何元组连接，那么 把“嫌疑人基本情况表”送到s i ，会使我们传送一些对于查询没有贡献的元组，所以我 们应该在传送之前去掉这些元组，特别是在网络代价比较高的时候，这样做就显得更加 重要。此时我们就可以采用前边提到的半连接策略。 我们可以设计如下的策略： 在s 2 上计算t e m p i = p j - 疑人嫌疑人基本情况表。 将t e m p l 由s 2 送到s i 。 在s 1 上计算船坍阮= 嫌疑